张量分解学习

彭毅1基本概念及记号2张量（tensor）◦多维数组3一阶张量（向量）二阶张量（矩阵）三阶张量张量空间◦由若干个向量空间中的基底的外积张成的空间4向量的外积和内积阶（order/ways/modes/rank）◦张成所属张量空间的向量空间的个数一阶张量（向量）：二阶张量（矩阵）：三阶或更高阶张量：零阶张量（数量）：5{}ixx{}ijxX{}ijkxXx三阶张量：IJK××X纤维（fiber）6mode-1（列）纤维：:jkxmode-2（行）纤维：:ikxmode-3（管）纤维：:ijx切片（slice）7水平切片：::iX侧面切片：::jX正面切片：::()kkXX内积和范数◦设内积：（Frobenius）范数：812,NIII×××XY12121212111,NNNNIIIiiiiiiiiixyXY1212122111,NNNIIIiiiiiixXXX秩一张量/可合张量◦N阶张量是一个秩一张量，如果它能被写成N个向量的外积，即912NIII×××X(1)(2)()NaaaXXcba三阶秩一张量：abcX（超）对称和（超）对角◦立方张量：各个mode的长度相等◦对称：一个立方张量是对称的，如果其元素在下标的任意排列下是常数。如一个三阶立方张量是超对称的，如果◦对角：仅当时，10,,,ijkikjjikjkikijkjixxxxxxijk12Niii120Niiix张量的（超）对角线展开（matricization/unfolding/flattening）◦将N阶张量沿mode-n展开成一个矩阵11X(1)X三阶张量的mode-1展开()nXXn-mode（矩阵）乘积◦一个张量和一个矩阵的n-mode乘积，其元素定义为◦这个定义可以写成沿mode-n展开的形式◦性质：1212NIII×××XnJI×U111nnNIIJIIn××××××UX121111nNnnnNnIniiijiiijiiixuUX()()nnnUYUXYX,mnnmmnABBAXXnnnABBAXXn-mode（向量）乘积◦一个张量和一个向量的n-mode乘积，其元素定义为◦性质：1312NIII×××XnIv111nnNIIIIn×××××vX121111nNnnnNnIniiiiiiiiixvvX1,mnmnnmmnababbaXXX矩阵的Kronecker乘积◦，则◦性质：14111212122212JJIKJLIIIJaaaaaaaaa×BBBBBBABBBB,IJKL××ABABCDACBD+++ABAB矩阵的Kronecker乘积◦矩阵的Kronecker积还和张量和矩阵的n-mode乘积有如下关系15(1)()1T()()(1)(1)(1)()()NNnNnnnnAAYAXAAAAYX矩阵的Khatri-Rao乘积◦，则◦性质：161122IJKKK×ABababab,IKJK××ABABCABCABC矩阵的Hadamard乘积◦，则◦性质：17111112121121212222221122JJJJIJIIIIIJIJababababababababab×AB,IJIJ××ABTTTABABAABBTTT++ABAABBABCP分解18CP分解的其他名字◦PolyadicFormofaTensor,Hitchcock,1927◦PARAFAC(ParallelFactors),Harshman,1970◦CANDECOMP/CAND(Canonicaldecomposition),Carroll&Chang,1970◦TopographicComponentsModel,Möcks,1988◦CP(CANDECOMP/PARAFAC),Kiers,200019CP分解的张量形式◦将一个张量表示成有限个秩一张量之和，比如一个三阶张量可以分解为201,,RrrrrABCabcX三阶张量的CP分解X1cRc2c1bRb2b1aRa2aCP分解的矩阵形式◦因子矩阵：秩一张量中对应的向量组成的矩阵，如◦利用因子矩阵，一个三阶张量的CP分解可以写成展开形式2112RAaaaT(1)T(2)T(3)XACBXBCAXCBArc()kDCP分解的切片形式◦三阶张量的CP分解有时按（正面）切片写成如下形式：其中22()TkkXADB():diag()kkDc三阶张量CP分解的正面切片形式XATBrarbkX带权CP分解◦为了计算方便，通常假设因子矩阵的列是单位长度的，从而需要引入一个权重向量，使CP分解变为◦对于高阶张量，有其展开形式为231;,,RrrrrrλABCabcXRλ(1)(2)()(1)(2)()1;,,,RNNrrrrrλAAAaaaXT()()(1)(1)(1)()diag()nNnnnXAλAAAA张量的秩和秩分解◦张量的秩定义为用秩一张量之和来精确表示所需要的秩一张量的最少个数，记为◦秩分解：可见秩分解是一个特殊的CP分解，对应于矩阵的SVD◦目前还没有方法能够直接求解一个任意给定张量的秩，这被证明是一个NP-hard问题24XXrank()Xrank()(1)(2)()1NrrrraaaXX张量的秩◦不同于矩阵的秩，高阶张量的秩在实数域和复数域上不一定相同。例如一个三阶张量在实数域内进行秩分解得到的因子矩阵为而在复数域内进行分解得到的因子矩阵为25X1210010110XX101101110011011111ABC1111111122iiiiiiABC张量的低秩近似◦相对于矩阵的SVD来说，高阶张量的秩分解唯一性不需要正交性条件保证，只需满足：这里表示矩阵的k-秩：任意k列都线性无关的最大的k26()121nNnkRNAkAA张量的低秩近似◦然而在低秩近似方面，高阶张量的性质比矩阵SVD差Kolda给出了一个例子，一个立方张量的最佳秩-1近似并不包括在其最佳秩-2近似中，这说明张量的秩-k近似无法渐进地得到下面的例子说明，张量的“最佳”秩-k近似甚至不一定存在27112121211121212111111abcabcabcaabbccabcXY张量的低秩近似◦退化：如果一个张量能够被一系列的低秩张量任意逼近◦边缘秩（borderrank）：能够任意逼近一个张量的最少的成分个数28秩2秩3Y(0)X(1)X(2)XX一个秩为2的张量序列收敛到一个秩3张量CP分解的计算◦分解成多少个秩一张量（成分）之和？通常的做法是从1开始尝试，知道碰到一个“好”的结果为止如果有较强的应用背景和先验信息，可以预先指定◦对于给定的成分数目，怎么求解CP分解？目前仍然没有一个完美的解决方案从效果来看，交替最小二乘（AlternatingLeastSquare）是一类比较有效的算法29CP分解的计算◦以一个三阶张量为例，假定成分个数已知，目标为◦作为ALS的一个子问题，固定和，求解得再通过归一化分别求出和30XRˆ1ˆˆmins.t.;,,RrrrrrabcλABCXXXXBCT(1)mindiag()FAXAλCBTTT(1)(1)diag()++AλXCBXCBCCBBAλCP分解的计算◦ALS算法并不能保证收敛到一个极小点，甚至不一定能收敛到稳定点，它只能找到一个目标函数不再下降的点◦算法的初始化可以是随机的，也可以将因子矩阵初始化为对应展开的奇异向量，如将初始化为的前个左奇异向量31A(1)XRCP分解的应用◦计量心理学◦语音分析◦化学计量学◦独立成分分析◦神经科学◦数据挖掘◦高维算子近似◦随即偏微分方程◦…………32Tucker分解33Tucker分解的其他名字◦Three-modefactoranalysis(3MFA/Tucker3),Tucker,1966◦Three-modeprincipalcomponentanalysis(3MPCA),Kroonenberg&DeLeeuw,1980◦N-modeprincipalcomponentsanalysis,Kapteynetal.,1986◦Higher-orderSVD(HOSVD),DeLathauweretal.,2000◦N-modeSVD,VasilescuandTerzopoulos,200234Tucker分解◦Tucker分解是一种高阶的主成分分析，它将一个张量表示成一个核心（core）张量沿每一个mode乘上一个矩阵。对于三阶张量来说，其Tucker分解为◦因子矩阵通常是正交的，可以视为沿相应mode的主成分35123111;,,QPRpqrpqrpqrgABCABCabcXGG,,IPJQKR×××ABCIJK××XTucker分解◦容易看出，CP分解是Tucker分解的一种特殊形式：如果核心张量是对角的，且，则Tucker分解就退化成了CP分解36GPQR三阶张量的Tucker分解X23BCGAG13ACG12ABGCBTucker分解的矩阵形式◦三阶Tucker分解的展开形式为◦Tucker分解可以推广到高阶张量37T(1)(1)T(2)(2)T(3)(3)XAGCBXBGCAXCGBA(1)(2)()(1)(2)()12;,,,NNNAAAAAAXGGT()()(1)(1)(1)()()nNnnnnXAGAAAATucker2和Tucker1◦对于三阶张量固定一个因子矩阵为单位阵，就得到Tucker分解一个重要的特例：Tucker2。例如固定，则◦进一步，固定两个因子矩阵，就得到了Tucker1，例如令第二、三个因子矩阵为单位阵，则Tucker分解就退化成了普通的PCA3812;,,ABABIXGGCI1(1)(1);,,AAIIXAGXGG张量的n-秩近似◦一个N阶张量的n-秩定义为◦若设，则叫做一个秩-张量◦如果，则很容易得到的一个精确秩-Tucker分解；然而如果至少有一个使得，则通过Tucker分解得到的就是的一个秩-近似39X()rank()rank()nnXXrank(),1,,nnRnNX12,,,NRRRXrank(),1,,nnRnNX12,,,NRRRXnrank()nnRX12,,,NRRRX张量的n-秩近似40XGBCA1R1rank()X截断的Tucker分解：秩-近似123,,RRR张量的n-秩近似◦对于固定的n-秩，Tucker分解的唯一性不能保证，所以需要添加其他的约束◦通常要求核心张量是“简单”的，如各个mode的主成分之间尽量不发生相互作用（稀疏性），或者其他的“简单性”约束41Tucker分解的计算◦HOSVD：利用SVD对每个mode做一次Tucker1分解（截断或者不截断）◦HOSVD不能保证得到一个较好的近似，但HOSVD的结果可以作为一个其他迭代算法（如HOOI）的很好的初始解42Tucker分解的计算◦为了导出HOOI迭代算法，先考虑目标函数◦从而应该满足43(1)()()(1);,,vec()vec()NNA