CTC Algorithm Explained Part 2：Decoding the Network（CTC算法详解之解码篇）

CTC Algorithm Explained Part 2：Decoding the Network（CTC算法详解之解码篇）

Comments 26 comments


转载本文请注明出处：https://xiaodu.io/ctc-explained 作者：yudonglee

本文总共分为五部分来全面阐述CTC算法（本篇为Part 2）：
Part 1：Training the Network（训练算法篇），介绍CTC理论原理，包括问题定义、公式推导、算法过程等。Part 1链接。
Part 2：Decoding the Network（解码算法篇），介绍CTC Decoding的几种常用算法。Part 2链接。
Part 3：CTC Demo by Speech Recognition（CTC语音识别实战篇），基于TensorFlow实现的语音识别代码，包含详细的代码实战讲解。Part 3链接。
Part 4：CTC Demo by Handwriting Recognition（CTC手写字识别实战篇），基于TensorFlow实现的手写字识别代码，包含详细的代码实战讲解。Part 4链接。
Part 5：Conclusion（总结展望篇），总结CTC算法的理论局限性和适用场景，以及近年来相关的最新研究动态。Part 5链接。

在上一篇文章中我们详细介绍了CTC问题背景和模型训练的算法和原理，本篇是整体的第二部分，重点介绍CTC模型预测-解码算法。

一般在分类问题中，训练好模型之后，模型的预测过程非常简单，只需要加载模型文件从前到后执行即可得到分类结果。但在序列学习问题中，模型的预测过程本质是一个空间搜索过程，也称为解码，如何在限定的时间条件下搜索到最优解是一个非常有挑战的问题。下面，我们来详细介绍CTC的解码算法。

对CTC网络进行Decoding解码本质过程是选取条件概率最大的输出序列，即满足：argmax_{y}P(y|x)

解码单元为{a, b, _}，输入序列的长度为2，横轴为时间序列，纵轴为解码单元，栅格中的数字为输出概率

如上图的例子，按照时间序列展开得到栅格网络，解码的过程相当于空间搜索。我们可以选择暴力的解码策略：穷举搜索，但时间复杂度是指数级的N^{T}，显然不可行。我们也可以选择简单的解码策略：在每一步选择概率最大的输出值，这样就可以得到最终解码的输出序列（如上图例子，最终解码的输出序列l=blank）。然而，根据上一篇介绍我们知道，CTC网络的输出序列只对应了搜索空间的一条路径，一个最终标签可对应搜索空间的N条路径，所以概率最大的路径并不等于最终标签的概率最大，即不是最优解（如上图例子，最优解是p(l=b)而不是p(l=blank)）。

本篇我们介绍两种常见的CTC解码算法：CTC Prefix Search Decoding和CTC Beam Search Decoding。简而言之，Prefix Search Decoding是基于前缀概率的搜索算法，它能确保找到最优解，但最坏情况下耗时可能会随着序列长度呈指数增长；CTC Beam Search Decoding是一种Beam Search算法，它能在限定时间下找到近似解，但不保证一定能找到最优解。

1. CTC Prefix Search Decoding

CTC Prefix Search Decoding本质是贪心算法，每一次搜索都会选取“前缀概率”最大的节点扩展，直到找到最大概率的目标label，它的核心是利用动态规划算法计算“前缀概率”。下面先通过一个简单的例子来介绍CTC Prefix Search Decoding的大致过程，如下图。

最终label对应的字符集={a, b}，从根节点开始搜索扩展，其子节点为a、b和，每个节点上的数字表示其前缀概率，其中a和b为可扩展节点（表示可以往下扩展子节点），为结束节点（表示不可往下扩展子节点），最终搜索过程会在结束节点上停止，并输出最终的解码label与概率值。

如上图例子，CTC Prefix Search搜索过程：
1. 初始化最佳序列l ^{*} 为空集，最佳序列的概率p(l ^{*}) 。把根节点放入到扩展集合中，初始化它的前缀概率为1.0，初始化p(l ^{*})=0。
2. 从扩展集合中选取前缀概率最大的节点扩展，扩展子节点a和b，计算a和b的前缀概率（上图中第一层节点a和b的前缀概率分别为0.7和0.2），如果前缀概率大于p(l ^{*}) 则将其加入到扩展集合。同时，计算结束节点$的概率（上图中第一层节点$的概率为0.1），如果结束节点的概率大于p(l ^{*}) ，则将其对应的label设置为最佳序列l*，同时更新p(l ^{*}) 。
3. 继续搜索，重复步骤2，直到扩展集合为空，即搜索结束，输出最终解码的l*和概率p(l*)。（上图中最终l ^{*}=ab ，p(l ^{*})=0.3 ）

从上面的例子中可以看出，CTC Prefix Search的搜索过程非常简单，核心问题是如何计算前缀概率和每个结束节点对应的概率，它们的计算方式跟上一篇介绍前向概率和后向概率的动态规划算法类似，下面来正式介绍它们的定义与计算方式。

定义t时刻前缀为\rho 的概率为\gamma (\rho,t)：即在t时刻网络输出序列对应的label为\rho的概率。将\gamma (\rho,t)划分为两种情况：a）\gamma ^{-}(\rho,t)定义为t时刻网络输出blank空字符的概率，b）\gamma ^{+}(\rho,t)定义为t时刻网络输出非空字符的概率，则\gamma (\rho,t) = \gamma ^{-}(\rho,t) + \gamma ^{+}(\rho,t)。更加正式的定义如下：

定义L为建模单元的字符集（如上图例子中的{a, b}），{L}'为加入blank空字符后的扩展字符集（如上图例子中的{a, b, -}），\ss 是网络输出路径\pi 到输出序列l 的映射函数：\ss(\pi)=l ，路径集合Y = \{\pi \in {L}'^{t} : \ss (\pi)=\rho\} ，t时刻的前缀\rho的概率\gamma (\rho, t) = \sum_{\pi \in Y}p(\pi|x)，\gamma ^{+} (\rho, t) = \sum_{\pi \in Y : \pi_{t}=\rho_{|\rho|}}p(\pi|x)，\gamma ^{-} (\rho, t) = \sum_{\pi \in Y : \pi_{t}=blank}p(\pi|x)，最终序列l（假定输入序列长度为T）的概率p(\rho|x) = \gamma (\rho, T) = \gamma ^{-} (\rho, T) + \gamma ^{+} (\rho, T)，p(\rho...|x)=\sum_{s\neq \phi }^p(\rho + s | x)。

CTC Prefix Search算法过程

在给定足够时间的条件下CTC Prefix Search Decoding总能搜索到最大概率值，但随着输入序列长度的增加，搜索过程扩展的前缀可能呈指数级增加。所以在实际应用中为了能够在限定时间的条件下找到近似解，需要增加一些启发式的搜索剪枝策略，比如，分而解之的思路：将搜索空间按照空字符blank来划分为更小的子空间，再针对每个子空间进行CTC Prefix Search。

另外，在语音识别等实际应用中，解码过程往往还要加上一些条件约束，即满足：argmax_{l}p(l|x, G)，其中G可以是语言模型或语法等约束[4]，取决于具体应用的条件设定。p(l|x, G)=\frac{p(l|x)p(l|G)p(x)}{p(x|G)p(l)}，假定p(x)、p(x|G)和p(l)概率同等，则解码的目标是：argmax_{y}p(l|x)p(l|G)。所以，实际应用中可以在解码过程加上限定约束条件，比如，在语音识别中p(l|G)可以对应为语言模型或发音模型的概率。

2. CTC Beam Search Decoding

CTC Beam Search Decoding算法虽然简单，但在实际中应用广泛，我们有必要深入了解它的具体实现细节。Beam Search的过程非常简单，每一步搜索选取概率最大的W个节点进行扩展，W也称为Beam Width，其核心还是计算每一步扩展节点的概率。我们先从一个简单的例子来看下搜索的穷举过程，T=3，字符集为{a, b}，其时间栅格表如下图：

横轴表示时间，纵轴表示每一步输出层的概率，T=3，字符集为{a, b}

如果对它的搜索空间进行穷举搜索，则每一步都展开进行搜索，如下图所示：

如上所述，穷举搜索每一步都要扩展全部节点，能保证最终找到最优解（上图中例子最优解l*=b，p(l*)=0.164），但搜索复杂度太高，而Beam Search的思路很简单，每一步只选取扩展概率最大的W个节点进行扩展，如下图所示：

由此可见，Beam Search实际上是对搜索数进行了剪枝，使得每一步最多扩展W个节点，而不是随着T的增加而呈指数增长，降低了搜索复杂度。

下面我们再介绍CTC Beam Search中最核心的一步，计算节点扩展概率：\gamma (\rho,t)。跟上一节一样，定义t时刻前缀为\rho 的概率为\gamma (\rho,t)：即在t时刻网络输出序列对应的label为\rho的概率。另外，定义\hat{\rho}为\rho 的前继前缀，比如\rho=ab，则\hat{\rho}=a；定义\rho^{e}为字符串\rho的结尾字符，比如\rho=abc，则\rho^{e}=c；定义\hat{\rho}^{e}为字符串\hat{\rho}的结尾字符，比如\hat{\rho}=ab，则\hat{\rho}^{e}=b。将\gamma (\rho,t)划分为两种情况：a）\gamma ^{-}(\rho,t)定义为t时刻网络输出blank空字符的概率，b）\gamma ^{+}(\rho,t)定义为t时刻网络输出非空字符的概率，则\gamma (\rho,t) = \gamma ^{-}(\rho,t) + \gamma ^{+}(\rho,t)，我们可以递归求解\gamma ^{-}(\rho,t)和\gamma ^{+}(\rho,t)，如下：

至此，CTC Beam Search的求解过程就基本介绍完了，如上一节所述，在实际应用中往往需要加上一些条件约束，比如语言模型或语法约束等，我们对扩展字符的过程加上约束，修改\gamma ^{-}(\rho,t)和\gamma ^{+}(\rho,t)的递归求解如下：

其中，Pr(\rho ^{e}|\hat{\rho})表示从\hat{\rho}到\rho的扩展概率

综上所述，CTC Beam Search的算法过程如下：

References

  1. Graves et al., Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with RNNs. In ICML, 2006. （Graves提出CTC算法的原始论文）
  2. Graves et al., A Novel Connectionist System for Unconstrained Handwriting Recognition. In IEEE Transactions on PAML, 2009.（CTC算法在手写字识别中的应用）
  3. Graves et al., Towards End-to-End Recognition with RNNs. In JMLR, 2014.（CTC算法在端到端声学模型中的应用）
  4. Alex Graves, Supervised Sequence Labelling with Recurrent Neural Networks. In Studies in Computational Intelligence, Springer, 2012.（ Graves 的博士论文，关于sequence learning的研究，主要是CTC）

Loading

26 thoughts on “CTC Algorithm Explained Part 2：Decoding the Network（CTC算法详解之解码篇）”

  1. 非常謝謝大牛的分享，此外，我在搜索一些資料的時候，有看到prefix beam search的內容，大概是關於在不同的path構建中，遇到blank_token就加入當前path，如果遇到非blank_token就提前做一個去重複，去除blank_token的操作（目的是為了讓當前能夠生成相同label的path做一個合併動作），只是問題在於，我不清楚這個操作，是在beam_search 選取top n的path後做的，還是先有這個操作，再排名並選取top n 這樣？

    Reply

  2. 抱歉，還有一個小小的問題想請教一下，如果說我們現在就是在top n中進行這種操作，那麼比如說，當前能夠生成相同label的path，他們會捨棄掉概率最小的一條？還是說兩者都保留？另外這兩條path的概率分數該如何處理哈？

    Reply

    1. 1. 第一个问题，你可以参考文中CTC Beam Search的伪代码（第12~13行），每次遇到blank都会进行合并，然后再扩展子节点
      2. 第二个问题，遇到相同的label则进行合并，他们概率会相加，合并后只保留一个节点，代码也同样参考CTC Beam Search的伪代码（第12~13行）

      Reply

  4. t时刻的前缀的概率,那边的伽马+，伽马-写错了吧，作者仔细看看哈

    Reply

  5. 作者您好，CTC Beam Search伪代码中第十一行能详细解释下吗，这一步没有看懂。t时刻的网络输出的序列对应的label为p，那t-1时刻网络输出的序列对应的label不应该是p^吗？

    Reply

    1. 可以仔细看下gamma+(p,t)的定义，这行代码对应的就是它定义的实现。你可能看漏的细节是：从“ab”扩展到“abb”对应的最后label是“ab”，而从“ab_”扩展到“ab_b”对应的最后label才是“abb”

      Reply

  6. Beam Search Decoding里面穷举搜索的时候最后b是表示b__、_b_、__b么？如果是最后的概率是0.3*0.4*0.6+0.5*0.3*0.6+0.5*0.4*0.1=0.182，是我哪里理解有问题吗？

    Reply

    1. 你的理解是对的，图中0.164算错了，应该是0.182，已经修正更新，谢谢

      Reply

  8. 作者您好，我认为原论文中，prefix search decoding 算法24行有问题，应该是 probRemaining -= p(p | x)， 将已经不能再扩展的节点概率减去, 您觉得呢？

    Reply

  9. 请问一下，Beam Search Decode T2时刻是a的概率为什么是0.23，如果t1时刻选择了a，那么要使t2时刻输出a则t2时刻只能选择a或者blank即（aa, a-）概率为0.14，而你的0.23很明显是（-a，a-）的概率，如果是总的概率（-a，aa,a-）0.29. 为何结果是0.23，不是合并了重复的路径吗？还有，上面最终输出的结果是a的概率为0.198不是比b的0.182概率更大。

    Reply

    1. beam search算法第十二行应该是B不是B^吧，因为保证值计算过就好了，没必要非要在最大的M个里面吧

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *