算法视角下的机器学习 2

非负矩阵分解 Nonnegative Matrix Factorization

本章中，我们会探索非负矩阵分解问题。首先与我们更熟悉的奇异值分解 singular value decomposition 比较一下会很有帮助。在最糟糕的情况下，非负矩阵分解问题是 NP 难的（说真的，你还期望怎样呢？），但我们会做域特定假设 domain- specific assumption（称为可分性 separability），这会允许我们为其中的一种重要特例给出可证明的算法。之后我们把算法应用在了主题模型参数的学习问题中。这会是我们第一个案例研究：如何在面对计算棘手时不退缩，并找到方法绕过去。

2.1 引言

为了更好地理解非负矩阵分解问题背后的动机以及在应用中很有用的原因，首先介绍奇异值分解然后再比较两者会有所帮助。最后，我们会在本节后面将两者应用于文本分析中。

奇异值分解

奇异值分解（SVD）是线性代数中最有用的工具之一。假设有一 $m \times n$ 的矩阵 $\boldsymbol M$ ，其奇异值分解写作：

$\boldsymbol M = \boldsymbol U \boldsymbol\Sigma \boldsymbol V^{\top}$

其中 $\boldsymbol U$ 和 $\boldsymbol V$ 是标准正交矩阵， $\boldsymbol\Sigma$ 是一个只有对角线元素非零的方阵，并且元素都非负。或者可以写成：

$\boldsymbol M = \sum_{i=1}^r \sigma_i \boldsymbol u_i \boldsymbol v_i^{\top}$

其中 $\boldsymbol u_i$ 是 $\boldsymbol U$ 的第 $i$ 列， $\boldsymbol v_i$ 是 $\boldsymbol V$ 的第 $i$ 列， $\sigma_i$ 是 $\boldsymbol\Sigma$ 对角线的第 $i$ 个元素。

在整个章节中，我们将采用以下约定： $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$ 。在这种情况下， $\boldsymbol M$ 的秩恰好为 $r$ 。

在整个章节中，我们将有机会使用这种分解以及（可能更熟悉的）特征分解 eigendecomposition。假设有一 $m \times n$ 的矩阵 $\boldsymbol M$ ，其特征分解可以写成：

$\boldsymbol M = \boldsymbol P \boldsymbol D \boldsymbol P^{-1}$

其中 $\boldsymbol D$ 是对角矩阵。目前，要记住的重要事实有：

（1）存在性：每个矩阵都有其奇异值分解，即使它是方阵。反过来说，一个矩阵要能做特征分解则必须是方阵。即使这样，也并不是所有方阵都能对角化，但 $\boldsymbol M$ 能够对角化的一个充分条件是所有它的特征值都是相异的。

（2）算法：所有这些分解都能被高效计算。计算奇异值分解的最好的通用算法能在 $O(mn^2)$ 时间内完成（如果 $m \geq n$ ）。对于稀疏矩阵另有更快的算法。有算法能在 $O(n^3)$ 时间内计算特征分解，也有基于快速矩阵相乘的进一步改进，即便尚不清楚这些算法是否一样稳定实用。

（3）唯一性：奇异值分解是唯一的，当且仅当其奇异值是相异的。类似地，特征分解是唯一的，当且仅当其特征值是相异的。有些情况下，我们只需要非零的奇异值/特征值是相异的，因为我们可以忽略其他值。

两个应用

奇异值分解的两个最重要的性质是它可以用于寻找最佳的 $k$ -秩（rank）近似以及降维。接下来我们会探索这些。首先，我们正式地定义最佳的 $k$ -秩近似意味着什么。一种方法是使用 Frobenius 范数：

$\text{定义 2.1.1（Frobenius 范数）}\vert \vert \boldsymbol M \vert \vert _F = \sqrt{\sum\nolimits_{i,j} M_{i,j}^2}$

很容易看出，Frobenius 范数是旋转不变的。例如，接下来把 $\boldsymbol M$ 的每一列视为一个向量。一个矩阵的 Frobenius 范数的平方等于其列的范数的平方的累加和。因此左乘一个正交矩阵会维持它每列的范数不变。同样右乘一个正交矩阵结论也成立（但相应地使用行）。这种不变性使我们可以给出 Frobenius 范数的另一种非常有用的描述：

$\vert \vert \boldsymbol M \vert \vert _F = \vert \vert \boldsymbol U^{\top} \boldsymbol M \boldsymbol V \vert \vert _F = \vert \vert \boldsymbol \Sigma \vert \vert _F = \sqrt{ \sum \sigma_i^2 }$

第一个等式就是所有动作发生的地方，利用了上面证实的旋转不变性。

算法视角下的机器学习 2

非负矩阵分解 Nonnegative Matrix Factorization

2.1 引言

奇异值分解

两个应用

推荐阅读更多精彩内容