Learned Incremental Representations for Parsing

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 3086 - 3095 May 22-27, 2022 c⃝2022 Association for Computational Linguistics Learned Incremental Representations for Parsing Nikita Kitaev Thomas Lu Computer Science DivisionDan Klein University of California, Berkeley {kitaev,tlu2000,klein}@berkeley.edu Abstract We present an incremental syntactic represen- tation that consists of assigning a single dis- crete label to each word in a sentence, where the label is predicted using strictly incremen- tal processing of a prefix of the sentence, and the sequence of labels for a sentence fully de- termines a parse tree. Our goal is to induce a syntactic representation that commits to syn- tactic choices only as they are incrementally revealed by the input, in contrast with standard representations that must make output choices such as attachments speculatively and later throw out conflicting analyses. Our learned representations achieve 93.72 F1 on the Penn Treebank with as few as 5 bits per word, and at 8 bits per word they achieve 94.97 F1, which is comparable with other state of the art pars- ing models when using the same pre-trained embeddings. We also provide an analysis of the representations learned by our system, in- vestigating properties such as the interpretable syntactic features captured by the system and mechanisms for deferred resolution of syntac- tic ambiguities. 1 Introduction Language comprehension in humans is, to a non- trivial extent, an incremental process. Human speech is heard word by word, and, while the pre- cise nature of the incrementality is not a settled question, a listener does not wait for a full sentence to end before any processing or understanding can begin. In contrast, some of the highest-performing machine models for syntactic parsing operate pre- cisely in this manner: they require a full sentence as input, and perform deeply bidirectional processing to produce their outputs. Human capabilities sug- gest that we should also be able to build accurate parsers that instead operate incrementally. Incrementality in NLP has often been equated with left-to-right processing. For example, incre- mental transition-based parsers receive their input S VP 3 January Monday PP on NP proposal the approved NP Council The S VP goods luxury for taxes PP on NP proposal the approved NP Council The Figure 1: A case of ambiguity where speculatively committing to an attachment decision can lead an in- cremental parsing system into a dead end. one word at a time, and — after each word — out- put any number of actions such as shift or reduce, where the full sequence of actions represents a syn- tactic analysis of the input. However, in this paper we are interested in a stronger notion of incremen- tality, which we refer to as non-speculative incre- mentality. We say that a representation is specula- tive when a symbol in the representation encodes a commitment to a certain syntactic decision, but the evidence for that decision is not present in the corresponding prefix of the input. Transition-based systems are frequently speculative; …

Content truncated to 500 words