Title: RECURRENT NEURAL NETWORKS ARE UNIVERSAL FILTERS

Abstract: Recurrent neural networks (RNN) are powerful time series modeling tools in machine learning. It has been successfully applied in a variety of fields such as natural language processing (Mikolov et al. (2010), Graves et al. (2013 ), Du et al. (2015) ), control (Fei & Lu (2017) ) and traffic forecasting (Ma et al. (2015)), etc. In those application scenarios, RNN can be viewed as implicitly modelling a stochastic dynamic system. Another type of popular neural network, deep (feed-forward) neural network has also been successfully applied in different engineering disciplines, whose approximation capability has been well characterized by universal approximation theorem (Hornik et al. (1989 ), Park & Sandberg (1991), Lu et al. ( 2017)). However, the underlying approximation capability of RNN has not been fully understood in a quantitative way. In our paper, we consider a stochastic dynamic system with noisy observations and analyze the approximation capability of RNN in synthesizing the optimal state estimator, namely optimal filter. We unify the recurrent neural network into Bayesian filtering framework and show that recurrent neural network is a universal approximator of optimal finite dimensional filters under some mild conditions. That is to say, for any stochastic dynamic systems with noisy sequential observations that satisfy some mild conditions, we show that (informal)
where xk|k is RNN-based filter's estimate of state x k at step k conditioned on the observation history and E[x k |Y k ] is the conditional mean of x k , known as the optimal estimate of the state in minimum mean square error sense. As an interesting special case, the widely used Kalman filter (KF) can be synthesized by RNN.

1. INTRODUCTION:

Recurrent neural network (RNN) is a certain type of neural networks characterized by hidden variables that memorize the history of input sequences, and it has been successfully applied and brought amazing results in many different disciplines including computer vision, natural language processing and optimal control, etc. (Mikolov et al. (2010) , Graves et al. (2013) , Du et al. (2015) , Fei & Lu (2017) , Ma et al. (2015) ). Its huge empirical success in different engineering disciplines is grounded on the expressive power of RNN. However, how to understand the expressive power of RNN in a quantitative way is not fully understood. Even what RNN expresses is not totally clear. Another type of neural network, deep feed forward neural network has been well characterized as a universal function approximator (Hornik et al. (1989) , Park & Sandberg (1991) ). However, a similar way to characterize the expressive power of RNN is not obvious.

DNN is a mapping from a finite dimensional Euclidean space to another finite dimensional Euclidean space, that is to say it can be regarded as a vector-valued multivariate function. However, RNN is a mapping from a sequence space to another sequence space and the current output depends on both current input and the whole observation history. The input sequence, in principle, can be infinite. The function of RNN is capturing the relationship between input process and output process. For example, in machine translation, the input process (or the observation process) is sentence in one language and the output process (or the state process) is sentence in another language. And in many other RNN's application scenarios such as traffic forecast and optimal control, the input is a noisy observation or measurement sequence and the output is an estimate sequence of a certain quantity, e.g., the traffic speed.. We observe that the function of RNN is quite similar to a filter.

In our paper, we propose to characterize the expressive power of RNN in a quantitative way from the perspective of filtering. We consider a discrete filtering system as 1.

EQUATION

where the state x k at time instant k is an n-dimensional vector, f is an n-dimensional vectorvalued function, g is an n × r matrix-valued function, {w k , k = 0, 1, • • • } is an r-dimensional white Gaussian process and w k ∼ N (0, Q), where Q is the covariance matrix of w k . y k is the m-dimensional observation (measurement) process, h is an m-dimensional vector-valued function, {v k , k = 1, • • • } is an m-dimensional white Gaussian process and v k ∼ N (0, R), where R is the covariance matrix of v k . And we assume that {w k , k = 0, 1, • • • }, {v k , k = 1, • • • } and the initial state x 0 are jointly independent. We use Y k to denote the sequence of observations up to time instant k, i.e.,

EQUATION

Given the realization of the sequence of observations Y k , the aim of filtering problem is to compute the optimal estimate of x k conditioned on Y k .

Not surprisingly, recurrent neural network has been proposed to do filtering. James Ting Ho Lo showed that Recurrent Multi-layer Perceptron can be used to synthesize optimal filter (Lo (1994)).

However, Lo's approach is based on simply copying and storing the whole observation history in the hidden variables and thus require the time horizon to be finite, which is fundamentally limited. Besides Lo's work, many efforts have been made to connect RNN and dynamical system. Wilson & Finkel (2009) implemented a neural network based Kalman Filter (KF) but did not provide theoretical analysis on the approximation error. Parlos et al. (2001) proposed an algorithmic approach to do nonlinear filtering using recurrent neural network architecture but did not provide theoretical gurantee. Schäfer & Zimmermann (2006) shows that recurrent neural network is a universal approximator of dynamical system. However, they only consider the deterministic system dynamics and do not analyze the filtering relationship between two stochastic processes. Around the same time our work was under review, a similar paper was also uploaded in arXiv by Lim et al. (2019) , The results in the arXiv paper are similar to the June, 2018 graduation thesis of the first author of the current paper in the use of sufficient statistics, and emphasize on the design and implementation of the algorithm.

