AClass: A simple, online, parallelizable algorithm for probabilistic classification

Vikash K. Mansinghka, Daniel M. Roy, Ryan Rifkin, Joshua B. TenenbaumAISTATS 2007 · OpenReview

Abstract

We present AClass, a simple, online, parallelizable algorithm for supervised multiclass classification. AClass models each class-conditional density as a Chinese restaurant process mixture, and performs inference using sequential Monte Carlo. This approach allows for flexible, non-linear decision boundaries while maintaining the robust missing-data handling characteristic of generative models.

Introduction

In machine learning, a classic trade-off exists between generative and discriminative approaches. Generative models, such as Naive Bayes, excel at handling missing data and unlabeled examples by modeling the underlying feature distributions. However, they often rely on simplistic assumptions—like a single Gaussian per class—resulting in rigid, linear decision boundaries. Conversely, discriminative models like SVMs or Logistic Regression provide powerful nonlinear boundaries but typically require complete datasets and are difficult to update online as new data arrives.

AClass bridges this gap. It is designed to learn complex, nonlinear class shapes, handle missing features naturally, and process data points sequentially (online) without requiring access to the entire historical dataset.

The AClass Model

AClass models each class-conditional density using a Chinese Restaurant Process (CRP) mixture. This nonparametric Bayesian framework allows the number of clusters (or "prototypes") for each class to grow dynamically as new data points are observed, rather than requiring a pre-specified count.

Plate notation of the AClass generative model, illustrating the hierarchical relationship between class labels ($y_i$), cluster assignments ($z_i$), and observed features ($x_i$).

To maintain an online processing capability, AClass employs Sequential Monte Carlo (SMC), or particle filtering. Each particle represents a hypothesis regarding the clustering of past data. When a new observation arrives, these particles are updated based on the fit to existing clusters or the necessity of creating a new one. By utilizing conjugate priors (e.g., Beta-Bernoulli for binary data), the algorithm only needs to track sufficient statistics, making it highly memory-efficient. Furthermore, because each class is treated as an independent bank of filters, the training process is inherently parallelizable.

Experimental Evaluation

The authors evaluated AClass across three distinct domains:

  1. Synthetic Data: 50-dimensional binary vectors used to test the model's ability to discover the true number of latent clusters (ranging from 1 to 30).
  2. 20-Newsgroups: A text classification task reduced to 100 binary features.
  3. MNIST Digits: An "odd vs. even" classification task using the top 50 principal components of binarized handwritten digits.

A key insight from these experiments is "complexity on demand." AClass does not merely find a single class average; it identifies as many modes as the data supports, capturing disjoint shapes in feature space that simpler models fail to resolve.

Key Results

AClass demonstrated robust structural recovery on synthetic data, accurately identifying mixture components. Crucially, as a generative model, it handles missing data by simply ignoring missing dimensions in probability calculations—a method that proved significantly more robust than the imputation required by discriminative models.

Comparison of prediction accuracy on the MNIST dataset with no missing data. AClass (40 particles) matches or exceeds the performance of strong discriminative baselines as training size increases.

On the MNIST benchmark, AClass performed competitively with polynomial-kernel Regularized Least Squares (RLS) when data was complete and maintained superior accuracy as the percentage of missing features increased. On the 20-Newsgroups task, the model demonstrated sensible automatic regularization by effectively falling back to a single mode per class when additional complexity was not warranted.

Conclusion and Future Work

AClass provides a scalable framework for high-performance nonlinear classification on streaming data. While effective, the model's performance is sensitive to the number of particles used for inference, and it can be susceptible to noisy, irrelevant features. Future work may involve hyperparameter learning to automatically discount irrelevant dimensions and the implementation of memory bounds for the number of clusters in resource-constrained environments.

Summary updated

Abstract

We present AClass, a simple, online, parallelizable algorithm for supervised multiclass classification. AClass models each classconditional density as a Chinese restaurant process mixture, and perf...
BibTeX
@inproceedings{mansinghka2007aclass,
  author = {Vikash K. Mansinghka and Daniel M. Roy and Ryan Rifkin and Joshua B. Tenenbaum},
  title = {{AClass: A simple, online, parallelizable algorithm for probabilistic classification}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2007},
  url = {https://openreview.net/forum?id=BhNVkvhPyG5},
}
Figure