Abstract In this work, we present a phenomenon-oriented comparative analysis of the two dominant approaches in English Resource Semantic (ERS) parsing: classic, knowledge-intensive and neural, data-intensive models. To reflect state-of-the-art neural NLP technologies, a factorization-based parser is introduced that can produce Elementary Dependency Structures much more accurately than previous data-driven parsers. We conduct a suite of tests for different linguistic phenomena to analyze the grammatical competence of different parsers, where we show that, despite comparable performance overall, knowledge- and data-intensive models produce different types of errors, in a way that can be explained by their theoretical properties. This analysis is beneficial to in-depth evaluation of several representative parsing techniques and leads to new directions for parser development.

We propose variable-in-situ logico-semantic graphs to bridge the gap between semantic graph and logical form parsing.The new type of graph-based meaning representation allows us to include analysis for scope-related phenomena, such as quantification, negation and modality, in a way that is consistent with the state-of-the-art underspecification approach.Moreover, the well-formedness of such a graph is clear, since model-theoretic interpretation is available.We demonstrate the effectiveness of this new perspective by developing a new state-of-the-art semantic parser for Minimal Recursion Semantics.At the core of this parser is a novel neural graph rewriting system which combines the strengths of Hyperedge Replacement Grammar, a knowledgeintensive model, and Graph Neural Networks, a data-intensive model.Our parser achieves an accuracy of 92.39% in terms of ELEMENTARY DEPENDENCY MATCH, which is a 2.88 point improvement over the best data-driven model in the literature.The output of our parser is highly coherent: at least 91% graphs are valid, in that they allow at least one sound scoperesolved logical form.

A key problem in processing graph-based meaning representations is graph parsing, i.e. computing all possible derivations of a given graph according to a (competence) grammar.We demonstrate, for the first time, that exact graph parsing can be efficient for large graphs and with large Hyperedge Replacement Grammars (HRGs).The advance is achieved by exploiting locality as terminal edge-adjacency in HRG rules.In particular, we highlight the importance of 1) a terminal edge-first parsing strategy, 2) a categorization of a subclass of HRG, i.e. what we call Weakly Regular Graph Grammar, and 3) distributing argumentstructures to both lexical and phrasal rules.

This paper is concerned with semantic parsing for English as a second language (ESL).Motivated by the theoretical emphasis on the learning challenges that occur at the syntaxsemantics interface during second language acquisition, we formulate the task based on the divergence between literal and intended meanings.We combine the complementary strengths of English Resource Grammar, a linguistically-precise hand-crafted deep grammar, and TLE, an existing manually annotated ESL UD-TreeBank with a novel reranking model.Experiments demonstrate that in comparison to human annotations, our method can obtain a very promising SemBanking quality.By means of the newly created corpus, we evaluate state-of-the-art semantic parsing as well as grammatical error correction models.The evaluation profiles the performance of neural NLP techniques for handling ESL data and suggests some research directions.

Natural Language Processing (NLP) tasks are usually performed word by word on textual inputs.We can use arbitrary symbols to represent the linguistic meaning of a word and use these symbols as inputs.As "alternatives" to a text representation, we introduce Soundex, MetaPhone, NYSIIS, logogram to NLP, and develop fixed-output-length coding and its extension using Huffman coding.Each of those codings combines different character/digital sequences and constructs a new vocabulary based on codewords.We find that the integration of those codewords with text provides more reliable inputs to Neural-Networkbased NLP systems through redundancy than text-alone inputs.Experiments demonstrate that our approach outperforms the state-ofthe-art models on the application of machine translation, language modeling, and part-ofspeech tagging.The source code is available at https://github.com/abdulrafae/coding nmt.

We report our work on building linguistic resources and data-driven parsers in the grammatical relation (GR) analysis for Mandarin Chinese. Chinese, as an analytic language, encodes grammatical information in a highly configurational rather than morphological way. Accordingly, it is possible and reasonable to represent almost all grammatical relations as bilexical dependencies. In this work, we propose to represent grammatical information using general directed dependency graphs. Both only-local and rich long-distance dependencies are explicitly represented. To create high-quality annotations, we take advantage of an existing TreeBank, namely, Chinese TreeBank (CTB), which is grounded on the Government and Binding theory. We define a set of linguistic rules to explore CTB’s implicit phrase structural information and build deep dependency graphs. The reliability of this linguistically motivated GR extraction procedure is highlighted by manual evaluation. Based on the converted corpus, data-driven, including graph- and transition-based, models are explored for Chinese GR parsing. For graph-based parsing, a new perspective, graph merging, is proposed for building flexible dependency graphs: constructing complex graphs via constructing simple subgraphs. Two key problems are discussed in this perspective: (1) how to decompose a complex graph into simple subgraphs, and (2) how to combine subgraphs into a coherent complex graph. For transition-based parsing, we introduce a neural parser based on a list-based transition system. We also discuss several other key problems, including dynamic oracle and beam search for neural transition-based parsing. Evaluation gauges how successful GR parsing for Chinese can be by applying data-driven models. The empirical analysis suggests several directions for future study.

