CTC算法詳解

和其它文章初衷一樣潭千，網(wǎng)上解釋很多，但是講的不是很明白，在看完幾篇參考博客后特此記錄

簡介

先拿語音識別任務來說本砰，如果現(xiàn)在有一個包含剪輯語音和對應的文本，我們不知道如何將語音片段與文本進行對應钢悲，這樣對于訓練一個語音識別器增加了難度点额。

為了解決上述問題，我們可以先制定一個規(guī)則莺琳，例如“一個字符對于是個語言片段輸入”还棱。對于不同的人來說，他們說話的語速也不一樣惭等，這樣導致了上述的定義規(guī)則不可行珍手。另一個解決辦法，手動對齊每個字符在音頻中的位置辞做。這種方法對于我們訓練模型非常有效琳要，但是不可否認的是這種做法非常耗時。

上面只是拿語音識別來舉例秤茅，其實在其他一些識別任務中也會出現(xiàn)這個問題稚补，例如手寫字符識別，上面兩例如下圖所示

1.png

Connectionist Temporal Classification (CTC)正適合這種不知道輸入輸出是否對齊的情況使用的算法框喳，所以CTC適合語音識別和手寫字符識別的任務

為了方便下面的描述课幕，我們做如下定義，輸入(如音頻信號)用符號序列 $X=[x_{1},x_{2},...,x_{T}]$ 表示帖努，對應的輸出(如對應的標注文本)用符號序列 $Y=[y_{1},y_{2},...,y_{U}]$ 撰豺，為了方便訓練這些數(shù)據(jù)我們希望能夠找到輸入 $X$ 與輸出 $Y$ 之間精確的映射關系。

在使用有監(jiān)督學習算法訓練模型之前拼余，有幾個難點：

$X$ 和 $Y$ 都是變長的
$X$ 和 $Y$ 的長度比也是變化的
$X$ 和 $Y$ 相應的元素之間沒有嚴格的對齊(即 $x_{t}$ 與 $y_{u}$ 不一定對齊)

使用CTC算法能克服上述問題污桦。到這里可以知道CTC就是可以解決輸入輸出對應問題的一種算法。

這里我們首先需要明確的是匙监，還拿語音識別來說凡橱，現(xiàn)在使用的CTC常用的場景是RNN后接CTC算法小作，RNN模型輸入是個個音頻片段，輸出個數(shù)與輸入的維度一樣稼钩，有T個音頻片段顾稀，就輸出T個維度的概率向量，每個向量又由字典個數(shù)的概率組成坝撑。例如網(wǎng)絡輸入音頻個數(shù)定為T静秆，字典中不同字的個數(shù)為N，那么RNN輸出的維度為 $T\times N$ 巡李。根據(jù)這個概率輸出分布抚笔，我們就能得到最可能的輸出結果。在接下來的討論中可以把RNN+CTC看成一個整體侨拦，當然也可以將RNN替換成其他的提取特征算法

損失函數(shù)的定義：對于給定的輸入 $X$ 殊橙，我們訓練模型希望最大化 $Y$ 的后驗概率 $P(Y|X)$ , $P(Y|X)$ 應該是可導的，這樣我們就能利用梯度下降訓練模型了狱从。

測試階段：當我們已經訓練好一個模型后膨蛮，輸入 $X$ ，我們希望輸出 $Y$ 的條件概率最高即 $Y*=\mathop{\arg\max}_{Y}p(Y|X)$ 季研，而且我們希望盡量快速的得到 $Y*$ 值敞葛，利用CTC我們能在低投入情況下迅速找到一個近似的輸出。

算法

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

對齊

CTC算法并不要求輸入輸出是嚴格對齊的款慨。但是為了方便訓練模型我們需要一個將輸入輸出對齊的映射關系，知道對齊方式才能更好的理解之后損失函數(shù)的計算方法和測試使用的計算方法谬莹。

為了更好的理解CTC的對齊方法檩奠，先舉個簡單的對齊方法。假設對于一段音頻附帽，我們希望的輸出是 $Y=[c,a,t]$ 這個序列埠戳，一種將輸入輸出進行對齊的方式如下圖所示气忠，先將每個輸入對應一個輸出字符给郊，然后將重復的字符刪除。

2.png

上述對齊方式有兩個問題：

