CTC算法

  在语音识别或文字识别任务上，输入的语音或图像与输出的文字很难构建精准的映射关系。形式化的描述如下：

  CTC算法旨在解决输入与输出对应对齐的问题。

1、CTC对齐方法

直接去重
  输入一段语音或图像，RNN输出预测每个位置的预测单词的概率分布，例如输出ccaaat，可直接去重，得到cat。该方法简单，但容易将本来有的重复字母也去重了，例如helllooo去重为helo。

引入空位符
  为了解决上述问题，CTC算法引入的一个新的占位符用于输出对齐的结果。这个占位符称为空白占位符，通常使用符号“$ϵ$”（或“-”），这个符号在对齐结果中输出，但是在最后的去重操作会将所有的ϵ删除得到最终的输出。利用这个占位符，可以将输入与输出有了非常合理的对应关系。
  下面给出两个例子：

  本质上就是将空位符之间的字符串先去重，再去掉所有占位符，最后合并得到结果。

2、损失函数

• 如上图可知，得到正确的识别结果“state”有非常多的合理的序列。每一个序列都认为是想要的结果，因此我们希望将所有预测出能够转换为正确答案的序列的概率进行加和；
• CTC基于一个假设，每个时间步之间是相互独立的，因此对于某一个预测序列，其概率表示为各个时间步预测结果的累乘，例如：
  
  最后对所有的路径进行求和，即可得到groud truth的预测概率（目标函数）
• 如果想要计算出所有路径，复杂度为指数级的（T个时间步，n个类别，所有路径共有n^T个）。因此采用动态规划思想（类似于隐马尔可夫模型中的前后向算法）

2.1 训练阶段

  训练时，需要获得groud truth对应的模型预测的概率，并以此作为目标函数。由于groud truth对应有许多个预测序列（例如上图中给出了4种预测序列都能够得到正确的“state”结果），因此需要对所有可能的路径对应的概率进行求和。

  假设groud truth为“state”（记作 $l$ ），则在每个字符之间插入一个占位符（“-”），形成 $l^{\prime }$：

  假设RNN一共有12个时间步，则可以得到所有的可以转换为“state”的合法路径，这里的每一条路径记作 $\pi$：

• 前向算法：计算前t时刻，且在第t时刻字符为k时所有路径的概率之和，可得到动态规划的递推式：
  
• 后向算法：计算t-T时刻，且在第t时刻字符为k时，所有路径的概率之和，可得到动态规划的递推式：

  因此所有满足条件的路径的概率之和表达为：

  在对第t时刻预测为字符k的概率进行求导：

2.2 预测阶段

• 可以在每个时刻挑选概率最大的作为预测序列；
• 也可以采用beam search

3、CTC的几个性质

• 条件独立性：CTC做了一个假设就是不同时间步的输出之间是独立的。这个假设对于很多序列问题来说并不成立，输出序列之间往往存在联系。
• 单调对齐：CTC只允许单调对齐，在语音识别中可能是有效的，但是在机器翻译中，比如目标语句中的一些比较后的词，可能与源语句中前面的一些词对应，这个CTC是没法做到的。
• 多对一映射：CTC的输入和输出是多对一的关系。这意味着输出长度不能超过输入长度，这在手写字体识别或者语音中不是什么问题，因为通常输入都会大于输出，但是对于输出长度大于输入长度的问题CTC就无法处理了。