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!
