Dynamic Bayesian Networks

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

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

概述

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

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

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

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

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

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

     ：用于故障診斷等場(chǎng)景。

   • 二維HMMs

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

   • 分層HMMs (HHMMs)

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

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

     ：允許觀(guān)測(cè)節(jié)點(diǎn)間存在非線(xiàn)性依賴(lài)。

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

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

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

1 引言

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

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

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

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

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

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

2 表示

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

2.2 自回歸隱馬爾可夫模型

2.3 混合記憶馬爾可夫模型

2.4 階乘隱馬爾可夫模型

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

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

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

2.7 段模型

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

2.8 層級(jí)隱馬爾可夫模型（HHMMs）

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

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

2.8.1 HHMMs的應(yīng)用

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

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

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

狀態(tài)空間模型（SSM）的圖結(jié)構(gòu)看起來(lái)與隱馬爾可夫模型（HMM）的圖結(jié)構(gòu)相同，因?yàn)樗龀隽讼嗤臈l件獨(dú)立性假設(shè)。通常還會(huì)包括一個(gè)輸入節(jié)點(diǎn)，如圖18所示。在狀態(tài)空間模型中，所有節(jié)點(diǎn)都是連續(xù)的，所有的條件概率分布（CPDs）都是線(xiàn)性高斯的，即，

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

在線(xiàn)參數(shù)估計(jì)問(wèn)題可以通過(guò)將參數(shù)添加到狀態(tài)空間來(lái)表示。

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

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

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

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

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

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

3 推理

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

我們將專(zhuān)注于在線(xiàn)過(guò)濾和離線(xiàn)平滑；其他問(wèn)題可以通過(guò)類(lèi)似的方法解決。區(qū)分所有隱藏節(jié)點(diǎn)都是離散的模型和一些（或全部）隱藏節(jié)點(diǎn)是連續(xù)的模型會(huì)很有幫助，因?yàn)樗鼈冃枰煌慕鉀Q技術(shù)（正如我們?cè)贖MM中的推斷與SSM中的推斷需要不同的技術(shù)一樣）。

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

4.1 前向-后向算法

4.2 展開(kāi)的連接樹(shù)

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

4.2.1 約束消除排序

4.2.2 無(wú)約束消除排序

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

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

4.3 前沿算法

4.4 接口算法

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

5 近似過(guò)濾

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

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

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

5.1.2 束搜索

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

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

5.2.1 卡爾曼濾波器（KF）

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

5.2.2 擴(kuò)展卡爾曼濾波器（EKF）

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

其中 f 和 g 是任意可微函數(shù)?；舅枷胧鞘褂枚A泰勒展開(kāi)將 f 和 g 在先前的狀態(tài)估計(jì)上進(jìn)行線(xiàn)性化，然后應(yīng)用標(biāo)準(zhǔn)的卡爾曼濾波器方程。（方程中的噪聲方差（Q 和 R）不變，即，由于線(xiàn)性化而產(chǎn)生的額外誤差沒(méi)有被建模。）因此，我們用非平穩(wěn)線(xiàn)性動(dòng)態(tài)系統(tǒng)來(lái)近似平穩(wěn)非線(xiàn)性動(dòng)態(tài)系統(tǒng)。也就是說(shuō)，在時(shí)間 t，我們通過(guò)以下方式近似模型：

我們可以看到，UKF是對(duì)標(biāo)準(zhǔn)KF的簡(jiǎn)單修改，但可以比EKF更準(zhǔn)確地處理非線(xiàn)性，而無(wú)需計(jì)算導(dǎo)數(shù)。

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

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

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

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

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

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

5.4.1 重采樣步驟

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

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

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

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

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

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

5.4.4 DBN的粒子濾波

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

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

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

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

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

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

對(duì)象也可能從狀態(tài)空間中被移除，如果它最近沒(méi)有更新（例如，它離開(kāi)了場(chǎng)景）。因此，一般來(lái)說(shuō)，我們必須允許狀態(tài)空間動(dòng)態(tài)地增長(zhǎng)和收縮。

在這種可變大小狀態(tài)空間模型中進(jìn)行推斷的更嚴(yán)格方法是使用粒子濾波。這很容易，因?yàn)槊總€(gè)粒子可以有不同的維度。我們?cè)谙旅嬖敿?xì)舉例說(shuō)明，在線(xiàn)模型選擇的背景下。

6 近似平滑

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

6.1 雙濾波平滑

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

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

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

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

6.2 期望傳播（EP）

期望傳播將假設(shè)密度濾波（第5.2.4節(jié)）推廣到批處理的上下文中。它對(duì)貝葉斯更新的順序不太敏感，因?yàn)樗梢栽谄渌?xiàng)的上下文中來(lái)回優(yōu)化整體似然度的每個(gè)項(xiàng)。我們?cè)谙旅娓敿?xì)解釋這一點(diǎn)。

回想一下，在A(yíng)DF中，精確的后驗(yàn)概率由以下公式給出：

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

6.3 變分式方法

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

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

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

6.4 吉布斯采樣

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

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

7 練習(xí)

7.1 隱馬爾可夫模型

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

7.2 二維HMMs

考慮為掃描文本等二維數(shù)據(jù)定義似然函數(shù)。自然地，可以使用一個(gè)HMM對(duì)圖像的每一行建模，并使用另一個(gè)HMM對(duì)行與行之間的連接進(jìn)行建模。這被稱(chēng)為偽二維或嵌入式HMM?；舅枷肴鐖D52所示，其中我們有2行，每行長(zhǎng)度為3。

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

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

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

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

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

7.3 分層HMMs

本練習(xí)要求你為HHMM的DBN表示定義CPDs。我們分別考慮層次結(jié)構(gòu)的底層、中層和頂層（因?yàn)樗鼈兙哂胁煌木植客負(fù)浣Y(jié)構(gòu)），以及第一個(gè)、中間和最后一個(gè)時(shí)間切片。

7.4 故障診斷

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

7.5 廣義 α ? β 算法

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

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

7.6 對(duì)數(shù)空間平滑

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

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

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

3. 基于上述結(jié)果，可以通過(guò)首先沿序列正向運(yùn)行，然后從末尾反向運(yùn)行，并僅在中間點(diǎn)和端點(diǎn)處存儲(chǔ)所需的消息來(lái)構(gòu)建一個(gè)分治算法。然后，在左右兩半上遞歸調(diào)用該算法。請(qǐng)?jiān)敿?xì)寫(xiě)出該算法。

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

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

7.7 常數(shù)空間平滑

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

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

3. 解釋為什么一般來(lái)說(shuō)前向（和后向）算子不可逆。給出一個(gè)反例。

7.8 BK 算法

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

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