McDonald et al, ACL 2005: Non-Projective Dependency Parsing Using Spanning Tree Algorithms

Citation

R. McDonald, F. Pereira, K. Ribarov, J. Hajič. Non-projective dependency parsing using spanning tree algorithms, Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pp. 523-530, Vancouver, October 2005.

Online Version

PDF version

Summary

This paper addresses the problem of non-projective dependency prasing.

Given a sentence $\mathbf {x} =(x_{1},\ldots ,x_{n})$, we can construct a directed graph $\mathbf {G_{x}} =(V,E)$. The vertex set $V$ contains one vertex $v_{i}$ for each word $x_{i}$ in the sentence, plus a dummy vertex $v_{0}$ for the "root". The edge set $E$ contains all directed edges of the form $(v_{i},v_{j})$, where $0\leq i\leq n$, $1\leq j\leq n$, and $i\neq j$. Each edge has a score of the form $s(i,j)=\mathbf {w} \cdot \mathbf {f} (i,j)$, where $\mathbf {f} (i,j)$ is a feature vector depending on the words $x_{i}$ and $x_{j}$, and $\mathbf {w}$ is a weight factor.

A (non-projective) dependency parse tree $\mathbf {y}$ is a subgraph of $\mathbf {G_{x}}$ which covers all the vertices in $V$, and in which each vertex has exactly one predecessor (except for the root vertex which has no predecessor). The score of a dependency tree $\mathbf {y}$ is factored as the sum of the scores of its edges: $s(\mathbf {x} ,\mathbf {y} )=\sum _{(i,j)\in \mathbf {y} }\mathbf {w} \cdot \mathbf {f} (i,j)$

The decoding problem is to find the max-scoring dependency parse tree $\mathbf {y}$ given a sentence $\mathbf {x}$, assuming that the weight vector $\mathbf {w}$ is known. The learning problem is to find an optimal weight vector $\mathbf {w}$, such that the sum of the scores of the dependency parse trees in a training corpus is maximized.