关于CTC的一点个人理解：

CTC在训练时其实不关心对齐，这一点从ctc_loss的表达式可看出，CTC在训练时将可能映射（去重、去空）出的标签的所有路径的概率之和最大化，那么在解码时根据给定输入搜索概率最大的路径时就更可能搜索出能映射到正确结果的路径。且前缀集束搜索考虑了“多对一”的情况，进一步增加了解码出正确结果的可能性。综上CTC其实并不是学习了一种对齐，对齐可以理解为一种过程，而CTC在乎的是结果，他是一种不需要对齐而能解码得到正确结果的方法。

前缀集束搜索时，涉及的是部分概率较大正确映射的合法路径，且是非空token较早出现的路径。比如一种极端的路径。输入是一个200帧的wav，标签是“hello”，5个token，假如某一条路径前195个是“”，最后5个是“hello”。这条路径在训练时是会被概率最大化的合法路径，但是在解码时可能就不会影响解码过程，因为前缀集束搜索有从左到右的顺序，这种路径在解码时就会因为前几步概率过小而被“淘汰”。

至少CTC在训练时绝对不是对齐，但CTC在解码时，特别是前缀集束搜索解码时，参与解码的部分合法路径可能是“比较整齐的界限分明的多对一对齐”。

    关于CTC我一直有个疑问，CTC的损失会最大化所有合法路径的和，那么‘hello’，就算预测成‘h,e,l,l,o, ∈,∈,∈,∈,∈,∈,∈,∈,…’也是正确的路径，他也会被概率最大化，那么这显然不是一个直观上的好的选择，最终或许会影响解码结果。后来突然意识到，声音是连续的。拿语谱图特征举例，分帧是很短的（毫秒级），那么一个字一定对应很多帧，而一个字的发音是相近的，而预测是根据特征得出的，也即是说会倾向于预测好几个一样的连续的结果。所以其实不会出现上述的前面预测完，后面全是空格符的结果，只是理论上成立，现实中很难出现。倾向于得出的结果是‘h,h,h,h, ∈,∈,∈,∈,e,e,e,e,e,e,e, ∈,∈,l,l,…’这样的结果。CTC的边界可能不是很清晰，但解码的结果是对的。所以CTC说重结果不重过程。

以下是原博文：

Sequence Modeling With CTC——Awni Hannun （2017.11）

在语音识别中，我们的数据集是音频文件和其对应的文本，让模型更有效地收敛。不幸的是，由于人的语速的不同，或者字符间距离的不同，音频文件和文本很难再单词的单位上对齐。

传统语音识别模型中，数据的预处理操作需要人工将标签文本与语音进行严格对齐。很费时间，而且预测的结果不是整个序列的输出结果，还需人工操作。CTC是一种让网络自动学会对齐的好方法，十分适合语音识别和书写识别。

为了描述地更形象一些，我们可以把输入序列（音频）映射为X=[x1,x2,…,xT]，其相应的输出序列（转录）即为Y=[y1,y2,…,yU]。这之后，将字符与音素对齐的操作就相当于在X和Y之间建立一个准确的映射。

 给定一个X，CTC能基于所有可能是准确映射的Y给出输出分布。根据这个分布，我们可以推理最可能的输出，或计算分布内各字符的可能性概率。

CTC概览

CTC算法的输入和输出的对齐方式有下列属性： 

1、输入与输出的对齐方式是单调的，即如果输入前进到下一时间片，输出会保持不变或者也会移动到下一个时间片段 （本质上就指的是“多对一”）

2、输入与输出是多对一的关系 

3、输出的长度不能大于输入 

通过CTC损失函数训练模型：

CTC的对齐方式展示了一种利用时间步长概率推测输出概率的方法。

对应标签，其关于输入的后验概率可以表示为所有映射为的路径之和，我们的目标就是最大化关于的后验概率。CTC假设每个时间片的输出是相互独立的，则路径的后验概率是每个时间片概率的累积。

计算CTCloss前需要配合CNN或RNN给出每个时间步的经过softmax的输出字典上的分布，是输出字典（例如标签是“hello”，那么输出字典就是{h,e,l,o,}），表示时序。乘法表示一条路径的所有字符概率相乘，加法表示累加多条路径。实际还需要输入输出的序列长度，用以在计算损失时，消除padding的影响。

（路径：例如和对应的都是“”，这就是输出的其中两条路径，要将所有的路径相加才是输出的条件概率。）

Y的概率；所有可能路径概率求和；逐个计算单个路径概率  

计算p(Y|X)方法：动态规划

对于一个时间片长度为的分类任务，所有可能的路径数为，往往会很大，用来计算Loss不现实。在CTC中采用动态规划的思想来快速计算loss，动态规划算法的核心思想是如果两种路径、用相同步长映射到同一输出，那它们就能被合并。

左：总结所有路径会占用大量资源；右：动态规划算法合并了路径，计算更快

下图中，横轴的单位是的时间片，纵轴单位是插入后的序列。因为CTC允许在Y中的字符前任意加入ϵ，所以为了更直观地描述算法，例如对单词“ZOO”，我们可以在每个字符之间，还有字符串的首位插入空白占位符，此时输入被设为：

                                     

假定输入有9个时间片，标签内容是“ZOO”。根据CTC的对齐方式的三个特征， 的所有可能的合法路径如下图

CTC中单词ZOO的所有合法路径，outputY=[z、o、]  

上图分成两种情况，设为相同对齐路径合并后的CTC得分（概率） ，更准确的说，是输入时间步后子序列的得分（概率）。可以发现，如果要获得，我们可以从最后那个时间步长开始计算。只要能算出最后时间步长时的值，我们就能得到。

Case1:

1）=,则只能由前一个空格或者上一个时间步的其本身得到，