Our current paper has been dramatically improved by introducing the error analysis and asymptotic convergence of the algorithm. And our work is inspired by the finite dimensional filter such as Beneš filter Beneš (1981) .

Compared to the existing work, we make the following specific contributions:

• Motivated by the similarity between RNN and filter, we propose to use the ability to approximate optimal filter to characterize the expressive power of RNN. Unlike existing work on expressive power of RNN (Schäfer & Zimmermann (2006) ) where only deterministic system is considered, we consider a stochastic dynamic system with noisy observations and analyze the capability of RNN to estimate unknown state. • We unify RNN-based filter into Bayesian filtering framework. In this framework, the hidden variables of RNN are interpreted as statistics of the observation history. And the evolution of hidden variables are interpreted as the evolution of statistics. • Based on the Bayesian filtering framework, we derive our main result: Recurrent Neural Networks (RNN) are universal approximators of a large class of optimal finite dimensional filters. That is to say, RNN estimator's asymptotic estimation error can be as close to minimum mean square error as desired. As an interesting special case, the widely used Kalman Filter can be synthesized by RNN. The consideration of asymptotic error differentiates us from existing work on expressive power of RNN (Schäfer & Zimmermann (2006) ).

2. PRELIMINARY: THE BAYESIAN FRAMEWORK OF FILTERING:

We first introduce the definition of minimum mean square error estimate. Proof. Proof can be found in our appendix A.1.

The Bayesian filtering consists of recursive prediction and update procedures (Jazwinski (1970)):

Prediction Step p(x k-1 |Y k-1 ) → p(x k |Y k-1 ): Given the posterior distribution p(x k-1 |Y k-1 ) at instant k -1, the prior distribution p(x k |Y k-1

) of x k satisfies the Chapman-Kolmogorov equation:

p(x k |Y k-1 ) = p(x k |x k-1 )p(x k-1 |Y k-1 ) dx k-1 ;

(3)

Updating Step p(x k |Y k-1 ) → p(x k |Y k ): Given prior distribution p(x k |Y k-1

), when the observation y k at instant k arrives, the posterior distribution p(x k |Y k ) at instant k is given by equation 4,

EQUATION

)

Then we can get the MMSE estimate by simply doing integration:

EQUATION

To facilitate subsequent discussion, we make the following definition. Our RNN based filter's architecture, Bayesian Filter Net (BFN), consists of three parts: prediction network, update network and estimation network. To mimic the prediction step in Bayesian filtering, we use the prediction network to map the posterior distribution representation vector to a prior distribution representation vector. To mimic the update step in Bayesian filtering, we then use an update network to update the prior state distribution representation vector and the observation to get the posterior state distribution representation vector. Finally, we use an estimation network to map the current posterior state distribution representation vector to current estimation xk . We will see in the subsequent discussions, the so-called representation vector or hidden variables indeed can be interpreted as statistics of the underlying conditional distribution. 

4. RNN BASED FILTER IS UNIVERSAL:

We now show that our proposed RNN based filter is universal in that it can approximate a large class of optimal finite dimensional filters to any asymptotic accuracy we desire. We summarize our insight into the diagram 2. 

(x k |Y k-1 ) posterior probability p(x k |Y k ) resp.

of the state at step k by finite dimensional prior statistics s k|k-1 (posterior statistics s k|k resp.). In finite dimensional filter case (Beneš (1981; 1985) ; Daum (1987) ), there exist finite dimensional statistics that are sufficient, that is to say, the evolution of conditional probability can be fully captured by the evolution of a finite dimensional vector. We denote the evolution function in updating step by ϕ and the evolution function in prediction step by φ. And further, after modelling the the probability distribution as finite dimensional statistics, we use two neural networks to approximate the evolution of them. And to get the final estimate of the state, we use another neural network to approximate the map from the statistics to the optimal estimation.

For the RNN based filter, one can naturally ask:

1. Will the neural network approximation error accumulate and blow up when time goes to infinity and make RNN asymptotically not work at all? 2. How general is this approach? What filter can RNN approximate?

We give the answers in this section.

4.1. KALMAN FILTER (KF) CAN BE SYNTHESIZED BY RNN:

When system equation 1 is linear and satisfies Gaussian noise assumption as shown in equation 7, it is well known that the filtering problem can be optimally solved by Kalman Filter (KF) (Kalman (1960) ). (See more details in our Appendix A.3.)

EQUATION

where F, G, H are constant matrices with proper dimensions, the initial state x 0 is Gaussian, and

{w k , k = 0, 1, • • • } and {v k , k = 1, • • • } are two independent white

