非负矩阵分解（NMF）算法

题目描述
给定一个非负矩阵 \(V \in \mathbb{R}^{m \times n}\)（即所有元素 \(V_{ij} \geq 0\)），NMF 的目标是找到两个非负矩阵 \(W \in \mathbb{R}^{m \times k}\) 和 \(H \in \mathbb{R}^{k \times n}\)（其中 \(k \ll \min(m, n)\)），使得它们的乘积近似等于原矩阵：

\[V \approx WH. \]

NMF 常用于数据降维、特征提取和话题建模（如文本分析），其非负性约束使得分解结果具有直观的可解释性。

解题过程

1. 问题形式化
NMF 是一个非凸优化问题，常用目标函数为平方误差（Frobenius 范数）：

\[\min_{W \geq 0, H \geq 0} \| V - WH \|_F^2. \]

由于非凸性，通常通过迭代更新算法寻找局部最优解。

2. 乘法更新规则（Lee-Seung 算法）
最经典的求解方法是基于梯度下降的乘法更新规则：

• 初始化：随机生成非负的 \(W\) 和 \(H\)。
• 迭代更新：交替固定 \(W\) 或 \(H\)，通过乘法形式更新另一变量，保证非负性。

更新步骤：
（1）更新 \(H\)（固定 \(W\)）：

\[H_{ij} \leftarrow H_{ij} \frac{(W^T V)_{ij}}{(W^T W H)_{ij}}. \]

（2）更新 \(W\)（固定 \(H\)）：

\[W_{ij} \leftarrow W_{ij} \frac{(V H^T)_{ij}}{(W H H^T)_{ij}}. \]

每次更新后，需对 \(W\) 的列进行归一化（避免数值不稳定）。

3. 更新规则的推导（直观解释）
以更新 \(H\) 为例：

• 目标函数对 \(H\) 的梯度为 \(\nabla_H \|V - WH\|_F^2 = -2W^T(V - WH)\)。
• 将梯度分解为正向部分（\(W^T V\)）和负向部分（\(W^T W H\)）。
• 乘法更新规则可视为对梯度下降步长的自适应调整：

\[H_{ij} \leftarrow H_{ij} - \eta_{ij} [\nabla_H]_{ij}, \]

其中步长 \(\eta_{ij} = \frac{H_{ij}}{(W^T W H)_{ij}}\)。代入后即得到乘法形式。

4. 收敛性与停止条件

• 乘法更新规则能保证目标函数非递增（证明需利用辅助函数法）。
• 停止条件通常设为：
  • 目标函数变化小于阈值（如 \(\|V - WH\|_F^2\) 变化量 < \(10^{-6}\)）；
  • 或达到最大迭代次数（如 1000 次）。

5. 算法总结

输入：非负矩阵 V，秩 k，最大迭代次数 T
输出：非负矩阵 W, H
1. 初始化 W, H 为随机非负矩阵
2. for t = 1 to T:
3.   更新 H：H = H .* (W^T V) ./ (W^T W H)   # .* 和 ./ 表示逐元素乘除
4.   更新 W：W = W .* (V H^T) ./ (W H H^T)
5.   对 W 的每列进行归一化（保持尺度平衡）
6.   若目标函数收敛则提前终止
7. 返回 W, H

6. 应用示例（文本聚类）
假设 \(V\) 是词-文档矩阵（每列为一个文档的词频向量），NMF 分解后：

• \(W\) 的每一列可视为一个“话题”的词汇分布；
• \(H\) 的每一行表示文档对该话题的隶属度。
  通过非负性，话题和文档关系均被解释为加权组合，而非负值。

关键点

• NMF 的非负约束带来可解释性，但解不唯一（尺度、旋转不确定性）。
• 实际中需谨慎选择秩 \(k\)，可通过重建误差或领域知识确定。
• 改进算法（如投影梯度、交替最小二乘）可提升收敛速度或稳定性。