【机器学习】常用优化方法原理

不念不忘少年蓝@ 2022-06-02 03:57 381阅读 0赞

在ML/DL中，有许多优化方法可以选择，只有清楚了它们的原理才能更好地选择。

# 1、SGD #

随机梯度下降是最经典的方法，其思想如下图所示：

![674][]

首先求出m个样本的Loss的和，求这个和对于神经网络参数theta的梯度，并将该梯度除以样本数m，得到平均梯度。然后，利用反向梯度来更新参数theta。η\_k是学习率，k表示第k次迭代更新。通常，学习率会随着k的增大逐渐减小。

其他的优化器，都是在这个基础上修改完善得来的。

# 2、Momentum #

动量优化器如下图所示：

![700][]

与SGD相比，在更新参数theta时，除了像SGD一样按照本次的反向梯度更新外，还会：

将上次更新的反向梯度乘以系数alpha后也更新到参数theta中。

这相当于：上次更新时是往前走的，这次更新的梯度算出来是往左走，这变化太剧烈了，所以我们来做个折中，往左前方走。感觉上像是上次更新还带有一定的惯性。

# 3、Nesterov Momentum #

Nesterov Momentum如下图所示：

![700 1][]

该优化器相对于Momentum，唯一不同的是计算反向梯度的时机。Momentum计算的是当前位置的反向梯度，Nesterov Momentum 计算的是按照上次更新方向走一小步后的反向梯度。

这相当于：上次是往前走了10米，这次我先往前走上2米，然后再来观察下一步怎么走。可以认为是分两步更新了theta。

# 4、AdaGrad #

AdaGrad相当于增加了一个学习率递减系数：

![646][]

特殊之处在于这个递减系数由之前所有更新的反向梯度的平方的和来决定。可见，AdaGrad的学习率始终是在减小。  
它的优点在于：上图中的theta可以某一个具体的参数，而不是所有参数组成的向量。当theta是某个具体参数时，可以发现，这样计算学习率递减系数相当于：  
如果某个参数在这一步中梯度非常大，那么这一步中学习率衰减就要大一些，好比坡太陡，往下走时必须小步走，步子一大就滚下去了。如果某个参数在这一步中梯度非常小，那么，这一步中学习率衰减就小一些。

但它的问题在于，衰减系数累积了所有更新步骤中的梯度，我们可能更希望考察最近几步中的梯度来决定衰减系数。这就是RMSProp。

# 5、RMSProp #

![700 2][]

随着更新进行，越早时候计算的梯度对计算衰减系数的影响越小，这种影响的减小速度就是decay\_rate的指数衰减速度。

# 6、Adam #

Adam综合了Momentum的更新方向策略和RMProp的计算衰减系数策略，如下图所示：

![700 3][]

**可见，优化器之间是有着内在关联的，存在互相借鉴和改进的关系。最后，用图来表示不同的优化器的效果：**

![620][]

https://i.stack.imgur.com/qAx2i.gif

![620 1][]

https://i.stack.imgur.com/1obtV.gif

# tensorflow中一些常见的优化器 #

**Optimizer：**

tf.train.GradientDescentOptimizer  
tf.train.AdadeltaOptimizer  
tf.train.AdagradOptimizer  
tf.train.AdagradDAOptimizer  
tf.train.MomentumOptimizer  
tf.train.AdamOptimizer  
tf.train.FtrlOptimizer  
tf.train.ProximalGradientDescentOptimizer  
tf.train.ProximalAdagradOptimizer  
tf.train.RMSPropOptimizer

各种优化器对比：

标准梯度下降法：先计算所有样本汇总误差，然后根据总误差来更新权值  
随机梯度下降法：随机抽取一个样本来计算误差，然后更新权值  
批量梯度下降法：是一种折中的方案，从总样本中选取一个批次（比如一共有10000个样本，随机选取100个样本  
作为一个batch），然后计算这个batch的总误差，根据总误差来更新权值。

# **常用的最优化方法（梯度下降法，牛顿法，拟牛顿法，共轭梯度法等）** #

