非负矩阵分解 | 降维Ⅲ

原始论文：Algorithms for Non-negative Matrix Factorization - Daniel D.Lee、H. Sebastian Seung

问题描述

传统的非负矩阵分解（Non-negative matrix factorization, NMF）问题可以描述如下：
对于给定的一个非负矩阵$\mathbf V\in\Bbb R_+^{n\times m}$，将其分解为非负矩阵$\mathbf W\in\Bbb R_+^{n\times d}$ 和非负矩阵$\mathbf H\in\Bbb R_+^{d\times m}$ 的乘积，即$\mathbf{V=W\cdot H}$。

事实上，上式中的等号很难成立（目前已有的解法得不到精确解），所以 $\mathbf W$ 和 $\mathbf H$ 相乘只能尽量逼近 $\mathbf V$，即$\mathbf{V\approx WH=\tilde{V}}$。

非负矩阵分解可理解为：原始矩阵$\mathbf V$ 的列向量是通过$\mathbf W$ 中所有列向量加权求和得到的，而权重系数就是$\mathbf H$ 对应列向量的元素。因此称$\mathbf W$ 为基矩阵，$\mathbf H$ 为系数矩阵。

一般情况下$d$ 的选择要比$m,n$ 小得多，即满足$d \ll\min(m,n)$ ，通常要求$(m+n)d\lt mn$。

从数据科学的角度出发，非负矩阵$\mathbf V$ 代表着样本数是$m$ 的样本，每个样本的特征数（维度）是$n$。通过 NMF 我们就可以利用基矩阵$\mathbf W$ 代替原始矩阵，从而实现降维（降到了$d$ 维），同时也实现了对原始数据的特征提取，这减少了存储空间和计算机资源。

这种分解有利于发现潜在的特征和模式，因为非负性能够保持数据的可加性和解释性，从而在多个应用域中有着重要的意义。

求解方法

NMF的求解实际上就是一个最优化问题，而且是一个NP问题。其目标函数根据不同的假设也有很多种不同的定义，其中应用最广泛的是欧氏距离和 KL散度。

欧氏距离

假设噪声矩阵$\mathbf {E=V-\tilde{V}=V-WH}$ 服从于高斯分布，那么最大化其似然函数就等价于最小化$\mathbf V$ 和$\tilde{\mathbf V}$ 之间的欧氏距离。矩阵的欧氏距离在数学上可以用 Frobenius范数 表示，定义为矩阵所有元素的平方和。

Frobenius范数的优化目标形式化为：

$$J(\mathbf{W}, \mathbf{H})=\min_{\mathbf{W}, \mathbf{H}} \| \mathbf{V} - \mathbf{W}\mathbf{H} \|_F^2 = \min_{\mathbf{W}, \mathbf{H}} \sum_{i,j}(v_{ij} - (WH)_{ij})^2$$

其中，下标$F$ 表示Frobenius范数，$v_{ij}$ 是矩阵$\mathbf{V}$ 中的元素，而$(WH)_{ij}$ 是矩阵乘积$\mathbf{W}\mathbf{H}$ 中的元素。

KL散度

如果噪声矩阵服从于泊松分布，那么损失函数正好是KL散度：

$$J(\mathbf{W}, \mathbf{H})=\min_{\mathbf{W}, \mathbf{H}} KL(\mathbf{V}||\mathbf{W}\mathbf{H}) = \min_{\mathbf{W}, \mathbf{H}} \sum_{i,j}\left( v_{ij}\log\frac{v_{ij}}{(WH)_{ij}} - v_{ij} + (WH)_{ij} \right)$$

其中$KL(\cdot||\cdot)$ 表示 Kullback-Leibler 散度。

梯度下降修正

根据梯度下降法的思想，为了最小化损失函数，我们很容易得出，应该在每步迭代时计算损失函数$J(\mathbf{W}, \mathbf{H})$ 关于$\mathbf{W}$ 和$\mathbf{H}$ 的梯度：

