首页课程笔记自动化系凸优化

# Vanilla Gradient Descent（基本梯度下降）

  1. 基本思想

    基本梯度下降算法遵循的思想是：梯度的相反方向指向较低的区域。所以它在梯度的相反方向迭代。

    更新公式

    对于每个参数 θ\theta，更新公式为：

    θ←θ−η⋅∇J(θ)\theta \leftarrow \theta - \eta \cdot \nabla J(\theta)

    其中：

    • η\eta 是学习率（learning rate）
    • ∇J(θ)\nabla J(\theta) 是目标函数 JJ 关于参数 θ\theta 的梯度

    特点：

    • 算法简单直观
    • 每次迭代只考虑当前梯度
    • 可能收敛较慢，特别是在条件数大的问题上
    • 可能产生锯齿形路径

# Momentum（动量）

  1. 基本思想

    带有动量的梯度下降算法（简称动量）借鉴了物理学的思想。想象一下在无摩擦的碗里滚动一个球。没有在底部停止，而是积累的动量推动它前进，球继续前后滚动。

    更新公式

    在每个步骤中，除了常规的梯度之外，它还考虑了前一步中的移动：

    m←γ⋅m+η⋅∇J(θ)θ←θ−m\begin{aligned} m &\leftarrow \gamma \cdot m + \eta \cdot \nabla J(\theta) \\ \theta &\leftarrow \theta - m \end{aligned}

    其中：

    • mm 是动量项（momentum）
    • γ\gamma 是衰减率（decay rate），通常取 0.9
    • η\eta 是学习率

    叠加模式

    也可以写成叠加模式：

    sum_of_gradient=gradient+previous_sum_of_gradient×decay_ratedelta=−learning_rate×sum_of_gradientθ←θ+delta\begin{aligned} \text{sum\_of\_gradient} &= \text{gradient} + \text{previous\_sum\_of\_gradient} \times \text{decay\_rate} \\ \text{delta} &= -\text{learning\_rate} \times \text{sum\_of\_gradient} \\ \theta &\leftarrow \theta + \text{delta} \end{aligned}

  2. 优势

    动量比基本梯度下降有两个优点：

    • 移动更快：因为它积累的所有动量，使得算法在一致方向上加速
    • 逃脱局部极小值：动量可能推动它脱离局部极小值
    • 通过高原区：能够更好地通过平坦区域（高原区）

  3. 可视化解释

    在可视化中，动量方法会"记住"之前的移动方向，在一致方向上加速，在相反方向上减速。

# Nesterov Accelerated Gradient（Nesterov 加速梯度）

  1. 基本思想

    NAG（Nesterov Accelerated Gradient）是 Momentum 的改进，在梯度更新时做一个矫正。

    更新公式

    m←γ⋅m+η⋅∇J(θ−γ⋅m)θ←θ−m\begin{aligned} m &\leftarrow \gamma \cdot m + \eta \cdot \nabla J(\theta - \gamma \cdot m) \\ \theta &\leftarrow \theta - m \end{aligned}

    其中 semi_gradient 取的是 (θ−decay_rate×old_delta)(\theta - \text{decay\_rate} \times \text{old\_delta}) 处的函数梯度。

  2. 直观解释

    Momentum 的行为：

    • 首先计算一个梯度（短的蓝色向量）
    • 然后在加速更新梯度的方向进行一个大的跳跃（长的蓝色向量）

    NAG 的行为：

    • 首先在之前加速的梯度方向进行一个大的跳跃（棕色向量）
    • 计算梯度然后进行校正（绿色梯度向量）

    这相当于"往前看"一步，利用未来位置的信息。

  3. 等效形式

    可以对 NAG 原来的更新公式进行变换，得到等效形式：

    di=βdi−1+g(θi−1)+β[g(θi−1)−g(θi−2)]θi=θi−1−αdi\begin{aligned} d_i &= \beta d_{i-1} + g(\theta_{i-1}) + \beta[g(\theta_{i-1}) - g(\theta_{i-2})] \\ \theta_i &= \theta_{i-1} - \alpha d_i \end{aligned}

    其中 β\beta 是衰减率，α\alpha 是学习率，g(θ)g(\theta) 是梯度。

  4. 与 Momentum 的区别

    这个 NAG 的等效形式与 Momentum 的区别在于，本次更新方向多加了一个 β[g(θi−1)−g(θi−2)]\beta[g(\theta_{i-1}) - g(\theta_{i-2})]，它的直观含义是：

    • 能够让算法提前看到前方的地形梯度
    • 如果前面的梯度比当前位置的梯度大，那我就可以把步子迈得比原来大一些
    • 如果前面的梯度比现在的梯度小，那我就可以把步子迈得小一些
    • 这个大一些、小一些，都是相对于原来不看前方梯度、只看当前位置梯度的情况来说的

    本质：NAG 本质上是多考虑了目标函数的二阶导信息，可以加速收敛！比喻起来是说"往前看"，数学本质上则是利用了目标函数的二阶导信息。

