論文閱讀(二)：理解概率圖模型的兩個要點：關于推理和學習的知識

1.論文鏈接：Essentials to Understand Probabilistic Graphical Models: A Tutorial about Inference and Learning

摘要：

????????本章的目的是為沒有概率圖形模型背景或沒有深入背景的科學家提供一個高級教程。對于更熟悉這些模型的讀者，本章將作為定義和一般方法的概要，供隨意瀏覽。這一章是有意自成一體的，首先提醒人們注意一些基本的定義，如邊緣獨立和有條件獨立的區別。然后，本章布里介紹了最流行的幾類概率圖模型：馬爾可夫鏈、貝葉斯網絡和馬爾可夫隨機域。接下來，在貝葉斯網絡上下文中解釋和說明概率推斷。最后給出了參數學習和結構學習的方法。

關鍵詞：概率圖模型，貝葉斯網絡，馬爾可夫隨機場，參數學習，結構學習，概率推理

背景：

????????本章的目的是為沒有概率圖形模型背景或沒有深入背景的科學家提供一個高級教程。對于更熟悉這些模型的讀者，本章將被用作定義和一般方法的綱要，可以隨意瀏覽。

????????本章首先從提醒基本定義開始。特別是邊緣獨立性和條件獨立性，利用概率圖模型的關鍵概念之一之間的區別會詳細解釋。因子圖和鏈圖分別被描述為馬爾可夫和貝葉斯網絡的統一模型和擴展模型。

????????第2.4節專門討論貝葉斯網絡中的概率推理。作為介紹，三個主要的規范推理查詢提到：證據的概率，最可能的解釋，最大后驗假設。然后，本節概述了用于推理的各種方法的基本原理和技術。精確的推理說明變量消除，消息傳遞算法，包括和產品算法（或信念傳播），條件，和消息傳播連接樹。特別是，后一個主題引起了圍繞圖道德化，圖三角剖分和連接樹建設的發展。近似推理是通過循環和廣義的信念傳播，隨機抽樣和變分方法。三個標準的抽樣方法適用于近似推理概述吉布斯抽樣，大都會黑斯廷斯算法，和重要性抽樣。重點放在重要性抽樣和變分方法的機制。

????????2.5節討論了貝葉斯網絡類的參數和結構學習。首先，通過三種標準方法回顧了從完全數據中進行參數學習的過程：一種統計方法（似然最大化）和兩種貝葉斯方法（最大后驗估計和期望后驗估計）。在不完全數據的情況下，描述了一個涉及標準期望最大化（EM）的通用框架。處理結構學習的方法可分為兩類。基于約束的方法依賴于依賴性分析。在這一類別中，簡短概述了IC和PC算法，并綜述了相關概念（獨立映射、依賴映射）。在第二類中，啟發式策略的基石是使用可分解的和馬爾可夫等價的分數。描述了這樣的分數，其或者求助于信息論域或者貝葉斯范式。除了啟發式搜索有向圖的空間，這一節還提到了導航可替換搜索空間的方法；這樣的空間是變量排序的空間（與標準K2算法相關）和由貪婪等價搜索方法導航的完全部分有向無環圖的空間。為了將基于分數的算法的范圍擴展到不完全數據，結構期望最大化提供了一個通用框架，其被解釋為通過在每次移動時在參數上嵌入EM的結構空間爬山。最后對隱變量的特殊情況進行了分析。

????????第2.6節介紹了馬爾可夫隨機數類的參數和結構學習。在完整數據和一般無向圖的情況下，這兩個任務仍然比貝葉斯網絡更具挑戰性。迭代方法，如梯度下降和二階方法是解決最大化可能性的解決方案。然而，導數的評估需要在馬爾可夫網絡中進行推理，這也是一個困難的任務，除了三角圖。另一方面，通過使用偽似然，有效地規避了似然棘手性。相比之下，三角化圖是易于處理的，因為它們表現出聯合概率的特殊因子分解。在一般圖的情況下，結構學習可以通過使用懲罰偽似然來處理。除了基于分數的算法之外，對優度度量和復雜度度量的凸逼近確保了全局最優值的獲得。在這種情況下，說明了一個L1正則化技術。最后，三角圖的情況下，表示一類屬性來自圖論狀態如何建立現任圖的鄰居圖，在本地搜索過程中。

????????在2.7節中，重點是因果網絡，它們與貝葉斯網絡的區別，以及用于學習其結構的策略。特別是，主動學習的兩種模式-批量干預和順序干預。最后，一個參考文獻列表引導讀者閱讀幾本關于概率圖模型的著名書籍，以及更具體地關注推理或學習的書籍章節。

2.1 介紹

????????概率圖模型（PGMs）為不確定性和獨立性的表示和推理提供了一個定性框架。PGM的定性部分是變量之間的依賴關系的圖形表示，例如，由有向無環圖（DAG）、無向圖（UG）或鏈圖表示，即，可以具有有向和無向邊但沒有任何有向環的圖。關于變量之間的定性依賴關系的不確定性知識是借助于稱為參數的概率分布形式化的。參數代表模型的定量部分。在這一介紹性章節中，我們首先簡要介紹了最流行的幾種PGM，包括馬爾可夫隨機場（MRF）及其一些變體，貝葉斯網絡（BN），一個由因子圖類組成的統一模型，以及代表MRF和BN擴展的鏈圖類。然后，我們展示了用于實現概率推理的各種機制，主要是在貝葉斯網絡中。隨后，我們概述了學習PGMs的突出策略。在大多數應用中，特別是在高維數據的情況下，很少有專家可以指定圖形模型的圖形結構。因此，不僅需要學習模型的參數，還需要學習圖形結構和參數，這在對數據的忠實性和易處理性方面代表了一個艱巨的挑戰。在模型學習的教程中，我們還提到了概率圖模型依賴于潛變量或隱變量的情況。最后，我們用一個簡短的部分來討論BN和因果網絡之間的區別。我們概述了用于學習因果結構的原則。

????????關于圖形模型的文獻是大量的。增加這一貢獻的動力來自于公認的對介于經典調查和廣泛匯編之間的文獻的需要。前者的省略風格賦予讀者更深的知識。詳細的匯編并不是一個綜合的觀點。因此，我們提供本教程。

????????這篇文章中提到的參考文獻必然代表了一種任意的選擇，很大程度上受到作者個人觀點和興趣的影響。在下文中，除非另有明確說明，否則我們將把框架約束為離散隨機變量。大寫字母表示隨機變量。將使用非大寫字母表示觀察結果。此外，為了簡化符號，我們有時會把 $X=T$ （對于true或1）和 $X=F$ （對于false or 0）分別表示為 $X$ 和 $\overline{X}$ 。此外，為了簡潔起見，我們有時會縮寫 $\mathbb{P}(A=a,B=b,C=c)$ 為 $\mathbb{P}(a,b,c)$ 。

2.2 基本概念

在本節中，我們回顧了聯合分布、邊際分布和條件分布等基本概念，以及貝葉斯框架的基石元素。

定義2.1（聯合分布、鏈式法則（或乘積法則））：

????????兩個二元隨機變量 $A$ 和 $B$ 的聯合（二元）分布定義了事件的概率 $\{A,\overline{A}\}\times \{B,\overline{B}\}$ 。這個概念推廣到任意數量的隨機變量 $X_{1},...,X_{n},$ 定義一個多變量分布。

鏈式法則提供了聯合分布：

$\forall x_{1},x_{2},...,x_{n}\in D_{X_{1}},D_{X_{2}},...,D_{X_{n-1}},D_{X_{n}}$ ，這里 $D_{X_{i}}$ 代表 $X_{i}$ 取值的域

為了簡便，我們僅僅這樣寫：

定義2.2（邊際分布）

給定 $X=\{X_{1},...,X_{n}\}$ ，有 $I\subset \{1,...,n\}$ ，以及通過將 $I$ 映射到 $X$ 得到的隨機變量集合 $X_{I}$ ， $X_{I}$ 的聯合分布就是 $X_{I}$ 的邊緣分布，通過在 $X\setminus X_{I}$ 中其他變量的域上對概率進行求和（“邊緣化”）得到。被忽略的變量被稱為被邊緣化。

邊緣化過程的表達式為：

因此，條件概率分布可以通過將聯合分布除以一個（或多個）變量的邊際分布來計算。

定義2.3（雙變量情況下的條件分布）

性質2.1（邊際分布和條件分布之間的關系）

圖2.1和表2.1所示的例子說明了這些概念及其在三變量情況下的關系。

例如，邊緣化 $S$ 和 $G$ 得到：

這也可以利用 $D$ 在 $SG$ ， $S\overline{G}$ ， $\overline{S}G$ ， $\overline{S}\overline{G}$ 條件下的四個條件分布來計算，分別用先驗（即非條件）概率加權：

現在我們回想一下貝葉斯定理，它以最簡單的形式將兩個條件概率聯系起來。

定義2.4（貝葉斯定理）

給定兩個隨機變量 $A$ 和 $B$ ，假設 $\mathbb{P}(B)\neq 0$

條件獨立的概念對于概率圖模型是基礎性的。讓我們首先回顧一下獨立性的概念，也稱為統計獨立性或邊緣獨立性。

定義2.5（獨立性（或邊際獨立性））

給定兩個隨機變量 $A$ 和 $B$ ?， $A$ 和 $B$ 之間的獨立性（記作 $A \perp\!\!\!\perp B$ ）定義為： $\mathbb{P}(A, B) = \mathbb{P}(A)\mathbb{P}(B)$ 。不相等意味著兩個變量是依賴的（ $A \not\perp\!\!\!\perp B$ ）。上述定義與獨立性的直觀概念之間的聯系也可以通過條件概率的使用來表達。獨立性的概念可以通過以下三個等價條件中的任何一個來重新表述，前提是 $\mathbb{P}( B)$ 不等于 0 和 1（這兩個值都對應于平凡情況）：

這意味著，如果知道事件 $B$ 發生或不發生，或者對 $B$ 的發生沒有了解，都不會影響事件 $A$ 發生的概率，那么 $A$ ?和 $B$ ?是獨立的。當 $A$ ?和 $B$ ?互換時，這種解釋仍然成立。

結合表 2.2，并使用網格單元格，圖 2.2說明了獨立性意味著“? $A$ 在 $B$ 中的比例”與“ $A$ 在所有可能性中的比例”保持一致。從而突出了 $B$ 對 $A$ 沒有影響。解釋獨立性的另一種方式是注意到 $A$ 的概率分布對于 $B$ 的所有值都是相同的， $B$ 的概率分布對于 $A$ 的所有值也都是相同的：對其中一個變量的任何值進行條件化不會改變另一個變量的概率分布。表 2.3 強調了這一點。

定義2.6（條件獨立性）

給定三個變量 $A$ ， $B$ ， $C$ 。 $A$ 和 $B$ 在給定 $C$ 的狀態下的條件獨立性 $(A \perp\!\!\!\perp B \mid C)$ 定義為： $\mathbb{P}(A, B \mid C) = \mathbb{P}(A \mid C)\mathbb{P}(B\mid C)$ 。當 $\mathbb{P}(C) > 0$ 時，等價于 $\mathbb{P}(A \mid B, C) = \mathbb{P}(A \mid C)$ 。

需要注意的是，例如，上述定義中的第二個命題確實意味著以下內容：對于所有 $a,b,b^{\prime}$ 和 $c$ ,當

$\mathbb{P}(C=c)>0,\mathbb{P}(A=a\mid B=b, C=c)=\mathbb{P}(A=a\mid B=b^{\prime}, C=c)=\mathbb{P}(A=a\mid C=c)$

（或者通過交換 A 和 B 對稱地得到）；也就是說，A 和 B 在給定 C 的條件下是條件獨立的，當且僅當，給定 C 的任何值，A 的概率分布對于 B 的所有值都保持不變（這等價于說，給定 C 的任何值，B 的概率分布對于 A 的所有值都保持不變）。對于邊際獨立性，只需檢查 $\mathbb{P}(A=T, B=T)=\mathbb{P}(A=T)\mathbb{P}(B=T)$ 。由于這個問題高度受限，這個等式意味著其他三個等式也得到滿足。不那么正式地說，A 和 B 在給定 C 的條件下是條件獨立的，當且僅當，給定是否發生 C 的知識，知道 B 是否發生不會提供關于 A 發生概率的信息（這也意味著，對稱地，知道 A 是否發生不會提供關于 B 發生概率的信息）。不滿足所需約束條件意味著兩個變量在給定 C 的條件下是條件相關的，記作 $(A\not \perp\!\!\!\perp B \mid C)$ 。

