机器学习中的优化方法_杏鑫娱乐-注册登录站

杏鑫资讯

公司新闻

行业动态

技术资讯

公司新闻

机器学习中的优化方法

发布日期：2024-05-13 来源: 网络阅读量（）

本文主要对机器学习中的优化方法进行系统的回顾和总结。首先描述了机器学习中的优化问题。然后，介绍了常用优化算法的原理以及优化算法在一些热门机器学习领域的应用和发展。

大多数机器学习算法的本质是建立一个优化模型，从给定的数据中学习目标函数中的参数。几乎所有的机器学习算法都可以表示成优化问题。根据建模目的以及需要解决的问题，机器学习算法分为以下几类：

监督学习 （用于分类，回归）
半监督学习 （用于分类，回归，聚类，降维）
无监督学习 （用于聚类，降维）
强化学习 （用于策略学习使智能体获得最大的奖赏）

对于监督学习（Supervised Learning），目标是找到一个最优映射函数 $f(x)$ 来最小化训练样本的损失函数，损失函数分为经验风险损失函数和结构风险损失函数。经验风险损失函数指预测结果和实际结果的差别，可表示为如下优化问题：

$\\begin{gather} \\mathop{\\min}_{\ heta}\\frac{1}{N}\\sum_{i=1}^{N}{L(y^i,f(x^i,\ heta))}\\\\ \\end{gather}\\\\$ 结构风险损失函数是指经验风险损失函数加上正则，可以减轻过拟合，可表示为如下优化问题： $\\begin{gather} \\mathop{\\min}_{\ heta}\\frac{1}{N}\\sum_{i=1}^{N}{L(y^i,f(x^i,\ heta))+\\lambda||\ heta||^2_2}\\\\ \\end{gather}\\\\$ 其中， $N$ 是训练样本量， $\ heta$ 是映射函数的参数， $x^i$ 是样本 $i$ 的特征向量， $y^i$ 是样本 $i$ 对应的标签， $L$ 是损失函数。损失函数（loss function）是用来估量模型的预测值 $f(x)$ 与真实值 $y$ 的不一致程度，它是一个非负实值函数，损失函数越小，通常模型性能越好。不同模型用的损失函数一般也不一样。监督学习中常用的损失函数如下：

模型类型	损失函数	含义	优点	缺点	应用
分类模型	0-1损失函数 (zero-one Loss Function)	当预测错误时，损失函数为1，当预测正确时，损失函数值为0	能够直观地刻画分类的错误率	由于其非凸、非光滑的特点，使算法很难直接对该函数进行优化	感知机
分类模型	对数损失函数 / 交叉熵损失函数 (Cross-entropy Loss Function)	在二分类问题下，y 取值为0或1，输出的 f(x) 可以理解为1的概率	能非常好的表征概率分布	健壮性不强，相比于hinge loss对噪声更敏感	逻辑回归、神经网络
分类模型	指数损失函数(exponential Loss Function）	通过弱分类器投票进行强分类器的合成	序列性迭代决策；分类函数线介于square和log；对过拟合的情况不必担心	对离群点、噪声非常敏感；计算量较大	AdaBoost
分类模型	合页损失函数 (Hinge Loss Function）	如果被分类正确，损失为0，否则损失为 1?yf(x)	更专注于整体的误差；健壮性相对较高，对异常点、噪声不敏感	没有太好的概率解释	SVM
回归模型	平方损失函数（MSE）	选择使用欧式距离作为误差度量，计算残差的平方和	处处可导；梯度随误差变化，不需要额外调整学习率	对异常点敏感	回归
回归模型	绝对值损失函数 (MAE)	计算预测值与目标值的差的绝对值	对异常点不敏感；收敛速度快	在0处不连续；梯度固定，无论误差大小梯度都是一样的	回归
回归模型	Huber损失函数	当δ~ 0时，Huber损失会趋向MAE；当δ~ ∞，Huber损失会趋向于MSE	同时具备MSE和MAE这两种损失函数的优点；对异常值更鲁棒性	需要训练超参数δ，而且这个过程需要不断迭代	回归

半监督学习 (Semi-Supervised Learning，SSL) 属于无监督学习（没有任何标记的训练数据）和监督学习（完全标记的训练数据）之间。半监督学习利用少量有标签的数据和大量无标签的数据来训练模型。半监督学习算法可分为：self-training（自训练算法）、Graph-based Semi-supervised Learning（基于图的半监督算法）、Semi-supervised supported vector machine（半监督支持向量机，S3VM）等。其中，S3VM算法可以表示为如下优化问题：

$\\begin{gather} \\mathop{\\min}_{\ extbf{w},b,\\eta,\\xi,z}C \\left[ \\sum_{i=1}^{l}{\\eta^i}+ \\sum_{j=l+1}^{l+k}{min(\\xi^j,z^j)}\\right]+\\left| \\left| \ extbf{w}\\right|\\right|\\\\ \\end{gather}\\\\ y^i(\ extbf{w}\\cdot x^i+b)+\\eta^i\\geq1 \\qquad i=1,...l\\\\ \\eta^i\\geq0 \\qquad i=1,...l\\\\ \ extbf{w}\\cdot x^j+b+\\xi^j \\geq1 \\qquad j=l+1,...l+k\\\\ \\xi^j \\geq0 \\qquad j=l+1,...l+k\\\\ -(\ extbf{w}\\cdot x^j+b)+z^j \\geq1 \\qquad j=l+1,...l+k\\\\ z^j \\geq0 \\qquad j=l+1,...l+k\\\\$ 其中， $C$ 是惩罚系数。

有标签的数据： $\\left\\{ \\left\\{ x^1,y^1\\right\\},\\left\\{ x^2,y^2 \\right\\},....,\\left\\{ x^l,y^l \\right\\}\\right\\}$

无标签的数据： $\\left\\{ x^{l+1},x^{l+2},...,x^N\\right\\}$

为了利用无标签的数据，在加了松弛变量 $\\eta^i$ 的支持向量机（SVM）的基础上，S3VM 添加了两个对无标签的数据的约束。令 $\\xi^j$ 为假设未标记的点属于类别1时的错分误差， $z^j$ 为假设未标记的点属于类别2时的错分误差。

目标是使有标签的误差 $\\sum_{i=1}^{l}{\\eta^i}$ 以及无标签的误差 $\\sum_{j=l+1}^{l+k}{min(\\xi^j,z^j)}$ 最小。

S3VM 是非凸离散组合优化，求解难度大且很难获得全局最优解。

聚类算法

聚类算法将一组样本分成多个簇，保证同一簇内样本之间的差异尽可能小，不同簇内的样本尽可能不同。

K-means聚类算法可表示为如下优化问题：

$\\begin{gather} \\mathop{\\min}_{S}\\ \\sum_{k=1}^{K}{\\sum_{x\\in S_k}{\\left| \\left| x-\\mu_k \\right| \\right|_2^2}}\\\\ \\end{gather}\\\\$ 其中， $K$ 是簇的个数， $x$ 是样本的特征向量， $\\mu_k$ 是第 $k$ 个簇的均值向量， $S_k$ 是第 $k$ 个簇的样本集合。目标是让同一个簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

降维算法

在高维情形下会出现数据样本稀疏、距离计算困难等问题，即“维数灾难(curse of simensionality)”。缓解维数灾难的一个重要途径是降维(dimension reduction)， 即通过某种数学变换将原始高维属性空间转变为一个低维 ”子空间“(subspace)，在这个子空间中样本密度大幅提高，距离计算也变得更为容易。

所以降维算法的目标是确保将数据投影到低维空间后，尽可能保留原始信息。

Principal component analysis (PCA)算法是一个经典的降维算法，可以表示为如下优化问题：

$min\\sum_{i=1}^{N}{\\left| \\left| \\bar{x}^i-x^i \\right| \\right|_2^2}\\\\ \\bar{x}^i=\\sum_{j=1}^{D'}{z_j^ie_j}\\\\ D'\\ll D\\\\$

其中， $N$ 是样本量， $x^i$ 是 $D$ 维的特征向量， $\\bar{x}_i$ 是 $x^i$ 的重构向量， $D'$ 维。 $z_j^i=\\left\\{ z_1^i,z_2^i,...,z_{D'}^i \\right\\}$ 是 $x^i$ 在 $D'$ 维坐标中的投影。 $e_j$ 是 $D'$ 维坐标下的标准正交基。

概率模型中另一个常见的优化目标是最大化训练样本的对数似然函数 (MLE)：

$max\\sum_{i=1}^{N}{ln(p(x^i,\ heta))}\\\\$ 在贝叶斯方法的框架下，往往在参数 $\ heta$ 上假设一些先验分布，这也有缓解过拟合的作用。

强化学习与监督学习和无监督学习不同，旨在找到一个最优策略函数，其输出随环境而变化。强化学习主要分三种方法分别是：基于价值（value-based）、基于策略（policy-based）以及基于模型（model-based）的方法。

基于价值方法的目标是优化价值函数 $V_\\pi(s)$ ：

$\\begin{gather} \\mathop{\\max}_{\\pi}\\ V_\\pi(s)\\\\ \\end{gather}\\\\$

$V_\\pi(s)$ 是状态 $s$ 下的价值函数值，是智能体可以预期的未来奖励积累总值： $V_\\pi(s)=E_\\pi[R_{t+1}+\\gamma R_{t+2}+\\gamma^2 R_{t+3}+...|S_t=s]\\\\$ 其中， $R_{t+1},R_{t+2},R_{t+3}...$ 是未来每一个时间步的奖励；

$\\gamma$ 表示折扣率，在0和1之间：

· $\\gamma$ 越大，折扣越小。表示智能体越在意长期的奖励。

· $\\gamma$ 越小，折扣越大。表示智能体越在意短期的奖励。

机器学习的主要步骤是建立模型假设，定义目标函数，求解目标函数的最大值或最小值来确定模型的参数。在这三个至关重要的步骤中，前两步是将机器学习的问题建模成最优化问题，第三步是通过优化算法求解出想要的模型。

机器学习中的最优化问题分为无约束的最优化问题，带等式约束的最优化问题，带不等式约束以及等式约束的最优化问题。

无约束的最优化问题： $min f(x),x\\in R^n \\\\$

$f(x)$ 至少一阶可微。

根据费马引理，可导函数的每一个可导的极值点都是驻点（函数的导数在该点为零）：

驻点只是函数取得极值的必要条件而不是充分条件，但可以先找到驻点，再判断和筛选它们是不是极值点。无论是解析法，还是数值优化算法，一般都以找驻点作为找极值点的目标。在解析法中，对于一元函数，先求导数，然后求解令导数为0的方程可找到所有驻点。对于多元函数，对各个自变量求偏导数，令它们为0，解方程组，即可找到所有驻点。

带等式约束的最优化问题： $\\begin{gather} \\mathop{\\min}_{x}\\ f(x)\\\\ \\end{gather}\\\\ s.t. \\quad h_j(x)=0,j=1,2,...m\\\\$ 该问题一般使用 dual ascent （对偶上升法），即拉格朗日乘数法求解。

首先构造拉格朗日乘子函数： $L(x,\\lambda)=f(x)+\\sum_{j=1}^{m}{\\lambda_jh_j(x)}\\\\$ 在极值点处，拉格朗日乘子函数 $L(x,\\lambda)$ 对 $x_k(k=1,2,...d_x)$ 和拉格朗日乘子变量 $\\lambda_{j}(j=1,2,...m)$ 的导数都为0： $\\frac{\\partial L}{\\partial x_k}=0,for \\, k=1,2,...d_x(x的维度) \\\\ \\frac{\\partial L}{\\partial \\lambda_j}=0,for \\, j=1,2,...m\\\\$

求解可得到 $x,\\lambda$ 。为使 $x$ 有解，约束的个数 $m$ 应小于 $x$ 的维数 $d_x$ ，否则对 $x$ 的约束方程数将大于 $x$ 的变量个数导致约束太强，各约束方程无法同时被满足而无解。

带不等式约束以及等式约束的最优化问题： $\\begin{gather} \\mathop{\\min}_{x}\\ f(x)\\\\ \\end{gather}\\\\ s.t. \\quad h_j(x)=0,j=1,2,...m\\\\ \\quad \\quad \\quad g_i(x)\\leq0,i=1,2,...n,\\\\$ 创建一般化的拉格朗日算子：

$L(x,\\lambda)=f(x)+\\sum_{j=1}^{m}{\\lambda_jh_j(x)}+\\sum_{i=1}^{n}{\\gamma_ig_i(x)}\\\\$ 在极值点 $x^*$ 处，满足如下KKT条件：

$\\frac{\\partial L}{\\partial x}|_{x=x^*}=0, \\\\ \\frac{\\partial L}{\\partial \\lambda_j}=0,即h_j(x^*)=0，for \\, j=1,2,...m\\\\ g_i(x^*)\\leq0,i=1,2,...n\\\\ \\lambda_j\ e 0,j=1,2,...m\\\\ \\gamma_i\\geq0,i=1,2,...n\\\\ \\gamma_ig_i(x^*)=0,i=1,2,...n\\\\$ 条件 1 是对拉格朗日函数取极值的一个必要条件，条件2、3是原约束条件，条件 4 是拉格朗日系数约束（同等式情况），条件 5 是拉格朗日系数约束（不等式约束情况），条件 6 是互补松弛条件。

最优化问题可以通过解析法和数值法求解。相对数值法，解析法更快，并且能得到精确的解。

以线性回归模型为例：求解 $\\omega$ 和 $b$ 使损失函数 $L(\\omega,b)=\\sum_{i=1}^{m}{(y^i-(\\omega x^i+b))}^2$ 最小化。

这是个无约束的优化问题，将 $L(\\omega,b)$ 分别对 $\\omega$ 和 $b$ 求导，得到：

$\\frac{\\partial L(\\omega,b)}{\\partial \\omega}=2(\\omega \\sum_{i=1}^{m}{(x^i)^2-\\sum_{i=1}^{m}{(y^i-b)x^i)}},\\\\ \\frac{\\partial L(\\omega,b)}{\\partial b}=2(mb-\\sum_{i-1}^{m}{(y^i-wx^i)}),\\\\$

令上面两个式子为0，可得到 $\\omega$ 和 $b$ 的解析解：

$\\omega=\\frac{\\sum_{i=1}^{m}{y^i(x^i-\\bar{x})}}{\\sum_{i=1}^{m}{(x^i)^2}-\\frac{1}{m}(\\sum_{i=1}^{m}{x^i})^2},\\\\ b=\\frac{1}{m}\\sum_{i=1}^{m}{(y^i-wx^i)},\\\\$

但有时由于时间和硬件性能的限制或解析解是未知的时候，则必须采用数值法。比如，大多数机器学习的目标函数或约束都存在指数函数、对数函数之类的超越函数，梯度等于0的方程组是没法直接解出来的。对于这种无法直接求解的问题，只能采用近似的算法来求解，即数值优化算法。数值优化算法的有效性和效率极大地影响着机器学习模型的推广和应用。为了促进机器学习的发展，已经有一系列行之有效的优化方法被提出，提高机器学习方法的性能和效率。数值优化一般采用基于迭代的方法来求解一个问题的极值，即，首先确定一个初始点 $x_0$ ，然后基于前一步的结果确定下一步的解，最终求得的是目标函数驻点的一个近似点。

从数值优化中的梯度信息来看，数值优化方法可以分为三类：

一阶优化方法 （stochastic gradient methods 等）：采用目标函数的一阶导数
高阶优化方法 （Newton’s method 等）：采用目标函数的高阶导数
启发式无导数优化方法 （coordinate descent methods等）

首先介绍梯度下降法的发展（GD, SGD, NAG, AdaGrad, AdaDelta, RMSProp, Adam, SAG, SVRG）。接着介绍乘子交替方向法（ADMM）和数值优化中的Frank-Wolfe方法。

梯度下降（Gradient Descent）

函数的梯度（gradient）指出了函数的最陡增长方向。按梯度的方向走，函数增长得最快。按梯度的负方向走，函数值降低得最快。

梯度下降的伪代码如下：

首先选择迭代法的初始点。接着选取迭代方向，也就是从当前点迭代的方向。梯度下降法选取当前点的梯度负方向 $-\ abla f(x)$ 作为迭代方向，因为梯度的负方向是局部下降最快的方向。接着选择迭代步长 $t$ 。更新 $x$ 为 $x-t\ abla f(x)$ 。

以线性回归为例，假设 $f_\ heta(x)$ 是需要学习的函数， $\ heta$ 是需要学习的参数， $L(\ heta)$ 是损失函数。目标是最小化如下损失函数： $L(\ heta)=\\frac{1}{2N}\\sum_{i=1}^{N}{(f_\ heta(x^i)-y^i)^2}\\\\ f_\ heta(x)=\\sum_{j=1}^{D}{\ heta_jx_j}\\\\$ 其中， $N$ 是样本量； $D$ 是特征数量。梯度下降法交替执行以下两个步骤，直到收敛：

（1）计算 $L(\ heta)$ 关于 $\ heta$ 的梯度 $\\frac{\\partial L(\ heta)}{\\partial\ heta_j}=-\\frac{1}{N}\\sum_{i=1}^{N}{(y^i-f_\ heta(x^i))x_j^i}\\\\$

(2) 更新 $\ heta$ $\ heta_{j}=\ heta_{j}-\\alpha \\sum_{i=1}^{n}\\left(f_{\ heta}\\left(x^{i}\\right)-y^{i}\\right) \\cdot x^{i}_j \\\\$

梯度下降法与最速下降法的对比

最速下降法的伪代码如下：

最速下降法的迭代思路是找泰勒一阶展开式 $f(x+v)\\approx f(x)+\ abla f(x)^Tv$ 中，能使方向导数（Directional Derivative）最小的 $v$ 。最速下降法的下降方向受到范数的限制，如果这里的范数取欧式范数（Euclidean Norm），则最速下降法与梯度法是一样的，所以梯度法是最速下降法使用欧式范数的特殊情况。但如果这里取其它范数，则会得到不同的结果。

随机梯度下降（Stochastic gradient descent, SGD）

随机梯度下降是批量梯度下降的一个变体，相对于批量梯度下降需要使用所有的样本进行更新，随机梯度下降每次更新只使用一个样本进行计算。还是以线性回归为例:

$\ heta_{j}=\ heta_{j}-\\alpha\\left(f_{\ heta}\\left(x^{i}\\right)-y^{i}\\right) \\cdot x^{i}_j \\\\$

由于 SGD 每次迭代仅使用一个样本，因此每次迭代的计算复杂度为 $O(D)$ ，其中 $D$ 是特征数。当样本数 $N$ 很大时，SGD 每次迭代的更新速率比批量梯度下降快得多。然而，SGD 由于随机选择引入的额外噪声会导致梯度方向振荡。因此需要的迭代次数将增加，而且得到的解可能并非最优解。

此外，如何选择学习率是梯度算法中的重要问题。学习率太小会导致收敛速度变慢，而学习率太大会阻碍收敛。解决这个问题的一种方法是设置一个预定义的学习率列表或学习率衰减公式，并在学习过程中调整学习率。常用的学习率衰减方法： $\\alpha=\\frac{1}{1+decayrate\\ast epocnum}\\ast \\alpha_0\\\\$ 其中， $decayrate$ 为衰减率（超参数）， $epocnum$ 为将所有的训练样本完整过一遍的次数。

但是，这些列表或公式需要根据数据集的特性提前定义。对所有参数使用相同的学习率也是不合适的。

后续的NAG, AdaGrad, AdaDelta, RMSProp, Adam等算法就如何调整学习率，如何加快收敛速度，在搜索过程中如何防止陷入局部极小值的问题进行了进一步的优化。

Nesterov Accelerated Gradient Descent （NAG）

该算法通过累积之前的梯度作为动量来加速当前的梯度下降，并以动量进行梯度更新过程。在处理有噪声的梯度时，动量法可以加快收敛速度。动量算法引入变量 $v$ 作为速度，表示参数在参数空间中运动的方向和速率。速度设为负梯度的指数加权平均。

指数加权平均（Exponentially Weight Average）是一种常用的序列数据处理方式，计算公式为：

$S_t=\\begin{cases}Y_t,& \ ext{t=1}\\\\ \\beta S_{t-1}+(1-\\beta)Y_t,& \ ext{t>1}\\end{cases}\\\\$

其中， $Y_t$ 是 $t$ 时刻下的实际值， $S_t$ 是 $t$ 时刻下加权平均后的值， $\\beta$ 是权重。

动量算法更新变量 $v$ 不仅用到梯度下降中的 $\\eta \\cdot(-\\frac{\\partial L(\ heta)}{\\partial \ heta})$ ，还融入了过去更新的速度 $v_{old}$ ： $v=\\eta \\cdot(-\\frac{\\partial L(\ heta)}{\\partial \ heta})+m\\cdot v_{old}\\\\$ 其中， $m\\in[0,1]$ 是动量项的权重。如果当前梯度与之前的速度 $v_{old}$ 平行，那么之前的速度可以加快本次搜索的速度。当学习率 $\\eta$ 较小时，适当的动量起到加速收敛的作用。如果梯度衰减到0，它将继续更新 $v$ 以达到平衡，并会因摩擦而衰减。这有利于在训练过程中逃离局部最小值，从而使搜索过程可以更快地收敛。如果当前梯度与之前更新的 $v_{old}$ 相反，则 $v_{old}$ 的取值会对本次搜索产生减速效果。具有合适的动量项权重 $m$ 的动量法可以减小学习率较大时收敛的振荡。然而，如果动量因子较小，很难获得提高收敛速度的效果。如果动量因子很大，当前点可能会跳出最优值点。许多实验已经根据经验验证了动量因子最合适的设置是 0.9。

然而，当优化问题的各变量尺度差异较大时，动量法在更新过程中会出现震荡问题，Nesterov算法给出了初步解决：

$\\begin{equation}\\left\\{ \\begin{array}{**lr**}\ ilde{\ heta}=\ heta+m\\cdot v_{old}, & \\\\ v=\\eta \\cdot(-\\frac{\\partial L(\ ilde{\ heta})}{\\partial \ heta})+m\\cdot v_{old}, \\\\ \ heta'=\ heta+v, & \\end{array}\\right. \\end{equation}\\\\$ 跟上面动量算法的唯一区别在于，梯度不是根据当前参数位置，而是根据先走了本来计划要走的一步后，达到的参数位置计算出来的。如果前面的梯度比当前位置的梯度大，则梯度下降的幅度比原来大一些，如果前面的梯度比现在的梯度小，则梯度下降的幅度比原来小一些。

Adaptive Learning Rate Method

自适应学习率方法（AdaGrad，AdaDelta，RMSProp，Adam）主要用来自动调整学习率。这些方法无需调参，收敛速度快，往往能取得不错的效果。它们广泛用于深度神经网络以处理优化问题。

AdaGrad

SGD 最直接的改进是 AdaGrad，其主要思路是根据之前一些迭代中的历史梯度动态调整学习率。更新公式如下：

$\\begin{equation}\\left\\{ \\begin{array}{**lr**}g_t=\\frac{\\partial L(\ heta_t)}{\\partial \ heta}, & \\\\ V_t=\\sqrt{\\sum_{i=1}^{t}{(g_t)^2+\\epsilon}}, \\\\ \ heta_{t+1}=\ heta_t+\\eta\\frac{g_t}{V_t}, & \\end{array}\\right. \\end{equation}\\\\$ 其中 $g_t$ 是参数 $\ heta$ 在第 $t$ 次迭代时的梯度， $V_t$ 是参数 $\ heta$ 在第 $t$ 次迭代时的累积历史梯度， $\ heta_t$ 是参数 $\ heta$ 在第 $t$ 次迭代时的值。AdaGrad 与梯度下降的区别在于，在参数更新过程中，学习率不再是固定的，而是使用累积到本次迭代的所有历史梯度来计算的。 $\\eta$ 一般使用默认值 0.01。

虽然 AdaGrad 自适应调整学习率，但它仍然存在两个问题。

1）算法仍然需要手动设置全局学习率 $\\eta$ 。

2）随着训练时间的增加，累积的梯度会越来越大，使得学习率趋于零，导致参数更新无效。

RMSProp

RMSProp 为解决学习率最终会归零的问题，改进了AdaGrad。相比AdaGrad方法累积所有历史梯度，RMSProp 只关注一段时间内窗口中的梯度，并使用指数移动平均计算二阶累积动量，即，将历史梯度平方值按照 $\\beta^{t}$ 衰减之后再累加，将AdaGrad中的 $V_t$ 改为下式： $V_t=\\sqrt{{(1-\\beta)(g_t)^2+\\beta V_{t-1}}}, \\\\$ 其中 $\\beta$ 是人工设定的参数。RMSProp也需要人工指定的全局学习率 $\\eta$ 。

AdaDelta

AdaDelta算法也像RMSProp算法一样，使用指数移动平均计算二阶累积动量：

$s_t=(1-\\beta)(g_t)^2+\\beta s_{t-1}, \\\\$ 与RMSProp算法不同的是，AdaDelta算法还维护一个额外的状态变量 $\\Delta \ heta$ ，其元素同样在时间步0时被初始化为0。AdaDelta 使用 $\\Delta \ heta_{t-1}$ 来计算自变量的变化量：

$g_t'=\\sqrt{\\frac{\\Delta \ heta_{t-1}+\\varepsilon}{s_t+\\varepsilon}}\\ast g_t\\\\$ 其中， $\\varepsilon$ 是为了维持数值稳定性而添加的常数。接着更新自变量：

$\ heta_t=\ heta_{t-1}-g_t'\\\\$ 最后，使用 $\\Delta\ heta$ 来记录自变量变化量 $g_t'$ 按元素平方的指数加权移动平均： $\\Delta\ heta_t=(1-\\beta)(g_t')^2+\\beta \\Delta\ heta_{t-1}, \\\\$ 可以看到，如不考虑 $\\varepsilon$ 的影响，AdaDelta算法与RMSProp算法的不同之处在于使用 $\\sqrt{\\Delta\ heta_{t-1}}$ 来替代超参数 $\\eta$ 。

Adaptive moment estimation (Adam)

Adam是另一种先进的 SGD 方法，它为每个参数引入自适应学习率。Adam 结合了自适应学习率和动量方法。除了如 AdaDelta 和 RMSProp 方法中存储过去梯度平方的指数衰减平均值 $V_t$ ：

$V_t=\\sqrt{{(1-\\beta_2)(g_t)^2+\\beta_2 V_{t-1}}}, \\\\$ Adam 还保留过去梯度的指数衰减平均值 $m_t$ ，类似于动量法： $m_t=\\sqrt{{(1-\\beta_1)g_t+\\beta_1 m_{t-1}}}, \\\\$ 其中 $\\beta_1$ 和 $\\beta_2$ 是指数衰减率。参数 $\ heta$ 的最终更新公式为：

$\ heta_{t+1}=m_t-\\eta\\frac{\\sqrt{1-\\beta_2}}{1-\\beta_1}\\frac{m_t}{V_t+\\epsilon}\\\\$ $\\beta_1$ 、 $\\beta_2$ 和 $\\epsilon$ 的默认值建议分别设置为 0.9、0.999 和 $10^{-8}$ 。 Adam 在实践中表现良好,广泛应用于深度学习。

Alternating Direction Method of Multipliers（ADMM）

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）利用凸优化问题中的可分离算子，将一个大问题分解成多个可以分布式求解的小问题。即，利用ADMM算法可以将原问题的目标函数等价的分解成若干个可求解的子问题，然后并行求解每一个子问题，最后协调子问题的解得到原问题的全局解。理论上，ADMM的框架可以解决大部分的大规模优化问题。

考虑以下示例：

$\\begin{gather} \\mathop{\\min}_{x}\\ f_1(x)+f_2(y)\\\\ \\end{gather}\\\\ s.t. \\quad Ax+By=c,x\\subseteq X,y\\subseteq Y\\\\$ 构造增广拉格朗日函数（augmented Lagrangian function）：
$L_{\\rho}(x,y,\\lambda)=f_1(x)+f_2(y)+\\lambda^T(Ax+By-c)+(\\rho/2)\\|Ax+By-c\\|_2^2.\\\\$ 增广拉格朗日函数是在拉格朗日函数后面加了个平方的正则项（系数 $\\rho/2$ ， $\\rho> 0$ ），主要是为了增加对偶上升方法的鲁棒性和放松目标严格凸（strictly convex）的要求。对 $L_\\rho$ 用dual ascent（对偶上升法）：
$\\begin{align}(x_{t+1},y_{t+1}):=~ & \\arg\\min_{x,y}L_{\\rho}(x,y,\\lambda_t)\\\\ \\lambda_{t+1}:=~ & \\lambda_t+\\rho(Ax_{t+1}+By_{t+1}-c). \\end{align}\\\\$ ADMM 是在此基础上（ $x,y$ 一起迭代）改成 $x,y$ 单独交替迭代。即：
$\\begin{align}x_{t+1}:=~ & \\arg\\min_{x}L_{\\rho}(x,y_t,\\lambda_t)\\\\ y_{t+1}:=~ & \\arg\\min_{y}L_{\\rho}(x_{t+1},y,\\lambda_t)\\\\ \\lambda_{t+1}:=~ & \\lambda_t+\\rho(Ax_{t+1}+By_{t+1}-c). \\end{align}\\\\$ 将前面的增广拉格朗日函数带入上式： $\\begin{align}x_{t+1}:=~ & \\arg\\min_{x}\\left\\{ f_1(x)+(\\lambda_t)^TAx+(\\rho/2)\\|Ax+By_t-c\\|_2^2 \\right\\}\\\\ y_{t+1}:=~ & \\arg\\min_{y}\\left\\{ f_2(y)+(\\lambda_t)^TAy+(\\rho/2)\\|Ax_{t+1}+By-c\\|_2^2 \\right\\}\\\\ \\lambda_{t+1}:=~ & \\lambda_t+\\rho(Ax_{t+1}+By_{t+1}-c). \\end{align}\\\\$

惩罚参数 $\\rho$ 对 ADMM 算法的收敛速度有一定的影响。 $\\rho$ 越大，对约束项的惩罚越大。

Frank-Wolfe Method

Frank-Wolfe Method 是一种求解线性约束下非线性规划问题的算法。其基本思想是将目标函数作线性近似，通过求解线性规划求得可行下降方向,并沿该方向在可行域内作一维搜索。这种方法又称作近似线性化方法。

考虑如下问题：

$\\begin{gather} \\mathop{\\min}_{x}\\ f(x)\\\\ \\end{gather}\\\\ s.t. \\quad Ax=b,x\\geq0\\\\$

$f(x)$ 可用 $f(x)\\approx f(x_t)+\ riangledown f(x_t)^T(x-x_t)$ 来近似，将其带入上式：

$\\begin{gather} \\mathop{\\min}_{x}\\ f(x_t)+\ riangledown f(x_t)^T(x-x_t)\\\\ \\end{gather}\\\\ s.t. \\quad Ax=b,x\\geq0\\\\$ 等价于：

$\\begin{gather} \\mathop{\\min}_{x}\\ \ riangledown f(x_t)^Tx\\\\ \\end{gather}\\\\ s.t. \\quad Ax=b,x\\geq0\\\\$ 假设存在最优解 $y_t$ ，则如下式子必然成立：

$\ riangledown f(x_t)^Ty_t\\leq \ riangledown f(x_t)^Tx_t\\\\ \ riangledown f(x_t)^T(y_t-x_t)\\leq0\\\\$ 所以 $y_t-x_t$ 是 $f(x)$ 在 $x_t$ 处的下降方向。

Frank-Wolfe 算法的伪代码如下：

Frank-Wolfe 算法的特点是早期迭代收敛速度快，后期收敛速度较慢。当迭代点接近最优解时，搜索方向与目标函数的梯度方向趋于正交。这样的方向不是最好的向下方向，因此Frank-Wolfe算法可以在下降方向的选择上进行改进和扩展。

各一阶优化方法总结如下表：

优化方法	性质	优点	缺点
GD	沿着梯度下降的方向求解最优值。该方法以线性速率收敛。	当目标函数是凸函数时，解是全局最优的。	每次参数更新都需要计算总样本的梯度，计算成本高。
SGD	更新参数是使用随机采样的小批量样本计算的。该方法以次线性速率收敛。	每次更新的计算时间不依赖于总的训练样本，节省了大量的计算成本。	很难选择合适的学习率，对所有参数使用相同的学习率不合适。在某些情况下，会陷入鞍点。
NAG	通过累积之前的梯度作为动量来加速当前的梯度下降，并以动量进行梯度更新过程。	当梯度方向发生变化时，动量可以减缓更新速度，减少振荡；当梯度方向保持不变时，动量可以加速参数更新。动量有助于跳出局部最优解。	很难选择合适的学习率。
AdaGrad	学习率根据所有历史梯度的平方和自适应调整。	在训练初期，累积梯度较小，学习率较大，学习速度较快。该方法适用于处理稀疏梯度问题。每个参数的学习率自适应调整。	随着训练时间的增加，累积梯度会越来越大，使得学习率趋于零，导致参数更新无效。需要手动调整学习率。不适合处理非凸问题。
AdaDelta / RMSProp	将总梯度累加的方式改为指数移动平均。	改善 AdaGrad 后期无效学习问题。适用于优化非平稳和非凸问题。	在后期训练阶段，可能会围绕局部最小值重复更新过程。
Adam	结合自适应方法和动量方法。利用梯度的一阶矩估计和二阶矩估计动态调整各参数的学习率。添加偏差校正。	梯度下降过程相对稳定。适用于大多数大数据集、高维空间的非凸优化问题。	在某些情况下，该方法可能不会收敛。
ADMM	该方法通过将线性约束作为惩罚项添加至目标，并将问题分成可以迭代解决的子问题来解决具有线性约束的优化问题。	该方法利用凸优化问题中的可分离算子将一个大问题分解成多个可以分布式求解的小问题。该框架在大多数大规模优化问题中都很实用。	原始残差和对偶残差都与惩罚系数有关，惩罚系数的值难以确定。
Frank-Wolfe	该方法用线性函数逼近目标函数，求解线性规划寻找可行的下降方向，并在可行域内沿该方向进行一维搜索。	该方法可以解决具有线性约束的优化问题，其收敛速度在早期迭代中很快。	该方法在后期阶段收敛缓慢。当迭代点接近最优解时，搜索方向与目标函数的梯度趋于正交。这样的方向不是好的下降方向。

二阶方法通过引入曲率信息，用于解决目标函数高度非线性的问题。二阶方法有：

牛顿法（Newton’s method）
拟牛顿法（Quasi-Newton method）

牛顿法（Newton’s method）

牛顿法的基本思想是同时使用一阶导数（梯度）和二阶导数（Hessian矩阵），用二次函数逼近目标函数，然后求解二次函数的最小值。重复此过程，直到更新的变量收敛。

一维牛顿法迭代公式表示为：

$\ heta_{t+1}=\ heta_t-\\eta_t\\frac{f'(\ heta_t)}{f''(\ heta_t)}\\\\$

其中， $f$ 是目标函数， $\\eta_t$ 是步长。高维牛顿迭代公式为：

$d_t=-\ riangledown^2f(\ heta_t)^{-1}\ riangledown f(\ heta_t)\\\\ \ heta_{t+1}=\ heta_t+\\eta_td_t\\\\$ 其中， $\ riangledown^2f(\ heta_t)$ 是 $f$ 的 Hessian矩阵。牛顿法比梯度下降法有更快的收敛速度，但每次迭代时需要计算Hessian矩阵，运算量大。如果Hessian矩阵不可逆，则无法使用牛顿法。

拟牛顿法（Quasi-Newton method）

拟牛顿法是一种以牛顿法为基础设计的，求解非线性方程组或连续的最优化函数的零点或极大、极小值的算法。拟牛顿法可以解决牛顿法中雅可比矩阵或Hessian矩阵难以甚至无法计算的情况。其本质思想是用一个正定矩阵来逼近Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法是求解非线性优化问题最有效的方法之一。

与牛顿法相同，拟牛顿法是用一个二次函数来近似目标函数 $f(x)$ ， $f(x)$ 的二阶泰勒展开为：

$f(x_k+\\Delta x)\\approx f(x_k)+\ riangledown f(x_k)^T\\Delta x+\\frac{1}{2}\\Delta x^TB\\Delta x\\\\$ 其中， $\ riangledown f$ 是 $f(x)$ 的梯度， $B$ 是Hessian矩阵 $H[f(x)]$ 的近似。梯度 $\ riangledown f$ 可用下式近似：

$\ riangledown f(x_k+\\Delta x)\\approx\ riangledown f(x_k)+B\\Delta x\\\\$ 令上式等于0，得到Newton步长 $\\Delta x$ ：

$\\Delta x=-B^{-1}\ riangledown f(x_k)\\\\$ 拟牛顿法主要迭代步骤：

1） $\\Delta x=-\\alpha B_k^{-1}\ riangledown f(x_k)$

2） $x_{k+1}=x_k+\\Delta x$

3) 计算新的迭代点下的梯度 $\ riangledown f(x_{k+1})$

4) 令 $y_k=\ riangledown f(x_{k+1})-\ riangledown f(x_{k})$

5) 利用 $y_k$ ，近似 $B_{k+1}^{-1}$ ，近似的方法如下表:

启发式无导数优化方法（坐标轮换法 等）是一类不需要函数导数信息的方法，通过试算来寻找优化方向。

优势：对函数没有可微假设。

劣势：收敛速度往往很慢。

坐标轮换法(univariate search technique)

从某个初始点 $x_0$ 出发，沿着各个坐标轴依次做一维搜索得 $x_k$ ，直到 $x_k$ 不再显著变化。

算法步骤：

1）选取初始点。设定 $x_0$ ，误差阈值 $\\epsilon>0$ ，令 $k\\leftarrow0$

2）进行一维搜索。从 $x_{k-1}$ 出发，沿坐标轴方向 $e_k$ 进行一维搜索，求 $\\lambda_{k-1}$ 使得

$f(x_{k-1}+\\lambda_{k-1}e_k)=min_\\lambda f(x_{k-1}+\\lambda e_k)\\\\$ 令 $x_k=x_{k-1}+\\lambda_{k-1}e_k$

3）检查迭代次数。若 $k=N$ ，则跳到步骤4，否则令 $k\\leftarrow k+1$ 跳到步骤2

4）检查终止准则。若 $|x_N-x_0|\\leq \\epsilon$ ，终止迭代输出 $x_N$ ，否则令 $x_0=x_N,k\\leftarrow1$ ，返回步骤2

参考文献：

[1]Sun S, Cao Z, Zhu H, et al. A survey of optimization methods from a machine learning perspective[J]. IEEE transactions on cybernetics, 2019, 50(8): 3668-3681.

[2]S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.

机器学习中的优化方法

相关资讯

官方微信