6 ms·

Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

83 points by lambdamore 8y ago

adamnemecek 8y ago
The idea of duality is insane. Its present in linear logic, automatic diff, constructive mathematics, probability, quantum theory, game design, discrete optimization, etc. I wonder if it's related to chirality.
- ssivark 8y ago
  For those of us who are not aware of duality in auto differentiation (and haven't had a chance to read the above review), could you introduce the idea? Are you talking about forward mode vs reverse mode -- since I haven't pondered, what's interesting/deep about that?
  - adamnemecek 8y ago
    AD relies on dual numbers. Dual numbers are more suited for doing calculus. Structurally, dual numbers are numbers of the form a + b * e (where e is epsilon s.t. e^2 = 0 but e != 0. Think of it as the imaginary constant but instead of i^2 = -1, you have e^2=0). For example, multiplication of two dual numbers (a + b * e)(c + d * e) = (ac + ad * e + bc * e +bd * e^2). Since e^2 = 0, you end up with (ac + (ad + bc) * e). Here comes the magic. Dual numbers let you evaluate a function and get the derivative at that point by just evaluating the function. In the above, example, if this was the result of a function, ac is the value of the function and ad + bc is the derivative of that function at that value. https://blog.demofox.org/2014/12/30/dual-numbers-automatic-differentiation/ https://blog.demofox.org/2014/12/30/dual-numbers-automatic-d...
    - selimthegrim 8y ago
      Before looking at the wiki I thought, huh, Grassmann numbers on HN?
      - adamnemecek 8y ago
        You are not wrong.
  - b_tterc_p 8y ago
    Edit: I think I answered a different question than I believed. Been a while but my best crack at it: If you’re trying to minimize a function, you can call it the primal function. It will have n inputs and m constraints (like how many of each product should I buy constrained by budget and carrying capacity). You can flip the problem around into its dual formulation. This will be a function with m inputs and n constraints, and it will be a maximization problem. If you can solve the dual formulation (global max), you know that the primal cannot possibly be lower than the dual. For some types of problems (convex), you can even guarantee that the global max of the dual is the global min of the primal. The transformation between primal and dual formulations goes both ways, so the primal is the dual of the dual.
    - bitL 8y ago
      I'd add a very important thing - with your primal problem you are trying to e.g. minimize a function and you proceed the way that all your intermediate solutions are feasible. With dual approach you flip the direction, i.e. maximization in this case, but you start in completely infeasible solutions and hope to end up in the very first feasible solution that should be your optimum. Now how does that relate to automatic differentiation I am not sure either.
- selimthegrim 8y ago
  I think the dualities in quantum field theory are different from the dualities in optimization but maybe some category theorist can correct me if I’m wrong
  - adamnemecek 8y ago
    Category theory isn't quite the correct formalism.
    - selimthegrim 8y ago
      What would be then?
      - adamnemecek 8y ago
        I like linear logic a lot. Not saying it solves everything but it's easier to understand and you don't really give up much of what category theory has. Also alternating graphs or game semantics. These are all related.
- WallWextra 8y ago
  Those are a bunch of different ideas. It's the word "duality" that is insane(ly overloaded).
  - adamnemecek 8y ago
    They aren't, the underlying idea is the same, or very similar. Pick two of them and I'll provide reference on the connection.
    - twtw 8y ago
      Discrete optimization and automatic differentiation.
      - adamnemecek 8y ago
        Gimme five and I'll answer two. There's quite a few pairwise permutations and some are easier to understand and more instructive than others. Fundamentally, they are both connected via the idea of convex optimization. Automatic differentiation is a computational technique to solve optimization problems. Yes optimization problems is very general however calculus is a fundamental tool. Dual numbers are somewhat like lie groups, very smooth and conducive to optimization.
        wenc 8y ago
        Curious, can you expand on the connection to convex optimization? To my understanding, discrete optimization is nonconvex by nature due to discontinuities in the feasible space.
        adamnemecek 8y ago
        There are two types of spaces, discrete and continuous. These are in a dual relationship. Duality is the isomorphism between these two. For example, for humans, it's easier to reason about discrete spaces. However a lot of things simply cannot be done that way. Think of anything that is tangential (pun intended) to Lie theory. In the context of Lie theory, you have the discrete group and the continuous algebra (the group's tangent space). You go between these two using the exponent (group -> algebra) and logarithm to go back (algebra -> group). It's the difference between an integral and a Rieman sum. It's the fundamental idea that underlies sampling (say audio sampling or even statistical sampling). You capture some invariants and then you interpolate between these invariants to recreate some smooth curve (or distribution). The nice thing about the smooth space is that optimization is easy. In the exponential space, addition is multiplication and some expensive things are cheap (computationally speaking).