Gaussian sequences that are also independent of the initial state x 0 .

It can be known that the prior and posterior distributions are Gaussian and fully characterized by the sufficient statistics s composed of mean and covariance matrix. (See more details in our Appendix A.3.)

EQUATION

where m k|k-1 and P k|k-1 are the conditional mean and covariance in step k conditioned on Y k-1 and m k|k and P k|k are the mean and covariance in step k conditioned on Y k , and vec(• n1×n2 ) is the n 1 n 2 × 1 column vector obtained by stacking the columns of the matrix • on top of one another. s k|k (s k|k-1 resp.) is the theoretical statistic that determines the conditional probability distribution of the state x k conditioned on the observation history Y k (Y k-1 resp.) and evolves according to some function ϕ and φ. (See more details in our Appendix A.3.) We also know that there exists some function γ that maps

s k|k to MMSE estimate E[x k |Y k ].

Thus we have,

EQUATION

We use function φ generated by a deep (feedforward) neural network (i.e. update network) to approximate ϕ, and use φ generated by another DNN (i.e. prediction network) to approximate φ.

And the numerical statistics computed by RNN are denoted as sk|k and sk+1|k , i.e., sk|k = φ(s k|k-1 , y k ), sk+1|k = φ(s k|k ).

(10)

And we use function γ generated by the third deep feedforward neural network (i.e. estimation network) to approximate γ in equation 6, i.e.,

EQUATION

We consider the probability space (Ω, F , P) with inner product x, y = E[x T y] and norm

x := E 1/2 [x T x],

which is a Hilbert space and denoted as L 2 (Ω, F , P). We first state the universal approximation theorem of feedforward neural network before we proceed to show our results.

Theorem 2 (Universal Approximation Theorem (Hornik et al. (1989) )). For any given compact subset K ⊂ R n , any given continuous function f defined on K and any given accuracy degree > 0, there exists a function g represented by a single-hidden-layer neural network with non-constant and bounded activation function such that

max x∈K |f (x) -g(x)| < .

Proof. It is a natural corollary of the Thm. 2.1 in Hornik et al. (1989) .

Define e k|k := s k|k -sk|k , which represents the cumulative error caused by the approximation error of φ and φ. Similarly, we define e k|k-1 := s k|k-1 -sk|k-1 . In the following theorem, we shall give the condition which ensures the cumulative error will not blow up as time k approaches ∞.

Before we proceed to show our main result, we first establish a key lemma, Lem. 2. We make two assumptions on the system we'll consider.. Assumption 1. We assume that the linear dynamic system of the state in equation 7 is stable in mean square sense (Samuels (1959)), i.e., lim

EQUATION

)

where M is a finite constant.

Assumption 2. The dynamical system equation 7 is uniformly completely observable and uniformly completely controllable.

The definitions of uniformly completely observable and uniformly completely controllable can be found in section 7.5 of Jazwinski (1970) . We then state a lemma on the boundedness of conditional covariance.

Lemma 1 (Lemma 7.1 in Jazwinski ( 1970)). If Assumption 2 is satisfied and P 0|0 03 , then P k|k is uniformly bounded from above for all k ≥ N ,

EQUATION

)

where N is a positive integer, I is the n × n identity matrix and α, β are positive constants.

Based on Lemma 1, Assumption 1 and Assumption 2, we give the key Lemma 2. Lemma 2. In the discrete linear system equation 7, suppose the Assumption 1 and Assumption 2 are satisfied, then for any given > 0 there exists a compact subset K ⊂ R dim(s k|k ) such that the statistics computed by KF s k|k-1 , s k|k and the statistics sk|k-1 , sk|k computed by RNN based filter with nonconstant and bounded activation function satisfy s k|k-1 1 s k|k-1 ∈K < , s k|k 1 s k|k ∈K < , sk|k-1 1 sk|k-1 ∈K < and sk|k 1 sk|k ∈K < , where 1 A is an indicator function.

Proof. Proof can be found in our appendix A.4.

We then derive our main result. Theorem 3. Assume s k|k , k ≥ 0 are the theoretical statistics evolving according to equation 9 and sk|k , k ≥ 0 are the real statistics computed by our RNN-based filter evolving according to equation 10. Suppose the Assumption 1 and Assumption 2 are satisfied. Furthermore, we need to assume functions ϕ, φ, γ are Lipschitz, i.e., for any

EQUATION

)

where 

Furthermore, we have lim sup

EQUATION

Proof. For any δ > 0, we have the following. By Lem. 3, there exists a compact ball K = B(0, r) ⊂ R dim(s k|k ) , such that s k|k-1 1 s k|k-1 ∈K < δ, s k|k 1 s k|k ∈K < δ, sk|k-1 1 sk|k-1 ∈K < δ and sk|k 1 sk|k ∈K < δ. By Theorem 2, given any small δ ϕ , δ φ ∈ R + and δ γ ∈ R + , there exist two functions φ, φ which are represented by the DNN, such that

