张量分解——张量分解的基础知识

简单的说张量就是多维数组。我们知道一维数组叫向量,二维的叫矩阵,三维及三维以上的就是张量了。
如图:

基本概念

矩阵补全(Matrix Completion)目的是为了估计矩阵中缺失的部分(不可观察的部分),可以看做是用矩阵X近似矩阵M,然后用X中的元素作为矩阵M中不可观察部分的元素估计。
矩阵分解(Matrix Factorization)是指用$A \times B$来近似矩阵M,那么$A \times B$的元素就可以用来估计M中对应不可见位置的元素,而$A \times B$可以看成是矩阵M的分解
这是因为协同过滤本质上是考虑大量用户的偏好信息(协同),来对某一用户的偏好做出预测(过滤),那么当我们把这样的偏好用评分矩阵表达后,正等价于用M其他行已知的值(每一行包含一个用户对所有商品的已知评分),来估计并填充某一行的缺失值。若要对所有用户进行预测,便是填充整个矩阵,这是所谓的”协同过滤的本质是矩阵填充“。
矩阵分解是一种主流方法。因为协同过滤有一个隐含的重要假设,“如果用户A和用户B同时偏好商品X,那么用户A和用户B对其他商品的偏好性有更大的几率相似”。这个假设反应在矩阵M上即使矩阵的低秩。
极端情况之一是若所有用户对不同商品的偏好保持一致,那么填充完的M每行应两两相等,即秩为1。

矩阵分解的几种形式

看我这篇博客

张量相关基础知识

论文
总结的比较好的文章

张量范数

张量范数:即所有元素的平法和的平方根

张量内积

两个相同大小张量的内积就是他们对应元素乘积的和

张量外积

给定向量$\vec a=\left( 1,2 \right) ^{T}$ ,向量$\vec b=\left( 3,4 \right) ^{T}$ ,则$\vec a\circ \vec b=\vec a\vec b^{T}=\left[ \begin{array}{cc} 3 & 4 \\ 6 & 8 \\ \end{array} \right]$,运算符号“$\circ $”表示外积。另给定向量$\vec c=\left( 5,6,7 \right) ^{T}$ ,若${\mathcal{X}}=\vec a\circ \vec b\circ \vec c$,则

其中,${\mathcal{X}}$是一个三维数组(有三个索引),对于任意索引$\left( i,j,k \right)$ 上的值为$x_{ijk}=a_i\cdot b_j\cdot c_k,i=1,2,j=1,2,k=1,2,3,$在这里,向量$\vec a, \vec b, \vec c$的外积即可得到一个第三阶张量(third-order tensor),如图

向量$\vec a, \vec b, \vec c$的外积

在大量的文献中,Kronecker积的符号“$\otimes $”有时也用来表示向量的外积。

Rank-one张量

Rank-one Tensor是一种特殊的张量,如果一个N阶的张量能以N个张量的外积来表示,这就是个Rank-one张量。

张量展开

在实际应用中,由于高阶张量比向量、矩阵都抽象,最简单地,向量和矩阵可以很轻松地书写出来并进行运算,而高阶张量则不那么直观,如何将高阶张量转换成二维空间的矩阵呢?这就是张量的展开,有时,也将张量的展开称为张量的矩阵化(Matricization: transforming a tensor into a matrix)。
给定大小为$4\times 3\times 2$的张量${\mathcal{ X}}$,其中,矩阵${\mathcal{ X}}\left( :,:,1 \right)= \left[ \begin{array}{ccc} x_{111} & x_{121} & x_{131} \\ x_{211} & x_{221} & x_{231} \\ x_{311} & x_{321} & x_{331} \\ x_{411} & x_{421} & x_{431} \\ \end{array} \right]$,矩阵${\mathcal{ X}}\left( :,:,2 \right)= \left[ \begin{array}{ccc} x_{112} & x_{122} & x_{132} \\ x_{212} & x_{222} & x_{232} \\ x_{312} & x_{322} & x_{332} \\ x_{412} & x_{422} & x_{432} \\ \end{array} \right]$,按照模态1(mode-1, 即对应着张量的第一阶)展开可以得到,

即矩阵${\mathcal{ X}}_{\left( 1 \right)} =\left[{\mathcal{ X}}\left( :,:,1 \right) ,{\mathcal{ X}}\left( :,:,2 \right) \right]$ ,其大小为$4\times 6$.

