剪枝 | 机器之心

简介

剪枝顾名思义，就是删去一些不重要的节点，来减小计算或搜索的复杂度。剪枝在很多算法中都有很好的应用，如：决策树，神经网络，搜索算法,数据库的设计等。在决策树和神经网络中，剪枝可以有效缓解过拟合问题并减小计算复杂度；在搜索算法中，可以减小搜索范围，提高搜索效率。

1.决策树中的剪枝

在决策树生成的过程中，有些节点分类是意义不大的，而这些节点的存在不仅增加复杂度而且减少了分类器的正确率。剪枝算法就是减除决策树中意义不大的节点来从而减小决策树的大小。剪枝算法可以有效缓解过拟合问题，从而提高了预测准确性。

[描述来源：Wikipedia；https://en.wikipedia.org/wiki/Pruning_(decision_trees)]

在决策树算法中，最终分类树的大小一直是一个关注的问题。如果一个决策树太大（也就是分类太多）就很有可能存在训练集过拟合的问题。如果一个决策数太小（分类较少）的话就很难抓到样本空间中重要的结构信息。但是，在训练过程中，很难告诉一个分类树何时停止继续分类。因为，分类树增加节点的同时，它的误差是不断减小的。这类问题被总结为 horizon effect (眼界问题)。最传统的方法是让树分类直到每个节点包含一定数量的实例时，然后利用剪枝来删除意义不大的节点。当然，剪枝算法应该减小树大小的同时，不影响树分类的正确率。这一般使用 cross-validation（交叉验证）来检验。

剪枝算法主要分为两类：从上往下剪枝和从下往上剪枝。上往下剪枝遍历所有节点从根开始剪枝，也成为：预剪枝。然而从下往上剪枝是从叶节点开始从下往上剪枝，也成为：后剪枝。

预剪枝是在决策树生成过程中，对树进行剪枝，提前结束树的分支生长。
后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。

经典的剪枝算法：

Reduced error pruning误差降低剪枝（REP）；Pesimistic-Error Pruning悲观错误剪枝(PEP）；Cost-Complexity Pruning代价复杂剪枝（CCP)；Minimum Error Pruning最小误差剪枝（MEP）; Minimum Description Length（MDL) basedpruning.

剪枝名称	剪枝方式	计算复杂度	误差估计
REP	自底向上	0(n)	剪枝集上误差估计
PEP	自顶向下	o(n)	使用连续纠正
CCP	自底向上	o(n2)	标准误差
MEP	自底向上	o(n)	使用连续纠正

2.搜索算法中的剪枝

Search algorithm 便是专门解决搜索问题的。就是在特定的数据结构中（如：链表，树，数组等）搜索出需要检索的信息。深度优先算法，广度优先算法，A*算法，贪婪算法都是经典的搜索算法。然而当搜索的范围太大时，复杂度是必须考虑的问题。因此，剪枝算法在搜索问题中也得到了广泛的运用。例如，基于MINMAX衍生出的Alpha–beta（α-β）剪枝是典型的剪枝算法。α-β剪枝是在应用于双人博弈（如tic-tac-toe, 象棋, 围棋等, etc.）的对抗搜索算法。

