首页 > 编程语言 >BFGS算法

BFGS算法

时间:2023-05-31 16:00:49浏览次数:46  
标签:BFGS 迭代 牛顿 矩阵 算法 Hessian


今天,我来讲一种在机器学习中常用到的优化算法,叫做BFGS算法。BFGS算法被认为是数值效果最好的拟牛顿

法,并且具有全局收敛性和超线性收敛速度。那么接下来将会详细讲解。


Contents

 

   1. 什么是拟牛顿法

   2. 拟牛顿法原理

   3. DFP算法原理

   4. BFGS算法原理

   5. BFGS算法的实现



1. 什么是拟牛顿法

 

   前面Logisitc回归讲解中,我介绍了牛顿法。牛顿法的特点是:收敛速度快,迭代次数少,但是当Hessian

   矩阵很稠密时,每次迭代的计算量很大。随着数据规模的增大,那么Hessian矩阵会越大,需要的存储空间会

增多,计算量也会增大,有时候大到不可计算,所以针对海量数据的计算,牛顿法不再适用。

 

 拟牛顿法是在牛顿法的基础上引入了Hessian矩阵的近似矩阵,避免每次迭代都计算Hessian矩阵的逆,它

   的收敛速度介于梯度下降法和牛顿法之间。拟牛顿法跟牛顿法一样,也是不能处理太大规模的数据,因为计算

   量和存储空间会开销很多。拟牛顿法虽然每次迭代不像牛顿法那样保证是最优化的方向,但是近似矩阵始终是

   正定的,因此算法始终是朝着最优化的方向在搜索。

 

 

2. 拟牛顿法原理

 

   拟牛顿法的基本思想是在牛顿法中用Hessian矩阵的某个近似矩阵来代替它。在高数中,学过泰勒公式,如下

 

       

BFGS算法_拟牛顿法

 

   关于泰勒展开的更多内容,可以参考这里:泰勒公式介绍泰勒公式应用。泰勒公式是用一个近似的多项式

   来代替原来复杂的函数表达式。对于拟牛顿法来说,构造二次模型。如下

 

   

BFGS算法_牛顿法_02

 

   忽略高阶无穷小部分,进行求导得到

 

       

BFGS算法_牛顿法_03

 

   令

BFGS算法_拟牛顿法_04

,那么得到

 

       

BFGS算法_迭代_05

 

   牛顿迭代中,要求Hessian矩阵的逆,计算量增大,而拟牛顿法是用Hessian矩阵的逆矩阵来代替Hessian

   矩阵。即如下迭代式

 

       

BFGS算法_牛顿法_06

 

这个方程就是拟牛顿方程,这就是拟牛顿的核心公式啊。所以最关键的问题是如何得到每一步的

BFGS算法_拟牛顿法_07

。关

   于这个问题,又有很多种方法来迭代计算,接下来主要介绍DFP算法和BFGS算法。

 

 

3. DFP算法原理

 

   在上面的拟牛顿法原理介绍中,已经得到拟牛顿方程。现在来介绍一种算法,叫做DFP算法,它是Davidon、

   Fletcher、Powell三位牛人名字的首字母缩写。在DFP算法中,假设有如下迭代

 

       

BFGS算法_迭代_08

 

   其中

BFGS算法_拟牛顿法_09


BFGS算法_拟牛顿法_10

均为实数,

BFGS算法_拟牛顿法_11


BFGS算法_拟牛顿法_12

均为

BFGS算法_迭代_13

维向量,那么带入上述的拟牛顿方程中,有如下推导

 

       

BFGS算法_拟牛顿法_14

 

那么进一步有

   

BFGS算法_迭代_15

 

 

   接下来,我们重新记一下符号,设

 

   

BFGS算法_迭代_16

 

   那么得到

 

   

BFGS算法_迭代_17

 

   现在只要我们求出了

BFGS算法_牛顿法_18


BFGS算法_拟牛顿法_19


BFGS算法_牛顿法_20


BFGS算法_迭代_21

,那么问题也就解决了。那么为了更容易看出结论,继续作如下变换

 

   

BFGS算法_牛顿法_22

 

那么只需要如下几个条件成立就可以了

 

   

BFGS算法_迭代_23

 

   带入原式最终得到

 

   

BFGS算法_牛顿法_24

 

   由于虽然是有矩阵相乘,但是实际上是向量相乘,然后又矩阵相加,所以时间复杂度为

BFGS算法_拟牛顿法_25

,比起普通

   牛顿迭代矩阵求逆来说,时间复杂度大大降低,这就是DFP算法的原理。

 

 

4. BFGS算法原理

 

   上面的DFP算法中,已经很好地解决了问题,接下来,继续学习BFGS算法。它是Broyden,Fletcher,

   Goldfarb,Shanno四位牛人发明出来到现在的40多年时间里,它仍然被认为是最好的拟牛顿算法。假设

   迭代如下

 

       

