$w_{t}^{w}=g_{t}^{w}\left[g_{t}^{a}a_{t}+\left(1-g_{t}^{a}\right)w_{t}^{cw}\right]$
(3.35)

Then, the memory is updated by the following rule

$M_{t}=M_{t-1}\circ\left(E-g_{t}^{w}w_{t}^{w}e_{t}^{\top}\right)+g_{t}^{w}w_{t}^{w}v_{t}^{\top}$
(3.36)

Temporal memory linkage & read weightings: DNC uses a temporal link matrix
$L_{t}\in\left[0,1\right]{}^{N\times N}$ to keep track of consecutively
modified memory locations, and $L_{t}\left[i,j\right]$ represents the degree
to which location $i$ was the location written to after location $j$. Each
time a memory location is modified, the link matrix is updated to remove old
links to and from that location, and add new links from the last-written
location. To compute the link matrix, DNC maintains a precedence weighting to
keep track of which locations were most recently written by using the
following equation

$p_{t}=\left(1-\stackrel{{\scriptstyle[}}{{i}}]{N}{\sum}w_{t}^{w}\left(i\right)\right)p_{t-1}+w_{t}^{w}$
(3.37)

Then $p_{t}$ is used to update the link matrix as follows,

$L_{t}\left(i,j\right)=\left(1-w_{t}^{w}\left(i\right)-w_{t}^{w}\left(j\right)\right)L_{t-1}\left(i,j\right)+w_{t}^{w}\left(i\right)p_{t-1}\left(j\right)$
(3.38)

Given the link matrix, the final read-weight is given as follow,

$w_{t}^{r,k}=\pi_{t}^{k}\left(1\right)L_{t}^{\top}w_{t-1}^{r,k}+\pi_{t}^{k}\left(2\right)w_{t}^{cr,k}+\pi_{t}^{k}\left(3\right)L_{t}w_{t-1}^{r,k}$
(3.39)

The read mode weight $\pi_{t}^{k}$ is used to balance between the content-
based read-weight and the forward $L_{t}w_{t-1}^{r,k}$ and backward
$L_{t}^{\top}w_{t-1}^{r,k}$ of the previous read. Then, the $k$-th read value
$r_{t}^{k}$ is retrieved using the final read-weight vector

$r_{t}^{k}=\stackrel{{\scriptstyle[}}{{i}}]{N}{\sum}w_{t}^{r,k}(i)M_{t}(i)$
(3.40)

The performance of DNC is better than that of NTM, LSTM and other variants of
memory networks. It achieves state-of-the-art results under various
experimental settings such as copy/recall, question-answering and graph
reasoning Graves et al. (2016).

####  3.3.5 Memory-augmented Encoder-Decoder Architecture

A memory-augmented encoder-decoder (MAED) consists of two neural controllers
linked via external memory. This is a natural extension to read-write MANNs to
handle sequence-to-sequence problems, which has been investigated in Sec. 3.2.
MAED has recently demonstrated promising results in machine translation Britz
et al. (2017); Wang et al. (2016), OCR Nguyen et al. (2019) and healthcare Le
et al. (2018c, b); Prakash et al. (2017). In this thesis, MAED is the basic
framework on which some of our proposed architectures are built upon. Here, we
briefly analyse the operations of MAED. More details can be found in Chapter
4.

As mentioned in Sec. 3.2.1, Seq2Seq only allows information transfer from the
encoder to the decoder via “thought vector”. Attention mechanism creates
shortcut connections via directly attending to other timesteps (see Sec. 3.2.2
and 3.2.3). Unlike these approaches, MAED uses an external memory as a
reservoir containing past information to which the controllers attend. That
is, instead of directly attending to other timesteps, the controllers (both
encoder and decoder) attend to the memory to store and retrieve relevant
information The information then participates in other decision-making
processes such as output predictions, feature extractions and memory
operations. If the number of memory slots is finite, the method keeps the
computation resource linear to the length of the sequence, which is feasible
for life-long learning. Furthermore, selectively attending to a fixed number
of memory slots requires the model to learn to compress the information to the
external memory. On one hand, it may make the learning harder since the
controllers must learn to write timestep information to the memory
efficiently. On the other hand, attending to all timesteps is biologically
implausible and information compression is a powerful skill that mimics the
capacity of memory in the brain. Hence, this thesis has chosen MAED as the key
framework to study and develop several memory and attention techniques for
neural networks (Chapter 4 and 5).

###  3.4 Closing Remarks

We have reviewed MANNs, a family of recurrent neural networks with external
memory, which is useful for a wide range of sequential learning tasks. Armed
with operations such as gating and attention mechanisms, MANNs are able to
control and update external vector or matrix memory module. The power of MANNs
has been verified in learning long sequential data, in which their
performances are superior to that of vanilla RNNs.

We hypothesise that MANNs are also effective in open challenges in multi-
process/multi-view data, data with uncertainty, ultra-long sequences and
problems required universal computation. We address these challenges in
Chapters 4, 5, 6 and 7, respectively. A recurring theme across all of our
proposed MANNs is found on slot-based memory architecture.

##  Chapter 4 Memory Models for Multiple Processes

###  4.1 Introduction

####  4.1.1 Multi-Process Learning

Traditional sequential learning focuses on modeling single processes, in which
the sequence of outputs shares the same domain with the input sequence. We can
extend the problem to broader scenarios where input and output sequences are
from different processes (sequence to sequence) or there are multiple
sequences acting as inputs and outputs (multi-view sequential mapping). For
example, in healthcare setting, there are at least three processes that are
executed: the disease progression, the treatment protocols, and the recording
rules.

Let us start with a generic formulation of the multi-process learning. Let
$S^{i_{1}}$, …,$S^{i_{M}}$ and $S^{o_{1}}$, …,$S^{o_{N}}$ denote $M$ input and
$N$ output view spaces, respectively. Each sample of the multi-process problem
$\left(\left\\{X^{i_{k}}\right\\}_{k=1}^{M},\left\\{Y^{o_{k}}\right\\}_{k=1}^{N}\right)$
consists of $M$ input views:
$X^{i_{1}}=\left\\{x_{1}^{i_{1}},...,x_{t_{1}}^{i_{1}},...,x_{L^{i_{1}}}^{i_{1}}\right\\}$,
…,
$X^{i_{M}}=\left\\{x_{1}^{i_{M}},...,x_{t_{M}}^{i_{M}},...,x_{L^{i_{M}}}^{i_{M}}\right\\}$
and $N$ output views
$Y^{o_{1}}=\left\\{y_{1}^{o_{1}},...,y_{t_{1}}^{o_{1}},...,y_{L^{o_{1}}}^{o_{1}}\right\\},...,Y^{o_{N}}=\left\\{y_{1}^{o_{N}},...,y_{t_{N}}^{o_{N}},...,y_{L^{o_{N}}}^{o_{N}}\right\\}$.
Each view has a particular length ($L^{i_{1}}$, …, $L^{i_{M}}$ and
$L^{o_{1}}$, …, $L^{o_{N}}$) and can be treated as a set/sequence of events
that belongs to different spaces ($x_{t_{1}}^{i_{1}}\in S^{i_{1}}$, …,
$x_{t_{M}}^{i_{M}}\in S^{i_{M}}$, $y_{t_{1}}^{o_{1}}\in S^{o_{1}}$, …,
$y_{t_{N}}^{o_{N}}\in S^{o_{N}}$). Each event then can be represented by an
one-hot vector $v\in\left[0,1\right]^{\left\|C\right\|}$, where $C$ can be
$S^{i_{1}}$, …, $S^{i_{M}}$ or $S^{o_{1}}$, …, $S^{o_{N}}$. In single process,
$M=N=1$ and $S^{i_{1}}=S^{o_{1}}$. Practical problems belonging to this
setting can be solved efficiently using RNNs or LSTM as in language modeling
Mikolov et al. (2010), speech and optical character recognition Graves et al.
(2013); Graves (2013); Graves and Schmidhuber (2005). We focus more on other
complicated cases, which are dual processes (sequence to sequence) and dual-
view mapping, where $M=N=1$, $S^{i_{1}}\neq S^{o_{1}}$ and $M=2,N=1$,
$S^{i_{1}}\neq S^{i_{2}}\neq S^{o_{1}}$, respectively. These cases represent
two classes of problems that traditional RNNs may struggle to deal with. Thus,
we aim to solve them using MAED (Sec. 3.3.5) by proposing: (i) separate
controls for two separate sub-processes (encoding, decoding) and (ii) multiple
memories for multiple parallel, asynchronous processes. To account for these
settings, we need more powerful MAEDs to handle the complexity of long-term
dependencies and view interactions, which will be presented in the next
sections using healthcare as a practical domain.

####  4.1.2 Real-World Motivation

A main motivation for our work in this chapter is modeling healthcare
processes. In healthcare, a hospital visit is documented as one admission
record consisting of diagnosis and treatment codes for the admission. The
collection of these records are electronic medical records (EMRs) of a
patient. Recently, using EMRs as the data for scientists to analyse and make
treatment predictions has become the key for improving healthcare Williams
(2008). A typical EMR contains information about a sequence of admissions for
a patient and a wide range of information can be stored in each admission,
such as detailed records of symptoms, data from monitoring devices,
clinicians’ observations. Diagnoses, procedures or drug prescriptions are the
most important information stored in EMRs and are typically coded in
standardised formats, each of which represents a medical process in EMR data.

In particular, diagnoses are coded using WHO’s ICD (International
Classification of Diseases) coding schemes. For example, in the ICD10 scheme,
E10 encodes Type 1 diabetes mellitus, E11 encodes Type 2 diabetes mellitus and
F32 indicates depressive episode. The treatment can be procedure or drug. The
procedures are typically coded in CPT (Current Procedural Terminology) or ICHI
(International Classification of Health Interventions) schemes. The drugs are
often coded in ATC (Anatomical Therapeutic Chemical) or NDC (National Drug
Code).

It is important to note that there are order dependencies amongst medical
processes such as the diagnosis codes as well as procedure or drug codes. For
example, diagnosis codes are often sequenced under some strict rules such as:
(i) condition codes must be sequenced first, followed by the manifestation
codes, (ii) primary diagnosis that describe the nature of the sequela must be
coded before the secondary diagnosis that describes the original injury, (iii)
single conditions that require more than one code have clear instructions that
indicate which must be coded first. Similarly, procedure or drug codes often
follow specific order, often corresponding to the order of diagnosis codes or
the order of prescriptions. Moreover, the dependency in EMR clinical codes can
be very long-term. Due to the fact that EMR data is temporally sequenced by
patient medical visits, clinical codes at current admission may be related to
other codes appearing in previous admissions. Since it is normal for patients
to periodically visit hospital for regular health check, the number of
admissions for some person should be very large and thus the dependency
amongst clinical codes should be very long. Another characteristic of EMR data
is its rarity. Although the number of EMR records are increasing day by day,
it cannot cover many rarely-seen symptoms and treatments which appear sparsely
throughout the history of EMR documentation. More seriously, rare diseases are
deadly and rare treatments are expensive, so it is compulsory to make use of
these rare information in order to make significant predictions.

Unfortunately, it is not easy for prediction models to capture the long-term
dependencies and rarity of EMR data. Recent researches dealing with medical
prediction have largely focused on modeling the admission’s diagnosis and
treatments as two set of codes and only capture sequential dependencies from
one admission to another Nguyen et al. (2017); Pham et al. (2017). Also, most
of these methods avoid using rare data by only keeping codes that appear
frequently. This approach exposes three limitations. First, using set
representation ignores the internal internal sequential dependencies and thus
fail to discover sequential relations amongst codes from the same admission.
Second, refusing to use rare clinical events makes the contribution less
significant because in healthcare, rare events are the more important ones.
Third, outputs of this approach are often set of codes, which again detaches
from realistic need where treatments and diagnoses have to follow strict
orders. These challenges motivate new approaches that treat EMR history as
sequences of correlated processes.

##### Sequence to sequence mapping

Treatment recommendation can be cast as sequence to sequence problem. Once
diagnoses are confirmed, we want to predict the output sequence (treatment
codes of the current visit) given the input sequence (all diagnoses followed
by treatments from the first visit to the previous visit plus the diagnoses of
the current visit). More formally, we denote all the unique medical codes
(diagnosis, procedures and drugs) from the EMR data as
$c_{1},c_{2},..c_{\left|C\right|}\in C$, where $\left|C\right|$ is the number
of unique medical codes. A patient’s $n$-th admission’s input is represented
by a sequence of codes:

$\left[c_{d_{1}}^{1},c_{d_{2}}^{1},...,\textrm{$\permil$},c_{p_{1}}^{1},c_{p_{2}}^{1}...,\diameter\allowbreak,...,c_{d_{1}}^{n-1},c_{d_{2}}^{n-1},...,\textrm{$\permil$},c_{p_{1},}^{n-1},c_{p_{2}}^{n-1},....,\diameter\allowbreak,c_{d_{1}}^{n},c_{d_{2}}^{n},...,\permil\right]$
(4.1)

Here, $c_{d_{j}}^{k}$ and $c_{p_{j}}^{k}$ are the $j$-th diagnosis and
treatment code of the $k$-th admission, respectively. $\permil$ , $\diameter$
are special characters that informs the model about the change from diagnosis
to treatment codes and the end of an admission, respectively. This reflects
the natural structure of a medical history, which is a sequence of clinical
visits, each of which typically includes a subsequence of diagnoses, and a
subset of treatments. A diagnosis subsequence usually starts with the primary
condition followed by secondary conditions. In a subset of treatments, the
order is not strictly enforced, but it may reflect the coding practice. The
output of the patient’s $n$-th admission is :
$\left[c_{p_{1}}^{n},c_{p_{2}}^{n},...,c_{p_{L_{out}}}^{n},\diameter\right]$,
in which $L_{out}$ is the length of the treatment sequence we want to predict
and $\diameter$ is used to inform the model to stop predicting. Finally, each
code is represented by one-hot vector
$v_{c}\in\left[0,1\right]^{\left\|C\right\|}$, where
$v_{c}=\left[0,...,0,1,0..,0\right]$ ($v_{c}[i]=1$ if and only if $v_{c}$
represents $c_{i}$). Unlike set encoding of each admission, representing the
data in this way preserves the admission’s internal order information allowing
sequence-based methods to demonstrate their power of capturing sequential
events.

In Sec. 4.3, we present a novel treatment recommendation model using memory
network to remember long-term dependencies and rare events from EMR data. This
model is built upon Differential Neural Computer (DNC) Graves et al. (2016), a
fully differentiable implementation of memory-augmented neural network (MANN)
(see Sec. 3.3.4). In question-answer bAbI task Weston et al. (2015), DNC
treats the story, question as sequences of words and perform well on the task
of predicting sequence of answers, which suggests the power of DNC in handling
sequence input and solving sequence prediction task. Despite of its successes,
DNC have never been applied to realistic domain such as healthcare, especially
in clinical treatment sequence prediction. This realisation motivates us to
design a DNC-based architecture that fits and works well with healthcare
domain. In our design, we make use of two controllers instead of one to handle
dual processes: diagnoses and treatments. Each controller will employ
different remembering strategies for each process and thus increase the
robustness of prediction and the speed of learning. Besides, we apply a write-
protected policy for our controller to direct the model toward reasonable
remember strategies.

##### Two-view sequential learning

For two-view problems, the generic notations simplify to $S^{i_{1}}$,
$S^{i_{2}}$ denoting input view spaces and $S$ the output view space. Each
sample of the two-view problem $\left(X^{i_{1}},X^{i_{2}},Y\right)$ consists
of two input views:
$X^{i_{1}}=\left\\{x_{1}^{i_{1}},...,x_{t_{1}}^{i_{1}},...,x_{L^{i_{i}}}^{i_{1}}\right\\}$,
$X^{i_{2}}=\left\\{x_{1}^{i_{2}},...,x_{t_{2}}^{i_{2}},...,x_{L^{i_{2}}}^{i_{2}}\right\\}$
and one output view $Y=\left\\{y_{1},...,y_{t},...,y_{L}\right\\}$. Each view
has a particular length ($L^{i_{1}}$, $L^{i_{2}}$ or $L$), each of which is a
set/sequence of events that belongs to different spaces ($x_{t_{1}}^{i_{1}}\in
S^{i_{1}}$, $x_{t_{2}}^{i_{2}}\in S^{i_{2}}$, $y_{t}\in S$). It should be
noted that this formulation can be applied to many situations including video-
audio understanding, image-captioning and other two-channel time-series
signals. Here we focus effort on solving the two-view problems in healthcare.

For example, in drug prescription, doctors prescribe drugs after considering
diagnoses and procedures administered to patients. In modeling disease
progression, doctor may refer to patient’s history of admissions to help
diagnoses the current diseases or to predict the future disease occurrences of
the patient. There are clinical recording rules applying to EMR codes such
that diagnoses are “ordered by priority” or procedures follow the order that
“the procedures were performed”111https://mimic.physionet.org/mimictables/.
Besides, although medical codes from different views are highly correlated,
they are not aligned. For instances, some diagnoses may correspond to one
procedure or one diagnosis may result in multiple medicines. Hence, these
problems can be treated as asynchronous two-view sequential learning.

In the drug prescription context, $S^{i_{1}}$ and $S^{i_{2}}$ represent the
diagnosis and procedure spaces, respectively and $S$ corresponds to the
medicine space. The drug prescription objective is to select an optimal subset
of medications from $S$ based on diagnosis and procedure codes. Similarly, we
can formulate the disease progression problem as two input sequences
(diagnoses and interventions) and one output set (next diagnoses). Although
our architecture can model sequential output, the choice of representing
output as set is to follow a common practice in healthcare where the order of
medical suggestions is specified. Because a patient may have multiple
admission records for different hospital visits, a patient record can be
represented as
$\left\\{\left(X_{a}^{i_{1}},X_{a}^{i_{2}},Y_{a}\right)\right\\}_{a=1}^{A}$,
where $A$ is the number of admissions this patient commits. In order to
predict $Y_{a}$, we may need to exploit not only
$\left(X_{a}^{i_{1}},X_{a}^{i_{2}}\right)$ but also
$\left\\{\left(X_{pa}^{i_{1}},X_{pa}^{i_{2}}\right)\right\\}_{pa=1}^{a-1}$.
More details on how our work makes use of previous admissions and handles
long-term dependencies will be given in Sec. 4.4.3.

In Sec. 4.4, we propose a novel memory augmented neural network model solving
the problem of asynchronous interactions and long-term dependencies at the
same time. Our model makes use of three neural controllers and two external
memories constituting a dual memory neural computer. In our architecture, each
input view is assigned to a controller and a memory to model the intra-view
interactions in that particular view. At each time step, the controller reads
an input event, updates the memory, and generates an output based on its
current hidden state and read vectors from the memory. Corresponding to the
two types of inter-view interactions, there are two modes in our architecture:
late-fusion and early-fusion memories. In the late-fusion mode, the memory
space for each view is separated and independent, that is, there is no
information exchange between the two memories during the encoding process. The
memories’ read values are only synthesised to generate inter-view knowledge in
the decoding phase. Contrast to the late-fusion mode, the memory addressing
space in the early-fusion mode is shared amongst views. That is, the encoder
from one view can access and modify the contents of the other view’s memory.
This design ensures the information is shared across views via memories
accessing. In order to facilitate this asynchronous sharing, we design novel
cache components that temporarily hold the write values of every timestep.
This enables related information at different time steps to be written to the
memories together. Finally, we apply memory write-protected mechanism in the
decoding process to make the inference of our model more efficient.

###  4.2 Background

####  4.2.1 Multi-View Learning

In multi-view learning, data can be naturally partitioned into channels
presenting different views of the same data. Multi-view sequential learning is
a sub-class of multi-view learning where each view data is in the form of
sequential events, which can be synchronous or asynchronous. In the
synchronous setting, all views share the same time step and view length. Some
problems of this type include video consisting of visual and audio streams;
and text as a joint sequence of words and part-of-speech tags. Synchronous
multi-view sequential learning is an active area Rajagopalan et al. (2016);
Zadeh et al. (2017, 2018). These works make assumptions on the time step
alignment and thus they are constrained by the scope of synchronous multi-view
problems.

In this work, we relax these assumptions and focus more on asynchronous
settings, that is, there is no alignment amongst views and the sequence
lengths vary across views. These occur when the data is collected from
channels having different time scales or we cannot infer the precise time
information when extracting data. In healthcare, for instance, 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. Although an admission is time-stamped, medical events from each view
inside the admission are not synchronous and different in length.

Asynchronous multi-view data often demonstrates three types of view
interactions. The first type is intra-view interactions, those involving only
one view, representing the internal dynamics. For example, each EMR view has
specific rules for coding its events, forming distinctive correlations amongst
medical events inside a particular view. The second type is late inter-view
interactions, those that span from input views to output, representing the
mapping function between the inputs and the outputs. We call it “late” because
the interaction across input views is considered only in the inference
process. The third type is early inter-view interactions, those that account
for relations covering multiple input views and happening before the inference
process. For example, in drug prescription, the diagnosis view is the cause of
the medical procedure view, both of which affect the output which are
medicines prescribed for patient. The interactions in sequential views not
only span across views but also extend throughout the length of the sequences.
One example involves patients whose diseases in current admission are related
to other diseases or treatments from distant admissions in the past. The
complexity of view interactions, together with the unalignment and long-term
dependencies amongst views poses a great challenge in asynchronous multi-view
sequential problems.

####  4.2.2 Existing Approaches

Deep learning for healthcare: The recent success of deep learning has drawn
board interest in building AI systems to improve healthcare. Several studies
have used deep learning methods to better categorise diseases and patients:
denoising autoencoders, an unsupervised approach, can be used to cluster
breast cancer patients Tan et al. (2014), and convolutional neural networks
(CNNs) can help count mitotic divisions, a feature that is highly correlated
with disease outcome in histological images Cireşan et al. (2013). Another
branch of deep learning in healthcare is to solve biological problems such as
using deep RNN to predict gene targets of microRNAs Zurada (1994). Despite
these advances, a number of challenges exist in this area of research, most
notably how to make use of other disparate types of data such as electronic
medical records (EMRs). Recently, more efforts have been made to utilise EMR
data in disease prediction Pham et al. (2017), unplanned admission and risk
prediction Nguyen et al. (2017) problems. Other works apply LSTMs, both with
and without attention to clinical time series for heart failure prediction
Choi et al. (2016) or diagnoses prediction Lipton et al. (2016). Treatment
recommendation is also an active research field with recent deep learning
works that model EMR codes as sequence such as using sequence of billing codes
for medicine suggestions Bajor and Lasko (2017) or using set of diagnoses for
medicine sequence prediction Zhang et al. (2017). Differing from these
approaches, our works focus on modeling both the admission data and the
treatment output as two sequences to capture order information from input
codes and ensure dependencies amongst output codes at the same time.

Multi-view learning in healthcare: Multi-view learning is a well-studied
problem, where methods often exploit either the consensus or the complementary
principle Xu et al. (2013). A straightforward approach is to concatenate all
multiple views into one single view making it suitable for conventional
machine learning algorithms, both for vector inputs González et al. (2015);
Zadeh et al. (2016) or sequential inputs Morency et al. (2011); Song et al.
(2012). Another approach is co-training Blum and Mitchell (1998); Nigam and
Ghani (2000), aiming to maximise the mutual agreement on views. Other
approaches either establish a latent subspace shared by multiple views
Quadrianto et al. (2009) or perform multiple kernel learning Rakotomamonjy et
al. (2007). These works are typically limited to non-sequential views.

More recently, deep learning is increasingly applied for multi-view problems,
especially with sequential data. For example, LSTM Hochreiter and Schmidhuber
(1997) is extended for multi-view problems Rajagopalan et al. (2016) or
multiple kernel learning is combined with convolution networks Poria et al.
(2015). More recent methods focus on building deep networks to extract
features from each view before applying different late-fusion techniques such
as tensor products Zadeh et al. (2017), contextual LSTM Poria et al. (2017)
and gated memory Zadeh et al. (2018). All of these deep learning methods are
designed only for synchronous sequential input views. Hence, the applications
of these methods mostly fall into tagging problems where the output is aligned
with the input views. As far as we know, the only work that can apply to
asynchronous inputs is in Chung et al., (2017), in which the authors construct
a dual LSTM for feature extraction and use attention for late-fusion Chung et
al. (2017). Without multiple memories for multi-view sequences, LSTM-based
models fail short in capturing long-term dependencies in the sequences. LSTM
encoder-decoder with attention can only support late-fusion modeling, which
may be insufficient for cases that require early-fusion. More importantly,
attentional LSTMs do not assume fixed size memory, which may be impractical
for ultra-long sequences, online and life-long learning.

In healthcare, there are only few works that make use of multi-view data. A
multi-view multi-task model is proposed to predict future chronic diseases
given multi-media and multi-model observations Nie et al. (2015). However,
this model is only designed for single-instance regression problems. DeepCare
Pham et al. (2017) solves the disease progression problem by combining
diagnosis and intervention views. It treats medical events in each admission
as a bag and uses pooling to compute the feature vectors for the two views in
an admission. The sequential property of events inside each admission is
ignored and there is no mechanism to model inter-view interactions at event
level. There are many other works using deep learning such as RETAIN Choi et
al. (2016), Dipole Ma et al. (2017b) and LEAP Zhang et al. (2017) that attack
different problems in healthcare. However, they are designed for single input
view.

MANNs for healthcare: Memory augmented neural networks (MANNs) have emerged as
a new promising research topic in deep learning. Memory Networks (MemNNs)
Weston et al. (2014) and Neural Turing Machines (NTMs) Graves et al. (2014)
are the two classes of MANNs that have been applied to many problems such as
meta learning Santoro et al. (2016) and question answering Sukhbaatar et al.
(2015). In healthcare, there is limited work applying MemNN-based models to
handle medical-related problems such as clinical textual QA Hasan et al.
(2016) or diagnosis inference Prakash et al. (2017). However, these works have
been using clinical documents as input, rather than just using medical codes
stored in EMRs. Our work, on the other hand, learns end-to-end from raw
medical codes in EMRs by leveraging Differentiable Neural Computer (DNC)
Graves et al. (2016), the latest improvement over the NTM. In practice, DNC
and other NTM variants have been used for various domains such as visual
question answering Ma et al. (2017a), and one-shot learning Santoro et al.
(2016), yet it is the first time DNC is adapted for healthcare tasks.

###  4.3 Dual Control Architecture

Figure 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.

We now present our first contribution–a deep neural architecture called Dual
Controller Write-Protected Memory Augmented Neural Network (DCw-MANN) (see
Fig. 4.1). Our DCw-MANN introduces two simple but crucial modifications to the
original DNC: (i) using two controllers to handle dual processes of encoding
and decoding, respectively; and (ii) applying a write-protected policy in the
decoding phase.

In the encoding phase, after going through embedding layer $W_{E}$, the input
sequence is fed to the first controller (encoder) $LSTM_{E}$. At each time
step, the controller reads from and writes to the memory information necessary
for the later decoding process. In the decoding phase, the states of the first
controller is passed to the second controller (decoder) $LSTM_{D}$. The use of
two controllers instead of one is important in our setting because it is
harder for a single controller to learn many strategies at the same time.
Using two controllers will make the learning easier and more focused. Also
different from the encoder, the decoder can make use of its previous
prediction (after embedding layer $W_{D}$) as the input together with the read
values from the memory. Another important feature of DCw-MANN is its write-
protected mechanism in the decoding phase. This has an advantage over the
writing strategy used in the original DNC since at decoding step, there is no
new input that is fed into the system. Of course, there remains dependencies
amongst codes in the output sequence. However, as long as the dependencies
amongst output codes are not too long, they can be well-captured by the cell
memory $c_{t}$ inside the decoder’s LSTM. Therefore, the decoder in our design
is prohibited from writing to the memory. To be specific, at time step $t+1$
we have the hidden state and cell memory of the controllers calculated as:

$h_{t+1},c_{t+1}=\begin{cases}LSTM_{E}\left(\left[W_{E}v_{d_{t}},r_{t}\right],h_{t},c_{t}\right);&t\leq
L_{in}\\\
LSTM_{D}\left(\left[W_{D}v_{p_{t}},r_{t}\right],h_{t},c_{t}\right);&t>L_{in}\end{cases}$
(4.2)

where $v_{d_{t}}$ is the one-hot vector representing the input sequence’s code
at time $t\leq L_{in}$ and $v_{p_{t}}$ is the predicted one-hot vector output
of the decoder at time $t>L_{in}$, defined as
$v_{p_{t}}=onehot\left(o_{t}\right)$, i.e.,:

$v_{p_{t}}\left[i\right]=\begin{cases}1&;i=\underset{1\leqslant
j\leqslant\left|C_{p}\right|}{argmax}(o_{t}\left[j\right])\\\
0&;\mathrm{otherwise}\end{cases}.$ (4.3)

We propose a new memory update rule to enable the write-protected mechanism:

$M_{t}=\begin{cases}M_{t-1}\circ\left(E-w_{t}^{w}e_{t}^{\top}\right)+w_{t}^{w}v_{t}^{\top};&t\leq
L_{in}\\\ M_{t-1};&t>L_{in}\end{cases}$ (4.4)

where $E$ is an $N\times D$ matrix of ones ,
$w_{t}^{w}\in\left[0,1\right]^{N}$ is the write-weight,
$e_{t}\in\left[0,1\right]^{D}$ is an erase vector, $v_{t}\in\mathbb{R}^{D}$ is
a write vector, $\circ$ is point-wise multiplication, and $L_{in}$ is the
length of input sequence.

###  4.4 Dual Memory Architecture

We now present the second contribution to solve the generic asynchronous two-
view sequential learning: a new deep memory augmented neural network called
Dual Memory Neural Computer (DMNC).

Figure 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.

####  4.4.1 Dual Memory Neural Computer

