Title: ANALYSIS OF MEMORY ORGANIZATION FOR DY-NAMIC NEURAL NETWORKS Anonymous

Abstract: An increasing number of neural memory networks have been developed, leading to the need for a systematic approach to analyze and compare their underlying memory capabilities. Thus, in this paper, we propose a taxonomy for four popular dynamic models: vanilla recurrent neural network, long short-term memory, neural stack and neural RAM and their variants. Based on this taxonomy, we create a framework to analyze memory organization and then compare these network architectures. This analysis elucidates how different mapping functions capture the information in the past of the input, and helps to open the dynamic neural network black box from the perspective of memory usage. Four representative tasks that would fit optimally the characteristics of each memory network are carefully selected to show each network's expressive power. We also discuss how to use this taxonomy to help users select the most parsimonious type of memory network for a specific task. Two natural language processing applications are used to evaluate the methodology in a realistic setting.

1. INTRODUCTION:

Memory is crucial for both cognitive science and machine learning in applications that require the use of past information such as sequence learning problems. It is fair to say that recurrent neural networks are the most popular memory networks nowadays. Elman and Jordan proposed the first classic version of the recurrent neural network (RNN) Elman (1990) Jordan (1986) . which is often referred to as vanilla RNNs (vRNNs) currently. However, since the memory of vRNN is internal memory encoded in hidden states, vRNN is difficult to implement in practice: if the temporal dependency relationship of the time series is complex and long, the number of hidden units has to be tremendously increased to fully capture useful past information. The long range dependence problem is one common example of this difficultyTrinh et al. ( 2018) Belletti et al. (2018) Bengio et al. (1994) .

Many dynamic neural networks with new memory structures have recently emerged as improvements of the vRNN architecture. (The terms recurrent, dynamic, and memory neural network are used interchangeably in this paper.) Some of these networks adopt internal memory; some adopt external memory; some adopt logic gates; while others adopt an attention mechanism. As expected, all these methods have advantages for some specific tasks, but selecting or designing an optimal memory model for a new task is very difficult unless we have a clear understanding of how their memory helps solve problem at hand. This is not an easy issue because 'memory' is a very abstract concept and the specific memory requirements for a specific task are implicit, which means that quantitatively conceptualizing and analyzing memory is a very hard problem. Cognitive scientists have defined many different types of memory, which shows the richness of the concept. In engineering, there are only a few engineering quantifiers of memory such as memory depth and memory resolution, but they are not enough for the ever-growing applications of machine learning.

Thus, the main goal of this paper is to investigate the characteristics of memory implemented by each architecture and what information these networks can extract from the input time series. We illustrate the role and characteristics of mapping functions and describe how memory is implemented of each memory network. We also classify popular memory networks into four types and find the essential relationships amongst these classes. The results are summarized in a rigorous taxonomy, which serves as a simple way to quantify the capabilities of extracting and using past information of each class. A secondary goal is to employ the knowledge gained from the different characteristics of these memory structures to help users select the most parsimonious type of memory network given the problem at hand. We achieve this goal by connecting models' relative expressive power to the memory requirements of different tasks and use four synthetic tasks to exemplify each task type. Moreover, two natural language processing applications are used to evaluate the methodology in a realistic setting.

2. RELATED WORK:

Among the abundant recurrent network literature, minimal attention has been given to understanding and analysis of their memory characteristics. Omlin & Giles (1996) discussed how vRNNs behaves like deterministic finite-state automata. Gers & Schmidhuber ( 2001) Rodriguez (2001) Schmidhuber et al. (2002) compared the performance of long short-term memory (LSTM) Hochreiter & Schmidhuber (1997) and vRNN on some context-free/sensitive language. Collins et al. (2016) studied the capacity of recurrent nets and how difficult they are to train. Karpathy et al. (2015) visualized longterm interactions and representations learned by recurrent networks. Greff et al. (2017) empirically studied the importance of various computational components of LSTM. Jozefowicz et al. (2015) evaluated a variety of recurrent neural network architectures and attempted to find the best one. Chung et al. (2014) compared gated recurrent unit (GRU) networks Cho et al. (2014) to LSTM. Yogatama et al. (2018) tested and compared performances of sequential, random access, and stack memory architectures on language modeling dataset. These works assessed network performance based on the output error. By contrast, our work focuses on how these networks encode information to solve a problem. vRNN's internal memory has a lot of limitations since all the useful information is compressed in the hidden states that are continuously changing with the input samples: the past contents and their time information are mixed together, i.e., a certain event can not be extracted without interference, the hidden state has to be updated at every time steps, the long range dependency problem makes it hard to train, etc. These problems make vRNN unpractical. Compared to vRNN, the type of memory of LSTM, neural stack and neural RAM is external. LSTM introduced an external memory slot and the corresponding gate mechanism to address the long range dependency problem. With this external memory slot, a useful event in the past can be extracted without interference. However, if there are multiple useful events, they have to be compressed as a compounded event and accessed as a whole. The specific content of each event and their temporal order can not be captured. Neural stack and neural RAM addressed this problem by introducing multiple-slot external memory, where multiple events can be stored and their temporal order information is also retained. The difference between neural RAM and neural stack is the contents of neural RAM can be accessed randomly.

