第20章用貝葉斯網學習和動作

第三部分知識的表示和推理第20章用貝葉斯網學習和動作學習貝葉斯網

學習一個貝葉斯網的問題是尋找一個網絡——它能最好地匹配(按照某個記分度量)一個數據訓練集(trainingset)Ξ，Ξ是所有(至少有一些)變量值的實例集合。說“尋找一個網”，

我們的意思是既要找到DAG結構，也要找到與DAG中每個節(jié)點相關的條件概率表(CPT)。

學習貝葉斯網

已知網絡結構

如果知道網絡的結構，那么只需找到CPT，我們首先描述這種情況。通常，人類專家能對一個問題領域提出適當的結構但不能做出CPT。在我們必須學習網絡結構的情況下，學習CPT仍是必需的。學習CPT有一個比較容易的和一個比較難的兩種情況。在容易的情況下，沒有缺失的數據，即訓練集合己的每個成員對網中表達的每個變量有一個值。然而在更實際的設置中，情況常常是一些訓練記錄的變量值缺失了；缺失的數據導致更難以學習CPT。

學習貝葉斯網

無缺失數據

已知網絡結構

我們用向量變量Pi指稱與Vi的雙親有關的變量，用向量值Pi指稱這些變量的值。采樣統(tǒng)計結果，由Ξ中有Vi=vi和Pi=pi的采樣數除以有Pi=pi的采樣數得到。

假如我們觀察了圖中G、M、B和L的100組值(注意到有些組合沒有出現，有些比其他出現得更頻繁)。為了計算采樣概率，我們只要計算在所有的采樣中B為True出現的次數，得到同樣，。對節(jié)點B和L，這些概率正是它們的CPT所需要的。

學習貝葉斯網

已知網絡結構

無缺失數據

我們用下面解釋的典型計算方式計算節(jié)點M的CPT行：為了計算(簡寫為)，計算M為True、B為True，L為False的次數，并除以B為True、L為False的次數。我們得到。對節(jié)點G我們進行相似的計算?？梢杂嬎阏麄€采樣統(tǒng)計結果集。注意，在例子中，有些采樣統(tǒng)計是基于很小的采樣的——導致相應的基礎概率的可能不精確評估。一般地講，一個CPT的指數級數量的大量參數可能無法使訓練集對這些參數產生良好評估的能力。如果很多參數有相同(或接近相同)的值，可能會減輕這個問題。

學習貝葉斯網

缺失數據

已知網絡結構

在收集被一個學習過程使用的訓練數據中，常常發(fā)生數據缺失。有時，要被捕獲的數據不經意地缺失了，有時數據缺失本身是重要的。這里處理第一種情況。一個簡單、收斂的迭代計算采樣統(tǒng)計過程已被證明是對之有效的。用剛剛描述的例子來介紹該方法的主要思想。

星號*表示變量值組中與那個位置相關的變量值缺失了。問題是當試圖評估這個網絡的CPT時，我們如何處理這些缺失值?

學習貝葉斯網

已知網絡結構

缺失數據

先考慮三次采樣，其中G＝False，M＝True，L＝True，B的值缺失的情況。這二次采樣中的每一次可能有B＝True或B＝False，我們不知道是哪一個。但對這些采樣，我們知道G、M和L的值。因此，雖然不知道B的值，但給定了G、M和L的值，我們能計算B的概率p(B|﹁G，M，L)。

這個概率能用前面講述的概率推理方法計算——工作在網絡結構和網絡的CPT上，條件是我們有這些CPT(當然，我們還沒有它們，但是將簡要討論這個問題)。因此，為了計算采樣統(tǒng)計以估計該網絡的CPT，三次采樣中的每一次能用兩個加權采樣代替——一個是B＝True，用p(B|﹁G，M，L)加權，另一個是B＝False，權值為p(﹁B|﹁G，M，L)=1-p(B|﹁G，M，L)。學習貝葉斯網

已知網絡結構

缺失數據

