一种新的全连接张量网络分解：突破TT和TR分解的局限性｜AAAI 2021

作者 | 郑玉棒

编辑 | 陈大鑫

近日电子科技大学张量建模与计算团队与日本理化学研究所张量学习团队一篇合作论文被人工智能领域顶级会议AAAI 2021 (CCF A类推荐会议) 接收，标题为《Fully-Connected Tensor Network Decomposition and Its Application to Higher-Order Tensor Completion》。

论文第一作者为电子科技大学博士生郑玉棒，通讯作者为电子科技大学黄廷祝教授和赵熙乐教授，合作作者为日本理化学研究所张量学习团队负责人Qibin Zhao博士和西南财经大学蒋太翔副教授。

论文链接：https://www.aaai.org/AAAI21Papers/AAAI-4990.ZhengY.pdf 或 https://yubangzheng.github.io/

代码链接：https://yubangzheng.github.io/

主要内容

论文提出了一种全连接张量网络 (fully-connected tensor network, FCTN) 分解。

其优势在于：

(1) 建立了任意两个因子间的运算，使其可以充分地刻画张量任意两个模式 (modes) 间的相关性；

(2) 具有转置不变性，即对于不同的张量mode排列，分解本质上是相同的。进一步地，论文将FCTN分解应用到张量填充任务中，设计了基于临近交替极小化 (proximal alternating minimization, PAM [1]) 的求解算法，证明了算法的收敛性。

1

研究背景

信息技术的飞速发展使得数据形式逐渐趋向高维化，如视频数据、高光谱图像以及交通流量数据，通常可用张量表示。然而，高维数据往往存在像素缺失现象，如成像条件不佳导致高光谱图像部分像素被云覆盖以及感知器故障导致交通数据在连续时间内元素缺失 (如图1所示)，这种退化现象严重影响了其后续应用。

张量填充旨在从部分的观测数据中反推出完整的真实数据，属于经典的反问题，通常需要利用正则化方法引入高维数据的先验知识 (内在性质) 限制解空间并稳定求解过程。在众多先验知识中，高维数据的全局相关性 (低秩性) 尤为重要。

图1：被云覆盖的高光谱图像和具有元素缺失的交通数据

张量分解旨在将一个高阶张量分解为一系列低维因子，对张量的全局相关性具有强大的捕捉能力。

在过去的十年中，Tucker和CANDECOMP/PARAFAC (CP) 分解 [2] 取得了巨大的成功。但是Tucker分解只能描述张量一个mode与其他所有modes之间的相关性，而不是任意两个modes之间的相关性，且需要较高的存储成本；CP分解无法灵活刻画张量不同modes之间的不同相关性。

最近几年，张量链 (tensor train, TT) 和张量环 (tensor ring, TR) 分解显示出了处理高阶，特别是超过三阶张量的强大能力 [3,4]。

更具体地说，TT分解将一个N阶张量分解为N-2个三阶张量和两个矩阵。并且，从第一个TT因子 (矩阵) 开始，每个因子都需要与下一个因子进行运算，直到最后一个因子 (矩阵)。TR分解用三阶张量代替了TT因子中的两个矩阵，并在它们之间建立了额外的运算。

但是TT和TR分解有两个明显的局限性：

(1) 这两种分解方法只建立了相邻两个因子之间的运算，而不是任意两个因子之间的联系，导致其相关性度量能力有限；

(2) 它们只在张量的modes作反向排列 (TT和TR) 或循环移动 (TR) 时具有不变性，这意味着TT和TR分解对张量mode的排列高度敏感。

那么如何解决这些问题？

图2：Tucker、CP、TT和TR分解

2

新型张量分解：全连接张量网络分解

该论文提出了一种新的张量分解，即全连接张量网络 (FCTN) 分解，它将一个N阶张量分解成一系列低维的N阶因子，并在任意两个因子之间建立了一个运算，其数学表达形式为：

FCTN秩定义为由组成的向量。

图3：FCTN分解

图3展示了FCTN分解的图表示。可以看到，在二阶情况下，FCTN分解实际上是矩阵分解，而FCTN秩实际上是矩阵秩。此外，对于高阶张量，任意两个FCTN因子间都有一个大小相等的mode用于进行运算，这使得FCTN分解能够充分表征张量任意两个modes之间的相关性。

众所周知，矩阵分解具有转置不变性，即而对于高阶张量，论文证明了FCTN分解同样具有广义转置不变性，即

也就是说对于不同的张量mode排列，FCTN分解本质上是相同的。这意味着在使用FCTN分解时，不需要考虑张量mode排列顺序。而对于TT和TR分解，不同的mode排列对应的分解是不同的，使用时通常需要寻找最优mode排列。

