概述
背景
在實際的序列學習場景中經常會遇到從沒有切分的，帶有噪音的數據中對序列的label進行預測胜臊，例如語音識別中需要將聲學信號轉換成words或者是 sub-words.
文章提出了一種新的rnn訓練方法，可以將沒有切分的序列生成相應的標簽回右。
傳統(tǒng)方法的問題
傳統(tǒng)方法中常用的HMM,CRF等有一些可以較好的解決這種序列標注問題咙冗，但是它們也存在相應的問題：
- 通常需要大量的領域相關知識，例如定義相關的label伪货，選擇crf的輸入特征等等。
- 需要基于一定的相關性假設钾怔，例如HMM中觀察序列之間是相互獨立的碱呼。
- 對HMM 來說訓練是產生式的，即使序列標注問題是一個判別問題宗侦。
RNN的優(yōu)勢
- 不需要任何關于數據的先驗知識愚臀，除了選擇定義輸入和輸出的格式。
- 具有強大的特征表達能力矾利，能夠很好的對問題進行建模姑裂，并且可以表示判別式模型。
- 對于噪音問題處理的更加魯棒男旗。
- 可以利用long-range seququence 建模舶斧。
效果
效果優(yōu)于hmm和hmm-rnn模型。
具體思路
將網絡的輸出表示為所有可能的label序列的概率分布察皇，有了這個概率分布可以定義目標函數為直接最大化正確的label序列的概率茴厉。
因為目標函數可導，所以可以用標準的bp方法進行訓練什荣。
Temporal Classification
記號
$S$表示從一個分布$D_{X \times Z}$提取的訓練樣本
輸入空間$X = (Rm)*$ 是所有的$m$維的實數向量矾缓。
目標空間 $Z = L ^* $ 是所有的Label（有限的）組成的序列空間。
我們稱$L^*$中的元素為label sequences 或labellings稻爬。
任意的一個樣本$s \in S,s= (x,z)$,
目標序列$z = (z_1, z_2, ..., z_U)$,
輸入序列$x = (x_1, x_2,...,x_T)$
其中$U <= T$
目標是用$S$來訓練一個temporal classifier s.t. $h: X -> Z$
Label Error Rate
度量錯誤
給定一個測試集$S^\prime \subset D_{X \times Z}$
定義$h$的標簽錯誤率（LER = Label Error Rate)為$S ^ \prime$數據集上的標準化的 分類結果和目標之間的編輯距離嗜闻。
\begin{equation}
LER(h,S^\prime) = {1 \over {|S ^ \prime|}} \sum _{(x, z) \in S ^ \prime} { {ED(h(x),z)} \over {|z|} }
\label{eq:defLER}
\end{equation}
其中$ED(p,q)$是sequence$p,q$之間的編輯距離偿曙。（插入笑陈，替換和刪除）
Connectionist Temporal Classification
介紹了如何表示RNN的輸出可以用來做CTC,最直接的想法是將RNN的輸出表示為一個給定的輸入的關于Label sequences的條件概率分布
網絡輸出到標簽序列
CTC網絡有一個softmax輸出層，
輸出層有$|L| + 1$個輸出單元碗旅，
其中$|L|$指的是label的個數傅是，
1代表空格或其他非label的輸出基公。
具體形式
首先定義初步的映射關系
輸入序列$X,|X| = T$
RNN $m$個輸入迁筛，$n$個輸出($n = |L| + 1$)和權重向量$w$ as \space a \space continuous \space map :
$N_w ： (R^m) ^ T -> (R^n) ^ T$
定義$y = N_w(x)$是神經網絡從輸出咳蔚，并且$y_k ^ t$是第$k$個單元的在時間$t$時的激活值
即label $k$在時間$t$概率,則有長度$T$的序列關于$L ^ \prime = L \bigcup \{blank\}$概率為：
\begin{equation}
p(\pi | X) = \prod _ {t = 1} ^ T y_{\pi _t} ^ t, \forall \pi \in {L ^ \prime } ^ T
\label{eq:ctcSeqProb}
\end{equation}
定義一個多對一的映射
映射形式如下:
$\beta : (L ^ \prime )^T -> L {<=T}$,$L{<= T}$是可能的標簽
具體步驟:
將所有的空格和重復的標簽從路徑中移除，例如
$\beta (a\ab\)= \beta (\aa\\abb) = aa$,其中代表空格
計算關于$l \in L^ {<= T}$的條件概率
\begin{equation}
p(l|x) = \sum _ {\pi \in \beta ^ {-1}(l)} p (\pi | x)
\label{eq:binverseprob}
\end{equation}
構建分類器
有了以上的計算方法锯茄，分類器的輸出應該是對輸入生成的標注可能性最大的一個序列。
\begin{equation}
h(x) = arg max _ {l \in L ^{\leq T}} p(l | x)
\label{eq:targetFunction}
\end{equation}
此過程可以借鑒傳統(tǒng)的叫法decoding茶没，但是目前還沒有一個通用的肌幽，tractable的解碼算法。
目前常用以下兩種 近似的方法 來做解碼：
第一種解碼方法（Best Path Decoding)
思路：假設最可能的路徑（$\pi$）往往和最可能的labeling相關：
\begin{equation}
h(x) \approx \beta(\pi ^ )
\label{eq:decodeMethod1}
\end{equation}
其中：$\pi ^ = arg max _ {\pi \in N^t} p (\pi | x)$
此方法簡單易于實現抓半，而且找到的是在各個時間點的激活值最大的值喂急，但是不能保證找到的是最有可能的label序列。
第二種解碼方法(Prefix Search Decoding)
類似于前后向算法基礎上進行笛求，具體見第四章（下一章訓練網絡部分）
這種方法只要時間足夠往往可以找到最優(yōu)的結果廊移，但是解碼時間跟序列長度成指數增長。
通常使用啟發(fā)式的解碼方法探入。
啟發(fā)式的思路如下：
首先根據輸出中預測是blank的節(jié)點進行切分狡孔，然后分段進行prefix 查找。
缺陷
通常情況下啟發(fā)式的方法工作的很好蜂嗽，并且能夠找到最優(yōu)的路徑苗膝，但是在一些情況下會出錯，例如在一個分割點的兩端兩者的預測label都相同植旧，而且概率較小辱揭。
訓練網絡
CTC前后向算法
我們需要一個高效的方式來計算$p(l|x)$,但是參考公式 \ref{eq:binverseprob} 會發(fā)現這是一個難以計算的任務。
本文引入了動態(tài)規(guī)劃的方法病附，類似于hmm中的前后向算法问窃，如下：
一個序列$q$,長度為$r$,記為$q_{1:p}$ 和$q_{r-p, r}$作為它的最前和最后的$p$的標記。
對一個labeling序列 $l$,定義前向變量$ \alpha _ t (s) = \sum _ {\pi \in N^T:\beta(\pi_{1:t})=l_{1:s}} \prod _ {t ^\prime = 1} ^ t y _ {\pi _ {t ^ \prime}} ^ {t ^ \prime} $
（前s個label由前t個觀察序列生成的概率完沪，應該s<=t）
對序列在處理一下對序列$l$前后及中間增加一個blank域庇，則$l-> l^\prime,長度為2|l|+1$
（此時應該$s< |l^\prime| - 2(T-t)-1$）
則有以下等式成立
$$
\alpha 1 (1) = y_b ^ 1 \
\alpha _ 1 (2) = y{l _ 1} ^ 1 \
\alpha _ 1 (s) = 0, {\forall s > 2}
$$
并且有遞歸形式如下：
\begin{equation}
\alpha_t(s) =
\begin{cases}
(\alpha_{t-1}(s) + \alpha_{t - 1}(s - 1))y_{l_s ^ \prime} ^ t, & \text {$if \space l ^ \prime _ s = b \space or \space l ^ \prime _ {s - 2} = l _ s ^ \prime$} \
(\alpha_{t-1}(s) + \alpha_{t - 1}(s - 1) + \alpha _ {t - 1} (s - 2)) y_{l_s ^ \prime} ^ t, & \text {otherwise}
\end{cases}
\label{eq:recurrForward}
\end{equation}
其中 $y_k ^ t$是第$k$個單元的在時間$t$時的激活值
即label $k$在時間$t$概率,則有長度$T$的序列關于$L ^ \prime = L \bigcup \{blank\}$概率
解釋
狀態(tài)序列$b,l_1,b,l_2,b,l_3,...,b,l_k,b$
- 當前狀態(tài)為blank
則當前狀態(tài)可以由 前一個狀態(tài)是blank（$\alpha _{t - 1} (s)$)或者前一個狀態(tài)是狀態(tài)序列中的前一個狀態(tài)（$\alpha _{t - 1} (s - 1)$轉移而來 - 當前狀態(tài)和兩步前的狀態(tài)相同
則當前狀態(tài)可以由前一個狀態(tài)是blank（$\alpha _{t - 1} (s)$)和前一個狀態(tài)跟兩步前相同的狀態(tài)（$\alpha _{t - 1} (s - 1)$轉移而來 - 其余的情況有三條轉移途徑
當前狀態(tài)不為空，而且前兩步的狀態(tài)和當前狀態(tài)不同- 兩步前狀態(tài)不為空
則當前狀態(tài)可以由中間狀態(tài)為兩步前狀態(tài)丽焊，空和當前狀態(tài)三條路徑轉移而來较剃。 - 兩步前狀態(tài)為空
則當前狀態(tài)可以由中間狀態(tài)為空，中間狀態(tài)為狀態(tài)序列中兩步前狀態(tài)和中間狀態(tài)為當前狀態(tài)轉移而來技健。
- 兩步前狀態(tài)不為空
定義前向算法
參考文獻
minimum edit distance
Temporal classification Extending the classification paradigm to multivariate time series
Supervised Sequence Labelling with Recurrent Neural Networks 第7章
