5 ms·

I can't wait for someone to figure out automatic integration (similar to automatic differentiation). Current ways of integrating are such clusterfuck.

hervature 6y ago
I think you will be waiting a long time. I hope this helps elucidate why: https://math.stackexchange.com/questions/1635949/is-there-a-chain-rule-for-integration https://math.stackexchange.com/questions/1635949/is-there-a-...
- adamnemecek 6y ago
  This assumes a little too much about how automatic differentiation would work.
  - hervature 6y ago
    Based on the rest of your comments, I'm not sure you know that automatic differentiation is a well established technique that is 40+ years old.
    - adamnemecek 6y ago
      Based on your comment, I'm not sure you know that dual numbers, the foundation of autodiff, is 150+ years old.
      - hervature 6y ago
        > This assumes a little too much about how automatic differentiation would work. The use of 'would' implies that automatic differentiation has not been established. Also, if something is 40+ years old, then it follows that its foundation is even older.
        adamnemecek 6y ago
        I meant automatic integration.
- ogogmad 6y ago
  Integration and differentiation are opposites: Integration is well behaved numerically, but poorly behaved algebraically. Differentiation is poorly behaved numerically, but well behaved algebraically. Therefore if one wants to do "automatic integration", one has to approach it in a radically different way to autodiff. And arguably, such a method does already exist; it's just very inefficient.
  - srean 6y ago
    > Integration is well behaved numerically, but poorly behaved algebraically. > Differentiation is poorly behaved numerically, but well behaved algebraically. This is so pithy and true, am stealing that.
eeegnu 6y ago
There's a nice discussion here: https://math.stackexchange.com/questions/20578/why-is-integration-so-much-harder-than-differentiation/20635 https://math.stackexchange.com/questions/20578/why-is-integr... on why integration is a fundamentally harder problem than differentiation. New techniques would be required to programatically analytically solve integrals as well as current differentiation programs, but it would be exciting to see.
- adamnemecek 6y ago
  I actually have an idea about how it would work that side steps all of this. I need more time to develop it but watch this space. But I agree with the local vs global relationship, in fact the whole trick is about handling this.
laplacesdemon48 6y ago
Definitely not an expert but there's a fundamental hurdle to this. One way to think of this is to realize how easy it is to multiply numbers but how much more work it takes to divide numbers. For something like automatic differentiation, you're essentially applying the chain rule for partial derivatives repeatedly. This is analytically pretty straightforward to do for most applications. All you need is an analytical derivative for the simple functions your more-complex function is comprised of (e.g. a neural network). For integration, the analogue of the chain rule is integration by substitution [1]. The toolbox for solving integration problems is more limited than for differentiation. You run into issues where the answer cannot even be expressed using standard mathematical notation [2]. Sometimes you get lucky and the answer can be expressed via an alternating Taylor series so you can estimate the answer within some margin of error [3]. Stan is a piece of software that runs state-of-the-art MCMC methods to basically just compute fancy integrals. A Stan model will take an order of magnitude more time to run than a simple neural network via something like PyTorch on the same dataset. But they answer different questions. [1] https://math.stackexchange.com/questions/1635949/is-there-a-chain-rule-for-integration/ https://math.stackexchange.com/questions/1635949/is-there-a-... [2] https://math.stackexchange.com/questions/1397132/why-cant-some-integral-befound-though-they-are-anti-derivative-exist https://math.stackexchange.com/questions/1397132/why-cant-so... [3] https://math.stackexchange.com/questions/145087/how-to-calculate-the-integral-in-normal-distribution https://math.stackexchange.com/questions/145087/how-to-calcu...
- adamnemecek 6y ago
  You are right, however the same way with automatic differentiation, you never get the expression, with automatic integration it would be the same.
  - laplacesdemon48 6y ago
    Can you please elaborate on "you never get the expression"? When you input the variable values into a symbolic derivative you just get a value at the end. d/dx x^2 = 2x. If x = 0.5 then d/dx = 1. The same is true for symbolic integrals. For most practical applications, we don't really care about the full symbolic expression. We just want the answer, or at least a good approximation. This post uses a specific example of the difference between two Beta distributions. We want to get that 0.71. It is very hard to "automatically" make that happen.
konjin 6y ago
It has been figured out: https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm The problem is that it's unknown if a symbolic equality algorithm exists for elementary functions and what those functions should be. It is known that the general case is undecidable: https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem
- adamnemecek 6y ago
  Risch is not automatic.
  - konjin 6y ago
    Because there is no known algorithm for deciding equality. It becomes automatic if we assume an oracle. Since deciding equality is an open problem and the answer is probably 'no there isn't a decidable equality algorithm' it is as good an answer as we are going to get.
    - adamnemecek 6y ago
      You are assuming that we care about expressing the integral as a function. Given that with autodiff, we don't actually get the function expression, presumably with autodiff, we also wouldn't get it.
      - konjin 6y ago
        In automatic differentiation we depend on the fact that a closed form elementary solution exists even if we don't calculate it directly. For integration we need to prove that such a object exists for each expression we want to integrate before we try integrating. Which as far as I'm aware is a problem equivalent to that solved by the Risch algorithm.
        adamnemecek 6y ago
        OK but that's not how automatic differentiation would work?
