其他
机器学习最优化算法(全面总结)
转自:网络
导言
对于几乎所有机器学习算法,无论是有监督学习、无监督学习,还是强化学习,最后一般都归结为求解最优化问题。因此,最优化方法在机器学习算法的推导与实现中占据中心地位。在这篇文章中,小编将对机器学习中所使用的优化算法做一个全面的总结,并理清它们直接的脉络关系,帮你从全局的高度来理解这一部分知识。
机器学习要求解的数学模型
几乎所有的机器学习算法最后都归结为求一个目标函数的极值,即最优化问题,例如对于有监督学习,我们要找到一个最佳的映射函数f (x),使得对训练样本的损失函数最小化(最小化经验风险或结构风险):
对于形式和特点各异的机器学习算法优化目标函数,我们找到了适合它们的各种求解算法。除了极少数问题可以用暴力搜索来得到最优解之外,我们将机器学习中使用的优化算法分成两种类型(本文不考虑随机优化算法如模拟退火、遗传算法等):
公式求解
数值优化
能正确的找到各种情况下的极值点
速度快
对于一个可导函数,寻找其极值的统一做法是寻找导数为0的点,即费马定理。微积分中的这一定理指出,对于可导函数,在极值点处导数必定为0:
如果f''(x)>0,则在该点处去极小值
如果f''(x)<0,则在该点处去极大值
如果f''(x)>=0,还要看更高阶导数
如果Hessian矩阵正定,函数在该点有极小值
如果Hessian矩阵负定,函数在该点有极大值
如果Hessian矩阵不定,还需要看更(此处误)
费马定理给出的不带约束条件下的函数极值的必要条件。对于一些实际应用问题,一般还带有等式或者不等式约束条件。对于带等式约束的极值问题,经典的解决方案是拉格朗日乘数法。
对于如下问题:
主成分分析
线性判别分析
流形学习中的拉普拉斯特征映射
隐马尔可夫模型
KKT条件是拉格朗日乘数法的推广,用于求解既带有等式约束,又带有不等式约束的函数极值。对于如下优化问题:
支持向量机(SVM)
前面讲述的三种方法在理论推导、某些可以得到方程组的求根公式的情况(如线性函数,正态分布的最大似然估计)中可以使用,但对绝大多数函数来说,梯度等于0的方程组是没法直接解出来的,如方程里面含有指数函数、对数函数之类的超越函数。对于这种无法直接求解的方程组,我们只能采用近似的算法来求解,即数值优化算法。这些数值优化算法一般都利用了目标函数的导数信息,如一阶导数和二阶导数。如果采用一阶导数,则称为一阶优化算法。如果使用了二阶导数,则称为二阶优化算法。工程上实现时通常采用的是迭代法,它从一个初始点x0开始,反复使用某种规则从xk移动到下一个点xk+1,构造这样一个数列,直到收敛到梯度为0的点处。即有下面的极限成立:
梯度下降法沿着梯度的反方向进行搜索,利用了函数的一阶导数信息。梯度下降法的迭代公式为:
为了加快梯度下降法的收敛速度,减少震荡,引入了动量项。动量项累积了之前迭代时的梯度值,加上此项之后的参数更新公式为:
AdaGrad算法是梯度下降法最直接的改进。梯度下降法依赖于人工设定的学习率,如果设置过小,收敛太慢,而如果设置太大,可能导致算法那不收敛,为这个学习率设置一个合适的值非常困难。AdaGrad算法根据前几轮迭代时的历史梯度值动态调整学习率,且优化变量向量X的每一个分量xi都有自己的学习率。参数更新公式为:
RMSProp算法是对AdaGrad的改进,避免了长期累积梯度值所导致的学习率趋向于0的问题。具体做法是由梯度值构造一个向量RMS,初始化为0,按照衰减系数累积了历史的梯度平方值。更新公式为:
AdaDelta算法也是对AdaGrad的改进,避免了长期累积梯度值所导致的学习率趋向于0的问题,另外,还去掉了对人工设置的全局学习率的依赖。假设要优化的参数为x,梯度下降法第t次迭代时计算出来的参数梯度值为gt。算法首先初始化如下两个向量为0向量:
Adam算法整合了自适应学习率与动量项。算法用梯度构造了两个向量m和v,前者为动量项,后者累积了梯度的平方和,用于构造自适应学习率。它们的初始值为0,更新公式为:
假设训练样本集有N个样本,有监督学习算法训练时优化的目标是这个数据集上的平均损失函数:
牛顿法是二阶优化技术,利用了函数的一阶和二阶导数信息,直接寻找梯度为0的点。牛顿法的迭代公式为:
牛顿法在每次迭代时需要计算出Hessian矩阵,并且求解一个以该矩阵为系数矩阵的线性方程组,Hessian矩阵可能不可逆。为此提出了一些改进的方法,典型的代表是拟牛顿法。拟牛顿法的思路是不计算目标函数的Hessian矩阵然后求逆矩阵,而是通过其他手段得到一个近似Hessian矩阵逆的矩阵。具体做法是构造一个近似Hessian矩阵或其逆矩阵的正定对称矩阵,用该矩阵进行牛顿法的迭代。所有这些主要的数值优化算法都可以在SIGAI云端实验室上免费完成实验:www.sigai.cn通过构造目标函数,指定优化算法的参数与初始化迭代值,可以可视化的显示出算法的运行过程,并对不同参数时的求解结果进行比较。
标准牛顿法可能不会收敛到一个最优解,也不能保证函数值会按照迭代序列递减。解决这个问题可以通过调整牛顿方向的步长来实现,目前常用的方法有两种:直线搜索和可信区域法。可信域牛顿法是截断牛顿法的一个变种,用于求解带界限约束的最优化问题。在可信域牛顿法的每一步迭代中,有一个迭代序列xk,一个可信域的大小Δk,以及一个二次目标函数:
分治法是一种算法设计思想,它将一个大的问题分解成子问题进行求解。根据子问题解构造出整个问题的解。在最优化方法中,具体做法是每次迭代时只调整优化向量的一部分分量,其他的分量固定住不动。
坐标下降法的基本思想是每次对一个变量进行优化,这是一种分治法。假设要求解的优化问题为;
SMO算法也是一种分治法,用于求解支持向量机的对偶问题。加上松弛变量和核函数后的对偶问题为:
分阶段优化的做法是在每次迭代时,先固定住优化变量X一部分分量a不动,对另外一部分变量b进行优化;然后再固定住b不动,对b进行优化。如此反复,直至收敛到最优解处。AdaBoost算法是这种方法的典型代表。AdaBoost算法在训练时采用了指数损失函数:
动态规划也是一种求解思想,它将一个问题分解成子问题求解,如果整个问题的某个解是最优的,则这个解的任意一部分也是子问题的最优解。这样通过求解子问题,得到最优解,逐步扩展,最后得到整个问题的最优解。隐马尔可夫模型的解码算法(维特比算法),强化学习中的动态规划算法是这类方法的典型代表,此类算法一般是离散变量的优化,而且是组合优化问题。前面讲述的基于导数的优化算法都无法使用。动态规划算法能高效的求解此类问题,其基础是贝尔曼最优化原理。一旦写成了递归形式的最优化方程,就可以构造算法进行求解。推荐阅读 点击标题可跳转