非负矩阵分解(NMF)简介

什么是非负矩阵分解？

非负矩阵分解，顾名思义就是，将非负的大矩阵分解成两个非负的小矩阵。

(1)

回顾矩阵分解本身，在空间分布的一堆数据有它们分布的某些规律，那么找一组更能直观反映这种规律的基，再把原来的数据投影到这组基上表示，这样就能便于后续的应用，比如分类等。

公式(1)中的V是一个n*m维的矩阵，其中每一列就是空间中的一个向量，共m个向量;W是一个n*k维的矩阵，即k个基；H是k*m的矩阵，每一列为V投影到W上得到的向量。

那么非负和其它的有什么不同呢？下面我就盗一张图来直观地展示几种矩阵分解方法的效果差异。（出自Lee and Seung (1999)）

其中original原图即为V中的一列；等式左边第一块是W，其中的每一小块是W的一列；等式左边第二块是H的一列；等式右边的图像是左边相乘还原得到的与original相对应的一个向量（只不过显示成二维图像）。

图中就对比了三种方法的区别。

VQ的约束是要求H的每一列只有一个元素为1，其它为0，因此相当于将m个数据归纳成了k个代表，原数据映射过去就是取k个基当中与原向量距离最小的来重新表示。所以VQ的基都是一张张完整正常的脸，它们都是最具代表性的脸。

PCA大家用得比较多，就是求一组标准正交基，第一个基的方向取原数据方差最大的方向，然后第二个基在与第一个基正交的所有方向里再取方差最大的，这样在跟前面的基都正交的方向上一直取到k个基。所以PCA的基没有直观的物理意义，而且W和H里面的元素都是可正可负的，这就意味着还原时是用W的基加加减减得到的。

NMF因为约束了非负，所以只准把基相加，不能相减，这就意味着基与基是通过拼接组合来还原原象的。所以我们可以看到NMF的每个基实际上在表示着脸部的某个部件，这种性质在许多场景上就有了它特有的用处了。

我们换个角度来想像一下这三种情景。

VQ其实就像kmeans，它的基都落在原数据的最具代表性的位置上。

PCA的基则是指向四向八方的，相互正交着。

NMF的原数据首先就是只分布在非负子空间里面的，然后它的基则在这个非负子空间靠近边缘的区域，像一组长短不一、间隔不一的伞骨。

怎么分解？

这是个有界优化问题

所以最直观的最简单的方法就是

方法一：

嗯，真是简单到几行代码就搞定了，而且跟原问题保持一致。

我们看标准的有界优化问题

标准的解法

所以我们方法一是按套路出牌的。

但是，作为有追求有理想的同学们，Lee and Seung (1999)认为方法一不够好，要来点更快的。

方法二：

这个又叫乘法更新法，因为人家用了乘法......

推导起来有点麻烦，但写起代码来也是相当简单，几行代码足矣，而且收敛比方法一快一些。

但是，作为有追求有理想的同学们，林智仁（没错，就是搞libsvm那个林智仁）C Lin(2007)摇摇头，“看我的”。

方法三：

传说中这个方法是快了一些，然而我觉得有方法一和二就妥妥了，像现在这么强计算力的时代，计算省下来那点时间，还抵不回写这复杂代码多花的时间。

林智仁这篇文章C Lin(2007)是后期出来的，review了之前几种主流的方法，再提出自己的新方法，所以这篇的内容比较全（懒人只看这一篇就够了）。