CTC:连接时序分类器

作者: HRain | 来源:发表于2019-03-21 22:12 被阅读0次

简介

CTC：Connectionist Temporal Classiﬁcation
论文：Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks
原文：Sequence Modeling With CTC

对于语音识别任务来说，数据是一段剪辑的语音，标签是语音对应的文本，我们不知道如何将语音片段与文本在单词层面上进行对齐，这样对于训练一个语音识别器就增加了难度。

为了解决这个问题，我们可以先制定一个规则，例如“文本中一个字符对应十个语言片段输入”。但是对于不同的人来说，他们说话的语速是不一样的，这样导致了上述的定义规则不可行。另一个解决办法是手动对齐每个字符在音频中的位置，这种方法对于我们训练模型非常有效，但是却非常耗时。

上面只是拿语音识别来举例，其实在其他一些识别任务中也会出现这个问题，例如手写字符识别、在视频中添加动作标记等。Connectionist Temporal Classification (CTC)正适合处理这种不知道输入输出如何对齐的情况，所以很适合语音识别和手写字符识别的任务。

为了方便描述，我们做如下定义，输入(如音频信号)用符号序列 $X=[x_{1},x_{2},...,x_{T}]$ 表示，对应的输出(如对应的标注文本)用符号序列 $Y=[y_{1},y_{2},...,y_{U}]$ 表示。为了方便训练这些数据，我们希望能够找到输入 $X$ 与输出 $Y$ 之间精确的映射关系。

在使用有监督学习算法训练模型之前，有几个难点：

$X$ 和 $Y$ 都是变长的；
$X$ 和 $Y$ 的长度比也是变化的；
$X$ 和 $Y$ 相应的元素之间没有严格的对齐(即 $x_{t}$ 与 $y_{u}$ 不一定对齐)。

使用CTC算法能克服上述问题。到这里也可以知道CTC就是用来解决输入输出对齐问题的一种算法。对于一个给定的输入序列 $X$ ，CTC给出所有可能的 $Y$ 的输出分布。根据这个分布，我们可以输出最可能的结果或者给出某个输出的概率。

还拿语音识别来说，CTC常用的场景是RNN后接CTC算法，RNN模型输入是许多音频片段，输出长度与输入的长度一样，有 T 个音频片段，就输出 T 个概率向量，每个概率向量包含字典中每个字符的概率。例如网络输入音频个数定为 T，字典中不同字符的个数为 N，那么RNN输出的维度为 TxN。根据这个概率输出分布，我们就能得到最可能的输出结果。在接下来的讨论中可以把RNN+CTC看成一个整体，当然也可以将RNN替换成其他的特征提取算法。

损失函数：对于给定的输入 X，我们训练模型希望最大化 Y 的后验概率 P(Y|X)，P(Y|X) 应该是可导的，这样我们就能利用梯度下降训练模型了。

测试阶段：当我们已经训练好一个模型后，输入 X，我们希望输出条件概率最高的 Y，即 $Y^{*}=\mathop{\arg\max}_{Y}p(Y|X)$ 而且我们希望尽量快速的得到 $Y^{*}$ 值，利用CTC我们能在不花费很多时间的情况下迅速找到一个近似的输出。

算法

CTC算法对于输入的 X 能给出每个可能的输出 Y 的条件概率(可以想象RNN输出 TxN 的概率分布矩阵，所以通过矩阵中元素的组合可以得到很多Y值作为最终输出)。在计算输出过程的一个关键问题就是CTC算法如何将输入和输出进行对齐。接下来我们先来看一下对齐方式，然后介绍如何利用对齐方式计算损失函数以及如何在测试阶段找到最合理的输出。

对齐方式

CTC算法并不要求输入输出是严格对齐的。但是为了方便训练模型，我们需要知道 X 的输出路径和最终输出结果的对应关系，因为在CTC中，多个输出路径可能对应一个输出结果。知道输入输出的对应关系才能更好的理解之后损失函数的计算方法和测试使用的计算方法。

为了更好的理解CTC的对齐方法，先举个简单的例子。假设有一段音频长度为6，我们希望的输出是 Y=[c,a,t] 这个序列，一种将输入输出进行对齐的方式如下图所示：为每个输入指定一个输出字符，然后将重复的字符删除。

上述对齐方式有两个问题：

通常这种对齐方式是不合理的。比如在语音识别任务中，有些音频片可能是无声的，这时候应该是没有字符输出的；
对于一些本应含有重复字符的输出，这种对齐方式没法得到准确的输出。例如输出对齐的结果为 [h,h,e,l,l,l,o]，通过去重操作后得到的不是“hello”而是“helo”

为了解决上述问题，CTC算法引入的一个新的占位符用于输出对齐的结果。这个占位符称为空白占位符，通常使用符号 $\epsilon$ 来表示。例如OCR中的字符间距、语音识别中的停顿均表示为这个符号。所以，CTC的对齐涉及去除重复字母和去除 ϵ 两部分。利用这个占位符，输入与输出有了非常合理的对应关系，如下图所示：

