优化算法

        机器学习实际上是以一个函数来拟和训练数据中可能存在的一种结构。这个函数有的是本身存在的（结构验证，只求参数），有的是需要我们去寻找的（结构发现，求参数和确定连接方式，神经网络模型）。模型拟和是通过输出结果和预测结果之间的差别，或者是拟合分布与实际分布之间的差别的最小化来实现的。这个过程通过一个实际上比较呆板方法设计的目标函数（损失项 + 惩罚项）来实现。

        现在问题变成对于目标函数求极值。求解的方法有两种，一种是解析法，一种是数值方法。对于比较简单的函数，我们可以通过它的系数关系得到获得极值对应的变量值，这个就是解析法，中学时代，求方程的根等等都是典型的这个方法。但是另外一种是无法求解的，这个就只能通过数值法来获取。比如绝大多数的微分方程，我们都是无法求得他的准确解的。

        可以利用解析法求极值的，对于一个单独函数（无论显示还是隐式），可以通过求导，并且令导数为零的方式来实现；对于有等式约束条件的函数，就用拉格朗日法；对于还有不等式约束条件函数，就用拉格朗日方法改进的KKT方法。当然，这三者都是极大值或者极小值存在的必要而非充分条件。这个方法在理论上是能得到全局最优解的。

        对于大多数的实际问题，由于本身复杂程度，根本不可能有解析法方法来求解，这个时候就只能用数值法来求解。数值法方法有很多，比如可以使用 Monte Carlo 仿真的方法来实现，针对目标函数的特点，要寻找其极值点使用的是数值法中的优化算法。数值法存在的问题，一个是一般的计算量都很大，另外一个容易陷入局部最优解。对于优化算法，一般都是利用导数（一阶或者二阶）这个工具来实现，导数的几何解释是函数图像某一个点切线斜率，越大越陡。虽然都从导数入手，解析法是从极值点结果考虑，数值法中的优化算法则是从极值点变化过程发现。二者有着不同思路。

       利用导数优化算法一般用到一阶和二阶导数。 梯度下降法是典型的使用一阶导数实现方法。通过把误差与对应参数求导（中间有几层结构，可以看着是函数的复合，求导过程会用到链式法则），寻找到哪一个参数是影响最大的，然后按一定的规则（δ规则），对这个参数进行调整（学习率η,动力因子α来确定纠正量），之后再重新测算对误差的影响，这个过程会不断地迭代（几十甚至上百次），直到在通过调整参数时候，对整个误差的影响已经不明显了（足够小的误差能量！）才停下来，然后再把这种方式往反向下一层（神经网络类型模型）推进。在这个过程中，参数多，更主要的是要对提供用于训练样本中每一个输入向量都进行计算，对计算资源消耗巨大，尤其是对于人工神经网络，或者是现在常用深度学习模型（ANN 的改进），因此常常使用运算量小得多的随机梯度下降方法，当然，还是别的改进方法。为了使得对函数求导过程中尽快收敛，使用二阶导数当然更快，这就是所谓的牛顿法，以及改进的拟牛顿法等。这个方法消耗运算资源多（尤其是前者，有矩阵求逆），而且在神经网络/深度学习模型中常用的 BP 算法（运算分为 前向阶段和反向阶段）在将误差信号进行反向传播阶段因为导数（一阶或者二阶）为0或者接近0而造成无法调整参数形成的所谓梯度弥散现象。二阶导数更容易出现这个情况。因此实际工作中使用梯度下降法更多。

        除了以上在计算方法上的技巧，还有策略上的改进。这就是分而治之的思想，把一个大问题分成多个小问题，每一次只优化其中一个，通过局部的优化达到整体的优化。这个分而治之的实现可以在两个不同维度实现。一个是相对于空间的，一个是相对于时间的。前者是那些子问题并列的，后者是子问题在时间上分段的。前者如坐标下降法，SMO 等，后者如我们常见的动态规划法等，强化学习使用的也是这个思想。