Our architecture consists of three neural controllers (two for encoding and
one for decoding), each of which interacts with two external memory modules
(see Fig. 4.2). Each of the two memory modules is similar to the external
memory module in DNC Graves et al. (2016), that is, it is equipped with
temporal linkage and dynamic allocation. The three controllers have their own
embedding matrices $W_{E}^{i_{1}}$, $W_{E}^{i_{2}}$, $W_{E}$ which project the
one-hot representation of events to a unified $d$-dimensional space. We use
$\mathbf{x}_{t_{1}}^{i_{1}}$, $\mathbf{x}_{t_{2}}^{i_{2}}$, $\mathbf{y}_{t}$
$\in\mathbb{R}^{d}$ to denote the embedding vector of $x_{t_{1}}^{i_{1}}$,
$x_{t_{2}}^{i_{2}}$, $y_{t}$, respectively, in which
$\mathbf{x}_{t_{1}}^{i_{1}}=W_{E}^{i_{1}}x_{t_{1}}^{i_{1}},\mathbf{x}_{t_{2}}^{i_{2}}=W_{E}^{i_{2}}x_{t_{2}}^{i_{2}},\mathbf{y}_{t}=W_{E}y_{t}$.
The embedding vectors $\mathbf{x}_{t_{1}}^{i_{1}}$,
$\mathbf{x}_{t_{2}}^{i_{2}}$ are always used as inputs of the encoders while
the embedding vector $\mathbf{y}_{t}$ will only be used as input of the
decoder if the output view is a sequence.

Each encoder will transform the embedding vectors to $h$-dimensional hidden
vectors. The current hidden vectors and outputs of the encoders are computed
as:

$h_{t_{1}}^{i_{1}},o_{t_{1}}^{i_{1}}=LSTM{}^{i_{1}}\left(\left[\mathbf{x}_{t_{1}}^{i_{1}},r_{t_{1}-1}^{i_{1}}\right],h_{t_{1}-1}^{i_{1}}\right),1\leq
t_{1}<L^{i_{1}}$ (4.5)

$h_{t_{2}}^{i_{2}},o_{t_{2}}^{i_{2}}=LSTM{}^{i_{2}}\left(\left[\mathbf{x}_{t_{2}}^{i_{2}},r_{t_{2}-1}^{i_{2}}\right],h_{t_{2}-1}^{i_{2}}\right),1\leq
t_{2}<L^{i_{2}}$ (4.6)

where $r_{t_{1}-1}^{i_{1}}$, $r_{t_{2}-1}^{i_{2}}$ are read vectors at
previous time step of each encoder and $L^{i_{1}},$$L^{i_{2}}$ are the lengths
of input views. It should be noted that the time step in each view may be
asynchronous and the lengths may be different. In our applications, since we
treat input views as sequences, we use $LSTM$ as the core of the
encoders222For inputs as sets, we can replace the $LSTM$s with $MLP$s. Using
separated encoder for each view naturally encourages the intra-view
interactions. To model inter-view interactions, we use two modes of memories,
late-fusion and early-fusion.

Late-fusion memories: In this mode, our architecture only models late inter-
view interactions. In particular, $r_{t_{1}}^{i_{1}}$ and $r_{t_{2}}^{i_{2}}$
are computed separately:

$r_{t_{1}}^{i_{1}}=\left[r_{t_{1}}^{i_{1,1}},...,r_{t_{1}}^{i_{1,R}}\right]=m{}_{read}^{e_{1}}\left(o_{t_{1}}^{i_{1}},M_{1}\right)$
(4.7)

$r_{t_{2}}^{i_{2}}=\left[r_{t_{2}}^{i_{2,1}},...,r_{t_{2}}^{i_{2,R}}\right]=m{}_{read}^{e_{2}}\left(o_{t_{2}}^{i_{2}},M_{2}\right)$
(4.8)

where $M_{1}$, $M_{2}$ are the two memory matrices containing view-specific
contents and $m_{read}^{e_{1}}$, $m_{read}^{e_{2}}$ are two read functions of
the encoders with separated set of parameters. Given the encoder output
vectors, the read functions produce the keys $k_{t_{1}}^{i_{1}}$,
$k_{t_{2}}^{i_{2}}$ in the manner of DNC. The keys are used to address the
corresponding memory and compute the read vectors using Eq.(3.40). This design
ensures the dynamics of computation in one view does not affect the other’s
and only in-view contents are stored in view-specific memory. This mode is
important because in certain situations, writing external contents to view-
specific memory will interfere the acquired knowledge and obstruct the
learning process. In Section 4.1, we will show a case study that fits with
this setting and the empirical results will demonstrate that the late-fusion
mode is necessary to achieve better performance.

Early-fusion memories: When there exists a strong correlation between the two
input views, requiring to model early inter-view interactions, we introduce
another mode of memories: early-fusion mode. In this mode, the two memories
share the same addressing space, that is, the encoder from one view can access
the memory content from another view and vice versa. Also, the read functions
$m_{read}^{e}$ share the same parameter set:

$r_{t_{1}}^{i_{1}}=\left[r_{t_{1}}^{i_{1,1}},...,r_{t_{1}}^{i_{1,R}}\right]=m{}_{read}^{e}\left(o_{t_{1}}^{i_{1}},\left[M_{1},M_{2}\right]\right)$
(4.9)

$r_{t_{2}}^{i_{2}}=\left[r_{t_{2}}^{i_{2,1}},...,r_{t_{2}}^{i_{2,R}}\right]=m{}_{read}^{e}\left(o_{t_{2}}^{i_{2}},\left[M_{1},M_{2}\right]\right)$
(4.10)

Since the read vectors for one encoder can come from either memories, the
encoder’s next hidden values are dependent on both views’ memory contents,
which enables possible early inter-view interactions in this mode.

1:Training set
$\\{\\{(X^{i_{1}}_{a},X^{i_{2}}_{a},Y_{a}\\}_{a=1}^{A}\\}_{n=1}^{N}$

2:Sample $B$ samples from training set

3:for each sample in $B$ do

4: Clear memory $M_{1}$, $M_{2}$

5: for $a=1,A$ do

6: $(X^{i_{1}},X^{i_{2}},Y)=(X^{i_{1}}_{a},X^{i_{2}}_{a},Y_{a})$

7: while $t_{1}<L^{i_{1}}$ or $t_{2}<L^{i_{2}}$ do

8: if $t_{1}<L^{i_{1}}$ then

9: Use Eq.(4.5) to calculate $h_{t_{1}}^{i_{1}},o_{t_{1}}^{i_{1}}$

10: Use Eq.(3.36) or Eq.(4.13) to update $M_{1}$

11: Use Eq.(4.7) or Eq.(4.9) to read $M_{1}$

12: $t_{1}=t_{1}+1$

13: end if

14: if $t_{2}<L^{i_{2}}$ then

15: Use Eq.(4.6) to calculate $h_{t_{2}}^{i_{2}},o_{t_{2}}^{i_{2}}$

16: Use Eq.(3.36) or Eq.(4.13) to update $M_{2}$

17: Use Eq.(4.8) or Eq.(4.10) to read $M_{2}$

18: $t_{2}=t_{2}+1$

19: end if

20: end while

21: Use Eq.(4.14) and Eq.(4.15) to read $M_{1}$,$M_{2}$

22: Use Eq.(4.18) to calculate $\widehat{y}$

23: Update parameter $\theta$ using
$\nabla_{\theta}Loss_{set}\left(Y,\widehat{y}\right)$

24: end for

25:end for

Algorithm 1 Training algorithm for healthcare data (set output)

Memories modification with cache components: In both modes, the two memories
are updated every timestep by the two encoders. While in the late-fusion mode,
the writings to two memories are independent and can be executed in parallel
using Eq.(3.36), in the early-fusion mode, the writings must be executed in an
alternating manner. In particular, the two encoders take turn writing to
memories, allowing the exchange of information at every timestep. Doing this
way is optimal if the two views are synchronous and equal in lengths. To make
it work with variable length input views, we introduce a new component to our
architecture: a cache memory that lies between the controller and the external
memory. Different from the original DNC which writes directly the event’s
value to the external memory, in the early-fusion mode of our architecture,
each controller integrates write values inside its own cache memory $c_{t}$
until an appropriate moment before committing them to the external memory. We
introduce $g_{t}^{c}$ as a learnable cache gate to control the degree of
integration between current write value and the previous cache’s content as
follows:

$\displaystyle g_{t}^{c}$ $\displaystyle=$ $\displaystyle
f^{c}\left(o_{t}^{i}\right)$ (4.11) $\displaystyle c_{t}$ $\displaystyle=$
$\displaystyle g_{t}^{c}\circ c_{t-1}+\left(1-g_{t}^{c}\right)\circ v{}_{t}$
(4.12)

In these equations, $g_{t}^{c}$ is the cache gate, $o_{t}^{i}$ is the encoder
output, $f^{c}$ is a learnable function333In this section, all $f$ functions
are implemented as single-layer feed-forward neural networks, $c_{t}$ is the
cache content and $v_{t}$ is the write value. Then, the cache will be written
to the memory using the following formula:

$M_{t}=M_{t-1}\circ\left(E-g_{t}^{w}w_{t}^{w}e_{t}^{\top}\right)+g_{t}^{w}w_{t}^{w}c_{t}^{\top}$
(4.13)

We propose this new writing mechanism for early-fusion mode to enable one
encoder to wait for another while processing input events (in this context,
waiting means the encoder stops writing to memory). In the original DNC, if
the write gate $g_{t}^{w}$ is close to zero, the encoder does not write to
memory and the write value at current time step will be lost. However, in our
design, even when there is no writing, the write value somehow can be kept in
the cache if $g_{t}^{c}<1$. The cache in a view may choose to hold an event’s
write value instead of writing it immediately at the read time step. Thus, the
information of the event is compressed in the cache until appropriate
occasion, which may be after the appearance of another event from the other
view. This mechanism enables two related asynchronous events to simultaneously
involve in building up the memories.

Write-protected memories: In our architecture, during the inference process,
the decoder stops writing to memories. We add this feature to our design
because the decoder does not receive any new input when producing output.
Writing to memories in this phase may deteriorate the memory contents,
hampering the efficiency of the model.

####  4.4.2 Inference in DMNC

In this section, we give more details on the operation of the decoder. Because
the decoder works differently for different output types (set or sequence), we
will present two versions of decoder implementation.

Output as sequence: In this setting, the decoder ingests the encoders’ final
states as its initial hidden state
$h_{0}=\left[h_{L^{i_{1}}}^{i_{1}},h_{L^{i_{2}}}^{i_{2}}\right]$ . The
decoder’s hidden and output vectors are given as:
$h_{t},\left[o_{t}^{1},o_{t}^{2}\right]=LSTM^{d}\left(\left[\mathbf{y}_{t-1}^{*},r_{t-1}^{i_{1}},r_{t-1}^{i_{2}}\right],h_{t-1}\right)$.
Here, $\mathbf{y}_{t-1}^{*}$ is the embedding of the previous prediction
$y_{t-1}^{*}$. The decoder combines the read vectors from both memories to
produce a probability distribution over the output:

$r_{t}^{i_{1}}=\left[r_{t}^{i_{1,1}},...,r_{t}^{i_{1,R}}\right]=m_{read}^{d}\left(o_{t}^{1},M_{1}\right)$
(4.14)

$r_{t}^{i_{2}}=\left[r_{t}^{i_{2,1}},...,r_{t}^{i_{2,R}}\right]=m_{read}^{d}\left(o_{t}^{2},M_{2}\right)$
(4.15)

$P\left(y_{t}|X^{i_{1}},X^{i_{2}}\right)=\pi\left(\left[o_{t}^{1},o_{t}^{2}\right]+f^{d}\left(\left[r_{t}^{i_{1}},r_{t}^{i_{2}}\right]\right)\right)$
(4.16)

where $r_{t}^{i_{1}},r_{t}^{i_{2}}$ are read vector from $M_{1},M_{2}$,
respectively, provided by the read function $m_{read}^{d}$, $f^{d}$ is a
learnable function and $\pi$ is softmax function. The current prediction is
$y_{t}^{*}=\underset{y\in
S}{argmax}\,P\left(y_{t}=y|X^{i_{1}},X^{i_{2}}\right)$ and the loss function
is the cross entropy:

$Loss_{seq}\left(Y,P\right)=-\stackrel{{\scriptstyle[}}{{t}}=1]{L}{\sum}\log
P\left(y_{t}|X^{i_{1}},X^{i_{2}}\right)$ (4.17)

Output as set: In this setting, the decoder uses $m_{read}^{d}$ to read from
the memories once to get the read vectors $r^{i_{1}},r^{i_{2}}$. The decoder
combines these vectors with the encoders’ final hidden values to produce the
output vector $\hat{y}\in\mathbb{R}^{\left|S\right|}$:

$\hat{y}=\sigma\left(f^{d}(W_{1}r^{i_{1}}+W_{2}r^{i_{2}}+W_{3}\left[h_{L^{i_{1}}}^{i_{1}},h_{L^{i_{2}}}^{i_{2}}\right])\right)$
(4.18)

Here, the combination is simply the linear weighted summation with parameter
matrices $W_{1}$, $W_{2}$, $W_{3}$. $f^{d}$ is a learnable function and
$\sigma$ is the sigmoid function. For set output, the loss function is multi-
label loss defined as:

$Loss_{set}\left(Y,\widehat{y}\right)=-\left(\underset{y_{l}\in
Y}{\sum}\log\widehat{y}_{l}+\underset{y_{l}\notin
Y}{\sum}\log\left(1-\widehat{y}_{l}\right)\right)$ (4.19)

For both settings, the decoder makes use of both memories’ contents and
encoders’ final hidden values to produce the output. While memory contents
represent the long-term knowledge, the encoder’s hidden values represent the
short-term information stored inside the controllers. Both are crucial to
model inter-view interactions and necessary for the decoder to predict the
correct outputs.

####  4.4.3 Persistent Memory for Multiple Admissions

As mentioned earlier in Sec. 4.1.2, one unique property of healthcare is the
long-term dependencies amongst admissions. Therefore, the output at the
current admission $Y_{a}$ is dependent on the current and all previous
admission’s inputs
$\left\\{\left(X_{pa}^{i_{1}},X_{pa}^{i_{1}}\right)\right\\}_{pa=1}^{a}$.
There are several ways to model this property. The simplest solution is to
concatenate the current admission with previous ones to make up single
sequence input for the model. This method causes data replication and
preprocessing overhead. Another solution is to use recurrent neural network to
model the dependencies. Some papers use GRU and LSTM where each time step is
fed with an admission. The admission is treated as a set of medical events and
represented by a feature vector Choi et al. (2015); Pham et al. (2017).

In our memory-augmented architecture, we can model this dependencies by using
the memories to store information from previous admissions. In the original
DNC, the memory content is flushed every time new data sample (i.e. new
admission) is fed – this certainly loses the information of admission history.
We modify this mechanism by keeping the memories persistent during a patient’s
admissions processing. That is, the content of memories is built up and
modified during the whole history of a patient’s admissions. The memories are
only cleared prior to reading a new patient’s record.

Persistent memories in our architecture play two important roles. First,
because the number of events across admissions are large while memory sizes
are moderate, the memory modules learn to compress efficiently the input
views, keeping only essential information. This makes memory look-ups in the
decoding process only limited to a fixed size of chosen knowledge. This is
more compact and focused than attention mechanisms, in which the decoder has
to attend to all events in the input. Second, each memory slot can store
information of any event in the input views, which enables skip-connection
reference in the decoding process, i.e., the decoder can jump to any input
event, even the one in the farthest admission, to look for relevant
information. The whole process of training our dual memory neural computer for
healthcare data is summarised in Algorithm 1.

###  4.5 Applications

In this section, we perform experiments both on real-world data and synthetic
tasks. The purpose of the synthetic task is to study the incremental impact of
dual control modifications we propose. Moreover, we demonstrate the
effectiveness of our proposed dual memory model DMNC. We use $DMNC_{l}$ and
$DMNC_{e}$ to denote the late-fusion and early-fusion mode of our model,
respectively. The data for real-world problems are real EMR data sets, some
are public accessible. We make the source code of DCw-MANN and DMNC publicly
available at https://github.com/thaihungle/MAED and
https://github.com/thaihungle/DMNC, respectively.

####  4.5.1 Synthetic Task: Odd-Even Sequence Prediction

Figure 4.3: Training Loss of Odd-Even Task

Figure 4.4: Training NLD of Odd-Even Task

In this task, the input is sequence of random odd numbers chosen without
replacement from the set $S_{o}=\left\\{1,3,5,...,49\right\\}$ and the output
is sequence of even numbers from the set $S_{e}=\left\\{2,4,6,..98\right\\}.$
The $n$-th number $y_{n}$ in the output sequence is computed as:

$y_{n}=\begin{cases}2x_{n}&n\leq\left\lfloor\frac{L}{2}\right\rfloor\\\
y_{n-1}+2&n>\left\lfloor\frac{L}{2}\right\rfloor\end{cases}$. $x_{n}$ is the
$n$-th number in the input sequence and $L$ is the length of both input and
output sequence chosen randomly from the range $\left[1,20\right]$. The
formula is designed to reflect healthcare situations where treatment options
depend both on diagnoses in the input sequence and other treatments in the
same output sequence. Here is an example of an input-output sequence pair with
$L=7$: $input\coloneqq\left[11,7,25,39,31,1,13\right]$ and
$output\coloneqq\left[22,14,50,52,54,56,58\right]$. We want to predict the
even numbers in the output sequence given odd numbers in the input sequence,
hence we name it odd-even prediction task. In this task, the model has to
“remember” the first half of the input sequence to compute the first half of
the output sequence, then it should switch from using input to using previous
output at the middle of the output sequence to predict the second half.

Evaluations: Our baselines are Seq2Seq Sutskever et al. (2014a), its attention
version Bahdanau et al. (2015) and the original DNC Graves et al. (2016).
Since we want to analyse the impact of new modifications, in this task, we
explore two other models: DNC with write-protected mechanism in the decoding
phase and dual controller MANN without write-protected mechanism (DC-MANN). We
use the Levenshtein distance (edit distance) to measure the model’s
performance. To account for variable sequence lengths, we normalise this
distance over the length of the longer sequence (between 2 sequences). The
predicted sequence is good if its Normalised Levenshtein Distance (NLD) to the
target sequence is small.

Implementation details: For all experiments, deep learning models are
implemented in Tensorflow 1.3.0. Optimiser is Adam Kingma and Ba (2014) with
learning rate of 0.001 and other default parameters. The hidden dimensions for
LSTM and the embedding sizes for all models are set to 256 and 64,
respectively. Memory’s parameters including number of memory slots and the
size of each slot are set to 128 and 128 , respectively.

Results: After training with 4000 input-output pair of sequences, the models
will be tested for the next 1000 pairs. The learning curves of the models are
plotted in Figs. 4.4 and 4.4. The average NLD of the predictions is summarised
in Table 4.5. As is clearly shown, the proposed model outperforms other
methods. Seq2Seq-based methods fail to capture the data pattern and
underperform other methods. The introduction of two controllers helps boost
the performance of DNC significantly. Additional DNC-variant with write-
protected also performs better than the original one, which suggests the
benefit of decoding without writing.

Model | NLD
---|---
Seq2Seq | 0.679
Seq2Seq with attention | 0.637
DNC | 0.267
DNC (write-protected) | 0.250
DC-MANN | 0.161
DCw-MANN | 0.082
Table 4.1: Test Results on Odd-Even Task (lower is better)

Figure 4.5: Read Modes of MANNs on Odd-Even Task

Fig. 4.5 plots read mode weights for three reading strategies employed in
encoding and decoding phases. We can observe the differences in the way the
models prefer reading strategies. The biggest failure of DNC is to keep using
backward read in the decoding process. This is redundant because in this
problem, it is the forward of the previous read location (if the memory
location that corresponds to $x_{n-1}$ is the previous read, then its forward
is the memory location that corresponds to $x_{n}$) that defines the current
output ($y_{n}$). On the other hand, dual controllers with write-protected
mechanism seems help the model avoid bad strategies and focus more on learning
reasonable strategies. For example, using dual controllers tends to lessen the
usage of content-based read in the encoding phase. This strategy is reasonable
in this example since the input at each time step is not repeated. Write-
protected policy helps balance the forward and content-based read in the
decoding phase, which may reflect the output pattern – half-dependent on the
input and half-dependent on the previous output.

####  4.5.2 Treatment Recommendation Tasks

The dataset used for this task is MIMIC-III Johnson et al. (2016), which is a
publicly available dataset consisting of more than 58k EMR admissions from
more than 46k patients. An admission history in this dataset can contain
hundreds of medical codes, which raises a great challenge in handling long-
term dependencies. In MIMIC-III, there are both procedure and drug codes for
the treatment process so we consider two separate treatment recommendation
tasks: procedure prediction and drug prescription. In practice, if we use all
the drug codes in an EMR record, the drug sequence can be very long since,
each day in hospital, the doctor can prescribe several types of drugs for the
patient. Hence, we only pick the first drug used in a day during the admission
as the representative drug for that day. We also follow the previous practice
that only focuses on patients who have more than one visit Ma et al. (2017b);
Nguyen et al. (2017); Pham et al. (2017). The statistics of the two sub-
datasets is detailed in Table 4.2.

MIMIC-III Dataset (# of visit >1) | Procedure as output | Drug as output
---|---|---
# of patients | 6,314 | 5,620
# of admissions | 16,317 | 14,656
# of unique diagnosis codes | 4,669 | 4,563
# of unique treatment codes | 1,439 | 2,446
Average # of diagnosis sequence length | 13.3 | 13.8
Max # of diagnosis sequence length | 39 | 39
Average # of treatment sequence length | 4.7 | 11.4
Max # of treatment sequence length | 40 | 186
Average # of visits per patient | 2.5 | 2.6
Max # of visits per patient | 29 | 29
Table 4.2: Statistics of MIMIC-III sub-datasets

Evaluations: For comprehensiveness, beside direct competitors, we also compare
our methods with classical for healthcare predictions, which are Logistic
Regression and Random Forests. Because traditional methods are not designed
for sequence predictions, we simply pick the top outputs (ignoring ordering
information). In treatment recommendation tasks, we use precision, which is
defined as the number of correct predicted treatment codes (ignoring the
order) divided by the number of predict treatment codes. More formally, let
$S_{p}^{n}$ be the set of ground truth treatments for the $n$-th admission,
$S_{q}^{n}$ be the set of treatments that the model outputs. Then the
precision is:
$\frac{1}{N}\stackrel{{\scriptstyle[}}{{n}}=1]{N}{\sum}\frac{\left|S_{p}^{n}\cap
S_{q}^{n}\right|}{\left|S_{q}^{n}\right|}$, where $N$ is total number of test
patients. To measure how closely the generated treatment compares against the
real treatment, we use Mean Jaccard Coefficient444The metrics actually are at
disadvantage to the proposed sequence-to-sequence model, but we use to make
them easy to compare against non-sequential methods., which is defined as the
size of the intersection divided by the size of the union of ground truth
treatment set and predicted treatment set:
$\frac{1}{N}\stackrel{{\scriptstyle[}}{{n}}=1]{N}{\sum}\frac{\left|S_{p}^{n}\cap
S_{q}^{n}\right|}{\left|S_{p}^{n}\cup S_{q}^{n}\right|}$.

Implementation details: We randomly divide the dataset into the training,
validation and testing set in a $0.7:0.1:0.2$ ratio, where the validation set
is used to tune model’s hyper-parameters. For the classical Random Forests and
Logistic Classifier, the input is bag-of-words. Also, we apply One-vs-Rest
strategy Rifkin and Klautau (2004) to enable these classifiers to handle
multi-label output and the hyper-parameters are found by grid-searching.

Results: Table 4.3 reports the prediction results on two tasks (procedure
prediction and drug prescription). The performance of the proposed DCw-MANN is
higher than that of baselines on the testing data for both tasks, validating
the use of dual controllers with write-protected mechanism. Without memory,
Seq2Seq methods seem unable to outperform classical methods, possibly because
the evaluations are set-based, not sequence-based. In the drug prescription
task, there is a huge drop in performance of the Seq2Seq-based approaches.

Model | Procedure Output | Drug Output
---|---|---
Precision | Jaccard | Precision | Jaccard
Logistic Regression | 0.256 | 0.185 | 0.412 | 0.311
Random Forest | 0.276 | 0.199 | 0.491 | 0.405
Seq2Seq | 0.263 | 0.196 | 0.220 | 0.138
Seq2Seq with attention | 0.272 | 0.204 | 0.224 | 0.142
DNC | 0.285 | 0.214 | 0.577 | 0.529
DCw-MANN | 0.292 | 0.221 | 0.598 | 0.556
Table 4.3: Results on MIMIC-III dataset for procedure prediction and drug
prescription (higher is better).

It should be noted that, in drug prescription, the drug codes are given day by
day; hence, the average length of output sequence are much longer than the
procedure’s one. This could be a very challenging task for Seq2Seq. Memory-
augmented models, on the other hand, have an external memory to store
information, so it can cope with long-term dependencies. Figs. 4.7 and Fig.
4.7 show that compared to DNC, DCw-MANN is the faster learner in drug
prescription task. This case study demonstrates that a MANN with dual
controller and write-protected mechanism can significantly improve the
performance of the sequence prediction task in healthcare.

Figure 4.6: Training Loss of Drug Prescription Task

Figure 4.7: Testing Loss of Drug Prescription Task

####  4.5.3 Synthetic Task: Sum of Two Sequences

Figure 4.8: Training loss of sum of two sequences task. The training error curves have similar patterns. Table 4.4: Sum of two sequences task test results. Max train sequence length is 10. Model | Accuracy (%)
---|---
$L_{max}=10$ | $L_{max}=15$ | $L_{max}=20$
LSTM | 35.17 | 24.12 | 18.64
DNC | 37.8 | 20.43 | 14.67
Dual LSTM | 52.41 | 42.57 | 30.47
WLAS | 55.98 | 43.29 | 32.49
$DMNC_{l}$ | 99.76 | 98.53 | 78.17
$DMNC_{e}$ | 98.84 | 93.00 | 69.93

We conduct this synthetic experiment to verify our model performance and
behavior. In this problem, the input views are two randomly generated sequence
of numbers: $\left\\{x_{1}^{1},...,x_{L}^{1}\right\\}$,
$\left\\{x_{1}^{2},...,x_{L}^{2}\right\\}$. Each sequence has $L$ integer
numbers. $L$ is randomly chosen from range $\left[1,L_{max}\right]$ and the
numbers are randomly chosen from range $\left[1,50\right]$. The output view is
also a sequence of integer numbers defined as
$\left\\{y_{i}=x_{i}^{1}+x_{L+1-i}^{2}\right\\}_{i=1}^{L}$, in which
$y_{i}\in\left[2,100\right]$. Note that this summation form is unknown to the
model. During training, only the outputs are given. Because the output’s
number is the sum of two numbers from the two input views, we name the task as
sum of two sequences. It should be noted that two input numbers in the
summation do not share the same time step; hence, the problem is asynchronous.
To learn and solve the task, a model has to read all the numbers from the two
input sequences and discover the correct pair that will be used to produce the
summation. Synchronous multi-view models certainly fail this task because they
assume the inputs to be aligned. In the training phase, we choose
$L_{max}=10$, training for 10,000 iterations with mini batch size $=50$. In
the testing phase, we evaluate on 2500 random samples with $L_{max}=10$,
$L_{max}=15$, $L_{max}=20$ to verify the generalisation of the models beyond
the range where they are trained.

Evaluations: the baselines for this synthetic task are chosen as follows:

  * •

View-concatenated sequential models: This concatenates events in input views
to form one long sequence. This technique transforms the two-view sequential
problem to normal sequence-to-sequence problem. We pick LSTM and DNC as two
representative methods for this approach.

  * •

Attention model WLAS Chung et al. (2017): This has a LSTM encoder per view,
and attention is used for decoding, similar to that in machine translation Cho
et al. (2014a); Bahdanau et al. (2015). The model is applied successfully in
the problem of video sentiment analysis. To make it suitable for our tasks, we
replace the encoders’ feature-extraction layers in the original WLAS by an
embedding layer. We choose this model as baseline since its architecture is
somehow similar to ours. The difference is that we make use of external
memories instead of attention mechanism.

  * •

Dual LSTM: This model is the WLAS model without attention, that is, only the
final states of encoders are passed into the decoder.

Implementations: For all models, embedding and hidden dimensions are 64 and
128, respectively. Word size for memory-based methods are 64\. Memory size for
the view-concatenated DNC and DMNC are 32 and 16, respectively. We double the
memory size for view-concatenated DNC to account for the fact that the length
of the input sequence is nearly double due to view concatenation. We use Adam
optimiser with default parameters and apply gradient clipping size $=10$ to
train all models. Since output is a sequence, we use the cross-entropy loss
function in Eq.(4.17). The evaluation metric used in this task is accuracy –
the number of correct predictions over the length of output sequence.

Results: The training loss curves of the models are plotted in Fig. 4.8. The
test average accuracy is summarised in Table 4.4. As clearly shown, overall
the proposed model outperforms other methods by a huge margin of about 45%.
Although dual LSTM and WLAS perform better than view-concatenated methods,
it’s too hard for non-memory methods to “remember” correctly pairs of inputs
for later output summation. View-concatenated DNC even with double memory size
still fails to learn the sum rule because storing two views’ data in a single
memory seems to mess up the information, making this model perform worst.
Between two versions of DMNC, late-fusion mode is better perhaps due to the
independence between two inputs’ number sequences. This is the occasion where
trying to model early cross-interactions damages the performance. The slight
drop in performance when testing with $L_{max}=15$ shows that our model really
learns the sum rule. When $L_{max}=20$, the input length is longer than the
memory size, so even when DMNCs can learn the sum rule, they cannot store all
input pairs for later summation. However, our methods still manage to perform
better than any other baseline.

####  4.5.4 Drug Prescription Task

Table 4.5: MIMIC-III data statistics. # of admissions | 42,586 | # of diag | 6,461
---|---|---|---
# of patients | 34,594 | # of proc | 1,881
Avg. view len | 53.86 | # of drug | 300
Table 4.6: Mimic-III drug prescription test results.

Model | AUC | F1 | P@1 | P@2 | P@5
---|---|---|---|---|---
|  Diagnosis Only
Binary Relevance | 82.6 | 69.1 | 79.9 | 77.1 | 70.3
Classifier Chains | 66.8 | 63.8 | 68.3 | 66.8 | 61.1
LSTM | 84.9 | 70.9 | 90.8 | 86.7 | 79.1
DNC | 85.4 | 71.4 | 90.0 | 86.7 | 79.8
|  Procedure Only
Binary Relevance | 81.8 | 69.4 | 82.6 | 80.1 | 73.6
Classifier Chains | 63.4 | 61.7 | 83.7 | 80.3 | 71.9
LSTM | 83.9 | 70.8 | 88.1 | 86.0 | 78.4
DNC | 83.2 | 70.4 | 88.4 | 85.8 | 78.7
|  Diagnosis and procedure
Binary Relevance | 84.1 | 70.3 | 81.0 | 78.2 | 72.3
Classifier Chains | 64.6 | 63.0 | 84.6 | 81.5 | 74.2
LSTM | 85.8 | 72.1 | 91.6 | 86.8 | 80.5
DNC | 86.4 | 72.4 | 90.9 | 87.4 | 80.6
Dual LSTM | 85.4 | 71.4 | 90.6 | 87.1 | 80.5
WLAS | 86.6 | 72.5 | 91.9 | 88.1 | 80.9
$DMNC_{l}$ | 87.4 | 73.2 | 92.4 | 88.9 | 82.6
$DMNC_{e}$ | 87.6 | 73.4 | 92.1 | 89.9 | 82.5

The data set used for this task is MIMIC-III, which is a publicly available
dataset consisting of more than 52k EMR admissions from more than 46k
patients. In this task, we keep all the diagnosis and procedure codes and only
preprocess the drug code since the raw drug view’s average length can reach
hundreds of codes in an admission, which is too long given the amount of data.
Therefore, only top 300 frequently used of total 4781 drug types are kept
(covering more than 70% of the raw data). The final statistics of the
preprocessed data is summarised in Table 4.5.

Evaluations: We compare our model with the following baselines:

  * •

Bag of words and traditional classifiers: In this approach, each input view is
considered as a set of events. The vector represents the view is the sum of
one-hot vectors representing the events. These view vectors are then
concatenated and passed into traditional classifiers: SVM, Logistic
Regression, Random Forest. To help traditional methods handle multi-label
output, we apply two popular techniques: Binary Relevance Luaces et al. (2012)
and Classifier Chains Read et al. (2011). We will only report the best model
for each of the two techniques, which are Logistic Regression and Random
Forest, respectively.

  * •

View-concatenated sequential models (LSTM, DNC), Dual LSTM and WLAS Chung et
al. (2017): similar to those described in the synthetic task.

  * •

Single-view models: To see the performance gains when making use of two input
views, we also report results when only using one view for Binary Relevance,
Classifier Chains, LSTM and DNC.

Implementations: We randomly divide the dataset into the training, validation
and testing set in a $2/3:1/6:1/6$ ratio. For traditional methods, we use
grid-searching over typical ranges of hyper-parameters to search for best
hyper-parameter values. Deep learning models’ best embedding and hidden
dimensions are 64 and 64, respectively. Optimal word and memory size for DMNC
are 64 and 16, respectively. The view-concatenated DNC shares the same setting
except the memory size is doubled to 32 memory slots. Since the output in this
task is a set, we use the multi-label loss function in Eq.(4.19) for deep
learning methods. We measure the relative quality of model performances by
using common multi-label metrics, Area Under the ROC Curve (AUC) and F1
scores, both of which are macro-averaged. Similar results can be achieved when
using micro-averaged so we did not report them here. In practice, precision at
$k$ (P@$k$) are often used to judge the treatment recommendation quality.
Therefore, we also include them ($k=1,2,5$) in the evaluation metrics.

Results: Table 4.5.4 shows the performance of experimental models on
aforementioned performance metrics. We can see the benefit of using two input
views instead of one, which helps improve the model performances. Traditional
methods clearly underperform deep learning methods perhaps because these
methods are hard to scale when there are many output labels and the inputs in
our problem are not bag-of-words. Amongst deep learning models, our proposed
ones consistently outperform others in all type of measurements. Our methods
demonstrate 1-2% improvements over the second runner-up baseline WLAS. The
late-fusion mode seems suitable for certain type of metrics, but overall, the
early-fusion mode is the winner, highlighting the importance of modeling early
inter-view interactions.

Case study: In Table 4.7, we show an example of drugs prescribed for a patient
given his current diagnoses and procedures. The patient had serious problems
with his bowel as described in the first four diagnoses. The next three
diagnoses are also severe relating to his heart problems while the remaining
diagnoses are less urgent. It seems that heart-related diagnoses later led to
heart surgeries listed in the procedure codes. Both modes of DMNC predict
correctly the drug Docusate Sodium used to cure urgent bowel symptoms.
Relating to heart diseases and surgeries, our models predict closely to
expert’s choices. Potassium Chloride is necessary for a healthy heart.
Acetaminophen and Propofol are commonly used during surgeries. However, some
heart medicine such as Heparin is missed by the two models. Figs. 4.9 and 4.10
demonstrate the “focus” of the two memories on diagnosis and procedure view,
respectively. The higher the write gate values, the more information of the
medical codes will be written into the memories. We can see both modes pay
less attention on last diagnoses corresponding to less severe symptoms.
Compared to the late-fusion, the early-fusion mode keeps more information on
procedures, especially the heart-related events. This may help increase the
weight on heart-related medicines and enable it to include Acetylsalicylic
Acid, a common drug used after heart attack in the top recommendations.

Figure 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}$.

Figure 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}$.

Table 4.7: Example Recommended Medications by DMNCs on MIMIC-III dataset. Bold denotes matching against ground-truth. Diagnoses |  Calculus Of Gallbladder (57411),Vascular disorders of male genital organs (60883), Abdominal Pain (78901), Poisoning By Other Tranquilizers (9695), Acute Myocardial Infarction Of Other Inferior Wall (41042), Hematoma Complicating (99812), Malignant hypertensive heart disease 40200), Dizziness and giddiness (7804), Venous (Peripheral) Insufficiency, Unspecified (45981), Hemorrhage Of Gastrointestinal Tract (5789)
---|---
Procedures |  Coronary Bypass Of Three Coronary Arteries (3613), Single Internal Mammary Artery Bypass (3615), Extracorporeal circulation auxiliary to open heart surgery (3961), Insertion Of Intercostal Catheter For Drainage (3404), Operations on cornea(114)
Top 5 Ground-truth drugs (manually picked by experts) |  Docusate Sodium (DOCU100L), Acetylsalicylic Acid (ASA81), Heparin (HEPA5I), Acetaminophen (ACET325), Potassium Chloride (KCLBASE2)
Top 5 Late-fusion Recommendations |  Docusate Sodium (DOCU100L), Neostigmine (NEOSI), Acetaminophen (ACET325), Propofol (PROP100IG), Potassium Chloride (KCLBASE2)
Top 5 Early-fusion Recommendations |  Docusate Sodium (DOCU100L), Acetaminophen (ACET325), Potassium Chloride (KCLBASE2), Dextrose (DEX50SY), Acetylsalicylic Acid (ASA81)

####  4.5.5 Disease Progression Task

Data used in this task are two chronic cohorts of diabetes and mental EMRs
collected between 2002-2013 from a large regional hospital in Australia. Since
we want to predict the next diagnoses for a patient given his or her history
of admission, we preprocessed the datasets by removing patients with less than
2 admissions, which ends up with 53,208 and 52,049 admissions for the two
cohorts. In this data set, procedures and medicines are grouped into
intervention codes, together with diagnosis codes forming a patient’s
admission record. The number of diagnosis and intervention codes are 249 and
1071, respectively. We follow the same preprocessing steps and data split as
in Pham et al., (2017). Different from MIMIC-III, a patient record suffering
from chronic conditions often consists of multiple admissions, which is
suitable for the task of predicting disease progression. The average number
and the maximum number of admission per patient are 5.35 and 253,
respectively.

Evaluations: For comparison, we choose the second best-runner in our previous
experiments WLAS and the current state-of-the-art DeepCare Pham et al. (2017)
as the two baselines.

Implementations: We use the validation data set to tune the hyper-parameters
of our implementing methods and have the best embedding and hidden dimensions
are 20 and 64, respectively. The word and memory size for DMNC are found to be
32 and 32, respectively. For performance measurements, we use P@$k$ metric
($k=1,2,3$) to make it comparable with DeepCare’s results reported in Pham et
al., (2017).

Table 4.8: Regional hospital test results. P@K is precision at top K predictions in %. Model | Diabetes | Mental
---|---|---
P@1 | P@2 | P@3 | P@1 | P@2 | P@3
DeepCare | 66.2 | 59.6 | 53.7 | 52.7 | 46.9 | 40.2
WLAS | 65.9 | 60.8 | 56.5 | 51.8 | 48.9 | 45.7
$DMNC_{l}$ | 66.5 | 61.3 | 57.0 | 52.7 | 49.4 | 46.2
$DMNC_{e}$ | 67.6 | 61.2 | 56.9 | 53.6 | 50.0 | 47.1

Results: We report the results on test data of models for disease progression
task in Table 4.8. For both cohorts, our proposed model consistently
outperforms other methods and the performance gains become larger as the
number of predictions increase. Compared to DeepCare which uses pre-trained
embeddings and time-intervals as extra information, our methods only use raw
medical codes and perform better. This emphasises the importance of modeling
view interactions at event level. The late-fusion DMNC seems to perform
slightly better than the early-fusion DMNC in the diabetes cohort, yet
overall, the latter is the better one, which again validates its ability to
model all types of view interactions.

###  4.6 Closing Remarks

In this chapter, we have introduced DCw-MANN and DMNC, which are slot-based
MANNs designed for multiple processes. Under our designs, each input sequence
is assigned a neural controller to encode and store its events to a dedicated
memory. After all input sequences are stored, a decoder will access the
memories and synthesise the read contents to produce the final output. Our
methods can be generalised to sequence-to-sequence and multi-view prediction
tasks that require special handling of long-term dependencies and view
interactions.

In summary, our main contributions are: (i) handling very long-term
dependencies and rare events in healthcare data by solving the sequence
prediction problem, (ii) proposing a novel memory-augmented architecture that
uses dual controller and write-protected mechanism (DCw-MANN) to fit with
sequence-in-sequence-out (SISO) task, (iii) proposing a novel dual memory
neural computer (DMNC) to solve the asynchronous multi-view sequential problem
and designing our architecture to model view interactions and long-term
dependencies, (iv) demonstrating the efficacy of our proposed model on real-
world medical data sets for the problems of treatment recommendation, drug
prescription and disease progression. In particular, our models outperform
other baselines by 1-2% across various metrics, which is significant in the
domain. More importantly, explainability is critical in healthcare and we can
somehow explain the behavior of our models by analysing the write gate of the
memory.

We wish to emphasise that although our models are designed as predictive model
targeted to healthcare, they can be applied to other sequential domains with
similar data characteristics (i.e., sequential, long-term, rare and multi-
view) such as video understanding. Also, the current work is limited to
generating simple and deterministic output sequences. In the next chapter, we
will focus on another important problem, in which, an external memory is
necessary for holding temporal information and composing mixture distributions
in the latent space of generative models.

##  Chapter 5 Variational Memory in Generative Models

###  5.1 Introduction

In the previous chapter, we have addressed the problem of encoder-decoder
architecture with long-term dependencies. However, the decoding is an ill-
posed problem, where there are many possible decoded sequences given an input
sequence. To account for such variation, we need a method to model latent
variables underlying these uncertainty. This lends naturally to generative
model of sequences.

Recent advances in generative modeling have led to exploration of generative
tasks. While generative models such as GAN Goodfellow et al. (2014) and VAE
Kingma and Welling (2014); Rezende et al. (2014) have been applied
successfully for image generation, learning generative models for sequential
discrete data is a long-standing problem. Early attempts to generate sequences
using RNNs Graves (2013) and neural encoder-decoder models Kalchbrenner and
Blunsom (2013); Vinyals and Le (2015) gave promising results, but the
deterministic nature of these models proves to be inadequate in many realistic
settings. Tasks such as translation, question-answering and dialog generation
would benefit from stochastic models that can produce a variety of outputs for
an input. For example, there are several ways to translate a sentence from one
language to another, multiple answers to a question and multiple responses for
an utterance in conversation.

For tasks involving language understanding and production, handling intrinsic
uncertainty and latent variations is necessary. The choice of words and
grammars may change erratically depending on speaker intentions, moods and
previous languages used. The underlying RNNs in neural sequential models find
it hard to capture the dynamics and their outputs are often trivial or too
generic Li et al. (2016). One way to overcome these problems is to introduce
variability into these models. Unfortunately, sequential data such as speech
and natural language is a hard place to inject variability Serban et al.
(2017) since they require a coherence of grammars and semantics yet allow
freedom of word choice.

We propose a novel hybrid approach that integrates MAED (Sec. 3.3.5) and VAE,
called Variational Memory Encoder-Decoder (VMED), to model the sequential
properties and inject variability in sequence generation tasks. In this
proposal, we utilise DC-MANN described in Sec. 4.3 where the powerful DNC
Graves et al. (2016) is chosen as the external memory. We prefer to allow
writing to the memory during inference because in this work, we focus on
generating diverse output sequences, which requires a dynamic memory for both
encoding and decoding process. Furthermore, we introduce latent random
variables to model the variability observed in the data and capture
dependencies between the latent variables across timesteps. Our assumption is
that there are latent variables governing an output at each timestep. In the
conversation context, for instance, the latent space may represent the
speaker’s hidden intention and mood that dictate word choice and grammars. For
a rich latent multimodal space, we use a Mixture of Gaussians (MoG) because a
spoken word’s latent intention and mood can come from different modes, e.g.,
whether the speaker is asking or answering, or she/he is happy or sad. By
modeling the latent space as an MoG where each mode associates with some
memory slot, we aim to capture multiple modes of the speaker’s intention and
mood when producing a word in the response. Since the decoder in our model has
multiple read heads, the MoG can be computed directly from the content of
chosen memory slots. Our external memory plays a role as a mixture model
distribution generating the latent variables that are used to produce the
output and take part in updating the memory for future generative steps.

To train our model, we adapt Stochastic Gradient Variational Bayes (SGVB)
framework Kingma and Welling (2014). Instead of minimising the $KL$ divergence
directly, we resort to using its variational approximation Hershey and Olsen
(2007) to accommodate the MoG in the latent space. We show that minimising the
approximation results in $KL$ divergence minimisation. We further derive an
upper bound on our total timestep-wise $KL$ divergence and demonstrate that
minimising the upper bound is equivalent to fitting a continuous function by a
scaled MoG. We validate the proposed model on the task of conversational
response generation. This task serves as a nice testbed for the model because
an utterance in a conversation is conditioned on previous utterances, the
intention and the mood of the speaker. Finally, we evaluate our model on two
open-domain and two closed-domain conversational datasets. The results
demonstrate our proposed VMED gains significant improvement over state-of-the-
art alternatives.

###  5.2 Preliminaries

####  5.2.1 Conditional Variational Autoencoder (CVAE) for Conversation
Generation

A dyadic conversation can be represented via three random variables: the
conversation context $x$ (all the chat before the response utterance), the
response utterance $y$ and a latent variable $z$, which is used to capture the
latent distribution over the reasonable responses. A variational autoencoder
conditioned on $x$ (CVAE) is trained to maximise the conditional log
likelihood of $y$ given $x$, which involves an intractable marginalisation
over the latent variable $z$, i.e.,

$p\left(y\mid x\right)=\int_{z}p\left(y,z\mid x\right)dz=\int_{z}p\left(y\mid
x,z\right)p\left(z\mid x\right)dz$ (5.1)

Fortunately, CVAE can be efficiently trained with the Stochastic Gradient
Variational Bayes (SGVB) framework Kingma and Welling (2014) by maximising the
variational lower bound of the conditional log likelihood. In a typical CVAE
work, $z$ is assumed to follow multivariate Gaussian distribution with a
diagonal covariance matrix, which is conditioned on $x$ as
$p_{\phi}\left(z\mid x\right)$ and a recognition network $q_{\theta}(z\mid
x,y)$ to approximate the true posterior distribution $p(z\mid x,y).$ The
variational lower bound becomes