在这个映射方式中，如果在 Y 中有重复的字符，有效的对齐方式必须在两个重复的字符当中插入 ϵ 占位符，这样上面的“hello”就不会变成“helo”了。

回到上面输入 X 长度为6，输出 Y=[c,a,t] 这个例子来，下图中有几个示列说明有效的对齐方式和无效的对齐方式，在无效的对齐方式中举了三种例子：占位符插入位置不对导致的输出不对、输出长度与对齐后的长度不一致、输出缺少字符a。

CTC算法的对齐方式有下列属性：

输入与输出的对齐方式是单调的，即当输入下一个输入片段时输出会保持不变或者也会移动到下一个字符，而不会移动到上一个字符；
输入与输出是多对一的关系，一个或多个输入只能对齐到一个输出；
输出的长度小于等于输入。

损失函数

这里要明确一点，对于一个标定好的音频片段，训练该片段时，我们希望的输出就是标定的文本，如下图所示，比如音频的长度为 T，RNN或者其他模型输出的也是 T 个概率向量，每个概率向量内部存放每个字符（包括空白占位符）的概率。CTC对齐方式很自然的为我们提供了一种从每个时间步的概率得到输出序列概率的方法。比如我们输入一段长度为10的音频，对应的文本是 "hello"，那么字符字典就是 {h, e, l, o, ϵ}。现在把音频输入到RNN中，那么在每一个输入时步中，网络会计算该时刻字典中每个字符的概率分布，得到概率向量，最终会得到10个概率向量。然后根据这些概率向量，可以计算出概率最大的输出序列，然后经过处理得到最终的输出。整个过程如下图所示：

确切的说，对于一对输入输出 (X,Y) 来说，CTC的目标是将所有有效路径的概率和最大化：

$p(Y|X)=\sum_{A\in\mathcal{A}_{X,Y}} \prod^{T}_{t=1}p_{t}(a_{t}|X)$

解释一下，对于RNN+CTC模型来说，RNN每一个时步的输出就是字典中所有字符的概率分布 $p_{t}(a_{t}|X)$ ，t 表示每一个时步。RNN通常运行良好，因为它考虑了输入中的上下文联系，但是我们可以自由地使用任何学习算法，只要能满足在给定固定大小的输入切片的情况下输出所有分类的概率分布。乘法表示一条有效路径中的所有字符的概率相乘，加法表示一个标定文本会对应多条有效路径。例如 hheϵllϵloϵ 与heeϵllϵllo对应的都是“hello”，要将所有的路径相加才是某个输出的条件概率，这里最大化的是有效输出。

但是对于一个输出，路径会非常的多，对于一个时间片长度为 T 的 N 分类任务，所有可能的路径数为 T^N ，这样直接计算概率是不现实的。CTC算法采用动态规划的思想来求解输出的条件概率，如下图所示，该图想说明的是通过动态规划来进行路径的合并，如果两个路径在同一时步有相同的输出，就可以合并它们：（下面会有解释）

假设我们现在有输入音频 X 对应的标定输出 Y 为单词“ZOO”，为了方便解释下面动态规划的思想，现在每个字符之间还有字符串的首位插入空白占位符 ϵ，得到下面结果 Z={ϵ,Z,ϵ,O,ϵ,O,ϵ}。为了便于说明，先定义好下图的横纵坐标轴的含义，横轴是 X 时步单位 t，纵轴为 Z 序列单位为 s。根据CTC的对齐方式的三个特征，输入有 9个time-step，标签内容是“ZOO”， P(Y|X) 的所有可能的合法路径如下图：

α 表示不同有效路径合并后的节点的概率。 $\alpha_{s,t}$ 表示上图中坐标为 (s,t) 的节点的概率，之前的节点都已经合并了。该点的概率计算分为下面两种情况：

Case 1：

1）如果 $(s,t)=\epsilon$ ，则 $\alpha_{s,t}$ 只能由上一个时步的非空字符 $\alpha_{s-1,t-1}$ 或者上一个时步的空字符本身 $\alpha_{s,t-1}$ 得到。之所以不能从 $\alpha_{s-2,t-1}$ 的空字符得到，是因为在最终的输出中会跳过两个空字符间的非空字符，导致错误输出。
2）如果 $(s,t)$ 不等于 ϵ，但是 $(s,t)$ 为连续字符的第二个，即 $s=s-2(s-1=\epsilon)$ ，则 $\alpha_{s,t}$ 只能由一个空白符 $\alpha_{s-1,t-1}$ 或者其本身 $\alpha_{s,t-1}$ 得到，而不能由前一个字符得到，否则去重复时就给去掉了。

