Learning Where to Sample in Structured Prediction
Tianlin Shi, Jacob Steinhardt, Percy Liang
Abstract
In structured prediction, most inference algorithms allocate a homogeneous amount of computation to all parts of the output, which can be wasteful when different parts vary widely in terms of difficulty. In this paper, we propose a heterogeneous approach that dynamically allocates computation to the different parts. Given a pre-trained model, we tune its inference algorithm (a sampler) to increase test-time throughput. The inference algorithm is parametrized by a meta-model and trained via reinforcement learning, where actions correspond to sampling candidate parts of the output, and rewards are log-likelihood improvements. The meta-model is based on a set of domain-general meta-features capturing the progress of the sampler. We test our approach on five datasets and show that it attains the same accuracy as Gibbs sampling but is 2 to 5 times faster.
BibTeX
@InProceedings{pmlr-v38-shi15,
title = {{Learning Where to Sample in Structured Prediction}},
author = {Shi, Tianlin and Steinhardt, Jacob and Liang, Percy},
booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics},
pages = {875--884},
year = {2015},
editor = {Lebanon, Guy and Vishwanathan, S. V. N.},
volume = {38},
series = {Proceedings of Machine Learning Research},
address = {San Diego, California, USA},
month = {09--12 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v38/shi15.pdf},
url = {https://proceedings.mlr.press/v38/shi15.html},
abstract = {In structured prediction, most inference algorithms allocate a homogeneous amount of computation to all parts of the output, which can be wasteful when different parts vary widely in terms of difficulty. In this paper, we propose a heterogeneous approach that dynamically allocates computation to the different parts. Given a pre-trained model, we tune its inference algorithm (a sampler) to increase test-time throughput. The inference algorithm is parametrized by a meta-model and trained via reinforcement learning, where actions correspond to sampling candidate parts of the output, and rewards are log-likelihood improvements. The meta-model is based on a set of domain-general meta-features capturing the progress of the sampler. We test our approach on five datasets and show that it attains the same accuracy as Gibbs sampling but is 2 to 5 times faster.}
}