Echo State Condition at the Critical Point

Abstract

Recurrent networks with transfer functions that fulfil the Lipschitz continuity with $K=1$ may be echo state networks if certain limitations on the recurrent connectivity are applied. It has been shown that it is sufficient if the largest singular value of the recurrent connectivity is smaller than 1. The main achievement of this paper is a proof under which conditions the network is an echo state network even if the largest singular value is one. It turns out that in this critical case the exact shape of the transfer function plays a decisive role in determining whether the network still fulfills the echo state condition. In addition, several examples with one-neuron networks are outlined to illustrate effects of critical connectivity. Moreover, within the manuscript a mathematical definition for a critical echo state network is suggested.

1. Introduction

Classic approaches of recurrent neural networks (RNNs), such as back-propagation through time [1], have been considered difficult to handle. In particular learning in the recurrent layer is slow and problematic due to potential instabilities. About 15 years ago, reservoir computing [2] was suggested as an alternative approach for RNNs. Here, it is not necessary to train connectivity in the recurrent layer. Instead, constant, usually random, connectivity weights are used in the recurrent layer. The supervised learning can be done by training the output layer using linear regression. Two types of reservoir computing are well established in the literature. The first is called liquid state machines (LSMs, [3]), which are usually based on a network of spiking neurons. The second type is called an echo state nework (ESN, [4]), which uses real valued neurons that initially use a sigmoid as a transfer function. Although a random recurrent connectivity pattern can be used, heuristically it has been found that typically the performance of the network depends strongly on the statistical features of this random connectivity (cf. for example [5] for ESNs).

Thus, what is a good reservoir with regard to particular stationary input statistics? This has been a fundamental question for research in this field since the invention of reservoir computing. One fundamental idea is that a reservoir can only infer training output from this window of the input history of which traces still can be found inside the reservoir dynamics. However, if the necessary inference from time series in order to learn the training output is far in the past, it may happen that no traces of this input remain inside the reservoir. So, the answer seems to be that a good reservoir is a reservoir from whose states it is possible to reconstruct an input history with a time span that is as long as possible. More precisely, they should be reconstructed in a way that is sufficiently accurate in order to predict the training output. In other words, a good reservoir is a reservoir that has a good memory of the input history.

There have been efforts to quantify the quality of the memory of the reservoir. Most common is the “memory capacity” (MC) according to Jaeger’s definition [4]. However, MC has several drawbacks. For example, it is not directly compatible to a Shannon information based measure. Still, it illustrates that ESNs are relatively tightly restricted in the way that the upper limit of the MC is equal to the number of hidden layer neurons. So the capabilities of the network increase with the number of neurons.

One more important limiting factor with regard to the reservoir memory is the strength of the recurrent connectivity. According to the echo state condition, the nature of the reservoir requires that the maximum ${\left|\lambda \right|}_{\max }$ of its eigenvalues in modulus is smaller than 1, which is called the echo state property (ESP). This seems always to result in a exponential forgetting of previous states. Thus, forgetting is independent from the input statistics but instead has to be pre-determined and is due to the design of the reservoir dynamics.

In order to proceed, there are several important aspects. First, it is necessary to get rid of the intrinsic time scale of forgetting that is induced by ${\left|\lambda \right|}_{\max }<1$. More precisely, the remaining activity of inputs to the reservoir that date back earlier than $\Delta t$ is a fraction smaller than ${\left|\lambda \right|}_{\max }^{\Delta t}$. Networks where the largest eigenvalue is larger than 1 cannot be used as reservoirs anymore, a point which is detailed below. One can try ${\left|\lambda \right|}_{\max }=1$ and see if this improves the network performance and how this impacts the memory of the reservoir on earlier events. Steps toward this direction have been made by going near the “edge of chaos” [5] or even further where the network may not be an echo state network for all possible input sequences but instead just around some permissible inputs [6]. Presumably, these approaches still all forget exponentially fast.

Strictly, networks with ${\left|\lambda \right|}_{\max }=1$ are not covered by the initial proof of Jaeger for the echo state condition. One important purpose of this paper is to close this gap and to complete Jaeger’s proof in this sense. The other purpose is to motivate the principles of [7] in as simple as possible examples and thus to increase the resulting insight.

The intentions of the following sections of the paper are to motivate the concept of critical neural networks and explain how they are related to memory compression. These intentions comprise a relatively large part of the paper because it seems important to argue for the principle value of critical ESNs. Section 2 introduces the concept of reservoir computing and also defines important variables for the following sections. An important feature is that Lyapunov coefficients are reviewed in order to suggest a clear definition for critical reservoirs that can be used analytically on candidate reservoirs. Section 3 describes how critical one-neuron reservoirs can be designed and also introduces the concept of extending to large networks. Section 4 explains why the critical ESNs are not covered by Jaeger’s proof. The actual proof for the echo state condition can be found in Section 5. Certain aspects of the proof have been transferred to the appendix.

2. Motivation

The simplest way to train with data in a supervised learning paradigm is to interpolate data (cf. for example [8]). Thus, for a time series of input data ${\mathbf{u}}_{\mathit{t}}\in {\mathbb{R}}^n$ that forms an input sequence ${\overline{\mathbf{u}}}^{\infty }$ and a corresponding output data ${\mathbf{o}}_{\mathit{t}}\in {\mathbb{R}}^m$ one can choose a vector of non-linear, linearly independent functions $\mathbf{F}\left({\mathbf{u}}_{\mathit{t}}\right):{\mathbb{R}}^n\to {\mathbb{R}}^k$ and a transfer matrix ${\mathbf{w}}^{out}:{\mathbb{R}}^k\to {\mathbb{R}}^m$. Then, one can define

$$\begin{array}{ccc}\hfill {\mathbf{x}}_{\mathit{t}}& =& \mathbf{F}\left({\mathbf{u}}_{\mathit{t}}\right)\hfill \\ \hfill \widetilde{{\mathbf{o}}_{\mathit{t}}}& =& {\mathbf{w}}^{out}{\mathbf{x}}_{\mathit{t}}.\hfill \end{array}$$

${\mathbf{w}}^{out}$ can be calculated by linear regression, i.e.,

