Koo and Collins ACL 2010

Citation

Koo, T. and Collins, M. 2010. Efficient Third-Order Dependency Parsers. In Proceedings of ACL, pp. 1-11. Association for Computational Linguistics.

Online version

ACL

Summary

This paper presents a higher-order dependency parser that can evaluate substructures containing three dependencies, using both sibling-style and grandchild-style interactions. The algorithms presented require only $O(n^{4})$ time and were evaluated on the Penn Treebank and the Prague Dependency Treebank. The implementation code was publicly released [1].

Dependency parsing is defined as a search for the highest-scoring analysis of $x$:

$y^{*}(x)=_{y\in Y(x)}^{argmax}{\textrm {Score}}(x,y)$

Where $Y(x)$ is the set of all trees compatible with $x$ and ${\textrm {Score}}(x,y)$evaluates the event that tree $y$ is the analysis of sentence $x$. Directly solving the equation is unfeasible because the number of possible trees grow exponentially with the length of the sentence. A common strategy is to factor each dependency tree into small parts which can be scored individually, then:

${\textrm {Score}}(x,y)=\sum _{p\in y}{\textrm {ScorePart}}(x,p)$

Experimental results

Bla bla.

Related papers

Bla bla.