動態(tài)貝葉斯網(wǎng)絡(luò) Dynamic Bayesian Networks?

Dynamic Bayesian Networks

動態(tài)貝葉斯網(wǎng)絡(luò)

https://webdocs.cs.ualberta.ca/~rgreiner/C-366/RG-2002-SLIDES/dbn-murphy.pdf

概述

Dynamic Bayesian Networks 是一篇綜述性論文，其核心重點在于系統(tǒng)地介紹和分析動態(tài)貝葉斯網(wǎng)絡(luò)這一強大的概率圖模型框架。

文章的主要內(nèi)容和重點可以概括為以下幾點：

1. 統(tǒng)一框架的建立：文章旨在將多種廣泛應(yīng)用于時間序列建模和推斷的模型（如隱馬爾可夫模型HMM、卡爾曼濾波KF、狀態(tài)空間模型SSM、因子化HMM、耦合HMM、分層HMM等）納入一個統(tǒng)一的DBN框架下進行理解和比較。這有助于揭示不同模型之間的內(nèi)在聯(lián)系和區(qū)別。

2. 核心算法與推斷：深入探討了在DBN中進行高效推斷的核心算法，特別是前向-后向算法及其各種變體（如廣義α-β算法、對數(shù)空間平滑、常數(shù)空間平滑），并分析了它們的時間和空間復(fù)雜度。此外，還介紹了更高級的推斷技術(shù)，如基于連接樹的精確推斷、粒子濾波（包括Rao-Blackwell化）、期望傳播和結(jié)構(gòu)化變分近似等。

3. 模型擴展與應(yīng)用：討論了DBN的各種擴展形式，例如：

   • 切換狀態(tài)空間模型 (Switching SSMs)

     ：用于故障診斷等場景。

   • 二維HMMs

     ：用于處理圖像等二維數(shù)據(jù)。

   • 分層HMMs (HHMMs)

     ：用于建模具有層次結(jié)構(gòu)的時間序列。

   • 埋藏式馬爾可夫模型 (Buried Markov Models)

     ：允許觀測節(jié)點間存在非線性依賴。

4. 歷史沿革與文獻綜述：文章通過詳盡的參考文獻，梳理了DBN及相關(guān)概念（如HMM、KF、粒子濾波等）的發(fā)展歷史和重要里程碑，為讀者提供了豐富的背景知識和研究脈絡(luò)。

5. 理論與實踐結(jié)合：不僅闡述了理論基礎(chǔ)和算法原理，還通過具體的例子（如雙水箱系統(tǒng)故障診斷、語音識別、機器人導(dǎo)航、SLAM等）展示了DBN在實際工程問題中的強大建模能力和應(yīng)用價值。

總而言之，本文的重點是構(gòu)建一個全面、系統(tǒng)的DBN知識體系，從基礎(chǔ)概念、核心算法到高級擴展和實際應(yīng)用，旨在為研究者和工程師提供一個理解和運用這一強大工具的權(quán)威指南。

1 引言

第??章介紹了隱馬爾可夫模型（HMMs），第??章介紹了狀態(tài)空間模型（SSMs）；這兩類模型雖廣為使用，但在建模序列數(shù)據(jù)時仍顯不夠靈活。本章將探討更為復(fù)雜的模型。其核心推廣在于：將隱狀態(tài)表示為一組隨機變量，而非單一隨機變量；類似地，觀測也可采用因子化（factorized）或分布式（distributed）方式加以表示。隨后，我們可借助圖模型來刻畫這些變量之間的條件獨立性——既包括同一時刻（within-slice）的變量間關(guān)系，也包括跨時刻（across time steps）的依賴結(jié)構(gòu)。

序列數(shù)據(jù)主要有兩種形式：

• 時序（時間序列）數(shù)據(jù) ：由某種因果過程依次生成；
• 序列數(shù)據(jù) （例如生物序列或自然語言）：我們對其生成機制持更開放（agnostic）的態(tài)度。

