CTC演算法詳解

??以語音識別為例，如果現在有一個包含剪輯語音以及相應文本的資料集，如何將語音片段與文本字符一一對應，是訓練語音識別器面臨的首要問題，為了解決上述問題，我們制定簡單的規則，如每個字符對應十個輸入，考慮到不同的人說話的語速有區別，這樣的規則并不具備泛化能力，當然，我們也可以手動的對齊每個字符在音頻中的位置，這種方法得到的資料對于模型的訓練非常友好，但是這種做法非常耗費人力物力，這個問題同樣也存在于其他序列識別的任務中，如圖片中的文本識別，

??CTC（Connectionist Temporal Classification）正是這種不知道輸入輸出是否對齊的情況下使用的演算法，所以CTC適合語音識別和文本識別的任務，

??為了方便下面的描述，我們做如下定義，輸入（如音頻信號）用序列\(X=[x_1,x_2,...,x_T]\)表示，對應的輸出（如對應的標注文本）用序列\(Y=[y_1,y_2,...,y_U]\)，為了方便訓練這些資料，我們希望能夠找到輸入\(X\)與輸出\(Y\)之間精確的映射關系，

??在使用有監督學習演算法訓練模型之前，有以下難點：
????1. 輸入\(X\)與輸出\(Y\)都是變長的；
????2. 輸入\(X\)與輸出\(Y\)的長度比值也是變化的；
????3. 輸入\(X\)與輸出\(Y\)相應的元素之間沒有嚴格的對齊（即\(x_t\)與\(y_u\)不一定對齊）；

??然而，CTC演算法能夠克服上述問題，對于給定的\(X\)，CTC可以為我們提供所有可能的\(Y\)的輸出分布，我們根據該分部既可以推斷出可能的輸出也可以評估給定輸出的概率，

??因此，CTC演算法需要同時具備損失函式計算與執行推理兩項功能：
損失函式：對于給定的輸入，我們希望訓練出的模型能夠最大化將輸入映射到正確輸出的概率，為此，我們需要有效的計算條件概率\(p(Y|X)\)，這個函式\(p(Y|X)\)應該是可導的，便于我們使用梯度下降訓練模型，
推理：當訓練好模型之后，我們需要使用模型根據給定的\(X\)得到可能的\(Y\)，這意味著解決
\(Y^*=argmax\, p(Y|X) \atop Y\)
理想情況是，\(Y^*\)可以被高效的找到，利用CTC演算法，我們能夠在投入較低的情況下找到近似的解決方案，

演算法
??CTC演算法對于輸入的\(X\)能給出非常多\(Y\)的條件概率輸出(可以想象RNN輸出概率分布矩陣，所以通過矩陣中元素的組合可以得到很多Y值作為最終輸出)，在計算輸出程序的一個關鍵問題就是CTC演算法如何將輸入和輸出進行對齊的，在接下來的部分中，我們先來看一下對齊的解決方法，然后介紹損失函式的計算方法和在測驗階段中找到合理輸出的方法，

對齊
??CTC演算法并不要求輸入輸出是嚴格對齊的，但是為了方便訓練模型我們需要一個將輸入輸出對齊的映射關系，知道對齊方式才能更好的理解之后損失函式的計算方法和測驗使用的計算方法，

??為了更好的理解CTC的對齊方法，先舉個簡單的對齊方法，假設對于一段音頻，我們希望的輸出是\(Y=[c,a,t]\)這個序列，一種將輸入輸出進行對齊的方式如下圖所示，先將每個輸入對應一個輸出字符，然后將重復的字符洗掉，

??然而，上述對齊方式明顯存在問題：
????1. 通常這種對齊方式是不合理的，比如在語音識別任務中，有些音頻片可能是無聲的，這時候應該是沒有字符輸出的；
????2. 對于一些本應含有重復字符的輸出，這種對齊方式沒法得到準確的輸出，例如輸出對齊的結果為\([h,h,e,l,l,l,o]\)，通過去重操作后得到的不是“hello”而是“helo”，

??為了解決上述問題，CTC 演算法引入了一個新的占位符用于輸出對齊結果，這個占位符稱為空白占位符，通常使用符號\(\epsilon\)，這個符號在對齊結果中輸出，但是在最后的去重操作會將所有的\(\epsilon\)洗掉得到最終的輸出，
??CTC允許對齊長度與輸入長度相同，我們允許在合并重復與洗掉\(\epsilon\)標記之后映射到\(Y\)的任何輸出序列結果，

??如果\(Y\)在一行中有兩個相同的字符，那么有效的對齊必須在它們之間存在一個\(\epsilon\)，有了這個規則，我們便能夠區分“hello”和“helo”對應的輸出序列，

??回到輸出為\([c,a,t]\)的示例，該示例的輸入長度為6，下面列舉了一些有效和無效的對齊，

??CTC的對齊方式有下列特性：
????1. \(X\)和\(Y\)之間合法的對齊是單調的，即如果前進到下一個輸入片段，輸出會保持不變或者也會移動到下一個片段；
????2. \(X\)和\(Y\)之間是多對一的關系，即一個或者多個輸入元素映射到一個單一的輸出元素；
????3. 基于特性2，所以輸出\(Y\)的長度不能大于輸入\(X\)的長度，

損失函式
??這里要明確一點，對于一個標定好的音頻片段，訓練該片段時，我們希望的輸出就是標定的文本，如下圖所示，音頻說的一個hello，RNN或者其他模型輸出的是相同長度的向量，每個向量對應一個輸入，向量里的每個元素代表該輸入對應每個字母的概率，

??對于一組\((X,Y)\)來說，CTC的目標是將下式概率最大化：

??對于RNN+CTC模型來說，RNN輸出的就是概率，t表示的是RNN里面的時間的概念，乘法表示一條路徑的所有字符概率相乘，加法表示多條路徑，因為上面說過CTC對齊輸入輸出是多對一的，例如\(he\epsilon l\epsilon lo\epsilon\)與\(hee\epsilon l\epsilon lo\)對應的都是“hello”，這就是輸出的其中兩條路徑，要將所有的路徑相加才是輸出的條件概率，但是對于一個輸出，路徑會非常的多，這樣直接計算概率是不現實的，CTC演算法采用動態規劃的思想來求解輸出的條件概率，如下圖所示，該圖想說明的是通過動態規劃來進行路徑的合并，其中的關鍵部分是如果兩個對齊在同一步驟達到相同的輸出，那么我們可以合并它們，

??因為我們允許在\(Y\)中的任何一個標記前面或者后面存在一個\(\epsilon\)，所以使用包含\(\epsilon\)的序列描述動態規劃演算法的程序更加清晰，我們使用序列

即\(Y\)的開頭、結尾以及每個字符之間都包含一個\(\epsilon\)，

??我們用\(\alpha\)表示在給定節點合并對齊結果后的概率，更進一步，\(\alpha _{s,t}\)表示在\(t\)個輸入序列后，得到\(Z\)的子序列\(Z_{1:s}\)的概率，我們將在最后一個時間片（最后一個輸入），計算最終的輸出概率\(P(Y|X)\)，只要我們知道前一個時間步的\(\alpha\)，就能夠計算\(\alpha _{s,t}\)，下面是計算節點合并對齊后概率的兩種情況，

case1：
??在這種情況中，我們不能跳過\(Z\)中當前符號的前一個符號\(z_{s-1}\)，第一種原因是，\(z_{s-1}\)是\(Y\)中的一個元素，如果跳過，最后得到的對齊序列無法合并為輸出\(Y\)，根據\(Z\)的生成規則，我們可以推斷出當前的符號\(z_{s}=\epsilon\)，第二種原因是，當前的符號\(z_{s}\)與上上個符號\(z_{s-2}\)屬于相同字符，如果跳過中間的\(z_{s-1}=\epsilon\)，那么合并對齊結果同樣得不到正確的輸出\(Y\)，

??為了確保不會跳過\(z_{s-1}\)，當前的節點\(\alpha _{s,t}\)只能經過節點\(\alpha _{s-1,t-1}\)或者節點\(\alpha _{s,t-1}\)到達，因此，這種case下，\(\alpha _{s,t}\)的計算公式如下圖所示，

case2：
??在這種情況中，我們允許跳過\(Z\)中當前符號的前一個符號\(z_{s-1}\)，這說明\(z_{s-1}=\epsilon\)且\(z_{s}!=z_{s-2}\)，即兩個不同的字符之間沒有包含\(\epsilon\)，這種case下，\(\alpha _{s,t}\)能夠經過節點\(\alpha _{s-1,t-1}\)、節點\(\alpha _{s,t-1}\)以及節點\(\alpha _{s-2,t-1}\)到達，可以得到\(\alpha _{s,t}\)的計算公式如下圖所示，

??以下是動態規劃演算法執行的計算示例，每個有效對齊在此圖中都有一條路徑，

