翻译文章，原文地址:https://distill.pub.
本文不接受任何形式未经许可的转载和传播。仅供个人学习。
翻译作者: 简书ID:跑得比谁都慢
PS:懒得去适配简书的数学公式语法。需要pdf的同学可以评论要我看到的话发给你，之所以不附pdf下载链接主要还是不想传播的太容易。。。然后，建立英文还好的同学直接看原文，我翻译的太差了还是。
在语音识别场景中，我们拥有一段语音数据和对应的标注数据。不幸的是，我们不知道标注结果里的字符是如何对应到语音中的。这使得训练一个语音识别模型比我们想的要难一些。
没有这个对准关系，简单的方法就都不再适用。我们当然可以设计一条规则比如"每一个字符对应于十个输入"，但是人们讲话的频率是不同的，这样一条规则总会有失败的时候。另一个可选的方法是手动将每一个字符对准到语音里的位置上。从模型的角度来看这非常棒，我们有了每一个输入时间步的正确输出。然后，对于任何一个有意义的数据量的数据集来说，标注工作的困难都会使人望而却步。
这个问题不仅仅出现在语音识别上。我们经常碰到这类问题其实。比如从图片里识别手写字符串，一张图片里的笔画序列等等。还有一个例子是一段视频的行为标注。
Free-Converter.com-handwriting_recognition-63274901.png
Free-Converter.com-speech_recognition-58354900.png
CTC是一种能够解决这种不知道输入与输出对准关系情况的方法。我们很快就会看到，这种方法很好的契合了像语音识别或者手写字符识别这样的应用场景。
我们将输入的一段语音输入序列定义成$X=[x_1,x_2,…,x_T]$,对于该语音对应的标注输出是$Y=[y_1,y_2,...y_U]$.我们想要找到一个准确的从$X$到$Y$的映射(也就是给定$X$能够得到对应的$Y$).
不过这对于只会使用简单的监督学习算法的我们来说有些困难，特别是:
- $X$和$Y$的长度是不一样的。
- $X$和$Y$的长度比率是不一样的。
- 我们并没有一个准确的$X$和$Y$的对准方案。
CTC算法克服了这些挑战。对应于一个给定的$X$，X中给出了所有的可能的Y的分布。我们可以使用这个分布或者去前向推断最有可能的输出或者去给出对应的某个输出的概率值。
并非所有的计算loss和前向推断的方法都是容易做到的。那么我们需要CTC能够在这两个问题上都极具效率的完成。
Loss Function:对于一个给定的输入，我们需要去训练模型以最大化它对应到正确答案的概率。为了做到这一点，我们需要有效率的去计算条件概率$p(Y|X)$。并且该条件概率需要是可导的，只有这样才能使用梯度下降去优化模型。
Inference:很自然的，当我们训练好模型之后，我们希望使用它来从$X$中得到$Y$，这意味着我们需要求解$Y^* = argmax p(Y|X)$,理想的$Y^*$不太可能有效率的找到，使用CTC我们将会使用节省复杂度并且能够得到大概不错的结果的一些方法。
The Algorithm
CTC算法可以得到针对给定的X得到任何一个Y蛋概率值。计算这个概率的关键在于CTC是如何考虑输入和输出之间的对准拓扑的。下面我们将一步步从观察这些对准拓扑然后给出如何使用一些算法使得能够有效的计算出Loss和前向计算。
Alignment
实际上CTC算法是不需要对准的，它不需要输入和输出之间有对准拓扑关系。然而，为了针对输入X给出输出Y蛋概率，CTC是通过计算所有可能的对准拓扑的概率值的和来得出的。那么为了理解最后Loss Function是如何计算出来的我们必须要首先理解这个对准是什么意思。
首先考虑一个naive的方法。举例来说，假设输入的长度是6并且$Y=[c,a,t]$.一种从X和Y的对准妇女告诉是将输出的每一个字符都对应到输入上，并且去重。
Free-Converter.com-naive_alignment-25794902.png
这种方法有两个问题:
- 有些情况下输入的某些步就是没有任何意义的，强行将每一个步都对应到输出上是不合适的。例如在语音识别上，经常会有某些时间步是安静的不对应任何输出的。
- 这种对准方法的话我们就没有办法得到包含相邻两个字符是相同的这样的输出了。比如说对准方法得到的输入对应是[h,h,e,l,l,l,o],那么对应的前向输出就是‘helo’而非正确的‘hello’。
为了解决这些问题，CTC引入了一个空白符号Blank到输入序列李。我们用$\epsilon$或者$B$来表示。显然，$\epsilon$并不代表任何有意义的输出在最后的输出里是要被删除的。
CTC允许的或者说正确的对准是指这样的对准:在去除重复和$\epsilon$后，得到的结果是正确的Y.
Free-Converter.com-ctc_alignment_steps-55494901.png
如果Y里面有两个相邻的相同字符，那么正确的对准方案里两者之间必须有一个$\epsilon$.通过这样的规则，我们就可以得到'hello'这样的结果了。
让我们回到输入长度是6输出是$[c,a,t]$这个例子上，下面是一些正确的对准和错误的对准的例子。
Free-Converter.com-valid_invalid_alignments-4034902.png
多说一句，以上所说的对准其实指的是，输入当前时间步上输出哪个字符这样的一个关系。因为X其实是一个概率矩阵，每个时间步上都会给出当前时间步给出各个字符的概率，我们选择将当前时间步对准到哪个字符，那么对应的概率值也就确定了。那么我们希望的自然是，所有可能的对准方案里，能够得到正确Y的概率最大。
CTC允许的对准有一些特点。首先，关于X和Y蛋对准是单调的。如果我们走到下一个时间步上，我们可以停留在当前输出位置或者走到下一步上。第二个特性是X和Y蛋对应关系是多对一这样的关系。一个或多个输入可能对应都输出的某一步上，反之不亦然。第三点是Y蛋长度不能够比X长，这个需要我们设计结构的时候就做到，否则CTC是解决不了Y比X长这样的问题的，举例来说，这相当于你需要从一个时间帧得到两个输出结果，CTC做不到。不过一般我们涉及的问题都是符合这个要求的，比如像素之于字符，声音帧之于语言。
Loss Function
CTC对准方法给了我们一个很自然的从输入概率分布得到输出序列的方法。
屏幕快照 2017-12-30 下午3.54.26.png
使用CTC训练的模型一般都是循环神经网络来给出每个时间步是哪个的概率分布，$p_t(a_t|X)$.RNN因为输出考虑了上下文所以一般表现不错，但是RNN对于CTC来说并非必须，我们可以使用任何一种学习算法，只要它能够针对输入的长度给出在每个时间步上的概率分布。
如果我们不再深究，CTC-Loss的计算可谓是极耗算力。我们可以直接计算所有可能的对准方式，并选择其中正确的对准方式从而得到给定X对准到Y的概率值。不过问题在于这样的对准关系极多，计算起来耗时很大。举例来说长度是128，每一个时间步可能的字符种类是100，那么久需要12800个计算，包括判断是否正确，以及概率值的连乘，这仅是1个样本所需要计算的次数。
幸运的是，可以用动态规划来解决这个问题从而将复杂度降低到仅和输入输出长度乘积相关。输入假设还是128，输出是10，那么只需要1280次计算。(其实还是挺耗时的…).
能够使用动态规划的原因是:假设两个对准方案得到的输出是一样的，那么我们可以merge它们。
因为我们已经对Y中增加了$\epsilon$,那么我们不妨换一个表示字母来表示输出。
$Z=[\epsilon,y_1,\epsilon,y_2,,,,\epsilon,y_U,\epsilon]$
那么使用dp[s,t]来表示要求解的内容，其中s指的是当前到达了输出的第s步，t表示到达了输入的第t步。也就是说dp[s,t]表示的是当前输入的X[1:t]能够正确对准到Z[1:s]上的概率值,并且结尾这俩字符是对准的。那么，显然我们需要求解的内容是dp[S,T],也就是最后一步(二维数组的右下角)。
为了简洁，我们不再考虑数组推断里的一些边界情况。也就是s=0和t=0的那些情况，其实可以说下，t=0时，对应的s最大为1(原因?根据这个原因可以进一步减少运算量，也就是，有些二维数组里有些值我们也不需要全部计算出来)，可以直接得到结果。s=0时，dp[s,t]=dp[s,t-1]*P[B,t].
那么，dp[s,t]的递推公式是?
分情况，当s=0时已经说过了，当s为其他偶数时，说明Z[s]是B,那么Z[s-1]必然是一个字符。我们需要保证的是，之前真的有一个输入时间步对应到了Z[s-1]，那么久两种，一种是前一个时间步就走到了Z[s-1],另一种是前一个时间步就走到了当前。那么公式就是:
$dp[s,t]=(dp[s,t-1]+dp[s-1,t-1])*P[Z[s]|X_t]$
还有一种情况也是类似，就是当前s位置和s-2位置是同一个字符，那么我们需要保证的也是前一个位置也就是s-1有对应的输入时间步了。公式和上面一样。
其余情况就不需要考虑上一个字符是否被对准到了，那么如何另外加一项，表示上一个字符被跳过了。也就是$dp[s-2,t-1]$,最后公式为:
$dp[s,t]=(dp[s,t-1]+dp[s-1,t-1]+dp[s-2,t-1])*P[Z[s]||X_t]$
如此，就可以实现整个计算。并且还可以更加简化，我们考虑这样一个问题，第一层遍历输入时间步长T变量，第二层遍历输出步长L变量。给定t，l需要从0遍历到L-1吗？自然是不需要，我们定义S为L遍历开头，E为L遍历结尾，假设t刚开始还小，那么t的长度的输入最大对应的输出长度是小于L的，也就是说E要小于。假设t已经很大，还剩下T-t个数个输入，他们最多对应那么多个输出，也就是说S不能太小，否则T-t个输出不够对应剩下的那些输出，也就是说S要大于0.
具体的S,E的值计算是这样的:
$S = max(0,L-2*(T-t))$
$E = min(2*t+2,L)$
不再验证这两个式子正确性。
如此，就可以计算出dp[s,t]的值了(其实是dp[s,t]+dp[s-1][t],因为最后一个字符其实是不必要非对应到B上的)。
Free-Converter.com-ctc_cost-17624901.png.png
计算概率值就相当于得出了loss，不够对于模型训练来说，我们还需要梯度值。CTC计算的过程只涉及到加法乘法，是可导的。
那么优化的损失函数可以写作:
屏幕快照 2017-12-29 下午5.29.00.png
Inference
前面说完了CTC算法的loss计算方法，那么这里当我们训练完成模型之后，我们希望能够根据X得到Y.具体来说，我们需要解决:
$Y^* = argmax p(Y|X)$
一个启发式的解决方法是，在每一个时间步我们均取当前概率值最大的输出，而后对结果进行去重去空白符。这种贪心的思路效果很好，并且速度很快。
$A^* = argmax \prod_{t=1}^Tp_T(a_t|X)$
然而贪心法让我们很不安，我们不太看好它尽管它表现很不错。因为贪心法毕竟没有考虑到对准关系这个因素而只是简单在每一步给出答案。
假设输入对准到的结果$[a,a,\epsilon]$和$[a,a,a]$,单调计算两个结果的概率都低于$[b,b,b]$,那么最后会给出结果b，不过假如说前两个加起来的概率大于后者的，那么正确的答案应该是a而不是b。针对这个问题，我们需要一种算法，能够考虑到前两者对应的是同一个结果从而也能够知道a的概率大于b。
算法称为beam-search.简单版本的beam-search的基本思想是:在输入的每一个时间步上，均保留当前看起来topn个最可能序列(这一步考虑到了去重操作，但不会将B去掉，并且对于从不同路径计算出来的相同序列的概率会进行求和)，而后到下一步计算。只保留topn保证了计算复杂度低。
Free-Converter.com-beam_search-75614900.png
但上面这个方法比贪心法好些但其实依然没有解决之前提的例子，因为在它看来，$[a,a,a]$和$[a,a,\epsilon]$是两个不同的序列，它们的概率值是不会相加的。
那么我们进行修改，也就是在每个时间步上，在原先去重的基础上，也做去$\epsilon$的操作。不过需要注意的是，如果下一个字符恰好和当前末尾字符一样，那么还是得按照两条路线去做，一个是包含$\epsilon$的，一个是不包含的。也就是在去除$\epsilon$时，需要同时存储下两个概率值，一个是以$\epsilon$结尾，一个是不以$\epsilon$结尾的。当下一个字符和当前结尾不一样时，按照两者的和往下走，如果一样，则需要分出两个分支往下走。也就是说，在整个算法里前缀序列都不会显示的出现$\epsilon$这个符号了，而是针对结尾是否有$\epsilon$存两个概率值。
Properties of CTC
条件独立。
CTC假设每一个时间步的输出和其他步的输出都无关。这个是CTC的优点也是缺点。缺点显而易见，对于一些存在前后关系的场景，这种独立性不太合适。优点也同样，有些场景就是前后独立的。
举例来说，假设我们通过一堆金融行业的对话语音实现了语音识别模型，那么如果是前后相关的模型，那么可能迁移到其他场景下比如教育行业的语音就可能效果不佳，因为二者虽然说的都是话，但风格可能不同，比如金融里常见的组合是“经济效益”，而教育行业则更可能是"经济学"，基于前后上下文的模型可能因为见多了“经济效益”从而识别出“经济”后强行给出“效益”，而通过CTC训练出来的模型由于并不关注每个输出的前后关系而是独立的输出则迁移性更加好。
网友评论