013 量化不確定性

Post date: 2013/1/9 下午 01:01:54

本章我們將會看到代理人如何以信度駕馭不確定性

不確定環境下的行動

代理人必須處理不確定性,無論是部分可觀察的、不確定的,或是兩者並存者。

代理人可能也永遠無法確切知道目前是何種狀態,或經過一連串的動作後,在哪個階段結束。

解決問題代理人與邏輯代理人被設計為,藉由紀錄信度狀態(對其可能所處的所有可能世界狀態集之表示)來處理不確定性,

並且產生應變計畫以處理各種可能的事件,事件指的是在執行中由感測器的回報。

代理人無法確定地下出像「計畫A90將使我們及時到達機場」這樣的結論。

反之,代理人得出一個較弱的結論:「計畫A90將使我們及時到達機場,只要車不拋錨,汽油沒用完,我沒遇到任何交通事故,

橋上也沒有交通事故,飛機沒有提前起飛,而且...........」。

這些條件中沒有一個可以演繹得到,所以這個計劃能否成功是無法推論。

這是限制問題(qualification problem),也就是我們到目前為止仍無看到實際解決方法。

在所有可被執行的規劃中,A90是被預期能最大化代理人的效能指標。

效能指標包括能夠及時到達機場趕上飛機,避免長時間、徒勞地在機場等待,以及避免在路上被開超速罰單。

對於A90,代理人擁有的資訊不能保證得到以上任何結果,但可以為他們的達成提供某種程度的把握。

其他計畫,例如A120,也許會增強代理人對準時到達機場的信心,但是也增加了長時間等待的可能性。

該做的事情─即理性決策─因此既取決於各種目標的相對重要性,也取決於達到這些目標的可能性或程度。

不確定性總結

牙疼和蛀牙間的聯繫並不是一方對另一方的邏輯結果。

代理人的知識頂多只能提供相關雨具的確信度(degree of belief,或信度)。我們處理確信度的主要工具為機率理論。

機率理論和邏輯學的本體論約定相同─即在世界由任一個特殊情況要麼成立要麼不成立的事實所組成─

但認識倫理約定卻不相同:邏輯代理人確信每個語句必為是、非或無意見,然而機率代理人為0到1之間的數值作為其確信度。

機率論提供了一種方法來囊括我們的惰性和無知所造成的不確定性,從而解決限制問題。

病患是否蛀牙,為何說蛀牙的機率為0.8,機率敘述由相對應的知識基礎所決定的,而非對應於真實世界。

我們說「患者有蛀牙的機率為0.8,因為她有牙痛症狀」,假若後續我們得知病患有牙周病的病史,

則我們可能有不同的敘述:「病患有蛀牙的機率為0.4,因為她有牙痛且有牙周病的病史。」假設我們

收集更多確切的證據推翻蛀牙,則我們可能說「這位病患根據我們目前所瞭解,有蛀牙的機率幾乎為零」。

每一個個別的主張皆是依據不同的知識基礎。

不確定性與理性決策

代理人必須首先在各種計劃的不同可能結果之間有所偏好。

一個特定結果是一種被完全指定的狀態,包括像是代理人是否按時到達機場,以及在機場需要等待多久等各種因素。

我們將使用效用理論(utility theory)來對偏好進行表示和推理。

透過效用表達的偏好在稱作決策理論(decision)的通用理性決策理論中與機率做結合:

決策理論 = 機率理論 + 效用理論

決策理論最基本想法是:一個代理人是理性的,若且微弱他選擇能產生最高期望效用的行動,而期望效用是行

動的所有可能結果的平均值。這稱為期望效用最大化(Maximun Expected Utility,MEU)原則。

基本機率標記法

關於機率

機率斷言與邏輯斷言一樣,都是用於可能世界的。但是,當邏輯斷言會將某些世界的存在嚴格排除掉(因為這個世界所對應的邏輯斷言為假)時,機率斷言討論的則是這些可能世界存在的機率有多少。

用機率理論的話來說,所有可能世界的集合就稱為樣本空間(sample space)。

一個完整定義的機率模型(probability model)會對每個可能世界都給定一個機率數值P(w)。機率理論最基本的公理告訴我們,每個可能世界的機率必介於0與1之間,且

所有可能世界的機率加總必為1:

0 <= P(w) <= 1 對於所有w 且加總P(w) = 1

機率判斷與查詢並不適常為可能世界的特定情況,而是其中的集合。例如,我們可能會想要知道諸如兩個骰子點數合計為11,

或是兩個骰子擲出相同點數的機率。在機率理論中,會將這些集合稱為事件(event)─

但是,這個詞我們以在地12章大量用於描述另一個不同的觀念。而在人工智慧中,集合會以採正規語言之命題來描述。