按照模态2(mode-2, 即对应着张量的第二阶)展开可以得到,

即矩阵${\mathcal{ X}}_{\left( 2 \right) }=\left[{\mathcal{ X}}\left( :,:,1 \right)^T,{\mathcal{ X}}\left( :,:,2 \right)^T \right]$ ,其大小为$3\times 8$.

按照模态3(mode-3, 即对应着张量的第三阶)展开可以得到,

即矩阵${\mathcal {X}}_{\left( 3 \right) }=\left[{\mathcal{ X}}\left( :,1,: \right)^T,{\mathcal{ X}}\left( :,2,: \right)^T,{\mathcal{ X}}\left( :,3,: \right)^T \right]$ ,其大小为$2\times 12$.

类似地,如果给定一个大小为$2\times 2\times 2\times 2$的第四阶张量${\mathcal{ X}}$,则在各个模态下的展开分别为

举一个例子,若${\mathcal{ X}}\left( :,:,1,1 \right) =\left[ \begin{array}{cc} 1 & 2 \\ 3 & 4 \\ \end{array} \right]$,${\mathcal{ X}}\left( :,:,2,1 \right) =\left[ \begin{array}{cc} 5 & 6 \\ 7 & 8 \\ \end{array} \right]$,${\mathcal{ X}}\left( :,:,1,2 \right) =\left[ \begin{array}{cc} 9 & 10 \\ 11 & 12 \\ \end{array} \right]$,${\mathcal{ X}}\left( :,:,2,2 \right) =\left[ \begin{array}{cc} 13 & 14 \\ 15 & 16 \\ \end{array} \right],$则

可惜的是,张量的展开虽然有一定的规则,但并没有很强的物理意义,对高阶张量进行展开会方便使用相应的矩阵化运算。除此之外,高阶张量可以展开自然也就可以还原(即将展开后的矩阵还原成高阶张量,这个过程称为folding)。

DiagonalTensor

张量乘法

张量与矩阵相乘(又称为模态积)相比矩阵与矩阵之间的相乘更为抽象,如何理解呢?

假设一个大小为$n_1 \times n_2 \times … \times n_d$的张量${\mathcal{X}}$,同时给定一个大小为$m\times n_k$的矩阵A,则张量${\mathcal{X}}$与矩阵A的k模态积(k-mode product)记为${\mathcal{X}}\times_k A$,其大小为$n_1 \times n_2 \times … \times n_{k-1} \times m \times n_{k+1} \times … \times n_d$,对于每个元素而言,有

其中,$1\leq i_1\leq n_1,…,1\leq i_d\leq n_d,1\leq j\leq m$,我们可以看出,模态积是张量、矩阵和模态(mode)的一种“组合”运算。另外,${\mathcal{Y}}={\mathcal{X}}\times_kA与{\mathcal{Y}}_{\left( k \right) }=A{\mathcal{X}}_{\left( k \right) }$是等价的,这在接下来的例子里会展现相应的计算过程。
上述给出张量与矩阵相乘的定义,为了方便理解,下面来看一个简单的示例,若给定张量${\mathcal{ X}}为{\mathcal{ X}}\left( :,:,1 \right) =\left[ \begin{array}{cc} 1 & 2 \\ 3 & 4 \\ \end{array} \right],{\mathcal{ X}}\left( :,:,2 \right) =\left[ \begin{array}{cc} 5 & 6 \\ 7 & 8 \\ \end{array} \right]$,其大小为$2\times 2\times 2$,另外给定矩阵$A=\left[ \begin{array}{cc} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ \end{array} \right]$,试想一下:张量${\mathcal{ X}}$和矩阵A相乘会得到什么呢?

假设${\mathcal{ Y}}={\mathcal{ X}}\times _1A$,则对于张量${\mathcal{ Y}}$在任意索引$\left( i,j,k \right) $上的值为$y_{ijk}=\sum_{m=1}^{2}{\left( x_{mjk}\cdot a_{im} \right) }$ ,这一运算规则也不难发现,张量${\mathcal{ Y}}$的大小为$3\times 2\times 2$,以$\left( 1,1,1 \right)$ 位置为例,$y_{111}=\sum_{m=1}^{2}{\left( x_{m11}\cdot a_{1m} \right) } =x_{111}\cdot a_{11}+x_{211}\cdot a_{12}=7$

