Computational capabilities of recurrent NARX neural networks

TLDR

Recurrent neural networks are computationally powerful, and NARX networks—based on nonlinear autoregressive models with exogenous inputs and limited output‑only feedback—have become popular in control applications. The study seeks to determine the minimal amount of feedback or recurrence required for a network to achieve Turing‑equivalence and to identify feedback restrictions that limit computational power. By formalizing NARX networks as y(t)=Ψ(u(t−n_u)…u(t), y(t−n_y)…y(t−1)) with a multilayer perceptron mapping, the authors constructively prove that finite‑parameter NARX networks are as computationally strong as fully connected recurrent networks. The authors conclude that, theoretically, NARX models can replace conventional recurrent networks without computational loss despite their limited feedback.

Abstract

Recently, fully connected recurrent neural networks have been proven to be computationally rich-at least as powerful as Turing machines. This work focuses on another network which is popular in control applications and has been found to be very effective at learning a variety of problems. These networks are based upon Nonlinear AutoRegressive models with eXogenous Inputs (NARX models), and are therefore called NARX networks. As opposed to other recurrent networks, NARX networks have a limited feedback which comes only from the output neuron rather than from hidden states. They are formalized by y(t)=/spl Psi/(u(t-n/sub u/), ..., u(t-1), u(t), y(t-n/sub y/), ..., y(t-1)) where u(t) and y(t) represent input and output of the network at time t, n/sub u/ and n/sub y/ are the input and output order, and the function /spl Psi/ is the mapping performed by a Multilayer Perceptron. We constructively prove that the NARX networks with a finite number of parameters are computationally as strong as fully connected recurrent networks and thus Turing machines. We conclude that in theory one can use the NARX models, rather than conventional recurrent networks without any computational loss even though their feedback is limited. Furthermore, these results raise the issue of what amount of feedback or recurrence is necessary for any network to be Turing equivalent and what restrictions on feedback limit computational power.