# AdaGrad（自适应梯度）

  1. 基本思想

    Adaptive Gradient 算法（简称 AdaGrad）不是像动量一样跟踪梯度之和，而是跟踪梯度平方之和，并使用这种方法在不同的方向上调整梯度。

    更新公式

    对于每个维度：

    s←s+∇J(θ)⊙∇J(θ)θ←θ−ηs+ε⊙∇J(θ)\begin{aligned} s &\leftarrow s + \nabla J(\theta) \odot \nabla J(\theta) \\ \theta &\leftarrow \theta - \frac{\eta}{\sqrt{s + \varepsilon}} \odot \nabla J(\theta) \end{aligned}

    其中：

    • ss 是梯度平方的累积和
    • ⊙\odot 表示逐元素相乘（Hadamard 积）
    • ε\varepsilon 是一个小常数（如 10−810^{-8}），防止除零

  2. 解决的问题

    在机器学习优化中，一些特征是非常稀疏的。稀疏特征的平均梯度通常很小，所以这些特征的训练速度要慢得多。

    解决思路：

    • 你已经更新的特征越多，你将来更新的就越少
    • 这样就有机会让其它特征（例如稀疏特征）赶上来
    • 为每个特征设置不同的学习率，自适应调整

  3. 可视化解释

    用可视化的术语来说，更新这个特征的程度即在这个维度中移动了多少，这个概念由梯度平方的累积和表达。

    • 基本梯度让球走直角移动
    • 如果 AdaGrad 调整合适，球会沿对角线方向移动
    • AdaGrad 将采取直线路径，而梯度下降（或相关的动量）采取的方法是"让我先滑下陡峭的斜坡，然后才可能担心较慢的方向"

    优势：

    • 更好地避开鞍点
    • 有时候，原版梯度下降可能非常满足的仅仅停留在鞍点，那里两个方向的梯度都是 0
    • AdaGrad 能够自适应地调整不同方向的学习率

  4. 问题

    AdaGrad 的问题在于它非常慢。这是因为梯度的平方和只会增加而不会减小，导致学习率越来越小，最终可能变得极小。

# RMSProp（均方根传播）

  1. 基本思想

    RMSProp（Root Mean Square Propagation）通过添加衰减因子来修复 AdaGrad 的问题。

    更新公式

    s←γ⋅s+(1−γ)⋅∇J(θ)⊙∇J(θ)θ←θ−ηs+ε⊙∇J(θ)\begin{aligned} s &\leftarrow \gamma \cdot s + (1-\gamma) \cdot \nabla J(\theta) \odot \nabla J(\theta) \\ \theta &\leftarrow \theta - \frac{\eta}{\sqrt{s + \varepsilon}} \odot \nabla J(\theta) \end{aligned}

    其中：

    • γ\gamma 是衰减率（decay rate），通常设置为 0.9
    • (1−γ)(1-\gamma) 是当前梯度的权重

  2. 衰减因子的作用

    衰减率表明只是最近的梯度平方有意义，而很久以前的梯度基本上会被遗忘。

    与动量的区别：

    • 与我们在动量中看到的衰减率不同，除了衰减之外，这里的衰减率还有一个缩放效应
    • 它以一个因子 (1−衰减率)(1 - \text{衰减率}) 向下缩放整个项
    • 如果衰减率设置为 0.99，除了衰减之外，梯度的平方和将是 1−0.99=0.1\sqrt{1-0.99} = 0.1
    • 因此对于相同的学习率，这一步大 10 倍

  3. 与 AdaGrad 的对比

    • AdaGrad（白色）最初与 RMSProp（绿色）差不多，正如调整学习率和衰减率的预期
    • 但是 AdaGrad 的梯度平方和累计得非常快，以至于它们很快变得非常巨大
    • RMSProp 通过衰减机制避免了这个问题，使得学习率不会无限减小

