7 ms·

Deep neural networks as computational graphs (2018)

103 points by softwaredoug 3y ago

orbifold 3y ago
Ironically the very first publication on "Backpropagation" by a Finish master student (1972) already pointed out how to compute gradients in computational graphs. This if anything is the main thing which distinguishes Backpropagation as an algorithm from simply applying the chain rule.
dynamite-ready 3y ago
Wasn't that the paradigm behind Tensorflow?
- ggr2342 3y ago
  AFAIK it was first brought forward by PyTorch. I may be wrong though.
  - 6gvONxR4sf7o 3y ago
    It's been a core part of automatic differentiation for decades.
    - ggr2342 3y ago
      Oh! Can you give some pointers where to read about it more?
      - PartiallyTyped 3y ago
        The original 2017 PyTorch paper is probably a good one.
      - 6gvONxR4sf7o 3y ago
        The wikipedia page for automatic differentiation and its references would be a good start. https://en.wikipedia.org/wiki/Automatic_differentiation https://en.wikipedia.org/wiki/Automatic_differentiation In particular, the section "Beyond forward and reverse accumulation" tells you how hard it is to deal with the graph in optimal ways, hence the popularity of simpler forwards and backwards traversals of the graph.
  - cgearhart 3y ago
    It certainly pre-dates PyTorch. Applying computational graphs to neural networks was the central purpose of the Theano framework in the early 2010s. TensorFlow heavily followed those ideas, and Theano shut down a year or two later because they were so close conceptually and a grad research lab can’t compete with the resources of Google.
  - mhh__ 3y ago
    PyTorch's insight was to be very dynamic and simple. The underlying model is basically the same with the caveat that tensorflow uses/used something called a "tape".
  - HarHarVeryFunny 3y ago
    Before PyTorch there was Torch (which was Lua-based, hence the Py- prefix of the follow on PyTorch). With Torch, like the later TensorFlow 1.0, you first explicitly constructed the computational graph then executed it. PyTorch's later innovation was define-by-run where you just ran the code corresponding to your computational graph and the framework traced your code and built the graph behind the scenes... this was so much more convenient that PyTorch quickly became more popular than TensorFlow, and by the time TF 2.0 "eager mode" copied this approach it was too late (although TF shot itself in the foot in many ways, which also accelerated it's demise).
- dkislyuk 3y ago
  As another commenter said, viewing a neural network as a computation graph is how all automatic differentiation engines work (particularly reverse-mode where one needs to traverse through all the previous computations to correctly apply the gradient), and there were several libraries predating Tensorflow following this idea. The initial contribution of Tensorflow and PyTorch was more about making the developer interface much cleaner and enabling training on a wider range of hardware by developing a bunch of useful kernels as part of the library.
  - dekhn 3y ago
    I always thought of seeing most computations of functions as computational graphs- at least, when I used MathLink to connect Mathematica to Python, it basically gives you a protocol to break any Mathematica function into its recursively expanded definition. Konrad Hinsen suggested using python's built-in operator overloading, so if you said "1 + Symbol('x')" it would get converted to "Plus(1, Symbol('x')) and then sent over MathLink to Mathematica, which would evaluate Plus(1, x), and return an expression which I'd then convert back to a Python object representation. I don't think we talked about doing any sort of automated diff (in my day we figured out our own derivatives!) but after I made a simple eigendecomp of a matrix of floats, the mathematica folks contributed an example that did eigendecomp of a matrix with symbols (IE, some of the terms weren't 5.7 but "1-x"). Still kind of blows my mind today how much mathematica can do with computation graphs. IIUC this is the basis of LISP as well.
    - dkislyuk 3y ago
      The one distinction I would add with neural networks is that it's not just a recursive tree traversal that one would get when evaluating an arithmetic statement, but an actual graph: a computation node can have gradients from multiple sources (e.g. if a skip connection is added), so each node needs to keep accumulated state around that can be updated by arbitrary callers. Of course, optimized autograd / autodiff is more parallelized than node-based message passing, but it's a useful model to start with.
      - 3y ago
ttul 3y ago
Indeed, the self-attention mechanism within the transformer architecture is often described as a graph, where tokens are the nodes and the key and query vectors are combined to establish the affinity that each token has for each other token.
- blackbear_ 3y ago
  These are two different things, actually. The graph you are talking about is constructed using the inputs of the attention layer (ie, nodes=tokens, edges=affinity), while the article talks about graphs that represent the actual operations performed in the attention layer (ie, nodes=weights and intermediate results, edges=mathematical operations that combine them).
garganzol 3y ago
The article is a thought-provoking piece of art. A few personal observations from me: a) An acyclic computational graph is equivalent to a program without loops and thus not Turing-complete b) A cyclic computational graph is equivalent to a program with recursion. The closest analogy from the programming world is a program without loops but with recursive calls. This means that it has Turing completeness, as loops are fully interchangeable with recursion (just different facets of the same thing). As easy as 2+2=4. This means that a neural network is essentially a program. The only difference is the way to write the program: neural networks do it themselves by "learning". Those simple observations explain everything. Brain is essentially a biological Turing-complete processing unit with full plasticity, as you can build any network (program) by changing "weights" of the neurons. This also means that full AI is possible, it is just a matter of the available computational power. Why is that? Because Turing completeness guarantees the absence of boundaries for achieving progressively sophisticated system abilities.
- gcr 3y ago
  Most neural networks these days aren't recursive however. GPT-3 and friends certainly isn't, unless you count the inference loop as recursion, which is bounded both by vocabulary size and maximum token length (hardcoded for now).
  - garganzol 3y ago
    This only means that there is so much more space for AI to grow and improve in the future. As far as I know, having a recursion in neural networks poses an extravagant dilemma: from one hand, recursive networks are more capable; from another, they are harder to train and may have issues with stability caused by occasional positive feedback loops.
    - gcr 3y ago
      well, be careful with "more capable" - the universal approximation theorem shows that a NN with one hidden layer is able to represent any function (in the limit of how wide that layer is, at least). So there's nothing fundamental about "more capable" or "less capable." It's only about which representations are easy to train and which aren't.
blackbear_ 3y ago
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!
  - 3y ago
