【十分钟 机器学习 系列课程】 讲义（三十九）：最大熵模型之拟牛顿法的DFP和BFGS算法

欢迎回来。上期我们给大家介绍了最大熵模型中的「拟牛顿法的基本原理」【十分钟 机器学习 系列课程】 讲义（三十八）：最大熵模型之拟牛顿法原理，里面提到了「拟牛顿法」的精髓在于找到求解海森矩阵的逆的替代品，也就意味着要满足拟牛顿法的条件，写成两种形式是：

❝

• 条件一：
• 条件二：

❞

其中 和 ， ， 就是海森矩阵啦。

这两个式子就是「拟牛顿法的条件」！每个条件都可以得到一个算法。

这期我们就要讲讲拟牛顿法中的「DFP算法」和「BFGS算法」。

壹  什么是DFP算法？

1.DFP算法的推导

DFP算法是三个人名的首字母，分别对应的是 Davidon、Fletcher、Powell，这个算法就是由他们三人得到的，所以这个算法名字是不是很好记？

这里的DFP算法其实就是「条件一」推导而来的。接着我们来看看到底怎么用它来进行迭代。

❝

还记得「拟牛顿法」的精髓是什么吗？【十分钟 机器学习 系列课程】 讲义（三十八）：最大熵模型之拟牛顿法原理

❞

没错，正是要「找到求解海森矩阵的逆的替代品」，这里我们不妨就将它写成：

好啦，接着，咱们就开启「推导之旅」。

Step 1  标记出第 的迭代矩阵

这里的 和 就是两个附加项，它们的作用实际就代表了 和 之间的差值 ，只不过就是分解为两个值来表示。

Step 2 找到相应的 和

那么该怎么找到这两个值呢？这还得用到条件中的式子。咱们将 代入式中，可以得到：

注意哦，之所以这么代入，就是为了「满足拟牛顿法的条件」。

接着，要做一个简单的小变换，咱们可以令:

❝

❞

在上期【十分钟 机器学习 系列课程】 讲义（三十八）：最大熵模型之拟牛顿法原理，我们说到「海森矩阵」和它的逆矩阵一定是对称且正定的矩阵，那么就意味着，这里的 和 也是对称的。

注意哦，这里的 和 是向量，我们不能直接做除法，也就是说，

于是为了求出让 成立的 ，我们利用向量的内积构造一个矩阵 ，

很容易根据矩阵相乘的结合律得到，

此时， 是一个数，所以分子分母可以约掉啦，因此 就是我们想要找到的一个满足条件的矩阵。

举个例子：

❝

假设：此时对于 而言分别有 个维度，当 时，那么意味着计算出的 便是一个 的矩阵，可以写成：

❞

同理，对应的 自然也是一个 的矩阵，而 则是 的矩阵。

这样，代入到

同理，咱们也可以构造出满足条件的矩阵 ：

各位小伙伴可以根据结合律验证一下哦。

Step 3 写成 的迭代公式

搞明白了DFP算法的推导过程，接着我们就来看看它的迭代思路吧。

2.DFP算法的解读

首先，还是要明确输入和输出的变量。

对于这个迭代过程而言，和之前的迭代原理相同，还需要一个精度来作为停止条件。

「输入」：目标函数 ，梯度 ，计算精度

「输出」： 的极小值点

迭代过程五步走：

Step1 选取初始值 以及初始正定对称矩阵 ，令

先来代入一个初值，试试吧！

Step2 计算 ，如果 ，停止迭代，令 ，输出结果。否则，转（3）继续迭代。

这一步很简单，就是来求一个梯度，计算后看看计算结果是否满足精度，如果满足，那么恭喜你，算法就到此结束咯。

Step3 置 ,利用一维搜索公式得到最优步长

