CTC 算法详解之测试篇

本来想把关于CTC的所有东西都写在一篇文章，但后面发现内容太多，遂拆分成如下几个部分：
CTC算法详解之训练篇
CTC算法详解之测试篇
CTC算法详解之总结展望篇（待更）

引言

CTC鼻祖论文[1]主要讨论了CTC网络的训练可微问题，而对于怎么测试，其本质是从网络的输出分布 $y$ 中搜索得到最优序列的问题，有非常多经典的算法能够完成CTC解码工作，除了[1]中提供的Best path decoding和Prefix search decoding外，还有Beam Search Decoding，Token Passing等等。本文先讲解[1]中描述的两种解码算法，我有时间了再添加Beam Search Decoding，Token Passing。

译码过程就是使输出标签概率最大化的过程，即 $h(x)=\text{argmax }p(l|x)$ ，其中标签 $l$ 的概率定义成所有正确路径的概率和： $p(l|x)=\sum_{\pi\in B^{-1}}p(\pi|x)$ ， $B^{-1}(l)$ 是 $B$ 的逆映射（ $B$ 的定义见《训练篇》），表示所有能映射成 $l$ 的路径。因为 $B$ 是many-to-one映射的缘故，故计算 $p(l|x)$ 要涉及到很多路径 $\pi$ 穷举所有的路径是非常困难的，其空间复杂度为 $O(N^T)$ ， $N$ 为字典大小， $T$ 为路径长度，实际操作中，我们会通过某些策略来缩小求解范围，加快计算。

1.最优路径解码（best path decoding）

这种解码方式是最快速的。best path decoding基于一个假设：概率最大的路径 $\pi$ 和概率最大的标签 $l^*$ 是一一对应的，把映射 $B$ 退化成了one-to-one映射，那么有 $h(x)≈B(\pi)$ ， $\pi=\text{argmax }p(\pi|x)$ 。

best path decoding的实现非常简单，把每个时刻概率最大的类别取出来，拼接得到路径 $\pi$ ，最后通过移除连续重复符号和blank得到标签。《训练篇》的图2即为这种解码方式。

然而best path decoding的前提不一定正确，比如有1条概率为0.1的路径可得到标签A，但有10条概率为0.05的路径可得到概率B，显然标签B比标签A更可信。所以这种方法是通过牺牲精度来换取速度，但实际应用中这种解码方式因为实现简单，速度快，并且精度能够接受，[1]表明，在精度上bset path decoding解码仅差Prefix Search Decoding1%，所以被广泛使用。

2.Prefix Search Decoding

比起搜索所有可能的标签，Prefix Search Decoding只搜索最大概率的的前缀，大大减少了搜索空间，然后每一步迭代都拓展这个前缀直到找出最优标签。

搜索过程如下：

1.每一次迭代中，我们有一个前缀集合，每个前缀对应一个概率。这个集合的初态仅包含一个空字符串，其概率为1。

2.从前缀集合中找出概率最大的前缀。对这个前缀我们可以选择拓展一个新符号或是将其作为最终的解码标签。
3.计算上一步中每种选择的概率。
4.如果将某前缀作为解码标签的概率大于该前缀的任何拓展概率，则找到了最优解码标签。
5.如果上一步不成立，则把拓展后的前缀作为新的前缀，替换老前缀，并更新前缀概率。
6.重复2~5，直到找出最优解码标签。

[1]提供了算法的直观示意图：

图1 Prefix Search Decoding示意图

如果允许的译码时常 $T$ 足够大，前缀搜索是能够找出真正的最佳结果的，但是算法的搜索空间随着T的增大是指数型增长的，为了解决这个问题，[1]使用了一种启发式策略来加速计算，把CTC的输出根据blank符号分割成数个片段（chunk），每个片断独立地使用prefix search decoding，最后再拼接起来。

目前为止我们只是粗略地讨论了算法流程，并没有讲到怎么计算步骤3中的概率，而这，正好是算法的核心与难点。为计算前缀相关的概率，我们要定义一些变量，然后通过动态规划算法来计算。用 $\gamma_t(p_n)$ 表示 $t$ 时刻译码得到前缀 $p$ 并且最后一个符号为非空的概率（n表示non-blank}），用 $\gamma_t(p_b)$ 表示 $t$ 时刻译码得到前缀 $p$ 并且最后一个符号为空的概率（b表示blank）。注意，前缀 $p$ 是由路径 $\pi$ 经过去重并且移除 $blank$ 符号得到的，所以 $p$ 中并不包含 $blank$ ，这里是指 $p$ 对应的路径 $\pi$ 的最后一个符号。

所以前缀 $p$ 作为标签的概率为（终止概率，比如图1第2行数字中的0.1）：

$P(p|x) = \gamma_t(p)=\gamma_T(p_n) + \gamma_T(p_b)\tag{1}$

其中 $T$ 为输入序列的长度（最大译码长度）。接下来我们要定义前缀 $p$ 的后缀为非空字符串的概率为（拓展概率，比如图1第2行数字中的0.7和0.2）：

