text:
\section{Conversion of FSMs to RNNs}

As an appendix to our main paper, we provide here a variant of a proof that any finite state machine
can be simulated with a recurrent neural net, using neurons as representations of the states. Note that
this is opposed to our simulation via reservoir memory machines, where we use the entire state vector,
and not just a single neuron, as representation of a Moore machine state.

\begin{thm}\label{thm:fsm_to_rnn}
Let $(\states, \inps, \outps, \delta, \rho, q_0)$ be a Moore machine
with $\states = \{1, \ldots, L\}$, $\inps = \{e_1, \ldots, e_m\}$ and $\outps = \{e_1, \ldots, e_K\}$,
where $e_i$ is the $i$th unit basis vector. Further, let $x_1, \ldots, x_T$ be any sequence over $\inps$.
Then, there exists a recurrent neural network $(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0)$ with
$\bm{U} \in \R^{n \times m}$, $\bm{W} \in \R^{n \times n}$, $\bm{V} \in \R^{K \times n}$, $\vec b, \vec h \in \R^n$ and $n = L \cdot (m+1)$.

Further, let $\vec h_t$ be the state and $\vec y_t$ be the output of the recurrent neural net at step $t$
of processing the input sequence $x_1, \vec 0, x_2, \ldots, \vec 0, x_T$ according to Equation~\ref{eq:rnn},
and let $q_t$ be the state and $y_t$ be the output of the Moore machine at step $t$ of processing
the input sequence $x_1, \ldots, x_T$. Then it holds for all $t \in \{1, \ldots, T\}$:
$\vec h_{2t} = e_{q_t}$ and $\vec y_{2t} = y_t$.

\begin{proof}
The idea of our proof is quite simple. Our aim is to set up $\vec h_{2t-1}$ such that
the coordinates $L+1, \ldots, (m+1) \cdot L$ represent the tuple $(q_{t-1}, x_t)$ via one-hot coding,
which then makes it trivial to map $\vec h_{2t-1}$ to $\vec h_{2t} = e_{q_t}$.

In particular, we set the weight matrices $\bm{U}$, $\bm{W}$, and $\bm{V}$ as well as the
bias vector $\vec b$ as follows.
\begin{align*}
w_{k, l} &=
\begin{cases}
1 & \text{if } \lfloor (l-1) / L \rfloor = i, \mod(l, L) = j \text{ and } \delta(e_i, j) = k\\
1 & \text{if } k > L \text{ and } \mod(k, L) = l\\
0 & \text{otherwise}
\end{cases} \\
u_{k, i} &=
\begin{cases}
1 & \text{if } 0 < \lfloor (k-1) / L \rfloor = i \leq m \\
0 & \text{otherwise}
\end{cases} \\
b_k &=
\begin{cases}
-\frac{1}{2} & \text{if } k \leq L\\
-\frac{3}{2} & \text{otherwise}
\end{cases} \\
v_{j, k} &=
\begin{cases}
1 & \text{if } \rho(k) = e_j \\
0 & \text{otherwise}
\end{cases}
\end{align*}
We finally set $\sigma$ as the Heaviside function, i.e.\ $\sigma(x) = 1$ if $x > 0$ and $\sigma(x) = 0$
otherwise, and $\vec h_0$ as $e_{q_0}$. An example of this translation is visualized in Figure~\ref{fig:fsm_to_rnn}
for the Moore machine $(\{1, 2\}, \{e_1, e_2\}, \{e_1, e_2\}, \delta, \rho, 0)$ with $\delta(e_1, 1) = \delta(e_2, 2) = 2$
and $\delta(e_1, 2) = \delta(e_2, 1) = 1$ as well as $\rho(1) = e_1$ and $\rho(2) = e_2$.
An example processing of the input sequence $e_1, e_2, e_2, e_1$ would be processed by
the neural net as shown in Table~\ref{tab:fsm_to_rnn}.

Now, consider the claim $\vec h_{2t} = e_{q_t}$. We prove this claim via induction over $t$.
First, for $t = 0$, the claim holds because we set $\vec h_0 = e_{q_0}$.
Next, consider $t > 0$ and let's inspect the state $\vec h_{2t-1}$.
We wish to show that $h_{2t-1, k} = 1$ if $e_{\lfloor (k-1) / L \rfloor} = x_t$ and
$\mod(k, L) = q_{t-1}$ and $h_{2t-1, k} = 0$ otherwise. Due to induction we know that
$\vec h_{2t-2} = e_{q_{t-1}}$. Hence, we know that the sum $\sum_l w_{k, l} \cdot h_{2t-2, l}$
is $1$ if $k > L$ as well as $\mod(k, L) = q_{t-1}$. In any other case, this sum is zero
because $w_{k, l}$ is otherwise only nonzero if $\lfloor (l-1) / L \rfloor = i$, which only
occurs if $l > L$, but all coordinates $h_{2t-2, l}$ for $l > L$ are zero.

Further, we know that the sum $\sum_i u_{k, i} \cdot x_{t, i}$ is $1$ if there exists
an $i \in \{1, \ldots, m\}$ such that $\lfloor (k-1) / L \rfloor = i$ and $e_i = x_t$.
Otherwise, the sum is zero. Plugging these results together we obtain that the sum
$\sum_l w_{k, l} \cdot h_{2t-2, l} + \sum_i u_{k, i} \cdot x_{t, i}$ is zero if $k \leq L$,
is $1$ if $k > L$ and either $\mod(k, L) = q_{t-1}$ or $\lfloor (k-1) / L \rfloor = i$,
but not both, and is $2$ if both $\mod(k, L) = q_{t-1}$ and $\lfloor (k-1) / L \rfloor = i$.
Combining this with the definition of $b_k$ and the Heaviside function, we obtain
indeed that $h_{2t-1, k} = 1$ if $e_{\lfloor (k-1) / L \rfloor} = x_t$ and
$\mod(k, L) = q_{t-1}$ and $h_{2t-1, k} = 0$ otherwise.

Now, consider the coordinate $h_{2t, q_t}$. This coordinate must be one because the
term $w_{q_t, L \cdot i + q_{t-1}} \cdot h_{2t-1, L \cdot i + q_{t-1}}$ for $e_i = x_t$
is $1$ and, hence, the sum $\sum_l w_{q_t, l} \cdot h_{2t-1, l} - \frac{1}{2}$ is positive.
For all other coordinates $k$, note that the conditions
$\lfloor (l-1) / L \rfloor = i, \mod(l, L) = j \text{ and } \delta(e_i, j) = k$ do not hold
and that all coordinates $h_{2t-1, l}$ for $l \leq L$ are zero. Hence, the sum
$\sum_l w_{k, l} \cdot h_{2t-1, l} - b_k$ for all $k \neq q_t$ is negative.
This concludes the proof by induction.

Once this result is established, showing that $\vec y_{2t} = y_t$ is straightforward.
We simply notice that $y_t = \rho(q_t)$ and $\vec y_{2t} = \bm{V} \cdot \vec h_{2t}
= \bm{V} \cdot e_{q_t}$, such that the sum $\sum_k v_{j, k} \cdot h_{2t, k}$ is $1$
if $k = q_t$ and $\rho(k) = e_j$ and zero otherwise, which concludes the proof.´
\end{proof}
\end{thm}

