4 ms·

OP here. This is a dense paper since it involves many concepts (abstract algebras, tensors, automata) and I don't fully grok it (not even close). The main poin

OP here. This is a dense paper since it involves many concepts (abstract algebras, tensors, automata) and I don't fully grok it (not even close). The main points seem to be: - Realization of the duality between programs and maps over vector space (simplification: assumes the real field). - Define differentiation for those programs. - Expand over current automatic differentiation approaches by having a well defined algebra, as opposed to a pure algorithmic translation of the chain rule by forward/backward propagation. - Since the differentiation operator is well defined, get higher-order derivatives "for free" . - Also, get composition of differentiable programs "for free". This formalization seem to have a lot of potential IMO by allowing generalization of techniques researchers have to currently "hand craft" in neural networks (control structures, recursion, composition).

kxyvr 10y ago
I skimmed their paper and don't claim to understand everything, but I am curious about some of your comments. As far as higher-order derivatives, there's not really been an issue with obtaining these derivatives with traditional automatic differentiation techniques. The hard part is how to compute them efficiently. For example, Hessian-vector products can be obtained via forward-over-reverse or reverse-or-forward methods, but one runs significantly faster than the other. What's not clear to me in this paper is the practical efficiency of their technique especially for high-order derivatives. Second, as far as neural networks, it's also not clear to me what's currently missing from using existing AD tools and what this new paper provides. Right now, there exist good AD tools that work just fine with control structures, recursion, and composition. In my opinion, a much better way to implement the training algorithms for machine learning is to just run an AD package on a particular model and then feed the resulting derivatives into an appropriate optimization algorithm. It's accurate, clean, and save time and effort. As such, what do we really gain from using this new methodology? That said, I appreciate that the authors put together some interesting abstractions that I'd not seen before in this context. I think it's worth a read even if just for that.
- hcarvalhoalves 10y ago
  > What's not clear to me in this paper is the practical efficiency of their technique especially for high-order derivatives. On section "5.3.1 Order reduction for nested applications": > We gained the ability of writing a differentiable program acting on derivatives of another program, stressed as crucial (but lacking in most models) by other authors [18]. See http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1370&context=ecetr http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1370&... for [18]. --- > Right now, there exist good AD tools that work just fine with control structures, recursion, and composition. See their example implementation (https://github.com/ZigaSajovic/dCpp https://github.com/ZigaSajovic/dCpp) to understand what "control structures, recursion and composition" mean in this context.
  - kxyvr 10y ago
    Thanks for the reply. Perlmutter and Siskind's paper doesn't really talk about the efficiency of higher-order derivatives either and only has a very simple run time for a gradient calculation. I had a look at the code and I can't figure out how their abstractions would allow for efficient higher-order derivatives. Even on the front page, they list the examples // df/dxdx std::cout<<"df/dxdx = "<<f.d(&x).d(&x).id<<std::endl; // df/dxdy std::cout<<"df/dxdy = "<<f.d(&x).d(&y).id<<std::endl; Generally, I think those abstractions make it hard to compute things like Hessian-vector products because we really need a reverse pass to generate either a program or computational tree that we can fly through with a forward pass. That involves giving an explicit instruction to run a reverse pass since we don't do it automatically since it's expensive. Also, we generally give an entire vector to the forward pass at one time since we can overlap a lot of computation. Finding second order derivatives one at a time, like `df/dxdy` for an entire Hessian tends to be slow. It looks like most of the action is in var.cpp, but I can't see how this would run fast. Do you have any idea how this scales up for derivative calculations (gradient and Hess-vec) as we get at least into the thousands of variables in terms of derivative time vs evaluation time with no AD abstractions? Certainly, I may be misunderstanding something. That said, if the efficiency doesn't scale, it seems like the practical significance will be limited.
cs702 10y ago
The idea of composing complicated differentiable programs (that have control structures, recursion, etc.) from simpler differentiable programs by means of an abstract algebra of differentiable programs is truly mind-bending. It upends the conventional concept I have of "programming" for day-to-day purposes. It also upends the conventional concept I have of "designing" (i.e., handcrafting) machine learning models, like deep neural nets, for different problems. Like you, I don't yet grok all the nitty-gritty details of the paper (it will take a me a long time to grok them), but it's clear to me that if the paper survives peer review (which I would expect, given that the authors have published working code), you're right: its formalization has a lot of potential for the fields of machine learning, AI, and computer science. Holy cow. EDIT: Removed the "could revolutionize" bit, which was over-enthusiastic.
- m_hack 10y ago
  Agreed. The paper seems to be about a lot more than AD, as AD isn't really the main subject. This approach to programming really does strike me as new and important. I too havent yet grasped all the details, having spent a few hours on it today. I commented a short synopsis bellow. I will try to get a better grasp of it tomorrow.

