貝氏網路

貝氏網路的性質。舉例而言，貝氏網路可用來表示疾病和其相關症狀間的機率關係；倘若已知某種症狀下，貝氏網路就可用來計算各種可能罹患疾病之發生機率。一般而言，貝氏網路的有向無環圖中的節點表示隨機變數，它們可以是可觀察到的變數，抑或是潛在變數、未知引數等。連線兩個節點的箭頭代表此兩個隨機變數是具有因果關係或是非條件獨立的；而兩個節點間若沒有箭頭相互連線一起的情況就稱其隨機變數彼此間為條件獨立。若兩個節點間以一個單箭頭連線在一起，表示其中一個節點是「因」，兩節點就會產生一個條件機率值。比方說，我們以formula_2表示第i個節點，而formula_2的「因」以formula_4表示，formula_2的「果」以formula_6表示；圖一就是一種典型的貝氏網路結構圖，依照先前的定義，我們就可以輕易的從圖一可以得知：formula_7，以及formula_8大部分的情況下，貝氏網路適用在節點的性質是屬於離散型的情況下，且依照formula_9此條件機率寫出，此條件機率表的每一列;zh-tw:列;zh-hans:行;zh-cn:行的機率總和必為1。寫出條件機率表後就很容易將事情給條理化，且輕易地得知此貝氏網路結構圖中各節點間之因果關係；但是條件機率表也有其缺點：若是節點formula_2是由很多的「因」所造成的「果」，如此條件機率表就會變得在計算上既複雜又使用不便。下圖為圖一貝氏網路中某部分結構圖之條件機率表。數學定義.令 "G" = ("I","E") 表示一個有向無環圖，其中 "I" 代表圖中所有的節點的集合，而 "E" 代表有向連線線段的集合，且令 "X" = ("X""i")"i"∈"I" 為其有向無環圖中的某一節點 "i" 所代表之隨機變數，若節點 "X" 的聯合機率分配可以表示成：formula_13則稱 X 為相對於一有向無環圖 G 的貝氏網路，其中formula_14表示節點 i 之「因」。對任意的隨機變數，其聯合分配可由各自的區域性條件機率分配相乘而得出：formula_15依照上式，我們可以將一貝氏網路的聯合機率分配寫成：formula_16（對每個相對於Xi的「因」變數 Xj 而言)上面兩個表示式之差別在於條件機率的部分，在貝氏網路中，若已知其「因」變數下，某些節點會與其「因」變數條件獨立，只有與「因」變數有關的節點才會有條件機率的存在。如果聯合分配的相依數目很稀少時，使用貝氏函式的方法可以節省相當大的記憶體容量。舉例而言，若想將10個變數其值皆為0或1儲存成一條件機率表型式，一個直觀的想法可知我們總共必須要計算formula_17個值；但若這10個變數中無任何變數之相關「因」變數是超過三個以上的話，則貝氏網路的條件機率表最多隻需計算formula_18個值即可。另一個貝式網路優點在於：對人類而言，它更能輕易地得知各變數間是否條件獨立或相依與其區域性分配的型態來求得所有隨機變數之聯合分配。馬可夫毯.定義一個節點之馬可夫毯為此節點的因節點、果節點與果節點的因節點所成之集合。一旦給定其馬可夫毯的值後，若網路內之任一節點"X"皆會與其他的節點條件獨立的話，就稱"X"為相對於一有向無環圖"G"的貝氏網路。舉例說明.假設有兩個伺服器formula_19，會傳送封包到使用者端。則此貝氏網路之聯合機率分配可以表示成：formula_20此模型亦可回答如：「假設已知使用者端成功接受到封包，求第一伺服器成功傳送封包的機率?」諸如此類的問題，而此型別問題皆可用條件機率的方法來算出其所求之發生機率：formula_21formula_22formula_23formula_24。求解方法.以上例子是一個很簡單的貝氏網路模型，但是如果當模型很複雜時，這時使用列舉式的方法來求解機率就會變得非常複雜且難以計算，因此必須使用其他的替代方法。一般來說，貝氏機率有以下幾種求法：隨機推論.在此，以馬可夫鏈蒙地卡羅演演算法為例，又馬可夫鏈蒙地卡羅演演算法的型別很多，故在這裡只說明其中一種吉布斯取樣的操作步驟：首先將已給定數值的變數固定，然後將未給定數值的其他變數隨意給定一個初始值，接著進入以下迭代步驟：隨意挑選其中一個未給定數值的變數從條件分配formula_25抽樣出新的formula_2的值，接著重新計算formula_27當迭代結束後，刪除前面若干筆尚未穩定的數值，就可以求出的近似條件機率分配。馬可夫鏈蒙地卡羅演演算法的優點是在計算很大的網路時效率很好，但缺點是所抽取出的樣本並不具獨立性。當貝氏網路上的結構跟引數皆已知時，我們可以透過以上方法來求得特定情況的機率，不過，如果當網路的結構或引數未知時，我們必須藉由所觀測到的資料去推估網路的結構或引數，一般而言，推估網路的結構會比推估節點上的引數來的困難。依照對貝氏網路結構的瞭解和觀測值的完整與否，我們可以分成下列四種情形：以下就結構已知的部分，作進一步的說明。1.結構已知，觀測值完整：.此時我們可以用最大概似估計法來求得引數。其對數概似函式為formula_28其中formula_29代表formula_2的因變數，formula_31代表第formula_32個觀測值，"N"代表觀測值資料的總數。以圖二當例子，我們可以求出節點"U"的最大概似估計式為formula_33由上式就可以藉由觀測值來估計出節點"U"的條件分配。如果當模型很複雜時，這時可能就要利用數值分析或其它最佳化技巧來求出引數。2.結構已知，觀測值不完整：.如果有些節點觀測不到的話，可以使用EM演演算法來決定出引數的區域最佳概似估計式。而EM演演算法的主要精神在於如果所有節點的值都已知下，在M階段就會很簡單，如同最大概似估計法。而EM演演算法的步驟如下：：formula_34其中formula_35代表在目前的估計引數下，事件x的條件機率期望值為formula_36，直到引數收斂為止，即可得到最佳的引數估計值。補充例子.讓我們考慮一個應用在醫藥上的機率推論例子，在此病人會被診斷出是否有呼吸困難的症狀。表一代表一個我們所觀測到的資料集合，包含10筆觀測值，"S"代表的是吸菸與否的症狀。『1』和『0』分別代表『是』和『否』。此醫藥網路結構顯示於圖三。表二代表的是整個網路的經驗聯合機率分配，是由所收集到的資料所建構而成，利用此表可建構出節點的聯合機率分配。見圖四。此貝氏公式formula_37可利用節點的邊際機率和聯合機率去計算節點的條件機率，待會會應用在建立條件機率表格上。見圖五。貝氏網路的聯合機率可由下列式子計算：formula_38其值見表三。使用整個網路經驗聯合機率分配所計算出來的值會與使用CPT所計算出來的值不同，其差異可由表二和表三得知。其中差異不只是值的不同，也出現了新事件的機率。建立在觀測資料上的機率推論演演算法：1.資料集合formula_39，其中formula_40，且一共有n個觀測值。每一個觀測值包含formula_41個變數formula_42，第j個變數有formula_43狀態。2.此貝氏網路的結構G代表N個前代節點集合formula_44，也就是對第j個節點，formula_45為其親代節點的集合, j=1,2,…,N3.範例點formula_46為節點在已知狀態，即在此狀態的機率為1。如果範例點為空集合，將使用古典機率推論使用表一的觀測值和圖一的貝氏網路結構，並且已知範例點為formula_47，也就是病人為非吸菸者和罹癌者：formula_48問題：1.病人患有支氣管炎的機率formula_492.病人會有呼吸困難的機率formula_50解答：1. formula_51formula_52故為0.22. formula_53formula_54formula_55formula_56formula_57formula_58formula_59formula_60應用.貝氏網路目前應用在類比計算生物學與生物資訊學、蛋白質結構、基因表達分析、醫學、文件分類、資訊檢索、決策支援系統、工程學、、影象處理等。