非负矩阵分解（Non-negative Matrix Factorization, NMF）的乘性更新规则（Multiplicative Update Rules）及其推导
字数 4487 2025-12-23 03:22:30

非负矩阵分解（Non-negative Matrix Factorization, NMF）的乘性更新规则（Multiplicative Update Rules）及其推导

题目描述

给定一个非负矩阵 \(\mathbf{V} \in \mathbb{R}^{m \times n}_{\ge 0}\)（即所有元素大于等于零），非负矩阵分解（NMF）的目标是将其分解为两个非负矩阵的乘积：

\[\mathbf{V} \approx \mathbf{W} \mathbf{H}, \]

其中 \(\mathbf{W} \in \mathbb{R}^{m \times r}_{\ge 0}\)，\(\mathbf{H} \in \mathbb{R}^{r \times n}_{\ge 0}\)，且 \(r \ll \min(m, n)\)。这里 \(r\) 是低秩或隐藏特征的维度。
为了找到合适的 \(\mathbf{W}\) 和 \(\mathbf{H}\)，需要定义一个损失函数来度量分解的误差。一种常见选择是使用 Frobenius 范数平方误差（欧几里得距离）：

\[D(\mathbf{V} \| \mathbf{WH}) = \frac{1}{2} \|\mathbf{V} - \mathbf{WH}\|_F^2 = \frac{1}{2} \sum_{i,j} (V_{ij} - (\mathbf{WH})_{ij})^2. \]

本题要求推导用于优化该问题的 乘性更新规则（Multiplicative Update Rules），并解释其为什么能保证矩阵的非负性、如何迭代更新以及收敛性质。

解题过程

1. 问题形式化与约束优化

我们要最小化损失函数：

\[\min_{\mathbf{W} \ge 0, \mathbf{H} \ge 0} \frac{1}{2} \|\mathbf{V} - \mathbf{W}\mathbf{H}\|_F^2. \]

这是一个带非负约束的优化问题。由于约束的存在，不能直接使用梯度下降后截断为零（可能破坏梯度方向的最优性）。因此，我们需要一种能自然保持非负性的优化方法。

2. 推导乘性更新规则的基本思路

乘性更新规则由 Lee 和 Seung (2001) 提出，其核心思想是：

  • 使用梯度下降的框架，但将学习率选择为一个与当前参数成比例的特定值，使得更新步骤变为乘法形式。
  • 这种选择能自动确保非负性：如果初始值非负，则更新后仍保持非负。

我们先分别对 \(\mathbf{W}\) 和 \(\mathbf{H}\) 推导。

3. 对 \(\mathbf{H}\) 的更新规则推导

固定 \(\mathbf{W}\)，考虑损失函数关于 \(\mathbf{H}\) 的梯度。设 \(\mathbf{A} = \mathbf{W} \mathbf{H}\)，则：

\[\frac{\partial D}{\partial H_{ab}} = \frac{\partial}{\partial H_{ab}} \left[ \frac{1}{2} \sum_{i,j} (V_{ij} - A_{ij})^2 \right]. \]

注意 \(A_{ij} = \sum_k W_{ik} H_{kj}\)，所以：

\[\frac{\partial A_{ij}}{\partial H_{ab}} = \begin{cases} W_{ia}, & \text{if } j = b \\ 0, & \text{otherwise} \end{cases}. \]

因此：

\[\frac{\partial D}{\partial H_{ab}} = \sum_i (A_{ib} - V_{ib}) W_{ia} = \left[ \mathbf{W}^T (\mathbf{W} \mathbf{H} - \mathbf{V}) \right]_{ab}. \]

记梯度矩阵为：

\[\nabla_{\mathbf{H}} D = \mathbf{W}^T (\mathbf{W} \mathbf{H} - \mathbf{V}). \]

梯度下降更新为：

\[H_{ab} \leftarrow H_{ab} - \eta_{ab} \cdot \frac{\partial D}{\partial H_{ab}}, \]

其中 \(\eta_{ab} > 0\) 是学习率。

为了得到乘性更新，我们选择学习率为：

\[\eta_{ab} = \frac{H_{ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H})_{ab}}. \]

注意分母 \((\mathbf{W}^T \mathbf{W} \mathbf{H})_{ab}\) 非负（因为所有矩阵非负）。

代入更新公式：