We demonstrate that an SHRG-based parser can produce semantic graphs much more accurately than previously shown, by relating synchronous production rules to the syntacto-semantic composition process.Our parser achieves an accuracy of 90.35 for EDS (89.51 for DMRS) in terms of ELEMENTARY DEPENDENCY MATCH, which is a 4.87 (5.45) point improvement over the best existing data-driven model, indicating, in our view, the importance of linguistically-informed derivation for data-driven semantic parsing.This accuracy is equivalent to that of English Resource Grammar guided models, suggesting that (recurrent) neural network models are able to effectively learn deep linguistic knowledge from annotations.

Motivated by the positive impact of empty categories on syntactic parsing, we study neural models for pre-and in-parsing detection of empty categories, which has not previously been investigated.We find several non-obvious facts: (a) BiLSTM can capture non-local contextual information which is essential for detecting empty categories, (b) even with a BiLSTM, syntactic information is still able to enhance the detection, and (c) automatic detection of empty categories improves parsing quality for overt words.Our neural ECD models outperform the prior state-of-the-art by significant margins.

A DAG automaton is a formal device for manipulating graphs.By augmenting a DAG automaton with transduction rules, a DAG transducer has potential applications in fundamental NLP tasks.In this paper, we propose a novel DAG transducer to perform graph-to-program transformation.The target structure of our transducer is a program licensed by a declarative programming language rather than linguistic structures.By executing such a program, we can easily get a surface string.Our transducer is designed especially for natural language generation (NLG) from type-logical semantic graphs.Taking Elementary Dependency Structures, a format of English Resource Semantics, as input, our NLG system achieves a BLEU-4 score of 68.07.This remarkable result demonstrates the feasibility of applying a DAG transducer to resolve NLG, as well as the effectiveness of our design.

We present experiments for cross-domain semantic dependency analysis with a neural Maximum Subgraph parser.Our parser targets 1-endpoint-crossing, pagenumber-2 graphs which are a good fit to semantic dependency graphs, and utilizes an efficient dynamic programming algorithm for decoding.For disambiguation, the parser associates words with BiLSTM vectors and utilizes these vectors to assign scores to candidate dependencies.We conduct experiments on the data sets from Se-mEval 2015 as well as Chinese CCGBank.Our parser achieves very competitive results for both English and Chinese.To improve the parsing performance on cross-domain texts, we propose a data-oriented method to explore the linguistic generality encoded in English Resource Grammar, which is a precisionoriented, hand-crafted HPSG grammar, in an implicit way.Experiments demonstrate the effectiveness of our data-oriented method across a wide range of conditions.

This paper studies semantic parsing for interlanguage (L2 1 ), taking semantic role labeling (SRL) as a case task and learner Chinese as a case language.We first manually annotate the semantic roles for a set of learner texts to derive a gold standard for automatic SRL.Based on the new data, we then evaluate three off-the-shelf SRL systems, i.e., the PCFGLA-parser-based, neural-parserbased and neural-syntax-agnostic systems, to gauge how successful SRL for learner Chinese can be.We find two non-obvious facts: 1) the L1-sentence-trained systems performs rather badly on the L2 data; 2) the performance drop from the L1 data to the L2 data of the two parser-based systems is much smaller, indicating the importance of syntactic parsing in SRL for interlanguages.Finally, the paper introduces a new agreement-based model to explore the semantic coherency information in the large-scale L2-L1 parallel data.We then show such information is very effective to enhance SRL for learner texts.Our model achieves an F-score of 72.06, which is a 2.02 point improvement over the best baseline.

We study the Maximum Subgraph problem in deep dependency parsing.We consider two restrictions to deep dependency graphs: (a) 1-endpoint-crossing and (b) pagenumber-2.Our main contribution is an exact algorithm that obtains maximum subgraphs satisfying both restrictions simultaneously in time O(n 5 ).Moreover, ignoring one linguistically-rare structure descreases the complexity to O(n 4 ).We also extend our quartic-time algorithm into a practical parser with a discriminative disambiguation model and evaluate its performance on four linguistic data sets used in semantic dependency parsing.

We model a dependency graph as a book, a particular kind of topological space, for semantic dependency parsing.The spine of the book is made up of a sequence of words, and each page contains a subset of noncrossing arcs.To build a semantic graph for a given sentence, we design new Maximum Subgraph algorithms to generate noncrossing graphs on each page, and a Lagrangian Relaxation-based algorithm to combine pages into a book.Experiments demonstrate the effectiveness of the book embedding framework across a wide range of conditions.Our parser obtains comparable results with a state-of-the-art transition-based parser.

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 dependency graphs: Constructing complex graphs via constructing simple subgraphs.We discuss two key problems in this perspective: (1) how to decompose a complex graph into simple subgraphs, and (2) how to combine subgraphs into a coherent complex graph.Experiments demonstrate the effectiveness of graph merging.Our parser reaches state-of-the-art performance and is significantly better than two transition-based parsers.

