Connectionist Temporal Classification 了解一下

05-25

語音識別問題

音頻片段可以看做一組幀序列

$x=left{ x_{1}...x_{T} ight}$

需要注意的是，在 $t$ 時刻對應的幀 $x_{t}$ 是一個向量，代表構成這一幀聲譜所需的全部權重。

$x_{t}=left[ x_{t,1}...x_{t,G} ight]^{T}$

我們定義輸入RNN網路的每個幀 $x_{t}$ 對應的輸出為 $y_{t}$ ，其中 $y_{t}$ 是預測所有字元(假設一共有K個)的概率分布

$y_{t}=left{ y_{t,1}...y_{t,K} ight}$

其中， $y_{t,k}=P(l_{t}=k)$ 表示在 $t$ 時刻預測字元為 $k$ 的概率，是softmax後的結果，後面推導反向傳播公式時會用到。

這時，我們可以定義語音片段 $x$ 輸入RNN網路後全部單元的輸出結果為 $y$ 。註：此時 $x 和y$ 是二維矩陣，每個列向量分別代表 $t$ 時刻的輸入和輸出。

$y=left{ y_{1}...y_{T} ight}$

那麼問題來了， $y$ 是每個時刻預測所有字元的概率分布的集合，也就是 $y$ 裡面所有元素的取值在[0,1]之間，那我們如何從 $y$ 預測出字元序列呢？直觀的想法是，我們找到一個路徑 $pi$

$pi={{pi_{1}...pi_{T}}}$

其中 $pi_{t}in[1,K]$ ，

$pi=argmax_{pi}P(pi|y)$

$P(pi|y)=prod_{t=1}^{T}y_{t,pi_{t}}$

然而，我們不是想要路徑 $pi$ ，舉個例子，比如我們說一個字母「a」，假設該音頻片段的長度T=5，我們可能從T=3開始發聲，則路徑 $pi=\_ \_ aaa$ ，或者我們從T=1開始發聲，但是T=4時，我們就停止了，這樣路徑 $pi=aaa\_ \_$ 。註：「 _」是表示空白，可理解為沒有聲音輸入。以此類推，還有很多種路徑的可能性。由此可見，我們最後所需要的既不是 $y$ 也不是 $pi$ ，而是我們稱之為label的序列，記做 $l$

$l={l_{1}...l_{S}}$

其中 $Sleq T$ ，這樣我們把可以上面所有路徑 $pi$ 都歸結到一個標籤 $l={a}$

再舉一個例子。比如我們的標籤是 $l={b,e,e}$ ，假設時序長度T=9，那我們可能的路徑是什麼呢？

$pi={bbbeee \_ ee}\ pi={\_bb\_ee\_ \_ee}\ pi={\_ \_bbbe \_ e\_}$

但是如果我們的路徑設置為：

$pi={\_ b\_eeeeee}\ pi={bbb\_ \_eeee}\ pi={\_ bb \_ eee \_ \_}$

這時候，其實歸結到的標籤是 $l={b,e}$ 。由此，我們可以看出「_」在分割連續字元時的重要性。

綜上所述，語音識別的輸出既不是字母概率分布 $y$ ，也不是路徑 $pi$ ，而是標籤 $l$ 。所以CTC是一種從 $y$ 結合 $pi$ 推導出 $l$ 的方法。

$P(l|x)=sum_{pi}^{}P(l|pi)P(pi|x)$

表示所有可能輸入序列對齊的和。

$P(pi|x)=prod_{t=1}^{T}y_{t,pi_{t}}$

動態時間規整

因為 $y$ 的長度通常比標籤 $l$ 長，從 $y$ 推理 $l$ 的過程稱之為動態時間規整。時間規整，是指把每一幀 $y_{t}$ 映射到標籤中的某個字元 $l_{s}$ 。我認為可以看成一個對齊的操作。

舉個栗子，我們有個音頻片段：「bee」,最有可能的路徑 $pi$ 是

顯然，我們想把這個路徑映射到 $l=left{ b,e,e ight}$ .似乎我們可以這樣映射

但是我們並不能阻止演算法映射路徑 $pi$ 中所有的「e」到標籤 $l$ 中的第一個"e"

同時，還有一個問題，就是我們如何映射路徑 $pi$ 中的「_」空白到標籤 $l$ 。

一個解決方法是，我們映射路徑 $pi$ 到 $l^{}$ ，而不是到標籤 $l$ 。其中， $l^{}$ 是在原始標籤 $l$ 的前後插入空白「_」。再次舉個栗子，如果 $l=left{ b,e,e ight}$ ,則

$l^{}=left{\_,b,\_,e,\_,e,\_ ight}$

這時，我們的規整工作變為這樣一個映射：

稍微特殊一點的情況是這樣的，如果我們的路徑 $pi$ 在開頭不含空白「_」，那麼我們把第一幀預測為字元「b」是合理的。

前向後向演算法

編者按：前面都還基本好理解，到了前向後向演算法，我真的理解了好久。尤其是兩個遞推公式的推導。我們一起了解一下。

