Invited Talk by V. Gogate - Algorithms for Solving The Constrained Most Probable Explanation Problem
Channel: TPM Workshop
Date: 2022-09-01

Invited Talk by Vibhav Gogate (UT Dallas, USA) at the 5th Workshop on Tractable Probabilistic Modeling @ UAI 2022, Eindhoven, The Netherlands (05/08/2022).

Title: Algorithms for Solving The Constrained Most Probable Explanation Problem

Abstract: Recently there has been growing interest in developing probabilistic models that are robust to minor perturbations in input and are explainable in that they are able to explain why they made a particular decision to a user. In this talk, I will describe a new unifying optimization task called constrained most probable explanation (CMPE), and show that the two aforementioned tasks, making models robust and explainable, can be reduced to CMPE. I will show that CMPE is strongly NP-hard in general on arbitrary probabilistic models, but only weakly NP-hard on probabilistic models having small k-separators (a sub-class of tractable models that admit poly-time marginal inference). The main virtue of this weakly NP-hard property is that we can leverage it to derive efficient cutset sampling and local search approximations for lower bounding the optimal value of CMPE. For upper bounding, I will present efficient approaches that combine graph-based partitioning techniques with approximations developed in the literature on knapsack problems. These upper bounding techniques are guaranteed to be better than linear programming based bounds on probabilistic models that admit tractable marginal inference and have much smaller computational complexity. I will end my talk by presenting experimental results and applications as well as avenues for future work. (Joint work with Sara Rouhani, Rohith Peddi and Tahrima Rahman)

Bio: Vibhav Gogate is an Associate Professor in the Computer Science Department at the University of Texas at Dallas. He got his Ph.D. at University of California, Irvine in 2009 and then did a two-year post-doc at University of Washington. His research interests are in AI, machine learning and data mining. His ongoing focus is on probabilistic graphical models; their first-order logic based extensions such as Markov logic and probabilistic programming; tractable probabilistic models and explainable AI. He is a recipient of the national science foundation CAREER award and the co-winner of 2010 and 2012 UAI inference competitions.