Title: REASONING WITH MEMORY AUGMENTED NEURAL NETWORKS FOR LANGUAGE COMPREHENSION

Abstract: Hypothesis testing is an important cognitive process that supports human reasoning. In this paper, we introduce a new computational hypothesis testing framework that is based on memory augmented neural networks. Our approach involves a hypothesis testing loop that reconsiders and progressively refines a previously formed hypothesis in order to generate new hypotheses to test. We applied the proposed approach to language comprehension task by using Neural Semantic Encoders (NSE). Our NSE models achieved the state-of-the-art results showing an absolute improvement of 1.2% to 2.6% accuracy over previous results obtained by single and ensemble systems on standard machine comprehension benchmarks such as the Children's Book Test (CBT) and Who-Did-What (WDW) news article datasets.
With the recent development of large-scale Cloze-type QA datasets (Hermann et al., 2015; Hill et al., 2015; Onishi et al., 2016) and deep neural network methods, remarkable advances have been made in order to solve the problem in an end-to-end fashion. The existing neural network approaches can

1. INTRODUCTION:

Formulating new hypotheses and testing them is a cognitive process that supports human reasoning and intelligence. This hypothesis testing process involves selective attention, working memory and cognitive control (Just and Carpenter, 1992; Polk and Seifert, 2002) . Attention and working memory are engaged in order to maintain, manipulate, and update new hypotheses. Cognitive control is required to inspect and ignore incorrect hypotheses. Inspired by the hypothesis testing process in the human brain and to support dynamic reasoning of machines, in this work, we introduce a reasoning approach that is based on memory augmented neural networks (MANN) . A new hypothesis is formed by regressing the original statement (i.e. query in context of QA). Then the hypothesis is tested against reality (i.e. data or document story). If the model is satisfied with the current test response or the hypothesis is true, the reasoning process is halted and the answer is found. Otherwise, another hypothesis is formulated by refining the previous one and the process is repeated until the answer is found.

While the idea of modeling hypothesis testing with MANN remains a generic reasoning framework and is applicable to several AI tasks, we apply this approach to cloze-type QA by using Neural Semantic Encoders (NSE). NSE is a flexible MANN architecture and have shown a notable success on several language understanding tasks ranging from sentence classification to language inference and machine translation (Munkhdalai and Yu, 2016) . NSE has read, compose and write modules to manipulate external memories and it has introduced a concept of shared and multiple memory accesses, which has shown to be effective for sequence transduction problems.

Cloze-type question answering (QA) is a clever way to assess the ability of human and machine to comprehend natural language. This type of tasks are attractive for the natural language processing (NLP) community because the test sets or datasets can be generated without requiring expert's supervision, in an automatic manner, which is typically useful in training and testing artificial intelligent (AI) systems that can understand human language. In cloze-type QA setup, the machine is first presented with a text document containing a fact set and then it is asked to output answer for a query related to the document. be broadly divided into single-step or multi-step comprehension depending on how documenting reading and answer inference processes are modeled. By mimicking human readers for a deeper reasoning, the multi-step comprehension systems have shown promising results (Hermann et al., 2015; Hill et al., 2015; Trischler et al., 2016; Sordoni et al., 2016) . However, the current multiturn models are designed with the predefined number of computational hops for inference while the difficulty of document and query pairs can vary. Some of the query-document pairs require a shallow reasoning like word or sentence level matching, but for some of them a deeper document level reasoning or a complex semantic understanding is crucial.

The proposed NSE comprehension models perform a reasoning process we called hypothesis-test loop. In each step, a new hypothesis for the correct answer is formed by a query regression. Then the hypothesis is checked and if it is true, the model halts the reasoning process (or the hypothesistest loop) to give the correct answer. To this end, unlike previous methods with fixed computation our models introduce halting procedure in the hypothesis-test loop. When trained with classic back-propagation algorithm, our NSE models show consistent improvements over state-of-the-art baselines on two cloze-type QA datasets.

2. RELATED WORK:

Recently, several large-scale datasets for machine comprehension have been introduced, including the cloze-type QA (Hermann et al., 2015; Hill et al., 2015; Onishi et al., 2016) . Consequently there is an increasing interest in developing neural network approaches to solve the problem in an end-toend fashion. The existing models for cloze-type QA can be categorized into single-step or multi-step approach depending on their comprehension process.

