CTC算法讲解
本文共 10615 字，大约阅读时间需要 35 分钟。
目录
CTC是什么，有什么用？
CTC（Connectionist Temporal Classification），用来解决输入序列和输出序列难以一一对应的问题。
在语音识别中，我们希望音频中的音素和翻译后的字符可以一一对应。但是对齐是一个很困难的事，有人说话快，有人说话慢，每个人说话快慢不同，手动对齐太耗时。
在OCR中，使用RNN时，RNN的每一个输出要对应字符图像中的每一个位置，要手工做这样的标记工作量太大，而且图像中的字符数量不同，字体样式不容，大小不同，导致输出不一定能和每一个字符一一对应。CTC基本原理
假设一个RNN，用r表示RNN的参数，则RNN可以表示为一个函数： y = N w ( x ) y = N_w(x) y=Nw(x)。
定义输入x的时间步长为T，每个时间步长的特征维度记作m，表示m维特征。 x = ( x 1 , x 2 , . . . , x T ) x = (x^1 , x^2, ... , x^T) x=(x1,x2,...,xT) x t = ( x 1 t , x 2 t , . . . , x m t ) x^t = (x^t_1 , x^t_2, ... , x^t_m) xt=(x1t,x2t,...,xmt) 输出时间步也为T，和输入可以一一对应，每个时间步的输出维度作为n，表示n维的输出，实际上是n个概率。 y = ( y 1 , y 2 , . . . , y T ) y = (y^1 , y^2, ... , y^T) y=(y1,y2,...,yT) y t = ( y 1 t , y 2 t , . . . , y m t ) y^t = (y^t_1 , y^t_2, ... , y^t_m) yt=(y1t,y2t,...,ymt) 假设要对26个英文字符进行识别，考虑到有些位置没有字符，定义一个 blank(用 - 代替) 作为空白符加入到字符集合中， L ′ = { a , b , c , . . . , z } ∪ { − } = L ∪ { − } L'= \{a, b, c, ... , z\} \cup \{-\} = L \cup \{-\} L′={ a,b,c,...,z}∪{ −}=L∪{ −}，那么对于RNN而言每个 时间步长的输出维度n就是27，表示27个字符在时间步长上输出的概率。 如果根据这些概率进行选取，每个时间步选取一个元素，就可以得到输出序列，其输出空间可以记作 L ′ T L'^T L′T。 定义一个转换函数B，对RNN的输出序列进行变换，变换成真实的输出，把连续的相同字符删减为1个并删去空白符。如下： B ( π 1 ) = B ( − − s t t a − t − − − e ) = s t a t e B(\pi^1)=B(--stta-t---e)=state B(π1)=B(−−stta−t−−−e)=state B ( π 2 ) = B ( s s t − a a a − t e e − ) = s t a t e B(\pi^2)=B(sst-aaa-tee-)=state B(π2)=B(sst−aaa−tee−)=state B ( π 3 ) = B ( − − s t t a a − t e e − ) = s t a t e B(\pi^3)=B(--sttaa-tee-)=state B(π3)=B(−−sttaa−tee−)=state B ( π 4 ) = B ( s s t − a a − t − − − e ) = s t a t e B(\pi^4)=B(sst-aa-t---e)=state B(π4)=B(sst−aa−t−−−e)=state 其中 π \pi π表示RNN的一种输出序列。当我们在优化RNN时，需要最大化以下概率，即给定输入x的情况下，输出为l的概率，l表示真实的输出，对下式取负号，就可以使用梯度下降求最小。 p ( l ∣ x ) = ∑ B ( π ) = l p ( π ∣ x ) p(l|x)=\sum^{}_{B(\pi)=l }{p(\pi|x)} p(l∣x)=B(π)=l∑p(π∣x)假设时间步之间输出独立，那么对任意一个输出序列 π \pi π的概率计算如下： p ( π ∣ x ) = ∏ t = 1 T y π t t p(\pi|x)=\prod_{t=1}^T{y^t_{\pi_t}} p(π∣x)=t=1∏Tyπtt其中下标 π t \pi_t πt表示的是，输出序列在t时间步选取元素对应的索引，比如该序列在第一时间步选取的元素是a，那么的到值就是1,。选取的是z，那么得到的值就是26,。选取的是空白符，那么得到的值就是27。 对于某一个真实的输出，如state，是有过个RNN输出序列通过B转换得到，这些序列都是我们想要的结果，我们要给定x，这些输出序列的概率加起来最大。如果逐条遍历，时间复杂度使指数级，因为有T个位置，每个位置有n种选择（字符集合的大小），那么就有 n T n^T nT种可能，因此CTC使用HMM中的前向-后向算法来计算。CTC中的前向后向算法
由于真实输出 l l l是一个序列，序列可以通过一个路径图中的一条路径来表示，我们也称输出序列 l l l为路径 l l l。定义路径 l ′ l' l′为：在路径 l l l每两个元素之间以及头尾插入空白符。如下： l = s t a t e l=state l=state l ′ = − s − t − a − t − e − l'=-s-t-a-t-e- l′=−s−t−a−t−e−对某个时间步长的某个字符求导（这里用k表示字符集合中的某个字符或者字符索引）恰好是与概率 y k t y^t_k ykt相关的路径。 ∂ p ( l ∣ x ) ∂ y k t = ∂ ∑ B ( π ) = l , π t = k p ( π ∣ x ) ∂ y k t \frac{\partial p(l | x)}{\partial y_{k}^{t}}=\frac{\partial \sum_{B(\pi)=l, \pi_{t}=k} p(\pi | x)}{\partial y_{k}^{t}} ∂ykt∂p(l∣x)=∂ykt∂∑B(π)=l,πt=kp(π∣x)以前面的 π 1 , π 2 , π 3 , π 4 \pi^{1}, \pi^{2}, \pi^{3}, \pi^{4} π1,π2,π3,π4为例子，简单绘制如下示意图：
4条路径都在t=6时经过了字符a，观察4条路径，可以得到如下式子。 π 1 = b = b 1 : 5 + a 6 + b 7 : 12 π 2 = r = r 1 : 5 + a 6 + r 7 : 12 π 3 = b 1 : 5 + a 6 + r 7 : 12 π 4 = r 1 : 5 + a 6 + b 7 : 12 \begin{aligned} &\pi^{1}=b=b_{1: 5}+a_{6}+b_{7: 12}\\ &\pi^{2}=r=r_{1: 5}+a_{6}+r_{7: 12}\\ &\pi^{3}=b_{1: 5}+a_{6}+r_{7: 12}\\ &\pi^{4}=r_{1: 5}+a_{6}+b_{7: 12} \end{aligned} π1=b=b1:5+a6+b7:12π2=r=r1:5+a6+r7:12π3=b1:5+a6+r7:12π4=r1:5+a6+b7:12 p ( π 1 , π 2 , π 3 , π 4 ∣ x ) = y 1 − ⋅ y 2 − ⋅ y 3 ⋅ y 4 + y 5 t ⋅ y 6 ⋅ y 7 − ⋅ y 8 + y 9 − y 10 − y 11 − y 12 e + y 1 s ⋅ y 2 s ⋅ y 3 t ⋅ y 4 − y 5 ⋅ y 6 ⋅ y 7 a ⋅ y 8 − y 9 t ⋅ y 10 ⋅ y 11 e ⋅ y 12 + y 1 − ⋅ y 2 − ⋅ y 3 ⋅ y 4 + y 5 t 5 ⋅ y 6 ⋅ y 7 ⋅ y 8 − y 9 t 9 ⋅ y 10 ⋅ y 11 e − y 12 − + y 1 s ⋅ y 2 − x 3 s 3 ⋅ y 4 + y 5 t 5 + y 6 a 7 ⋅ y 7 ⋅ y 8 − y 9 t 9 ⋅ y 10 ⋅ y 11 e ⋅ y 12 − + y 1 s ⋅ y 2 s ⋅ y 3 t ⋅ y 4 − y a 5 ⋅ y 6 ⋅ y 7 − y 8 ⋅ 9 − y 10 − y 11 − y 12 e \begin{aligned} p\left(\pi^{1}, \pi^{2}, \pi^{3}, \pi^{4} | x\right) &=y^{1}-\cdot y^{2}-\cdot y^{3} \cdot y^{4}+y^{5} t \cdot y^{6} \cdot y^{7}-\cdot y^{8}+y^{9}-y^{10}-y^{11}-y^{12} e \\ &+y^{1} s \cdot y^{2} s \cdot y^{3} t \cdot y^{4}-y^{5} \cdot y^{6} \cdot y^{7} a \cdot y^{8}-y^{9} t \cdot y^{10} \cdot y^{11} e \cdot y^{12} \\ &+y^{1}-\cdot y^{2}-\cdot y^{3} \cdot y^{4}+y^{5} t^{5} \cdot y^{6} \cdot y^{7} \cdot y^{8}-y^{9} t^{9} \cdot y^{10} \cdot y^{11} e^{-y^{12}}-\\ &+y^{1} s \cdot y^{2}-x^{3} s^{3} \cdot y^{4}+y^{5} t^{5}+y^{6} a^{7} \cdot y^{7} \cdot y^{8}-y^{9} t^{9} \cdot y^{10} \cdot y^{11} e \cdot y^{12}-\\ &+y^{1} s \cdot y^{2} s \cdot y^{3} t \cdot y^{4}-y^{5}_{a} \cdot y^{6} \cdot y^{7}-y^{8} \cdot^{9}-y^{10}-y^{11}-y^{12} e \end{aligned} p(π1,π2,π3,π4∣x)=y1−⋅y2−⋅y3⋅y4+y5t⋅y6⋅y7−⋅y8+y9−y10−y11−y12e+y1s⋅y2s⋅y3t⋅y4−y5⋅y6⋅y7a⋅y8−y9t⋅y10⋅y11e⋅y12+y1−⋅y2−⋅y3⋅y4+y5t5⋅y6⋅y7⋅y8−y9t9⋅y10⋅y11e−y12−+y1s⋅y2−x3s3⋅y4+y5t5+y6a7⋅y7⋅y8−y9t9⋅y10⋅y11e⋅y12−+y1s⋅y2s⋅y3t⋅y4−ya5⋅y6⋅y7−y8⋅9−y10−y11−y12e 令： forward = p ( b 1 : 5 + r 1 : 5 ∣ x ) = y 1 ⋅ y 2 − y 3 ⋅ y 4 ⋅ t 5 + y 1 ⋅ y 2 ⋅ y 2 ⋅ y 3 ⋅ y 4 − y 5 a backward = p ( b 7 : 12 + r 7 : 12 ∣ x ) = y 7 − ⋅ y t 8 ⋅ y 9 − ⋅ y 10 − ⋅ y e 11 + y a 7 ⋅ y − 8 ⋅ y t 9 ⋅ y e 10 ⋅ y e 11 ⋅ y 12 \begin{aligned} &\text { forward }=p\left(b_{1: 5}+r_{1: 5} | x\right)=y^{1} \cdot y^{2}-y^{3} \cdot y^{4} \cdot t^{5}+y^{1} \cdot y^{2} \cdot y^{2} \cdot y^{3} \cdot y^{4}-y^{5} a\\ &\text { backward }=p\left(b_{7: 12}+r_{7: 12} | x\right)=y^{7}-\cdot y^{8}_{t} \cdot y^{9}-\cdot y^{10}-\cdot y^{11}_{e}+y^{7}_{a} \cdot y^{8}_{-} \cdot y_{t}^{9} \cdot y^{10}_{e} \cdot y^{11}_{e} \cdot y^{12} \end{aligned} forward =p(b1:5+r1:5∣x)=y1⋅y2−y3⋅y4⋅t5+y1⋅y2⋅y2⋅y3⋅y4−y5a backward =p(b7:12+r7:12∣x)=y7−⋅yt8⋅y9−⋅y10−⋅ye11+ya7⋅y−8⋅yt9⋅ye10⋅ye11⋅y12 那么可以做如下表示： p ( π 1 , π 2 , π 3 , π 4 ∣ x ) = forward ⋅ y a t ⋅ backward p\left(\pi^{1}, \pi^{2}, \pi^{3}, \pi^{4} | x\right)=\text { forward } \cdot y_{a}^{t} \cdot \text { backward } p(π1,π2,π3,π4∣x)= forward ⋅yat⋅ backward 上述forward和backward只包含了四条路径，如果推广一下forward和backward的含义，考虑所有路径，可以做如下表示： ∑ B ( π ) = l , π 6 = a p ( π ∣ x ) = forward ⋅ y a t ⋅ backward \sum_{B(\pi)=l, \pi_{6}=a} p(\pi | x)=\text { forward } \cdot y_{a}^{t} \cdot \text { backward } B(π)=l,π6=a∑p(π∣x)= forward ⋅yat⋅ backward 定义forward为 α t ( l k ′ ) \alpha_{t}\left(l_{k}^{\prime}\right) αt(lk′)，表示t时刻经过 l k ′ l_{k}^{\prime} lk′字符的路径概率中1-t的概率之和，式子定义如下： α t ( l k ′ ) = ∑ B ( π ) = l , π t = l k ′ ∏ t ′ = 1 t y π t ′ t ′ \alpha_{t}\left(l_{k}^{\prime}\right)=\sum_{B(\pi)=l, \pi_{t}=l_{k}^{\prime}} \prod_{t^{\prime}=1}^{t} y_{\pi_{t^{\prime}}}^{t^{\prime}} αt(lk′)=B(π)=l,πt=lk′∑t′=1∏tyπt′t′ t=1时，符号只能是空白符或者 l 1 l_{1} l1，可以得到以下初始条件： α 1 ( − ) = y 1 − α 1 ( l 1 ) = y l 1 1 α 1 ( l t ) = 0 , ∀ t > 1 \begin{aligned} \alpha_{1}(-) &=y^{1}-\\ \alpha_{1}\left(l_{1}\right) &=y_{l_{1}}^{1} \\ \alpha_{1}\left(l_{t}\right)=0, \forall t>1 \end{aligned} α1(−)α1(l1)α1(lt)=0,∀t>1=y1−=yl11 
观察上图可以看出，如果t=6时字符是a，那么t=5时只能是字符a，t，空白符三选一。 可以得到如下递推关系： α 6 ( a ) = ( α 5 ( a ) + α 5 ( t ) + α 5 ( − ) ) ⋅ y a 6 \alpha_{6}(a)=\left(\alpha_{5}(a)+\alpha_{5}(t)+\alpha_{5}(-)\right) \cdot y_{a}^{6} α6(a)=(α5(a)+α5(t)+α5(−))⋅ya6更一般： α t ( l k ′ ) = ( α t − 1 ( l k ′ ) + α t − 1 ( l k − 1 ′ ) + α t − 1 ( − ) ) ⋅ y l k t \alpha_{t}\left(l_{k}^{\prime}\right)=\left(\alpha_{t-1}\left(l_{k}^{\prime}\right)+\alpha_{t-1}\left(l_{k-1}^{\prime}\right)+\alpha_{t-1}(-)\right) \cdot y_{l_{k}}^{t} αt(lk′)=(αt−1(lk′)+αt−1(lk−1′)+αt−1(−))⋅ylkt 定义backward为 β t ( s ) \beta_{t}(s) βt(s)，表示t时刻经过 l k ′ l_{k}^{\prime} lk′字符的路径概率中t~T的概率之和，式子如下： β t ( l k ′ ) = ∑ B ( π ) = l , π t = l k ′ ∏ t ′ = t T y π t ′ t ′ \beta_{t}\left(l_{k}^{\prime}\right)=\sum_{B(\pi)=l, \pi_{t}=l_{k}^{'}} \prod_{t'=t}^{T} y_{\pi_{ {t}^{\prime}}}^{t^{\prime}} βt(lk′)=B(π)=l,πt=lk′∑t′=t∏Tyπt′t′t=T时，符号只能是空白符或者 l ∣ l ′ ∣ − 1 l_{\left|l^{\prime}\right|-1} l∣l′∣−1，可以得到以下初始条件： β T ( − ) = y − T β T ( l ∣ l ′ ∣ − 1 ′ ) = y l ∣ l ′ ∣ − 1 ′ T β T ( l ∣ l ′ ∣ − i ) = 0 , ∀ i > 1 \begin{aligned} \beta_{T}(-) &=y^{T}_{-} \\ \beta_{T}\left(l_{\left|l^{\prime}\right|-1}^{\prime}\right) &=y_{l_{|l^{\prime}|-1}^{\prime} }^{T} \\ \beta_{T}\left(l_{\left|l^{\prime}\right|-i}\right) &=0, \forall i>1 \end{aligned} βT(−)βT(l∣l′∣−1′)βT(l∣l′∣−i)=y−T=yl∣l′∣−1′T=0,∀i>1 同理，可以得到如下递归条件： β t ( l k ′ ) = ( β t + 1 ( l k ′ ) + β t + 1 ( l k + 1 ′ ) + β t + 1 ( − ) ) ⋅ y l k t t k \beta_{t}\left(l_{k}^{\prime}\right)=\left(\beta_{t+1}\left(l_{k}^{\prime}\right)+\beta_{t+1}\left(l_{k+1}^{\prime}\right)+\beta_{t+1}(-)\right) \cdot y_{l_{k}^{t}}^{t_{k}} βt(lk′)=(βt+1(lk′)+βt+1(lk+1′)+βt+1(−))⋅ylkttk 根据forward和backward的式子定义，它们相乘可以得到： α t ( l k ′ ) β t ( l k ′ ) = ∑ B ( π ) = l , π t = l k t y l k t ∏ t = 1 T y π t t \alpha_{t}\left(l_{k}^{\prime}\right) \beta_{t}\left(l_{k}^{\prime}\right)=\sum_{B(\pi)=l, \pi_{t}=l_{k}^{t}} y_{l_{k}^{t}} \prod_{t=1}^{T} y_{\pi_{t}}^t αt(lk′)βt(lk′)=B(π)=l,πt=lkt∑ylktt=1∏Tyπtt 又因为 p ( l ∣ x ) p(l | x) p(l∣x)对 l k ′ l_{k}^{\prime} lk′求导时，只跟那些 π t = l k ′ \pi_{t}=l_{k}^{\prime} πt=lk′的路径有关，那么求导时可以简写如下式子： p ( l ∣ x ) = ∑ B ( π ) = l , π t = l k ′ p ( π ∣ x ) = ∑ B ( π ) = l , π t = l k ′ ∏ t = 1 T y π t t p(l | x)=\sum_{B(\pi)=l, \pi_{t}=l_{k}^{\prime}} p(\pi | x)=\sum_{B(\pi)=l, \pi_{t}=l_{k}^{\prime}} \prod_{t=1}^{T} y_{\pi_{t}}^{t} p(l∣x)=B(π)=l,πt=lk′∑p(π∣x)=B(π)=l,πt=lk′∑t=1∏Tyπtt结合上面两个式子，得到： p ( l ∣ x ) = ∑ B ( π ) = l , π t = l k ′ α t ( l k ′ ) β t ( l k ′ ) y l k ′ t p(l | x)=\sum_{B(\pi)=l, \pi_{t}=l_{k}^{\prime}} \frac{\alpha_{t}\left(l_{k}^{\prime}\right) \beta_{t}\left(l_{k}^{\prime}\right)}{y_{l_{k}^{\prime}}^{t}} p(l∣x)=B(π)=l,πt=lk′∑ylk′tαt(lk′)βt(lk′)最后可以得到求导式（这里用k来表示字符，和 l k ′ l_{k}^{\prime} lk′）的含义相同： ∂ p ( l ∣ x ) ∂ y k t = ∂ ∑ B ( π ) = l , π t = k α t ( k ) β t ( k ) y k t ∂ y k t \frac{\partial p(l | x)}{\partial y_{k}^{t}}=\frac{\partial \sum_{B(\pi)=l, \pi_{t}=k} \frac{\alpha_{t}(k) \beta_{t}(k)}{y_{k}^{t}}}{\partial y_{k}^{t}} ∂ykt∂p(l∣x)=∂ykt∂∑B(π)=l,πt=kyktαt(k)βt(k)求导式里，forward和backward可以用前面的dp递推公式计算出来，时间复杂度是nT，大大减小了计算量。 这样对RNN的输出y求导之后，再根据y对RNN里面的权重参数w进行链式求导，就可以使用梯度下降的方法来更新参数了。 CTC预测
一种方法是Best Path search。计算概率最大的一条输出序列，但是这样没有考虑多个输出序列对应一个真实输出。如： [ s , s , − ] [s, s,-] [s,s,−]和 [ s , s , s ] [s, s, s] [s,s,s]的概率比 [ s , t , a ] [s, t, a] [s,t,a]低，但是他们的概率之和会高于 [ s , t , a ] [s, t, a] [s,t,a]。
第二种方法，是Beam Search。假设指定B=3，预测过程如下图所示。在第一时间步长选取概率最大的三个字符，然后在第二个时间步也选取概率最大的三个字符，两两组合可以组合成9个序列，这些序列在B转换之后会得到一些相同输出，把具有相同输出的序列进行合并，比如有三个序列都可以转换为a，把他们合并，计算出概率最大的三个序列，然后继续和下一个时间步长的字符进行相同的合并。
有一点需要注意的是合并相同字符，比如上图，T=3时，第一个前缀序列a，在跟相同字符a合并的时候，除了产生a之外，还会产生一个aa的有效输出，这是因为这个前缀序列a在T=2的时候曾经把空白符号合并掉了，实际上这个前缀序列a后面是跟着一个空白符的，所以它在跟相同字符a合并的时候中间是有一个隐藏的空白符，合并之后得到的应该是两个a。 因此合并相同字符的时候，如果要合并成aa，需要统计在这之前以空白符结尾的那些序列的概率，如果要合并成a，计算的是不以空白符结尾的那些序列的概率。出于这个事实，我们需要跟踪前两处的输出，以便后续的合并运算。
CTC的性质
- 条件独立假设。CTC做了一个假设是不同时间步的输出之间是独立的。这个假设对于很多序列问题来说并不成立，输出序列之间往往存在联系。
- 单调对齐。CTC只允许单调对齐，在语音识别中可能是有效的，但是在机器翻译中，比如目标语句中的一些比较后的词，可能与源语句中前面的一些词对应，这个CTC无法做到。
- 多对一映射。CTC的输入和输出是多对一的关系。这意味着输出长度不能超过输入长度，这在手写字体识别或者语音中不是什么问题，因为通常输入都会大于输出，但是对于输出长度大于输入长度的问题，CTC就无法处理。
参考文章
转载地址：http://grjgz.baihongyu.com/
你可能感兴趣的文章