$\displaystyle L\left(\phi,\theta;y,x\right)=$ $\displaystyle-
KL\left(q_{\theta}\left(z\mid x,y\right)\parallel p_{\phi}\left(z\mid
x\right)\right)$ (5.2) $\displaystyle+\mathbb{E}_{q_{\theta}\left(z\mid
x,y\right)}\left[\log p\left(y\mid x,z\right)\right]\leq\log p\left(y\mid
x\right)$ (5.3)

where $KL$ is the Kullback–Leibler divergence. With the introduction of the
neural approximator $q_{\theta}(z\mid x,y)$ and the reparameterisation trick
Kingma et al. (2014), we can apply the standard back-propagation to compute
the gradient of the variational lower bound. Fig. 5.1(a) depicts elements of
the graphical model for this approach in the case of using CVAE.

####  5.2.2 Related Works

With the recent revival of recurrent neural networks (RNNs), there has been
much effort spent on learning generative models of sequences. Early attempts
include training RNN to generate the next output given previous sequence,
demonstrating RNNs’ ability to generate text and handwriting images Graves
(2013). Later, encoder-decoder architecture Sutskever et al. (2014b) enables
generating a whole sequence in machine translation Kalchbrenner and Blunsom
(2013), text summation Nallapati et al. (2016) and conversation generation
Vinyals and Le (2015). Although these models have achieved significant
empirical successes, they fall short to capture the complexity and variability
of sequential processes.

These limitations have recently triggered a considerable effort on introducing
variability into the encoder-decoder architecture. Most of the methods focus
on conditional VAE (CVAE) by constructing a variational lower bound
conditioned on the context. The setting can be found in many applications
including machine translation Zhang et al. (2016a) and dialog generation
Bowman et al. (2016); Serban et al. (2017); Shen et al. (2017); Zhao et al.
(2017). A common trick is to place a neural net between the encoder and the
decoder to compute the Gaussian prior and posterior of the CVAE. This design
is further enhanced by the use of external memory Chen et al. (2018) and
reinforcement learning Wen et al. (2017). In contrast to this design, our VMED
uses recurrent latent variable approach Chung et al. (2015), that is, our
model requires a CVAE for each step of generation. Besides, our external
memory is used for producing the latent distribution, which is different from
the one proposed in Chen et al. (2018) where the memory is used only for
holding long-term dependencies at sentence level. Compared to variational
addressing scheme mentioned in Bornschein et al. (2017), our memory uses
deterministic addressing scheme, yet the memory content itself is used to
introduce randomness to the architecture. More relevant to our work is GTMM
Gemici et al. (2017) where memory read-outs involve in constructing the prior
and posterior at every timestep. However, this approach uses Gaussian prior
without conditional context.

Using mixture of models instead of single Gaussian in VAE framework is not a
new concept. Several works proposed replacing the Gaussian prior and posterior
in VAE by MoGs for clustering and generating image problems Dilokthanakul et
al. (2016); Jiang et al. (2017); Nalisnick et al. (2016). Others applied MoG
prior to model transitions between video frames and caption generation Shu et
al. (2016); Wang et al. (2017). These methods use simple feed forward network
to produce Gaussian sub-distributions independently. In our model, on the
contrary, memory slots are strongly correlated with each others, and thus
modes in our MoG work together to define the shape of the latent distributions
at specific timestep. To the best of our knowledge, our work is the first
attempt to use an external memory to induce mixture models for sequence
generation problems.

###  5.3 Variational Memory Encoder-Decoder

Built upon CVAE and partly inspired by VRNN Chung et al. (2015), we introduce
a novel memory-augmented variational recurrent network dubbed Variational
Memory Encoder-Decoder (VMED). With an external memory module, VMED explicitly
models the dependencies between latent random variables across subsequent
timesteps. However, unlike the VRNN which uses hidden values of RNN to model
the latent distribution as a Gaussian, our VMED uses read values $r$ from an
external memory $M$ as a Mixture of Gaussians (MoG) to model the latent space.
This choice of MoG also leads to new formulation for the prior $p_{\phi}$ and
the posterior $q_{\theta}$ mentioned in Eq. (5.2). The graphical
representation of our model is shown in Fig. 5.1(b).

Figure 5.1: Graphical Models of the vanilla CVAE (a) and our proposed VMED (b)

####  5.3.1 Generative Process

The VMED includes a CVAE at each time step of the decoder. These CVAEs are
conditioned on the context sequence via $K$ read values
$r_{t-1}=\left[r_{t-1}^{1},r_{t-1}^{2},...,r_{t-1}^{K}\right]$ from the
external memory. Since the read values are conditioned on the previous state
of the decoder $h_{t-1}^{d}$, our model takes into account the temporal
structure of the output. Unlike other designs of CVAE where there is often
only one CVAE with a Gaussian prior for the whole decoding process, our model
keeps reading the external memory to produce the prior as a Mixture of
Gaussians at every timestep. At the $t$-th step of generating an utterance in
the output sequence, the decoder will read from the memory $K$ read values,
representing $K$ modes of the MoG. This multi-modal prior reflects the fact
that given a context $x$, there are different modes of uttering the output
word $y_{t}$, which a single mode cannot fully capture. The MoG prior
distribution is modeled as

$g_{t}=p_{\phi}\left(z_{t}\mid
x,r_{t-1}\right)=\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi_{t}^{i,x}\left(x,r_{t-1}^{i}\right)\mathcal{N}\left(z_{t};\mu_{t}^{i,x}\left(x,r_{t-1}^{i}\right),\sigma_{t}^{i,x}\left(x,r_{t-1}^{i}\right)^{2}\mathbf{I}\right)$
(5.4)

We treat the mean $\mu_{t}^{i,x}$ and standard deviation (s.d.)
$\sigma_{t}^{i,x}$ of each Gaussian distribution in the prior as neural
functions of the context sequence $x$ and read vectors from the memory. The
context is encoded into the memory by an $LSTM^{E}$ encoder. In decoding, the
decoder $LSTM^{D}$ attends to the memory and choose $K$ read vectors. We split
each read vector into two parts $r^{i,\mu}$ and $r^{i,\sigma}$ , each of which
is used to compute the mean and s.d., respectively:
$\mu_{t}^{i,x}=r_{t-1}^{i,\mu}$,
$\sigma_{t}^{i,x}=softplus\left(r_{t-1}^{i,\sigma}\right)$. Here we use the
softplus function for computing s.d. to ensure the positiveness. The mode
weight $\pi_{t}^{i,x}$ is chosen based on the read attention weights
$w_{t-1}^{i,r}$ over memory slots. Since we use soft-attention, a read value
is computed from all slots yet the main contribution comes from the one with
highest attention score. Thus, we pick the maximum attention score in each
read weight and normalise to become the mode weights:
$\pi_{t}^{i,x}=\max\,w_{t-1}^{i,r}/\stackrel{{\scriptstyle[}}{{i}}=1]{i=K}{\sum}\max\,w_{t-1}^{i,r}$.

Armed with the prior, we follow a recurrent generative process by
alternatively using the memory to compute the MoG and using latent variable
$z$ sampled from the MoG to update the memory and produce the output
conditional distribution. The pseudo-algorithm of the generative process is
given in Algorithm 1.

1:Given $p_{\phi}$, $\left[r_{0}^{1},r_{0}^{2},...,r_{0}^{K}\right]$,
$h_{0}^{d}$, $y_{0}^{*}$

2:for $t=1,T$ do

3: Sampling $z_{t}\sim p_{\phi}\left(z_{t}\mid x,r_{t-1}\right)$ in Eq.(5.4)

4: Compute:
$o_{t}^{d},h_{t}^{d}=LSTM^{D}\left(\left[y_{t-1}^{*},z_{t}\right],h_{t-1}^{d}\right)$

5: Compute the conditional distribution: $p\left(y_{t}\mid x,z_{\leq
t}\right)=\operatorname{softmax}\left(W_{out}o_{t}^{d}\right)$

6: Update memory and read $[r_{t}^{1},r_{t}^{2},...,r_{t}^{K}]$ using
$h_{t}^{d}$ as in DNC

7: Generate output $y_{t}^{*}=\underset{y\in
Vocab}{argmax}\,p\left(y_{t}=y\mid x,z_{\leq t}\right)$

8:end for

Algorithm 1 VMED Generation

####  5.3.2 Neural Posterior Approximation

At each step of the decoder, the true posterior $p\left(z_{t}\mid x,y\right)$
will be approximated by a neural function of $x,y$ and $r_{t-1}$, denoted as
$q_{\theta}\left(z_{t}\mid x,y,r_{t-1}\right)$ . Here, we use a Gaussian
distribution to approximate the posterior. The unimodal posterior is chosen
because given a response $y$, it is reasonable to assume only one mode of
latent space is responsible for this response. Also, choosing a unimodel will
allow the reparameterisation trick during training and reduce the complexity
of $KL$ divergence computation. The approximated posterior is computed by the
following the equation

$f_{t}=q_{\theta}\left(z_{t}\mid x,y_{\leq
t},r_{t-1}\right)=\mathcal{N}\left(z_{t};\mu_{t}^{x,y}\left(x,y_{\leq
t},r_{t-1}\right),\sigma_{t}^{x,y}\left(x,y_{\leq
t},r_{t-1}\right)^{2}\textrm{$\mathbf{I}$}\right)$ (5.5)

with mean $\mu_{t}^{x,y}$ and s.d. $\sigma_{t}^{x,y}$. We use an $LSTM^{U}$
utterance encoder to model the ground truth utterance sequence up to timestep
$t$-th $y_{\leq t}$. The $t$-th hidden value of the $LSTM^{U}$ is used to
represent the given data in the posterior:
$h_{t}^{u}=LSTM^{U}\left(y_{t},h_{t-1}^{u}\right)$. The neural posterior
combines the read values
$\mathbf{r}_{t}=\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi_{t}^{i,x}r_{t-1}^{i}$
together with the ground truth data to produce the Gaussian posterior:
$\mu_{t}^{x,y}=W_{\mu}\left[\mathbf{r}_{t},h_{t}^{u}\right]$,
$\sigma_{t}^{x,y}=softplus\left(W_{\sigma}\left[\mathbf{r}_{t},h_{t}^{u}\right]\right)$.
In these equations, we use learnable matrix weights $W_{\mu}$ and $W_{\sigma}$
as a recognition network to compute the mean and s.d. of the posterior,
ensuring that the distribution has the same dimension as the prior. We apply
the reparamterisation trick to calculate the random variable sampled from the
posterior as $z^{\prime}_{t}=\mu_{t}^{x,y}+\sigma_{t}^{x,y}\odot\epsilon$,
$\epsilon\in\mathcal{N}\left(0,\mathbf{I}\right)$. Intuitively, the
reparameterisation trick bridges the gap between the generation model and the
inference model during the training.

####  5.3.3 Learning

In the training phase, the neural posterior is used to produce the latent
variable $z^{\prime}_{t}$. The read values from memory are used directly as
the MoG priors and the priors are trained to approximate the posterior by
reducing the $KL$ divergence. During testing, the decoder uses the prior for
generating latent variable $z_{t}$, from which the output is computed. The
training and testing diagram is illustrated in Fig. 5.2. The objective
function becomes a timestep-wise variational lower bound by following similar
derivation presented in Chung et al., (2015),

$\mathcal{L}\left(\theta,\phi;y,x\right)=E_{q*}\left[\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}-KL\left(q_{\theta}\left(z_{t}\mid
x,y_{\leq t},r_{t-1}\right)\parallel p_{\phi}\left(z_{t}\mid
x,r_{t-1}\right)\right)+\log p\left(y_{t}\mid x,z_{\leq t}\right)\right]$
(5.6)

where $q*=q_{\theta}\left(z_{\leq T}\mid x,y_{\leq T},r_{<T}\right)$. To
maximise the objective function, we have to compute $KL$ divergence between
$f_{t}=q_{\theta}\left(z_{t}\mid x,y_{\leq t},r_{t-1}\right)$ and
$g_{t}=p_{\phi}\left(z_{t}\mid x,r_{t-1}\right)$. Since there is no closed-
form for this $KL\left(f_{t}\parallel g_{t}\right)$ between Gaussian $f_{t}$
and Mixture of Gaussians $g_{t}$, we use a closed-form approximation named
$D_{var}$ Hershey and Olsen (2007) to replace the $KL$ term in the objective
function. For our case: $KL\left(f_{t}\parallel g_{t}\right)\approx
D_{var}\left(f_{t}\parallel
g_{t}\right)=-\log\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi^{i}e^{-KL\left(f_{t}\parallel
g_{t}^{i}\right)}$. Here, $KL\left(f_{t}\parallel g_{t}^{i}\right)$ is the
$KL$ divergence between two Gaussians and $\pi^{i}$ is the mode weight of
$g_{t}$. The final objective function is

$\displaystyle\mathcal{L}=$
$\displaystyle\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\log\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\left[\pi_{t}^{i,x}\exp\left(-KL\left(\mathcal{N}\left(\mu_{t}^{x,y},\sigma_{t}^{x,y}{}^{2}\textrm{$\mathbf{I}$}\right)\parallel\mathcal{N}\left(\mu_{t}^{i,x},\sigma_{t}^{i,x}{}^{2}\mathbf{I}\right)\right)\right)\right]$
(5.7)
$\displaystyle+\frac{1}{L}\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\stackrel{{\scriptstyle[}}{{l}}=1]{L}{\sum}\log
p\left(y_{t}\mid x,z_{\leq t}^{(l)}\right)$

Figure 5.2: Training and testing of VMED

####  5.3.4 Theoretical Analysis

We now show that by modeling the prior as MoG and the posterior as Gaussian,
minimising the approximation results in $KL$ divergence minimisation.

######  Theorem 5.1.

The KL divergence between a Gaussian and a Mixture of Gaussians has an upper
bound $D_{var}$.

A sketch of the proof is derived (see C.1 for full derivation). Let define the
log-likelihood $L_{f}\left(g\right)=E_{f\left(x\right)}\left[\log
g\left(x\right)\right]$, we have

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

Thus, minimising $D_{var}$ results in $KL$ divergence minimisation. Next, we
establish an upper bound on the total timestep-wise $KL$ divergence in Eq.
(5.6) and show that minimising this upper bound is equivalent to fitting a
continuous function by a scaled MoG. The total timestep-wise $KL$ divergence
reads

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

where $g_{t}=\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}\pi_{t}^{i}g_{t}^{i}$
and $g_{t}^{i}$ is the $i$-th Gaussian in the MoG at timestep $t$-th. If at
each decoding step, minimising $D_{var}$ results in adequate $KL$ divergence
such that the prior is optimised close to the neural posterior, according to
Chebyshev’s sum inequality, we can derive an upper bound on the total
timestep-wise $KL$ divergence as (see Supplementary Materials for full
derivation)

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

