张量分解学习

《张量分解学习》由会员分享，可在线阅读，更多相关《张量分解学习（47页珍藏版）》请在装配图网上搜索。

1、彭毅 1 基本概念及记号 2 张量（tensor）多维数组 3 一 阶 张 量（ 向 量 ）二 阶 张 量（ 矩 阵 ） 三 阶 张 量 张量空间由若干个向量空间中的基底的外积张成的空间 4向 量 的 外 积 和 内 积 阶（order/ways/modes/rank）张成所属张量空间的向量空间的个数一阶张量（向量）：二阶张量（矩阵）：三阶或更高阶张量：零阶张量（数量）： 5 ixx ijxX ij kxX x 三 阶 张 量 ： I J K X 纤维（fiber） 6mode-1 （ 列） 纤 维 ： :jkx mode-2 （ 行） 纤 维 ： :i kx mode-3 （ 管 ）纤 维

2、： :ijx 切片（slice） 7水 平 切 片 ： :iX 侧 面 切 片 ： : :jX 正 面 切 片 ： : ( )k kX X 内积和范数设内积：（Frobenius）范数： 8 1 2, NI I I X Y 1 2 1 2 1 21 21 1 1, N N NNII I i i i i i ii i i x y X Y 1 2 1 21 2 21 1 1, N NNII I i i ii i i x X X X 秩一张量/可合张量 N阶张量 是一个秩一张量，如果它能被写成N个向量的外积，即 9 1 2 NI I I X (1) (2) ( )Na a aX X c ba三 阶

3、秩 一 张 量 ： a b cX （超）对称和（超）对角立方张量：各个mode的长度相等对称：一个立方张量是对称的，如果其元素在下标的任意排列下是常数。如一个三阶立方张量是超对称的，如果对角：仅当 时， 10 , , ,ijk ikj jik jki kij kjix x x x x x i j k 1 2 Ni i i 1 2 0Ni i ix 张 量 的 （ 超 ） 对 角 线 展开（matricization/unfolding/flattening）将N阶张量 沿mode-n展开成一个矩阵 11 X(1)三 阶 张 量 的 mode-1展 开 ( )nXX n-mode（矩阵）乘积一个

4、张量 和一个矩阵 的n-mode乘积 ，其元素定义为这个定义可以写成沿mode-n展开的形式性质： 12 1 2 NI I I X nJ I U 1 1 1n n NI I J I In UX 1 21 1 1 1n N nn n N nIn i i i jii i ji i i x u UX ( ) ( )n n n U Y UXY X , m n n m m n A B B AX X n n n A B BAX X n-mode（向量）乘积一个张量 和一个向量 的n-mode乘积 ，其元素定义为性质： 13 1 2 NI I I X nIv 1 1 1n n NI I I In vX 1

5、21 1 1 1n N nn n N nIn i i i ii i i i i x v vX 1 ,m n m n n m m n a b a b b aX X X 矩阵的Kronecker乘积 ，则性质： 14 11 12 121 22 21 2 JJ IK JLI I IJa a aa a aa a a B B BB B BA B B B B ,I J K L A B A B C D AC BD + + +A B A B 矩阵的Kronecker乘积矩阵的Kronecker积还和张量和矩阵的n-mode乘积有如下关系 15 (1) ( )1 T( ) ( ) ( 1) ( 1) (1)(

6、) ( ) NNn N n nn n A AY A X A A A AY X 矩阵的Khatri-Rao乘积 ，则性质： 16 1 1 2 2 IJ KK K A B a b a b a b,I K J K A B A B C A B C A B C 矩阵的Hadamard乘积 ，则性质： 17 11 11 12 12 1 121 21 22 22 2 21 1 2 2 J JJ J I JI I I I IJ IJa b a b a ba b a b a ba b a b a b A B ,I J I J A B T T T A B A B A A B B TT T +A B A A B B

7、 A B CP分解 18 CP分解的其他名字 Polyadic Form of a Tensor, Hitchcock, 1927 PARAFAC(Parallel Factors), Harshman, 1970 CANDECOMP/CAND(Canonical decomposition), Carroll , , R r r r rr A B C a b cX R(1) (2) ( ) (1) (2) ( )1; , , , RN Nr r r rr A A A a a aX T( ) ( ) ( 1) ( 1) (1)( ) diag( )n N n nn X A A A A A 张量

8、的秩和秩分解张量 的秩定义为用秩一张量之和来精确表示 所需要的秩一张量的最少个数，记为秩分解：可见秩分解是一个特殊的CP分解，对应于矩阵的SVD目前还没有方法能够直接求解一个任意给定张量的秩，这被证明是一个NP-hard问题 24 X Xrank( )Xrank( ) (1) (2) ( )1 Nr r rr a a aXX 张量的秩不同于矩阵的秩，高阶张量的秩在实数域和复数域上不一定相同。例如一个三阶张量在实数域内进行秩分解得到的因子矩阵为而在复数域内进行分解得到的因子矩阵为 25 X1 21 0 0 1 0 1 1 0 X X1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1

9、1 1 A B C1 1 1 1 1 11 1 2 2i i i i i i A B C 张量的低秩近似相对于矩阵的SVD来说，高阶张量的秩分解唯一性不需要正交性条件保证，只需满足：这里 表示矩阵 的k-秩：任意k列都线性无关的最大的k 26 ( )1 2 1nNn k R N AkA A 张量的低秩近似然而在低秩近似方面，高阶张量的性质比矩阵SVD差 Kolda给出了一个例子，一个立方张量的最佳秩-1近似并不包括在其最佳秩-2近似中，这说明张量的秩-k近似无法渐进地得到下面的例子说明，张量的“最佳”秩-k近似甚至不一定存在 27 1 1 2 1 2 1 2 1 11 2 1 2 1 2 1

