Structured Perceptron with Inexact Search

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 142–151, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Structured Perceptron with Inexact Search Liang Huang Information Sciences Institute University of Southern California liang.huang.sh@gmail.com Suphan Fayong Dept. of Computer Science University of Southern California suphan.ying@gmail.com Yang Guo Bloomberg L.P. New York, NY yangg86@gmail.com Abstract Most existing theory of structured prediction assumes exact inference, which is often in- tractable in many practical problems. This leads to the routine use of approximate infer- ence such as beam search but there is not much theory behind it. Based on the structured perceptron, we propose a general framework of “violation-fixing” perceptrons for inexact search with a theoretical guarantee for conver- gence under new separability conditions. This framework subsumes and justifies the pop- ular heuristic “early-update” for perceptron with beam search (Collins and Roark, 2004). We also propose several new update meth- ods within this framework, among which the “max-violation” method dramatically reduces training time (by 3 fold as compared to early- update) on state-of-the-art part-of-speech tag- ging and incremental parsing systems. 1 Introduction Discriminative structured prediction algorithms such as conditional random fields (Lafferty et al., 2001), structured perceptron (Collins, 2002), max- margin markov networks (Taskar et al., 2003), and structural SVMs (Tsochantaridis et al., 2005) lead to state-of-the-art performance on many structured prediction problems such as part-of-speech tagging, sequence labeling, and parsing. But despite their success, there remains a major problem: these learn- ing algorithms all assume exact inference (over an exponentially-large search space), which is needed to ensure their theoretical properties such as conver- gence. This exactness assumption, however, rarely holds in practice since exact inference is often in- tractable in many important problems such as ma- chine translation (Liang et al., 2006), incremen- tal parsing (Collins and Roark, 2004; Huang and Sagae, 2010), and bottom-up parsing (McDonald and Pereira, 2006; Huang, 2008). This leads to routine use of approximate inference such as beam search as evidenced in the above-cited papers, but the inexactness unfortunately abandons existing the- oretical guarantees of the learning algorithms, and besides notable exceptions discussed below and in Section 7, little is known for theoretical properties of structured prediction under inexact search. Among these notable exceptions, many exam- ine how and which approximations break theoretical guarantees of existing learning algorithms (Kulesza and Pereira, 2007; Finley and Joachims, 2008), but we ask a deeper and practically more useful ques- tion: can we modify existing learning algorithms to accommodate the inexactness in inference, so that the theoretical properties are still maintained? For the structured perceptron, Collins and Roark (2004) provides a partial answer: they suggest vari- ant called “early update” for beam search, which up- dates on partial hypotheses when the correct solution falls out of the beam. This method works signif- icantly better than standard perceptron, and is fol- lowed by later incremental parsers, for instance in (Zhang and Clark, 2008; Huang and Sagae, 2010). However, two problems remain: first, up …

Content truncated to 500 words