Sequence Transduction with Recurrent Neural Networks

Introduction

The ability to transform and manipulate sequences is a crucial part of human intelligence: everything we know about the world reaches us in the form of sensory sequences, and everything we do to interact with the world requires sequences of actions and thoughts. The creation of automatic sequence transducers therefore seems an important step towards artificial intelligence. A major problem faced by such systems is how to represent sequential information in a way that is invariant, or at least robust, to sequential distortions. Moreover this robustness should apply to both the input and output sequences.

For example, transforming audio signals into sequences of words requires the ability to identify speech sounds (such as phonemes or syllables) despite the apparent distortions created by different voices, variable speaking rates, background noise etc. If a language model is used to inject prior knowledge about the output sequences, it must also be robust to missing words, mispronunciations, non-lexical utterances etc.

Recurrent neural networks (RNNs) are a promising architecture for general-purpose sequence transduction. The combination of a high-dimensional multivariate internal state and nonlinear state-to-state dynamics offers more expressive power than conventional sequential algorithms such as hidden Markov models. In particular RNNs are better at storing and accessing information over long periods of time. While the early years of RNNs were dogged by difficulties in learning (Hochreiter et al., 2001), recent results have shown that they are now capable of delivering state-of-the-art results in real-world tasks such as handwriting recognition (Graves et al., 2008; Graves & Schmidhuber, 2008), text generation (Sutskever et al., 2011) and language modelling (Mikolov et al., 2010). Furthermore, these results demonstrate the use of long-range memory to perform such actions as closing parentheses after many intervening characters (Sutskever et al., 2011), or using delayed strokes to identify handwritten characters from pen trajectories (Graves et al., 2008).

However RNNs are usually restricted to problems where the alignment between the input and output sequence is known in advance. For example, RNNs may be used to classify every frame in a speech signal, or every amino acid in a protein chain. If the network outputs are probabilistic this leads to a distribution over output sequences of the same length as the input sequence. But for a general-purpose sequence transducer, where the output length is unknown in advance, we would prefer a distribution over sequences of all lengths. Furthermore, since we do not how the inputs and outputs should be aligned, this distribution would ideally cover all possible alignments.

Connectionist Temporal Classification (CTC) is an RNN output layer that defines a distribution over all alignments with all output sequences not longer than the input sequence (Graves et al., 2006). However, as well as precluding tasks, such as text-to-speech, where the output sequence is longer than the input sequence, CTC does not model the interdependencies between the outputs. The transducer described in this paper extends CTC by defining a distribution over output sequences of all lengths, and by jointly modelling both input-output and output-output dependencies.

As a discriminative sequential model the transducer has similarities with ‘chain-graph’ conditional random fields (CRFs) (Lafferty et al., 2001). However the transducer’s construction from RNNs, with their ability to extract features from raw data and their potentially unbounded range of dependency, is in marked contrast with the pairwise output potentials and hand-crafted input features typically used for CRFs. Closer in spirit is the Graph Transformer Network (Bottou et al., 1997) paradigm, in which differentiable modules (often neural networks) can be globally trained to perform consecutive graph transformations such as detection, segmentation and recognition.

Section 2 defines the RNN transducer, showing how it can be trained and applied to test data, Section 3 presents experimental results on the TIMIT speech corpus and concluding remarks and directions for future work are given in Section 4.

Recurrent Neural Network Transducer

Let $\bm{x}=(x_{1},x_{2},\ldots,x_{T})$ be a length $T$ input sequence of arbitrary length belonging to the set $\mathcal{{X}}^{*}$ of all sequences over some input space $\mathcal{{X}}$. Let $\bm{y}=(y_{1},y_{2},\ldots,y_{U})$ be a length $U$ output sequence belonging to the set $\mathcal{{Y}}^{*}$ of all sequences over some output space $\mathcal{{Y}}$. Both the inputs vectors $x_{t}$ and the output vectors $y_{u}$ are represented by fixed-length real-valued vectors; for example if the task is phonetic speech recognition, each $x_{t}$ would typically be a vector of MFC coefficients and each $y_{t}$ would be a one-hot vector encoding a particular phoneme. In this paper we will assume that the output space is discrete; however the method can be readily extended to continuous output spaces, provided a tractable, differentiable model can be found for $\mathcal{{Y}}$.

Define the extended output space $\bar{\mathcal{{Y}}}$ as $\mathcal{{Y}}\cup\varnothing$, where $\varnothing$ denotes the null output. The intuitive meaning of $\varnothing$ is ‘output nothing’; the sequence $(y_{1},\varnothing,\varnothing,y_{2},\varnothing,y_{3})\in\bar{\mathcal{{Y}}}^{*}$ is therefore equivalent to $(y_{1},y_{2},y_{3})\in\mathcal{{Y}}^{*}$. We refer to the elements $\bm{a}\in\bar{\mathcal{{Y}}}^{*}$ as alignments, since the location of the null symbols determines an alignment between the input and output sequences. Given $\bm{x}$, the RNN transducer defines a conditional distribution $\Pr(\bm{a}\in\bar{\mathcal{{Y}}}^{*}|\bm{x})$. This distribution is then collapsed onto the following distribution over $\mathcal{{Y}}^{*}$

where $\mathcal{B}:\bar{\mathcal{{Y}}}^{*}\mapsto\mathcal{{Y}}^{*}$ is a function that removes the null symbols from the alignments in $\bar{\mathcal{{Y}}}^{*}$.

Two recurrent neural networks are used to determine $\Pr(\bm{a}\in\bar{\mathcal{{Y}}}^{*}|\bm{x})$. One network, referred to as the transcription network $\mathcal{F}$, scans the input sequence $\bm{x}$ and outputs the sequence $\bm{f}=(f_{1},\ldots,f_{T})$ of transcription vectorsFor simplicity we assume the transcription sequence to be the same length as the input sequence; however this may not be true, for example if the transcription network uses a pooling architecture (LeCun et al., 1998) to reduce the sequence length.. The other network, referred to as the prediction network $\mathcal{G}$, scans the output sequence $\bm{y}$ and outputs the prediction vector sequence $\bm{g}=(g_{0},g_{1}\ldots,g_{U})$.

The prediction network $\mathcal{G}$ is a recurrent neural network consisting of an input layer, an output layer and a single hidden layer. The length $U+1$ input sequence $\hat{\bm{y}}=(\varnothing,y_{1},\ldots,y_{U})$ to $\mathcal{G}$ output sequence $\bm{y}$ with $\varnothing$ prepended. The inputs are encoded as one-hot vectors; that is, if $\mathcal{{Y}}$ consists of $K$ labels and $y_{u}=k$, then $\hat{\bm{y}}_{u}$ is a length $K$ vector whose elements are all zero except the $k^{th}$, which is one. $\varnothing$ is encoded as a length $K$ vector of zeros. The input layer is therefore size $K$. The output layer is size $K+1$ (one unit for each element of $\bar{\mathcal{{Y}}}$) and hence the prediction vectors $g_{u}$ are also size $K+1$.

Given $\hat{\bm{y}}$, $\mathcal{G}$ computes the hidden vector sequence $(h_{0},\ldots,h_{U})$ and the prediction sequence $(g_{0},\ldots,g_{U})$ by iterating the following equations from $u=0$ to $U$:

where $W_{ih}$ is the input-hidden weight matrix, $W_{hh}$ is the hidden-hidden weight matrix, $W_{ho}$ is the hidden-output weight matrix, $b_{h}$ and $b_{o}$ are bias terms, and $\mathcal{H}$ is the hidden layer function. In traditional RNNs $\mathcal{H}$ is an elementwise application of the $tanh$ or logistic sigmoid $\sigma(x)=1/(1+\exp(-x))$ functions. However we have found that the Long Short-Term Memory (LSTM) architecture (Hochreiter & Schmidhuber, 1997; Gers, 2001) is better at finding and exploiting long range contextual information. For the version of LSTM used in this paper $\mathcal{H}$ is implemented by the following composite function:

The prediction network attempts to model each element of $\bm{y}$ given the previous ones; it is therefore similar to a standard next-step-prediction RNN, only with the added option of making ‘null’ predictions.

2 Transcription Network

The transcription network $\mathcal{F}$ is a bidirectional RNN (Schuster & Paliwal, 1997) that scans the input sequence $\bm{x}$ forwards and backwards with two separate hidden layers, both of which feed forward to a single output layer. Bidirectional RNNs are preferred because each output vector depends on the whole input sequence (rather than on the previous inputs only, as is the case with normal RNNs); however we have not tested to what extent this impacts performance.

Given a length $T$ input sequence $(x_{1}\ldots x_{T})$, a bidirectional RNN computes the forward hidden sequence $(\overrightarrow{h}_{1},\ldots,\overrightarrow{h}_{T})$, the backward hidden sequence $(\overleftarrow{h}_{1},\ldots,\overleftarrow{h}_{T})$, and the transcription sequence $(f_{1},\ldots,f_{T})$ by first iterating the backward layer from $t=T$ to $1$:

then iterating the forward and output layers from $t=1$ to $T$:

For a bidirectional LSTM network (Graves & Schmidhuber, 2005), $\mathcal{H}$ is implemented by Eqs. 4, 5, 6, 7 and 8. For a task with $K$ output labels, the output layer of the transcription network is size $K+1$, just like the prediction network, and hence the transcription vectors $f_{t}$ are also size $K+1$.

The transcription network is similar to a Connectionist Temporal Classification RNN, which also uses a null output to define a distribution over input-output alignments.

3 Output Distribution

Given the transcription vector $f_{t}$, where $1\leq t\leq T$, the prediction vector $g_{u}$, where $0\leq u\leq U$, and label $k\in\bar{\mathcal{{Y}}}$, define the output density function

$\Pr(k|t,u)$ is used to determine the transition probabilities in the lattice shown in Fig. 1. The set of possible paths from the bottom left to the terminal node in the top right corresponds to the complete set of alignments between $\bm{x}$ and $\bm{y}$, i.e. to the set $\bar{\mathcal{{Y}}}^{*}\cap\mathcal{B}^{-1}(\bm{y})$. Therefore all possible input-output alignments are assigned a probability, the sum of which is the total probability $\Pr(\bm{y}|\bm{x})$ of the output sequence given the input sequence. Since a similar lattice could be drawn for any finite $\bm{y}\in\mathcal{{Y}}^{*}$, $\Pr(k|t,u)$ defines a distribution over all possible output sequences, given a single input sequence.

A naive calculation of $\Pr(\bm{y}|\bm{x})$ from the lattice would be intractable; however an efficient forward-backward algorithm is described below.

4 Forward-Backward Algorithm

Define the forward variable $\alpha(t,u)$ as the probability of outputting $\bm{y}_{[1:u]}$ during $\bm{f}_{[1:t]}$. The forward variables for all $1\leq t\leq T$ and $0\leq u\leq U$ can be calculated recursively using

with initial condition $\alpha(1,0)=1$. The total output sequence probability is equal to the forward variable at the terminal node:

Define the backward variable $\beta(t,u)$ as the probability of outputting $\bm{y}_{[u+1:U]}$ during $\bm{f}_{[t:T]}$. Then

with initial condition $\beta(T,U)=\varnothing(T,U)$. From the definition of the forward and backward variables it follows that their product $\alpha(t,u)\beta(t,u)$ at any point $(t,u)$ in the output lattice is equal to the probability of emitting the complete output sequence if $y_{u}$ is emitted during transcription step $t$. Fig. 2 shows a plot of the forward variables, the backward variables and their product for a speech recognition task.

5 Training

Given an input sequence $\bm{x}$ and a target sequence $\bm{y}^{*}$, the natural way to train the model is to minimise the log-loss $\mathcal{L}=-\ln\Pr(\bm{y}^{*}|\bm{x})$ of the target sequence. We do this by calculating the gradient of $\mathcal{L}$ with respect to the network weights parameters and performing gradient descent. Analysing the diffusion of probability through the output lattice shows that $\Pr(\bm{y}^{*}|\bm{x})$ is equal to the sum of $\alpha(t,u)\beta(t,u)$ over any top-left to bottom-right diagonal through the nodes. That is, $\forall\ n:1\leq n\leq U+T$

From Sections 2.4, 18 and 19 and the definition of $\mathcal{L}$ it follows that

The gradient with respect to the network weights can then be calculated by applying Backpropagation Through Time (Williams & Zipser, 1995) to each network independently.

A separate softmax could be calculated for every $\Pr(k|t,u)$ required by the forward-backward algorithm. However this is computationally expensive due to the high cost of the exponential function. Recalling that $\exp(a+b)=\exp(a)\exp(b)$, we can instead precompute all the $\exp\left(f(t,\bm{x})\right)$ and $\exp(g(\bm{y}_{[1:u]}))$ terms and use their products to determine $\Pr(k|t,u)$. This reduces the number of exponential evaluations from $O(TU)$ to $O(T+U)$ for each length $T$ transcription sequence and length $U$ target sequence used for training.

6 Testing

When the transducer is evaluated on test data, we seek the mode of the output sequence distribution induced by the input sequence. Unfortunately, finding the mode is much harder than determining the probability of a single sequence. The complication is that the prediction function $g(\bm{y}_{[1:u]})$ (and hence the output distribution $\Pr(k|t,u)$) may depend on all previous outputs emitted by the model. The method employed in this paper is a fixed-width beam search through the tree of output sequences. The advantage of beam search is that it scales to arbitrarily long sequences, and allows computational cost to be traded off against search accuracy.

Let $\Pr(\bm{y})$ be the approximate probability of emitting some output sequence $\bm{y}$ found by the search so far. Let $\Pr(k|\bm{y},t)$ be the probability of extending $\bm{y}$ by $k\in\bar{\mathcal{{Y}}}$ during transcription step $t$. Let $pref(\bm{y})$ be the set of proper prefixes of $\bm{y}$ (including the null sequence $\bm{\varnothing}$), and for some $\hat{\bm{y}}\in pref(\bm{y})$, let $\Pr(\bm{y}|\hat{\bm{y}},t)=\prod_{u=|\hat{\bm{y}}|+1}^{|\bm{y}|}{\Pr(y_{u}|\bm{y}_{[0:u-1]},t)}$. Pseudocode for a width $W$ beam search for the output sequence with highest length-normalised probability given some length $T$ transcription sequence is given in Algorithm 1.

The algorithm can be trivially extended to an $N$ best search ($N\leq W$) by returning a sorted list of the $N$ best elements in $B$ instead of the single best element. The length normalisation in the final line appears to be important for good performance, as otherwise shorter output sequences are excessively favoured over longer ones; similar techniques are employed for hidden Markov models in speech and handwriting recognition (Bertolami et al., 2006).

Observing from Eq. 2 that the prediction network outputs are independent of previous hidden vectors given the current one, we can iteratively compute the prediction vectors for each output sequence $\bm{y}+k$ considered during the beam search by storing the hidden vectors for all $\bm{y}$, and running Eq. 2 for one step with $k$ as input. The prediction vectors can then be combined with the transcription vectors to compute the probabilities. This procedure greatly accelerates the beam search, at the cost of increased memory use. Note that for LSTM networks both the hidden vectors $h$ and the state vectors $s$ should be stored.

Experimental Results

To evaluate the potential of the RNN transducer we applied it to the task of phoneme recognition on the TIMIT speech corpus (DAR, 1990). We also compared its performance to that of a standalone next-step prediction RNN and a standalone Connectionist Temporal Classification (CTC) RNN, to gain insight into the interaction between the two sources of information.

The core training and test sets of TIMIT (which we used for our experiments) contain respectively 3696 and 192 phonetically transcribed utterances. We defined a validation set by randomly selecting 184 sequences from the training set; this put us at a slight disadvantage compared to many TIMIT evaluations, where the validation set is drawn from the non-core test set, and all 3696 sequences are used for training. The reduced set of 39 phoneme targets (Lee & Hon, 1989) was used during both training and testing.