2.1. SINGLE-STEP COMPREHENSION:

Singe-step comprehension methods read input document once with a single computational hop to make answer prediction. The reading process mainly involves context modeling with bi-directional recurrent neural networks (RNN) and selective focusing with attention mechanism. Hermann et al. (2015) introduced a CNN/Daily News QA task along with a set of baseline models such as Attentive Reader and Impatient Reader. The Attentive Reader model reads the document and the query with bi-directional LSTM (BiLSTM) networks and selects a query-relevant context by attending over the document. Chen et al. (2016) re-designed the Attentive Reader model (so called Stanford Attentive Reader) and examined the CNN/Daily News QA task. They found out that roughly 25% of all queries in Hermann et al. (2015)'s dataset is unanswerable and the recent neural network approaches have obtained the ceiling performance on this task. Kadlec et al. (2016) proposed an Attention Sum (AS) reader model that first attends over the document and then aggregates all the attention score for the same candidate answer to select the highest scoring candidate as correct answer.

However, for complex document and query pairs with deeper semantic association machine reading only once may not be enough and multiple reading and checking is crucial to perform deeper reasoning.

2.2. MULTI-STEP COMPREHENSION:

Similar to a human reader, multi-step comprehension methods read the document and the query before making the final prediction. This kind of comprehension is mostly achieved by implementing an external memory and an attention mechanism to retrieve the query-relevant information from the memory throughout time steps. Hermann et al. (2015) 's Impatient Reader revisits the document states with the attention mechanism whenever it reads the next query word in each time scale. Hill et al. (2015) extended multi-hop Memory Networks (Sukhbaatar et al., 2015) with self-supervision to retrieve supporting memory. EpiReader performs a two-stage computation (Trischler et al., 2016) . First it chooses a set of most probable answers with the AS model and forms new queries by replacing an answer placeholder in the original query with the candidate answer words. Second EpiReader runs an entailment estimation between the document and the new query pairs to predict the correct answer. Gated Attention (GA) reader extends the AS model with document-gating and iterative reading of the document and the query (Dhingra et al., 2016) . The query representation is used as gating for the document and the iterative reading is accomplished by having separate bi-directional gated recurrent unit (GRU) networks for each computational hop. Iterative Alternative Attention (IAA) reader (Sordoni et al., 2016) is a multi-step comprehension model which uses a GRU network to search for correct answers from a document. In this model, the GRU network is expected to collect evidence from the document and the query that assists prediction in the last time step. Cui et al. (2016) introduced attention-over-attention loss by computing a word level query-document matching matrix. This model provides a fine-grained word-level supervision signal which seems to help model training.

Our proposed model performs multiple computational steps for deeper reasoning. Unlike the previous work, in our model the number of steps to revise the document is not predefined and it is dynamically adapted for a particular document and query pair. Furthermore, we define novel ways to substitute query words with a word chosen from the document (i.e. regression process) and to check a hypothesis that the selected document word actually compliments the query (i.e. check process). When the hypothesis is true, our model halts the reading process and outputs the word chosen from the document as the correct answer. NSE is used as a controller for the whole process throughout the reasoning steps.

Among the aforementioned models, EpiReader seems to be the most relevant one to our language comprehension models. However, having an entailment estimation introduces a constraint in EpiReader which limits its application. Our model is generic and can be useful in different tasks other than machine comprehension such as language-based conversational tasks, knowledge inference and link prediction. As EpiReader has tightly integrated two-stage neural network modules, the performance directly depends on the first stage. If the first module misses out or fails to choose enough candidates, no correct answer can be found. Our model has no such issue and is not constrained in forming new queries. More recently, the idea of dynamic termination in the context of language comprehension is proposed by Shen et al. (2016) independently. While they use reinforcement learning, we explore two different approaches: adaptive computation and query gating to be fully trained by end-to-end back-propagation.

3. PROPOSED APPROACH:

Our dataset consists of tuples (D, Q, A, a), where D is the document (i.e. passage) serving as a fact for the query Q, A is a set of candidate answers and a ∈ A is the true answer. The document and the query are sequences of tokens drawn from a vocabulary V . We train a model to predict the correct answer a from the candidate set A for given a pair of query and document.

The main components of our proposed model are shown in Figure 1 . First the query and the document memory are initialized via context embedding (omitted from the figure). The memories are then processed with memory read and write operations throughout the hypothesis-test loop. In each step of the loop, the read module formulates a new hypothesis by updating the query memory with relevant content from the document memory. Then the write module tests whether the new hypothesis is true by inspecting the current query and the document states. Selecting relevant content from the document to regress the old query is essentially an inference (i.e. prediction) in our model. Intuitively the input query is regressed toward (becoming) a complete query containing the correct answer word within it. If the write module thinks that the query is complete and the correct answer is found, it halts the hypothesis-test loop. The write module also supervises the query state transitions and retains the right to roll back the new query changes during the reasoning process. To avoid an overconfident prediction and to halt the reasoning process, we explore two different strategies: (a) query gating and (b) adaptive computation.

Like a human reader, the model reads the document multiple times, formulates a hypothetical answer for the query and tests it against the story of the document throughout the hypothesis-test steps. Once satisfied with the response of the current hypothesis, the model outputs the response as the correct answer.

3.1. MEMORY INITIALIZATION:

Instead of using raw word embeddings, we initialize the document and the query memories via context embedding in order to inform the memory slots of contextual information from text passages.

r M d M t q c w M q t+1 s q t-1 , s d t-1 t t+1 Answer r M d M t q c w M q t+1 s q t-1 , s d t-1 t t+1

Answer Two BiLSTM networks are applied to the document and the query sequences separately, as:

EQUATION

EQUATION

where M q 0 ∈ R k×|Q| and M d ∈ R k×|D| are the memory representations. k is the size of BiLSTM hidden layer. The query memory is evolved over time while the document memory is not updated and rather serves as a fact set for the query.

Note that in our model the context embedding network can be any network accepting word embeddings as input, such as multilayer perceptron (MLP) or convolutional neural network. We choose BiLSTM because it is able to learn the word-centered context representation effectively by reading text with LSTMs from both left and right and concatenating resulting hidden vectors.

3.2. HYPOTHESIS TESTING:

The query and the document memories are further processed through an iterative process called hypothesis-test loop. In each step of the loop, the query memory M q is updated with content from the document memory to form a new query (i.e. hypothesis formulation). The new query is then checked against the document facts and used to make an answer prediction (i.e. hypothesis testing). The NSE read, compose and write modules collectively perform the following overall process.

Read: this module takes in the query and the document states s q t-1 , s d t-1 ∈ R k from the previous time step t -1 as input and computes the alignment vectors l q t ∈ R |Q| , l d t ∈ R |D| , the new query and the document states s q t , s d t ∈ R k and the query memory key vector z q t ∈ R |Q| as follows1 :

EQUATION

EQUATION

s q t = sof tmax(l q t ) M q t-1

(5)

EQUATION

EQUATION

s d t = sof tmax(l d t ) M d (8)

Intuitively depending on the previously retrieved document content as well as the previous query states, the read module retrieves from the document a word to be relocated to the query and computes the positions of this word in the query. Since the document word can be located in multiple different positions in the query, sigmoid function is used to normalize the alignment vector l q t . The document state s d t represents the newly retrieved word and the key vector z q t defines its new position in the query memory. Because such a decision is made sequentially in every step, we equip the read module with a LSTM network (i.e. read LST M ). We initialize the document and the query states s d 0 , s q 0 with the last hidden states of the query and the document BiLSTM networks. Compose: the compose module combines the current query and document states s q t , s d t and the current hidden state of the read module r t ∈ R k as:

EQUATION

The resulting single vector c t ∈ R k is passed to the write module for subsequent process. The compose module can be viewed as a feature extractor from the current document and query pair. By taking in the hidden state r t , the compose module also informs the write module of the read module's current decision.

Write: this module accepts the outputs of the read module and updates the query memory as follows:

EQUATION

