15.3 隱馬爾可夫模型

前一節(jié)中發(fā)展了使用一個(gè)與具體形式的轉(zhuǎn)移模型和傳感器模型無關(guān)的通用框架進(jìn)行時(shí)序概率推理的算法。在本節(jié)及緊接著的兩節(jié)中，我們討論更具體的模型與應(yīng)用，描述基本算法的能力以及在特殊情況下所允許的進(jìn)一步改進(jìn)。

我們從隱馬爾可夫模型（hidden Markov model，或縮寫為HMM）開始。隱馬爾可夫模型是用單一離散隨機(jī)變量描述過程狀態(tài)的時(shí)序概率模型。該變量的可能取值就是世界的可能狀態(tài)。所以前一節(jié)所描述的雨傘例子是一個(gè)隱馬爾可夫模型，因?yàn)樗挥幸粋€(gè)狀態(tài)變量：Raint。其他的狀態(tài)變量也可以加入到一個(gè)時(shí)序模型中，同時(shí)保持隱馬爾可夫模型框架，不過只能通過將所有的狀態(tài)變量組合成單個(gè)的“大變量”的方式實(shí)現(xiàn)，其取值范圍是全部單個(gè)狀態(tài)變量取值構(gòu)成的所有可能元組。我們將看到，這種受限的隱馬爾可夫模型結(jié)構(gòu)能夠得到所有基本算法的一種非常簡(jiǎn)單而優(yōu)雅的矩陣實(shí)現(xiàn)[22]。第 15.6節(jié)說明了隱馬爾可夫模型是如何用于語音識(shí)別的。

簡(jiǎn)化的矩陣算法

通過單個(gè)離散狀態(tài)變量Xt，我們能夠給出表示轉(zhuǎn)移模型、傳感器模型以及前向、后向消息的具體形式。令狀態(tài)變量Xt的值用整數(shù)1, …, S表示，其中S表示可能狀態(tài)的數(shù)目。轉(zhuǎn)移模型P(Xt|Xt-1)成為一個(gè)S × S的矩陣T，其中：

Ti j=P(Xt=j|Xt-1=i)

也就是說，Ti j表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率。例如，雨傘世界的轉(zhuǎn)移矩陣為：我們同樣可以將傳感器模型用矩陣形式表示。在這種情況下，由于證據(jù)變量Et的取值已知為，比如說et，我們只需要使用指定出現(xiàn)et的概率的那部分模型。對(duì)于每一個(gè)時(shí)間步t，我們可以構(gòu)造一個(gè)對(duì)角型矩陣Ot，其對(duì)角線上的條目由P(et|Xt= i)的值提供，而其他位置的條目為0。例如，在雨傘世界中的第1天，U1=true，所以根據(jù)圖15.2我們有

現(xiàn)在，如果我們用列向量表示前向消息和后向消息，則整個(gè)計(jì)算過程變成了簡(jiǎn)單的矩陣-向量運(yùn)算。前向公式（15.3）變成：

后向公式（15.7）則變成：

由這些公式，我們可以了解到應(yīng)用于長(zhǎng)度為 t 的序列時(shí)，前向-后向算法（圖 15.4）的時(shí)間復(fù)雜度是O(S2t)，因?yàn)槊恳徊蕉夹枰獙⒁粋€(gè)S元向量與一個(gè)S × S矩陣相乘。算法的空間需求為O(S t)，因?yàn)榍跋蜻^程保存了t個(gè)S元向量。

除了為隱馬爾可夫模型的濾波和平滑算法提供一種優(yōu)雅的描述以外，矩陣的形式化還揭示了改進(jìn)算法的機(jī)會(huì)。首先是前向-后向算法的一種簡(jiǎn)單變形，使算法能夠在常數(shù)空間內(nèi)完成平滑，而與序列長(zhǎng)度無關(guān)。其思想是，根據(jù)公式(15.6)，對(duì)任何特定時(shí)間片k的平滑都需要同時(shí)給出前向和后向消息，即f1: k和bk+1: t。前向-后向算法是通過將前向運(yùn)行過程中所計(jì)算出來的f保存起來以便在后向運(yùn)行過程中使用而實(shí)現(xiàn)的。實(shí)現(xiàn)這一目標(biāo)的另一種方法是在單一運(yùn)行過程里同時(shí)向相同的方向傳遞f和b。例如，如果我們讓公式(15.10)從另一個(gè)方向執(zhí)行，“前向”消息f也可以后向傳遞：

