聯(lián)接主義時序分類CTC的細(xì)致推導(dǎo)（一）

參考：Alex Graves,?Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks

本篇的主要目的如下：

? ? ? ? 1）第一部分幻碱，跟隨原論文做些常規(guī)性介紹琴许，以及一些個人理解；

? ? ? ? 2）第二部分借跪，我將補充原論文中所有公式的推導(dǎo)細(xì)節(jié)。

自己瞎BB

? ? ? ? “聯(lián)接主義時序分類”譯自Connectionist?Temporal Classification（簡稱CTC）?愧薛，首次聽到這名字就覺得此算法必不是凡夫俗子晨炕；在深度學(xué)習(xí)背景下，“聯(lián)接主義”基本指代的是基于神經(jīng)網(wǎng)絡(luò)的實現(xiàn)毫炉。其原理還是挺優(yōu)美的瓮栗，甚至在我看來作為學(xué)習(xí)材料，與Transformer什么的相比瞄勾，CTC更勝一籌费奸。我認(rèn)為早期阻礙深度學(xué)習(xí)進(jìn)軍語音識別領(lǐng)域的障礙就是對齊問題，因而后來發(fā)展出了CTC和Seq2Seq框架丰榴。

CTC的基本動機(jī)

? ??????我們會碰到某些序列分類任務(wù)货邓，其人工標(biāo)注不能與輸入特征序列形成嚴(yán)格對齊，也就是不能知道每一幀輸入具體的輸出標(biāo)簽四濒，因而就不能使用深度學(xué)習(xí)框架典型的監(jiān)督學(xué)習(xí)組件來進(jìn)行訓(xùn)練换况。比如：語音識別、光學(xué)字符識別等等都是這類任務(wù)盗蟆。

? ? ? ? CTC的基本動機(jī)是：構(gòu)建一個無需逐幀對齊的訓(xùn)練算法戈二，可以自動進(jìn)行隱式地對齊，例如和GMM-HMM的語音識別框架類似喳资，有個強制對齊過程觉吭。這兩種算法的強制對齊策略都是基于數(shù)據(jù)序列和標(biāo)簽序列的單調(diào)對應(yīng)這個事實（不妨見下圖2）；這種性質(zhì)可以使得我們在對齊過程加上約束仆邓，得到可行性更高的算法鲜滩，另外提供一個高效的解碼算法。

????????CTC的基本思路是：1）給到一個將神經(jīng)網(wǎng)絡(luò)（典型地為RNN）的輸出向量序列映射成所有可能的標(biāo)簽序列上的概率分布节值；2）基于這個分布徙硅，可以設(shè)計一個目標(biāo)函數(shù)，并且該目標(biāo)函數(shù)是可導(dǎo)的搞疗，進(jìn)而可以使用BPTT算法進(jìn)行優(yōu)化嗓蘑；3）基于這個分布，可以設(shè)計一個高效的解碼過程匿乃。

時序分類器的構(gòu)建

引入一些記號：

a） $\mathcal X=(\mathbb R^m)^* \equiv \{(\boldsymbol x_1,\boldsymbol x_2,..., \boldsymbol x_T)\ |\ \boldsymbol x_i \in \mathbb R^m, T\in \mathbb N \}$ 桩皿，即長度有限的m維實向量序列全體

b） $L$ 為有限字母表，即轉(zhuǎn)錄的目標(biāo)字符集幢炸， $L^{\ast}=\bigcup_{N=1}^{+\infty} L^N$ 為所有長度有限的標(biāo)簽序列全體

c） $L^{\le T} =\bigcup_{N\le T} L^N$ 為所有長度小于等于 $T$ 的由 $L$ 中的字符構(gòu)成的字符序列全體

