概率圖模型

概率圖模型是之前一直擱置的內(nèi)容综苔，然而躲得過初一躲不過十五鹦肿，看葫蘆書時發(fā)現(xiàn)其中有整整一章關于概率圖逼泣，方才意識到概率圖模型的重要性，回過頭來重新補上這部分內(nèi)容告组。

概率圖模型（Probabilistic Graphical Model,PGM）煤伟，簡稱圖模型，是指一種用圖結(jié)構(gòu)來描述多元隨機變量之間條件獨立關系的概率模型木缝。給研究高維空間中的概率模型帶來了很大的便捷性便锨。

對于一個 $K$ 維隨機向量 $X = [X_1,X_2,\dots,X_K]^T$ ，其聯(lián)合概率為高維空間中的分布我碟，一般難以直接建模放案。假設每個變量為離散變量并有 $m$ 個取值，在不作任何獨立假設條件下矫俺，則需要 $m^K-1$ 個參數(shù)才能表示其概率分布（因為我們需要給出每一組可能的 $[x_1,x_2,\dots,x_K]^T$ 的概率吱殉，共 $m^K$ 種可能，由于概率和為1因此在此基礎上減1）恳守。不難看出考婴，參數(shù)數(shù)量是指數(shù)級的，這在實際應用中是不可接受的催烘。

一種有效減少參數(shù)量的方法是獨立性假設沥阱。將 $K$ 維隨機向量的聯(lián)合概率分解為 $K$ 個條件概率的乘積：

$\begin{aligned} p(\mathbf{x}) & \triangleq P(\mathbf{X}=\mathbf{x}) \\ &=p\left(x_{1}\right) p\left(x_{2} | x_{1}\right) \cdots p\left(x_{K} | x_{1}, \cdots, x_{K-1}\right) \\ &=\prod_{k=1}^{K} p\left(x_{k} | x_{1}, \cdots, x_{k-1}\right) \\ \end{aligned}$

其中 $x_k$ 表示變量 $X_k$ 的取值。如果某些變量之間存在條件獨立伊群，其參數(shù)量就可以大幅減少考杉。

假設有四個二值變量 $X_1,X_2,X_3,X_4$ 策精，在不知道這幾個變量依賴關系的情況下以用一個聯(lián)合概率表來記錄每一種取值的概率需要 $2^4?1=15$ 個參數(shù)。假設在已知 $X_1$ 時 $X_2$ 和 $X_3$ 獨立崇棠，即有：

$p(x_2|x_1,x_3)=\frac{p(x_2,x_3|x_1)}{p(x_3|x_1)}=\frac{p(x_2|x_1)p(x_3|x_1)}{p(x_3|x_1)}=p(x_2|x_1)$

同理：

$p(x_3|x_1,x_2)=p(x_3|x_1)$

在已知 $X_2$ 和 $X_3$ 時 $X_1$ 也和 $X_4$ 獨立咽袜，即有：

$p(x_4|x_1,x_2,x_3)=p(x_4|x_2,x_3)$

那么其聯(lián)合概率 $p(x)$ 可以分解為：

$\begin{aligned} p(x)&=p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)p(x_4|x_1,x_2,x_3)\\ &=p(x_1)p(x_2|x_1)p(x_3|x_1)p(x_4|x_2,x_3)\\ \end{aligned}$

是 $4$ 個局部條件概率的乘積。如果分別用 $4$ 個表格來記錄這 $4$ 個條件概率的話枕稀，只需要 $1 + 2 + 2 + 4 = 9$ 個獨立參數(shù)询刹。

當概率模型中的變量數(shù)量比較多時，其條件依賴關系也比較復雜萎坷。我們可以使用圖結(jié)構(gòu)的方式將概率模型可視化凹联，以一種直觀、簡單的方式描述隨機變量之間的條件獨立性的性質(zhì)哆档，并可以將一個復雜的聯(lián)合概率模型分解為一些簡單條件概率模型的組合蔽挠。下圖給出了上述例子中 $4$ 個變量之間的條件獨立性的圖形化描述。

圖模型有三個基本問題：

表示問題：對于一個概率模型瓜浸，如何通過圖結(jié)構(gòu)來描述變量之間的依賴關系澳淑。
推斷問題：在已知部分變量時算其它變量的后驗概率分布。
學習問題：圖模型的學習包括圖結(jié)構(gòu)的學習和參數(shù)的學習插佛。

很多機器學習模型都可以歸結(jié)為概率模型杠巡，即建模輸入和輸出之間的條件概率分布。因此朗涩，圖模型提供了一種新的角度來解釋機器學習模型忽孽，并且這種角度有很多優(yōu)點绑改，比如了解不同機器學習模型之間的聯(lián)系谢床，方便設計新模型等。

1厘线、模型表示

圖由一組節(jié)點和節(jié)點之間的邊組成识腿。在概率圖模型中，每個節(jié)點都表示一個隨機變或一組隨機變量造壮，邊表示這些隨機變量之間的概率依賴關系渡讼。

常見的概率圖模型可以分為兩類向圖模型和無向圖模型。有向圖模型的圖結(jié)構(gòu)為有向非循環(huán)圖耳璧，如果兩個節(jié)點之間有連邊成箫，表示對于的兩個變量為因果關系。無向圖模型使用無向圖來描述變量之間的關系旨枯。每條邊代表兩個變量之間有概率依賴關系蹬昌，但是并不一定是因果關系。

1.1攀隔、有向圖模型

有向圖模型皂贩，也稱貝葉斯網(wǎng)絡（Bayesian Network）或信念網(wǎng)絡（Belief Network）栖榨，是指用有向圖來表示概率分布的圖模型。

貝葉斯網(wǎng)絡：對于一個隨機向量 $X = [X_1,X_2,\dots,X_K]^T$ 和一個有 $K$ 個節(jié)點的有向非循環(huán)圖 $G$ 明刷， $G$ 中的每個節(jié)點都對應一個隨機變量婴栽，可以是可觀測的變量，隱變量或是未知參數(shù)辈末。 $G$ 中的每個連接 $e_{ij}$ 表示兩個隨機變量 $X_{i}$ 和 $X_{j}$ 之間具有非獨立的因果關系愚争。 $X_{\pi_k}$ 表示變量 $X_k$ 的所有父節(jié)點變量集合，每個隨機變量的局部條件概率分布（local conditional probability distribution）為 $P(X_k|X_{\pi_k})$ 挤聘。

若 $X$ 的聯(lián)合概率分布可以分解為每個隨機變量 $X_k$ 的局部條件概率的連乘形式准脂，即：

$p(x)=\prod_{i=1}^K p(x_k|x_{\pi_k})$

那么 $(G, X)$ 構(gòu)成了一個貝葉斯網(wǎng)絡。

條件獨立性：在貝葉斯網(wǎng)絡中檬洞，如果兩個節(jié)點是直接連接的狸膏，它們肯定是非條件獨立的直接因果關系。父節(jié)點是“因”添怔，子節(jié)點是“果”湾戳。

如果兩個節(jié)點不是直接連接的，但是它們之間有一條經(jīng)過其它節(jié)點的路徑來連接广料，那么這兩個節(jié)點之間的條件獨立性就比較復雜砾脑，例如：

(a)(b)(c)(d)分別代表間接因果關系、間接果因關系艾杏、共因關系韧衣、共果關系。

局部馬爾可夫性質(zhì)：對一個更一般的貝葉斯網(wǎng)絡购桑，其局部馬爾可夫性質(zhì)為：每個隨機變量在給定父節(jié)點的情況下畅铭，條件獨立于它的非后代節(jié)點。

$X_{k} \perp Z | X_{\pi_{k}}$

其中 $Z$ 為 $X_k$ 的非后代變量勃蜘。

1.2硕噩、常見的有向圖模型

1.2.1、Sigmoid信念網(wǎng)絡

一種簡單的參數(shù)化模型為Sigmoid信念網(wǎng)絡缭贡。Sigmoid信念網(wǎng)絡種變量取值為 $\{0,1 \}$ 炉擅，對于變量 $X_k$ 和它的父節(jié)點集合 $\pi_k$ ，條件概率分布表示為：

$P(X_k=1|\pi_k;\theta)=\sigma(\theta_0+\sum_{x_i\in X_{\pi_k}} \theta_i x_i)$

其中 $σ(·)$ 是Logistic sigmoid函數(shù)阳惹， $\theta_i$ 是可學習的參數(shù)谍失。假設變量 $X_k$ 的父節(jié)點數(shù)量為 $M$ ，如果使用表格來記錄條件概率需要 $2^M$ 個參數(shù)莹汤，如果使用參數(shù)化模型只需要 $M + 1$ 個參數(shù)快鱼。如果對不同的變量的條件概率都共享使用一個參數(shù)化模型，其參數(shù)數(shù)量又可以大幅減少。

值得一提的是Sigmoid信念網(wǎng)絡與Logistic回歸模型都采用Logistic函數(shù)來計算條件概率攒巍。如果假設Sigmoid信念網(wǎng)絡中只有一個葉子節(jié)點嗽仪，其所有的父節(jié)點之間沒有連接，且取值為實數(shù)柒莉，那么sigmoid信念網(wǎng)絡的網(wǎng)絡結(jié)構(gòu)和Logistic回歸模型類似闻坚，如圖所示。

這兩個模型區(qū)別在于Logistic回歸模型中的 $x$ 作為一種確定性的參數(shù)兢孝，而非變量窿凤。因此Logistic回歸模型只建模條件概率 $p(y|x)$ ，是一種判別模型跨蟹，而Sigmoid信念網(wǎng)絡建模 $p(x, y)$ 雳殊，是一種生成模型。

1.2.2窗轩、樸素貝葉斯分類器

樸素貝葉斯分類器是一類簡單的概率分類器夯秃，在強（樸素）獨立性假設的條件下運用貝葉斯公式來計算每個類別的后驗概率。

給定一個有 $d$ 維特征的樣本 $x$ 和類別 $y$ 痢艺，類別的后驗概率為：

$p(y | \mathbf{x} ; \theta)=\frac{p\left(x_{1}, \cdots, x_rbl378q | y\right) p(y)}{p\left(x_{1}, \cdots, x_cx72772\right)}∝ p\left(x_{1}, \cdots, x_27b7p72 | y;\theta\right) p(y;\theta)$

其中 $\theta$ 是概率分布的參數(shù)仓洼。

樸素貝葉斯分類器中，假設在給定 $Y$ 的情況下 $X_i$ 之間條件獨立堤舒，即 $X_i \perp X_j|Y$ 色建。下圖給出了樸素貝葉斯分類器的圖形表示。

條件概率分布 $p(y|x)$ 可以分解為：

$p(y|x;\theta)∝p(y|\theta_c)\prod_{i=1}^d p(x_i|y;\theta_{i,y})$

其中 $θ_c$ 是 $y$ 的先驗概率分布的參數(shù)舌缤， $\theta_{i,y}$ 是條件概率分布 $p(x_i|y;θ_{i,y})$ 的參數(shù)箕戳。若 $x_i$ 為連續(xù)值， $p(x_i|y;θ_{i,y})$ 可以用高斯分布建模国撵。若 $x_i$ 為離散值陵吸， $p(x_i|y;θ_{i,y})$ 可以用多項分布建模。

雖然樸素貝葉斯分類器的條件獨立性假設太強卸留，但是在實際應用中走越，樸素貝葉斯分類器在很多任務上也能得到很好的結(jié)果，并且模型簡單耻瑟，可以有效防止過擬合。

1.2.3赏酥、隱馬爾科夫模型

隱馬爾科夫模型是一種含有隱變量的馬爾可夫過程喳整。下圖給出隱馬爾可夫模型的圖模型表示。

隱馬爾可夫模型的聯(lián)合概率可以分解為：

$p(x,y;\theta)=\prod_{i=1}^T p(y_t|y_{t-1},\theta_s)p(x_t|y_t,\theta_t)$

其中 $p(x_t|y_t,\theta_t)$ 為輸出概率裸扶， $p(y_t|y_{t-1},\theta_s)$ 為轉(zhuǎn)移概率框都， $\theta_s,\theta_t$ 分別表示兩類條件概率的參數(shù)。

1.3呵晨、無向圖模型

無向圖模型魏保，也稱為馬爾可夫隨機場或馬爾科夫網(wǎng)絡熬尺，是一類用無向圖來描述一組具有局部馬爾可夫性質(zhì)的隨機向量 $X$ 的聯(lián)合概率分布的模型。

馬爾可夫隨機場：對于一個隨機向量 $X = [X_1,X_2,\dots,X_K]^T$ 和一個有 $K$ 個節(jié)點的無向圖 $G(V,\epsilon)$ （可有循環(huán)）谓罗， $G$ 中節(jié)點 $k$ 表示隨機變量 $X_k$ 粱哼， $1\leq k \leq K$ 。如果 $(G,X)$ 滿足局部馬爾可夫性質(zhì)檩咱，即一個變量 $X_k$ 在給定它的鄰居的情況下獨立于所有其它變量：