2）不等于，但是为连续字符的第二个，即,（比如“ZOO”中的第二个O），则只能由前一个空格,或其本身得到，而不能由前一个字符得到，因为这样做会将连续的两个字符合并成一个（例如连续字符中间不用隔开的话，就会合并成）表示在时刻t输出字符的概率，表示上图中坐标为(s,t)节点的概率。

           

         即=（第t-1个输入时间步后对齐路径的CTC得分和）（第t个输入时字符的概率）

Case2:

如果不为Case1中的情况，则可以由,以及得来，可以表示为：

        

从上图可以发现，合法路径有两个起始点，两个终止点。合法路径的总概率是两个最终节点（final nodes）的概率之和。

现在，我们已经可以高效的计算损失函数，下一步是工作便是计算梯度用于训练模型。由于的计算只涉及加法和乘法，因此CTC损失函数对于每个时间步长输出概率是可微的，进而我们可以使用梯度下降优化模型。

对于训练数据集，模型参数先要调整以使负对数似然值最小化，而不是直接使似然值最大化。

以上两种情形的简单图示是：

Case1：如上图所示，在这一情形下，我们不能跳过前一个token.  上文中所述1）为右边的情况，即a,ϵ  ,a；2）为左边所述情况，即ϵ,a,ϵ

Case2：在这一情形下，我们可以跳过Z中之前的token.当上一个时间步token为位于两个不同字符间的ϵ时，构成这一情形 

现在我们可以有效地计算损失函数，下一步就是计算一个梯度并训练模型。CTC损失函数对于每个时间步长输出概率是可微的，因为它只是它们的总和和乘积。鉴于此，我们可以分析计算相对于（非标准化）输出概率的损失函数的梯度，并像往常那样从那里运行反向传播。

对于训练集D，模型参数先要调整以使负对数似然值最小化：

利用训练好的模型推理：

训练好模型后，我们就需要根据给定输入计算可能的输出，也就是计算

                                             

求解大概率输出有两种方案，一种是贪心搜索（Greedy Search），一种是集束搜索（beam search）

关于两种搜索可参照：seq2seq 模型（机器翻译模型、集束搜索、贪心搜索）简记

使用贪婪搜索和一般集束搜索的问题：

1、没有考虑单个输出可能有多个对齐，可以举个例子。假设输出[a, a, ϵ]和[a, a, a]的概率比[b，b，b]低，但它们的概率之和高于后者。在这种情况下，启发式方法会给出Y=[b]这样的错误结论，因为它忽视了[a, a, ϵ]和[a, a, a]可以折叠为一个输出，而真正的答案应该是Y=[a]。  

2、一般的束搜索还有一个问题是，在保存的 top N 条路径中，因为是在解码后才进行去重等操作，可能存在多条结果最后实际上是同一结果（经过去重复、去 blank 操作）。这减少了搜索结果的多样性。 

解决方法是：前缀技术搜索（prefix beam search）

先去重，再去

变形集束搜索->前缀束搜索（Prefix Beam Search）：

如果要处理多个对齐映射到同一输出这种情况，我们可以修改原始集束搜索，即不保留束中的对齐列表，而是存储折叠重复字符并移除ϵ后的输出前缀。前缀束搜索在搜索的每一步，我们都会基于映射到给定前缀的所有对齐为该前缀累计分数（概率）。

T=3，出现[b,a,a]映射[b,a]的去重操作；T=2，出现[a,]映射[a]的去操作；T=2,时有多个对齐映射同一输出的操作，[a]、[a，]同时映射[a]

当出现重复字符时，提议扩展可以映射到两个输出，如下图T=3， 其中红'a'是前缀蓝[a]的提议扩展，对该扩展而言，[a]和[a, a]都是有效输出。因为“a,ϵ”和“a，a”合并为“a”作为前缀，如果再遇到“a”则会出现“a,ϵ , a”和“a,a,a”两种可能，而第一种不能去重合并，所以解码为“a,a”作为下一时间步的前缀，第二种情况就可以去重合并成“a”。

相应的，因为连续字母中间必须有若干，否则会被合并，所以当我们将[a]扩展为[a, a]时，我们只需统计之前以空白标记结尾的所有路径的概率（位于连续字符中间的也要统计）。同样的，如果是扩展到[a]，那我们计算的就是不以结尾的所有路径概率。

鉴于此，我们需要跟踪当前输出在搜索树中前两处输出。无论是以结尾还是不以结尾，如果我们在剪枝时为每一种假设做好得分排序，我们就能在计算中使用组合分数。 

追踪假设序列被扩展到的概率将“”区别于“”和“”

CTC的特性：

1、条件独立：模型假设，对给定输入而言，每个输出与其他输出条件独立。在许多序列排序问题中，这一假设有问题。事实上，利用CTC建立的语音识别器既不能根据输出学习语言模型，也不能学习条件依赖语言模型，它只能通过包含独立语言模型来提高准确性。

        当然，这种假设虽然会产生不小的麻烦，但也不是一无是处，它能使模型迅速适应相互对立的新场景。如果我们用和朋友的通话录音训练识别器生成语音答复信息，由于领域不同，同一模型可能会把语音内容归类为完全不同的两个领域，而CTC的模型可以弥补这一点，它能在领域转换时更换新的语言模型。

2、 单调对齐 ：CTC的另外一个约束是输入与输出之间的单调对齐，在OCR和语音识别中，这种约束是成立的。但是在一些场景中例如机器翻译，这个约束便无效了。

3、多对一映射：CTC的又一个约束是输入序列的长度大于标签数据的长度，但是对于 的长度大于的长度的场景，CTC便失效了。 

参考文章：Sequence Modeling With CTC

                  Sequence Modeling With CTC 译文