$P(p\ldots|x) = \sum_{\ell \ne \varnothing} P(p + \ell | x) \tag2$

在定义公式（1）和（2）后我们就可以讨论怎么计算前面说的概率了。

我们来模拟译码的过程。首先将前缀集合初始化为 $P=\{\varnothing\}$ ，集合中只包含一个空字符串，用 $l^*$ 表示译码过程中得到的最优标签， $p^*$ 表示当前译码时刻的前缀， $l^*$ 和 $p^*$ 都初始化成空字符串。选取概率最大的一个前缀 $p^*$ ，对其拓展一个字符得到 $p'=p^*+k$ ， $k$ 可能是字典中的任意一个符号。对于每一个可能的 $k$ ，我们都要计算新序列作为整个标签的概率和新序列继续作为前缀的概率，即 $P(p'|x) = P(p^*+k|x)$ 和 $P(p'\ldots|x)$ 。整个算法的核心就是通过动态规划来计算这两个式子。

公式（1）的计算

容易有：

$\gamma_t(p'_n) = y_t(k) \big(\text{new}(t) + \gamma_{t-1}(p'_n)\big) \\ \gamma_t(p'_b) = y_t(b) \big(\gamma_{t-1}(p'_b) + \gamma_{t-1}(p'_n)\big) \tag3$

$new(t)$ 表示t时刻得到某个非空字符的概率。

公式（4）说明有两种方式可以在时刻t得到新字符 $k$ ：

如果前缀 $p^*$ 已经是以 $k$ 结尾的话，需要 $t-1$ 时刻序列 $p$ 以 $blank$ 结尾；
否在，上一时刻的前缀应以非 $k$ 符号结尾。比如路径-k-和abk都可以在第3个时刻得到新符号k，但-ka，kkk等路径则不行。

公式（3）的第一行表示，当路径不以 $blank$ 结尾时，我们不可能得到一个空的前缀，因为路径的末尾已经包含了一个non-blank符号，译码得到的整个前缀也肯定非空。

公式（3）的第二行表示，必须是连续的 $t$ 个 $blank$ 才可能译码得空前缀，我们只需将在将每个时刻的 $blank$ 概率相乘。

接下来讨论 $\gamma_t$ 的初态： $\gamma_1(p_n')$ 和 $\gamma_1(p_b')$ 。如果在第一个时刻输出 $blank$ 符号，就不存在前缀 $p$ 了，所以 $\gamma_1(p_b')$ 为不可能事件；而 $\gamma_1(p'_n)$ 很容易通过CTC的译码规则求出，为第1个时刻

的对应符号的激活概率：

$\begin{align*} \gamma_1(p_b')=0 \\ \gamma_1(p'_n) = y_1(k)\end{align*} \tag5$

特别的，对于空字符串前缀：

$\begin{align*} \gamma_t(\varnothing_n) = 0 \\ \gamma_t(\varnothing_b) = \prod_{i=1}^t y_i(b) \end{align*} \tag6$

在知道递推公式（3）和初态（5）的情况下，我们就可以计算任意 $\gamma_t$ 了，然后根据公式（1）计算前缀作为标签的概率（终止概率）。

公式（2）的计算

我们通过间接方式来计算拓展概率 $P(p'\ldots|x)$ 。拓展概率以=前缀概率-终止概率：

$P(p'\ldots|x) = P(p'\text{ is a prefix}|x) - P(p'|x)\tag7$

比如图2第2行有(0.7+0.2)=1-0.1

公式（8）中的拓展概率可以被拆解成1~T时刻的符号概率之和：

$P(p' \text{ is a prefix }|x) = \gamma_1(p'_n) + \sum_{t=2}^T y_t(k) \cdot \text{new}(t)\tag8$

迭代

现在我们能够计算某个前缀的拓展概率和终止概率了，每一步迭代如下：

如果新前缀 $p'$ 作为标签的概率比最佳标签 $l^*$ 的概率要高，即 $P(p'|x)>P(l^*|x)$ ，则用 $p'$ 更新 $l^*$ ；
如果 $p'$ 的拓展概率（未作其它符号前缀的概率）比最佳标签要高即 $P(p'\ldots|x) > P(\ell^*|x)$ ，则把 $p'$ 加入前缀集合 $P$ 中。

在完成前缀 $p*$ 相关的概率计算后：

把p从前缀集合中删除*；
根据最大的 $P(p^*\ldots|x)$ 找到新前缀，替换老前缀。

一直迭代下去，知道找不出概率大于最佳标签的前缀（ $P(p^*\ldots|x) < P(\ell^*|x)$ ），此时的 $l^*$ 即为最优解码标签。

整个算法可用如下伪代码来描述，图片摘自[4]：

下载.png

参考资料
[1] Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks
[2] CTC Algorithm Explained Part 2：Decoding the Network（CTC算法详解之解码篇）
[3]Speech Recognition with Neural Networks
[4]Supervised Sequence Labeling, Alex Gravessuoyi