Correlated Equilibria for Approximate Variational Inference in MRFs
Correlated Equilibria for Approximate Variational Inference in MRFs
复制标题
DOI：
--
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Luis E. Ortiz;Ze Gong
中科院分区：
文献类型：
--
作者：
Luis E. Ortiz;Ze Gong
几乎所有博弈论图形模型的工作都反映了以前概率图形模型的工作。我们的工作考虑了相反的方向：利用概率推理的平衡计算的最新进展。我们提出了在马尔可夫随机场（MRFs）的推理问题的配方在一定的一类博弈论图形模型的平衡计算。我们具体地建立了MRF变分概率推理和相关平衡之间的精确连接。没有以前的工作利用最近的理论和实证结果，从文献中的算法和计算博弈论上的听话，多项式时间计算的精确或近似相关的平衡，在图形游戏任意，循环图结构。我们讨论了如何设计新的算法，同样易于处理的保证MRF的近似变分推理的计算。此外，受先前所述的博弈论观点的启发，最先进的树重新加权（TRW）的消息传递技术的信念推理为零和博弈，我们提出了一个不同的，一般和潜在的游戏设计近似虚拟播放技术。我们进行合成实验，评估我们提出的近似算法与标准方法和TRW的几类经典伊辛模型（即，二进制随机变量）。我们还使用从MNIST数据集学习的伊辛模型来评估算法。我们的实验表明，我们的全球性的方法是有竞争力的，特别是闪耀在一类伊辛模型与恒定的，“非常有吸引力的”边权重，它往往是优于所有其他的替代品，我们评估。除了一个明显的例外，我们更本地化的方法没有那么有效。然而，公平地说，几乎所有的替代方案通常都不比一个简单的基线好：估计0.5。
Almost all of the work in graphical models for game theory has mirrored previous work in probabilistic graphical models. Our work considers the opposite direction: Taking advantage of recent advances in equilibrium computation for probabilistic inference. We present formulations of inference problems in Markov random fields (MRFs) as computation of equilibria in a certain class of game-theoretic graphical models. We concretely establishes the precise connection between variational probabilistic inference in MRFs and correlated equilibria. No previous work exploits recent theoretical and empirical results from the literature on algorithmic and computational game theory on the tractable, polynomial-time computation of exact or approximate correlated equilibria in graphical games with arbitrary, loopy graph structure. We discuss how to design new algorithms with equally tractable guarantees for the computation of approximate variational inference in MRFs. Also, inspired by a previously stated game-theoretic view of state-of-the-art tree-reweighed (TRW) message-passing techniques for belief inference as zero-sum game, we propose a different, general-sum potential game to design approximate fictitious-play techniques. We perform synthetic experiments evaluating our proposed approximation algorithms with standard methods and TRW on several classes of classical Ising models (i.e., with binary random variables). We also evaluate the algorithms using Ising models learned from the MNIST dataset. Our experiments show that our global approach is competitive, particularly shinning in a class of Ising models with constant, "highly attractive" edge-weights, in which it is often better than all other alternatives we evaluated. With a notable exception, our more local approach was not as effective. Yet, in fairness, almost all of the alternatives are often no better than a simple baseline: estimate 0.5.