機率像是P(Total = 11)與P(doubles)被稱作為非條件性或事前機率,在缺乏其他資訊的時候,會參造提案的確信度。

多半的時候,然而我們已有一些資訊,通常稱之為證據,這些皆是已展現出來的。

舉例來說,第一個骰子已經出現5,而我們屏息等待另一個投擲結果。

在這個例子中,我們並不是對於擲出相同點數的非條件機率有興趣,而對於擲出相同點數的條件機率或事後機率,在此給定的條件是第一個骰子是5。

語言的命題於機率推斷

可能世界的命題敘述即核備表示為命題邏輯與限制滿足符號的合併元素。他是一個因式表示,

其中可能世界由成對之變數與數值的集合所表示。

變數於機率理論中稱之為隨機變數,且變數名以大寫字母開始。因此以骰子為例,Total與Die1

皆是隨機變數。每一個隨機變數都有一個定義域─由其可能的值構成之集合。

我們可使用命題邏輯的連接詞合併這些基本命題。

例如,我們可表示「病患是青少年且無牙痛,他有蛀牙的機率為0.1」為如下;

P(cavity | ┐toothache ^ teen) = 0.1

有時候,我們想談論一個隨機變數所有可能值的機率。我們可寫為:

P(Weather = sunny) = 0.6

P(Weather = rain) = 0.1

P(Weather = cloudy) = 0.29

P(Weather = snow) = 0.01

若為縮寫可允許為

P(Weather) = {0.6 , 0.1 , 0.29 , 0.01}

其中粗體字P表示結果為向量的數字,且我們假設預先定義天氣Weather的定義域順序為(sunny,rain,cloudy,snowon)。

我們說P陳述為隨機變數Weather定義一個機率分布。P的註記同樣用於條件分布:P(X|Y)對每個可能的 i 和 j 給出了 P(X = |Y = yi)的值。

P(NoonTemp= x) = Uniform[18C,26C](x)

表示的是,對於中午溫度均勻分布於攝氏18至26度間的信度。我們稱此為機率密度函數

除了單一變數的分布之外,我們還需要多重變數的分布表示。在此使用逗號,例如,P(Weather,Cavity)表示為所有Weather和Cavity值的機率組合。

這是一個4*2的機率表,稱為Weather 和 Cavity 的聯合機率分布( joint probability distribution)。

我們也可混呵變數與數值,P(sunny,Cavity)為兩個元素之向量,給定了在晴天且蛀牙以及晴天且沒有蛀牙的機率。P的表示使得部分的表達更為簡潔。

由目前可能世界的定義,具有如下的機率模型,完全由所有隨機變數的聯合分佈所決定─也稱之為全聯合機率分佈

機率公理與其合理性

機率的基本公理和說明確信度之間的部分關係可根據邏輯關係的命題。例如,對於機率的命題與機率的否定我們可沿生出相似的關聯性

我們也可對於機率的選岩衍生出眾所週知的公式,有時稱之為排容原理:

P(a v b) = P(a) + P(b) - P(a ^ b) (13.4)

這條公里其實很容易記憶。所有a成立的情況以及b成立的情況合起來當然包含了ab的所有情況;

但把這兩組情況相加,就會對他們的交集技術兩次,因此我們必須把P(a ^ b)減掉。

