常见迭代优化算法解析及python实现

内容

1、梯度下降

1.1.1批量梯度下降：每次迭代依据全体样本的误差结果更新回归系数

1.1.2随机梯度下降：每次迭代依据某个样本的误差结果更新回归系数

1.1.3小批量梯度下降：每次迭代依据部分样本的误差结果更新回归系数

1.2算法优缺点：

2、坐标下降

2.1坐标下降法特点：

3、牛顿迭代

4、逐步回归

4.1、向前选择

4.2、向后剔除

5、最小角回归

6、拉格朗日乘法

6.1.1 拉格朗日乘子-无约束条件下的目标函数最优解->最优解：J(x,y)梯度为0的点

6.2 拉格朗日对偶性

7、代码

当数据集较小时，可以通过诸如求导方式一步就能求出参数w，但当数据集很大时，计算速度就会变得很慢，有时无法直接通过求导计算，这个时候可以通过迭代优化算法逐步求解 $w^{*}$ 。常见优化算法如下

梯度下降：成本函数：总误差和最小值。一阶导数、梯度、迭代同步更新 $w^{*}$
Conjugate Gradient：线搜索算法，无需手动设置步长，
坐标下降：线搜索算法，无需手动设置步长，代价函数：总误差和最小值。偏导，逐项迭代更新 $w^{*}$
牛顿迭代：线搜索算法，无需手动设置步长，二阶导数
逐步回归：成本函数：总误差和最小值。逐项迭代更新 $w^{*}$
Least Angle Regression：目标函数：找到残差最大的特征列，迭代更新 $w^{*}$
拉格朗日乘法：解决约束优化问题

1、梯度下降

如下图所示，已知一组线性分布数据(x,y)，我们想寻找出一条直线h(x)=AX+B，拟合数据。那么如何寻找出这样一条直线呢？

进行如下操作：

我们只要确定系数A，截距项(偏置项)b，就可以找到这样一条直线。那么如何确定呢？我们可以用穷举法，通过无数的(A,b)，构造出无数中直线，从中选出一条最佳直线。那么如何确定是最拟合的直线呢？
计算每条线上的点与已知点的距离的平方差之和的值来计算代价函数（损失函数），看哪条线的值最小，则说明这条线是最好的。最佳拟合，但是这样找到最佳直线太费力了，无异于大海捞针，那么如何改进呢？
我们可以设计这样一个代价函数，寻找使代价函数最小时的参数(A,b)，对于每一个系数(A,b)对应的代价函数值可以表示为： $J(A,b)=\sum \left ( y^{pred}-y^{true} \right )^{2}$ ，其中假设函数： $y^{pred}=Ax+b$ ，这样就能找到最佳拟合直线，如下公式所示：
$\underset{A,b}{argmin} \sum \left ( y^{pred}-y^{true} \right )^{2}$ 更一般地，设有如下数据集 X (m*n：m行样本，n列特征， $x_{0}=1$ 表示截距项)，n列特征对应的权重系数为 w (n*1)，应变量 Y (m*1)。则有如下代价函数公式，如下所示：
计算出最优参数 $w^{*}$ ，我们就可以找出最优拟合直线(注：这里的代价函数为凸函数，计算出解即使是局部的解也是全局最优解)。那么如何计算上面的代价函数求解出参数w*？
1. 使用最小二乘法即标准线性回归方程求解 $w^{*}$ 注意：最小二乘法涉及矩阵求逆，但是如果该矩阵是个奇异矩阵，则无法对其进行求解，并且当数据集很大时，求逆会造成很大开销。
2.使用迭代优化方法之一：梯度下降求解 $w^{*}$ 注意：这里代价函数乘以1/m，乘或不1/m不影响 $w^{*}$ 最终计算结果
3.迭代更新参数 $w^{*}$ ，对参数矩阵 w 中每个参数w分别求偏导乘以学习率后，同步迭代更新w，直到到达最佳解(最优解/局部最优解)，算法收敛

