Backpropagation

Backpropagation(反向传播)，就是告诉我们用gradient descent来train一个neural network的时候该怎么做，它只是求微分的一种方法，而不是一种新的算法

Gradient Descent

$\theta=w_1,w_2,...,b_1,b_2,...$ 里面可能会有将近million个参数

所以现在最大的困难是，如何有效地把这个近百万维的vector给计算出来，这就是Backpropagation要做的事情，所以Backpropagation并不是一个和gradient descent不同的training的方法，它就是gradient descent，它只是一个比较有效率的算法，让你在计算这个gradient的vector的时候更有效率

Chain Rule

Backpropagation里面并没有什么高深的数学，你唯一需要记得的就只有Chain Rule(链式法则)

$L(\theta)=\sum\limits_{n=1}^N l^n(\theta)$ ，它等于所有training data的loss之和

$x^n$ $y^n$ $\hat{y}^n$ 作cross entropy，这个 $y^n$ $\hat{y}^n$ $l^n(\theta)$ ，如果cross entropy比较大的话，说明output和target之间距离很远，这个network的parameter的loss是比较大的，反之则说明这组parameter是比较好的

$l^n(\theta)$ $L(\theta)$ $L(\theta)$ 对某一个参数w做偏微分，表达式如下：

\frac{\partial L(\theta)}{\partial w}=\sum\limits_{n=1}^N\frac{\partial l^n(\theta)}{\partial w}

$\frac{\partial l^n(\theta)}{\partial w}$ ，再将所有training data的cross entropy对参数w的偏微分累计求和，就可以把total loss对某一个参数w的偏微分给计算出来

$x_1,x_2$ $z=b+w_1 x_1+w_2 x_2$ $y_1,y_2$

$\frac{\partial l}{\partial w}$ $\frac{\partial l}{\partial w}=\frac{\partial z}{\partial w} \frac{\partial l}{\partial z}$ ，这两项分别去把它计算出来。前面这一项是比较简单的，后面这一项是比较复杂的

$\frac{\partial z}{\partial w}$ $\frac{\partial l}{\partial z}$ 的process，我们称之为Backward pass

Forward pass

$\frac{\partial z}{\partial w}$ $\frac{\partial z}{\partial w_1}=x_1 ,\ \frac{\partial z}{\partial w_2}=x_2$

它的规律是这样的： $\frac{\partial z}{\partial w}$ $\frac{\partial z}{\partial w}$ 值就是什么，因此只要计算出neural network里面每一个neuron的output就可以知道任意的z对w的偏微分

$w_1$ $x_1$ $x_1$ $w_2$ $x_2$ $x_2$
$\frac{\partial z}{\partial w}$ 的值就是前一层的z经过activation function之后输出的值(下图中的数据是假定activation function为sigmoid function得到的)

Backward pass

$\frac{\partial l}{\partial z}$ 这一项，它是比较复杂的，这里我们依旧假设activation function是sigmoid function

公式推导

$a=\sigma(z)$ $w_3$ $z'$ $w_4$ $z''$ ，后面还会发生很多很多其他事情，不过这里我们就只先考虑下一步会发生什么事情：

\frac{\partial l}{\partial z}=\frac{\partial a}{\partial z} \frac{\partial l}{\partial a}

$\frac{\partial a}{\partial z}$ $\frac{\partial l}{\partial a}$ $z'$ $z''$ $z'$ $z''$ $l$ ，所以通过chain rule可以得到

\frac{\partial l}{\partial a}=\frac{\partial z'}{\partial a} \frac{\partial l}{\partial z'}+\frac{\partial z''}{\partial a} \frac{\partial l}{\partial z''}

$\frac{\partial z'}{\partial a}=w_3$ $\frac{\partial z''}{\partial a}=w_4$ $\frac{\partial l}{\partial z'}$ $\frac{\partial l}{\partial z''}$ $\frac{\partial l}{\partial z'}$ $\frac{\partial l}{\partial z''}$ $\frac{\partial l}{\partial z}$ 给轻易地算出来

\frac{\partial l}{\partial z}=\frac{\partial a}{\partial z} \frac{\partial l}{\partial a}=\sigma'(z)[w_3 \frac{\partial l}{\partial z'}+w_4 \frac{\partial l}{\partial z''}]

另一个观点

这个式子还是蛮简单的，然后，我们可以从另外一个观点来看待这个式子

$\frac{\partial l}{\partial z'}$ $\frac{\partial l}{\partial z''}$ $\frac{\partial l}{\partial z'}$ $w_3$ $\frac{\partial l}{\partial z''}$ $w_4$ $\sigma'(z)$ $\frac{\partial l}{\partial z}$

这张图描述了一个新的“neuron”，它的含义跟图下方的表达式是一模一样的，作这张图的目的是为了方便理解