對于時序數(shù)據(jù)建模，采用有向圖模型（directed graphical models）是自然的選擇，因其能體現(xiàn)時間單向流動的特性。“時間片內(nèi)”（within a time-slice）的弧可為有向或無向，用以刻畫變量間的“瞬時”相關(guān)性；若所有弧——包括片內(nèi)與片間——均為有向，則該模型稱為動態(tài)貝葉斯網(wǎng)絡(luò)（Dynamic Bayesian Network, DBN）。此處“動態(tài)”意指我們所建模的是一個動態(tài)系統(tǒng)，并非指圖結(jié)構(gòu)隨時間變化。DBN因其易于解釋與學(xué)習(xí)而廣受歡迎：由于圖結(jié)構(gòu)是有向的，每個節(jié)點的條件概率分布（CPD）可被獨立估計。本章將聚焦于DBN。

對于非時序的序列數(shù)據(jù)建模，既可采用有向圖模型，也可采用無向圖模型。本章關(guān)于時序模型的離線推斷（offline inference）討論，多數(shù)同樣適用于非時序模型；而所介紹的在線推斷（online inference）方法雖主要面向時序模型，亦可用于靜態(tài)模型的序列學(xué)習(xí)（sequential learning）——當(dāng)數(shù)據(jù)具有非平穩(wěn)性或規(guī)模過大、難以采用批處理（batch）方法時，這一能力尤為有用。

本章暫不涉及學(xué)習(xí)問題（參數(shù)估計與模型選擇），因相關(guān)技術(shù)僅是對靜態(tài)模型學(xué)習(xí)方法的直接拓展。此外，序列決策問題（即控制或強化學(xué)習(xí)）的討論將延至第??章。

2 表示

2.1 具有混合高斯輸出的隱馬爾可夫模型

2.2 自回歸隱馬爾可夫模型

2.3 混合記憶馬爾可夫模型

2.4 階乘隱馬爾可夫模型

因此，自由參數(shù)，即方程右側(cè)的成對轉(zhuǎn)移矩陣，以一種難以拆解的方式組合在一起：見圖8。相比之下，如果所有的條件概率分布（CPD）都是線性高斯的，那么得到的聯(lián)合分布是一個多元高斯分布，稀疏的圖形結(jié)構(gòu)對應(yīng)于傳統(tǒng)意義上具有許多零的稀疏矩陣：見第2.9節(jié)。

2.5 耦合隱馬爾可夫模型（Coupled HMMs）

2.6 變時隱馬爾可夫模型（Variable-duration (semi-Markov) HMMs）

2.7 段模型

段模型的基本思想是每個隱馬爾可夫模型（HMM）狀態(tài)可以生成一系列觀測值，如圖12所示，而不僅僅是單個觀測值。與變時隱馬爾可夫模型（variable-duration HMM）的區(qū)別在于，我們不假設(shè)每個段內(nèi)的觀測值是條件獨立的；相反，我們可以使用任意模型來表示它們的聯(lián)合分布。似然性由以下公式給出：

2.8 層級隱馬爾可夫模型（HHMMs）

層級隱馬爾可夫模型（HHMM）是段隱馬爾可夫模型（segment HMM）的推廣。它允許段隱馬爾可夫模型以層級方式由段子隱馬爾可夫模型組成。圖15展示了基本概念的示意圖。此外，不是用隨機變量指定每個段的長度，而是通過子隱馬爾可夫模型進入其結(jié)束狀態(tài)所需的時間隱式定義長度。（到結(jié)束狀態(tài)的轉(zhuǎn)換可能由某些環(huán)境條件觸發(fā)。）進入結(jié)束狀態(tài)會終止該段，并將控制權(quán)返回給調(diào)用狀態(tài)，然后調(diào)用狀態(tài)可以自由變化。