This paper is concerned with whether deep syntactic information can help surface parsing, with a particular focus on empty categories.We design new algorithms to produce dependency trees in which empty elements are allowed, and evaluate the impact of information about empty category on parsing overt elements.Such information is helpful to reduce the approximation error in a structured parsing model, but increases the search space for inference and accordingly the estimation error.To deal with structure-based overfitting, we propose to integrate disambiguation models with and without empty elements, and perform structure regularization via joint decoding.Experiments on English and Chinese TreeBanks with different parsing models indicate that incorporating empty elements consistently improves surface parsing.

We propose a new Maximum Subgraph algorithm for first-order parsing to 1endpoint-crossing, pagenumber-2 graphs.Our algorithm has two characteristics: (1) it separates the construction for noncrossing edges and crossing edges; (2) in a single construction step, whether to create a new arc is deterministic.These two characteristics make our algorithm relatively easy to be extended to incorporiate crossing-sensitive second-order features.We then introduce a new algorithm for quasi-second-order parsing.Experiments demonstrate that second-order features are helpful for Maximum Subgraph parsing.

From the perspective of structural linguistics, we explore paradigmatic and syntagmatic lexical relations for Chinese POS tagging, an important and challenging task for Chinese language processing. Paradigmatic lexical relations are explicitly captured by word clustering on large-scale unlabeled data and are used to design new features to enhance a discriminative tagger. Syntagmatic lexical relations are implicitly captured by syntactic parsing in the constituency formalism, and are utilized via system combination. Experiments on the Penn Chinese Treebank demonstrate the importance of both paradigmatic and syntagmatic relations. Our linguistically motivated, hybrid approaches yield a relative error reduction of 18% in total over state-of-the-art baselines. Despite the effectiveness to boost accuracy, computationally expensive parsers make hybrid systems inappropriate for many realistic NLP applications. In this article, we are also concerned with improving tagging efficiency at test time. In particular, we explore unlabeled data to transfer the predictive power of hybrid models to simple sequence models. Specifically, hybrid systems are utilized to create large-scale pseudo training data for cheap models. Experimental results illustrate that the re-compiled models not only achieve high accuracy with respect to per token classification, but also serve as a front-end to a parser well.

Derivations under different grammar formalisms allow extraction of various dependency structures. Particularly, bilexical deep dependency structures beyond surface tree representation can be derived from linguistic analysis grounded by CCG, LFG, and HPSG. Traditionally, these dependency structures are obtained as a by-product of grammar-guided parsers. In this article, we study the alternative data-driven, transition-based approach, which has achieved great success for tree parsing, to build general dependency graphs. We integrate existing tree parsing techniques and present two new transition systems that can generate arbitrary directed graphs in an incremental manner. Statistical parsers that are competitive in both accuracy and efficiency can be built upon these transition systems. Furthermore, the heterogeneous design of transition systems yields diversity of the corresponding parsing models and thus greatly benefits parser ensemble. Concerning the disambiguation problem, we introduce two new techniques, namely, transition combination and tree approximation, to improve parsing quality. Transition combination makes every action performed by a parser significantly change configurations. Therefore, more distinct features can be extracted for statistical disambiguation. With the same goal of extracting informative features, tree approximation induces tree backbones from dependency graphs and re-uses tree parsing techniques to produce tree-related features. We conduct experiments on CCG-grounded functor–argument analysis, LFG-grounded grammatical relation analysis, and HPSG-grounded semantic dependency analysis for English and Chinese. Experiments demonstrate that data-driven models with appropriate transition systems can produce high-quality deep dependency analysis, comparable to more complex grammar-driven models. Experiments also indicate the effectiveness of the heterogeneous design of transition systems for parser ensemble, transition combination, as well as tree approximation for statistical disambiguation.

Yantao Du, Weiwei Sun, Xiaojun Wan. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2015.

This paper is concerned with building linguistic resources and statistical parsers for deep grammatical relation (GR) analysis of Chinese texts.A set of linguistic rules is defined to explore implicit phrase structural information and thus build high-quality GR annotations that are represented as general directed dependency graphs.The reliability of this linguistically-motivated GR extraction procedure is highlighted by manual evaluation.Based on the converted corpus, we study transition-based, datadriven models for GR parsing.We present a novel transition system which suits GR graphs better than existing systems.The key idea is to introduce a new type of transition that reorders top k elements in the memory module.Evaluation gauges how successful GR parsing for Chinese can be by applying datadriven models.

We present a comparative study of transition-, graph- and PCFG-based models aimed at illuminating more precisely the likely contribution of CFGs in improving Chinese dependency parsing accuracy, especially by combining heterogeneous models. Inspired by the impact of a constituency grammar on dependency parsing, we propose several strategies to acquire pseudo CFGs only from dependency annotations. Compared to linguistic grammars learned from rich phrase-structure treebanks, well designed pseudo grammars achieve similar parsing accuracy and have equivalent contributions to parser ensemble. Moreover, pseudo grammars increase the diversity of base models; therefore, together with all other models, further improve system combination. Based on automatic POS tagging, our final model achieves a UAS of 87.23%, resulting in a significant improvement of the state of the art.