在整个机器学习的第三步,我们需要找一个最好的函数 $f^{\ast}$, 其实就是在解决优化问题

其中 $L$ 是损失函数,$\theta$ 是一组参数,我们使用梯度下降方法完成参数更新。

假设现在的 $\theta$ 中有两个变量 $\{\theta_1, \theta_2 \}$, 随机选择起始点

这里使用上标表示某一组参数,下标表示这组参数中的第 $1$ 个和第 $2$ 个元素。接下来计算 $\theta_{1}^{0}$ 和 $\theta_{2}^{0}$ 对 $L$ 的偏微分,并用原始的 $\theta_{1}^{0}$ 和 $\theta_{2}^{0}$ 减去学习率 $\eta$ 乘上对应偏微分的值进行更新,即:

因为每个元素的处理方式相同,上面的两次更新过程可以简写成

不同的学习率

作为一种人为设定的超参数,学习率的设置有时候会带来一些问题,如上图所示:

  • 红色:学习率合适,随着多次更新,一步步到达局部最优点
  • 蓝色:学习率过低,随着很多次更新,最终会到达局部最优点
  • 绿色:学习率稍大,无法实际收敛到局部最优点,而是在周围摇摆
  • 黄色:学习率过大,随着参数更新,损失函数可能反而变高

左侧的可视化图片适用于参数维度低的情况,此时可以很明显看到更新的方向,而在高维空间情况下很难进行可视化。但能够可视化出损失函数的值随着更新次数产生的变化,这些颜色的曲线与左图是对应的。所以在做梯度下降时,应当将这种损失的变化进行可视化,有助于分析过程,即时对学习率进行调整。

自适应学习率调整:Adagrad

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. JMLR 2011.

有一些自动的方法可以帮助我们调整学习率,最基本也是最简单的原则是:学习率随着参数的更新次数变多而变得越来越小。这是因为最开始的时候,初始点距离局部最小点(目标点) 很远,此时不妨令学习率大一点;经过几次参数更新后,距离目标点已经很近了,应该减少学习率使之最终能够收敛。例如取决于时间或更新次数 $t$:$\eta^{t}=\eta / \sqrt{t+1}$. 但是上面例子中的学习率更新策略过于死板,对于每个参数我们应当“因材施教”,因此在学习率调整上有着许多小技巧,最简单最实用的方法是 Adagrad: 每一个参数的学习率除以之前算出来的微分值的均方根(Root Mean Square).

为了实现学习率对不同参数的自适应,需要将参数分开考虑。假设现在有一个参数 $w$, 一般的梯度下降更新方法是:

而在 Adagrad 中,我们的梯度下降形式为:

其中 $g^{t}=\frac{\partial L\left(\theta^{t}\right)}{\partial w}$, $\sigma ^t$ 是过去所有 $w$ 微分值的均方根,对不同的参数是不一样的。流程如下:

又由于前面提到的 $\eta^{t}=\eta / \sqrt{t+1}$ 和 $\sigma^{t}=\sqrt{\frac{1}{t+1} \sum_{i=0}^{t}\left(g^{i}\right)^{2}}$ 中的 $\sqrt{t+1}$ 在 Adagrad 中可以相互抵消,所以最终的形式中可以不用计算平均:

自适应学习率调整还有许多方法(比如 Adam, 这些在后面深度学习的内容中会细讲),Adagrad 只是其中最简单的一种。矛盾之处在于,Adagrad 中的 $g^{t}$ 这一项告诉我们微分值越大,参数更新幅度越大;而 $\frac{\eta}{\sqrt{\sum_{i=0}^{t}\left(g^{i}\right)^{2}}}$ 这一项却表明微分值越大更新的幅度却要更小。一种直观的解释认为,这是为了强调前后计算出的微分值之间存在的“反差”。

梯度与步长的关系

我们来考虑一元二次函数 $y=a x^{2}+b x+c$, 很容易知道微分 $\left|\frac{\partial y}{\partial x}\right|=|2 a x+b|$, 且最低点是在 $x = -\frac{b}{2 a}$ 的位置。如果随机选一个点 $x_0$ 做梯度下降,我们知道此时最好的步长应该是 $\left|x_{0}+\frac{b}{2 a}\right|$, 整理一下变成 $\frac{\left|2 a x_{0}+b\right|}{2 a}$, 而上面这一项就是 $x_0$ 这一点处的一次微分。因此梯度下降计算出来的微分值越大,表明距离最低点越远,如果踏出去的步伐与一次微分值大小成正比,则有可能是最好的步伐。

可在同时考虑好几个参数的时候,上面的结论不一定成立,如上图所示。如果只考虑 $w_1$ 的变化(蓝色线条), 比较 $a$ 和 $b$ 点的一次微分和距离最低点的距离,结论依旧成立;同理只考虑 $w_2$ 的变化(绿色线条), 比较 $c$ 和 $d$ 点的一次微分和距离最低点的距离,结论依旧成立。但是如果考虑不同的参数如 $a$ 和 $c$ 点,虽然 $c$ 对 $w_2$ 的微分值比 $a$ 对 $w_1$ 的微分值大,但它到最低点的距离却比 $a$ 点要近,因此“更新幅度应该与微分值成正比”的论述在跨参数的情况下并不成立。

仔细观察之前提到的最好的步长 $\frac{\left|2 a x_{0}+b\right|}{2 a}$, 我们知道上面是一次微分值,而分母项为常数 $2a$. 可以发现 $\frac{\partial^{2} y}{\partial x^{2}}=2 a$, 即对 $y$ 的二次微分。所以现在可以知道,最好的步长应该正比于一次微分值,且反比于二次微分。如果考虑二次微分,则会发现在 $w_1$ 方向上二次微分较小,在 $w_2$ 方向上二次微分较大,此时仅仅比较 $a$ 和 $c$ 的一次微分值是不够的。

此时我们回过头看 Adagrad 的公式

$\eta$ 是常数不用去管,$g^{t}$ 是一次微分,而下面的过去的所有一次微分均方根,其实就是想要代表二次微分。在参数量非常多时,计算二次微分非常费时费力,用均方根的计算进行替代可以节省计算开销。

为什么可以进行这样的近似替代呢?我们考虑一个二次微分比较小的峡谷和一个二次微分比较大的峡谷,并考虑一次微分的值,如果我们在一个区间内随机采样足够多的点,就会发现:在左边比较平滑的峡谷中,一次微分通常比较小;在右边比较尖的峡谷中,一次微分通常比较大。而 Adagrad 中的均方根计算,可以想象成在这些地方采样并计算,从而反映二次微分的大小。

随机梯度下降

Large-Scale Machine Learning with Stochastic Gradient Descent

随机梯度下降(Stochastic Gradient Descent) 可以加快训练速度,下面是线性回归的损失函数:

此时的损失是基于所有训练样本计算的误差平方和,梯度下降策略是:

而随机梯度下降的策略是每次顺序或随机取出一个样本 $x^n$, 只考虑现在的参数对其预测效果的影响:

每次只看一个样本,便很快去更新一次参数。如果假设一共有 20 个样本,梯度下降在看完这 20 个样本后只更新了一次参数,而随机梯度下降已经更新了 20 次参数。天下武功,唯快不破,虽然总的计算量差异不大,但是随机梯度下降的方式走得反而较快,如下图所示(左边是梯度下降,右边是随机梯度下降):

特征缩放

假设我们现在要解决回归问题 $y=b+w_{1} x_{1}+w_{2} x_{2}$, 输入特征有 $x_1$ 和 $x_2$. 如果你发现 $x_1$ 和 $x_2$ 的分布范围很不一样,则需要做特征缩放(Feature Scaling). 比如当 $x_2$ 的分布范围远大于 $x_2$ 时,对 $x_2$ 的值进行缩放,使得两个特征的分布比较一致。

[注:这张图来自斯坦福 CS231n 课程]

为什么要使不同的特征范围尽可能一致呢?假设 $x_1$ 的输入值都很小,而 $x_2$ 的输入值都很大,你会发现 $w_1$ 的变化对 $y$ 的变化影响较小,而 $w_2$ 的变化对 $y$ 的变化影响较大。这时候如果画出损失平面,看起来像是椭圆,在 $w_1$ 方向上比较平滑,在 $w_2$ 方向上比较扁而尖。如果输入的分布范围一致,损失平面更像是一个正圆,这种形状上的差异会给梯度下降带来一定的影响。

左图中的梯度下降,需要使用自适应的学习率方法,否则参数更新很难取得较好的效果;而对于缩放后的正圆形,梯度下降总是向最低点的圆心方向走,这样比较有效率。

特征缩放的实现

假设现在有 $R$ 个样本 $x^1,x^2, \ldots , x^r, \ldots ,x^R$, 每个样本中有一组特征,如 $x^1$ 中有 $x^1_1 , x^2_2, \ldots$. 对于每个维度 $i$ 去计算均值 $m_i$ 与标准差 $\sigma_i$, 接着对第 $r$ 个样本的第 $i$ 个元素进行如下处理:

