# 第二周：优化算法 (Optimization algorithms)

## 2.1 Mini-batch 梯度下降（Mini-batch gradient descent）

神经网络训练过程是同时对所有m个样本（称为batch）通过向量化计算方式进行的。如果m很大，训练速度会很慢，因为每次迭代都要对所有样本进进行求和运算和矩阵运算。这种梯度下降算法称为Batch Gradient Descent

解决：

把m个训练样本分成若干个子集，称为mini-batches，然后每次在单一子集上进行神经网络训练，这种梯度下降算法叫做Mini-batch Gradient Descent

假设总的训练样本个数$$m=5000000$$，其维度为$$(n\_x,m)$$。将其分成5000个子集，每个mini-batch含有1000个样本。将每个mini-batch记为$$X^{{t}}$$，其维度为$$(n\_x,1000)$$。相应的每个mini-batch的输出记为$$Y^{{t}}$$，其维度为(1,1000)，且$$t=1,2,\cdots,5000$$

* $$X^{(i)}$$**：第i个样本**
* $$Z^{\[l]}$$：**神经网络第**$$l$$**层网络的线性输出**
* $$X^{{t}},Y^{{t}}$$**：第t组mini-batch**

Mini-batches Gradient Descent是先将总的训练样本分成T个子集（mini-batches），然后对每个mini-batch进行神经网络训练，包括Forward Propagation，Compute Cost Function，Backward Propagation，循环至T个mini-batch都训练完毕

$$
for\ \ t=1,\cdots,T\ \ {
$$

$$
\ \ \ \ Forward\ Propagation
$$

$$
\ \ \ \ Compute\ Cost\ Function
$$

$$
\ \ \ \ Backward\ Propagation
$$

$$
\ \ \ \ W:=W-\alpha\cdot dW
$$

$$
\ \ \ \ b:=b-\alpha\cdot db
$$

$$
}
$$

经过T次循环之后，所有m个训练样本都进行了梯度下降计算。这个过程称之为经历了一个epoch。对于Batch Gradient Descent而言，一个epoch只进行一次梯度下降算法；而Mini-Batches Gradient Descent，一个epoch会进行T次梯度下降算法

对于Mini-Batches Gradient Descent，可以进行多次epoch训练。每次epoch，最好是将总体训练数据打乱、重新分成T组mini-batches，这样有利于训练出最佳的神经网络模型

## 2.2 理解 mini-batch 梯度下降法（Understanding mini-batch gradient descent）

Batch gradient descent和Mini-batch gradient descent的cost曲线：

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/5import.png)

对于一般的神经网络模型，使用Batch gradient descent，随着迭代次数增加，cost是不断减小的。而使用Mini-batch gradient descent，随着在不同的mini-batch上迭代训练，其cost不是单调下降，而是受类似noise的影响，出现振荡。但整体的趋势是下降的，最终也能得到较低的cost值

出现细微振荡的原因是不同的mini-batch之间是有差异的。可能第一个子集$$(X^{{1}},Y^{{1}})$$是好的子集，而第二个子集$$(X^{{2}},Y^{{2}})$$包含了一些噪声noise。出现细微振荡是正常的

如果mini-batch size=m，即为Batch gradient descent，只包含一个子集为$$(X^{{1}},Y^{{1}})=(X,Y)$$；

如果mini-batch size=1，即为Stachastic gradient descent，每个样本就是一个子集$$(X^{{1}},Y^{{1}})=(x^{(i)},y^{(i)})$$，共有m个子集

蓝色的线代表Batch gradient descent，紫色的线代表Stachastic gradient descent。Batch gradient descent会比较平稳地接近全局最小值，但因为使用了所有m个样本，每次前进的速度有些慢。Stachastic gradient descent每次前进速度很快，但路线曲折，有较大的振荡，最终会在最小值附近来回波动，难达到最小值。而且在数值处理上不能使用向量化的方法来提高运算速度

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/6import.png)

mini-batch size不能设置得太大（Batch gradient descent），也不能设置得太小（Stachastic gradient descent）。相当于结合了Batch gradient descent和Stachastic gradient descent各自的优点，既能使用向量化优化算法，又能较快速地找到最小值。mini-batch gradient descent的梯度下降曲线如下图绿色所示，每次前进速度较快，且振荡较小，基本能接近全局最小值。

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/7import.png)

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/14import.png)

