核心要点

OBD：引入二阶导数信息对神经网络进行最小损失剪枝。

OBS：引入删除权重补偿概念，使得剪枝损失降到更小。

提出问题

随着神经网络的发展，神经网络在现实世界中解决了越来越多的问题，但随之而来的是模型变的越来越大，结构变得越来越复杂，推理时间变的越来越长，部署起来也越来越不方便，并且随着参数逐渐变多，导致过拟合的风险也越来越大，所以我们就提出了下面这个问题：

如何选择性得删除一些权重来减小网络大小的同时不要引入太多的误差呢？

解决方法

理论推导

为了解决这一问题，我们需要定义什么是删除权重带来的误差呢？

目标函数在机器学习中起着核心作用，因此定义一个参数的显著性是指删除该参数所导致的目标函数的变化。但是通过暂时删除每个参数并重新评估目标函数来从这个定义中评估显著性将是极其繁琐的。

不过，可以构建一个错误函数的局部模型并分析地预测扰动参数向量的影响。我们用对目标函数$E$进行泰勒展开。对参数向量的扰动$\delta U$对目标函数的影响如下式所示。

$$\begin{array}{c}\delta E=\sum _i{g}_i\delta u_i+\frac{1}{2}\sum _i{h}_{ii}\delta u_i^2+\frac{1}{2}\sum _{i\ne j}{h}_{ij}\delta u_i\delta u_j+O\left(\Vert \delta U{\Vert }^3\right)\end{array}$$

其中有$g_i=\frac{\partial E}{\partial u_i}\text{ and }{h}_{ij}=\frac{{\partial }^{2}E}{\partial u_i\partial u_j}$，$g_i$是$U$对$E$的梯度，$h_{ij}$是$U$对$E$的海森矩阵的元素。

有了上面的误差函数，我们接下来的目标就是找到一组参数，使得这个$\delta E$最小，但由于$H$太大了，所以这个问题几乎无法解决，所以我们需要对这个函数做出一些近似。

a. $\text{Diagonal}$: 我们假设由于删除多个参数导致的E增量等于分别删除每个参数导致的E增量之和，换句话说就是对于参数的删除导致误差是独立的，参数之间不会有相互影响，所以我们可以把交叉项$\frac{1}{2}{\sum }_{i\ne j}{h}_{ij}\delta u_i\delta u_j$忽略

b. $\text{Extremal}$: 我们假设网络是已经完美收敛了，此时我们的参数$U$就是对于$E$的局部最小值处，换句话说，就是$U$对$E$的梯度$g_i$等于$$$$，所以我们可以把第一项${\sum }_i{g}_i\delta u_i$忽略。

c. $\text{Quadratic}$: 我们假设这个$\delta E$就是一个二次的函数，更高次的项我们不考虑，所以我们可以把最后一项$O\left(\Vert \delta U{\Vert }^3\right)$忽略。

最终，经过一系列的优化，我们可以得到如下所示对于损失的一个近似表示

$$\begin{array}{c}\delta E=\frac{1}{2}\sum _i{h}_{ii}\delta u_i^2\end{array}$$

具体实现

具体怎么计算海森矩阵我们到下一章进行描述

对于OBD来说，具体流程如下图所示：其中saliency有$s_k=h_{kk}{u}_k^2/$

再提出问题

我们这种直接把它置零的方法是足够好的吗，有没有更好的缩减误差的方法？

再提出方案

Introducing OBS(Optimal Brain Surgeon).

In addition to cutting out weights, changing the strengths of other weights.

和上面一样，我们考虑训练到局部最小误差的网络。相对于权重扰动$\delta \mathbf{w}$的的Loss函数的泰勒展开为：

$$\begin{array}{c}\delta \mathrm{E}=\underset{\approx 0}{{\left(\frac{\partial \mathrm{E}}{\partial \mathbf{w}}\right)}^{\mathrm{T}}\cdot \delta \mathbf{w}}+\frac{1}{2}\delta {\mathbf{w}}^{\mathrm{T}}\cdot \mathbf{H}\cdot \delta \mathbf{w}+\underset{\approx 0}{O\left(\Vert \delta \mathbf{w}{\Vert }^3\right)}\end{array}$$

