Monotonicity Marking from U niversal D ependency Trees (2021)

Abstract: Dependency parsing is a tool widely used in the field of Natural language processing and computational linguistics. However, there is hardly any work that connects dependency parsing to monotonicity, which is an essential part of logic and linguistic semantics. In this paper, we present a system that automatically annotates monotonicity information based on Universal Dependency parse trees. Our system utilizes surface-level monotonicity facts about quantifiers, lexical items, and token-level polarity information. We compared our system’s performance with existing systems in the literature, including NatLog and ccg2mono, on a small evaluation dataset. Results show that our system outperforms NatLog and ccg2mono.

## introduction the number of computational approaches for natural language inference (nli) has rapidly grown in recent years. most of the approaches can be categorized as (1) systems that translate sentences into first-order logic expressions and then apply theorem proving @xcite . (2) systems that use blackbox neural network approaches to learn the inference @xcite . (3) systems that apply natural logic as a tool to make inferences @xcite @xcite . compared to neural network approaches, systems that apply natural logic are more robust, formally more precise, and more explainable. several systems contributed to the third category @xcite @xcite to solve the nli task using monotonicity reasoning, a type of logical inference that is based on word replacement. below is an example of monotonicity reasoning: (b) not all students carry a laptop. as the example shows, the word replacement is based on the polarity mark (arrow) on each word. a monotone polarity (↑) allows an inference from (1a) to ( 1b ), where a more general concept laptop replaces the more specific concept macbook. an antitone polarity (↓) allows an inference from ( 1a ) to ( 1c ), where a more specific concept new students replaces the more general concept students. the direction of the polarity marks can be reversed by adding a downward entailment operator like not which allows an inference from (2a) to ( 2b ). thus, successful word placement relies on accurate polarity marks. to obtain the polarity mark for each word, an automatic polarity marking system is required to annotate a sentence by placing polarity mark on each word. this is formally called the polarization process. polarity markings support monotonicity reasoning, and thus are used by systems for natural language inference and data augmentations for language models. (maccartney and @xcite @xcite . in this paper, we introduce a novel automatic polarity marking system that annotates monotonicity information by applying a polarity algorithm on a universal dependency parse tree. our system is inspired by ccg2mono, an automatic polarity marking system @xcite used by @xcite . in contrast to ccg2mono, which derives monotonicity information from ccg @xcite parse trees, our system's polarization algorithm derives monotonicity information using universal dependency @xcite parse trees. there are several advantages of using ud parsing for polarity marking rather than ccg parsing. first, ud parsing is more accurate since the amount of training data for ud parsing is larger than those of ccg parsing. the high accuracy of ud parsing should lead to more accurate polarity annotation. second, ud parsing works for more types of text. overall, our system opens up a new framework for performing inference, semantics, and automated reasoning over ud representations. we will introduce the polarization algorithm's general steps, a set of rules we used to mark polarity on dependency parse trees, and comparisons between our system and some existing polarity marking tools, including natlog (maccartney and @xcite and ccg2mono. our evaluation focuses on a small dataset used to evaluate ccg2mono @xcite . our system outperforms natlog and ccg2mono. in particular, our system achieves the highest annotation accuracy on both the token level and the sentence level. ## related work universal dependencies (ud) @xcite was first designed to handle language tasks for many different languages. the syntactic annotation in ud mostly relies on dependency relations. words enter into dependency relations, and that is what ud tries to capture. there are 40 grammatical dependency relations between words, such as nominal subject (nsubj), relative clause modifier (acl:relcl), and determiner (det). a dependency relation connects a headword to a modifier. for example, in the dependency parse tree for all dogs eat food (figure 1 ), the dependency relation nsubj connects the modifier dogs and the headword eat. the system presented in this paper utilizes universal dependencies to obtain a dependency parse tree from a sentence. we will explain the details of the parsing process in the implementation section. there are two relevant systems of prior work: (1) the natlog (maccartney and @xcite system included in the stanford corenlp library @xcite ; (2) the ccg2mono system @xcite . the natlog system is a natural language inference system, a part of the stanford corenlp library. nat-log marks polarity to each sentence by applying a pattern-based polarization algorithm to the dependency parse tree generated by the stanford dependency parser. a list of downward-monotone and non-monotone expressions are defined along with an arity and a tregex pattern for the system to identify if an expression occurred. the ccg2mono system is a polarity marking tool that annotates a sentence by polarizing a ccg parse tree. the polarization algorithm of ccg2mono is based on van benthem (1986)'s work and moss (2012)'s continuation on the soundness of internalized polarity marking. the system uses a marked/order-enriched lexicon and can handle application rules, type-raising, and composition in ccg. the main polarization contains two steps: mark and polarize. for the mark step, the system puts markings on each node in the parse tree from leaf to root. for the polarize step, the system generates polarities to each node from root to leaf. compared to natlog, an advantage of ccg2mono is that it polarizes on both the word-level and the constituent level. ## comparison to existing systems we conducted several preliminary comparisons to two existing systems. first, we compared to nat-log's monotonicity annotator. natlog's annotator also uses dependency parsing. the polarization algorithm does pattern-based matching for finding occurrences of downward monotonicity information, and the algorithm only polarizes on word-level. in contrast, our system uses a tree-based polarization algorithm that polarizes both on word-level polarities and constituent level polarities. our intuition is that the tregex patterns used in natlog is not as common or as easily understandable as the binary tree structure, which is a classic data structure wildly used in the filed of computer science. according to the comparison on a list of sentences, natlog's annotator does not perform as well as our system. for example, for a phrase the rabbit, rabbit should have a polarity with no monotonicity information (=). however, natlog marks rabbit as a monotone polarity (↑). natlog also incorrectly polarizes sentences containing multiple negations. for example, for a triple negation sentence, no newspapers did not report no bad news, natlog gives: comparing to ccg2mono, our algorithm shares some similarities to its polarization algorithm. both of the systems polarize on a tree structure and rely on a lexicon of rules, and they both polarize on the word-level and the constituent level. one difference is that ccg2mono's algorithm contains two steps, the first step puts markings on each node, and the second step puts polarities on each node. our system does not require the step of adding markings and only contains the step of adding polarities on each node. our system has multiple advantages over ccg2mono. for parsing, our system uses ud pars-ing, which is more accurate than ccg parsing used by ccg2mono due to a large amount of training data. also, our system covers more types of text than ccg2mono because ud parsing works for a variety of text genres such as web texts, emails, reviews, and even informal texts like twitter tweets. @xcite @xcite . our system can also work for more languages than ccg2mono since ud parsing supports more languages than ccg parsing. overall, our system delivers more accurate polarization than ccg2mono. many times the ccg parser makes mistakes and leads to polarization mistakes later on. for example, in the annotation the ↓ market ↓ is ↓ not ↓ impossible ↓ to ↓ navigate ↓ , ccg2mono incorrectly marks every word as ↓. our system, on the other hand, uses ud parsing which has higher parsing accuracy than ccg parsing, and thus leads to fewer polarization mistakes compared to ccg2mono. for the expression above, our system correctly polarizes it as the ↑ @xmath0. our system also handles multi-word quantifiers better than ccg2mono. for example, for a multiword quantifier expression like all of the dogs, ccg2mono mistakenly marks dogs as =. our system, however, can correctly mark the expression: moreover, the core of ccg2mono does not include aspects of verbal semantics of downwardentailing operators like forgot and regret @xcite . for example ccg2mono's polarization for every ↑ member ↓ forgot ↑ to ↑ attend ↑ the ↑ @xmath1. in contrast, our system produces a correct result: every ↑ member ↓ forgot ↑ to ↓ attend ↓ the ↓ @xmath2. all three systems have difficulty polarizing sentences containing numbers. a scalar number n's monotonicity information is hard to determine because it can presenter different contexts: a single number n, without additional quantifiers or adjectives, can either mean at least n, at most n, exactly n, and around n. these contexts are syntactically hard to identify for a dependency parser or a ccg parser because it would require pragmatics and some background knowledge which the parsers do not have. for example, in the sentence a dog ate 2 rotten biscuits, the gold label for 2 @xmath3. however, our system marks this as "↓ since it considers the dependency parser in order to obtain a universal dependency parse tree from a sentence, we utilize a parser from stanza @xcite , a python natural language analysis package made by stanford. the neural pipeline in stanza allow us to use pretrained neural parsing models to generate universal dependency parse trees. to achieve optimal performance, we trained two neural parsing models: one parsing model trained on universal dependency english gum corpus @xcite . the pretrained parsing model achieved 90.0 las @xcite evaluation score on the testing data. ## evaluation ## conclusion and future work in this paper, we have demonstrated our system's ability to automatically annotate monotonicity information (polarity) for a sentence by conducting polarization on a universal dependency parse tree. the system operates by first converting the parse tree to a binary parse tree and then marking polarity on each node according to a lexicon of polarization rules. the system produces accurate annotations on sentences involving many different linguistic phenomena such as quantifiers, double negation, relative clauses, and conditionals. our system had better performance on polarity marking than existing systems including ccg2mono @xcite and natlog @xcite . additionally, by using ud parsing, our system offers many advantages. our system supports a variety of text genres and can be applied to many languages. in general, this paper opens up a new framework for performing inference, semantics, and automated reasoning over ud representations. for future work, an inference system can be made that utilizes the monotonicity information annotated by our system, which is similar to the mon-alog system @xcite . several improvements can be made to the system to obtain more accurate annotations. one improvement would be to incorporate pragmatics to help determine the monotonicity of a scalar number.