$p\left(x_{k} | \mathbf{x}_{\backslash k}\right)=p\left(x_{k} | \mathbf{x}_{N(k)}\right)$

其中 $N(k)$ 為變量 $X_k$ 的鄰居集合揭措， $\backslash k$ 為除 $X_k$ 外其它變量的集合，那么 $(G, X)$ 就構(gòu)成了一個馬爾可夫隨機場刻蚯。

無向圖的馬爾可夫性：無向圖中的馬爾可夫性可以表示為：

$X_{k} \perp \mathbf{X}_{\backslash N(k), \backslash k} | \mathbf{X}_{N(k)}$

其中 $\mathbf{X}_{\backslash N(k), \backslash k}$ 表示除 $X_{N(k)}$ 和 $X_k$ 外的其它變量绊含。

上圖中由馬爾可夫性質(zhì)可以得到： $X_1\perp X_4|X_2,X_3$ 和 $X_2\perp X_3|X_1,X_4$ 。

1.4炊汹、無向圖模型的概率分解

團：由于無向圖模型并不提供一個變量的拓撲順序躬充，因此無法用鏈式法則對 $p(x)$ 進行逐一分解。無向圖模型的聯(lián)合概率一般以全連通子圖為單位進行分解讨便。無向圖中的一個全連通子圖麻裳，稱為團（Clique），即團內(nèi)的所有節(jié)點之間都連邊器钟。在所有團中津坑，如果一個團不能被其它的團包含，這個團就是一個最大團（Maximal Clique）傲霸。

因子分解：無向圖中的的聯(lián)合概率可以分解為一系列定義在最大團上的非負函數(shù)的乘積形式疆瑰。

Hammersley -Clifford定理：如果一個分布 $p(x) > 0$ 滿足無向圖 $G$ 中的局部馬爾可夫性質(zhì)，當且僅當 $p(x)$ 可以表示為一系列定義在最大團上的非負函數(shù)的乘積昙啄，即：

$p(x)=\frac{1}{Z} \prod_{c\in C}\phi_c(x_c)$

上式也稱為吉布斯分布穆役。其中 $C$ 為 $G$ 中的最大團集合， $\phi_c(x_c)$ 是定義在團 $c$ 上的勢能函數(shù)梳凛， $Z$ 是配分函數(shù)（Partition Function）耿币，用來將乘積歸一化為概率形式。

$Z=\sum_{\mathbf{x} \in \mathcal{X}} \prod_{c \in \mathcal{C}} \phi_{c}\left(\mathbf{x}_{c}\right)$

其中 $\mathcal{X}$ 為隨機向量 $X$ 的取值空間韧拒。

無向圖模型與有向圖模型的一個重要區(qū)別是有配分函數(shù) $Z$ 淹接。配分函數(shù)的計算復雜度是指數(shù)級的，因此在推斷和參數(shù)學習時都需要重點考慮叛溢。

由于勢能函數(shù)必須為正的塑悼，因此我們一般定義為：

$\phi_c(\mathbf{x_c})=\exp(-E_c(\mathbf{x_c}))$

其中 $E_c(\mathbf{x_c})$ 為能量函數(shù)。這里的負號是遵從物理上的習慣楷掉，即能量越低意味著概率越高厢蒜。

因此無向圖上定義的概率分布可以表示為：

$\begin{aligned} P(\mathbf{x}) &=\frac{1}{Z} \prod_{c \in \mathcal{C}} \exp \left(-E_{c}\left(\mathbf{x}_{c}\right)\right) \\ &=\frac{1}{Z} \exp \left(\sum_{c \in \mathcal{C}}-E_{c}\left(\mathbf{x}_{c}\right)\right) \\ \end{aligned}$

這種形式的分布又稱為玻爾茲曼分布（Boltzmann Distribution）。任何一個無向圖模型都可以用上式來表示其聯(lián)合概率。

1.5斑鸦、常見的無向圖模型

1.5.1愕贡、對數(shù)線性模型

勢能函數(shù)一般定義為：

$\phi_{c}\left(\mathbf{x}_{c} | \theta_{c}\right)=\exp \left(\theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)\right)$

其中函數(shù) $f_{c}\left(\mathbf{x}_{c}\right)$ 為定義在 $\mathbf{x}_c$ 上的特征向量， $\theta_c$ 為權重向量巷屿。這樣聯(lián)合概率 $p(x)$ 的對數(shù)形式為：

$\log p(\mathbf{x} ; \theta)=\sum_{c \in C} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)-\log Z(\theta)$

其中 $θ$ 代表所有勢能函數(shù)中的參數(shù) $θ_c$ 固以。這種形式的無向圖模型也稱為對數(shù)線性模型或最大熵模型。

如果用對數(shù)線性模型來建模條件概率 $p(y|x)$ 攒庵，有：

$p(y | \mathbf{x} ; \theta)=\frac{1}{Z(\mathbf{x} ; \theta)} \exp \left(\theta^{\mathrm{T}} f(\mathbf{x}, y)\right)$

其中 $Z(\mathbf{x};\theta)=\sum_y \exp (\theta^{\mathrm{T}} f(\mathbf{x}, y))$ 嘴纺。這種對數(shù)線性模型也稱為條件最大熵模型或softmax回歸模型。

1.5.2浓冒、條件隨機場

條件隨機場是一種直接建模條件概率的無向圖模型栽渴。

和條件最大熵模型不同，條件隨機場建模的條件概率 $p(y|x)$ 中稳懒， $y$ 一般為隨機向量闲擦，因此需要對 $p(y|x)$ 進行因子分解。設條件隨機場的最大團集合為 $C$ 场梆，條件概率為：

$p(\mathbf{y} | \mathbf{x} ; \theta)=\frac{1}{Z(\mathbf{x} ; \theta)} \exp \left(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}, \mathbf{y}_{c}\right)\right)$

其中 $Z(\mathbf{x};\theta)=\sum_y \exp(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}, \mathbf{y}_{c}\right))$ 為歸一化項墅冷。

一個最常用的條件隨機場為圖(b)中所示的鏈式結(jié)構(gòu)，其條件概率為：

$p(\mathbf{y} | \mathbf{x} ; \theta)=\frac{ 1}{Z(\mathbf{x} ; \theta)} \exp \left(\sum_{t=1}^{T} \theta_{1}^{\mathrm{T}} f_{1}\left(\mathbf{x}, y_{t}\right)+\sum_{t=1}^{T-1} \theta_{2}^{\mathrm{T}} f_{2}\left(\mathbf{x}, y_{t}, y_{t+1}\right)\right)$

