Finding ReMO (Related Memory Object): A Simple Neural Architecture for Text based Reasoning
Jihyung Moon Hyochang Yang Sungzoon Cho
cs.AI



Dust in brown dwarfs and extra-solar planets
    Mahesh Babu Vaddi and B. Sundar Rajan
 
 Department of Electrical Communication Engineering, Indian Institute of Science, Bengaluru 560012, KA, India 
 E-mail: {vaddi, bsrajan}@iisc.ac.in 
    Received: 21 Sep 2017 / Accepted: 25 Jan 2018
================================================================================================================================================================================================




To solve the text-based question and answering task that requires relational reasoning, it is necessary to memorize a large amount of information and find out the question relevant information from the memory.
Most approaches were based on external memory and four components proposed by Memory Network.
The distinctive component among them was the way of finding the necessary information and it contributes to the performance.
Recently, a simple but powerful neural network module for reasoning called Relation Network (RN) has been introduced. 
We analyzed RN from the view of Memory Network, and realized that its MLP component is able to reveal the complicate relation between question and object pair.
Motivated from it, we introduce Relation Memory Network (RMN) which uses MLP to find out relevant information on Memory Network architecture.
It shows new state-of-the-art results in jointly trained bAbI-10k story-based question answering tasks and bAbI dialog-based question answering tasks.




§ INTRODUCTION


Neural network has made an enormous progress on the two major challenges in artificial intelligence: seeing and reading.
In both areas, embedding methods have served as the main vehicle to process and analyze text and image data for solving classification problems. As for the task of logical reasoning, however, more complex and careful handling of features is called for.
A reasoning task requires the machine to answer a simple question upon the delivery of a series of sequential information. For example, imagine that the machine is given the following three sentences: “Mary got the milk there.”,  “John moved to the bedroom.”, and “Mary traveled to the hallway.” 
Once prompted with the question, “Where is the milk?", the machine then needs to sequentially focus on the two supporting sentences, “Mary got the milk there." and “Mary traveled to the hallway." in order to successfully determine that the milk is located in the hallway.

Inspired by this reasoning mechanism, <cit.> has introduced the memory network (MemNN), which consists of an external memory and four components: input feature map (I), generalization (G), output feature map (O), and response (R).
The external memory enables the model to deal with a knowledge base without loss of information. 
Input feature map embeds the incoming sentences. Generalization updates old memories given the new input and output feature map finds relevant information from the memory. Finally, response produces the final output.

Based on the memory network architecture, neural network based models like end-to-end memory network (MemN2N) <cit.>, gated end-to-end memory network (GMemN2N) <cit.>, dynamic memory network (DMN) <cit.>, and dynamic memory network + (DMN+) <cit.> are proposed.
Since strong reasoning ability depends on whether the model is able to sequentially catching the right supporting sentences that lead to the answer, the most important thing that discriminates those models is the way of constructing the output feature map. 
As the output feature map 
becomes more complex, it is able to learn patterns for more complicate relations.
For example, MemN2N, which has the lowest performance among the four models, measures the relatedness between question and sentence by the inner product, while the best performing DMN+ uses inner product and absolute difference with two embedding matrices.



Recently, a new architecture called Relation Network (RN) <cit.> has been proposed as a general  solution to relational reasoning. 
The design philosophy behind it is to directly capture the supporting relation between the sentences through the multi-layer perceptron (MLP).
Despite its simplicity, RN achieves better performance than previous models without any catastrophic failure. 


The interesting thing we found is that RN can also be interpreted in terms of MemNN. 
It is composed of O and R where each corresponds to MLP which focuses on the related pair and another MLP which infers the answer.
RN does not need to have G because it directly finds all the supporting sentences at once.
In this point of view, the significant component would be MLP-based output feature map.
As MLP is enough to recognize highly non-linear pattern, RN could find the proper relation better than previous models to answer the given question.

However, as RN considers a pair at a time unlike MemNN, the number of relations that RN learns is n^2 when the number of input sentence is n.
When n is small, the cost of learning relation is reduced by n times compared to MemNN based models, which enables more data-efficient learning <cit.>.
However, when n increases, the performance becomes worse than the previous models.
In this case, the pair-wise operation increases the number of non-related sentence pairs more than the related sentence pair, thereby confuses RN's learning.
<cit.> has suggested attention mechanisms as a solution to filter out unimportant relations; however, since it interrupts the reasoning operation, it may not be the most optimal solution to the problem.

