A Latent Source Model for Nonparametric Time Series Classification

George H. Chen, Stanislav Nikolov, Devavrat Shah

TL;DR: Researchers from MIT and Twitter provide a theoretical foundation for the surprising effectiveness of nearest-neighbor methods in time series classification. By modeling time series as variations of a few "latent sources," they developed a weighted majority voting algorithm that can predict Twitter trending topics nearly an hour and a half before they are officially flagged, achieving a 95% true positive rate.

The Challenge of Time Series Classification

In machine learning, simple nearest-neighbor (NN) classifiers—which categorize a new data point based on the most similar examples in the training set—often outperform complex neural networks or support vector machines when applied to time series data. However, this success has largely been observed experimentally without a strong theoretical foundation.

This paper addresses two main gaps:

  1. Theoretical Justification: Why does a simple "look-alike" approach work so well for complex, high-dimensional time series?
  2. Precognition: Can we classify a time series (like a news topic's popularity) before the full pattern has emerged? This is particularly relevant for "trending" topics, where the goal is to identify a trend while it is still in its infancy.

The Latent Source Model

To operationalize their hypothesis, the authors introduce a Latent Source Model. The core idea is that while there are millions of observed time series (e.g., different hashtags), there are only a few "prototypical" ways a topic actually becomes popular.

Illustration of time-shifted latent sources

Key components of this approach include:

  • Latent Sources: A small number of unknown "master" patterns generate all observed data.
  • Generative Process: Observed time series are created by taking a latent source, shifting it in time, and adding random noise.
  • Weighted Majority Voting (WMV): Instead of relying on a single nearest neighbor, this algorithm lets every training example "vote" on the label of a new series. The closer a training example is to the new series, the more weight its vote carries.
  • Similarity Measure: The model uses a squared Euclidean distance that accounts for time shifts, ensuring that two identical patterns aren't seen as different just because one started ten minutes later than the other.

Key Insights: Classification vs. Learning

The authors argue that explicitly "learning" the underlying patterns (like fitting a Gaussian Mixture Model) is often overkill. If the goal is simply to classify, using training data as a proxy for the latent sources is more efficient and requires less data.

The success of the model depends heavily on the "gap"—the minimum distance between patterns of different classes. As long as this gap grows logarithmically relative to the number of sources, the classifier remains highly accurate. Furthermore, while NN and WMV perform similarly when the full time series is available, WMV is significantly more robust in an "online" setting. When only the first few minutes of a trend are observed, a single nearest neighbor might be a fluke; the weighted average of many neighbors provides a much more stable prediction.

The paper evaluates the model using both synthetic data (to test mathematical bounds under controlled noise) and a real-world Twitter dataset consisting of 500 "trending" and 500 "non-trending" topics.

Early detection performance and ROC curves on Twitter data

When applied to the Twitter data, the WMV algorithm demonstrated remarkable predictive power:

  • Early Detection: The algorithm predicted trending topics 79% of the time before Twitter officially declared them trends.
  • The "Early Advantage": On average, the system detected trends 1 hour and 26 minutes in advance of the official trending status.
  • Accuracy: The model achieved a 95% true positive rate with only a 4% false positive rate.

Crucially, the authors also established "nonasymptotic" guarantees, providing mathematical proof that the algorithm works reliably with a finite, practical amount of training data, rather than relying on the assumption of an infinite dataset.

Limitations and Future Work

While powerful, the model has a few limitations. It assumes a time series has a single, static label (e.g., "trend" or "not trend") and does not currently handle cases where a series might change labels over time. Additionally, the primary proofs assume each latent source is equally likely to appear. Finally, the current similarity measure handles simple time shifts but does not account for "time warping" (where a pattern might be stretched or compressed), which is common in other domains like speech recognition.

Summary updated

Abstract

For classifying time series, a nearest-neighbor approach is widely used in practice with performance often competitive with or better than more elaborate methods such as neural networks, decision trees, and support vector machines. We develop theoretical justification for the effectiveness of nearest-neighbor-like classification of time series. Our guiding hypothesis is that in many applications, such as forecasting which topics will become trends on Twitter, there aren't actually that many prototypical time series to begin with, relative to the number of time series we have access to, e.g., topics become trends on Twitter only in a few distinct manners whereas we can collect massive amounts of Twitter data. To operationalize this hypothesis, we propose a latent source model for time series, which naturally leads to a weighted majority voting" classification rule that can be approximated by a nearest-neighbor classifier. We establish nonasymptotic performance guarantees of both weighted majority voting and nearest-neighbor classification under our model accounting for how much of the time series we observe and the model complexity. Experimental results on synthetic data show weighted majority voting achieving the same misclassification rate as nearest-neighbor classification while observing less of the time series. We then use weighted majority to forecast which news topics on Twitter become trends, where we are able to detect such "trending topics" in advance of Twitter 79% of the time, with a mean early advantage of 1 hour and 26 minutes, a true positive rate of 95%, and a false positive rate of 4%."
BibTeX
@inproceedings{chen2013latent,
  author = {George H. Chen and Stanislav Nikolov and Devavrat Shah},
  title = {{A Latent Source Model for Nonparametric Time Series Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=rJNaFwW_-r},
}

Loading related content...

Figure