$$\nabla_{\mathbf{W}} J = \frac{\partial J}{\partial \mathbf{W}}, \quad \nabla_{\mathbf{H}} J = \frac{\partial J}{\partial \mathbf{H}}$$

然后使用下面的规则对其进行更新：

$$\begin{aligned} \mathbf{W} &\leftarrow \mathbf{W} - \mu \nabla_{\mathbf{W}} J,\\ \mathbf{H} &\leftarrow \mathbf{H} - \eta \nabla_{\mathbf{H}} J \end{aligned}$$

其中$\mu,\eta$ 是学习率，用于控制每次迭代中参数更新的步长。

利用梯度下降法求解NMF问题固然有效，但存在一个关键问题是难以保证更新后的$\mathbf{W}$ 和$\mathbf{H}$ 仍然满足非负条件，并且还要选择合适的学习率来调整算法的收敛性能。

实际上，我们可以通过设计学习率的表达式来修正这个问题。为了方便展示，我们将梯度下降法从上面提到的矩阵形式写成元素形式：

$$\begin{aligned} w_{ik}\leftarrow w_{ik}-\mu_{ik}\frac{\partial J(\mathbf{W,H})}{\partial w_{ik}}\\ h_{kj}\leftarrow h_{kj}-\eta_{kj}\frac{\partial J(\mathbf{W,H})}{\partial h_{kj}}\\ \end{aligned}$$

如何是以Frobenius范数作为目标函数，则：

$$\begin{aligned} \frac{\partial J(\mathbf{W,H})}{\partial w_{ik}}&=-\left[(\mathbf{V-WH})\mathbf H^\top\right]_{ik}\\ \frac{\partial J(\mathbf{W,H})}{\partial h_{kj}}&=-\left[\mathbf W^\top(\mathbf{V-WH})\right]_{kj}\\ \end{aligned}$$

由于非负矩阵的乘积还是非负矩阵，我们可以调整学习率从而将梯度下降法变为乘法算法。令：

$$\mu_{ik}=\frac{w_{ik}}{[\mathbf{WHH}^\top]_{ik}},\quad \eta_{kj}=\frac{h_{kj}}{[\mathbf W^\top\mathbf{WH}]_{ik}}$$

最终更新公式可写为：

$$\begin{aligned} w_{ik} &\leftarrow w_{ik} \frac{[\mathbf{V} \mathbf{H}^\top]_{ik}}{[\mathbf{W} \mathbf{H} \mathbf{H}^\top]_{ik}}\\ h_{kj} &\leftarrow h_{kj} \frac{[\mathbf{W}^\top \mathbf{V}]_{kj}}{[\mathbf{W}^\top \mathbf{W} \mathbf{H}]_{kj}} \end{aligned}$$

收敛性证明可以参考：Lee D D, Seung H S. Algorithms for Non-negative Matrix Factorization[C]// NIPS. 2000:556–562.

拉格朗日数乘

另一个更朴素的想法是通过拉格朗日乘子法应对这种有约束的优化问题。

$$\begin{aligned} \min_{\mathbf{W}, \mathbf{H}} \| \mathbf{V} - \mathbf{W}\mathbf{H} \|_F^2\\\\ s.t.\quad \mathbf{W}\in\Bbb R_{+},\mathbf{H}\in\Bbb R_{+} \end{aligned}$$

其无约束的对偶拉格朗日函数为：

$$\mathcal L=\sum_{i=1}^m\sum_{j=1}^n\left(v_{ij}-\sum_{k=1}^dw_{ik}h_{kj}\right)^2-\sum_{i=1}^m\sum_{k=1}^d\lambda_{ik}w_{ik}-\sum_{k=1}^d\sum_{j=1}^n\lambda_{kj}w_{kj}$$

分别求导，利用 KKT 互补松弛条件 blabla

非负矩阵分解（NMF）迭代公式推导证明 - 知乎 (zhihu.com)

交替最小二乘

