Correlated Equilibria for Approximate Variational Inference in MRFs

Luis E. Ortiz, Boshen Wang, Ze GongPGM 2020 · OpenReview

TL;DR

This paper bridges the gap between game theory and probabilistic graphical models by framing inference problems in Markov Random Fields (MRFs) as finding correlated equilibria in graphical games. This novel perspective allows for the development of new, game-theoretic inspired algorithms for approximate inference, which show competitive performance, particularly on challenging MRF instances.

What Problem Does This Paper Address?

Probabilistic graphical models (PGMs), like Markov Random Fields (MRFs), are powerful tools for representing complex systems and performing inference. However, exact inference in MRFs is often computationally intractable. While much research has focused on adapting PGM techniques to game theory, this paper explores the reverse: leveraging advances in computational game theory to improve inference in MRFs. Specifically, it addresses the challenge of finding efficient and effective approximate inference algorithms for MRFs by reformulating inference as the computation of correlated equilibria (CE) in specially constructed graphical games. This approach aims to overcome limitations of existing methods, especially on complex, "loopy" MRF structures.

Methods

The core of this paper is the novel connection established between MRF inference and correlated equilibria. The authors propose to model MRF inference problems as graphical potential games. They demonstrate that finding a correlated equilibrium in these games is equivalent to finding approximate solutions to inference problems in the corresponding MRFs.

Key methodological contributions include:

  • MRF-induced Graphical Games: Formulating graphical games where players' actions and payoffs are derived from the structure and potential functions of an MRF.
  • Equilibrium as Inference: Showing that finding correlated equilibria in these games corresponds to approximate inference (e.g., marginal probabilities) in the original MRF.
  • Game-Theoretic Algorithms for Inference: Adapting algorithms from game theory, specifically fictitious play and no-regret learning algorithms, to perform approximate inference in MRFs. This includes proposing a "hybrid" sequential fictitious play algorithm.
  • Theoretical Connections: Establishing theoretical links between concepts like correlated equilibria, Nash equilibria, and variational inference approximations (e.g., mean-field).

Datasets

The paper evaluates its proposed algorithms on two types of synthetic Ising models:

  • Synthetic Ising Models: Generated with varying edge-weight magnitudes and probabilities of attractive interactions on 8x8 and 12x12 grid graphs.
  • MNIST-based Ising Models: Derived from handwritten digit images (28x28 pixels) to represent more realistic settings for belief inference (specifically, confidence measures for de-noised pixel values).

Key Insights and Ideas

  • Game Theory as a New Lens for Inference: The most significant insight is that viewing MRF inference through the lens of game theory, specifically correlated equilibria, opens up new avenues for algorithmic development.
  • Fictitious Play for Inference: Game-theoretic learning algorithms like fictitious play, traditionally used for finding equilibria, can be adapted to provide effective approximate inference solutions for MRFs.
  • "Harder" MRF Instances: The paper identifies specific classes of Ising models (e.g., with constant edge-weight magnitudes and varied sign probabilities) that are more challenging for existing inference algorithms, highlighting the need for novel approaches.
  • Global vs. Local Approaches: The proposed global, game-theoretic approach shows promise, particularly on challenging instances where local methods might struggle.

Key Results

The experimental evaluation on synthetic and MNIST-based Ising models yielded several key findings:

  • Competitive Performance: The proposed fictitious play (fp (ce)) algorithm demonstrated competitive performance against established methods like TRW and Gibbs sampling, especially on "harder" synthetic Ising models.
  • "Mixed" and "Attractive" Cases: In "mixed" Ising models, Gibbs sampling (gs) generally performed best. In "attractive" models, TRW often performed well, but the proposed fp (ce) algorithm also showed strong results.
  • Challenging Instances: For Ising models with constant edge-weight magnitudes and varied sign probabilities, many algorithms, including TRW, struggled and performed no better than a simple baseline (estimating marginals as 0.5). In these cases, the proposed fp (ce) algorithm consistently outperformed the baseline.
  • MNIST Performance: On MNIST-derived Ising models, all algorithms performed well, with the proposed methods showing comparable results to established techniques.
  • Convergence: The fictitious play algorithm appeared to converge to reasonable estimates in a relatively low number of iterations.

Limitations and Future Work

  • Local vs. Global Solutions: The authors acknowledge that, like most variational approximation methods, their approach is primarily focused on finding locally optimal solutions.
  • Algorithm Complexity: While the proposed algorithms are relatively simple to implement, the paper notes that more complex algorithms like TRW can be computationally intensive.
  • Future Directions: The authors suggest several promising avenues for future research:
  • Exploring the exact relationship between MRF joint distributions and equilibrium points in induced games.
  • Investigating the use of algorithms like NashProp for approximate MSNE computation in loopy games.
  • Conducting more extensive experimental studies with complex implementations and rigorous comparisons.
  • Further exploring the synergy between game theory and probabilistic inference, potentially leading to novel contributions in both fields.

Summary updated

BibTeX
@inproceedings{ortiz2020correlated,
  author = {Luis E. Ortiz and Boshen Wang and Ze Gong},
  title = {{Correlated Equilibria for Approximate Variational Inference in MRFs}},
  booktitle = {PGM},
  year = {2020},
  url = {https://openreview.net/forum?id=Jjeq-CJwKP},
}
Figure