优化算法

title: 优化算法 tags:

• 优化算法

• 机器学习

  categories:

• 机器学习

• 数学

梯度下降

梯度下降（Gradient Descent，GD）是迭代法的一种，可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，另一种常用的方法是最小二乘法。在求解损失函数的最小值时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数和模型参数值。反过来，如果我们需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。

梯度

在微积分里面，对多元函数的参数求 $\partial 偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。

比如函数 $f(x,y)​$ ，分别对 $x,y​$ 求偏导数，求得的梯度向量就是 $\begin{bmatrix}\frac{\partial{f}}{\partial{x}} \ \frac{\partial{f}}{\partial{y}} \end{bmatrix}​$，简称 ​$grad f(x,y)​$ 或者 ​$\nabla f(x,y)​$。

梯度的几何意义是函数变化增加最快的地方。

描述

• 确定优化目标函数 $h_\theta (x)$ 和 $J(\theta)$

• 初始化相关参数 $模型参数\theta ,终止距离 \epsilon,学习速率\alpha$

• 算法过程

  • 确定当前位置损失函数的梯度

    $$\frac{\partial}{\partial\theta}J(\theta) \hspace{3em} 梯度$$
  • 用学习速率 （$\alpha$ ，也称为步长）乘以损失函数的梯度，得到当前位置下降的距离（这里，步长和距离不是同一个概念）

    $$\alpha\frac{\partial}{\partial\theta}J(\theta) \hspace{3em} 下降距离 \Delta \theta$$
  • 如果向量 $\theta​$ 中所有元素都小于终止距离 $\epsilon​$ ，则终止算法；否则继续

  • 更新 $\theta$ 向量

    $$\theta := \theta - \alpha\frac{\partial}{\partial\theta}J(\theta)$$

调优

• 步长选择

• 参数初始值选择

• 归一化

特点

• 实现简单

• 梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向

• 对于非凸函数，不保证收敛到全局最优解

梯度下降与梯度上升

如果实值函数 $F(x)$ 在a处可微且有定义，那么函数 $F(x)$ 在沿着梯度的方向 $\nabla F(a)$ 上升最快，沿梯度相反方向 $-\nabla F(a)$ 下降最快。

梯度下降

$$b = a - \nabla F(a)$$

梯度上升

$$b = a - \nabla F(a)$$

梯度上升法其基本原理与下降法一致，区别在于：梯度上升法是求函数的局部最大值。因此，对比梯度下降法，其几何意义和很好理解，那就是：算法的迭代过程是一个“上坡”的过程，每一步选择坡度变化率最大的方向往上走，这个方向就是函数在这一点梯度方向（注意不是反方向了）。最后随着迭代的进行，梯度还是不断减小，最后趋近与零。

有一点我是这样认为的：所谓的梯度“上升”和“下降”，一方面指的是你要计算的结果是函数的极大值还是极小值。计算极小值，就用梯度下降，计算极大值，就是梯度上升；另一方面，运用上升法的时候参数是不断增加的，下降法是参数是不断减小的。但是，在这个过程中，“梯度”本身都是下降的。

梯度下降家族

批量梯度下降

批量梯度下降（Batch Gradient Descent，BGD）是梯度下降法最常用的形式，在每次迭代更新参数时，使用所有样本来进行更新。

上面描述的便是批量梯度下降

随机梯度下降

随机梯度下降法（Stochastic Gradient Descent，SGD），和批量梯度下降法原理类似，区别在与每次迭代中，只选择一个样本进行训练。

随机梯度下降法和批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

小批量梯度下降

小批量梯度下降法（Mini-batch Gradient Descent，MBGD）是批量梯度下降法和随机梯度下降法的折衷，每次迭代选取 $x(1\leqslant x \leqslant m)$ 个样本进行训练。

最小二乘法

最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。

描述

• 确定优化目标函数 $h_\theta(x)$

• 确定损失函数

  • $$J(\theta) = \sum \limits_{i=1}^{m} (h_\theta(x)-y_i)^2$$
• 求解

  • 一次计算，直接求解出 $\theta$ ，参考博客

