Deterministic Dependency Parsing of English Text

What it is about

The paper presents one of the first deterministic, linear-time labeled dependency parsers for English, trained on the Wall Street Journal part of the Penn Treebank. The parser uses a shift-reduce transition system (left-arc, right-arc, reduce, shift) that builds projective trees in one pass, and a memory-based learner (TiMBL, k = 5) that predicts the next transition and arc label. Features are the stack top, the next input token, their heads and leftmost or rightmost dependents, and three lookahead tags. The treebank is converted to dependencies by head rules, with arc labels taken from the Penn function tags (7 labels) or from bracket plus function labels (50 labels). The best model reaches 87.1% unlabeled attachment; labeled accuracy is 86.0% on the 7-label set, while root accuracy is clearly weaker than dependency accuracy and falls for longer sentences.

Ideas

I1. Root accuracy as a reported metric in en parse-eval: add root accuracy and complete-match rate, by sentence-length bins of 10 words, on EWT test; the paper locates the largest weakness at the root of long sentences.
I2. Clause pre-split probe: split sentences over 20 words at clause boundaries before en parsing, then measure LAS and root accuracy on EWT test for that subset; the paper suggests clausing as a fix for root errors.
I3. Label granularity study: train the en perceptron with coarse labels (function-tag level, as in the 7-label set) and with the full mova labels, and compare LAS on EWT test and root accuracy; the paper finds the coarser set easier and the unlabeled score higher with more labels.
I4. Label-source check: count how many gold labels in the converted mova corpus come from function-like tags versus default labels, and how many errors fall on the default; test only on GUM, which is NC.

For Mova

The code is en/src/parse.rs (the arc-standard parser and its features) and the en parse-eval command. The chapter is languages/en/21-clause-structure.md. Measure first: root accuracy and LAS by sentence length on EWT test against the current LAS 80.24, because the paper shows that a good LAS can hide a poor root.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/C04-1010.pdf

Summary

The paper investigates whether a fast, greedy dependency parser can handle English well when trained on a treebank built for constituent analysis. The authors convert the Wall Street Journal part of the Penn Treebank into dependency trees using head rules from Yamada and Matsumoto. Arc labels are derived from Penn Treebank II bracket and grammatical role annotations. They then apply Nivre's (2003) transition-based algorithm, which parses in a single left-to-right pass and runs in linear time. At each step, a memory-based classifier (TiMBL, k-nearest neighbours) picks both the next transition and the dependency label. The best configuration reaches 87.1% unlabeled attachment. Labeled accuracy is 86.0% with a 7-label set and 84.4% with a 50-label set. Structural accuracy is below Collins, Charniak and Yamada & Matsumoto, but labeling accuracy appears close to the state of the art. The work matters because it was among the first labeled dependency parsers evaluated on the Penn Treebank. It showed that a deterministic, incremental approach is competitive on a standard English benchmark.

Key points

Transition system. The parser has four transitions: Left-Arc, Right-Arc, Reduce and Shift. It needs at most 2n transitions for n tokens and always produces acyclic, projective graphs.
Classifier. TiMBL's IB1 is used with k = 5, the MVDM distance (overlap for rare values) and inverse-distance-weighted voting.
Features. The classifier sees:
- the word forms and POS tags of the stack top and the next input token;
- labels and POS tags of selected already-built arcs;
- three tokens of POS lookahead.
State models. Model 2 drops the POS tags of neighbouring arcs that Model 1 includes.
Results (Table 1).
- Model 2 with label set B: 87.1 UAS and 84.4 LAS.
- Restricting B to the grammatical-role labels (BG) gives 86.0 LAS.
- Model 1 with set B: 86.7 UAS and 84.0 LAS.
Comparison (Table 2).

Parser Dependency accuracy Root accuracy Complete match

Nivre & Scholz 87.3 84.3 30.4

Yamada & Matsumoto 90.3 91.6 38.4

Charniak 92.1 95.2 45.2
Error analysis. The authors give three reasons for the structural gap:
- a weaker POS tagger (96.1% vs 97.1%);
- impoverished dependency labels in the converted treebank;
- poor root identification, which degrades sharply on long sentences.

Parser	Dependency accuracy	Root accuracy	Complete match
Nivre & Scholz	87.3	84.3	30.4
Yamada & Matsumoto	90.3	91.6	38.4
Charniak	92.1	95.2	45.2

Interesting ideas

Joint transition and label prediction. A single multi-class decision chooses both the parser action and the arc label. This avoids a separate labeling stage and suits learners that handle many classes easily. Such learners include memory-based ones, which the authors chose over SVMs for this reason.
Features from the partial tree. The classifier uses labels of arcs the parser has already built as input. This lets earlier decisions guide later ones. The authors note this works best when the treebank has informative labels, which is relevant when choosing or designing annotation, e.g. UD-style treebanks.
Tuning features to annotation richness. POS features of neighbouring arcs are mostly redundant when labels are rich. They can compensate when labels are poor. Testing both feature sets per dataset is a cheap way to adapt a parser to a new treebank.
Separate root accuracy, broken down by sentence length. Tracking root accuracy apart from attachment, and splitting it by sentence length, exposed a global-structure weakness that averaged scores hid. The authors suggest clause-level preprocessing as a possible fix.
Checking a method on a benchmark. The method was first tested on a small Swedish treebank that had no comparable results. Moving it to a standard benchmark made its performance interpretable, which is a useful step for any method developed on a low-resource language.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1220355.1220365