3. A MEMORY NETWORK TAXONOMY:

The different memory organizations give these networks different expressive power. Actually one class of network architectures can be seen as a special case of another class as shown in Fig. 1 . The memory types are summarized in Table .1. In next section, we will analyze their underlying structures in details and showing their essential relationships. 

4. MEMORY STRUCTURE ANALYSIS:

In this section, we analyze the memory structures of four popular RNNs: vRNN, LSTM, neural stack and neural RAM. Attention is paid to how their underlying memory organizations lead to different features and expressive power. The vRNN network Jordan ( 1986) is composed of three layers: input, hidden recurrent and output. In addition to the feedforward connections, a feedback connection from the hidden layer to itself exists. The architecture is shown in Fig. 2 (a). The dynamics of the hidden layer can be written as

EQUATION

EQUATION

where x t , h t and o t are the input, hidden state and output vector at time t. We use w and b to represent the weight and bias, and f (x) is the nonlinear activation function.

A vRNN induces memory by encoding the past information in its hidden state units h t , which are continuously changing and forced to be used every time; thus, the memory of the vRNN is called state memory or internal memory. Fig. 2 (b) shows the state transition diagram of a vRNN, where s0, s1, ..., s4 represent the state at times t 0 , t 1 , ..., t 4 , respectively. The arrows show the dependency of the variables. Here, state s1 is decided by only s0, s2 is decided by only s1 and so on. (All the memory visualization figures in this paper ignore the current input.)

As the number of hidden units is limited in practice, a compromise between memory depth and memory resolution always exists in the vRNN De Vries & Principe (1992) . For long memory depth sequences, a vRNN requires a very large number of hidden units to achieve acceptable accuracy. If the sequences are composed of symbols or discrete numbers, the limitation of vRNN is even easier to see: the process can be viewed from a Markov transition model perspective. Specifically, the vRNN attempts to learn a first-order Markov transition model (with transition probability 1), where the current state is decided by only current input and the state in the previous step. Thus, since the state space is not very large (the number of states is less than the size of input symbols' alphabet) for first-order Markov sequences, the vRNN always performs well. However, for higher-order Markov sequences or sequences that do not satisfy the Markov property, the vRNN still attempts to build a first-order Markov state model, which results in a very large state space (several old states must be combined into a new state). The compromise between memory depth and memory resolution (which are related to the number and temporal resolution of the states) would make vRNN not suitable for these kinds of sequences. Hence, vRNN is only suitable for lower-order Markov chains.

4.2. LSTM:

LSTM was proposed to address the vanishing gradient problem of vRNN. It was the first memory network that had to address the problem of how to store and retrieve information from an external source to improve performance (through gating networks). In this section, we analyze how LSTM provides greater flexibility from the perspective of memory usage. In contrast to vRNN, in the classic LSTM shown in Fig. 3 (a), the feedback connection of the hidden layer must pass through external memory m t ,

EQUATION

EQUATION

EQUATION

EQUATION

where h t (or c t ) is the network state. The external memory m t is a combination of m t-1 and the current state c t . If g i,t = 0 and g f,t = 1 for several successive time steps, the content saved in the external memory m t would constitute the long-term memory of the system.

The external memory m t adds greater flexibility to the state transition diagram. As shown in Fig. 3(b) , the current state s t (represented by hidden state h t ) depends on either the previous state s t-1 or the external memory m t-1 (if forget gate g f,t = 0 and input gate g i,t = 1, s t depends on s t-1 ; if g f,t = 1 and g i,t = 0, s t depends on m t-1 ; if 0 < g f,t < 1 and 0 < g i,t < 1, s t depends on both m t-1 and s t-1 .

The detailed calculations of these gates are provided in Appendix A.1). For example, s1 depends on the previous state s0, as illustrated by the blue arrows; s7 and s8 depend on the long-term memory M 00, as illustrated by the yellow arrows; and s9 depends on both the previous state s8 and the long-term memory M 00. The introduced external memory circumvents the compromise between the memory depth and memory resolution that is always present in the state memory in vRNN. For instance, for a 10th-order binary Markov sequence whose state dependence relationship is s t = f (s t-1 , s t-10 ), a vRNN has to learn a state space with 2 10 states (10 states are combined into a new state); however, LSTM needs to learn a state model with only 2 states and an external memory storing the state information from 10 steps in the past. By constructing this short path between long-term memory and the current state, LSTM performs much better than vRNN for sequences that skip intermediate values of time dependencies. This long-term memory can also be seen as the event extracted from the input time series. The relationship of LSTM and vRNN is shown in Theorem1.

Theorem 1. LSTM degrades to a vRNN if i) all three gates are constants, i.e., g o = 0, g i = 1 and g f = 0; ii) weight w hc and bias b c are set to constants, i.e., w hc = I and b c = 0; iii) the activation function t(x) is a linear activation function, i.e., t 1 (x) = x.