kgwgk 6y ago
And how would the similarity work? The derivative is defined at a point, it makes sense to calculate f(x) and f’(x) together. What integral are you talking about precisely?
- adamnemecek 6y ago
  An integral between the two extrema.
  - kgwgk 6y ago
    The extrema of the function are the min/max values. If you think a bit about it, you’ll notice that what you write doesn’t make much sense.
ogogmad 6y ago
Integration is a computable operator ([1]), so arguably such a thing does already exist. The difficulty though is in computing it efficiently, especially in high dimensions. [1] - https://en.wikipedia.org/wiki/Computable_analysis#Basic_results https://en.wikipedia.org/wiki/Computable_analysis#Basic_resu...
mlthoughts2018 6y ago
The NUTS algorithm in hybrid monte carlo would be pretty close to this. The problem is that integration suffers from the curse of dimensionality much worse than differentiation. Differentiation is a local activity. You approximate a derivative near any point. Integration is non-local, you must aggregate a function over a span of points in the domain space. As the dimensions get higher, differentiation merely must apply local approximation to each successive dimension of a point in a grid. It only adds the computation cost. Integration requires exponentially more data (for a given level of accuracy) because adding a new dimension enlarges the entire integration domain space that must be ranged over, and worse you generally need all that new “volume” of the enlarged space to be covered evenly to avoid bias. So there are some fundamental asymmetries between differentiation and integration that play a role in why “automatic integration” isn’t as straightforwardly feasible as for differentiation.
- srean 6y ago
  The selling point of Monte Carlo is that regardless of dimension the estimation error is going to go down as 1/sqrt(n). That hides the dimension part in the 'constants' and the sampling routine. Usually one cannot afford to visit all of the space. One visits high density regions preferentially.
  - mlthoughts2018 6y ago
    Yes, agreed, I just meant why we won’t see “automatic quadrature” in the same sense as “automatic differentiation”. It’s always going to rely on adaptive sampling, for exactly this reason of dimensionality.
Hitton 6y ago
Differentiation is like squeezing toothpaste out of tube, integration is like pushing the paste back inside.
alew1 6y ago
In a sense, probabilistic programming languages are automatic (approximate) integrators. Programs can represent arbitrary measures, and the back-ends provide various methods of estimating integrals with respect to them.

hervature 6y ago

I think you will be waiting a long time. I hope this helps elucidate why: https://math.stackexchange.com/questions/1635949/is-there-a-chain-rule-for-integration https://math.stackexchange.com/questions/1635949/is-there-a-...

adamnemecek 6y ago
This assumes a little too much about how automatic differentiation would work.
- hervature 6y ago
  Based on the rest of your comments, I'm not sure you know that automatic differentiation is a well established technique that is 40+ years old.
  - adamnemecek 6y ago
    Based on your comment, I'm not sure you know that dual numbers, the foundation of autodiff, is 150+ years old.
    - hervature 6y ago
      > This assumes a little too much about how automatic differentiation would work. The use of 'would' implies that automatic differentiation has not been established. Also, if something is 40+ years old, then it follows that its foundation is even older.
      - adamnemecek 6y ago
        I meant automatic integration.
ogogmad 6y ago
Integration and differentiation are opposites: Integration is well behaved numerically, but poorly behaved algebraically. Differentiation is poorly behaved numerically, but well behaved algebraically. Therefore if one wants to do "automatic integration", one has to approach it in a radically different way to autodiff. And arguably, such a method does already exist; it's just very inefficient.
- srean 6y ago
  > Integration is well behaved numerically, but poorly behaved algebraically. > Differentiation is poorly behaved numerically, but well behaved algebraically. This is so pithy and true, am stealing that.

eeegnu 6y ago

There's a nice discussion here: https://math.stackexchange.com/questions/20578/why-is-integration-so-much-harder-than-differentiation/20635 https://math.stackexchange.com/questions/20578/why-is-integr... on why integration is a fundamentally harder problem than differentiation. New techniques would be required to programatically analytically solve integrals as well as current differentiation programs, but it would be exciting to see.

adamnemecek 6y ago
I actually have an idea about how it would work that side steps all of this. I need more time to develop it but watch this space. But I agree with the local vs global relationship, in fact the whole trick is about handling this.

laplacesdemon48 6y ago

