Nonnegative Matrix Factorization and Probabilistic Latent Semantic Indexing: Equivalence Chi-Square Statistic, and a Hybrid Method

Chris H. Q. Ding, Tao Li, Wei PengAAAI 2006

Abstract

This paper demonstrates that Nonnegative Matrix Factorization (NMF) and Probabilistic Latent Semantic Indexing (PLSI)—two prominent document clustering techniques—are mathematically equivalent in their objective functions. However, their distinct update rules lead them to different local minima. By exploiting these differences, the authors introduce a hybrid algorithm that alternates between the two methods to achieve superior clustering performance.

Introduction

Document clustering is essential for organizing and summarizing large-scale text data. Historically, NMF (a linear algebra approach) and PLSI (a statistical approach) were treated as separate methodologies. While a connection was suspected, previous proofs were often incomplete or technically flawed. This research resolves the relationship between these methods, provides a statistical justification for NMF via the $\chi^2$ statistic, and leverages their algorithmic differences to create a more robust hybrid clustering method.

Theoretical Equivalence and Statistical Grounding

The authors provide a rigorous proof showing that likelihood maximization in PLSI is identical to minimizing the KL-divergence-based NMF objective function, provided the NMF matrices are $L_1$ normalized. This normalization ensures that the matrix factorization aligns with the probabilistic constraints of PLSI, where probabilities must sum to one.

Furthermore, the paper establishes that the NMF objective function is a first-order approximation of the $\chi^2$ (chi-square) statistic. This provides a strong statistical foundation for applying NMF to word-frequency count data, bridging the gap between algebraic factorization and classical statistics.

The Hybrid "Leapfrog" Algorithm

Despite sharing an objective function, NMF and PLSI are different algorithms. They follow different numerical trajectories and often converge to different local minima even when starting from the same point. The authors treat these local minima as temporary states rather than failures.

The proposed hybrid method uses a "leapfrog" strategy:

  1. Initialization: Start with a smoothed K-means solution.
  2. NMF Phase: Run NMF until it converges to a local minimum.
  3. PLSI Phase: Switch to PLSI update rules to "jump" out of the current minimum and find a deeper one.
  4. Iteration: Alternate between the two until the solution stabilizes.

Experimental Evaluation

The methods were tested on five diverse datasets: CSTR (technical reports), WebKB (webpages), Log (log messages), Reuters (news), and WebAce (news articles). Performance was measured using Accuracy, Purity, Entropy, and the Adjusted Rand Index (ARI).

Comparison of baseline clustering methods (K-means, NMF, and PLSI) across four metrics and five datasets.

Key Results and Insights

The experimental results confirmed the theoretical findings. As shown in the baseline comparisons in Figure 6, NMF and PLSI often yield very similar performance levels, reflecting their shared objective function. However, the hybrid method significantly outperformed all standalone approaches.

  • Accuracy Improvements: On the CSTR dataset, the Hybrid method reached an accuracy of 0.878, a substantial jump from the ~0.67 achieved by standalone NMF and PLSI.
  • Robustness: The hybrid approach showed significant gains in 3 out of 5 datasets and marginal improvements in others, proving that alternating between update rules is an effective strategy for finding better global solutions in complex optimization landscapes.
  • Algorithmic Divergence: Numerical examples confirmed that NMF and PLSI converge to different matrices from the same starting point, definitively proving they are distinct algorithms despite sharing an objective.

Conclusion

This work clarifies the relationship between NMF and PLSI, proving their mathematical equivalence while highlighting their algorithmic distinctions. By treating local minima as temporary states and alternating between optimization paths, the hybrid method provides a powerful tool for high-performance document clustering. Future work could explore the computational overhead of this alternating approach and extend the analysis to other variants of NMF, such as the sum-of-squared-errors version.

Summary updated

BibTeX
@inproceedings{ding2006nonnegative,
  author = {Chris H. Q. Ding and Tao Li and Wei Peng},
  title = {{Nonnegative Matrix Factorization and Probabilistic Latent Semantic Indexing: Equivalence Chi-Square Statistic, and a Hybrid Method}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure