CTC Algorithm Explained Part 2:Decoding the Network(CTC算法详解之解码篇)


转载本文请注明出处: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)

CTC Algorithm Explained Part 1:Training the Network(CTC算法详解之训练篇)

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

现实应用中许多问题可以抽象为序列学习(sequence learning)问题,比如词性标注(POS Tagging)、语音识别(Speech Recognition)、手写字识别(Handwriting Recognition)、机器翻译(Machine Translation)等应用,其核心问题都是训练模型把一个领域的(输入)序列转成另一个领域的(输出)序列。近年来基于RNN的序列到序列模型(sequence-to-sequence models)在序列学习任务中取得了显著的效果提升,本文介绍一种RNN(Recurrent Neural Networks)的端到端训练方法——CTC(Connectionist Temporal Classification)算法,它可以让RNN直接对序列数据进行学习,而无需事先标注好训练数据中输入序列和输出序列的映射关系,打破了RNN应用于语音识别、手写字识别等领域的数据依赖约束,使得RNN模型在序列学习任务中取得更好的应用效果。

本文总共分为五部分来全面阐述CTC算法(本篇为Part 1):
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链接。

接下来,我们先从“问题”的背景说起。

1. 背景介绍

在序列学习任务中,RNN模型对训练样本一般有这样的依赖条件:输入序列和输出序列之间的映射关系已经事先标注好了。比如,在词性标注任务中,训练样本中每个词(或短语)对应的词性会事先标注好,如下图(DT、NN等都是词性的标注,具体含义请参考链接)。由于输入序列和输出序列是一一对应的,所以RNN模型的训练和预测都是端到端的,即可以根据输出序列和标注样本间的差异来直接定义RNN模型的Loss函数,传统的RNN训练和预测方式可直接适用。

然而,在语音识别、手写字识别等任务中,由于音频数据和图像数据都是从现实世界中将模拟信号转为数字信号采集得到,这些数据天然就很难进行“分割”,这使得我们很难获取到包含输入序列和输出序列映射关系的大规模训练样本(人工标注成本巨高,且启发式挖掘方法存在很大局限性)。因此,在这种条件下,RNN无法直接进行端到端的训练和预测。

如下图,输入是“apple”对应的一段说话音频和手写字图片,从连续的音频信号和图像信号中逐一分割并标注出对应的输出序列非常费时费力,在大规模训练下这种数据要求是完全不切实际的。而如果输入序列和输出序列之间映射关系没有提前标注好,那传统的RNN训练方式就不能直接适用了,无法直接对音频数据和图像数据进行训练。

因此,在语音识别、图像识别等领域中,由于数据天然无法切割,且难以标注出输入和输出的序列映射关系,导致传统的RNN训练方法不能直接适用。那么,如何让RNN模型实现端到端的训练成为了关键问题。

Connectionist Temporal Classification(CTC)[1]是Alex Graves等人在ICML 2006上提出的一种端到端的RNN训练方法,它可以让RNN直接对序列数据进行学习,而无需事先标注好训练数据中输入序列和输入序列的映射关系,使得RNN模型在语音识别等序列学习任务中取得更好的效果,在语音识别和图像识别等领域CTC算法都有很比较广泛的应用。总的来说,CTC的核心思路主要分为以下几部分:

  • 它扩展了RNN的输出层,在输出序列和最终标签之间增加了多对一的空间映射,并在此基础上定义了CTC Loss函数
  • 它借鉴了HMM(Hidden Markov Model)的Forward-Backward算法思路,利用动态规划算法有效地计算CTC Loss函数及其导数,从而解决了RNN端到端训练的问题
  • 最后,结合CTC Decoding算法RNN可以有效地对序列数据进行端到端的预测

接下来,通过一个语音识别的实际例子来引出CTC的解决思路

2. 一个实际的例子–声学模型

语音识别的核心问题是把一段音频信号序列转化文字序列,传统的语音识别系统主要分为以下几部分,如下图。

其中,X表示音频信号,O是它的特征表示,一般基于LPC、MFCC等方法提取特征,也可以基于DNN的方式“学到”声学特征的表示。为了简化问题,我们暂且把O理解为是由实数数组组成的序列,它是音频信号的特征表示。Q是O对应的发音字符序列,即建模单元,一般可以是音素、音节、字、词等。W是音频信号X对应的文字序列,即我们最终的识别结果。

如图所示,核心问题是通过解码器找到令P(W|X)最大化的的W,通过贝叶斯公式可将其分解为P(O|Q)、P(Q|W)、P(W),分别对应声学模型、发音模型、语言模型。

其中,声学模型就是对P(O|Q)进行建模,通过训练可以“学到”音频信号和文字发音间的联系。为了简化问题,我们假定声学模型的建模单元Q选择的是音节,O选择的是MFCC特征(由39维数组组成的序列)。

如下图,输入序列是一段“我爱你中国”的音频,输出序列是音节序列“wo3 ai4 ni3 zhong1 guo2”,如果训练样本中已经“分割”好音频,并标注好它和音节的对应关系,则RNN模型如下:

然而,如前面所述,对音频“分割”并标注映射关系的数据依赖是不切实际的,实际情况是对音频按照时间窗口滑动来提取特征,比如按照每10毫秒音频提取特征得到一个N维数组。如下图所示:

由于人说话发音是连续的,且中间也会有“停顿”,所以输出序列中存在重复的元素,比如“wo3 wo3”,也存在表示间隔符号“_”。需从输出序列中去除掉重复的元素以及间隔符,才可得到最终的音节序列,比如,“wo3 wo3 ai4 _ ni3 _ zhong1 guo2 _” 归一处理后得到“wo3 ai4 ni3 zhong1 guo2”。因此,输出序列和最终的label之间存在多对一的映射关系,如下图:

RNN模型本质是对𝒑(𝒛│𝒙)建模,其中x表示输入序列,o表示输出序列,z表示最终的label,o和l存在多对一的映射关系,即:𝒑(𝒛│𝒙)=sum of all P(o|x),其中o是所有映射到z的输出序列。因此,只需要穷举出所有的o,累加一起即可得到𝒑(𝒛│𝒙),从而使得RNN模型对最终的label进行建模。

经过以上的映射转换,解决了端到端训练的问题,RNN模型实际上是对映射到最终label的输出序列的空间建模。然而,对每一个z都“穷举所有的o”,这个计算的复杂度太大,会使得训练速度变得非常慢,因此怎么更高效地进行端到端训练成为待解决的关键问题。

通过以上的实际例子,我们对问题的解决思路有了更加直观的了解,接下来就开始正式介绍CTC的理论原理。

3. 问题定义

以RNN声学模型为例子,建模的目标是通过训练得到一个RNN模型,使其满足:

本质上是最大似然预估, S是训练数据集,X和Z分别是输入空间(由音频信号向量序列组成的集合)和目标空间(由声学模型建模单元序列组成的集合),L是由输出的字符集(声学建模单元的集合),且x的序列长度小于或等于z的序列长度。

接下来,在介绍如何计算Loss函数之前,我们需要对RNN输出层做一个简单的扩展。

4. RNN输出层扩展

如下图,为了便于读者理解,简化了RNN的结构,只有单向的一层LSTM,把声学建模单元选择为字母{a-z},并对建模单元字符集做了扩展,且定义了从输出层到最终label序列的多对一映射函数,使得RNN输出层能映射到最终的label序列。

所以,如果要计算𝒑(𝒛│𝒙),可以累加其对应的全部输出序列(也即映射到最终label的“路径”)的概率即可,如下图。

5. CTC Loss函数定义

如下图,基于RNN条件独立假设,即可得到CTC Loss函数的定义:

假定选择单层LSTM为RNN结构,则最终的模型结构如下图:

6. CTC Loss函数计算

由于直接暴力计算 𝒑(𝒛│𝒙)的复杂度非常高,作者借鉴HMM的Forward-Backward算法思路,利用动态规划算法求解。

如下图,为了更形象表示问题的搜索空间,用X轴表示时间序列, Y轴表示输出序列,并把输出序列做标准化处理,输出序列中间和头尾都加上blank,用l表示最终标签,l’表示扩展后的形式,则由2|l| + 1 = 2|l’|,比如:l=apple => l’=_a_p_p_l_e_

图中并不是所有的路径都是合法路径,所有的合法路径需要遵循一些约束,如下图:

所以,依据以上约束规则,遍历所有映射为“apple”的合法路径,最终时序T=8,标签labeling=“apple”的全部路径如下图:

接下来,如何计算这些路径的概率总和?暴力遍历?分而治之?作者借鉴HMM的Forward-Backward算法思路,利用动态规划算法求解,可以将路径集合分为前向和后向两部分,如下图所示:

通过动态规划求解出前向概率之后,可以用前向概率来计算CTC Loss函数,如下图:

类似地方式,我们可以定义反向概率,并用反向概率来计算CTC Loss函数,如下图:

去掉箭头方向,把前向概率和后向概率结合起来也可以计算CTC Loss函数,这对于后面CTC Loss函数求导计算是十分重要的一步,如下图所示:

总结一下,根据前向概率计算CTC Loss函数,得到以下结论:

根据后向概率计算CTC Loss函数,得到以下结论:

根据任意时刻的前向概率和后向概率计算CTC Loss函数,得到以下结论:

至此,我们已经得到CTC Loss的有效计算方法,接下来对其进行求导

7. CTC Loss函数求导

我们先回顾下RNN的网络结构,如下图飘红部分是CTC Loss函数求导的核心部分:

CTC Loss函数相对于RNN输出层元素的求导过程如下图所示:

8. 总结

总结一下,本篇通过RNN声学模型的例子引出了问题背景,并通过实际例子一步一步的介绍如何定义和计算CTC Loss函数,最终通过反向传播算法完成对RNN模型的端到端训练过程。

至此,CTC算法的模型训练过程与原理介绍完了,下一篇将介绍CTC算法的模型预测部分,Part2链接

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)