AlgoPy-automatic differentiation for Python programs

Note: There was failure in running the example in my system consisting of Python 2.7 and the 0.3.1 version of AlgoPy.

Introduction

I had a problem determining the gradient of the ordinal logistic model and I could not find online references on the formula for the gradient. You see it takes around 6 seconds to compute the parameters of model using the BFGS (Broyden, Fletcher, Goldfarb, Shanno) optimizer.

I have heard of ADOL-C before for automatic differentiation, in fact I was browsing the second hand Book Sale and I found a reference book with Java-Forte programs on a CD. That turned me off, since Forte is relative old IDE and I decided NOT to buy it. So lets try an automatic differentiation package for Python.


The home page is at http://packages.python.org/algopy/ homepage.

The documentation at the homepage states the purpose of AlgoPy nicely:


The purpose of AlgoPy is the evaluation of higher-order derivatives in the forward and reverse mode of Algorithmic Differentiation (AD) of functions that are implemented as Python programs. Particular focus are functions that contain numerical linear algebra functions as they often appear in statistically motivated functions. The intended use of AlgoPy is for easy prototyping at reasonable execution speeds. More precisely, for a typical program a directional derivative takes order 10 times as much time as time as the function evaluation. This is approximately also true for the gradient.

Capabilities of AlgoPy

AlgoPy promises to compute the following if possible the following:

• evaluation of derivatives useful for nonlinear continuous optimization
  
• gradient
  
• Jacobian
  
• Hessian
  
• Jacobian vector product
  
• vector Jacobian product
  
• Hessian vector product
  
• vector Hessian vector product
  
• higher-order tensors
  
• Taylor series evaluation
  

Installation

I am using the latest Ubuntu OS ( march 24, 2012
Oneiric Ocelot) on my laptop which serves as my main computer. Try to see the version of your installed default Python by issuing python --version. I see that I have 2.7.2+ Now try this:

sudo easy_install-2.7 algopy

That's all! Here are the terminal output messages

sudo easy_install-2.7 algopy
Searching for algopy
Reading http://pypi.python.org/simple/algopy/
Reading http://packages.python.org/algopy
Reading http://www.github.com/b45ch1/algopy
Best match: algopy 0.3.1
Downloading http://pypi.python.org/packages/source/a/algopy/algopy-0.3.1.zip#md5=84edf4722e0f67ae254d663906893ff5
Processing algopy-0.3.1.zip
Running algopy-0.3.1/setup.py -q bdist_egg --dist-dir /tmp/easy_install-SvuPun/algopy-0.3.1/egg-dist-tmp-8pSEhA
.dev
warning: manifest_maker: MANIFEST.in, line 1: 'recursive-include' expects    ...

zip_safe flag not set; analyzing archive contents...
algopy.__init__: module references __file__
algopy.tracer.tests.environment: module references __file__
Adding algopy 0.3.1 to easy-install.pth file

Installed /usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg
Processing dependencies for algopy
Finished processing dependencies for algopy

Actually easy_install has three versions in my machine, namely easy_install easy_install-2.6 easy_install-2.7 I got the following error for instance by typing easy_install only:

sudo easy_install algopy
[sudo] password for toto: 
Traceback (most recent call last):
  File "/usr/local/bin/easy_install", line 5, in 
    from pkg_resources import load_entry_point
  File "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 2676, in 
    parse_requirements(__requires__), Environment()
  File "/usr/lib/python2.7/dist-packages/pkg_resources.py", line 552, in resolve
    raise DistributionNotFound(req)

It is much better to install easy_install to your system than downloading the tarred package from the homepage and unpacking and installing it via python setup.py install

Trying out an example

import numpy, algopy
from algopy import UTPM, exp

def eval_f(x):
    """ some function """
    return x[0]*x[1]*x[2] + exp(x[0])*x[1]

# forward mode without building the computational graph
# -----------------------------------------------------
x = UTPM.init_jacobian([3,5,7])
y = eval_f(x)
algopy_jacobian = UTPM.extract_jacobian(y)
print 'jacobian = ',algopy_jacobian

# reverse mode using a computational graph
# ----------------------------------------

# STEP 1: trace the function evaluation
cg = algopy.CGraph()
x = algopy.Function([1,2,3])
y = eval_f(x)
cg.trace_off()
cg.independentFunctionList = [x]
cg.dependentFunctionList = [y]

# STEP 2: use the computational graph to evaluate derivatives
print 'gradient =', cg.gradient([[3.,5,7]])
print 'Jacobian =', cg.jacobian([[3.,5,7]])
print 'Hessian =', cg.hessian([[3.,5.,7.]])
print 'Hessian vector product =', cg.hess_vec([[3.,5.,7.]],[[4,5,6]])

When the above is executed in my laptop, it prints to the console or terminal the following:

.
>>> import numpy, algopy
>>> from algopy import UTPM, exp
>>> 
>>> def eval_f(x):
...     """ some function """
...     return x[0]*x[1]*x[2] + exp(x[0])*x[1]
... 
>>> # forward mode without building the computational graph
... # -----------------------------------------------------
... x = UTPM.init_jacobian([3,5,7])
>>> y = eval_f(x)
>>> algopy_jacobian = UTPM.extract_jacobian(y)
>>> print 'jacobian = ',algopy_jacobian
jacobian =  [ 135.42768462   41.08553692   15.        ]
>>> 
>>> # reverse mode using a computational graph
... # ----------------------------------------
... 
>>> # STEP 1: trace the function evaluation
... cg = algopy.CGraph()
>>> x = algopy.Function([1,2,3])
>>> y = eval_f(x)
>>> cg.trace_off()

>>> cg.independentFunctionList = [x]
>>> cg.dependentFunctionList = [y]
>>> 
>>> # STEP 2: use the computational graph to evaluate derivatives
... print 'gradient =', cg.gradient([[3.,5,7]])
gradient = [array([ 135.42768462,   41.08553692,   15.        ])]
>>> print 'Jacobian =', cg.jacobian([[3.,5,7]])
Jacobian =
Traceback (most recent call last):
  File "", line 1, in 
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/tracer/tracer.py", line 262, in jacobian
    self.pushforward(utpm_x_list)
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/tracer/tracer.py", line 103, in pushforward
    f.__class__.pushforward(f.func, f.args, Fout = f)
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/tracer/tracer.py", line 637, in pushforward
    out  = func(*args)
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/utpm/utpm.py", line 73, in __getitem__
    tmp = self.data.__getitem__((slice(None),slice(None)) + tuple(sl))
IndexError: invalid index
>>> print 'Hessian =', cg.hessian([[3.,5.,7.]])
Hessian =
Traceback (most recent call last):
  File "", line 1, in 
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/tracer/tracer.py", line 349, in hessian
    self.pushforward(utpm_x_list)
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/tracer/tracer.py", line 103, in pushforward
    f.__class__.pushforward(f.func, f.args, Fout = f)
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/tracer/tracer.py", line 637, in pushforward
    out  = func(*args)
  File "/usr/local/lib/python2.7/dist-packages/algopy-0.3.1-py2.7.egg/algopy/utpm/utpm.py", line 73, in __getitem__
    tmp = self.data.__getitem__((slice(None),slice(None)) + tuple(sl))
IndexError: invalid index
>>> print 'Hessian vector product =', cg.hess_vec([[3.,5.,7.]],[

Ouch, we have fatal errors! We do have the latest version of AlgoPy (0.3.1). But you may be luckier than me.

We are a little sorry for this post. But we will come back soon, we need to visit the mailing list or the algopy group (if there is). We will come back soon!