@inproceedings{nivre2004deterministic,
  title = {{Deterministic Dependency Parsing of English Text}},
  author = {Nivre, Joakim and Scholz, Mario},
  booktitle = {COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics},
  year = {2004},
  doi = {10.3115/1220355.1220365},
  url = {https://doi.org/10.3115/1220355.1220365}
}

References

35 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

D. W. Aha, D. Kibler, and M. Albert. 1991. Instance-based learning algorithms. Machine Learning, 6:37–66. find our card
D. Aha, editor. 1997. Lazy Learning. Kluwer. find
A. Bies, M. Ferguson, K. Katz, and R. MacIntyre. 1995. Bracketing guidelines for Treebank II style, Penn Treebank project. University of Pennsylvania, Philadelphia. find
E. Black, F. Jelinek, J. Lafferty, D. Magerman, R. Mercer, and S. Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. In Proceedings of the 5th DARPA Speech and Natural Language Workshop. find
D. Blaheta and E. Charniak. 2000. Assigning function tags to parsed text. In Proceedings of NAACL, pages 234–240. find
S. Buchholz. 2002. Memory-Based Grammatical Relation Finding. Ph.D. thesis, University of Tilburg. find
J. Carroll, E. Briscoe, and A. Sanfilippo. 1998. Parser evaluation: A survey and a new proposal. In Proceedings of LREC, pages 447–454, Granada, Spain. find
E. Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL. find
M. Collins, J. Hajič, E. Brill, L. Ramshaw, and C. Tillmann. 1999. A Statistical Parser of Czech. In Proceedings of ACL, pages 505–512, University of Maryland, College Park, USA. ≤ 10 11–20 21–30 31–40 ≥ 41 Table 3: Accuracy in relation to sentence length (number of words) find
M. Collins. 1996. A new statistical parser based on bigram lexical dependencies. In Proceedings of ACL, pages 184–191, Santa Cruz, CA. find
M. Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of ACL, pages 16–23, Madrid, Spain. find
M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find our card
S. Cost and S. Salzberg. 1993. A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 10:57–78. find
W. Daelemans, A. van den Bosch, and J. Zavrel. 2002. Forgetting exceptions is harmful in language learning. Machine Learning, 34:11–43. find
W. Daelemans, J. Zavrel, K. van der Sloot, and A. van den Bosch. 2003. Timbl: Tilburg memory based learner, version 5.0, reference guide. Technical Report ILK 03-10, Tilburg University, ILK. find
W. Daelemans. 1999. Memory-based language processing. Introduction to the special issue. Journal of Experimental and Theoretical Artificial Intelligence, 11:287–292. find
S. A. Dudani. 1976. The distance-weighted knearest neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics, SMC-6:325–327. find
J. Einarsson. 1976. Talbankens skriftspråkskonkor-dans. Lund University. find
J. M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING, Copenhagen, Denmark. find our card
E. Fix and J. Hodges. 1952. Discriminatory analysis: Nonparametric discrimination: Consistency properties. Technical Report 11, USAF School of Aviation Medicine, Randolph Field, Texas. find
J. Hajic. 1998. Building a syntactically annotated corpus: The prague dependency treebank. In Issues of Valency and Meaning, pages 106–132. Karolinum. find
M. T. Kromann. 2003. The Danish dependency treebank and the DTAG treebank tool. In Proceedings of the Second Workshop on Treebanks DA 93.7 88.8 87.4 86.8 84.6 RA 96.6 86.4 83.4 78.1 74.9 CM 83.6 39.5 20.8 9.9 1.8 and Linguistic Theories, pages 217–220, Växjö, Sweden. find
T. Kudo and Y. Matsumoto. 2000. Japanese dependency structure analysis based on support vector machines. In Proceedings of EMNLP/VLC, Hongkong. find
D. Lin. 1998. Dependency-based evaluation of MINIPAR. In Proceedings of LREC. find
D. M. Magerman. 1995. Statistical decision-tree models for parsing. In Proceedings of ACL, pages 276–283, Boston, MA. find
M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19:313–330. find our card
J. Nivre, J. Hall, and J. Nilsson. 2004. Memory-based dependency parsing. In Proceedings of CoNLL, pages 49–56. find
J. Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of IWPT, pages 149–160, Nancy, France. find our card
K. Oflazer. 2003. Dependency parsing with an extended finite-state approach. Computational Linguistics, 29:515–544. find
R. Skousen. 1989. Analogical Modeling of Language. Kluwer. find
R. Skousen. 1992. Analogy and Structure. Kluwer. find
C. Stanfill and D. Waltz. 1986. Toward memory-based reasoning. Communications of the ACM, 29:1213–1228. find
V. N. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer-Verlag. find
J. Veenstra and W. Daelemans. 2000. A memory-based alternative for connectionist shift-reduce parsing. Technical Report ILK-0012, University of Tilburg. find
H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, pages 195–206, Nancy, France. find our card