非负矩阵分解算法

《非负矩阵分解算法》由会员分享，可在线阅读，更多相关《非负矩阵分解算法（13页珍藏版）》请在金锄头文库上搜索。

1、 1 非负矩阵分解非负矩阵分解算法算法 1 摘摘 要要 非负矩阵分解 NMF 是一种处理多变量数据分解极为有效的方 法 这里分析了两种不同的 NMF 多重算法 它们只在矫正规则 2中使用 的乘法因子上略有不同 一种算法可以最小化传统的最小二乘误差 而 另一种算法则能将广义的 Kullback Leibler 发散度最小化 两种算法 的单调收敛性均可使用类似于用于证明期望最大化算法收敛的辅助函 数来证明 这些算法采用对角比例梯度下降的方式 重新调整因子被 最优选择以确保收敛 关键词关键词 非负矩阵分解 NMF 多重算法 最小二乘误差 K L 发散度 一一 介绍介绍 无监督的学习算法 如主成分分析

2、和矢量量化 一种解释是对不 同约束条件下的数据矩阵进行分解的算法 根据所使用的约束 所得 到的因子可以显示出具有非常不同的表征性质 主成分分析仅执行弱 1 Translated by 卢天培 2 update rules 2 正交约束 3 导致了非常分散的表示 这种表示采用用消去法生成变异 性 1 2 另一方面 矢量量化使用一个有力的全局最优约束 从而将 数据聚类成互相独立的原型 3 我们以前已经证明 非负性是矩阵分解中有用的约束来进行数据 的部分性学习 4 5 非负基学习向量用于分布式 仍然采用稀疏组合产 生表达式 6 7 在本文中 我们详细分析了从数据中学习最优非负因 子的两种数值算法 二

3、二 非负矩阵分解非负矩阵分解 我们正式考虑算法来解决以下问题 非负矩阵分解 NMF 给定非负矩阵 找到非负矩阵因子 和 使得 1 NMF 可以以下列方式应用于多变量数据的统计分析 给定一组多 元 n 维数据向量 将向量放置在n m矩阵 的列中 其中 m 是数据集 中的示例数 然后将该矩阵近似分解为n r矩阵 和r m矩阵 通常 r 小于 n 或 m 使 和 小于原始矩阵 得到原始数据矩阵的压缩版 本 3 Principal components analysis enforces only a weak or thogonality constraint resulting in a very

4、 distributed representation that uses cancellations to generate variability 1 2 3 方程式 1 近似的意义在于它可以逐列重写为v 其中 和 是 和 的对应列 换句话说 每个数据向量 近似的由 的列进行 线性组合 用 的分量进行加权 因此 可以被认为是包含对于 中 的数据的线性近似优化的基础 由于相对较少的基向量用于表示许多 数据向量 所以在数据中只有在基向量发现潜在的结构时才能实现良 好的近似 本文不是关于 NMF 的应用 而是侧重于找到非负矩阵分解的技术 方面 当然 其他类型的元分解因子在数值线性代数中已经得到了

5、广 泛研究 但是这种非负性约束使得以前的很多工作都不适用于目前的 情况 8 在这里 我们讨论了基于W和H的迭代矫正的两种 NMF 算法 由 于这些算法易于实现 其收敛性能得到保证 我们发现它们在实际应 用中非常有用 其他算法可能在整体计算时间内更有效 但是更难实 现 并且不能将其推广到不同的成本函数 只有一个因素类似于我们 的算法 已经被用于去卷积发射断层扫描和天文图像 9 10 11 12 在我们的算法的每次迭代中 通过将当前值乘以取决于方程式 1 中的近似质量的一些因子来找到W或H的新值 我们证明近似的质量 随着这些乘法矫正规则的应用而单调改善 实际上 这意味着矫正规 则的重复迭代保证收敛

