Approximate Decentralized Bayesian Inference

Trevor Campbell, Jonathan P. HowUAI 2014 · OpenReview

TL;DR

This paper introduces AMPS, a novel algorithm for decentralized Bayesian inference that effectively handles models with parameter permutation symmetry. AMPS allows distributed agents to combine their local approximate posteriors, overcoming limitations of previous methods and achieving better performance on complex models.

What Problem Does This Paper Address?

Machine learning algorithms are increasingly being deployed in decentralized settings, such as sensor networks, where data is collected and processed by multiple agents without a central coordinator. This presents a challenge for Bayesian inference, which typically relies on a global view of the data and model. While distributed methods exist, they often assume a central hub. Decentralized methods, which avoid this assumption, face difficulties due to asynchronous communication, lack of a shared state, and potential agent failures. A key challenge in decentralized Bayesian inference, particularly for models with symmetries (like Gaussian mixture models or topic models), is how to combine local approximate posteriors from different agents. Naive combination methods can lead to poor approximations because they fail to account for the fact that different agents might have learned different, but equally valid, orderings of symmetric parameters.

Methods

The paper proposes the Approximate Merging of Posteriors with Symmetry (AMPS) algorithm. The core idea is to first have each agent perform variational inference on its local data to obtain an approximate posterior. Then, instead of directly combining these posteriors, AMPS introduces a "symmetrization" step. This step accounts for parameter permutation symmetry by effectively averaging over possible permutations of parameters within each agent's posterior. After this symmetrization, the agents combine their posteriors using a modified Bayesian update rule that explicitly considers the possible pairings of symmetric parameters across agents. The combination objective is formulated as a maximum weight bipartite matching problem, which can be solved approximately. This approach allows for asynchronous communication and is robust to dynamic network topologies and agent failures.

Datasets

  • Synthetic Gaussian Mixture Model: Used to demonstrate the failure of naive methods and the success of AMPS in handling parameter permutation symmetry.
  • 20 Newsgroups dataset: Used for evaluating decentralized Latent Dirichlet Allocation (LDA).
  • Synthetic Latent Feature Assignment Model: Used to evaluate AMPS on a model with feature permutation symmetry.
  • Yale and Caltech faces datasets: Used for evaluating AMPS on a real-world latent feature assignment task.

Key Insights and Ideas

  • Symmetry is Crucial: Approximate inference methods (like variational inference) can break symmetries present in the true posterior, leading to poor decentralized approximations when combining posteriors.
  • Symmetrization as a Preprocessing Step: Explicitly accounting for parameter permutation symmetry before combining posteriors is key to achieving accurate decentralized inference in models with such symmetries.
  • Decentralized Inference is Harder: Unlike distributed methods, decentralized approaches must cope with asynchronous communication and lack of a global state, making robust combination strategies essential.
  • AMPS Offers Flexibility: The algorithm can be combined with existing streaming variational inference methods and can handle dynamic network structures.

Key Results

  • Gaussian Mixture Model: AMPS significantly outperforms the naive decentralized approach, producing a posterior that is a much better approximation of the true batch posterior, especially when parameter permutation symmetry is present.
  • Latent Dirichlet Allocation (LDA): AMPS achieves better test log likelihoods compared to individual agent posteriors and is competitive with batch methods, especially as the number of agents increases. It also exhibits lower variance in performance.
  • Latent Feature Assignment: AMPS discovers latent features with lower error and better predictive log likelihoods compared to the naive approach, and is comparable to batch methods.
  • Computational Performance: AMPS generally offers advantages in computational performance and predictive test likelihood over previous batch and distributed methods, particularly in scenarios with many agents.

Limitations and Future Work

  • Computational Cost: The optimization step in AMPS can become computationally expensive as the number of agents increases. The authors suggest exploring hierarchical optimization schemes to mitigate this.
  • Bayesian Nonparametrics: Extending AMPS to handle models where the number of latent parameters is unknown (e.g., Bayesian nonparametric models) is an area for future research.
  • Bounds on Performance: While AMPS performs well in practice, finding theoretical bounds on its performance relative to the true optimal solution would be beneficial.
  • Streaming Inference: While AMPS can be used with streaming methods, it is not inherently a streaming procedure. The authors suggest that periodically merging posteriors using AMPS could address this.

Summary updated

BibTeX
@inproceedings{campbell2014approximate,
  author = {Trevor Campbell and Jonathan P. How},
  title = {{Approximate Decentralized Bayesian Inference}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2014},
  url = {https://openreview.net/forum?id=UDQGwkjQBy},
}
Figure