人生艰难,复习一下基本的东西,然后说不定毕不了业的时候就只能靠这个了。非负矩阵分解也是个靠谱的方法,尤其是在PS越来越实用的时代。

NMF,其实说起来很简单,对于\(X = [X_{.,1},...,X_{.,N}] \in R_{+}^{M \times N}\),代表非负数据矩阵,其中每一列代表一个数据点,每一行代表一种特征,NMF的目标是为了将\(X\)分解为元素均为非负的\(U = [U_{i,k}] \in R_{+}^{M \times K}\)\(V = [V_{j,k}] \in R_{+}^{N \times K}\),其中\(K\)为降低以后的维度。即为

\[X \approx UV^T\]

而分解后的矩阵以后,\(U\)看做新空间的基矩阵和\(V\)是新空间的坐标。然后通过,

\[X_j \approx U(V_{j,.})^T=\sum_k^K U_{.,k}V_{j,k}\]

即目标函数

\[min_{U,V}||X - UV^T||_F^2, s.t. U \geq 0, V \geq 0\]

当然这里的范数可以换,而且使用不同的范数的效果也不一样。NMF作为一种像PGM一样的建模手段可以用到很多地方,比如把它当做一个降维的过程,然后对\(V\)的新坐标进行聚类,或者在迁移复习中,利用学习出来的\(U\)当做新空间的基。

NMF由于分解的结果都是正的,所以很多时候可以解释成概率,比如在对于文本数据的时候,PLSALDA都可以看成把词-文章矩阵分解成词-主题主题-文章矩阵(当然LDA可以通过超参来调解分解矩阵的分布)。只要保证NMF中的\(V\)是归一化的,就能认为\(V\)是在\(U\)的基的聚类中心上的各个类的分类结果。

multi-view

multi-view也是很常见的问题,数据来源于同一实体的不同view的描述,比如同一个新闻,不同报纸的报道,我们有理由认为,同一个新闻的主题应该是一致的,但是不同报纸的报道用词会不相同,采用多个view学习可以更好地学习到新闻所处的空间。

先回顾一下概率图的multi-view的样子。

同一个实体会在不同的view下有不同的坐标,因为他们根本不在一个基坐标,所以直接观测的坐标信息,是不能使用的,但是我们可以假设\(X = UV^T\),这样我们就可以就把不同的基坐标和实际的坐标分开,然后假设\(V\)应该是共享的,自然而然的就得到了目标函数。

\[\sum_{v = 1}^{n_v}||X^{(v)} - U^{(v)}(V^{(v)})^T||_F^2 + \sum_{v = 1}^{n_v}\lambda_v ||V^{(v)} - V^*||\] \[s.t.\forall 1 \leq k \leq K, ||U_{.,k}^{(k)}||_1 = 1\ \ and \ \ U^{(v)},V^{(v)}, V^* \geq 0\]

其中\(\lambda\)可以用来调节不同\(view\)的权重,不过这个麻烦的地方在对于\(U\)的每一列都有归一化的约束。为了简化,不妨转化一下,加入

\[Q^{(v)} = Diag(\sum_{i=1}^M U_{i,1}^{(v)},\sum_{i=1}^M U_{i,2}^{(v)}, ... ,\sum_{i=1}^M U_{i,K}^{(v)})\]

其中\(Diag(.)\)代表对角阵,其对角元为括号中内容,剩下元素为0。然后目标函数就可以转化为

\[\sum_{v = 1}^{n_v}||X^{(v)} - U^{(v)}(V^{(v)})^T||_F^2+ \sum_{v = 1}^{n_v}\lambda_v ||V^{(v)}Q^{(v)} - V^*||\] \[s.t.\forall 1 \leq v \leq n_v, \ \ and \ \ U^{(v)},V^{(v)}, V^* \geq 0\]

其实这里相当于把用来归一化的系数的倒数传递给\(V^{(v)}\),然后再通过乘\(Q^{(v)}\)把这部分给消掉。这样式子就简化很多。

为了求解这个式子,我们一次在固定其它元素的情况下,求解单一矩阵的局部极值,然后不断迭代。

固定\(V^*\)以及\(V^{(v)}\)计算\(U^{(v)}\)

原式为 \[ \begin{split} O & =\sum_{v = 1}^{n_v}||X^{(v)} - U^{(v)}(V^{(v)})^T||_F \\ &+ \sum_{v = 1}^{n_v}\lambda_v ||V^{(v)}Q^{(v)} - V^*|| \\ &= Tr((X - UV^T)(X - UV^T)^T) + \\ & = \lambda_v Tr((VQ-V^*)(VQ-V^*)^T) \end{split}\]

然后利用拉格朗日乘子法加上非负约束,只考虑与\(U\)有关的项。

\[ L_1 = Tr(UV^TVU^T-2XVU^T) + \lambda_v R + Tr(\Psi U) \]

这里的\(\Psi\)是拉格朗日乘子矩阵,展开会发现,其迹正好是所有元素的乘数和。

其中\(R = Tr(VQQ^TV^T-2VQ(V^*)^T)\)

先展开看\(R\)这一项

