Online Learning for Deterministic Dependency Parsing

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1139–1143, Prague, June 2007. c⃝2007 Association for Computational Linguistics Online learning for Deterministic Dependency Parsing Prashanth Reddy Mannem Language Technologies Research Center IIIT-Hyderabad, India prashanth@research.iiit.ac.in Abstract Deterministic parsing has emerged as an ef- fective alternative for complex parsing algo- rithms which search the entire search space to get the best probable parse tree. In this pa- per, we present an online large margin based training framework for deterministic pars- ing using Nivre’s Shift-Reduce parsing al- gorithm. Online training facilitates the use of high dimensional features without cre- ating memory bottlenecks unlike the popu- lar SVMs. We participated in the CoNLL Shared Task-2007 and evaluated our system for ten languages. We got an average multi- lingual labeled attachment score of 74.54 % (with 65.50% being the average and 80.32% the highest) and an average multilingual un- labeled attachment score of 80.30% (with 71.13% being the average and 86.55% the highest). 1 Introduction CoNLL-X had a shared task on multilingual depen- dency parsing (Buchholz et al., 2006) by providing treebanks for 13 languages in the same dependency format. A look at the performance sheet in the con- test shows that two systems with quite different ap- proaches (one using deterministic parsing with SVM and the other using MIRA with nondeterministic and dynamic programming based MST approach ) per- formed with good results (McDonald et al., 2006; Nivre et al., 2006). More recently, deterministic parsing has gener- ated a lot of interest because of their simplicity (Nivre, 2003). One of the main advantages of de- terministic parsing lies in the ability to use the sub- tree information in the features to decide the next step. Parsing algorithms which search the entire space (Eisner, 1996; McDonald, 2006) are restricted in the features they use to score a relation. They rely only on the context information and not the history information to score a relation. Using history infor- mation makes the search intractable. Whereas, since deterministic parsers are at worst O(n2) (Yamada and Matsumoto, 2003) (Nivre (2003) is only O(2n) in the worst case), they can use the crucial history information to make parsing decisions. So, in our work Nivre’s parsing algorithm has been used to ar- rive at the dependency parse tree. Popular learning algorithms for deterministic parsing like Support Vector Machines (SVM) run into memory issues for large data since they are batch learning algorithms. Though more informa- tion is available in deterministic parsing in terms of subtree information, high dimensional features can’t be used due to the large training times for SVMs. This is where online methods come into the picture. Unlike batch algorithms, online algorithms con- sider only one training instance at a time when optimizing parameters. This restriction to single- instance optimization might be seen as a weakness, since the algorithm uses less information about the objective function and constraints than batch algo- rithms. However, McDonald (2006) argues that this potential weakness is balanced by the simplicity of online …

Content truncated to 500 words