通常這種對齊方式是不合理的拷获。比如在語音識別任務中喳钟，有些音頻片可能是無聲的屁使，這時候應該是沒有字符輸出的
對于一些本應含有重復字符的輸出在岂，這種對齊方式沒法得到準確的輸出。例如輸出對齊的結果為 $[h,h,e,l,l,l,o]$ 蛮寂，通過去重操作后得到的不是“hello”而是“helo”

為了解決上述問題蔽午，CTC算法引入的一個新的占位符用于輸出對齊的結果。這個占位符稱為空白占位符酬蹋，通常使用符號 $\epsilon$ 及老，這個符號在對齊結果中輸出，但是在最后的去重操作會將所有的 $\epsilon$ 刪除得到最終的輸出范抓。利用這個占位符骄恶，可以將輸入與輸出有了非常合理的對應關系，如下圖所示

3.png

在這個映射方式中尉咕，如果在標定文本中有重復的字符叠蝇，對齊過程中會在兩個重復的字符當中插入 $\epsilon$ 占位符。利用這個規(guī)則年缎，上面的“hello”就不會變成“helo”了悔捶。

回到上面 $Y=[c,a,t]$ 這個例子來，下圖中有幾個示列說明有效的對齊方式和無效的對齊方式单芜，在無效的對齊方式中舉了三種例子蜕该，占位符插入位置不對導致的輸出不對，輸出長度與輸入不對齊洲鸠，輸出缺少字符a

4.png

CTC算法的對齊方式有下列屬性：

輸入與輸出的對齊方式是單調的堂淡，即如果輸入下一輸入片段時輸出會保持不變或者也會移動到下一個時間片段
輸入與輸出是多對一的關系
輸出的長度小于等于輸入

損失函數(shù)

這里要明確一點，對于一個標定好的音頻片段扒腕，訓練該片段時绢淀，我們希望的輸出就是標定的文本，如下圖所示瘾腰，音頻說的一個hello皆的，RNN或者其他模型輸出的是相同數(shù)量的向量，向量里是每個字母的概率

5.png

對于一對輸入輸出 $(X,Y)$ 來說蹋盆，CTC的目標是將下式概率最大化
$p(Y|X)=\sum_{A\in\mathcal{A}_{X,Y}} \prod^{T}_{t=1}p_{t}(a_{t}|X)$
解釋一下费薄，對于RNN+CTC模型來說，RNN輸出的就是 $p_{t}(a_{t}|X)$ 概率栖雾，t表示的是RNN里面的時間的概念楞抡。乘法表示一條路徑的所有字符概率相乘，加法表示多條路徑析藕。因為上面說過CTC對齊輸入輸出是多對一的召廷，例如 $he\epsilon l\epsilon lo\epsilon$ 與 $hee\epsilon l\epsilon lo$ 對應的都是“hello”，這就是輸出的其中兩條路徑，要將所有的路徑相加才是輸出的條件概率

但是對于一個輸出柱恤，路徑會非常的多数初，這樣直接計算概率是不現(xiàn)實的，CTC算法采用動態(tài)規(guī)劃的思想來求解輸出的條件概率梗顺，如下圖所示泡孩，該圖想說明的是通過動態(tài)規(guī)劃來進行路徑的合并(看不懂也沒關系，下面有詳細的解釋)

6.png

假設我們現(xiàn)在有輸入音頻 $X$ 對應的標定輸出 $Y$ 為單詞“ZOO”寺谤，為了方便解釋下面動態(tài)規(guī)劃的思想仑鸥，現(xiàn)在每個字符之間還有字符串的首位插入空白占位符 $\epsilon$ ，得到下面結果
$Z=\{\epsilon,Z,\epsilon,O,\epsilon,O,\epsilon\}$
為了便于說明变屁，先定義好下圖的橫縱坐標軸的含義眼俊，橫軸是 $X$ 的時間片單位為t，縱軸為 $Z$ 序列單位為s粟关。根據(jù)CTC的對齊方式的三個特征疮胖，輸入有9個時間片，標簽內容是“ZOO”闷板， $P(Y|X)$ 的所有可能的合法路徑如下圖

7.png

