Learning Input and Recurrent Weight Matrices in Echo State Networks

Echo State Networks (ESNs) are a special type of the temporally deep network model, the Recurrent Neural Network (RNN), where the recurrent matrix is carefully designed and both the recurrent and input matrices are fixed. An ESN uses the linearity of the activation function of the output units to simplify the learning of the output matrix. In this paper, we devise a special technique that take advantage of this linearity in the output units of an ESN, to learn the input and recurrent matrices. This has not been done in earlier ESNs due to their well known difficulty in learning those matrices. Compared to the technique of BackPropagation Through Time (BPTT) in learning general RNNs, our proposed method exploits linearity of activation function in the output units to formulate the relationships amongst the various matrices in an RNN. These relationships results in the gradient of the cost function having an analytical form and being more accurate. This would enable us to compute the gradients instead of obtaining them by recursion as in BPTT. Experimental results on phone state classification show that learning one or both the input and recurrent matrices in an ESN yields superior results compared to traditional ESNs that do not learn these matrices, especially when longer time steps are used.


Introduction
Recurrent Neural Networks (RNNs) belong to a general type of deep neural networks which are used to model time sequences and dynamical systems [1,2,3,4,5,6]. Echo State Networks (ESNs) belong to the general class of the RNNs [7,8,9,10]. The following properties of an ESN make it distinct from other types of RNNs. First, both the recurrent and input matrices in an ESN are fixed and not learned (this is largely due to the difficulty in learning RNN [11,12]. Second, the number of hidden neurons in an ESN is typically much larger than those in regular RNNs. The main challenges of training RNNs described in [11,12] is avoided in ESN by not training most of the very large number of difficult network parameters. This also leads to avoiding potential overfitting problems. Third, the output units, also called readout units, in an ESN are linear. This is unlike the typically nonlinear output units in regular RNNs. Given the very large number of hidden neurons of an ESN, the output or readout weight matrix is very large as well. The use of linear output units allows the output weight matrix to be learned very efficiently and with a simple regularization mechanism based on ridge regression. Fourth, the learning of the ESN parameters (i.e. output matrix) is much simpler than that for regular RNNs. The former uses linear learning with convex optimization, and the latter, is based typically on Back Propagation Through Time (BPTT) and is highly nonlinear and non-convex. As a result, learning the ESN parameters can be effectively carried out via batch training. This greatly facilitates parallel implementation. Learning the general RNN parameters on the other hand, typically requires stochastic gradient descent, and is more difficult for parallelization.
The simplicity in ESN learning comes at the cost of not learning some important parameters (including the input and the recurrent weight matrices) and of using linear output units. While the special design of the recurrent matrices (see [13]) and the use of a large number of hidden neurons help in reducing the weakness of using fixed parameters, it is desirable to make these parameters adapt to the data. This is as long as the required learning remains simpler and more parallelizable than the common BPTT learning method applied to regular RNNs. This paper presents this type of learning for the input and recurrent matrices of ESNs. We propose a technique that makes full use of the linearity in the output units when constructing constraints on all three input, output, and recurrent matrices in an ESN. The constraints enable us to compute the gradients as the learning signal in an analytical form, and this makes the gradient estimate more accurate than when computed by recursion as in BPTT. Our preliminary experimental results on phone classification are highly positive. It is demonstrated that learning one or both of the input and recurrent matrices in an ESN gives better phone classification accuracy than that obtained by a traditional ESN without learning them. Furthermore, when longer time steps are used in analytically computing the gradients, the better classification results are obtained.

General Recurrent Networks and Specific Echo State Networks
A general RNN has temporal connections as well as input-to-hidden layer, hidden layer-to-output connections. These connections are mathematically represented by the recurrent weight matrix W rec , the input weight matrix W, and the output weight matrix U, respectively. The RNN architecture is illustrated in Fig. 1. It also includes input-to-output and output-to-hidden (feedback) connections, with the latter denoted by W f b . The sequential sections of Fig. 1(a), 1(b), 1(c), . . . , denote the RNN as it unfolds in time. Note that all the weight matrices are constrained to be the same (i.e. they are tied) at any discrete point in time.

Wfb
Wfb Wfb Wfb  In Figure 1, x i , h i and y i represent the input, hidden and output vectors at discrete time t = i. Again, the connections between the input (x i ) and hidden (h i ) layers, the hidden and output (y i ) layers, and the output and hidden layers are represented by W, U and W f b respectively. The temporal connection between h i and h i+1 is represented by the matrix W rec . Note that the direct connections from the input to the output layer form a part of the matrix U; i.e., it is equivalent to concatenating the input layer with the hidden layer.
There are two standard methods to train RNNs, BPTT and the method based on Extended Kalman Filtering (EKF) [13]. BPTT is a first order method, which extends error backpropagation for feedforward networks by treating each time step as a new hidden layer ( but ties all the weight matrices across time). Generally, BPTT has slow convergence. Its difficulty in capturing long-term memory due to vanishing gradient and exploding gradient problems has been well known for many years [11]. It is often non-trivial to obtain good results with BPTT; see the tremendous amount of engineering required to make BPTT work [2,14,15]. The EKF-based method, on the other hand, has fast convergence properties and belongs to a second-order method. However, the computational requirements of the EKF method are high and its implementation is non-trivial [13], especially for large-scale problems.
One prominent approach that has been proposed to overcome the difficulty in training RNNs is the ESN [9], [13]. As explained above, an ESN is a special type of RNNs whose recurrent weights (W rec ) and input to hidden layer weights (W) are fixed and only U ( that represents the hidden layer to output and the input to output weights ) is trained. The recurrent connections in W rec are sparse and their values are carefully fixed in a way that the echo-state property is preserved. ESNs can be trained very fast because the only connections that are trained are the output connections. With good initialization, ESNs have been shown to yield good performance for one dimensional sequences; but for high dimensional data such as speech, the studies have been relatively limited; please see [10].
Since the output units in an ESN have a linear activation function and assuming the hidden units have a sigmoid activation function, the formulation of an ESN as a special type of RNNs ( as shown in Fig. 1 ) can be succinctly described by 1+e −x . As discussed earlier, an ESN has a special designed recurrent matrix, which is endowed with the echo state property in most existing versions [13,9,10]. The echo state property implies that the state, or the hidden units' activities, of the network can be determined uniquely based on the current and previous inputs and outputs provided the network has been running for a sufficiently long time. The formal definition of echo states is described in [13]. Assume that the maximum eigenvalue of W rec is λ max , the activation function of the hidden units is sigmoid and | λ max |> 4, then the network does not have echo states. This is a sufficient condition for the echo states to not exist 1 [13]. However, as emphasized in [13], in practice, when | λ max |< 4 the network has echo states. There is a similar sufficient condition under which the exploding gradient problem for recurrent weights would not happen [16].
In ESN training, only the output weight matrix, U, is trained. The input and recurrent weight matrices should be carefully fixed. There are three main steps in training an ESN: constructing a network with the echo state property, computing the network states, and estimating the output weights.
To construct a network with the echo state property, the input weight matrix W and the sparse recurrent weight matrix W rec are randomly generated. Then, the maximum eigenvalue of W rec is calculated and all entries of W rec are renormalized as follows: where λ < 4 for sigmoid activation function. λ is also an important parameter which affects the memory length of the network and should be determined based on the required memory size for the specific task. As emphasized in [13], the entries of the input weight matrix are also of great importance; large entries cause most hidden units to saturate while small entries lead hidden units to stay in the linear region of the sigmoid function. The value of λ should be predetermined and fixed ( based on the desired task ) before the second step (that calculates the network states).
To find the outputs of the hidden layer units, the hidden states are initialized to zero or another initial state. Then the network runs freely for i trans time steps where the hidden states of each time step are calculated using (1)  To calculate the output weights U, we stack the desired outputs or targets corresponding to input signal x i as a matrix T; i.e., Since H is computed using all known quantities (incluidng the fixed input and recurrent matrices) using (1) and hence it is known also, U can be obtained by minimizing the following mean-squareerror cost function: where F stands for the Frobenius norm of a matrix, tr(.) is the trace of a matrix and Minimizing (6), we have the globally optimal estimate of U determined by setting the gradient of the above cost function to zero and solving it; i.e., In practical implementation, to prevent inaccurate results when HH T is singular or close to singular, the following solution of "ridge regression" is used for estimating U: where I is the identity matrix and µ is a fixed positive number.

Learning the Input Weight Matrix in ESN
Assuming the memory of the network extends back to m time steps, we use the following notation to facilitate the development of the learning method for the input weight matrix W: Therefore, equations (1) and (2) can be written as: To find the gradient of the cost function E with respect to W and learn input weights W we consider two cases in the remainder of this section. In Case 1, we assume that U does not depend on W and in Case 2 we take into account the dependency between U and W. Note that in both cases we take into account the time dependency among the hidden state vectors in H, i.e., the dependency of h i+1 on h i at every time step i 2 . Since Case 2 is a more realistic formulation of the gradient, it is used for learning the input weight matrix in our experimental results presented in Section 5. We derive the gradient for one time step dependency and then generalize it to n time step dependency, i.e., H i depends on H i−1 , H i−2 and so on up to n time steps.

Case 1
The gradient of the cost function with respect to W can be written as Assuming that H 1 depends on W, i.e., H 1 = σ(W rec H 0 + W T X 1 ), and denoting the term independent of W by: then using chain rule of calculus we have: and therefore where • is element-wise multiplication.

Case 2
The gradient calculated in Case 1 is not accurate because the dependency between U and W is ignored. To take this dependency into consideration, the first line of equation (13) is rewritten as: Since tr(AB) = tr(BA) and tr(A) = tr(A T ) we have Using the chain rule presented in equation (126) of [20], the gradient can be written as: Below we first calculate matrix A and then matrix B.
For constant values of hidden states H 2 we define F, M and S as follows: Then, using the chain rule again, we obtain considering the fact that tr(AB) = tr(BA), A 1 can be written as From equation (107) of [20] we have Since F T = F and M T = M, A 1 can be written as Considering equation (114) of [20], A 2 will be as follows substituting S and using M = M T results in Now substituting M and F in (23) results in the final formulation for A as follows To calculate B, we assume that there is just one time step dependency, i.e., H 2 depends on H 1 and W and H 1 does not depend on H 0 but depends on W. The generalization to an arbitrary number of time steps is straightforward and is presented at the end of this section. From (22) and (11) we write B as: which is similar to the term calculated in (16) and therefore By substituting (30) and (32) in (22) we get the gradient formulation for one time step dependency as follows: This gradient formulation can be generalized for an arbitrary number of time steps as follows: where n is the number of time steps and To calculate A using (30), H n and T n are used.
After calculating the gradient of the cost function w.r.t W, the input weights W are updated using the following update equation where α is the step size and and where the initial value for m old and m new is 1. The third term in (36) helps the algorithm to converge faster and is based on the FISTA algorithm proposed in [21] and used in [19].

Learning the Recurrent Weight Matrix (W rec ) in the ESN
To learn the recurrent weights, the gradient of the cost function w.r.t W rec should be calculated. We first derive the formulation for the two time steps dependency, i.e., H 2 depends on H 1 and H 1 depends on H 0 but no more time dependencies. Then it will be generalized to the arbitrary number of time steps. The same method that is used in section 3 can be used to get the following formulation for the gradient: A will be the same as (30). To calculate B we have and therefore the gradient will be: It can be generalized for arbitrary number of time steps as follows: where H 0 includes the initial hidden states and and A is calculated using (30) based on H n and T n .
Only the non-zero entries of the sparse matrix W rec are updated using (36) and the gradient calculated in (41). To make sure that the network has the echo state property after each epoch, the entries of W rec are renormalized such that the maximum eigenvalue of W rec is λ that is predetermined in (3). This renormalization also prevents the gradient explosion problem for recurrent weights from happening.
A summary of the learning method is as follows: • The echo state network with predetermined maximum eigenvalue of W rec is constructed based on the explanations presented in section 2. • Input weights matrix W is updated based on (34), (35), (36) and (37).
• Non-zero entries of the sparse recurrent weights matrix W rec are updated based on (41), (42), (36) for W rec and (37). • Updated W rec is renormalized to have the predetermined maximum eigenvalue λ.
• The forward pass is repeated with the updated input and recurrent weights to find the hidden states. The network runs freely for i trans time steps and then the hidden states are recorded as matrix H. • Taking into account the direct connections from the input to output in the network, the output weight matrix U is calculated using (9).
To prevent the value of the gradient w.r.t W from exploding, we use a similar approach proposed in [16] where the gradient value is renormalized when it is greater than a threshold.

Experiments
We carried out the experiments for frame-level classification of phone states on the TIMIT dataset using an ESN with all parameters learned as discussed so far. The training data includes 1,124,589 frames. The validation set has 122,488 frames from 50 speakers. The results are reported using the core test set consisting of 192 sentences and 57,920 frames. The speech is analysed using the standard Mel Frequency Cepstral Coefficients (MFCC). Each feature vector has 39 entries, including first and second derivatives. We have used 3 states for each of 61 phones resulting in a target class vector with 183 entries. Phone state labels are extracted using a GMM-HMM system which aligns the frames with their corresponding states.
We have used a context window of 3 frames for all experiments resulting in the input vectors with 3 × 39 = 117 entries. The regularization parameter µ used in (9) is set to 10 −8 . The maximum eigenvalue of W rec is set to 3.9. We have used a step size (α in (36)) of 0.07. The task is to classify each frame in the TIMIT core test set into one of 183 phone states. The results are presented in Table 1 for different hidden layer sizes in the ESN, one for each row in the table. The results are also arranged by four different ways of learning the input and recurrent weigh matrices W and W rec , where m is the number of time steps in incorporating matrices' dependencies in the learning. The column of "ESN" refers to the traditional ESN as in [7,8,9,10] where W and W rec are not learned. The preliminary experimental results shown in Table verify that learning input and recurrent weight matrices in the ESN is superior to the ESN with the same structure but without learning the two matrices. Furthermore, the longer the time steps are incorporated in the learning, the lower error rates are. On the column of "ESN", we also observe that the traditional ESN improves its performance as the number of hidden units increases, consistent with the findings reported in [10]. Finally, we would like to remark that the results obtained so far are very preliminary, and the task is on framelevel classification of 183 phone states. Our first step of research is focused on this easiest task since it is a pure and simple machine learning problem and it requires no expertise in speech recognition. The next steps are to move 1) from 183-state classification to 39-phone classification; 2) from frame level to segment level (which requires dynamic programming over three states of each phone); and 3) from classification (with no phone insertion and deletion errors) to recognition (with phone insertion and deletion errors). Then we can meaningfully compare the results with other approaches in the literature on the TIMIT phone recognition task.

Discussion and Conclusion
The main idea of this paper is straightforward: the traditional ESN learns only one of three important sets of weight matrices, and we want to learn them all. The key property that characterizes the ESN is the use of linear output units so that the learning is simple, convex, forms a least-square ridge regression problem with a global optimum (in learning the output weights). In extending the learning of the output weights to only learning input and recurrent weights, we make use of the same property of linear output units to develop and formulate constraints among various sets of ESN weight matrices. Such constraints are then used to derive analytic forms of the error gradients w.r.t the input and recurrent weights to be learned. The standard learning method of BPTT for the general RNN (with typically nonlinear output units) does not admit analytical forms of gradient computation. BPTT requires recursively propagating the error signal backward through time, a very different style of computation and learning than what we have developed in this work for ESNs.
In this paper we focus on ESNs with one layer and with no feedback connection, i.e., W f b = 0, without loss of generality. As our future work, to build more layers of ESN, we can simply stack the output of one-layer ESN on top of another, or we can combine the output with the original data input and/or with hidden units. Also, in the current work with one-layer ESN, we take into account the dependency between U and W, h i and W, h i and h i−1 , etc. When more layers of ESN are built, a richer dependency becomes available to exploit but the same principle used in this work in deriving the analytic forms of the gradient computation would apply to the multiple-layer ESN in our future work.