Rendered at 18:03:03 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
akssri 14 hours ago [-]
The intuition here is okay - but the math is hand-wavy with imprecise terms like "blow-up" etc.
The statements however, if taken to mean optimality, are also incorrect. Reverse-mode AD (backprop) is generally quite efficient for scalar outputs (more generally, when n_inputs >> n_outputs), but it's not strictly optimal even for this particular scalar-output case.
Consider for eg. a MLP, with 4-layers with dims (1, N, 1, N, 1) - reverse-mode here does ~3N multiplies, but the optimal is ~2N. The optimal ordering for gradient accumulation is in fact NP-hard on general DAGs, but such 'cross-mode' AD is apparently quite hard to implement and not often seen given the marginal gains.
Griewank-Walther's excellent book is a excellent reference for this and much more,
They also had a library called ADOL-C that had mixed-mode.
eigenspace 2 hours ago [-]
Here's how I like to think about it:
Forwards mode AD (and finite differences) tell you how much wibble of the inputs corresponds to a given wobble in the outputs.
Reverse mode AD tells you how much wobble of the outputs corresponds to a given wibble in the inputs.
If you have more inputs than outputs (such as in optimization), it's cheaper to calculate the wibbles given a wobble, than the other way around.
omnicognate 10 hours ago [-]
I'm not familiar with the details of backprop in neural networks, but AIUI it's an application of automatic/algorithmic differentiation, which comes in two modes: forward and reverse.
Reverse mode is harder to implement as you need to retain state through the calculation, but it scales differently. Forward mode is O(number of inputs) while reverse is O(number of outputs). Seems obvious that reverse mode is what you want for training a neural network, where you have huge numbers of inputs and usually one output, the loss you're training on.
(And indeed that appears to be what the article is saying, in different language.)
_0ffh 6 hours ago [-]
True, though the timeline was more the other way around. Error backprop was used as a method for training before using AD to automate the implementation work became the norm. Previously you had to write the backward pass by hand, now we use AD to derive it from the forward pass.
omnicognate 3 hours ago [-]
Interesting, didn't know that history. I've used algo diff but in unrelated fields. I think it's a technique that has been independently discovered several times and has terribly inconsistent terminology across domains as a result.
dkrylov 14 hours ago [-]
The real reason is that backprop is basically matrix multiplication and multiplying from left to right is way cheaper from right to left. Since on the left side you will have a scalar loss term and you keep vector - matrix multiplication through the network instead of doing matrix by matrix multiplication from the right side.
kazinator 14 hours ago [-]
It's vaguely analogous to why ray tracing goes backwards.
TeMPOraL 19 minutes ago [-]
Which is also not obvious especially given the way it's presented is that it goes forwards.
The naive explanation from the top of my mind (I used to know it better years ago, when I was toying with writing raytracers): because viewport is fixed, an it's much less rays to trace if you cast from viewport pixels in various directions, than if you cast from light sources in every direction and throw away ~99% of them as they never pass through the viewport. Plus, you get spatially uniform image this way, whereas realistic take would oversample the bright parts before giving you any samples for the dark parts.
qwlk4 5 hours ago [-]
Backprop is just memoizing intermediate results. The whole mystique and convoluted explanations (hi Karpathy!) are typical of the whole AI circus.
LoganDark 15 hours ago [-]
So basically it's for the same reason that tup is fast: if the arrows go up, you need far less arrows!
The statements however, if taken to mean optimality, are also incorrect. Reverse-mode AD (backprop) is generally quite efficient for scalar outputs (more generally, when n_inputs >> n_outputs), but it's not strictly optimal even for this particular scalar-output case.
Consider for eg. a MLP, with 4-layers with dims (1, N, 1, N, 1) - reverse-mode here does ~3N multiplies, but the optimal is ~2N. The optimal ordering for gradient accumulation is in fact NP-hard on general DAGs, but such 'cross-mode' AD is apparently quite hard to implement and not often seen given the marginal gains.
Griewank-Walther's excellent book is a excellent reference for this and much more,
https://epubs.siam.org/doi/book/10.1137/1.9780898717761
They also had a library called ADOL-C that had mixed-mode.
Forwards mode AD (and finite differences) tell you how much wibble of the inputs corresponds to a given wobble in the outputs.
Reverse mode AD tells you how much wobble of the outputs corresponds to a given wibble in the inputs.
If you have more inputs than outputs (such as in optimization), it's cheaper to calculate the wibbles given a wobble, than the other way around.
Reverse mode is harder to implement as you need to retain state through the calculation, but it scales differently. Forward mode is O(number of inputs) while reverse is O(number of outputs). Seems obvious that reverse mode is what you want for training a neural network, where you have huge numbers of inputs and usually one output, the loss you're training on.
(And indeed that appears to be what the article is saying, in different language.)
The naive explanation from the top of my mind (I used to know it better years ago, when I was toying with writing raytracers): because viewport is fixed, an it's much less rays to trace if you cast from viewport pixels in various directions, than if you cast from light sources in every direction and throw away ~99% of them as they never pass through the viewport. Plus, you get spatially uniform image this way, whereas realistic take would oversample the bright parts before giving you any samples for the dark parts.