* 总体样本数量m不太大时，例如$$m\leq2000$$，建议直接使用Batch gradient descent
* 总体样本数量m很大时，建议将样本分成许多mini-batches。推荐常用的mini-batch size为64,128,256,512。都是2的幂。原因是计算机存储数据一般是2的幂，这样设置可以提高运算速度
*  mini-batch 中确保 $$X{{t}}$$ 和$$Y{{t}}$$要符合 CPU/GPU 内存，取决于应用方向以及训练集的大小。如果处理的 mini-batch 和 CPU/GPU 内存不相符，不管用什么方法处理数据，算法的表现都急转直下变得惨不忍睹

### 从训练集（X，Y）中构建小批量

* 随机洗牌（**Shuffle**）：创建训练集（X，Y）的混洗版本，X和Y的每一列代表一个训练示例。随机混洗是在X和Y之间同步完成的。这样在混洗之后第$$i$$列的X对应的例子就是Y第$$i$$列中的标签。混洗步骤可确保将示例随机分成不同的小批次

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/16import.png)

* 分区（**Partition**）：将混洗（X，Y）分区为小批量mini\_batch\_size（此处为64）。训练示例的数量并非总是可以被mini\_batch\_size整除。最后一个小批量可能会更小

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/17import.png)

## 2.3 指数加权平均数（Exponentially weighted averages）

半年内伦敦市的气温变化：

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/11import.png)

> 温度数据有noise，抖动较大

如果希望看到半年内气温的整体变化趋势，可以通过移动平均（moving average）的方法来对每天气温进行平滑处理

设$$V\_0=0$$，当成第0天的气温值

第一天的气温与第0天的气温有关：

$$
V\_1=0.9V\_0+0.1\theta\_1
$$

第二天的气温与第一天的气温有关：

$$
\begin{aligned}V\_2
\=&0.9V\_1+0.1\theta\_2\\
\=&0.9(0.9V\_0+0.1\theta\_1)+0.1\theta\_2\\
\=&0.9^2V\_0+0.9\cdot0.1\theta\_1+0.1\theta\_2
\end{aligned}
$$

第三天的气温与第二天的气温有关：

$$
\begin{aligned}V\_3
\=&0.9V\_2+0.1\theta\_3\\
\=&0.9(0.9^2V\_0+0.9\cdot0.1\theta\_1+0.1\theta\_2)+0.1\theta\_3\\
\=&0.9^3V\_0+0.9^2\cdot 0.1\theta\_1+0.9\cdot 0.1\theta\_2+0.1\theta\_3
\end{aligned}
$$

第$$t$$天与第$$t-1$$天的气温迭代关系为：

$$
\begin{aligned}V\_t
\=&0.9V\_{t-1}+0.1\theta\_t\\
\=&0.9^tV\_0+0.9^{t-1}\cdot0.1\theta\_1+0.9^{t-2}\cdot 0.1\theta\_2+\cdots+0.9\cdot0.1\theta\_{t-1}+0.1\theta\_t
\end{aligned}
$$

经过移动平均处理得到的气温如下图红色曲线所示：

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/12import.png)\
这种滑动平均算法称为指数加权平均（exponentially weighted average）。一般形式为：

$$
V\_t=\beta V\_{t-1}+(1-\beta)\theta\_t
$$

$$\beta$$值决定了指数加权平均的天数，近似表示为：

$$
\frac{1}{1-\beta}
$$

当$$\beta=0.9$$，则$$\frac{1}{1-\beta}=10$$，表示将前10天进行指数加权平均。当$$\beta=0.98$$，则$$\frac{1}{1-\beta}=50$$，表示将前50天进行指数加权平均。$$\beta$$值越大，则指数加权平均的天数越多，平均后的趋势线就越平缓，但是同时也会向右平移

绿色曲线和黄色曲线分别表示了$$\beta=0.98$$和$$\beta=0.5$$时，指数加权平均的结果

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/13import.png)

## 2.4 理解指数加权平均数（Understanding exponentially weighted averages ）