Proof. See Appendix B.1.

Although LSTM is more effective than vRNN, some limitations still exist. For example, if there is no skip in the time dependence, i.e., s t = f (s t-1 , s t-2 , ..., s t-10 ), LSTM and vRNN have the same expressive power. Therefore, the statement that "LSTM is always better than vRNN" is not correct.

Another drawback of LSTM is the transient storage of long-term memory. In other words, if the long-term memory is updated, the old value is erased. For example, in Fig. 3 (b), at time t 9 , when M00 is updated to M01, M00 is erased. Thus, the future states no longer have access to memory M00. Therefore, this architecture is useful when the previous states do not need to be reutilized after they are updated.

4.3. NEURAL STACK:

A neural stack is a neural network that uses a stack as its external memory. The stack is controlled by either a feedforward network or a vRNN. One property of a stack is that only the topmost content of the stack can be read or written. Writing to the stack is implemented via three operations: push, adding an element to the top of the stack; pop, removing the topmost element of the stack; no-operation, keeping the stack unchanged.

A diagram of a neural stack network is shown in Fig. 4 (a) (here, we use the architecture in Joulin & Mikolov (2015) ). Elements in the stack are updated as follows: 

EQUATION

EQUATION

)

where r t is the vector read at time t,

EQUATION

Although the neural stack architecture looks very different from that of vRNN and LSTM, some underlying similarities exist from a memory organization perspective. Fig. 4 (b) shows the memory space for the neural stack. In contrast to LSTM, a neural stack can store more than one useful event in its external memory bank. ( In LSTM, if there is only one useful event, it can be stored as it is, but if there are multiple useful events, they have to be compressed into one compounded event and can only be accessed as a whole.) For example, at time t 0 , M 00 is saved in memory belt M 0, and at time t 2 , M 10 is saved in belt M 1. The black arrow on the left of the memory content points to the top of the stack in each time step. All these contents can be addressed as needed. For example, M 10 is used again at time t 4 after popping out M 20 in belt M 2. All the useful information of the input is retained with this external memory. In contrast to state memory, the previous content is not altered but is stored in its original or transformed form. As the past content and operations are separate, we can efficiently select the useful content from this structured memory rather than using the mixture of all previous content.

LSTM can be seen as a special case of a neural stack as proved in Theorem 2. In a neural stack, if all the contents in the stack below the topmost element are never addressed again, a single memory belt is sufficient. In this case, the neural stack degrades to LSTM, as shown in Fig. 4 (b) in the green dashed box. The stack operators (push, pop, no-operation) in the neural stack have the same function as the input and forget gates in LSTM: deciding how to revise the memory contents. The problem in LSTM is that the previous memory is erased after the update, which also occurs continuously with the vRNN state. Hence, both learning models have difficulties in performing some simple memorization tasks, such as reversing a sequence. However, the external memory bank in a neural stack can help to solve this problem via the online storage and extraction of more than one content. Although the neural stack can return to previous memory, two constraints exist. First, the neural stack cannot jump to any memory position: the previous memory must be addressed and updated sequentially. For example, as shown in the second line of Fig. 4 (b), if we want to return to the memory in belt M 1, we first have to pass the memory in belt M 2. Second, the memory content is forgotten after it is popped out of the stack. For example, at time t 4 , the memory in belt M 2 is popped out, so in the subsequent time steps, the content in belt M 2 can no longer be accessed and updated.

From the state transition analysis above, we can conclude that the stack neural network is the ideal choice for tasks where the previous memory must be addressed sequentially (first in last out). One solution to this difficulty is to read from and write to all the memory slots with different strengths. These strengths represent the probability that each slot is be read from and written to. Specifically, the reading vector at time step t is

EQUATION

)

where m is a memory bank with M memory slots, w r t (i) is the normalized reading weight for the ith slot at time t, which satisfies i w r t (i) = 1, 0 ≤ w r t (i) ≤ 1. In the writing process, each memory slot is updated as

EQUATION

EQUATION

) where w r t (i) is the writing weight, and e t (i) is the erasing weight for memory slot i at time t. The detailed calculations of these weights are presented in Appendix A.3. The dynamics of the hidden layer are

EQUATION

