University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Worst-case Optimal Submodular Extensions for Marginal Estimation

Pansari, Pankaj, Russell, Christopher and Kumar, M.Pawan (2018) Worst-case Optimal Submodular Extensions for Marginal Estimation In: 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018), 09-11 Apr 2018, Hotel H10 Rubicon Palace, Playa Blanca, Lanzarote, Canary Islands.

Worst-case Optimal Submodular Extensions for Marginal Estimation.pdf

Download (1MB) | Preview


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 worst-case optimality of the submodular extension for Potts model used in the literature; (ii) identify the worst-case optimal submodular extension for the more general class of metric labeling; and (iii) efficiently compute the marginals for the widely used dense CRF model with the help of a recently proposed Gaussian filtering method. Using 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.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Electronic Engineering
Authors :
Pansari, Pankaj
Kumar, M.Pawan
Editors :
Storkey, Amos
Perez-Cruz, Fernando
Date : 11 April 2018
Copyright Disclaimer : © The authors 2018
Uncontrolled Keywords : Learning; Computer Vision and Pattern Recognition; Machine Learning
Related URLs :
Depositing User : Clive Harris
Date Deposited : 23 Jan 2018 13:31
Last Modified : 16 Jan 2019 19:07

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800