Ensemble Methods for Structured Prediction

We present a series of learning algorithms and theoretical guarantees for designing accurate en-sembles of structured prediction tasks. This in-cludes several randomized and deterministic al-gorithms devised by converting on-line learning algorithms to batch ones, and a boosting-style al-gorithm applicable in the context of structured prediction with a large number of labels. We give a detailed study of all these algorithms, including the description of new on-line-to-batch conver-sions and learning guarantees. We also report the results of extensive experiments with these algo-rithms in several structured prediction tasks. 1