本文是Hassibi 和Stork 等人1993年在LeCun的OBD方法基础上提出的，名为OBS。
文章目录
摘要
为了进一步改善泛化能力、简化神经网络、减少硬件和存储需求、加快训练速度、或者是规则提取，我们研究了所有使用误差函数的二阶导数去进行剪枝的相关信息。我们提出了OBS方法，相比较基于数值大小剪枝和OBD方法剪枝（这两种方法会剪掉错误的参数），我们的方法表现更佳。在同样的训练集和损失的情况下，OBS方法能比其他方法剪掉更多的权重参数，因此可以在相同的测试集上有更好的泛化能力。OBS方法的关键之处在于递归的计算海森矩阵的逆矩阵H−1。实验表明，OBS可以分别将三个在MONK问题上的基准神经网络（使用权重衰减）减少76%,62%,90%的参数。在一个XNOR网络上，使用OBS，OBD, 基于数值大小剪枝这三种方法，只有OBS在所有情况下都剪掉了正确的权重参数。最后，Sejnowski和Rosenberg提出的NETtalk网络有1800个权重，我们使用OBS方法在性能保持不变的情况下，将权重减少到1560个。
1.介绍
在机器学习和模式识别中，一个重要的问题就是最小化系统复杂度（description length， VC维等），在神经网络中，正则化问题经常扮演着最小化连接数量的角色，如果不使用正则化的话，将会导致网络过拟合，即泛化能力很差。相反的，如果网络中的权重太少，网络就可能学习不到数据的特征。
如果我们训练的网络有太多的权重，那么问题来了：我们应该删除哪些权重？应该怎样调整剩下的权重使得网络达到最佳的性能？应该怎么样快速高效的完成这样的网络剪枝过程？
一个方法是基于权重数量级的剪枝方法（mag），该方法会将较小的权重删除。这个方法的思想很简单，但是并不完全合理，有时候会将错误的权重删除–因为有时候数值较小的权重也是必要的。OBD方法使用了最小化训练误差增加的标准方法，为了计算的简便，OBD假设海森矩阵是对角线矩阵，但事实上，在我们研究的所有问题中，海森矩阵都不是对角线矩阵，所以OBD方法会删除掉错误的权重。我们的OBS方法是基于LeCun的OBD方法，但是并不对海森矩阵做任何限制，因此OBS总是消除正确的权重参数，而且，和其他方法不同，OBS在剪枝掉一个权重之后不需要重训练。
2.Optimal Brain Surgeon
和LeCun的方法一样，在进行剪枝之前，我们需要一个训练至误差达到局部极小的神经网络。误差函数关于权重w的导数可以用泰勒级数表示为：
∂E=(∂w∂E)T∗δw+21δwT∗H∗δw+O(∣∣δw∣∣3)（1）
其中H=∂w2∂2E是海森矩阵（包含所有的二阶导数），上标T表示向量的转置。对于一个误差达到局部极小的神经网络，（1）式的第一项为0，另外，我们也将第三项及更高次幂项忽略。然后，我们的目标是将其中的一个权重wq置零，从而使得（1）式的变化最小。消除wq可以表示为δwq+wq=0,或者更加通俗的表示为：
eqT∗δwq+wq=0(2)
其中eq是在权重空间中对应于wq的一个单位向量。于是我们的目标就变为了：qmin（δwmin(21δwT∗H∗δw)∣eqT∗δwq+wq=0）(3)
为了解决公式（3），我们将公式（1）（2）转换为拉格朗日等式：
L=21δwT∗H∗δw+λ(eqT∗δw+wq)(4)
其中λ是拉格朗日乘子，对（3）式求导，并使用逆矩阵来找到最优的权重改变并且将最优改变对误差函数的影响是：
δw=−[H−1]qqwq∗H−1∗eq(5)
Lq=21[h−1]qqwq2(6)
注意，这里的海森矩阵H和逆矩阵H−1都不要求是对角矩阵。进一步，我们的方法通过公式（5）重新计算了网络中所有权重的大小。我们将Lq叫做权重q的“贡献度“（当某个参数删除后，所引起的误差的增加）。该方法定义的贡献度比OBD方法更加通用，当然该方法也包含了OBD方法。
于是我们就算法流程如下：
- 训练一个相当大的神经网络至收敛
- 计算海森矩阵的逆矩阵H−1
- 找到使得Lq最小的q。如果这个候选误差比E小得多，那么第q个权重就应该被删除，然后转到步骤4，否则转到步骤5。(也可以选择其他的停止条件)
- 使用第3步的q，用公式（5）更新所有的权重，然后转到步骤2
- 没有更多的权重可以删除，结束。（可以进行重训练）
图1展示了OBS算法的基本思想。三种方法在剪枝之后（重训练之前）的误差取决于特定的问题，但是遵循一个规律：E(mag)≥E(OBD)≥E(OBS)，这正是OBS方法的优势所在。在这个例子中，OBS和OBD都选择删除权重1，但是在大多数情况下，OBS选择的参数和OBD选择的参数是不一样的。我们将该方法叫做OBS是因为本方法不仅删除了权重，还在不需要进行反向传播梯度下降或者增量重新训练的情况下，重新计算并改变了其他权重的值。
3.计算海森矩阵的逆矩阵
在OBS算法流程中，第二步是最困难的，因为需要计算一个具有成千上万的元素矩阵的逆矩阵。接下来，我们将给出一个完全训练好的神经网络的逆海森矩阵的一般推导，该推导与神经网络的训练方式（梯度下降、竞争、玻尔兹曼机、或者任何其他的算法）无关。我们推导出海森矩阵可以被简化为一个协方差矩阵和特定的梯度向量组成。而且，OBS算法需要的梯度向量计算很简单；并且由协方差组成的海森矩阵，计算其逆矩阵有一个递归的公式，这使得海森矩阵的计算变得容易的多。
考虑一个通用的非线性神经网络，根据下面的式子将一个维度为ni的输入映射到维度为no的输出，
o=F(w,in)(7)
其中w是一个n维的向量，表示神经网络的权重及其他参数。为了简便，我们将w看作是权重向量。训练集的均方误差可以表示为:
E=2P1k=1∑P(t[k]−o[k])T(t[k]−o[k])(8)
其中P是训练pattern，t[k],o[k]分别是对应与第k个训练pattern的实际值和网络输出值。误差函数关于w的一阶导数是：
∂w∂E=−P1k=1∑P∂w∂F(w,in[k])(t[k]−o[k])(9)
二阶导数或者说是海森矩阵是：
H=P1k=1∑P[∂w∂F(w,in[k])∗∂w∂F(w,in[k])T−∂w2∂2F(w,in[k])∗(t[k]−o[k])](10)
接下来我们考虑一个神经网络的误差训练至局部极小时，w=w∗。在这种情况下，网络的输出o[]k将会和真实值t[]k很接近，因此，我们可以忽略包含(t[k]−o[k])的每一项。即使在后面的剪枝过程中，当某个训练pattern的误差不是足够小时，这个近似也可以被修正(看下一章)。这个近似将海森矩阵变为：
H=P1k=1∑P∂w∂F(w,in[k])∗∂w∂F(w,in[k])T(11)
如果我们的神经网络只有一个输出，那么我们定义n维的向量X[k]为导数：
X[k]=∂w∂F(w,in[k])(12)
则公式（11）就变成了：
H=P1k=1∑PX[k]X[k]T(13)
如果我们的神经网络有多个输出，那么X就是n个xn0的向量组成的矩阵：
X[k]=∂w∂F(w,in[k])=∂w∂F1(w,in[k]),...∂w∂F2(w,in[k])=(X1[k],...,Xn0[k])(14)
其中Fi是F的第i个元素，那么公式11）就变成了：
H=P1k=1∑Pl=1∑n0Xl[k]Xl[k]T(15)
公式(13)和公式(15)表明H是与梯度变量X相关的样本协方差矩阵,公式(13)还表明了在单个输出的情况下，海森矩阵可以通过按顺序添加连续的“组件”计算：
Hm+1=Hm+P1X[m+1]∗X[m+1]T(16)
其中H0=αI, Hp=H
但是OBS算法需要的是海森矩阵的逆矩阵，这个计算可以使用标准逆矩阵公式来求解：
(A+B∗C∗D)−1=A−1−A−1∗B∗(C−1+D∗A−1∗B)−1∗D∗A−1(17)
将公式（17）代入到公式（16）可得：
Hm+1−1=Hm−1+P+X[m+1]T∗Hm−1∗X[m+1]Hm−1∗X[m+1]∗X[m+1]T∗Hm−1(18)
其中H0−1=α−1I, Hp=H−1，且α(10−8≤α≤10−4)是一个很小的常数值，使得OBS方法不是那么敏感。实际上，等式（18）需要计算(H+αI)的逆矩阵，这一项对应着等式4 中的惩罚项α∣∣δw∣∣2。有效权值的衰减有利于惩罚权值空间中较大的候选跳变，从而有助于确保忽略等式1中的高阶项是有效的。
等式18允许使用m个序列遍历训练数据(1≤m≤P)来计算H−1。对于多个输出的情况，将等式16推广到两个索引：
Hm,l+1=Hm,l+P1Xl+1[m]Xl+1[m]T
Hm+1,l=Hm,n0+P1Xl[m+1]Xl[m+1]T(19)
相应的，使用等式17来计算其逆矩阵H−1
4.(t−0)→0 的近似
等式11中使用的近似，即使在训练误差不可忽略的情况下，也可以进行网络剪枝，这一事实可以从计算和功能的角度加以证明。从计算的角度来看，首先一般的海森矩阵是退化的（尤其是在剪枝之前），并且它的逆矩阵没有很好的定义。这个近似保证了在计算H−1的过程中没有奇异点，还保证了计算H−1的复杂度和计算H的复杂度一样为O(Pn2)。在统计学中，该近似是Fisher变换得分的基础，其目标就是使用期望值代替海森矩阵从而保证海森矩阵是正定矩阵。
从功能的角度来看这个近似，如果一个训练至收敛（误差很小）的网络（训练过程中包含了噪声），当我们剪枝时，我们希望将导致过拟合的那些权重删除（例如学习到噪声的那些权重），如果在剪枝过程中没有使用(t−0)→0这个近似，那么每次剪枝之后进行权重的调整时，都会重新将噪声项注入到网络中。从另一个角度看这个近似，当我们使用OBS方法剪枝之后，网络误差达到一个新的局部最小点时，即使该误差的提升小到可以忽略，我们也想尽可能的保持误差在新的局部最小点附近，因此我们想象一个新的、有效的真实值t∗,可以保证误差在新的最小点附近。然后，我们就要使用(t∗−o)来进行近似。
5.OBS和反向传播
使用如图２所示的反向传播的神经网络，从等式12可以得到该网络的导数向量为：
X[k]=(Xv[k]Xu[k])(20)
其中Xv[k]是误差函数对隐含层到输出层权重vj的导数，式子如下：
[Xv[k]]T=(f′(net[k])oj=1[k],...,f′(net[k])onj[k])(21)
其中Xu[k]是误差函数对输入层到隐含层权重uji的导数，激活函数是f(.),式子如下：
[Xu[k]]T=(f′(net[k])f′(net1k)v1[k]oi=1[k],...,f′(net[k])f′(net1k)v1[k]on[k],...,f′(net[k])f′(netnj[k])vnj[k]o1[k],...,f′(net[k])f′(netnj[k])vnj[k]on[k])(22)
6.仿真实验
我们之前已经发现了OBS方法表现好于OBD和mag。接下来我们在一个针对XOR问题的2-2-1的神经网络上分别使用这三种方法。首先训练该神经网络，达到了误差为0的情况，然后开始进行剪枝，三种方法有时选择删除相同的权重，但大部分情况下，会选择删除不同的权重，如图3所示，每个方法都选择删除不同的权重，在这一特定情况下，OBD和mag都选择删除了错误的权重，导致不管后期如何进行重训练，网络的误差都无法再恢复到之前的状态，但是 OBS选择删除了正确的权重，经过等式5的权重调整，网络的性能没有变化。所以，即使在OBD和mag都删除了错误的权重的情况下，OBS却在剪枝之后，不需要任何梯度下降重训练的情况下，保持了网络的性能。
图4是图3中的网络训练完成，未进行剪枝之前的海森矩阵，从图中可以看出，海森矩阵明显不是一个对角线矩阵，而且非对角线上的元素对最终误差也起到了重要的作用。
图5展示了具有9个参数的XOR网络在局部最优点w∗处的二维的“贡献”。图的左右半部分分别是mag方法和OBS方法的对比效果和OBD和OBS的对比效果。
值得注意的是局部最优点w∗，经过OBD和mag剪枝之后，无论怎样进行重训练，网络都无法达到之前误差为0状态，简而言之，是因为这两种方法删除了错误的权重，导致的错误无法通过重训练恢复，只有OBS删除了正确的权重。
我们也将OBS应用在了更大的神经网络上，并且与文献[11]（其反向传播神经网络比其他所有优化神经网络性能都好）的结果进行对比。所有网络的海森矩阵都不是对角线矩阵。
从表２中可以看出，相比较与反向传播神经网络，OBS方法剪枝之后（不需要重训练）的网络仅需要其24%、38%、10%的权重数量就可以达到与其相同的性能。
OBS极大地减少了权值，从而生成了足够简单的网络，可以从修剪后的网络中恢复生成数据的逻辑规则。因此，OBS可能有助于解决神经网络经常受到的批评:它们可能难以理解。
我们也将OBS应用在一个三层的NETtalk网络，文献[10]了18000个权重，本文训练NETtalk网络至收敛，权重数量只有5546个，然后进行OBS剪枝，权重数量为2438个，在这里加入了重训练过程，然后进行迭代剪枝，最后的权重数量为1560个，且测试误差也有提升。所以OBS也可以应用与现实世界中的应用，例如有着上千个参数语言识别应用。
7.分析和总结
为什么OBS可以在减少参数数量上如此优秀？我们可以反过来问：问什么最简单的mag表现如此差呢？重新看一下图1，从局部最优点w∗开始，mag选择删除了错误的权重weight2，然后通过重训练，weight1变大，weight2=0，这个结果与OBS产生的结果weight1=0，weight2增大，恰恰相反。在图1中，误差的变化看起来很小，但是在现实世界中的大型神经网络中，删除错误的权重数量增多，将会导致误差变化很大。更重要的一点是，mag方法相信即使错误的删除了很多权重，也可以通过后期的重训练使得网络到达一个全局最优，这一点是错的，尤其当网络已经是很简单的结构时，这一点更加不能实现。
我们也看到了OBD是采用了近似（海森矩阵是对角线矩阵）之后进行的计算，但是根据我们的调查，海森矩阵大部分情况下，都不是对角线矩阵，而且也有很多非对角线元素比对角线元素更大更重要。这就解释了为什么OBD方法表现欠佳。
我们的OBS方法包含之前的方法，更加通用。用术语表示的话，mag方法是假设海森矩阵是各向同性的矩阵;OBD方法假设海森矩阵是对角线矩阵；文献[5]假设激活函数f(.)是线性的，且只更新输出层的权重。我们也已经证明了这些假设都不是合理的且也不足以作为删除权重的依据。
OBS方法也比[2]中的方法更加通用。例如，与其通过将权重置零的方式删除一个权重，还不如通过投影到任意平面来减少*度。本文讨论的剪枝约束wq=0使得重训练(如果需要)特别简单。另外，很多权重（权重，偏置）可以同时删除。另一个改进的更加通用的地方是，OBS使用交叉熵损失或者是Kullback-Leibler损失，这就是使得海森矩阵可以变为Fisher 信息矩阵转换。我们还注意到，OBS本身并没有给出何时停止修剪的标准，因此OBS可以用于各种各样的标准。此外，渐进的方法，如学习过程中的权重衰减，可以与OBS结合使用。