目錄
[toc]

第一部分：貝葉斯網(wǎng)基礎(chǔ)

第二部分：貝葉斯網(wǎng)推理

2.1 概率推理中的變量消元方法

本節(jié)主要介紹基于貝葉斯網(wǎng)的概率推理方法，如何降低推理復(fù)雜度是需要考慮的主要問題。
變量消元方法是用于降低貝葉斯網(wǎng)推理復(fù)雜度的主要手段。而變量消元的復(fù)雜度又與變量消元的順序有關(guān)，通過一些啟發(fā)式算法，可以找到較好的消元順序。
除了尋找較好的消元順序來降低推理復(fù)雜度，還可以通過獨(dú)立性關(guān)系剔除與推理無關(guān)的變量，對(duì)推理問題進(jìn)行簡(jiǎn)化，對(duì)推理問題的簡(jiǎn)化將在下一講再介紹。

2.1.1 推理問題

貝葉斯網(wǎng)推理主要包含三大類問題：后驗(yàn)概率問題、最大后驗(yàn)假設(shè)問題和最大可能解釋問題。其中后驗(yàn)概率問題是最基本的問題。
（1）后驗(yàn)概率問題
后驗(yàn)概率問題是指已知貝葉斯網(wǎng)中某些變量的值，計(jì)算另外一些變量的后驗(yàn)概率分布。如第一部分所使用的Alarm案例中，若接到Mary電話通知警鈴響了，這時(shí)會(huì)計(jì)算『發(fā)生了盜竊』的概率是多少，即計(jì)算 $P(B=y|M=y)$ 。
此類問題中，已知變量稱為證據(jù)變量，記為E，取值記為e；需要計(jì)算后驗(yàn)概率分布的變量稱為查詢變量，記為Q；需要計(jì)算的后驗(yàn)概率分布為 $P(Q|E=e)$ .
人們常說的概率推理指的就是后驗(yàn)概率問題，根據(jù)證據(jù)變量和查詢變量的因果關(guān)系不同，概率推理又可分為以下4種類型：

從結(jié)果到原因的診斷推理。例如，已知Mary打電話，計(jì)算發(fā)生盜竊的概率。
從原因到結(jié)果的預(yù)測(cè)推理。例如，已知發(fā)生了入室盜竊，計(jì)算Mary打電話的概率。
同一結(jié)果的不同原因之間的原因間推理。例如，地震和入室盜竊都是導(dǎo)致警鈴報(bào)警的原因。已知警鈴響，又獲知發(fā)生了地震，則對(duì)入室盜竊這一原因的信度則會(huì)降低。原因之間存在此消彼長(zhǎng)的關(guān)系。
包含上述多種類型的混合推理。例如，已知John打電話和發(fā)生了地震，計(jì)算警鈴響的概率，這里既有診斷推理，又有預(yù)測(cè)推理。

雖然存在以上多種推理類型，但貝葉斯網(wǎng)推理都使用同一種方法來處理，即計(jì)算證據(jù)變量已知條件下查詢變量的條件概率。

（2）最大后驗(yàn)假設(shè)問題
已知證據(jù)E=e，有時(shí)會(huì)對(duì)一些變量的后驗(yàn)概率最大的狀態(tài)組合感興趣，這些變量稱為假設(shè)變量，記作H。H的一個(gè)狀態(tài)組合稱為一個(gè)假設(shè)，記為h。在所有可能的假設(shè)中，找出后驗(yàn)概率最大的那個(gè)假設(shè) $h^*$ ，即：
$h^*=\argmax_h P(H=h|E=e)$
這就是最大后驗(yàn)假設(shè)問題，簡(jiǎn)稱為MAP(Maximum a posteriori hypothesis)。
可以看到，MAP問題的基礎(chǔ)是后驗(yàn)概率問題。但MAP問題的復(fù)雜度與假設(shè)變量H的個(gè)數(shù)呈指數(shù)關(guān)系，對(duì)實(shí)際情況，需要作特殊的化簡(jiǎn)處理，關(guān)于該問題將在下一講進(jìn)行討論。

（3）最大可能解釋問題
在貝葉斯網(wǎng)中，證據(jù)E=e的一個(gè)解釋指的是網(wǎng)絡(luò)中全部變量的一個(gè)與E=e相一致狀態(tài)組合。往往有時(shí)最關(guān)心概率最大的那個(gè)解釋，即最大可能解釋，簡(jiǎn)稱MPE(Most probable explanation)。MPE問題可視為MAP問題的一個(gè)特例，即MAP中的假設(shè)變量H包含了網(wǎng)絡(luò)中所有非證據(jù)變量。

可以看出，以上三種問題中，最基礎(chǔ)的是后驗(yàn)概率問題。而通過變量間的條件獨(dú)立關(guān)系對(duì)聯(lián)合分布進(jìn)行分解，減少模型參數(shù)個(gè)數(shù)，可使推理過程簡(jiǎn)化。下面將介紹最基本的貝葉斯網(wǎng)推理算法：變量消元法。

2.1.2 變量消元法

2.1.2.1 概率分布的分解與推理復(fù)雜度

下面用一個(gè)最簡(jiǎn)單的貝葉斯網(wǎng)來分析推理的復(fù)雜度。
設(shè)有如下圖所示的貝葉斯網(wǎng)，考慮計(jì)算P(D)。

一個(gè)鏈狀貝葉斯網(wǎng)

\begin{split} P(D) &= \sum_{A,B,C} P(A,B,C,D) \\ &= \sum_{A,B,C} P(A)P(B|A)P(C|B)P(D|C) \end{split} \tag{2.1.1}

假設(shè)所有變量均為二值，則上式的運(yùn)算復(fù)雜度如下：

\begin{align*} P(A=0)\{&P(B=0|A=0)[&P(C=0|B=0)P(D|C=0)&\\ &&+P(C=1|B=0)P(D|C=1)&]\\ +&P(B=1|A=0)[&P(C=0|B=1)P(D|C=0)&\\ &&+P(C=1|B=1)P(D|C=1)&]\}\\ +\\ P(A=1)\{&P(B=0|A=1)[&P(C=0|B=0)P(D|C=0)&\\ &&+P(C=1|B=0)P(D|C=1)&]\\ +&P(B=1|A=1)[&P(C=0|B=1)P(D|C=0)&\\ &&+P(C=1|B=1)P(D|C=1)&]\} \end{align*}

其中乘法14次，加法7次，對(duì)與D=0和D=1都要進(jìn)行以上運(yùn)算，所以總共有乘法28次，加法14次。
為了利用聯(lián)合概率分布的分解來降低推理復(fù)雜度，我們可以依次求出P(B)、P(C)和P(D)的邊緣概率分布：

P(B)=P(B|A=0)P(A=0)+P(B|A=1)P(A=1)\\ P(C)=P(C|B=0)P(B=0)+P(C|B=1)P(B=1)\\ P(D)=P(D|C=0)P(C=0)+P(D|C=1)P(C=1)

計(jì)算P(B=0)需要2次乘法和1次加法，從而計(jì)算P(B)共需要4次乘法和2次加法；計(jì)算P(C)和P(D)的復(fù)雜度與P(B)一致。從而，共需12次乘法運(yùn)算和6次加法運(yùn)算。比直接用式(2.1.1)計(jì)算的復(fù)雜度低。
聯(lián)合分布的分解之所以能降低推理復(fù)雜度，是因?yàn)樗沟眠\(yùn)算局部化。在式(2.1.1)中，消去A涉及到所有變量。而在第二種方法中，消去A只涉及到它自身和與它相連的變量B，因此復(fù)雜度降低。在變量眾多的網(wǎng)絡(luò)中，這種運(yùn)算量的降低可能是指數(shù)級(jí)的，與貝葉斯網(wǎng)的節(jié)點(diǎn)度有關(guān)。
下面，我們定義嚴(yán)格的消元運(yùn)算。

