精华内容
下载资源
问答
  • 常用优化算法介绍

    万次阅读 多人点赞 2018-07-10 19:59:16
    我们把解决此类优化问题的方法叫做优化算法优化算法本质上是一种数学方法,常见的优化算法包括梯度下降法、牛顿法、Momentum、Nesterov Momentum、Adagrad、Adam等。其实大部分机器学习算法...

    作者:Walker

    在机器学习的世界中,通常我们会发现有很多问题并没有最优的解,或是要计算出最优的解要花费很大的计算量,面对这类问题一般的做法是利用迭代的思想尽可能的逼近问题的最优解。我们把解决此类优化问题的方法叫做优化算法,优化算法本质上是一种数学方法,常见的优化算法包括梯度下降法、牛顿法、Momentum、Nesterov Momentum、Adagrad、Adam等。其实大部分机器学习算法的本质都是建立优化模型,通过优化算法对损失函数(优化的目标函数)进行优化,从而训练出最好的模型。

    (1)梯度下降法:
    梯度下降法是最常用的一种优化算法。其核心思想是:在当前位置寻找梯度下降最快的方向,来逐渐逼近优化的目标函数。且离目标函数越近,逼近的“步伐”也就越小。梯度下降法本质是一种迭代方法,常用于机器学习算法的模型参数求解。其示意图如下图1所示:

    图1梯度下降法

    梯度下降法的更新公式为:

    其中α为梯度上每次逼近的步长,前边的“-”表示搜索方向为负梯度的方向,L我损失函数。算法更新终止的条件是梯度向量接近于0即可。此外需要特别注意的是,梯度下降法不一定能够找到全局的最优解,很有可能找到的是一个局部最优解。

    (2)梯度下降法的变式

    通常基于梯度的下降方法又有很多变式,我们主要为大家介绍:随机梯度下降法(SDG)、Momentum、Nesterov Momentum、Adagrad、Adam。

    随机梯度下降法是每次使用一批数据进行梯度的计算,而非计算全部数据的梯度,因为如果每次计算全部数据的梯度,会导致运算量加大,运算时间变长,容易陷入局部最优解,而随机梯度下降可能每次不是朝着真正最小的方向,这样反而可以跳出局部的最优解。

    Momentum是在随机梯度下降法的基础上,增加了动量(Momentum)的技术。其核心是通过优化相关方向的训练和弱化无关方向的振荡,来加速SGD训练。Momentum的方法能够在一定程度上缓解随机梯度下降法收敛不稳定的问题,并且有一定的摆脱陷入局部最优解的能力。

    Nesterov Momentum是基于Momentum的加速算法,相比于传统的动量算法,最大的优化是计算经过动量更新之后的位置梯度。

    Adagrad即adaptive gradient,是一种自适应学习率的梯度法。它通过记录并调整每次迭代过程中的前进方向和距离,使得针对不同问题都有一套自适应学习率的方法。Adagrad最大的优势是不需要手动来调整学习率,但与此同时会降低学习率。

    Adam即Adaptive Moment Estimation,是能够自适应时刻的估计方法,能够针对每个参数,计算自适应学习率。这是一种综合性的优化方法,在机器学习实际训练中,往往能够取得不错的效果。

    (3)牛顿法和拟牛顿法

    与上述梯度类型的优化算法最大的不同是,牛顿法是一种二阶收敛算法,所以它的收敛速度相较于一阶算法会更快。牛顿法二阶的意义在于它不仅会沿着梯度最大的方向下降,还会考虑走的下一步坡度是不是也很大,它能够以较远的目光全局的逼近目标函数。其算法的具体步骤为:

    1.首先选择接近于函数f(x)的零点x0,并计算f(x0)处的斜率f’(x0)。然后我们求解以下方程,得到比刚刚的x0更加准确的解x1。

    2.接下来我们利用x1进行下一轮的迭代,迭代公式如下所示。这样经过反复的迭代过程,我们便能取得函数f(x)的最优解。

    牛顿法的迭代示意图如下所示:

    图2 牛顿法

    虽然牛顿法相较于梯度下降法等优化算法收敛速度更快,但每一步都需要求解复杂的Hessian矩阵,计算非常不易。所以后来美国Argonne国家实验室的物理学家W.C.Davidon又针对牛顿法计算复杂的缺陷提出了拟牛顿法。它的核心思想是使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂。另外,因为拟牛顿法不需要二阶导数的信息,所以现在拟牛顿法在机器学习实际问题中应用更加的广泛。

    【总结】:除了以上几类较为常见的优化算法以外,还有共轭梯度法、启发式优化算法等。在实际的机器学习问题中,往往需要具体问题具体分析,根据每类优化问题的特征,选择合适的优化算法。

    展开全文
  • 【磐创AI导读】:本文主要介绍常用的一些机器学习中常用优化算法。 在机器学习的世界中,通常我们会发现有很多问题并没有最优的解,或是要计算出最优的解要花费很大的计算量,面对这类问题一般的做法是利用迭代...

    【磐创AI导读】:本文主要介绍了常用的一些机器学习中常用的优化算法。

    在机器学习的世界中,通常我们会发现有很多问题并没有最优的解,或是要计算出最优的解要花费很大的计算量,面对这类问题一般的做法是利用迭代的思想尽可能的逼近问题的最优解。我们把解决此类优化问题的方法叫做优化算法,优化算法本质上是一种数学方法,常见的优化算法包括梯度下降法、牛顿法、Momentum, Nesterov Momentum, Adagrad, Adam等。其实大部分机器学习算法的本质都是建立优化模型,通过优化算法对损失函数(优化的目标函数)进行优化,从而训练出最好的模型。
    (1)梯度下降法
    梯度下降法是最常用的一种优化算法。其核心思想是:在当前位置寻找梯度下降最快的方向,来逐渐逼近优化的目标函数。且离目标函数越近,逼近的“步伐”也就越小。梯度下降法本质是一种迭代方法,常用于机器学习算法的模型参数求解。其示意图如下图1所示:

    image

    图1梯度下降法


    梯度下降法的更新公式为:

    image

    其中α为梯度上每次逼近的步长,前边的“-”表示搜索方向为负梯度的方向,L我损失函数。算法更新终止的条件是梯度向量接近于0即可。此外需要特别注意的是,梯度下降法不一定能够找到全局的最优解,很有可能找到的是一个局部最优解。
    (2)梯度下降法的变式
    通常基于梯度的下降方法又有很多变式,我们主要为大家介绍:随机梯度下降法(SGD), Momentum, Nesterov Momentum, Adagrad, Adam。

    随机梯度下降法是每次使用一批数据进行梯度的计算,而非计算全部数据的梯度,因为如果每次计算全部数据的梯度,会导致运算量加大,运算时间变长,容易陷入局部最优解,而随机梯度下降可能每次不是朝着真正最小的方向,这样反而可以跳出局部的最优解。

    Momentum是在随机梯度下降法的基础上,增加了动量(Momentum)的技术。其核心是通过优化相关方向的训练和弱化无关方向的振荡,来加速SGD训练。Momentum的方法能够在一定程度上缓解随机梯度下降法收敛不稳定的问题,并且有一定的摆脱陷入局部最优解的能力。

    Nesterov Momentum是基于Momentum的加速算法,相比于传统的动量算法,最大的优化是计算经过动量更新之后的位置梯度。

    Adagrad即adaptive gradient,是一种自适应学习率的梯度法。它通过记录并调整每次迭代过程中的前进方向和距离,使得针对不同问题都有一套自适应学习率的方法。Adagrad最大的优势是不需要手动来调整学习率,但与此同时会降低学习率。

    Adam即Adaptive Moment Estimation,是能够自适应时刻的估计方法,能够针对每个参数,计算自适应学习率。这是一种综合性的优化方法,在机器学习实际训练中,往往能够取得不错的效果。
    (3)牛顿法和拟牛顿法
    与上述梯度类型的优化算法最大的不同是,牛顿法是一种二阶收敛算法,所以它的收敛速度相较于一阶算法会更快。牛顿法二阶的意义在于它不仅会沿着梯度最大的方向下降,还会考虑走的下一步坡度是不是也很大,它能够以较远的目光全局的逼近目标函数。其算法的具体步骤为:
    1)首先选择接近于函数f(x)的零点x0,并计算f(x0)处的斜率f’(x0)。然后我们求解以下方程,得到比刚刚的x0更加准确的解x1。

    image

    2)接下来我们利用x1进行下一轮的迭代,迭代公式如下所示。这样经过反复的迭代过程,我们便能取得函数f(x)的最优解。

    image

    牛顿法的迭代示意图如下所示:

    image

    图2 牛顿法


    虽然牛顿法相较于梯度下降法等优化算法收敛速度更快,但每一步都需要求解复杂的Hessian矩阵,计算非常不易。所以后来美国Argonne国家实验室的物理学家W.C.Davidon又针对牛顿法计算复杂的缺陷提出了拟牛顿法。它的核心思想是使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂。另外,因为拟牛顿法不需要二阶导数的信息,所以现在拟牛顿法在机器学习实际问题中应用更加的广泛。

    【总结】:除了以上几类较为常见的优化算法以外,还有共轭梯度法、启发式优化算法等。在实际的机器学习问题中,往往需要具体问题具体分析,根据每类优化问题的特征,选择合适的优化算法。

    原文发布时间为:2018-07-10
    本文作者:Walker
    本文来自云栖社区合作伙伴“磐创AI”,了解相关信息可以关注“磐创AI”。

    展开全文
  • 机器学习初探-常用优化算法介绍

    千次阅读 2018-01-10 11:31:31
    目的:简单介绍机器学习中常用的一些优化算法,主要用于无约束最优化问题的求解。具体包括梯度下降法(最速梯度下降),牛顿法,几个拟牛顿法(包括DFP,BFGS,LBFGS等,共轭方向法,共轭梯度法,信赖域方法等不在本次...

    目的:简单介绍机器学习中常用的一些优化算法,主要用于无约束最优化问题的求解。具体包括梯度下降法(最速梯度下降),牛顿法,几个拟牛顿法(包括DFP,BFGS,LBFGS等,共轭方向法,共轭梯度法,信赖域方法等不在本次做讨论)。

    概述

    一般的有监督的机器学习问题中,有了带有标注的数据之后,我们往往会先假设一个模型(比如在二分类问题中,我们可以假设有一个超平面把不同类别的case分开),这些假设的模型的数学表达中会有一些未定的参数。然后,我们会设计一个函数,来衡量会这个模型的输出和我们期望的输出之间的“差距”,这个函数一般被叫做损失函数。之后在将这个损失函数和正则化项组合成目标函数(obj)。最后对obj函数进行最优化(一般也就是求极值),来确定模型中的各个参数,最终完成模型假设。这个过程也就是我们常说的机器学习的过程,也就是参数估计的过程。

    这当中的最优化问题,说直白点,就是有一个函数,我们要找到它的极值(全局或者局部)。如果我们找到这些极值,就可以用这些取得极值时的数据,来确定我们假设模型中的参数。总体来说,我们的目标就是当obj确定了之后,通过一些方法,来确定极值在哪里,是多少。

    本文后面的部分,就是来讨论一下针对最优化这一问题,一般有哪些常用的方法。

     

    问题抽象

    确定函数下找最值(以下我们以找最小值为例),就是一般的通用无约束最优化问题:

     

    怎么找呢?如果f本身连续,又可导,可微,而且f比较简单(比如说单变量二次函数),那么我们可能直接可以通过解方程的方式得到解析解,从而找到最小值。但是在一般情况下,f(x)都比较复杂(尤其是维度很大,f本身非凸的情况下),有可能会不可导,不可微分,或者求导困难,所以针对更一般的情况,我们采取的通用方法是迭代法。迭代法大体是如下一种方法:是先猜一个点(估计点),之后根据这个点x0,再附近(比较近的范围内)再找一个点x1,让f(x1)<f(x0),之后再根据x1找到一个 x2,让f(x2)<f(x1),就这样一值找下去,直到找到一个点,使得基本没办法再找到新的,使得了,或者周边的f(x)差距非常非常小了,那么这个点可能就是我们希望找到的f(x)取得最小值的x的取值点(全局或者局部最小点)。

    用数学一点的话来讲,我们希望找到一个序列 x0,x1,x2.....(或者找到一个算法生成这样的序列),使得在定义域上,f(x0)>f(x1)>f(x2).....>f(),如果f() 基本上等于f(x)的最小值,或者说lim  == X*,lim ||-X*|| == 0(在k趋近于无穷时,X*为极值点的x取值),那我们就说这个算法产生的迭代,收敛于f(x)的最小值取值点X*。

     

    一般做法

    我们希望找到一个算法,或者找到一个迭代,使得上面的过程成立,从而找到最小值。具体怎么做呢?

    我们聚焦到一步,来看看一般情况下的做法。假设我们目前更新到的Xk,那下面就有2种情况:第一种情况,无论向周边怎么移动,也没有比f()更小的值了,那么时就取得了f(x)的最小值;第二种,如果至少还有1个方向P(||P||==1),使得向这个方向移动,可以使f(x)的值变小,那么我们让+aP,使得f()<f()即可。这里我们称P为方向,也就是X要往哪里走,a为步长,也就是走多少。如果算法是有效的,那么最终我们就会找到X*。

    所以,优化问题基本可以看成2个阶段的抉择:1.选取一个方向P;2.选取一个步长a。其中选取P比较重要,各种各样不同的算法,基本上就是根据选取P的策略不同而不同的。对a的选择也有很多方法,最简单的方法是固定选取一个固定的,较小的a(比如a=0.005 ~ 0.01);有的时候可以先选一个a,之后根据迭代后P的大小,来动态的调整a;另外就是line search类a选取方法等等,我们下面会有详细的涉及。

     

    下面我们就来看看几个常用的无约束问题的优化算法。


    梯度下降法(最速下降法)

    梯度下降(Gradient Descent) 也被称之为最快下降法(Steepest Descent),可用于寻找函数的最小值(局部最小值)。梯度下降法的思路,是利用函数值在梯度反方向来作为X的迭代方向,也就是。只要沿着函数的梯度反方向移动足够小的距离到一个新的点,那么函数值必定是非递增的,而且在梯度下降法的假设前提下,负的梯度方向是下降是最快的方向。

    梯度下降法,顾名思义,就是利用obj函数的一阶导数来寻找最小值。对于f(x),我们根据泰勒公式的一阶展开,可以得到如下的拟合(对应向量的情况):

    其中的高阶无穷小,忽略。并且是我们要找的方向,且==1,是步长,且>0。

    我们先来看看如何找到。我么你要找一个,使。我们根据,要达到,只要 <0即可。

    根据向量夹角公式,我们可以把写成 。cos的最小值是-1,即theta的取值为π时,当取得。(Cuachy-Schwartz不等式保证了)。

    梯度下降算法就是选取了,所以也叫最速下降法(一阶情况下,这个方向最快!)

     

    下面给出了梯度下降算法的基本算法描述:

    按照上面的算法一,第三步的d,我们每次选取当前点的负梯度方向,这个已经解决了。在第四步,需要选取一个合理的步长,使得的h(a)最小。

    a的好坏对收敛速度的影响也很大,一句话来说:a太小,收敛太慢;a太大,容易震荡,甚至找不到最小值点。(如图)

    怎么寻找合适的步长呢?答案就是 Line search

    线性搜索,又叫一维搜索,试求一元函数极值的迭代方法。

    在给定搜索方向 dk  的前提下,线性搜索要解决的问题如下:  

    如果 h(α)  可微且导数也是连续函数,我们能直接通过解方程的方式求出解析解,从而得到最优的步长,这种方法一般叫做*精确线性搜索(精确line search);但非线性,不连续的优化问题需要通过迭代形式求得近似的最优步长。对于上式,局部或全局最优解对应的导数为

    因为dk与f(xk)在xk处的梯度方向夹角大于90度(这样才函数值会下降),因此h'(a)<=0,如果能找到α1,使得h'(α1)>0,那么必定存在 αt[0,α1) ,使得h'(αt)=0。有多种迭代算法可以求得αt的近似值,下面选择几种典型的介绍。

        *二分线性搜索(Bisection Line Search),其实就是二分折半查找,收敛速度就是log级别的

        *黄金分割发,单峰函数上的搜索,可以不要求函数连续

        *回溯线性搜索(Backing Line Search),根据Armijo(阿米霍)法则,从大得a开始逐渐按比例减小,直到达到满足下降情况的要求。(后续还可以加入wolfe准则)

                    Armijo准则:

        *多项式插值法(Interpolation),也是基于Armijo法则,常用的是根据f(xk),f'(xk)和一个尝试的f(xk+a0dk),来构造一个二项式来拟合f(x) ,通过迭代来得到f(x)的最小值

        *其实牛顿法也可以用来求步长,牛顿法我们后面具体再说,求步长其实就是把要求的函数换成h(a),求a得极值即可。


    ok,现在我们找到了要移动的方向P,又找到了移动的步长a,这样迭代下去,直到收敛或者达到最大的设定迭代次数,基本就可以找到obj的最小值了。那么梯度下降法有什么缺点呢?它真的是下降最快的算法吗?其实选取负梯度的方向作为x的移动方向,只能保证在x一定的邻域内有这种快速的下降性质,对整个定义域内,f的最小化来说,并不一定是这样。比如下图:

     

    同心椭圆的最速下降过程可以看出,最速下降法对全局来说,不一定是下降最快的,它的下降过程是一种阶梯下降,而且随着越来越接近最优点(即f'(x)接近0的点),收敛速度会变的越来越缓慢。

    下面就请出传说中的Rosenbrock function(罗森布罗克方程)!噔噔蹬蹬! 

    它是个非凸函数,在最优化领域,它通常被用来作为一个最优化算法的performance test函数,三维图像如下:

    利用梯度下降法,我们的迭代情况如下图所示:


    可以看到刚一开始速度还可以,但是到后面的收敛情况变得非常的缓慢。

    在看另一个函数:

    它的图像如下:

    利用梯度下降法,迭代情况如下图所示:

    由此可见,从全局情况来看,梯度下降法(最速下降法)不一定会快,但是他还是能收敛的,收敛速度是线性收敛。

    当然,梯度下降法也有很多优点:对初始化点无要求,过程简单(程序好写),计算量也不大,它是很多其他优化算法的基础,其他方法的初始化方向很多也是选用负梯度方向。

     

    梯度下降法应用的3种方式

    实际应用(训练)中一般有三种使用梯度下降的方式:随机梯度下降(stochastic gradient descent),批量梯度下降(batch gradient descent)以及小批量梯度下降(mini-batch gradient descent)。看名字就知道,这三种的区分,就是看要用多少数据来计算梯度方向。

    批量梯度下降(batch gradient descent),也叫Vanilla gradient descent,是用全部数据来计算梯度方向,,计算量比较大,但是单次迭代看方向更准。

    随机梯度下降(stochastic gradient descent)每一轮都会用一个数据来计算梯度方向,,比较适合做online learn,计算很简单,但是更新方向不稳定,可能波动会很大,需要学习率配合来达到收敛。下图描述的就是sgd的下降情况,他是在小范围呢波动的情况下,整体趋势下降。

    小批量梯度下降(mini-batch gradient descent)介于上面两个方法之间,,计算量介于前两者之间0,方向波动比sgd小。

     

    在海量训练数据的情况下,sgd相对于batch在整体收敛速度方面有很大的优势,这也使它在现在的实际应用中更为常见一些;在收敛性质方面,sgd是依期望收敛域最小值附近,这个证明比较复杂,会基于几个基本假设,比如梯度变化不能太剧烈,梯度选择的分布情况等,还会涉及强凸函,又牵扯到很多数学上计算boundary的过程,在这里不再详细描述,感兴趣的同学,可以参考《Optimization Methods for Large-Scale Machine Learning》 一文中的 ”4 Analyses of Stochastic Gradient Methods“中的详细证明。l领一个简单版本的证明请见慕容熙熙的博客中”随机梯度下降“一文。(http://www.cnblogs.com/murongxixi/p/3467365.html)

    PS:为了防止那天404,我们把简单的证明过程贴过来。copyright by 慕容熙熙。

    可以看到,这个证明基本上也是基于几个假设:梯度的期望值不能太大,初始点的值不能距离最优值不靠谱的远,另外证明过程中隐含了F的凸函数特性。当满足这些假设后,我们选取合适的学习率让,它满足上面的条件,即可以得到SGD依照期望收敛的证明。

     

    速度方面,海量训练数据情况下,sgd有着比较明显的优势,我们看下表来得到收敛的速度以及误差的情况。

    可以看到,sgd的搜索速度,基本和迭代次数相关,而batch的梯度下降,和训练数据n成正比。具体细节,可以参考上面提到的综述。


    理性放一旁!感性的认识。。

    看证明比较痛苦,不过没关系,我们可以直接的从感官上来理解一下为什么sgd比bgd的收敛,一般情况下会快一点。

    我们看一个一般的需要优化的目标函数,如下:

    我们假设L函数是简单的单变量2次形式,我们又有6个样本点,每个样本点都有点噪声波动,暂时不考虑正则部分欧米伽的话,于是我们有了下图:

    其中黑色的是每个样例的单独的图像,对应sgd一次迭代时的某一种选择,而红色的是所有的样例合起来再取均值的图像,对应的最终我们要求得目标函数,也就是bgd时的图像。

    当我们初始化了一个x之后,如果x比较靠近数轴的左边(或者比较靠近右边),比如x取的值小于-10,那么无论你随机取到哪一个样例来做sgd,x的更新方向都和做bgd时一样,是向右的。但是sgd得到这个向右的更新方向,要比用bgd少算了5次。看到了吧,计算量变少了!这时间我们跟新x,比如x变成了-5,那么后面的计算同理,无论下一轮sdg取哪个样例来计算方向,方向还是对的,你有,有少算了5次。。。那是不是一直会这样的?不是的,当x更新的比较接近最优值了,比如x在4左右,那么在使用sgd的时候,就有很大概率会取得错误的方向,这时候就看出了bgd的好处,它的方向是稳定了,但是得到这个方向还是要经过N此计算才可以。反观sdg,虽然有不小的概率取得错误的方向,但是,取得对的方向的概率还是会比取得错误的概率大一些(正确方向刚好是sgd的期望),在这样的情况下,如果我们能让步长不太大,那么x更新的范围就不会太大,收敛情况的震荡的就不会太厉害了,多迭代几轮,或者接受一个可以忍受的小误差,我们还是能很快得到最小值时x*的近似解的,这个计算每次只需要一次计算,及时做很多次,只要比N小,还是划算,这也就是sgd在很多时候,收敛的速度都比bgd快的原因了。

    这中采样的方式,使得sgd的波动在取值在最优值附近的时候难以避免,整个收敛因为采样的原因呈现波动性,随着学习率的不断降低,波动的幅度减小。整个收敛的过程如下图所示。

     

    这里要注意的是,当梯度变小时,sgd要求学习率也要变得很小,这个会导致sgd对x的更新变慢,但是由于只有梯度很小时才有这个问题,这个时候x的值已经比接近最优值x*了,所以还是可以接受的。实际中,使用sgd的时候,经验上我们也推荐使用更小的学习率,来保证收敛。

     

    牛顿法(Newton's Method)

    牛顿法,也叫牛顿迭代法,也是以迭代方式来求函数的根,变通一下就可用于求极值。它基本思想是从一个初始点出发,不断在当前点xk处用切线近似函数f(x),并求得该切线与x轴的交点作为下一次的迭代初始点xk+1,直到找到 f(x)=0的近似解为止。对于二次可微函数f(x),如果我们是对其导数来求0值点,那么对于也就相当于求得了原先f(x)的驻点,如果f(x)是凸函数,也就求到了f(x)的极值了。因此Newton法可用于二次可微函数f(x)的最优化问题。


    假设我们要最优化的函数为f(x),我们在xk处对f(x)进行二阶的泰勒展开:

     

    Bk就是f(x)在kx对应的hessian矩阵,我们可以用

    的右边来拟合f(x),我们称之为q(x)。于是问题就化成了,在xk附近找到一个增量△x,使得q(x)取得极小值,所以变量就变为△x。我们对q(△x)求导可得xk+1=xk+△x处的导数为

    要求q(xk+1)为最值,那么q(xk+1)==1,所以有

    这样,我们通过解方程,或者直接求海森矩阵的逆来计算新的xk+1的值即可。

    牛顿法的迭代算法流程如下:

    牛顿法的收敛速度很快,二次函数的话(正定),可以直接1次找到最优解。这点很不错,但是也有缺点:1.计算比较多。每个迭代都要求一阶导数,二阶导数(海森矩阵)以及海森矩阵的逆矩阵。2.要求函数可导,海森举证可逆(海森矩阵非奇异,若果奇异了,就需要修正)。3.迭代有可能出现循环(),这个就尴尬了,有时候虽然得到了行的xk+1,但是却并不能使f(xk+1)<f(xk)。。。后面这几种情况下,我们可以将这一轮的牛顿法迭代退化为梯度下降法,具体的细节这里不详细说明了,大家感兴趣可以自己查阅后面提到的参考资料;另外的解决方案,就是拟牛顿法。

     

    拟牛顿法(Quasi-Newton's Method)

    拟牛顿法是一些列方法的总称,顾名思义,这些方法都是通过”模拟“牛顿法的方法来解决最优化问题的,它们模拟了牛顿法中搜索方向(可以叫作”牛顿方向“)的生成方式。

    前面提到了,牛顿法在每一次要得到新的搜索方向的时候,都需要计算海森矩阵。这个计算在自变量维数非常大的时候非常耗时,为了优化这一计算,拟牛顿法就应运而生了。它们采用了一定的方法来构造与海森矩阵相似的正定矩阵,而这个构造方法计算量比牛顿法小很多了。

    那用海森矩阵的相似矩阵代替的话,优化效果会变差么?简单来说,我们知道牛顿方向本身就是根据泰勒公式的二阶拟合来推断下降方向的,其中已经舍弃了高阶无穷小的部分,本身就是一种近似了,如果海森矩阵的相似矩阵跟原始的海森矩阵相差很小,那么这个替代计算出的,也应该还是下降方向的近似,不会差太远,不会对下降方向的选择造成很大影响。实际上,这个相似矩阵的替换,不但不会降低效果,反而很多时候效果还会变好。。。根据牛顿迭的原理,我们可以得到

    进而可以得到

    左边的部分就是Y,也就是f(x)沿着q'(x)方向的变化量,如果要函数下降,就需要这个值是负数,也就是右边是负数。也就是要求Bk是正定矩阵。在远离最小点的区域,牛顿法求得的B不一定是正定矩阵,而拟牛顿法中我们找的B的相似矩阵H就可以是正定矩阵,保证了下降。当靠近最小点的区域,那么B和H很接近,都有二阶收敛速度。所以整体上来说,这种相似替代,很可能会有差不多,甚至更好的收敛。

    一般的拟牛顿算法流程如下:

    下面就让我们看看几种有名的拟牛顿算法。

     a.DFP方法

    DFP方法应该是历史上的第一个拟牛顿方法,是William C.Davidson在1959年发明的,并由Roger Fletcher和Michael J.D.Powell完善,因此这个方法就称为DFP。我们的目标是,在第k个迭代过程中,我们希望从上一个迭代的海森矩阵Bk-1的基础上,得到当前点xk的海森矩阵Bk,在计算出牛顿方向。在第k个迭代中,我们已知的有xk,xk-1,f'(x),f'(xk-1),要通过它们来计算出Bk,之后通过它找到xk+1。DFP通过求解这个优化问题来通过Bk-1求得Bk

    这个最优化问题希望找到一个B,和Bk-1尽量接近,B本身是对称矩阵,让后要满足B(xk-xk-1)=yk-1,这是因为B本身应该满足在xk的比较小的邻域内,有

    而xk-1距离xk就非常近,因此将xk-1带入,也应该满足这个性质。在一整理,就得到了上面的第二个约束。

    这个方程有解析解如下:

    这个等式的解法略复杂,在这里不再给出,有感兴趣的同学可以参考最优化理论与方法(袁亚湘 孙文瑜)的第五章。

    这个迭代能保证f一直下降么?我们知道f要下降,就要B正定,以下资料给出了这种迭代下B正定的证明(这里是B的逆矩阵来迭代的推导过程)。

    有了上面的解法,容易想到,B能推的话,当然B的逆矩阵应该也能推!(这里的推导过程留给下面的BFGS来展示)

    优点:不用每次计算海森矩阵,收敛速速很快

    缺点:要计算逆矩阵(*),存储空间大

    b.BFGS方法

    最初的DFP算法是每次求得海森矩阵个的近似,值后再求逆矩阵计算拟牛顿方向,每次求逆比较费力,这一步可以优化么?我们能直接近似得到海森矩阵逆矩阵的近似么?1970年,四位大师Charles G.Broyden,Roger Fletcher,Daniel Goldfarb,David F.Shanno各自独立的发现了这个可行性,并发明了BFGS算法。把增量的求解B转换成了增量的求解B的逆矩阵H。于是乎和DFP的优化问题相似,我们的优化问题变成了如下形式:

    这个几乎和DFP的优化问题是一样的,只是将s和y的位置互换了而已。相应的,问题的解也有相似的形式:

    下面给一个BGFS的逆问题的证明过程,如果我们假设Bk=Bk-1+▽B的话,那么我们要求▽B对称,且尽量小,如果在保证第二个约束,那么基本就能满足上式子。要▽B尽量小,我们最容易想到的就是可以限制它的秩,比如我们让▽B的秩为2,于是▽B就可以写成 aUUt+bVVt,在带入约束,有

    对于这样的公式,U和V可以有无数组解,于是我们可以很容易想到一组解,让

    其中两个括号内的乘机为实数,所以可以设

    带入可得

    解得

    最终得到

    于是我们得到了递推式

    各种拟牛顿算法的主要差异在于近似Hessian矩阵的更新策略,下面的列表列出了部分主流的拟牛顿算法的迭代更新规则。


    BFGS保留并更新H,进而通过H*f'达到牛顿方法的收敛速度。这个在维度不大的时候还可以,但是当维度比较大的时候,保存H需要O(n^2)的存储空间,这个比较被动,因此出现了L-BFGS算法。

    优点:不用每次计算海森矩阵,收敛速速很快,收敛稳定

    缺点:存储空间大


    c.L-BFGS

    L-BFGS就是Limited-memory BFGS,顾名思义,就是更少使用内存的BFGS。BFGS要存储海森矩阵个的逆,这个需要O(n^2)的存储空间,如果feature有10W维,每个fearture用double存储,那么总共需要100000*100000*8/(10^9)约80G的空间,这个存储要求的空间太多,为了减少内存,L-BFGS算法诞生了。它通过2重迭代,保存之前m个步骤之中的y和s,用它们来近似出牛顿方向,这样就省去了存储海森矩阵的逆,它把存储降低到了O(m*n)。一般情况下m设置为3-20之间。

    我们让


    则根据BFGS中Hk和Hk-1的关系,我们有如下的展开:


    最终可以得到

    于是我们看到,可以通过上面的公式,用s和y,以及一个之前的H,推导出现在的H。这个过程可以通过2重循环实现,具体的作法如下:

    通过分析可以看到,第一个循环内,我们假定qi为第i轮的q的值,假定ai为第i轮的a的值,那么可以得到


    这个就是上面每一个+号分割的项的右半边,之后q再乘上H(k-m),进入第二轮循环,我们可以得到


    这样展开下去,最终就可以的得到Hk了。看到这里可能有同学会问,这里面还有个H(k-m)那,这个不是还是n*n的么?对,为了不保存这个n*n,我们需要找到一个H的近似,且占用空间要是n级别的。因为上面的2重循环操作都是矩阵乘法(本质上就是一系列的伸缩和旋转),那么比较相似的矩阵经过这一些列操作后,还是和相似的。其次解决占用空间的问题,我们可以让H变化呢过对角矩阵,这样存储空间就变为n了。实际解决中会尝试多种H的近似,实践上使用


    效果比较好,因为刚好是梯度的梯度的逆,用它来拟合海森矩阵的初值比较合理。H0的近似使用单位矩阵就可以。这样一来,连这n数也不用存啦,可以通过计算得到,所以总的空间复杂度变成了O(m*n)。


    常用的梯度下降算法改进(深度学习中)

    神经网络的训练一般都离不开梯度下降,由于网络本身比较复杂,数据的维度也很大,所以实际应用上一般都不选择二阶的方法(比如牛顿法),而且以sdg来进行训练居多。

    但是一般的sdg有一些问题,比如:1.学习率(步长)不好定 2.为了收敛,学习率往往会使用类似退火算法来逐步缩小,但是这个缩小往往是按照预先制定的计划,或者是根据某个阈值来进行逐步收缩的,这里就牵扯到设定这个计划,或者设定阈值需要有比较多的经验,而且不能自动的根据数据来匹配。3.学习率会一视同仁的作用在所有param上。4.sdg往往会收敛在局部最小,跟严重的是面对马鞍形面时,sdg很难走出鞍点,因为鞍点附近的梯度都非常小。

    针对上面的几个弱点,有了下面一些优化的算法。


    Momentum

    Momentum(动量)方法通过将之前的梯度信息,用到本次更新中,来带来更好的更新方向。这相当于考虑了更多之前的方向信息(更趋向全局信息)来生成本次更新的方向。公式和图像如下:

    一般经验上把设定为0.9左右。

    这个可以想成圆球在椭圆形的碗里滚到最低点的过程类似:动量每次都在累积,小球越来越快。每次梯度一致的方向上,速度越来越大,不一致的方向上,累积较小,甚至减小。这个最终使得收敛加速,震荡减少。

      "With Momentum update, the parameter vector will build up velocity in any direction that has consistent gradient."

    Nesterov Momentum(Nesterov accelerated gradient)

    Nesterov动量跟上面的动量法类似,区别在于在计算新梯度的时候,没有用当前的,而使用了距离更新后参数更接近的来计算,具体公式如下:


    他和一般动量法的区别,可以看以下图像解释:


    这个更新方法,可以更快的估计更新后的点的梯度,从而更快的知道是否跑过了。。。从而减少震荡,可以看下面的图来理解下:

    蓝线是Momentum的一次更新,可以看到他先算了当前的梯度,之后和之前的剩余(大蓝线)加起来。而NAG则是直接看剩余(棕色箭头),之后计算这个点的梯度(红色),在更新参数(绿箭头)。注意:第二次更新,红箭头回头了!!!这说明,过了,往回走吧~~,从而可以看出,NAG可以更更好的防止震荡问题。


    上面的算法我们已经根据之前的多个梯度,通过调整参数更新方向,使收敛加速啦~~~下面我们在看看针对不同参数的重要度,能否通过算法来调整它们更新的大小。


    Adagrad

    Adagrad的想法很简单:更新次数越频繁的参数,应该快到达了微调阶段,后面的学习率要更小;更新次数比较少的,刚开始向最优点移动,学习率可以大一些。这些在sparse的数据里尤为明显。adagrad的公式如下:

    t是轮数,i是第i个参数,是当前的梯度,而是之前t步的g的平方和,是防止除0的,一般设置成1e-8。


    Adadelta

    Adagrad中,因为分母部分一直在增加,训练轮数多了之后,会导致学习率变得非常非常小,导致收敛很慢的问题。另外全局的默认学习率也需要人工给定。

    针对第一种问题,Adadelta做出了改进,让最近几轮(window)的g决定衰减,之前的g使之影响最小化,同时不在使用梯度的平方和来做累积,转而使用窗口中的梯度平方和的均值作为影响的主要项。简化起见,可以给了一个乘数因子来模拟窗口的作用,利用这个乘数因子来计算衰减,具体公式如下:

    这样会使更新率的减低速度得到缓解,从而解决了第一个问题。但是通过上面的公式可以看到,更新的参数单位有点不对了,因为现在的分母部分有了单位。。。按照梯度的定义,根据牛顿迭代法,我们知道梯度乘以x的变化量,才是y的变化量拟合,之前的学习率是没有单位的,所以梯度的单位还在,但这里梯度的单位似乎消掉了。这咋办?简答的做法是把分母部分的单位直接去掉,搞成标量,但是有点粗暴哈。Adadelta的发明者考虑了另一种方法,他又计算了一个参数的平方累积,用来衡量参数本身的更新情况(其实用的也是均值)来加入影响,并且使单位问题的到解决。


    这样一搞,我们发现,不但单位问题解决了,隐隐的,公式还有了点动量累积的感觉~~~而且后续的学习率也不用人工给出啦。好的,除了学习率的自动退火,之前的梯度累积也被考虑到了更新参数的公式中。PS:因为在计算本轮参数之前,我们是没有本轮参数与之前参数的平方均值的(这句话说得比较绕),所以我们用前一次的来代替。

    RMS(x)是平方和求根函数。


    RMSprop

    RMSprop是Geoff Hinton在他的“neural Networks for ML”课程中提到的算法,基本和Adadelta的第一部分一样,公式如下:


    这里,学习率推荐值是0.001。

    同上面Adadelta类似,我们也可以把之前的theta搞进去,这里也可以用RMS,大同小异哈。

    Adam

    Adaptive Moment Estimation(Adam,自适应矩估计),它也是一种可以自动调节不同参数学习率的算法,和Adadelta类似,还包含了类似Momentum保存之前累积的梯度的做法,这样就让Adam可以即更新方向,有自动更新学习率。它保存了参数的梯度累积,以及梯度平方的累积,在根据他们的期望估计新的参数在哪里。

    是梯度方向的累积,可以对应g的一阶矩估计,是g^2的累积,对应g的二级估计,我们希望通过当前的m和v,估计出g和g^2的期望,然后按照

     

    来估计参数的更新。

    我们可以得到,进而得到

    最终得到了=/,即。同样的推理,可得。最终的跟新规则如下:




    经验上,我们设置  β1=0.9,β2=0.999,ϵ=1e-8。实际上用的时候,我们可以直接m和v替换m_head和v_head,实践上效果和速度没有太大区别。


    几个方法的可视化比较

                                   图1

    上面的等高线图图1可以直观的看出几个算法的特性:SDG(带固定学习率退火的)比较慢;Adagrad,Adadelta,RMSprop3个算法可以调整学习率,很快找到朝向全局的最低方向;Momentum,NAG刚一开始的时候由于步子大,过了,但是找到合理方向后,在正确方向上的累积,导致最终的收敛速度还不错。


                                  图2

    图2展现了马鞍形表面在鞍点附近(一维梯度是正的,一位梯度是负的)的下降情况。可以看到,普通的SGD到达鞍点之后就跪了(梯度基本为0了),Adagrad,Adadelta,RMSprop可以快速突破,但是Adagrad会越来越慢,Momentum,NAG由于步子大,刚开始呈现震荡(对称),但是找到正确方向之后,下降速度很快。

     

    最终的实践结论,Adadelta,RMSprop,Adam都还不错,不过也有很多就是用的naive的SDG(尤其是object functin比较简单的,凸的情况),不过针对神经网络的,还是建议用优化过的梯度下降算法,正如下面说的: 

    “Consequently, if you care about fast convergence and train a deep or complex neural network, you should choose one of the adaptive learning rate methods.”


    总结

    以上就是我们平时常用的一阶,二阶的优化方法,另外还有共轭方向法,共轭梯度法等方法,这里就不设计了,感兴趣的同学可以查查书和资料。

    我们的目的是让大家了解常用的一般的优化的方法,在实践中清楚其原理,进而可以轻松驾驭,或者根据实际情况优化自己的算法提供些许信息,能达到这个目的就ok了。


    参考资料

    最优化理论与方法 (袁亚湘 孙文瑜)

    最优化理论与方法 (傅英定 成孝予 唐应辉)

    http://www.cnblogs.com/jeromeblog/p/3801025.html

    http://www.codelast.com

    http://www.tianyancha.com/research/LR_intro.pdf

    http://imgur.com/a/Hqolp

    http://sebastianruder.com/optimizing-gradient-descent/

    https://homes.cs.washington.edu/~galen/files/quasi-newton-notes.pdf

    http://www.cnblogs.com/xinchrome/p/4964930.html

    https://arxiv.org/abs/1606.04838

    http://www.cnblogs.com/murongxixi/p/3467365.html

    https://zhuanlan.zhihu.com/p/21486826

    https://zhuanlan.zhihu.com/p/22810533

    https://blog.slinuxer.com/2016/09/sgd-comparison

    展开全文
  • 常用优化算法简述

    千次阅读 2018-10-13 16:01:54
    本文介绍优化问题的基本概念与常用优化算法,内容持续更新中。 文章目录最优化问题简述无约束问题最优化方法线性规划约束问题最优化方法可行方向法(直接法)罚函数法(间接法)乘子法(间接法)序列二次规划法...

    本文介绍优化问题的基本概念与常用的优化算法,内容持续更新中。

    最优化问题简述

    优化问题可概括为如下一般形式:

    • 求设计变量: x1,x2,,xnx_{1},x_{2},\dots,x_{n}
    • 极小化目标函数: f(x1,x2,,xn)f(x_{1},x_{2},\dots,x_{n})
    • 满足约束条件:gu(x1,x2,,xn)0,u=1,2,,pg_{u}(x_{1},x_{2},\dots,x_{n})\leq 0,\quad u=1,2,\dots,p hv(x1,x2,,xn)=0,v=1,2,,mh_{v}(x_{1},x_{2},\dots,x_{n}) = 0,\quad v=1,2,\dots,m
      根据是否满足约束条件可以把设计点分成可行点(又称内点)和非可行点(又称外点),根据约束边界是否通过某个设计点,又可将约束条件分成该设计点的起作用约束不起作用约束。通常一个设计问题只有一个目标函数,这就是单目标最优化问题

    求解最优化问题的求解方法是针对比较复杂的极值问题提出的一种区别于解析法的数值法,或者说迭代算法。迭代法一般采用如下格式:Xk+1=Xk+αSkX^{k+1} = X^{k} + \alpha S^{k} 迭代算法产生的点列所对应的函数值严格地单调递减,并且最终收敛于最优化问题的极小点时,称此迭代算法具有收敛性。判断迭代点是否达到给定精度要求的判别式称为最优化算法的终止准则。常用的终止准则有以下三种:

    1. 点距准则:Xk+1Xkε\|X^{k+1}-X^{k}\|\leq \varepsilon
    2. 值差准则:f(Xk)f(Xk+1)ε|f(X^{k})-f(X^{k+1})|\leq \varepsilon 或者 f(Xk)f(Xk+1)f(Xk)ε\left| \frac{f(X^{k}) - f(X^{k+1})}{f(X^{k})} \right| \leq \varepsilon
    3. 梯度准则:f(Xk+1)ε\|\nabla f(X^{k+1})\|\leq\varepsilon

    关于最优化研究的数学基础读者可参考此文,此处省略。

    对于无约束问题,由微积分理论可知,一元函数 f(x)f(x)xkx_{k} 处取得极值的必要条件是函数在该点的一阶导数等于零,充分条件是对应的二阶导数不等于零。类似的,多元函数 f(X)f(X) 在点 XkX^{k} 取得极值的必要条件是函数在该点的所有方向导数都等于零,即函数在该点的梯度等于零:f(Xk)=0\nabla f(X^{k}) = 0 根据泰勒展开式,函数在该点的近似式整理后可得:f(X)f(Xk)=12[XXk]T2f(Xk)[XXk]f(X) - f(X^{k}) = \frac{1}{2}[X-X^{k}]^{T}\nabla^{2}f(X^{k})[X-X^{k}]XkX^{k} 为函数的极小值点时,因为有 f(X)f(Xk)&gt;0f(X) - f(X^{k})&gt;0 ,故必有 [XXk]T2f(Xk)[XXk]&gt;0[X-X^{k}]^{T}\nabla^{2}f(X^{k})[X-X^{k}] &gt;0 即函数的二阶导数矩阵必须是正定的,这就是多元函数取得极小值的充分条件。一般来说,上式对最优化问题只有理论意义,因为就实际问题而言,由于目标函数比较复杂,二阶导数矩阵不容易求得,正定性判断更加困难。因此,具体的最优化算法只将导数作为判断极小点的终止准则。关于无约束问题的极值条件等更详细内容请参考此文

    约束问题的极值条件比无约束问题复杂得多。下面就等式约束和不等式约束两种情况稍加讨论,详细讨论请参考此文

    对于等式约束问题minf(X)\min f(X) s.t. hv(X)=0,v=1,2,,m\text{s.t. } h_{v}(X)=0,\quad v=1,2,\dots,m 建立如下拉格朗日函数:L(X,λ)=f(X)+v=1mλvhv(X)L(X,\lambda) = f(X) + \sum_{v=1}^{m}\lambda_{v}h_{v}(X)L(X,λ)=0\nabla L(X,\lambda) = 0 得:f(X)+v=1mλvhv(X)=0\nabla f(X) + \sum_{v=1}^{m}\lambda_{v}\nabla h_{v}(X) = 0 λv不全为零\lambda_{v} \text{不全为零} 这就是等式约束问题在点 XX 取得极值的必要条件,即在等式约束的极值点上,目标函数的负梯度等于诸约束函数梯度的非零线性组合

    对于不等式约束问题minf(X)\min f(X) s.t. gu(X)0,u=1,2,,p\text{s.t. } g_{u}(X)\leq 0,\quad u=1,2,\dots,p 引入 pp 个松弛变量 xn+u0x_{n+u}\geq 0 可将不等式约束转化为等式约束:minf(X)\min f(X) s.t. gu(X)+xn+u2=0,u=1,2,,p\text{s.t. } g_{u}(X) + x_{n+u}^{2} = 0,\quad u=1,2,\dots,p 建立这一问题的拉格朗日函数 L(X,λ,Xˉ)=f(X)+u=1pλu[gu(X)+xn+u2]L(X,\lambda, \bar{X}) = f(X) + \sum_{u=1}^{p}\lambda_{u}[g_{u}(X) + x_{n+u}^{2}] 同样令其梯度为零,即 L(X,λ,Xˉ)=0\nabla L(X,\lambda, \bar{X}) = 0 则有 LX=f(X)+u=1pλugu(X)=0Lλ=gu(X)+xn+u2=0LXˉ=2λuxn+u=0,u=1,2,,p\begin{aligned} &amp;\frac{\partial L}{\partial X} = \nabla f(X) + \sum_{u=1}^{p}\lambda_{u}\nabla g_{u}(X) = 0 \\ &amp;\frac{\partial L}{\partial \lambda} = g_{u}(X) + x_{n+u}^{2} = 0 \\ &amp;\frac{\partial L}{\partial \bar{X}} = 2\lambda_{u}x_{n+u} = 0,\quad u=1,2,\dots,p \end{aligned} 不等式约束问题的极小点要么在可行域内,要么在约束边界上取得,其条件概括为 f(X)+iIkλigi(X)=0\nabla f(X) + \sum_{i\in I_{k}}\lambda_{i}\nabla g_{i}(X) = 0 λi0,iIk\lambda_{i}\geq 0, i\in I_{k} 式中 gi(X)0(iIk)g_{i}(X)\leq 0 (i\in I_{k}) 为点 XX 的起作用约束。上述条件也成为Kuhn-Tucker条件,简称 K-T条件。该条件是约束问题极值的必要条件,其意义可概括为在不等式约束问题的极小点上,目标函数的负梯度等于起作用约束梯度的非负线性组合。在一般情况下,K-T点就是约束问题的最优点。

    举个例子,用K-T条件判断点 Xk=[2,0]TX^{k}=[2,0]^{T} 是否是一下问题的最优点:minf(X)=(x13)2+x22\min f(X) = (x_{1}-3)^{2} + x_{2}^{2} s.t. g1(X)=x12+x240g2(X)=x20g3(X)=x10\begin{aligned} \text{s.t. }&amp;g_{1}(X) = x_{1}^{2} + x_{2} -4\leq 0 \\&amp;g_{2}(X) = -x_{2}\leq 0 \\ &amp; g_{3}(X) = -x_{1}\leq 0\end{aligned} 解:由于g1(Xk)=22+04=0g2(Xk)=0g3(Xk)=2\begin{aligned} &amp;g_{1}(X^{k}) =2^{2} + 0-4=0 \\ &amp;g_{2}(X^{k})=0 \\ &amp;g_{3}(X^{k})=-2 \end{aligned} 可知点 XkX^{k} 的起作用约束是 g1(X)0,g2(X)0g_{1}(X)\leq 0, g_{2}(X)\leq 0,在点 XkX^{k}f(Xk)=[2,0]Tg1(Xk)=[4,1]Tg2(Xk)=[0,1]T\begin{aligned} &amp;\nabla f(X^{k}) = [-2,0]^{T} \\ &amp;\nabla g_{1}(X^{k})= [4,1]^{T} \\ &amp;\nabla g_{2}(X^{k}) = [0,-1]^{T} \end{aligned} 将上式代入 K-T条件的第一式有 f(Xk)=λ1g1(Xk)+λ2g2(Xk)-\nabla f(X^{k}) = \lambda_{1}\nabla g_{1}(X^{k})+\lambda_{2}\nabla g_{2}(X^{k}) 解得 λ1=λ2=0.5\lambda_{1} = \lambda_{2} = 0.5,均大于零,满足K-T条件,说明 XkX^{k} 就是所给约束最优化问题的最优点。

    无约束问题最优化方法

    求解无约束优化问题的下降迭代解法具有统一的迭代格式,其基本的问题是选择搜索方向和在这些方向上进行一维搜索。根据搜索方式不同可将优化方法分为导数法(或称解析法) 和 **模式法(或称直接法)**两大类。

    利用目标函数的一阶导数或二阶导数信息构造搜索方向的方法称为导数法。由于导数是函数变化的具体描述,因此导数法的收敛性和收敛速度都比较好。模式法通过几个已知点上的函数值的比较构造搜索方向,由于构成搜索方向的信息仅仅是几个有限点上的函数值,因此难以得到较为理想的搜索方向。

    常见的导数法如梯度法、牛顿法、拟牛顿法和共轭梯度法可参考此文,此处从略。常见的模式法如鲍威尔法此处不作介绍。

    线性规划

    目标函数和约束函数都是线性函数的最优化问题成为线性规划问题,对应的算法成为线性规划算法。线性规划问题的可行域是一种封闭的凸多边形或凸多面体,它的最优解一般位于可行域的某一顶点上,而可行域的顶点是有限的。

    线性规划问题的数学模型一般包含一组等式约束和一组设计变量的非负性约束:minf(X)=j=1ncjxj\min f(X) = \sum_{j=1}^{n}c_{j}x_{j} s.t. j=1naijxj=bi,i=1,2,,m\text{s.t. } \sum_{j=1}^{n}a_{ij}x_{j} = b_{i},\quad i=1,2,\dots,m xj0,j=1,2,,nx_{j}\geq 0,\quad j=1,2,\dots,n 或者写成向量形式:minf(X)=CTX\min f(X) = C^{T}X s.t. AX=B\text{s.t. } AX = B xi0,i=1,2,,nx_{i}\geq 0,i=1,2,\dots,n 一般情况下, m&lt;nm&lt;n。如果实际问题中还存在其他不等式约束条件存在,则要在这些不等式约束条件中分别引入一个非负变量,使不等式变为等式,这种新加入的非负变量称为松弛变量

    求解线性规划问题最优解通常采用单纯形算法,这是一宗基于基本可行解的变换原理构成的一种线性规划算法,一般采用列表变换的形式进行,所列表格称为单纯形表,对应的算法亦称为单纯形表法。具体步骤此处不作介绍。

    约束问题最优化方法

    求解约束最优化问题的关键在于如何处理各种约束条件,其求解方法可分为直接法和间接法两类。在迭代过程中逐点考察约束,并使迭代点始终局限于可行域之内的算法成为直接法。把约束条件代入目标函数,使约束最优化问题转化为无约束最优化问题求解,或者将非线性问题转化为相对简单的二次规划问题或线性规划问题求解的算法称为间接法

    可行方向法(直接法)

    可行方向法用来求解如下不等式约束问题:minf(X)\min f(X) s.t. gu(X)0,u=1,2,,p\text{s.t. } g_{u}(X)\leq 0, u=1,2,\dots,p 这种方法的基本思想是从可行域内一个可行点出发,选择一个合适的搜索方向和步长因子,使下一个迭代点既不超出可行域,又使目标函数的值下降得尽可能多。既使目标函数下降,又指向可行域内的下降可行方向 SS 必须同时满足以下关系:[f(Xk)]TS&lt;0[\nabla f(X^{k})]^{T}S&lt;0 [gi(Xk)]TS&lt;0[\nabla g_{i}(X^{k})]^{T}S&lt;0 式中 IkI_{k} 为点 XkX^{k} 的起作用约束的下标集合。

    罚函数法(间接法)

    罚函数法是一种将约束最优化问题转化为无约束最优化问题求解的算法。构造如下无约束问题:minϕ(X,rk1,rk2)=f(X)+rk1G[gu(X)]+rk2H[hv(X)]\min\phi(X,r_{k1},r_{k2}) = f(X) + r_{k1}G[g_{u}(X)] + r_{k2}H[h_{v}(X)] 当点 XX 在可行域之外时,对目标函数值加以惩罚,或者当点 XX 位于约束边界附近时,这两项的函数值趋于无穷大,这相当于在约束边界筑起一道围墙,迫使迭代点在可行域内移动。

    罚函数法分为外点法内点法,以及结合二者的混合法。此处不作具体介绍,更多细节请参考此文

    乘子法(间接法)

    惩罚函数法具有方法简单、使用方便等优点。但它存在固有的缺点,即随着惩罚因子越来越趋向极限值,惩罚函数也变得越来越病态,从而给计算带来了很多困难。乘子法可以克服此困难,其构造方法与罚函数法类似,具体介绍参考此文

    序列二次规划法(间接法)

    序列二次规划(SQP)算法是将复杂的非线性约束最优化问题转化为比较简单的二次规划问题求解的算法。所谓的二次规划问题就是目标函数为二次函数,约束函数为线性函数的最优化问题。序列二次规划算法是目前求解非线性约束最优化问题的常用算法,此处不作详细介绍。

    遗传算法

    遗传算法是一种自适应全局最优化概率搜索算法。在遗传算法中,将设计变量 X=[x1,x2,,xn]TX = [x_{1},x_{2},\dots,x_{n}]^{T}nn 个同类编码,即:X:X1,X2,,XnX:X_{1},X_{2},\dots,X_{n} 其中每一个 XiX_{i} 都是一个 qq 位编码符号串。符号串的每一位称为一个遗传基因,基因的所有可能取值称为等位基因,基因所在的位置称为该基因的基因座。于是,XX 就可以看作由 n×qn\times q 个遗传基因组成的染色体,也称个体 XX。由 mm 个个体组成一个群体,记作 P(t)(t=1,2,,m)P(t)(t=1,2,\dots,m)

    最简单的等位基因由 0011 表示,相应的染色体或个体就是一个二进制符号串,称为个体的基因型,与之对应的十进制数称为个体的表现型。遗传算法使用适应度这个概念来度量群体中各个个体的优劣程度,并以个体适应度的大小,通过选择运算决定哪些个体被淘汰,哪些个体遗传到下一代。再经过交叉变异运算得到性能更加优秀的新个体和群体,最终得到最佳个体,即最优化问题的最优解。

    遗传编码

    把原问题的可行解转化为个体符号串的方法称为编码。最常用的方法是二进制编码

    二进制编码所构成的个体基因是一个二进制符号串,符号串长度与要求的精度有关。假设某一个参数的取值范围是 [Umin,Umax][U_{min},U_{max}],若用长度为 ll 的二进制符号串来表示,总共产生 2l2^{l} 个不同的编码。编码精度为:δ=UmaxUmin2l1\delta = \frac{U_{max}-U_{min}}{2^{l}-1} 假设某一个个体的编码是 X:blbl1b2b1X:b_{l}b_{l-1}\cdots b_{2}b_{1} 则对应的解码公式是:x=Umin+(i=1lbi2i1)UmaxUmin2l1x = U_{min}+\left(\sum_{i=1}^{l}b_{i}\cdot 2^{i-1}\right)\frac{U_{max}-U_{min}}{2^{l}-1}

    个体适应度

    适应度较高的个体遗传到下一代的概率较大。度量个体适应度的函数称为适应度函数 F(X)F(X) ,一般由目标函数或惩罚函数转换而来。例如对于极小化问题:minf(X)\min f(X) F(X)={Cmaxf(X),f(X)&lt;Cmin0,f(X)CmaxF(X)= \left\{\begin{aligned} &amp;C_{max} - f(X),\quad &amp;f(X)&lt;C_{min} \\ &amp;0, &amp;f(X)\geq C_{max} \end{aligned}\right.

    遗传运算

    tt 代群体记作 P(t)P(t),遗传算法的运算就是群体的反复演变的过程。对于群体 P(t)P(t) ,对其进行选择、交叉和变异运算,以求得最优的个体,即问题的最优解。

    1. 选择运算

    遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作。最常见的方法是比例选择运算,即个体被选中并遗传到下一代的概率与它的适应度的大小成正比。设群体大小为 MM,个体 ii 的适应度为 fif_{i},则个体 ii 被选中的概率 PisP_{is} 为:Pis=fi/i=1MfiP_{is} = f_{i}/\sum_{i=1}^{M}f_{i}

    2. 交叉运算

    交叉运算模仿生物交配重组的过程,即两个个体交换部分基因,形成两个新生代个体。目前最常用的方法是单点交叉运算交叉

    3. 变异运算

    变异运算将个体编码串中的某些基因座上的基因值用它的不同等位基因来替换,从而产生新的个体。最简单的方法是基本位变异。基本位变异操作是在个体编码串中依变异概率 PsP_{s} 随机指定某一位或某几位基因座上的基因值作变异运算。
    变异

    展开全文
  • 深度学习最常用的算法:Adam优化算法

    千次阅读 2019-04-23 22:25:51
    Adam优化算法是随机梯度下降...本文分为两部分,前一部分简要介绍了Adam优化算法的特性和其在深度学习中的应用,后一部分从Adam优化算法的原论文出发,详细解释和推导了它的算法过程和更新规则。我们希望读者在读完...
  • 在深度学习训练模型的时候...本篇文章主要介绍一下常用优化算法 梯度下降算法 指数加权平均算法 动量梯度下降 RMSprop算法 Adam优化算法 常用优化算法在面试的时候也会经常被问到。 一、梯度下降算...
  • 这篇文章介绍了不同优化算法之间的主要区别,以及如何选择最佳的优化方法。 1、什么是优化算法优化算法的功能,是通过改善训练方式,来最小化(或最大化)损失函数E(x)。 模型内部有些参数,是用来计算测试集中...
  • 智能优化算法性能比较:常用的23组测试函数 文章目录智能优化算法性能比较:常用的23组测试函数1. 单模态的基准测试函数2. 多模态的基准测试函数3. 复合基准测试函数4. 测试函数代码 在智能优化算法的性能比较过程中...
  • 下面的内容就是记录一下在深度学习中常用到的几种优化算法,以备日后查询。 1、SGD、BGD、Mini-BGD 把这三个放到一起是因为其有很多共性,接下来就来一一介绍: 1、SGD(随机梯度下降) SGD(stochastic g...
  • 在机器学习中,有很多的问题并没有...  这些常用优化算法包括:梯度下降法(Gradient Descent),共轭梯度法(Conjugate Gradient),Momentum算法及其变体,牛顿法和拟牛顿法(包括L-BFGS),AdaGrad,Adadel...
  • 梯度下降算法是机器学习中使用非常广泛的优化算法,也是众多机器学习算法中最常用的优化方法。几乎当前每一个先进的(state-of-the-art)机器学习库或者深度学习库都会包括梯度下降算法的不同变种实现。但是,它们就像...
  • 吴恩达老师的深度学习课程第二课中介绍了深度学习的常见的优化算法,包括基于梯度下降的,还有基于指数加权的~~ 一个一个记录 梯度下降法的优化(Mini-Batch gradient decent) 梯度下降法,是当今最...
  • 最全的机器学习中的优化算法介绍

    万次阅读 多人点赞 2017-08-06 12:57:02
    在机器学习中,有很多的问题并没有...  这些常用优化算法包括:梯度下降法(Gradient Descent),共轭梯度法(Conjugate Gradient),Momentum算法及其变体,牛顿法和拟牛顿法(包括L-BFGS),AdaGrad,Adadelta
  • 机器学习常用的最优化算法 本篇blog将介绍梯度下降法、随机梯度下降法、坐标下降法、牛顿法。 梯度下降法 基本步骤 首先写出梯度下降法的简单步骤: 我们需要最优化的函数是f(x),其中x为向量。 1、初始化...
  • 深度学习的优化算法从SGD--&gt;SGDM--&gt;NAG--&gt;AdaGrad--&gt;AdaDelta--&gt;Adam--&gt;Nadam这样的发展历程,理论知识参考这里,下面我们依次介绍TensorFlow中这些优化器的实现类,官方...
  • 1.神经网络的优化算法有很多,分为一阶优化算法和二阶优化算法。 2.一阶就是我们平时常用的梯度法。例如神经网络里面自带的SGD,Adam等等。 3.原始的 BP 算法是基于梯度下降法,训练过程是通过调整权值和阀值,使...
  • HLS 简介 Xilinx Vivado HLS工具可以将用户使用C++编写的逻辑自动转化为硬件语言(如Verilog或VHDL语言)编写的RTL级硬件逻辑...此过程中,用于制导的pragma优化命令的使用对最终RTL代码生成影响很大,有关各种优...
  • 数值最优化算法与理论(第2版)》较为系统地介绍最优化领域中比较成熟的基本理论与方法。基本理论包括最优化问题解的必要条件和充分条件以及各种算法的收敛性理论。介绍的算法有:无约束问题的最速下降法、Newton法、拟...
  • ...动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的...《五大常用算法系列介绍之一:分治算法》 《五大常
  • 应用粒子群优化(PSO)算法对电力系统的机组优化组合问题进行研究,介绍算法原理,分析了算法中各个参数的不同取值对算法搜索能力和收敛速度的影响,并以常用的测试函数进行验证,建立了相应的数学模型,并以IEEE3机6节点...
  • 在本综述中,我们介绍梯度下降的不同变形形式,总结这些算法面临的挑战,介绍常用优化算法,回顾并行和分布式架构,以及调研用于优化梯度下降的其他的策略。1 引言梯度下降法是最著名的优化算法之一,也是迄今...
  • 本文主要分机器学习和深度学习两部分介绍介绍常用优化算法优化算法的重要性是不言而喻的,优化算法决定了损失函数的收敛速度,甚至是损失函数是否容易收敛,是否会收敛在最小值处(全局优化)。 机器学习优化...
  • 常用推荐算法总结

    2018-12-10 11:31:30
    蟾宫推荐算法的总结介绍,包括非个性化推荐:热度排行,协同过滤算法,基于内容,基于知识的推荐,混合方法;推荐算法最新研究:学习排序,页面整体优化,情景推荐:张量分解,分解机,深度学习
  • 优化算法-梯度下降法

    2015-04-06 21:36:08
    本文深入浅出地介绍优化算法常用的梯度下降法
  • 遗传算法:遗传算法包含遗传、变异和选择三个流程。个体编码常用无符号的二进制整数来表示。具体步骤包括:构造一定规模的初始种群,计算适应度决定遗传的概率,遗传运算(常用轮盘赌法),交叉运算(按概率发生片段...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,119
精华内容 447
关键字:

常用优化算法介绍