卷积核的低秩分解

通过这篇blog了解一下低秩分解。

低秩分解仅作用于线性网络层的权重,可能忽略不同网络层的联系。

There are works that try to address these issues, and its still an active research area.

全连接层的张量分解

首先简单介绍一下SVD。奇异值分解(SVD)是对矩阵进行分解:
$$
A_{n times m}=U_{n times n} S_{n times m} V_{m times m}^{T}
$$
其中$S$是非负实数对角矩阵,对角线上元素即为$A$的奇异值。通常会将奇异值由大到小排序。$U$和$V$是酉矩阵,满足$U^{T} U=V^{T} V=I$。当我们取其最大的$t$个奇异值,将剩下的值置0,则能得到近似矩阵$hat{A}=U_{n x t} S_{t x t} V_{m x t}^{T}$。

我们对全连接层的公式$A x+b$进行分解有:$left(U_{n times t} S_{t times t} V_{m times t}^{T}right) x+b=U_{n times t}left(S_{t times t} V_{m times t}^{T} xright)+b$

这样将一个大矩阵转化为两个小矩阵,参数量从 $n times m$ 降为 $t (n+m)$

卷积层的张量分解

下面介绍对卷积层进行张量分解最经典的两种方法:CP分解和Tucker分解

CP分解

论文地址:Speeding-up Convolutional Neural Networks Using Fine-tuned CP-Decomposition

对$A$进行低秩分解有:
$$
A(i, j)=sum_{n=1}^{R} A_{1}(i, r) A_{2}(j, r), quad i=overline{1, n}, quad j=overline{1, m}
$$
对d维的$A$进行CP分解有:
$$
Aleft(i_{1}, ldots, i_{d}right)=sum_{r=1}^{R} A_{1}left(i_{1}, rright) ldots A_{d}left(i_{d}, rright)
$$
对$d times d times S times T$的4D的卷积核进行CP分解
$$
K(i, j, s, t)=sum_{r=1}^{R} K^{x}(i-x+delta, r) K^{y}(j-y+delta, r) K^{s}(s, r) K^{t}(t, r)
$$
则输出可以$V$ 表示为:
$$
V(x, y, t)=sum_{r=1}^{R} K^{t}(t, r)left(sum_{i=x-delta}^{x+delta} K^{x}(i-x+delta, r)left(sum_{j=y-delta}^{y+delta} K^{y}(j-y+delta, r)left(sum_{s=1}^{S} K^{s}(s, r) U(i, j, s)right)right)right)
$$
则1个卷积操作可以分解为4个卷积操作:
$$
begin{aligned} U^{s}(i, j, r) &=sum_{s=1}^{S} K^{s}(s, r) U(i, j, s) \ U^{s y}(i, y, r) &=sum_{j=1}^{y+delta} K^{y}(j-y+delta, r) U^{s}(i, j, r) \ U^{s y z}(x, y, r) &=sum_{i=x-delta}^{x+delta} K^{x}(i-x+delta, r) U^{s y}(i, y, r) \ V(x, y, t) &=sum_{r=1}^{R} K^{t}(t, r) U^{s y x}(x, y, r) end{aligned}
$$

  1. 用$1times1$的pointwise卷积将输入降至R纬度
  2. 在垂直维度做$dtimes1$的depthwise卷积
  3. 在水平纬度做$dtimes1$的depthwise卷积

  4. 用$1times 1$的pointwise卷积获得$T$维的输出

复杂度分析:

  • 原始卷积 $STd^2$
  • CP分解 $R(S+2d+T)$

Tucker分解

论文地址:Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications

Tucker分解也称为高阶SVD,4D卷积核表示为:
$$
K(i, j, s, t)=sum_{r_{1}=1}^{R_{1}} sum_{r_{2}=1}^{R_{2}} sum_{r_{3}=1}^{R_{3}} sum_{r_{4}=1}^{R_{4}} C’_{r_1, r_2, r_3, r_4} K_{r 1}^{x}(i) K_{r_2}^{y}(j) K_{r_3}^{s}(s) K_{r _4}^{t}(t)
$$
卷积核通常比较小($3 times 3$),就不再在空间维度进行分解
$$
K(i, j, s, t)=sum_{r_{3}=1}^{R_{3}} sum_{r_{4}=1}^{R_{4}} C’_{i,j, r_3, r_4} K_{r_3}^{s}(s) K_{r _4}^{t}(t)
$$
其中$C$代表$d times d times R_3 times R_4$ 的核心张量。

于是将1个卷积操作分解为3个卷积操作:
$$
begin{aligned} mathcal{Z}_{h, w, r_{3}} &=sum_{s=1}^{S} U_{s, r_{3}}^{(3)} mathcal{X}_{h, w, s} \ mathcal{Z}_{h^{prime}, w^{prime}, r_{4}}^{D} &=sum_{i=1}^{D} sum_{j=1}^{D} sum_{r_{3}=1}^{R_{3}} mathcal{C}_{i, j, r_{3}, r_{4}} z_{h_{i} w_{j}, r_{3}} \ y_{h^{prime}, w^{prime}, t} &=sum_{r_{4}=1}^{R_{4}} U_{t, r_{4}}^{(4)} mathcal{Z}_{h^{prime}, w^{prime}, r_{4}}^{prime} end{aligned}
$$

  1. 用$1times1$的pointwise卷积将输入降至R纬度
  2. 进行$d times d$的卷积
  3. 用$1times 1$的pointwise卷积获得$T$维的输出

挑选分解的秩

在分解的时候秩$R$的选择很重要,Tucker分解中用了VBMF的方法。