Fig. 5 (b) shows the memory structure of neural RAM. The RAM network can be seen as an improvement of the neural stack in the sense that all the contents in the memory bank can be read from and written to multiple times. Moreover, no requirements exist for the order of storing, updating and accessing the memory elements. For example, in Fig. 5(b) , at time t 0 , memory M 00 is stored in belt M 0; at time t 1 , the system control can directly jump to belt M 2 to store M 20. Additionally, the reading and writing slots can be different. For example, at t 1 , the network writes to belt M 2 and reads from M 0. The black arrows on the left of the contents in external memory represent the reading contents. This neural RAM network can degrade to a neural stack if the memory accessing order is restricted. Their relationship is stated in Theorem 3. Similarly, the network can degrade to LSTM if only one memory belt is used. The above analysis indicates that neural RAM is the most powerful network among the models discussed in this paper. Theorem 3. Neural RAM can degrade to a neural stack if i) all the reading weights except that of the topmost memory slot are set to zero, w r t (i) = 0, if i = 0; ii) only the writing weight for the topmost memory slot is learned, and all others are copied from it, w r t (i) = w r t (0), if i = 0; iii) in the writing process, instead of learning all the contents to be written to the stack, as in Eq.( 11), only the content of M0 is learned as c t (0) = t(w T hc h t-1 + b c ) + γm t-1 (1), and all other contents are calculated as c t (i) = m t-1 (i -1) + γm t-1 (i + 1), if i = 0.; iv) only the writing and erasing weights for the topmost element are learned, and all others are copied from the values of the topmost element, w r t (i) = w r t (0), e t (i) = e t (0).

Proof. See Appendix B.3.

5. MAPPING FROM NETWORK TYPES TO TASK TYPES:

From the analysis above, we know that the proposed taxonomy for the four most conventional memory architectures appears as a simple way to quantify the past information: state memory, memory of one compounded event, memory of multiple events with restricted access order, memory of multiple events with randomly access order. In this section, we will discuss how to utilize this proposed taxonomy to help practitioners select the right model.

The proposed taxonomy resembles the hierarchical organization of automata: vRNN⇔Finite state machine, neural stack⇔Deterministic pushdown automaton, neural RAM⇔Turing machine. Hence, if our task is sequence recognition or classification, the recognizable sequences for each network can be illustrated by the Chomsky hierarchy. However, these networks can perform additional sequence learning tasks, such as prediction. In this case, sequences do not need to satisfy the restricted grammars. For example, no need exists for the input sequences to always start from a start state and return to an accepted state. Hence, to ensure that our taxonomy fits these more general sequences, we have to analyze the memory requirements of the specific task first and match it with these four types of memory networks.

Four representative tasks that would fit optimally the characteristics of each memory organization are discussed here: counting, counting with interference, reversing and repeat copying. Therefore, practitioners can compare their own problem with these four tasks and get some hints to select the right model. We will analyze the memory requirements of each task individually.

Counting In the counting task, the input sequences are composed of a's, b's and c's. The output sequence is the cumulative count of the number of a's. For instance, when the input sequence is aaabcaa, the output sequence would be 1233345. For this type of sequence, a state variable is required to remember the number of a's. A state transition occurs when an a is encountered. In this problem, the state space is not very large, and a first-order Markov state model provides a sufficient description. Hence, the counting task can be completed as long as the network has one feedback loop. In this paper, "task can be completed" means the output error is almost zero.

Counting with interference In the counting with interference task, the input sequences are the same as those of the counting task. The goal is still to count the number of a's, but if a b or c is encountered, the output should be b or c. For example, if the input is aabbaca, the output sequence is 12bb3c4. For this type of problem, an external memory cache is required because the hidden layer's output (internal memory) is overwritten when a b or c is encountered. If we want to recall the number of a's, the value must be stored in external memory for future use, and an input gate must be used to protect the external memory when inputting b and c (g i = 1 when the input is a, and g i = 0 when the input is b or c). Thus, LSTM, neural stack and neural RAM are capable of solving this problem. However, in a vRNN, since the only memory is the state memory and the output is forced to be a function of this state memory, the interference of b and c prevent a vRNN from accomplishing this task.

Reversing The third task is sequence reversing. For example, if the input sequence is abacdeδxxxxxx, the output sequence should be xxxxxxxedcaba. δ is the delimiter symbol, and x represents any symbol. When δ is encountered in the input sequence, regardless of the subsequent symbols, the output is the input symbols before δ in reverse order. For this task, all the useful past information should be stored and then retrieved in reverse order. Hence, the memory must have the ability to store more than one element, and the reading order is related to the writing order. Since vRNN does not have a memory bank and LSTM's memory is forgotten after being updated, these two networks fail in this task. By contrast, the neural stack and neural RAM can both store more than one content and can solve this task, which satisfy the "first in last out" principle.