Definitely not an expert but there's a fundamental hurdle to this. One way to think of this is to realize how easy it is to multiply numbers but how much more work it takes to divide numbers. For something like automatic differentiation, you're essentially applying the chain rule for partial derivatives repeatedly. This is analytically pretty straightforward to do for most applications. All you need is an analytical derivative for the simple functions your more-complex function is comprised of (e.g. a neural network). For integration, the analogue of the chain rule is integration by substitution [1]. The toolbox for solving integration problems is more limited than for differentiation. You run into issues where the answer cannot even be expressed using standard mathematical notation [2]. Sometimes you get lucky and the answer can be expressed via an alternating Taylor series so you can estimate the answer within some margin of error [3]. Stan is a piece of software that runs state-of-the-art MCMC methods to basically just compute fancy integrals. A Stan model will take an order of magnitude more time to run than a simple neural network via something like PyTorch on the same dataset. But they answer different questions. [1] https://math.stackexchange.com/questions/1635949/is-there-a-chain-rule-for-integration/ https://math.stackexchange.com/questions/1635949/is-there-a-... [2] https://math.stackexchange.com/questions/1397132/why-cant-some-integral-befound-though-they-are-anti-derivative-exist https://math.stackexchange.com/questions/1397132/why-cant-so... [3] https://math.stackexchange.com/questions/145087/how-to-calculate-the-integral-in-normal-distribution https://math.stackexchange.com/questions/145087/how-to-calcu...

adamnemecek 6y ago
You are right, however the same way with automatic differentiation, you never get the expression, with automatic integration it would be the same.
- laplacesdemon48 6y ago
  Can you please elaborate on "you never get the expression"? When you input the variable values into a symbolic derivative you just get a value at the end. d/dx x^2 = 2x. If x = 0.5 then d/dx = 1. The same is true for symbolic integrals. For most practical applications, we don't really care about the full symbolic expression. We just want the answer, or at least a good approximation. This post uses a specific example of the difference between two Beta distributions. We want to get that 0.71. It is very hard to "automatically" make that happen.

konjin 6y ago

It has been figured out: https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm The problem is that it's unknown if a symbolic equality algorithm exists for elementary functions and what those functions should be. It is known that the general case is undecidable: https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem

adamnemecek 6y ago
Risch is not automatic.
- konjin 6y ago
  Because there is no known algorithm for deciding equality. It becomes automatic if we assume an oracle. Since deciding equality is an open problem and the answer is probably 'no there isn't a decidable equality algorithm' it is as good an answer as we are going to get.
  - adamnemecek 6y ago
    You are assuming that we care about expressing the integral as a function. Given that with autodiff, we don't actually get the function expression, presumably with autodiff, we also wouldn't get it.
    - konjin 6y ago
      In automatic differentiation we depend on the fact that a closed form elementary solution exists even if we don't calculate it directly. For integration we need to prove that such a object exists for each expression we want to integrate before we try integrating. Which as far as I'm aware is a problem equivalent to that solved by the Risch algorithm.
      - adamnemecek 6y ago
        OK but that's not how automatic differentiation would work?

kgwgk 6y ago

And how would the similarity work? The derivative is defined at a point, it makes sense to calculate f(x) and f’(x) together. What integral are you talking about precisely?

adamnemecek 6y ago
An integral between the two extrema.
- kgwgk 6y ago
  The extrema of the function are the min/max values. If you think a bit about it, you’ll notice that what you write doesn’t make much sense.

ogogmad 6y ago

Integration is a computable operator ([1]), so arguably such a thing does already exist. The difficulty though is in computing it efficiently, especially in high dimensions. [1] - https://en.wikipedia.org/wiki/Computable_analysis#Basic_results https://en.wikipedia.org/wiki/Computable_analysis#Basic_resu...

mlthoughts2018 6y ago

The NUTS algorithm in hybrid monte carlo would be pretty close to this. The problem is that integration suffers from the curse of dimensionality much worse than differentiation. Differentiation is a local activity. You approximate a derivative near any point. Integration is non-local, you must aggregate a function over a span of points in the domain space. As the dimensions get higher, differentiation merely must apply local approximation to each successive dimension of a point in a grid. It only adds the computation cost. Integration requires exponentially more data (for a given level of accuracy) because adding a new dimension enlarges the entire integration domain space that must be ranged over, and worse you generally need all that new “volume” of the enlarged space to be covered evenly to avoid bias. So there are some fundamental asymmetries between differentiation and integration that play a role in why “automatic integration” isn’t as straightforwardly feasible as for differentiation.

srean 6y ago
The selling point of Monte Carlo is that regardless of dimension the estimation error is going to go down as 1/sqrt(n). That hides the dimension part in the 'constants' and the sampling routine. Usually one cannot afford to visit all of the space. One visits high density regions preferentially.
- mlthoughts2018 6y ago
  Yes, agreed, I just meant why we won’t see “automatic quadrature” in the same sense as “automatic differentiation”. It’s always going to rely on adaptive sampling, for exactly this reason of dimensionality.

Hitton 6y ago

Differentiation is like squeezing toothpaste out of tube, integration is like pushing the paste back inside.

alew1 6y ago

In a sense, probabilistic programming languages are automatic (approximate) integrators. Programs can represent arbitrary measures, and the back-ends provide various methods of estimating integrals with respect to them.