Our proposed model, “Relation Memory Network” (RMN), is able to find complex relation even when a lot of information is given.
It uses MLP to find out relevant information with a new generalization which simply erase the information already used.
In other words, RMN inherits RN's MLP-based output feature map on Memory Network architecture.
Experiments show its state-of-the-art result on the text-based question answering tasks. 



§ RELATION MEMORY NETWORK







Relation Memory Network (RMN) is composed of four components - embedding, attention, updating, and reasoning.
It takes as the inputs a set of sentences x⃗_1, x⃗_2, ..., x⃗_n and its related question u⃗, and outputs an answer a⃗.
Each of the x⃗_i, u⃗, and a⃗ is made up of one-hot representation of words, for example, x⃗_i = {x⃗_i1, x⃗_i2, x⃗_i3, ..., x⃗_in_i} (x⃗_ij∈ℝ^V, j = (1,2,...,n_i), V= vocabulary size, n_i= number of words in sentence i).




 §.§ Embedding component
 
We first embed words in each x⃗_i = {x⃗_i1, x⃗_i2, x⃗_i3, ..., x⃗_in_i} and u⃗ to a continuous space multiplying an embedding matrix A ∈ℝ^d × V.
Then, the embedded sentence is stored and represented as a memory object m⃗_i while question is represented as q⃗.
Any of the following methods are available for embedding component: simple sum (equation <ref>), position encoding <cit.> (equation <ref>), concatenation (equation <ref>), LSTM, and GRU.
In case of LSTM or GRU, m⃗_i is the final hidden state of it.

    m⃗_i = ∑_j A x⃗_ij


    m⃗_i = ∑_j l_j · A x⃗_ij   (l_kj = (1-j/n_i) - (k/d)(1-2j/n_i))


    m⃗_i = [A x⃗_i1, A x⃗_i2, ... , A x⃗_in_i]

As the following attention component takes the concatenation of m⃗_i and q⃗, it is not necessarily the case that sentence and question have the same dimensional embedding vectors unlike previous memory-augmented neural networks.




 §.§ Attention component
 
Attention component can be applied more than once depending on the problem; Figure <ref> illustrates 2 hop version of RMN.
We refer to the i^th embedded sentence on the t^th hop as m⃗_i^t.


To constitute the attention component, we applied simple MLP represented as g_θ^t.
It must be ended with 1 unit output layer to provide a scalar weight w_i^t, which leads to an attention weight α_i^t between 0 and 1.
In the beginning, a vector concatenated with m⃗_i^1 and q⃗ flows to the g_θ^1.
From the result of g_θ^1, attention weight α_i^1 is calculated using additional variable β^1 (≥ 1) to control the intensity of attention, inspired by the way Neural Turing Machine <cit.> reads from the memory.
Then we get the related memory object r⃗^1, a weighted sum of α_i^1 and memory object m⃗_i^1 for all i.
If there exist more hops, r⃗^1 is directly taken to the next hop and iterates over this process with the updated memory object m⃗_i^2.
All the procedures are rewritten as equation <ref>, <ref>, and <ref>:

    w_i^t ← g_θ^t ([m⃗_i^t, r⃗^t-1])    (i = (1, 2, ..., n), r⃗^0 = q⃗)


    α_i^t ←exp (β^t w_i^t)/∑_i exp (β^t w_i^t)   (β^t(z) = 1 + log(1 + exp(z)))



    r⃗^t←∑_i α_i^t ·m⃗_i^t




 §.§ Updating component
 
To forget the information already used, we use intuitive updating component to renew the memory.
It is replaced by the amount of unconsumed from the old one:

    m⃗_i^t+1← (1 - α_i^t ) m⃗_i^t

Contrary to other components, updating is not a mandatory component.
When it is considered to have 1 hop, there is no need to use this.




 §.§ Reasoning component
 
Similar to attention component, reasoning component is also made up of MLP, represented as f_ϕ.
It receives both q⃗ and the final result of attention component r⃗^f and then takes a softmax to produce the model answer â⃗̂:

    â⃗̂←Softmax ( f_ϕ ([r⃗^f, q⃗]))






§ RELATED WORK










  
 











 §.§ Memory-Augmented Neural Network

