[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki

[ Back to the navigation ]

Table of Contents

Non-projective Dependency Parsing using Spanning Tree Algorithms

Ryan McDonald, Fernando Pereira, Kiril Ribarov and Jan Hajič
Non-projective Dependency Parsing using Spanning Tree Algorithms
in proceedings of ACL 2005

report by Lasha Abzianidze


In the paper, authors formalize weighted dependency parsing as searching for maximum spanning trees (MST) in complete directed graphs, where vertices are words of a sentence and edges dependency relations. Based on this representation, they use Chu-Liu-Edmonds MST algorithm for non-projective parsing (allowing non-projective parses). With this result they got the less complex non-projecting parsing algorithm with <latex>O(n^2)</latex> time complexity than Eisner's algorithm for projective parsing (forbids non-projective parses) with <latex>O(n^3)</latex> time complexity. Moreover, the non-projective parsing algorithm shows the increase in efficiency and accuracy for languages with non-projective dependencies (checked on Czech PDT).


What do we like about the paper

What do we dislike about the paper

written by Lasha Abzianidze

[ Back to the navigation ] [ Back to the content ]