反向传播算法-入门

知识准备

1. sigmoid的神经元是这样的
   $z=b+\sum\limits_ix_iw_i$
   $y=\dfrac{1}{1+e^{-z}}$

2. sigmoid神经元的特点
   $\dfrac{dy}{dz}= y(1-y)$

一些定义

此处的例子是一种特殊的神经网络：三层，最后一层是线性层，隐含层是sigmoid，cost Function是平方和。
先以这种特殊的神经网络为例，说明反向传播算法。然后推广到更一般的的表达式

变量定义：

• n表示第n个case/sample
• C表示误差，是一个数字
• 3层神经网络，M是输入层，I表示中间层，J表示输出层
• 对于每个神经元：
  • $v$表示神经元的输出
  • $u$表示神经元的输入
  • $\sigma()$表示神经元的激活函数（所以$v=\sigma(u)$）
  • 上标表示所在的层数，下标表示所在的个数，例如$v_i^l$表示$l$层第$i$个神经元的输出

为何计算

学习过程$w_{ij}(n+1)=w_{ij}(n)+\Delta w_{ij}(n)$
其中$\Delta w_{ij}(n)=-\eta\dfrac{\partial e(n)}{\partial w_{ij}}$
所以，问题在于如何求解$\dfrac{\partial e(n)}{\partial w_{ij}}$
反向传播算法的目的就在于求解上面这个偏微分

对于第n个case,J层情况

1. 用链式法则拆分

$\dfrac{\partial e(n)}{\partial w_{ij}} =\dfrac{\partial e}{\partial e_j} \dfrac{\partial e_j}{\partial v_j} \dfrac{\partial v_j}{\partial u_j} \dfrac{\partial u_j}{\partial w_{ij}}$

• 关于第一项
  $e=0.5\sum e_j^2$
  于是$\dfrac{\partial e}{\partial e_j}=e_j=t_j-v_j^J$
• 关于第二项
  $e_j=t_j-v_j^J$
  于是$\dfrac{\partial e_j}{\partial v_j}=-1$
• 关于第三项
  $v_j^J=\sigma(u_j^J)$
  于是$\dfrac{\partial v_j}{\partial u_j}=\sigma’(u_j^J)$
• 关于第四项
  $u_j^J=\sum\limits_{i\in I}w_{ij}v_i^I $
  于是$\dfrac{\partial u_j}{\partial w_{ij}}=v_i^I$

2. 学习

定义梯度为：
$\delta_j^J= \dfrac{\partial e}{\partial e_j} \dfrac{\partial e_j}{\partial v_j} \dfrac{\partial v_j}{\partial u_j}$

于是:
$\dfrac{\partial e}{\partial w_{ij}} =\delta_j^Jv^I_i$
所以：
$\Delta w_{ij}(n)=-\eta \delta_j^J v_i^I$

对于第n个case，I层学习

(I层之前为M层) $\Delta w_{mi}^I= - \eta \dfrac{\partial e}{\partial w_{mi}}$

用链式法则拆分
$\dfrac{\partial e}{\partial w_{mi}} =\dfrac{\partial e}{\partial v_i^I} \dfrac{\partial v_i^I}{\partial u_i^I} \dfrac{\partial u_i^I}{\partial w_{mi}}$

• 其中，前两项为梯度： $\delta_i^I= \dfrac{\partial e}{\partial v_i} \dfrac{\partial v_i}{\partial u_i}$
  • 第一项为
    $\dfrac{\partial e}{\partial v_i^I}=\sum\limits_{j\in J}\delta_j^Jw_{ij}$
  • 所以$\delta_i^I= \sum\limits_{j\in J}\delta_j^Jw_{ij} \dfrac{\partial v_i}{\partial u_i}$

用梯度形式改写迭代式
$\Delta w_{mi}^I=-\eta \delta_i^I v_m^M$

反向传播算法-梯度表示

上面的推导中，思路是以$\dfrac{\partial C}{\partial w}$为核心，试图寻找权重$w$的最佳改进方向。
在推导中发现，如果以梯度$\delta$为核心，算法看起来会更优美，并且更有一般性（本质上还是等价的）
定义梯度$\delta_j^l=\dfrac{\partial C}{\partial u_j^l}$

BP1

输出层$\delta^L=\nabla_vC \odot \sigma’(u^L)$
上式是向量形式表达的，解释如下：

