Convolutional-Match Networks for Question Answering

1 Introduction

Methods and algorithms that emulate a general purpose computing machine at a neural level [Graves et al., 2014; 2016; Sukhbaatar et al., 2015] have recently seen strong interest. The basic premise of these methods is that an external or internal memory is formed and that this memory is searched iteratively for data relevant to a certain task. The searching mechanism is often termed "attention". This creates an artificial "bandwidth" limiter that removes the bulk of input information - letting only the most relevant information pass through for further processing.

In order to test the performance of one of these new models, Memory Networks, Facebook Research created a dataset [Weston et al., 2015] termed Basic Tasks for AI (bAbI). The dataset is based on twenty different task types that portray different question-answering scenarios. These tasks are formed in Data-Question-Answer triplets. A textual input (the data) is presented to a machine-learning algorithm, followed by a question on the data. The algorithm is then tasked with answering that question, based on the given textual data.

In this paper we devise an architecture that is meant to be both general enough to serve as a general-purpose neural network, and strong enough to attack the relevant problem of "searching through the seas of irrelevancy" adequately to (almost) solve the bAbI tasks. The main contribution of this work is the new neural architecture, termed Convolutional Match Network (CNM), which, as we demonstrate, improves the performance on the bAbI question-answering dataset compared to previous published state-of-the-art work.

The basic premise of our architecture is fairly simple; text data is processed through an embedding layer [Mikolov et al., 2013], which encodes relevant information in a wordby-word basis and transforms each word into a real-valued vector. Thus, a series of words is converted into a series of vectors. Those vectors are sequentially processed by a one-dimensional convolutional layer [LeCun et al., 1998]. The addition of this convolutional layer, alongside a different match function, is the main extension of this work over that of [Samothrakis et al., 2016]. The question asked is processed by exactly the same mechanism - weights are shared between the data and question convolutional layers. Both word-vector sequences are then passed through a maxpooling layer, which aims to subsample the textual information down to a small sequence of neuronal activations that roughly retains the original textual information. At this stage we have "compressed" our sentence and question data. Next we perform what we call a "matching" operation which aims to identify the differences between the compressed question and each compressed sentence. This matching step helps the neural network identify which bits of the source data (i.e. which bits of a "sentence") are likely to be most helpful in answering (i.e. the closest "match" to) the question. This results in a separate match vector for each sentence-question pair. Following that, we perform a non-linear transformation to each matched sentence-question pair. Next, we apply a timed softmax attention procedure that loops through each question-answer pair, resulting in a single vector containing the most relevant information. We then feed this final vector back in another recurrence, acting as a complementary question. After three such recurrent loops through the network (or "hops"), we pass the final output to a softmax layer which provides the final answer. This whole process is described in detail in Section 3.

The organisation of the paper is as follows. The next section provides all the necessary background. The new neural network architecture is presented in more detail in Section 3. In Section 4, we discuss and analyse the experiments performed with the new architecture on the bAbI tasks. The paper ends with a short discussion and conclusion in Section 5.

2 Background

Attention mechanisms have been very popular lately and a number of datasets have been proposed that should (in theory) make the qualities of algorithms that incorporate them shine [Luong et al., 2015; Xu et al., 2015b; Xiong et al., 2016]. One characteristic of attention mechanisms is that they tend to ignore large chunks of data; this is somewhat reminiscent, but significantly different, to the LASSO [Tibshirani, 1996] regulariser, which tries to ignore features by setting weight coefficients to zero. The importance of each feature is conditioned on the input, hence which features are "penalised" changes continuously from sample to sample.

In this paper, we focus on the bAbI dataset [Weston et al., 2015]. The version of bAbI used in this paper contains 20 different question answering tasks, each having 10, 000 training examples. The test set of these tasks comprises of 1, 000 examples. When working with the bAbI dataset, results may be presented for either training a different network/classifier for each task, or for training a single network to solve all tasks together. In this paper, we train one network to solve all tasks together, referred to as "joint trainng," meaning the dataset comprises 200, 000 training and 20, 000 testing instances.

A human would presumably find it hard to directly answer the questions posed by the dataset by just following the "information" pathway of different facts. Instead, one would first need to search for specific "facts", rescan the data for relevant sentences and iterate until a sentence with information that can answer the question is identified. If, however, one has identified the relevant sentences, the task is made much easier. Hence, focusing the algorithm's attention almost trivialises the problem and showcases the power of attention mechanisms. Note that in all results presented here, we do not manually tell the network which memories/sentences/facts are most relevant, but instead we rely on the network's in-built attention mechanism to figure these details out for itself.