$\alpha$ 表示對齊結果合并后(如圖3.png)節(jié)點的概率澎灸。 $\alpha_{s,t}$ 表示上圖中坐標為(s,t)節(jié)點的概率，該點的概率計算分為下面兩種情況：
Case 1：
1）如果 $\alpha_{s,t}=\epsilon$ 遮晚，則 $\alpha_{s,t}$ 只能由前一個字符 $\alpha_{s-1,t-1}$ 或者本身 $\alpha_{s,t-1}$ 得到
2）如果 $\alpha_{s,t}$ 不等于 $\epsilon$ 性昭，但是 $\alpha_{s,t}$ 為連續(xù)字符的第二個，即 $\alpha_{s}=\alpha_{s-2}$ ( $\alpha_{s-1}=\epsilon$ )县遣，則 $\alpha_{s,t}$ 只能由一個空白符 $\alpha_{s-1,t-1}$ 或者其本身 $\alpha_{s,t-1}$ 得到糜颠，而不能由前一個字符得到。

上述兩種情況中萧求， $\alpha_{s,t}$ 可以由下式算出其兴，其中 $p_{t}(z_{s}|X)$ 表示在時刻t輸出字符 $z_{s}$ 的概率。
$\alpha_{s,t}=(\alpha(s,t-1)+\alpha(s-1,t-1))\cdot p_{t}(z_{s}|X)$

Case 2：
如果 $\alpha_{s,t}$ 不等于 $\epsilon$ 夸政，則 $\alpha_{s,t}$ 可以由 $\alpha_{s,t-1}$ 忌警， $\alpha_{s-1,t-1}$ 以及 $\alpha_{s-2,t-1}$ 得來，可以表示為
$\alpha_{s,t}=(\alpha(s,t-1)+\alpha(s-1,t-1)+\alpha(s-2,t-1))\cdot p_{t}(z_{s}|X)$

從圖7中可以看到合法路徑由兩個起始點秒梳，輸出兩個終止點，最后輸出的條件概率為兩個終止點輸出概率的和箕速。使用這種計算方法就能高效的計算損失函數(shù)酪碘，下一步的工作表示計算梯度用于訓練模型。由于P(Y|X)的計算只涉及加法和乘法盐茎，因此是可導的兴垦。對于訓練集 $\mathcal{D}$ ，模型優(yōu)化的目標是最小化負對數(shù)似然函數(shù)
$\sum_{(X,Y)\in \mathcal{D}}-logp(Y|X)$

預測

當我們訓練好一個模型后，我們輸入 $X$ 探越，我們的目的是計算下式得到輸出
$Y*=\mathop{\arg\max}_{Y}p(Y|X)$

1.一種方法是貪婪算法狡赐，取RNN每次輸出概率最大的節(jié)點，計算方式如下
$A*=\mathop{\arg\max}_{A} \prod^{T}_{t=1}p_{t}(a_{t}|X)$
然后通過去重得到輸出結果钦幔。

通常這種啟發(fā)式的算法很有效枕屉，但是這種方法忽略了一個輸出可能對應多個對齊結果。例如 $[a,a,\epsilon]$ 和 $[a,a,a]$ 各自的概率均小于 $[b,b,b]$ 的概率鲤氢，但是他們相加的概率比 $[b,b,b]$ 概率高搀擂。簡單的啟發(fā)是算法得到結果為 $Y=[b]$ ，但是結果為 $Y=[a]$ 更為合理卷玉∩谒蹋考慮到這點第二種方式變的更為合理

2.第二種算法是Beam search的一種變形
先來說一下Beam search算法，該算法有個參數(shù)叫做寬度相种，假設寬度設為3威恼，在RNN的輸出中，該算法每個時間t輸出時寝并，不同于貪婪算法只找最高的箫措，而是找最高的三個概率作為下一次的輸入，依次迭代食茎，如下圖所示蒂破，每次t時間都是基于t-1輸出的最高三個查找當前概率最高的三個。(這里也可以看出别渔，當寬度設置為1時就是貪婪算法)

8.png

因為我們這里想要結合多個對齊能夠映射到同一輸出的這種情況附迷，這時每次t時間的輸出為去重后以及移除 $\epsilon$ 的結果，具體如下圖所示

9.png

當輸出的前綴字符串遇上重復字符時哎媚，可以映射到兩個輸出喇伯，如圖9所示，當T=3時拨与，前綴包含a稻据，遇上新的a，則[a]和[a,a]兩個輸出都是有效的买喧。

