无约束优化2022-08-27

符号定义

$n$ ：训练样本数目
$\mathbf{x}$ ：训练样本
$y$ ：label
$\mathbf{w}$ ：参数向量
$L$ $L = \frac{1}{n} \sum_{i=1}^n (\mathbf{w \cdot x}_i - y_i)^2$
$L_i$ $i$ $L_i = (\mathbf{w \cdot x}_i - y_i)^2$
$t$ ：时间步
$g_t$ $损失函数关于$ $t$ 个时间步的参数的梯度，以平方损失函数为例
$\begin{matrix} (1) & \begin{aligned} g_{t} & = g (w_{t}) \\ = \frac{\partial L}{\partial w_{t}} \\ = \frac{1}{n} \sum_{i = 1}^{n} 2 x_{i} (w_{t} {\cdot x}_{i} - y_{i}) \end{aligned} \end{matrix}$
$\nabla f$ $f$ 的梯度

方向导数

方向导数定义

$z=f(x,y)$ $(x_0,y_0)$ $\vec{l} = (\cos \alpha, \cos \beta)$ $\lim \limits_{t \rightarrow 0} \frac{f(x_0 + t \cos \alpha, y_0 + t \cos \beta) - f(x_0, y_0)}{t}$ $f(x,y)$ $(x_0, y_0)$ $\vec l$ $\left.\begin{matrix} \frac{\partial f}{\partial \vec l} \end{matrix}\right|_{(x_0, y_0)}$

$f(x,y)$ $\left.\begin{matrix} \frac{\partial f}{\partial \vec l} \end{matrix}\right|_{(x_0, y_0)} = {f}'_x(x_0, y_0) \cdot \cos \alpha + {f}'_y(x_0, y_0) \cdot \cos \beta$

陷阱：上述公式仅限于可微前提下，若不可微，必须回归方向导数的定义。

方向导数与偏导数的关系

方向导数定义：

\begin{matrix} (2) & lim_{t \to 0} \frac{f (x_{0} + t \cos α, y_{0} + t \cos β) - f (x_{0}, y_{0})}{t} \end{matrix}

偏导数定义：

\begin{matrix} (3) & f_{x}^{'} = lim_{Δ x \to 0} \frac{f (x_{0} + Δ x, y_{0}) - f (x_{0}, y_{0})}{Δ x} f_{y}^{'} = lim_{Δ y \to 0} \frac{f (x_{0}, y_{0} + Δ y) - f (x_{0}, y_{0})}{Δ y} \end{matrix}

所以：

\begin{matrix} (4) & \begin{matrix} 当 \vec{l} = (1, 0) 时 ， 方 向 导 数 = lim_{t \to 0} \frac{f (x_{0} + t, y_{0}) - f (x_{0}, y_{0})}{t} = f_{x}^{'} \\ 当 \vec{l} = (0, 1) 时 ， 方 向 导 数 = lim_{t \to 0} \frac{f (x_{0}, y_{0} + t) - f (x_{0}, y_{0})}{t} = f_{y}^{'} \end{matrix} \end{matrix}

结论：

\begin{matrix} (5) & f_{x}^{'} 是 沿 (1, 0) 方 向 的 方 向 导 数 ， f_{y}^{'} 是 沿 (0, 1) 方 向 的 方 向 导 数 。 \end{matrix}

梯度

$z=f(x,y)$ $(x_0, y_0)$ 处可微，梯度定义如下：

\begin{matrix} (6) & \nabla f = grad f = (\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}) = \frac{\partial f}{\partial x} \cdot \vec{i} + \frac{\partial f}{\partial y} \cdot \vec{j} \end{matrix}

梯度与方向导数的关系

$f(x,y)$ 可微的前提下：

\begin{matrix} (7) & \begin{aligned} {\begin{array}{c} \frac{\partial f}{\partial \vec{l}} \end{array} |}_{(x_{0}, y_{0})} & = f_{x}^{'} (x_{0}, y_{0}) \cdot \cos α + f_{y}^{'} (x_{0}, y_{0}) \cdot \cos β \\ = \vec{grad} f \cdot \vec{l} \\ = | \vec{grad} f | \cdot | \vec{l} | \cdot \cos θ \\ 其 中 ， & θ 为 \vec{grad} f 与 \vec{l} 之 间 的 夹 角 \end{aligned} \end{matrix}

