Echo state networks are universal

Lyudmila Grigoryeva; Juan-Pablo Ortega

Source-linked AI summary

Echo state networks are universal

Lyudmila Grigoryeva, Juan-Pablo Ortega

arXiv:1806.00797v2Jun 3, 2018cs.NEcs.AI

TL;DR

The paper asks whether simple reservoir-computing models can uniformly approximate infinite discrete-time fading-memory filters with uniformly bounded inputs. It combines external approximation by state-affine systems with internal approximation by ESNs, proving that ESNs are universal uniform approximants. The result provides a finite-dimensional neural-network-type state-space realization with a static linear readout within the stated setting.

Problem
The paper addresses universal approximation for infinite discrete-time filters with the fading memory property and uniformly bounded inputs.
Method
The proof combines external approximation by state-affine reservoir systems with internal approximation of reservoir filters by ESNs using neural-network universality.
Results
Echo state networks are universal uniform approximants for discrete-time fading memory filters with uniformly bounded inputs defined on negative infinite times.
Takeaways & Limitations
The result supports approximating the stated class of fading-memory input/output systems with finite-dimensional reservoir models and linear readouts over infinite time intervals.
Takeaways & Limitations
The theorem does not explain the empirically observed robustness of ESNs to randomly chosen architecture parameters; that question remains open.

Abstract

from arXiv · show

This paper shows that echo state networks are universal uniform approximants in the context of discrete-time fading memory filters with uniformly bounded inputs defined on negative infinite times. This result guarantees that any fading memory input/output system in discrete time can be realized as a simple finite-dimensional neural network-type state-space model with a static linear readout map. This approximation is valid for infinite time intervals. The proof of this statement is based on fundamental results, also presented in this work, about the topological nature of the fading memory property and about reservoir computing systems generated by continuous reservoir maps.

1 Introduction

The paper addresses universal approximation for infinite discrete-time fading-memory filters and shows that ESNs provide universal uniform approximants for uniformly bounded inputs. Its proof combines external approximation by state-affine reservoir systems with internal approximation of reservoir filters by ESNs.

Motivation: Universal approximation asks whether a computationally feasible family can approximate every transformation in a sufficiently rich class with arbitrarily small error.The paper situates this question in machine learning and dynamical system identification, where models are learned from input-output observations.
Problem setting: The paper studies discrete-time filters of infinite-length signals with the fading memory property, using reservoir computers defined by finite-dimensional state and readout maps.Reservoir computing translates questions about infinite-dimensional filters into questions about maps on finite-dimensional spaces.
Main result: Echo state networks are shown to be universal approximants for discrete-time fading memory filters with uniformly bounded inputs defined on negative infinite times.The result concerns uniform approximation over infinite time intervals.
Proof strategy: The proof uses external approximation by non-homogeneous state-affine systems, whose linear-readout filters uniformly approximate the target fading-memory filters.This establishes an intermediate reservoir-computing approximation before the ESN approximation step.
Proof strategy: Internal approximation then uses neural-network universality to approximate any reservoir-computing filter, including state-affine-system filters, with an ESN filter.Together, the external and internal steps yield the ESN universality result.
Foundations: The paper characterizes fading memory as continuity in the product topology rather than as a metric property, so the property specifies forgetting qualitatively but not its rate.It also develops conditions for unique reservoir filters, their continuity, and preservation of filter proximity under internal approximation.

2 Continuous and fading memory filters

This section formalizes discrete-time filters and fading memory on uniformly bounded input sequences, showing that the relevant topologies and filter-functional correspondences support the paper’s universality analysis.

Continuity and the fading memory property: Fading memory is characterized as continuity in the product topology on uniformly bounded input sequences, rather than as a metric property tied to one weighting sequence.The paper states that all weighted norms induce the same topology on uniformly bounded sequence sets, making the fading memory property independent of the chosen weighting sequence.
Filters and systems: Causal time-invariant filters correspond bijectively to functionals on left-infinite input sequences through restriction, extension, projection, and time-shift constructions.The maps Ψ and Φ are inverse linear isomorphisms, with HU(z)=U(ze)0 and UH(z)t=H((PZ−◦T−t)(z)).
Filters and systems: A reservoir map satisfying the echo state property generates a causal and time-invariant filter, while system isomorphisms preserve the relevant system implications reversibly.Reservoir computing represents filters through finite-dimensional reservoir and readout maps, linking infinite-dimensional filter questions to simpler state-space maps.
Continuity and the fading memory property: Continuity and the fading memory property transfer between a causal time-invariant filter and its associated functional under the Ψ and Φ correspondences.The paper states this transfer in both directions and restricts the correspondence to the corresponding continuous and fading-memory spaces.
Continuity and the fading memory property: All weighted norms induce the same topology on uniformly bounded sequences, while this coincidence need not extend beyond such bounded sets.For compact input sets, the sequence spaces are also compact and complete under the relevant weighted norms; convexity additionally requires compact convex input domains.