To answer the question from a given set of facts, the model needs to memorize these facts from the past. 
Long short term memory (LSTM) <cit.>, one of the variants of recurrent neural network (RNN), is inept at remembering past stories because of their small internal memory <cit.>. 
To cope with this problem, <cit.> has proposed a new class of memory-augmented model called Memory Network (MemNN). 
MemNN comprises an external memory m and four components: input feature map (I), generalization (G), output feature map (O), and response (R). 
I encodes the sentences which are stored in memory m.
G updates the memory, whereas O reads output feature o from the memory.
Finally, R infers an answer from o.


MemN2N, GMemN2N, DMN, and DMN+ all follow the same structure of MemNN from a broad perspective, however, output feature map is composed in slightly different way.
The relation between question and supporting sentences is realized from its cooperation.
MemN2N first calculates the relatedness of sentences in the question and memory by taking the inner product, and the sentence with the highest relatedness is selected as the first supporting sentence for the given question.
The first supporting sentence is then added with the question and repeat the same operation with the updated memory to find the second supporting sentence.
GMemN2N selects the supporting sentence in the same way as MemN2N, but uses the gate to selectively add the the question to control the influence of the question information in finding the supporting sentence in the next step.
DMN and DMN + use output feature map based on various relatedness such as absolute difference, as well as inner product, to understand the relation between sentence and question at various points.

The more difficult the task, the more complex the output feature map and the generalization component to get the correct answer.
For a dataset experimenting the text-based reasoning ability of the model, the overall accuracy could be increased in order of MemN2N, GMemN2N, DMN, and DMN+, where the complexity of the component increases.







 §.§ Relation Network


Relation Network (RN) has emerged as a new and simpler framework for solving the general reasoning problem.
RN takes in a pair of objects as its input and simply learns from the compositions of two MLPs represented as g_θ and f_ϕ.
The role of each MLP is not clearly defined in the original paper, but from the view of MemNN, it can be understood that g_θ corresponds to O and f_ϕ corresponds to R.
Table <ref> summarizes the interpretation of RN compared to MemN2N and our model, RMN.


To verify the role of g_θ, we compare the output when pairs are made with supporting sentences and when made with unrelated sentences.
Figure <ref> shows the visualization result of each output.

When we focus on whether the value is activated or not, we can see that g_θ distinguishes supporting sentence pair from non-supporting sentence pair as output feature map examines how relevant the sentence is to the question.
Therefore, we can comprehend the output of g_θ reveals the relation between the object pair and the question and f_ϕ aggregates all these outputs to infer the answer. 







§ EXPERIMENTS




 §.§ Dataset



bAbI story-based QA dataset   bAbI story-based QA dataset <cit.> is composed of 20 different types of tasks for testing natural language reasoning ability.
Each task requires different methods to infer the answer.
The dataset includes a set of statements comprised of multiple sentences, a question and answer.
A statement can be as short as two sentences and as long as 320 sentences.
To answer the question, it is necessary to find relevant one or more sentences to a given question and derive answer from them.
Answer is typically a single word but in a few tasks, answers are a set of words.  
Each task is regarded as success when the accuracy is greater than 95%.
There are two versions of this dataset, one that has 1k training examples and the other with 10k examples.
Most of the previous models test their accuracy on 10k dataset with trained jointly.

bAbI dialog dataset   bAbI dialog dataset <cit.> is a set of 5 tasks within the goal-oriented context of restaurant reservation. 
It is designed to test if model can learn various abilities such as performing dialog management, querying knowledge bases (KBs), and interpreting the output of such queries. 
The KB can be queried using API calls and 4 fields (a type of cuisine, a location, a price range, and a party size).
They should be filled to issue an API call.
Task 1 tests the capacity of interpreting a request and asking the right questions to issue an API call.
Task 2 checks the ability to modify an API call.
Task 3 and 4 test the capacity of using outputs from an API call to propose options in the order of rating and to provide extra-information of what user asks for.
Task 5 combines everything. 
The maximum length of the dialog for each task is different: 14 for task 1, 20 for task 2, 78 for task 3, 13 for task 4, and 96 for task 5.
As restaurant name, locations, and cuisine types always face new entities, there are normal and OOV test sets to assess model's generalization ability. 
Training sets consist fo 1k examples, which is not a large amount of creating realistic learning conditions.










 §.§ Training details


