A Scalable Asynchronous Distributed Algorithm for Topic Modeling

Hsiang-Fu Yu, Cho-Jui Hsieh, Hyokun Yun, S.V.N. Vishwanathan, Inderjit Dhillon

Abstract:   Learning meaningful topic models with massive document collections which contain millions of documents and billions of tokens is challenging because of two reasons. First, one needs to deal with a large number of topics (typically on the order of thousands). Second, one needs a scalable and efficient way of distributing the computation across multiple machines. In this paper, we present a novel algorithm F+Nomad LDA which simultaneously tackles both these problems. In order to handle large number of topics we use an appropriately modified Fenwick tree. This data structure allows us to sample from a multinomial distribution over T items in $O(\log T)$ time. Moreover, when topic counts change the data structure can be updated in $O(\log T)$ time. In order to distribute the computation across multiple processors, we present a novel asynchronous framework inspired by the Nomad algorithm of Yun et al, 2014. We show that F+Nomad LDA significantly outperforms recent state-of-the-art topic modeling approaches on massive problems which involve millions of documents, billions of words, and thousands of topics.

Download: pdf, arXiv version, code, software

Citation

  • A Scalable Asynchronous Distributed Algorithm for Topic Modeling (pdf, arXiv, software, code)
    H. Yu, C. Hsieh, H. Yun, S. Vishwanathan, I. Dhillon.
    In International World Wide Web Conference (WWW), pp. 1340-1350, May 2015. (Oral)

    Bibtex:

Software

Associated Projects