Probabilistic graphical models, such as Markov random fields (MRF),
exploit dependencies among random variables to model a rich family of joint probability distributions.
Inference algorithms, such as belief propagation (BP),
can effectively compute the marginal posteriors for decision making.
Nonetheless,
inferences involve sophisticated probability calculations and are difficult for humans to interpret.
Among all existing explanation methods for MRFs,
no method is designed for fair attributions of an inference outcome to elements on the MRF where the inference takes place.
Shapley values provide rigorous attributions but so far have not been studied on MRFs.
We thus define Shapley values for MRFs to capture both probabilistic and topological contributions of the variables on MRFs.
We theoretically characterize the new definition regarding independence, equal contribution, additivity, and submodularity.
As bruteforce computation of the Shapley values is challenging,
we propose GraphShapley, an approximation algorithm that exploits
the decomposability of Shapley values,
the structure of MRFs,
and the iterative nature of BP inference
to speed up the computation.
In practice,
we propose metaexplanations to explain the Shapley values and make them more accessible and trustworthy to human users.
On four synthetic and nine realworld MRFs,
we demonstrate that GraphShapley generates sensible and practical explanations.
more »
« less
Correlated Equilibria for Approximate Variational Inference in MRFs
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 advances in equilibrium computation for probabilistic inference. In particular, we present formulations of inference problems in Markov random fields (MRFs) as computation of equilibria in a certain class of gametheoretic graphical models. While some previous work explores this direction, we still lack a more precise connection between variational probabilistic inference in MRFs and correlated equilibria. This paper sharpens the connection, which helps us exploit relatively more recent theoretical and empirical results from the literature on algorithmic and computational game theory on the tractable, polynomialtime computation of exact or approximate correlated equilibria in graphical games with arbitrary, loopy graph structure. Our work discusses how to design new algorithms with equally tractable guarantees for the computation of approximate variational inference in MRFs. In addition, inspired by a previously stated gametheoretic view of treereweighted messagepassing techniques for belief inference as a zerosum game, we propose a different, generalsum potential game to design approximate fictitiousplay techniques. Empirical evaluations on synthetic experiments and on an application to soft denoising on realworld image datasets illustrate the performance of our proposed approach and shed some light on the conditions under which the resulting belief inference algorithms may be most effective relative to standard stateoftheart methods.
more »
« less
 NSFPAR ID:
 10294335
 Editor(s):
 Jaeger, Manfred; Nielsen, Thomas Dyhre
 Date Published:
 Journal Name:
 Proceedings of Machine Learning Research
 Volume:
 138
 ISSN:
 26403498
 Page Range / eLocation ID:
 329  340
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Statistical relational learning models are powerful tools that combine ideas from firstorder logic with probabilistic graphical models to represent complex dependencies. Despite their success in encoding large problems with a compact set of weighted rules, performing inference over these models is often challenging. In this paper, we show how to effectively combine two powerful ideas for scaling inference for large graphical models. The first idea, lifted inference, is a wellstudied approach to speeding up inference in graphical models by exploiting symmetries in the underlying problem. The second idea is to frame Maximum a posteriori (MAP) inference as a convex optimization problem and use alternating direction method of multipliers (ADMM) to solve the problem in parallel. A wellstudied relaxation to the combinatorial optimization problem defined for logical Markov random fields gives rise to a hingeloss Markov random field (HLMRF) for which MAP inference is a convex optimization problem. We show how the formalism introduced for coloring weighted bipartite graphs using a color refinement algorithm can be integrated with the ADMM optimization technique to take advantage of the sparse dependency structures of HLMRFs. Our proposed approach, lifted hingeloss Markov random fields (LHLMRFs), preserves the structure of the original problem after lifting and solves lifted inference as distributed convex optimization with ADMM. In our empirical evaluation on realworld problems, we observe up to a three times speed up in inference over HLMRFs.more » « less

One of the primary challenges in graphical models is inference, or reconstructing a marginal probability from the graphical model’s factorized representation. While tractable for some graphs, the cost of inference grows exponentially with the graphical model’s complexity, necessitating approximation for more complex graphs. For interactive applications, latency is the dominant concern, making approximate inference the only feasible option. Unfortunately, approximate inference can be wasteful for interactive applications, as exact inference can still converge faster, even for moderately complex inference problems. In this paper, we propose a new family of convergent inference algorithms (CIAs) that bridge the gap between approximations and exact solutions, providing early, incrementally improving approximations that become exact after a finite period of time. We describe two specific CIAs based on a cryptographic technique called linear congruential generators, including a novel incremental join algorithm for dense relations called Leaky Joins. We conclude with experiments that demonstrate the utility of Leaky Joins for convergent inference: On both synthetic and realworld probabilistic graphical models, Leaky Joins converge to exact marginal probabilities almost as fast as state of the art exact inference algorithms, while simultaneously achieving approximations that are almost as good as state of the art approximation algorithms.more » « less

This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem [Formula: see text] as a largescale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worstcase attacks. We show that optimal solutions of [Formula: see text] can be obtained from the equilibria of a largescale zerosum game. Our equilibrium analysis involves both gametheoretic and combinatorial arguments and leads to a computationally tractable approach to solve [Formula: see text]. First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSPbased solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in largescale networks by strategically positioning a small number of detectors.more » « less

null (Ed.)Sumproduct networks (SPN) are knowledge compilation models and are related to other graphical models for efficient probabilistic inference such as arithmetic circuits and AND/OR graphs. Recent investigations into generalizing SPNs have yielded sumproductmax networks (SPMN) which offer a datadriven alternative for decision making that has predominantly relied on handcrafted models. However, SPMNs are not suited for decisiontheoretic planning which involves sequential decision making over multiple time steps. In this paper, we present recurrent SPMNs (RSPMN) that learn from and model decisionmaking data over time. RSPMNs utilize a template network that is unfolded as needed depending on the length of the data sequence. This is significant as RSPMNs not only inherit the benefits of SPNs in being data driven and mostly tractable, they are also well suited for planning problems. We establish soundness conditions on the template network, which guarantee that the resulting SPMN is valid, and present a structure learning algorithm to learn a sound template. RSPMNs learned on a testbed of data sets, some generated using RDDLSim, yield MEUs and policies that are close to the optimal on perfectlyobserved domains and easily improve on a recent batchconstrained RL method, which is important because RSPMNs offer a new modelbased approach to offline RL.more » « less