Learned Incremental Representations for Parsing (2022)

Abstract: We present an incremental syntactic representation that consists of assigning a single discrete label to each word in a sentence, where the label is predicted using strictly incremental processing of a prefix of the sentence, and the sequence of labels for a sentence fully determines a parse tree. Our goal is to induce a syntactic representation that commits to syntactic 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 parsing models when using the same pre-trained embeddings. We also provide an analysis of the representations learned by our system, investigating properties such as the interpretable syntactic features captured by the system and mechanisms for deferred resolution of syntactic ambiguities.

## introduction language comprehension in humans is, to a nontrivial extent, an incremental process. human speech is heard word by word, and, while the precise 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 precisely in this manner: they require a full sentence as input, and perform deeply bidirectional processing to produce their outputs. human capabilities suggest 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, incremental transition-based parsers receive their input one word at a time, and -after each word -output any number of actions such as shift or reduce, where the full sequence of actions represents a syntactic analysis of the input. however, in this paper we are interested in a stronger notion of incrementality, which we refer to as non-speculative incrementality. we say that a representation is speculative 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; we give an example sentence in figure 1 , where a decision must be made regarding whether the preposition "on" attaches to noun "proposal" or the verb "approved." transition-based approaches such as shift-reduce or attach-juxtapose @xcite place the action that determines the preposition attachment earlier in the left-to-right processing pattern than the disambiguating word ("monday" or "taxes") that reveals the correct analysis. similarly in ccg parsing, the representation of a ccg analysis in the form of a sequence of supertags is likewise speculative -including for this same example, where the correct supertag for each word cannot be predicted based on only that word and its preceding context. the speculative nature of incremental transition systems or ccg supertags makes it impractical to recover an accurate parse by simply committing to the highest-scoring option at each each point where a decision must be made. an incremental parser in the speculative paradigms must instead consider multiple analyses in parallel, and later throw out analyses that are inconsistent with the sentence; this can be done through a procedure like beam search. in other words, the true representation of syntactic information at each point in the sentence is not a single sequence of actions (or supertags), but rather a belief state (beam state) that contains multiple candidate analyses. in the limit of infinite beam size, the parser ceases to be incremental: its belief state can contain all reasonable analyses, deferring all choices to the very end of a sentence. our goal in this work is to design a representation for parsing that is maximally speculation free. in other words, it should record commitments to syntactic choices only as they are incrementally revealed by the input. we additionally want our representation to relate to constituency trees in a similar way to how transition-based actions relate to them: that is, through a deterministic transformation function. a sequence of shift-reduce or attach-juxtapose actions is not identical to a parse tree, but it can be mapped to a tree using a deterministic automaton that interprets the discrete actions as operations on a tree fragment or stack of tree fragments. a sequence of supertags is likewise not the same as a tree, and mapping it to a tree requires further processing in the form of finding and applying an appropriate series of combinators. these mappings are non-trivial, especially in the case of ccg, so we should not expect our mapping to be trivial either -our only requirement is that it be deterministic and operate entirely from our representation, having already discarded the raw text in the sentence. finally, we would like our representation to take the familiar form of a sequence of discrete symbols. we propose to arrive at such a representation through end-to-end learning, rather than manual construction. the model can then make its own decisions about when syntactic decisions take place, how to handle cases of ambiguity, and how to represent belief states within the learned system itself. this system will learn to encode linguistic and structural features to allow effective incremental parsing. our end-to-end approach is a model that proceeds in two stages. the first stage maps from individual words to syntactic decisions, which are represented as discrete tokens drawn from a small, bounded vocabulary. the second component of our system is a read-out network that takes a sequence of discrete tags as input and produces a conventional parse tree as output. both stages are trained jointly in an end-to-end manner. crucially, we do not a priori assign meaning to the discrete tokens (e.g. actions like shift, or supertags like in ccg); we only specify the total number of symbols available to the model to control the complexity of the representation. unlike a speculative system, our representation can be used by finding the single highest-scoring tag at each position in a sentence, and then converting the resulting sequence of tags into a tree. important properties that we evaluate for our proposed approach are its quality (as measured by f1 score on the penn treebank), as well as compactness (how many bits per word are required to encode syntactic information). at 5 bits per word, a parser using our representations achieves 93.72 f1, and at 8 bits per word it achieves 94.97 f1 -comparable to the method of @xcite trained with the same pre-trained embeddings. we further provide an analysis of the symbols learned by our model, including explorations of the linguistic features captured by the symbol set, the information content of our incremental representation for prefixes of a full utterance, and the system's ability to defer resolution of attachment ambiguities. our models and code are publicly available. foot_0 this work is inspired by the concept of incremental parsing implemented in works such as @xcite and @xcite . with regards to neural parsers, recent strides in incremental parsing include the attach-juxtapose parsers from @xcite . however, these neural models often have incremental tree construction mechanisms, but are not incremental from the raw input level due to reliance on pretrained bidirectional models such as the works of @xcite and @xcite . the placement of an information bottleneck on token representations has also been studied in the bidirectional case by @xcite , who reported many similar findings about the syntactic features learned by discrete tags. however, our model differs in that it explores the incremental, non-speculative case, as well as in the implementation of the parsing model and its constraints on representation size. our incremental parsing system can be compared to manually formulated representations such as shift-reduce or ccg supertagging. however, for purely incremental parsing, limitations of shiftreduce and ccg supertagging may necessitate the use of beam search to produce more accurate, viable parse trees, as in the works of @xcite and @xcite . other works have also analyzed the discrete features useful for syntactic parsing. some researchers augmented parsing models by adding discrete, hand-coded indicator features based on the raw sentence as in @xcite . similar hand-coded, discrete features have been shown to improve other tasks such as nmt @xcite . previous experiments by @xcite have analyzed whether neural parsers based on bidirectional lstms capture other handmade indicator functions from earlier hypotheses by @xcite . by contrast, our model seeks to directly learn new features, and in fact, many of the hand-made indicators from previous works arise naturally in the learned symbols of our model. there also exists work examining the learned grammatical rules of a stack-based recurrent neural network via analysis of an attention mechanism @xcite . by contrast, our analysis has a lesser focus on the attention distribution between tokens, and a greater focus on the features and syntactic decisions captured by each individual symbol. ## approach our model is based on a parsing architecture that contains an encoder layer that uses a pretrained network and a chart-based decoder, as detailed in @xcite . to ensure incrementality, the encoder for this incremental model uses gpt-2 as a base, which disallows a backwards flow of information from future tokens @xcite . at the interface between the pre-trained encoder and subsequent parts of the model (which we refer to as the read-out network), we introduce a discretization step that collapses the continuous, highdimensional vectors from the encoder network to a small inventory of discrete symbols. the read-out network has access only to these discrete symbols and not to the original text of the input; in other words, the sequence of discrete symbols must encode all information necessary to represent the syntactic structure of the sentence. we introduce an information bottleneck that limits the size of the discrete token vocabulary to as few as 32 distinct symbols per raw input token. the decision to label each token with a single symbol is partially rooted in prior research providing evidence that syntactic decisions among human speakers adhere to the uniform information density hypothesis, thus each token may convey similar amounts of syntactic information @xcite . concretely, a learned projection matrix is first applied to the token-level representation vectors of gpt-2. each projected vector is then converted into a single discrete symbol via vector quantization @xcite . the number of symbols is kept small; as such, only a few bits are needed to encode all symbols. in comparison, the base architecture uses a 512-dimensional vector of 32bit floating point numbers for each token. we can obtain high parsing accuracy sending 5 bits per token, which is only 0.03% of the bits of the base architecture's token representations. at around 8 bits per token, parsing performance approximately matches that of the base architecture. after discretization, each symbol from the sequence is associated with a learned embedding, as specified in the vector quantization codebook. these vectors are fed as an input to the bidirectional read-out network, which consists of transformer layers and an mlp-based span classification layer that otherwise match the base architecture. the output of the network is a chart of scores representing each possible constituent span of the sentence. a tree is then efficiently generated through the cky algorithm following the span scoring methods of @xcite . it should be noted that while the encoder is unidirectional, our read-out network is bidirectional. the bidirectionality allows the network enough slack to learn a flexible mapping between the induced representation and standard constituency trees. for example, the discrete symbol associated with a word may help determine a syntactic attachment that concerns previous words that have already been assigned their own symbols. in practice, the behavior of the read-out network exhibits consistent patterns that we interpret in section 5. moreover, the main product of our method -and the principle object of analysis in this paper -is not the network itself but rather the sequence of discrete symbols, each of which encodes no knowledge of future context. we train our models using a learning rate of 3e-5 for weights carried over from pre-training, a learning rate of 1e-4 for randomly initialized weights, and a batch size of 32. in order to facilitate training, the first two epochs of training proceed without the use of vector quantization. during this time, a streaming k-means algorithm @xcite calculates the initial centroids to use for vector quantization. over the course of the third epoch, the model linearly interpolates between continuous and quantized representations, and uses only the quantized version from the fourth epoch until the end of training. we found that cold-starting with randomly-initialized centroids performs worse, in the sense that some centroids would never be used or updated at any point during training. we attribute this degradation to the fact that randomly sampled code vectors are a poor distributional fit for outputs arising from a pre-trained gpt-2 model. ## results we apply our approach to the labeled constituent trees of the english penn treebank @xcite . the final incremental model generated using this setup achieves a score of 94.97 f1 on the penn treebank wsj test set. this model uses only 8 bits per token (256 symbols) to define the discrete symbol set using a unidirectional pretrained model (gpt2-medium). a comparable model @xcite that combines the same pre-trained encoder with deep bidirectional processing achieves 95.10 f1. this shows that our representation can induce parse trees with competitive accuracy. in in the case of the attach-juxtapose parser, the same can be achieved via the use of beam search. nevertheless, incrementally predicting either of these representations fails to leverage the full power of the pre-trained encoder. the choice of gpt-2 rather than a stronger bidirectional model has a large effect on the performance on the penn treebank. to give a more accurate comparison with other models, even higher scores are achievable by using stronger pre-trained models, different forms of bidirectional processing, and additional supervision in the form of dependency trees; mrini et al. (2020) combine all of these elements to achieve 96.38 f1. however, many of these techniques are either orthogonal to our work, or they cannot be borrowed into an incremental setting due to their focus on deeply bidirectional neural processing. we further evaluate our approach in terms of the compactness of the produced representations. to do this, we trained a number of models while varying the size of the symbol set. for added comparison, we also trained models using a bidirectional pretrained encoder (bert). as a baseline, we also produced a model that assigns symbols through simple k-means clustering of single-word embeddings @xcite rather than fine-tuned contextual models. the average f1 score for each model across a range of tag set sizes is shown in while our best-performing unidirectional model uses 8 bits per token, using as few as 5 bits per token (32 symbols) retains a performance of 93.72 f1 on the test set. as a point of comparison, gold ccg supertags in the ccgbank @xcite training data have an entropy of 5.14 bits per word. however, ccg decoding typically requires multiple analyses to be considered in parallel. a better comparison, then, might be the entropy of top-k supertag predictions from a supertagging model. we find that the trained model of @xcite has an entropy of 5.98 bits/word for its ranked top-2 predictions, 7.57 for top-3, and 9.03 for top-4. our method's best-performing setting of 8 bits per word is therefore at an entropy level similar to top-3 or top-4 predictions for a recent ccg supertagger. ## conclusion in this paper, we present an approach to inducing syntactic representations that associate each token in the input with a discrete symbol from an arbitrarily-sized vocabulary, where the representations can be predicted incrementally in a strictly append-only manner. our models achieve high f1 on the wsj test set despite a steep information bottleneck limiting the information that can be associated with each token. the token-level tags produced by our model encode relevant syntactic information suitable for the given bit rate, while the locations of these tags serve to concretely define the location at which syntactic decisions can be committed to in a speculation-free manner. these systems can serve to improve our understanding of incremental parsing and sequential decision making, and the underlying computational methods may be useful in the analysis of other incremental contexts.