Equivalence Results between Feedforward and Recurrent Neural Networks for Sequences

1 Introduction

Learning on sequential data has always been a hot topic since many are the application domains where this skill could be applied, e.g. natural language processing, bioinformatics, video surveillance, time series prediction, robotics, etc. There are many different approaches that can be used to perform learning on sequential data, ranging from deterministic to probabilistic ones. In this paper, we focus on Recurrent Neural Networks (RNN) (see for example [Kremer, 2001]), which constitute a powerful computational tool for sequences modelling and prediction, as recently demonstrated in [Boulanger-Lewandowski et al., 2012], where many different approaches for sequence learning have been compared on a prediction task involving polyphonic music. Training a RNN, however, is hard, the main problem being the well known vanishing gradient problem which makes difficult to learn long-term dependencies [Bengio et al., 1994]. Partial solutions to this problem have been suggested in literature, such as the introduction of LSTM networks [Hochreiter and Schmidhuber, 1996], more efficient training procedures, such as Hessian Free Optimization [Martens and Sutskever, 2011], and smart weight initialisation procedures, as stressed, for example, in [Sutskever et al., 2013], and demonstrated for RNN in [Pasa and Sperduti, 2014]. Notwithstanding these progresses, efficient and effective training of RNNs is still an open problem.

∗This work was supported by the University of Padova under the strategic project BIOINFOGEN.

Our position about this state of the art is that current learning algorithms for general RNN architectures are not based on a good understanding of how information is processed by a RNN. Specifically, we believe that efficient and effective learning algorithms should address in different ways the functional and the memory components of a RNN. Thus a better understanding of how these two components interact each other inside a RNN is needed. In this paper, we report on some results that we believe, in part, elucidate the interplay between these two components. The approach we have pursued can be explained as follows. We consider a set of bounded sequences for which a prediction task at each time step should be carried on. We pretend to have enough computational resources to be able to fully unroll these sequences and to exploit a feedforward neural network with as many input units as the number of components belonging to the longest sequence. We consider the set of functions that such network can compute on the given set of sequences and show how it is possibile to design a RNN able to reproduce the same set of functions. The feedforward network does not need to have a memory component since the (sub)sequences presented in input are fully unrolled. Thus, the feedforward network can be understood as a system with a pure functional component. However, when we construct the "equivalent" RNN, we need to introduce a memory component, since the RNN can only read one item of the sequence at a time. The memory component we introduce is based on linear autoencoders for sequences, i.e., a special case of the autoencoders for structured data introduced in [Sperduti, 2006; Micheli and Sperduti, 2007; Sperduti, 2007]. Specifically, an autoencoder is used to keep memory of the temporary results computed by the functional component of the feedforward network. Additional considerations of properties of sigmoidal functions will also allow the substitution of linear units with sigmoidal units, incurring into an arbitrarily small error in reproducing the functions computed by the original feedforward network. Overall, we get a practical procedure that, given a feedforward neural network processing unrolled sequences, is able to return an "equivalent" RNN processing the sequences one item at a time. Since we use autoencoders, the procedure also returns RNNs with a number of hidden units which is not extremely large. In fact, we try to give upper bounds on the number of hidden units of the resulting RNN.

We believe that the main contribution of the paper is to start a research path towards a better understanding of the weight space of RNNs, so to allow, in a hopefully near future, the design of more efficient and effective learning algorithms for RNNs.

2 Background

In the following, we introduce background knowledge on linear autoencoders for sequences, and feedforward and recurrent neural networks with a single layer.

2.1 Linear Autoencoders for sequences

In [Sperduti, 2006; Micheli and Sperduti, 2007; Sperduti, 2007], a closed form solution for linear autoencoders for structured data has been proposed. Specifically, given a set of temporal sequences of input vectors {sq ≡ (xq1 , xq2 , . . . , xqlq )|q = 1, . . . , n, xqj ∈ Ra }, a linear autoencoder can be defined by considering the coupled linear dynamical systems

