台大李宏毅机器学习——梯度下降

关于梯度下降的理论基础

梯度下降是要解决这样的一个凸优化问题: \[ \theta^* = \arg \max_{\theta} L(\theta), L \text{ is the object function, }\theta \text{ is parameters}. \] 用向量 \(\bigtriangledown L = \begin{bmatrix} \frac{\partial L}{\partial \theta_1} \\ \frac{\partial L}{\partial \theta_2} \\ \vdots \\ \frac{\partial L}{\partial \theta_n} \end{bmatrix}\) 表示梯度。

为了求解这个目标函数,我们需要按照下面方法更新\(\theta\): \(\boldsymbol{\theta}^1 = \boldsymbol{\theta}^0 - \eta \begin{bmatrix} \frac{\partial L}{\partial \theta_1} \\ \frac{\partial L}{\partial \theta_2} \\ \vdots \\ \frac{\partial L}{\partial \theta_n} \end{bmatrix}.\)

这里我们发现有个\(\eta\)参数。这个参数我们称为 Learning Rate。Learning Rate 本身是机器学习中需要调节的一个重要参数。如果我们将梯度下降当做是爬山,那么Learning Rate我们可以认为是每一次爬山迈的步子大小,而梯度是我们面向的方向。所以很多时候,我们会将learning rate叫做步长。

上图显示了,如果我们有个很大的learning rate,那么我们可能会一步跨到更高的地方,或者来回震荡,无法迭代到最优解,相反,很小的 learning rate 可以让你到达最优解,但是将消耗大量的时间。

那么是否有办法来自适应调节 learning rate?

比如,一开始我们通常离最优解很远,那么可以让 learning rate 大一点,随着迭代次数增加,可以减少 learning rate。因此我们可以这样设计 \(\eta^t = \eta^0 / \sqrt{t+1}\)

事实上有很多种自适应的方法,例如Adagrad,Adam等。李老师介绍了Adagrad。定义为每个 parameter 都去除之前所有的微分的 root mean square。

比如我们有一个参数 \(w\), 原来的梯度下降是这样定义的: \[ w^{t+1} = w^t - \eta^t g^t, \] 而adagrad是: \[ w^{t+1} = w^t - \frac{\eta^t}{\sigma^n} g^t, \]\(\sigma^t\) 就是 \(w\) 在前 \(t\) 步微分的 root mean square。

所以 adagrad 这样更新 \(w\)

这里要注意一点,adagrad中,梯度算出来越大,说明在这个参数方向上离最优解越远。直观上步长应该越大越快收敛,但是分母部分,梯度越大,步长越小。对于单个参数而言,这没有问题,但是如果现在考虑多个参数,那么梯度越大,不一定离最优解越远。如下图:

我们看到,绿色的曲线,我们离最优解其实是比较近的,但是梯度很大,这时候如果我们只用一阶导数的话,要走好几步才能走到底。这就跟我们之前想的不太一致了,我们希望步长是慢慢减小的,但是我们希望的是步长在该大的地方大,改小的地方小。所以只考虑一阶段远远不够。

因此最好的 step 应该是还要考虑二次微分,最好的步长是一阶微分的绝对值除以二阶微分,这样才能在不同参数之间比较。

回过头来,adagrad 里面的分母起到的作用就是来替代二阶微分的作用。为什么这样的设计能够work?

如图所示,我们画出一阶微分的绝对值,只要我们 sample 足够多的数据,我们就能得到,由于二阶微分较小,所以左边的函数一阶微分的 root mean square 就比较小。

那么有没有提高梯度下降效率的方法?一般梯度下降需要遍历整个数据集,而 SGD(Stochastic Gradient Descent)每一次更新仅仅考虑一个 sample 的 Loss。

从图上看,两者的差别就在于 SGD 更散乱,但更快收敛。

实践上,为了让模型收敛不是太散乱,同时兼顾效率,会考虑使用 mini-batch SGD。也就是说,一次性用一小批数据来更新梯度。

另外一个可以加速收敛的方法是做 feature scaling。考虑下图的情况

在做 scaling 前,左边的 \(x_2\) 导致 \(w_2\) 的变动对 loss function 的影响非常大,所以左图最后收敛方向都会沿着 \(w_1\) 缓慢下降。因此不用 adagrad 的话,左图的收敛非常慢。而右图因为接近正圆形,沿着任意方向都能快速接近最优解。

那么 scaling 方法有哪些?常见的比如 z-score,0-1标准化等。这个也叫作normalization。


这里开始讨论梯度下降的数学原理。

梯度下降可以成立是基于泰勒展开,Taylor series。那么函数可以写成: \[ \begin{align} h(x) &= \sum_{k=0}^{\infty} \frac{h^{(k)}(x_0)}{k!}(x-x_0)^k \\ &= h(x_0) + h'(x_0)(x-x_0)+\frac{h''(x_0)}{2!}(x-x_0)^2+\dots \end{align} \]\(x\) 无限趋近于 \(x_0\) 时候,我们取一阶泰勒展开就可以近似估计原函数。相应的,如果原函数是个多元函数,那么相应的将导数改成偏导数就可以。

那么,基于泰勒公式,我们的 Loss function 就可以用泰勒展开为一阶多项式。

那么在图上一个红色的圆圈内,如何让 Loss 最小?我们可以发现,Loss 只跟两个向量有关,一个是\((u, v)\),另一个是\((\theta_1 - a, \theta_2 - b)\)。我们用\((\Delta \theta_1\), \(\Delta \theta_2)\) 表示第二个向量。

因此我们可以知道,要让Loss最小,就是上述两个向量的内积最小,也就是找\((u, v)\)反方向上长度最长的向量: \[ \begin{bmatrix} \Delta \theta_1 \\ \Delta \theta_2 \end{bmatrix} = -\eta \begin{bmatrix} u \\ v \end{bmatrix} \] 也就是 \[ \begin{bmatrix} \theta_1 \\ \theta_2 \end{bmatrix} = \begin{bmatrix} a \\ b \end{bmatrix} - \eta \begin{bmatrix} u \\ v \end{bmatrix} \]

优化方法有很多,之前博客里面写的遗传算法,退火算法,蚁群算法等都是,但是 mini-batch SGD 是目前最常用的方法,因为效率极高。但是这不意味着 SGD 就是最好的方法,因为这是一个很典型的贪心算法,大部分情况下只能接近局部最优。 如下图:

通常我们发现梯度下降很慢的时候,就会停止迭代了,但实际上,可能我们离局部最优都很远,更不用说全局最优。深度学习常见的一个坑。

乞讨码