我們把相同的過程應用到7次采樣B＝True，L＝True，G和M的值缺失的情形。這些采樣中的每一個可由對應組合(G，M)、(G，﹁M)、(﹁G，M)和(﹁G，﹁M)的4個加權采樣代替，權值分別是概率p(G,M|B,L),p(G,﹁M|B,L)、p(﹁G,M|B,L)，和p(﹁G,﹁M|B,L)。我們可以再次用網絡結構和CPT計算這些概率(當在任何一個采樣中的缺失值數量很大時，存在指數爆炸的采樣危險)。學習貝葉斯網

已知網絡結構

缺失數據

現在，我們能用加權采樣(其中，缺失值已被填充——用所有可能的方法)和其他采樣(它們中沒有缺失值)一起進行頻率統(tǒng)計以計算CPT的估計。這個過程與在沒有缺失值中描述的過程相同，除了一些計數現在不是整個數量(因為加權)外。但是正如前面提到的，為了通過概率推理計算權值，我們需要CPT，然而我們沒有它。一個叫期望最大化(EM)的方法可以用來對一個CPT集合調零。首先，我們?yōu)檎麄€網絡的CPT中的參數選擇隨機值，用這些隨機值計算需要的權值(給定觀察要數據的值時缺失數據值的條件概率)，然后用這些權值反過來估計新的CPT。我們迭代這個過程，直到CPT收斂，保證收斂能達到。在大部應用中，收斂是快速的。學習貝葉斯網

學習網絡結構

記分制

有幾個度量方法可用來對網絡打分。一種方法是基于描述長度的。它的思想是：假如我們想發(fā)送訓練集Ξ給某個人，為此，把變量值編碼成一個位串，然后發(fā)送位。我們需要多少位呢?即，消息的長度是多少?有效的編碼利用要發(fā)送數據的統(tǒng)計屬性，這些統(tǒng)計屬性正是我們企圖在貝葉斯網中建模的。如果找到一個適當的貝葉斯網，我們能基于它使用哈夫曼編碼對要傳輸的數據編碼。學習貝葉斯網

根據信息理論，一組數據Ξ，按照一個給定貝葉斯網B的組合概率分布，其最好編碼需要L(Ξ，B)比特，L(Ξ,B)＝-log[Ξ]其中p[Ξ]是被發(fā)送的特殊數據的概率(按照B規(guī)定的聯(lián)合概率)。給定一些特殊數據已Ξ，我們企圖找到網絡B，它使L(Ξ，B)最小化。在了解這個方法之前，我們先計算logp[Ξ]。假定數據Ξ包含m個采樣值：v1，…，vm，每個vi是n個變量值的一個n維向量，p(Ξ)是聯(lián)合概率p[v1，…，vm]。假定每個數據按照B指定的概率分布被獨立提供，我們有

和

其中每個p(vi)(由vi指稱變量值的聯(lián)合概率)從貝葉斯網B計算。學習網絡結構

記分制

但是單獨的L(Ξ，B)不是一個非常好的度量，因為它的使用促成了有很多弧的大網絡。這樣一個網絡對Ξ過于特殊化，即它過于適合數據。對記分度量的適當調整能這樣實現；為了用一個基于B的有效編碼把Ξ傳送給某個人，我們也必須傳遞B的描述以便接收者能夠對消息解碼。這樣，我們必須加一項到L(Ξ，B)，這個項是傳輸B需要的消息長度。粗略地講，傳送B要求的比特數是，其中|B|是B中的參數個數，一般被認為是適合表示每個數字參數的比特數。因此調整后的記分制L(Ξ，B)為，

現在，我們搜索一個給出數據和網絡編碼的最小描述長度的網絡。使用兩個因子允許我們對發(fā)送數據和網絡做出更好的權衡。

記分制

學習網絡結構

學習貝葉斯網

學習貝葉斯網

學習網絡結構

記分制

例:對下左圖中顯示的網絡和下右圖中所示的發(fā)送數據，我們計算L′(Ξ，B)。首先，我們計算L(Ξ，B)，即發(fā)送下右圖中的數據要求的比特數——假定數據由下左圖中的貝葉斯網給定的一個概率分布提供。

學習貝葉斯網

學習網絡結構

記分制

P(第1項)=p(G|B)p(M|B，L)p(B)p(L)＝0.95×0.9×0.95×0.7＝0.569采用負對數(對以2為底的)，產生-logp(第1項)＝0.814在數據中有54個這種“第1項”，因此54個第1項對L(Ξ，B)的作用結果是54×0.814＝43．9。表中其他項的總結果分別是6.16、27.9、52.92、16.33、12.32、24.83和12.32。把這些結果加起來得到：L(Ξ,B)＝196.68bit

下圖中表的第1項的概率是

學習貝葉斯網

學習網絡結構

記分制

下面，我們計算，發(fā)送圖的網絡需要的位數。在這個網中有8個參數。因此＝4×6.64＝26.58bit因此這個網絡的記分度量是L′(Ξ,B)＝19.68十26.58＝223.26bit其他的網絡可用同樣的方式評估。學習貝葉斯網

學習網絡結構

搜索網絡空間

當然，所有可能的貝葉斯網集合是如此之大，以致我們不可能企求一種詳盡的搜索以發(fā)現一個位L′(Ξ,B)最小的網絡。一種可能是利用下山搜索或“貪婪”搜索。即我們從一個給定的網絡開始(比如一個沒有弧的網絡，假定它獨立于所有的變量)，估計該網絡的L′(Ξ,B)，然后對它做一些小改變，來看這些改變產生的網絡是否減少了L′(Ξ,B)。這些小改變可以是加一條弧，或減一條弧，或者掉轉一條弧的方向。每發(fā)生一個改變，我們用從Ξ中導出的采樣統(tǒng)計計算改變網絡的CPT。然后這些CPT被用來計算L′(Ξ,B)的部分。新網絡中的參數數量用來計算部分（|B|logm)/2。這些計算可以簡化，由于描述長度計算可分解成網絡中每個CPT上的計算。當記分度量可分解時，總度量是局部度量的和。因此，當一個弧被加、被減或被反向時，我們只需計算在采樣統(tǒng)計中的變化和改變涉及到的節(jié)點V的p(Vi|p(Vi))，其他的p(Vi|p(Vi))保持不變。

學習貝葉斯網

學習網絡結構

搜索網絡空間

學習貝葉斯網

學習網絡結構

搜索網絡空間

有時，網絡結構可以通過增加節(jié)點而大大地簡化。這些節(jié)點所代表的變量值沒有在訓練集Ξ中給定。這些節(jié)點叫做隱藏節(jié)點。作為一個簡單的例子，考慮下圖中所示的兩個貝葉斯網。左邊的網絡比右邊有隱藏節(jié)點H的網絡有更多的參數；如果右邊的網和它一樣好或更好(如果它是變量因果關系的更好表示)，那么它的描述長度分數將會更糟。由于我們不能度量隱藏變量，必須用搜索過程虛構它的存在。因此，貪婪搜索必須向它的可能改變的列表中添加一個新節(jié)點。相應的變量值當然是“缺失數據”，和這個變量相關的概率必須通過前面描述的EM方法引證。

概率推理與動作

一般設置

合理化的說法：即使采用的動作并不總會有它的預期效果，傳感器有時會出錯，但傳感器(平均地)將使agent通過狀態(tài)空間知道它的進展，并且重復計劃將再次引導agent朝著需要的目標(或獎賞)前進。

現在，有工具允許我們更適當地處理不確定性，就能明確地采用更現實的假設。新的agent不知道它在哪個狀態(tài)，它僅僅知道它在各種狀態(tài)的概率。agent的傳感器不能給出環(huán)境狀態(tài)的確切知識，它最多只能加深這些狀態(tài)的概率。動作結果僅僅被大概地了解：在一個給定狀態(tài)下采取的動作可能導致一組新狀態(tài)中的任何一個——每一個都有相應的概率。通過計劃和感知，我們想讓agent選擇使它的預期應用最大化的那個動作。一個agent能在它的完全一般化中處理這個問題需要的計算量非常大，并需要再一次近似和進一步的限制假設。

概率推理與動作

一個擴展的例子

考慮處于上圖所示的一個機器人，我們用一個狀態(tài)變量E表示它，E有5個可能值{-2，-1，0，1，2}，每個位置對機器人有一個應用U。為了開始過程，我們假定機器人(精確地)知道當t＝0時，它在標志為0的單元中，即E0＝0。機器人在第i個時間步驟采取的動作用符號Ai指稱。它試圖向左移一個單元(Ai＝L)或向右移一個單元(Ai＝R)。無論哪種情況，一個移動有預期結果的概率為0.5；每個動作沒有任何結果的概率是0.25，一個動作使機器人以與預期相反的方向移動到相鄰單元的概率為0.25。因此，在幾次移動后，機器人只有它實際位置的概率知識。

概率推理與動作

一個擴展的例子

機器人在第i個時間步驟通過一個感知信號Si感知它的位置。但是我們假定那個傳感器有點不可靠。假如Ei有確定值，Si有同樣值的概率是0.9。Si有每個其他值的概率是0.025。面對各種障礙，機器人的問題是做出使它的應用的期望值提前幾步最大化的移動。如果我們使預期的應用僅提前一步最大化，用來選擇機器人的下一步動作的決策技術最容易解釋。假定當t＝0時機器人企圖向右移動，即A0＝R。所得到的環(huán)境狀態(tài)由E1給出。為了繼續(xù)感知／計劃／動作循環(huán)，機器人通過觀察S1＝1感知它的位置。它下一步采取什么移動呢?確實，在做了那個移動后，它如何基于感知數據、對當前狀態(tài)所做推理和動作和效果來?概率推理與動作

一個擴展的例子

使用一個叫做動態(tài)決策網的特殊信念網的概率推理，來選擇最大化應用動作。在下圖中顯示了適合這個問題的網絡。這個網絡允許機器人在采用動作時和新感知的信息變得可用時迭代地進行推理，給定E0=0、A0＝R和S0＝l后，我們能用普通的概率推理計算期望的應用值U2，它先由A1＝R產生，再由A1＝L產生。然后機器人選擇給出更大值的動作(這種情況下的動作選擇基于機器人僅向前看一步。進一步的向前看將涉及到對可選動作序列計算更遠的應用)。在動態(tài)決策網中使用不同形狀的節(jié)點表示這些節(jié)點的不同假設。方形節(jié)點表示變量的值仍在agent的完全控制之下，它們被稱為決策點。在一個動態(tài)決策網中，在agent已經做了決策之后，它們成為(有已知值)普通信念網節(jié)點。棱形節(jié)點表示應用值的變量。應用變量的期望值是它們雙親的各種值的概率函數概率推理與動作

一個擴展的例子

首先，給定時刻t＝0時已知的東西，和假定A1的兩個不同概率，我們需要計算兩個預期應用：

和

為了計算這兩個預期值，對A1的兩個值中的每一個的E2的不同值，我們要計算p（E2|E0=0，A0=R，S1=1，A1）。這些計算形式在后面的步驟中將被重復，但為了具體，在此問題的步驟中都寫出它。這個形式對A1的每個值也是相同的，因此僅寫出A1=R的情形。我們用上一章解釋的polytree算法計算p（E2|E0=0，A0=R，S1=1，A1=R）。概率推理與動作

一個擴展的例子

首先，我們“包含沒有給定的雙親”，得到：p（E2|E0=0，A0=R，S1=1，A1=R）=p（E2|E0=0，A0=R，S1=1，A1=R，E1）p（E1|E0=0，A0=R，S1=1，A1=R）考慮條件獨立性，這個等式能被簡化：p（E2|E0=0，A0=R，S1=1，A1=R）=p（E2|A1=R，E1）p（E1|E0=0，A0=R，S1=1）在用于機器人動作選擇的決策網中，上述求和的第一項叫做馬爾可夫過程的動作模型。對一個給定的前一個狀態(tài)和動作，它給出各種可能的隨后狀態(tài)的概率。