2.1.2.2 消元運(yùn)算

在貝葉斯網(wǎng)基本概念中，介紹了聯(lián)合分布的分解的概念。抽象地講，一個(gè)聯(lián)合分布是一個(gè)多變量函數(shù)，分解的概念可以推廣到一般的多元函數(shù)。設(shè) $F(X_1,X_2,\cdots,X_n)$ 是變量 $\{X_1,X_2,\cdots,X_n\}$ 的一個(gè)函數(shù)，而 $\mathscr F = \{f_1,f_2,\cdots,f_m\}$ 是一組函數(shù)，其中每個(gè) $f_i$ 所涉及的變量是 $\{X_1,X_2,\cdots,X_n \}$ 的一個(gè)子集。如果：
$F=\prod_{i=1}^m f_i$
則稱 $\mathscr F$ 是F的一個(gè)分解， $f_1,f_2,\cdots,f_m$ 是這個(gè)分解的因子。
不失一般性，設(shè) $\mathscr F$ 中與 $X_1$ 相關(guān)的函數(shù)為 $\{ f_1,\cdots,f_k \}$ 。
從 $\mathscr F$ 中消去 $X_1$ 的過程稱為消元運(yùn)算，包括指如下過程：
(1) 從 $\mathscr F$ 中刪去所有與 $X_1$ 相關(guān)的函數(shù) $f_1,\cdots,f_k$ ；
(2) 將這些函數(shù)相乘，并通過如下運(yùn)算消去變量 $X_1$ ：
$\sum_{X_1}\prod_i^k f_i$
(3) 將新函數(shù) $\sum_{X_1}\prod_i^k f_i$ 放回 $\mathscr F$ 中。

以下定理保證了該消元運(yùn)算等價(jià)于直接從聯(lián)合概率分布求邊緣概率分布。

定理2.1.1
設(shè) $\mathscr F$ 是函數(shù) $F(X_1,X_2,\cdots,X_n)$ 的一個(gè)分解，設(shè) $\mathscr F'$ 是從 $\mathscr F$ 中消去 $X_1$ 后所得的一組函數(shù)。 $G(X_2,\cdots,X_n)$ 是從 $F(X_1,X_2,\cdots,X_n)$ 中消去 $X_1$ 后所得的函數(shù)。那么
$\mathscr F'$ 是 $G(X_2,\cdots,X_n)$ 的一個(gè)分解。

證明：
設(shè) $\mathscr F =\{ f_1,f_2,\cdots,f_m \}$ ，而 $X_1$ 只在 $\{f_1,\cdots,f_k\}$ 中出現(xiàn)。有：
$\begin{align*} G(X_2,\cdots,X_n)&=\sum_{X_1}F(X_1,X_2,\cdots,X_n)\\ &=\sum_{X_1}\prod_{i=1}^m f_i\\ &=\sum_{X_1}(\prod_{i=1}^k f_i \prod_{i=k+1}^m f_i)\\ &=(\sum_{X_1}\prod_{i=1}^k f_i)\prod_{i=k+1}^m f_i \end{align*}$
定理得證。

2.1.2.3 基于變量消元法的后驗(yàn)概率推理算法

設(shè)X是一個(gè)貝葉斯網(wǎng)N中所有變量的集合， $\mathscr F$ 是N中所有概率分布的集合。按照貝葉斯網(wǎng)的定義， $\mathscr F$ 是N所表示的聯(lián)合概率分布P(X)的一個(gè)分解。
假設(shè)觀測(cè)到了證據(jù)E=e。在 $\mathscr F$ 的因子中，將個(gè)證據(jù)變量設(shè)置為它們的觀測(cè)值，得到另一組函數(shù)，記為 $\mathscr F'$ ，該步驟稱為證據(jù)設(shè)置。 $\mathscr F'$ 是函數(shù)P(Y,E=e)的一個(gè)分解，這里Y=X\E。
設(shè)Q是Y的一個(gè)子集，從 $\mathscr F'$ 中逐個(gè)消去所有在Y中但不在Q中的變量，得到另一個(gè)函數(shù)集合，記為 $\mathscr F''$ 。根據(jù)定理2.1.1， $\mathscr F''$ 是P(Q,E=e)的一個(gè)分解。所以，將 $\mathscr F''$ 中的所有因子相乘，就得到P(Q,E=e)，進(jìn)一步可得到：
$P(Q|E=e)=\frac{P(Q,E=e)}{\sum_Q P(Q,E=e)}$
上述過程給出了一個(gè)計(jì)算后驗(yàn)概率分布的算法，即變量消元法，簡(jiǎn)稱VE算法。其形式化描述如下：