$(x_0, y_0)$ 的邻域内沿梯度方向函数增加最快，沿负梯度方向函数减小最快。

梯度与等高线的关系

结论：梯度垂直于等高线的切线。

梯度下降法

$L(w)$ ，优化目标为：

\begin{matrix} (8) & m i n L (w) \end{matrix}

则使用梯度下降法求解的步骤为：

\begin{matrix} (9) & \begin{aligned} w_{t} & = w_{t - 1} - l r * \frac{\partial L}{\partial w_{t - 1}} \\ = w_{t - 1} - l r * g (w_{t - 1}) \\ = w_{t - 1} - l r * g_{t - 1} \end{aligned} \end{matrix}

$n$ $x$ $y$ $wx$ $L(w) = \sum_{i=0}^n(wx-y)^2$ ，那么，参数的更新公式为：

\begin{matrix} (10) & \begin{aligned} w_{t} & = w_{t - 1} - l r * \frac{\partial L}{\partial w_{t - 1}} \\ = w_{t - 1} - l r * (\sum_{i = 0}^{n} 2 x (w_{t - 1} x - y)) \end{aligned} \end{matrix}

$O(n)$ 。

随机梯度下降法

$O(n)$ $O(1)$ 。

小批量梯度下降法

$B$ $O(B)$ 。

梯度下降算法的缺点

下降速度慢
可能会在沟壑两边持续震荡，停留在一个局部最优点

动量法

\begin{matrix} (11) & \begin{aligned} v_{t} & = γ v_{t - 1} + η * g (w_{t - 1}) \\ w_{t} & = w_{t - 1} - v_{t} \\ 其 中 ， & v 为 一 阶 动 量 ， γ 为 超 参 数 ， \\ g 为 损 失 函 数 的 一 阶 梯 度 ， η 为 学 习 率 \end{aligned} \end{matrix}

假设起始点为A，起始点的动量初始化为0：

A -> B：方向为点A的负梯度方向
B -> C：方向为点B的负梯度方向+点A的梯度方向

NAG(Nesterov Accelerated Gradient)

\begin{matrix} (12) & \begin{aligned} g_{t - 1} & = g (w_{t - 1} - γ v_{t - 1}) \\ v_{t} & = γ v_{t - 1} + η * g_{t - 1} \\ w_{t} & = w_{t - 1} - v_{t} \\ 其 中 ， & v 为 一 阶 动 量 ， γ 为 超 参 数 ， \\ g 为 损 失 函 数 的 一 阶 梯 度 ， η 为 学 习 率 \end{aligned} \end{matrix}

牛顿法

零点求解

$f(x) = 0$

迭代步骤：

