Improved Large Margin Dependency Parsing via Local Constraints and Laplacian Regularization

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 21–28, New York City, June 2006. c⃝2006 Association for Computational Linguistics Improved Large Margin Dependency Parsing via Local Constraints and Laplacian Regularization Qin Iris Wang Colin Cherry Dan Lizotte Dale Schuurmans Department of Computing Science University of Alberta � wqin,colinc,dlizotte,dale � @cs.ualberta.ca Abstract We present an improved approach for learning dependency parsers from tree- bank data. Our technique is based on two ideas for improving large margin train- ing in the context of dependency parsing. First, we incorporate local constraints that enforce the correctness of each individ- ual link, rather than just scoring the global parse tree. Second, to cope with sparse data, we smooth the lexical parameters ac- cording to their underlying word similar- ities using Laplacian Regularization. To demonstrate the benefits of our approach, we consider the problem of parsing Chi- nese treebank data using only lexical fea- tures, that is, without part-of-speech tags or grammatical categories. We achieve state of the art performance, improving upon current large margin approaches. 1 Introduction Over the past decade, there has been tremendous progress on learning parsing models from treebank data (Collins, 1997; Charniak, 2000; Wang et al., 2005; McDonald et al., 2005). Most of the early work in this area was based on postulating gener- ative probability models of language that included parse structure (Collins, 1997). Learning in this con- text consisted of estimating the parameters of the model with simple likelihood based techniques, but incorporating various smoothing and back-off esti- mation tricks to cope with the sparse data problems (Collins, 1997; Bikel, 2004). Subsequent research began to focus more on conditional models of parse structure given the input sentence, which allowed discriminative training techniques such as maximum conditional likelihood (i.e. “maximum entropy”) to be applied (Ratnaparkhi, 1999; Charniak, 2000). In fact, recently, effective conditional parsing mod- els have been learned using relatively straightfor- ward “plug-in” estimates, augmented with similar- ity based smoothing (Wang et al., 2005). Currently, the work on conditional parsing models appears to have culminated in large margin training (Taskar et al., 2003; Taskar et al., 2004; Tsochantaridis et al., 2004; McDonald et al., 2005), which currently demonstrates the state of the art performance in En- glish dependency parsing (McDonald et al., 2005). Despite the realization that maximum margin training is closely related to maximum conditional likelihood for conditional models (McDonald et al., 2005), a sufficiently unified view has not yet been achieved that permits the easy exchange of improvements between the probabilistic and non- probabilistic approaches. For example, smoothing methods have played a central role in probabilistic approaches (Collins, 1997; Wang et al., 2005), and yet they are not being used in current large margin training algorithms. However, as we demonstrate, not only can smoothing be applied in a large mar- gin training framework, it leads to generalization im- provements in much the same way as probabilistic approaches. The second key observation we make is somewhat more subtle. It turns out that probabilistic approaches …

Content truncated to 500 words