當我們將[a]擴展為[a, a]時捻悯，我們只需統(tǒng)計之前以空白標記 $\epsilon$ 結尾的所有路徑的概率（位于字符中間的?也要統(tǒng)計）。同樣的淤毛，如果是擴展到[a]今缚，那我們計算的就是不以 $\epsilon$ 結尾的所有路徑概率。所以每次的輸出只需要記錄空白標記 $\epsilon$ 結尾的所有路徑的概率和不以 $\epsilon$ 結尾的所有路徑概率來進行下一次的概率計算低淡。這個算法的實現(xiàn)姓言，Awni Hannun給出了示例

CTC的特征

條件獨立：CTC的一個非常不合理的假設是其假設每個時間片都是相互獨立的瞬项，這是一個非常不好的假設。在OCR或者語音識別中何荚，各個時間片之間是含有一些語義信息的囱淋，所以如果能夠在CTC中加入語言模型的話效果應該會有提升。
單調對齊：CTC的另外一個約束是輸入 $X$ 與輸出 $Y$ 之間的單調對齊餐塘，在OCR和語音識別中妥衣，這種約束是成立的。但是在一些場景中例如機器翻譯唠倦，這個約束便無效了称鳞。
多對一映射：CTC的又一個約束是輸入序列 $X$ 的長度大于標簽數(shù)據(jù) $Y$ 的長度，但是對于 $X$ 的長度大于 $Y$ 的長度的場景稠鼻，CTC便失效了冈止。

參考

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

歡迎加入OCR交流群：785515057(此群已滿)
歡迎加入OCR交流群2：826714963

最后編輯于：2019.12.06 14:20:53

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市候齿，隨后出現(xiàn)的幾起案子熙暴，更是在濱河造成了極大的恐慌，老刑警劉巖慌盯，帶你破解...
沈念sama閱讀 217,542評論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件周霉，死亡現(xiàn)場離奇詭異，居然都是意外死亡亚皂，警方通過查閱死者的電腦和手機俱箱，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,822評論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來灭必，“玉大人狞谱，你說我怎么就攤上這事〗欤” “怎么了跟衅？”我有些...
開封第一講書人閱讀 163,912評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長播歼。經常有香客問我伶跷，道長，這世上最難降的妖魔是什么秘狞？我笑而不...
開封第一講書人閱讀 58,449評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任叭莫，我火速辦了婚禮，結果婚禮上烁试，老公的妹妹穿的比我還像新娘雇初。我一直安慰自己，他們只是感情好廓潜，可當我...
茶點故事閱讀 67,500評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著，像睡著了一般辩蛋。火紅的嫁衣襯著肌膚如雪呻畸。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,370評論 1贊 302
城市分裂傳說
那天悼院，我揣著相機與錄音伤为，去河邊找鬼。笑死据途，一個胖子當著我的面吹牛绞愚，可吹牛的內容都是我干的。我是一名探鬼主播颖医，決...
沈念sama閱讀 40,193評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼位衩，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了熔萧？” 一聲冷哼從身側響起糖驴，我...
開封第一講書人閱讀 39,074評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎佛致，沒想到半個月后贮缕，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經...
沈念sama閱讀 45,505評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡俺榆，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 37,722評論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年感昼，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片罐脊。...
茶點故事閱讀 39,841評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡定嗓，死狀恐怖，靈堂內的尸體忽然破棺而出爹殊，到底是詐尸還是另有隱情蜕乡，我是刑警寧澤，帶...
沈念sama閱讀 35,569評論 5贊 345
?日本核電站爆炸內幕
正文年R本政府宣布梗夸，位于F島的核電站层玲，受9級特大地震影響，放射性物質發(fā)生泄漏反症。R本人自食惡果不足惜辛块，卻給世界環(huán)境...
茶點故事閱讀 41,168評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望铅碍。院中可真熱鬧润绵，春花似錦、人聲如沸胞谈。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,783評論 0贊 22
一樁弒父案憨愉，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至卿捎，卻和暖如春配紫，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背午阵。一陣腳步聲響...
開封第一講書人閱讀 32,918評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工躺孝，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人底桂。一個月前我還...
沈念sama閱讀 47,962評論 2贊 370
代替公主和親
正文我出身青樓植袍，卻偏偏與公主長得像，于是被迫代替她去往敵國和親籽懦。傳聞我的和親對象是個殘疾皇子于个，可洞房花燭夜當晚...
茶點故事閱讀 44,781評論 2贊 354

CTC算法詳解

簡介

算法

對齊

損失函數(shù)

預測

CTC的特征

參考

推薦閱讀更多精彩內容