The Application of Constraint Rules to Data-driven Parsing

Proceedings of Recent Advances in Natural Language Processing, pages 232–238, Hissar, Bulgaria, Sep 7–9 2015. The Application of Constraint Rules to Data-driven Parsing Sardar Jaf The University of Manchester jafs@cs.man.ac.uk Allan Ramsay The University of Manchester ramsaya@cs.man.ac.uk Abstract In this paper, we show an approach to ex- tracting different types of constraint rules from a dependency treebank. Also, we show an approach to integrating these con- straint rules into a dependency data-driven parser, where these constraint rules in- form parsing decisions in specific situa- tions where a set of parsing rule (which is induced from a classifier) may recommend several recommendations to the parser. Our experiments have shown that parsing accuracy could be improved by using dif- ferent sets of constraint rules in combina- tion with a set of parsing rules. Our parser is based on the arc-standard algorithm of MaltParser but with a number of exten- sions, which we will discuss in some de- tail. 1 Introduction In this paper we present a new implementation of the arc-standard algorithm of MaltParser (Joakim, 2003; Nivre, 2006; Nivre, 2008). The key fea- tures of this implementation are that (i) it includes a new approach to handling non-projective trees (Section 3); (ii) it allows the inclusion of infor- mation about local subtrees as an extra guide to parsing (Section 8); (iii) the assignment of labels to arcs is carried out as a separate phase of analy- sis rather than during the determination of depen- dency relations between words (Section 5). We compare the performance of the arc-standard ver- sion of MaltParser with four different versions of our parser in Section 9. 2 Deterministic Shift-reduce Parsing The arc-standard algorithm deterministically gen- erates dependency trees using two data-structures: a queue of input words, and a stack of items that have been looked at by the parser. Three parse actions are applied to the queue and the stack: SHIFT, LEFT-ARC and RIGHT-ARC. SHIFT moves the head of the queue onto the top of the stack, LEFT-ARC makes the head of the queue a parent of the topmost item on the stack and pops this item from the stack, and RIGHT-ARC makes the topmost item on the stack a parent of the head of the queue, removing the head of the queue and moving the topmost item on the stack back to the queue. At each parse transition the parser uses a classifier trained on a dependency treebank for predicting the next parse action given the current state of the parser. 3 Non-projective Parsing The arc-standard version of the MaltParser fails to deal with non-projective trees. Figure 1 shows a well-known example of a Czech sentence with a non-projective dependency tree. Figure 2 shows the problem with the ba- sic algorithm. In step 8 from Figure 2 the parser may perform either LEFT-ARC, RIGHT-ARC, or SHIFT, but none of these operations lead to pro- ducing a tree matching the original non-projective tree. According to the dependency relations that are extracted from the tree (as shown at …

Content truncated to 500 words