Equivalence Results between Feedforward and Recurrent Neural Networks for Sequences

Alessandro Sperduti

Abstract

This paper establishes a formal mathematical equivalence between single-layer feedforward neural networks (FFNNs) and recurrent neural networks (RNNs) for sequence processing. By utilizing linear autoencoders to manage sequence history and Singular Value Decomposition (SVD) for weight factorization, the author demonstrates a constructive method to transform an FFNN into an equivalent RNN. This work provides a framework for decoupling functional computation from memory storage in recurrent architectures, offering potential solutions to the vanishing gradient problem.

Introduction

Recurrent Neural Networks (RNNs) are the standard tool for sequence processing, but they are notoriously difficult to train due to the "vanishing gradient" problem. A major reason for this difficulty is our lack of understanding regarding how RNNs actually manage information. In a standard RNN, the hidden state must simultaneously perform a functional task (computing the output for the current step) and a memory task (storing relevant information for the future).

The author addresses this by asking: If we have a feedforward network that sees the entire sequence at once (purely functional), can we systematically turn it into an RNN that sees the sequence one step at a time? By answering "yes," the paper helps decouple the computational logic from the memory requirements.

Methodology: From FFNN to RNN

The paper introduces a constructive procedure to map a single-layer FFNN ($N_f$) to an equivalent RNN ($N_{rec}$). The process begins by viewing the FFNN as an "unrolled" network that processes a fixed-length window of the sequence history.

Unrolled feedforward network architecture representing the functional task over a sequence.

The key steps in the transformation include:

  1. Linear Autoencoders for Sequences: The author uses a specialized form of autoencoder to find a compressed representation of the sequence history. This acts as the "memory" component of the resulting RNN.
  2. Weight Factorization: The weight matrix of the FFNN is decomposed using Singular Value Decomposition (SVD). This allows the author to identify the "rank" and "timespan" of the information needed to reproduce the FFNN's behavior.
  3. The "Equivalent" RNN Construction: The RNN’s hidden layer is split into two distinct parts: one that mimics the FFNN's hidden units (functional) and one that implements the autoencoder's state (memory).
  4. Sigmoidal Approximation: While the memory component is initially linear, the author proves that these units can be replaced with sigmoidal units with an arbitrarily small error, making the architecture a standard nonlinear RNN.

Architecture and Insights

The most significant insight is that we can treat an RNN as a system where some units are dedicated to computation (high gain) and others to memory (low gain). This suggests that RNN training could be improved by addressing these two components differently.

The constructed equivalent RNN architecture, demonstrating the separation of functional units and memory feedback.

The complexity (number of hidden units) of the equivalent RNN is bounded by the rank of the FFNN's weight matrix and its "timespan" (how far back in the sequence it looks). This perspective allows us to view RNNs as "compiled" FFNNs, suggesting a novel training strategy: train a feedforward network on unrolled sequences first (which is easier), then "compile" it into an RNN for efficient online processing.

Experimental Evaluation

The paper evaluates the theory using a DNA sequence dataset consisting of 71 sequences. The task is a binary classification at each position to predict whether an amino acid is part of a specific secondary structure (a helix).

  • Exact Equivalence: The author successfully transformed a 10-hidden-unit FFNN (trained to 99% accuracy) into an RNN.
  • State Space Compression: While the theoretical "exact" reconstruction required a large state space (1,655 units), SVD truncation showed a trade-off. By keeping only the top $k$ singular values, the state space could be reduced significantly. For example, with $k \ge 1,108$, the RNN's predictions were identical to the FFNN's.
  • Graceful Degradation: The discrepancy between the RNN and FFNN decreased smoothly as the state space grew, demonstrating that the RNN can approximate the FFNN even with limited memory resources.

Conclusion and Future Work

While the results are primarily derived for single-layer networks, they highlight the high parameter cost of storing long-term dependencies in standard RNN architectures. Future work may involve developing new learning algorithms that explicitly interleave functional learning with memory learning, potentially bypassing the vanishing gradient problem by initializing RNNs with "pre-compiled" feedforward logic.

Summary updated

Abstract

In the context of sequence processing, we study the relationship between single-layer feedforward neural networks, that have simultaneous access to all items composing a sequence, and single-layer recurrent neural networks which access information one step at a time. We treat both linear and nonlinear networks, describing a constructive procedure, based on linear autoencoders for sequences, that given a feedforward neural network shows how to define a recurrent neural network that implements the same function in time. Upper bounds on the required number of hidden units for the recurrent network as a function of some features of the feedforward network are given. By separating the functional from the memory component, the proposed procedure suggests new efficient learning as well as interpretation procedures for recurrent neural networks.
BibTeX
@inproceedings{sperduti2015equivalence,
  author = {Alessandro Sperduti},
  title = {{Equivalence Results between Feedforward and Recurrent Neural Networks for Sequences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure