【科普】一阶凸优化算法归纳

kirin77 · 发表于 2022-2-22 14:13

本文章内容参考自Stanford的深度学习课程CS231n，参考链接见文章底部。

Greeting!
凸优化问题指的是在定义域内具有全局最优解的问题，数理定义就省略了。那么显然现有的优化问题求解是以凸优化算法为基础的，具有奠定基石的意义。对于非凸优化问题，其实也是通过将其以凸优化的思路来求解或近似求解（类似于用线性回归的方法解决非线性回归的问题）。曾经有大佬说过：“目前对于这些非凸优化问题取得的算法理论方面的突破大体其实归结于找到这些非凸优化问题中‘凸’的结构”。因此，本文主要关注于最基础的一阶凸优化算法的总结，因为这些算法最基础，最实用，同时也是最重要的。

Vanilla update

从最简单的形式说起，称为Vanilla update：朝着梯度的负方向进行更新。设参数为和梯度为 $dx$ ，则有：
# Vanilla update
x += - learning_rate * dx其中，learning rate是学习率，它是一个固定常数。

Momentum update

动量法（Momentum update）：该方法从物理角度上看待最优化问题，它认为梯度只是影响速度，然后速度再影响位置，这个理解与随机梯度下降（SDG）不同，在SGD中，梯度影响位置。
# Momentum update
v = mu * v - learning_rate * dx # integrate velocity
x += v # integrate position其中， $v$ 是初始化为0的变量，可以理解为速度； $mu$ 是一个额外的超参数，有时被称为“动量”，但从物理上可以理解为摩擦系数，它决定了抑制速度/动能的快慢。交叉验证时，此参数通常设置为 [0.5, 0.9, 0.95, 0.99] 等值。动量在学习的后期阶段可不断增加，一个典型的设置是从大约从 0.5 开始，并逐渐将其退火到 0.99 左右。

Nesterov Momentum update

牛顿动量法（Nesterov Momentum update）：这个基本上就是动量法的一种变体，它对凸函数有更强的理论收敛保证，并且在实践中它也始终比标准动量法略好。
它的核心思路是：计算 $x + mu * v$ 位置的梯度而不是 $x$ 位置的梯度，如下图所示

x_ahead = x + mu * v
# evaluate d(x_ahead) (the gradient at x_ahead instead of at x)
v = mu * v - learning_rate * dx_ahead
x += v然而这里需要计算 d(x_ahead)。在实践中，人们更愿意将更新表达与动量法相同的形式，因此则变为如下代码（注意 x_ahead 重新命名为 x ，详细推导见链接）：
v_prev = v # back this up
v = mu * v - learning_rate * dx # velocity update stays the same
x += -mu * v_prev + (1 + mu) * v # position update changes form 其中，第二行更新速度 $v$ 的格式与动量法保持一致，而第三行更新的代码格式相当提前抵达“lookahead”位置进行计算，因而更快收敛。
<hr/>在上面的算法中，我们平均地全局地使用了固定学习率来处理所有参数。调整学习率是一个昂贵的步骤，有很多算法可以自适应地调整学习率，即接收高梯度的权重将降低其有效学习率，而接收小或不频繁更新的权重将提高其有效学习率。这类算法称为自适应学习率算法（adaptive learning rate method）。

Adagrad

AdaGrad算法（Adaptive Subgradient Methods）是Duchi等人最初提出的一种自适应学习率算法：
# AdaGrad
cache += dx**2
x += -learning_rate * dx / (np.sqrt(cache) + eps)其中，变量cache是向量，它的长度等于梯度的数量，并跟踪每个参数的梯度平方和。有趣的是，平方根运算非常重要，没有它，算法的性能会更差。平滑项eps（通常设置在 1e-4 到 1e-8 的范围内）避免被零除。Adagrad 的一个缺点是，在深度学习的情况下，单调的学习率通常过于激进并且过早停止学习。

RMSprop

RMSprop算法（Root Mean Square prop）源于 Geoff Hinton 的 Coursera 课程第 6 讲PPT的第29页，此算法以一种非常简单的方式调整 Adagrad 方法，试图降低其激进的、单调递减的学习率。特别是，它使用平方梯度的滑动平均，给出：
# RMSProp
cache = decay_rate * cache + (1 - decay_rate) * dx**2
x += - learning_rate * dx / (np.sqrt(cache) + eps)其中，decay_rate是一个超参数，典型值为 [0.9, 0.99, 0.999]。RMSProp仍然是基于梯度的大小来对每个权重的学习率进行修改，与 Adagrad 不同的是，学习率不会单调变小。

Adam

Adam算法的本质是RMSProp + Momentum，简化的代码如下所示：
# Adam
m = beta1 * m + (1-beta1) * dx
v = beta2 * v + (1-beta2) * (dx**2)
x += - learning_rate * m / (np.sqrt(v) + eps)其中，Adam算法与 RMSProp 更新类似，除了使用“平滑”版本的梯度 m 而不是原始的梯度向量 dx 。论文中的推荐值为eps = 1e-8，beta1 = 0.9，beta2 = 0.999。
完整的 Adam 更新还包括一个偏置（bias）矫正机制，因为 m, v 两个矩阵初始为0，在没有完全热身之前存在偏差，需要采取一些补偿措施。使用偏差校正机制的代码如下所示：
# t is your iteration counter going from 1 to infinity
m = beta1 * m + (1-beta1) * dx
mt = m / (1-beta1**t)
v = beta2 * v + (1-beta2) * (dx**2)
vt = v / (1-beta2**t)
x += - learning_rate * mt / (np.sqrt(vt) + eps)在实践中，目前建议使用 Adam 作为默认算法，并且通常比 RMSProp 稍微好一点。但是，通常也值得尝试使用 SGD+Nesterov Momentum 作为替代方案。

最后推荐一下CS231n课程：深度网络参数的优化目前是一个非常活跃的研究领域。实践中使用反向传播算法计算出梯度用于执行参数的更新。而这个参数最优问题的本质就是一个凸优化问题。这些都可以在CS231n课件中找到相关的内容。
除此以外，CS231n课件中还有一些进行深度学习前或深度学习时的一些注意事项（Gradient Checks、Sanity Checks、Babysitting the learning process: Tips/Tricks），值得反复学习！
参考链接：https://cs231n.github.io/neural-networks-3/#anneal

		自动登录	找回密码
密码			立即注册

【科普】一阶凸优化算法归纳

本帖子中包含更多资源