常见优化方法

常见的优化方法

— 梯度下降法和牛顿法

原文 http://www.cnblogs.com/maybe2030/p/4751804.html

学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解,比如我们现在学习的机器学习算法,大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等.

梯度下降法

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

梯度下降法的缺点

  1. 靠近极小值时收敛速度慢
  2. 直线搜索时可能产生一些问题
  3. 可能之字形下降
    梯度下降法问题

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

批量梯度下降法(Batch Gradient Descent,BGD)

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

$$
h{ \theta } = \sum{j=0}^n\theta_jxj \
J(\theta) = \frac1{2m} *\sum
{j=0}^m(h_{\theta}(x^{(j)}) - y^{(j)} )^2
$$

  1. 首先对$J(\theta)$进行求导 得到每一个theta对应的导数
    $$
    {\partial J \over \partial \thetaj} = \frac1m * \sum{j=0}^m(h_\theta(x^{(j)}) -y^{(j)} )*x_j
    $$
  2. 由于是要最小化风险函数,所以按每个参数theta的梯度负方向,来更新每个$\theta$:
    $$\theta = \theta - \frac1m \sum{j=0}^m(h\theta(x^{(j)}) -y^{(j)} )x^{(j)}$$

  3. 从上面公式可以注意到,它得到的是一个全局最优解,但是每迭代一步,都要用到训练集所有的数据,如果m很大,那么可想而知这种方法的迭代速度会相当的慢。
    对于批量梯度下降法,样本个数m,x为n维向量,一次迭代 需要把m个样本全部带入计算,迭代一次计算量为m*n 2
    所以,这就引入了另外一种方法——随机梯度下降。

随机梯度下降法(Random Gradient Descent,RGD)

$$\theta = \theta - (h_\theta(x^{(j)}) -y^{(j)} )*x_j$$

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

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

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

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

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

牛顿法和拟牛顿法(Newton’s method & Quasi-Newton Methods)

牛顿法

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

$$x_{n+1} = x_n -\frac{f(x)}{f’(x)}
$$
上式主要用来求f(x) = 0 的解,如果要求最大最小值,那么 要转化成求f’(x) = 0

也就是

$$x_{n+1} = x_n -\frac{f’(x)}{f’’(x)}$$

如果是多维向量的话
$$x_{n+1} = x_n -H^{-1}*J$$

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

由于牛顿法是基于当前位置的切线来确定下一次的位置,所以牛顿法又被很形象地称为是”切线法“。牛顿法的搜索路径(二维情况)如下图所示:
enter image description here

牛顿法与梯度下降法的对比:

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

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

牛顿法的优缺点总结:

优点: 二阶收敛,收敛速度快;

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

拟牛顿法

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

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

