专栏名称: 机器学习算法与Python实战

长期跟踪关注统计学、数据挖掘、机器学习算法、深度学习、人工智能技术与行业发展动态，分享Python、机器学习等技术文章。回复机器学习有惊喜资料。

机器学习最优化算法（全面总结）

机器学习算法与Python实战 · 公众号 · · 2024-04-02 17:46

正文

导言

对于几乎所有机器学习算法，无论是有监督学习、无监督学习，还是强化学习，最后一般都归结为求解最优化问题。因此，最优化方法在机器学习算法的推导与实现中占据中心地位。在这篇文章中，小编将对机器学习中所使用的优化算法做一个全面的总结，并理清它们直接的脉络关系，帮你从全局的高度来理解这一部分知识。

机器学习要求解的数学模型

几乎所有的机器学习算法最后都归结为求一个目标函数的极值，即最优化问题，例如对于有监督学习，我们要找到一个最佳的映射函数f (x)，使得对训练样本的损失函数最小化（最小化经验风险或结构风险）：

在这里，N为训练样本数，L是对单个样本的损失函数，w是要求解的模型参数，是映射函数的参数，xi为样本的特征向量，yi为样本的标签值。

或是找到一个最优的概率密度函数p(x)，使得对训练样本的对数似然函数极大化（最大似然估计）：

在这里，θ是要求解的模型参数，是概率密度函数的参数。

对于无监督学习，以聚类算法为例，算法要是的每个类的样本离类中心的距离之和最小化：

在这里k为类型数，x为样本向量，μi为类中心向量，Si为第i个类的样本集合。

对于强化学习，我们要找到一个最优的策略，即状态s到动作a的映射函数（确定性策略，对于非确定性策略，是执行每个动作的概率）：

使得任意给定一个状态，执行这个策略函数所确定的动作a之后，得到的累计回报最大化：

这里使用的是状态价值函数。

总体来看，机器学习的核心目标是给出一个模型（一般是映射函数），然后定义对这个模型好坏的评价函数（目标函数），求解目标函数的极大值或者极小值，以确定模型的参数，从而得到我们想要的模型。在这三个关键步骤中，前两个是机器学习要研究的问题，建立数学模型。第三个问题是纯数学问题，即最优化方法，为本文所讲述的核心。

最优化算法的分类

对于形式和特点各异的机器学习算法优化目标函数，我们找到了适合它们的各种求解算法。除了极少数问题可以用暴力搜索来得到最优解之外，我们将机器学习中使用的优化算法分成两种类型（本文不考虑随机优化算法如模拟退火、遗传算法等）：

公式求解
数值优化

前者给出一个最优化问题精确的公式解，也称为解析解，一般是理论结果。后者是在要给出极值点的精确计算公式非常困难的情况下，用数值计算方法近似求解得到最优点。除此之外，还有其他一些求解思想，如分治法，动态规划等。我们在后面单独列出。一个好的优化算法需要满足：

能正确的找到各种情况下的极值点
速度快

下图给出了这些算法的分类与它们之间的关系：

接下来我们将按照这张图来展开进行讲解。

费马定理

对于一个可导函数，寻找其极值的统一做法是寻找导数为0的点，即费马定理。微积分中的这一定理指出，对于可导函数，在极值点处导数必定为0：

对于多元函数，则是梯度为0：

导数为0的点称为驻点。需要注意的是，导数为0只是函数取得极值的必要条件而不是充分条件，它只是疑似极值点。是不是极值，是极大值还是极小值，还需要看更高阶导数。对于一元函数，假设x是驻点：

如果f''(x)>0，则在该点处去极小值
如果f''(x)<0，则在该点处去极大值
如果f''(x)>=0，还要看更高阶导数

对于多元函数，假设x是驻点：

如果Hessian矩阵正定，函数在该点有极小值
如果Hessian矩阵负定，函数在该点有极大值
如果Hessian矩阵不定，还需要看更（此处误）

在导数为0的点处，函数可能不取极值，这称为鞍点，下图是鞍点的一个例子（来自SIGAI云端实验室）：

除鞍点外，最优化算法可能还会遇到另外一个问题：局部极值问题，即一个驻点是极值点，但不是全局极值。如果我们对最优化问题加以限定，可以有效的避免这两种问题。典型的是凸优化，它要求优化变量的可行域是凸集，目标函数是凸函数。