- throwawaymath 8y ago
  I think characterizing duality in this way is kind of superfluous, because the only way all those meanings of duality are the same is in the most abstract sense of the word. In other words, lots of things have duals. But the duality between any given pair of things doesn't necessarily expose any deep, fundamental connection to another pair of things which have duality. So it's not that duality features so heavily throughout mathematics as its own concept; rather, we frequently build new theories to tie these things together. It's helpful to be able to translate things from one context to another context. We could just as easily say that isomorphisms are insane because they feature heavily throughout mathematics. But I don't think that provides a deep insight, because it's not like an isomorphism is a special property that ties a bunch of mathematics together in a grand way. Specific pairs of things can be isomorphic. Likewise specific pairs of things can be duals. Any given pair of dual things is its own duality. It doesn't necessarily have anything to do with the way another pair of objects is in duality. The terminology here is semantically convenient for intuition, but it's definitely overloaded. I think the commonalities you're seeing here are simply due to the vast utility of linearity in all of those disciplines.
  - adamnemecek 8y ago
    > I think characterizing duality in this way is kind of superfluous, It's an analysis done out of necessity. These dualities might not be a 100% in every case, but maybe I care about the ways in which they are similar. > because the only way all those meanings of duality are the same is in the most abstract sense of the word. So is a monad. Do you think that in the future, the level of abstraction in mathematics is going to increase or decrease?
    - throwawaymath 8y ago
      It will increase, which I guess is sort of my point. We already know there's a lot of abstraction. If these things are only alike semantically (two pairs of dual things can be completely unrelated), what does it gain you to point out they've everywhere? I don't mean to be obtuse, but it strikes me as saying that a city is full of concrete.
deleted 8y ago
[deleted]
cs702 8y ago
I'm trembling with excitement at the prospect that easy-to-use high-performance automatic differentiation looks likely to become a "must have" capability for more and more computer languages. It's going to become easier and easier to specify objective functions and have the computer optimize programs for a wider range of application.
- thearn4 8y ago
  I work on non-linear optimization problems for most of my work projects, and I know exactly what you mean. One of these years we'll be freed from remembering calculus I :)
  - killjoywashere 8y ago
    right after the year of the Linux desktop, eh?

83 points by lambdamore 8y ago

The idea of duality is insane. Its present in linear logic, automatic diff, constructive mathematics, probability, quantum theory, game design, discrete optimization, etc. I wonder if it's related to chirality.