EQUATION

)

where h

K ∞ := max x∈K |h(x)|.

And without loss of generality, we set φ(0) = φ(0), ϕ(0) = φ(0) and γ(0) = γ(0). In the prediction step, based on the evolution equations equation 9 and equation 10, we have

EQUATION

where the last inequality follows from equation 14 and equation 17 and C φ is the Lipschitz constant of φ. We let

δ φ := δ φ + (C φ + C φ)δ.

Similarly, in the updating step, we have e k|k ≤ C ϕ e k|k-1 + δ ϕ ,where

δ ϕ := δ ϕ + (C ϕ + C φ)δ.

Combining this and equation 18, we obtain

EQUATION

Using equation 19 repeatedly, it follows that4 

EQUATION

)

Thus lim sup

k→+∞ e k|k ≤ C ϕ δ φ + (C φ + C φ)δ + δ ϕ + (C ϕ + C φ)δ 1 1 -C ϕ C φ as k → ∞ once the condition |C ϕ C φ | < 1 holds.

We choose small enough δ φ , δ ϕ and δ such that

C ϕ δ φ + (C φ + C φ)δ + δ ϕ + (C ϕ + C φ)δ 1 1 -C ϕ C φ < .

Then we get 15. Now we prove

EQUATION

where the inequality 1 follows equation 14 and equation 17, the inequality 2 follows equation 59, and C γ is the Lipschitz constant of γ. Thus lim sup

k→+∞ xk|k -E[x k |Y k ] ≤ C γ (C ϕ δ φ + δ ϕ )(-C ϕ C φ + 1) -1 + δ γ + (C γ + C γ )δ.

Again we can choose small enough δ φ , δ ϕ , δ γ and δ such

that C γ (C ϕ δ φ + δ ϕ )(-C ϕ C φ + 1) -1 + δ γ + (C γ + C γ )δ < .

Then we obtain the desired 16.

An example satisfying all the assumptions of Thm. 3 can be found in our Appendix A.5, and a general class of systems satisfying assumption |C ϕ C φ | < 1 can be found in Appendix A.6. We also remark that in our proof, we implicitly require that the Lipschitz constants of φ, φ, γ are uniformly upper bounded. (See more details in our Appendix A.8) Thm. 3 highlights that the optimal filter in linear system with Gaussian noise, Kalman Filter, can be synthesized by RNN. And RNN based filter's asymptotic error can be as small as wanted under some Lipschitz conditions. That is to say, RNN is an approximator of Kalman filter.

4.2. RNN BASED FILTER IS A UNIVERSAL APPROXIMATOR OF OPTIMAL FINITE DIMENSIONAL:



FILTER:

Thm. 3 shows that Kalman Filter (KF) can be synthesized by RNN. In this section, we'll try to answer the question "How general is the RNN based filter?" and extend the result into a more general case. We'll show that any optimal finite dimensional filter can be universally approximated by RNN under some mild conditions. For a general system with noisy observation as shown in equation 1, once the conditional distribution p(x k |Y k ) is obtained, the filtering problem is solved. However, we usually need to solve an infinite number of ordinary differential equations (ODE) in order to solve p(x k |Y k ).

If the distribution p(x k |Y k ) admits a finite dimensional sufficient statistics, then we only need to solve a finite number of ODE (Chen (2003) ) and we call such filter finite dimensional filter. Finite dimensional filter has been an active research area after the seminal work (Beneš (1981; 1985) ) of Beneš. It's is a large class of filters. Some nontrivial finite dimensional nonlinear filter examples can be found in Daum (1986) ; Ferrante & Runggaldier (1990) ; GÜnther (1981); Levine & Marino (1986) .

Similarly, we use vector S k|k to denote the finite dimensional sufficient statistics of the posterior distribution p(x k |Y k ) and S k|k-1 to denote the finite dimensional sufficient statistics of the prior distribution p(x k |Y k-1 ). The evolution functions of the statistics are denoted as Φ and Ψ, and the map from S k|k to conditional mean E(x k |Y k ) is denoted as Γ, i.e.,

EQUATION

Similarly, in our proposed neural networks, we use DNN generated function Φ (prediction network) to approximate Φ, use another DNN generated Ψ (update network) to approximate Ψ, and use the third DNN generated function Γ to approximate Γ. And the numerical statistics computed by RNN are denoted as Sk|k and Sk|k-1 , i.e., Sk|k-1 = Φ( Sk-1|k-1 ), Sk|k = Ψ( Sk|k-1 , y k ), xk|k = Γ( Sk|k ).

(23) We also need the following assumption. Assumption 3. We assume that for any given > 0 there exists a compact subset K ⊂ R dim(S k|k ) such that the statistics computed by the optiaml finite dimensional filter S k|k-1 and S k|k satisfy S k|k-1 1 S k|k-1 ∈K < , and S k|k 1 S k|k ∈K < .

