Deep neural networks as computational graphs (2018)

https://medium.com/tebs-lab/deep-neural-networks-as-computational-graphs-867fcaa56c9

by softwaredoug • 3 years ago

103 44 3 years ago

medium.com

dynamite-ready• 3 years ago

Wasn't that the paradigm behind Tensorflow?

ggr23422• 3 years ago

AFAIK it was first brought forward by PyTorch. I may be wrong though.

6gvONxR4sf7o2• 3 years ago

It's been a core part of automatic differentiation for decades.

cgearhart• 3 years 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__3• 3 years 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• 3 years 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).

dkislyuk2• 3 years 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.

dekhn2• 3 years 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.

ttul• 3 years 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_3• 3 years 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).

garganzol5• 3 years 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.

gcr2• 3 years 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).

garganzol5• 3 years 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.

geysersam2• 3 years ago

Brain is essentially a biological Turing-complete processing unit

How do you know that?

Some would answer, "well, everything in the physical universe can be simulated by a Turing machine, so also the brain" but that would be begging the question.

garganzol5• 3 years ago

I just presume that a biological brain is a network of neurons with connections between them, including feedback connections, at least this is what we see under the microscope. In terms of math, this structure corresponds to a cyclic directed computational graph - this only fact makes it Turing-complete.

Currently it is just a highly plausible conjecture, not a formal proof. However, I think I can prove it. But should I?

blackbear_3• 3 years 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/0...

curiousgal• 3 years 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_3• 3 years 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__3• 3 years ago

Not quite. Some people want bump Greeks. For example a company may have a standard bump.

Make of that what you will.

KMag• 3 years 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• 3 years 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'

necroforest• 3 years 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/tensorf... while Jax represents computations in an intermediate representation: https://jax.readthedocs.io/en/latest/jaxpr.html

lgessler• 3 years 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

BaculumMeumEst• 3 years ago

Excellent post, thank you for writing it.

mathisfun123• 3 years 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

Anyway it's just software (and not even particularly clever software), not the second coming lol.

gavi• 3 years ago

I highly recommend the video from karpathy 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• 3 years 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

garganzol5• 3 years 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.

bjourne2• 3 years ago

You might be interested in the universal approximation theorem.

IIAOPSW• 3 years ago

I had an idea, perhaps crackpot, that will maybe catch fire for you too. What if the graph structure of the natural language parse tree was directly reflected in the literal biological neural network. What if the reason for natural language grammar is that it directly reflects the way it is processed under the hood.

touisteur• 3 years 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.

bjourne2• 3 years ago

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

orbifold• 3 years 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.

Deep neural networks as computational graphs (2018)

Related Stories