{"id":1274,"date":"2016-04-10T23:51:43","date_gmt":"2016-04-10T23:51:43","guid":{"rendered":"http:\/\/blog.themusio.com\/?p=1274"},"modified":"2024-05-01T11:06:33","modified_gmt":"2024-05-01T02:06:33","slug":"backpropagation-through-time","status":"publish","type":"post","link":"https:\/\/blog.themusio.com\/?p=1274","title":{"rendered":"Backpropagation through time"},"content":{"rendered":"

Goal<\/strong>
\nToday’s summary will a give insight into the machinery behind optimization, namely the backpropagation algorithm, in any kind of neural network, whether it is a standard feed forward, convolutional or recurrent one.<\/p>\n

Motivation<\/strong>
\nIn order to adjust the weights of layers in neural networks in a way that the model shows learning behavior, we have to determine how the individual weights influence the final output.<\/p>\n

Ingredients<\/strong>
\nchain rule, differentiation, gradient<\/p>\n

Steps<\/strong>
\nWe start be providing the objects that we have to handle for the above defined task of adjusting the weights in a meaningful way.
\nIn general, we are interested in the behavior of some function depending on the output of the last layer.
\nInstead of just looking directly at the output, one usually defines a loss function that specifies the error that the model is currently making for some task.
\nThen the objective would be to minimize the error and correspondingly the loss function by changing the network accordingly.
\nNow in order to find the direction in which we should push the weights of each layer, we start calculating gradients with respect to the loss function.
\nThe first step is simply to provide the gradient of the loss function with respect to the last output.
\nWe are talking of gradients, since the input to our function, will be a vector in most cases.
\nThis is nothing more than generalizing the one-dimensional partial derivative to multiple dimensions.
\nSince our neural networks possess a certain depth in layers, we also have to calculate the gradients of the loss function with respect to the weights of first layer.
\nThe mathematical tool to accomplish this in a convenient way is called the chain rule.<\/p>\n

The intuition for the backpropagation algorithm can be provided by considering a computation which involves several steps, say first a addition of two numbers and then a multiplication by a third one.
\nAt every step of the computation we are able to compute locally the outputs and the gradients of the outputs with respect to the input.
\nWhen we reach the final layer, we can hence start to back propagate the gradients and obtain a each step and understanding of how to change the input in order to increase or decrease the final outcome of our computation.<\/p>\n

For a neural network the computational steps involve matrix multiplication and activation functions which introduce non-linearity.
\nSince gradient calculations can be rather tricky one usually relies on staged computation by explicitly computing the gradient for every step.
\nIn particular some activation functions, like the sigmoid, are easy to handle since their gradients are not difficult to calculate.
\nEven more simple is the ReLu whose gradient is either one or zero.
\nIn recent years more and more libraries provide the gradient calculations for us.
\nTheano is one framework that allows to build the gradients symbolically along the computational graph.<\/p>\n

Let us now go a little bit more into detail of the actual algorithm.
\nThe first task is to compute the activations for every layer by providing some input.
\nNext we compute the output error, meaning the gradient of the loss function with respect to the output of the last layer.
\nThen we are ready to back propagate this error the previous layer by multiplication with the computed activations of the feed forward step.
\nFinally, we are interested in the gradients of the loss function with respect to the weights, since we are going to adjust those and not the outputs.
\nBut this is just another simple multiplication by the input to the layer we are considering.
\nDespite that chain rule is known quite easy to understand and is known for a long time, the backpropagation algorithm is relatively new.
\nAn alternative way to calculate the gradients directly is to vary the input of every node of a layer by a tiny amount and calculate the effect on the loss function.
\nHowever, in practice this method requires a an enormous amount of computational steps since we should do this for every node in our network.<\/p>\n

For the final part, we take a look at backpropagation in convolutional and recurrent networks.
\nConvolutional networks are not that different from standard ones and so one might guess that there is only little work to be done to adjust the algorithm.
\nIndeed, the only change it needs is taking convolutions of errors and previous outputs instead of matrix multiplication to back propagate the error.
\nRecurrent neural networks involve a time component, since the input is fed as a sequence.
\nHence, in the hidden layers we have to additionally propagate the errors through time.
\nThat’s were the naming for the algorithm in recurrent networks comes from.
\nThe reason for this is that the weights are shared within the layer and the best intuition for that can be gathered by rolling out the network in time.
\nDepending on the length of the input sequence, the steps to compute the gradients of the loss function with respect to the first outputs can become large.
\nThis gives rise to the vanishing gradient problem, since in every step the value of gradient of the activation function is usually between one and zero.
\nTherefore, calculating gradients through several activations quickly leads to a vanishing gradient.
\nIn practice, one truncates the calculation to a few steps.
\nOther attempts involve a proper initialization of the weights, some kind of regularization or introducing LSTM or GRU units.
\nSometimes one also takes care of exploding gradients by clipping the values if the exceed a defined value.<\/p>\n

Resources
\n“<\/strong>CS231n Convolutional Neural Networks for Visual Recognition<\/a>” (WEB). CS231n Convolutional Neural Networks for Visual Recognition. <\/em>Accessed 11 April 2016.
\n<\/em>“Calculus on Computational Graphs: Backpropagation<\/a>” (WEB). Calculus on Computational Graphs: Backpropagation<\/em>. 31st August 2015. Accessed 11 April 2016.
\n“How the backpropagation algorithm works<\/a>” (WEB). How the backpropagation algorithm works<\/em>. 22nd Jan 2016. Accessed 11 April 2016.
\n“Recurrent Neural Networks Tutorial, Part 3 \u2013 Backpropagation Through Time and Vanishing Gradients<\/a>” (WEB). Recurrent Neural Networks Tutorial, Part 3 \u2013 Backpropagation Through Time and Vanishing Gradients<\/em>. 8th October 2015. Accessed 11 April 2016.<\/p>\n","protected":false},"excerpt":{"rendered":"

Goal Today’s summary will a give insight into the machinery behind optimization, namely the backpropagat […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3642,3640],"tags":[3650,3652,3760,3698,3656,4114,3762,3658,3700,3664,4116,4118,3710],"class_list":["post-1274","post","type-post","status-publish","format-standard","hentry","category-ai-en","category-all-en","tag-ai-ja-en","tag-aka-ja-en","tag-artificial-intelligence-en","tag-backpropogation-en","tag-baggage-en","tag-chain-rule-en","tag-children-book-ja-en","tag-christmas-en","tag-cmos-en","tag-crowd-funding-en","tag-differentiation-en","tag-gradient-en","tag-musio-en"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t