$\left\\{1,5,10\right\\}$, respectively. The metric used to measure the
performance is the average accuracy across decoding steps. For each
configuration of hyper-parameters, we run the experiment 5 times and report
the mean accuracy with error bars.

Figs. 6.2(a) and (c) depict the performance of UW and regular writing under
different configurations. In any case, UW boosts the prediction accuracy of
MANNs. The performance gain can be seen clearly when the compression ratio is
between $10-40\%$. This is expected since when the compression ratio is too
small or too big, UW converges to regular writing. Interestingly, increasing
the memory size does not always improve the performance, as in the case of NTM
with RNN controllers. Perhaps, learning to attend to many memory slots is
tricky for some task given limited amount of training data. This supports the
need to apply UW to MANN with moderate memory size. We also conduct
experiments to verify the benefit of using UW for bigger memory. The results
can be found in Appendix D.8.

We also measure the speed-up of training time when applying UW on DNC and NTM,
which is illustrated in Figs. 6.2(b) and (d). The result shows that with UW,
the training time can drop up to $60\%$ for DNC and $28\%$ for NTM,
respectively. As DNC is more complicated than NTM, using UW to reduce memory
access demonstrates clearer speed-up in training (similar behavior can be
found for testing time).

####  6.5.2 Synthetic Memorisation

Here we address a broader range of baselines on two synthetic memorisation
tasks, which are the sequence copy and reverse. In these tasks, there is no
discrimination amongst timesteps so the model’s goal is to learn to compress
the input efficiently for later retrieval. We experiment with different
sequence lengths of 50 and 100 timesteps. Other details are the same as the
previous double task except that we fix the learning rate and gradient
clipping to 0.001 and 10, respectively. The standard baselines include LSTM,
NTM and DNC. All memory-augmented models have the same memory size of $4$
slots, corresponding to compression ratio of $10\%$ and $5\%$, respectively.
We aim at this range of compression ratio to match harsh practical
requirements. UW and CUW (cache size $L=5$) are built upon the DNC, which from
our previous observations, works best for given compression ratios. We choose
different dimensions $N_{h}$ for the hidden vector of the controllers to
ensure the model sizes are approximately equivalent. To further verify that
our UW is actually the optimal writing strategy, we design a new baseline,
which is DNC with random irregular writing strategy (RW). The write is sampled
from a binomial distribution with $p=\left(D+1\right)/T$ (equivalent to
compression ratio). After sampling, we conduct the training for that policy.
The final performances of RW are taken average from 3 different random
policies’ results.

The performance of the models is listed in Table 6.1. As clearly seen, UW is
the best performer for the pure memorisation tests. This is expected from the
theory as all timesteps are importantly equivalent. Local attention mechanism
in CUW does not help much in this scenario and thus CUW finishes the task as
the runner-up. Reverse seems to be easier than copy as the models tend to
“remember” more the last-seen timesteps whose contributions $\lambda^{T-t}$
remains significant. In both cases, other baselines including random irregular
and regular writing underperform our proposed models by a huge margin.

Model | $N_{h}$ | # parameter | Copy | Reverse
---|---|---|---|---
L=50 | L=100 | L=50 | L=100
LSTM | 125 | 103,840 | 15.6 | 12.7 | 49.6 | 26,1
NTM | 100 | 99,112 | 40.1 | 11.8 | 61.1 | 20.3
DNC | 100 | 98,840 | 68.0 | 44.2 | 65.0 | 54.1
DNC+RW | 100 | 98,840 | 47.6 | 37.0 | 70.8 | 50.1
DNC+UW | 100 | 98,840 | 97.7 | 69.3 | 100 | 79.5
DNC+CUW | 95 | 96,120 | 83.8 | 55.7 | 93.3 | 55.4
Table 6.1: Test accuracy (%) on synthetic memorisation tasks. MANNs have 4
memory slots.

####  6.5.3 Synthetic Reasoning

Tasks in the real world rarely involve just memorisation. Rather, they require
the ability to selectively remember the input data and synthesise intermediate
computations. To investigate whether our proposed writing schemes help the
memory-augmented models handle these challenges, we conduct synthetic
reasoning experiments which include add and max tasks. In these tasks, each
number in the output sequence is the sum or the maximum of two numbers in the
input sequence. The pairing is fixed as:
$y_{t}=\frac{x_{t}+x_{T-t}}{2},t=\overline{1,\left\lfloor\frac{T}{2}\right\rfloor}$
for add task and
$y_{t}=\max\left(x_{2t},x_{2t+1}\right),t=\overline{1,\left\lfloor\frac{T}{2}\right\rfloor}$
for max task, respectively. The length of the output sequence is thus half of
the input sequence. A brief overview of input/output format for these tasks
can be found in Appendix D.7. We deliberately use local (max) and distant
(add) pairing rules to test the model under different reasoning strategies.
The same experimental setting as in the previous section is applied except for
the data sample range for the max task, which is $\left[1,50\right]$444With
small range like $\left[1,10\right]$, there is no much difference in
performance amongst models. LSTM and NTM are excluded from the baselines as
they fail on these tasks.

Table 6.2 shows the testing results for the reasoning tasks. Since the memory
size is small compared to the number of events, regular writing or random
irregular writing cannot compete with the uniform-based writing policies.
Amongst all baselines, CUW demonstrates superior performance in both tasks
thanks to its local attention mechanism. It should be noted that the timesteps
should not be treated equally in these reasoning tasks. The model should
weight a timestep differently based on either its content (max task) or
location (add task) and maintain its memory for a long time by following
uniform criteria. CUW is designed to balance the two approaches and thus it
achieves better performance. Further insights into memory operations of these
models are given in Appendix D.9.

Model | Add | Max
---|---|---
L=50 | L=100 | L=50 | L=100
DNC | 83.8 | 22.3 | 59.5 | 27.4
DNC+RW | 83.0 | 22.7 | 59.7 | 36.5
DNC+UW | 84.8 | 50.9 | 71.7 | 66.2
DNC+CUW | 94.4 | 60.1 | 82.3 | 70.7
Table 6.2: Test accuracy (%) on synthetic reasoning tasks. MANNs have 4 memory
slots.

####  6.5.4 Synthetic Sinusoidal Regression

In real-world settings, sometimes a long sequence can be captured and fully
reconstructed by memorising some of its feature points. For example, a
periodic function such as sinusoid can be well-captured if we remember the
peaks of the signal. By observing the peaks, we can deduce the frequency,
amplitude, phase and thus fully reconstructing the function. To demonstrate
that UW and CUW are useful for such scenarios, we design a sequential
continuation task, in which the input is a sequence of sampling points across
some sinusoid: $y=5+A\sin(2\pi fx+\varphi)$. Here,
$A\sim\mathcal{U}\left(1,5\right)$, $f\sim\mathcal{U}\left(10,30\right)$ and
$\varphi\sim\mathcal{U}\left(0,100\right)$. After reading the input
$y=\left\\{y_{t}\right\\}_{t=1}^{T}$, the model have to generate a sequence of
the following points in the sinusoid. To ensure the sequence $y$ varies and
covers at least one period of the sinusoid, we set
$x=\left\\{x_{t}\right\\}_{t=1}^{T}$ where
$x_{i}=\left(t+\epsilon_{1}\right)/1000$,
$\epsilon_{1}\sim\mathcal{U}\left(-1,1\right)$. The sequence length for both
input and output is fixed to $T=100$. The experimental models are LSTM, DNC,
UW and CUW (built upon DNC). For each model, optimal hyperparameters including
learning rate and clipping size are tuned with 10,000 generated sinusoids. The
memories have $4$ slots and all baselines have similar parameter size. We also
conduct the experiment with noisy inputs by adding a noise
$\epsilon_{2}\sim\mathcal{U}\left(-2,2\right)$ to the input sequence $y$. This
increases the difficulty of the task. The loss is the average of mean square
error (MSE) over decoding timesteps.

We plot the mean learning curves with error bars over 5 runnings for
sinusoidal regression task under clean and noisy condition in Figs. 6.3(a) and
(b), respectively. Regular writing DNC learns fast at the beginning, yet soon
saturates and approaches the performance of LSTM ($MSE=1.05$ and $1.39$ in
clean and noisy condition, respectively). DNC performance does not improve
much as we increase the memory size to $50$, which implies the difficulty in
learning with big memory. Although UW starts slower, it ends up with lower
errors than DNC and perform slightly better than CUW in clean condition
($MSE=0.44$ for UW and $0.61$ for CUW). CUW demonstrates competitive
performance against other baselines, approaching to better solution than UW
for noisy task where the model should discriminate the timesteps ($MSE=0.98$
for UW and $0.55$ for CUW). More visualisations can be found in Appendix D.10.

Figure 6.3: Learning curves of models in clean (a) and noisy (b) sinusoid
regression experiment.

####  6.5.5 Flatten Image Recognition

We want to compare our proposed models with DNC and other methods designed to
help recurrent networks learn longer sequence. The chosen benchmark is a
pixel-by-pixel image classification task on MNIST in which pixels of each
image are fed into a recurrent model sequentially before a prediction is made.
In this task, the sequence length is fixed to 768 with highly redundant
timesteps (black pixels). The training, validation and testing sizes are
50,000, 10,000 and 10,000, respectively. We test our models on both versions
of non-permutation (MNIST) and permutation (pMNIST) Le et al. (2015). More
details on the task and data can be found in Le et al., (2015). For DNC, we
try with several memory slots from $\left\\{15,30,60\right\\}$ and report the
best results. For UW and CUW, memory size is fixed to 15 and cache size $L$ is
set to 10. The controllers are implemented as single layer GRU with
$100$-dimensional hidden vector. To optimise the models, we use RMSprop with
initial learning rate of 0.0001.

Table 6.3 shows that DNC underperforms r-LSTM, which indicates that regular
DNC with big memory finds it hard to beat LSTM-based methods. After applying
UW, the results get better and with CUW, it shows significant improvement over
r-LSTM and demonstrates competitive performance against dilated-RNNs models.
Notably, dilated-RNNs use 9 layers in their experiments compared to our singer
layer controller. Furthermore, our models exhibit more consistent performance
than dilated-RNNs. For completeness, we include comparisons between CUW and
non-recurrent methods in Appendix D.11

Model | MNIST | pMNIST
---|---|---
iRNN† | 97.0 | 82.0
uRNN∘ | 95.1 | 91.4
r-LSTM Full BP⋆ | 98.4 | 95.2
Dilated-RNN◆ | 95.5 | 96.1
Dilated-GRU◆ | 99.2 | 94.6
DNC | 98.1 | 94.0
DNC+UW | 98.6 | 95.6
DNC+CUW | 99.1 | 96.3
Table 6.3: Test accuracy (%) on MNIST, pMNIST. Previously reported results are
from the literature Le et al. (2015)†, Arjovsky et al. (2016)∘, Trinh et al.
(2018)⋆, and Chang et al. (2017)◆.

####  6.5.6 Document Classification

To verify our proposed models in real-world applications, we conduct
experiments on document classification task. In the task, the input is a
sequence of words and the output is the classification label. Following common
practices Yogatama et al. (2017); Seo et al. (2018), each word in the document
is embedded into a $300$-dimensional vector using Glove embedding Pennington
et al. (2014). We use RMSprop for optimisation, with initial learning rate of
0.0001. Early-stop training is applied if there is no improvement after 5
epochs in the validation set. Our UW and CUW are built upon DNC with single
layer $512$-dimensional LSTM controller and the memory size is chosen in
accordance with the average length of the document, which ensures $10-20\%$
compression ratio. The cache size for CUW is fixed to 10. The datasets used in
this experiment are common big datasets where the number of documents is
between 120,000 and 1,400,000 with maximum of 4,392 words per document (see
Appendix D.12 for further details). The baselines are recent state-of-the-arts
in the domain, some of which are based on recurrent networks such as D-LSTM
Yogatama et al. (2017) and Skim-LSTM Seo et al. (2018). We exclude DNC from
the baselines as it is inefficient to train the model with big document
datasets.

Our results are reported in Table 6.4. On five datasets out of six, our models
beat or match the best published results. For IMDb dataset, our methods
outperform the best recurrent model (Skim-LSTM). The performance gain is
competitive against that of the state-of-the-arts. In most cases, CUW is
better than UW, which emphasises the importance of relaxing the timestep
equality assumption in practical situations. Details results across different
runs for our methods are listed in Appendix D.13.

Model | AG | IMDb555Methods that use semi-supervised training to achieve higher accuracy are not listed. | Yelp P. | Yelp F. | DBP | Yah. A.
---|---|---|---|---|---|---
VDCNN∙ | 91.3 | - | 95.7 | 64.7 | 98.7 | 73.4
D-LSTM∗ | - | - | 92.6 | 59.6 | 98.7 | 73.7
Standard LSTM‡ | 93.5 | 91.1 | - | - | - | -
Skim-LSTM‡ | 93.6 | 91.2 | - | - | - | -
Region Embedding▲ | 92.8 | - | 96.4 | 64.9 | 98.9 | 73.7
DNC+UW | 93.7 | 91.4 | 96.4 | 65.3 | 99.0 | 74.2
DNC+CUW | 93.9 | 91.3 | 96.4 | 65.6 | 99.0 | 74.3
Table 6.4: Document classification accuracy (%) on several datasets.
Previously reported results are from the literature Conneau et al. (2016)∙,
Yogatama et al. (2017)∗, Seo et al. (2018)‡ and Qui et al. (2018)▲. We use
italics to denote the best published and bold the best records.

###  6.6 Closing Remarks

We have introduced Uniform Writing (UW) and Cached Uniform Writing (CUW) as
faster solutions for longer-term memorisation in MANNs. With a comprehensive
suite of synthetic and practical experiments, we provide strong evidences that
our simple writing mechanisms are crucial to MANNs to reduce computation
complexity and achieve competitive performance in sequence modeling tasks. In
complement to the experimental results, we have proposed a meaningful
measurement on MANN memory capacity and provided theoretical analysis showing
the optimality of our methods. In the next chapter, we shift the focus back to
designing a better MANN that is capable of learning multiple procedures at the
same time and behaving like a universal Turing machine rather than a Turing
machine.

##  Chapter 7 Neural Stored-Program Memory

###  7.1 Introduction

Recurrent Neural Networks (RNNs) are Turing-complete, that is, we can
theoretically construct a Turing machine by using RNN elements Siegelmann and
Sontag (1995). However, in practice RNNs struggle to learn simple procedures
as they lack explicit memory Graves et al. (2014); Mozer and Das (1993) .
Memory Augmented Neural Networks (MANNs) as analysed in Chapter 3, lift these
limitations as they are capable of emulating modern computer behavior by
detaching memorisation from computation via memory and controller network,
respectively. In previous chapters, we have also demonstrated that MANNs are
powerful in many settings, ranging from encoding multi-processes, generating
complex sequences, to skip-readings. Nonetheless, MANNs have barely simulated
general-purpose computers as they miss a key concept in computer design:
stored-program memory.

The concept of stored-program has emerged from the idea of Universal Turing
Machine (UTM) Turing (1936) and developed in the Von Neumann Architecture
(VNA) von Neumann (1993). In UTM/VNA, both data and programs that manipulate
the data are stored in memory. A control unit then reads the programs from the
memory and executes them with the data. This mechanism allows flexibility to
perform universal computations. Unfortunately, current MANNs such as Neural
Turing Machine (NTM) Graves et al. (2014), Differentiable Neural Computer
(DNC) Graves et al. (2016) and Least Recently Used Access (LRUA) Santoro et
al. (2016) only support memory for data and embed a single program into the
controller network, which goes against the stored-program memory principle.

Our goal is to advance a step further towards UTM/VNA by coupling a MANN with
an external program memory. The program memory co-exists with the data memory
in the MANN, providing more flexibility, reuseability and modularity in
learning complicated tasks. The program memory stores the weights of the
MANN’s controller network, which are retrieved quickly via a key-value
attention mechanism across timesteps yet updated slowly via backpropagation.
By introducing a meta network to moderate the operations of the program
memory, our model, henceforth referred to as Neural Stored-program Memory
(NSM), can learn to switch the programs/weights in the controller network
appropriately, adapting to different functionalities aligning with different
parts of a sequential task, or different tasks in continual and few-shot
learning.

To validate our proposal, the NTM armed with NSM, namely Neural Universal
Turing Machine (NUTM), is tested on a variety of synthetic tasks including
algorithmic tasks Graves et al. (2014), composition of algorithmic tasks and
continual procedure learning. For these algorithmic problems, we demonstrate
clear improvements of NUTM over NTM. Further, we investigate NUTM in few-shot
learning by using LRUA as the MANN and achieve notably better results.
Finally, we expand NUTM application to linguistic problems by equipping NUTM
with DNC core and achieve competitive performances against state-of-the-arts
in the bAbI task Weston et al. (2015).

