6 ms·
Who Invented Backpropagation?
- joshu 1y agoIt's always Schmidhuber
- scheisshausDan 1y ago[flagged]
- fritzo 1y agoTIL that the same Shun'ichi Amari who founded information geometry also made early advances to gradient descent.
- DoctorOetker 1y agoToday You Learn that the same Shun'ichi Amari who founded information geometry also made early advances to autodifferentiation. Iterating gradient descent is much, much older, and immediately recognized upon defining what a gradient is (regardless of how one computes this gradient). AD vs { symbolic differentiation, numeric finite "differentiation" } is about the insight how to compute a numeric gradient efficiently both in terms of (space) memory and time (compute) requirements.
- mystraline 1y ago> BP's modern version (also called the reverse mode of automatic differentiation) So... Automatic integration? Proportional, integrative, derivative. A PID loop sure sounds like what they're talking about.
- eigenspace 1y agoReverse move automatic differentiation is not integration. It's still differentiation, but just a different method of calculating the derivative than the one you'd think to do by hand. It basically just applies the chain rule in the opposite order from what is intuitive to people. It has a lot more overhead than regular forwards mode autodiff because you need to cache values from running the function and refer back to them in reverse order, but the advantage is that for function with many many inputs and very few outputs (i.e. the classic example is calculating the gradient of a scalar function in a high dimensional space like for gradient descent), it is algorithmically more efficient and requires only one pass through the primal function. On the other hand, traditional forwards mode derivatives are most efficient for functions with very few inputs, but many outputs. It's essentially a duality relationship.
- stephencanon 1y agoI don't think most people think to do either direction by hand; it's all just matrix multiplication, you can multiply them in whatever order makes it easier.
- eigenspace 1y agoIm just talking about the general algorithm to write down the derivative of `f(g(h(x)))` using the chain rule. For vector valued functions, the naive way you would learn in a vector calculus class corresponds to forward mode AD.
- imtringued 1y agoForward mode automatic differentiation creates a formula for each scalar derivative. If you have a billion parameters you have to calculate each derivative from scratch. As the name implies, the calculation is done forward. Reverse mode automatic differentiation starts from the root of the symbolic expression and calculates the derivative for each subexpression simultaneously. The difference between the two is like the difference between calculating the Fibonacci sequence recursively without memoization and calculating it iteratively. You avoid doing redundant work over and over again.
- deleted 1y ago[deleted]
- digikata 1y agoThere are large bodies of work for optimization of state space control theory that I strongly suspect as a lot of crossover for AI, and at least has very similar mathematical structure. e.g. optimization of state space control coefficients looks something like training a LLM matrix...
- brosco 1y agoThere is indeed a lot of crossover, and a lot of neural networks can be written in a state space form. The optimal control problem should be equivalent to training the weights, as you mention. However, from what I have seen, this isn't really a useful way of reframing the problem. The optimal control problem is at least as hard, if not harder, than the original problem of training the neural network, and the latter has mature and performant software for doing it efficiently. That's not to say there isn't good software for optimal control, but it's a more general problem and therefore off-the-shelf solvers can't leverage the network structure very well. Some researchers have made interesting theoretical connections like in neural ODEs, but even there the practicality is limited.
- blt 1y agoYes, in most cases the reduction of supervised learning to optimal control is not interesting. We can also reduce supervised learning to reinforcement learning, but that doesn't mean we should use RL algorithms to do supervised learning. We can also reduce sorting a list of integers to SAT, but that doesn't mean we should use a SAT solver to sort lists of integers.
- cubefox 1y agoSee also: The Backstory of Backpropagation - https://yuxi.ml/essays/posts/backstory-of-backpropagation/ https://yuxi.ml/essays/posts/backstory-of-backpropagation/
- pjbk 1y agoAs it is stated, I always thought it came from formulations like Euler-Lagrange procedures in mechanics used in numeric methods for differential geometry. In fact when I recreated the algorithm as an exercise it immediately reminded me of gradient descent for kinematics, with the Jacobian calculation for each layer similar to an iterative pose calculation in generalized coordinates. I never thought it was something "novel".
- pncnmnp 1y agoI have a question that's bothered me for quite a while now. In 2018, Michael Jordan (UC Berkeley) wrote a rather interesting essay - https://medium.com/@mijordan3/artificial-intelligence-the-revolution-hasnt-happened-yet-5e1d5812e1e7 https://medium.com/@mijordan3/artificial-intelligence-the-re... (Artificial Intelligence — The Revolution Hasn’t Happened Yet) In it, he stated the following: > Indeed, the famous “backpropagation” algorithm that was rediscovered by David Rumelhart in the early 1980s, and which is now viewed as being at the core of the so-called “AI revolution,” first arose in the field of control theory in the 1950s and 1960s. One of its early applications was to optimize the thrusts of the Apollo spaceships as they headed towards the moon. I was wondering whether anyone could point me to the paper or piece of work he was referring to. There are many citations in Schmidhuber’s piece, and in my previous attempts I've gotten lost in papers.
- psYchotic 1y agoI found this,maybe it helps: https://gwern.net/doc/ai/nn/1986-rumelhart-2.pdf https://gwern.net/doc/ai/nn/1986-rumelhart-2.pdf
- pncnmnp 1y agoApologies - I should have been clear. I was not referring to Rumelhart et al., but to pieces of work that point to "optimizing the thrusts of the Apollo spaceships" using backprop.
- costates-maybe 1y agoI don't know if there is a particular paper exactly, but Ben Recht has a discussion of the relationship between techniques in optimal control that became prominent in the 60's, and backpropagation: https://archives.argmin.net/2016/05/18/mates-of-costate/ https://archives.argmin.net/2016/05/18/mates-of-costate/
- observationist 1y agoKelley 1960 (the gradient/adjoint flight‑path paper) https://perceptrondemo.com https://perceptrondemo.com AIAA 65‑701 (1965) “optimum thrust programming” for lunar transfers via steepest descent (Apollo‑era) https://arc.aiaa.org/doi/abs/10.2514/6.1965-701 https://arc.aiaa.org/doi/abs/10.2514/6.1965-701 Meditch 1964 (optimal thrust programming for lunar landing) https://openmdao.github.io/dymos/examples/moon_landing/moon_landing.html https://openmdao.github.io/dymos/examples/moon_landing/moon_... Smith 1967 & Colunga 1970 (explicit Apollo‑type trajectory/re‑entry optimization using adjoint gradients) https://ntrs.nasa.gov/citations/19670015714 https://ntrs.nasa.gov/citations/19670015714 One thing AI has been great for, recently, has been search for obscure or indirect references like this, that might be one step removed from any specific thing you're searching for, or if you have a tip-of-the-tongue search where you might have forgotten a phrase, or know you're using the wrong wording. It's cool that you can trace the work of these rocket scientists all the way to the state of the art AI.
- dudu24 1y agoIt's just an application of the chain rule. It's not interesting to ask who invented it.
- qarl 1y agoFrom the article: Some ask: "Isn't backpropagation just the chain rule of Leibniz (1676) [LEI07-10] & L'Hopital (1696)?" No, it is the efficient way of applying the chain rule to big networks with differentiable nodes—see Sec. XII of [T22][DLH]). (There are also many inefficient ways of doing this.) It was not published until 1970 [BP1].
- uoaei 1y agoThe article says that but it's overcomplicating to the point of being actually wrong. You could, I suppose, argue that the big innovation is the application of vectorization to the chain rule (by virtue of the matmul-based architecture of your usual feedforward network) which is a true combination of two mathematical technologies. But it feels like this and indeed most "innovations" in ML is only considered as such due to brainrot derived from trying to take maximal credit for minimal work (i.e., IP).
- qarl 1y agoThe real metric is whether anyone remembers it in 100 years. Any other discussion just comes off as petty.
- piperly 1y agoYou got it right: Leibniz!
- mindcrime 1y agoWho didn't? Depending on exactly how you interpret the notion of "inventing backpropagation" it's been invented, forgotten, re-invented, forgotten again, re-re-invented, etc, about 7 or 8 times. And no, I don't have specific citations in front of me, but I will say that a lot of interesting bits about the history of the development of neural networks (including backpropagation) can be found in the book Talking Nets: An Oral History of Neural Networks[1]. [1]: https://www.amazon.com/Talking-Nets-History-Neural-Networks/dp/0262511118 https://www.amazon.com/Talking-Nets-History-Neural-Networks/...
- convolvatron 1y agodon't undergrad adaptive filters count? https://en.wikipedia.org/wiki/Adaptive_filter https://en.wikipedia.org/wiki/Adaptive_filter doesn't need a differentiation of the forward term, but if you squint it looks pretty close
- catgary 1y agoI think it’s the move towards GPU-based computing is probably more significant - the constraints put in place by GPU programming (no branching, try not to update tensors in place, etc) sync up with the constraints put in place by differentiable programming. Once people had a sufficiently compelling reason to write differentiable code, the frameworks around differentiable programming (theano, tensorflow, torch, JAX) picked up a lot of steam.
- albertzeyer 1y agoHow do you not have the citations in front of you? They are all in the article? I don't expect that any relevant (re)invention of backprop is missing there. Or, if you really know some reinvention of backprop that is not mentioned here, tell Jürgen Schmidhuber, he is actually very curious to learn about other such instances that he is not aware of yet.
- mindcrime 1y agoThey are all in the article? Maybe they are. I'm not here to do a deep research project that involves reading every citation in that article. If it makes you feel better, pretend that what I said was instead: "I don't have all the relevant citations stored in my short-term memory right this second and I am not interested in writing a lengthy thesis to satisfy pedantic navel-gazers on HN." Or, if you really know some reinvention of backprop that is not mentioned here, WTF are you on about? I never made any such claim, or anything remotely close to it.
- caycep 1y agothis fight has become legendary and infamous
- caycep 1y agothis fight has become legendary and infamous, and also pops up on HN every 2-3 years
- aaroninsf 1y agoWhen I worked on neural networks, I was taught David Rumelhart.
- cs702 1y agoWhatever the facts, the OP comes across as sour grapes. The author, Jürgen Schmidhuber, believes Hopfield and Hinton did not deserve their Nobel Prize in Physics, and that Hinton, Bengio, and LeCun did not deserve their Turing Award. Evidently, many other scientists disagree, because both awards were granted in consultation with the scientific community. Schmidhuber's own work was, in fact, cited by the Nobel Prize committee as background information for the 2024 Nobel.[a] Only future generations of scientists, looking at the past more objectively, will be able to settle these disputes. [a] https://www.nobelprize.org/uploads/2024/11/advanced-physicsprize2024-3.pdf https://www.nobelprize.org/uploads/2024/11/advanced-physicsp...
- icelancer 1y agoDidn't click the article, came straight to the comments thinking "I bet it's Schmidhuber being salty." Some things never change.
- throwaway2562 1y agoDo yourself a big favour and read the article before commenting, perhaps? Hint: Schmidhuber has amassed solid evidence over years of digging.
- matusp 1y agoI think the unspoken claim here is that the North American scientific establishment takes credit from other sources and elevates certain personas instead of the true innovators who are overlooked. Arguing that the establishment doesn't agree with this idea is kinda pointless.
- eigenspace 1y agoFor what it's worth, it's a very mainstream opinion in the physics community that Hinton did not at all deserve a nobel prize in physics for his work. But that's because his work, and wasnt impactful at all to the physics community
- Lerc 1y ago
- uoaei 1y agoCalling the implementation of chain rule "inventing" is most of the problem here.
- dicroce 1y agoIsn't it just kinda a natural thing once you have the chain rule?
- whimsicalism 1y agoyes
- vintermann 1y agoReverse mode differentiation? No, it can't be that natural since it took until 1970 to be proposed. But also in a sense basic (which you could also guess, since it was introduced in a MSc thesis).
- PunchTornado 1y agoFunny that hinton is not mentioned. Like how childish can the author be?
- cma 1y agoI tried to verify this, and it isn't true. This is one of the first footnotes: [HIN] J. Schmidhuber (AI Blog, 2020). Critique of Honda Prize for Dr. Hinton. Science must not allow corporate PR to distort the academic record.
- albertzeyer 1y agoWhat do you mean? This popular paper is cited: [RUM] DE Rumelhart, GE Hinton, RJ Williams (1985). Learning Internal Representations by Error Propagation.
- bjornsing 1y agoThe chain rule was explored by Gottfried Wilhelm Leibniz and Isaac Newton in the 17th century. Either of them would have ”invented” backpropagation in an instant. It’s obvious.
- _fizz_buzz_ 1y agoFunny enough. For me it was the other way around. I always knew how to compute the chain rule. But really only understood what the chain rule means when I read up on what back propagation was.
- Lerc 1y agoThat's essentially it. Learning what the chain rule does, and learning what it can be used for, and how to apply it. Neither are really inventions, they are discoveries, if anything the chain rule leans slightly more to invention than backdrop. I understand the need for attribution as a means to track the means and validity of discovery, but I intensely dislike it when people act like it is a deed of ownership of an idea.
- Jensson 1y agoYou don't think the people who invented the chain rule understood what it means?
- _fizz_buzz_ 1y agoObviously, Newton and Leibniz and many other Mathematicians (and other people) understood the chain rule before back propagation. But unfortunately I am very far from a Newton or Leibniz, so it took me a lot longer to grasp why the chain rule is the way it is. And back propagation just made it click for me. I was really just talking about me personally.
- cutlilacs 1y agoWhat insight did you gain from back propagation that you didn't have from just the formula of the chain rule?
- Anon84 1y agoCan we back propagate credit?
- amai 1y agoGood ideas are never invented. They are always rediscovered.
- kypro 1y agoI've always found it rather crazy that the power of backpropagation and artificial neural networks was doubted by AI researchers for so long. It's really only since the early 2010s that researchers started to take the field seriously. This is despite the core algorithm (backpropagation) being known for decades. I remember when I learnt about artificial neural networks at university in the late 00s my professors were really sceptical of them, rightly explaining that they become hard to train as you added more hidden layers. See, what makes backpropagation and artificial neural networks work are all of the small optimisations and algorithm improvements that were added on top of backpropagation. Without these improvements it's too computationally inefficient to be practical and you have to contend with issues like exploding gradients. I think Geoffrey Hinton has noted a few times that for people like him who have been working on artificial neural networks for years it's quite surprising that today neural networks just work because for years it was so hard to get them to do anything. In this sense while backpropagation is the foundational algorithm, it's not sufficient on it's own. It was the many improvements that were made on top of backpropagation that actually make artificial neural networks work and take off in the 2010s when some of the core components of modern neural networks started to fall into place. I remember when I first learnt about neural networks I thought maybe coupling them with some kind of evolutionary approach might be what was needed to make them work. I had absolutely no idea what I was doing of course, but I spent so many nights experimenting with neural networks. I just loved the idea of an artificial "neural network" being able to learn a new problem and spit out an answer. The biggest regret of my life was coming out of university and going into web development because there were basically no AI jobs back then, and no such thing as an AI startup. If you wanted to do AI back then you basically had to be a researcher which didn't interest me at the time.
- RaftPeople 1y ago> I remember when I first learnt about neural networks I thought maybe coupling them with some kind of evolutionary approach might be what was needed to make them work. I did this in an artificial life simulation. It was pretty fun to see the creatures change from pure random bouncing around to movement that helped them get food and move away from something eating them. My naive vision was all kinds of advanced movement, like hiding around corners for prey, but it never got close to something like that. As I worked the evolutionary parameters I began to realize more and more that the process of evolving specific advanced traits requires lots of time and (I think) environmental complexity and compartmentalization of groups of creatures. There are lots of simple/dumb capabilities that help with survival and they are much much easier to acquire than a more advanced capability like being aware of other creatures and tracking it's movement on the other side of an obstacle.
- vonneumannstan 1y agoThe only surprise here is that Schmidhuber himself didn't claim to invent it lol
- 6gvONxR4sf7o 1y agoMy favorite take on this is that yes, in fact it is just the chain rule. The usual argument goes that automatic and symbolic differentiation are fundamentally different, so anything particularly old (pre-computers, for example) doesn't count as inventing back prop. But here's my favorite take on equivalences between AD and symbolic diff [0]. I wish there wasn't such importance placed on who invented it for stuff like this. Clearly, someone codifying backprop wasn't a bottleneck in making ML progress, so why's it get so much attention? [0] https://emilien.ca/Notes/Notes/notes/1904.02990v4.pdf https://emilien.ca/Notes/Notes/notes/1904.02990v4.pdf
- galaxyLogic 1y agoSEE ALSO: https://www.stonewright.ai/2023/05/01/picking-apart-the-origins-of-backpropagation/ https://www.stonewright.ai/2023/05/01/picking-apart-the-orig...
- whimsicalism 1y agoDespite the common refrain about how different symbolic differentiation and AD are, they are actually the same thing.
- DoctorOetker 1y agoNot at all. There are mainly 2 forms of AD: forward mode (optimal when the function being differentiated has more outputs than latent parameter inputs) and reverse mode (when it has more latent parameter inputs than outputs). If you don't understand why, you don't understand AD. If you understand AD, you'd know why, but then you'd also see a huge difference with symbolic differentiation. In symbolic differentiation, input is an expression or DAG, the variables being computed along the way are similar such symbolic expressions (typically computed in reverse order in high school or uni, so the expression would grow exponentially with each deeper nested function, and only at the end are the input coordinates filled into the final expression, to end up with the gradient). Both forward and reverse mode have numeric variables being calculated, not symbolic expressions. The third "option" is numeric differentiation, but for N latent parameter inputs this requires (N+1) forward evaluations: N of the function f(x1,x2,..., xi + delta, ..., xN) and 1 reference evaluation at f(x1, ..., xN). Picking a smaller delta makes it closer to a real gradient assuming infinite precision, but in practice there will be irregular rounding near the pseudo "infinitesimal" values of real world floats; alternatively take delta big enough, but then its no longer the theoretical gradient. So symbolic differentiation was destined to fail due to ever increasing symbolic expression length (the chain rule). Numeric differentiation was destined to fail due to imprecise gradient computation and huge amounts (N+1, many billions for current models) of forward passes to get a single (!) gradient. AD gives the theoretically correct result with a single forward and backward pass (as opposed to N+1 passes), without requiring billions of passes, or lots of storage to store strings of formulas.
- whimsicalism 1y agoI simply do not agree that you are making a real distinction and I think comments like "If you don't understand why, you don't understand AD" are rude. AD is just simple application of the pushbacks/pullforwards from differential geometry that are just the chain rule. It is important to distinguish between a mathematical concept and a particular algorithm/computation for implementing it. The symbolic manipulation with an 'exponentially growing nested function' is a particular way of applying the chain rule, but it is not the only way. The problem you describe with symbolic differentiation (exponential growth of expressions) is not inherent to symbolic differentiation itself, but to a particular naïve implementation. If you represent computations as DAGs and apply common subexpression elimination, the blow-up you mention can be avoided. In fact, forward- and reverse-mode AD can be viewed as particular algorithmic choices for evaluating the same derivative information that symbolic differentiation encodes. If you represent your function as a DAG and propagate pushforwards/pullbacks, you’ve already avoided swell https://emilien.ca/Notes/Notes/notes/1904.02990v4.pdf https://emilien.ca/Notes/Notes/notes/1904.02990v4.pdf
- riedel 1y agoThe real essence of the piece is that Leibnitz did not schmidhuber [0] Seppo Linnainma (probably because he was dead at the time). Actually it is a nice piece and I was really happy to get my expectations fulfilled when reading to the very end. [0] https://www.urbandictionary.com/define.php?term=schmidhubered https://www.urbandictionary.com/define.php?term=schmidhubere...
- caycep 1y agodear lord he's in urban dictionary now?!
- rramadass 1y agoRelevant: Annotated History of Modern AI and Deep Learning - https://people.idsia.ch/~juergen/deep-learning-history.html https://people.idsia.ch/~juergen/deep-learning-history.html Japanese scientists were pioneers of AI, yet they’re being written out of its history - https://theconversation.com/japanese-scientists-were-pioneers-of-ai-yet-theyre-being-written-out-of-its-history-243762 https://theconversation.com/japanese-scientists-were-pioneer...
- pyman 1y agoGreat article and research!