其中$\mathbf{H}=\frac{{\partial }^2\mathrm{E}}{\partial {\mathbf{w}}^2}$是Loss对参数的海森矩阵。和上面一样，我们忽略第一项和第三项，那么我们对权重${\mathrm{w}}_{\mathrm{q}}$进行删除的操作可以表示为(其中${\mathbf{e}}_q$是权重空间${\mathbf{e}}_q$中相对于${\mathrm{w}}_{\mathrm{q}}$的单位向量

$$\begin{array}{c}\delta {\mathrm{w}}_q+{\mathrm{w}}_q=0\text{ or }{\mathbf{e}}_q^{\mathrm{T}}\cdot \delta \mathbf{w}+{\mathrm{w}}_q=0\end{array}$$

这样，我们的目标就是解下面这个最优化问题：

$$\begin{array}{c}{\mathrm{Min}}_q\left\{{\mathrm{Min}}_{\delta \mathbf{w}}\left\{\frac{1}{2}\delta {\mathbf{w}}^{\mathrm{T}}\cdot \mathbf{H}\cdot \delta \mathbf{w}\right\}\text{ such that }{\mathbf{e}}_q^T\cdot \delta \mathbf{w}+{\mathrm{w}}_q=0\right\}\end{array}$$

接下来我们把他转换为拉格朗日乘数法有如下表示：

$$\begin{array}{c}L=\frac{1}{2}\delta {\mathbf{w}}^{\mathrm{T}}\cdot \mathbf{H}\cdot \delta \mathbf{w}+\lambda \left({\mathbf{e}}_q^T\cdot \delta \mathbf{w}+{\mathrm{w}}_q\right)\end{array}$$

不难解出：

$$\begin{array}{c}\delta \mathbf{w}=-\frac{{\mathrm{w}}_q}{{\left[{\mathbf{H}}^{-1}\right]}_{qq}}{\mathbf{H}}^{-1}\cdot {\mathbf{e}}_q\text{ and }L=\frac{1}{2}\frac{{\mathrm{w}}_q^2}{{\left[{\mathbf{H}}^{-1}\right]}_{qq}}\end{array}$$

这样的话我们就可以得到一个$\delta \mathbf{w}$使得我们剪切了${\mathrm{w}}_{\mathrm{q}}$的同时调整了其他的权重使得Loss变动最小。

为什么OBS是更好的方法呢？

我们考虑如图所示的例子，来对比OBS、OBD和基于大小的权重剪切方法。

从${\mathrm{w}}^{\ast }$ 处的局部最小值开始，基于大小的方法删除错误的 $\text{weight2}$ 并且通过再训练，$\text{weight1}$将增加。而与之对比OBD和OBS删除正确的$\text{weight1}$，并且OBS更改了 $\text{weight2}$ 来达到局部最小值。在这个例子中可能最终误差的大小差异并不明显，但是如果在一个比较大的网络中，使用基于大小的方法删除了错误的权重可能会导致最终误差的明显增加，显然这是不合理的。

并且在实验中表明了海森矩阵并不是只有对角的部分是有用的，其他的部分也是有和对角线部分几乎相同的作用，所以我们的方法并不会只考虑对角海森矩阵，而是通过外积近似的方式计算整个海森矩阵。

海森矩阵计算

现在我们已经知道了如何对神经网络进行修剪优化，但海森矩阵具体怎么算呢。接下来，我们参考 $\text{PRML}$ 和 $\text{OBS}$ 来对如何计算对角海森矩阵进行讲述。

假设我们有如图所示的一个网络，那么这个网络有两部分参数，input到hidden的参数${\mathbf{u}}_{ji}$、hidden到output的参数${\mathbf{v}}_j$，接下来我们以MSE为例解释如何计算这些参数对Loss的海森矩阵。

首先，我们易知MSE的表达式如下所示：

$$\begin{array}{c}E=\frac{1}{2\mathrm{P}}\sum _{k=1}^{\mathrm{P}}{\left({\mathrm{t}}^{[k]}-{\mathrm{o}}^{[k]}\right)}^2\end{array}$$

则Loss对这些参数的二阶导数有如下表示：

$$\begin{array}{c}\frac{{\partial }^{2}E}{\partial {\mathrm{v}}_j\partial {\mathrm{v}}_{j^{\prime }}}=\frac{1}{\mathrm{P}}\sum _{k=1}^{\mathrm{P}}\left\{{\mathrm{f}}^{\prime }{\left({\text{ net }}^{[k]}\right)}^2-\left({\mathrm{t}}^{[k]}-{\mathrm{o}}^{[k]}\right){\mathrm{f}}^{\prime \prime }\left({\mathrm{net}}^{[k]}\right)\right\}{\mathrm{o}}_j^{[k]}{\mathrm{o}}_{j^{\prime }}^{[k]}\end{array}$$
∂2E∂vj∂uj′i′=1P∑k=1P{{{f′( net [k])2−(t[k]−o[k])f′′( net [k])}vj′f′( net j′[k])oi′[k]oj[k]}−(t[k]−o[k])f′(net[k])f′(netj′[k])δjj′oi′[k]}begin{equation}

begin{aligned}

frac{partial^2 E}{partial mathrm{v}_j partial mathrm{u}_{j^{prime} i^{prime}}}= & frac{1}{mathrm{P}} sum_{k=1}^{mathrm{P}}left{left{left{mathrm{f}^{prime}left(text { net }^{[k]}right)^2-left(mathrm{t}^{[k]}-mathrm{o}^{[k]}right) mathrm{f}^{prime prime}left(text { net }^{[k]}right)right} mathrm{v}_{j^{prime}} mathrm{f}^{prime}left(text { net }_{j^{prime}}^{[k]}right) mathrm{o}_{i^{prime}}^{[k]} mathrm{o}_j^{[k]}right}-right. \

& left.left(mathrm{t}^{[k]}-mathrm{o}^{[k]}right) mathrm{f}^{prime}left(mathrm{net}^{[k]}right) mathrm{f}^{prime}left(mathrm{net}_{j^{prime}}^{[k]}right) delta_{j j^{prime}} mathrm{o}_{i^{prime}}^{[k]}right}

end{aligned}

end{equation}∂vj​∂uj′i′​∂2E​=​P1​k=1∑P​{{{f′( net [k])2−(t[k]−o[k])f′′( net [k])}vj′​f′( net j′[k]​)oi′[k]​oj[k]​}−(t[k]−o[k])f′(net[k])f′(netj′[k]​)δjj′​oi′[k]​}​​​
$$\begin{array}{c}\begin{array}{rl}& \frac{{\partial }^{2}E}{\partial {\mathrm{u}}_{ji}\partial {\mathrm{u}}_{j^{\prime }{i}^{\prime }}}=\frac{1}{\mathrm{P}}\sum _{k=1}^{\mathrm{P}}\{\left[{\mathrm{f}}^{\prime }{\left({\mathrm{net}}^{[k]}\right)}^2-\left({\mathrm{t}}^{[k]}-{\mathrm{o}}^{[k]}\right){\mathrm{f}}^{\prime \prime }\left({\mathrm{net}}^{[k]}\right)\right\}{\mathrm{v}}_j{\mathrm{v}}_{j^{\prime }}{\mathrm{f}}^{\prime }\left({\mathrm{net}}_j^{[k]}\right){\mathrm{f}}^{\prime }\left({\mathrm{net}}_{j^{\prime }}^{[k]}\right){\mathrm{o}}_i^{[k]}{\mathrm{o}}_{i^{\prime }}^{[k]}-\\ & \left({\mathrm{t}}^{[k]}-{\mathrm{o}}^{[k]}\right){\mathrm{f}}^{\prime }\left({\text{ net }}^{[k]}\right){\mathrm{v}}_j{\mathrm{f}}^{\prime \prime }\left({\text{ net }}_{\mathrm{j}}^{[k]}\right){\delta }_{j{j}^{\prime }}{\mathrm{o}}_i^{[k]}{\mathrm{o}}_{i^{\prime }}^{[k]}\}\\ & \end{array}\end{array}$$

由于我们进行剪切的网络已经是一个经过训练达到了局部最小的网络，即${\mathrm{t}}^{[k]}-{\mathrm{o}}^{[k]}\approx 0$，上式可以简化为：

$$\begin{array}{c}\frac{{\partial }^{2}E}{\partial {\mathrm{v}}_j\partial {\mathrm{v}}_{j^{\prime }}}=\frac{1}{\mathrm{P}}\sum _{k=1}^{\mathrm{P}}{\mathrm{f}}^{\prime }{\left({\mathrm{net}}^{[k]}\right)}^2{\mathrm{o}}_j^{[k]}{\mathrm{o}}_{j^{\prime }}^{[k]}\end{array}$$
$$\begin{array}{c}\frac{{\partial }^{2}E}{\partial {\mathrm{v}}_j\partial {\mathrm{u}}_{j^{\prime }{i}^{\prime }}}=\frac{1}{\mathrm{P}}\sum _{k=1}^{\mathrm{P}}{\mathrm{f}}^{\prime }{\left({\text{ net }}^{[k]}\right)}^2{\mathrm{v}}_{j^{\prime }}{\mathrm{f}}^{\prime }\left({\mathrm{net}}_{j^{\prime }}^{[k]}\right){\mathrm{o}}_{i^{\prime }}^{[k]}{\mathrm{o}}_j^{[k]}\end{array}$$
$$\begin{array}{c}\frac{{\partial }^{2}E}{\partial {\mathrm{u}}_{ji}\partial {\mathrm{u}}_{j^{\prime }{i}^{\prime }}}=\frac{1}{\mathrm{P}}\sum _{k=1}^{\mathrm{P}}{\mathrm{f}}^{\prime }{\left({\text{ net }}^{[k]}\right)}^2{\mathrm{v}}_j{\mathrm{v}}_{j^{\prime }}{\mathrm{f}}^{\prime }\left({\mathrm{net}}_j^{[k]}\right){\mathrm{f}}^{\prime }\left({\mathrm{net}}_{j^{\prime }}^{[k]}\right){\mathrm{o}}_i^{[k]}{\mathrm{o}}_{i^{\prime }}^{[k]}\end{array}$$

这样的话，我们就可以通过一阶导向量的外积对海森矩阵进行近似：

$$\begin{array}{c}{\left[{\mathbf{X}}_{\mathrm{v}}^{[k]}\right]}^{\mathrm{T}}=\left({\mathrm{f}}^{\prime }\left({\text{ net }}^{[k]}\right){\mathrm{o}}_{j=1}^{[k]},\dots ,{\mathrm{f}}^{\prime }\left({\text{ net }}^{[k]}\right){\mathrm{o}}_{n_j}^{[k]}\right)\end{array}$$
$$\begin{array}{c}\begin{array}{rl}{\left[{\mathbf{X}}_{\mathrm{u}}^{[k]}\right]}^{\mathrm{T}}=& ({\mathrm{f}}^{\prime }\left({\mathrm{net}}^{[k]}\right){\mathrm{f}}^{\prime }\left({\mathrm{net}}_1^{[k]}\right){\mathrm{v}}_1^{[k]}{\mathrm{o}}_{i=1}^{[k]},\dots ,{\mathrm{f}}^{\prime }\left({\text{ net }}^{[k]}\right){\mathrm{f}}^{\prime }\left({\mathrm{net}}_1^{[k]}\right){\mathrm{v}}_1^{[k]}{\mathrm{o}}_{n_i}^{[k]},\dots ,\\ & {\mathrm{f}}^{\prime }\left({\text{ net }}^{[k]}\right){\mathrm{f}}^{\prime }\left({\mathrm{net}}_{n_j}^{[k]}\right){\mathrm{v}}_{n_j}^{[k]}{\mathrm{o}}_1^{[k]},\dots ,{\mathrm{f}}^{\prime }\left({\text{ net }}^{[k]}\right){\mathrm{f}}^{\prime }\left({\mathrm{net}}_{n_j}^{[k]}\right){\mathrm{v}}_{n_j}^{[k]}{\mathrm{o}}_{n_i}^{[k]})\end{array}\end{array}$$

接下来我们把这两个向量连接起来成为一个维度大小为该层网络参数量的一阶导向量${\mathbf{X}}^{[k]}$,

$$\begin{array}{c}{\mathbf{X}}^{[k]}=\left(\begin{array}{c}{\mathbf{X}}_{\mathrm{V}}^{[k]}\\ {\mathbf{X}}_{\mathbf{u}}^{[k]}\end{array}\right)\end{array}$$

那么我们可以得到海森矩阵的外积近似如下所示：

$$\begin{array}{c}\mathbf{H}=\frac{{\partial }^2\mathrm{E}}{\partial {\mathbf{w}}^2}=\frac{1}{\mathrm{P}}\sum _{k=1}^{\mathrm{P}}{\mathbf{X}}^{[k]}\cdot {\mathbf{X}}^{[k]\mathrm{T}}\end{array}$$

这样我们就得到了OBD中所需要的海森矩阵的对角矩阵

$$\begin{array}{c}D=\left[\begin{array}{cccc}[H{]}_{1,1}& 0& \cdots & 0\\ 0& [H{]}_{2,2}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & [H{]}_{n,n}\end{array}\right]\end{array}$$

我们可以看到上面对海森矩阵mathbf{H的表示是一个加和最终结果的形式，具体每一步的计算如下所示：

$$\begin{array}{c}{\mathbf{H}}_{\mathrm{m}+1}={\mathbf{H}}_{\mathrm{m}}+\frac{1}{\mathrm{P}}{\mathbf{X}}^{[\mathrm{m}+1]}\cdot {\mathbf{X}}^{[\mathrm{m}+1]\mathrm{T}}\text{ with }{\mathbf{H}}_0=\alpha \mathbf{I}\text{ and }{\mathbf{H}}_{\mathrm{P}}=\mathbf{H}\end{array}$$

矩阵和的逆的计算法则如下所示：

$$\begin{array}{c}(\mathbf{A}+\mathbf{B}\cdot \mathbf{C}\cdot \mathbf{D}{)}^{-1}={\mathbf{A}}^{-1}-{\mathbf{A}}^{-1}\cdot \mathbf{B}\cdot {\left({\mathbf{C}}^{-1}+\mathbf{D}\cdot {\mathbf{A}}^{-1}\cdot \mathbf{B}\right)}^{-1}\cdot \mathbf{D}\cdot {\mathbf{A}}^{-1}\end{array}$$

那么我们则有海森矩阵的逆${\mathbf{H}}^{-1}$的计算方式如下所示：

$$\begin{array}{c}{\mathbf{H}}_{\mathrm{m}+1}^{-1}={\mathbf{H}}_{\mathrm{m}}^{-1}-\frac{{\mathbf{H}}_{\mathrm{m}}^{-1}\cdot {\mathbf{X}}^{[\mathrm{m}+1]}\cdot {\mathbf{X}}^{[\mathrm{m}+1]\mathrm{T}}\cdot {\mathbf{H}}_{\mathrm{m}}^{-1}}{\mathrm{P}+{\mathbf{X}}^{[\mathrm{m}+1]\mathrm{T}}\cdot {\mathbf{H}}_{\mathrm{m}}^{-1}\cdot {\mathbf{X}}^{[\mathrm{m}+1]\mathrm{T}}}\text{ with }{\mathbf{H}}_0^{-1}={\alpha }^{-1}\mathbf{I}\text{ and }{\mathbf{H}}_{\mathrm{P}}^{-1}={\mathbf{H}}^{-1}\end{array}$$

下面是不考虑bias的MSE，CE的海森矩阵的外积近似，大家有兴趣可以推导一下。

$$\begin{array}{c}{H}_{\theta }={\nabla }_{\theta }^{2}MSE(\theta )=\frac{2}{n}\sum _{i=1}^n{\nabla }_{\theta }{f}_{\theta }\left(x_i\right){\nabla }_{\theta }{f}_{\theta }{\left(x_i\right)}^T\end{array}$$
$$\begin{array}{c}{H}_{\theta }={\nabla }_{\theta }^{2}CE(\theta )=\sum _{i=1}^n{f}_{\theta }\left(x_i\right)\left(1-f_{\theta }\left(x_i\right)\right){\nabla }_{\theta }{f}_{\theta }\left(x_i\right){\nabla }_{\theta }{f}_{\theta }{\left(x_i\right)}^T\end{array}$$