Memory and attention
in deep learning

by

Hung Thai Le

BSc. (Honours)

Submitted in fulfilment of the requirements for the degree of

Doctor of Philosophy

Deakin University

_August 2019_

## Acknowledgements

I would like to thank my principal supervisor A/Prof. Truyen Tran for his
continual guidance and support. I have been lucky to have an outstanding
supervisor with deep insight and great vision, who has taught me valuable
lessons for both my work and personal life. I would also like to express my
appreciation to my co-supervisor Prof. Svetha Venkatesh for giving me the
opportunity to undertake research at PRaDA and for her valuable advice and
inspirational talks. Thanks to my friends Kien Do, Tung Hoang, Phuoc Nguyen,
Vuong Le, Romelo, Tin Pham, Dung Nguyen, Thao Le, Duc Nguyen and everyone else
at PRaDA for making it an original and interesting place to do research. Most
of all, I would like to thank my parents, my sister and my wife for their
encouragement, love and support.

###### Contents

  1. Acknowledgements
  2. Abstract
  3. Relevant Publications
  4. 1 Introduction
    1. 1.1 Motivations
    2. 1.2 Aims and Scope
    3. 1.3 Significance and Contribution
    4. 1.4 Thesis Structure
  5. 2 Taxonomy for Memory in RNNs
    1. 2.1 Memory in Brain
      1. 2.1.1 Short-term Memory
      2. 2.1.2 Long-term Memory
    2. 2.2 Neural Networks and Memory
      1. 2.2.1 Introduction to Neural Networks
      2. 2.2.2 Semantic Memory in Neural Networks
      3. 2.2.3 Associative Neural Networks
    3. 2.3 The Constructions of Memory in RNNs
      1. 2.3.1 Attractor dynamics
      2. 2.3.2 Transient Dynamics
    4. 2.4 External Memory for RNNs
      1. 2.4.1 Cell Memory
      2. 2.4.2 Holographic Associative Memory
      3. 2.4.3 Matrix Memory
      4. 2.4.4 Sparse Distributed Memory
    5. 2.5 Relation to Computational Models
    6. 2.6 Closing Remarks
  6. 3 Memory-augmented Neural Networks
    1. 3.1 Gated RNNs
      1. 3.1.1 Long Short-Term Memory
      2. 3.1.2 Gated Recurrent Unit
    2. 3.2 Attentional RNNs
      1. 3.2.1 Encoder-Decoder Architecture
      2. 3.2.2 Attention Mechanism
      3. 3.2.3 Multi-Head Attention
    3. 3.3 Slot-Based Memory Networks
      1. 3.3.1 Neural Stack
      2. 3.3.2 Memory Networks
      3. 3.3.3 Neural Turing Machine
      4. 3.3.4 Differentiable Neural Computer
      5. 3.3.5 Memory-augmented Encoder-Decoder Architecture
    4. 3.4 Closing Remarks
  7. 4 Memory Models for Multiple Processes
    1. 4.1 Introduction
      1. 4.1.1 Multi-Process Learning
      2. 4.1.2 Real-World Motivation
    2. 4.2 Background
      1. 4.2.1 Multi-View Learning
      2. 4.2.2 Existing Approaches
    3. 4.3 Dual Control Architecture
    4. 4.4 Dual Memory Architecture
      1. 4.4.1 Dual Memory Neural Computer
      2. 4.4.2 Inference in DMNC
      3. 4.4.3 Persistent Memory for Multiple Admissions
    5. 4.5 Applications
      1. 4.5.1 Synthetic Task: Odd-Even Sequence Prediction
      2. 4.5.2 Treatment Recommendation Tasks
      3. 4.5.3 Synthetic Task: Sum of Two Sequences
      4. 4.5.4 Drug Prescription Task
        1. 4.5.5 Disease Progression Task
          1. 4.6 Closing Remarks
            1. 5 Variational Memory in Generative Models
              1. 5.1 Introduction
              2. 5.2 Preliminaries
                1. 5.2.1 Conditional Variational Autoencoder (CVAE) for Conversation Generation
                2. 5.2.2 Related Works
              3. 5.3 Variational Memory Encoder-Decoder
                1. 5.3.1 Generative Process
                2. 5.3.2 Neural Posterior Approximation
                3. 5.3.3 Learning
                4. 5.3.4 Theoretical Analysis
              4. 5.4 Experiments and Results
                1. 5.4.1 Quantitative Results
                2. 5.4.2 Qualitative Analysis
              5. 5.5 Closing Remarks
                1. 6 Optimal Writing Memory
                  1. 6.1 Introduction
                  2. 6.2 Related Backgrounds
                  3. 6.3 Theoretical Analysis on Memorisation
                    1. 6.3.1 Generic Memory Operations
                    2. 6.3.2 Memory Analysis of RNNs
                    3. 6.3.3 Memory Analysis of MANNs
                  4. 6.4 Optimal Writing for Slot-based Memory Models
                    1. 6.4.1 Uniform Writing
                    2. 6.4.2 Local Optimal Design
                    3. 6.4.3 Local Memory-Augmented Attention Unit
                  5. 6.5 Experiments and Results
                    1. 6.5.1 An Ablation Study: Memory-Augmented Neural Networks with and without Uniform Writing
                    2. 6.5.2 Synthetic Memorisation
                    3. 6.5.3 Synthetic Reasoning
                    4. 6.5.4 Synthetic Sinusoidal Regression
                    5. 6.5.5 Flatten Image Recognition
                    6. 6.5.6 Document Classification
                  6. 6.6 Closing Remarks
                    1. 7 Neural Stored-Program Memory
                      1. 7.1 Introduction
                      2. 7.2 Backgrounds
                        1. 7.2.1 Turing Machines and MANNs
                        2. 7.2.2 Related Approaches
                      3. 7.3 Neural Stored-Program Memory and Neural Universal Turing Machine
                        1. 7.3.1 Neural Stored-Program Memory
                        2. 7.3.2 Neural Universal Turing Machine
                        3. 7.3.3 On the Benefit of NSM to MANN: An Explanation from Multilevel Modeling
                      4. 7.4 Applications
                        1. 7.4.1 NTM Single Tasks
                        2. 7.4.2 NTM Sequencing Tasks
                        3. 7.4.3 Continual Procedure Learning
                        4. 7.4.4 Few-Shot Learning
                        5. 7.4.5 Text Question Answering
                      5. 7.5 Closing Remarks
                        1. 8 Conclusions
                          1. 8.1 Summary
                          2. 8.2 Future Directions
                            1. Appendix
                              1. C Supplementary for Chapter 5
                                1. C.1 Proof of Theorem 5.1
                                2. C.2 Derivation of the Upper Bound on the Total Timestep-Wise $KL$ Divergence
                                3. 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
                                4. C.4 Details of Data Descriptions and Model Implementations
                                5. C.5 Full Reports on Model Performance
                              2. D Supplementary for Chapter 6
                                1. D.1 Derivation on the Bound Inequality in Linear Dynamic System
                                2. D.2 Derivation on the Bound Inequality in Standard RNN
                                3. D.3 Derivation on the Bound Inequality in LSTM
                                4. D.4 Proof of Theorem 6.1
                                5. D.5 Proof of Theorem 6.2
                                6. D.6 Proof of Theorem 6.3
                                7. D.7 Summary of Synthetic Discrete Task Format
                                8. D.8 UW Performance on Bigger Memory
                                9. D.9 Memory Operating Behaviors on Synthetic Tasks
                                10. D.10 Visualisations of Model Performance on Sinusoidal Regression Tasks
                                11. D.11 Comparison with Non-Recurrent Methods in Flatten Image Classification Task
                                12. D.12 Details on Document Classification Datasets
                                13. D.13 Document Classification Detailed Records
                              3. E Supplementary for Chapter 7
                                1. E.1 Full Learning Curves on Single NTM Tasks
                                2. E.2 Clustering on The Latent Space
                                3. E.3 Program Usage Visualisations
                                  1. E.3.1 Visualisation on Program Distribution across Timesteps (Single Tasks)
                                  2. E.3.2 Visualisation on Program Distribution across Timesteps (Sequencing Tasks)
                                  3. E.3.3 Perseveration Phenomenon in NTM (Sequencing Tasks)
                                4. E.4 Details on Synthetic Tasks
                                  1. E.4.1 NTM Single Tasks
                                  2. E.4.2 NTM Sequencing Tasks
                                  3. E.4.3 Continual Procedure Learning Tasks
                                5. E.5 Details on Few-Shot Learning Task
                                6. E.6 Details on bAbI Task
                                7. E.7 Others

###### List of Figures

  1. 2.1 Types of memory in cognitive models
  2. 2.2 A multilayer perceptron with a single hidden-layer.
  3. 2.3 A typical Recurrent Neural Network (Left) and its unfolded representation (Right). Each neuron at timestep $t$ takes into consideration the current input $x_{t}$ and previous hidden state $h_{t-1}$ to generate the $t$-th output $o_{t}$. $W$, $U$ and $V$ are learnable weight matrices of the model.
  4. 2.4 (a) Hopfield network with five neurons. (b) Structure of a Liquid State Machine $M$. The machine wants to transform input stream $u(\cdot)$ into output stream $y(\cdot)$ using some dynamical system $L^{M}$ (the liquid).
  5. 2.5 Error back flow from $\vartheta_{u}\left(t\right)$ to $\vartheta_{v}\left(t-q\right)$ in the computation graph. Each computation node has $n$ children. Each product term corresponds to a computation path of depth $q$ from node $u$ to $v$. The sum of $n^{q-1}$ products is the total error.
  6. 2.6 (a) Example of a tree encoded by TPR. (b) SDM’s memory write (red) and read (blue) access. The read and write involve all memory locations around the queried points.
  7. 2.7 Relation between external memory and computational models
  8. 3.1 Block diagram of a modern LSTM unit. $\times$ and $+$ are element-wise product and add operators, respectively. $\sigma$ and $\tanh$ are sigmoid and tanh functions, respectively.
  9. 3.2 (a) Seq2Seq Model. Gray and green denote the LSTM encoder and decoder, respectively. In this architecture, the output at each decoding step can be fed as input for the next decoding step. (b) Seq2Seq Model with attention mechanism. The attention computation is repeated across decoding steps.
  10. 3.3 Computation stages of the encoding using self-attention (a) and encoding-decoding architecture–The Transformer (b). Embedding layers convert input/output tokens to vectors of fix dimension, followed by Positional Encoding layers that add temporal information to each vector. The main block of computation combines multi-head attention, residual connection, layer normalisation and Feed-forward layers, which can be repeated multiple times.
  11. 3.4 (a) Architecture of NTM. Circles denote intermediate variables computed by the controller. The controller takes the current timestep data $x_{t}$ and the previous read value $r_{t-1}$ as the input and produces $r_{t}$, updates memory $M_{t}$ and predict output $o_{t}$. (b) Architecture of DNC. The operation is similar to NTM’s with extra modules to keep track of memory usage $u_{t}$, precedence $p_{t}$ and link matrix $L_{t}$.
  12. 4.1 Dual Controller Write-Protected Memory Augmented Neural Network. $LSTM_{E}$ is the encoding controller. $LSTM_{D}$ is the decoding controller. Both are implemented as LSTMs.
  13. 4.2 Dual Memory Neural Computer. $LSTM^{i_{1}}$, $LSTM^{i_{2}}$ are the two encoding controllers implemented as LSTMs. $LSTM^{d}$ is the decoding controller. The dash arrows represent cross-memory accessing in early-fusion mode.
  14. 4.5.1 Synthetic Task: Odd-Even Sequence Prediction
  15. 4.5.1 Synthetic Task: Odd-Even Sequence Prediction
  16. 4.5.2 Treatment Recommendation Tasks
  17. 4.8 Training loss of sum of two sequences task. The training error curves have similar patterns.
  18. 4.9 $M_{1}$’s $g_{t}^{w}$ over diagnoses. Diagnosis codes of a MIMIC-III patient is listed along the x-axis (ordered by priority) with the y-axis indicating how much the write gate allows a diagnosis to be written to the memory $M_{1}$.
  19. 4.10 $M_{2}$’s $g_{t}^{w}$ over procedures. Medical procedure codes of a MIMIC-III patient is listed along the x-axis (in the order of executions) with the y-axis indicating how much the write gate allows a procedure to be written to the memory $M_{2}$.
  20. 5.1 Graphical Models of the vanilla CVAE (a) and our proposed VMED (b)
  21. 5.2 Training and testing of VMED
  22. 6.1 Writing mechanism in Cached Uniform Writing. During non-writing intervals, the controller hidden states are pushed into the cache. When the writing time comes, the controller attends to the cache, chooses suitable states and accesses the memory. The cache is then emptied.
  23. 6.2 The accuracy (%) and computation time reduction (%) with different memory types and number of memory slots. The controllers/sequence lengths/memory sizes are chosen as LSTM/50/$\left\\{2,4,9,24\right\\}$ (a&b) and RNN/30/$\left\\{2,4,9,14\right\\}$ (c&d), respectively.
  24. 6.3 Learning curves of models in clean (a) and noisy (b) sinusoid regression experiment.
  25. 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}$.
  26. 7.2 Learning curves on NTM tasks.
  27. 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.
  28. 7.4 Learning curves on sequencing NTM tasks.
  29. 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.
  30. 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.
  31. 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.
  32. D.3 Sinusoidal generation with clean input sequence for DNC, UW and CUW in top-down order.
  33. D.4 Sinusoidal generation with noisy input sequence for DNC, UW and CUW in top-down order.
  34. E.1 Learning curves on NTM tasks.
  35. 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.
  36. E.3 Copy (p=2).
  37. E.4 Repeat Copy (p=2).
  38. E.5 Associative Recall (p=2).
  39. E.6 Dynamic N-grams (p=2).
  40. E.7 Priority Sort (p=2).
  41. E.8 Long Copy (p=2).
  42. E.9 Copy+Repeat Copy (p=3).
  43. E.10 Copy+Associative Recall (p=3).
  44. E.11 Copy+Priority Sort (p=3).
  45. E.12 Copy+Repeat Copy+Associative Recall+Priority Sort (p=4).
  46. E.13 Copy+Repeat Copy perseveration (only Repeat Copy).
  47. E.14 Copy+Associative Recall perseveration (only Copy).
  48. E.15 Copy+Priority Sort perseveration (only Copy).
  49. E.16 Copy+Repeat Copy+Associative Recall+Priority Sort perseveration (only Repeat Copy).
  50. E.17 Testing accuracy during training (five random classes/episode, one-hot vector labels, of length 50).
  51. E.18 Testing accuracy during training (ten random classes/episode, one-hot vector labels, of length 75).