\[H_{ab} \leftarrow H_{ab} - \frac{H_{ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H})_{ab}} \cdot \left[ \mathbf{W}^T (\mathbf{W} \mathbf{H} - \mathbf{V}) \right]_{ab}. \]

整理：

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

这就是 \(\mathbf{H}\) 的乘性更新规则。

非负性保持：如果初始 \(H_{ab} > 0\)，且 \((\mathbf{W}^T \mathbf{V})_{ab} \ge 0\)（因为 \(\mathbf{W}, \mathbf{V}\) 非负），分母 \((\mathbf{W}^T \mathbf{W} \mathbf{H})_{ab} > 0\)，则更新后 \(H_{ab}\) 仍非负。若某元素 \(H_{ab} = 0\)，则更新后仍为 0（因为乘以一个因子）。

4. 对 \(\mathbf{W}\) 的更新规则推导

固定 \(\mathbf{H}\)，类似地求梯度。由对称性，损失函数对 \(\mathbf{W}\) 的梯度为：

\[\nabla_{\mathbf{W}} D = (\mathbf{W} \mathbf{H} - \mathbf{V}) \mathbf{H}^T. \]

选择学习率：

\[\eta_{ij} = \frac{W_{ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T)_{ij}}. \]

梯度下降更新：

\[W_{ij} \leftarrow W_{ij} - \frac{W_{ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T)_{ij}} \cdot \left[ (\mathbf{W} \mathbf{H} - \mathbf{V}) \mathbf{H}^T \right]_{ij}. \]

整理得：

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

这就是 \(\mathbf{W}\) 的乘性更新规则。

5. 算法步骤总结

  1. 初始化：随机生成非负矩阵 \(\mathbf{W}^{(0)}\) 和 \(\mathbf{H}^{(0)}\)，或使用其他非负初始化方法。
  2. 迭代更新（直到收敛或达到最大迭代次数）：
    • 更新 \(\mathbf{H}\)：

\[ H_{ab} \leftarrow H_{ab} \cdot \frac{(\mathbf{W}^T \mathbf{V})_{ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H})_{ab}}, \quad \forall a,b. \]

  • 更新 \(\mathbf{W}\)：

\[ W_{ij} \leftarrow W_{ij} \cdot \frac{(\mathbf{V} \mathbf{H}^T)_{ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T)_{ij}}, \quad \forall i,j. \]

  1. 输出：分解矩阵 \(\mathbf{W}\) 和 \(\mathbf{H}\)。

6. 乘性更新规则的性质

  • 非负性保持：如上所述，更新公式只包含非负矩阵的乘除，因此只要初始值非负，迭代中永远非负。
  • 单调性：可以证明，在更新规则下，损失函数 \(D\) 是单调不增的（通常下降）。这源于更新规则实际上是对损失函数在某个辅助函数上的最小化（利用 MM 算法 或 辅助函数法）。
  • 收敛性：迭代生成的序列会收敛到一个稳定点（通常是一个局部最小值或鞍点）。但可能收敛缓慢，且对初始值敏感。
  • 计算简便：只需矩阵乘法和逐元素除法，易于实现。

7. 直观理解与示例

  • 直观解释：更新规则将当前估计 \(\mathbf{W} \mathbf{H}\) 与目标 \(\mathbf{V}\) 进行比较，通过比例因子调整。例如，若 \((\mathbf{W}^T \mathbf{V})_{ab}\) 较大（表示 \(\mathbf{W}\) 的第 \(a\) 列与 \(\mathbf{V}\) 的第 \(b\) 列相关性高），则增加 \(H_{ab}\)；反之则减小。
  • 示例：假设 \(\mathbf{V}\) 是文档-词矩阵（每列为一个文档的词频向量），NMF 可解释为：
    \(\mathbf{W}\) 的每一列是一个“主题”的词分布，
    \(\mathbf{H}\) 的每一列是一个文档的主题权重。
    乘性更新可视为不断调整主题和权重，以更好地拟合观测数据。

总结

非负矩阵分解的乘性更新规则提供了一种简单有效的方法，在保持非负约束的同时最小化欧几里得损失。其推导基于梯度下降结合特定的学习率选择，确保了迭代中的非负性和损失函数下降。该算法广泛应用于文本挖掘、图像分析和推荐系统等领域，是处理非负数据分解的重要工具。

