百面机器学习｜第七章优化算法知识点(二)

2019-01-30 本文已影响33人蓝白绛

前言

如果你能找到这里，真是我的幸运~这里是蓝白绛的学习笔记，本集合主要针对《百面机器学习——算法工程师带你去面试》这本书。主要记录我认为重要的知识点，希望对大家有帮助。

第七章优化算法

6、随机梯度下降法的加速

随机梯度下降是深度学习中最常用的优化方法，但是偶尔也会失效，因为随机梯度下降好比蒙上眼睛只凭脚底踩石头的感觉判断下山路径，每步接收到的信息量有限，因此对梯度的估计常常出现偏差，造成目标函数曲线收敛很不稳定，伴有剧烈波动，甚至出现不收敛的情况。如下图所示。
7-6 随机梯度下降参数优化轨迹
随机梯度下降与批量梯度下降：批量梯度下降法为了获取准确的梯度，每一步都把整个训练集载入进来进行计算，时间花费和内存开销都非常大，无法应用于大数据集、大模型的场景。随机梯度下降则放弃了对梯度准确性的追求，每步仅仅随机采样一个(或少量)样本来估计当前梯度，计算速度快，内存开销小。
对随机梯度下降法来说，最可怕的不是局部最优点，而是山谷和鞍点两类。山谷点导致收敛不稳定和收敛速度慢；鞍点导致随机梯度下降法无法准确察觉出梯度的微小变化，结果就停滞下来。
随机梯度下降法的优化：随机梯度下降本质上是用迭代方式更新参数，更新公式为： $\theta_{t+1}=\theta_t+\eta g_t$ 基于梯度下降有以下几种优化方法：

动量(Momentum)方法：我们希望当沿山谷滚下时，不容易受到途中旁力的干扰，使轨迹更稳更直；当来到鞍点中心处时，在惯性的作用下继续前行，从而有机会冲出平坦的陷阱。动量方法模型参数的迭代公式为： $v_t=\gamma v_{t-1}+\eta g_t$ $\theta_{t+1}=\theta_t-v_t$ 可以看到不加动量的方法每次只利用当前估计的梯度 $g_t$ ，而动量方法利用了上一次的步伐 $v_{t-1}$ 和当前估计的梯度 $g_t$ 。惯性就体现在对前一次步伐信息的重利用上。当前梯度好比加速度，前一次步伐好比前一刻的速度，当前步伐好比当前时刻的速度。另外，衰减系数 $\gamma$ 扮演了阻力的作用。
相比随机梯度下降，动量方法收敛速度更快，收敛曲线更加稳定。如下图所示。
7-6 动量方法的效果
AdaGrad方法：除了可以从过去的步伐中获得冲劲，还可以获得对周围环境的感知，即使蒙上眼睛，依靠前几次迈步的感觉，应该也能判断出一些信息。
例如在文本处理中训练词嵌入模型的参数时，有的词或词组频繁出现，有的很少出现。数据的稀疏性导致相应参数的梯度的稀疏性，不频繁出现的词或词组的参数的梯度在大多数情况下为0，因而这些参数被更新的频率很低。
我们希望更新频率低的参数可以拥有较大的更新步幅，而更新频率高的参数的步幅可以减小。AdaGrad方法采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性，取值越小表明越稀疏，更新公式表示为： $\theta_{t+1,i}=\theta_{t.i}-\frac{\eta}{\sqrt{\sum_{k=0}^{t}g_{k,i}^2+\epsilon}}g_{t,i}$ 其中 $\theta_{t+1,i}$ 表示 $t+1$ 时刻参数向量 $\theta_{t+1}$ 的第 $i$ 个参数， $g_{k,i}$ 表示 $k$ 时刻的梯度向量 $g_k$ 的第 $i$ 个维度。另外，分母中求和形式实现了退火过程，这是很多优化技术中常见的策略，意味着随着时间推移，学习速率 $\frac{\eta}{\sqrt{\sum_{k=0}^{t}g_{k,i}^2+\epsilon}}$ 越来越小，保证了算法的收敛。
注：简言之，这里 $\theta_{t+1,i}$ 是第 $i$ 个分量，它的参数更新，与该分量从时刻0到时刻 $t$ 的梯度的第 $i$ 个分量的平方的和有关，也就是记录了该分量 $t$ 时刻及以前的所有更新。并将这个和做了分母，让更新比较少的参数拥有更大的更新步幅。为了避免分母为0，还加入了 $\epsilon$ 。
Adam方法：Adam方法将惯性保持和环境感知两个优点集于一身。一方面，Adam记录梯度的一阶矩(first moment)，即过往梯度与当前梯度的平均，这体现了惯性保持；另一方面，Adam还记录梯度的二阶矩(second moment)，即过往梯度平方与当前梯度平方的平均，这类似AdaGrad方法，体现了环境感知能力，为不同参数产生自适应的学习速率。一阶矩和二阶矩采用类似于滑动窗口内求平均的思想进行融合，即当前梯度和近一段时间内梯度的平均值，时间久远的梯度对当前平均值的贡献呈指数衰减。具体来说，一阶矩和二阶矩采用指数衰减平均(exponential decay average)技术，计算公式为： $m_t=\beta_1m_{t-1}+(1-\beta_1)g_t$ $v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2$ 其中 $\beta_1$ ， $\beta_2$ 为衰减系数， $m_t$ 是一阶矩， $v_t$ 是二阶矩。
一阶矩相当于估计 $\mathbb{E}[g_t]$ ，当下梯度 $g_t$ 是随机采样得到的估计结果，我们更关注它的期望。二阶矩相当于估计 $\mathbb{E}[g_t^2]$ ，AdaGrad是加和，Adam是期望。他们的物理意义是：
(1) $||m_t||$ 大且 $v_t$ 也大时，梯度大且稳定，表明遇到了明显的大坡，前进方向明确；
(2) $||m_t||$ 趋于0且 $v_t$ 大时，梯度不稳定，表明可能遇到一个峡谷，容易引起反弹震荡；
(3) $||m_t||$ 大且 $v_t$ 趋于0时，这种情况不可能出现；
(4) $||m_t||$ 趋于0且 $v_t$ 趋于0时，梯度趋于0，可能到达局部最低点，也可能走到一片坡度极缓的平地，此时要避免陷入平原陷阱(鞍点)。
Adam方法还考虑了 $m_t$ ， $v_t$ 在零初始之情况下的偏置矫正。具体来说，Adam的更新公式为： $\theta_{t+1}=\theta_t-\frac{\eta\cdot\hat{m}_t}{\sqrt{\hat{v}_t+\epsilon}}$ 其中， $\hat{m}_t=\frac{m_t}{1-\beta_1^t}$ ， $\hat{v}_t=\frac{v_t}{1-\beta_2^t}$ 。 $m_t=\beta_1m_{t-1}+(1-\beta_1)g_t$ $v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2$
Nesterov Accelerated Gradient方法：该方法扩展了动量方法，顺着惯性方法，计算未来可能位置处的梯度而非当前位置的梯度，这个“提前量”的设计让算法有了对前方环境预判的能力。
AdaDelta和RMSProp方法：两个方法非常类似，是对AdaGrad方法的改进。AdaGrad方法采用所有历史梯度平方和的平方根做分母，分母随时间单调递增，产生自适应学习速率随时间衰减的速度过于激进。AdaDelta和RMSProp采用指数衰减平均的方法，用过往梯度的均值代替它们的求和。
AdaMax方法：该方法是Adam方法的变种，对梯度平方的处理由指数衰减平均改为指数衰退求最大值。
Nadam方法：该方法可以看成Nesterov Accelerated Gradient版的Adam。

7、L1正则化与稀疏性

稀疏性：稀疏性是我们希望的。我们希望模型参数具有稀疏性，也就是模型的很多参数是0(是0而不是很小很小的数)。这相当于对模型进行了一次特征选择，只留下一些比较重要的特征，提高模型的泛化能力，降低过拟合的可能。在实际应用中，机器学习模型的输入动辄几百上千万维，稀疏性就显得非常重要。
L1正则化产生稀疏解的原因：