虽然驻点只是函数取得极值的必要条件而不是充分条件，但如果我们找到了驻点，再判断和筛选它们是不是极值点，比之前要容易多了。无论是理论结果，还是数值优化算法，一般都以找驻点作为找极值点的目标。对于一元函数，先求导数，然后解导数为0的方程即可找到所有驻点。对于多元函数，对各个自变量求偏导数，令它们为0，解方程组，即可达到所有驻点。这都是微积分中所讲授的基础方法。幸运的是，在机器学习中，很多目标函数都是可导的，因此我们可以使用这套方法。

拉格朗日乘数法

费马定理给出的不带约束条件下的函数极值的必要条件。对于一些实际应用问题，一般还带有等式或者不等式约束条件。对于带等式约束的极值问题，经典的解决方案是拉格朗日乘数法。

对于如下问题：

构造拉格朗日乘子函数：

在最优点处对x和乘子变量λi的导数都必须为0：

解这个方程即可得到最优解。对拉格朗日乘数法更详细的讲解可以阅读任何一本高等数学教材。机器学习中用到拉格朗日乘数法的地方有：

主成分分析
线性判别分析
流形学习中的拉普拉斯特征映射
隐马尔可夫模型

KKT条件

KKT条件是拉格朗日乘数法的推广，用于求解既带有等式约束，又带有不等式约束的函数极值。对于如下优化问题：

和拉格朗日对偶的做法类似，KKT条件构如下乘子函数：

λ和μ称为KKT乘子。在最优解处x*应该满足如下条件：

等式约束hj (x*)=0和不等式约束gk (x*)<=0是本身应该满足的约束，▽xL(x*)=0和之前的拉格朗日乘数法一样。唯一多了关于gi (x)的条件：

KKT条件只是取得极值的必要条件而不是充分条件。在机器学习中用到KKT条件的地方有：

支持向量机（SVM）

数值优化算法

前面讲述的三种方法在理论推导、某些可以得到方程组的求根公式的情况（如线性函数，正态分布的最大似然估计）中可以使用，但对绝大多数函数来说，梯度等于0的方程组是没法直接解出来的，如方程里面含有指数函数、对数函数之类的超越函数。对于这种无法直接求解的方程组，我们只能采用近似的算法来求解，即数值优化算法。这些数值优化算法一般都利用了目标函数的导数信息，如一阶导数和二阶导数。如果采用一阶导数，则称为一阶优化算法。如果使用了二阶导数，则称为二阶优化算法。

工程上实现时通常采用的是迭代法，它从一个初始点x0开始，反复使用某种规则从xk移动到下一个点xk+1，构造这样一个数列，直到收敛到梯度为0的点处。即有下面的极限成立：

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

梯度下降法

梯度下降法沿着梯度的反方向进行搜索，利用了函数的一阶导数信息。梯度下降法的迭代公式为：

根据函数的一阶泰勒展开，在负梯度方向，函数值是下降的。只要学习率设置的足够小，并且没有到达梯度为0的点处，每次迭代时函数值一定会下降。需要设置学习率为一个非常小的正数的原因是要保证迭代之后的xk+1位于迭代之前的值xk的邻域内，从而可以忽略泰勒展开中的高次项，保证迭代时函数值下降。

梯度下降法及其变种在机器学习中应用广泛，尤其是在深度学习中。）

动量项

为了加快梯度下降法的收敛速度，减少震荡，引入了动量项。动量项累积了之前迭代时的梯度值，加上此项之后的参数更新公式为：

其中Vt+1是动量项，它取代了之前的梯度项。动量项的计算公式为：

它是上一时刻的动量项与本次梯度值的加权平均值，其中α是学习率，μ是动量项系数。如果按照时间t进行展开，则第t次迭代时使用了从1到t次迭代时的所有梯度值，且老的梯度值安μt的系数指数级衰减：

动量项累积了之前迭代时的梯度值，使得本次迭代时沿着之前的惯性方向向前走。

AdaGrad算法

AdaGrad算法是梯度下降法最直接的改进。梯度下降法依赖于人工设定的学习率，如果设置过小，收敛太慢，而如果设置太大，可能导致算法那不收敛，为这个学习率设置一个合适的值非常困难。

AdaGrad算法根据前几轮迭代时的历史梯度值动态调整学习率，且优化变量向量X的每一个分量xi都有自己的学习率。参数更新公式为：

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

RMSProp算法

RMSProp算法是对AdaGrad的改进，避免了长期累积梯度值所导致的学习率趋向于0的问题。具体做法是由梯度值构造一个向量RMS，初始化为0，按照衰减系数累积了历史的梯度平方值。更新公式为：