$${\mathbf{w}}^{out}={\left(A{A}^{\prime }\right)}^{-1}\left(AB\right),$$

(1)

where the rectangular matrices $A=[{\mathbf{x}}_{\mathit{0}},{\mathbf{x}}_{\mathit{1}},\cdots ,{\mathbf{x}}_{\mathit{t}}]$ and $B=[{\mathbf{o}}_0,{\mathbf{o}}_1,\cdots ,{\mathbf{o}}_t]$ are composed from the data of the training set and $A^{\prime }$ is the transpose of A. Further, one can use a single transcendental function $\theta (.)$ such that

$${\mathbf{x}}_{\mathit{t}}=\mathbf{F}\left({\mathbf{u}}_{\mathit{t}}\right)=\theta \left({\mathbf{w}}^{in}{\mathbf{u}}_{\mathit{t}}\right),$$

(2)

where ${\mathbf{w}}^{in}:{\mathbb{R}}^n\to {\mathbb{R}}^k$ is a matrix in which each line consists of a unique vector and $\theta (.)$ is defined in the Matlab fashion; so the function is applied to each entry of the vector separately. Linear independence of the components of $\mathbf{F}$ can then be guaranteed if the column vectors of ${\mathbf{w}}^{in}$ are linearly independent. Practically, linear independence can be assumed if the entries of ${\mathbf{w}}^{in}$ are chosen randomly from a continuous set and $k\ge n$.

The disadvantage of the pure interpolation method with regard to time series is that the input history, that is ${\mathbf{u}}_{\mathit{t}-\mathit{1}},{\mathbf{u}}_{\mathit{t}-\mathit{2}},\cdots {\mathbf{u}}_{\mathit{0}}$, has no impact on training the current output $\widetilde{{\mathbf{o}}_{\mathit{t}}}$. Thus, if a relation between previous inputs and current outputs exists, that relation cannot be learned.

Different from Equation (1), a reservoir in the sense of reservoir computing [2,9,10] can be defined as

$${\mathbf{x}}_{\mathit{t}}=\mathbf{F}({\mathbf{x}}_{\mathit{t}-\mathit{1}},{\mathbf{u}}_{\mathit{t}}).$$

(3)

The recursive update function adds several new aspects to the interpolation that is outlined in Equation (1):

• The new function turns the interpolation into a dynamical system:

  $${\mathbf{x}}_{\mathit{t}}=\mathbf{F}({\mathbf{x}}_{\mathit{t}-\mathit{1}},{\mathbf{u}}_{\mathit{t}})={\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}\left({\mathbf{x}}_{\mathit{t}-\mathit{1}}\right),$$

  (4)

  where the notation ${\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}\left({\mathbf{x}}_{\mathit{t}-\mathit{1}}\right)$ is intended to illustrate the character of the particular discrete time, deterministic dynamical system and the fact that each possible time series ${\overline{\mathbf{u}}}^{\infty }$ defines a specific set of dynamics (For obvious reasons one may call $\mathbf{F}$ an input driven system.).
  The superset $\mathcal{F}$ over all possible ${\overline{\mathbf{u}}}^{\infty }$,

  $$\mathcal{F}=\bigcup _{{\overline{\mathbf{u}}}^{\infty }}{\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }},$$

  may be called the reservoir dynamics. Thus, $\mathcal{F}$ covers all possible dynamics of a particular reservoir with regard to any time series of input vectors in ${\mathbb{R}}^n$. Note that this way of looking into the dynamics of reservoirs is non-standard. Rather the standard approach is to interpret the reservoir as a non-autonomous dynamical system and then to formalize the system accordingly [6]. For the present work, the turn towards standard dynamical systems has been chosen because here the relevant methodology is well established and the above mentioned formalization appears sufficient for all purposes of this work.
• It is now possible to account for information from a time series’ past in order to calculate the appropriate output.

One important question is if the regression step in the previous section, and thus the interpolation, works at all for the recursive definition in Equation (3). Jaeger showed ([4], p. 43; [11]) that the regression is applicable, i.e., the echo state property (ESP) is fulfilled, if and only if the network is uniformly state contracting. Uniformly state contraction is defined in the following.

Assume an infinite stimulus sequence ${\overline{\mathbf{u}}}^{\infty }={\left\{{\mathbf{u}}_n\right\}}_{n=0}^{\infty }$ and two random initial internal states of the system ${\mathbf{x}}_0$ and ${\mathbf{y}}_0$. To both initial states ${\mathbf{x}}_0$ and ${\mathbf{y}}_0$ the sequences ${\overline{\mathbf{x}}}^{\infty }={\left\{{\mathbf{x}}_n\right\}}_{n=0}^{\infty }$ and ${\overline{\mathbf{y}}}^{\infty }={\left\{{\mathbf{y}}_n\right\}}_{n=0}^{\infty }$ can be respectively assigned.

$$\begin{array}{ccc}\hfill {\mathbf{x}}_{\mathit{t}}=\mathbf{F}({\mathbf{x}}_{\mathit{t}-\mathit{1}},{\mathbf{u}}_{\mathit{t}})& =& {\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}\left({\mathbf{x}}_{\mathit{t}-\mathit{1}}\right)\hfill \\ \hfill {\mathbf{y}}_{\mathit{t}}=\mathbf{F}({\mathbf{y}}_{\mathit{t}-\mathit{1}},{\mathbf{u}}_{\mathit{t}})& =& {\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}\left({\mathbf{y}}_{\mathit{t}-\mathit{1}}\right)\hfill \\ \hfill q_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}}& =& d({\mathbf{x}}_{\mathit{t}},{\mathbf{y}}_{\mathit{t}}),\hfill \end{array}$$

(5)

where $q_{{\overline{\mathbf{u}}}^{\infty }}$ is another series and $d(.,.)$ shall be a distance measure using the square norm.

Then the system $\mathcal{F}$ is uniformly state contracting if it is independent from ${\overline{\mathbf{u}}}^{\infty }$ and if for any initial state (${\mathbf{x}}_0$,${\mathbf{y}}_0$) and all real values $ϵ>0$ there exists a finite ${\tau }_{\mathcal{F}}\left(ϵ\right)<\infty$ for which

