Dynamic Bayesian Networks

動態貝葉斯網絡

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

概述

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

文章的主要內容和重點可以概括為以下幾點：

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

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

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

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

     ：用于故障診斷等場景。

   • 二維HMMs

     ：用于處理圖像等二維數據。

   • 分層HMMs (HHMMs)

     ：用于建模具有層次結構的時間序列。

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

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

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

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

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

1 引言

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

序列數據主要有兩種形式：

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

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

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

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

2 表示

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

2.2 自回歸隱馬爾可夫模型

2.3 混合記憶馬爾可夫模型

2.4 階乘隱馬爾可夫模型

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

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

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

2.7 段模型

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

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

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

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

2.8.1 HHMMs的應用

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

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

2.9 狀態空間模型

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

2.10 聯合狀態參數估計

在線參數估計問題可以通過將參數添加到狀態空間來表示。

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

2.11 切換狀態空間模型（Switching SSMs）

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

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

2.11.1 數據關聯

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

3 推理

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

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

4 離散狀態模型中的精確推斷

4.1 前向-后向算法

4.2 展開的連接樹

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

4.2.1 約束消除排序

4.2.2 無約束消除排序

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

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

4.3 前沿算法

4.4 接口算法

4.5 條件可追蹤子結構

5 近似過濾

5.1 信念狀態 = 離散分布

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

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

5.1.2 束搜索

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

5.2 信念狀態 = 高斯分布

5.2.1 卡爾曼濾波器（KF）

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

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

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

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

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

5.2.4 假設密度濾波器（ADF）/ 矩匹配濾波器

我們已經在第5.1.1節中遇到了ADF，其中我們假設信念狀態可以表示為離散邊際的乘積。在本節中，我們假設信念狀態由高斯分布表示。目標是找到這個高斯分布的參數。

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

5.3 信念狀態 = 高斯混合

5.4 信念狀態 = 樣本集合（粒子濾波）

粒子濾波的基本思想是通過一組加權粒子或樣本來近似信念狀態：

5.4.1 重采樣步驟

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

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

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

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

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

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

5.4.4 DBN的粒子濾波

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

5.5 信念狀態 = 可變大小

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

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

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

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

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

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

6 近似平滑

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

6.1 雙濾波平滑

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

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

6.1.3 信念狀態 = 高斯混合

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

6.2 期望傳播（EP）

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

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

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

6.3 變分式方法

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

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

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

6.4 吉布斯采樣

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

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

7 練習

7.1 隱馬爾可夫模型

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

7.2 二維HMMs

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

1. 此模型與第2.7節討論的分段HMMs有何關系？

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

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

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

5. 與傳統的無向MRF相比，因果MRF有哪些優缺點？

7.3 分層HMMs

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

7.4 故障診斷

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

7.5 廣義 α ? β 算法

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

討論這兩種算法的相對優劣。

7.6 對數空間平滑

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

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

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

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

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

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

7.7 常數空間平滑

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

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

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

7.8 BK 算法

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

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