LM和BFGS算法的性能分析与比较-毕业论文

摘要

数值优化是机器学习的重要部分，不断研究和改进已有的优化算法，使其更快更高效，是机器学习领域的一个重要研究方向。作为数值优化算法中具有代表性的两个二阶算法，LM和BFGS算法各有优缺点，对它们的性能进行分析和比较给二阶数值算法的改进及更广泛的应用提供重要参考。

本论文从LM和BFGS算法的数学基础开始阐述，通过对比两个算法求解多个函数极小值的问题，我们发现LM算法和BFGS算法的差异并不大。大多数情况下LM算法能够达到更小的误差，但是迭代次数比BFGS算法稍多。对于等高线为椭圆的函数，LM算法的收敛速度通常比BFGS算法快，但是后期运算的迭代次数比BFGS算法多；而其他情况下LM算法和BFGS算法的收敛速度差别不大。由于LM算法在大部分情况下的极值求解效率稍高，我们实现了基于LM算法在前向神经网络中的学习，并用于解决模式分类问题。实验结果表明基于LM算法的前向神经网络在垃圾邮件分类应用中能取得90%以上的分类正确率。

关键词：数值优化，LM算法，BFGS算法，前向神经网络

Abstract

Numerical optimization is an important part of machine learning. The analysis

study of existing optimization algorithms to make them faster and more efficient is an important research direction in the field of machine learning. As two popular second-order algorithms, the LM and BFGS algorithms have their own advantages and disadvantages. The analysis and comparison of their performance have great significance for the improvement of the second-order numerical algorithms and their wider application in engineering areas.

This thesis starts from introducing the mathematical foundation of LM and

BFGS algorithms. By comparing the performance of the two algorithms for finding the minima of different functions, we find that the LM and BFGS algorithms have similar performance for numerical optimization problems. In most cases of our experiments, the LM algorithm can achieve smaller error, but the number of iterations is slightly higher than that of the BFGS algorithm. For the functions with elliptical contours, the convergence speed of the LM algorithm is usually faster than that of the BFGS algorithm, but the iterations of later computation are much more than those of the BFGS algorithm. while in other cases,their convergence speed is almost the same. Because of the higher efficiency of the LM algorithm in most cases, the LM algorithm is employed to train feedforward neural networks which are applied to deal with some pattern classification problem. The experimental results show that the feedforward neural network trained by the LM algorithm can reach more than 90% classification accuracy in the applications of classify spam and none spam email.

Keywords：Numerical optimization，LM algorithm，BFGS algorithm，Feedforward neural networks

第一章 绪论

1.1 研究背景

优化算法是用来求解问题的最优解或近似最优解的[15]。我们在工程领域遇到的许多问题都可以建模成最优化模型来求解。大部分的机器学习算法本质都是建立优化模型，将学习问题转化为优化问题，通过数值优化算法对目标函数进行优化，从而训练出有效的结果。近年来，人工智能迅速发展起来，为能完成更多更复杂的智能应用，机器学习技术的发展备受期待。机器学习基于数据统计并严重依赖于数值优化算法的效率，如今智能应用中的计算量日益庞大，计算平台越来越强大，人们对速度、精度以及效率的追求不断提高。数值优化作为机器学习的一个重要支柱，对优化算法的改进和研究成为机器学习领域的重要课题[9,12]。从最流行的梯度下降法（Gradient Descent，GD）、牛顿法（Newton’s method）、拟牛顿法（Quasi-Newton method），到目前一些启发式算法如模拟退火算法（Simulated Annealing Algorithm，SAA）、粒子群优化算法（Particle Swarm Optimization，PSO）、差分衍化算法（Differential Evolution，DE）、遗传算法（Genetic Algorithm，GA）等。不同的算法都有各自的优点和局限性，针对不同的问题，结合问题需求选择适合的优化算法将对最终结果产生很大影响。对各有优势和局限性的优化算法性能进行仔细分析比较，不仅能帮助那些正在为如何选择合适的优化算法而发愁的人们，而且能给那些正在进行优化算法改进研究的人员们提供一些参考数据，从而设计出应用更广泛的新算法，以解决更具挑战性的机器学习问题。

数值优化算法可分为一阶算法和二阶算法，一阶优化算法如梯度下降法以及一些它的改进算法是神经网络里很常用的算法[15]。一阶优化算法只需要计算一阶偏导数，计算量少算法简单，但有时候收敛速度很慢。如在目标函数（代价函数）较为平坦的区域，梯度的变化十分小使收敛速度会很慢。还有在深度神经网络中网络深度较深的情况下，其梯度可能消失而导致收敛速度缓慢对于这种情况进行二阶偏导寻优效果可能会更好。二阶的优化算法，如传统的牛顿算法是需要计算二阶偏导的，这使得计算量比一阶算法多，且复杂度和难度都升高。但是二阶算法却具有收敛速度快并且不容易陷入鞍点的优点。对于本论文中所研究的两个算法：LM（Levenberg–Marquardt

algorithm）和BFGS（Broyden-Fletcher-Goldfarb-Shanno algorithm）算法都是改进的二阶算法，不需要直接计算二阶偏导海森（Hessian）矩阵，而是计算拟海森矩阵或近似的海森矩阵，大大减小了计算复杂度，是目前较为受欢迎的两个二阶算法。其中LM算法通过引入阻尼系数正则化海森矩阵，不仅保证了海森矩阵正定可逆，并且避免在靠近鞍点的地方梯度向错误的方向移动[10]。而BFGS算法通过梯度迭代来近似海森矩阵的逆矩阵减少计算量[13]。对非线性优化领域具有代表性的LM和BFGS算法性能进行分析比较，将为今后优化算法的应用、改进和设计提供重要参考资料。

1.2 国内外研究现状

机器学习的主流是神经网络，为使得神经网络能够有更多更广泛的应用，机器学习领域的学者们也在努力进行优化算法的改进。

李南星、盛益强、倪宏分别采用LM、Adam和GD算法训练MLP模型，对比分析MLP模型的测试集MSE，确定使用LM算法的MLP模型提出一种基于CT图像准确预测颅骨声参数的方法[1]。