其中 $f1(\mathbf{x},y_t)$ 為狀態(tài)特征或油，一般和位置 $t$ 相關寞忿， $f_2(\mathbf{x}, y_t,y_{t+1})$ 為轉(zhuǎn)移特征，一般可以簡化為 $f_2(y_t,y_{t+1})$ 并使用狀態(tài)轉(zhuǎn)移矩陣來表示顶岸。

1.6腔彰、有向圖和無向圖之間的轉(zhuǎn)換

無向圖模型可以表示有向圖模型無法表示的一些依賴關系，比如循環(huán)依賴辖佣；但它不能表示有向圖模型能夠表示的某些關系霹抛，比如因果關系。

以圖(a)中的有向圖為例卷谈，其聯(lián)合概率分布可以分解為：

$p(x) = p(x_1)p(x_2)p(x_3)p(x_4|x_1,x_2,x_3)$

其中 $p(x_4|x_1,x_2,x_3)$ 和四個變量都相關杯拐。如果要轉(zhuǎn)換為無向圖，需要將這四個變量都歸屬于一個團中世蔗。因此需要將 $x_4$ 的三個父節(jié)點之間都加上連邊端逼，如圖(b)所示。這個過程稱為道德化（Moralization）凸郑。轉(zhuǎn)換后的無向圖稱為道德圖（Moral Graph）裳食。

在道德化的過程中來有向圖的一些獨立性會丟失，比如上面 $X_1\perp X_2\perp X_3|\varnothing$ 在道德圖中不再成立芙沥。

2、推斷

在圖模型中，推斷（Inference）是指在觀測到部分變量 $\mathbf{e}=\{e_1,e_2,\dots,e_m \}$ 時而昨，計算其它變量的某個子集 $\mathbf{q}=\{q_1,q_2,\dots,q_n \}$ 的后驗概率 $p(\mathbf{q}|\mathbf{e})$ 救氯。

假設一個圖模型中，除了變量 $\mathbf{e},\mathbf{q}$ 外歌憨，其余變量表示為 $\mathbf{z}$ 着憨。根據(jù)貝葉斯公式有：

$\begin{aligned} p(\mathbf{q} | \mathbf{e}) & = \frac{ p(\mathbf{q}, \mathbf{e})}{p(\mathbf{e})} \\ &=\frac{\sum_{\mathbf{z}} p(\mathbf{q}, \mathbf{e}, \mathbf{z})}{\sum_{\mathbf{q}, \mathbf{z}} p(\mathbf{q}, \mathbf{e}, \mathbf{z})} \\ \end{aligned}$

因此，圖模型的推斷問題可以轉(zhuǎn)換為求任意一個變量子集的邊際概率分布問題务嫡。

在圖模型中用的推斷方法可以分為精確推斷和近似推斷兩類甲抖。

2.1、變量消除法

以上圖為例心铃，假設推斷問題為計算后驗概率 $p(x_1|x_4)$ ，需要計算兩個邊際概率 $p(x_1,x_4)$ 和 $p(x_4)$ 。

根據(jù)條件獨立性假設藤为，有：

$p(x_1,x_4)=\sum_{x_2,x_3}p(x_1)p(x_2|x_1)p(x_3|x_1)p(x_4|x_2,x_3)$

假設每個變量取 $K$ 個值宁改，計算上面的邊際分布需要 $K^2$ 次加法以及 $3K^2$ 次乘法。

根據(jù)乘法的分配律愉棱，邊際概率 $p(x_1,x_4)$ 可以寫為：

$p(x_1,x_4)=\sum_{x_3}p(x_3|x_1)\sum_{x_2}p(x_2|x_1)p(x_4|x_2,x_3)$

這樣計算量可以減少到 $K^2+K$ 次加法和 $K^2+K+1$ 次乘法唆铐。

這種方法是利用動態(tài)規(guī)劃的思想，每次消除一個變量奔滑，來減少計算邊際分布的計算復雜度艾岂，稱為變量消除法。

2.2朋其、信念傳播算法

信念傳播（Belief Propagation,BP）算法王浴，也稱為和積（Sum-Product）算法或消息傳遞（Message Passing）算法，是將變量消除法中的和積（Sum-Product）操作看作是消息令宿，并保存起來叼耙，這樣可以節(jié)省大量的計算資源。

2.2.1粒没、鏈式結(jié)構(gòu)上的的信念傳播算法

以上圖所示的無向馬爾可夫鏈為例筛婉，其聯(lián)合概率 $p(x)$ 為：

$\begin{aligned} p(\mathbf{x}) &=\frac{1}{Z} \prod_{c \in \mathcal{C}} \phi_{c}\left(\mathbf{x}_{c}\right) \\ &=\frac{1}{Z} \prod_{t=1}^{T-1} \phi\left(x_{t}, x_{t+1}\right) \end{aligned}$

其中 $?(x_t,x_{t+1})$ 是定義在團 $(x_t,x_{t+1})$ 的勢能函數(shù)。

第 $t$ 個變量的邊際概率 $p(x_t)$ 為：

$\begin{aligned} p\left(x_{t}\right) &=\sum_{x_{1}} \cdots \sum_{x_{t-1}} \sum_{x_{t+1}} \cdots \sum_{x_{T}} p(\mathbf{x}) \\ &=\frac{1}{Z} \sum_{x_{1}} \cdots \sum_{x_{t-1}} \sum_{x_{t+1}} \cdots \sum_{x_{T}} \prod_{t=1}^{T-1} \phi\left(x_{t}, x_{t+1}\right) \end{aligned}$

假設每個變量取 $K$ 個值癞松，不考慮歸一化項爽撒，計算上述邊際分布需要 $K^{T?1}$ 次加法以及 $(T?1)K^{T?1}$ 次乘法。

根據(jù)乘法的分配律際概率 $p(x_t)$ 可以通過下面方式進行計算：