最优化问题，比如考虑一个问题“在一定成本约束下，如何使利润最大化”等。最优化方法是一种数学方法，是研究在给定约束之下如何寻求某些因素（的量），以使某一（或某些）指标达到最优的一些学科的总称。

随着学习的深入，发现最优化方法的重要性。大多问题都可以建模成一种最优化模型进行求解，比如大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的最优化方法有梯度下降法，牛顿法和拟牛顿法，共轭梯度法等。

### **1.梯度下降法（Gradient Descent）** ###

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。**梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是“最速下降法“最速下降法越接近目标值，步长越小，前进越慢。**梯度下降法的搜索迭代示意图如下图所示：

![1022856-20170916201932735-243646199.png][]

**梯度下降法的缺点：**

**　　（1）靠近极小值时收敛速度减慢，如下图所示;**

**　　（2）直线搜索时可能会产生一些问题;**

**　　（3）可能会“之字形”地下降。**

![1022856-20170916202005797-174952848.png][]

从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

比如对一个线性回归（Linear Logistics）模型，假设下面的h（x）是要拟合的函数，J（theta）为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数H（THETA）就出来了。其中米是训练集的样本个数，N是特征的个数。

![1022856-20170916202042188-838465200.png][]

![1022856-20170916202049594-161217114.png][]

**1）批量梯度下降法（Batch Gradient Descent，BGD）**

（1）将Ĵ（THETA）对THETA求偏导，得到每个THETA对应的的梯度：

![20130525190603437][]

（2）由于是要最小化风险函数，所以按每个参数THETA的梯度负方向，来更新每个THETA：

![20130525190954867][]

（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果米很大，那么可想而知这种方法的迭代速度会相当的慢所以，这就引入了另外一种方法 - 随机梯度下降。

对于批量梯度下降法，样本个数M，X为Ñ维向量，一次迭代需要把米个样本全部带入计算，迭代一次计算量为M \* N 2。

**2）随机梯度下降（随机梯度下降，SGD）**

（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：

![20130525191712216][]

（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：

![20130525192139662][]

（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。**两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。**

**对批量梯度下降法和随机梯度下降法的总结：**

**批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。**

**随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。**

### **2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）** ###

**1）牛顿法（Newton's method）**

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

## **具体步骤：** ##

首先，选择一个接近函数 *f *(*x*)零点的 *x*0，计算相应的 *f *(*x*0) 和切线斜率*f  ' *(*x*0)（这里*f ' *表示函数 *f  *的导数）。然后我们计算穿过点(*x*0,  *f  *(*x*0)) 并且斜率为*f *'(*x*0)的直线和 *x *轴的交点的*x*坐标，也就是求如下方程的解：

![222309088311820.png][]

我们将新求得的点的 *x *坐标命名为*x*1，通常*x*1会比*x*0更接近方程*f  *(*x*) = 0的解。因此我们现在可以利用*x*1开始下一轮迭代。迭代公式可化简为如下所示：

![222309221284615.png][]

已经证明，如果*f  *' 是连续的，并且待求的零点*x*是孤立的，那么在零点*x*周围存在一个区域，只要初始值*x*0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果*f  *' (*x*)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。

由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

牛顿法搜索动态示例图：

![1022856-20170916202719078-1588446775.gif][]

**关于牛顿法和梯度下降法的效率对比：**

**　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）**

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

![1022856-20170916202746985-1087770168.png][]

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

**牛顿法的优缺点总结：**

**优点：二阶收敛，收敛速度快；**

**　　缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。**

**2）拟牛顿法（Quasi-Newton Methods）**

拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。

**拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。**拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

**具体步骤：**

拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：

![222253268161863.png][]

这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：

![222254384106201.png][]

其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk

代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk

的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：

![222256385508904.png][]

我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求

![222257530664204.png][]

*　　*从而得到

![222258392223638.png][]

这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。

### **3. 共轭梯度法（Conjugate Gradient）** ###

**共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算海塞矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。**  在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

具体的实现步骤请参加[维基百科共轭梯度法][Link 1]。

下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：

![1022856-20170916202934203-1179802638.png][]