$\sigma'(z)$ 是一个constant常数，它并不是一个function，因为z其实在计算forward pass的时候就已经被决定好了，z是一个固定的值

$\sigma'(z)$ ，就得到了output，因此这个neuron被画成三角形，代表它跟我们之前看到的圆形的neuron的运作方式是不一样的，它是直接乘上一个constant(这里的三角形有点像电路里的运算放大器op-amp，它也是乘上一个constant)

两种情况

$\frac{\partial l}{\partial z'}$ $\frac{\partial l}{\partial z''}$ 这两项，假设有两个不同的case：

case 1：Output Layer

$z'$ $z''$ 后的这两个红色的neuron已经是output layer，它的output就已经是整个network的output了，这个时候计算就比较简单

\frac{\partial l}{\partial z'}=\frac{\partial y_1}{\partial z'} \frac{\partial l}{\partial y_1}

$\frac{\partial y_1}{\partial z'}$ $z'$ 的偏微分

$\frac{\partial l}{\partial y_1}$ $y_1$ $\frac{\partial l}{\partial y_1}$ 的值就不一样

$l$ $w_1$ $w_2$ $\frac{\partial l}{\partial w_1}$ $\frac{\partial l}{\partial w_2}$ 算出来了

Case 2：Not Output Layer

$z'$ $a'$ $a'$ $w_5$ $w_6$ $z_a$ $z_b$ ，如下图所示

$\frac{\partial l}{\partial z_a}$ $\frac{\partial l}{\partial z_b}$ $\frac{\partial l}{\partial z'}$ $\frac{\partial l}{\partial z_a}$ $w_5$ $\frac{\partial l}{\partial z_b}$ $w_6$ $\sigma'(z')$ $\frac{\partial l}{\partial z'}$

\frac{\partial l}{\partial z'}=\sigma'(z')[w_5 \frac{\partial l}{\partial z_a} + w_6 \frac{\partial l}{\partial z_b}]

$z'$ $z''$ $z$ $z_a$ $z_b$ $z'$ ，...... ，现在这个过程就可以反复进行下去，直到找到output layer，我们可以算出确切的值，然后再一层一层反推回去

你可能会想说，这个方法听起来挺让人崩溃的，每次要算一个微分的值，都要一路往后走，一直走到network的output，如果写成表达式的话，一层一层往后展开，感觉会是一个很可怕的式子，但是！实际上并不是这个样子做的

$\frac{\partial l}{\partial z}$ 开始算，你就会发现它的运算量跟原来的network的Feedforward path其实是一样的

$z_1$ $z_2$ $z_3$ $z_4$ $z_5$ $z_6$ $l$ $z$ $z_1$ $z_3$ $z_4$ $z_3$ $z_4$ $z_5$ $z_6$ $z_1$ $z_2$ 的偏微分开始算，那就没有效率

$z_5$ $z_6$ $\frac{\partial l}{\partial z_5}$ $\frac{\partial l}{\partial z_6}$ $\frac{\partial l}{\partial z_3}$ $\frac{\partial l}{\partial z_4}$ $\frac{\partial l}{\partial z_1}$ $\frac{\partial l}{\partial z_2}$ ，而这一整个过程，就可以转化为op-amp运算放大器的那张图

$\sigma'(z_1)$ $\sigma'(z_2)$ $\sigma'(z_3)$ $\sigma'(z_4)$ $\frac{\partial l}{\partial z_5}$ $\frac{\partial l}{\partial z_6}$ $\frac{\partial l}{\partial z_3}$ $\frac{\partial l}{\partial z_4}$ $\frac{\partial l}{\partial z_1}$ $\frac{\partial l}{\partial z_2}$ 这两个偏微分的值，这样就计算完了，这个步骤，就叫做Backward pass

$l$ $z$ $\frac{\partial l}{\partial z}$ $l$ $z$ $\frac{\partial l}{\partial z}$ $l$ $z$ $\frac{\partial l}{\partial z}$ 都给算出来

$\frac{\partial l}{\partial z}$ $\frac{\partial l}{\partial z}$ 都给计算一遍，会造成很多不必要的重复运算，如果写成code的形式，就相当于调用了很多次重复的函数；而如果是反向做Backward pass，实际上就是把这些调用函数的过程都变成调用“值”的过程，因此可以直接计算出结果，而不需要占用过多的堆栈空间

Summary

最后，我们来总结一下Backpropagation是怎么做的

Forward pass $\frac{\partial z}{\partial w}$

Backward pass $\frac{\partial l}{\partial z}$

$\frac{\partial z}{\partial w}$ $\frac{\partial l}{\partial z}$ $l$ $w$ $\frac{\partial l}{\partial w}$

\frac{\partial l}{\partial w} = \frac{\partial z}{\partial w}|_{forward\ pass} \cdot \frac{\partial l}{\partial z}|_{backward \ pass}