上述两种情况中， $\alpha_{s,t}$ 可以由下式算出，其中 $p_{t}(z_{s}|X)$ 表示在时刻 t 输出字符 $z_{s}$ 的概率。
$\alpha_{s,t}=(\alpha_{s,t-1}+\alpha_{s-1,t-1})\cdot p_{t}(z_{s}|X)$

Case 2：

如果 $(s,t)$ 不等于 ϵ，则 $\alpha_{s,t}$ 可以由 $\alpha_{s,t-1}$ , $\alpha_{s-1,t-1}$ 以及 $\alpha_{s-2,t-1}$ 得来，可以表示为：
$\alpha_{s,t}=(\alpha_{s,t-1}+\alpha_{s-1,t-1}+\alpha_{s-2,t-1})\cdot p_{t}(z_{s}|X)$

从上图可以看到合法路径由两个起始点（空字符和 'Z'），输出两个终止点（空字符和 ‘O’），最后输出的条件概率为两个终止点输出概率的和。使用这种计算方法就能高效的计算损失函数，下一步的工作表示计算梯度用于训练模型。由于P(Y|X)的计算只涉及加法和乘法，因此是可导的，可以利用SGD进行优化。对于训练集 $\mathcal{D}$ ，模型优化的目标是最小化负对数似然函数：
$\sum_{(X,Y) \in \mathcal{D}} -log(p(Y|X))$

预测

当我们训练好一个模型后，我们输入 X，我们的目的是计算下式得到输出
$Y*=\mathop{\arg\max}_{Y}p(Y|X)$

一种方法是贪心算法。

取RNN每次输出概率最大的节点，计算方式如下：
$A*=\mathop{\arg\max}_{A} \prod^{T}_{t=1}p_{t}(a_{t}|X)$

然后通过去重得到输出结果。通常这种启发式的算法很有效，但是这种方法忽略了一个输出可能对应多个对齐结果。例如 [a,a,ϵ] 和 [a,a,a] 各自的概率均小于 [b,b,b] 的概率，但是他们相加的概率比 [b,b,b] 概率高。贪心算法得到结果为 Y=[b]，但是实际上 Y=[a]更为合理。考虑到这点第二种方式变的更为合理。

第二种算法是Beam Search的一种变形。

先来说一下Beam Search算法，Beam Search是寻找全局最优值和Greedy Search在查找时间和模型精度的一个折中。一个简单的beam search在每个时间片计算所有可能假设的概率，并从中选出最高的几个作为一组。然后再从这组假设的基础上产生概率最高的几个作为一组假设，依次进行，直到达到最后一个时间片。该算法有个参数叫做宽度，假设宽度设为3，在RNN的输出中，该算法每个时间 t 输出时，不同于贪心算法只找最高的，而是找最高的三个概率作为下一次的输入，依次迭代，如下图所示，每次 t 时间都是基于 t-1 输出的最高三个查找当前概率最高的三个，字典为[a, b, ϵ]。(这里也可以看出，当宽度设置为1时就是贪心算法)

因为我们这里想要结合多个对齐方式能够映射到同一输出的这种情况，这时每次 t 时间的输出为去重后以及移除 ϵ 的结果，具体如下图所示：

当输出的前缀字符串遇上重复字符时，可以映射到两个输出，如上图所示，当T=3时，前缀包含a，遇上新的a，则[a]和[a,a]两个输出都是有效的，因为两个a之间本来有一种包含 ϵ 的情况（T=2到T=3过程中），但是被去掉了空白符号。

当我们将 [a] 扩展为[a, a]时，我们只需统计上一个时步以空白标记 ϵ 结尾的所有路径的概率（位于字符中间的 ϵ 也要统计）比如T=2时刻的 aϵ 。同样的，如果不扩展仍然是[a]，那我们计算的就是不以 ϵ 结尾的所有路径概率，如T=2时刻的 aa。所以每次的输出只需要记录空白标记 ϵ 结尾的所有路径的概率和不以 ϵ 结尾的所有路径概率来进行下一次的概率计算。

这个算法的实现，Awni Hannun给出了Python示例。

CTC的性质

条件独立：CTC最广为人知的一个缺点是其假设每个时刻的输入都是相互独立的，这是一个非常不好的假设。在OCR或者语音识别中，各个时刻输入之间是含有一些语义信息的，所以如果能够在CTC中加入语言模型的话效果应该会有提升。
单调对齐：CTC的另外一个约束是输入 X 与输出 Y 之间的单调对齐，在OCR和语音识别中，这种约束是成立的。但是在一些场景中例如机器翻译，这个约束就是不准确的。
多对一映射：CTC的又一个约束是输入序列 X 的长度大于标签数据 Y 的长度，但是对于 X 的长度小于 Y 的场景，CTC就失效了。

CTC:连接时序分类器

简介

算法

对齐方式

损失函数

Case 1：

Case 2：

预测

CTC的性质

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读