[AI随记

NoiseFloor · 发表于 2022-3-14 11:18

注：此文在机器学习方面属于入门性的文章，虽是一篇机器学习方向的随记，但其中方法，思路并非仅限于机器学习相关方向。也不要求对于机器学习相关领域有太多的基础和理解。有一定数学基础，涉及系统参数优化方法的，都可以参考之~

这两天看Coursera上面Hinton的神经网络课程，第八周有讲到一个Hessian Free的算法，可以比普通的算法更高效地收敛，鉴于Hinton课程一贯的粗犷风格，决定额外写一篇随记来详细解释这个算法的来龙去脉。
鄙人基础薄弱，智商堪忧，第一次发文，若有不明确不准确不正确之处，欢迎探讨质疑与指点
本文的主要框架和大量参考来自于Andrew Gibiansky的博客，行文风格和语言组织吸取了@曹逸君的建议。
转载请通知本人并注明出处。
（吐槽一下Coursera，讲述Hessian Free算法Lecture8a因为被标记成了Optional，直接不出现在视频列表里了，害我对着讲义PPT在Video-free的状态下啃了老半天）
-------------------------------------------------并不华丽的分割线----------------------------------------------
▍0. 序

在许多复杂系统的优化过程中，都无法或难以对其参数进行一次性地进行求解，而需要通过迭代逼近的方式来寻找最优或局部最优的参数集。
比如有一类机器学习系统可以粗略地进行如下的解释：

如果存在一系列 “条件 - 结果” 对（比如为向量<身高，体重，性别，....>，为这个人的寿命），那么这个机器学习系统要做的是，在审阅了足够多的后，给定一个新的输入 $x_{new}$ ，尽可能预测出一个接近于真实 $r_{new}$ 值的结果 $y_{new}$

此时将系统视作一个函数 $y = F(x)$ ，其中 $F$ 可能包含一系列参数 $a,b,c....$ （比如 $y = a x^2+bx+c$ ），对于每个输入数据 $x_{0}$ ，系统给出一个预测值 $y_{0}$ 。

其实也可以视作存在 $F = G(a,b,c,...)$ 使得 $y = G(a,b,c,...)(x) = F(x)$ ，或称 $y = G(p)(x) = F(x)$ ，其中p为向量 $\langle a,b,c....\rangle$

额外的，对于已知的，我们根据系统的实际表现 $\langle x,y \rangle$ 设计一个函数作为代价函数，使得随着 $y$ 和的差距变大而变大。那么如果我们能够找到一组 $a,b,c...$ 使得c在各种下尽量小，那么这样的参数就比较合适于这样的系统。

这样我们就把系统的参数优化问题，转换成了寻找函数全局/局部最小值的问题

寻找这组参数的方法有很多，本文的目的是从最基础的梯度下降法出发，一步步推导到Hessian Free算法。
▍1. 梯度下降法（Gradient Descent）回顾

考虑代价函数，且 $y = F(x) = G(p)(x)$ ，当 $x,r$ 已知时（即输入数据与预期输出已知，记得我们要求出的是，使得对于已知的数据对，取到尽量小的值），可以看做关于的函数。

我们知道，对于函数 $C_{xr} (p)$ ，令 $p^{(i)}$ 表示向量的第个分量，我们只要求得其在各个分量上的偏导数 $\frac{\partial C_{xr}}{\partial p^{(i)}}$ ，即可得到其梯度：
$\nabla C_{xr}(p) = \langle \frac{\partial C_{xr}}{\partial p^{(0)}}, \frac{\partial C_{xr}}{\partial p^{(1)}},\frac{\partial C_{xr}}{\partial p^{(2)}}, .... \rangle$
由于函数的梯度代表了函数值增长率最高的方向，于是我们可以认为，对于任意，在 $\nabla C_{xr}(p) \ne 0$ 的情况下，只要让向量沿着当前梯度 $\nabla C_{xr}(p)$ 的反方向移动一小段，就可以找到新的使得 $C_{xr}(p_{i+1}) < C_{xr}(p_{i})$ 。
于是我们的梯度下降算法就呼之欲出了：

通过某种方式（比如随机数或启发式方法）选定一个初始向量
根据已知数据集求在处的梯度 $d_{i} = \nabla C_{xr}(p_{0})$
通过一定方式确定一个步长（比如根据经验指定一个常数），计算 $p_{1} = p_{0} - \alpha p_{0}$
对于任意一步的，使用2、3的办法计算，直到达到特定条件（比如 $\nabla C_{xr}(p_{i}) = 0$ 或者迭代次数超过一定阈值等）

这一方法的优势在于简单明了容易实现，但也存在许多缺点，比如：

步骤<3>中的需要用一定方法确定，如果过大可能导致结果不收敛（越过极值点），过小则导致收敛需要极多的迭代次数
在较为复杂的代价函数 $C$ 或者分步（mini-batch）训练中， $C_{xr}(p_{i})$ 的梯度方向可能在不同的迭代周期反复迂回，造成大量的迭代次数浪费

总之相对于传统的梯度下降方法，我们首当其冲要解决的问题就是：慢。
▍2. “一步到位”的牛顿法

在为实数时，考虑关于的一元二次函数的最值，我们知道，当 $f'(p) = 2\alpha p + \beta = 0$ 时 $f(p)$ 取到最值。也就是说如果我们的能够表示为于的一元二次函数，那么我们可以立刻求出使得最小的 $p = - \frac{\beta}{2 \alpha}$ ，简直就是一步到位！
但是现实世界并没有那么美好，多数情况下我们的会是一个复杂的多的函数，但是上面的方法可以给我们一个提示：
如果我们能够将用二次函数的形式表示出来，我们就可以通过上面的办法大踏步的前进了！
由此我们祭出将任意N阶可导函数化为N次多项式的神器：N阶泰勒展开
选定一个的情况下，我们可以根据 $C_{xr}(p_{0})$ 的二阶泰勒展开式
$C_{xr}(p + p_{0}) \approx C_{xr}(p_{0}) + C_{xr}'(p_{0})p+C_{xr}''(p)\frac{p^2}{2}$
得到的点 $(p + p_{0})$ 上的近似值，当 $\frac{dC_{xr}(p+p_0)}{dp} = C_{xr}'(p_0) + C_{xr}''(p_0)p = 0$ ，也即 $p = -\frac{C_{xr}'(p_0)}{C_{xr}''(p_0)}$ 时，取得极值。