圖 2.3 提供了一個圖形說明。它通過建立由 $\mathbb{P}(C=c)>0$ 對于 $c\in\{T, F\}, \mathbb{P}(B=b)>0$ 對于 $b\in\{T, F\}$ 以及對于所有 $b, c\in\{T, F\}$ , $\mathbb{P}(A=T\mid B=b, C=c)=\mathbb{P}(A=T\mid C=c)$ 所隱含的約束系統來構建，然后設置網格的表面（n=40）并固定最小數量的參數以解決約束系統。表 2.4 檢查對稱約束系統是否得到驗證。

定義2.7（給定一組變量的條件獨立性）

給定變量的一個子集 $S\subseteq X\backslash\left\{X_{i}, X_{j}\right\}$ ， $X_{i}$ 和 $X_{j}$ 在知道 $S$ 的狀態下的條件獨立性（記作 $S\left(X_{i}\perp\perp X_{j}\mid S\right)$ 定義為： $\mathbb{P}\left(X_{i}, X_{j}\mid S\right)=\mathbb{P}\left(X_{i}\mid S\right) \mathbb{P}\left(X_{j}\mid S\right)$ 。不等式意味著在知道 $S$ （的狀態）的情況下，兩個變量是條件相關的，這記作 $S\left(X_{i}\not\perp\!\!\!\perp X_{j}\mid S\right)$ 。

2.3各類概率圖模型

在本節中，我們布里簡單回顧了概率圖模型的一些流行實例，即無向馬爾可夫網絡模型或馬爾可夫隨機數，貝葉斯網絡類，以及統一的模型類，因子圖和由鏈圖組成的擴展模型。我們記得，我們限制到離散變量的情況。

2.3.1馬爾可夫鏈和隱馬爾可夫模型

2.3.2馬爾科夫隨機場

馬爾可夫隨機場（MRF）是一種概率圖模型，其結構是一個無向圖（UG）。必須注意的是，與貝葉斯網絡相反，馬爾可夫隨機場允許循環依賴。另一方面，馬爾可夫隨機場不能代表貝葉斯網絡可以編碼的某些依賴，例如誘導依賴。

2.3.3馬爾可夫隨機場概念的變體

隱馬爾可夫隨機場

條件隨機場

2.3.4貝葉斯網絡

最流行的概率圖模型之一是貝葉斯網絡（BN）。BN在廣泛的自動推理應用中發揮著核心作用，包括診斷，傳感器驗證，概率風險分析，信息融合和糾錯碼解碼。BN的圖形組件是有向無環圖（DAG）。該DAG確定了聯合概率分布的條件分解，從而大大簡化了聯合分布的計算。該屬性減少了描述聯合概率分布所需的參數數量。

表2.5概括了當以集合S為條件時，頂點C關閉或打開頂點A和B之間的路徑的情況。

2.3.5統一模型和模型擴展

馬爾可夫隨機數和貝葉斯網絡可以用因子圖的統一類來表示。另一方面，鏈圖類代表了馬爾可夫隨機數和貝葉斯網絡的擴展。

因子圖

基本上，因子圖編碼了一個可以分解為因子的全局函數[27，51]。例如，圖2.6A所示的因子圖表示函數的因子分解

鏈圖

鏈圖表示一類圖形模型，包括馬爾可夫網絡和貝葉斯網絡作為特殊情況。當變量之間既存在響應解釋關系又存在對稱關系時，鏈圖是最合適的，而貝葉斯網絡更特別地關注前一類關聯，而馬爾可夫隨機場則專門解決后者。作為一個混合圖，鏈圖允許有向邊和無向邊;它的特征在于不存在半有向（或部分有向）圈（見圖2.7）。

2.4概率推理

在本節中，我們概述了用于概率推理的各種機制，為了簡潔起見，主要關注貝葉斯網絡。然而，其中一些方法適用于貝葉斯網絡和馬爾可夫隨機場的推理。推理是查詢圖形模型的任務。有三個標準的推理查詢需要解決。

