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

4.1 The CTC Forward-Backward Algorithm

1. How does the CTC forward-backward algorithm handle blanks?
   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.

   • Graves et al., 2006, Connectionist Temporal Classification (Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)), §4.1, pp. 372–373
2. Give the CTC forward recursion.
   \(\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)\).
   • Graves et al., 2006, Connectionist Temporal Classification (Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)), §4.1, pp. 372–373
3. Why can’t a CTC path skip the blank between two identical labels, e.g. in “aa”?
   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.
   • Graves et al., 2006, Connectionist Temporal Classification (Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)), §4.1, pp. 372–373
4. How do CTC’s forward and backward variables combine?
   \(\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}}\).
   • Graves et al., 2006, Connectionist Temporal Classification (Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)), §4.1, pp. 372–373
5. How did Graves et al. avoid numerical underflow in CTC?
   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\).
   • Graves et al., 2006, Connectionist Temporal Classification (Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)), §4.1, pp. 372–373