非负矩阵分解（Non-negative Matrix Factorization, NMF）的交替最小二乘（Alternating Least Squares, ALS）优化过程
字数 2673 2025-12-14 01:31:43

非负矩阵分解（Non-negative Matrix Factorization, NMF）的交替最小二乘（Alternating Least Squares, ALS）优化过程

题目描述
非负矩阵分解（NMF）旨在将一个非负矩阵 \(V \in \mathbb{R}^{m \times n}_{\ge 0}\) 近似分解为两个非负矩阵的乘积 \(W H\)，其中 \(W \in \mathbb{R}^{m \times k}_{\ge 0}\)，\(H \in \mathbb{R}^{k \times n}_{\ge 0}\)，且 \(k \ll \min(m, n)\)。目标是使重构误差 \(\| V - WH \|_F^2\) 最小化。交替最小二乘（ALS）是一种常用优化方法，通过交替固定一个矩阵、优化另一个矩阵来求解，同时保证非负性约束。本题目将详细讲解NMF的ALS优化过程，包括目标函数构造、更新规则推导、迭代步骤及收敛性考虑。

解题过程

  1. 问题形式化
    给定非负矩阵 \(V\)，寻找非负矩阵 \(W\) 和 \(H\) 以最小化平方Frobenius范数损失：

\[ \min_{W \ge 0, H \ge 0} f(W, H) = \frac{1}{2} \| V - WH \|_F^2 \]

其中 \(\| \cdot \|_F\) 是Frobenius范数，\(\frac{1}{2}\) 是为了后续求导方便。这是一个非凸优化问题，但若固定 \(W\) 或 \(H\)，子问题关于另一变量是凸的。

  1. 交替优化框架
    ALS的核心思想是交替优化：

    • 固定 \(H\)，更新 \(W\) 以最小化 \(f(W, H)\)；
    • 固定 \(W\)，更新 \(H\) 以最小化 \(f(W, H)\)。
      每次子问题是一个带非负约束的二次规划问题。

  2. 固定 \(H\) 优化 \(W\) 的推导
    当 \(H\) 固定时，目标函数关于 \(W\) 的梯度为：

\[ \nabla_W f = (WH - V)H^T \]

在无约束情况下，令梯度为零可得最小二乘解：

\[ W \leftarrow V H^T (H H^T)^{-1} \]

但此解可能包含负值。为保证非负性，采用投影梯度法：在每次梯度下降后，将负值置零。然而标准的ALS使用乘法更新规则，可自然地保持非负性。其推导基于梯度下降结合自适应步长：

  • 将梯度分解为正向部分和负向部分：

\[ \nabla_W f = [W H H^T] - [V H^T] = \nabla^+ - \nabla^- \]

 其中 $ \nabla^+ = W H H^T $，$ \nabla^- = V H^T $ 均为非负矩阵。
  • 采用自适应步长矩阵 \(\eta_{ij} = \frac{W_{ij}}{(W H H^T)_{ij}}\) 进行梯度下降：

\[ W_{ij} \leftarrow W_{ij} - \eta_{ij} [\nabla_W f]_{ij} = W_{ij} \cdot \frac{(V H^T)_{ij}}{(W H H^T)_{ij}} \]

 此乘法更新自动保持非负性（因所有项非负），且当梯度为零时更新停止。
  1. 固定 \(W\) 优化 \(H\) 的推导
    同理，固定 \(W\) 时，目标函数关于 \(H\) 的梯度为：

\[ \nabla_H f = W^T (W H - V) \]

分解梯度：

\[ \nabla_H f = [W^T W H] - [W^T V] = \nabla^+ - \nabla^- \]

