<commit_before>layout:     post
title:      Back-propagation: An introduction
date:       2016-12-21 21:00:00
author:     <NAME> and <NAME>
visible:    false
---

Given the sheer number of backpropagation tutorials on the internet, is there really need for another? One of us (Sanjeev) recently taught backpropagation in [undergrad AI](https://www.cs.princeton.edu/courses/archive/fall16/cos402/) and couldn't find any account he was happy with. So here's our exposition, together with some history and context, as well as a few advanced notions at the end. This article assumes the reader knows the definitions of gradients and neural networks.

##What is backpropagation? 

It is the basic algorithm in training neural nets, apparently independently rediscovered several times in the 1970-80’s (e.g., see Werbos’ [Ph.D. thesis](https://www.researchgate.net/publication/35657389_Beyond_regression_new_tools_for_prediction_and_analysis_in_the_behavioral_sciences) and [book](http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471598976.html), and [Rumelhart et al.](http://www.nature.com/nature/journal/v323/n6088/abs/323533a0.html)). Some related ideas existed in control theory in the 1960s. 

Backpropagation gives a fast way to compute the sensitivity of the output of a neural network to all of its parameters while keeping the inputs of the network fixed: specifically it computes all partial derivatives ${\partial f}/{\partial w_i}$ where $f$ is the output and $w_i$ is the $i$th parameter. (Here *parameters* can be edge weights or biases associated with nodes or edges of the network, and the precise details of the node computations ---e.g., the precise form of nonlinearity like Sigmoid or RELU--- are unimportant.)  Doing so gives the *gradient* $\nabla f$ of $f$ with respect to its  network parameters, which allows a *gradient descent* step in the training: change all parameters simultaneously to move the vector of parameters  a small amount in the direction $-\nabla f$. 

Note that backpropagation computes the gradient exactly, but properly training neural nets needs many more tricks than just backpropagation. Understanding backpropagation is useful for understanding the advanced tricks.

The importance of backpropagation derives from its efficiency. Assuming node operations take unit time, the running time is *linear*, specifically, $O(\text{Network Size}) = O(V + E)$, where $V$ is the number of nodes in the network and $E$ is the number of edges.  The only technical ingredient  is chain rule from calculus, but applying it naively would have resulted in quadratic running time---which would be hugely inefficient  for networks with millions or even thousands of parameters.

Backpropagation can be efficiently implemented using highly parallel vector operations available  in today’s [GPUs (Graphical Processing Units)](https://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units), which play an important role in the the recent neural nets revolution. 

**Side Note:** Expert readers will recognize that in the standard accounts of neural net training,
the actual quantity of interest is the gradient of the *training loss*, which happens to be a  simple function of the network output. But the above phrasing is fully general since  one can simply add a new output node to the network that computes the training loss from the old output. Then the quantity of interest is indeed the gradient of this new output with respect to network parameters. 


##Problem Setup 

Backpropagation applies only to acyclic networks with directed edges. (Later we briefly sketch its use on networks with cycles.) 

Without loss of generality, acyclic networks can be visualized as being structured in numbered layers,  with nodes in the $t+1$th layer getting all their inputs from the outputs of nodes in layers $t$ and earlier. We use $f \in \mathbb{R}$ to denote the output of the network. In all our figures, the input of the network is at the bottom and the output on the top.

We start with a simple claim that reduces the problem of computing the gradient to the problem of computing partial derivatives with respect to the nodes: 

>**Claim 1:** To compute the desired gradient with respect to the parameters, it suffices to compute $\partial f/\partial u$ for every node $u$.
<commit_msg>Update 2016-12-21-backprop.md<commit_after>layout:     post
title:      Back-propagation: An introduction
date:       2016-12-21 21:00:00
author:     <NAME> and <NAME>
visible:    True
---

Given the sheer number of backpropagation tutorials on the internet, is there really need for another? One of us (Sanjeev) recently taught backpropagation in [undergrad AI](https://www.cs.princeton.edu/courses/archive/fall16/cos402/) and couldn't find any account he was happy with. So here's our exposition, together with some history and context, as well as a few advanced notions at the end. This article assumes the reader knows the definitions of gradients and neural networks.

##What is backpropagation? 

It is the basic algorithm in training neural nets, apparently independently rediscovered several times in the 1970-80’s (e.g., see Werbos’ [Ph.D. thesis](https://www.researchgate.net/publication/35657389_Beyond_regression_new_tools_for_prediction_and_analysis_in_the_behavioral_sciences) and [book](http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471598976.html), and [Rumelhart et al.](http://www.nature.com/nature/journal/v323/n6088/abs/323533a0.html)). Some related ideas existed in control theory in the 1960s. 

Backpropagation gives a fast way to compute the sensitivity of the output of a neural network to all of its parameters while keeping the inputs of the network fixed: specifically it computes all partial derivatives ${\partial f}/{\partial w_i}$ where $f$ is the output and $w_i$ is the $i$th parameter. (Here *parameters* can be edge weights or biases associated with nodes or edges of the network, and the precise details of the node computations ---e.g., the precise form of nonlinearity like Sigmoid or RELU--- are unimportant.)  Doing so gives the *gradient* $\nabla f$ of $f$ with respect to its  network parameters, which allows a *gradient descent* step in the training: change all parameters simultaneously to move the vector of parameters  a small amount in the direction $-\nabla f$. 

Note that backpropagation computes the gradient exactly, but properly training neural nets needs many more tricks than just backpropagation. Understanding backpropagation is useful for understanding the advanced tricks.

The importance of backpropagation derives from its efficiency. Assuming node operations take unit time, the running time is *linear*, specifically, $O(\text{Network Size}) = O(V + E)$, where $V$ is the number of nodes in the network and $E$ is the number of edges.  The only technical ingredient  is chain rule from calculus, but applying it naively would have resulted in quadratic running time---which would be hugely inefficient  for networks with millions or even thousands of parameters.

Backpropagation can be efficiently implemented using highly parallel vector operations available  in today’s [GPUs (Graphical Processing Units)](https://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units), which play an important role in the the recent neural nets revolution. 

**Side Note:** Expert readers will recognize that in the standard accounts of neural net training,
the actual quantity of interest is the gradient of the *training loss*, which happens to be a  simple function of the network output. But the above phrasing is fully general since  one can simply add a new output node to the network that computes the training loss from the old output. Then the quantity of interest is indeed the gradient of this new output with respect to network parameters. 


##Problem Setup 

Backpropagation applies only to acyclic networks with directed edges. (Later we briefly sketch its use on networks with cycles.) 

Without loss of generality, acyclic networks can be visualized as being structured in numbered layers,  with nodes in the $t+1$th layer getting all their inputs from the outputs of nodes in layers $t$ and earlier. We use $f \in \mathbb{R}$ to denote the output of the network. In all our figures, the input of the network is at the bottom and the output on the top.

We start with a simple claim that reduces the problem of computing the gradient to the problem of computing partial derivatives with respect to the nodes: 

>**Claim 1:** To compute the desired gradient with respect to the parameters, it suffices to compute $\partial f/\partial u$ for every node $u$.

{'fraction_non_alphanumeric': 0.05866789370758081, 'fraction_numerical': 0.015414701483952605, 'mean_word_length': 4.697247706422019, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 6, 'lorem ipsum': 0, 'www.': 8, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3840258', 'n_tokens_mistral': 2263, 'n_tokens_neox': 2056, 'n_words': 1205}