精华内容
参与话题
问答
  • 优化理论与凸优化到底是干嘛的?

    万次阅读 多人点赞 2017-12-15 20:47:53
    优化的定义 1.1 凸优化 ...1.1 凸优化优化问题目前在机器学习,数据挖掘等领域应用非常广泛,因为机器学习简单来说,主要做的就是优化问题,先初始化一下权重参数,然后利用优化方法来优化这个
    1. 凸优化的定义
      1.1 凸优化
      1.2 全局最优化与局部最优化
    2. Least-squares and linear programming(最小二乘与线性规划)
      2.1 最小二乘
      2.2 线性规划
    3. 最优化方法的一般结构
    4. 优化理论在机器学习,深度学习中扮演的角色

    1.优化的定义

    1.1 凸优化

    最优化问题目前在机器学习,数据挖掘等领域应用非常广泛,因为机器学习简单来说,主要做的就是优化问题,先初始化一下权重参数,然后利用优化方法来优化这个权重,直到准确率不再是上升,迭代停止,那到底什么是最优化问题呢?

    它的一般形式为:

    minimize f0(x)
    使 fi(x)bi,i=1,,m
    第一个为优化的目标,即最小化目标函数f(x),而带大于号或小于号的,则是约束条件。我们希望找到一个满足约束条件的x,使得对于任意的z满足约束条件:
    f1(z)b1,,fm(z)bm
    f0(z)f0(x)
    x就是我们所求的最后结果。

    • 相当于你要从上海去北京,你可以选择搭飞机,或者火车,动车,但只给你500块钱,要求你以最快的时间到达,其中到达的时间就是优化的目标,500块钱是限制条件,选择动车,火车,或者什么火车都是x。

    满足所有约束条件的点集称为可行域,记为X,又可以写为:

    min f(x)   s.t xX
    ,s.t表示受限于(subject to)。

    在优化问题中,应用最广泛的是凸优化问题:

    • 若可行域X是一个凸集:即对于任给的x,yX,总有
      λx+(1λ)yX, λ(0,1)
    • 并且目标函数是一个凸函数:即
      f(λx+(1λ)y))λf(x)+(1λ)f(y)
      我们称这样的优化问题为凸优化问题。

    用图像来表示就是:
    这里写图片描述
    函数上方的点集就是凸集,函数上任意两点的连线,仍然在函数图像上方。

    一句话说清楚就是:希望找到合适的x,使得f0(x)最小。

    1.2 全局最优化与局部最优化

    全局最优化指的是在满足条件约束的情况下,找到唯一的一个点满足最大值或者最小值。

    局部最优化指的是在满足条件约束的情况下,有可能找到一个局部最大/小点,但不是全局最大或者最小的点。
    用图像表示为:
    这里写图片描述

    2.Least-squares and linear programming(最小二乘与线性规划)

    关于这两个问题的更详细的例子会在接下来的文章中说到,这次只是简单的介绍一下我们的内容。

    2.1 最小二乘

    最小二乘问题是无约束的优化问题,通常可以理解为测量值与真实值之间的误差平方和:

    minimize f0(x)=Axb22=i=1k(aTixbi)2
    其中ARk x nk>naTiAix

    这个问题既然没有约束条件,那应该怎么求解呢?我们的目标是求解出最好的x,观察这个式子可以发现,这个式子一定是大于等于0的,所以这样的最优化问题,我们可以把它转成线性方程来求解:

    ATAx=ATb
    AT为A的转置,因此根据矩阵的逆:
    (ATA)1ATA=1
    可以把上式表示为:
    x=(ATA)1ATb

    加权的最小二乘问题

    i=1kwi(aTixbi)2
    权值均为正数,代表每一个aTixbi对结果的影响程度。

    正则化的最小二乘问题:

    i=1k(aTixbi)2+ρi=1nx2i
    ρ是人为的选择的,用来权衡 最小化ki=1(aTixbi)2的同时,使得ni=1x2i不必太大的关系。

    2.2 线性规划
    另一类重要的优化问题是线性规划,它的目标函数和约束条件都是线性的:

    minimize cTx
    s.t    aTixbi,i=1,,m

    用画图的方法,就是根据条件,画出可行域,然后将目标函数在可行域上移动,直到得到最大值。
    这里写图片描述

    3.最优化方法的一般结构

    最优化的过程,相当于爬山,如图:
    这里写图片描述
    希望找到一个点列xk使得他的函数值是一直减少的,直到到达某一停止条件或者达到最小值的点xk.

    用数学上的术语可以表示为:

    • xk为第k次迭代点,dk为第k次搜索方向,αk为第k次迭代的步长因子,则第k次迭代为:
      xk+1=xk+αkdk

    从这里可以看到不同的步长和不同的搜索方向组成了不同的优化方法,这就是最优化理论中所讨论的。fxk的函数,搜索方向dkfxk处的下降方向,即dk满足:

    f(xk)Tdk<0
    或者
    f(xk+1)=f(xk+αkdk)<f(xk)

    而最优化的基本可以表示为:给定初始点xk

    1. 确定搜索方向dk,即按照一定规则画方法确定f在xk处的下降方向
    2. 确定步长因子αk,使得目标函数有一定的下降
    3. xk+1=xk+αkdk
      不断迭代,直到xk+1满足某种某种停止条件,即得到最优解xk+1

    最优化中的问题中,大部分都是在寻找各种各样的方法确定步长和方向,使得迭代的速度尽可能快,得到的解尽可能是最优的解。

    4.优化理论在机器学习,深度学习中扮演的角色

    凸优化,或者更广泛的说,是最优化理论,在目前的机器学习,数据挖掘,或者是深度学习的神经网络中,都要用到。

    他的地位相当于人的脊背一样的,支撑着整个模型的学习过程。因为模型,通俗来说就像人学习思考一样,我们自己知道自己该学什么,该怎么学,发现自己的知识学错了之后怎么调整,但计算机可没有人这么聪明,知道学什么,往哪里学。

    而最优化,就是告诉模型应该学什么,怎么学的工具。模型学习的往往都是一个映射函数,也就是模型中的参数W,这个参数的好坏,得看答案才能知道,但知道自己错了之后,该往哪里学,怎么学,怎么调整,这就是优化理论在其中扮演的角色。如果没有优化理论,那么模型是不知道该怎么学习的,也就是没有了最优化,模型的学习永远都是停滞不前的,这下你知道最优化理论的重要性了吧。

    展开全文
  • 深度学习各种优化函数详解

    万次阅读 2017-04-12 19:47:00
    深度学习中有众多有效的优化函数,比如应用最广泛的SGD,Adam等等,而它们有什么区别,各有什么特征呢?下面就来详细解读一下一、先来看看有哪些优化函数BGD 批量梯度下降所谓的梯度下降方法是无约束条件中最常用的...

    深度学习中有众多有效的优化函数,比如应用最广泛的SGD,Adam等等,而它们有什么区别,各有什么特征呢?下面就来详细解读一下


    一、先来看看有哪些优化函数


    BGD 批量梯度下降

    所谓的梯度下降方法是无约束条件中最常用的方法。假设f(x)是具有一阶连续偏导的函数,现在的目标是要求取最小的f(x) : min f(x)

    核心思想:负梯度方向是使函数值下降最快的方向,在迭代的每一步根据负梯度的方向更新x的值,从而求得最小的f(x)。因此我们的目标就转变为求取f(x)的梯度。

    当f(x)是凸函数的时候,用梯度下降的方法取得的最小值是全局最优解,但是在计算的时候,需要在每一步(xk处)计算梯度,它每更新一个参数都要遍历完整的训练集,不仅很慢,还会造成训练集太大无法加载到内存的问题,此外该方法还不支持在线更新模型。其代码表示如下:

    for i in range(nb_epochs):
      params_grad = evaluate_gradient(loss_function, data, params)
      params = params - learning_rate * params_grad

    我们首先需要针对每个参数计算在整个训练集样本上的梯度,再根据设置好的学习速率进行更新。

    公式表示如下:
    假设h(theta)是我们需要拟合的函数,n表示参数的个数,m表示训练集的大小。J(theta)表示损失函数。
    这里写图片描述

    这里写图片描述

    不难看出,在批量梯度下降法中,因为每次都遍历了完整的训练集,其能保证结果为全局最优,但是也因为我们需要对于每个参数求偏导,且在对每个参数求偏导的过程中还需要对训练集遍历一次,当训练集(m)很大时,这个计算量是惊人的!

    所以,为了提高速度,减少计算量,提出了SGD随机梯度下降的方法,该方法每次随机选取一个样本进行梯度计算,大大降低了计算成本。


    SGD随机梯度下降

    随机梯度下降算法和批量梯度下降的不同点在于其梯度是根据随机选取的训练集样本来决定的,其每次对theta的更新,都是针对单个样本数据,并没有遍历完整的参数。当样本数据很大时,可能到迭代完成,也只不过遍历了样本中的一小部分。因此,其速度较快,但是其每次的优化方向不一定是全局最优的,但最终的结果是在全局最优解的附近。

    需要:学习速率 ϵ, 初始参数 θ
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差并更新参数

    代码表示如下:(需要注意的是,在每次迭代训练中,需要重新洗牌训练集)

    for i in range(nb_epochs):
      np.random.shuffle(data)
      for example in data:
        params_grad = evaluate_gradient(loss_function, example, params)
        params = params - learning_rate * params_grad

    虽然BGD可以让参数达到全局最低点并且停止,而SGD可能会让参数达到局部最优,但是仍然会波动,甚至在训练过程中让参数会朝一个更好的更有潜力的方向更新。但是众多的实验表明,当我们逐渐减少学习速率时,SGD和BGD会达到一样的全局最优点。

    优点:
    训练速度快,避免了批量梯度更新过程中的计算冗余问题,对于很大的数据集,也能够以较快的速度收敛.

    缺点:
    由于是抽取,因此不可避免的,得到的梯度肯定有误差.因此学习速率需要逐渐减小,否则模型无法收敛
    因为误差,所以每一次迭代的梯度受抽样的影响比较大,也就是说梯度含有比较大的噪声,不能很好的反映真实梯度.并且SGD有较高的方差,其波动较大,如下图:
    这里写图片描述

    学习速率该如何调整:
    那么这样一来,ϵ如何衰减就成了问题.如果要保证SGD收敛,应该满足如下两个要求:

    这里写图片描述

    而在实际操作中,一般是进行线性衰减:

    这里写图片描述

    其中ϵ0是初始学习率, ϵτ是最后一次迭代的学习率. τ自然代表迭代次数.一般来说,ϵτ 设为ϵ0的1%比较合适.而τ一般设为让训练集中的每个数据都输入模型上百次比较合适.那么初始学习率ϵ0怎么设置呢?书上说,你先用固定的学习速率迭代100次,找出效果最好的学习速率,然后ϵ0设为比它大一点就可以了.

    • 另外,需要注意的是因为存在样本选择的随机性,所以在梯度下降过程中会存在较大的噪声,因此学习速率应该要逐渐减小,来寻找一个相对全局最优的方向。

    • 同时也考虑到每次只选择一个样本进行梯度更新存在较大的噪声,学者们开始尝试每次选择一小批样本进行梯度更新,在降低噪声的同时提高速度,因此就有了下面的MBGD小批量梯度下降法。


    MBGD小批量梯度下降

    为了综合上述两种方法,提出了小批量梯度下降。它:(1)降低在SGD中高方差的问题,能使得收敛更加稳定;(2)可以利用深度学习中最先进的库进行矩阵优化的操作,加速操作;(3)一般的小批量介于50~256,但是当适用很小的批量时,有时也统称为SGD。

    核心思想:在每次迭代时考虑一小部分样本,比如考虑10个样本,同时计算在这10个样本点上的每个参数的偏导数,对于每个优化参数,将该参数在这10个样本点的偏导数求和。

    代码表示:

    for i in range(nb_epochs):
      np.random.shuffle(data)
      for batch in get_batches(data, batch_size=50):
        params_grad = evaluate_gradient(loss_function, batch, params)
        params = params - learning_rate * params_grad

    但是,需要注意的是因为这里也存在样本选择的随机性,学习速率应该要逐渐减小,同时上述方法并不能保证好的收敛性。主要存在的挑战有:

    1. 选择适当的学习率可能很困难。 太小的学习率会导致收敛性缓慢,而学习速度太大可能会妨碍收敛,并导致损失函数在最小点波动。
    2. 使用学习率计划:尝试在训练期间调整学习率。 比如根据预先制定的规则缓慢的降低学习速率,或者当每次迭代之间的偏导差异已经低于某个阈值时,就降低学习速率。但是这里面的学习速率更新规则,以及阈值都是需要预先设定的,因此不适应于所有的数据集。
    3. 此外,使用梯度更新的方法会导致所有参数都用学习速率更新。但是当训练集数据是稀疏的,或者特征的频率是不同的,我们可能不希望它们更新到同样的程度,因此使用相同的学习速率会导致那些很少出现的特征有较大的变化。
    4. 在求取那些高度非凸的误差函数的最小值时,我们应该避免陷入局部最优解,实验表明,最困难的不是从局部最优而是鞍点,鞍点就是沿着某一个方向他是稳定的,沿着另一个方向不稳定,既不是最小点也不是最大点。这会使得该点在所有维度上梯度为0,让SGD难以逃脱。

    基于上述问题,又有了如下更多的优化策略!


    momentum

    上述SGD和MBGD算法都存在样本选择的随机性,因此含有较多的噪声,而momentum能解决上述噪声问题,尤其在面对小而较多噪声的梯度时,它往往能加速学习速率。

    这里写图片描述

    核心思想:Momentum借用了物理中的动量概念,即前几次的梯度也会参与运算。为了表示动量,引入了一个新的变量v(velocity)。v是之前的梯度的累加,但是每回合都有一定的衰减。

    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,并更新速度v和参数θ:

    ĝ ←+1m∇θ∑iL(f(xi;θ),yi)
    v←αv−ϵĝ
    θ←θ+v

    其中参数α表示每回合速率v的衰减程度.同时也可以推断得到,如果每次迭代得到的梯度都是g,那么最后得到的v的稳定值为 ϵ∥g∥/1−α

    也就是说,Momentum最好情况下能够将学习速率加速1/1−α倍.一般α的取值为0.9或者更小。当然,也可以让α的值随着时间而变化,一开始小点,后来再加大.不过这样一来,又会引进新的参数.

    特点:
    本质上来说,就和我们把球从山上退下来一样,球的速度会越来越快。和我们的参数更新一样,当方向一致时,动量项会增加;当方向不一致时,动量项会降低。
    即:
    前后梯度方向一致时,能够加速学习
    前后梯度方向不一致时,能够抑制震荡


    Nesterov Momentum

    仅仅有一个追求速度的球往山下滚是不能令人满意的,我们需要一个球,它能知道往前一步的信息,并且当山坡再次变陡时他能够减速。因此,带有nesterov的出现了!

    在momentum里,先计算当前的梯度(短蓝色线),然后结合以前的梯度执行更新(长蓝色线)。而在nesterov momentum里,先根据事先计算好的梯度更新(棕色),然后在预计的点处计算梯度(红色),结合两者形成真正的更新方向(绿色)。
    这里写图片描述
    这是对之前的Momentum的一种改进,大概思路就是,先对参数进行估计(先往前看一步,探路),然后使用估计后的参数来计算误差
    具体实现:
    需要:学习速率 ϵ, 初始参数 θ, 初始速率v, 动量衰减参数α
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,并更新速度v和参数θ:

    ĝ ←+1m∇θ∑iL(f(xi;θ+αv),yi)
    v←αv−ϵĝ
    θ←θ+v

    注意在估算ĝ 的时候,参数变成了θ+αv而不是之前的θ

    推荐好文——揭开nesters momentum的面纱


    AdaGrad

    AdaGrad可以自动变更学习速率,只是需要设定一个全局的学习速率ϵ,但是这并非是实际学习速率,实际的速率是与以往参数的模之和的开方成反比的.也许说起来有点绕口,不过用公式来表示就直白的多:

    这里写图片描述

    其中δ是一个很小的常亮,大概在10−7,防止出现除以0的情况.

    核心思想:对于频繁出现的参数使用更小的更新速率,对于不频繁出现的参数使用更大的更新速率。
    正因为如此,该优化函数脚适用于稀疏的数据,比如在Google从YouTube视频上识别猫时,该优化函数大大提升了SGD的鲁棒性。在训练GloVe词向量时该优化函数更加适用。

    具体实现:
    需要:全局学习速率 ϵ, 初始参数 θ, 数值稳定量δ
    中间变量: 梯度累计量r(初始化为0)
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,更新r,再根据r和梯度计算参数更新量

    在SGD中,我们对所有参数进行同时更新,这些参数都使用同样的学习速率。
    比图用gt,i表示在t时间点,对i参数求得的偏导。
    这里写图片描述
    那么在SGD中就会用同一个学习速率对i参数进行更新:
    这里写图片描述
    但是在adagrad里,会综合考虑i之前的所有梯度值来更新学习速率,其中Gt,ii是一个对角矩阵,i行i列存储了目前时间点为止的所有i参数的偏导的平方和。后面的项是一个很小的值(1e−8),为了防止除0错误。
    这里写图片描述
    优点:
    能够实现学习率的自动更改。如果这次梯度大,那么学习速率衰减的就快一些;如果这次梯度小,那么学习速率衰减的就慢一些。

    缺点:
    最大的缺点在于分母中那个G是偏导的累积,随着时间的推移,分母会不断的变大,最后会使得学习速率变的非常小,而此时会使得模型不再具备学习其他知识的能力。
    经验表明,在普通算法中也许效果不错,但在深度学习中,深度过深时会造成训练提前结束。因为它到后面的衰减可能越来越慢,然后就提前结束了。为了解决提前结束的问题,引入了如下的算法:Adadelta!RMSprop!


    Adadelta
    adadelta是adagrad的延伸,不同于adadelta将以前所有的偏导都累加起来,adadelta控制了累加的范围到一定的窗口中。
    但是,并非简单的将窗口大小设置并且存储,我们是通过下式动态改变的上述的G:
    这里写图片描述
    这里面的gamma类似于momentum里面的项(通常取值0.9),用来控制更新的权重。
    因此以前的:
    这里写图片描述
    将被改变为:
    这里写图片描述


    RMSprop

    RMSProp通过引入一个衰减系数,让r每回合都衰减一定比例,类似于Momentum中的做法。(我觉得和Adadelta没啥区别)

    具体实现:
    需要:全局学习速率 ϵ, 初始参数 θ, 数值稳定量δ,衰减速率ρ
    中间变量: 梯度累计量r(初始化为0)
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,更新r,再根据r和梯度计算参数更新量

    这里写图片描述

    算法的提出者建议如上式所示,gamma取0.9,学习速率为0.001

    优点:
    相比于AdaGrad,这种方法很好的解决了深度学习中过早结束的问题
    适合处理非平稳目标,对于RNN效果很好

    缺点:
    又引入了新的超参,衰减系数ρ
    依然依赖于全局学习速率


    Adam

    Adam(Adaptive Moment Estimation)是另外一种给每个参数计算不同更新速率的方法,其本质上是带有动量项的RMSprop,它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。它和上述的adadelta和RMSprop一样,都存储了以前的偏导平方衰减平均值,此外,它还存储以前的偏导衰减平均值。

    具体实现:
    需要:步进值 ϵ, 初始参数 θ, 数值稳定量δ,一阶动量衰减系数ρ1, 二阶动量衰减系数ρ2
    其中几个取值一般为:δ=10−8,ρ1=0.9,ρ2=0.999
    中间变量:一阶动量s,二阶动量r,都初始化为0
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,更新r和s,再根据r和s以及梯度计算参数更新量

    这里写图片描述

    其中的Mt和Vt分别表示平均值角度和非中心方差角度的偏导。
    这里写图片描述
    这里写图片描述

    才方法的作者建议 β1取0.9, β2取0.999 ,ϵ取10-8。并且声称Adam在实践中比其他的自适应算法有更好的表现。


    二、可视化

    让我们来可视化的看看它们的表现:

    比较一下速度:
    这里写图片描述

    比较一下在鞍点的性能:
    这里写图片描述


    三、如何选择


    • 如果你的数据很稀疏,那应该选择有自适应性的优化函数。并且你还可以减少调参的时间,用默认参数取得好的结果。
    • RMSprop是adagrad的一个拓展,旨在解决它提前结束的问题。
    • 而RMSprop和Adadelta类似,只是adadelta采用了RMS的方法更新参数。
    • 在RMSprop基础上增加了偏差校正和momentum,形成了Adam。
    • 综上,RMSprop、Adadelta、Adam都是类似的。
    • Kingma【Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13.】的实验表示,偏差校正使得Adam在优化到后面梯度变的稀疏的时候使得其优化性能最好。
    • 所以,可能Adam是最好的优化函数。
    • 所以,如果你希望你的训练能变的更快,或者你要训练的是一个复杂的深度的网络,尽量选择自适应的优化函数。

    参考

    展开全文
  • 程序员的数学:优化理论

    千人学习 2019-11-11 01:10:08
    程序员的数学-优化理论
  • 优化方法总结:SGD,Momentum,AdaGrad,RMSProp,Adam

    万次阅读 多人点赞 2017-08-06 10:55:40
    1. SGDBatch Gradient Descent在每一轮的训练过程中,Batch Gradient Descent算法用整个训练集的数据计算cost fuction的梯度,并用该梯度对模型参数进行更新:Θ=Θ−α⋅▽ΘJ(Θ)\Theta = \Theta -\alpha \cdot \...

    1. SGD

    Batch Gradient Descent

    在每一轮的训练过程中,Batch Gradient Descent算法用整个训练集的数据计算cost fuction的梯度,并用该梯度对模型参数进行更新:

    Θ=Θ−α⋅▽ΘJ(Θ) \Theta = \Theta -\alpha \cdot \triangledown_\Theta J(\Theta ) Θ=ΘαΘJ(Θ)

    优点:

    • cost fuction若为凸函数,能够保证收敛到全局最优值;若为非凸函数,能够收敛到局部最优值

    缺点:

    • 由于每轮迭代都需要在整个数据集上计算一次,所以批量梯度下降可能非常慢
    • 训练数较多时,需要较大内存
    • 批量梯度下降不允许在线更新模型,例如新增实例。

    Stochastic Gradient Descent

    和批梯度下降算法相反,Stochastic gradient descent 算法每读入一个数据,便立刻计算cost fuction的梯度来更新参数:
    Θ=Θ−α⋅▽ΘJ(Θ;x(i),y(i))\Theta = \Theta -\alpha \cdot \triangledown_\Theta J(\Theta ;x^{(i)},y^{(i)})Θ=ΘαΘJ(Θ;x(i),y(i))

    优点:

    • 算法收敛速度快(在Batch Gradient Descent算法中, 每轮会计算很多相似样本的梯度, 这部分是冗余的)
    • 可以在线更新
    • 有几率跳出一个比较差的局部最优而收敛到一个更好的局部最优甚至是全局最优

    缺点:

    • 容易收敛到局部最优,并且容易被困在鞍点

    Mini-batch Gradient Descent

    mini-batch Gradient Descent的方法是在上述两个方法中取折衷, 每次从所有训练数据中取一个子集(mini-batch) 用于计算梯度:
    Θ=Θ−α⋅▽ΘJ(Θ;x(i:i+n),y(i:i+n))\Theta = \Theta -\alpha \cdot \triangledown_\Theta J(\Theta ;x^{(i:i+n)},y^{(i:i+n)})Θ=ΘαΘJ(Θ;x(i:i+n),y(i:i+n))

    Mini-batch Gradient Descent在每轮迭代中仅仅计算一个mini-batch的梯度,不仅计算效率高,而且收敛较为稳定。该方法是目前深度学训练中的主流方法

    上述三个方法面临的主要挑战如下:

    • 选择适当的学习率α\alphaα 较为困难。太小的学习率会导致收敛缓慢,而学习速度太块会造成较大波动,妨碍收敛。
    • 目前可采用的方法是在训练过程中调整学习率大小,例如模拟退火算法:预先定义一个迭代次数m,每执行完m次训练便减小学习率,或者当cost function的值低于一个阈值时减小学习率。然而迭代次数和阈值必须事先定义,因此无法适应数据集的特点。
    • 上述方法中, 每个参数的 learning rate 都是相同的,这种做法是不合理的:如果训练数据是稀疏的,并且不同特征的出现频率差异较大,那么比较合理的做法是对于出现频率低的特征设置较大的学习速率,对于出现频率较大的特征数据设置较小的学习速率。
    • 近期的的研究表明,深层神经网络之所以比较难训练,并不是因为容易进入local minimum。相反,由于网络结构非常复杂,在绝大多数情况下即使是 local minimum 也可以得到非常好的结果。而之所以难训练是因为学习过程容易陷入到马鞍面中,即在坡面上,一部分点是上升的,一部分点是下降的。而这种情况比较容易出现在平坦区域,在这种区域中,所有方向的梯度值都几乎是 0。

    2. Momentum

    SGD方法的一个缺点是其更新方向完全依赖于当前batch计算出的梯度,因而十分不稳定。Momentum算法借用了物理中的动量概念,它模拟的是物体运动时的惯性,即更新的时候在一定程度上保留之前更新的方向,同时利用当前batch的梯度微调最终的更新方向。这样一来,可以在一定程度上增加稳定性,从而学习地更快,并且还有一定摆脱局部最优的能力:

    vt=γ⋅vt−1+α⋅▽ΘJ(Θ)v_{t} = \gamma \cdot v_{t-1} + \alpha \cdot \triangledown_\Theta J(\Theta )vt=γvt1+αΘJ(Θ)
    Θ=Θ−vt\Theta = \Theta-v_{t}Θ=Θvt

    Momentum算法会观察历史梯度vt−1v_{t-1}vt1,若当前梯度的方向与历史梯度一致(表明当前样本不太可能为异常点),则会增强这个方向的梯度,若当前梯度与历史梯方向不一致,则梯度会衰减。**一种形象的解释是:**我们把一个球推下山,球在下坡时积聚动量,在途中变得越来越快,γ可视为空气阻力,若球的方向发生变化,则动量会衰减。

    3. Nesterov Momentum

    在小球向下滚动的过程中,我们希望小球能够提前知道在哪些地方坡面会上升,这样在遇到上升坡面之前,小球就开始减速。这方法就是Nesterov Momentum,其在凸优化中有较强的理论保证收敛。并且,在实践中Nesterov Momentum也比单纯的 Momentum 的效果好:

    vt=γ⋅vt−1+α⋅▽ΘJ(Θ−γvt−1)v_{t} = \gamma \cdot v_{t-1} + \alpha \cdot \triangledown_\Theta J(\Theta -\gamma v_{t-1})vt=γvt1+αΘJ(Θγvt1)
    Θ=Θ−vt\Theta = \Theta-v_{t}Θ=Θvt

    其核心思想是:注意到 momentum 方法,如果只看 γ * v 项,那么当前的 θ经过 momentum 的作用会变成 θ-γ * v。因此可以把 θ-γ * v这个位置看做是当前优化的一个”展望”位置。所以,可以在 θ-γ * v求导, 而不是原始的θ。
    这里写图片描述

    4. Adagrad

    上述方法中,对于每一个参数θiθ_iθi 的训练都使用了相同的学习率α。Adagrad算法能够在训练中自动的对learning rate进行调整,对于出现频率较低参数采用较大的α更新;相反,对于出现频率较高的参数采用较小的α更新。因此,Adagrad非常适合处理稀疏数据。

    我们设gt,ig_{t,i}gt,i为第t轮第i个参数的梯度,即gt,i=▽ΘJ(Θi)g_{t,i}=\triangledown_\Theta J(\Theta_i)gt,i=ΘJ(Θi)。因此,SGD中参数更新的过程可写为:

    Θt+1,i=Θt,i−α⋅gt,i\Theta_{t+1,i} =\Theta_{t,i}-\alpha \cdot g_{t,i}Θt+1,i=Θt,iαgt,i

    Adagrad在每轮训练中对每个参数θiθ_iθi的学习率进行更新,参数更新公式如下:

    Θt+1,i=Θt,i−αGt,ii+ϵ⋅gt,i\Theta_{t+1,i} =\Theta_{t,i}- \frac{\alpha}{\sqrt{G_{t,ii}+\epsilon }}\cdot g_{t,i}Θt+1,i=Θt,iGt,ii+ϵαgt,i

    其中,Gt∈Rd×dG_t\in \mathbb{R}^{d\times d}GtRd×d为对角矩阵,每个对角线位置i,ii,ii,i为对应参数θiθ_iθi从第1轮到第t轮梯度的平方和。ϵ是平滑项,用于避免分母为0,一般取值1e−8。Adagrad的缺点是在训练的中后期,分母上梯度平方的累加将会越来越大,从而梯度趋近于0,使得训练提前结束。

    5. RMSprop

    RMSprop是Geoff Hinton提出的一种自适应学习率方法。Adagrad会累加之前所有的梯度平方,而RMSprop仅仅是计算对应的平均值,因此可缓解Adagrad算法学习率下降较快的问题。
    E[g2]t=0.9E[g2]t−1+0.1gt2E[g^2]_t=0.9E[g^2]_{t-1}+0.1g_t^2E[g2]t=0.9E[g2]t1+0.1gt2
    Θt+1=Θt−αE[g2]t+ϵ⋅gt\Theta_{t+1} =\Theta_{t}- \frac{\alpha}{\sqrt{E[g^2]_t+\epsilon }}\cdot g_{t}Θt+1=ΘtE[g2]t+ϵαgt

    6. Adam

    Adam(Adaptive Moment Estimation)是另一种自适应学习率的方法。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。公式如下:
    mt=β1mt−1+(1−β1)gtm_t=\beta_1m_{t-1}+(1-\beta_1)g_tmt=β1mt1+(1β1)gt
    vt=β2vt−1+(1−β2)gt2v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2vt=β2vt1+(1β2)gt2
    m^t=mt1−β1t\hat{m}_t=\frac{m_t}{1-\beta_1^t}m^t=1β1tmt
    v^t=vt1−β2t\hat{v}_t=\frac{v_t}{1-\beta_2^t}v^t=1β2tvt
    Θt+1=Θt−αv^t+ϵm^t\Theta_{t+1} =\Theta_{t}- \frac{\alpha}{\sqrt{\hat{v}_t }+\epsilon }\hat{m}_tΘt+1=Θtv^t+ϵαm^t

    其中,mtm_tmtvtv_tvt分别是对梯度的一阶矩估计和二阶矩估计,可以看作对期望E[gt]E[g_t]E[gt]E[gt2]E[g_t^2]E[gt2]的近似;mt^\hat{m_t}mt^vt^\hat{v_t}vt^是对mtm_tmtvtv_tvt的校正,这样可以近似为对期望的无偏估计。 Adam算法的提出者建议β1\beta_1β1 的默认值为0.9,β2\beta_2β2的默认值为.999,$\epsilon $默认为10−810^{-8}108。 另外,在数据比较稀疏的时候,adaptive的方法能得到更好的效果,例如Adagrad,RMSprop, Adam 等。Adam 方法也会比 RMSprop方法收敛的结果要好一些, 所以在实际应用中 ,Adam为最常用的方法,可以比较快地得到一个预估结果。

    最后两张动图从直观上展现了算法的优化过程。第一张图为不同算法在损失平面等高线上随时间的变化情况,第二张图为不同算法在鞍点处的行为比较。
    这里写图片描述

    这里写图片描述

    7. 参考资料

    展开全文
  • 优化算法——常见优化算法分类及总结

    万次阅读 多人点赞 2018-10-27 12:54:53
    之前做特征选择,实现过基于群智能算法进行最优化的搜索,看过一些群智能优化算法的论文,在此做一下总结。 最优化问题  在生活或者工作中存在各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题“在...

    之前做特征选择,实现过基于群智能算法进行最优化的搜索,看过一些群智能优化算法的论文,在此做一下总结。

    最优化问题

      在生活或者工作中存在各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题“在一定成本下,如何使利润最大化”等。最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。

      工程设计中最优化问题(optimalization problem)的一般提法是要选择一组参数(变量),在满足一系列有关的限制条件(约束)下,使设计指标(目标)达到最优值。因此,最优化问题通常可以表示为数学规划形式的问题。进行工程优化设计时,应将工程设计问题用上述形式表示成数学问题,再用最优化的方法求解。这项工作就是建立优化设计的数学模型。

    optimalization

      
      最优化问题分为函数优化问题和组合优化问题两大类,其中函数优化的对象是一定区间的连续变量,而组合优化的对象则是解空间中的离散状态。其中典型的组合优化问题有旅行商(Traveling salesman problem,TSP)问题、加工调度问题(Scheduling problem,如Flow-shop,Job-shop)、0-1背包问题(Knapsack problem)、装箱问题(Bin packing problem)、图着色问题(Graph coloring problem)、聚类问题(Clustering problem)等。

    最优化算法

    根据自己对最优化的理解,采用最优化算法解决实际问题主要分为下列两步:

    • 建立数学模型。对可行方案进行编码(变量),约束条件以及目标函数的构造。
    • 最优值的搜索策略。在可行解(约束条件下)搜索最优解的方法,有穷举、随机和启发式搜索方法。

    最优化算法有三要素:变量(Decision Variable)、约束条件(Constraints)和目标函数(Objective function)。最优化算法,其实就是一种搜索过程或规则,它是基于某种思想和机制,通过一定的途径或规则来得到满足用户要求的问题的解。

    优化问题相关算法有如下分类:

    优化算法

    精确算法(绝对最优解)

    精确算法包括线性规划、动态规划、整数规划和分支定界法等运筹学中的传统算法,其算法计算复杂性一般很大,只适合于求解小规模问题,在工程中往往不实用。

    启发式算法(近似算法)

      启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案。

    领域搜索算法。从任一解出发,对其领域的不断搜索和当前解的替换来实现优化。根据搜索行为,它又可分为局部搜索法和指导性搜索法。

    • 局部领域搜索法(也称爬山法)。以局部优化策略在当前解的领域中贪婪搜索,如只接受优于当前解的状态作为下一当前解的爬山法;接受当前邻域中的最好解作为下一当前解的最陡下降法等。

    • 指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索,如SA、GA、EP、ES和TS等.

    个体启发(寻找相对最优)

    特点:每次输出的是相同的。从一个解开始,寻找最优,易陷入局部最优。

    爬山算法

    算法思想:从当前的节点开始,和周围的邻居节点的值进行比较。如果当前节点是最大的,那么返回当前节点,作为最大值(即山峰最高点);反之就用最高的邻居节点替换当前节点,从而实现向山峰的高处攀爬的目的。

    其实就是,在初始值的附近,找到最大的一个。

    • 优点

      • 容易理解,容易实现,具有较强的通用性;
      • 局部开发能力强,收敛速度很快
    • 缺点

      • 全局开发能力弱,只能搜索到局部最优解;
      • 搜索结果完全依赖于初始解和邻域的映射关系。

    禁忌算法(Tabu Search,TS)

    基本思想:基于爬山算法的改进,标记已经解得的局部最优解或求解过程,并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于,太过于对某一局部区域以及其邻域的搜索,导致一叶障目。为了找到全局最优解,禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它,从而或得更多的搜索区域

    • 特点:

      • 避免在搜索过程中的循环
      • 只进不退的原则,通过禁忌表实现
      • 不以局部最优作为停止准则
      • 邻域选优的规则模拟了人类的记忆功能
    • 禁忌表:用于防止搜索出现循环

      • 记录前若干步走过的点、方向或目标值,禁止返回
      • 表是动态更新的
      • 表的长度称为Tabu-Size
    • 禁忌表的主要指标(两项指标)

      • 禁忌对象:禁忌表中被禁的那些变化元素
      • 禁忌长度:禁忌的步数
    • 禁忌对象(三种变化)

      • 以状态本身或者状态的变化作为禁忌对象
      • 以状态分量以及分量的变化作为禁忌对象
      • 采用类似的等高线做法,以目标值变化作为禁忌对象
    • 禁忌长度:可以是一个固定的常数(T=c),也可以是动态变化的,可按照某种规则或公式在区间内变化。

      • 禁忌长度过短,一旦陷入局部最优点,出现循环无法跳出;
      • 禁忌长度过长,候选解全部被禁忌,造成计算时间较大,也可能造成计算无法继续下去。

    参考:

    1. 禁忌搜索算法(Tabu Search)
    2. 禁忌搜索算法详解

    贪婪算法

    从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。

    基本都要先排序,从排序的开始那个依次判断,符合就留下不符合就去掉。

    模拟退火(simulated annealing,SA)

    模拟退火算法作为局部搜索算法的扩展,在每一次修改模型的过程中,随机产生一个新的状态模型,然后以一定的概率选择邻域中能量值大的状态.这种接受新模型的方式使其成为一种全局最优算法,并得到理论证明和实际应用的验证.SA虽然在寻优能力上不容置疑,但它是以严密的退火计划为保证的,具体地讲,就是足够高的初始温度、缓慢的退火速度、大量的迭代次数及同一温度下足够的扰动次数。

    用兔子的故事来说:兔子喝醉了。他随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。

    其实就是,先用初始值进行随机更新,记录每次更新的值,最后取历史记录中最大的值。

    参考:模拟退火算法

    群体智能(全局最优)

    类别:

    • 粒子群算法(PSO)
    • 蚁群算法(ACO)
    • 人工蜂群算法(ABC)
    • 人工鱼群算法(AFSA)
    • 混洗蛙跳算法(SFLA)
    • 烟花算法(FWA)
    • 细菌觅食优化(BFO)
    • 萤火虫算法(FA)

    特点:

    • 全局寻优
    • 每次的解都不同
    • 时间较长

    智能计算包括:

    • 进化算法(EC),如遗传算法。
    • 模糊逻辑
    • 群智能(SI)算法
    • 人工免疫系统(AIS)
    • 人工神经网络(ANN)

    参考:

    1. 最优化问题及其分类
    2. 遗传算法
    3. 《MATLAB神经网络30个案例分析》的13个案例中的GA优化SVM参数
    4. 手把手教你实现SVM算法(一)
    5. 遗传算法学习笔记(一):常用的选择策略
    6. 粒子群算法介绍(讲解的很清晰,将PSO的算法原理、算法特点以及参数的设置)
    7. 群体智能简介ppt(粒子群和人工蚁群优化)
    8. 优化算法分类

     

    原文出处:http://dingby.site/2018/04/07/%E6%9C%80%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95%E2%80%94%E2%80%94%E5%B8%B8%E8%A7%81%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95%E5%88%86%E7%B1%BB%E5%8F%8A%E6%80%BB%E7%BB%93/

    展开全文
  • 优化

    2019-12-13 10:49:23
    做了大概半年多VR应用了,VR由于双眼double渲染的原因,对性能的优化要求比较高,在项目的进展过程中,总结了一些关于移动平台上Unity3D的性能优化经验,供分享。 一、移动平台硬件架构 移动平台无论是Android ...
  • 三种快排,四种优化

    千次阅读 2018-08-31 16:18:07
    1、快速排序的基本思想: 快速排序使用分治的思想,通过一趟排序将待排序列分割成两部分,其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。...
  • 优化理论与方法

    千次阅读 2019-04-23 12:28:47
    优化问题 :eg:,其中x在控制问题中被称为为控制决策变量;在数学优化中叫做决策量。无论是最优控制还是数学优化(数学规划)都是优化问题,即都是这样的形式。 1. 优化的两个基本问题 确定一个优化的必要或/和...
  • 三种快排及四种优化方式

    千次阅读 2018-05-02 21:29:50
    文章: 三种快排及四种优化方式 博文地址:https://blog.csdn.net/hacker00011000/article/details/52176100 1、快速排序的基本思想:  快速排序使用分治的思想,通过一趟排序将待排序列分割成两部分,其中一...
  • 常见的几种最优化方法

    万次阅读 2017-02-23 21:55:50
    参考:http://blog.csdn.net/majinlei121/article/details/47260917 ...
  • for循环之性能优化

    千次阅读 多人点赞 2020-01-19 11:24:43
    for循环是开发时常用的语法之一,比如对数组,集合的遍历等,但是如果使用不好也会出现很多新能损耗的问题,今天就来讲解一下for循环的常用性能优化问题。 嵌套循环 嵌套循环是有俩层或者俩层以上的循环嵌套在一起...
  • 前言:最近在做一些OpenCV的优化相关的东西,发现OpenCV现在的执行效率很高的原因一部分是来自于底层的优化,比如指令集优化,但是一直没找到比较系统性的关于CPU指令集优化的文章或者是书籍,于是自己打算做一个...
  • 粒子群优化算法(PSO)

    万次阅读 多人点赞 2018-06-04 20:07:09
    粒子群优化算法(Partical Swarm Optimization PSO),粒子群中的每一个粒子都代表一个问题的可能解,通过粒子个体的简单行为,群体内的信息交互实现问题求解的智能性。由于PSO操作简单、收敛速度快,...
  • 优化算法之粒子群算法(PSO)

    万次阅读 多人点赞 2018-08-03 10:26:45
      粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的协作和信息共享来寻找最优...
  • 优化算法——遗传算法

    万次阅读 多人点赞 2015-05-10 17:09:28
    与遗传算法的第一次接触 遗传算法的基本概念 基本定义 遗传算法的基本流程 遗传算法过程中的具体操作 参数的编码 二进制编码 Gray编码 实数编码 有序编码 初始群体的设定 适应度函数的计算 遗传操作设计 选择...
  • 基于遗传算法的BP神经网络优化算法

    万次阅读 多人点赞 2016-04-10 20:22:41
    遗传算法优化BP神经网络分为BP神经网络结构确定、遗传算法优化和 BP神经网络预测3个部分。其中,BP神经网络结构确定部分根据拟合函数输入输出参数个数确定 BP神经网络结构,这样就可以确定遗传算法优化参数个数,...
  • 优化算法

    千次阅读 2019-08-09 03:17:13
    优化算法1 小批量梯度下降(Mini-batch gradient descent)1.1 什么是小批量下降算法1.2 如何设置batch的大小 1 小批量梯度下降(Mini-batch gradient descent) 1.1 什么是小批量下降算法 机器学习是一个高度依赖...
  • 智能优化算法

    万次阅读 2018-09-03 21:27:12
    智能优化算法 目录 智能优化算法 目录 遗传算法(Genetic Algorithm) 理论 特点 领域 算法流程 差分进化算法(Differential Evolution Algorithm) 理论 特点 领域 算法流程 免疫算法(Immune Algorithm,...
  • 最近研究了一下梯度下降的几个算法,网上python的源码少且不清晰,我自己全部实现了一遍,我觉得还是相当清晰明了的,话不多说,且看下文: 文章目录梯度下降批量梯度下降BGD随机梯度下降SGD带动量的随机梯度下降...
  • 优化算法

    千次阅读 2010-03-13 10:05:00
    PSO粒子群优化算法 1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation),由Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究 PSO同遗传算法类似,是一种基于迭代的优化工具。系统...

空空如也

1 2 3 4 5 ... 20
收藏数 2,548,489
精华内容 1,019,395
关键字:

优化