Koo and Collins ACL 2010

From Cohen Courses
Jump to navigationJump to search

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 time and were evaluated on the Penn Treebank and the Prague Dependency Treebank. The implementation code was publicly released [1].

Background

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

where is the set of all trees compatible with and evaluates the event that tree is the analysis of . 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:

The order of a part is defined according to the number of dependencies it contains, a terminology used in previous parsing algorithms, such as first-order factorization and second-order sibling factorization. The factorizations in this new third-order parser uses the following parts:

Dpo3-01.png

Description of new method

The overall method augments each span with a grandparent index. The concept of spans comes from the Eisner algorithm structures, where complete spans consist of a head-word and its descendants on one side, and incomplete spans consist of a dependency and the region between the head and modifier. Based on this, the paper introduces three parsing algorithms based on three different models.

Model 0: all grandchildren

This model factors each dependency tree into a set of grandchild parts (pairs of dependencies connected head to tail). Formally, a triple of indices where and are dependencies. Both complete and incomplete spans are augmented with grand-parent indices to produced g-spans. The next figure describes complete and incomplete g-spans and provides a graphical specification of the dynamic-programming algorithm:

Dpo3-02.png

Model 0 parsing algorithm is similar to the first-order parser, but every recursive construction sets the grandparent indices of the smaller g-spans. Model 0 can be parsed by adapting standard top-down or bottom-up chart parsing techniques. The following pseudocode sketches a bottom-up chart parser for this model:

Dpo3-03.png

The complexity of the algorithm is time and space. This is still a second-order parsing algorithm but the next models (1 and 2) are third-order parsers.

Model 1: all grand-siblings

This model decomposes each tree into a set of grand-sibling parts: 4-tuples of indices where is a sibling part and and are grandchild parts. These factorizations are parsed using sibling g-spans, as graphically described in the next figure:

Dpo3-04.png

The parsing algorithm for Model 1 is similar to the second-order sibling parser with the addition of grandparent indices. Like Model 0, Model 1 can also be parsed adapting standard chart-parsing techniques and despite using third-order parts, they also require only time and space.

Experimental results

Bla bla.

Related papers

Bla bla.