對(duì)于輸入序列 X = [ x 1 , x 2 , . . , x T ] X=[x_1, x_2, .., x_T] X=[x1,x2,..,xT] 和 輸出序列 Y = [ y 1 , y 2 , . . . , y U ] Y = [y_1, y_2, ..., y_U ] Y=[y1,y2,...,yU]，我們希望訓(xùn)練一個(gè)模型使條件概率 P ( Y ∣ X ) P(Y|X) P(Y∣X) 達(dá)到最大化，并且給定新的輸入序列時(shí)我們希望模型可以推測(cè)出最優(yōu)的輸出序列， Y ∗ = a r g m a x Y P ( Y ∣ X ) Y^*=\underset{Y}{argmax}\space P(Y|X) Y∗=Yargmax P(Y∣X)，而CTC算法剛好可以同時(shí)做到訓(xùn)練和解碼。
那么對(duì)于整個(gè)數(shù)據(jù)集，可以得到目標(biāo)函數(shù) ∑ ( X , Y ) ∈ 訓(xùn) 練 數(shù) 據(jù) 集 − l o g P ( Y ∣ X ) \sum_{(X,Y)\in 訓(xùn)練數(shù)據(jù)集}-log\space P(Y|X) ∑(X,Y)∈訓(xùn)練數(shù)據(jù)集−log P(Y∣X)，訓(xùn)練中需要將其最小化。
為了實(shí)現(xiàn)這個(gè)算法，先引入一個(gè)中間序列 Z = ( ϵ , y 1 , ϵ , y 2 . . . , ϵ , y U ) Z=(\epsilon,y_1,\epsilon,y_2...,\epsilon,y_U) Z=(ϵ,y1,ϵ,y2...,ϵ,yU)，也就是在label序列的起始，中間和終止位置插入空白token，引入這個(gè)中間序列可以說是CTC算法的精髓之一，下面我們以簡(jiǎn)單的 Y = ( a , b ) Y=(a,b) Y=(a,b) 輸出序列進(jìn)行說明：
中間序列 Z = ( ϵ , a , ϵ , b , ϵ ) Z=(\epsilon,a,\epsilon,b,\epsilon) Z=(ϵ,a,ϵ,b,ϵ)，長(zhǎng)度為 S S S
輸入序列 X = ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) X=(x_1, x_2, x_3, x_4,x_5,x_6) X=(x1,x2,x3,x4,x5,x6)，長(zhǎng)度為 T T T
遞歸參數(shù) α s , t \alpha_{s,t} αs,t 到 t t t 時(shí)刻為止中間序列的子序列 Z 1 : s Z_{1:s} Z1:s獲得的概率分?jǐn)?shù)，也就是在 t t t時(shí)刻走到中間序列第 s s s個(gè)token時(shí)的概率分?jǐn)?shù)
算法整體流程如下圖所示，和原文中的圖比起來加入了具體數(shù)值，理解起來更加直觀，圖中的紅色路徑表示不能進(jìn)行跳轉(zhuǎn)，因?yàn)槿绻苯訌? t = 2 t=2 t=2 的第一個(gè) ϵ \epsilon ϵ 跳到 t = 3 t=3 t=3 時(shí)刻的第3個(gè) ϵ \epsilon ϵ，中間的token a a a 會(huì)被忽略，這樣后面的路徑不管怎么走都得不到正確的token序列。
其他情況下都可以接受來自上一個(gè)時(shí)刻的第 s − 2 , s − 1 , s s-2,s-1,s s−2,s−1,s個(gè)token的跳轉(zhuǎn)，再對(duì)圖中的節(jié)點(diǎn)做進(jìn)一步解釋，以綠色節(jié)點(diǎn)為例，該節(jié)點(diǎn)就是 α 4 , 4 \alpha_{4,4} α4,4 （下標(biāo)從1開始），表示前面不管怎么走，在 t = 4 t=4 t=4時(shí)刻落到第4個(gè)token時(shí)獲得的概率分?jǐn)?shù)，也就是把這個(gè)時(shí)刻能走到 b b b 的所有alignment 概率分?jǐn)?shù)加起來。那么把最后一幀的2個(gè)節(jié)點(diǎn)的概率分?jǐn)?shù)相加就是所有alignment的概率分?jǐn)?shù)，即 P ( Y ∣ X ) = α S , T + α S − 1 , T P(Y|X)=\alpha_{S,T}+\alpha_{S-1, T} P(Y∣X)=αS,T+αS−1,T
下面直接給出dp的狀態(tài)轉(zhuǎn)換公式， p t ( z s ∣ X ) p_t(z_s|X) pt(zs∣X) 表示 t t t 時(shí)刻第 s s s 個(gè)字符的概率：
α s , t = ( α s , t − 1 + α s − 1 , t − 1 ) × p t ( z s ∣ X ) \alpha_{s,t}=(\alpha_{s,t-1}+\alpha_{s-1, t-1})\times p_t(z_s|X) αs,t=(αs,t−1+αs−1,t−1)×pt(zs∣X)， ( a , ϵ , a ) (a,\epsilon, a) (a,ϵ,a)或者 ( ϵ , a , ϵ ) (\epsilon,a,\epsilon) (ϵ,a,ϵ) 模式
α s , t = ( α s − 2 , t − 1 + α s − 1 , t − 1 + α s , t − 1 ) × p t ( z s ∣ X ) \alpha_{s,t}=(\alpha_{s-2,t-1}+\alpha_{s-1,t-1}+\alpha_{s,t-1})\times p_t(z_s|X) αs,t=(αs−2,t−1+αs−1,t−1+αs,t−1)×pt(zs∣X)，其他情況
解碼
解碼問題就是已經(jīng)有訓(xùn)練好的模型，需要通過輸入序列推測(cè)出最優(yōu)的token序列，實(shí)際上就是解決 Y ∗ = a r g m a x Y P ( Y ∣ X ) Y^*=\underset{Y}{argmax}\space P(Y|X) Y∗=Yargmax P(Y∣X) 這個(gè)問題，那么能想到最直接的方法就是取每一幀概率分?jǐn)?shù)最高的token，連接起來去掉 ϵ \epsilon ϵ 組成輸出序列，也就是貪婪解碼：
常用的算法是改進(jìn)版的beam search，常規(guī)的beam search是在每一幀都會(huì)保存概率分?jǐn)?shù)最大的前幾個(gè)路徑并舍棄其他的，最后會(huì)給出最優(yōu)的 b e a m beam beam 個(gè)路徑，在此基礎(chǔ)上，我們?cè)诼窂剿阉鞯倪^程中，需要對(duì)能映射到相同輸出的alignment進(jìn)行合并，合并之后再進(jìn)行beam的枝剪。
由于語言模型分?jǐn)?shù)和CTC的條件概率分?jǐn)?shù)相互獨(dú)立，因此最終的解碼序列可以寫成
Y ∗ = a r g m a x Y P ( Y ∣ X ) × P ( Y ) α Y^*=\underset{Y}{argmax} \space P(Y|X)\times P(Y)^\alpha Y∗=Yargmax P(Y∣X)×P(Y)α， P ( Y ) P(Y) P(Y)表示語言模型的概率分?jǐn)?shù)，可以是bigram也可以是3gram，以bigram為例的話，如果當(dāng)前時(shí)刻序列是 ( a , b , c ) (a,b,c) (a,b,c)，計(jì)算下一幀跳到 d d d 的概率分?jǐn)?shù)時(shí)，不僅要考慮下一時(shí)刻的token概率分布，還要考慮訓(xùn)練文本中 ( c , d ) (c,d) (c,d) 出現(xiàn)的頻次，即 c o u n t ( c , d ) / c o u n t ( c , ∗ ) count(c,d) / count(c,*) count(c,d)/count(c,∗)，將這個(gè)概率和 d d d出現(xiàn)的概率相乘才是最終的概率分?jǐn)?shù)， α \alpha α 是語言模型因子，需要fine tuning。