VE(N,E,e,Q,p):
輸入：   N   一個(gè)貝葉斯網(wǎng)
        E   證據(jù)變量
        e   證據(jù)變量的取值
        Q   查詢變量
        p   消元順序，包含所有不在Q和E中的變量
輸出：   P(Q|E=e)
1. 將N中所有概率分布的集合賦值給F
2. 在F的因子中，將證據(jù)變量E設(shè)置為其觀測(cè)值e
3. while(p不空):
4.     設(shè)Z為p中排在最前面的變量，將Z從p中刪除
5.     F←Elim(F,Z)
6. end while
7. 將F中所有因子相乘，得到Q的函數(shù)h(Q)
8. return h(Q)/sum_Q(h(Q))

Elim(F,Z):
輸入：   F   一個(gè)函數(shù)集合
        Z   待消元變量
輸出：   另一個(gè)函數(shù)集合
1. 從F中刪除所有涉及Z的函數(shù)，設(shè)這些函數(shù)為{f1,f2,...,fk}
2. g←將這k個(gè)函數(shù)連乘$\prod_{i=1}^k f_i$
3. h←對(duì)g中的Z累加消元$\sum_Z g$
4. 將h放回F中
5. return F

例2.1.1 在下圖所示的貝葉斯網(wǎng)中，設(shè)證據(jù)為{F=0}，使用VE算法計(jì)算P(A|F=0).

變量消元法示例

設(shè)消元順序p=<C,E,B,D>。
貝葉斯網(wǎng)給出的聯(lián)合分布的分解為：
$\mathscr F = \{P(A),P(B),P(C),P(D|A,B),P(E|B,C),P(F|D,E)\}$
(1) VE算法首先設(shè)置證據(jù)F=0，得：
$\mathscr F = \{P(A),P(B),P(C),P(D|A,B),P(E|B,C),P(F=0|D,E)\}$
(2) 依照消元順序p，首先消去變量C，與C有關(guān)的因子是 $P(C),P(E|B,C)$ ，消去C得：
$\mathscr F = \{ P(A),P(B),P(D|A,B),P(F=0|D,E), \psi_1(B,E) \}$
其中， $\psi_1(B,E)=\sum_C P(C)P(E|B,C)$
(3) 接著消去變量E，與E有關(guān)的因子是 $P(F=0|D,E),\psi_1(B,E)$ ，消去E得：
$\mathscr F=\{P(A),P(B),P(D|A,B),\psi_2(D,B,F=0)\}$
其中， $\psi_2(D,B,F=0)=\sum_E P(F=0|D,E)\psi_1(B,E)$
(4) 接著消去變量B，與B有關(guān)的因子是 $P(B),P(D|A,B),\psi_2(D,B,F=0)$ ，消去B得：
$\mathscr F=\{P(A),\psi_3(A,D,F=0)\}$
其中， $\psi_3(A,D,F=0)=\sum_B P(B)P(D|A,B)\psi_2(B,D,F=0)$
(5) 最后消去變量D，與D有關(guān)的因子是 $\psi_3(A,D,F=0)$ ，消去D得：
$\mathscr F = \{P(A),\psi_4(A,F=0)\}$
其中， $\psi_4(A,F=0)=\sum_D \psi_3(A,D,F=0)$
(6) 計(jì)算 $h(A,F=0)=P(A)\psi_4(A,F=0)$
(7) 返回：
$P(A|F=0)=\frac{h(A,F=0)}{\sum_A h(A,F=0)}$

