几种常见的优化算法有哪些_几种基本算法

几种常见的优化算法有哪些_几种基本算法阅读目录1.梯度下降法(GradientDescent)2.牛顿法和拟牛顿法(Newton'smethod& Quasi-NewtonMethods)3.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

  我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题“在一定成本下,如何使利润最大化”等。最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。随着学习的深入,博主越来越发现最优化方法的重要性,学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解,比如我们现在学习的机器学习算法,大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。

1. 梯度下降法(Gradient Descent)

  梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局最优解,梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。最速下降法越接近目标值,步长越小,前进越慢。梯度下降法的搜索迭代示意图如下图所示:

 几种常见的优化算法有哪些_几种基本算法

 

  牛顿法的缺点:

  (1)靠近极小值时收敛速度减慢,如下图所示;

  (2)直线搜索时可能会产生一些问题;

  (3)可能会“之字形”地下降。

 几种常见的优化算法有哪些_几种基本算法

 

  从上图可以看出,梯度下降法在接近最优解的区域收敛速度明显变慢,利用梯度下降法求解需要很多次的迭代。

  在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。

  比如对一个线性回归(Linear Logistics)模型,假设下面的h(x)是要拟合的函数,J(theta)为损失函数,theta是参数,要迭代求解的值,theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数,n是特征的个数。

几种常见的优化算法有哪些_几种基本算法

几种常见的优化算法有哪些_几种基本算法

  1)批量梯度下降法(Batch Gradient Descent,BGD)

  (1)将J(theta)对theta求偏导,得到每个theta对应的的梯度:

几种常见的优化算法有哪些_几种基本算法

  (2)由于是要最小化风险函数,所以按每个参数theta的梯度负方向,来更新每个theta:

几种常见的优化算法有哪些_几种基本算法

  (3)从上面公式可以注意到,它得到的是一个全局最优解,但是每迭代一步,都要用到训练集所有的数据,如果m很大,那么可想而知这种方法的迭代速度会相当的慢。所以,这就引入了另外一种方法——随机梯度下降。

  对于批量梯度下降法,样本个数m,x为n维向量,一次迭代需要把m个样本全部带入计算,迭代一次计算量为m*n2

  2)随机梯度下降(Stochastic Gradient Descent,SGD)

  (1)上面的风险函数可以写成如下这种形式,损失函数对应的是训练集中每个样本的粒度,而上面批量梯度下降对应的是所有的训练样本:

几种常见的优化算法有哪些_几种基本算法

  (2)每个样本的损失函数,对theta求偏导得到对应梯度,来更新theta:

几种常见的优化算法有哪些_几种基本算法

  (3)随机梯度下降是通过每个样本来迭代更新一次,如果样本量很大的情况(例如几十万),那么可能只用其中几万条或者几千条的样本,就已经将theta迭代到最优解了,对比上面的批量梯度下降,迭代一次需要用到十几万训练样本,一次迭代不可能最优,如果迭代10次的话就需要遍历训练样本10次。但是,SGD伴随的一个问题是噪音较BGD要多,使得SGD并不是每次迭代都向着整体最优化方向。

  随机梯度下降每次迭代只使用一个样本,迭代一次计算量为n2,当样本个数m很大的时候,随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解:随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价,换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

  对批量梯度下降法和随机梯度下降法的总结:

  批量梯度下降—最小化所有训练样本的损失函数,使得最终求解的是全局的最优解,即求解的参数是使得风险函数最小,但是对于大规模样本问题效率低下。

  随机梯度下降—最小化每条样本的损失函数,虽然不是每次迭代得到的损失函数都向着全局最优方向, 但是大的整体的方向是向全局最优解的,最终的结果往往是在全局最优解附近,适用于大规模训练样本情况。