where 1 is a matrix of ones. Note that the values of the key vector z q t ranges from zero to one and zero (or near zero) values indicate the query position where the new document word is written.

The write module is also responsible for checking the new hypothesis in order to decide whether to halt the hypothesis-test loop for the final answer or to continue. We explore two different strategies to be discussed below. Both methods take in the output of the compose module and employs the LSTM to make the sequential decision.

3.2.1. QUERY GATING:

Figure 1 (a) shows the overall architecture of our model with query gating mechanism. In this model instead of making a hard decision on halting the loop (i.e. stop reading), the write module performs a word-level query gating as:

EQUATION

EQUATION

M q t = M q t (1 -g q t ) + M q t-1 g q t (13) where 1 is a matrix of ones. The key part in the above equation is obtaining the gating weights. This is accomplished by comparing each memory slot with the hidden vector w t ∈ R k and normalizing resulting scores with sigmoid function. Therefore, the gating vector g q t ∈ R |Q| have ones for preserving and zeros for erasing content of the old query.

This can be seen as a memory gating process which prevents the model from forgetting the old query information. Note that even if the query memory is updated with the document content given by the read module, the write module makes the final decision based on features extracted by the compose module. In other words if the write module decides to keep the old query information, the changes in the new query are simply ignored and the same query from the previous time step is passed along to the next step. The number of steps T in the hypothesis-test loop is a hyperparameter in this model. Therefore, in this setup the write module is expected to lock the query state with its gating mechanism as soon as the hypothesis is true.

3.2.2. ADAPTIVE COMPUTATION:

In this model, the write module is equipped with a termination head as shown in Figure 1 (b) . Particularly, the write module with the termination head decides its willingness to continue or finish the computation in each step.

We define a probabilistic framework for halting. Our approach is similar to the input and output handling mechanism of Neural Random-Access Machines (Kurach et al., 2016) . In each time step, the write module outputs a termination score e t as follows:

EQUATION

)

EQUATION

where o ∈ R k is a trainable vector that projects the hidden state w t to a scalar value. Then the probability to halt the hypothesis-test loop after t steps is

EQUATION

We also introduce a hyperparameter T for the maximum number of permitted steps. If the model runs out of the time without halting the process (after T steps), we force the model to output the final answer in step T . In this case, the probability to stop reading is

p T = 1 - T -1 i=1 p i (17)

3.3. ANSWER PREDICTION:

In step t, the query-to-document alignment score l d t is used to compute the probability P (a|Q, D) that the answer a is correct given the document and the query. In particular, we adapt the pointer sum attention mechanism (Kadlec et al., 2016) as

EQUATION

where v ∈ R |D| is a mask denoting the positions of the answer token a in the document (ones for the token and zeros otherwise). LSTMs (context + query) (Hill et al., 2015) 51.2 41.8 62.6 56.0 MemNNs (window mem. + self-sup.) (Hill et al., 2015) 70.4 66.6 64.2 63.0 AS Reader (Kadlec et al., 2016) 73.8 68.6 68.8 63.4 GA Reader (Dhingra et al., 2016) 74.9 69.0 69.0 63.9 EpiReader (Trischler et al., 2016) 75.3 69.7 71.5 67.4 IAA Reader (Sordoni et al., 2016) 75.2 68.6 72.1 69.2 AoA Reader (Cui et al., 2016) 77.8 72.0 72.2 69.4

MemNN (window mem. + self-sup. + ensemble) (Hill et al., 2015) 70.4 66.6 64.2 63.0 AS Reader (ensemble) (Kadlec et al., 2016) 74.5 70.6 71.1 68.9 EpiReader (ensemble) (Trischler et al., 2016) 76.6 71.8 73.6 70.6 IAA Reader (ensemble) (Sordoni et al., 2016) 76.9 72.0 74.1 71.0 For the query gating model, we use the probability P T (a|Q, D) produced in the last step T to choose the correct answer. For the second model, we incorporate the termination score p t and redefine the probability as