• $\odot$是向量对应项乘积(标量积)，称为 Hadamard乘积，或者 Schur 乘积
• 标量形式：$\delta_j^L=\dfrac{\partial C}{\partial v_j}\dfrac{\partial v_j^L}{\partial u_j^L} ,\forall j$

BP2

使用$l+1$层的$\delta^{l+1}$来表示$\delta^l$
$\delta^l=((w^{l+1})^T\delta^{l+1}))\odot \sigma’(u^l)$

• 标量形式：$\delta_j^l=\dfrac{\partial C}{\partial u_j^l}=\sum_k\dfrac{\partial C}{\partial u_j^{l+1}}\dfrac{\partial u_k^{l+1}}{\partial v_j^l}\dfrac{\partial v_j^l}{\partial u_j^l}=\sum_k\delta_k^{l+1}w_{jk}^l \sigma’(u_j^l)$

BP3

标量形式$\dfrac{\partial C}{\partial b_j^l}=\delta_j^l$
向量形式$\dfrac{\partial C}{\partial b^l}=\delta^l$

BP4

标量形式$\dfrac{\partial C}{\partial w_{jk}^l}=v^{l-1}_k\delta_j^l$
向量形式$\dfrac{\partial C}{\partial w}=v^{l-1}\delta^{l}$(其实是矩阵形式)

扩展

反向传播算法的核心目的是为了求$\dfrac{\partial C}{\partial w}$,
有一个看起来更简单的方案$\dfrac{\partial C}{\partial w_i}\approx \dfrac{C(w+\varepsilon e_i)-C(w)}{\varepsilon}$
如果有n个w，需要计算n+1次C，计算量远大于反向传播算法。

反向传播算法-矢量化运算

中括号表示第几层，圆括号表示第几个神经元，尖括号表示第几次迭代/第几组数据

forward propagation

• input layer
  $A^{[0]}=X$ （$X_{n^{[0]}\times m}$，$m$ 是样例个数）
• hidden layer（for loop）
  $Z^{[l]}=W^{[l]} A^{[l-1]}+b^{[l]}$（$W_{n^{[l]}\times n^{[l-1]}}, A_{n^{[l]}\times m},b_{n^{l}\times 1}$，公式里面的加号$+$进行了一次 broadcasting）
  $A^{[l]}=g^{[l]}(Z^{[l]})$