d） $(X,\boldsymbol l)$ 為一個訓(xùn)練數(shù)據(jù)對泄隔，其中 $X=(\boldsymbol x_1,\boldsymbol x_2,...,\boldsymbol x_T),\boldsymbol l=(\boldsymbol l_1,\boldsymbol l_2,...,\boldsymbol l_N)$ 因為CTC對一幀輸入只產(chǎn)生一個輸出，所以必有 $N\leq T$ 成立阳懂，否則將不能生成完整的目標(biāo)字符序列梅尤。

e） $\boldsymbol l_{1:s}$ 表示子串 $[\boldsymbol l_1,...,\boldsymbol l_s], s \le N$

? ? ? ? CTC使用Softmax輸出層柜思，來逐幀地產(chǎn)生字符集 $L$ 上的概率分布序列岩调；將這些分布序列解釋為標(biāo)簽序列上的概率分布巷燥，并最終解碼成一個個標(biāo)簽；另外例如語音識別中号枕，通常輸入特征幀會遠(yuǎn)大于輸出標(biāo)簽序列缰揪；因此，我們需要一個合并過程：將對應(yīng)到同一個字符的連續(xù)標(biāo)簽合并葱淳，這當(dāng)然是合理的（比如在語音識別中钝腺，一個音素的完整發(fā)音必然包含多個連續(xù)的聲學(xué)特征幀）。

????????但是赞厕，人工標(biāo)注的字符序列中本來就可以包含連續(xù)的重復(fù)字符艳狐，則這樣的合并過程必然導(dǎo)致錯誤的輸出，例如下左圖：字符串 $\text {“好好學(xué)習(xí)”}$ 對應(yīng)的語音特征序列為 $[\boldsymbol x_1, \boldsymbol x_2, ..., \boldsymbol x_9]$ 皿桑，CTC解碼可能是 $\text{“好好好學(xué)學(xué)習(xí)習(xí)習(xí)”}$ 毫目，直接合并后會變成 $\text{“好學(xué)習(xí)”}$ 。因此作者增加了一個空白符 $\epsilon$ 來分離連續(xù)的相同字符诲侮，并用兩個階段的合并方法镀虐，例如下右圖：若CTC解碼的結(jié)果為 $“\text{好好}\epsilon\text{好}\text{學(xué)習(xí)習(xí)}\epsilon”$ ，則：1）將連續(xù)的相同字符合并得 $“\text{好}\epsilon\text{好}\text{學(xué)習(xí)}\epsilon”$ 沟绪，2）再將空白符去除得到正確的字符序列 $“\text{好}\text{好}\text{學(xué)習(xí)}”$ 刮便。

? ? ? ? 形式地說绽慈，上面的合并過程構(gòu)建了一個映射 ${\mathcal B} :( L^{\prime} )^T \to ( L )^N$ ，其中 $N\leq T,\ \ L^{\prime}=L\cup \{\epsilon\}$ 為擴(kuò)展字符集坝疼，這是一個“多到一”的映射。這相當(dāng)于使用映射 $\mathcal B$ 在集合 $(L^{\prime})^T$ 上定義了一個等價類裙士，那些映射（合并）到相同字符串 $\boldsymbol l \in L^N$ 的擴(kuò)展字符串序列 $\pi \in {L^{\prime}}^T$ 被歸為一個等價類入客；即桌硫， $\mathcal B$ 給出了集合 ${ L^{\prime} }^T$ 的一個不交并。

圖1铆隘，左邊無空白符直接合并結(jié)果，右邊先合并再去除空白結(jié)果