式(13.1)和(13.4)常稱為科莫果洛夫公理(Kolmogorov's axioms)

使用全聯合分佈進行推理

在本捷中我們描述一種機率推理的簡單方法─也就是,根據觀察到的證據計算查詢命題的事後機率。

我們將使用全聯合機率分佈作為「知識庫」,從中倒出所有問題的答案。

一個由3個布林變數 Toothache、Cavity以及Catch(牙醫可怕的鋼針刺進我的牙理了)組成的定義域。

其全聯合分佈是一個2*2*2的表格

toothache ┐toothache

catch ┐catch catch ┐catch

cavity 0.108 0.012 0.072 0.008

┐cavity 0.016 0.064 0.144 0.576

我們只須找出所有蘊含該命題為真的原子事件,然後把他們的機率加起來即可。

命題cavity v toothache 在6個原子事件中成立:

P(cavity v toothache) = 0.108 + 0.012 + 0.072 + 0.008 + 0.0165 + 0.064 = 0.28

將第一行的條目加起來就得到cavity的無條件機率,或者稱為邊緣機率:

P(cavity) = 0.108 + 0.012 + 0.072 + 0.008 = 0.2

這個過程稱為邊緣化,或者稱為加總消去(summing out)─因為我們將所有其他變數的可能直的機率都加總,

因此將他們由等式消去。

獨立性

除非他是神靈化身,否則一個人應該不會認為自己牙齒的問題會影響到天氣。

也被稱為邊緣獨立性和絕對獨立性。

當獨立性斷言可用時,他們能夠幫助縮小領域表示的規模,並降低推理問題的複雜度。

可以用獨立性清楚分割整個集合的變數的情況是相當少見的。

只要兩個變數之間存在著聯繫,無論是多麼間接,獨立性就沒辦法成立。

即使是獨立子集合也可以非常龐大─例如,牙科可能涉及到彼此相關的數十種疾病和數百種症狀。

要處理這樣的問題,我們需要比直截了當的獨立性概念更精細的方法。

(a) (b)

兩個使用絕對獨立把大的聯合分部分解成較小聯合分部的例子。

(a)天氣和牙齒問題是獨立的。(b)硬幣投擲間是獨立的

貝氏法則及其應用

應用貝氏法則:一個簡單例子

P(cause | effect) = P(effect | cause)P(cause) / P(effect)

條件機率P(effect | cause)量化了因果方向的關係,然而P(cause | effect)敘述了診斷方向。

在像是這樣的醫療診斷任務中,我們常有因果關係的條件機率[也就是說醫生知道P(symptoms | disease)]且想要推導出一個診斷P(disease | symptoms)。

醫生知道腦膜炎有(例如)50%的機率會引起病人脖子僵硬。醫生還了解一些無條件事實:病人換腦膜炎的是前機率是 1 / 50000 ,而任何一個病人脖子僵硬的

事前機率為1/20。

我們預期 700 個脖子僵硬的病人中只有 1 個人患有腦膜炎。注意:儘管腦膜炎相當強地蘊含著脖子僵硬的症狀(機率為0.7),但

脖子僵硬的患者患腦膜炎的機率卻仍然很低。這是因為病人脖子僵硬的事前機率高於患腦膜炎的事前機率的緣故。

關於貝氏法則的一個明顯疑問是,何以一個人在一個方向上有可用的條件機率,在反方向卻沒有。

在從症狀到病因的診斷方向上,醫生有量化的資訊。

診斷知識往往要比因果知識脆弱。如果腦膜炎突然大流行,那麼腦膜炎的無條件機率 P(m)會上升。

如果醫生擁有的真段機率 P(m | s) 是直接根據在腦膜炎流行之前對病人的統計觀察得來,他將會對如何更新這個機率值一無所知。

因果資訊 P(s | m) 不受大流行影響,因為他只是反映了腦膜炎的原理。

對這種直接的因果知識,或稱基於模型(model-based)的知識的運用,提供了關鍵的強固性;

這種強固性是實作在現實上可行的機率系統所必需的。

使用貝氏法則 : 合併證據

貝氏法則對於回答在一條證據─例如,脖子僵硬─的條件限制下的機率查詢問題,是非常有用的。

尤其是,我們已經討論過機率資訊經常是以P(effect | cause)的形式出現的。

如果我們知道全聯合分佈,則可以直接讀出:

P(Cavity | toothache ^ catch) = a(0.108 , 0.016 ) = (0.871 , 0.129)

然而我們知道,這種方法的規模不能擴展到大量的變數。

對於給定 Cavity 後彼此條件獨立的 n 種症狀而言,表示的規模以 O(n)而不是 O(2^n)的速度上升。因此,

條件獨立性斷言使得機率系統能夠進行規模擴展;而且,條件獨立性也比絕對獨立性斷言更加易於取得。

從概念上來看,Cavity分隔了Toothache 和 Catch ,因為她是他們二者的直接原因。透過條件獨立性將一個大的機率領域

分解成衣些彼此只有微弱聯繫的子集,是人工智慧領域近來的歷史中最重大的進展之一。

重遊 wumpus 世界

(a) (b)

(a)在方格[1,2]和[2,1]裡面發現微風後,代理人無處可去─沒有安全的方格可以檢索。

(b)對於關於方格[1,3]的查詢,將所有的方格劃分為:Known(已知)、Fringe(邊緣)和Others(其他)

我們可以結合本章捷所介紹的許多想法,以解決wumpus世界的機率推理問題。(關於 wumpus世界的完整描述參見第七章)。

由於wumpus世界中代理人的感測器只提供關於世界的不完整的、局部的資訊,因此不確定性會出現。

例如,上圖顯示了一種情況:在3個可以到達的方格─[1,3],[2,2]以及[3,1]─之中,每一個都有可能包含陷阱。

純粹的羅基推理無法推斷哪個方格最有可能是安全的,所以邏輯代理人也許會被迫隨基地做選擇。

我們會發現機率代理人可以做得比邏輯代理人好得多。

我們的目標是計算這3個方格中每一個包含陷阱的機率。(對於此例我們忽略wumpus和金子。)

wumpus世界的重要性值包括:

(1) 陷阱在所有相鄰方格內引起微風;

(2) 除了方格[1,1]以外的所有方格包含陷阱的機率都是0.2。

第一步是訂出我們需要的一組隨機變數:

● 和在命題邏輯中的情況一樣,我們對於每個方格都需要一個布林變數Pi,j,Pi,j為真若且為若方格[i,j]中確實包含陷阱。

● 我們也需要布林變數 Bi,j;Bi,j為真若且為若方格[i,j]中有微風。我們只為能夠觀察到的方格─

在這裡就是[1,1],[1,2],以及[2,1]─加入這些變數。

下一步是指定全聯合分佈 P(P1,1,....P4,4,B1,1,B1,2,B2,1)。應用積法則,我們有

P(P1,1,...,P4,4,B1,1,B1,2,B2,1) = P(B1,1,B1,2,B2,1 | P1,1,...,P4,4) P(P1,1,...,P4,4)

這個分解形式使我們很容易就看出聯合機率中應該有哪些值。

第一項是在給定陷阱布局後,微風布局的條件機率分佈;若微風相鄰時其值為1,否則等於0。

第二項是陷阱布局的事前機率。

每一個方格包含陷阱的機率都是0.2,並且與其他方格是否包含陷阱無關;

證據包括了從每個走過的方格觀察到(或者未觀察到)的微風,以及這些的方格中不包含陷阱的事實。

我們對回答像P(P1,3 | known,b)這樣的查詢感興趣:在迄今為止得到的觀察資料下,方格[1,3]有陷阱的可能性有多大?

為了回答這個查詢,我們可以按等式(13.9)所提供的標準方法進行,即是將全聯合分佈的項目加總。

令Unknown(未知)為除known(已知)方格及查詢方格[1,3]以外的所有Pi,j變數的集合。

然後根據公式(13.9),我們得到:

P(P1,3 | known,b) = a加總unknown P(P1,3,unknown,known,b)

注意,當邊緣的值與對微風的觀察一致時,運算式P(b | know, P1,3,fringe)等於1,否則等於0。

圖13.6顯示出了這些模型以及他們所關聯的事前機率─P(frontier)。

我們有 P(P1,3 | known, b)= a'(0.2(0.04+0.16+0.16),0.8(0.04+0.16)) = (0.31,0.69)

也就是說,[1,3](以及對稱的[3,1])包含陷阱的機率大約是31%。

第七章提及的邏輯代理人並不知方格[2,2]比其他方格更糟糕。由邏輯可得知於方格[2,2]尚未知是否有陷阱,

但我們必須由機率得知有陷阱的可能性。

本節旨在說明即使看起來非常複雜的問題,也可用機率理論精確地正規化,並透過簡單的演算法得解。

獨立性和條件獨立性關係可以用於對所需的加總進行簡化,已得到有效率的解法。這些關係

通常對應用於我們對問題應該如何拆解的自然理解。

總結

本章對於不確定推理提出一個適用的機率理論基礎以及提供使用的介紹。

● 不確定性是因為懶惰和無知而出現的。在複雜的、非確定的、或部分可觀察的環境中,不確定性是無可避免的。

● 機率表達了代理人在確定語句真假上的力有未逮。機率概括了代理人相對於證據的信心。

● 決策論總和了代理人的信心與期望,定義出了期望效用最大化的最佳行動。

● 基本機率語句包括簡單命題與複合命題上事前機率和條件機率。

● 機率公理限制了對命題機率的可能賦值。違反這些公理的代理人將在某些環境下表現出非理性。

● 全聯合機率分布指定了每個隨機變數的每種可能的值的機率。不過聯合機率分布通常過於龐大,以至於其直接的形式難以建立和使用,

但當有全聯合分佈可用時,他可以用於回答查詢;只要把對應於查詢命題的可能世界的條目加起來即可。

● 隨機變數的子集間的絕對獨立性允許全聯合分佈被分解成較小的聯合分佈,而大幅降低複雜度。現實上絕對獨立很少會發生。

● 貝氏法則允許透過已知的(通常是因果方向的)條件機率來計算未知的機率。將貝氏法則應用到多條證據時通常會遇到全聯合分佈同樣遇到的規模擴展問題。

● 領域中直接因果關係所帶來的條件獨立性使全聯合分佈可以分解成較小的條件分布。原始貝氏模型假設在給定單一的原因變數後,所有的結果變數的都是條件獨立的;

此模型的規模隨結果個數呈線性增長。

● 一個wumpus 世界的代理人能夠計算世界中未被觀察到的層面的機率,從而優於純粹邏輯代理人所做的決策。條件獨立使得這些計算可追溯。