4 ms·

I cannot stress enough how foundational of an idea it is to store mathematical expressions as graphs! Analyzing and manipulating such graphs enables, among othe

I cannot stress enough how foundational of an idea it is to store mathematical expressions as graphs! Analyzing and manipulating such graphs enables, among other things, to automatically obtain derivatives of a function with respect to its parameters, which is one of the cornerstones of most AI methods. Before this was invented, people had to manually find expressions for these derivatives, and implement the code to compute them. Needless to say, this took way too much time and was likely to result in sub-optimal and unoptimized code, while nowadays nobody has to deal with this anymore (except on their homeworks)! For the curious of how this works, I present a simple implementation on my blog [1]. [1] https://e-dorigatti.github.io/math/deep%20learning/2020/04/07/autodiff.html https://e-dorigatti.github.io/math/deep%20learning/2020/04/0...

mathisfun123 3y ago
There's always a particular brand of woo on display in threads like this that irks me to my core - like someone arriving at show and tell but really they don't know enough to tell. >I cannot stress enough how foundational of an idea it is to store mathematical expressions as graphs... one of the cornerstones of most AI methods. Firstly what are AI methods? That's pretty vague huh? Secondly you're just saying that expression trees are useful. Ok? I mean this was known since like the days of... Church? > Before this was invented, people had to manually find expressions for these derivatives, and implement the code to compute them. There were (and still are) lots of AD systems and not all of them use a wengert tape. https://www.autodiff.org/?module=Tools&language=ALL https://www.autodiff.org/?module=Tools&language=ALL Anyway it's just software (and not even particularly clever software), not the second coming lol.
curiousgal 3y ago
Another major application is in finance! Computing risk metrics for hedging purposes used to to be based on a "bump and reprice" method, i.e. you bump the input by a small amount and see how that affects the price (the definition of a derivative). But now in modern quant libraries, implementing the pricing as a graph allows you to get all of the sensitivities (derivatives) for free!
- blackbear_ 3y ago
  That's cool! But it relies on the model being an accurate representation of reality, right? What kind of models are we talking about anyways, and what inputs do they use? (Asking out of curiosity, not skepticism)
  - mhh__ 3y ago
    A model is a computation based on its initial assumptions. Sometimes that's fine. The key thing is that the (good) practitioners know the finance and know the models. If it's obviously wrong that's a sign in itself - a simple model doesn't fit the market: You might be about to lose some money, or you could take on some risk from other people and get rewarded for it (people are panicking). Weirder derivatives and so on can get more dangerous, of course. However even the really famous example from the 07 crash (pricing CDOs and CDS against them) was arguably due to a deliberate ignorance of widespread fraud and fictitious numbers than the models as per se. Garbage in garbage out (the model was also not great but still)
- mhh__ 3y ago
  Not quite. Some people want bump Greeks. For example a company may have a standard bump. Make of that what you will.
- KMag 3y ago
  Not quite free. Last I checked, adding automatic differentiation to GPU computation for pricing exotic derivatives roughly doubled the computation cost. (Though, traditional bump-and-reprice has exponential cost in the number of dimensions.)
joe_the_user 3y ago
I cannot stress enough how foundational of an idea it is to store mathematical expressions as graphs!.. Understanding a function's computational graph is certainly useful but storing a function as a computation graph is, in fact, quite expensive. Deep learning systems don't store their computational graphs, the graphs are implicit in their computation process. Deep learning systems instead store their functions as tensors; generalized arrays/matrices. This allows both efficient storage and efficient computation. It's quite possible do automatic differentiation on these structures as well - that is the basis of "backpropagation". It's important to distinguish useful conceptual structures like computation graphs (or symbolic representations) and the structures that are necessary for efficient computation. Automatic differentiation itself is important because the traditional symbolic differentiation one learns in calculus "blows up", can have O(m^expression-length) cost, when attempted on a large expression where automatic differentiation has a cost that is not that much higher than the base cost of computing a given function (but if that base cost is high, you lose your advantage also). Just sayin'
- deleted 3y ago
  [deleted]
- necroforest 3y ago
  you can't store a function as a tensor. the tensors are the inputs/outputs that flow along the edges of the graph. TF stores things directly as a graph: https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/framework/node_def.proto https://github.com/tensorflow/tensorflow/blob/master/tensorf... while Jax represents computations in an intermediate representation: https://jax.readthedocs.io/en/latest/jaxpr.html https://jax.readthedocs.io/en/latest/jaxpr.html
