背景

手写体识别、语音识别中，输入数据和输出的识别结果长度不一致、而且可变。直接用神经网络训练需要预分割、调整，得到对应关系，这很难做到。CTC提供了一种建模方式解决了这个问题^[1]。

CTC算法

调整(Alignment)

CTC不需要调整输入和输出，模型可以自动调整。引入空字符一方面一段语音中确实是有“空”的部分，强迫这部分去从音素表中选一个元素是不合理的，另一方面这可以实现时间规整，使得输入输出可以对应起来，更重要的是提供了两个相同音素的分割。如下面的例子，如果没有，“hello”会被认为成“helo”。

这种自动调整来自于CTC的“多对一(many-to-one)”映射特性。

误差函数(Loss Function)

输入语音信号，输出识别的词句序列，

如果训练模型是RNN，则RNN的每一小段时间的输出为概率。这里的隐含着条件独立的假设，可以大大简化模型。

动态规划算法

对所有可能的集合求边缘概率，这是CTC模型可以自动调整的原因。其组合随着序列长度增加指数增加，但可以用动态规划的方法高效求解一一因为可以合并经过共同节点的组合分支。

Summing over all alignments can be very expensive.	Dynamic programming merges alignments, so it’s much faster.

写出概率传播的递推公式，即可用动态规划的方法求损失函数。

前向-后向算法

也可以采用HMM的前向-后向算法^[2]。如下图的两个序列，，两个路径都经过这个点，表示在时的音是，概率记做。点把路径，分成两部分，，，，于是产生了条路径。

path	P

可以看出每一条路径可以分为和与这个点的概率无关的正向路径之和一一前置项和后向路径之和一一后置项，边缘概率即条路径相加

前置项和后置项都与递推公式，可以非常高效地计算出边缘概率。给定训练集，通常用最小化负的对数似然代替最大化似然。

推断(Inference)

推断(Inference)或称为解码(Decoding)，指利用训练后的网络进行语音识别。

常用的算法有“最优路径搜索”，“束搜索”，“前缀搜索”，参考^[3][4]，有很详细的介绍和代码。

附录

条件独立假设

前面提到了CTC的条件独立假设，理论上这会造成性能损失，可以后续用语言模型LM增加先验信息来修正。论文^[5][6]提出考虑到历史输出到RNN，如下图所示。

A schematic representation of CTC and RNNT.

^[7]明确指出，这种条件独立是作用于语言模型（language model）的，声学模型（acoustic model）里每个音素的判别还是和前后输入序列有关（这种相关性通过RNN网络来自动建立）。语言模型可以通过在外面追加先验概率来获得相关性，例如直接用语言模型进行shallow fusion/deep fusion^[8]/cold fusion^[9]/language model distill^[10]。其优点缺点^[11][1]里面有详细的分析。

通常认为CTC是一种hard alignment（RNN-Transducer同）^[11]。文章^[7]指出，这只是计算概率的一种方法，一个概念性的中间步骤，实际效果是是soft alignment。把beam search输出的个序列里面每个位置用概率表示，可以看作是soft label。

算法说明

前面介绍了动态规划算法，前向-后向算法，还提到了最优路径搜索算法，束搜索算法，前缀搜索算法。这里再区分一下。

先回顾HMM模型的三大任务^[12]。

第一个任务scoring用来计算某个数据属于模型的概率；第二个matching用来预测后续状态；第三个任务training用来估计模型参数。

在CTC的training过程中，用动态规划/前向-后向算法来计算marginal。在decoding过程中，用最优路径搜索/束搜索/前缀搜索来解码。前者对应HMM的scoring，后者对于matching。前者求边沿概率marginal，后者求最大概率MAP。

Reference

1. Sequence Modeling With CTC ↩ ↩

2. 白话CTC(connectionist temporal classification)算法讲解 ↩

3. CTC的Decode算法-Prefix Beam Search ↩

4. 连接时序分类 ↩

5. Sequence Transduction with Recurrent Neural Networks ↩

6. Streaming End-to-end Speech Recognition for Mobile Devices ↩

7. An overview of end-to-end automatic speech recognition ↩ ↩

8. On Using Monolingual Corpora in Neural Machine Translation ↩

9. Cold fusion: Training Seq2seq models together with language models ↩

10. Learn spelling from teachers: Transferring knowledge from language models to sequence-to-sequence speech recognition ↩

11. A COMPARISON OF TECHNIQUES FOR LANGUAGE MODEL INTEGRATION IN ENCODER-DECODER SPEECH RECOGNITION ↩ ↩

12. 漫谈 HMM：Definition ↩