How does the CTC loss work?

Question

I am trying to implement CTC loss in TensorFlow, but their documentation is pretty limited. So I am not sure how to approach the problem. I found a good example in Theano.

Are any other resources that explain the CTC loss?

I am also trying to understand how its forward-backward algorithm works and what the beam decoder in the case of the CTC loss is.

Answer 1

Connectionist Temporal Classification (CTC) can be useful for sequence modeling problems, like speech recognition and handwritten recognition, where the input and output sequences might have different sizes, so there's the problem of aligning the sequences. For instance, in speech recognition, not all sounds in speech correspond to a character, so how do we know if a sound should be converted to one of the possible chars? Moreover, we assume that we don't have a training dataset where the input and output sequences are aligned. The creation/labeling of such a dataset would be quite consuming. That's why CTC was introduced.

So, mathematically, the speech/handwritten recognition task can be written as

$$ Y^* = \text{argmax}_Y p(Y \mid X), $$ where $Y^* = [y_1, \dots, y_M]$ is the ideal output sequence for $X = [x_1, \dots, x_T]$. Note that $T$ may be different from $M$.

Now, let's say that you have a speech $X = [x_1, \dots, x_N]$ and the output should be the sequence $Y^* = [h, e, l, l, o]$. One naive approach to solve this problem would be, for each input $x_i$, we would predict the most likely char, so we could end up with an output sequence like $\hat{Y} = [h, e, e, l, l, l, o]$ (when $T = 7$ and $M = 5$), then we could remove all duplicates, so we would end up with $\hat{Y}' = [h, e, l, o]$. However, this is not the correct approach, because, as you can see, there are words where the same letter appears twice in a row.

To solve this problem, we can introduce a special character, which we can denote by $\epsilon$. So, in this case, the idea is that $\epsilon$ should be predicted around exactly two (and not more or less) "l". Once the sequence is predicted, we can remove $\epsilon$ and, hopefully, we have a valid word, rather than a word like "helo" or "hellllo".

The idea of CTC is, for each $x_i$, the neural network produces a probability distribution over the possible chars, which we can denote by $p_t(a_t \mid X)$. In the example above, a probability distribution over $\{h, e, l, o, \epsilon \}$. So, for example, the probability vector for $x_1$ could be $p_1(a_1 \mid X) = [0.6, 0.1, 0.1, 0.1, 0.1]$. Given all probability vectors $p_t(a_t \mid X)$, for $t=1, \dots, T$, we can compute the probability of an alignment (a specific output sequence). Then we marginalize over the set of alignments.

To reflect these ideas, the CTC loss function is defined as follows

$$ p(Y \mid X)=\underbrace{\sum_{A \in \mathcal{A}_{X, Y}} }_{\text{Marginalization}\\\text{over set of}\\ \text{alignments}} \underbrace{\prod_{t=1}^{T} p_{t}\left(a_{t} \mid X\right)}_{\text{Probability}\\\text{for a single}\\\text{alignment}} $$ We can then use an RNN to model $p_t(a_t \mid X)$ given that RNNs are good for sequence prediction.

Now, another problem is that there can be many alignments, so the computation of the loss may be expensive if done naively. To solve this problem, you can use a dynamic programming algorithm, the CTC forward-backward algorithm. The details of how this is done, how the gradient of the CTC loss is computed, how inference is done in this context (including the details of beam search), and other details can be found in this nice article Sequence Modeling With CTC (2017) by Awni Hannun, which this answer is based on.

You can also read the original paper Connectionist Temporal Classification: Labeling Unsegmented Sequence Data with Recurrent Neural Networks (2006), by Alex Graves et al., mentioned in the linked TensorFlow documentation, which presents and explains the CTC loss and the CTC forward-backward algorithm (in section 4.1).