??由于序列開頭和結尾的\(\epsilon\)是可選的，因此有兩個有效的起始節點和兩個有效的最終節點，完整的概率是兩個最終節點的概率總和，

??現在我們可以有效地計算損失函式，下一步是計算梯度并訓練模型， CTC 損失函式對于每個時間步的輸出概率是可微的，因為它只是它們的總和與乘積，鑒于此，我們可以分析計算損失函式相對于（未歸一化的）輸出概率的梯度，并從那里照常運行反向傳播，

??對于訓練集\(D\)，模型優化的目標是最小化負對數似然函式

而不是直接最大化概率，

推理
??訓練好模型后，我們希望對于給定的輸入\(X\)，能夠得到可能的輸出，也就是說，我們需要求解：

一種方法是啟發式演算法，在每個時間步獲取概率最大的輸出，這樣得到的對齊輸出是概率最大的：

根據\(A^*\)我們可以合并重復并洗掉\(\epsilon\)以獲取推理結果\(Y\)，

??對于許多應用程式，這種啟發式方法效果很好，尤其是當大部分概率分配給單個對齊時，然而，這種方法有時會錯過容易找到的概率更高的輸出，問題本質是，這種方法沒有考慮到單個輸出可以有許多對齊的事實，例如\([a,a,\epsilon]\)和\([a,a,a]\)各自的概率均小于\([b,b,b]\)的概率，但是他們相加的概率比[b,b,b]概率高，簡單的啟發式演算法得到結果為\(Y=[b]\)，但是結果為\(Y=[a]\)更為合理，考慮到這點的第二種方式更為合理，

??第二種方法是Bean Search演算法的一種變形，鑒于計算能力有限，變形后的Bean Search演算法并不需要找到最可能的輸出\(Y\)，這個方法有一個很好的特性，我們能夠通過付出更多的計算，來得到漸進更好的解決方案，

??常規的Beam Search在每個輸入步驟計算一組新的候選，新的候選集是通過使用所有可能的輸出字符擴展每個候選并僅保留最佳候選者而從前一組生成的，

??我們可以修改beam search來處理映射到同一輸出的多個對齊，在這種情況下，我們不是在bean中保留對齊串列，而是在合并重復并洗掉\(\epsilon\)字符后存盤輸出前綴，在搜索的每一步，我們都會根據映射到它的所有對齊方式為給定前綴累積概率分數，

??如果字符是重復的，則建議的擴展可以映射到兩個輸出前綴，這在上圖中的\(T=3\)處顯示，其中“\(a\)”被提議作為前綴\([a]\)的擴展，\([a]\)和\([a, a]\)都是此擴展的有效輸出，

??鑒于此，我們必須跟蹤beam中每個前綴的兩個概率，所有以\(\epsilon\)結尾的對齊的概率和所有不以\(\epsilon\)結尾的對齊的概率，當我們在修剪beam之前對每個步驟的候選進行排名時，我們將使用它們的綜合分數，

??變形Beam Search的實作不需要太多代碼，但是想要正確執行卻比較棘手，所以此處給出了Python版本的代碼示例，

??在某些問題中，例如語音識別，在輸出上加入語言模型可以顯著提高準確性，我們可以將語言模型作為推理問題的一個因素，關于這一點，已經脫離CTC本身，故不做深入討論，

CTC的特征

1. 條件獨立：CTC的一個非常不合理的假設是其假設每個時間片都是相互獨立的，這是一個非常不好的假設，在OCR或者語音識別中，各個時間片之間是含有一些語意資訊的，所以如果能夠在CTC中加入語言模型的話效果應該會有提升，
2. 單調對齊：CTC的另外一個約束是輸入\(X\)與輸出\(Y\)之間的單調對齊，在OCR和語音識別中，這種約束是成立的，但是在一些場景中例如機器翻譯，這個約束便無效了，
3. 多對一映射：CTC的又一個約束是輸入序列$$X的長度大于標簽資料 \(Y\)的長度，但是對于\(Y\)的長度大于\(X\)的長度的場景，CTC便失效了，

參考
[1] https://www.jianshu.com/p/0cca89f64987
[2] https://distill.pub/2017/ctc/
[3] https://gist.github.com/awni/56369a90d03953e370f3964c826ed4b0
[4] https://zhuanlan.zhihu.com/p/42719047
[5] https://www.zhihu.com/question/47642307
[6] https://www.cs.toronto.edu/~graves/icml_2006.pdf

標籤：其他

上一篇：微信公眾號實作助力、砍價活動的方法，微信活動怎么制作？

下一篇：HCIA學習筆記四：華為設備登錄資訊