通过自适应步长 \(\eta_{ij} = \frac{H_{ij}}{(W^T W H)_{ij}}\) 得乘法更新：

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

  1. 完整ALS迭代步骤
    a. 初始化：随机生成非负初始矩阵 \(W^{(0)}\) 和 \(H^{(0)}\)，或使用SVD分解结果取绝对值。
    b. 交替更新（迭代 \(t = 1, 2, \dots\) 直到收敛）：
    • 固定 \(H^{(t-1)}\)，更新 \(W^{(t)}\)：

\[ W_{ij}^{(t)} = W_{ij}^{(t-1)} \cdot \frac{(V (H^{(t-1)})^T)_{ij}}{(W^{(t-1)} H^{(t-1)} (H^{(t-1)})^T)_{ij}} \]

  - 固定 $ W^{(t)} $，更新 $ H^{(t)} $：

\[ H_{ij}^{(t)} = H_{ij}^{(t-1)} \cdot \frac{((W^{(t)})^T V)_{ij}}{((W^{(t)})^T W^{(t)} H^{(t-1)})_{ij}} \]

c. 收敛判断：通常设置最大迭代次数，或当目标函数变化 \(|f^{(t)} - f^{(t-1)}| / f^{(t-1)} < \epsilon\) 时停止。

  1. 算法特性与注意事项
    • 非负性保持：乘法更新中所有分子分母均为非负，且初始化非负，因此迭代中 \(W, H\) 始终非负。
    • 收敛性：目标函数在每次更新后非增，但可能收敛到局部极小点（因问题非凸）。
    • 数值稳定性：分母可能接近零，需添加小常数 \(\delta\)（如 \(10^{-9}\)）防止除零：

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

  • 尺度不确定性：分解不唯一，可对 \(W\) 列归一化，相应调整 \(H\) 的行。
  • 与梯度下降关系：乘法更新可视为带自适应步长的梯度下降，步长自动选择保证非负性和单调递减。
  1. 应用示例
    在文本主题模型中，\(V\) 是词-文档矩阵（元素为词频），分解后 \(W\) 的列表示主题-词分布，\(H\) 的行表示文档-主题分布。ALS优化可提取可解释的非负主题结构。
