机器学习中的最优化算法总结下图给出了这些算法的分类与它们之间的关系: 接下来我们将按照这张图来展开进

文件名称: 机器学习中的最优化算法总结

所属分类: 机器学习

开发工具:

文件大小: 557kb

下载次数: 0

上传时间: 2019-07-02

提供者: aba****

下载 (557kb)

不能下载？报告错误

详细说明：机器学习中的最优化算法总结下图给出了这些算法的分类与它们之间的关系: 接下来我们将按照这张图来展开进行讲解。费马定理对于一个可导函数,寻找其极值的统一做法是寻找导数为0的点,即费马定理。微积分中的这一定理指出,对于可导函数,在极值点处导数必定为0: 对于多元函数,则是梯度为0 导数为0的点称为驻点。需要注意的是,导数为0只是函数取得极值的必要条件而不是充分条件,它只是疑似极值点。是不是极值,是极大值还是极小值,还需要看更高阶导数。对于元函数,假设x是驻点如果 (x)>0,则在该点处去极小值 2.如果 F (x)<0,则在该点处去极大值如果 f (x)=0,还要看更高阶导数对于多元函数,假设x是驻点: 1.如果 Hessian矩阵止定,函数在该点有极小值 2.如果 Hessian矩阵负定,函数在该点有极大值 3.如果 Hessian矩阵不定,则不是极值点在导数为0的点处,函数可能不取极值,这称为鞍点,下图是鞍点的个例子(来自 SIGAL云端实验室) 除鞍点外,最优化算法可能还会遇到另外一个问题:局部极值问题,即一个驻点是极值点, 但不是全局极值。如果我们对最优化问题加以限定,可以冇效的避免这两种问题。典型的是凸优化,它要求优化变量的可行域是凸集,日标函数是凸函数。关于凸优化的详细讲解可以阅读 SIGAL之前的公众号文章“理解凸优化”。虽然驻点只是函数取得极值的必要条件而不是充分条件,但如果我们找到了驻点,再判断和筛选它们是不是板值点,比之前要容易多了。无论是理论结果,还是数值优化算法,一般都以找驻点作为找极值点的目标。对于一元函数,先求导数,然后解导数为0的方程即可找到所有驻点。对于多元函数,对各个自变量求偏导数,令它们为0,解方程组,即可达到所有驻点。这都是微积分中所讲授的基础方法。幸运的是,在机器学习中,很多目标函数都是可导的,因此我们可以使用这套方法。拉格朗日乘数法费马定理给出的不带约束条件下的函数极值的必要条件。对于一些实际应用问题,一般还带有等式或者不等式约束条件。对于带等式约束的极值问题,经典的解决方案是拉格朗日乘数法对于如下问题构造拉格朗日乘子函数: 在最优点处对x和乘子变量入2 Lambda_0] 的导数都必须为0 解这个方程即可得到最优解。对拉格朗日乘数法更详细的讲解可以阅读任何一木高等数学教材。机器学习中用到拉格朗日乘数法的地方有主成分分析线性判别分析流形学习中的拉普拉斯特征映射隐马尔可夫模型 KKT条件 KKT条件是拉格朗日乘数法的推广,用于求解既带有等式约束,又带有不等式约束的函数极值。对于如下优化问题: 和拉格朗日对偶的做法类似,KKT条件构如下乘子函数入 Lambda 和称为KKT乘子。在最优解处木 X 应该满足如下条件: 等式约束 h 01 )=0和不等式约束 9k g_Ik] e 0是本身应该满足的约束, )=0和之前的拉格朗日乘数法一样。唯一多了关于 g_0 (x)的条件 KKT条件只是取得极值的必要条件而不是允分条件。在机器学习中用到KKT条件的地方有: 支持向量机(SWM) 具体的推导可以阅读 SIGAI之前的公众号文章“用一张图理解SⅦM的脉络”。数值优化算法前面讲述的三种方法在理论推导、某些可以得到方程组的求根公式的情况(如线性函数,正态分布的最大似然估计)中可以使用,但对绝大多数函数来说,梯度等于0的方程组是没法直接解出来的,如方程里面含有指数函数、对数函数之类的超越凶数。对于这种无法直接求解的方程组,我们只能采用近似的算法来求解,即数值优化算法。这些数值优化算法一般都利用了日标函数的导数信息,如一阶导数和二阶导数。如果采川一阶导数,则称为一阶优化算法。如果使用了二阶导数,则称为二阶优化算法。工程上实现时通常采用的是迭代法,它从一个初始点 0 开始,反复使用某种规则从 k 移动到下一个点 k+1 X_{K+1} 构造这样一个数列,直刭收敛到梯度为0的点处。即有下面的极限成立: 这些规则一般会利用一阶导数信息即梯度;或者二阶导数信息即 Hessian矩阵。这样迭代法的核心是得到这样的由上一个点确定下一个点的迭代公式: 梯度下降法梯度下降法沿着梯度的反方冋进行搜索,利用∫函数的一阶导数信息。梯度下降法的迭代公式为根据函数的一阶泰勒展开,在负梯度方向,函数值是下降的。只要学习率 lgamma 设置的足够小,并且没有到达梯度为0的点处,每次迭代时函数值一定会下降。需要设置学习率为一个非常小的正数的原因是要保证迭代之后的 k+1 k+1} 位于迭代之前的值的邻域内,从而可以忽略泰勒展开中的高次项,保证迭代时函数值下降梯度下降法及其变种在机器学习中应用广泛,尤其是在深度学习中。对梯度下降法吏全面的介绍可以阅读 SIGAI之前的公众号文章“理解梯度下降法”。动量项为了加快梯度下降法的收敛速度,减少震荡,引入了动量项。动量项累积了之前迭代时的梯度值,加上此项之后的参数更新公式为: 其中 V{t+1} 是动量项,它取代了之前的梯度项。动量项的讣算公式为它是上一时刻的动量项与本次梯度值的加权平均值,其中 a lalpha 是学习率, mu 是动量项系数。如果按照时间t进行展廾,则第t次迭代时使用了从1到t次迭代时的所有梯度值,且老的梯度值安 Amut 的系数指数级衰减: 动量项累积了之前迭代时的梯度值,使得木次迭代时沿着之前的惯性方向向前走。 Adagrad算法 Adagrad算法是梯度下降法最直接的改进。梯度下降法依赖于人工设定的学习率,如果设置过小,收敛太慢,而如果设置太大,可能导致算法那不收敛,为这个学习率设置一个合适的值非常困难 Adagrad算法根据前几轮迭代时的历史梯度值动态调整学习率,且优化变量向量x的每一个分量都有自己的学习率。参数更新公式为其中 lalpha 是学习因子, g_{ 是第t次迭代时参数的梯度向量, 是一个很小的正数,为了避免除0操作,下标i表示向量的分量。和标准梯度下降法唯一不同的是多了分母中的这一项,它累积了到本次迭代为止梯度的历史值信息用于生成梯度下降的系数值。根据上式,历史导数值的绝对值越人分量学习率越小,反之越人。虽然实现了自适应学习率,但这种算法还是存在问题:需要人工设置一个全局的学习率 lalpha ,随着时间的萘积,上式中的分母会越来越大,导致学习率趋向于0,参数无法有效更新。 RMSProp算法 RMSProp算法是对 Adagrad的改进,避免了长期累积梯度值所导致的学习率趋向于0的问题具体做法是由梯度值构造一个向量RMS,初始化为0,按照衰减系数累积了历史的梯度平方值。更新公式为: Adagrad直接累加所有历史梯度的平方和,而这里将历史梯度平方值按照 \delta (th 衰减之后再累加。参数更新公式为其中是人工设定的参数,与 Adagrad一样,这里也需要人工指定的全局学习率 lalpha AdaDelta算法 AdaDelta算法也是对 AdaGrad的改进,避免了长期累积娣度值所导致的学习率趋向于0的问题,另外,还去掉了对人工设置的全局学习率的依赖。假设要优化的参数为x,梯度下降法第t次迭代时计算出来的参数梯度值为 gt g_{ 。算法首先初始化如下两个向量为0向量: 其中E[ ]是梯度平方(对每个分量分别平分)的累计值,更新公式为: 在这里是向量每个元素分别计算平方,后面所有的计算公式都是对向量的每个分量进行。接下来计算如下RMS量这也是一个向量,计算时分别对向量的每个分量进行。然后计算参数的更新值: RMS [△x]{t-1} 的计算公式和这个类似。这个更新值同样通过梯度来构造,只不过学习率是通过梯度的历史值确定的。更新公式为: 参数更新的迭代公式为: Adam算法 Adam算法整合∫自适应学习率与动量项。算法用梯度构造∫两个向量m和v,前者为动量项, 后者累积了梯度的平方和,用于构造自适应学习率。它们的初始值为0,更新公式为: 其中 B1 beta 1

(系统自动生成,下载前可以参看下载内容)