指数加权平均公式的一般形式：

$$
\begin{aligned}V\_t
\=&\beta V\_{t-1}+(1-\beta)\theta\_t\\
\=&(1-\beta)\theta\_t+(1-\beta)\cdot\beta\cdot\theta\_{t-1}+(1-\beta)\cdot \beta^2\cdot\theta\_{t-2}+\cdots
+(1-\beta)\cdot \beta^{t-1}\cdot \theta\_1+\beta^t\cdot V\_0
\end{aligned}
$$

$$\theta,\theta{t-1},\theta\_{t-2},\cdots,\theta\_1$$是原始数据值，$$(1-\beta),(1-\beta)\beta,(1-\beta)\beta^2,\cdots,(1-\beta)\beta^{t-1}$$是类似指数曲线，从右向左，呈指数下降的。$$V\_t$$ 的值是这两个子式的点乘，将原始数据值与衰减指数点乘，相当于做了指数衰减，离得越近，影响越大，离得越远，影响越小，衰减越厉害

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/11.bmp)

为了减少内存的使用，使用这样的语句来实现指数加权平均算法：

$$
V\_{\theta}=0
$$

$$
Repeat\ {
$$

$$
\ \ \ \ Get\ next\ \theta\_t
$$

$$
\ \ \ \ V\_{\theta}:=\beta V\_{\theta}+(1-\beta)\theta\_t
$$

$$
}
$$

## 2.5 指 数 加 权 平 均 的 偏 差 修 正 （ Bias correction inexponentially weighted averages ）

当$$\beta=0.98$$时，指数加权平均结果如绿色曲线。但实际上真实曲线如紫色曲线

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/212Eimport.png)

紫色曲线与绿色曲线的区别是，紫色曲线开始的时候相对较低一些。因为开始时设置$$V\_0=0$$，所以初始值会相对小一些，直到后面受前面的影响渐渐变小，趋于正常

修正这种问题的方法是进行**偏移校正（bias correction）**，即在每次计算完$$V\_t$$后，对$$V\_t$$进行下式处理：

$$
\frac{V\_t}{1-\beta^t}
$$

刚开始的时候，$$t$$比较小，$$(1-\beta^t)<1$$,$$V\_t$$被修正得更大一些，效果是把紫色曲线开始部分向上提升一些，与绿色曲线接近重合。随着$$t$$增大，$$(1-\beta^t)\approx1$$，$$V\_t$$基本不变，紫色曲线与绿色曲线依然重合。实现了简单的偏移校正，得到希望的绿色曲线

机器学习中，偏移校正并不是必须的。因为，在迭代一次次数后（$$t$$较大），$$V\_t$$受初始值影响微乎其微，紫色曲线与绿色曲线基本重合。一般可以忽略初始迭代过程，等到一定迭代之后再取值就不需要进行偏移校正

## 2.6 动量梯度下降法（Gradient descent with Momentum ）

动量梯度下降算法速度比传统的梯度下降算法快很多。做法是在每次训练时，对梯度进行指数加权平均处理，然后用得到的梯度值更新权重$$W$$和常数项$$b$$

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/7.bmp)

原始的梯度下降算法如上图蓝色折线所示。在梯度下降过程中，梯度下降的振荡较大，尤其对于$$W$$、$$b$$之间数值范围差别较大的情况。此时每一点处的梯度只与当前方向有关，产生类似折线的效果，前进缓慢。而如果对梯度进行指数加权平均，使当前梯度不仅与当前方向有关，还与之前的方向有关，在纵轴方向，\
平均过程中，正负数相互抵消，所以平均值接近于零。但在横轴方向，所\
有的微分都指向横轴方向，因此横轴方向的平均值仍然较大，用算法几次迭代后，最终纵轴方向的摆动变小了，横轴方向运动更快，因此算法走了一\
条更加直接的路径，在抵达最小值的路上减少了摆动，这样处理让梯度前进方向更加平滑，减少振荡，能够更快地到达最小值处

权重$$W$$和常数项$$b$$的指数加权平均表达式如下：

$$
V\_{dW}=\beta\cdot V\_{dW}+(1-\beta)\cdot dW
$$

$$
V\_{db}=\beta\cdot V\_{db}+(1-\beta)\cdot db
$$