3 Internal approximation of reservoir filters

The section establishes when reservoir filters exist, are unique and continuous, and inherit fading memory, then shows that uniformly approximating reservoir maps yields uniformly approximating filters.

Internal approximation: The associated filter depends continuously on the reservoir map, so sufficiently close reservoir maps produce uniformly close reservoir filters.If the internal map distance is below δ(ϵ) := (1 − r)ϵ, the filter distance is below ϵ.
Existence and continuity: A continuous reservoir map guarantees existence of reservoir solutions for every admissible input, though solutions need not be unique.The proof uses compactness, convexity, continuity, and Schauder’s Fixed Point Theorem.
Existence and continuity: A contraction reservoir map guarantees the echo state property and a unique causal, time-invariant filter with fading memory.The contraction condition is uniform over reservoir states and inputs.
Echo state networks: Echo state networks always have associated generalized reservoir filters, while continuous squashing functions ensure existence and differentiable ones satisfying ∥A∥2 Lσ < 1 ensure ESP and fading memory.For the latter case, the resulting reservoir filter is unique and time-invariant.
Echo state networks: The sufficient condition ∥A∥2 Lσ < 1 is not sharp, although stronger sufficient ESP conditions from prior work also imply fading memory.The paper explicitly identifies this condition as conservative rather than necessary.

4 Echo state networks as universal uniform approximants

The paper proves that echo state networks are universal uniform approximants for discrete-time fading-memory filters, using successive approximations through state-affine systems and feedforward reservoir maps.

Approximation strategy: The internal approximation property reduces approximation of infinite-dimensional reservoir filters to approximation of finite-dimensional reservoir maps.This connects operator-density arguments with standard finite-dimensional approximation theory.
Universality: Echo state networks can uniformly approximate any causal, time-invariant discrete-time filter with the fading memory property.The result applies to filters on infinitely long, uniformly bounded input sequences.
Practical scope: In practice, ESNs typically randomize recurrent and input parameters while training only the readout by linear regression.The universality theorem does not explain the observed robustness to those randomly chosen parameters, which remains open.
Approximation strategy: The proof first approximates a fading-memory reservoir filter by a non-homogeneous state-affine system satisfying contraction conditions.The state-affine system has polynomial reservoir components and a linear readout.
Approximation strategy: A contracting state-affine reservoir map is then uniformly approximated by a one-hidden-layer feedforward neural-network map.The construction controls the approximation on a bounded state-input domain and preserves the state-space range.
ESN construction: The feedforward reservoir is converted into an echo state network by factoring its hidden-layer weights into the recurrent matrix and linear state embedding.The resulting ESN uses a continuous componentwise squashing function and a linear readout.

5 Appendices

The appendices establish time-shift properties of reservoir solutions and relate continuity of filters to continuity of associated functionals.

Appendix results: The echo state property makes the reservoir solution compatible with time shifts of the input sequence.Shifted solutions are identified by uniqueness for the same transformed input.
Appendix results: Conversely, continuity of the input transformation yields continuity of its associated functional.The proof applies the uniform continuity condition to shifted and projected input sequences.
Appendix results: Continuity of an input functional follows from continuity of the corresponding filter under the stated uniform-norm condition.The argument uses a modulus δH(ϵ) controlling output changes when input sequences are sufficiently close.

5.3 Proof of Theorem 2.6

The proof of Theorem 2.6 shows that a weighted metric on bounded negative-time sequences induces the product topology and forms a complete metric space.

Metric properties: The weighted metric satisfies the metric axioms on sequences in (R^n)^Z−.The proof verifies identity, symmetry, and the triangle inequality componentwise.
Topology equivalence: The weighted metric topology therefore coincides with the product topology.Both inclusions between metric balls and product-topology basis sets are established.
Topology equivalence: Weighted-metric neighborhoods contain suitable product-topology basis neighborhoods.The proof chooses a sufficiently large cutoff N so that the weighted tail contributes less than ϵ.
Topology equivalence: Product-topology basis neighborhoods contain weighted-metric balls by restricting the finitely many specified coordinates.The construction uses the minimum of the finitely many coordinate tolerances after weighting.
Completeness: The sequence space is complete under the weighted metric.A Cauchy sequence converges coordinatewise, and the proof then establishes convergence in the weighted metric.
Completeness: The coordinatewise convergence argument is completed by controlling any finite set of coordinates simultaneously.Taking the maximum of the relevant coordinate indices yields eventual membership in each chosen product neighborhood.

