一、本文参考
根据重要性排名
【Learning Notes】CTC 原理及实现_MoussaTintin的博客-CSDN博客_ctc实现
白话CTC(connectionist temporal classification)算法讲解_罗罗可爱多的博客-CSDN博客_ctc 算法
二、CTC的作用概述
CTC（connectionist Temporal Classification）连接时序分类。
?
?
以语音识别为例，以一段”你好”的语音为例，经过MFCC特征提取后产生30帧，每帧含有12个特征，即
。经过DNN后得到后验概率
，矩阵里面每一列之和为1（softmax之和为1）。
我们希望在最后的softmax矩阵中使得生成”nihao”的所有路径的概率最大。
因此在音素没有对齐的情况下，目标函数应该为
中所有元素的概率之和。即：
其中z为目标音素的扩展版字符集。
CTC的训练过程是通过
调整w值使得值最大，计算过程如下:
因此，只要得到，即可根据反向传播，得到
。
解读如下：
正向：输入的x经过神经网络后得到y，计算p(z|y)的值
反向：p(z|y)对上一层的输出y求导，然后y再对x求导就得到了w的值
三、CTCLoss原理
1、aligh-free变长映射
ocr或者语音序列学习任务一般是多对多的映射关系，语音识别中好几帧对应若干音节或者字符，并且每个输入和输出之间也没有清楚的对应关系。
CTC引入一个特殊blank字符解决多对一映射问题。
扩展原始词表?L?为?L′=L∪{blank}L′=L∪{blank}。对输出字符串，定义操作?B：
1）合并连续的相同符号；
2）去掉 blank 字符
2、定义
（1）
表示在第t个时间，类别为k的softmax值。
神经网络层最终输出的为softmax矩阵，也即后验概率矩阵y
（2）
表示路径集合，l为路径字符集
（3）和大多数有监督学习一样，CTC使用最大似然标准进行训练
在给定输入情况下，输出路径的概率为：
?
所有路径
，我们的目标是p(l|x)越大越好。
在t点k类别时
。
3、前向-后向的缘由
假设有2条路径在t时刻经过k类别，如下所示：
定义F1为从第1时间点到t时间点的路径概率积的值，F1‘为从第1时间点到t-1时间点的路径概率积的值。
，类似的B1定义为: 
为什么不直接定义F1为从第1点到第t-1点的概率之积？因为此时F1没有固定唯一的终点，从没有固定的起点到没有固定的终点，是不能这么定义的，定义时至少有一个明确的起点或者终点。
此时通过以上2条路径可以衍生出4条路径：
对t时刻k类别的p(l|x)继续计算如下：
用??α?来表示forward的部分，??β?表示backward的部分，上式继续计算如下：
?
最后得到：
?
反向传播求导如下：
除法的求导公式如下：
于是：
因为
中包含
，所以对其求导后再乘以
，就又得到了
。
L中可能包含多个k字符，它们计算的梯度要进行累加
优化似然函数取对数，于是：
4、forward和backward的递推关系
都有对应的初始化值和递推关系如下：
末尾带有blank和不带有blank都是正确的，最后可以得到似然?p(l|x)=αT(|l′|)+αT(|l′|?1)。
四、解码
训练好的模型用新的样本输入来预测对应的输出字符串，这个过程是解码的过程。
按照最大似然准则，最优的解码结果为：
求该解可用贪心搜索算法和束搜索算法。
1、贪心搜索
贪心搜索就是每个时间t中都选择概率最高的那个分类组成最后的路径。
2、束搜索
贪心搜索只能找出局部最优的一条路径，而束搜索是找出局部最优的N条路径，N是束宽（beam size）。
假如取beam size为2，
第1个时间点找到最优的两个是AC
第2个时间点，通过A遍历所有类别，通过C遍历所有类别，在上述2个类别的值中找到最优的两个是AB和CE
第3个时间点，通过AB遍历所有类别，通过CE遍历所有类别，在上述2个类别的值中找到最优的两个是ABD和CED。
计算时间复杂度，假如beam size为k，时间段为T，类别为N，则时间复杂度为：T*N*k