[描述来源：Wikipedia；URL:https://en.wikipedia.org/wiki/Search_algorithm]

Alpha–beta（α-β）剪枝的核心思想：游戏由Max选手的Min选手组成， α值可作为最佳得分的下界， β值可作为最佳得分的上界，beta <= alpha时的节点可以被删除。

上图是一个α-β剪枝案例，灰色节点代表被剪枝的节点。方括号代表MAX方选择策略，圆括号代表MIN放选择策略；所以在第4层的4 beta = 4比其父节点（第三层）的alpha值5要小，所以将其剩余的枝剪去。

3.神经网络中的剪枝

在神经网络的训练过程中，为了选择合适的大小的神经网络，也有两种方法，和决策树生成的方法类似。第一种，由小的神经网络慢慢的加入新的隐含层来扩大神经网络结构。第二种，由一个较大的神经网络结构通过剪枝来获得较为何时大小的神经网络。

而剪枝算法就是应用于第二种方法中。剪枝采用自顶而下的设计方式，先构建一个足够大的网络，然后通过在训练时删除或合并某些节点或者权值来达到精简网络结构的目的。经典的剪枝方法有：权衰减法，灵敏度计算方法，相关性剪枝方法。剪枝的三个主要步骤：

（1） 进行正常的网络训练；

（2） 删除所有权重小于一定阈值的连接；

（3） 对上面得到的稀疏连接网络再训练；

权衰减法：它通过在网络目标函数中引入代表结构复杂性的正则化项来达到减低网络结构复杂性的目的。通常的目标函数如下，其中E(W)通常取网络误差平方和，C(W)为网络的复杂性。

灵敏度计算方法（Sensitivity Calculations）：该方法是指在网络进行训练时，或在网络训练结束后，计算节点（输入节点及隐节点）或连接权对网络误差的贡献，即灵敏度，删除那些贡献小的节点或权。

相关性剪枝方法：最常见的相关性剪枝方法是先判断隐节点输出之间的相关性，然后合并具有较大相关性的隐节点。

发展历史

Pruning in Decision Tree

Breiman 等人(1984) 和 Gelfand等人(1991)认为剪枝算法在决策树的建立中处于最重要的位置。1984年，Breiman 在决策树中使用CCP（代价复杂剪枝）方法，该方法将目标函数加入复杂度的衡量标准；然而其复杂度过高。随后，1987年，Quinlan 提出REP 和 PEP算法，PEP算法基于训练数据的误差评估，因此不用单独找剪枝数据集。但训练数据也带来错分误差偏向于训练集，因此需要加入修正1/2。是自上而下的修剪。同年，Niblett T, Bratko I 提出MEP算法，MEP算法与PEP方法相近，但是对类的计数处理是不同的。自底向上剪枝。而这些剪枝算法，并不能提取决策树中的生成规则。因为规则可以提供强大的基函数来近似高度非线性函数，2008年提出的RuleFit的算法从树木中提取规则。随着系数学习和优化算法的发展，2017年，决策树中的剪枝问题也被定义为sparse optimization problem，该算法在RuleFit的基础上考虑了树的结构。当然，随着决策树剪枝各种算法的成熟，2016年Jonathan等人提出了一个optimal pruning approach最优剪枝方法从一些列剪枝方法进行剪枝后树的集合里，找出最优的剪枝的决策树。

Network Prunning

神经网络的剪枝已经广泛的应用于CNN模型中。Mozer, Smol ensky 1989提出删除输入节点或隐节点的方法，当某节点的灵敏度低于预定的阈值时，便可以删除该节点,也就是灵敏度计算方法的经典算法。sefee and carter 26研究了该算法发现，即使系统有更小的参数也不会使得这个系统过于敏感。1990年，Karnin 13提出一种删除权值的方法，该方法在神经网络学习中动态计算每个权值的灵敏度，因此计算量较小。Weight等人基于Rissanen的最短描述长度来描述学习机器的复杂性，并提出权消去法（weight-Elimination）,该方法用于剪除网络中冗余的权值。Reed在1993年曾对早期的剪枝算法进行简单的分类。1993年，Hassibi等人提出的Optimal Brain Surgeon剪枝网络通过Hessian损失函数来减少关联，并且实验表明，算法比权衰减法要好。

但这些方法都需要事先知道一些信息才能断定神经网络的大小。之后，GA遗传，PSO等算法被应用于剪枝中，GA或PSO可以找出合适的隐含层数目或者节点数目。优化算法和神经网络的结合大大提高了神经网络的计算效率，也被称为iterative pruning。例如1997,Slawomir 等人使用随机优化算法对神经网络进行剪枝；

最近，因为深度学习是计算密集型和存储密集型的，这使得它难以被部署到只有有限硬件资源的嵌入式系统上。2015年，Han等人发现剪枝后的网络的参数的数目减小了一个数量级；并且提出了一个新的去除冗余的方式，“密集-稀疏-密集”（DSD）训练方法。

Search-space Pruning

减少搜索范围的剪枝算法很早就已经衍生，Lawler在1966年提出的Branch-and-Bound分支界定法是经典的剪枝算法之一;它基于广度优先搜索的基础上将重复的节点删除；基于MINMAX提出的剪枝算法有 Alpha–beta（α-β）剪枝，其更是广泛应用于博弈中，然和由于搜索算法的高复杂度，搜索效率依旧低下，特别是像围棋这种高复杂度的应用场景。所以1993年， Chrilly Donnige提出了null move pruning空着向前剪枝算法。该算法与之前不同的是，从前向后剪枝；null move 指的是不走棋子时当前局面的着法，且若该着法所导致的子树的值为v,应有v<=α。若然而β<=v，立刻剪枝。此算法大大加快了搜索的效率，但是null move pruning算法会导致搜索的不稳定性，如无等着局面(Zugzwang)；被将军时。随后，Heinz在1999年提出自适应的null move pruning 剪枝算法可以动态的选择合适的深度。通过使用最佳的深度,这种技术能够限制战术失误,同时保留大部分的减少搜索工作。在2002年David-Tabibi证实了 null-move pruning空着向前剪枝算法的安全性，也称为“带验证的空着裁剪”(Verified Null-Move Pruning)。

主要事件

年份	事件/决策树	论文
1984	Breiman 在决策树中使用CCP方法	Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and regression trees. CRC press.
1987	Quinlan 提出REP 和 PEP算法	Quinlan, J. R. (1987). Simplifying decision trees. International journal of man-machine studies, 27(3), 221-234.
1995	Mehta M提出MDL-Based Pruning算法	Mehta M, Rissanen J, Agrawal R. MDL-Based Decision Tree Pruning[C]//KDD. 1995, 21(2): 216-221.
2008	Friedman从树的生成中找出规则	Friedman, J. H., & Popescu, B. E. (2008). Predictive learning via rule ensembles. The Annals of Applied Statistics, 916-954.
2016	Oliver J等人提出optimal pruning approach	Oliver, J. J., & Hand, D. J. (2016, January). On pruning and averaging decision trees. In Machine Learning: Proceedings of the Twelfth International Conference (pp. 430-437).

年份	事件/神经网络	论文
1989	Mozer, Smol ensky等人提出一种灵敏度计算方法应用于剪枝方法中	Mozer, M. C., & Smolensky, P. (1989). Skeletonization: A technique for trimming the fat from a network via relevance assessment. In Advances in neural information processing systems (pp. 107-115).
1991	Weigend等人提出权衰弱法进行剪枝	Weigend, A. S., Rumelhart, D. E., & Huberman, B. A. (1991). Generalization by weight-elimination with application to forecasting. In Advances in neural information processing systems (pp. 875-882).
1993	Reed对经典的剪枝算法进行归纳验证，经典的pruning servey之一	Reed, R. (1993). Pruning algorithms-a survey. IEEE transactions on Neural Networks, 4(5), 740-747.
2015	Han S基于剪枝提出了一个压缩神经网络的新方法	Han, S., Mao, H., & Dally, W. J. (2015). A deep neural network compression pipeline: Pruning, quantization, huffman encoding. arXiv preprint arXiv:1510.00149, 10.
2015	Han S为了减小神经网络的高消耗，提出了DSD的三步骤剪除冗余的神经网络	Han, S., Pool, J., Tran, J., & Dally, W. (2015). Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems (pp. 1135-1143).

发展分析

瓶颈

神经网络的高计算量和高存储花费使得它在边缘计算很难部署。

当数据不充分的时候，神经网络就无法进行工作。

未来发展方向

近年来，人工神经网络正向模拟人类认知的道路上更加深入发展，与模糊系统、遗传算法，成为人工智能的一个重要方向，将在实际应用中得到发展。将信息几何应用于人工神经网络的研究，为人工神经网络的理论研究开辟了新的途径。神经计算机的研究发展很快，已有产品进入市场。光电结合的神经计算机为人工神经网络的发展提供了良好条件。

神经网络在很多领域已得到了很好的应用，但其需要研究的方面还很多。其中，具有分布存储、并行处理、自学习、自组织以及非线性映射等优点的神经网络与其他技术的结合以及由此而来的混合方法和混合系统，已经成为一大研究热点。由于其他方法也有它们各自的优点，所以将神经网络与其他方法相结合，取长补短，继而可以获得更好的应用效果。目前这方面工作有神经网络与模糊逻辑、专家系统、遗传算法、小波分析、混沌、粗集理论、分形理论、证据理论和灰色系统等的融合。

[描述来源：百度百科；URL:https://baike.baidu.com/item/%E4%BA%BA%E5%B7%A5%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C/382460?fr=aladdin#7 (https://en.wikipedia.org/wiki/Pruning_(decision_trees))]

Contributor: Ruiying Cai

简介