动量的角度来看，以权重$$W$$为例，$$V\_{dW}$$可以理解成速度$$V$$，$$dW$$可以看成是加速度$$a$$。指数加权平均实际上是计算当前的速度，当前速度由之前的速度和现在的加速度共同影响。而$$\beta<1$$又能限制速度$$V\_{dW}$$过大。即当前的速度是渐变的，而不是瞬变的，是动量的过程。保证了梯度下降的平稳性和准确性，减少振荡，较快地达到最小值处

动量梯度下降算法的过程如下：

$$On\ iteration\ t:$$

$$
\ \ \ \ Compute\ dW,\ db\ on\ the\ current\ mini-batch
$$

$$
\ \ \ \ V\_{dW}=\beta V\_{dW}+(1-\beta)dW
$$

$$
\ \ \ \ V\_{db}=\beta V\_{db}+(1-\beta)db
$$

$$
\ \ \ \ W=W-\alpha V\_{dW},\ b=b-\alpha V\_{db}
$$

初始时，令$$V\_{dW}=0,V\_{db}=0$$。一般设置$$\beta=0.9$$，即指数加权平均前10次的数据，实际应用效果较好。

偏移校正可以不使用。因为经过10次迭代后，随着滑动平均的过程，偏移情况会逐渐消失

## 2.7 RMSprop(root mean square prop)

RMSprop是另外一种优化梯度下降速度的算法。每次迭代训练过程中，其权重$$W$$和常数项$$b$$的更新表达式为：

$$
S\_{dW}=\beta S\_{dW}+(1-\beta)dW^2
$$

$$
S\_{db}=\beta S\_{db}+(1-\beta)db^2
$$

$$
W:=W-\alpha \frac{dW}{\sqrt{S\_{dW}}},\ b:=b-\alpha \frac{db}{\sqrt{S\_{db}}}
$$

### RMSprop算法的原理解释

令水平方向为$$W$$的方向，垂直方向为$$b$$的方向

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/8.bmp)

梯度下降（蓝色折线）在垂直方向（$$b$$）上振荡较大，在水平方向（$$W$$）上振荡较小，表示在$$b$$方向上梯度较大，即$$db$$较大，而在$$W$$方向上梯度较小，即$$dW$$较小。因此，上述表达式中$$S\_{db}$$较大，而$$S\_{dW}$$较小。在更新$$W$$和$$b$$的表达式中，变化值$$\frac{dW}{\sqrt{S\_{dW}}}$$较大，而$$\frac{db}{\sqrt{S\_{db}}}$$较小。也就使得$$W$$变化得多一些，$$b$$变化得少一些。即加快了$$W$$方向的速度，减小了$$b$$方向的速度，减小振荡，实现快速梯度下降算法，其梯度下降过程如绿色折线所示。总的来说，就是如果哪个方向振荡大，就减小该方向的更新速度，从而减小振荡

为了避免RMSprop算法中分母为零，通常可以在分母增加一个极小的常数$$\varepsilon$$：

$$
W:=W-\alpha \frac{dW}{\sqrt{S\_{dW}}+\varepsilon},\ b:=b-\alpha \frac{db}{\sqrt{S\_{db}}+\varepsilon}
$$

$$\varepsilon=10^{-8}$$，或者其它较小值

## 2.8 Adam 优化算法(Adam optimization algorithm)

Adam（Adaptive Moment Estimation）算法结合了动量梯度下降算法和RMSprop算法。其算法流程为：

$$V{dW}=0, S{dW}, V{db}=0, S{db}=0$$

$$On iteration t:$$

$$
\ \ \ \ Cimpute\ dW,\ db
$$

$$
\ \ \ \ V\_{dW}=\beta\_1V\_{dW}+(1-\beta\_1)dW,\ V\_{db}=\beta\_1V\_{db}+(1-\beta\_1)db
$$

$$
\ \ \ \ S\_{dW}=\beta\_2S\_{dW}+(1-\beta\_2)dW^2,\ S\_{db}=\beta\_2S\_{db}+(1-\beta\_2)db^2
$$

