CTC论文浅析

CTC的目标

传统的RNN Seq2Seq模型要求输入为预分段序列，且输出需要后处理（例如been search）得到标签化序列
然而很多seq2seq任务中的输入是无法预分段的，例如语音识别、手写识别等

我们将标签化未分段数据序列（ Labelling unsegmented data sequences）的任务称为Temporal Classification
当应用RNN于此类问题时，我们称为Connectionist Temporal Classification，即CTC

一般我们说的CTC指论文中提出的CTC Loss

论文地址：Connectionist Temporal Classification Labelling Unsegmented Sequence Data with Recurrent Neural Networks

注意2006年ICML会议上发表的初版论文中有几处公式错误（公式(14)(15)及(16)），虽然作者Alex Graves之后作出了更正，但很多学术搜索引擎仍会搜索出初版论文（还常常是引用量最高的），此处的链接是更正版本

讲解前先做一些符号定义

• $\mathcal{D_{X\times Z}}$ 为真实数据分布，$S$是其子集（即训练集），其中$\mathcal{X}=(\mathbb{R}^m)^{}$为输入序列的集合（$m$维向量组成的任意长度的序列）,$\mathcal{Z}=L^{}$则为输出序列集合（由定义在字母表$L$​上的标签组成的序列）​
• $(x,z)\in S$​ 是训练集的一对输入输出，$z=(z_1,z_2,…,z_U),\ x=(x_1,x_2,…,x_T)$​ ，注意一定要满足 $U\leq T$​

我们的目标就是让网络根据$S$学得映射 $h \ :\ \mathcal{X} \rightarrow \mathcal{Z}$

网络输出转换为标签序列

我们令$L^{‘}=L\bigcup {blank}$​​​，那么网络的输出是经softmax处理的$|L^{‘}|$​​​维向量组成的长为$T$​​​​的序列，其中blank表示不输出任何符号

设$x$​​是长为$T$​​的输入序列，$\mathcal{N_w}\ :\ (\mathbb{R}^m)^T \rightarrow (\mathbb{R}^{|L^{‘}|})^T$​​​是RNN学得的映射， $y=\mathcal{N_w}(x)$​​是$x$​​对应的输出
令$y_k^t$​​表示$t$​​时刻输出字母表$|L^{‘}|$​​中第$k$​​​​个字符的概率

我们将任意属于${L^{‘}}^T$​​的序列称为path，那么根据网络输出$y$​可以得到任意$\pi \in {L^{‘}}^T$​​​产生的概率
该式中隐含了网络不同时刻的输出是条件独立的