Taken together, our study advances neural network simulation of Turing
Machines to neural architecture for Universal Turing Machines. This develops a
new class of MANNs that can store and query both the weights and data of their
own controllers, thereby following the stored-program principle. A set of five
diverse experiments demonstrate the computational universality of the
approach.

###  7.2 Backgrounds

####  7.2.1 Turing Machines and MANNs

In this section, we briefly review MANN and its relations to Turing Machines.
A MANN consists of a controller network and an external memory
$\mathbf{M}\in\mathbb{R}^{N\times M}$, which is a collection of $N$
$M$-dimensional vectors. The controller network is responsible for accessing
the memory, updating its state and optionally producing output at each
timestep. The first two functions are executed by an interface network and a
state network111Some MANNs (e.g., NTM with Feedforward Controller) neglect the
state network, only implementing the interface network and thus analogous to
one-state Turing Machine. , respectively. Usually, the interface network is a
Feedforward neural network whose input is $c_{t}$ \- the output of the state
network implemented as RNNs. Let $W^{c}$ denote the weight of the interface
network, then the state update and memory control are as follows,

$h_{t},c_{t}=RNN\left(\left[x_{t},r_{t-1}\right],h_{t-1}\right)$ (7.1)
$\xi_{t}=c_{t}W^{c}$ (7.2)

where $x_{t}$ and $r_{t-1}$ are data from current input and the previous
memory read, respectively. The interface vector $\xi_{t}$ then is used to read
from and write to the memory $\mathbf{M}$. We use a generic notation
$memory\left(\xi_{t},\mathbf{M}\right)$ to represent these memory operations
that either update or retrieve read value $r_{t}$ from the memory. To support
multiple memory accesses per step, there might be several interface networks
to produce multiple interfaces, also known as control heads. Readers are
referred to Graves et al., (2014, 2016) and Santoro et al., (2016) for details
of memory read/write examples.

A deterministic one-tape Turing Machine can be defined by 4-tuple
$\left(Q,\Gamma,\delta,q_{0}\right)$, in which $Q$ is finite set of states,
$q_{0}\in Q$ is an initial state, $\Gamma$ is finite set of symbol stored in
the tape (the data) and $\delta$ is the transition function (the program),
$\delta:Q\times\Gamma\rightarrow\Gamma\times\left\\{-1,1\right\\}\times Q$. At
each step, the machine performs the transition function, which takes the
current state and the read value from the tape as inputs and outputs actions
including writing new values, moving tape head to new location (left/right)
and jumping to another state. Roughly mapping to current MANNs, $Q$, $\Gamma$
and $\delta$ map to the set of the controller states, the read values and the
controller network, respectively. Further, the function $\delta$ can be
factorised into two sub functions:
$Q\times\Gamma\rightarrow\Gamma\times\left\\{-1,1\right\\}$ and
$Q\times\Gamma\rightarrow Q$, which correspond to the interface and state
networks, respectively.

By encoding a Turing Machine into the tape, one can build an UTM that
simulates the encoded machine Turing (1936). The transition function of the
UTM queries the encoded Turing Machine that solves the considering task.
Amongst 4 tuples, $\delta$ is the most important and hence uses most of the
encoding bits. In other words, if we assume that the space of $Q$, $\Gamma$
and $q_{0}$ are shared amongst Turing Machines, we can simulate any Turing
Machine by encoding only its transition function $\delta$. Translating to
neural language, if we can store the controller network into a queriable
memory and make use of it, we can build a Neural Universal Turing Machine.
Using NSM is a simple way to achieve this goal, which we introduce in the
subsequent section.

####  7.2.2 Related Approaches

Previous investigations into MANNs mostly revolve around memory access
mechanisms. The works in Graves et al., (2014, 2016) introduce content-based,
location-based and dynamic memory reading/writing. Further, Rae et al., (2016)
scales to bigger memory by sparse access while Le et al., (2019a) optimises
memory operations with uniform writing. These works keep using memory for
storing data rather than the weights of the network and thus parallel to our
approach. Other DNC modifications Csordas and Schmidhuber (2019); Franke et
al. (2018) are also orthogonal to our work.

Another line of related work involves modularisation of neural networks, which
is designed for visual question answering. In module networks Andreas et al.
(2016b, a), the modules are manually aligned with predefined concepts and the
order of execution is decided by the question. Although the module in these
works resembles the program in NSM, our model is more generic and flexible
with soft-attention over programs and thus fully differentiable. Further, the
motivation of NSM does not limit to a specific application. Rather, NSM aims
to help MANN reach general-purpose computability.

Finally, if we view NSM network as a dynamic weight generator, the program in
NSM can be linked to fast weight Hinton and Plaut (1987); Ba et al. (2016);
Munkhdalai and Yu (2017). These papers share the idea of using different
weights across timesteps to enable dynamic adaptation. However, fast weights
are directly generated while our programs are interpolated from a set of slow
weights.

###  7.3 Neural Stored-Program Memory and Neural Universal Turing Machine

####  7.3.1 Neural Stored-Program Memory

A Neural Stored-program Memory (NSM) is a key-value memory
$\mathbf{M}_{p}\in\mathbb{R}^{P\times(K+S)}$, whose value is the weight of
another neural network$-$the program. $P$, $K$, and $S$ are the number of
programs, the key space dimension and the program size, respectively. This
concept is a hybrid between the traditional slow-weight and fast-weight Hinton
and Plaut (1987). Like slow-weight, the weights in NSM are updated gradually
by backpropagation. However, they are dynamically recomputed on-the-fly during
the processing of a sequence, which resembles fast-weight computation. Let us
denote $\mathbf{M}_{p}\left(i\right).k$ and $\mathbf{M}_{p}\left(i\right).v$
as the key and the content of the $i$-th memory slot. At timestep $t,$ given a
query key $k_{t}^{p}$, the corresponding program is retrieved as follows,

$D\left(k_{t}^{p},\mathbf{M}_{p}(i).k\right)=\frac{k_{t}^{p}\cdot\mathbf{M}_{p}(i).k}{||k_{t}^{p}||\cdot||\mathbf{M}_{p}(i).k)||}$
(7.3)

$p_{t}=\stackrel{{\scriptstyle[}}{{i}}=1]{P}{\sum}\text{softmax}\left(\beta_{t}^{p}D\left(k_{t}^{p},\mathbf{M}_{p}(i).k\right)\right)\mathbf{M}_{p}\left(i\right).v$
(7.4)

where $D\left(\cdot\right)$ is cosine similarity and $\beta_{t}^{p}$ is the
scalar program strength parameter. The vector program $p_{t}$ is then reshaped
to its matrix form and ready to be used in other neural computations.

The key-value design is essential for convenient memory access as the size of
the program stored in $\mathbf{M}_{p}$ can be millions of dimensions and thus,
direct content-based addressing Graves et al. (2014, 2016) is infeasible. More
importantly, we can inject external control on the behavior of the memory by
imposing constraints on the key space. For example, program collapse will
happen when the keys stored in the memory stay close to each other. When this
happens, $p_{t}$ is a balanced mixture of all programs regardless of the query
key and thus having multiple programs is useless. We can avoid this phenomenon
by minimising a regularisation loss defined as the following,

$l_{p}=\stackrel{{\scriptstyle[}}{{i}}=1]{P}{\sum}\stackrel{{\scriptstyle[}}{{j}}=i+1]{P}{\sum}D\left(\mathbf{M}_{p}(i).k,\mathbf{M}_{p}(j).k\right)$
(7.5)

####  7.3.2 Neural Universal Turing Machine

It turns out that the combination of MANN and NSM approximates an Universal
Turing Machine (Sec. 7.2). At each timestep, the controller in MANN reads its
state and memory to generate control signal to the memory via the interface
network $W^{c}$, then updates its state using the state network $RNN$. Since
the parameters of $RNN$ and $W^{c}$ represent the encoding of $\delta$, we
store both into NSM to completely encode an MANN. For simplicity, in this
proposal, we only use NSM to store $W^{c}$, which is equivalent to the
Universal Turing Machine that can simulate any one-state Turing Machine.

In traditional MANN, $W^{c}$ is constant across timesteps and only updated
slowly during training, typically through backpropagation. In our design, we
compute $W_{t}^{c}$ from NSM for every timestep and thus, we need a program
interface network$-$the meta network $P_{\mathscr{\mathcal{I}}}-$that
generates an interface vector for the program memory:
$\xi_{t}^{p}=P_{\mathscr{\mathcal{I}}}\left(c_{t}\right)$, where
$\xi_{t}^{p}=\left[k_{t}^{p},\beta_{t}^{p}\right]$ and
$P_{\mathscr{\mathcal{I}}}$ is implemented as a Feedforward neural network.
The procedure for computing $W_{t}^{c}$ is executed by following Eqs.
(7.3)-(7.4), hereafter referred to as
$NSM\left(\xi_{t}^{p},\mathbf{M}_{p}\right)$. Figure 7.1 depicts the
integration of NSM into MANN.

Figure 7.1: Introducing NSM into MANN. At each timestep, the program interface
network ($P_{\mathscr{\mathcal{I}}}$) receives input from the state network
and queries the program memory $\mathbf{M}_{p}$, acquiring the working weight
for the interface network ($W_{t}^{c}$). The interface network then operates
on the data memory $\mathbf{M}$.

For the case of multi-head NTM, we implement one NSM per control head and name
this model Neural Universal Turing Machine (NUTM). Each control head will read
from (for read head) or write to (for write head) the data memory $\mathbf{M}$
via $memory\left(\xi_{t},\mathbf{M}\right)$ as described in Graves et al.,
(2014). Other MANNs such as DNC Graves et al. (2016) and LRUA Santoro et al.
(2016) can be armed with NSM in this manner. We also employ the regularisation
loss $l_{p}$ to prevent the programs from collapsing, resulting in a final
loss as follows,

$Loss=Loss_{pred}+\eta_{t}l_{p}$ (7.6)

where $Loss_{pred}$ is the prediction loss and $\eta_{t}$ is annealing factor,
reducing as the training step increases. The details of NUTM operations are
presented in Algorithm 1.

1:a sequence $x=\left\\{x_{t}\right\\}_{t=1}^{T}$, a data memory $\mathbf{M}$
and $R$ program memories $\left\\{\mathbf{M}_{p,n}\right\\}_{n=1}^{R}$
corresponding to $R$ control heads

2:Initilise $h_{0}$, $r_{0}$

3:for $t=1,T$ do

4: $h_{t},c_{t}=RNN([x_{t},r_{t-1}],h_{t-1})$ $\triangleright$ $RNN$ can be
replaced by GRU/LSTM

5: for $n=1,R$ do

6: Compute the program interface $\xi_{t,n}^{p}\leftarrow
P_{\mathscr{\mathcal{I}},n}\left(c_{t}\right)$

7: Compute the program $W_{t,n}^{c}\leftarrow
NSM\left(\xi_{t,n}^{p},\mathbf{M}_{p,n}\right)$

8: Compute the data interface $\xi_{t,n}\leftarrow c_{t}W_{t,n}^{c}$

9: Access/update data memory $r_{t,n}\leftarrow
memory\left(\xi_{t,n},\mathbf{M}\right)$$\triangleright$ Write heads return
$\emptyset$

10: end for

11: $r_{t}\leftarrow\left[r_{t,1},...,r_{t,R}\right]$

12:end for

Algorithm 1 Neural Universal Turing Machine

####  7.3.3 On the Benefit of NSM to MANN: An Explanation from Multilevel
Modeling

Learning to access memory is a multi-dimensional regression problem. Given the
input $c_{t}$, which is derived from the state $h_{t}$ of the controller, the
aim is to generate a correct interface vector $\xi_{t}$ via optimising the
interface network. Instead of searching for one transformation that maps the
whole space of $c_{t}$ to the optimal space of $\xi_{t}$, NSM first partitions
the space of $c_{t}$ into subspaces, then finds multiple transformations, each
of which covers subspace of $c_{t}$. The program interface network
$P_{\mathscr{\mathcal{I}}}$ is a meta learner that routes $c_{t}$ to the
appropriate transformation, which then maps $c_{t}$ to the $\xi_{t}$ space.
This is analogous to multilevel regression in statistics Andrew Gelman (2006).
Many practical studies have demonstrated that multilevel regression is better
than ordinary regression if the input is clustered Cohen et al. (2014); Huang
(2018).

RNNs have the capacity to learn to perform finite state computations Casey
(1996); Tiňo et al. (1998). The states of a RNN must be grouped into
partitions representing the states of the generating automation. As Turing
Machine is finite state automata augmented with an external memory tape, we
expect MANN, if learnt well, will organise its state space clustered in a way
to reflect the states of the emulated Turing Machine. That is, $h_{t}$ as well
as $c_{t}$ should be clustered. We realise that NSM helps NTM learn better
clusterisation over this space (see Appendix E.2), thereby improving NTM’s
performances.

###  7.4 Applications

####  7.4.1 NTM Single Tasks

Figure 7.2: Learning curves on NTM tasks. Task | Copy | Repeat Copy | A. Recall | D. N-grams | Priority Sort | Long Copy
---|---|---|---|---|---|---
NTM | 0.00 | 405.10 | 7.66 | 132.59 | 24.41 | 16.04
NUTM (p=2) | 0.00 | 366.69 | 1.35 | 127.68 | 20.00 | 0.02
Table 7.1: Generalisation performance of best models measured in average bit
error per sequence (lower is better). For each task, we pick a set of 1,000
unseen sequences as test data.

In this section, we investigate the performance of NUTM on algorithmic tasks
introduced in Graves et al., (2014): Copy, Repeat Copy, Associative Recall,
Dynamic N-Gram and Priority Sort. Besides these five NTM tasks, we add another
task named Long Copy which doubles the length of training sequences in the
Copy task. In these tasks, the model will be fed a sequence of input items and
is required to infer a sequence of output items. Each item is represented by a
binary vector.

In the experiment, we compare two models: NTM222For algorithmic tasks, we
choose NTM as the only baseline as NTM is known to perform and generalise well
on these tasks. If NSM can help NTM in these tasks, it will probably help
other MANNs as well. and NUTM with two programs. Although the tasks are
atomic, we argue that there should be at least two memory manipulation schemes
across timesteps, one for encoding the inputs to the memory and another for
decoding the output from the memory. The two models are trained with cross-
entropy objective function under the same setting as in Graves et al., (2014).
For fair comparison, the controller hidden dimension of NUTM is set smaller to
make the total number of parameters of NUTM equivalent to that of NTM (details
in Appendix E.4).

We run each experiments five times and report the mean with error bars of
training losses for the first 4 tasks in Fig. E.1. Except for the Copy task,
which is too simple, other tasks observe convergence speed improvement of NUTM
over that of NTM, thereby validating the benefit of using two programs across
timesteps even for the single task setting. Full report is listed in Appendix
E.1. As NUTM requires fewer training samples to converge, it generalises
better to unseen sequences that are longer than training sequences. Table 7.1
reports the test results of the best models chosen after five runs and
confirms the outperformance of NUTM over NTM for generalisation.

To illustrate the program usage, we plot NUTM’s program distributions across
timesteps for Repeat Copy and Priority Sort in Fig. 7.3 (a) and (b),
respectively. We observe two program usage patterns corresponding to the
encoding and decoding phases. For Repeat Copy, there is no reading in encoding
and thus, NUTM assigns the “no-read” strategy mainly to the “orange program”.
In decoding, the sequential reading is mostly done by the “blue program” with
some contributions from the “orange program” when resetting reading head. For
Priority Sort, while the encoding “fitting writing” (see Graves et al., (2014)
for explanation on the strategy) is often executed by the “blue program”, the
decoding writing is completely taken by the “orange” program (more
visualisations in Appendix E.3).

Figure 7.3: (a,b,c) visualises NUTM’s executions in synthetic tasks: the upper
rows are memory read (left)/write (right) locations; the lower rows are
program distributions over timesteps. The green line indicates the start of
the decoding phase. (d) visualises perservation in NTM: the upper row are
input, output, predicted output with errors (orange bits); the lower row is
reading location.

####  7.4.2 NTM Sequencing Tasks

In neuroscience, sequencing tasks test the ability to remember a series of
tasks and switch tasks alternatively Blumenfeld (2010). A dysfunctional brain
may have difficulty in changing from one task to the next and get stuck in its
preferred task (perseveration phenomenon). To analyse this problem in neural
algorithmic learners, we propose a new set of experiments in which a task is
generated by sequencing a list of subtasks. The set of subtasks is chosen from
the NTM single tasks (excluding Dynamic N-grams for format discrepancy) and
the order of subtasks in the sequence is dictated by an indicator vector put
at the beginning of the sequence. Amongst possible combinations of subtasks,
we choose {Copy, Repeat Copy}(C+RC), {Copy, Associative Recall} (C+AR), {Copy,
Priority Sort} (C+PS) and all (C+RC+AC+PS)333We focus on the combinations that
contain Copy as Copy is the only task where NTM can reach NUTM’s performance.
If NTM fails in these combinations, it will most likely fail in other
combinations.. The learner observes the order indicator following by a
sequence of subtasks’ input items and is requested to consecutively produce
the output items of each subtasks.

