Large-Margin Training of Dependency Parsers Using Pegasos Algorithm

ETRI Journal

关键词: Pegasos;    stochastic gradient descent;    Dependency parsing;   

Others  :  1185953
DOI  :  10.4218/etrij.10.0209.0483

【 摘 要 】

This letter presents a modified Pegasos algorithm for graph-based dependency parsing. We show that the modified Pegasos algorithm outperforms the margin infused relaxed and passive aggressive algorithms in three languages.

   

【 参考文献 】

• [1]J. Nivre and R. McDonald, "Integrating Graph-Based and Transition-Based Dependency Parsers," Proc. ACL-HLT, 2008, pp. 950-958.
• [2]R. McDonald and F. Pereira, "Non-Projective Dependency Parsing Using Spanning Tree Algorithms," Proc. HLT-EMNLP, 2005, pp. 523-530.
• [3]R. McDonald and F. Pereira, "Online Learning of Approximate Dependency Parsing Algorithms," Proc. EACL, 2006, pp. 81-88.
• [4]R. McDonald et al., "Multilingual Dependency Analysis with a Two-Stage Discriminative Parser," Proc. CoNLL, 2006, pp. 216-220.
• [5]K. Crammer et al., "Online Passive-Aggressive Algorithms," J. Machine Learning Research, vol. 7, 2006, pp. 551-585.
• [6]L. Bottou and O. Bousquet, "The Tradeoffs of Large Scale Learning," NIPS, vol. 20, 2008, pp. 161-168.
• [7]S. Shalev-Shwartz et al., "Pegasos: Primal Estimated Sub-GrAdient SOlver for SVM," Proc. ICML, 2007, pp. 807-814.
• [8]S. Buchholz and E. Marsi, "Conll-x Shared Task on Multilingual Dependency Parsing," Proc.CoNLL, 2006, pp. 149-164.
• [9]I. Tsochantaridis et al., "Support Vector Machine Learning for Interdependent and Structured Output Spaces," Proc. ICML, 2004, p. 104.
• [10]C. Lee and M. Jang, "A Modified Fixed-Threshold SMO for 1-Slack Structural SVMs," ETRI J., vol. 32, no. 1, Feb. 2010, pp. 120-128.
• [11]C. Lee and M. Jang, "Fast Training of Structured SVM Using Fixed-Threshold Sequential Minimal Optimization," ETRI J., vol. 31, no. 2, 2009, pp. 121-128.
• [12]J. Nivre et al., "Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines," Proc. CoNLL, 2006, pp. 221-225.