3

基于全连接网络分解的张量填充模型

为了验证FCTN分解的优越性，论文将其应用于张量填充任务，建立了如下基于FCTN分解的张量填充模型

同时，论文设计了一种基于临近交替极小化的求解算法，并证明了其理论收敛性。

4

实验结果

4.1 仿真数据实验

仿真数据实验主要是通过对比相应填充方法的性能，验证论文提出的FCTN分解相对于TT和TR分解的优越性。所有方法均由PAM求解以消除算法的影响。

此外，对于每个数据，论文测试两种张量mode排列，即原始排序和一种广义置换。重建张量与真实张量之间的相对误差 (RSE) 被用来评价不同方法的性能，图4为不同缺失率(missing ratio, MR)下不同方法的重建结果。

图4：不同缺失率下不同方法的重建结果

从图4可以观察到，首先，FCTN-TC方法对不同的张量mode排列具有鲁棒性，而TT-TC和TR-TC方法的性能对其比较敏感；

其次，在不同的数据、缺失率和mode排列情况下，FCTN-TC方法在三种方法中总是获得最低的RSE值，也就是最优的重建效果。

4.2 真实数据实验

在真实数据实验中，论文选取了基于不同张量分解的张量填充模型作为对比方法，即HaLRTC [5]、TMac [6]、t-SVD [7]、TMacTT [8] 和TRLRF [9]。PSNR和RSE被用来评价不同方法的性能。

表1报道了四个彩色视频 (http://trace.eas.asu.edu/yuv/) 在不同缺失率下所有比较方法的PSNR值和运行时间。

可以看到，在所有测试数据上，所提出的FCTN-TC方法与其他方法相比性能更佳。

表1：四个彩色视频在不同缺失率下所有比较方法的PSNR值和运行时间

在交通数据中，传感器故障通常会导致一段时间的数据全部丢失。因此，论文考虑列缺失问题。

图5展示了某一天的重构结果以及整个数据的RSE值。可以看出，论文提出的FCTN-TC方法在所有对比方法中取得了最好的结果。

图5：40%缺失率下不同方法在某一天的重建结果以及整个数据的RSE值

5

总结

这项工作有三方面的贡献。

第一，提出了一种全连接张量网络分解，它突破了TT和TR分解的局限性；

第二，将全连接张量网络分解应用于张量填充问题，并设计了一种基于PAM的求解算法；

第三，从理论上论证了算法的收敛性。

参考文献：

[1] Attouch, H.; Bolte, J.; and Svaiter, B. F.; Convergence of Descent Methods for Semi-Algebraic and Tame Problems: Proximal Algorithms, Forward-Backward Splitting, and Regularized Gauss-Seidel Methods, Mathematical Programming, 137(1): 91-129, 2013.

[2] Kolda, T. G.; and Bader, B. W.;  Tensor Decompositions and Applications, SIAM Review, 51(3): 455-500, 2009.

[3] Oseledets, I. V.; Tensor-Train Decomposition, SIAM Journal on Scientifific Computing 33(5): 2295-2317, 2021.

[4] Zhao, Q.; Zhou, G.; Xie, S.; Zhang, L.; and Cichocki, A; Tensor Ring Decomposition, arXiv preprint arXiv:1606.05535, 2016.

[5] Liu, J.; Musialski, P.; Wonka, P.; and Ye, J.; Tensor Completion for Estimating Missing Values in Visual Data, IEEE Transactions on Pattern Analysis and Machine Intelligence 35(1): 208-220, 2013.

[6] Xu, Y.; Hao, R.; Yin, W.; and Su, Z; Parallel Matrix Factorization for Low-Rank Tensor Completion, Inverse Problems and Imaging, 9(2): 601-624, 2015.

[7] Zhang, Z.; and Aeron, S; Exact Tensor Completion Using T-SVD, IEEE Transactions on Signal Processing, 65(6): 1511-1526, 2017.

[8] Bengua, J. A.; Phien, H. N.; Tuan, H. D.; and Do, M. N.; Effificient Tensor Completion for Color Image and Video Recovery: Low-Rank Tensor Train, IEEE Transactions on Image Processing, 26(5): 2466-2479, 2017.

[9] Yuan, L.; Li, C.; Mandic, D.; Cao, J.; and Zhao, Q.; Tensor Ring Decomposition with Rank Minimization on Latent Space: An Effificient Approach for Tensor Completion, In Proceedings of the AAAI Conference on Artifificial Intelligence, 9151-9158, 2019.