透彻理解神经网络剪枝算法

大家好，欢迎来到IT知识分享网。

1. 问题叙述
  心血来潮写点最近做的成果，主要分成两个博客来进行阐述。研究生上了一年半看了不少关于剪枝神经网络方面的文章，但是有很少的文章能让人感觉到耳目一新，打通了任督二脉的感觉。前段时间看到了一个剪枝算法就有这种感觉。和大家分享下。
  全连接神经网络在很多方面都用的很多，这我就不赘述了，全连接有很强的逼近能力但是很容易导致过拟合。所以 机器学习与模式识别最核心的问题就是减小系统的复杂度（description -length【1】,VC-dimensions【2】），在神经网络中，这样的核心问题就变成了减少连接权值的数量。
  减小模型复杂度方面，很常见的方法是在损失函数后面加上惩罚项

  为了是模型复杂度减小，通常使用2范数【3】






  但是2范数误差使权值和阈值稀疏化，进而使用1范数对权值和阈值进行惩罚






  进而陆续有很多关于惩罚项的改进【4】【5】【6】，接下来我要阐述的算法是OBS算法，很简单，并且很容易实现，效果显著。


2. OBS算法详述【7】

  OBS算法是一种基于Hessian矩阵的网络修剪算法，首先，构造误差曲面的一个局部模型，分析权值的扰动所造成的影响。

  通过对误差函数进行Taylor展开






H为Hessian矩阵，T表示矩阵的转置，w为神经网络中的参数（包括权值和阈值），
E为训练集的训练误差，训练神经网络用任意的优化算法，该剪枝算法都是适用的。通过优化算法（如L-M算法）得到一个局部最小点，则上式第一项为0，忽略第三项高阶无穷小项。可以得到






该方法通过将其中一个权值置为0，从而可以写成









为单位向量，只有在第q项为1其他的项为0。

当其中一个权值或者是阈值置为0时，使
最小，可以得到






通过拉格朗日乘子法，可以将有约束优化问题转化为无约束优化问题，







为拉格朗日乘子，通过对函数
求偏导，可以得到



导致误差的变化为






算法流程图如下







3. 感想

  1.OBS算法的全称为optimal brain surgeon,翻译成中文就是最优外科手术，表面的意思就是该方法是和神经网络过程是分开的。

  2.该方法是一种框架，只要是模型能求出参数的梯度，那么都可用这个方法进行稀疏化。


4. 例子

   y=sin(x) 生成100个样本，然后随机生成（0,1）的噪声加到干净的样本上

A: 用全连接神经网络对y=sin(x)函数近似，如图，隐层节点为17个






B:通过剪枝算法得到的网络为






通过人为化简为







从上图可以看出，全连接神经网络用来对函数y=sin(x)进行逼近只需要4个隐层节点，所以该算法可以将多余的隐层节点去掉，并且可以进行特征选择，将噪声去掉。


5. 引用

[1] Barron, A., Rissanen, J., & Yu, B. (1998). The minimum description length principle in coding and modeling. IEEE Transactions on Information Theory, 44(6), 2743-2760.

[2] Vapnik, V. N., & Chervonenkis, A. Y. (2015). On the uniform convergence of relative frequencies of events to their probabilities Measures of complexity (pp. 11-30): Springer.

[3] Chow, M.-Y., & Teeter, J. (1994). An analysis of weight decay as a methodology of reducing three-layer feedforward artificial neural networks for classification problems. Paper presented at the Neural Networks, 1994. IEEE World Congress on Computational Intelligence., 1994 IEEE International Conference on.

[4] Weigend, A. S., Rumelhart, D. E., & Huberman, B. A. (1991). Generalization by weight-elimination with application to forecasting. Paper presented at the Advances in neural information processing systems.

[5] Hoyer, P. O. (2004). Non-negative matrix factorization with sparseness constraints. Journal of machine learning research, 5(Nov), 1457-1469.

[6] Zeng, H., & Trussell, H. J. (2010). Constrained dimensionality reduction using a Mixed-Norm penalty function with neural networks. IEEE Transactions on Knowledge and Data Engineering, 22(3), 365-380.

[7] Hassibi, B., & Stork, D. G. (1993). Second order derivatives for network pruning: Optimal brain surgeon. Paper presented at the Advances in neural information processing systems.