調(diào)用上下文被存儲在一個深度受限的棧上。因此，HHMM比隨機上下文無關(guān)文法（SCFGs）和遞歸轉(zhuǎn)移網(wǎng)絡(luò)（RTNs）的表達能力要弱，后者都可以處理無界深度的遞歸。然而，HHMM對于許多實際問題已經(jīng)足夠表達能力強，這些問題通常只涉及尾遞歸（即，自轉(zhuǎn)移到一個抽象狀態(tài)）。此外，HHMM可以比SCFGs更高效地進行計算。特別是，SCFGs的推理算法稱為內(nèi)外算法，其時間復(fù)雜度為，而我們可以使用第3節(jié)中討論的任何技術(shù)在 時間內(nèi)對HHMM進行推理。

2.8.1 HHMMs的應(yīng)用

HHMMs 最明顯的應(yīng)用是語音識別。很自然地可以將單詞視為由音素組成，這些音素產(chǎn)生子音素，從而產(chǎn)生聲學(xué)信號。在實踐中，從單詞到音素的映射由音素字典固定，而從音素到聲學(xué)的映射則通過假設(shè)一個具有高斯輸出混合的三態(tài)左-右HMM來固定。因此，整個層次結(jié)構(gòu)可以“折疊”成一個扁平的HMM，適當(dāng)?shù)膮?shù)綁定表示層次結(jié)構(gòu)的底層可以在不同的更高層次上下文中重用。然而，如果對學(xué)習(xí)層次分解感興趣，HHMM可能會很有用。有關(guān)語音識別的更多信息，請參見第 ?? 章。

HHMMs的另一個應(yīng)用是移動機器人的地圖學(xué)習(xí)。很自然地可以將類似室內(nèi)辦公室的環(huán)境視為由走廊和房間組成，而這些又由更細粒度的位置組成。對于這個應(yīng)用，有必要對模型進行一些修改。首先，我們通常根據(jù)機器人執(zhí)行的動作來條件化所有狀態(tài)轉(zhuǎn)換。其次，更微妙的是，當(dāng)我們離開一個抽象狀態(tài)（例如，走廊）時，新的具體狀態(tài)（例如，走廊內(nèi)的位置）取決于舊的具體狀態(tài)，即，并不是所有的舊上下文在退出時都被“從棧中彈出”。（換句話說，走廊模型不是上下文無關(guān)的。）相反，我們根據(jù)舊狀態(tài)的某個函數(shù)來條件化新的起始狀態(tài)。我們把細節(jié)留作練習(xí)。

2.9 狀態(tài)空間模型

狀態(tài)空間模型（SSM）的圖結(jié)構(gòu)看起來與隱馬爾可夫模型（HMM）的圖結(jié)構(gòu)相同，因為它做出了相同的條件獨立性假設(shè)。通常還會包括一個輸入節(jié)點，如圖18所示。在狀態(tài)空間模型中，所有節(jié)點都是連續(xù)的，所有的條件概率分布（CPDs）都是線性高斯的，即，

2.10 聯(lián)合狀態(tài)參數(shù)估計

在線參數(shù)估計問題可以通過將參數(shù)添加到狀態(tài)空間來表示。

例如，假設(shè)我們想要遞歸地（即順序地）估計線性回歸模型中的系數(shù) α，其中我們假設(shè)噪聲水平 R 是已知的。這可以如圖20所示進行建模。條件概率分布（CPDs）如下：

2.11 切換狀態(tài)空間模型（Switching SSMs）

在圖22中，我們展示了一個切換狀態(tài)空間模型（也稱為切換線性動態(tài)系統(tǒng)（LDS）、跳躍馬爾可夫模型、跳躍線性系統(tǒng)、條件動態(tài)線性模型（DLM）等）。基本思想是模型可以在不同類型的動態(tài)“模式”或“狀態(tài)”之間切換。（由此產(chǎn)生的分段線性是近似非線性動態(tài)的一種方式。）這些模式本身的動態(tài)由一個離散狀態(tài)馬爾可夫鏈控制。因此，條件概率分布（CPDs）如下：

