先见树木，后见森林

流形上的非负矩阵分解

1.非负矩阵分解
流形学习和各种算法的结合很多，这里我先写写自己比较熟悉的非负矩阵分解[1]和流形学习或者图正则化的结合，我把标题定为“先见树木，后见森林”，是对一句名言“只见树木，不见森林”的修改，只见树木，不见森林说的是只关注局部，而忽略了整体。而非负矩阵分解背后的哲学则是"Is perception of the whole based on perception of its parts?"。把疑问句修改为陈述句，即对整体的感知是基于对部分的感知的，部分的相加等于整体。那么这是怎么做到的呢？

首先看图1，我们可以将一个人的脸分解为若干种鼻子、眼睛、脸型、眉毛和嘴巴等的加权之和，而非负矩阵分解的目标正是要实现这一点。首先看普通的矩阵V = WH，其还可以写成：

一般将W的行作为基（被加的部分），H被看为原数据的编码。假设V的第一行v1是一张人脸，那么v1可以被写成:

即一张人脸变成了W中的基的加权和，w1可以代表鼻子，w2可以代表眼睛。那么为什么需要非负矩阵分解呢？在非负矩阵分解中W,H的所有元素被强制大于等于0，这就强制了整体是部分的相加，而不存在相减的关系，这与我们更倾向于将一个整体事物分解为若干个局部事物的相加而非相减是相符合的。 图1.人脸的非负矩阵分解

然而这个问题该怎么求解呢？最为经典的Lee和Seung于2001年提出的乘性更新原则[2]，我们来看针对||V-WH||^2欧式距离损失函数的更新原则：

显然，只要当H和W的所有元素初始化时为非负，根据乘性原则更新最后的得到的W和H也必然非负（正数乘以正数永远为正）。乘性更新原则实际上是一种特殊步长设定的梯度提升方法，首先来看||V-WH||^2的梯度：

只要每步都对让步长\delta等于某一个数，梯度提升就等价于乘性更新原则了：

这里再提一下乘性原则的收敛性的问题，Lee和Seung是通过构建损失函数F(H) = ||V - WH||^2的附加函数G(H, H')来完成证明的，如图2所示，附加函数需要满足以下的性质：

图2，附加函数示意图

附加函数有一个优良的性质，每一步我们最小化G(h,h^{t+1})都会有

那么持续交替优化G(h^{t+1},h^t)会有如下结论：

原函数会不断的减小。

而乘性更新原则正是最小化||V - WH||²的一个附加函数的一个解,所以乘性原则交替更新最终会最小化||V - WH||²。

2.流形上的非负矩阵分解
那么非负矩阵分解怎么和流形学习相结合，这一块主要参照论文[3,4]。我们来看||X - UV^T||²，已知X中的每行的数据采集至某个流形之上，U中的每行为基础数据，而V则是流形数据X在U中基的编码。如果我们希望X的编码V同样保持X所在流形上的性质，那么我们可以在优化目标函数时加上一个图拉普拉斯正则项。（x1和x5在森林X中是相同的树，我们希望对于x1和x5的编码v1和v5之间有着较强的相关性。）

这个公式也可理解为X通过U的伪逆映射到V后，仍然要保持X流形上的特性。流形上的非负矩阵分解的乘性更新原则如下：

W就是已知的X中元素在流形上的相似矩阵。

而如图3所示，实验表明流形上的非负矩阵分解比普通的非负矩阵分解学习到的基更为稀疏。如果基更加稀疏，那么每个基的语义信息就更加清晰，这里可以这样来理解，我们将一张人脸分为鼻子、眼睛、口等部分，我们希望每组基都有清晰的语义特征，代表鼻子的就仅仅是鼻子，在眼睛和口等位置上的数为0。

图3 (a) 普通非负矩阵分解学习到的基。 (b) 流形上非矩阵分解学习到的基。明显流行上的非负矩阵分解所得到的基更加稀疏

总结来看，流形学习或者图正则项和其它机器学习方法相结合是可以提升这些方法的性能的，其原因是我们往往对数据之间的关系有着一定的先验知识，而这种先验知识是可以用流形\图结构来进行表征，然后以正则项的方法加入到模型优化函数之中。

参考文献
[1] Lee, Daniel D., and H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." Nature 401, no. 6755 (1999): 788.
[2] Lee, Daniel D., and H. Sebastian Seung. "Algorithms for non-negative matrix factorization." In Advances in neural information processing systems, pp. 556-562. 2001.
[3] Cai, Deng, Xiaofei He, Xiaoyun Wu, and Jiawei Han. "Non-negative matrix factorization on manifold." In 2008 Eighth IEEE International Conference on Data Mining, pp. 63-72. IEEE, 2008.
[4] Cai, Deng, Xiaofei He, Jiawei Han, and Thomas S. Huang. "Graph regularized nonnegative matrix factorization for data representation." IEEE transactions on pattern analysis and machine intelligence 33, no. 8 (2011): 1548-1560.