? ? ? ?所以南用，最終CTC使用的Softmax層將輸出擴(kuò)展字符集 $L^{\prime} = L\cup \{ \epsilon \}$ 上的概率分布掏湾，即對于輸入序列來說，神經(jīng)網(wǎng)絡(luò)定義了這樣的映射： $\mathcal N : ({\mathbb R}^{m})^T \to (\mathbb R^{|L^{\prime}|})^T$ 肿嘲，網(wǎng)絡(luò)輸出的 $T$ 個分布構(gòu)成的矩陣融击，其每個元素 $y^{t}_{k}$ 表示在時刻 $t$ 觀察到標(biāo)簽 $k$ 的概率，并將整個概率矩陣解釋為標(biāo)簽序列集 $(L^{\prime})^T$ 上的概率分布： $p(\pi\ | X)$ 雳窟，其中 $X=[\boldsymbol x_1,...,\boldsymbol x_T]$ 為特征序列尊浪， $\pi \in (L^{\prime})^{T}$ 為一個可能的對齊到目標(biāo)字符串上的擴(kuò)展標(biāo)簽序列，我們把它稱為一個路徑封救。

? ? ? ? 由于神經(jīng)網(wǎng)絡(luò)是一個確定性函數(shù)拇涤，因此在給定輸入特征序列后，整個網(wǎng)絡(luò)的狀態(tài)都是確定的誉结；為了得到一個簡單的標(biāo)簽序列上的分布鹅士，那么作者提出了這樣的假設(shè)：給定網(wǎng)絡(luò)狀態(tài)條件下，“網(wǎng)絡(luò)在不同時刻的輸出之間是條件獨立的”惩坑。因為不存在從輸出層到輸出層的自反饋鏈接掉盅，也不存在從輸出層到網(wǎng)絡(luò)內(nèi)部的反饋鏈接，所以這樣的假設(shè)是合理的旭贬，即假設(shè)下式成立：

$p(\pi\ | X) = \prod_{t=1}^{T}p(z_t=\pi_t| X)= \prod_{t=1}^{T} y^t_{\pi_t} , \ \forall \pi \in {L^{\prime}}^T$

? ? ? ? 由于 $p(\pi\ | X)$ 定義了路徑集合上的一個概率分布怔接，不同路徑（即不同的樣本）之間的概率滿足可加性，由映射 $\mathcal B$ 的定義稀轨，一個字符序列 $\boldsymbol l \in L^{\leq T}$ 對應(yīng)的路徑為 $\boldsymbol l$ 的逆像 $\mathcal B^{-1}(\boldsymbol l)$ 扼脐。因此，由概率的不交可加性有：

$p(\boldsymbol l| X) = \sum_{\pi \in \mathcal B^{-1}(\boldsymbol l)} p(\pi| X) \quad \cdots (1)$

????????由此奋刽，我們構(gòu)造了給定模型參數(shù)和輸入數(shù)據(jù)條件下瓦侮，任一長度為 $N\leq T$ 的字符序列集合上的分布。

解碼

? ? ? ? 有了公式（1）佣谐，我們就可以用下式找到最優(yōu)的標(biāo)簽序列 $\boldsymbol l$ 肚吏，當(dāng)給定模型和輸入特征序列 $X=[\boldsymbol x_1,\boldsymbol x_2,...,\boldsymbol x_T]$ 條件下。

$\boldsymbol l^* = {\rm arg}\max_{\boldsymbol l \in L^{\leq T}} p(\boldsymbol l\ |\ X)$

作者提出了兩個方法：

Best path decoding：

? ??? ?? $\boldsymbol l^* \approx B^{-1}(\pi^*)$ 狭魂，其中 $\pi^* = {\rm arg}\max_{\pi \in L^T} p(\pi | X)$

? ? ? ? 該方法基于這樣的假設(shè)：給定輸入序列罚攀，在標(biāo)簽序列集合 $L^{\leq T}$ 上由CTC構(gòu)建的概率分布中，正確的標(biāo)簽序列 $\boldsymbol l^* \in L^{\leq T}$ 對應(yīng)的逆像 $\mathcal B^{-1}(\boldsymbol l^*)$ 往往包含最優(yōu)的那一條路徑 $\pi^*$ （注意這兩者之間的關(guān)系雌澄，公式1）斋泄。其計算也簡單，因為由條件獨立性假設(shè)镐牺，要使 $p(\pi\ | X) = \prod_{t=1}^{T} y^t_{\pi_t} , \ \forall \pi \in {L^{\prime}}^T$ 最大炫掐，只要獨立地取使得 $y^t_{\pi_t}, \forall t$ 達(dá)到最大的那個 $\pi_t^*$ 即可。

