1. 思想

序列学习任务需要从未分割的输入数据中预测序列的结果。HMM模型与CRF模型是序列标签任务中主要使用的框架，这些方法对于许多问题已经获得了较好的效果，但是它们也有缺点：
（1）需要大量任务相关的知识，例如，HMM中的状态模型，CRF中的输入特征选择；
（2）需要有独立性假设作为支撑；
（3）对于标准的HMM模型，它是生成式的，但是序列标签时判别式的。

RNN网络除了出入与输出的表达方式需要选择之外不需要任何数据的先验。它可以进行判别训练，它的内部状态为构建时间序列提供了强大的通用机制。此外，其对时间和空间噪声具有很强的鲁棒性。

但是对于RNN呢，它是不能拿来做序列预测的，这是因为RNN只能去预测一些独立标签的分类，因而就需要进行序列预分割。要解决该问题，那么将RNN与HMM结合起来被称之为hybrid approach。在该方法中使用HMM为长序列结构数据建立模型，神经网络就提供局部分类。加入HMM之后可以使得在训练中自动分割序列，并且将原本的网络分类转换到标签序列。然而，它并没有避免上诉内容中HMM使用缺点。

这篇文章提出了CTC( Connectionist Temporal Classification)，可以解决前面提到的两点局限，直接使用序列进行训练。CTC引入了一个新的损失函数，可以使得RNN网络可以直接使用未切分的序列记性训练。为了使用这个损失函数，为RNN引入其可以输出的“blank”标签。RNN的输出是所有标签的概率。

RNN可以输出“blank”的好处：
（1）RNN可以选择任意时刻给出一个标签，例如在没有信息输入的音频空白时间给“blank”标签，其它则出处对应的标签；
（2）“blank”标签可以在某一时刻对一个正确的标签给一个很高的概率，在之前我们是查看此时所有标签的概率分布。

2. Temporal Classification

