Rigorous Explanation of Inference on Probabilistic Graphical Models
This addresses the need for interpretable AI in decision-making by providing a rigorous explanation method for graphical models, though it is incremental as it builds on existing Shapley value and belief propagation frameworks.
The paper tackles the problem of interpreting inference outcomes in probabilistic graphical models like Markov random fields, proposing GraphShapley to compute Shapley values efficiently, and demonstrates sensible explanations on nine graphs.
Probabilistic graphical models, such as Markov random fields (MRF), exploit dependencies among random variables to model a rich family of joint probability distributions. Sophisticated inference algorithms, such as belief propagation (BP), can effectively compute the marginal posteriors. Nonetheless, it is still difficult to interpret the inference outcomes for important human decision making. There is no existing method to rigorously attribute the inference outcomes to the contributing factors of the graphical models. Shapley values provide an axiomatic framework, but naively computing or even approximating the values on general graphical models is challenging and less studied. We propose GraphShapley to integrate the decomposability of Shapley values, the structure of MRFs, and the iterative nature of BP inference in a principled way for fast Shapley value computation, that 1) systematically enumerates the important contributions to the Shapley values of the explaining variables without duplicate; 2) incrementally compute the contributions without starting from scratches. We theoretically characterize GraphShapley regarding independence, equal contribution, and additivity. On nine graphs, we demonstrate that GraphShapley provides sensible and practical explanations.