31:Td3f,md`# Back Propagation Math Example. There's plenty of how it works videos and blog posts out there, but I still thought it would be fun to make a truly interactive one. It always helps me to be able to play around with setup variables and inputs, so who knows, maybe it helps you to. The example in this notebook demonstrates how to implement backpropagation for a multi layer convolutional neural network. We'll keep things as minimal as possible, use just one sample and a trivial network with just one hidden layer. We'll also be using automatic differentiation, and [ganja.js](https://github.com/enkimute/ganja.js) to help us with matrix math and multivariate dual numbers. We wont be using an AI library like tensorflow.js, as the point is showing the inner workings - not hiding them. It'll only take a good 15 lines of code to tackle this problem, so fear not ! ## Our problem The task at hand is to train a convolutional neural network to learn an (unknown, non-linear) function by looking at examples only. Specifically, we'll only have one training example ${tex`[0.05,0.1]`} and we'll expect our network to return ${tex`[0.01,0.99]`}. We'll be using a three-layer four-neuron network with a commonly used sigmoid activation function. There will be 8 weights (2 for each neuron) and 4 biases to optimize, and we'll be using gradient descent to minimize a mean-squared error function. ## Our network
The hidden (h0,h1) and output (o0,o1) neurons are dot products between the neuron's weight and the vector of outputs from the previous layer, tranformed with a sigmoid (logistic) function. The cost function we use is the common mean-squared error : ${tex`\frac{1}{2}\sum(sample_x-expected_x)^2`} And we'll use the logistic (sigmoid) activation function : ${tex`S(x) = \cfrac{1}{1+e^{-x}}`} The problem now becomes finding the weights that optimize the cost function. For that we'll need partial derivatives that tell us how the cost function changes when each of the weights changes individually. To calculate those derivatives we'll use multi-variable dual numbers. We have 12 weights and biases to optimize, so we'll need to construct an Algebra who's elements have 13 components, 1 real and 12 dual. `32:T94c,md`## Our Matrices Let's switch to matrix notation before we dive into the code - these network pictures are always nice, but they also quickly hide the simplicity of what we are doing. So, we'll start from an input sample ${tex`sample = \begin{bmatrix}0.05 \\ 0.1\end{bmatrix}`} We'll augment that with a ${tex`1`} for the bias : ${tex`sample = \begin{bmatrix}0.05 \\ 0.1 \\ 1\end{bmatrix}`} For the hidden layer our weights will be a 2x3 matrix. (shown with initial values used in the code) ${tex`\text{WH} = \begin{bmatrix}0.15 && 0.20 && 0.35 \\ 0.25 && 0.30 && 0.35 \end{bmatrix}`} The product ${tex`\text{WH}*sample`} is the convolution. (it is for each neuron a dot product between the input and the weights for that neuron). The result is a 2-component vector. Next we'll define the activation function as operating on each component of a vector. ${tex`\text{logistic}(x) : x_i = \cfrac{1}{1+e^{-x_i}} \space \space \forall x_i `} Now we can calculate the activation of the hidden layer with : ${tex`\text{hidden\_activations} = logistic(\text{WH} * sample)`} The result would be a 2 element vector, we again augment that with a ${tex`1`} bias for the output layer and use the following initial weight matrix : ${tex`\text{WO} = \begin{bmatrix}0.40 && 0.45 && 0.60 \\ 0.50 && 0.55 && 0.60 \end{bmatrix}`} Combining it all, we can forward evaluate our entire network eloquently : ${tex`\text{forward}(sample) = logistic( \text{WO} * \begin{bmatrix} logistic( \text{WH} * sample) \\ 1 \end{bmatrix} )`} Our error function can now be defined : ${tex`error(sample,expected) = \frac{1}{2}(forward(sample)-expected)^2`} Our task is to find the weights ${tex`\text{WH}`} and ${tex`\text{WO}`} that minimize the error. The method we use to do that is gradient descent, with dual numbers for the automatic calculation of the 12 needed partial derivatives. Labeling the elements from ${tex`\text{WH}`} and ${tex`\text{WO}`} as ${tex`e_1`} to ${tex`e_{12}`} the updates at each step are given by ${tex`update_i = -learning\_rate * \cfrac{\delta error}{\delta e_i}`} Using dual numbers, the partial derivative above is particularly easy to calculate, you get it for free when you calculate the forward step. Before we dive into the solution of our problem, lets quickly review dual numbers in ganja.js : `33:T561,NN_AND = A.inline(()=>{ // The initial weights, input and desired output of our network. var input = [[.35,.20],[0.7,0.55],[0.17,0.8],[0.9,0.3]], // input samples. WH = [[.15+1e1,.20+1e2,.35+1e3],[.25+1e4,.30+1e5,.35+1e6]], // hidden layer weights and bias WO = [[.40+1e7,.45+1e8,.60+1e9],[.50+1e10,.55+1e11,.60+1e12]], // output layer weights and bias expected = [[0.01,0.99],[0.99,0.01],[0.01,0.99],[0.01,0.99]]; // desired outputs. // The activation function, forward evaluator and error function. var logistic = x=>this.inv(1+this.exp(-x)), forward=(sample)=>(WO*[...(WH*[...sample,1]).map(logistic),1]).map(logistic), error = (sample,expected)=>.5*(expected-sample)**2; // Now train the network. for (var k=0;k<500;k++) { var update=input.reduce((l,c,i)=>l-5*error(forward(c), expected[i]),0); // forward eval WH = WH+[[...update.slice(1,4)],[...update.slice(4,7)]]; // backpropagate hidden layer WO = WO+[[...update.slice(7,10)],[...update.slice(10,13)]]; // backpropagate output layer } // Return some info (only WO and WH really needed) return { forward:forward,input,WO,WH,out:input.map(i=>forward(i).map(x=>x.s.toFixed(2)*1)), error:input.reduce((a,b,i)=>a+error(forward(b),expected[i]).s,0),expected} })()34:[] 2f:{"title":"Back Propagation Math Example.","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":376,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":425,"value":"md`## Automatic Differentiation\n\nIn the challenge above we have to calculate 12 partial derivatives, but before we do that lets start of with a single-variable example. Assume we have a function ${tex`f`} \n\n ${tex`f(x) = 3x^2 + 6`}\n\nAnd we want to evaluate the derivative ${tex`f'`} at ${tex`x=2`}. Using Dual numbers in ganja.js that looks like this :\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":430,"value":"Algebra(0,0,1,()=>{\n var f = x=>3*x*x + 6;\n return f(2+1e0)\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":435,"value":"md`So in one sweep go we found both ${tex`f(2)=18`} and ${tex`f'(2)=12`}. And we did not have to symbolically derive our function or evaluate it more than once. All we did was input ${tex`x`} and it's derivative, the constant 1 (as ${tex`e_0`}). \n\nThe same trick works for multi variables, although such an Algebra is not a Clifford Algebra, ganja.js can still be used to generate it. Lets demonstrate by evaluating (at [5,2]) the value and both partial derivatives of : \n\n ${tex`f(x,y) = 3x^2 - 2y^3 + 6`}\n\nThe algebra we need is not a Clifford Algebra, so we will have to specify our own basis and cayley table. As a basis we will use ${tex`[1,e_1,e_2]`} and here's the Cayley Table we need :\n\n ${tex`\\begin{bmatrix}1 && e_1 && e_2\\\\e_1&&0&&0\\\\e_2&&0&&0\\end{bmatrix}`}\n\nOnce we have that, we can again calculate both partial derivatives with a single evaluation of the function itself : \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":510,"value":"Algebra({\n basis : ['1','e1','e2'],\n Cayley: [[\"1\",\"e1\",\"e2\"],\n [\"e1\",\"0\",\"0\"],\n [\"e2\",\"0\",\"0\"]]},\n ()=>{\n var f = (x,y)=>3*x*x - 2*y*y*y + 6;\n return f(5+1e1,2+1e2)\n }\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":516,"value":"md`To optimize our neural network, we'll need an algebra with 12 of these dual components. (1 for each of the weights and biases).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":178,"value":"md`## Our Code\nWe proceed as above and create an Algebra with 12 dual components. We'll also define an inverse function. This is the algebra we will use for weights, activation and error values.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":190,"value":"A = {\n var nrDuals = 12;\n var basis = [...Array(nrDuals+1)].map((x,i)=>i?\"e\"+i:\"1\");\n var Cayley = basis.map(x=>basis.map(y=>x=='1'?y:y=='1'?x:\"0\")); \n var A = Algebra({basis,Cayley});\n A.inline(function(A){\n A.describe();\n A.inv = x=>x.map((c,i)=>i?-c/(x.s**2):1/c); // inverse function.\n })(A);\n return A;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":214,"value":"md`We'll define our input, output, and starting weights. For each parameter that we want a derivative of, we add in another dual basis vector.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":441,"value":"setup = A.inline`{\n sample : [0.05, 0.1],\n expected : [0.01, 0.99],\n WH : [[.15+1e1,.20+1e2,.35+1e3],[.25+1e4,.30+1e5,.35+1e6]],\n WO : [[.40+1e7,.45+1e8,.60+1e9],[.50+1e10,.55+1e11,.60+1e12]]\n}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":204,"value":"md`Now we can define the sigmoid function. The sigmoid is the default choice for logistic regression. We simply use the formula from above : ${tex`\\cfrac{1}{1+e^{-x}}`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"sigmoid = A.sigmoid = A.inline(x=>x.map(x=>this.inv(1+this.exp(-x))))","pinned":true,"hidden":false,"mode":"ojs"},{"id":234,"value":"md`Next, we implement the forward evaluator. We multiply the input sample with the weights of the hidden layer, WH, and apply the sigmoid to it. This gives us the activation vector of the hidden layer which we extend with a bias ${tex`1`}, before multiplying with the weights of the output layer, WO, and applying the sigmoid once more.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":236,"value":"forward = A.forward = A.inline((sample,WO,WH)=>this.sigmoid(WO*[...this.sigmoid(WH*[...sample,1]),1]))","pinned":true,"hidden":false,"mode":"ojs"},{"id":479,"value":"md`The error function is also a straightforward implementation of the math we have above :`","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"error = A.error = A.inline((sample,output)=>.5*(output-sample)**2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":243,"value":"md`Next we evaluate our network to see the results we get with our current weights :`","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"forward(setup.sample,setup.WO,setup.WH).map(x=>x.s)","pinned":true,"hidden":false,"mode":"ojs"},{"id":249,"value":"md`That's not quite the ${tex`[0.01,0.99]`} we are looking for.\n\nIn fact, the error here is :`","pinned":false,"hidden":false,"mode":"ojs"},{"id":257,"value":"error(forward(setup.sample,setup.WO,setup.WH),setup.expected).s","pinned":true,"hidden":false,"mode":"ojs"},{"id":266,"value":"md`So we implement a Gradient Descent optimizer with a learning rate of 0.5. That is, at each step we calculate the partial derivatives of the error function with respect to each of the weights and bias values and update them to minimize the error.\n\nWe repeat this procedure for 4000 epochs.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":268,"value":"optimize = A.inline((sample,WO,WH,expected)=>{\n for (var k=0;k<1000;k++) {\n var update = -0.5*this.error(this.forward(sample,WO,WH), expected); // forward evaluation and error calc\n WH = WH+[[...update.slice(1,4)],[...update.slice(4,7)]]; // backpropagate hidden layer\n WO = WO+[[...update.slice(7,10)],[...update.slice(10,13)]]; // backpropagate output layer\n }\n return {WO,WH}\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":493,"value":"md`And we call that function to find the optimal values of our network`","pinned":false,"hidden":false,"mode":"ojs"},{"id":275,"value":"optimal = optimize(setup.sample,setup.WO,setup.WH,setup.expected)","pinned":true,"hidden":false,"mode":"ojs"},{"id":281,"value":"md`To test, we will again evaluate the network, this time using the optimised weights :`","pinned":false,"hidden":false,"mode":"ojs"},{"id":283,"value":"forward(setup.sample,optimal.WO,optimal.WH).map(x=>x.s)","pinned":true,"hidden":false,"mode":"ojs"},{"id":288,"value":"md`That's much closer to ${tex`[0.01,0.99]`}, in fact we've reduced the error to `","pinned":false,"hidden":false,"mode":"ojs"},{"id":290,"value":"error(forward(setup.sample,optimal.WO,optimal.WH),setup.expected).s","pinned":true,"hidden":false,"mode":"ojs"},{"id":300,"value":"md`## More samples\n\nWe'll put everything together in one block, and make some minor modifications to train on a sample set 4 times as large. (yes four samples !). That gives us a convolutional neural network of 3 layers with Automatic Differentiation and Back propagation. (in 15 lines of code)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":302,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":617,"value":"md`You may have noticed that this last network is actually trained to perform a logical AND operation. Lets test that network on some noisy input : `","pinned":false,"hidden":false,"mode":"ojs"},{"id":620,"value":"({\n \"0 AND 0\" : NN_AND.forward([0,0,1]).map(x=>x.s)[0]>0.5,\n \"0 AND 1\" : NN_AND.forward([0,1,1]).map(x=>x.s)[0]>0.5,\n \"1 AND 0\" : NN_AND.forward([1,0,1]).map(x=>x.s)[0]>0.5,\n \"1 AND 1\" : NN_AND.forward([1,1,1]).map(x=>x.s)[0]>0.5,\n \"------------------------------\":\"\", \n \"0.1 AND 0.3\" : NN_AND.forward([0.1,0.3,1]).map(x=>x.s)[0]>0.5,\n \"0.9 AND 0.8\" : NN_AND.forward([0.9,0.8,1]).map(x=>x.s)[0]>0.5,\n \"0.6 AND 0.2\" : NN_AND.forward([0.6,0.2,1]).map(x=>x.s)[0]>0.5,\n \"0.4 AND 0.5\" : NN_AND.forward([0.4,0.5,1]).map(x=>x.s)[0]>0.5,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":702,"value":"md`Based on just 500 epochs on these 4 imperfect samples, here's the learned decision boundary : `","pinned":false,"hidden":false,"mode":"ojs"},{"id":688,"value":"A.graph((x,y)=>{ return NN_AND.forward([x/2+0.5,y/2+0.5,1])[0].s},{width:128,height:128})","pinned":false,"hidden":false,"mode":"ojs"},{"id":175,"value":"Algebra = require('ganja.js')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}