精华内容
下载资源
问答
  • 我以前主要搞优化算法,但对于大多数数值最优化算法求的都是局部最优,当然也些能求全局最优,就是凸集上的凸问题,简单说这类问题就一个局部最优解,当然也就是全局最优了。多局部极值的问题的全局最优问题还没有...

        我以前主要搞优化算法,但对于大多数数值最优化算法求的都是局部最优,当然也些

    能求全局最优,就是凸集上的凸问题,简单说这类问题就一个局部最优解,当然也就是全

    局最优了。多局部极值的问题的全局最优问题还没有根本最优解决,做的也是多找一些可

    能是全局最优解的局部最优结,再从中选择最打的那个,认为是最优的......
       单这样的问题就很复杂了,实际中有会有更多的问题.....
       我有几个师兄师姐是做供应链的,供应链应该是比较长的,也就是说是由很多企业的上

    下关系构成的。但我们研究的时候只是研究其中的一个环节比如两个,或者三个研究。找

    到这个环节最优策略,但是每个环节都最优了,整个供应链不一定是最优的。如果把整个

    供应作为研究整体,就是不现实的,太复杂了...
       就像我们以前听过的, 关于投资组合的问题,“让猴子去做”的可能都比我们计算半

    天,费了好大劲的效果好.........
       似乎,种研究没有作用,我以前也认为没有多大的意义,但从问题的另一面想想:
    局部最优的组合不一定是全局最优,但还是有可能是的. 最起码是最坏的策略. 如果用随机

    策略的,说不定会达到最差的.
       从概率的意义上讲,我们这样做加大了达到最优的可能性, 这样想**还是有意义的! 

    展开全文
  • 局部最优与鞍点问题

    2020-06-26 12:05:53
    一、什么是局部最优与鞍点 初学深度学习,总是担心优化算法会困在极差的局部最优。本文介绍如何正确看待局部最优以及深度学习中的优化问题。 如上图,平面的高度就是损失函数。在图中似乎各处都分布着局部最优。...

    一、什么是局部最优与鞍点

    初学深度学习,总是担心优化算法会困在极差的局部最优。本文介绍如何正确看待局部最优以及深度学习中的优化问题。
    在这里插入图片描述
    如上图,平面的高度就是损失函数。在图中似乎各处都分布着局部最优。梯度下降法或者某个算法可能困在一个局部最优中,而不会抵达全局最优。但是,问题的关键在于,低维特征(图示两维)让我们对局部最优产生误解。

    事实上,如果你要创建一个神经网络,通常梯度为零的点并不是这个图中的局部最优点,实际上成本函数的零梯度点,通常是鞍点。
    在这里插入图片描述
    一个具有高维度空间的函数,如果梯度为0,那么在每个方向,它可能是凸函数,也可能是凹函数。如果你在2万维空间中,那么想要得到局部最优,所有的2万个方向都需要是这样,但发生的机率也许很小(2**(-20000)),也许是,你更有可能遇到有些方向的曲线会这样向上弯曲,另一些方向曲线向下弯,而不是所有的都向上弯曲,因此在高维度空间,你更可能碰到鞍点。

    对于鞍点来讲,平稳段会减缓学习,平稳段是一块区域,其中导数长时间接近于0,如果你在此处,梯度会从曲面从从上向下下降,因为梯度等于或接近0,曲面很平坦,你得花上很长时间慢慢抵达平稳段的这个点,我们可以沿着这段长坡走,直到这里,然后走出平稳段。
    在这里插入图片描述

    二、如何判断模型陷入局部最优?

    造成神经网络难以优化的一个重要(乃至主要)原因不是高维优化问题中有很多局部极值,而是存在大量鞍点。
      吴恩达视频中讲的,虽然没有理论的证明,局部最小值就是全局最小值,但是很多实际的经验告诉我们,最后,只能收敛到一个最小值,也就是说,很多现实实际问题是只有一个最小值的。但这个最小值通常是鞍点。
    在这里插入图片描述
    那么如何来区分鞍点和局部最优点呢?这时候就需要用到神经网络的loss surfaceHessian矩阵,通过计算Hessian矩阵的特征值,我们就可以确定神经网络的解属于那种类型:

    • Hessian矩阵的特征值有正有负的时候,神经网络的一阶导数为零的点为鞍点
    • Hessian矩阵的特征值全部为非负的时候,神经网络的一阶导数为零的点为局部极小值点。

    我们可以知道近似情况下,神经网络的特征值分布图
    在这里插入图片描述
    其中 在这里插入图片描述是参数数目和数据量之比,越大代表相对数据越少;在这里插入图片描述 是loss的大小;在这里插入图片描述就是特征值。从这张图可以看出来:

    • Loss很大的时候,特征值分布有正有负,表明鞍点是困扰优化的主要原因
    • Loss很小的时候,逐渐鞍点消失,系统中主要是局部最小值点

    所以,我们在优化神经网络的过程中,主要克服的是鞍点问题。

    三、鞍点的解决办法

    1、鞍点的原理

    如果我们的模型真的收敛到鞍点上了,会很可怕吗?这就又回到了文章开头的那副马鞍状的图。显然,站在马鞍中央的时候,虽然很难翻过两边的山坡,但是往前或者往后随便走一步就能摔下马鞍!而在文章《batch size》中小夕讲过,我们默认使用的mini-batch梯度下降法本身就是有噪声的梯度估计,哪怕我们位于梯度为0的点,也经常在某个mini-batch下的估计把它估计偏了,导致往前或者往后挪了一步摔下马鞍,也就是mini-batch的梯度下降法使得模型很容易逃离特征空间中的鞍点。

    既然局部最优点很难踩到,鞍点也很容易逃离出去,那么为什么我们的模型看起来是收敛了呢?

    初学者可能会说 “会不会是学习率太大了,导致在“鞍点”附近震荡?” 首先,鞍点不像最优点那样容易震荡,而且哪怕你不断的减小学习率继续让模型收敛,大部分时候你这时计算output层或者后几层的梯度向量的长度时往往会发现它依然离0很遥远!(这句话是有实验支撑的,不过那篇论文我暂时没记起来,找到时贴出来)说明大部分时候收敛到的并不是鞍点。

    那会不会踩到的鞍点太多,虽然前面的鞍点都轻松逃逸了,但是最后恰好收敛到一个跳不下去的鞍点身上了?

    这倒是有可能,不排除有一些“马鞍面”特别平坦的鞍点区域,当模型陷入这种鞍点上时,由于计算出的梯度非常小,导致要连续迭代非常多次才可能慢慢移开这个鞍点,事实上大部分工程情况下,没等它移开的时候我们就已经默认为模型收敛、训练结束了,实际上人家模型还在努力逃离鞍点中呢。

    不过话说回来,虽然高维空间中的鞍点数量远远大于最优点,而且鞍点数量随着特征空间维度增高而指数级增长,但是鞍点的数量在整个空间中又是微不足道的:按前面的假设,假设在某个维度上随机一跳有10%的概率踩到导数为0的点,那么我们在101维的空间中的一步恰好踩到这个点上的概率为10^-100,也就是说在101维空间里随机乱跳的时候,有10^-100的可能性踩到鞍点身上。因此,即使有难以逃离的鞍点,即使我们的优化算法在努力向附近的鞍点靠拢,那么被我们正好踩到那些难以逃离的特殊鞍点的概率也是非常小的

    所以更令人信服的是,在高维空间里(深度学习问题上)真正可怕的不是局部最优也不是鞍点问题,而是一些特殊地形。比如大面积的平坦区域

    在平坦区域,虽然导数不为0但是却不大。虽然是在不断下降但是路程却非常长。对于优化算法来说,它需要走很多很多步才有可能走过这一片平坦区域。甚至在这段地形的二阶导数过于特殊的情况下,一阶优化算法走无穷多步也走不出去(设想一下,如果终点在一米外,但是你第一次走0.5米,后续每一步都是前一步的一半长度,那么你永远也走不到面前的一米终点处)。所以相比于栽到最优点和鞍点上,优化算法更有可能载到这种类似平坦区的地形中(如果这个平坦区又是“高原地带”,即loss值很高的地带,那么恭喜你悲剧了)。更糟糕的是,由于高维地形难以可视化,还有很多更复杂的未知地形会导致假收敛,一旦陷入到这些危险地形中,几乎是无解的

    2、鞍点的解决-理论

    如果你沿着中间部分往下走,你最终会摆脱它,但这可能需要很长时间。这只是两个维度上,但如果你有上十万甚至上百万维度呢?就像现在一般的研究中一样。在这种情况下,可能只有一条出路,其他的方向都不行,所以要找到逃逸的方向可能要花很长时间。当维度越来越大的时候,就有问题了。基于梯度下降的算法可能会有麻烦。
      只用一阶导数是难以区分最优点和鞍点的。但如果你有一个海森矩阵,这个问题将会消失,因为你会知道所有的方向,但你必须计算一个海森矩阵的特征向量。这两种情况都不好,因为它太复杂了也太慢。所以,梯度方法是个问题。

    我们想一下,最优点和鞍点的区别不就在于其在各个维度是否都是最低点嘛~只要某个一阶导数为0的点在某个维度上是最高点而不是最低点,那它就是鞍点。而区分最高点和最低点当然就是用二阶导数(斜率从负变正的过程当然就是“下凸”,即斜率的导数大于0,即二阶导数大于0。反之则为“上凹”,二阶导数小于0)。也就是说,若某个一阶导数为0的点在至少一个方向上的二阶导数小于0,那它就是鞍点啦。
      那么二阶导数大于0和小于0的概率各是多少呢?由于我们并没有先验知识,因此按照最大熵原理,我们认为二阶导数大于和小于0的概率均为0.5!

    那么对于一个有n个参数的机器学习/深度学习模型,“loss曲面”即位于n+1维空间(loss值为纵轴,n个参数为n个横轴)。在这个空间里,如果我们通过梯度下降法一路下滑终于滑到了一个各方向导数均为0的点,那么它为局部最优点的概率即0.5^ n,为鞍点的概率为1-0.5^n,显然,当模型参数稍微一多,即n稍微一大,就会发现这个点为鞍点的概率会远大于局部最优点!

    3、实际工程解决办法

    使用的mini-batch梯度下降法本身就是有噪声的梯度估计,哪怕我们位于梯度为0的点,也经常在某个mini-batch下的估计把它估计偏了,导致往前或者往后挪了一步摔下马鞍,也就是mini-batch的梯度下降法使得模型很容易逃离特征空间中的鞍点。

    更多的,我们可以从以下方面考虑:
      
      1)如何去设计一个尽量没有“平坦区”等危险地形的loss空间,即着手于loss函数的设计以及深度学习模型的设计;
      2)尽量让模型的初始化点远离空间中的危险地带,让最优化游戏开始于简单模式,即着手于模型参数的初始化策略;
      3)让最优化过程更智能一点,该加速冲时加速冲,该大胆跳跃时就大胆跳,该慢慢踱步时慢慢走,对危险地形有一定的判断力,如梯度截断策略;
      4)开外挂,本来下一步要走向死亡的,结果被外挂给拽回了安全区,如batch normalization策略等。

    4、鞍点的实际现象

    神经网络在学习过程中如果遇到鞍点,出现的直接现象是导致训练速度时间变长,这是因为神经网络是一个多维的神经网络,需要计算各个方向上的纬度,从而寻找出最优的路线,逃出鞍点。这时候通常是需要再重新多训练几次就可以了,或者使用优化算法进行解决。

    四、局部最优的解决办法

    局部最优需要注意的两个点分别是,

    • 局部最优出现时,神经网络的损失已经很小,在数据量足够的情况下,此时局部最优点接近全局最优。
    • 鞍点相比最优点更加稳定不易出现震荡,最优点容易出现震荡。

    解决办法:

    1 假如数据足够多,即使是局部最优,也是极好的解,而数据太大的时候,只有神经网络加随机梯度下降才能hold住
    2 网络足够深的时候,局部最优没那么局部,往往以鞍点存在,此时优化算法可以部分解决
    3 通过调整学习率等,可以部分避免局部最优尽管如此,非凸优化依然保证不了得到最优解。但是与其带来的好处相比就不值一提了,即使非最优解也常常吊打其他模型,所以大家还是用。

    展开全文
  • 文章目录力扣 455 分发饼干全部刷题学习记录原题目考查知识点自己的第一遍解法好的解法 全部刷题学习记录 【C++刷题学习笔记目录】 【C++百万并发网络通信-笔记目录】 原题目 题目地址:455. 分发饼干 假设你...

    力扣 455 分发饼干

    全部刷题与学习记录

    【C++刷题学习笔记目录】

    【C++百万并发网络通信-笔记目录】

    原题目

    题目地址:455. 分发饼干

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

    对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

    示例 1:

    输入: g = [1,2,3], s = [1,1]
    输出: 1
    解释: 
    你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
    虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
    所以你应该输出1。
    

    示例 2:

    输入: g = [1,2], s = [1,2,3]
    输出: 2
    解释: 
    你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2.
    

    考查知识点

    贪心


    自己的第一遍解法

    提炼一下题目信息

    孩子胃口g[i] {g1,g2,g3,...}
    饼干尺寸s[j] {s1,s2,s3,...}
    比较g1和s1,
    1)g1≤s1:满足一个孩子 ->比较g2和s2
    2)g1>s1:没有满足g1,继续用下一个饼干s2与g1比较
    

    这样进行比较其实也是一种贪心,每次用最小的饼干满足胃口最小的孩子

    但是这样有一个前提:g与s必须是排序之后的,这样才能保证每次比较都是最小的饼干与胃口最小的孩子进行比较。

    这道题表面看起来要用两个循环嵌套,其实一个循环就足够了,只需要不断移动两个数组的取数索引就可以。

    class Solution {
    private:
        int count = 0;//满足的孩子数量
        int idG = 0;
        int idS = 0;
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
            if (g.empty() or s.empty()) return 0;
    
            sort(g.begin(), g.end());
            sort(s.begin(), s.end());
            while (idG < g.size() and idS < s.size()) {
                if (g[idG] <= s[idS]) {//1)满足一个孩子,用下一块饼干与下一个孩子比较
                    count++;
                    idG++;
                    idS++;
                }
                else//2)没有满足,用下一块饼干再来看看能否满足当前这个孩子
                    idS++;
            }
    
            return count;
        }
    };
    
    int main() {
        Solution so;
        vector<int> g = {10,9,8,7};//如果Solution内部不排序,这样的输入会输出0,正确答案是2
        vector<int> s = {5,6,7,8};
        cout << so.findContentChildren(g, s) << endl;
    }
    

    好的解法

    【代码随想录】大佬给出了另外一种贪心解法,可能这才是正确的贪心思想:局部最优是每次将大饼干分给胃口最大的,保证胃口大的孩子拿到大饼干;全局最优是最后尽可能多的孩子被满足。我的思路其实跟大佬倒过来了,我就是先用最小的饼干满足胃口最小的孩子。

    关于局部最优与全局最优,大佬在【代码随想录】关于贪心算法,你该了解这些!解释得很清楚了,上一个传送门

    【代码随想录】贪心算法:分发饼干

    展开全文
  • 关于局部最优

    2019-12-12 16:09:17
    在开始学习梯度下降的时候,总会有这样的疑问:梯度下降只能到达局部最优,万一到达了一个较大的局部最优,错过了较小的全局最优或是另外一个更小的局部最优,那么是不是算法是失败呢? 其实在机器学习的大数据背景...

    在开始学习梯度下降的时候,总会有这样的疑问:梯度下降只能到达局部最优,万一到达了一个较大的局部最优,错过了较小的全局最优或是另外一个更小的局部最优,那么是不是算法是失败呢?

    在这里插入图片描述

    其实在机器学习的大数据背景下,随机到达的局部最优点与全局最优点虽然有差距,但是也足够优秀


    而且到达局部最优的可能性也不是很大。

    单独看一个特征,到达梯度为0的情况有两种:
    在这里插入图片描述
    而100个特征全部到达右边这种情况的概率值约为12100\frac{1}{2^{100}}

    大部分情况都是某些到达极小值,而其它的在鞍部:

    在这里插入图片描述

    展开全文
  • GWO算法有效性,对13个全局优化问题进行实验,分别GWO、GWO-EPD(改进的苍狼优化算法)、PSO、EA等算法进行了对比测试,从实验结果来看,MAR-GWO算法寻优成功率相对较高、收敛速度快,不易陷入局部最优,...
  • Matlab全局优化与局部优化

    千次阅读 2018-04-01 10:15:51
    优化问题一般分为局部最优全局最优局部最优,就是在函数值空间的一个有限区域内寻找最小值;而全局最优,是在函数值空间整个区域寻找最小值问题。函数局部最小点是那种它的函数值小于或等于附近点的点。但是有...
  • 文章目录局部变量、全局变量、局部函数、全局函数、static、extern可见域和作用域变量的声明定义:1、全局变量与局部变量全局变量:局部变量:2、全局函数内部函数链接过程解释extern建议最优用法1.一个c文件...
  • 随机梯度下降可以缓解这个问题,但还存在陷入局部最优、选择学习率等诸多问题。因此,优化问题还是很困难的,需要研究人员和从业人员多加关注。转载自:机器之心参与:李诗萌、张倩作者:Tivadar Danka关于深度学习...
  • 提出了一种基于Memetic算法的编码曝光最优码字序列...研究结果表明,相比其他方法,所提算法兼顾了全局最优与局部最优的求解,得到的最优码字序列具有更优性能指标,算法执行效率高,复原图像的主客观评价质量更好。
  • 此算法充分考虑粒子群算法复形法的特性,将复形法的局部搜索粒子群算法的全局搜索结合起来,以提高算法搜索能力,克服粒子群算法复形法易陷局部极值的不足。通过性能测试效果良好,同时算法简便、可行、高效。...
  • 2.静态测试 静态测试是通过阅读程序来查找软件的差错问题的一种方法其检查的重点为代码设计的要求是否一致代码的逻辑表示是否正确完整代码的结构是否合理是否有未定义或用错的局部变量或全局变量等 3....
  • 贪心算法-射击气球

    2021-03-08 22:36:16
    使用贪心策略要注意局部最优与全局最优的关系,选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题: 1、该问题是否适合使用贪心策略求解,也就是该问题是否具有贪心选择性质 。 2...
  • 贪心算法分解.ppt

    2020-08-08 02:16:02
    贪心算法 贪心方法的基本思想 贪心是一种解题策略,也是一种解题思想 使用贪心方法需要注意局部最优与全局最优的 关系,选择当前状态的局部最优并不一定能推 导出问题的全局最优 利用贪心策略解题,需要解决两个问题: ...
  • 【CSDN】贪心策略的特点与应用 基本问题使用贪心算法应注意 局部最优与全局最优的关系。这是贪心算法能够应用的一个十分重要的基础。2个基本问题应用贪心算法解决问题时,需注意两个问题: 该题是否适
  • 利用局部最优与全局最优的想法维护两个二维数组,来实现动态规划。 l[i][j]是在到达第i天,最多可以进行j次交易的局部最优利益。注意这里是最多进行j次交易,即l[2][2]为到达第二天,最多进行两次交易的局部最优利益...
  • 贪心法—背包问题

    2018-05-27 00:28:21
    使用贪心方法需要注意局部最优与全局最优的关系,选择当前状态的局部最优并不一定能推导出问题的全局最优 利用贪心策略解题,需要解决两个问题: 该题是否适合于用贪心策略求解 如何选择贪心标准,以得到问题的...
  • 贪心算法简述

    2020-07-09 20:37:02
    使用贪心策略要注意局部最优与全局最优的关系,选择当前的局部最优并不一定能推导出问题的全局最优。 2.贪心算法的思想 贪心算法的一般框架: 贪心算法一般按如下步骤进行: ①建立数学模型来描述问题 。 ②把求解...
  • 针对现有Web服务集成方法在动态性、...为实现集成服务整体的QoS目标,以一个通用的Web服务QoS度量模型为基础,将局部最优与全局最优的思想相结合,提出一种基于QoS的Web服务集成路径选择算法,通过实验验证了其有效性。
  • 针对分布式传感器网络检测系统中的最优决策融合问题,引入了奈曼-皮尔逊判定准则,在此基础上推导出由虚警率条件约束的最大检测准确概率的局部判决阀值和全局最优判决阀值的求解方法。设计了基于该准则的最优检测阀值...
  • LeetCode53_Maximum Subarray

    2019-02-24 11:58:27
    此题本身实现比较简单,但对复杂度的要求和分治的要求不太会实现,这其实是一个典型的动态规划问题,局部最优与全局最优的经典解法可以实现一遍循环即得结果。 题目如下:   Given an integer array nums, find...
  • 模型学习的过程实质上就是一个寻找最优参数的过程,例如BP算法试图通过最速下降来寻找使累积经验误差最下的权值阈值,在谈到最优时。一般会提到局部极小和全局最小。 1.局部极小解:参数空间中某个点,其邻域点的...
  • 文章目录第二章 机器学习基础2.1 基本概念2.1.1 大话理解机器学习本质2.1.2 什么是神经网络2.1.3 各种常见算法图示2.1.4 计算图的导数计算2.1.5 理解局部最优与全局最优2.1.5 大数据与深度学习之间的关系2.2 机器...
  • 机器学习基础

    2021-01-21 15:27:35
    文章目录第二章 机器学习基础2.1 基本概念2.1.1 大话理解机器学习本质2.1.2 什么是神经网络2.1.3 各种常见算法图示2.1.4 计算图的导数计算2.1.5 理解局部最优与全局最优2.1.5 大数据与深度学习之间的关系2.2 机器...
  • 提出的选择算子仅父代的大小顺序有关,既可避免原算法对 适应值必须为正的限制,又可避免算法过早收敛到局部解。证明了新算法的全局收敛性,并对新的选择 算子进行了性能分析。将改进的遗传算法引入受约束...
  • review2:机器学习基础

    2019-07-22 21:22:32
    review2:机器学习基础第二章 机器学习基础2.1 大话理解...2.7 理解局部最优与全局最优2.8 分类算法2.8.1 常用分类算法的优缺点?2.8.2 分类算法的评估方法?2.8.3 正确率能很好的评估分类算法吗?2.8.4 什么样的分...
  • 移动机器人技术是近年来的研究热点,在...本文重点分别从全局路径规划和局部路径规划角度对移动机器人路径规划的研究方法进行了分析总结,同时也分析了移动机器人路径规划算法的未来发展趋势。自主移动机器人属于...
  • 第二章_机器学习基础

    千次阅读 2019-12-08 15:47:06
    文章目录第二章 机器学习基础2.1 各种...2.7 理解局部最优与全局最优2.8 分类算法2.8.1 常用分类算法的优缺点?2.8.2 正确率能很好的评估分类算法吗?2.8.3 分类算法的评估方法?2.8.4 什么样的分类器是最好的?2....
  • 深度学习 - 第二章 - 机器学习基础

    千次阅读 2019-01-04 11:29:37
    深度学习 - 第二章 - 机器学习基础第二章 机器学习基础2.1 各种常见...2.7 理解局部最优与全局最优2.8 分类算法2.8.1 常用分类算法的优缺点?2.8.2 正确率能很好的评估分类算法吗?2.8.3 分类算法的评估方法?2.8.4...
  • 利用该算法其他算法对IEEE5节点算例进行分析比较,结果表明改进的混沌微粒群优化算法可较好处理最优潮流约束条件,有效提高了PSO算法的全局收敛能力和计算精度。在处理最优潮流问题上具有一定的有效性和优越性。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 612
精华内容 244
关键字:

局部最优与全局最优