We can see equation 7 is the special case of system equation 1, and it satisfies the Assumption 3 according to Lemma 2. We further have Lem. 3 and Thm. 4. Lemma 3. In the discrete system equation 1, for any given > 0 there exists a compact subset K ⊂ R dim(S k|k ) such that the statistics Sk|k-1 , Sk|k computed by RNN based filter with non-constant and bounded activation function satisfy Sk|k-1 1 Sk|k-1 ∈K < and Sk|k 1 Sk|k ∈K < , where 1 A is indicator function.

Proof. The proof is similar to the step 2 of the proof of Lem. 2.

Theorem 4. Consider a discrete filtering system equation 1 with optimal finite dimensional filter and suppose S k|k , k ≥ 0 are the theoretical statistics evolving according to equation 22 and Sk|k , k ≥ 0 are the statistics generated by our RNN based filter and evolving according to equation 23. Suppose the Assumption 3 is satisfied. Furthermore, we need to assume that functions Φ and Ψ are Lipschitz, i.e., for any S 1 , S 2 , Furthermore, we have lim sup

EQUATION

EQUATION

)

Proof. The procedure is similar to the proof of Theorem 3.

Thm. 4 highlights that RNN based filter can not only approximate Kalman filter, but any optimal finite dimensional filter under some Lipschitz conditions. Therefore, RNN's expressive power is characterized as the universal filtering property.

5. CONCLUSION:

In our paper, we try to characterize the expressive power of RNN from the filtering perspective. We unify the recurrent neural network into Bayesian filtering framework and show that recurrent neural network is a universal approximator of optimal finite dimensional filters under some Lipschitz conditions. As an interesting special case, the widely used Kalman filter can be synthesized by RNN. Understanding the expressive power of RNN based filter in more general nonlinear filtering cases (with no finite dimensional sufficient statistics) can be a very interesting future direction.

Xiaolei Ma, Zhimin Tao, Yinhai Wang, Haiyang Yu, and Yunpeng Wang. Long short-term memory neural network for traffic speed prediction using remote microwave sensor data. 

A APPENDIX:

A.1 PROOF OF THEOREM 1

Proof. It is known that

EQUATION

and let

EQUATION

and

E (x k -µ k ) T (x k -µ k ) (29)

is independent of xk , equation 27 becomes

E[L M SE ] =E E (x k -xk ) T (x k -xk ) Y k =E E (x k -µ k + µ k -xk ) T (x k -µ k + µ k -xk ) Y k =E E (x k -µ k ) T (x k -µ k ) + (µ k -xk ) T (µ k -xk ) +2(x k -µ k ) T (µ k -xk ) Y k =E (x k -µ k ) T (x k -µ k ) + E (µ k -xk ) T (µ k -xk ) =const + E (µ k -xk ) T (µ k -xk ) (30) Therefore E[L M SE ] is clearly minimized by setting xk = µ k = E[x k |Y k ].

A.2 THE EVOLUTION OF DISTRIBUTION IN UPDATING STEP OF BAYESIAN FILTER:

Let p(x k |Y k ) denote the conditional distribution of state x k conditioned on the observation history Y k , then using Bayes' rule, we have:

EQUATION

It can be seen that the posterior distribution p(x k |Y k ) is determined by the prior distribution p(x k |Y k-1 ) and likelihood function p(y k |x k ), which depends on the observation model and the known distribution of v k .

A.3 THE EVOLUTION FUNCTION OF STATISTICS FOR KALMAN FILTER:

The widely used Kalman Filter assumes that the posterior distribution at every instant is Gaussian, and then it can be parameterized by the mean and covariance. We consider the following system:

EQUATION

where F, G, H are constant matrices with proper dimensions, the initial state x 0 is Gaussian, and {w k , k = 0, 1, • • • } and {v k , k = 1, • • • } are two independent white Gaussian sequences that are also independent of the initial state x 0 jointly.

Then KF can be viewed as the following recursive relationship:

EQUATION

where in the prediction step,

EQUATION

in the updating step,

           m k|k = m k|k-1 + P k|k-1 H T (HP k|k-1 H T + R) -1

• (y k -Hm k|k-1 )

EQUATION

and N (x; m, P ) is a Gaussian distribution with mean m, and covariance P . The evolution functions of mean and covariance in the prediction step and updating step can be expressed in the following compact form:

EQUATION

EQUATION

where φ 1 , φ 2 , ϕ 1 and ϕ 2 are defined as

EQUATION

and ϕ 1 (m, P, y) := m + P H T (HP H T + R) -1 (y -Hm) ϕ 2 (m, P, y) := P -P H T (HP

EQUATION

Here,

EQUATION

) are the conditional means of state conditioned on observation history.

P k|k-1 = E (x k -m k|k-1 )(x k -m k|k-1 ) T |Y k-1 , P k|k = E (x k -m k|k )(x k -m k|k ) T |Y k (41)

