机器学习笔记：梯度下降

这一节将会分析一下梯度下降算法的理论知识。

梯度下降回顾

首先回顾一下，我们在进行梯度下降的时候需要解决下面这个带有损失函数的优化问题：

$$\boldsymbol{\theta}^*=\arg\min_{\theta}L(\boldsymbol{\theta})$$

其中$L$是损失函数，$\theta$是模型的参数。也就是找到一个最好的参数能够让损失函数最小。假设参数有两个：${\theta_1,\theta_2}$，我们用梯度下降法从一个随机的初始状态开始$\boldsymbol{\theta}_0=\begin{bmatrix}\theta_1^0 \\ \theta_2^0\end{bmatrix}$，然后按照下面的方式将$\theta^0$向$\theta^1$更新：

$$\boldsymbol{\theta}^1 = \boldsymbol{\theta}^0 - \eta\nabla L(\boldsymbol{\theta}^0)$$

其中

$$\nabla L(\boldsymbol{\theta}) = \begin{bmatrix} \partial L(\theta_1)/\partial\theta_1 \\\\ \partial L(\theta_2)/\partial\theta_2 \end{bmatrix}$$

然后这个步骤反复不断进行

$$\boldsymbol{\theta}^2 = \boldsymbol{\theta}^1 - \eta\nabla L(\boldsymbol{\theta}^1) \\\\ \boldsymbol{\theta}^3 = \boldsymbol{\theta}^2 - \eta\nabla L(\boldsymbol{\theta}^2) \\\\ \cdots$$

梯度下降的Tips

Tips 1: 调整学习率

如果学习率太低，梯度下降太慢。学习率太大，比较难收敛。如下图：

有一些方法能够自适应地调整学习率：刚开始学习率应该比较大，随后学习率应该逐渐减小。例如$1/t$ decay方法：$\eta^t=\eta/\sqrt{t+1}$。除此之外，不同的参数还应该用不同的学习率来更新。

AdaGrad

核心思想：每一个参数的learning rate都应该除以包含了之前所有导数的均方根。

$$w^{t+1}\leftarrow w^t-\frac{\eta^t}{\sigma^t}g^t$$

其中$w$是某一个参数，$\sigma^t$是之前参数所有导数的均方根。假设第一次更新：

$$w^1\leftarrow w^0-\frac{\eta^0}{\sigma^0}g^0 \\\\ \sigma^0=\sqrt{(g^0)^2}$$

第二次更新：

$$w^2\leftarrow w^1-\frac{\eta^1}{\sigma^1}g^1 \\\\ \sigma^1=\sqrt{\frac{1}{2}\left[(g^0)^2 + (g^1)^2\right]}$$

第三次更新：

$$w^3\leftarrow w^2-\frac{\eta^2}{\sigma^2}g^2 \\\\ \sigma^2=\sqrt{\frac{1}{3}\left[(g^0)^2 + (g^1)^2 + (g^2)^2\right]}$$

一直到第$t$次更新：

$$w^{t+1}\leftarrow w^t-\frac{\eta^t}{\sigma^t}g^t \\\\ \sigma^t=\sqrt{\frac{1}{t+1}\sum_{i=0}^t(g^i)^2}$$

其中$\eta^t$为：

$$\eta^t=\frac{\eta}{\sqrt{t + 1}}$$

由于$\eta^t$和$\sigma^t$中都有$\sqrt{t + 1}$项，所以

$$w^{t+1}\leftarrow w^t-\frac{\eta}{\sqrt{\sum_{i=0}^t(g^i)^2}}g^t$$

对于AdaGrad有效性的解释有很多。其中一个是：对于只含有一个参数的模型来说，最佳的更新方向就是参数的一阶导数方向。但当包含不止一个参数的时候，这个“最佳”就不再成立了，而应该是“一阶导数除以二阶导数”的方向。而AdaGrad的分子中的$g^t$是一阶导数，而分母里的$\sigma^t$是对二阶导数的一个“低运算成本的模拟”。

Tips 2： 随机梯度下降

梯度下降使用的loss function为（以Linear Regression为例）：

$$L=\sum_n\left(\hat{y}^n-(b+w\cdot x^n)\right)^2$$

然后用梯度下降更新：$\boldsymbol{\theta}^i=\boldsymbol{\theta}^{i-1}\eta\nabla L(\boldsymbol{\theta}^{i-1})$

而随机梯度下降每次只从数据集中拿出1个样本进行运算（而非利用整个数据集取平均），损失函数则是：

$$L^n=\left(\hat{y}^n-(b+w\cdot x^n)\right)^2$$

