最优化算法总结

maltadirk · 发表于 2022-6-1 10:14

最优化问题

几乎所有的机器学习算法最后都归结为求一个目标函数的极值，即优化问题。因此，最优化方法在机器学习算法的实现中占据中心地位。
最优化问题就是求解函数极值的问题，包括极大值和极小值，微积分为求函数的极值提供了一个统一的思路：找函数的导数等于0的点，因为根据费马引理，在极值点处，导数必定为0。这样，只要函数的可导的，就可以用这个万能的方法解决问题，幸运的是，在实际应用中遇到的函数基本上都是可导的。
在机器学习之类的实际应用中，一般将最优化问题统一表述为求解函数的极小值问题，即：

其中x称为优化变量，f称为目标函数。极大值问题可以转换成极小值问题来求解，只需要将目标函数加上负号即可：

导数与梯度

由于实际应用中一般都是多元函数，因此直接介绍多元函数的情况。梯度是导数对多元函数的推广，它是多元函数对各个自变量偏导数形成的向量。多元函数的梯度定义为：

其中 $\nabla$ 称为梯度算子，它作用于一个多元函数，得到一个向量。下面是计算函数梯度的一个例子：

可导函数在某一点处取得极值的必要条件是梯度为0，梯度为0的点称为函数的驻点，这是疑似极值点。需要注意的是，梯度为0只是函数取极值的必要条件而不是充分条件，即梯度为0的点可能不是极值点。至于是极大值还是极小值，要看二阶导数/Hessian矩阵，这是由函数的二阶偏导数构成的矩阵。分为下面几种情况：
1) 如果Hessian矩阵正定，函数有极小值
2) 如果Hessian矩阵负定，函数有极大值
3) 如果Hessian矩阵不定，则需要进一步讨论
这和一元函数的结果类似，Hessian矩阵可以看做是一元函数的二阶导数对多元函数的推广。一元函数的极值判别法为，假设在某点处导数等于0，则：
1) 如果二阶导数大于0，函数有极小值
2) 如果二阶导数小于0，函数有极大值
3) 如果二阶导数等于0，情况不定
数值优化算法

在这里可能会问：直接求函数的导数/梯度，然后令导数/梯度为0，解方程，问题不就解决了吗？

事实上这个方程可能很难解。比如下面的函数：

分别对x和y求偏导数，并令它们为0，得到下面的方程组：

这个方程非常难以求解，对于有指数函数，对数函数，三角函数的方程，称为超越方程，求解的难度并不比求极值本身小。精确的求解不太可能，所以不能得到解析解，只能求近似解，这称为数值优化算法。这些数值优化算法一般都利用了目标函数的导数信息，如一阶导数和二阶导数。如果采用一阶导数，则称为一阶优化算法。如果使用了二阶导数，则称为二阶优化算法。
工程上实现数值优化算法通常采用的是迭代法，它从一个初始点  开始，反复使用某种规则从  移动到下一个点 $x_{k+1}$ ，构造这样一个数列，直到收敛到梯度为0的点处。即有下面的极限成立：

这些规则一般会利用一阶导数信息即梯度；或者二阶导数信息即Hessian矩阵。这样迭代法的核心是得到这样的由上一个点确定下一个点的迭代公式：

这个过程就像处于山上的某一位置，要到山底找水喝，因此必须到达最低点处。此时我们没有全局信息，根本就不知道哪里是地势最低的点，只能想办法往山下走，走一步看一步。刚开始我们在山上的某一点处，每一步，我们都往地势更低的点走，以期望能走到山底。
优化算法的分类及关系

一阶优化算法

1. 梯度下降法：

首先来看一元函数的泰勒展开，以便于更好的理解多元函数的泰勒展开。如果一个一元函数n阶可导，它的泰勒展开公式为：

如果在某一点处导数值大于0（+），则函数在此处是增函数，加大x的值函数值会增加，减小x的值（-）函数会减小。相反的，如果在某一点处导数值小于0（-），则函数是减函数，增加x的值（+）函数值会减小（-），减小x的值函数值会增加。因此我们可以得出一个结论：如果x的变化很小，并且变化值与导数值反号，则函数值下降。对于一元函数，x的变化只有两个方向，要么朝左，要么朝右。
下面把这一结论推广到多元函数的情况。多元函数
在x点处的泰勒展开为：

这里忽略了二次及更高的项。其中，一次项是梯度向量  与自变量增量  的内积，这等价于一元函数的 $f^{\prime}(x) \Delta x$ 。这样，函数的增量与自变量的增量、函数梯度的关系可以表示为：

$f(\mathrm{x}+\Delta \mathrm{x})-f(\mathrm{x})=(\nabla f(\mathrm{x}))^{\mathrm{T}} \Delta \mathrm{x}+o(\Delta \mathrm{x})$
如果  足够小，在x的某一邻域内，则我们可以忽略二次及以上的项（高阶无穷小），有：