The benchmark has previously been used to assess various architectures (e.g. [Graves et al., 2016; Sukhbaatar et al., 2015; Kumar et al., 2015; Graves et al., 2014; Peng et al., 2015; Samothrakis et al., 2016]), all using somewhat similar ideas, but with different executions and implementations. For example, [Graves et al., 2016] use three different attention mechanisms to assess the relevancy of memory content, while [Peng et al., 2015] use a simple combination of convolution and max-pooling. These implementational differences lead to widely different performance. A common theme among these efforts is their apparent instability - with even the best score achievable and the mean results presented being widely different; leading practitioners to often present the best of several runs. The amount of preprocessing required is yet another interesting point of difference, and some architectures require the input to be heavily pre-processed (e.g., as to extract features at a sentence level), whereas others (including ours, but also see [Graves et al., 2016]) perform inference at a word level. The memory mechanisms used in the vast majority of the work is internal to the network, but attention systems could also possibly be coupled with completely external memories (e.g. databases) and produce end-to-end data inquiry pathways, with some results towards this direction presented in [Yin et al., 2015].

3 Neural Architecture

This section describes the architecture of the whole network in more detail, delving into individual components. Our architecture is in effect a straightforward application of [Collobert et al., 2011], extended to include memory and attention mechanisms as discussed in [Samothrakis et al., 2016], and is presented in Figure 1.

3.1 Input Encoding

Both the question and all data-sentences are encoded initially by two concurrent processing pipelines that share the same weights. The first one involves encoding the data (received in our setting in the form of a text). An embedding layer processes the data word by word, similarly as in word2vec [Mikolov et al., 2013]. First, each word is encoded as a vector of length n neurons, and then each sentence is padded out with blank words so that all sentences are uniform length, n mns. Each sequence of sentences is also padded to the maximum data length available. The padding is done for two reasons. The first one is to create tensors of a fixed shape that are required in modern neural network frameworks. The second one is per-sentence padding, which is effectively done as a way of saying "This is where a sentence ends". Both are tricks to get away from the fact that one needs to pass 3D tensors of certain shapes. The number of sentences is n memories. All sentences and words are represented as an output matrix of dimension (n words × n neurons), where n words = n mns ∗ n memories. Dropout [Srivastava et al., 2014] is applied, resulting in a new matrix of the same dimension, but with some elements zeroed out.

The matrix is then passed into a 1-dimensional convolutional layer with the number of filters set to n filters = n neurons. Each convolutional filter is of dimension n mns×n neurons. The convolution filters are passed over the input matrix, with stride length 1. The input matrix is padded with zeros so that the result of each convolution is the same dimension as the input matrix 1 . Again, the result is a matrix of dimension (n words × n filters).

After convolution, a non-linearity is applied. As the final step of encoding, each input sentence (or memory) is compressed into a single shorter vector using max-pooling. The max-pooling operation compresses each whole sentence down to a single vector of dimension n filters. Hence the final representation of all input sentences is a matrix of dimension (n memories × n f ilters). The whole procedure until now is captured in the first four layers of the graph in Figure 1 (Embedding, Dropout, Convolution1D, MaxPooling).

A second, separate pathway involves encoding the question. Each question is processed identically to a single sentence. The question is passed through the same embedding layer, followed by the same convolutional layer, resulting in a matrix of dimension (n mns × n filters). This is followed by a non-linearity, and by max-pooling, which compresses all of the "word vectors" in the question into a single vector of length n neurons. Hence, the final encoding of the question is a single output vector of dimension n filters = n neurons. Again, this is represented in the first four layers of Figure 1.

1 This is "border mode = same" in some terminologies.

3.2 The Matching AttentionMechanism

After the encoding we apply a match function, which compares each sentence (one at a time) to the question. The purpose of the match function is to provide a vector output indicating how relevant each component of a particular preprocessed sentence st is to the given preprocessed question q. The match function we use is:

where the index i indicates the vector component. In Figure 1 this corresponds to the Match layer.

A match vector mt is thus formed for each sequence (i.e. for all t = 1 . . . n memories). Each match vector mt is processed further via a dense neural layer, and a non-linearity, using what is termed a time distributed layer (TDD - see Figure 1). A time distributed layer is a layer that applies a nonlinearity (i.e. an ordinary layer) to a sequence of data. So assuming input data of shape (n memories, n neurons), an ordinary dense layer is applied to each set of neuron activations n neurons.

