不必一次列出整張聯合分布表
概率模型可以由數張小表指定。回答查詢時,把所有表乘成一張大表雖然可行,卻未必必要。變量消去利用分配律,逐個對隱藏變量求和,同時保留其餘相關的交互作用。
定義 12.1.1
(因子與因子乘積)
假設只有有限個離散變量,每個變量的取值域有限且非空。因子是在某一指定變量子集(其範圍)上的非負實數表。因子乘積對其範圍聯集的一個賦值,乘起各表中與該賦值相符的項。純量是範圍為空的因子。貝葉斯(Bayes)網絡在有向無環圖上提供因子 ,其乘積就是聯合分布。以下計算也適用於其他明確給出的非負因子乘積,但須另行處理正規化。
定義 12.1.2
(限制與未正規化的查詢質量)
固定查詢變量 、取值為 的已觀察變量 和隱藏變量 ;三者不相交且涵蓋模型變量。先在每個含證據的因子中代入對應觀察值,稱為限制;其範圍隨之去掉那些變量。對查詢賦值 ,所需未正規化質量為
分母須為正。若因子乘積是已正規化的聯合分布,分母即 。更一般地,若未正規化權重的總和 為正,其誘導分布滿足 ,後驗比值不變。若 ,這些權重不能定義概率分布。第一式使用原因子;限制後證據參數已代入。若分母為零,此後驗沒有定義,不能把零向量正規化。
消去一步
定義 12.1.3
(消去一個變量)
選一個隱藏變量 。收集範圍包含 的所有當前因子,設為 ,其範圍聯集為 。把它們換成單一因子
其中 是目前賦值在第 個因子範圍上的限制,並令 。不含 的每個因子都保留,包括純量。若沒有因子含 ,對它求和會產生等於其取值域大小的純量;一般網絡輸入通常為每個未觀察變量保留一個因子,但這約定使步驟完整。對 中每個變量重複。讀出查詢值之前不要消去查詢變量。
定理 12.1.4
(變量消去的不變式)
設隱藏變量按任意次序消去, 是目前已消去的集合。作為 以外變量的函數,當前因子的乘積等於限制後原因子乘積對 的所有賦值求和。特別是 時,不論次序如何,其餘因子的乘積對每個查詢賦值都等於 。
證明
(對已消去集合作歸納)
對已消去變量的個數作歸納。 時,當前因子就是限制後的原因子,命題是恆等式。假設命題對 成立,再消去 ,所用的組 是範圍含 的所有當前因子。固定 以外變量的賦值 。組以外的因子範圍都不含 ,所以它們的乘積 與 無關,可以從對 的求和中提出:
右邊是新的當前因子在 的乘積;左邊是舊的當前因子在 的乘積對 求和。由歸納假設,舊乘積的值是原乘積對 求和,而有限和可以重排,所以新乘積在 的值就是原乘積對 求和。歸納完成。這個論證只涉及哪些變量出現在哪個範圍,並不斷言隨機變量在概率上獨立。當 ,其餘範圍都在 內;若某查詢變量不在任何範圍,只是令所得函數沿它取常數。
證明透視
證明為何需要整組因子
證明只用了一個結構事實:收集了該組之後,其餘因子的範圍都不含 。這正是 能離開對 求和的原因,而它之所以成立,是因為該組包含了所有提到 的當前因子。只要有一個這樣的因子留在組外,它就依賴 ,這一步便不成立,所以比「全部收集」更弱的做法都不足夠。證明沒有用到網絡的無環性;無環性只影響範圍會變得多大。
隱藏變量可以任意次序消去:有限求和與乘積可重新排列,精確算術下最終質量相同。然而中間因子範圍可能不同,因而影響時間及儲存量;浮點運算中不同次序也可能產生不同捨入誤差。以共同正數縮放因子不改變最終正規化後驗,但若要還原原證據質量,必須記錄所有縮放常數;不要把數值下溢誤作精確零值。
常見錯誤
(把範圍當成獨立性)
在下面的鏈中消去 時,因子 留在求和之外,是因為 不在它的範圍內。這只是關於表的參數的陳述,並不表示 與 獨立;它們其實相依,因為 ,而 。
帶觀察證據的鏈
例題 12.1.5
(鏈中第一個變量的後驗)
考慮二元變量 ,明確假設分解為
設 、、、、,其餘二元概率為補數。我們要求 。
先把最後因子限制為 ,再消去隱藏變量 :
對 ,;對 ,。剩餘未正規化質量為 和 。因此證據概率為 ,而
常見錯誤
(把中間因子當成後驗)
此處中間因子 是以 為變量的似然,不是 的後驗分布。此例中兩項恰好總和為一只是數值巧合,不能因此把 當成後驗。只將 正規化並不能得到後驗:仍須考慮先驗。若先把 除以共同正數,再乘先驗並於最後正規化,得到的後驗不變,因為該常數會抵消。
概念視角算法
把鏈上的消去看成矩陣乘向量
令 (第一個指標對應 ,第二個對應 ),並令 。則 ,因為 。此處
與上面算出的各項相符。在鏈上,從證據一端起逐個消去隱藏變量,就是逐次作矩陣乘向量。範圍較大時,各表是張量,同一求和就是張量縮並,這也說明為何消去次序決定成本。
例題 12.1.6
(中間變量的後驗)
沿用同一條鏈,以證據 查詢 ,這次消去隱藏變量 。含 的因子是 與 ,所以
得 ,。乘以限制後的因子 , 的質量為 , 為 。總和是 ,與先前的證據概率相同,這正是不變式所要求的與次序無關。因此 ,。
例題 12.1.7
(零項與不可能的證據)
把鏈改為 、。此時 、,質量為 和 。總和為 ,故 、。表中出現零項,並不使證據不可能。再令 :每個 都是 ,總質量為 , 沒有定義。模型認為這個觀察的概率為零,算法必須報告,而不是正規化。
反例模式
消去變量時漏掉證據因子
一個誘人的捷徑,是只用因子 消去 ,理由是 說的是 。在這條鏈上,對 的兩個值都得到 ,質量就是先驗 與 ,於是聲稱 。正確值是 。被漏掉的因子範圍含 ,屬於該組;漏掉它就丟掉了證據。修正方法就是消去步驟的規則:收集範圍含 的所有當前因子。
成本與模型限制
命題 12.1.8
(單步消去的成本)
從 個稠密因子中消去 ,這些因子的範圍聯集為 。這一步最多讀取並相乘 個表項,新因子有 個項目。
證明
(數算範圍聯集的賦值)
的賦值共有 個。對每個賦值,從 個因子各讀一項、相乘,再加進 中去掉 後的賦值所對應的項目。 是 上的稠密表。
即使原本每張表都小,若消去次序產生很大的範圍,所需項目數仍可呈指數增長。變量消去對所指定模型是精確的,但它不證明分解或證據準確反映真實世界。
練習
快速檢查
(在上述鏈中,對 求和以計算 。哪些概率須取補數?)
寫出 。
解答 · 答案
。須取補數的是 、 與 。核對:。
快速檢查
(為何證據概率為零必須報告,而不能正規化?若證據總量為正,其中一個查詢項為零又表示甚麼?)
後驗是質量除以證據總量;想想總量為零時這個商是甚麼。
解答 · 答案
後驗是 。若總量為零,商是 :模型給所觀察的證據概率為零,條件概率沒有定義;改用均勻向量等於自行增加假設,所以必須報告。若總量為正而 ,則在該證據下 的後驗概率為零,其餘項照常正規化;這是合法答案,例如 時 。
快速檢查
(若因子不含所消去變量,為何它可留在求和之外?為何這不證明其範圍內的變量與所消去變量在概率上獨立?)
把 寫成 ,再在鏈上找反例。
解答 · 答案
範圍內沒有 的因子,對 求和時是常數,分配律給出 ;這只涉及表的參數。概率上的獨立是聯合分布的性質。在上述鏈中消去 時, 留在求和之外,但 ,所以 與 相依。