由于該模型同時具有離散和連續(xù)的隱藏變量，因此有時被稱為混合動態(tài)貝葉斯網(wǎng)絡(luò)（DBN）。在這種模型中進行精確推斷是非常困難的，正如我們在第5.2.4節(jié)中討論的那樣。與自回歸隱馬爾可夫模型（HMM）（第2.2節(jié)）形成對比，后者所有隱藏變量都是離散的，使得精確推斷變得容易。

2.11.1 數(shù)據(jù)關(guān)聯(lián)

由于其軍事重要性，已經(jīng)投入了大量精力來解決在混亂環(huán)境中跟蹤多個目標的問題。詳見第5.5節(jié)以獲取進一步討論。

3 推理

在觀察了大量不同的動態(tài)貝葉斯網(wǎng)絡(luò)（DBNs）之后，我們現(xiàn)在討論如何在這些模型中執(zhí)行推斷。我們可能感興趣的推斷問題有多種（參見圖24以獲取摘要）：

我們將專注于在線過濾和離線平滑；其他問題可以通過類似的方法解決。區(qū)分所有隱藏節(jié)點都是離散的模型和一些（或全部）隱藏節(jié)點是連續(xù)的模型會很有幫助，因為它們需要不同的解決技術(shù)（正如我們在HMM中的推斷與SSM中的推斷需要不同的技術(shù)一樣）。

4 離散狀態(tài)模型中的精確推斷

4.1 前向-后向算法

4.2 展開的連接樹

不幸的是，當(dāng)我們從展開的DBN創(chuàng)建一個連接樹時，團（cliques）往往非常大，這常常使得精確推斷變得難以處理。特別是，對于每個時間切片（可能除了序列的開始和結(jié)束附近），通常會有一個團包含該切片中所有具有跨切片連接的節(jié)點。（我們將在下面更詳細地說明）。參見圖25中的一個例子。圖26說明了這一點的直觀原因：即使切片內(nèi)的節(jié)點沒有直接相關(guān)，它們最終也會因為共享過去的共同祖先而變得相關(guān)。

4.2.1 約束消除排序

4.2.2 無約束消除排序

如果我們使用無約束的消除排序會發(fā)生什么？原則上我們可以做得更好。然而，實際上這種情況很少發(fā)生。回想一下，找到最優(yōu)的消除排序是NP難的。因此，大多數(shù)消除排序是使用局部搜索算法計算的。經(jīng)驗上，許多研究人員發(fā)現(xiàn)，在受限的空間中進行搜索通常會提高找到的局部最優(yōu)解的質(zhì)量。例如，無約束算法可能會選擇在每個切片中依次消除第一個節(jié)點，然后是第二個，等等，創(chuàng)建跨越許多時間切片的寬“水平”團，而不是在時間上局部化的窄“垂直”團。這樣的水平排序通常比垂直排序有更大的團大小（對于足夠大的 T），因此不會被一個好的搜索算法選擇。然而，一個貪婪搜索算法（例如，基于最小填充啟發(fā)式）可能很容易選擇這樣的次優(yōu)排序。

無約束排序的另一個問題是以下內(nèi)容。我們不希望每次改變序列長度時都不得不計算一個新的消除排序，因為這太慢了。相反，我們希望對一個固定大小的DBN進行三角化，識別結(jié)果連接樹中的團，然后通過復(fù)制重復(fù)結(jié)構(gòu)來重用它們，適用于所有序列長度。為了確保連接樹中出現(xiàn)這樣的重復(fù)結(jié)構(gòu)，我們必須使用時間上受限的消除排序。即便如此，涉及動態(tài)改變連接樹結(jié)構(gòu)的簿記工作也變得相當(dāng)棘手。

4.3 前沿算法

4.4 接口算法

4.5 條件可追蹤子結(jié)構(gòu)

5 近似過濾

5.1 信念狀態(tài) = 離散分布

直觀上，即使投影在每個時間步引入了錯誤，轉(zhuǎn)換的隨機性質(zhì)和觀測的信息性質(zhì)足以減少錯誤，以防止其累積。

BK算法的準確性取決于我們用來近似信念狀態(tài)的簇。精確推斷對應(yīng)于使用一個包含所有接口節(jié)點的單個簇。最具侵略性的近似對應(yīng)于每個變量使用一個簇（“完全分解”近似）。

5.1.2 束搜索

一種完全不同的近似方法是假設(shè)只有少量可能的假設(shè)。從每個這樣可能的先驗狀態(tài)，我們嘗試找到下一個最可能的狀態(tài)集合。我們可以保留 k 個最可能的狀態(tài)，或者保留足夠的狀態(tài)以確保我們覆蓋了足夠多的概率質(zhì)量。這種方法在語音識別中廣泛使用，我們只跟蹤句子最可能的解釋，以及在故障診斷中，我們只跟蹤最可能的故障。

5.2 信念狀態(tài) = 高斯分布

5.2.1 卡爾曼濾波器（KF）

我們可以通過使用第4節(jié)中討論的連接樹算法，并將求和、乘法和除法的定義修改為可以應(yīng)用于高斯勢而不是離散勢，從而將卡爾曼濾波方程推廣到任何線性高斯DBN。

5.2.2 擴展卡爾曼濾波器（EKF）

擴展卡爾曼濾波器（EKF）可以應(yīng)用于形式如下的模型：

其中 f 和 g 是任意可微函數(shù)。基本思想是使用二階泰勒展開將 f 和 g 在先前的狀態(tài)估計上進行線性化，然后應(yīng)用標準的卡爾曼濾波器方程。（方程中的噪聲方差（Q 和 R）不變，即，由于線性化而產(chǎn)生的額外誤差沒有被建模。）因此，我們用非平穩(wěn)線性動態(tài)系統(tǒng)來近似平穩(wěn)非線性動態(tài)系統(tǒng)。也就是說，在時間 t，我們通過以下方式近似模型：

我們可以看到，UKF是對標準KF的簡單修改，但可以比EKF更準確地處理非線性，而無需計算導(dǎo)數(shù)。

5.2.4 假設(shè)密度濾波器（ADF）/ 矩匹配濾波器

我們已經(jīng)在第5.1.1節(jié)中遇到了ADF，其中我們假設(shè)信念狀態(tài)可以表示為離散邊際的乘積。在本節(jié)中，我們假設(shè)信念狀態(tài)由高斯分布表示。目標是找到這個高斯分布的參數(shù)。

例如，考慮一個具有線性高斯動態(tài)但非線性、非高斯觀測的系統(tǒng)（例如，高斯混合模型，這不能通過EKF或UKF處理）。我們從一個近似高斯先驗開始：

5.3 信念狀態(tài) = 高斯混合

5.4 信念狀態(tài) = 樣本集合（粒子濾波）

粒子濾波的基本思想是通過一組加權(quán)粒子或樣本來近似信念狀態(tài)：

5.4.1 重采樣步驟

到目前為止描述的算法被稱為序貫重要性采樣（SIS）。SIS的一個眾所周知的問題是，隨著時間的推移，一個歸一化的重要性權(quán)重趨向于1，而其他權(quán)重趨向于零（即使我們使用最優(yōu)的提議分布：參見第5.4.2節(jié)）。因此，大量樣本實際上被浪費了，因為它們的權(quán)重可以忽略不計。這被稱為粒子“貧化”。

“有效”樣本數(shù)量的估計由以下公式給出：

對于預(yù)測未來，從轉(zhuǎn)移先驗中采樣是足夠的，因為沒有未來的證據(jù)。但對于監(jiān)控/過濾來說，這并不高效，因為這相當(dāng)于“猜直到猜對”。例如，如果轉(zhuǎn)換具有高度隨機性，從先驗中采樣將導(dǎo)致粒子在整個狀態(tài)空間中被提出；如果觀測具有高度信息性，大多數(shù)粒子將被“淘汰”（即，被賦予低權(quán)重）。在這種情況下，首先查看證據(jù) ，然后提出建議更有意義：

5.4.3 拉奧-布萊克韋爾化粒子濾波（RBPF）

拉奧-布萊克韋爾定理展示了如何在每個凸損失函數(shù)下改進任何給定的估計器。其核心是以下眾所周知的恒等式：

修改后的算法如圖444所示。這比從轉(zhuǎn)移先驗中采樣更昂貴，因為對于每個粒子 i，我們必須遍歷所有狀態(tài) s 以計算提議分布。然而，這可能需要更少的粒子，從而總體上更快。

5.4.4 DBN的粒子濾波

結(jié)合粒子濾波與分解的信念狀態(tài) 可以將粒子濾波與Boyen-Koller算法（參見第5.1.1節(jié)）結(jié)合使用，即通過

5.5 信念狀態(tài) = 可變大小

在某些應(yīng)用中，狀態(tài)空間的大小事先不是固定的。例如，當(dāng)我們跟蹤多個對象時，每個測量可能由它們中的任何一個引起，背景，或者可能是進入“場景”的新對象。這個問題出現(xiàn)在視覺跟蹤、雷達跟蹤導(dǎo)彈以及移動機器人中，特別是在SLAM（同時定位與地圖構(gòu)建）問題中。

檢測新對象存在的標準啟發(fā)式方法是，如果觀測出現(xiàn)在未預(yù)期的位置。如果我們對每個對象的位置有先驗，我們可以計算預(yù)期測量位置的分布：

如果這些密度是高斯分布，這通常表示為置信橢圓或驗證門。如果觀測值落在這個橢圓內(nèi)，我們假設(shè)它是由對象生成的。如果橢圓內(nèi)有多個觀測值，或者觀測值落在多個橢圓內(nèi)，我們可以將觀測值分配給最近的（使用馬氏距離）目標，或者計算所有可能的觀測值到目標的聯(lián)合分配的似然度，并選擇最有可能的一個（注意，最近鄰規(guī)則可能會將相同的測量值分配給多個對象，這會導(dǎo)致不準確）。

如果觀測值沒有落在任何現(xiàn)有對象的驗證門內(nèi)，它可能是由于新對象，或者是由于背景干擾。因此我們考慮這兩種假設(shè)，并將新對象添加到臨時列表中。一旦臨時列表中的對象在其驗證門內(nèi)接收到最小數(shù)量的測量值，它就被添加到狀態(tài)空間中。

對象也可能從狀態(tài)空間中被移除，如果它最近沒有更新（例如，它離開了場景）。因此，一般來說，我們必須允許狀態(tài)空間動態(tài)地增長和收縮。

在這種可變大小狀態(tài)空間模型中進行推斷的更嚴格方法是使用粒子濾波。這很容易，因為每個粒子可以有不同的維度。我們在下面詳細舉例說明，在線模型選擇的背景下。

6 近似平滑

有兩種主要類型的近似平滑算法：那些對數(shù)據(jù)進行單次前后向通過的算法（雙濾波平滑器），以及那些進行多次通過的算法。精確推斷算法只需要進行一次前后向通過，但在一般情況下，如果允許進行多次通過，近似推斷可以實現(xiàn)更好的結(jié)果。我們將簡要討論以下各種算法。

6.1 雙濾波平滑

無跡卡爾曼平滑器 可以對后向通過的 β 或 γ 版本應(yīng)用無跡變換，得到無跡卡爾曼平滑器。我們把細節(jié)留作練習(xí)。