2.1.3 復(fù)雜度分析

2.1.3.1 復(fù)雜性的度量

在VE算法中，最耗費(fèi)時(shí)間和空間的步驟是對(duì)Elim(F,Z)的調(diào)用，因此可以把這一步的復(fù)雜度作為整個(gè)算法的復(fù)雜度。
Elim(F,Z)從F中挑出所有涉及Z的函數(shù) $\{ f_1,\cdots,f_k \}$ ，將它們相乘得到函數(shù)g，在將Z從g中消去。設(shè) $\{ X_1,\cdots,X_l \}$ 是g中除Z以外的變量。若將g表示為多維表，則g所儲(chǔ)存的函數(shù)值的個(gè)數(shù)為 $|Z|\prod_{i=1}^l|X_i|$ 。該值可作為函數(shù)g復(fù)雜性的一個(gè)恰當(dāng)度量，從而也是Elim(F,Z)的復(fù)雜性的恰當(dāng)度量。我們稱之為變量Z的消元成本，記為 $\mathscr{C}( Z)$ .
在推理過程中，VE算法需要消去多個(gè)變量，設(shè)它們依次為 $Z_1,Z_2,\cdots,Z_n$ 。則VE算法的復(fù)雜度可以用總消元成本 $\mathscr C=\sum_{i=1}^n \mathscr C(Z_i)$ 來度量。式中最大的一項(xiàng)對(duì)整個(gè)式子的大小起支配作用，因此有時(shí)也用其中的最大項(xiàng)來度量VE算法的復(fù)雜度。該最大項(xiàng)被稱為最大團(tuán)的大小，在下一節(jié)討論團(tuán)樹傳播算法時(shí)會(huì)再提到。

2.1.3.2 復(fù)雜度的計(jì)算

VE算法的復(fù)雜度與貝葉斯網(wǎng)的結(jié)構(gòu)相關(guān)。
考慮一個(gè)函數(shù)集合 $\mathscr F = \{f_1,f_2,\cdots,f_m\}$ ，它的結(jié)構(gòu)圖是一個(gè)按如下方法定義的無向圖：
(1) 從空?qǐng)D出發(fā)，對(duì) $\mathscr F$ 中每一個(gè)變量添加一個(gè)節(jié)點(diǎn)；
(2) 對(duì)任意兩個(gè)變量X和Y，若它們出現(xiàn)在同一因子中，則在它們對(duì)應(yīng)的節(jié)點(diǎn)之間添加一條邊；
例如，函數(shù)集合
$\mathscr F = \{ P(A), P(T|A), P(S), P(L|S), P(B|S), P(R|T,L), P(X|R),P(D|R,B) \}$
其結(jié)構(gòu)圖如下所示。

函數(shù)集合F的結(jié)構(gòu)圖

可以看出，結(jié)構(gòu)圖與端正圖相同，結(jié)構(gòu)圖是從函數(shù)集合

\mathscr F

的角度定義，端正圖是從貝葉斯網(wǎng)的角度定義。

從 $\mathscr F$ 中消去一個(gè)變量Z的成本為 $\mathscr{C}(Z)=|Z|\prod_{i=1}^l |X_i|$ ，其中 $Z,X_1,\cdots,X_l$ 是函數(shù) $g=\prod_{i=1}^k f_i$ 所涉及的所有變量，而 $f_1,\cdots,f_k$ 是所有涉及Z的因子。根據(jù)結(jié)構(gòu)圖的定義， $\{ X_1,\cdots,X_l \}$ 是 $\mathscr F$ 的結(jié)構(gòu)圖中與Z相鄰的節(jié)點(diǎn)集合，記為nb(Z)。因此有：
$\mathscr C(Z)=|Z|\prod_{X\in nb(Z)}|X|$

對(duì)于上圖，設(shè)所有變量都取二值。從 $\mathscr F$ 中消去變量T。在結(jié)構(gòu)圖中，T的鄰居節(jié)點(diǎn)nb(T)={A,L,R}，所以：
$\mathscr C(T)=|T|\prod_{X\in nb(T)}|X|=16$

從 $\mathscr F$ 中消去T后得到新的函數(shù)集合 $\mathscr F'$ ， $\mathscr F'$ 的結(jié)構(gòu)圖可以通過對(duì)上圖作如下圖的變換得到：

圖消元

即首先在原圖G中將所有與Z相鄰的節(jié)點(diǎn)nb(Z)兩兩相連，再?gòu)膱D中除去節(jié)點(diǎn)Z，以及與Z相連的所有邊。

考慮一個(gè)消元順序p，通過如下CostVE算法可計(jì)算VE算法的復(fù)雜度。

CostVE(N,E,Q,p):
輸入：   N   貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)
        E   證據(jù)變量
        Q   查詢變量
        p   消元順序，包含所有不再Q(mào)和E中的變量
輸出：   用VE算法計(jì)算P(Q|E=e)的復(fù)雜度
1. 將N端正化為G
2. 從G中除去所有證據(jù)變量
3. 復(fù)雜度C賦初值0
4. while(p不空):
5.     從p中移去第一個(gè)變量Z
6.     C=C+|Z|\prod_{X\in nb(Z)}|X|
7.     從G中消去節(jié)點(diǎn)Z
8. end while
9. return C

例考慮用VE算法消去上圖所示貝葉斯網(wǎng)中所有變量。設(shè)這些變量均取二值，用CostVE算法計(jì)算兩個(gè)不同的消元順序分別對(duì)應(yīng)的消元成本。
(1) 消元順序p=<A,X,D,S,B,L,T,R>
(2) 消元順序p=<R,L,T,D,B,S,A,X>
如下兩圖所示，分別為兩種消元順序的圖變換過程。
第一種順序的消元成本為：
$\mathscr C = 2^2+2^2+2^3+2^3+2^3+2^2+2=46$
第二種順序的消元成本為：
$\mathscr C = 2^6+2^6+2^6+2^5+2^4+2^3+2^2+2=254$

消元順序<A,X,D,S,B,L,T,R>

消元順序<R,L,T,D,B,S,A,X>

2.1.4 消元順序

從上例我們可以看到，兩種不同消元順序會(huì)導(dǎo)致不同的消元成本。在所有消元順序中，總成本最低的消元順序稱為最優(yōu)消元順序。在推理之前，我們希望能預(yù)先確定最優(yōu)消元順序。然而，尋找最優(yōu)消元順序是一個(gè)NP難問題。實(shí)際中，我們可以使用啟發(fā)式規(guī)則來尋找較好、但不一定是最優(yōu)的消元順序。常用的確定消元順序的啟發(fā)式方法包括：最大勢(shì)搜索和最小缺邊搜索。

2.1.4.1 最大勢(shì)搜索

最大勢(shì)搜索的方法為：首先從結(jié)構(gòu)圖中任選一個(gè)節(jié)點(diǎn)，編號(hào)為1；然后在剩下的未編號(hào)節(jié)點(diǎn)中選擇與最多已編號(hào)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，并依次編號(hào)；若出現(xiàn)多個(gè)候選待編號(hào)節(jié)點(diǎn)，則任選一個(gè)；在所有節(jié)點(diǎn)都完成編號(hào)后，按編號(hào)由大到小將節(jié)點(diǎn)排序，該順序則為按最大勢(shì)搜索的消元順序。
以下圖的貝葉斯網(wǎng)為例，用最大勢(shì)搜索來確定消元順序。

最大勢(shì)搜索