非负矩阵分解（Non-negative Matrix Factorization, NMF）的交替最小二乘（Alternating Least Squares, ALS）优化过程 题目描述 非负矩阵分解（NMF）旨在将一个非负矩阵 \( V \in \mathbb{R}^{m \times n} {\ge 0} \) 近似分解为两个非负矩阵的乘积 \( W H \)，其中 \( W \in \mathbb{R}^{m \times k} {\ge 0} \)，\( H \in \mathbb{R}^{k \times n}_ {\ge 0} \)，且 \( k \ll \min(m, n) \)。目标是使重构误差 \( \| V - WH \|_ F^2 \) 最小化。交替最小二乘（ALS）是一种常用优化方法，通过交替固定一个矩阵、优化另一个矩阵来求解，同时保证非负性约束。本题目将详细讲解NMF的ALS优化过程，包括目标函数构造、更新规则推导、迭代步骤及收敛性考虑。 解题过程 问题形式化 给定非负矩阵 \( V \)，寻找非负矩阵 \( W \) 和 \( H \) 以最小化平方Frobenius范数损失： \[ \min_ {W \ge 0, H \ge 0} f(W, H) = \frac{1}{2} \| V - WH \|_ F^2 \] 其中 \( \| \cdot \|_ F \) 是Frobenius范数，\( \frac{1}{2} \) 是为了后续求导方便。这是一个非凸优化问题，但若固定 \( W \) 或 \( H \)，子问题关于另一变量是凸的。 交替优化框架 ALS的核心思想是交替优化： 固定 \( H \)，更新 \( W \) 以最小化 \( f(W, H) \)； 固定 \( W \)，更新 \( H \) 以最小化 \( f(W, H) \)。 每次子问题是一个带非负约束的二次规划问题。 固定 \( H \) 优化 \( W \) 的推导 当 \( H \) 固定时，目标函数关于 \( W \) 的梯度为： \[ \nabla_ W f = (WH - V)H^T \] 在无约束情况下，令梯度为零可得最小二乘解： \[ W \leftarrow V H^T (H H^T)^{-1} \] 但此解可能包含负值。为保证非负性，采用投影梯度法：在每次梯度下降后，将负值置零。然而标准的ALS使用乘法更新规则，可自然地保持非负性。其推导基于梯度下降结合自适应步长： 将梯度分解为正向部分和负向部分： \[ \nabla_ W f = [ W H H^T] - [ V H^T ] = \nabla^+ - \nabla^- \] 其中 \( \nabla^+ = W H H^T \)，\( \nabla^- = V H^T \) 均为非负矩阵。 采用自适应步长矩阵 \( \eta_ {ij} = \frac{W_ {ij}}{(W H H^T) {ij}} \) 进行梯度下降： \[ W {ij} \leftarrow W_ {ij} - \eta_ {ij} [ \nabla_ W f] {ij} = W {ij} \cdot \frac{(V H^T) {ij}}{(W H H^T) {ij}} \] 此乘法更新自动保持非负性（因所有项非负），且当梯度为零时更新停止。 固定 \( W \) 优化 \( H \) 的推导 同理，固定 \( W \) 时，目标函数关于 \( H \) 的梯度为： \[ \nabla_ H f = W^T (W H - V) \] 分解梯度： \[ \nabla_ H f = [ W^T W H] - [ W^T V ] = \nabla^+ - \nabla^- \] 通过自适应步长 \( \eta_ {ij} = \frac{H_ {ij}}{(W^T W H) {ij}} \) 得乘法更新： \[ H {ij} \leftarrow H_ {ij} \cdot \frac{(W^T V) {ij}}{(W^T W H) {ij}} \] 完整ALS迭代步骤 a. 初始化 ：随机生成非负初始矩阵 \( W^{(0)} \) 和 \( H^{(0)} \)，或使用SVD分解结果取绝对值。 b. 交替更新 （迭代 \( t = 1, 2, \dots \) 直到收敛）： 固定 \( H^{(t-1)} \)，更新 \( W^{(t)} \)： \[ W_ {ij}^{(t)} = W_ {ij}^{(t-1)} \cdot \frac{(V (H^{(t-1)})^T) {ij}}{(W^{(t-1)} H^{(t-1)} (H^{(t-1)})^T) {ij}} \] 固定 \( W^{(t)} \)，更新 \( H^{(t)} \)： \[ H_ {ij}^{(t)} = H_ {ij}^{(t-1)} \cdot \frac{((W^{(t)})^T V) {ij}}{((W^{(t)})^T W^{(t)} H^{(t-1)}) {ij}} \] c. 收敛判断 ：通常设置最大迭代次数，或当目标函数变化 \( |f^{(t)} - f^{(t-1)}| / f^{(t-1)} < \epsilon \) 时停止。 算法特性与注意事项 非负性保持 ：乘法更新中所有分子分母均为非负，且初始化非负，因此迭代中 \( W, H \) 始终非负。 收敛性 ：目标函数在每次更新后非增，但可能收敛到局部极小点（因问题非凸）。 数值稳定性 ：分母可能接近零，需添加小常数 \( \delta \)（如 \( 10^{-9} \)）防止除零： \[ W_ {ij} \leftarrow W_ {ij} \cdot \frac{(V H^T) {ij}}{(W H H^T) {ij} + \delta} \] 尺度不确定性 ：分解不唯一，可对 \( W \) 列归一化，相应调整 \( H \) 的行。 与梯度下降关系 ：乘法更新可视为带自适应步长的梯度下降，步长自动选择保证非负性和单调递减。 应用示例 在文本主题模型中，\( V \) 是词-文档矩阵（元素为词频），分解后 \( W \) 的列表示主题-词分布，\( H \) 的行表示文档-主题分布。ALS优化可提取可解释的非负主题结构。