Connectionist Temporal Classification

CTC（Connectionist Temporal Classification）是为递归神经网络设计的一种输出层的损失准则。在语音领域，识别任务实际上是一种序列标记任务。比如，识别的目标就是要将观测到的帧序列映射到字符序列。传统的识别方案需要依靠因素分类器（即声学模型）得到当前观测帧的因素后验，之后借助解码网络得到最优路径从而得到字符序列。

但是，分类器并不能很好的进行序列标注任务。因为对于某一标注类别/label，分类器给出的是该类别/label出现可能的预测，这是一个沿时间轴的离散概率分布，对于连续label出现的情况，并不能直直接给出预测，而是要通过后续处理（比如解码，借助语言模型和字典等专业信息完成状态后验到最终的字符序列的映射）的方式完成对label序列概率分布的建模。其次，分类器的训练需要提前获知当前输入的标注信息。但是在实际任务中，比如因素状态分类器，通常无法直接从音频抄本中获知当前帧所对应的状态序列，所以，要借助已有的声学模型来获取，这一过程称为在识别任务中称为强制对齐（Force Alignment）。显然，声学模型，或者说分类器的表现效果十分依赖对齐的结果。

CTC允许RNN网络输出直接对label的标注序列进行预测，比如音素，字，词等等。所以，CTC具有以下优势：

1. CTC损失函数的计算只依赖于对于输入的序列标注信息，对于音频而言，就是抄本，而不需要获得每一次输入的状态标注，比如每一帧对应的因素状态这样的信息。如此，舍去了传统识别框架中的对齐操作，也避免了由于对齐效果差对模型训练造成的负面影响。

2. CTC层的输出直接给出的是标注序列的出现概率。比如标记的是关键词序列$K = {c_1, c_2, c_3}$，那么，网络可以直接给出对$K$的概率预测，而不需要借助后续处理。因此，相比于分类器的“窗型”输出，CTC的输出呈现尖峰效应，如下图所示（BLSTM+CTC的数字序列预测）。

假设CTC层输出可以将输入映射到label集合$A$，并在集合$A$之外定义一个空label符号$\epsilon$，令$A’ = A \cup {\epsilon}$。$\epsilon$符号表示当前输入不产生任何输出。对于一个长度为$T$的观测序列$\boldsymbol{x}$，CTC输出一条在集合$A’$上的序列$\pi$。假设每一时刻网络的输出概率都是独立的，那么可以得到序列$\pi$在给定长度为$T$的观测$\boldsymbol{x}$下的条件概率：

$$p(\pi | \boldsymbol{x}) = \prod_{t = 1}^{T} y_{\pi_t}^t$$

其中$y_{\pi_t}^t$表示在$t$时刻路径$\pi$对应的label出现的概率。考虑到最终要得到的是在集合$A$上的序列$\boldsymbol{l}$，所以还需要将$A’$上的序列$\pi$对应到$\boldsymbol{l}$上（训练阶段的抄本）。假设$A = {x, y}$，网络给出的路径$\pi$可能为${xx{\epsilon}xy{\epsilon}y, x{\epsilon}yy, x{\epsilon}{\epsilon}y}$，它们都可以对应到$A$上的一条序列$\boldsymbol{l} = xy$。若借助$\mathcal{F}: \pi \to \boldsymbol{l}$来表示这种多到一的映射关系，那么序列$\boldsymbol{l}$在给定观测$\boldsymbol{x}$下的条件概率为：

