The fundamental idea in dependency-based parsing is that parsing crucially involves establishing binary relations between words in a sentence. This simple idea can be implemented in a variety of ways.
On the one hand, we have approaches that can be characterized as dependency parsing in a broad sense, where the actual form of the syntactic analysis may vary, but where the construction of the analysis nevertheless depends on finding syntactic relations between lexical heads. In this category, we find the widely used link grammar parser for English Sleator and Temperley 1991, as well as the influential probabilistic parsers of Collins 1997 and Charniak 2000, but also a variety of other lexicalized parsing models that can be subsumed under the general notion of bilexical grammars Eisner 2000.
On the other hand, we have what we may call dependency parsing in a narrow sense, which is the focus of the CoNLL shared tasks in 2006 and 2007, where the goal of the parsing process is to build a dependency structure, consisting only of words connected by binary dependency relations. This tradition is represented by Maruyama 1990, Eisner 1996, Tapanainen and JÃ¤rvinen 1997, Menzel and SchrÃ¶der 1998, Duchier and Debusmann 2001, Yamada and Matsumoto 2003, Nivre et al. 2004, and McDonald et al. 2005, among others.
Until quite recently, most data-driven parsers (whether dependency-based or not) had been applied only to one or a few languages, but this situation has now changed dramatically, especially after the CoNLL shared task 2006 (Buchholz and Marsi 2006), where 19 different systems were used to parse 13 different languages. The CoNLL shared task 2007 continues this tradition through its multilingual track, adding several new languages.
For more information about specific approaches to dependency parsing, used in the CoNLL shared task 2006 and elsewhere, consult the parsing frameworks page. For a more thorough introduction to dependency parsing, try Joakim Nivre's and Sandra Kuebler's ACL tutorial or chapter 3 of Nivre 2006.
One well known characteristic of supervised parsing models is that they typically perform much worse on data that does not come from the training domain (Gildea 2001). Due to the large overhead in annotating text with deep syntactic parse trees, the need to adapt parsers from domians with plentiful resources (e.g., news) to domain with little resources is an important problem. Work on domain adaptation falls roughly into two categories:
Limited annotated resources in new domain. Many studies have shown that large gains can be made when a small amount of annotated resources exist in the new domain. This includes the work of Roark and Bacchiani 2003, Florian et al 2004, Chelba and Acero 2004, Daume and Marcu 2006, and Titov and Henderson 2006. Of these R&B2003 and T&H2006 deal specifically with syntactic parsing.
No annotated resources in new domain. This is a more common problem and is considerably more difficult. Recent work by McClosky et al 2006 and Blitzer et al 2006 have shown that the existence of a large unlabeled corpus in the new domain can be leveraged in adaptation.
Another approach might be to use transductive learning, where the model is learned based on the training set and the unlabeled test set. Self-training (McClosky et al 2006) can be considered a variant of transductive learning.
John Blitzer, Ryan McDonald, and Fernando Pereira. Domain Adaptation with Structural Correspondence Learning. EMNLP 2006.
- Jason Eisner. Bilexical Grammars and Their Cubic-Time Parsing Algorithms. In Bunt and Nijholt (eds.) Advances in Probabilistic and Other Parsing Technologies, Kluwer, 2000.
- Eugene Charniak. A maximum-entropy-inspired parser. NAACL 2000.
- Chelba and Acero. Adaptation of maximum entropy capitalizer: Little data can help a lot. EMNLP 2004.
- Michael Collins. Three Generative, Lexicalized Models for Natural Language Parsing. ACL 1997.
- Hal Daume and Daniel Marcu. Domain Adaptation for Statistical Classifiers. Journal of Artificial Intelligence Research 2006.
- Denys Duchier and Ralph Debusmann. Topological Dependency Parsing: A Constraint-Based Account of Linear Precedence. ACL 2001.
- Jason Eisner. Three New Probabilistic Models for Dependency Parsing: An Exploration. COLING 1990.
- Florian et al. A statisical model for multilingual entity detection and tracking. HLT-NAACL 2004.
- Daniel Gildea. Corpus Variation and Parser Performance. EMNLP 2001.
- Matthew Lease and Eugene Charniak. Parsing Biomedical Literature. Second International Joint Conference on Natural Language Processing 2005.
- Hiroshi Maruyama. Structural Disambiguation with Constraint Propagation. ACL 1990.
David McClosky, Eugene Charniak, and Mark Johnson. Reranking and Self-Training for Parser Adaptation. COLING-ACL 2006.
Ryan McDonald, Coby Krammer and Fernando Pereira. Online Large-Margin Training of Dependency Parsers. ACL 2005.
- Wolfgang Menzel and Ingo SchrÃ¶der. Decision Procedures for Dependency Parsing Using Graded Constraints. COLING-ACL Workshop 1998.
- Joakim Nivre, Johan Hall and Jens Nilsson. Memory-Based Dependency Parsing. CoNLL 2004.
- Roark and Bacchiani. Supervised and unsupervised PCFG adaptation to novel domains. HLT-NAACL 2003.
- D. D. K. Sleator and D. Temperley. Parsing English with a Link Grammar. International Workshop on Parsing Technologies (IWPT) 1991.
- Pasi Tapanainen and Timo JÃ¤rvinen. A non-projective dependency parser. ANLP 1997.
- I. Titov and J. Henderson. Porting statistical parsers with data-defined kernels. Computational Natural Language Learning (CoNLL) 2006.
- Hiroyasu Yamada and Yuji Matsumoto. Statistical Dependency Analysis with Support Vector Machines. IWPT 2003.