$\begin{aligned} p\left(x_{t}\right) &=\frac{1}{Z}\left(\sum_{x_{1}} \cdots \sum_{x_{t-1}} \prod_{j=1}^{t-1} \phi\left(x_{j}, x_{j+1}\right)\right) \cdot\left(\sum_{x_{t+1}} \cdots \sum_{x_{T}} \prod_{j=t}^{T-1} \phi\left(x_{j}, x_{j+1}\right)\right) \\ &=\frac{1}{Z}\left(\sum_{x_{t-1}} \phi\left(x_{t-1}, x_{t}\right) \cdots\left(\sum_{x_{2}} \phi\left(x_{2}, x_{3}\right)\left(\sum_{x_{1}} \phi\left(x_{1}, x_{2}\right)\right)\right)\right) \\ &\left(\sum_{x_{t+1}} \phi\left(x_{t}, x_{t+1}\right) \cdots\left(\sum_{x_{T-1}} \phi\left(x_{T-2}, x_{T-1}\right)\left(\sum_{x_{T}} \phi\left(x_{T-1}, x_{T}\right)\right)\right)\right) \\ &=\frac{1}{Z} \mu_{t-1, t}\left(x_{t}\right) \mu_{t+1, t}\left(x_{t}\right) \end{aligned}$

其中 $\mu_{t-1, t}(x_t)$ 定義為變量 $X_{t-1}$ 向變量 $X_t$ 傳遞的消息响蓉， $\mu_{t-1, t}(x_t)$ 是關于變量 $X_t$ 的函數(shù)硕勿，可以遞歸計算：

$\mu_{t-1, t}\left(x_{t}\right) \triangleq \sum_{x_{t-1}} \phi\left(x_{t-1}, x_{t}\right) \mu_{t-2, t-1}\left(x_{t-1}\right)$

$\mu_{t+1, t}(x_t)$ 為變量 $X_{t+1}$ 向變量 $X_t$ 傳遞的消息，定義為：

$\mu_{t+1, t}\left(x_{t}\right) \triangleq \sum_{x_{t+1}} \phi\left(x_{t}, x_{t+1}\right) \mu_{t+2, t+1}\left(x_{t+1}\right)$

邊際概率 $p(x_t)$ 的計算復雜度減少為 $O(TK^2)$ 枫甲。如果要計算整個序列上所有變量的邊際概率源武，不需要將消息傳遞的過程重復 $T$ 次扼褪，因為其中每兩個相鄰節(jié)點上的消息是相同的。

2.2.2粱栖、樹結(jié)構(gòu)上的信念傳播算法

信念傳播算法也可以推廣到具有樹結(jié)構(gòu)的圖模型上话浇。如果一個有向圖滿足任意兩個變量只有一條路徑（忽略方向），且只有一個沒有父節(jié)點的節(jié)點闹究，那么這個有向圖為樹結(jié)構(gòu)幔崖，其中唯一沒有父節(jié)點的節(jié)點稱為根節(jié)點。如果一個無向圖滿足任意兩個變量只有一條路徑渣淤，那么這個無向圖也為樹結(jié)構(gòu)赏寇。在樹結(jié)構(gòu)的無向圖中任意一個節(jié)點都可以作為根節(jié)點。

樹結(jié)構(gòu)圖模型的信念傳播過程為）從葉子節(jié)點到根節(jié)點依次計算并傳遞消息）從根節(jié)點開始到葉子節(jié)點价认，依次計算并傳遞消息）在每個節(jié)點上計算所有接收消息的乘積（如果是無向圖還需要歸一化）嗅定，就得到了所有變量的邊際概率。

3刻伊、近似推斷

在實際應用中露戒，精確推斷一般用于結(jié)構(gòu)比較簡單的推斷問題。當圖模型的結(jié)構(gòu)比較復雜時捶箱，精確推斷的計算開銷會比較大智什。此外，如果圖模型中的變量是連續(xù)的丁屎，并且其積分函數(shù)沒有閉式解時荠锭，也無法使用精確推斷。因此晨川，在很多情況下也常常采用近似的方法來進行推斷证九。

采樣法是通過模擬的方式來采集符合某個分布 $p(x)$ 的一些樣本，并通過這些樣本來估計和這個分布有關的運算共虑，比如期望等愧怜。

下面介紹基于采樣法的近似推斷。

3.1妈拌、蒙特卡羅方法

蒙特卡羅方法的一個最簡單的應用例子是計算圓周率 $π$ 拥坛。蒙特卡羅方法的基本思想可以歸結(jié)為根據(jù)一個已知概率密度函數(shù)為 $p(x)$ 的分布來計算函數(shù) $f (x)$ 的期望：

$\mathbb{E}[f(x)]=\int_{x} f(x) p(x) d x$

當 $p(x)$ 比較復雜時，很難用解析方法來計算這個期望尘分。為計算 $E[f(x)]$ 猜惋，我們可通過數(shù)值方法來近似計算。首先從 $p(x)$ 中獨立抽取 $N$ 個樣本 $x^{(1)},x^{(2)},\dots,x^{(N)}$ 培愁， $f(x)$ 的期望可以用這 $N$ 個樣本的均值 $\hat{f}_N$ 來近似：

$\hat{f}_N=\frac{1}{N}(f(x^{(1)})+f(x^{(2)})+\dots+f(x^{(N)}))$

根據(jù)大數(shù)定律著摔， $N$ 趨向于無窮大時，樣本均值收斂于期望值：

$\hat{f}_{N} \stackrel{P}{\longrightarrow} \mathbb{E}_{p}[f(x)] \quad when \quad N\longrightarrow \infty$

這就是蒙特卡羅方法的理論依據(jù)定续。

蒙特卡羅方法的難點是如何進行隨機采樣谍咆，即如何讓計算機生成滿足概率密度函數(shù) $p(x)$ 的樣本禾锤。我們知道，計算機可以比較容易地隨機生成一個在 $[0, 1]$ 區(qū)間上均布分布的樣本 $ξ$ 卧波。如果要隨機生成服從某個非均勻分布的樣本时肿，就需要一些間接的采樣方法庇茫。

如果一個分布的概率密度函數(shù)為 $p(x)$ 港粱，其累積分布函數(shù) $cdf(x)$ 為連續(xù)的嚴格增函數(shù)，且存在逆函數(shù) $cdf^{?1}(y),y ∈ [0, 1]$ 旦签，那么我們可以利用累積分布函數(shù)的逆函數(shù)來生成服從該隨機分布的樣本查坪。假設 $ξ$ 是 $[0, 1]$ 區(qū)間上均勻分布的隨機變量 $cdf^{?1}(ξ)$ 服從概率密度函數(shù)為 $p(x)$ 的分布。

但當 $p(x)$ 非常復雜宁炫，累積分布函數(shù)的逆函數(shù)難以計算偿曙，就難以直接對 p(x) 進行采樣，往往需要使用一些間接的采樣策略羔巢，比如拒絕采樣望忆、重要性采樣、馬爾可夫鏈蒙特卡羅采樣等竿秆。這些方法一般是先根據(jù)一個比較容易采樣的分布進行采樣启摄，然后通過一些策略來間接得到符合 $p(x)$ 分布的樣本。

