精华内容
下载资源
问答
  • 最优化方法:深度学习最优化方法

    千次阅读 2016-08-18 14:33:32
    深度学习最优化算法 ...深度学习框架中常见的最优化方法,如tensorflow中的最优化方法及相关参数如下: tf.train.Optimizer tf.train.GradientDescentOptimizer tf.train.AdadeltaOptimizer tf.tr...

    http://blog.csdn.net/pipisorry/article/details/52135832

    深度学习最优化算法

    深度学习框架中常见的最优化方法。

    tensorflow tf.keras.optimizers中的最优化方法及相关参数如下:

    Adadelta、Adagrad、Adam、Adamax、Ftrl、Nadam、Optimizer、RMSprop、SGD

    [https://www.tensorflow.org/api_docs/python/tf/keras/optimizers][tensorflow Optimizers]

    pytorch中的最优化方法及相关参数如下:

    SGD、Adagrad、Adadelta、RMSprop、Adam、AdamW、SparseAdam、Adamax、ASGD、LBFGS、Rprop

    [https://pytorch.org/docs/stable/optim.html#]

     

    基本算法

    SGD 随机梯度下降(Stochastic Gradient Descent)

            此处的SGD一般指mini-batch gradient descent。SGD就是每一次迭代计算mini-batch的梯度,然后对参数进行更新,是最常见的优化方法。即:

    θ^t+1 = θ^t + delta(θ^t)

    其中,η是学习率,g_t是梯度SGD完全依赖于当前batch的梯度。

    缺点:SGD 的缺点在于收敛速度慢,可能在鞍点处震荡,并且如何合理的选择学习率是 SGD 的一大难点。

    具体为1 选择合适的learning rate比较困难- 对所有的参数更新使用同样的learning rate。对于稀疏数据或者特征,有时我们可能想更新快一些(lz稀疏特征少,不平滑,影响更大),对于不经常出现的特征,对于常出现的特征更新慢一些,这时候SGD就不太能满足要求了。2 SGD容易收敛到局部最优,并且在某些情况下可能被困在鞍点【查阅论文发现,其实在合适的初始化和step size的情况下,鞍点的影响并没这么大】。

    [最优化方法:梯度下降(批梯度下降和随机梯度下降)]

    动量Momentum

          如果把要优化的目标函数看成山谷的话,可以把要优化的参数看成滚下山的石头,参数随机化为一个随机数可以看做在山谷的某个位置以0速度开始往下滚。目标函数的梯度可以看做给石头施加的力,由力学定律知:F=ma,所以梯度(施加的力)与石头下滚的加速度成正比。因而,梯度直接影响速度,速度的累加得到石头的位置,对这个物理过程进行建模,可以得到参数更新过程为:

    启发式算法:物体的动能 = 上一个时刻的动能 + 上一时刻的势能差(相对于单位质量),当前的速度取决于上一个时刻的速度和势能的改变量。由于有阻力和转换时的损失,所以两者都乘以一个系数。

    这样在更新参数时,除了考虑到梯度以外,还考虑了上一个时刻参数的历史变更幅度。如果参数上一次更新幅度较大,并且梯度还不小(当前还远未到达谷底),那么再更新时也应该很猛烈(不一定更猛烈,因为还有系数嘛,但是正因为有系数,不好定,所以不怎么自适应)。

    # Momentum update
    v = momentum * v - learning_rate * dx # integrate velocity
    x += v # integrate position

    代码中v指代速度,其计算过程中有一个超参数momentum,称为动量(momentum)。虽然名字为动量,其物理意义更接近于摩擦,其可以降低速度值,降低了系统的动能,防止石头在山谷的最底部不能停止情况的发生(除非momentum为0,不然还是停不下来的,可能通过NAG解决部分问题,但是怎么说momentum和nag都容易在谷底震荡停不下来,可以看下面的“鞍点”和“损失平面等高线”动图)。

    动量的取值范围通常为[0.5, 0.9, 0.95, 0.99],一种常见的做法是在迭代开始时将其设为0.5,在一定的迭代次数(epoch)后,将其值更新为0.99。

    在实践中,一般采用SGD+momentum的配置,相比普通的SGD方法,这种配置通常能极大地加快收敛速度。faster convergence and reduced oscillation振荡。

     

    NAG 加速梯度法(Nesterov accelerated gradient,NAG)

          还是以小球的例子来看,momentum方式有个缺点就是在临近最优点附近控制不住速度(梯度为0了,但是moment不为0,还是有速度,还会运动;lz并且快到最优点时,势能系数*势能还是>0的,还会运动)。我们希望小球很smart,它可以预判后面的"地形",要是后面地形还是很陡,那就继续坚定不移的大胆走下去;不然的话咱就收敛点。当然,小球自己也不知道真正要走到哪里,所以这里(θ−γv_{t−1})作为近似下一位置

    vt=γvt−1+η∇θJ(θ−γvt−1).  θ=θ−vt.

    Hinton的slides是这样给出的:

    momentum首先计算一个梯度(短的蓝色向量,势能),然后在加速更新梯度的方向进行一个大的跳跃(长的蓝色向量,动能);两个blue vectors分别理解为梯度和动能,两个向量和即为momentum方式的作用结果。

    nesterov项首先在之前加速的梯度方向进行一个大的跳跃(棕色向量,动能),计算梯度然后进行校正(绿色梯向量,势能)(反着来也没问题);靠左边的brown vector是动能,可以看出它那条blue vector是平行的,但是它预测了下一阶段的梯度是red vector,因此向量和就是green vector,即NAG方式的作用结果。

    -柚子皮-

     

    其实,momentum项和nesterov项都是为了使梯度更新更加灵活,对不同情况有针对性。但是,人工设置一些学习率总还是有些生硬(之前所讲的方法中所有参数在更新时均使用同一个learning rate),接下来介绍几种自适应学习率的方法。

    自适应学习率算法

    Adagrad

    Adagrad的每一个参数的每一次更新中都使用不同的learning rate,其实是对学习率进行了一个约束。即:

     (学习率为,当前梯度g_t在“所有历史梯度和”中的占比,占比大则更新快。这里很明显可以想到,应该只看最近几个历史梯度和更好,所以有了后面的adadelta)

    对迭代次数 t,基于每个参数之前计算的梯度值,将每个参数的学习率η按如下方式修正:

    其中G是一个对角阵,对角线上的元素是从一开始到 t 时刻目标函数对于参数梯度的平方和;\epsilon是一个平滑项,以避免分母为 0 的情况,它的数量级通常在1e^-8;一般超参数 η 就取 0.01。有趣的是,如果不开方的话,这个算法的表现会变得很糟。

    因为在其对角线上,含有过去目标函数对于参数 梯度的平方和,我们可以利用一个元素对元素的向量乘法,将我们的表达式向量化:

    [深度解读最流行的优化算法:梯度下降]

    特点:

    • 前期g_t较小的时候, regularizer较大,能够放大梯度;后期g_t较大的时候,regularizer较小,能够约束梯度;
    • 主要优势之一,是它不需要对每个学习率手工地调节。
    • 适合处理稀疏梯度。("It adapts the learning rate to the parameters, performing larger updates for infrequent and smaller updates for frequent parameters." 它对不同的参数调整学习率,具体而言,对低频出现的参数进行大的更新(lz因为低频参数少,累积和也小,分母小),对高频出现的参数进行小的更新。因此,他很适合于处理稀疏数据,对于稀疏数据上有着良好的表现。)(通常nlp模型的输入是非常稀疏的。对于包含几十万上百万词的词表,在训练的每个 Batch 中能出现的独立词数不超过几万个。也就是说,在每一轮梯度计算过程中,只有几万个词的 embedding 的梯度是非 0 的,其它 embedding 的梯度都是 0。)

    缺点:

    • 由公式可以看出,仍依赖于人工设置一个全局学习率
    • η设置过大的话,会使regularizer过于敏感,对梯度的调节太大
    • 主要劣势,是它在分母上的 Gt 项中积累了平方梯度和,中后期将会越来越大(每次加入的项总是一个正值),使gradient->0,使得训练提前结束——此时,这个算法已经不能从数据中学到额外的信息。RMSprop 和 Adadelta 都是为了解决 Adagrad 学习率急剧下降问题的。

    然而一般大多数自适应的learning rate都是有根据变化幅度而更改,并且具有逐渐收敛的特性。所以这种启发式方法仅是一种可行性方式,并不是唯一的,也绝不是最好的,把握其本质即可。

    Adadelta

    Adadelta是对Adagrad的扩展。

    计算上的简化,Adagrad会累加之前所有的梯度平方,而Adadelta只累加固定大小w的项,并且也不直接存储这些项,仅仅是近似计算对应的平均值。即:

    超参数设定值: 学习率 η 为 0.001。

    梯度值累积值按如下的方式递归地定义:它被定义为关于过去梯度值的衰减均值(decade average),当前时间 t 的梯度均值  是基于过去梯度均值  和当前梯度值平方  的加权平均,其中 p 是类似上述动量项的权值。此时Adadelta其实还是依赖于全局学习率。

    但后来的方案中,作者做了一定处理,经过近似牛顿迭代法之后:

    (其中,超参数一般设定为 0.9;E代表求期望。pytorch当前的adadelta基本就是这个版本的。)

    此时,可以看出Adadelta已经不用依赖于全局学习率了。

    因为分母表达式的形式与梯度值的方均根(root mean squared,RMS)形式类似,因而我们使用相应的简写来替换:

    特点:

    • 训练初中期,加速效果不错,很快
    • 训练后期,反复在局部最小值附近抖动
    • lz善于处理稀疏梯度(同adagrade)

    RMSprop

    RMSprop 是 Geoff Hinton 提出的一种自适应学习率方法,和Adadelta法几乎同时被发展出来,他们解决Adagrad激进的学习率缩减问题。可以算作Adadelta的一个特例,实际上, RMSprop和我们推导出的Adadelta法第一个更规则相同

    当\rho=0.5时,就变为了求梯度平方和的平均数。

    (注:Hinton建议设定 \rho 为0.9,对\eta  而言,0.001是一个较好的默认值。)

    如果再求根的话,就变成了RMS(均方根)。

    此时,这个RMS就可以作为学习率\eta的一个约束:

    特点:

    • 其实RMSprop依然依赖于全局学习率
    • RMSprop算是Adagrad的一种发展,和Adadelta的变体,效果趋于二者之间
    • 适合处理非平稳目标- 对于RNN效果很好

    万金油优化器:Adam 适应性动量估计法(Adaptive Moment Estimation)

            Adam 优化器可以说是目前使用最广泛、收敛速度较快且收敛过程较稳定的优化器。Adam(Adaptive Moment Estimation)本质上是带有动量项的RMSprop,它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。

    除了像 Adadelta 和 RMSprop 一样存储了过去梯度平方 vt 的指数衰减平均值 ,也像 momentum 一样保持了过去梯度 mt 的指数衰减平均值:

          

    m_t、n_t分别是对梯度的一阶矩估计和二阶矩估计,可以看作对期望E|g_t|,E|g_t^2|的估计。
          

    \hat{m_t},\hat{n_t}是对m_t、n_t的校正,这样可以近似为对期望的无偏估计。如果 mt 和 vt 被初始化为 0 向量,那它们就会向 0 偏置,所以做了偏差校正, 通过计算偏差校正后的 mt 和 vt 来抵消这些偏差。

    (后面的n超参可以不要)

    Note:这个格式是不是非常像牛顿迭代法?牛顿迭代法就是二阶收敛的,快。[最优化方法:牛顿迭代法和拟牛顿迭代法]

    可以看出,直接对梯度的矩估计对内存没有额外的要求,而且可以根据梯度进行动态调整,而对学习率形成一个动态约束,而且有明确的范围。

    超参数设定值:

    建议 u= 0.9,v = 0.999,ϵ = 10e−8。

    Adam 中二阶矩估计时,一般对于梯度稀疏问题如 NLP 与 CV,建议将此值设大,接近 1,因此通常默认设置为 0.999,而robert中设为 0.98。(lz太稀疏时,当前点可能更偏异常,占比小点好)[RoBERTa:高级丹药炼制记录]

    实践表明,Adam 比其他适应性学习方法效果要好。

    特点:

    • 动量的引入可以防止训练时产生震荡
    • 结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点
    • 对内存需求较小
    • 为不同的参数计算不同的自适应学习率
    • 也适用于大多非凸优化- 适用于大数据集和高维空间

    问题

           NLP 输入稀疏的特点与 Adam 使用动量计算梯度的特点相结合就引入了麻烦。每一轮更新参数时,只有极少数 embedding 的梯度是非 0 的,大部分 embedding 的梯度是 0 即上图公式中的 gt 是 0。但是,计算了动量之后,这些原本梯度都应该是 0 的 embedding 有了非零梯度 mt 用于梯度下降更新。想象一个极端的例子,“拉姆塞”这个词在一个 epoch 中只在第一个 batch 出现了,于是第一个 batch 计算了“拉姆塞”这个 embedding 的真实梯度 g0 用于更新参数,在以后的每个 batch 中虽然“拉姆塞”这个词没有出现过,Adam 都会计算它的动量梯度 mt,并用于更新“拉姆塞”这个 embedding,实际上方向与 g0 完全相同,只是每一轮做一次 β1 倍的衰减。这样的做法就相当于对这些出现次数较少的低频词的 embedding,每次梯度下降的等效学习率是非常大的,容易引起类似过拟合的问题。

    解决方法

            知道了问题的根节,解决方法就很简单了,每轮迭代只更新这个 batch 中出现过的词的 embedding 即可。TensorFlow 中可以使用 tf.contrib.opt.LazyAdamOptimizer,也可参考 https://www.zhihu.com/question/265357659/answer/580469438 的实现。

    [NLP 神经网络训练慎用 Adam 优化器]

    Adamax

    Adamax是Adam的一种变体,此方法对学习率的上限提供了一个更简单的范围。公式上的变化如下:

    可以看出,Adamax学习率的边界范围更简单。

    Nadam

    Nadam类似于带有Nesterov动量项的Adam。Much like Adam is essentially RMSprop with momentum, Nadam is Adam with Nesterov momentum.[https://www.tensorflow.org/api_docs/python/tf/keras/optimizers/Nadam]

    公式如下:

    可以看出,Nadam对学习率有了更强的约束,同时对梯度的更新也有更直接的影响。

    一般而言,在想使用带动量的RMSprop,或者Adam的地方,大多可以使用Nadam取得更好的效果。

    -柚子皮-

     

    不同最优化算法对比

    经验之谈

    • 对于稀疏数据,尽量使用学习率可自适应的优化方法,不用手动调节,而且最好采用默认值。
    • 如果在意更快的收敛,并且需要训练较深较复杂的网络时,推荐使用学习率自适应的优化方法。
    • SGD通常训练时间更长,但是在好的初始化和学习率调度方案的情况下,结果更可靠。
    • Adadelta,RMSprop,Adam是比较相近的算法,在相似的情况下表现差不多。
    • 在想使用带动量的RMSprop,或者Adam的地方,大多可以使用Nadam取得更好的效果。

    学习速率 alpha

    如果 alpha 设置得非常大,那么训练可能不会收敛,就直接发散了;
    如果 alpha 设置的比较小,虽然可以收敛,但是训练时间可能无法接受;
    如果 alpha 设置的稍微高一些,训练速度会很快,但是当接近最优点会发生震荡,甚至无法稳定。

                       不同学习速率的训练效果

    理想的学习速率是:刚开始设置较大,有很快的收敛速度,然后慢慢衰减,保证稳定到达最优点。所以,前面的很多算法都是学习速率自适应的。

    How to adjust learning rate

    [https://pytorch.org/docs/stable/optim.html#how-to-adjust-learning-rate]

    效果比较

    几种最优化算法在“鞍点”(optimization on saddle point)和“损失平面等高线”(optimization on loss surface contours)上的表现:

    上面两种情况都可以看出,Adagrad, Adadelta, RMSprop 几乎很快就找到了正确的方向并前进,收敛速度也相当快,而其它方法要么很慢(SGD),要么走了很多弯路才找到(Momentum和NAG)。由图可知自适应学习率方法即 Adagrad, Adadelta, RMSprop, Adam 在这种情景下会更合适而且收敛性更好。[(Image credit: Alec Radford)]

    [深度学习优化器算法详解:梯度更新规则+缺点+如何选择]

    from: http://blog.csdn.net/pipisorry/article/details/52135832

    ref: [http://sebastianruder.com/optimizing-gradient-descent/]

    [深度学习最全优化方法总结比较(SGD,Adagrad,Adadelta,Adam,Adamax,Nadam)]*

    [David Silver 增强学习补充知识——梯度下降法]*

    [深度解读最流行的优化算法:梯度下降]

    [从 SGD 到 Adam —— 深度学习优化算法概览(一)]

     

    展开全文
  • 最优化学习目录

    万次阅读 2021-05-31 01:14:59
    最优化学习目录 凸优化问题 常见凸优化问题的类型 无约束优化问题的最优性条件 强凸性 下降算法初步与线搜索方法 算法收敛性 最速下降法(steepest Descent) 牛顿法(Newton’s method) 拟牛顿...

    最优化学习目录


    从这里开始,我会开始学习我们的最优化
    我的主要参考书有Numerical optimization还有
    Convex Optimization,这本书是斯坦福的boyd公开课的教材,这里也给出链接:https://stanford.edu/~boyd/cvxbook/,也可以在上面找到相应的教材和幻灯片和练习。

    这两本是国内较为经典的讲述优化算法与理论的书籍,涵盖了2000年左右及以前的主要优化内容。放至当下,仍具有很高的参考价值,只是缺少了一些近20年来优化领域出现的成果。在国内出版书籍中,这些较新的成果可参考近期北京大学文再文教授团队编写的中文书籍《最优化:建模、算法与理论》。



    展开全文
  • 最优化算法之粒子群算法(PSO)

    万次阅读 多人点赞 2018-08-03 10:26:45
    粒子群优化算法的基本思想:是通过群体中个体之间的协作和信息共享来寻找优解.   PSO的优势:在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制...

    一、粒子群算法的概念

      粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的协作和信息共享来寻找最优解.
      PSO的优势:在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。

    二、粒子群算法分析

    1、基本思想

      粒子群算法通过设计一种无质量的粒子来模拟鸟群中的鸟,粒子仅具有两个属性:速度和位置,速度代表移动的快慢,位置代表移动的方向。每个粒子在搜索空间中单独的搜寻最优解,并将其记为当前个体极值,并将个体极值与整个粒子群里的其他粒子共享,找到最优的那个个体极值作为整个粒子群的当前全局最优解,粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。下面的动图很形象地展示了PSO算法的过程:
    这里写图片描述

    2、更新规则

      PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中,粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后,粒子通过下面的公式来更新自己的速度和位置。
    这里写图片描述
    公式(1)的第一部分称为【记忆项】,表示上次速度大小和方向的影响;公式(1)的第二部分称为【自身认知项】,是从当前点指向粒子自身最好点的一个矢量,表示粒子的动作来源于自己经验的部分;公式(1)的第三部分称为【群体认知项】,是一个从当前点指向种群最好点的矢量,反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础,形成了PSO的标准形式
    这里写图片描述
    公式(2)和 公式(3)被视为标准PSO算法

    3、PSO算法的流程和伪代码

    这里写图片描述

    4、PSO算法举例

    这里写图片描述
    这里写图片描述

    5、PSO算法的demo

    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <map>
    #include <algorithm>
    #include <random>
    #include <ctime>
    #include <Eigen/Dense>
    using namespace Eigen;
    using namespace std;
    
    const int dim = 1;//维数
    const int p_num = 10;//粒子数量
    const int iters = 100;//迭代次数
    const int inf = 999999;//极大值
    const double pi = 3.1415;
    //定义粒子的位置和速度的范围
    const double v_max = 4;
    const double v_min = -2;
    const double pos_max = 2;
    const double pos_min = -1;
    //定义位置向量和速度向量
    vector<double> pos;
    vector<double> spd;
    //定义粒子的历史最优位置和全局最优位置
    vector<double> p_best;
    double g_best;
    //使用eigen库定义函数值矩阵和位置矩阵
    Matrix<double, iters, p_num> f_test;
    Matrix<double, iters, p_num> pos_mat;
    
    //定义适应度函数
    double fun_test(double x)
    {
        double res = x * x + 1;
        return res;
    }
    
    //初始化粒子群的位置和速度
    void init()
    {
        //矩阵中所有元素初始化为极大值
        f_test.fill(inf);
        pos_mat.fill(inf);
        //生成范围随机数
        static std::mt19937 rng;
        static std::uniform_real_distribution<double> distribution1(-1, 2);
        static std::uniform_real_distribution<double> distribution2(-2, 4);
        for (int i = 0; i < p_num; ++i)
        {
            pos.push_back(distribution1(rng));
            spd.push_back(distribution2(rng));
        }
        vector<double> vec;
        for (int i = 0; i < p_num; ++i)
        {
            auto temp = fun_test(pos[i]);//计算函数值
            //初始化函数值矩阵和位置矩阵
            f_test(0, i) = temp;
            pos_mat(0, i) = pos[i];
            p_best.push_back(pos[i]);//初始化粒子的历史最优位置
        }
        std::ptrdiff_t minRow, minCol;
        f_test.row(0).minCoeff(&minRow, &minCol);//返回函数值矩阵第一行中极小值对应的位置
        g_best = pos_mat(minRow, minCol);//初始化全局最优位置
    }
    
    void PSO()
    {
        static std::mt19937 rng;
        static std::uniform_real_distribution<double> distribution(0, 1);
        for (int step = 1; step < iters; ++step)
        {
            for (int i = 0; i < p_num; ++i)
            {
                //更新速度向量和位置向量
                spd[i] = 0.5 * spd[i] + 2 * distribution(rng) * (p_best[i] - pos[i]) +
                    2 * distribution(rng) * (g_best - pos[i]);
                pos[i] = pos[i] + spd[i];
                //如果越界则取边界值
                if (spd[i] < -2 || spd[i] > 4)
                    spd[i] = 4;
                if (pos[i] < -1 || pos[i] > 2)
                    pos[i] = -1;
                //更新位置矩阵
                pos_mat(step, i) = pos[i];
            }
            //更新函数值矩阵
            for (int i = 0; i < p_num; ++i)
            {
                auto temp = fun_test(pos[i]);
                f_test(step, i) = temp;
            }
            for (int i = 0; i < p_num; ++i)
            {
                MatrixXd temp_test;
                temp_test = f_test.col(i);//取函数值矩阵的每一列
                std::ptrdiff_t minRow, minCol;
                temp_test.minCoeff(&minRow, &minCol);//获取每一列的极小值对应的位置
                p_best[i] = pos_mat(minRow, i);//获取每一列的极小值,即每个粒子的历史最优位置
            }
            g_best = *min_element(p_best.begin(), p_best.end());//获取全局最优位置
        }
        cout << fun_test(g_best);
    }
    
    int main()
    {
        init();
        PSO();
        system("pause");
        return 0;
    }

    参考:https://blog.csdn.net/myarrow/article/details/51507671
    https://blog.csdn.net/google19890102/article/details/30044945
    https://wenku.baidu.com/view/65c600b9294ac850ad02de80d4d8d15abe230048.html
    https://blog.csdn.net/darin1997/article/details/80675933

    展开全文
  • 最优化计算方法

    千次阅读 2018-09-17 14:42:44
    最优化计算方法 本文记录了博主在学习《最优化计算方法》时的总结,主要侧重于与深度学习相关的内容,更新于2018.09.17。 书目信息:《最优化计算方法》,黄正海等著,出版时间2015.02,科学出版社。 最优化...

    #最优化计算方法
    本文记录了博主在学习《最优化计算方法》时的总结,主要侧重于与深度学习相关的内容,更新于2018.09.17。
    书目信息:《最优化计算方法》,黄正海等著,出版时间2015.02,科学出版社。

    更多内容,欢迎加入星球讨论。
    在这里插入图片描述

    文章目录


    ##第1章 引论
    ###最优化问题概述
    最优化要解决的问题:在一定限制条件下使得所关心的指标达到最优。
    最优化问题的基本数学模型:

    KaTeX parse error: No such environment: split at position 8: \begin{̲s̲p̲l̲i̲t̲}̲ &\min \quad &f…

    其中xRnx\in \mathbb R^n称为决策向量,函数f:RnRf:\mathbb R^n \to \mathbb R称为目标函数,函数ci()(iI)c_i(\cdot)(i \in I)称为不等式约束函数,函数ci()(iE)c_i(\cdot)(i\in E)称为等式约束函数,不等式ci(x)0(iI)c_i(x)\geq0(i\in I)称为不等式约束,方程ci(x)=0(iE)c_i(x)=0(i\in E)称为等式约束,II称为不等式约束的指标集,EE称为等式约束的指标集。记:

    \begin{split}
    \mathscr F:=\left{ x\in \mathbb R^n \left\vert
    \begin{aligned}
    & c_i(x)\geq 0,\quad \forall i\in I={1,2,\cdot\cdot\cdot,p};\
    & c_i(x)=0,\quad \forall i\in E={p+1,p+2,\cdot\cdot\cdot,m}
    \end{aligned}
    \right. \right}
    \end{split}

    F\mathscr F为上述最优化问题的可行域,F\mathscr F中的每个点xx称为上述最优化问题的一个可行点。若F=\mathscr F=\varnothing,则称上述最优化问题不可行;否则,称问题是可行的。

    因此,上述最优化问题就是在可行域F\mathscr F中找到一个点xx,使其对应的f(x)f(x)的值不大于任何其他F\mathscr F中的点对应的目标函数值。

    **定义:**假设可行域F\mathscr F由上式给出:
    (i)若xFx^*\in \mathscr F,且对所有的xFx\in \mathscr F恒有f(x)f(x)f(x^*)\leq f(x),则称xx^*为上述最优化问题的一个全局解;
    (ii)若xFx^*\in \mathscr F,且对所有的xF/ xx\in \mathscr F/\ {x^*}恒有f(x)&lt;f(x)f(x^*)\lt f(x),则称xx^*为上述最优化问题的严格全局最优解;
    (iii)若xFx^*\in \mathscr F,且存在xx^*的某个邻域
    Nε(x)&quot;={xRnxx&lt;ε}ε\mathscr N_\varepsilon (x^*)&quot;=\left\{x\in \mathbb R^n \left\vert \Vert x-x^*\Vert \lt \varepsilon \right. \right\},\varepsilon 为正实数且\Vert\cdot\Vert表示某种范数
    使得对所有的xFNε(x)x\in \mathscr F \cap\mathscr N_\varepsilon(x^*)恒有f(x)f(x)f(x^*)\leq f(x),那么称xx^*为上述最优化问题的一个局部最优解。
    (iv)若xFx^*\in \mathscr F,且存在xx^*的某个邻域Nε(x)\mathscr N_\varepsilon(x^*),使得对所有的xFNε(x)/ xx\in\mathscr F \cap \mathscr N_\varepsilon(x^*)/\ {x^*}恒有f(x)&lt;f(x)f(x^*)\lt f(x),那么称xx^*为为上述最优化问题的一个严格局部最优解。

    **定义:**对于上述最优化问题,称其最优解xx^*对应的目标函数值f(x)f(x^*)为此优化问题的最优值。

    最优解不一定存在,存在也不一定唯一,但如果存在最优解,那么最优值一定唯一。最优化问题也常被写成:

    \begin{split}
    \min\left{f(x) \left\vert
    \begin{aligned}
    & c_i(x)\geq 0,\quad \forall i\in I={1,2,\cdot\cdot\cdot,p};\
    & c_i(x)=0,\quad \forall i\in E={p+1,p+2,\cdot\cdot\cdot,m}
    \end{aligned}
    \right. \right}
    \end{split}

    ###预备知识
    约定向量取列向量形式,即xRnx\in \mathbb R^n是指xx具有如下形式:

    \begin{split}
    x:=(x_1,x_2,\cdot\cdot\cdot)^T=
    \left(
    \begin{aligned}
    &x1\
    &x2\
    &\cdot\
    &\cdot\
    &\cdot\
    &x_n
    \end{aligned}
    \right)
    \end{split}

    对任意的x,yRnx,y\in \mathbb R^n,常用的内积x,y\langle x,y\rangle定义为:
    x,y:=i=1nxiyi=xTy\langle x,y\rangle:=\sum_{i=1}^nx_iy_i=x^Ty

    常用的向量范数:
    l1l_1-范数x1=i=1nxi\Vert x\Vert_1=\sum_{i=1}^n\vert x_i\vert
    l2l_2-范数x2=xTx=i=1nxi2\Vert x\Vert_2=\sqrt{x^Tx}=\sqrt{\sum_{i=1}^nx_i^2}
    ll_\infty-范数x=max{xii{1,2,,n}}\Vert x\Vert_\infty=\max \{\vert x_i\vert \vert i\in \{1,2,\cdot\cdot\cdot,n\}\}

    一般地,对于p[1,)p\in \left[1,\infty\right)lpl_p-范数定义为:
    xp=(i=1nxip)1/p\Vert x_p \Vert=\left( \sum_{i=1}^n\vert x_i\vert^p\right)^{1/p}

    各范数之间的关系有:
    xx2x1nx\Vert x \Vert _\infty \leq \Vert x\Vert _2 \leq \Vert x \Vert _1 \leq n\Vert x\Vert _\infty

    常用的矩阵范数
    假设ARn×nA\in \mathbb R^{n\times n}是对称正定矩阵,那么向量的椭球范数A\Vert\cdot\Vert_A定义如下:
    xA:=xTAx,xRn\Vert x \Vert _A:=\sqrt{x^TAx},\quad\forall x \in \mathbb R^n

    对于任意的A=(aij)n×nRn×nA=(a_{ij})_{n\times n}\in \mathbb R^{n\times n},常用的矩阵范数是Frobenius范数,定义为:
    AF:=i=1nj=1naij2=Tr(ATA)\Vert A\Vert _F:=\sqrt{\sum_{i=1}^n\sum_{j=1}^na_{ij}^2}=\sqrt{Tr(A^TA)}
    其中,Tr(ATA)Tr(A^TA)表示矩阵ATAA^TA的迹,即ATAA^TA的所有主对角线元素之和,也等于ATAA^TA的所有特征值之和。

    另一个常用的矩阵范数是由向量所诱导的矩阵范数,也称算子范数,定义为:
    A:=maxxRn/ {0}Axx,ARn×n\Vert A \Vert:=\max_{x\in \mathbb R^n/\ \{0\}}\frac{\Vert Ax\Vert}{\Vert x\Vert},\quad \forall A\in \mathbb R^{n\times n}
    其中,\Vert \cdot\Vert是某种向量范数。
    特别地,对于任意的ARn×nA\in \mathbb R ^{n\times n},有:

    • 由向量l1l_1-范数诱导的矩阵范数(列范数)为A1=max{i=1naijj{1,2,,n}}\Vert A \Vert _1 = \max \left\{ \sum_{i=1}^n\vert a_{ij}\vert \left\vert j\in \{1,2,\cdot\cdot\cdot,n\}\right. \right\}
    • 由向量ll_\infty-范数诱导的矩阵范数(行范数)为A=max{j=1naiji{1,2,,n}}\Vert A \Vert _\infty = \max \left\{ \sum_{j=1}^n\vert a_{ij}\vert \left\vert i\in \{1,2,\cdot\cdot\cdot,n\}\right. \right\}
    • 由向量l2l_2-范数诱导的矩阵范数(谱范数)为KaTeX parse error: Got function '\max' with no arguments as subscript at position 33: …= \sqrt{\lambda_̲\max(A^TA)},其中KaTeX parse error: Got function '\max' with no arguments as subscript at position 8: \lambda_̲\max(A^TA)表示矩阵ATAA^TA的最大特征值。

    矩阵范数满足相容性条件,常用的不等式有Cauchy-Schwarz不等式,广义Cauchy-Schwarz不等式,Young不等式,Holder不等式,Minkowski不等式。

    函数的可微性
    如果函数ff是二阶连续可微,那么函数ff在点xx处的二阶导数组成的矩阵称为Hesse阵。
    给定多变量向量值函数FF,如果其在xx处连续可微,那么函数FF在点xx处的一阶导数矩阵称为Jacobi矩阵。

    ###凸集、凸函数、凸规划
    凸集
    给定非空集合FRn\mathscr F \subseteq \mathbb R^n。如果对任意的x,yFx,y\in \mathscr F以及任意的实数α[0,1]\alpha \in [0,1]都有
    αx+(1+α)yF\alpha x+(1+\alpha)y\in \mathscr F
    那么,称F\mathscr FRn\mathbb R^n中的一个凸集。若凸集F\mathscr F为开集,则称为开凸集;若凸集F\mathscr F为闭集,则称为闭凸集。

    空集\varnothing通常被规定为凸集。

    凸集分离定理
    假设F1,F2Rn\mathscr F_1, \mathscr F_2 \subseteq \mathbb R^n为两个非空凸集。如果存在非零向量wRnw\in\mathbb R^n和实数tt,使得
    (i)对任意的xF1x\in\mathscr F_1yF2y\in \mathscr F_2,都有wTxtw^Tx\geq twTytw^Ty\leq t,则称超平面π:={xRnwTx=t}\pi := \{x\in \mathbb R^n \vert w^Tx=t\}分离集合F1\mathscr F_1F2\mathscr F_2
    (ii)对任意的xF1x\in\mathscr F_1yF2y\in \mathscr F_2,都有wTx&gt;tw^Tx\gt twTy&lt;tw^Ty\lt t,则称超平面π:={xRnwTx=t}\pi := \{x\in \mathbb R^n \vert w^Tx=t\}严格分离集合F1\mathscr F_1F2\mathscr F_2

    Farkas引理
    ARm×nA\in \mathbb R^{m\times n}bRnb\in \mathbb R^n,考虑不等式组
    Ax0,bTx&gt;0Ax\leq0,\quad b^Tx\gt 0
    和等式不等式组
    ATy=b,y0A^Ty=b,\quad y\geq0
    那么,上述两式有且仅一组有解。

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

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

    千次阅读 2018-07-25 10:55:56
    最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印) 前面我们已经讨论无约束问题的最优化方法,但实际碰到的问题常常是存在约束的。一般的约束最优化问题的数学模型为: minf(X)s....
  • 最优化理论算法

    千次阅读 多人点赞 2018-12-22 21:05:14
    1 预备知识 1.1 最优化问题 1.1.1最优化问题的数学模型一般形式为:  目标函数  s.t 约束条件 ...
  • 最优化理论·非线性最小二乘

    万次阅读 多人点赞 2017-02-24 10:20:53
    最优化理论·非线性最小二乘标签(空格分隔): 数学 非线性最小二乘问题是椭圆拟合中最易遇到的优化问题,本文主要对非线性二乘的基本分析做简单介绍 1. 什么是最小二乘问题目标函数能够写为m个函数平方和的优化...
  • 最优化:约束最优化之正则化

    千次阅读 2018-06-05 19:22:04
    感谢 点击打开链接附加L1范数或者L2范数的约束最优化中,正则化参数是如何选取的,即调优参数是如何选取的。
  • 最优化算法总结

    万次阅读 多人点赞 2018-08-22 21:53:05
    本文为SIGAI 2018/8/22最优化算法总结的直播笔记。 目录 总结图片: 1、精确求解(公式求解) 2 数值优化算法 2.1 梯度下降法 2.1.1 动量项 2.1.2 自适应学习率法  AdaGrad  RMSProp  AdaDelta  ...
  • 全部笔记的汇总贴:最优化学习目录 上溢和下溢 这里先介绍一个数值优化常出现的一个概念上溢和下溢 下溢(Underflow):当接近零的数被四舍五⼊为零时发生下溢。 上溢(Overflow):当⼤量级的数被近似为∞\infin∞...
  • 最优化理论

    千次阅读 2019-01-20 15:07:42
    最优化理论 机器学习简单来说,主要做的就是线性逼近,其根本就是优化问题: •先初始化一下权重参数 •然后利用优化方法来优化这个权重 •直到准确率不再是上升 •迭代停止 通常的形式:优化目标(目标函数) + ...
  • 最优化问题简介

    千次阅读 2016-02-23 15:17:12
     一年多学习以来,无论是前面学习压缩感知,还是这半年学习机器学习,一直离不开最优化,比如压缩感知的基追踪类重构算法,核心问题就是一个优化问题,而机器学习中的很多算法也需要最优化的知识,比如支持向量机...
  • - 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印) 在第四章中,我们解决了确定搜索步长的问题,现在解决确定搜索方向的问题。 1、最速下降法 基本思路 搜索方向总沿着f(X)f...
  • 最优化中的鞍点

    万次阅读 多人点赞 2016-11-06 23:13:03
    在学习最优化课程时,不时听到“鞍点”这个名词。老师很快提了这个词,但没有详细介绍鞍点的含义。 鞍点 (saddle point)的数学含义是: 目标函数在此点上的梯度(一阶导数)值为 0, 但从该点出发的一个方向是...
  • 常用最优化方法

    千次阅读 2018-05-18 14:14:15
    熟悉机器学习的童鞋都知道,优化方法是其中一个非常重要的话题,最常见的情形就是利用目标函数的导数通过多次迭代来求解无约束最优化问题。实现简单,coding方便,是训练模型的必备利器之一。 2. 几个数学概念 1)...
  • 把有约束最优化问题转化为无约束最优化问题之罚函数法 待补充
  • 1. 问题描述最优化问题的一般形式如下所示: 对于f:D⊆Rn→R1f:D\subseteq R^n \rightarrow R^1,求解 minx∈Ωf(x)s.t.{s(x)⩾0h(x)=0 \min_{x\in\Omega} f(x) \qquad s.t. \left\{ \begin{aligned} s(x)\...
  • 约束最优化方法之最优性条件

    万次阅读 多人点赞 2017-12-07 20:51:14
    一般性约束最优性条件前面几篇博客主要讲了无约束最优化问题的一些求解方法。从这一篇博客开始将开始讲有约束的最优化方法。首
  • 最优化理论与凸优化到底是干嘛的?

    万次阅读 多人点赞 2017-12-15 20:47:53
    1.2 全局最优化与局部最优化 Least-squares and linear programming(最小二乘与线性规划) 2.1 最小二乘 2.2 线性规划 最优化方法的一般结构 1.优化的定义 1.1 凸优化最优化问题目前在机器学习,数据挖掘等领域应用...
  • MATLAB 求解最优化问题

    万次阅读 多人点赞 2017-08-17 20:49:03
    MATLAB 求解最优化问题 MATLAB 优化工具箱解线性规划 模型1 minz=cXs.t.AX≤b \text{min} \quad z=cX \\ s.t.\quad AX\leq b 命令:x=linprog(c,A,b)x=\text{linprog}(c,A,b) 模型2 minz=cXs.t.AX≤...
  • Deep Learning 最优化方法之RMSProp

    千次阅读 2018-03-16 20:51:18
    原文地址:http://blog.csdn.net/bvl10101111/article/details/72616378本文是Deep Learning 之 ...整个优化系列文章列表:Deep Learning 之 最优化方法Deep Learning 最优化方法之SGDDeep Learning 最优化方法之Mom...
  • 最优化资源分配问题

    千次阅读 2018-10-28 12:33:26
    最优化资源分配问题 问题提出:现有三个发电厂A,B,C其生产成本和最大发电度数分别如下: 发电厂 生产成本T 最大发电度数 A P^2.2 1千万度 B 2p^1.8 1.5千万度 C 0.8p^2.0 1.8千万度 问:全年总发电量不少于3千万度,...
  • 机器学习的最优化问题

    千次阅读 2016-05-20 23:55:33
    机器学习的最优化问题机器学习中的大多数问题都可以转化为最优化问题。 过程为:把一些经典问题,转化为最优化数学模型,然后用最优化方法求解。机器学习和数据挖掘中,哪些属于最优化问题,见下表。 无约束的...
  • 机器学习中的最优化算法总结

    万次阅读 2018-08-23 14:05:37
    其它机器学习、深度学习算法的全面系统讲解可以阅读《机器学习-原理、算法与应用》,清华大学出版社,...对于几乎所有机器学习算法,无论是有监督学习、无监督学习,还是强化学习,最后一般都归结为求解最优化问题...
  • 最优化问题及其分类

    万次阅读 多人点赞 2016-02-24 22:24:52
    归纳而言,最优化问题分为函数优化问题和组合优化问题两大类,其中函数优化的对象是一定区间的连续变量,而组合优化的对象则是解空间中的离散状态。 一、函数优化问题函数优化问题通常可描述为:令S S为R n R^n上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,845,828
精华内容 738,331
关键字:

最优化