Parsing for Grammatical Relations via Graph Merging

Proceedings of the 21st Conference on Computational Natural Language Learning (CoNLL 2017), pages 26–35, Vancouver, Canada, August 3 - August 4, 2017. c⃝2017 Association for Computational Linguistics Parsing for Grammatical Relations via Graph Merging Weiwei Sun, Yantao Du and Xiaojun Wan Institute of Computer Science and Technology, Peking University The MOE Key Laboratory of Computational Linguistics, Peking University {ws,duyantao,wanxiaojun}@pku.edu.cn Abstract This paper is concerned with building deep grammatical relation (GR) analysis using data-driven approach. To deal with this problem, we propose graph merging, a new perspective, for building flexible de- pendency graphs: Constructing complex graphs via constructing simple subgraphs. We discuss two key problems in this per- spective: (1) how to decompose a com- plex graph into simple subgraphs, and (2) how to combine subgraphs into a coher- ent complex graph. Experiments demon- strate the effectiveness of graph merging. Our parser reaches state-of-the-art perfor- mance and is significantly better than two transition-based parsers. 1 Introduction Grammatical relations (GRs) represent functional relationships between language units in a sen- tence. Marking not only local but also a wide variety of long distance dependencies, GRs en- code in-depth information of natural language sen- tences. Traditionally, GRs are generated as a by- product by grammar-guided parsers, e.g. RASP (Carroll and Briscoe, 2002), C&C (Clark and Cur- ran, 2007b) and Enju (Miyao et al., 2007). Very recently, by representing GR analysis using gen- eral directed dependency graphs, Sun et al. (2014) and Zhang et al. (2016) showed that considerably good GR structures can be directly obtained using data-driven, transition-based parsing techniques. We follow their encouraging work and study the data-driven approach for producing GR analyses. The key challenge of building GR graphs is due to their flexibility. Different from surface syn- tax, the GR graphs are not constrained to trees, which is a fundamental consideration in design- ing parsing algorithms. To deal with this problem, we propose graph merging, a new perspective, for building flexible representations. The basic idea is to decompose a GR graph into several subgraphs, each of which captures most but not the complete information. On the one hand, each subgraph is simple enough to allow efficient construction. On the other hand, the combination of all subgraphs enables whole target GR structure to be produced. There are two major problems in the graph merging perspective. First, how to decompose a complex graph into simple subgraphs in a principled way? To deal with this problem, we considered structure-specific properties of the syntactically-motivated GR graphs. One key prop- erty is their reachability: In a given GR graph, almost every node is reachable from a same and unique root. If a node is not reachable, it is dis- connected from other nodes. This property en- sures a GR graph to be successfully decomposed into limited number of forests, which in turn can be accurately and efficiently built via tree parsing. We model the graph decomposition problem as an optimization problem and employ Lagrangian Re- laxation for solutions. Second, how to merge subgraphs into one co- …

Content truncated to 500 words