The left term is sum of the entropies of $f_{t}\left(x\right)$, which does not
depend on the training parameter $\phi$ used to compute $g_{t}$, so we can
ignore that. Thus given $f$, minimising the upper bound of the total timestep-
wise $KL$ divergence is equivalent to maximising the right term of Eq. (5.8).
Since $g_{t}$ is an MoG and products of MoG is proportional to an MoG,
$\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\prod}g_{t}\left(x\right)$ is a scaled
MoG (see Supplementary material for full proof). Maximising the right term is
equivalent to fitting function
$\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}f_{t}\left(x\right)$, which is sum
of Gaussians and thus continuous, by a scaled MoG. This, in theory, is
possible regardless of the form of $f_{t}$ since MoG is a universal
approximator Bacharoglou (2010); Maz’ya and Schmidt (1996).

###  5.4 Experiments and Results

####  5.4.1 Quantitative Results

Table 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).  Model | Cornell Movies | OpenSubtitle | LJ users | Reddit comments
---|---|---|---|---
B1 | B4 | AG | B1 | B4 | AG | B1 | B4 | AG | B1 | B4 | AG
Seq2Seq | 18.4 | 9.5 | 0.52 | 11.4 | 5.4 | 0.29 | 13.1 | 6.4 | 0.45 | 7.5 | 3.3 | 0.31
Seq2Seq-att | 17.7 | 9.2 | 0.54 | 13.2 | 6.5 | 0.42 | 11.4 | 5.6 | 0.49 | 5.5 | 2.4 | 0.25
DNC | 17.6 | 9.0 | 0.51 | 14.3 | 7.2 | 0.47 | 12.4 | 6.1 | 0.47 | 7.5 | 3.4 | 0.28
CVAE | 16.5 | 8.5 | 0.56 | 13.5 | 6.6 | 0.45 | 12.2 | 6.0 | 0.48 | 5.3 | 2.8 | 0.39
VLSTM | 18.6 | 9.7 | 0.59 | 16.4 | 8.1 | 0.43 | 11.5 | 5.6 | 0.46 | 6.9 | 3.1 | 0.27
VMED (K=1) | 20.7 | 10.8 | 0.57 | 12.9 | 6.2 | 0.44 | 13.7 | 6.9 | 0.47 | 9.1 | 4.3 | 0.39
VMED (K=2) | 22.3 | 11.9 | 0.64 | 15.3 | 8.8 | 0.49 | 15.4 | 7.9 | 0.51 | 9.2 | 4.4 | 0.38
VMED (K=3) | 19.4 | 10.4 | 0.63 | 24.8 | 12.9 | 0.54 | 18.1 | 9.8 | 0.49 | 12.3 | 6.4 | 0.46
VMED (K=4) | 23.1 | 12.3 | 0.61 | 17.9 | 9.3 | 0.52 | 14.4 | 7.5 | 0.47 | 8.6 | 4.6 | 0.41

Datasets and pre-processing: We perform experiments on two collections: The
first collection includes open-domain movie transcript datasets containing
casual conversations: Cornell
Movies111http://www.cs.cornell.edu/~cristian/Cornell_Movie-Dialogs_Corpus.html
and OpenSubtitle222http://opus.nlpl.eu/OpenSubtitles.php. They have been used
commonly in evaluating conversational agents Lison and Bibauw (2017); Vinyals
and Le (2015). The second are closed-domain datasets crawled from specific
domains, which are question-answering of LiveJournal (LJ) users and Reddit
comments on movie topics. For each dataset, we use 10,000 conversations for
validating and 10,000 for testing.

Baselines, implementations and metrics: We compare our model with three
deterministic baselines: the encoder-decoder neural conversational model
(Seq2Seq) Vinyals and Le (2015) and its two variants equipped with attention
mechanism Cho et al. (2014a); Bahdanau et al. (2015) (Seq2Seq-att) and a DNC
external memory Graves et al. (2016) (DNC). The vanilla CVAE is also included
in the baselines. To build this CVAE, we follow similar architecture
introduced in Zhao et al. (2017) without bag-of-word loss and dialog act
features333Another variant of non-memory CVAE with MoG prior is also examined.
We produce a set of MoG parameters by a feed forward network with the input as
the last encoder hidden states. However, the model is hard to train and fails
to converge with these datasets.. A variational recurrent model without memory
is also included in the baselines. The model termed VLSTM is implemented based
on LSTM instead of RNN as in VRNN framework Chung et al. (2015). We try our
model VMED444Source code is available at https://github.com/thaihungle/VMED
with different number of modes ($K=1,2,3,4$). It should be noted that, when
$K=1$, our model’s prior is exactly a Gaussian and the $KL$ term in Eq. (7.6)
is no more an approximation. Details of dataset descriptions and model
implementations are included in Supplementary material.

We report results using two performance metrics in order to evaluate the
system from various linguistic points of view: (i) Smoothed Sentence-level
BLEU Chen and Cherry (2014): BLEU is a popular metric that measures the
geometric mean of modified ngram precision with a length penalty. We use
BLEU-1 to 4 as our lexical similarity. (ii) Cosine Similarly of Sentence
Embedding: a simple method to obtain sentence embedding is to take the average
of all the word embeddings in the sentences Forgues et al. (2014). We follow
Zhao et al., (2017) and choose Glove Levy and Goldberg (2014) as the word
embedding in measuring sentence similarly (A-Glove) Zhao et al. (2017). To
measure stochastic models, for each input, we generate output ten times. The
metric between the ground truth and the generated output is calculated and
taken average over ten responses.

Metric-based Analysis: We report results on four test datasets in Table 5.1.
For BLEU scores, here we only list results for BLEU-1 and 4. Other BLEUs show
similar pattern and will be listed in Supplementary material. As clearly seen,
VMED models outperform other baselines over all metrics across four datasets.
In general, the performance of Seq2Seq is comparable with other deterministic
methods despite its simplicity. Surprisingly, CVAE or VLSTM does not show much
advantage over deterministic models. As we shall see, although CVAE and VLSTM
responses are diverse, they are often out of context. Amongst different modes
of VMED, there is often one best fit with the data and thus shows superior
performance. The optimal number of modes in our experiments often falls to
$K=3$, indicating that increasing modes does not mean to improve accuracy.

It should be noted that there is inconsistency between BLEU scores and A-Glove
metrics. This is because BLEU measures lexicon matching while A-Glove
evaluates semantic similarly in the embedding space. For example, two
sentences having different words may share the same meaning and lie close in
the embedding space. In either case, compared to others, our optimal VMED
always achieves better performance.

####  5.4.2 Qualitative Analysis