3.2幽钢、拒絕采樣

拒絕采樣歉备，也叫接受-拒絕采樣。假設原始分布 $p(x)$ 難以直接采樣匪燕，我們可以引入一個容易采樣的分布 $q(x)$ 蕾羊，一般稱為提議分布(Proposal Distribution），然后以某個標準來拒絕一部分的樣本使得最終采集的樣本服從分布 $p(x)$ 帽驯。

在拒絕采樣中龟再，已知未歸一化的分布 $\hat{p}(x)$ ，我們需要構(gòu)建一個提議分布 $q(x)$ 和一個常數(shù) $k$ 尼变，使得 $kq(x)$ 可以覆蓋函數(shù) $\hat{p}(x)$ 利凑，即 $kq(x) ≥ \hat{p}(x),?x$ 。如圖所示享甸。

對于每次抽取的樣本 $\hat{x}$ 截碴，計算接受概率（acceptance probability）：

$\alpha(\hat{x})=\frac{\hat{p}(\hat{x})}{kq(\hat{x})}$

并以概率 $\alpha(\hat{x})$ 來接收樣本 $\hat{x}$ 。

拒絕采樣的采樣過程如下：

判斷一個拒絕采樣方法的好壞就是看其采樣效率蛉威，即總體的接受率日丹。如果函數(shù) $kq(x)$ 遠大于原始分布函數(shù) $\hat{p}(x)$ ，拒絕率會比較高樣蚯嫌，效率會非常不理想哲虾。要找到一個和 $\hat{p}(x)$ 比較接近的提議分布往往比較困難丙躏，特別是在高維空間中采樣率會非常低，導致很難應用到實際問題中束凑。

3.3晒旅、重要性采樣

如果采樣的目的是計算分布 $p(x)$ 下函數(shù) $f(x)$ 的期望，那么實際上抽取的樣本不需要嚴格服從分布 $p(x)$ 汪诉。也可以通過另一個分布废恋，即提議分布 $q(x)$ ，直接采樣并估計 $\mathbb{E}_p[f(x)]$ 扒寄。

函數(shù) $f(x)$ 在分布$p(x)下的期望可以寫為：

$\begin{aligned} \mathbb{E}_{p}[f(x)] &=\int_{x} f(x) p(x) d x \\ &=\int_{x} f(x) \frac{p(x)}{q(x)} q(x) d x \\ &=\int_{x} f(x) w(x) q(x) d x \\ &=\mathbb{E}_{q}[f(x) w(x)] \\ \end{aligned}$

其中 $w(x)$ 稱為重要性權重鱼鼓。

重要性采樣（Importance Sampling）是通過引入重要性權重分布將 $p(x)$ 下 $f(x)$ 的期望變?yōu)樵诜植?img class="math-inline" src="https://math.jianshu.com/math?formula=q(x)" alt="q(x)" mathimg="1">下 $f(x)w(x)$ 的期望，從而可以近似為：

$\hat{f}_{N}=\frac{1}{N}\left(f\left(x^{(1)}\right) w\left(x^{(1)}\right)+\cdots+f\left(x^{(N)}\right) w\left(x^{(N)}\right)\right)$

其中 $x^{(1)},x^{(2)},\dots,x^{(N)}$ 是從 $q(x)$ 中獨立抽樣出的樣本點该编。

重要性采樣也可以在只知道未歸一化的分布 $\hat{p}(x)$ 的情況下計算函數(shù) $f(x)$ 的期望：

$\begin{aligned} \mathbb{E}_{p}[f(x)] &= \int_{x} f(x) \frac{ \hat{p}(x)}{Z} d x \\ &=\frac{\int_{x} \hat{p}(x) f(x) d x}{\int_{x} \hat{p}(x) d x} \\ & \approx \frac{\sum_{n=1}^{N} f\left(x^{(n)}\right) \hat{w}\left(x^{(n)}\right)}{\sum_{n=1}^{N} \hat{w}\left(x^{(n)}\right)} \\ \end{aligned}$

其中 $\hat{w}(x)=\frac{\hat{p}(x)}{q(x)}$ 迄本， $x^{(1)},x^{(2)},\dots,x^{(N)}$ 是從 $q(x)$ 中獨立抽樣出的樣本點。

3.4课竣、馬爾可夫鏈蒙特卡羅方法

在高維空間中嘉赎，拒絕采樣和重要性采樣的效率隨空間維數(shù)的增加而指數(shù)降低。馬爾可夫鏈蒙特卡羅方法（MCMC）是一種更好的采樣方法以很容易地對高維變量進行采樣于樟。

MCMC方法也有很多不同的具體采樣方法公条，但其核心思想是將采樣過程看作是一個馬爾可夫鏈：

$x_1,x_2,\dots,x_{t-1},x_t,x_{t+1},\dots$

第 $t + 1$ 次采樣依賴于第 $t$ 次抽取的樣本以及狀態(tài)轉(zhuǎn)移分布（即提議分布） $q(x|x_t)$ ，如果這個馬爾可夫鏈的平穩(wěn)分布為 $p(x)$ 隔披，那么在狀態(tài)平穩(wěn)時抽取的樣本就服從 $p(x)$ 的分布赃份。