第1步，任選一個(gè)節(jié)點(diǎn)，比如B節(jié)點(diǎn)，編號(hào)為1；
第2步，候選待節(jié)點(diǎn)為<S,R,D>，因?yàn)樗鼈兊南噜徆?jié)點(diǎn)中已編號(hào)的數(shù)量都是1，任選其中一個(gè)節(jié)點(diǎn)，比如S，編號(hào)為2；
第3步，候選待編號(hào)節(jié)點(diǎn)為<L,R,D>，它們的相鄰節(jié)點(diǎn)已編號(hào)的數(shù)量都是1，任選其中一個(gè)節(jié)點(diǎn)，比如D，編號(hào)為3；
第4步，候選待編號(hào)節(jié)點(diǎn)為<R>，它的相鄰節(jié)點(diǎn)已編號(hào)的數(shù)量最多，為2，將其編號(hào)為4；
第5步，以此類推，分別將L、T、X、A編號(hào)為5、6、7、8；
最后，按編號(hào)由大到小排序得到<A,X,T,L,R,D,S,B>的消元順序。
有CostVE算法可以計(jì)算得到，該消元順序的成本為46。

2.1.4.2 最小缺邊搜索

定義節(jié)點(diǎn)Z的缺邊數(shù)為消去該節(jié)點(diǎn)后需要添加的邊的條數(shù)。比如在上例的初始貝葉斯圖上，節(jié)點(diǎn){A,T,L,R,S,B,D,X}的缺邊數(shù)分別為{0,2,2,8,1,2,0,0}.
最小缺邊搜索的方法為：計(jì)算所有節(jié)點(diǎn)的缺邊數(shù)，選擇缺邊數(shù)最小的，編號(hào)為1，若有多個(gè)候選待編號(hào)節(jié)點(diǎn)，則任選一個(gè)；從圖中消去該節(jié)點(diǎn)，再重復(fù)以上過程，直至所有節(jié)點(diǎn)都消去。所得編號(hào)，按由小到大排序，該順序即為按最小缺邊搜索的消元順序。
下圖為按最小缺邊搜索的過程，得到的消元順序?yàn)?lt;A,X,T,D,S,L,B,R>，由CostVE算法可以計(jì)算得到，該消元順序的成本為46。

最小缺邊搜索.png

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

貝葉斯網(wǎng)專題4：概率推理中的變量消元方法

貝葉斯網(wǎng)專題4：概率推理中的變量消元方法

第一部分：貝葉斯網(wǎng)基礎(chǔ)

1.1 信息論基礎(chǔ)

1.2 貝葉斯網(wǎng)基本概念

1.3 變量獨(dú)立性的圖論分析

第二部分：貝葉斯網(wǎng)推理

2.1 概率推理中的變量消元方法

2.1.1 推理問題

2.1.2 變量消元法

2.1.2.1 概率分布的分解與推理復(fù)雜度

2.1.2.2 消元運(yùn)算

2.1.2.3 基于變量消元法的后驗(yàn)概率推理算法

2.1.3 復(fù)雜度分析

2.1.3.1 復(fù)雜性的度量

2.1.3.2 復(fù)雜度的計(jì)算

2.1.4 消元順序

2.1.4.1 最大勢(shì)搜索

2.1.4.2 最小缺邊搜索

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

貝葉斯網(wǎng)專題4：概率推理中的變量消元方法

第一部分：貝葉斯網(wǎng)基礎(chǔ)

1.1 信息論基礎(chǔ)

1.2 貝葉斯網(wǎng)基本概念

1.3 變量獨(dú)立性的圖論分析

第二部分：貝葉斯網(wǎng)推理

2.1 概率推理中的變量消元方法

2.1.1 推理問題

2.1.2 變量消元法

2.1.2.1 概率分布的分解與推理復(fù)雜度

2.1.2.2 消元運(yùn)算

2.1.2.3 基于變量消元法的后驗(yàn)概率推理算法

2.1.3 復(fù)雜度分析

2.1.3.1 復(fù)雜性的度量

2.1.3.2 復(fù)雜度的計(jì)算

2.1.4 消元順序

2.1.4.1 最大勢(shì)搜索

2.1.4.2 最小缺邊搜索

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av