טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentIlan Tchernowitz
SubjectEffective Greedy Inference for Graph-based Non-Projective
Dependency Parsing
DepartmentDepartment of Industrial Engineering and Management
Supervisors Assistant Professor Reichart Roi
Dr. Yedidsion Liron
Full Thesis textFull thesis text - English Version


Abstract

The Dependency Parsing problem is a basic task in the Natural Language Processing (NLP) field. The task is to find the syntactic structure of an input sentence, which can in turn assist in higher level NLP tasks. This structure is the so called Dependency Tree, which is composed of a set of directed relations (arcs) over the words that form a rooted directed tree. Each directed arc between two words, (head, modifier), in the tree represents the syntactic dependency between them. For example, an adjective would have an incoming arc from the noun it describes.

One of the most popular formulations of this task is the graph based approach, in which the dependency tree coincides with the Maximum Weight Spanning Tree (MST) of the graph. The main limitation of this formulation is that it does not take into account complex syntactic structures, which consists of more than two words. Thus the problem was expanded to the Higher Order Dependency Parsing Problem, in which the MST is calculated with respect to a new scoring function which takes into account word triplets (for the 2nd order case), word quadruplets (for 3rd order) and so on. However, this formulation has been shown to be NP-Hard, hence sophisticated approximation techniques based on algorithms such as belief propagation and dual decomposition have been employed.

In contrast, we propose a simple greedy search approximation for this problem which is very intuitive and easy to implement. We implement the algorithm within a state of the art parser and experiment with the datasets of the CoNLL 2006 and 2007 shared task on multilingual dependency parsing. Our algorithm improves the run time of the parser by a factor of 1.43 while losing 1% in parsing accuracy on average across languages. Moreover, an ensemble method exploiting the joint power of the parsers, achieves an average accuracy 0.27% higher than the benchmark parser.