长春电商网站建设费用,江门建网站,网站seo排名优化工具在线,网站如何做sem文章目录1.基础介绍2.Connectionist Temporal Classification(CTC)算法2.1 什么是Temporal Classification2.2 CTC问题描述2.2关于对齐2.3 前向后向算法2.4 推理时3.pytorch中的CTCLOSS参考资料欢迎访问个人网络日志#x1f339;#x1f339;知行空间#x1f339;#x1f3…
文章目录1.基础介绍2.Connectionist Temporal Classification(CTC)算法2.1 什么是Temporal Classification2.2 CTC问题描述2.2关于对齐2.3 前向后向算法2.4 推理时3.pytorch中的CTCLOSS参考资料欢迎访问个人网络日志知行空间 1.基础介绍 论文Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks 这是2006年第23次ICML会以上的一篇论文。
很多实际应用需要从未切分的数据中输出序列信息如语音识别中的语音转文字,光学字符识别(Optical character recognition,OCR)中的字符图片转字符序列。循环神经网络(Recurrent neural networks,RNN)十分适合序列数据的学习但其训练数据要求必须是切分后的序列而实际应用中切分的训练序列数据标注比较困难是很难获取的。 上图是OCR的两种模型一种如图(a)可直接输入OCR检测得到的图片得到图片中的字符串can另外一种需要先将图片按字符进行切割这种方式比较数据处理比较复杂而这种正是循环神经网络RNN要求的输入。
为了充分利用循环神经网络RNN处理序列数据的能力同时避免对输入序列图像进行切分本文作者提出了Connectionist Temporal Classificatio(CTC)算法。
2.Connectionist Temporal Classification(CTC)算法
2.1 什么是Temporal Classification
SSS是从分布DX×Z\mathcal{D}_{\mathcal{X}\times\mathcal{Z}}DX×Z从获取的训练数据 输入空间X(Rm)∗\mathcal{X}(\mathbb{R}^m)^*X(Rm)∗是mmm维的实值向量序列目标空间ZL∗\mathcal{Z}L^*ZL∗由字母集LLL组成的标签序列训练数据集SSS中的每个样本由序列对(x,z)(\mathbf{x},\mathbf{z})(x,z)组成。目标序列z(z1,z2,...,zU)\mathbf{z}(z_1,z_2,...,z_U)z(z1,z2,...,zU)长度小于等于输入序列x(x1,x2,...,xT),i.e.U≤T\mathbf{x}(x_1,x_2,...,x_T),i.e.U\le Tx(x1,x2,...,xT),i.e.U≤T。输入序列和输出序列长度一般不同因此没有先验知识可以对齐他们。
Temporal Classification的任务是使用训练数据SSS,学习一个分类器能够将输入序列分成对应的目标序列h:X→Zh:\mathcal{X}\rightarrow\mathcal{Z}h:X→Z
从第一部分介绍可以知道OCR任务本身就是一个Temporal Classification翻译成了时间序列分类问题。其输入是卷积后得到特征图序列输出的是字符序列。
之所以被称为Connectionist Temporal Classification是这样理解的原始输入的是一整张联结在一起未切分的字符图像输出的是字符序列因为没有对原始图像上的字符进行切分预处理因此被称之为连接序列分类。
2.2 CTC问题描述 从网络输入到获取标签序列要分成两步
第一步可以将输入为长度为TTT的序列x[x1,x2,...,xT]\mathbf{x}[x_1,x_2,...,x_T]x[x1,x2,...,xT](序列中每个xxx都是m维),输出为长度TTT的序列y[y1,y2,...,yT]\mathbf{y}[y_1,y_2,...,y_T]y[y1,y2,...,yT](序列中每个yyy都是n维),参数为www的映射(即循环神经网络)定以为Nw:(Rm)T→(Rn)T\mathcal{N}_w:(\mathbb{R}^m)^T\rightarrow(\mathbb{R}^n)^TNw:(Rm)T→(Rn)TyNw(x)\mathbf{y}\mathcal{N}_w(\mathbf{x})yNw(x)。将ykty_k^tykt表示成第ttt个序列值为kkk的概率L′TL^TL′T表示长度为TTT的序列,其中每个元素取自字母集L′L∪{blank}LL\cup\{blank\}L′L∪{blank}序列L′TL^TL′T也被称之为路径表示成π\piπ。
根据以上定义给定输入x\mathbf{x}x,输出为路径π\piπ的概率可表示成
p(π∣x)∏t1Tyπtt,∀π∈L′Tp(\pi|\mathbf{x})\prod_{t1}^{T}y_{\pi_t}^t,\forall\pi\in L^T p(π∣x)t1∏Tyπtt,∀π∈L′T
其实这里还有个条件就是每一步输出之间是相互独立上面的公式才能成立。
第二步我们知道输入x\mathbf{x}x对应的标签序列为长度等于UUU的序列z[z1,z2,...,zU]U≤T\mathbf{z}[z_1,z_2,...,z_U]U\le Tz[z1,z2,...,zU]U≤T,在第一步中循环神经网络给出的只是长度为TTT的中间序列y\mathbf{y}y,要和长度为UUU的标签序列z\mathbf{z}z对应还需要定义个从中间序列到标签序列的映射B:L′T↦LT\mathcal{B}:L^T\mapsto L^{\lt T}B:L′T↦LT,很明显B\mathcal{B}B是一个多对一的映射。这个映射可以定义为移除中间序列中的重复相邻字符和空格占位符如B(s−ta−tt−e)B(s−t−aa−tt−e)state\mathcal{B}(s-ta-tt-e)\mathcal{B}(s-t-aa-tt-e)stateB(s−ta−tt−e)B(s−t−aa−tt−e)state,定义了映射B\mathcal{B}B后可以将输出标签序列z\mathbf{z}z的后验概率表示成
p(z∣x)∑π∈B−1(z)p(π∣x)p(\mathbf{z}|\mathbf{x})\sum_{\pi\in\mathcal{B}^{-1}(\mathbf{z})}p(\pi|\mathbf{x}) p(z∣x)π∈B−1(z)∑p(π∣x)
2.2关于对齐
为什么要使用上述的方法来进行网络的训练呢那是因为输入x[x1,x2,...,xm]\mathbf{x}[x_1,x_2,...,x_m]x[x1,x2,...,xm]和标签序列z[z1,z2,...,zU]\mathbf{z}[z_1,z_2,...,z_U]z[z1,z2,...,zU]之间在序列长度序列长度比例对应元素之间找不到什么对应关系。 如上图是对齐后的数据但在实际中是很难知道(x1,x2)↦c,(x3,x4,x5)↦a,(x6)↦t(x_1,x_2)\mapsto c,(x_3,x_4,x_5)\mapsto a,(x_6)\mapsto t(x1,x2)↦c,(x3,x4,x5)↦a,(x6)↦t,标注这样的数据也需要花费大量的时间因此更希望模型能够拥有从未对齐数据中学习的能力通过前面的介绍使用CTC算法可以从未对齐的输入中求得标签序列。
2.3 前向后向算法 使用暴力方法计算
p(z∣x)∑π∈B−1(z)p(π∣x)p(\mathbf{z}|\mathbf{x})\sum_{\pi\in\mathcal{B}^{-1}(\mathbf{z})}p(\pi|\mathbf{x}) p(z∣x)π∈B−1(z)∑p(π∣x)
因为要计算每一条路径因此对于序列字典中有nnn个元素长度为TTT的序列要计算所有路径的概率时间复杂度为O(nT)O(n^T)O(nT)这是指数级的时间复杂度对于大部分长度的序列这个运算都过于耗时。论文作者为了解决这个问题提出了前向后向递推算法采用动态规划的方法将时间复杂度降到了O(nT)O(nT)O(nT),使算法更可行。
先借个例子来看一下。
假设标签序列为 zstate\mathbf{z} state zstate
在序列前后和每个字符中间添加空格占位符−-−
z′−s−t−a−t−e−\mathbf{z}-s-t-a-t-e- z′−s−t−a−t−e−
对z′\mathbf{z}z′中任意的字符重复任意次经过B\mathcal{B}B映射都能得到标签序列statestatestate因此可以将z′\mathbf{z}z′当成满足变换条件的基础序列。B\mathcal{B}B是多对一的映射如下4个路径都能得到statestatestate
B(−−sttaa−tee−)stateB(−−stta−t−−−e)stateB(sst−aaa−tee−)stateB(sst−aa−t−−−e)state\mathcal{B}(--sttaa-tee-)state\\ \mathcal{B}(--stta-t---e)state\\ \mathcal{B}(sst-aaa-tee-)state\\ \mathcal{B}(sst-aa-t---e)state B(−−sttaa−tee−)stateB(−−stta−t−−−e)stateB(sst−aaa−tee−)stateB(sst−aa−t−−−e)state
将z′\mathbf{z}z′写成列的形式则上述四条路径可以写成如下图的形式 从上图可以看到四条路径在序列t6t6t6时都经过字符aaa,记上面的四条路径为π1,π2,π3,π4\pi^1,\pi^2,\pi^3,\pi^4π1,π2,π3,π4
π1bb1:5{a}6b7:12π2rr1:5{a}6r7:12π3b1:5{a}6r7:12π4r1:5{a}6b7:12\pi^1bb_{1:5}\{a\}_6b_{7:12}\\ \pi^2rr_{1:5}\{a\}_6r_{7:12}\\ \pi^3b_{1:5}\{a\}_6r_{7:12}\\ \pi^4r_{1:5}\{a\}_6b_{7:12} π1bb1:5{a}6b7:12π2rr1:5{a}6r7:12π3b1:5{a}6r7:12π4r1:5{a}6b7:12
记ykty_k^tykt表示序列第ttt步元素为kkk的概率则上面四条路径都包含ya6y_a^6ya6这一项将计算上面四条路径的概率表示可以提取公因式写成
fowardp(b1:5r1:5∣x)y−1∗y−2∗ys3∗yt4∗yt5ys1∗ys2∗yt3∗y−4∗ya5backwardp(b7:12r7:12∣x)y−7∗yt8∗y−9∗y−10∗y−11∗ye12ya7∗y−8∗yt9∗ye10∗ye11∗y−12foward p(b_{1:5}r_{1:5}|\mathbf{x}) y_-^1*y_-^2*y_s^3*y_t^4*y_t^5 y_s^1*y_s^2*y_t^3*y_-^4*y_a^5\\ backward p(b_{7:12}r_{7:12}|\mathbf{x}) y_-^7*y_t^8*y_-^9*y_-^{10}*y_-^{11}*y_e^{12} y_a^7*y_-^8*y_t^9*y_e^{10}*y_e^{11}*y_-^{12} fowardp(b1:5r1:5∣x)y−1∗y−2∗ys3∗yt4∗yt5ys1∗ys2∗yt3∗y−4∗ya5backwardp(b7:12r7:12∣x)y−7∗yt8∗y−9∗y−10∗y−11∗ye12ya7∗y−8∗yt9∗ye10∗ye11∗y−12
然后上面四条路径的概率和可以写成
p(π1,π2,π3,π4∣x)forward∗ya6∗backwardp(\pi^1,\pi^2,\pi^3,\pi^4|\mathbf{x}) forward*y_a^6*backward p(π1,π2,π3,π4∣x)forward∗ya6∗backward
上面的介绍中只取了四条经过变换B\mathcal{B}B后能得到statestatestate的路径实际上的路径要远远多于此 从上图中选出经过{a}6\{a\}_6{a}6的所有路径概率∑B(π)z,π6ap(π∣x)\sum\limits_{\mathcal{B}(\pi)\mathbf{z},\pi_6a}p(\pi|x)B(π)z,π6a∑p(π∣x)(π6a\pi_6aπ6a表示路径π\piπ的第6个字符为a),同样还是可以表示成如下形式:
∑B(π)z,π6ap(π∣x)forward∗ya6∗backward\sum\limits_{\mathcal{B}(\pi)\mathbf{z},\pi_6a}p(\pi|x)forward*y_a^6*backwardB(π)z,π6a∑p(π∣x)forward∗ya6∗backward
进一步推广定义αt(s)\alpha_t(s)αt(s)表示路径π\piπ中的第t个字符与加了占位符后标签序列z′\mathcal{z}z′的第s个字相对应且路径π\piπ满足B(π1:t)z1:s\mathcal{B}(\pi_{1:t})\mathbf{z}_{1:s}B(π1:t)z1:s时所有路径π1:t\pi_{1:t}π1:t的概率和,表示成
αt(s)∑B(π1:t)留−z1:s′∏t′1tyπt′t′\alpha_t(s)\sum\limits_{\mathcal{B}(\pi_{1:t})\overset{留-}{}\mathbf{z}_{1:s}}\prod_{t1}^{t}y^{t}_{\pi_{t}} αt(s)B(π1:t)留−z1:s′∑t′1∏tyπt′t′
可以看到这等同于前向变量forwardforwardforward现在来看t1t1t1时的α1(s)\alpha_1(s)α1(s),要经过B\mathcal{B}B映射后能得到保留占位符的标签序列sss就只能等于1或者2看上图中−s−t−a−t−e−-s-t-a-t-e-−s−t−a−t−e−的例子t1时刻只能取z′\mathcal{z}z′的−-−或者sss,否则无法经过B\mathcal{B}B映射得到标签序列因此
α1(1)y−1α1(2)yz2′1α1(s)0,∀s2\alpha_1(1)y^1_{-}\\ \alpha_1(2)y^1_{\mathbf{z}_2}\\ \alpha_1(s)0,\forall s\gt2 α1(1)y−1α1(2)yz2′1α1(s)0,∀s2
还看statestatestate的例子当过z′6{\mathbf{z}}_6z′6时t5t5t5对应的字符只能是t/−/at/-/at/−/a,可以推出来上面例子中
α6(6)(α5(4)α5(5)α5(6))∗ya6\alpha_6(6)(\alpha_5(4)\alpha_5(5)\alpha_5(6))*y_a^6 α6(6)(α5(4)α5(5)α5(6))∗ya6 一般化推广可得
αt(s)(αt−1(s−2)αt−1(s−1)αt−1(s))∗yzs′t\alpha_t(s)(\alpha_{t-1}(s-2)\alpha_{t-1}(s-1)\alpha_{t-1}(s))*y_{\mathbf{z}_s}^{t} αt(s)(αt−1(s−2)αt−1(s−1)αt−1(s))∗yzs′t
还需考虑一个特殊情况看下面例子zzoo,z′−z−o−o−\mathbf{z}zoo,\mathbf{z}-z-o-o-zzoo,z′−z−o−o−,t2,s6或3: 很明显因为B\mathcal{B}B映射会去除重复的字母因此上面两种情况在t−1t-1t−1时刻不能取s−2s-2s−2
综上可得最终t≥2t\ge2t≥2时前向递推公式为(也就是原论文上的递推公式)
αt(s){(αt−1(s−1)αt−1(s))∗yzs′tifzs′−orzs′zs−2′(αt−1(s−2)αt−1(s−1)αt−1(s))∗yzs′totherwise\alpha_t(s)\left\{\begin{matrix} (\alpha_{t-1}(s-1)\alpha_{t-1}(s))*y_{\mathbf{z}_s}^{t}\,if\,z_s-\,or\,z_sz_{s-2} \\ (\alpha_{t-1}(s-2)\alpha_{t-1}(s-1)\alpha_{t-1}(s))*y_{\mathbf{z}_s}^{t}\,otherwise \end{matrix}\right. αt(s){(αt−1(s−1)αt−1(s))∗yzs′tifzs′−orzs′zs−2′(αt−1(s−2)αt−1(s−1)αt−1(s))∗yzs′totherwise
将公式中相同的项合并一下就可以得到论文上的公式了。
同样的方法可以定义backwardbackwardbackward:
βt(s)∑B(πt:T)留−zs:∣z′∣′∏t′tTyπt′t′\beta_t(s)\sum\limits_{\mathcal{B}(\pi_{t:T})\overset{留-}{}\mathbf{z}_{s:|z|}}\prod_{tt}^{T}y^{t}_{\pi_{t}} βt(s)B(πt:T)留−zs:∣z′∣′∑t′t∏Tyπt′t′
t≥2t\ge2t≥2时βt(s)\beta_t(s)βt(s)的递推公式
βt(s){(βt1(s)βt1(s1))∗yzs′tifzs′−orzs′zs2′(βt1(s)βt1(s1)βt1(s2))∗yzs′totherwise\beta_t(s)\left\{\begin{matrix} (\beta_{t1}(s)\beta_{t1}(s1))*y_{\mathbf{z}_s}^{t}\,if\,z_s-\,or\,z_sz_{s2} \\ (\beta_{t1}(s)\beta_{t1}(s1)\beta_{t1}(s2))*y_{\mathbf{z}_s}^{t}\,otherwise \end{matrix}\right. βt(s){(βt1(s)βt1(s1))∗yzs′tifzs′−orzs′zs2′(βt1(s)βt1(s1)βt1(s2))∗yzs′totherwise
求得αt(s)\alpha_t(s)αt(s)和βt(s)\beta_t(s)βt(s)后标签序列z\mathbf{z}z的后验概率可以写成
p(z∣x)∑zs′∈πtαt(s)βt(s)yzs′tp(\mathbf{z}|\mathbf{x})\sum_{z_s\in\pi_t}\frac{\alpha_t(s)\beta_t(s)}{y_{z_s}^t} p(z∣x)zs′∈πt∑yzs′tαt(s)βt(s)
求得p(z∣x)p(\mathbf{z}|\mathbf{x})p(z∣x)后可以知道使用CTCCTCCTC时的目标就是最大化p(z∣x)p(\mathbf{z}|\mathbf{x})p(z∣x),可以定义损失函数为−log(p(z∣x))-log(p(\mathbf{z}|\mathbf{x}))−log(p(z∣x))可以推导损失的计算和损失函数梯度都能使用递推的方式来计算减少运算量加快运算速度。
2.4 推理时
训练完成后在网络推理时希望取概率最大的输出序列
z∗argmaxzp(z∣x)\mathbf{z}^* \underset{\mathbf{z}}{argmax} \,p(\mathbf{z}|\mathbf{x}) z∗zargmaxp(z∣x)
对所有路径的概率求和然后取概率最大的路径作为预测的结果应该是最合理的方式但当序列比较长时面临计算量过大影响推理速度的情况。
一种做法是对于第ttt步取概率最大的字符然后将所有的字符组合起来经过去重当作最终的输出但这种做法只考虑了一条路径有可能有多条路径对应标签各条路径的概率加和后有可能更大。
一种替代的折衷方法是改进版的Beam Search。
常规的Beam Search算法对于每个时间步取概率最大的几个(Beam Size)可能结果如下为字母集为−,a,b-,a,b−,a,bBeam Size3的Beam Search的过程 上图中Beam Search到当前步最大的几个(Beam Size)可能字符都只有一条前缀序列实际上可以有多条前缀序列和当前的字符组合后都得到相同的输出如下图对于路径长度T2T2T2时λa\lambda aλa,a−a-a−,aaaaaa最后都能对应的aaa a a a b a a a b b a ϵ a b ϵ a b ϵ a b λ a b ϵ a b ϵ a b ϵ a b λ ϵ a b T 4 T 3 T 2 T 1 current hypotheses proposed extensions current hypotheses proposed extensions current hypotheses proposed extensions current hypotheses Multiple extensions merge to the same prefix empty string 且观察T3T3T3时前缀序列aaaaaa对应的输出有可能是aaa或者aaaaaa,因此对应的概率应该分别进行计算。
3.pytorch中的CTCLOSS
计算未切分的连续时间序列和目标序列之间的损失。
torch.nn.CTCLoss(blank0, reductionmean, zero_infinityFalse)class CTCLoss:...def forward(self, log_probs: Tensor, targets: Tensor, input_lengths: Tensor, target_lengths: Tensor) - Tensor:... log_probsTensor of size (T,N,C)/(T,C),T是输入长度N是Batch SizeC是序列字典的大小(包括空格) targetsTensor of sizeNSN是batch sizeS是最大目标序列长度目标序列中的每个元素是类别的序号。 input_lengths每个输入序列的长度为元组tuple或shape为(N,)的张量N是batch sizeinput_lengths的值≤T\le T≤T target_lengths,每个目标序列的长度为元组tuple或shape为(N,)的张量N是batch size如果targets的shape是(N,S),这里其实是把每个targettargettarget添加padding后变成了S假设第n个序列目标长度为sns_nsn,target_lengths中第n个元素值就为sns_nsn。
import torchT 2
C 3
N 1
S 2
S_min 1input torch.randn(T,N,C).log_softmax(2).detach().requires_grad_()
print(input)
target torch.tensor([0,1], dtypetorch.long).reshape(shape(N, S))
print(target)
input_lengths torch.full(size(N,), fill_valueT, dtypetorch.long)
target_lengths torch.tensor([2], dtypetorch.long).reshape(shape(N,))
ctc_loss torch.nn.CTCLoss()
loss ctc_loss(input, target, input_lengths, target_lengths)
print(loss)# tensor([[[-0.4002, -1.5314, -2.1752]], [[-0.8444, -2.2039, -0.7770]]], requires_gradTrue)
# tensor([[0, 1]])
# tensor(1.3021, grad_fnMeanBackward0)上面示例的计算过程 从上图可以看到目标是010101即at路径有且仅有此一条损失值计算为
loss−12[−0.4002(−2.2039)]1.3021loss -\frac{1}{2}[-0.4002(-2.2039)]1.3021 loss−21[−0.4002(−2.2039)]1.3021 欢迎访问个人网络日志知行空间 参考资料 1.https://distill.pub/2017/ctc/2.https://zhuanlan.zhihu.com/p/1611869073.https://zhuanlan.zhihu.com/p/5199609054.https://zhuanlan.zhihu.com/p/58526617