\begin{matrix} (13) & \begin{aligned} 1. 初 始 点 (x_{0}, y_{0}) \\ 2. 过 (x_{0}, y_{0}) 点 做 f (x) 的 切 线 方 程 ， 则 方 程 为 \frac{y - f (x_{0})}{x - x_{0}} = f^{'} (x_{0}) ， 化 简 得 ： \\ y = f (x_{0}) + f^{'} (x_{0}) (x - x_{0}) \\ 3. 求 切 线 与 x 轴 的 交 点 ： x_{1} = x_{0} - \frac{f (x_{0})}{f^{'} (x_{0})} \\ 4. 由 此 ， 得 到 迭 代 公 式 ： x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})} \\ 5. 按 照 迭 代 公 式 进 行 迭 代 ， 直 到 满 足 阈 值 要 求 \end{aligned} \end{matrix}

牛顿迭代法执行步骤示例：

牛顿法

$L(w)$ ，优化目标为：

\begin{matrix} (14) & m i n L (w) \end{matrix}

$L(w)$ $L(w)$ ${L}'(w)=0$ 的点。

$g(x) = {L}'(w)$ $g(x)=0$ 的点，则迭代公式为：

\begin{matrix} (15) & \begin{aligned} x_{n + 1} & = x_{n} - \frac{g (x_{n})}{g^{'} (x_{n})} \\ = x_{n} - \frac{f^{'} (x_{n})}{f^{″} (x_{n})} \end{aligned} \end{matrix}

AdaGrad

$t=0$ $s_0$ 中的每个元素都初始化为0

$t$ $g(w_{t-1})$ $s_t$ ：

\begin{matrix} (16) & \begin{matrix} s_{t} = s_{t - 1} + g (w_{t - 1}) ⊙ g (w_{t - 1}) \\ 其 中 ， ⊙ 是 按 元 素 相 乘 \end{matrix} \end{matrix}

将目标函数自变量中每个元素的学习率通过按元素运算重新调整：

\begin{matrix} (17) & \begin{matrix} w_{t} = w_{t - 1} - \frac{η}{\sqrt{s_{t} + ϵ}} ⊙ g (w_{t - 1}) \\ 其 中 ， η 是 学 习 率 ， ϵ 是 为 了 维 持 数 值 稳 定 性 而 添 加 的 常 数 ， 如 10^{- 6} \end{matrix} \end{matrix}

$s_t$ 一直在累加按元素平方的小批量随机梯度，所以目标函数自变量每个元素的学习率在迭代过程中一直在降低（或不变）。因此，当学习率在迭代早期降得较快且当前解依然不佳时，AdaGrad算法在迭代后期由于学习率过小，可能较难找到一个有用的解。

RMSProp

$t \gt 0$ 时，

\begin{matrix} (18) & \begin{matrix} s_{t} = γ s_{t - 1} + (1 - γ) g_{t - 1} ⊙ g_{t - 1} \\ w_{t} = w_{t - 1} - \frac{η}{\sqrt{s_{t} + ϵ}} ⊙ g (w_{t - 1}) \\ 其 中 ， γ 为 超 参 数 ， 0 \leq γ < 1 \\ η 为 学 习 率 \\ ϵ 是 为 了 维 持 数 值 稳 定 性 而 添 加 的 常 数 ， 如 10^{- 6} \end{matrix} \end{matrix}

$s_t$ $g(w_{t-1}) \odot g(w_{t-1})$ $1/(1-\gamma)$ 个时间步的小批量随机梯度平方项的加权平均。因此，自变量每个元素的学习率在迭代过程中就不再一直降低（或不变）。

AdaDelta

$t=0$ $s_t$ $\Delta w_t$ 所有元素被初始化为0

$t \gt 0$ 时：

\begin{matrix} (19) & s_{t} = ρ s_{t - 1} + (1 - ρ) g (w_{t - 1}) ⊙ g (w_{t - 1}) \end{matrix}

计算自变量的变化量：

\begin{matrix} (20) & \begin{matrix} g_{t}^{^{'}} = \sqrt{\frac{Δ w_{t - 1} + ϵ}{s_{t} + ϵ}} ⊙ g (w_{t - 1}) \\ 其 中 ， ϵ 是 为 了 维 持 数 值 稳 定 性 而 添 加 的 常 数 ， 如 10^{- 5} \end{matrix} \end{matrix}

更新自变量：

\begin{matrix} (21) & w_{t} = w_{t - 1} - g_{t}^{^{'}} \end{matrix}

$\Delta w_t$ $g^{'}_t$ 按元素平方的指数加权移动平均：

\begin{matrix} (22) & Δ w_{t} = ρ Δ w_{t - 1} + (1 - ρ) g_{t}^{^{'}} ⊙ g_{t}^{^{'}} \end{matrix}

$\epsilon$ $\sqrt{\Delta w_{t-1}}$ $\eta$ 。

Adam

Adam = Adaptive+Momentum

$t=0$ $v_t$ $s_t$ 初始化为0

$t \gt 0$ ，

\begin{matrix} (23) & \begin{aligned} v_{t} & = β_{1} v_{t - 1} + (1 - β_{1}) g (w_{t - 1}) \\ s_{t} & = β_{2} s_{t - 1} + (1 - β_{2}) g (w_{t - 1}) ⊙ g (w_{t - 1}) \\ 其 中 ， β_{1} 和 β_{2} 为 超 参 数 \\ 0 \leq β_{1} < 1 ， 建 议 为 0.9 \\ 0 \leq β_{2} < 1 ， 建 议 为 0.999 \end{aligned} \end{matrix}

无偏修正：

\begin{matrix} (24) & \begin{matrix} {\hat{v}}_{t} = \frac{v_{t}}{1 - β_{1}^{t}} \\ {\hat{s}}_{t} = \frac{s_{t}}{1 - β_{2}^{t}} \end{matrix} \end{matrix}

更新参数：

\begin{matrix} (25) & w_{t} = w_{t - 1} - \frac{η {\hat{v}}_{t}}{\sqrt{{\hat{s}}_{t} + ϵ}} \end{matrix}

NAdam

NAG回顾与改写

回顾NAG的公式：

\begin{matrix} (26) & \begin{aligned} g_{t - 1} & = g (w_{t - 1} - γ v_{t - 1}) \\ v_{t - 1} & = γ v_{t - 2} + η * g_{t - 1} \\ w_{t} & = w_{t - 1} - v_{t - 1} \\ 其 中 ， & v 为 一 阶 动 量 ， γ 为 超 参 数 ， \\ g 为 损 失 函 数 的 一 阶 梯 度 ， η 为 学 习 率 \end{aligned} \end{matrix}

$\left \lfloor 未来位置 \right \rceil ： w_{t-1} - \gamma v_{t-1}$ $\left \lfloor 未来位置 \right \rceil$ $g_{t-1} = g(w_{t-1})$ $w_t$ $w_t = w_{t-1} \; - \; v_{t}$ ，那么理论上所达到的效果是类似的。

理论上，下一刻的动量为：

\begin{matrix} (27) & v_{t} = γ v_{t - 1} + η * g_{t} \end{matrix}

在假定连续两次的梯度变化不大的情况下，那么：

\begin{matrix} (28) & \begin{aligned} g_{t} & \approx g_{t - 1} \\ v_{t} & = γ v_{t - 1} + η * g_{t} \\ \approx γ v_{t - 1} + η * g_{t - 1} \\ = {\bar{v}}_{t} \end{aligned} \end{matrix}

$\bar{v}_t$ $w$ 的迭代公式中。

因此，原始NAG的公式可以修改为：

\begin{matrix} (29) & \begin{aligned} g_{t - 1} & = g (w_{t - 1}) \\ v_{t - 1} & = γ v_{t - 2} + η * g_{t - 1} \\ {\bar{v}}_{t} & = γ v_{t - 1} + η * g_{t - 1} \\ w_{t} & = w_{t - 1} - {\bar{v}}_{t} \\ 其 中 ， & v 为 一 阶 动 量 ， γ 为 超 参 数 ， \\ g 为 损 失 函 数 的 一 阶 梯 度 ， η 为 学 习 率 \end{aligned} \end{matrix}

NAdam

$\hat{v}_t \to \bar{v}_t$ $\hat{v}_t$ 展开有：

\begin{matrix} (30) & \begin{aligned} {\hat{v}}_{t} & = \frac{v_{t}}{1 - β_{1}^{t}} \\ = \frac{β_{1} v_{t - 1}}{1 - β_{1}^{t}} + \frac{(1 - β_{1}) g (w_{t - 1})}{1 - β_{1}^{t}} \end{aligned} \end{matrix}

$\bar{v}_t$ $\hat{v}_t$ （与Adam的不同之处）：

\begin{matrix} (31) & {\bar{v}}_{t} = \frac{β_{1} v_{t}}{1 - β_{1}^{t + 1}} + \frac{(1 - β_{1}) g (w_{t - 1})}{1 - β_{1}^{t}} \end{matrix}

再进行更新：

\begin{matrix} (32) & w_{t} = w_{t - 1} - \frac{η {\bar{v}}_{t}}{\sqrt{{\hat{s}}_{t} + ϵ}} \end{matrix}

常见问题

为什么深度学习不使用牛顿法或者拟牛顿法？
- 牛顿法需要用到梯度和Hessian矩阵，这两个都难以求解。因为很难写出深度神经网络拟合函数的表达式，遑论直接得到其梯度表达式，更不要说得到基于梯度的Hessian矩阵了。
- 即使可以得到梯度和Hessian矩阵，当输入向量的维度N较大时，Hessian矩阵的大小是N×N，所需要的内存非常大。
- 在高维非凸优化问题中，鞍点相对于局部最小值的数量非常多，而且鞍点处的损失值相对于局部最小值处也比较大。而二阶优化算法是寻找梯度为0的点，所以很容易陷入鞍点。
如何选择合适的优化算法？

符号定义

方向导数

方向导数定义

方向导数与偏导数的关系

梯度

梯度与方向导数的关系

梯度与等高线的关系

梯度下降法

随机梯度下降法

小批量梯度下降法

梯度下降算法的缺点

动量法

NAG(Nesterov Accelerated Gradient)

牛顿法

零点求解

牛顿法

AdaGrad

RMSProp

AdaDelta

Adam

NAdam

NAG回顾与改写

NAdam

常见问题

参考文档