Learning Ensembles of Structured Prediction Rules

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1–12, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Learning Ensembles of Structured Prediction Rules Corinna Cortes Google Research 111 8th Avenue, New York, NY 10011 corinna@google.com Vitaly Kuznetsov Courant Institute 251 Mercer Street, New York, NY 10012 vitaly@cims.nyu.edu Mehryar Mohri Courant Institute and Google Research 251 Mercer Street, New York, NY 10012 mohri@cims.nyu.edu Abstract We present a series of algorithms with the- oretical guarantees for learning accurate ensembles of several structured prediction rules for which no prior knowledge is as- sumed. This includes a number of ran- domized and deterministic algorithms de- vised by converting on-line learning al- gorithms to batch ones, and a boosting- style algorithm applicable in the context of structured prediction with a large number of labels. We also report the results of ex- tensive experiments with these algorithms. 1 Introduction We study the problem of learning accurate en- sembles of structured prediction experts. Ensem- ble methods are widely used in machine learn- ing and have been shown to be often very effec- tive (Breiman, 1996; Freund and Schapire, 1997; Smyth and Wolpert, 1999; MacKay, 1991; Fre- und et al., 2004). However, ensemble methods and their theory have been developed primarily for bi- nary classification or regression tasks. Their tech- niques do not readily apply to structured predic- tion problems. While it is straightforward to com- bine scalar outputs for a classification or regres- sion problem, it is less clear how to combine struc- tured predictions such as phonemic pronuncia- tion hypotheses, speech recognition lattices, parse trees, or alternative machine translations. Consider for example the problem of devising an ensemble method for pronunciation, a crit- ical component of modern speech recognition (Ghoshal et al., 2009). Often, several pronunci- ation models or experts are available for transcrib- ing words into sequences of phonemes. These models may have been derived using other ma- chine learning algorithms or they may be based on carefully hand-crafted rules. In general, none of these pronunciation experts is fully accurate and each expert may be making mistakes at different positions along the output sequence. One can hope that a model that patches together the pronuncia- tion of different experts could achieve a superior performance. Similar ensemble structured prediction problems arise in other tasks, including machine translation, part-of-speech tagging, optical character recogni- tion and computer vision, with structures or sub- structures varying with each task. We seek to tackle all of these problems simultaneously and consider the general setting where the label or out- put associated to an input x ∈ X is a structure y ∈ Y that can be decomposed and represented by l substructures y1, . . . , yl. For the pronuncia- tion example just discussed, x is a specific word or word sequence and y its phonemic transcrip- tion. A natural choice for the substructures yk is then the individual phonemes forming y. Other possible choices include n-grams of consecutive phonemes or more …

Content truncated to 500 words