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. 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.