开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【CVPR 2021】剪枝篇（二）：Convolutional Neural Network Pruning with Structural Redundancy Reduction -> 正文阅读

[数据结构与算法]【CVPR 2021】剪枝篇（二）：Convolutional Neural Network Pruning with Structural Redundancy Reduction

【CVPR 2021】剪枝篇（二）：Convolutional Neural Network Pruning with Structural Redundancy Reduction

论文地址：
主要问题：
主要思路：
理论分析：
- 基本定义：
- 公式和声明：
具体实现：
1-覆盖面数的估值：
- 卷积选择策略：
实验结果：
联系作者：
我的公众号：

论文地址：

https://arxiv.org/abs/2104.03438

主要问题：

现有的模型剪枝工作通常集中于删除网络中最不重要的卷积核，以实现紧凑的网络结构

在这项研究中作者声称结构冗余比寻找不重要的卷积核起更重要的作用

主要思路：

作者首先从冗余减少的角度对模型剪枝问题进行统计建模，发现结构冗余最多的层中的剪枝优于在所有层中修剪最不重要的卷积核

通过这一发现，我们提出了一种基于结构冗余减小（SSR）的层自适应通道剪枝方法，通过为CNN的每个卷积层建立一个图，并使用与图相关的两个量（即 $? ?$ 覆盖数和商空间大小）作为每一层冗余的测量

理论分析：

基本定义：

假设我们有两个CNN，它们分别带有 $m$ 和 $n$ 个卷积，其中 $n > > m$

假设 $\{\xi_1,\xi_2,...,\xi_m\}$ 和 $\{\eta_1,\eta_2,...,\eta_n\}$ 是一维正随机变量（RV），表示每个卷积对网络性能的贡献

例如，卷积的贡献可以表示为修剪该卷积后训练精度下降或训练损失变化的绝对值

为了方便起见，我们称这两层为 $ξ$ 层和 $η$ 层

公式和声明：

如果一个层具有更高的冗余，那么我们将裁剪该层中的卷积，无论是随机地还是选择性地，都优于修剪所有层中最不重要的卷积

我们选取正的常量 $a, b > 0$ ，并使用随机事件 $(\sum_{i=1}^m\xi_i\geq a)$ 和 $(\sum_{i=1}^n\eta_i\geq b)$ 来表示 $ξ$ 层和 $η$ 层是否“表现的好”

因此系统的性能（即整个神经网络） $p$ 就可以通过上述两个事件的概率的总和来衡量

并且 $p_o$ 越大表示由 $p_o)$ 表示的系统性能越好

一个自然的问题是，如果我们从网络中裁剪某一个卷积，即从 ${ξ_1,ξ_2,...,ξ_m,η_1,η_2,...,η_n\}$ 中删除一个变量，系统性能如何变化？

作者将上述裁剪行为分成以下五种情况：

没有剪枝；
在 $η$ 层中随机裁剪一个卷积，而没有失去一般性（我们假设最后一个 $η_n$ 被裁剪）；
裁剪 $η$ 层中最不重要的过滤器 $\underlineη=min\{η_1,...,η_n\}$ ；
裁剪 $ξ$ 层中最不重要的过滤器 $\underlineξ=min\{ξ_1,...,ξ_n\}$ ；
裁剪全局最不重要的卷积，即 $min\{\underlineξ,\underlineη\}$ ；

上述五种情况的系统性能公式分别如下：

$1.\space\space p_o=P(\sum_{i=1}^m\xi_i\geq a)+P(\sum_{i=1}^n\eta_i\geq b)$

$2.\space\space p_{ηr}=P(\sum_{i=1}^m\xi_i\geq a)+P(\sum_{i=1}^{n-1}\eta_i\geq b)$

$3.\space\space p_{\underlineη}=P(\sum_{i=1}^m\xi_i\geq a)+P(\sum_{i=1}^n\eta_i-\underlineη\geq b)$

$4.\space\space p_{\underlineξ}=P(\sum_{i=1}^m\xi_i-\underlineξ\geq a)+P(\sum_{i=1}^n\eta_i\geq b)$

$5.\space\space p_g=\frac{m}{m+n}p_{\underlineξ}+\frac{n}{m+n}p_{\underline\eta}$

