Optimal Submodular Extensions for Marginal Estimation

Pankaj Pansari, Chris Russell, M Pawan Kumar
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:327-335, 2018.

Abstract

Submodular extensions of an energy function can be used to efficiently compute approximate marginals via variational inference. The accuracy of the marginals depends crucially on the quality of the submodular extension. To identify the best possible extension, we show an equivalence between the submodular extensions of the energy and the objective functions of linear programming (LP) relaxations for the corresponding MAP estimation problem. This allows us to (i) establish the optimality of the submodular extension for Potts model used in the literature; (ii) identify the optimal submodular extension for the more general class of metric labeling; and (iii) efficiently compute the marginals for the widely used dense CRF model using a recently proposed Gaussian filtering method. Using both synthetic and real data, we show that our approach provides comparable upper bounds on the log-partition function to those obtained using tree-reweighted message passing (TRW) in cases where the latter is computationally feasible. Importantly, unlike TRW, our approach provides the first practical algorithm to compute an upper bound on the dense CRF model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-pansari18a, title = {Optimal Submodular Extensions for Marginal Estimation}, author = {Pansari, Pankaj and Russell, Chris and Pawan Kumar, M}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {327--335}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/pansari18a/pansari18a.pdf}, url = {https://proceedings.mlr.press/v84/pansari18a.html}, abstract = {Submodular extensions of an energy function can be used to efficiently compute approximate marginals via variational inference. The accuracy of the marginals depends crucially on the quality of the submodular extension. To identify the best possible extension, we show an equivalence between the submodular extensions of the energy and the objective functions of linear programming (LP) relaxations for the corresponding MAP estimation problem. This allows us to (i) establish the optimality of the submodular extension for Potts model used in the literature; (ii) identify the optimal submodular extension for the more general class of metric labeling; and (iii) efficiently compute the marginals for the widely used dense CRF model using a recently proposed Gaussian filtering method. Using both synthetic and real data, we show that our approach provides comparable upper bounds on the log-partition function to those obtained using tree-reweighted message passing (TRW) in cases where the latter is computationally feasible. Importantly, unlike TRW, our approach provides the first practical algorithm to compute an upper bound on the dense CRF model.} }
Endnote
%0 Conference Paper %T Optimal Submodular Extensions for Marginal Estimation %A Pankaj Pansari %A Chris Russell %A M Pawan Kumar %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-pansari18a %I PMLR %P 327--335 %U https://proceedings.mlr.press/v84/pansari18a.html %V 84 %X Submodular extensions of an energy function can be used to efficiently compute approximate marginals via variational inference. The accuracy of the marginals depends crucially on the quality of the submodular extension. To identify the best possible extension, we show an equivalence between the submodular extensions of the energy and the objective functions of linear programming (LP) relaxations for the corresponding MAP estimation problem. This allows us to (i) establish the optimality of the submodular extension for Potts model used in the literature; (ii) identify the optimal submodular extension for the more general class of metric labeling; and (iii) efficiently compute the marginals for the widely used dense CRF model using a recently proposed Gaussian filtering method. Using both synthetic and real data, we show that our approach provides comparable upper bounds on the log-partition function to those obtained using tree-reweighted message passing (TRW) in cases where the latter is computationally feasible. Importantly, unlike TRW, our approach provides the first practical algorithm to compute an upper bound on the dense CRF model.
APA
Pansari, P., Russell, C. & Pawan Kumar, M.. (2018). Optimal Submodular Extensions for Marginal Estimation. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:327-335 Available from https://proceedings.mlr.press/v84/pansari18a.html.

Related Material