1
$\begingroup$

I am reading a blog post that tries to explain backpropagation. In the build up the author shows how a naive method for computing gradients is sub-optimal.

Consider this:

Naive feedforward algorithm (not efficient!)

It is useful to first point out the naive quadratic time algorithm implied by the chain rule. Most authors skip this trivial version, which we think is analogous to teaching sorting using only quicksort, and skipping over the less efficient bubblesort.

The naive algorithm is to compute ∂ui/∂uj for every pair of nodes where ui is at a higher level than uj. Of course, among these V2 values (where V is the number of nodes) are also the desired ∂f/∂ui for all i since f is itself the value of the output node.

This computation can be done in feedforward fashion. If such value has been obtained for every uj on the level up to and including level t, then one can express (by inspecting the multivariate chain rule) the value ∂uℓ/∂uj for some uℓ at level t+1 as a weighted combination of values ∂ui/∂uj for each ui that is a direct input to uℓ. This description shows that the amount of computation for a fixed j is proportional to the number of edges E. This amount of work happens for all V values of j, letting us conclude that the total work in the algorithm is O(VE).

I understand the quadratic complexity, but how does this method work without having the training error first?

You must need the training error for updating any parameter, how can you then proceed in a feed forward manner?

$\endgroup$
2
$\begingroup$

Basically forward mode differentiation gives you the derivatives of one specific input for all possible outputs. Respectively backwards differentiation gives you the derivatives for one output over all possible inputs.

So the forward differentiating method does not need a specific training error / output; it just needs all the specific inputs. Correspondingly you do not require any specific inputs when backpropagating; just the outputs at each layer.

This may help understanding: https://colah.github.io/posts/2015-08-Backprop/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.