张量分解、低秩分解(tensorfactorization、lowrankfactorization)

http://www.xiongfuli.com/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2016-06/tensor-decomposition-tucker.html
https://www.cnblogs.com/jimchen1218/p/11957885.html
深度网络加速和压缩的第一种方法是Low-Rank低秩分解。由于卷积神经网络中的主要计算量在于卷积计算，而卷积计算本质上是矩阵分析的问题，通过在大学对矩阵分析、高等数学的学习我们知道通过SVD奇异值分解等矩阵分析方法可以有效减少矩阵运算的计算量。

对于二维矩阵运算来说SVD是非常好的简化方法，所以在早期的时候，微软研究院就做过相关的工作来对网络实现加速。后面对于高维矩阵的运算往往会涉及到Tensor分解方法来做加速和压缩，主要是CP分解、Tucker分解、Tensor Train分解和Block Term分解这些在2015年和2016年所做的工作。

应该说矩阵分解方法经过过去的发展已经非常成熟了，所以在2017、2018年的工作就只有Tensor Ring和Block Term分解在RNN的应用两篇相关文章了。

那么为什么Low-Rank不再流行了呢？除了刚才提及的分解方法显而易见、比较容易实现之外，另外一个比较重要的原因是现在越来越多网络中采用1×1的卷积，而这种小的卷积使用矩阵分解的方法很难实现网络加速和压缩。

一、简介

https://wenku.baidu.com/link?url=dSfKH34IuILQXHC3dA7QwCwYXKXFSefBSEY8pFJeJRHUeKwXInD_hKUWUtA763wbOxxOdV3ugIGA3ch2ozMcgrgUS8ZmP8vLzXSS5nIjmAO
https://blog.csdn.net/zouxy09/article/details/24972869

（一）、定义一

这一部分的思路比较简单，如果把原先网络的权值矩阵当作满秩矩阵来看，那么是不是可以用多个低秩的矩阵来逼近原来的矩阵，以达到简化的目的？答案是肯定的。

原先稠密的满秩矩阵可以表示为若干个低秩矩阵的组合，低秩矩阵又可以分解为小规模矩阵的乘积。

对于二维矩阵运算来说SVD是非常好的简化方法，所以在早期的时候，微软研究院就做过相关的工作来对网络实现加速。后面对于高维矩阵的运算往往会涉及到Tensor分解方法来做加速和压缩，主要是CP分解、Tucker分解、Tensor Train分解和Block Term分解这些在2015年和2016年所做的工作。在这方面有几篇经典的论文。

（二）、定义二

卷积层的卷积核是一个4维张量，张量维度对应于卷积核的宽度、高度，以及输入和输出的通道数。4−D的张量可以分解成t−D,(t=1,…4)的张量。低秩分解的目的是为了寻找一个近似张量Ŵ 来逼近原始张量W，而近似张量可以有更高的计算效率。

低秩分解法的关键不同之处在于如何排列四个维度和低秩约束是怎么规定的。以下按照滤波器所分解成的元素个数来分类。

（三）、定义三

一个典型的 CNN 卷积核是一个 4D 张量，而全连接层也可以当成一个 2D 矩阵，低秩分解同样可行。这些张量中可能存在大量的冗余。所有近似过程都是逐层进行的，在一个层经过低秩滤波器近似之后，该层的参数就被固定了，而之前的层已经用一种重构误差标准（reconstruction error criterion）微调过。这是压缩 2D 卷积层的典型低秩方法，如下图所示。

使用低阶滤波器加速卷积的时间已经很长了，例如，高维 DCT（离散余弦变换）和使用张量积的小波系统分别由 1D DCT 变换和 1D 小波构成。

学习可分离的 1D 滤波器由 Rigamonti 等人提出，遵循字典学习的想法。Jaderberg 的工作提出了使用不同的张量分解方案，在文本识别准确率下降 1％ 的情况下实现了 4.5 倍加速。

