机器学习&数据挖掘笔记_12(对Conjugate Gradient 优化的简单理解)
数学优化方法在机器学习算法中至关重要,本篇博客主要来简单介绍下Conjugate Gradient(共轭梯度法,以下简称CG)算法,内容是参考的文献为:An Introduction to the Conjugate Gradient Method Without the Agonizing Pain,具体细节大家还需仔细阅读那篇文章,这篇博客并不是重现那篇论文的内容,只是简单的梳理下CG算法的流程,以及它的重要思路,方便大家理解CG算法。
首先我们需要解决的问题是:求满足线性方程(1):的解x.
那么有人就这么认为了:这个解x不就是吗?对,这样说也不能算错,但是如果A不可逆那么x这样就解不出来了。另外当A矩阵的尺度非常大时(比如几百万维),即使其逆存在,这样计算的计算量也太大。而CG算法则可以通过少数的几步迭代来求出其近似解,虽然求出的解是近似的,但是其精度可以达到很高,完全可以满足我们的需求。
下面就来看看CG算法实现时的大概流程:
1. 随机选取一个初始点,记为,并记为此时方程(1)的残差,记第一个搜索方向为,搜索步长为.
2. 现在假设我们已经按照某个迭代公式在第k步求出了,此时的残差,前面k次的搜索方向分别为,很明显这些变量都是已知的,而现在我们需要求的是第k次的搜索方向.在CG理论中,有这么一个假设,即为,的线性组合,记为.
3. 为了求出,就必须求出系数,怎么求呢?CG理论中另外一个性质就是:和这k个向量关于A共轭,即满足共轭方程,其中0<=j<=k-1. 下面就可以利用该性质列出k个方程来求解这些系数了,其结果为:当0<=j<k-1时,系数;当j=k-1时,系数. 因此此时的搜索方向.
4. 既然的值有了,搜索方向也有了,下一步就改确定搜索步长了,求它的思想是使取得极值,即导数为0。一旦求出了,则下一个迭代点也就求出了。表达式对求导为0后可求得.
5. 循环步骤2,3,4,直到满足收敛条件。
上面只是CG算法的基本版本,而常见的CG算法版本是针对上面的计算公式和作了进一步推导,利用Krylov 子空间的一些性质,最后简化为:和,同时对残差也是经过迭代得到(此处省略)。 由简化前后(此处省略N公式)对比可知,将原先表达式中一些矩阵和向量的乘积运算量减小了,因为很大一部分矩阵乘向量都转换成了向量乘向量。
最后附上论文中关于CG算法的流程图,大家可以参考上面5个步骤来理解CG的主要思路,本博客中的符号可能和论文中的不一定相同,且公式也不一定是正确的,博文只是让大家知道这些公式是由什么理论推出的,有个宏观认识,一切需以论文中的内容为主。
参考资料:
Shewchuk, J. R. (1994). An introduction to the conjugate gradient method without the agonizing pain, Carnegie Mellon University, Pittsburgh, PA.
最新文章
- initialization &; finalization
- JS Nice – JavaScript 代码美化和格式化工具
- Java 泛型(Generics)
- SQL Server内存数据写入磁盘方法比较
- lightoj 1224
- oracle 分区和分区索引
- laravel框架——composer导入laravel
- android Bluetooth(官方翻译)
- 【一天一道LeetCode】#160. Intersection of Two Linked Lists
- 洛谷P5111 zhtobu3232的线段树
- window下tomcat的内存溢出问题
- Visual Studio 2017 - Windows应用程序打包成exe文件(2)- Advanced Installer 关于Newtonsoft.Json,LINQ to JSON的一个小demo mysql循环插入数据、生成随机数及CONCAT函数 .NET记录-获取外网IP以及判断该IP是属于网通还是电信 Guid的生成和数据修整(去除空格和小写字符)
- LeetCode--No.015 3Sum
- Android学习笔记----Java字符串MD5加密
- 标准正态分布表(scipy.stats)
- P3587 [POI2015]POD
- Realtek 8192cu 支持 Android Hotspot 软ap
- Scala中的类学习
- MySQL 连接注意事项
- 缓存数据库redis、memcached。 MongoDB 资源集锦
热门文章
- [转]Maven 划分模块
- Linux下安装tomcat
- 《利用Python进行数据分析》第4章学习笔记
- LDA和PLSA
- LiveCD DSET日志收集
- 【Win10 UWP】微信SDK基本使用方法和基本原理
- MQTT协议简记
- 【C语言学习】《C Primer Plus》第1章 概览
- 何必苦等VS2015?来看看VS2013下实现移动端的跨平台开发
- [异常解决] 安卓6.0权限问题导致老蓝牙程序出现异常解决办法:Need ACCESS_COARSE_LOCATION or ACCESS_FINE_LOCATION permission...