Training Input-Output Recurrent Neural Networks through Spectral Methods

Hanie Sedghi, Anima AnandkumararXiv 2016 · OpenReview

TL;DR

This paper introduces a novel spectral method for training Input-Output Recurrent Neural Networks (IO-RNNs) and Bidirectional RNNs (BRNNs), which are crucial for sequence labeling tasks. By leveraging tensor decomposition techniques and score functions derived from the input's probability distribution, the authors provide a provable guarantee for learning network parameters with polynomial sample and computational complexity.

What Problem Does This Paper Address?

Training Recurrent Neural Networks (RNNs), especially for sequence labeling tasks, is notoriously challenging. Traditional methods like backpropagation suffer from vanishing and exploding gradients, making it difficult to learn long-term dependencies. While architectures like LSTMs offer improvements, theoretical understanding and guaranteed training methods for standard RNNs remain limited. This paper tackles this gap by proposing a spectral approach that offers theoretical guarantees for learning IO-RNNs and BRNNs, which are widely used in applications like Part-of-Speech (POS) tagging and Named-Entity Recognition (NER).

Methods

The core of this work lies in a novel spectral approach that utilizes tensor decomposition. The authors extend the "score function" concept, which relates to the derivatives of the input's probability density function, to sequences. They form cross-moment tensors between the output and these score functions. By decomposing these tensors, they can recover the network's weight matrices.

Key techniques include:

  • Score Function Tensors: Extending the definition of score functions to sequences and deriving their forms for RNNs and Markovian input sequences.
  • Tensor Decomposition: Employing CP (Candecomp/Parafac) tensor decomposition to extract latent parameters from the cross-moment tensors.
  • GLOREE Algorithm: A proposed algorithm (GLOREE for Guaranteed Learning Of Recurrent nEural networks) that orchestrates these steps to recover IO-RNN parameters.
  • GLOREE-B Algorithm: An extension of GLOREE to train Bidirectional RNNs.
  • Spectral Norm and Lipschitz Properties: Analyzing these properties to establish concentration bounds for the empirical moments, which are crucial for proving sample complexity guarantees.

The novelty lies in applying spectral methods to the non-linear, sequential nature of RNNs, overcoming challenges like the propagation of non-linearities across time steps and the lack of i.i.d. samples.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees and assumes access to labeled samples from an IO-RNN or BRNN model.

Key Insights and Ideas

  • Score Functions as a Bridge: Score functions, derived from the input's probability distribution, act as a crucial bridge to connect unsupervised input modeling with supervised network training. This allows for the transfer of generative information into discriminative learning.
  • Tensor Decomposition for Sequential Data: The paper demonstrates that tensor decomposition, a powerful tool for latent variable models, can be effectively adapted to uncover the parameters of sequential models like RNNs, even with their inherent non-linearities and temporal dependencies.
  • Provable Guarantees: A significant contribution is the theoretical guarantee of consistent parameter recovery under specific, yet transparent, conditions (e.g., polynomial activations, Markovian input, full-rank weight matrices). This moves beyond empirical performance to offer theoretical backing.
  • Handling Non-linearities: The spectral approach cleverly circumvents the direct challenge of non-linear activations by leveraging their derivatives (score functions) to form tensors that can be decomposed.

Key Results

The paper presents theoretical results, not empirical ones. The main findings are:

  • Guaranteed Parameter Recovery: The proposed spectral methods (GLOREE and GLOREE-B) are shown to recover the parameters of IO-RNNs and BRNNs with polynomial activation functions.
  • Polynomial Sample and Computational Complexity: The learning process is guaranteed to have polynomial sample and computational complexity under stated assumptions.
  • Extension to BRNNs: The spectral approach is successfully extended to Bidirectional RNNs, which incorporate information from both past and future time steps.
  • Analysis of Assumptions: The paper provides insights into the role of assumptions like Markovian input and bounded hidden states for achieving these guarantees.

Limitations and Future Work

  • Realizable Setting: The current guarantees are for the "realizable setting," meaning the data is assumed to be generated by an RNN with the exact structure and parameters the algorithm aims to recover. The problem of approximation bounds for RNNs with a fixed number of neurons is noted as an interesting future direction.
  • Polynomial Activations: The current theoretical framework primarily focuses on polynomial activation functions. While the paper mentions extensions, the analysis for general sigmoidal activations might be more complex.
  • Non-stationary Inputs: The current analysis assumes stationary inputs. Relaxing this assumption to handle non-stationary inputs is suggested as future work.
  • Aligned Inputs/Outputs: The paper mentions that the framework can be relaxed to obtain more general RNNs, implying current work might assume aligned inputs and outputs.
  • Approximation Bounds: The paper acknowledges that approximation bounds for RNNs with a fixed number of neurons are not satisfactorily resolved and is an area for future research.

Summary updated

Abstract

We consider the problem of training input-output recurrent neural networks (RNN) for sequence labeling tasks. We propose a novel spectral approach for learning the network parameters. It is based on decomposition of the cross-moment tensor between the output and a non-linear transformation of the input, based on score functions. We guarantee consistent learning with polynomial sample and computational complexity under transparent conditions such as non-degeneracy of model parameters, polynomial activations for the neurons, and a Markovian evolution of the input sequence. We also extend our results to Bidirectional RNN which uses both previous and future information to output the label at each time point, and is employed in many NLP tasks such as POS tagging.
BibTeX
@misc{sedghi2016training,
  author = {Hanie Sedghi and Anima Anandkumar},
  title = {{Training Input-Output Recurrent Neural Networks through Spectral Methods}},
  year = {2016},
  eprint = {1603.00954},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1603.00954},
}
Figure