Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models

Tatiana Shpakova, Francis Bach, Anton Osokin
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:278-288, 2018.

Abstract

We consider the structured-output prediction problem through probabilistic approaches and generalize the “perturb-and-MAP” framework to more challenging weighted Hamming losses, which are crucial in applications. While in principle our approach is a straightforward marginalization, it requires solving many re- lated MAP inference problems. We show that for log-supermodular pairwise models these op- erations can be performed efficiently using the machinery of dynamic graph cuts. We also pro- pose to use double stochastic gradient descent, both on the data and on the perturbations, for efficient learning. Our framework can naturally take weak supervision (e.g., partial labels) into account. We conduct a set of experiments on medium-scale character recognition and image segmentation, showing the benefits of our algo- rithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-shpakova18a, title = {Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models}, author = {Shpakova, Tatiana and Bach, Francis and Osokin, Anton}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {278--288}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/shpakova18a/shpakova18a.pdf}, url = {https://proceedings.mlr.press/r16/shpakova18a.html}, abstract = {We consider the structured-output prediction problem through probabilistic approaches and generalize the “perturb-and-MAP” framework to more challenging weighted Hamming losses, which are crucial in applications. While in principle our approach is a straightforward marginalization, it requires solving many re- lated MAP inference problems. We show that for log-supermodular pairwise models these op- erations can be performed efficiently using the machinery of dynamic graph cuts. We also pro- pose to use double stochastic gradient descent, both on the data and on the perturbations, for efficient learning. Our framework can naturally take weak supervision (e.g., partial labels) into account. We conduct a set of experiments on medium-scale character recognition and image segmentation, showing the benefits of our algo- rithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models %A Tatiana Shpakova %A Francis Bach %A Anton Osokin %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-shpakova18a %I PMLR %P 278--288 %U https://proceedings.mlr.press/r16/shpakova18a.html %V R16 %X We consider the structured-output prediction problem through probabilistic approaches and generalize the “perturb-and-MAP” framework to more challenging weighted Hamming losses, which are crucial in applications. While in principle our approach is a straightforward marginalization, it requires solving many re- lated MAP inference problems. We show that for log-supermodular pairwise models these op- erations can be performed efficiently using the machinery of dynamic graph cuts. We also pro- pose to use double stochastic gradient descent, both on the data and on the perturbations, for efficient learning. Our framework can naturally take weak supervision (e.g., partial labels) into account. We conduct a set of experiments on medium-scale character recognition and image segmentation, showing the benefits of our algo- rithms. %Z Reissued by PMLR on 04 October 2026.
APA
Shpakova, T., Bach, F. & Osokin, A.. (2018). Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:278-288 Available from https://proceedings.mlr.press/r16/shpakova18a.html. Reissued by PMLR on 04 October 2026.

Related Material