A Multilingual Dependency Analysis System Using Online Passive-Aggressive Learning

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1149–1155, Prague, June 2007. c⃝2007 Association for Computational Linguistics A Multilingual Dependency Analysis System using Online Passive-Aggressive Learning Le-Minh Nguyen, Akira Shimazu, and Phuong-Thai Nguyen Japan Advanced Institute of Science and Technology (JAIST) Asahidai 1-1, Nomi, Ishikawa, 923-1292 Japan {nguyenml,shimazu,thai}@jaist.ac.jp Xuan-Hieu Phan Tohoku University Aobayama 6-3-09, Sendai, 980-8579, Japan hieuxuan@ecei.tohoku.ac.jp Abstract This paper presents an online algorithm for dependency parsing problems. We propose an adaptation of the passive and aggressive online learning algorithm to the dependency parsing domain. We evaluate the proposed algorithms on the 2007 CONLL Shared Task, and report errors analysis. Experimen- tal results show that the system score is bet- ter than the average score among the partici- pating systems. 1 Introduction Research on dependency parsing is mainly based on machine learning methods, which can be called history-based (Yamada and Matsumoto, 2003; Nivre et al., 2006) and discriminative learning methods (McDonald et al., 2005a; Corston-Oliver et al., 2006). The learning methods using in discrimina- tive parsing are Perceptron (Collins, 2002) and on- line large-margin learning (MIRA) (Crammer and Singer, 2003). The difference of MIRA-based parsing in com- parison with history-based methods is that the MIRA-based parser were trained to maximize the accuracy of the overall tree. The MIRA based parsing is close to maximum-margin parsing as in Taskar et al. (2004) and Tsochantaridis et al. (2005) for parsing. However, unlike maximum-margin parsing, it is not limited to parsing sentences of 15 words or less due to computation time. The perfor- mance of MIRA based parsing achieves the state-of- the-art performance in English data (McDonald et al., 2005a; McDonald et al., 2006). In this paper, we propose a new adaptation of on- line larger-margin learning to the problem of depen- dency parsing. Unlike the MIRA parser, our method does not need an optimization procedure in each learning update, but users only an update equation. This might lead to faster training time and easier im- plementation. The contributions of this paper are two-fold: First, we present a training algorithm called PA learning for dependency parsing, which is as easy to im- plement as Perceptron, yet competitive with large margin methods. This algorithm has implications for anyone interested in implementing discrimina- tive training methods for any application. Second, we evaluate the proposed algorithm on the multilin- gual data task as well as the domain adaptation task (Nivre et al., 2007). The remaining parts of the paper are organized as follows: Section 2 proposes our dependency pars- ing with Passive-Aggressive learning. Section 3 discusses some experimental results and Section 4 gives conclusions and plans for future work. 2 Dependency Parsing with Passive-Aggressive Learning This section presents the modification of Passive- Aggressive Learning (PA) (Crammer et al., 2006) for dependency parsing. We modify the PA algo- rithm to deal with structured prediction, in which our problem is to learn a discriminant function that maps an input sentence x to a dependency tree y. Figure 1 shows an example of dependency parsing …

Content truncated to 500 words