\mathttSpectralLeader : Online Spectral Learning for Single Topic Models

Tong Yu, Branislav Kveton, Zheng Wen, Hung Hai Bui, Ole J. MengshoelECML/PKDD 2018 · OpenReview

TL;DR

This paper introduces SpectralLeader, a novel online learning algorithm for latent variable models that guarantees convergence to the global optimum, unlike traditional online EM methods that can get stuck in local optima. SpectralLeader achieves this by adapting spectral methods for online learning and demonstrates competitive or superior performance to tuned online EM in both synthetic and real-world experiments.

What Problem Does This Paper Address?

Learning latent variable models (LVMs) is crucial for understanding underlying structures in data, with applications ranging from natural language processing to computer vision. Traditionally, LVMs are learned in an "offline" setting, where the entire dataset is available at once. However, many real-world scenarios involve data arriving as a stream, requiring "online" learning. The dominant online approach, online Expectation-Maximization (EM), is computationally efficient but suffers from a significant drawback: it often converges to a local optimum, leading to suboptimal model performance. This paper addresses the challenge of learning LVMs online while guaranteeing convergence to the globally optimal solution, a feat not achieved by existing online EM methods.

Methods

The core innovation is SpectralLeader, an online learning algorithm that adapts the spectral method for LVMs to an online setting. The spectral method, known for its ability to find global optima in offline settings, typically relies on tensor decomposition of moments of the data. SpectralLeader ingeniously translates this to an online scenario by:

  • Framing as a Regret Minimization Problem: The goal is to minimize the cumulative difference between the model's predictions and the best possible model in hindsight.
  • Adapting Spectral Techniques: It uses techniques like eigendecomposition and tensor decomposition on approximations of data moments derived from a limited set of past observations.
  • Reservoir Sampling: To manage computational and memory costs associated with processing an ever-growing stream of data, SpectralLeader employs reservoir sampling. This allows it to maintain a fixed-size representative sample of past data, enabling efficient computation of the necessary moments and tensors.

This approach contrasts with online EM, which iteratively updates parameters based on current data without a global optimality guarantee.

Datasets

The paper evaluates SpectralLeader on:

  • Synthetic Datasets: Two types of synthetic data are used:
  • Stochastic Setting: Topics are sampled independently and identically distributed (i.i.d.) from a fixed distribution.
  • Non-Stochastic Setting: Topics are strongly correlated over time, mimicking more realistic scenarios where user interests or trends evolve.
  • Real-World Datasets:
    • Newspapers Data: Collected over multiple years, exhibiting changing topic distributions.
  • Twitter Data: Collected during the 2016 US elections, also showing temporal shifts in topic distributions.

These datasets are preprocessed to a vocabulary of 500 most frequent words, with K=5 topics.

Key Insights and Ideas

  • Global Optimality in Online Learning: The most significant insight is demonstrating that it's possible to achieve global optimality guarantees in online learning for LVMs, a problem previously thought to be intractable for online methods.
  • Spectral Methods for Online Learning: The paper successfully bridges the gap between offline spectral methods (known for global convergence) and online learning, showing their applicability in dynamic data streams.
  • Reservoir Sampling for Efficiency: The introduction of reservoir sampling is crucial for making spectral methods computationally feasible in an online setting, preventing memory and computation from growing unboundedly.
  • Regret as a Performance Metric: Framing the problem as regret minimization provides a theoretically sound way to evaluate online algorithms, measuring their performance against the best possible offline solution.

Key Results

  • Theoretical Guarantees: SpectralLeader is theoretically proven to converge to the global optimum and has a sublinear upper bound on its n-step regret.
  • Competitive Performance: In synthetic experiments, SpectralLeader performs similarly to or better than the stepwise EM, even when the latter is carefully tuned with its best parameters.
  • Robustness to Hyperparameters: Unlike stepwise EM, which is highly sensitive to its tuning parameters (step-size reduction power $\alpha$ and mini-batch size $m$), SpectralLeader is much less sensitive, requiring minimal parameter tuning.
  • Adaptation to Non-Stochastic Settings: SpectralLeader shows strong adaptation capabilities in non-stochastic settings where topics are correlated over time, outperforming stepwise EM.
  • Real-World Efficacy: On real-world datasets (Newspapers and Twitter), SpectralLeader demonstrates competitive performance, particularly under the log-likelihood metric, offering good results without extensive parameter tuning.

Limitations and Future Work

  • Model Complexity: The current work focuses on single topic models. The authors express a desire to extend the method to more complex latent variable models, such as Hidden Markov Models (HMMs) and Latent Dirichlet Allocation (LDA).
  • Parameter Tuning: While SpectralLeader is less sensitive to parameters than stepwise EM, some parameters (like the reservoir size $m$) still require careful selection for optimal performance, especially in noisy settings. The paper discusses the trade-offs between reservoir size and regret.
  • Noisy Settings: The analysis in the paper covers both noise-free and noisy settings. While the theoretical bounds are established, the practical implications and performance in highly noisy real-world scenarios might warrant further investigation.

Summary updated

Abstract

We study the problem of learning a latent variable model online from a stream of data. Latent variable models are popular because they can explain observed data through unobserved concepts. These models have traditionally been studied in the offline setting. In the online setting, online expectation maximization (EM) is arguably the most popular approach for learning latent variable models. Although online EM is computationally efficient, it typically converges to a local optimum. In this work, we develop a new online learning algorithm for latent variable models, which we call $$\mathtt{SpectralLeader}$$ . $$\mathtt{SpectralLeader}$$ converges to the global optimum, and we derive a sublinear upper bound on its n-step regret in a single topic model. In both synthetic and real-world experiments, we show that $$\mathtt{SpectralLeader}$$ performs similarly to or better than online EM with tuned hyper-parameters.
BibTeX
@inproceedings{yu2018mathttspectralleader,
  author = {Tong Yu and Branislav Kveton and Zheng Wen and Hung Hai Bui and Ole J. Mengshoel},
  title = {{\textbackslash\{\}mathttSpectralLeader : Online Spectral Learning for Single Topic Models}},
  booktitle = {ECML/PKDD},
  year = {2018},
  url = {https://openreview.net/forum?id=nirI5B_tHu},
}
Figure