一种 flatten 结构将原始三维卷积转换为 3 个一维卷积，参数复杂度由 O(XYC)降低到O(X+Y+C)，运算复杂度由 O(mnCXY) 降低到 O(mn(X+Y+C)。

低阶逼近是逐层完成的。完成一层的参数确定后，根据重建误差准则对上述层进行微调。这些是压缩二维卷积层的典型低秩方法，如图 2 所示。

按照这个方向，Lebedev 提出了核张量的典型多项式（CP）分解，使用非线性最小二乘法来计算。Tai 提出了一种新的从头开始训练低秩约束 CNN 的低秩张量分解算法。它使用批量标准化（BN）来转换内部隐藏单元的激活。一般来说， CP 和 BN分解方案都可以用来从头开始训练 CNN。

低秩方法很适合模型压缩和加速，但是低秩方法的实现并不容易，因为它涉及计算成本高昂的分解操作。另一个问题是目前的方法都是逐层执行低秩近似，无法执行全局参数压缩，因为不同的层具备不同的信息。最后，分解需要大量的重新训练来达到收敛。

二、方法

https://blog.csdn.net/flying_sfeng/article/details/87453217
https://zhuanlan.zhihu.com/p/57410790
https://jacobgil.github.io/deeplearning/tensor-decompositions-deep-learning
https://zhuanlan.zhihu.com/p/72523589
https://zhuanlan.zhihu.com/p/141563287
https://zhuanlan.zhihu.com/p/176990341
https://zhuanlan.zhihu.com/p/77834369
https://zhuanlan.zhihu.com/p/24798389
https://zhuanlan.zhihu.com/p/340113856
https://zhuanlan.zhihu.com/p/24824550
https://zhuanlan.zhihu.com/p/25067269
https://zhuanlan.zhihu.com/p/87604902
https://zhuanlan.zhihu.com/p/25512080
https://zhuanlan.zhihu.com/p/338975251
https://zhuanlan.zhihu.com/p/85305561

（一）、Tucker分解 【COMPRESSION OF DEEP CONVOLUTIONAL NEURAL NETWORKS FOR FAST AND LOW POWER MOBILE APPLICATIONSICLR 2016】

https://zhuanlan.zhihu.com/p/57410790

1、简介

张量本质上是多维的数组，例如向量可以看作1维张量，矩阵是2维张量。两个最常见的张量分解方法是CP分解【10,11,12】和Tucker分解【13,14,15】，本文利用的是Tucker分解。Tucker分解可以看作是一个高阶的SVD分解，对于全连接层的Tucker分解就等同于SVD分解，即针对卷积层做Tucker分解，针对全连接层做SVD分解。对于第一层卷积，由于输入通道数很小（彩图为3）因此也是做SVD分解，具体的流程如图2.1所示

2、内容

如图所示为本文提出方法的流程，压缩整个网络包括三个步骤：1）选择合适的秩；2）Tucker分解；3）参数调优。在第一步中，本文利用VBMF分析参数张量，并得到合适的秩；接着使用Tucker分解针对每一层做压缩，每个张量保留的秩就是VBMF得到的秩；最后利用BP（back propagation）做参数调优。

（1）卷积层操作表示

在CNN中，我们不考虑batch那一维，那么实际卷积的输入张量，卷积核和输出张量设为X, K, Y

则卷积层的操作可以通过如下公式获得，式中 Δ为stride，P为padding的大小

（2）卷积核参数表示

如果我们以秩(R1,R2,R3,R4) 做Tucker分解，那么卷积核参数可以估计表示为如下形式，式中C为核张量，U1,U2,U3,U4为参数矩阵

（3）卷积核参数近似表示

对于我们实际CNN中的模型，我们不用对所有维度做分解，比如第2，3维，实际上对应与空间维度D*D本身很小不需要压缩，因此实际应用的对参数张量的估计为下式，式中C为核张量

（4）卷积操作近似表示（分解）

我们将卷积公式中的参数张量用估计的张量来表示，于是得到以下的计算公式，式中都是临时张量，而下式中的每一步都可以用卷积来实现。

（5）分解示意图

分解后的卷积过程如图3.1所示，首先是11的卷积，可以看作通道维度的压缩，第二个卷积是DD的卷积，可以看作是做空间维度的信息交流，最后一个卷积是11的卷积，可以看作是将通道维度还原。

从上图中，我们可以看到第一个卷积和第三个卷积都是 11的卷积核本质上是对于输入特征图X做了通道维度的线性重组，这个方法与“network-in-network”很相似，而且这种结构也广泛应用与CNN模型中（比如GoogLeNet中的Inception结构），但是本文提出的结构与之最大的不同在于，第一个和第二个卷积之后并没有加非线性层。

3、复杂度分析

4、CP分解与Tucker分解的对比

5、参数调优

由于本文提出的方法是最小化参数张量的重建误差，（asymmetric 3d方法中是最小化特征图的重建误差）因此直接做Tucker分解后模型的准确率会有很大程度的降低（在作者的试验中，AlexNet压缩后会有50%的准确率损失）。图3.3为参数调优的实验，横坐标为训练迭代次数，纵坐标为ImageNet Top-5准确率。通过实验可以发现，参数调优可以很容易地恢复模型地准确率，而且仅经过1Epoch的迭代就可以将模型准确率恢复到不错的效果。

在作者的实验中，设定基本学习率是0.001，之后每5Epoch或10Epoch降为之前的0.1。同时为了证明Tucker分解的有效性，作者按照分解后的网络结构，以高斯随机分布初始化网络参数从头训练，发现得到的模型效果并不好，由此可以证明Tucker分解获得分解后的参数是必要的。

（二）、Cholesky分解

https://zhuanlan.zhihu.com/p/267371673

（三）、奇异值分解（即Turkey）

https://zhuanlan.zhihu.com/p/25512080

（四）、特征分解/谱分解

https://zhuanlan.zhihu.com/p/31106828
https://zhuanlan.zhihu.com/p/52890135

（五）、LU分解

https://zhuanlan.zhihu.com/p/279323822
https://zhuanlan.zhihu.com/p/54943042

（六）、QR分解

https://zhuanlan.zhihu.com/p/54957185
https://zhuanlan.zhihu.com/p/279323822

（七）、Cholesky三角分解

https://zhuanlan.zhihu.com/p/279323822
https://zhuanlan.zhihu.com/p/115381559

（八）、PALU分解

https://zhuanlan.zhihu.com/p/279323822

（九）、满秩分解

https://zhuanlan.zhihu.com/p/344306107
https://zhuanlan.zhihu.com/p/97923419
https://zhuanlan.zhihu.com/p/356686048

（十）、TT分解（[Tensorizing Neural Network]）Tensor-Train-Decomposition

https://zhuanlan.zhihu.com/p/72523589
《Tensorizing Neural Network》

（十一）、CP分解（Accelerating Deep Neural Networks with Tensor Decompositions）

CP decomposition
https://jacobgil.github.io/deeplearning/tensor-decompositions-deep-learning
https://github.com/TianhaoFu/pytorch-tensor-decompositions

（十）、高性能计算SVD

https://zhuanlan.zhihu.com/p/57439266

1、Randomized SVD

https://scikit-learn.org/stable/modules/generated/sklearn.utils.extmath.randomized_svd.html#sklearn.utils.extmath.randomized_svd
https://cloud.tencent.com/developer/article/1005571

2、并行SVD分解(只包括两种特殊矩阵）

三、方法

（一）、两元分解

两元分解，权重张量被分解成两部分，卷积层会被两个连续相接的层替代。《Speeding up convolutional neural networks with low rank expansions》将ω∗h的卷积核分解成ω×1和1×h大小的小核，实现运算量的压缩。

（二）、三元分解

（三）、四元分解

三、论文

（一）、rank-1的重构 (用fx1+1xf的卷积核来替代f*f的卷积核)

• 2014-Speeding up Convolutional Neural Networks with Low Rank Expansions
  这篇文章提出用fx1+1xf的卷积核来替代f*f的卷积核的线性组合卷积核基底的方法来进行低秩近似，下图可以很直观的表达作者思想：

  

  image

  该方法在场景文字识别中实验在无精度损失的情况下达到原来的2.5倍速，而达到4.5倍速的同时仅损失1%的accuracy。

（二）、rank-k重构

• 2014-NPIS-Exploiting Linear StructureWithin Convolutional Networks for Efficient Evaluation
  上面这个是属于rank-1的重构，这篇文章则是提出rank-k的重构，他对卷积使用一个中间层来进行降秩，通过单谱段处理（monochromatic convolution approximation）（暂时还不太懂这个，只知道是通过固定某一个维度，合并其他三个维度进行SVD）和双聚类处理（bicluster）加上SVD对矩阵进行降k维估计。该方法对于每个卷积层能提速一倍，损失1%的精度。

  

  image

• 2015-NPIS-Structured transforms for small footprint deep learning

（三）、用结构化矩阵

• 2015-Accelerating Very Deep Convolutional Networks for Classification and Detection

• 2014-Speeding-up Convolutional Neural Networks Using Fine-tuned CP-Decomposition||pytorch代码||借鉴博客

• 2015-Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications||pytorch代码

• 2017-High performance ultra-low-precision convolutions on mobile devices

四、存在问题

应该说矩阵分解方法经过过去的发展已经非常成熟了，所以在2017、2018年的工作就只有Tensor Ring和Block Term分解在RNN的应用两篇相关文章了。
那么为什么Low-Rank在这两年不再流行了呢？除了刚才提及的分解方法显而易见、比较容易实现之外，另外一个比较重要的原因是现在越来越多网络中采用1×1的卷积，而这种小的卷积使用矩阵分解的方法很难实现网络加速和压缩。

• 超参数的数量随着网络层数的增加呈线性变化趋势，例如中间层的特征通道数等等。参考2016年的NIPSConvolutional neural networks with low-rank regularization
• 随着模型复杂度的提升，搜索空间急剧增大——Learning structured sparsity in deep neural networks