Extrapolation in NLP

Abstract: We argue that extrapolation to examples outside the training space will often be easier for models that capture global structures, rather than just maximise their local fit to the training data. We show that this is true for two popular models: the Decomposable Attention Model and word2vec.

In a controversial essay, BIBREF0 draws the distinction between two types of generalisation: interpolation and extrapolation; with the former being predictions made between the training data points, and the latter being generalisation outside this space. He goes on to claim that deep learning is only effective at interpolation, but that human like learning and behaviour requires extrapolation.
On Twitter, Thomas Diettrich rebutted this claim with the response that no methods extrapolate; that what appears to be extrapolation from X to Y is interpolation in a representation that makes X and Y look the same. 
It is certainly true that extrapolation is hard, but there appear to be clear real-world examples. For example, in 1705, using Newton's then new inverse square law of gravity, Halley predicted the return of a comet 75 years in the future. This prediction was not only possible for a new celestial object for which only a limited amount of data was available, but was also effective on an orbital period twice as long as any of those known to Newton. Pre-Newtonian models required a set of parameters (deferents, epicycles, equants, etc.) for each body and so would struggle to generalise from known objects to new ones. Newton's theory of gravity, in contrast, not only described celestial orbits but also predicted the motion of bodies thrown or dropped on Earth.
In fact, most scientists would regard this sort of extrapolation to new phenomena as a vital test of any theory's legitimacy. Thus, the question of what is required for extrapolation is reasonably important for the development of NLP and deep learning.
 BIBREF0 proposes an experiment, consisting of learning the identity function for binary numbers, where the training set contains only the even integers but at test time the model is required to generalise to odd numbers. A standard multilayer perceptron (MLP) applied to this data fails to learn anything about the least significant bit in input and output, as it is constant throughout the training set, and therefore fails to generalise to the test set. Many readers of the article ridiculed the task and questioned its relevance. Here, we will argue that it is surprisingly easy to solve Marcus' even-odd task and that the problem it illustrates is actually endemic throughout machine learning.
 BIBREF0 links his experiment to the systematic ways in which the meaning and use of a word in one context is related to its meaning and use in another BIBREF1 , BIBREF2 . These regularities allow us to extrapolate from sometimes even a single use of a word to understand all of its other uses.
In fact, we can often use a symbol effectively with no prior data. For example, a language user that has never have encountered the symbol Socrates before may nonetheless be able to leverage their syntactic, semantic and inferential skills to conclude that Socrates is mortal contradicts Socrates is not mortal.
Marcus' experiment essentially requires extrapolating what has been learned about one set of symbols to a new symbol in a systematic way. However, this transfer is not facilitated by the techniques usually associated with improving generalisation, such as L2-regularisation BIBREF3 , drop-out BIBREF4 or preferring flatter optima BIBREF5 .
In the next section, we present four ways to solve this problem and discuss the role of global symmetry in effective extrapolation to the unseen digit. Following that we present practical examples of global structure in the representation of sentences and words. Global, in these examples, means a model form that introduces dependencies between distant regions of the input space.
The problem is described concretely by BIBREF6 , with inputs and outputs both consisting of five units representing the binary digits of the integers zero to thirty one. The training data consists of the binary digits of the even numbers INLINEFORM0 and the test set consists of the odd numbers INLINEFORM1 . The task is to learn the identity function from the training data in a way that generalises to the test set.
The first model (slp) we consider is a simple linear single layer perceptron from input to output.
In the second model (flip), we employ a change of representation. Although the inputs and outputs are given and fixed in terms of the binary digits 1 and 0, we will treat these as symbols and exploit the freedom to encode these into numeric values in the most effective way for the task. Specifically, we will represent the digit 1 with the number 0 and the digit 0 with the number 1. Again, the network will be a linear single layer perceptron without biases.
Returning to the original common-sense representation, 1 INLINEFORM0 1 and 0 INLINEFORM1 0, the third model (ortho) attempts to improve generalisation by imposing a global condition on the matrix of weights in the linear weights. In particular, we require that the matrix is orthogonal, and apply the absolute value function at the output to ensure the outputs are not negative.
For the fourth model (conv), we use a linear Convolutional Neural Network (ConvNet, BIBREF7 ) with a filter of width five. In other words, the network weights define a single linear function that is shifted across the inputs for each output position.
Finally, in our fifth model (proj) we employ another change of representation, this time a dimensionality reduction technique. Specifically, we project the 5-dimensional binary digits INLINEFORM0 onto an INLINEFORM1 dimensional vector INLINEFORM2 and carry out the learning using an INLINEFORM3 -to- INLINEFORM4 layer in this smaller space. DISPLAYFORM0 
where the entries of the matrix INLINEFORM0 are INLINEFORM1 . In each case, our loss and test evaluation is based on squared error between target and predicted outputs.
The Stanford Natural Language Inference (SNLI, BIBREF10 ) dataset attempts to provide training and evaluation data for the task of categorising the logical relationship between a pair of sentences. Systems must identify whether each hypothesis stands in a relation of entailment, contradiction or neutral to its corresponding premise. A number of neural net architectures have been proposed that effectively learn to make test set predictions based purely on patterns learned from the training data, without additional knowledge of the real world or of the logical structure of the task.
Here, we evaluate the Decomposable Attention Model (DAM, BIBREF11 ) in terms of its ability to extrapolate to novel instances, consisting of contradictions from the original test set which have been reversed. For a human that understands the task, such generalisation is obvious: knowing that A contradicts B is equivalent to knowing that B contradicts A. However, it is not at all clear that a model will learn this symmetry from the SNLI data, without it being imposed on the model in some way. Consequently we also evaluate a modification, S-DAM, where this constraint is enforced by design.
Word embeddings, such as GloVe BIBREF12 and word2vec BIBREF13 , have been enormously effective as input representations for downstream tasks such as question answering or natural language inference. One well known application is the INLINEFORM0 example, which represents an impressive extrapolation from word co-occurrence statistics to linguistic analogies BIBREF14 . To some extent, we can see this prediction as exploiting a global structure in which the differences between analogical pairs, such as INLINEFORM1 , INLINEFORM2 and INLINEFORM3 , are approximately equal.
Here, we consider how this global structure in the learned embeddings is related to a linearity in the training objective. In particular, linear functions have the property that INLINEFORM0 , imposing a systematic relation between the predictions we make for INLINEFORM1 , INLINEFORM2 and INLINEFORM3 . In fact, we could think of this as a form of translational symmetry where adding INLINEFORM4 to the input has the same effect on the output throughout the space.
We hypothesise that breaking this linearity, and allowing a more local fit to the training data will undermine the global structure that the analogy predictions exploit.
Language is a very complex phenomenon, and many of its quirks and idioms need to be treated as local phenomena. However, we have also shown here examples in the representation of words and sentences where global structure supports extrapolation outside the training data.
One tool for thinking about this dichotomy is the equivalent kernel BIBREF15 , which measures the extent to which a given prediction is influenced by nearby training examples. Typically, models with highly local equivalent kernels - e.g. splines, sigmoids and random forests - are preferred over non-local models - e.g. polynomials - in the context of general curve fitting BIBREF16 .
However, these latter functions are also typically those used to express fundamental scientific laws - e.g. INLINEFORM0 , INLINEFORM1 - which frequently support extrapolation outside the original data from which they were derived. Local models, by their very nature, are less suited to making predictions outside the training manifold, as the influence of those training instances attenuates quickly.
We suggest that NLP will benefit from incorporating more global structure into its models. Existing background knowledge is one possible source for such additional structure BIBREF17 , BIBREF18 . But it will also be necessary to uncover novel global relations, following the example of the other natural sciences.
We have used the development of the scientific understanding of planetary motion as a repeated example of the possibility of uncovering global structures that support extrapolation, throughout our discussion. Kepler and Newton found laws that went beyond simply maximising the fit to the known set of planetary bodies to describe regularities that held for every body, terrestrial and heavenly.
In our SNLI example, we showed that simply maximising the fit on the development and test sets does not yield a model that extrapolates to reversed contradictions. In the case of word2vec, we showed that performance on the analogy task was related to the linearity in the objective function.
More generally, we want to draw attention to the need for models in NLP that make meaningful predictions outside the space of the training data, and to argue that such extrapolation requires distinct modelling techniques from interpolation within the training space. Specifically, whereas the latter can often effectively rely on local smoothing between training instances, the former may require models that exploit global structures of the language phenomena.
The authors are immensely grateful to Ivan Sanchez Carmona for many fruitful disagreements. This work has been supported by the European Union H2020 project SUMMA (grant No. 688139), and by an Allen Distinguished Investigator Award.

Figure and table captions:
Figure 1: Generalising to unseen data: dotted line = training manifold; black arrows = interpolation; grey arrows = extrapolation. Both directions are represented globally in the training data, but local interpolation is only effective in one of them at each point.
Table 1: Mean Squared Error on the Train (even numbers) and Test (odd numbers) Sets.
Table 2: Accuracy on all instances, contradictions and reversed contradictions from the SNLI test set.
Table 3: Accuracy on the analogy task.

Questions about this paper:
What dimensions do the considered embeddings have?

Answers:
100, 200, 400