$$p(\pi | x)=\prod_{t=1}^Ty_{\pi_{t}}^t, \ \forall \pi \in {L^{'}}^{T}$$

然而$\pi$​​还不是最终结果，我们需要将$\pi$​​中相邻的重复字符和blank删除
即定义映射 $\mathcal{B}\ :\ {L^{‘}}^T \rightarrow L^{\leq T}$​​，则标签序列$l=\mathcal{B}(\pi)$​​​为最终结果​

举个例子说明，即$\mathcal{B}(a-ab-)=\mathcal{B}(-aa—abb)=aab$​
以语音识别为例说明这个操作的原因，不同的人语速不同，同一字符发音有时可能很长，删除重复字符可以防止类似ccccat这样的输出
而在字母表中添加blank则是为了防止原本应该重复的字符被删除
例如apple，若没有blank，可能导致$\mathcal{B}(apple)=aple$​，加入blank则为$\mathcal{B}(a-p-p-l-e)=apple$​​

此时我们可以得到任意最终标签序列$l$的概率

$$p(l|x)=\sum_{\pi \in \mathcal{B}^{-1}(l)}p(\pi|x)$$

CTC的前后向算法

显然网络输出应该是概率最大的标签序列$l$，即

$$h(x)=\arg \max_{l\in L^{\leq T}} p(l|x)$$

然而要枚举所有$\pi$​找到这个$l$​​显然是不可能的，因为总共由$|L^{‘}|^T$​个不同的标签序列$\pi$​​
一种简单的贪心思路是直接使用概率最大的$\pi$​，即

$$h(x)=\mathcal{B}(\pi^{*}) \\ \pi^{*} = \arg \max_{\pi \in N^T} p(\pi|x)$$

这样就只需要把$T$​​​个时刻中每个时刻概率最大的字符连接在一起
然而这种方法并不能保证一定的到正确的结果，因此作者引入了基于动态规划的前后向算法

前后向算法原理

对于某个目标标签序列$l$​​​，令$\alphat(s)$​​​​表示$t$​​​​时刻可以转化成$l{1:s}$​​​​​的所有path的概率和，即

$$\alpha_t(s)=\sum_{\pi \in N^T, \mathcal{B}(\pi_{1:t})=l_{1:s}}\prod_{t'=1}^t y_{\pi_{t'}^{t'}}$$

为了方便处理网络输出中包含的blank的概率，我们在目标标签序列 $l$​ 每两个字符间以及开头、结尾插入blank，记为$l’$​​
则$\alphat(s)$​​表示转化成$l^{‘}{1:s}$​或$l^{‘}_{1:s}$删除若干blank得到的的子序列的概率
例如$l=abcd,l’=-a-b-c-d-$​​，那么$\alpha_t(4)$​​表示转化成$-a-b、-ab、a-b、ab$​​的概率

以下将blank简记为b，初始条件为

$$\alpha_1(1)=y_b^1 \\ \alpha_1(2)=y_{l_1}^1 \\ \alpha_1(s)=0, \forall s>2$$

状态转移方程为

$$\alpha_t(s)=\begin{cases} \overline{\alpha}_t(s)y_{l'_s}^t & l'_s=b \ \mathrm{or}\ l'_{s-2}=l'_s\\ (\overline{\alpha}_t(s)+\alpha_{t-1}(s-2))y_{l'_s}^t & \mathrm{otherwise} \end{cases}$$

其中

$$\overline{\alpha}_t(s)=\alpha_{t-1}(s)+\alpha_{t-1}(s-1)$$

转移方程不难理解，首先$\alphat(s)$​​​​​​可以从$\alpha{t-1}(s-1)$​​​​​​转移来是显然的
当$l^{‘}s\not= b,\ l^{‘}{s-2}\not=l^{‘}s$​​​​​​时，因为之后会删除相邻重复字符，所以$\alpha_t(s)$​​​​​​还可以从$\alpha{t-1}(s)$​​​​​​转移来
而因为$l’$​​​​​​的第$s$​​​​​​和$s-2$​​​​​​个字符不同，即使没有blank分割也不会有上一节说的删除问题，所以$\alphat(s)$​​​​​​还可以从$\alpha{t-1}(s-2)$​​​​​​转移来

但是当$l^{‘}s=b$​时，若从$\alpha{t-1}(s-2)$​转移则会丢失blank之间的字符
但是当$l^{‘}s=l^{‘}{s-2}$​时，若从$\alpha_{t-1}(s-2)$​转移则会在删除重复字符时删除过多

还有一种特殊情况，即没有足够的输出来完成解码时

$$\alpha_t(s)=0,\ \forall s < |l'|-2(T-t)-1$$

最终我们得到

$$p(l|x)=\alpha_T(|l'|)+\alpha_T(|l'|-1)$$

同理我们定义$\betat(s)$​​表示$t$​​时刻可以转化成$l{s:T}$​​的所有path的概率和，即

$$\beta_t(s)=\sum_{\pi \in N^T, \mathcal{B}(\pi_{t:T})=l_{s:|l|}}\prod_{t'=1}^t y_{\pi_{t'}^{t'}}$$

同样用$l’$来处理，得到初始条件和状态转移方程

$$\beta_T(|l'|)=y_b^T \\ \beta_T(|l'|-1)=y_{l_{|l|}}^T \\ \beta_T(s)=0, \forall s<|l'|-1 \\ \beta_t(s)=0, \forall s>2t \\ \\ \beta_t(s)=\begin{cases} \overline{\beta}_t(s) y_{l^{'}_s}^t & l^{'}_s=b \ \mathrm{or} \ l^{'}_{s+2}=l^{'}_s \\ (\overline{\beta}_t(s)+\beta_{t+1}(s+2))y_{l^{'}_s}^t & \mathrm{otherwise} \end{cases} \\ \overline{\beta}_t(s)=\beta_{t+1}(s)+\beta_{t+1}(s+1)$$

前后向算法在应用中的改进

上述的前后向算法仍然存在两个问题

• 时间复杂度仍然较高，为$O(T|l’|)$

论文中引入了一种启发式方法
设定一个阈值，若某时刻预测blank的概率超过该阈值，则在此处将序列截断
这样可以将序列分成多个小段分别处理再合并结果

• $\alpha$和$\beta$​​​会产生下溢（underflow）

下溢即数值趋近于0，小于计算机所能表示的最小的数，通过如下缩放公式可以解决这个问题

$$C_t=\sum_s \alpha_t(s), \ \ \hat{\alpha}_t(s)=\frac{\alpha_t(s)}{C_t} \\ D_t=\sum_s \beta_t(s), \ \ \hat{\beta}_t(s)=\frac{\beta_t(s)}{D_t}$$

前后向算法与反向传播

根据定义，$\frac{\alphat(s)\beta_t(s)}{y{l^{‘}_s}^t}$​表示所有可以转化成$l$​且在$t$​时刻经过了字符$s$​的path的概率，即

$$\frac{\alpha_t(s)\beta_t(s)}{y_{l^{'}_s}^t}=\sum_{\pi \in \mathcal{B}^{-1}(l),\pi_t=l^{'}_s} p(\pi|x)$$

于是可以得到网络输出转化成$l$​​​​​的概率

$$p(l|x)=\sum_{s=1}^{|l'|}\frac{\alpha_t(s)\beta_t(s)}{y_{l^{'}_s}^t}$$

前文提到的初版论文公式错误中该公式 ( 公式(14) ) 错误的加入了$\sum_{t=1}^T$对$t$求和，而实际上无论$t$等于多少，$\alpha_t(s)\beta_t(s)$​​都已经隐含了所有时刻

接下来设$lab(l,k)$表示$l$中标签$k$出现的所有位置的集合，即$lab(l,k)={s | l^{‘}_s=k}$，则

$$
\frac{\partial p(l|x)}{\partial y_k^t}=\frac{1}