修改后的平滑算法首先執(zhí)行標(biāo)準(zhǔn)的前向過程計(jì)算ft : t（拋棄所有的中間結(jié)果），然后對(duì)b和f同時(shí)執(zhí)行后向過程，用它們來計(jì)算每一時(shí)間步的平滑估計(jì)。因?yàn)槊總€(gè)消息都只需要一份拷貝，存儲(chǔ)需求就是不變的（即與序列長(zhǎng)度t無關(guān)）。不過這個(gè)算法有一個(gè)顯著的限制：它要求轉(zhuǎn)移矩陣必須是可逆的，并且傳感器模型沒有零元素——也就是說，所有觀察值在每個(gè)狀態(tài)下都是可能的。

通過矩陣形式化揭示出可改進(jìn)的第二個(gè)方面是使用具有固定延遲的聯(lián)機(jī)平滑。平滑能夠在常數(shù)空間里實(shí)現(xiàn)的事實(shí)提示我們，聯(lián)機(jī)平滑應(yīng)該也存在一種高效的遞歸算法——即一種時(shí)間復(fù)雜度與延遲長(zhǎng)度無關(guān)的的算法。讓我們假設(shè)延遲為d，我們要對(duì)時(shí)間片t?d進(jìn)行平滑，這里t表示當(dāng)前時(shí)間。根據(jù)公式（15.6）我們需要為時(shí)間片t?d計(jì)算

α f1:t?dbt?d+1:t

然后，當(dāng)有了新的觀察后，我們需要為時(shí)間片t?d+1計(jì)算

α f1:t?d+1 bt?d+2:t+1

這是如何通過增量的方式實(shí)現(xiàn)的？首先，我們可以通過標(biāo)準(zhǔn)的濾波過程，即公式（15.3）由f1: t?d計(jì)算f1: t?d+1。

增量計(jì)算后向消息則需要更多的技巧，因?yàn)樵谂f的后向消息bt?d+1: t和新的后向消息bt?d+2 : t+1之間并不存在簡(jiǎn)單關(guān)系。反過來，我們將檢查舊的后向消息bt?d+1: t和序列前端的后向消息bt+1: t。為了實(shí)現(xiàn)這一點(diǎn)，我們將公式（15.11）應(yīng)用d次得到：

其中矩陣Bt-d+1: t為T和O矩陣序列的乘積。B可以被認(rèn)為是一個(gè)“變換算子”，它將后來的后向消息變換成早先的后向消息。當(dāng)有了下一個(gè)觀察之后，對(duì)于新的后向消息有類似的公式成立：

考察公式（15.12）和公式（15.13）中的乘積表達(dá)式，我們發(fā)現(xiàn)它們有一個(gè)簡(jiǎn)單關(guān)系：要得到第二個(gè)乘積，只要用第一個(gè)乘積“除以”第一項(xiàng) TOt?d+1，然后再乘以新的最后一項(xiàng) TOt+1。那么，在矩陣語言中，在新舊B矩陣之間有一個(gè)簡(jiǎn)單關(guān)系：

這個(gè)公式提供了對(duì)B矩陣的增量更新，并進(jìn)而（通過公式（15.13））允許我們計(jì)算新的后向消息bt-d+2: t+1。圖15.6中顯示了保存和更新f與B的完整算法。

圖15.6 具有固定的d步時(shí)間延遲的平滑算法，作為一種能夠在給定新時(shí)間步的觀察下輸出新的平滑估計(jì)的聯(lián)機(jī)算法而實(shí)現(xiàn)