注：绿色为梯度下降法，红色代表共轭梯度法

### **4.启发式优化方法** ###

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时，利用过去的经验，选择已经行之有效的方法，而不是系统地，以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法，遗传算法，蚁群算法以及粒子群算法等等。

还有一种特殊的优化算法被称之多目标优化算法，它主要针对同时优化多个目标（两个及两个以上）的优化问题，这方面比较经典的算法有NSGAII算法，MOEA / d算法以及人工免疫算法等。

### ** 5.解决约束优化问题 - 拉格朗日乘数法** ###

在向量微积分中，标量场的梯度是一个向量场。标量场中某一点上的梯度指向标量场增长最快的方向，梯度的长度是这个最大的变化率。更严格的说，从欧几里得空间Rn到R的函数的梯度是在Rn某一点最佳的线性近似。

在判别式模型中，通常会用到梯度下降、牛顿、拟牛顿学习算法，学习参数，使得模型f(x)可以逼近实际的y。

![20160810164724696][]

## **1.梯度下降** ##

**1.1 为何使用梯度作为下降方向？**

**梯度实际上是函数值变化最快的方向。**

比如说，你站在一个山上，梯度所指示的方向是高度变化最快的方向。你沿着这个方向走，能最快的改变（增加或是减小）你所在位置的高度，但是如果你乱走，可能走半天所在位置高度也没有变化多少。也就是说，如果你一直沿着梯度走，你就能最快的到达山的某个顶峰或低谷（偶尔会到鞍点，不过这几乎不可能）。

所以实际上，梯度下降法是用来数值搜索局部极小值或极大值的，它是实际应用中一种非常高效，高速且可靠的方法。

梯度下降（Gradient Descent）算法是机器学习中使用非常广泛的优化算法。当前流行的机器学习库或者深度学习库都会包括梯度下降算法的不同变种实现。

以线性回归算法损失函数求极小值来说明如何使用梯度下降算法并给出python实现。

*  梯度下降

梯度下降原理：将函数比作一座山，我们站在某个山坡上，往四周看，从哪个方向向下走一小步，能够下降的最快。

![Center][]

在线性回归算法中，损失函数为![Center 1][]

在求极小值时，在数据量很小的时候，可以使用矩阵求逆的方式求最优的θ值。但当数据量和特征值非常大，例如几万甚至上亿时，使用矩阵求逆根本就不现实。而梯度下降法就是很好的一个选择了。

使用梯度下降算法的**步骤**：

1）对θ赋初始值，这个值可以是随机的，也可以让θ是一个全零的向量。

2）改变θ的值，使得目标损失函数J(θ)按梯度下降的方向进行减少。

![Center 2][]

其中为学习率或步长，需要人为指定，若过大会导致震荡即不收敛，若过小收敛速度会很慢。

3）当下降的高度小于某个定义的值，则停止下降。

另外，对上面线性回归算法损失函数求梯度，结果如下：

![Center 3][]

在实际应用的过程中，梯度下降算法有三类，它们不同之处在于每次学习(更新模型参数)使用的样本个数，每次更新使用不同的样本会导致每次学习的准确性和学习时间不同。下面将分别介绍原理及python实现。

*  **批量梯度下降(Batch gradient descent) **

每次使用全量的训练集样本来更新模型参数，即给定一个步长，然后对所有的样本的梯度的和进行迭代：

![Center 4][]

梯度下降算法最终得到的是局部极小值。而线性回归的损失函数为凸函数，有且只有一个局部最小，则这个局部最小一定是全局最小。所以线性回归中使用批量梯度下降算法，一定可以找到一个全局最优解。

**优点**：全局最优解；易于并行实现；总体迭代次数不多  
**缺点**：当样本数目很多时，训练过程会很慢，每次迭代需要耗费大量的时间。

*  随机梯度下降(Stochastic gradient descent)

随机梯度下降算法每次从训练集中随机选择一个样本来进行迭代，即：

![Center 5][]

随机梯度下降算法每次只随机选择一个样本来更新模型参数，因此每次的学习是非常快速的，并且可以进行在线更新。