更復雜的查詢可以從以前的查詢中構建。貝葉斯網絡的推理算法主要分為兩種：精確和近似。精確推理查詢通過邊緣化不相關的變量來求值。一般來說，所需的全部求和是不容易處理的。PE的決策版本是PP-完全的，其中PP代表“概率多項式時間”：問題可以通過運行一個隨機的多項式時間算法足夠（但有界）的次數來解決到任何指定的準確度。MPE的決策版本是NP-完全的，這意味著它不能以任何已知的方式在多項式時間內求解。MAP的決策版本仍然更加困難。然而，可以開發出易處理的精確算法。

2.4.1精確推理

在這一節中，我們給出了可用于精確推理的各種方法。除非特別艾德，否則下面的方法可以解決貝葉斯網絡中的推理問題。然而，貝葉斯網絡和馬爾可夫隨機分布都可以用因子圖表示。因此，兩類圖形模型可以共享用于推斷的公共解決方案。

所有精確方法通過系統地利用貝葉斯網絡圖中編碼的條件獨立性來計算邊緣概率。提出了兩類精確方法。第一類方法通過沿著無環圖的箭頭傳播消息來實現感興趣概率的計算。這一類包括變量消除和樹的消息傳遞，后來擴展到多樹。多樹是一種不允許無向環的有向無環圖（DAG）。通過添加循環切割集條件，消息傳遞的原理被推廣到圖中。第二類方法通過道德化和三角剖分從原始圖構建一個新結構—一個連接樹；然后在這個圖的新表示上應用一個適應的消息傳播方案。

變量消除

在變量消去法中，由于聯合概率分布的因式分解形式，邊緣化過程中的一些步驟被簡化：因式分解決定了連續邊緣化（即消除）的變量的順序[99，25，56]。這種邊緣化相當于一系列當地產品和當地邊緣化。消除變量的具體方法取決于手頭的查詢。特別是，如果目標是解決證據的概率，那么通過求和來消除變量。在MPE查詢中，通過最大化變量來消除變量。為了求解MAP，需要執行兩種類型的消除。我們用一個玩具例子來說明消除過程：

消息傳遞算法

條件

連接樹中的消息傳播

第二類方法依賴于連接樹中的消息傳播[56，41，72]。在這樣的樹中，節點是原始圖中頂點的簇;因此這些方法被稱為聚類方法。其中，消息傳播依賴于勢的概念以及將聯合概率分布分解為集團和分隔符的勢。第一步為原始圖構建一個連接樹，應用道德化，然后三角剖分。我們在下面定義這些概念。

2.4.2近似推理

最常見的近似推理算法有循環置信傳播法、廣義置信傳播法、隨機馬爾可夫鏈蒙特卡羅模擬法和變分法等。

循環和廣義置信傳播

必須注意的是，和積算法也可以應用于具有循環的因子圖，因為所有更新都是局部的。更一般地說，循環置信傳播是指在包含循環（即無向循環）的BN上使用消息傳遞方案，例如眾所周知的Pearl polytree算法[69]。由于這些循環，將導致沒有自然終止的迭代算法，消息在給定的邊緣上傳遞多次。雖然循環置信傳播算法的結果不能被解釋為精確的邊際函數，但這種近似方案在諸如糾錯碼的主要應用中表現出驚人的性能[60]。直覺是，如果循環很長，那么循環的效果會隨著消息的傳播而逐漸消失：隨著時間的推移，所有的消息都會趨于某種穩定的平衡。循環置信傳播確保收斂的條件仍然沒有得到很好的理解;例如，已知包含單個循環的圖保證收斂，但獲得的概率可能是不正確的[64，88]。

[92]中提出了廣義置信傳播，以科普一般圖中的消息傳遞。簡而言之，它表明，信念傳播只能收斂到自由能函數的近似值的一個穩定點，在統計物理學中稱為貝特自由能：即，邊緣后驗概率是信念傳播算法的x點，當且僅當它們是貝特自由能梯度為零的點。廣義置信傳播版本是基于更精確的自由能近似（稱為菊池近似）開發的[45]。這些新算法可以比原來的算法更準確，在用戶可調的復雜性增加。

隨機采樣

