Incremental Processing in the Age of Non-Incremental Encoders: An Empirical Assessment of Bidirectional Models for Incremental NLU (2020)

Abstract: While humans process language incrementally, the best language encoders currently used in NLP do not. Both bidirectional LSTMs and Transformers assume that the sequence that is to be encoded is available in full, to be processed either forwards and backwards (BiLSTMs) or as a whole (Transformers). We investigate how they behave under incremental interfaces, when partial output must be provided based on partial input seen up to a certain time step, which may happen in interactive systems. We test five models on various NLU datasets and compare their performance using three incremental evaluation metrics. The results support the possibility of using bidirectional encoders in incremental mode while retaining most of their non-incremental quality. The “omni-directional” BERT model, which achieves better non-incremental performance, is impacted more by the incremental access. This can be alleviated by adapting the training regime (truncated training), or the testing procedure, by delaying the output until some right context is available or by incorporating hypothetical right contexts generated by a language model like GPT-2.

## introduction in "the story of your life", a science fiction short story by ted @xcite , earth is visited by alien creatures whose writing system does not unfold in time but rather presents full thoughts instantaneously. in our world, however, language does unfold over time, both in speaking and in writing. there is ample evidence @xcite , inter alia) that it is also processed over time by humans, in an incremental fashion where the interpretation of a full utterance is continuously built up while the utterance is being perceived. in computational linguistics and natural language processing, this property is typically abstracted away by assuming that the unit to be processed (e.g., a sentence) is available as a whole. 1 the return and subsequent mainstreaming of recurrent neural networks (rnns), originally introduced by @xcite and repopularized i.a. by @xcite , may have made it seem that time had found a place as a first-class citizen in nlp. however, it was quickly discovered that certain technical issues of this type of model could be overcome, for example in the application of machine translation, by encoding input sequences in reverse temporal order @xcite . this turns out to be a special case of the more general strategy of bidirectional processing, proposed earlier in the form of birnns @xcite and bil-stms @xcite , which combine a forward and a backward pass over a sequence. more recently, transformers @xcite also function with representations that inherently have no notion of linear order. atemporal processing has thus become the standard again. in this paper, we explore whether we can adapt such bidirectional models to work in incremental processing mode and what the performance cost is of doing so. we first go back and reproduce the work of @xcite , who compare the performance of lstms and bilstms in sequence tagging, extending it with a bert-based encoder and with a collection of different datasets for tagging and classification tasks. then we address the following questions: q1. if we employ inherently non-incremental models in an incremental system, do we get functional representations that are adequate to build correct and stable output along the way? we examine how bidirectional encoders behave under an incremental interface, revisiting the approach proposed by @xcite for pos taggers. after standard training, we modify the testing procedure by allowing the system to see only successively extended prefixes of the input available so far with which they must produce successively extended prefixes of the output, as shown in figure 1 . the evaluation metrics are described in section 3, and the discussion is anchored on the concepts of timeliness, monotonicity, and decisiveness and their trade-off with respect to the non-incremental quality @xcite . we show that it is possible to use them as components of an incremental system (e.g. for nlu) with some trade-offs. q2. how can we adapt the training regime or the real-time procedure to mitigate the negative effect that the non-availability of right context (i.e., future parts of the signal) has on nonincremental models? to tackle this question, we implement three strategies that help improve the models' incremental quality: truncated training, delayed output and prophecies (see section 4). our results are relevant for incremental natural language understanding, needed for the design of dialogue systems and more generally interactive systems, e.g. those following the incremental processing model proposed by @xcite . these systems rely on the availability of partial results, on which fast decisions can be based. similarly, simultaneous translation is an area where decisions need to be based on partial input with incomplete syntactical and semantic information. ## evaluation of incremental processors the hierarchical nature of language makes it likely that incremental processing leads to non-monotonic output due to re-analysis, as in the well-known "garden path" sentences. incremental systems may edit the output by adding, revoking, and substituting its parts @xcite . we expect an incremental system to produce accurate output as soon as possible @xcite , with a minimum amount of revocations and substitutions, ideally only having correct additions, to avoid jittering that may be detrimental to subsequent processors working on partial outputs. to assess the incremental behavior of sequence tagging and classification models, we use the evaluation metrics for incremental processors established by @xcite and @xcite . the latter defines three diachronic metrics: edit overhead (@xmath0, 1]), the proportion of unnecessary edits (the closer to 0, the fewer edits were made); correction time (@xmath1, 1]), the fraction of the utterance seen before the system commits on a final decision for a piece of the output (the closer to 0, the sooner final decisions were made); and relative correctness (@xmath2, 1]), the proportion of outputs that are correct with respect to the non-incremental output (being close to 1 means the system outputs were most of the time correct prefixes of the non-incremental output). the sequence tagging tasks we evaluate are massively incremental @xcite , meaning that a new label is always added to the output after a new word is processed. the models can also substitute any previous labels in the output sequence in the light of new input. sequence classifiers must add one label (the sequence's class) after seeing the first word and can only substitute that single label after each new word. in both cases, additions are obligatory and substitutions should ideally be kept as low as possible, but there can be no revocations. moreover, our data is sequential, discrete, and order-preserving @xcite . given a sequence of length n, the number of necessary edits is always the number of tokens in the sequence (all additions) for sequence taggers and we set it to 1 for sequence classifiers. all other edits (substitutions) count as unnecessary and their number is bounded by n-1 @xmath3, and by (n -1), for classification. we need to slightly adapt the ct measure for sequences. it is originally defined as fd-f0, the time step of a final decision minus the time step when the output first appeared. f0 is fixed for every word in a sequence (the systems always output a new label corresponding to each new word it sees), but each label will have a different fd. in order not to penalize initial labels, which have more opportunities of being substituted than final ones, we instead sum the fd of each token and divide by the sum of the number of times each one could be modified, to get a score for the sequence as a whole. let the sequence length be n, then here @xmath4. we define it to be 0 for sequences of one token. again, 0 means every label is immediately committed, 1 means all final decisions are delayed until the last time step. figure 2 presents a concrete example of how to estimate the metrics. based on the trade-off between responsiveness and output quality @xcite , we also estimate whether there is any improvement in the quality of the outputs if the encoder waits for some right context to appear before committing on output previously generated. for that, we use delayed eo and delayed rc (also named discounted in @xcite , which allows one or two words of the right context to be observed before outputting previous labels, named eo/rc∆1 and eo/rc∆2, respectively. in order to concentrate on the incremental quality despite the eventual non-incremental deficiencies, we follow the approach by @xcite and evaluate intermediate outputs in comparison to the processor's final output, which may differ from the gold output but is the same as the nonincremental output. the general non-incremental correctness should be guaranteed by having high accuracy or f1 score in the non-incremental performance. ## models we test the behavior of five neural networks, illustrated in figure 3 , under an incremental processing interface operating on word level and having full sentences as processing units: a) a vanilla lstm; b) a vanilla bilstm; c) an lstm with a crf (conditional random field) layer; d) a bilstm with a crf layer; and e) bert. the vanilla lstm is the only model that works solely in temporal direction. we choose to use the basic forms of each model to isolate the effect of bidirectionality. they perform well enough on the tasks to enable a realistic evaluation (see sequence tagging implies a one-to-one mapping from words to labels, so that for every new word the system receives, it outputs a sequence with one extra label. in sequence classification, we map every input to a single label. in that case, the lstm can also edit the output since it can change the chosen label as it processes more information. because the datasets we use are tokenized and each token has a corresponding label, we follow the instructions given by @xcite for dealing with bert's subtokenization: the scores of the first subtoken are used to predict its label, and further subtoken scores are ignored. except for the lstm on sequence tagging, all models' outputs are non-monotonic, i.e., they may reassign labels from previous words. the concept of timeliness is trivial here because we know exactly that the label for the t-th word will appear for the first time at the t-th version of the output, for all t. even so, we can delay the output to allow some lookahead. in terms of decisiveness, all models commit to a single output at every time step. figure 4 shows an example of the computation graph. bilstms can recompute only the backward pass, while bert needs a complete recomputation. ## discussion and conclusion we show that bidirectional encoders can be adapted to work under an incremental interface without a too drastic impact on their performance. even though the training (being done on complete sequences) differs from the testing situation (which exposes the model to partial input), the incremental metrics of most models are, in general, good: in sequence tagging, edit overhead is low, final decisions are taken early, and often partial outputs are a correct prefix of the complete non-incremental output. sequence classification is more unstable because, at initial steps, there is a higher level of uncertainty on what is coming next. our experiments show that the deficiencies of bert in the incremental metrics can be mitigated with some adaptations (truncated training or prophecies together with delay), which make its incremental quality become as good as those of other models. since the semantic information is only kept encoded for a few steps in rnns @xcite , this may be a reason why delay causes incremental metrics to be much better. if long-range dependencies are not captured, only neighboring words exert more influence in the choice of a label, so after seeing two words in the right context, the system rarely revises labels further back. bert, having access to the whole sentence at any time step, is less stable because new input can cause it to reassess past labels more easily. besides, we also found evidence of different behavior of the instability of partial outputs between correct and incorrect output sequences, which could potentially be a signal of later lower quality. this could be used, for example, in dialog systems: if edit overhead gets too high, a clarification request should be made. a follow-up idea is training a classifier that predicts more precisely how likely it is that the final labels will be accurate based on the development of eo. however, our initial experiments on building such classifier were not successful. we suppose this is due to the fact that, in our datasets, incorrect final output sequences still usually have more than 90% correct labels, so the learnable signal may be too weak. the use of gpt-2 prophecies led to promising improvements for bert in sequence tagging. we see room for improvement, e.g. resorting to domain adaptation to make prophecies be more related to each genre. a natural extension is training a language model that generates the prophecies together with the encoder.