本來想把關(guān)于CTC的所有東西都寫在一篇文章独榴，但后面發(fā)現(xiàn)內(nèi)容太多斋陪，遂拆分成如下幾個(gè)部分：
CTC算法詳解之訓(xùn)練篇
CTC算法詳解之測(cè)試篇
CTC算法詳解之總結(jié)展望篇（待更）
引言
CTC鼻祖論文[1]主要討論了CTC網(wǎng)絡(luò)的訓(xùn)練可微問題迹冤，而對(duì)于怎么測(cè)試， 其本質(zhì)是從網(wǎng)絡(luò)的輸出分布中搜索得到最優(yōu)序列的問題屏轰，有非常多經(jīng)典的算法能夠完成CTC解碼工作公荧，除了[1]中提供的Best path decoding和Prefix search decoding外，還有Beam Search Decoding微渠，Token Passing等等搭幻。本文先講解[1]中描述的兩種解碼算法，我有時(shí)間了再添加Beam Search Decoding逞盆，Token Passing檀蹋。
譯碼過程就是使輸出標(biāo)簽概率最大化的過程，即云芦，其中標(biāo)簽
的概率定義成所有正確路徑的概率和：
俯逾，
是
的逆映射（
的定義見《訓(xùn)練篇》）贸桶，表示所有能映射成
的路徑。因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=B" alt="B" mathimg="1">是many-to-one映射的緣故桌肴，故計(jì)算
要涉及到很多路徑
窮舉所有的路徑是非常困難的皇筛，其空間復(fù)雜度為
，
為字典大小坠七，
為路徑長(zhǎng)度水醋，實(shí)際操作中，我們會(huì)通過某些策略來縮小求解范圍灼捂，加快計(jì)算离例。
1.最優(yōu)路徑解碼（best path decoding）
這種解碼方式是最快速的。best path decoding基于一個(gè)假設(shè)：概率最大的路徑和概率最大的標(biāo)簽
是一一對(duì)應(yīng)的悉稠，把映射
退化成了one-to-one映射宫蛆，那么有
，
的猛。
best path decoding的實(shí)現(xiàn)非常簡(jiǎn)單耀盗，把每個(gè)時(shí)刻概率最大的類別取出來，拼接得到路徑卦尊，最后通過移除連續(xù)重復(fù)符號(hào)和blank得到標(biāo)簽叛拷。《訓(xùn)練篇》的圖2即為這種解碼方式岂却。
然而best path decoding的前提不一定正確忿薇，比如有1條概率為0.1的路徑可得到標(biāo)簽A，但有10條概率為0.05的路徑可得到概率B躏哩，顯然標(biāo)簽B比標(biāo)簽A更可信署浩。所以這種方法是通過犧牲精度來?yè)Q取速度，但實(shí)際應(yīng)用中這種解碼方式因?yàn)閷?shí)現(xiàn)簡(jiǎn)單扫尺，速度快筋栋，并且精度能夠接受，[1]表明正驻，在精度上bset path decoding解碼僅差Prefix Search Decoding1%弊攘，所以被廣泛使用。
2.Prefix Search Decoding
比起搜索所有可能的標(biāo)簽姑曙，Prefix Search Decoding只搜索最大概率的的前綴襟交，大大減少了搜索空間，然后每一步迭代都拓展這個(gè)前綴直到找出最優(yōu)標(biāo)簽伤靠。
搜索過程如下：
- 1.每一次迭代中婿着，我們有一個(gè)前綴集合，每個(gè)前綴對(duì)應(yīng)一個(gè)概率。這個(gè)集合的初態(tài)僅包含一個(gè)空字符串竟宋，其概率為1。
2.從前綴集合中找出概率最大的前綴形纺。對(duì)這個(gè)前綴我們可以選擇拓展一個(gè)新符號(hào)或是將其作為最終的解碼標(biāo)簽丘侠。
3.計(jì)算上一步中每種選擇的概率。
4.如果將某前綴作為解碼標(biāo)簽的概率大于該前綴的任何拓展概率逐样，則找到了最優(yōu)解碼標(biāo)簽蜗字。
5.如果上一步不成立，則把拓展后的前綴作為新的前綴脂新，替換老前綴挪捕，并更新前綴概率。
6.重復(fù)2~5争便，直到找出最優(yōu)解碼標(biāo)簽级零。
[1]提供了算法的直觀示意圖：
如果允許的譯碼時(shí)常足夠大，前綴搜索是能夠找出真正的最佳結(jié)果的滞乙，但是算法的搜索空間隨著T的增大是指數(shù)型增長(zhǎng)的奏纪，為了解決這個(gè)問題，[1]使用了一種啟發(fā)式策略來加速計(jì)算斩启，把CTC的輸出根據(jù)blank符號(hào)分割成數(shù)個(gè)片段（chunk）序调，每個(gè)片斷獨(dú)立地使用prefix search decoding，最后再拼接起來兔簇。
目前為止我們只是粗略地討論了算法流程发绢，并沒有講到怎么計(jì)算步驟3中的概率，而這垄琐，正好是算法的核心與難點(diǎn)边酒。為計(jì)算前綴相關(guān)的概率，我們要定義一些變量此虑，然后通過動(dòng)態(tài)規(guī)劃算法來計(jì)算甚纲。用表示
時(shí)刻譯碼得到前綴
并且最后一個(gè)符號(hào)為非空的概率（n表示non-blank}），用
表示
時(shí)刻譯碼得到前綴
并且最后一個(gè)符號(hào)為空的概率（b表示blank）朦前。注意介杆，前綴
是由路徑
經(jīng)過去重并且移除
符號(hào)得到的，所以
中并不包含
韭寸，這里是指
對(duì)應(yīng)的路徑
的最后一個(gè)符號(hào)春哨。
所以前綴作為標(biāo)簽的概率為（終止概率，比如圖1第2行數(shù)字中的0.1）：
其中為輸入序列的長(zhǎng)度（最大譯碼長(zhǎng)度）恩伺。接下來我們要定義前綴
的后綴為非空字符串的概率為（拓展概率赴背，比如圖1第2行數(shù)字中的0.7和0.2）：
在定義公式（1）和（2）后我們就可以討論怎么計(jì)算前面說的概率了。
我們來模擬譯碼的過程。首先將前綴集合初始化為凰荚，集合中只包含一個(gè)空字符串燃观，用
表示譯碼過程中得到的最優(yōu)標(biāo)簽，
表示當(dāng)前譯碼時(shí)刻的前綴便瑟，
和
都初始化成空字符串缆毁。選取概率最大的一個(gè)前綴
，對(duì)其拓展一個(gè)字符得到
到涂，
可能是字典中的任意一個(gè)符號(hào)脊框。對(duì)于每一個(gè)可能的
，我們都要計(jì)算新序列作為整個(gè)標(biāo)簽的概率和新序列繼續(xù)作為前綴的概率践啄，即
和
浇雹。整個(gè)算法的核心就是通過動(dòng)態(tài)規(guī)劃來計(jì)算這兩個(gè)式子。
公式（1）的計(jì)算
容易有：
表示t時(shí)刻得到某個(gè)非空字符的概率屿讽。
公式（4）說明有兩種方式可以在時(shí)刻t得到新字符：
如果前綴
已經(jīng)是以
結(jié)尾的話昭灵，需要
時(shí)刻序列
以
結(jié)尾；
否在聂儒，上一時(shí)刻的前綴應(yīng)以非
公式（3）的第一行表示，當(dāng)路徑不以結(jié)尾時(shí)非春，我們不可能得到一個(gè)空的前綴柱徙，因?yàn)槁窂降哪┪惨呀?jīng)包含了一個(gè)non-blank符號(hào)，譯碼得到的整個(gè)前綴也肯定非空奇昙。
公式（3）的第二行表示护侮，必須是連續(xù)的個(gè)
才可能譯碼得空前綴，我們只需將在將每個(gè)時(shí)刻的
概率相乘储耐。
接下來討論的初態(tài)：
和
羊初。如果在第一個(gè)時(shí)刻輸出
符號(hào)，就不存在前綴
了什湘，所以
為不可能事件长赞；而
很容易通過CTC的譯碼規(guī)則求出，為第1個(gè)時(shí)刻
的對(duì)應(yīng)符號(hào)的激活概率：
特別的闽撤，對(duì)于空字符串前綴：
在知道遞推公式（3）和初態(tài)（5）的情況下得哆，我們就可以計(jì)算任意了，然后根據(jù)公式（1）計(jì)算前綴作為標(biāo)簽的概率（終止概率）哟旗。
公式（2）的計(jì)算
我們通過間接方式來計(jì)算拓展概率贩据。拓展概率以=前綴概率-終止概率：
比如圖2第2行有(0.7+0.2)=1-0.1
公式（8）中的拓展概率可以被拆解成1~T時(shí)刻的符號(hào)概率之和：
迭代
現(xiàn)在我們能夠計(jì)算某個(gè)前綴的拓展概率和終止概率了栋操，每一步迭代如下：
- 如果新前綴
作為標(biāo)簽的概率比最佳標(biāo)簽
的概率要高，即
饱亮，則用
- 如果
，則把
中近上。
在完成前綴相關(guān)的概率計(jì)算后：
- 把p從前綴集合中刪除*蠕啄；
- 根據(jù)最大的
找到新前綴，替換老前綴戈锻。
一直迭代下去，知道找不出概率大于最佳標(biāo)簽的前綴（）和媳，此時(shí)的
即為最優(yōu)解碼標(biāo)簽格遭。
整個(gè)算法可用如下偽代碼來描述，圖片摘自[4]：
參考資料
[1] Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks
[2] CTC Algorithm Explained Part 2：Decoding the Network（CTC算法詳解之解碼篇）
[3]Speech Recognition with Neural Networks
[4]Supervised Sequence Labeling, Alex Gravessuoyi
