A Transition-based Parser for Unscoped Episodic Logical Forms (2021)

Abstract: “Episodic Logic: Unscoped Logical Form” (EL-ULF) is a semantic representation capturing predicate-argument structure as well as more challenging aspects of language within the Episodic Logic formalism. We present the first learned approach for parsing sentences into ULFs, using a growing set of annotated examples. The results provide a strong baseline for future improvement. Our method learns a sequence-to-sequence model for predicting the transition action sequence within a modified cache transition system. We evaluate the efficacy of type grammar-based constraints, a word-to-symbol lexicon, and transition system state features in this task. Our system is available at https://github.com/genelkim/ulf-transition-parser . We also present the first official annotated ULF dataset at https://www.cs.rochester.edu/u/gkim21/ulf/resources/ .

## introduction el-ulf was recently introduced as a semantic representation that accurately captures linguistic semantic structure within an expressive logical formalism, while staying close to the surface language, facilitating annotation of a dataset that can be used to train a parser @xcite . the goal is to overcome the limitations of fragile rulebased systems, such as the episodic logic (el) parser used for gloss axiomatization @xcite and domain-specific ulf parsers used for schema generation and dialogue systems @xcite ). el's rich model-theoretic semantics enables deductive inference, uncertain inference, and natural logic-like inference @xcite @xcite ; and the unscoped version, el-ulf, supports natural logic-like monotonic inferences @xcite (i.pro ( @xcite (to @xcite and inferences based on some classes of entailments, presuppositions, and implicatures which are common in discourse @xcite . the lack of robust parsers have prevented large scale experiments using these powerful representations. we will refer to el-ulf as simply ulf in the rest of this paper. in this paper we present the first system that learns to parse ulfs of english sentences from an annotated dataset, and provide the first official release of the annotated ulf corpus, whereon our system is trained. we evaluate the parser using sembleu @xcite and a modified version of smatch @xcite , establishing a baseline for future work. an initial effort in learning a parser producing a representation as rich as ulf is bound to face a data sparsity issue. 1 thus a major goal in our choice of a transition-system-based parser has been to reduce the search space of the model. we investigate three additional methods of tackling this issue: @xcite constraining actions in the decoding phase based on faithfulness to the ulf type system, (2) using a lexicon to limit the possible word-aligned symbols that the parser can generate, and (3) defining learnable features of the transition system state. ## unscoped logical form episodic logic is an extension of first-order logic (fol) that closely matches the form and ex-pressivity of natural language, using reifying operators to enrich the domain of basic individuals and situations with propositions and kinds, keeping the logic first-order. it also uses other type-shifters, e.g., for mapping predicates to modifiers, and allows for generalized quantifiers @xcite . ulf fully specifies the semantic type structure of el by marking the types of the atoms and all of the predicate-argument relationships while leaving operator scope, anaphora, and word sense unresolved @xcite . ulf is the critical first step to parsing full-fledged el formulas. types are marked on ulf atoms with a suffixed tag resembling the part-of-speech (e.g., .v, .n, .pro, .d for verbs, nouns, pronouns, and determiners, respectively). names are instead marked with pipes (e.g. |john|) and a closed set of logical and macro operators have unique types and are left without a type marking. each suffix denotes a set of possible semantic denotations, e.g. .pro always denotes an entity and .v denotes an n-ary predicate where n can vary. the symbol without the suffix or pipes is called the stem. type shifters in ulf maintain coherence of the semantic type compositions. for example, the type shifter adv-a maps a predicate into a verbal predicate modifier as in the prepositional phrase "in my new shoes" in figure 1 , as opposed to its predicative use "a spider is in my new shoes". the syntactic structure is closely reflected in ulf even under syntactic movement through the use of rewriting macros which explicitly mark these occurrences and upon expansion make the exact semantic argument structure available. also, further resembling syntactic structure, ulfs are trees. the operators in operator-argument relations of ulf can be in first or second position, disambiguated by the types of the participating expressions. this further reduces the amount of word reordering between english and ulfs. the el type system only allows function application for combining types, a, b , @xmath0, much like montagovian semantics @xcite , but without type-raising. ## background currently, there is semantic parsing research occurring on multiple representational fronts, which is showcased by the cross-framework meaning representation parsing task @xcite . the key differentiating factor of ulf from other meaning representations is the model-theoretic expres-sive capacity. to highlight this, here are a few limitations of notable representations: amr @xcite ) neglects issues such as articles, tense, and nonintersective modification in favor of a canonicalized form that abstracts away from the surface structure; minimal recursion semantics @xcite captures metalevel semantics for which inference systems cannot be built directly based on model-theoretic notions of truth and entailment; and extant semantic parsers for drss generate fol-equivalent lfs, thus precludes proper treatment of phenomena such as generalized quantifiers, modification, and reification. due to space limitations, we refer to @xcite for an in-depth description and motivation of ulf, including comparisons to other representations. we also refer to @xcite which places el-the antecedent of ulf-in a broad context. our ulf parser development draws inspiration from the body of semantic parsing research on graph-based formalism of natural language, in particular, the recent advances in amr parsing @xcite . the core organization of our parser is based on @xcite , which uses a sequence-to-sequence model to predict the transition action sequence for a cache transition system with transition system features and hard attention alignment. there are many transition-based parsers that were developed for parsing meaning representations @xcite @xcite . these are mainly based on what's called an arceager parsing method, termed by abney and @xcite . arc-eager parsing greedily adds edges between nodes before full constituents are formed, which keeps the partial graph as connected as possible during the parsing process @xcite . they modify arc-eager parsing in various ways to generalize to the graph structures. our transition system can be considered a modification of bottomup arc-standard parsing due to restrictions on arc formation. while this leads to a longer action sequence for parsing, the parser's access to complete constituents allows promotion-based symbol generation for unary operators such as type shifters and standard bottom-up type analysis for constrained parsing. ## our transition system our transition system is a modification of the cache transition system @xcite which has been shown to be effective in amr parsing @xcite . the distinctive aspect of our version is that the transition system generates nodes that are derived, but distinct, from the input sequence. we call it a node generative transition system. this eliminates the two-stage parsing framework of @xcite . our transition system also restricts the parses to be bottom-up to enable node generation and decoding constraints by the available constituents since ulf has an bottom-up compositional type system. the transition parser configuration is while the size of the cache is a hyperparameter that can be set for the cache transition parser, we restrict the cache size to 2 in order to keep the oracle simple despite the newly added actions. this means that only tree structures can be parsed. in describing the transition system, we differentiate between phases and actions. phases are classes of states in the transition system and the actions move between states. figure 2 shows the full state transition diagram and shows how the phases dictate which actions can be taken and how actions move between phases. actions may take variables to specify how to move into the next phase. phases also determine which features go into the determining the next action. we will write phases in small caps (e.g. gen) and actions in bold (e.g. tokengen) for clarity. the gen and promote phases are novel to our transition system. the gen phase generates graph vertices that are transformations of the buffer values. this allows us to put words of the input sentence in β instead of a pre-computed ulf atom sequence. the promote phase enables contextsensitive symbol generation. it generates unaligned symbols in the context of an existing constituent in the partial graph. (use of logical operators without word alignments only makes sense with respect to something for the operators to act on.) we now describe each of the actions in the transition system. the following are parser actions that were almost directly inherited from the vanilla cache transition parser. we introduce two sets, s p and s s , which define the vocabulary of the two unaligned symbol generation actions: promotesym and symgen, respectively. s p consists of logical and macro operators that do not align with english words. s s consists of symbols that could not be aligned in the training set and are not members of s p . ## model our model has three basic components: (1) a word sequence encoder, (2) a ulf atom sequence encoder, and (3) an action decoder, all of which are figure 4 : the model consists of a sentence-encoding bilstm, a symbol-encoding lstm, and an action-decoding lstm. new symbols generated in the gen and promote phases of the transition system are appended to the symbol sequence. the transition system supplies hard attention pointers that select the relevant word and symbol embeddings. these are concatenated with the transition state feature vector and supplied as input to the action decoder, which predicts the next action that updates the transition system. lstms. during decoding, the transition system configuration, c, is updated with decoded actions and used to organize the action decoder inputs using the sequence encoders. the system models the following probability ## parsing the model is trained on the cross-entropy loss of the model probability (2) using the oracle action sequence. both training and decoding are limited to a maximum action length of 800. for the training set the oracle has an average action length of 134 actions and a maximum action length of 1477. ## experiments we ran our experiments on a hand-annotated dataset of ulfs totaling 1,738 sentences @xcite . the dataset is a mixture of sentences from crowd-sourced translations, news text, a question dataset, and novels. the distribution of sentences leans towards more questions, requests, clause-taking verbs, and counterfactuals because a portion of the dataset comes from the dataset used by @xcite for generating inferences from ulfs of those constructions. the data is split by segmenting the dataset into 10 sentence segments and distributing them in a round-robin fashion, with the training set receiving eight chunks in each round. this splitting method is designed to allow document-level topics to distribute into splits while limiting any performance inflation of the dev and test results that can result when localized word-choice and grammatical patterns are distributed into all splits. @xcite found that interannotator agreement (ia) on ulfs using the el-smatch metric @xcite is 0.79. 8 we add a second pass to further reduce variability in our annotations. 9 further details about the dataset are available in appendix a and the complete annotation guidelines are available as part of the dataset. ulf-amr in order to use parsing and evaluation methods developed for amr parsing (banarescu et al., 2013a), we rewrite ulfs in penman format @xcite ) by introducing a node for each ulf atom and generating left-to-right arcs in the order that they appear (:arg0, :arg1, etc.), assuming the leftmost constituent is the parent. in order to handle non-atomic operators in penman format which only allows atomic nodes, we introduce a complex node with an :instance edge to mark the identity of the non-atomic operator. setup we evaluate the model with sem-bleu @xcite , a metric for parsing accuracy of amrs @xcite . this metric extends bleu @xcite to node-and edge-labeled graphs. we also measure el-smatch, a generalization of smatch to graphs with non-atomic nodes, for analysis of the model since it has f1, precision, and recall components. the tokens, lemmas, pos tags, ner tags, and dependencies are all extracted using the stanford corenlp toolkit @xcite . in all experiments the model was trained for 25 epochs. starting at the 12th epoch we measured the sem-bleu performance on the dev split with beam size 3. hyperparameters were tuned manually on the dev split performance of a smaller, preliminary version of the annotation corpus. we use roberta-base embeddings with frozen parameters, 300 dimensional glove embeddings, and 100 dimensional t i , l i , p i , action, and symbol embeddings. the word encoder is 3 layers. the symbol encoder and action decoder are 2 layers. experiments were run on a single nvidia tesla k80 or geforce rtx 2070 gpu. training the full model 8 cf. amr is reported to have about 0.8 ia using the smatch metric @xcite 9 we did not measure iaa on our dataset and take the prior report as an lower-end estimate given the similarity of our annotations methods and our additional review phase. our annotation process was collaborative and result in a single annotation per sentence so iaa cannot be measured. takes about 6 hours. the full tables of results and default parameters are available in appendix d. ## conclusion we presented the first annotated ulf dataset and the first parser trained on such a dataset. we showed that our parser is a strong baseline, outperforming existing semantic parsers from a similar task. surprisingly, our experiments showed that even in this low-resource setting, constrained decoding with a lexicon or a type system does more harm than good. however, the symbol generation method and features designed for ulfs result in a performance lead over using an amr parser with minimal representational assumptions. we hope that releasing this dataset will spur other efforts into improving ulf parsing. this of course includes expanding the dataset, using our comprehensive annotation guidelines and tools; but we see many additional avenues of improvement. the type grammar opens up many promising possibilities: sampling of silver data (in conjunction with ulf to english generation @xcite ), use as a weighted constraint, or direct incorporation into a model to avoid the pitfalls we observed in our simple approach to semantic type enforcement. sheng zhang, xutai ma, kevin duh, and benjamin van durme. 2019a. amr parsing as sequence-tograph transduction. in proceedings of the 57th annual meeting of the association for computational linguistics, pages 80-94, florence, italy. association for computational linguistics. sheng zhang, xutai ma, kevin duh, and benjamin van durme. 2019b. broad-coverage semantic parsing as transduction. in proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (emnlp-ijcnlp), pages 3786-3798, hong kong, china. association for computational linguistics.