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. Recently, Janzamin et al. [7] derived a new framework for training input-output models in the supervised framework. It is based on spectral decomposition of moment tensors, obtained after certain non-linear transformations of the input. These non-linear transformations take the form of score functions, which depend on generative models of the input. This provides a new approach for transferring generative information, obtained through unsupervised learning, into discriminative training on labeled samples. Based on the aforementioned approach, Janzamin et al. [8] provided guaranteed risk bounds for training two-layer feedforward neural network models with polynomial sample and computational bounds. The conditions for obtaining the risk bounds are mild: a small approximation error for the target function under the given class of neural networks, a generative input model with a continuous distribution, and general sigmoidal activations at the neurons. In this paper, we consider new spectral approaches for training IO-RNNs in both classification and regression settings. The previous score function approach for training feedforward networks (as described above) does not immediately extend, and there are some non-trivial challenges: (i) Non-linearity in a RNN is propagated along multiple steps in the sequence, while in the two-layer feedforward network, non-linearity is applied only once to the input. It is not immediately clear on how to "untangle" all these non-linearities and obtain guaranteed estimates of the network weights. (ii) Learning bidirectional RNNs is even more challenging since recursive non-linearities are applied in both the directions, and (iii) Assumption of i.i.d. input and output training samples is no longer applicable, and analyzing concentration bounds for samples generated from a RNN with non-linear state evolution is challenging. We address all these challenges concretely in this paper. Our main contributions are: (i) novel approaches for training input-output RNN and bidirectional RNN models using tensor decomposition methods, (ii) guaranteed recovery of network parameters with polynomial computational and sample complexity, and (iii) transparent conditions for successful recovery based on non-degeneracy of model parameters and bounded evolution of hidden states. Score function transformations: Training input-output neural networks under arbitrary input is computationally hard. On the other hand, we show that training becomes tractable through spectral methods when the input is generated from a probabilistic model on a continuous state space. This paper can be considered as study of what it takes to uncover the nonlinear dynamics in the system. Since learning under arbitrary input is extremely challenging, we seek to discover under what functions/information of the input the problem becomes tractable. Although this differs from usual approach in training IO-RNNs, this is a promising first step towards demystifying these widelyused models. We show that with some knowledge of the input distribution, we can solve the extremely hard problem of training nonlinear IO-RNNs. We assume knowledge of score function forms, which correspond to normalized
Work by REF gives a moment-based approach for learning some classes of non-linear recurrent neural networks.
Training Input-Output Recurrent Neural Networks through Spectral Methods
ArXiv
ArXiv
Computer Science Mathematics