View source for Echo state network

==Formalism and theory== 

'''System equations.''' The basic
discrete-time, sigmoid-unit echo state network with <math>N</math> reservoir units,
<math>K</math> inputs and <math>L</math> outputs is governed by the
state update equation

(1)  <math>\mathbf{x}(n+1) = f(\mathbf{W} \mathbf{x}(n) + \mathbf{W}^{in}
\mathbf{u}(n+1) + \mathbf{W}^{fb} \mathbf{y}(n))\ ,</math>

where <math>\mathbf{x}(n)</math> is the <math>N</math>-dimensional
reservoir state, <math>f</math> is a sigmoid function (usually the
logistic sigmoid or the tanh function), <math>\mathbf{W}</math> is the
<math>N \times N</math> reservoir weight matrix,
<math>\mathbf{W}^{in}</math> is the <math>N \times K</math> input
weight matrix, <math>\mathbf{u}(n)</math> is the
<math>K</math>dimensional input signal, <math>\mathbf{W}^{fb}</math>
is the <math>N \times L</math> output feedback matrix, and
<math>\mathbf{y}(n)</math> is the <math>L</math>-dimensional output
signal. In tasks where no output feedback is required,
<math>\mathbf{W}^{fb}</math> is nulled. The extended system state
<math>\mathbf{z}(n) = [\mathbf{x}(n); \mathbf{u}(n)]</math> at
time <math>n</math> is the concatenation of the reservoir and input
states. The output is obtained from the extended system state by

(2)  <math>\mathbf{y}(n) = g(\mathbf{W}^{out} \mathbf{z}(n))\ ,</math>

where <math>g</math> is an output activation function (typically the
identity or a sigmoid) and <math>\mathbf{W}^{out}</math> is a
<math>L \times (K+N)</math>-dimensional matrix of output
weights. 

'''Learning equations.''' In the state harvesting stage of the
training, the ESN is driven by an input sequence <math>\mathbf{u}(1),
\ldots, \mathbf{u}(n_{max})\ ,</math> which yields a sequence
<math>\mathbf{z}(1), \ldots, \mathbf{z}(n_{max})</math> of extended
system states. The system equations (1), (2) are used here. If the
model includes output feedback (i.e., nonzero
<math>\mathbf{W}^{fb}</math>), then during the generation of the
system states, the correct outputs <math>\mathbf{d}(n)</math> (part of
the training data) are written into the output units ("teacher
forcing"). The obtained extended system states are filed row-wise into
a state collection matrix <math>\mathbf{S}</math> of size
<math>n_{max} \times (N + K)\ .</math> Usually some initial portion of
the states thus collected are discarded to accommodate for a washout of
the arbitrary (random or zero) initial reservoir state needed at time
1. Likewise, the desired outputs <math>\mathbf{d}(n)</math> are sorted
row-wise into a teacher output collection matrix
<math>\mathbf{D}</math> of size <math>n_{max} \times L\ .</math>

The desired output weights <math>\mathbf{W}^{out}</math> are the
linear regression weights of the desired outputs
<math>\mathbf{d}(n)</math> on the harvested extended states
<math>\mathbf{z}(n)\ .</math> A mathematically straightforward way to compute <math>\mathbf{W}^{out}</math> is to invoke the pseudoinverse (denoted by <math>\cdot^{\dagger}</math>) of <math>\mathbf{S}\ :</math>

(3)  <math>\mathbf{W}^{out} =
     (\mathbf{S}^{\dagger}\mathbf{D})'\ </math>,

which is an  offline algorithm (the prime denotes matrix transpose). Online adaptive methods known from linear signal processing can also be used to compute output weights (Jaeger 2003).

'''Echo state property.''' In order for the ESN principle to work, the
reservoir must have the ''echo state property'' (ESP), which relates
asymptotic properties of the excited reservoir dynamics to the driving
signal. Intuitively, the ESP states that the reservoir will
asymptotically wash out any information from initial conditions. The
ESP is guaranteed for additive-sigmoid neuron reservoirs, if the
reservoir weight matrix (and the leaking rates) satisfy certain
algebraic conditions in terms of singular values. For such reservoirs
with a tanh sigmoid, the ESP is violated ''for zero input'' if the
spectral radius of the reservoir weight matrix is larger than
unity. Conversely, it is empirically observed that the ESP is granted
for any input if this spectral radius is smaller than unity. This has
led in the literature to a far-spread but erroneous identification of
the ESP with a spectral radius below 1. Specifically, the larger the
input amplitude, the further above unity the spectral radius may be
while still obtaining the ESP. An abstract characterization of the ESP
for arbitrary reservoir types, and algebraic conditions for
additive-sigmoid neuron reservoirs are given in Jaeger (2001a); for an
important subclass of reservoirs, tighter algebraic conditions are
given in Buehner and Young (2006) and Yildiz et al. (2012); for leaky integrator neurons,
algebraic conditions are spelled out in Jaeger et al. (2007). The relationship between input signal characteristics and the ESP are explored in Manjunath and Jaeger (2013), where a fundamental 0-1-law is shown: if the input comes from a stationary source, the ESP holds with probability 1 or 0. 

'''Memory capacity.''' Due to the auto-feedback nature of RNNs, the
reservoir states <math>\mathbf{x}(n)</math> reflect traces of the past input
history. This can be seen as a dynamical short-term memory. For a
single-input ESN, this short-term memory's capacity <math>C</math> can be
quantified by <math>C = \sum_{i = 1, 2, \ldots} r^2(u(n-i), y_i(n))\ ,</math> where
<math>r^2(u(n-i), y_i(n))</math> is the squared correlation coefficient between
the input signal delayed by <math>i</math> and a trained output signal <math>y_i(n)</math>
which was trained on the task to retrodict (memorize) <math>u(n-i)</math> on the
input signal <math>u(n)\ .</math> It turns out that for i.i.d. input, the memory
capacity <math>C</math> of an echo state network of size <math>N</math> is bounded by <math>N\ ;</math> in the absence
of numerical errors and with a linear reservoir the bound is attained
(Jaeger 2002a; White and Sompolinsky 2004; Hermans & Schrauwen 2009). These findings imply that
it is impossible to train ESNs on tasks which require unbounded-time
memory, like for instance context-free
grammar parsing tasks (Schmidhuber et al. 2007). However, if output
units with feedback to the reservoir are trained as attractor memory
units, unbounded memory spans can be realized with ESNs, too (cf. the
multistable switch example in Jaeger 2002a; beginnings of a theory of feedback-induced memory-hold attractors in Maass, Joshi & Sontag 2007; an ESN based model of working memory with stable attractor states in Pascanu & Jaeger 2010). 

'''Universal computation and approximation properties.''' ESNs can
realize every nonlinear filter with bounded memory arbitrarily
well. This line of theoretical research has been started and advanced
in the field of Liquid State Machines (Maass, Natschlaeger & Markram 2002; Maass, Joshi & Sontag 2007), and the reader is
referred to the LSM article for detail.