Minimized Models and Grammar-Informed Initialization for Supertagging with Highly Ambiguous Lexicons

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 495–503, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Minimized models and grammar-informed initialization for supertagging with highly ambiguous lexicons Sujith Ravi1 Jason Baldridge2 Kevin Knight1 1University of Southern California Information Sciences Institute Marina del Rey, California 90292 {sravi,knight}@isi.edu 2Department of Linguistics The University of Texas at Austin Austin, Texas 78712 jbaldrid@mail.utexas.edu Abstract We combine two complementary ideas for learning supertaggers from highly am- biguous lexicons: grammar-informed tag transitions and models minimized via in- teger programming. Each strategy on its own greatly improves performance over basic expectation-maximization training with a bitag Hidden Markov Model, which we show on the CCGbank and CCG-TUT corpora. The strategies provide further er- ror reductions when combined. We de- scribe a new two-stage integer program- ming strategy that efficiently deals with the high degree of ambiguity on these datasets while obtaining the full effect of model minimization. 1 Introduction Creating accurate part-of-speech (POS) taggers using a tag dictionary and unlabeled data is an interesting task with practical applications. has been explored at length in the literature sinceIt Merialdo (1994), though the task setting as usu- ally defined in such experiments is somewhat arti- ficial since the tag dictionaries are derived from tagged corpora. Nonetheless, the methods pro- posed apply to realistic scenarios in which one has an electronic part-of-speech tag dictionary or a hand-crafted grammar with limited coverage. Most work has focused on POS-tagging for English using the Penn Treebank (Marcus et al., 1993), such as (Banko and Moore, 2004; Gold- water and Griffiths, 2007; Toutanova and John- son, 2008; Goldberg et al., 2008; Ravi and Knight, 2009). This generally involves working with the standard set of 45 POS-tags employed in the Penn Treebank. The most ambiguous word has 7 dif- ferent POS tags associated with it. Most methods have employed some variant of Expectation Max- imization (EM) to learn parameters for a bigram or trigram Hidden Markov Model (HMM). Ravi and Knight (2009) achieved the best results thus far (92.3% word token accuracy) via a Minimum Description Length approach using an integer pro- gram (IP) that finds a minimal bigram grammar that obeys the tag dictionary constraints and cov- ers the observed data. A more challenging task is learning supertag- gers for lexicalized grammar formalisms such as Combinatory Categorial Grammar (CCG) (Steed- man, 2000). For example, CCGbank (Hocken- maier and Steedman, 2007) contains 1241 dis- tinct supertags (lexical categories) and the most ambiguous word has 126 supertags. This pro- vides a much more challenging starting point for the semi-supervised methods typically ap- plied to the task. Yet, this is an important task since creating grammars and resources for CCG parsers for new domains and languages is highly labor- and knowledge-intensive. Baldridge (2008) uses grammar-informed initialization for HMM tag transitions based on the universal combinatory rules of the CCG formalism to obtain 56.1% accu- racy on ambiguous word tokens, a large improve- ment over the 33.0% accuracy obtained with uni- …

Content truncated to 500 words