一個突出的近似推理方法依賴于隨機抽樣方法，以及許多變體。其中，馬爾可夫鏈蒙特卡羅（MCMC）方法被設計為通過構建具有期望分布作為其平衡分布的馬爾可夫鏈來從感興趣的概率分布進行采樣。然后，在鏈運行大量步驟（老化階段）之后，從鏈中進行采樣，以近似變量之一或變量的某個子集的目標邊際分布。吉布斯采樣和Metropolis-Hastings算法是這類算法中最流行的[31]。重要性抽樣代表了另一類方法。

Gibbs抽樣

Metropolis-Hastings算法

重要抽樣

變分方法

總之，聯合概率分布的形式通過適當選擇變分變換來簡化艾德，從而簡化了推理問題。此外，一些或所有變量（即，頂點）可以被變換，這導致兩類變分方法，順序方法和塊方法。在序貫方法中，變量一次轉換一個，順序在推理過程中確定。這一順序取決于證據的具體形式。然而，在某些情況下，提前確定要變換的變量可能是有利的：因此，當圖中已知某些特殊的子結構時，塊方法適用。

塊的方法，它只轉換一些變量，這意味著精確的方法被用作變分近似框架內的子程序。在該方案中，圖的部分變換可以保持一些原始圖形結構不變;或者可以引入新的圖形結構，其支持精確推理方法的應用;或者可以考慮這兩種方式。在有限的范圍內使用變分近似，將圖變換成可應用精確方法的簡化艾德圖是貝內的。這通常提供比不考慮易處理的子結構而變換整個圖的算法更接近的邊界。

圖形模型中變分推理的變體有很多。廣泛的文獻參考，特別是開創性的作品，允許對這個問題進行更深入的研究（見[43，57，84，85]僅舉幾例）。有關完整的細節，工作的例子，以及其他推理策略的其他見解，讀者可以參考[67]的匯編。

2.5貝葉斯網絡學習

2.5.1參數學習

完整數據

不完整數據

2.5.2結構學習

本節專門討論貝葉斯網絡中的結構學習，組織如下。首先，我們提出了基于約束的方法，該方法基于數據中條件獨立性的識別來學習結構。然后，我們處理基于分數的方法，瀏覽空間的結構，同時優化分數。下一小節布里伊提到了混合方法。第四，我們提到如何基于分數的方法可以適應處理不完整的數據。最后，一個小節討論了使用潛變量學習貝葉斯網絡的更具體的情況。

基于約束的算法

基于約束的算法執行統計測試來學習條件獨立性。為了呈現這兩個主要策略，我們需要以下定義：

基于分數的算法

理解使用等價分數導航DAG搜索空間的必要性是至關重要的。給定數據，唯一可以訪問的知識是數據編碼的條件依賴和獨立集合。然而，一個給定的數據集，它提供了一個獨特的條件依賴性和獨立性，可以與幾個DAG，都屬于同一個馬爾可夫等價類。在學習BN的結構時，沒有理由對這些等效DAG候選者中的任何一個有利。因此，當通過評分函數評估時，這些候選DAG返回相同的值是至關重要的。特別是，這一基本原理解釋了將貝葉斯狄利克雷（BD）分數（不是等效分數）重新轉換為BDe分數（等效分數）的努力。明智地調整先驗（盡管保持足夠的通用性）是這種適應的關鍵。

與評分函數和鄰域的定義一起，實現結構學習所需的第三個要素是搜索策略。為了防止標準局部搜索（或爬山）[36]的常見缺點，即陷入局部最優，迭代爬山從多個解開始搜索（隨機重新開始）。或者，使用其他啟發式搜索方法，例如模擬退火[36]，禁忌搜索[8]，遺傳算法[54，90]，可變鄰域搜索[24]，蟻群優化[22]，貪婪隨機自適應搜索程序（GRASP）[23]和分布估計算法[7]。

