Connectionist Temporal Classification.

paper：Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks

在文本识别、语音识别等任务中，输入和输出可能不是对齐的，而是受不同人的书写习惯和说话速度影响：

Connectionist Temporal Classification (CTC)正适合这种不知道输入输出是否对齐的情况使用的算法。

为了方便描述，做如下定义，输入(如音频信号)用符号序列$X=[x_1,x_2,…,x_T]$表示，对应的输出(如对应的标注文本)用符号序列$Y=[y_1,y_2,…,y_U]$表示，为了方便训练这些数据,希望能够找到输入$X$与输出$Y$之间精确的映射关系。

输入和输出的特点：

$X$和$Y$都是变长的；
$X$和$Y$的长度比也是变化的；
$X$和$Y$相应元素之间没有严格的对齐（即$x_t$和$y_u$不一定对齐）。

需要明确的是，CTC常用的场景是RNN后接CTC算法，（以语音识别为例）RNN模型输入是划分后的$T$个音频片段，输出$T$个概率向量，每个向量又由字典个数$N$的概率组成，则RNN输出的维度为$T×N$。根据这个概率输出分布，就能得到最可能的输出结果。

1. 对齐

CTC算法对于输入$X$能给出非常多不同的$Y$(RNN输出概率分布矩阵，所以通过矩阵中元素的组合可以得到很多$Y$值作为最终输出)，在计算输出过程的一个关键问题就是CTC算法如何将输入和输出进行对齐。

CTC算法并不要求输入输出是严格对齐的。引入的一个新的占位符用于输出对齐的结果。这个占位符称为空白占位符，通常使用符号$ε$，这个符号在对齐结果中输出，但是在最后的去重操作会将所有的$ε$删除得到最终的输出。利用这个占位符，可以对输入与输出建立非常合理的对应关系，如下图所示：

在这个映射方式中，如果在标定文本中有重复的字符，对齐过程中会在两个重复的字符当中插入$ε$占位符。利用这个规则，上面的“hello”就不会变成“helo”了。

CTC算法的对齐方式有下列属性：

输入与输出的对齐方式是单调的，即如果输入下一片段时输出会保持不变或者也会移动到下一个时间片段
输入与输出是多对一的关系
输出的长度小于等于输入

2. 目标函数

CTC算法的目标函数如下：

\[p(Y \mid X) = \sum_{A \in A_{X,Y}}^{} {\prod_{t=1}^{T} {p_t(a_t \mid X)}}\]

RNN输出的就是概率$p_t$，$t$表示时间步。乘法表示一条路径的所有字符概率相乘，加法表示多条路径对应同一个序列。因为CTC对齐输入输出是多对一的，例如$heεlεloε$和$heeεlεlo$对应的都是$hello$，这就是同一个输出的其中两条路径，要将所有的路径相加才是输出的条件概率。

对于一个输出，路径会非常的多，这样直接计算概率是不现实的，CTC算法采用动态规划的思想来求解输出的条件概率。

假设输入音频$X$对应的标签输出$Y$为单词“ZOO”，为了方便解释下面动态规划的思想，现在每个字符之间还有字符串的首末位插入空白占位符$ε$，得到序列$Z= [ ε,Z,ε,O,ε,O,ε ]$，则输出$zoo$对应所有可能的合法路径为：

上图横轴$X$对应时间步$T$，假设有$9$个时间步；纵轴$Z$为序列可取的值。

直观解释：寻找所有合法的对应输出为$zoo$的长度为$9$的路径。

从图中可以看到合法路径由两个起始点（$ε$或$z$），输出两个终止点（$ε$或$o$），最后输出的条件概率为所有合法路径出现概率的和。使用这种计算方法就能高效的计算损失函数。

记$p_{s,t}$表示第$t$个时间步输出为字符$s$($s$按构造序列$Z$的位置)的概率，$α_{s,t}$表示上图中路径到达坐标为$(s,t)$节点的概率（即生成长度为$t$且最后一位为$s$的未化简序列的概率）。

情况1：

第$t$个时间步输出的字符$s$是空白字符$ε$或输出序列中连续重复的字符（如$zoo$中的第二个$o$），则其前一个字符可能是空白字符$ε$（对应$s-1$）或本字符（对应$s$）：

\[α_{s,t} = (α_{s-1,t-1}+α_{s,t-1})p_{s,t}\]

情况2：

第$t$个时间步输出的字符$s$是输出序列中不连续首字符（如$zoo$中的第一个$o$），则其前一个字符可能是空白字符$ε$（对应$s-1$）或本字符（对应$s$）或上一个字符（对应$s-2$）：

\[α_{s,t} = (α_{s-1,t-1}+α_{s,t-1}+α_{s-2,t-1})p_{s,t}\]

下一步的工作是计算梯度用于训练模型。由于$p(Y \mid X)$的计算只涉及加法和乘法，因此是可导的。对于训练集$D$，模型优化的目标是最小化负对数似然函数:

\[\sum_{(X,Y) \in D}^{} {-log(p(Y \mid X))}\]

3. 预测

当训练好一个模型后，输入$X$，目标是计算下式得到输出：

\[Y^* = \mathop{\arg\max}_{Y} p(Y \mid X)\]

可以采用：

贪婪算法
Beam search

（1）贪婪算法

贪婪算法取RNN每次输出概率最大的节点，然后通过去重得到输出结果:

\[A^* = \mathop{\arg\max}_{A} \prod^{T}_{t=1}p_{t}(a_{t}|X)\]

通常这种启发式的算法很有效，但是这种方法忽略了一个输出可能对应多个对齐结果。例如$[a,a,\epsilon]$和$[a,a,a]$各自的概率均小于$[b,b,b]$的概率，但是他们相加的概率比$[b,b,b]$概率高。

（2）Beam search

Beam search算法设置了参数宽度，假设宽度为$3$，在RNN的输出中，该算法每个时间$t$输出时，寻找最高的三个概率作为下一次的输入，依次迭代，如上图所示。每次$t$时间都是基于$t-1$输出的最高三个查找当前概率最高的三个(当宽度设置为$1$时就是贪婪算法)。

由于想要结合多个对齐能够映射到同一输出的这种情况，这时每次$t$时间的输出为去重后以及移除$\epsilon$的结果:

4. 代码实现

Pytorch中有现成的CTC接口：

torch.nn.CTCLoss(blank=0,reduction='mean',zero_infinity=False）

Tensorflow中也有现成的CTC接口：

tf.nn.ctc_loss(
    labels,
    inputs,
    sequence_length,
    preprocess_collapse_repeated=False,
    ctc_merge_repeated=True,
    ignore_longer_outputs_than_inputs=False,
    time_major=True
)