Exact MAP Inference by Avoiding Fractional Vertices

Erik M. Lindgren, Alexandros G. Dimakis, Adam Klivans
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2120-2129, 2017.

Abstract

Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice and it is a major open question is to explain why this is true. We give a natural condition under which we can provably perform MAP inference in polynomial time—we require that the number of fractional vertices in the LP relaxation exceeding the optimal solution is bounded by a polynomial in the problem size. This resolves an open question by Dimakis, Gohari, and Wainwright. In contrast, for general LP relaxations of integer programs, known techniques can only handle a constant number of fractional vertices whose value exceeds the optimal solution. We experimentally verify this condition and demonstrate how efficient various integer programming methods are at removing fractional solutions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-lindgren17a, title = {Exact {MAP} Inference by Avoiding Fractional Vertices}, author = {Erik M. Lindgren and Alexandros G. Dimakis and Adam Klivans}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2120--2129}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/lindgren17a/lindgren17a.pdf}, url = {https://proceedings.mlr.press/v70/lindgren17a.html}, abstract = {Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice and it is a major open question is to explain why this is true. We give a natural condition under which we can provably perform MAP inference in polynomial time—we require that the number of fractional vertices in the LP relaxation exceeding the optimal solution is bounded by a polynomial in the problem size. This resolves an open question by Dimakis, Gohari, and Wainwright. In contrast, for general LP relaxations of integer programs, known techniques can only handle a constant number of fractional vertices whose value exceeds the optimal solution. We experimentally verify this condition and demonstrate how efficient various integer programming methods are at removing fractional solutions.} }
Endnote
%0 Conference Paper %T Exact MAP Inference by Avoiding Fractional Vertices %A Erik M. Lindgren %A Alexandros G. Dimakis %A Adam Klivans %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-lindgren17a %I PMLR %P 2120--2129 %U https://proceedings.mlr.press/v70/lindgren17a.html %V 70 %X Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice and it is a major open question is to explain why this is true. We give a natural condition under which we can provably perform MAP inference in polynomial time—we require that the number of fractional vertices in the LP relaxation exceeding the optimal solution is bounded by a polynomial in the problem size. This resolves an open question by Dimakis, Gohari, and Wainwright. In contrast, for general LP relaxations of integer programs, known techniques can only handle a constant number of fractional vertices whose value exceeds the optimal solution. We experimentally verify this condition and demonstrate how efficient various integer programming methods are at removing fractional solutions.
APA
Lindgren, E.M., Dimakis, A.G. & Klivans, A.. (2017). Exact MAP Inference by Avoiding Fractional Vertices. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2120-2129 Available from https://proceedings.mlr.press/v70/lindgren17a.html.

Related Material