014 機率推理

Post date: 2013/1/14 下午 12:31:22

本章我們解釋,如何根據機率論法則建構網路模型,以在不確定性之下進行推理。

不確定領域中的知識表示

在第十三章中,我們已經看到全聯合機率分布能夠回答關於領域的任何問題,然而當變數數目增多時,分布的規模會增大到難解的程度。

此為,為每個可能世界個別指派機率是不自然且冗長的。

變數之間的獨立性和條件獨立關係可以大幅減少為了定義全聯合機率分布所需要指定的機率樹木。

本節將介紹一種稱為貝氏網路(bayesian network)的資料結構,用以表示變數之間的依賴關係。

貝氏網路基本上可以表示為任何全聯合機率分布且於許多情況皆可非常簡潔地表示。

貝氏網路是一個有向圖,其中每個節點都標註了定量機率資訊。其完整的規範如下:

1. 每個節點皆符合隨機變數,其中變數可能是離散或連續。

2. 一組有向連結(即箭頭)將節點成對連接。如果有一根箭頭從節點X指向節點Y,則稱X是Y的

一個父(parent)節點。圖中不存在有向循環(因此是一個有向無循環圖(directed acyclic graph,

縮寫為DAG))。

3. 每個節點Xi都有一個條件機率分布P(Xi | Parents(Xi)),量化其父節點們對該節點的影響。

網路的拓樸結構─即節點和連結的集合─描述了在領域中成立的條件獨立關係;精確地描述方法將在下文詳述。

圖14.2 一個典型的貝氏網路,其顯示了拓樸結構和條件機率表(conditional probability table,CPT)。在這些CPT中,

字母B,E,A,J,M分別表示Burglary(竊盜),Earthquake(地震),Alarm(警報),JohnCalls(John 打電話)及MaryCalls(Mary 打電話)

這於圖14.2的條件分布表示了條件機率表或是CPT。(這種形式的表格可以用於離散隨機變數;其他表示方法,包括適合用於連續隨機變數的表示法,

會在第14.2節中描述)。CPT中的每一列包含了每個節點值相對於一個條件事件(conditioning case)的條件機率。

貝氏網路的語意

理解貝氏網路的語意的方式有兩種。

第一種是將貝氏網路視為對聯合機率分布的表示。

第二種將其視為是對條件獨立的語句之集合的編碼。

這兩種觀點是等價的,但是前者能夠幫助我們理解如何建構網路,而後者則能夠幫助我們設計推理程序。

表示全聯合機率分布

看作是一塊「語法」,貝氏網路是一個有向非迴圈圖形,並且每個節點上附加一些數值參數。

一個用以定義網路意義的方法─他的語意─用來定義方法,其中表示對於所有變數的特殊聯合機率分布。

根據等式(14.1)所定義的語意確實為條件機率表。為了說明這一點,我們可以計算警鈴響了,但既沒有盜賊闖入,

也沒有發生地震同時John和Mary都打電話的機率。由聯合分佈相乘元素(使用單一字母命名變數):

P(j,m,a,倒b,倒e)=P(j|a) P(m|a) P(a|倒b 交集 倒e) P(倒b) P(倒e)

=0.90 * 0.70 * 0.001 * 0.999 * 0.998 = 0.000628

第13.3節解釋了聯合機率分布可以用來回答任何關於領域的查詢。

如果貝氏網路是對聯合機率分布的一種表示法,那麼透過加總所有相關的聯合條目,他也可以用於回答任何查詢。

一種建構貝氏網路的方法

公式(14.2)蘊含了某些條件獨立關係,可以被用引導知識工程師建構網路的拓樸結構。

首先,我們利用積法則(13.2.1節),以條件機率重寫聯合機率分布:

P(x1,x2,...,xn)=P(xn|xn-1,...,x1)P(xn-1,...,x1)

然後我們重複這個過程,把每個連言機率化約為一個條件機率和一個較小的連言。最後我們得到一個大的連乘:

P(x1,...,xn)=P(xn|xn-1,...,x1)P(xn-1|xn-2,...,x1)...P(x2|x1)P(x1)

=n拍i=1 P(xi|xi-1,...,x1)

這特徵稱作連鎖律(chain rule),對於任何一組隨機變數都成立。

P(Xi | Xi-1,...,X1) = P(Xi | Parents(Xi)) (14.3)

公式(14.3)所說的是,只有在給定了父節點之後,每個節點都與排在他前面的先行節點(predecessor)條件獨立時,

該貝氏網路才是對領域的一個正確表示。

依照下列的方法可滿足這些條件:

1. 節點:首先決定變數的集合以用來塑模定義域。而後將其排序{X1,...,Xn}。任何順序皆可,但若

