Who Invented Backpropagation?

https://people.idsia.ch/~juergen/who-invented-backpropagation.html

by nothrowaways • 11 months ago

200 100 11 months ago

people.idsia.ch

fritzo• 11 months ago

TIL that the same Shun'ichi Amari who founded information geometry also made early advances to gradient descent.

DoctorOetker2• 11 months ago

Today 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• 11 months 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.

eigenspace3• 11 months ago

Reverse 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• 11 months ago

I 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.

imtringued• 11 months ago

Forward 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.

digikata• 11 months ago

There 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• 11 months ago

There 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.

cubefox4• 11 months ago

See also: The Backstory of Backpropagation - https://yuxi.ml/essays/posts/backstory-of-backpropagation/

pjbk2• 11 months ago

As 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".

pncnmnp3• 11 months ago

I 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-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• 11 months ago

I found this,maybe it helps: https://gwern.net/doc/ai/nn/1986-rumelhart-2.pdf

pncnmnp3• 11 months ago

Apologies - 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.

drsopp• 11 months ago

Perhaps this:

Henry J. Kelley (1960). Gradient Theory of Optimal Flight Paths.

[1] https://claude.ai/public/artifacts/8e1dfe2b-69b0-4f2c-88f5-0...

pncnmnp3• 11 months ago

Thanks! This might be it. I looked up Henry J. Kelley on Wikipedia, and in the notes I found a citation to this paper from Stuart Dreyfus (Berkeley): "Artificial Neural Networks, Back Propagation and the Kelley-Bryson Gradient Procedure" (https://gwern.net/doc/ai/nn/1990-dreyfus.pdf).

I am still going through it, but the latter is quite interesting!

cco• 11 months ago

Count another in the win column for the USA's heavy investment into basic sciences during the space race.

So sad to see the current state. Hopefully we can turn it around.

duped• 11 months ago

They're probably talking about Kalman Filters (1961) and LMS filters (1960).

pjbk2• 11 months ago

To be fair, any multivariable regulator or filter (estimator) that has a quadratic component (LQR/LQE) will naturally yield a solution similar to backpropagation when an iterative algorithm is used to optimize its cost or error function through a differentiable tangent space.

cubefox4• 11 months ago

... 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 think "its" refers to control theory, not backpropagation.

mellosouls• 11 months ago

See Widnall's overview here which discusses some of the ground that crosses over with what has come to be known as backpropagation:

The Minimum-Time Thrust-Vector Control Law in the Apollo Lunar-Module Autopilot (1970)

https://www.sciencedirect.com/science/article/pii/S147466701...

leokoz8• 11 months ago

It is in Applied Optimal Control by Bryson and Ho (1969). Yann LeCun acknowledges this in his 1989 paper on backpropagation:https://new.math.uiuc.edu/MathMLseminar/seminarPapers/LeCunB....

"Since his first work on the subject, the author has found that A. Bryson and Y.-C. Ho [Bryson and Ho, 1969] described the backpropagation algorithm using Lagrange formalism. Although their description was, of course, within the framework of optimal control rather than machine learning, the resulting procedure is identical to backpropagation."

seertaak• 11 months ago

Rumelhart et al wrote "Parallel Distributed Processing"; there's a chapter where he proves that the backprop algorithm maximizes "harmony", which is simply a different formulation of error minimization.

I remember reading this book enthusiastically back in the mid 90s. I don't recall struggling with the proof, it was fairly straightforward. (I was in senior high school year at the time.)

dudu24• 11 months ago

It's just an application of the chain rule. It's not interesting to ask who invented it.

qarl2• 11 months ago

From 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].

uoaei2• 11 months ago

The 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).

piperly• 11 months ago

You got it right: Leibniz!

mindcrime3• 11 months ago

Who 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/...

convolvatron• 11 months ago

don't undergrad adaptive filters count?

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• 11 months ago

I 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.

albertzeyer3• 11 months ago

How 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.

mindcrime3• 11 months ago

They 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.

caycep4• 11 months ago

this fight has become legendary and infamous

caycep4• 11 months ago

this fight has become legendary and infamous, and also pops up on HN every 2-3 years

aaroninsf• 11 months ago

When I worked on neural networks, I was taught David Rumelhart.

cs7022• 11 months ago

Whatever 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-physicsp...

icelancer• 11 months ago

Didn't click the article, came straight to the comments thinking "I bet it's Schmidhuber being salty."

Some things never change.