and looking for the smallest possibile matrices A, B, and C able to satisfy eq. (1) and eq. (2).

The solution proposed in [Sperduti, 2006] hinges on the factorisation of the matrix Y collecting as rows the state vectors of the linear system described by eq. (1). In fact, assuming as initial state y0 = 0 (the null vector), and a single sequence for the sake of presentation, Y can be factorized as

where, given s = al, Ξ ∈ Rl×s is the data matrix collecting all the (inverted) input subsequences (including the whole sequence) as rows, and Ω is the parameter matrix of the dynamical system. By considering the thin svd decomposition of Ξ =VΛUT , the state space can be confined into a subspace of dimension ρ = rank(Ξ) if matrices A and B are chosen so to have UTΩ = I, i.e. the identity matrix. By exploiting the fact that UUT = I, this condition turns into Ω = U. Using matrices

where Pa,s is an operator that annihilates all except the first a components of vectors multiplied to its left and Ra,s is an operator that shifts down of a positions the components of vectors multiplied to its right replacing the first a components with zeros, it is not difficult to verify that A ≡ UTPa,s ∈ Rρ×a and B ≡ UTRa,sU ∈ Rρ×ρ satisfy equation Ω = U. It is also not difficult to recognise that, since Y = VΛ, it is possibile to fully reconstruct the original data Ξ by computing YUT = VΛUT = Ξ, which can be achieved by running the dynamical system

starting from yl, i.e. [ AT BT ] is the matrix C defined in eq. (2).

Finally, when considering a set of sequences, the same result can be obtained by stacking the data matrix of each sequence and filling up with zeros where needed. E.g., given a sequence s1 of length 3 and a sequence s2 of length 2, the full

2.2 Feedforward and Recurrent Neural Networks

In this paper, we mainly work with feedforward and recurrent neural networks with a single hidden layer. Specifically, with no loss in generalisation, we consider feedforward neural networks Nf with a single output described by the following equation

where x is the input vector with a component set to 1 to account for the bias term, σ(·) is the hyperbolic tangent function, H is the number of hidden units of the network, wh are the weight vectors of the hidden units, and woh are the components of the output weight vector, where wo 0 is associated to the constant 1 (i.e., here we assume that h0(x) = 1) to account for the bias term.

Here we also consider a linear version of the feedforward network (which, because of linearity, reduces to a single linear unit), i.e. NL whose output is described by

The output of the recurrent neural network Nrec considered here is a nonlinear version of eq. (1) and eq. (2), i.e.

where we assume y0 = 0, σ(·) is the function which applies component-wise the hyperbolic tangent to the input vector, A ∈ RH×(a+1) is the input-to-hidden weight matrix (we assume a constant input to 1 to account for the bias), B ∈ RH×H is the hidden-to-hidden weight matrix, c ∈ RH+1 is the hidden-to-output weight vector (again, we assume a constant input to 1 to account for the bias).

As a final remark, we observe that the hyperbolic tangent function σ(z) is almost linear around 0. In fact, if we consider the function βσ( zβ ), given z ∈ [-b, b] and an error value ϵ, there exists a value β⋆ such that |β⋆σ( z β⋆ )-z| < ϵ. This fact can be understood recalling that the first terms of the Taylor expansion of the hyperbolic tangent function are z - z3 3 + 2z5 15 - · · · , which for βσ( zβ ) becomes z - z3 3β2 + 2z5 15β4 - · · · .

We will use this fact for some of our results on nonlinear networks.

3 Theoretical Results

We start by considering the task to learn a function F(·) from multivariate input sequences of bounded length to desired output values, in the following sense: given a training set T = {(sq , dq )|q = 1, . . . , n, sq ≡ (xq1 , xq2 , . . . , xqlq ), dq ≡ (dq1 , dq2 , . . . , dqlq ), xqt ∈ Ra , dqt ∈ R}, we expect to learn a function F(·) such that ∀q, t F(sq [1, t]) = dqt , where sq [1, t] ≡ (xq1 , xq2 , . . . , xqt ). Actually, here we are not interested into generalisation issues, but into computational issues, i.e., we would like to seek an answer to the following question: what is the relationship between an implementation of F(·) by a feedforward neural network able to directly access the sequence items read up to time t and an implementation of F(·) by a recurrent neural network that can directly access only the current item at time t (after having read all the previous items of the sequence). An answer to this question would allow to gain a better understanding of how a recurrent neural network is able to manage the memory component which is needed to store the (relevant features of the) sequence items which are read one at a time, jointly with the functional component needed to reproduce the desired output value. This improved understanding could be a good starting point to device more efficient and effective learning algorithms for recurrent neural networks.

We start our investigation by first considering linear functions. After that, we discuss how the findings obtained with linear functions can be extended to nonlinear functions.

3.1 Linear Functions

Here we consider linear functions Fw(·) which can be implemented by a linear network NL with weight vector w, as described by eq. (3). Starting from NL we show how to build a linear dynamical system (a special case of the one described by eq. (1) and eq. (2)) which computes the very same function. Specifically, let l =maxi∈{1,...,q} li, m= argmaxi∈{1,...,q} li. We consider NL to have an input of size al, i.e. w ∈ Ral . Given an input sequence sq ≡ (xq1 , xq2 , · · · , xqlq-1 , xqlq ), the linear network NL takes as input the vectors obtained by concatenating (in reverse order) the first i items of the sequence, padding the obtained vector with zeros, so to obtain a vector in Ral . By collecting these vectors as rows of a matrix we obtain where we have made explicit that the weight vector w can be decomposed into l subvectors wi of size a, i.e. ∀i wi ∈ Ra : w1 is used to process the last read item of the sequence, w2 to process the second-last read item, and so on. Thus, the tth read item of the jth sequence can be computed as Fw(sj [1, t]) = djt = ∑tk=1 xj T k wt-k+1. We start from this equation to show how to define a linear dynamical system able to reproduce the same output. In addition, we require the linear dynamical system to have the smallest state space as possibile.

Let consider the vectors belonging to the canonical basis of Rl , i.e. ei ∈ Rl , where eij = δi,j and δi,j is the Kronecker delta function. We can use these vectors to rewrite djt as follows

where B ∈ Ra×r , r = rank(W) ≤ a, is a matrix whose columns constitute a basis for the subspace spanned by the columns of W, and Γ ∈ Rr×l is such that W = BΓ. By defining z jt = [ξ j T t ,ξ j T t-1 , · · · ,ξ j T 1 ], we can introduce, for j ∈ {1, .., n}, matrices

such that d = Z vec(Γ), where vec(·) is the vectorization function which, given a matrix in input, returns a column vector obtained by stacking the columns of the matrix on top of one another. We can now observe that Z has the same structure of Ξ, so given the thin svd decomposition Z = VΛUT we can exploit the encoding part of the linear autoencoder given by A ≡ UTPr,rl ∈ Rρ×r and B ≡ UTRr,rlU ∈ Rρ×ρ , where ρ = rank(Z), to define the following equivalent (over T ) linear dynamical system NLrec :

where y0 = 0, i.e. the zero vector of dimension ρ. It is not difficult to verify that, by construction, ∀j, t

Thus, we have demonstrated that, given a specific T and w, it is possibile to build an equivalent (over T ) linear dynamical system with state space dimension equal to ρ = rank(Z). Notice that, since vec(Γ)TU ∈ Rρ , the total number of parameters of the dynamical system is ρ(r + ρ + 1), instead of the al parameters compounding w. Of course, it is trivial to state that ρ ≤ min{∑ni=1 li, rl}, i.e. the minimum between the number of rows and the number of columns of Z. To ease future discussion, let N = ∑ni=1 li.

In the following, we argue that, looking at properties of w and/or to structural features of the proposed construction, it may be possible to define an equivalent linear dynamical systemwith state space dimension smaller than ρ. In order to discuss this issue, we need to define two specific properties of w:

Definition 3.1 (rank and timespan of w over T ). We say that w has rank r⋆ if r⋆ = rank(W) and timespan t⋆ if wt⋆ ̸= 0 and ∀t > t⋆ , wt = 0.

We start by observing that if t⋆ < l, then

Thus we can define new vectors

to use for the construction of matrices Zt⋆ j and Zt⋆ , with the feature that the number of nonzero columns of Zt⋆ is less or equal to r⋆ t⋆ , and in general ρt⋆ = rank(Zt⋆ ) ≤ ρ, since by construction the columns of Zt⋆ are also in Z. In this case, the trivial bound to ρt⋆ is min{N, r⋆ t⋆}.

Another important observation is that it is not difficult to define a dynamical system that can selectively forget some of the information stored into the state space. In fact, we can exploit the same idea underpinning a linear autoencoder and make a small modification. We can notice that matrix Ra,s corresponds to a linear function that pushes down the components of the input vector of a positions, i.e. given in input a vector x ∈ Rs , it returns a vector x↓ ∈ Rs with x↓i = 0 for i = 1, . . . , a, and x↓i = xi-a+1 for i = a + 1, . . . , s. If we now consider the matrix Ra,s/p = Ra,s - 1p+a,p s , where 1i,j s is a s × s matrix of all zeros except for entry i, j, which is equal to 1, then Ra,s/p, in addition to shifting down of a positions the components of x, also annihilates the (p + a)th component of the resulting vector. Thus, if we consider the following linear dynamical system

and feed it with all the sequences in T , the matrix Ξ/p obtained by collecting all the state vectors y1 1 , y1 2 , . . . , yn ln as rows, will be equal to Ξ, except for columns p + a, p + 2a, p + 3a, . . . which will have zero entries. If we now consider the thin svd decomposition of Ξ/p = V/pΛ/pUT/p , we can project the state space vectors into the subspace spanned by the columns of Ξ/p, obtaining ˜yt = U/pTyt. Exploiting the fact that U/p˜yt = yt, we can write

i.e., we get a very similar solution as in the case of the linear autoencoder where instead of using the thin svd decomposition of Ξ and Ra,s, we use the thin svd decomposition of Ξ/p and Ra,s/p. Notice that ρ/p = rank(Ξ/p) ≤ ρ. Exploiting this observation, we can state the following theorem

Theorem 3.1. Given a vector w with rank r⋆ and timespan t⋆ over T , then there exists a linear dynamical system with space dimension ρ/π ≤ min{N, 1 2 [(1 + 2t⋆ )r⋆ - r⋆2 ]} implementing Fw(·) over T .

Proof. From the above discussion it is clear that there exists a linear dynamical system with space dimension less or equal to r⋆ t⋆ able to implement Fw(·). However, it is possibile to further reduce such dimension by an appropriate choice of the basis B. In fact, if we create B incrementally by setting B1 = wt⋆ and then trying to add new columns to B by proceeding backward to vectors wt⋆-1, wt⋆-2, . . ., the memory of the dynamical system can discard one by one the contribution of the columns of B while approaching t⋆ . The worst case is given by the scenario where B is constituted by the linearly independent vectors wt⋆-r⋆+1, . . . , wt⋆ , since in that case the dynamical system must keep in memory the full contributions of B for the first t⋆ - r⋆ time steps; after that, the contributions of columns of B can be discarded one by one at each time step, starting form the last column backward to the first column. This can be obtained by using Ra,s/π, where π is the sequence of indexes that need to be annihilated. Thus, in the worst case the dimension of the state vector is given by (t⋆ -r⋆ )r⋆ coordinates for storing information for the first t⋆ - r⋆ time steps, plus 1 2 (r⋆ + 1)r⋆ coordinates for storing information for the last time steps before reaching t⋆ .

It should be remarked that, by definition, r⋆ ≤ a. Moreover, the rank of the matrix collecting all the state vectors of the resulting dynamical system can in practice be far less than the bound given above.

3.2 Nonlinear Functions