# Adam（自适应矩估计）

  1. 基本思想

    Adam（Adaptive Moment Estimation）同时兼顾了动量和 RMSProp 的优点。Adam 在实践中效果很好，因此在最近几年，它是深度学习问题的常用选择。

    更新公式

    m←β1⋅m+(1−β1)⋅∇J(θ)[Momentum]s←β2⋅s+(1−β2)⋅∇J(θ)⊙∇J(θ)[RMSProp]m^←m1−β1ts^←s1−β2tθ←θ−ηs^+ε⊙m^\begin{aligned} m &\leftarrow \beta_1 \cdot m + (1-\beta_1) \cdot \nabla J(\theta) \quad \text{[Momentum]} \\ s &\leftarrow \beta_2 \cdot s + (1-\beta_2) \cdot \nabla J(\theta) \odot \nabla J(\theta) \quad \text{[RMSProp]} \\ \hat{m} &\leftarrow \frac{m}{1-\beta_1^t} \\ \hat{s} &\leftarrow \frac{s}{1-\beta_2^t} \\ \theta &\leftarrow \theta - \frac{\eta}{\sqrt{\hat{s} + \varepsilon}} \odot \hat{m} \end{aligned}

    其中：

    • β1\beta_1 是一阶矩梯度之和（动量之和）的衰减率，通常设置为 0.9
    • β2\beta_2 是二阶矩梯度平方和的衰减率，通常设置为 0.999
    • tt 是迭代次数
    • ε\varepsilon 是超参数，建议值是 10−810^{-8}

  2. 偏差修正

    可以看到前两项和 Momentum 和 RMSProp 是非常一致的。由于和的初始值一般设置为 0，在训练初期其可能较小，第三和第四项主要是为了放大它们（偏差修正，bias correction）。

    • m^=m1−β1t\hat{m} = \frac{m}{1-\beta_1^t}：修正一阶矩的偏差
    • s^=s1−β2t\hat{s} = \frac{s}{1-\beta_2^t}：修正二阶矩的偏差

  3. 算法特点

    优点：

    • 结合了动量和自适应学习率的优点
    • 在实践中表现优异
    • 对超参数选择相对鲁棒
    • 能够处理稀疏梯度和非平稳目标

    超参数：

    • 超参数越来越多，研究近似炼丹
    • 但 Adam 的默认超参数通常工作良好

  4. 可视化表现

    在一个表面上动画演示 5 个梯度下降法：

    • 梯度下降（青色）
    • Momentum（洋红色）
    • AdaGrad（白色）
    • RMSProp（绿色）
    • Adam（蓝色）

    关键观察：

    • 左坑是全局极小值，右坑是局部极小值
    • 在下面图中有两座小山阻挡了通往全局极小值的道路
    • Adam 是上述算法中，唯一能够找到通往全局极小值的算法
    • Adam 能够更好地处理复杂的优化地形，包括鞍点和局部极小值

  5. 算法比较总结

    算法 特点 优势 劣势
    Vanilla GD 基本梯度下降 简单 收敛慢，可能陷入局部最优
    Momentum 引入动量 加速收敛，可能逃脱局部最优 可能振荡
    NAG Momentum 改进 提前"看"梯度，加速收敛 计算稍复杂
    AdaGrad 自适应学习率 处理稀疏特征，避开鞍点 学习率衰减过快
    RMSProp 衰减梯度平方 解决 AdaGrad 问题 需要调衰减率
    Adam 结合动量和自适应 综合性能最好 超参数较多