Max-Margin Parsing

Max-Margin Parsing Ben Taskar Computer Science Dept. Stanford University btaskar@cs.stanford.edu Dan Klein Computer Science Dept. Stanford University klein@cs.stanford.edu Michael Collins CS and AI Lab MIT mcollins@csail.mit.edu Daphne Koller Computer Science Dept. Stanford University koller@cs.stanford.edu Christopher Manning Computer Science Dept. Stanford University manning@cs.stanford.edu Abstract We present a novel discriminative approach to parsing inspired by the large-margin criterion underlying sup- port vector machines. Our formulation uses a factor- ization analogous to the standard dynamic programs for parsing. In particular, it allows one to efficiently learn a model which discriminates among the entire space of parse trees, as opposed to reranking the top few candi- dates. Our models can condition on arbitrary features of input sentences, thus incorporating an important kind of lexical information without the added algorithmic com- plexity of modeling headedness. We provide an efficient algorithm for learning such models and show experimen- tal evidence of the model’s improved performance over a natural baseline model and a lexicalized probabilistic context-free grammar. 1 Introduction Recent work has shown that discriminative techniques frequently achieve classification ac- curacy that is superior to generative techniques, over a wide range of tasks. The empirical utility of models such as logistic regression and sup- port vector machines (SVMs) in flat classifica- tion tasks like text categorization, word-sense disambiguation, and relevance routing has been repeatedly demonstrated. For sequence tasks like part-of-speech tagging or named-entity ex- traction, recent top-performing systems have also generally been based on discriminative se- quence models, like conditional Markov mod- els (Toutanova et al., 2003) or conditional ran- dom fields (Lafferty et al., 2001). A number of recent papers have consid- ered discriminative approaches for natural lan- guage parsing (Johnson et al., 1999; Collins, 2000; Johnson, 2001; Geman and Johnson, 2002; Miyao and Tsujii, 2002; Clark and Cur- ran, 2004; Kaplan et al., 2004; Collins, 2004). Broadly speaking, these approaches fall into two categories, reranking and dynamic programming approaches. In reranking methods (Johnson et al., 1999; Collins, 2000; Shen et al., 2003), an initial parser is used to generate a number of candidate parses. A discriminative model is then used to choose between these candi- dates. In dynamic programming methods, a large number of candidate parse trees are repre- sented compactly in a parse tree forest or chart. Given sufficiently “local” features, the decod- ing and parameter estimation problems can be solved using dynamic programming algorithms. For example, (Johnson, 2001; Geman and John- son, 2002; Miyao and Tsujii, 2002; Clark and Curran, 2004; Kaplan et al., 2004) describe ap- proaches based on conditional log-linear (max- imum entropy) models, where variants of the inside-outside algorithm can be used to effi- ciently calculate gradients of the log-likelihood function, despite the exponential number of trees represented by the parse forest. In this paper, we describe a dynamic pro- gramming approach to discriminative parsing that is an alternative to maximum entropy estimation. Our method extends the max- margin approach of Taskar et al. (2003) to the case of context-free grammars. The present method has several compelling advantages. Un- like …

Content truncated to 500 words