are the corresponding conditional covariance. Then we know that the posterior distribution p(x k |Y k ) is parameterized by the conditional mean m k|k and covariance P k|k which are functions of Y k , i.e., p(x k |Y k-1 ) is parameterized by {m k|k , P k|k }. And the similar conclusion can be obtained for prior distribution p(x k |Y k-1 ).

Now we vectorize {m k|k , P k|k } as the statistics

EQUATION

Vectorizing the second equation in equation 36 and equation 37, we have 

where we omit subscript characters without causing confusion, and vec -1 n1×n2 is the inverse operator of vec such that vec -1 n1×n2 (vec(• n1×n2 )) = • n1×n2 . Then we obtain the evolution functions of the statistics: Step 1: It can be known from the KF that the evolution function for conditional covariance is as follows (see appendix):

EQUATION

EQUATION

and the initial value is P 0|0 . It follows that the conditional covariance P evolves in a deterministic manner and without any randomness according to the evolution equation equation 46, therefore P is independent of the observations. Since

P k|k = E x k -m k|k x k -m k|k T Y k ,

and P k|k is independent of Y k , we have

EQUATION

According to Lemma 1, we have

EQUATION

)

where N is a positive integer and α, β are positive constants. It can be easily checked that, there exists a positive constant α 0 , such that

EQUATION

)

According to equation 47, we have

EQUATION

where tr( ) denotes the trace of matrix . Combining equation 49 and equation 50, we know that

EQUATION

Then according to equation 12 and equation 51, we have

EQUATION

where C 0 is a positive constant and can be chosen to be √ nα 0 + M . Now we have the conclusion that m k|k and P k|k are bounded for all k ≥ 0. Similarly, we know that m k|k-1 and P k|k-1 are all bounded following the similar procedure as above. According to equation 8, we know that all sufficient statistics s k|k-1 , s k|k are bounded.

Step 2: We then prove that sk|k-1 1 sk|k-1 ∈K < and sk|k 1 sk|k ∈K < . Recall that

EQUATION

where φ and φ are approximating functions generated by neural networks with non-constant and bounded activation functions. Let σ denote the activation functions used by the neural network and assume that |σ(x)| < C σ , ∀x ∈ R. And without loss of generality, we assume φ(s k|k-1 , y

k ) = V 1 σ(W 1 p 1 (s k|k-1 , y k ) + b 1 ) + c 1

, where p 1 is the vector valued function that takes input to the last hidden layer's output, V 1 and W 1 are matrices with suitable dimension, b 1 is a vector with suitable dimension. Then we'll have,

EQUATION

where dim(x) is the dimension of the vector of x. We choose the compact set K to cover the compact ball {x ∈ R dim(s k|k ) :

x E ≤ V 1 dim(b 1 )C σ + c 1 } where E denotes Euclidean norm

of . Then it can be seen that sk|k-1 1 sk|k-1 ∈K < . And sk|k 1 sk|k ∈K < can be shown in a similar way.

A.5 AN EXAMPLE THAT SATISFIES ALL THE ASSUMPTIONS OF THM. 3:

Here we verify that the system shown in equation 55 with state's dimension 1 satisfies all assumptions in Theorem 3.

EQUATION

where 0 < α < 1 is a small positive parameter.

• As for Assumption 1, from the state equation of equation 55 we have

EQUATION

then we have

EQUATION

It can be easily checked that Assumption 1 is satisfied. • As for Assumption 2, it can be easily checked that system shown in equation 55 satifies Assumption 2 using the definitions of uniformly completely observable and uniformly completely controllable in section 7.5 of Jazwinski (1970). 

EQUATION

where a, g, b are constants, ∆t = t k -t k-1 << 1 is the step size of sampling, {w k , k = 1, • • • } is an 1-dimensional white Gaussian process and w k ∼ N (0, Q), and {v ∆ t k } is 1-dimensional white Gaussian process with distribution N (0, R/∆t). According to Jazwinski (1970), we know that the discrete observation system in equation 58 is the sampled system of continuous observations. Following equation ( 34)-( 35) in Appendix A.2, we have φ 1 (m, P ) = am, φ 2 (m, P ) = gQg + a 2 P,

and ϕ 1 (m, P ) = m + K(y -b∆tm), ϕ 2 (m, P ) = P -Kb∆tP, where K = P b(∆t) 2 ((b∆t) 2 P ∆t + R) -1 . It can be easily checked that ∇φ = a 0 0 a 2 , ∇ϕ = 1 -Kb∆t (y -∆tm) ∂K ∂P 0 1 -Kb∆t -b∆tP ∂K ∂P , where ∂K ∂P = (b∆t) 2 R((b∆t) 2 P ∆t + R) -2 . Then we have C φ = max{a, a 2 }, C ϕ = E ∇ϕ 2 ≤ E ∇ϕ F = 1 + O(∆t),

