张量分解学习课件.ppt
第1页，此课件共47页哦2基本概念及记号第2页，此课件共47页哦3张量（tensor）多维数组一阶张量（一阶张量（向量）向量）二阶张量（二阶张量（矩阵）矩阵）三阶张量三阶张量第3页，此课件共47页哦4张量空间 由若干个向量空间中的基底的外积张成的空间向量的外积和内积向量的外积和内积第4页，此课件共47页哦5阶（order/ways/modes/rank）张成所属张量空间的向量空间的个数 一阶张量（向量）：二阶张量（矩阵）：三阶或更高阶张量：零阶张量（数量）：ixxijxXijkxXx三阶张量：三阶张量：I J K X第5页，此课件共47页哦6纤维（fiber）mode-1 mode-1（列）（列）纤维：纤维：:jkxmode-2 mode-2（行）（行）纤维：纤维：:i kxmode-3 mode-3（管）（管）纤维：纤维：:ijx第6页，此课件共47页哦7切片（slice）水平切片：水平切片：:iX侧面切片：侧面切片：:jX正面切片：正面切片：:()kkXX第7页，此课件共47页哦8内积和范数 设内积：（Frobenius）范数：12,NIIIX Y121 21 212111,NNNNIIIi iii iiiiixy X Y121 2122111,NNNIIIi iiiiix XX X第8页，此课件共47页哦9秩一张量/可合张量 N阶张量 是一个秩一张量，如果它能被写成N个向量的外积，即12NIIIX(1)(2)()NaaaXXcba三阶秩一张量：三阶秩一张量：a b cX第9页，此课件共47页哦10（超）对称和（超）对角 立方张量：各个mode的长度相等 对称：一个立方张量是对称的，如果其元素在下标的任意排列下是常数。如一个三阶立方张量是超对称的，如果 对角：仅当 时，,ijkikjjikjkikijkjixxxxxxi j k12Niii1 20Ni iix张量的（超）对角线张量的（超）对角线第10页，此课件共47页哦11展开（matricization/unfolding/flattening）将N阶张量 沿mode-n展开成一个矩阵 X(1)X三阶张量的三阶张量的mode-1mode-1展开展开()nXX第11页，此课件共47页哦12n-mode（矩阵）乘积 一个张量 和一个矩阵 的n-mode乘积 ，其元素定义为 这个定义可以写成沿mode-n展开的形式 性质：12NIIIXnJ IU111nnNIIJ IIn UX1 21111nNnnnNnIni iijiiijiiixuUX()()nnnUYUXYX,mnnmmnABBAXXnnnABBAXX第12页，此课件共47页哦13n-mode（向量）乘积 一个张量 和一个向量 的n-mode乘积 ，其元素定义为 性质：12NIIIXnIv111nnNIIIInvX1 21111nNnnnNnIni iiiiiiiixvvX1,mnmnnmmnababbaXXX第13页，此课件共47页哦14矩阵的Kronecker乘积 ，则 性质：111212122212JJIK JLIIIJaaaaaaaaaBBBBBBABBBB,I JK LABABCDACBD+ABAB第14页，此课件共47页哦15矩阵的Kronecker乘积 矩阵的Kronecker积还和张量和矩阵的n-mode乘积有如下关系(1)()1T()()(1)(1)(1)()()NNnNnnnnAAYAXAAAAYX第15页，此课件共47页哦16矩阵的Khatri-Rao乘积 ，则 性质：1122IJ KKKABababab,I KJ KABABCABCABC第16页，此课件共47页哦17矩阵的Hadamard乘积 ，则 性质：11 1112 121121 212222221122JJJJI JIIIIIJIJa ba ba ba ba ba ba ba ba bA B,I JI JAB TTTABABA AB B TTT+ABA AB BAB第17页，此课件共47页哦18CP分解第18页，此课件共47页哦19CP分解的其他名字 Polyadic Form of a Tensor,Hitchcock,1927 PARAFAC(Parallel Factors),Harshman,1970 CANDECOMP/CAND(Canonical decomposition),Carroll&Chang,1970 Topographic Components Model,Mcks,1988 CP(CANDECOMP/PARAFAC),Kiers,2000第19页，此课件共47页哦20CP分解的张量形式 将一个张量表示成有限个秩一张量之和，比如一个三阶张量可以分解为1,RrrrrA B CabcX三阶张量的三阶张量的CPCP分解分解X1cRc2c1bRb2b1aRa2a第20页，此课件共47页哦21CP分解的矩阵形式 因子矩阵：秩一张量中对应的向量组成的矩阵，如 利用因子矩阵，一个三阶张量的CP分解可以写成展开形式12RAaaaT(1)T(2)T(3)XA CBXB CAXC BA第21页，此课件共47页哦22rc()kDCP分解的切片形式 三阶张量的CP分解有时按（正面）切片写成如下形式：其中()TkkXADB():diag()kkDc三阶张量三阶张量CPCP分解的正面切片形式分解的正面切片形式XATBrarbkX第22页，此课件共47页哦23带权CP分解 为了计算方便，通常假设因子矩阵的列是单位长度的，从而需要引入一个权重向量 ，使CP分解变为 对于高阶张量，有其展开形式为1;,Rrrrrr A B CabcXR(1)(2)()(1)(2)()1;,RNNrrrrr AAAaaaXT()()(1)(1)(1)()diag()nNnnnXAAAAA第23页，此课件共47页哦24张量的秩和秩分解 张量 的秩定义为用秩一张量之和来精确表示 所需要的秩一张量的最少个数，记为 秩分解：可见秩分解是一个特殊的CP分解，对应于矩阵的SVD 目前还没有方法能够直接求解一个任意给定张量的秩，这被证明是一个NP-hard问题XXrank()Xrank()(1)(2)()1NrrrraaaXX第24页，此课件共47页哦25张量的秩 不同于矩阵的秩，高阶张量的秩在实数域和复数域上不一定相同。例如一个三阶张量在实数域内进行秩分解得到的因子矩阵为而在复数域内进行分解得到的因子矩阵为X121001 0110XX101101110 0110111 1 1ABC11111111 22iiiiiiABC第25页，此课件共47页哦26张量的低秩近似 相对于矩阵的SVD来说，高阶张量的秩分解唯一性不需要正交性条件保证，只需满足：这里 表示矩阵 的k-秩：任意k列都线性无关的最大的k()121nNnkRNAkAA第26页，此课件共47页哦27张量的低秩近似 然而在低秩近似方面，高阶张量的性质比矩阵SVD差 Kolda给出了一个例子，一个立方张量的最佳秩-1近似并不包括在其最佳秩-2近似中，这说明张量的秩-k近似无法渐进地得到 下面的例子说明，张量的“最佳”秩-k近似甚至不一定存在112121211121212111111 abcabcabcaabbccabcXY第27页，此课件共47页哦28张量的低秩近似 退化：如果一个张量能够被一系列的低秩张量任意逼近 边缘秩（border rank）：能够任意逼近一个张量的最少的成分个数秩秩2 2秩秩3 3Y(0)X(1)X(2)XX一个秩为一个秩为2 2的张量序列收敛到一个秩的张量序列收敛到一个秩3 3张量张量第28页，此课件共47页哦29CP分解的计算 分解成多少个秩一张量（成分）之和？通常的做法是从1开始尝试，知道碰到一个“好”的结果为止 如果有较强的应用背景和先验信息，可以预先指定 对于给定的成分数目，怎么求解CP分解？目前仍然没有一个完美的解决方案 从效果来看，交替最小二乘（Alternating Least Square）是一类比较有效的算法第29页，此课件共47页哦30CP分解的计算 以一个三阶张量 为例，假定成分个数 已知，目标为 作为ALS的一个子问题，固定 和 ，求解得再通过归一化分别求出 和XR1min s.t.;,Rrrrrrabc A B CXXXXBCT(1)mindiag()FAXACBTTT(1)(1)diag()+AXCBXCBC C B BA第30页，此课件共47页哦31CP分解的计算 ALS算法并不能保证收敛到一个极小点，甚至不一定能收敛到稳定点，它只能找到一个目标函数不再下降的点 算法的初始化可以是随机的，也可以将因子矩阵初始化为对应展开的奇异向量，如将 初始化为 的前 个左奇异向量A(1)XR第31页，此课件共47页哦32CP分解的应用 计量心理学 语音分析 化学计量学 独立成分分析 神经科学 数据挖掘 高维算子近似 随即偏微分方程 第32页，此课件共47页哦33Tucker分解第33页，此课件共47页哦34Tucker分解的其他名字 Three-mode factor analysis(3MFA/Tucker3),Tucker,1966 Three-mode principal component analysis(3MPCA),Kroonenberg&De Leeuw,1980 N-mode principal components analysis,Kapteyn et al.,1986 Higher-order SVD(HOSVD),De Lathauwer et al.,2000 N-mode SVD,Vasilescu and Terzopoulos,2002第34页，此课件共47页哦35Tucker分解 Tucker分解是一种高阶的主成分分析，它将一个张量表示成一个核心（core）张量沿每一个mode乘上一个矩阵。对于三阶张量 来说，其Tucker分解为 因子矩阵 通常是正交的，可以视为沿相应mode的主成分123111;,QPRpqrpqrpqrgA B CABCabcXGG,I PJ QK RABCI J K X第35页，此课件共47页哦36Tucker分解 容易看出，CP分解是Tucker分解的一种特殊形式：如果核心张量 是对角的，且 ，则Tucker分解就退化成了CP分解GPQR三阶张量的三阶张量的TuckerTucker分解分解X23BCGAG13ACG12ABGCB第36页，此课件共47页哦37Tucker分解的矩阵形式 三阶Tucker分解的展开形式为 Tucker分解可以推广到高阶张量T(1)(1)T(2)(2)T(3)(3)XAGCBXBGCAXCGBA(1)(2)()(1)(2)()12;,NNNAAAAAAXGGT()()(1)(1)(1)()()nNnnnnXAGAAAA第37页，此课件共47页哦38Tucker2和Tucker1 对于三阶张量固定一个因子矩阵为单位阵，就得到Tucker分解一个重要的特例：Tucker2。例如固定 ，则 进一步，固定两个因子矩阵，就得到了Tucker1，例如令第二、三个因子矩阵为单位阵，则Tucker分解就退化成了普通的PCA12;,ABA B IXGGCI1(1)(1);,AA I IXAGXGG第38页，此课件共47页哦39张量的n-秩近似 一个N阶张量 的n-秩定义为 若设 ，则 叫做一个秩-张量 如果 ，则很容易得到 的一个精确秩-Tucker分解；然而如果至少有一个 使得 ，则通过Tucker分解得到的就是 的一个秩-近似X()rank()rank()nnXXrank(),1,nnR nNX12,NR RRXrank(),1,nnR nNX12,NR RRXnrank()nnRX12,NR RRX第39页，此课件共47页哦40张量的n-秩近似XGBCA1R1rank()X截断的截断的TuckerTucker分解：秩分解：秩-近似近似123,R R R第40页，此课件共47页哦41张量的n-秩近似 对于固定的n-秩，Tucker分解的唯一性不能保证，所以需要添加其他的约束 通常要求核心张量是“简单”的，如各个mode的主成分之间尽量不发生相互作用（稀疏性），或者其他的“简单性”约束第41页，此课件共47页哦42Tucker分解的计算 HOSVD：利用SVD对每个mode做一次Tucker1分解（截断或者不截断）HOSVD不能保证得到一个较好的近似，但HOSVD的结果可以作为一个其他迭代算法（如HOOI）的很好的初始解第42页，此课件共47页哦43Tucker分解的计算 为了导出HOOI迭代算法，先考虑目标函数 从而 应该满足(1)()()(1);,vec()vec()NNAAAAXGXGG(1)T()T1NNAAGX第43页，此课件共47页哦44Tucker分解的计算 目标函数的平方变为2(1)()22(1)()(1)()22(1)T()T12222(1)T()T1 ;,2,;,;,2,2,NNNNNNNAAAAAAAAAAXGXXGGXXGGXG GGXX第44页，此课件共47页哦45Tucker分解的计算 所以问题可以进行如下转化 利用交替求解的思想，问题变为解如下子问题这个问题可以通过令 为 的前 个左奇异值向量来解决(1)()(1)T()T1 min;,maxNNNAAAAXGX()T()(1)(1)(1)()maxs.t.nNnnnAWWXAAAA()nAWnR第45页，此课件共47页哦46Tucker分解的应用 化学分析 计量心理学 信号处理 机器视觉（面部、动作）数据压缩 纹理生成 数据挖掘 环境和网络建模 第46页，此课件共47页哦2022-9-6感谢大家观看第47页，此课件共47页哦