In this section, we discuss how to exploit the results obtained for linear functions in the case in which F(·) can be implemented by feedforward neural networks. Specifically, we show how to build a recurrent neural network able to implement F(·) over T with a number of hidden units which is bounded by a function of two quantities that are generalisations of the rank and timespan already discussed for the case of linear functions.

We start by considering a specific class of feedforward neural networks, and then we move to the general class of feedforward neural networks.

Definition 3.2. A single hidden layer feedforward neural network Nf is said to have the 1-time-step property if any hidden unit only connects to input units belonging to the same time step.

An example of feedforward network with this property is shown in Figure 1. If a network has the 1-time-step property, then it is possibile to write the output oNf of Nf to the (unrolled) input (sub)sequence s ≡ (x1, x2, · · · , xl) as

where Ht is the number of hidden units associated with the input at time step t. Notice that Ht can be 0 for some values of t. Moreover, woht are the weights from the hidden units to the output unit, thus they are the components of a vector that we denote as wo . Let H = ∑lt=1 Ht, i.e. the number of hidden units of Nf , and

be the row vector that collects the output of all hidden units to the same input xi. This vector can be understood as the set of contributions that xi can give at time steps from 1 to l. The idea is to replace the original sequence s ≡ (x1, x2, · · · , xl) with sequence (h(x1), h(x2), · · · , h(xl)) and then apply a construction similar to the one described for linear functions. Specifically, we can define H as

Notice that H contains all the information needed to compute the desired function over T . In fact, by defining the weight row vector ˜w ∈ RHl as

we can write, ∀j, t

where hj,t = row(ι(j, t),H), i.e. the row of matrix H of index ι(j, t) = ∑j-1 k=1 Hk + t.

A recurrent neural network Nrec with vector states given by rows of H can be obtained as follows. Let H/[1,H] be H without the first H columns and H[1,H] be the first H columns of H. Nrec will have a input units, i.e. what is needed to read input vector xt ∈ Ra at time t. Moreover, Nrec will have a hidden layer composed of H hidden units with hyperbolic tangent function, which are the same as the hidden units of Nf , all connected to the input units. In addition to these hidden units, the hidden layer of Nrec will have ρH/[1,H] = rank(H/[1,H]) linear hidden units implementing the encoding part of an autoencoder defined on the sequences generated by the first H hidden units. Notice that items of these sequences are rows of H[1,H] and that H/[1,H] corresponds to the Ξ matrix of the state space matrix factorisation. In summary, while the first H sigmoidal hidden units take as input only the input vector xt at time t, the linear hidden units at time t take as input the output of the full hidden layer at time t -1.

Mathematically, the obtained network, with H + ρH/[1,H] hidden units, can be described as

where matrices U, A, and B are obtained by H/[1,H]. Moreover, we assume y0 = 0 and ˜y0 = 0. A pictorial representation of the network is shown in Figure 2.

Notice that linear hidden units can be substituted by sigmoidal units by incurring into a predefined error ϵ. In fact, we can observe that, by construction, the linear hidden units get a bounded input, since they process the output of sigmoidal units, which is bounded between -1 and 1. Moreover, we are considering bounded sequences. Thus, by using sigmoidal units βσ( zβ ) in place of linear units, we can always find suitable values of βs so to keep an approximation error for the output within the desired tolerance ϵ.

As in the linear case, we can further reduce the size of the hidden space. In fact, we can define the timespan of Nf over T as follows

Definition 3.3 ( timespan of Nf over T ). We say that Nf has timespan t⋆ if Ht⋆ ̸= 0 and ∀t > t⋆ , Ht = 0.

We can observe that the dynamical system derived from H/[1,H] can forget the first tH state components after t time steps. This leads to a bound on the number of hidden units which is min{N, 1 2 Ht⋆ (Ht⋆ + 1)}, where Ht⋆ = ∑t⋆ i=1 Hi .

