Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6255–6261 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 6255 Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference Nikita Kitaev and Dan Klein Computer Science Division University of California, Berkeley {kitaev, klein}@cs.berkeley.edu Abstract We present a constituency parsing algorithm that, like a supertagger, works by assigning labels to each word in a sentence. In order to maximally leverage current neural architec- tures, the model scores each word’s tags in par- allel, with minimal task-specific structure. Af- ter scoring, a left-to-right reconciliation phase extracts a tree in (empirically) linear time. Our parser achieves 95.4 F1 on the WSJ test set while also achieving substantial speedups com- pared to current state-of-the-art parsers with comparable accuracies. 1 Introduction Recent progress in NLP, and practical machine learning applications more generally, has been driven in large part by increasing availability of compute. These advances are made possible by an ecosystem of specialized hardware accelerators such as GPUs and TPUs, highly tuned kernels for executing particular operations, and the abil- ity to amortize computational costs across tasks through approaches such as pre-training and multi- task learning. This places particular demands for a model to be efficient: it must parallelize, it must maximally use standard subcomponents that have been heavily optimized, but at the same time it must adequately incorporate task-specific insights and inductive biases. Against this backdrop, constituency parsing stands as a task where custom architectures are prevalent and parallel execution is limited. State- of-the-art approaches use custom architecture com- ponents, such as the tree-structured networks of RNNG (Dyer et al., 2016) or the per-span MLPs in chart parsers (Stern et al., 2017; Kitaev et al., 2019). Approaches to inference range from autoregressive generation, to cubic-time CKY, to A* search – none of which are readily parallelizable. Our goal is to demonstrate a parsing algorithm that makes effec- tive use of the latest hardware. The desiderata for our approach are (a) to maximize parallelism, (b) to minimize task-specific architecture design, and (c) to lose as little accuracy as possible com- pared to a state-of-the-art highly-specialized model. To do this, we propose an algorithm that reduces parsing to tagging, where all tags are predicted in parallel using a standard model architecture such as BERT (Devlin et al., 2019). Tagging is followed by a minimal inference procedure that is fast enough to schedule on the CPU because it runs in linear time with low constant factors (subject to mild as- sumptions). 2 Related Work Label-based parsing A variety of approaches have been proposed to mostly or entirely reduce parsing to a sequence labeling task. One family of these approaches is supertagging (Bangalore and Joshi, 1999), which is particularly common for CCG parsing. CCG imposes constraints on which supertags may form a valid derivation, necessitat- ing complex search procedures for finding a high- scoring sequence of supertags that is self-consistent. An example of how such a search procedure can be implemented is the system of Lee …

Content truncated to 500 words