Automatic Differentiation

[jramapuram]

This would be cool: http://en.wikipedia.org/wiki/Automatic_differentiation
Theano uses this.

This should be a secondary objective. Initially (and for performance reasons) it will make sense to provide the derivatives of functions, however this feature will provide extensibility for later unknown model types.

[futurely]

The cost is longer compile time which is very counter-productivity especially for quick iterations of research and prototyping.

[jramapuram]

Yup, mentioned above already

[sherjilozair]

There is nothing fundamental about automatic differentiation that associates it with longer compile times. Some folks from Berkeley are implementing an alternative to Theano (rll.berkeley.edu/cgt/), which essentially solves the long compilation problem.

[botev]

So I've actually have already implemented a baby step of this, however an old version of it in Rust. As mentioned in #28 I find Arrayfire the perfect backend for this. Haven't check CGT by myself, but I can see it is still python based. I prefer a C++ version of this rather than python, and later it could be ported to other languages easily. However it requires also and some knowledge and expectation of the backend. I'm quite happy to work on it but wanted to hear what you guys think. Another nice part is that you can apply methods such as CRISP(https://cs.nyu.edu/web/Research/TechReports/TR1995-698/TR1995-698.pdf) which can benefit both for paralelization and memory usage on the device.

There isn't a specific literature on the topic, since it is quite simple. Have the optimization of the graph is not so trivial to do in constant number of passes. This usually include mathematical identity simplification, groupings, possible register allocations (or blobs of memory) and deciding which operations can be inlined. Any way I think for ML this is the standard since it gives you order of magnitute benefit on prototyping and research as well as run time speed. If the graph optimization is made well compilation times are going to be a few seconds longer, which if you get a boost in run time does not really matter.

[jramapuram]

I also suggest this post: http://colah.github.io/posts/2015-08-Backprop/index.html
The automatic differentiation doesn't need to be extremely fast. Most of the time all you need is symbolic derivatives after which you can substitute values back into the result (at a rapid rate).

[botev]

Mm in general you would want to do source generation, otherwise just substitution will mean that you will have to do manual GC on the graph, rather than let the compiler do what it does best.

I was wondering if I implement this on a purely graph based structure, what are the important parts of each node that would be required for ArrayFire to know? Usually each node has some meta data like:

• ndim
• shape (not necessarily constant might depend on some inputs)
• broadcastable dimensions
• operator (obviously)

Would it be required to explicitly know the device on which the memory will live or anything else that I'm missing (here please excuse me, but I really never used ArrayFire before, just yd started trying it).

[pavanky]

@botev We do most of what you suggest internally inside arrayfire's JIT engine. @jramapuram opened a ticket on upstream arrayfire library to perform Automatic differentiation.

I am fairly new to the subject. All I've seen / read so far is what other DNN libraries are doing to a certain extent. However I haven't yet figured out the scope of operations to support.

[botev]

Hmm, so could you point me to a document so that I can understand better what happens under the hood of array fire JIT. Are you building a symbolic graph of the computation? Or are you referring to storing the dim, shape, broadcasts etc of each variable?
I must say that I'm really quite far from low level HPC, so have no idea how you guys do the computation inside. To most extend what other DNN libraries do is defacto the same, just have different ways of expressing it. The most general currently is Theano, which represents gradients as operations on the graph (adding nodes), which imho is the best, since it allows to easily later to derive things like Hessain vector products in a very natural way. In terms of operations to be supported, in general the more you have the better. Ah, I can write lots on this topic, but as I said I'm a noob on HPC and have no idea how you guys manage stuff under the hood.

[jramapuram]

I think the tensorflow implementation is far superior to theano. Here is their whitepaper: http://download.tensorflow.org/paper/whitepaper2015.pdf

[pavanky]

@botev It is internal to arrayfire so it is not very well documented..

• This file is representative of how a node is constructed: https://github.com/arrayfire/arrayfire/blob/devel/src/backend/cuda/binary.hpp
  There are other types of nodes that expect a different input but create a node on the graph.
• This file shows how the graph is traversed and the (nvvm) code is generated:
  https://github.com/arrayfire/arrayfire/blob/devel/src/backend/cuda/jit.cpp
• This directory (only the .hpp files) have implementation of different types of nodes https://github.com/arrayfire/arrayfire/tree/devel/src/backend/cuda/JIT

[pavanky]

If I can understand the theory well enough, I think jit.cpp and header files inside JIT directory can be extended to implement automatic differentiation.

[botev]

@jramapuram The automatic differentiation part is the same. If you look at section 4.1 and observe a Theano graph with gradients you will see that the way that gradients are symbolically computed are exactly the same (this is also true for torch, cgt and almost any other good DNN library out there). The difference is in how they manage the exact computation, code generation, compilation etc later