參數是有序則得到的結論網路會較精簡。

2. 連結:對於i=1至n作:

● 選擇由 X1,...,Xi-1一組最小的父集合給Xi,,如同滿足等式(14.3)的型態。

● 對於所有父集合插入一個由父集合至Xi之連結。

● 條件機率表:寫下條件機率表,P(Xi|Parents(Xi))。

正規來說,我們相信下述條件獨立性語句成立:

P(MaryCalls | JohnCalls,Alarm,Earthquake,Burglary)= P(MaryCalls | Alarm)

因此Alarm 將是 MaryCalls 的唯一父節點。

由於每一個節點僅連接先前的節點,這樣的建構方式確保網路是非循環的。另一個貝氏網路的重要特徵是他們沒有冗餘機率值。

若沒有冗餘,則沒有可能有矛盾情況:對於知識工程師或領域專家不可能違反機率公理而建立貝氏網路。

小巧性與節點排序

作為對領域的一種完備且不累贅的表示,貝氏網路往往比全聯合機率分布小巧(compact)得多。

貝氏網路的小巧是局部結構化(locally structured)或稱稀疏(sparse)系統中一個非常普遍的特性的例子。在一個局部結構化系統中,不論組件的總數有多少,

每個不建都只與有線數量的其他組件直接互動。局部結構通常伴隨著線性的而非指數及的複雜度增長。

在貝氏網路的情況下,我們可以合理地作以下假設:對於某個常數k,大多數領域中每個隨機變數只受到至多k個其他隨機變數的影響。

如果為簡單起見我們假設有n個布林變數,那麼要指定每個條件機率表所需的資訊至多為2 ^ k 個數字,而整個網路便可用不超過n2 ^k個數字描述。

反之,聯合機率分佈會包含2 ^n個資料。為了使其更具體,可以假設我們有 n=30 個節點,每個節點有 5個父節點(k=5)。那麼貝氏網路需要 960個數字,

但全聯合機率分布需要的數字超過10億個。

在有些領域中,每個變數都被所有其他變數所直接影響,也至於網路是完全連通的。那麼指定貝氏網路的條件機率表

所需的資料量就和指定聯合機率分佈所需的一樣多。

如果地震發生了,John和Mary即使聽到了警報聲也部會打電話,因為他們會假定地震是引起警鈴的原因。

是否需要加入從節點Earthquake到節點JohnCalls以及節點MaryCalls的連節(並因此增大條件機率表)取決於提高機率精確度的重要性

與指定額外資訊的成本之間的權衡。

貝氏網路中的條件獨立關係

我們已經將貝氏網路的「數值」語意表示為全聯合分佈,當我們使用這樣的語意來導出建構貝氏網路的方法,

我們會被導向這樣的結果:若父節點已知,一個節點與他的先行節點們之間是條件獨立的。事實上,我們也可以反向而行。我們可以從拓樸語意出發,

指向圖結構所編碼的條件獨立關係,然後我們可以由此推導出數值語意。

給定父節點,拓樸語意指定每個非後裔的變數為條件獨立

條件分佈的有效率表示

父節點與子節點之間的關係是完全任意的。通常來說,這種關係可以用一個符合某種標準模式的正則分佈(canonical distrbution)來描述。

確定性節點(deterministic nodes) 一個確定性節點的值完全由由其父節點的值所決定,沒有任何不確定性。

不確定性關係經常可以用所謂的雜訊(noisy)邏輯關係來刻畫。

一個標準的例子是雜訊或(noisy-OR)關係,是邏輯或的一般化。

假設所有可能原因都已列出(假設有些部分遺失,我們總是可以增加一個稱之為遺漏節點(leak node)來涵蓋「各式各樣的原因」)

包含連續變數的貝氏網路

一種處理連續性隨機變數的可能方式是透過離散化(discretization)─也就是,將所有可能值劃分到固定的一組區間中─

以避免出現連續變數。

同時包含離散隨機變數和連續隨機變數的網路稱為混合貝氏網路(hybrid Bayesian network)。

貝氏網路中的精確推理

再給定某個以觀察事件─也就是一組證據變數的某個賦值後,任何機率推理系統的基本任務都是要計算一組查詢變數的事後機率分佈。

透過窮舉進行推理

變數消元演算法

對因數的運算

變數次序和變數相關性

精確推理的複雜度

在貝氏網路中精確推理的複雜度與其網路架構極度相關。圖14.2所示的防盜網路屬於這樣一個網路家族:

網路中任何兩個節點都至多只有一條無向路徑相連。這種網路結構稱為單連通(singly connected)網路