10、1 11 1 1 a b c a b c a b ca a b b c c a b cXY 张量的低秩近似退化：如果一个张量能够被一系列的低秩张量任意逼近边缘秩（border rank）：能够任意逼近一个张量的最少的成分个数 28 秩 2 秩 3 Y(0)X (1)X (2)X X一 个 秩 为 2的 张 量 序 列 收 敛 到 一 个 秩 3张 量 CP分解的计算分解成多少个秩一张量（成分）之和？通常的做法是从1开始尝试，知道碰到一个“好”的结果为止如果有较强的应用背景和先验信息，可以预先指定对于给定的成分数目，怎么求解CP分解？目前仍然没有一个完美的解决方案从效果来看，交替最小二乘（Alt

11、ernating Least Square）是一类比较有效的算法 29 CP分解的计算以一个三阶张量 为例，假定成分个数 已知，目标为作为ALS的一个子问题，固定 和 ，求解得再通过归一化分别求出 和 30 X R 1 min s.t. ; , ,R r r r rr a b c A B CX X X X B C T(1)min diag( ) FA X A C B T T T(1) (1)diag( ) + +A X C B X C B C C B BA CP分解的计算 ALS算法并不能保证收敛到一个极小点，甚至不一定能收敛到稳定点，它只能找到一个目标函数不再下降的点算法的初始化可以是随机的

12、，也可以将因子矩阵初始化为对应展开的奇异向量，如将 初始化为 的前 个左奇异向量 31 A (1)X R CP分解的应用计量心理学语音分析化学计量学独立成分分析神经科学数据挖掘高维算子近似随即偏微分方程 32 Tucker分解 33 Tucker分解的其他名字 Three-mode factor analysis(3MFA/Tucker3), Tucker, 1966 Three-mode principal component analysis(3MPCA), Kroonenberg , , QP R pqr p q rp q r g A B C A B C a b cX G G , ,I

13、P J Q K R A B CI J K X Tucker分解容易看出，CP分解是Tucker分解的一种特殊形式：如果核心张量 是对角的，且 ，则Tucker分解就退化成了CP分解 36 G P Q R 三 阶 张 量 的 Tucker分 解X 2 3 B CGA G 1 3 A CG 1 2 A BG C B Tucker分解的矩阵形式三阶Tucker分解的展开形式为 Tucker分解可以推广到高阶张量 37 T(1) (1) T(2) (2) T(3) (3) X AG C BX BG C AX CG B A(1) (2) ( ) (1) (2) ( ) 1 2 ; , , ,N NN A

14、 A A A A AX G G T( ) ( ) ( 1) ( 1) (1)( ) ( )n N n nn n X A G A A A A Tucker2和Tucker1对于三阶张量固定一个因子矩阵为单位阵，就得到Tucker分解一个重要的特例：Tucker2。例如固定 ，则进一步，固定两个因子矩阵，就得到了Tucker1，例如令第二、三个因子矩阵为单位阵，则Tucker分解就退化成了普通的PCA 38 1 2 ; , , A B A B IX G G C I1 (1) (1); , , A A I I X AGX G G 张量的n-秩近似一个N阶张量 的n-秩定义为若设 ，则 叫做一个秩-

15、张量如果 ，则很容易得到 的一个精确秩- Tucker分解；然而如果至少有一个 使得 ，则通过Tucker分解得到的就是 的一个秩- 近似 39 X ( )rank ( ) rank( )n n XXrank ( ) , 1, ,n nR n N X 1 2, , , NR R R Xrank ( ) , 1, ,n nR n N X 1 2, , , NR R R Xn rank ( )n nRX 1 2, , , NR R RX 张量的n-秩近似 40 X G BCA1R 1rank ( )X截 断 的 Tucker分 解 ： 秩 - 近 似 1 2 3, ,R R R 张量的n-秩近似对

16、于固定的n-秩，Tucker分解的唯一性不能保证，所以需要添加其他的约束通常要求核心张量是“简单”的，如各个mode的主成分之间尽量不发生相互作用（稀疏性），或者其他的“简单性”约束 41 Tucker分解的计算 HOSVD：利用SVD对每个mode做一次Tucker1分解（截断或者不截断） HOSVD不能保证得到一个较好的近似，但HOSVD的结果可以作为一个其他迭代算法（如HOOI）的很好的初始解 42 Tucker分解的计算为了导出HOOI迭代算法，先考虑目标函数从而 应该满足 43 (1) ( )( ) (1) ; , ,vec( ) vec( )NN A AA AX GX G G (1

17、)T ( )T1 NN A AG X Tucker分解的计算目标函数的平方变为 44 2(1) ( ) 22 (1) ( ) (1) ( )2 2(1)T ( )T12 2 22 (1)T ( )T1 ; , ,2 , ; , , ; , ,2 ,2 , N N NNN NN A AA A A AA AA AX GX X G GX X G GX G G GX X Tucker分解的计算所以问题可以进行如下转化利用交替求解的思想，问题变为解如下子问题这个问题可以通过令 为 的前 个左奇异值向量来解决 45 (1) ( )(1)T ( )T1 min ; , ,max NNN A AA AX GX ( )T ( ) ( 1) ( 1) (1)( )maxs.t. n N n nn A WW X A A A A ( )nA W nR Tucker分解的应用化学分析计量心理学信号处理机器视觉（面部、动作）数据压缩纹理生成数据挖掘环境和网络建模 46 47