张量分解(5)——Tucker分解

大家好，欢迎来到IT知识分享网。

🍅 写在前面
👨‍🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
                       LeetCode算法实例
                       张量分解

张量分解系列知识，详见下方链接：

张量分解(1)——初探张量

张量分解(2)——张量运算

张量分解(3)——CP分解

张量分解(4)——SVD奇异值分解

张量分解(5)——Tucker分解

Tucker分解综述

Tucker分解是高阶主成分分析的一种形式，它将一个张量分解成核张量与每一维矩阵的乘积。三维张量Tucker分解表示如下图：

Tucker分解公式

以三维张量$\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$为例，可以得到Tucker分解公式为：
$$\mathbf{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}]]$$
有了前几节基础知识的铺垫，相信这里公式不难理解。
这里$\mathbf{A}\in {\mathbb{R}}^{I\times P},\mathbf{B}\in {\mathbb{R}}^{J\times Q}$, and $\mathbf{C}\in {\mathbb{R}}^{K\times R}$是张量的因子矩阵，它们通常是正交的，可以将它们看做每一个维度上的主要成分。
扩展到更高维度，Tucker分解的公式如图：

Tucker分解也能够转化为矩阵形式，具体形式为：
$$\begin{array}{rl}& {\mathbf{X}}_{(1)}\approx {\mathbf{AG}}_{(1)}(\mathbf{C}\otimes \mathbf{B}{)}^{\top },\\ & {\mathbf{X}}_{(2)}\approx {\mathbf{BG}}_{(2)}(\mathbf{C}\otimes \mathbf{A}{)}^{\top },\\ & {\mathbf{X}}_{(3)}\approx {\mathbf{CG}}_{(3)}(\mathbf{B}\otimes \mathbf{A}{)}^{\top }.\end{array}$$

Tucker分解优化

Tucker分解的优化通常有两种方法，分别是HOSVD和HOOI。
1、HOSVD:higher-order SVD(HOSVD)，它通过张量的每一个mode上做SVD分解对各个mode上的因子矩阵进行求解,最后计算张量在各个mode上的投影之后的张量作为核张量。它的算法过程如下图所示：

最终优化目标为：
$$\left|\mathcal{X}-\left[\left[\mathcal{G};{\mathbf{A}}^{(1)},\cdots ,{\mathbf{A}}^{(\mathbb{N})}\right]\right]\right|=\left|\mathrm{vec}(\mathcal{X})-\left({\mathbf{A}}^{(\mathbb{N})}\otimes \cdots \otimes {\mathbf{A}}^{(1)}\right)\mathrm{vec}(\mathcal{G})\right|$$
整体平方化简得：
$$\begin{array}{rl}& {\Vert \mathcal{X}-\left[\mathcal{G};{\mathbf{A}}^{(1)},\cdots ,{\mathbf{A}}^{(\mathrm{N})}\right]\Vert }^2\\ =& \Vert \mathcal{X}{\Vert }^2-2⟨\mathcal{X},[\mathcal{G};{\mathbf{A}}^{(1)},\cdots ,{\mathbf{A}}^{(\mathrm{N})}\Vert ⟩+\Vert \mathcal{G};{\mathbf{A}}^{(1)},\cdots ,{\mathbf{A}}^{(\mathrm{N})}]{\Vert }^2\\ =& \Vert \mathcal{X}{\Vert }^2-2⟨\mathcal{X}{\times }_1{\mathbf{A}}^{(1)\mathrm{T}}\dots {\times }_{\mathrm{N}}{\mathbf{A}}^{(\mathrm{N})\mathrm{T}},\mathcal{G}⟩+\Vert \mathcal{G}{\Vert }^2\\ =& \Vert \mathcal{X}{\Vert }^2-2⟨\mathcal{G},\mathcal{G}⟩+\Vert \mathcal{G}{\Vert }^2\\ =& \Vert \mathcal{X}{\Vert }^2-{\Vert \mathcal{X}{\times }_1{\mathbf{A}}^{(1)\mathrm{T}}\cdots {\times }_{\mathrm{N}}{\mathbf{A}}^{(\mathrm{N})\mathrm{T}}\Vert }^2\end{array}$$
由于 $\Vert \mathcal{X}\Vert$ 是一个常数,最小化上面的式子相当于最大化后面的: $\max \Vert \mathcal{X}\times {}_1{\mathbf{A}}^{(1)\mathrm{T}}\cdots {\times }_{\mathrm{N}}{\mathbf{A}}^{(\mathrm{N})\mathrm{T}}\Vert$最终得到:
$$\begin{array}{rl}& \max \Vert {\mathbf{A}}^{(\mathrm{n})\mathrm{T}}\mathbf{W}\Vert \\ & \text{ s.t. }\mathbf{W}={\mathbf{X}}_{(\mathrm{n})}\left({\mathbf{A}}^{(\mathrm{N})}\otimes \dots \otimes {\mathbf{A}}^{(\mathrm{n}+1)}\otimes {\mathbf{A}}^{(\mathrm{n}-1)}\cdots \otimes {\mathbf{A}}^{(1)}\right)\\ & \end{array}$$
2、HOOI:这个算法本人还不是太了解，暂且将步骤放在这里。