机器学习优化算法_机器学习优化算法与启发式算法比较 - CSDN
精华内容
参与话题
  • 机器学习中,有很多的问题并没有解析形式的解,或者有解析形式的解但是计算量很大(譬如,超定问题的最小二乘解),对于此类问题,通常我们会选择采用一种迭代的优化方式进行求解。   这些常用的优化算法包括:...

    在机器学习中,有很多的问题并没有解析形式的解,或者有解析形式的解但是计算量很大(譬如,超定问题的最小二乘解),对于此类问题,通常我们会选择采用一种迭代的优化方式进行求解。
      这些常用的优化算法包括:梯度下降法(Gradient Descent),共轭梯度法(Conjugate Gradient),Momentum算法及其变体,牛顿法和拟牛顿法(包括L-BFGS),AdaGrad,Adadelta,RMSprop,Adam及其变体,Nadam。


    梯度下降法(Gradient Descent)

    想象你在一个山峰上,在不考虑其他因素的情况下,你要如何行走才能最快的下到山脚?当然是选择最陡峭的地方,这也是梯度下降法的核心思想:它通过每次在当前梯度方向(最陡峭的方向)向前“迈”一步,来逐渐逼近函数的最小值。
      在第n次迭代中,参数θn=θn1+Δθ
      我们将损失函数在θn1处进行一阶泰勒展开:
      L(θn)=L(θn1+Δθ)L(θn1)+L(θn1)Δθ

    为了使L(θn)<L(θn1),可取Δθ=αL(θn1),即得到我们的梯度下降的迭代公式:
    θn:=θn1αL(θn1)
      梯度下降法根据每次求解损失函数L带入的样本数,可以分为:
      全量梯度下降(计算所有样本的损失),
      批量梯度下降(每次计算一个batch样本的损失)
      随机梯度下降(每次随机选取一个样本计算损失)。
    PS:现在所说的SGD(随机梯度下降)多指Mini-batch-Gradient-Descent(批量梯度下降),后文用gn来代替L(θn)

    SGD的优缺点
    优点:操作简单,计算量小,在损失函数是凸函数的情况下能够保证收敛到一个较好的全局最优解。
    缺点:

    • α是个定值(在最原始的版本),它的选取直接决定了解的好坏,过小会导致收敛太慢,过大会导致震荡而无法收敛到最优解。
    • 对于非凸问题,只能收敛到局部最优,并且没有任何摆脱局部最优的能力(一旦梯度为0就不会再有任何变化)。
      PS:对于非凸的优化问题,我们可以将其转化为对偶问题,对偶函数一定是凹函数,但是这样求出来的解并不等价于原函数的解,只是原函数的一个确下界
      这里写图片描述

    Momentum

    SGD中,每次的步长一致,并且方向都是当前梯度的方向,这会收敛的不稳定性:无论在什么位置,总是以相同的“步子”向前迈。
      Momentum的思想就是模拟物体运动的惯性:当我们跑步时转弯,我们最终的前进方向是由我们之前的方向和转弯的方向共同决定的。Momentum在每次更新时,保留一部分上次的更新方向:

    Δθn=ρΔθn1+gn1

    θn:=θn1αΔθn

      这里ρ值决定了保留多少上次更新方向的信息,值为0~1,初始时可以取0.5,随着迭代逐渐增大;α为学习率,同SGD。
    优点:一定程度上缓解了SGD收敛不稳定的问题,并且有一定的摆脱局部最优的能力(当前梯度为0时,仍可能按照上次迭代的方向冲出局部最优点),直观上理解,它可以让每次迭代的“掉头方向不是那个大“。左图为SGD,右图为Momentum。
    这里写图片描述

    图片来源于《An overview of gradient descent optimization algorithms》

    缺点:这里又多了另外一个超参数ρ需要我们设置,它的选取同样会影响到结果。


    Nesterov Momentum

    Nesterov Momentum又叫做Nesterov Accelerated Gradient(NAG),是基于Momentum的加速算法。
      通过上述,我们知道,在每次更新的时候,都在ρΔθn1+L(θn)走α这么远,那么我们为什么不直接走到这个位置,然后从这个位置的梯度再走一次呢?为此,引出NAG的迭代公式:

    Δθn=ρΔθn1+g(θn1αΔθn1)

    θn:=θn1αΔθn

      我们可以这样理解,每次走之前,我们先用一个棍子往前探一探,这根棍子探到的位置就是L(θn1αΔθn1),然后我们求解此处的梯度:如果梯度大,我们迈一大步,反之,迈一小步。如果我们将上式改写一下:

    Δθn=ρΔθn1+gn1+ρ(gn1gn2))

    θn:=θn1αΔθn

      如果这次的梯度比上次大,那么我们有理由认为梯度还会继续变大!于是,当前就迈一大步,因为使用了二阶导数的信息(二阶导数>0即一阶导单调递增,也即gn1>gn2,因此可以加快收敛。
    这里写图片描述
    图片来自Hinton在Coursera上DL课程的slides

      蓝色的线代表原始的Momentum更新方向,在NAG中,我们先求解得到了这个方向,也即棕色的线,然后求解此处的梯度(红色的线),从而得到最终的前进方向。
      


    共轭梯度法(Conjugate Gradient)

    同样的,CG也在选取前进方向上,对SGD做了改动。它对性能有很大的提升,但是不适用高维数据,求解共轭的计算量过大。网上有很多讲CG的,但是个人感觉都是从某一篇文献里面摘出来的几个图,这里推荐一个专门讲解CG的painless conjugate gradient,讲的很细致。



      不同于上述算法对前进方向进行选择和调整,后面这些算法主要研究沿着梯度方向走多远的问题,也即如何选择合适的学习率α。

    Adagrad

    即adaptive gradient,自适应梯度法。它通过记录每次迭代过程中的前进方向和距离,从而使得针对不同问题,有一套自适应调整学习率的方法:

    Δθn=1i=1n1gi+ϵ

    θn:=θn1αΔθn

      可以看到,随着迭代的增加,我们的学习率是在逐渐变小的,这在“直观上”是正确的:当我们越接近最优解时,函数的“坡度”会越平缓,我们也必须走的更慢来保证不会穿过最优解。这个变小的幅度只跟当前问题的函数梯度有关,ϵ是为了防止0除,一般取1e-7。
    优点:解决了SGD中学习率不能自适应调整的问题
    缺点:

    • 学习率单调递减,在迭代后期可能导致学习率变得特别小而导致收敛及其缓慢。
    • 同样的,我们还需要手动设置初始α

    Adagrad-like

    在《No More Pesky Learning Rates》一文中,提到另外一种利用了二阶导信息的类adagrad算法。它是由Schaul于2012年提出的,使用了如下形式的更新公式:

    这里写图片描述

      Hn是二阶梯度的Hession矩阵,这里只使用了前t个梯度来缩放学习率。它是由LecCun提出来的一种逼近Hession矩阵的更新方式的变体,原始版本为:
    这里写图片描述

    优点:缓解了Adagrad中学习率单调递减的问题
    缺点:Hession矩阵的计算必须采用较好的近似解,其次t也成为了新的超参数需要手动设置,即我们需要保留参数前多少个梯度值用来缩放学习率。


    Adadelta

    Adadelta在《ADADELTA: An Adaptive Learning Rate Method 》一文中提出,它解决了Adagrad所面临的问题。定义:

    这里写图片描述

      则更新的迭代公式为:
    这里写图片描述

      这里ρ为小于1的正数,随着迭代次数的增加,同一个E[g2]i会因为累乘一个小于1的数而逐渐减小,即使用了一种自适应的方式,让距离当前越远的梯度的缩减学习率的比重越小。分子是为了单位的统一性,其实上述的算法中,左右的单位是不一致的,为了构造一致的单位,我们可以模拟牛顿法(一阶导\二阶导),它的单位是一致的,而分子就是最终推导出的结果,具体参考上面那篇文章。这样,也解决了Adagrad初始学习率需要人为设定的问题。
    优点:完全自适应全局学习率,加速效果好
    缺点:后期容易在小范围内产生震荡


    RMSprop

    其实它就是Adadelta,这里的RMS就是Adadelta中定义的RMS,也有人说它是一个特例,ρ=0.5的Adadelta,且分子α,即仍然依赖于全局学习率。


    Adam

    Adam是Momentum和Adaprop的结合体,我们先看它的更新公式:

    这里写图片描述

      它利用误差函数的一阶矩估计和二阶矩估计来约束全局学习率。
    优点:结合Momentum和Adaprop,稳定性好,同时相比于Adagrad,不用存储全局所有的梯度,适合处理大规模数据
    一说,adam是世界上最好的优化算法,不知道用啥时,用它就对了。
    详见《Adam: A Method for Stochastic Optimization


    Adamax

    它是Adam的一个变体,简化了二阶矩估计的取值:

    这里写图片描述

    Nadam和NadaMax

    Nadam是带有NAG的adam:

    这里写图片描述

     每次迭代的ϕ都是不同的,如果参考Adamax的方式对二阶矩估计做出修改,我们可以得到NadaMax,
    详见:《Incorporating Nesterov Momentum intoAdam


    牛顿法

    牛顿法不仅使用了一阶导信息,同时还利用了二阶导来更新参数,其形式化的公式如下:

    这里写图片描述

      回顾之前的θn=θn1+Δθ,我们将损失函数在θn1处进行二阶泰勒展开:
    这里写图片描述

      要使L(θn)<L(θn1),我们需要极小化L(θn1)Δθ+L(θn1)Δθ22,对其求导,令导数为零,可以得到:

    Δθ=Ln1Ln1

      也即牛顿法的迭代公式,拓展到高维数据,二阶导变为Hession矩阵,上式变为:

    Δθ=H1Ln1

      直观上,我们可以这样理解:我们要求一个函数的极值,假设只有一个全局最优值,我们需要求得其导数为0的地方,我们把下图想成是损失函数的导数的图像f(x),那么:
    k=tanθ=f(x0)=f(x0)x0x1x1=x0f(x0)f(x0)

      我们一直这样做切线,最终xn将逼近与f(x)的0点,对于原函数而言,即Δθ=Ln1Ln1
    这里写图片描述

    牛顿法具有二阶收敛性,每一轮迭代会让误差的数量级呈平方衰减。即在某一迭代中误差的数量级为0.01,则下一次迭代误差为0.0001,再下一次为0.00000001。收敛速度快,但是大规模数据时,Hession矩阵的计算与存储将是性能的瓶颈所在。
      为此提出了一些算法,用来近似逼近这个Hession矩阵,最著名的有L-BFGS,优于BFGS,可适用于并行计算从而大大提高效率,详见:Large-scale L-BFGS using MapReduce



    有人会问,既然有这么多方法,为什么很多论文里面还是用的SGD?需要注意的是,其他的方法在计算性能和收敛方面确实优秀很多,有的甚至不用认为干涉,它会自适应的调整参数,但是,在良好的调参情况下,SGD收敛到的最优解一般是最好的。

    转自:https://blog.csdn.net/qsczse943062710/article/details/76763739
    参考:
    http://www.cnblogs.com/maybe2030/p/4751804.html
    https://blog.csdn.net/huangfei711/article/details/79883350
    https://zhuanlan.zhihu.com/p/33175839

    展开全文
  • 最全的机器学习中的优化算法介绍

    万次阅读 多人点赞 2017-08-07 09:45:12
    机器学习中,有很多的问题并没有解析形式的解,或者有解析形式的解但是计算量很大(譬如,超定问题的最小二乘解),对于此类问题,通常我们会选择采用一种迭代的优化方式进行求解。   这些常用的优化算法包括:...

      在机器学习中,有很多的问题并没有解析形式的解,或者有解析形式的解但是计算量很大(譬如,超定问题的最小二乘解),对于此类问题,通常我们会选择采用一种迭代的优化方式进行求解。
      这些常用的优化算法包括:梯度下降法(Gradient Descent)共轭梯度法(Conjugate Gradient)Momentum算法及其变体,牛顿法和拟牛顿法(包括L-BFGS)AdaGradAdadeltaRMSpropAdam及其变体,Nadam

    梯度下降法(Gradient Descent)

      想象你在一个山峰上,在不考虑其他因素的情况下,你要如何行走才能最快的下到山脚?当然是选择最陡峭的地方,这也是梯度下降法的核心思想:它通过每次在当前梯度方向(最陡峭的方向)向前“迈”一步,来逐渐逼近函数的最小值。
      在第n次迭代中,参数θn=θn1+Δθ
      我们将损失函数在θn1处进行一阶泰勒展开

    L(θn)=L(θn1+Δθ)L(θn1)+L(θn1)Δθ

      为了使L(θn)<L(θn1),可取Δθ=αL(θn1),即得到我们的梯度下降的迭代公式:
    θn:=θn1αL(θn1)

      梯度下降法根据每次求解损失函数L带入的样本数,可以分为:全量梯度下降(计算所有样本的损失),批量梯度下降(每次计算一个batch样本的损失)和随机梯度下降(每次随机选取一个样本计算损失)。
    PS:现在所说的SGD(随机梯度下降)多指Mini-batch-Gradient-Descent(批量梯度下降),后文用gnL(θn)

    SGD的优缺点

    优点:操作简单,计算量小,在损失函数是凸函数的情况下能够保证收敛到一个较好的全局最优解。
    缺点

    • α是个定值(在最原始的版本),它的选取直接决定了解的好坏,过小会导致收敛太慢,过大会导致震荡而无法收敛到最优解。

    • 对于非凸问题,只能收敛到局部最优,并且没有任何摆脱局部最优的能力(一旦梯度为0就不会再有任何变化)。
      PS:对于非凸的优化问题,我们可以将其转化为对偶问题,对偶函数一定是凹函数,但是这样求出来的解并不等价于原函数的解,只是原函数的一个确下界

    Momentum

      SGD中,每次的步长一致,并且方向都是当前梯度的方向,这会收敛的不稳定性:无论在什么位置,总是以相同的“步子”向前迈。
      Momentum的思想就是模拟物体运动的惯性:当我们跑步时转弯,我们最终的前进方向是由我们之前的方向和转弯的方向共同决定的。Momentum在每次更新时,保留一部分上次的更新方向

    Δθn=ρΔθn1+gn1
    θn:=θn1αΔθn

      这里ρ值决定了保留多少上次更新方向的信息,值为0~1,初始时可以取0.5,随着迭代逐渐增大;α为学习率,同SGD。

    优点:一定程度上缓解了SGD收敛不稳定的问题,并且有一定的摆脱局部最优的能力(当前梯度为0时,仍可能按照上次迭代的方向冲出局部最优点),直观上理解,它可以让每次迭代的“掉头方向不是那个大“。左图为SGD,右图为Momentum。

    SGD和Momentum比较
    图片来源于《An overview of gradient descent optimization algorithms》

    缺点:这里又多了另外一个超参数ρ需要我们设置,它的选取同样会影响到结果。

    Nesterov Momentum

      Nesterov Momentum又叫做Nesterov Accelerated Gradient(NAG),是基于Momentum的加速算法。
      通过上述,我们知道,在每次更新的时候,都在ρΔθn1+L(θn)α这么远,那么我们为什么不直接走到这个位置,然后从这个位置的梯度再走一次呢?为此,引出NAG的迭代公式:

    Δθn=ρΔθn1+g(θn1αΔθn1)
    θn:=θn1αΔθn

      我们可以这样理解,每次走之前,我们先用一个棍子往前探一探,这根棍子探到的位置就是L(θn1αΔθn1),然后我们求解此处的梯度:如果梯度大,我们迈一大步,反之,迈一小步。如果我们将上式改写一下:
    Δθn=ρΔθn1+gn1+ρ(gn1gn2))
    θn:=θn1αΔθn

      如果这次的梯度比上次大,那么我们有理由认为梯度还会继续变大!于是,当前就迈一大步,因为使用了二阶导数的信息(二阶导数>0即一阶导单调递增,也即gn1>gn2,因此可以加快收敛


    图片来自Hinton在Coursera上DL课程的slides

      蓝色的线代表原始的Momentum更新方向,在NAG中,我们先求解得到了这个方向,也即棕色的线,然后求解此处的梯度(红色的线),从而得到最终的前进方向。

    共轭梯度法(Conjugate Gradient)

      同样的,CG也在选取前进方向上,对SGD做了改动。它对性能有很大的提升,但是不适用高维数据,求解共轭的计算量过大。网上有很多讲CG的,但是个人感觉都是从某一篇文献里面摘出来的几个图,这里推荐一个专门讲解CG的painless conjugate gradient,讲的很细致。


      不同于上述算法对前进方向进行选择和调整,后面这些算法主要研究沿着梯度方向走多远的问题,也即如何选择合适的学习率α

    Adagrad

      即adaptive gradient,自适应梯度法。它通过记录每次迭代过程中的前进方向和距离,从而使得针对不同问题,有一套自适应调整学习率的方法:

    Δθn=1n1i=1gi+ϵgn1
    θn:=θn1αΔθn

      可以看到,随着迭代的增加,我们的学习率是在逐渐变小的,这在“直观上”是正确的:当我们越接近最优解时,函数的“坡度”会越平缓,我们也必须走的更慢来保证不会穿过最优解。这个变小的幅度只跟当前问题的函数梯度有关,ϵ是为了防止0除,一般取1e-7。

    优点:解决了SGD中学习率不能自适应调整的问题
    缺点

    • 学习率单调递减,在迭代后期可能导致学习率变得特别小而导致收敛及其缓慢。
    • 同样的,我们还需要手动设置初始α

    Adagrad-like

      在《No More Pesky Learning Rates》一文中,提到另外一种利用了二阶导信息的类adagrad算法。它是由Schaul于2012年提出的,使用了如下形式的更新公式:

    Δθn=1|diag(Hn)|(n1i=ntgi)2n1i=ntg2ign1
    θn:=θn1Δθn

      Hn是二阶梯度的Hession矩阵,这里只使用了前t个梯度来缩放学习率。它是由LecCun提出来的一种逼近Hession矩阵的更新方式的变体,原始版本为:
    Δθn=1|diag(Hn)|+ϵgn1
    θn:=θn1Δθn

    优点:缓解了Adagrad中学习率单调递减的问题
    缺点:Hession矩阵的计算必须采用较好的近似解,其次t也成为了新的超参数需要手动设置,即我们需要保留参数前多少个梯度值用来缩放学习率。

    Adadelta

      Adadelta在《ADADELTA: An Adaptive Learning Rate Method 》一文中提出,它解决了Adagrad所面临的问题。定义:

    RMS[g]n=E[g2]n+ϵ
    E[g2]n=ρE[g2]n1+(1ρ)g2n

      则更新的迭代公式为:
    θn:=θn1RMS[Δθ]n1RMS[g]ngn

      这里ρ为小于1的正数,随着迭代次数的增加,同一个E[g2]i会因为累乘一个小于1的数而逐渐减小,即使用了一种自适应的方式,让距离当前越远的梯度的缩减学习率的比重越小。分子是为了单位的统一性,其实上述的算法中,左右的单位是不一致的,为了构造一致的单位,我们可以模拟牛顿法(一阶导\二阶导),它的单位是一致的,而分子就是最终推导出的结果,具体参考上面那篇文章。这样,也解决了Adagrad初始学习率需要人为设定的问题。

    优点:完全自适应全局学习率,加速效果好
    缺点:后期容易在小范围内产生震荡

    RMSprop

      其实它就是Adadelta,这里的RMS就是Adadelta中定义的RMS,也有人说它是一个特例,ρ=0.5的Adadelta,且分子α,即仍然依赖于全局学习率。

    Adam

      Adam是Momentum和Adaprop的结合体,我们先看它的更新公式:

    E[g2]n=ρE[g2]n1+(1ρ)g2n
    E[g]n=ϕE[g]n1+(1ϕ)g2n
    E[g2]n¯=E[g2]n1ρn
    E[g]n¯=E[g]n1ϕn
    θn:=θn1αE[g]n¯E[g2]n¯+ϵgn

      它利用误差函数的一阶矩估计和二阶矩估计来约束全局学习率。
    优点:结合Momentum和Adaprop,稳定性好,同时相比于Adagrad,不用存储全局所有的梯度,适合处理大规模数据
    一说,adam是世界上最好的优化算法,不知道用啥时,用它就对了。
    详见《Adam: A Method for Stochastic Optimization》

    Adamax

      它是Adam的一个变体,简化了二阶矩估计的取值:

    E[g2]n=max(|gn|,E[g2]n1ρ)

    θn:=θn1αE[g]n¯E[g2]n+ϵgn

    Nadam和NadaMax

      Nadam是带有NAG的adam:

    gn¯=gn1ni=1ϕi

    E[g]n=ϕE[g]n1+(1ϕ)g2n
    E[g]n¯=E[g]n1n+1i=1ϕi
    E[g2]n=ρE[g2]n1+(1ρ)g2n
    E[g2]n¯=E[g]n1ρn
    E[g]n¯=(1ϕn)gn¯+ϕn1E[g]n¯
    θn:=θn1αE[g]n¯E[g2]n+ϵ

      每次迭代的ϕ都是不同的,如果参考Adamax的方式对二阶矩估计做出修改,我们可以得到NadaMax,
    详见:《Incorporating Nesterov Momentum intoAdam》

    牛顿法

      牛顿法不仅使用了一阶导信息,同时还利用了二阶导来更新参数,其形式化的公式如下:

    θn:=θn1αLn1L′′n1

      回顾之前的θn=θn1+Δθ,我们将损失函数在θn1处进行二阶泰勒展开
    L(θn)=L(θn1+Δθ)L(θn1)+L(θn1)Δθ+L′′(θn1)Δθ22

      要使L(θn)<L(θn1),我们需要极小化L(θn1)Δθ+L′′(θn1)Δθ22,对其求导,令导数为零,可以得到:
    Δθ=Ln1L′′n1

      也即牛顿法的迭代公式,拓展到高维数据,二阶导变为Hession矩阵,上式变为:
    Δθ=H1Ln1

      直观上,我们可以这样理解:我们要求一个函数的极值,假设只有一个全局最优值,我们需要求得其导数为0的地方,我们把下图想成是损失函数的导数的图像f(x),那么:

    k=tanθ=f(x0)=f(x0)x0x1x1=x0f(x0)f(x0)

      我们一直这样做切线,最终xn将逼近与f(x)的0点,对于原函数而言,即Δθ=Ln1L′′n1

    牛顿法

      牛顿法具有二阶收敛性,每一轮迭代会让误差的数量级呈平方衰减。即在某一迭代中误差的数量级为0.01,则下一次迭代误差为0.0001,再下一次为0.00000001。收敛速度快,但是大规模数据时,Hession矩阵的计算与存储将是性能的瓶颈所在。
      为此提出了一些算法,用来近似逼近这个Hession矩阵,最著名的有L-BFGS,优于BFGS,可适用于并行计算从而大大提高效率,详见:Large-scale L-BFGS using MapReduce


      有人会问,既然有这么多方法,为什么很多论文里面还是用的SGD?需要注意的是,其他的方法在计算性能和收敛方面确实优秀很多,有的甚至不用认为干涉,它会自适应的调整参数,但是,在良好的调参情况下,SGD收敛到的最优解一般是最好的。

    展开全文
  • 机器学习优化算法总结

    千次阅读 2019-07-04 09:55:15
    机器学习中有很多优化算法,下面对这些优化算法写一些自己的理解。 梯度下降法(Gradient Descent) 梯度下降法是最早接触的优化算法,也是应用最广泛的优化算法,梯度具有两个重要的性质: 1. 梯度方向是函...

    机器学习中有很多优化算法,下面对这些优化算法写一些自己的理解。

    • 梯度下降法(Gradient Descent

    梯度下降法是最早接触的优化算法,也是应用最广泛的优化算法,梯度具有两个重要的性质:

    1. 梯度方向是函数值最速上升方向,那么负梯度方向是函数值最速下降方向

    2. 如果某点的梯度不为0,则必与该点的等值面垂直。

    文章是这样理解的:

    我按照梯度的定义解释一下\theta_{n}:=\theta_{n-1}+\alpha L^{'}(\theta_{n-1}) ,-L^{'}(\theta_{n-1})是目标函数关于\theta的负梯度方向,\alpha是我们选择的步长,我们要沿着-L^{'}(\theta_{n-1})方向走\alpha步长,由于负梯度方向是函数值下降方向,因此\theta的值是不断减小的,如果目标函数是凸的,定义域也是凸的,那么\theta可以到达全局最小值,否则\theta有可能是局部最小值,不能保证全局最优性。

    步长的选择也很有技巧,如果步长(学习率)太小,必须经过多次迭代,算法才能收敛,这是非常耗时的。如下图所示:

    如果学习率太大,你将跳过最低点,到达山谷的另一面,可能下一次的值比上一次还要大。这可能使的算法是发散的,函数值变得越来越大,永远不可能找到一个好的答案                                                                                                                                       

    梯度下降(批量梯度)中每一步计算时都包含了整个训练集 ,每一次训练过程都使用所有的的训练数据。因此,在大数据集上,其会变得相当的慢( 但是我们接下来将会介绍更快的梯度下降算法) 。然而,梯度下降的运算规模和特征的数量成正比。训练一个数千数量特征的线性回归模型使用*梯度下降要比使用正态方程快的多。

    梯度下降法可以有两种其他的版本:随机梯度下降法(SGD)和小批量梯度下降法 (Mini-batch-Gradient-Descent)

    • 随机梯度下降法(Stochastic Gradient Descent)

     由于梯度下降法每次计算时包含整个数据集,会影响计算的速度,与其完全相反的随机梯度下降(SGD),在每一步的梯度计算上只随机选取训练集中的一个样本。

    由于它的随机性,与批量梯度下降相比,其呈现出更多的不规律性:它到达最小值不是平缓的下降,损失函数会忽高忽低,只是在大体上呈下降趋势。随着时间的推移,它会非常的靠近最小值,但是它不会停止在一个值上,它会一直在这个值附近摆动。因此,当算法停止的时候,最后的参数还不错,但不是最优值。

    当损失函数很不规则时,随机梯度下降算法能够跳过局部最小值。虽然随机性可以很好的跳过局部最优值,但同时它却不能达到最小值。解决这个难题的一个办法是逐渐降低学习率。 开始时,走的每一步较大( 这有助于快速前进同时跳过局部最小
    值) ,然后变得越来越小,从而使算法到达全局最小值。 这个过程被称为模拟退火.

    • 小批量梯度下降法 (Mini-batch-Gradient-Descent)(常用)

    批量梯度使用整个训练集,随机梯度时候用仅仅一个实例,在小批量梯度下降中,它则使用一个随机的小型实例集(m个实例,1<m<n)。它比随机梯度的主要优点在于你可以通过矩阵运算的硬件优化得到一个较好的训练表现.小批量梯度下降在参数空间上的表现比随机梯度下降要好的多,尤其在有大量的小型实例集时。作为结果,小批量梯度下降会比随机梯度更靠近最小值。但是,另一方面,它有可能陷在局部最小值中。

    • 动量梯度下降法(Gradient descent with Momentum)

    参考:https://www.cnblogs.com/jiaxblog/p/9695042.html

     Momentum算法又叫做冲量算法,其迭代更新公式如下:

    \bg_green \nu^{n} _{dw}=\beta \nu^{n-1} _{dw}+(1-\beta)dw^{n-1}\\ & w^{n}=w^{n-1}-\alpha \nu^{n} _{dw}\\ \nu^{n} _{db}=\beta \nu^{n-1} _{db}+(1-\beta)db^{n-1}\\ b^{n}=b^{n-1}-\alpha \nu^{n} _{db}

    一般的梯度下降法的更新公式为{\color{Blue} w^{n}=w^{n-1}-\alpha dw^{n-1}},其中,{\color{Blue} dw^{n-1}}代表损失函数对w的导数,如果我们把动量梯度下降法和梯度下降法对比就会发现,动量梯度下降法多了一项\nu^{n-1}(不考虑系数关系),这项代表以前梯度的指数加权平均,指数加权平均的思想是现在的梯度方向和之间的梯度有指数加权的关系,也就是弱化了在dw处的梯度的作用,如果梯度在某一方向出现震荡,那么指数加权平均可以让这些震荡加起来上下抵消,加速了不震荡方向的迭代,这项就是给梯度下降法加的动量,所以叫动量梯度下降法。

    光看上面的公式有些抽象,我们先介绍一下指数加权平均,再回过头来看这个公式,会容易理解得多。

    指数加权平均

    假设我们有一年365天的气温数据\theta_{1},\theta_{2},...,\theta_{365},把他们化成散点图,如下图所示:

    这些数据有些杂乱,我们想画一条曲线,用来表征这一年气温的变化趋势,那么我们需要把数据做一次平滑处理。最常见的方法是用一个滑动窗口滑过各个数据点,计算窗口的平均值,从而得到数据的滑动平均值。但除此之外,我们还可以使用指数加权平均来对数据做平滑。其公式如下:

    v就是指数加权平均值,也就是平滑后的气温。β的典型值是0.9,平滑后的曲线如下图所示:

    其中,1-\beta^k是所有权重的和,这相当于对权重做了一个归一化处理。

    \beta取值为0.98的时候,指数加权平均计算的是最近\bg_green \frac{1}{1-\beta }=50个数据的平均值 。

    下面的图中,紫色的线就是没有做修正的结果,修正之后就是绿色曲线。二者在前面几个数据点之间相差较大,后面则基本重合了。

    回看Momentum算法

    现在再回过头来看Momentum算法的迭代更新公式:

    \bg_green \nu^{n} _{dw}=\beta \nu^{n-1} _{dw}+(1-\beta)dw^{n-1}\\ & w^{n}=w^{n-1}-\alpha \nu^{n} _{dw}\\ \nu^{n} _{db}=\beta \nu^{n-1} _{db}+(1-\beta)db^{n-1}\\ b^{n}=b^{n-1}-\alpha \nu^{n} _{db}

    针对目标函数是上图这种形式,小批量梯度下降法(梯度下降法)的迭代轨迹如上图蓝色曲线所示,在收敛过程中产生了震荡,减慢了迭代的速度,我们观察这些震荡,在纵轴上是对称的,上下几乎可以相互抵消,也就是说如果直接沿着横轴方向迭代,收敛速度可以加快。那怎么抵消这些震荡呢?就用到上面的指数加权平均算法,指数加权平均的思想是现在的梯度方向和之间的梯度有指数加权的关系,也就是弱化了在dw^{n-1}处的梯度的作用,\nu^{n} _{dw}的大小和之前梯度的平均值有关\nu^{n-1} _{dw},之间梯度的平均值基本和水平平行的,所以就加大了水平方向的动量,因此迭代的速度更快。

    • Nesterov 加速梯度(( Nesterov Accelerated Gradient,NAG)

    参考:https://blog.csdn.net/google19890102/article/details/69942970

    https://baijiahao.baidu.com/s?id=1613121229156499765&wfr=spider&for=pc

    球从山上滚下的时候,盲目地沿着斜率方向,往往并不能令人满意。我们希望有一个智能的球,这个球能够知道它将要去哪,以至于在重新遇到斜率上升时能够知道减速。

    Nesterov加速梯度下降法(Nesterov accelerated gradient,NAG)是一种能够给动量项这样的预知能力的方法。我们知道,我们利用动量项\beta \nu^{n-1} _{dw}来更新参数w。Nesterov加速梯度下降法和动量梯度下降法相比只把之前的\LARGE {\color{Blue} dw^{n-1}}变成了{\color{Red} d(w^{n-1}-\alpha \nu^{n-1} _{dw})},
    这里写图片描述 
    图3:Nesterov更新(来源:G. Hinton的课程6c) 

    Momentum梯度法首先计算的是当前的梯度(图中的小蓝色向量)然后沿着更新的累积梯度的方向来一个大的跳跃(图中大蓝色向量),而NAG梯度法首先沿着先前的累积梯度方向(棕色向量)实现一个大的跳跃,然后加上一个小的按照动量梯度法计算的当前梯度(上图红色向量)进行修正得到上图绿色的向量。此处我抛出一个问题,上图为什么画了两个三角形?如果能理解第二个矢量三解形的意义,才能正在理解NAG。注意第二个矢量三角形的棕色向量与前一个的绿色向量方向一致,因为上一个矢量三角形的结果是绿色向量,而棕色代表的是先前的累积梯度,方向就应该和绿色的一样。然后,再加上当前按照动量梯度法计算出的梯度,就得到第二个三角形的绿色向量。

    我们先给出类似生活体验的通俗的解释:我们要让算法要前瞻性,提前看到前方的地形梯度,如果前面的梯度比当前位置的梯度大,那我就可以把步子迈得比原来大一些,如果前面的梯度比现在的梯度小,那我就可以把步子迈得小一些。这个大一些、小一些,都是相对于原来不看前方梯度、只看当前位置梯度的情况来说的。

    下面转自知乎上的解释,讲解的非常好:https://zhuanlan.zhihu.com/p/22810533

    作为一个调参狗,每天用着深度学习框架提供的各种优化算法如Momentum、AdaDelta、Adam等,却对其中的原理不甚清楚,这样和一条咸鱼有什么分别!(误)但是我又懒得花太多时间去看每个优化算法的原始论文,幸运的是,网上的大神早就已经帮人总结好了:《An overview of gradient descent optimization algorithms》,看完了这篇文章,总算可以说对自己平时用的工具有一个大概的了解啦!

    文章的内容包括了Momentum、Nesterov Accelerated Gradient、AdaGrad、AdaDelta和Adam,在这么多个优化算法里面,一个妖艳的贱货(划去)成功地引起了我的注意——Nesterov Accelerated Gradient,简称NAG。原因不仅仅是它名字比别人长,而且还带了个逼格很高、一听就像是个数学家的人名,还因为,它仅仅是在Momentum算法的基础上做了一点微小的工作,形式上发生了一点看似无关痛痒的改变,却能够显著地提高优化效果。为此我折腾了一个晚上,终于扒开了它神秘的面纱……(主要是我推导公式太慢了……)

    话不多说,进入正题,首先简要介绍一下Momentum和NAG,但是本文无耻地假设你已经懂了Momentum算法,如果不懂的话,强烈推荐这篇专栏:《路遥知马力——Momentum - 无痛的机器学习 - 知乎专栏》,本文的实验代码也是在这篇专栏的基础上改的。

    Momentum改进自SGD算法,让每一次的参数更新方向不仅仅取决于当前位置的梯度,还受到上一次参数更新方向的影响:

     

    公式1,Momentum的数学形式

    其中,[公式][公式]分别是这一次和上一次的更新方向,[公式]表示目标函数在[公式]处的梯度,超参数[公式]是对上一次更新方向的衰减权重,所以一般是0到1之间,[公式]是学习率。总的来说,在一次迭代中总的参数更新量包含两个部分,第一个是由上次的更新量得到的[公式],第二个则是由本次梯度得到的[公式]

     

    所以Momentum的想法很简单,就是多更新一部分上一次迭代的更新量,来平滑这一次迭代的梯度。从物理的角度上解释,就像是一个小球滚落的时候会受到自身历史动量的影响,所以才叫动量(Momentum)算法。这样做直接的效果就是使得梯度下降的的时候转弯掉头的幅度不那么大了,于是就能够更加平稳、快速地冲向局部最小点:

     

    图片引自《An overview of gradient descent optimization algorithms

    然后NAG就对Momentum说:“既然我都知道我这一次一定会走[公式]的量,那么我何必还用现在这个位置的梯度呢?我直接先走到[公式]之后的地方,然后再根据那里的梯度再前进一下,岂不美哉?”所以就有了下面的公式:

    公式2,NAG的原始形式

    对上面红色字体的解释:

    Momentum 的迭代公式为:,我们把第一个式子带入到第二个中得到:

    & \theta_i=\theta_{i-1}-\alpha(\beta d_{i-1}+g(\theta_{i-1})) \\ & = [\theta_{i-1}-\alpha \beta d_{i-1}]-\alpha g(\theta_{i-1})

    在一次迭代中总的参数更新量包含两个部分,第一个是由上次的更新量得到的[公式],第二个则是由本次梯度得到的[公式],带括号的意思是我们已经知道我们要更新成这样了,也就是[公式]是由以前的累计的,上一次就可以计算出来了,我们这一次更新的时候肯定要减去这一项,所以我们本来要使用的是目标函数对\theta_{i-1}的导数,但是现在相当于我们知道了目标函数对\theta_{i}导数的一半信息,即知道了这个值[\theta_{i-1}-\alpha \beta d_{i-1}],所以我们为啥还要用目标函数对\theta_{i-1}的导数,为什么不用更加接近最优值 的导数信息呢?因此,我们把Momentum中的\theta_{i-1}变成了[\theta_{i-1}-\alpha \beta d_{i-1}]

     

     

    跟上面Momentum公式的唯一区别在于,梯度不是根据当前参数位置[公式],而是根据先走了本来计划要走的一步后,达到的参数位置[公式]计算出来的。

    对于这个改动,很多文章给出的解释是,能够让算法提前看到前方的地形梯度,如果前面的梯度比当前位置的梯度大,那我就可以把步子迈得比原来大一些,如果前面的梯度比现在的梯度小,那我就可以把步子迈得小一些。这个大一些、小一些,都是相对于原来不看前方梯度、只看当前位置梯度的情况来说的。

    但是我个人对这个解释不甚满意。你说你可以提前看到,但是我下次到了那里之后不也照样看到了吗?最多比你落后一次迭代的时间,真的会造成非常大的差别?可是实验结果就是表明,NAG收敛的速度比Momentum要快:

    图片引自《路遥知马力——Momentum - 无痛的机器学习 - 知乎专栏》,上图是Momentum的优化轨迹,下图是NAG的优化轨迹

    为了从另一个角度更加深入地理解这个算法,我们可以对NAG原来的更新公式进行变换,得到这样的等效形式(具体推导过程放在最后啦):

    公式3,NAG的等效形式

    这个NAG的等效形式与Momentum的区别在于,本次更新方向多加了一个[公式],它的直观含义就很明显了:如果这次的梯度比上次的梯度变大了,那么有理由相信它会继续变大下去,那我就把预计要增大的部分提前加进来;如果相比上次变小了,也是类似的情况。这样的解释听起来好像和原本的解释一样玄,但是读者可能已经发现了,这个多加上去的项不就是在近似目标函数的二阶导嘛!所以NAG本质上是多考虑了目标函数的二阶导信息,怪不得可以加速收敛了!其实所谓“往前看”的说法,在牛顿法这样的二阶方法中也是经常提到的,比喻起来是说“往前看”,数学本质上则是利用了目标函数的二阶导信息。

    关于二阶导数的理解:由于g(\theta_{i})g(\theta_{i-1})是目标函数在\theta_i\theta_{i-1}处的导数,二阶导数的就是关于一阶导数的导数,二阶导数\frac{g(\theta_i)-g(\theta_{i-1})}{\theta_i-\theta_{i-1}}[公式]只是相差系数关系,但是描述的导数变化率是相同的。

     

    那么,变换后的形式真的与NAG的原始形式等效么?在给出数学推导之前,先让我用实验来说明吧:

     

    上图是公式3给出的优化轨迹,下图是公式2给出的优化轨迹——完全一样

    实验代码放在Github,修改自《路遥知马力——Momentum - 无痛的机器学习 - 知乎专栏》的实验代码。有兴趣的读者可以多跑几个起始点+学习率+衰减率的超参数组合,无论如何两个算法给出的轨迹都会是一样的。

    最后给出NAG的原始形式到等效形式的推导。由

    可得

     

     

    上式代入上上式,就得到了NAG等效形式的第二个式子:

     

    [公式]展开可得

     

    于是我们可以写出[公式]的形式,然后用[公式]减去[公式]消去后面的无穷多项,就得到了NAG等效形式的第一个式子:

    最终我们就得到了NAG的等效形式:

     

    结论:在原始形式中,Nesterov Accelerated Gradient(NAG)算法相对于Momentum的改进在于,以“向前看”看到的梯度而不是当前位置梯度去更新。经过变换之后的等效形式中,NAG算法相对于Momentum多了一个本次梯度相对上次梯度的变化量,这个变化量本质上是对目标函数二阶导的近似。由于利用了二阶导的信息,NAG算法才会比Momentum具有更快的收敛速度。

     来自:https://blog.csdn.net/SIGAI_CSDN/article/details/81979837

    简而言之,这种算法会降低学习速度,但对于陡峭的尺寸,其速度要快于具有温和的斜率的尺寸。 这被称为自适应学习率。 它有助于将更新的结果更直接地指向全局最优 。 另一个好处是它不需要那么多的去调整学习率超参数 η。

    对于简单的二次问题,AdaGrad 经常表现良好,但不幸的是,在训练神经网络时,它经常停止得太早。 学习率被缩减得太多,以至于在达到全局最优之前,算法完全停止。 所以,即使TensorFlow 有一个 AdagradOptimizer ,你也不应该用它来训练深度神经网络( 虽然对线性回归这样简单的任务可能是有效的)
     

    • RMSprop算法(Root Mean Square Prop)

    尽管 AdaGrad 的速度变慢了一点,并且从未收敛到全局最优,但是 RMSProp 算法通过仅累积最近迭代( 而不是从训练开始以来的所有梯度) 的梯度来修正这个问题。
     

    还是观察上面的图

    如果纵坐标是b,横坐标是w,梯度方向在b方向上的投影大,在w方向上的投影小,故db>dw,db^{2}>dw^{2},所以我们希望在横轴(w)方向步长大一些,在纵轴(b)方向步长小一些。

    RMSprop公式如下所示:

    S^{n}_{dw}=\beta_{1} S^{n-1}_{dw}+(1-\beta_{1})dw^{2} 

    S^{n}_{db}=\beta_{2} S^{n-1}_{db}+(1-\beta_{2})db^{2}

    w^{n}=w^{n-1}-\alpha \frac{dw}{\sqrt{S_{dw}+\varepsilon}}

    b^{n}=b^{n-1}-\alpha \frac{db}{\sqrt{S_{db}+\varepsilon}}

    由于db^{2}>dw^{2},所以S_{db}相对于S_{dw}较大,故\sqrt{S_{db}+\varepsilon}\sqrt{S_{dw}+\varepsilon}大一些,因此\frac{db}{\sqrt{S_{db}+\varepsilon}}更小一些,就减小的b方向上的步长,加快了w方向上的步长。为什么有\varepsilon呢?防止S_{db}, S_{dw}为0,导致分母为0,一般除以一个数,防止该数为0,都回分母上加一个小的正数\varepsilon。通过RMSprop,我们可以调整不同维度上的步长,加快收敛速度。把上式合并后,RMSprop迭代更新公式如下:

    除了非常简单的问题,这个优化器几乎总是比 AdaGrad 执行得更好。 它通常也比动量优化和Nesterov 加速梯度表现更好。 事实上,这是许多研究人员首选的优化算法,直到 Adam 优化出现。
     

    •  Adam(Adaptive Moment Estimation

    Adam,代表自适应矩估计,结合了动量优化和 RMSProp 的思想:就像动量优化一样,它追踪过去梯度的指数衰减平均值,就像 RMSProp 一样,它跟踪过去平方梯度的指数衰减平均值。
     

     Adam是Moment和RMSprop的结合,Adam的公式如下:

     \beta _{1}=0.9, \beta_{2}=0.999,\varepsilon=10^{-8},\alpha需要调试。

    Adam的优点

    1. 计算高效,方便实现,内存使用也很少。
    2. 更新步长和梯度大小无关,只和alpha、beta_1、beta_2有关系。并且由它们决定步长的理论上限。
    3. 对目标函数没有平稳要求,即loss function可以随着时间变化
    4. 能较好的处理噪音样本,并且天然具有退火效果
    5. 能较好处理稀疏梯度,即梯度在很多step处都是0的情况

     迄今为止所讨论的所有优化技术都只依赖于一阶偏导数( 雅可比矩阵) 。 优化文献包含基于二阶偏导数( 海森矩阵) 的惊人算法。 不幸的是,这些算法很难应用于深度神经网络,因为每个输出有 n ^ 2 个海森值( 其中 n 是参数的数量) ,而不是每个输出只有 n 个雅克比值。由于 DNN 通常具有数以万计的参数,二阶优化算法通常甚至不适合内存,甚至在他们这样做时,计算海森矩阵也是太慢了。

    优化算法还没更新完,等到碰到会继续更新!

     

    展开全文
  • 机器学习中的最优化算法总结

    万次阅读 2019-10-21 15:00:07
    机器学习中的最优化算法总结》同主题直播 https://live.bilibili.com/11928465 对于几乎所有机器学习算法,无论是有监督学习、无监督学习,还是强化学习,最后一般都归结为求解最优化问题...

    其它机器学习、深度学习算法的全面系统讲解可以阅读《机器学习-原理、算法与应用》,清华大学出版社,雷明著,由SIGAI公众号作者倾力打造。

    《机器学习中的最优化算法总结》同主题直播

    https://live.bilibili.com/11928465

    对于几乎所有机器学习算法,无论是有监督学习、无监督学习,还是强化学习,最后一般都归结为求解最优化问题。因此,最优化方法在机器学习算法的推导与实现中占据中心地位。在这篇文章中,SIGAI将对机器学习中所使用的优化算法做一个全面的总结,并理清它们直接的脉络关系,帮你从全局的高度来理解这一部分知识。

    机器学习要求解的数学模型

    几乎所有的机器学习算法最后都归结为求一个目标函数的极值,即最优化问题,例如对于有监督学习,我们要找到一个最佳的映射函数f(x),使得对训练样本的损失函数最小化(最小化经验风险或结构风险):

     

    在这里,N为训练样本数,L是对单个样本的损失函数,w是要求解的模型参数,是映射函数的参数, x_{i} 为样本的特征向量, y_{i} 为样本的标签值。

    或是找到一个最优的概率密度函数p(x),使得对训练样本的对数似然函数极大化(最大似然估计):

    在这里, \theta 是要求解的模型参数,是概率密度函数的参数。

    对于无监督学习,以聚类算法为例,算法要是的每个类的样本离类中心的距离之和最小化:

    在这里k为类型数,x为样本向量, \mu_{i} 为类中心向量, S_{i} 为第i个类的样本集合。

    对于强化学习,我们要找到一个最优的策略,即状态s到动作a的映射函数(确定性策略,对于非确定性策略,是执行每个动作的概率)

     

    使得任意给定一个状态,执行这个策略函数所确定的动作a之后,得到的累计回报最大化:

    这里使用的是状态价值函数。

    总体来看,机器学习的核心目标是给出一个模型(一般是映射函数),然后定义对这个模型好坏的评价函数(目标函数),求解目标函数的极大值或者极小值,以确定模型的参数,从而得到我们想要的模型。在这三个关键步骤中,前两个是机器学习要研究的问题,建立数学模型。第三个问题是纯数学问题,即最优化方法,为本文所讲述的核心。

    最优化算法的分类

    对于形式和特点各异的机器学习算法优化目标函数,我们找到了适合它们的各种求解算法。除了极少数问题可以用暴力搜索来得到最优解之外,我们将机器学习中使用的优化算法分成两种类型(不考虑随机优化算法如模拟退火、遗传算法等,对于这些算法,我们后面会专门有文章进行介绍):

    公式解
    数值优化

    前者给出一个最优化问题精确的公式解,也称为解析解,一般是理论结果。后者是在要给出极值点的精确计算公式非常困难的情况下,用数值计算方法近似求解得到最优点。除此之外,还有其他一些求解思想,如分治法,动态规划等。我们在后面单独列出。一个好的优化算法需要满足:

    能正确的找到各种情况下的极值点
    速度快

    下图给出了这些算法的分类与它们之间的关系:

     

    接下来我们将按照这张图来展开进行讲解。

    费马定理

    对于一个可导函数,寻找其极值的统一做法是寻找导数为0的点,即费马定理。微积分中的这一定理指出,对于可导函数,在极值点处导数必定为0:

    对于多元函数,则是梯度为0:

     

    导数为0的点称为驻点。需要注意的是,导数为0只是函数取得极值的必要条件而不是充分条件,它只是疑似极值点。是不是极值,是极大值还是极小值,还需要看更高阶导数。对于一元函数,假设x是驻点:

    1.如果 f^{''} (x)>0,则在该点处去极小值

    2.如果 f^{''} (x)<0,则在该点处去极大值

    3.如果 f^{''} (x)=0,还要看更高阶导数

    对于多元函数,假设x是驻点:

    1.如果Hessian矩阵正定,函数在该点有极小值

    2.如果Hessian矩阵负定,函数在该点有极大值

    3.如果Hessian矩阵不定,则不是极值点

    在导数为0的点处,函数可能不取极值,这称为鞍点,下图是鞍点的一个例子(来自SIGAI云端实验室):

     

    除鞍点外,最优化算法可能还会遇到另外一个问题:局部极值问题,即一个驻点是极值点,但不是全局极值。如果我们对最优化问题加以限定,可以有效的避免这两种问题。典型的是凸优化,它要求优化变量的可行域是凸集,目标函数是凸函数。关于凸优化的详细讲解可以阅读SIGAI之前的公众号文章“理解凸优化”。

    虽然驻点只是函数取得极值的必要条件而不是充分条件,但如果我们找到了驻点,再判断和筛选它们是不是极值点,比之前要容易多了。无论是理论结果,还是数值优化算法,一般都以找驻点作为找极值点的目标。对于一元函数,先求导数,然后解导数为0的方程即可找到所有驻点。对于多元函数,对各个自变量求偏导数,令它们为0,解方程组,即可达到所有驻点。这都是微积分中所讲授的基础方法。幸运的是,在机器学习中,很多目标函数都是可导的,因此我们可以使用这套方法。

    拉格朗日乘数法

    费马定理给出的不带约束条件下的函数极值的必要条件。对于一些实际应用问题,一般还带有等式或者不等式约束条件。对于带等式约束的极值问题,经典的解决方案是拉格朗日乘数法。

    对于如下问题:

     

    构造拉格朗日乘子函数:

    在最优点处对x和乘子变量 \lambda_{i} 的导数都必须为0:

    解这个方程即可得到最优解。对拉格朗日乘数法更详细的讲解可以阅读任何一本高等数学教材。机器学习中用到拉格朗日乘数法的地方有:

    主成分分析
    线性判别分析
    流形学习中的拉普拉斯特征映射
    隐马尔可夫模型

    KKT条件

    KKT条件是拉格朗日乘数法的推广,用于求解既带有等式约束,又带有不等式约束的函数极值。对于如下优化问题:

    和拉格朗日对偶的做法类似,KKT条件构如下乘子函数:

     

    \lambda 和 \mu 称为KKT乘子。在最优解处 x^{*} 应该满足如下条件:

    等式约束 h_{j} ( x^{*} )=0和不等式约束 g_{k} ( x^{*} ) \leq 0是本身应该满足的约束, ▽_{x} Lx^{*} )=0和之前的拉格朗日乘数法一样。唯一多了关于 g_{i} (x)的条件:

    KKT条件只是取得极值的必要条件而不是充分条件。在机器学习中用到KKT条件的地方有:

    支持向量机(SVM)

    具体的推导可以阅读SIGAI之前的公众号文章“用一张图理解SVM的脉络”。

    数值优化算法

    前面讲述的三种方法在理论推导、某些可以得到方程组的求根公式的情况(如线性函数,正态分布的最大似然估计)中可以使用,但对绝大多数函数来说,梯度等于0的方程组是没法直接解出来的,如方程里面含有指数函数、对数函数之类的超越函数。对于这种无法直接求解的方程组,我们只能采用近似的算法来求解,即数值优化算法。这些数值优化算法一般都利用了目标函数的导数信息,如一阶导数和二阶导数。如果采用一阶导数,则称为一阶优化算法。如果使用了二阶导数,则称为二阶优化算法。

    工程上实现时通常采用的是迭代法,它从一个初始点 x_{0} 开始,反复使用某种规则从 x_{k} 移动到下一个点 x_{k+1} ,构造这样一个数列,直到收敛到梯度为0的点处。即有下面的极限成立:

    这些规则一般会利用一阶导数信息即梯度;或者二阶导数信息即Hessian矩阵。这样迭代法的核心是得到这样的由上一个点确定下一个点的迭代公式:

    梯度下降法

    梯度下降法沿着梯度的反方向进行搜索,利用了函数的一阶导数信息。梯度下降法的迭代公式为:

    根据函数的一阶泰勒展开,在负梯度方向,函数值是下降的。只要学习率 \gamma 设置的足够小,并且没有到达梯度为0的点处,每次迭代时函数值一定会下降。需要设置学习率为一个非常小的正数的原因是要保证迭代之后的 x_{k+1} 位于迭代之前的值 x_{k} 的邻域内,从而可以忽略泰勒展开中的高次项,保证迭代时函数值下降。

    梯度下降法及其变种在机器学习中应用广泛,尤其是在深度学习中。对梯度下降法更全面的介绍可以阅读SIGAI之前的公众号文章“理解梯度下降法”。

    动量项

    为了加快梯度下降法的收敛速度,减少震荡,引入了动量项。动量项累积了之前迭代时的梯度值,加上此项之后的参数更新公式为:

    其中 V_{t+1} 是动量项,它取代了之前的梯度项。动量项的计算公式为:

    它是上一时刻的动量项与本次梯度值的加权平均值,其中 \alpha 是学习率, \mu 是动量项系数。如果按照时间t进行展开,则第t次迭代时使用了从1到t次迭代时的所有梯度值,且老的梯度值安 \mu^{t} 的系数指数级衰减:

    动量项累积了之前迭代时的梯度值,使得本次迭代时沿着之前的惯性方向向前走。

    AdaGrad算法

    AdaGrad算法是梯度下降法最直接的改进。梯度下降法依赖于人工设定的学习率,如果设置过小,收敛太慢,而如果设置太大,可能导致算法那不收敛,为这个学习率设置一个合适的值非常困难。

    AdaGrad算法根据前几轮迭代时的历史梯度值动态调整学习率,且优化变量向量x的每一个分量 x_{i} 都有自己的学习率。参数更新公式为:

    其中 \alpha 是学习因子, g_{t} 是第t次迭代时参数的梯度向量, \xi 是一个很小的正数,为了避免除0操作,下标i表示向量的分量。和标准梯度下降法唯一不同的是多了分母中的这一项,它累积了到本次迭代为止梯度的历史值信息用于生成梯度下降的系数值。根据上式,历史导数值的绝对值越大分量学习率越小,反之越大。虽然实现了自适应学习率,但这种算法还是存在问题:需要人工设置一个全局的学习率 \alpha ,随着时间的累积,上式中的分母会越来越大,导致学习率趋向于0,参数无法有效更新。

    RMSProp算法

    RMSProp算法是对AdaGrad的改进,避免了长期累积梯度值所导致的学习率趋向于0的问题。具体做法是由梯度值构造一个向量RMS,初始化为0,按照衰减系数累积了历史的梯度平方值。更新公式为:

    AdaGrad直接累加所有历史梯度的平方和,而这里将历史梯度平方值按照 \delta^{t} 衰减之后再累加。参数更新公式为:

    其中 \delta 是人工设定的参数,与AdaGrad一样,这里也需要人工指定的全局学习率 \alpha 。

    AdaDelta算法

    AdaDelta算法也是对AdaGrad的改进,避免了长期累积梯度值所导致的学习率趋向于0的问题,另外,还去掉了对人工设置的全局学习率的依赖。假设要优化的参数为x,梯度下降法第t次迭代时计算出来的参数梯度值为 g_{t} 。算法首先初始化如下两个向量为0向量:

    其中E[ g^{2} ]是梯度平方(对每个分量分别平分)的累计值,更新公式为:

    在这里 g^{2} 是向量每个元素分别计算平方,后面所有的计算公式都是对向量的每个分量进行。接下来计算如下RMS量:

    这也是一个向量,计算时分别对向量的每个分量进行。然后计算参数的更新值:

    RMS [△x]_{t-1} 的计算公式和这个类似。这个更新值同样通过梯度来构造,只不过学习率是通过梯度的历史值确定的。更新公式为:

    参数更新的迭代公式为:

    Adam算法

    Adam算法整合了自适应学习率与动量项。算法用梯度构造了两个向量m和v,前者为动量项,后者累积了梯度的平方和,用于构造自适应学习率。它们的初始值为0,更新公式为:

    其中 \beta_{1} , \beta_{2} 是人工指定的参数,i为向量的分量下标。依靠这两个值构造参数的更新值,参数的更新公式为:

    在这里,m类似于动量项,用v来构造学习率。

    随机梯度下降法

    假设训练样本集有N个样本,有监督学习算法训练时优化的目标是这个数据集上的平均损失函数:

    其中L(w, x_{i} , y_{i} )是对单个训练样本( x_{i} , y_{i} )的损失函数,w是需要学习的参数,r(w)是正则化项, \lambda 是正则化项的权重。在训练样本数很大时,如果训练时每次迭代都用所有样本,计算成本太高,作为改进可以在每次迭代时选取一批样本,将损失函数定义在这些样本上。

    批量随机梯度下降法在每次迭代中使用上面目标函数的随机逼近值,即只使用M \ll N个随机选择的样本来近似计算损失函数。在每次迭代时要优化的目标函数变为:

    随机梯度下降法在概率意义下收敛。

    牛顿法

    牛顿法是二阶优化技术,利用了函数的一阶和二阶导数信息,直接寻找梯度为0的点。牛顿法的迭代公式为:

    其中H为Hessian矩阵,g为梯度向量。牛顿法不能保证每次迭代时函数值下降,也不能保证收敛到极小值点。在实现时,也需要设置学习率,原因和梯度下降法相同,是为了能够忽略泰勒展开中的高阶项。学习率的设置通常采用直线搜索(line search)技术。

    在实现时,一般不直接求Hessian矩阵的逆矩阵,而是求解下面的线性方程组:

    其解d称为牛顿方向。迭代终止的判定依据是梯度值充分接近于0,或者达到最大指定迭代次数。

    牛顿法比梯度下降法有更快的收敛速度,但每次迭代时需要计算Hessian矩阵,并求解一个线性方程组,运算量大。另外,如果Hessian矩阵不可逆,则这种方法失效。对牛顿法更全面的介绍可以阅读SIGAI之前的公众号文章“理解牛顿法”。

    牛顿法在logistic回归,AdaBoost算法等机器学习算法中有实际应用。

    拟牛顿法

    牛顿法在每次迭代时需要计算出Hessian矩阵,并且求解一个以该矩阵为系数矩阵的线性方程组,Hessian矩阵可能不可逆。为此提出了一些改进的方法,典型的代表是拟牛顿法。拟牛顿法的思路是不计算目标函数的Hessian矩阵然后求逆矩阵,而是通过其他手段得到一个近似Hessian矩阵逆的矩阵。具体做法是构造一个近似Hessian矩阵或其逆矩阵的正定对称矩阵,用该矩阵进行牛顿法的迭代。

    所有这些主要的数值优化算法都可以在SIGAI云端实验室上免费完成实验:

    www.sigai.cn

    通过构造目标函数,指定优化算法的参数与初始化迭代值,可以可视化的显示出算法的运行过程,并对不同参数时的求解结果进行比较。

     

     

    可信域牛顿法

    标准牛顿法可能不会收敛到一个最优解,也不能保证函数值会按照迭代序列递减。解决这个问题可以通过调整牛顿方向的步长来实现,目前常用的方法有两种:直线搜索和可信区域法。可信域牛顿法是截断牛顿法的一个变种,用于求解带界限约束的最优化问题。在可信域牛顿法的每一步迭代中,有一个迭代序列 x^{k} ,一个可信域的大小 \Delta_{k} ,以及一个二次目标函数:

    这个式子可以通过泰勒展开得到,忽略二次以上的项,这是对函数下降值:

    的近似。算法寻找一个 s^{k} ,在满足约束条件丨丨s丨丨 \leq \Delta_{k} 下近似最小化 q_{k} (s)。接下来检查如下比值以更新 w^{k} 和 \Delta_{k} :

    是函数值的实际减少量和二次近似模型预测方向导致的函数减少量的比值。根据之前的计算结果,再动态调整可信域的大小。

    可信域牛顿法在logistic回归,线性支持向量的求解时有实际的应用,具体可以阅读liblinear开源库。

    分治法

    分治法是一种算法设计思想,它将一个大的问题分解成子问题进行求解。根据子问题解构造出整个问题的解。在最优化方法中,具体做法是每次迭代时只调整优化向量x的一部分分量,其他的分量固定住不动。

    坐标下降法

    坐标下降法的基本思想是每次对一个变量进行优化,这是一种分治法。假设要求解的优化问题为;

    坐标下降法求解流程为每次选择一个分量 x_{i} 进行优化,将其他分量固定住不动,这样将一个多元函数的极值问题转换为一元函数的极值问题。如果要求解的问题规模很大,这种做法能有效的加快速度。

    坐标下降法在logistic回归,线性支持向量的求解时有实际的应用,具体可以阅读liblinear开源库。

    SMO算法

    SMO算法也是一种分治法,用于求解支持向量机的对偶问题。加上松弛变量和核函数后的对偶问题为:

     

    SMO算法的核心思想是每次在优化变量中挑出两个分量 \alpha_{i} 和 \alpha_{j} 进行优化,让其他分量固定,这样能保证满足等式约束条件。之所以要选择两个变量进行优化而不是选择一个变量,是因为这里有等式约束,如果只调整一个变量的值,将会破坏等式约束。

    假设选取的两个分量为 \alpha_{i} 和 \alpha_{j} ,其他分量都固定即当成常数。对这两个变量的目标函数是一个二元二次函数。这个问题还带有等式和不等式约束条件。对这个子问题可以直接求得公式解,就是某一区间内的一元二次函数的极值。

    分阶段优化

    分阶段优化的做法是在每次迭代时,先固定住优化变量x一部分分量a不动,对另外一部分变量b进行优化;然后再固定住b不动,对b进行优化。如此反复,直至收敛到最优解处。

    AdaBoost算法是这种方法的典型代表。AdaBoost算法在训练时采用了指数损失函数:

    由于强分类器是多个弱分类器的加权和,代入上面的损失函数中,得到算法训练时要优化的目标函数为:

    这里将指数损伤函数拆成了两部分,已有的强分类器 F_{j-1} ,以及当前弱分类器f对训练样本的损失函数,前者在之前的迭代中已经求出,因此可以看成常数。这样目标函数可以简化为:

    其中:

    这个问题可以分两步求解,首先将弱分类器权重 \beta 看成常数,得到最优的弱分类器f。得到弱分类器之后,再优化它的权重系数 \beta 。

    动态规划算法

    动态规划也是一种求解思想,它将一个问题分解成子问题求解,如果整个问题的某个解是最优的,则这个解的任意一部分也是子问题的最优解。这样通过求解子问题,得到最优解,逐步扩展,最后得到整个问题的最优解。

    隐马尔可夫模型的解码算法(维特比算法),强化学习中的动态规划算法是这类方法的典型代表,此类算法一般是离散变量的优化,而且是组合优化问题。前面讲述的基于导数的优化算法都无法使用。动态规划算法能高效的求解此类问题,其基础是贝尔曼最优化原理。一旦写成了递归形式的最优化方程,就可以构造算法进行求解。

     

    推荐阅读

    [1]机器学习-波澜壮阔40年【获取码】SIGAI0413.

    [2]学好机器学习需要哪些数学知识?【获取码】SIGAI0417.

    [3] 人脸识别算法演化史【获取码】SIGAI0420.

    [4]基于深度学习的目标检测算法综述 【获取码】SIGAI0424.

    [5]卷积神经网络为什么能够称霸计算机视觉领域?【获取码】SIGAI0426.

    [6] 用一张图理解SVM的脉络【获取码】SIGAI0428.

    [7] 人脸检测算法综述【获取码】SIGAI0503.

    [8] 理解神经网络的激活函数 【获取码】SIGAI2018.5.5.

    [9] 深度卷积神经网络演化历史及结构改进脉络-40页长文全面解读【获取码】SIGAI0508.

    [10] 理解梯度下降法【获取码】SIGAI0511.

    [11] 循环神经网络综述—语音识别与自然语言处理的利器【获取码】SIGAI0515

    [12] 理解凸优化 【获取码】 SIGAI0518

    [13] 【实验】理解SVM的核函数和参数 【获取码】SIGAI0522

    [14]【SIGAI综述】行人检测算法 【获取码】SIGAI0525

    [15] 机器学习在自动驾驶中的应用—以百度阿波罗平台为例(上)【获取码】SIGAI0529

    [16]理解牛顿法【获取码】SIGAI0531

    [17] 【群话题精华】5月集锦—机器学习和深度学习中一些值得思考的问题【获取码】SIGAI 0601

    [18] 大话Adaboost算法 【获取码】SIGAI0602

    [19] FlowNet到FlowNet2.0:基于卷积神经网络的光流预测算法【获取码】SIGAI0604

    [20] 理解主成分分析(PCA)【获取码】SIGAI0606

    [21] 人体骨骼关键点检测综述 【获取码】SIGAI0608

    [22]理解决策树 【获取码】SIGAI0611

    [23] 用一句话总结常用的机器学习算法【获取码】SIGAI0611

    [24] 目标检测算法之YOLO 【获取码】SIGAI0615

    [25] 理解过拟合 【获取码】SIGAI0618

    [26]理解计算:从√2到AlphaGo ——第1季 从√2谈起 【获取码】SIGAI0620

    [27] 场景文本检测——CTPN算法介绍 【获取码】SIGAI0622

    [28] 卷积神经网络的压缩和加速 【获取码】SIGAI0625

    [29] k近邻算法 【获取码】SIGAI0627

    [30]自然场景文本检测识别技术综述 【获取码】SIGAI0627

    [31] 理解计算:从√2到AlphaGo ——第2季 神经计算的历史背景 【获取码】SIGAI0704

    [32] 机器学习算法地图【获取码】SIGAI0706

    [33] 反向传播算法推导-全连接神经网络【获取码】SIGAI0709

    [34] 生成式对抗网络模型综述【获取码】SIGAI0709.

    [35]怎样成为一名优秀的算法工程师【获取码】SIGAI0711.

    [36] 理解计算:从根号2到AlphaGo——第三季 神经网络的数学模型【获取码】SIGAI0716

    [37]【技术短文】人脸检测算法之S3FD 【获取码】SIGAI0716

    [38] 基于深度负相关学习的人群计数方法【获取码】SIGAI0718

    [39] 流形学习概述【获取码】SIGAI0723

    [40] 关于感受野的总结 【获取码】SIGAI0723

    [41] 随机森林概述 【获取码】SIGAI0725

    [42] 基于内容的图像检索技术综述——传统经典方法【获取码】SIGAI0727

    [43] 神经网络的激活函数总结【获取码】SIGAI0730

    [44] 机器学习和深度学习中值得弄清楚的一些问题【获取码】SIGAI0802

    [45] 基于深度神经网络的自动问答系统概述【获取码】SIGAI0806

    [46] 机器学习与深度学习核心知识点总结 写在校园招聘即将开始时 【获取 码】SIGAI0808

    [47] 理解Spatial Transformer Networks【获取码】SIGAI0810

    [48]AI时代大点兵-国内外知名AI公司2018年最新盘点【获取码】SIGAI0813

    [49] 理解计算:从√2到AlphaGo ——第2季 神经计算的历史背景 【获取码】SIGAI0815

    [50] 基于内容的图像检索技术综述--CNN方法 【获取码】SIGAI0817

    [51]文本表示简介 【获取码】SIGAI0820

    展开全文
  • 机器学习中,有很多的问题并没有解析形式的解,或者有解析形式的解但是计算量很大(譬如,超定问题的最小二乘解),对于此类问题,通常我们会选择采用一种迭代的优化方式进行求解。 负梯度方法与Newton型方法在最...
  • 机器学习算法最终总是能转化为最优化问题,习惯上会转化为最小化问题。 个人总结迭代优化算法关键就两点: (1) 找到下降方向 (2) 确定下降步长 最速梯度下降算法 梯度下降算法是以最优化函数的梯度...
  • 机器学习优化算法—L-BFGS

    千次阅读 2014-11-27 10:15:05
    L-BFGS算法由于其高效的性能而被广泛运用在实际工程中,本文首先介绍L-BFGS算法和其它算法的比较,然后详细介绍该算法的主要思想以及每一步迭代时近似矩阵的更新细节。
  • 优化算法 1、梯度下降法  梯度下降法可以说是机器学习中最常用的算法,当然在深度学习中也会使用。不过一般使用的都是梯度下降法的变体—小批量梯度下降法,因为在样本较大时使用全样本进行梯度下降时需要计算的...
  • 机器学习优化算法概述

    千次阅读 2014-11-25 17:17:50
    机器学习的问题最终都会...大多数机器学习问题最终都要解一个无约束的优化问题,因此本文主要对无约束优化问题及其优化算法做一个概述。下文提到的优化问题都指无约束优化问题。 提到优化问题,自然就要知道优化算法
  • [杂谈] 机器学习优化算法的对比

    千次阅读 2019-08-01 16:57:24
    机器学习算法的本质:  在求解一个问题(输入X,输出什么?)时,不清楚问题的模型是什么,不知道各个变量之间符合什么规则(式子),所以干脆把现成的各种万能模型(线性回归、逻辑回归、SVM、神经网络等等)...
  • Python与机器学习优化算法

    千次阅读 2017-10-19 14:27:23
    Python与机器学习优化算法 回顾圣经,在监督学习中优化算法是关键的步骤——分析模型并得到最优模型,才是最终的目的。
  • 机器学习中,对于目标函数、损失函数、代价函数等不同书上有不同的定义。通常来讲,目标函数可以衡量一个模型的好坏,对于模型的优化通常求解模型的最大化或者最小化,当求取最小化时也称loss function即损失函数...
  • 机器学习算法比较

    千次阅读 2016-05-31 09:42:37
    本文主要回顾下几个常用算法的适应场景及其优缺点!...机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启
  • 机器学习算法 综述(入门)

    万次阅读 多人点赞 2019-06-16 22:19:28
    学习了一个学期机器学习算法,从什么都不懂到对十个机器学习算法有一定的了解,下面总结一下十大机器学习算法,从算法的概念、原理、优点、缺点、应用等方面来总结,如果有错误的地方,欢迎指出。 目录 1.决策树...
  • 机器学习优化算法论文合集

    千次阅读 2019-01-16 18:34:47
    单机确定性优化算法 共轭梯度法:https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf 坐标下降法:http://www.optimization-online.org/DB_FILE/2014/12/4679.pdf 牛顿法: ...
  • 机器学习优化算法之EM算法

    千次阅读 2016-07-13 09:06:43
    EM算法的应用范围很广,基本机器学习需要迭代优化参数的模型在优化时都可以使用EM算法。 EM算法的思想和过程 E-Step:E的全称是Expectation,即期望的意思。E-step也是获取期望的过程。即根据现有的模型,计算各个...
  • 机器学习中的优化算法(附代码)

    千次阅读 2019-07-05 09:46:26
    > 优化算法指通过改善训练方式,来最小化(或最大化)损失函数E(x) 局部最优问题 局部最优与鞍点。在神经网络中,最小化非凸误差函数的另一个关键挑战是避免陷于多个其他局部最小值中。实际上,问题并非源于局部...
  • 机器学习常见的优化算法

    千次阅读 2016-05-01 19:16:48
    机器学习中常见的一些优化算法的总结,以最直接的方式理解。 注:梯度下降法图片来自Rachel-Zhang的博客 机器学习常见的优化算法 不是所有的方程都具有解析解,因此可采用优化的方法寻找其最有解,在机器学习中...
  • 实现算法的论文,代码源码,测试函数,请见本人的git账户: https://github.com/qiu997018209/MachineLearning以下是mymain.m文件内容 clear % mex cec13_func.cpp -DWINDOWS func_num=1; D=10; VRmin=-100; VRmax=...
  • 如何调度高级算法优化代价函数 Matlab实现方法 实例: 假设已知代价函数,我们通过代价函数求得了偏导数 首先,完成代价函数的实现(代码如下) function [jVal,gradient] = costFunc...
1 2 3 4 5 ... 20
收藏数 172,308
精华内容 68,923
关键字:

机器学习优化算法