CTC算法详解

发布时间：2024-06-16 18:01

1.语音识别的基本架构

2. RNN循环神经网络

3.损失函数

4. CTC Loss函数计算

5. CTC训练算法总结

6. CTC解码

6.1 CTC Prefix Search Decoding

6.2 CTC Beam Search Decoding

7 总结

1.语音识别的基本架构

假设输入的音频序列为 $X = [X_{1},X_{2},......,X_{n}]$ ，输出文本序列为 $W = W_{1}, W_{2},......,W_{n}$ 。我们的目的是训练一个模型，最大化，也就是训练集中所有样本的后验概率最大。为什么是后验呢，因为人在说话的时候是想好了文本，然后产生的。所以是因，是果。单独拿出一个样本的后验概率使用贝叶斯可以得到：

$P(W|X)=\frac{P(X|W)*P(W)}{P(X)}\propto P(X|W)*P(W)$

在进行解码的时候输入O是保持不变的，目的是找到一个W使得后验概率最大，所以我们忽略分母项。再看分子，是输出词序列的概率，用语言模型来刻画。为似然概率，用声学模型来刻画。所以语音识别问题就是：

$W^{^{*}}=argmax_{W}P(X|W)*P(W)$

对于声学模型,我们在建模的时候往往是以音素、音节、字、词等为建模单元的，比如GMM-HMM里常常会用一个三状态hmm对音素建模，分别表示音素的起始、中间、结尾。所以我们需要进一步拆分成两部分：

$W^{*}=argmax_{W}\sum_{Q}P(O|Q)P(Q|W)P(W)$

其中，O表示音频特征，一般基于MFCC、FBank等方法提取特征。Q是O对应的发音字符序列，也就是刚刚所说的建模单元。这个时候，才是真正意义的声学模型，表示在词序列条件下的音素序列的概率，这就是发音词典。

在介绍CTC之前先复习一下RNN。

2. RNN循环神经网络

RNN循环神经网络，是神经网络的一种。本质是对线性层的复用。RNN主要用于处理具有序列性质的输入数据。

RNN的好处是基于上一个隐藏层输出 $h^{t-1}$ ,能把更前面的序列也建模进去，考虑了更多的上下文信息。用代码来表示这个过程就是：

 h = 0
 for x in X:
 	h = Linear(x, h)

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

对于常规的RNN模型，我们需要对每一个输出都要有label，这样才能计算loss和梯度以实现训练。

但在ASR的场景中我们很难做到这一点。比如我们拿到了一段2s的音频，按照25ms的分帧，帧间间隔为10ms的时长来算，输入有近200个音频帧，但是说话人在这2s内只说了hello这个单词，我们很难对于给每一帧去打标签来确认这一帧是hello中的h、l、l、e、o中的哪一个字母。

于是我们就有一个需求：能不能在不需要逐帧的标签的情况下，也能通过上述的模型输出和音频label来计算一个loss，并且这个loss求解函数可导使得我们的模型可以实现端到端训练？这就是我们今天要介绍的CTC，全称是Connectionist Temporal Classification。

实际情况是这样做的：对音频按照时间窗口来提取特征，比如按照每10豪ms音频提取特征得到一个N维数组，如下图：

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

这正是CTC的不同之处，该方法直接自动对齐输出标签与输入序列，不再像DNN-HMM那样需要提前作viteribi对齐标注。CTC在输入序列 $X=[x_{1}, x_{2},......,x_{T}]$ 和输出序列 $Y=[y_{1},y_{2},......,y_{U}]$ 之间直接建立多对一的映射关系，寻求最佳匹配。

输入： $x_{1}$ $x_{2}$ $x_{3}$ $x_{4}$ $x_{5}$ $x_{6}$ $x_{7}$ $x_{8}$ $x_{9}$ $x_{10}$ $x_{11}$ $x_{12}$ $x_{13}$ $x_{14}$ $x_{15}$ $x_{16}$ $x_{17}$ $x_{18}$ $x_{19}$ $x_{20}$

$\hat{y}$ : H h e e l - l o o - - w o o o r l l d d

输出： H e l l o w o r l d

如上面所示，输出序列("Hello World")的字符个数和输入序列的长度(这里是帧数20)并不相等，无法将他们直接匹配起来，但可以看到，我们通过中间的重复字符和空白字符（“-”），可以建立与输入序列一一对应的关系。在识别之后，需要去除空白字符和连续重复字符，如“o-”变为“o”，“ee”变成“e”，最后得到精简后的输出序列。

在此基础上，定义了CTC的损失函数，并在训练过程中自动对齐并使损失函数最小化。

3.损失函数

定义为建模单元集，建模单元可以是字符，如英文字母{}，也可以是音素，如汉语普通话的声韵母。为了对静音、字母停顿、字间混淆进行建模，CTC引入额外的“空白”标签(表示为'-'),把扩展为，在识别最后需要剔除“空白”标签，如和均表示。