随机梯度下降最大的缺点在于每次更新可能并不会按照正确的方向进行，因此可以带来优化波动(扰动)。不过从另一个方面来看，随机梯度下降所带来的波动有个好处就是，对于类似盆地区域（即很多局部极小值点）那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点，这样便可能对于非凸函数，最终收敛于一个较好的局部极值点，甚至全局极值点。

**优点**：训练速度快，每次迭代计算量不大  
**缺点**：准确度下降，并不是全局最优；不易于并行实现；总体迭代次数比较多。

*  Mini-batch梯度下降算法

Mini-batch梯度下降综合了batch梯度下降与stochastic梯度下降，在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择b,b<m个样本进行学习，即：

![Center 6][]

## 批量梯度下降算法 ##

#!/usr/bin/python  
    #coding=utf-8  
    import numpy as np  
    from scipy import stats  
    import matplotlib.pyplot as plt  
      
    # 构造训练数据  
    x = np.arange(0., 10., 0.2)  
    m = len(x)  # 训练数据点数目  
    print m  
    x0 = np.full(m, 1.0)  
    input_data = np.vstack([x0, x]).T  # 将偏置b作为权向量的第一个分量  
    target_data = 2 * x + 5 + np.random.randn(m)  
      
    # 两种终止条件  
    loop_max = 10000  # 最大迭代次数(防止死循环)  
    epsilon = 1e-3  
      
    # 初始化权值  
    np.random.seed(0)  
    theta = np.random.randn(2)  
      
    alpha = 0.001  # 步长(注意取值过大会导致振荡即不收敛,过小收敛速度变慢)  
    diff = 0.  
    error = np.zeros(2)  
    count = 0  # 循环次数  
    finish = 0  # 终止标志  
      
    while count < loop_max:  
        count += 1  
      
        # 标准梯度下降是在权值更新前对所有样例汇总误差，而随机梯度下降的权值是通过考查某个训练样例来更新的  
        # 在标准梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算  
        sum_m = np.zeros(2)  
        for i in range(m):  
            dif = (np.dot(theta, input_data[i]) - target_data[i]) * input_data[i]  
            sum_m = sum_m + dif  # 当alpha取值过大时,sum_m会在迭代过程中会溢出  
      
        theta = theta - alpha * sum_m  # 注意步长alpha的取值,过大会导致振荡  
        # theta = theta - 0.005 * sum_m      # alpha取0.005时产生振荡,需要将alpha调小  
      
        # 判断是否已收敛  
        if np.linalg.norm(theta - error) < epsilon:  
            finish = 1  
            break  
        else:  
            error = theta  
        print 'loop count = %d' % count, '\tw:',theta  
    print 'loop count = %d' % count, '\tw:',theta  
      
    # check with scipy linear regression  
    slope, intercept, r_value, p_value, slope_std_error = stats.linregress(x, target_data)  
    print 'intercept = %s slope = %s' % (intercept, slope)  
      
    plt.plot(x, target_data, 'g*')  
    plt.plot(x, theta[1] * x + theta[0], 'r')  
    plt.show()

## 随机梯度下降算法 ##