由于ALS在每一步都能保证成本函数的单调递减，所以它通常具有较好的收敛性。但是，需要注意的是，因为NMF问题是非凸的，数学上ALS并不能保证找到全局最优解，它可能会收敛到局部最优。此外，这种方法对初始值敏感，不同的初始化可能会导致不同的结果。

待更：https://www.cnblogs.com/xingshansi/p/6679325.html

sklearn实现

from sklearn.decomposition import NMF

nmf = NMF(n_components=2,  # 降维后的维数，默认保留全部特征
          init=None,  # W H 的初始化方法，包括'random' | 'nndsvd'(默认) |  'nndsvda' | 'nndsvdar' | 'custom'.
          solver='cd',  # 'cd' | 'mu'
          beta_loss='frobenius',  # {'frobenius', 'kullback-leibler', 'itakura-saito'}，一般默认就好
          tol=1e-4,  # 停止迭代的极限条件
          max_iter=200,  # 最大迭代次数
          random_state=None,
          alpha=0.,  # 正则化参数
          l1_ratio=0.,  # 正则化参数
          verbose=0,  # 冗长模式
          shuffle=False  # 针对"cd solver"
          )

W = nmf.fit_transform(X) #基矩阵
H = nmf.components_ #系数矩阵

err = nmf.reconstruction_err_ #重构误差
errs = nmf.residuals_ #每步迭代的残差

与PCA的区别

虽然NMF和PCA都用于降维和特征提取，但它们的基本假设，约束和应用有所不同。

假设和约束

• 非负性约束： NMF 的基矩阵和系数矩阵具有非负性约束。此约束使 NMF 特别适用于无法用负值准确表示的数据，例如图像和文本数据。
• 正交性与非负性： PCA寻求最大化方差的正交基（主成分），而NMF旨在找到模式的加性非负组合。这种约束差异导致了NMF中包含了可加性的特征部分的表示，而PCA中的则是原数据总体的表示。通常用于降噪、可视化和压缩。在对数据的固有结构没有明确的先验知识时比较有用。

可解释性

• NMF 中的可解释性：NMF 中的非负性约束通常会导致更可解释的表示，因为算法的基于部分的性质与数据的性质非常吻合。在了解基础组件至关重要的情况下，这可能是有利的。

• PCA可解释性：虽然 PCA 提供了有效的降维，但主成分可能并不总是与数据中的直观特征相对应。它们是原始要素的线性组合，可能更难直接解释。

通过上图中的面部特征提取的例子，我们得以领略NMF处理数据的方式。

最左边的大矩阵由一系列的小图组成，这些小图是分析数据库中包含的2429个人脸图像的结果，每幅图像由19×19个像素组成。
传统方法（VQ分解）中这样的小图是一幅完整的人脸图像，但是在NMF方法中，每个小图是通过一组基图像乘以一个权重矩阵而产生的面部特征图，经过这样处理的每幅小图像恰好表示了诸如“鼻子”、“嘴巴”、“眼睛”等人脸局部概念特征，这便大大压缩了存放的图像数据量。

事实上Lee和Seung在他们的论文中更深入地指出，与人类识别事物的过程相似，NMF也是一种优化的机制，近似于我们的脑分析和存储人脸数据的过程。这个例子中，原图像表示这些局部特征的加权组合，这与人类思维中“局部构成整体”的概念是相吻合的。因此，NMF算法似乎体现了一种智能行为。

附：收敛唯一性证明

Lee D D, Seung H S. Algorithms for Non-negative Matrix Factorization[C]// NIPS. 2000:556–562.

待更：http://www.xiongfuli.com/机器学习/2016-01/NMF.html

参考

1. 非负矩阵分解（NMF）迭代公式推导证明 - 知乎
2. 【机器学习】NMF(非负矩阵分解)-CSDN博客
3. 非负矩阵分解（3）：拉格朗日乘子法求解 - LeeLIn
4. Non-negative matrix factorization (NMF) vs Principal Component Analysis (PCA)
5. 非负矩阵分解 - 熊伏枥个人空间
6. 文本主题模型之非负矩阵分解(NMF) - 刘建平Pinard - 博客园 (cnblogs.com)