非负矩阵分解算法外文翻译资料

非负矩阵分解算法

原文作者 DD Lee; HS Seung

单位 Lucent Technologies; Massachusetts Institute of Technology

摘要：非负矩阵分解（NMF）先前已被证明是一个有用的多元数据分解。本文分析了两种不同的NMF乘法算法。它们在更新规则中使用的乘法因子略有不同。一种算法可以最小化常规最小平方误差，而另一种算法可以最小化广义Kullback-Leibler散度。两种算法的单调收敛性可以使用类似于用于证明期望最大化算法的收敛性的辅助函数来证明。该算法也可以解释为对角调整梯度下降，其中缩放因子是最佳选择，以确保收敛性。

关键词：非负矩阵分解； 收敛性； 缩放因子； 更新规则

介绍

无监督学习算法，如主成分分析和矢量量化，可以理解为一个不同约束条件下的数据矩阵分解。根据所使用的约束，所得到的因子可以显示出具有非常不同的表征性质。主成分分析只执行一个弱正交约束，导致一个使用取消产生可变性的非常分散的表示[1,2]。另一方面，矢量量化使用硬winnertake-all约束，导致数据聚集成相互独立的原型[3]。我们先前已经表明，非负性是矩阵分解的一个有用约束，可以学习数据的部分表示[4,5]。所学的非负基向量用于分布的，但仍然稀疏的组合，以在重建中产生表现力[6,7]。在这篇文章中，我们详细分析了两个从数据中学习最佳非负因子的数值算法。

非负矩阵分解

我们正式考虑解决以下问题的算法：

非负矩阵分解（NMF） 给出一个非负矩阵，找到非负矩阵因子和，使得

（1）

NMF可以按照以下方式应用于多元数据的统计分析。给定一组多元维数据向量，向量被放置在矩阵中，其中是数据集中的实例数。这个矩阵是近似分解成矩阵和矩阵。通常被选择为小于或，使得和小于原始矩阵。这将导致原始数据矩阵的压缩版本。

公式（1）中的近似值有什么意义？它可以改写列为，其中和是和的对应列。换句话说，每一个数据向量通过的列向量的线性组合来近似，其由的分量加权。因此，可以看作是包含一个为中的数据的线性近似优化的基础。由于相对较少的基向量用来表示许多数据向量，故只有在基向量发现数据中隐含的结构时，才能实现良好的近似。

本次提交的内容不是关于NMF的应用，而是把注意力集中在寻找非负矩阵分解的技术方面。当然，其他类型的矩阵分解已在数值线性代数进行了广泛的研究，但非负性约束使得许多以前的工作不适用于本案例[8]。

在这里，我们讨论了两种基于和迭代更新的NMF算法。因为这些算法很容易编码和使用，我们发现它们在实际应用中非常有用。其他算法可能在整体计算时间内效率更高，但实现起来可能相当困难。与我们的算法类似，其中只有一个因素被改编成以前已被用于发射层析成像和天文图像的反卷积[9,10,11]。

在我们的算法的每次迭代中，或的新值是通过将当前值乘以依赖于（1）的近似质量的一些因子来发现的。我们证明了随着这些乘法更新规则的应用，近似的质量单调提高。实际上，这意味着更新规则的重复迭代被保证收敛到局部最优矩阵分解。

成本函数

为了找到近似因式分解，我们首先需要定义量化近似质量的成本函数。这样的成本函数可以用两个非负矩阵和之间的距离来构造。一个有用的测度就是和之间欧几里德距离的平方[12]，

（2）

下限为零，并且当且仅当时明显消失。

另一个有用的措施是

（3）

像欧氏距离一样，这个值也是下界为零，并且当且仅当时才消失，但它不能被称为“距离”，因为它在和是非对称的，所以我们将它称为“散度”。当时，它减少到Kullback Leibler散度或相对熵，使得和可以作为归一化的概率分布。

我们现在考虑NMF的两种替代形式作为最优化问题：

问题1 对于和，将最小化，其中.

问题2 对于和，将最小化，其中.

尽管函数和只在中是凸的或仅在中是凸的，但它们不是在两个变量中都是凸的。因此，期望一个算法在求全局最小值的情况下解决问题1和2是不现实的。然而，有许多数值优化技术可用于寻找局部最小值。

梯度下降也许是最简单的实现技术，但收敛速度可能会很慢。其他方法如共轭梯度法，至少在局部最小值附近，其收敛速度更快，但比梯度下降更复杂[8]。基于梯度的方法的收敛还具有对步长选择非常敏感的缺点，这对于大型应用来说是非常不方便的。

乘法更新规则

我们发现下面的“乘法更新规则”是解决问题1和2的速度和易实现性之间的一个很好的折衷方案。

定理1 在以下更新规则下，欧氏距离不增加：

（4）

当且仅当和处于距离的一个固定点时，这些更新下的欧氏距离是不变的。

