6 ms·
Understanding Automatic Differentiation in 30 lines of Python
- eachro 3y agoI really enjoy small elegant code demonstrations like this that really allow you to get your hands dirty to try to understand a concept. Another example is Sasha Rush's gpu puzzles, tensor puzzles -https://github.com/srush/GPU-Puzzles https://github.com/srush/GPU-Puzzles -https://github.com/srush/Tensor-Puzzles https://github.com/srush/Tensor-Puzzles
- Scene_Cast2 3y agoIn that case, you might also enjoy https://jaykmody.com/blog/gpt-from-scratch/ https://jaykmody.com/blog/gpt-from-scratch/ (here's the raw code: https://github.com/jaymody/picoGPT/blob/main/gpt2.py https://github.com/jaymody/picoGPT/blob/main/gpt2.py)
- eachro 3y agoThis is really cool! Thanks for sharing :)
- deleted 3y ago[deleted]
- craigching 3y agoAlso micrograd from Andrej Karpathy: https://github.com/karpathy/micrograd https://github.com/karpathy/micrograd
- stkdump 3y agoThe variant of auto differentiation I know doesn't build up a graph of operations. Instead it calculates the corresponding value on the fly.
- fjkdlsjflkds 3y agoYou are probably thinking of forward-mode autodiff (which is more useful when the dimensionality of the output of your function is comparatively large), which is different from backward-mode autodiff (which is more useful when the dimensionality of the output is comparatively small). Both will work, but one will be more efficient than the other (depending on the context). For things like "training neural networks", people tend to use backward-mode (since you often want to optimize a single loss output w.r.t. many things).
- montebicyclelo 3y agoHere's my autodiff in 26 lines of Python (2022): https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b042 https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b0...
- blitzar 3y agoI appreciate the brevity, but my brain seems to function way better on a healthy dose of white space. I need to practice some of these alternative methods.
- Cef111 3y agoInteresting video by Andrej Karpathy building an autograd engine, quite insightful: https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7 https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7 Repo: https://github.com/karpathy/micrograd https://github.com/karpathy/micrograd
- IngoBlechschmid 3y agoAutomatic differentiation feels magical. Many compsci people have been captivated by it and wrote introductions, trying to put the technique into a wider perspective. Here is mine, including a "poor man's variant" of automatic differentiation which does without operator overloading, but uses complex numbers instead: https://pizzaseminar.speicherleck.de/automatic-differentiation/notes.pdf https://pizzaseminar.speicherleck.de/automatic-differentiati...
- nicolapede 3y agoIt does feel magic indeed. Nice write up, thanks for sharing it. Would you know of any introduction to back-propagation written in a similar fashion?
- hansvm 3y agoBackprop is the same algorithm? Autodiff computes a derivative by examining a computational graph (either up-front all at once, or implicitly by examining each computation) and producing a new graph. The person defines the forward pass (graph), and the computer figures out the backward pass. Backprop is what happens when you tell the programmer to do the thing autodiff is doing. You examine the computational graph, write down all the local changes that autodiff would do to compute the derivative, and that new code (that you hand-wrote rather than letting a machine generate) is a function computing the derivative by backpropagating error terms through each edge in that computational graph.
- V1ndaar 3y agoI think this goes back to "The complex-step derivative approximation" from 2003 by J. Martins, P. Sturdza and J. Alonso. [0] That paper is a great read! [0]: https://doi.org/10.1145/838250.838251 https://doi.org/10.1145/838250.838251
- dekhn 3y agoAt the time I worked in Machine Learning (94-95) I was unaware of AD and my professor who built the objective function also determined its analytic derivative manually. I didn't learn about it until a few years ago and was amazed because I spend much of the late 90's learning enough Mathematica to make my own analytic derivatives.
- taminka 3y agoi wish people would just call autodiff (or at least describe it) as numerical chain rule, because that’s quite literally all it is (plus a few tricks for not explicitly computing the jacobian for certain operations), it’s a lot more clear that way
- gipp 3y agoMore precise maybe, but I certainly wouldn't call that more clear.
- taminka 3y agoeveryone studies chain rule in school, so it's definitely more clear, especially if you look at the amount of unnecessary complexity and convolutedness in many autodiff explanations (an substantial amount for such a simple subject)
- evertedsphere 3y agoThe version described here and used most frequently in backpropagation implementations, "autodiff", is reverse-mode AD, but forward-mode exists, as does a spectrum of strategies between the two extremes. Sure, it all comes down to the chain rule, but at an algorithmic level the choice is not at all a trivial one. In fact, if asked to use the chain rule to propagate gradients through a computation graph, I suspect most people would intuitively default to the forward mode. (I would!) https://en.wikipedia.org/wiki/Automatic_differentiation#Beyond_forward_and_reverse_accumulation https://en.wikipedia.org/wiki/Automatic_differentiation#Beyo... Given this, it seems useful to use the term to denote a particular method of accumulating the gradients as one traverses the expressions provided by the chain rule.
- sdenton4 3y agoTechnically incorrect! The numerical chain rule uses the method of finite difference, which will accumulate errors as you move through the computation. See the 'differences from other methods' section: https://en.m.wikipedia.org/wiki/Automatic_differentiation https://en.m.wikipedia.org/wiki/Automatic_differentiation The point, as the neighborhood comment says, is that the implementation really matters, and is worthy of study. It's fine to say that autodiff is a family of methods for implementing the chain rule, but incorrect to say that it's 'just' the numerical chain rule.
- globular-toast 3y agoOh, this is interesting. I thought the title referred to symbolic differentiation (that's what you learnt in school, but in a computer). I didn't realise automatic differentiation was a different thing.
- jprete 3y agoThe symbolic differentiation appears to be embedded in the algorithm, based on reading the article and skimming the algebraic expression trees.
- korvalds 3y agoVery similar to techniques used in Knowledge Based Engineering systems, where the term "dependency tracking" is used. Together with caching of nodes/tensors this reduces calculations, especially useful for large parametric 3D models. When getting a value it will recursively call the binary/dependency tree to find out which variables have changed and only recalculate them when needed. Custom python objects and properties with __set__ and __get__ methods makes this a built-in feature of an object-oriented model. x = Tensor(3) y = Tensor(5) z = x + y print(x, y) # 3, 5 print(z) # 8 x.value = 4 # when setting value nothing is recalculated print(z) # 9 since getting value triggers recalculation of dependencies that have changed
- tromp 3y agoA concise implementation of automatic differentiation in Haskell: https://crypto.stanford.edu/~blynn/haskell/ad.html https://crypto.stanford.edu/~blynn/haskell/ad.html
- pharmakom 3y agoAnyone know of a purely functional version?
- lbrindze 3y agoI remember seeing this one and an ocaml versions while back. https://gist.github.com/ttesmer/948df432cf46ec6db8c1e83ab59b1b21 https://gist.github.com/ttesmer/948df432cf46ec6db8c1e83ab59b...
- marcle 3y agoI wrote a purely functional AD library in Mercury [0], which adapts a general approach from [1]. I believe that Owl provides a similar approach [2]. [0] https://github.com/mclements/mercury-ad https://github.com/mclements/mercury-ad [1] https://github.com/qobi/AD-Rosetta-Stone/ https://github.com/qobi/AD-Rosetta-Stone/ [2] https://github.com/owlbarn/owl/tree/main/src/base/algodiff https://github.com/owlbarn/owl/tree/main/src/base/algodiff
- sdenton4 3y agoCheck out Jax: https://jax.readthedocs.io/en/latest/notebooks/autodiff_cookbook.html https://jax.readthedocs.io/en/latest/notebooks/autodiff_cook...
- rd11235 3y agoAnyone who believes that this completes their understanding of automatic differentiation is tricking themselves. When your graph is a TREE, then everything is very simple, as in this post. When your graph is instead a more general directed acyclic graph (e.g., x = 5; y = 2x; z = xy), then the IMPLEMENTATION is still very simple, but understanding WHY that implementation works is not as simple (repeat: if you think it’s ‘just the ordinary chain rule’, you are tricking yourself). One of the earliest descriptions of this was by Paul Werbos. He called the required rule “the chain rule for ordered derivatives”, which he proved by induction from the ordinary chain rule. But it is nevertheless not immediately evident from the ordinary chain rule. I welcome anyone who believes otherwise to prove me wrong. If you do I will be very happy.
- taminka 3y agochain rule is defined for partial derivatives, so it's still technically just chain rule
- nimonian 3y agoOC's point is that the chain rule for partial derivatives shouldn't be assumed because the ordinary chain rule holds, there's more depth to it than that, and the proof is harder than you might instinctively expect based on the ordinary chain rule. It's epistemically acceptable to understand these both as "the chain rule" once we're satisfied they've both been proved, and apply liberal amounts of synecdoche from there (and I don't think OC disagrees with you on that).
- rd11235 3y agoActually by 'ordinary chain rule' I am referring to what you're referring to as 'the chain rule for partial derivatives'. It seems like backprop follows very quickly even from that, but it does not.
- rd11235 3y ago> chain rule is defined for partial derivatives I agree. That's what I'm referring to as 'the ordinary chain rule'. > so it's still technically just chain rule No. Go try to derive backprop for general DAGs using only the chain rule. If you complete the proof, then you will agree that the proof was more elaborate than you ever expected.
- rebeccaskinner 3y agoI've been meaning to learn more about this for a while, but haven't made time for it because I had assumed it would be more complicated than this. It's surprisingly accessible. As a haskell person, the implementation here brings to mind a free monad (https://serokell.io/blog/introduction-to-free-monads https://serokell.io/blog/introduction-to-free-monads) with a fairly trivial interpreter.
- deleted 3y ago[deleted]
- danbruc 3y agoWhat is the reasoning behind calling the class a tensor? Is there some way to think of the represented expression or its derivative as a tensor? Or just because scalars are tensors and this could be extended to support other tensor types?
- jdthedisciple 3y agoI might be wrong but mathematically we would call a 2-dimensional object a matrix and a 3- or higher-dimensional object a tensor. Now I guess since the described auto grad algorithm works for arbitrarily high dimensional objects it makes sense to call these objects tensors.
- danbruc 3y agoTensors are objects that combine in a certain way and act on vectors in a certain way, they roughly represent a collection of linear transformations. One way to represent a tensor is a matrix after fixing a basis.
- mbbutler 3y agoMachine learning people use "tensor" to just mean an N-dimensional array of numbers. The term is divorced from its meaning in Physics and Mathematics, which caused me some confusion when I started looked at machine learning papers coming from physics.
- jdthedisciple 3y agoAgain, doesn't seem so divorced: "N-dimensional array of numbers" pretty much works for Mathematics from my understanding.
- eli_gottlieb 3y agoAD is just a Cartesian lens of Jacobians and total derivatives in the category of smooth functions, what's the problem? https://www.youtube.com/watch?v=ne99laPUxN4 https://www.youtube.com/watch?v=ne99laPUxN4