Optimal Brain Surgeon and General Network Pruning

首先，回忆下泰勒展开和麦克劳林级数：
对于任意一个函数\(p(x)\)，可以在\(x=0\)处展开为：

\[p(x)=p(0)+p'(0)x+\frac{1}{2}p''(0)x^2+...+\frac{1}{n!}p^{(n)}(0)x^n+o(x^n) \tag{1} \label{eq1} \]

也就是当\(x\)的取值在0附近时，\(p(x)\)可以用上述多项式近似。
同理，如果要在其他的点展开，则展开式子为：

\[p(x)=p(x_0)+p'(x_0)(x-x_0)+\frac{1}{2}p''(x_0)(x-x_0)^2+...+\frac{1}{n!}p^{(n)}(x_0)(x-x_0)^n+o(x^n) \tag{2} \label{eq2} \]

对于神经网络的损失函数\(E(W;X)\)同样可以展开，按\(\eqref{eq2}\)展开，假定展开处的权重是\(W_0\)，则

\[E(W)=E(W_0)+(\frac{\partial E}{\partial W})^T\cdot (W-W_0)+\frac{1}{2}(W-W_0)^T\cdot H\cdot (W-W_0)+o(||W-W_0||^3) \]

上式表示权重取值在\(W_0\)附近时的误差的多项式近似值。移项得到：

\[E(W)-E(W_0)=(\frac{\partial E}{\partial W})^T\cdot (W-W_0)+\frac{1}{2}(W-W_0)^T\cdot H\cdot (W-W_0)+o(||W-W_0||^3) \]

将变化量记作\(\delta\)，则上式变为：

\[\delta E=(\frac{\partial E}{\partial W})^T\cdot \delta W+\frac{1}{2}\delta W^T\cdot H\cdot \delta W+o(||\delta W||^3) \]

其中，\(H\)是hessian矩阵，也就是二阶导组成的矩阵。关于多元函数的泰勒展开，可以参考其他文章，例如：https://zhuanlan.zhihu.com/p/90496291
这就是论文OBS中的公式(1)。

OBS的思路是：

剪掉对模型误差影响最小的权重
更新其他权重

剪枝和更新都被表达为对权重施加一个变量\(\delta W\)

剪枝相当于在当前权重\(W_0\)附近找一个权重\(W\)，该权重将部分元素剪掉，同时error的变化最小，也就是让\(\delta E\)最小。剪掉\(w_p\)就是令权重矩阵中的权重\(w_p=0\)，相当于\(\delta w_p+w_p=0\)。每次剪枝一个权重，就相当于找到一个\(\delta W\)，使得\((\delta W+W_0)_p=0\)，表达成数学公式就是：

\[\mathbb{e}^T_q\cdot \delta W + w_q=0 \]

其中\(e_q\)是单位向量，只有在q的位置是1.

所以优化目标就变成了：

\[\min_q{\{\min_{\delta W}(\frac{1}{2}\delta W^T\cdot H\cdot \delta W) | \mathbb{e}^T_q\cdot \delta W + w_q=0\}} \]

这里忽略了一次项和三次及以上的项。因为训练到局部最优的网络，一阶导数是0(或者接近0，可以忽略不计)，三阶项也忽略。

这就变成了带约束的极值求解问题，用拉格朗日乘子法：

\[L=\frac{1}{2}\delta W^T\cdot H\cdot \delta W+\lambda (\mathbb{e}^T_q\cdot \delta W + w_q) \]

求解上式，得到：

\[\delta W=-\frac{w_q}{H^{-1}_{qq}}H^{-1}\cdot e_q \\ L_q=\frac{1}{2}\frac{w_q^2}{H^{-1}_{qq}} \]