拟牛顿法

牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息, 而计算Hesse矩阵工作量大, 并且有的目标函数的Hesse矩阵很难计算, 甚至不好求出来, 这就导致仅用目标函数的一阶导数的方法, 拟牛顿法就是利用目标函数值和一阶导数信息, 构造出目标函数的曲率近似, 而不需要明显形成Hesse矩阵, 同时具有收敛速度快的优点. 一: 拟牛顿法条件 目标函数\(f\)在\({x_{k + 1}}\)附近的二次近似为: \[f(x) \approx f({x_{k + 1}}) + g_{k + 1}^T(x - {x_{k + 1}}) + \frac{1}{2}{(x - {x_{k + 1}})^T}{G_{k + 1}}(x - {x_{k + 1}})\] 对上面的式子两边求导, … 继续阅读

共轭梯度法

一: 共轭方向法 共轭方向法是介于最速下降法与牛顿法之间的一个方法, 它仅需利用一阶导数信息, 但克服了最速下降法收敛慢的缺点, 又避免了存储和计算牛顿法所需要的二阶导数信息. 共轭方向法是从研究二次函数的极小化产生的, 但是它可以推广到处理非二次函数的极小化问题. 最典型的共轭方向法是共轭梯度法. 而拟牛顿法也是共轭方向法的一种. 共轭方向的概念是这么定义的: 设\(G\)是\(n \times n\)对称矩阵, \({d_1},{d_2}\)是\(n\)维非零向量, 如果\(d_1^TG{d_2} = 0\), 则称向量\({d_1},{d_2}\)是\(G – \)共轭的. 类似地, 设\({d_1},{d_2},…,{d_m}\)是\({R^n}\)中的任意一组非零向量. 若有\(d_i^TG{d_j} = 0,(i \ne j)\), 则称\({d_1},{d_2},…,{d_m}\)是\(G – \)共轭的. 显然地, 当\(G\)是\(n\)阶单位矩阵时, \(d_i^T{d_j} = 0,(i \ne j)\), 即是正交向量组. 因而共轭概念是正交概念的推广. … 继续阅读

牛顿法

一: 最速下降法 下降法的迭代格式为\({x_{k + 1}} = {x_k} – {\alpha _k}{d_k}\), 其中\({d_k}\)为下降方向, 设\({g_k} = \nabla f({x_k}) \ne 0\), 则下降方向要满足\(d_k^T{g_k} < 0\). 当步长确定时, \(d_k^T{g_k}\)的值越小, 即\({\rm{ - }}d_k^T{g_k}\)的值越大, 函数下降得越快. 由Cauchy-Schwartz不等式\(\left| {d_k^T{g_k}} \right| \le \left\| {{d_k}} \right\|\left\| {{g_k}} \right\|\), 当且仅当\({d_k} = - {g_k}\)时, \(d_k^T{g_k}\)的值最小. … 继续阅读

[ZZ]经典的机器学习方面源代码库

今天给大家介绍一下经典的开源机器学习软件: (非常全,数据挖掘,计算机视觉,模式识别,信息检索相关领域都适用的了) 编程语言:搞实验个人认为当然matlab最灵活了(但是正版很贵),但是更为前途的是python(numpy+scipy+matplotlib)和C/C++,这样组合既可搞研究,也可搞商业开发,易用性不比matlab差,功能组合更为强大,个人认为,当然R和java也不错. 1.机器学习开源软件网(收录了各种机器学习的各种编程语言学术与商业的开源软件) http://mloss.org 2 偶尔找到的机器学习资源网:(也非常全,1和2基本收录了所有ML的经典开源软件了) http://www.dmoz.org/Computers/Artificial_Intelligence/Machine_Learning/Software/ 3 libsvm (支持向量机界最牛的,不用多说了,台湾大学的林教授的杰作) http://www.csie.ntu.edu.tw/~cjlin/libsvm/ 4 WEKA (基于java的机器学习算法最全面最易用的开源软件) http://www.cs.waikato.ac.nz/ml/weka/ 5 scikit (本人最喜欢的一个基于python的机器学习软件,代码写得非常好,而且官方的文档非常全,所有都有例子,算法也齐全,开发也活跃 ,强烈推荐给大家用) http://scikit-learn.org/stable/ 6 OpenCv(最牛的开源计算机视觉库了,前途无可限量,做图像处理与模式识别的一定要用,总不能整天抱着matlab做实验和工业界脱节吧,但是有一定难度) http://opencv.willowgarage.com/wiki/ 7 Orange (基于c++和python接口的机器学习软件,界面漂亮,调用方便,可以同时学习C++和python,还有可视化的功能,) http://orange.biolab.si/ 8 Mallet (基于JAVA实现的机器学习库,主要用于自然语言处理方面,特色是马尔可夫模型和随机域做得好,可和WEKA互补) http://mallet.cs.umass.edu/ 9 NLTK(PYTHON的自然处理开源库,非常易用,也强大,还有几本orelly的经典教程) http://nltk.org/ 10 lucene(基于java的包括nutch,solr,hadoop,mahout等全套,是做信息检索和搜索引擎的同志们必学的开源软件了,学JAVA的必学) http://lucene.apache.org/ 转载地址:http://www.cnblogs.com/kshenf/archive/2012/06/14/2548708.html

一维搜索linesearch

一: 精确搜索-区间分割方法 1). 0.618法 对于一个单谷函数想通过迭代不断缩小该区间的长度, 当区间长度充分小时, 可取这个小区间中的一点作为\(\varphi (t)\)的一个近似极小点. 每次迭代时在搜索区间中任取两个点, 然后比较这两个点的函数值定下新的搜索区间. 当我们想在第二迭代开始时每次只搜索一个点, 即要把上一次迭代被抛弃的点利用上, 并且限制住收缩比相同. 则可以推出0.618法. 2). Fibonacci法 问题的提出: 在0.618法中, 经过N-1次迭代后的搜索区间\(\left[ {{a_N},{b_N}} \right]\)的长度为\({b_N}{\rm{ – }}{a_N} = {\tau ^{N – 1}}({b_1} – {a_1})\), 那么, 如果事先给定了搜索算法的迭代次数N, 按那种规则选取试探点可以使给定的搜索区间长度做最快分割呢? 上面的问题可以转化为一个优化问题: \[\begin{array}{*{20}{c}} {\min }&{{\tau _1}{\tau _2} \cdots … 继续阅读

最优化方法结构

一:无约束问题的最优性条件 对于一个无约束问题\(\min f(x),x \in {R^n}\). 它的极小点类型有局部极小和总体极小两种. 而且一般来说, 总体求总体极小点是一个相当困难的任务, 很多实际问题中求局部极小点已满足了问题的要求. 当研究的问题是具有某种凸性时, 局部极小点就是全局极小点. 设\(f\)的一阶导数和二阶导数存在, 且分别表示为\(g(x) = \nabla f(x),G(x) = {\nabla ^2}f(x),\) 则 1. 收敛点的一阶必要条件: \(g({x^{\rm{*}}}) = 0\); 2. 收敛点的二阶必要条件: \(g({x^{\rm{*}}}) = 0,G({x^{\rm{*}}}) \ge 0\); 3. 收敛点的二阶充分条件: \(g({x^{\rm{*}}}) = 0,G({x^{\rm{*}}})\)是正定矩阵; 4. 如果目标函数为凸函数, 那么全局极小值点的充分必要条件就是\(g({x^{\rm{*}}}) … 继续阅读