这里将Temporal Classification定义为$h$h，训练数据集合$S$S中数据是成对存在的$(x, z)$(x,z)，其中$x$x是训练的时序数据，$z$z是标签数据。目标就是找到一个时序分类器$h$h使得$S$S中的$x$x被分类到$z$z。训练这个分类器，就需要一个错误度量，这里就借鉴了ED距离度量，而引入了label error rate（LER）。在这里还对其进行了归一化，从而得到了如下的形式：
$LER(h,S^{,})=\frac{1}{Z} \sum_{(x,z) \in S^{'}}ED(h(x))------(1)$LER(h,S,)=Z1​(x,z)∈S′∑​ED(h(x))−−−−−−(1)

3. 时序分类器

这一部分是最为关键的一步，将网络输出转换成为基于标签序列的条件概率，从而可以使用分类器对输入按照概率大小进行分类。

3.1 从网络输出到连续标签

在CTC网络中拥有一个softmax输出层，其输出的个数为$|L|+1$∣L∣+1，$L$L是标签元素的集合，额外的一个那当然就是“blank”标签了。这些输出定义了将所有可能的标签序列与输入序列对齐的所有可能路径的概率。任何一个标签序列的总概率可以通过对其不同排列的概率求和得到。

首先，对于一条可行的路径$p(\pi |x)$p(π∣x)被定义为，对应路径上各个时刻输出预测概率的乘积。其定义如下：

对于预测结果中的一条路径的标签，在论文中假设的是这些不同时刻网络的输出是相互独立的，而这是通过输出层与自身或网络之间不存在反馈连接来确保实现的。

在此基础上还定义了映射函数$B$B，它的职责就是去除“blank”与重复的标签。因而给定的一个标签其输出概率就可以描述为几个可行路径相加和的形式：

3.2 构建分类器

在上面的内容中已经得到了一个序列标签的输出条件概率，那么怎么才能找到输入数据最匹配的标签呢？最为直观的便是求解$argmax$argmax了

在给定输入情况下找到其最可能的标签序列，这样的过程使用HMM中的术语叫做解码。目前，还没有一种通过易理解的解码算法，但下面的两种方法在实践过程中也取得了不错的效果。

3.2.1 最佳路径解码

该方法是建立在概率最大的路径与最可能的标签时对应的，因而分类器就被描述为如下形式：

从上面的形式中就可以看出，最佳路径解码的计算式很容易的，因为最佳路径中的元素是各个时刻输出的级联。但是呢，这是不能保证找到最可能的标签的。

3.2.2 前缀解码

通过修改论文中4.2节的前向和后向算法，便可以有效计算标签前缀的连续扩展概率，见下图

前缀解码在足够时间的情况下会找到最可能的标签，但是随着输入序列长度的增强时间也会指数增加。如果输入的概率分布是尖状的，那么可以在合理的时间内找到最可能的路径。

实践中，前缀搜索在这个启发式下工作得很好，通常超过了最佳路径解码，但是在有些情况下，效果不佳。

4. 网络训练

目标函数是由极大似然原理导出的。也就是说，最小化它可以最大化目标标签的对数可能性。有了损失函数之后就可以使用依靠梯度进行优化的算法进行最优化。

4.1 CTC的网络结构

在下图中给出了CTC放置的位置，其放置在双向递归网络的后面作为序列预测的损失来源。CTC会在RNN网络中传播梯度，进而使得其学习一条好路径。

4.2 CTC前向传播算法与反向传播算法

4.2.1 前向传播

需要一种有效的方法来计算单个标签的条件概率$p(l|x)$p(l∣x)。对于这样问题，其实是对应于给定标签的所有路径的总和，通常有很多这样的路径。这里采用使用动态规划算法计算所有可能路径的概率和，其思想是，与标签对应的路径和可以分解为与标签前缀对应的路径的迭代和。
然后，可以使用递归向前和向后变量有效地计算迭代。

以下是本文设计到的一些符号定义：
$y_{k}^{t}$ykt​，时刻$t$t的输出字符$k$k
$l$l，标签序列对应的损失
$l^{'}$l′，相同的标签序列，但是在字符之间添加了“blank”标签

其中，$B$B是移除所有“blank”与重复字符的变换；$\pi \in N^T:B(\pi _{1:t}=l_{1:s}^{'}$π∈NT:B(π1:t​=l1:s′​是时刻1到t的预测矩阵中，给出经过变换$B$B之后与标签有前s个一致的所有可行路径；$y^{t^{'}}$yt′是指时刻$t^{'}$t′时RNN的输出。而且$\alpha_{t}(s)$αt​(s)可以通过$\alpha_{t-1}(s)$αt−1​(s)与$\alpha_{t-1}(s-1)$αt−1​(s−1)迭代计算出来。

图3中描述的状态转移图与上面公式的含义是相同的。为了能够在输出路径中出现“blank”标签，将标签修改成了$l^{'}$l′，也就是在标签的前后与字符之前插入空白标签，因而生成的标签长度就变成了$2|l|+1$2∣l∣+1的长度，使其可以再空白标签与非空白标签之间转换，也可以使非空白标签之间发生转换。

上面的公式1中已经给出了其计算的内容，但其计算并不具有可行性。但是可以根据图3中$\alpha_{t}(s)$αt​(s)的递归定义使用动态规划算法去解决该问题，仔细看这幅图，是不是有点像HMM的前向计算过程。

对于解决该问题使用动态规划的算法进行解决，首先来分析时刻1时候的情况：

对于后序状态的关系推导

最后就可以得到一个序列的输出概率

4.2.1 反向传播

反向传播的变量$\beta_{t}(s)$βt​(s)被定义为$t$t时刻$l_{s:|l|}$ls:∣l∣​的总概率

注意：$\beta_{t}(2)=0 \forall s \gt 2t and s \gt |l^{’}|$βt​(2)=0∀s>2tands>∣l’∣，可见与图3的左下角处未连接的圆圈。在实践中上述的计算过程通常会导致数值下溢，其中的一种解决办法就是对其进行归一化操作，对于前向传播算法这里定义了如下作

对于反向传播算法中，也是有类似的定义的

最后的最大似然误差，也是建立在此基础之上的

4.3 最大似然训练

最大似然训练的目的是同时最大化训练集中所有正确分类的对数概率。因而这里可以将损失函数定义为：

为了使用梯度进行网络训练，因而就需要对网络的输出进行微分，且训练样本是相互独立的，也就是说可以单独考虑了，因而可以将微分写为：

这里可以用前向后向算法计算上式。主要思想是：对于一个标记l，在给定s和t的情况下，前向和后向变量的内积是对应l所有可能路径的概率。表达式为：

且根据上面的公式（2）联合可以得到：

再与前面的公式（3）联合可以得到

由于网络的输出是条件独立的，我们需要考虑路径在时刻t经过标记k，得到$p(l|t)$p(l∣t)的偏导数，这是对于$y_k^t$ykt​而言的，注意到相同的标签肯能会重复几次再一个标记l中，我们定义了一个位置集合，标签k出现，记为$lab(l,k)={s:l_s^{'}=k}$lab(l,k)=s:ls′​=k,它可能是空的。然后去求微分

最后，对于softmax层的反向传播的梯度，我们需要对未归一化的输出$u_k^t$ukt​的目标函数进行推导。