Mohammad Mehdi Ebadzadeh和Armin Salimi-Badr提出了一种基于LM算法的相关模糊规则模糊神经网络模型（CFNN），用于逼近非线性函数，特别是输入变量之间高相关性的模糊规则数量较少的函数。该算法已被成功应用于静态函数逼近，时间序列预测，非线性动态系统辨识和现实世界复杂回归问题等7个测试实例。根据测试观察，它可以比其他过去的算法更好地逼近非线性函数，结构更紧凑，模糊规则数更少[2]。

权凌霄、郭海鑫、盛世伟、李雷提出一种使用遗传算法和LM算法相结合的优化算法，采用遗传算法确定BP神经网络的最佳初始权值矩阵，应用LM算法在局部解空间里训练BP神经网络寻求全局最优解。可证明该方法解决了标准BP神经网络在故障诊断时存在的一些缺点，比如学习效率不高、收敛速度很慢、容易陷入局部极小值点以及对初始参数较为敏感等。此外该算法除了保留了BP神经网络的广泛映射能力还提升了学习速度和精确搜索的能力。通过对MOOG D761-2716A机械反馈伺服阀进行故障诊断，进一步说明了该方法具有实用性和高效性[3]。

王良诣、姜礼杰、王勇针对曲柄转角限定和未限定的平面四杆机构轨迹综合问题,将遗传算法全局搜索快速收敛和BFGS算法局部快速收敛的优越性，设计出一种结合

了遗传算法和BFGS算法的平面四杆机构优化算法。和其他启发式智能算法运用在一些实例上得出的优化结果进行对比，可证明关于曲柄转角限定以及曲柄转角未限定的平面四杆机构的轨迹拟合问题中，这种结合遗传算法和BFGS算法的新算法具有非常好的全局收敛性能[4]。

Neculai Andrei提出了用于无约束优化问题的双参数标度BFGS算法。此方法中，在原有的BFGS修正公式的前两项进行正参数缩放，而第三项进行另一种正参数缩放。选择这种参数调整是为了改进BFGS修正的矩阵Bk的特征值结构。通过对缩放的BFGS矩阵的特征值进行聚类来确定如何缩放BFGS修正公式的前两个项的参数。另一方面，缩放第三项参数的确定是与共轭梯度方法的共轭条件最小化相结合得到的。忽略优化目标函数的凸性，使用非精确线性搜索法Wolfe搜索时，可证明双参数标度BFGS法的全局收敛性是很好的。使用80个无约束优化测试函数和中等规模数量的变量，经过实验初步证明，这种双参数标度BFGS方法比标准BFGS修正或其他一些缩放BFGS方法更有效[5]。

1.3 研究内容

本课题从LM算法和BFGS算法最基础的数学原理开始研究，然后通过求解一些函数极值问题对这两个优化算法的性能进行比较分析。为了进行公平的比较，这两个算法所采用的停止条件、寻优起始点都是相同的。通过比较LM算法和BFGS算法在求解过程中的运算复杂度、迭代次数、计算精度、运算时间等，结合两个算法的寻优轨迹图以及函数变化曲线图分析出两个算法在求解这类问题时的各自的优点和局限性。

通过比较结果，决定将LM算法运用到实际应用中。本论文最后设计实现了基于LM算法前向神经网络的学习。一个三层的前向神经网络理论上可以逼近闭区间上任意一个连续的函数，三层前向神经网络是常用的模型之一，而传统的前向神经网络用的最多的是梯度下降法优化目标函数。这种算法收敛速度很慢，并易陷入局部最优解，而运用LM算法训练的前向神经网络具有超线性收敛。

从UCI上下载几个数据集作为样本和测试集，将其用来训练和测试运用了LM算法前向神经网络。最后通过调整隐层神经元数量对该算法性能做出分析。

1.4 论文结构

本论文由五个部分组成，包括四个章节和一个总结。 第一章是绪论部分，阐述了本课题的研究意义、现状和内容。

第二章是优化算法的基础知识部分，介绍LM算法和BFGS算法的一些基础数学原理、两个算法的基本流程以及步长搜索算法的数学基础算法流程。

第三章是LM算法和BFGS算法求解优化问题的实验结果和分析比较。 第四章是介绍前向神经网络的基础知识以及运用LM算法的前向神经网络的的实际运用。

最后是总结，通过实验得出的总结论，对LM算法和BFGS算法性能各自的优缺点做出最终的比较和分析。

第二章 数值优化算法基础

2.1 LM算法

LM算法是用来解决最小二乘问题最常用的方法，它结合了梯度下降法和高斯-牛顿法（Gauss-Newton method，G-N），当实际值与理想值相差很多的时候，LM算法接近于梯度下降法，而当实际值与理想值比较接近的时候，LM算法则表现得像高斯牛顿法。

2.1.1 非线性最小二乘问题

非线性最小二乘问题作为无约束优化问题中很重要的一个的应用，其在实际应用中的很多方面都有涉及。非线性最小二乘问题也被称作无约束极小平方和函数[17]，其基本形式如下：

fnyno(m)( 2.1.1 )

2Sfi(m) 2  ( 2.1.2 )

i 1 n

式中θ为自变量，S为目标函数。

当训练神经网络模型时，f为误差函数（代价函数），yn为理想值，o()为实际值，S为误差平方和，前面的系数只是为了方便后续计算并不影响整体思想，θ为神经网络中的权值或阈值，需要找到合适的 1，2,,m 的值使得S的值最小。神经网络的优化过程就是方差或均方差最小化的过程。

2.1.2 牛顿法（Newton method）

前面提到的梯度下降法是根据一阶泰勒级数展开式推导而来，而本节的牛顿法是忽略了高阶无穷小的二阶泰勒级数展开式推导得到，如下所示：

f(x)f(xx)f(x)gTx1xTHxkk1kkkkkkk2( 2.1.3 )

其中，gk为函数f的梯度向量gkf(xk)，Hk为函数f的二阶偏导Hk2f(xk)，即海森矩阵。

牛顿法的关键就是要求出这个二次逼近的驻点，从而得到函数的极小值。所以得

到必要条件：

Hx k  g k  k  0 ( 2.1.4 )

