Mathematical justification for using recurrent neural networks over feed-forward networks

Question

I was wondering and trying to understand if there exists any mathematical reason behind the superiority of RNNs over Feed-forward networks when dealing with sequential data. For example when modeling time series, HMMs, etc. Assume that the length of the sequence is fixed, but very large.

Intuitively it's clear that RNNs are able to remember the relevant information till the current time instant $t$ in the state variable $h_{t-1}$ and use that to update their state to $h_t$ based on the current input $x_t$. For example, if we want to model $Y_t=X_t+X_{t-1}+\ldots+X_0$ using a Feed-forward network, we should have an input node for each $X_i$ and sum them to obtain $Y_t$ whereas with RNN we just need a single input node for $X_t$ and the state remembers the sum $X_{t-1}+\ldots+X_0$.

Though the above example is pretty elementary, it highlights that the complexity of RNN (# of nodes, depth) is much less compared to that of a Feed-forward one.

Can anyone provide an example of families of functions which can't be captured by Feed-forward but can be well approximated by RNNs? Any references directing to the same is also appreciated.

Answer 1

I don't think this will be a very satisfying answer, because it's somewhat of a proof by definition, but I believe it is correct nonetheless (albeit not very mathematical).

Can anyone provide an example of families of functions which can't be captured by Feed-forward but can be well approximated by RNNs?

No. At least not if we accept this definition of a function;

...a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. [Wikipedia]

If we imagine some hypothetical function $\psi(x)$ that operates on some vector of inputs $x$ and cannot yet be expressed by any feed forward neural network, we could simply use $\psi(x)$ as a transfer functions and, voila, we can now construct a simple perceptron which performs a superset of the functionality of $\psi(x)$;

$f(x) = \psi(b + wx)$

I will leave it as an exercise for the reader to figure out which values we need for the bias, $b$, and weight vector, $w$, in order to make our perceptron output $f(x)$ mimic that of our mystery function $\psi(x)$!

The only thing that an RNN can do that a feed forward network cannot is retain state. By virtue of the requirement that an input maps to only a single output, functions cannot retain state. So by the above contorted example we can see that a feed forward network can do anything (but no more) than any function (continuous or otherwise).

Note: I think I've answered your question, but I think it's worth pointing out a slight caveat; while there does not exist a function that cannot be mapped by a feed-forward network, there most certainly are functions that are better suited to RNNs than feed-forward networks. Any function that is arranged in such a way that feature-sets within the function are readily expressed as transformations of previous results may be better suited to an RNN.

An example of this might be finding the nth number of the fibonacci sequence, iff the inputs are presented sequentially;

$F(x) = F(x-1) + F(x-2)$

An RNN might approximate this sequence effectively by using only a set of linear transformation functions, whereas a stateless function, or feed-forward neural net, would need to approximate the functional solution to the Fibonacci sequence:

$F(x) = \frac{\phi^n - \psi^n}{\sqrt5}$

where $\phi$ is the golden ratio and $\psi \approx 1.618$.

As you can imagine, the first variant is far easier to approximate given the usual array of transfer functions available to the designer of a neural network.