Deterministic Dependency Parsing of English Text

Deterministic Dependency Parsing of English Text Joakim Nivre and Mario Scholz School of Mathematics and Systems Engineering V¨axj¨o University SE-35195 V¨axj¨o Sweden joakim.nivre@msi.vxu.se Abstract This paper presents a deterministic dependency parser based on memory-based learning, which parses English text in linear time. When trained and evaluated on the Wall Street Journal sec- tion of the Penn Treebank, the parser achieves a maximum attachment score of 87.1%. Unlike most previous systems, the parser produces la- beled dependency graphs, using as arc labels a combination of bracket labels and grammatical role labels taken from the Penn Treebank II an- notation scheme. The best overall accuracy ob- tained for identifying both the correct head and the correct arc label is 86.0%, when restricted to grammatical role labels (7 labels), and 84.4% for the maximum set (50 labels). 1 Introduction There has been a steadily increasing interest in syn- tactic parsing based on dependency analysis in re- cent years. One important reason seems to be that dependency parsing offers a good compromise be- tween the conflicting demands of analysis depth, on the one hand, and robustness and efficiency, on the other. Thus, whereas a complete dependency structure provides a fully disambiguated analysis of a sentence, this analysis is typically less com- plex than in frameworks based on constituent anal- ysis and can therefore often be computed determin- istically with reasonable accuracy. Deterministic methods for dependency parsing have now been ap- plied to a variety of languages, including Japanese (Kudo and Matsumoto, 2000), English (Yamada and Matsumoto, 2003), Turkish (Oflazer, 2003), and Swedish (Nivre et al., 2004). For English, the interest in dependency parsing has been weaker than for other languages. To some extent, this can probably be explained by the strong tradition of constituent analysis in Anglo-American linguistics, but this trend has been reinforced by the fact that the major treebank of American English, the Penn Treebank (Marcus et al., 1993), is anno- tated primarily with constituent analysis. On the other hand, the best available parsers trained on the Penn Treebank, those of Collins (1997) and Char- niak (2000), use statistical models for disambigua- tion that make crucial use of dependency relations. Moreover, the deterministic dependency parser of Yamada and Matsumoto (2003), when trained on the Penn Treebank, gives a dependency accuracy that is almost as good as that of Collins (1997) and Charniak (2000). The parser described in this paper is similar to that of Yamada and Matsumoto (2003) in that it uses a deterministic parsing algorithm in combination with a classifier induced from a treebank. However, there are also important differences between the two approaches. First of all, whereas Yamada and Mat- sumoto employs a strict bottom-up algorithm (es- sentially shift-reduce parsing) with multiple passes over the input, the present parser uses the algorithm proposed in Nivre (2003), which combines bottom- up and top-down processing in a single pass in order to achieve incrementality. This also means that the time complexity of the algorithm used here is linear in the size of …

Content truncated to 500 words