Deep Learning (3) - Optimization Algorithms
Posted on
Edited on
Batch. vs. Mini-Batch
机器学习算法通常会有大量的training sample需要处理，这个数字可能是百万量级，甚至更高。这会导致矩阵迭代的时候，计算时间过长。当sample数达到一定数量的时候，通常会采用将整个训练集，分成若干小集合，即mini-batch，采用迭代的方法来计算。这样就将一次矩阵运算串行化，降低运算复杂度，速度会大幅提升。缺点是收敛会困难一些。看下图：
 - Optimization Algorithms/1534979648469.png)
How to choose mini-batch size?
- If small training set (m
2000), use batch gradient descent.
- Typical mini-batch size: 64, 128, 256, 512,
->
~
- Make sure mini-batch size fit your CPU/GPU memory.
 - Optimization Algorithms/SVGab6db0e32c10c5236f874ef75e78db13)
Learning Rate Decay
动态调整learning rate的算法有很多种，下面这种是比较常用的
 - Optimization Algorithms/SVG356875ee64da59f32f090db53d327595)
随着epoch_num越来越大，
 - Optimization Algorithms/SVGc745b9b57c145ec5577b82542b2df546)
越来越小。Other learning rate decay methods:
- discrete stair case
- manual decay
 - Optimization Algorithms/SVGea7f36258d6afd834a962cafba5fcc1a)
 - Optimization Algorithms/SVGed9a0ac5081c98ec5d6ba32d1a5bbda1)
指数加权平均相关算法
Momentum, RMSprop, Adam都是和指数加权平均算法(Exponential Weighted Average)相关的。下面一一介绍：
Exponential Weighted Average
公式是:
 - Optimization Algorithms/SVGd8ddcf2e016ce270ec114753e5a9b363)
 - Optimization Algorithms/SVGf5df0fb7447200a566946388337a8005)
个数据进行平均，并添加权重 - Optimization Algorithms/SVG8217ed3c32a785f0b5aad4055f432ad8)
，对本轮数据采用权重 - Optimization Algorithms/SVG13741a4267de21d2928d76992e54f9e9)
。例如 - Optimization Algorithms/SVG13a004478b7652adb8e40ef21ba7fe0d)
，则会加权平均前10个数据，并添加0.1本轮数据。其效果如下图： - Optimization Algorithms/1534980671272.png)
- 蓝点是原始数据
- 红线采用
- 绿线采用
，累积前20个数据的影响
- 黄线采用
，累积前2个数据的影响
可见，采用指数加权平均后，数据变平滑，且
How it works?
其工作原理如下图：
 - Optimization Algorithms/1534981358549.png)
Bias Correction Exponential Weighted Average
之所以有这个bias correction，因为这个指数加权的初始值选的是0，造成开始一段的迭代，会偏离真实值较远。例如下面绿线和紫线。
 - Optimization Algorithms/1535013368575.png)
 - Optimization Algorithms/SVG427639a808a7436d39a85ef7b19f2e51)
 - Optimization Algorithms/SVG2d0078ef79ecf73f88d1bed1892f805b)
也比较小，这样可以让计算出来的 - Optimization Algorithms/SVG3e3c6ee78813607a4d976d92c19dd36e)
没那么小，以达到纠正偏差的效果。Momentum
Momentum就是指数加权平均算法的一种应用。
 - Optimization Algorithms/1535016214569.png)
 - Optimization Algorithms/1535013718754.png)
RMSprop (Root Mean Square prop)
RMSprop是根据Momentum衍生出来的算法。具体做法如下：
On iteration t:
- Compute dw and db on current mini-batch
 - Optimization Algorithms/SVGa9be9fc0d73ca8cc40d13d80682f68fd)
 - Optimization Algorithms/SVG2a9b47056c6bcf0411c6e93da4a5f61a)
 - Optimization Algorithms/SVG67f3e536a6ef4b4169349f3ec466f070)
 - Optimization Algorithms/SVGaedee71cf17574864273c0bc18f25770)
 - Optimization Algorithms/SVG6c291d7691fdc61d45cf64127d6cb702)
为了区分Momentum和Exponential Weighted Average中的hyper parameter
 - Optimization Algorithms/SVG2cae3bbfffb6ab2858054ba28bfcba80)
Adam optimization algorithm
Adam = Adaptive Moment Estimation
Adam = Momentum + Bias Correction + RMSprop
具体算法如下：
 - Optimization Algorithms/SVG96f3d699cafedfa057a74a2c15b5494b)
On iteration t:
- Compute dw and db on current mini-batch
,
,
,
,
Hyper parameters (通常去经验值)
 - Optimization Algorithms/SVGa3a93df97ce5ddc8916fccf598b10ba6)
 - Optimization Algorithms/SVG07d30becbe926e602f10e6769bd36119)
 - Optimization Algorithms/SVG2910c3973a8553d1ba3b2e13f629d0c2)
 - Optimization Algorithms/SVG61e67d308b8deee477513a546e33a13e)
 - Optimization Algorithms/1535017116124.png)
Local Optima Problem
Andrew解释了，在现代的机器学习问题中，不太可能出现local optima
 - Optimization Algorithms/1535017928729.png)