Bayesian Nonexhaustive Learning for Online Discovery and Modeling of Emerging Classes

Murat Dundar, Ferit Akova, Yuan (Alan) Qi, Bartek Rajwa

Machine learning models typically operate under a "closed-world" assumption, presuming the training set is exhaustive and contains every possible class the model will ever encounter. However, in real-world applications—such as biosecurity or fraud detection—new categories of data emerge constantly. When a traditional classifier encounters a sample from a novel class, it rarely flags it as unknown; instead, it confidently misclassifies it into an existing category.

This paper introduces a framework for nonexhaustive learning. It allows a system to classify known categories while simultaneously discovering and modeling entirely new ones as they appear in a real-time data stream.

TL;DR

The authors propose a Bayesian framework using Dirichlet Process Priors (DPP) and Particle Filtering to perform online classification in "open" environments. Unlike standard models, this system can identify when a sample belongs to a new, previously unseen class and begin modeling that new class on the fly without needing to retrain from scratch.

The Challenge of Nonexhaustive Training Data

Most supervised learning algorithms fail when the training set is nonexhaustive. For example, in biosensing, a library might contain signatures for 2,400 known strains of Salmonella, but a new mutation could emerge tomorrow.

There are two main challenges in these open environments:

  1. Discovery: Recognizing that a data point doesn't fit any known category.
  2. Modeling: Grouping these "novelties" into coherent new classes rather than just treating them as random noise or outliers.

While "novelty detection" exists, it usually just flags anomalies. This paper goes further by performing online class discovery, where the model builds a statistical profile of the new classes as they emerge. This capability is critical for identifying the onset of events like a biological outbreak.

Methods: A Dynamic Bayesian Classifier

The authors combine Bayesian non-parametrics with sequential inference to create a dynamic classifier capable of adapting to new information:

  • Dirichlet Process Prior (DPP): They use a DPP to model the distribution of classes. The DPP is "non-parametric," meaning it doesn't assume a fixed number of classes. It uses the "Chinese Restaurant Process" metaphor, where a new sample can either sit at an existing "table" (known class) or start a new one.
  • Informative Priors: Unlike pure unsupervised clustering, the model uses the known classes in the training set to estimate the parameters of a "base distribution" (a bivariate Normal $\times$ Inverted Wishart). This tells the model what a "typical" class looks like in this specific domain.
  • Sequential Importance Resampling (SIR): This acts as the "online" engine. Standard Bayesian methods like Gibbs Sampling require looking at the whole dataset at once (batch processing), which is too slow for streaming data. By using SIR (a type of Particle Filter), the model updates its beliefs using only the current sample and a set of weighted "particles" representing potential class structures.

Datasets and Evaluation

The model was evaluated on two primary datasets to test its discovery capabilities:

  1. Synthetic 2D Data: A dataset with 23 distinct classes. Three classes were intentionally hidden during training to test if the model could "discover" them and recover their distributions during testing as new data streamed in.
Evolution of online class discovery on synthetic 2D data.
  1. Bacteria Detection Dataset: A real-world dataset consisting of 2,054 samples from 28 bacterial serovars (strains). The features are 50-dimensional phenotypic characteristics derived from laser scatter patterns of bacterial colonies. 24 classes were used for training, and 4 were held out as "emerging" classes.

Key Insights

  • Beyond Novelty Detection: The core innovation is treating discovery and classification as the same probabilistic problem. By modeling unknown classes as "unlabeled clusters," the model can track the growth of a new pathogen strain in real-time.
  • The Power of the Prior: By using samples from known classes to inform the DPP's base distribution, the model avoids the "vague prior" problem. It learns the expected variance and shape of a class from known data, making it much better at deciding when a new cluster is actually a new class versus just a noisy outlier.
  • Efficiency for Human Experts: In biosecurity, every "new cluster" found by an AI must eventually be checked by a human in a lab. The authors' method (NEL-SIR) produces fewer, more accurate clusters than previous methods, significantly reducing the "false alarm" workload for human analysts.

Key Results

The proposed NEL-SIR algorithm was compared against Bayes-NoDe (a previous state-of-the-art for novelty detection) and an "Exhaustive" benchmark (a theoretical upper bound where all classes are known).

  • Accuracy on New Classes: On the bacteria dataset, NEL-SIR achieved between 75.7% and 99.5% accuracy in identifying samples from the four "emerging" classes.
  • Cluster Quality: NEL-SIR discovered an average of 1.2 to 2.0 clusters for each new class, whereas the older Bayes-NoDe method fragmented the new classes into as many as 5.5 clusters.
  • Stability: The model maintained high accuracy (91.1%) on the original known classes, proving that the ability to learn new things didn't "break" its existing knowledge.

Limitations and Future Work

  • The "Long Tail" Problem: The authors note that in a standard Dirichlet Process, the probability of discovering a new class eventually drops to zero as you see more data. They suggest that a Pitman-Yor process might be a better prior for modeling "heavy-tailed" discovery where new things keep appearing indefinitely.
  • Simple Data Models: The current work assumes classes follow a Normal distribution. Real-world biological data can be more complex, suggesting a need for "mixture models" within each class.
  • Temporal Dynamics: The model doesn't explicitly account for "burstiness"—the idea that a new class might suddenly appear in a huge wave (like an outbreak). Incorporating time-dependent priors is a suggested next step.

Summary updated

Abstract

We present a framework for online inference in the presence of a nonexhaustively defined set of classes that incorporates supervised classification with class discovery and modeling. A Dirichlet process prior (DPP) model defined over class distributions ensures that both known and unknown class distributions originate according to a common base distribution. In an attempt to automatically discover potentially interesting class formations, the prior model is coupled with a suitably chosen data model, and sequential Monte Carlo sampling is used to perform online inference. Our research is driven by a biodetection application, where a new class of pathogen may suddenly appear, and the rapid increase in the number of samples originating from this class indicates the onset of an outbreak.
BibTeX
@inproceedings{dundar2012bayesian,
  author = {Murat Dundar and Ferit Akova and Yuan (Alan) Qi and Bartek Rajwa},
  title = {{Bayesian Nonexhaustive Learning for Online Discovery and Modeling of Emerging Classes}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
}
Figure