什么是梯度下降呢？在机器学习中可以简单表示为如下图所示，具体可以理解为for循环遍历具有方向的步长(步长乘以斜率/方向导数/梯度)来计算loss值，直到斜率接近0，斜率=0表明某次循环后计算的loss值最小，这样我们就找到了loss值最小时的对应的”最优解”系数A。梯度的方向即为方向导数取极值的方向或函数变化速度最快的方向，如右下图所示，系数的代价函数的二维等高线图。

注意：如下图所示，我们在迭代更新参数时，首先要设计一个初始参数 $w_{old}$ ，然后再进行下一步

当代价函数为非凸时，初始参数的差异也会影响收敛速度和最终计算结果可能时的局部最优解，如下图所示：

注：此图来自吴恩达的机器学习教程

当代价函数为凸函数时，凸函数的局部最优解为全局最优解。如果迭代次数足够，则不需要考虑不同初始系数值对最终最优解位置的影响，如下图：

因此，在设计模型时，为了获得全局最优解，应尽可能将目标函数设计为凸函数。

1.1.1批量梯度下降：每次迭代依据全体样本的误差结果更新回归系数

迭代：，停止迭代，直到迭代次数达到最大要求或参数集中的值更新前后没有明显变化。 η：学习率。

1.1.2随机梯度下降：每次迭代依据某个样本的误差结果更新回归系数

迭代：，停止迭代，直到迭代次数达到最大要求或参数集中的值更新前后没有明显变化。

1.1.3小批量梯度下降：每次迭代依据部分样本的误差结果更新回归系数

迭代：，停止迭代，直到迭代次数达到最大要求或参数集中的值更新前后没有明显变化。

1.2算法优缺点：

优点：梯度下降是一个有逻辑的更新递进求解的过程，前进方向(迭代方向)按照切线方向(负梯度方向)，可以保证每一次前进以后，Loss值都会降低，对于大部分连续函数和曲线都可以用此方法求解，速度比穷举快。梯度下降法比较“柔和”，如下所示

注：黑色虚线表示总误差和，图像右侧Y坐标有误，应注明为误差和(懒得重画了)

梯度下降法仅在小范围内最快，其收敛速度受学习率影响较大，算法鲁棒性较差。对于一般的二次型，如果条件数很大，抖动下降会变成梯度下降法的正常状态，所以梯度下降法的下降速度不是很快，会来回跳跃，而且收敛慢，所以梯度下降法也很不稳定。

缺点：

梯度只能知道导数方向（切线方向），但无法知道到最优点的距离，所以我们需要手动构建一个固定步长*方向导数，这样就可以在之前的参数，这个固定的步长我们也可以称之为学习率。该算法对学习率的大小极为敏感。学习率太大：可能会直接错过最低点。观点。
不能保证全局最优性，当函数存在多个波分波谷，使用梯度下降只能定位到当前波谷的最低点，而不能跳出这个范围到另一个波谷中，也就是说当前Loss还不是最小值还可以更低。所以求解逻辑回归问题时，通常需要使代价函数为凸函数。不同于线性回归问题，线性回归的代价函数(MSE)通常为凸函数，而在逻辑回归(分类)问题中，采用MSE+sigmoid函数的代价函数为非凸函数，只能找到局部最优解，因此需要保证逻辑回归的代价函数为凸函数，因此采用交叉熵函数作为逻辑回归的代价函数。

注：此图来自网络。

2、共轭梯度法

待添加

3、坐标下降

坐标轴下降法，顾名思义，就是沿着坐标轴的方向下降，与梯度下降不同，梯度下降是沿着梯度的负方向下降。但是梯度下降和坐标下降的共同点是迭代法。通过启发式方法逐步迭代求解函数的最小值。梯度下降是同步更新参数，坐标下降是逐项更新每个参数。

使用坐标轴下降求解，对参数w的每个元素求偏导为0时的极值点( $w_{j}^{*}$ )后迭代更新参数 $w_{j}^{*}$ ，计算过程如下所示：

