Pólya Urn Latent Dirichlet Allocation: A Doubly Sparse Massively Parallel Sampler.

Area of Science:

• Machine Learning
• Natural Language Processing
• Computational Statistics

Background:

• Latent Dirichlet Allocation (LDA) is a foundational topic model in NLP and ML.
• Existing iterative training methods for LDA struggle with large corpora and distributed computing.
• Current parallel inference techniques for LDA often lack convergence or require excessive memory.

Purpose of the Study:

• To introduce a novel sampler for LDA that addresses limitations of existing iterative and parallel approaches.
• To demonstrate improved speed and accuracy for LDA training on large-scale datasets.
• To challenge existing assumptions about the efficiency of partially collapsed samplers in topic modeling.

Main Methods:

• Development of a novel Pólya-urn-based approximation within a sparse partially collapsed sampler for LDA.
• Theoretical analysis proving that the approximation error diminishes with increasing data size.
• Empirical and theoretical comparisons against existing Gibbs samplers for LDA.

Main Results:

• The novel sampler demonstrates superior speed compared to previous Gibbs samplers for LDA, both empirically and theoretically.
• The proposed method is proven to be asymptotically exact, a crucial property for large-scale topic models.
• An explicit example illustrates that partially collapsed samplers can outperform fully collapsed samplers, contrary to common belief.

Conclusions:

• The novel sparse partially collapsed sampler offers a significant advancement for training LDA on big corpora in parallel and distributed environments.
• The algorithm achieves asymptotically exact inference, making it suitable for large-scale machine learning applications.
• This work provides a more efficient and accurate alternative for topic modeling, with implications for NLP and data analysis.