L ocation A ttention for E xtrapolation to L onger S equences (2020)

Abstract: Neural networks are surprisingly good at interpolating and perform remarkably well when the training set examples resemble those in the test set. However, they are often unable to extrapolate patterns beyond the seen data, even when the abstractions required for such patterns are simple. In this paper, we first review the notion of extrapolation, why it is important and how one could hope to tackle it. We then focus on a specific type of extrapolation which is especially useful for natural language processing: generalization to sequences that are longer than the training ones. We hypothesize that models with a separate content- and location-based attention are more likely to extrapolate than those with common attention mechanisms. We empirically support our claim for recurrent seq2seq models with our proposed attention on variants of the Lookup Table task. This sheds light on some striking failures of neural models for sequences and on possible methods to approaching such issues.

## introduction it is indisputable that, in recent years, neural network research has made stunning progress on a wide variety of tasks that require to process sequential inputs, such as machine translation @xcite and speech recognition @xcite . however, many researchers have questioned the forms of generalization that neural networks exhibit, which significantly diverges from human-like generalization @xcite . this discrepancy with human-like generalization is particularly true when it comes to extrapolating "outside" the training space @xcite . as neural networks are powerful memorizers @xcite and easily learn superficial * shared senior authorship statistical cues @xcite , testing extrapolation and generalization to samples from the long tails of a distribution might be the only way of quantifying their capacity of abstract reasoning @xcite . despite this benefit, little work has been done in extrapolation. a possible explanation is that the probability of encountering a test example in the extrapolation setting seems low when the training set d is large. 1 however, such an argument fails to consider the high cost of error in extrapolation settings, and this can be a barrier for real-world scenarios (e.g., self-driving cars). in this paper, we focus on extrapolation in sequences. more precisely, how to generalize sequence-to-sequence predictors to inputs of length n * > n d , where n d denotes the length of the longest sequence in the training set. such extrapolation is crucial for language acquisition, where humans have limited learning resources to account for the unbounded nature of language. to successfully generalize, a language learner needs to process new and potentially longer sentences than previously encountered ones @xcite . accounting for this unbounded nature of language is challenging for neural networks. this issue has recently been uncovered for seq2seq models by looking at simple artificial tasks (lake and @xcite @xcite . @xcite find that seq2seq architectures can converge to local minima that generalize, but rarely do. this suggests that neural networks could generalize but lack inductive biases that favor extrapolatable behavior. in the following sections, we review the concepts of attention and extrapolation. we then argue that current attention mechanisms, which are mainly responsible for recent successes in natural language processing (nlp), are unlikely to extrapolate as they depend on the content of trained embeddings. this leads us to introduce a novel location-based attention that is loosely inspired by human visual attention. to avoid gaining extrapolation capabilities at the cost of expressivity, we introduce an attention mixer that combines content-and position-based attentions. finally, we show that recurrent models equipped with this new attention mechanism can extrapolate to longer sequences. ## extrapolation extrapolation is often used but rarely formally defined. @xcite have found that when extrapolation is explicitly defined, it often refers to points outside a hull delimited by the training set. e.g., rectangular hull, concave hull, or convex hull. in this work we use the rectangle hull definition @xcite , as any model which is extrapolatable for this region would also be extrapolatable for the convex and concave definition. given any finite training dataset d := {x (n) } n @xmath0, we define the interpolation domain to be the d-dimensional interval i inter : the rest of the paper discusses how to constrain representations used by our neural models foot_2 to be in i inter regardless of the source sentence length, without decreasing their expressivity. ## desiderata first and foremost, we would like a model that can extrapolate to sequences longer than the longest training one n d (extrapolation constraint). as previously discussed, models with inputs or temporary representations in i extra will very likely break. to satisfy the extrapolation constraint, neural models should thus not depend on features that take values in i extra for sequences longer than n d . second, our model should be able to learn very complex positional attention patterns (positional patterns constraint). finally, although the position of words in a sentence is important, many tasks depend on their semantics. the model should thus still be able to learn content-based attention patterns (content patterns constraint). in the following section, we review previously proposed attention-mechanism and discuss why they do not fulfill the three aforementioned desired properties. ## attention mechanisms an attention mechanism (or attender) takes as input a matrix of keys k := {k t s } ns @xmath1, and outputs a probability mass function α α α @xmath2:= {v t s } ns @xmath3. following @xcite , it is useful to think of the attender as a memory access module, α α α t as the soft address and g t as the accessed vector. figure 2 illustrates attention in a recurrent seq2seq @xcite , which we will use for our experiments. both the keys and the values correspond to the set of encoder hidden states @xmath4:= {e t s } ns @xmath5, while the query corresponds to the current decoder hidden state q @xmath6. figure 2 : attender in a recurrent seq2seq. ## model in this section, we propose a location attender that can satisfy the extrapolation and positional patterns constraint. we then discuss how to incorporate content attention to satisfy the content patterns constraint. ## discussion in this paper, we focused on one type of extrapolation, which is especially important in nlp: generalization to longer sequences. we propose a new location-based attention, and show that it can extrapolate better than previous models while learning various attention patterns. despite promising initial results, our model is still unable to extrapolate perfectly for harder tasks. by analyzing its behavior, we uncovered an interesting heuristic used by seq2seq models, namely that they keep track of a decoding "counter" to know when to output @xmath7. this is a bottleneck for extrapolation, suggesting that removing this heuristic is key to reaching perfect extrapolation and should be investigated in future work. once @xmath8, we could test the model on real-world datasets. it would also be interesting to test such attention mechanisms in self-attentive seq2seq models without recurrence. finally, as the location attender is not model dependent, it could be pretrained on complex location patterns and incorporated as a plug-and-play module to get extrapolatable position attention. taking a step back, we have shown that current deep learning models with common attention mechanisms are unable to extrapolate well on seemingly straightforward tasks. this tends to be overlooked by the field due to standard benchmarks that can be solved using only interpolation. we hope that this paper acts as a reminder that extrapolation is a hard setting that has not been much investigated by the machine learning community. as current methods that memorize and learn superficial cues are unable to extrapolate while humans are, we believe that such a setting might help (and force) the field to come up with more human-like computational models that are capable of abstract reasoning.