Source-linked AI summary
Streaming Variational Bayes
Tamara Broderick, Nicholas Boyd, Andre Wibisono, Ashia C. Wilson, Michael I. Jordan
TL;DR
Large streaming datasets challenge Bayesian inference because complex models do not generally fit streaming time and memory restrictions. SDA-Bayes combines streaming updates with distributed and asynchronous computation through a user-specified approximation primitive, using variational Bayes for LDA. The framework improves runtime without performance cost in its full form and addresses SVI’s fixed-dataset-size limitation, while asynchronous updates introduce additional approximation and EP performs poorly for LDA.
Problem
Complex Bayesian models generally do not satisfy the time and memory restrictions of large streaming datasets, while SVI targets a fixed, pre-specified number of data points.
Method
SDA-Bayes recursively updates an approximate posterior over minibatches and supports distributed and asynchronous computation through a user-specified approximation primitive, using VB for LDA.
Results
Full SDA-Bayes improves runtime with no performance cost, and the framework outperforms SVI on obtaining posteriors based on documents seen so far rather than a fixed document count.
Takeaways & Limitations
SDA-Bayes provides approximate Bayesian posteriors indexed by the number of documents processed, including in streaming settings where SVI is designed for a pre-chosen data size.
Takeaways & Limitations
Asynchronous updates add approximation because the master posterior can change while a worker computes, and an EP primitive was not effective for LDA.
Abstract
from arXiv · showhide
We present SDA-Bayes, a framework for (S)treaming, (D)istributed, (A)synchronous computation of a Bayesian posterior. The framework makes streaming updates to the estimated posterior according to a user-specified approximation batch primitive. We demonstrate the usefulness of our framework, with variational Bayes (VB) as the primitive, by fitting the latent Dirichlet allocation model to two large-scale document collections. We demonstrate the advantages of our algorithm over stochastic variational inference (SVI) by comparing the two after a single pass through a known amount of data---a case where SVI may be applied---and in the streaming setting, where SVI does not apply.
1 Introduction
SDA-Bayes addresses the difficulty of applying Bayesian inference to large streaming data by combining scalable approximation with genuinely sequential posterior updates. It extends this framework to distributed and asynchronous computation while using variational Bayes as the paper’s primary primitive.
- Large streaming datasets impose time and memory constraints that complex hierarchical Bayesian models generally cannot meet.Existing scalable procedures often use simple models and non-Bayesian inference, leaving hierarchical modeling and coherent uncertainty treatment difficult in the Big Data setting.
- Stochastic variational inference applies variational Bayes to large-scale topic modeling but targets a posterior for a fixed, pre-specified number of documents D.The algorithm uses a lower-bound objective and stochastic gradient updates based on the conceptual existence of a full dataset of size D.
- SDA-Bayes instead produces an approximate posterior for each processed collection of D′ data points, rather than only for a pre-specified final dataset size D.The framework returns to recursive Bayesian updating while allowing each update to be an approximation such as VB.
- The framework is designed to support streaming, distributed, and asynchronous computation, matching capabilities of modern computer architectures.The paper argues that streaming VB naturally lends itself to distributed and asynchronous implementations.
2 Streaming, distributed, asynchronous Bayesian updating
The framework recursively updates approximate posteriors over minibatches, then distributes or asynchronously combines local updates in a shared exponential-family representation. Its preferred asynchronous design uses the latest master posterior as each worker’s prior, improving practice while adding approximation error.
- Streaming Bayesian updating: Streaming Bayesian updating treats the posterior after one minibatch as the prior for the next, avoiding revisits to old data.With an approximation primitive A, the recursive update is q_b(Θ) = A(C_b, q_b−1(Θ)); it is exact when A returns the Bayes posterior.
- Distributed Bayesian updating: Minibatch approximate posteriors can be computed in parallel and combined by summing their natural-parameter increments with the original prior parameter.This produces the exponential-family parameter of the full posterior approximation.
- Exponential-family representation: The method assumes the prior and approximating distributions belong to the same exponential family, making the normalizing constant readily available.Conjugacy in the generative model, or a restricted form for the true intermediate or final posterior, is not required.
- Asynchronous Bayesian updating: Asynchronous workers process minibatches and return posterior increments, while the master adds each received increment immediately.The preferred scheme copies the current master posterior locally before each worker computes its update.
- Asynchronous Bayesian updating: Using the latest posterior as a worker’s prior better matches streaming updates but adds approximation because the master may change during computation.Despite this loss of exactness, the authors report that the latter framework performs better in practice.
- Framework scope: SDA-Bayes is a general framework that accepts a user-specified local approximation primitive and a prior over global parameters.The paper uses variational Bayes as its preferred primitive.
3 Case study: latent Dirichlet allocation
LDA models documents as mixtures of latent topics, with topic-word and document-topic distributions inferred through approximate posterior methods. The case study compares VB, SVI, SSU, and SDA-Bayes-compatible primitives for scalable and single-pass inference.
- LDA model: LDA represents each topic as a distribution over vocabulary words and each document as an admixture of topics.
- LDA model: The LDA posterior over global topics, document-specific topic mixtures, and latent word topics is intractable to normalize, so it must be approximated.
- Mean-field variational Bayes: VB approximates the posterior with factorized Dirichlet distributions for topics and document mixtures, plus categorical distributions for latent word topics.
- Mean-field variational Bayes: VB finds variational parameters by minimizing KL divergence from the true posterior, typically using coordinate descent until convergence.
- Algorithm comparison: VB repeatedly passes through stored data, whereas SVI makes a single pass and SSU is streaming, distinguishing their data-access patterns.
- Single-pass algorithms: SVI applies stochastic gradient descent to the same VB optimization problem, while its target posterior depends on a prespecified number of documents D.
- Single-pass algorithms: SSU updates local parameters as minibatches arrive and adds their sufficient-statistics terms to the current global parameter estimate; it equals SDA-Bayes with one VB global iteration.
4 Evaluation
The evaluation compares SDA-Bayes with SVI and SSU on Wikipedia and Nature, measuring held-out log predictive probability and running time. SDA-Bayes preserves performance while enabling streaming and distributed computation, whereas SVI depends on fixed data-size and step-size choices.
- Experimental setup: Higher log predictive probability indicates better held-out-word prediction, and Table 1 compares SDA-Bayes, SVI, and SSU on this metric and running time.The comparison includes SDA-Bayes with 32 threads and 1 thread.
- Experimental setup: Wikipedia and Nature provide large, topic-diverse LDA evaluation corpora, with 3,611,558 and 351,525 training documents, respectively.The experiments hold out 10,000 Wikipedia documents and 1,024 Nature documents for testing.
- Single-pass comparison: With one thread, SDA-Bayes incurs only a small performance loss relative to SVI, while SSU performs much worse; SVI is faster in this single-pass setting.This comparison evaluates a setting where a known total data size permits applying SVI.
- Distributed computation: Full SDA-Bayes improves run time with no performance cost when using 32 threads instead of the single-thread configuration.The reported minibatch size accounts for the total data points processed per round across threads.
- Distributed computation: With minibatch size fixed, increasing threads from 1 to 32 produces dramatic run-time improvement and slight performance improvement for SDA-Bayes.The experiments compare thread counts {1, 2, 4, 8, 16, 32}.
- Streaming comparison: SVI is sensitive to total data size D and learning step size, while step-size cross-validation requires multiple data passes and is unsuitable for streaming.The evaluation varies D from 0.01 to 100 times the true value and examines step-size parameters (τ0, κ).
- Primitive comparison: The EP primitive is ineffective for LDA, reaching stabilized log predictive probabilities of around −7.95 on Wikipedia and −8.02 on Nature after more than 91 and 97 hours.The authors leave open whether SDA-Bayes with EP may work in domains where EP is effective.
5 Discussion
The discussion presents SDA-Bayes as a general framework for streaming, distributed, asynchronous approximate Bayesian inference. Using VB for LDA on Wikipedia and Nature, it reports advantages over SVI and SSU, especially for posteriors indexed by documents processed so far.
- Framework: SDA-Bayes performs streaming updates to an approximate Bayesian posterior using a user-specified local approximation primitive.The framework is demonstrated with variational Bayes as the primitive.
- Framework: The framework supports streaming, distributed, and asynchronous computation and is demonstrated by fitting LDA to the Wikipedia and Nature corpora.Its generality comes from allowing different local approximation procedures and requiring a prior on global parameters.
- Implications: SDA-Bayes is advantageous when approximations are needed for the number of documents processed so far rather than for a fixed preselected number of documents.The discussion contrasts this focus with SVI and SSU.
A.1 Batch VB
Batch variational Bayes seeks a constrained distribution q_D that best approximates the true posterior p_D. The optimization typically adjusts q_D’s parameters because a closed-form optimum is unavailable.
- VB minimizes the KL divergence between the approximating distribution q_D and the true posterior p_D.
- The approximating distribution q_D usually has a constrained form, so optimization searches over its parameters.
- For LDA, λ describes topics, γ describes document topic proportions, and φ describes word-to-topic assignments.
A.1.1 Evidence lower bound
VB can optimize either the KL-divergence formulation or its equivalent evidence lower bound. For LDA, the ELBO is expressed using model variables, variational parameters, and fixed hyperparameters.
- Maximizing the ELBO is equivalent to minimizing the KL divergence because the marginal likelihood is constant in q_D.
- The LDA ELBO uses model parameters β, θ, z, data w, and fixed hyperparameters η and α.
- ELBO(λ, γ, φ) is the expected log joint probability minus the expected log variational distribution.
- The required expectations can be evaluated using the digamma function ψ and trigamma function ψ1.
A.1.2 Coordinate ascent
Coordinate ascent maximizes the LDA ELBO by iteratively updating λ, γ, and φ. Local parameters are iterated to convergence before the global topic parameter is updated, and minibatch updates produce streaming posterior parameters.
- A.1.2 Coordinate ascent: Coordinate ascent maximizes the ELBO by updating λ, γ, and φ one variational-parameter dimension at a time.
- Variational parameter λ: For λ, setting the ELBO gradient to zero yields updates based on word-token assignments represented by φ.
- Variational parameter λ: Using word counts n_dv, the λ update can be written in terms of occurrences of vocabulary type v in document d.
- Variational parameter γ: For γ, fixing λ and φ allows document-specific updates obtained by setting the ELBO gradient to zero.
- Update schedule: In practice, φ and γ are iterated until convergence, followed by an update to the global parameter λ.
- BatchVB and streaming updates: BatchVB processes minibatches using a prior on topic parameters β and summarizes each resulting posterior with parameters λ^(b).
- Streaming VB: Streaming VB initializes λ^(0) with η and processes each document minibatch sequentially.
- SDA-Bayes with VB: SDA-Bayes maintains λ^(post) at a master while workers apply local minibatch computations and asynchronous updates.
B.1 Batch EP
Batch EP approximates the collapsed LDA posterior over topic and document proportions through iterative, word-level updates. It uses moment matching and reports a slower token-level variant alongside the main type-level algorithm.
- Collapsed posterior: EP approximates the collapsed posterior after integrating out word assignments z.
- Variational distribution: The EP variational distribution uses Dirichlet factors for topic parameters β and document proportions θ.
- Optimization problem: EP minimizes reverse KL divergence by iteratively fixing most factors and optimizing parameters associated with one document-word pair.
- Local updates: Each EP iteration removes one word contribution, replaces it with the corresponding topic-mixture term, and updates global and document parameters.
- Moment matching: The moment-matching equations can be solved by Newton’s method or by matching the first and average second moments.
- Algorithm choice: The reported main-text results use type-level EP updates rather than the modified token-level algorithm.
- Algorithm choice: The token-level variant requires many more iterations, is much slower, and performs worse than SDA-Bayes or SVI despite better predictive performance than type-level EP.For Nature, log predictive probability leveled off at about −7.96 versus −8.02 for the reported algorithm.
B.2 SDA-Bayes EP
SDA-Bayes incorporates batch EP for LDA in nearly the same way as batch VB, because both use compatible Dirichlet priors and approximate posteriors. The framework also extends beyond EP and VB.
- Batch EP and batch VB fit SDA-Bayes in nearly identical ways for LDA.The similarity follows because SDA-Bayes works directly with a batch approximation algorithm in the required form.
- For fixed α, BatchEP takes a prior on topic parameters β and a document minibatch as input.
- Streaming EP for LDA is the same as the corresponding streaming VB algorithm, replacing the batch VB primitive with batch EP.
- Asynchronous distributed updates can be applied to the batch EP primitive and LDA model within SDA-Bayes.
- SDA-Bayes applies more generally to approximation primitives beyond EP and VB.