$$\underset{\mathcal{F}}{\max }{q}_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}}\le ϵ$$

(6)

for all $\mathit{t}\ge {\tau }_{\mathcal{F}}$.

Another way to look at the echo state condition is that the network $\mathcal{F}$ behaves in a time invariant manner, in the way that some finite subsequence in an input time series will roughly result always in the same outcome. In other words

$${\mathbf{x}}_{\Delta t+t_0}\approx {\mathbf{y}}_{\Delta t+t_0}$$

independent of $t_0$, ${\mathbf{x}}_{t_0}$ and ${\mathbf{y}}_{t_0}$ and if $\Delta t$ is sufficiently large.

Lyapunov analysis is a method to analyze predictability versus instability of a dynamical system (see [12]). More precisely, it measures exponential stability.

In the context of non-autonomous systems, one may define the Lyapunov exponent as

$${\mathsf{\Lambda }}_{{\overline{\mathbf{u}}}^{\infty }}=\underset{|q_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}=\mathit{0}}|\to 0}{\lim }\underset{t\to \infty }{\lim }\frac{1}{t}\log \frac{|q_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}}|}{|q_{{\overline{\mathbf{u}}}^{\infty },0}|},$$

(7)

Thus, if

$$q_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}}\propto \exp \left(b\mathit{t}\right),$$

then ${\mathsf{\Lambda }}_{{\overline{\mathbf{u}}}^{\infty }}$ approximates b and thus measures the exponent of exponential decay. For power law decays, the Lyapunov exponent is always zero (For example, one may try $q_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}}=\frac{1}{\mathit{t}+\mathit{1}}$).

In order to define criticality, we use the following definition.

Definition 1.

A reservoir that is uniformly state contracting shall be called critical if for at least one input sequence ${\overline{\mathbf{u}}}^{\infty }$ there is at least one Lyapunov exponent ${\mathsf{\Lambda }}_{{\overline{\mathbf{u}}}^{\infty }}$ that is zero.

The echo state network (ESN) is an implementation of reservoir dynamics as outlined in Equation (3). Like other reservoir computing approaches, the system is intended to resemble the dynamics of a biologically inspired recurrent neural network. The dynamics can be described for discrete time-steps $\mathit{t}$, with the following equations:

$$\begin{array}{c}{\mathbf{x}}_{\mathit{lin},\mathit{t}}=\mathbf{W}{\mathbf{x}}_{\mathit{t}-\mathit{1}}+{\mathbf{w}}^{in}{\mathbf{u}}_{\mathit{t}}\hfill \\ {\mathbf{x}}_{\mathit{t}}=\theta \left({\mathbf{x}}_{\mathit{lin},\mathit{t}}\right)\hfill \\ \widetilde{{\mathbf{o}}_{\mathit{t}}}={\mathbf{w}}^{out}{\mathbf{x}}_{\mathit{t}.}\hfill \end{array}$$

(8)

With regard to the transfer function $\theta (.)$, it shall be assumed that it is continuous, differentiable, transcendental and monotonically increasing with the limit $1\ge {\theta }^{\prime }(.)\ge 0$, which is compatible with the requirement that $\theta (.)$ fulfills the Lipschitz continuity with $K=1$. Jaeger’s approach uses random matrices for $\mathbf{W}$ and ${\mathbf{w}}^{in}$, learning is restricted to the output layer ${\mathbf{w}}^{out}$. The learning (i.e., training ${\mathbf{o}}_{\mathit{t}}$) can be performed by linear regression (cf. Equation (1)).

The ESN fulfills the echo state condition (i.e., it is uniformly state contracting) if certain restrictions on the connectivity of the recurrent layer apply, for which one can name a necessary condition and a sufficient condition:

• C1 A network has echo states only if

  $${1>\left|\lambda \right|}_{\max }=\max \mathrm{abs}\left(\lambda \left(\mathbf{W}\right)\right),$$

  (9)

  i.e., the absolute value of the biggest eigenvalue of $\mathbf{W}$ is below 1. The condition means that a network is not and ESN if $1<\max \mathrm{abs}\left(\lambda \right(\mathbf{W}\left)\right)$.
• C2 Jaeger named here initially

  $$1>s_{\max }=\max s\left(\mathbf{W}\right),$$

  (10)

  where s is the vector of singular values of the matrix $\mathbf{W}$. However, a closer sufficient condition has been found in [13]. Thus, it is already sufficient to find a full rank matrix D for which

  $$1>\max s\left(D\mathbf{W}{D}^{-1}\right).$$

  (11)

The authors of [14] found another formulation of the same constraint: The network with internal weight matrix $\mathbf{W}$ satisfies the echo state property for any input if W is diagonally Schur stable, i.e., there exists a diagonal $P>0$ such that $W^{T}PW-P$ is negative definite.

Apart from the requirement that a reservoir has to be uniformly state contracting, the learning process itself is not of interest in the scope of this paper.

3. Critical Reservoirs with Regard to the Input Statistics ${\overline{\mathbf{u}}}^{\infty }$

Various ideas on what types of reservoirs work better than others have been brought up. One can try to keep the memories of the input history in the network as long as possible. The principle idea is to tune the network’s recurrent connectivity to a level where the convergence for a subset of ${\mathcal{F}}_{crit}\in \mathcal{F}$ with regard to Equation (6) is

$$q_{{\overline{\mathbf{u}}}_{crit}^{\infty },\mathit{t}}\propto t^a$$

(12)

rather than

$$q_{{\overline{\mathbf{u}}}^{\infty },\mathit{t}}\propto b^t,$$

(13)

where $a<0$ and $0<b<1$ are system specific values, i.e., they depend on ${\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}$.

A network according to Equation (12) is still an ESN since it fullfils the ESP. Still, forgetting of initial states is not bound to a certain time scale. Remnants of information can —under certain circumstances— remain for virtually infinite long times within the network given that not too much unpredictable new input enters the network. Lyapunov analysis of a time series according to Equation (12) would result in zero, and Lyapunov analysis of Equation (13) yields a nonzero result.