$$
\ \ \ \ V\_{dW}^{corrected}=\frac{V\_{dW}}{1-\beta\_1^t},\ V\_{db}^{corrected}=\frac{V\_{db}}{1-\beta\_1^t}
$$

$$
\ \ \ \ S\_{dW}^{corrected}=\frac{S\_{dW}}{1-\beta\_2^t},\ S\_{db}^{corrected}=\frac{S\_{db}}{1-\beta\_2^t}
$$

$$
\ \ \ \ W:=W-\alpha\frac{V\_{dW}^{corrected}}{\sqrt{S\_{dW}^{corrected}}+\varepsilon},\ b:=b-\alpha\frac{V\_{db}^{corrected}}{\sqrt{S\_{db}^{corrected}}+\varepsilon}
$$

Adam算法包含了几个超参数，分别是：$$\alpha,\beta\_1,\beta\_2,\varepsilon$$,$$\beta\_1$$通常设置为0.9，$$\beta\_2$$通常设置为0.999，$$\varepsilon$$通常设置为$$10^{-8}$$。一般只需要对$$\beta\_1$$和$$\beta\_2$$进行调试

Adam算法结合了动量梯度下降和RMSprop各自的优点，使得神经网络训练速度大大提高

## 2.9 学习率衰减(Learning rate decay)

减小学习因子$$\alpha$$也能有效提高神经网络训练速度，这种方法被称为learning rate decay, Learning rate decay就是随着迭代次数增加，学习因子$$\alpha$$逐渐减小

下图中，蓝色折线表示使用恒定的学习因子$$\alpha$$，由于每次训练$$\alpha$$相同，步进长度不变，在接近最优值处的振荡也大，在最优值附近较大范围内振荡，与最优值距离就比较远。绿色折线表示使用不断减小的$$\alpha$$，随着训练次数增加，$$\alpha$$逐渐减小，步进长度减小，使得能够在最优值处较小范围内微弱振荡，不断逼近最优值。相比较恒定的$$\alpha$$来说，learning rate decay更接近最优值

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/10import.png)

Learning rate decay中对$$\alpha$$的公式：

$$
\alpha=\frac{1}{1+decay\_rate\*epoch}\alpha\_0
$$

deacy\_rate是参数（可调），epoch是迭代次数。随着epoch增加，$$\alpha$$会不断变小

其它计算公式：

$$
\alpha=0.95^{epoch}\cdot \alpha\_0
$$

$$
\alpha=\frac{k}{\sqrt{epoch}}\cdot \alpha\_0\ \ \ \ or\ \ \ \ \frac{k}{\sqrt{t}}\cdot \alpha\_0
$$

$$k$$为可调参数，$$t$$为mini-bach number

还可以设置$$\alpha$$为关于$$t$$的离散值，随着$$t$$增加，$$\alpha$$呈阶梯式减小。也可以根据训练情况灵活调整当前的$$\alpha$$值，但会比较耗时间

## 2.10 局部最优的问题(The problem of local optima)

以前对局部最优解的理解是形如碗状的凹槽，如下图左边所示。但是在神经网络中，local optima的概念发生了变化。大部分梯度为零的“最优点”并不是这些凹槽处，而是形如右边所示的马鞍状，称为saddle point（鞍点）。即梯度为零并不能保证都是convex（极小值），也有可能是concave（极大值）。特别是在神经网络中参数很多的情况下，所有参数梯度为零的点很可能都是右边所示的马鞍状的saddle point，而不是左边那样的local optimum

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/8import.png)

类似马鞍状的plateaus（平稳端）会降低神经网络学习速度。Plateaus是梯度接近于零的平缓区域，在plateaus上梯度很小，前进缓慢，到达saddle point需要很长时间。到达saddle point后，由于随机扰动，梯度一般能够沿着图中绿色箭头，离开saddle point，继续前进，只是在plateaus上花费了太多时间

![](https://baozou.gitbooks.io/neural-networks-and-deep-learning/content/assets/9import.png)

local optima的两点总结：

* **只要选择合理的强大的神经网络，一般不太可能陷入local optima**
* **Plateaus可能会使梯度下降变慢，降低学习速度**

动量梯度下降，RMSprop，Adam算法都能有效解决plateaus下降过慢的问题，大大提高神经网络的学习速度