A Knee_Guided Evolutionary Algorithm for Compressing Deep Neural Networks （KGEA）解读

• 1、主要思想
• 2、模型压缩
• • 2.1 滤波器剪枝
  • 2.2 衡量滤波器重要性
• 3、KGEA
• • 3.1 NSGA-II
  • 3.2 KGEA
  • 3.3 KGEA算法
• 4、实验
• 5、总结
• 6、参考文献

原论文：A Knee-Guided Evolutionary Algorithm for Compression Deep Neural Networks

1、主要思想

这篇文章的最主要的思想就是将模型压缩的问题转化为了多目标优化的问题，然后用改进的遗传算法来求解这个问题。

主要涉及三方面的知识：模型压缩、多目标优化、遗传算法。以下分别讲解。

2、模型压缩

2.1 滤波器剪枝

这篇文章使用的模型压缩方法是滤波器剪枝方法 [2] 。其过程如下：

我们知道，在卷积神经网络中，卷积层是由多个滤波器组成的，而每个滤波器也是由多个卷积核组成的。而且，每一层的滤波器数量是等于该层的输出特征图数量的，也就是等于输出通道；而每个滤波器的卷积核数量则等于输入特征图的数量，即等于输入通道。

所以，为了保持这种结构上的对应关系，在对滤波器剪枝时，在该层剪掉一个滤波器，就应相应的把该层的输出通道给剪掉，且下一层对应的每个滤波器的卷积核也应该被剪掉。像上图那样。就像这张图中的虚框一样。经过这样的剪枝后，网络的参数大大减小了。这就是滤波器剪枝的过程。

在滤波器剪枝研究中，最重要的问题就是如何去选择那些被剪的滤波器。或说，如何衡量滤波器的重要性。

2.2 衡量滤波器重要性

一般的做法：

• 基于滤波器的权重值： 如求权重和（Weight Sum, WS）[2]，和越大，则越重要；
• 基于激活函数： 基于激活函数：如计算激活函数输出中0占的比例（Average Percentage of Zeros，APoZ) [3] ;
• 基于重建误差： 如通过最小化特征重建误差来确定哪些滤波器需要裁剪（ThiNet）[4] 。

本文没有使用以上的方法，而是根据一个最直接的指标——神经网络的性能来衡量滤波器的重要性。同时考虑网络性能和滤波器数量，以找到平衡两者的最优结构。

滤波器重不重要，网络性能最能说明问题。剪掉一个滤波器，如果性能变得很差，那说明这个滤波器很重要，但是如果性能几乎不变，，那就说明这个滤波器不重要，可以剪掉。所以用网络性能来衡量滤波器重要性是非常直接且有效的。

既然是模型压缩问题，滤波器数量当然是要考虑的，我们希望得到一个参数量更小的网络。所以，要同时优化网络性能和滤波器数量这两个目标，这就成为了一个多目标优化的问题了。

这就是文章给出的这个问题的数学表达。

其中，C是cost，也就是网络的损失函数，D是数据集。W是滤波器权重，M是掩膜，其元素全为0或1。M乘W的意思就是：若M全为0则，则乘上W后W就变为0，就相当于把这个滤波器剪掉了。若全为1，则W不变，也就是保留这个滤波器。这样就能达到剪枝和保留的作用了。

第二个式子用1-范数来计算滤波器数量，即计算有多少元素全为1的M的个数，有多少个元素全为1的M，那就有多少个滤波器保留下来。

就这样，通过这个式子，滤波器剪枝问题就变成了一个多目标优化的问题。接下来，就是如何去求解这个问题了。

3、KGEA

本文使用的求解办法是膝盖导向进化算法（ Knee_guided Evolutionary Algorithm, KGEA）。它是进化算法的一种，是对非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm, NSGA-II） [5] 的改进，主要就是提出使用最小曼哈顿距离（Minimum Manhattan Distance, MMD） [6] 来计算种群中的一个最优解，即膝盖knee，然后以Knee为进化方向，选择优秀的个体保留到下一代种群中。这就是KGEA的主要思想。

3.1 NSGA-II

在讲解NSGA-II前，有些概念需要被知道。

• 支配与非支配： 如果任何两个解S1和S2对所有目标而言，S1均优于S2，则称S1支配S2；若S1不被其他解支配，则S1即为非支配解，即不被支配的解。

如这里有4个个体ABCD，A和B相对于C和D来说，在网络损失和滤波器数量上都要好，且A和B之间没有说哪一个非常好的，所以A和B就是非支配解。同样的，C相对于D来说也是非支配解。

• 帕雷托前沿面： 就是在找到非支配解后，这些解所形成的曲面就是帕雷托前沿面（Pareto Front，PF） 。

如这里，AB 就构成一个PF，C构成一个PF，D一个PF。因为这里只有两个目标，所以PF是曲线。当目标数较多时，PF就是曲面。

• 非支配排序： 对帕雷托前沿面从非支配到被支配进行排序。非支配解排在前面。

这里，AB构成的PF排第一，接着是C，到D。

可以看到，PF排名靠前的个体在各方面都比排名靠后的个体要优秀的。

所以，NSGA-II的思想就是将这些PF排名靠前的个体作为精英保留到下一代，使种群往更优的方向发展，加快搜索到最优解的速度。

• 算法
  

算法: NSGA-II