然后在梯度下降时只用这一个样本进行更新:$\boldsymbol{\theta}^i=\boldsymbol{\theta}^{i-1}\eta\nabla L^n(\boldsymbol{\theta}^{i-1})$

Tips 3: Feature Scaling

即将输入的各个维度都压缩到相同数量级的范围内。

梯度下降的理论基础

在进行梯度下降的过程中，我们如何从一个当前的参数，找到能够让损失函数下降最快的方向然后进行一次参数更新？这还要从泰勒展开说起。

泰勒展开: 如果函数$h(x)$在$x=x_0$附近可以无限阶可导，那么这个函数可以在$x=x_0$附近展开成：

$$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$$

当$x=x_0$附近的时候，我们可以把后面的高次项删掉：$h(0)\approx h(x_0)+h’(x_0)(x-x_0)$。

除此之外，如果函数包括多个变量（例如有两个变量$x,y$），那么在$x=x_0, y=y_0$附近$h(x,y)$可以展开成：

$$h(x,y) = h(x_0, y_0) + \frac{\partial h(x_0, y_0)}{\partial x}(x-x_0) + \frac{\partial h(x_0, y_0)}{\partial y}(y-y_0)$$

注意，上式中泰勒展开原本包含的高次项已经忽略掉。

回到梯度下降，当我们有一个初始化的参数点$(a,b)$时（假设参数有两个），在$\theta_1=a, \theta_2=b$附近足够小的范围内，下面这个对损失函数的泰勒展开是成立的：

$$L(\theta_1, \theta_2) = L(a,b)+\frac{\partial L(a,b)}{\partial\theta_1}(\theta_1-a)+\frac{\partial L(a,b)}{\partial\theta_2}(\theta_2-b)$$

然后我们假设$s=L(a,b)$，$u=\frac{\partial L(a,b)}{\partial\theta_1}$，$v=\frac{\partial L(a,b)}{\partial\theta_2}$，此时我们可以把上面那个泰勒展开改写成：

$$L(\boldsymbol{\theta})\approx s+u(\theta_1-a) + v(\theta_2-b)$$

现在的问题变成，我们该如何在一个很小的范围内（例如$d$）寻找$\theta_1,\theta_2$使得损失函数最小。我们可以用一个半径为$d$的圆作为约束：$(\theta_1-a)^2+(\theta_2-b)^2\leq d^2$来最小化损失函数的泰勒展开

$$L(\boldsymbol{\theta})\approx u\cdot\Delta\theta_1+v\cdot\Delta\theta_2$$

其中由于$s$对参数优化没有作用所以忽略，并假设$\Delta\theta_1=\theta_1-a$，$\Delta_theta_2=theta_2-b$。

上面这个损失函数的式子，实际上是$(u,b)$和$(\Delta\theta_1,\Delta\theta_2)$这两个向量的内积！那么我们如何选择$(\Delta\theta_1,\Delta\theta_2)$来让这个损失最小呢？显然是选择向量$(u,v)$相反的方向。即图下图所示：

所以，为了让损失最小，所选择的参数为：

$$\begin{bmatrix} \Delta\theta_1 \\\\ \Delta\theta_2 \end{bmatrix} = -\eta \begin{bmatrix} u \\\\ v \end{bmatrix}$$

即为$u,v$的反方向的$\eta$倍是算出的Loss应该是最小的。然后再整理一下公式，由于$\Delta\theta_1=\theta_1-a$，$\Delta\theta_2=\theta_2-b$，所以能够得到：

$$\begin{bmatrix} \theta_1 \\\\ \theta_2 \end{bmatrix} = \begin{bmatrix} a \\\\ b \end{bmatrix} -\eta \begin{bmatrix} u \\\\ b \end{bmatrix} = \begin{bmatrix} a \\\\ b \end{bmatrix} -\eta \begin{bmatrix} \frac{\partial L(a,b)}{\partial \theta_1} \\\\ \frac{\partial L(a,b)}{\partial \theta_2} \end{bmatrix}$$

而上面这个式子起始就是梯度下降。不过这个梯度下降成立的前提，是泰勒展开的估计是准确的。也就是说，只有当约束半径$d$足够小的时候才成立。即我们需要保证$\eta$足够小。所以我们会发现当$\eta$过大的时候性能反而变差。

另一方面，我们上面对泰勒展开的近似只考虑了一次式，而起始有一些优化方法是可以考虑更高阶式子的，例如牛顿法考虑了二阶展开部分。保留更高阶的展开意味着可以用更大的学习率，但需要花费更多的运算来计算二阶导数。