或者多樹(polytree),有一個特別好的性質:多樹上的精確推理的時間與空間複雜度都與網路規模呈線性關係。

這裡,網路規模定義為條件機率表中的條目個數;如果每個節點的父節點個數都不超過某個常數,

那麼複雜度與網路節點個數呈線性關係。

團演算法

對於回答單個查詢,變數消元演算法是簡單有效的。然而,假若我們希望計算出網路中所有節點變數的事後機率,那麼變數消元演算法就不那麼地有效了。

團演算法的基本想法是將網路中的單獨節點聯合起來形成團(cluster)節點,使得最終得到的網路結構是一顆多樹。

貝氏網路的近似推理

直接取樣演算法

貝氏網路中的拒絕取樣演算法

似然加權

似然加權(likelihood weighting)只產生與證據e一致的事件,從而避免拒絕取樣演算法的低效率。

這是一般的重點取樣統計技術的特殊實例,專為貝氏網路中的推論所設計。

馬可夫鏈模擬的推理

馬可夫鏈蒙地卡羅(Markov chain Monte Carlo,以下簡稱為MCMC)演算法作用將予拒絕取樣和似然加權有些許不同。

貝氏網路中的吉布斯演算法

吉布斯取樣演算法對於貝氏網路再任意狀態開始(根據證據變數修改他們的預測值),並且藉由從非證據變數Xi中隨機取樣一個值

以產生下一個狀態。

吉布斯取樣進行原理

現在我們要證明MCMC能夠為事後機率返回一致估計。

這個不尋常的特性來自於特定的轉移機率(transition probability),也就是過程從一種狀態轉移到另一種狀態的機率,透過被取樣變數再給定馬可夫涵蓋下

的條件機率分佈而定義。

關連與一階機率模型

可能世界

對於貝氏網路,可能世界將值指定給變數,特別地以布林例子,可能世界與這些命題邏輯相同。

對於一階機率模型,可能世界必須為一階邏輯─即是物件的集合之間有關係,且說明於這些物件對應關係,常數符號對應於物件

、謂詞符號對於關係、及函數符號對於函數。

機率模型也必須定義出每個可能世界的機率,就如同貝氏網路定義機率指定值給變數。

資料庫語意建立獨特名稱假設─這裡我們採用在常數符號。這也假設定義域封閉─此外沒有更多的物件被命名。

沒有關係由符號對應至物件或關於物件存在的不確定性。我們稱這些依照此方式定義的模型為關係機率模型(relational probability models 或 RPMs)。

每個顧客是由登入識別碼(ID)來區分辨識,但不誠實的顧客可能會有上千個ID!在電腦安全領域,這種多重ID稱為錫比(sibyl)

關係機率模型

如同一階邏輯,RPM 包含常數、函數和謂詞符號(其結果更容易看出謂詞如同函數會回傳 true 或 false)。

我們也假設類型特徵(type signature)給每個函數,也就是說對於各個參數和函數值的類型描述。

假設每個物件的類型為已知的,許多偽造的可能世界就將會根據這個機制被排除。

RPM 的語義包含了這些已知常數的相關實例,給出貝氏網路,其定義透過RPM 隨機變數的聯合分佈。

我們可藉由導入特定文脈獨立性以反映出事實來改善這個模型,將忽略不真誠的顧客所提的評價。

如何於RPM做推論。一個方法是收集證據、查詢和其中的常數符號建立等價貝氏網路,應用

於本章以探討過的推論模型。這樣的技術稱為展開。

所有前述的方法假設RPM 必須為部分或完整未展開於貝氏網路。這正類似於於一階邏輯推論的泛化命題之方法。

開放宇宙的機率模型

先前所爭議的資料庫語義適用於我們知道相關物件的集合確實存在且可明確地辨識他們之情況

(實際上,關於物件的所有事實正確地與常數符號命名)。在許多真實世界設置,然而這些假設是根本站不住腳的。

● 前瞻系統不會知道什麼存在,若任何事於下一個轉角,也將不會知道他目前所見的是否與數分鐘後是同一個。

● 本文理解系統不會更進一步地知道文本中那些單元是特定的,並且有關片語例如「Mary」、「Dr.Smith」、「she」、「his cardiologist」、「his mother」

等等諸如此類指的是相同的目標。

● 情報分析人員搜索間諜從不知確實有多少的間諜存在,並且只能猜測各種假名、電話號碼與目擊屬於同一人。

不確定推理的其他方法

● 預設推理(default reasoning),他不是把結論當作在某種程度上相信,而是將其當作相信,除非找到相信其他事物的更好理由。