于是我们的在为实数时可以如此计算的极小值：

选取开始迭代
对于迭代中的每第步，根据的泰勒展开，计算 $p_{i+1} = p_i -\frac{C_{xr}'(p_i)}{C_{xr}''(p_i)}$ 得到下一个近似极值点。
重复迭代直到满足终止条件

在这种情况下，我们可以用更少的迭代次数大踏步地前进，并且前进的方向也更趋向于函数的全局最优解（即最值而非极值点），同时也能够摆脱上面梯度下降法中确定的痛苦。
让我们将上面的算式推广到为n阶向量的情况：
首先我们引入Hessian矩阵的概念：

对于关于向量的函数，我们可以根据各分量构建二阶偏导矩阵 $H(f)$ ，使得，即 $H(f) = \begin{bmatrix} \frac{\partial^2 f}{\partial x^{(0)} \partial x^{(0)}} & \frac{\partial^2 f}{\partial x^{(0)} \partial x^{(1)}} & ... &\frac{\partial^2 f}{\partial x^{(0)} \partial x^{(n)}} \\ \frac{\partial^2 f}{\partial x^{(1)} \partial x^{(0)}} & \frac{\partial^2 f}{\partial x^{(1)} \partial x^{(1)}} & ... &\frac{\partial^2 f}{\partial x^{(1)} \partial x^{(n)}} \\ ...& ...& ...& ...\\ \frac{\partial^2 f}{\partial x^{(n)} \partial x^{(0)}} & \frac{\partial^2 f}{\partial x^{(n)} \partial x^{(1)}} & ... &\frac{\partial^2 f}{\partial x^{(n)} \partial x^{(n)}} \\ \end{bmatrix}$

则对于为向量时，上面算法中的第<2>步就变为：
计算 $p_{i+1} = p_i - \frac{\nabla C_{xr}(p_{i})}{H(C_{xr})(p_i)} = pi - H(C_{xr}(p_i))^{-1}\nabla C_{xr}(p_{i})$

那么问题来了，我们发现Hessian矩阵逆矩阵 $H(C_{xr}(p_i))^{-1}$ 不一定是可以求解的，哪怕可以求解，对于 $n$ 维向量，其Hessian矩阵的大小是 $n \times n$ ，一个生产环境中的系统动辄成千上万个参数（也就是向量的维度），每一次迭代都要重新计算一次Hessian矩阵并且求逆。。。你逗我玩呢？
不过别怕，既然难以对Hessian矩阵求逆以在每次迭代中对局部极值的近似一步到位，那么我们就给出一个折衷的算法：Conjugate Gradient - 共轭梯度法。
▍3. 共轭梯度法（Conjugate Gradient）

设某二次函数的极值点在，对于任意一点，存在连接和的向量 $D_i = \overrightarrow{p_ip_t}$ ，按照之前的牛顿法可知，我们在理论上是可以直接求得向量的，然而因为该方法在扩展到任意函数时存在上面指出的种种问题，所以难以进行实际应用。
而牛顿法难以实际应用的最根本原因，就是在推广算式里有一个的存在，这一因子在多参数时变成了对矩阵的求逆运算。那么我们是否可以绕过，想办法求得呢？
答案是肯定的，如果我们回顾梯度下降法，我们会发现，在最终收敛到极值的梯度下降中，所有迭代中移动的那一点点向量之和，一定等于，那么我们只要通过一定办法，在尽量少的移动次数下，使所有移动向量的总和为

此时我们引用一个定理：

维空间中任意向量，都可以用个线性无关向量之和表示

所以如果我们能够讲分解为一组线性无关的向量，就可以在次迭代下，将维向量移动到函数的极值点。
那么问题是，如何进行分解？
就此我们引出向量共轭的概念：

对于向量 $v$ ，如果存在矩阵和向量，使得 $v^TAu = 0$ ，那么认为这两个向量是共轭的

向量共轭的意义在于哪里呢？我们知道如果存在两个向量 $u,v$ 使得 $u^T\times v=0$ ，那么这两个向量互相正交。而向量-矩阵的乘法实际上是向量根据该矩阵进行的线性变换。所以两向量共轭的本质意义是：一个向量与另一个向量经过的线性变换结果向量成正交关系。

不难证明，如果一个维空间下存在个对同一变换矩阵共轭的向量，那么这个向量互相是线性无关的。

于是我们可以开始尝试设计我们在二次函数下求最值的迭代算法了：
考虑一个关于实数的二次函数 $C_{xr}(p)=ap^2 + bp + c$ ，现在我们把他推广到为维向量的形式：

$C_{xr}(p) = \frac{1}{2}\sum_{i=1}^{n} \sum_{j=1}^{n}{A_{ij}p^{(i)}p^{(j)}} + \sum_{i=1}^{n}B_{i}p^{(i)}+C = \frac{1}{2}p^TAp + B^Tp+C$

其中是一个 $N\times N$ 的对称矩阵， $A_{ij}$ 代表展开式中项所对应的系数。（注意两个 $\Sigma$ 前面的 $1/2$ ，是为了避免和 $p^{(j)}p^{(i)}$ 被重复计算。
对于任意点, 我们求解 $C_{xr}(p_i)$ 的梯度 $g_i = \nabla C_{xr}(p_i) = Ap_i + B$ 。
设 $d_i = -g_i$
而后我们求解关于的方程 $\frac{dC_{xr}(p_i+\alpha d_i)}{d\alpha} = 0$ ，使得 $C_{xr}(p_i + \alpha d_i)$ 取得最小值，该方程的求解过程这里就不赘述了，结果为

接下来我们将移动 $\alpha d_i$ 得到 $p_{i+1} = p_i + \alpha d_i$
此时如果我们能够找到一个新的向量,使其共轭于，也即是使得在的梯度函数 $Ap+B$ 中变换所定义的空间中与正交，也就意味着此时点在方向上的移动不会影响到梯度空间中分量上的值，所以，在所有互相共轭的方向上移动一番之后，我们就会移动到目标最小值点。
那么如何找到呢？
首先我们可以求解 $C_{xr}(p_{i+1})$ 的梯度 $g_{i+1} = \nabla C_{xr}(p_{i+1}) = Ap_{i+1} + B$ ，之后我们找到一个使得 $-(g_{i+1}) + \beta d_i = d_{i+1}$ ，也即是找到以去除中与 $d_{i}$ 相关的那一部分。

由前提和关于共轭，我们可以得到 $d_{i+1}^TAd_i = -\nabla C_{xr}(p_{i+1})^TAd_i + \beta d_i^TAd_i = 0$ ，于是得到。
于是我们可以得出结论，使用这种方法，在一个关于维向量的二次函数上，我们可以使用次迭代，从任意一点出发找到最值点，此算法称为共轭梯度法（Conjugate Gradient），事实上可以认为是梯度下降法和牛顿法的折衷。
由此我们可以得到一个求解任意二阶可导函数极值的算法：

以一定方式（比如随机）选取作为初始点开始迭代

对于迭代中的每第步，根据的泰勒展开 $c_{xr}(p_i + p) \approx C_{xr}(p_i) + \nabla C_{xr}(p_i)^Tp + p^TH(C_{xr})p$ ，在附近的近似。

使用共轭梯度法代替原来的牛顿法进行对泰勒展开式的极值进行迭代求解，次迭代后，得到最小值点，此时虽然仍然需要求解但不再需要对其求逆

重复步骤2-3直到收敛或其他指定条件。

那么我们就可以通过牛顿法的启发，在不需要额外指定学习率的情况下，进行学习了。
。。。那么。。。能再给力点么？
可以。因为我们不需要计算整个
▍4. Hessian-Free Optimization

注意上面共轭梯度法中的两个主要参数的确定公式：

和
我们可以看到，此处所有的都并非单独出现，而是以 $Ad_i$ 的形式出现的，由矩阵乘法的结合律知，我们可以先求出 $\gamma_i = Ad_i$ ，从而 $\alpha = - \frac{d_i^T(\gamma_i+B)}{d_i^T\gamma_i}$ ， $\beta = -\frac{\nabla C_{xr}(p_{i+1})^T\gamma_i}{d_i^T\gamma_i}$ 。
现在我们将代换成实际使用的矩阵，由矩阵的定义及矩阵乘法的定义，我们可以对于 $y_i$ 的第行进行如下求解：
$\gamma_i^{(u)} = (H(C_{xr})d_i)^{(u)} = \sum^N_{v=1}{\frac{\partial^2 C_{xr}}{\partial p_i^{(u)} \partial p_i^{(v)}}}(p_i) = \nabla \frac{\partial C_{xr}}{\partial p_i^{(u)}}(p_i)d_i$
即关于 $p^{(u)}$ 偏导数对向量的方向导数。
根据方向导数的定义

对函数，有 $\nabla_vf \approx \frac{f(x + \varepsilon v) - f(x)}{\varepsilon}$ （足够小）

我们可以选取一个小小的，得到新的近似算法：
$\gamma_i^{(u)} = \nabla \frac{\partial C_{xr}}{\partial p_i^{(u)}}(p_i)d_i \approx \frac{\frac{\partial C_{xr}}{\partial p_i^{(u)}}(p_i + \varepsilon d_i) - \frac{\partial C_{xr}}{\partial p_i^{(u)}}(p_i)}{\varepsilon}$
又，因为 $\gamma_i = H(C_{xr})d_i$ 可以视作由所有行向量 $\{\gamma_i^{(u)}| u \in \mathbb{N}, u \in [1,N]\}$ 组成的列向量，所以我们有：
$\gamma_i = H(C_{xr})d_i \approx \frac{\nabla C_{xr}(p_i + \varepsilon d_i) - \nabla C_{xr}(p_i)}{\varepsilon}$
Duang！我们无需真正求解矩阵，只需要确定一个，在每一步计算两次梯度即可~
▍5. 一点提醒

注意本文第三部分中最后总结出算法的第三步：

3. 使用共轭梯度法代替原来的牛顿法进行对泰勒展开式的极值进行迭代求解，次迭代后，得到最小值点，此时虽然仍然需要求解但不再需要对其求逆

我们需要注意的一件事是，这“次迭代”会在整个算法进行全局迭代的每一步进行，意味着：
如果我们的参数数量非常非常多，那么我们的每一步都会因此耗时非常非常久！
这也就意味着：
在参数数量足够多的情况下，Hessian-Free Optimize算法的效率可能低于梯度下降法！
如何解决这一问题呢？
一般来说，如果我们从一个点出发，寻找附近的极值点，该点到目标极值点的距离越远，Hessian-Free方法相对传统梯度下降法的收益越高。
所以一种更实用的优化是，指定一些策略，使得系统在一开始采用Hessian-Free方法进行几次迭代后，转而使用梯度下降法进行后续的迭代。

最后，鉴于鄙人基础薄弱，智商堪忧，又加上此文又臭又长的特性，难免有不明确不准确不正确之处，欢迎探讨质疑与指点。

BlaXuan · 发表于 2022-3-14 11:27

写的太好了

pc8888888 · 发表于 2022-3-14 11:34

一步一步渐进，写的不错！辛苦

stonstad · 发表于 2022-3-14 11:36

好好研究研究

mypro334 · 发表于 2022-3-14 11:41

大神能问一下这个没有字幕你是纯靠听的吗本人弱鸡。。。

DungDaj · 发表于 2022-3-14 11:44

我也在学hinton的课程，这部分完全天书。。跟着你这个介绍到3节共轭的地方又开始迷失了。。

xiangtingsl · 发表于 2022-3-14 11:44

写得好棒！期待后续大作！可以转到开发者头条吗？: )

Ylisar · 发表于 2022-3-14 11:47

共轭梯度每次都在与前几次正交的维度上走足，所以到达最小值要经历的步数和模拟函数的维度有关？

xiangtingsl · 发表于 2022-3-14 11:56

好呀~~注明出处就好~~~ ：P

Zephus · 发表于 2022-3-14 12:05

对的

		自动登录	找回密码
密码			立即注册