首先分析如何构造矩阵可以近似Hesse矩阵的逆:

  1. 设第k次迭代之后得到点$ \mathbf{x}{k+1} $,将目标函数$ f(\mathbf{x}) $在$ \mathbf{x}{k+1} $处展成Taylor级数,取二阶近似,得到
    $ f(\mathbf{x})\approx f(\mathbf{x}{k+1})+\nabla f(\mathbf{x}{k+1})(\mathbf{x}-\mathbf{x}{k+1})+\frac{1}{2}(\mathbf{x}-\mathbf{x}{k+1})^{\rm T}\nabla^2f(\mathbf{x}{k+1})(\mathbf{x}-\mathbf{x}{k+1}) $
  2. 再对左右求一阶导数
    $ \nabla f(\mathbf{x}) \approx \nabla f(\mathbf{x}{k+1})+\nabla^2f(\mathbf{x}{k+1})(\mathbf{x}-\mathbf{x}_{k+1}) $
  3. 令$ \mathbf{x}=\mathbf{x}k $,则
    $ \nabla f(\mathbf{x}
    {k+1})-\nabla f(\mathbf{x}k) \approx\nabla^2f(\mathbf{x}{k+1})(\mathbf{x}k-\mathbf{x}{k+1}) $
  4. 记$ \mathbf{s}k=\mathbf{x}{k+1}-\mathbf{x}_k,\quad \mathbf{y}k=\nabla f(\mathbf{x}{k+1})-\nabla f(\mathbf{x}k) $
    同时设Hesse矩阵$ \nabla^2f(\mathbf{x}
    {k+1}) $可逆,则上式可以表示为
    $ \mathbf{s}k \approx [\nabla^2f(\mathbf{x}{k+1})]^{-1}\mathbf{y}_k $
  5. 因此,只需计算目标函数的一阶导数,就可以依据方程(4)估计该处的Hesse矩阵的逆。也即,为了用不包含二阶导数的矩阵$ \mathbf{H}{k+1} $近似牛顿法中的Hesse矩阵$ \nabla^2f(\mathbf{x}{k+1}) $的逆矩 阵,$ \mathbf{H}_{k+1} $必须满足$ \mathbf{s}k \approx \mathbf{H}{k+1}\mathbf{y}k $ (5)
    方程(5)也称为拟牛顿条件。
    $ \mathbf{H}
    {k+1} $只是一个普通矩阵,代表着海塞矩阵的逆矩阵

下面给出两个最常用的$ \mathbf{H}_{k+1} $构造公式

  1. DFP解法
    设初始的矩阵$ \mathbf{H}_0 $为单位矩阵$ \textbf{I} $,然后通过修正$ \mathbf{H}k $给出$ \mathbf{H}{k+1} $,即
    $ \mathbf{H}_{k+1}=\mathbf{H}_k+\Delta \mathbf{H}_k $
    DFP算法中定义校正矩阵为
    $ \Delta \mathbf{H}_k=\frac{\mathbf{s}_k\mathbf{s}_k^{\rm T}}{\mathbf{s}_k^{\rm T}\mathbf{y}_k}-\frac{\mathbf{H}_k\mathbf{y}_k\mathbf{y}_k^{\rm T}\mathbf{H}_k}{\mathbf{y}_k^{\rm T}\mathbf{H}_k\mathbf{y}k} $
    因此
    $ \mathbf{H}
    {k+1}=\mathbf{H}_k+\frac{\mathbf{s}_k\mathbf{s}_k^{\rm T}}{\mathbf{s}_k^{\rm T}\mathbf{y}_k}-\frac{\mathbf{H}_k\mathbf{y}_k\mathbf{y}_k^{\rm T}\mathbf{H}_k}{\mathbf{y}_k^{\rm T}\mathbf{H}_k\mathbf{y}k} $ (6)
    可以验证,这样产生的$ \mathbf{H}
    {k+1} $对于二次凸函数而言可以保证正定,且满足拟牛顿条件

  2. BFGS公式
    BFGS公式有时也称为DFP公式的对偶公式。这是因为其推导过程与方程(6)完全一样,只需要用矩阵$ \mathbf{B}{k+1} $取 代$ \mathbf{H}{k+1}^{-1} $,同时将$ \mathbf{s}_k $和 $ \mathbf{y}k $互换,最后可以得到
    $ \mathbf{H}
    {k+1}=\mathbf{H}_k+[1+\frac{\mathbf{y}_k^{\rm T}\mathbf{H}_k\mathbf{y}_k}{\mathbf{s}_k^{\rm T}\mathbf{y}_k}]\cdot\frac{\mathbf{s}_k\mathbf{s}_k^{\rm T}}{\mathbf{s}_k^{\rm T}\mathbf{y}_k}-\frac{\mathbf{s}_k\mathbf{y}_k^{\rm T}\mathbf{H}_k}{\mathbf{s}_k^{\rm T}\mathbf{y}_k} $ (7)
    这个BFGA公式要优于DFP公式,因此目前得到了最为广泛的应用。

共轭梯度法(Conjugate Gradient)

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

启发式优化方法

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

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