where • F is the Frobenius norm.

If a < 1, which is a very natural stable condition, then lim

∆t→0 |C ϕ C φ | ≤ lim ∆t→0 |(a + O(∆t)) = a < 1.

Apparently, we have |C ϕ C φ | < 1 with small step size ∆t.

Algorithm 1 Bayesian Filter Net (BFN) training algorithm 1: Setting the sampling path number N , the number of simulated steps M, the optimization horizon length l and the learning rate λ 2: Sampling x 0 (ω i ) i.i.d from the initial distribution σ 0 (x) and set y 0 (ω i ) = 0 3: for 0 ≤ m ≤ M l -1 do 4:

Initialize loss(θ) to be 0 5:

for ml ≤ k < (m + 1)l do 6:

for 1 ≤ i ≤ N do 7:

x k+1 (ω i ) ← -f (x k (ω i )) + g(x k (ω i ))w k-1 (ω i ) 8: y k+1 (ω i ) ← -h(x k+1 (ω i )) + v k (ω i ) 9:

end for 10:

for 1 ≤ i ≤ N do 11:

Feed the sampled y k+1 (ω i ) to the Bayesian-Filter-Net(BFN) and get the corresponding output xk+1 (ω i )

12:

Add the estimation squared error to the loss function loss(θ) ← -loss(θ) + xk+1 (ω i -x k+1 (ω i )

2 2

13:

end for 14:

end for 15:

Doing back propagation and update the network parameters θ ← -θ -λ∇ θ loss(θ) 16: end for where α < 1 is a small positive parameter controlling the changing rate of the system state, I n is a n × n identity matrix and A n is a matrix with elements a ij satisfying a ij = 1, if i = j + 1, -n i-1 , if j = n and 0, otherwise. From Fig. 3a , we can see that as the number of training epochs increase, RNN-based filter's MSE decrease and finally converge. And from Fig. 3b as the dimension of the hidden variable increases, the converged MSE decreases. The results in Fig. 3 highlight that just with the number of 90 hidden variables, RNN based filter can achieve the performance of Kalman filter. Considering that there are 65 independent statistics in this case, this is a very efficient approximation.

A.9.4 RNN BASED FILTER CAN STILL WORK FOR INFINITE DIMENSIONAL FILTER:

For finite dimensional filter, our analysis has shown that RNN based filter is a universal approximator of optimal filter. In this subsection, we show that in infinite dimensional filter case (where finite dimensional statistics are not admitted to fully determine the distribution), our RNN based method achieves even better performance to state-of-the-art spectral method Luo & Yau (2013) . We consider a special and well-known infinite dimensional case.

EQUATION

)

where α is a positive parameter controlling the change rate of the system. We set the α to be 0.01, the total sampling steps to be 5000, the number of sampled paths to be 1000, the number of training epochs to be 100. We only use two fully connected layers for the prediction network, update network and estimation network. compare our algorithm's performance with existing state-of-the-art spectral method. Our proposed DFN's TPMSE is 0.18, which is much smaller than spectral method's TPMSE 0.40. One potential reason for its RNN's applicability in infinite dimensional filter case is that RNN implicitly learns the most relevant finite dimensional statistics.

:

The sufficient statistic s k|k (or s k|k-1 ) can be any vector-valued function of Y k (or Y k-1 ) as long as it can fully determine p(x k |Y k ) (or p(x k |Y k-1 )). Taking linear system as an example, s k|k can be the vector composed of the conditional mean and covariance because these two quantities sufficiently determine the conditional density function of the state in linear filtering system. (See more details in our AppendixA.3.)

For instance, as for the Kalman Filter in linear system, the sufficient statistic s k|k can be chosen to be the conditional mean and conditional covariance, thus γ function can be the function that copy the conditional mean part of s k|k .

Here, X Y (X Y resp.) if and only if X -Y (Y -X resp.) is positive semi-definite, where X and Y are symmetric matrices.

See more details in our Appendix A.7.

Figures and Tables:

Figure 2: Our approach's illustrative diagram

C ϕ and C φ are Lipschitz constants. If C ϕ and C φ satisfy |C ϕ C φ | < 1, then for any > 0, there exists an RNN based filter (with non-constant and bounded activation function) such that lim sup k→∞ e k|k = lim sup k→∞ s k|k -sk|k < .

24)where C Ψ and C Φ are Lipschitz constants. If C Ψ and C Φ satisfy |C Ψ C Φ | < 1, then for any > 0, there exists a RNN based filter with non-constant and bounded activation function such that lim sup k→∞ S k|k -Sk|k < .(25)

(m, P, y) vec(ϕ 2 (m, P, y)) = ϕ 1 (m, vec -1 (vec(P )), y) vec(ϕ 2 (m, vec -1 (vec(P )), y)) ϕ(m, vec(P ), y) = ϕ(s, y), (43) and φ 1 (m, P ) vec(φ 2 (m, P )) φ(m, vec(P )) = φ(s),