Let now consider a feedforward neural network with no restriction, i.e. a feedforward neural network where hidden units take input from all time slots. In this case, for each hidden node, we can apply what we have seen for linear functions when considering its net input. Thus, each hidden unit h generates a corresponding matrix of states Y(h). All these matrices can be concatenated to form a single large matrix ˜Y ≡ [Y(1), . . . ,Y(H)] that can again be decomposed by thin svd ˜Y = ˜V˜Λ˜UT . ˜U can now be used to compress this component of the state vector and ˜U to expand it back when it is needed to use it for the net input of the hidden units. Since all operations are linear, the size of the resulting component of the state vector will be ˜ ρ = rank( ˜Y). Upper bounds on ˜ ρ can trivially be derived by using the upper bound we already derived for a single linear unit when considering its rank and timespan. Thus, overall, the resulting Nrec will have H + ˜ ρ hidden units. Again, linear units can be substituted by sigmoidal units incurring into a predefined error.

4 Empirical assesment

In this section, we empirically evaluate on a real dataset the size of the state space of a recurrent neural network derived by a feed-forward network with hidden units. This constitutes the worst case scenario among the ones described in the previous sections. As dataset we have selected 71 DNA sequences 1 of up to 159 amino-acids. Each of the 20 occurring amino-acid is encoded by a vector of size 12 with ±1 components. For these sequences we have defined a binary classification task at each position (amino-acid). The task consists in predicting whether the considered amino-acid is part of a specific secondary structure, i.e. a helix, or not. In the first case, the target for that amino-acid is set to +1 (2, 282 cases), otherwise to -1 (4, 925 cases). The length distribution of the sequences is reported in Figure 3. Overall, 7207 predictions have to be performed.

1 The dataset can be retrieved at the following URL: http://www.math.unipd.it/˜sperduti/DNAdataset.zip.

A feed-forward network with 10 hidden units and 12×159 inputs, able to access all the amino-acids read till a given position, has been trained on the classification task, obtaining an accuracy of almost 0.99 (73 errors over 7, 207 predictions). The resulting timespan of the hidden weight vectors is maximum (159), as can be verified in Figure 4 for one hidden unit. This feed-forward network has then been transformed into a recurrent neural network, as explained in Subsection 3.2. Exact reconstruction of the output of the feed-forward network is obtained with a state space of size 1, 655. However, by only considering the first k singular values of the SVD decomposition (thin SVD), it is also possibile to construct recurrent neural networks with different degrees of approximation. The very same prediction of the feed-forward network is preserved for k ≥ 1, 108. For smaller values of k the predictions of the obtained recurrent neural network disagree with the predictions of the feed-forward network at different levels. In Figure 5 we have reported the normalised discrepancy ndD(Nf ,Nreck ) between the recurrent network Nreck with state space of size k and the feed-forward network Nf , over the dataset D, as a function of k. Normalised discrepancy is computed as

where with x we refer to the input for a single prediction, i.e. in our case the amino-acid (and amino-acid already read for the considered sequence) for which a prediction should be performed. The factor 2 takes into account that predictions are ±1 values, i.e. in case of disagreement |Nf (x) - Nreck (x)| = 2.

For this dataset and task, it is clear that the need to implement a memory (which is external in the case of the feedforward network) within the recurrent neural network costs very many additional parameters (weights).

5 Conclusions

The results we have described in this paper should be considered into the right perspective. They do not constitute a complete basis for the design of new efficient and effective learning algorithms for RNN. However, they suggest many research directions, both concerning learning and interpretation of a RNN. When considering learning, one trivial suggestion is to design a learning algorithm that learns feedforward components in separation and then merges them as shown in the paper, or an approach that starts by learning shorter sequences using feedforward networks which are then turned into RNNs to be further combined with additional feedforward networks. Another line of research could be to make an explicit separation, inside a RNN, of the functional component from the memory component, and to interleave learning on the functional component with learning on the memory component. When considering interpretation of a RNN, a trivial observation seems to be that hidden units with high gain are probably mainly involved into the functional component of the RNN, while hidden units with low gain are probably mainly involved into the memory component of the RNN. More sophisticated interpretation approaches could try to devise a decoding function for the hidden units in analogy to what happens with linear autoencoders.