概率推理與動作

一個擴展的例子

根據Polytree算法，求和中的第二項用貝葉斯法則重寫為：p（E2|E0=0，A0=R，S1=1）=kp（S1=1|E0=0，A0=R，E1）p（E1|E0=0，A0=R）其中k是一個標準化因子，它被選擇(后面)以使概率和為1。再使用條件獨立，我們有p（E2|E0=0，A0=R，S1=1）=kp（S1=1|E1）p（E1|E0=0，A0=R）上述結果中的第1項叫感知模型。對很多環(huán)境狀態(tài)，它給出了傳感器將有各種值的概率(對每個環(huán)境狀態(tài)，一個完全可靠和提供最多信息的傳感器，將把所有的概率集中到一個傳感器值)。第2項又是一個動作模型。匯集我們的結果，產生：p（E2|E0=0，A0=R，S1=1，A1=R）=kp（E2|A1=R，E1）p(S1=1|E1)p（E1|E0=0，A0=R）概率推理與動作

一個擴展的例子

為了評估這個表達式(為E2的各種值)，使用我們已經做出的關于動作結果和傳感器可信度的概率假設。為了說明，我們僅計算p（E2=1|E0=0，A0=R，S1=1，A1=R）。計算涉及到下面的概率，它們是圖20-5中網絡的CPT條目(我們必須對所有的E1值求和)。p（E2=1|A1=R，E1=0）=0.5p（E2=1|A1=R，E1=1）=0.25p（E2=1|A1=R，E1=2）=0.25p（E2=1|A1=R，E1=-1）=0.5和p（E2=1|A1=R，E1=-2）=0.5都等于0。p（S1=1|E1=-2）=0.025p（S1=1|E1=-1）=0.025p（S1=1|E1=0）=0.025p（S1=1|E1=1）=0.025p（S1=1|E1=2）=0.025p（E1=-1|E0=0，A0=R）=0.25p（E1=0|E0=0，A0=R）=0.25p（E1=1|E0=0，A0=R）=0.25p（E1=-2|E0=0，A0=R）和p（E1=2|E0=0，A0=R）都等于0。概率推理與動作

一個擴展的例子

執(zhí)行求和產生p（E2=1|E0=0，A0=R，S1=1，A1=R）＝k×[(0.5×0.025×0.25)十(0.25×0.9×0.5)]＝k×0.1437；我們對E2的其他值執(zhí)行類似的計算以得到p（E2|E0=0，A0=R，S1=1，A1=R）。由于所有這些的和為1，我們能求出k。用E2的這些概率，

給定A1＝R，我們計算比的預期值。重復這個過程來計算給定A1＝L的U2的預期值，并選擇產生更大值的動作(從問題的結構我們知道它將是A1＝R。但是，用這個例子僅僅說明這個方法——沒有什么驚奇的)。

概率推理與動作

一般化舉例

分析方程p（E2|E0=0，A0=R，S1=1，A1=R），允許我們把它擴展到隨后的時間步。這個方程在t＝1時被估計，就像S1＝1已被感知和動作A1＝R被采取前一樣。其他“給定”的值成為過去。因此，我們能改寫為p(E2＜valuesbeforet＝1＞，S1=1，A1=R)。同樣，在求和中的表達式p（E2|E0=0，A0=RR）能被寫為p(E1|<valuesbeforet=1>)。用這些改變，我們有：p(E2＜valuesbeforet＝1＞，S1=1，A1)＝kp(E2|A1，E1)p(S1=1|E1)p(E1|<valuesbeforet=1>)將等式一般化為：p(Ei+1＜valuesbeforet＝i＞，Si=si，Ai)＝kp(Ei+1|Ai，Ei)p(Si=si|Ei)p(Ei|<valuesbeforet=i>)概率推理與動作

一般化舉例

為了決定動作，當我們處理時，用下面的方式使用這個等式。為了計算在t＝i時要采取的動作A．：1)從上一個時間步(i-1)(以及感知到