\begin{figure}
\begin{center}
\begin{tikzpicture}[>=stealth']

\begin{scope}
\node at (0,2) {Moore Machine};

\node[state,initial]   (q0) at (-2,0) {$1$};
\node[state,accepting] (q1) at (+2,0) {$2$};

\path[->]
(q0) edge[bend left]  node[above] {$e_1$} (q1)
(q0) edge[loop above] node[above] {$e_2$} (q0)
(q1) edge[bend left]  node[below] {$e_1$} (q0)
(q1) edge[loop above] node[above] {$e_2$} (q1);

\end{scope}

\begin{scope}[shift={(-2.25,-4)}]
\node at (2.25,2.5) {Recurrent neural net};

\node[state] (x1) at (0,+1) {$x_1$};
\node[state] (x2) at (0,-1) {$x_2$};

\node[state, inner sep=0pt] (h1) at (3.5,+1) {$h_1|\frac{1}{2}$};
\node[state, inner sep=0pt] (h2) at (3.5,-1) {$h_2|\frac{1}{2}$};
\node[state, inner sep=0pt] (h3) at (1.5,+1.5) {$h_3|\frac{3}{2}$};
\node[state, inner sep=0pt] (h4) at (1.5,+0.5) {$h_4|\frac{3}{2}$};
\node[state, inner sep=0pt] (h5) at (1.5,-0.5) {$h_5|\frac{3}{2}$};
\node[state, inner sep=0pt] (h6) at (1.5,-1.5) {$h_6|\frac{3}{2}$};

\node[state] (y1) at (5,+1) {$y_1$};
\node[state] (y2) at (5,-1) {$y_2$};

\node (U) at (0.75,2) {$\bm{U}$};
\node (W) at (2.5,2)  {$\bm{W}$};
\node (V) at (4.25,2)    {$\bm{V}$};

\path[->]
(x1) edge (h3) edge (h4)
(x2) edge (h5) edge (h6)
(h1) edge (h3) edge[bend left=5] (h5) edge (y1)
(h2) edge (h4) edge[bend left=5] (h6) edge (y2)
(h3) edge (h2)
(h4) edge (h1)
(h5) edge[bend left=5] (h1)
(h6) edge[bend left=5] (h2);

\end{scope}

\end{tikzpicture}
\end{center}
\caption{An example for the translation from a Moore machine (top) to a recurrent neural network
(bottom). For simplicity, weight values are not denotes because all weights are $1$.
The negative bias value for each neuron is denoted after a vertical bar.}
\label{fig:fsm_to_rnn}
\end{figure}

\begin{table*}
\caption{The processing of the example sequence $e_1, e_2, e_2, e_1$ via the recurrent neural
network shown in Figure~\ref{fig:fsm_to_rnn}. Note that the input symbol at time $t$ is
put into the network at time $2t$.}
\label{tab:fsm_to_rnn}
\begin{center}
\begin{tabular}{cccccccccc}
$t$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$& $8$ \\
\cmidrule(lr){1-1} \cmidrule(lr){2-10}
$\vec x_t$ & - &
$\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ \\
$\vec h_t$ &
$\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$ \\
$\vec y_t$ & - &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ &
$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ &
$\begin{pmatrix} 1 \\ 0 \end{pmatrix}$
\end{tabular}
\end{center}
\end{table*}

\end{appendix}

\end{document}

\section{Introduction}

\IEEEPARstart{D}{ifferentiable} neural computers (DNCs) are artificial neural networks that
combine a recurrent neural network controller with an external memory to store
information without interference over long stretches of time \cite{NTM}. Such networks have
achieved impressive successes in recent years, solving tasks such as storing inputs
losslessly, performing associative memory recalls, up to question-answering and graph
traversal \cite{DNCMDS,NTM,MANN,Pushdown}. However, DNCs are difficult to train, typically
requiring several ten thousand input sequences until convergence \cite{NTM_impl}.
In this work, we propose a model that can be trained with simple convex optimization
techniques and little data, but still retains a lot of the capabilities of DNCs.
The only sacrifice we need to make for these advantages is that examples of viable memory
access behavior need to be provided as part of the training data.

Architecturally, our proposed model is an echo state network \cite{ESN}
with an explicit external memory to which access is controlled by a convex classifier -
in our case a support vector machine. We show in this work that this external memory
enhances the computational capabilities of echo state machines from strictly less than finite
state machines \cite{DMM} to strictly more than finite state machines. More generally, we
obtain a model with lossless memory over arbitrarily long time spans, which extends beyond the
abilities of high but finite capacity memory reservoirs in recent works \cite{MemCap,DeepESN,LMU}.

Finally, our work is an extension of our first version of reservoir memory machines \cite{RMM}.
In particular, we simplify the architecture by merging read and write behavior into a single
classifier, thus making it easier to implement and to train, and we provide a novel model
variant that can solve associative recall tasks, which was beyond the old version. As we
will see in the experiments, a key reason why these changes work is that we now use a
reservoir that can losslessly recall past input states over long stretches of time, namely the
Legendre delay network \cite{LMU}.

In summary, our contributions in this paper are:
\begin{itemize}
\item A novel reservoir neural network architecture - namely reservoir memory machines (RMMs) - which
is equipped with an external memory but can still be trained using convex optimization,
\item a proof that RMMs are strictly more powerful than finite state machines, and
\item a series of experiments that demonstrate that RMMs can solve many benchmark tasks for differentiable
neural computers that are beyond the abilities of standard recurrent models (including deep ones).
\end{itemize}

\section{Background and Related Work}

\subsection{Differentiable Neural Computers}

The original authors define a differentiable neural computer (DNC) as 'a neural network that can
read from and write to an external memory matrix, analogous to the random-access memory in a
conventional computer' \cite{NTM}.
The mechanism to read from and write to memory is typically content-based,
i.e.\ the controller writes to and reads from locations that are similar to a query vector produced
by the controller \cite{NTM}. However, not all memory accesses in computing tasks can be implemented
in a content-based fashion. Therefore, the model is extended with a linking matrix that connects
subsequent write locations in memory and can thus be used during reading to move spatially
in the memory \cite{NTM}. While reviewing the full breadth and depth of neural computing history is
beyond the scope of this paper, we wish to note at least that many variations of this basic setup
exist, such as additional sharpening operations and more effective initialization schemes \cite{DNCMDS,NTM_impl}.
Further, we note the long history of neural computing approaches, going
back at least to the neural pushdown automaton models of \cite{Pushdown}.

Instead, our aim in this work is to develop a network that is as easy to train as possible
while still retaining some of the computational power of DNCs. In particular, we suggest the
following changes.
First, we observe that most benchmark tasks for DNCs can be solved without content-based addressing,
such that our proposed model rather predicts the memory access location directly. We only use
content-based addressing for the associative recall task, where it is necessary.
Second, after writing something to memory, we do not erase it anymore. This enables us to merge the
write and read head: The first access to a memory location is interpreted as writing, all subsequent
accesses as reading.
Third, all our memory accesses are strict and discrete instead of smooth and differentiable.
This reduces memory access to a straightforward classification problem, provided that training data
for memory access behavior is available. We thus also avoid the need for sharpening operations
as suggested in some DNC works \cite{NTM,DNCMDS}.
Finally, and most prominently, we do not train the system end-to-end but only train the memory
address classifier and the mapping from state to output. This enables training via simple convex
optimization, which thus becomes orders of magnitude faster.

While our simplified model can not be expected to achieve the same computational capabilities
as a full DNC (which aims at emulating Turing machines \cite{NTM_impl}), we can show that
our system is strictly more powerful than finite state machines.

\subsection{Finite State Machines}

We analyze the computational power of our system in comparison to finite state machines (FSMs),
in particular \emph{Moore Machines} \cite{FSM}. We define a Moore machine as a $6$-tuple
$(\states, \inps, \outps, \delta, \rho, q_0)$, where $\states$ is a finite set called \emph{states}, $\inps$
is a finite set called \emph{input alphabet}, $\outps$ is a finite set called \emph{output alphabet},
$\delta : \inps \times \states \to \states$ is called the \emph{state transition function}, $\rho : \states \to \outps$ is
called the \emph{output function} and $q_0 \in \states$ is called the \emph{start state}. A Moore machine
transforms an input sequence $x_1, \ldots, x_T \in \inps$ to an output sequence
$y_1, \ldots, y_T \in \outps$ via the dynamical system $q_t = \delta(x_t, q_{t-1})$ and
$y_t = \rho(q_t)$ for all $t \in \{1, \ldots, T\}$. We note in passing that Moore machines are a strict
generalization of finite state automata which can be seen as Moore Machines with the output
alphabet $\outps = \{0, 1\}$ where $\rho(q) = 1$ if $q$ is an accepting state and $\rho(q) = 0$ otherwise.
By virtue of this mechanism, a Moore machine can recognize any regular/Chomsky-3 language \cite{TheoInf}.

\subsection{Relationship of recurrent neural networks and finite state machines}
\label{sec:rnns}

Finite state machines are a particularly interesting model for comparison because their dynamics
are very similar to recurrent neural networks. In more detail, we define a \emph{recurrent neural network}
as a $6$-tuple $(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0)$
of matrices $\bm{U} \in \R^{n \times m}$, $\bm{W} \in \R^{n \times n}$, and $\bm{V} \in \R^{K \times n}$,
as well as a bias vector $\vec b \in \R^n$, some function $\sigma : \R \to \R$, and an initial state $\vec h_0 \in \R^n$
(typically the zero vector). The system dynamics is then defined as follows.
\begin{align}
\vec h_t = &\rec(\vec x_t, h_t) = \sigma\Big(\bm{U} \cdot \vec x_t + \bm{W} \cdot \vec h_{t-1} + \vec b \Big), \notag \\
\vec y_t = &\out(\vec h_t) = \bm{V} \cdot \vec h_t, \label{eq:rnn}
\end{align}
where $\sigma$ is applied element-wise. This has the same Markovian structure as a Moore machine
with $\rec$ being related to $\delta$ and $\out$ to $\rho$. Indeed, it is well known that recurrent
neural network can implement any finite state machine via a correspondence of neurons and
states \cite{Neurautomata}. Indeed, the computational power of recurrent nets goes far beyond finite
state machines. By carefully selecting the weights, a recurrent neural network even with rational-valued
weights can simulate a full Turing machine \cite{RecTuring}.
However, if we limit our network to \emph{small weights}, i.e.\ $\bm{W}$ is a contractive map,
the computational power is reduced below finite state machines because the state information will be
lost over time \cite{DMM}. This applies in particular to reservoir neural networks.

\subsection{Reservoir neural networks and their computational limits}

We define a reservoir as a $5$-tuple $(\bm{U}, \bm{W}, \vec b, \sigma, \vec h_0)$
with $\bm{U} \in \R^{n \times m}$, $\bm{W} \in \R^{n \times n}$, $\vec b \in \R^n$, $\sigma : \R \to \R$
and $\vec h_0 \in \R^n$ which has the same dynamics as in Equation~\ref{eq:rnn} but where
$\rec$ ensures the \emph{echo state property}, i.e.\ that the initial state $\vec h_0$ washes out
over time \cite{ESN,EchoStateProperty}.
This property is key to ensure that the state always reacts to the input instead of degenerating to
a stable fix point \cite{ESN} and is typically achieved by designing $\rec$ as a contractive map \cite{MarkovESN}. However, $\rec$ being contractive implies that any recurrent neural network based
on a reservoir is computationally strictly less powerful than a finite state machine \cite{DMM}.
It is yet unclear whether reservoirs at the edge of chaos \cite{MemCap,DeepESN,MarkovESN,EdgeChaos}
extend this capability.

The core motivation for using reservoirs is that they provide a rich representation of
short-term dynamics in the input time series without having to adjust the
matrices $\bm{U}$ or $\bm{W}$ in any way \cite{ESN,MarkovESN,Universality}.
Accordingly, one can leave all reservoir parameters as-is and still obtain a well-performing recurrent
neural net by simply optimizing the matrix $\bm{V}$ via linear regression \cite{ESN,MarkovESN,Traffic}.
We call such a recurrent neural network an echo-state network \cite[ESN]{ESN}.
In this work, we use the same basic strategy - combining a fixed reservoir with an easy-to-train output
layer - but we extend an echo state network with an explicit memory from which we can recall past
reservoir states.
Strictly speaking, this violates the echo state property, because we can also recall the initial state.
However, this violation is controlled, because a recall only occurs if a trained classifier says so.
This controlled violation also raises the computational power beyond finite state machines.

Our proposed model is an extension of a prior version of reservoir memory machines \cite{RMM}, where
the model stores past inputs that align well with the output sequence. In our current work,
we store reservoir states instead of past inputs, such that a single memory entry can summarize a long
stretch of past inputs. To ensure that we do not lose the input information we also
propose to use Legendre delay networks as reservoirs which support the lossless reconstruction
of inputs from reservoir states \cite{LMU}.
We further replace the alignment mechanism with an additional teaching input
channel which the user can use to specify when data should be stored or read for the training data.
Finally, we simplify the architecture by merging read and write heads into a single
state classifier (except for the associative recall task), thus simplifying training.

\section{Method}

In this section we describe our main contribution. In particular, we introduce two mechanisms to
extend an echo state network with external memory, prove that this extension suffices to
raise the computational power beyond finite state machines, and provide training algorithms
for both mechanisms.
The first mechanism implements address-based memory with a shared read and write head,
whereas the second mechanism implements associative memory with separate read and write heads.
We use the first mechanism for most of our experimental tasks and the second only for the
associative recall task.

\subsection{Standard Reservoir Memory Machines}

We define a standard reservoir memory machine (RMM) as an $8$-tuple
$(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0, \states, \cls)$, where
$(\bm{U}, \bm{W}, \vec b, \sigma, \vec h_0)$ is a reservoir with $m$ inputs and $n$ neurons,
$\states = \{0, \ldots, L\}$ for $L \in \N$ is a finite set which we call the
\emph{address set}, and where $\cls : \R^n \to \states$ is a classifier, mapping the continuous
reservoir state to a memory address.
The idea behind our RMM architecture is to maintain the usual
recurrent neural network dynamic as long as $\cls$ outputs the zero address, write to the
memory whenever a nonzero address is selected the first time, and read from memory whenever
a nonzero address is selected a subsequent time.

In more detail, we adjust the system dynamics from Equation~\ref{eq:rnn} as follows,
where $\vec m_{t, l}$ denotes the $l$th memory entry at time $t$.
\begin{align}
\tilde h_t &= \rec(\vec x_t, \vec h_{t-1}) = \sigma\Big(\bm{U} \cdot \vec x_t + \bm{W} \cdot \vec h_{t-1} + \vec b \Big), \notag \\
a_t &= \cls(\tilde h_t) \notag \\
\vec m_{t, l} &= \begin{cases}
\tilde h_t & \text{if } l = a_t \text{ and } \vec m_{t-1, l} = \vec 0 \\
\vec m_{t-1, l} \, & \text{otherwise}
\end{cases} \notag \\
\vec h_t &= \begin{cases}
\tilde h_t & \text{if } a_t = 0 \\
\vec m_{t, a_t} & \text{otherwise}
\end{cases} \label{eq:rmm}
\end{align}
where all memory entries are initialized as $\vec m_{0, l} = \vec 0$, except if $\cls(\vec h_0) > 0$.
In that case, $\vec m_{0, \cls(\vec h_0)} = \vec h_0$.

\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{point}=[circle, fill=skyblue1, draw=skyblue3, semithick, inner sep=0.07cm]

\draw[fill=skyblue1,draw=none, opacity=0.4] (-2,2) -- (-0.5,2) -- (2,-1) -- (2,-2) -- (-2,-2) -- cycle;
\draw[fill=orange1,draw=none, opacity=0.4] (-0.5,2) -- (2,-1) -- (2,2) -- cycle;

\node[skyblue3, right] at (-2,-1.5) {address 0};
\node[orange3, right]  at (1.2,1) {address 1};

\draw[semithick, ->, >=stealth'] (-2,-2) -- (-2,2);
\draw[semithick, ->, >=stealth'] (-2,-2) -- (2,-2);
\draw[semithick] (-2,0) -- (-1.9,0);
\draw[semithick] (0,-2) -- (0,-1.9);
\node[left] at (-2,0) {$0$};
\node[below] at (0,-2) {$0$};

\node[above] at (0,2) {state space};

\node[point] (h0) at (0,0)     [label={[skyblue3]above:$\vec h_0$}] {};
\node[point] (h1) at (60:0.7)  [label={[skyblue3]right:$\vec h_1$}] {};
\node[point, draw=orange3, fill=orange1] (h2) at (80:1.5)  [label={[orange3]right:{$\vec h_2 =: \vec h_8$}}] {};
\node[point] (h3) at (120:1.4) [label={[skyblue3]above:$\vec h_3$}] {};
\node[point] (h4) at (160:1.3) [label={[skyblue3]left:$\vec h_4$}] {};
\node[point] (h5) at (220:1.1) [label={[skyblue3]left:$\vec h_5$}] {};
\node[point] (h6) at (270:0.8) [label={[skyblue3]below:$\vec h_6$}] {};
\node[point] (h7) at (330:0.9) [label={[skyblue3]below:$\vec h_7$}] {};
\node[point, draw=orange3, fill=orange1] (h8) at (5:1.2)  [label={[orange3]right:$\tilde h_8$}] {};

\path[thick, skyblue3, ->, >=stealth', fill=skyblue1]
(h0) edge (h1)
(h1) edge (h2)
(h2) edge (h3)
(h3) edge (h4)
(h4) edge (h5)
(h5) edge (h6)
(h6) edge (h7)
(h7) edge (h8)
(h8) edge[orange3, dashed, bend right=20] (h2);

\end{tikzpicture}
\end{center}
\caption{An illustration of the reservoir memory machine dynamics. The first time the continuous
state $\vec h_t$ crosses into the receptive field of a memory address $a_t > 0$ (orange
region), it is stored in memory. Whenever the continuous state re-enters this receptive field, the
stored state is recovered (here, for example $\vec h_8 = \vec h_2$).}
\label{fig:state_space}
\end{figure}

A sketch of the system dynamic is provided in Figure~\ref{fig:state_space}.
The reservoir memory machine behaves like a regular reservoir neural network until the classifier
$\cls$ outputs a nonzero memory address. In that case, we record the current state $\vec h_t$ in memory,
which we recover whenever $\cls$ outputs the same memory address another time (here in time step $8$, where we recover $\vec h_8 = \vec h_2$).
Note that this is a strict generalization over a standard recurrent neural network
because we recover Equation~\ref{eq:rnn} by setting $\cls$ to be zero at all times.

\subsection{Computational Power}

In this section we analyze the computational power of our model in more detail.
We first introduce the notion of cycles both in a Moore machine and in a RMM. Then we show
that the state of a RMM resulting from any sequence is equivalent to the state resulting from
its cycle-free version, which in turn implies our main result, namely that reservoir memory machines
can implement any finite state machine. We will further show that there exist tasks for which
reservoir memory machines need exponentially less memory compared to finite state machines.

\begin{dfn}[Cycles]\label{dfn:cycles}
Given a Moore machine $\mathcal{A}$ and an input sequence $x_1, \ldots, x_T \in \inps$, we define an
\emph{$\mathcal{A}$-cycle} as a subsequence $x_{t'}, \ldots, x_t$ where $0 \leq t' < t \leq T$ and
$q_{t'} = q_t$.

Similarly, given a RMM $\mathcal{M}$ and an input sequence $\vec x_1, \ldots, x_T \in \inps$,
we define a \emph{$\mathcal{M}$-cycle} as a subsequence $x_{t'}, \ldots, x_t$ where
$0 \leq t' < t \leq T$ and $a_{t'} = a_t > 0$ (with $a_0 := \cls(\vec h_0)$). Further, we define the
\emph{$\mathcal{M}$-cycle-reduced version} of $x_1, \ldots, x_T$ as the result of the following
recursive procedure: Identify the largest $t$ such that there exists a $t'$
with $\vec x_{t'}, \ldots, \vec x_t$ being a $\mathcal{M}$-cycle. If no such $t$ exists, return
the sequence itself. Otherwise, take the lowest such $t'$ and return the $\mathcal{M}$-cycle-reduced
version of $\vec x_1, \ldots, \vec x_{t'}, \vec x_{t+1}, \ldots \vec x_T$.
\end{dfn}

As an example, consider Figure~\ref{fig:state_space}. There, $\vec x_2, \ldots, \vec x_8$ is a
$\mathcal{M}$-cycle because $a_2 = a_8 = 1 > 0$. The cycle-reduced version of the sequence would
be $\vec x_1, \vec x_2$.

\begin{lma}\label{lma:states}
Let $\mathcal{M}$ be a RMM, let $\vec x_1, \ldots, \vec x_T \in \inps$, and let
$\vec x'_1, \ldots, \vec x'_\tau \in \inps$ be its $\mathcal{M}$-cycle reduced version.
Then, $\vec h_T = \vec h'_\tau$, i.e.\ the final states for both input sequences are the same.

\begin{proof}
We prove this statement via an induction over the number of cycles in $\vec x_1, \ldots, \vec x_T$.
First, assume that $\vec x_1, \ldots, \vec x_T$ contains no cycles. Then, the claim holds trivially
because the sequence is equal to its cycle-reduced version.

Second, assume that $\vec x_1, \ldots, \vec x_T$ contains at least one cycle and let
$\vec x_{t'}, \ldots, \vec x_t$ be the cycle with largest $t$ and smallest $t'$, i.e.\ the first
cycle that would be removed in Definition~\ref{dfn:cycles}.
Then, consider the sequence $\vec x_1, \ldots, \vec x_{t'}$ and let
$\vec x'_1, \ldots, \vec x'_\tau$ be its cycle-reduced version. Because
$\vec x_1, \ldots, \vec x_{t'}$ contains at least one cycle less than $\vec x_1, \ldots, \vec x_T$,
it follows by induction that $\vec h_{t'} = \vec h'_\tau$. Further, because $a_{t'} = a_t$, we
know that the RMM recalls the same state in $t$ as in $t'$, which yields $\vec h_t = \vec h_{t'}
= \vec h'_\tau$. Finally, we know that $\vec x_{t+1}, \ldots \vec x_T$ does not add any cycles,
otherwise $t$ would not have been maximal. Therefore, $\vec x'_1, \ldots, \vec x'_\tau, \vec x'_{\tau+1}, \ldots, \vec x'_{\tau+T-t}$ with $\vec x'_{\tau+1}, \ldots, \vec x'_{\tau+T-t}
= \vec x_{t+1}, \ldots, \vec x_T$ is exactly the cycle-reduced version of $\vec x_1, \ldots, \vec x_T$ and we
obtain $\vec h_T = \vec h'_{\tau + T - t}$ as desired. This concludes the proof.
\end{proof}
\end{lma}

Now follows our main result regarding the computational power of RMMs.

\begin{thm}\label{thm:fsm}
Let $\mathcal{A} = (\states, \inps, \outps, \delta, \rho, q_0)$ be a Moore machine with
$\states = \{1, \ldots, L\}$. Then, for any reservoir $(\bm{U}, \bm{W}, \vec b, \sigma, \vec h_0)$
that can linearly separate any two subset of input sequences up to length $|\states|$,
there exists a reservoir memory machine $\mathcal{M} = (\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0, \states, \cls)$
such that in each time step the memory address of the RMM is equal to the state of
the Moore machine and the output of the RMM can mapped to the output of the
Moore machine.
\begin{proof}
First, without loss of generality, assume that $\inps = \{e_1, \ldots, e_m\}$, i.e.\ the
$m$-dimensional unit basis for some $m$, otherwise code $\inps$ via one-hot coding first.
Further, assume that $\outps = \{1, \ldots, K\}$ for some $K$, otherwise enumerate $\outps$ in
some arbitrary order.

Second, we introduce two auxiliary functions which compute the state of $\mathcal{A}$ and
$\mathcal{M}$ respectively, in particular: $\Delta(x_1, \ldots, x_T) := \delta(x_T, \Delta(x_1, \ldots, x_{T-1}))$
with $\Delta(\varepsilon) = q_0$ and $F(x_1, \ldots, x_T) = \sigma(\bm{U} \cdot x_T + \bm{W}
\cdot F(x_1, \ldots, x_{T-1}) + \vec b)$ with $F(\varepsilon) = \vec h_0$.

Next, we define two auxiliary sets, namely a) the set $\mathcal{X}_0(q)$ of all sequences
$x_1, \ldots, x_T$ with $\Delta(x_1, \ldots, x_T) = q$ which contain no $\mathcal{A}$-cycle,
and b) the set $\mathcal{X}_1(q)$ of all sequences $x_1, \ldots, x_T$ with
$\Delta(x_1, \ldots, x_T) = q$ where $x_1, \ldots, x_{T-1}$ contains no $\mathcal{A}$-cycle
but there exists some $t < T$ such that $\Delta(x_1, \ldots, x_t) = q$, i.e.\ the sequence
contains exactly one cycle that ends in $T$. Note that $T \leq |\states|$, otherwise
$x_1, \ldots, x_{T-1}$ would contain a cycle.

Now, consider the set $\mathcal{H}(q) =
\{ F(\bar x) | \bar x \in \mathcal{X}_0(q) \cup \mathcal{X}_1(q)\}$, i.e.\ the set of all
states $\vec h$ that result from putting a sequence from $\mathcal{X}_0(q)$ or
$\mathcal{X}_1(q)$ into the reservoir. Because we required that any subset of input
sequences up to length $|\states|$ can be linearly separated by its state,
we can efficiently construct a classifier $\cls$ that can map any $\vec h \in \mathcal{H}(q)$
to $q$ for all $q$.

We next show via induction over the number of $\mathcal{A}$-cycles that this classifier suffices
to ensure the equality of Moore machine state and memory address in the RMM for \emph{any}
input sequence. First let $x_1, \ldots, x_T \in \inps^*$ be $\mathcal{A}$-cycle free. Then,
$q_t = a_t$ follows immediately from our classifier construction above. Now, assume that
$x_1, \ldots, x_T$ contains at least one $\mathcal{A}$-cycle and let $x_r, \ldots, x_s$ with
$r < s$ be the $\mathcal{A}$-cycle with largest $s$ and smallest $r$.
Because $x_1, \ldots, x_{s-1}$ contains at least one $\mathcal{A}$-cycle less than before,
we know by induction that $q_t = a_t$ for $t < s$. Accordingly, the equality also holds for
the $\mathcal{M}$-cycle reduced version $x'_1, \ldots, x'_\tau$ of $x_1, \ldots, x_{s-1}$,
which hence implies that $x'_1, \ldots, x'_\tau$ is also $\mathcal{A}$-cycle free.
Now, consider the sequence $x'_1, \ldots, x'_\tau, x_s$. Since $x'_1, \ldots, x'_\tau$
is $\mathcal{A}$-cycle free, $x'_1, \ldots, x'_\tau, x_s$ must lie either in $\mathcal{X}_0(q)$
or $\mathcal{X}_1(q)$ for some $q$. Accordingly, our classifier construction
ensures that $q_s = q'_{\tau+1} = a'_{\tau+1}$. Further, thanks to Lemma~\ref{lma:states}, we know
that the state $\vec h'_\tau$ is equal to $\vec h_{s-1}$, which in turn implies that
$a'_{\tau+1} = a_s$.
Next, because $x_{s+1}, \ldots, x_T$ adds no $\mathcal{A}$-cycles
(otherwise $s$ would not have been maximal), $x'_1, \ldots, x'_\tau, x_{s+1}, \ldots, x_T$ is
$\mathcal{A}$-cycle free, which means that our classifier construction ensures
that the states $q_{s+t} = q'_{\tau+t} = a'_{\tau+t}$ for all $t \in \{1, \ldots, T-s\}$.
Lemma~\ref{lma:states} then yields $a'_{\tau+t} = a_{s+t}$, which concludes our proof by induction.

Finally, consider the sets $\mathcal{G}(y) = \{ F(\bar x) |
\exists q \in \states : \rho(q) = y, \bar x \in \mathcal{X}_0(q)\}$. In other words,
$\mathcal{G}(y)$ covers the states $\vec h_t$ of the reservoir memory machine that occur if the Moore
machine would output $y$. Because we required that the reservoir is
expressive enough to linearly separate any subset of input sequences up to length $|\states|$,
we know that there must exist a matrix $\bm{V} \in \R^{K \times n}$ and some vector $\vec \theta \in \R^K$
such that $\out_k(\vec h_t) = \vec v_k \cdot \vec h_t - \theta_k$ is a function that is larger zero
if and only if $\vec h_t \in \mathcal{G}(k)$ for all $k \in \Gamma$. Accordingly, we can map
$\vec y_t = \bm{V} \cdot \vec h_t$ to $y_t$ via the function $\arg\max_k y_{t, k} - \theta_k$.

Furthermore, this construction suffices to ensure the correct output for \emph{any} input sequence
$x_1, \ldots, x_T$. In particular, Lemma~\ref{lma:states} guarantees that the state $\vec h_T$ is
the same as the state $F(x'_1, \ldots, x'_\tau)$ where $x'_1, \ldots, x'_\tau$ is the
$\mathcal{M}$-cycle free version of $x_1, \ldots, x_T$. Further, because $q'_t = a'_t$ for all
$t \in \{1, \ldots, \tau\}$, $x'_1, \ldots, x'_\tau$ is also $\mathcal{A}$-cycle free, which
ensures that $x'_1, \ldots, x'_\tau \in \mathcal{X}_0(q'_\tau)$ and, hence, $\vec h_T
= F(x'_1, \ldots, x'_\tau) \in \mathcal{G}(y_T)$. This, finally, implies that
$\arg\max_k y_{T, k} - \theta_k = y_T$, which concludes the proof.
\end{proof}
\end{thm}

We note in passing that the linear separability requirement on the reservoir can be relaxed if we
permit a nonlinear classifier for $\cls$ and nonlinear regression for the output function.

We have now shown that RMMs are at least as powerful as finite state machines. We now proceed
to show that RMMs are strictly more powerful because they can solve some tasks with linear
memory size and reservoir size for which a finite state machine would require exponentially or
infinitely many states.

\begin{thm}\label{thm:copy}
Let $\inps \subset \R^m$ be a finite set with $\vec 0 \in \inps$. We define the copy task as follows:
For any input sequence $x_1, \ldots, x_T, \vec 0, \ldots, \vec 0$ with
$x_1, \ldots, x_T \neq \vec 0$ and $T$ zero vectors at the end we define the
desired output sequence $x_1, \ldots, x_T, x_1, \ldots, x_T$, i.e.\ the input is copied once.
It holds: a) For any reservoir $(\bm{U}, \bm{W}, \vec b, \sigma, \vec h_0)$
that is rich enough to linearly extract the current time step up to $T$ as well as the current input
there exists a reservoir memory machine $(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0, \states, \cls)$
with $|\states| = T$ that solves the copy task. b) Any Moore machine that solves the copy
task has at least $|\inps|^T$ states
\begin{proof}
a) To construct the RMM, let $\cls$ a function which maps the current state $\vec h_t$ to $t$ for
$t \leq T$ and maps the first $\vec 0$ vector to $1$. This is possible because we required our
reservoir to be rich enough to represent time steps up to $T$ as well as the current input.
Accordingly, we obtain the state sequence $1, \ldots, T, 1$ for the first $T+1$ states. Since
$q_{T+1} = 1$, we obtain $\vec h_{T+1} = \vec h_1$. This in turn implies $c(\tilde h_{T+2})
= c(\tilde h_2) = 2$, and so on, which yields the overall state sequence
$1, \ldots, T, 1, \ldots, T$. Further, since we required the reservoir to be rich enough to
linearly extract the current input, there exists a matrix $\bm{V}$ such that $\vec y_t =
\bm{V} \cdot \vec h_t = x_t$ and, by extension, $\vec y_{t+T} = \bm{V} \cdot \vec h_{t+T}
= \bm{V} \cdot \vec h_t = x_t$ for all $t \in \{1, \ldots, T\}$.

b) Assume there exists a Moore machine with less than $|\inps|^T$ that solves the copy task.
Because there are $|\inps|^T$ different sequences of length $T$ over $\inps$, there must thus
exist two sequences $x_1, \ldots, x_T \neq x'_1, \ldots, x'_T$ over $\inps$ which lead to the
same state. Accordingly, if we now input $T$ zeros, the output of the Moore Machine
will be the same as well, which is incorrect for at least one of the two sequences.
\end{proof}
\end{thm}

By extending $\Sigma$ to an infinite set, the same construction yields that no Moore machine
can solve the copy task, whereas an RMM still can.

\subsection{Associative Memory}

To implement associative memory we need to separate write and read access again.
Roughly speaking, we change $\cls$ to a binary classifier that only decides whether we want
to write to memory or not, and we read from memory whenever a) we don't write to it and b) the
current state is similar enough to some state stored in memory.
More precisely, we define an associative RMM (aRMM) as a $11$-tuple
$(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0, Q, \cls, \phi, \psi, \theta)$ where
$(\bm{U}, \bm{W}, \vec b, \sigma, \vec h_0)$ is a reservoir with $n$ neurons as before,
$Q = \{1, \ldots, L\}$ is an address set as before, $\cls : \R^n \to \{0, 1\}$ is now a binary classifier
which we call the write head, $\theta \in \R^+$ is a threshold and $\phi : \R^n \to \R^d$ as well as
$\psi : \R^n \to \R^d$ are auxiliary mappings into some latent space in which we measure distance for
the purpose of association. In particular, the aRMM dynamic is:
\begin{align}
\tilde h_t &= \rec(\vec x_t, \vec h_{t-1}) = \sigma\Big(\bm{U} \cdot \vec x_t + \bm{W} \cdot \vec h_{t-1} + \vec b \Big), \notag \\
a_t &= a_{t-1} + \cls(\tilde h_t) \notag \\
\vec m_{t, l} &= \begin{cases}
\tilde h_t & \text{if } l = a_t \text{ and } \cls(\tilde h_t) = 1 \\
\vec m_{t-1, l} \, & \text{otherwise}
\end{cases} \notag \\
\vec h_t &= \begin{cases}
\tilde h_t & \text{if } \cls(\tilde h_t) = 1 \text{ or } \forall l: d_{t, l}^2 > \theta  \\
\vec m_{t, l^*} & \text{otherwise, with } l^* = \arg\min_l d_{t, l}^2
\end{cases}\notag \\
d_{t, l}^2 &= \lVert \phi(\tilde h_t) - \psi(\vec m_{t, l}) \rVert^2  \label{eq:rmm_assoc}
\end{align}
where all $\vec m_{0, l} = \vec 0$ and $a_0 = 0$. Note that, once the memory is full,
additional writes are ignored.

\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{point}=[circle, fill=skyblue1, draw=skyblue3, semithick, inner sep=0.07cm]

\begin{scope}[shift={(-2,0)}]

\node[above] at (0,1.5) {state space};

\draw[fill=skyblue1,draw=none, opacity=0.4] (-1.5,1.5) -- (-0.5,1.5) -- (1.5,-1) -- (1.5,-1.5) -- (-1.5,-1.5) -- cycle;
\draw[fill=orange1,draw=none, opacity=0.4] (-0.5,1.5) -- (1.5,-1) -- (1.5,1.5) -- cycle;

\node[skyblue3, right] at (-1.5,-1.2) {don't write to memory};
\node[orange3, right]  at (-0.3,1.3) {write to memory};

\draw[semithick, ->, >=stealth'] (-1.5,-1.5) -- (-1.5,1.5);
\draw[semithick, ->, >=stealth'] (-1.5,-1.5) -- (1.5,-1.5);
\draw[semithick] (-1.5,0) -- (-1.4,0);
\draw[semithick] (0,-1.5) -- (0,-1.4);
\node[left] at (-1.5,0) {$0$};
\node[below] at (0,-1.5) {$0$};

\node[point] (h0) at (0,0) [label={[skyblue3]above:$\vec h_0$}] {};
\node[point, draw=orange3, fill=orange1] (h1) at (20:0.8) [label={[orange3]right:{$\vec h_1 = \vec h_5$}}] {};
\node[point, draw=orange3, fill=orange1] (h2) at (60:1)  [label={[orange3]right:{$\vec h_2$}}] {};
\node[point] (h3) at (120:1) [label={[skyblue3]above:$\vec h_3$}] {};
\node[point] (h4) at (170:0.9) [label={[skyblue3]left:$\vec h_4$}] {};
\node[point] (h5) at (260:0.7) [label={[skyblue3]left:$\tilde h_5$}] {};

\path[thick, skyblue3, ->, >=stealth', fill=skyblue1]
(h0) edge[orange3] (h1)
(h1) edge[orange3] (h2)
(h2) edge (h3)
(h3) edge (h4)
(h4) edge (h5)
(h5) edge[orange3, dashed, bend right=20] (h1);
\end{scope}

\begin{scope}[shift={(+2.5,0)}]

\node[above] at (0,1.5) {latent space};

\draw[fill=skyblue1,draw=none, opacity=0.4] (-1.5,-1.5) rectangle (1.5,1.5);

\draw[fill=white, draw=none] (1,0.5) circle (0.7);
\draw[fill=orange1, opacity=0.4, draw=none] (1,0.5) circle (0.7);
\draw[fill=white, draw=none] (-0.8,-0.8) circle (0.7);
\draw[fill=orange1, opacity=0.4, draw=none] (-0.8,-0.8) circle (0.7);
\draw[fill=white, draw=none] (1.5,1.5) rectangle (1.8,-1.5);

\node[skyblue3, right] at (-0.1,-1.15) {don't read};
\node[orange3, above=0.2cm] at (1,0.5) {address 1};
\node[orange3, above=0.2cm] at (-0.8,-0.8) {address 2};

\draw[semithick, ->, >=stealth'] (-1.5,-1.5) -- (-1.5,1.5);
\draw[semithick, ->, >=stealth'] (-1.5,-1.5) -- (1.5,-1.5);
\draw[semithick] (-1.5,0) -- (-1.4,0);
\draw[semithick] (0,-1.5) -- (0,-1.4);
\node[left]  at (-1.5,0) {$0$};
\node[below] at (0,-1.5) {$0$};

\node[point, draw=orange3, fill=orange1] (h1) at (1,0.5) [label={[orange3]right:{$\psi(\vec h_1)$}}] {};
\node[point, draw=orange3, fill=orange1] (h2) at (-0.8,-0.8)  [label={[orange3]right:{$\psi(\vec h_2)$}}] {};
\node[point] (h3) at (-1.3,1.2) [label={[skyblue3]below:$\phi(\tilde h_3)$}] {};
\node[point] (h4) at (-0.2,0.8) [label={[skyblue3]below:$\phi(\tilde h_4)$}] {};
\node[point] (h5) at (0.5,0.3) [label={[skyblue3]below:$\phi(\tilde h_5)$}] {};

\path[thick, skyblue3, ->, >=stealth', fill=skyblue1]
(h3) edge (h4)
(h4) edge (h5);
\end{scope}

\end{tikzpicture}
\end{center}
\caption{An illustration of the aRMM dynamics.
Left: Any state in the orange region is written to memory. The stored states are then mapped
via $\psi$ to a latent space (right) and compared with the current latent state
$\phi(\vec h_t)$. Whenever $\phi(\vec h_t)$ enters a $\theta$-ball around $\psi(\vec m)$
for some memory state $\vec m$, $\vec m$ is read from memory and overrides $\vec h_t$.}
\label{fig:state_space_assoc}
\end{figure}

The system dynamic is illustrated in Figure~\ref{fig:state_space_assoc}.
The orange region corresponds to the receptive field of the write head, i.e.\ where
$\cls(\tilde h_t) = 1$. All states in that region are written to memory until the memory is full.
The association mechanism then works as follows. We map the current state $\tilde h_t$ to
a latent space via the mapping $\phi$ and all memory states to the same space via a mapping $\psi$.
Whenever $\phi(\tilde h_t)$ enters a $\theta$-ball around some memory state $\psi(\vec m_{t, l})$,
we set $\vec h_t = \vec m_{t, l}$. If multiple $\theta$-balls are entered, we take the closest
memory state.

\subsection{Training Reservoir Memory Machines}

The first step in setting up a reservoir memory machine is to initialize a reservoir
$(\bm{U}, \bm{W}, \vec b, \sigma, \vec h_0)$ that is expressive enough to enable address
classification as well as the output mapping.
Although our approach is agnostic regarding the choice of reservoir, we generally recommend Legendre
delay networks as reservoirs because they are designed to losslessly
extract past states via linear operations, have few hyperparameters, and are deterministically
constructed, which avoids issues of unfortunate random initializations \cite{LMU}. We will also see
that this type of reservoir performs best on our benchmarks.

Once a reservoir is set up, we require training data in the form of three sequences
$\vec x_1, \ldots, \vec x_T \in \R^m$, $a_1, \ldots, a_T \in \{0, \ldots, L\}$, and
$\vec y_1, \ldots, \vec y_T \in \R^K$, where $\vec x_1, \ldots, \vec x_T$ are the inputs,
$a_1, \ldots, a_T$ are the desired memory addresses, and $\vec y_1, \ldots, \vec y_T$ are the
desired outputs. The fact that the memory addresses are part of the training data makes our approach
more demanding on the user compared to differentiable neural computers, which can learn the memory addresses \cite{NTM}. However, we would still argue that the memory access pattern is typically
straightforward to construct for the training data, at least for all tasks in our experiments (see there).
If this is not the case, one would develop data-driven heuristics to recognize
special states which need to be stored and recovered, such as a clustering based on the output
or an alignment of input and output states as recommended in our past work \cite{RMM}.

Once such training data is constructed, we can compute the state sequence $\vec h_1, \ldots, \vec h_T$
by applying the dynamics in Equation~\ref{eq:rmm} or~\ref{eq:rmm_assoc}, where $a_t$ is given by the
training data instead of a classifier, i.e.\ we perform teacher forcing. We can then train the
output weights $\bm{V}$ via linear regression with the training pairs $(\vec h_t, \vec y_t)$

The final step of our training mechanism is the state classifier. If we wish to train a standard
RMM we can directly use the pairs $(\vec h_t, a_t)$ as training data. Again, our approach is agnostic
to the choice of classifier but we generally recommend support vector machines (SVMs) because they
can be trained swiftly via convex optimization. This yields the final RMM
$(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0, \{0, \ldots, L\}, \cls)$.

By contrast, if we wish to train an associative RMM, we first create a new address sequence $\hat a_1, \ldots, \hat a_T$
where $\hat a_t = 1$ if $a_t > 0$ and there is no $\tau < t$ with $a_t = a_\tau$. Otherwise, $\hat a_t$
is zero. We use this new sequence to train a binary write classifier (e.g.\ a SVM) $\cls$ with the
training data $(\vec h_t, \hat a_t)$.
Our remaining problem is now to find mappings $\phi$ and $\psi$ as well as a
threshold $\theta$, such that for all $t$ with $\hat a_t = 0$ the distances $\lVert \phi(\vec h_t) - \psi(\vec m_{t, l}) \rVert^2$ are
smaller $\theta$ if $l = a_t > 0$ and larger $\theta$ otherwise. As a shorthand,
we re-write the data as triples $(\vec h_i, \vec m_i, z_i)$ with $z_i = +1$ if $\vec h_i$ and $\vec m_i$
should be associated and $z_i = -1$ otherwise.
This can be seen as a metric learning problem \cite{MetricLearn} or a transfer learning problem
\cite{TransferLearn}, either of which is hard to solve in general. Fortunately, our specific problem
is simpler because any state $\vec h_t$ can only encode the past inputs. Accordingly, a
natural latent space is the space of past inputs. We therefore construct linear
operators $\bm{\Phi}_1, \ldots, \bm{\Phi}_\tau \in \R^{m \times n}$ which reconstruct the input $t$ steps
ago from the current state (this is particularly straightforward for Legendre delay networks \cite{LMU})
and then we solve the problem:
\begin{align*}
\min_{\bm{A} \in \R^{\tau \times \tau}_+, \theta \geq 0} \quad &\sum_i \Big[ (d_i^2 - \theta) \cdot z_i + 1 \Big]_+ \\
\text{s.t.} \quad &d_i^2 = \sum_{t=1}^\tau \sum_{t'=1}^\tau \alpha_{t, t'} \cdot \lVert \bm{\Phi}_t \cdot \vec h_i - \bm{\Phi}_{t'} \cdot \vec m_i \rVert^2 & \forall i
\end{align*}
where $[x]_+ = \max\{0, x\}$ denotes the hinge loss. Note that this loss is zero if and only if
$d_i^2 - \theta < -1$ if $z_i = +1$ and $d_i^2 - \theta > 1$ if $z_i = -1$, i.e.\ if and only if
all associations are correct and a margin of safety for the associations is maintained.
The $d_i^2$ term in this problem further corresponds exactly to the squared distance
$\lVert \phi(\vec h_i) - \psi(\vec m_i)\rVert^2$ by setting $\phi(\vec h_i) = (\sqrt{\alpha_{1, 1}} \cdot \bm{\Phi}_1, \ldots, \sqrt{\alpha_{1, \tau}} \cdot \bm{\Phi}_1, \ldots, \sqrt{\alpha_{\tau, \tau}} \cdot \bm{\Phi}_\tau) \cdot \vec h_i$
and $\psi(\vec m_i) = (\sqrt{\alpha_{1, 1}} \cdot \bm{\Phi}_1, \ldots, \sqrt{\alpha_{1, \tau}} \cdot \bm{\Phi}_\tau, \ldots, \sqrt{\alpha_{\tau, \tau}} \cdot \bm{\Phi}_\tau) \cdot \vec m_i$,
where the commas indicate row-wise concatenation.
Note that we can omit operators in the concatenation where $\alpha_{t, t'} = 0$, which we can
further incentivize with an L1 regularization term. Note that the problem above is a highly
sparse linear program, which can thus be solved efficiently with standard LP solvers.
This completes the construction of the associative RMM
$(\bm{U}, \bm{W}, \bm{V}, \vec b, \sigma, \vec h_0, Q, \cls, \phi, \psi, \theta)$.

\section{Experiments and Results}

In this section we introduce our six benchmark tasks, strategies for generating the required memory
addresses, explain the experimental setup, and present our results.

\subsection{Benchmark Tasks}

We evaluate our reservoir memory machines (RMMs) on the following six benchmark tasks:

\paragraph{latch \cite{RMM}} The input is a one-dimensional time series of length 9-200
that is always zero except for ones at 3 random time points. The desired output is zero
until the first one in the input, where it switches to one, then back to zero at the next one,
and back to one at the third one.
\paragraph{copy \cite{NTM_impl}} The input is a nine-dimensional time series of 1-20 random vectors from $\{0, 1\}^8$ on the first eight channels, followed by zeros. The last input channel is zero except
for a one right before and after the input vectors.
The desired output is a copy of the first eight channels as in Theorem~\ref{thm:copy}.
\paragraph{repeat copy \cite{NTM_impl}} The input is a seven-dimensional time series of
1-10 random vectors from $\{0, 1\}^8$ on the first eight channels, followed by zeros.
The desired output are $1-10$ copies of the first eight input channels. Each copy is preceded
by a one on the last input channel, which is zero otherwise. Refer to Figure~\ref{fig:data} (left)
for an example.
\paragraph{associative recall \cite{NTM_impl}} The input is a seven-dimensional time series with
2-6 random blocks á 3 random vectors from $\{0, 1\}^6$ on the first six channels, followed by
a one on the seventh channel and then a random repeated block from the previous input. The
desired output is the block \emph{after} the presented element. Refer to
Figure~\ref{fig:data} (center) for an example.
\paragraph{\sigCopy} The input is a two-dimensional time series of two smooth random wavelets
of length $256$ on the first channel, followed by 1-10 blocks of $256$ zeros each.
On the second channel, each block of $256$ time steps ends with one of two marker wavelets of
length $32$. The first block with marker one, the second with marker two, and a random marker
(one or two) otherwise. The desired output is that each marker is followed
by its associated wavelet in the respective next $256$ time steps. Refer to Figure~\ref{fig:data} (right)
for an example.
\paragraph{FSMs} For finite state machine learning we construct Moore machines with
$\inps = \outps = \{(1, 0)^T, (0, 1)^T\}$, $\states = \{1, 2, 3, 4\}$ and randomly sampled
transition as well as output functions. As training data, we construct all sequences with
exactly one repeated state in the Moore machine as suggested in Theorem~\ref{thm:fsm}.
The test data consists of much longer sequences of length $256$ over $\inps$ and the
output the Moore machine would predict.

We note that, amongst these tasks, only latch and FSM can be solved straightforwardly with
Moore machines. Copy, repeat copy, and associative recall require exponentially many states
by the same argument as in Theorem~\ref{thm:copy}, and \sigCopy\ is not solvable with a Moore
machine because there are infinitely many smooth wavelets that could be generated.

\begin{figure*}
\begin{center}
\begin{tikzpicture}
\tikzstyle{copy_region}=[orange3, pattern=north east lines, pattern color=orange3, semithick, opacity=0.7]

\begin{groupplot}[view={0}{90}, xlabel={$t$}, ymin=0, ymax=8,
group style={group size=2 by 3,
	x descriptions at=edge bottom,y descriptions at=edge left,
	horizontal sep=0.4cm, vertical sep=0.2cm},
width=4cm, height=3cm,
colormap={tango}{color(0cm)=(white); color(1cm)=(skyblue3)}]
\nextgroupplot[title={repeat copy$\strut$},ymax=9,ylabel={input$\strut$}]
\addplot3[surf,mesh/ordering=y varies,mesh/rows=10,shader=flat corner] file {repeat_copy_input.csv};
\draw[copy_region] (axis cs:1,0.05) rectangle (axis cs:4,8);
\node[inner sep=0] (rc_block) at (axis cs:2.5,0) {};
\nextgroupplot[title={associative recall$\strut$},ymax=7,height=2.7cm, yshift={0.15cm}]
\addplot3[surf,mesh/ordering=y varies,mesh/rows=8,shader=flat corner] file {associative_recall_input.csv};
\draw[copy_region, pattern=crosshatch dots] (axis cs:0,0.05) rectangle (axis cs:3,5.95);
\draw[copy_region, pattern=crosshatch dots] (axis cs:10,0.05) rectangle (axis cs:13,5.95);
\draw[copy_region] (axis cs:3,0.05) rectangle (axis cs:6,5.95);
\node (ar_block1) at (axis cs:1.5,6) {};
\node (ar_block1_repeat) at (axis cs:11.5,6) {};
\node (ar_block2) at (axis cs:4.5,0) {};
\nextgroupplot[ymax=1,height=1.7cm,ylabel={address$\strut$}, yticklabels={,,}]
\addplot3[surf,mesh/ordering=y varies,mesh/rows=2,shader=flat corner] file {repeat_copy_states.csv};
\nextgroupplot[ymax=1,height=1.7cm,yticklabels={,,}, yshift={-0.3cm}]
\addplot3[surf,mesh/ordering=y varies,mesh/rows=2,shader=flat corner] file {associative_recall_states.csv};
\nextgroupplot[ymax=8,ylabel={output$\strut$},height=2.9cm]
\addplot3[surf,mesh/ordering=y varies,mesh/rows=9,shader=flat corner] file {repeat_copy_output.csv};
\draw[copy_region] (axis cs:1,0.05) rectangle (axis cs:4,8);
\draw[copy_region] (axis cs:5,0.05) rectangle (axis cs:8,8);
\draw[copy_region] (axis cs:9,0.05) rectangle (axis cs:12,8);
\draw[copy_region] (axis cs:13,0.05) rectangle (axis cs:16,8);
\node[inner sep=0] (rc_block_copy1) at (axis cs:2.5,8) {};
\node[inner sep=0] (rc_block_copy2) at (axis cs:6.5,8) {};
\node[inner sep=0] (rc_block_copy3) at (axis cs:10.5,8) {};
\node[inner sep=0] (rc_block_copy4) at (axis cs:14.5,8) {};
\nextgroupplot[ymax=6,height=2.6cm,yshift={-0.3cm}]
\addplot3[surf,mesh/ordering=y varies,mesh/rows=7,shader=flat corner] file {associative_recall_output.csv};
\draw[copy_region] (axis cs:13,0.05) rectangle (axis cs:15.95,5.95);
\node (ar_block2_recall) at (axis cs:14.5,6) {};
\end{groupplot}

\begin{scope}[shift={(6.5,0.2)}]
\begin{groupplot}[xlabel={$t$},xmin=0,xmax=1535,
group style={group size=1 by 3,
	x descriptions at=edge bottom,y descriptions at=edge left,
	horizontal sep=0.4cm, vertical sep=0.25cm},
width=9cm, height=2.8cm,
xtick={0,256,512,768,1024,1280}]
\nextgroupplot[title={\sigCopy$\strut$}, ytick={-3,0,3}]
\addplot[semithick, skyblue3] table[x=t,y=x1,col sep=tab] {signal_copy.csv};
\addplot[semithick, scarletred3]  table[x=t,y=x2,col sep=tab] {signal_copy.csv};
\draw[copy_region] (axis cs:0,-4) rectangle (axis cs:256,3.5);
\draw[copy_region, pattern=crosshatch dots] (axis cs:256,-4) rectangle (axis cs:512,3.5);
\node[inner sep=0] (sc_block1) at (axis cs:128,-4) {};
\node[inner sep=0] (sc_block2) at (axis cs:384,-4) {};

\nextgroupplot[height=1.9cm, ytick={0,1,2}, yticklabels={0,,}]
\addplot[semithick, skyblue3] table[x=t,y=q,col sep=tab] {signal_copy.csv};
\nextgroupplot[ytick={-3,0,3}]
\addplot[semithick, skyblue3] table[x=t,y=y,col sep=tab] {signal_copy.csv};
\draw[copy_region] (axis cs:768,-4)  rectangle (axis cs:1024,3.5);
\draw[copy_region, pattern=crosshatch dots] (axis cs:1024,-4) rectangle (axis cs:1280,3.5);
\draw[copy_region] (axis cs:1280,-4) rectangle (axis cs:1536,3.5);

\node[inner sep=0] (sc_block1_copy1) at (axis cs:896,3.5) {};
\node[inner sep=0] (sc_block2_copy1) at (axis cs:1152,3.5) {};
\node[inner sep=0] (sc_block1_copy2) at (axis cs:1408,3.5) {};
\end{groupplot}
\end{scope}

\path[->, >=stealth, semithick, orange3, opacity=0.8]
(rc_block) edge[out=270, in=90] (rc_block_copy1)
(rc_block) edge[out=270, in=90] (rc_block_copy2)
(rc_block) edge[out=270, in=90] (rc_block_copy3)
(rc_block) edge[out=270, in=90] (rc_block_copy4)
(ar_block1) edge[out=90, in=90] (ar_block1_repeat)
(ar_block2) edge[out=270, in=90] (ar_block2_recall)
(sc_block1) edge[out=270, in=90, looseness=0.8] (sc_block1_copy1)
(sc_block1) edge[out=270, in=90, looseness=0.8] (sc_block1_copy2)
(sc_block2) edge[out=270, in=90, looseness=0.8] (sc_block2_copy1);
\end{tikzpicture}
\vspace{-0.7cm}
\end{center}
\caption{An example from the repeat copy (left), associative recall (center), and \sigCopy\ (right)
data set, each with input in the first, memory addresses in the second, and output in the third row.
Task-relevant blocks are highlighted with stripes/dots and arrows.}
\label{fig:data}
\end{figure*}

\subsection{Generating Memory Addresses}

To train RMMs we require example memory address sequences for the training data.
The optimal strategy for such example address sequences depends on the task. We generally
recommend the following strategies:

For tasks with discrete and abstract outputs such as latch, we suggest to apply a clustering
on the target outputs. More specifically, for latch the memory address sequence becomes the training output $+1$ (i.e.\ naming the clusters 1 and 2).

For tasks which aim at storing information and recalling it in the same order, such as copy and repeat
copy, we suggest to use the state sequence $1, \ldots, T, 1, \ldots, T, \ldots, 1, \ldots, T$,
i.e.\ to enumerate each input vector and then recall each vector to generate the copy.
This is equivalent to the proof of Theorem~\ref{thm:copy}.

For associative recall tasks, such as associative recall and \sigCopy, we suggest to write
each block that could be recalled to memory and set the memory address to zero otherwise.
More specifically, for \sigCopy\ the state sequence is zero almost everywhere
except after each block of $256$ where it is $1$ for marker one and $2$ for marker two.
For associative recall the state sequence is $0, 0, 0, 0, 0, 1, 0, 0, 2, \ldots$, i.e.\ we
mark each block of 3, except the first one, and recall the index of the state to be recalled
after the presented item.

For FSM learning we use the ground-truth FSM to provide the state labels. We also evaluate the
alternative of first learning an FSM from data and using that to provide labels.

For repeat copy, associative recall, and \sigCopy, example inputs, outputs, and state sequences
are shown in Figure~\ref{fig:data}.

\subsection{Experimental Setup}

We use a standard RMM with $64$ neurons for latch, \sigCopy, and FSM learning, a standard
RMM with $256$ neurons for copy and repeat copy, and an associative RMM with $256$ neurons for
associative recall. We compare against echo state networks \cite[ESN]{ESN} without an external memory
and the same number of neurons. We compare three kinds of reservoir, namely Gaussian random numbers
normalized to a spectral radius $< 1$ (rand), cycle reservoirs with jumps \cite[CRJ]{CRJ}, and Legendre delay networks \cite[LDN]{LMU}.
In each case we optimize the reservoir hyperparameters via random search with $10$ trials and $3$ repeats
per trial.
On the first four tasks, we additionally compare against deep learning models with the same number
of neurons, namely a gated recurrent unit \cite[GRU]{GRU}, and a deep version of our reservoir memory
machine with a GRU as a recurrent controller, a softmax state classifier, and linear output. We
train this GRU-RMM to minimize the mean squared error on the output plus the crossentropy loss on the
state predictions.
We train the deep models with an ADAM optimizer with learning rate $10^{-3}$, weight decay of
$10^{-8}$, and minibatch size of $32$. We stop the training after $1000$ minibatches or
if the loss is below $10^{-3}$.

All models are trained on $90$ training sequences and $10$ test sequences from the data sets.
We repeat all experiments $20$ times for the reservoir models and $3$ times for the deep models.
All experiments are performed on a consumer grade Laptop with a 2017 Intel core i7 CPU and 16 GB RAM.

All experimental source code and reference implementations are available at
\url{https://gitlab.com/bpaassen/rmm}.

\subsection{Results}

\begin{table*}
\centering
\caption{The root mean square error for all data sets and all models ($\pm$ std.\ dev.).}
\label{tab:results}
\begin{scriptsize}
\begin{tabular}{ccccccccc}
dataset & rand-ESN & CRJ-ESN & LDN-ESN & GRU & GRU-RMM & rand-RMM & CRJ-RMM & LDN-RMM \\
\cmidrule(lr){1-1}\cmidrule(lr){2-4}\cmidrule(lr){5-6}\cmidrule(lr){7-9}
latch & $0.80 \pm 0.82$ & $0.52 \pm 0.02$ & $0.53 \pm 0.02$ & $0.08 \pm 0.06$ & $\bm{0.00 \pm 0.00}$ & $0.01 \pm 0.04$ & $\bm{0.00 \pm 0.00}$ & $\bm{0.00 \pm 0.00}$\\
copy & $0.39 \pm 0.01$ & $0.46 \pm 0.01$ & $0.34 \pm 0.01$ & $0.40 \pm 0.02$ & $\bm{0.03 \pm 0.00}$ & $0.44 \pm 0.03$ & $0.47 \pm 0.01$ & $0.07 \pm 0.06$\\
repeat copy & $0.44 \pm 0.01$ & $0.46 \pm 0.01$ & $0.39 \pm 0.01$ & $0.46 \pm 0.00$ & $\bm{0.02 \pm 0.00}$ & $0.39 \pm 0.03$ & $0.43 \pm 0.01$ & $0.04 \pm 0.05$\\
\sigCopyShort & $18.17 \pm 43.87$ & $17.79 \pm 43.93$ & $16.04 \pm 38.27$ & $\bm{4.13 \pm 1.76}$ & $6.02 \pm 4.13$ & $18.13 \pm 43.87$ & $17.76 \pm 43.93$ & $5.41 \pm 21.50$\\
FSMs & $0.47 \pm 0.16$ & $0.60 \pm 0.22$ & $0.54 \pm 0.19$ & - & - & $\bm{0.00 \pm 0.00}$ & $\bm{0.00 \pm 0.00}$ & $\bm{0.00 \pm 0.00}$\\
assoc.\ recall & $0.42 \pm 0.01$ & $0.32 \pm 0.01$ & $0.31 \pm 0.02$ & - & - & $0.43 \pm 0.02$ & $0.35 \pm 0.02$ & $\bm{0.09 \pm 0.05}$\\
\end{tabular}
\end{scriptsize}
\end{table*}

The average root mean square errors ($\pm$ std.) for all models on all data sets is shown in
Table~\ref{tab:results}. As can be seen, all RMM variants outperform ESNs on latch and FSM learning,
but only the LDN-RMM variant also achieves better results on copy, repeat copy, associative
recall and smooth associative recall.
This is likely due to the fact that LDNs guarantee lossless reconstruction of past inputs,
which is required for these four tasks.
In comparison to the deep learning models we note that the standard GRU performs well on latch and
\sigCopy, but comparable to standard ESNs on copy and repeat copy, which replicates earlier
results on differentiable neural computers \cite{NTM}. By contrast, a GRU-RMM can solve all tasks,
although the error remains in the same order of magnitude as the LDN-RMM.

Regarding FSM learning, we also consider a setting where we first learn a finite state
machine via Gold's algorithm \cite{FSM_learning} on the training sequences and then use
the states of this surrogate FSM as training memory address sequence.
This increases the error to $0.02 \pm 0.07$ for all RMM variants, which is still close to
optimal.

\begin{table*}
\centering
\caption{The average runtime in seconds for all data sets and all models ($\pm$ std.\ dev.).}
\label{tab:runtimes}
\begin{scriptsize}
\begin{tabular}{ccccccccc}
dataset & rand-ESN & CRJ-ESN & LDN-ESN & GRU & GRU-RMM & rand-RMM & CRJ-RMM & LDN-RMM \\
\cmidrule(lr){1-1}\cmidrule(lr){2-4}\cmidrule(lr){5-6}\cmidrule(lr){7-9}
latch & $\bm{0.21 \pm 0.02}$ & $0.21 \pm 0.01$ & $0.33 \pm 0.05$ & $694.10 \pm 21.95$ & $1720.91 \pm 32.44$ & $0.48 \pm 0.05$ & $0.47 \pm 0.07$ & $0.62 \pm 0.09$\\
copy & $0.26 \pm 0.05$ & $\bm{0.11 \pm 0.01}$ & $0.18 \pm 0.02$ & $229.94 \pm 3.89$ & $428.27 \pm 27.55$ & $3.03 \pm 0.33$ & $11.51 \pm 1.50$ & $6.55 \pm 0.65$\\
repeat copy & $0.29 \pm 0.05$ & $\bm{0.15 \pm 0.01}$ & $0.20 \pm 0.02$ & $333.33 \pm 2.20$ & $710.81 \pm 9.42$ & $3.64 \pm 0.50$ & $5.08 \pm 0.60$ & $1.46 \pm 0.16$\\
\sigCopyShort & $3.66 \pm 0.09$ & $\bm{3.46 \pm 0.11}$ & $3.84 \pm 0.13$ & $13011.93 \pm 493.89$ & $33344.53 \pm 757.30$ & $5.27 \pm 0.21$ & $5.02 \pm 0.17$ & $5.38 \pm 0.17$\\
FSMs & $0.21 \pm 0.04$ & $\bm{0.13 \pm 0.03}$ & $0.26 \pm 0.06$ & - & - & $0.81 \pm 0.03$ & $0.73 \pm 0.04$ & $0.82 \pm 0.06$\\
assoc.\ recall & $0.26 \pm 0.02$ & $\bm{0.10 \pm 0.01}$ & $0.15 \pm 0.02$ & - & - & $3.99 \pm 0.46$ & $5.55 \pm 1.18$ & $4.04 \pm 0.52$\\
\end{tabular}
\end{scriptsize}
\end{table*}

Table~\ref{tab:runtimes} shows the time needed for training and prediction as measured by Pythons
\texttt{time} function. We observe that RMMs are generally slower than standard echo state networks (up to a
factor of 100) but remain in the second range. The overhead is driven by the SVM training, which
is less costly on data sets with small explicit memory and, thus, fewer classes
(such as latch and \sigCopy).
Among the RMM variants, runtimes are comparable.
By contrast, the difference to the deep learning models is striking, with the deep
learning models requiring up to a factor 5000 more training time compared to RMMs.

\section{Conclusion}

We introduced a novel reservoir memory machine (RMM) architecture which extends echo state networks
with an external memory and thereby becomes computationally strictly more powerful than finite state
machines, whereas standard echo state networks are strictly weaker. In addition to these theoretical
results, we showed that RMMs can solve many benchmark tasks of differentiable neural computers which
are out of reach for standard recurrent neural networks. These successes require a sacrifice, namely
that examples of memory access behavior need to be supplied as part of the training data.
Future research should investigate how optimal memory access behavior can instead be learned from data,
perhaps via heuristics. Still, our model makes neural computation much more efficient to train, requiring
both less time and less training data compared to differentiable neural computers.

\section*{Acknowledgment}

Funding by the German Research Foundation (DFG) under grant number PA 3460/1-1
is gratefully acknowledged.