An Empirical Evaluation of Algorithms for Computing Equilibria in Games for Approximate Inference in Large Dimensional Probabilistic Graphical Models

Probabilistic graphical models;Belief inference;Game theory;Equilibrium computation;Ising models;Computer science;Computer and Information Science, College of Engineering & Computer Science

Wang, BoshenMaxim, Bruce ;

University of Michigan

关键词: Probabilistic graphical models;    Belief inference;    Game theory;    Equilibrium computation;    Ising models;    Computer science;    Computer and Information Science, College of Engineering & Computer Science;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/140771/ms_draft%20%282%29.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Work in graphical models for game theory typically borrows from results in probabilistic graphical models. In this work, we instead consider the opposite direction. By using recent advances in equilibrium computation, we propose game-theoretic inspired, practical methods to perform probabilistic inference. We perform synthetic experiments using several different classes of Ising models, in order to evaluate our proposed approximation algorithms along with existing methods in the probabilistic graphical model literature. We also perform experiments using Ising models learned from the popular MNIST dataset. Our experiments show that the game-theoretic inspired methods are competitive with current state-of-the-art algorithms such as tree-reweighed message passing, and even consistently outperform said algorithms in certain cases.