#!/usr/bin/python  
    #coding=utf-8  
    import numpy as np  
    from scipy import stats  
    import matplotlib.pyplot as plt  
      
    # 构造训练数据  
    x = np.arange(0., 10., 0.2)  
    m = len(x)  # 训练数据点数目  
    x0 = np.full(m, 1.0)  
    input_data = np.vstack([x0, x]).T  # 将偏置b作为权向量的第一个分量  
    target_data = 2 * x + 5 + np.random.randn(m)  
      
    # 两种终止条件  
    loop_max = 10000  # 最大迭代次数(防止死循环)  
    epsilon = 1e-3  
      
    # 初始化权值  
    np.random.seed(0)  
    theta = np.random.randn(2)  
    # w = np.zeros(2)  
      
    alpha = 0.001  # 步长(注意取值过大会导致振荡,过小收敛速度变慢)  
    diff = 0.  
    error = np.zeros(2)  
    count = 0  # 循环次数  
    finish = 0  # 终止标志  
    ######-随机梯度下降算法  
    while count < loop_max:  
        count += 1  
      
        # 遍历训练数据集，不断更新权值  
        for i in range(m):  
            diff = np.dot(theta, input_data[i]) - target_data[i]  # 训练集代入,计算误差值  
      
            # 采用随机梯度下降算法,更新一次权值只使用一组训练数据  
            theta = theta - alpha * diff * input_data[i]  
      
            # ------------------------------终止条件判断-----------------------------------------  
            # 若没终止，则继续读取样本进行处理，如果所有样本都读取完毕了,则循环重新从头开始读取样本进行处理。  
      
        # ----------------------------------终止条件判断-----------------------------------------  
        # 注意：有多种迭代终止条件，和判断语句的位置。终止判断可以放在权值向量更新一次后,也可以放在更新m次后。  
        if np.linalg.norm(theta - error) < epsilon:     # 终止条件：前后两次计算出的权向量的绝对误差充分小  
            finish = 1  
            break  
        else:  
            error = theta  
    print 'loop count = %d' % count,  '\tw:',theta  
      
      
    # check with scipy linear regression  
    slope, intercept, r_value, p_value, slope_std_error = stats.linregress(x, target_data)  
    print 'intercept = %s slope = %s' % (intercept, slope)  
      
    plt.plot(x, target_data, 'g*')  
    plt.plot(x, theta[1] * x + theta[0], 'r')  
    plt.show()

## Mini-batch梯度下降 ##

#!/usr/bin/python  
    #coding=utf-8  
    import numpy as np  
    from scipy importstats  
    import matplotlib.pyplot as plt  
      
    # 构造训练数据  
    x = np.arange(0.,10.,0.2)  
    m = len(x)  # 训练数据点数目  
    print m  
    x0 = np.full(m, 1.0)  
    input_data = np.vstack([x0, x]).T  # 将偏置b作为权向量的第一个分量  
    target_data = 2 *x + 5 +np.random.randn(m)  
      
    # 两种终止条件  
    loop_max = 10000  #最大迭代次数(防止死循环)  
    epsilon = 1e-3  
      
    # 初始化权值  
    np.random.seed(0)  
    theta = np.random.randn(2)  
      
    alpha = 0.001  #步长(注意取值过大会导致振荡即不收敛,过小收敛速度变慢)  
    diff = 0.  
    error = np.zeros(2)  
    count = 0  #循环次数  
    finish = 0  #终止标志  
    minibatch_size = 5  #每次更新的样本数  
    while count < loop_max:  
        count += 1  
      
        # minibatch梯度下降是在权值更新前对所有样例汇总误差，而随机梯度下降的权值是通过考查某个训练样例来更新的  
        # 在minibatch梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算  
      
        for i inrange(1,m,minibatch_size):  
            sum_m = np.zeros(2)  
            for k inrange(i-1,i+minibatch_size-1,1):  
                dif = (np.dot(theta, input_data[k]) - target_data[k]) *input_data[k]  
                sum_m = sum_m + dif  #当alpha取值过大时,sum_m会在迭代过程中会溢出  
      
            theta = theta- alpha * (1.0/minibatch_size) * sum_m #注意步长alpha的取值,过大会导致振荡  
      
        # 判断是否已收敛  
        if np.linalg.norm(theta- error) < epsilon:  
            finish = 1  
            break  
        else:  
            error = theta  
        print 'loopcount = %d'% count, '\tw:',theta  
    print 'loop count = %d'% count, '\tw:',theta  
      
    # check with scipy linear regression  
    slope, intercept, r_value, p_value,slope_std_error = stats.linregress(x, target_data)  
    print 'intercept = %s slope = %s'% (intercept, slope)  
      
    plt.plot(x, target_data, 'g*')  
    plt.plot(x, theta[1]* x +theta[0],'r')  
    plt.show()

**1.2 以逻辑斯蒂回归（LR）为例**

1.  **模型参数估计** 
    
    ![70][]
2.  **梯度下降学习参数** 
    
    ![70 1][]