關(guān)于Best path decoding的個人思考

? ? ? ? 這其實和經(jīng)典語音識別中使用的Viterbi訓(xùn)練的思想非常類似睬涧，只不過在那里是在訓(xùn)練階段用的募胃，訓(xùn)練中有明確的目標(biāo)旗唁；而這里是在解碼階段检疫，所以風(fēng)險更高一些参袱。

????????那么這樣的假設(shè)合理嗎抹蚀？似乎沒什么緣由企垦，不過，當(dāng)每個候選字符序列 $\boldsymbol l \in L^{\leq T}$ 對應(yīng)的逆像 $\mathcal B^{-1}(\boldsymbol l)$ 中的概率質(zhì)量的分布充分地集中到最大路徑上時郑现，那么在每個等價類 $\mathcal B^{-1}(\boldsymbol l)$ 中分別挑選最大概率的路徑 $\pi^*_{\boldsymbol l} \in \mathcal B^{-1}(\boldsymbol l)$ 進(jìn)行比較接箫，就對應(yīng)著在不同的字符序列 $\boldsymbol l$ 的概率之間進(jìn)行比較。因此辛友，作者驗證了在某一些任務(wù)中剪返，確實有不錯的表現(xiàn)脱盲。

????????但是，一方面：這樣得到的結(jié)果 $\mathcal B(\pi^*)$ 可能不對應(yīng)任何合法的語句钱反。為什么這樣？我們已經(jīng)根據(jù)最大似然準(zhǔn)則來訓(xùn)練模型哎壳，例如：使它可以在“好好學(xué)習(xí)”對應(yīng)的音頻上能產(chǎn)生“好好學(xué)習(xí)”字符序列的概率達(dá)到最大了岸汀？

? ? ? ? 這就是CTC目標(biāo)函數(shù)訓(xùn)練的結(jié)果蹲坷，回到最開始，我們并沒有“好好學(xué)習(xí)”音頻的每一幀對應(yīng)的標(biāo)簽级乐，我們不是在使用softmax-crossentropy損失訓(xùn)練县匠；而是使用CTC損失在整體上將多幀音頻特征映射到字符序列，并給出一個整體上的對應(yīng)權(quán)重（似然值）贼穆。也就是在訓(xùn)練階段兰粉，賦予對應(yīng)的輸入序列 $X$ 的權(quán)重是通過前向變量算的所有可能路徑 $\mathcal B^{-1}(\boldsymbol l)$ 上的權(quán)重和；誰也不知道愕秫，在訓(xùn)練期間權(quán)重是如何在路徑集 $\mathcal B^{-1}(\boldsymbol l)$ 中進(jìn)行分配的戴甩。

????????換句話說，就是在訓(xùn)練階段甜孤，是許多團(tuán)隊 $\{\mathcal B^{-1}(\boldsymbol l) \ |\ \forall \boldsymbol l \in L^{\le T}\}$ 之間的團(tuán)隊競賽课蔬；而在測試階段郊尝，卻只讓每個團(tuán)隊派一個最厲害的工程師 $\{\pi^*_{\boldsymbol l} \ |\ \pi^*_{\boldsymbol l} = \arg\max_{\pi \in \mathcal B^{-1}(\boldsymbol l) } p(\pi|X) \ \rm {s.t.}\ \boldsymbol l \in L^{\le T} \}$ 進(jìn)行較量流昏，二者顯然不一致。另一方面谚鄙，即便best path decoding剛好得到一個合法的語句刁绒，也很可能不在 $\mathcal B^{-1}(\boldsymbol l^*)$ 之中，這里 $\boldsymbol l^*$ 為最優(yōu)字符序列傻盟。

