深度学习模型剪枝的评述 摘要 近年来，深度神经网络在机器视觉和自然语言处理领域都取得了巨大的成功。然而，要将这些模型部署到诸如机器人芯片、智能手机等微型嵌入式设备上仍是一个巨大的挑战。因此，对于这样的平台，模型压缩是一种降低内存消耗和计算复杂度的合理解决方案，目前处理这一问题的技术手段仍然是模型剪枝，而通道级别的模型剪枝又是最有效的手段之一。因此如何有效的实现通道级别的模型剪枝是至关重要的，并且一直是一个具有大量研究成果的主题。 本文阐述了近年来出现的通道级别模型剪枝的主要技术手段，我们主要讨论各个论文的研究成果和遇到的问题，以及根据共同的特点按类别组织的解决方案列表，并且还列出了各个实验结果之间的比较。 关键词：深度学习，模型压缩，通道剪枝 一．引言 在最近这几年中，深度学习赢得了越来越多的关注，并且促进了非常多领域的突破，这依赖于深度神经网络百万甚至千万级别的参数量，和图形处理器的高速计算能力都起着至关重要的作用。 然而，深度学习模型不管在训练还是在部署到设备上时都存在需要问题。比如，[1]在2012年的ImageNet Challenge中取得了突破性的成果，使用了包含6000万个参数的5个卷积层和3个全连接层的网络。通常需要两到三天的时间在NVIDIA K40机器来训练整个模型的ImagetNet数据集。有时在仅依赖于全连接层的架构中，参数的数量可以增长到数十亿[2]。另一方面，卷积运算消耗了大量的计算资源，而这在移动设备上是非常稀缺的，数十亿的网络参数对于嵌入式设备来说也是高存储开销。以VGG-16模型为例，它拥有超过1.38亿个参数，占用超过500MB的内存空间。同时，224×224图像的分类需要300亿次浮点运算(FLOPs)。显然，将如此大的模型直接部署到嵌入式设备中是不切实际的。 因此，在精度没有明显下降的情况下压缩深度模型是一个关键问题。在这种情况下，许多模型压缩方法也相继被提出。最近的一些压缩和加速方法，包括权值剪枝[3-5]、网络量化[6-8]、低秩近似[9,10]、高效模型设计[11-12]。神经元剪枝方法[3]通过去除一些不那么重要的连接，使权值变得稀疏。网络量化针对存储空间压缩问题，提出了一种降低参数表示精度的网络量化[7]算法。低秩近似[9]利用低秩矩阵技术将权值矩阵分解成几个存储空间较小的小矩阵。但是以上方法或多或少存在一些问题，权值剪枝与网络量化需要特殊的软硬件结合使用才能达到好的效果，低秩近似对于1*1的卷积并无效果。而高效模型设计更多关注设计一些不同的网络模型而不是优化已有的卷积运算或者网络架构来压缩加速。 通道剪枝[4,5]是另一种权值剪枝方法，不同于神经元剪枝。与去除单个神经元连接相比，修剪整个通道有两个优点。首先，它不引入原始网络结构的稀疏性，因此不需要对生成的模型进行特殊的软硬件实现。其次，推理阶段不需要庞大的磁盘存储和运行时内存。 本文综述了近年来通道剪枝在深神经网络的压缩和加速研究进展，这些研究引起了深度
AlphaBeta剪枝算法 关于AlphaBeta剪枝的文章太多，这个方法是所有其它搜索方法的基础，得多花些时间认真地理解。 先把基本概念再回顾一遍： 节点：在中国象棋中就是一个棋盘的当前局面Board，当然该轮到谁走棋也是确定的。这里的圆形节点表示终止节点，在中国象棋里就是一方被将死的情况（或者到达了搜索的最大深度），后续不会再有着法产生，游戏如果走到这里就会结束。在引擎里通常给红方一个很大的评估值，如+30000，给黑方一个很小的评估值，如-30000，来方便地判断这种结束局面。（胜利局面有稍微不同的表示法，用-30000+层数ply来表示） 连线：表示一步着法Move，通过这步着法后，局面发生变化，先后手也要交换。 层：通常的术语是ply，复数形式是plies，也有称为levels，当然与depth也是对应的。这个术语是为了与比赛里常说的回合相区分，一个回合通常包含2步，这个ply就表示某一方走了一步。根节点记为0层，以下的层数递增。 深度depth：要注意是从下到上的，还是从上到下的。（1）通常的算法书中都是从下到上递增的，即根节点为最大搜索深度，走到最底部的叶子结点为0，这种算法只要记住一个depth 值就可以了。（2）而另一种记法是根部结点为0，越向下depth增加，这时在搜索时就要传递2个参数值，depth和maxDepth，稍微有点啰嗦，应该也会影响一点效率。另外在探查置换表中的结点时，用第（1）种记法也方便一些，因为要知道从当前节点迭代的深度值，否则还要在置换表中保存depth和maxDepth两个值。 AlphaBeta剪枝方法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。 这种方法的前提假设与Minimax也是一样的： 1）双方都按自己认为的最佳着法行棋。 2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，红方有利时给一个正数，黑方有利时给一个负数。（如果红方有利时返回正数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回正数，这种评估方法都不适合于常规的算法描述） 3）从我们的搜索程序（通常把它称为Max）看来，分值大的数表示对己方有利，而对于对方Min来说，它会选择分值小的着法。 但要注意：用Negamax风格来描述的AlphaBeta中的评估函数，对轮到谁走棋是敏感的。 也就是说： 在Minimax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋评估值仍是100。 但在Negamax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋时评估值要为-100。
谈搜索算法的剪枝优化 许晋炫 【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧。首先由回溯法解决迷宫问题展开论述，介绍了什么是剪枝；而后分析剪枝的三个原则棗正确、准确、高效，并分别就剪枝的两种思路：可行性剪枝及最优性剪枝，结合例题作进一步的阐述；最后对剪枝优化方法进行了一些总结。 【关键字】搜索、优化、剪枝、时间复杂度 引论 在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。 搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。 所以，对程序进行优化，就成为搜索算法编程中最关键的一环。 本文所要讨论的便是搜索算法中优化程序的一种基本方法棗“剪枝”。 什么是剪枝 相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的： 1、这个方向有路可走，我没走过 2、往这个方向前进 3、是死胡同，往回走，回到上一个路口 4、重复第一步，直到找着出口 这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。 我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？ 答案是：可以的。 剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。 搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。 剪枝的原则 1、正确性 正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也
ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2005年第45卷第S1期 2005,V o l.45,N o.S15/39 1748-1752 最大频繁项集挖掘中搜索空间的剪枝策略 马志新, 陈晓云, 王 雪, 李龙杰 (兰州大学信息科学与工程学院,兰州730000) 收稿日期:2005-05-20 基金项目:国家自然科学基金资助项目(60473095)作者简介:马志新(1973-),男(汉),甘肃,副教授。 E-mail:mazhx@lz https://www.doczj.com/doc/aa4046129.html, 摘 要:最大频繁项集挖掘可以广泛应用在多种重要的Web 挖掘工作中。为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略。这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝。应用该策略,对M A FI A 算法进行改进优化。实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原M AF IA 算法提高3～5倍。 关键词:W eb 挖掘;最大频繁项集;剪枝策略;搜索空间中图分类号:T P 311文献标识码:A 文章编号:1000-0054(2005)S 1-1748-05 Pruning strategy for mining maximal frequent itemsets MA Zhixin ,CHE N Xiaoyun ,WANG Xue ,LI Lon gjie (School of I nformation Science and Engineering ,Lanzhou University ,Lanzhou 730000,China ) Abstract :M in ing maximal frequent itemsets is a fundamental problem in man y practical w eb m ining ap plications.T his paper presen ts ESEquivPS (exten sion sup por t equivalency pruning strategy),a n ew search space p runing s trategy for mining m axim al frequent itemsets to effectively reduce the s earch s pace.ESE qu ivPS w as based on a depth-first travers al of lexicographic su bset en umer ation tree and uses equivalency of item's ex tension supports to pru ne s earch space.Furthermore,th e M AFIA (m axim al frequen t items et alg or ith m)w as improved by u sing ESEquivPS.T he ex perimental r esu lts show that ES EquivPS can efficiently redu ce the search space.E specially on s pars e dataset w ith longer items ets ,the siz e of search s pace can be trimmed off by 2/3and n ew algorithm runs around three to five times fas ter th an previou s M AFIA algorithm. Key words :w eb m ining; maximal frequent items ets ; pruning strategy;search space 频繁项集挖掘是一类重要的数据挖掘问题,可以广泛应用在客户行为模式分析、网页关联分析、日志分析和网络入侵检测等重要的Web 挖掘工作中。 该问题描述如下:给定事务数据库D ,项目集合I 和用户指定的支持度阈值 ,频繁项集挖掘是在D 中找出支持度大于或等于阈值 的所有项集。 典型的频繁项集挖掘算法是A priori 以及在此基础上的各种改进算法[1],该类算法采用自底向上广度优先的思想,依次计算出所有的频繁1项集,频繁2项集,直到找出所有的频繁项集。当出现大量长的频繁项集时,该类算法代价很高,需要多次扫描数据库并且产生大量的候选项集,对于长度为m 的频繁项集需要枚举出所有可能的2m -2个子集,出现组合问题,导致算法效率低下或无法计算。因此,最大频繁项集挖掘和封闭频繁项集挖掘方法受到该研究领域的重视,先后提出多种重要的最大频繁项集挖掘算法和封闭频繁项集挖掘算法[27]。 如何有效地进行搜索空间剪枝是最大频繁项集挖掘研究工作的一个核心[6]。本文提出了一种新的搜索空间剪枝策略:扩展支持度相等性剪枝策略ESEquivPS (ex tension support equivalency pruning strateg y ),该策略基于词典序子集枚举树,利用树中子节点与父节点的扩展集中相同项的扩展支持度相等的特性,对搜索空间进行削减。该策略可以方便的应用到各种最大频繁项集挖掘算法中,大幅度提高算法的效率。本文结合ESEquivPS 对MA FIA 算法进行了优化改进,并在不同特征的Web 数据集上进行了实验验证。实验结果表明,该剪枝策略可以有效削减搜索空间,改进后的算法效率明显优于原有的MAFIA 算法。 1 最大频繁项集挖掘与搜索空间剪枝策略 最大频繁项集挖掘问题具体描述如下。
下面我们举一个例子——Betsy 的旅行(USACO)。 题目简述：一个正方形的小镇被分成N 2个小方格，Betsy 要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N ，计算出Betsy 能采用的所有的旅行路线的数目。 实际上，由于Betsy 的每一次移动，只会影响到附近的格子，所以每次执行剪枝判断时，应当只对她附近的格子进行检查： 对于第一个剪枝条件，我们可以设一个整型标志数组，分别保存与每个格子相邻的没被经过的格子的数目，Betsy 每次移动到一个新位置，都只会使与之相邻的至多4个格子的标志值发生变化，只要检查它们的标志值即可。 而对于第二个剪枝条件，处理就稍稍麻烦一些。但我们仍然可以使用局部分析的方法，即只通过对Betsy 附近的格子进行判断，就确定是否应当剪枝，下图简要说明了剪枝的原理： 上图给出了可以剪枝的三种情况。由于Betsy 到过的所有格子都一定是四连通的，所以每种情况下的两个白色的格子之间必定是不连通的，它们当中必然至少有一个是属于某个孤立区域的，都一定可以剪枝。 一、 优性剪枝 下面举一个应用最优性剪枝的典型例题——最少乘法次数。 题目简述：由x 开始，通过最少的乘法次数得出n x ，其中n 为输入数据。（参见参考书目1） 因为两式相乘等于方幂相加，所以本题可以等效的表示为：构造一个数列{}i a ，满足 ???><<=+==)1(),1()1(1i i k j a a i a k j i 要求n a t =，并且使t 最小。 我们选择回溯法作为本程序的主体结构：当搜索到第i 层时，i a 的取值范围
搜索中的剪枝优化 在11+-i a 到2*1-i a 之间，为了尽快接近目标n ，应当从2*1-i a 开始从大到小为i a 取值，当然，选取的数都不能大于n 。当搜索到n 出现时，就得到了一个解，与当前保存的解比较取优。最终搜索结束之后，即得到最终的最优解。 如果按上述结构直接进行搜索，效率显然很低。因此，我们可以考虑使用最优性剪枝进行优化： 优化之一：当然首先要建立估价函数。由于使数列中的最大数加倍无疑是最快的增长方式，所以一种最简单的估价函数为（设数列中当前的最大者是i a ，即当前搜索深度为i ）： ????? ?=i a n h 2log 然而，这个估价函数的准确性太差，特别是当i a 大于2 n 时，h 只能等于1，根本不能发挥剪枝的作用。因此，无论是深度优先的回溯法还是宽度优先的A*搜索方法，只要还使用这个估价函数，其优化效果都比较有限。 下面，我们再讨论一些进一步的优化手段—— 优化之五：当数列中的当前最大数i a 超过2 n 后，原估价函数就难以发挥作用了。但是，此后的最优方案，实际上就等价于从1a 到i a 这i 个数中，选出尽可能少的数（可重复），使它们的和等于n 。这个问题已经可以使用动态规划方法来解决。这样得到的“估价函数”不但完全准确，甚至直接就可以代替后面的搜索过程。这里也体现出了搜索和动态规划的优势互补。 二、“最少乘法次数”的估价函数的改进： 最初的估价函数的设计思路实际上是在当前数列i a a ,,1 的基础上理想化的构造i p i i a a a 2,,4,2 ，当i p i p a n a 122+<<时，原估价方法认为只需再进行一次加法，即找一个数与i p a 2相加就够了。 然而，这只是保证了能够得到大于等于n 的数，并不一定恰好得到n 。我们可以作如下分析： 首先，任何一个自然数i 都可以表示成),()12(2___-∈+Z m k m k 的形式，我们可以设)(i k 表示一个自然数i 所对应的k 值。显然，对于任何两个自然数a 和b ，都有()()(){}b k a k b a k ,min ≥+（我们由此可以很容易的联想到“奇+奇=偶，偶+偶=偶，奇+偶=奇”的性质）。 然后，我们再研究前述估价时所构造的数列： i p i i i a a a a a a 2,,4,2,,,,21 （其中，i p i p a n a 122+<<） 在应用新的剪枝判断之前，我们应当先检验()()??p a a n i i ≥+-12/log ，这个条件可以保证只有构造上述数列才是最优的。 若存在自然数()p j j ≤≤1，使得() ()n k a k i j >2，由()()(){}b k a k b a k ,min ≥+， 则有()()()()()p t j n k a k a k a a k i j i t i p i t ≤≤>≥≥+2222 n a a i p i t ≠+∴22 （()()b k a k =是b a =的必要条件） 即i p i j a a 2,,2 中的任何一个数与i p a 2相加都不可能得到n 。 所以，如果i j i p a a n 122->-，则在得到i p a 2后，至少还需要再进行两次加法
火力网的搜索优化方案 搜索是万能算法，如果加上剪枝，它将变的更加完美，必要的剪枝可以使程序的效率成几何倍数的增长，所以可以说剪枝是搜索的生命。 问题：火力网（见附录一） 初解：由于最大节点数只有10*10=100个，因此考虑用深度优先搜索解决。在最初的棋盘上对所有的空地放上或拆除碉堡，用类似八皇后问题的回溯法很容易编出程序（见附录二）。但发现到当n>=8时，程序已经不能很快出解了，剪枝势在必行。 剪枝一：改变数据结构，使数据结构为算法服务。 原来用的是二维数组，在搜索时不免因为大量的非空节点（有墙或被控制）使找空节点的效率十分低下。方案：可以将所有的空节点放在一个数组中，记录x,y坐标。 剪枝二：避免重复的搜索，使搜索有序。（下界剪枝） 有时可能出现第I次搜索先选了A格子，后选了B格子，而又在第J次搜索先选了B格子，后选了A格子 为了避免重复的搜索，可以在每次选择一个空地放之后在编号大于它的空地中找下一个可放的位置，这样减去了大量的重复。 剪枝三：对不可能大于Max的进行剪枝。（上界剪枝） 比如现在已经放了n个碉堡，还剩m块空地，若n+m<=Max，那么就不可能大于Max了。 所以，需要对全部未扩展节点+已扩展节点仍不能大于Max的进行剪枝。
***以上只是对于搜索的最一般剪枝方法，与题目关系不大，以 下是针对题目的剪枝。 剪枝四：对横路径数&竖路径数剪枝。 对于一个题目中的图，如果可以看成由空地组成的路径，就可以计算出有多少个横路径和竖路径。比如 122 3333 44 5555 有5条横路径 156 1356 56 2456 6条竖路径。 把题目中的空地抽象成横路径和竖路径后，由于每条路径最多放一个碉堡。根据抽屉原理，碉堡数不超过横路径数或者竖路径数。如果找到方案可以达到最大，那么就输出结束。（这样比 n*n/2更加优秀）。
搜索问题 计算机学院2006级师范班程文华 搜索被称为“通用的解题法”，在算法和人工智能方面占有非常重要的低位，特别是在各类ACM程序设计比赛中非常常见，在题目中一般位于中间位置，作为中等难度的题目出现。因此我们需要着重掌握各类的搜索算法，才能面对各类即将到来的ACM大赛。“只要功夫深，铁棒磨成针”，“冰冻三尺，非一日之寒”，要能熟练的掌握和AC比赛中的题目，必须在熟练掌握各类搜索算法的基础上勤加练题，也是唯一的好方法。 本次讲解中，首先给出有关搜索的基本概念，然后针对各类专题，讲解具体的几个例题并加于分析（注：题目全部选自poj中的题目）。 一概念介绍 状态（state）问题在某一时刻的进展情况的数学描述。 算符（operator）/ 状态转移问题从一种状态变换成另一种(或几种)状态的操作。 解答树搜索的过程实际是在遍历一个图，它的结点就是所有的状态，有向边对应于算符，而一个可行解就是一条从起始节点出发到目标状态集中任意一个结点的路径。特个图称为状态空间（state space），这样的搜索称为状态空间搜索（Single-Agent Search），得到的遍历树称为解答数。 基本搜索法： 枚举枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。枚举算法的特点比较单纯，往往容易写出程序，也容易证明算法的正确性和分析算法的时间复杂度，可以解决一些很小的问题。它的缺点是效率特别低，往往很多题目不能用枚举方法，用了只会超时。所以它适应于容易找到状态并且状态较少的题目。没有信心确定其状态较少，请勿立即动手写程序！ 深度优先搜索DFS（有时称为回溯法）遵循的搜索策略是尽可能深地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探索到的边，就沿此边继续搜索下去。当结点V的所有边都已被探寻过时，搜索将回溯到发现结点V有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择另一个未发现的结点作为新的源结点重新上面的过程，直至所有的结点都搜索到。