1. 由遗传算法产生种群Pt；
2. 种群个体变异，产生的子代Qt和父代Pt一起构成新的种群Rt；
3. 对种群进行非支配排序，保留**帕雷托前沿面（PF)**排名靠前的个体；
4. 若保留的个体超出种群个数，则对PF最后的个体进行拥挤距离计算，保留拥挤距离较大的个体；
5. 保留下来的个体构成新种群Pt+1，继续遗传进化；

这就是NSGA-II的过程。首先遗传算法，产生种群，然后变异产生子代，子代和父代合并为新的种群，对种群进行非支配排序，保留PF靠前的个体。

但这里有个问题就是，要保留的个体可能超出种群的数量。所以这里，NSGA提出对要保留的最后一个PF里的个体再进行一次拥挤距离排序。

所谓拥挤距离，就是计算一个解与最近两个解的在各个目标上的距离。如图中的i 。计算公式如上，简单理解就是计算这个长方形的周长的一半。从上图可以看出，i与i-1、i+1在f1上的距离就是长方形的长，f2上就是宽，所以就是长方形周长的一半。

拥挤距离表示的是解的相似度。如果保留的解都是相似度高的，则容易陷入局部最优中，所以，为了保持种群的多样性，增加探索，所以要保留那些拥挤距离大的个体。

这就是整个NSGA-II的一个过程了。

3.2 KGEA

• 思想

膝盖进化算法在NSGA-II的基础上，提出拥挤距离排序阶段，使用膝盖导向作为主要的个体选择方法，而拥挤距离则作为辅助方法，然后综合这两种方法来选择要保留的个体。

所谓的膝盖是指种群中在各个目标上都比较平衡且优秀的个体。一般就是那个拐点，像人的膝盖一样，所以叫做膝盖，如下图。因为膝盖是平衡了各个目标的最优解，所以将其作为一个进化方向，保留其附近的个体，能让种群发展更好，更快收敛。

怎么找到这个膝盖呢？文章提出使用最小化曼哈顿距离（Minimum Manhattan Distance, MMD） 来求这个膝盖。其公式如下，其实曼哈顿距离就是1-范数。这个公式的意思就是求每个点与理想点组成的向量的模，就是距离，距离最小的点就是膝盖点，这个向量就是膝盖向量knee vector。

x ∗ = arg min ⁡ x ∣ ∣ f ( x ) L − Z min ⁡ L ∣ ∣ 1 w h e r e   L = max ⁡ f ( x ) − min ⁡ f ( x ) , Z min ⁡ = min ⁡ f ( x ) ,   ∣ ∣ ⋅ ∣ ∣ 1   r e p r e s e n t s   t h e   M a n h a t t a n   n o r m . \small x^* = \argmin_x ||{f(x)\above{1pt} L} -{Z^{\min} \above{1pt} L}||_1 \\ \small where \space L=\max f(x)-\min f(x),\\ \small Z^{\min }=\min f(x), \space ||\cdotp||_1 \space represents \space the \space Manhattan \space norm. x∗=xargmin​∣∣Lf(x)​−LZmin​∣∣1​where L=maxf(x)−minf(x),Zmin=minf(x), ∣∣⋅∣∣1​ represents the Manhattan norm.

又因为用MMD来求膝盖向量的时候需要边界信息，即公式里的L和Z^min ，所以边界周围的点也被认为是重要的。

因此，这个膝盖导向就变成了，以两个边界和一个膝盖向量为参考向量，综合选择与他们相近的个体保留到下一代。

如何衡量这个近，本文使用的就是计算和这三个参考向量的夹角，并分别排序，保留那些排名靠前的个体。

这就是这篇膝盖导向算法的改进过程。

3.3 KGEA算法

这就是整个KGEA的算法。

KGEA和NSGA-II的不同就是这些红框标出来的地方。首先利用MMD求膝盖向量，然后和两个边界一起作为参考向量。然后在要保留的PF超过群体数量后，对最后一个PF的个体再进行一次排序，就是计算每个个体和那三个参考向量的角度，然后进行排序，作为主要的选择依据。同时，这里也还是使用了NSGA-II里面的拥挤度排序，作为一个辅助选择依据。最后综合考虑这两个排序，保留那些排序靠前的个体到下一代。

4、实验

为验证KGEA的效果，文章做了实验。

使用KGEA对一个训练好的全卷积LeNet进行剪枝，并在MNIST数据集上进行验证。


这就是实验完后的结果。在剪枝后，还对剪枝后的网络进行了微调，也就是再训练了几个回合。

可以看到，剪枝后，参数的数量已经减少了81.34%，而且，经过微调后的网络的精度反而还提高了。

这足以说明这篇文章提出的方法的有效性。这也能够说明，神经网络确实有很多参数是冗余的。所以研究神经网络的压缩是有必要的，对神经网络自组织原理的研究也是很有必要的。

5、总结

好了，这就是这篇文章的所有内容了。

总的来说，就是将卷积神经网络滤波器剪枝这样一个模型压缩的问题，转化为了一个多目标优化的问题，也就是同时考虑了网络的性能和滤波器的数量这两个目标，然后用改进的遗传算法即KGEA来求解这个问题。

6、参考文献

[1] A Knee-Guided Evolutionary Algorithm for Compression Deep Neural Networks
[2] Pruning Filters for Efficient Convnets
[3] Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures
[4] ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression
[5] A Fast and Elitist Multiobjective Genetic Algorithm：NSGA-II
[6] Minimum Manhattan Distance Approach to Multiple Criteria Decision Making in Multiobjective Optimization Problems