梯度下降和坐标的区别：

在每次迭代中：仅沿一个（同时更新所有特征）方向（当前下降最快的方向）进行梯度下降

while 最大次数或者 $w$ 收敛程度
更新 $w$

而坐标轴下降法逐项更新每个方向zuowhile 最大次数或者 $w$ 收敛程度

for j in 方向：
将 $w_{j}$ 更新为 $w$

3.1坐标下降法特点：

在坐标轴下降法的每一次迭代中，在当前点沿一个坐标方向进行一维搜索，固定其他维度的坐标方向，寻找一个函数的局部最小值。梯度下降总是沿着梯度的负方向找到函数的局部最小值。
轴下降优化方法是一种非梯度优化算法。整个过程依次使用不同的坐标方向进行迭代，一个循环的一维搜索迭代过程相当于一个梯度下降迭代
梯度下降使用目标函数的导数来确定搜索方向，该方向可能不平行于任何轴。坐标轴下降法使用当前坐标方向进行搜索，不需要求目标函数的导数，只根据某个坐标方向搜索最小值。
两者都是迭代算法，且每一轮迭代都需要O(mn)的计算量(m为样本数，n为维度数)
当多个变量之间有较强的关联性时，坐标下降不是一个很好的方法,坐标下降法会使得优化过程异常缓慢。在应用坐标下降法之前可以先使用主成分分析法（PCA）使各变量之间尽可能相互独立。

4、牛顿迭代

待补充…

5、逐步回归

逐步回归是一种线性回归模型自变量选择方法。它的基本思想是一个一个地引入变量，引入的条件是经验平方的偏回归和显着。同时，每引入一个新变量后，对已选入回归模型的旧变量进行一一检验，将检验后认为不显着的变量删除（归零），以保证每一个获得的自变量子集中的变量是显着的。这个过程经历了几个步骤，直到不能再引入新的变量。此时，回归模型中的所有变量都对因变量显着（显着减少残差）。

我们知道多元回归中的元是指自变量，多元就是多个自变量，即多个x(这里指特征列)。这多个x中有一个问题需要我们考虑，那就是是不是这多个x都对y有作用。答案就是有的时候都管用，有的时候部分管用。那对于那些没用的部分我们最好是不让它加入到回归模型里面。我们把这个筛选起作用的变量或者剔除不起作用变量的过程叫做变量选择。
如何评判一个自变量到底有用没用呢？判断依据就是对自变量进行显著性检验。具体方法是将一个自变量加入到模型中时，有没有使残差平方和显著减少，如果有显著减少则说明这个变量是有用的，可以把这个变量加入到模型中，否则说明时无用的，就可以把这个变量从模型中删除(或者其权重置零)。有没有显著减少的判断标准就是根据F统计量来判断。
变量选择主要包括：前向选择、后向消除、逐步回归（前向选择+后向消除）、最优子集等。

5.1、向前选择

前向选择可以理解为从零开始选择，因为模型一开始没有自变量。具体步骤如下：
拿现有的k个变量分别和y建立回归模型，最后会得到k个模型以及每个模型中变量对应的F统计量和其p_value，然后从显著的模型中挑选出F统计量最大模型对应的自变量，将该自变量加入到模型中，如果k个模型都不显著，则选择结束。
通过第一步我们已经得到了一个显著性变量，并把这个变量加入到了模型中。接下来再在已经加入一个变量的模型里面继续分别加入剩下的变量，能够得到k-1个模型，然后在这k-1个模型里面挑选F值最大且显著的变量继续加入模型。如果没有显著变量，则选择结束。
重复以上两步，直到模型中不能添加显着变量

5.2、向后剔除