大多數學習算法使用DAG搜索空間。可能的替代方案包括瀏覽變量的排序空間，完成的PDAG空間（見定義2.26）或所謂的RPDAG空間（受限的PDAG）。在[24]和[53]中，主搜索過程探索變量的排序空間。然后，對于每個候選排序，評分函數評估通過在與該拓撲排序兼容的DAG的子空間中執行的二次搜索（通常為K2算法）獲得的最佳貝葉斯網絡。另一方面，提出了在馬爾可夫等價空間中的貪婪搜索，以節省生成具有相等得分的結構所浪費的時間。[61]和[12]中的開創性工作為貪婪等價搜索（GES）奠定了基礎，它只依賴于兩個操作（在特定有效性條件下插入或刪除弧），并由兩個階段組成。簡而言之，第一個貪婪階段迭代地增加完整的PDAG結構，直到達到局部最大值;對稱地，第二個階段簡化完整的PDAG結構，直到達到局部最大值（參見例如[13]）。同樣，使用等效分數是必要的。

類似于完整的PDAG，RPDAG也允許在DAG的馬爾可夫等價類中導航;然而，為了效率，兩個不同的RPDAG可以表示相同的等價類（參見例如[1]）。

混合方法

為了實現結構學習，有幾種方法結合了聯合收割機測試條件獨立性和使用分數。例如，在[77]和[81]中，通過條件獨立性測試產生拓撲排序;然后運行K2算法。在[91]中，運行在依賴性分析下游的算法是遺傳算法。與之前的方案相比，其他方法進行啟發式搜索，依賴于傳統的基于約束的技術。在[21]中，該算法使用基于依賴分析的啟發式搜索已完成的PDAG的空間;然后將每個PDAG轉換為DAG，并用貝葉斯得分對其進行評分。

基于分數的算法在不完全數據中的應用

結構EM可以被解釋為通過結構空間爬山，在DAG空間中的每次移動時將EM嵌入參數。[28]和[29]的開創性工作分別依賴于信息理論得分（BIC，MDL）和貝葉斯框架（貝葉斯得分）。另外，進化算法也被提出[65]。

EM算法提供了一個自然的框架來估計潛在變量。在這條線上，變分EM方法近似后驗分布到更簡單的，從而允許使用的邊緣似然的下限。該方案通過保持潛變量和參數的后驗分布來推廣EM算法[4]。

潛變量

處理潛變量的問題是雙重的：一個必須發現這些變量，一個必須調整它們的基數（在離散變量的情況下）。我們在上面提到，EM算法提供了一個自然的框架來估計潛在變量。這說明，結構EM為基礎的計劃是解決結構學習在這些條件下的一般答案。

此外，在潛在變量的情況下，對效率的追求可能迫使我們在貝葉斯網絡的一個子類中處理學習任務。在這方面，潛在樹模型（LTM）--以前被稱為層次潛在類模型--受到了廣泛的研究，這些研究始于[100]中的開創性工作。LTM的結構被限制到僅允許將潛在變量連接到其子節點的鏈路的層。此外，最常見的情況是，底層由所有觀察到的變量組成，而且只由它們組成。在這種情況下，LTM的結構可以被解釋為基于潛在類模型（LCM）的基本結構的分形拓撲（參見圖2.9）。用于學習語言記憶的方法有兩種類型：傳統的基于搜索的方法和基于變量聚類的方法。在第一類中，提出了各種爬山方法來搜索規則LTM的空間。

為了搜索常規LTM的空間，可能的開始可以是LCM。探索給定LTM的鄰域所涉及的操作包括添加或移除潛在頂點以及鄰域重定位。互補操作旨在通過添加或刪除給定潛在頂點的狀態來優化潛在變量的基數。這些操作可以順序或同時執行[11，97，98]，允許在給定當前結構的情況下進行細粒度的探索。

有效的替代方案利用層次結構來開發基于變量聚類的上升構造策略。給定聚類中的所有變量本質上表示要創建的潛在變量的子變量。最簡單的方法是處理二叉樹的方法[33，39]，也可能限制潛變量具有二元基數[39]。必須注意的是，在[39]中，基于二叉樹的LTM可以用兄弟節點之間的連接來擴充。然而，二叉樹并不總是容易解釋的。它們也沒有優化潛在變量的數量。為了放松這種結構約束，使用了幾種策略：例如，從二叉樹開始，相鄰隱變量之間的成對獨立性測試允許我們檢測冗余，并因此消除兩個鄰居中的一個，并將其子女重新移植為另一個頂點變量的子女[87];其他學習算法構建層次結構的當前層，從前一層的觀測變量或估算潛變量構建LCM：在[86]中，在遞增構造的每一步，用兩個子變量初始化的LCM通過貪婪添加其他變量來豐富，直到滿足某個有效性標準;在[59]和[62]中，在每一步，為前一層的變量獲得一個劃分為集團的劃分。每一個這樣的集團組成對的依賴變量，代表盡可能多的候選人包含一個共同的潛在變量。在[63]中提供了對潛在樹模型的全面調查。