? ? ? ? 所以在解碼階段，我們?nèi)匀幌Ｍ凑沼?xùn)練階段的做法來规哲。但是在訓(xùn)練中唉锌，我們有每個音頻對應(yīng)的標(biāo)柱字符序列竿奏，因而可以根據(jù)標(biāo)注構(gòu)建狀態(tài)轉(zhuǎn)移圖，并以此進(jìn)行動態(tài)規(guī)劃計算概率痘番。而測試階段平痰，我們只有 $T$ 幀網(wǎng)絡(luò)的輸出宗雇，并不知道對應(yīng)哪句話（不然還解什么碼）莹规。也不可能窮舉所有長度 $\le T$ 的合法語句，然后針對每個語句使用forward算法計算概率舞虱。

? ? ? ? 但是矾兜，如果我們能像訓(xùn)練階段的Forward算法那樣：累積所有對齊到相同的字符序列上的路徑的概率總和，那就可以得到每個字符串對應(yīng)的概率了椅寺，而非一個個孤立的路徑上的概率占调；由此迟螺，引出了下面的Prefix search decoding方法。

Prefix search decoding

? ? ? ? 可以基于下面介紹的Forward-backward算法链韭，計算連續(xù)擴(kuò)展的標(biāo)簽前綴的概率苫耸。這一部分在原論文沒有詳細(xì)介紹褪子，不過可以直接看distill的CTC介紹，這篇文章圖文并茂笼痛，很好地解釋了基于beam search的解碼過程（TODO）缨伊。

模型的訓(xùn)練

? ? ? ? 基于最大似然原則，找到一個可導(dǎo)的損失函數(shù)谭胚，使用梯度下降算法，進(jìn)行負(fù)對數(shù)似然下降旁趟。為了計算本篇第二部分中的每個時刻對網(wǎng)絡(luò)輸出的梯度轻庆，我們需要先引入下面的前向-后向變量：

CTC前向-后向算法

? ? ? ? 為了表述明確，我們使用“字符序列”表示合并后的對齊序列或者人工標(biāo)注序列GT蛾方，下面記為 $\boldsymbol l$ 拓春；并繼續(xù)用“路徑”表示CTC算法輸出的帶空白符 $\epsilon$ 的序列，記為 $\pi$ 懂鸵。

? ? ? ? 在訓(xùn)練的時候行疏，從訓(xùn)練集中取出樣本 $(\boldsymbol l, X)$ 匆光，其中 $\boldsymbol l=[\boldsymbol l_1,...,\boldsymbol l_N], X=[\boldsymbol x_1,...,\boldsymbol x_T]$ 分別為字符序列和特征序列，我們嘗試最大化概率 $p( \boldsymbol l | X)$ 酿联；對于一個稍長的標(biāo)簽序列 $\boldsymbol l \in L^{\leq T}$ 终息，其逆像 $\mathcal B^{-1}(\boldsymbol l)$ 包含太多的路徑，往往不可直接根據(jù)定義來計算贞让；因此我們需要一個和HMM類似的前向-后向算法周崭。

圖2，上為left-right的HMM狀態(tài)轉(zhuǎn)移震桶，下為CTC狀態(tài)轉(zhuǎn)移

????????和GMM-HMM語音框架不同的是，CTC并沒有類似詞典、語言模型那樣的用于將音素組織成目標(biāo)語句的過程歼指。因此，CTC在計算概率時需要顯示地引入空白符來控制輸出語句的結(jié)構(gòu)脱拼。如圖（2）丁侄，上面的是典型的left-right HMM狀態(tài)轉(zhuǎn)移圖潮孽，只能有“自跳”和“下跳”请祖，而下面的CTC轉(zhuǎn)移圖除了“自跳”眼虱、“下跳”還包括一個“跨字跳躍”诈豌，不過這種跳躍是有條件的：1）如圖所示，只有當(dāng)前字符不是空白符 $\epsilon$ ，且當(dāng)前字符“好”和后面第二個字符“學(xué)”不是同一個字時，才能執(zhí)行“跨字跳躍”它掂。