As shown in Fig. 7.4, some tasks such as Copy and Associative Recall, easy to
solve if trained separately, become unsolvable by NTM when sequenced together.
One reason for NTM’s poor performance is its failure to change the memory
access behavior (perseveration). For example, NTM keeps following repeat copy
reading strategy for all timesteps in C+RC task (Fig. 7.3 (d)). Meanwhile,
NUTM can learn to change program distribution when a new subtask appears in
the sequence and thus ensure different memory accessing strategy per subtask
(Fig. 7.3 (c)).

Figure 7.4: Learning curves on sequencing NTM tasks.

####  7.4.3 Continual Procedure Learning

In continual learning, catastrophic forgetting happens when a neural network
quickly forgets previously acquired skills upon learning new skills French
(1999). In this section, we prove the versatility of NSM by showing that a
naive application of NSM without much modification can help NTM to mitigate
catastrophic forgetting. We design an experiment similar to the Split MNIST
Zenke et al. (2017) to investigate whether NSM can improve NTM’s performance.
In our experiment, we let the models see the training data from the 4 tasks:
Copy (C), Repeat Copy (RC), Associative Recall (AR) and Priority Sort (PS),
consecutively in this order. Each task is trained in 20,000 iterations with
batch size 16 (see Appendix E.4 for task details). To encourage NUTM to spend
exactly one program per task while freezing others, we force “hard” attention
over the programs by replacing the softmax function in Eq. 7.4 with the
Gumbel-softmax Jang et al. (2016). Also, to ignore catastrophic forgetting in
the state network, we use Feedforward controllers in the two baselines.

After finishing one task, we evaluate the bit accuracy $-$measured by $1-$(bit
error per sequence/total bits per sequence)$-$over 4 tasks. As shown in Fig.
7.5, NUTM outperforms NTM by a moderate margin (10-40% per task). Although
NUTM also experiences catastrophic forgetting, it somehow preserves some
memories of previous tasks. Especially, NUTM keeps performing perfectly on
Copy even after it learns Repeat Copy. For other dissimilar task transitions,
the performance drops significantly, which requires more effort to bring NSM
to continual learning.

Figure 7.5: Mean bit accuracy for the continual algorithmic tasks. Each of the
first four panels show bit accuracy on four tasks after finishing a task. The
rightmost shows the average accuracy.

####  7.4.4 Few-Shot Learning

Few-shot learning or meta learning tests the ability to rapidly adapt within a
task while gradually capturing the way the task structure varies Thrun (1998).
By storing sample-class bindings, MANNs are capable of classifying new data
after seeing only few samples Santoro et al. (2016). As NSM gives flexible
memory controls, it makes MANN more adaptive to changes and thus perform
better in this setting. To verify that, we apply NSM to the LRUA memory and
follow the experiments introduced in Santoro et al., (2016), using the
Omniglot dataset to measure few-shot classification accuracy. The dataset
includes images of 1623 characters, with 20 examples of each character. During
training, a sequence (episode) of images are randomly selected from $C$
classes of characters in the training set (1200 characters), where $C=5,10$
corresponding to sequence length of 50, 75, respectively. Each class is
assigned a random label which shuffles between episodes and is revealed to the
models after each prediction. After 100,000 episodes of training, the models
are tested with unseen images from the testing set (423 characters). The two
baselines are MANN and NUTM (both use LRUA core). For NUTM, we only tune $p$
and pick the best values: $p=2$ and $p=3$ for 5 classes and 10 classes,
respectively.

Table 7.2 reports the classification accuracy when the models see characters
for the second, third and fifth time. NUTM generally achieves better results
than MANN, especially when the number of classes increases, demanding more
adaptation within an episode. For the persistent memory mode, which demands
fast forgetting old experiences in previous episodes, NUTM outperforms MANN
significantly (10-20%).

Model | Persistent | 5 classes | 10 classes
---|---|---|---
memory444If the memory is not artificially erased between episodes, it is called persistent. This mode is hard for the case of 5 classes Santoro et al. (2016) | $2^{nd}$ | $3^{rd}$ | $5^{th}$ | $2^{nd}$ | $3^{rd}$ | $5^{th}$
MANN (LRUA)* | No | 82.8 | 91.0 | 94.9 | - | - | -
MANN (LRUA) | No | 82.3 | 88.7 | 92.3 | 52.7 | 60.6 | 64.7
NUTM (LRUA) | No | 85.7 | 91.3 | 95.5 | 68.0 | 78.1 | 82.8
MANN (LRUA) | Yes | 66.2 | 73.4 | 81.0 | 51.3 | 59.2 | 63.3
NUTM (LRUA) | Yes | 77.8 | 85.8 | 89.8 | 69.0 | 77.9 | 82.7
Table 7.2: Test-set classification accuracy (%) on the Omniglot dataset after
100,000 episodes of training. * denotes available results from Santoro et al.,
(2016). See Appendix E.5 for more details.

####  7.4.5 Text Question Answering

Reading comprehension typically involves an iterative process of multiple
actions such as reading the story, reading the question, outputting the
answers and other implicit reasoning steps Weston et al. (2015). We apply NUTM
to the question answering domain by replacing the NTM core with DNC Graves et
al. (2016). Compared to NTM’s sequential addressing, dynamic memory addressing
in DNC is more powerful and thus suitable for NSM integration to solve non-
algorithmic problems such as question answering. Following previous works of
DNC, we use bAbI dataset Weston et al. (2015) to measure the performance of
the NUTM with DNC core (two variants $p=2$ and $p=4$). In the dataset, each
story is followed by a series of questions and the network reads all word by
word, then predicts the answers. Although synthetically generated, bAbI is a
good benchmark that tests 20 aspects of natural language reasoning including
complex skills such as induction, counting and path finding,

We found that NUTM with 4 programs, after 50 epochs jointly trained on all 20
question types, can achieve a mean test error rate of 3.3% and manages to
solve 19/20 tasks (a task is considered solved if its error <5%). The mean and
s.d. across 10 runs are also compared with other results reported by recent
works (see Table 7.3). Excluding baselines under different setups, our result
is the best reported mean result on bAbI that we are aware of. More details
are described in Appendix E.6.

Model | Error
---|---
DNCGraves et al. (2016) | 16.7 ± 7.6
SDNCRae et al. (2016) | 6.4 ± 2.5
ADNCFranke et al. (2018) | 6.3 ± 2.7
DNC-MDCsordas and Schmidhuber (2019) | 9.5 ± 1.6
NUTM (DNC core) $p=2$ | 7.5 ± 1.6
NUTM (DNC core) $p=4$ | 5.6 ± 1.9
Table 7.3: Mean and s.d. for bAbI error ($\%$).

###  7.5 Closing Remarks

This chapter introduces the Neural Stored-program Memory (NSM), a new type of
external memory for neural networks. The memory, which takes inspirations from
the stored-program memory in computer architecture, gives memory-augmented
neural networks (MANNs) flexibility to change their control programs through
time while maintaining differentiability. The mechanism simulates modern
computer behavior, potential making MANNs truly neural computers. Our
experiments demonstrated that when coupled with our model, the Neural Turing
Machine learns algorithms better and adapts faster to new tasks at both
sequence and sample levels. When used in few-shot learning, our method helps
MANN as well. We also applied the NSM to the Differentiable Neural Computer
and observed a significant improvement, reaching the state-of-the-arts in the
bAbI task.

##  Chapter 8 Conclusions

###  8.1 Summary

In this thesis, we have presented several types of memory for neural networks
in general and Recurrent Neural Networks (RNNs) in particular. We emphasise
the notion of the memory as an external storage for RNNs in which, RNNs can
learn to read from and write to the external memory to support their working
memory (Chapter 2). We reviewed advancements to solve the difficulties in
training RNNs such as gating and attention mechanisms and especially we
focused on slot-based MANNs, which is based on sparse distributed memory
model–the main theme of new models we propose in the thesis (Chapter 3). Our
main contributions are four-fold. First, we extended MANNs as a multi-process
multi-view model to handle complex problems such as sequence-to-sequence
mapping and multi-view sequential learning (Chapter 4). We further extended
MANNs as a model for discrete sequence generation on conversational data where
variability and coherence are required (Chapter 5). We also shed light into
memory operations to estimate MANN capacity and proposed new writing schemes
to maximise the capacity (Chapter 6). Finally, we introduced a new class of
MANNs that follows stored-program memory principle and can switch the
controller’s programs to execute different functionalities through time.

In Chapter 4, we presented our first contributions: Dual Controller Write-
Protected Memory Augmented Neural Network (DCw-MANN), an extension of MANN to
model sequence to sequence mapping, and Dual Memory Neural Computer (DMNC)
that can capture the correlations between two views by exploiting two external
memory units. We demonstrated these models on predicting next disease stages
and recommending medicines in healthcare. The results are competitive against
contemporary state-of-the-arts.

Chapter 5 presented Variational Memory Encoder-Decoder, a novel memory-
augmented generation framework. Our external memory not only holds long-term
context but also constructs mixture model distribution generating the latent
variables. We derived theoretical analysis to validate our training protocol
using Stochastic Gradient Variational Bayes framework by minimising
variational approximation of KL divergence. We evaluated our model on two
open-domain and two closed-domain conversational datasets and outperformed
other baselines by a large margin.

Chapter 6 focused more on theoretical analysis of a meaningful measurement on
MANN’s memory capacity. We proposed solution dubbed Uniform Writing is optimal
in terms of maximising the memory capacity. To encourage forgetting when
necessary, we introduce modifications to the original solution, resulting in a
new solution termed Cached Uniform Writing. This method aims to balance
between memorising and forgetting via allowing overwriting mechanism. We
conducted a set of diverse experiments on six ultra-long sequential learning
problems given a limited number of memory slots to demonstrate the superiority
of our methods.

Chapter 7 addressed the simulation capacity of MANNs. To make current MANNs
truly simulate modern computers, a design of Neural Stored-program Memory
(NSM) was proposed to implement stored-program principle, which resulted in
new MANN architectures that materialise Universal Turing Machines.

###  8.2 Future Directions

There are possible extensions of the work proposed in this thesis for further
investigations. First, in Chapter 4, we can extend the DCw-MANN to handle
multiple healthcare tasks by developing new capabilities for medical question
answering, which can be cast to a sequence-to-sequence mapping problem.
Moreover, DMNC can be generalised to multi-input multi-output settings and
extending the range of applications to bigger problems such as multi-media and
multi-agent systems. For VMED (Chapter 5), future explorations may involve
implementing a dynamic number of modes that enable learning of the optimal $K$
for each timestep. Another aspect would be multi-person dialog setting, where
our memory as mixture model may be useful to capture more complex modes of
speaking in the dialog. Future investigations for Chapter 6 will focus on
tightening the measurement bound. Last but not least, we emphasise that apart
from MANNs, other neural networks can also reap benefits from the NSM proposed
in Chapter 7. More effort will be spent on integrating NSM into different
neural networks to make them more flexible and modular.

## Appendix

###  C Supplementary for Chapter 5

####  C.1 Proof of Theorem 5.1

###### Proof.

$D_{var}$$\left(f\parallel g\right)$ Hershey and Olsen (2007) is an
approximation of $KL$ divergence between two Mixture of Gaussians (MoG), which
is defined as the following,

$\displaystyle D_{var}\left(f\parallel g\right)=$
$\displaystyle\underset{j}{\sum}\pi_{j}^{f}\log\frac{\underset{j^{\prime}}{\sum}\pi_{j^{\prime}}^{f}e^{-KL\left(f_{j}\parallel
f_{j^{\prime}}\right)}}{\underset{i}{\sum}\pi_{i}^{g}e^{-KL\left(f_{j}\parallel
g_{i}\right)}}$ (8.1)

In our case, $f$ is a Gaussian, a special case of MoG where the number of mode
equals one. Then, Eq. (8.1) becomes

$D_{var}\left(f\parallel
g\right)=\log\frac{1}{\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi_{i}^{g}e^{-KL\left(f\parallel
g^{i}\right)}}=-\log\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi^{i}e^{-KL\left(f\parallel
g^{i}\right)}$

Let define the log-likelihood
$L_{f}\left(g\right)=E_{f\left(x\right)}\left[\log g\left(x\right)\right]$,
the lower bound for $L_{f}\left(g\right)$ can be also be derived, using
variational parameters as follows,

$\displaystyle L_{f}\left(g\right)=$ $\displaystyle
E_{f}\left[\log\left(\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi^{i}g^{i}\left(x\right)\right)\right]$
$\displaystyle=$
$\displaystyle\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}f\left(x\right)\log\left(\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\beta^{i}\pi^{i}\frac{g^{i}\left(x\right)}{\beta^{i}}\right)dx$
$\displaystyle\geq$
$\displaystyle\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\beta^{i}\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}f\left(x\right)\log\left(\pi^{i}\frac{g^{i}\left(x\right)}{\beta^{i}}\right)dx$

where $\beta^{i}\geq 0$ and
$\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\beta^{i}=1$. According to Durrieu
et al., (2012), maximising the RHS of the above inequality with respect to
$\beta^{i}$ provides a lower bound for $L_{f}\left(g\right)$ Durrieu et al.
(2012),

$\displaystyle L_{f}\left(g\right)\geq$
$\displaystyle\log\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi^{i}e^{-KL\left(f\parallel
g^{i}\right)}+L_{f}\left(f\right)$ $\displaystyle=$ $\displaystyle-
D_{var}+L_{f}\left(f\right)$ $\displaystyle\Rightarrow D_{var}\geq$
$\displaystyle L_{f}\left(f\right)-L_{f}\left(g\right)$ $\displaystyle=$
$\displaystyle KL\left(f\parallel g\right)$

Therefore, the $KL$ divergence has an upper bound: $D_{var}$. ∎

####  C.2 Derivation of the Upper Bound on the Total Timestep-Wise $KL$
Divergence

######  Lemma C.1.

Chebyshev’s sum inequality:

if

$a_{1}\geq a_{2}\geq...\geq a_{n}$

and

$b_{1}\geq b_{2}\geq...\geq b_{n}$

then

$\frac{1}{n}\stackrel{{\scriptstyle[}}{{k}}=1]{n}{\sum}a_{k}b_{k}\geq\left(\frac{1}{n}\stackrel{{\scriptstyle[}}{{k}}=1]{n}{\sum}a_{k}\right)\left(\frac{1}{n}\stackrel{{\scriptstyle[}}{{k}}=1]{n}{\sum}b_{k}\right)$

###### Proof.

Consider the sum

$S=\stackrel{{\scriptstyle[}}{{j}}=1]{n}{\sum}\stackrel{{\scriptstyle[}}{{k}}=1]{n}{\sum}\left(a_{j}-a_{k}\right)\left(b_{j}-b_{k}\right)$

The two sequences are non-increasing, therefore $a_{j}-a_{k}$ and
$b_{j}-b_{k}$ have the same sign for any $j,k$. Hence $S\geq 0$. Opening the
brackets, we deduce

${\displaystyle 0\leq
2n\sum_{j=1}^{n}a_{j}b_{j}-2\sum_{j=1}^{n}a_{j}\,\sum_{k=1}^{n}b_{k}}$

whence

${\displaystyle{\frac{1}{n}}\sum_{j=1}^{n}a_{j}b_{j}\geq\left({\frac{1}{n}}\sum_{j=1}^{n}a_{j}\right)\,\left({\frac{1}{n}}\sum_{k=1}^{n}b_{k}\right)}$

∎

In our problem, $a_{i}=f_{i}\left(x\right)$ and
$b_{i}=\log\left[g_{i}\left(x\right)\right]$, $i=\overline{1,T}$. Under the
assumption that at each step, thanks to minimising $D_{var}$, the
approximation between the MoG and the Gaussian is adequate to preserve the
order of these values, that is, if $f_{i}\left(x\right)\leq
f_{j}\left(x\right)$, then $g_{i}\left(x\right)\leq g_{j}\left(x\right)$ and
$\log\left[g_{i}\left(x\right)\right]\leq\log\left[g_{j}\left(x\right)\right]$.
Without loss of generality, we hypothesise that $f_{1}\left(x\right)\leq
f_{2}\left(x\right)\leq...\leq f_{T}\left(x\right)$, then we have
$\log\left[g_{1}\left(x\right)\right]\leq\log\left[g_{2}\left(x\right)\right]\leq...\leq\log\left[g_{T}\left(x\right)\right]$.
Thus, applying Lemma LABEL:lem:Chebyshev's-sum-inequality:, we have

$\displaystyle\frac{1}{T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\log\left[g_{t}\left(x\right)\right]dx\geq$
$\displaystyle\frac{1}{T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\frac{1}{T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\log\left[g_{t}\left(x\right)\right]dx$
$\displaystyle\Rightarrow\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\log\left[g_{t}\left(x\right)\right]dx\geq$
$\displaystyle\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}\frac{1}{T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\log\left[g_{t}\left(x\right)\right]dx$
$\displaystyle\Rightarrow\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\log\left[g_{t}\left(x\right)\right]dx\geq$
$\displaystyle\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}\frac{1}{T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\log\left[\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}g_{t}\left(x\right)\right]dx$

Thus, the upper bound on the total timestep-wise $KL$ divergence reads

$\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\log\left[f_{t}\left(x\right)\right]dx\quad-\stackrel{{\scriptstyle[}}{{-}}\infty]{+\infty}{\int}\frac{1}{T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)\log\left[\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}g_{t}\left(x\right)\right]dx$

####  C.3 Proof
$\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}g_{t}\left(x\right)=\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi_{t}^{i}g_{t}^{i}\left(x\right)$
Is a Scaled MoG

######  Lemma C.2.

Product of two Gaussians is a scaled Gaussian.

###### Proof.

Let $\mathcal{N}_{x}\left(\mu,\Sigma\right)$ denote a density of $x$, then

$\mathcal{N}_{x}\left(\mu_{1},\Sigma_{1}\right)\cdot\mathcal{N}_{x}\left(\mu_{2},\Sigma_{2}\right)=c_{c}\mathcal{N}_{x}\left(\mu_{c},\Sigma_{c}\right)$

where

$\displaystyle c_{c}=$
$\displaystyle\frac{1}{\sqrt{\det\left(2\pi\left(\Sigma_{1}+\Sigma_{2}\right)\right)}}\exp\left(-\frac{1}{2}\left(m_{1}-m_{2}\right)^{T}\left(\Sigma_{1}+\Sigma_{2}\right)^{-1}\left(m_{1}-m_{2}\right)\right)$
$\displaystyle m_{c}=$
$\displaystyle\left(\Sigma_{1}^{-1}+\Sigma_{2}^{-1}\right)^{-1}\left(\Sigma_{1}^{-1}m_{1}+\Sigma_{2}^{-1}m_{2}\right)$
$\displaystyle\Sigma_{c}=$
$\displaystyle\left(\Sigma_{1}^{-1}+\Sigma_{2}^{-1}\right)$

∎

######  Lemma C.3.

Product of two MoGs is proportional to an MoG.

###### Proof.

Let
$g_{1}\left(x\right)=\stackrel{{\scriptstyle[}}{{i}}=1]{K_{1}}{\sum}\pi_{1,i}\mathcal{N}_{x}\left(\mu_{1,i},\Sigma_{1,i}\right)$
and
$g_{2}\left(x\right)=\stackrel{{\scriptstyle[}}{{j}}=1]{K_{2}}{\sum}\pi_{2,j}\mathcal{N}_{x}\left(\mu_{2,j},\Sigma_{2,j}\right)$
are two Mixtures of Gaussians. We have

$\displaystyle g_{1}\left(x\right)\cdot g_{2}\left(x\right)=$
$\displaystyle\stackrel{{\scriptstyle[}}{{i}}=1]{K_{1}}{\sum}\pi_{1,i}\mathcal{N}_{x}\left(\mu_{1,i},\Sigma_{1,i}\right)\cdot\stackrel{{\scriptstyle[}}{{j}}=1]{K_{2}}{\sum}\pi_{2,j}\mathcal{N}_{x}\left(\mu_{2,j},\Sigma_{2,j}\right)$
$\displaystyle=$
$\displaystyle\stackrel{{\scriptstyle[}}{{i}}=1]{K_{1}}{\sum}\stackrel{{\scriptstyle[}}{{,}}j=1]{K_{2}}{\sum}\pi_{1,i}\pi_{2,j}\mathcal{N}_{x}\left(\mu_{1,i},\Sigma_{1,i}\right)\cdot\mathcal{N}_{x}\left(\mu_{2,j},\Sigma_{2,j}\right)$
(8.2)

By applying Lemma C.2 to Eq. (8.2), we have

$\displaystyle g_{1}\left(x\right)\cdot g_{2}\left(x\right)=$
$\displaystyle\stackrel{{\scriptstyle[}}{{i}}=1]{K_{1}}{\sum}\stackrel{{\scriptstyle[}}{{,}}j=1]{K_{2}}{\sum}\pi_{1,i}\pi_{2,j}c_{ij}\mathcal{N}_{x}\left(\mu_{ij},\Sigma_{ij}\right)$
$\displaystyle=$
$\displaystyle\>C\stackrel{{\scriptstyle[}}{{i}}=1]{K_{1}}{\sum}\stackrel{{\scriptstyle[}}{{,}}j=1]{K_{2}}{\sum}\frac{\pi_{1,i}\pi_{2,j}c_{ij}}{C}\mathcal{N}_{x}\left(\mu_{ij},\Sigma_{ij}\right)$
(8.3)

where
$C=\stackrel{{\scriptstyle[}}{{i}}=1]{K_{1}}{\sum}\stackrel{{\scriptstyle[}}{{,}}j=1]{K_{2}}{\sum}\pi_{1,i}\pi_{2,j}c_{ij}$.
Clearly, Eq. (8.3) is proportional to an MoG with $K_{1}\cdot K_{2}$ modes ∎

######  Theorem C.1.

$\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}g_{t}\left(x\right)=\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi_{t}^{i}g_{t}^{i}\left(x\right)$
is a scaled MoG.

###### Proof.

By induction from Lemma C.3, we can easily show that product of $T$ MoGs is
also proportional to an MoG. That means
$\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}g_{t}\left(x\right)$ equals to a
scaled MoG. ∎

####  C.4 Details of Data Descriptions and Model Implementations

Here we list all datasets used in our experiments:

  * •

Open-domain datasets:

    * –

Cornell movie dialog: This corpus contains a large metadata-rich collection of
fictional conversations extracted from 617 raw movies with 220,579
conversational exchanges between 10,292 pairs of movie characters. For each
dialog, we preprocess the data by limiting the context length and the
utterance output length to 20 and 10, respectively. The vocabulary is kept to
top 20,000 frequently-used words in the dataset.

    * –

OpenSubtitles: This dataset consists of movie conversations in XML format. It
also contains sentences uttered by characters in movies, yet it is much bigger
and noisier than Cornell dataset. After preprocessing as above, there are more
than 1.6 million pairs of contexts and utterance with chosen vocabulary of
40,000 words.

  * •

Closed-domain datasets::

    * –

Live Journal (LJ) user question-answering dataset: question-answer dialog by
LJ users who are members of anxiety, arthritis, asthma, autism, depression,
diabetes, and obesity LJ communities111https://www.livejournal.com/. After
preprocessing as above, we get a dataset of more than 112,000 conversations.
We limit the vocabulary size to 20,000 most common words.

    * –

Reddit comments dataset: This dataset consists of posts and comments about
movies in Reddit website222https://www.reddit.com/r/movies/. A single post may
have multiple comments constituting a multi-people dialog amongst the poster
and commentors, which makes this dataset the most challenging one. We crawl
over four millions posts from Reddit website and after preprocessing by
retaining conversations whose utterance’s length are less than 20, we have a
dataset of nearly 200 thousand conversations with a vocabulary of more than 16
thousand words.

We trained with the following hyperparameters (according to the performance on
the validate dataset): word embedding has size 96 and is shared across
everywhere. We initialise the word embedding from Google’s Word2Vec Mikolov et
al. (2013) pretrained word vectors. The hidden dimension of LSTM in all
controllers is set to 768 for all datasets except the big OpenSubtitles whose
LSTM dimension is 1024\. The number of LSTM layers for every controller is set
to 3. All the initial weights are sampled from a normal distribution with mean
$0$, standard deviation 0.$1$. The mini-batch size is chosen as 256. The
models are trained end-to-end using the Adam optimiser Kingma and Ba (2014)
with a learning rate of 0.001 and gradient clipping at 10. For models using
memory, we set the number and the size of memory slots to 16 and 64,
respectively. As indicated previously, it is not trivial to optimise VAE with
RNN-like decoder due to the vanishing latent variable problem Bowman et al.
(2016). Hence, to make the variational models in our experiments converge we
have to use the $KL$ annealing trick by adding to the $KL$ loss term an
annealing coefficient $\alpha$ starts with a very small value and gradually
increase up to 1.

####  C.5 Full Reports on Model Performance

Model | BLEU-1 | BLEU-2 | BLEU-3 | BLEU-4 | A-glove
---|---|---|---|---|---
Seq2Seq | 18.4 | 14.5 | 12.1 | 9.5 | 0.52
Seq2Seq-att | 17.7 | 14.0 | 11.7 | 9.2 | 0.54
DNC | 17.6 | 13.9 | 11.5 | 9.0 | 0.51
CVAE | 16.5 | 13.0 | 10.9 | 8.5 | 0.56
VLSTM | 18.6 | 14.8 | 12.4 | 9.7 | 0.59
VMED (K=1) | 20.7 | 16.5 | 13.8 | 10.8 | 0.57
VMED (K=2) | 22.3 | 18.0 | 15.2 | 11.9 | 0.64
VMED (K=3) | 19.4 | 15.6 | 13.2 | 10.4 | 0.63
VMED (K=4) | 23.1 | 18.5 | 15.5 | 12.3 | 0.61
Table C.1: Results on Cornell Movies Model | BLEU-1 | BLEU-2 | BLEU-3 | BLEU-4 | A-glove
---|---|---|---|---|---
Seq2Seq | 11.4 | 8.7 | 7.1 | 5.4 | 0.29
Seq2Seq-att | 13.2 | 10.2 | 8.4 | 6.5 | 0.42
DNC | 14.3 | 11.2 | 9.3 | 7.2 | 0.47
CVAE | 13.5 | 10.2 | 8.4 | 6.6 | 0.45
VLSTM | 16.4 | 12.7 | 10.4 | 8.1 | 0.43
VMED (K=1) | 12.9 | 9.5 | 7.5 | 6.2 | 0.44
VMED (K=2) | 15.3 | 13.8 | 10.4 | 8.8 | 0.49
VMED (K=3) | 24.8 | 19.7 | 16.4 | 12.9 | 0.54
VMED (K=4) | 17.9 | 14.2 | 11.8 | 9.3 | 0.52
Table C.2: Results on OpenSubtitles Model | BLEU-1 | BLEU-2 | BLEU-3 | BLEU-4 | A-glove
---|---|---|---|---|---
Seq2Seq | 13.1 | 10.1 | 8.3 | 6.4 | 0.45
Seq2Seq-att | 11.4 | 8.7 | 7.1 | 5.6 | 0.49
DNC | 12.4 | 9.6 | 7.8 | 6.1 | 0.47
CVAE | 12.2 | 9.4 | 7.7 | 6.0 | 0.48
VLSTM | 11.5 | 8.8 | 7.3 | 5.6 | 0.46
VMED (K=1) | 13.7 | 10.7 | 8.9 | 6.9 | 0.47
VMED (K=2) | 15.4 | 12.2 | 10.1 | 7.9 | 0.51
VMED (K=3) | 18.1 | 14.8 | 12.4 | 9.8 | 0.49
VMED (K=4) | 14.4 | 11.4 | 9.5 | 7.5 | 0.47
Table C.3: Results on LJ users question-answering Model | BLEU-1 | BLEU-2 | BLEU-3 | BLEU-4 | A-glove
---|---|---|---|---|---
Seq2Seq | 7.5 | 5.5 | 4.4 | 3.3 | 0.31
Seq2Seq-att | 5.5 | 4.0 | 3.1 | 2.4 | 0.25
DNC | 7.5 | 5.6 | 4.5 | 3.4 | 0.28
CVAE | 5.3 | 4.3 | 3.6 | 2.8 | 0.39
VLSTM | 6.9 | 5.1 | 4.1 | 3.1 | 0.27
VMED (K=1) | 9.1 | 6.8 | 5.5 | 4.3 | 0.39
VMED (K=2) | 9.2 | 7.0 | 5.7 | 4.4 | 0.38
VMED (K=3) | 12.3 | 9.7 | 8.1 | 6.4 | 0.46
VMED (K=4) | 8.6 | 6.9 | 5.9 | 4.6 | 0.41
Table C.4: Results on Reddit comments

###  D Supplementary for Chapter 6

####  D.1 Derivation on the Bound Inequality in Linear Dynamic System

The linear dynamic system hidden state is described by the following recursive
equation

$h_{t}=Wx_{t}+Uh_{t-1}+b$

By induction,

$h_{t}=\stackrel{{\scriptstyle[}}{{i}}=1]{t}{\sum}U^{t-i}Wx_{i}+C$

where $C$ is some constant with respect to $x_{i}$. In this case,
$\frac{\partial h_{t}}{\partial x_{i}}=U^{t-i}W$. By applying norm sub-
multiplicativity333If not explicitly stated otherwise, norm refers to any
consistent matrix norm which satisfies sub-multiplicativity. ,

$\displaystyle c_{i-1,t}$ $\displaystyle=\left\|U^{t-i+1}W\right\|$
$\displaystyle\leq\left\|U\right\|\left\|U^{t-i}W\right\|$
$\displaystyle=\left\|U\right\|c_{i,t}$

That is, $\lambda_{c}=\left\|U\right\|$.

####  D.2 Derivation on the Bound Inequality in Standard RNN

The standard RNN hidden state is described by the following recursive equation

$h_{t}=\tanh\left(Wx_{t}+Uh_{t-1}+b\right)$

From $\frac{\partial h_{t}}{\partial x_{i}}=\frac{\partial h_{t}}{\partial
h_{t-1}}\frac{\partial h_{t-1}}{\partial x_{i}}$, by induction,

$\frac{\partial h_{t}}{\partial
x_{i}}=\left(\stackrel{{\scriptstyle[}}{{j}}=i+1]{t}{\prod}\frac{\partial
h_{j}}{\partial h_{j-1}}\right)\frac{\partial h_{i}}{\partial
x_{i}}=\left(\stackrel{{\scriptstyle[}}{{j}}=i]{t}{\prod}diag\left(\tanh^{\prime}\left(a_{j}\right)\right)\right)U^{t-i}W$

where $a_{j}=Wx_{j}+Uh_{j-1}+b$ and $diag\left(\cdot\right)$ converts a vector
into a diagonal matrix. As
$0\leq\tanh^{\prime}\left(x\right)=1-\tanh\left(x\right)^{2}\leq 1$,
$\left\|diag\left(\tanh^{\prime}\left(X\right)\right)\right\|$ is bounded by
some value $B$. By applying norm sub-multiplicativity,

$\displaystyle c_{i-1,t}$
$\displaystyle=\left\|\left[\stackrel{{\scriptstyle[}}{{j}}=i]{t}{\prod}diag\left(\tanh^{\prime}\left(a_{j}\right)\right)\right]diag\left(\tanh^{\prime}\left(a_{i-1}\right)\right)U^{t-i+1}W\right\|$
$\displaystyle\leq\left\|U\right\|\left\|\stackrel{{\scriptstyle[}}{{j}}=i]{t}{\prod}diag\left(\tanh^{\prime}\left(a_{j}\right)\right)U^{t-i}W\right\|\left\|diag\left(\tanh^{\prime}\left(a_{i-1}\right)\right)\right\|$
$\displaystyle=B\left\|U\right\|c_{i,t}$

That is, $\lambda_{c}=B\left\|U\right\|$.

####  D.3 Derivation on the Bound Inequality in LSTM

For the case of LSTM, the recursive equation reads

$\displaystyle c_{t}$
$\displaystyle=\sigma\left(U_{f}x_{t}+W_{f}h_{t-1}+b_{f}\right)\odot c_{t-1}$
$\displaystyle+\sigma\left(U_{i}x_{t}+W_{i}h_{t-1}+b_{i}\right)\odot\tanh\left(U_{z}x_{t}+W_{z}h_{t-1}+b_{z}\right)$
$\displaystyle h_{t}$
$\displaystyle=\sigma\left(U_{o}x_{t}+W_{o}h_{t-1}+b_{o}\right)\odot\tanh\left(c_{t}\right)$

Taking derivatives,

$\displaystyle\frac{\partial h_{j}}{\partial h_{j-1}}$
$\displaystyle=\sigma^{\prime}\left(o_{j}\right)\tanh\left(c_{j}\right)W_{o}+\sigma\left(o_{j}\right)\tanh^{\prime}\left(c_{j}\right)\sigma^{\prime}\left(f_{j}\right)c_{j-1}W_{f}$
$\displaystyle+\sigma\left(o_{j}\right)\tanh^{\prime}\left(c_{j}\right)\sigma^{\prime}\left(i_{j}\right)\tanh\left(z_{j}\right)W_{i}+\sigma\left(o_{j}\right)\tanh^{\prime}\left(c_{j}\right)\sigma\left(i_{j}\right)\tanh^{\prime}\left(z_{j}\right)W_{z}$
$\displaystyle\frac{\partial h_{j-1}}{\partial x_{j-1}}$
$\displaystyle=\sigma^{\prime}\left(o_{j-1}\right)\tanh\left(c_{j-1}\right)U_{o}+\sigma\left(o_{j-1}\right)\tanh^{\prime}\left(c_{j-1}\right)\sigma^{\prime}\left(f_{j-1}\right)c_{j-2}U_{f}$
$\displaystyle+\sigma\left(o_{j-1}\right)\tanh^{\prime}\left(c_{j-1}\right)\sigma^{\prime}\left(i_{j-1}\right)\tanh\left(z_{j-1}\right)U_{i}$
$\displaystyle+\sigma\left(o_{j-1}\right)\tanh^{\prime}\left(c_{j-1}\right)\sigma\left(i_{j-1}\right)\tanh^{\prime}\left(z_{j-1}\right)U_{z}$
$\displaystyle\frac{\partial h_{j}}{\partial x_{j}}$
$\displaystyle=\sigma^{\prime}\left(o_{j}\right)\tanh\left(c_{j}\right)U_{o}+\sigma\left(o_{j}\right)\tanh^{\prime}\left(c_{j}\right)\sigma^{\prime}\left(f_{j}\right)c_{j-1}U_{f}$
$\displaystyle+\sigma\left(o_{j}\right)\tanh^{\prime}\left(c_{j}\right)\sigma^{\prime}\left(i_{j}\right)\tanh\left(z_{j}\right)U_{i}+\sigma\left(o_{j}\right)\tanh^{\prime}\left(c_{j}\right)\sigma\left(i_{j}\right)\tanh^{\prime}\left(z_{j}\right)U_{z}$

where $o_{j}$ denotes the value in the output gate at $j$-th timestep (similar
notations are used for input gate ($i_{j}$), forget gate ($f_{j}$) and cell
value ($z_{j}$)) and “non-matrix” terms actually represent diagonal matrices
corresponding to these terms. Under the assumption that $h_{0}$=0, we then
make use of the results stating that $\left\|c_{t}\right\|_{\infty}$ is
bounded for all $t$ Miller and Hardt (2018) . By applying $l_{\infty}$-norm
sub-multiplicativity and triangle inequality, we can show that

$\frac{\partial h_{j}}{\partial h_{j-1}}\frac{\partial h_{j-1}}{\partial
x_{j-1}}=M\frac{\partial h_{j}}{\partial x_{j}}+N$

with

$\displaystyle\left\|M\right\|_{\infty}$ $\displaystyle\leq
1/4\left\|W_{o}\right\|_{\infty}+1/4\left\|W_{f}\right\|_{\infty}\left\|c_{j}\right\|_{\infty}+1/4\left\|W_{i}\right\|_{\infty}+\left\|W_{z}\right\|_{\infty}=B_{m}$
$\displaystyle\left\|N\right\|_{\infty}$ $\displaystyle\leq
1/16\left\|W_{o}U_{i}\right\|_{\infty}+1/16\left\|W_{o}U_{f}\right\|_{\infty}\left(\left\|c_{j}\right\|_{\infty}+\left\|c_{j-1}\right\|_{\infty}\right)+1/4\left\|W_{o}U_{z}\right\|_{\infty}$
$\displaystyle+1/16\left\|W_{i}U_{o}\right\|_{\infty}+1/16\left\|W_{i}U_{f}\right\|_{\infty}\left(\left\|c_{j}\right\|_{\infty}+\left\|c_{j-1}\right\|_{\infty}\right)+1/4\left\|W_{i}U_{z}\right\|_{\infty}$
$\displaystyle+1/16\left(\left\|W_{f}U_{o}\right\|_{\infty}+1/16\left\|W_{f}U_{i}\right\|_{\infty}+1/4\left\|W_{f}U_{z}\right\|_{\infty}\right)\left(\left\|c_{j}\right\|_{\infty}+\left\|c_{j-1}\right\|_{\infty}\right)$
$\displaystyle+1/4\left\|W_{z}U_{o}\right\|_{\infty}+1/4\left\|W_{z}U_{f}\right\|_{\infty}\left(\left\|c_{j}\right\|_{\infty}+\left\|c_{j-1}\right\|_{\infty}\right)+1/4\left\|W_{z}U_{i}\right\|_{\infty}$
$\displaystyle=B_{n}$

By applying $l_{\infty}$-norm sub-multiplicativity and triangle inequality,

$\displaystyle c_{i-1,t}$
$\displaystyle=\left\|\stackrel{{\scriptstyle[}}{{j}}=i+1]{t}{\prod}\frac{\partial
h_{j}}{\partial h_{j-1}}\frac{\partial h_{i}}{\partial h_{i-1}}\frac{\partial
h_{i-1}}{\partial x_{i-1}}\right\|_{\infty}$
$\displaystyle=\left\|\stackrel{{\scriptstyle[}}{{j}}=i+1]{t}{\prod}\frac{\partial
h_{j}}{\partial h_{j-1}}\left(\frac{\partial h_{i}}{\partial
x_{i}}m+n\right)\right\|_{\infty}$ $\displaystyle\leq
B_{m}c_{i,t}+B_{n}\stackrel{{\scriptstyle[}}{{j}}=i+1]{t}{\prod}\left\|\frac{\partial
h_{j}}{\partial h_{j-1}}\right\|_{\infty}$

As LSTM is $\lambda$-contractive with $\lambda<1$ in the $l_{\infty}$-norm
(readers are recommended to refer to Miller and Hardt, (2018) for proof),
which implies $\left\|\frac{\partial h_{j}}{\partial
h_{j-1}}\right\|_{\infty}<1$,
$B_{n}\stackrel{{\scriptstyle[}}{{j}}=i+1]{t}{\prod}\left\|\frac{\partial
h_{j}}{\partial h_{j-1}}\right\|_{\infty}\rightarrow 0$ as
$t-i\rightarrow\infty$. For $t-i<\infty$, under the assumption that
$\frac{\partial h_{j}}{\partial x_{j}}\neq 0$, we can always find some value
$B<\infty$ such that $c_{i-1,t}\leq Bc_{i,t}$. For $t-i\rightarrow\infty$,
$\lambda_{c}\rightarrow B_{m}$. That is,
$\lambda_{c}=\max\left(B_{m},B\right)$.

####  D.4 Proof of Theorem 6.1

###### Proof.

Given that $\lambda_{c}c_{i,t}\geq c_{i-1,t}$ with some
$\lambda_{c}\in\mathbb{R^{+}}$, we can use $c_{t,t}\lambda_{c}^{t-i}$ as the
upper bound on $c_{i,t}$ with $i=\overline{1,t}$, respectively. Therefore,

$f(0)\leq\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}c_{t,T}\leq
c_{T,T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\lambda_{c}^{T-t}=f\left(\lambda_{c}\right)$

where
$f(\lambda)=c_{T,T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\lambda^{T-t}$
is continuous on $\mathbb{R^{+}}$. According to intermediate value theorem,
there exists $\lambda\in\left(0,\lambda_{c}\right]$ such that
$c_{T,T}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\lambda^{T-t}=\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}c_{t,T}$.
∎

####  D.5 Proof of Theorem 6.2

###### Proof.

According to Theorem 6.1, there exists some $\lambda_{i}\in\mathbb{R^{+}}$such
that the summation of contribution stored between $K_{i}$ and $K_{i+1}$ can be
quantified as
$c_{K_{i+1},K_{i+1}}\stackrel{{\scriptstyle[}}{{t}}=K_{i}]{K_{i+1}}{\sum}\lambda_{i}^{K_{i+1}-t}$
(after ignoring contributions before $K_{i}$-th timestep for simplicity). Let
denote
$P(\lambda)=\stackrel{{\scriptstyle[}}{{t}}=K_{i}]{K_{i+1}}{\sum}\lambda^{K_{i+1}-t}$,
we have $P^{\prime}\left(\lambda\right)>0,\mathbb{\forall\lambda\in R^{+}}$.
Therefore, $P(\lambda_{i})\geq
P\left(\underset{i}{\min}\left(\lambda_{i}\right)\right)$. Let
$C=\underset{i}{\min}\left(c_{i,i}\right)$ and
$\lambda=\underset{i}{\min}\left(\lambda_{i}\right)$, the average contribution
stored in a MANN has a lower bound quantified as $I_{\lambda}$, where

$I_{\lambda}=C\frac{\stackrel{{\scriptstyle[}}{{t}}=1]{K_{1}}{\sum}\lambda^{K_{1}-t}+\stackrel{{\scriptstyle[}}{{t}}=K_{1}+1]{K_{2}}{\sum}\lambda^{K_{2}-t}+...+\stackrel{{\scriptstyle[}}{{t}}=K_{D-1}+1]{K_{D}}{\sum}\lambda^{K_{D}-t}+\stackrel{{\scriptstyle[}}{{t}}=K_{D}+1]{T}{\sum}\lambda^{T-t}}{T}$
(8.4)

. ∎

####  D.6 Proof of Theorem 6.3

###### Proof.

The second-order derivative of $f_{\lambda}\left(x\right)$ reads

$f_{\lambda}^{\prime\prime}\left(x\right)=-\frac{\left(\ln\lambda\right)^{2}}{1-\lambda}\lambda^{x}$
(8.5)

We have $f_{\lambda,}^{\prime\prime}\left(x\right)\leq 0$ with $\forall
x\in\mathbb{R^{+}}$ and $1>\lambda>0$, so $f_{\lambda}\left(x\right)$ is a
concave function. Thus, we can apply Jensen inequality as follows:

$\frac{1}{D+1}\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}f_{\lambda}(l_{i})\leq
f_{\lambda}\left(\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}\frac{1}{D+1}l_{i}\right)=f_{\lambda}\left(\frac{T}{D+1}\right)$
(8.6)

Equality holds if and only if $l_{1}=l_{2}=...=l_{D+1}=\frac{T}{D+1}$. We
refer to this as Uniform Writing strategy. By plugging the optimal values of
$l_{i}$, we can derive the maximised average contribution as follows,

$I_{\lambda}max\equiv
g_{\lambda}\left(T,D\right)=\frac{C\left(D+1\right)}{T}\left(\frac{1-\lambda^{\frac{T}{D+1}}}{1-\lambda}\right)$
(8.7)

When $\lambda=1$,
$I_{\lambda}=\frac{C}{T}\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}l_{i}=C$.
This is true for all writing strategies. Thus, Uniform Writing is optimal for
$0<\lambda\leq 1$. ∎

We can show that this solution is also optimal for the case $\lambda>1$. As
$f_{\lambda}^{\prime\prime}\left(x\right)>0$ with $\forall
x\in\mathbb{R^{+}};\lambda>1$, $f_{\lambda}\left(x\right)$ is a convex
function and Eq. (8.6) flips the inequality sign. Thus, $I_{\lambda}$ reaches
its minimum with Uniform Writing. For $\lambda>1$, minimising $I_{\lambda}$ is
desirable to prevent the system from diverging.

We can derive some properties of function $g$. Let
$x=\frac{D+1}{L},g_{\lambda}\left(L,D\right)=g_{\lambda}\left(x\right)=Cx(\frac{\lambda^{\frac{1}{x}}-1}{\lambda-1})$.
We have
$g_{\lambda}^{\prime}\left(x\right)=C\lambda\left(1-\lambda^{\frac{1}{x}}\right)\left(x-\ln\lambda\right)>0$
with $0<\lambda\leq 1,\forall x\geq 0$, so $g_{\lambda}\left(T,D\right)$ is an
increasing function if we fix $T$ and let $D$ vary. That explains why having
more memory slots helps improve memorisation capacity. If $D=0$,
$g_{\lambda}\left(T,0\right)$ becomes E.q (6.5). In this case, MANNs
memorisation capacity converges to that of recurrent networks.

####  D.7 Summary of Synthetic Discrete Task Format

Task | Input | Output
---|---|---
Double | $x_{1}x_{2}...x_{T}$ | $x_{1}x_{2}...x_{T}x_{1}x_{2}...x_{T}$
Copy | $x_{1}x_{2}...x_{T}$ | $x_{1}x_{2}...x_{T}$
Reverse | $x_{1}x_{2}...x_{T}$ | $x_{T}x_{T-1}...x_{1}$
Add | $x_{1}x_{2}...x_{T}$ | $\frac{x_{1}+x_{T-1}}{2}\frac{x_{2}+x_{T-2}}{2}...\frac{x_{\left\lfloor T/2\right\rfloor}+x_{\left\lceil T/2\right\rceil}}{2}$
Max | $x_{1}x_{2}...x_{T}$ | $\max\left(x_{1},x_{2}\right)\max\left(x_{3},x_{4}\right)...\max\left(x_{T-1},x_{T}\right)$
Table D.1: Synthetic discrete task’s input-output formats. $T$ is the sequence
length.

####  D.8 UW Performance on Bigger Memory

Model | $N_{h}$ | Copy (L=500)
---|---|---
DNC | 128 | 24.19%
DNC+UW | 128 | 81.45%
Table D.2: Test accuracy (%) on synthetic copy task. MANNs have 50 memory
slots. Both models are trained with 100,000 mini-batches of size 32.

####  D.9 Memory Operating Behaviors on Synthetic Tasks

In this section, we pick three models (DNC, DNC+UW and DNC+CUW) to analyse
their memory operating behaviors. Fig. D.1 visualises the values of the write
weights and read weights for the copy task during encoding input and decoding
output sequence, respectively. In the copy task, as the sequence length is 50
while the memory size is 4, one memory slot should contain the accumulation of
multiple timesteps. This principle is reflected in the decoding process in
three models, in which one memory slot is read repeatedly across several
timesteps. Notably, the number of timesteps consecutively spent for one slot
is close to $10$-the optimal interval, even for DNC ( Fig. D.1(a)), which
implies that the ultimate rule would be the uniform rule. As UW and CUW are
equipped with uniform writing, their writing patterns follow the rule
perfectly. Interestingly, UW chooses the first written location for the final
write (corresponding to the <eos> token) while CUW picks the last written
location. As indicated in Figs. D.1(b) and (c), both of them can learn the
corresponding reading pattern for decoding process, which leads to good
performances. On the other hand, regular DNC fails to learn a perfect writing
strategy. Except for the timesteps at the end of the sequence, the timesteps
are distributed to several memory slots while the reading phase attends to one
memory slot repeatedly. This explains why regular DNC cannot compete with the
other two proposed methods in this task.

For the max task, Fig. D.2 displays similar visualisation with an addition of
write gate during encoding phase. The write gate indicates how much the model
should write the input at some timestep to the memory. A zero write gate means
there is no writing. For this task, a good model should discriminate between
timesteps and prefer writing the greater ones. As clearly seen in Fig. D.2(a),
DNC suffers the same problem as in copy task, unable to synchronise encoding
writing with decoding reading. Also, DNC’s write gate pattern does not show
reasonable discrimination. For UW (Fig. D.2(b)), it tends to write every
timestep and relies on uniform writing principle to achieve write/read
accordance and thus better results than DNC. Amongst all, CUW is able to
ignore irrelevant timesteps and follows uniform writing at the same time (see
Fig. D.2(c)).

Figure D.1: Memory operations on copy task in DNC (a), DNC+UW (b) and
DNC+CUW(c). Each row is a timestep and each column is a memory slot. Figure
D.2: Memory operations on max task in DNC (a), DNC+UW (b) and DNC+CUW(c). Each
row is a timestep and each column is a memory slot.

####  D.10 Visualisations of Model Performance on Sinusoidal Regression Tasks

We pick randomly 3 input sequences and plot the output sequences produced by
DNC, UW and CUW in Figs. D.3 (clean) and D.4 (noisy). In each plot, the first
and last 100 timesteps correspond to the given input and generated output,
respectively. The ground truth sequence is plotted in red while the predicted
in blue. We also visualise the values of MANN write gates through time in the
bottom of each plots. In irregular writing encoding phase, the write gate is
computed even when there is no write as it reflects how much weight the
controller puts on the timesteps. In decoding, we let MANNs write to memory at
every timestep to allow instant update of memory during inference.

Under clean condition, all models seem to attend more to late timesteps during
encoding, which makes sense as focusing on late periods of sine wave is enough
for later reconstruction. However, this pattern is not clear in DNC and UW as
in CUW. During decoding, the write gates tend to oscillate in the shape of
sine wave, which is also a good strategy as this directly reflects the
amplitude of generation target. In this case, both UW and CUW demonstrate this
behavior clearer than DNC.

