用牛顿法优化KL散度的NMF，速度快且收敛有保障。
An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence
- 基于损失函数二阶泰勒展开构造牛顿型算法
- 在多种数据集上优于现有先进方法，收敛性可证明
- 适合处理计数型数据如文本或图像词频矩阵
非负矩阵分解（NMF）是无监督学习中的基础工具，通过两个低秩非负因子的乘积近似一个非负矩阵。当分解数据服从泊松分布时，使用Kullback-Leibler（KL）散度衡量数据与模型间的差异最为合适，这常见于词-文档矩阵或图像等计数型数据。现有大多数KL-NMF算法通过最小化损失的可分离上界来寻找下一迭代点，但该方法已接近性能极限。本文提出改用损失函数的二阶泰勒展开，构建牛顿型算法，并通过推广经典的HALS算法来最小化这一不可分离的代理函数。所提出的算法高效、收敛性可证明，在多种数据集上表现优于当前最优方法。
原文摘要 · Abstract (English)
Nonnegative Matrix Factorization (NMF) is a fundamental tool in unsupervised learning, which approximates a nonnegative matrix by the product of two low-rank nonnegative factors. The Kullback-Leibler (KL) divergence is best suited to measure the data to model discrepancy when the decomposed data sample follows a Poisson distribution, which is the case for count datasets such as term-document matrices or images. Most KL-NMF algorithms in the literature minimize a separable majorant of the loss to find their next iterate. We argue that this method has reached its limits and propose to use instead the second-order Taylor expansion of the loss, leading to a Newton-type method. We minimize this non-separable surrogate by proposing a generalization of the well-known HALS algorithm. This yields an efficient KL-NMF algorithm which provably converges and which competes favorably with state-of-the-art algorithms on a large variety of datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。