其中 $a$ 和 $b$ 可以被认为是一个阈值，只要一层中卷积的总贡献大于阈值，我们就认为它就没有性能损失

而如果一个层冗余过多（在模型的上下文中有太多卷积），那么修剪一些卷积后的总贡献很可能仍然大于阈值

值得注意的是 $0\le\eta_n-\underline\eta\le\eta_n$ ，即：

$P(\sum_{i=1}^{n-1}\eta_i\geq b)\le P(\sum_{i=1}^{n}\eta_i-\underline\eta\geq b)\le P(\sum_{i=1}^{n}\eta_i\geq b)$

也就是说 $p_{\eta r}\le p_{\underline\eta}\le p_o$

对于 $η$ 层中的卷积，我们自然地假设卷积对网络性能的贡献不可能是无限的，即卷积贡献的方差是一致有界的：

$\exist C_1>0,s.t. \space\mathbb{D}_{\eta_i}\le C_1,i=1,2,...,n$

由切比雪夫不等式，对于任意 $\epsilon>0$ ，有：

$P(\frac{1}{n}|\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)|\ge\epsilon)\le\frac{\mathbb{D}(\sum^n_{i=1}\eta_i)}{\epsilon^2n^2}$

我们可以得到：

$Cov(\eta_i,\eta_j)\le\sqrt{\mathbb{D}_{\eta_i}\cdot\mathbb{D}_{\eta_j}}\le C_1$

我们进一步定义，在 $\eta$ 层中共有 $C_2n(0\le C_2\le1)$ 对相关卷积，也就是说：

$\#\{(i,j):Cov(\eta_i,\eta_j)\ne0,i\ne j,\space i,j=1,...,n\}\le C_2n$

这样我们就可以得到：

$\begin{aligned} \mathbb{D}(\sum^n_{i=1}\eta_i)&=\sum^n_{i=1}\mathbb{D}\eta_i+\sum_{i\ne j}Cov(\eta_i,\eta_j) \\ &\le C_1n+C_1C_2n=C1(1+C_2)n \end{aligned}$

再结合上式，有：

$P(\frac{1}{n}|\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)|\ge\epsilon)\le\frac{C_1(1+C_2)}{\epsilon^2n^2}\rightarrow0$

这表示假定 $\eta$ 层中卷积数量 $n$ 足够大（例如 $n>\frac{2b}{\epsilon_o}$ ）， $\frac{1}{n}\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)$ 概率上收敛到 $0$ ，也就是说：

$\frac{1}{n}\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)\stackrel{P}{\rightarrow}0$

我们考虑卷积的贡献应该是整数，但是它可以非常小

也就是说对卷积贡献的期望具有统一的正下界：

$\exist \epsilon_0>0,s.t. \space\mathbb{E}_{\eta_i}\le \epsilon_0,i=1,2,...,n$

根据之前的推导，我们可以得出：

$\begin{aligned} P(\frac{1}{n}\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)>-\frac{\epsilon_0}{2})&=P(\sum^n_{i=1}\eta_i>\sum^n_{i=1}\mathbb{E}\eta_i-\frac{\epsilon_0}{2}n) \\ &=P(\sum^n_{i=1}\eta_i>\frac{\epsilon_0}{2}n+\sum^n_{i=1}(\mathbb{E}\eta_i-\epsilon_0)) \\ &\le P(\sum^n_{i=1}\eta_i>\frac{\epsilon_0}{2}n)\le P(\sum^n_{i=1}\eta_i>b) \end{aligned}$

如果有 $n\rightarrow +\infty$ ，取极限并且考虑 $\frac{1}{n}\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)\stackrel{P}{\rightarrow}0$ ，那么我们可以得到：

$lim_{n\rightarrow\infty}P(\sum^n_{i=1}\eta_i>b)\geq lim_{n\rightarrow\infty}P(\frac{1}{n}\sum^n_{i=1}(\eta_i-\mathbb{E}\eta_i)>-\frac{\epsilon_0}{2})=1$