• output layer
  $Y=A^{[L]}=g^{[L]}(Z^{[L]})$
  $L(\hat Y,Y)=(Y\log(\hat Y)+(1-Y)\log(1-\hat Y)$（实际上还应当在外面套一个$-1/m*\sum$）

back propagation

以下维度应当一模一样： $(dZ,Z),(dA,A),(dW,W),(db,b)$
（这个符号来自吴恩达的课程，这里的d不是微分算子，应当理解为“梯度”，精确地说，是$”dZ”=\dfrac{\partial L}{\partial Z}$）

$dZ^{[l]}=dA^{[l]}\odot g’(Z^{[l]})$
$dA^{[l-1]}=\dfrac{\partial \mathcal L}{\partial A^{[l-1]}}=W^{[l]T}dZ^{[l]}$

合并起来，就是（以$dA$为核心，进行迭代）

• output layer（以 sigmoid为例） $dA^{[L]}=-np.sum(Y/A+(1-Y)/(1-A))$ （其中，$Y_{1\times m},A_{1 \times m}$, 除法是标量除）
• for loop
  $dA^{[l-1]}=\dfrac{\partial \mathcal L}{\partial A^{[l-1]}}=W^{[l]T} dA^{[l]}\odot g’(Z^{[l]})$
  • 在每一层：
    $dW^{[l]}=\dfrac{\partial \mathcal L}{\partial W^{[l]}}=1/m * dZ^{[l]}A^{[l-1]T}$
    $db^{[l]}=\dfrac{\partial \mathcal L}{\partial b^{[l]}}=1/m * np.sum(dZ^{[l]},axis=1,keepdims=True)$

或者以$dZ$为核心，进行迭代：

• output layer
  $dZ^{[L]}=A^{[L]}-Y$
• for loop
  $dZ^{[l]}=W^{[l+1]T}dZ^{[l+1]}\odot g’(Z^{[l]})$
  • 在每一层：
    $dW^{[l]}=\dfrac{\partial \mathcal L}{\partial W^{[l]}}=1/m * dZ^{[l]}A^{[l-1]T}$
    $db^{[l]}=\dfrac{\partial \mathcal L}{\partial b^{[l]}}=1/m * np.sum(dZ^{[l]},axis=1,keepdims=True)$

优化算法

前面解释了“梯度”这一重要步骤，我们的目标还是拿梯度去优化参数。

mini-batch

batch：每次迭代放入全量数据
mini-batch：每次迭代放入一组数据

记号：
对于第t个mini-batch，这么记$X^{{ t }},Y^{{ t }}$
（我们用$x^{(i)}$表示第i个sample，用$Z^{[l]}$表示第l个layer）
“1 epoch”：pass through training set

Why

如果 mini-batch size=1，叫做 stochastic gradient descent. 缺点是不能矢量化运算，实际训练速度也慢。
mini-batch 设定为合理值，既可以享受矢量化计算的速度，而且每次更新参数也不用很久。

choosing mini-batch size：

• if small training set，use batch gradient decent
• if big training set，use 64/128/256/512/1024. Make sure mini-batch fit in cpu/gpu memory

Exponentially weighted averages

exponentially weighted moving averages:
原序列是$\theta_t$,新序列是$v_t=\beta v_{t-1}+(1-\beta)\theta_t, (v_0=0)$
分析上面的序列，发现：

1. $v$反映的是过去$1/(1-\beta)$期内的平均。
2. 每期只需要1份内存进行存储，而不是$1/(1-\beta)$份
3. 因为$v_0=0$导致的不准，可以用$\dfrac{v_t}{1-\beta^t}$进行调整

应用：gradient descent with momentum
compute dw,db on current mini-batch
$v_{dw}=\beta v_{dw}+(1-\beta)dw$
$v_{db}=\beta v_{db}+(1-\beta)db$

$w-=\alpha v_{dw},b-=\alpha v_{db}$

超参数$\beta$：0.8~0.999都可以，默认0.9

RMSprop

$S_{dw}=\beta S_{dw}+(1-\beta)dw\odot dw$
$S_{db}=\beta S_{db}+(1-\beta)db\odot db$

$w:=w-\alpha\dfrac{dw}{\sqrt{S_{dw}}}$
$b:=b-\alpha\dfrac{db}{\sqrt{S_{db}}}$

效果：梯度很大的变量，变化稍微一点。梯度很小的变量，变化稍微大一点。如此，你可以使用更大的 learning rate

Adam optimization algorithm

Adam stands for Adaptive Moment Estimation
During the history of deep learning, many optimization algorithms works well in a few problems, but not general.
Adam is one of rare algorithms that has really stood up.

Adam = Momentum + RMSProp

• momentum $v_{dw}=\beta_1 v_{dw}+(1-\beta_1)dw, v_{db}=\beta_1 v_{db}+(1-\beta_1)db$
• RMSprop $S_{dw}=\beta_2 S_{dw}+(1-\beta_2)dw\odot dw, S_{db}=\beta_2 S_{db}+(1-\beta_2)db$
• 解决初始值为0引发的问题：$v$

完整版如下：
\(\begin{cases} v_{dW^{[l]}} = \beta_1 v_{dW^{[l]}} + (1 - \beta_1) \frac{\partial \mathcal{J} }{ \partial W^{[l]} } \\ v^{corrected}_{dW^{[l]}} = \frac{v_{dW^{[l]}}}{1 - (\beta_1)^t} \\ s_{dW^{[l]}} = \beta_2 s_{dW^{[l]}} + (1 - \beta_2) (\frac{\partial \mathcal{J} }{\partial W^{[l]} })^2 \\ s^{corrected}_{dW^{[l]}} = \frac{s_{dW^{[l]}}}{1 - (\beta_2)^t} \\ W^{[l]} = W^{[l]} - \alpha \frac{v^{corrected}_{dW^{[l]}}}{\sqrt{s^{corrected}_{dW^{[l]}}} + \varepsilon} \end{cases}\)

参数设置

• $alpha$ needs to be tune
• $\beta_1$ 0.9
• $\beta_2$ 0.999
• $\varepsilon:10^{-8}$

Learning rate decay

$\alpha=\dfrac{1}{DecayRate*EpochNum}\alpha_0$

还有一些其它形式：指数、阶梯、幂函数等，甚至还可以手动。

The problem of local optima

虽然自然的理解是，陷入梯度为0的点就是陷入局部最优点，但更多的情况是（尤其是维度很高的情况下，如果陷入无法优化的点，这个点是局部最优点的概率极小）：

• 陷入到 saddle point
• plateaus

（自己画个图看看就懂了）

参考资料

• http://michaelnielsen.org/
• deeplearning.ai