我的书签
添加书签
移除书签七、共轭梯度法
7.1 最速下降法
最速下降法是梯度下降法的一个特例：在每次梯度下降时，学习率的选择是使得当前函数值下降最快的那个学习率。
梯度下降法仅仅指明：负梯度的方向是使得代价函数值下降的方向。它并没有说明沿着负梯度的方向推进多少步长。
最速下降法通过显式对学习率建模，求解沿着负梯度的方向需要推进多少步长。
在最速下降法中，假设上一次搜索方向是
，当前搜索方向是 。可以证明有：即：前后两次搜索的方向是正交的。
证明过程：
已知
的梯度 ，根据 ，则有：在最速下降法中，前进过程是锯齿形的。在某种意义上，这意味着消除了之前的线性搜索方向上取得的进展：
如果前一次搜索已经找出了某个方向上的最小值，最速下降法不会保持这一方向。
7.2 共轭梯度法
- 共轭：给定一个正定矩阵 ，如果非零向量 满足： ，则称向量 关于 共轭。
- 如果 为单位矩阵，则有 。即：向量共轭是向量点积为0的推广。
7.2.1 共轭梯度原理
对于线性空间
，如果能找到 个向量 ，且它们满足： ，则可以证明这一组向量是线性无关的。此时这一组向量可以作为线性空间的一组基向量，空间中任意向量
都可以用这组向量表示： 。对于二次函数极值问题（其中
为正定矩阵）： ，将 代入上式，令 ：根据
，有：现在变量
已经被分开，可以分别优化。于是求解第
项的最小值：直接求导即可得到：
最优解为：
上述最优解可以这样理解：
- 目标函数沿着方向 （即：）求解极小值，得到 。
- 总和所有的 个方向求得的极小值，得到 。
现在的问题是：
个关于 共轭的向量组 未知。- 目标函数沿着方向
7.2.2 共轭梯度搜索
共轭梯度法通过迭代来搜索关于
共轭的向量组 。令梯度
，由于 ，则有：假设
为对称的正定矩阵，则有： 。因此有： 。任取一个初始点
。如果
，则停止计算。因为此时 就是极值点。否则，令
，即： 沿着点 的梯度方向。沿着
方向搜索： ，使得沿着这个方向，目标函数下降最多。解得：
由于
，因此有：
选择第二个迭代点：
注意：这里有
，但是不保证后面的 。构建下一个搜索方向，使得
与 关于 共轭。令：
，代入 ，有：同理：得到
时，计算梯度 ，同时用 和 来构建下一个搜索方向：得到：
.
7.2.3 共轭梯度算法
共轭梯度法的搜索方向
会保持前一次线性搜索方向上 取得的进展：其中
的大小控制了：要保留多大比例的上一次搜索方向。在实际应用中，目标函数往往是高于二次的函数。此时为非线性共轭梯度，
就是海森矩阵 。直接计算
也需要计算海森矩阵的逆矩阵，比较复杂。有两个计算 的流行方法（不需要计算海森矩阵的逆矩阵）：这里不再保证
和 关于 是共轭的。Fletcher-Reeves：Polak_Ribiere：
目标函数在高于二次的函数时，往往可能存在局部极值。此时共轭梯度法不能在
维空间内依靠 步搜索到达极值点。此时需要重启共轭梯度法，继续迭代，以完成搜索极值点的工作。
共轭梯度法：
输入：
- 初始参数
- 包含 个样本的训练集
- 初始参数
算法步骤：
初始化：
迭代，直到到达停止条件。迭代步骤为：
计算梯度：
计算
如果是非线性共轭梯度：则可以以一定的频率重置
为零（如每当 为 5 的倍数时）。计算搜索方向：
执行线性搜索：
在前面推导过程中，并没有出现这一步。这是因为：在非线性共轭梯度下，以及修改的
的情况下，不再满足 和 关于 是共轭的。对于真正的二次函数：存在
的解析解，无需显式搜索。- 应用更新：
- 应用更新：
7.2.4 共轭梯度算法性质
神经网络的目标函数比二次函数复杂得多，但是共轭梯度法在这种情况下仍然适用。此时非线性共轭梯度算法会偶尔采取一些重置操作（重置
为零）。尽管共轭梯度算法是批方法（需要所有的样本来计算梯度），目前也开发出了
mini-batch版本。理论上，对于二次函数的目标函数，需要迭代
步， 为参数的个数。每一步中都需要计算梯度。在神经网络中，这样有两个问题：
- 当参数的数量 巨大时，迭代的量非常大，而且难以并行（后面的迭代依赖前面的迭代），计算量非常庞大。
- 当样本的数量巨大时，每次迭代中的梯度计算的计算量非常庞大。
- 当参数的数量