kxyvr 10y ago

I skimmed their paper and don't claim to understand everything, but I am curious about some of your comments. As far as higher-order derivatives, there's not really been an issue with obtaining these derivatives with traditional automatic differentiation techniques. The hard part is how to compute them efficiently. For example, Hessian-vector products can be obtained via forward-over-reverse or reverse-or-forward methods, but one runs significantly faster than the other. What's not clear to me in this paper is the practical efficiency of their technique especially for high-order derivatives. Second, as far as neural networks, it's also not clear to me what's currently missing from using existing AD tools and what this new paper provides. Right now, there exist good AD tools that work just fine with control structures, recursion, and composition. In my opinion, a much better way to implement the training algorithms for machine learning is to just run an AD package on a particular model and then feed the resulting derivatives into an appropriate optimization algorithm. It's accurate, clean, and save time and effort. As such, what do we really gain from using this new methodology? That said, I appreciate that the authors put together some interesting abstractions that I'd not seen before in this context. I think it's worth a read even if just for that.

hcarvalhoalves 10y ago
> What's not clear to me in this paper is the practical efficiency of their technique especially for high-order derivatives. On section "5.3.1 Order reduction for nested applications": > We gained the ability of writing a differentiable program acting on derivatives of another program, stressed as crucial (but lacking in most models) by other authors [18]. See http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1370&context=ecetr http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1370&... for [18]. --- > Right now, there exist good AD tools that work just fine with control structures, recursion, and composition. See their example implementation (https://github.com/ZigaSajovic/dCpp https://github.com/ZigaSajovic/dCpp) to understand what "control structures, recursion and composition" mean in this context.
- kxyvr 10y ago
  Thanks for the reply. Perlmutter and Siskind's paper doesn't really talk about the efficiency of higher-order derivatives either and only has a very simple run time for a gradient calculation. I had a look at the code and I can't figure out how their abstractions would allow for efficient higher-order derivatives. Even on the front page, they list the examples // df/dxdx std::cout<<"df/dxdx = "<<f.d(&x).d(&x).id<<std::endl; // df/dxdy std::cout<<"df/dxdy = "<<f.d(&x).d(&y).id<<std::endl; Generally, I think those abstractions make it hard to compute things like Hessian-vector products because we really need a reverse pass to generate either a program or computational tree that we can fly through with a forward pass. That involves giving an explicit instruction to run a reverse pass since we don't do it automatically since it's expensive. Also, we generally give an entire vector to the forward pass at one time since we can overlap a lot of computation. Finding second order derivatives one at a time, like `df/dxdy` for an entire Hessian tends to be slow. It looks like most of the action is in var.cpp, but I can't see how this would run fast. Do you have any idea how this scales up for derivative calculations (gradient and Hess-vec) as we get at least into the thousands of variables in terms of derivative time vs evaluation time with no AD abstractions? Certainly, I may be misunderstanding something. That said, if the efficiency doesn't scale, it seems like the practical significance will be limited.

cs702 10y ago

The idea of composing complicated differentiable programs (that have control structures, recursion, etc.) from simpler differentiable programs by means of an abstract algebra of differentiable programs is truly mind-bending. It upends the conventional concept I have of "programming" for day-to-day purposes. It also upends the conventional concept I have of "designing" (i.e., handcrafting) machine learning models, like deep neural nets, for different problems. Like you, I don't yet grok all the nitty-gritty details of the paper (it will take a me a long time to grok them), but it's clear to me that if the paper survives peer review (which I would expect, given that the authors have published working code), you're right: its formalization has a lot of potential for the fields of machine learning, AI, and computer science. Holy cow. EDIT: Removed the "could revolutionize" bit, which was over-enthusiastic.

m_hack 10y ago
Agreed. The paper seems to be about a lot more than AD, as AD isn't really the main subject. This approach to programming really does strike me as new and important. I too havent yet grasped all the details, having spent a few hours on it today. I commented a short synopsis bellow. I will try to get a better grasp of it tomorrow.