头像

Cyan

四川成都

深度强化学习炼丹师

张量分解

张量分解

2022-08-10 · 186次阅读 · 原创 · 数学

一、张量基本术语

1.1 阶(Order)

张量的阶,即为张量的维度大小。

1.2 纤维(Fibers)

从张量中抽取出的一维向量,指固定其它维度,而某个维度的元素全部选取。

例: 有一个三阶张量 Xi,j,kX_{i,j,k} ,其列纤维(column fibers),行纤维(row fibers)和管纤维(tube fibers)如下图所示。

三阶张量的纤维

1.3 切片(Slice)

是张量的二维截面,除了两个维度,其他维度全部固定。

例: 有一个三阶张量 Xi,j,kX_{i,j,k} ,其水平切片(horizontal slices),横向切片(lateral slices)和前切片(frontal slices)如下图所示。

三阶张量的切片

1.4 范数(Norm)

一个张量 XRI1×I2××IN\mathcal{X}\in \mathbb{R}^{I_1\times I_2\times \cdots \times I_N} 的范数是所有元素的平方和开平方,记为 X||\mathcal{X}||

X=i1=1I1i2=1I2iN=1INxi1i2iN2||\mathcal{X}||=\sqrt{\sum_{i_1=1}^{I_1}\sum_{i_2=1}^{I_2}\cdots\sum_{i_N=1}^{I_N}x^2_{i_1i_2\cdots i_N}}

1.5 内积(Inner product)

对于两个相同维度的张量 X,YRI1×I2××IN\mathcal{X}, \mathcal{Y} \in \mathbb{R}^{I_1\times I_2\times\cdots\times I_N},他们的 内积 表示为对应(相同下标)元素的乘积的和,如下式子:

X,Y=i1=1I1i2=1I2iN=1INxi1i2iNyi1i2iN\left \langle \mathcal{X},\mathcal{Y} \right \rangle = \sum_{i_1=1}^{I_1}\sum_{i_2=1}^{I_2}\cdots\sum_{i_N=1}^{I_N}x_{i_1i_2\cdots i_N}y_{i_1i_2\cdots i_N}

可以发现,X,X=X2\left \langle \mathcal{X},\mathcal{X} \right \rangle = ||\mathcal{X}||^2

1.6 Rank-one tensors

一种特殊的张量,如果一个 N 阶张量能表示为 N 个一维向量的外积(outer product),那么该张量即为Rank-One Tensor,如下式子:

X=a(1)a(2)a(N)\mathcal{X} = a^{(1)} \circ a^{(2)} \circ \cdots \circ a^{(N)}

其中“\circ”符号代表外积操作。可以发现张量的每个元素为对应向量元素的乘积,即下式子成立:

xi1i2iN=ai1(1)ai2(2)aiN(N)x_{i_1i_2\cdots i_N}=a_{i_1}^{(1)}a_{i_2}^{(2)}\cdots a_{i_N}^{(N)}

1.7 对称性(Symmetry)

当一个张量的所有维度的大小都相同,可以称其为 立方体(cubical)。而当一个立方体的张量的每个元素在其下标的排列中仍保持不变,即可称该张量为 超对称的(supersymmetry)

例如,一个三阶张量 XRI×I×I\mathcal{X} \in \mathbb{R}^{I\times I \times I} 是超对称的当下式成立时满足:

xijk=xikj=xjik=xjki=xkij=xkjii,j,k=1,2,,Ix_{ijk} = x_{ikj} = x_{jik} = x_{jki} = x_{kij} = x_{kji} \qquad i, j, k = 1, 2, \cdots, I

更一般的情况,还存在局部对称,即在某两维或更多维是对称的情况。例如,三阶张量的前切面(frontal slices)是对称的二维矩阵。

1.8 对角张量(Diagonal tensors)

一个张量 XRI1×I2××IN\mathcal{X}\in \mathbb{R}^{I_1\times I_2\times \cdots \times I_N} 是对角张量,当且仅当 i1=i2==iNi_1 = i_2 = \cdots =i_Nxi1i2iN0x_{i_1i_2\cdots i_N} \neq 0

1.9 矩阵化(Matricization)

将高阶张量转化为一个矩阵,在此仅讨论mode-n 矩阵化。

对于三阶张量,有三种展开方式,如下图

三阶张量矩阵化

1.10 张量乘法(Tensor multiplication)

张量乘矩阵

