非负矩阵分解（NMF）的交替最小二乘法（ALS）及其优化
题目描述
非负矩阵分解（Non-negative Matrix Factorization, NMF）是一种重要的数据分析和特征提取技术。给定一个非负矩阵 \(V \in \mathbb{R}^{m \times n}\) 和一个预设的秩 \(k\)（满足 \(k < \min(m, n)\)），NMF旨在找到两个非负矩阵 \(W \in \mathbb{R}^{m \times k}\) 和 \(H \in \mathbb{R}^{k \times n}\)，使得它们的乘积 \(WH\) 尽可能地逼近原始矩阵 \(V\)，即 \(V \approx WH\)。这个问题在机器学习、图像处理和文本挖掘等领域有广泛应用。本题将重点讲解求解NMF的经典算法——交替最小二乘法（Alternating Least Squares, ALS）的核心思想、具体步骤、优化技巧以及其背后的数学原理。
解题过程循序渐进讲解
1. 问题形式化
我们的目标是找到非负矩阵 \(W\) 和 \(H\)，以最小化重构误差。通常使用Frobenius范数来度量误差：
\[\min_{W \ge 0, H \ge 0} \| V - WH \|_F^2 \]
其中，\(\| A \|_F^2 = \sum_{i,j} A_{ij}^2\)。约束条件 \(W \ge 0\) 和 \(H \ge 0\) 意味着矩阵的所有元素必须非负。这是一个非凸优化问题，但通过固定其中一个变量，对另一个变量进行优化，可以转化为一系列凸子问题，这正是交替最小二乘法的核心思想。
2. 交替最小二乘法（ALS）的基本框架
ALS算法通过交替地固定 \(W\) 或 \(H\)，并求解相应的最小二乘问题来更新变量，直至满足收敛条件。基本步骤如下：
- 步骤1（初始化）：随机初始化 \(W\) 和 \(H\) 为非负矩阵（例如，从均匀分布或正态分布采样后取绝对值）。
- 步骤2（交替更新）：
a. 固定 \(H\)，更新 \(W\)：此时优化问题变为：
\[ \min_{W \ge 0} \| V - WH \|_F^2 \]
由于 $ H $ 固定，这是一个关于 $ W $ 的约束最小二乘问题。
b. 固定 \(W\)，更新 \(H\)：此时优化问题变为：
\[ \min_{H \ge 0} \| V - WH \|_F^2 \]
类似地，这是一个关于 $ H $ 的约束最小二乘问题。
- 步骤3（迭代与收敛）：重复步骤2，直到重构误差的变化小于预设阈值，或达到最大迭代次数。
3. 子问题的详细求解：非负最小二乘
在ALS中，关键是如何高效求解每个子问题。以“固定 \(H\)，更新 \(W\)”为例，目标函数可以展开为：
\[\| V - WH \|_F^2 = \text{tr}((V - WH)^T(V - WH)) \]
其中 \(\text{tr}(\cdot)\) 表示矩阵的迹。对 \(W\) 求梯度并设为零，在无约束情况下可得正规方程：
\[\frac{\partial}{\partial W} \| V - WH \|_F^2 = -2VH^T + 2WHH^T = 0 \quad \Rightarrow \quad WHH^T = VH^T \]
这是一个关于 \(W\) 的线性方程组。但由于有非负约束 \(W \ge 0\)，我们不能直接解这个方程组。一种经典的处理方法是投影梯度法：先计算无约束解，然后将负元素投影到零。具体地：
- 计算无约束最小二乘解：\(W_{\text{unconstrained}} = VH^T (HH^T)^{-1}\)。
- 投影：将 \(W_{\text{unconstrained}}\) 中的负元素置为零，得到新的 \(W\)。
然而，直接求逆计算量大（复杂度 \(O(k^3)\)），且可能数值不稳定。因此，实践中常采用更高效的更新规则。
4. 乘法更新规则（Multiplicative Update Rules）
为了高效确保非负性，Lee和Seung提出了著名的乘法更新规则，它是ALS的一种特例，通过梯度下降结合特定步长推导得出。对于Frobenius范数目标函数，更新规则为：
- 更新 \(H\)：
\[ H_{ij} \leftarrow H_{ij} \frac{(W^T V)_{ij}}{(W^T W H)_{ij}} \]
- 更新 \(W\)：
\[ W_{ij} \leftarrow W_{ij} \frac{(V H^T)_{ij}}{(W H H^T)_{ij}} \]
这些更新是逐元素进行的，且由于所有参与运算的矩阵非负，更新后 \(W\) 和 \(H\) 仍保持非负。乘法更新可以看作是一种归一化的梯度下降，步长选择使得更新量总为正，从而自动满足约束。算法步骤为：
- 初始化 \(W, H\) 为非负随机矩阵。
- 交替使用上述乘法公式更新 \(H\) 和 \(W\)。
- 重复直到收敛。
乘法更新简单易实现，但收敛速度可能较慢，且可能收敛到鞍点。
5. 加速与优化技巧
为了提高ALS的性能，可以采用以下优化：
- 正则化：在目标函数中加入正则化项（如L1或L2范数）以防止过拟合，例如：
\[ \min_{W \ge 0, H \ge 0} \| V - WH \|_F^2 + \alpha \|W\|_F^2 + \beta \|H\|_F^2 \]
此时更新规则需相应调整，例如更新 \(W\) 的公式变为：
\[ W_{ij} \leftarrow W_{ij} \frac{(V H^T)_{ij}}{(W H H^T + \alpha W)_{ij}} \]
- 交替非负最小二乘（ANLS）：使用更精确的非负最小二乘求解器（如活动集法）代替乘法更新，虽然每次迭代成本更高，但可能减少总迭代次数。
- 随机化与并行化：对于大规模矩阵，可以使用随机采样（如随机行/列子集）来近似计算 \(VH^T\) 和 \(HH^T\)，或并行化更新步骤以加速。
6. 收敛性与停止准则
由于目标函数有下界（非负）且每次迭代不增，ALS算法保证目标函数值单调递减，从而收敛到某个局部极小点。常用停止准则包括：
- 相对误差变化：\(\frac{| \text{error}_{t} - \text{error}_{t-1} |}{\text{error}_{t-1}} < \epsilon\)。
- 梯度投影范数：检查KKT条件的违反程度。
通常设置最大迭代次数作为备用停止条件。
7. 应用示例与总结
假设 \(V\) 是一个词-文档矩阵（元素表示词频），经过NMF分解后，\(W\) 的列可解释为“主题”或“基础特征”，\(H\) 的行表示文档在这些主题上的权重。由于非负性，分解结果具有直观的可解释性。
总结：NMF的交替最小二乘法通过将非凸问题分解为两个凸子问题，交替优化来求解。基础ALS结合投影或乘法更新，在保证非负性的同时逼近最优解。尽管可能收敛到局部最优，但其高效性和可解释性使其成为处理高维非负数据的强大工具。