$$\begin{align} p(\boldsymbol{l} | \boldsymbol{x}) = \sum_{\pi \in \mathcal{F'}(\boldsymbol{l})} p(\pi | \boldsymbol{x}) \tag{1} \end{align}$$

CTC的设计原理就是要通过最大化$\boldsymbol{l}$在观测序列$\boldsymbol{x}$下的条件概率，从而达到优化网络的目的。在识别任务中，$\boldsymbol{l}$为音频对应的抄本，$\boldsymbol{x}$为音频对应的特征。CTC通过映射$\mathcal{F}$成功解决了在序列标注问题中，输入输出维度不一致的问题（抄本序列长度往往低于音频长度）。

定义$\boldsymbol{l}$的长度为$U$，下标为$u$的label $\boldsymbol{l}_u$，那么$p(\boldsymbol{l} | \boldsymbol{x})$计算的是在时刻$T$到达$\boldsymbol{l}_U$的所有可能路径$\pi$在给定观测$\boldsymbol{x}$下的条件概率之和。这个问题如果直接求解，枚举满足条件的$\pi$，计算复杂度很高。可以根据动态规划原理，定义子问题$\alpha_t( u)$（在时刻$t$到达$\boldsymbol{l}_u$的可能路径条件概率之和）和$\beta_t(u)$（从时刻$t$和$\boldsymbol{l}_u$开始到达$\boldsymbol{l}_U$的可能路径条件概率之和）间接求解。他们分别被称为前向，后向概率。

令$F_t(u)$和$B_t(u)$为前向，后向概率计算中的可能路径集合，那么，前向，后向概率由下式计算得到：

$$\begin{align} \alpha_t(u) &= \sum_{\pi \in F_t(u)} \prod_{i = 1}^{t} y_{\pi_t}^t \notag \\ \beta_t(u) &= \sum_{\pi \in B_t(u)} \prod_{i = t}^{T} y_{\pi_t}^t \notag \end{align}$$

据此，可以计算出$(1)$式，令：

$$\theta_t(u) = \alpha_t(u)\beta_t(u) = \sum_{\pi_t = \boldsymbol{l}_u, \mathcal{F}(\pi) = \boldsymbol{l}} \prod_{i = 1}^{T} y_{\pi_t}^t = \sum_{\pi_t = \boldsymbol{l}_u, \mathcal{F}(\pi) = \boldsymbol{l}} p(\pi | \boldsymbol{x}) \notag$$

那么

$$p(\boldsymbol{l} | \boldsymbol{x}) = \sum_{u = 1}^{|\boldsymbol{l}|} \theta_t(u)$$

实际在CTC的输出层是有空label $\epsilon$的，$\epsilon$被安插在每俩个相邻非空label之间。label序列$\boldsymbol{l}$被拓展为$\boldsymbol{l}’(U’ = 2U + 1)$。如果将前向，后向算法的搜索空间表示出来的话，如下图所示。

在状态$(t, u)$（即在时刻$t$，当前label为$\boldsymbol{l}’_u$），对于前向概率，有如下转移情况：

1. 如果当前label为空，那么$(t, u)$可以由状态$(t - 1, u)$和$(t - 1, u - 1)$得到。

2. 如果当前label非空，那么$(t, u)$可以由状态$(t - 1, u)$，$(t - 1, u - 1)$和$(t - 1, u - 2)$得到。

转移方程表示为：

$$\begin{equation} \alpha_t(u)= \begin{cases} [\alpha_{t-1}(u-1)+\alpha_{t-1}(u)]y_{\boldsymbol{l}'_u}^t, & \boldsymbol{l}'_u=\epsilon \text{ or } \boldsymbol{l'}_u=\boldsymbol{l}'_{u-2} \\ [\alpha_{t-1}(u-2)+\alpha_{t-1}(u-1)+\alpha_{t-1}(u)]y_{\boldsymbol{l}'_u}^t, & \text{otherwise} \end{cases} \notag \end{equation}$$

类似的，对于后向概率转移方程为：

$$\begin{equation} \beta_t(u)= \begin{cases} [\beta_{t+1}(u+1)+\beta_{t+1}(u)]y_{\boldsymbol{l}'_u}^t, & \boldsymbol{l}'_u=\epsilon \text{ or } \boldsymbol{l}'_u=\boldsymbol{l}'_{u+2} \\ [\beta_{t+1}(u+2)+\beta_{t+1}(u+1)+\beta_{t+1}(u)]y_{\boldsymbol{l}'_u}^t, & \text{otherwise} \end{cases} \notag \end{equation}$$

CTC层的损失函数通过似然函数表示，对于单个输入和标记label序列$(\boldsymbol{x}, \boldsymbol{l})$，似然函数为$\mathcal{L}(\boldsymbol{x}, \boldsymbol{l}) = -\ln p(\boldsymbol{l} | \boldsymbol{x})$，依次对CTC输出层的每个输出单元$y_s^t$求导（$1 \leqslant s \leqslant U + 1$）：

$$\begin{align} \frac{\partial \mathcal{L}(\boldsymbol{x}, \boldsymbol{l})}{y_s^t} = -\frac{\partial \ln p(\boldsymbol{l} | \boldsymbol{x})}{y_s^t} &= -\frac{1}{\ln p(\boldsymbol{l} | \boldsymbol{x})} \frac{\partial p(\boldsymbol{l} | \boldsymbol{x})}{y_s^t} \notag \\ &= -\frac{1}{\ln p(\boldsymbol{l} | \boldsymbol{x})} \sum_{u = 1}^{|\boldsymbol{l}'|} \frac{\partial \theta_t(u)}{y_s^t} \notag \\ &= -\frac{1}{\ln p(\boldsymbol{l} | \boldsymbol{x}) y_s^t} \sum_{u \in S(\boldsymbol{l}', s)} \theta_t(u) \notag \end{align}$$

其中$S(\boldsymbol{l’}, s) = {u: \boldsymbol{l’}_u = s}$。得到损失函数对输出层的导数之后，就可以按照RNN中梯度传递规则，对CTC层之前的RNN网络进行训练了。