后向剔除是一种与前向选择相对应的方法，是前向选择的逆向方法。具体步骤如下：
将所有的自变量都加入到模型中，建立一个包含k个自变量的回归模型。然后分别去掉每一个自变量以后得到k个包含k-1个变量的模型，比较这k个模型，看去掉哪个变量以后让模型的残差平方和减少的最少，即影响最小的变量，就把这个变量从模型中删除。
通过第一步，我们删除了一个无用的变量。第二步，在一个已经被删除的变量的基础上，继续删除剩下的变量，从模型中删除使模型残差平方和最小的自变量。 .
重复以上两步，直到去掉一个自变量不会显着减少残差。此时，其余变量均显着。

向前选择和向后剔除都有明显的不足。向前选择可能存在这样的问题：它不能反映引进新的自变量值之后的变化情况。因为某个自变量开始被引入后得到回归方程对应的AIC最小，但是当再引入其他变量后，可能将其从回归方程中提出会是的AIC值变小，但是使用前进法就没有机会将其提出，即一旦引入就会是终身制的。这种只考虑引入而没有考虑剔除的做法显然是不全面的。类似的，向后剔除中一旦某个自变量被剔除，它就再也没有机会重新进入回归方程。

根据前向选择和后向淘汰的思路和方法，人们自然想到将这两种方法结合起来，从而导致逐步回归。

逐步回归是向前选择和向后踢的组合。是这两种方法的交集，即一选一淘汰。为逐步回归选择变量的过程涉及两个基本步骤：

是在回归模型中引入新变量（正向回归）
被测试为不显着的变量从回归模型中排除（向后拒绝）
while 总误差平方和变化程度:
for j inw:#逐项遍历更新
#向前返回
for sign in [-1,0,1] #向左走、向右走或不走->w[j]增加、减小或不变
w[j] +=step*sign
loss1 =更新当前w[j]下的代价函数(总误差平方和)
#后向消除，特征列对应的权重参数直接置零
w[j] = 0
loss2 =更新当前w[j]下的代价函数(总误差平方和)
#判断哪种方式的代价函数降低，就选哪种方式更新当前参数w[j]
w[j]=前向回归(-1/0/1)/后退剔除
end

逐步回归在每次往模型中增加变量时用的是向前选择，将F统计量最大的变量加入到模型中，将变量加入到模型中以后，针对目前模型中存在的所有变量进行向后剔除，一直循环选择和剔除的过程，直到最后增加变量不能够导致残差平方和变小至前后”不在变化”为止。

6、最小角回归

关于最小角度回归，首先解释一下什么是“最小角度”。这里的角度是指两个向量之间的夹角，用来衡量两个向量的相似度。在这里，它指的是线性相关。如下图，就是余弦相似度计算方法。更多相似度计算方法，见文章计算相似度的三种方法

如上公式，可以得到余弦相似度和夹角成反比，向量夹角越小，其余弦相似度越高，相关性也越强，即最小角回归算法其实也可以称为最大相关回归算法，这里的相关指样本X的特征向量(m*1)与残差( $resid=Y-Y_{pred}=Y-XW$ )的相关性，所以，最小角回归算法的目标函数是在迭代寻找与残差最大相关的每项特征向量，而逐项回归的目标函数是总误差和最小。

算法步骤如下：

数据预处理：标准化。初始化参数 w (n*1)为0向量
计算当前参数 w 下的残差： $resid=Y-XW$
计算所有特征向量与残差余弦相似度，寻找与残差最大的相关的特征向量及其对应的余弦相似度 $\rho_{max}$ ，索引J
更新权重系数： $w\left [ J \right ]+=step\times \rho _{max}$
重复步骤2、3、4

注意：这里除了余弦相似度外，还可以用皮尔逊相关系数来衡量线性相关性。数据归一化后余弦相似度和皮尔逊相关系数等价，皮尔逊相关系数等价于数据归一化后的协方差。具体请参见计算相似度的三种方法。

最小角度回归和逐步回归算法的思想其实很相似。他们都测试了自变量的重要性。区别在于：

对于逐步回归：逐项更新参数w的每一个元素，更新依据总误差平方和大小，更新方式：前向回归/向后剔除