假设是训练数据集，每个样本由输入序列 $X=[x_{1}, x_{2},......,x_{T}]$ 和输出序列 $Y=[y_{1},y_{2},......,y_{U}]$ 组成，其中，是输入序列的长度，是输出序列的长度，的每个标注都来自于建模单元集。CTC的训练目标就是，训练一个模型，使和尽量匹配，即最大化输出概率。

我们刚刚也说到，输入一段语音，对应输出标签，比如abc。而产生abc的可能路径有很多条：

a	a	b	b	b	c
a	b	b	c	c	c
a	-	b	-	-	c
-	a	-	b	-	c
-	a	b	b	-	c

以上路径 $\hat{y}$ 均可以产生输出。所以为了计算,我们需要穷举这样所有可能的路径。我们把下对应所有路径放到一个集合 $A_{CTC}(X,Y)$ 里，于是：

$P(Y|X)=\sum_{\hat{y}\subseteq A_{ctc}(X,Y)}^{}P(\hat{y}|X)$

其中， $\hat{y}$ 表示和在CTC网络下的某条对齐路径，其长度和输入序列 $X=[x_{1}, x_{2},......,x_{T}]$ 一致，即 $\hat{y}=[\hat{y_{1}},\hat{y_{2}},......,\hat{y_{n}}]$ ，去除 $\hat{y}$ 的重复字符和空白标签后得到。

而每一条路径 $\hat{y}$ 出现的概率可以这样表示：

$P(\hat{y}|X)=\prod_{t=1}^{T}P(\hat{y_{t}}|x_{t})$

其中， $\hat{y_{t}}$ 表示 $\hat{y}$ 路径在时刻的输出标签(中的一个)， $P(\hat{y_{t}}|x_{t})$ 是其对应的输出概率。

我们先来看一个时刻t下从原始输入 $x_{t}$ 到最后输出 $\hat{y_{t}}$ 的计算过程：

假设扩展建模单元集L’的个数为K，则CTC输出层对应K个节点。如图所示，输入 $x_{t}$ 经过一个RNN，隐层输出 $h_{t}$ 经过可以得到在时刻对应每一个字符的概率。我们用 $[p_{t}^{1}, p_{t}^{2},p_{t}^{3},.......,p_{t}^{K}]$ 表示这个概率。对于在t时刻的输出 $\hat{y_{t}}$ ,根据其在建模单元集的索引选择K个节点中的一个，假如选第3个，则其值为 $p_{t}^{3}$ , 即 $P(\hat{y_{t}}|x_{t})=p_{t}^{3}$ .这个过程如下图所示：

这样，对于每一个时刻，我们都能算得其对应每个字符的输出概率 $p_{t}^{\hat{y_{t}}}$ (时刻生成 $\hat{y_{t}}$ 的概率)。将每个时刻得到的输出概率一一相乘，就可以得到 $P(\hat{y}|X)$ 。整个过程如下图所示：

总结：

输入序列 $X=[x_{1}, x_{2},......,x_{T}]$ ，分别通过得到隐层输出 $[h_{1}^{\hat{y_{1}}}, h_{2}^{\hat{y_{2}}},.....,h_{T}^{\hat{y_{T}}}]$ 。通过softmax转换得到每个时刻的输出概率 $p_{t}^{\hat{y_{t}}}$ , 再将这些概率连乘得到 $P(\hat{y}|X)$ 。于是就知道怎么计算损失函数了。定义损失函数，为训练集S所有样本的负对数概率之和：

$Loss = -\sum_{(X,Y)\subseteq S}^{}lnP(Y|X) =-\sum_{(X,Y)\subseteq S}^{}ln\sum_{\hat{y}}^{}P(\hat{y}|X) =-\sum_{(X,Y)\subseteq S}^{}ln\sum_{\hat{y}}^{}\prod_{t=1}^{T}P(\hat{y_{t}}|x_{t})$

举个例子：

下面这个10维的 $X=[x_{1}, x_{2},.....,x_{10}]$ 送入。建模字符集是，对于每个时刻，经过再通过转换得到对应每个字符的概率。

比如下面这样(数值我随便取的)：

第1时刻，生成的概率是 ,

第2时刻，生成的概率是

第3时刻，生成的概率是

第4时刻，生成的概率是

第5时刻，生成的概率是

第6时刻，生成的概率是

第7时刻，生成的概率是

第8时刻，生成的概率是

第9时刻，生成的概率是

第10时刻，生成的概率是

现在，如果我们的输出标签是hello，那么我们就得找到所有会产生hello的可能路径，算出这些所有可能路径 $\hat{y_{t}}$ 的概率后一一相加，就可以计算损失函数。其中一条可能路径是he-ll-lloo，那么这条路径的生成概率就是0.3*0.1*0.2*0.1*0.3*0.2*0.3*0.1*0.3*0.1。