gavi 3y ago
I highly recommend the video from karpathy https://www.youtube.com/watch?v=VMj-3S1tku0 https://www.youtube.com/watch?v=VMj-3S1tku0 - This explains the same idea spelled out in code. It really helped me understand the mathematical expression graph of neural networks. He uses graphviz to show the expressions and initially calculate gradients manually and then implement back propagation.
data_maan 3y ago
This says nothing new. This idea was around since the 80s, if not earlier, and used extensively for automatic differentiation textbook. But, for an audience that seems to think it rides on the frontier of knowledge and that we have just discoveres things (when, in fact, it's our ignorance of earlier research that is the reason that we are re-discovering them), such a medium post might be like a drug :D
- touisteur 3y ago
  The interesting thing, to me is how this taskgraph representation of neural networks has taken off AND been optimized to hell, just looking at the techs behind tensorrt, jax, openvino, tvm,finn and the whole hell these tools make the graph go through to wring interesting performance, is amazing. For once, we almost standardised on one (or 2, or 3, relatively transpilable) simpler language/DSLs, and a whole industry jumped on optimizing them is rarely heard of, except for gcc and llvm. This actual 'at last a new reduced semantic that we can maybe optimized better' has such huge effort (and success) behind is the amazing part, for me.
- garganzol 3y ago
  Sometimes simple (and old) ideas start to click and ignite a tornado when the timing is right. While many may argue that the notion of a computational graph was associated with neural networks (NN) from the very beginning, this post is quite novel. It sheds the light on how NN and the general computation theory are actually interconnected, it is basically the same thing. For me, it was an instant blast: the computational graph reminds me a typical intermediate representation (IR) tree of a textbook compiler. And because it is a formal graph, all mathematical benefits of the graph theory suddenly start to click. For instance, the graph theory formalizes the definitions of cyclic directed graphs versus acyclic directed graphs. If we imagine for a moment that a graph vertex represents a unit of computation, and an edge represents a data flow, it immediately starts to resonate with Lambda calculus. It quickly becomes evident that when the graph is cyclic, it represents a recursion in terms of Lambda calculus and thus becomes Turing-complete. If computational graph is acyclic, Turing completeness is not achievable. If you are going to say that this is an obvious and well-known observation - I will be surprised, because it is not. And all that enlightenment was possible thanks to this article combined with a bit of knowledge about graphs, compilers, and lambda calculus. (It just so happened that I'm relatively well-versed in those topics due to a professional involvement.) --- If we continue to formalize this observation further, we may soon find a formal proof that a program P and a neural network NN are equivalent: P ~= NN Both have inputs (I) and outputs (O): O = P(I) O = NN(I) Both perform a computation by calculating output O for a given input I. The Turing-completeness observation and the direct mapping to and from the Lambda calculus will give us a way to translate an arbitrary program P to an equivalent neural network NN: P -> NN But the most intriguing part is that the inverse operation also becomes available: NN -> P Congratulations. We have just found a way to translate a working neural network NN to a formal program P written in a programming language L. What are consequences of that? The most obvious one is that we can now create a software that will be able to automatically translate a trained neural network NN to a working deterministic program P written in a programming language of choice and vice versa. We have just made a small step towards an imaginary AI system that can work as good as a professional software developer. Basically, one day we will be able to create a software-based software developer, a skilled one. And the level of skills will 100% surpass human abilities one day because Turing-completeness guarantees the unboundedness. The steps of NN -> P and P -> NN translation may be performed by the neural network itself. It seems that we already started to see that with ChatGPT 3. --- As you can see, one simple observation allowed us to precisely calculate the future for many years ahead. And this is why I love the math so much.
bjourne 3y ago
I don't get the profundity. Computational directed acyclic graphs have been aa mainstay of computer science for decades.

103 points by softwaredoug 3y ago

Ironically the very first publication on "Backpropagation" by a Finish master student (1972) already pointed out how to compute gradients in computational graphs. This if anything is the main thing which distinguishes Backpropagation as an algorithm from simply applying the chain rule.

dynamite-ready 3y ago

Wasn't that the paradigm behind Tensorflow?

ggr2342 3y ago
AFAIK it was first brought forward by PyTorch. I may be wrong though.
- 6gvONxR4sf7o 3y ago
  It's been a core part of automatic differentiation for decades.
  - ggr2342 3y ago
    Oh! Can you give some pointers where to read about it more?
    - PartiallyTyped 3y ago
      The original 2017 PyTorch paper is probably a good one.
    - 6gvONxR4sf7o 3y ago
      The wikipedia page for automatic differentiation and its references would be a good start. https://en.wikipedia.org/wiki/Automatic_differentiation https://en.wikipedia.org/wiki/Automatic_differentiation In particular, the section "Beyond forward and reverse accumulation" tells you how hard it is to deal with the graph in optimal ways, hence the popularity of simpler forwards and backwards traversals of the graph.
- cgearhart 3y ago
  It certainly pre-dates PyTorch. Applying computational graphs to neural networks was the central purpose of the Theano framework in the early 2010s. TensorFlow heavily followed those ideas, and Theano shut down a year or two later because they were so close conceptually and a grad research lab can’t compete with the resources of Google.
- mhh__ 3y ago
  PyTorch's insight was to be very dynamic and simple. The underlying model is basically the same with the caveat that tensorflow uses/used something called a "tape".
- HarHarVeryFunny 3y ago
  Before PyTorch there was Torch (which was Lua-based, hence the Py- prefix of the follow on PyTorch). With Torch, like the later TensorFlow 1.0, you first explicitly constructed the computational graph then executed it. PyTorch's later innovation was define-by-run where you just ran the code corresponding to your computational graph and the framework traced your code and built the graph behind the scenes... this was so much more convenient that PyTorch quickly became more popular than TensorFlow, and by the time TF 2.0 "eager mode" copied this approach it was too late (although TF shot itself in the foot in many ways, which also accelerated it's demise).
dkislyuk 3y ago
As another commenter said, viewing a neural network as a computation graph is how all automatic differentiation engines work (particularly reverse-mode where one needs to traverse through all the previous computations to correctly apply the gradient), and there were several libraries predating Tensorflow following this idea. The initial contribution of Tensorflow and PyTorch was more about making the developer interface much cleaner and enabling training on a wider range of hardware by developing a bunch of useful kernels as part of the library.
- dekhn 3y ago
  I always thought of seeing most computations of functions as computational graphs- at least, when I used MathLink to connect Mathematica to Python, it basically gives you a protocol to break any Mathematica function into its recursively expanded definition. Konrad Hinsen suggested using python's built-in operator overloading, so if you said "1 + Symbol('x')" it would get converted to "Plus(1, Symbol('x')) and then sent over MathLink to Mathematica, which would evaluate Plus(1, x), and return an expression which I'd then convert back to a Python object representation. I don't think we talked about doing any sort of automated diff (in my day we figured out our own derivatives!) but after I made a simple eigendecomp of a matrix of floats, the mathematica folks contributed an example that did eigendecomp of a matrix with symbols (IE, some of the terms weren't 5.7 but "1-x"). Still kind of blows my mind today how much mathematica can do with computation graphs. IIUC this is the basis of LISP as well.
  - dkislyuk 3y ago
    The one distinction I would add with neural networks is that it's not just a recursive tree traversal that one would get when evaluating an arithmetic statement, but an actual graph: a computation node can have gradients from multiple sources (e.g. if a skip connection is added), so each node needs to keep accumulated state around that can be updated by arbitrary callers. Of course, optimized autograd / autodiff is more parallelized than node-based message passing, but it's a useful model to start with.
    - 3y ago

