# Expressive power of RNNs and deep RNNs

In class, my professor that a recurrent neural network is for problems where the state changes as a function of past state and new input, i.e. h_(t+1) = f(h_t, x_t), for any f. Then he said we would have, in each RNN cell, a universal function approximation (e.g. a deep neural network) to learn any f and thus solve all of these problems.

But then he said that this actually won't work for many reasons (e.g. too slow and too unstable). Instead, usually only a single matrix multiplication is used, or some variant on this like LSTM/GRU. And to add complexity, multiple RNN layers can be used one after another.

I am having a hard time seeing whether this is as powerful as using a deep NN in each cell (if we somehow got it to work). In other words, can a deep RNN learn the recurrence for any f? This seems much more non-trivial to show

I am also not seeing what, if any, different inductive biases that this approach has compared with the theoretical deep NN approach.

As you said, in problems where RNNs are used, we assume that there exist a function $$f: (\mathcal X\times \mathcal X)\to \mathcal X$$ and a function $$g: \mathcal X \to \mathcal Y$$ such that for all $$T\in\mathbb N$$, the correspondence between a sequence $$x_1,\ldots,x_T\in\mathcal X$$ and an output $$y_T\in\mathcal Y$$ is given by $$y_T = g( h_T)$$ Where the sequence $$(h_t)_{1\le t\le T}$$ is recursively defined as $$h_1 := f(x_1,x_0),\quad h_{t+1} = f(h_t,x_t)$$ for $$x_0$$ some element of $$\mathcal X$$. Here, the function $$g$$ is not too important (it doesn't depend on time, so it is efficiently learnable by a standard Feedforward Neural Network up to very mild assumptions), so we will ignore it (that is, we will pretend it is known) and focus on $$f$$.

In the vanilla RNN, given an input sequence $$x_1,\ldots,x_T$$, we approximate the output $$y_T$$ by $$\hat y_T = g(\hat h_T),\quad \hat h_1 := f_\theta (x_1,x_0),\quad \hat h_{t+1}=f_\theta(\hat h_t, x_t)$$ Where, crucially, the function $$f_\theta$$ is of the form $$f_\theta(h,x) := \sigma(Ah + Bx + v) \tag1$$ Where $$\sigma$$ is some activation function (tanh, sigmoid... or even the identity !) and $$A,B,v$$ are matrices/vectors of appropriate dimensions (these are the parameters we want to optimize over). Now, something is very clear : if the target function $$f$$ is not expressible as in expression $$(1)$$, RNNs will never be able to learn the true input/output mapping, since even the best $$f_\theta^*$$ can remain arbitrarily far from $$f$$.

Therefore, if we want any approximation guarantees on vanilla RNNs, we have to assume that $$f$$ is indeed (close to) expressible as in $$(1)$$. This is indeed the approach taken in the literature : see the recent A Brief Survey on the Approximation Theory for Sequence Modelling or chapter 8 of this older review. This may seem underwhelming, since this seems like an overly restrictive assumption in practice (outside of dynamical systems). Indeed, this is an issue and it is partially allievated by using more sophisticated units $$f_\theta$$ (like GRUs) which improve the expressivity of the neural networks, but from an approximation perspective, the improvements are marginal at best.

So now you ask : why not take $$f_\theta$$ to be a good old Deep Feedforward Neural Network ? We know that these will be able to represent almost any functions, right ? That is perfectly true : given any mildly regular function, you can find a Neural Network that approximates this function well in basically any norm you want (Sobolev norm, $$L^2$$ norm, uniform norm...).

The issue however is that we need to learn that function. That is, you are free to pick a Neural Network with one billion parameters as your class of functions $$\{f_\theta\}$$, in which case you're sure that for some parameters $$\theta$$, you will have a good approximation of $$f$$ (and thus the output $$y_T$$), but the issue is that you don't know what these parameters are, you have to find them ! For these kind of models, the state-of-the-art way to find this "best neural network" is by performing gradient descent/backpropagation on the loss with respect to the parameters.

Here is the bad news : RNNs highly suffer from the vanishing/exploding gradient problem, that is even if you pick the simplest function $$f_\theta$$ given in $$(1)$$, the norm of the gradient will roughly scale like $$\|A\|^T$$, which for vanishes/explodes exponentially fast in $$T$$, leading to unstable training, making it very hard to find the best possible RNN in the hypothesis class (this is the reason why people have considered alternatives like LSTMs, bi-directional RNNs etc... in the first place : they alleviate this phenomenon by quite a lot).

If you replace $$f_\theta$$ from the vanilla expression $$(1)$$ to a Deep Neural Network (which also suffer from the vanishing gradient problem), you will basically compound the effect, leading to a gradient norm roughly scaling like $$\|A\|^{LT}$$, where $$L$$ is the depth of the Neural Network you picked. This is untrainable in practice, and thus finding the best Neural Network $$f^*_\theta$$ would simply be impossible. (I encourage you to try on a non-trivial problem and report your results here !)

In conclusion : If we replaced the function $$f_\theta$$ from a linear combination of $$h$$ and $$x$$ to a Deep Network, we would gain a lot of expressivity, but at the cost of having unlearnable, and thus unusable models. Also note that it may seem restrictive to ask for $$f$$ to be of the form $$(1)$$, but in practice, RNNs (or some variants) have been succesfully used on numerous highly complex NLP tasks, so it seems like the assumption is actually not that unreasonable. My intuition for that would be that due to the time dependency, even for a very simple function $$f$$, the relationship between $$y_T$$ and $$x_1,\ldots,x_T$$ might be highly complex. This is essentially the main idea of dynamical systems and chaos theory (though to be honest I know nothing about these topics).

Hope that helps !