Discriminative learning and spanning tree algorithms for dependency parsing

In this thesis we develop a discriminative learning method for dependency parsing using online large-margin training combined with spanning tree inference algorithms. We will show that this method provides state-of-the-art accuracy, is extensible through the feature set and can be implemented efficiently. Furthermore, we display the language independent nature of the method by evaluating it on over a dozen diverse languages as well as show its practical applicability through integration into a sentence compression system. We start by presenting an online large-margin learning framework that is a generalization of the work of Crammer and Singer [34, 37] to structured outputs, such as sequences and parse trees. This will lead to the heart of this thesis---discriminative dependency parsing. Here we will formulate dependency parsing in a spanning tree framework, yielding efficient parsing algorithms for both projective and non-projective tree structures. We will then extend the parsing algorithm to incorporate features over larger substructures without an increase in computational complexity for the projective case. Unfortunately, the non-projective problem then becomes NP-hard so we provide structurally motivated approximate algorithms. Having defined a set of parsing algorithms, we will also define a rich feature set and train various parsers using the online large-margin learning framework. We then compare our trained dependency parsers to other state-of-the-art parsers on 14 diverse languages: Arabic, Bulgarian, Chinese, Czech, Danish, Dutch, English, German, Japanese, Portuguese, Slovene, Spanish, Swedish and Turkish. Having built an efficient and accurate discriminative dependency parser, this thesis will then turn to improving and applying the parser. First we will show how additional resources can provide useful features to increase parsing accuracy and to adapt parsers to new domains. We will also argue that the robustness of discriminative inference-based learning algorithms lend themselves well to dependency parsing when feature representations or structural constraints do not allow for tractable parsing algorithms. Finally, we integrate our parsing models into a state-of-the-art sentence compression system to show its applicability to a real world problem