$f(\mathrm{x}+\Delta \mathrm{x})-f(\mathrm{x}) \approx(\nabla f(\mathrm{x}))^{\mathrm{T}} \Delta \mathrm{x}$
这里的情况比一元函数复杂很多，  是一个向量，有无穷多种方向，该往哪个方向走呢？
如果能保证：

则有：

即函数值递减，这就是下山的正确方向。因为有：

$(\nabla f(\mathrm{x}))^{\mathrm{T}} \Delta \mathrm{x}=\|\nabla f(\mathrm{x})\|\|\Delta \mathrm{x}\| \cos \theta$
在这里， $\|\cdot\|$ 表示向量的模， $\theta$ 是向量  和  的夹角。因为向量的模一定大于等于0，如果：

则能保证：

即选择合适的增量  ，就能保证函数值下降，要达到这一目的，只要保证梯度和  的夹角的余弦值小于等于0就可以了。由于有：

只有当 $\theta=\pi$ 时有极小值-1，此时梯度和  反向，即夹角为180度。向量  可由  表示为：

即在梯度相反的方向函数值下降的最快。此时有：

函数的下降值为：

只要梯度不为0，往梯度的反方向走函数值一定是下降的。直接用 $\Delta \mathrm{x}=-\alpha \nabla f(\mathrm{x})$ 可能会有问题，因为  可能会超出x的邻域范围之外，此时是不能忽略泰勒展开中的二次及以上的项的，因此步伐不能太大。一般设：

其中  为一个接近于0的正数，称为步长（学习率），由人工设定，用于保证  在x的邻域内，从而可以忽略泰勒展开中二次及更高的项，则有：

从初始点  开始，使用如下迭代公式：

只要没有到达梯度为0的点，则函数值会沿着序列  递减，最终会收敛到梯度为0的点，这就是梯度下降法。迭代终止的条件是函数的梯度值为0（实际实现时是接近于0），此时认为已经达到极值点。注意我们找到的是梯度为0的点，这不一定就是极值点，后面会说明。梯度下降法只需要计算函数在某些点处的梯度，实现简单，计算量小。
实现细节问题
下面介绍梯度下降法实现时的一些细节问题：
1) 初始值的设定：
一般的，对于不带约束条件的优化问题，可以将初始值设置为0，或者设置为随机数，对于神经网络的训练，一般设置为随机数，这对算法的收敛至关重要。
2) 学习率的设定
最简单的，可以将学习率设置为一个很小的正数，如0.001。另外，可以采用更复杂的策略，在迭代的过程中动态的调整学习率的值。比如前20次迭代为0.001，接下来20次迭代时设置为0.0001。
3) 面临的问题
在实现时，梯度下降法可能会遇到一些问题，典型的是局部极小值和鞍点问题，下面分别进行介绍。

局部极小值：

有些函数可能有多个局部极小值点，下面是一个例子：

这张图中的函数有3个局部极值点，分别是A，B和C，但只有A才是全局极小值，梯度下降法可能迭代到B或者C点处就终止。

鞍点：

鞍点是指梯度为0，Hessian矩阵既不是正定也不是负定，即不定的点。下面是鞍点的一个例子，假设有函数：

显然在(0, 0)这点处不是极值点，但梯度为0，下面是梯度下降法的运行结果：

在这里，梯度下降法遇到了鞍点，认为已经找到了极值点，从而终止迭代过程，而这根本不是极值点。

变型
梯度下降法有大量的变型，它们都只利用之前迭代时的梯度信息来构造每次的更新值，下面我们分别进行介绍。
改进的方向主要就是学习率的改进和梯度的计算方法的改进，对于学习率的改进主要是为了避免人工设定学习率，对于梯度计算方法的改进主要是累积之前的梯度信息，类似于保持行走时的惯性，目的是避免来回震荡，加快收敛速度。

2. 动量项：

最直接的改进是为迭代公式加上动量项，动量项累积了之前的权重更新值，加上此项之后的参数更新公式为：

$\mathrm{X}_{t+1}=\mathrm{X}_{t}+\mathrm{V}_{t+1}$
其中 $\mathrm{V}_{t+1}$ 是动量项，它取代了之前的梯度项。动量项的计算公式为：

动量项累积了之前的梯度信息，类似于保持行走时的惯性，以避免来回震荡，加快收敛速度。
3. 自适应梯度：

AdaGrad为自适应梯度，即adaptive gradient算法，是梯度下降法最直接的改进。唯一不同的是，AdaGrad根据前几轮迭代时的历史梯度值来调整学习率，而不依赖于人工设定的学习率，参数更新公式为：

其中  是学习率（全局学习率），  是第t次迭代时的参数梯度向量，  是一个很小的正数，为了避免除0操作，下标i表示向量的分量。和标准梯度下降法唯一不同的是多了分母中的这一项，它累积了到本次迭代为止梯度的历史值信息用于生成梯度下降的系数值。根据上式，历史导数值的绝对值越大分量学习率越小，反之越大。虽然实现了自适应学习率，但这种算法还是存在问题：需要人工设置一个全局的学习率  ，随着时间的累积，上式中的分母会越来越大，导致学习率趋向于0，参数无法有效更新。
4. AdaDelta算法