Under noisy condition, DNC and CUW try to follow sine-shape writing strategy.
However, only CUW can learn the pattern and assign write values in accordance
with the signal period, which helps CUW decoding achieve highest accuracy. On
the other hand, UW choose to assign write value equally and relies only on its
maximisation of timestep contribution. Although it achieves better results
than DNC, it underperforms CUW.

Figure D.3: Sinusoidal generation with clean input sequence for DNC, UW and
CUW in top-down order.

Figure D.4: Sinusoidal generation with noisy input sequence for DNC, UW and
CUW in top-down order.

####  D.11 Comparison with Non-Recurrent Methods in Flatten Image
Classification Task

Model | MNIST | pMNIST
---|---|---
The Transformer⋆ | 98.9 | 97.9
Dilated CNN◆ | 98.3 | 96.7
DNC+CUW | 99.1 | 96.3
Table D.3: Test accuracy (%) on MNIST, pMNIST. Previously reported results are
from Vaswani et al., (2017)⋆ and Chang et al., (2017)◆.

####  D.12 Details on Document Classification Datasets

Dataset | Classes |  Average lengths |  Max lengths |  Train samples |  Test samples
---|---|---|---|---|---
IMDb | 2 |  282 |  2,783 |  25,000 |  25,000
Yelp Review Polarity (Yelp P.) | 2 |  156 |  1,381 |  560,000 |  38,000
Yelp Review Full (Yelp F.) | 5 |  158 |  1,381 |  650,000 |  50,000
AG’s News (AG) | 4 |  44 |  221 |  120,000 |  7,600
DBPedia (DBP) | 14 |  55 |  1,602 |  560,000 |  70,000
Yahoo! Answers (Yah. A.) | 10 |  112 |  4,392 |  1,400,000 |  60,000
Table D.4: Statistics on several big document classification datasets

####  D.13 Document Classification Detailed Records

Model | AG | IMDb | Yelp P. | Yelp F.
---|---|---|---|---
UW | 1 | 93.42 | 91.39 | 96.39 | 64.89
2 | 93.52 | 91.30 | 96.31 | 64.97
3 | 93.69 | 91.25 | 96.39 | 65.26
Mean/Std | 93.54$\pm$0.08 | 91.32$\pm$0.04 | 96.36$\pm$0.03 | 65.04$\pm$0.11
CUW | 1 | 93.61 | 91.26 | 96.42 | 65.63
2 | 93.87 | 91.18 | 96.29 | 65.05
3 | 93.70 | 91.32 | 96.36 | 64.80
Mean/Std | 93.73$\pm$0.08 | 91.25$\pm$0.04 | 96.36$\pm$0.04 | 65.16$\pm$0.24
Table D.5: Document classification accuracy (%) on several datasets reported
for 3 different runs. Bold denotes the best records.

###  E Supplementary for Chapter 7

####  E.1 Full Learning Curves on Single NTM Tasks

Figure E.1: Learning curves on NTM tasks.

####  E.2 Clustering on The Latent Space

As previously mentioned in Sec. 3.3, MANN should let its states form clusters
to well-simulate Turing Machine. Fig. E.2 (a) and (c) show NTM actually
organises its $c_{t}$ space into clusters corresponding to processing states
(e.g, encoding and decoding). NUTM, which explicitly partitions this space,
clearly learn better clusters of $c_{t}$ (see Fig. E.2 (b) and (d)). This
contributes to NUTM’s outperformance over NTM.

Figure E.2: Visualisation of the first two principal components of $c_{t}$
space in NTM (a,c) and NUTM (b,d) for Copy (red) and Repeat Copy (blue). Fader
color denotes lower timestep in a sequence. Both can learn clusters of hidden
states yet NUTM exhibits clearer partition.

####  E.3 Program Usage Visualisations

E.3.1 and E.3.2 visualise the best inferences of NUTM on test data from single
and sequencing tasks. Each plot starts with the input sequence and the
predicted output sequence with error bits in the first row. The second and
fourth rows depict the read and write locations on data memory, respectively.
The third and fifth rows depict the program distribution of the read head and
write head, respectively. E.3.3 visualises random failed predictions of NTM on
sequencing tasks. The plots follow previous pattern except for the program
distribution rows.

#####  E.3.1 Visualisation on Program Distribution across Timesteps (Single
Tasks)

Figure E.3: Copy (p=2). Figure E.4: Repeat Copy (p=2). Figure E.5: Associative
Recall (p=2). Figure E.6: Dynamic N-grams (p=2). Figure E.7: Priority Sort
(p=2). Figure E.8: Long Copy (p=2).

#####  E.3.2 Visualisation on Program Distribution across Timesteps
(Sequencing Tasks)

Figure E.9: Copy+Repeat Copy (p=3). Figure E.10: Copy+Associative Recall
(p=3). Figure E.11: Copy+Priority Sort (p=3). Figure E.12: Copy+Repeat
Copy+Associative Recall+Priority Sort (p=4).

#####  E.3.3 Perseveration Phenomenon in NTM (Sequencing Tasks)

Figure E.13: Copy+Repeat Copy perseveration (only Repeat Copy). Figure E.14:
Copy+Associative Recall perseveration (only Copy). Figure E.15: Copy+Priority
Sort perseveration (only Copy). Figure E.16: Copy+Repeat Copy+Associative
Recall+Priority Sort perseveration (only Repeat Copy).

####  E.4 Details on Synthetic Tasks

#####  E.4.1 NTM Single Tasks

Tasks | #Head | Controller Size | Memory Size | #Parameters
---|---|---|---|---
NTM | NUTM | NTM | NUTM | NTM | NUTM | NTM | NUTM
Copy | 1 | 1 | 100 | 80 | 128 | 128 | 63,260 | 52,206
Repeat Copy | 1 | 1 | 100 | 80 | 128 | 128 | 63,381 | 52,307
Associative Recall | 1 | 1 | 100 | 80 | 128 | 128 | 62,218 | 51,364
Dynamic N-grams | 1 | 1 | 100 | 80 | 128 | 128 | 58,813 | 48,619
Priority Sort | 5 | 5 | 200 | 150 | 128 | 128 | 344,068 | 302,398
Long Copy | 1 | 1 | 100 | 80 | 256 | 256 | 63,260 | 52,206
Table E.1: Model hyper-parameters (single tasks). Tasks | Training | Testing
---|---|---
Copy | Sequence length range: [1, 20] | Sequence length: 120
Repeat Copy | Sequence length range: [1, 10] | Sequence length range: [10, 20]
#Repeat range: [1, 10] | #Repeat range: [10, 20]
Associative Recall | Sequence length: 3 | Sequence length: 3
#Item range: [2, 6] | #Item range: [6, 20]
Item length: 3 | Item length: 3
Dynamic N-grams | Sequence length: 50 | Sequence length: 200
Priority Sort | #Item: 20 | #Item: 20
#Sorted Item: 16 | #Sorted Item: 20
Long Copy | Sequence length range: [1, 40] | Sequence length: 200
Table E.2: Task settings (single tasks).

#####  E.4.2 NTM Sequencing Tasks

Tasks | #Head | Controller Size | Memory Size | #Parameters
---|---|---|---|---
NTM | NUTM | NTM | NUTM | NTM | NUTM | NTM | NUTM
C+RC | 1 | 1 | 200 | 150 | 128 | 128 | 206,481 | 153,941
C+AR | 1 | 1 | 200 | 150 | 128 | 128 | 206,260 | 153,770
C+PS | 3 | 3 | 200 | 150 | 128 | 128 | 275,564 | 263,894
C+RC+AR+PS | 3 | 3 | 250 | 200 | 128 | 128 | 394,575 | 448,379
Table E.3: Model hyper-parameters (sequencing tasks). Tasks | Training | Testing
---|---|---
C+RC | Sequence length range: [1, 10] | Sequence length range: [10, 20]
#Repeat range: [1, 10] | #Repeat range: [10, 15]
C+AR | Sequence length range: [1, 10] | Sequence length range: [10, 20]
#Item range: [2, 4] | #Item range: [4, 6]
Item length: 8 | Item length: 8
C+PS | Sequence length range: [1, 10] | Sequence length range: [10, 20]
#Item: 10 | #Item: 10
#Sorted Item: 8 | #Sorted Item: 10
C+RC+AR+PS | Sequence length range: [1, 10] | Sequence length range: [10, 20]
#Repeat range: [1, 5] | #Repeat: 6
#Item range: [2, 4] | #Item: 5
Item length: 6 | Item length: 6
#Item: 10 | #Item: 10
#Sorted Item: 8 | #Sorted Item: 10
Table E.4: Task settings (sequencing tasks).

#####  E.4.3 Continual Procedure Learning Tasks

Tasks | Training | Testing
---|---|---
Copy | Sequence length range: [1, 10] | Sequence length range: [1, 10]
Repeat Copy | Sequence length range: [1, 5] | Sequence length range: [1, 5]
#Repeat range: [1, 5] | #Repeat range: [1, 5]
Associative Recall | Sequence length: 3 | Sequence length: 3
#Item range: [2, 3] | #Item range: [2, 3]
Item length: 3 | Item length: 3
Priority Sort | #Item: 10 | #Item: 10
#Sorted Item: 8 | #Sorted Item: 8
Table E.5: Task settings (continual procedure learning tasks).

####  E.5 Details on Few-Shot Learning Task

We use similar hyper-parameters as in Santoro et al. (2016), which are
reported in Tab. E.6.

Model | $p$ | #Head | Controller Size | $N$ | $M$ |  $\mathbf{M}_{p}.K$ Size | Optimiser | Learning Rate
---|---|---|---|---|---|---|---|---
MANN (LRUA) | 1 | 4 | 200 | 128 | 40 | 0 | RMSprop | $10^{-4}$
NUTM (LRUA) | 2 | 4 | 180 | 128 | 40 | 2 | RMSprop | $10^{-4}$
NUTM (LRUA) | 3 | 4 | 150 | 128 | 40 | 3 | RMSprop | $10^{-4}$
Table E.6: Hyper-parameters for few-shot learning.

Testing accuracy through time is listed below,

Figure E.17: Testing accuracy during training (five random classes/episode,
one-hot vector labels, of length 50). Figure E.18: Testing accuracy during
training (ten random classes/episode, one-hot vector labels, of length 75).

Final testing accuracy is listed as follows,

Model | Persistent | 5 classes | 10 classes
---|---|---|---
memory444If the memory is not artificially erased between episodes, it is called persistent. This mode is hard for the case of 5 classes Santoro et al. (2016) | $2^{nd}$ | $3^{rd}$ | $5^{th}$ | $2^{nd}$ | $3^{rd}$ | $5^{th}$
MANN (LRUA)* | No | 82.8 | 91.0 | 94.9 | - | - | -
MANN (LRUA) | No | 82.3 | 88.7 | 92.3 | 52.7 | 60.6 | 64.7
NUTM (LRUA) | No | 85.7 | 91.3 | 95.5 | 68.0 | 78.1 | 82.8
Human* | Yes | 57.3 | 70.1 | 81.4 | - | - | -
MANN (LRUA)* | Yes | $\approx 58.0$ | - | $\approx 75.0$ | $\approx 60.0$ | - | $\approx 80.0$
MANN (LRUA) | Yes | 66.2 | 73.4 | 81.0 | 51.3 | 59.2 | 63.3
NUTM (LRUA) | Yes | 77.8 | 85.8 | 89.8 | 69.0 | 77.9 | 82.7
Table E.7: Test-set classification accuracy (%) on the Omniglot dataset after
100,000 episodes of training. * denotes available results from Santoro et al.,
(2016) (some are estimated from plotted figures).

It should be noted that our goal was not to achieve state of the art
performance on this dataset. It was to exhibit the benefit of NSM to MANN.
Compared to current methods, the MANN and NUTM used in our experiments do not
use CNN to extract visual features, thus achieve lower accuracy.

####  E.6 Details on bAbI Task

We train the models using RMSprop optimiser with fixed learning rate of
$10^{-4}$ and momentum of 0.9. The batch size is 32 and we adopt layer
normalisation Lei Ba et al. (2016) to DNC’s layers. Following common practices
Franke et al. (2018), we also remove temporal linkage for faster training. The
details of hyper-parameters are listed in Table E.8. Full NUTM ($p=4$) results
are reported in Table E.9.

#Head | Controller Size | $N$ | $M$ | $p$ |  $\mathbf{M}_{p}.K$ Size | #Parameters
---|---|---|---|---|---|---
4 | 172 | 196 | 64 | 4 | 4 | 794,773
4 | 200 | 196 | 64 | 2 | 2 | 934,787
Table E.8: NUTM hyper-parameters for bAbI. Task | bAbI Best Results | bAbI Mean Results
---|---|---
1: 1 supporting fact | 0.0 | 0.0 $\pm$ 0.0
2: 2 supporting facts | 0.2 | 0.6 $\pm$ 0.3
3: 3 supporting facts | 4.0 | 7.6 $\pm$ 3.9
4: 2 argument relations | 0.0 | 0.0 $\pm$ 0.0
5: 3 argument relations | 0.4 | 1.0 $\pm$ 0.4
6: yes/no questions | 0.0 | 0.0 $\pm$ 0.0
7: counting | 1.9 | 1.5 $\pm$ 0.8
8: lists/sets | 0.6 | 0.3 $\pm$ 0.2
9: simple negation | 0.0 | 0.0 $\pm$ 0.0
10: indefinite knowledge | 0.1 | 0.1 $\pm$ 0.0
11: basic coreference | 0.0 | 0.0 $\pm$ 0.0
12: conjunction | 0.0 | 0.0 $\pm$ 0.0
13: compound coreference | 0.1 | 0.0 $\pm$ 0.0
14: time reasoning | 0.3 | 1.6 $\pm$ 2.2
15: basic deduction | 0.0 | 2.6 $\pm$ 8.3
16: basic induction | 49.3 | 52.0 $\pm$ 1.7
17: positional reasoning | 4.7 | 18.4 $\pm$ 12.7
18: size reasoning | 0.4 | 1.6 $\pm$ 1.1
19: path finding | 4.3 | 23.7 $\pm$ 32.2
20: agent’s motivation | 0.0 | 0.0 $\pm$ 0.0
Mean Error (%) | 3.3 | 5.6 $\pm$ 1.9
Failed (Err. >5%) | 1 | 3 $\pm$ 1.2
Table E.9: NUTM ($p=4$) bAbI best and mean errors (%).

####  E.7 Others

If we deliberately set the key dimension equal to the number of programs, we
can even place an orthogonal basis constraint on the key space of NSM by
minimising the following loss,

$l_{p_{2}}=\left\|\mathbf{M}_{p}.K\mathbf{M}_{p}.K^{T}-\mathbf{I}\right\|$
(8.8)

where $\mathbf{M}_{p}.K$ and $\mathbf{I}$ denote the key part in NSM and the
identity matrix, respectively.

For all tasks, $\eta_{t}$ is fixed to $0.1$, reducing with decay rate of
$0.9$.

