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

Introduction

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).

Comments

What do we like about the paper

What do we dislike about the paper


written by Lasha Abzianidze