再以$\left( 1,1,2 \right)$ 位置为例,$y_{112}=\sum_{m=1}^{2}{\left( x_{m12}\cdot a_{1m} \right) } =x_{112}\cdot a_{11}+x_{212}\cdot a_{12}=19$,这样,可以得到张量${\mathcal{ Y}}$为


$
{\mathcal{ Y}}\left( :,:,1 \right) =\left[ \begin{array}{cc} 1\times 1+3\times 2 & 2\times 1+4\times 2 \\ 1\times 3+3\times 4 & 2\times 3+4\times 4 \\ 1\times 5+3\times 6 & 2\times 5+4\times 6 \\ \end{array} \right]=\left[ \begin{array}{cc} 7 & 10 \\ 15 & 22 \\ 23 & 34 \\ \end{array} \right]$ ,
${\mathcal{ Y}}\left( :,:,2 \right) =\left[ \begin{array}{cc} 5\times 1+7\times 2 & 6\times 1+8\times 2 \\ 5\times 3+7\times 4 & 6\times 3+8\times 4 \\ 5\times 5+7\times 6 & 6\times 5+8\times 6 \\ \end{array} \right]=\left[ \begin{array}{cc} 19 & 22 \\ 43 & 50 \\ 67 & 78 \\ \end{array} \right]$

其中,由于模态积的运算规则不再像Kronecer积和Khatri-Rao积那么“亲民”,所以有兴趣的读者可以自己动手计算一遍。

实际上,${\mathcal{ Y}}={\mathcal{ X}}\times _2A$(会得到大小为$2\times 3\times 2$的张量)或${\mathcal{ Y}}={\mathcal{ X}}\times _3A$(会得到大小为$2\times 2\times 3$的张量)也可以用上述同样的运算规则进行计算,这里将不再赘述,有兴趣的读者可以自行推导。需要注意的是,${\mathcal{ Y}}={\mathcal{ X}}\times _1A$有一个恒等的计算公式,即${\mathcal{ Y}}_{\left( 1 \right) }=A{\mathcal{ X}}_{\left( 1 \right) }$,由于${\mathcal{ X}}_{\left( 1 \right) }=\left[{\mathcal{ X}}\left( :,:,1 \right) ,{\mathcal{ X}}\left( :,:,2 \right) \right] =\left[ \begin{array}{cccc} 1 & 2 & 5 & 6 \\ 3 & 4 & 7 & 8 \\ \end{array} \right]$,则

满足$ {\mathcal{ Y}}_{\left( 1 \right) }=\left[{\mathcal{ Y}}\left( :,:,1 \right),{\mathcal{ Y}}\left( :,:,2 \right) \right]$,即采用张量矩阵化的形式进行运算可以使问题变得更加简单,从这里也可以看出高阶张量进行矩阵化的优点。

KroneckerProduct

Khatri-RaoProduct

HadamardPRoduct

按元素对应相乘,但是两个张量的维度必须相同。

推荐系统中常用的矩阵分解

在我们常见的推荐系统(如商品推荐系统、电影推荐系统等)中,给定一个大小为$ m\times n$的评分矩阵R,元素$r_{ij}$表示用户(user)i对项(item,如电影、商品等)j的评分值,如1~5分不等。
当矩阵R的秩为$k=rank\left( R \right) \ll \min {\left(m,n \right)}$,并且能够写成如下形式

$R=UV^{T}$
其中,U是大小为$m\times k$的矩阵(用户因子矩阵,user-factor matrix),V是大小为$n\times k$的矩阵(项因子矩阵,item-factor matrix)。这一过程就是矩阵分解。
当$k< rank\left( R \right)$ 时,我们可以将矩阵分解的过程看作是一个低秩逼近问题(low-rank approximation problem),原来的分解过程则变成

$R\approx UV^{T}$
和前面相同,U是大小为$m\times k$的矩阵(用户因子矩阵,user-factor matrix),V是大小为$n\times k$的矩阵(项因子矩阵,item-factor matrix)。在这个低秩逼近问题中,可以很明显得看出整体误差为残差矩阵$R-UV^{T}$中所有元素的平方和,即$|| R-UV^{T} || ^{2}$(这种写法含义是矩阵F-范数的平方,等价于矩阵中所有元素的平方和)。
如果简单地使总的误差最小,那么,可以将矩阵分解的逼近问题转化为一个无约束的优化问题,即

