Covington Variations

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1144–1148, Prague, June 2007. c⃝2007 Association for Computational Linguistics Covington Variations Svetoslav Marinov School of Humanities and Informatics, University College Sk¨ovde, 54128 Sk¨ovde & GSLT, G¨oteborg University, 40530 G¨oteborg, Sweden Svetoslav.Marinov@his.se Abstract Three versions of the Covington algorithm for non-projective dependency parsing have been tested on the ten different languages for the Multilingual track of the CoNLL- X Shared Task. The results were achieved by using only information about heads and daughters as features to guide the parser which obeys strict incrementality. 1 Introduction In this paper we focus on two things. First, we in- vestigate the impact of using different flavours of Covington’s algorithm (Covington, 2001) for non- projective dependency parsing on the ten differ- ent languages provided for CoNLL-X Shared Task (Nivre et al., 2007). Second, we test the perfor- mance of a pure grammar-based feature model in strictly incremental fashion. The grammar model re- lies only on the knowledge of heads and daughters of two given words, as well as the words themselves, in order to decide whether they can be linked with a certain dependency relation. In addition, none of the three parsing algorithms guarantees that the output dependency graph will be projective. 2 Covington’s algorithm(s) In his (2001) paper, Covington presents a “funda- mental” algorithm for dependency parsing, which he claims has been known since the 1960s but has, up to his paper-publication, not been presented systematically in the literature. We take three of its flavours, which enforce uniqueness (a.k.a. single-headedness) but do not observe projectivity. The algorithms work one word at a time and attempt to build a connected dependency graph with only a single left-to-right pass through the input. The three flavours are: Exhaustive Search, Head First with Uniqueness (ESHU), Exhaustive Search Dependents First with Uniqueness (ESDU) and List-based search with Uniqueness (LSU). ESHU ESDU for i = 1 to n for i = 1 to n for j = i-1 downto 0 for j = i-1 downto 0 if HEAD?(j,i) if HEAD?(i,j) LINK(j,i) LINK(i,j) if HEAD?(i,j) if HEAD?(j,i) LINK(i,j) LINK(j,i) The yes/no function HEAD?(w1,w2), checks whether a word w1 can be a head of a word w2 ac- cording to a grammar G. It also respects the single- head and no-cycle conditions. The LINK(w1,w2) procedure links word w1 as the head of word w2 with a dependency relation as proposed by G. When traversing Headlist and Wordlist we start with the last word added. (Nivre, 2007) describes an op- timized version of Covington’s algorithm imple- mented in MaltParser (Nivre, 2006) with a running time c(n2 2 − n 2 ) for an n-word sentence, where c is some constant time in which the LINK operation can be performed. However, due to time constraints, we will not bring this version of the algorithm into focus, but see some preliminary remarks on it with respect to our parsing model in 6. 1144 LSU1 Headlist := [] Wordlist := [] while (!end-of-sentence) W := …

Content truncated to 500 words