ssivark 8y ago
For those of us who are not aware of duality in auto differentiation (and haven't had a chance to read the above review), could you introduce the idea? Are you talking about forward mode vs reverse mode -- since I haven't pondered, what's interesting/deep about that?
- adamnemecek 8y ago
  AD relies on dual numbers. Dual numbers are more suited for doing calculus. Structurally, dual numbers are numbers of the form a + b * e (where e is epsilon s.t. e^2 = 0 but e != 0. Think of it as the imaginary constant but instead of i^2 = -1, you have e^2=0). For example, multiplication of two dual numbers (a + b * e)(c + d * e) = (ac + ad * e + bc * e +bd * e^2). Since e^2 = 0, you end up with (ac + (ad + bc) * e). Here comes the magic. Dual numbers let you evaluate a function and get the derivative at that point by just evaluating the function. In the above, example, if this was the result of a function, ac is the value of the function and ad + bc is the derivative of that function at that value. https://blog.demofox.org/2014/12/30/dual-numbers-automatic-differentiation/ https://blog.demofox.org/2014/12/30/dual-numbers-automatic-d...
  - selimthegrim 8y ago
    Before looking at the wiki I thought, huh, Grassmann numbers on HN?
    - adamnemecek 8y ago
      You are not wrong.
- b_tterc_p 8y ago
  Edit: I think I answered a different question than I believed. Been a while but my best crack at it: If you’re trying to minimize a function, you can call it the primal function. It will have n inputs and m constraints (like how many of each product should I buy constrained by budget and carrying capacity). You can flip the problem around into its dual formulation. This will be a function with m inputs and n constraints, and it will be a maximization problem. If you can solve the dual formulation (global max), you know that the primal cannot possibly be lower than the dual. For some types of problems (convex), you can even guarantee that the global max of the dual is the global min of the primal. The transformation between primal and dual formulations goes both ways, so the primal is the dual of the dual.
  - bitL 8y ago
    I'd add a very important thing - with your primal problem you are trying to e.g. minimize a function and you proceed the way that all your intermediate solutions are feasible. With dual approach you flip the direction, i.e. maximization in this case, but you start in completely infeasible solutions and hope to end up in the very first feasible solution that should be your optimum. Now how does that relate to automatic differentiation I am not sure either.
selimthegrim 8y ago
I think the dualities in quantum field theory are different from the dualities in optimization but maybe some category theorist can correct me if I’m wrong
- adamnemecek 8y ago
  Category theory isn't quite the correct formalism.
  - selimthegrim 8y ago
    What would be then?
    - adamnemecek 8y ago
      I like linear logic a lot. Not saying it solves everything but it's easier to understand and you don't really give up much of what category theory has. Also alternating graphs or game semantics. These are all related.
WallWextra 8y ago
Those are a bunch of different ideas. It's the word "duality" that is insane(ly overloaded).
- adamnemecek 8y ago
  They aren't, the underlying idea is the same, or very similar. Pick two of them and I'll provide reference on the connection.
  - twtw 8y ago
    Discrete optimization and automatic differentiation.
    - adamnemecek 8y ago
      Gimme five and I'll answer two. There's quite a few pairwise permutations and some are easier to understand and more instructive than others. Fundamentally, they are both connected via the idea of convex optimization. Automatic differentiation is a computational technique to solve optimization problems. Yes optimization problems is very general however calculus is a fundamental tool. Dual numbers are somewhat like lie groups, very smooth and conducive to optimization.
      - wenc 8y ago
        Curious, can you expand on the connection to convex optimization? To my understanding, discrete optimization is nonconvex by nature due to discontinuities in the feasible space.
        adamnemecek 8y ago
        There are two types of spaces, discrete and continuous. These are in a dual relationship. Duality is the isomorphism between these two. For example, for humans, it's easier to reason about discrete spaces. However a lot of things simply cannot be done that way. Think of anything that is tangential (pun intended) to Lie theory. In the context of Lie theory, you have the discrete group and the continuous algebra (the group's tangent space). You go between these two using the exponent (group -> algebra) and logarithm to go back (algebra -> group). It's the difference between an integral and a Rieman sum. It's the fundamental idea that underlies sampling (say audio sampling or even statistical sampling). You capture some invariants and then you interpolate between these invariants to recreate some smooth curve (or distribution). The nice thing about the smooth space is that optimization is easy. In the exponential space, addition is multiplication and some expensive things are cheap (computationally speaking).
throwawaymath 8y ago
I think characterizing duality in this way is kind of superfluous, because the only way all those meanings of duality are the same is in the most abstract sense of the word. In other words, lots of things have duals. But the duality between any given pair of things doesn't necessarily expose any deep, fundamental connection to another pair of things which have duality. So it's not that duality features so heavily throughout mathematics as its own concept; rather, we frequently build new theories to tie these things together. It's helpful to be able to translate things from one context to another context. We could just as easily say that isomorphisms are insane because they feature heavily throughout mathematics. But I don't think that provides a deep insight, because it's not like an isomorphism is a special property that ties a bunch of mathematics together in a grand way. Specific pairs of things can be isomorphic. Likewise specific pairs of things can be duals. Any given pair of dual things is its own duality. It doesn't necessarily have anything to do with the way another pair of objects is in duality. The terminology here is semantically convenient for intuition, but it's definitely overloaded. I think the commonalities you're seeing here are simply due to the vast utility of linearity in all of those disciplines.
- adamnemecek 8y ago
  > I think characterizing duality in this way is kind of superfluous, It's an analysis done out of necessity. These dualities might not be a 100% in every case, but maybe I care about the ways in which they are similar. > because the only way all those meanings of duality are the same is in the most abstract sense of the word. So is a monad. Do you think that in the future, the level of abstraction in mathematics is going to increase or decrease?
  - throwawaymath 8y ago
    It will increase, which I guess is sort of my point. We already know there's a lot of abstraction. If these things are only alike semantically (two pairs of dual things can be completely unrelated), what does it gain you to point out they've everywhere? I don't mean to be obtuse, but it strikes me as saying that a city is full of concrete.

deleted 8y ago

[deleted]

cs702 8y ago

I'm trembling with excitement at the prospect that easy-to-use high-performance automatic differentiation looks likely to become a "must have" capability for more and more computer languages. It's going to become easier and easier to specify objective functions and have the computer optimize programs for a wider range of application.

thearn4 8y ago
I work on non-linear optimization problems for most of my work projects, and I know exactly what you mean. One of these years we'll be freed from remembering calculus I :)
- killjoywashere 8y ago
  right after the year of the Linux desktop, eh?