throwaway2562• 11 months ago

Do yourself a big favour and read the article before commenting, perhaps?

Hint: Schmidhuber has amassed solid evidence over years of digging.

matusp• 11 months ago

I 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.

eigenspace3• 11 months ago

For 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

Lerc2• 11 months ago

I think Hinton himself has made that observation.

In a recent talk he made a quip that he had to change some slides because if you have a Nobel prize in physics you should at least get the units right.

DalasNoin• 11 months ago

At least among friends who are studying physics at university, many have had some kind of ML model as part of their thesis project, like an ML model to estimate early universe background radiation. Whether that's actually useful for the field is another question.

cs7022• 11 months ago

Yeah, I agree with that. When I first saw the announcement, my immediate thought was something like "huh, the Nobel guys sure want to make sure they've given an award for something related to AI which they can describe as foundational." However, I do think Hinton, Bengio, and LeCun deserved their Turing Award.

fooker3• 11 months ago

wasnt impactful at all to the physics community

There are two reasons why Hinton got the prize.

A good majority of modern physics research depends on ML in some aspect. Look at the list of talks at any physics conference and count the number of talks that mention ML in the title.

And the 'physics community' has not produced any fundamental physics for a while. Look at the last several years of physics nobel prize. You can categorize the last ten years of prizes into two categories: engineering breakthroughs, and confirming important predictions. Both are impportant, but lacking fundamental physics breakthroughs, they are not clearly ahead in impact compared to ML.

caycep4• 11 months ago

granted, this goes way back before the Nobel and isn't limited to the trio above. JS is known for frequently and publicly challenging anyone who presents anything on neural networks. He was pestering Ian Goodfellow about who did GANs first in a NEURIPS tutorial in 2016, amongst others

cubefox4• 11 months ago

Evidently, many other scientists disagree, because both awards were granted in consultation with the scientific community.

That's not a good argument. They do in fact sometimes give awards with which the "scientific community" disagrees. Schmidhuber actually gave object level arguments on why the official justification for the Turing award contained substantial errors.

uoaei2• 11 months ago

Calling the implementation of chain rule "inventing" is most of the problem here.

dicroce• 11 months ago

Isn't it just kinda a natural thing once you have the chain rule?

whimsicalism3• 11 months ago

yes

vintermann• 11 months ago

Reverse 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• 11 months ago

Funny that hinton is not mentioned. Like how childish can the author be?

cma• 11 months ago

I 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.

albertzeyer3• 11 months ago

What do you mean? This popular paper is cited:

[RUM] DE Rumelhart, GE Hinton, RJ Williams (1985). Learning Internal Representations by Error Propagation.

bjornsing• 11 months ago

The 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_3• 11 months ago

Funny 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.

Lerc2• 11 months ago

That'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• 11 months ago

You don't think the people who invented the chain rule understood what it means?

Kranar3• 11 months ago

It's not at all obvious, as the article points out it was assumed for 40 years that backpropagation was not an efficient approach for training neural networks.

nothrowaways• 11 months ago

It still is not efficient approach.

Anon84• 11 months ago

Can we back propagate credit?

amai• 11 months ago

Good ideas are never invented. They are always rediscovered.

kypro• 11 months ago

I'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• 11 months 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.

cubefox4• 11 months ago

Apart from backpropagation, the biggest improvements were probably changes in the network architecture. Standard feed-forward MPCs are fairly inefficient. Then there were architectures like CNNs, LSTMs, Transformers. There were also improvements in the activation function and in the gradient descent method (AdamW), but I'm not sure whether these had a substantial impact like CNNs or Transformers. Another factor was training on GPUs.

vonneumannstan• 11 months ago

The only surprise here is that Schmidhuber himself didn't claim to invent it lol

6gvONxR4sf7o• 11 months ago

My 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

joshu• 11 months ago

It's always Schmidhuber

galaxyLogic• 11 months ago

whimsicalism3• 11 months ago

Despite the common refrain about how different symbolic differentiation and AD are, they are actually the same thing.

DoctorOetker2• 11 months ago

Not 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.

whimsicalism3• 11 months ago

I 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

riedel• 11 months ago

The 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=schmidhubere...

caycep4• 11 months ago

dear lord he's in urban dictionary now?!

rramadass• 11 months ago

Relevant:

Annotated History of Modern AI and Deep Learning - 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-pioneer...

pyman• 11 months ago

Great article and research!

Who Invented Backpropagation?

Related Stories