$lim_{n\rightarrow\infty}P(\sum^n_{i=1}\eta_i-\eta_r>b)\geq lim_{n\rightarrow\infty}P(\frac{1}{n}\sum^n_{i=1}\eta_i-\underline{\eta}>b)=1$

然后如果 $n$ 足够大，我们又有 $p_{\eta r}\approx p_{\underline{\eta}}\approx p_o$

注意 $p_{\underline{\xi}}\leq p_o\approx p_{\underline{\eta}}$ 并且 $p_g$ 是 $p_{\underline{\xi}}$ 和 $p_{\underline{\eta}}$ 的加权均值

因此我们可以得到： $p_{\underline{\xi}}\leq p_g\leq p_{\underline{\eta}}$

这表明（即使是随机的）修剪层中冗余更大的卷积的性能优于在所有层中修剪最不重要的卷积

这个结论依赖于 $n \to + \infty$ 的假设，而且这个假设可以在现实应用中放松，这样 $p_η≥p_g$ 仍然近似有效（尽管不是在每个剪枝过程的选择步骤中）

具体实现：

基本符号：

模型剪枝：

假设一个CNN有 $L$ 个层

对于第 $i$ 层，输入和输出通道数分别表示为 $N_i$ 和 $N_{i+1}$

因此 CNN 的参数 $w$ 就可以写作： $\{W^{(i)}\in\mathbb{R}^{N_{i+1}×N_i×h_i×w_i},i=1,2,...,L\}$ ，其中 $h_i$ 和 $w_i$ 分别是卷积核的高和宽

