机器学习基础(3)-梯度下降
梯度下降
对于机器学习来说，我们有它的三要素，分别是模型、策略以及算法。其中的策略方面，我们会定义损失函数，而几乎所有的机器学习算法，最终都会归结于求某个目标函数的极值（一般是损失函数的最小值）。这对应到最优化问题，而在机器学习中，常用的最优化方法就是梯度下降。
首先考虑存在一个假设空间\(H\)，训练集为\(D(|D| =N)\)。机器学习需要学习得到的目标函数为\(y = f(x)\)，一个具体的目标函数对应一组特定的参数\(w\)。考虑损失函数Loss Function，它可以表示成\(L(y,f(x))\)。由于\(f(x)\)的确定需要\(w\)的参与，所以损失函数表示成\(L(w,x,y)\)。于是我们的策略就是如下的最优化问题： \[ \min_{w} \frac{1}{N}\sum_{i=1}^{N}L(w,x_i,y_i) \] 这个最优化问题是说，我们需要选取一个参数向量\(w\)使得损失函数在训练集上的平均损失最小。此时，整体的优化目标函数看作是关于\(w\)的函数，如果我们能够找到在某个\(w\)上，上面式子的梯度（导数）为0，则表示找到了一个极值点。这里的优化目标函数记作\(L(w)\)，它和损失函数\(L(w,x,y)\)有如下关系，注意区分不同的表述。 \[ L(w) = \frac{1}{N}\sum_{i=1}^{N}L(w,x_i,y_i) \] 找到一个极值点就像在山谷中找到一个最低点。梯度下降的思想在于，通过迭代向下，每次选取当前最优的下降方向迈出一小步，经过多轮迭代之后，就能够达到谷底。对于当前位置来说，下降的最优方向就是当前的梯度方向。同时我们还需要考虑当前下降的步长是多少，所以还需要引入学习率（Learning Rate）的概念，通常使用\(\eta\)来表示。
我们用\(w^{i}\)表示经过第\(i\)次参数更新后参数向量\(w\)的值，那么初始值就是\(w^0\)，而梯度下降每次的参数更新就可以表示成下面的过程： \[ w^{n+1} \leftarrow w^{n} - \eta \bigtriangledown L(w) \] 在梯度下降的过程中，我们会多次重复上面的过程，直到优化目标函数的值收敛不变。不过这是一种理想情况，很多时候是走不到梯度严格为0的地方的，所以一般的停止条件是经过足够多轮数的迭代，从而我们认为此时的优化目标已经足够小了。
当然我们可以直觉地考虑，如果学习率\(\eta\)设置得过大，有可能我们会在最低点附近反复横跳，错失损失函数的最小值；而如果设置得过小，则有可能需要迭代非常多的次数才能够找到最小值，消耗较多的时间。因此在实际过程中，选择一个合适的学习率是非常重要的。
不同的梯度下降方法
标准梯度下降
标准的梯度下降在每一次参数更新中，需要考虑训练集中所有的数据，计算损失函数\(L(w,x,y)\)在每个数据\(x_i\in D\)上的梯度之后进行平均，以此作为一次梯度更新的值。
这种算法每次都在遍历了整个训练集之后才对参数进行更新，因此下降方向是最优的方向。但是也是由于每一轮都需要遍历整个训练集，所以在时间和效率上花费较大。
Mini-Batch 梯度下降
标准的梯度下降每次更新梯度都需要遍历整个训练集，但是很多时候通过整个训练集计算出来的梯度，与通过部分训练集计算出来的梯度相差并不是很多，于是我们可以在每次更新参数的时候，随机从样本中抽取\(M\)个样本进行梯度的计算，从而进行参数更新。这种方式叫做Mini-Batch 梯度下降，\(M\)被称为batch size。相比于标准梯度下降来说，能够提高算法的运行速度。
当然在实际使用的时候，我们不会每次更新都随机挑选\(M\)个样本。我们会首先将所有的训练集划分成一个个batch，\(batch\ size=M\)。之后进行迭代，每次迭代的时候看一个batch，并进行参数更新update。过程依次进行，直到看过所有的batch之后，我们称为经过了一个epoch。之后重新从第一个batch开始，进行下一次的参数更新。我们也可以引入Shuffle操作，主要目的在于将batch的分割变得随机化，使得在每一次epoch中，batch的内容都是与上一次epoch不同的。
随机梯度下降SGD
在Mini-Batch 梯度下降中，极端地如果batch size为1，也就是每次更新参数的时候只从训练集中随机选取一个样本进行梯度计算，这种方式被称为随机梯度下降（Stochastic Gradient Descent，SGD）。由于每次仅仅计算在一个样本上的梯度，SGD的速度要比Mini-Batch 梯度下降还要高，但是也因为仅使用一个样本梯度方向来表示整个数据上的梯度方向，下降路径很容易受到噪声的影响。看起来就像醉汉走路一样，变得歪歪斜斜。
Momentum 梯度下降
Momentum 梯度下降对参数更新的方式进行调整。Momentum意为动量，这种方法参考了物理学中的概念。我们每次更新参数时，并不仅仅参考当前的梯度方向\(g=\bigtriangledown L(w)\)，还参考之前的方向\(m\).（类似于矢量相加的效果）： \[ \begin{aligned} \text{初始参数为：} & w ^0 \\ \text{movement为：} &m^0 = 0 \text{(上一步没有移动)} \\ \text{计算梯度：} &g^0\\ \\ \text{进行第一次移动：}& m^1 = \lambda m^0 - \eta g^0 \\ \text{第一次参数更新：}& w ^1 = w ^0 + m^1 \\ \\ \text{梯度计算：} &g^1\\ \text{movement为：} & m^2 = \lambda m^1 - \eta g^1\\ \text{第二次参数更新：}& w ^2 = w ^1 + m^2\\ \end{aligned} \] 这里引入了新的参数\(\lambda\)，同学习率一样，需要我们事先进行确定。该参数的含义表示我们应该对过往的动量方向给予多少的重视度。
上面的计算过程进行迭代，又可以得到m的一系列连续的表达式： \[ \begin{aligned} m^0 &= 0 \\ m^1 &= -\eta g^0 \\ m^2 &= -\lambda \eta g^0 - \eta g^1 \\ m^3 &= -\lambda ^2 \eta g^0 - \lambda \eta g^1 - \eta g^2 \\ ... \end{aligned} \] 这也就是说，在每次进行参数更新的时候，都是考虑从前所有的梯度，使用从前的梯度的某种线性组合来进行更新。这种优化方式并不会立刻改变梯度优化的方向，而是通过积累一点点变化的。这种优化方式的好处在于通过不同训练样本求梯度的时候，始终都会增大最优方向上的梯度值，因此可以减少许多震荡。
AdaGrad 梯度下降
从直觉上考虑，当我们远离谷底的时候，我们应该使我们的步长尽量大一些，以便于快速接近谷底。而当我们靠近谷底的时候，步长应该尽量变小，因为如果在谷底附近步长仍然很大的话，容易导致优化目标函数的值在山谷中来回震荡。所以实际上在整个学习过程中，学习率不应该使一成不变的。在训练过程中，应该对不同情况进行学习率的调整，即对学习率进行客制化，做到学习率的调整（Adaptive Learning Rate）。从总体上把握，在梯度较小的地方，我们希望学习率较大；在梯度较大的地方，我们需要学习率较小。
为了调整，考虑参数\(w\)的更新过程，将更新过程改进为： \[ w^{t+1} = w ^t -\frac{\eta}{\sigma ^t} g^t \] 这里的上标t表示更新参数的次数，式子中，\(\sigma^t\)即为我们用于客制化学习率的参数向量，这一参数如何计算得来也有多种方式。一种方法是利用方均根（Root Mean Square）来计算\(\sigma\):
\[ \begin{aligned} w^1 \leftarrow w^0 - \frac{\eta}{\sigma ^0} g^0 \quad \sigma^0 &= \sqrt{(g^0)^2} = ||g^0|| \\ w^2 \leftarrow w^1 - \frac{\eta}{\sigma ^1} g^1 \quad \sigma^1 &= \sqrt{\frac{1}{2}[(g^0)^2+(g^1)^2]} \\ w^3 \leftarrow w^2 - \frac{\eta}{\sigma ^2} g^2 \quad \sigma^2 &= \sqrt{\frac{1}{3}[(g^0)^2+(g^1)^2+(g^2)^2]} \\ &... \\ w^{t+1} \leftarrow w^t - \frac{\eta}{\sigma ^t} g^t \quad \sigma^t &= \sqrt{\frac{1}{t+1}\sum \limits^{t}_{i=0}(g^i)^2} \\ \end{aligned} \] 这样设置，对于某一个参数\(w_i\)的更新，假如这个参数所处的地方比较平坦，梯度都比较小，那么设置的学习率就会更大；反之如果参数所处的地方比较陡峭，梯度较大，那么设置的学习率就会更小。这种动态调整学习率的方法，对应的方法就是Adagrad 梯度下降。
RMSProp
上面的Adagrad梯度下降方法也存在某种局限性，它考虑当前的位置的时候，过往的梯度都具有相同的重要性。而RMSProp方法在Adagrad方法的基础上进行更新，改进其中\(\sigma\)的计算方式，得到如下方法：
\[ \begin{aligned} w^1 \leftarrow w^0 - \frac{\eta}{\sigma ^0} g^0 \quad \sigma^0 &= \sqrt{(g^0)^2} = ||g^0|| \\ w^2 \leftarrow w^1 - \frac{\eta}{\sigma ^1} g^1 \quad \sigma^1 &= \sqrt{\alpha(\sigma^0)^2 + (1 - \alpha)(g^1)^2} \\ w^3 \leftarrow w^2 - \frac{\eta}{\sigma ^2} g^2 \quad \sigma^2 &= \sqrt{\alpha(\sigma^1)^2 + (1 - \alpha)(g^2)^2} \\ &... \\ w^{t+1} \leftarrow w^t - \frac{\eta}{\sigma ^t} g^t \quad \sigma^t &= \sqrt{\alpha(\sigma^{t-1})^2 + (1 - \alpha)(g^t)^2} \\ \end{aligned} \] 其中引入的参数\(\alpha\)来进行调整，范围为\(0 < \alpha < 1\)。
在这种方法中，\(\sigma\)同样考虑了之前所有的梯度\(g\)，但是与之前考虑所有的梯度具有相同的重要性不一样，这种方法可以利用参数\(\alpha\)来调整当前梯度的重要性，因此可以设置对梯度地变化更加敏感。
Adam 梯度下降
Adam在上面一些梯度下降方法的基础上，进行改进，有如下的更新方式，其中\(\beta_1,\beta_2\)都是接近1的数，\(\epsilon\)是为了防止除以0，\(g_t\)表示当前轮次的梯度。在Adam原论文以及一些深度学习框架中，默认值为\(\beta_1=0.9,\beta_2=0.999,\epsilon=10^{-8},\eta=0.001\)： \[ \begin{aligned} m_t &= \beta_1 m_{t-1} + (1-\beta_1)g_t\\ v_t &= \beta_2 v_{t-1} + (1-\beta_2)g^2_t\\ \hat{m}_t&=\frac{m_{t-1}}{1-{\beta}^{t-1}_1} \\ \hat{v}_t&=\frac{v_{t-1}}{1-{\beta}^{t-1}_2} \\ {w}_{t+1}&={w}_t-\frac{\eta}{\sqrt{\hat{v_t}}+\epsilon}m_t \\ \end{aligned} \] 整个过程可以分解为如下的步骤：
首先\(m_t\)与\(v_t\)分别表示对梯度以及梯度的平方进行滑动平均，使得每次的更新都与历史值相关。之后的\(\hat{m}_t\)与\(\hat{v}_t\)是对初期滑动平均偏差较大的一个修正，叫做 bias correction，当\(t\)越来越大时，\(1−β^t_1\)和\(1−β^t_2\) 都趋近于 1，这时 bias correction 的任务也就完成了。之后对参数进行更新，更新方式就和最后一行表示的相同。这里每轮的学习率都是变化的，与\(\hat{v}_t\)相关，同时更新使用的不是梯度\(g\)而是\(m\)，有类似于Momentum的思想。