3 ms·

There's more information here: https://github.com/conal/talk-2018-essence-of-ad https://github.com/conal/talk-2018-essence-of-ad That said, has anyone had a l

by kxyvr 8y ago

There's more information here: https://github.com/conal/talk-2018-essence-of-ad https://github.com/conal/talk-2018-essence-of-ad That said, has anyone had a look at the paper? What I can't figure out is the assertion that, "In contrast to commonly used RAD implementations, the algorithms defined here involve no graphs, tapes, variables, partial derivatives, or mutation. They are inherently parallel-friendly, correct by construction, and usable directly from an existing programming language with no need for new data types or programming style, thanks to use of an AD-agnostic compiler plugin." That would be fantastic, but that's not immediately obvious to me. Generally, reverse mode is extremely non-parallel friendly because we're essentially traversing a computation graph. That traversal can be done in parallel, but figuring out how to partition that graph is probably more expensive that traversing it in serial. Now, the paper makes a big deal about not building that graph and passing along the derivative at the same time as the function. Fine. But does that method really produce a more parallel friendly code and is that as efficient as a more traditional graph or tape based method? Unless I'm missing something, I don't see any benchmarks of the method and what would be really helpful would be a ratio of the run time of a routine versus the run time of the routine with the AD method instrumented and the gradient calculated. The big question is how does this ratio hold as the method is scaled up in terms of variables. If the parallel claim holds true, then we should be able to also calculate the resulting parallel efficiencies. Anyway, I'm genuinely curious if someone has additional information about the computational viability.

fmap 8y ago
I don't think Conal makes any performance claims. The code is more parallel friendly because it doesn't involve global state, but for reverse mode AD you are not calculating derivatives as you go, but instead building up a function that will calculate the derivatives at the end. That's the effectively the same operation as normal reverse mode AD. Anyway, this discussion still misses the point. The actual program transformation that powers this paper is "compiling to categories", which is essentially making the computation graph explicit in a modular way. This is why you can go through the program in parallel afterwards - sharing and dependencies are already made explicit and there is no need to discover them as you go. The main innovation of the paper is the factorization of different AD modes in terms of simple transformations on categories (e.g. the Yoneda embedding applied to forward AD gives you reverse AD). In this format it is easy to see that the methods are correct and easy to extend the code since there just isn't very much of it. This is a great paper (and talks!). It's taking a messy algorithm and factorizing it into simple and reusable components.
syllogism 8y ago
I can't tell because I don't speak category theory, but I've been told the essence is similar to how I've implemented the neural networks for spaCy: https://github.com/explosion/thinc https://github.com/explosion/thinc If so, then it definitely works fine. On the other hand I don't think parallelism is so easy to achieve, so maybe it's not the same thing after all.
- orbifold 8y ago
  My understanding is also that it is. Your implementation drove the point home for me that it can be practical. The dictionary is rather simple - a lambda \x . f(x) is known as an "internal hom object" - you get a closure by using the partial application morphism (see https://en.wikipedia.org/wiki/Cartesian_closed_category https://en.wikipedia.org/wiki/Cartesian_closed_category) - copying a variable is known as Δ : x ↦ (x,x) - there is a contravariant functor T^\star: X → T^\star X between a manifold X and its cotangent space, which maps f: X → Y to its adjoint f^\star: T^\star Y → T^\star X - you can then consider the product of the category of smooth manifolds Man × Man^{op} and define a functor Man → Man × Man^{op}, which maps a manifold X to the product of manifolds (X,T^\star X) and a morphism f : X → Y to the morphism (f,f^\star). - All you have to do to get from your implementation to the notions in the paper is to convert the prescription you give into a point free style and apply some jargon (You need things like the partial application map and evaluation map, which are defined in any closed cartesian category, but easily translate to programming languages as well)
dzdt 8y ago
I don't think there are any great advantages for computational viability. He is introducing a new category-theoretic language, but in the end the same computations have to be done. In his language, there is no "tape" because instead there is "continuation passing" which plays exactly the same role. I guess he hopes to construct the continuation-passing form at compile time, which limits the application to cases where the tape would be small anyway. He hints that his approach should allow more parallelization but I don't see it. In practice the people trying to build AD engines are paying attention to the actual computation being done, and understand what can be parallelized. A more abstract understanding of the problem is little help there I think.

by kxyvr 8y ago

fmap 8y ago

I don't think Conal makes any performance claims. The code is more parallel friendly because it doesn't involve global state, but for reverse mode AD you are not calculating derivatives as you go, but instead building up a function that will calculate the derivatives at the end. That's the effectively the same operation as normal reverse mode AD. Anyway, this discussion still misses the point. The actual program transformation that powers this paper is "compiling to categories", which is essentially making the computation graph explicit in a modular way. This is why you can go through the program in parallel afterwards - sharing and dependencies are already made explicit and there is no need to discover them as you go. The main innovation of the paper is the factorization of different AD modes in terms of simple transformations on categories (e.g. the Yoneda embedding applied to forward AD gives you reverse AD). In this format it is easy to see that the methods are correct and easy to extend the code since there just isn't very much of it. This is a great paper (and talks!). It's taking a messy algorithm and factorizing it into simple and reusable components.

syllogism 8y ago

I can't tell because I don't speak category theory, but I've been told the essence is similar to how I've implemented the neural networks for spaCy: https://github.com/explosion/thinc https://github.com/explosion/thinc If so, then it definitely works fine. On the other hand I don't think parallelism is so easy to achieve, so maybe it's not the same thing after all.

orbifold 8y ago
My understanding is also that it is. Your implementation drove the point home for me that it can be practical. The dictionary is rather simple - a lambda \x . f(x) is known as an "internal hom object" - you get a closure by using the partial application morphism (see https://en.wikipedia.org/wiki/Cartesian_closed_category https://en.wikipedia.org/wiki/Cartesian_closed_category) - copying a variable is known as Δ : x ↦ (x,x) - there is a contravariant functor T^\star: X → T^\star X between a manifold X and its cotangent space, which maps f: X → Y to its adjoint f^\star: T^\star Y → T^\star X - you can then consider the product of the category of smooth manifolds Man × Man^{op} and define a functor Man → Man × Man^{op}, which maps a manifold X to the product of manifolds (X,T^\star X) and a morphism f : X → Y to the morphism (f,f^\star). - All you have to do to get from your implementation to the notions in the paper is to convert the prescription you give into a point free style and apply some jargon (You need things like the partial application map and evaluation map, which are defined in any closed cartesian category, but easily translate to programming languages as well)

dzdt 8y ago

I don't think there are any great advantages for computational viability. He is introducing a new category-theoretic language, but in the end the same computations have to be done. In his language, there is no "tape" because instead there is "continuation passing" which plays exactly the same role. I guess he hopes to construct the continuation-passing form at compile time, which limits the application to cases where the tape would be small anyway. He hints that his approach should allow more parallelization but I don't see it. In practice the people trying to build AD engines are paying attention to the actual computation being done, and understand what can be parallelized. A more abstract understanding of the problem is little help there I think.