Repeat copying:

The most challenging task is repeat copying, where the output sequence is the input sequence repeated several times. For example, if the input sequence is adbcεxxxxxxxxxxxxxx, the output should be xxxxxxxadbcadbcadbc. That is, when the repeating number symbol ε is encountered, the output is the previous input sequence repeated ε times. For this type of task, more than one past content must be stored and retrieved multiple times, in this case, 3 times. Since all the saved information in a neural stack is forgotten after being popped out, a neural stack cannot perform this task; thus, only a neural RAM can complete this task.

This classification of tasks is meaningful since it can guide users in the right direction. If we select the wrong type of network, an error and/or speed penalty will occur regardless of how we adjust the hyperparameters. As shown in our experiment, for sequence reversing (i.e., the third type of task), neural stack and neural RAM with 6 hidden neurons converge to near zero error, but for vRNN and LSTM, even if we set the number of hidden neurons to 1000, the output will always fluctuate around a nonzero value.

6. EXPERIMENTS:

We test the performance of the four networks on the synthetic tasks described in last section to illustrate the impact of different memory organizations. We also visualize how each network encodes information to solve a problem in AppendixD. Then, we use two natural language processing applications to elaborate how to employ the knowledge gained from the different characteristics of the memory structures to help users to select the appropriate type of network. The details of parameters settings are given in AppendixC.

6.1 SYNTHETIC TASKS Figure 6 : Learning curves for four synthetic tasks

The learning curves for the four tasks when using different networks are shown in Fig. 6 . The performance is measured in terms of MSE for first two tasks and output entropy for the last two tasks. We use the same number of units in all the architectures to ensure a fair comparison. The results indicate that for counting, all four networks can achieve an almost zero error; for counting with interference, all the networks except vRNN can complete the task; for sequence reversing, neural stack and neural RAM are suitable networks; and for repeat copying, neural RAM is the only network that can solve the problem. We also apply different parameter settings, for instance, varying the number of hidden units from 5 to 1000. The performances are the same as shown in Fig. 6 , except a different nonzero error value is observed when the network is not capable of accomplishing the task.

6.2. NATURAL LANGUAGE PROCESSING:

Synthetic problems could be designed to exemplify the expressive power of the different memory networks. For real-world problems, this task is more complex because the memory requirements of the problem may be difficult to determine and the problem may be a blend of classes. In this case, all the networks may be able to solve the problem to a certain extent. Hence, in this section, we illustrate how to select the minimum network resources to accomplish the task with relatively good performance.

Sentiment analysis:

The first experiment is sentiment analysis to infer the emotional tone of a text as negative or positive. The sentiment of a text is mainly based on the occurrence and reoccurrence of some discriminating words. Specifically, if there are a lot of positive words, such as 'good, love' in the text, the sentiment of the text is always positive, and vice versa. Hence, external memory whose value is affected by these discriminating words is useful to judge the emotional tone of text. Thus LSTM, neural stack and neural RAM should perform better than vRNN. Since the goal is to classify the emotional tone as either 1 or 0, the specific contents of the text are not important and thus do not need to be all stored. For example, as long as it is a positive word, whether it is 'love''good' or 'like' is not very important. Hence, multi-slot memory which can store multiple contents does not have more advantages than the single-slot memory.

We test the network performance on the IMDb movie review dataset Pennington et al. (2014) . The results are presented in Table 2 , which shows that vRNN performs worst. LSTM, neural stack, and neural RAM have similar performances; thus, our analysis is verified.

Question answering:

The second experiment investigates the performance of these four networks on three question answering tasks from the bAbI datasetWeston et al. ( 2015). The target is to answer a question after reading a short story. For example, for the story "Mary got the milk there. John moved to the bedroom. Sandra went back to the kitchen. Mary travelled to the hallway.", and the question "Where is the milk?", the expected answer is "hallway". For this problem, to give the correct answer, the network must memorize the facts that Mary got the milk and traveled to the hallway. Additionally, since the does not know the question before reading the story, all the potentially useful facts must be stored. Thus, an external memory bank in which any content can be visited is useful. According to our memory capability analysis, the neural RAM should perform the best in this scenario. The results in Table 3 confirm that neural RAM achieves the best performance.

From the results we can see that, neural stack's performance is worse than LSTM. We know that both LSTM and neural stack are not suitable for this task. If we apply LSTM or neural stack to the problem, they will try their best to find their approximate solutions. If we apply LSTM to this task, LSTM would compress all the useful information in its external memory, although the right answer is mixed with other information, the output can at least get some information from it. However, if we apply neural stack to this task, the push signal sometimes is very large (d push ≈ 1, d pop ≈ 0, d no-op ≈ 0), which means that the right answer will then be pushed down in the stack which cannot be accessed when needed. Hence, we think although the neural stack attempts to find the right answer, it is more likely to be stuck in local points due to its complicated operation. But we have to be aware that it is not due to the memory limitation of stack itself, a better implementation of the three operators may help improve neural's stack performance for this kind of problem.