? ? ? ? CTC在計算概率時，會把原先長度為 $N$ 的字符串?dāng)U展成長度為 $2N+1$ 帶空白符的字符串纵菌，記作 $\boldsymbol l^{\prime}$ 手幢，如圖（2）在首尾各加一個空白符监透，并在相鄰兩字符之間插入一個空白符粪狼。為什么要在首位加上空白符呢米碰？比如可以用來吸收語音前后的靜音、噪聲供鸠、換氣等非語音信號。而字間的空白符一方面擔(dān)任著分割疊字的任務(wù)，另一方面也可以用來吸收語句內(nèi)的短停拳球。

? ? ? ? 因此，以圖（2）為例珍特，CTC中的合法的起始狀態(tài)有兩個： $\boldsymbol l^{\prime}_1=\epsilon$ 和 $\boldsymbol l^{\prime}_2=“好”$ 祝峻，終止?fàn)顟B(tài)也有兩個： $\boldsymbol l^{\prime}_6=“學(xué)"$ 和 $\boldsymbol l^{\prime}_7=\epsilon$ 。

前向變量

? ? ? ? 我們期望計算 $p(\boldsymbol l | X)\equiv p(\boldsymbol l_{1:N}|X)$ 扎筒，也就是計算從起始狀態(tài)到終止?fàn)顟B(tài)所有路徑上的概率總和莱找，因而需要定義前向變量：

$\alpha_t(s) = \sum_{\begin{aligned} &\quad \pi \in {L^{\prime}}^T \\ &\mathcal B(\pi_{1:t})=\boldsymbol l_{1:s} \end{aligned}} \prod_{\tau=1}^{t} y^t_{\pi_{\tau}}$

? ? ? ? 也就是映射到 $\boldsymbol l$ 的前 $s$ 個字符的所有長度為 $t$ 的路徑上的概率總和。但是由于增加了空白符 $\epsilon$ 嗜桌，我們需要在擴(kuò)展的字符串 $\boldsymbol l^{\prime}$ 上進(jìn)行動態(tài)規(guī)劃奥溺，即定義前向變量 $\alpha_t(s)\ ,\ s \in [1,...,2N+1]$ 。只要確保最終迭代步 $\alpha_T(s)\ ,\ \forall s$ 中包含且僅包含能夠合并成 $\boldsymbol l$ 的全部路徑 $\pi$ 骨宠，就能保證 $\sum_{s}\alpha_T(s) = p(\boldsymbol l | X)$ 浮定。

DP初始化：

$\begin{aligned}&\alpha_{1}(1) = y^1_{\epsilon}\\&\alpha_{1}(2) = y^1_{\boldsymbol l_1}\\&\alpha_{1}(s) = 0\ ,\ \forall s >2\end{aligned}$

????????其中： $y^t_{\epsilon}$ 為在時間 $t$ 模型輸出字符 $\epsilon$ 對應(yīng)的概率； $y^t_{\boldsymbol l_s}$ 為在時間 $t$ 模型輸出目標(biāo)字符串 $\boldsymbol l$ 中第 $s$ 個字符在softmax輸出層中對應(yīng)的概率层亿。

DP迭代：

????????利用動態(tài)規(guī)劃求迭代方程壶唤，根據(jù)CTC的狀態(tài)轉(zhuǎn)移，需分兩類狀態(tài)討論：

1）當(dāng) $\boldsymbol l^{\prime}_s=\epsilon$ 或 $\boldsymbol l^{\prime}_{s-2}=\boldsymbol l^{\prime}_s$ 時棕所，不能進(jìn)行“跨字跳躍”，在這種情況下悯辙，CTC只能“自跳”或“下跳”琳省；

