感想

CTC的想法很难懂，尤其是对前向后向算法不熟的人，然后再网上发现了一篇很好的教程，我把它翻译了下来，里面有大量的例子，专注于原理的讲解，非常透彻，不像CTC的原论文，那样全面冗长，希望也能帮助大家理解。我在五六月份找过其它中文资料，发现原理详解的很少，我特地弥补一下中文这一块的空缺。

 

介绍

Connectionist Temporal Classification (CTC)是一项技术，它是为RNN专门设计的顶层（top layer）。使得针对输入序列的每一帧，网络能够输出一个标签或者空白（blank）。CTC使得用一个RNN构建语音识别系统成为可能，这个和混合方法HMM+DNN不一样。

 

语音识别问题

输入是一个声音片段x,然后分割成很多个帧：

X={x1,…,xT}

每一帧在时刻t,用xt表示，xt由G个声谱的权重组成：

Xt=[xt1,…,xt,G]T

我们可以设计一个RNN对每一帧xt的输出yt:：

Y={y1,…,yT}

Yt是一个字母表的概率分布：

Yt=[yt,1…yt,K]T

其中yt,k和lt代表在时刻t发音字母。

那么，问题来了，我们怎样把y解释成一串字母。

首先，很直接，我们要找一个路径

Π={π1…πT}

其中πt属于[1,K]

 

 

设想一个人说了一个“a”,在说之前，之后有一个安静的部分（silence），路径π可以是：

aaaaaaaa

aaaaa___

____aaaa

__aaaaa_

但这个没考虑到安静期和发音的变化，下面这个例子所有对应 “a”的路径：

aa______

aaa_____

_aaa____

___aaaa_

_aaaaaaa

 

上面的例子告诉我们，网络的输出既不是y也不是π。而是一些叫做标签的序列，用l表示：

L={l1,…,lS}

其中S<=T

对于上面的例子，所有那些路径都是对应样本标签：l={a}.

 

所有下面的样例对应l={h,e}:

hhheeee

__heeee

_hee___

hh__eee

_hh_eee

h__ee__

__h_ee_

注意空白（blanks）可以出现在he之前，之间，之后。

 

更复杂一点的例子是l={b,e,e}:

bbbeee_ee

_bb_ee__e

__bbbe_e_

但下面的例子对应l={b,e}

_b_eeeeee

bbb__eeee

_bb_eee__

这两个例子显示了空白在分开连续重复字母的重要性。

 

综上，语音识别的输出并不是字母表的分布y或者路径π，而是标签l.CTC 是从y结合π来推出l的方法。

动态时间规整（Dynamic Time Warping）

Y的长度可能和l的长度不一样，因此从y推理（inference）l实际上是动态时间规整问题。动态时间规整算法使得我们可以用（x,l）对进行训练，而不是(x,y)对，这是非常有价值的，因为我们在训练前不需要预先分割y,并且把x和y对齐。

时间规整的意思是我们想要把yt映射到某个ls.由上述的例子我们其实是想要把yt   映射到要么是ls,要么是一个空白。因为要是我们这样做了，我们就有机会识别后继字母，比如coffee中“ff”，bee中的”ee“。

 

假设我们有一个“bee”的语音片段，最可能的路径π是：

___bbeeee____

我们想要把它规整到l={b,e,e},好像我们可以建立下面的映射：

但是事实是我们没有太多信息去组织算法把所有的e映射到l中的第一个e：

 

另一个问题是我们应该把这些空白(blanks)映射到π中的哪一个。

一个解决办法就是我们把π映射到l’,我们在l之前，中间，后面都插入blank就构成了l’,对于上面的例子，我们就可以得到：

L’={,b,,e,,e,}

就有了下面的规整：

 

但有时π中的第一个字符不是空白，所以我们可以把第一帧对应到‘b’,而不是对应l’中的空白:

一个相似的情况是π中没有对齐的空白，因此没有帧可以对齐l’中的空白。所以这两种情况都需要我们设计一个算法计算π和l’的映射。

 

前向后向算法

这里我们推导用于计算P(l^{'}|x)，很显然他和P(l|x)等价，因为l^{'}在给定l的情况下构造是唯一的

1.前向算法

上面的规整的例子说明\pi _{T}可以映射到要么\iota ^{'}_{|l^{'}|},即\iota^{'}的空白，要么\iota ^{'}_{|l^{'}-1|},根据\iota^{'}的构造法则，即l的最后一个元素。


 

可以写成下面的形式：

 

 

在上面例子中，π1可以映射到要么是\iota ^{'}_{1},即的第一个空白；要么是\iota ^{'}_{2}，l 的第一个元素。因此：

 

 

假设我们有l’={_,h,_,e,_}和一串序列y，因此有以下两种情况：

 

紧接着我们用一个更通用的方法去映射\pi _{s}.大体上，我们可以这样映射一个\pi _{t}到：

1.   \pi_{t-1} π_{t-1},用\iota ^{'}_{s(t-1)}表示

2.    紧挨着\iota ^{'}_{s(t-1)}的元素，用\iota ^{'}_{s(t-1)+1}表示，或者

3.    \iota ^{'}_{s(t-1)+2},如果\iota ^{'}_{s(t-1)}="_"

第三个情况是我们想跳过空白，即\iota ^{'}_{s(t-1)}="_".

 

一个例子：我们想要把π={h,h,h,h,e,e,e}映射到l’={_,h,_,e,_}

 

但是，当\iota ^{'}_{s(t-1)+2}=\iota ^{'}_{s(t-1)}的时候，上述第3种情况是不合理的。在这种情况下，我们不应该跳过空白。例如，当识别单词bee的时候，l’={_,b ,_,e ,_,e ,_},在这种情况下，当我们跳过两个e之间的空格,我们就会把两个e错误地当成了一个e.在下面这个样例中，即使我们把这帧（y5）听起来更像一个e而不是空白，我们还是想要把它映射成空白，即\iota ^{'}_{5}="_"，因此我们识别出了bee这个单词。

综上，我们可得：

2.后向算法

和前向变量α（t ,s）相似，我们定义后向变量β(t ,s)

 

由于时间规整把πT映射到要么是\iota ^{'}_{|l^{'}}|},,即用1的概率对齐空白，要么\iota ^{'}_{|l^{'}-1|},即l集合中最后一个元素，概率为1，即：

 

和前向算法的泛华规则相似，我们有：

 

 

搜索空间

计算α(t ,s)的时候，我们需要α(t-1 ,s)，α(t-1 ,s-1)，α(t-1 ,s-2)。为了计算β(t,s),我们需要β(t+1,s)，β(t+1,s+1)，β(t+1,s+2)。其中的一些值为0，如图：

每个圈代表搜索空间的一个可能状态，这些状态以t和s的各自对齐，箭头连接一个状态和另一个状态，当我们计算α(t ,s)的时候，我们不需要进入不可能的区域，即右上角的的连接状态。

 

当我们计算β(t ,s)的时候，我们不可能进入左下角的状态：

为了约束动态规划算法（dynamic programming algorithm），我们需要下列条件：

 

 

参考文献

[1]. Connectionist Temporal Classification:A Tutorial with Gritty Details.

https://cxwangyi.wordpress.com/2015/10/07/connectionist-temporal-classification-the-gritty-details/