7. CONCLUSION:

In this paper, we analyze the memory structures of several recurrent networks and propose a taxonomy. We use four synthetic tasks and two natural language processing problems to illustrate utility of the taxonomy. Although we show differences in performance in the experiments, it is too early to say that we presented all the tools necessary to select the parsimonious memory architecture for a given application. Because the user has to analyze the requirements of the application, which may not be trivial, additionally work is needed to create guidelines to assist practitioners.

A NETWORK ARCHITECTURE COMPONENTS:

A.1 LSTM

The three gates are in LSTM are calculated as follows:

EQUATION

EQUATION

EQUATION

)

where w hgi , w hg f , w hgo are K h × 1 weights , w hgi , w hg f , w hgo are K i × 1 weights and b gi , b gi and b gi are bias. These three gates give flexibility to operate on memories.

A.2 NEURAL STACK:

Neural network interacts with the stack memory by d push t , d pop t , d no-op t , c t and r t . According to Sun (1993) the domain of the operations is relaxed to any real value in [0, 1]. This extension adds a continuous amplitude dimension to the operations. For example, if the push signal d push = 1, the current vector will be pushed into the stack as it is, if d push = 0.8, the current vector is first multiplied by 0.8 and then pushed into the stack.

d push t , d pop t , d no-op t

and c t are decided by the hidden layer outputs and the corresponding weights,

d = [d push t , d pop t , d no-op t ] T = s(w T hd h t + b op )

, where w hd is the K h × 3 weights and b op is the 3 × 1 bias.

c t = g(w T hc h t + b c )

, where w hc is the K h × N weights and b op is the N × 1 bias. Here we assume all the elements saved in the stack are N × 1 vectors.

A.3 NEURAL RAM:

In the neural RAM, the read weighting w r t (i) is learned as,

EQUATION

w ha is the K h × M weight and b a is M × 1 bias, w r t = [w r t (0), w r (1), ..., w r (M -1)] T The nonlinear activation function f is usually set as softmax function. The write weighting is learned as,

EQUATION

)

where

w hb is K h × M weight,w xb are K i × M weight, b b is M × 1 bias.

And the erase weighting is learned as,

EQUATION

where e t = [e t (1), e t (2), ..., e t (M )] T , w he is K h × M weights, w xe is K i × M weight, and b e are M × 1 bias. In practice, instead of learning the read and write head from scratch, some methods were proposed to simplify the learning process. For example in Neural Turing machine Graves et al. (2014) , e t (i) is coupled with write weight w w t (i), e t (i) = 1 -w w t (i). And reading weight w r t and writing weight w w t are obtained by content-addressing and location-addressing mechanisms. The content-addressing mechanism gives the weights w r t (i) (or w w t (i)) by checking the similarity of the key d with all the contents in the memory, the normalized version is,

w r t (i) = exp(αK[d, m t (i)]) j (exp(αK[d, m t (j)]))

,

where α is the parameter to control the precision of the focus, K is a similarity measure. Then, the weights will be further adapted by the location-addressing mechanism. For example, the weights obtained by content addressing can firstly blend with the previous weight and then shifted for several steps,

w r t (i) = g t w r t-1 (i) + (1 -g t )w r t (i), (20) w r t (i) = w r t ([i -n] M ).

(21) g t is the gate to balance the previous weight and current weight, n is the shifting steps, [i -n] M means the circular shift for M entities. Since the shifting operation is not differentiable, the method in Graves et al. (2014) should be utilized as an approximation.

Another example is Graves et al. (2016) which improves the performance even more. To be specific, for reading, a matrix to remember the order of memory locations they are written to can be introduced. With this matrix, the read weight is a combination of the content-lookup and the iterations through the memory location in the order they are written to. And for writing, a usage vector is introduced, which guides the network to write more likely to the unused memory. With this modification, the neural RAM gets flexibility similar to working memory of human cognition which makes it more suitable to intelligent prediction. With these modifications, the training time for the neural RAM is also reduced.

B THEOREM PROOFS B.1 PROOF OF THEOREM 1:

Compared to vRNN, LSTM introduces an external memory and the gate operation mechanism. So if we set the output gate g o = 0, input gate g i = 1 and the forget gate g f = 0 instead of learning from the sequences, the dynamics of LSTM is degraded to vRNN as follows,

EQUATION

Here ( 23) is due to g o = 0, (24) is due to g i = 1 and g f = 0, (26) is because the weight w hc and bias b c are set as constants and the activation function t(x) is set as linear activation function,