BFGS算法_牛顿法_26

 

   这样最终得到迭代式如下

 

       

BFGS算法_牛顿法_27

 

   这就是BFGS算法的原理。

 

 

 

5. BFGS算法的实现

 

   BFGS算法的C++实现参考这里在Python中,有一个优化算法工具,叫做scipy。scipy中的optimize子

   包中提供了常用的最优化算法函数实现。我们可以直接调用这些函数完成我们的优化问题。optimize中函数

   最典型的特点就是能够从函数名称上看出是使用了什么算法,可以参考这里比如BFGS算法的用法如下

 

    

BFGS算法_迭代_28

 

   运行结果如下

 

    

BFGS算法_迭代_29

 

 

标签:BFGS,迭代,牛顿,矩阵,算法,Hessian
From: https://blog.51cto.com/u_16146153/6387827

相关文章

  • Java实战-基于JDK的LRU算法实现、优雅的实现代码耗时统计(Spring AOP、AutoCloseable
    场景Java中基于JDK的LRU算法实现LRU算法-缓存淘汰算法-Leastrecentlyused,最近最少使用算法根据数据的历史访问记录来进行淘汰数据,其核心思想是:如果有数据最近被访问过,那么将来被访问的几率也更高在Java中可以利用LinkedHashMap容器简单实现LRU算法LinkedHashMap底层就是用......
  • twitter僵尸网路检测,只能twitter自己做这种算法
     twitter僵尸网路检测数据样例 TwitterbotdetectorIntheprevioussections,wesawhowtobuildamachinelearning-basedbotnetdetector.Inthisnewproject,wearegoingtodealwithadifferentprobleminsteadofdefendingagainstbotnetmalware.Weareg......
  • 聚类算法:ISODATA算法 ——kmeans算法升级版,不知道k也可以,但是需要你自己指定其他参数
    当K值的大小不确定时,可以使用ISODATA算法。ISODATA的全称是迭代自组织数据分析法。在K均值算法中,聚类个数K的值需要预先人为地确定,并且在整个算法过程中无法更改。而当遇到高维度、海量的数据集时,人们往往很难准确地估计出K的大小。ISODATA算法就是针对这个问题进行了改进,它的思想......
  • 超参数调优——google Vizier采用迁移学习的思想,主要是从之前调参的经验中学习,为新算
    Google使用一套超参数调优算法来烘焙更美味的饼干“超参数调优”和“烘焙饼干”这两件事情,乍一听感觉风马牛不相及,但细想一下,似乎又有一定的相似之处——“黑盒优化”。结构复杂的深度学习模型某种程度上就是一个黑盒,为实现更好的优化目标,我们不断进行“超参数调优”来优化这个黑盒......
  • 一文通吃:从 ZooKeeper 一致性,Leader选举讲到 ZAB 协议与 PAXOS 算法(下)
    本文首发自「慕课网」,想了解更多IT干货内容,程序员圈内热闻,欢迎关注"慕课网"或慕课网公众号!作者:大能|慕课网讲师上篇文章,我们介绍了ZooKeeper集群保证数据一致性和Zookeeper集群Leader选举,这边文章我们接着介绍ZAB协议和Paxos算法ZAB协议在ZooKeeper在处理事务型请求的时候有提到......
  • 算法- 求解最大平均值的子树-经典dfs题目
    给一棵二叉树,找到有最大平均值的子树。返回子树的根结点。Example样例1输入:{1,-5,11,1,2,4,-2}输出:11说明:这棵树如下所示:1/\-511/\/\124-211子树的平均值是4.333,为最大的。样例2输入:{1,-5,11}输出:11说明:1/\-5......
  • 字符串解压缩问题——贪心算法
     importsysdefload_data():returnsys.stdin.read()defget_position_map(s):result={}stack=[]fori,cinenumerate(s):ifc=="[":result[i]=-1stack.append(i)elifc=="......
  • python dijkstra 最短路算法示意代码
     defdijkstra(graph,from_node,to_node):q,seen=[(0,from_node,[])],set()whileq:cost,node,path=heappop(q)seen.add(node)path=path+[node]ifnode==to_node:returncost,pathfora......
  • 第三代测序中基于德布鲁因图的长读错误纠正算法
    第三代测序中基于德布鲁因图的长读错误纠正算法摘要——PacBio单分子实时测序平台可以产生大量的长读序列,这对基因组的从头组装非常重要。尽管这些长读取具有15%的高错误率,但是由于它们的高错误率而放弃它们是不明智的。Illumina测序平台产生了长度在100bp左右的短读,错误率低,成本......
  • 面向第三代测序技术的基因组长序列片段比对算法研究
    面向第三代测序技术的基因组长序列片段比对算法研究周佩霞湖南师范大学摘要:随着测序技术不断发展和改进,测得的基因组序列片段数据的特征也在不断变化。为适应当前第三代测序技术,基因组序列比对算法需要进行深入的研究和改进,以便更适合于处理第三代测序技术测得的长序列片......