AdaDelta算法也是对AdaGrad的改进，避免了长期累积梯度值所导致的学习率趋向于0的问题，另外，还去掉了对人工设置的全局学习率的依赖。假设要优化的参数为x，梯度下降法第t次迭代时计算出来的参数梯度值为  ，算法首先初始化如下两个等于0的向量：

其中 $E\left(g^{2}\right)$ 是梯度平方（对每个分量分别平分）的累计值，更新公式为：
$\begin{gathered} \mathrm{E}\left[\mathrm{g}^{2}\right]_{t}=\rho \mathrm{E}\left[\mathrm{g}^{2}\right]_{t-1}+(1-\rho) \mathrm{g}_{t}^{2} \\ E\left[\Delta x^{2}\right]_{t}=\rho E\left[\Delta x^{2}\right]_{t-1}+(1-\rho) \Delta x_{t}^{2} \end{gathered}$
在这里， $\rho$ 为人工给定的参数 $g^{2}$ 是向量每个元素分别计算平方，后面所有的计算公式都是对向量的每个分量进行。接下来计算如下RMS量：
$\begin{aligned} \mathrm{RMS}[\mathrm{g}]_{t} &=\sqrt{\mathrm{E}\left[\mathrm{g}^{2}\right]_{t}+\varepsilon} \\ R M S(\Delta x)_{t} &=\sqrt{E\left[(\Delta x)^{2}\right]_{t}+\varepsilon} \end{aligned}$
其中  为了稳定数值计算，RMS量也是一个向量，计算时分别对向量的每个分量进行。然后计算参数的更新值：

更新的迭代公式为：

和带动量项的梯度下降法不同的是这里用历史梯度值来构造学习率，同时包括了梯度的平方值。
Adadelta对于AdaGrad的改进主要是:
1) 对于每个维度,用梯度平方的加权平均代替了全部梯度的平方和,避免了后期更新时更新幅度逐渐趋近于0的问题。
2) 用更新量的平方的加权平均来动态得代替了全局的学习率,避免了对学习率的敏感。
5.RMSProp算法

RMSProp算法也是标准梯度下降法的变型，它由梯度值构造一个向量MS，初始化为0，更新公式为：

参数更新公式为：

$\left(\mathrm{x}_{t+1}\right)_{i}=\left(\mathrm{x}_{t}\right)_{i}-\alpha \frac{\left(\mathrm{g}_{t}\right)_{i}}{\sqrt{\operatorname{MS}\left(\left(\mathrm{x}_{t}\right)_{i}\right)}}$
其中 $\delta$ 是人工设定的参数。这种方法通过梯度的历史信息来生成参数更新值的权重系数。
6. Adam算法

Adam算法全称为adaptive moment estimation，它由梯度项构造了两个向量m和v，它们的初始值为0，更新公式为：

其中 $\beta_{1}$ ， $\beta_{2}$ 是人工指定的参数，i为向量的分量下标。依靠这两个值构造参数的更新值，参数的更新公式为：

在这里，用m代替梯度，用v来构造学习率，  是一个非常小的数，防止除以0。
7. 随机梯度下降法

对于有些机器学习问题，假设训练样本集有N个样本，有监督学习算法训练时优化的目标是这个数据集上的平均损失函数：

其中 $L\left(w, \boldsymbol{x}_{i}, y_{i}\right)$ 是对单个训练样本 $(x_{i},y_{i})$ 的损失函数，w是需要学习的参数，r(w)是正则化项， $\lambda$ 是正则化项的权重。如果训练时每次都用所有样本计算梯度并更新，成本太高，作为改进可以在每次迭代时选取一批样本，将损失函数定义在这些样本上。
批量随机梯度下降法在每次迭代中使用上面目标函数的随机逼近值，即只使用 $M \ll N$ 个样本来近似计算损失函数。在每次迭代时要优化的目标函数变为：

已经证明，随机梯度下降法在数学期望的意义下收敛，即随机采样产生的梯度的期望值是真实的梯度。因为每次迭代时的目标函数实际上是不一样的，因此随机梯度下降法并不能保证每次迭代时函数值一定下降。
<hr/>二阶优化算法

在优化过程中使用二阶导数，则称为二阶优化算法，二阶优化算法在深度学习中很少使用，主要原因如下：
a. 二阶优化算法（比如牛顿法）使用的是目标函数的二阶导数，需要计算Hessian矩阵，在高维情况下这个矩阵非常大，计算和存储都是问题。

b. 在小批量的情况下，牛顿法对于二阶导数的估计噪声太大。

最大的问题就是计算复杂度。二阶一次迭代更新的复杂度是n*n，这在高维的时候是不可行的。
其次是模型的稳定性。越简单的东西往往越robust，对于优化算法也是这样。二阶方法能够更快地求得更高精度的解，但是在神经网络这类深层模型中，不高的精度对模型还有益处，能够提高模型的泛化能力。
<hr/>参考:
https://mp.weixin.qq.com/s/lqwUkimO4irkIZmAnp0bcg

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

最优化算法总结

本帖子中包含更多资源