6、到局部最优矩阵分解 三三 成本函数成本函数 4 为了找到一个近似分解 我们首先需要定义量化近似质 量的成本函数 可以使用两个非负矩阵 和 之间的距离的一些度量 来构造这样的成本函数 一个有用的方法只是 和 之间的欧几里得 距离的平方 13 1 34 34 1 34 2 下限为零 距离消失当且仅当 另外一个有用等方法为 34 34 34 34 3 像欧几里德的距离一样 这也是下限为零 当且仅当 A B 时 才距离消失 但它不能被称为 距离 它在 A 和 B 中不对称 所 以我们把它称之为 A 对于 B 的 散度 它减少到 K L 散度或相对 熵 当 34 34 34 1 34 使得 A 和 B

7、可以被认为是归一化的概率 分布 我们现在考虑 NMF 的两种替代方案作为优化问题 问题问题 1 1 最小化 V WH 1用W和H 约束条件 H 0 问题问题 2 2 最小化 用W和H 约束条件 H 0 尽管方程 V WH 1和 在仅W下凸或在仅H下凸 它 在两者之下不为凸 因此 期望一种算法在找到全局最小值的意义 上解决问题 1 和 2 是不切实际的 然而 有许多数值优化技术可以 应用于寻找局部最小值 5 梯度下降法 4可能是实现起来最简单的技术 但其收敛速度可能 很慢 其他方法如共轭梯度具有更快的收敛 至少在局部最小值附 近 但是比梯度下降更复杂 8 并且 基于梯度的方法的收敛具有 对步长选

8、择非常敏感的缺点 这对于大型应用非常不方便 四 四 乘法乘法矫正矫正规则规则 我们发现 以下 乘法矫正规则 是解决问题 1 和 2 的速度和 易于实施的一个很好的妥协方法 理论理论 1 1 欧氏距离 在 4 的矫正规则下非减 4 4 当且仅当W和H同一点时 欧几里得距离固定 理论理论 2 2 散度D V WH 在 5 的矫正规则下非减 5 5 当且仅当 W 和 H 处于静止状态时 散度是不变的 这些定理的证明在后面的部分给出 现在我们注意到 每个矫 正都是乘以一个因子 特别地 当V WH时 可以直观地看出这 个乘数因子是一致的 所以完美的重构必然是矫正规则的固定一点 点 4 Gradient

9、descent 6 五五 乘法乘法与加法与加法矫正矫正规则规则 可以将这些乘法矫正与梯度下降产生的矫正进行对比 14 特别 地 对于减小平方距离的 H 的简单加法矫正可以被写为 TU TU TU X TU X TU 6 如果 TU设置为小正数 这相当于常规梯度下降方法 只要数字 充分的小矫正会减少到 如果我们对对角进行重新调整 5变量并设置 TU Z Z 7 那么我们获得在定理 1 中给出的 H 的矫正规则 注意 该重新 调整会得出乘子因子 分母中的梯度的正分量和因子的分子中的负 分量的绝对值 对于散度 对角线重新调整梯度下降采取以下显示 TU TU TU 3T 3U 3U 3 3T 3 8

10、同样的 如果 TU设置为小正数 这相当于常规梯度下降方法 只要数字充分的小矫正会减少到D V WH 如果设置 TU Z 9 那么我们获得在定理 2 中给出的 H 的矫正规则 该重新调整同 样会得出乘子因子 分母中的梯度的正分量和因子的分子中的负分 量的绝对值 5 diagonally rescale 7 由于我们对 TU的取值不是很小 似乎不能保证这种重新缩放的 梯度下降降低成本函数 令人惊讶的是 如下一节所示 这是确定 的情况 六 六 衔接证明衔接证明 我们将利用类似于期望最大化算法中使用的辅助函数 15 16 证明 定理 1 和 2 定义定义 1 1 G h 是 的辅助函数 如果下面的条件