w hc = I, b c = 0, t 1 (x) = x.

Since Eq.( 22) is the dynamic of LSTM and Eq.( 26) is the dynamic of vRNN, the argument that vRNN is a special case of LSTM is proved.

B.2 PROOF OF THEOREM 2:

The dynamic of LSTM is,

EQUATION

And the dynamic of neural stack is,

EQUATION

According to Eq.( 27) and Eq.( 28), the dynamics of the neural stack have similar form as LSTM except for the reading vector, i.e., the reading vector is r t = g o s t (0). If we set the pop signal as zero, d pop t = 0, and no operation on the stack contents except for the topmost elements is available, then

s t (0) = d push t c + d no-op t s t-1 (0), s t (i) = 0, if i = 0.

Since the d push t , d no-op t are calculated in the same way the input gate g i,t and forget gate g f,t are calculated in LSTM as shown in Eq.( 14) to Eq.( 15), the read vector would be,

r t = g o s t (0) = g o (d push t c + d no-op t s t-1 (0))

In this manner, this is exactly how the LSTM organizes its memory,

r t = g o (g i,t c + g f,t s t-1 (0)) d push t

can be seen as the input gate and d no-op t can be seen as the forget gate. Hence, it is proved that LSTM can be seen as a special case of neural stack.

B.3 PROOF OF THEOREM 3:

Neural RAM is more powerful than neural stack because it has access to all the contents in the memory bank. If we restrict the read and write vector, neural RAM is degraded to neural stack. To be specific, for the read head w r t , all the read weights except the topmost are set to zeros,

EQUATION

here w ha is K h × 1 vector and b a is the scalar. Eq.( 29) is a special case of Eq.( 17).

EQUATION

all others are calculated as,

EQUATION

And in the writing process, Eq.( 30), Eq.( 31) can be seen as a special case of Eq.( 11) because h t-1 in ( 11) is a function of m t-1 . Substitute (30)(31) into the memory update equation of neural RAM (12), we get,

EQUATION

Finally since Eq.( 3) and Eq.( 3) can be seen as a special case of Eq.( 18) and Eq.( 19), the neural stack can be treated as a special case of neural RAM. Compared the memory writing operation of neural stack (7) and neural RAM (32), we can see that, w w t (0), γw w t (0) and e t (0) works as the push, pop and no-operate operations respectively. Compared the memory reading operation of neural stack and neural RAM, we can see that we can see that, w r t (0) in neural RAM (29) works as the output gate in neural stack (9).

C EXPERIMENT PARAMETERS SETTING C.1 COUNTING AND COUNTING WITH INTERFERENCE:

In the experiment, the activation function is Relu in vRNN. In LSTM, the external memory's content is initialized as zero. In the neural stack, the push, pop and no-op operations are initialized as random numbers with mean 0 and variance 1. At first, there is only one content in the stack which is initialized as zero. The depth of the stack can increase to any number as required. In neural RAM, memory depth is set as M = 3. In LSTM, neural stack and neural RAM, memory width is set as N = 3, the nonlinear activation functions for all the gates are sigmoid functions and others are tanh. The number of input neurons, hidden neurons and output neurons are 3. All the weights are initialized as random numbers with mean 0 and variance 1, all the bias are initialized as 0.1. For counting task, the model is trained with the synthetic sequences up to length 20. When the input is a, the first elements in the output vector would add one, otherwise, the output vector is unchanged. After encoding, the input and output vectors are, time step input sequence output sequence 1

[1 0 0] [1 0 0] 2 [1 0 0] [2 0 0] 3 [0 1 0] [2 0 0] 4 [0 1 0] [2 0 0] 5 [1 0 0] [3 0 0] 6 [0 0 1] [3 0 0] 7 [1 0 0] [4 0 0]

For counting with interference task, after encoding, the input and output vectors are, into M 1 to M 5 are never used again. Fig. 10 shows the memory contents of the neural RAM and the corresponding operations of it. From Fig. 10 (a), we can see that M 0, M 1 and M 2 cooperate to learn the pattern. When a is received, the values in M 0, M 1 and M 2 are increased. The read weights for M 0, M 1 and M 2 are all around 0.3 as shown in Fig.10(b) . From this experiment we can see that M 1 and M 2 are redundant here. The experiment settings are same as "counting" task. Fig. 11 to Fig. 13 shows the memory usage of LSTM, neural stack and neural RAM. Fig. 11 shows that when a is received, the third element of the memory content would increase by around 0.2. 

D.4 REPEAT COPYING:

Since neural RAM is the only network that can handle this problem, Fig. 16 shows how the neural RAM solves this problem. From the writing weights we can see that, the starting symbol is saved in M0, and symbols needed to be repeated are save in M2, M4, M6, M9. After t=4, the network would read from M2/M5, M4,M6,M9. At the beginning of every loop, the network reads from both M2 and M5 probably because the repeating time symbol δ is saved in M5. The value in M5 can tell the