ttul 3y ago

Indeed, the self-attention mechanism within the transformer architecture is often described as a graph, where tokens are the nodes and the key and query vectors are combined to establish the affinity that each token has for each other token.

blackbear_ 3y ago
These are two different things, actually. The graph you are talking about is constructed using the inputs of the attention layer (ie, nodes=tokens, edges=affinity), while the article talks about graphs that represent the actual operations performed in the attention layer (ie, nodes=weights and intermediate results, edges=mathematical operations that combine them).

garganzol 3y ago

The article is a thought-provoking piece of art. A few personal observations from me: a) An acyclic computational graph is equivalent to a program without loops and thus not Turing-complete b) A cyclic computational graph is equivalent to a program with recursion. The closest analogy from the programming world is a program without loops but with recursive calls. This means that it has Turing completeness, as loops are fully interchangeable with recursion (just different facets of the same thing). As easy as 2+2=4. This means that a neural network is essentially a program. The only difference is the way to write the program: neural networks do it themselves by "learning". Those simple observations explain everything. Brain is essentially a biological Turing-complete processing unit with full plasticity, as you can build any network (program) by changing "weights" of the neurons. This also means that full AI is possible, it is just a matter of the available computational power. Why is that? Because Turing completeness guarantees the absence of boundaries for achieving progressively sophisticated system abilities.

gcr 3y ago
Most neural networks these days aren't recursive however. GPT-3 and friends certainly isn't, unless you count the inference loop as recursion, which is bounded both by vocabulary size and maximum token length (hardcoded for now).
- garganzol 3y ago
  This only means that there is so much more space for AI to grow and improve in the future. As far as I know, having a recursion in neural networks poses an extravagant dilemma: from one hand, recursive networks are more capable; from another, they are harder to train and may have issues with stability caused by occasional positive feedback loops.
  - gcr 3y ago
    well, be careful with "more capable" - the universal approximation theorem shows that a NN with one hidden layer is able to represent any function (in the limit of how wide that layer is, at least). So there's nothing fundamental about "more capable" or "less capable." It's only about which representations are easy to train and which aren't.

