【张量分解(三)】Tucker分解

本文是对论文Tensor Decompositions and Applications进行了翻译、整理、筛选和适当的补充，如何希望深入理解可以阅读原文。

相关文章：

【张量分解(一)】符号与基础知识
【张量分解(二)】CP分解
【张量分解(三)】Tucker分解

一、Tucker分解

1.1 定义

Tucker分解可以看作是主成分分析(PCA)的一种高阶版本，其将张量分解为一个核张量与每一维度上对应矩阵的乘积。具体来说，以三阶张量$\mathcal{X}\in\mathbb{R}^{I\times J\times K}$X∈RI×J×K为例，其Tucker分解写为
$\mathcal{X}\approx\mathcal{G}\times_1\textbf{A}\times_2\textbf{B}\times_3\textbf{C}=\sum_{p=1}^P\sum_{q=1}^Q\sum_{r=1}^R=g_{pqr}\textbf{a}_p\circ\textbf{b}_q\circ\textbf{c}_r=\lgroup\mathcal{G};\textbf{A,B,C}\rgroup$X≈G×1​A×2​B×3​C=p=1∑P​q=1∑Q​r=1∑R​=gpqr​ap​∘bq​∘cr​=⟮G;A,B,C⟯
其中，$\textbf{A}\in\mathbb{R}^{I\times P},\textbf{B}\in\mathbb{R}^{J\times Q},\textbf{C}\in\mathbb{R}^{K\times R}$A∈RI×P,B∈RJ×Q,C∈RK×R是不同维度上的因子矩阵，这些矩阵通常被认为是不同维度上的主成分。$\mathcal{G}\in\mathbb{R}^{P\times Q\times R}$G∈RP×Q×R称为核张量，其中的每个元素代表了不同成分之间的交互程度。


从元素的角度看，Tucker分解可以写为
$x_{ijk}\approx\sum_{p=1}^P\sum_{q=1}^Q\sum_{r=1}^R g_{pqr}a_{ip}b_{jq}c_{kr},i=1,...,I,j=1,...,J,k=1,...,K$xijk​≈p=1∑P​q=1∑Q​r=1∑R​gpqr​aip​bjq​ckr​,i=1,...,I,j=1,...,J,k=1,...,K
$P,Q和R$P,Q和R是因子矩阵$\textbf{A,B,C}$A,B,C的成分数(例如因子矩阵的列数)。如果$P,Q和R$P,Q和R小于$I,J,K$I,J,K，那么张量$\mathcal{G}$G可以被认为是张量$\mathcal{X}$X的压缩版本。在某些情况下，压缩版本的张量可以节省大量的存储空间。Tucker分解形象展示如下图：

1.2 张量矩阵化后的Tucker分解

Tucker分解的矩阵化版本为
$\textbf{X}_{(1)}\approx\textbf{AG}_{(1)}(\textbf{C}\otimes\textbf{B})^T$X(1)​≈AG(1)​(C⊗B)T
$\textbf{X}_{(2)}\approx\textbf{BG}_{(2)}(\textbf{C}\otimes\textbf{A})^T$X(2)​≈BG(2)​(C⊗A)T
$\textbf{X}_{(3)}\approx\textbf{CG}_{(3)}(\textbf{B}\otimes\textbf{A})^T$X(3)​≈CG(3)​(B⊗A)T

1.3 Tucker分解的N维推广

上面仅介绍了三维张量的Tucker分解，其在N维张量上的分解为
$\mathcal{X}=\mathcal{G}\times_1 \textbf{A}^{(1)}\times_2 \textbf{A}^{(2)}\dots\times_N \textbf{A}^{(N)}=\lgroup\mathcal{G};\textbf{A}^{(1)},\textbf{A}^{(2)},\dots,\textbf{A}^{(N)}\rgroup$X=G×1​A(1)×2​A(2)⋯×N​A(N)=⟮G;A(1),A(2),…,A(N)⟯
元素角度的N维张量Tucker分解为：
$x_{i_1 i_2\dots i_N}=\sum_{r_1=1}^{R_1}\sum_{r_2=1}^{R_2}\dots\sum_{r_N=1}^{R_N}g_{r_1 r_2\dots r_N}a_{i_1 r_1}^{(1)}a_{i_2 r_2}^{(2)}\dots a_{i_N r_N}^{(N)}$xi1​i2​…iN​​=r1​=1∑R1​​r2​=1∑R2​​⋯rN​=1∑RN​​gr1​r2​…rN​​ai1​r1​(1)​ai2​r2​(2)​…aiN​rN​(N)​
矩阵化版本为
$\textbf{X}_{(n)}=\textbf{A}^{(n)}\textbf{G}_{(n)}(\textbf{A}^{(N)}\otimes\dots\otimes\textbf{A}^{(n+1)}\otimes\textbf{A}^{(n-1)}\otimes\dots\otimes\textbf{A}^{(1)})^T$X(n)​=A(n)G(n)​(A(N)⊗⋯⊗A(n+1)⊗A(n−1)⊗⋯⊗A(1))T

二、n秩(n-rank)与截断Tucker分解

2.1 n秩(n-rank)

若$\mathcal{X}$X是一个大小为$I_1\times I_2\times \dots \times I_N$I1​×I2​×⋯×IN​的N阶张量，那么其n秩的含义是：$\mathcal{X}$X在模n矩阵化后的矩阵$\textbf{X}_{(n)}$X(n)​的列秩，其表示为$rank_n(\mathcal{X})$rankn​(X)。如果在Tucker分解中，令$R_n=rank_n(\mathcal{X}),n=1,...,N$Rn​=rankn​(X),n=1,...,N
那么就称张量$\mathcal{X}$X是一个$rank-(R_1,R_2,\dots,R_N)$rank−(R1​,R2​,…,RN​)的张量。(注：不要混淆张量n秩和张量秩的概念)

2.2 截断Tucker分解

$\mathcal{X}$X是一个n秩为$rank-(R_1,R_2,\dots,R_N)$rank−(R1​,R2​,…,RN​)的数据张量。如果令$R_n=rank_n(\mathcal{X})$Rn​=rankn​(X)，则可以很容易找到$\mathcal{X}$X的精确Tucker分解。但是，如果存在至少一个维度满足$R_n<rank_n(\mathcal{X})$Rn​<rankn​(X)，那么Tucker分解必然不准确且计算困难，在这种情况下的Tucker分解称为截断Tucker分解，如原理如下图所示。

截断Tucker分解无法准确的再生张量$\mathcal{X}$X

三、计算Tucker分解

3.1 高阶SVD(HOSVD)

高阶SVD(HOSVD)的思想是找到那些能很好的捕获维度n上变化的矩阵，而且其不受到其他维度的影响。HOSVD是矩阵的SVD(奇异值分解)在高维张量上的推广。其算法如下所示：

当至少存在一个$R_n<rank_n(\mathcal{X})$Rn​<rankn​(X)，则称为截断HOSVD。

3.2 HOOI

截断HOSVD并不能直接得到最优值，但是其结果可以作为迭代交替最小二乘法(ALS)的一个很好的迭代起点。HOOI就是一种ALS算法，其算法如下图所示：

HOOI原理：


若$\mathcal{X}$X是一个大小为$I_1\times I_2\times \dots \times I_N$I1​×I2​×⋯×IN​的N阶张量，那么计算Tucker分解要解决的优化问题为
$min \|\mathcal{X}-\lgroup\mathcal{G};\textbf{A}^{(1)},\textbf{A}^{(2)},\dots,\textbf{A}^{(N)}\rgroup\|\tag{1}$min∥X−⟮G;A(1),A(2),…,A(N)⟯∥(1)
其中，$\mathcal{G}\in\mathbb{R}^{R_1\times R_2\times \dots \times R_N}$G∈RR1​×R2​×⋯×RN​，矩阵$\textbf{A}^{(n)}\in\mathbb{R}^{I_n\times R_n}$A(n)∈RIn​×Rn​且列正交。
如果在最优解处，那么核张量$\mathcal{G}$G必然满足
$\mathcal{G}=\mathcal{X}\times_1\textbf{A}^{(1)T}\times_2\textbf{A}^{(2)T}\dots\times_N\textbf{A}^{(N)T}$G=X×1​A(1)T×2​A(2)T⋯×N​A(N)T
将上式代入到公式(1)中，那么优化目标可以重写为
$max\|\mathcal{X}\times_1\textbf{A}^{(1)T}\times_2\textbf{A}^{(2)T}\dots\times_N\textbf{A}^{(N)T}\|\tag{2}$max∥X×1​A(1)T×2​A(2)T⋯×N​A(N)T∥(2)
其中，矩阵$\textbf{A}^{(n)}\in\mathbb{R}^{I_n\times R_n}$A(n)∈RIn​×Rn​且列正交。将公式(2)重写为矩阵形式
$\|\textbf{A}^{(n)T}\textbf{W}\|且\textbf{W}=\textbf{X}_{(n)}(\textbf{A}^{(N)}\otimes\dots\otimes\textbf{A}^{(n+1)}\otimes\textbf{A}^{(n-1)}\otimes\dots\otimes\textbf{A}^{(1)})$∥A(n)TW∥且W=X(n)​(A(N)⊗⋯⊗A(n+1)⊗A(n−1)⊗⋯⊗A(1))
使用SVD可以求解上面的优化问题，仅需要令$\textbf{A}^{(n)}$A(n)为矩阵$\textbf{W}$W的左奇异向量。但是，这个方法不能保证收敛到全局最优值。

四、缺失唯一性

Tucker分解是不唯一的。对于三维张量的分解，如果令$\textbf{U}\in\mathbb{R}^{P\times P},\textbf{V}\in\mathbb{R}^{Q\times Q},\textbf{W}\in\mathbb{R}^{R\times R}$U∈RP×P,V∈RQ×Q,W∈RR×R为非奇异矩阵。那么对Tucker分解可以做下面的变换
$\lgroup\mathcal{G};\textbf{A,B,C}\rgroup=\lgroup\mathcal{G}\times_1\textbf{U}\times_2\textbf{V}\times_3\textbf{W};\textbf{AU}^{-1},\textbf{BV}^{-1},\textbf{CW}^{-1}\rgroup$⟮G;A,B,C⟯=⟮G×1​U×2​V×3​W;AU−1,BV−1,CW−1⟯
换句话说，我们可以在不影响拟合结果的情况下修改核张量$\mathcal{G}$G，只要同时对因子矩阵进行反向修改即可。


这种特性提供了一个渠道，让我们可以简化核张量$\mathcal{G}$G，从而是$\mathcal{G}$G中的大多数元素为0，这样就可以消除各个维度上成分的相互作用。