Year: 2018

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 RELATED WORK
text: 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.

heading: 3 A MEMORY NETWORK TAXONOMY
text: 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).
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.
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.

heading: 4 MEMORY STRUCTURE ANALYSIS
text: 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.
4.1 VRNN
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
ht = f(w T xhxt +w T hhht−1 + bh), (1)
ot = f(w T hoht + bo), (2)
where xt, ht and ot 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 ht, 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 t0, t1, ..., t4, 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.

heading: 4.2 LSTM
text: 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 mt,
ct = f(w T hcht + bc), (3)
mt = gi,tct + gf,tmt−1, (4)
rt = mt, (5)
ht = f(w T xhxt +w T rhgo,trt−1 + bh), (6)
where ht (or ct) is the network state. The external memory mt is a combination of mt−1 and the current state ct. If gi,t = 0 and gf,t = 1 for several successive time steps, the content saved in the external memory mt would constitute the long-term memory of the system.
The external memory mt adds greater flexibility to the state transition diagram. As shown in Fig.3(b), the current state st (represented by hidden state ht) depends on either the previous state st−1 or the external memory mt−1 (if forget gate gf,t = 0 and input gate gi,t = 1, st depends on st−1; if gf,t = 1 and gi,t = 0, st depends on mt−1; if 0 < gf,t < 1 and 0 < gi,t < 1, st depends on both mt−1 and st−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 M00, as illustrated by the yellow arrows; and s9 depends on both the previous state s8 and the long-term memory M00. 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 st = f(st−1, st−10), a vRNN has to learn a state space with 210 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., go = 0, gi = 1 and gf = 0; ii) weight whc and bias bc are set to constants, i.e., whc = I and bc = 0; iii) the activation function t(x) is a linear activation function, i.e., t1(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., st = f(st−1, st−2, ..., st−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 t9, 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.

heading: 4.3 NEURAL STACK
text: 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:
st(i) =
{ dpusht c+ d pop t st−1(1) + d no−op t st−1(0), if i = 0,
dpusht st−1(i− 1) + d pop t st−1(i+ 1) + d no−op t st−1(i), otherwise,
(7)
st(i) is the content of the stack at time t in position i. st(0) is the topmost content at time t, c is the candidate content to be pushed onto the stack, and dpusht , dpopt and d no−op t are the push, pop and no-operation signals. All operations have to be implemented by continuous functions over a continuous domain to train the network with backpropagation through time. The calculation details of the stack contents and the corresponding operators are given in Appendix A.2. Since recurrence is introduced by stack memory, the dynamics of the model are
ht = g(w T xhxt +w T rhrt + bh), (8)
where rt is the vector read at time t,
rt = gost(0). (9)
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 t0, M00 is saved in memory belt M0, and at time t2, M10 is saved in
belt M1. 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, M10 is used again at time t4 after popping out M20 in belt M2. 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. Theorem 2. The neural stack can degrade to LSTM if the pop signal is zero, i.e., dpopt = 0. The dpusht in a neural stack works as the input gate in LSTM, and d no−op t in a neural stack works as the forget gate in LSTM.
Proof. See Appendix B.2.
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 M1, we first have to pass the memory in belt M2. Second, the memory content is forgotten after it is popped out of the stack. For example, at time t4, the memory in belt M2 is popped out, so in the subsequent time steps, the content in belt M2 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).

heading: 4.4 NEURAL RAM
text: Dynamic neural networks with external random access memory have recently been studied. In these networks, all the contents in the memory bank can be randomly accessed. The neural Turing machine Graves et al. (2014) (NTM), whose network architecture is shown in Fig.5(a), is one example. The challenge with this network is that all the memory addresses are discrete in nature. To learn, read and write addresses by error backpropagation, the addresses have to be extended to continuous domain.
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
rt = M−1∑ i=0 wrt (i)mt(i), (10)
where m is a memory bank with M memory slots, wrt (i) is the normalized reading weight for the ith slot at time t, which satisfies ∑ i wrt (i) = 1, 0 ≤ wrt (i) ≤ 1. In the writing process, each memory slot is updated as
ct = f(w T hcht + bc), (11)
mt(i) = w w t (i)ct(i) + et(i)mt−1(i),∀i (12) where wrt (i) is the writing weight, and et(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
ht = f(w T xhxt +w T rhrt−1 + bh), (13)
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 t0, memory M00 is stored in belt M0; at time t1, the system control can directly jump to belt M2 to store M20. Additionally, the reading and writing slots can be different. For example, at t1, the network writes to belt M2 and reads from M0. 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, wrt (i) = 0, if i 6= 0; ii) only the writing weight for the topmost memory slot is learned, and all others are copied from it, wrt (i) = w r t (0), if i 6= 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 ct(0) = t(w ′T hcht−1 + bc) + γmt−1(1), and all other contents are calculated as ct(i) = mt−1(i− 1) + γmt−1(i+ 1), if i 6= 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, wrt (i) = w r t (0), et(i) = et(0).
Proof. See Appendix B.3.

heading: 5 MAPPING FROM NETWORK TYPES TO TASK TYPES
text: 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 (gi = 1 when the input is a, and gi = 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.

heading: 6 EXPERIMENTS
text: 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.

heading: 6.1 SYNTHETIC TASKS
text: 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.

heading: 6.2 NATURAL LANGUAGE PROCESSING
text: 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 (dpush ≈ 1, dpop ≈ 0, dno−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.

heading: 7 CONCLUSION
text: 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.

heading: A NETWORK ARCHITECTURE COMPONENTS

heading: A.1 LSTM
text: The three gates are in LSTM are calculated as follows:
gi,t = s(w T hgiht−1 +w T xgixt + bgi), (14)
gf,t = s(w T hgf ht−1 +w T xgf xt + bgf ), (15)
go,t = s(w T hgoht−1 +w T xgoxt + bgo). (16)
where whgi , whgf , whgo are Kh × 1 weights , whgi , whgf , whgo are Ki × 1 weights and bgi , bgi and bgi are bias. These three gates give flexibility to operate on memories.

heading: A.2 NEURAL STACK
text: Neural network interacts with the stack memory by dpusht , d pop t , d no−op t , ct and rt. 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 dpush = 1, the current vector will be pushed into the stack as it is, if dpush = 0.8, the current vector is first multiplied by 0.8 and then pushed into the stack.
dpusht , d pop t , d no−op t and ct are decided by the hidden layer outputs and the corresponding weights,
d = [dpusht , d pop t , d no−op t ] T = s(wThdht + bop),
where whd is the Kh × 3 weights and bop is the 3× 1 bias.
ct = g(w T hcht + bc),
where whc is the Kh ×N weights and bop is the N × 1 bias. Here we assume all the elements saved in the stack are N × 1 vectors.

heading: A.3 NEURAL RAM
text: In the neural RAM, the read weighting wrt (i) is learned as,
wrt = f(w T haht−1 + br), (17)
wha is the Kh ×M weight and ba is M × 1 bias, wrt = [wrt (0), wr(1), ..., wr(M − 1)]T The nonlinear activation function f is usually set as softmax function. The write weighting is learned as,
wwt = s(w T hbht−1 +w T xbxt + bw). (18)
where whb is Kh ×M weight,wxb are Ki ×M weight, bb is M × 1 bias. And the erase weighting is learned as,
et = s(w T heht−1 +w T xext + be), (19)
where et = [et(1), et(2), ..., et(M)]T, whe is Kh ×M weights, wxe is Ki ×M weight, and be 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), et(i) is coupled with write weight wwt (i), et(i) = 1− wwt (i). And reading weight wrt and writing weight wwt are obtained by content-addressing and location-addressing mechanisms. The content-addressing mechanism gives the weights wrt (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,
wrt (i) = exp(αK[d,mt(i)])∑ j(exp(αK[d,mt(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,
wrt (i) = gtw r t−1(i) + (1− gt)wrt (i), (20)
wrt (i) = w r t ([i− n]M ). (21)
gt 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.

heading: B THEOREM PROOFS

heading: B.1 PROOF OF THEOREM 1
text: Compared to vRNN, LSTM introduces an external memory and the gate operation mechanism. So if we set the output gate go = 0, input gate gi = 1 and the forget gate gf = 0 instead of learning from
the sequences, the dynamics of LSTM is degraded to vRNN as follows,
ht = t(w T xhxt +w T rhgort + bh) (22)
= t[wTxhxt +w T rhrr + bh] (23)
= t[wTxhxt +w T rhmt + bh]
= t[wTxhxt +w T rh(gict + gfmt−1) + bh]
= t(wTxhxt +w T rhct + bh) (24)
= t[wTxhxt +w T rht1(w T hcht−1 + bc) + bh] (25)
= t(wTxhxt +w T rhht−1 + bh) (26)
Here (23) is due to go = 0, (24) is due to gi = 1 and gf = 0, (26) is because the weight whc and bias bc are set as constants and the activation function t(x) is set as linear activation function,
whc = I,
bc = 0,
t1(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.

heading: B.2 PROOF OF THEOREM 2
text: The dynamic of LSTM is, ht = f(w T xhxt +w T rhgo,trt + bh), (27)
And the dynamic of neural stack is,
ht = g(w T xhxt +w T rhrt + bh), (28)
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 rt = gost(0). If we set the pop signal as zero, dpopt = 0, and no operation on the stack contents except for the topmost elements is available, then
st(0) = d push t c+ d no−op t st−1(0),
st(i) = 0, if i 6= 0.
Since the dpusht , d no−op t are calculated in the same way the input gate gi,t and forget gate gf,t are calculated in LSTM as shown in Eq.(14) to Eq.(15), the read vector would be,
rt = gost(0)
= go(d push t c+ d no−op t st−1(0))
In this manner, this is exactly how the LSTM organizes its memory,
rt = go(gi,tc+ gf,tst−1(0))
dpusht 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.

heading: B.3 PROOF OF THEOREM 3
text: 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 wrt , all the read weights except the topmost are set to zeros,
wrt (i) = { 0, if i 6= 0 t(w
′T haht−1 + ba), if i = 0
, (29)
here w′ha is Kh × 1 vector and ba is the scalar. Eq.(29) is a special case of Eq.(17).
ct(0) = t(w ′T hcht−1 + bc) + γmt−1(1), (30)
all others are calculated as,
ct(i) = mt−1(i− 1) + γmt−1(i+ 1), if i 6= 0. (31)
And in the writing process, Eq.(30), Eq.(31) can be seen as a special case of Eq.(11) because ht−1 in (11) is a function of mt−1. Substitute (30)(31) into the memory update equation of neural RAM (12), we get,
m t (i) = wwt (i)ct(i) + et(i)mt−1(i)
=  wwt (i)t(w ′T hcht−1 + bc)+ γwwt (i)mt−1(1) + et(i)mt−1(i), ifi = 0 wwt (i)mt−1(i− 1)+
γwwt (i)mt−1(i+ 1)ct(i) + et(i)mt−1(i), otherwise
=  wwt (i)t(w ′T hcht−1 + bc)+ γwwt (i)mt−1(1) + et(i)mt−1(i), ifi = 0 wwt (i)mt−1(i− 1)+
γwwt (i)mt−1(i+ 1)ct(i) + et(i)mt−1(i), otherwise
(32)
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, wwt (0), γw w t (0) and et(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, wrt (0) in neural RAM (29) works as the output gate in neural stack (9).

heading: C EXPERIMENT PARAMETERS SETTING

heading: C.1 COUNTING AND COUNTING WITH INTERFERENCE
text: 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,
time step input sequence output sequence 1 [1 0 0] [1 0 0] 2 [1 0 0] [2 0 0] 3 [0 1 0] [0 1 0] 4 [0 1 0] [0 1 0] 5 [1 0 0] [3 0 0] 6 [0 0 1] [0 0 1] 7 [1 0 0] [4 0 0]

heading: C.2 REVERSING AND REPEAT COPYING
text: Some network settings are different from the first two experiments. In vRNN, the activation function in the hidden layer is sigmoid function since we use entropy instead of mean square error as the cost function. In neural RAM, the word size and memory depth are set as 16. The length of read and write vectors are also set as 16. The number of input neurons, hidden neurons and output neurons are 6, 64, 6. The model is trained with sequences up to length 20. In repeat copying experiment, the training sequences are composed of a starting symbol , some symbols in set {a, b, c, d, e} followed by a repeating number symbol δ and some random symbols. , a, b, c, d, e are one-hot encoded with on value 1 and off value 0; δ is encoded with on value n and off value 0, n is the repeating number.

heading: C.3 SENTIMENT ANALYSIS
text: In our experiments, the number of input neurons, hidden neurons and output neurons are 50, 64, 2 for all the four network architectures. After encoding all the words into vectors, they are fed into the network one by one. Here we use a pretrained model: GloVe Pennington et al. (2014) to create our word vector. The matrix contains 400,000 word vectors, each with a dimensionality of 50. The matrix is created in a way that words having similar definitions or context reside in the relatively same position in the vector space. The decision of the tone of the paragraph will be made at the end of the paragraph. The output is [1, 0] for the positive text and [0, 1] for the negative text. The dataset adopted here is the lmdb movie review dataMaas et al. (2011) which has 12500 positive reviews and 12500 negative reviews. Here we use 11500 reviews for training and 1000 data for testing. In our experiments, the nonlinear activation functions for all the gates are sigmoid. The activation functions at the output layer are sigmoid and others are tanh. In neural RAM, the word size and memory depth are set as 64. The number of read and write head are 4 and 1. The results are average of 20 runs with random initializations.

heading: C.4 QUESTION ANSWERING
text: For each task, we use the 10,000 questions to train and report the error rates on the test set. The experimental settings for LSTM and neural RAM are the same as Graves et al. (2016) and the results for these two networks are from Graves et al. (2016). In vRNN and neural stack, the nonlinear activation functions for all the gates are sigmoid. The activation functions at the output layer are sigmoid and others are tanh. The number of input neurons, hidden neurons and output neurons are 150, 64, 150. The memory width for neural stack is 64.

heading: D MEMORY WORKING PROCESS VISUALIZATION FOR THE SYNTHETIC TASKS

heading: D.1 COUNTING
text: Fig.7 to Fig.10 show the details of the memory contents after the models are well-trained. They are tested on a input sequence bbacacbabababcc. The little checks on the left side of each image mark the memories which affect the output results. In Fig.7, when a is received, the first element of the hidden layer is increased by 1. In Fig.8, when a is received, the first element of M0 is decreased by around 0.15. As long as there is at least one element (h0 in vRNN and the first element of M0 in LSTM) in the memory learning the pattern, after multiplying with the weight vector, the output of the network can give the expected values. Fig.9 shows how the neural stack uses its memory. Although the neural stack has the potential to use unbounded number of stack contents, it only uses the topmost content (M0) here, i.e. the push and no-operation cooperate to learn the pattern. The contents pushed
into M1 to M5 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 M0, M1 and M2 cooperate to learn the pattern. When a is received, the values in M0, M1 and M2 are increased. The read weights for M0, M1 and M2 are all around 0.3 as shown in Fig.10(b). From this experiment we can see that M1 and M2 are redundant here.

heading: D.2 COUNTING WITH INTERFERENCE
text: 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. Fig.12 and Fig.13 also show the similar incremental patterns of neural stack and neural RAM. An notable difference between Fig.11-Fig.12 and Fig.8-Fig.9 is the usage of the memory. When dealing with counting task, the output gates are always 1, however, when dealing with counting with interference task, the output gates are 0 when inputting b and c, this helps to cut off the interference from the memory. Similarly, the read vector
are always around [0.3, 0.3, 0.3] in Fig.10, however, in Fig.13, the read vector’s elements are almost zeros when encountering b and c. The read vector here works as the output gate in LSTM and neural stack. It also shows why neural RAM does not need an output gate.

heading: D.3 REVERSING
text: Fig.14 shows how neural stack utilizes its stack memory to solve this problem. Since each memory bank’s word size is 16, here we only use colors instead of the specific numbers to show the values of contents in memory. Different from the first two tasks, the function of the stack is finally exploited. In the first half sequence, the input symbols are encoded as 16-elements vectors and pushed into the stack. In the second half of the sequence, the contents in the stack are popped out sequentially. It should be noticed that as long as the contents are popped out, they can not be revisited anymore. Different from neural stack, the contents in neural stack are never wiped as shown in Fig.15. The contents in the memory bank are only wiped if they are useless in the future or they have to be wiped
to make space for new stuffs. Another feature of the memory bank for neural RAM is the memory banks are not used in order such as M0, M1, M2...In this example, the memory banks are used in the order M0, M2, M7, M13.... But as long as the network knows the writing order, the task can be accomplished. Fig15(b)(c) shows the reading and writing weights, we can see that the second half of the reading weights is the mirror of the first half of the sequence of the writing weights, which means the network learns to reverse.

heading: D.4 REPEAT COPYING
text: 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
network whether to continue repeating or not. We can see from Fig.16(b), at time t=22, after reading from M2 and M5, the network stops reading from M4 to M9 and turns to M0.

Review summaries:
The authors propose a review-style overview of memory systems within neural networks, from simple RNNs to stack-based memory architectures and NTM / MemNet-style architectures. They propose some reductions to imply how one model can be used (or modify) to simulate another. They then make predictions about which type of models should be best on different types of tasks.