Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks

Training RNNs to label unsegmented sequences directly, e.g. transcribing speech into phonemes. Standard objectives are defined per time step, so RNNs needed pre-segmented training data and post-processing of their outputs into label sequences.

They need task-specific knowledge (HMM state models, CRF input features); they need explicit, often questionable dependency assumptions for tractable inference (e.g. independent observations in HMMs); and standard HMM training is generative although labelling is discriminative.

The HMM models long-range sequential structure, segments the data during training and turns the network’s local frame classifications into label sequences. Hybrids inherit the HMMs’ drawbacks and don’t exploit RNNs’ full power for sequence modelling.

Interpret the network outputs as a probability distribution over all possible label sequences given the input sequence, and train by directly maximizing the probability of the correct labelling. The objective is differentiable, so standard backpropagation through time works.

Temporal classification maps an input sequence \(\mathbf{x}\) of length \(T\) to a label sequence \(\mathbf{z}\) of length \(U \le T\), with no a priori alignment between them. Framewise classification labels each time step (frame) independently.

The total edit distance (insertions, substitutions, deletions) between the classifier’s outputs and the targets on a test set, divided by the total number of target labels: \(\text{LER}(h, S') = \frac{1}{Z} \sum_{(\mathbf{x}, \mathbf{z}) \in S'} \text{ED}(h(\mathbf{x}), \mathbf{z})\).

A softmax with one more unit than there are labels: \(y_k^t\) is the probability of label \(k\) at time \(t\), and the extra unit is the probability of a blank (no label). The probability of a path \(\pi\) of length \(T\) over labels plus blank is \(p(\pi \mid \mathbf{x}) = \prod_{t=1}^{T} y_{\pi_t}^t\), assuming outputs are conditionally independent given the network’s internal state.

It maps a path to a labelling by first merging repeated labels and then removing blanks: \(\mathcal{B}(a{-}ab{-}) = \mathcal{B}({-}aa{-}{-}abb) = aab\). A new label is emitted whenever the network switches from blank to a label or between different labels; a blank between two equal labels keeps them separate.

As the sum over all paths that collapse to it: \(p(\mathbf{l} \mid \mathbf{x}) = \sum_{\pi \in \mathcal{B}^{-1}(\mathbf{l})} p(\pi \mid \mathbf{x})\). Summing over alignments means no segmentation is needed.

A trained CTC network typically predicts each label as a short spike, separated by strongly predicted blanks, instead of aligning labels with manual segment boundaries as a framewise network must. Labels that always occur together (e.g. the closure dcl and the stop d) may appear as a double spike.

Take the most active output at every time step and collapse: \(h(\mathbf{x}) \approx \mathcal{B}(\pi^*)\), \(\pi^* = \arg\max_\pi p(\pi \mid \mathbf{x})\). It is trivial to compute but not guaranteed to find the most probable labelling, since that probability is spread over many paths.

A modified forward-backward algorithm computes the probability of extensions of labelling prefixes; the most probable remaining prefix is always expanded, until one complete labelling beats every remaining prefix. It finds the best labelling given enough time, but can take exponential time; in practice the output was split at points where blank probability exceeds a threshold, and each section decoded separately.

Maximum likelihood: minimize \(O^{ML} = -\sum_{(\mathbf{x}, \mathbf{z}) \in S} \ln p(\mathbf{z} \mid \mathbf{x})\), the same principle as standard network objectives. Its derivatives with respect to the outputs are backpropagated through time.

It works on a modified label sequence \(\mathbf{l}'\) with blanks added at the start, the end and between every pair of labels, so \(|\mathbf{l}'| = 2|\mathbf{l}| + 1\). Paths may start with a blank or the first label, and may end with the last label or the final blank.

\(\alpha_t(s) = \bar\alpha_t(s)\, y^t_{l'_s}\) if \(l'_s\) is blank or \(l'_{s-2} = l'_s\); otherwise \(\alpha_t(s) = (\bar\alpha_t(s) + \alpha_{t-1}(s-2))\, y^t_{l'_s}\), where \(\bar\alpha_t(s) = \alpha_{t-1}(s) + \alpha_{t-1}(s-1)\). Initialization: \(\alpha_1(1) = y^1_b\), \(\alpha_1(2) = y^1_{l_1}\). Result: \(p(\mathbf{l} \mid \mathbf{x}) = \alpha_T(|\mathbf{l}'|) + \alpha_T(|\mathbf{l}'| - 1)\).

Without the blank the repeated label would be merged by \(\mathcal{B}\) into a single a. So the skip transition \(s - 2 \to s\) is allowed only between different non-blank labels.

\(\alpha_t(s)\beta_t(s) / y^t_{l'_s}\) is the total probability of all paths for \(\mathbf{l}\) that pass through \(l'_s\) at time \(t\), so for any \(t\), \(p(\mathbf{l} \mid \mathbf{x}) = \sum_{s=1}^{|\mathbf{l}'|} \frac{\alpha_t(s)\beta_t(s)}{y^t_{l'_s}}\).

By rescaling the forward and backward variables at each time step by their sums \(C_t = \sum_s \alpha_t(s)\) and \(D_t = \sum_s \beta_t(s)\), as for HMMs. Then \(\ln p(\mathbf{l} \mid \mathbf{x}) = \sum_{t=1}^{T} \ln C_t\).

\(\frac{\partial O^{ML}}{\partial u_k^t} = y_k^t - \frac{1}{y_k^t Z_t} \sum_{s \in lab(\mathbf{z}, k)} \hat\alpha_t(s)\hat\beta_t(s)\), where \(lab(\mathbf{z}, k)\) are the positions of label \(k\) in \(\mathbf{z}'\) and \(Z_t\) normalizes: the output minus the posterior probability of \(k\) at time \(t\) over all valid alignments.

Initially, with small random weights, it is determined by the target sequence only; as the network starts predicting, the error localizes around its predictions; once it strongly predicts the correct labelling, the error virtually disappears.

A bidirectional LSTM (BLSTM), combining LSTM’s ability to bridge long time lags with bidirectional access to past and future context; standard BRNNs and unidirectional networks did worse. The hybrid baseline used the same architecture, for a fair comparison.

TIMIT phonetic labelling with 61 phonemes (4620 training, 1680 test utterances, 5% of training for validation). Audio was cut into 10 ms frames with 5 ms overlap, giving 12 MFCCs plus log-energy and their first derivatives: 26 coefficients per frame, normalized.

BLSTM with peepholes and forget gates, 100 blocks in each direction, a 62-unit softmax (61 phonemes plus blank), about 115k weights; online gradient descent with learning rate \(10^{-4}\), momentum 0.9, and Gaussian input noise (σ = 0.6) for generalization. The HMM baseline had over 900k parameters.

Label error rates: context-independent HMM 38.85%, context-dependent HMM 35.21%, BLSTM/HMM hybrid 33.84%, hybrid with weighted error 31.57%, CTC best path 31.47%, CTC prefix search 30.51%.

The hybrid gave long and short phonemes equal weight by scaling its framewise error. CTC’s objective depends only on the label sequence, not on durations or segmentation.

It needn’t locate inherently ambiguous boundaries (in speech or handwriting) and can group predictions of labels that occur together; segmenting is wasted effort if only labels are needed. It seems unsuited where segmentation is required, but its spikes roughly align with the input, enough for e.g. keyword spotting.

Not explicitly, unlike graphical models that assume a \(k\)th-order Markov chain over labels. It does so implicitly, through the RNN’s state, e.g. predicting labels that commonly occur together as a double spike.