Memory-Based Dependency Parsing

Memory-Based Dependency Parsing Joakim Nivre, Johan Hall and Jens Nilsson School of Mathematics and Systems Engineering V¨axj¨o University SE-35195 V¨axj¨o Sweden firstname.lastname@msi.vxu.se Abstract This paper reports the results of experiments using memory-based learning to guide a de- terministic dependency parser for unrestricted natural language text. Using data from a small treebank of Swedish, memory-based classifiers for predicting the next action of the parser are constructed. The accuracy of a classifier as such is evaluated on held-out data derived from the treebank, and its performance as a parser guide is evaluated by parsing the held-out por- tion of the treebank. The evaluation shows that memory-based learning gives a signficant im- provement over a previous probabilistic model based on maximum conditional likelihood esti- mation and that the inclusion of lexical features improves the accuracy even further. 1 Introduction Deterministic dependency parsing has recently been pro- posed as a robust and efficient method for syntactic pars- ing of unrestricted natural language text (Yamada and Matsumoto, 2003; Nivre, 2003). Dependency parsing means that the goal of the parsing process is to construct a dependency graph, of the kind depicted in Figure 1. De- terministic parsing means that we always derive a single analysis for each input string. Moreover, this single anal- ysis is derived in a monotonic fashion with no redundancy or backtracking, which makes it possible to parse natural language sentences in linear time (Nivre, 2003). In this paper, we report experiments using memory- based learning (Daelemans, 1999) to guide the parser de- scribed in Nivre (2003), using data from a small tree- bank of Swedish (Einarsson, 1976). Unlike most pre- vious work on data-driven dependency parsing (Eisner, 1996; Collins et al., 1999; Yamada and Matsumoto, 2003; Nivre, 2003), we assume that dependency graphs are la- beled with dependency types, although the evaluation will give results for both labeled and unlabeled represen- tations. The paper is structured as follows. Section 2 gives the necessary background definitions and introduces the idea of guided parsing as well as memory-based learning. Section 3 describes the data used in the experiments, the evaluation metrics, and the models and algorithms used in the learning process. Results from the experiments are given in section 4, while conclusions and suggestions for further research are presented in section 5. 2 Background 2.1 Dependency Graphs The linguistic tradition of dependency grammar com- prises a large and fairly diverse family of theories and for- malisms that share certain basic assumptions about syn- tactic structure, in particular the assumption that syntactic structure consists of lexical nodes linked by binary re- lations called dependencies (see, e.g., Tesni`ere (1959), Sgall (1986), Mel’ˇcuk (1988), Hudson (1990)). Thus, the common formal property of dependency structures, as compared to the representations based on constituency (or phrase structure), is the lack of nonterminal nodes. In a dependency structure, every word token is depen- dent on at most one other word token, usually called its head or regent, which means that the structure can be represented as a directed graph, with …

Content truncated to 500 words