百度去年开源了第一个机器学习库——Connectionist Temporal Classification(CTC)，CTC到底是什么算法呢？


CTC是由Graves等人于2006年提出来的一种时序分类算法，重点要解决的问题是：在时序分类任务中，传统的做法是输入数据与给定标签必须要在时间上一一对齐，只有这样才能采取交叉熵按帧训练来进行分类，而CTC的做法是不需要标签在时间上一一对齐就可以进行训练，在对输入数据的任一时刻做出的预测不是很关心，而关心的是整体上输出是否与标签一致，从而减少了标签预划定的冗杂工作。


CTC与传统的framewise还有一个很重要的不同之处就是：CTC输出的是整体序列的概率，而framewise输出的是单帧的概率，而对于时序问题来说，输出序列的概率远比输出单帧的概率重要得多，因此framewise训练需要做额外的时序工作，而CTC就不需要额外的工作。因此，CTC很善于处理时序分类问题。


先直观感受一下CTC与framewise的不同之处，下图是它们在语音识别中的应用图示。在framewise训练中，每一帧的标签需要预先划分，如垂直虚线所示；在输出标签概率上，CTC中每个标签的输出概率像是有一个尖峰，而标签与标签之间是由空白标签来分隔的，空白标签的概率由灰色虚线表示。







下面以语音识别为例来具体了解一下CTC算法的原理。


语言识别中，通常包括声学模型和语言模型，而声学模型现在大多由深度神经网络构成，深度神经网络的输出为一系列标签的概率分布，例如若处理的是字符水平的语音识别，这些标签就是26个英文字母+一个blank标签，blank在CTC中的作用是分隔每个标签。


假设每一时刻输出的标签概率互不影响，那么整体输出的概率就等于各时刻输出概率的乘积。即：







通常，标签序列的长度要小于训练时帧的长度，换句话说，如果标签序列是day，训练时输出的序列可能是dd_aaa__yy_。那么怎么样建立输出序列与标签序列之间的联系从而训练整个声学模型呢？


这里CTC采取的做法是自定义一个映射函数F，F的定义如下：


将输出序列中所有相邻重复的元素归结为单个元素，如F(baac)=bac；

将输出序列中所有的blank剔除，如F(a_b_c)=abc；


有了以上两点定义以后，我们就不用担心重复标签以及blank标签对最后结果的影响了。另外，从输出标签经F转化为目标标签的可能路径肯定有很多，那么总的概率就等于所有这些路径概率之和：


其中π是指所有满足目标标签的可能路径。


那么，在CTC中为什么要引入blank标签呢？设想一下，如果没有blank标签的话，相同的字母就不能出现在同一行了，因为根据F的第一条定义，可知所有重复的字母要归结为单个字母；另一方面，网络可能要等到另外一个字母发音才开始去预测下一个单词，这是极为不方便的，因为语音识别中，很有可能会发生停顿的现象，这个时候blank就很起作用了。


那么，p(l|x)该如何去计算呢？纵然所有可能的路径有那么多，而且路径的个数是随着输入序列的长度呈指数倍数增长的，难道我们要去一一枚举然后求和吗？这样计算量显然是非常巨大的。


CTC在这里选择了一种高效的算法——动态编程，类似于隐马尔科夫模型中的前向-后向算法，关键思想就是所有路径可以分解为根据给定标签的前缀来计算。







为了允许输出标签中包含blank标签，我们将目标标签首先做一补充，例如如果一段音频的目标标签是DOG，那么我们在这个目标标签的首尾均加一个blank，另外在字母与字母之间，也加一个blank，这样得到的新的目标标签即为：_D_O_G_。也就是说，假如原始的目标标签l长度为U，那么变形后的新目标标签l'的长度为U'=2U+1。这样，我们就允许字母与blank之间的概率转移以及不同的字母之间的概率转移。


现在首先来定义一个前向变量α(t,u)，其代表的意思是在t时刻所有路径输出结果为原始目标标签l的u/2个前缀的总概率，即：







因为所有的正确路径一开始都必须以blank或者目标标签中的第一个字母开头，而若以其他字母开头就肯定不正确。因此前向变量必须具有以下初始条件：







再举一张图来回顾一下CTC中的前向变量的递归计算路径：







同理，我们还可以定义一个后向变量β(t,u)，其代表的意思是在t+1时刻追加到α(u,t)的所有路径输出结果为原始目标标签l的总概率，即：







同样，后向变量也是按照递归来计算：










 

以上只是t时刻位置恰好处于u的所有正确路径的概率和，回到一般情况，对于任何t，我们可以计算所有位置的正确路径得到总概率：






这就是时序分类中的CTC算法。
 
 
 
 
 
 
来源： 张泽旺 深度学习每日摘要
智造家 查看全部