Skip to content

14.6 非负矩阵分解

原文 The Elements of Statistical Learning
翻译 szcf-weiya
发布 2016-09-30
更新 2019-09-01 23:58:46
状态 Done

非负矩阵分解 (Lee and Seung, 1999)1是最近提出来的一个用来替代主成分分析的方法,在这个方法中数据以及成分假定为非负的.这对于建立非负数据的模型很有用,比如图象数据.

$N\times p$ 数据矩阵 $\mathbf X$ 由下式近似

其中 $\mathbf W$ 阶为 $N\times r$,$\mathbf H$ 阶为 $r\times p, r\le \max(N,p)$.我们假设 $x_{ij}, w_{ik}, h_{kj}\ge 0$.

通过最大化下式来确定 $\mathbf W$ 和 $\mathbf H$

这是模型的对数似然,模型中 $x_{ij}$ 服从均值为 $(\mathbf{WH})_{ij}$ 的 Poisson 分布——这对于正值数据是很合理的.

下面的轮换 (alternating) 算法 (Lee and Seung, 2001)2 收敛到 $L(\mathbf W, \mathbf H)$ 的局部最大值:

这个算法可以由最大化 $L(\mathbf W, \mathbf H)$ 的 minorization 过程来导出(练习14.23

weiya 注:Ex. 14.23

练习 14.23 已解答,详细过程参见 Issue 86: Ex. 14.23

weiya 注:minorization

练习 14.23中介绍了 minorization 的概念.对于函数$g(x, y)$和$f(x)$,若对于定义域中所有的 $x$ 和 $y$,若满足 则称$g(x,y)$ minorize $f(x)$.

并且与对数线性模型的 迭代比例缩放算法 (iterative-proportional-scaling algorithm) 相关(练习 14.24).

weiya 注:Ex. 14.24

练习 14.24 已解答,详细过程参见 Issue 87: Ex. 14.24

图 14.33 展示了从 Lee and Seung (1999)1 中选取的例子,其中比较了非负矩阵分解 (NMF),向量量化(VQ,等价于 $k$ 均值聚类)以及主成分分析 (PCA).将这三种学习方法应用到大小为 $N=2429$ 的人脸数据库中,每个包含 $19\times 19$的像素点,得到一个 $2429\times 381$ 的矩阵 $\X$.如 $7\times 7$ 个蒙太奇画(每个都是 $19\times 19$ 的图象)所示,每种方法学习 $r=49$ 张基图象集.正值用黑色像素表示,而负值用红色像素点表示.对于一张特定的脸,如右上角所示,用基图象的线性叠加来近似.线性叠加的系数在 $7\times 7$ 数组中的每个蒙太奇画的右边,最终得到的叠加图像显示在等式右边.作者指出,与 VQ 和 PCA 不同,NMF 是用表示脸的不同部位的基图象来学习去表征脸.

Donoho and Stodden (2004)3 指出非负矩阵分解的一个潜在的严重问题.即使在 $\X=\W\H$严格成立的情形下,分解可能不是唯一的.图 14.34 说明了这个问题.

数据点落在 $p=2$ 维空间中,并且数据与坐标轴之间存在开放的区域 (open space).我们可以在这个开放区域中选择基向量 $h_1$ 和 $h_2$,并且用这些向量的非负线性组合来精确表示每个数据点.这个不唯一性表明上述的算法得到的解会依赖初始值,并且似乎阻碍了因子分解的解释性.尽管这个解释性方面的不足,非负矩阵分解及其应用吸引力许多研究者的兴趣.

原型分析

归功于 Cutler and Breiman (1994)4,这个方法通过原型(数据点的线性组合)来近似数据点.在这个意义上,与 $K$ 均值聚类有相似的地方.然而,不是用单个附近的原型来近似每个数据点,原型分析通过一系列原型的凸组合来近似每个数据点.凸组合的使用强制原型位于数据云的 凸包 (convex hull) 上.在这个意义下,原型是纯的 (pure),或典型的 (archetypal).

如 \eqref{14.72} 一样,$N\times p$ 的数据矩阵 $\X$ 建模为

其中 $\W$ 阶为 $N\times r$,且 $\H$ 为 $r\times p$.我们假设 $w_{ik}\ge 0$,且 $\sum_{k=1}^rw_{ik}=1\;\forall i$.因此 $p$ 维空间中的 $N$ 个数据点($\X$ 的行)用 $r$ 个原型($\H$ 的行)的凸组合来表示.我们还假设

其中 $\B$ 阶为 $r\times N$,其中 $b_{ki}\ge 0$,且 $\sum_{i=1}^Nb_{ki}=1\forall k$.因此原型本身是数据点的凸组合.使用 \eqref{14.75} 和 \eqref{14.76},我们对下式关于权重 $\W$ 和 $\B$ 最小化

我们采用轮换的模式对函数进行最小化,其中每个单独的最小化都涉及到凸优化.然而整个问题不是凸的,所以算法收敛到准则的一个局部最小值点.

图 14.35 展示了二维中模拟数据的例子.上面板展示了 $K$ 均值聚类的结果.为了从原型的凸组合中重构出数据,需要在数据的凸包上定位原型.可以在图 14.35 的上图中看到,并且一般地是这种情形,如 Cutler and Breiman (1994)4 所证明的那样.如图中下面板所示,$K$ 均值聚类在数据云的中间选择原型.

我们可以把 $K$ 均值聚类看成原型模型的特殊情形,其中 $\W$ 的每一行有一个元素取 1,其余取 0.

注意到原型模型 \eqref{14.75} 与非负矩阵分解模型 \eqref{14.72} 有相同的一般形式.然而,这两个模型应用在不同的条件中,并且目标也不太相同.非负矩阵分解目的是近似数据矩阵 $\X$ 的列,并且主要感兴趣的是 $\W$ 的列,它表示了数据中主要的非负组分.原型分析而是关注用 $\H$ 的行(表示了原型数据点)来近似 $\X$ 的行.非负矩阵分解还假设 $r\le p$.当 $r=p$,简单将 $\W$ 选为列经过缩放(所以加起来和为1)的 $\X$,可以得到精确的重构.相反,原型分析要求 $r\le N$,但允许 $r>p$.举个例子,在图 14.35 中,$p=2,N=50$,而 $r=2,4,8$.额外的约束 \eqref{14.76} 表明典型分析不是完美的,即使 $r>p$.

图 14.36 展示了将典型分析应用于图 14.22 中的 3 的数据集的结果. 图 14.36 中的三行是取自三次原型分析的结果,分别是 2 个原型、3 个原型和 4 个原型.和预想一样,该算法得到了大小和形状上都极端的 3.


  1. Lee, D. and Seung, H. (1999). Learning the parts of objects by non-negative matrix factorization, Nature 401: 788. 

  2. Lee, D. and Seung, H. (2001). Algorithms for non-negative matrix factorization, Advances in Neural Information Processing Systems, (NIPS 2001), Vol. 13, Morgan Kaufman, Denver., pp. 556–562. 

  3. Donoho, D. and Stodden, V. (2004). When does non-negative matrix factorization give a correct decomposition into parts?, in S. Thrun, L. Saul and B. Sch¨olkopf (eds), Advances in Neural Information Processing Systems 16, MIT Press, Cambridge, MA. 

  4. Cutler, A. and Breiman, L. (1994). Archetypal analysis, Technometrics 36(4): 338–347. 

Comments