Back-propagation for the rest of us

Introduction

In this short article notes we give an account of the famous back-propagation algorithm. We decouple it from the learning process and describe what it is about. The aim of this material is pedagogical and limited in scope with the purpose of on-boarding interested readers to the work horse of modern learning algorithms. We describe it in the general case by avoiding any reference to neural networks unless it is completely necessary as a means of motivation. We present the general back-propagation algorithm as a warm-up, then we move to the back-propagation through time algorithm. Finally we close with the blocked back-propagation algorithm which is of practical importance.

For the reader

The main article is written in LaTex and TikZ. You can find the source code and the generated pdf file in this repository. I find LaTeX an ideal for expanding the details of this short article because it allows the expression of the mathematical reasoning. I recommend to use the article as a quick exposition of the general idea and head to the PDF document for the details. There we present the blocked back-propagation algorithm that is of practical importance.

Back propagation algorithm

Our target is a function that can be factored as a series of function applications. We can use an approximation scheme in a similar manner with the help of known functions all from different parametric families. Without loss of generality we pose the requirement that all of them are defined on the same parameter space (we will revise this later). Here is the scheme in all its glory.

For computing the derivative for a generic parametric scheme, we make the following observation

Take a close look on how this derivative takes the form of an affine transformation on the derivative of the input. Our approximation scheme under the derivative takes the form

Now we give the algorithm that computes the total A and b from the partial A and b, the indexed ones.

==============================

The Back-propagation Algorithm

==============================
Require fixed x and λ
A <- I and b <- 0 and K <- k
While k ≥ 1
b <- b + A × b[k]
A <- A × A[k]
k <- k - 1
End While

return A,b

==============================

At the very end:

Back-propagation through time algorithm

Here, we generalize the previous equations including time and state. This can be done through the equation of a non-linear dynamical system which in absence of driving input it is autonomous.

As before we approximate this system with a scheme of the form

The functions appearing can be factorized as in the previous section and the previous methodology applies. Our purpose is to find the derivative of y at time T. This equation can be transformed to a diagram of the form

where

Let us write as an operator, the application of back-propagation algorithm

Now we are ready to give the back-propagation through time algorithm for the calculation of the said derivative. How to derive it, is easy, if we notice the similarities between the previous diagram and the one for back-propagation

==============================

The Back-propagation Through
Time Algorithm

==============================
Require fixed x[.], z[.] and λ
A <- I and b <- 0 and T <- t
While t ≥ 1
temp1,temp2 = BP(β(.,x[t] | λ)
b <- b + A × temp1
A <- A × temp2
t <- t - 1
End While

temp1,temp2 = BP(α(.,x[T] | λ)
return temp2 × b + temp1

==============================

As you can see the back-propagation through time algorithm is in reality a double back propagation one.

Blocked back-propagation algorithm

We now revise our initial assumption of the uniform parameter. We make the assumption that it is a block of parameters, a block for each component of the scheme

Now the scheme we saw in the beginning takes the form

which upon derivation gives

The form has to do with the fact that the b components are localized to the blocks (see LaTex document for the derivation).

By taking into consideration that

our task is to find the A and bb, the blocked form of b. The interesting fact is that A is common among the blocks. Here is the algorithm that takes into account the block structure.

==============================

The Blocked Back-propagation Algorithm

==============================
Require fixed x and λ
A <- I and bb <- [] and K <- k
While k ≥ 1
bb[k] <- A × b[k]
A <- A × A[k]
k <- k - 1
End While

return A, bb

==============================

In an analogous manner, the blocked derivative is b. The back-propagation through time algorithm has a double blocked nature, owing to the distinct parameter sets of α and β algorithms and to the blocked nature of each one. See the LaTeX document for the details.

Epilogue

I know it is a bit of notation and calculations to digest. Take your time to follow the computations, paper and pencil are highly recommended. I hope that now, you have a better understanding of this simple but also confusing topic. The source code is a sufficient example of TikZ usage. Have a look. For the resizing I used the following command line

%userprofile%\scoop\apps\imagemagick\current\magick fig1.pdf -verbose -density 700 -trim -quality 100 -sharpen 0x1.0 fig1.png

Feel free to commend if something is wrong. Thank you for your attention. Cheers!