我以前主要搞优化算法，但对于大多数数值最优化算法求的都是局部最优，当然也些
能求全局最优，就是凸集上的凸问题，简单说这类问题就一个局部最优解，当然也就是全
局最优了。多局部极值的问题的全局最优问题还没有根本最优解决，做的也是多找一些可
能是全局最优解的局部最优结，再从中选择最打的那个，认为是最优的......
   单这样的问题就很复杂了，实际中有会有更多的问题.....
   我有几个师兄师姐是做供应链的，供应链应该是比较长的，也就是说是由很多企业的上
下关系构成的。但我们研究的时候只是研究其中的一个环节比如两个，或者三个研究。找
到这个环节最优策略，但是每个环节都最优了，整个供应链不一定是最优的。如果把整个
供应作为研究整体，就是不现实的，太复杂了...
   就像我们以前听过的， 关于投资组合的问题，“让猴子去做”的可能都比我们计算半
天，费了好大劲的效果好.........
   似乎，种研究没有作用，我以前也认为没有多大的意义，但从问题的另一面想想:
局部最优的组合不一定是全局最优,但还是有可能是的. 最起码是最坏的策略. 如果用随机
策略的,说不定会达到最差的.
   从概率的意义上讲,我们这样做加大了达到最优的可能性, 这样想**还是有意义的! 

一、什么是局部最优与鞍点
初学深度学习，总是担心优化算法会困在极差的局部最优。本文介绍如何正确看待局部最优以及深度学习中的优化问题。



如上图，平面的高度就是损失函数。在图中似乎各处都分布着局部最优。梯度下降法或者某个算法可能困在一个局部最优中，而不会抵达全局最优。但是，问题的关键在于，低维特征（图示两维）让我们对局部最优产生误解。
事实上，如果你要创建一个神经网络，通常梯度为零的点并不是这个图中的局部最优点，实际上成本函数的零梯度点，通常是鞍点。



一个具有高维度空间的函数，如果梯度为0，那么在每个方向，它可能是凸函数，也可能是凹函数。如果你在2万维空间中，那么想要得到局部最优，所有的2万个方向都需要是这样，但发生的机率也许很小（2**（-20000）），也许是，你更有可能遇到有些方向的曲线会这样向上弯曲，另一些方向曲线向下弯，而不是所有的都向上弯曲，因此在高维度空间，你更可能碰到鞍点。
对于鞍点来讲，平稳段会减缓学习，平稳段是一块区域，其中导数长时间接近于0，如果你在此处，梯度会从曲面从从上向下下降，因为梯度等于或接近0，曲面很平坦，你得花上很长时间慢慢抵达平稳段的这个点，我们可以沿着这段长坡走，直到这里，然后走出平稳段。


二、如何判断模型陷入局部最优？
造成神经网络难以优化的一个重要（乃至主要）原因不是高维优化问题中有很多局部极值，而是存在大量鞍点。

  吴恩达视频中讲的，虽然没有理论的证明，局部最小值就是全局最小值，但是很多实际的经验告诉我们，最后，只能收敛到一个最小值，也就是说，很多现实实际问题是只有一个最小值的。但这个最小值通常是鞍点。



那么如何来区分鞍点和局部最优点呢？这时候就需要用到神经网络的loss surface的Hessian矩阵，通过计算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 分发饼干
文章目录
力扣 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;
}


好的解法
【代码随想录】大佬给出了另外一种贪心解法，可能这才是正确的贪心思想：局部最优是每次将大饼干分给胃口最大的，保证胃口大的孩子拿到大饼干；全局最优是最后尽可能多的孩子被满足。我的思路其实跟大佬倒过来了，我就是先用最小的饼干满足胃口最小的孩子。
关于局部最优与全局最优，大佬在【代码随想录】关于贪心算法，你该了解这些！解释得很清楚了，上一个传送门
【代码随想录】贪心算法：分发饼干

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

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

而且到达局部最优的可能性也不是很大。
单独看一个特征，到达梯度为0的情况有两种：



而100个特征全部到达右边这种情况的概率值约为$\frac{1}{2^{100}}$。
大部分情况都是某些到达极小值，而其它的在鞍部：