bAbI story-based QA dataset   We trained 2 hop RMN jointly on all tasks using 10k dataset for model to infer the solution suited to each type of tasks.  
We limited the input to the last 70 stories for all tasks except task 3 for which we limited input to the last 130 stories, similar to <cit.> which is the hardest condition among previous models.
Then, we labeled each sentence with its relative position. 
Embedding component is similar to <cit.>, where story and question are embedded through different LSTMs; 32 unit word-lookup embeddings; 32 unit LSTM for story and question.
For attention component, as we use 2 hop RMN, there are g_θ^1 and g_θ^2; both are three-layer MLP consisting of 256, 128, 1 unit with ReLU activation function <cit.>.
f_ϕ is composed of 512, 512, and 159 units (the number of words appearing in bAbI dataset is 159) of three-layer MLP with ReLU non-linearities where the final layer was a linear that produced logits for a softmax over the answer vocabulary. 
For regularization, we use batch normalization <cit.> for all MLPs. 
The softmax output was optimized with a cross-entropy loss function using the Adam optimizer <cit.> with a learning rate of 2e^-4.


bAbI dialog dataset   We trained on full dialog scripts with every model response as answer, all previous dialog history as sentences to be memorized, and the last user utterance as question. 
Model selects the most probable response from 4,212 candidates which are ranked from a set of all bot utterances appearing in training, validation and test sets (plain and OOV) for all tasks combined. 
We also report results when we use match type features for dialog. 
Match type feature is an additional label on the candidates indicating if word is found on the dialog history.
For example, if the world `Seoul' is found, then the `location' field is checked to hint model this word is important and should be used in API call.
This feature can alleviate OOV problem. 
Training was done with Adam optimizer and a learning rate of 1e^-4 for all tasks.
Additional model details are given in Appendix <ref>.







§ RESULTS AND DISCUSSION




 §.§ bAbI story-based QA


As we can see in table <ref>, RMN shows state-of-the-art result on bAbI story-based Question Answering dataset: 98.8% accuracy where only a single task with no catastrophic failure. 
It succeeded on task 17, 18, 19 where MemN2N, GMemN2N, and DMN are failed to solve, and on task 16 which DMN+, DNC, and EntNet scored high error rates.




footnote-1
For a fair comparison, we report EntNet's result which was jointly trained on all tasks. It was written in the appendix of the paper.
footnote1
Our implementation. The result is different from what <cit.> mentioned, which is caused by the initialization.





Table <ref> shows how our model solved several tasks.
RMN's attention component g_θ^1 and g_θ^2 complement each other to identify the necessary facts to answer correctly.
Sometimes both g_θ^1 and g_θ^2 concentrate on the same sentences which are all critical to answer the question, and sometimes g_θ^1 finds a fact related to the given question and with this information g_θ^2 chooses the key fact to answer. 
While trained jointly, RMN learns these different solutions for each task.
For the task 3, the only failed task, attention component still functions well; it focuses sequentially on the  supporting sentences.  
However, the reasoning component, f_ϕ, had difficulty catching the word `before'. 
We could easily figure out `before' implies `just before' the certain situation, whereas RMN confused its meaning. 
As shown in table <ref>, our model found all previous locations before the garden. 
Still, it is remarkable that the simple MLP carried out all of these various roles. 





 §.§ bAbI dialog




The results in the Table <ref> show that the RMN has the best results in any conditions.
Without any match type, RN and RMN outperform previous memory-augmented models on both normal and OOV tasks.
This is mainly attributed to the impressive result on task 4 which can be interpreted as an effect of MLP based output feature map.  

To solve task 4, it is critical to understand the relation between `phone number' of user input and `r_phone' of previous dialog as shown in Table <ref>.
We assumed that inner product was not sufficient to capture their implicit similarity and performed an supporting experiment.
We converted RMN's attention component to inner product based attention, and the results revealed the error rate increased to 11.3%.

For the task 3 and task 5 where the maximum length is especially longer than the others, RN performs worse than MemN2N, GMemN2N and RMN.
The number of unnecessary object pairs created by the RN not only increases the processing time but also decreases the accuracy. 


With the match type feature, all models other than RMN have significantly improved their performance except for task 3 compared to the plain condition.
RMN was helped by the match type only on the OOV tasks and this implies RMN is able to find relation in the With Match condition for the normal tasks.