\[\begin{split} R& = \sum_{j=1}^N \sum_{k=1}^K(V_{j,k}\sum_{i=1}^MU_{i,k}\sum_{i=1}^M U_{i,k}V_{j,k}) \\ &-2\sum_{j=1}^N\sum_{k=1}^K(V_{j,k}\sum_{i=1}^MU_{i,k}V^*_{j,k}) \end{split}\]

然后对\(U\)求偏导

\[ P_{i,k} = \frac{\delta R}{\delta U_{i,k}}=2(\sum_{l=1}^M U_{l,k}\sum_{j=1}^N V_{j,k}^2 - \sum_{j=1}^N V_{j,k}V_{j,k}^*) \]

有了这个就可以对整个目标函数求导,索性带迹的求导并不复杂

\[\begin{split} \frac{\delta L_1}{\delta U} = -2XV + 2UV^TV + \lambda_v P + \psi \end{split}\]

然后根据这个就能把迭代式写出来,这里有个技巧,简单来说就是负的除以正的,具体的证明要构造一个辅助函数,详细的过程可以看这篇论文

最后得到

\[ U_{i,k} \leftarrow U_{i,k} \frac{(XV)_{i,k} + \lambda_v \sum_{j = 1}^N V_{j,k}V_{j,k}^*}{(UV^TV)_{i,k}+\lambda_v \sum_{l=1}^MU_{l,k}\sum_{j=1}^N V_{j,k}^2} \]

显然这能保证U的非负性。

固定\(V^*\)以及\(U^{(v)}\),计算\(V^{(v)}\)

计算\(V\)的过程类似,先写出

\[\begin{split} L_2 & = Tr(UV^TVU^T-2XVU^T) \\ & + \lambda_v Tr(VV^T - 2V(V^*)^T) + Tr(\Phi V) \end{split}\]

然后继续查查矩阵求导手册,就可以写出来,

\[ \frac{\delta L_2}{\delta V} = 2VU^TU - 2X^TU + 2\lambda_v(V -V^*) + \Phi \]

然后继续负的除以正的

\[ V_{j,k} \leftarrow V_{j,k}\frac{(X^T U)_{j,k} + \lambda_v V^*_{j,k}}{(VU^TU)_{j,k} + \lambda_v V_{j,k}} \]

固定U和V,优化\(V^*\)

\(V^*\)有关的就一项,

\[\begin{split} \frac{\delta O}{\delta V^*} & = \frac{\delta \sum_{v=1}^{n_v} \lambda_v ||V^{(v)}Q^{(v)} - V^*||_F^2}{\delta V^*} \\ & = \sum_{v = 1}^{n_v} \lambda_v(-2V^(v) + 2 V^*) \end{split}\]

这个就好求了

\[ V^* = \frac{\sum_{v = 1}^{n_v} \lambda_v V^{(v)}Q^{(v)}}{\sum_{v = 1}^{n_v} \lambda_v} \]

至此,三个迭代式就都求出来了。

Manifold

流形指在局部同坯与欧式空间的空间。比如三维空间的球面,宇宙空间中地球表面,我们在计算两个很近的城市的距离的时候,一般是不会考虑地球的曲面的性质,误差也不会很大。

话说流形这个词的,来自『天地有正气,杂然赋流形』,给人一种形变、流动的感觉。

由于流形的存在,我们在计算距离的时候,不能直接计算欧氏距离,而应该计算低维嵌入流形的测地线,由此产生了Isomap这种算法。其实说起来很简单,为了能准确的测量距离,利用流行空间与欧式空间局部同坯的性质,先构建一个近邻图,假设近邻之间有路径,非近邻没有路径,然后用求最短路径的算法,就可以计算任意两点真正的距离了。

那在矩阵分解中怎么应用这个性质呢?首先用graph Laplacian近似流形上的\(L = D - W\),其中

\[ W_{ij} = \left\{\begin{matrix} 1, & if x_i \in N_p(x_j)\ \ or\ \ x_j =in N_p(x_i)\\ 0, & otherwise \end{matrix}\right. \]

然后,D是一个对角阵,其中每一个元素都是对应的W的行之和,即\(D_{ii} = \sum_j W_{ij}\)

我们希望的应该是如果两个点在流形空间中接近,那么他们在分解以后的空间也接近。即

\[\begin{split} R_k &= \frac{1}{2} \sum_{i,j=1}^N (f_k(x_i) - f_k(x_j))^2)W_{ij} \\ &=\sum_{i=1}^N f_k(x_i)D_{ii} - \sum_{i,j=1}^N f_k(x_i)f_k(x_j)W_{ij} \\ & = \sum_{i=1}^N v_{ik}^2 D_{ii} - \sum_{i,j=1}^N v_{ik}v_{jk}W_{ij} \\ & = v_k^T D v_k - v_k^T Wv_k \\ & = v_k^TLv_k \end{split}\]

使用\(v_{ik}\)近似\(f_k(x_i)\),然后如果两个在流型空间接近的话,那么他们的近邻关系也应该近似。把这一项当成正则项加进入。

\[\begin{split} O &= ||X - UV^T||_F^2 + \lambda \sum_{i=1}^k R_k \\ & = ||X - UV^T||_F^2 + \lambda Tr(V^TLV) \end{split}\]

求解方法和之前的没什么太大区别。

那么流形在概率图上怎么对应呢。看这篇论文




X