Discrete Component Analysis

Wray L. Buntine, Aleks JakulinSLSFS 2005 · DOI

Introduction

Principal Component Analysis (PCA) has served as a cornerstone for data reduction and feature extraction for over a century. However, PCA's fundamental assumptions—real-valued data and Gaussian (normal) distributions—often clash with the reality of modern datasets, particularly "large sparse discrete matrices." Examples include document-word count matrices where millions of words are distributed across hundreds of thousands of documents. In these contexts, PCA often fails to provide meaningful or statistically sound representations.

The Limitations of Gaussian Assumptions

The application of PCA to discrete count data is problematic for several reasons. First, word counts are inherently non-negative and discrete, making them better suited for Poisson or Multinomial distributions rather than the continuous Gaussian distribution assumed by PCA. As shown in Figure 1, the Gaussian approximation can severely underestimate the probability of rare events and fails to capture the skewness typical of count data.

Comparison of Binomial, Poisson, and Gaussian distributions for count data.

Furthermore, PCA often produces negative values in its component matrices, which lacks physical or linguistic interpretability (e.g., a "negative" word count in a topic). Finally, the Euclidean distance metric used by PCA does not align with human perception of similarity in linguistic or psychological spaces.

Discrete Component Analysis (DCA)

To address these issues, we propose Discrete Component Analysis (DCA), a unified framework for "admixture models." In DCA, the expected value of the observed data is modeled as a linear combination of latent component scores and a loading matrix.

The foundational building block of this framework is the Gamma-Poisson (GaP) model. In this model, component scores are assumed to be independent and Gamma-distributed, while the observed counts follow a Poisson distribution based on the product of these scores and the loading matrix.

A Unified Framework

One of the primary contributions of DCA is its ability to unify several popular but disparate techniques. As summarized in the table below, models such as Non-negative Matrix Factorization (NMF), Latent Dirichlet Allocation (LDA), and Multinomial PCA (MPCA) can be viewed as specific instances or variations of the broader DCA framework.

Comparison of discrete component models within the DCA framework.

For instance, NMF is effectively a maximum likelihood version of the GaP model, while LDA and MPCA are equivalent to GaP under specific parameter constraints, such as a constant scaling parameter.

Algorithmic Approaches

Solving these models efficiently requires specialized algorithms. The paper explores three main families:

  1. Variational Approximation: A fast, EM-like approach that minimizes Kullback-Leibler divergence.
  2. Direct Gibbs Sampling: A conceptually simple Markov Chain Monte Carlo (MCMC) method.
  3. Rao-Blackwellised Gibbs Sampling: A more advanced sampling technique that marginalizes out certain variables, significantly improving efficiency and reducing memory overhead.

Experimental Evaluation

The DCA framework was evaluated across diverse datasets to demonstrate its versatility:

  • US Senate Voting Records: Applying DCA (with $K=5$ components) to roll-call data successfully identified distinct political blocs, ranging from staunch partisans to moderates in both parties.
  • 20 Newsgroups: Integrating 50 DCA-generated features into a standard SVM classifier increased classification accuracy from 87.1% to 90.7%, highlighting the value of capturing latent word co-occurrences.
  • Reuters-21578: In contrast, DCA provided little improvement for categories defined by specific, high-frequency keywords (e.g., "grain"). This suggests that DCA's strength lies in modeling complex latent themes rather than simple keyword matching.

Conclusion

Discrete Component Analysis provides a statistically principled alternative to PCA for count data. By unifying models like LDA and NMF under the Gamma-Poisson framework and introducing efficient Rao-Blackwellised sampling, DCA offers a powerful tool for discovering structure in sparse, discrete datasets. While computationally more intensive than traditional methods, its ability to capture nuanced co-occurrence patterns makes it invaluable for complex classification and exploratory data analysis tasks.

Summary updated

BibTeX
@inproceedings{buntine2005discrete,
  author = {Wray L. Buntine and Aleks Jakulin},
  title = {{Discrete Component Analysis}},
  booktitle = {SLSFS},
  year = {2005},
  doi = {10.1007/11752790\_1},
}
Figure