训练优化的目标就是使最小化，但计算的复杂度太高了，像上面那样，我们得把所有可能路径都穷举出来，然后把生成概率相加才行。为了简化这个过程, 借鉴HMM的forward-backward算法思路，利用动态规划算法来求解。

4. CTC Loss函数计算

如下图，为了更形象表示问题的搜索空间，用X轴表示时间序列， Y轴表示输出序列，并把输出序列做标准化处理，输出序列中间和头尾都加上blank。原来的字符集 $[y_{1},y_{2},......,y_{n}]$ 经过补充后，变为 $[-,y_{1},-,y_{2},.......,y_{n},-]$ 。用表示最终标签，表示扩展后的形式，则有2|| + 1 = 2||，比如：=apple => =_a_p_p_l_e_

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

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

那么如何来计算这些路径的概率总和呢？可以将路径集合分为前向和后向两个部分，如下图所示：

定义在时刻经过节点s的全部前缀子路径的概率总和为 $\alpha _{t}(s)$ :

$\alpha _{t}(s)=P(x_{1},x_{2},...,x_{t},s)$

这个前向概率即下面这个图表示的意思。

前向算法按输入序列的时间顺序，从前往后递推获得最终输出概率。

第一步，初始化：

$\alpha _{1}(1)=P(y_{-}^{1}|x_{1})$ 表示第一时刻从字符序列(Y轴)的第一个字符：空字符 '-' 出发。

$\alpha _{1}(2)=P(y_{seq(2)}^{1}|x_{1})$ 表示第一时刻从字符序列(Y轴)的第二个字符出发

$\alpha _{1}(s) = 0 , \forall s>2$ 表示第一时刻从Y轴第三个字符及以后出发的概率为0

其中，s表示y轴第几个符号的索引。 $y_{seq(s)}^{t}$ 表示t时刻第s个字符的概率。

也就是说，一开始只能从空字符或第一个有效字符开始转移。

第二步：递推

这要分三种情况：

1. t时刻转移第s个符号为空符号，我们想一下，一共有这俩种可能：从t-1时刻的同一个空符号转移过来，或是从t-1时刻的上一个有效字符转移过来。而不会从其他地方过来。如下面这个图画的那样，黄色位置只能从两个蓝色位置转移过来。

2. t时刻转移到第s个符号，且第s个字符和s-2个字符是相同的。这个时候，也只有俩种可能：从上一时刻的同一字符转移过来，或是从上一时刻的前一个空字符转移过来。注意，他不会从上一时刻第s-2个字符转移过来，这是为了避免与解码重复字符混淆。

我们来看这样一条有效路径：。经过简化，可以得到apple。

第t=4时刻，是处在字符处的，t=5时刻，是转移到了-空字符。

如果在第t=5时刻，我们还转移到字符处，如下图黑色线所示，这时对应序列为, 简化后得到aple。所以说，为避免与解码重复字符混淆(最终会合并成一个，即)，其实际路径表示为, 即中间加空白字符，则不能跳转。

3.既不属于情况1，也不属于情况2：

这是一般情况：从t-1刻的同一字符、空字符、上一有效字符均可能转移过来。

总结前向算法计算概率：

这样，一直往前转移，直到最后一个时刻。在最后一刻，可能会在最后一个有效字符结束，也可能会在最后一个空字符结束(因为只有这俩种情况才能把所有有效字符遍历，才会映射到标签上)。

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

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

前向后向算法总结：

损失函数计算及求导过程：

5. CTC训练算法总结

1. 通过前向和后向算法分别计算 $\alpha _{t}(s)$ 和 $\beta _{t}(s)$

2.求导：通过 $\alpha _{t}(s)$ 和 $\beta _{t}(s)$ 计算导数 $\frac{\partial \alpha _{t}(s)}{\partial h_{t}^{k}}$

3.通过反向传播每层参数进行逐层优化

4.重复步骤2、3，直到CTC损失代价收敛，即可完成端到端训练。

6. CTC解码

ctc解码是基于已经训练好的ctc模型，对输入序列进行解码，得到识别结果。给定输入序列，CTC的解码目标是找到概率最大的输出序列 $Y^{*}$ ，即：

$Y^{*}=argmax_{Y}{P(Y|X)}$

一种启发式方法是在每个时刻t计算概率最高的输出单元，然后删除重复和空白字符得到输出序列 $Y^{*}$ 。但是这样得到的最高概率只是来自单挑路径的最高概率， $Y^{*}$ 并不代表就是最后的输出序列 $Y^{*}$ 。这是因为，该输出序列可能由多条路径组成。虽然这每一条路径都比最大概率的路径小，但他们加起来就比最大概率大。

如下图所示，解码单元为，输入序列的长度为3，栅格中的输出为t时刻对应解码单元的输出概率。