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

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

相关文章：

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

一、Tucker分解

1.1 定义

Tucker分解可以看作是主成分分析(PCA)的一种高阶版本，其将张量分解为一个核张量与每一维度上对应矩阵的乘积。具体来说，以三阶张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$为例，其Tucker分解写为
$$\mathcal{X}\approx \mathcal{G}{\times }_1\text{A}{\times }_2\text{B}{\times }_3\text{C}=\sum _{p=1}^P\sum _{q=1}^Q\sum _{r=1}^R=g_{pqr}{\text{a}}_p\circ {\text{b}}_q\circ {\text{c}}_r=⟮\mathcal{G};\text{A,B,C}⟯$$
其中，$\text{A}\in {\mathbb{R}}^{I\times P},\text{B}\in {\mathbb{R}}^{J\times Q},\text{C}\in {\mathbb{R}}^{K\times R}$是不同维度上的因子矩阵，这些矩阵通常被认为是不同维度上的主成分。$\mathcal{G}\in {\mathbb{R}}^{P\times Q\times 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$$
$P,Q和R$是因子矩阵$\text{A,B,C}$的成分数(例如因子矩阵的列数)。如果$P,Q和R$小于$I,J,K$，那么张量$\mathcal{G}$可以被认为是张量$\mathcal{X}$的压缩版本。在某些情况下，压缩版本的张量可以节省大量的存储空间。Tucker分解形象展示如下图：

1.2 张量矩阵化后的Tucker分解

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

1.3 Tucker分解的N维推广

上面仅介绍了三维张量的Tucker分解，其在N维张量上的分解为
$$\mathcal{X}=\mathcal{G}{\times }_1{\text{A}}^{(1)}{\times }_2{\text{A}}^{(2)}\cdots {\times }_N{\text{A}}^{(N)}=⟮\mathcal{G};{\text{A}}^{(1)},{\text{A}}^{(2)},\dots ,{\text{A}}^{(N)}⟯$$
元素角度的N维张量Tucker分解为：
$$x_{i_1{i}_2\dots i_N}=\sum _{r_1=1}^{R_1}\sum _{r_2=1}^{R_2}\cdots \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)}$$
矩阵化版本为
$${\text{X}}_{(n)}={\text{A}}^{(n)}{\text{G}}_{(n)}({\text{A}}^{(N)}\otimes \cdots \otimes {\text{A}}^{(n+1)}\otimes {\text{A}}^{(n-1)}\otimes \cdots \otimes {\text{A}}^{(1)}{)}^T$$

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

2.1 n秩(n-rank)

若$\mathcal{X}$是一个大小为$I_1\times I_2\times \cdots \times I_N$的N阶张量，那么其n秩的含义是：$\mathcal{X}$在模n矩阵化后的矩阵${\text{X}}_{(n)}$的列秩，其表示为$ran{k}_n(\mathcal{X})$。如果在Tucker分解中，令$$R_n=ran{k}_n(\mathcal{X}),n=1,...,N$$
那么就称张量$\mathcal{X}$是一个$rank-(R_1,R_2,\dots ,R_N)$的张量。(注：不要混淆张量n秩和张量秩的概念)

2.2 截断Tucker分解

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

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

三、计算Tucker分解

3.1 高阶SVD(HOSVD)

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

当至少存在一个$R_n<ran{k}_n(\mathcal{X})$，则称为截断HOSVD。

3.2 HOOI

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

HOOI原理：


若$\mathcal{X}$是一个大小为$I_1\times I_2\times \cdots \times I_N$的N阶张量，那么计算Tucker分解要解决的优化问题为
$$min\Vert \mathcal{X}-⟮\mathcal{G};{\text{A}}^{(1)},{\text{A}}^{(2)},\dots ,{\text{A}}^{(N)}⟯\Vert \text{\hspace{1em}(1)}$$
其中，$\mathcal{G}\in {\mathbb{R}}^{R_1\times R_2\times \cdots \times R_N}$，矩阵${\text{A}}^{(n)}\in {\mathbb{R}}^{I_n\times R_n}$且列正交。
如果在最优解处，那么核张量$\mathcal{G}$必然满足
$$\mathcal{G}=\mathcal{X}{\times }_1{\text{A}}^{(1)T}{\times }_2{\text{A}}^{(2)T}\cdots {\times }_N{\text{A}}^{(N)T}$$
将上式代入到公式(1)中，那么优化目标可以重写为
$$max\Vert \mathcal{X}{\times }_1{\text{A}}^{(1)T}{\times }_2{\text{A}}^{(2)T}\cdots {\times }_N{\text{A}}^{(N)T}\Vert \text{\hspace{1em}(2)}$$
其中，矩阵${\text{A}}^{(n)}\in {\mathbb{R}}^{I_n\times R_n}$且列正交。将公式(2)重写为矩阵形式
$$\Vert {\text{A}}^{(n)T}\text{W}\Vert 且\text{W}={\text{X}}_{(n)}({\text{A}}^{(N)}\otimes \cdots \otimes {\text{A}}^{(n+1)}\otimes {\text{A}}^{(n-1)}\otimes \cdots \otimes {\text{A}}^{(1)})$$
使用SVD可以求解上面的优化问题，仅需要令${\text{A}}^{(n)}$为矩阵$\text{W}$的左奇异向量。但是，这个方法不能保证收敛到全局最优值。

四、缺失唯一性

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


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