In ESNs forgetting according to the power law of Equation (12) for an input time series $q_{{\overline{\mathbf{u}}}_{crit}^{\infty },\mathit{t}}$ is achievable if the following constraints are fulfilled:

• The recurrent connectivity $\mathbf{W}$, the input connectivity ${\mathbf{w}}^{in}$ of the ESN and the transfer function $\theta (.)$ have to be arranged in a way that if the ESN is fed with $q_{{\overline{\mathbf{u}}}_{crit}^{\infty },\mathit{t}}$ one approximates

  $$\underset{\mathit{t}\to \infty }{\lim }\left|\dot{\theta }\left({\mathbf{x}}_{\mathit{lin},\mathit{t}}\right)\right|=1.$$

  Thus, the aim of the training is

  $$\left|\dot{\theta }\left({\mathbf{x}}_{\mathit{lin},\mathit{t}}\right)\right|=1.$$

  (14)

  Since the ESN has to fulfil the Lipschitz continuity with $K=1$, the points where $\dot{\theta }=1$ have to be inflection points of the transfer function. In the following these inflection points shall be called epi-critical points (ECPs).
• The recurrent connectivity of the network is to be designed in a way that the largest absolute eigenvalue and the largest singular value of $\mathbf{W}$ both are equal to one. This can be done by using normal matrices for $\mathbf{W}$ (see Section 3.5).

3.1. Transfer Functions

The standard transfer function that is widely used in ESNs and other types of neural networks is the sigmoid function, i.e.,

$$\theta \left(x\right)=\tanh \left(x\right).$$

(15)

The sigmoid transfer function has one ECP ${\mathsf{\Pi }}_0=0$.

As a second possible transfer function, one may consider

$$\theta \left(x\right)=0.5x-0.25\sin \left(2x\right).$$

(16)

Here, one has a infinite set of ECPs at ${\mathsf{\Pi }}_i=(n+0.5)\times \pi$. It is important to have more than one ECP in the transfer functions because for a network with discrete values it appears necessary that each neuron has at least 2 possible states in order to have any inference from the past to the future. In the case of $\tanh$, the only solution of Equation (14) is

$${\mathbf{x}}_{\mathit{lin},\mathit{t}}=0.$$

That type of trained network cannot infer information from the past to the present for the expected input, which significantly restricts its capabilities. One can see that from

$${\mathbf{x}}_{\mathit{t}}=\tanh \left({\mathbf{x}}_{\mathit{lin},\mathit{t}}\right)=0.$$

The next iteration yields

$${\mathbf{x}}_{\mathit{t}+\mathit{1}}=\tanh \left({\mathbf{w}}^{\mathrm{in}}{\mathbf{u}}_{\mathit{t}}\right),$$

which again, after training would require

$$0={\mathbf{w}}^{in}{\mathbf{u}}_{\mathit{t}}.$$

Thus, the network can only anticipate the same input at all time steps.

In the case of Equation (16), the maximal derivative ${\theta }^{\prime }\left(x\right)$ is 1 at $x=\pi (n+1/2)$, where n is an integer number (confer Figure 1). Here the main advantage is that there exists an infinite set of epi-critical points. However, all these points are positioned along the linear function $y=x/2$. This setting still significantly restricts the training of ${\mathcal{F}}_{crit}$. Here one can consider the polynomial with the lowest possible rank (cf. the green line in Figure 1, left side) that interpolates between the epi-critical points (in the following called an epi-critical transfer function). In the case of Equation (16) the epi-critical transfer function is the linear function

$${\mathbf{x}}_{\mathit{t}+\mathit{1}}=0.5\mathbf{W}{\mathbf{x}}_{\mathit{t}}+0.5{\mathbf{w}}^{in}{\mathbf{u}}_{\mathit{t}.}$$

Thus, the effective dynamics of the trained reservoir on the expected input time series is -if this is possible- the dynamics of a linear network. This results in a very restricted set of trainable time series.

As an alternative, one could consider also a transcendental function for the interpolation between the points, such as depicted in Figure 2. The true transfer function (blue line in Figure 2) can be constructed in the following way. Around a set of defined epi-critical points ${\mathsf{\Pi }}_i$, define θ as either

$$\theta \left(x\right)=\tanh (x-{\mathsf{\Pi }}_i)+\tanh \left({\mathsf{\Pi }}_i\right)$$

or

$$\theta \left(x\right)=\tanh \left(x\right).$$

This is one conceptional suggestion for further investigations. The result is a transfer function with the epi-critical points ${\mathsf{\Pi }}_i$ and 0. The epi-critical transfer in this case is a $\tanh$ function.

3.2. Examples Using a Single Neuron as a Reservoir

In this and the following sections, practical examples are brought up where a single neuron represents a reservoir. Single neuron reservoirs have been studied in other researches [15,16]. Here the intention is to illustrate the principle benefits and other features of critical ESNs.

First one can consider a neuron with $\tanh$ as a transfer function along with a single input unit

$$x_{t+1}=\tanh (b{x}_t+u_t),$$

(17)

where in order to achieve a critical network $\left|b\right|$ has to be equal to 1. i.e., the network exactly fulfills the boundary condition. From previous consideration one knows that ${\mathcal{F}}_{crit}$ has the dynamics that results from $u_t=0$ as an input. In this case the only fixed-point of the dynamics is $x_t=0$, which is also the epi-critical point if $\left|b\right|=1$.

Power law forgetting: Starting from the two initial values $x_0=0$ and say $y_0=0.01$, one can see that the two networks converge in a power law manner to zero. On the other hand, for a linear network

$$x_{t+1}=b{x}_t+u_t$$

with the same initial conditions the dynamics of the two networks never converge (independently of $u_t$). Instead, the difference between $x_0=0$ and say $y_0=0.01$ stays the same forever. Thus, the network behavior in the the case of $\left|b\right|=1$ depends on the nature of the transfer function. For all other values of b, both transfer functions result qualitatively in the same behavior in dependence on b: either they diverge or they converge exponentially. Since $\left|b\right|=1$ is also the border between convergence and divergence and thus the border between uniformly state contracting networks and not uniformly state contracting networks, the case of $\left|b\right|=1$ is a critical point of the dynamical system, in a similar manner as a critical point at the transition from ordered dynamics to instability. In the following it is intended to extend rules for different transfer functions, where different transfer functions result in the critical point in uniformly state contracting networks and where this is not the case.