Table 5.2: Examples of context-response pairs. /*/ denotes separations between stochastic responses. Input context |  Response
---|---
Reddit comment: What is your favorite scene in film history ? Mine is the restaurant scene in the Godfather. |  Seq2Seq: The scene in
|  Seq2Seq-att: The final
|  DNC: The scene in
|  CVAE: Inception god! Not by a shark /*/ Amour great /*/ Pro thing you know
3 dead
|  VLSTM: The scene in /*/ The of a dead /*/ The sky in scene
|  VMED (K=3): The opening scene from history movie /*/ The scene in a shot
nights! Robin movie /*/ The psycho scene in fight from
Reddit comment: What actor will win an Oscar in the next 10 years ? |  Seq2Seq: Colin
|  Seq2Seq-att: Liam Neeson
|  DNC: Tom Gyllenhaal
|  CVAE: Daryl and Aaron /*/ Carefully count Alfred Deniro /*/ Ponyo Joker
possible
|  VLSTM: Michael Bullock /*/ Michael /*/ Michael De
|  VMED (K=3): Edward or Leo Dicaprio goes on /*/ Dicaprio will /*/ Dicaprio
Tom has actually in jack on road
LJ user: Your very pretty and your is very cute. May i add ya to my friends list ? |  Seq2Seq: I! Add and too you back
|  Seq2Seq-att: I did may! Away back
|  DNC: Sure you added
|  CVAE: Sure ! I can add you /*/ Thank cool of surely /*/ Thank hi of sure!
|  VLSTM: Haha of do go /*/ Haha of sure! Yes lol /*/ Haha sure! Go
|  VMED (K=3): Thank cool for sure /*/ Add definitely! Sure surely friends /*/
Thank girl go ahead
Cornell movies: Nobody can murder someone with their feelings . I mean that is crazy ? |  Seq2Seq: Yes you are
|  Seq2Seq-att: Really not is it
|  DNC: Managing the truth
|  CVAE: Sure not to be in here /*/ Oh yes but i know! /*/ That to doing with
here and
|  VLSTM: I am dead . ! That is … /*/ I did not what way . /*/ I am not . But
his things with …
|  VMED (K=4): You are right! /*/ That is crazy /*/ You can’t know Jimmy
OpenSubtitle: I’m obliged for your hospitality. I appreciate it and your husband too. |  Seq2Seq: That is have got coming about these
|  Seq2Seq-att: May you not what nothing nobody
|  DNC: Yes i am taking this
|  CVAE: No . that for good! And okay /*/ All in the of two thing /*/ Sure. Is
this!
|  VLSTM: I … /*/ I understand /*/ I ! . …
|  VMED (K=3): I know. I can afford /*/ I know nothing to store for you pass
/*/ I know. Doing anymore you father

Table 5.2 represents responses generated by experimental models in reply to
different input sentences. The replies listed are chosen randomly from 50
generated responses whose average of metric scores over all models are
highest. For stochastic models, we generate three times for each input,
resulting in three different responses. In general, the stochastic models
often yield longer and diverse sequences as expected. For closed-domain cases,
all models responses are fairly acceptable. Compared to the rest, our VMED’s
responds seem to relate more to the context and contain meaningful
information. In this experiment, the open-domain input seems nosier and harder
than the closed-domain ones, thus create a big challenge for all models.
Despite that, the quality of VMED’s responses is superior to others. Amongst
deterministic models, DNC’s generated responses look more reasonable than
Seq2Seq’s even though its BLEU scores are not always higher. Perhaps, the
reference to external memory at every timestep enhances the coherence between
output and input, making the response more related to the context. VMED may
inherit this feature from its external memory and thus tends to produce
reasonable responses. By contrast, although responses from CVAE and VLSTM are
not trivial, they have more grammatical errors and sometimes unrelated to the
topic.

###  5.5 Closing Remarks

In this chapter, we propose a novel approach to sequence generation called
Variational Memory Encoder-Decoder (VMED) that introduces variability into
encoder-decoder architecture via the use of external memory as mixture model.
By modeling the latent temporal dependencies across timesteps, our VMED
produces a MoG representing the latent distribution. Each mode of the MoG
associates with some memory slot and thus captures some aspect of context
supporting generation process. To accommodate the MoG, we employ a $KL$
approximation and we demonstrate that minimising this approximation is
equivalent to minimising the $KL$ divergence. We derive an upper bound on our
total timestep-wise $KL$ divergence and indicate that the optimisation of this
upper bound is equivalent to fitting a continuous function by an scaled MoG,
which is in theory possible regardless of the function form. This forms a
theoretical basis for our model formulation using MoG prior for every step of
generation. We apply our proposed model to conversation generation problem.
The results demonstrate that VMED outperforms recent advances both
quantitatively and qualitatively.

So far we have designed and applied MANNs to long-term sequential modeling
problems without considering the memorisation ability of these models.
Besides, we have followed common memory access patterns without judging the
effectiveness of these accesses. We will tackle these issues in the next
chapter.

##  Chapter 6 Optimal Writing Memory

###  6.1 Introduction

Recall that a core task in sequence learning is to capture long-term
dependencies amongst timesteps which demands memorisation of distant inputs
(Sec. 2.4). In recurrent neural networks (RNNs), the memorisation is
implicitly executed via integrating the input history into the state of the
networks. However, learning vanilla RNNs over long distance proves to be
difficult due to the vanishing gradient problem (Sec. 2.4.1). One alleviation
is to introduce skip-connections along the execution path, in the form of
dilated layers Van Den Oord et al. (2016); Chang et al. (2017), which is not
our main focus. Other solutions have been mentioned in Chapter 3 including
attention mechanisms Cho et al. (2014a); Vaswani et al. (2017); Bahdanau et
al. (2015) and external slot-based memory Graves et al. (2014, 2016).

Amongst all, using external memory most resembles human cognitive architecture
where we perceive the world sequentially and make decision by consulting our
memory. Recent attempts have simulated this process by using RAM-like memory
architectures that store information into memory slots. Reading and writing
are governed by neural controllers using attention mechanisms (Sec. 3.3).

Despite the promising empirical results, there is no theoretical analysis or
clear understanding on optimal operations that a memory should have to
maximise its performance. To the best of our knowledge, no solution has been
proposed to help MANNs handle ultra-long sequences given limited memory. This
scenario is practical because (i) sequences in the real-world can be very long
while the computer resources are limited and (ii) it reflects the ability to
compress in human brain to perform life-long learning. Previous attempts Rae
et al. (2016) 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. This chapter presents a new approach towards finding
optimal operations for MANNs that serve the purpose of learning longer
sequences with finite memory.

More specifically, upon analysing RNN and MANN operations we first introduce a
measurement on the amount of information that a MANN holds after encoding a
sequence. This metric reflects the quality of memorisation under the
assumption that contributions from timesteps are equally important. We then
derive a generic solution to optimise the measurement. We term this optimal
solution as Uniform Writing (UW), and it is applicable for any MANN due to its
generality. Crucially, UW helps reduce significantly the computation time of
MANN. Third, to relax the assumption and enable the method to work in
realistic settings, we further propose Cached Uniform Writing (CUW) as an
improvement over the Uniform Writing scheme. By combining uniform writing with
local attention, CUW can learn to discriminate timesteps while maximising
local memorisation. Finally we demonstrate that our proposed models outperform
several MANNs and other state-of-the-art methods in various synthetic and
practical sequence modeling tasks.

###  6.2 Related Backgrounds

Traditional recurrent models such as RNN/LSTM Elman (1990); Hochreiter and
Schmidhuber (1997) exhibit some weakness that prevents them from learning
really long sequences. The reason is mainly due to the vanishing gradient
problem or to be more specific, the exponential decay of input value over
time, which is analysed in Sec. 2.4.1. It should be noted that although LSTM
is designed to diminish the problem, it is limited to the capacity of cell
memory. In other words, if the amount of relevant information exceeds the
capacity, LSTM will forget distant inputs since exponential decay still exists
outside the cell memory. One different approach to overcome this problem is
enforcing the exponential decay factor close to one by putting a unitary
constraint on the recurrent weight Arjovsky et al. (2016); Wisdom et al.
(2016). Although this approach is theoretically motivated, it restricts the
space of learnt parameters.

More relevant to our work, the idea of using less or adaptive computation has
been proposed by many Graves (2016); Yu et al. (2017, 2018); Seo et al.
(2018). Most of these works are based on the assumption that some of timesteps
in a sequence are unimportant and thus can be ignored to reduce the cost of
computation and increase the performance of recurrent networks. Different form
our approach, these methods lack theoretical supports and do not directly aim
to solve the problem of memorising long-term dependencies.

Dilated RNN Chang et al. (2017) is another RNN-based proposal which improves
long-term learning by stacking multiple dilated recurrent layers with
hierarchical skip-connections. This theoretically guarantees the mean
recurrent length and shares with our method the idea to construct a
measurement on memorisation capacity of the system and propose solutions to
optimise it. The difference is that our system is memory-augmented neural
networks while theirs is multi-layer RNNs, which leads to totally different
optimisation problems.

Recent researches recommend to replace traditional recurrent models by other
neural architectures to overcome the vanishing gradient problem. The
Transformer Vaswani et al. (2017) attends to all timesteps at once, which
ensures instant access to distant timestep yet requires quadratic computation
and physical memory proportional to the sequence length (see Sec. 3.2.3).
Memory-augmented neural networks (MANNs), on the other hand, learn to
establish a limited-size memory and attend to the memory only, which is
scalable to any-length sequence (see Sec. 3.3). Compared to others, MANNs
resemble both computer architecture design and human working memory Logie
(2014). However, the current understanding of the underlying mechanisms and
theoretical foundations for MANNs are still limited.

Recent works on MANNs rely almost on reasonable intuitions. Some introduce new
addressing mechanisms such as location-based Graves et al. (2014), least-used
Santoro et al. (2016) and order-based Graves et al. (2016). Others focus on
the scalability of MANN by using sparse memory access to avoid attending to a
large number of memory slots Rae et al. (2016). These problems are different
from ours which involves MANN memorisation capacity optimisation.

Our local optimal solution to this problem is related to some known neural
caching Grave et al. (2017b, a); Yogatama et al. (2018) in terms of storing
recent hidden states for later encoding uses. These methods either aim to
create structural bias to ease the learning process Yogatama et al. (2018) or
support large scale retrieval Grave et al. (2017a). These are different from
our caching purpose, which encourages overwriting and relaxes the equal
contribution assumption of the optimal solution. Also, the details of
implementation are different as ours uses local memory-augmented attention
mechanisms.

###  6.3 Theoretical Analysis on Memorisation

####  6.3.1 Generic Memory Operations

Memory-augmented neural networks can be viewed as an extension of RNNs with
external memory $M$. The memory supports read and write operations based on
the output $o_{t}$ of the controller, which in turn is a function of current
timestep input $x_{t}$, previous hidden state $h_{t-1}$ and read value
$r_{t-1}$ from the memory. Let assume we are given these operators from recent
MANNs such as NTM Graves et al. (2014) or DNC Graves et al. (2016),
represented as

$r_{t}=f_{r}\left(o_{t},M_{t-1}\right)$ (6.1)
$M_{t}=f_{w}\left(o_{t},M_{t-1}\right)$ (6.2)

The controller output and hidden state are updated as follows,

$o_{t}=f_{o}\left(h_{t-1},r_{t-1},x_{t}\right)$ (6.3)
$h_{t}=f_{h}\left(h_{t-1},r_{t-1},x_{t}\right)$ (6.4)

Here, $f_{o}$ and $f_{h}$ are often implemented as RNNs while $f_{r}$ and
$f_{w}$ are designed specifically for different memory types.

Current MANNs only support regular writing by applying Eq. (6.2) every
timestep. In effect, regular writing ignores the accumulated short-term memory
stored in the controller hidden states which may well-capture the recent
subsequence. We argue that the controller does not need to write to memory
continuously as its hidden state also supports memorising. Another problem of
regular writing is time complexity. As the memory access is very expensive,
reading/writing at every timestep makes MANNs much slower than RNNs. This
motivates a irregular writing strategy to utilise the memorisation capacity of
the controller and consequently, speed up the model. In the next sections, we
first define a metric to measure the memorisation performance of RNNs, as well
as MANNs. Then, we solve the problem of finding the best irregular writing
that optimises the metric.

####  6.3.2 Memory Analysis of RNNs

We first define the ability to “remember” of recurrent neural networks, which
is closely related to the vanishing/exploding gradient problem Pascanu et al.
(2013). In RNNs, the state transition $h_{t}=\phi\left(h_{t-1},x_{t}\right)$
contains contributions from not only $x_{t}$, but also previous timesteps
$x_{i<t}$ embedded in $h_{t-1}$. Thus, $h_{t}$ can be considered as a function
of timestep inputs, i.e, $h_{t}=f\left(x_{1},x_{2},...,x_{t}\right)$. One way
to measure how much an input $x_{i}$ contributes to the value of $h_{t}$ is to
calculate the norm of the gradient $\left\|\frac{\partial h_{t}}{\partial
x_{i}}\right\|$. If the norm equals zero, $h_{t}$ is constant w.r.t $x_{i}$,
that is, $h_{t}$ does not “remember” $x_{i}$. As a bigger
$\left\|\frac{\partial h_{t}}{\partial x_{i}}\right\|$ implies more influence
of $x_{i}$ on $h_{t}$, we propose using $\left\|\frac{\partial h_{t}}{\partial
x_{i}}\right\|$ to measure the contribution of the $i$-th input to the $t$-th
hidden state. Let $c_{i,t}$ denotes this term, we can show that in the case of
common RNNs, $\lambda_{c}c_{i,t}\geq c_{i-1,t}$ with some
$\lambda_{c}\in\mathbb{R^{+}}$(see Appendix D.1 \- D.3 for proof). This means
further to the past, the contribution decays (when $\lambda_{c}<1$) or grows
(when $\lambda_{c}>1$) with the rate of at least $\lambda_{c}$ .We can measure
the average amount of contributions across $T$ timesteps as follows (see
Appendix D.4 for proof):

######  Theorem 6.1.

There exists $\lambda\in\mathbb{R^{+}}$such that the average contribution of a
sequence of length T with respect to a RNN can be quantified as the following,

$I_{\lambda}=\frac{\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}c_{t,T}}{T}=c_{T,T}\frac{\stackrel{{\scriptstyle[}}{{t}}=1]{T}{\sum}\lambda^{T-t}}{T}$
(6.5)

If $\lambda<1$, $\lambda^{T-t}\rightarrow 0$ as $T-t\rightarrow\infty$. This
is closely related to vanishing gradient problem. LSTM is known to “remember”
long sequences better than RNN by using extra memory gating mechanisms, which
help $\lambda$ to get closer to 1. If $\lambda>1$, the system may be unstable
and suffer from the exploding gradient problem.

Figure 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.

####  6.3.3 Memory Analysis of MANNs

In slot-based MANNs, memory $M$ is a set of $D$ memory slots. A write at step
$t$ can be represented by the controller’s hidden state $h_{t}$, which
accumulates inputs over several timesteps (i.e., $x_{1}$, …,$x_{t}$). If
another write happens at step $t+k$, the state $h_{t+k}$’s information
containing timesteps $x_{t+1}$, …,$x_{t+k}$ is stored in the memory ($h_{t+k}$
may involves timesteps further to the past, yet they are already stored in the
previous write and can be ignored). During writing, overwriting may happen,
replacing an old write with a new one. Thus after all, $D$ memory slots
associate with $D$ chosen writes of the controller. From these observations,
we can generalise Theorem 6.1 to the case of MANNs having $D$ memory slots
(see Appendix D.5 for proof).

######  Theorem 6.2.

With any $D$ chosen writes at timesteps $1\leq$$K_{1}$$<$ $K_{2}$$<$
…$<$$K_{D}$$<T$, there exist $\lambda,C\in\mathbb{R^{+}}$such that the lower
bound on the average contribution of a sequence of length $T$ with respect to
a MANN having $D$ memory slots can be quantified as the following,

$\displaystyle I_{\lambda}$
$\displaystyle=C\frac{\stackrel{{\scriptstyle[}}{{t}}=1]{K_{1}}{\sum}\lambda^{K_{1}-t}+\stackrel{{\scriptstyle[}}{{t}}=K_{1}+1]{K_{2}}{\sum}\lambda^{K_{2}-t}+...+\stackrel{{\scriptstyle[}}{{t}}=K_{D-1}+1]{K_{D}}{\sum}\lambda^{K_{D}-t}+\stackrel{{\scriptstyle[}}{{t}}=K_{D}+1]{T}{\sum}\lambda^{T-t}}{T}$
$\displaystyle=\frac{C}{T}\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}\stackrel{{\scriptstyle[}}{{j}}=0]{l_{i}-1}{\sum}\lambda^{j}=\frac{C}{T}\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}f_{\lambda}(l_{i})$
(6.6)

where $l_{i}=\begin{cases}K_{1}&;i=1\\\ K_{i}-K_{i-1}&;D\geq i>1\\\
T-K_{D}&;i=D+1\end{cases}$,
$f_{\lambda}\left(x\right)=\begin{cases}\frac{1-\lambda^{x}}{1-\lambda}&\lambda\neq
1\\\ x&\lambda=1\end{cases}$, $\forall x\in\mathbb{R}^{+}$.

If $\lambda\leq 1$, we want to maximise $I_{\lambda}$ to keep the information
from vanishing. On the contrary, if $\lambda>1$, we may want to minimise
$I_{\lambda}$ to prevent the information explosion. As both scenarios share
the same solution (see Appendix D.6), thereafter we assume that $\lambda\leq
1$ holds for other analyses. By taking average over $T$, we are making an
assumption that all timesteps are equally important. This helps simplify the
measurement as $I_{\lambda}$ is independent of the specific position of
writing. Rather, it is a function of the interval lengths between the writes.
This turns out to be an optimisation problem whose solution is stated in the
following theorem.

######  Theorem 6.3.

Given $D$ memory slots, a sequence with length $T$, a decay rate
$0<\lambda\leq 1$, then the optimal intervals
$\left\\{l_{i}\in\mathbb{R^{+}}\right\\}_{i=1}^{D+1}$ satisfying
$T=\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}l_{i}$ such that the lower
bound on the average contribution
$I_{\lambda}=\frac{C}{T}\stackrel{{\scriptstyle[}}{{i}}=1]{D+1}{\sum}f_{\lambda}(l_{i})$
is maximised are

$l_{1}=l_{2}=...=l_{D+1}=\frac{T}{D+1}$ (6.7)

We name the optimal solution as Uniform Writing (UW) and refer to the term
$\frac{T}{D+1}$ and $\frac{D+1}{T}$ as the optimal interval and the
compression ratio, respectively. The proof is given in Appendix D.6.

1:a sequence $x=\left\\{x_{t}\right\\}_{t=1}^{T}$, a cache $C$ sized $L$, a
memory sized $D$.

2:for $t=1,T$ do

3: $C$.append($h_{t-1}$)

4: if $t\bmod L==0$ then

5: Use Eq.(6.10) to calculate $a_{t}$

6: Execute Eq.(6.3): $o_{t}=f_{o}\left(a_{t},r_{t-1},x_{t}\right)$

7: Execute Eq.(6.4): $h_{t}=f_{h}\left(a_{t},r_{t-1},x_{t}\right)$

8: Update the memory using Eq.(6.2)

9: Read $r_{t}$ from the memory using Eq.(6.1)

10: $C$.clear()

11: else

12: Update the controller using Eq.(6.4):
$h_{t}=f_{h}\left(h_{t-1},r_{t-1},x_{t}\right)$

13: Assign $r_{t}=r_{t-1}$

14: end if

15:end for

Algorithm 1 Cached Uniform Writing

###  6.4 Optimal Writing for Slot-based Memory Models

####  6.4.1 Uniform Writing

Uniform writing can apply to any MANNs that support writing operations. Since
the writing intervals are discrete, i.e., $l_{i}\in\mathbb{N^{+}}$, UW is
implemented as the following,

$M_{t}=\begin{cases}f_{w}\left(o_{t},M_{t-1}\right)&\mathrm{if}\>t=\left\lfloor\frac{T}{D+1}\right\rfloor
k,k\in\mathbb{N^{+}}\\\ M_{t-1}&\mathrm{otherwise}\end{cases}$ (6.8)

By following Eq. (6.8), the write intervals are close to the optimal interval
defined in Theorem 6.3 and approximately maximise the average contribution.
This writing policy works well if timesteps are equally important and the task
is to remember all of them to produce outputs (i.e., in copy task). However,
in reality, timesteps are not created equal and a good model may need to
ignore unimportant or noisy timesteps. That is why overwriting in MANN can be
necessary. In the next section, we propose a method that tries to balance
between following the optimal strategy and employing overwriting mechanism as
in current MANNs.

####  6.4.2 Local Optimal Design

To relax the assumptions of Theorem 6.3, we propose two improvements of the
Uniform Writing (UW) strategy. First, the intervals between writes are equal
with length $L$ ($1\leq L\leq\left\lfloor\frac{T}{D+1}\right\rfloor$). If
$L=1$, the strategy becomes regular writing and if
$L=\left\lfloor\frac{T}{D+1}\right\rfloor$, it becomes uniform writing. This
ensures that after $\left\lfloor\frac{T}{L}\right\rfloor$ writes, all memory
slots should be filled and the model has to learn to overwrite. Meanwhile, the
average kept information is still locally maximised every $L*D$ timesteps.

Second, we introduce a cache of size $L$ to store the hidden states of the
controller during a write interval. Instead of using the hidden state at the
writing timestep to update the memory, we perform an attention over the cache
to choose the best representative hidden state. The model will learn to assign
attention weights to the elements in the cache. This mechanism helps the model
consider the importance of each timestep input in the local interval and thus
relax the equal contribution assumption of Theorem 6.3. We name the writing
strategy that uses the two mentioned-above improvements as Cached Uniform
Writing (CUW). An illustration of the writing mechanism is depicted in Fig.
6.1.

####  6.4.3 Local Memory-Augmented Attention Unit

In this subsection, we provide details of the attention mechanism used in our
CUW. To be specific, the best representative hidden state $a_{t}$ is computed
as follows,

$\alpha_{tj}=softmax\left(v^{T}\tanh\left(Wh_{t-1}+Ud_{j}+Vr_{t-1}\right)\right)$
(6.9)

$a_{t}=\stackrel{{\scriptstyle[}}{{j}}=1]{L}{\sum}\alpha_{tj}d_{j}$ (6.10)

where $\alpha_{tj}$ is the attention score between the $t$-th writing step and
the $j$-th element in the cache; $W$, $U$, $V$ and $v$ are parameters; $h$ and
$r$ are the hidden state of the controller and the read-out (Eq. (6.1)),
respectively; $d_{j}$ is the cache element and can be implemented as the
controller’s hidden state ($d_{j}=h_{t-1-L+j}$).

The vector $a_{t}$ will be used to replace the previous hidden state in
updating the controller and memory. The whole process of performing CUW is
summarised in Algo. 1111Source code is available at
https://github.com/thaihungle/UW-DNC.

###  6.5 Experiments and Results

Figure 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.

####  6.5.1 An Ablation Study: Memory-Augmented Neural Networks with and
without Uniform Writing

In this section, we study the impact of uniform writing on MANNs under various
circumstances (different controller types, memory types and number of memory
slots). We restrict the memorisation problem to the double task in which the
models must reconstruct a sequence of integers sampled uniformly from range
$\left[1,10\right]$ twice. We cast this problem to a sequence to sequence
problem with 10 possible outputs per decoding step. The training stops after
10,000 iterations of batch size 64. We choose DNC222Our reimplementation based
on https://github.com/deepmind/dnc and
NTM333https://github.com/MarkPKCollier/NeuralTuringMachine as the two MANNs in
the experiment. The recurrent controllers can be RNN or LSTM. With LSTM
controller, the sequence length is set to 50\. We choose sequence length of 30
to make it easier for the RNN controller to learn the task. The number of
memory slots $D$ is chosen from the set $\left\\{2,4,9,24\right\\}$ and
$\left\\{2,4,9,14\right\\}$ for LSTM and RNN controllers, respectively. More
memory slots will make UW equivalent to the regular writing scheme. For this
experiment, we use Adam optimiser Kingma and Ba (2014) with initial learning
rate and gradient clipping of $\left\\{0.001,0.0001\right\\}$ and