【数学应用】机器学习常用最优化算法小结

本文主要是从通俗直观的角度对机器学习中的无约束优化算法进行对比归纳，详细的公式和算法过程可以看最后附的几个链接，都是干货。

机器学习基本概念

统计机器学习整个流程就是：基于给定的训练数据集，由实际需求，需要解决的问题来选择合适的模型;再根据确定学习策略，是最小化经验风险，还是结构风险，即确定优化目标函数;最后便是采用什么样的学习算法，或者说优化算法来求解最优的模型。参照《统计机器学习方法》所讲，统计机器学习(特指有监督学习)的三要素为：

1)模型

模型是指基于训练数据集，所要学习到的概率分布或者决策函数，比如线性模型(线性回归，逻辑回归等)，非线性模型(决策树，神经网络)。还有个重要概念，就是模型的假设空间。比如需要学习的决策函数为线性函数，则所有的线性函数构成了该模型的假设空间。

2) 策略

确定了需要学习哪种模型，接下来任务的便是从该类模型的假设空间中选择出最优的模型。模型的优劣需要通过一定的准则来评价，直观来讲，选用模型的预测误差作为评判标准比较合理。而不同的模型基于模型原理或解优化的便利性，往往对应着不同的误差函数，也叫损失函数，如：

-平方损失函数，对应线性回归;

-对数损失函数，对应logistic回归;

-指数损失函数，对应boosting;

-hinge损失函数，对应SVM;

这里所说的策略就是指：当目标函数仅含有损失函数时，对应经验风险最小化策略，即选择的最优模型在训练集上的平均损失最小;而当目标函数由损失函数项和正则化项构成时，对应结构风险最小化策略，即选择的最优模型不仅在训练集上平均误差比较小，同时在测试集上也能有不错的表现，也就是说得到的模型 要有较好的泛化能力。

当样本集数目足够大时，由于样本的覆盖量足够大，能较好地体现实际数据的分布，直接采用经验风险最小化策略就能保证有很好的学习效果;但当样本 容量不够充足时，并不能很好的体现真实的数据分布，因此过于追求减小模型在训练集上的误差，就容易导致“过拟合”现象，即学习到的模型在未知测试数据上效果不理想。

3)算法

算法便是对应上面最后一步最优模型的具体求解方法，称为最优化算法。

优化算法小结

在机器学习模型求解过程中，一般采用迭代法。常见的迭代优化算法有梯度下降，牛顿法，拟牛顿，高斯-牛顿，BFGS，L-BFGS。。。

1)梯度下降

梯度下降也称为最速下降法，属于一阶优化算法。我们知道，梯度方向对应着函数值变化最快的方向，而目标是寻找局部最小值，若当前初始点的梯度值为正时，最小值应该位于该点的左边，则应该给当前点坐标加上一个负值，故参数的调整量与梯度值的符号是相反的。故，沿着当前点梯度的负方向以合适的步长更新至下一个参数状态是合理的，而且保证以较快速度收敛到局部最小值。而当优化函数为凸函数时，找到的局部最小值就是全局最小值，该点对应的参数集便是全局最优解。

2)牛顿法

牛顿法属于二阶优化算法，来源于数值分析中对方程f(x)=0求根的近似解法，即对f(x)在当前点x0进行一阶泰勒展开式：

f(x)=f(x0)+(x-x0)f’(x0)+O(x-x0)

令展开式为0即可得到增量(x-x0)。在目标函数J(x)的最优化过程中，试图求解J’(x)=0的解，J’(x)便对应上式中的f(x)。这里重点讲下个人对牛顿法的直观理解，函数局部最小值对应的梯度为0，即J’(x)=0。牛顿法的核心思想是采用近似、迭代求解的方式，就是用一个简单的二次曲面模型(或者称抛物线模型，为严格凸的)来拟合当前参数点所对应的局部误差曲面，并且以该二次近似曲面极小值对应的参数增量作为下一次的参数更新量。这样的好处是不仅考虑了当前点的梯度方向，同时考虑了更新后的点的梯度情况，对于比简单的梯度下降法更加快速和稳定。

3)高斯-牛顿法

高斯-牛顿法是一种针对模型优化策略为非线性最小二乘法(LMA)时所设计的特定最优化算法。在上述的牛顿法中，由于需要求解函数Hessian矩阵以及其逆矩阵，不仅计算量大，且并不能保证Hessian矩阵一定是正定的(即不能保证参数更新的方向是梯度下降的)。因此，在高斯牛顿法中，用一阶导Jacobian矩阵的内积来近似二阶导hessian矩阵。

4)拟牛顿法

拟牛顿法的提出就是为了解决牛顿法中求解Hessian矩阵计算量大以及Hessian矩阵可能不可逆的问题，通过建立拟牛顿方程可以方便地获得一个Hessian矩阵的近似矩阵，该矩阵必定为正定矩阵。

5)BFGS算法

上述拟牛顿法中，仍然涉及到近似矩阵的求逆过程，计算量仍然很大。BFGS算法就是进一步对上述的近似矩阵的逆求取一个近似矩阵，求取的过程也是通过建立一系列等式展开的。

6)L-BFGS算法

BFGS法比较适合于解决参数规模适中的无约束最优化问题，而当参数维度特别大时，由于上述获得的近似矩阵随着迭代更新次数的增加将越来越变得稠密，便将导致存储空间不足和计算复杂度过高的问题。L-BFGS算法正是为了解决以上问题提出来的，为了减少矩阵所占的存储空间，L-BFGS利用最近几次迭代过程中的曲率信息来构建当前迭代所需的Hessian近似矩阵;而为了减少计算量，L-BFGS则是首先给当前迭代过程一个Hessian近似矩阵的初始估计H0，在利用前面几代所保存的曲率信息对H0进行修正即得到当前迭代过程的Hessian近似矩阵。