A Probabilistic Model for Online Document Clustering with Application to Novelty Detection

Jian Zhang, Zoubin Ghahramani, Yiming YangNeurIPS 2004 · OpenReview

Introduction

This paper introduces a Bayesian framework for online document clustering that uses a Dirichlet Process (DP) prior to automatically handle an unknown, growing number of topics. By treating the first document of every new cluster as a "novel" event, the authors achieve state-of-the-art results in novelty detection. Their work demonstrates that formal probabilistic models can successfully compete with, and occasionally outperform, heavily tuned heuristic systems in real-world streaming environments.

The Challenge of Novelty Detection

In the world of streaming news, spotting the very first report of a breaking story is known as the "Novelty Detection" or First Story Detection problem.

The challenge is primarily three-fold:

  1. Online Constraints: Systems must process documents sequentially as they arrive; they cannot look into the future to contextualize current events.
  2. Unknown Scale: The number of topics that will emerge over time is entirely unknown and unbounded.
  3. High Dimensionality: Text data involves tens of thousands of unique words (features), making traditional clustering computationally expensive and highly susceptible to noise.

Most existing solutions rely on heuristic "nearest neighbor" clustering using cosine similarity. The authors argue for a more principled approach: a generative probabilistic model that can quantify uncertainty and adapt dynamically to new information.

A Principled Probabilistic Approach

The authors build their system on a Dirichlet Process Mixture Model. The core components of their methodology include:

  • The Dirichlet Process (DP): Acting as a "non-parametric" prior, the DP allows the number of clusters to grow naturally as more data arrives. This is a significant advantage over algorithms like K-means, which require the number of clusters ($K$) to be defined upfront.
  • Base Distribution ($G_0$): When a brand-new cluster is formed, it needs a starting point. The authors use a "General English" language model (a Dirichlet distribution) as this base. This provides a sensible "background" for any new topic, helping the model distinguish between common noise words and the specific keywords that define a new event.
  • Dirichlet-Multinomial Model: Each cluster is modeled as a multinomial distribution over words. By using a Bayesian approach (a Dirichlet prior), the model integrates over the parameter space to handle cluster uncertainty, rather than relying on a single "best guess" Maximum Likelihood Estimate (MLE).
  • Empirical Bayes: To avoid manual tuning, the authors use a historical dataset to estimate hyperparameters, such as the word frequencies of general English ($\pi$) and the rate at which new clusters typically appear ($\lambda$).

Key Insights

The DP provides a mathematically elegant way to calculate the probability that a document belongs to a new cluster versus an existing one. This probability serves directly as the "novelty score."

Furthermore, the authors recognized that the rate of new events is not constant. They modeled the precision parameter $\lambda$ as a function of time, allowing the model to account for the changing "burstiness" of news as a stream progresses.

Experimental Setup and Results

The study utilizes the Topic Detection and Tracking (TDT) corpora, standard benchmarks for this field. TDT2 (over 60,000 documents with 96 labeled clusters) was used as the historical training set to estimate hyperparameters, while TDT3 was used as the evaluation set to test the model's ability to detect novel events in a fresh stream.

The model was evaluated using the Normalized Detection Cost ($C_{det}$), a metric that balances "misses" (failing to spot a new story) and "false alarms" (flagging a follow-up story as new).

Performance Comparison Table

As shown in the performance table above, the DP model with a variable arrival rate ($\lambda_{var}$) and Hard Decisions (HD) achieved a topic-weighted cost of 0.6901. This outperformed the GAC-INCR method (0.6945), which was the top-performing heuristic system in official TDT evaluations at the time.

The results also highlight an interesting dynamic between decision strategies. "Hard Decisions" (assigning a document to the single most likely cluster) generally performed better than "Soft Probabilistic" (PD) updates for this specific task. This is likely because news stories tend to belong to distinct, non-overlapping events. Additionally, while the DP model won on topic-weighted cost, a Logistic Regression baseline slightly edged it out on story-weighted cost (0.6911).

Limitations and Future Work

While highly effective, the model has limitations. It relies on a "bag-of-words" (unigram) assumption, which ignores word order and context—a naive assumption that could be improved with richer language models. Furthermore, while Bayesian inference is mathematically elegant, handling the "intractable" nature of forking many potential cluster paths can be slower than simple cosine similarity.

Future work could involve conditioning the novelty detection on specific broad categories (e.g., Sports vs. Politics) to make the base distribution priors more accurate and context-aware.

Summary updated

Abstract

In this paper we propose a probabilistic model for online document clus- tering. We use non-parametric Dirichlet process prior to model the grow- ing number of clusters, and use a prior of general English language model as the base distribution to handle the generation of novel clusters. Furthermore, cluster uncertainty is modeled with a Bayesian Dirichlet- multinomial distribution. We use empirical Bayes method to estimate hyperparameters based on a historical dataset. Our probabilistic model is applied to the novelty detection task in Topic Detection and Tracking (TDT) and compared with existing approaches in the literature.
BibTeX
@inproceedings{zhang2004probabilistic,
  author = {Jian Zhang and Zoubin Ghahramani and Yiming Yang},
  title = {{A Probabilistic Model for Online Document Clustering with Application to Novelty Detection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2004},
  url = {https://openreview.net/forum?id=HkZaaLW_WB},
}
Figure