MCMC方法的關鍵是如何構(gòu)造出平穩(wěn)分布為 $p(x)$ 的馬爾可夫鏈，并且該馬爾可夫鏈的狀態(tài)轉(zhuǎn)移分布 $q(x|x^{'})$ 一般為比較容易采樣的分布奢米。

使用MCMC方法進行采樣時需要注意兩點：一是馬爾可夫鏈需要經(jīng)過一段時間的隨機游走才能達到平穩(wěn)狀態(tài)抓韩，這段時間稱為預燒期（Burn-in Period）。預燒期內(nèi)的采樣點并不服從分布 $p(x)$ 鬓长，需要丟棄谒拴；二是基于馬爾可夫鏈抽取的相鄰樣本是高度相關的。而在機器學習中涉波，我們一般需要抽取的樣本是獨立同分布的英上。為了使得抽取的樣本之間獨立，我們可以每間隔 $M$ 次隨機游走啤覆，抽取一個樣本苍日。如果 $M$ 足夠大則可以認為抽取的樣本是獨立的。

3.4.1窗声、Metropolis-Hastings 算法

Metropolis-Hastings算法相恃，簡稱MH算法，是一種應用廣泛的MCMC方法笨觅。

假設馬爾可夫鏈的狀態(tài)轉(zhuǎn)移分布（即提議分布 $q(x|x^{'})$ 為一個比較容易采樣的分布拦耐，其平穩(wěn)分布往往不是 $p(x)$ 耕腾。為此MH算法引入拒絕采樣的思想來修正提議分布，使得最終采樣的分布為 $p(x)$ 杀糯。

在MH算法中設第 $t$ 次采樣樣本為 $x_t$ 扫俺，首先根據(jù)提議分布 $q(x|x_t)$ 抽取一個樣本 $\hat{x}$ ，并以概率 $A(\hat{x},x_t)$ 來接受 $\hat{x}$ 作為第 $t+1$ 次的采樣樣本 $x_{t+1}$ ：

$A(\hat{x},x_t)=\min(1,\frac{p(\hat{x})q(x_t|\hat{x})}{p(x_t)q(\hat{x}|x_t)})$

因為每次 $q(x|x_t)$ 隨機生成一個樣本 $\hat{x}$ 固翰，并以 $A(\hat{x},x_t)$ 的概率接受狼纬，因此修正的馬爾可夫鏈狀態(tài)轉(zhuǎn)移概率為：

$q^{'}(\hat{x}|x_t)=q(\hat{x}|x_t)A(\hat{x},x_t)$

該修正的馬爾可夫鏈可以達到平穩(wěn)狀態(tài)，且平穩(wěn)分布為 $p(x)$ 倦挂。

證明：根據(jù)馬爾可夫鏈的細致平穩(wěn)條件畸颅，有：

$\begin{aligned} p\left(\mathbf{x}_{t}\right) q^{\prime}\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right) &=p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right) A\left(\hat{\mathbf{x}}, \mathbf{x}_{t}\right) \\ &=p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right) \min \left(1, \frac{p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right)}{p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right)}\right) \\ &=\min \left(p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right), p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right)\right) \\ &=p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right) \min \left(\frac{p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right)}{p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right)}, 1\right) \\ &=p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right) A\left(\mathbf{x}_{t}, \hat{\mathbf{x}}\right) \\ &=p(\hat{\mathbf{x}}) q^{\prime}\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right) \end{aligned}$

因此 $p(x)$ 是狀態(tài)轉(zhuǎn)移概率為 $q^{′}(\hat{x}|x_t)$ 的馬爾可夫鏈的平穩(wěn)分布。

3.4.2方援、Metropolis算法

如果MH算法中的提議分布是對稱的，即 $q(\hat{x}|x_t) = q(x_t|\hat{x})$ 涛癌，第 $t + 1$ 次采樣的接受率可以簡化為：

$A(\hat{x},x_t)=\min(1,\frac{p(\hat{x})}{p(x_t)})$

這種MCMC方法稱為Metropolis算法犯戏。

3.4.3、吉布斯采樣

吉布斯采樣是一種有效地對高維空間中的分布進行采樣的MCMC方法拳话，可以看作是Metropolis-Hastings算法的特例先匪。

吉布斯采樣使用全條件概率作為提議分布來依次對每個維度進行采樣，并設置接受率為 $A = 1$ 弃衍。

對于一個 $M$ 維的隨機向量 $X = [X_1,X_2,\dots,X_M]^T$ 呀非，其第 $i$ 個變量 $X_i$ 的全條件概率為：

$\begin{aligned} p\left(x_{i} | \mathbf{x}_{i}\right) & \triangleq P\left(X_{i}=x_{i} | X_{\backslash i}=\mathbf{x}_{\backslash i}\right) \\ &=p\left(x_{i} | x_{1}, x_{2}, \cdots, x_{i-1}, x_{i+1}, \cdots, x_{M}\right) \end{aligned}$

其中 $\mathbf{x}_{\backslash i}=[x_{1}, x_{2}, \cdots, x_{i-1}, x_{i+1}, \cdots, x_{M}]^T$ 表示除 $X_i$ 外其他變量的取值。

吉布斯采樣可以按照任意的順序根據(jù)全條件分布依次對每個變量進行采樣镜盯。假設從一個隨機的初始化狀態(tài) $x^{(0)} = [x_1^{(0)} , x_2^{(0)} , · · · , x_M^{(0)}]^T$ 開始岸裙，按照下標順序依次對 $M$ 個變量進行采樣。

吉布斯采樣的每單步采樣也構(gòu)成一個馬爾可夫鏈速缆。假設每個單步（采樣維度為第 $i$ 維）的狀態(tài)轉(zhuǎn)移概率 $q(x|x^{′})$ 為：

