14 | 如何在深度学习中运用数值代数的迭代法做训练?

你好,我是朱维刚。欢迎你继续跟我学习线性代数,今天我要讲的内容是“数值线性代数的迭代法,以及如何在实践中运用迭代法求解线性方程组”。

大密度线性方程组的计算已经成为了世界上最快计算机的测试标准。2008 年,IBM 为美国能源部 Los Alamos 国家实验室建造了“Roadrunner”计算机系统,它的运算速度达到了 1.026 petaflop/s(千万亿次 / 秒,petaflop 是衡量计算机性能的一个重要单位,1 petaflop 等于每秒钟进行 1 千万亿次的数学运算)。按摩尔定律计算,现在世界上最快的计算机已经达到了 200 petaflop,我国也早就进入了世界前列,并有望实现 1 exaflop/s(百亿亿次 / 秒),成为世界第一。

可能你会有些疑惑,为什么我要在课程后期来讲数值线性代数呢?

那是因为数值线性代数是一门特殊的学科,是特别为计算机上进行线性代数计算服务的,可以说它是研究矩阵运算算法的学科,偏向算法实践与工程设计。有了之前基础知识的铺垫后,学习数值线性代数会更有效,而且它是可以直接运用在计算机科学中的,比如:在图像压缩中,使用奇异值分解(SVD)来节省内存;在深度学习中,使用共轭梯度来加速神经网络的收敛。

迭代方法说明

课程内容的前期一直都在用直接法来解线性方程组,比如高斯消元法。但在实践中,我们在面对复杂场景时,更多的会使用迭代法来求解(也就是所谓的间接法),因为很多场景会用到大型稀疏矩阵。所以,我打算在这里讲讲机器学习中的迭代法应用。这里需要注意,不是说直接法不重要,直接法解决了许多相对简单的问题,也是其他方法的基础。

现在我就来说一说什么是迭代法?

我们还是通过线性方程组

按这样的方式持续下去,通过迭代的方式来解 。这就类似于把复杂问题层层分解和简化,最终使得这个迭代等式成立:

更具体一点来说,我们其实是从 开始,解

那么究竟应该如何快速地逼近真实解呢?

这里,

它是等式②和①差后得出的结果,迭代的每一步里,错误都会被 乘,如果 越小,那逼近 0 的速度就更快。在极端分解情况下,

但是,这一次迭代的成本太高,我们回到了非迭代方式的原点。所以,你也知道,鱼和熊掌不能兼得, 的选择成为了关键。那我们要如何在每一次迭代的速度和快速收敛之间做出平衡呢?我给你 选择的几种常见方法:

  1. 雅可比方法(Jacobi method): 的对角部分。
  2. 高斯 - 赛德尔方法(Gauss-Seidel): 的下三角部分,包含对角。
  3. ILU 方法(Incomplete LU):

雅可比方法实践

总体介绍了迭代法理论之后,我们就进入迭代法运用的实践环节。

首先,我们先来试试使用雅可比方法解线性方程组,雅克比迭代法是众多迭代法中比较早且较简单的一种。所以,作为迭代法的实践开篇比较合适。让我们设一个 2×2 的线性方程组:

我们很容易就能得出这个方程组的解如下。

现在我们就用雅可比方法来看看怎么解这个方程组:

首先,我们把线性方程组转换成矩阵形式。

接着,把 A 的对角线放在等式左边,得出 矩阵。

其余部分移到等式右边,得出 矩阵。

于是,雅可比迭代就可以表示成下面这样的形式。

现在是时候进行迭代了,我们从

第一次迭代后,我们得到:

第二次迭代后得到:

第三次迭代后得到:

第四次迭代后得到:

第五次迭代后,我们得到:

经过五次迭代后发现收敛,因为它的结果接近真实解。

现在,再来看一下错误等式,$\mathrm{Se}{k+1}=T e{k}ST$ 代入等式,得出:

计算 的逆矩阵和 相乘 得出:

这里, 的逆矩阵和 T 相乘 有特征值

通过 的逆矩阵和 相乘 ,我们得到:

这里的特征值

高斯 - 赛德尔方法实践

现在我们再来看下高斯 - 赛德尔方法,高斯 - 赛德尔迭代可以节约存储加速迭代,每迭代一次只需一组存储单元,而雅可比迭代需要两组单元。

的下三角部分,还是使用之前雅可比方法中的例子,我们得出方程组:

这里有一个比较大的变化,那就是 消失了,通过 ,我们可以直接得到 ,这样有什么好处呢?两大好处是显而易见的,就是节约存储加速迭代

接下来,我们从

第一次迭代后,我们得到:

第二次迭代后得到:

第三次迭代后得到:

经过三次迭代后发现收敛,因为第三次迭代后的结果接近真实解。

错误经过计算分别是

逐次超松弛方法

最后,我们在高斯 - 赛德尔方法上做个小调整,在迭代中引入一个参数“omega”,,即超松弛因子。然后选择一个合适的 ,使得 的谱半径尽可能小,这个方法就叫做逐次超松弛方法(Successive over-relaxation method,简称 SOR)。