NSE (T =

EQUATION

We then train the models to minimize cross-entropy loss between the predicted probabilities and correct answers.

4. EXPERIMENTS:

We evaluated our models on two large-scale datasets: Childrens Book Test (CBT) (Hill et al., 2015) and Who-Did-What (WDW) (Onishi et al., 2016) . We focused on these tasks because there is still a large gap between the human and the machine performances on CBT and WDW, which is in contrast to the CNN/Daily News QA datasets covered in Section 2. The CBT dataset was constructed from the children book domain whereas the WDW corpus was built from the news article domain (the English Gigaword corpus); therefore we think that the two datasets are quite representative for evaluation of our models. Furthermore the CBT dataset comes with two difficult tasks depending on the type of answer words to be predicted: named entity (CBT-NE) and common nouns (CBT-CN).

The WDW training set has two different setups with strict and relaxed baseline suppression. Table 1 summarizes some important statistics of the datasets.

4.1. TRAINING DETAILS:

We chose one-layer LSTM networks for the read and the write modules and an MLP with singlelayer for the composition module. We used stochastic gradient descent with an Adam optimizer to train the models. The initial learning rate (lr) was set to 0.0005 for CBT-CN or 0.001 for other tasks.

A pre-trained 300-D Glove 840B vectors (Pennington et al., 2014) were used to initialize the word embedding layer2 ; therefore the embedding layer size is 300. The hidden layer size of the context embedding BiLSTM nets k = 436. The embeddings for out-of-vocabulary words and the model parameters were randomly initialized from the uniform distribution over [-0.1, 0.1). The gradient clipping threshold was set to 15. The models were regularized by applying 20% dropouts to the embedding layer3 . We used the batch size n = 32 for the CBT dataset and n = 25 for the WDW dataset and early stopping with a patience of 1 epoch. For the WDW dataset, we anonymized the answer candidates by following the work of Onishi et al. (2016) and Hermann et al. (2015) .

We run a hyperparameter search over k = 256, 368, 436, 512 , lr = 0.0005, 0.001 and l 2 decay = 0.0001, 0.00005, 0.00001 on the CBT dev sets to come up with the current setting for training. Among these parameters, the l 2 weight decay regularizer did not seem to help and thus it was not applied. We did not tune the dropouts.

We used the following batching heuristic in order to speedup the training. We created a temporary example pool by randomly sampling from the training set and sorted them according to the length of the document. Then the first n examples (n = 32 or n = 25) of the ordered pool were put into the same batch, without replacement, and the rest of the pool was replaced back in the training set. This is performed until there is not enough training examples to create a new pool. Finally the documents in the same batch are padded with special symbol <pad> to the same length. The batches were regenerated in every epoch to prevent the model from learning a simple mapping function. We also padded queries in the same batch with the special symbol to an equal length.

4.2. RESULTS:

In Tables 2 and 3 we compared the performance of our models with all published models (as baselines) including their ensemble variations. We report the performance of our query gating model at the varying number of hypothesis-test steps T = 1, 2, 6, 9, 12 . T for our adaptive computation model was set to 2 or 12. When T = 1, both models update the memory only once and do not have enough time to read it back and thus they are reduced to the same model called NSE (i.e. NSE T = 1). Typically when T is greater than one, the proposed halting strategies result in two different models.

Our query gating model achieves 72.6% and 72.0% accuracy on the CBT tasks outperforming all the previous baselines. The performance varies for the different number of steps. For the larger number of allowed steps, the query gating model tends to overfit on the CBT dataset as the performance gap between the dev and test sets increases. Our NSE Adaptive Computation model sets the best score on CBT-NE task with 73.2% accuracy. Overall our NSE models bring modest improvements of 1.2% on CBT-NE and 2.6% on CBT-CN tasks and now the performance differences between the human and the machines are only 8.4% and 9.6%.

On the WDW task our single model, NSE with adaptive computation, scores 2.2% and 1.7% higher than the previous best result of Stanford Attentive Reader. The NSE Query Gating model obtains its best result when T = 9. Comparing to the proposed variations of NSE, our Adaptive Computation model is more robust and sets new state-of-the-art performance on three out of four tasks by effectively deciding when to halt the reasoning processing with the termination head. Memory locking (to prevent from forgetting) did not show to be as effective as the termination-based approach on this task. In Appendix A, we visualize query regression process in both models and observe that while new queries are generated, query words relevant to the correct answer are not overwritten by the memory write module.

The performance of the NSE model with T = 1 matches that of the previous single systems. In general given a small number of permitted steps, the proposed models tend to less overfit but the final performance is not high. As the number of permitted steps increases both dev and test accuracy improves yielding an overall higher performance. However, this holds up to a certain point and with a large permitted steps we no longer observe a significant performance improvement in terms of testing accuracy. For example, NSE Query Gating model with T = 15 (not included in the table) achieved 79.2% dev accuracy and 71.4% test accuracy on CBT-NE task, showing the highest accuracy on the dev set yet massively overfitting on the test set. Furthermore it becomes expensive to train a model with a large number of allowed steps.

It is worth noting that even if the proposed models in this work were trained using classic end-toend back-propagation, they can easily be trained with reinforcement learning methods, such as the REINFORCE algorithm (Williams, 1992), for further evaluation. Such an adaptation is particularly straightforward for NSE Adaptive Computation because this model has already incorporated a probabilistic termination head in it.

5. CONCLUSION:

Inspired by cognitive process of hypothesis testing in human brain, we proposed a reasoning approach based memory augmented neural networks and applied it to language comprehension. Our proposed NSE models with dynamic reasoning have achieved the state-of-the-art results on two machine comprehension tasks. In order to halt reasoning process we explored two different strategies to be fully trained with classic back-propagation algorithm: query memory gating which prevents from forgetting old query and adaptive computation with termination head. The NSE adaptive computation model has shown to be effective in the experiments. Our proposed models can be trained using reinforcement learning. We plan to apply our approach to other AI tasks, such language-based conversational tasks, link prediction and knowledge inference.

:

For brevity, we omit the broadcasting operations from the equations.

http://nlp.stanford.edu/projects/glove/

More detail on hyperparameters can be found in our code: https://bitbucket.org/tsendeemts/nse-rc

Figures and Tables:

Figure 1: High-level architectures of our proposed models: the NSE Query Gating model (a) and the NSE Adaptive Computation model (b).The query memory of the former is gated to the next step by the write module whereas the query memory in the latter is updated and passed to the next step without gating and the write module is trained to halt the hypothesis-test loop. r: read, c: compose and w: write module.

Statistics of the datasets. train (s): train strict, train (r): train relaxed and cands: candidates.

Table content: <table><tr><td/><td/><td>WDW</td><td/><td/><td/><td>CBT-NE</td><td/><td/><td>CBT-CN</td><td/></tr><tr><td/><td colspan="2">train (s) train (r)</td><td>dev</td><td>test</td><td>train</td><td>dev</td><td>test</td><td>train</td><td>dev</td><td>test</td></tr><tr><td># queries</td><td colspan="10">127,786 185,978 10,000 10,000 108,719 2,000 2,500 120,769 2,000 2,500</td></tr><tr><td>avg. # cands</td><td>3.5</td><td>3.5</td><td>3.4</td><td>3.4</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td></tr><tr><td>avg. # tokens</td><td>365</td><td>378</td><td>325</td><td>326</td><td>433</td><td>412</td><td>424</td><td>470</td><td>448</td><td>461</td></tr><tr><td>vocab size</td><td>308,602</td><td colspan="2">347,406</td><td/><td/><td>53,063</td><td/><td/><td>53,185</td><td/></tr></table>

Model comparison on the CBT dataset.

Table content: <table><tr><td>CBT-NE</td><td>CBT-CN</td></tr></table>

Model comparison on the WDW dataset.

Table content: <table><tr><td>Strict</td><td>Relaxed</td></tr></table>

Peer review (iclr2017):
First I would like to apologize for the delay in reviewing. Summary : this work introduces a novel memory based artificial neural network for reading comprehension. Experiments show improvement on state of the art. The originality of the approach seems to be on the implementation of an iterative procedure with a loop testing that the current answer is the correct one. In order to get a better sense of the reason for improvement it would be interesting to have a complexity and/or a time analysis of the algorithm. I might be mistaken but I don*t see you reporting anything on the actual number of loops necessary in the reported experiments. The dataset description in section 2.2, should be moved to section 4 where the other datasets are described.