blackbear_ 3y ago

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!
- 3y ago

gavi 3y ago

I highly recommend the video from karpathy https://www.youtube.com/watch?v=VMj-3S1tku0 https://www.youtube.com/watch?v=VMj-3S1tku0 - This explains the same idea spelled out in code. It really helped me understand the mathematical expression graph of neural networks. He uses graphviz to show the expressions and initially calculate gradients manually and then implement back propagation.

data_maan 3y ago

This says nothing new. This idea was around since the 80s, if not earlier, and used extensively for automatic differentiation textbook. But, for an audience that seems to think it rides on the frontier of knowledge and that we have just discoveres things (when, in fact, it's our ignorance of earlier research that is the reason that we are re-discovering them), such a medium post might be like a drug :D

touisteur 3y ago
The interesting thing, to me is how this taskgraph representation of neural networks has taken off AND been optimized to hell, just looking at the techs behind tensorrt, jax, openvino, tvm,finn and the whole hell these tools make the graph go through to wring interesting performance, is amazing. For once, we almost standardised on one (or 2, or 3, relatively transpilable) simpler language/DSLs, and a whole industry jumped on optimizing them is rarely heard of, except for gcc and llvm. This actual 'at last a new reduced semantic that we can maybe optimized better' has such huge effort (and success) behind is the amazing part, for me.
garganzol 3y ago
Sometimes simple (and old) ideas start to click and ignite a tornado when the timing is right. While many may argue that the notion of a computational graph was associated with neural networks (NN) from the very beginning, this post is quite novel. It sheds the light on how NN and the general computation theory are actually interconnected, it is basically the same thing. For me, it was an instant blast: the computational graph reminds me a typical intermediate representation (IR) tree of a textbook compiler. And because it is a formal graph, all mathematical benefits of the graph theory suddenly start to click. For instance, the graph theory formalizes the definitions of cyclic directed graphs versus acyclic directed graphs. If we imagine for a moment that a graph vertex represents a unit of computation, and an edge represents a data flow, it immediately starts to resonate with Lambda calculus. It quickly becomes evident that when the graph is cyclic, it represents a recursion in terms of Lambda calculus and thus becomes Turing-complete. If computational graph is acyclic, Turing completeness is not achievable. If you are going to say that this is an obvious and well-known observation - I will be surprised, because it is not. And all that enlightenment was possible thanks to this article combined with a bit of knowledge about graphs, compilers, and lambda calculus. (It just so happened that I'm relatively well-versed in those topics due to a professional involvement.) --- If we continue to formalize this observation further, we may soon find a formal proof that a program P and a neural network NN are equivalent: P ~= NN Both have inputs (I) and outputs (O): O = P(I) O = NN(I) Both perform a computation by calculating output O for a given input I. The Turing-completeness observation and the direct mapping to and from the Lambda calculus will give us a way to translate an arbitrary program P to an equivalent neural network NN: P -> NN But the most intriguing part is that the inverse operation also becomes available: NN -> P Congratulations. We have just found a way to translate a working neural network NN to a formal program P written in a programming language L. What are consequences of that? The most obvious one is that we can now create a software that will be able to automatically translate a trained neural network NN to a working deterministic program P written in a programming language of choice and vice versa. We have just made a small step towards an imaginary AI system that can work as good as a professional software developer. Basically, one day we will be able to create a software-based software developer, a skilled one. And the level of skills will 100% surpass human abilities one day because Turing-completeness guarantees the unboundedness. The steps of NN -> P and P -> NN translation may be performed by the neural network itself. It seems that we already started to see that with ChatGPT 3. --- As you can see, one simple observation allowed us to precisely calculate the future for many years ahead. And this is why I love the math so much.

bjourne 3y ago

I don't get the profundity. Computational directed acyclic graphs have been aa mainstay of computer science for decades.