3.  **最终模型** 
    
    ![70 2][]

### **1.3 具体学习过程(python代码示例)** ###

**梯度下降是最小化风险函数、损失函数的一种常用方法，随机梯度下降和批量梯度下降是两种迭代求解思路。**

根据batch\_size的不同，可以有大概一下几种形式。

**（1）梯度下降伪代码**

*  每个回归参数初始化为1
 *  重复R次 
    
     *  计算整个数据集的梯度
     *  使用alpha × gradient更新回归系数的向量
     *  返回回归系数

示例代码：

def gradAscent(dataMatIn, classLabels):
        dataMatrix = mat(dataMatIn)             #convert to NumPy matrix
        labelMat = mat(classLabels).transpose() #convert to NumPy matrix
        m,n = shape(dataMatrix)
        alpha = 0.001
        maxCycles = 500
        weights = ones((n,1))
        for k in range(maxCycles):              #heavy on matrix operations
            h = sigmoid(dataMatrix*weights)     #matrix mult
            error = (labelMat - h)              #vector subtraction
            weights = weights + alpha * dataMatrix.transpose()* error #matrix mult
        return weights

**（2）随机梯度下降伪代码：**

*  每个回归参数初始化为1
 *  重复R次 
    
     *  计算每个样本的梯度
     *  使用alpha × gradient更新回归系数的向量
     *  返回回归系数

示例代码：

细心的读者可以看到，其中alpha是变化的，这样可以在一定程度上避免局部最优解。

def stocGradAscent1(dataMatrix, classLabels, numIter=150):
        m,n = shape(dataMatrix)
        weights = ones(n)   #initialize to all ones
        for j in range(numIter):
            dataIndex = range(m)
            for i in range(m):
                alpha = 4/(1.0+j+i)+0.0001    #apha decreases with iteration, does not 
                randIndex = int(random.uniform(0,len(dataIndex)))#go to 0 because of the constant
                h = sigmoid(sum(dataMatrix[randIndex]*weights))
                error = classLabels[randIndex] - h
                weights = weights + alpha * error * dataMatrix[randIndex]
                del(dataIndex[randIndex])
        return weights

**（3）自定义batch\_size,算法流程与上面基本差不错，累计误差更新参数。**梯度下降，就是batch\_size = 全部样本量，随机梯度下降就是batch\_size = 1。

## **2.牛顿法** ##

**2.1 基本介绍**

在最优化的问题中，线性最优化至少可以使用单纯行法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法。假设任务是优化一个目标函数f，求函数f的极大极小问题，可以转化为求解函数f的导数f’=0的问题，这样求可以把优化问题看成方程求解问题（f’=0）。

为了求解f’=0的根，把f（x）的泰勒展开，展开到2阶形式：

![20160810171420241][]

这个式子是成立的，当且仅当 Δx 无线趋近于0。此时上式等价与：

![20160810171458336][]

求解：

![20160810171545160][]

得出迭代公式：

![20160810171643932][]

一般认为牛顿法可以利用到曲线本身的信息，比梯度下降法更容易收敛（迭代更少次数），如下图是一个最小化一个目标方程的例子，红色曲线是利用牛顿法迭代求解，绿色曲线是利用梯度下降法求解。

![20160810171716645][]

**二维情形，图片来源自网络**

**2.2 算法流程**

![70 3][]

**2.3 特性**

1.  牛顿法收敛速度为二阶，对于正定二次函数一步迭代即达最优解。
2.  牛顿法是局部收敛的，当初始点选择不当时，往往导致不收敛
3.  牛顿法不是下降算法，当二阶海塞矩阵非正定时，不能保证产生方向是下降方向。
4.  二阶海塞矩阵必须可逆，否则算法进行困难。
5.  对函数要求苛刻（二阶连续可微，海塞矩阵可逆），而且运算量大。

**2.4 牛顿法的改进**

![70 4][]

**3.拟牛顿法**

**3.1 特征**

1.  只需用到函数的一阶梯度；（Newton法用到二阶Hesse阵）
2.  下降算法，故全局收敛；
3.  不需求矩阵逆；（计算量小）
4.  一般可达到超线性收敛；（速度快）
5.  有二次终结性。