可求得  x k 为：  x k   H k 1 g k 式（2.1.5）也称为牛顿方向，是保证函数值下降的搜索方向。

从而得到牛顿法的迭代方程： x k  1  x k  H k 1 g k

2.1.3 Jacobian矩阵

假设我们所讨论的目标函数为如下的平方和函数的形式

f ( x )  1n2  F 2i ( x )  F T ( x )F (x ) i则函数f的梯度的第j个元素为

 f ( x )   f ( x )   nj F ( x )  F i ( x ) xijixj则函数f的梯度可表示为：

g   f ( x )  J T ( x ) F ( x ) 其中J(x) 称为雅克比（Jacobian）矩阵，其形式为：

  F1(x)F1(x)F1(x)  x 1x2xm  F 

2(x)F2(x)F2(xJ(x))

xx 12xm   Fn(x)Fn(x)F) n(xx1x2xm

( 2.1.5 ) ( 2.1.6 ) ( 2.1.7 ) ( 2.1.8 ) ( 2.1.9 ) ( 2.1.10 )

2.1.4 LM算法原理

式（2.1.3）中提到的海森矩阵，它作为函数f的二阶偏导矩阵，其第j，k个元素为：

n2Fi(x)2f(x)Fi(x)Fi(x)F i(  f j ,k ( x )    x )  ( 2.1.11 )  xjxkxkxjxki1xj

2Fi(x)当假设 F x ) 很小时，可得到近似的海森矩阵： i(xjxk2( x ) ( 2.1.12 ) H ( x )   f ( x )  J ( x ) J

将（2.1.12）和（2.1.9）代入（2.1.6）可得：

2Tx k x k ) F x k  1  [ J ( x k ) J ( x k )] J ( ( x k ) ( 2.1.13 )

式（2.1.13）就是高斯-牛顿法，相比传统的牛顿法，高斯-牛顿法不需要计算二阶偏导，大大减少了计算量，但是得到的近似海森矩阵并不一定可逆，因此对原来的近似海森矩阵做了修改：

G  H   I ( 2.1.14 ) 式中加入阻尼系数，因此得到了LM算法：

x k  1  x k  [ J T ( x k ) J ( x k )   1 J T ( x k ) F ( x k ) ( 2.1.15 ) I ]k 由（2.1.15）式可看出，当k变得很大，LM算法接近于小学习率的梯度下降法，而当k趋近于0时，LM算法变成了高斯-牛顿法。

阻尼系数k的选择对LM算法来说是十分关键的，它对优化成功率和效率都有很大影响。增大阻尼系数k会减小学习率也就是步长会缩短，减小阻尼系数k会增大学习率也即步长增长，所以LM算法中已经包括了学习率的调整。

起初，将阻尼系数k设为一个较小的值，如果得到的新函数值没有减小则增大阻尼系数的值，重新计算函数值，一直重复该步骤最终将会使函数值减小因为此时相当于朝着最速下降的方向。如果第一次就使得函数值减小，那么减小阻尼系数的值，此时算法将接近高斯-牛顿法较快的收敛，因此LM算法很好的折中了牛顿法和最速下降法的优点，保证了算法的收敛性和运算速度。

T1T

2.1.5 LM算法流程

LM算法主要包括六个步骤，其流程如下：

1、首先初始化x0、阻尼系数0、参数β、误差容限，初始矩阵I为单位矩阵，求出初始函数值f(x0)以及F(x0)；

2、计算出雅克比矩阵Jk；

TTJkkI以及函数梯度fkJkFk； 3、计算海森矩阵修正式GkJk4、检验迭代终止条件fk，如果满足，则目前的xk就是最优解坐标停止迭代，否则往下；

15、计算出增量xkGkfk，根据xnewxkxk得到新的函数值f(xnew)以及

F(xnew)；

6、如果函数值下降，即f(xnew)f(xk)，则xk1xnew，F(xk1)F(xnew)，

f(xk1)f(xnew)且缩小阻尼系数为k1k/，跳转到第2步。否则不作更新，xk1xk，F(xk1)F(xk)，f(xk1)f(xk)且放大阻尼系数为k1k，跳转到第

3步。

其中迭代是从k0开始的，阻尼系数的初始值一般取比较小的值如0.01，而调整参数>1，如10。这里对阻尼系数的调整用到的是信赖域法。

2.2 BFGS算法

1970年Broyden，Fletcher，Goldfarb，Shanno提出了一种不易变为奇异矩阵的矩阵迭代修正法将其命名为BFGS算法，该算法可使用非精确搜索方法，其具有全局收敛性和超线性收敛性[6]，后来被证实是解决无约束优化问题最有效的方法之一。一直以来，BFGS算法被公认为是拟牛顿法中数值优化效果最好的算法。

2.2.1 拟牛顿法（Quasi-Newton method）

式（2.1.6）得到了牛顿迭代，从之前的叙述我们可知，牛顿迭代中的需要求海森矩阵的逆，计算量很大，还要求函数必须有连续的二阶偏导，并且不能保证海森矩阵

正定可逆。因此拟牛顿法的提出就是用拟海森矩阵或是拟海森矩阵的逆来代替原来的

1海森矩阵，通常BkHk，DkHk，保证拟海森矩阵正定对称[13]。

拟牛顿法的关键就是如何求出每一步的Bk或Dk，确保可以求出使函数下降的方向。关于Bk或Dk的修正方法，有DFP（Davidon-Fletcher-Powell）法、BFGS算法。

对二阶泰勒展开式（2.1.3）进行求导得到：

 f ( x k  1)   f ( x k )  H k  x k ( 2.2.1 ) 1( x k )   f ( x k 1 )   f H k  1  x k ( 2.2.2 )

式（2.2.2）就是拟牛顿条件，式中xkxk1xk并不是牛顿法搜索方向而是增量。

2.2.1 BFGS算法原理

BFGS算法采用秩2修正法修正Bk：

TTykykBkskskBk B 1  B T  T ( 2.2.3 ) kk ykskskBksk式中ykf(xk1)f(xk) ，skxk1xk。

T矩阵Bk正定是使目标函数下降的条件，而保证其正定的充要条件是：

s k y k 0 ( 2.2.4 ) 所以BFGS算法中在该条件下对矩阵Bk进行修正就可以使得目标函数下降。

2.2.2 BFGS算法流程

BFGS算法流程主要包括五个部分： 1、求解搜索的方向：

1dBkk  g k ( 2.2.5 )

2、沿着搜索到的方向进行线性搜索学习率λ:

x f x k   kd k   min  f k   k  ( 2.2.6 ) kd0得到新的点：

xk1xkkdk ( 2.2.7 )

3、运用式（2.2.3）修正Bk得到Bk1；

4、判断迭代终止条件是否满足：

 f ( x k )   ( 2.2.8 )

上述流程 从k=0开始迭代，初始B0一般为单位矩阵。当满足终止条件说明达到收敛，xk即为所求点的坐标结束迭代。否则将修正得到的Bk1带入第一步，重新进入整个流程重复迭代，直到满足收敛条件。

2.3 Armijo搜索

有很多可进行学习率搜索的一维线性搜索方法，大致分为两类：精确线性搜索和非精确线性搜索。常用的精确线性搜索方法有黄金分割法（0.618法）等，常见的非精确线性搜索方法有Armijo法、Goldstein法以及Wolf-Powell法等[6]。

精确线性搜索方法要求求出学习率λ作为自变量的一元函数()f[xkdk]的最小值点，计算量很大并且有些函数求不到最小值点。而非精确线性搜索只要求学习率λ使得函数在xk处的值(k)f[xkkdk]比(0)f(xk)小，因此在计算上容易实现，计算量也相应比精确线性搜索少[7]。

本课题运用的是Armijo型线性搜索，对于给定的(0,0.5)，取k0使得： f ( x k   k d k )  f ( x k )   k  f ( x k ) d k ( 2.3.1 )

T当(0,0.5)时，可保证牛顿法和拟牛顿法的超线性收敛性。 利用函数()f[xkdk]，可将（2.3.1）等价为：

  (  k )   (0)  k  (0) ( 2.3.2 )

由于dk是f在xk处的下降方向且满足'(0)f(xk)Tdk0，则式（2.3.1）对充分小的正数k均成立。

在BFGS算法中应用Armijo搜素算法时，并不能保证yksk0。但是Armijo搜索算法因为简单且程序容易实现而深受欢迎，本课题使用该方法并不会影响LM算法和BFGS算法的性能对比分析，但为了保证矩阵Bk的对称正定性，采用如下修正方式：

TB,ykksk0

TTBBssByyk1 B k k k k k k T ( 2.3.3 ) ksTBsyTs,yksk0kkkkkT'只要B0对称正定，（2.3.3）式可保证矩阵Bk对称正定。

第三章 基于LM算法与BFGS算法的优化问题求解

本章将运用LM算法和BFGS算法求解一些函数的最优解，其中大部分函数是数值优化领域经典的测试函数，如Rosenbrock函数、Beale函数、Powell’s Quadratic函数等。针对不同的函数，两个算法选取相同的起始点开始迭代，并且统一终止迭代的条件，误差容限精度相等。LM算法的阻尼系数初始值为2，调整系数为1.5，两个算法的误差精度都设为110-6。运行算法后通过比较算法的迭代次数、误差、运算时间以及寻优轨迹图进行两个算法性能的分析。

运用优化算法对目标函数进行优化的实质就是求解目标函数的最小值或极小值，其过程就是从一初始点开始，根据优化算法得到的方向和步长运行到下一个点，直到找到一个函数值最小的点。整个过程就像一个下山的过程，一直朝着高度减小的方向走，直到走到山底。而这个寻找下降方向和每一步步长的过程就是优化算法的任务。

3.1 Rosenbrock函数的极值求解

图 3.1.1 Rosenbrock函数（N=2）三维曲面图

由于Rosenbrock函数的全局最优解位于一个平坦的“山谷”中，要收敛到全局

最小值点是比较困难的，所以它常被用来作为优化算法的测试函数，其公式如下：

222x )  x x f ( [(1 i )  100( x i  i ) ] ( 3.1.1 ) 1

i1N1 其中xRN，该函数没有局部最优解，只在(1,1,1...)T处也即xi1时有一个全局

最优解0。

当Rosenbrock函数N=2时，其方程为：

f(x)(1x1)2100(x2x12)2( 3.1.2 )

其三维曲面图如图3.1.1所示。

运用LM算法和BFGS算法求解N=2的Rosenbrock函数的全局最优解，理想的最优解在(1,1)T其函数值为0。

1)T，两个算法运行后的寻优轨迹图和函数值变化曲线图如选取起始点为(0.4，下：

图3.1.2 起始点为(0.4,1)的等高线寻优轨迹图

T

图3.1.3 起始点为(0.4,1)的函数值变化曲线

T选取起始点为(0,0)T，两个算法运行后的寻优轨迹图和函数值变化曲线图如下：

图3.1.4 起始点为(0,0)的等高线寻优轨迹图

T

图3.1.5 起始点为(0,0)的函数值变化曲线

T选取起始点为(0.6,0.1)T，两个算法运行后的寻优轨迹图如图3.1.6所示，函数值变化曲线图如图3.1.7所示。

2)T，两个算法运行后的寻优轨迹图如图3.1.8所示，函数值变选取起始点为(2，化曲线图如图3.1.9所示。

5)T，两个算运行后的寻优轨迹图如图3.1.10所示，函数值变化选取起始点为(5，曲线如图3.1.11所示。

0.1)的等高线寻优轨迹图 图3.1.6 起始点为(0.6，T

0.1)的函数值变化曲线 图3.1.7 起始点为(0.6，T

T图3.1.8 起始点为(2,2)的等高线寻优轨迹图

2)的函数值变化曲线 图3.1.9 起始点为(2，T

图3.1.10 起始点为(5,5)的等高线寻优轨迹图

T

5)的函数值变化曲线 图3.1.11 起始点为(5，T根据以上不同起始点的等高线寻优轨迹图和函数值变化曲线，可看出，对Rosenbrock函数（N=2）求解极小值时，在起始点靠近全局最优解的时候或是起始点距离全局最优解较远的情况下，LM算法的收敛速度大部分情况下是比BFGS算法快的，但是当收敛到一定情况下时，LM算法收敛速度减慢，学习率变小，而BFGS算法的学习率却是波动较小的。

表3.1.1 LM算法和BFGS算法求解Rosenbrock函数（N=2）最小值性能比较

起始点

LM迭代次数 BFGS迭代次数

LM误差

BFGS误差

LM运行时间 BFGS运行时间

(0，0)T (0.6，0.1)T (0.4，1)T (2,2)(5,5)T17 15 15 15 17 20

21 20 13 24 47 67

9.6977×10-19 4.1686×10-15 1.2860×10-18

1.190×10-12

2.9078 s 3.1835 s 2.5712 s 2.3726 s 2.84 s 3.2620 s

4.1040 s 3.9293 s 2.8510 s 5.01 s 6.3435 s 5.9763 s

1.2180×10-18 1.3221×10-13 8.9131×10-18 2.1171×10-15 1.3383×10-19 1.3341×10-13 2.3622×10-19 3.1778×10-17

T(10,10)T

表3.1.2 起始点为(0,0)的不同维度Rosenbrock函数求解对比

N

LM迭代次数 BFGS迭代次数

LM误差

BFGS误差

LM运行时间

BFGS运行时间

T2 3 4 5 6 7 8 9 10

17 16 17 18 19 20 22 23 24

21 26 28 34 39 42 47 50 55

9.6977×10-19 4.1686×10-15 8.9500×10-17 4.34×10-14 5.7859×10-17 6.7678×10-13 5.2980×10-17 2.6506×10-15 5.3814×10-17 1.9618×10-13 5.6127×10-17 1.9924×10-14 4.3400×10-17 4.4370×10-13 4.5391×10-17 4.5391×10-17 4.7539×10-17 2.8375×10-12

2.9078 s 5.6207 s 6.8435 s 8.7447 s 8.7363 s 14.8170 s 12.7125 s 20.3751 s 22.6591 s

4.1040 s 9.7260 s 9.3070 s 22.2176 s 22.238 s 31.7683 s 25.9286 s 42.9034 s 39.0883 s

通过以上的对比，用LM算法和BFGS算求解Rosenbrock函数（N=2）最小值时，大部分情况下LM算法运行的速度是比BFGS算法快的，并且LM算法的收敛速度也更快一些，需要的迭代次数也比BFGS算法少，最终得到的误差比BFGS算小很多。

针对二元的Rosenbrock函数求解最小值，LM算法在运行速度、收敛速度、误差、迭代次数上是比BFGS算法适合的。

0)T运取式（3.1.1）不同的N即不同维度的Rosenbrock函数，从同一个起始点(0，行LM算法和BFGS算法，得到如表3.1.2不同的比较。

两个算法对不同维度的Rosenbrock函数求解最小值，通过对比结果可知，LM算法计算的精度比BFGS算法高，运算的速度也更快，迭代次数少。目前还不能就此得出LM算法比BFGS算法更优越的结论，下面要用LM算法和BFGS算法求解不同函数的极值，再进行针对不同函数的对比。

3.2 不同函数的极值求解对比

选择(0,3)T作为起始点，用这两个算法对下式函数求解其极小值：

42 f 1( x )  ( x 1  2)  ( x1  2 x 2 ) ( 3.2.1 )

该函数在(2,1)T只有一个全局最优解，其值为0，LM算法和BFGS算法在函数等高线上的寻优轨迹图3.2.1和函数值变化曲线图3.2.2为：

图 3.2.1 求f1(x)最优解的等高线寻优轨迹图

由图3.2.1和图3.2.2可知，LM算法的收敛速度是更快的，从等高线寻优轨迹图中可看出，在起始点的时候函数值是较大的，而LM算法在前面的几次迭代中函数值迅速的下降到了较小的值，BFGS算法前面几次迭代中下降的速度是没有LM算法快的，也就是说LM算法收敛得比较快，但是当函数减小到一定值的时候，LM算法的

下降变得非常慢，使得它最终的迭代次数超过了BFGS算法的。从表3.2.2中可看出，两个算法得到的f1(x)的极小值中，BFGS算法得到的值是更小的且更接近目标值0，虽然相差不大，但是说明LM算法并不是对所有的函数求解都有更高的精度，其次LM算法的运行时间和迭代次数这次计算中都超过了BFGS算法。

图 3.2.2 求解f1(x)极小值的函数变化曲线图

选取起始点坐标为(1,1)T，用这两个算法求解De Jong函数的极小值。De Jong函数在(3,1)T处有一个全局最优解0。其函数表达式为：

f x )  x 1  2 x 2 (2 ( 3.2.2 ) 两个算法对其求解的等高线寻优轨迹图和函数值变化曲线图如下所示：

44

图3.2.3 求解De Jong函数的等高线寻优轨迹图

从求解De Jong函数的图3.2.3和图3.2.4这两个比较图，可得到类似于求解f1(x)函数的结果，也就是LM算法的收敛速度是比BFGS算法快的，但是当函数值减小到一定程度后，LM算法变得比BFGS算法慢。从表3.2.2可知，这两个算法对De Jong函数的求解结果中，LM算法比BFGS算法的误差略小，但是相差不大，而LM算法的迭代次数比BFGS算法多一点相差也不算大。

图3.2.4 求解De Jong函数时的函数值变化曲线

选取起始点为(2.1,1)T，运用这两个算法对Beale函数求解极小值，Beale函数在

(3,0.5)T有一个全局最优解0，其函数表达式为：

f 3 (  x 1  x 2 2 2 3 2 ( 3.2.3 ) x ) (1.51x2)(2.25x1x1x2)(2.625x1x1x2)这两个算法对Beale函数求解极值的等高线寻优轨迹图和函数值变化曲线如下所示：

图3.2.5 求解Beale函数的等高线寻优轨迹图

对于Beale函数的求解，从图3.2.5和图3.2.6中可看出两个算法中，BFGS算法这次收敛得稍微快一点，但并不是很明显，迭代次数也更少一点，相差也不大，说明对于Beale函数这两个算法的求解能力差别不太大，但LM算法这次依旧是误差更小一点。

图3.2.6 求解Beale函数时的函数值变化曲线

选取起始点为(0.6,2)T，运用这两个算法求解Booth’s函数的极小值， Booth’s函数在(1,3)T处有一个全局最优解0，其函数表达式为：

f4 ( x )  ( x 1 2 x 2  7)  (2 x 1  x 2  5) ( 3.2.4 ) 这两个算法对Beale函数求解极值的等高线寻优轨迹图和函数值变化曲线如下所示：

图3.2.7 求解Booth’s函数的等高线寻优轨迹图

22从图3.2.7和图3.2.8中可看出，BFGS算法与LM算法的收敛速度是几乎一样的，

但是BFGS算法的最终迭代次数比LM算法少，而更多的迭代次数也使得LM算法最终得到的结果误差比BFGS算法小。

图3.2.8 求解Booth’s函数时的函数值变化曲线

下面要运用这两个算法求解Powell’s Quadratic函数的极小值，作为又一个经典的优化测试函数，Powell’s Quadratic函数在(0,0,0,0)T处有一个全局最优解0，其函数表达式如下：

0 f 5 ( x )  1 2 1 x 1  5 ( x 3 x 4 ) ( x 2  2 x 3 )  1 ( x 1  x 4 ) ( 3.2.5 )

由于该函数为函数，所以只绘制了两个算法求解极值的函数值变化曲线图，如下所示：

图3.2.9 求解Powell’s Quadratic函数时的函数值变化曲线

2244

表3.2.1 两个算法求解不同函数极小值时的迭代次数对比

目标函数

LM算法/次 BFGS算法/次

Rosenbrock De Jong Beale Booth's Powell’s Quadratic

59 17 59 15 11 65

48 21 13 6 63

表3.2.2 两个算求解不同函数极小值的误差对比

目标函数

Rosenbrock De Jong Beale Booth's Powell’s Quadratic

LM算法 2.1855×10-22 9.6977×10-19 2.0980×10-22 4.9849×10-17 6.8371×10-18 1.4580×10-23

BFGS算法 6.3902×10-23 4.1686×10-15 3.4835×10-19 2.1005×10-15 8.38×10-14 9.93×10-20

从以上几个函数求解极值的对比，可看出其实LM算法和BFGS算法的求解差别不大，只不过在大部分情况下LM算法的求解误差是比BFGS算法小的。并且从等高线的寻优轨迹图中可以总结出，LM算法在求解的过程中，前期的收敛是较BFGS算法稍快的，特别是对于等高线图类似于椭圆的函数。而当函数值下降到一定程度时，LM算法的步伐放慢，BFGS算法的迭代次数相对比LM算法少，但是最终结束迭代，LM算法得到误差更小的结果。针对LM算法在大部分情况下误差更小并且收敛速度较快的结果，在下一章将进行基于LM算法的前向神经网络的研究，并运用于实际二分类问题。

第四章 基于LM算法的前向神经网络的学习

4.1 前向神经网络

y1

x1xn图4.1 含一个隐层的3层前向神经网络模型

x2y2y3如图4.1所示的网络模型是前向神经网络中最常用的结构，即只含有一个隐层的三层前向神经网络。前向神经网络算法主要分为两个部分：首先是，前向传播计算，从输入层通过隐层传输到输出层；然后是，误差反向传播计算，从输出层反馈到隐层最后到输入层，也就是先调整隐层到输出层的权值和偏置，再调整输入层到隐层的权值和偏置[17]。

每一个节点的细节情况如图4.2所示,这也叫作神经元的M-P模型。

图4.1网络结构有n个输入，隐层含有m个神经元，有l个输出。输入为

x1,x2,,xn；从输入层到隐层有m个偏置，分别为1，2，，m，输入层到隐层的

（1）权值为wi,j，隐层的输入为： I式中i=1,2,...,n， j=1,2,...,m。

（ j1 ）

w i ,j x i   j ( 4.1.1 )  （1）i1nx1w1fx2w2xnwn图4.2 神经元的M-P模型

一般激活函数选择sigmod型函数，形如：

1 ( 4.1.2 )

f(x)1ex将式（4.1.1）作为输入带入式（4.1.2）可得到隐层的输出：

O (1)  f ( 1 ( 4.1.3 ) I)jj式中j=1,2,...,m。

1eIj，l，从隐层到输出层的权值为从隐层到输出层有l个偏置，分别为1，2，(2)wa,b（a=1,2,..,m; b=1,2,...,l）。

(2) I b (2)  O j w a ,b   b ( 4.1.4 )

a1m

式（4.1.4）作为输出层激活函数的输入，得到最终输出为：

1 O (2)  f ( I ) ( 4.1.5 ) bb1e(-Ib)

式（4.1.4）和式（4.1.5）中b=1,2,...,l

可得到前向传播计算后网络的误差为：

eiyiOi(2)式中i=1,2,,...,l

一般常用误差的方差和函数作为优化的目标，如下：

( 4.1.6 )

pl1 E    e 2 ( 4.1.7 ) miniw,2j1i1而寻求它得到最小值时的权值和偏置就是前向神经网络的任务。对于传统前向神经网络算法，是按照Widrow-Hoff准则进行误差反向传播计算[8]。本论文将用LM算法对误差函数进行优化，并将优化的前向神经网络运用于二分类问题，通过实验结果分析性能。

4.2 基于LM算法的前向神经网络学习

根据上述的LM算法，将式（4.1.7）作为优化目标函数，那么计算式（2.1.14）中矩阵G的时候需要用到的误差向量为：

TTF(x)e [... e 1,1 , e 2,1 e l e 1,2 , e 2,2 ... e l, p ] ( 4.2.1 ) ,1,P为样本个数， 为输出个数。

l自变量是权值和偏置，所以自变量向量为：

w 2 ...w l ] x  [ x x 2 ... x N ]  [ 1,1 , w 1,2 ... w n , 1 ,  m ,... m , ( 4.2.2 ) 1,m ,l,...T11111122N n  m  m  m  l  l ，n为输入个数，m为隐层神经元个数，l 为输出个数。

误差函数对隐层到输出层权值和偏置的偏导为：

el,p(2)(2)(1)O(1O)Ojji  w 2 ( 4.2.3 )

i,je l, p  O j(2) (1  O j (2) ) ( 4.2.4 )

2j i =1,2...m ; j =1,2... l 。

误差函数对输入层到隐层的权值和偏置的偏导为：

el,p(2)(2)2(1)(1)OO 1  j (1  O j ) w i ,j O i (1  i ) x h ( 4.2.5 )

wh,ip (2)  e l , (1  O (2) ) w 2 O (1) O (1) ( 4.2.6 ) O(1jji,jii)1ih=1,2...,n; l 为输出个数，p为样本个数，m为隐层神经元个数，n为输入个数。

对误差向量里的所有元素进行式（4.2.2）里所有元素求偏导，并按一定的顺序排列后就得到了三层前向神经网络的雅克比矩阵为：

误差函数的梯度为：

e1,1w11,1e2,11w1,1el,1J(x)1w1,1  e1,21w1,1el,p1w1,1e1,11w1,2e1,1w1n,me2,1w1n,mel,1w1n,me1,111e2,111el,1111,211e2,11w1,2el,1w11,2  e e  e

w1,211,2w1,21n,mel,p1w1,2el,pw1n,mel,p11e1,1l2e2,1l2el,1l2  e  1,2l2el,pl2( 4.2.3 )

Tg) ( 4.2.4 ) ( x )  J ( x ) e ( x

4.3 在模式分类中的应用

本节运用从UCI上下载的数据集训练和测试LM算改进的前向神经网络，首先选择的数据集是来自UCI上的冷冻治疗结果数据集Cryotherapy，该数据集包含了使用冷冻疗法的90名患者的疣治疗结果信息。下面使用该数据集进行冷冻治疗结果诊断，每个患者有6个特征值和1类标签（是否治疗成功），网络中有10个隐层神经元。

图 4.3.1 冷冻治疗诊断误差曲线图

将该数据集用来训练LM算法改进的前向神经网络，可达到诊断正确率为85.1%，最终误差为0.0016515。

接下来使用的是来自新竹市输血服务中心的数据集，包含748份捐赠者数据，根据每个捐赠者的4个特征值判断2007年3月该捐赠者是否进行了献血（1类标签），网络中有10个隐层神经元。

将该数据集用来训练LM算法改进的前向神经网络，可达到判断正确率为75.5%，最终误差为0.081，训练误差变化如图4.3.2所示。

图 4.3.2 输血服务中心献血判断误差曲线

本次实验还使用了经典的垃圾邮件数据集，里面包含4601个邮件信息，每个邮件有57个特征值和一个标签（是否为垃圾邮件），网络有10个隐层神经元，通过训练后，垃圾邮件判别正确率达到为.0%，最终误差为0.047，训练误差变化如图4.3.3所示。

图4.3.3 垃圾邮件判别误差曲线

根据这三个数据集的训练结果，LM算法改进的前向神经网络是可行有效的，在前50次的迭代中收敛速度是极快的，最终的正确率也都能满足应用的要求。其次可看出，隐层神经元个数一样时，样本特征值和样本数量越多，最终的训练效果越好，正确率越高。

4.3.1 参数对分类效果的影响

针对冷冻治疗诊断的数据集取数量不同的隐层神经元进行训练，最终得到如下结果：

图 4.3.4 误差与隐层神经元个数的关系曲线

图 4.3.5 正确率与隐层神经元个数的关系曲线

根据上图4.3.4和图4.3.5可知，对于冷冻治疗的数据集，训练结果受到隐层神经元个数的影响，除去可能由于偶然性造成的异常数据如隐层神经元为40个的时候，可得到隐层神经元个数超过25个后正确率以及最终误差都有所上升。从图4.3.6可观察到，隐层神经元个数不同误差收敛速度也不一样，说明隐层神经元个数对收敛速度有影响，其次隐层神经元个数对治疗诊断的误差变化范围从0到0.13不等。

图4.3.6 不同隐层神经元数量下的误差变化曲线

针对输血服务中心献血判断的数据集取数量不同的隐层神经元进行训练，最终得到如下结果：

图 4.3.7 误差与隐层神经元个数的关系曲线

根据图4.3.7和图4.3.8可观察到，隐层神经元个数对训练效果存在一定影响，当隐层神经元个数为20的时候可得到几次实验中最好的训练效果，不排除实验的偶然性，比如最终误差在隐层神经元个数为25个时出现峰值，但是正确率也在这个时候出现峰值。再从图4.3.8可见，误差变化集中在0.08附近，其次隐层神经元数量对收敛速度有一定影响，但其影响不如上一个数据集明显。

图 4.3.8 误差与隐层神经元个数的关系曲线

图4.3.9 不同隐层神经元数量下的误差变化曲线

针对垃圾邮件判断的数据集取数量不同的隐层神经元进行训练，最终得到如图4.3.10、图4.3.11和图4.3.12的结果。从图中我们可以明显看到除了隐层神经元为25个时的异常点外，当隐层神经元个数增加到一定数量的时候，最终误差以及测试正确率都下降了，数量大于35个后训练效果变差很快。随着隐层神经元个数的变化，从图4.3.12可看出误差收敛速度变化较大，其次误差变化在0.05到0.12。

根据本节的测试结果，隐层神经元个数对训练效果、收敛速度有很大影响，排除一些异常的情况，当隐层神经元个数太少或太多都会得出较差的训练结果。其次，不同的数据集，神经元个数对其影响程度不一样，所以针对不同数据集的，根据它的特征值个数甚至可能样本个数的不同选取合适的隐层神经元个数是十分关键的。

图 4.3.10 误差与隐层神经元个数的关系曲线

图 4.3.11 误差与隐层神经元个数的关系曲线

图4.3.12 不同隐层神经元数量下的误差变化曲线

结论

数值优化算法对机器学习领域有着不可替代的重要地位，传统的优化算法在实际应用中存在许多局限性，为朝着更智能、更高效、更快速、更节能的方向前进，改进优化算法是机器学习领域一直不断努力的方向。

本课题是根据目前优化算法的研究现状而提出对两个二阶优化算法：LM算法和BFGS算法进行性能对比分析。基于对两个算法基础原理的研究，运用这两个算法进行多个函数求极值问题的分析，做出统计后得出在大部分情况下LM算法在总体性能上稍微优于BFGS算法，但这并不能否定BFGS算法的性能。通过更仔细的分析，可发现LM算法在运行的前期收敛速度是很快的，大部分情况下比BFGS算法快，但是最终LM算法的迭代次数却大于BFGS算法。这是由于当函数值下降到一定程度接近极小值的时候，寻找到的点到相对平坦的区域，为保证得到正确的极小值，LM算法变得十分“谨慎”从而缩短学习率。而BFGS算法却不会有这种“忧虑”，只要保证满足拟牛顿条件以及Bk矩阵正定，BFGS修正算法将保证方向一直是正确的。所以大部分情况下最后BFGS算法迭代次数少于LM算法。

LM算法在大部分情况下得到误差更小的结果，所以在后期设计了基于LM的前向神经网络算法，将其应用于二分类的实际应用中，通过实验证明该算法是可行有效的，并且效果可观，垃圾邮件分类正确率最高达到96%。在原有算法基础上改变隐层神经元数量，训练的效果受到不同程度的影响，但过多或过少的隐层神经元个数都会大大降低训练效果。

此外本人也在基于BFGS的前向神经网络上做了努力，最终没有得到理想的效果，今后还会在这方面做更多的功课，将基于BFGS的前向神经网络算法继续完善。BFGS算法在本实验中使用的步长搜索算法是Armijo算法，选择这个算法是因为它简单实用，但在学习研究的时候，发现大部分BFGS算法运用的搜索算法是Wolf-Powell算法，这能够使得BFGS算法有更好的收敛性，在今后的学习中会努力将BFGS算法完善得更好尝试使用更好的步长搜索算法。

致谢

本次毕业设计能够顺利完成，要感谢黄鹤老师以及同学们提供的莫大帮助。从刚开始对算法的原理充满困惑，到后来调试程序中出现的种种难题，再到最后对论文撰写的迷茫，黄鹤老师一直十分耐心的指导我，给我提出许多有益的改善性意见，让我一次又一次取得突破，直到最终完成设计和论文。每一次在课题的探讨中我总能在老师深入浅出的讲解中得到新思路和启发，他以严谨的治学态度以及广博的学识一次次使我折服。总之特别感谢黄鹤老师一直以来对我的帮助。还要深深的感谢身边同学的鼓励和支持，让我在遇到难题的时候坚持下来，陪我一起度过难关。同时，感谢在本次毕业设计中与我合作交流的同学们,我们一起在实验室共同突破一个又一个难题最终顺利完成了各自的课题。

此外，我还要感谢我用到的参考文献的所有作者，读了他们的文献让我收获良多，对本课题有了更深入的了解。感谢在我成长过程中给予过我帮助的所有人，没有综合技能的一次次提升，就不会有足够的能力和坚定的信心来进行本次毕业设计。感恩之余，诚恳的请各位老师、专家对本论文中的欠妥的地方提出修改意见，今后我便努力朝着更好的方向发展。

最后，谨以此衷心感谢老师们百忙之中抽出时间评阅我的毕业设计和论文。

参考文献

[1] 李南星, 盛益强, 倪宏. 基于LM算法的MLP模型及其应用[J]. 网络新媒体技

术, 2018, 7(01):59-63.

[2] Ebadzadeh M M, Salimi-Badr A. CFNN: Correlated fuzzy neural network[J].

Neurocomputing, 2015, 148(1):430-444.

[3] 权凌霄, 郭海鑫, 盛世伟,李雷. 采用“GA+LM”优化BP神经网络的电液伺服阀故

障诊断[J]. 中国机械工程, 2018, 29(05):505-510.

[4] 王良诣, 姜礼杰, 王勇. 基于遗传拟牛顿混合算法的四杆机构优化[J]. 合肥工业大

学学报(自然科学版), 2018, 41(02):150-153

[5] Andrei N. A double parameter scaled BFGS method for unconstrained optimization[J].

Journal of Computational & Applied Mathematics, 2018, 332.

[6] 李董辉, 童小娇, 万中. 数值最优化算法与理论[M]. 科学出版社, 2010, 24-59 [7] 马昌凤. 最优化方法及其Matlab程序设计[M]. 科学出版社, 2010, 22-95

[8] M. T. Hagan, H. B. Demuth and M. Beale, Neural Network Design[M]. Boston, PWS

Publishing Co, 1996

[9] Bottou L, Curtis F E, Nocedal J. Optimization Methods for Large-Scale Machine

Learning[J]. 2016.

[10] Cherrak O, Ghennioui H, Abarkan E, et al. Levenberg-Marquardt Algorithm[J].

Tutoral on Lm Algorithm, 2013, 11(1):101-110.

[11] Bertsekas D P. Nonlinear Programming[J]. Journal of the Operational Research

Society, 1997, 48(3):334-334.

[12] Berahas A S, Nocedal J, Takáč M. A Multi-Batch L-BFGS Method for Machine

Learning[J]. 2016.

[13] Xia J H, Rusli, Kumta A S. Feedforward Neural Network Trained by BFGS Algorithm

for Modeling Plasma Etching of Silicon Carbide[J]. IEEE Transactions on Plasma Science, 2010, 38(2):142-148.

[14] Wilamowski B M, Yu H. Improved Computation for Levenberg–Marquardt

Training[J]. IEEE Transactions on Neural Networks, 2010, 21(6):930-7.

[15] 袁亚湘, 孙文瑜. 最优化理论与方法[M]. 科学出版社, 1997.

[16] 龚纯, 王正林. 精通MATLAB优化计算（第4版）[M]. 电子工业出版社. 2016.

[17] Ren Y Y, Xu Y X, Bao J. The Study of Learning Algorithm the BP Neural Network

Based on Extended BFGS Method[C]// International Conference on Computer, Mechatronics, Control and Electronic Engineering. IEEE, 2010:208-211.