ICML 2018oral9 citations
Learning Maximum-A-Posteriori Perturbation Models for Structured Prediction in Polynomial Time
Abstract
MAP perturbation models have emerged as a powerful framework for inference in structured prediction. Such models provide a way to efficiently sample from the Gibbs distribution and facilitate predictions that are robust to random noise. In this paper, we propose a provably polynomial time randomized algorithm for learning the parameters of perturbed MAP predictors. Our approach is based on minimizing a novel Rademacher-based generalization bound on the expected loss of a perturbed MAP predictor, which can be computed in polynomial time. We obtain conditions under which our randomized learning algorithm can guarantee generalization to unseen examples.
BibTeX
@InProceedings{pmlr-v80-ghoshal18a,
title = {Learning Maximum-A-Posteriori Perturbation Models for Structured Prediction in Polynomial Time},
author = {Ghoshal, Asish and Honorio, Jean},
booktitle = {Proceedings of the 35th International Conference on Machine Learning},
pages = {1754--1762},
year = {2018},
editor = {Dy, Jennifer and Krause, Andreas},
volume = {80},
series = {Proceedings of Machine Learning Research},
month = {10--15 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v80/ghoshal18a/ghoshal18a.pdf},
url = {https://proceedings.mlr.press/v80/ghoshal18a.html},
abstract = {MAP perturbation models have emerged as a powerful framework for inference in structured prediction. Such models provide a way to efficiently sample from the Gibbs distribution and facilitate predictions that are robust to random noise. In this paper, we propose a provably polynomial time randomized algorithm for learning the parameters of perturbed MAP predictors. Our approach is based on minimizing a novel Rademacher-based generalization bound on the expected loss of a perturbed MAP predictor, which can be computed in polynomial time. We obtain conditions under which our randomized learning algorithm can guarantee generalization to unseen examples.}
}