CTC
How it works
1) The network outputs a softmax distribution over labels plus a blank symbol for each of T timesteps. 2) A collapse rule is defined: merge consecutive identical labels, then remove all blanks. 3) The probability of the target label sequence is the sum of the probabilities of all paths that collapse to it. 4) This sum and its gradients are computed with the forward-backward algorithm over the extended label sequence (blanks inserted between and around labels). 5) The loss is the negative log of this probability, computed in log-space for numerical stability. 6) At inference, the output is decoded by taking the most likely path (greedy/best-path) or via beam search (often combined with an external language model).
Problem solved
Traditional sequence learning required frame-level alignment between inputs and labels (e.g. which audio frame corresponds to which phoneme), which is costly and often unavailable. CTC removes the need for such alignment by training directly from (input sequence, label sequence) pairs.
Components
An extra label denoting no output at a timestep and separating repeated labels, enabling correct path collapsing.
Output layer producing a probability distribution over the label set augmented with blank, for each timestep.
Dynamic programming that sums the probabilities of all alignments consistent with the target sequence and computes gradients.
Procedure mapping network outputs to the final label sequence (best-path or beam search, optionally with a language model).
Implementation
Products of many small probabilities cause underflow; computations must be done in log-space.
Two identical adjacent labels in the target must be separated by a blank, otherwise the collapse rule merges them.
CTC assumes conditional independence of per-timestep labels given the input, yielding a weak implicit language model; it is usually combined with an external LM.
The number of timesteps must be sufficient to represent the label sequence (accounting for blanks between repeats).
Evolution
Graves et al. present CTC at ICML, enabling alignment-free RNN training on unsegmented sequence data.
Systems such as Deep Speech use CTC for end-to-end speech recognition without manual phoneme alignment.
Hyperparameters (configurable axes)
Position of the blank symbol in the label set; must match between training and decoding.
Number of hypotheses kept during beam-search decoding; trades quality for compute.
Number of output labels plus the blank symbol.
Computational complexity
Time complexity: O(T · L). Space complexity: O(T · L).
Parallelism
The network pass and batching are parallel, but the forward-backward recursion is sequential along the time axis.
Hardware requirements
CTC is a loss criterion and decoding method independent of specific hardware; it benefits from GPU/TPU acceleration like any neural-network training.