ADF/矩匹配平滑器 我們將在第6.1.3節(jié)的切換SSM中討論矩匹配平滑器的上下文中，以及第6.2節(jié)的期望傳播上下文中討論。

6.1.3 信念狀態(tài) = 高斯混合

GPB2濾波對應(yīng)于以下連接樹中的收集操作，我們使用弱邊緣化從高斯混合中邊緣化離散節(jié)點：

6.2 期望傳播（EP）

期望傳播將假設(shè)密度濾波（第5.2.4節(jié)）推廣到批處理的上下文中。它對貝葉斯更新的順序不太敏感，因為它可以在其他項的上下文中來回優(yōu)化整體似然度的每個項。我們在下面更詳細解釋這一點。

回想一下，在ADF中，精確的后驗概率由以下公式給出：

EP的另一個應(yīng)用是迭代BK算法。這允許算法從早期通過中不正確的獨立性假設(shè)中恢復(fù)。通常2-3次通過足以提高性能。

6.3 變分式方法

變分式方法在第？？章中討論，可以以直接的方式應(yīng)用于DBN。其中一些方法，如結(jié)構(gòu)化變分近似和變分EM，使用第4節(jié)中的精確推斷程序作為子程序。

由于在此模型中精確推斷是難以處理的，我們選擇以下形式的可處理近似：

對該模型的一些簡單實驗表明，使用確定性退火的變分近似與ADF算法（未退火EP）的性能相當(dāng)；如果不進行退火，性能會差得多。

6.4 吉布斯采樣

一般來說，MCMC方法和吉布斯采樣在第？？章中討論，可以直接應(yīng)用于DBN。其中一些方法，如結(jié)構(gòu)化變分近似和變分EM，使用第4節(jié)中的精確推斷程序作為子程序。

一個可能使用此方法的示例是在切換SSM中。（在這種情況下，使用吉布斯采樣而不是EP或變分方法的優(yōu)勢是，算法最終可能會收斂到正確答案。）基本算法如下：

7 練習(xí)

7.1 隱馬爾可夫模型

“埋藏式”馬爾可夫模型通過允許可觀測節(jié)點之間存在非線性依賴關(guān)系，推廣了自回歸HMMs（第2.2節(jié)）。此外，依賴關(guān)系的性質(zhì)會根據(jù)Qt的取值而改變：參見圖51中的示例。此類模型被稱為動態(tài)貝葉斯“多網(wǎng)絡(luò)”，因為它是不同網(wǎng)絡(luò)的混合體。討論為在這些模型中進行推斷，前向-后向算法需要做出哪些（如有）修改。

7.2 二維HMMs

考慮為掃描文本等二維數(shù)據(jù)定義似然函數(shù)。自然地，可以使用一個HMM對圖像的每一行建模，并使用另一個HMM對行與行之間的連接進行建模。這被稱為偽二維或嵌入式HMM。基本思想如圖52所示，其中我們有2行，每行長度為3。

1. 此模型與第2.7節(jié)討論的分段HMMs有何關(guān)系？

2. 為偽二維HMMs推導(dǎo)一種高效的基于消息傳遞的推斷算法。提示：首先計算每行的似然度，然后在頂層HMM中使用這些似然度；在反向傳遞過程中，利用自上而下的信息在每一行-HMM內(nèi)進行完整的平滑處理。

3. 通過修改第2.5節(jié)中的耦合HMM，推導(dǎo)出一個真正的二維“HMM”，使得每個節(jié)點都依賴于其上方和左側(cè)最近的鄰居。（此類模型有時被稱為“因果”MRF。）

4. 在真正的二維HMM中，精確推斷的復(fù)雜度是多少？

5. 與傳統(tǒng)的無向MRF相比，因果MRF有哪些優(yōu)缺點？

7.3 分層HMMs

