為何需要圖
個二元變量的聯合分布有 個自由參數。直接指定並不切實際,而且整張表也看不出哪些變量影響哪些變量。貝葉斯(Bayes)網絡以一個有向無環圖,加上每個變量一張小型條件表,取代整張聯合表。圖所記錄的建模假設是:每個變量只直接依賴其父節點。本單元證明由此得到的乘積確實是概率分布,並說明圖決定了一族條件獨立性,可用純圖形的 d-分離判準讀出。本單元建基於「條件獨立與證據」一課,亦為「變量消去」一課作準備,因為後者的因子正是這裏定義的各張表。
定義
定義 33.1.1
(貝葉斯網絡及其聯合分布)
設 為隨機變量,各自取值於有限非空集合。貝葉斯網絡包括:
- 一個有向無環圖(DAG),節點為 ;以 表示 的父節點集合;
- 對每個 給出條件概率表(CPT):對每個取值 及父節點的每個聯合取值 ,有數值 ,且對每個 都有 。沒有父節點的節點則給出普通的表 。
網絡定義聯合分布
其中 是 在 的父節點上的限制。拓撲序把節點排列成每個父節點都先於其子節點;因 無環,拓撲序必定存在。若某分布對某些 CPT 等於上述乘積,便稱它按 因子分解。
定義 33.1.2
(條件獨立)
對三個互不相交的變量集合 ,若對所有 的取值都有 ,則稱在給定 時 與 條件獨立,記作 。
因子分解定理
定理 33.1.3
(貝葉斯網絡的因子分解)
設 按拓撲序排列。上述乘積是概率分布,且對每個 及每個滿足 的賦值,
證明
(對最後一個變量求和)
乘積非負。先對 求和。由於次序是拓撲序, 不是任何 ()的父節點,所以只有最後一個因子含 ,而 。因此乘積對 的和等於前 個因子的乘積,即刪去 後的網絡所對應的同類表達式。重複這一步,全部變量的總和等於 ,而且 的邊際分布為 。把第 個邊際分布除以第 個,即得第二個結論。
證明透視
無環性用在哪裏
證明從次序的尾端逐個移走變量。無環性只在一處起作用:移走 之後,其餘因子必須不含 ,而這成立,是因為次序較前的變量都不以 為父節點。於是 令最後一個因子消失,剩下同類的 個節點的網絡,歸納便可繼續。沒有無環性,這一步會失效:取兩個二元變量,邊為 與 ,兩張表在兩個值相同時都是 ,否則是 。乘積在 時為 ,其餘為 ,總和是 而不是 。
因子分解定理就是鏈式法則 ,只是每個條件集合都縮小為父節點。這個縮小才是實質的建模主張:給定父節點時,變量與次序中其餘前驅獨立。因此自由參數個數為 ,父節點集合小時數目很小。
概念視角算法
把乘積看成抽樣程序
按拓撲序逐個訪問節點,依據父節點已抽得的值選出表中對應的一行 ,再從中抽取 。由於父節點必定排在前面,每次運行都有明確定義;運行得出 的概率,就是各次抽取概率的乘積,亦即定義中的乘積。在警報網絡中,運行結果 的概率為 。因此貝葉斯網絡既是一組數字表,也是產生數據的配方。
d-分離
定義 33.1.4
(路徑、阻斷與 d-分離)
圖所蘊涵的獨立性,可通過檢查無向路徑(即相異節點的序列,相鄰節點之間有任一方向的邊)而得。設 是路徑上的節點,其在路徑上的鄰點為 與 ,則該三元組稱為
- 鏈: 或 ;
- 叉:;
- 對撞:。
設 為已觀察節點集合。若路徑含有
- 一個中間節點 的鏈或叉,或
- 一個中間節點 且 沒有後代在 中的對撞,
則稱該路徑被 阻斷。對互不相交的集合 及與兩者都不相交的 ,若每條由 的節點到 的節點的路徑都被 阻斷,便稱 與 被 d-分離;否則稱在給定 時 與 d-連通。
定理 33.1.5
(d-分離的可靠性)
若在 中 與 被 d-分離,則對每個按 因子分解的分布,都有 。
證明
(鏈、叉與對撞三種情形)
我們證明三種基本情形,以說明各條規則的來源,一般情形只陳述而不證明。條件化時均設 。
- 鏈 :。
- 叉 :。
- 對撞 :對 求和得 ,故 。然而 一般不是乘積,所以觀察 或其後代可以產生相依性。
反過來並不成立:d-連通只表示對某些 CPT 的選取,相依性有可能出現,並非對所有選取都成立。
反例模式
對撞點的後代也會使路徑開通
一個誘人的簡化說法是:只要對撞點本身沒有被觀察,經過它的路徑就被阻斷。取網絡 並加上子節點 ,其中 是獨立的公平二元位, 恰在 或 時成立,而 。對撞點 雖未被觀察,但以 為條件就等於以 為條件:,而 ,所以給定 時 與 並不獨立。正確的規則就是定義中的那一條:只有對撞點及其所有後代都沒有被觀察時,經過它的路徑才被阻斷。
例題
例題 33.1.6
(讀出聯合分布的一項並計算參數個數)
取二元變量:入屋爆竊 、地震 、警報 ,以及兩位鄰居 、,邊為 、、、。各表為
而 時 依次為 。對應於 的聯合分布值為
此網絡共有 個自由參數(、 各一個, 四個,、 各兩個),而不受限制的聯合表需要 個。
例題 33.1.7
(d-分離查詢與解釋消除)
在同一個圖中, 與 被 d-分離:唯一的路徑 以 為對撞, 未被觀察,亦沒有被觀察的後代。給定 時兩者 d-連通,因為 是 的後代;給定 時同樣 d-連通。另外, 與 在 下 d-連通(叉 是開通的),但被 d-分離。 與 亦被 d-分離:唯一路徑是經過已觀察節點 的鏈 。
數值顯示對撞效應。首先 ( 一項貢獻 )。於是
得知發生地震會降低爆竊的概率:警報被「解釋掉」了,儘管 與 在先驗下彼此獨立。
例題 33.1.8
(鏈上的相依性與給定中間節點後的獨立性)
取二元變量構成的鏈 ,、、、、。網絡有 個自由參數,完整聯合表則需要 個。其中一項聯合值是 。
沒有觀察時鏈是開通的:,而 ,所以 與 相依。給定 後鏈被阻斷:不論 取何值,、,故 。邊界情形:若 ,鏈仍然 d-連通,但 與 實際上獨立;圖只容許相依,並不強制相依。
常見錯誤與細微之處
常見錯誤
(把邊讀成因果)
只要給定 CPT,因子分解定理對任何 DAG 都成立;邊的方向只決定給出哪些條件表。不同的 DAG 可以定義同一族分布。
常見錯誤
(把 d-連通讀成相依)
d-分離只能證明獨立,從不證明相依。若 是二元變量 的唯一父節點,而 ,則在該網絡中 ,儘管邊 是一條 d-連通路徑。
常見錯誤
(以為觀察節點必定阻斷路徑)
觀察 會阻斷鏈 ,卻會使對撞 開通。觀察一個節點的效果取決於它在路徑上的角色,所以先把每個三元組分類為鏈、叉或對撞,才下判斷。
另有兩點。以一個既不在某條路徑上、也不是該路徑上某個對撞點後代的節點為條件,不會改變該路徑的狀態。此外,只有條件事件概率為正時,條件獨立的陳述才有意義。
習題
快速檢查
(在第一個例題的警報網絡中,計算 。)
每個變量取一項表值相乘,需要時用互補概率。
解答 · 答案
。
快速檢查
(在邊為 、、、、 的 DAG 中,判斷下列各項在 d-分離意義下是否成立:(a) 給定 時的 與 ;(b) 給定 時的 與 ;(c) 給定 時的 與 ;(d) 給定 時的 與 。)
把每條路徑上的三元組分類為鏈、叉或對撞,再判斷路徑是否被阻斷。
解答 · 答案
(a) 成立。叉 因 已觀察而被阻斷;路徑 的對撞點 未被觀察,其唯一後代 亦未被觀察,故被阻斷。(b) 不成立。此時 是對撞點 的後代且已被觀察,所以 開通;另一條路徑仍被阻斷,但只要有一條開通路徑就是 d-連通。(c) 不成立。叉 的中間節點未被觀察,路徑開通。(d) 成立。由 到 的每條路徑( 與 )都以 為鏈上節點,而 已觀察,故兩條都被阻斷。
快速檢查
(設 為獨立的公平二元位,而 恰在 或 時成立。計算 、 與 。)
先寫出 的聯合分布,再對該事件條件化。
解答 · 答案
事件 的概率為 ,其中 的概率為 ,所以第一個值是 。給定 與 , 仍是公平二元位:。給定 與 ,必有 ,值為 。三個值 展示了解釋消除的模式。
快速檢查
(網絡有邊 ,且 。證明 ,儘管 與 d-連通。)
由各表算出 ,並與 比較。
解答 · 答案
無論 為何,對每個 都有 。邊際分布 ,故 ,即 。單獨一條邊是開通路徑,所以兩者 d-連通;這說明 d-連通只是容許相依。