A Novel Approach for Constrained Optimization in Graphical Models

Abstract

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Rouhani et al. "A Novel Approach for Constrained Optimization in Graphical Models." Neural Information Processing Systems, 2020.

Markdown

[Rouhani et al. "A Novel Approach for Constrained Optimization in Graphical Models." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/rouhani2020neurips-novel/)

BibTeX

@inproceedings{rouhani2020neurips-novel,
  title     = {{A Novel Approach for Constrained Optimization in Graphical Models}},
  author    = {Rouhani, Sara and Rahman, Tahrima and Gogate, Vibhav},
  booktitle = {Neural Information Processing Systems},
  year      = {2020},
  url       = {https://mlanthology.org/neurips/2020/rouhani2020neurips-novel/}
}