**3.2 DFP法**

x, s, y, H 表示第k 步的量，![20160810184138081][]等表示第k+1步的量。

![70 5][]

![70 6][]

![70 7][]

![70 8][]

**3.3 BFGS法**

若把前面的推导，平行地用在y=Bs公式上，可得到

![70 9][]

用此公式求方向时，需用到矩阵求逆或解方程

![70 10][]

由于每次只有秩2的变换，这里的计算量仍可以降下来。为了得到H-公式，可对上面求逆（推导得）：

![70 11][]

BFGS法有拟牛顿法的全部优点，并且在一定条件下可以证明在BFGS法中使用不精确一维搜索有全局收敛性。

====================================================================

二阶偏导数矩阵也就所谓的赫氏矩阵(Hessian matrix).   
一元函数就是二阶导，多元函数就是二阶偏导组成的矩阵.   
求向量函数最小值时用的，矩阵正定是最小值存在的充分条件。   
经济学中常常遇到求最优的问题，目标函数是多元非线性函数的极值问题尚无一般的求解方法，但判定局部极小值的方法是有的，就是用hessian矩阵，   
在x0点上，hessian矩阵是负定的，且各分量的一阶偏导数为0，则x0为极大值点.   
在x0点上，hessian矩阵是正定的，且各分量的一阶偏导数为0，则x0为极小值点.   
矩阵是负定的充要条件是各个特征值均为负数.   
矩阵是正定的充要条件是各个特征值均为正数.

[![Hessian\_matrix\_1][Hessian_matrix_1]][Hessian_matrix_1_Hessian_matrix_1]