一个高阶张量 XRI1×I2×IN\mathcal{X}\in\mathbb{R}^{I_1\times I_2\cdots\times I_N} 和一个二阶矩阵 URJ×In\mathbf{U} \in \mathbb{R}^ {J\times I_n}n-mode 乘法如下:

(X×nU)i1in1jin+1iN=in=1Inxi1i2iNujin(\mathcal{X}\times_{n}\mathbf{U})_{i_1\cdots i_{n-1}ji_{n+1}\cdots i_N}=\sum_{i_n=1}^{I_n}x_{i_1i_2\cdots i_N}u_{ji_n}

其他公式:

Y=X×nU    Y(n)=UX(n)\mathcal{Y} = \mathcal{X} \times_n \mathbf{U} \iff \mathbf{Y}_{(n)} = \mathbf{U}\mathbf{X}_{(n)}

X×mA×nB=X×nB×mA(mn)\mathcal{X}\times_m \mathbf{A} \times_n \mathbf{B} = \mathcal{X}\times_n \mathbf{B} \times_m \mathbf{A} \quad (m \neq n)

X×nA×nB=X×n(BA)\mathcal{X}\times_n \mathbf{A} \times_n \mathbf{B} = \mathcal{X}\times_n (\mathbf{BA})

张量乘向量

一个高阶张量 XRI1×I2×IN\mathcal{X}\in\mathbb{R}^{I_1\times I_2\cdots\times I_N} 和一个一维向量 VRInV \in \mathbb{R}^ {I_n}n-mode 乘法如下:

(X×ˉnv)i1in1in+1iN=in=1Inxi1i2iNvin(\mathcal{X}\bar{\times}_{n}\mathbf{v})_{i_1\cdots i_{n-1}i_{n+1}\cdots i_N}=\sum_{i_n=1}^{I_n}x_{i_1i_2\cdots i_N}v_{i_n}

其他公式:

X ×ˉm a ×ˉn b=(X ×ˉm a) ×ˉn1 b=(X ×ˉn b) ×ˉm aform<n\mathcal{X} \ \bar\times_m \ \mathbf{a} \ \bar\times_n \ \mathbf{b} = (\mathcal{X} \ \bar\times_m \ \mathbf{a}) \ \bar\times_{n - 1} \ \mathbf{b} = (\mathcal{X} \ \bar\times_n \ \mathbf{b}) \ \bar\times_m \ \mathbf{a} \quad \text{for}\quad m < n

上式中间部分,由于 X\mathcal{X}b\mathbf{b} 相乘后维度减少一维,在 m<nm < n 的情况下,原来的第 mm 维消失,后面维度整体前移一维,所以原来的第 nn 维变为了 n1n-1 维。

1.11 三种矩阵乘法

(1) Kronecker product

对于两个矩阵 ARI×J\mathbf{A} \in \mathbb{R}^{I \times J}BRK×L\mathbf{B} \in \mathbb{R}^{K \times L} ,其 Kronecker product 表示为 AB\mathbf{A} \otimes \mathbf{B} ,其结果为 (IK)×(JL)(IK)\times(JL) 大小的矩阵:

AB=[a11Ba12Ba1JBa21Ba22Ba2JBaI1BaI2BaIJB]=[a1b1a1b2a1b3aJbL1aJbL]\begin{aligned} \mathbf{A} \otimes \mathbf{B} &= \begin{bmatrix} a_{11}\mathbf{B} & a_{12}\mathbf{B} & \cdots & a_{1J}\mathbf{B} \\ a_{21}\mathbf{B} & a_{22}\mathbf{B} & \cdots & a_{2J}\mathbf{B} \\ \vdots & \vdots & \ddots & \vdots \\ a_{I1}\mathbf{B} & a_{I2}\mathbf{B} & \cdots & a_{IJ}\mathbf{B} \end{bmatrix} \\ &=\begin{bmatrix} \mathbf{a}_1\otimes\mathbf{b}_1 & \mathbf{a}_1\otimes\mathbf{b}_2 & \mathbf{a}_1\otimes\mathbf{b}_3 & \cdots & \mathbf{a}_J\otimes\mathbf{b}_{L-1} & \mathbf{a}_J\otimes\mathbf{b}_L\end{bmatrix} \end{aligned}

如下例子:

