Data association for topic intensity tracking

Andreas Krause, Jure Leskovec, Carlos Guestrin

Introduction

When analyzing a stream of data—such as a news feed or an email inbox—we typically observe two primary signals: content (what the document is about) and timing (when it arrived). Traditionally, researchers have treated these as separate, sequential steps: first classifying documents into topics (Data Association), and then analyzing those grouped documents to identify temporal bursts of activity (Intensity Tracking).

This paper argues that separating these processes leaves valuable information on the table. If a specific topic is currently "bursting" (e.g., a major product launch), a new, slightly ambiguous document is statistically more likely to belong to that active topic. Conversely, correctly identifying a few documents as belonging to a rare topic helps better estimate its current underlying intensity. Solving this requires overcoming a "chicken and egg" problem: topic labels are needed to find intensities, but intensities are needed to improve labeling. To address this, the authors introduce a unified framework that simultaneously classifies documents and tracks the changing frequency of those topics over time.

Methodology: From Explicit to Implicit Tracking

The researchers propose a progression of models, evolving from an intuitive but computationally heavy approach to a mathematically elegant and efficient framework:

  1. EDA-IT (Explicit Data Association): This initial model attempts to keep track of the exact time every single topic was last seen. While conceptually intuitive, it is computationally intractable because the state space grows exponentially with the number of documents.
  2. IDA-IT (Implicit Data Association): This represents the core breakthrough of the paper. By exploiting the memoryless property of exponential distributions (which model the time between events), the authors demonstrate that the model does not actually need to remember when a topic was last seen. It only needs to track the current rates (intensities).
  3. The Mathematical Trick: Using exponential order statistics, they prove that the probability of the next document belonging to topic $k$ is simply its intensity divided by the sum of all topic intensities. This transforms the intractable problem into a Factorial Hidden Markov Model (FHMM), enabling exact inference for small cases and efficient approximate inference (like particle filtering) for larger ones.
  4. IDA-ITT (Topic Tracking): To handle "topic drift"—where the vocabulary of a topic naturally evolves over time (e.g., an "election" topic shifting from "primaries" to "inauguration")—the authors integrate a Switching Kalman Filter. This allows the model to track the evolving word "centroid" for each topic in a low-dimensional space.
Graphical models for IDA-IT and IDA-ITT

Key Insights

  • Temporal Information as a Dynamic Prior: Instead of relying on a static prior for classes (e.g., assuming "10% of emails are always about HR"), the model uses the current intensity as a dynamic prior. If a topic is currently hot, the prior probability for that class dynamically increases.
  • Negative Evidence Matters: The model learns not just from when a topic appears, but also from its absence. If a long period elapses without an email for a specific topic, the model correctly downgrades its belief in that topic's current intensity.
  • Synergy Beats Separation: The interplay between content and timing is crucial. The paper demonstrates that even if the underlying text classifier is mediocre, the temporal model can "rescue" the classification by recognizing the bursty pattern of the underlying events.

Datasets and Key Results

The models were rigorously evaluated on both synthetic and real-world data streams, including an Enron Email Corpus (554 emails across specific folders over several months) and a Reuters Document Corpus (over 2,300 news articles across four distinct topics).

Topic bursts in the Enron dataset
  • Noise Resilience: On synthetic datasets injected with up to 30% topic noise, the IDA-IT model successfully recovered the true underlying intensity levels. In contrast, traditional algorithms relying on hard assignments (like Kleinberg’s WAM) were completely misled by the noise.
  • Classification Boost: By leveraging temporal dynamics, IDA-IT significantly improved classification accuracy. It reduced classification error by 32% on the Enron dataset compared to a standard Gaussian Naive Bayes classifier, and achieved a relative error reduction of 22% to 45% on the Reuters dataset.
  • Inference Flexibility: While exact inference yields the best results, the authors showed that approximate methods like Particle Filtering provide nearly identical performance, ensuring the model remains scalable to more complex, real-world scenarios.

Limitations and Future Work

Despite its elegance, the framework has limitations. While the "implicit" trick makes time-tracking tractable, the Factorial HMM structure still struggles to scale as the total number of topics ($K$) grows very large, due to the state space expanding as $L^K$ (where $L$ is the number of intensity levels). Additionally, the model currently relies on a manually set or cross-validated transition probability ($\theta$) to determine how likely intensities are to change; a fully Bayesian approach to automate this is a promising next step. Finally, while the current model operates in discrete steps, extending it into a true continuous-time Markov process could offer even more granular tracking capabilities in the future.

Summary updated

Abstract

We present a unified model of what was traditionally viewed as two separate tasks: data association and intensity tracking of multiple topics over time. In the data association part, the task is to assign a topic (a class) to each data point, and the intensity tracking part models the bursts and changes in intensities of topics over time. Our approach to this problem combines an extension of Factorial Hidden Markov models for topic intensity tracking with exponential order statistics for implicit data association. Experiments on text and email datasets show that the interplay of classification and topic intensity tracking improves the accuracy of both classification and intensity tracking. Even a little noise in topic assignments can mislead the traditional algorithms. However, our approach detects correct topic intensities even with 30% topic noise.
BibTeX
@inproceedings{krause2006data,
  author = {Andreas Krause and Jure Leskovec and Carlos Guestrin},
  title = {{Data association for topic intensity tracking}},
  booktitle = {International Conference on Machine Learning},
  year = {2006},
  doi = {10.1145/1143844.1143907},
}
Figure