经过这样的处理后,所有维度的均值将变为 $0$, 方差会变为 $1$.

这是常见的标准化/归一化(Normalization) 方法,当然还有其他方法。

梯度下降的数学原理(可选)

当使用梯度下降解决 $\theta^{*}=\arg \min _{\theta} L(\theta)$ 问题时,每次参数更新是否都有这种情况?

显然不一定,比如学习率设置得过大时。

首先不考虑梯度下降,假设我们要解决一个优化问题,参数 $\theta$ 中有两个变量 $\{\theta_1, \theta_2 \}$, 随机选择起始点 $\theta^0$, 我们有方法在起始点附近画一个红色圆圈,在圈中找出里面的最低点。

也即是说给出整个损失函数 $L(\theta)$, 无法立即找出或解出全局最优点,但如果给出一个初始点 $\theta^0$, 可以在附近找出一个最小值点 $\theta^1$, 将圆圈中心点更新为 $\theta^1$, 再找到新的圆圈范围内的最低点 $\theta^2$, 一直重复。怎样在红色圆圈中找到此时能令 $L(\theta)$ 最小的参数呢?这里要用到泰勒展开式。

泰勒展开式指的是,对于任意在 $x=x_0$ 附近可微的函数 $h(x)$, 函数可以写为:

当 $x$ 很接近 $x_0$ 时,会发现一次微分项远大于后面的高次项,因此有

我们举三角函数 $h(x)=\sin (x)$ 在 $x_{0}=\pi / 4$ 的例子来说明:

上图中的水平横线是常数项,斜线是一次项,橙色的曲线是原始的三角函数。如果考虑低次项的曲线形状,与原来的三角函数曲线完全不像。但是在 $x_{0}=\pi / 4$ 附近,形状就很接近,因此此时可以只考虑一次项的部分。

推广到多元的情况,假设现在是两个参数 $x$ 和 $y$, $h(x,y)$ 在 $(x_0, y_0)$ 附近的泰勒展开为:

同样地在很接近 $(x_0, y_0)$ 的地方,后面的项可以消去,则有

基于泰勒展开式的形式,如果以中心点 $(a,b)$ 画了一个很小的半径为 $d$ 的圆圈,这时可以将损失函数简化:

其中 $S=\mathrm{L}(a, b)$ 是一个常数,$u=\frac{\partial \mathrm{L}(a, b)}{\partial \theta_{1}}$, $v=\frac{\partial \mathrm{L}(a, b)}{\partial \theta_{2}}$ 也都是常数. 因此有:

问题变成了:

其中常数 $s$ 不用理会,与 $\theta$ 无关,我们用 $\Delta \theta_1$ 代替 $(\theta_{1}-a)$, 用 $\Delta \theta_2$ 代替 $(\theta_{2}-b)$, 得到:

问题变成了在红色圆圈范围内找出向量 $(\Delta \theta_1, \Delta \theta_2)$, 使之与 $(u, v)$ 的内积最小。显然此时 $(\Delta \theta_1, \Delta \theta_2)$ 的方向应该与 $(u, v)$ 相反,理想情况下大小应当等于圆圈半径 $d$. 这里的“半径”其实就是在两个参数的情况下,进行一次参数更新的限定范围,而机器学习中的特征和参数通常是高维的,又由于目前梯度是已求得的,所以一般将 $\theta$ 的单次参数更新过程引入学习率 $\eta$ 进行表示,二维情况下就是:

整理则可以得到

这个式子实际上就是梯度下降公式,使之成立的前提是泰勒展开式足够精确,即红色圆圈的半径要比较小,对应梯度下降的学习率要很小。理论上学习率 $\eta$ 必须无穷小,才能够保证最终能够找到局部最小点。

因此如果学习率 $\eta$ 没设置好,泰勒展开式不够精确,导致梯度下降的时候损失 $L$ 无法越来越小。

损失函数在梯度下降时可以不可以考虑泰勒展开的二次项甚至更高次项呢?理论上是可行的,这时学习率可以设置得大一些。但需要计算二次微分就很麻烦,可能会引入 Hessian 矩阵进行运算,对于有着大量参数的情况不太适用。

梯度下降的局限性

我们都知道梯度下降会卡在局部最小点,《Gradient Descent Converges to Minimizers》这篇文章中进行了解释。但实际上它还可能卡在鞍点(Saddle Point), 微分值也为零。更常见的情况是,只要微分值接近零时,就可能卡住或者停下在一个类似高原(Plateau) 的地方。想一想为什么?