footnote-1
We only compare models under the same conditions
footnote+1
Our implementation.

When we look at the OOV tasks more precisely, RMN failed to perform well on the OOV task 1 and 2 even though g_θ^1 properly focused on the related object as shown in Table <ref>.
We state that this originated from the fact that the number of keywords in task 1 and 2 is bigger than that in task 4.
In task 1 and 2, all four keywords (cuisine, location, number and price) must be correctly aligned from the supporting sentence in order to make the correct API call which is harder than task 4.
Consider the example in Table <ref> and Table <ref>.
Supporting sentence of task 4 have one keyword out of three words, whereas supporting sentences of task 1 and 2 consist of four keywords (cuisine, location, number and price) out of sixteen words. 

Different from other tasks, RMN yields the same error rate 25.1% with MemN2N and GMemN2N on the task 3. 
The main goal of task 3 is to recommend restaurant from knowledge base in the order of rating.
All failed cases are displaying restaurant where the user input is silencewhich is somewhat an ambiguous trigger to find the input relevant previous utterance. 
As shown in Table <ref>, there are two different types of response to the same user input. 
One is to check whether all the required fields are given from the previous utterances and then ask user for the missing fields or send a “Ok let me look into some options for you.” message.
The other type is to recommend restaurant starting from the highest rating. 
All models show lack of ability to discriminate these two types of silences so that concluded to the same results.  
To verify our statement, we performed an additional experiment on task 3 and checked the performance gain (extra result is given in Table <ref> of Appendix <ref>). 










 §.§ Model analysis


Effectiveness of the MLP-based output feature map  The most important feature that distinguishes MemNN based models is the output feature map.
Table <ref> summarizes the experimental results for the bAbI story-based QA dataset when replacing the RMN's MLP-based output feature map with the idea of the previous models.
inner product was used in MemN2N, inner product with gate was used in GMemN2N, and inner product and absolute difference with two embedding matrices was used in DMN and DMN+.
From the Table <ref>, the more complex the output feature map, the better the overall performance.
In this point of view, MLP is the effective output feature map. 




Performance of RN and RMN according to memory size  
Additional experiments were conducted with the bAbI story-based QA dataset to see how memory size affects both performance and training time of RN and RMN. 
Test errors with training time written in parentheses are summarized in Table <ref>.

When memory size is small, we could observe the data-effeciency of RN.
It shows similar performance to RMN in less time.
However, when the memory size increases, performance is significantly reduced compared to RMN, even though it has been learned for a longer time.
It is even lower than itself when the memory size is 20.
On the other hand, RMN maintains high performance even when the memory size increases.




Effectiveness of the number of hops  bAbI story based QA dataset differs in the number of supporting sentences by each task that need to be referenced to solve problems.
For example, task 1, 2, and 3 require single, two, and three supporting facts, respectively.
The result of the mean error rate for each task according to the number of hops is in Table <ref>.


Number in parentheses indicates the number of supporting sentences to solve the task

Overall, the number of hops is correlated with the number of supporting sentences.
In this respect, when the number of relations increases, RMN could reason across increasing the number of hops to 3, 4 or more.












  
















§ CONCLUSION


Our work, RMN, is a simple and powerful architecture that effectively handles text-based question answering tasks when large size of memory and high reasoning ability is required.
Multiple access to the external memory to find out necessary information through a multi-hop approach is similar to most existing approaches.
However, by using a MLP that can effectively deal with complex relatedness when searching for the right supporting sentences among a lot of sentences, RMN raised the state-of-the-art performance on the story-based QA and goal-oriented dialog dataset.
When comparing RN which also used MLP to understand relations, RMN was more effective in the case of large memory.

Future work will apply RMN to image based reasoning task (e.g., CLEVR, DAQUAR, VQA etc.). 
To extract features from the image, VGG net <cit.> is used in convention and outputs 196 objects of 512 dimensional vectors which also require large sized memory. 
An important direction will be to find an appropriate way to focus sequentially on related object which was rather easy in text-based reasoning.


































iclr2018_conference






§ MODEL DETAILS






§ ADDITIONAL RESULTS





We modify the user input from silenceto silencesilencewhen looking for restaurant recommendations.
This makes model to distinguish two different situations whether to ask for additional fields or to recommend restaurant. 