Standard speech preprocessing was applied to transform the audio files into feature sequences. 26 channel mel-frequency filter bank and a pre-emphasis coefficient of 0.97 were used to compute 12 mel-frequency cepstral coefficients plus an energy coefficient on 25ms Hamming windows at 10ms intervals. Delta coefficients were added to create input sequences of length 26 vectors, and all coefficient were normalised to have mean zero and standard deviation one over the training set.

The standard performance measure for TIMIT is the phoneme error rate on the test set: that is, the summed edit distance between the output sequences and the target sequences, divided by the total length of the target sequences. Phoneme error rate, which is customarily presented as a percentage, is recorded for both the transcription network and the transducer. The error recorded for the prediction network is the misclassification rate of the next phoneme given the previous ones.

We also record the log-loss on the test set. To put this quantity in more accessible terms we convert it into the average number of bits per phoneme target.

2 Network Parameters

The prediction network consisted of a size 128 LSTM hidden layer, 39 input units and 40 output units. The transcription network consisted of two size 128 LSTM hidden layers, 26 inputs and 40 outputs. This gave a total of 261,328 weights in the RNN transducer. The standalone prediction and CTC networks (which were structurally identical to their counterparts in the transducer, except that the prediction network had one fewer output unit) had 91,431 and 169,768 weights respectively. All networks were trained with online steepest descent (weight updates after every sequence) using a learning rate of $10^{-4}$ and a momentum of 0.9. Gaussian weight noise (Jim et al., 1996) with a standard deviation of $0.075$ was injected during training to reduce overfitting. The prediction and transduction networks were stopped at the point of lowest log-loss on the validation set; the CTC network was stopped at the point of lowest phoneme error rate on the validation set. All network were initialised with uniformly distributed random weights in the range [-0.1,0.1]. For the CTC network, prefix search decoding (Graves et al., 2006) was used to transcribe the test set, with a probability threshold of 0.995. For the transduction network, the beam search algorithm described in Algorithm 1 was used with a beam width of 4000.

3 Results

The results are presented in Table 1. The phoneme error rate of the transducer is among the lowest recorded on TIMIT (the current benchmark is 20.5% (Dahl et al., 2010)). As far as we are aware, it is the best result with a recurrent neural network.

Nonetheless the advantage of the transducer over the CTC network on its own is relatively slight. This may be because the TIMIT transcriptions are too small a training set for the prediction network: around 150K labels, as opposed to the millions of words typically used to train language models. This is supported by the poor performance of the standalone prediction network: it misclassifies almost three quarters of the targets, and its per-phoneme loss is not much better than the entropy of the phoneme distribution (4.6 bits). We would therefore hope for a greater improvement on a larger dataset. Alternatively the prediction network could be pretrained on a large ‘target-only’ dataset, then jointly retrained on the smaller dataset as part of the transducer. The analogous procedure in HMM speech recognisers is to combine language models extracted from large text corpora with acoustic models trained on smaller speech corpora.

4 Analysis

One advantage of a differentiable system is that the sensitivity of each component to every other component can be easily calculated. This allows us to analyse the dependency of the output probability lattice on its two sources of information: the input sequence and the previous outputs. Fig. 3 visualises these relationships for an RNN transducer applied to ‘end-to-end’ speech recognition, where raw spectrogram images are directly transcribed with character sequences with no intermediate conversion into phonemes.

Conclusions and Future Work

We have introduced a generic sequence transducer composed of two recurrent neural networks and demonstrated its ability to integrate acoustic and linguistic information during a speech recognition task.

We are currently training the transducer on large-scale speech and handwriting recognition databases. Some of the illustrations in this paper are drawn from an ongoing experiment in end-to-end speech recognition.

In the future we would like to look at a wider range of sequence transduction problems, particularly those that are difficult to tackle with conventional algorithms such as HMMs. One example would be text-to-speech, where a small number of discrete input labels are transformed into long, continuous output trajectories. Another is machine translation, which is particularly challenging due to the complex alignment between the input and output sequences.

Ilya Sutskever, Chris Maddison and Geoffrey Hinton provided helpful discussions and suggestions for this work. Alex Graves is a Junior Fellow of the Canadian Institute for Advanced Research.

References