The transformed input is now passed through another layer with output dimension of 2. The output vector at this layer is denoted by the two-dimensional vector yt, for sentence number t. The components of yt are then transformed by:

This recursive softmax operation produces two components of zt, which sum to 1. The aim of these components is to compare the current memory with all the previous ones and gradually build a new "focused" output. Thus, a hidden vector ht (of dimension n neurons) is updated via the following recurrent update:

initialised with h0 = 0. This recurrent loop is referred to as the AttentionRecurrent layer in Figure 1. At each timestep, the layer checks the relevance of its input, working over memories and comparing the proportion of importance each one has.

The steps "Match, TDD, AttentionRecurrent" form one "hop", i.e. one pass over memory. There are scenarios, however, where multiple passes are needed in order for the network to infer a relevant memory. In these cases, a second and third hop are performed, using the new match function:

where (hp)t is the ht vector from the previous hop. The number of hops used in this paper is set to 3, but there is virtually no limit on the number of hops. All hops share the same weights.

The final stage of processing, after all hops are completed, is the Dense Softmax Layer. This puts the final ht vector through a dense neural layer, and non-linearity, producing an output vector with dimension 195 (corresponding to the 195 possible answers in the bAbI dataset). A softmax operator is applied to this vector to turn the output into probabilities. Note that when multiple output words are requested, the current setup will output a sequence directly (e.g., "apple, football, milk") - this is required, for instance, by tasks 8 and 19.

4 Experiments

This section showcases the relevant experimental setup and obtained results.

4.1 Setup

We assess the quality of each method by: (i) determining the algorithmic accuracy, and (ii) counting the number of tasks solved. A task is solved when the error is below 5%, as defined by the benchmark [Bordes et al., 2015]. All tasks are used for both training and testing, which results in 200, 000 training instances and 20, 000 testing instances. Each network training phase lasts for 50 epochs, followed by measurements on the (out-of-core-training) test set. In call cases, categorical cross entropy is used as the loss function. Note that there is no intermediate supervision - we don't, at any point, tell the machine which memories/sentences are important and which are not. We rely on the end-to-end supervised learning process to train the attention mechanism to work this out by itself. Initial weight values were given by Gaussian Glorot initialisation [Glorot and Bengio, 2010], whereas recurrent softmax layer weights were initialised using orthogonal initialisation. All activation functions (nonlinearities) used were Leaky ReLU [Maas et al., 2013; Xu et al., 2015a]. The dropout rate used was 0.2. The training algorithm used was Adam [Kingma and Ba, 2015], with initial learning rate 0.001. Adam modifies the learning rate of each individual weight as it progresses through minibatches. The time it took to go through one iteration (i.e. a full sweep over the training dataset) was 760 seconds on an Nvidia 1080. The hyperparameters where chosen using a validation set on the smaller version of the bAbI tasks. We used Keras 2 (a neural network framework), Theano 3 (a deep learning library) and Python for our implementation. Each neural layer had 128 units. In total there were 263, 621 parameters (weights). The full code of this work can be found here: https://github.com/ssamot/conv-match 4 .

4.2 Results

For the main architecture, we present two different tables of results and a progress plot (see Figure 2) on the training set iteration notice the relative stability of the runs. Both tables contain the same Convolutional Match Network (CMN) results, but they compare against prior works' best-run performance (Table 1) and mean performance (Table 2). The reporting of the results follows the conventions of [Graves et al., 2016] - where the failure rate is calculated by running the experiments n times (in our case, n = 20) and finding out the mean failures we had (where error > 5%) for each task. It can be seen from the outset that our results are better than their direct competitors. The CMN architecture is extremely stable when it comes to learning, with very few "bumps". Note that we do not report the "best" score, as we did not collect results using a similar procedure to [Graves et al., 2016] - i.e. reporting the best of a validation set - hence, we use the mean instead of the best. This can be considered a strength of our architecture, in that training-run performance is so robust. Though not formally reported in the tables, our best result has 2.8 overall error rate, which is also comparable to [Xiong et al., 2016]. Note that [Xiong et al., 2016] compare their results with neural networks that are trained for each task individually (and also follow the pattern of reporting "best results") - thus we assume they follow the same methodology and do not include a full comparison with their results here.

2 https://github.com/fchollet/keras

3 https://github.com/Theano/Theano

4 To be used in conjunction with Keras commit ID 06cc6d7fea7527e99e36c9fc766390c51e73ebba.

Figure 2: Average loss on the training set for the 99th interval on the 10K bAbI dataset.