[1231][0321]=[10132023121122213033101332311211]=[0306214209036321]\begin{bmatrix}1 & 2 \\ 3 & 1 \end{bmatrix} \otimes \begin{bmatrix}0 & 3 \\ 2 & 1 \end{bmatrix}= \begin{bmatrix} 1\cdot 0 & 1 \cdot 3 & 2\cdot 0 & 2\cdot 3 \\ 1\cdot 2 & 1 \cdot 1 & 2\cdot 2 & 2\cdot 1 \\ 3\cdot 0 & 3 \cdot 3 & 1\cdot 0 & 1\cdot 3 \\ 3\cdot 2 & 3 \cdot 1 & 1\cdot 2 & 1\cdot 1 \end{bmatrix}= \begin{bmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \end{bmatrix}

(2) Khatri-Rao product

对于两个矩阵 ARI×K\mathbf{A} \in \mathbb{R}^{I \times K}BRJ×K\mathbf{B} \in \mathbb{R}^{J \times K} ,其 Khatri-Rao product 表示为 AB\mathbf{A} \odot \mathbf{B} ,其结果为 (IJ)×K(IJ)\times K 大小的矩阵:

AB=[a1b1a2b2aKbK]\mathbf{A}\odot \mathbf{B}=\begin{bmatrix}\mathbf{a}_1\otimes \mathbf{b}_1 & \mathbf{a}_2\otimes \mathbf{b}_2 & \cdots & \mathbf{a}_K\otimes \mathbf{b}_K \end{bmatrix}

它由两个矩阵对应的列向量的Kronecker积排列而成。因此,Khatri-Rao积又叫做对应列Kronecker积。

注:aabb 是向量,则有 ab=aba\otimes b=a\odot b

(3) Hadamard product

按张量的对应元素相乘,需要两个矩阵的大小相同。对于两个矩阵 ARI×J\mathbf{A} \in \mathbb{R}^{I\times J}BRI×J\mathbf{B} \in \mathbb{R}^{I\times J} ,其 Hadamard product 表示为 AB\mathbf{A} * \mathbf{B} ,其结果为 I×JI\times J 大小的矩阵:

AB=[a11b11a12b12a1Jb1Ja21b21a22b22a2Jb2JaI1bI1aI2bI2aIJbIJ]\mathbf{A}*\mathbf{B}= \begin{bmatrix} a_{11}b_{11} & a_{12}b_{12} & \cdots & a_{1J}b_{1J} \\ a_{21}b_{21} & a_{22}b_{22} & \cdots & a_{2J}b_{2J} \\ \vdots & \vdots & \ddots & \vdots \\ a_{I1}b_{I1} & a_{I2}b_{I2} & \cdots & a_{IJ}b_{IJ} \end{bmatrix}


二、张量的Tucker分解

Tucker分解是SVD分解的高阶形式,其将张量分解为一个核张量与每一维度上对应矩阵的乘积。具体来说,以三阶张量 XRI×J×K\mathcal{X} \in \mathbb{R}^{I \times J \times K} 为例,其Tucker分解写为如下形式:

XG×1A×2B×3C=p=1Pq=1Qr=1Rgpqr apbqcr=[[G;A,B,C]]\begin{aligned} \mathcal{X} &\approx \mathcal{G} \times_1 \mathbf{A} \times_2 \mathbf{B} \times_3 \mathbf{C} \\ & = \sum_{p=1}^{P} \sum_{q=1}^{Q} \sum_{r=1}^{R} g_{pqr} \ \mathbf{a}_p \circ\mathbf{b}_q \circ \mathbf{c}_r \\ &= [[\mathcal{G};\mathbf{A}, \mathbf{B}, \mathbf{C}]] \end{aligned}

其中,ARI×P\mathbf{A} \in \mathbb{R}^{I \times P}BRJ×Q\mathbf{B} \in \mathbb{R}^{J \times Q}CRK×R\mathbf{C} \in \mathbb{R}^{K \times R} 是不同维度上的因子矩阵,这些矩阵通常被认为是不同维度上的主成分。GRP×Q×R\mathcal{G}\in\mathbb{R}^{P\times Q\times R} 称为核张量,其中的每个元素代表了不同成分之间的交互程度。

从元素的角度看,Tucker分解可以写为:

Xijkp=1Pq=1Qr=1Rgpqraipbjqckri=1,,I,j=1,,J,k=1,,K\mathbf{X}_{ijk} \approx \sum_{p=1}^{P} \sum_{q=1}^{Q} \sum_{r=1}^{R} \mathbf{g}_{pqr} \mathbf{a}_{ip} \mathbf{b}_{jq} \mathbf{c}_{kr} \\ i = 1,\cdots,I,\quad j=1,\cdots,J,\quad k=1,\cdots,K

P\mathbf{P}Q\mathbf{Q}R\mathbf{R}是因子矩阵 A,B,C\mathbf{A,B,C} 的成分数(例如因子矩阵的列数)。如果 P\mathbf{P}Q\mathbf{Q}R\mathbf{R} 小于I,J,K\mathbf{I,J,K},那么张量 G\mathcal{G} 可以被认为是张量 X\mathcal{X} 的压缩版本。

2.1 HOSVD算法

HOSVD算法

2.2 HOOI算法

X\mathcal{X} 是一个大小为 I1×I2××INI_1\times I_2 \times \cdots \times I_N 的 N 阶张量,那么计算 Tucker 分解要解决的优化问题为

minX[[G;A(1),A(2),,A(N)]](1)min \left \Vert \mathcal{X} - [[\mathcal{G}; \mathbf{A}^{(1)}, \mathbf{A}^{(2)},\cdots,\mathbf{A}^{(N)}]] \right \Vert \tag{1}

其中,GRR1×R2××RN\mathcal{G} \in \mathbb{R}^{R_1 \times R_2 \times \cdots \times R_N}, 矩阵 A(n)RIn×Rn\mathbf{A}^{(n)} \in \mathbb{R} ^{I_n \times R_n} 且列正交。

如果在最优解处,那么核张量 G\mathcal{G} 必然满足

G=X×1(A(1))T×2(A(2))T×3×N(A(N))T(2)\mathcal{G} = \mathcal{X} \times_1 (\mathbf{A}^{(1)})^T \times_2 (\mathbf{A}^{(2)})^T \times_3 \cdots \times_N (\mathbf{A}^{(N)})^T \tag{2}

将上式导入到公式(1)中,那么优化目标可以重写为:

X[[G;A(1),A(2),,A(N)]]2=X22X,[[G;A(1),A(2),,A(N)]]+[[G;A(1),A(2),,A(N)]]2=X22X×1(A(1))T×2×N(A(N))T,G+G2=X22G,G+G2=X2G2=X2X×1(A(1))T×2×N(A(N))T2\begin{aligned} &\left \Vert \mathcal{X}- [[\mathcal{G};\mathbf{A}^{(1)}, \mathbf{A}^{(2)},\cdots,\mathbf{A}^{(N)}]] \right \Vert^2 \\ &\qquad = \left \Vert \mathcal{X} \right \Vert^2 - 2 \left \langle \mathcal{X}, [[\mathcal{G};\mathbf{A}^{(1)}, \mathbf{A}^{(2)},\cdots,\mathbf{A}^{(N)}]] \right \rangle + \left \Vert [[\mathcal{G};\mathbf{A}^{(1)}, \mathbf{A}^{(2)},\cdots,\mathbf{A}^{(N)}]] \right \Vert^2 \\ &\qquad = \left \Vert \mathcal{X} \right \Vert^2 - 2 \left \langle \mathcal{X}\times_1 (\mathbf{A}^{(1)})^T\times_2\cdots \times_N(\mathbf{A}^{(N)})^T, \mathcal{G} \right \rangle + ||\mathcal{G}||^2 \\ &\qquad = \left \Vert \mathcal{X} \right \Vert^2 - 2 \left \langle \mathcal{G}, \mathcal{G} \right \rangle + \left \Vert \mathcal{G} \right \Vert^2 \\ &\qquad = \left \Vert \mathcal{X} \right \Vert^2 - \left \Vert \mathcal{G} \right \Vert^2 \\ &\qquad = \left \Vert \mathcal{X} \right \Vert^2 - \left \Vert \mathcal{X}\times_1 (\mathbf{A}^{(1)})^T\times_2\cdots \times_N(\mathbf{A}^{(N)})^T \right \Vert^2 \end{aligned}

最小化上述式子,即最大化下式:

maxA(n)X×1(A(1))T×2×N(A(N))Tsubject toA(n)RIn×Rnand columnwise orthogonal\max_{\mathbf{A}^{(n)}} \left \Vert \mathcal{X}\times_1 (\mathbf{A}^{(1)})^T\times_2\cdots \times_N(\mathbf{A}^{(N)})^T \right \Vert \\ \text{subject to} \quad \mathbf{A^{(n)}} \in \mathbb{R}^{I_n \times R_n} \quad \text{and columnwise orthogonal}

HOOI算法


标题: 张量分解
链接: https://www.fightingok.cn/detail/242
更新: 2022-11-13 19:52:21
版权: 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可