$\min J=\frac{1}{2} || R-UV^{T} || ^{2}$
在实际应用中,这里的评分矩阵R往往是一个稀疏矩阵,即很多位置上的元素是空缺的,或者说根本不存在。试想一下,如果有10000个用户,同时存在10000部电影,如果我们需要构造一个评分矩阵,难道每个用户都要把每部电影都看一遍才知道用户的偏好吗?其实不是,我们只需要知道每个用户仅有的一些评分就可以利用矩阵分解来估计用户的偏好,并最终推荐用户可能喜欢的电影。
在这里,我们将矩阵R中存在评分的位置记为$\left( i,j \right)$ ,所有观测到的位置索引记作集合S,其中,用户的索引为$i\in \left\{ 1,2,…,m \right\} $,项的索引为$j\in \left\{ 1,2,…,n \right\} $,需要注意的是,推荐系统中的矩阵分解对原矩阵R有一定的要求,即矩阵的每行和每列至少有一个元素。此时,任意位置$\left( i,j \right)$ 所对应的评分估计值为$\hat{r} _{ij}=\left(UV^{T}\right)_{ij}=\sum_{q=1}^{k}{u_{iq}\cdot v_{jq}}$ 。
则原来的优化问题等价于

对目标函数J中的u_{iq}和v_{jq}求偏导数,得

这里,可以将两个偏导数分别简写为$\frac{\partial J}{\partial u_{iq}} =-\sum_{j:\left( i,j \right)\in S } {e_{ij}v_{jq}}和\frac{\partial J}{\partial v_{jq}} =-\sum_{i:(i,j)\in S}{e_{ij}u_{iq}}$,其中,$i\in \left\{ 1,2,…,m \right\} ,j\in \left\{ 1,2,…,n \right\} ,q\in \left\{ 1,2,…,k \right\} 。$

根据梯度下降(gradient descent)方法,$u_{iq}$和$v_{jq}$在每次迭代过程中的更新公式为

这里的$\alpha>0$表示梯度下降的步长,又称为学习率(learning rate),另外,更新公式中的求和项下标$j:\left( i,j \right)\in S$ 和$i:\left( i,j \right)\in S$ 分别表示向量$R\left( i,: \right)$ 和$R\left( :,j \right)$ 上所有非零元素的位置索引构成的集合。

隐性因子模型(LFM)

上面已经简单地介绍了矩阵分解的原理,对推荐系统有了解的读者可能对上面这一过程并不陌生,上面的矩阵分解在推荐系统中常常被称为隐性因子模型(latent factor model, LFM),其实张量分解与上述过程非常相似,为了便于读者初步地理解张量分解,这里将会沿用矩阵分解类似的推导过程。
定义一个关于用户(user)i在环境(context,如时间,注意:这里将context翻译成“环境”不一定准确,在隐性语义分析中常常理解为“语境”或“上下文”)c下对项(item)j的评分为$r_{ijc}$,评分张量的大小为$m\times n\times d$,所有观测到位置索引仍然记作集合S,其中,用户的索引为$i\in \left\{ 1,2,…,m \right\} $,项的索引为$j\in \left\{ 1,2,…,n \right\} $,环境的索引为$c\in \left\{1,2,…,d \right\}$ 。
Charu C. Aggarwal在其著作《Recommender systems》中给出了一个特殊的张量分解结构,即大小为$m\times n\times d$的评分张量${\mathcal{R}}$分解后会得到三个矩阵,这三个矩阵分别是:大小为$m\times k$的用户因子矩阵U(user-factor matrix)、大小为$n\times k$的项因子矩阵V(item-factor matrix)和大小为$d\times k$的环境因子矩阵W(context-factor matrix),这种分解结构是隐性因子模型的一种高阶泛化。
此时,第3阶张量${\mathcal{R}}$上任意位置$\left( i,j,c \right)$ 所对应的评分估计值为

即$\hat r_{ijc}=\sum_{q=1}^{k}\left(u_{iq}v_{jq}+u_{iq}w_{cq}+v_{jq}w_{cq}\right)$
矩阵分解中的低秩逼近问题相似,评分张量分解的逼近问题为

对目标函数J中的u_{iq}、v_{jq}和w_{cq}求偏导数,得