$q\left(\mathbf{x} | \mathbf{x}^{\prime}\right)=\left\{\begin{array}{cc}{\frac{p(\mathbf{x})}{p\left(\mathbf{x}_{\backslash i}^{\prime}\right)}} & {\text { if } \mathbf{x}_{\backslash i}=\mathbf{x}_{\backslash i}^{\prime}} \\ {0} & {\text { otherwise }}\end{array}\right.$

其中邊際分布 $p(\mathbf{x}_{\backslash i}^{'})=\sum_{x^{'}}p(x^{'})$ 降允，等式 $\mathbf{x}_{\backslash i}=\mathbf{x}_{\backslash i}^{\prime}$ 表示 $x_j = x_j^{'}, ?j \neq i$ ，因此有 $p(\mathbf{x}_{\backslash i}^{'})=p(\mathbf{x}_{\backslash i})$ 艺糜，并可以得到：

$p\left(\mathbf{x}^{\prime}\right) q\left(\mathbf{x} | \mathbf{x}^{\prime}\right)=p\left(\mathbf{x}^{\prime}\right) \frac{p(\mathbf{x})}{p\left(\mathbf{x}_{\backslash i}^{\prime}\right)}=p(\mathbf{x}) \frac{p\left(\mathbf{x}^{\prime}\right)}{p\left(\mathbf{x}_{\backslash i}\right)}=p(\mathbf{x}) q\left(\mathbf{x}^{\prime} | \mathbf{x}\right)$

根據(jù)細致平穩(wěn)條件狀態(tài)轉(zhuǎn)移概率 $q(x|x^{′})$ 的馬爾可夫鏈的平穩(wěn)分布為 $p(x)$ 剧董。

4、學習

圖模型的學習可以分為兩部分：一是網(wǎng)絡結(jié)構(gòu)學習破停，即尋找最優(yōu)的網(wǎng)絡結(jié)構(gòu)翅楼；二是網(wǎng)絡參數(shù)估計，即已知網(wǎng)絡結(jié)構(gòu)真慢，估計每個條件概率分布的參數(shù)毅臊。網(wǎng)絡結(jié)構(gòu)學習一般比較困難，一般是由領域?qū)＜襾順?gòu)建晤碘。這里只討論在給定網(wǎng)絡結(jié)構(gòu)條件下的參數(shù)估計問題褂微。

4.1功蜓、不含隱變量的參數(shù)估計

如果圖模型中不包含隱變量，即所有變量都是可觀測的宠蚂，那么網(wǎng)絡參數(shù)一般可以直接通過最大似然來進行估計式撼。

有向圖模型：在有向圖模型中，所有變量 $x$ 的聯(lián)合概率分布可以分解為每個隨機變量 $x_k$ 的局部條件概率 $p(x_k|x_{π_k};θ_k)$ 的連乘形式求厕，其中 $θ_k$ 為第 $k$ 個變量的局部條件概率的參數(shù)著隆。

給定 $N$ 個訓練樣本 $D = \{x^{(n)}\}_{n=1}^N$ ，其對數(shù)似然函數(shù)為：

$\begin{aligned} \mathcal{L}(\mathcal{D} ; \theta) &=\frac{1}{N} \sum_{n=1}^{N} \log p\left(\mathbf{x}^{(n)} ; \theta\right) \\ &=\frac{1}{N} \sum_{n=1}^{N} \sum_{k=1}^{K} \log p\left(x_{k}^{(n)} | x_{\pi_{k}}^{(n)} ; \theta_{k}\right) \\ \end{aligned}$

其中 $θ_k$ 為模型中的所有參數(shù)呀癣。

因為所有變量都是可觀測的美浦，最大化對數(shù)似然 $L(D;θ))$ ，只需要分別地最大化每個變量的條件似然來估計其參數(shù)项栏。

$\theta_{k}=\arg \max \sum_{n=1}^{N} \log p\left(x_{k}^{(n)} | x_{\pi_{k}}^{(n)} ; \theta_{k}\right)$

無向圖模型：在無向圖模型中浦辨，所有變量 $x$ 的聯(lián)合概率分布可以分解為定義在最大團上的勢能函數(shù)的連乘形式。以對數(shù)線性模型為例：

$p(\mathbf{x} ; \theta)=\frac{1}{Z(\theta)} \exp \left(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)\right)$

其中 $Z(\theta)=\sum_{\mathbf{x}} \exp \left(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)\right)$ 沼沈。

給定 $N$ 個訓練樣本 $D = \{x^{(n)}\}_{n=1}^N$ 流酬，其對數(shù)似然函數(shù)為：

$\begin{aligned} \mathcal{L}(\mathcal{D} ; \theta) &=\frac{1}{N} \sum_{n=1}^{N} \log p\left(\mathbf{x}^{(n)} ; \theta\right) \\ &=\frac{1}{N} \sum_{n=1}^{N}\left(\sum_{c \in C} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}^{(n)}\right)\right)-\log Z(\theta) \\ \end{aligned}$

其中 $θ_c$ 為定義在團 $c$ 上的勢能函數(shù)的參數(shù)。

可以看出列另，無向圖模型的參數(shù)估計要比有向圖更為復雜芽腾。在有向圖中，每個局部條件概率的參數(shù)是獨立的页衙；而在無向圖中摊滔，所有的參數(shù)都是相關的，無法分解店乐。

因此艰躺，無向圖的參數(shù)估計通常采用近似的方法。一是利用采樣來近似計算這個期望响巢；二是坐標上升法描滔，即固定其它參數(shù)，來優(yōu)化一個勢能函數(shù)的參數(shù)踪古。

4.2含长、含隱變量的參數(shù)估計

如果圖模型中包含隱變量，即有部分變量是不可觀測的伏穆，就需要用EM算法進行參數(shù)估計拘泞。

最后編輯于：2020.03.02 23:27:04

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市枕扫，隨后出現(xiàn)的幾起案子陪腌，更是在濱河造成了極大的恐慌，老刑警劉巖，帶你破解...
沈念sama閱讀 223,126評論 6贊 520
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件诗鸭，死亡現(xiàn)場離奇詭異染簇，居然都是意外死亡，警方通過查閱死者的電腦和手機强岸，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,421評論 3贊 400
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門锻弓，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人蝌箍，你說我怎么就攤上這事青灼。” “怎么了妓盲？”我有些...
開封第一講書人閱讀 169,941評論 0贊 366
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵杂拨，是天一觀的道長。經(jīng)常有香客問我悯衬，道長弹沽，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 60,294評論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任甚亭，我火速辦了婚禮贷币，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘亏狰。我一直安慰自己，他們只是感情好偶摔，可當我...
茶點故事閱讀 69,295評論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布暇唾。她就那樣靜靜地躺著，像睡著了一般辰斋。火紅的嫁衣襯著肌膚如雪策州。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,874評論 1贊 314
城市分裂傳說
那天宫仗，我揣著相機與錄音够挂，去河邊找鬼。笑死藕夫，一個胖子當著我的面吹牛孽糖，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播毅贮，決...
沈念sama閱讀 41,285評論 3贊 424
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼办悟，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了滩褥？” 一聲冷哼從身側(cè)響起病蛉，我...
開封第一講書人閱讀 40,249評論 0贊 277
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后铺然，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體俗孝，經(jīng)...
沈念sama閱讀 46,760評論 1贊 321
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,840評論 3贊 343
?白月光啟示錄
正文我和宋清朗相戀三年魄健，在試婚紗的時候發(fā)現(xiàn)自己被綠了赋铝。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,973評論 1贊 354
活死人
序言：一個原本活蹦亂跳的男人離奇死亡诀艰，死狀恐怖柬甥，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情其垄，我是刑警寧澤苛蒲，帶...
沈念sama閱讀 36,631評論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站绿满，受9級特大地震影響臂外，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜喇颁，卻給世界環(huán)境...
茶點故事閱讀 42,315評論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一漏健、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧橘霎，春花似錦蔫浆、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,797評論 0贊 25
一樁弒父案瓦盛，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至外潜，卻和暖如春原环，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背处窥。一陣腳步聲響...
開封第一講書人閱讀 33,926評論 1贊 275
情欲美人皮
我被黑心中介騙來泰國打工嘱吗，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人滔驾。一個月前我還...
沈念sama閱讀 49,431評論 3贊 379
代替公主和親
正文我出身青樓谒麦，卻偏偏與公主長得像，于是被迫代替她去往敵國和親嵌灰。傳聞我的和親對象是個殘疾皇子弄匕，可洞房花燭夜當晚...
茶點故事閱讀 45,982評論 2贊 361