A Novel Approach for Constrained Optimization in Graphical Models

We consider the following constrained maximization problem in discrete probabilistic graphical models (PGMs). Given two (possibly identical) PGMs M 1 and M 2 defined over the same set of variables and a real number q, find an assignment of values to all variables such that the probability of the assignment is maximized w.r.t. M 1 and is smaller than q w.r.t. M 2 . We show that several explanation and robust estimation queries over graphical models are special cases of this problem. We propose a class of approximate algorithms for solving this problem. Our algorithms are based on a graph concept called k-separator and heuristic algorithms for multiple choice knapsack and subset-sum problems. Our experiments show that our algorithms are superior to the following approach: encode the problem as a mixed integer linear program (MILP) and solve the latter using a state-of-the-art MILP solver such as SCIP.