On top of the initial results, we provide a set of further results in Table 3. This set of results is conducted on variations of the original architecture. Though none of the architectural modifications achieves improved results over the original, they are worth discussing as they give some insight as to why this architecture is so successful. In the table, columns headings prefixed by "10K" indicate the full dataset of 10,000 questions per task were used. Those columns headed 10K - n, where n is one of 3, 5, 7, 9, are versions of the network that do not pad on sentence level, and use n × n neurons as the convolution filter length. From the results it can be seen that filter lengths of n = 5 produce the best results, with n = 7 producing the worst. We cannot see any relationship between the filter size and the data. Though smaller filter sizes allow for more "granularity", they also create more chunks of information to attend over - hence we hypothesise that optimal lengths are very much task specific. The very high variance between different filter sizes might explain why DNC results have such a large variance - the extra knowledge provided by padding and fixing the filter length to the sentence size is very beneficial. Columns "10K-Max" and "10K-Mean" demonstrate variations of the architecture that remove the AttentionRecurrent layer and replace it with a simple max or mean operation over all incoming inputs, along each neuron. Again, the results indicate that this layer greatly helps the network, especially with tasks that need a lot of "recursive searching", like QA2 - Two Supporting Facts, QA03 - Three Supporting Facts and QA19 - Path Finding. The results of "10K-CNN" replaces the TDD layer with a convolution of filter length n = 3. This doesn't seem to affect the overall performance that much, but does actually get rather low scores in QA17 - Positional Reasoning and QA03 - Three Supporting Facts.

For the sake of completeness, we also provide results for the version of the test where only 1K examples per task are given (column headed "1K"). We solve more tasks than the best MEM2NN - see [Sukhbaatar et al., 2015] (6 failures instead of 10), but have a slightly higher mean error (13 vs 12.4), which can be clearly attributed to our failure in dealing with task QA16 - Basic Induction. For the 1K training setting we used a dropout rate of 0.5 and 500 training epochs, to account for less training examples per epoch.

Overall, CMN's mean is better than the best provided result of its competitors. The worst number of failed tasks we have observed is two, and we suspect that this can be fixed with hyperparameter tuning. The only task that CMN fails to attack successfully is QA16 - Basic Induction. We hypothesise that this is due to the fact that our architecture focuses too much on differences between memories and questions and fails to adequately capture the relevance of different memories with one another.

A MEM2NN uses bag of words for each sentence (and positional encoding), and compares each question to each sentence individually, so it is aware of the sentence level structure of the task. This is much heavier pre-processing than the one we use. One of our strengths is that we don't use bags of words, we directly throw the data to the NN (with padding). DNCs operate on word level directly, with no knowledge that a sentence exists. This might be a reason behind their inherent instability - as discussed above. We provide knowledge of "what is a good data chunk to attend over" combined with using the natural structure of the sentences. Note that none of the architectures (including ours) embeds sentences directly - all operate more or less on a word level. Note also that we do not perform any other kind of pre-processing, in contrast for example to both [Sukhbaatar et al., 2015] and [Xiong et al., 2016] who used fewer sentences for task QA3 - Three Supporting Facts.

5 Conclusion

In this paper, we have proposed a novel method for attacking problems that respond well to memory and attention mechanisms. Our contribution is in presenting a new neural network architecture, Convolutional Match Networks (CMN), that combines individual neuron match functions and a recurrent softmax attention mechanism.

We have tested the performance of this new neural architecture against the current state-of-the-art mechanisms: the Neural Turing Machine (NTM), Memory Networks (MEM2NN) and the Differentiable Neural Computer (DNC), using the bAbI benchmark set of question-answering tasks. In the previous section, we presented results that show that CMN outperforms the state-of-the-art in terms of mean scores by a large margin. Although in our experiments CNM failed to solve the QA16 - Basic Induction task, we believe this is an issue that can be fixed with an attention layer that includes a separate set of weights or a hop that does not address a specific question, but rather propagates memories directly.

There are several avenues for future work. There is scope to vary some of the design choices made so far in this architecture, such as the choice of hyperparameters and match function. Also it would be interesting to vary the application mode of the convolution, or the application of the match function to later hops, or the design of equation (2) to vary the way recurrent memories are decayed. We are also aiming at introducing hops without a corresponding question. Finally, it would be interesting to use the explicit knowledge learned from the bABI tasks and use it as a seed for general question answering, possibly combined with some method that avoids catastrophic forgetting [French, 1999]. This should allow for the incremental learning of different memory representations, something that would greatly help in real-world scenarios.