牛顿法

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 $f(x)$ 的泰勒级数的前面几项来寻找方程 $f(x) = 0$ 的根。牛顿法最大的特点就在于它的收敛速度很快。

描述

• 把 $f(\theta)$ 在 $\theta_k$ 处泰勒展开

  $$f(\theta) = f(\theta_k) + f'(\theta_k)(\theta-\theta_k)$$
• 设 $f(\theta) 在 \thetak$ 处的切线与 $x$ 轴交点为 $\theta{k+1}$，该点比 $\theta_{k}$ 更接近 $f(\theta) = 0$ 的根

• 由导数含义可知， $f(\theta) 在 \theta_k$ 处的导数 $f'(\theta_k)$ 是切线的斜率，进而有

  $$f'(\theta_k) = \frac{f(\theta_k)}{\theta_k - \theta_{k+1}}$$
• 得到迭代公式

  $$\theta_{k+1} = \theta_k - \frac{f(\theta_k)}{f'(\theta_{k})}$$
• 以上是使用牛顿法，迭代求解 $f(\theta) = 0$ 的根的过程

使对数似然函数最大化

• 确定对数似然函数 $\ell(\theta)$

• 为了是 $\ell(\theta)$ ，需要找到一个值 $\theta$ 使得 $\ell'(\theta) = 0$

• 使用牛顿法求解 $\theta$，迭代公式为

  $$\theta^{(t+1)} = \theta^{(t)} - \frac{\ell'(\theta^{(t)})}{\ell''^{(t)}}$$
• 更一般地，当 $\theta$ 是一个向量时，有

  $$\theta^{(t+1)} = \theta^{(t)} - H^{-1} \nabla_\theta\ell \\ 其中 \\ \nabla_\theta\ell \hspace{1em} 为目标函数的梯度 \\ H \ 为\ Hession 矩阵,H_{ij} = \frac{\partial^2 \ell}{\partial\theta_i\partial\theta_j}$$

  ​

牛顿法求最优值步骤总结

• 确定目标函数 $\ell(\theta)$

• 随机选取起始点 $x^{(t)}$

• 更新

  • 计算目标函数在 $x^{(t)}$ 的一阶导数和海森矩阵 $H$

  • 根据迭代公式 $\theta^{(t+1)} = \theta^{(t)} - H^{-1} \nabla_\theta\ell$ 更新 $\theta$ 值

• 如果 $\theta^{(t+1)} - \theta^{(t)} < \epsilon$ 则停止迭代，否则继续执行更新步骤

优缺点

优点

• 使用二阶导数，收敛速度快

缺点

• 牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算量大

拟牛顿法

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。

拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

描述

基本步骤和牛顿法相同，知识在每次迭代更新参数时，使用正定矩阵 $G$ 代替海森矩阵的逆。

• 迭代步骤

  $$\theta^{(t+1)} = \theta^{(t)} - G \nabla_\theta\ell \\ 其中 \\ \nabla_\theta\ell \hspace{1em} 为目标函数的梯度 \\ G \ 为正定矩阵，近似Hession 矩阵逆矩阵$$

条件

选择正定矩阵代替海森矩阵的逆矩阵，需要满足以下两个条件。

• 拟牛顿条件

  $$G(\ell'(\theta^{(t+1)}) - \ell'(\theta^{(t)})) = \theta^{(t+1)} - \theta^{(t)}$$
• $G$ 为正定矩阵。因为只有正定才能保证牛顿法的搜索方向是向下搜索。

问题

梯度下降和最小二乘法比较

• 梯度下降法需要选择步长，而最小二乘法不需要。

• 梯度下降法是迭代求解，最小二乘法是计算解析解。

• 如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。

• 最小二乘方法，是线性假设下的一种有闭式解的参数求解方法，最终结果为全局最优；梯度下降法，是假设条件更为广泛（无约束）的，一种通过迭代更新来逐步进行的参数优化方法，最终结果为局部最优。

梯度下降和牛顿法比较

• 梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解

• 牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快

• 不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解

• 相对而言，使用牛顿法/拟牛顿法收敛更快，但是每次迭代的时间比梯度下降法长

• 从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径

  

  红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径

参考

• 参考一
• 参考二