# A Linear Memory CTC-Based Algorithm for Text-to-Voice Alignment of Very Long Audio Recordings
## 3 Method
### The CTC Alignment Algorithm
#### 3.3.1 Definitions  
Let \(\mathcal{L}\) denote a finite alphabet of labels, and \(\mathcal{L}^{*}\) denote the set of label sequences, called _labellings_. We also define \(\mathcal{L}_{\varepsilon}=\mathcal{L}\cup\{\varepsilon\}\), where \(\varepsilon\) is a blank label, and let \(\mathcal{L}_{\varepsilon}^{*}\) denote the set of sequences of labels and blanks, subsequently called the _labelling extension_ or simply _extensions_.  
Let \(\mathcal{M}:\ \mathcal{L}_{\varepsilon}^{T}\mapsto\mathcal{L}^{\leq T}\) denote the many-to-one function mapping different extensions of length \(T\) to a single labelling of length \(\leq T\) by removing the successive duplicated labels and blanks. For instance, the following different extensions are mapped to the same labelling:  
\[\left.\begin{array}{c}heeelello\\ hheeeleloe\\ eeleleloo\end{array}\right\}\xrightarrow{\mathcal{M}}\mathit{hello}\]  
A _connectionist temporal classifier_ (CTC) is a neural network whose input is a feature sequence \(\mathbf{x}\), and whose output \(\mathbf{p}\) is a \(|\mathcal{L}_{\varepsilon}|\times T\) tensor, called a _posteriorgram_. The last layer is a softmax layer applied on the first dimension; thus, each timeframe at instant \(t\) is interpreted as the probability mass function of the label discrete probability distribution over \(\mathcal{L}_{\varepsilon}\). More precisely, if we denote \(p(k,t|\mathbf{x})\), the output corresponding to the \(k^{th}\) label at time \(t\), \(p(k,t|\mathbf{x})\) represents the probability of observing label \(k\) at time \(t\), given the input sequence \(\mathbf{x}\).  
A posteriori thus defines a distribution over the set of possible labelling extensions of length \(T\), as visualized on Figure 7. The conditional probability of a given labelling extension \(\mathbf{b}\in\mathcal{L}_{\varepsilon}^{T}\) is thus:  
\[p(\mathbf{b}|\mathbf{x})=\prod_{t=1}^{T}p(b_{t},t|\mathbf{x}) \tag{12}\]  
The conditional probability of any labelling of \(\mathbf{l}\in\mathcal{L}^{\leq T}\) is thus the sum of the probability of all its corresponding extensions:  
\[p(\mathbf{l}|\mathbf{x})=\sum_{\mathbf{b}\in\mathcal{M}^{-1}(\mathbf{l})}p( \mathbf{b}|\mathbf{x}) \tag{13}\]  
A CTC network is trained to find the most likely labelling \(\mathbf{l}^{*}\in\mathcal{L}^{\leq T}\), maximising Equation (13):  
\[\mathbf{l}^{*}=\operatorname*{arg\,max}_{\mathbf{l}\in\mathcal{L}^{\leq T}}p( \mathbf{l}|\mathbf{x}) \tag{14}\]The objective function of Equation (13), called the _CTC loss_, is usually intractable in its direct form, because a labelling has typically too many extensions. The idea proposed by [PERSON] et al. was to compute the probability in Equation (13) recursively, similarly to what was conducted with the alignment measure of Equation (5).  
Consider the first \(t-1\) labels in \(\mathbf{b}\). By definition of the extensions, there are different possibilities for the next label, depending on whether the last one is blank or non-blank:  
* If it is a blank label \(\epsilon\), the next label can be \(\epsilon\) or the next non-blank label \(l_{s}\).
* If it is a non-blank label \(l_{s-1}\), the next label can either be the same label \(l_{s-1}\), the blank label \(\epsilon\), or the next label, \(l_{s}\), if \(l_{s-1}\
eq l_{s}\).  
These permitted transitions are depicted in the Figure 8.  
The trick proposed by [PERSON] et al. to account for transitions to and from \(\epsilon\) in Figure 8 was to consider a new sequence \(\mathbf{a}\) obtained interleaving \(\epsilon\) between each label pair of \(\mathbf{l}\), and adding \(\epsilon\) at the beginning and the end. Consequently, \(|\mathbf{a}|=2|\mathbf{l}|+1\), and if we let \(i\) denote the index of \(\mathbf{a}\), \(i=2s\), as depicted in Figure 9.  
Figure 8: CTC labelling-permitted extensions  
Figure 7: The posteriorgram of the first sentence of chapter 10 of “The problems of philosophy”, by [PERSON]. Audio publicly available on Librivox. See Section 4.2 for details.