首页 计算机科学 机器学习

# 梯度下降法的概念

\quad 对于一个线性回归的损失函数 L(w,b)L(w,b)，我们希望找到它的最小值 min⁡w,bL(w,b)\min_{w,b}L(w,b)。而梯度下降就是一种可用于尝试任何函数最小化的算法，这不仅仅局限与线性回归的损失函数。
\quad 梯度下降法是一种常用的一阶 (first-order) 优化方法，是求解无约束优化问题最简单、最经典的方法之一。考虑一个无约束优化问题 min⁡xf(x)\min_xf(x)，其中 f(x)f(x) 为连续可微函数，如果能够构造一个序列 xx,x1,x2,⋯x_x,x_1,x_2,\cdots 并能够满足 f(xt+1)<f(xt),t=0,1,2,⋯f(x_{t+1})<f(x_t),\ t=0,1,2,\cdots。那么我们就能够不断执行该过程即可收敛到局部极小点，可参考下图。

\quad 那么这个问题的关键就在于：下一个 xt+1x_{t+1} 是从上一个 xtx_t 沿着哪一个方向走一小步 Δx\Delta x 得到的？

\quad 对于一元函数来说，xx 自会有两个走向：要么是正方向 (Δx>0)(\Delta x>0)，要么是负方向 (Δx<0)(\Delta x<0)。判断应该往哪个方向走其实很简单，利用在该点的导数，即梯度，就可以了。若该点的导数 f′(xt)>0f'(x_t)>0，说明正方向是使得函数值增大的方向，则应该往负方向走；反之，则相反。因此，我们可以令走的步长为：

Δx=−ηf′(x);(η>0)(1)\Delta x = -\eta f'(x);\quad(\eta>0) \tag{1}

其中 f′(x)f'(x) 是该点的导数值。而 η\eta 是一个大于零的小量，这是一个很重要的量，我们称它为学习率。
\quad 这一方法也很容易进行高维推广，例如二元函数 f(x1,x2)f(x_1,x_2)。我们可以将它两个方向进行梯度下降，下降的步长为：

Δx1=−η∂f∂x1;Δx2=−η∂f∂x2(2)\Delta x_1 = -\eta \frac{\partial f}{\partial x_1};\quad\Delta x_2 = -\eta \frac{\partial f}{\partial x_2} \tag{2}

# 梯度下降法会遇到的问题

\quad 梯度下降法是一种简单的、经典的最优化算法。但这并不会说明它是完美的，它会遇到如下的问题：

  1. 运用梯度下降法要选择初始点与学习率。这个过程本就具有随机性与不确定性，一个函数的极小值点也许有很大。却决于初始点和学习率的不同，梯度下降法也许会收敛到不同的极小值点，而这些极小值点不一定是最小点。这一问题在一元函数就会遇到，推广到高维那么就会更棘手了。

  1. 学习率的选择很重要。学习率太大，会导致步长太大，也许就无法收敛到极小值点；学习率太小，步长太短，收敛速度就会太慢，并且也许会收敛到一个不想要的 “小坑” 里面无法爬出来，而不能收敛到想要的最小值。过大或过小的学习率都会影响算法的效率，因此学习率可以作为超参数由人为指定，也可以在搜索过程中由算法本身自适应调节。

# 梯度下降法的改进

# 自适应学习率的 Bold Driver 方法

\quad 自适应学习率的 Bold Driver 方法的操作很简单，就是将函数 f(xt)f(x_t) 与其之前的值 f(xt−1)f(x_{t-1}) 进行比较：

  1. 若函数值的确减小了，则将学习率 η\eta 增加一小部分（通常为 1%∼5%1\%\sim 5\%）；
  2. 若函数值是增加了，则撤销最后一步 xtx_t 的移动，并大幅减小 η\eta（通常减小 50%50\%）。

该方法实现了自适应学习率调节：在梯度下降取得成功时会尝试更大的步伐试探；如果失败，则自己可能走在错误的相反斜率上（意味着函数可能已经到达了一个棘手的区域），此时就大幅度减小步长以进行更保守的试探。

\quad 该方法即为有效。但在函数包含大量噪声的时候容易失效（容易钻到某个微小谷中无法跳出）。

# 淬火学习率调整法

\quad 在函数包含大量噪声时，可以考虑采用淬火学习率调整法，学习率随迭代次数如下变换：

η=η01+n/N(3)\eta = \frac{\eta_0}{1+n/N} \tag{3}

其中 nn 为已迭代的次数。NN 是设置的一个较大值。该算法的特点是：在初始附近的步骤保持几乎不变的学习率，随着算法进行到 NN 后显著减小学习率。

# 市场上相对成熟的梯度下降算法

  1. Nesterov accelerated gradient\text{Nesterov\ accelerated\ gradient}：提前使用下一点的梯度。
  2. Adapgrad\text{Adapgrad}：存储在各个方向上震荡的历史积累，并以此作为震荡抑制，但容易抑制过度。
  3. momentum\text{momentum}：为梯度下降引入一个惯性，即r⃗t+1=r⃗t−ηf′(r⃗t)+γ(r⃗t−r⃗t−1)\vec{r}_{t+1}=\vec{r}_t-\eta f'(\vec{r}_t)+\gamma(\vec{r}_t-\vec{r}_{t-1})，有助于减缓收敛过程出现的振荡，并且可以冲出局部最优解。
  4. Adapgrad\text{Adapgrad}：存储在各个方向上震荡的历史积累，并以此作为震荡抑制，但容易抑制过度。
  5. RMsProp\text{RMsProp}：相比 grad_squared 加了一个 decay ，让阻力不太过分。
  6. Adam\text{Adam}：整合了 momentum 派系以及阻力派系。
    ......