###### List of Tables

  1. 4.2 Statistics of MIMIC-III sub-datasets
  2. 4.3 Results on MIMIC-III dataset for procedure prediction and drug prescription (higher is better).
  3. 4.4 Sum of two sequences task test results. Max train sequence length is 10.
  4. 4.5 MIMIC-III data statistics.
  5. 4.7 Example Recommended Medications by DMNCs on MIMIC-III dataset. Bold denotes matching against ground-truth.
  6. 4.8 Regional hospital test results. P@K is precision at top K predictions in %.
  7. 5.1 BLEU-1, 4 and A-Glove on testing datasets. B1, B4, AG are acronyms for BLEU-1, BLEU-4, A-Glove metrics, respectively (higher is better).
  8. 5.2 Examples of context-response pairs. /*/ denotes separations between stochastic responses.
  9. 6.1 Test accuracy (%) on synthetic memorisation tasks. MANNs have 4 memory slots.
  10. 6.2 Test accuracy (%) on synthetic reasoning tasks. MANNs have 4 memory slots.
  11. 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)◆.
  12. 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.
  13. 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.
  14. 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.
  15. 7.3 Mean and s.d. for bAbI error ($\%$).
  16. C.1 Results on Cornell Movies
  17. C.2 Results on OpenSubtitles
  18. C.3 Results on LJ users question-answering
  19. C.4 Results on Reddit comments
  20. D.1 Synthetic discrete task’s input-output formats. $T$ is the sequence length.
  21. 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.
  22. D.3 Test accuracy (%) on MNIST, pMNIST. Previously reported results are from Vaswani et al., (2017)⋆ and Chang et al., (2017)◆.
  23. D.4 Statistics on several big document classification datasets
  24. D.5 Document classification accuracy (%) on several datasets reported for 3 different runs. Bold denotes the best records.
  25. E.1 Model hyper-parameters (single tasks).
  26. E.2 Task settings (single tasks).
  27. E.3 Model hyper-parameters (sequencing tasks).
  28. E.4 Task settings (sequencing tasks).
  29. E.5 Task settings (continual procedure learning tasks).
  30. E.6 Hyper-parameters for few-shot learning.
  31. 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).
  32. E.8 NUTM hyper-parameters for bAbI.
  33. E.9 NUTM ($p=4$) bAbI best and mean errors (%).

## Abstract

Intelligence necessitates memory. Without memory, humans fail to perform
various nontrivial tasks such as reading novels, playing games or solving
maths. As the ultimate goal of machine learning is to derive intelligent
systems that learn and act automatically just like human, memory construction
for machine is inevitable.

Artificial neural networks model neurons and synapses in the brain by
interconnecting computational units via weights, which is a typical class of
machine learning algorithms that resembles memory structure. Their descendants
with more complicated modeling techniques (a.k.a deep learning) have been
successfully applied to many practical problems and demonstrated the
importance of memory in the learning process of machinery systems.

Recent progresses on modeling memory in deep learning have revolved around
external memory constructions, which are highly inspired by computational
Turing models and biological neuronal systems. Attention mechanisms are
derived to support acquisition and retention operations on the external
memory. Despite the lack of theoretical foundations, these approaches have
shown promises to help machinery systems reach a higher level of intelligence.
The aim of this thesis is to advance the understanding on memory and attention
in deep learning. Its contributions include: (i) presenting a collection of
taxonomies for memory, (ii) constructing new memory-augmented neural networks
(MANNs) that support multiple control and memory units, (iii) introducing
variability via memory in sequential generative models, (iv) searching for
optimal writing operations to maximise the memorisation capacity in slot-based
memory networks, and (v) simulating the Universal Turing Machine via Neural
Stored-program Memory–a new kind of external memory for neural networks.

The simplest form of MANNs consists of a neural controller operating on an
external memory, which can encode/decode one stream of sequential data at a
time. Our proposed model called Dual Controller Write-Protected Memory
Augmented Neural Network extends MANNs to using dual controllers executing the
encoding and decoding process separately, which is essential in some
healthcare applications. One notable feature of our model is the write-
protected decoding for maintaining the stored information for long inference.
To handle two streams of inputs, we propose a model named Dual Memory Neural
Computer that consists of three controllers working with two external memory
modules. These designs provide MANNs with more flexibility to process
structural data types and thus expand the range of application for MANNs. In
particular, we demonstrate that our architectures are effective for various
healthcare tasks such as treatment recommendation and disease progression.

Learning generative models for sequential discrete data such as utterances in
conversation is a challenging problem. Standard neural variational encoder-
decoder networks often result in either trivial or digressive conversational
responses. To tackle this problem, our second work presents a novel approach
that models variability in stochastic sequential processes via external
memory, namely Variational Memory Encoder-Decoder. By associating each read
head of the memory with a mode in the mixture distribution governing the
latent space, our model can capture the variability observed in natural
conversations.

The third work aims to give a theoretical explanation on optimal memory
operations. We realise that the scheme of regular writing in current MANN is
suboptimal in memory utilisation and introduces computational redundancy. A
theoretical bound on the amount of information stored in slot-based memory
models is formulated and our goal is to search for optimal writing schemes
that maximise the bound. The proposed solution named Uniform Writing is proved
to be optimal under the assumption of equal contribution amongst timesteps. To
balance between maximising memorisation and overwriting forgetting, we modify
the original solution, resulting in a solution dubbed Cached Uniform Writing.
The proposed solutions are empirically demonstrated to outperform other
recurrent architectures, claiming the state-of-the-arts in various sequential
tasks.

MANNs can be viewed as a neural realisation of Turing Machines and thus, can
learn algorithms and other complex tasks. By leveraging neural network
simulation of Turing Machines to neural architecture for Universal Turing
Machines, we develop a new class of MANNs that uses Neural Stored-program
Memory to store the weights of the controller, thereby following the stored-
program principle in modern computer architectures. By validating the
computational universality of the approach through an extensive set of
experiments, we have demonstrated that our models not only excel in classical
algorithmic problems, but also have potential for compositional, continual,
few-shot learning and question-answering tasks.

## Relevant Publications

Part of this thesis has been published or documented elsewhere. The details of
these publications are as follows:

Chapter 4:

  * •

Le, H., Tran, T., & Venkatesh, S. (2018). Dual control memory augmented neural
networks for treatment recommendations. In Pacific-Asia Conference on
Knowledge Discovery and Data Mining (pp. 273-284). Springer, Cham.

  * •

Le, H., Tran, T., & Venkatesh, S. (2018). Dual memory neural computer for
asynchronous two-view sequential learning. In Proceedings of the 24th ACM
SIGKDD International Conference on Knowledge Discovery & Data Mining (pp.
1637-1645). ACM.

Chapter 5:

  * •

Le, H., Tran, T., Nguyen, T., & Venkatesh, S. (2018). Variational memory
encoder-decoder. In Advances in Neural Information Processing Systems (pp.
1508-1518).

Chapter 6:

  * •

Le, H., Tran, T., & Venkatesh, S. (2019). Learning to Remember More with Less
Memorization. In International Conference on Learning Representations. 2019.

Chapter 7:

  * •

Le, H., Tran, T., & Venkatesh, S. (2019). Neural Stored-program Memory. In
International Conference on Learning Representations. 2020.

Although not the main contributions, the following collaborative work is the
application of some work in the thesis:

  * •

Khan, A., Le, H., Do, K., Tran, T., Ghose, A., Dam, H., & Sindhgatta, R.
(2018). Memory-augmented neural networks for predictive process analytics.
arXiv preprint arXiv:1802.00938.

##  Chapter 1 Introduction

###  1.1 Motivations

In a broad sense, memory is the ability to store, retain and then retrieve
information on request. In human brain, memory is involved in not just
remembering and forgetting but also reasoning, attention, insight, abstract
thinking, appreciation and imagination. Modern machine learning models find
and transfer patterns from training data into some form of memory that will be
utilised during inference. In the case of neural networks, long-term memories
on output-input associations are stored in the weights on the connections
between processing units. These connections are a simple analogy of synapses
between neurons and this form of memory simulates the brain’s neocortex
responsible for gradual acquisition of data patterns. Learning in such
scenario is slow since the signal from the output indicating how to adjust the
connecting weights will be both noisy and weak Kumaran et al. (2016). While
receiving training data samples, the learning algorithm performs small update
per sample to reach a global optimisation for the whole set of data.

It is crucial to keep in mind that memory in neural networks does not limit to
the concept of storing associations in the observed data. For example, in
sequential processes, where the individual data points are no longer
independent and identically distributed (i.i.d.), some form of short-term
memory must be constructed across sequence before the output is given to the
network for weight updating. Otherwise, the long-term memory on associations
between the output and inputs, which are given at different timestamps, will
never be achieved. Interestingly, both forms of memory are found in Recurrent
Neural Networks (RNNs) Elman (1990); Jordan (1997); Rumelhart et al. (1988)– a
special type of neural network capable of modeling sequences. The featured
short-term memory, also referred to as working memory, has been known to
relate with locally stable points Hopfield (1982); Sussillo (2014) or
transient dynamics Maass et al. (2002); Jaeger and Haas (2004) of RNNs.
Although these findings shed light into the formation of the working memory,
the beneath memory mechanisms and how they affect the learning process remain
unclear. With the rise of deep learning, more layers with complicated
interconnections between neurons have been added to neural networks. These
complications make it harder to understand and exploit the working memory
mechanisms. Worse still, due to its short-term capacity, the working memory in
RNNs struggles to cope with long sequences. These challenges require new
interpretations and designs of memory for deep learning in general and RNNs in
particular.

In recent years, memory-augmented neural networks (MANNs) emerge as a new form
of memory construction for RNNs. They model external memories explicitly and
thus, overcome the short-term limitation of the working memory. Known as one
of the first attempts at representing explicit memory for RNNs, the Long
Short-Term Memory (LSTM) Hochreiter and Schmidhuber (1997) stores the “world
states” in a cell memory vector, which is determined after a single exposure
of input at each timestep. By referring to the cell memory, LSTM can bridge
longer time lags between relevant input and output events, extending the range
of RNN’s working memory. Recent advances have proposed new external memory
modules with multiple memory vectors (slots) supporting attentional retrieval
and fast-update Graves et al. (2014, 2016); Weston et al. (2014). The memory
slots are accessed and computed fast by a separated controller whose
parameters are slowly learnt weights. Because these memories are external and
separated, it is convenient to derive theoretical explanations on memorisation
capacity Gulcehre et al. (2017); Le et al. (2019). Nonetheless, with bigger
memory and flexible read/write operators, these models significantly
outperform other recurrent counterparts in various long-term sequential
testbeds such as algorithmic tasks Graves et al. (2014, 2016), reasoning over
graphs Graves et al. (2016), continual learning Lopez-Paz et al. (2017), few-
shot learning Santoro et al. (2016); Le et al. (2020a), healthcare Le et al.
(2018c); Prakash et al. (2017); Le et al. (2018b), process analytics Khan et
al. (2018), natural language understanding Le et al. (2018a, 2019) and video
question-answering Gao et al. (2018).

In this thesis, we focus on external memory of MANNs by explaining and
promoting its influence on deep neural architectures. In the original
formulation of MANNs, one controller is allowed to operate on one external
memory. This simple architecture is suitable for supervised sequence labeling
tasks where a sequence of inputs with target labels are provided for
supervised training. However, single controller/memory design is limited for
tasks involving sequence-to-sequence and especially, multi-view sequential
mappings. For example, an electronic medical record (EMR) contains information
on patient’s admissions, each of which consists of various views such as
diagnosis, medical procedure, and medicine. The complexity of view
interactions, together with the unalignment and long-term dependencies amongst
views poses a great challenge for classical MANNs. One important aspect of
external memory is its role in imagination or generative models. Sequence
generation can be supported by RNNs Graves (2013); Chung et al. (2015), yet
how different kinds of memory in RNNs or MANNs cooperate in this process has
not been adequately addressed. Another underexplored problem is to measure
memorisation capacity of MANNs. There is no theoretical analysis or clear
understanding on optimal operations that a memory should have to maximise its
capacity. Finally, the current form of external memory is definitely not the
ultimate memory mechanism for deep learning. Current MANNs are equivalent to
neural simulations of Turing Machines Graves et al. (2014). Hence, in terms of
computational capacity, MANNs are not superior to RNNs, which are known to be
Turing-complete Siegelmann and Sontag (1995). This urges new designs of
external memory for MANNs that express higher computational power and more
importantly, reach the capacity of human memory.

###  1.2 Aims and Scope

This thesis focuses on expanding the capacity of MANNs. Our objectives are:

  * •

To construct a taxonomy for memory in RNNs.

  * •

To design novel MANN architectures for modeling different aspects of memory in
solving complicated tasks, which include multiple processes, generative
memory, optimal operation, and universality.

  * •

To apply such architectures to a wide range of sequential problems, especially
those require memory to remember long-term contexts.

We study several practical problems that require memory:

  * •

_Sequence to sequence mapping and multi-view sequential learning_. The former
can be found in treatment recommendation where given time–ordered medical
history as input, we predict a sequence of future clinical procedures and
medications. The problem is harder than normal supervised sequence labeling
tasks because there are dual processes: input encoding and output decoding.
The latter is even more complicated as the input-output relations not only
extend throughout the sequence length, but also span across views to form
long-term intra-view and inter-view interactions, which is common in drug
prescription and disease progression in healthcare. We aim to extend MANNs to
handle these complexities, introducing generic frameworks to solve multi-view
sequence to sequence mapping problems.

  * •

_Learning generative models for sequential discrete data_. Tasks such as
translation, question-answering and dialog generation would benefit from
stochastic models that can produce a variety of outputs for an input.
Unfortunately, current approaches using neural encoder-decoder models and
their extensions using conditional variational autoencoder often compose short
and dull sentences. As memory plays an important role in human imagination, we
aim to use memory as a main component that blends uncertainty and variance
into neural encoder-decoder models, thereby introducing variability while
maintaining coherence in conversation generation.

  * •

_Ultra-long sequential learning given limited memory resources_. Current RAM-
like memory models maintain memory accessing every timesteps, thus they do not
effectively leverage the short-term memory held in the controller. Previous
attempts try to learn ultra-long sequences by expanding the memory, which is
not always feasible and do not aim to optimise the memory by some theoretical
criterion. It is critical to derive a theoretical bound on the amount of
stored information and formulate an optimisation problem that maximises the
bound under limited memory size constraint. Our theoretical analysis on this
problem results in novel writing mechanisms that exploit the short-term memory
and approximate the optimal solution.

  * •

_Universal sequential learning_. We focus on long-life learning scenarios
where sequences of tasks (subtasks) are handled by an agent, which requires a
memory for tasks to avoid catastrophic forgetting. Similar situations occur
when a Universal Turing Machine simulates any other Turing Machines to perform
universal tasks. Inspired by the stored-program principle in computer
architectures, we aim to build a Neural Stored-program Memory that enables
MANNs to switch tasks through time, adapt to variable contexts and thus fully
resemble the Universal Turing Machine or Von Neumann Architecture.

###  1.3 Significance and Contribution

The significance of this thesis is organised around three central lines of
work: (i) presenting taxonomy of memory in RNNs that arise under distinct
roles and relations to human memory (ii) introducing novel MANN designs to
model different aspects of memory and (iii) applying these designs to a wide
range of practical problems in healthcare, dialog, natural language
processing, few-shot, continual learning, etc. In particular, our
contributions are:

  * •

A survey for various types of memory studied for RNNs. The survey involves
different forms of memory in the brain, popular memory constructions in neural
networks and a taxonomy of external memory based on operational mechanisms as
well as relations to computational models. Several examples of implementations
by modern neural networks are also studied.

  * •

A generic deep learning model using external memory dubbed Dual Controller
Write-Protected Memory Augmented Neural Network for sequence to sequence
mapping. In the encoding phase, the memory is updated as new input is read; at
the end of this phase, the memory holds the history of the inputs. During the
decoding phase, the memory is write–protected and the decoding controller
generates one output at a time. The proposed model is demonstrated on the
MIMIC-III dataset on two healthcare tasks: procedure prediction and medication
prescription.

  * •

A novel MANN architecture named Dual Memory Neural Computer (DMNC) that can
model both synchronous and asynchronous dual view processes. In the modeling
facet, DMNC’s contributions are three-fold: (i) introducing a memory-augmented
architecture for modeling multi-view sequential processes, (ii) capturing
long-term dependencies and different types of interactions amongst views
including intra-view, late and early inter-view interactions, and (iii)
modeling multiple clinical admissions by employing a persistent memory. In the
application facet, we contribute to the healthcare analytic practice by
demonstrating the efficacy of DMNC on drug prescription and disease
progression.

  * •

A Variational Memory Encoder-Decoder (VMED) framework for sequence generation.
VMED introduces variability into encoder-decoder architecture via the use of
external memory as mixture model. By modeling the latent temporal dependencies
across timesteps, our model produces a Mixture of Gaussians representing the
latent distribution. We form a theoretical basis for our model formulation
using mixture prior for every step of generation and apply our proposed model
to conversation generation problem. The results demonstrate that VMED
outperforms recent advances both quantitatively and qualitatively.

  * •

A theory driven approach for optimising memory operations in slot-based MANNs.
We contribute a meaningful measurement on MANN memory capacity. Moreover, we
propose Uniform Writing (UW) and Cached Uniform Writing (CUW) as faster and
optimal writing mechanisms for longer-term memorisation in MANNs. Our models
are grounded in theoretical analysis on the optimality of the introduced
measurement. 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.

  * •

A new type of external memory for neural networks that paves the way for a new
class of MANNs that simulate Universal Turing Machines. The memory, which
takes inspirations from the stored-program memory in computer architecture,
gives memory-augmented neural networks a flexibility to change their control
programs through time while maintaining differentiability. The mechanism
simulates modern computer behavior, where CPU continually reads different
instructions from RAM to execute different functions, potentially making MANNs
truly neural computers.

###  1.4 Thesis Structure

This thesis contains 8 chapters with supplementary materials in the Appendix.
The rest of the thesis is arranged in the following order:

  * •

Chapter 2 presents our survey on taxonomy of memory in RNNs. The chapter first
reviews various memory definitions from cognitive science. A brief
introduction on the most basic neural network–Feedforward Neural Networks and
their fundamental form of memory are then presented. We process to the main
part that covers Recurrent Neural Networks (RNNs) and memory categories for
RNNs based on their formations. Further interpretations on memory taxonomy
based on operational mechanisms and automata simulations are also
investigated.

  * •

Chapter 3 reviews a special branch of memory in RNNs and also the main focus
of this thesis: memory-augmented neural networks (MANNs). We first describe
the Long Short-term Memory (LSTM) and its variants. Next, we also spend a
section for attention mechanism–a featured operation commonly exploited in
accessing external memory in MANNs. We then introduce several advanced
developments that empower RNNs with multiple memory slots, especially generic
slot-based memory architectures such as Neural Turing Machine and
Differentiable Neural Computer.

  * •

Chapter 4 introduces Dual Control Memory-augmented Neural Network (DC-MANN),
an extension of MANN to model sequence to sequence mapping. Our model supports
write-protected decoding (DCw-MANN), which is empirically proved suitable for
sequence-to-sequence task. We further extend our DC-MANN to a broader range of
problems where the input can come from multiple channels. To be specific, we
propose a general structure Dual Memory Neural Computer (DMNC) that can
capture the correlations between two views by exploiting two external memory
units. We conduct the experiments to validate the performance of these models
on applications in healthcare.

  * •

Chapter 5 presents a novel memory-augmented generation framework called
Variational Memory Encoder-Decoder. Our external memory plays a role as a
mixture model distribution generating the latent variables to produce the
output and take part in updating the memory for future generation steps. We
adapt Stochastic Gradient Variational Bayes framework to train our model by
minimising variational approximation of KL divergence to accommodate the
Mixture of Gaussians in the latent space. We derive theoretical analysis to
backup our training protocol and evaluate our model on two open-domain and two
closed-domain conversational datasets.

  * •

Chapter 6 suggests a meaningful measurement on MANN’s memory capacity. We then
formulate an optimisation problem that maximises the bound on the proposed
measurement. The proposed solution dubbed Uniform Writing is optimal under the
assumption of equal timestep contributions. To relax this assumption, 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. To validate the
effectiveness of our solutions, we conduct experiments on six ultra-long
sequential learning problems given a limited number of memory slots.

  * •

Chapter 7 interprets MANNs as neural realisations of Turing Machines. The
chapter points out a missing component–the stored-program memory, that is
potential for making current MANNs truly neural computers. Then, a design of
Neural Stored-program Memory (NSM) is proposed to implement stored-program
principle, together with new MANN architectures that materialise Universal
Turing Machines. The significance of NSM lies in its formulation as a new form
of memory, standing in between slow-weight and fast-weight concepts. NSM not
only induces Universal Turing Machine realisations, which imply universal
artificial intelligence, but also defines another type of adaptive weights,
from which other neural networks can also reap benefits.

  * •

Chapter 8 summarises the main content of the thesis and outlines future
directions.

##  Chapter 2 Taxonomy for Memory in RNNs

###  2.1 Memory in Brain

Memory is a crucial part of any cognitive model studying the human mind. This
section briefly reviews memory types studied throughout the cognitive and
neuroscience literature. Fig. 2.1 shows a taxonomy of cognitive memory
Kotseruba and Tsotsos (2018).

####  2.1.1 Short-term Memory

###### Sensory memory

Sensory memory caches impressions of sensory information after the original
stimuli have ended. It can also preprocess the information before transmitting
it to other cognitive processes. For example, echoic memory keeps acoustic
stimulus long enough for perceptual binding and feature extraction processes.
Sensory memory is known to associate with temporal lope in the brain. In the
neural network literature, sensory memory can be designed as neural networks
without synaptic learning Johnson et al. (2013).

###### Working memory

Working memory holds temporary storage of information related to the current
task such as language comprehension, learning, and reasoning Baddeley (1992).
Just like computer that uses RAM for its computations, the brain needs working
memory as a mechanism to store and update information to perform cognitive
tasks such as attention, reasoning and learning. Human neuroimaging studies
show that when people perform tasks requiring them to hold short-term memory,
such as the location of a flash of light, the prefrontal cortex becomes active
Curtis and D’Esposito (2003). As we shall see later, recurrent neural networks
must construct some form of working memory to help the networks learn the task
at hand. As working memory is short-term Goldman-Rakic (1995), the working
memory in RNNs also tends to vanish quickly and needs the support from other
memory mechanisms to learn complex tasks that require long-term dependencies.

####  2.1.2 Long-term Memory

###### Motor/procedural memory

The procedural memory, which is known to link to basal ganglia in the brain,
contains knowledge about how to get things done in motor task domain. The
knowledge may involve co-coordinating sequences of motor activity, as would be
needed when dancing, playing sports or musical instruments. This procedural
knowledge can be implemented by a set of if-then rules learnt for a particular
domain or a neural network representing perceptual-motor associations Salgado
et al. (2012).

###### Semantic memory

Semantic memory contains knowledge about facts, concepts, and ideas. It allows
us to identify objects and relationships between them. Semantic memory is a
highly structured system of information learnt gradually from the world. The
brain’s neocortex is responsible for semantic memory and its processing is
seen as the propagation of activation amongst neurons via weighted connections
that slowly change Kumaran et al. (2016).

###### Episodic memory

Episodic memory stores specific instances of past experience. Different from
semantic memory, which does not require temporal and spatial information,
episodic remembering restores past experiences indexed by event time or
context Tulving et al. (1972). Episodic memory is widely acknowledged to
depend on the hippocampus, acting like an autoassociate memory that binds
diverse inputs from different brain areas that represent the constituents of
an event Kumaran et al. (2016). It is conjectured that the experiences stored
in hippocampus transfer to neocortex to form semantic knowledge as we sleep
via consolidation process. Recently, many attempts have been made to integrate
episodic memory into deep learning models and achieved promising results in
reinforcement Mnih et al. (2015); Blundell et al. (2016); Pritzel et al.
(2017) and supervised learning Graves et al. (2016); Lopez-Paz et al. (2017);
Le et al. (2018b).

Figure 2.1: Types of memory in cognitive models

###  2.2 Neural Networks and Memory

####  2.2.1 Introduction to Neural Networks

##### Feed-forward neural networks

A feed-forward neural network arranges neurons in layers with connections
going forward from one layer to another, creating a directed acyclic graph.
That is, connections going backwards or between nodes within a layer are
prohibited. Each neuron in the network is a computation unit, which takes
inputs from outputs of other neurons, then applies a weighted sum followed by
a nonlinear transform, and produces an output. The multilayer perceptron (MLP)
is a commonly used feed-forward neural network for classifying data or
approximating an unknown function. An example MLP is shown in Fig. 2.2, with
three layers: input, output and a single “hidden” layer. In order to
distinguish linearly inseparable data points, the activation function must be
nonlinear. The weight of a connection, which resembles synapse of the
neocortex, is simply a coefficient by which the output of a neuron is
multiplied before being taken as the input to another neuron. Hence, the total
input to a neuron $j$ is

$y_{j}=\underset{i}{\sum}w_{ij}x_{i}+b_{j}$ (2.1)

where $x_{i}$ is the output of a neuron $i$, $w_{ij}$ is the weight of the
connection from neuron $i$ to neuron $j$, and $b_{j}$ is a constant offset or
bias. The output of neuron $j$, or $x_{j}$, is the result of applying an
activation function to $y_{j}$. The following lists common activation
functions used in modern neural networks,

$\operatorname{sigmoid}\left(z\right)=\frac{1}{1+e^{-z}}$ (2.2)

$\tanh\left(z\right)=\frac{e^{z}-e^{-z}}{e^{z}+e^{-z}}$ (2.3)

$\operatorname{relu}\left(z\right)=\max(z,0)$ (2.4)

Figure 2.2: A multilayer perceptron with a single hidden-layer.

Given a set of training data with ground truth label for each data points, the
network is typically trained with gradient-based optimisation algorithms,
which estimate the parameters by minimising a loss function. A popular loss
function is the average negative log likelihood

$\mathcal{L}=-\frac{1}{N}\stackrel{{\scriptstyle[}}{{i}}=1]{N}{\sum}\log
P\left(\hat{y}_{i}=y_{i}|x_{i}\right)$ (2.5)

where $N$ is the number of training samples, $x_{i}$ and $y_{i}$ is the $i$-th
data sample and its label, respectively, and $\hat{y_{i}}$ is the predicted
label. During training, forward propagation outputs $\hat{y_{i}}$ and
calculates the loss function. An algorithm called back-propagation, which was
first introduced in Rumelhart et al. (1988), computes the gradients of the
loss function $\mathcal{L}$ with respect to (w.r.t) the parameters
$\theta=\left\\{w_{ij},b_{j}\right\\}$. Then, an optimisation algorithm such
as stochastic gradient descent updates the parameters based on their gradients
$\left\\{\frac{\partial\mathcal{L}}{\partial
w_{ij}},\frac{\partial\mathcal{L}}{\partial b_{j}}\right\\}$ as follows,

$\displaystyle w_{ij}$ $\displaystyle\coloneqq
w_{ij}-\text{$\lambda\frac{\partial\mathcal{L}}{\partial w_{ij}}$}$ (2.6)
$\displaystyle b_{j}$ $\displaystyle\coloneqq
b_{j}-\lambda\frac{\partial\mathcal{L}}{\partial b_{j}}$ (2.7)

where $\lambda$ is a small learning rate.

##### Recurrent neural networks

A recurrent neural network (RNN) is an artificial neural network where
connections between nodes form a directed graph with self-looped feedback.
This allows the network to capture the hidden states calculated so far when
activation functions of neurons in the hidden layer are fed back to the input
layer at every time step in conjunction with other input features. The ability
to maintain the state of the system makes RNN especially useful for processing
sequential data such as sound, natural language or time series signals. So
far, many varieties of RNN have been proposed such as Hopfield Network
Hopfield (1982), Echo State Network Jaeger and Haas (2004) and Jordan Network
Jordan (1997). Here, for the ease of analysis, we only discuss Elman’s RNN
model Elman (1990) with single hidden layer as shown in Fig. 2.3.

Figure 2.3: A typical Recurrent Neural Network (Left) and its unfolded
representation (Right). Each neuron at timestep $t$ takes into consideration
the current input $x_{t}$ and previous hidden state $h_{t-1}$ to generate the
$t$-th output $o_{t}$. $W$, $U$ and $V$ are learnable weight matrices of the
model.

An Elman RNN consists of three layers, which are input
($x\in\mathbb{R^{\mathrm{N}}}$), hidden ($h\in\mathbb{R}^{\mathrm{D}}$) and
output ($o\in\mathbb{R}^{\mathrm{M}}$) layer. At each timestep, the feedback
connection forwards the previous hidden state $h_{t-1}$ to the current hidden
unit, together with the values from input layer $x_{t}$, to compute the
current state $h_{t}$ and output value $o_{t}$. The forward pass begins with a
specification of the initial state $h_{0}$, then we apply the following update
equations

$\displaystyle h_{t}$ $\displaystyle=f\left(h_{t-1}W+x_{t}U+b\right)$ (2.8)
$\displaystyle o_{t}$ $\displaystyle=g\left(h_{t}V+c\right)$ (2.9)

where $b\in\mathbb{R}^{\mathrm{D}}$ and $c\in\mathbb{R}^{\mathrm{M}}$ are the
bias parameters. $U\in\mathbb{R}^{\mathrm{N\times D}}$,
$V\in\mathbb{R}^{\mathrm{D\times M}}$ and $W\in\mathbb{R}^{\mathrm{D\times
D}}$ are weight matrices for input-to-hidden, hidden-to-output and hidden-to-
hidden connections, respectively. $f$ and $g$ are functions that help to add
non-linearity to the transformation between layers. For classification
problems, $g$ is often chosen as the softmax function and the output $o_{t}$
represents the conditional distribution of $t$-th output given previous
inputs. The final output $\hat{y_{t}}$ is the label whose probability score is
the highest. By repeating the updates, one can map the input sequence
$x=\\{x_{1},x_{2},...,x_{T}\\}$ to an output sequence
$\hat{y}=\\{\hat{y}_{1},\hat{y}_{2},...,\hat{y}_{T}\\}$. The total loss for a
given sequence $x$ paired with a ground-truth sequence
$y=\left\\{y_{1},y_{2},...,y_{T}\right\\}$ would then be the sum of the losses
over all the timesteps

$\mathcal{L}\left(y|x\right)=\sum_{t=1}^{T}\mathcal{L}_{t}\left(y_{t}|x_{1},x_{2},...,x_{t}\right)=-\sum_{t=1}^{T}\log
P\left(\hat{y}_{t}=y_{t}|x_{1},x_{2},...,x_{t}\right)$

The loss function can be minimised by using gradient descent approach. The
derivatives w.r.t the parameters can be determined by the Back-Propagation
Through Time algorithm Werbos (1990). RNNs are widely used in sequential tasks
such as language modeling Mikolov et al. (2010), handwriting generation Graves
(2013) and speech recognition Graves et al. (2013). RNNs demonstrate better
performance than other classical approaches using Hidden Markov Model (HMM) or
Conditional Random Fields (CRFs).

####  2.2.2 Semantic Memory in Neural Networks

Neural networks learn structured knowledge representation from the data by
adjusting connection weights amongst the units in the network under supervised
training paradigms Hinton et al. (1986); Rumelhart et al. (1988); Plunkett and
Sinha (1992). The connection weights capture the semantic structure of the
domain under modeling McClelland et al. (1995); Rogers and McClelland (2004).
The trained model generalises to novel examples rather than just naively
memorising training items. However, modern deep learning models are often
massively over-parameterised and thus prone to overfitting, even to noise
Zhang et al. (2016b). Further investigations indicate that although deep
networks may employ brute-force memorising strategy, they should operate in a
fashion that can perform inductive generalisation Arpit et al. (2017); Krueger
et al. (2017). Unfortunately, since all of these arguments are validated
empirically or via simulations, no theoretical principles governing semantic
knowledge extraction were given.

The lack of theoretical guarantee remained until recently when __ Saxe et al.
(2019) confirmed the existence of semantic memory in neural network by
theoretically describing the trajectory of knowledge acquisition and
organisation of neural semantic representations. The paper is restricted to a
simple linear neural network with one hidden layer. The network is trained to
correctly output the associated properties or features of the input items
(e.g., dog $\rightarrow$bark, horse $\rightarrow$big). Each time a training
sample $i$ is presented as $\left\\{x_{i},y_{i}\right\\}$, the weights of the
network $W_{1}$ and $W_{2}$ are adjusted by a small amount to gradually
minimise the squared error loss
$\mathcal{L}=\left\|y_{i}-\hat{y_{i}}\right\|^{2}$. The parameter update rule
is derived via standard back propagation as follows,

$\displaystyle\Delta W_{1}$ $\displaystyle=\lambda
W_{2}^{\top}\left(y_{i}-\hat{y_{i}}\right)x_{i}^{\top}$ (2.10)
$\displaystyle\Delta W_{2}$
$\displaystyle=\lambda\left(y_{i}-\hat{y_{i}}\right)\left(W_{1}x_{i}\right)^{\top}$
(2.11)

where $\lambda$ is the learning rate. We are interested in estimating the
total weight change after epoch $t$, which can be approximated, when
$\lambda\ll 1$, as the following,

$\displaystyle\Delta W_{1}\left(t\right)$ $\displaystyle\approx\lambda
PW_{2}\left(t\right)^{\top}\left(\varSigma^{yx}-W_{2}\left(t\right)W_{1}\left(t\right)\varSigma^{x}\right)$
(2.12) $\displaystyle\Delta W_{2}\left(t\right)$ $\displaystyle\approx\lambda
P\left(\varSigma^{yx}-W_{2}\left(t\right)W_{1}\left(t\right)\varSigma^{x}\right)W_{1}\left(t\right)^{\top}$
(2.13)

where $P$ is the number of training samples;
$\varSigma^{x}=E\left[xx^{\top}\right]$ and
$\varSigma^{yx}=E\left[yx^{\top}\right]$ are input and input-output
correlation matrices, respectively. We can take the continuum limit of this
difference equation to obtain the following system of differential equations

$\displaystyle\tau\frac{d}{dt}W_{1}$
$\displaystyle=W_{2}^{\top}\left(\varSigma^{yx}-W_{2}W_{1}\varSigma^{x}\right)$
(2.14) $\displaystyle\tau\frac{d}{dt}W_{2}$
$\displaystyle=\left(\varSigma^{yx}-W_{2}W_{1}\varSigma^{x}\right)W_{1}^{\top}$
(2.15)

where $\tau=\frac{1}{P\lambda}$. To simplify the equations, we assume
$\varSigma^{x}=I$ and apply reparametrisation trick to obtain

$\displaystyle\tau\frac{d}{dt}\overline{W}_{1}$
$\displaystyle=\overline{W}_{2}^{\top}\left(S-\overline{W}_{2}\overline{W}_{1}\right)$
(2.16) $\displaystyle\tau\frac{d}{dt}\overline{W}_{2}$
$\displaystyle=\left(S-\overline{W}_{2}\overline{W}_{1}\right)\overline{W}_{1}^{\top}$
(2.17)

where $S$ is the diagonal matrix in the singular value decomposition of
$\varSigma^{yx}=USV^{\top}$; $\overline{W}_{1}$ and $\overline{W}_{2}$ are new
variables such that $W_{1}=R\overline{W}_{1}V^{\top}$ and
$W_{2}=U\overline{W}_{2}R$ with an arbitrary orthogonal matrix $R$. When
$\overline{W}_{1}\left(0\right)$ and $\overline{W}_{2}\left(0\right)$ are
initialised with small random weights, we can approximate them with diagonal
matrices of equal modes. A closed form solution of the scalar dynamic
corresponding to each mode of Eqs. (2.16) and (2.17) can be derived as
follows,

$a_{\alpha}\left(t\right)=\frac{s_{\alpha}e^{2s_{\alpha}t/\tau}}{e^{2s_{\alpha}t/\tau}-1+s_{\alpha}/a_{\alpha}\left(0\right)}$
(2.18)

where $a_{\alpha}$ is a diagonal element of the time-dependent diagonal matrix
$A\left(t\right)$ such that
$A\left(t\right)=\overline{W}_{2}\left(t\right)\overline{W}_{1}\left(t\right)$
. Inverting the change of variables yields

$\displaystyle W_{1}\left(t\right)$
$\displaystyle=Q\sqrt{A\left(t\right)}V^{\top}$ (2.19) $\displaystyle
W_{2}\left(t\right)$ $\displaystyle=U\sqrt{A\left(t\right)}Q^{-1}$ (2.20)

where $Q$ is an arbitrary invertible matrix. If the initial weights are small,
then the matrix $Q$ will be close to a rotation matrix. Factoring out the
rotation, the hidden representation of item $i$ is

$h_{i}^{\alpha}\left(t\right)=\sqrt{a_{\alpha}\left(t\right)}v_{i}^{\alpha}$
(2.21)

where $v_{i}^{\alpha}=V^{\top}\left[\alpha,i\right]$. Hence, we obtain a
temporal evolution of internal representations $h$ of the deep network. By
using multi-dimensional scaling (MDS) visualisation of the evolution of
internal representations over developmental time, Saxe et al. (2019)
demonstrated a progressive differentiation of hierarchy in the evolution,
which matched the data’s underlying hierarchical structure. When we have the
explicit form of the evolution (Eq. (2.21)), this matching can be proved as an
inevitable consequence of deep learning dynamics when exposed to
hierarchically structured data Saxe et al. (2019).

####  2.2.3 Associative Neural Networks

Associative memory is used to store associations between items. It is a
general concept of memory that spans across episodic, semantic and motor
memory in the brain. We can use neural networks (either feed-forward or
recurrent) to implement associative memory. There are three kinds of
associative networks:

  * •

Heteroassociative networks store $Q$ pair of vectors
$\left\\{x^{1}\in\mathcal{X},y^{1}\in\mathcal{Y}\right\\}$, …,
$\left\\{x^{Q}\right.\in\mathcal{X},$ $\left.y^{Q}\in\mathcal{Y}\right\\}$
such that given some key $x^{k}$, they return value $y^{k}$.

  * •

Autoassociative networks are a special type of the heteroassociative networks,
in which $y^{k}=x^{k}$ (each item is associated with itself).

  * •

Pattern recognition networks are also a special case where $x^{k}$ is
associated with a scalar $k$ representing the item’s category.

Basically, these networks are used to represent associations between two
vectors. After two vectors are associated, one can be used as a cue to
retrieve the other. In principle, there are three functions governing an
associative memory:

  * •

Encoding function
$\otimes:\mathcal{X}\times\mathcal{\mathcal{Y}}\to\mathcal{M}$ associates
input items into some form of memory trace $\mathcal{M}$.

  * •

Trace composition function
$\mathcal{\oplus:M}\times\mathcal{\mathcal{M}}\to\mathcal{\mathcal{M}}$
combines memory traces to form the final representation for the whole dataset.

  * •

Decoding function
$\bullet:\mathcal{X}\times\mathcal{\mathcal{M}}\to\mathcal{\mathcal{Y}}$
produces a (noisy) version of the item given its associated.

Different models employ different kinds of functions (linear, non-linear, dot
product, outer product, tensor product, convolution, etc.). Associative memory
concept is potential to model memory in the brain Marr and Thach (1991). We
will come across some embodiment of associative memory in the form of neural
networks in the next sections.

###  2.3 The Constructions of Memory in RNNs

####  2.3.1 Attractor dynamics

Attractor dynamics denotes neuronal network dynamics which is dominated by
groups of persistently active neurons. In general, such a persistent
activation associates with an attractor state of the dynamics, which for
simplicity, can take the form of fixed-point Amit (1992). This kind of network
can be used to implement associative memory by allowing the network’s
attractors to be exactly those vectors we would like to store Rojas (2013).
The approach supports memory for the items per se, and thus differs from
semantic memory in the sense that the items are often stored quickly and what
being stored cannot represent the semantic structure of the data. Rather,
attractor dynamics resembles working and episodic memory. Like episodic
memory, it acts as an associative memory, returning stored value when
triggered with the right clues. The capacity of attractor dynamics is low,
which reflects the short-term property of working memory. In the next part of
the sub-section, we will study these characteristics through one embodiment of
attractor dynamics.

##### Hopfield network

The Hopfield network, originally proposed in 1982 Hopfield (1982), is a
recurrent neural network that implements associative memory using fix-points
as attractors. The function of the associative memory is to recognise
previously learnt input vectors, even in the case where some noise has been
added. To achieve this function, every neuron in the network is connected to
all of the others (see Fig. 2.4 (a)). Each neuron outputs discrete values,
normally $1$ or $-1$, according to the following equation

$x_{i}\left(t+1\right)=\operatorname{sign}\left(\stackrel{{\scriptstyle[}}{{j}}=1]{N}{\sum}w_{ij}x_{j}\left(t\right)\right)$
(2.22)

where $x_{i}\left(t\right)$ is the state of $i$-th neuron at time $t$ and $N$
is the number of neurons. Hopfield network has a scalar value associated with
the state of all neurons $x$, referred to as the "energy" or Lyapunov
function,

$E\left(x\right)=-\frac{1}{2}\stackrel{{\scriptstyle[}}{{i}}=1]{N}{\sum}\stackrel{{\scriptstyle[}}{{j}}=1]{N}{\sum}w_{ij}x_{i}x_{j}$
(2.23)

If we want to store $Q$ patterns $x^{p}$, $p=1,2,...,Q$, we can use the
Hebbian learning rule Hebb (1962) to assign the values of the weights as
follows,

$w_{ij}=\stackrel{{\scriptstyle[}}{{p}}=1]{Q}{\sum}x_{i}^{p}x_{j}^{p}$ (2.24)

which is equivalent to setting the weights to the elements of the correlation
matrix of the patterns111As an associative memory, Hopfield network implements
$\otimes$, $\oplus$, $\bullet$ by outer product, addition and nonlinear
recurrent function, respectively. .

Upon presentation of an input to the network, the activity of the neurons can
be updated (asynchronously) according to Eq. (2.22) until the energy function
has been minimised Hopfield (1982). Hence, repeated updates would eventually
lead to convergence to one of the stored patterns. However, the network will
possibly converge to spurious patterns (different from the stored patterns) as
the energy in these spurious patterns is also a local minimum.

##### The capacity problem

The memorisation of some pattern can be retrieved when the network produces
the desired vector $x^{p}$ such that
$x\left(t+1\right)=x\left(t\right)=x^{p}$. This happens when the crosstalk
computed by

$\stackrel{{\scriptstyle[}}{{q}}=1,q\neq p]{Q}{\sum}x^{q}\left(x^{p}\cdot
x^{q}\right)$ (2.25)

is less than $N$. If the crosstalk term becomes too large, it is likely that
previously stored patterns are lost because when they are presented to the
network, one or more of their bits are flipped by the associative computation.
We would like to keep the probability that this could happen low, so that
stored patterns can always be recalled. If we set the upper bound for one bit
failure at 0.01, the maximum capacity of the network is $Q\thickapprox 0.18N$
Rojas (2013). With this low capacity, RNNs designed as attractor dynamics have
difficulty handling big problems with massive amount of data.

Figure 2.4: (a) Hopfield network with five neurons. (b) Structure of a Liquid
State Machine $M$. The machine wants to transform input stream $u(\cdot)$ into
output stream $y(\cdot)$ using some dynamical system $L^{M}$ (the liquid).

####  2.3.2 Transient Dynamics

One major limitation of memorising by attractor mechanisms is the incapability
of remembering sequences of past inputs. This demands a new paradigm to
explain the working memory mechanism that enable RNNs to capture sequential
dependencies and memorise information between distance external stimuli.
Within this new paradigm, the trajectories of network states should become the
main carriers of information about external sensory stimuli. Recent proposals
Maass et al. (2002); Maass (2011); Jaeger and Haas (2004) have suggested that
an arbitrary recurrent network could store information about recent input
sequences in its transient dynamics despite the presence of attractors (the
pattern might or might not converge to the attractors). A useful analogy is
the surface of a liquid. Transient ripples on the surface can encode
information about past objects that were thrown in even though the water
surface has no attractors Ganguli et al. (2008). In the light of transient
dynamics, RNNs carry past information to serve a given task as a working
memory.

##### Liquid State Machines

Liquid State Machines (LSMs) Maass et al. (2002) use a dynamic
reservoir/liquid ($L^{M}$), which consists of nodes randomly connected to each
other, to handle time-series data. The purpose is to map an input function of
time $u\left(t\right)$–a continuous sequence of disturbances, to an output
function $y\left(t\right)$ that provides a real-time analysis of the input
sequence. In order to achieve that, we assume that at every time $t$, $L^{M}$
generates an internal “liquid state” $x^{M}\left(t\right)$, which constitutes
its current response to preceding perturbations $u(s)$ for $s\leq t$. After a
certain time-period, the state of the liquid $x^{M}\left(t\right)$ is read as
input for a readout network $f^{M}$, which by assumption, has no temporal
integration capability of its own. This readout network learns to map the
states of the liquid to the target outputs as illustrated in Fig. 2.4 (b).

All information about the input $u(s)$ from preceding time points $s\leq t$
that is needed to produce a target output $y(t)$ at time $t$ has to be
contained in the current liquid state $x^{M}\left(t\right)$. LSMs allow
realisation of large computational power on functions of time even if all
memory traces are continuously decaying. Instead of worrying about the code
and location where information about past inputs is stored, the approach
focuses on addressing the separation question: for which later time point $t$
will any two significantly different input functions of time $u\left(t\right)$
and $v\left(t\right)$ cause significantly different liquid states
$x_{u}^{M}(t)$ and $x_{v}^{M}(t)$ Maass (2011).

Most implementations of LSMs use the reservoir of untrained neurons. In other
words, there is no need to train the weights of the RNN. The recurrent nature
of the connections fuses the input sequence into a spatio-temporal pattern of
neuronal activation in the liquid and computes a large variety of nonlinear
functions on the input. This mechanism is theoretically possible to perform
universal continuous computations. However, separation and approximation
properties must be fulfilled for the system to work well. Similar neural
network design can be found in Echo state networks Jaeger and Haas (2004). A
Liquid State Machine is a particular kind of spiking neural networks that more
closely mimics biological neural networks Maass (1997).

##### Memory trace of recurrent networks

When viewing recurrent networks as transient dynamics, one may want to measure
the lifetimes of transient memory traces in the networks. Ganguli et al.
(2018) studied a discrete time network whose dynamics is given by

$x_{i}\left(n\right)=f\left(\left[Wx\left(n-1\right)\right]_{i}+v_{i}s\left(n\right)+z_{i}\left(n\right)\right),\,i=1,...,N$
(2.26)

Here, a scalar time-varying signal $s(n)$ drives an RNN of $N$ neurons. $x(n)$
is the network state at $n$-th timestep, $f(\cdot)$ is a general sigmoidal
function, $W$ is an $N\times N$ recurrent connectivity matrix, and $v$ is a
vector of feed-forward connections encoding the signal into the network.
$z(n)$ denotes a zero mean Gaussian white noise with covariance $\left\langle
z_{i}(k_{1}),z_{j}(k_{2})\right\rangle=\text{$\varepsilon\delta_{k_{1},k_{2}}$$\delta_{i,j}$}$.

The authors built upon Fisher information to construct useful measures of the
efficiency with which the network state $x(n)$ encodes the history of the
signal $s\left(n\right)$, which can be derived as

$J\left(k\right)=v^{\top}W^{k\top}\left(\varepsilon\stackrel{{\scriptstyle[}}{{k}}=0]{\infty}{\sum}W^{k}W^{k\top}\right)^{-1}W^{k}v$
(2.27)

where $J\left(k\right)$ measures the Fisher information that $x(n)$ retains
about a signal entering the network at $k$ time steps in the past. For a
special case of normal networks having a normal connectivity matrix $W$, Eq.
(2.27) simplifies to

$J\left(k\right)=\stackrel{{\scriptstyle[}}{{i}}=1]{N}{\sum}v_{i}^{2}\left|\lambda_{i}\right|^{2k}\left(1-\left|\lambda_{i}\right|^{2}\right)$
(2.28)

where $\lambda_{i}$ is the $i$-th eigenvalue of $W$. For large k, the decay of
the Fisher information is determined by the magnitudes of the largest
eigenvalues and it decays exponentially. Similar findings with different
measurements on the memory trace in modern recurrent networks are also found
in a more recent work Le et al. (2019).

###  2.4 External Memory for RNNs

Recurrent networks can in principle use their feedback connections to store
representations of recent input events in the form of implicit memory (either
attractor or transient dynamics). Unfortunately, from transient dynamics
perspective, the implicit memory tends to decay quickly Ganguli et al. (2008);
Le et al. (2019). This phenomenon is closely related to gradient
vanishing/exploding problems Bengio et al. (1994); Hochreiter and Schmidhuber
(1997); Pascanu et al. (2013) which often occur when training RNNs with
gradient-based algorithms such as Back-Propagation Through Time Williams and
Zipser (1989); Werbos (1990). A solution is to equip RNNs with external memory
to cope with exponential decay of the implicit short-term memory. The external
memory enhances RNNs with stronger working Hochreiter and Schmidhuber (1997);
Cho et al. (2014b); Graves et al. (2014, 2016) or even episodic-like memory
Graves et al. (2014); Santoro et al. (2016). We will spend the next sections
to analyse different types of external memory and their memory operation
mechanisms. Examples of modern recurrent neural networks that utilise external
memory are also discussed.

####  2.4.1 Cell Memory

Despite the fact that RNNs offer working memory mechanisms to handle
sequential inputs, learning what to put in and how to utilise the memory is
challenging. Back-Propagation Through Time Williams and Zipser (1989); Werbos
(1990) is the most common learning algorithm for RNNs, yet it is inefficient
in training long sequences mainly due to insufficient or decaying backward
error signals. This section will review the analysis of this problem and study
a group of methodologies that overcome the problem through the use of cell
memory and gated operation.

Figure 2.5: Error back flow from $\vartheta_{u}\left(t\right)$ to
$\vartheta_{v}\left(t-q\right)$ in the computation graph. Each computation
node has $n$ children. Each product term corresponds to a computation path of
depth $q$ from node $u$ to $v$. The sum of $n^{q-1}$ products is the total
error.

##### Hochreiter’s analysis on gradient vanishing/exploding problems

Let us assume that the hidden layer of an RNN has $n$ neurons. With
differentiable activation function $f_{i}$, the activation of a neuron $i$ at
step $t$ of the recurrent computation is as follow,

$\displaystyle y^{i}\left(t\right)$
$\displaystyle=f_{i}\left(\underset{j}{\sum}w_{ij}y^{j}\left(t-1\right)\right)$
(2.29) $\displaystyle=f_{i}\left(net_{i}\left(t\right)\right)$ (2.30)

The backpropagated error signal for neuron $j$ at step $t$ is

$\vartheta_{j}\left(t\right)=f_{j}^{\prime}\left(net_{j}\left(t\right)\right)\underset{i}{\sum}w_{ij}\vartheta_{i}\left(t+1\right)$
(2.31)

The error occurring at an arbitrary neuron $u$ at time step $t$
($\vartheta_{u}\left(t\right)$) is backpropagated through time for $q$
timesteps to an arbitrary neuron $v$ ($\vartheta_{v}\left(t-q\right)$). We can
measure the contribution of the former to the latter as the following,

$\frac{\partial\vartheta_{v}\left(t-q\right)}{\partial\vartheta_{u}\left(t\right)}=\begin{cases}f_{v}^{\prime}\left(net_{v}\left(t-1\right)\right)w_{uv}&;q=1\\\
f_{v}^{\prime}\left(net_{v}\left(t-q\right)\right)\sum_{l=1}^{n}\frac{\partial\vartheta_{l}\left(t-q+1\right)}{\partial\vartheta_{u}\left(t\right)}w_{lv}&;q>1\end{cases}$
(2.32)

By induction, we can obtain expressive form of the recursive Eq. (2.32) as

$\frac{\partial\vartheta_{v}\left(t-q\right)}{\partial\vartheta_{u}\left(t\right)}=\sum_{l_{1}=1}^{n}...\sum_{l_{q-1}=1}^{n}\prod_{m=1}^{q}f_{l_{m}}^{\prime}\left(net_{l_{m}}\left(t-m\right)\right)w_{l_{m}l_{m-1}}$
(2.33)

where $l_{q}=v$ and $l_{0}=u$. The computation can be visually explained
through a drawing of the computation graph as in Fig. 2.5.

It is obvious to realise that if
$\left|f_{l_{m}}^{\prime}\left(net_{l_{m}}\left(t-m\right)\right)w_{l_{m}l_{m-1}}\right|$
is greater (smaller) than $1$ for all $m$, then the largest product increases
(decreases) exponentially with $q$, which represents the exploding and
vanishing gradient problems in training neural networks. These problems are
critical since they prevent proper update on the weights of the model, and
thus freeze or disturb the learning process. With nonlinear activation
functions such as $\operatorname{sigmoid}$, the term
$\left|f_{l_{m}}^{\prime}\left(net_{l_{m}}\right)w_{l_{m}l_{m-1}}\right|$ goes
to zero when $w_{l_{m}l_{m-1}}\to\infty$ and is less than $1$ when
$\left|w_{l_{m}l_{m-1}}\right|<4$, which implies vanishing gradient tends to
occur with nonlinear activation function.

We can also rewrite Eq. (2.32) in matrix form for $q>1$ as follows,

$\frac{\partial\vartheta_{v}\left(t-q\right)}{\partial\vartheta_{u}\left(t\right)}=W_{u}^{\top}F^{\prime}\left(t-1\right)\prod_{m=2}^{q-1}\left(WF^{\prime}\left(t-m\right)\right)W_{v}f_{v}^{\prime}\left(net_{v}\left(t-q\right)\right)$
(2.34)

where the weight matrix $W$ have its elements $W_{ij}=w_{ij}$. $W_{u}$ and
$W_{v}$ are $u$’s incoming weight vector and $v$’s outgoing weight vector,
respectively, such that $\left[W_{u}\right]_{i}=w_{ui}$ and
$\left[W_{v}\right]_{i}=w_{vi}$. $F^{\prime}\left(t-m\right)$ is a diagonal
matrix whose diagonal elements
$F^{\prime}\left(t-m\right)_{ii}=f_{i}^{\prime}\left(net_{i}\left(t-m\right)\right)$.
Using a matrix norm $\left\|\cdot\right\|_{A}$ compatible with vector norm
$\left\|\cdot\right\|_{p}$, we define

$f_{max}^{\prime}\coloneqq\max_{m=1,...,q}\left\\{\left\|F^{\prime}\left(t-m\right)\right\|_{A}\right\\}$
(2.35)

By applying norm sub-multiplicativity and using the inequality

$\left|x^{T}y\right|\leq
n\left\|x\right\|_{\infty}\left\|y\right\|_{\infty}\leq
n\left\|x\right\|_{p}\left\|y\right\|_{p},$

we obtain a weak upper bound for the contribution

$\left|\frac{\partial\vartheta_{v}\left(t-q\right)}{\partial\vartheta_{u}\left(t\right)}\right|\leq
n\left(f_{max}^{\prime}\left\|W\right\|_{A}\right)^{q}$ (2.36)

This result confirms the exploding and vanishing gradient problems since the
error backprob contribution decays (when
$f_{max}^{\prime}\left\|W\right\|_{A}$ < 1) or grows (when
$f_{max}^{\prime}\left\|W\right\|_{A}$ >1) exponentially with $q$. More recent
analyses on the problems are presented by Bengio et al., (1994) and Pascanu et
al., (2013).

##### Problem with naive solution

When analysing a single neuron $j$ with a single connection to itself,
avoiding the exploding and vanishing gradient problems requires

$f_{j}^{\prime}\left(net_{j}\left(t\right)\right)w_{jj}=1$ (2.37)

In this case, the constant error flow is enforced by using linear function
$f_{j}$ and constant activation (e.g., $f_{j}\left(x\right)=x$ with $\forall
x$ and setting $w_{jj}=1$). These properties are known as the _constant error
carousel_ (CEC). The strict constraint makes this solution unattractive
because it limits computation capacity of RNNs with linear activation. Even
worse, neuron $j$ is connected to other neurons as well, which makes thing
complicated. Let us consider an additional input weight $w_{ji}$ connecting
neuron $i$ to $j$. $w_{ji}$ is learnt to keep relevant external input from $i$
such that $w_{ji}y_{i}>0$ when the input signal $y_{i}$ is relevant. Assume
that the loss function is reduced by keeping neuron $j$ active ($>0$) for a
while between two occurrences of two relevant inputs. During that period,
activation of neuron $j$ is possibly disturbed since with a fixed $w_{ji}$,
$w_{ji}y_{i}<0$ with irrelevant inputs. Since
$y^{j}\left(t\right)=f_{j}\left(w_{jj}y^{j}\left(t-1\right)+w_{ji}y^{i}\left(t-1\right)\right)$
where $f_{j}$ is linear, $y^{j}\left(t-1\right)$ is kept constant and
$y^{i}\left(t-1\right)$ scales with the external input, it is likely to
deactivate neuron $j$. Hence, if naively following CEC, learning a $w_{ji}$ to
capture relevant inputs while protecting neuron $j$ from disturbances of
irrelevant inputs is challenging (input weight conflict Hochreiter and
Schmidhuber (1997)). Similar problem happens with the output weight (output
weight conflict). These conflicts make the learning hard, and require a more
flexible mechanism for controlling input/output weight impact conditioned on
the input signal.

##### The original Long Short-Term Memory (LSTM)

Hochreiter and Schmidhuber (1997) originally proposed LSTM using
multiplicative gate units and a memory cell unit to overcome the weight
conflicts while following CEC. The idea is to apply CEC to neurons specialised
for memorisation, each of which has an internal state independent from the
activation function. This separation between memorisation and computation is
essential for external memory concept. Besides, to control input/output weight
impact, gate units conditioned on the inputs are multiplied with the
incoming/outgoing connections, modifying the connection value through time. In
particular, if a neuron $c_{j}$ becomes cell memory, its output is computed as

$y^{c_{j}}\left(t\right)=y^{out_{j}}\left(t\right)h\left(s_{c_{j}}\left(t\right)\right)$
(2.38)

where $y^{out_{j}}\left(t\right)$ is the output gate, $h$ is a differentiable
function for scaling down the neuron’s output, and $s_{c_{j}}$ captures past
information by using the dynamics

$\displaystyle s_{c_{j}}\left(0\right)$ $\displaystyle=0$ (2.39)
$\displaystyle s_{c_{j}}\left(t\right)$
$\displaystyle=y^{fg_{j}}\left(t\right)s_{c_{j}}\left(t-1\right)+y^{in_{j}}\left(t\right)f\left(net_{c_{j}}\left(t\right)\right)\,\mathrm{for}\,t>0$
(2.40)

where $y^{in_{j}}\left(t\right)$ is the input gate, $y^{fg_{j}}\left(t\right)$
is the (optional) forget gate and $f$ is the activation function, which can be
nonlinear. Without forget gate, $c_{j}$ can be viewed as a neuron with an
additional fixed self-connection. The computation paths that mainly pass
through this special neuron preserve the backward error. The remaining problem
is to protect this error from disturbance from other paths. The gates are
calculated as

$y^{g_{j}}\left(t\right)=f_{g_{j}}\left(\sum_{u}w_{g_{j}u}y^{u}\left(t-1\right)\right)$
(2.41)

where $g$ can represent input, output and forget gate. The gates are adaptive
according to the input from other neurons, hence, it is possible to learn
$\left\\{w_{g_{j}u}\right\\}$ to resolve the input/output weight conflict
problem.

Although the cell memory provides a potential solution to cope with training
RNN over long time lag, unfortunately, in practice, the multiplicative gates
are not good enough to overcome a fundamental challenge of LSTM: the gates are
not coordinated at the start of training, which can cause $s_{c_{j}}$ to
explode quickly (internal state drift). Various variants of LSTM have been
proposed to tackle the problem Greff et al. (2016). We will review some of
them in Chapter 3.

##### Cell memory as external memory

From Eq. (2.40), we can see the internal state of the cell memory holds two
types of information: (i) the previous cell state and (ii) the normal state of
RNN, which is the activation of current computation. Therefore, the cell state
contains a new form of external memory for RNNs. The size of the memory is
often equal the number of hidden neurons in RNNs and thus, cell memory is also
known as vector memory. The memory supports writing and reading mechanisms
implemented as gated operations in $y^{in_{j}}\left(t\right)$ and
$y^{out_{j}}$, respectively. They control how much to write to and read from
the cell state. With the cell state, which is designed to keep information
across timesteps, the working memory capacity of LSTM should be greater than
that of RNNs. The memory reading and writing are also important to determine
the memory capacity. For instance, if writing irrelevant information too
often, the content in the cell state will saturate and the memory fails to
hold much information. Later works make use of the gating mechanism to build
skip-connections between inputs (a source of raw memory) and neurons in higher
layers Srivastava et al. (2015); He et al. (2016), opening chance to ease the
training of very deep networks.

####  2.4.2 Holographic Associative Memory

The holographic associative memory (HAM) roots its operation on the principle
of optical holography, where two beams of light are associated with one
another in a holograms such that reconstruction of one original beam can be
made by presenting another beam. Recall that the capacity of associative
memory using attractor dynamics is low. To maintain $Q$ pairs of key-value (in
Hopfield network, value is also key), it requires $N^{2}$ weight storage where
$Q\approx 0.18N$. HAM presents a solution to compress the key-values into a
fixed size vector via Holographic Reduced Representation (HRR) without
substantial loss of information Plate (1995). This can be done in real or
complex domain using circular convolution or element-wise complex
multiplication for the encoding function ($\otimes$), respectively. The
compressed vector ($\mathcal{M}$), as we shall see, can be used as external
memory for RNNs.

##### Holographic Reduced Representation

Consider a complex-valued vector key $x\in\mathbb{C}^{N}$,

$x=\left[x_{a}\left[1\right]e^{ix_{\phi}\left[1\right]},...,x_{a}\left[N\right]e^{ix_{\phi}\left[N\right]}\right]$
(2.42)

The association encoding is computed by

$\displaystyle m$ $\displaystyle=x\circledast y$ (2.43)
$\displaystyle=\left[x_{a}\left[1\right]y_{a}\left[1\right]e^{i\left(x_{\phi}\left[1\right]+y_{\phi}\left[1\right]\right)},...,x_{a}\left[N\right]y_{a}\left[N\right]e^{i\left(x_{\phi}\left[N\right]+y_{\phi}\left[N\right]\right)}\right]$
(2.44)

where $\circledast$ is element-wise complex multiplication, which multiplies
the moduli and adds the phases of the elements. Trace composition function is
simply addition

$m=x^{1}\circledast y^{1}+x^{2}\circledast y^{2}+...+x^{Q}\circledast y^{Q}$
(2.45)

Although the memory $m$ is a vector with the same dimension as that of stored
items, it can store many pairs of items since we only need to store the
information that discriminates them. The decoding function is multiplying an
inverse key
$x^{-1}=\left[x_{a}\left[1\right]^{-1}e^{-ix_{\phi}\left[1\right]},...,x_{a}\left[N\right]^{-1}e^{-ix_{\phi}\left[N\right]}\right]$
with the memory as follows,

$\displaystyle\tilde{y}$ $\displaystyle=x^{-1}\circledast m$ (2.46)
$\displaystyle=x^{-1}\circledast\left(\sum_{\forall k}x^{k}\circledast
y^{k}\right)$ (2.47) $\displaystyle=y+x^{-1}\circledast\left(\sum_{\forall
k:x^{k}\neq x}x^{k}\circledast y^{k}\right)$ (2.48)

The second term in Eq. (2.48) is noise and should be minimised. Under certain
conditions, the noise term has zero mean Plate (1995). One way to reconstruct
better is to pass the retrieved vector through an auto-associative memory to
correct any errors.

##### Redundant Associative Long Short-Term Memory

One recent attempt to apply HRR to LSTM is the work by Danihelka et al.
(2016). The authors first propose Redundant Associative Memory, an extension
of HRR with multiple memory traces for multiple transformed copies of each key
vector. In particular, each key vector will be transformed $S$ times using $S$
constant random permutation matrix $P_{s}$. Hence, we obtain the memory trace
$c_{s}$ for the $s$-th copy

$c_{s}=\sum_{\forall k}\left(P_{s}x^{k}\right)\circledast y^{k}$ (2.49)

The $k$-th value is retrieved as follows,

$\displaystyle\tilde{y}^{k}$
$\displaystyle=\frac{1}{S}\sum_{s=1}^{S}\left(\overline{P_{s}x^{k}}\right)\circledast
c_{s}$ (2.50) $\displaystyle=y^{k}+\sum_{k^{\prime}\neq
k}y^{k^{\prime}}\circledast\frac{1}{S}\sum_{s=1}^{S}P_{s}\left[\overline{x^{k}}\circledast
x^{k^{\prime}}\right]$ (2.51)

where $\overline{P_{s}x^{k}}$ and $\overline{x^{k}}$ are the complex
conjugates of $P_{s}x^{k}$ and $x^{k}$, respectively, which are equal to the
inverses if the modulus $x_{a}^{k}=1$. Since permuting the key decorrelates
the retrieval noise, the noise term has variance $O\left(\frac{Q}{S}\right)$
and increase the number of copies will enhance retrieval quality.

Applying the idea to LSTM, we can turn the cell memory to a holographic memory
by encoding the term containing input activation in Eq. (2.40) before added up
to the cell memory. The network learns to generate the key $x^{k}$ and the
inverse key $\left(x^{-1}\right)^{k}$ for $k$-th timestep. It should be noted
that the inverse key at $k$-th timestep can associate to some preceding key.
Following Redundant Associative Memory extension, multiple copies of cell
memory are employed. The cell state will be decoded to retrieve some past
input activation necessary for current output Danihelka et al. (2016). Then
the decoded value will be multiplied with the output gate as in Eq. (2.38).

####  2.4.3 Matrix Memory

##### Correlation matrix memory

Correlation Matrix Memory (CMM) stores associations between pairs of vectors
using outer product as the encoding function. Although the purpose looks
identical to that of attractor dynamics, CMM is arranged differently using
feed-forward neural network without self-loop connections. The memory
construction ($\otimes+\oplus$) follows Hebbian learning

$M=\sum_{i=1}^{Q}y_{i}x_{i}^{\top}$ (2.52)

where $Q$ is the number of stored patterns, $x_{i}$ and $y_{i}$ are the $i$-th
key-value pair. The memory retrieval ($\bullet$) is simply dot product

$\displaystyle\tilde{y_{j}}$ $\displaystyle=Mx_{j}$ (2.53)
$\displaystyle=\left(\sum_{i=1}^{Q}y_{i}x_{i}^{\top}\right)x_{j}$ (2.54)
$\displaystyle=\sum_{i=1,i\neq
j}^{Q}y_{i}x_{i}^{\top}x_{j}+y_{j}\left\|x_{j}\right\|^{2}$ (2.55)

If the keys are orthonormal, then the retrieval is exact. Actually, linear
independence is enough for exact retrieval. In this case, WidrowHoff learning
rule should be used.

When the stored values are binary vectors, a threshold function is applied.
The capacity for binary CMM is heavily dependent on the sparsity of the
patterns (the sparser the better). In general, CMM offers a capacity that is
at least comparable to that of the Hopfield model Baum et al. (1988).

##### Fast-weight

Fast-weights refer to synapses that change slower than neuronal activities but
much faster than the standard slow weights. These fast weights form temporary
memories of the recent past that support the working memory of RNNs Hinton and
Plaut (1987); Schmidhuber (1992); Ba et al. (2016). In a recent fast-weight
proposal Ba et al. (2016), the memory is similar to a correlation matrix
memory with decaying factor to put more weight on the recent past. In
particular, the fast memory weight matrix $A$ is computed as follows,

$A\left(t\right)=\lambda A\left(t-1\right)+\eta
h\left(t\right)h\left(t\right)^{\top}$ (2.56)

where $\lambda$ and $\eta$ are the decay and learning rate, respectively.
$h\left(t\right)$ is the hidden state of the RNN and also the pattern being
stored in the associative memory. The memory is used to iteratively refine the
next hidden state of RNN as the following,

$h_{s+1}\left(t+1\right)=f\left(\left[Wh\left(t\right)+Cx\left(t\right)\right]+A\left(t\right)h_{s}\left(t+1\right)\right)$
(2.57)

where $h_{0}\left(t+1\right)=f\left(Wh\left(t\right)+Cx\left(t\right)\right)$,
following the ordinary dynamics of RNNs and $h_{s}\left(t+1\right)$ is the
hidden state at $s$-th step of refinement.

##### Tensor product representation

Tensor product representation (TPR) is a mechanism to store symbolic
structures. It shares common properties with CMM when the tensor is of order
2, in which tensor product is equivalent to outer product. In TPR, relations
between concepts are described by the set of filler-role bindings. The vector
space of filler and role are denoted as $V_{\mathcal{F}}$ and
$V_{\mathcal{R}}$, respectively. The TPR is defined as a tensor $T$ in a
vector space $V_{\mathcal{F}}\otimes V_{\mathcal{R}}$, where $\otimes$ is the
tensor product operator, which is computed as

$T=\sum_{i}f_{i}\otimes r_{i}$ (2.58)

where $f_{i}$ and $r_{i}$ are vectors representing some filler and role,
respectively. The tensor dot product $\bullet$ is used to decode the memory as
follows,

$f_{j}=T\bullet r_{j}$ (2.59)

For example, the following 4 concepts have relations: _dog_(_bark_) and
_horse_(_big_) in which the set of filler is
$\mathcal{F}=\left\\{bark,horse\right\\}$ and the set of role is
$\mathcal{R}=\left\\{bark,big\right\\}$. The TPR of these concepts is

$T=f_{dog}\otimes r_{bark}+f_{horse}\otimes r_{big}$ (2.60)

Or we can encode a tree structure as in Fig. 2.6 (a) by the following
operations:

$\displaystyle T$ $\displaystyle=A\otimes r_{0}\otimes+\left(B\otimes
r_{0}+C\otimes r_{1}\right)\otimes r_{1}$ (2.61) $\displaystyle=A\otimes
r_{0}\otimes+B\otimes r_{0}\otimes r_{1}+C\otimes r_{1}\otimes r_{1}$ (2.62)
$\displaystyle=A\otimes r_{0}\otimes+B\otimes r_{01}+C\otimes r_{11}$ (2.63)

This mechanism allows storing symbolic structures and grammars and thus
supports reasoning. For further details, we refer readers to the original work
Smolensky (1990) and recent application to deep learning Schlag and
Schmidhuber (2018); Le et al. (2020b).

Figure 2.6: (a) Example of a tree encoded by TPR. (b) SDM’s memory write (red)
and read (blue) access. The read and write involve all memory locations around
the queried points.

####  2.4.4 Sparse Distributed Memory

Matrix memory is a direct extension to vector memory for RNNs. There are two
ways to build a matrix memory: correlation matrix memory (or tensor memory)
and sparse distributed memory. While the former focuses on storing the
associations amongst items (e.g., Hopfield network, Holographic memory and
CMM), the latter aims to store each item as a high-dimensional vector, which
is closer to Random Access Memory in computer architecture. Because each
vector is physically stored in a memory slot, we also refer to this model as
slot-based memory. Sparse distributed memory (SDM) can represent correlation
matrix memory, computer memory, feed-forward artificial neural networks and
associative-memory models of the cerebellum. Such a versatility naturally
results in SDM’s applications to RNN as one form of external memory.

##### Kanerva memory model

In 1988, Pentti Kanerva introduced the SDM as a new approach to model human
long-term memory Kanerva (1988). The model revolves around a simple idea that
the distances between concepts in our minds correspond to the distances
between points of a high-dimensional space. As we, when hinted by key signals,
tend to remember specific things such as individual, object, scene and place,
the brain must make the identification nearly automatic, and high-dimensional
vectors as internal representations of things do that. Another important
property of high dimensional spaces is that distance between two random points
should be far, which allows inexact representation of the point of interest.
In other words, using long vectors to store items enables a fault-tolerant and
robust memory.

The SDM stores items (binary vectors) in a large number of hard locations or
memory slots whose addresses ($m_{a}$) are given by binary strings of length
$D$, randomly distributed throughout the address space
$\left\\{0,1\right\\}^{D}$. Input to the memory consists of two binary
patterns, an address pattern (location to be accessed) and a content pattern
(item to be stored). The pattern is called self-addressing when its content is
also its address. Furthermore, in SDM, each memory slot $m$ is armed with a
vector of counters $m_{c}$ initialised to $0$ with the same length of the
content. The memory operations are based on similarity between the addresses.

1:input $x$ and SDM

2:Find a set of chosen locations $M(x)$ using Eq. (2.64)

3:for each $m$ in $M(x)$ do

4: for $i=1,D$ do

5: if $x_{c}[i]==1$ then

6: $m_{c}[i]\mathrel{+}=1$

7: else

8: $m_{c}[i]\mathrel{-}=1$

9: end if

10: end for

11:end for

Algorithm 1 Memory writing in SDM

###### Memory writing

When storing input item $x=\left(x_{a},x_{c}\right)$ to the SDM, the address
pattern $x_{a}$ is compared against all memory location addresses. Relevant
physical locations to consider are those which lie within a hypersphere of
radius $r$ centered on the address pattern point

$M\left(x\right)=\left\\{m:d\left(m_{a},x_{a}\right)<r\right\\}$ (2.64)

where $d$ is some similarity measure between 2 vectors. In the original model,
Kanerva used Hamming distance. The content is distributed in the set of
locations $M\left(x\right)$ as in Algo. 1.

###### Memory reading

Basically, reading from any point in the memory space pools the data of all
nearby locations. Given a cue address $x_{a}^{\prime}$, contents of the
counters at locations near $x_{a}^{\prime}$ are summed and thresholded at zero
to return the binary content. The proximity criteria still follows Eq. (2.64).
The reading mechanism allows SDM to retrieve data from imprecise or noisy
cues. Fig. 2.6 (b) visualises the memory access behaviors.

The assumption underlying the original SDM are: (i) the location addresses are
fixed, and only the contents of the locations are modifiable, (ii) the
locations are sparse and distributed across the address space
$\left\\{0,1\right\\}^{D}$ (e.g., randomly sample $10^{6}$ addresses from an
address space of $1000$ dimensions ). These assumptions make the model perform
well on storing random input data.

###### SDM as an associative matrix memory

We can implement SDM by using three operations of associative memory. The
minimum setting for this implementation includes:

  * •

A hard-address matrix $A\in\mathbb{B}^{N\times D}$ where $N$ and $D$ are the
numbers of memory locations and the dimension of the address space,
respectively.

  * •

A counter (content) matrix $C\in\mathbb{B}^{N\times D}$.

  * •

Cosine similarity is used to measure proximity.

  * •

Threshold function $\boldsymbol{y}$ that maps distances to binary
values:$\boldsymbol{y}\left(d\right)=1$ if $d\geq r$ and vice versa.

  * •

Threshold function $\boldsymbol{z}$ that converts a vector to binary vector:
$\boldsymbol{z}\left(x\right)=1$ if $x\geq 0$ and vice versa.

Then, the memory writing ($\otimes+\oplus$) and reading ($\bullet$) become

$\displaystyle C$ $\displaystyle\coloneqq
C+\boldsymbol{y}\left(Ax_{a}\right)x_{c}^{\top}$ (2.65) $\displaystyle
x_{c}^{\prime}$
$\displaystyle=\boldsymbol{z}\left(C^{\top}\boldsymbol{y}\left(Ax_{a}^{\prime}\right)\right)$
(2.66)

These expressions are closely related to attention mechanisms commonly used
nowadays (Sec. 3.2.2).

In general, SDM overcomes limitations of correlation matrix memory such as
Hopfield network since the number of stored items in SDM is not limited by the
number of processing elements. Moreover, one can design SDM to store a
sequence of patterns. Readers are referred to Keeler (1988) for a detailed
comparison between SDM and Hopfield network Keeler (1988).

##### Memory-augmented neural networks and attention mechanisms

The current wave of deep learning has leveraged the concept of SDM to external
neural memory capable of supporting the working memory of RNNs Weston et al.
(2014); Graves et al. (2014, 2016); Miller et al. (2016). These models enhance
the SDM with real-valued vectors and learnable parameters. For example, the
matrices $A$ and $C$ can be automatically generated by a learnable neural
network. To make whole architecture learnable, differentiable functions and
flexible memory operations must be used. Attention mechanisms are the most
common operations used in MANNs to facilitate the similarity-based memory
access of SDM. Through various ways of employing attentions, RNNs can access
the external memory in the same manner as one accesses SDM. Details on neural
distributed (slot-based) memory and attention mechanisms will be provided in
Chapter 3.

###  2.5 Relation to Computational Models

Automatons are abstract models of machines that perform computations on an
input by moving through a series of states Sipser et al. (2006). Once the
computation reaches a finish state, it accepts and possibly produces the
output of that input. In terms of computational capacity, there are three
major classes of automaton:

  * •

Finite-state machine

  * •

Pushdown automata

  * •

Turing machine

Pushdown automata and Turing machine can be thought of as extensions of
finite-state machines (FSMs) when equipped with an external storage in the
form of stack and memory tape, respectively. With stored-program memory, an
even more powerful class of machines, which simulates any other Turing
machines, can be built as universal Turing machine Turing (1936). As some
Turing machines are also universal, they are usually regarded as one of the
most general and powerful automata besides universal Turing machines.

One major objective of automata theory is to understand how machines compute
functions and measure computation power of models. For example, RNNs, if
properly wired, are Turing-complete Siegelmann and Sontag (1995), which means
they can compute arbitrary sequences if they have unlimited memory.
Nevertheless, in practice, RNNs struggle to learn from the data to predict
output correctly given simple input sequence Bengio et al. (1994). This poses
a question on the effective computation power of RNNs.

Another way to measure the capacity of RNNs is via simulations of operations
that they are capable of doing. The relationship between RNNs and FSMs has
been discovered by many Giles et al. (1992); Casey (1996); Omlin and Giles
(1996); Tiňo et al. (1998), which suggest that RNNs can mimic FSMs by training
with data. The states of an RNN must be grouped into partitions representing
the states of the generating automation. Following this line of thinking, we
can come up with neural architectures that can simulate pushdown automata,
Turing machine and universal Turing machine. Neural stack is an example which
arms RNN with a stack as its external memory Mozer and Das (1993); Joulin and
Mikolov (2015); Grefenstette et al. (2015). By simulating push and pop
operations, which are controlled by the RNN, neural stack mimics the working
mechanism of pushdown automata. Neural Turing Machine and its extension
Differentiable Neural Computer Graves et al. (2014, 2016) are prominent neural
realisations of Turing machine. They use an RNN controller to read from and
write to an external memory in a manner resembling Turing machine’s operations
on its memory tape. Since the memory access is not limited to the top element
as in neural stack, these models have more computational flexibility. Until
recently, Le et al.__(2020) extended the simulation to the level of universal
Turing machine Le et al. (2020a); Le and Venkatesh (2020) by employing the
stored-program principle Turing (1936); von Neumann (1993). We save a thorough
analysis on the correspondence between these MANNs and Turing machines for
Chapter 7. Here, we briefly draw a correlation between models of recurrent
neural networks and automata (see Fig. 2.7 ).

It should be noted that the illustration is found on the organisation of
memory in the models rather than the computational capacity. For example, some
Turing machines are equivalent to universal Turing machine in terms of
capacity; RNNs are on par with other MANNs because they are all Turing-
complete. Having said that, when neural networks are organised in a way that
simulates powerful automata, their effective capacity is often greater and
thus, they tend to perform better in complicated sequential learning tasks
Graves et al. (2014, 2016); Le et al. (2020a). A similar taxonomy with proof
of inclusion relation amongst models can be found in the literature Ma and
Principe (2018).

Figure 2.7: Relation between external memory and computational models

###  2.6 Closing Remarks

We have briefly reviewed different kinds of memory organisations in the neural
network literature. In particular, we described basic neural networks such as
Feed-forward and Recurrent Neural Networks and their primary forms of memory
constructions, followed by a taxonomy on mathematical models of well-known
external memory designs based on memory operational mechanisms and relations
to automation theory. In the next chapter, we narrow the scope of literature
review to the main content of this thesis: Memory-augment Neural Networks and
their extensions.

##  Chapter 3 Memory-augmented Neural Networks

###  3.1 Gated RNNs

####  3.1.1 Long Short-Term Memory

Despite its ability to model temporal dependencies in sequential data, RNNs
face a big mathematical challenge of learning long sequences. The basic
problem is that gradients propagated over many steps tend to either vanish or
explode. Although the explosion can be prevented with the use of activation
functions (i.e., $\tanh$ or sigmoid) that restrict the range of update values,
the vanishing problem remains with these nonlinear activation functions (Sec.
2.4.1). The difficulty with long-term dependencies arises from the
exponentially smaller weights given to long-term interactions compared to
short-term ones. In practice, experiments have shown that RNNs might find it
hard to learn sequences of only length 10 or 20 Bengio et al. (1994).

Long Short-Term Memory (LSTM) Hochreiter and Schmidhuber (1997) is introduced
as a simple yet clever way to alleviate the problem. The core idea is to
produce paths where the gradient can flow for long duration by adding a linear
self-loop memory cell to the computation of the hidden unit. Notably, the
weight of the linear self-loop is gated (controlled by another hidden unit)
and dependent on the input. This enables the network to dynamically moderate
the amount of information passed by the hidden unit. In LSTM, there is a
system of gating units that controls the flow of information, as illustrated
in Fig. 3.1. The modern LSTM model is slightly different from the original
LSTM presented in Sec. 2.4.1, in which we move from neuronal to vector
representation with additional parameters.

Figure 3.1: Block diagram of a modern LSTM unit. $\times$ and $+$ are element-
wise product and add operators, respectively. $\sigma$ and $\tanh$ are sigmoid
and tanh functions, respectively.

The most important component is the cell memory $c_{t}$, which has a linear
self-loop formulation

$c_{t}=f_{t}\ast c_{t-1}+i_{t}\ast\tilde{c_{t}}$ (3.1)

where $f_{t}$ is the forget gate, $c_{t-1}$ is the previous cell value,
$i_{t}$ is the input gate, $\tilde{c_{t}}$ is the candidate value for current
cell memory and $\ast$ denotes element-wise multiplication. Similar to RNN’s
hidden state computation (Eq. (2.8)), $\tilde{c_{t}}$ is calculated as the
following,

$\tilde{c_{t}}=\tanh\left(W_{c}h_{t-1}+U_{c}x_{t}+b_{c}\right)$ (3.2)

The gates are also functions of previous hidden state and current input with
different parameters

$\displaystyle f_{t}$
$\displaystyle=\sigma\left(W_{f}h_{t-1}+U_{f}x_{t}+b_{f}\right)$ (3.3)
$\displaystyle i_{t}$
$\displaystyle=\sigma\left(W_{i}h_{t-1}+U_{i}x_{t}+b_{i}\right)$ (3.4)
$\displaystyle o_{t}$
$\displaystyle=\sigma\left(W_{o}h_{t-1}+U_{o}x_{t}+b_{o}\right)$ (3.5)

where $\sigma$ is the sigmoid function that keeps the gate values in range
$\left[0,1\right]$. The final hidden state $h_{t}$ is computed based on the
cell memory $c_{t}$, gated by the output gate $o_{t}$ as follows,

$h_{t}=o_{t}\ast\tanh\left(c_{t}\right)$ (3.6)

Given the hidden state $h_{t}$, other computations for the output $o_{t}$ are
the same as in Elman’s RNN (Eq. (2.9)).

In LSTM, the forget gate $f_{t}$ plays a crucial role in enabling the network
to capture long-term dependencies. If $f_{t}\rightarrow 1$, the previous
memory will be preserved and thus, the product of derivatives associated with
a distant input is close to one. This allows a distant input to take part in
the backpropagation update and slow down the gradient vanishing process. If
$f_{t}\rightarrow 0$, the path to previous cells is disconnected and the model
tends to remember only short-term events.

Empirical results have shown that LSTM networks learn long-term dependencies
more easily than the simple RNNs. State-of-the-art performances were obtained
in various challenging sequence processing tasks Graves and Schmidhuber
(2005); Vinyals and Le (2015). Other simpler alternatives to LSTM have been
studied including Highway Networks Srivastava et al. (2015) and GRUs Cho et
al. (2014b).

####  3.1.2 Gated Recurrent Unit

One simplified variant of LSTM is Gated Recurrent Unit (GRU) Cho et al.
(2014b), which uses two multiplicative gates to harness the vanishing
gradients problem and capture longer dependencies in the sequence. Unlike
LSTM, GRU does not require a separate memory cell. At each timestep, using a
reset gate $r_{t}$, the model computes a candidate hidden state
$\tilde{h_{t}}$ as follows,

$\displaystyle r_{t}$
$\displaystyle=\sigma\left(W_{r}x_{t}+U_{r}h_{t-1}+b_{r}\right)$ (3.7)
$\displaystyle\tilde{h_{t}}$
$\displaystyle=\tanh\left(W_{h}x_{t}+U_{h}\left(r_{t}\ast
h_{t-1}\right)+b_{h}\right)$ (3.8)

The candidate hidden state is determined by current input and previous hidden
state. When $r_{t}$ is close to 0, the candidate hidden state is reset with
the current input, allowing the model to delete any irrelevant information
from the past. The hidden state is then updated by linear interpolation
between the previous hidden state and the candidate hidden state

$h_{t}=z_{t}\ast h_{t-1}+\left(1-z_{t}\right)\ast\tilde{h_{t}}$ (3.9)

where an update gate $z_{t}$ decides how much the hidden state should update
its content. The removal of input gate prevents the amount of information in
the hidden states from exploding. $z_{t}$ is computed by

$\displaystyle z_{t}$
$\displaystyle=\sigma\left(W_{z}x_{t}+U_{z}h_{t-1}+b_{z}\right)$ (3.10)

A main advantage of GRU compared with LSTM is that GRU can run faster while
maintaining comparable performance Chung et al. (2014). The reduction of
parameters also helps GRU less overfit to training data as LSTM does.

###  3.2 Attentional RNNs

####  3.2.1 Encoder-Decoder Architecture

Intuitively, attention mechanism is motivated by human visual attention where
our eyes are able to focus on a certain region of an image/language with “high
resolution” while perceiving the surrounding context in “low resolution”. This
focus is adjusted dynamically overtime and directly contributes to our
decision making process. Before going into details, we will briefly review
sequence-to-sequence model–a recurrent architecture that is often used with
attention mechanism.

Amongst sequential modeling tasks, sequence-to-sequence mapping is one of the
most challenging one whose practical applications may include machine
translation, document summarisation and dialog response generation. To solve
such tasks, we may use an RNN-like encoder to model the input sequence and
then an RNN-like decoder to model the output sequence. To link the two models,
the final hidden state of the encoder (thought vector) is passed to the
decoder as the latter’s initial hidden state (see Fig. 3.2 (a)). This encoder-
decoder architecture, often referred to as Seq2Seq, is firstly introduced by
Cho et al. (2014) and has demonstrated superior performance over LSTM in
machine translation Cho et al. (2014a); Sutskever et al. (2014b).

Figure 3.2: (a) Seq2Seq Model. Gray and green denote the LSTM encoder and
decoder, respectively. In this architecture, the output at each decoding step
can be fed as input for the next decoding step. (b) Seq2Seq Model with
attention mechanism. The attention computation is repeated across decoding
steps.

####  3.2.2 Attention Mechanism

Even when applying LSTM to Seq2Seq helps to ease the gradient vanishing in
general, the decoder in Seq2Seq is likely to face this problem when the number
of decoding steps becomes larger. Given that the decoder receives a fixed-size
though vector representing the whole input sequence, it is hard to recover the
contribution of distant encoding input in predicting decoder’s outputs. To
overcome this, Bahdanau et al. (2015) proposed using attention mechanism in
encoder-decoder architecture. The key idea is to let the decoder look over
every piece of information that the original input sequence holds at every
decoding step, which is equivalent to creating a direct connection from a
decoder unit to any encoder unit (see Fig. 3.2 (b)). Each connection then will
be weighted by an attention score, which is a function of hidden states from
both encoder and decoder. The weight $\alpha_{ij}$ between the $i$-th decoding
step and the $j$-th encoding step is defined as

$\displaystyle e_{ij}$ $\displaystyle=v^{T}\tanh\left(Ws_{i-1}+Uh_{j}\right)$
(3.11) $\displaystyle\alpha_{ij}$
$\displaystyle=\frac{\exp\left(e_{ij}\right)}{\stackrel{{\scriptstyle[}}{{k}}=1]{L}{\sum}\exp\left(e_{ik}\right)}$
(3.12)

where $e_{ij}$ is the unnormalised weight, $v$ is a parametric vector and $W$,
$U$ are parametric matrices. $s$ and $h$ are used to denote the hidden state
of the decoder and the encoder, respectively. Eq. (3.12) is the well-known
softmax function to make the weights sum to one over $L$ encoding steps. Then,
a context vector for the $i$-th decoding step is computed using a weighted
summation of all encoder’s hidden states as follows,

$c_{i}=\stackrel{{\scriptstyle[}}{{j}}=1]{L}{\sum}\alpha_{ij}h_{j}$ (3.13)

Finally, the context vector $c_{i}$ is combined with the decoder hidden state
$s_{i}$ to compute the $i$-th decoder’s output and next state Bahdanau et al.
(2015). Attention mechanism has several modifications such as hard attention
Xu et al. (2015) and pointer network Vinyals et al. (2015).

####  3.2.3 Multi-Head Attention

Traditional RNNs read a sequence step by step to extract sequential
dependencies, which is slow and hard to capture far apart relations. Attention
helps link two distant timesteps quickly and thus, shows potential to replace
completely RNNs in modeling sequential data. However, the vanilla attention
mechanism is shallow with one step of computation per timestep, which relies
on the hidden state of RNNs for richer representation. In an effort to replace
RNNs with attention, Vaswani et al. (2017) proposed a deeper attention
mechanism with multiple heads implemented efficiently using dot-product
operation. The model reads all timesteps in the sequence at once like Feed-
forward Neural Networks, which utilises parallel computing. Moreover, multiple
keys, values and queries are packed into matrices $K$, $V$ and $Q$,
respectively. Then, the multi-head attention operation is computed as follows,

$Attention\left(Q,K,V\right)=\operatorname{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V$
(3.14)

where $d_{k}$ is the number of key dimension. The multi-head attention lies at
the core of self-attention mechanism, in which, relational features are
encoded from the input sequence (Fig. 3.3 (a)). Similarly, the output sequence
features can be extracted and combined with the encoded input to form an
encoder-decoder architecture called The Transformer. (Fig. 3.3 (b)).

The Transformer has empirically demonstrated that attention alone can replace
recurrent models in solving sequential tasks including machine translation and
language parsing Vaswani et al. (2017). This opens a new research direction in
deep learning where attention can be used to extract relations between time-
ordered events. The limitation of self-attention is its quadratic complexity.
However, this can be compensated with parallel computation ability. Detailed
discussion of this new research angle is beyond the scope of this thesis.
Instead, we will focus on slot-based memory networks, another approach with
attention that is built upon a readable/writable external memory. The approach
resembles closely SDM as well as human associative memory.

Figure 3.3: Computation stages of the encoding using self-attention (a) and
encoding-decoding architecture–The Transformer (b). Embedding layers convert
input/output tokens to vectors of fix dimension, followed by Positional
Encoding layers that add temporal information to each vector. The main block
of computation combines multi-head attention, residual connection, layer
normalisation and Feed-forward layers, which can be repeated multiple times.

###  3.3 Slot-Based Memory Networks

####  3.3.1 Neural Stack

Traditional stack is a storage of elements that works on the principle of
last-in-first-out, which describes the order in which the elements come off a
stack. In general, stack supports two operations: push, which adds an element
to the stack, and pop, which removes the most recently added element (the top
one). Additionally, a peek operation may give access to the value of the top
element without modifying the stack. Stack is a convenient memory for solving
problems with hierarchical structures because it stores the temporary results
in a way that supports backtracking and tree traversal. Recently, researchers
have tried to implement continuously differentiable prototype of traditional
stacks using deep networks Joulin and Mikolov (2015); Grefenstette et al.
(2015). We briefly review the implementations proposed by Grefenstette et al.
(2015) that aim to mimic Stack, Queue and Deque on solving natural language
transduction problems.

In the implementations, a row-expandable matrix $V$ is used to store the data.
The $i$-th row $V\left[i\right]$ is associated with a strength scalar
$s\left[i\right]$. When $v_{t}$–the item at timestep $t$– is presented, its
value is added to the matrix $V$ and never be modified, which yields,

$V_{t}\left[i\right]=\begin{cases}V_{t-1}\left[i\right]=v_{i}&\mathrm{if}\,1\leq
i<t\\\ v_{t}&\mathrm{if}\,i=t\end{cases}$ (3.15)

To modify the stack content under push and pop operations, we modify the
strength vector instead as the following,

$s_{t}\left[i\right]=\begin{cases}\max\left(0,s_{t-1}\left[i\right]-\max\left(0,u_{t}-\sum_{j=i+1}^{t-1}s_{t-1}\left[j\right]\right)\right)&\mathrm{if}\,1\leq
i<t\\\ d_{t}&\mathrm{if}\,i=t\end{cases}$ (3.16)

where $u_{t}$ and $d_{t}$ are the pop and push signals generated by a neural
network, respectively. Basically, the strength for the top item is set to the
push signal. Then, we want to subtract the strength of stored items
($s_{t}\left[i\right]$) by an amount of the pop signal $\left(u_{t}\right)$
from the top (highest index) to the bottom (lowest index) of the stack. If the
pop signal is greater than the strength, the strength of the item is set to
$0$ (totally popped out of the stack) and the remainder of the pop signal is
passed to lower items until we run out of pop signal. The peek or read
operation is carried out by

$r_{t}=\stackrel{{\scriptstyle[}}{{i}}=1]{t}{\sum}\left(\min\left(s_{t}\left[i\right],\max\left(0,1-\sum_{j=i+1}^{t}s_{t}\left[j\right]\right)\right)\right)V_{t}\left[i\right]$
(3.17)

The output $r_{t}$ of the read operation is the weighted sum of the rows of
$V_{t}$, scaled by the temporary strength values created during the traversal.
Intuitively, items with zero strength do not contribute to read value and
items on the bottom contribute less than those near the top. Neural Queue and
DeQue can be implemented in similar manners by modifying Eqs. (3.15)-(3.17).

A controller implemented as RNN is employed to control stack operations. The
current input $i_{t}$ from the sequence and the previous read-out $r_{t-1}$
will be concatenated as input for the RNN to produce the current hidden state
$h_{t}$ and the controller output $o_{t}^{\prime}$. The controller output will
be used to generate the item, control signals and final output of the whole
network as follows,

$\displaystyle d_{t}$
$\displaystyle=\sigma\left(W_{d}o_{t}^{\prime}+b_{d}\right)$ (3.18)
$\displaystyle u_{t}$
$\displaystyle=\sigma\left(W_{u}o_{t}^{\prime}+b_{u}\right)$ (3.19)
$\displaystyle v_{t}$
$\displaystyle=\tanh\left(W_{v}o_{t}^{\prime}+b_{v}\right)$ (3.20)
$\displaystyle o_{t}$
$\displaystyle=\tanh\left(W_{o}o_{t}^{\prime}+b_{o}\right)$ (3.21)

Experiments have demonstrated that the proposed models are capable of solving
transduction tasks for which LSTM-based models falter Grefenstette et al.
(2015).

####  3.3.2 Memory Networks

One solution to ensure a model will not forget is to create a slot-based
memory module and store every piece of information into the memory slots. The
memory can be implemented as a matrix $M\in\mathbb{R}^{N\times D}$ whose rows
contain vectors representing the considering piece of information. Here, $N$
is the number of slots and $D$ is the dimension of the representation vector
(word size). Following this principle, Memory Network (MemNN) Weston et al.
(2014) stores all information (e.g., knowledge base or background context)
into an external memory. When there is a retrieval request, it assigns a
relevance probability to each memory slot using content-based attention
scheme, and reads contents from each memory slot by taking their weighted sum.
Since the model is designed for language understanding, each slot of the
memory often associates with a document or a sentence. When a query/question
about facts related to the stored documents is presented, MemNN will perform
content-based attention as follows,

$p_{i}=\operatorname{softmax}\left(u^{T}m_{i}\right)$ (3.22)

where $u$ is the feature and $m_{i}$ is the memory’s $i$-th row vector, which
represent the query and the stored document, respectively. $p_{i}$ is the
attention score to the $i$-th memory slot, normalised by softmax function.

The output of the memory, given query $u$, is the read vector

$r=\stackrel{{\scriptstyle[}}{{i}}=1]{N}{\sum}p_{i}c_{i}$ (3.23)

where $c_{i}$ is the output vector corresponding to the $i$-th slot. In MemNN,
it is trainable parameter while in key-value memory network Miller et al.
(2016), it comes from the data. Then, the model can make prediction by feeding
the read values to another feed-forward neural network.

A multi-hop version MemN2N has also been studied and outperforms LSTM and
MemNN in question-answering tasks Sukhbaatar et al. (2015). MemN2N extends
MemNN by adding refinement updates on the query and the read-out. The
refinement reads

$u_{k+1}=Hu_{k}+r_{k}$ (3.24)

where $H$ is a parametric matrix and $k$ is the refinement step.

Although memory networks have big advantages over LSTM due to the use of
external matrix memory, it is hard to scale to big dataset since the number of
memory slots grows linearly with the number of data. Some tricks such as
hashing have been proposed but they have a trade-off between capacity and
accuracy. More importantly, it is unlikely that we tend to store everything in
our brain. We have the ability to forget the old memory and update with new
knowledge, which is ignored by memory network designs.

####  3.3.3 Neural Turing Machine

In contrast to MemNN, Neural Turing Machine (NTM) Graves et al. (2014)
introduces a slot-based read/write mechanism to the memory module. The memory
size does not need to equal the number of considering pieces of information.
The model learns to overwrite obsolete or unimportant memory slots with recent
and useful information to optimise a final goal. This writing scheme fits with
sequential task where the prediction goal can be achieved without paying
attention to all timestep inputs. To control the memory operations, NTM uses a
neural controller network whose parameters are slow-learning weights. The
controller is responsible for determining instantly after each timestep the
content to be read from and written to the memory. An illustration of NTM
components is described in Fig. 3.4 (a).

Figure 3.4: (a) Architecture of NTM. Circles denote intermediate variables
computed by the controller. The controller takes the current timestep data
$x_{t}$ and the previous read value $r_{t-1}$ as the input and produces
$r_{t}$, updates memory $M_{t}$ and predict output $o_{t}$. (b) Architecture
of DNC. The operation is similar to NTM’s with extra modules to keep track of
memory usage $u_{t}$, precedence $p_{t}$ and link matrix $L_{t}$.

In NTM, both reading and writing locations are determined by the address,
which is a weight over the memory slots. The weight is initially computed by
the content-based attention,

$w_{t}^{c}\left(i\right)=\frac{\exp\left(\beta_{t}m\left(k_{t},M_{t}\left(i\right)\right)\right)}{\stackrel{{\scriptstyle[}}{{j}}=1]{D}{\sum}\exp\left(\beta_{t}m\left(k_{t},M_{t}\left(j\right)\right)\right)}$
(3.25)

Here, $w_{t}^{c}\in\mathbb{R}^{N}$ is the content-based weight, $\beta_{t}$ is
a strength scalar, $m$ is a matching function that measures the similarity
between a key $k_{t}\in\mathbb{R}^{D}$ and the $i$-th memory slot
$M_{t}\left(i\right)$. In practice, $m$ is implemented as cosine similarity

$m\left(k_{t},M_{t}(i)\right)=\frac{k_{t}\cdot
M_{t}(i)}{||k_{t}||\cdot||M_{t}(i)||}$ (3.26)

Besides the content-based addressing, NTM supports location-based addressing
started with an interpolation between content-based weight and the previous
weight

$w_{t}^{g}=g_{t}w_{t}^{c}+\left(1-g_{t}\right)w_{t}$ (3.27)

where $g_{t}$ is the interpolation gate. This allows the system to learn when
to use (or ignore) content-based addressing. Also, the model is able to shift
focus to other rows by performing convolution shift modulo $R$ as the
following,

$\tilde{w_{t}}\left(i\right)=\stackrel{{\scriptstyle[}}{{j}}=0]{R}{\sum}w_{t}^{g}\left(i\right)s_{t}\left(i-j\right)$
(3.28)

where $s_{t}$ is the shift weighting. Finally, sharpening is used to prevent
the shifted weight from blurring, which results in the final weight

$w_{t}\left(i\right)=\frac{\tilde{w_{t}}\left(i\right)^{\gamma}}{\underset{j}{\sum}\tilde{w_{t}}\left(j\right)^{\gamma}}$
(3.29)

Given the weight calculated, the memory update is defined by using these
bellowing equations

$\displaystyle M_{t}^{erased}\left(i\right)$
$\displaystyle=M_{t-1}\left(i\right)\left[1-w_{t}\left(i\right)e_{t}\right]$
(3.30) $\displaystyle M_{t}\left(i\right)$
$\displaystyle=M_{t}^{erased}\left(i\right)+w_{t}\left(i\right)v_{t}$ (3.31)

where $e_{t}\in\mathbb{R}^{D}$ and $v_{t}\in\mathbb{R}^{D}$ are erase vector
and update vector, respectively. The read value is computed using the same
address weight as follows,

$r=\stackrel{{\scriptstyle[}}{{i}}=1]{N}{\sum}w_{t}\left(i\right)M_{t}\left(i\right)$
(3.32)

The controller can be implemented as a feed-forward network or LSTM fed with
an concatenation of the read-out $r_{t}$ and the timestep data $x_{t}$. The
computation of the output $o_{t}$ follows the same computing mechanism of the
controller network (see Sec. 3.1.1).

With a fixed size external memory, NTM can scale well when dealing with very
long sequence while maintaining better remembering capacity than other
recurrent networks such as RNN, GRU and LSTM. Experiments have shown NTM
outperforms LSTM by a huge margin in memorisation testbeds including copy,
repeat copy, associative recall and priority sort Graves et al. (2014).

####  3.3.4 Differentiable Neural Computer

In this subsection, we briefly review DNC Graves et al. (2016), a powerful
extension of the NTM. A DNC consists of a controller, which accesses and
modifies an external memory module using a number of read heads and one write
head. Given some input $x_{t}$, and a set of $R$ read values from memory
$r_{t-1}=\left[r_{t-1}^{1},...,r_{t-1}^{k},...,r_{t-1}^{R}\right]$, the
controller produces the output $o_{t}$ and the interface which consists of
intermediate variables, as depicted in Fig. 3.4 (b). DNC also uses the
content-based attention in Eq. (3.25) to determine the content-based write-
weight $w_{t}^{cw}$ and read-weights $w_{t}^{cr,k}$. However, different from
NTM, DNC does not support location-based attention. Instead, DNC introduces
dynamic memory allocation and temporal memory linkage for computing the final
write-weight $w_{t}^{w}$ and read-weights $w_{t}^{r,k}$ separately.

Dynamic memory allocation & write weightings: DNC maintains a differentiable
free list tracking the usage $u_{t}\in\left[0,1\right]^{N}$ for each memory
location. Usage is increased after a write and optionally decreased after a
read, determined by the free gates $f_{t}^{k}$ as follows,

$u_{t}=\left(u_{t-1}+w_{t-1}^{w}-u_{t-1}\circ
w_{t-1}^{w}\right)\stackrel{{\scriptstyle[}}{{k}}=1]{R}{\prod}\left(1-f_{t}^{k}w_{t}^{r,k}\right)$
(3.33)

The usage is sorted and then the allocation write-weight is defined as

$a_{t}\left[\varPhi_{t}\left[j\right]\right]=\left(1-u_{t}\left[\varPhi_{t}\left[j\right]\right]\right)\stackrel{{\scriptstyle[}}{{i}}=1]{j-1}{\prod}u_{t}\left[\varPhi_{t}\left[i\right]\right]$
(3.34)

in which, $\varPhi_{t}$ contains elements from $u_{t}$ sorted by ascending
order from least to most used. Given the write gate $g_{t}^{w}$ and allocation
gate $g_{t}^{a}$, the final write-weight then can be computed by interpolating
between the content-based write-weight and the allocation write-weight,