一、算法概述

1.1 svd分解

1.1.1 问题引出：对仿射变换进行降维线性近似

对一个卷积层来说，卷积的输出响应可表示为 $y=Wx$ ，其中 $W$ 扩展成 $(d \times (k \times k \times c+1))$ ， $x$ 扩展成 $(k \times k \times c+1)$ ， $c$ 为输入通道个数， $k$ 为卷积核大小， $d$ 为输出通道个数。

在假设输出响应 $y$ 是一个低秩空间下，存在低秩的矩阵 $M_{d \times d} ( rank(M) < d )$ ，使得 $y=M(y-\overline y)+y$ ，其中 $\overline y$ 为 $y$ 的均值，因此，输出响应可重写为：

$y=\mathbf{M}\mathbf{W}x+b$

其中， $b=y-\mathbf{M}\overline y$ 。低秩的 $M$ 可分解成两个矩阵的乘积，即 $M=PQ^T$ ，其中 $P,Q \in R^{d \times d'}, d'<d$ ，于是可得，

$y=PQ^TWx+b=PW'x+b$

其中， $W'=Q^TW$ 。因此，可使用两个卷积层（卷积核分别为 $W' \in R^{k \times k \times c}$ 和 $P \in R^{1 \times 1 \times d'}$ ）来近似原来的卷积层 $W$ ，该近似的完成还存在两个问题：

$M$ 矩阵如何求解？
如何分解 $M$ ？

$M$ 使用优化问题来求解：

$obj = \min \limits_{M} \sum_{i = 1}^{N} \| (y_i-\overline{y}) - M(y_i-\overline{y}) \|^2$

该优化问题可用svd求解：
令 $Y$ 为减去均值后的N个响应，协方差矩阵 $M=YY^T$ （根据协方差矩阵定义推导）。

2.上述矩阵 $M$ 的分解可用svd: $M=U_{d'}S_{d'}V_{d'}^T$ ,因此 $P=U_{d'}S_{d'}^{1/2}, Q=V_{d'}S_{d'}^{1/2}$

1.1.2 推广：对加入非线性（relu）层的卷积层进行降维近似

上述输出响应近似推广到非线性输出响应的近似，则优化问题可变为：

$obj = \min \limits_{M,b} \sum_{i} \| r(y_i)-r(My_i+b) \|^2_2$
解上述优化问题具有挑战性，因此可用通过求解近似优化问题来求解：

$obj = \min \limits_{M} \sum_{i } \| r(y_i)-r(z_i)) \|^2_2+ \lambda \| z_i- (My_i+b) \|^2_2$

这里当 $\lambda \rightarrow \infty$ 时，等价于原优化问题。使用迭代的方法分别优化 $M,b$ 和 $z_i$

固定 $z_i$ ，求解 $M,b$ ；
当 $z_i$ 固定时，最小化目标函数可得 $b=\overline{z}-M \overline{y}$ ,则优化问题变为：

$obj = \min \limits_{M} \sum_{i } \| (z_i-\overline{z})-M(y_i - \overline y) \|^2_2$

该优化问题与线性时的优化问题相似，但是这里有两个响应集，重写优化问题可得：

$obj = \min \limits_{M} \| Z-MY \|^2_F$
此处的响应集均是减均值之后的结果，该问题可用GSVD求解。

固定 $M,b$ ，求解 $z_i$ ；当 $M,b$ 固定后，可逐元素的优化 $z_i$ ：

$obj = \min \limits_{z_{ij}} (r(y_{ij})-r(z_{ij}))^2+\lambda (z_{ij} - y_{ij}^{'}) \|^2_2$

1.1.3 减小逐层误差累积：非对称分解思路

为了防止底层近似误差累积都深层，采用非对称方法来解决该问题，优化问题变成：

$obj = \min \limits_{M,b} \sum_{i} \| r(Wx_i)-r(MW\hat{x}_i+b) \|^2_2$

其中 $\hat{x}_i$ 是该层的近似输入，因此 $r(MW\hat{x}_i+b)$ 是近似输出。解该优化问题如非线性情况。

1.1.4 选择最优的衰减通道数

上述优化问题中 $d'$ 是决定近似层复杂度的唯一参数，每一层的冗余不同，因此不同层应合理的选择适当的参数值。

经验上PCA能量与分类准确率有关，定义目标函数：

$\varepsilon = \prod _{l} \sum_{a=1}^{d'} \sigma_{l,a}$
$s.t. \sum_{l} \frac{d_l^{'}}{d_l}C_l <=C$

其中， $\sigma_{l,a}$ 表示 $l$ 层第 $a$ 大的特征值， $C_l$ 是近似之前的复杂度， $C$ 是期望的近似之后的总复杂度。该优化可用贪心算法求解。

1.2 卷积核分解

1.2.1 scheme2

基于事实：不同的卷积核与通道之间存在冗余。

基于思想：每个卷积层可分解成一系列的两个子空间矩形卷积层，第一个卷积层有 $K$ 个 $k \times 1$ 卷积核，第二层有 $N$ 个 $1 \times k$ 卷积核。

因此原始的卷积核 $W_n * z = \sum _{c=1}^{C} W_n^c * z^c$ 可近似为：

$W_n * z \approx h_n * V=\sum_{k=1}^{K}h_n^k *(v_{k}*z)=\sum_{k=1}^{K}h_n^k *\sum_{c=1}^{C}(v_{k}^c*z^c) = \sum_{c=1}^{C}[\sum_{k=1}^{K}h_n^k *v_{k}^c]*z^c$
因此能得到优化问题：

$obj = \min \limits_{\{h_n^k \},\{v_k^c\}} \sum_{n = 1}^{N} \sum_{c = 1}^{C} \| W_n^c - \sum_{k=1}^{K}h_n^k*v_k^c\|^2$

使用共轭梯度法解该优化问题。

1.3 组合使用svd分解与卷积核分解

思路：先使用核分解将卷积层分解成 $k \times 1$ 和 $1 \times k$ 的卷积核，再使用通道近似的方法，将 $1 \times k$ 的卷积核近似成 $1 \times k$ 和 $1 \times 1$ 的卷积核。

二、实现步骤

2.1 脚本说明

compute_d.py 通道数 $d'$ 的选择
solve_linear_PWb_space.py 通道线性分解
solve_nonlinear_PWb.py 通道非线性分解
asymmetric.py 通道非对称分解
cgd_sch2.py 核分解

2.2 svd分解步骤

1、导出需要分解层的feature map和权重：

1.1 导出要分解层的feature map存成.h5文件（3000-6000幅图），每幅图feature map 为三维（feature_size, feature_size, output_channel）

    feature map文件：feature_map/conv1_1/imgname.h5

    注意：feature map为三维（feature high，feature width，outputchannel）,一般每层feature map取3000-6000幅为宜

1.2 将权重文件转成.pkl文件，以convname_w.pkl和convname_b.pkle命名

    权重文件：Wbs/conv1_1_w.pkl   Wbs/conv1_1_b.pkl

2、通道分解：

2.1 选择每层减少通道数de_ch：
    
    计算每层yyt的值，脚本solve_linear_PWb_space.py中已有相关计算，结果存于solution/solution_linear/conv1_1/accelerating_linear_Mb.pkl
    
    修改相应的卷积层名称layers，和原始复杂度计算Complexity
    
    修改输入文件名：init_dir 为accelerating_linear_Mb.pkl的地址
    
    设置期望近似后的复杂度 Complexity_predict=Complexity_total*0.4 
    
    $ python compute_d.py   打印出每层减少通道后的通道数

2.2 分别修改solve_linear_PWb_space.py、solve_nonlinear_PWb.py、asymmetric.py中每个feature map随机采样点数randsize=4，和输入文件地址：

    indir --- feature_map 地址
    wdir --- conv1_1_w.pkl地址
    bdir --- conv1_1_b.pkl 地址

2.3 线性、非线性和非对称分别执行：

    $ python solve_linear_PWb_space.py --layer=conv1_1 --de_ch=16 --batch_size=6000
    
    $ python solve_nonlinear_PWb.py --layer=conv1_1 --de_ch=16 --batch_size=6000
    
    $ python  asymmetric.py --layer=conv1_1 --de_ch=16 --batch_size=6000
    
    其中，layer为要分解卷积层，de_ch为减少通道数，batch_size为feature map的个数。
    
    注意：非对称分解需要输入上一层近似之后的feature map，因此分解一层都要导出前面都近似之后的feature map，且该feature map要和原始的feature map相对应。

2.4 分解好的权重文件存放在solution目录下：

    线性：solution_linear/conv1_1/accelerating_linear_PWb.pkl

    非线性：solution_nonlinear/conv1_1/accelerating_nonlinear_PWb.pkl
    
    非对称：solution_asy/conv1_1/acceleratin_asy_PWb.pkl

2.5 修改网络，测试精度：

    将分解层网络（3 * 3，outchannel）改成（3 * 3，de_ch）+ （1 * 1，outchannel），并导入相应层分解后的权重，测试精度

2.3 卷积核分解步骤

1 修改cgd_sch2.py中输入文件地址：

wdir =  'Wbs/' + FLAGS.layer + '_w.pkl' 权重文件

bdir =  'Wbs/' + FLAGS.layer + '_b.pkl' bias文件

2 $ Python cgd_sch2.py –layer=conv1_1 –de_ch=16

其中，layer为要分解卷积层，de_ch为减少通道数

3 分解好的权重文件solution/cgd/conv1_1/sch2_HV_cgd_step10.pkl

4 修改网络，测试精度：

将（3 * 3, outchannel）改成（3 * 1, de_ch） + （1 * 3, outchannel），并导入相应层分解后的权重文件，测试精度

三、注意

由于svd分解是基于对feature map冗余信息的降维近似，当生成feature map所用的数据集与原来训练网络模型时所用的数据集有差别时，分解的精度会受很大影响。但是卷积核分解不存在此问题。
利用svd的非线性方法进行分解时需要求解GSVD，当feature map的协方差矩阵低秩时可能有复数解，此时应该使用线性求解的方法
利用cgd求解双凸问题时，初始值的选择可能会影响目标函数的结果。

参考文献

[1] Zhang X, Zou J, He K, et al. Accelerating Very Deep Convolutional Networks for Classification and Detection[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2016, 38(10):1943.

[2] Jaderberg M, Vedaldi A, Zisserman A. Speeding up Convolutional Neural Networks with Low Rank Expansions[J]. Computer Science, 2014, 4(4):XIII.

[3] Takane Y, Hwang H. Regularized linear and kernel redundancy analysis[J]. Computational Statistics & Data Analysis, 2007, 52(1):394-405.

模型压缩

模型压缩

一、算法概述

1.1 svd分解

1.1.1 问题引出：对仿射变换进行降维线性近似

1.1.2 推广：对加入非线性（relu）层的卷积层进行降维近似

1.1.3 减小逐层误差累积：非对称分解思路

1.1.4 选择最优的衰减通道数

1.2 卷积核分解

1.2.1 scheme2

1.3 组合使用svd分解与卷积核分解

二、实现步骤

2.1 脚本说明

2.2 svd分解步骤

2.3 卷积核分解步骤

三、注意

模型压缩

一、算法概述

1.1 svd分解

1.1.1 问题引出：对仿射变换进行降维线性近似

1.1.2 推广： 对加入非线性（relu）层的卷积层进行降维近似

1.1.3 减小逐层误差累积： 非对称分解思路

1.1.4 选择最优的衰减通道数

1.2 卷积核分解

1.2.1 scheme2

1.3 组合使用svd分解与卷积核分解

二、实现步骤

2.1 脚本说明

2.2 svd分解步骤

2.3 卷积核分解步骤

三、注意

1.1.2 推广：对加入非线性（relu）层的卷积层进行降维近似

1.1.3 减小逐层误差累积：非对称分解思路