角度1：解空间形状
如下图所示，在二维的情况下，黄色的部分是L2和L1正则项约束后的解空间，绿色的等高线是凸优化问题中目标函数的等高线。由图可知L2正则项约束后的解空间是圆形，而L1正则项约束的解空间是多边形。显然，多边形的解空间更容易在尖角处与等高线碰撞出稀疏解。这个解释是正确的，但是不够精确。
7-7 L1L2正则化对应解空间角度
进一步挖深，为什么加入正则项就是定义了一个解空间约束？为什么L1和L2的解空间是不同的？可以通过KKT条件给出一个解释。
事实上，“带正则项”和“带约束条件”是等价的。为了约束 $w$ 的可能取值空间从而防止过拟合，我们为该优化问题加上一个约束，就是 $w$ 的L2范数的平方不能大于 $m$ ：
$\begin{cases} \min\sum_{i=1}^N(y_i-w^Tx_i)^2, \\ s.t. ||w_2^2\leq m||. \end{cases}$
为了求解带约束条件的凸优化问题，其拉格朗日函数为： $\sum_{i=1}^N(y_i-w^Tx_i)^2+\lambda(||w||_2^2-m)$ 若 $w^*$ 和 $\lambda^*$ 分别是原始问题和对偶问题的最优解，则根据KKT条件，它们应该满足： $\begin{cases} 0=\nabla_w\lgroup\sum_{i=1}^N(y_i-w^{*T}x_i)^2+\lambda^*(||w^*||_2^2-m)\rgroup, \\ 0\leq\lambda^*. \end{cases}$ 其中第一个式子就是 $w^*$ 为带L2正则项优化问题的最优解的条件，而 $\lambda$ 就是L2正则项前面的正则参数。所以L2正则项相当于为参数定义了一个圆形的解空间(因为必须保证L2范数不能大于 $m$ )，而L1正则化相当于为参数定义了一个菱形的解空间。
如果原问题目标函数的最优解不是恰好落在解空间内，那么约束条件下的最优解一定是在解空间的边界上。而L1“棱角分明”的解空间显然更容易与目标函数等高线在角点碰撞，从而产生稀疏解。
角度2：函数叠加
这个角度更加直观。仅考虑一维的情况，多维情况是类似的。假设棕线是原始目标函数 $L(w)$ 的曲线图，最小值点在蓝点处，对应的 $w^*$ 非0。
7-7 L1L2函数叠加角度
首先考虑加上L2正则项，目标函数变为 $L(w)+Cw^2$ ，其函数曲线为黄色，最小值点在黄点处，对应的 $w^*$ 的绝对值减小了，但仍然非0。
考虑加上L1正则项，目标函数变为 $L(w)+C|w|$ ，其函数曲线为绿色，此时最小值点在红点处，对应的 $w$ 是0，产生了稀疏性。
产生上述现象的原因也很直观，加入L1正则项后，对带正则项的目标函数求导，正则项部分产生的导数在原点左边部分是 $-C$ ，在原点右边部分是 $C$ ，因此只要原目标函数导数的绝对值小于 $C$ ，则带正则项的目标函数在原点左边部分始终是递减的，在原点右边部分始终是递增的，最小值点自然在原点处。
相反，L2正则项在原点处的导数为0，只要原目标函数在原点处的导数不为0，那么最小值点就不会在原点，所以L2只有减小 $w$ 绝对值的作用，对解空间的稀疏性没有贡献。
在一些线梯度下降算法中，往往会采用截断梯度法来产生稀疏性，这和L1正则项产生的稀疏性原理是类似的。
角度3：贝叶斯先验
从贝叶斯的角度来理解L1、L2正则化，L1正则化相当于对模型参数 $w$ 引入了拉普拉斯先验，L2正则化相当于引入了高斯先验，而拉普拉斯先验使参数为0的可能性更大。
下图为高斯分布曲线，它在极值点(0点)处是平滑的，也就是高斯先验分布认为 $w$ 在极值点附近取不同值的可能性是接近的。这就是L2正则化只会让 $w$ 更接近0点，而不会等于0的原因。
7-7 L1L2贝叶斯先验角度高斯分布曲线
下图为拉普拉斯分布曲线，它在极值点(0点)处是一个尖峰，所以拉普拉斯先验分布中参数 $w$ 的取值为0的可能性要更高。
7-7 L1L2贝叶斯先验角度拉普拉斯分布曲线