非负矩阵分解（Non-negative Matrix Factorization, NMF）的乘性更新规则（Multiplicative Update Rules）及其推导 题目描述 给定一个非负矩阵 \( \mathbf{V} \in \mathbb{R}^{m \times n} {\ge 0} \)（即所有元素大于等于零），非负矩阵分解（NMF）的目标是将其分解为两个非负矩阵的乘积： \[ \mathbf{V} \approx \mathbf{W} \mathbf{H}, \] 其中 \( \mathbf{W} \in \mathbb{R}^{m \times r} {\ge 0} \)，\( \mathbf{H} \in \mathbb{R}^{r \times n} {\ge 0} \)，且 \( r \ll \min(m, n) \)。这里 \( r \) 是低秩或隐藏特征的维度。 为了找到合适的 \( \mathbf{W} \) 和 \( \mathbf{H} \)，需要定义一个损失函数来度量分解的误差。一种常见选择是使用 Frobenius 范数平方误差 （欧几里得距离）： \[ D(\mathbf{V} \| \mathbf{WH}) = \frac{1}{2} \|\mathbf{V} - \mathbf{WH}\| F^2 = \frac{1}{2} \sum {i,j} (V {ij} - (\mathbf{WH})_ {ij})^2. \] 本题要求推导用于优化该问题的 乘性更新规则 （Multiplicative Update Rules），并解释其为什么能保证矩阵的非负性、如何迭代更新以及收敛性质。 解题过程 1. 问题形式化与约束优化 我们要最小化损失函数： \[ \min_ {\mathbf{W} \ge 0, \mathbf{H} \ge 0} \frac{1}{2} \|\mathbf{V} - \mathbf{W}\mathbf{H}\|_ F^2. \] 这是一个带非负约束的优化问题。由于约束的存在，不能直接使用梯度下降后截断为零（可能破坏梯度方向的最优性）。因此，我们需要一种能自然保持非负性的优化方法。 2. 推导乘性更新规则的基本思路 乘性更新规则由 Lee 和 Seung (2001) 提出，其核心思想是： 使用梯度下降的框架，但将学习率选择为一个与当前参数成比例的特定值，使得更新步骤变为乘法形式。 这种选择能自动确保非负性：如果初始值非负，则更新后仍保持非负。 我们先分别对 \( \mathbf{W} \) 和 \( \mathbf{H} \) 推导。 3. 对 \( \mathbf{H} \) 的更新规则推导 固定 \( \mathbf{W} \)，考虑损失函数关于 \( \mathbf{H} \) 的梯度。设 \( \mathbf{A} = \mathbf{W} \mathbf{H} \)，则： \[ \frac{\partial D}{\partial H_ {ab}} = \frac{\partial}{\partial H_ {ab}} \left[ \frac{1}{2} \sum_ {i,j} (V_ {ij} - A_ {ij})^2 \right ]. \] 注意 \( A_ {ij} = \sum_ k W_ {ik} H_ {kj} \)，所以： \[ \frac{\partial A_ {ij}}{\partial H_ {ab}} = \begin{cases} W_ {ia}, & \text{if } j = b \\ 0, & \text{otherwise} \end{cases}. \] 因此： \[ \frac{\partial D}{\partial H_ {ab}} = \sum_ i (A_ {ib} - V_ {ib}) W_ {ia} = \left[ \mathbf{W}^T (\mathbf{W} \mathbf{H} - \mathbf{V}) \right] {ab}. \] 记梯度矩阵为： \[ \nabla {\mathbf{H}} D = \mathbf{W}^T (\mathbf{W} \mathbf{H} - \mathbf{V}). \] 梯度下降更新为： \[ H_ {ab} \leftarrow H_ {ab} - \eta_ {ab} \cdot \frac{\partial D}{\partial H_ {ab}}, \] 其中 \( \eta_ {ab} > 0 \) 是学习率。 为了得到乘性更新，我们选择学习率为： \[ \eta_ {ab} = \frac{H_ {ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H}) {ab}}. \] 注意分母 \( (\mathbf{W}^T \mathbf{W} \mathbf{H}) {ab} \) 非负（因为所有矩阵非负）。 代入更新公式： \[ H_ {ab} \leftarrow H_ {ab} - \frac{H_ {ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H}) {ab}} \cdot \left[ \mathbf{W}^T (\mathbf{W} \mathbf{H} - \mathbf{V}) \right] {ab}. \] 整理： \[ H_ {ab} \leftarrow H_ {ab} \cdot \frac{(\mathbf{W}^T \mathbf{V}) {ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H}) {ab}}. \] 这就是 \( \mathbf{H} \) 的乘性更新规则 。 非负性保持 ：如果初始 \( H_ {ab} > 0 \)，且 \( (\mathbf{W}^T \mathbf{V}) {ab} \ge 0 \)（因为 \( \mathbf{W}, \mathbf{V} \) 非负），分母 \( (\mathbf{W}^T \mathbf{W} \mathbf{H}) {ab} > 0 \)，则更新后 \( H_ {ab} \) 仍非负。若某元素 \( H_ {ab} = 0 \)，则更新后仍为 0（因为乘以一个因子）。 4. 对 \( \mathbf{W} \) 的更新规则推导 固定 \( \mathbf{H} \)，类似地求梯度。由对称性，损失函数对 \( \mathbf{W} \) 的梯度为： \[ \nabla_ {\mathbf{W}} D = (\mathbf{W} \mathbf{H} - \mathbf{V}) \mathbf{H}^T. \] 选择学习率： \[ \eta_ {ij} = \frac{W_ {ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T) {ij}}. \] 梯度下降更新： \[ W {ij} \leftarrow W_ {ij} - \frac{W_ {ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T) {ij}} \cdot \left[ (\mathbf{W} \mathbf{H} - \mathbf{V}) \mathbf{H}^T \right] {ij}. \] 整理得： \[ W_ {ij} \leftarrow W_ {ij} \cdot \frac{(\mathbf{V} \mathbf{H}^T) {ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T) {ij}}. \] 这就是 \( \mathbf{W} \) 的乘性更新规则 。 5. 算法步骤总结 初始化 ：随机生成非负矩阵 \( \mathbf{W}^{(0)} \) 和 \( \mathbf{H}^{(0)} \)，或使用其他非负初始化方法。 迭代更新 （直到收敛或达到最大迭代次数）： 更新 \( \mathbf{H} \)： \[ H_ {ab} \leftarrow H_ {ab} \cdot \frac{(\mathbf{W}^T \mathbf{V}) {ab}}{(\mathbf{W}^T \mathbf{W} \mathbf{H}) {ab}}, \quad \forall a,b. \] 更新 \( \mathbf{W} \)： \[ W_ {ij} \leftarrow W_ {ij} \cdot \frac{(\mathbf{V} \mathbf{H}^T) {ij}}{(\mathbf{W} \mathbf{H} \mathbf{H}^T) {ij}}, \quad \forall i,j. \] 输出 ：分解矩阵 \( \mathbf{W} \) 和 \( \mathbf{H} \)。 6. 乘性更新规则的性质 非负性保持 ：如上所述，更新公式只包含非负矩阵的乘除，因此只要初始值非负，迭代中永远非负。 单调性 ：可以证明，在更新规则下，损失函数 \( D \) 是单调不增的（通常下降）。这源于更新规则实际上是对损失函数在某个辅助函数上的最小化（利用 MM 算法 或 辅助函数法 ）。 收敛性 ：迭代生成的序列会收敛到一个稳定点（通常是一个局部最小值或鞍点）。但可能收敛缓慢，且对初始值敏感。 计算简便 ：只需矩阵乘法和逐元素除法，易于实现。 7. 直观理解与示例 直观解释 ：更新规则将当前估计 \( \mathbf{W} \mathbf{H} \) 与目标 \( \mathbf{V} \) 进行比较，通过比例因子调整。例如，若 \( (\mathbf{W}^T \mathbf{V}) {ab} \) 较大（表示 \( \mathbf{W} \) 的第 \( a \) 列与 \( \mathbf{V} \) 的第 \( b \) 列相关性高），则增加 \( H {ab} \)；反之则减小。 示例 ：假设 \( \mathbf{V} \) 是文档-词矩阵（每列为一个文档的词频向量），NMF 可解释为： \( \mathbf{W} \) 的每一列是一个“主题”的词分布， \( \mathbf{H} \) 的每一列是一个文档的主题权重。 乘性更新可视为不断调整主题和权重，以更好地拟合观测数据。 总结 非负矩阵分解的乘性更新规则提供了一种简单有效的方法，在保持非负约束的同时最小化欧几里得损失。其推导基于梯度下降结合特定的学习率选择，确保了迭代中的非负性和损失函数下降。该算法广泛应用于文本挖掘、图像分析和推荐系统等领域，是处理非负数据分解的重要工具。