As a final preliminary remark, it has to be emphasized that a network being uniformly state contracting means that the states are contracting for any kind of input $u_t$. It does not mean that for any kind of input the contraction follows a power law. In fact, for all input settings $u_t\ne 0$ the contraction is exponential for the neuron of Equation (17), even in the critical case ($\left|b\right|=1$).

3.3. Single Neuron Network Example with Alternating Input and Power Law Forgetting

As outlined above, for practical purposes the sigmoid function, i.e., $\theta =tanh(.)$, is not useful for critical networks because the only critical state occurs when total activity of such a network is null. In that case it is not possible to transfer information about the input history. The reason is illustrated in the following example, where instead of a sigmoid function other types of transfer functions are used.

So, the one-neuron network

$$x_{t+1}=\theta (-b{x}_t+(2-b)u_t)$$

(18)

with a constant b, the transfer function of Equation (16) and the expected alternating input $u_t={(-1)}^t\pi /4$ has an attractor state when also $x_t$ is alternating with $x_t={(-1)}^t\pi /4$ independently from b. Thus, $u_t={(-1)}^t\pi /4$ shall be interpreted as the expected input that directs the activity of the network exactly to where ${\theta }^{\prime }=1$ and thus induces a critical dynamic ${\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}={\mathcal{F}}_{crit}$.

It is now interesting to investigate the convergence behavior for different values of b considering differing starting values for internal states $x_t$ and $y_t$. Figure 3 depicts the resulting different Lyapunov exponents for one-neuron networks with different values of b. One can see that—not surprisingly—the Lyapunov exponent for $b=1$ is zero. This is the critical point that marks the transition from order to instability in the system and at the same time the transition from ESP to non-ESP.

In the following the same network at $b=1$ is investigated. Some unexpected input, i.e., $u_t\ne {(-1)}^t\pi /4$, lets the network jump out of the attractor. If the input afterwards continues as expected, the network slowly returns to the attractor state in a power law fashion. Thus,

$$d(x_t,y_t)\propto t^{-a},$$

where $y_t$ represents the undisturbed time series and a is a constant value. Note that $x_t$ contains all information of the network history and that the network was simulated using IEEE 754-2008 double precision variables, which have a memory size of 64 bits on Intel architecture computers. Although floating point variables are organized in a complicated way of three parts, the sign, exponent and mantissa, it is clear that the total reservoir capacity cannot exceed those 64 bits, which means in the limit a reservoir of one-neuron cannot remember more than 64 binary i.i.d. random numbers.

Thus, about 64 iterations after an unexpected input the difference between $x_t$ and $y_t$ should be annihilated. Thus, if both networks $x_t$ and $y_t$ receive the same unexpected input that is of the same magnitude, the difference between the $x_t$ and $y_t$ should reach virtually 0 within 64 iterations. The consideration can be tested by setting the input

$$u_t=\pi /4\times \mathrm{rand},$$

where $\mathrm{rand}$ is an i.i.d. random list of +1s and -1s, that produces a representative of ${\mathcal{F}}_{{\overline{\mathbf{u}}}^{\infty }}\ne {\mathcal{F}}_{crit}$. Figure 4 and Figure 5 depict results from simulations, where after one iteration when two networks receive different inputs, both networks receive again the same input. Depicted is again the development of the difference between both networks $d(x_t,y_t)$ versus the number of iterations. The graphs appear in a double logarithmic fashion, so power law decays appear as straight lines. One can see that the networks that receive alternating, i.e., the expected input, pertains the difference for very long time spans (that exceed 64 iterations). On the other hand, if the network input for both networks is identical but i.i.d random and of the same order of magnitude as the expected input, the difference vanishes within 64 iterations.

The network distinguishes regular input from irregular input. Memories of irregular events pertain for a long time in the network provided that the following input is regular again. How a reservoir can be trained to anticipate certain input statistics has been discussed [7]. Additional solutions to this problem are subject to further investigations.

3.4. Relation to “Near Edge of Chaos” Approaches

It is a common experience that—in spite of given theoretical limits for the ESPs—the recurrent connectivity can be significantly higher than $s_{\max }=1$ for many practical input statistics. Those over-tuned ESNs in many cases show a much better performance than those that actually obey Jaeger’s initial limit ESP. So, recently researchers came up with theoretical insights with regard to ESPs that are subject to a network and a particular input statistic [6]. In the scope of this work, instead of defining the ESP for a network the ESP is always defined as related to a network and an input statistic. Also, similar efforts have been undertaken in the field of so-called liquid state machines [17,18].

One may assume that those approaches show similar properties as the one that has been presented here. However, for a good reason those approaches all are called ‘near edge of chaos’ approaches. In order to illustrate the problems that arise from those approaches, one may consider what happens if those overtuned ESNs are set exactly to the critical point. Here, just for the general understanding one may consider again a one-neuron network and a tanh as a transfer function, so

$$x_{t+1}=\tanh (-b{x}_t+u_t).$$

(19)

Note that the ESP limit outlined above requires that the recurrent connectivity should be $b<1$. An input time series than one can use is from the previous section

$$u_t={(-1)}^t\pi /4$$

(20)

Slightly tedious but basically simple calculus results in a critical value of $b\approx 2.344$ for the input time series, where $x_t\approx {(-1)}^t\times 0.757$. In this situation one can test for the convergence of two slightly different initial conditions and obtain a power law decay of the difference. However, setting up the amplitude of the input just a tiny bit higher is going to result in two diverging time series $x_t$ and $y_t$. If the conditions of the ESN are chosen to be exactly at the critical point, it is possible that a untrained input sequence very close to the trained input sequence turns the ESN into a state where the ESP is not fulfilled anymore (for a related and more detailed discussion with a numerical analysis, confer [19]).

For this reason all the networks have to be chosen at a significant margin away from the edge of instability. That is very different from the approach in the previous section where although the expected input sequence for the network is exactly at the critical point, all other input sequences result in a stable ESN in most cases with exponential forgetting.