while 总误差平方和变化程度:
for j inw:#逐项遍历更新
#向前返回
for sign in [-1,0,1] #向左走、向右走或不走->w[j]增加、减小或不变
w[j] +=step*sign
loss1 =更新当前w[j]下的代价函数(总误差平方和)
#后向消除，特征列对应的权重参数直接置零
w[j] = 0
loss2 =更新当前w[j]下的代价函数(总误差平方和)
#判断哪种方式的代价函数降低，就选哪种方式更新当前参数w[j]
w[j]=前向回归(-1/0/1)/后退剔除

end

对于最小角回归：更新参数w的每一个元素(不是逐项)，更新依据特征向量与残差的相关强度，更新方式：±相关系数*步长。注意这里的±表示正向关或负相关，稍后会有具体讨论

while 总误差平方和变化程度:
计算当前参数w下的残差resid(m*1)
找到与当前残差最相关的特征向量对应的相似度
更新该特征向量对应的参数w[j]=更新
end

最小角回归算法得到的参数w，是一个稀疏向量，每一个不为0的参数对应的特征列与残差的相关性强度均接近，即向量夹角接近。

注：有的文章称为公角平分线，即用等角条件作为更新参数条件。这个说法很形象但不准确，因为在计算机中，它是浮点数的输出。对于浮点数，相等是没有意义的。只能说这两个浮点数大小接近，当距离小于某个设定的阈值时，可以认为是“相等”。

关于相关性：

首先需要强调的是，相似度只反映变量之间是否存在线性关系。它只能表示是否存在线性关系，而不能通过是否线性相关来证明它是否独立，因为变量之间也可能存在非线性关系。

一般定义相似度或相关系数>0，认为正线性相关，即比如y随x的增长而增长，等于0表示线性不相关，小于0表示负相关，即比如y随x的增长而减小。

在机器学习-特征选择中，当样本数据中存在冗余特征时，即两个特征向量之间的相关性较强时，可以选择其中之一或者可以将对应的权重参数设置为零，称为特征提取或特征提取。飞涨

回到最小角度回归，与残差负相关的特征向量有什么用？可以去掉吗？也就是回到最小角度回归算法时，在更新参数时，是应该选择与残差正相关最强的相似度，还是应该同时考虑负相关的强度？有如下对比图，步长为动态值，左图是更新参数时只考虑正相关，相似度最大，还有一张图在第同时。相似度的绝对值最大。

仅用肉眼观察，右图似乎表明，对于相同的迭代次数，总误差平方和曲线下降得更快。所以负相关特征也有贡献。

此外，步长的设置对迭代算法的结果也有很大的影响。如下图，动态步长设置为固定步长

最小角度回归算法的效果如下：

观察此时固定步长容易使一些参数振荡，难以收敛，类似于梯度下降，如下图所示。

7、拉格朗日乘法

已知如下的模型，目标函数J(w,b)在约束g(w,b)条件下的最小值。在分类问题中可以表示为对于特征向量在决策分界面上测的点分类为类别1，下侧的点分类为类别-1，同时位于样本边界点(支持向量)的两条分界面的间隔最大。

拉格朗日乘子法是一种寻找多元函数在一组约束条件下的极值的方法。通过引入拉格朗日乘子λ，可将有d个变量(w,b)，k个约束条件的最优化问题转换为具有d+k个变量的无约束优化问题求解。

7.1.1拉格朗日乘子-无约束条件下的目标函数最优解->最优解：J(x,y)梯度为0的点

假设目标函数如下所示，J(x,y)的几何图像是一个抛物面，其在xoy面的投影是以原点为中心的同心圆环，由于目标函数J(x,y)为凸函数，凸函数的驻点(各偏导数为0的点)就是全局最优点，所以计算目标函数最小值只需求出J(x,y)关于变量的偏导数等于0的点，即目标函数J(x,y)梯度为0的点就是最优解。