:



Figures and Tables:

Figure 1: Memory Network Taxonomy In this section, we organize these popular dynamical networks according to their underlying memory structures. We classify them into four classes as shown in Fig.1, i.e., vRNN⊆ LSTM⊆neural stack⊆neural RAM. Some classes are named after a typical model. For example, the vRNN class also includes IRNN Le et al. (2015) and the highway network Srivastava et al. (2015), and the LSTM class also includes GRU Cho et al. (2014) and the peephole network Gers & Schmidhuber (2000). The neural stack class includes the architecture in Sun (1993); Sun et al. (2017); Joulin & Mikolov (2015); Grefenstette et al. (2015), and the neural RAM class includes NTM Graves et al. (2014), DNC Graves et al. (2016), enhanced LSTM Graves (2013) and Weston et al. (2014).

Figure 2: vRNN

Figure 3: LSTM: The blue belt, M 0, represents the external memory. At t 1 , memory M 00 is generated and stored; at time t 9 , M 00 is updated to M 01. The black dashed arrows represent the effect of the current state on the external memory. The state index is also the time index.

Figure 4: Neural stack: the network first saves state M 00 in belt M 0 and updates it to M 01. At time t 2 , instead of replacing M 01 with a new state M 10, a new belt M 1 is created to save M 10. In this way, both M 01 and M 10 are kept. Similarly, at time t 5 , M 30 is saved in another belt M 3. At time t 5 , the content in the stack is M 01, M 11, and M 30, where M 30 is the topmost element.

Figure 5: Neural RAM

Figure 7: Task1: vRNN: Internal memory content

Figure 10: Task1: Neural RAM: Memory bank content and corresponding read and write operation

Memory types of networks

Table content: <table><tr><td>Networks</td><td>Memory type</td><td/></tr><tr><td>vRNN</td><td>state memory</td><td>internal memory</td></tr><tr><td>LSTM</td><td>memory of a single compounded event at a time</td><td>external memory</td></tr></table>



Table content: <table><tr><td/><td/><td/><td colspan="2">: Average error for movie review</td></tr><tr><td/><td colspan="4">vRNN LSTM neural Stack neural RAM</td></tr><tr><td colspan="3">error rate 31±5 19±2.5</td><td>23±10</td><td>20±9</td></tr><tr><td/><td/><td colspan="3">Table 3: Average error for three tasks from bAbI tasks</td></tr><tr><td>Task</td><td>vRNN</td><td>LSTM</td><td colspan="2">neural Stack neural RAM</td></tr><tr><td colspan="3">task 1 52±1.5 28.4±1.5</td><td>41±2.0</td><td>9.0±12.6</td></tr><tr><td colspan="3">task 2 79±2.5 56.0±1.5</td><td>75±6</td><td>39.2±20.5</td></tr><tr><td colspan="3">task 3 85±2.5 51.3±1.4</td><td>78±6.4</td><td>39.6±16.4</td></tr></table>

Peer review (iclr2019):
 Summary ========= The paper analyses the taxonomy over memory-based neural networks, in the decreasing order of capacity: Neural RAM to Neural Stack, Neural Stack to LSTM and LSTM to vanilla RNN. The experiments with synthetic and NLP datasets demonstrate the benefits of using models that fit with task types. Comment ======== Overall, the paper is well written and presents interesting analysis of different memory architectures. However, the contribution is rather limited. The proposed taxonomy is not new. It is a little bit obvious and mentioned before in [1] (Unfortunately, this was not cited in the manuscript). The theorems on inclusion relationship are also obvious and the main contribution of the paper is to formally show that in mathematical forms. The experiments on synthetic tasks give some insights into the models’ operations, yet similar analyses can be found in [2, 3]. To verify the models really learn the task, the authors should include tests on unseen sequence lengths. There remains questions unexplained in NLP tasks such as why multi-slot memory did not show more advantages in Movie Review and why Neural Stack performed worse than LSTM in bAbI data. Minor potential errors: In Eq. (6), r_{t-1} should be r_t The LSTM presented in Section 3.2 is not the common one. Normally, there should be x_t term in Eq. (3) and h_t=g_{o,t}*.tanh(r_t) in Eq. (6). The author should follow the common LSTM formulas (which may lead to different proofs) or include reference to their LSTM version. [1] Yogatama et al. Memory Architectures in Recurrent Neural Network Language Models. ICLR’18 [2] Joulin et al. Inferring algorithmic patterns with stack-augmented recurrent nets. NIPS’15 [3] Graves et al. Neural Turing Machines. arXiv preprint arXiv:1410.5401 (2014).