## References

  * Amit (1992) Daniel J Amit.  _Modeling brain function: The world of attractor neural networks_.  Cambridge university press, 1992.
  * Andreas et al. (2016a) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein.  Learning to compose neural networks for question answering.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1545–1554, 2016a.  doi: 10.18653/v1/N16-1181.  URL https://www.aclweb.org/anthology/N16-1181.
  * Andreas et al. (2016b) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein.  Neural module networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 39–48, 2016b.
  * Andrew Gelman (2006) Jennifer Hill Andrew Gelman.  _Data Analysis Using Regression and Multilevel/Hierarchical Models_.  Cambridge University Press, 2006.
  * Arjovsky et al. (2016) Martin Arjovsky, Amar Shah, and Yoshua Bengio.  Unitary evolution recurrent neural networks.  In _International Conference on Machine Learning_ , pages 1120–1128, 2016.
  * Arpit et al. (2017) Devansh Arpit, Stanisław Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al.  A closer look at memorization in deep networks.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 233–242. JMLR. org, 2017.
  * Ba et al. (2016) Jimmy Ba, Geoffrey E Hinton, Volodymyr Mnih, Joel Z Leibo, and Catalin Ionescu.  Using fast weights to attend to the recent past.  In _Advances in Neural Information Processing Systems_ , pages 4331–4339, 2016.
  * Bacharoglou (2010) Athanassia Bacharoglou.  Approximation of probability distributions by convex mixtures of gaussian measures.  _Proceedings of the American Mathematical Society_ , 138(7):2619–2628, 2010.
  * Baddeley (1992) Alan Baddeley.  Working memory.  _Science_ , 255(5044):556–559, 1992.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _Proceedings of the International Conference on Learning Representations_ , 2015.
  * Bajor and Lasko (2017) Jacek M Bajor and Thomas A Lasko.  Predicting medications from diagnostic codes with recurrent neural networks.  In _International Conference on Learning Representations_ , 2017.
  * Baum et al. (1988) Eric B Baum, John Moody, and Frank Wilczek.  Internal representations for associative memory.  _Biological Cybernetics_ , 59(4-5):217–228, 1988\.
  * Bengio et al. (1994) Yoshua Bengio, Patrice Simard, and Paolo Frasconi.  Learning long-term dependencies with gradient descent is difficult.  _IEEE transactions on neural networks_ , 5(2):157–166, 1994.
  * Blum and Mitchell (1998) Avrim Blum and Tom Mitchell.  Combining labeled and unlabeled data with co-training.  In _Proceedings of the eleventh annual conference on Computational learning theory_ , pages 92–100. ACM, 1998.
  * Blumenfeld (2010) Hal Blumenfeld.  _Neuroanatomy through Clinical Cases_.  Oxford University Press, 2010.
  * Blundell et al. (2016) Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis.  Model-free episodic control.  _arXiv preprint arXiv:1606.04460_ , 2016.
  * Bornschein et al. (2017) Jörg Bornschein, Andriy Mnih, Daniel Zoran, and Danilo Jimenez Rezende.  Variational memory addressing in generative models.  In _Advances in Neural Information Processing Systems_ , pages 3923–3932, 2017.
  * Bowman et al. (2016) Samuel R Bowman, Luke Vilnis, Oriol Vinyals, Andrew Dai, Rafal Jozefowicz, and Samy Bengio.  Generating sentences from a continuous space.  In _Proceedings of The SIGNLL Conference on Computational Natural Language Learning_ , pages 10–21, 2016.
  * Britz et al. (2017) Denny Britz, Melody Guan, and Minh-Thang Luong.  Efficient attention using a fixed-size memory representation.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 392–400, 2017.
  * Casey (1996) Mike Casey.  The dynamics of discrete-time computation, with application to recurrent neural networks and finite state machine extraction.  _Neural computation_ , 8(6):1135–1178, 1996.
  * Chang et al. (2017) Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Witbrock, Mark A Hasegawa-Johnson, and Thomas S Huang.  Dilated recurrent neural networks.  In _Advances in Neural Information Processing Systems_ , pages 77–87, 2017.
  * Chen and Cherry (2014) Boxing Chen and Colin Cherry.  A systematic comparison of smoothing techniques for sentence-level bleu.  In _Proceedings of the Ninth Workshop on Statistical Machine Translation_ , pages 362–367, 2014.
  * Chen et al. (2018) Hongshen Chen, Zhaochun Ren, Jiliang Tang, Yihong Eric Zhao, and Dawei Yin.  Hierarchical variational memory network for dialogue generation.  In _Proceedings of the World Wide Web Conference on World Wide Web_ , pages 1653–1662. International World Wide Web Conferences Steering Committee, 2018.
  * Cho et al. (2014a) Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio.  On the properties of neural machine translation: Encoder-decoder approaches.  _arXiv preprint arXiv:1409.1259_ , 2014a.
  * Cho et al. (2014b) Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using rnn encoder–decoder for statistical machine translation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1724–1734, Doha, Qatar, October 2014b. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/D14-1179.
  * Choi et al. (2015) Edward Choi, Mohammad Taha Bahadori, and Jimeng Sun.  Doctor AI: Predicting Clinical Events via Recurrent Neural Networks.  _arXiv preprint arXiv:1511.05942_ , 2015.
  * Choi et al. (2016) Edward Choi, Mohammad Taha Bahadori, Jimeng Sun, Joshua Kulas, Andy Schuetz, and Walter Stewart.  RETAIN: An Interpretable Predictive Model for Healthcare using Reverse Time Attention Mechanism.  In _Advances in Neural Information Processing Systems_ , pages 3504–3512, 2016.
  * Chung et al. (2017) J. S. Chung, A. Senior, O. Vinyals, and A. Zisserman.  Lip reading sentences in the wild.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2017\.
  * Chung et al. (2014) Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  _arXiv preprint arXiv:1412.3555_ , 2014.
  * Chung et al. (2015) Junyoung Chung, Kyle Kastner, Laurent Dinh, Kratarth Goel, Aaron C Courville, and Yoshua Bengio.  A recurrent latent variable model for sequential data.  In _Advances in Neural Information Processing Systems_ , pages 2980–2988, 2015.
  * Cireşan et al. (2013) Dan C Cireşan, Alessandro Giusti, Luca M Gambardella, and Jürgen Schmidhuber.  Mitosis detection in breast cancer histology images with deep neural networks.  In _International Conference on Medical Image Computing and Computer-assisted Intervention_ , pages 411–418. Springer, 2013.
  * Cohen et al. (2014) Patricia Cohen, Stephen G West, and Leona S Aiken.  _Applied multiple regression/correlation analysis for the behavioral sciences_.  Psychology Press, 2014.
  * Conneau et al. (2016) Alexis Conneau, Holger Schwenk, Loıc Barrault, and Yann Lecun.  Very deep convolutional networks for natural language processing.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics_ , 2016.
  * Csordas and Schmidhuber (2019) Robert Csordas and Juergen Schmidhuber.  Improving differentiable neural computers through memory masking, de-allocation, and link distribution sharpness control.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=HyGEM3C9KQ.
  * Curtis and D’Esposito (2003) Clayton E Curtis and Mark D’Esposito.  Persistent activity in the prefrontal cortex during working memory.  _Trends in cognitive sciences_ , 7(9):415–423, 2003.
  * Danihelka et al. (2016) Ivo Danihelka, Greg Wayne, Benigno Uria, Nal Kalchbrenner, and Alex Graves.  Associative long short-term memory.  In _International Conference on Machine Learning_ , pages 1986–1994, 2016.
  * Dilokthanakul et al. (2016) Nat Dilokthanakul, Pedro AM Mediano, Marta Garnelo, Matthew CH Lee, Hugh Salimbeni, Kai Arulkumaran, and Murray Shanahan.  Deep unsupervised clustering with gaussian mixture variational autoencoders.  _arXiv preprint arXiv:1611.02648_ , 2016.
  * Durrieu et al. (2012) J-L Durrieu, J-Ph Thiran, and Finnian Kelly.  Lower and upper bounds for approximation of the kullback-leibler divergence between gaussian mixture models.  In _IEEE International Conference on Acoustics, Speech and Signal Processing._ , 2012.
  * Elman (1990) Jeffrey L Elman.  Finding structure in time.  _Cognitive science_ , 14(2):179–211, 1990.
  * Forgues et al. (2014) Gabriel Forgues, Joelle Pineau, Jean-Marie Larchevêque, and Réal Tremblay.  Bootstrapping dialog systems with word embeddings.  In _Nips, Modern Machine Learning and Natural Language Processing Workshop_ , volume 2, 2014.
  * Franke et al. (2018) Jörg Franke, Jan Niehues, and Alex Waibel.  Robust and scalable differentiable neural computer for question answering.  In _Proceedings of the Workshop on Machine Reading for Question Answering_ , pages 47–59. Association for Computational Linguistics, 2018.  URL http://aclweb.org/anthology/W18-2606.
  * French (1999) Robert M French.  Catastrophic forgetting in connectionist networks.  _Trends in cognitive sciences_ , 3(4):128–135, 1999.
  * Ganguli et al. (2008) Surya Ganguli, Dongsung Huh, and Haim Sompolinsky.  Memory traces in dynamical systems.  _Proceedings of the National Academy of Sciences_ , 105(48):18970–18975, 2008.
  * Gao et al. (2018) Jiyang Gao, Runzhou Ge, Kan Chen, and Ram Nevatia.  Motion-appearance co-memory networks for video question answering.  _arXiv preprint arXiv:1803.10906_ , 2018.
  * Gemici et al. (2017) Mevlana Gemici, Chia-Chun Hung, Adam Santoro, Greg Wayne, Shakir Mohamed, Danilo J Rezende, David Amos, and Timothy Lillicrap.  Generative temporal models with memory.  _arXiv preprint arXiv:1702.04649_ , 2017.
  * Giles et al. (1992) C Lee Giles, Clifford B Miller, Dong Chen, Hsing-Hen Chen, Guo-Zheng Sun, and Yee-Chun Lee.  Learning and extracting finite state automata with second-order recurrent neural networks.  _Neural Computation_ , 4(3):393–405, 1992.
  * Goldman-Rakic (1995) Patricia S Goldman-Rakic.  Cellular basis of working memory.  _Neuron_ , 14(3):477–485, 1995.
  * González et al. (2015) Alejandro González, Gabriel Villalonga, Jiaolong Xu, David Vázquez, Jaume Amores, and Antonio M López.  Multiview random forest of local experts combining rgb and lidar data for pedestrian detection.  In _Intelligent Vehicles Symposium (IV), 2015 IEEE_ , pages 356–361. IEEE, 2015.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Advances in Neural Information Processing Systems_ , pages 2672–2680, 2014.
  * Grave et al. (2017a) Edouard Grave, Moustapha M Cisse, and Armand Joulin.  Unbounded cache model for online language modeling with open vocabulary.  In _Advances in Neural Information Processing Systems_ , pages 6042–6052, 2017a.
  * Grave et al. (2017b) Edouard Grave, Armand Joulin, and Nicolas Usunier.  Improving neural language models with a continuous cache.  In _International Conference on Learning Representations_ , 2017b.
  * Graves et al. (2014) A. Graves, G. Wayne, and I. Danihelka.  Neural Turing Machines.  _ArXiv e-prints_ , October 2014.
  * Graves (2013) Alex Graves.  Generating sequences with recurrent neural networks.  _arXiv preprint arXiv:1308.0850_ , 2013.
  * Graves (2016) Alex Graves.  Adaptive computation time for recurrent neural networks.  _arXiv preprint arXiv:1603.08983_ , 2016.
  * Graves and Schmidhuber (2005) Alex Graves and Jürgen Schmidhuber.  Framewise phoneme classification with bidirectional lstm and other neural network architectures.  _Neural Networks_ , 18(5-6):602–610, 2005.
  * Graves et al. (2013) Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton.  Speech recognition with deep recurrent neural networks.  In _Acoustics, speech and signal processing (icassp), 2013 ieee international conference on_ , pages 6645–6649. IEEE, 2013.
  * Graves et al. (2014) Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  _arXiv preprint arXiv:1410.5401_ , 2014.
  * Graves et al. (2016) Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al.  Hybrid computing using a neural network with dynamic external memory.  _Nature_ , 538(7626):471–476, 2016.
  * Grefenstette et al. (2015) Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom.  Learning to transduce with unbounded memory.  In _Advances in Neural Information Processing Systems_ , pages 1828–1836, 2015.
  * Greff et al. (2016) Klaus Greff, Rupesh K Srivastava, Jan Koutník, Bas R Steunebrink, and Jürgen Schmidhuber.  Lstm: A search space odyssey.  _IEEE transactions on neural networks and learning systems_ , 28(10):2222–2232, 2016.
  * Gulcehre et al. (2017) Caglar Gulcehre, Sarath Chandar, and Yoshua Bengio.  Memory augmented neural networks with wormhole connections.  _arXiv preprint arXiv:1701.08718_ , 2017.
  * Hasan et al. (2016) Sadid A Hasan, Siyuan Zhao, Vivek V Datla, Joey Liu, Kathy Lee, Ashequl Qadir, Aaditya Prakash, and Oladimeji Farri.  Clinical question answering using key-value memory networks and knowledge graph.  In _TREC_ , 2016.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hebb (1962) Donald Olding Hebb.  _The organization of behavior: a neuropsychological theory_.  Science Editions, 1962.
  * Hershey and Olsen (2007) John R Hershey and Peder A Olsen.  Approximating the kullback leibler divergence between gaussian mixture models.  In _IEEE International Conference on Acoustics, Speech and Signal Processing._ , 2007.
  * Hinton and Plaut (1987) Geoffrey E Hinton and David C Plaut.  Using fast weights to deblur old memories.  In _Proceedings of the ninth annual conference of the Cognitive Science Society_ , pages 177–186, 1987.
  * Hinton et al. (1986) Geoffrey E Hinton et al.  Learning distributed representations of concepts.  In _Proceedings of the eighth annual conference of the cognitive science society_ , volume 1, page 12. Amherst, MA, 1986.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Hopfield (1982) John J Hopfield.  Neural networks and physical systems with emergent collective computational abilities.  _Proceedings of the national academy of sciences_ , 79(8):2554–2558, 1982.
  * Huang (2018) Francis L Huang.  Multilevel modeling and ordinary least squares regression: how comparable are they?  _The Journal of Experimental Education_ , 86(2):265–281, 2018.
  * Jaeger and Haas (2004) Herbert Jaeger and Harald Haas.  Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication.  _science_ , 304(5667):78–80, 2004.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ , 2016.
  * Jiang et al. (2017) Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou.  Variational deep embedding: An unsupervised and generative approach to clustering.  In _Proceedings of the International Joint Conference on Artificial Intelligence_ , pages 1965–1972. International Joint Conference on Artificial Intelligence, 2017.
  * Johnson et al. (2016) Alistair EW Johnson, Tom J Pollard, Lu Shen, Li-wei H Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark.  MIMIC-III, a freely accessible critical care database.  _Scientific data_ , 3, 2016.
  * Johnson et al. (2013) Samuel Johnson, J Marro, and Joaquín J Torres.  Robust short-term memory without synaptic learning.  _PloS one_ , 8(1):e50276, 2013.
  * Jordan (1997) Michael I Jordan.  Serial order: A parallel distributed processing approach.  In _Advances in psychology_ , volume 121, pages 471–495. Elsevier, 1997.
  * Joulin and Mikolov (2015) Armand Joulin and Tomas Mikolov.  Inferring algorithmic patterns with stack-augmented recurrent nets.  In _Advances in Neural Information Processing Systems_ , pages 190–198, 2015.
  * Kalchbrenner and Blunsom (2013) Nal Kalchbrenner and Phil Blunsom.  Recurrent continuous translation models.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 1700–1709, 2013.
  * Kanerva (1988) Pentti Kanerva.  _Sparse distributed memory_.  MIT press, 1988.
  * Keeler (1988) James D Keeler.  Comparison between kanerva’s sdm and hopfield-type neural networks.  _Cognitive Science_ , 12(3):299–329, 1988.
  * Khan et al. (2018) Asjad Khan, Hung Le, Kien Do, Truyen Tran, Aditya Ghose, Hoa Dam, and Renuka Sindhgatta.  Memory-augmented neural networks for predictive process analytics.  _arXiv preprint arXiv:1802.00938_ , 2018.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kingma and Welling (2014) Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  In _Proceedings of the International Conference on Learning Representations_ , 2014.
  * Kingma et al. (2014) Diederik P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling.  Semi-supervised learning with deep generative models.  In _Advances in Neural Information Processing Systems_ , pages 3581–3589, 2014.
  * Kotseruba and Tsotsos (2018) Iuliia Kotseruba and John K Tsotsos.  40 years of cognitive architectures: core cognitive abilities and practical applications.  _Artificial Intelligence Review_ , pages 1–78, 2018.
  * Krueger et al. (2017) David Krueger, Nicolas Ballas, Stanislaw Jastrzebski, Devansh Arpit, Maxinder S Kanwal, Tegan Maharaj, Emmanuel Bengio, Asja Fischer, and Aaron Courville.  Deep nets don’t learn via memorization.  2017\.
  * Kumaran et al. (2016) Dharshan Kumaran, Demis Hassabis, and James L McClelland.  What learning systems do intelligent agents need? complementary learning systems theory updated.  _Trends in cognitive sciences_ , 20(7):512–534, 2016.
  * Le and Venkatesh (2020) Hung Le and Svetha Venkatesh.  Neurocoder: Learning general-purpose computation using stored neural programs.  _arXiv preprint arXiv:2009.11443_ , 2020.
  * Le et al. (2018a) Hung Le, Truyen Tran, Thin Nguyen, and Svetha Venkatesh.  Variational memory encoder-decoder.  In _Advances in Neural Information Processing Systems_ , pages 1508–1518, 2018a.
  * Le et al. (2018b) Hung Le, Truyen Tran, and Svetha Venkatesh.  Dual memory neural computer for asynchronous two-view sequential learning.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery; Data Mining_ , KDD ’18, pages 1637–1645, New York, NY, USA, 2018b. ACM.  ISBN 978-1-4503-5552-0.  doi: 10.1145/3219819.3219981.  URL http://doi.acm.org/10.1145/3219819.3219981.
  * Le et al. (2018c) Hung Le, Truyen Tran, and Svetha Venkatesh.  Dual control memory augmented neural networks for treatment recommendations.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pages 273–284. Springer, 2018c.
  * Le et al. (2019) Hung Le, Truyen Tran, and Svetha Venkatesh.  Learning to remember more with less memorization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=r1xlvi0qYm.
  * Le et al. (2020a) Hung Le, Truyen Tran, and Svetha Venkatesh.  Neural stored-program memory.  In _International Conference on Learning Representations_ , 2020a.  URL https://openreview.net/forum?id=rkxxA24FDr.
  * Le et al. (2020b) Hung Le, Truyen Tran, and Svetha Venkatesh.  Self-attentive associative memory.  In _International Conference on Machine Learning_ , pages 5682–5691. PMLR, 2020b.
  * Le et al. (2015) Quoc V Le, Navdeep Jaitly, and Geoffrey E Hinton.  A simple way to initialize recurrent networks of rectified linear units.  _arXiv preprint arXiv:1504.00941_ , 2015.
  * Lei Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  _arXiv preprint arXiv:1607.06450_ , 2016.
  * Levy and Goldberg (2014) Omer Levy and Yoav Goldberg.  Neural word embedding as implicit matrix factorization.  In _Advances in Neural Information Processing Systems_ , pages 2177–2185, 2014.
  * Li et al. (2016) Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan.  A diversity-promoting objective function for neural conversation models.  In _Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 110–119, 2016.
  * Lipton et al. (2016) Zachary C Lipton, David C Kale, Charles Elkan, and Randall Wetzel.  Learning to Diagnose with LSTM Recurrent Neural Networks.  In _International Conference on Learning Representations_ , 2016.
  * Lison and Bibauw (2017) Pierre Lison and Serge Bibauw.  Not all dialogues are created equal: Instance weighting for neural conversational models.  In _Proceedings of the Annual SIGdial Meeting on Discourse and Dialogue_ , pages 384–394, 2017.
  * Logie (2014) Robert H Logie.  _Visuo-spatial working memory_.  Psychology Press, 2014.
  * Lopez-Paz et al. (2017) David Lopez-Paz et al.  Gradient episodic memory for continual learning.  In _Advances in Neural Information Processing Systems_ , pages 6467–6476, 2017.
  * Luaces et al. (2012) Oscar Luaces, Jorge Díez, José Barranquero, Juan José del Coz, and Antonio Bahamonde.  Binary relevance efficacy for multilabel classification.  _Progress in Artificial Intelligence_ , 1(4):303–313, 2012.
  * Ma et al. (2017a) Chao Ma, Chunhua Shen, Anthony Dick, and Anton van den Hengel.  Visual question answering with memory-augmented networks.  _arXiv preprint arXiv:1707.04968_ , 2017a.
  * Ma et al. (2017b) Fenglong Ma, Radha Chitta, Jing Zhou, Quanzeng You, Tong Sun, and Jing Gao.  Dipole: Diagnosis prediction in healthcare via attention-based bidirectional recurrent neural networks.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 1903–1911. ACM, 2017b.
  * Ma and Principe (2018) Ying Ma and Jose Principe.  A taxonomy for neural memory networks.  _arXiv preprint arXiv:1805.00327_ , 2018.
  * Maass (1997) Wolfgang Maass.  Networks of spiking neurons: the third generation of neural network models.  _Neural networks_ , 10(9):1659–1671, 1997.
  * Maass (2011) Wolfgang Maass.  Liquid state machines: motivation, theory, and applications.  In _Computability in context: computation and logic in the real world_ , pages 275–296. World Scientific, 2011.
  * Maass et al. (2002) Wolfgang Maass, Thomas Natschläger, and Henry Markram.  Real-time computing without stable states: A new framework for neural computation based on perturbations.  _Neural computation_ , 14(11):2531–2560, 2002\.
  * Marr and Thach (1991) David Marr and W Thomas Thach.  A theory of cerebellar cortex.  In _From the Retina to the Neocortex_ , pages 11–50. Springer, 1991\.
  * Maz’ya and Schmidt (1996) Vladimir Maz’ya and Gunther Schmidt.  On approximate approximations using gaussian kernels.  _IMA Journal of Numerical Analysis_ , 16(1):13–29, 1996.
  * McClelland et al. (1995) James L McClelland, Bruce L McNaughton, and Randall C O’Reilly.  Why there are complementary learning systems in the hippocampus and neocortex: insights from the successes and failures of connectionist models of learning and memory.  _Psychological review_ , 102(3):419, 1995.
  * Mikolov et al. (2010) Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černockỳ, and Sanjeev Khudanpur.  Recurrent neural network based language model.  In _Eleventh Annual Conference of the International Speech Communication Association_ , 2010.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In _Advances in Neural Information Processing Systems_ , pages 3111–3119, 2013.
  * Miller et al. (2016) Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston.  Key-value memory networks for directly reading documents.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1400–1409, 2016.
  * Miller and Hardt (2018) John Miller and Moritz Hardt.  When recurrent models don’t need to be recurrent.  _arXiv preprint arXiv:1805.10369_ , 2018.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529, 2015.
  * Morency et al. (2011) Louis-Philippe Morency, Rada Mihalcea, and Payal Doshi.  Towards multimodal sentiment analysis: Harvesting opinions from the web.  In _Proceedings of the 13th international conference on multimodal interfaces_ , pages 169–176. ACM, 2011.
  * Mozer and Das (1993) Michael C Mozer and Sreerupa Das.  A connectionist symbol manipulator that discovers the structure of context-free languages.  In _Advances in Neural Information Processing Systems_ , pages 863–870, 1993.
  * Munkhdalai and Yu (2017) Tsendsuren Munkhdalai and Hong Yu.  Meta networks.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 2554–2563. JMLR. org, 2017.
  * Nalisnick et al. (2016) Eric Nalisnick, Lars Hertel, and Padhraic Smyth.  Approximate inference for deep latent gaussian mixtures.  In _NIPS Workshop on Bayesian Deep Learning_ , volume 2, 2016.
  * Nallapati et al. (2016) Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Caglar Gulcehre, and Bing Xiang.  Abstractive text summarization using sequence-to-sequence rnns and beyond.  In _Proceedings of the SIGNLL Conference on Computational Natural Language Learning_ , pages 280–290, 2016.
  * Nguyen et al. (2019) Duc Nguyen, Nhan Tran, and Hung Le.  Improving long handwritten text line recognition with convolutional multi-way associative memory.  _arXiv preprint arXiv:1911.01577_ , 2019.
  * Nguyen et al. (2017) Phuoc Nguyen, Truyen Tran, Nilmini Wickramasinghe, and Svetha Venkatesh.  Deepr: A Convolutional Net for Medical Records.  _Journal of Biomedical and Health Informatics_ , 21(1), 2017\.
  * Nie et al. (2015) Liqiang Nie, Luming Zhang, Yi Yang, Meng Wang, Richang Hong, and Tat-Seng Chua.  Beyond doctors: future health prediction from multimedia and multimodal observations.  In _Proceedings of the 23rd ACM international conference on Multimedia_ , pages 591–600. ACM, 2015.
  * Nigam and Ghani (2000) Kamal Nigam and Rayid Ghani.  Analyzing the effectiveness and applicability of co-training.  In _Proceedings of the ninth international conference on Information and knowledge management_ , pages 86–93. ACM, 2000.
  * Omlin and Giles (1996) Christian W Omlin and C Lee Giles.  Constructing deterministic finite-state automata in recurrent neural networks.  _Journal of the ACM (JACM)_ , 43(6):937–972, 1996\.
  * Pascanu et al. (2013) Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio.  On the difficulty of training recurrent neural networks.  In _International Conference on Machine Learning_ , pages 1310–1318, 2013.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In _EMNLP_ , volume 14, pages 1532–1543, 2014.
  * Pham et al. (2017) Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh.  Predicting healthcare trajectories from medical records: A deep learning approach.  _Journal of Biomedical Informatics_ , 69:218–229, May 2017\.
  * Plate (1995) Tony A Plate.  Holographic reduced representations.  _IEEE Transactions on Neural networks_ , 6(3):623–641, 1995.
  * Plunkett and Sinha (1992) Kim Plunkett and Chris Sinha.  Connectionism and developmental theory.  _British Journal of Developmental Psychology_ , 10(3):209–254, 1992.
  * Poria et al. (2015) Soujanya Poria, Erik Cambria, and Alexander Gelbukh.  Deep convolutional neural network textual features and multiple kernel learning for utterance-level multimodal sentiment analysis.  In _Proceedings of the 2015 conference on empirical methods in natural language processing_ , pages 2539–2544, 2015.
  * Poria et al. (2017) Soujanya Poria, Erik Cambria, Devamanyu Hazarika, Navonil Majumder, Amir Zadeh, and Louis-Philippe Morency.  Context-dependent sentiment analysis in user-generated videos.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , volume 1, pages 873–883, 2017.
  * Prakash et al. (2017) Aaditya Prakash, Siyuan Zhao, Sadid A Hasan, Vivek V Datla, Kathy Lee, Ashequl Qadir, Joey Liu, and Oladimeji Farri.  Condensed memory networks for clinical diagnostic inferencing.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 3274–3280, 2017.
  * Pritzel et al. (2017) Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomènech, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell.  Neural episodic control.  _arXiv preprint arXiv:1703.01988_ , 2017.
  * Quadrianto et al. (2009) N. Quadrianto, A.J. Smola, T.S. Caetano, and Q.V. Le.  Estimating labels from label proportions.  _The Journal of Machine Learning Research_ , 10:2349–2374, 2009.
  * Qui et al. (2018) Chao Qui, Bo Huang, Guocheng Niu, Daren Li, Daxiang Dong, Wei He, Dianhai Yu, and Hua Wu.  A new method of region embedding for text classification.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=BkSDMA36Z.
  * Rae et al. (2016) Jack Rae, Jonathan J Hunt, Ivo Danihelka, Timothy Harley, Andrew W Senior, Gregory Wayne, Alex Graves, and Tim Lillicrap.  Scaling memory-augmented neural networks with sparse reads and writes.  In _Advances in Neural Information Processing Systems_ , pages 3621–3629, 2016.
  * Rajagopalan et al. (2016) Shyam Sundar Rajagopalan, Louis-Philippe Morency, Tadas Baltrusaitis, and Roland Goecke.  Extending long short-term memory for multi-view structured learning.  In _European Conference on Computer Vision_ , pages 338–353. Springer, 2016.
  * Rakotomamonjy et al. (2007) Alain Rakotomamonjy, Francis Bach, Stéphane Canu, and Yves Grandvalet.  More efficiency in multiple kernel learning.  In _Proceedings of the 24th international conference on Machine learning_ , pages 775–782. ACM, 2007.
  * Read et al. (2011) Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank.  Classifier chains for multi-label classification.  _Machine learning_ , 85(3):333–359, 2011.
  * Rezende et al. (2014) Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra.  Stochastic backpropagation and approximate inference in deep generative models.  In _Proceedings of the International Conference on International Conference on Machine Learning_ , pages II–1278. JMLR. org, 2014.
  * Rifkin and Klautau (2004) Ryan Rifkin and Aldebaro Klautau.  In defense of one-vs-all classification.  _Journal of machine learning research_ , 5(Jan):101–141, 2004.
  * Rogers and McClelland (2004) Timothy T Rogers and James L McClelland.  _Semantic cognition: A parallel distributed processing approach_.  MIT press, 2004.
  * Rojas (2013) Raúl Rojas.  _Neural networks: a systematic introduction_.  Springer Science & Business Media, 2013.
  * Rumelhart et al. (1988) David E Rumelhart, Geoffrey E Hinton, Ronald J Williams, et al.  Learning representations by back-propagating errors.  _Cognitive modeling_ , 5(3):1, 1988.
  * Salgado et al. (2012) Rodrigo Salgado, Francisco Bellas, Pilar Caamaño, Borja Santos-Diez, and Richard J Duro.  A procedural long term memory for cognitive robotics.  In _2012 IEEE Conference on Evolving and Adaptive Intelligent Systems_ , pages 57–62. IEEE, 2012.
  * Santoro et al. (2016) Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap.  Meta-learning with memory-augmented neural networks.  In _International conference on machine learning_ , pages 1842–1850, 2016.
  * Saxe et al. (2019) Andrew M Saxe, James L McClelland, and Surya Ganguli.  A mathematical theory of semantic development in deep neural networks.  _Proceedings of the National Academy of Sciences_ , 116(23):11537–11546, 2019.
  * Schlag and Schmidhuber (2018) Imanol Schlag and Jürgen Schmidhuber.  Learning to reason with third order tensor products.  In _Advances in Neural Information Processing Systems_ , pages 9981–9993, 2018.
  * Schmidhuber (1992) Jürgen Schmidhuber.  Learning to control fast-weight memories: An alternative to dynamic recurrent networks.  _Neural Computation_ , 4(1):131–139, 1992.
  * Seo et al. (2018) Minjoon Seo, Sewon Min, Ali Farhadi, and Hannaneh Hajishirzi.  Neural Speed Reading via Skim-RNN.  In _International Conference on Learning Representations_ , 2018.
  * Serban et al. (2017) Iulian Vlad Serban, Alessandro Sordoni, Ryan Lowe, Laurent Charlin, Joelle Pineau, Aaron C Courville, and Yoshua Bengio.  A hierarchical latent variable encoder-decoder model for generating dialogues.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 3295–3301, 2017.
  * Shen et al. (2017) Xiaoyu Shen, Hui Su, Yanran Li, Wenjie Li, Shuzi Niu, Yang Zhao, Akiko Aizawa, and Guoping Long.  A conditional variational framework for dialog generation.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , volume 2, pages 504–509, 2017.
  * Shu et al. (2016) Rui Shu, James Brofos, Frank Zhang, Hung Hai Bui, Mohammad Ghavamzadeh, and Mykel Kochenderfer.  Stochastic video prediction with conditional density estimation.  In _ECCV Workshop on Action and Anticipation for Visual Learning_ , volume 2, 2016.
  * Siegelmann and Sontag (1995) Hava T Siegelmann and Eduardo D Sontag.  On the computational power of neural nets.  _Journal of computer and system sciences_ , 50(1):132–150, 1995.
  * Sipser et al. (2006) Michael Sipser et al.  _Introduction to the Theory of Computation_ , volume 2.  Thomson Course Technology Boston, 2006.
  * Smolensky (1990) Paul Smolensky.  Tensor product variable binding and the representation of symbolic structures in connectionist systems.  _Artificial intelligence_ , 46(1-2):159–216, 1990\.
  * Song et al. (2012) Yale Song, Louis-Philippe Morency, and Randall Davis.  Multi-view latent variable discriminative models for action recognition.  In _Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on_ , pages 2120–2127. IEEE, 2012.
  * Srivastava et al. (2015) Rupesh K Srivastava, Klaus Greff, and Jürgen Schmidhuber.  Training very deep networks.  In _Advances in Neural Information Processing Systems_ , pages 2377–2385, 2015.
  * Sukhbaatar et al. (2015) Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, et al.  End-to-end memory networks.  In _Advances in Neural Information Processing Systems_ , pages 2440–2448, 2015.
  * Sussillo (2014) David Sussillo.  Neural circuits as computational dynamical systems.  _Current opinion in neurobiology_ , 25:156–163, 2014.
  * Sutskever et al. (2014a) Ilya Sutskever, Oriol Vinyals, and Quoc V. Le.  Sequence to sequence learning with neural networks.  _International Conference on Machine Learning_ , 2014a.  URL http://arxiv.org/abs/1409.3215.
  * Sutskever et al. (2014b) Ilya Sutskever, Oriol Vinyals, and Quoc VV Le.  Sequence to sequence learning with neural networks.  In _Advances in Neural Information Processing Systems_ , pages 3104–3112, 2014b.
  * Tan et al. (2014) Jie Tan, Matthew Ung, Chao Cheng, and Casey S Greene.  Unsupervised feature construction and knowledge extraction from genome-wide assays of breast cancer with denoising autoencoders.  In _Pacific Symposium on Biocomputing Co-Chairs_ , pages 132–143. World Scientific, 2014.
  * Thrun (1998) Sebastian Thrun.  Lifelong learning algorithms.  In _Learning to learn_ , pages 181–209. Springer, 1998.
  * Tiňo et al. (1998) Peter Tiňo, Bill G Horne, C Lee Giles, and Pete C Collingwood.  Finite state machines and recurrent neural networks–automata and dynamical systems approaches.  In _Neural networks and pattern recognition_ , pages 171–219. Elsevier, 1998.
  * Trinh et al. (2018) Trieu H Trinh, Andrew M Dai, Thang Luong, and Quoc V Le.  Learning longer-term dependencies in rnns with auxiliary losses.  In _Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80_ , 2018.
  * Tulving et al. (1972) Endel Tulving et al.  Episodic and semantic memory.  _Organization of memory_ , 1:381–403, 1972.