45) where ϕ and φ are defined in equation 43 and equation 44. A.4 PROOF TO LEM. 2 Proof.

CLASS OF SYSTEM THAT SATISFIES |C ϕ C φ | < 1 IN THEOREM 3 Actually this condition |C ϕ C φ | < 1 can be satisfied by a general class of systems. Let us consider the 1-dimensional linear systems with discretization in continuous observation equation, i.e.,

Figure 3: (a) The decrease of TPMSE of RNN based filter with different hidden variable dimensions in training. (b) Convergent TPMSE of RNN based filter with different dimensions of hidden variables.

Figure 4: (a) The evolution of PMSE k . (b) xk tracks x k well.

Definition 1 (Minimum Mean Square Error (MMSE) Estimate (Jazwinski (1970))). Let x be an estimate of random variable x and L MSE := (x -x) T (x -x). The estimate that minimizes E[L MSE ] is called the minimum mean square error estimate. Theorem 1(Theorem 5.3 in Jazwinski (1970)). Conditioned on the observation history Y k , the minimum mean square error estimate of state x k is the conditional mean E[x k |Y k ].

Table content: <table/>

Definition 2 (Sufficient Statistic (Beneš (1981))). If the conditional distribution p(x k |Y k ) (or p(x k |Y k-1 )) can be fully determined by a vector-valued function s k|k (or s k|k-1 ) of the observation sequence Y k (or Y k-1 ), then we say s k|k (or s k|k-1 ) is a sufficient statistic for p(x k |Y k ) (or p(x k |Y k-1 )). 1 Because sufficient statistic s k|k fully determines the posterior distribution p(x k |Y k ) and MMSE estimate E(x k |Y k ) is a functional of p(x k |Y k ), there exists a function γ that maps s k|k to E[x k |Y k ],

Table content: <table><tr><td/><td>2</td></tr><tr><td>i.e.,</td><td/></tr><tr><td>E[x k |Y k ] = γ(s k|k ).</td><td>(6)</td></tr><tr><td>3 RNN BASED FILTER'S ARCHITECTURE</td><td/></tr><tr><td colspan="2">Motivated by the Bayesian framework of filtering, we propose the RNN based filter's architecture as</td></tr><tr><td>shown in Fig. 1.</td><td/></tr></table>



Table content: <table><tr><td>Figure 1: RNN based filter's architecture: Bayesian Filter Net (BFN) .</td></tr></table>

Transportation Research Part C: Emerging Technologies, 54:187-197, 2015. Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černockỳ, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association, 2010. Anton Maximilian Schäfer and Hans Georg Zimmermann. Recurrent neural networks are universal approximators. In International Conference on Artificial Neural Networks, pp. 632-640. Springer, 2006. Robert Wilson and Leif Finkel. A neural implementation of the kalman filter. In Advances in neural information processing systems, pp. 2062-2070, 2009.

Table content: <table><tr><td>Jooyoung Park and Irwin W Sandberg. Universal approximation using radial-basis-function networks.</td></tr><tr><td>Neural computation, 3(2):246-257, 1991.</td></tr><tr><td>Alexander G Parlos, Sunil K Menon, and A Atiya. An algorithmic approach to adaptive state filtering</td></tr><tr><td>using recurrent neural networks. IEEE Transactions on Neural Networks, 12(6):1411-1432, 2001.</td></tr><tr><td>J Samuels. On the mean square stability of random linear systems. IRE Transactions on Circuit</td></tr><tr><td>Theory, 6(5):248-259, 1959.</td></tr></table>

Peer review (iclr2020):
This paper shows that RNN (of infinite horizon) can be universal approximators for any stochastic dynamics system. It does that by using the Bayesian framework of filtering, which shows that if sufficient statistics given the observations so far can be computed at each stage of filtering, then the expected hidden states at each stage can be estimated as well. The paper then follows this framework by constructing deep neural network mapping from “observations so-far” to “sufficient statistics” and by universal approximation theorem this is possible. Then as long as after each stage, the image of such a mapping is bounded into a certain region, and if the mapping is contractive (|C_psi C_phi| < 1), this can be applied to arbitrarily long sequence (and thus infinite horizon). The paper is well-written and easy to follow. However, I have concerns about its novelty. Overall the paper seems to be a straightforward application of universal approximation theorem of deep neural network. The authors don’t specify when the condition will hold (e.g., |C_psi C_phi| < 1), what kind of empirical RNNs fall into this category and whether the trained models are operating in the contractive region. Also with the same technique the authors also reach the same conclusion for nonlinear dynamics system (Sec. 4.2). From the proof, there is no much difference between linear case (Kalman Filter) and nonlinear case, since apparently DNN can fit everything. Then what are the new discoveries and takeaway messages? It is not clear what can we learn from this analysis and its impact is likely to be limited.