SOR 方法的方程是:

是不是看起来更复杂了?

没关系,其实它只是在我们眼中看起来复杂,对计算机来说是没区别的。对 SOR 来说,只是多了一个 ,而 选择越好就越快。具体 的选择,以及迭代的过程就不赘述了,我给你一个小提示,你可以在“ 大于 1”和“ 小于 1”两种情况下来多选择几个 进行尝试,最后你应该会得到结论:

  1. 大于 1 时, 越大,迭代的次数就越多,收敛速度就越慢, 接近 1 时,迭代的次数越小,收敛速度越快。
  2. 小于 1 时, 越小,迭代的次数就越多,收敛速度就越慢, 接近 1 时,迭代的次数越小,收敛速度越快。

所以,SOR 迭代法的关键就是 的选择,它可以被看作是高斯 - 赛德尔法的扩充。

雅可比法、高斯 - 赛德尔法,以及 SOR 迭代法都是定常迭代法。接下来我讲一下和定常迭代法不同的另一类方法,也是实践中用的比较多的方法——共轭梯度法(Conjugate gradient),它属于 Krylov 子空间方法。简单来说,Krylov 子空间方法是一种 “降维打击” 手段,是一种牺牲精度换取速度的方法。

共轭梯度法

要讲共轭梯度法,我们要先解释一下“共轭”,共轭就是按一定的规律相配的一对,通俗点说就是孪生。“轭”是牛拉车用的木头,那什么是共轭关系呢?同时拉一辆车的两头牛,就是共轭关系。

我们根据这个定义再来解释一下共轭方向,向量

现在来看看共轭梯度算法,设

首先,我们设初始值 或者一个估计值,来计算

接下来设

a. 计算

b. 计算

c. 计算

d. 如果 非常小,循环结束,如果不是就继续。

e. 计算

f. 计算

g.

  1. 返回结果

从算法中我们可以看出,共轭梯度法的优点是存储量小具有步收敛性。如果你熟悉 MATLAB,就会发现共轭梯度法的实现超级简单,只需要短短十几行代码(下方代码来自于 MATLAB/GNU Octave 的例子)。

function x = conjgrad(A, b, x)
r = b - A * x;
p = r;
rsold = r' * r;


for i = 1:length(b)
Ap = A * p;
alpha = rsold / (p' * Ap);
x = x + alpha * p;
r = r - alpha * Ap;
rsnew = r' * r;
if sqrt(rsnew) < 1e-10
break;
end
p = r + (rsnew / rsold) * p;
rsold = rsnew;
end
end

机器学习中的共轭梯度

共轭梯度法经常被用在训练神经网络中,在实践中已经证明,它是比梯度下降更有效的方法,因为就像刚才讲的,它不需要计算黑塞矩阵。那我现在就来讲一讲,使用共轭梯度法的神经网络训练过程。

在整个训练过程中,参数改进是重点,当然这也是所有神经网络训练的重点。这个过程是通过计算共轭梯度的训练方向,然后计算训练速率来实现的。在共轭梯度训练算法中,搜索是按共轭方向进行的,也就是说,训练方向是共轭的。所以,收敛速度比梯度下降要快。

现在我们来看训练方向的计算方法。首先,我们设置训练方向向量为 ,然后,定义一个初始参数向量 ,以及一个初始训练方向向量

其中, 是梯度向量, 是共轭参数。参数通过这个表达式来更新和优化。通常训练速率 可使用单变量函数优化方法求得。

本节小结

好了,到这里数值线性代数的迭代法这一讲就结束了,最后我再总结一下前面讲解的内容。

首先,我先解释了数值线性代数,接着再整体讲解了迭代方法。然后,举了一个线性方程组的例子,运用迭代法中的几个比较著名的实践方法:雅可比方法、高斯 - 赛德尔方法,以及逐次超松弛方法,来解这个线性方程组。最后,我把共轭梯度法用在了深度学习的神经网络训练中。

希望你能在了解了数值线性代数,以及迭代法后,更多地在计算机科学领域中,运用迭代法做矩阵运算。如果有兴趣,你也可以学习其它在实践中使用的迭代法。

线性代数练习场

练习时刻到了,这次继续使用第一篇线性方程组里的例子,你可以挑选任意一个迭代法来求解这个线性方程组。

假设,一个旅游团由孩子和大人组成,去程时他们一起坐大巴,每个孩子的票价 3 元,大人票价 3.2 元,总共花费 118.4 元。回程时一起做火车,每个孩子的票价 3.5 元,大人票价 3.6 元,总共花费 135.2 元。请问这个旅游团中有多少孩子和大人?

设小孩人数为 ,大人人数为 ,于是我们得到了一个方程组:

这个方程组的解是:

你可以计算一下多少次迭代后它能收敛,也就是逼近真实解?以及它的错误 又分别是多少?

欢迎在留言区晒出的你的运算过程和结果。如果有收获,也欢迎你把这篇文章分享给你的朋友。