因為對於每個給定的標籤 $l$ 唯一對應一個 $l^{}$ ，當我們用programming algorithm（動態規劃）對 $P(l^{}|x)$ 進行計算時，相當於計算 $P(l|x)$ 。

前向演算法

首先，我們考慮最後一個時刻T，對應的預測路徑為 $pi_{T}$ ， $pi_{T}$ 能被映射到 $l^{}$ 的最後一個位置 $l^{}_{left| l^{} ight|}$ ，是我們主動填充的空白「_」。或者，pi_{T}能被預測到 $l^{}$ 的倒數第二個位置，也就是標籤 $l$ 的最後一個字元。於是我們有以下公式：

這可以考慮為在時刻T時輸入圖片x預測到填充後的標籤 $l^{}$ 的全概率。

同時，我們引入一個表達式

$alpha(t,s)=P(l^{}_{1:s},pi_{t}=l^{}_{s}|x)$

$alpha(t,s)$ 表示到t時刻時，預測序列前 $s$ 個標籤的概率。所以在原論文里 $alpha(t,s)$ 被這樣定義：

$alpha(t,s)=sum_{piin N^{T}:\eta(pi_{1:t})=l_{1:s}}^{}{prod_{t^{}=1}^{t}y_{pi_{t^{}}}^{t^{}}}$

於是，我們可以推出下面公式：

上面的時間規整也說明了我們可以把路徑 $pi$ 中的第一個預測 $pi_{1}$ 映射到 $l_{1}^{}$ , $l^{}$ 中的第一個空白「_」，或者映射到標籤 $l$ 的一個元素 $l_{2}^{}$ 。於是，我們有

我們如何理解第三個公式呢？可以這樣認為：當輸入音頻序列的第一幀時，我們只能對位置靠前的部分進行合理的映射。舉個例子，{b,e,e}我們不會在第一個位置就預測到「e」，當然對應的概率也應該為0。但是開始的時候，我們可以選擇沉默一會兒「_」，或者直接發聲「b」。

As we will see， $alpha(t,s)$ 可以用下面的遞推公式求得。當然我初次看論文時，真的不明白，所以特意把原文里的這句話貼出來x_x。

為了理解這個公式，我們可以這樣看問題。當前時刻 $t$ 對應的 $pi_{t}$ 可能映射的位置是由什麼來決定的呢？比如 $alpha(2,2)$ ，表示T=2時刻，映射到前2個標籤的概率。這個概率是由T=1時刻，預測到第一個位置 $alpha(1,1)$ 和預測到第二個位置 $alpha(1,2)$ 轉移過來的。意思是我們在T=2時刻的 $pi_{2}$ 可能映射在第二個位置，也就是T=1時刻 $alpha(1,2)$ 映射的位置，或者是T=1時刻 $alpha(1,1)$ 預測位置的下一個位置。因為 $alpha(1,1)$ 是預測到第一個位置的概率，所以第二個位置是 $alpha(1,1)$ 預測位置的下一個位置。

那麼我們思考個簡單一點的問題， $alpha(2,1)$ 該如何計算呢？對了，可以看出來這個概率只和 $alpha(1,1)$ 和有關係，因為只能從 $alpha(1,1)$ 轉移到 $alpha(1,2)$ ，這也就是論文里為什麼最左上方那行箭頭一直往右畫。而 $alpha(2,2)$ 卻和 $alpha(1,1)$ 和 $alpha(1,2)$ 都有聯繫。

根據時序從左往右看------>

當然，我這裡沒有解釋為什麼會有累加前三項和前兩項這兩種情況。因為我自己還在學習理解，希望大家指正。貼下一篇論文解析的理解。

大致意思是我們在t時刻會有不同的映射情況，分別是當前對應的標籤 $l_{s}^{}$ 和前一時刻映射到該位置的概率有關、前一時刻的預測到該位置的前一位置的概率有關，當前 $l_{s}^{}$ ="_」時，這裡我有點疑惑（逃。

後向演算法

我們定義後向變數： $eta(t,s)$ 為t時刻，預測標籤 $s:left| l^{} ight|$ 位置字元的全部概率

當然根據定義 $eta(t,s)$ 可以這樣被定義：

$eta(t,s)=sum_{piin N^{T}:\eta(pi_{1:t})=l_{s:}left| l ight|}^{}{prod_{t^{}=t}^{T}y_{pi_{t^{}}}^{t^{}}}$

同理，T時刻最後位置的概率為：

當然，有些位置 $alpha(t,s)$ 是不會被預測到的，前面也舉了個栗子。同時， $eta(t,s)$ 在某些位置也不會被預測到。作者給了判斷的標準：

如果只是寫到這樣的程度，這篇文章是沒有意義的。為了方便理解，我會在舉一個實際的例子來理解這些公式。

RNN的輸出是 $[y_{1},y_{2},y_{3},y_{4},y_{5},y_{6},y_{7}]$ ，我們時序 $T=7$

標籤 $l={c,a,t}$ ,則 $l^{}={\_,c,\_,a,\_,t,\_}$ ,且 $left| l ight| leq T$

前向計算過程：

$t=1\ alpha(1,1)=y_{1, "\_"}\ alpha(1,2)=y_{1, "c"}\ \ t=2\ alpha(2,1)=y_{2, "\_"}cdot alpha(1,1)=y_{2, "\_"}cdot y_{1, "\_"}\ alpha(2,2)=y_{2, "c"}cdot (alpha(1,1)+alpha(1,2))=y_{2, "c"}cdot (y_{1, "\_"}+y_{1, "c"})\ alpha(2,3)=y_{2, "\_"}cdot (alpha(1,2)+alpha(1,3))=y_{2, "\_"}cdot (y_{1, "c"}+0)\ alpha(2,4)=y_{2, "a"}cdot (alpha(1,2)+alpha(1,3)+alpha(1,4))=y_{2, "a"}cdot (y_{1, "c"}+0+0)\ alpha(2,5)=y_{2, "\_"}cdot (alpha(1,4)+alpha(1,5))=y_{2, "\_"}cdot (0+0)=0\$

這裡是不是有個疑問，按照公式來說， $alpha(2,2)$ 對應的標籤為"c"，則應該有三項，但是我們沒有 $alpha(1,0)$ ，故只有兩項。同時，我們發現當 $sgeq 5$ 時，概率為0，這也就是為什麼搜索空間那個圖t=2時刻，箭頭只畫到s=4的位置！OK，我們接著開車，一路向北，離開有你的季節。

$t=3\ alpha(3,1)=?$

T=3時刻，距離第一個位置已經有點遠了，我們開始擔心是不是還能映射到第一個位置。計算下判別公式 $T=7\ left| l^{} ight|=7\ t=3\ 則left| l^{} ight|-2(T-t)-1=-1$

沒問題的，我們在這時刻還可飆車。

$alpha(3,1)=y_{3, "\_"}cdot (alpha(2,1))\ alpha(3,2)=y_{3, "c"}cdot (alpha(2,1)+alpha(2,2))\ alpha(3,3)=y_{3, "\_"}cdot (alpha(2,2)+alpha(2,3))\ alpha(3,4)=...\ alpha(3,5)=...\ alpha(3,6)=...\ alpha(3,7)=0$

這時候，我們需要注意下 $alpha(3,3)$ ，只由兩項構成因為該位置的標籤為"_"，按照公式是只有兩項的和。是不是和搜索空間的圖對應起來了！接下來的計算和上面一樣，就不展開推導了。

特別說明下，當t=5時，判別公式計算結果為3，則 $alpha(5,1)=0\ alpha(5,2)=0$

損失函數

我們發現，有大量的概率連乘操作，容易導致underflows。為了計算損失函數，我們先在做一個log scale的操作

$ln(a+b)=ln(a(1+frac{b}{a}))=lna+ln(1+e^{lnfrac{b}{a}})=lna+ln(1+e^{lnb-lna})$

這樣，我們只需要計算 $lna 和lnb$ 。

我們定義CTC的損失函數為在某個訓練集S，正確預測所有樣本標籤概率的負log函數。

根據前向後向演算法的定義，我們在t時刻，預測了整個序列的概率為：

這個公式可以這樣理解， $alpha$ 是預測前u個字元的概率， $eta$ 是預測後 $left| l ight|-u$ 個字元的概率。注意前後文記號的變化，這裡的u就是上文的s。這樣 $alphacdoteta$ 是預測整個序列的概率，此時我們隱去了時刻t，其實是一直存在的。

這裡我們已經定義好了損失函數，接下來進行求導。

損失函數求導

文章最開始提及了 $y_{t,k}$ ，我們的損失函數對其求導，得到：

其實就是 $(lnx)^{}=frac{1}{x}$

接下來計算

結合 $alpha(t,s)cdot eta(t,s)$ 的定義：

因為αβ是連乘定義的，求導相當於對應那項為1，就是整體除以對應求導的變數

於是:

為了把梯度從輸出層傳進裡面的隱藏層，我們需要定義一個變數 $a_{k}^{t}$ ,是進入激活函數前網路的輸出結果，意思就是 $y_{k}^{t}=softmax(a_{k}^{t})$ .

我們對softmax進行求導：

softmax求導分為i=j即角標相同的情況，和i!=j角標不同的情況。我們這裡角標都是k，故是角標相同的情況，則導數為： $y_{k}^{t}(1-y_{k}^{t})$ ,即：

上式中的 $delta$ 就是衝激函數代表1

這樣，綜合上述公式，我們可以推導：

整理上式得：

其中，後面一項我們稱之為"error signal"，反向傳播來訓練模型。

寫在最後：

本文作為學習CTC演算法的複習與總結，因為原論文寫得晦澀難懂，好多公式推導不過去，故綜合很多優秀的學習資料不斷理解。感謝有你！

參考文獻：

【1】Alex Graves. etc. Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks, 2006
【2】Yi Wang. Connectionist Temporal Classifaction A Tutorial with Gritty Details, 2015
【3】Alex Graves. Connectionist temporal classification, 2012