如果满足不了，接着就要用到最速梯度下降法的思路，找到往哪走是下降最快的步长，遍历搜索所有符合的 值，谁的  最小，就选它作为最优步长，对这个公式印象还不深的小伙伴，电梯送你回去瞅一眼【十分钟 机器学习 系列课程】 讲义（三十七）：最大熵模型之最速梯度下降法。

Step4 通过迭代公式更新

接着就可以把由这个最优步长生成的 值作为新一轮的迭代值。

Step5 计算 ，如果 ，停止迭代，令 ，输出结果，否则，令 ，计算

DFP的算法「关键点」来了，继续对 迭代值求偏导，判断是不是满足精度，要是不满足，「下一步就得用到咱们在上面推导出的豪华公式 值来代入计算」，用在下一个 中。

好啦，这就是DFP算法的解读。接着，我就继续看看用另一个拟牛顿法条件生成的BFGS算法吧。

贰 什么是BFGS算法？

1.BFGS算法的推导

这个算法和DFP一样，也是由4个人一起创造的，分别是 Broyden、Fletcher、Goldfarb和Shanno。同DFP的算法一样，这里我们用到的是拟牛顿法中的「条件二」推导而来的。

先把目光锁定在条件二上：

同DFP算法不同，这里我们不再是找海森矩阵的逆的替代品，而是「直接是海森矩阵的替代品」，写成：

接着就开启「推导之旅」吧~

Step 1  标记出第 的迭代矩阵

这里的 和 和DFP算法一样，也是两个附加项，代表了 和 之间的差值。

Step 2 找到相应的 和

那么该怎么找到这两个差值呢？这还得用到条件二中的式子。咱们将 代入式中，可以得到：

接着，我们不妨令：

这里还是为了计算简便，对 和 进行改造，可以得到满足条件的矩阵：

因为初始的矩阵 是正定的，因此迭代过程中的每个矩阵 都是正定的。

Step 3 写成 的迭代公式

好啦，这个豪华公式先放在这里，一会儿再用。

2.BFGS算法的解读

和DFP算法一样，对应的输入输出都不变，并且迭代的思路都一样，只不过在求解最优步长和 处有所不同，接着，就一起看看吧！

「输入」：目标函数 ，梯度 ，计算精度

「输出」： 的极小值点

迭代过程五步走：

Step1 选取初始值 以及初始正定对称矩阵 ，令

还是先来代入一个初值。

Step2 计算 ，如果 ，停止迭代，令 ，输出结果。否则，转（3）继续迭代。

这一步很简单，就是来求一个梯度，计算后看看计算结果是否满足精度，如果满足，那么恭喜你，算法就到此结束咯。

Step3 置 ,求出 ，利用一维搜索公式得到最优步长

如果第二步满足不了停止条件，接着就要用到「最速梯度下降法」的思路，找到往哪走是下降最快的步长，遍历搜索所有符合的 值，谁的  最小，就选它作为最优步长。

Step4 通过迭代公式更新

接着就可以把由这个最优步长生成的 值作为新一轮的迭代值。

Step5 计算 ，如果 ，停止迭代，令 ，输出结果，否则，令 ，计算

按照这个思路去迭代，这就是BFGS算法的解读。

叁 Broyden算法

这个Broyden算法实际上就是前两个算法得出的，他们都是拟牛顿法的两个条件，那么如果我们想让两个方法放在一个公式中呢？

很简单，这里的思路有点像「二项分布的公式」，我们可以先把BFGS算法中的 转为：

当然为了标记两个矩阵的不同，我们可以分别加一个算法的上角标，写成： 和 。

整理一下就得到了这两个算法线性组合：

当 时，采用BFGS算法。

当 时，采用DFP算法。

当然 的范围可以为：

这样就得到了类拟牛顿法，称为「Broyden算法」。

好啦，本期的拟牛顿法DFP算法和BFGS算法就介绍到这里啦，感兴趣的小伙伴可以点击视频链接继续学习，更新不易，请喜欢这篇讲义的你记得「转发+点赞+在看」哦。