5.4 Proof of Corollary 2.7

The proof of Corollary 2.7 identifies the weighted-norm topology on bounded sequence spaces with the corresponding restricted metric topology and the product subspace topology.

Topology on bounded spaces: On the bounded sequence space K_M, coordinate differences are uniformly bounded by 2M.This bound relates the weighted norm to the bounded coordinate metric.
Topology on bounded spaces: The weighted-norm topology on K_M coincides with the restricted weighted metric topology.The equivalence uses the uniform coordinate bound on K_M.
Topology on bounded spaces: The restricted weighted metric topology is the subspace topology inherited from the product topology.This follows from the preceding topology theorem applied to the bounded sequence space.

5.5 Proof of Corollary 2.8

The proof establishes that K_M is compact, closed, complete, and convex under the weighted norm and its associated topologies.

K_M is compact under the product topology by recognizing it as a product of compact spaces and applying Tychonoff’s Theorem.
The product topology on K_M coincides with the topology induced by the weighted norm and the metric D^2_M.
K_M is Hausdorff because the weighted-norm space is metrizable.
As a compact subspace of the relevant Banach space, K_M is closed and therefore complete.
K_M is convex because it is a product of convex sets.

5.6 Proof of Proposition 2.9

The proof compares the weighted-norm topology with the product topology, showing that the norm topology is strictly finer on the sequence space.

Every weighted-norm ball is contained in the corresponding product-metric ball, so the norm topology is finer than the product topology.
The inclusion is strict because the weighting sequence tends to zero, allowing arbitrarily large changes in sufficiently remote coordinates within a D_w-ball.
For a coordinate t_0 with sufficiently small weight, D_w(u,v_λ) remains below ε for every λ>0.
The weighted norm can nevertheless become arbitrarily large as λ increases, preventing any weighted-norm ball from containing that product-metric ball.
Consequently, the norm topology on ℓ_w^−(R^n) is strictly finer than the subspace topology induced by the product topology.

5.7 Proof of Lemma 2.10

Lemma 5.1 proves continuity of shifted-coordinate projections and shows that fading-memory, time-invariant maps on bounded input spaces have uniformly bounded outputs.

The operator P_Z−∘T_−t: K_M→K_M is continuous for every t∈Z−.
Each coordinate projection p_i: (ℓ_w^−(R^n),∥·∥_w)→(R^n,∥·∥) is continuous.
Continuity of the shifted projection follows by expressing it as an infinite Cartesian product of continuous coordinate maps under the product topology.
For a fading-memory map H, continuity on compact K_M makes H(K_M) compact, closed, and bounded, so its outputs lie in some finite-radius ball.
For a time-invariant fading-memory map U, continuity of the zeroth coordinate and time invariance imply U(K_M)⊂K_L for some L>0.

5.8 Proof of Proposition 2.11

The proof identifies fading-memory continuity with continuity under product topologies and establishes equivalences between reservoir maps and their associated filters.

The fading-memory property is equivalent to continuity between the weighted-norm spaces, and therefore to continuity under their product topologies.
By Lemma 2.10, these maps have the fading-memory property with respect to every weighting sequence.
A continuous reservoir map U induces a filter U_H with the fading-memory property through coordinatewise compositions and products of continuous maps.
Conversely, if U has the fading-memory property, its zeroth-coordinate readout H_U=p_0∘U also has the fading-memory property.
The constructions connecting U and H_U are inverse to each other on the corresponding function spaces.

5.9 Proof of Proposition 2.12

The proof establishes continuity for the relevant maps and verifies that the ESN reservoir map is a contraction under the stated norm condition, yielding a unique time-invariant fading memory reservoir filter.

Continuity of Ψ is established using inequality (2.18) together with (5.6).
Continuity of Φ follows from inequality (2.19), with the remaining inequalities proved similarly.
The ESN reservoir map FESN is continuous on the compact, convex state and input domains, so Theorem 3.1 applies.
The bound ∥FESN(x, z) − FESN(y, z)∥ ≤ Lσ∥A∥2∥x − y∥ establishes contraction when Lσ∥A∥2 < 1.
The contraction yields a unique fading memory reservoir filter, and Proposition 2.1 gives its time invariance.

is a Banach space

The proposition proves completeness of the weighted sequence space by showing that every weighted-norm Cauchy sequence converges to an element of the same space.

A weighted-norm Cauchy sequence satisfies a uniform ε-bound beyond a sufficiently large index.
For each fixed negative time, the corresponding sequence of values is Cauchy in R^n and therefore converges.
The pointwise limits form a sequence u, and the weighted estimates show that u belongs to the weighted sequence space.
The original sequence converges to u in the weighted norm, completing the completeness argument.