定理2 在以下更新规则下，散度不增加：

（5）

当且仅当和处于散度的稳定点时，这些更新下的散度是不变的。

这些定理的证明在后面的章节中给出。现在，我们注意到每个更新都由一个因子乘以乘法。尤其是，当时，我们可以直接看到这个乘法因子是一致的，因此完美重构必然是更新规则的一个固定点。

乘法与加法更新规则

将这些乘法更新与梯度下降引起的更新进行对比是很有用的[13]。特别地，减少平方距离的简单加法更新可写为

（6）

如果都等于一些小的正数，这相当于传统的梯度下降。只要这个数字足够小，更新应该会降低。

现在如果我们对角缩放变量并设定

（7）

那么我们得到定理1给出的的更新规则。

对于这种分歧，对角调整梯度下降的表现形式

（8）

再次，如果是小而正的，这个更新应该会减少。如果我们现在设置

（9）

那么我们得到定理2给出的的更新规则。

由于我们选择了并不小，似乎并不能保证这种重新调整的梯度下降会导致成本函数下降。令人惊讶的是，这确实如此，正如下一节所示。

收敛的证明

为了证明定理1和2，我们将使用一个类似于期望最大化算法[14,15]中的辅助函数。

定义1 如果满足条件

（10）

则是的辅助函数。

由于下面的引理，辅助函数是一个有用的概念，这也在图1中图解说明。

引理1 如果是一个辅助函数，那么在以下更新下不增加

（11）

证明：

请注意，只有当是局部最小值。如果的导数存在且在的一个小邻域中连续，那么这也意味着导数。因此，通过迭代式（11）中的更新，我们得到一个收敛到目标函数的局部极小值的估计序列：

（12）

我们将通过定义和的适当辅助函数来说明，定理1和2中的更新规则很容易从Eq.（11）中得到。

引理2 如果是对角矩阵

（13）

图1：对于，最小化辅助函数以保证。

那么

（14）

是

（15）

的辅助函数。

证明：由于很明显，我们只需要证得。要做到这一点，我们将

（16）

和公式（14）进行比较，发现等价于

（17）

为了证明正半定，考虑矩阵^[1]：

（18）

这仅仅是的重新缩放。那么是半正定的，当且仅当是半正定的，并且

（23）

（22）

（21）

（20）

（19）

现在我们可以证明定理1的收敛性：

定理1的证明 在公式（11）中用公式（14）代替，导致更新规则：

（24）

由于方程（14）是一个辅助函数，根据引理1，在这个更新规则下是不增加的。明确地写出这个方程的分量，我们得到

（25）

通过逆转引理1和引理2中和的作用，在的更新规则下，可以类似地显示为不增加。

我们现在考虑以下发散成本函数的辅助函数：

引理3 定义

（27）

（26）

这是

（28）

的辅助函数。

证明：验证是很简单的。为了证明，我们利用对数函数的凸性来推导不等式

（29）

它适用于所有非负的，总和统一。 设

（30）

我们得到

（31）

从这个不等式可看出。

接着从引理1中的应用证明定理2：

定理2的证明：相对于的最小值是通过将梯度设置为零来确定：

（32）

因此，式（11）的更新规则采用形式

（33）

由于是辅助函数，因此在式（28）中的关于此更新下不增加。以矩阵形式重写，这相当于式（5）中的更新规则。通过逆转和的角色，的更新规则可以类似地证明为不增加。

讨论

我们已经证明了在式（4）和（5）中应用更新规则。分别保证至少找到问题1和问题2的局部最优解。收敛证明依赖于定义一个适当的辅助函数。我们正在努力将这些定理推广到更复杂的约束。更新规则本身非常容易在计算上实现，并有望被其他人广泛应用。

我们感谢贝尔实验室的支持。 我们还要感谢Carlos Brody，Ken Clarkson，Corinna Cortes，Roland Freund，Linda Kaufman，Yann Le Cun，Sam Roweis，Larry Saul和Margaret Wright进行了有益的讨论。

外文文献出处：International Conference on Neural Information Processing Systems, 2000, 32(6): 535-541

附外文文献原文

Algorithms for Non-negative Matrix Factorization

Daniel D. Lee
Bell Laboratories

Lucent Technologies

Murray Hill, NJ 07974

H. Sebastian Seung
yDept. of Brain and Cog. Sci.

Massachusetts Institute of Technology

Cambridge, MA 02138

Abstract

Non-negative matrix factorization (NMF) has previously been shown to be a useful decomposition for multivariate data. Two different multiplicative algorithms for NMF are analyzed. They differ only slightly in the multiplicative factor used in the update rules. One algorithm can be shown to minimize the conventional least squares error while the other minimizes the generalized Kullback-Leibler divergence. The monotonic convergence of both algorithms can b

剩余内容已隐藏，支付完成后下载完整资料

---

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[279513]，资料为PDF文档或Word文档，PDF文档可免费转换为Word