上一篇矩阵补全展示了如何从部分观测恢复低秩矩阵。本篇回到一个更基本的问题:当数据矩阵的元素天然非负(如像素灰度、词频、评分),分解出来的因子也应该非负——这个简单的约束会带来什么?
答案是深刻的:非负约束迫使分解只能用加法组合来重建数据,不允许减法抵消。 这自然导致了”parts-based”表示——分解出的基向量对应数据的局部部件,而不是 PCA 那样的全局模式。Lee 和 Seung 在 1999 年的 Nature 论文中用人脸分解生动展示了这一点:PCA 给出鬼影般的”特征脸”(eigenfaces),每张都是全脸模式;NMF 给出眉毛、眼睛、鼻子、嘴巴等可解释的局部部件(见 Lee & Seung, 1999, Figure 1)。
NMF(Non-negative Matrix Factorization,非负矩阵分解) 是 Part 1 “拆” 应用阶段的核心方法之一。它与 SVD(Art. 3 SVD)的关系不是”特例”而是”另一条路”——SVD 追求正交性和全局最优,NMF 追求非负性和可解释性。两者回答不同的问题:SVD 问”最优低秩近似是什么”,NMF 问”数据由哪些部件叠加而成”。
问题定义:非负约束的深层含义
形式化
给定非负矩阵 A∈R≥0m×n(所有元素 aij≥0),NMF 寻找两个非负矩阵:
A≈WH,W∈R≥0m×k,H∈R≥0k×n
其中 k≪min(m,n) 是分解秩。
逐项理解:
- A∈R≥0m×n:原始数据矩阵,m 个样本 × n 个特征,所有元素非负
- W∈R≥0m×k:系数矩阵(也叫”混合矩阵”)——第 i 行 wi∈R≥0k 表示第 i 个样本由 k 个基的加权组合
- H∈R≥0k×n:基矩阵——第 a 行 ha∈R≥0n 是第 a 个”部件”的特征模式
- k:分解秩,决定部件的数量
每个数据点(A 的第 i 行)被近似表示为:
aiT≈∑a=1kwiahaT
由于 wia≥0 且 ha≥0,每个数据点是基向量的非负加权叠加。
非负约束 → 只允许加法 → Parts-Based
PCA vs NMF:全局模式 vs 局部部件
蓝色 = 正值,红色 = 负值;NMF 只有正值(蓝),自然产生局部部件
这是 NMF 最核心的洞察,值得仔细展开。
对比 PCA/SVD:在 PCA 中,数据的近似表示为 x~≈∑j=1kcjwj,其中系数 cj 和基向量 wj 的分量都可以是正的或负的。这意味着不同基向量可以互相抵消——一个基向量添加的特征,另一个可以减去。结果是每个基向量必须编码全局信息(它需要”知道”其他基向量会添加或减去什么),产生的是全局模式(holistic representation)。
NMF 的情况:非负约束 wia≥0, haj≥0 意味着基向量只能被加上去,不能被减去。如果第 a 个基在第 j 个特征上 haj>0,那这个基被使用时(wia>0)只会增加第 j 个特征的值,永远不会减少。
这个”只加不减”的约束有一个深刻的后果:每个基向量倾向于只在数据的一个局部区域激活。为什么?如果一个基在不相关的区域也有大的正值,而数据在那个区域的值很小,那叠加后会产生不必要的正值偏差——没有其他基能通过”减法”来补偿。因此,NMF 学到的基天然倾向于稀疏且局部。
用人脸的例子说:
- PCA 的第一个特征脸(PC1)可能在眼睛区域为正、在嘴巴区域为负——它编码的是”眼睛亮则嘴暗”这样的全局相关模式
- NMF 的一个基向量更可能只在”鼻子区域”为正、其他区域接近零——它就是”鼻子部件”
目标函数
NMF 最常用的目标函数是 Frobenius 范数平方下的重建误差(也叫欧氏距离目标):
minW≥0,H≥0∥A−WH∥F2=minW≥0,H≥0∑i=1m∑j=1n(aij−[WH]ij)2
其中 [WH]ij=∑a=1kwiahaj。
另一个常用目标是 KL 散度(Kullback-Leibler divergence,也叫广义 KL 散度或 I-散度):
DKL(A∥WH)=∑i,j(aijlog[WH]ijaij−aij+[WH]ij)
KL 散度目标在处理计数数据(如词频)时更自然,因为它对应泊松噪声模型。本文主要聚焦 Frobenius 范数目标。
非凸性:与 SVD 不同,NMF 的优化问题是非凸的——没有封闭解,也不保证找到全局最优。固定 W 优化 H 是凸的(非负最小二乘),固定 H 优化 W 也是凸的,但同时优化 W 和 H 是非凸的。这是 NMF 付出的代价:换来了可解释性,失去了全局最优的保证。
乘法更新规则:Lee & Seung 的核心贡献
Lee 和 Seung 在 NeurIPS 2000 提出了 NMF 最著名的求解算法——乘法更新规则(multiplicative update rules)。它的优雅之处在于:更新规则自动保持非负性,不需要额外的投影步骤。
更新公式
Haj←Haj(WTWH)aj(WTA)aj
Wia←Wia(WHHT)ia(AHT)ia
这两个规则交替应用:先固定 W 更新 H,再固定 H 更新 W,重复直到收敛。
关键性质:如果 W 和 H 初始化为正值,那么乘法更新永远保持非负性——因为每次更新都是”当前值 × 正数 / 正数 = 正数”。
从梯度下降推导乘法更新
乘法更新不是凭空出现的,它可以从标准梯度下降自然推导出来。下面给出完整推导。
第一步:计算目标函数对 H 的梯度。
目标函数 L=∥A−WH∥F2。展开:
L=tr[(A−WH)T(A−WH)]=tr(ATA)−2tr(ATWH)+tr(HTWTWH)
对 H 求矩阵导数(利用矩阵微积分的结果):
∂H∂L=−2WTA+2WTWH
逐项理解:
- −2WTA:“好”的部分,把 A 中的信息拉向 H(梯度为负 → 增大 H 会减小误差)
- +2WTWH:“坏”的部分,当前重建 WH 对 H 的惩罚(梯度为正 → 增大 H 会增大误差)
第二步:标准梯度下降。
标准梯度下降更新 H:
H←H−η⋅∂H∂L=H−η⋅(−2WTA+2WTWH)
即:
H←H+2η(WTA−WTWH)
问题:这个更新不保证非负性。即使 H 当前非负,减去一个正数后可能变负。
第三步:元素级自适应步长。
Lee 和 Seung 的关键洞察是:选择一个元素级的(element-wise)步长,而不是全局标量步长 η。具体地,令步长为:
ηaj=2(WTWH)ajHaj
注意 Haj≥0 且 (WTWH)aj≥0(因为所有因子非负),所以 ηaj≥0。
代入梯度下降公式:
Haj←Haj+2⋅2(WTWH)ajHaj⋅[(WTA)aj−(WTWH)aj]
=Haj+(WTWH)ajHaj⋅(WTA)aj−(WTWH)ajHaj⋅(WTWH)aj
=Haj+Haj(WTWH)aj(WTA)aj−Haj
=Haj(WTWH)aj(WTA)aj
这就是乘法更新规则!它不过是步长为 ηaj=2(WTWH)ajHaj 的元素级梯度下降。
W 的更新完全对称。目标函数对 W 的梯度是:
∂W∂L=−2AHT+2WHHT
选择元素级步长 ηia=2(WHHT)iaWia,同样的推导给出:
Wia←Wia(WHHT)ia(AHT)ia
收敛性保证
Lee 和 Seung 证明了以下性质(见 Lee & Seung, 2000, Theorem 1):
定理:在乘法更新规则下,目标函数 ∥A−WH∥F2 是单调不增的。即每次更新后,重建误差要么减小,要么不变。
证明的核心工具是辅助函数(auxiliary function)方法——构造一个目标函数的上界,证明乘法更新恰好是最小化这个上界的步骤。这与 EM 算法的思路类似。
注意:单调不增保证的是收敛到驻点(stationary point),不是全局最优。由于问题非凸,不同的初始化可能导致不同的局部最优解。实践中通常多次随机初始化,选择最终误差最小的结果。
直觉总结
乘法更新的直觉可以概括为:
每个元素按照”应该有多大”与”实际有多大”的比值来缩放。
- 如果 (WTA)aj>(WTWH)aj——“数据说这里应该更大”大于”当前重建认为的值”——比值 > 1,Haj 增大
- 如果 (WTA)aj<(WTWH)aj——“当前重建偏大”——比值 < 1,Haj 缩小
- 如果两者相等——已经匹配了——比值 = 1,Haj 不变
数值例子:3×4 矩阵的 NMF
为了把乘法更新规则落地,我们对一个小矩阵做手算 NMF。
数据矩阵(3 个样本 × 4 个特征):
A=541301000115
直觉上,前两行的特征 1-2 较大(“部件 A”),第三行的特征 4 较大(“部件 B”),特征 3 全为零。
目标:k=2,即 A≈WH,W∈R≥03×2,H∈R≥02×4。
初始化
随机初始化(取简单正值):
W(0)=111111,H(0)=[11111111]
第一轮迭代
更新 H:H←H⊙WTWHWTA(⊙ 表示逐元素乘法,分数表示逐元素除法)
计算分子 WTA(2×4):
W(0)TA=[111111]541301000115=[1010440077]
计算分母 WTWH:先算 WTW(2×2):
W(0)TW(0)=[3333]
再算 WTW⋅H(0)(2×4):
[3333][11111111]=[66666666]
逐元素更新:
H(1)=H(0)⊙WTWH(0)WTA=[11111111]⊙[10/610/64/64/60/60/67/67/6]
=[1.6671.6670.6670.667001.1671.167]
注意特征 3 的值直接变为 0——因为 A 中该列全为 0,分子 (WTA)⋅3=0。乘法更新自动处理了零元素。
更新 W:W←W⊙WHHTAHT
计算分子 AH(1)T(3×2):
AH(1)T=5413010001151.6670.66701.1671.6670.66701.167=11.5027.8358.16911.5027.8358.169
计算分母 W(0)H(1)H(1)T:先算 H(1)H(1)T(2×2):
H(1)H(1)T=[1.6672+0.6672+0+1.1672⋯⋯⋯]=[4.5844.5844.5844.584]
W(0)H(1)H(1)T=111111[4.5844.5844.5844.584]=9.1689.1689.1689.1689.1689.168
逐元素更新:
W(1)=W(0)⊙W(0)H(1)H(1)TAH(1)T=1.2550.8550.8911.2550.8550.891
第一轮后,W 和 H 的两列/行仍然相同(因为初始化完全对称)。但随着迭代继续,微小的数值差异会打破对称性。实践中通常用随机不对称初始化来避免这个问题。
经过约 50-100 轮迭代,NMF 会收敛到类似以下形态(具体值取决于初始化):
W≈1.71.30.00.10.21.4,H≈[2.90.71.70.6000.23.5]
解读:
- 基 1(H 第 1 行):特征 1、2 大,特征 3、4 小——对应”部件 A”
- 基 2(H 第 2 行):特征 4 大,其他小——对应”部件 B”
- 样本 1 和 2 主要由部件 A 构成(W 对应行的第 1 列大)
- 样本 3 主要由部件 B 构成(W 第 3 行的第 2 列大)
NMF 成功发现了数据的”部件结构”!
NMF vs PCA/SVD:核心区别
下面的交互组件展示 NMF 和 PCA(截断 SVD)在分解同一个非负矩阵时的区别。左侧 NMF 的基和权重全是非负的(蓝色深浅表示大小),右侧 SVD 的基和权重有正有负(蓝色 = 正,红色 = 负)。拖动滑块改变分解秩 k。
NMF vs PCA:分解方式对比
非负矩阵分解产生 parts-based 表示,PCA 产生全局模式
3
NMF
Frobenius 误差: 3.081
所有值 ≥ 0,局部部件可相加
SVD (PCA)
Frobenius 误差: 2.678
有正有负,全局模式可相消
观察几个关键差异:
-
NMF 基向量是稀疏的、局部的:每个基只在矩阵的一个区域有较大的非负值,其他区域接近零。这就是”parts-based”表示——每个基代表一个”部件”。
-
SVD 基向量是全局的、有正负的:每个奇异向量在整个矩阵范围内有正有负值。不同奇异向量之间通过正负抵消来精确重建,但单独一个奇异向量没有直观的”部件”含义。
-
SVD 的重建误差更小:对于相同的 k,SVD 截断(Eckart-Young 定理保证的最优性)总是给出 Frobenius 范数意义下的最小重建误差。NMF 由于非负约束的限制,重建误差一般更大——这是可解释性的代价。
-
NMF 结果可加性解释:NMF 的重建是 A≈∑a=1kwiahaT,每一项都是非负的,可以解释为”加上部件 a 的贡献”。SVD 的重建 A≈∑i=1kσiuiviT 中的各项有正有负,无法做这种加法解释。
应用:话题模型
NMF 最成功的应用之一是文档的话题发现(topic discovery),它可以被视为经典话题模型 LDA(Latent Dirichlet Allocation)的简化版。
文档-词矩阵的 NMF
NMF 话题模型:文档-词矩阵 ≈ 话题混合 × 话题词分布
考虑一个文档-词矩阵(term-document matrix)A∈R≥0m×n:
- m 个文档,n 个词
- aij = 词 j 在文档 i 中的出现次数(或 TF-IDF 权重)
- 所有元素天然非负
对 A 做 NMF:A≈WH
m×nA≈m×kW⋅k×nH
解读:
- H 的第 a 行 ha∈R≥0n:第 a 个话题的词分布——haj 大说明词 j 在话题 a 中重要
- W 的第 i 行 wi∈R≥0k:文档 i 的话题混合——wia 大说明文档 i 主要属于话题 a
- k:话题数量(需要人工指定)
NMF 的非负性在这里完美对应语义:
- 词频不能为负:一个词在一个话题中的重要性 ≥0
- 话题贡献不能为负:一篇文档中某个话题的权重 ≥0
- 加法组合:一篇文档 = 话题 1 的贡献 + 话题 2 的贡献 + …,没有”负话题”
与 LDA 的关系
LDA(Latent Dirichlet Allocation)是概率话题模型的标准方法,它假设:
- 每个话题是词上的概率分布(非负且归一化)
- 每篇文档是话题上的概率分布(非负且归一化)
NMF 的话题模型没有概率归一化约束,但在实践中,对 NMF 结果的行归一化可以得到类似的概率解释。实证研究表明,NMF 和 LDA 在许多话题发现任务上效果相当,而 NMF 的优势在于:
- 计算更简单:NMF 只需矩阵运算,不需要贝叶斯推断(变分推断或 MCMC)
- 确定性结果(给定初始化):不像 MCMC 采样那样有随机波动
- 容易添加正则化:如稀疏约束 ∥W∥1、∥H∥1
具体例子
假设有 4 篇文档和 6 个词,文档-词矩阵为:
| machine | learning | network | cat | dog | pet |
|---|
| doc1 | 5 | 4 | 3 | 0 | 0 | 0 |
| doc2 | 4 | 5 | 4 | 0 | 1 | 0 |
| doc3 | 0 | 0 | 0 | 4 | 5 | 3 |
| doc4 | 0 | 1 | 0 | 3 | 4 | 5 |
用 k=2 做 NMF,期望得到两个话题:
- 话题 1(“机器学习”):h1≈(hmachine,hlearning,hnetwork,0,0,0),“machine”、“learning”、“network” 权重大
- 话题 2(“宠物”):h2≈(0,0,0,hcat,hdog,hpet),“cat”、“dog”、“pet” 权重大
文档 1、2 的话题混合 wi 中话题 1 权重大;文档 3、4 中话题 2 权重大。doc2 和 doc4 可能有少量跨话题的词(如 doc2 中的 “dog”),NMF 会在话题混合中反映这一点。
NMF 的变体与正则化
稀疏 NMF
在基础 NMF 上添加 ℓ1 正则化项,鼓励 W 和/或 H 更稀疏:
minW≥0,H≥0∥A−WH∥F2+α∥W∥1+β∥H∥1
其中 ∥W∥1=∑iawia,∥H∥1=∑ajhaj。
稀疏正则化使得每个基更加局部(更多元素为零),话题模型中的话题更加”纯净”。
非唯一性问题
NMF 的分解结果不唯一:对于任何可逆的非负对角矩阵 D,W′=WD,H′=D−1H 给出相同的乘积 W′H′=WH。更一般地,对于非负可逆矩阵 C,W′=WC,H′=C−1H 也可能保持非负性。
这意味着 NMF 的 W 和 H 的绝对值没有唯一含义——只有它们的乘积 WH 是确定的。实践中通常对 H 的行或 W 的列做归一化来消除缩放歧义。
总结与展望
NMF 是 Part 1 “拆” 方法谱系中一个独特的分支——它放弃了 SVD 的正交性和全局最优性,换来了非负性和 parts-based 可解释性。
关键要点:
- 非负约束 → 只加不减 → parts-based:NMF 的核心洞察。非负约束迫使基向量稀疏且局部,自然产生”部件”表示
- 目标函数:minW≥0,H≥0∥A−WH∥F2,非凸优化,无封闭解
- 乘法更新规则:H←H⊙WTWHWTA,W←W⊙WHHTAHT——本质是自适应步长的元素级梯度下降
- Lee & Seung 的收敛保证:目标函数单调不增,收敛到驻点(但不保证全局最优)
- 话题模型:文档-词矩阵的 NMF 自然产生话题的词分布和文档的话题混合,可视为 LDA 的简化版
- 与 SVD/PCA 的互补:SVD 给最优近似但缺乏可解释性,NMF 给可解释的部件但近似质量稍差
方法谱系中的位置:
SVD(无约束最优)+正交PCA−正交+非负NMF
NMF “去掉正交、加上非负” 的思路揭示了一个普遍模式:不同的约束适合不同的数据结构。当数据天然非负且由部件叠加构成时,NMF 比 PCA 更合适;当数据分布在线性子空间上时,PCA 更合适。选择哪种分解,取决于你相信数据的生成机制。
下一篇我们转向推荐系统中的矩阵分解(MF)和 Factorization Machines(FM)——它们可以理解为 NMF 在预测任务中的扩展,允许偏置项和任意特征交叉。