MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization
MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization
复制标题
DOI：
10.1109/tkde.2017.2767592
复制
发表时间：
2018-03-01
影响因子：
8.9
通讯作者：
Park, Haesun
中科院分区：
文献类型：
--
作者：
Kannan, Ramakrishnan;Ballard, Grey;Park, Haesun
非负矩阵分解（NMF）是对给定的输入矩阵A确定两个非负的低秩因子W和H，使得A逼近WH的问题。NMF在文本挖掘中的主题建模、视频分析中的背景分离、社交网络中的社区检测等领域有着广泛的应用。尽管它在数据挖掘社区中很受欢迎，但缺乏有效的并行算法来解决大数据集的问题。这项工作的主要贡献是一个新的，高性能的并行计算框架的广泛的NMF算法，迭代解决交替非负最小二乘（NLS）子问题的W和H。它在内存中维护数据和因子矩阵（分布在处理器上），使用MPI进行处理器间通信，并且在密集的情况下，可证明最小化通信成本（在温和的假设下）。该框架是灵活的，能够利用各种NMF和NLS算法，包括乘法更新，分层交替最小二乘法，块主旋转。我们的实现使我们能够对大小从数亿到数十亿不等的大量密集和稀疏数据矩阵进行基准测试和比较不同的算法。我们展示了我们的算法的可扩展性，并将其与基线实现进行比较，显示出显着的性能改进。用于进行实验的代码和数据集可在线获得。
Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors W and H, for the given input matrix A, such that A approximate to WH. NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient parallel algorithms to solve the problem for big data sets. The main contribution of this work is a new, high-performance parallel computational framework for a broad class of NMF algorithms that iteratively solves alternating non-negative least squares (NLS) subproblems for W and H. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). The framework is flexible and able to leverage a variety of NMF and NLS algorithms, including Multiplicative Update, Hierarchical Alternating Least Squares, and Block Principal Pivoting. Our implementation allows us to benchmark and compare different algorithms on massive dense and sparse data matrices of size that spans from few hundreds of millions to billions. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements. The code and the datasets used for conducting the experiments are available online.