[http://zh.wikipedia.org/zh-cn/%E9%BB%91%E5%A1%9E%E7%9F%A9%E9%98%B5][http_zh.wikipedia.org_zh-cn_E9_BB_91_E5_A1_9E_E7_9F_A9_E9_98_B5]

[http://sunyaxin2005.blog.163.com/blog/static/46252046201001344241985/][http_sunyaxin2005.blog.163.com_blog_static_46252046201001344241985]

[674]: /images/20220602/8d9b907fa0fe425c98f8d4004c2e66d4.png
[700]: /images/20220602/84201f4dd1944a63a6229e53dd08c601.png
[700 1]: /images/20220602/5a951f25d35a42b2be0793b07e5926b9.png
[646]: /images/20220602/84646f8efee54054b935126ccea20716.png
[700 2]: /images/20220602/635b363a51934ffeacd2e037799984f9.png
[700 3]: /images/20220602/bcdd7fdf1892494cb6059bff441de304.png
[620]: /images/20220602/01b8827a88494f74ac20287ab6d3cd70.png
[620 1]: /images/20220602/a4715a2c21b1485ebdbc5545bd157023.png
[1022856-20170916201932735-243646199.png]: /images/20220602/2f12860b66d44c49a03786ef6229a25c.png
[1022856-20170916202005797-174952848.png]: /images/20220602/c7769cf309eb4894a8906798573fc606.png
[1022856-20170916202042188-838465200.png]: /images/20220602/242739792a9846bcb87550e150b10bca.png
[1022856-20170916202049594-161217114.png]: /images/20220602/92520964a9764fa7991ea1484c6ae0a7.png
[20130525190603437]: /images/20220602/9429e16ac7d642a0af20a51881d99f67.png
[20130525190954867]: /images/20220602/f9b6237971cf4ce5b7c7b1b4005a711c.png
[20130525191712216]: /images/20220602/46ec00da15d946098f4188ad5c158ea7.png
[20130525192139662]: /images/20220602/fefc6655be9a4d77b6aba914425e4e48.png
[222309088311820.png]: /images/20220602/d7a6ee62b6964374a42c90916c65b167.png
[222309221284615.png]: /images/20220602/989f94fb018b4bd186268025212d32ef.png
[1022856-20170916202719078-1588446775.gif]: /images/20220602/686d8b2f2bfb4a81abaf2d2f8a15157a.png
[1022856-20170916202746985-1087770168.png]: /images/20220602/055e00aa639d4459aec05ab7ad5c1e74.png
[222253268161863.png]: /images/20220602/9fd5341a3dd04f13826d043d4cc89ec2.png
[222254384106201.png]: /images/20220602/70a71e9e8502406aa06de4563f6e4987.png
[222256385508904.png]: /images/20220602/ca3e088fdf3449e094793aec06cd6d4c.png
[222257530664204.png]: /images/20220602/3c6186cb41da497e9f5b0f2d74db2ed6.png
[222258392223638.png]: /images/20220602/3fe91dd0c2b34fb49c0e77a60a9b8a6b.png
[Link 1]: https://en.wikipedia.org/wiki/Conjugate_gradient_method#Example_code_in_MATLAB
[1022856-20170916202934203-1179802638.png]: /images/20220602/66de68ec1b6345c296f52d72e4592ee9.png
[20160810164724696]: /images/20220602/05fd40ca7523401b9591737cccae173b.png
[Center]: /images/20220602/fa46b8535ddf4700a3b9a14966ddbcde.png
[Center 1]: /images/20220602/2e7d73ed9c0c4725980a98e893859aec.png
[Center 2]: /images/20220602/b27271c1fb4443459e210478b3617e10.png
[Center 3]: /images/20220602/bde174ad854540409d91cf33a334b812.png
[Center 4]: /images/20220602/3c28914fe794437cb729debf65908820.png
[Center 5]: /images/20220602/fe5e68101dc4400ea967e450b88b7be9.png
[Center 6]: /images/20220602/a2337a2b83af43199ab860fcfbde3993.png
[70]: /images/20220602/d59a2ff6bed74d6f8671c533558f8cde.png
[70 1]: /images/20220602/17a25c71a20348469ff7fb1e4c573247.png
[70 2]: /images/20220602/8565998ba1654e6da553d612c550bf1f.png
[20160810171420241]: /images/20220602/8d4c7b5dcfe04611bfa3883c01f6271d.png
[20160810171458336]: /images/20220602/a3c9ca6d01464c48a81d6b5ce87918c1.png
[20160810171545160]: /images/20220602/857d2a474f42497abf3b19ec46186011.png
[20160810171643932]: /images/20220602/85810ac25ce24cd3a3816c24be6e218f.png
[20160810171716645]: /images/20220602/1e552513a9f64b80a0261da118b9c6b7.png
[70 3]: /images/20220602/8907dab256ba4085b0599934847ba5ab.png
[70 4]: /images/20220602/ef623719d7064225a44ec905df16489a.png
[20160810184138081]: /images/20220602/64ebcf8d47aa42aab71cc0b91b3d1a22.png
[70 5]: /images/20220602/9668cca700a3430fb67ad35e3b7d8c0d.png
[70 6]: /images/20220602/12fbb8b0df4f4c3e96ee19824ab3f830.png
[70 7]: /images/20220602/ca9adfa42a394f2e9457d46a5c55e664.png
[70 8]: /images/20220602/0b3da0e684694271b3d2e967760b7f93.png
[70 9]: /images/20220602/162908b47737403f8fd9590350945f4b.png
[70 10]: /images/20220602/9a2e88cd9a27488b83b080fc9d072bfc.png
[70 11]: /images/20220602/7e7eab7963fa4f9c8bba45c00f5574c1.png
[Hessian_matrix_1]: http://images.cnblogs.com/cnblogs_com/emanlee/201108/201108031525302594.jpg
[Hessian_matrix_1_Hessian_matrix_1]: /images/20220602/a540733b09254952b025e823d6c8f0cd.png
[http_zh.wikipedia.org_zh-cn_E9_BB_91_E5_A1_9E_E7_9F_A9_E9_98_B5]: http://zh.wikipedia.org/zh-cn/%E9%BB%91%E5%A1%9E%E7%9F%A9%E9%98%B5
[http_sunyaxin2005.blog.163.com_blog_static_46252046201001344241985]: http://sunyaxin2005.blog.163.com/blog/static/46252046201001344241985/