CTC實現——compute ctc loss（1）

本文收錄在無痛的機器學習第二季目錄。

上一次我們介紹了關於CTC的一些基本問題，下面我們還是落到實處，來介紹一個經典的CTC實現程式碼——來自百度的warp-ctc。這次百度沒有作惡……

CTC：前向計算例子

這裡我們直接使用warp-ctc中的變數進行分析。我們定義T為RNN輸出的結果的維數，這個問題的最終輸出維度為alphabet_size。而ground_truth的維數為L。也就是說，RNN輸出的結果為alphabet_size*T的結果，我們要將這個結果和1*L這個向量進行對比，求出最終的Loss。

我們要一步一步地揭開這個演算法的細節……當然這個演算法的實現程式碼有點晦澀……

我們的第一步要順著test_cpu。cpp的路線來分析程式碼。第一步我們就是要解析small_test（）中的內容。也就是做前向計算，計算對於RNN結果來說，對應最終的ground_truth——t的label的機率。

這個計算過程可以用動態規劃的演算法求解。我們可以用一個變數來表示動態規劃的中間過程，它就是：

：表示在RNN計算的時間T時刻，這一時刻對應的ground_truth的label為第i個下標的值t［i］的機率。

這樣的表示有點抽象，我們用一個實際的例子來講解：

RNN結果：

，這裡的每一個變數都對應一個列向量。

ground_truth：

那麼

表示

的結果對應著

的機率，當然與此同時，前面的結果也都合理地對應完成。

從上面的結果我們可以看出，如果

的結果對應著

，那麼

的結果也必然對應著

。所以前面的結果是確定的。然而對於其他的一些情況來說，我們的轉換存在著一定的不確定性。

CTC：前向計算具體過程

我們還是按照上面的例子進行計算，我們把剛才的例子搬過來：

RNN結果：

，這裡的每一個變數都對應一個列向量。

ground_truth：

alphabet：

按照上面介紹的計算方法，第一步我們先做ground_truth的狀態擴充套件，於是我們就把長度從3擴充套件到了7，現在的ground_truth變成了：

我們的RNN結果長度為4，也就是說我們會從上面的7個ground_truth狀態中進行轉移，並最終轉移到最終狀態。理論上利用動態規劃的演算法，我們需要計算4*7=28箇中間結果。好了，下面我們用

表示RNN的第T時刻狀態為ground_truth中是第i個位置的機率。

那麼我們就開始計算了：

T=1時，我們只能選擇

和blank，所以這一輪我們終結狀態只可能落在0和1上。所以第一輪變成了：

T=2時，我們可以繼續選擇

，我們同時也可以選擇

，還可以選擇

和

之間的blank，所以我們可以進一步關注這三個位置的機率，於是我們將其他的位置的機率設為0。

T=3時，留給我們的時間已經不多了，我們還剩2步，要走完整個旅程，我們只能選擇

，

以及它們之間的空格。於是乎我們關心的位置又發生了變化：

是不是有點看暈了？沒關係，因為還剩最後一步了。下面是最後一步，因為最後一步我們必須要到

以及它後面的空格了，所以我們的機率最終計算也就變成了：

好吧，最終的結果我們求出來了，實際上這就是透過時間的推移不斷迭代求解出來的。關於迭代求解的公式這裡就不再贅述了。我們直接來看一張圖：

（注：T=2時的第一個紅色方框應該有一條線連線T=3的第一個紅色方框，感謝@WXB506 指出）

於是乎我們從這個計算過程中發現一些問題：

首先是一個相對簡單的問題，我們看到在計算過程中我們發現了大量的連乘。由於每一個數字都是浮點數，那麼這樣連乘下去，最終數字有可能非常小而導致underflow。所以我們要將這個計算過程轉到對數域上。這樣我們就將其中的乘法轉變成了加法。但是原本就是加法的計算呢？比方說我們現在計算了loga和logb，我們如何計算log（a+b）呢，這裡老司機給出瞭解決方案，我們假設兩個數中a>b，那麼有

這樣我們就利用了loga和logb計算出了log（a+b）來。

另外一個問題就是，我們發現在剛才的計算過程當中，對於每一個時間段，我們實際上並不需要計算每一個ground-truth位置的機率資訊，實際上只要計算滿足某個條件的某一部分就可以了。所以我們有沒有希望在計算前就規劃好這條路經，以保證我們只計算最相關的那些值呢？

如何控制計算的數量？

不得不說，這一部分warp-ctc寫得實在有點晦澀，當然也可能是我在這方面的理解比較渣。我們這裡主要關注兩個部分——一個是資料的準備，一個是最終的資料的使用。

在介紹資料準備之前，我們先簡單說一下這部分計算的大概思路。我們用兩個變數start和end表示我們需要計算的狀態的起止點，在每一個時間點，我們要更新start和end這兩個變數。然後我們更新start和end之間的機率資訊。這裡我們先要考慮一個問題，start和end的更新有什麼規律？

為了簡化思考，我們先假設ground_truth中沒有重複的label，我們的大腦瞬間得到了解放。好了，下面我們就要給出程式碼中的兩個變數——

T：表示RNN結果中的維度

S/2：ground_truth的維度（S表示了擴充套件blank之後的維度）

基本上具備一點常識，我們就可以知道T>=S/2。什麼？你覺得有可能出現T

好了，既然接受了上面的事實，那麼我們就來舉幾個例子看看：

我們假設T=3，S/2=3，那麼說白了，它們之間的對應關係是一一對應，說白了這就和blank位置沒啥關係了。在T=1時，我們要轉移到第一個結果，T=2，我們要轉移到第二個結果……

那麼我們還有別的情況麼？下回更精彩。

廣告時間

更多精彩盡在《深度學習輕鬆學：核心演算法與視覺實踐》！