2）當(dāng) $\boldsymbol l^{\prime}_s \ne \epsilon$ 且 $\boldsymbol l^{\prime}_{s-2} \neq \boldsymbol l^{\prime}_s$ 時迎吵，有額外的“跨字跳躍”；

????????而事件 $\mathcal B(\pi_{1:t-1})=\boldsymbol l_{1:s}\ ;\ \mathcal B(\pi_{1:t-1})= \boldsymbol l_{1:s-1}\ ;\ \mathcal B(\pi_{1:t-1})= \boldsymbol l_{1:s-2}$ 是互不相交的针贬，由概率可加性得到下面公式：

$\begin{aligned}\alpha_t(s) = \begin{cases} (\alpha_{t-1}(s-1)+\alpha_{t-1}(s))y^t_{\boldsymbol l^{\prime}_s} ,\quad &\text {if} \ \ \boldsymbol l^{\prime}_{s-2}=\boldsymbol l^{\prime}_s \ \text{or} \ \boldsymbol l^{\prime}_s=\epsilon\\ (\alpha_{t-1}(s-1)+\alpha_{t-1}(s)+\alpha_{t-1}(s-2))y^t_{\boldsymbol l^{\prime}_s}, \quad &\text{otherwise}\end{cases}\end{aligned}$

DP終止：

????????最終击费，由于在 $T$ 時刻，還沒有到達(dá)狀態(tài) $\boldsymbol l^{\prime}_{2N}$ 和 $\boldsymbol l^{\prime}_{2N+1}$ （即最后的目標(biāo)字符和最后的空白符）桦他；這樣的路徑是無效的（不包括在集合 $\mathcal B^{-1}(\boldsymbol l)$ 之內(nèi)）蔫巩，因而最終的概率為：

$p(\boldsymbol l | X)= \alpha_{T}(2N+1) + \alpha_{T}(2N)$

后向變量

????????類似可以定義后向變量 $\beta_t(s)$ 為在時刻 $t$ 處于 $\boldsymbol l$ 中的狀態(tài) $s$ ，并且后續(xù)經(jīng)過 $T-t$ 步到達(dá)終點的所有路徑上的概率總和：

$\beta_{t}(s) = \sum_{\begin{aligned} &\quad \pi \in {L^{\prime}}^T \\ &\mathcal B(\pi_{t:T})=\boldsymbol l_{s:N} \end{aligned}} \prod_{\tau=t}^{T} y^t_{\pi_{\tau}}$

????????過程初始化快压，有兩個合法的終止點：在 $T$ 時刻經(jīng)過 $\boldsymbol l^{\prime}_{2N+1}$ 的路徑圆仔，以及在 $T$ 時刻經(jīng)過 $\boldsymbol l^{\prime}_{2N}$ 的路徑顯然都只有它們自己，于是：

$\begin{aligned}&\beta_{T}(2N+1) = y^T_{\epsilon} \\&\beta_{T}(2N) = y^T_{\boldsymbol l_N} \\& \beta_{T}(s) = 0\ ,\ \forall s < 2N\end{aligned}$

并且有迭代公式：

$\begin{aligned}\beta_t(s) = \begin{cases} (\beta_{t+1}(s)+\beta_{t+1}(s+1))y^t_{\boldsymbol l^{\prime}_s} ,\quad &\text {if} \ \ \boldsymbol l^{\prime}_{s2}=\boldsymbol l^{\prime}_s \ \text{or} \ \boldsymbol l^{\prime}_s=\epsilon\\ (\beta_{t+1}(s)+\beta_{t+1}(s+1)+\beta_{t+1}(s+2))y^t_{\boldsymbol l^{\prime}_s}, \quad &\text{otherwise}\end{cases}\end{aligned}$

原論文公式的推導(dǎo)細(xì)節(jié)放在?第二部分