通道剪枝的目标是找到一组在某些目标函数上优化的参数，例如 $W`||_0<K$ ，其中 $||\cdot||_0$ 表示 $l_0$ 正则， $K$ 用来限制 $W ‘$ 中非零卷积核数目

根据不同的配置，目标函数可以是最小化CNN的成本函数、训练精度的下降或重构误差等

图理论：

假设 $X$ 是一个有限集，一个无向图可以表示为 $(X, E)$ ，其中 $E$ 是 $X \times X$ （或者写作 $\{(x,x)：x\in X\}$ ）的一个对称子集

我们吧 $x\in X$ 称作一个节点， $(x,y)\in E$ 称作边

对于 $x,y\in X$ ，从 $x$ 到 $y$ 的路径是一个有限列表 $\{x_0,x_1,...,x_n\}\subset X$

而且如果上述路径存在，该路径也许不是唯一的

假设 $d (x, y)$ 是从 $x$ 到 $y$ 的最短路径，并且当 $x, y$ 不可达时记作 $d(x,y)=+\infty$

那么 $d (x, y)$ 就可以看做一个整数值度量

补充：节点的 $x$ 度是与节点 $x$ 直接相连的边数

整体架构：

这个方法侧重于测量每个层中存在多少冗余，并从最冗余的层中修剪滤波器：

在这里插入图片描述
为了测量网络中的结构冗余，我们首先为每一层构建一个无向图，其中每个顶点表示一个卷积，并用卷积权重之间的距离定义边

我们使用与图相关的两个量（即商空间大小和 $?$ 覆盖数），作为每个图中存在多少冗余的度量，即每一层中存在的冗余

在每个步长的图建立和冗余量化之后，我们从具有最冗余的图中随机删除一个顶点及其相关边

然后我们重新计算下一次迭代的图重建后的冗余度

上述过程一直持续到达到优化目标（例如裁剪掉一定数量的卷积）

最后，我们根据具有一定卷积选择准则的每个图中剩余的顶点数对每一层的卷积进行裁剪

注意在裁剪阶段卷积在每个层中单独排序，而不是跨所有层进行全局排序，而且由于冗余识别阶段在每一层中选择了不同数量的卷积，该方法是一种层自适应方法

建立冗余图：

为了说明如何为卷积层构建一个图，我们使用 $X$ 来表示某一层 $W^{(i)}$ 的卷积的权重

我们首先展开（就是flatten操作）和标准化卷积的权重，将它们的长度更改为 $1$

这样的话 $X$ 就可以看做是变成了 $\mathbb{R}^n$ 空间中 $n$ 维单位球体的一个有限子集 $\mathbb{S}^n=\{x\in\mathbb{R}^n:|x|=1\}$

因此假设 $X$ 中的元素是不同的，我们可以将 $X$ 上的图定义如下：

我们选取正实数 $\gamma>0$ ，并将 $X$ 上的边集定义如下：

$E=\{(x,y)\in X×X \setminus\Delta :|x-y|/\sqrt{b}\le\gamma\}$

其中 $\Delta=\{(x,x):x\in X\}$ 是 $X$ 的对角， $∣ x ? y ∣$ 是 $\mathbb{R}^n$ 上的欧氏距离

这样我们就得到了图 $(X, E)$

根据定义 $(x, y) \in E$ ，如果 $γ$ 很小，意味着 $x$ 和 $y$ 近似相等

$?$ 覆盖数：

我们上面的定义表示 $(X, d)$ 是一个度量空间，其中 $d$ 是之前定义的图的一个度量

假设 $? > 0$ 是一个固定的自然数，子集 $X_0\subset X$ 被称作 $X$ 的 $?$ 覆盖数，如果 $X\subset\bigcup\{B(x`,?):x`\in X_0\}$

其中 $B(x`,?)=\{x\in X:d(x`,x)\le ?\}$ 是一个以 $x ‘$ 为中心的半径为 $?$ 的球体

这表示 $X$ 是由球 $KaTeX parse error: Expected 'EOF', got '}' at position 20: …x`,?):x`\in X_0}?$ 覆盖

我们称以下数量为 $X$ 的 $?$ 覆盖数：

$N^c_?(X)=min\{\#X_0:X_0 \space is\space an\space?-cover\space set\space of\space X\}$

图的分解：

图中我们定义等价关系 $x\sim y$ 当且仅当 $x$ 到 $y$ 存在路径

假设 $X/\sim=\{X_1,X_2，。。。，X_k\}$ 是商数空间

这个数学概念意味着：使用等价关系，我们可以将集合 $X$ 分解为一个不相交的并集 $X=X_1∪X_2∪···∪X_k$ ，使同一 $X_i$ 中的元素是等价的

因此我们称数字 $k$ （等价类的总数）为商空间的大小

直观地说 $k$ 就是 $(X, E)$ 的未连接子图的数量

图的冗余：

直观地说，商空间大小和 $?$ 覆盖数越大，表明一组数据越复杂，也就是冗余较少

事实上， $x \in B (x ‘, ?)$ 当且仅当 $d (x, x ’) \leq ?$ ，因此 $x$ 和 $x ‘$ 近似相等

因此， $?$ 覆盖数可以近似地看作是 $X$ 中线性无关的向量的总数

在论文的实现中，作者简单地使用了 $? = 1$ ，因为同时考虑了性能和计算效率

基于上述分析，我们就可以定义图（也就是模型中对应的层）冗余：

$R(X)=\frac{N}{w_1k+w_2N^c_1}$

其中 ${w1,w2\}$ 是平衡 $k$ 和 $N_1^c$ 的重要性的概率权值， $N$ 是卷积的数量

1-覆盖面数的估值：

由于 $?$ 覆盖数的计算是 $N P$ 问题，因此作者提出了一种轻量级的方法来估计 $N_1^c$

假设 $X_0$ 是图 $X$ 的 1-覆盖集，因此 $X_0=N_1^c$

我们通过如下方式估计 $X_0$ 的值：

我们取固定的 $?$ （ $1$ 或 $2$ ），假设 $x^{(?)}_1\in X$ ，满足 $deg(x^{(?)}_1)=max\{deg(x):x\in X\}$

我们定义一个优先序列 ${x^{(?)}_1,x^{(?)}_2,...,x^{(?)}_{n?}\}$ 如下：

如果我们定义了 $x^{(?)}_k$ 那么只有两种可能的情况：（1） $X=\bigcup_{i=1}^kB(x^{(?)}_k,?)$ ，也就是说球 $\{B(x^{(?)}_k,?):1\le i\le k\}$ 的族是 $X$ 的 $?$ -覆盖集，这样我们就可以停止构造这个序列；（2）否则选取 $x^{(?)}_{k+1}\in X\setminus\bigcup_{i=1}^kB(x^{(?)}_k,?)$ 加入序列，满足：