3.5. How the One-Neuron Example Can Be Extended to Multi-Neuron Networks: Normal Matrices

A normal matrix $\mathbf{W}$ commutes with its own transpose, i.e.,

$$\mathbf{W}{\mathbf{W}}^T={\mathbf{W}}^T\mathbf{W}.$$

For a normal matrix $\mathbf{W}$, it can easily be shown that

$$\max s\left(\mathbf{W}\right)=\max \mathrm{abs}\left(\lambda \right(\mathbf{W}\left)\right).$$

These matrices apply to the spectral theorem; the largest absolute eigenvalue is the same as the largest singular value, which makes a clear theoretical separation between networks that are uniformly state contracting and those that are not compatible to the echo state condition. Still, for normal matrices all previously known ES conditions do not determine to which of those two groups the critical point itself belongs.

Summarizing, all previous works result in theorems for an open set of conditions that are defined by the strict inequalities Equations (9) and (11). In the closest case, the case of normal matrices, when considering the singular condition

$$1=\max s\left(\mathbf{W}\right)=\max \mathrm{abs}\left(\lambda \right(\mathbf{W}\left)\right)$$

(21)

there is no statement of the above mentioned theorems if the network is uniformly state contracting.

Some simple, preliminary numerical tests reveal that in the case of networks that satisfy Equation (21) the further development of the network strictly depends on the exact shape of transfer function.

4. Echo State Condition Limit with Weak Contraction

In the previous section, it has been shown how power law forgetting may occur in an ESN type neural network. These networks are all tuned to the point where ${\left|\lambda \right|}_{\max }=S=1$. For this tuning it is still undetermined if the ESP is fulfilled or not even if normal matrices or one-neuron RNNs are used. The current section is dedicated to determining under which conditions Jaeger’s ESP can be extended to this boundary condition.

Jaeger’s sufficient echo state condition (see [4], App. C, p. 41) has strictly been proven only for non-critical systems (largest singular value $S<1$) and with $\tanh (.)$ as a transfer function. The original proof is based on the fact that $\tanh$ in combination with $S<1$ is a contraction. In that case Jaeger shows an exponential convergence.

The core of all considerations of a sufficient condition is to give a close upper estimate of the distance between the next iterations of two different states $y_t$ and $x_t$. The estimate is of the form

$$\underset{{\overline{\mathbf{u}}}^{\infty }}{\max }d(y_{t+1},x_{t+1})=\underset{\mathcal{F}}{\max }d(\mathcal{F}\left(y_t\right),\mathcal{F}\left(x_t\right))\le {\varphi }_1·d(y_t,x_t),$$

where the parameter ${\varphi }_1$ basically is quantified by the nature of the transfer function and the strength of the connectivity matrix. The estimate has to be good enough that the iterative application of ${\varphi }_1$ should result in a convergence to 0:

$$\underset{t\to \infty }{\lim }{[{\varphi }_1·]}^{t}d(y_0,x_0)=0,$$

(22)

This is equivalent to investigating a series $q_t$ with

$$d(y_t,x_t)<q_t={[{\varphi }_1·]}^{t}d(y_0,x_0)$$

and

$$\underset{t\to \infty }{\lim }{q}_t=0,$$

(23)

which can prove that the requirement of uniformly state contraction (cf. Equation (6)) is fulfilled. For example, consider the case of a reservoir with one-neuron as described in Equation (17). Here the challenge is to find an estimator for ${\varphi }_1$ such that

$$\underset{u_t\in \mathbb{R}}{\max }d(\theta (b{y}_t+u_t),\theta (b{x}_t+u_t))\le {\varphi }_1·d(y_t,x_t),$$

where the chosen ${\varphi }_1$ still holds the limit in Equation (22). For $\left|b\right|<1$, convergence can be proven easily:

$$\begin{array}{ccc}\hfill \underset{u_t\in \mathbb{R}}{\max }d(\theta (b{y}_t+u_t),\theta (b{x}_t+u_t))& \le & \hfill \\ \hfill \underset{u_t\in \mathbb{R}}{\max }\left|\right|b{y}_t+u_t-b{x}_t-u_t{\left|\right|}_2& =& \hfill \\ \hfill \left|b\right|·d(y_t,x_t).& \end{array}$$

Thus for $\left|b\right|<1$, one can easily define ${\varphi }_1=\left|b\right|$. So $q_t$ can be defined as

$$q_t={\left|b\right|}^t·d(y_0,x_0).$$

So Equation (23) is fulfilled. The convergence is exponential. The arguments so far are analogous to the core of Jaeger’s proof for the sufficient echo state condition C2 that is restricted to one dimension.

For $\left|b\right|=1$, this argument does not work anymore. Obviously, Jaeger’s proof is not valid under these circumstances. However, the initial theorem can be extended. As a pre-requisite, one can replace the constant ${\varphi }_1$ with a function that depends on $q_t$ as an argument.

So one can try

$${\varphi }_1\left(q_t\right)=1-\eta q_t^{\kappa },$$

where $\eta >0$ and $\kappa >1$ have to be defined appropriately. This works for small values of $q_t$. However, it is necessary to name a limit for large $q_t>\gamma$. Define