- lgessler 3y ago
  > Deep learning systems don't store their computational graphs, the graphs are implicit in their computation process I'm not sure about other frameworks, but in PyTorch, I think it's fair to say that while graphs are implicit in the sense that they are dynamically constructed at runtime (as opposed to statically defined at compilation time as with TF), they are not implicit in the sense that they are not directly represented by PyTorch's data structures: PyTorch does store the computational graph. After a backward pass, you can ask each Tensor in the graph, for example, for its associated Node: https://pytorch.org/docs/stable/autograd.html#autograd-graph https://pytorch.org/docs/stable/autograd.html#autograd-graph
BaculumMeumEst 3y ago
Excellent post, thank you for writing it.

mathisfun123 3y ago

There's always a particular brand of woo on display in threads like this that irks me to my core - like someone arriving at show and tell but really they don't know enough to tell. >I cannot stress enough how foundational of an idea it is to store mathematical expressions as graphs... one of the cornerstones of most AI methods. Firstly what are AI methods? That's pretty vague huh? Secondly you're just saying that expression trees are useful. Ok? I mean this was known since like the days of... Church? > Before this was invented, people had to manually find expressions for these derivatives, and implement the code to compute them. There were (and still are) lots of AD systems and not all of them use a wengert tape. https://www.autodiff.org/?module=Tools&language=ALL https://www.autodiff.org/?module=Tools&language=ALL Anyway it's just software (and not even particularly clever software), not the second coming lol.

curiousgal 3y ago

Another major application is in finance! Computing risk metrics for hedging purposes used to to be based on a "bump and reprice" method, i.e. you bump the input by a small amount and see how that affects the price (the definition of a derivative). But now in modern quant libraries, implementing the pricing as a graph allows you to get all of the sensitivities (derivatives) for free!

blackbear_ 3y ago
That's cool! But it relies on the model being an accurate representation of reality, right? What kind of models are we talking about anyways, and what inputs do they use? (Asking out of curiosity, not skepticism)
- mhh__ 3y ago
  A model is a computation based on its initial assumptions. Sometimes that's fine. The key thing is that the (good) practitioners know the finance and know the models. If it's obviously wrong that's a sign in itself - a simple model doesn't fit the market: You might be about to lose some money, or you could take on some risk from other people and get rewarded for it (people are panicking). Weirder derivatives and so on can get more dangerous, of course. However even the really famous example from the 07 crash (pricing CDOs and CDS against them) was arguably due to a deliberate ignorance of widespread fraud and fictitious numbers than the models as per se. Garbage in garbage out (the model was also not great but still)
mhh__ 3y ago
Not quite. Some people want bump Greeks. For example a company may have a standard bump. Make of that what you will.
KMag 3y ago
Not quite free. Last I checked, adding automatic differentiation to GPU computation for pricing exotic derivatives roughly doubled the computation cost. (Though, traditional bump-and-reprice has exponential cost in the number of dimensions.)

joe_the_user 3y ago

I cannot stress enough how foundational of an idea it is to store mathematical expressions as graphs!.. Understanding a function's computational graph is certainly useful but storing a function as a computation graph is, in fact, quite expensive. Deep learning systems don't store their computational graphs, the graphs are implicit in their computation process. Deep learning systems instead store their functions as tensors; generalized arrays/matrices. This allows both efficient storage and efficient computation. It's quite possible do automatic differentiation on these structures as well - that is the basis of "backpropagation". It's important to distinguish useful conceptual structures like computation graphs (or symbolic representations) and the structures that are necessary for efficient computation. Automatic differentiation itself is important because the traditional symbolic differentiation one learns in calculus "blows up", can have O(m^expression-length) cost, when attempted on a large expression where automatic differentiation has a cost that is not that much higher than the base cost of computing a given function (but if that base cost is high, you lose your advantage also). Just sayin'

deleted 3y ago
[deleted]
necroforest 3y ago
you can't store a function as a tensor. the tensors are the inputs/outputs that flow along the edges of the graph. TF stores things directly as a graph: https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/framework/node_def.proto https://github.com/tensorflow/tensorflow/blob/master/tensorf... while Jax represents computations in an intermediate representation: https://jax.readthedocs.io/en/latest/jaxpr.html https://jax.readthedocs.io/en/latest/jaxpr.html
lgessler 3y ago
> Deep learning systems don't store their computational graphs, the graphs are implicit in their computation process I'm not sure about other frameworks, but in PyTorch, I think it's fair to say that while graphs are implicit in the sense that they are dynamically constructed at runtime (as opposed to statically defined at compilation time as with TF), they are not implicit in the sense that they are not directly represented by PyTorch's data structures: PyTorch does store the computational graph. After a backward pass, you can ask each Tensor in the graph, for example, for its associated Node: https://pytorch.org/docs/stable/autograd.html#autograd-graph https://pytorch.org/docs/stable/autograd.html#autograd-graph

BaculumMeumEst 3y ago

Excellent post, thank you for writing it.