2. 牛顿法和拟牛顿法(Newton’s method & Quasi-Newton Methods)

  1)牛顿法(Newton’s method)

  牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数(x)的泰勒级数的前面几项来寻找方程(x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

  具体步骤:

  首先,选择一个接近函数 (x)零点的 x0,计算相应的 (x0) 和切线斜率f  ‘ (x0)(这里f ‘ 表示函数 f  的导数)。然后我们计算穿过点(x0,  f  (x0)) 并且斜率为‘(x0)的直线和 轴的交点的x坐标,也就是求如下方程的解:

几种常见的优化算法有哪些_几种基本算法

  我们将新求得的点的 坐标命名为x1,通常x1会比x0更接近方程f  (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示:

几种常见的优化算法有哪些_几种基本算法

  已经证明,如果f  ‘ 是连续的,并且待求的零点x是孤立的,那么在零点x周围存在一个区域,只要初始值x0位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果f  ‘ (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。

 

  由于牛顿法是基于当前位置的切线来确定下一次的位置,所以牛顿法又被很形象地称为是”切线法”。牛顿法的搜索路径(二维情况)如下图所示:

  牛顿法搜索动态示例图:

 几种常见的优化算法有哪些_几种基本算法

 

  关于牛顿法和梯度下降法的效率对比:

  从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)

  根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。

几种常见的优化算法有哪些_几种基本算法

注:红色的牛顿法的迭代路径,绿色的是梯度下降法的迭代路径。

  牛顿法的优缺点总结:

  优点:二阶收敛,收敛速度快;

  缺点:牛顿法是一种迭代算法,每一步都需要求解目标函数的Hessian矩阵的逆矩阵,计算比较复杂。

  2)拟牛顿法(Quasi-Newton Methods)

  拟牛顿法是求解非线性优化问题最有效的方法之一,于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠,使得非线性优化这门学科在一夜之间突飞猛进。

  拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷,它使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化,构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法,尤其对于困难的问题。另外,因为拟牛顿法不需要二阶导数的信息,所以有时比牛顿法更为有效。如今,优化软件中包含了大量的拟牛顿算法用来解决无约束,约束,和大规模的优化问题。

  具体步骤:

  拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型:

几种常见的优化算法有哪些_几种基本算法

  这里Bk是一个对称正定矩阵,于是我们取这个二次模型的最优解作为搜索方向,并且得到新的迭代点:

几种常见的优化算法有哪些_几种基本算法

  其中我们要求步长ak

满足Wolfe条件。这样的迭代与牛顿法类似,区别就在于用近似的Hesse矩阵Bk

代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk

的更新。现在假设得到一个新的迭代xk+1,并得到一个新的二次模型:
 
 
 
 

几种常见的优化算法有哪些_几种基本算法
  我们尽可能地利用上一步的信息来选取Bk。具体地,我们要求
 
几种常见的优化算法有哪些_几种基本算法

  从而得到

几种常见的优化算法有哪些_几种基本算法
  这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。

3. 共轭梯度法(Conjugate Gradient)

  共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。 在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。
  具体的实现步骤请参加wiki百科共轭梯度法
  下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图:
 
几种常见的优化算法有哪些_几种基本算法

 

 
注:绿色为梯度下降法,红色代表共轭梯度法
  MATLAB代码:
复制代码
function [x] = conjgrad(A,b,x)
    r=b-A*x; p=r; rsold=r'*r; for i=1:length(b) Ap=A*p; alpha=rsold/(p'*Ap); x=x+alpha*p; r=r-alpha*Ap; rsnew=r'*r; if sqrt(rsnew)<1e-10 break; end p=r+(rsnew/rsold)*p; rsold=rsnew; end end
复制代码

4. 启发式优化方法

  启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多,包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

  还有一种特殊的优化算法被称之多目标优化算法,它主要针对同时优化多个目标(两个及两个以上)的优化问题,这方面比较经典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。

  这部分的内容会在之后的博文中进行详细总结,敬请期待。这部分内容的介绍已经在博客[Evolutionary Algorithm] 进化算法简介》进行了概要式的介绍,有兴趣的博友可以进行参考(2015.12.13)。

 5. 解决约束优化问题——拉格朗日乘数法

  有关拉格朗日乘数法的介绍请看另一篇博客:《拉格朗日乘数法》 http://www.cnblogs.com/maybe2030/p/4946256.html
 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166964.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Jmeter面试题_软件测试的面试题及答案

    Jmeter面试题_软件测试的面试题及答案最近有个学生反馈,自己在面试的时候,遇到一个jmeter题目,要我帮忙看下,题目如下:进入http://www.weather.com.cn/网站,用jmeter编写脚本实现如下操作(下列要求在同一个测试脚本):(1)编写获取北京天气紫外线、穿衣、洗车、感冒指数的压测脚本,要求将城市参数化10个(城市名字自定义),将城市的当前实时天气>10度作为断言,并将天气数字输出打印到日志,设置2…

  • maven常用打包命令

    maven常用打包命令maven常用打包命令1、mvncompile编译,将Java源程序编译成class字节码文件。2、mvntest测试,并生成测试报告3、mvnclean将以前编译得到的旧的class字节码文件删除4、mvnpakage打包,动态web工程打war包,Java工程打jar包。5、mvninstall将项目生成jar包放在仓库中,以便别的模块调用6、mvncleaninstall-Dmaven.test.skip=true打成jar包,并且抛弃测

  • 时序数据库 日志_mysql恢复数据库

    时序数据库 日志_mysql恢复数据库1.基础1.1时序数据的定义什么是时间序列数据(TimeSeriesData,TSD,以下简称时序)从定义上来说,就是一串按时间维度索引的数据。用描述性的语言来解释什么是时序数据,简单的说,就是这类数据描述了某个被测量的主体在一个时间范围内的每个时间点上的测量值。它普遍存在于IT基础设施、运维监控系统和物联网中。对时序数据进行建模的话,会包含三个重要部分,分别是:主体,时间点和测量值。套用这…

  • Swift4 String截取字符串

    Swift4 String截取字符串varstr1="AlexanderYeah";//1截取字符串的第一种方式//prefix截取前3个字符串varstr2=str1.prefix(3);print(str2);//suffix截取后3个字符串varstr3=str1.suffix(3);print(str3);//2截取一个范围的字符串//从0开始到倒数第二位结…

  • Storm On YARN带来的好处

    Storm On YARN带来的好处

    2021年12月17日
  • ChromeDriver与Chrome版本对应参照表及ChromeDriver下载链接[通俗易懂]

    ChromeDriver与Chrome版本对应参照表及ChromeDriver下载链接[通俗易懂]ChromeDriverVersionChromeVersion74.0.3729.67473.0.3683.687372.0.3626.69722.4671-732.4671-732.4570-722.4469-712.4369-712.4268-702.4167-692.4066-68…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号