● 基於規則(rule-based)的方法也被嘗試用來處理不確定性。這種方法希望建立在基於規則的邏輯系統的成功基礎上,不過對每條規則增加某種偽因數以容納不確定性。

● Dempster-Shafer 理論使用區間值(interval-valued)信度來表示代理人對命題機率的知識。

● 機率採用與邏輯相同的本體論約定:事件在世界中或為真或為假,即使代理人不能肯定究竟屬於哪種情況。

而模糊邏輯(fuzzy logic)的研究者們則提出了一種允許模糊性的本體論:事件可以在某種程度為真。

基於規則的不確定推理方法

基於規則的系統出現於早先圍繞實用和值觀的邏輯推理系統所做的研究工作。

整體而言,邏輯系統,特別是基於規則的邏輯系統,具有3個令人滿意的特性:

● 局部性(locality):

在邏輯系統中,一旦我們有了規則 A=>B,那麼只要已知證據A,我們就能夠得出結論B,而不用擔心與其他規則衝突。

在機率系統中,我們必須要考量所有的證據。

● 分離性(detachment):

一旦找到了關於命題 B 的一個邏輯證明,那麼在使用中是不需要考慮這個命題到底如何得到的。

也就是說,我們可以將該命題與其準則分離。

相反,在處理機率問題時,信度的證據來源對於後續推理過程是非常重要的。

● 真值函數性(truth-functionality):

在邏輯中,複合語句的真值可以透過其各組成部分的真值來計算。而除非存在非常強的獨立性假設,這種方式的機率組合是行不通的。

用於不確定性推理的真值函數性系統最著名的例子是確定因素模型(certainty factors model)。

表示無知性:Dempster-Shafer 理論

Dempster-Shafer 理論設計的目標是要處理不確定性(uncertainty)和無知性(ignorance)之間的區別。

他不去計算一個命題的機率,而是計算證據可能支持命題的機率。這種信度度量稱為信度函數(belief function),寫作Bel(X)

Dempster-Shafer 理論的數學基礎與這些機率理論有相似的味道,主要的差異在於取代指定機率於可能世界,這個理論

指定團塊於可能世界的集合,也就是事件。

表示模糊性:模糊集與模糊邏輯

模糊集理論(fuzzy set theory)是一種指名一個事物在多大程度上滿足一個模糊描述的方法。

模糊邏輯(fuzzy logic)是一種使用邏輯運算式來描述模糊集合中的隸屬關係的推理方法。

因此,模糊邏輯也是一個真值函數性系統─這是會引起嚴重問題的一個事實。

模糊控制(fuzzy control)是一種透過模糊規則表示實值輸入到輸出的映對關係以建構控制系統的方法論。

模糊謂詞也可以從隨機集(random set)─也就是,可能取值為物件集合的隨機變數─的角度給出機率解釋。

總結

本章描述了貝氏網路,一種已經得到成熟發展的不確定知識表示方法。貝氏網路所扮演的角色大致相當於命題邏輯在確定知識中的角色。

● 貝氏網路是一個節點對應於隨機變數的有向無環圖;每個節點在給定父節點下都有一個條件機率分佈。

● 貝氏網路提供了一種表示域中的條件獨立關係的簡潔方式。

● 貝氏網路指定了全聯合機率分佈,其中的每一個聯合條目被定義為局部條件分佈中的對應條目

的乘積。貝氏網路的規模往往指數集地小於全聯合機率分布。

● 很多條件分佈都可以透過規範分佈族非常緊湊地表示出來。包含離散隨機變數和連續隨機變數

的混合貝氏網路使用多種正則分佈。

● 貝氏網路中的推理意味著給定一個證據變數集合後,計算一個查詢變數集合的機率分佈。精確推理演算法,

例如變數消元演算法,盡可能高效地計算條件機率的乘積的合。

● 在多樹(單連通網路)中,精確推理需要花費與網路規模呈線性關係的時間。而在一般情況下,問題是難解的。

● 諸如似然加權、馬可夫鏈蒙地卡羅方法這樣的隨機近似技術能夠提供對網路的真實事後機率的合理估計,

並能夠處理比精確演算法規模大得多的網路。

● 機率理論能夠和來自於一階邏輯的表示想法相結合,產生不確定條件下的非常強有力的推理系統。

關係機率模型(RPM)中包含了表示限制,能夠保證良好定義的機率分佈可以表示為等價的貝氏網路。

開放宇宙機率模型處理的存在與辨識不確定性,透過一階可能世界的無限空間定義出機率分佈。

● 我們還介紹了各種在不確定性條件下進行推理的替代系統。整體而言,真值函數性系統不太適合處理這樣的推理。