Algopy - Incorrect derivative for functions with conditionals

[AlgoDiff]

I have been testing algopy for the last one week. I have a question around functions which have an "if" condition. Consider this script -

import algopy
def max_organic(x1,x2):
    if x1 > x2:
        y = x1
    else:
        y = x2
    return y

cg = algopy.CGraph()
x1 = algopy.Function(3.0)
x2 = algopy.Function(2.0)
y = max_organic(x1, x2)
cg.trace_off()
cg.independentFunctionList = [x1, x2]
cg.dependentFunctionList = [y]

print "Function = ", cg.function([118.0, 9.0])
print cg.gradient([[6.0], [3.0]])

Function =  [9.0]

[array([ 0.]), array([ 1.])]

This script yields wrong results. Are conditionals not handled since they lead to vector valued function? Any help is highly appreciated.

[Sebastian Walter]

Hello Tarun,

AlgoPy stores the sequence of elementary functions in an instance of CGraph.

However, an if-then-else statement is **not** considered to be an elementary function.

So, AlgoPy will simply record the elementary functions that are performed when a **certain** control flow is executed.

In other words,  AlgoPy won't know about the other possible control flows.

No matter what inputs you provide, cg.gradient will always execute the sequence of operations that were recorded when you traced the function.

You can output the sequence of operations by ```print cg```

Your options are:

1) use the forward mode, i.e., use the UTPM.init_jacobian and UTPM.extract_jacobian to compute the gradient. In that case, no computational graph is recorded, so the problem with the program branches does not exist.

2) Create two copies cg1, cg2, each one containing the computational graph of the particular control flow.

3) Extend AlgoPy to support control flows within the computational graph. 

kind regards,

Sebastian

--
You received this message because you are subscribed to the Google Groups "algopy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to algopy+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[AlgoDiff]

Hello Sebastian,

Thanks very much for your reply - it was very helpful. Here are a few followup questions -

1. Other than conditionals, what about loops (while, for) etc? They seem to be handled - but would like to verify. Any documentation which lists the limitations of the reverse mode AD.
2. I had guessed that the cg would be created using the initial input values with which it were traced. However, check the example script I posted. I use x1=3.0, x2=2.0 to trace the graph. This should execute the path y = x1. This means that the partial w.r.t. to x2 should be always zero. However, when I call gradient with values x1=6 and 2=3.0, I get a gradient wrt to x2 = 0. Why is that? Does the inclusion of "if" condition mess up the trace?
3.  I like the idea (2) and I will proceed using that in the time being. However, I would like to extend algopy to include (3). 
1. Is there any documentation which explains how the cg is created/traced and how is it stored? 
2. Why weren't conditional branches not included in your version? What made its support complex?
3. How hard is it to add conditional branches? Any pointers on extending your cg will serve very helpful.
4. I believe algopy was inspired by ADOL-C. Once I have built a prototype of my application using algopy, I would want to move to a C++ tool. Does ADOL-C have similar limitations wrt to conditionals or code that branches? Do you have any recommendations about which C++ tool to start with?

Thanks a lot again!

[Sebastian Walter]

On Sun, Jul 28, 2013 at 10:43 AM, AlgoDiff <tarun...@gmail.com> wrote:

Hello Sebastian,

Thanks very much for your reply - it was very helpful. Here are a few followup questions -

1. Other than conditionals, what about loops (while, for) etc? They seem to be handled - but would like to verify. Any documentation which lists the limitations of the reverse mode AD.

if the number of loop repetitions is constant you are fine. E.g.,

for i in range(10):

   do something

would be OK.

However, not OK would be:

def f(x):

    while x < 10:

        x *= 2

    return x

since then the sequence of elementary functions *= depends on the input value.

Once you have traced the function evaluation, the sequence of operations is fix.

 

1. I had guessed that the cg would be created using the initial input values with which it were traced. However, check the example script I posted. I use x1=3.0, x2=2.0 to trace the graph. This should execute the path y = x1. This means that the partial w.r.t. to x2 should be always zero. However, when I call gradient with values x1=6 and 2=3.0, I get a gradient wrt to x2 = 0. Why is that? Does the inclusion of "if" condition mess up the trace?

I should have read your email more carefully! You are absolutely right, this doesn't make sense.

Explanation: comparison operators <, >, <=, >= were, as of now, not implemented for Function objects.

Python uses the memory address to compare objects by default. Thats why it can happen that Function(3.) < Function(2.).

I have now added the missing comparison operators, so your test example should work. Can you download a recent version from 

https://github.com/b45ch1/algopy and verify?

1.  I like the idea (2) and I will proceed using that in the time being. However, I would like to extend algopy to include (3). 
1. Is there any documentation which explains how the cg is created/traced and how is it stored? 

The general idea is the following:

1) each Function object has the following attributes:

Function.ID

Function.args

Function.func

Function.x

2) an elementary operation such as Function.__add__(self, other)

creates a new Function f, where

f.ID is some unique id

f.args = [self, other]

f.func = operator.add

f.x = f.func(self.x, other.x)

i.e., the numerical value is stored in f.x.

3) Additionally, the CGraph instance cg stores a list of all Function nodes in cg.functionList.

You can plot the computational graph using cg.plot.

 

1. Why weren't conditional branches not included in your version? What made its support complex?
2. How hard is it to add conditional branches? Any pointers on extending your cg will serve very helpful.

The problem is that the control flow statements if, for, while, etc. cannot be "overloaded" in Python, 

so there is no possibility to automatically add an "if" statement to the computational graph.

 

1. I believe algopy was inspired by ADOL-C. Once I have built a prototype of my application using algopy, I would want to move to a C++ tool. Does ADOL-C have similar limitations wrt to conditionals or code that branches? Do you have any recommendations about which C++ tool to start with?

ADOL-C also doesn't support control flow statements. 

It has, however, a function called condassign  which can be used to "emulate" control flow statements.

You could also try pyadolc, the Python interface to ADOL-C. 

https://github.com/b45ch1/pyadolc/blob/master/adolc/tests/test_wrapped_functions.py#L190

Of course, one could also add similar support to AlgoPy. 

Sebastian

[AlgoDiff]

Sebastian,

 

I verified your fix and it works as you outlined. Thanks!