This paper presents an effective training algorithm for linearly-scored dependency parsers that implements online large-margin multi-class training (Crammer and Singer, 2003; Crammer et al., 2003) on top of efficient parsing techniques for dependency trees (Eisner, 1996). The trained parsers achieve competitive dependency accuracy for both English and Czech with no language-specific enhancements. The paper discusses the challenges of training parsers from annotated data, focusing on models and training algorithms for phrase structure parsing. Generative parsing models are convenient for training but make complicated assumptions. Discriminatively trained models, such as Ratnaparkhi's conditional maximum entropy model, have shown better performance in tasks like document classification and shallow parsing. Discriminatively trained parsers that score entire trees for a given sentence have been recently investigated. However, discriminative training requires repeatedly reparsing the training corpus with the current model, which is computationally expensive for lexicalized grammars. Dependency trees, an alternative syntactic representation, can be parsed in O(n^3) time and have been shown to be useful in various applications. The authors propose a new approach to training dependency parsers based on online large-margin learning algorithms. Unlike previous methods, their parsers are trained to maximize the accuracy of the overall tree. The approach is related to those of Collins and Roark (2004) and Taskar et al. (2004) for phrase structure parsing. The authors demonstrate that their method is efficient and accurate, as shown experimentally on English and Czech treebank data. The paper describes the system, including definitions, parsing algorithms, online learning, feature sets, and system summary. The experiments show that the proposed method performs as well or better than previous comparable systems, including that of Yamada and Matsumoto (2003). The system is efficient, general, and can be augmented with features over lexicalized phrase structure parsing decisions to increase dependency accuracy. The authors plan to extend their parser by adding labels to dependencies to represent grammatical roles and allowing non-projective dependencies, which occur in languages such as Czech, German, and Dutch. The work was supported by NSF ITR grants.This paper presents an effective training algorithm for linearly-scored dependency parsers that implements online large-margin multi-class training (Crammer and Singer, 2003; Crammer et al., 2003) on top of efficient parsing techniques for dependency trees (Eisner, 1996). The trained parsers achieve competitive dependency accuracy for both English and Czech with no language-specific enhancements. The paper discusses the challenges of training parsers from annotated data, focusing on models and training algorithms for phrase structure parsing. Generative parsing models are convenient for training but make complicated assumptions. Discriminatively trained models, such as Ratnaparkhi's conditional maximum entropy model, have shown better performance in tasks like document classification and shallow parsing. Discriminatively trained parsers that score entire trees for a given sentence have been recently investigated. However, discriminative training requires repeatedly reparsing the training corpus with the current model, which is computationally expensive for lexicalized grammars. Dependency trees, an alternative syntactic representation, can be parsed in O(n^3) time and have been shown to be useful in various applications. The authors propose a new approach to training dependency parsers based on online large-margin learning algorithms. Unlike previous methods, their parsers are trained to maximize the accuracy of the overall tree. The approach is related to those of Collins and Roark (2004) and Taskar et al. (2004) for phrase structure parsing. The authors demonstrate that their method is efficient and accurate, as shown experimentally on English and Czech treebank data. The paper describes the system, including definitions, parsing algorithms, online learning, feature sets, and system summary. The experiments show that the proposed method performs as well or better than previous comparable systems, including that of Yamada and Matsumoto (2003). The system is efficient, general, and can be augmented with features over lexicalized phrase structure parsing decisions to increase dependency accuracy. The authors plan to extend their parser by adding labels to dependencies to represent grammatical roles and allowing non-projective dependencies, which occur in languages such as Czech, German, and Dutch. The work was supported by NSF ITR grants.