非负矩阵分解(NMF)的乘法更新规则与非负约束保证

非负矩阵分解（NMF）的目标是把一个非负矩阵 $V$ 分解成两个低秩非负矩阵 $W$ 和 $H$，使得 $V \approx WH$。核心难点有两点：如何高效求解（乘法更新规则），以及如何始终保证分解结果是非负的。下面直接拆解这两个问题。

1. 定义问题与损失函数

确定输入：给定一个大小为 $m \times n$ 的非负矩阵 $V$，所有元素 $\ge 0$。
设定目标：寻找两个非负矩阵 $W$（大小 $m \times r$）和 $H$（大小 $r \times n$），其中 $r$ 是预定秩（$r \ll \min(m,n)$），使得 $V \approx WH$。
选择损失函数：最常用是欧几里得距离的平方（Frobenius范数平方）：

$$F = \frac{1}{2} \| V - WH \|_F^2 = \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^n (V_{ij} - (WH)_{ij})^2$$

要求：保持 $W \ge 0$ 和 $H \ge 0$ 作为硬约束。

使用梯度下降时，如果采用标准减法更新（例如 $W \leftarrow W - \eta \nabla_W F$），无法保证更新后的 $W$ 仍是非负的。乘法更新规则通过将学习率 $\eta$ 巧妙设计为与当前值成正比的项，将减法转化为逐元素乘法，从而自动保持非负性。

计算梯度：
- 对 $W$ 的梯度：$\nabla_W F = (WH - V) H^\top$
- 对 $H$ 的梯度：$\nabla_H F = W^\top (WH - V)$
构造乘法更新：
- 将减法更新 $W \leftarrow W - \eta_W \odot \nabla_W F$ 中的学习率 $\eta_W$ 设为 $\eta_W = \frac{W}{W H H^\top}$（逐元素除法），得到：
$$W \leftarrow W \odot \frac{V H^\top}{W H H^\top}$$

其中 $\odot$ 表示逐元素相乘，分数线表示逐元素相除。
- 类似地，对于 $H$ 取 $\eta_H = \frac{H}{W^\top W H}$，得到：
$$H \leftarrow H \odot \frac{W^\top V}{W^\top W H}$$
解释：因为 $V$、$W$、$H$ 所有元素非负，所以乘法更新式中的分子和分母都非负。整个更新过程只涉及乘法、除法、加法，没有减法，因此只要初始 $W$ 和 $H$ 非负，更新后仍非负。

初始条件：随机初始化 $W$ 和 $H$ 为所有元素大于0的矩阵（例如均匀分布 $[0,1]$）。
迭代过程：执行以下两步直至收敛：
- 更新 $W$：$W \leftarrow W \odot \frac{V H^\top}{W H H^\top}$
- 更新 $H$：$H \leftarrow H \odot \frac{W^\top V}{W^\top W H}$
由于每一步只做乘法、除法、加法，所有结果自动 $\ge 0$（分母可能出现零？实际操作会在分母上加一个极小正数如 1e-10 防止除零）。
为什么不是减法？ 传统梯度下降 $W \leftarrow W - \alpha \nabla_W F$ 允许负梯度导致 $W$ 元素变成负数。乘法更新等价于选择了一个自适应学习率，使得步长恰好抵消了梯度中的减法，只剩下正项相乘。

初始化：生成 $W_{init} \in \mathbb{R}^{m \times r}$ 和 $H_{init} \in \mathbb{R}^{r \times n}$，元素为 $[0,1]$ 均匀随机数。
设置参数：定义最大迭代次数 max_iter（如200）和收敛阈值 tol（如 1e-4）。
迭代循环：对于 t=1 到 max_iter：
- 计算 $H$ 的更新因子：factor_H = (W.T @ V) / (W.T @ W @ H + eps)（eps 是极小数如 1e-10）。
- 更新 $H$：$H \leftarrow H \odot factor_H$
- 计算 $W$ 的更新因子：factor_W = (V @ H.T) / (W @ H @ H.T + eps)
- 更新 $W$：$W \leftarrow W \odot factor_W$
- 计算损失：loss = 0.5 * sum((V - W @ H)**2)
- 判断收敛：如果损失变化小于 tol 则停止。
输出结果：返回 $W$ 和 $H$，两者所有元素 $\ge 0$，满足非负约束。

乘法更新规则 的核心公式为：

$$W \leftarrow W \odot \frac{V H^\top}{W H H^\top}, \quad H \leftarrow H \odot \frac{W^\top V}{W^\top W H}$$
非负保证来源于更新式中只有乘法、除法、加法，无减法操作。同时要求初始值 $>0$，避免分母为零。
收敛性：在欧几里得距离下，该规则保证损失函数单调不增，且极限点为驻点（KTT点），证明可参考 Lee & Seung 2001 论文。

直接应用：将上述公式转换为编程语言（ Python + NumPy）即可运行。无需调参学习率，唯一需指定的参数是秩 $r$。