根据梯度下降方法,u_{iq}、v_{jq}和w_{cq}在每次迭代过程中的更新公式为

需要注意的是,更新公式中的求和项下标$j,c:(i,j,c)\in S、i,c:(i,j,c)\in S$和$i,j:(i,j,c)\in S$分别表示矩阵${\mathcal{R}}\left( i,:,: \right) 、{\mathcal{R}}\left( :,j,: \right) 和{\mathcal{R}}\left( :,:,c \right) $上所有非零元素的位置索引构成的集合

高阶奇异值分解

矩阵的奇异值分解(singular value decomposition ,SVD)是线性代数中很重要的内容,通常给定一个大小为$M \times n$的矩阵A,奇异值分解形式为:
$ A=U\Sigma V^T $
其中矩阵$ U,\Sigma,V$的大分别为$m\times m,m\times n,n\times n$矩阵U是由左奇异向量(left singular vector)构成的,矩阵V是由右奇异向量(right singular vector)构成的,矩阵\Sigma对角线上的元素称为奇异值(singular value),这一分解过程很简单,但实际上,关于奇异值分解的应用是非常广泛的。
就高阶奇异值分解而言,著名学者Tucker于1966年给出了计算Tucker分解的三种方法,第一种方法就是我们这里要提到的高阶奇异值分解,其整个分解过程也是由矩阵的奇异值分解泛化得到的。
对于给定一个大小为$n_1 \times n_2 \times … \times n_d$的张量${\mathcal{X}}$,将k模态下的展开记为${\mathcal{X}}_{\left( k \right) }$,则k模态的矩阵进行奇异值分解,可以写成

这里的$U_k,\Sigma_k,V_k$是通过矩阵${\mathcal{X}}_{\left( k \right) }$的奇异值分解得到的,如果取出各个模态下得到的矩阵$U_1,U_2,…,U_d$,则张量${\mathcal{X}}$的高阶奇异值分解可以写成如下形式:

其中,${\mathcal{G}}$是核心张量,其计算公式为${\mathcal{G}}={\mathcal{X}} \times_1U_1^T \times_2U_2^T… \times_dU_d^T$,在这里,这条计算公式等价于${\mathcal{G}}_{\left( k \right) }=U_k^T{\mathcal{X}}_{\left( k \right) }\left( U_d \otimes … \otimes U_{k+1} \otimes U_{k-1} \otimes… \otimes U_1 \right)$$ ({\mathcal{X}}_{\left( k \right) }=U_k{\mathcal{G}}_{\left( k \right) }\left( U_d \otimes … \otimes U_{k+1} \otimes U_{k-1} \otimes… \otimes U_1 \right)^T也是恒成立的)$。

细心的读者可能会发现,根据奇异值分解的定义,这里的核心张量${\mathcal{G}}$的大小为$n_1\times n_2\times\cdots\times n_d$,而矩阵$U_1,U_2,…,U_d$的大小则分别为$n_1\times n_1,n_2\times n_2,…,n_d \times n_d$.
我们也知道,对于矩阵的奇异值分解是可以进行降维(dimension reduction)处理的,即取前r个最大奇异值以及相应的左奇异向量和右奇异向量,我们可以得到矩阵$U,\Sigma,V$的大小分别为$m\times r,r\times r,n\times r$,这也被称为截断的奇异值分解(truncated SVD),对于高阶奇异值分解是否存在类似的“降维”过程(即truncated HOSVD, 截断的高阶奇异值分解)呢?
给定核心张量${\mathcal{G}}$的大小为$r_1 \times r_2 \times … \times r_d$,并且$r_1\leq n_1,r_2\leq n_2,…,r_d\leq n_d$,则对于k模态的矩阵${\mathcal{X}}_{\left( k \right) }$进行奇异值分解取前$r_k$个最大奇异值对应的左奇异向量,则矩阵$U_k$的大小为$n_k\times r_k$,对矩阵${\mathcal{X}}_{\left( k \right) },k=1,2,…,d$进行奇异值分解,知道了$U_1,U_2,…,U_d$后,再计算核心张量${\mathcal{G}}={\mathcal{X}} \times_1U_1^T \times_2U_2^T… \times_dU_d^T$,我们就可以最终得到想要的Tucker分解了。


-------------本文结束感谢您的阅读-------------


本文标题:张量分解——张量分解的基础知识

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年11月06日 - 21:11

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/7515431d.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!