机器学习之优化算法
机器学习优化算法（1）什么是优化算法？（2）优化算法作用是什么？（3）优化算法有哪些？
1.什么是优化算法？优化算法就是那个使策略（损失函数）最小化的方法，或者说通过迭代的方法（优化算法）计算损失函数的最优解。
2.优化算法作用是什么？简单说优化算法作用就是，用来调节模型参数，进而使得损失函数最小化，（此时的模型参数就是那个最优解）目前优化算法求解损失函数的最优解一般都是迭代的方式。（可以看一下下面两个图不同的优化算法，在寻找最优解的过程，还有鞍点问题）
如果是凸优化问题，如果数据量特别大，那么计算梯度非常耗时，因此会选择使用迭代的方法求解，迭代每一步计算量小，且比较容易实现。
对于非凸问题，只能通过迭代的方法求解，每次迭代目标函数值不断变小，不断逼近最优解。
因此优化问题的重点是使用何种迭代方法进行迭代，即求迭代公式。
3.优化算法有哪些？深度学习中常用的优化算法是梯度下降，着重介绍，一般来说，梯度下降算法有三种变种，它们之间的区别是使用多少数据来计算目标函数的梯度。取决于数据的大小，我们在参数更新的精度和花费的时间进行平衡。
Batchgradientdescent
批量梯度下降是一种对参数的update进行累积，然后批量更新的一种方式。这种算法很慢，并且对于大的数据集并不适用；并且使用这种算法，我们无法在线更新参数。
Stochasticgradientdescent
随机梯度下降是一种对参数随着样本训练，一个一个的及时update的方式。这种方法迅速并且能够在线使用；但是它频繁的更新参数会使得目标函数波动很大。
Mini-batchgradientdescent
吸取了BGD和SGD的优点，每次选择一小部分样本进行训练。
尽管Mini-batchgradientdescent算法不错，它也不能保证收敛到好的值，并且带来了新的挑战：
很难选择合适的学习率。过小的学习率会使得收敛非常缓慢；多大的学习率会发生震荡甚至发散。
学习率相关的参数只能提前设定，无法使用数据集的特性
所有的参数更新都使用相同的学习率
如何跳出局部最小
下面是梯度下降的一系列变种：
（1）SGD随机梯度下降，下面提到的深度学习的优化算法都是基于此展开（2）带动量（momentum）的SGD虽然随机梯度下降仍然是非常受欢迎的优化方法，但其学习过程有时会很慢。动量方法旨在加速学习，特别是处理高曲率、小但一致的梯度，或是带噪声的梯度。动量算法积累了之前梯度指数级衰减的移动平均，并且继续沿该方向移动。SGD方法的一个缺点是，其更新方向完全依赖于当前的batch，因而其更新十分不稳定。解决这一问题的一个简单的做法便是引入momentum。momentum即动量，它模拟的是物体运动时的惯性，即更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。这样一来，可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力。
带动量（Momentum）的SGD特点：
下降初期时，使用上一次参数更新，下降方向一致，乘上较大的能够进行很好的加速
下降中后期时，在局部最小值来回震荡的时候，，使得更新幅度增大，跳出陷阱
在梯度改变方向的时候，能够减少更新总而言之，momentum项能够在相关方向加速SGD，抑制振荡，从而加快收敛
（3）Nesterov动量SGD首先，按照原来的更新方向更新一步（棕色线），然后在该位置计算梯度值（红色线），然后用这个梯度值修正最终的更新方向（绿色线）。上图中描述了两步的更新示意图，其中蓝色线是标准momentum更新路径。其实，momentum项和nesterov项都是为了使梯度更新更加灵活，对不同情况有针对性。
但是，人工设置一些学习率总还是有些生硬，接下来介绍几种自适应学习率的方法：
（4）AdaGrad(AdaGrad)算法：在参数空间中更为平缓的倾斜方向会取得更大的进步说明一：大多数方法对于所有参数都使用了同一个更新速率。但是同一个更新速率不一定适合所有参数，比如有的参数可能已经到了仅需要微调的阶段，但又有些参数由于对应样本少等原因，还需要较大幅度的调动。Adagrad就是针对这一问题提出的，自适应地为各个参数分配不同学习率的算法。
说明二：AdaGrad是第一个自适应算法，通过每次除以根号下之前所有梯度值的平方和，从而使得步长单调递减。同时因为cache的变化与每个维度上的值有关，所以此方法可以解决各个维度梯度值相差较大的问题。对于每个参数，随着其更新的总距离增多，其学习速率也随之变慢。
特点：
前期较小的时候，regularizer较大，能够放大梯度后期较大的时候，regularizer较小，能够约束梯度适合处理稀疏梯度缺点：
由算法8.4可以看出，仍依赖于人工设置一个全局学习率设置过大的话，会使regularizer过于敏感，对梯度的调节太大中后期，分母上梯度平方的累加将会越来越大，使，使得训练提前结束（5）RMSProp算法简单的说，RMSProp对于AdaGrad的改进在于cache的更新方法。不同于不断的累加梯度的平方，RMSProp中引入了泄露机制，使得cache每次都损失一部分，从而使得步长不再是单调递减了。RMSprop可以算作Adadelta的一个特例
特点：
其实RMSprop依然依赖于全局学习率RMSprop算是Adagrad的一种发展，和Adadelta的变体，效果趋于二者之间适合处理非平稳目标-对于RNN效果很好RMSProp算法修改AdaGrad以在非凸设定下效果更好，改变梯度累积为指数加权的移动平均。AdaGrad旨在应用于凸问题时快速收敛。AdaGrad根据平方梯度的整个历史收缩学习率，可能使得学习率在达到这样的凸结构前就变得太小了。
RMSprop使用指数衰减平均来丢弃遥远过去的历史，使其在找到凸结构后快速收敛，就像一个初始化于该碗装结构的AdaGrad算法实例。相比于AdaGrad，使用移动平均引入了一个新的超参数ρ，用来控制移动平均的长度范围。
（6）Nesterov动量RMSProp（7）Adam算法Adam被看作结合RMSProp和具有一些重要区别的动量的变种。首先，Adam中动量直接并入梯度一阶矩（指数加权）的估计。其次，Adam包括偏置修正，修泽和那个从原点初始化的一阶矩（动量项）和（非中心的）二阶矩的估计。RMSProp也采用了（非中心的）二阶矩估计，然而缺失了修正因子。因此，RMSProp二阶矩估计可能在训练初期有很高的偏置。Adam通常被认为对超参数的选择相当鲁棒，尽管学习率有时需要遵从建议的默认参数0.001。（本人比较喜欢用adam，总之适合自己才是最好的）Adam(AdaptiveMomentEstimation)本质上是带有动量项的RMSprop，它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。
特点：
结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点对内存需求较小为不同的参数计算不同的自适应学习率也适用于大多非凸优化-适用于大数据集和高维空间看一下大神是如何总结的：
如果你的数据特征是稀疏的，那么你最好使用自适应学习速率SGD优化方法(Adagrad、Adadelta、RMSprop与Adam)，因为你不需要在迭代过程中对学习速率进行人工调整。RMSprop是Adagrad的一种扩展，与Adadelta类似，但是改进版的Adadelta使用RMS去自动更新学习速率，并且不需要设置初始学习速率。而Adam是在RMSprop基础上使用动量与偏差修正。RMSprop、Adadelta与Adam在类似的情形下的表现差不多。Kingma指出收益于偏差修正，Adam略优于RMSprop，因为其在接近收敛时梯度变得更加稀疏。因此，Adam可能是目前最好的SGD优化方法。有趣的是，最近很多论文都是使用原始的SGD梯度下降算法，并且使用简单的学习速率退火调整（无动量项）。现有的已经表明：SGD能够收敛于最小值点，但是相对于其他的SGD，它可能花费的时间更长，并且依赖于鲁棒的初始值以及学习速率退火调整策略，并且容易陷入局部极小值点，甚至鞍点。因此，如果你在意收敛速度或者训练一个深度或者复杂的网络，你应该选择一个自适应学习速率的SGD优化方法。个人总结：适合自己的才是最好的！
除梯度下降外的一些优化方法：（感兴趣的自行研究吧，牛顿法、拟牛顿法、最小二乘、启发式优化方法（模拟退火方法、遗传算法、蚁群算法以及粒子群算法等））
（8）二阶近似方法：与一阶方法相比，二阶方法使用二阶导数改进了优化。最广泛使用的二阶方法是牛顿法。
牛顿法牛顿法是二阶收敛的，梯度下降是一阶收敛的，所以牛顿法更快，如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）。根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。优点：二阶收敛，收敛速度快；缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
共轭梯度方法共轭梯度法是介于梯度下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了梯度降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：注：绿色为梯度下降法，红色代表共轭梯度法
好了看了这么多，还是直接看大神的吧：http://ruder.io/optimizing-gradient-descent/index.html#gradientdescentvariants
人工智能：智能优化算法
**
人工智能：智能优化算法优化问题是指在满足一定条件下，在众多方案或参数值中寻找最优方案或参数值，以使得某个或多个功能指标达到最优，或使系统的某些性能指标达到最大值或最小值。优化问题广泛地存在于信号处理、图像处理、生产调度、任务分配、模式识别、自动控制和机械设计等众多领域。优化方法是一种以数学为基础，用于求解各种优化问题的应用技术。各种优化方法在上述领域得到了广泛应用，并且已经产生了巨大的经济效益和社会效益。实践证明，通过优化方法，能够提高系统效率，降低能耗，合理地利用资源，并且随着处理对象规模的增加，这种效果也会更加明显。在电子、通信、计算机、自动化、机器人、经济学和管理学等众多学科中，不断地出现了许多复杂的组合优化问题。面对这些大型的优化问题，传统的优化方法（如牛顿法、单纯形法等）需要遍历整个搜索空间，无法在短时间内完成搜索，且容易产生搜索的“组合爆炸”。例如，许多工程优化问题，往往需要在复杂而庞大的搜索空间中寻找最优解或者准最优解。鉴于实际工程问题的复杂性、非线性、约束性以及建模困难等诸多特点，寻求高效的优化算法已成为相关学科的主要研究内容之一。受到人类智能、生物群体社会性或自然现象规律的启发，人们发明了很多智能优化算法来解决上述复杂优化问题，主要包括：模仿自然界生物进化机制的遗传算法；通过群体内个体间的合作与竞争来优化搜索的差分进化算法；模拟生物免疫系统学习和认知功能的免疫算法；模拟蚂蚁集体寻径行为的蚁群算法；模拟鸟群和鱼群群体行为的粒子群算法；源于固体物质退火过程的模拟退火算法；模拟人类智力记忆过程的禁忌搜索算法；模拟动物神经网络行为特征的神经网络算法；等等。这些算法有个共同点，即都是通过模拟或揭示某些自然界的现象和过程或生物群体的智能行为而得到发展；在优化领域称它们为智能优化算法，它们具有简单、通用、便于并行处理等特点。**
1进化类算法****自然界的生物体在遗传、选择和变异等一系列作用下，优胜劣汰，不断地由低级向高级进化和发展，人们将这种“适者生存”的进化规律的实质加以模式化而构成一种优化算法，即进化计算。进化计算是一系列的搜索技术，包括遗传算法、进化规划、进化策略等，它们在函数优化、模式识别、机器学习、神经网络训练、智能控制等众多领域都有着广泛的应用。其中，遗传算法是进化计算中具有普遍影响的模拟进化优化算法。为了求解切比雪夫多项式问题，RainerStorn和KennethPrice根据这种进化思想提出了差分进化算法。它是一种采用实数编码、在连续空间中进行随机搜索、基于群体迭代的新兴进化算法，具有结构简单、性能高效的特点。而免疫算法是模仿生物免疫机制，结合基因的进化机理，人工地构造出的一种新型智能搜索算法。该算法具有一般免疫系统的特征，它采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解，相当于属于进化算法的变种算法。
1.1遗传算法遗传算法（GeneticAlgorithm，GA）是模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化搜索算法。它最早由美国的J.H.Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究；70年代，K.A.DeJong基于遗传算法的思想，在计算机上进行了大量的纯数值函数优化计算试验；80年代，遗传算法由D.J.Goldberg在一系列研究工作的基础上归纳总结而成。遗传算法是通过模仿自然界生物进化机制而发展起来的随机全局搜索和优化方法。它借鉴了达尔文的进化论和孟德尔的遗传学说，本质上是一种并行、高效、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作：使用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境。
1.2差分进化算法差分进化算法（DifferentialEvolution，DE）是一种新兴的进化计算技术。它由Storn等人于1995年提出，其最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。差分进化算法是基于群体智能理论的优化算法，是通过群体内个体间的合作与竞争产生的智能优化搜索。但相比于进化计算，差分进化算法保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和“一对一”的竞争生存策略，降低了进化计算的复杂性。同时，差分进化算法特有的记忆能力使它可以动态跟踪当前的搜索情况，以调整其搜索策略，它具有较强的全局收敛能力和稳健性，且不需要借助问题的特征信息，适用于求解一些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。
1.3免疫算法最早的免疫系统模型是由Jerne于1973年提出的，他基于Burnet的克隆选择学说，开创了独特型网络理论，给出了免疫系统的数学框架，并采用微分方程建模来仿真淋巴细胞的动态变化。Farmal等人于1986年基于免疫网络学说理论构造出免疫系统的动态模型，展示了免疫系统与其他人工智能方法相结合的可能性，开创了免疫系统研究的先河。免疫算法（ImmuneAlgorithm，IA）是模仿生物免疫机制，结合基因的进化机理，人工构造出的一种新型智能搜索算法。免疫算法具有一般免疫系统的特征，采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解。相比较于其他算法，免疫算法利用自身产生多样性和维持机制，保证了种群的多样性，克服了一般寻优过程中（特别是多峰值的寻优过程中）不可避免的“早熟”问题，可求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。**
2群智能算法**群智能指的是“无智能的主体通过合作表现出智能行为的特性”，是一种基于生物群体行为规律的计算技术。它受社会昆虫（如蚂蚁、蜜蜂）和群居脊椎动物（如鸟群、鱼群和兽群）的启发，用来解决分布式问题。它在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了一种新的思路。群智能方法易于实现，其算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需要目标函数的输出值，而不需要其梯度信息。已完成的群智能理论和应用方法研究证明：群智能方法是一种能够有效解决大多数全局优化问题的新方法。近年来群智能理论研究领域出现众多算法，如：蚁群算法、粒子群算法、鱼群算法、蜂群算法、猫群算法、狼群算法、鸡群算法、鸟群算、文化算法、杂草算法、蝙蝠算法、布谷鸟算法、果蝇算法、蛙跳算法、细菌觅食算法、萤火虫算法和烟花算法，等等。其中蚁群算法和粒子群算法是最主要的两种群智能算法。群智能理论研究领域有两种主要的算法：蚁群算法和粒子群算法。前者是对蚂蚁群体食物采集过程的模拟，已成功应用于许多离散优化问题；后者起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化算法。
2.1蚁群算法蚁群算法（AntColonyOptimization，ACO）是由意大利学者M.Dorigo、V.Maniezzo和A.Colorni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法，是群智能理论研究领域的一种主要算法。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径，并且能随环境的变化，自适应地搜索新的路径。其根本原因是蚂蚁在寻找食物时，能在其走过的路径上释放一种特殊的分泌物——信息素。随着时间的推移，该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来的蚂蚁选择该路径的概率也就越高，从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通信等特征，易于与其他优化算法相结合。它通过简单个体之间的协作，表现出了求解复杂问题的能力，已经广泛应用于优化问题的求解。
2.2粒子群算法粒子群算法（ParticleSwarmOptimization，PSO）是Kennedy和Eberhart受人工生命研究结果的启发，通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法；1995年IEEE国际神经网络学术会议上发表了题为“ParticleSwarmOptimization”的论文，标志着粒子群算法的诞生。粒子群算法一经提出，由于它算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，成为一个研究热点。粒子群算法与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索。同时，它又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体中的个体看成是在D维搜索空间中没有质量和体积的粒子，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbestpbest和邻域历史最佳位置gbestgbest聚集，实现对候选解的进化。粒子群算法因具有很好的生物社会背景而易于理解，由于参数少而容易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。**
3模拟退火算法**模拟退火算法（SimulatedAnnealing，SA）的思想最早由Metropolis等人于1953年提出。Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题。模拟退火算法是一种基于MonteCarlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其目的在于：为具有NP（Non-deterministicPolynomial）复杂性的问题提供有效的近似求解算法，它克服了传统算法优化过程容易陷入局部极值的缺陷和对初值的依赖性。模拟退火算法是一种通用的优化算法，是局部搜索算法的扩展。它与局部搜索算法的不同之处，是以一定的概率选择邻域中目标值大的状态。从理论上来说，它是一种全局最优算法。模拟退火算法具有十分强大的全局搜索性能，这是因为它采用了许多独特的方法和技术：基本不用搜索空间的知识或者其他的辅助信息，而只是定义邻域结构，在邻域结构内选取相邻解，再利用目标函数进行评估；采用概率的变迁来指导它的搜索方向，它所采用的概率仅仅是作为一种工具来引导其搜索过程朝着更优化解的区域移动。因此，虽然看起来它是一种盲目的搜索方法，但实际上有着明确的搜索方向。
**
4禁忌搜索算法**搜索是人工智能的一个基本问题，一个问题的求解过程就是搜索。人工智能在各应用领域中，被广泛地使用。现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索技术。禁忌搜索算法（TabuSearchorTabooSearch，TS）的思想最早由美国工程院院士Glover教授在1986年提出，并在1989年和1990年对该方法做出了进一步的定义和发展。在自然计算的研究领域中，禁忌搜索算法以其灵活的存储结构和相应的禁忌准则来避免迂回搜索，在智能算法中独树一帜，成为一个研究热点，受到了国内外学者的广泛关注。禁忌搜索算法是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。它通过禁忌准则来避免重复搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效搜索，以最终实现全局优化。
**
5神经网络算法**人工神经网络（ArtificialNeuralNetwork，ANN）简称为神经网络或称为连接模型。早在1943年，心理学家McCulloch和数学家Pitts合作提出了形式神经元的数学模型，从此开创了神经科学理论研究的时代；1957年Rosenblatt提出的感知器模型，由阈值性神经元组成，试图模拟动物和人脑的感知和学习能力；1982年H.Hofield提出了具有联想记忆功能的Hopfield神经网络，引入了能量函数的原理，给出了网络的稳定性判据，这一成果标志着神经网络的研究取得了突破性的进展。神经网络具有一些显著的特点：具有非线性映射能力；不需要精确的数学模型；擅长从输入输出数据中学习有用知识；容易实现并行计算；由大量的简单计算单元组成，易于用软硬件实现；等等。因为神经网络是一种模仿生物神经系统的新的信息处理模型，并具有独特的结构，所以人们期望它能够解决一些用传统方法难以解决甚至无法解决的问题。迄今为止，已经出现了许多神经网络模型及相应的学习算法。其中Rumelhart和McClelland于1985年提出的BP网络的误差反向后传（BackPropagation，BP）学习算法是一种最常用的神经网络算法。
**
参考文献**《智能优化算法及其MATLAB实例（第2版）》，包子阳，电子工业出版社。