11、成立 d 10 辅助函数说一个有用对概念 因为下面引理 Fig 1 中的插 图 引理引理 1 1 如果 是一个辅助函数 那么 是非增在以下条件下 efg argmin k e 11 证明 证明 efg efg e e e e 注意到 efg e 仅当 e是 e局部最小值时满足 如 果 的导数存在且在 e的短区间内连续 这也表明 e 0 因此 通过 Eq 11 重复矫正 我们估计得到了下列方程的收敛局部最小值 o3p argmin k o3p efg e 1 g s 12 我们接下去证明通过定义适当的辅助函数 e对 和 矫正规则对定理 1 和 2 遵循 Eq 11 8 图 1 最小化辅助函数 e

12、 确保 efg e对于 efg argmin k e 理论理论 2 2 如果K e 是对角矩阵 Tv e Tv X e T T e 13 那么 e e e X e g 1 e X e e 14 是一个辅助函数对于 g 1 3 3T T T 1 3 15 证明证明 因为显然 我们只需要证明 d 为了证明需要 我们对比 e e X e g 1 e X X e 16 和 Eq 14 来得到 d 等价于 0 e X e X e 17 9 为了证明正向半定性 6 考虑矩阵 Tv e T e e X Tv v e 18 只是 e X 的重新调整 那么 e X 具有正向半 定性当且仅当M是且符合 X T T

13、v Tv v 19 T e X Tv v e T 1 Tv T T e X Tv v e v X Tv T e v e Tv g 1 T 1 g 1 v 1 T v g 1 X Tv T e v e Tv T v 1 0 现在我们可以证明定理 1 的收敛性 定理定理 1 1 的证明的证明 在Eq 11中用Eq 14替换 e得到矫正规则 efg e e zg e 20 因为 Eq 14 为辅助函数 在矫正法则下非增 根据引理 1 明 确写出这个方程的组成部分 我们得到 T efg T e k 21 通过替换掉引理 1 和 2 中的 和 可以被相似地证明在对 矫正规则非增 我们现在考略接下去的辅助

14、方程对于收敛花费方程 引理引理 3 3 定义 e 3 3 3 3 3T T 3T 3 k k 3T T k k 3T 22 6 positive semidefiniteness 10 为辅助方程对于 3log k 3 3T T T3 23 证明 证明 显然 为证明 e 我们使用对 数函数的凸度来导出不等式 3T T T T k T 24 这适用于所有非负的求和基本单位 T 设置 T k k 25 我们得到 3T T T k k 3T T k k T 26 对于这个不等式 遵循 e 而定理 2 遵循引理 1 等应用 定理定理 1 1 的证明的证明 e的最小值需要考虑通过将梯度设置为 零来确定h

15、 k k k 3 k k g k 3 3T 3 0 27 因此 Eq 11 矫正规则采取以下形式 T efg k k 3T 3 28 因为 是辅助函数对于 在 Eq 23 非增 以矩阵形式重写 这等 同于 Eq 5 中的矫正规则 通过反转H和W的作用 W的矫正规则可 以类似地证明为非增 11 七 讨论七 讨论 我们已经证明 应用矫正规则在 Eq 4 和 Eq 5 保证至少可以分别 找到问题 1 和 2 的局部最优解 收敛证据依赖于定义适当的辅助函 数 我们正在努力将这些定理推广到更复杂的约束条件下 矫正规 则本身非常容易在计算上实现 并且较易于被其他人用于各种各样的 应用 感谢贝尔实验室的支持

16、 我们还要感谢 Carlos Brody Ken Clarkson Corinna Cortes Roland Freund Linda Kaufman Yann Le Cun Sam Roweis Larry Saul 和 Margaret Wright 的帮助性讨 论 12 参考文献参考文献 1 Jolliffe IT 1986 Principal Component Analysis New York Springer Verlag 2 Turk M Pentland A 1991 Eigenfaces for recognition J Cogn Neurosci 3 71 86 3 Gersho A Gray RM 1992 Vector Quantization and Signal Compression Kluwer Acad Press 4 Lee DD Seung HS Unsupervised learning by convex and conic coding 1997 Proceedings ofthe Conference on Neural Inform