本練習(xí)要求你為HHMM的DBN表示定義CPDs。我們分別考慮層次結(jié)構(gòu)的底層、中層和頂層（因為它們具有不同的局部拓撲結(jié)構(gòu)），以及第一個、中間和最后一個時間切片。

7.4 故障診斷

切換狀態(tài)空間模型（SSMs）的一個重要應(yīng)用是用于故障診斷。例如，考慮圖53中的“雙水箱”系統(tǒng)，這是故障診斷領(lǐng)域的一個基準問題（盡管通常人們會考慮n個水箱，其中n遠大于2）。這是一個非線性系統(tǒng)，因為流量 = 壓力 / 阻力（或流量 = 壓力 × 電導(dǎo)率）。更成問題的是，阻力值可能會緩慢漂移，或因管道破裂而發(fā)生不連續(xù)變化。此外，傳感器也可能間歇性失效并給出錯誤結(jié)果。請說明如何將此模型表示為動態(tài)貝葉斯網(wǎng)絡(luò)（DBN）。

7.5 廣義 α ? β 算法

基于第4.4節(jié)中的廣義 α ? γ 算法，推導(dǎo)一個廣義 α ? β 算法。前向傳遞過程將完全相同，但后向傳遞過程應(yīng)計算HMMs中公式(12.44)的類似形式：

討論這兩種算法的相對優(yōu)劣。

7.6 對數(shù)空間平滑

本練習(xí)開發(fā)了一種前向-后向算法的版本，該算法在 O(S log T) 的工作空間內(nèi)計算 P(X? | y?:?)，而非 O(ST) 的空間（忽略表示算法輸入和輸出所需的空間）。這對于從長序列中學(xué)習(xí)模型很有用，因為充分統(tǒng)計量 Σ? P(X? | y?:?) 可以存儲在常數(shù)空間內(nèi)。

1. 為簡化起見，假設(shè) T 為奇數(shù)，并令中點 h = (T + 1)/2。證明：對于 t = 1 : h，僅憑 α?、β??? 和 y?:? 即可計算出 P(X? | y?:?)。

2. 對序列的后半部分證明類似的結(jié)果。

3. 基于上述結(jié)果，可以通過首先沿序列正向運行，然后從末尾反向運行，并僅在中間點和端點處存儲所需的消息來構(gòu)建一個分治算法。然后，在左右兩半上遞歸調(diào)用該算法。請詳細寫出該算法。

4. 證明空間復(fù)雜度為 O(S log T)，其中 S 是 α 或 β 消息的大小。時間復(fù)雜度是多少？

5. 如果我們將序列劃分為 k > 2 個部分，復(fù)雜度會如何變化？哪個 k 值能產(chǎn)生最小的空間占用？如果愿意等待的時間最多是標準算法的兩倍，應(yīng)使用哪個 k 值？

7.7 常數(shù)空間平滑

1. 給定一個 O(T2) 算法，該算法在常數(shù)空間內(nèi)計算所有 t 對應(yīng)的 P(X? | y?:?)（忽略表示輸入和輸出所需的空間）。

2. 假設(shè)我們可以對前向算子進行求逆，使得 α? = Fwd?1(α???, y???)。說明我們?nèi)绾卫眠@一點在 O(1) 空間和 O(T) 時間內(nèi)計算所有 t 對應(yīng)的 P(X? | y?:?)。提示：將 β???|? 表示為矩陣乘積再乘以 β???|? = 1；類似地，將 β?????|??? 表示為矩陣乘積再乘以 β???|??? = 1；然后找出它們之間的關(guān)系。

3. 解釋為什么一般來說前向（和后向）算子不可逆。給出一個反例。

7.8 BK 算法

修改圖34中的前向算子，使其輸入為因子化的先驗 α???，并輸出因子化的后驗 α?。

https://webdocs.cs.ualberta.ca/~rgreiner/C-366/RG-2002-SLIDES/dbn-murphy.pdf