$${\varphi }_1\left(z\right):=\left\{\begin{array}{cc}1-\eta z^{\kappa }\hfill & \mathrm{if} z<\gamma \hfill \\ 1-\eta {\gamma }^{\kappa }\hfill & \mathrm{if} z\ge \gamma .\hfill \end{array}\right.$$

(24)

Three things have to be done to check this cover function:

• First of all, one needs to find out if indeed the cover function ${\varphi }_1$ fulfills

  $$\underset{u_t\in \mathbb{R}}{\max }d(\theta (y_t+u_t),\theta (x_t+u_t))\le d(y_t,x_t){\varphi }_1\left(d(y_t,x_t)\right).$$

  In order to keep the proof compatible with the proof for multiple neurons for this work, one has to chose a slightly different application for ${\varphi }_1$,

  $$\underset{u_t\in \mathbb{R}}{\max }{d}^2(\theta (y_t+u_t),\theta (x_t+u_t))\le d^2(y_t,x_t){\varphi }_1\left(d^2(y_t,x_t)\right),$$

  which serves the same purpose and is much more convenient for multiple neurons.
  In Appendix C one can find a recipe for this check.
• Second, one has to look for the convergence of

  $$q_{t+1}=q_t{\varphi }_1\left(q_t\right)=q_t(1-\eta q_t^{\kappa }),$$

  when $q_t\le \gamma$. The analysis is done in Appendix A.
• Third, one needs to check

  $$q_{t+1}=q_t{\varphi }_1\left(q_t\right)=q_t(1-\eta {\gamma }^{\kappa }),$$

  as long as $q_t>\gamma$. Since the factor $(1-\eta {\gamma }^{\kappa })$ is positive, smaller than one and constant, the convergence process is exponential, obviously.

Note that the next section’s usage of the cover function differs slightly even through it has the same form as Equation (24).

5. Sufficient Condition for a Critical ESN

The content of this section is a replacement of the condition C2 where the validity of the ESP is inferred for $S\le 1$.

Theorem 1.

If hyperbolic tangent or the function of Equation (16) are used as transfer functions, the echo state condition (see Equation (6)) is fulfilled even if $S=1$.

Summary of the Proof.

As an important precondition, the proof requires that both transfer functions fulfill

$$d(\theta \left(y_t\right),\theta \left(x_t\right))\le d(y_t,x_t){\varphi }_k\left(d^2(y_t,x_t)\right),$$

(25)

where ${\varphi }_k\left(z\right)$ is defined for a network with k hidden neurons as

$${\varphi }_k\left(z\right):=\left\{\begin{array}{cc}1-\eta z^{\kappa }\hfill & \mathrm{if} z<\gamma \hfill \\ 1-\eta {\gamma }^{\kappa }\hfill & \mathrm{if} z\ge \gamma \hfill \end{array}\right..$$

(26)

Here, $1>\gamma >0,1>\eta >0$, $\kappa \ge 1$ are constant parameters that are determined by the transfer function and the metric norm $d(.,.)={\left|\right|.\left|\right|}_2$ ☐

In Appendix C it is shown that indeed both transfer functions fulfil that requirement. It then remains to prove that in the slowest case we have a convergence in a process with 2 stages. In the first stage, if $d^2(y_t,x_t)>\gamma$ there is a convergence that is faster or equal to an exponential decay. The second stage is a convergence process that is faster or equal to a power law decay.

Proof. 

Note with regard to the test function ${\varphi }_k$:

$$\begin{array}{ccc}& & {\varphi }_k\le 1,\hfill \\ \hfill \forall z,\forall Z:0\le z\le Z& \leftrightarrow & {\varphi }_k\left(z\right)\ge {\varphi }_k\left(Z\right),\hfill \\ \hfill \mathrm{and}\forall z,\forall Z:0\le z\le Z& \leftrightarrow & Z\times {\varphi }_k\left(Z\right)\ge z\times {\varphi }_k\left(z\right)\hfill \end{array}$$

In analogy to Jaeger, one can check now the contraction between the time step t and $t+1$:

$$\begin{array}{c}{d}^2({\mathbf{y}}_{t+1},{\mathbf{x}}_{t+1})=d^2(\theta \left({\mathbf{y}}_{lin,t+1}\right),\theta \left({\mathbf{x}}_{lin,t+1}\right))\hfill \\ \le d^2({\mathbf{y}}_{lin,t+1},{\mathbf{x}}_{lin,t+1})\times {\varphi }_k\left(d^2({\mathbf{y}}_{lin,t+1},{\mathbf{x}}_{lin,t+1})\right)\hfill \end{array}$$

(27)

One can rewrite

$$\begin{array}{c}{d}^2({\mathbf{y}}_{lin,t+1},{\mathbf{x}}_{lin,t+1})=\left|\right|\mathbf{W}{\mathbf{y}}_t+I-\mathbf{W}{\mathbf{x}}_t-{I\left|\right|}_2^2=\left|\right|\mathbf{W}({\mathbf{y}}_t-{\mathbf{x}}_t){\left|\right|}_2^2,\hfill \end{array}$$

(28)

where $I={\mathbf{w}}^{in}{\mathbf{u}}_t$. Next one can consider that one can decompose the recurrent matrix by using singular value decomposition (SVD) and obtain $\mathbf{W}=\mathbf{U}·\mathbf{S}·{\mathbf{V}}^T$. Note that both $\mathbf{U}$ and $\mathbf{V}$ are orthogonal matrices and that $\mathbf{S}$ is diagonal with positive values $s_i$ on the main diagonal. We consider

$$\mathbf{a}={\mathbf{V}}^T({\mathbf{y}}_t-{\mathbf{x}}_t).$$

Because $\mathbf{V}$ is an orthogonal matrix, the left side of the equation above is a rotation of the right side and the length $\left|\right|\mathbf{a}\left|\right|$ is the same as $\left|\right|{\mathbf{y}}_t-{\mathbf{x}}_t\left|\right|$. One can write

$$d^2({\mathbf{y}}_t,{\mathbf{x}}_t)=\sum _i{a}_i^2,$$

where the $a_i$ are entries of the vector $\mathbf{a}$. Since

$${\mathbf{y}}_{lin,t+1}-{\mathbf{x}}_{lin,t+1}=\mathbf{U}\mathbf{S}\mathbf{a}$$

and $\mathbf{U}$ is again a rotation matrix, one can write

$$d^2({\mathbf{y}}_{lin,t+1},{\mathbf{x}}_{lin,t+1})=\sum _i{s}_i^2{a}_i^2,$$

where $s_i$ is the i-th component of the diagonal matrix $\mathbf{S}$, i.e., the i-th singular value.

In the following we define $s_{\max }={\max }_i{s}_i$ and calculate

$$\begin{array}{c}{d}^2({\mathbf{y}}_{lin,t+1},{\mathbf{x}}_{lin,t+1})\times {\varphi }_k\left(d^2({\mathbf{y}}_{lin,t+1},{\mathbf{x}}_{lin,t+1})\right)\hfill \\ =\left({\sum }_i{s}_i^2{a}_i^2\right)\times {\varphi }_k\left({\sum }_i{s}_i^2{a}_i^2\right)\hfill \\ \le \left(s_{\max }^2{\sum }_i{a}_i^2\right)\times {\varphi }_k\left(s_{\max }^2{\sum }_i{a}_i^2\right)\hfill \\ \le \left(s_{\max }^2{d}^2({\mathbf{y}}_t,{\mathbf{x}}_t)\right)\times {\varphi }_k\left(s_{\max }^2{d}^2({\mathbf{y}}_t,{\mathbf{x}}_t)\right)\hfill \end{array}$$

(29)

Merging Equations (27) and (29) results in the inequality

$$d({\mathbf{y}}_{t+1},{\mathbf{x}}_{t+1})\le s_{\max }d({\mathbf{y}}_t,{\mathbf{x}}_t)\times ({\varphi }_k{\left(s_{\max }^2{d}^2({\mathbf{y}}_t,{\mathbf{x}}_t)\right)}^{0.5}.$$

First, assuming $s_{\max }<1$ and since we know ${\varphi }_k\le 1$, we get an exponential decay

$$d(y_n,x_n)\le s_{\max }^{t}d(x_0,y_0).$$

This case is handled by Jaeger’s initial proof. With regard to an upper limit of the contraction speed (cf. Equation (6)), one can find

$$\tau \left(ϵ\right)=\frac{\log ϵ-\log \left(d(y_0,x_0)\right)}{\log s_{\max }}.$$

If the largest singular value $s_{\max }>1$, then for some type of connectivities (i.e., normal matrices) the largest absolute eigenvalue is also larger than 1 due to the spectral theorem. In this case, the echo state condition is not always fulfilled, which has been shown also by Jaeger.

What remains is to check the critical case $s_{\max }=1$. Here again one can discuss two different situations (rather two separate phases of the convergence process) separately:

If $d^2({\mathbf{y}}_{lin,t},{\mathbf{x}}_{lin,t})>\gamma$, we can write the update inequality of Equation (30) as:

$$d^2({\mathbf{y}}_{t+1},{\mathbf{x}}_{t+1})\le (1-\eta {\gamma }^{\kappa })d^2({\mathbf{y}}_t,{\mathbf{x}}_t).$$

Thus, for all ${ϵ}^2\ge \gamma$, the slowest decay process can be covered by

$$\tau \left(ϵ\right)=\frac{2\log ϵ-2\log \left(d(y_0,x_0)\right)}{\log (1-\eta {\gamma }^{\kappa })}.$$

If ${ϵ}^2<\gamma$, then Equation (30) becomes:

$$d^2({\mathbf{y}}_{t+1},{\mathbf{x}}_{t+1})\le d^2({\mathbf{y}}_t,{\mathbf{x}}_t)(1-\eta d{({\mathbf{y}}_t,{\mathbf{x}}_t)}^{2\kappa }).$$

One can replace

$$q_t=d^2({\mathbf{y}}_t,{\mathbf{x}}_t)$$

(30)

and again consider the sequence

$$q_{t+1}=q_t(1-\eta q_t^{\kappa }),$$

which is discussed in Appendix A. The result there is that the sequence converges faster than

$$q_{*}\left(t\right)={[\frac{\eta }{\kappa }t+q_0^{-\kappa }]}^{-1/\kappa }.$$

(31)

Note that, although the Lyapunov exponent (cf. Equation (7)) of $q_{*}\left(t\right)$ is zero, the sequence $q_{*}\left(t\right)$ converges in a power law fashion. Thus,

$$\underset{t\to \infty }{\lim }q\left(t\right)=d^2({\mathbf{y}}_t,{\mathbf{x}}_t)=0$$

(32)

and thus ESP has been proven. ☐

Moreover, one can calculate the upper time limit $\tau \left(ϵ\right)$:

$$\tau \left(ϵ\right)=\frac{\kappa }{\eta }({ϵ}^{-2\kappa }-a_0^{-\kappa }).$$

6. Summary, Discussion and Outlook

The background of this paper is to investigate the limit of recurrent connectivity in ESNs. The preliminary hypothesis towards the main work can be summarized in Figure 6. Initially it is hard to quantify the transition point between uniformly state contracting and non-state contracting ESNs exactly. However, for normal matrices and one-neuron networks the gap between the sufficient condition and the necessary condition collapses in a way that there are two neighboring open sets. The first open set is known to have the ESP, and the other open set evidently does not have the ESP. What remains is the boundary set. The boundary set is interesting to analyze because it can easily be shown that here power law forgetting can occur.

The proof of Section 4 shows a network is an ESN even if the largest eigenvalue of the recurrent connectivity matrix is equal to 1 and if the transfer function is either Equation (15) or (16). The proof is also extensible to other transfer functions. On the other hand it is obvious that some transfer functions result in networks that are not ESNs. For example a linear transfer function ($\theta \left(x\right)=x$) is not state contracting.

Even if the network is state contracting, it is not necessarily exponentially uniformly state contracting. Its rate of convergence might follow a power law in the slowest case. Several examples for power law forgetting have been shown in the present work. More examples of preliminary learning have been outlined in [7]. One important target of the present research is to allow for a kind of memory compression in the reservoir by letting only the unpredicted input enter the reservoir.

One ultimate target of the present work is to find a way to organize reservoirs as recurrent filters with a memory compression feature. In order to bring concepts of data compression into the field of reservoir computing and in order to project as much as possible of the input history to the limit size reservoir, principles of memory compression have to be transferred into reservoir computing. However, the reservoir computing techniques that are analogous to classic memory compression have not been identified so far.

Another topic that needs further investigation is entropy in time series. Power law forgetting is only possible if the time series that relates to the criticality is either of a finite entropy, i.e., from a certain point in time all following entries of the time series can be predicted from the previous entries, or if the network simply ignores certain aspects of the incoming time series.

There also potential analogies in biology. Several measurements of memory decay in humans exist that reveal that there the forgetting follows a power law at least for a large fraction of the investigated examples [20,21].