2.6學習馬爾可夫隨機場

除了在三角馬爾可夫隨機ELDs的情況下，歸一化常數的存在使得馬爾可夫隨機ELDs的學習任務變得棘手。關于參數學習，我們主要考慮完整數據的情況。我們首先為理解基于梯度的方法和二階方法如何解決這個問題奠定基礎，將其轉換為無約束優化問題。或者，可以通過使用似然的近似（所謂的偽似然）來實現易處理的解決方案。最后，為了說明馬爾可夫隨機場中的結構學習，我們選擇了一種基于分數的方法，該方法依賴于最小絕對收縮和選擇算子（LASSO）技術。

2.6.1參數學習

完整數據

一般圖

除了梯度和二階方法，另一種選擇是選擇一個目標函數近似的聯合概率，這是易于處理的，相反的可能性。所謂的偽似然度量為棘手性提供了一個簡單的解決方案[6]。

三角化圖

不完整數據

在不完全數據的情況下，似然性失去了凹度性質。至于貝葉斯網絡，期望最大化仍然是萬靈藥，并將提供一個局部最大值。讀者可以參考[10]，例如，一個稱為Gibbsian EM的過程將EM算法推廣到馬爾可夫隨機域的環境中。

2.6.2結構學習

馬爾可夫隨機域（MRF）的結構學習問題已經引起了很多研究者的關注。對于貝葉斯網絡，解決這一問題的方法是基于約束或基于評分。基于約束的方法使用相關性測試從數據中估計條件獨立性，然后確定表示這些獨立性的圖[78]。為了給一個候選圖打分，基于分數的方法聯合收割機一個度量t的優度的度量和一個度量圖的復雜度的度量。在標準的基于分數的方法中涉及的爬山過程由于可能的圖的數量而使得問題是NP-難的，這在變量的數量上是超指數的。此外，MRF的結構學習必然包括參數估計，這對于一般的無向模型來說是一個非常復雜的任務。再次，偽似然性代表了開發基于有效分數的方法的基石，這些方法旨在瀏覽可能結構的空間。為了避免溢出，一個簡單的方法是考慮將分數規則化，例如下面的類似MDL的分數：

塊正則化在精神上與LASSO組相似[95]。Group LASSO通過對預測變量的某些特征的權重進行分組，在組級別上擴展了LASSO：然后，根據正則化參數，整個預測變量組可能會退出模型，從而導致組的稀疏選擇。組LASSO對MRF結構學習的適應是雙重的：（1）預測器的平方誤差之和被替換為對對數似然的近似;以及（2）邊緣的所有特征權重被分組。為了避免過度填充和密集連接的結構，使用塊L1正則化優化對數似然

2.7因果網絡

被動學習（即僅使用觀察數據）只關注兩個變量是否在統計上相關，這可以通過許多不同的潛在因果結構來解釋。一個顯著的例外是，因果網絡中的所有 v-結構都可以從觀察數據中發現。此外，已有多項工作致力于識別在僅考慮觀察數據的情況下，可以可靠評估某些因果假設的條件[79, 70]。在主動學習框架中，干預數據允許我們通過對觀察系統的擾動來推斷因果關系[80]。形式上，對單個變量的干預可以通過插入一個額外的變量作為該變量的額外父節點來建模。

這種對網絡的“手術”可能會打破貝葉斯網絡之間的馬爾可夫等價性。然而，除了在簡單情況下，干預不太可能對識別真實因果結構最有效（最大效果意味著這種干預將允許我們區分馬爾可夫等價類中的不同 DAG）。相反，通常通過隨機實驗，馬爾可夫等價類 DAG 被順序細化為一些更小的子類。然后可以在 PDAG的每個所謂的鏈組件中分別進行邊的方向化，代表馬爾可夫等價類。