為了降低估計後驗概率P(c|x)的困難,樸素貝葉斯採用了「屬性條件獨立性假設」。然而,在實際應用中,這樣的假設(所有變量相互獨立)是很難成立的。因此我們需要對該假設進行一定程度的放鬆,比如採用「獨依賴估計」(假設每個屬性在類別之外僅依賴一個其他屬性)策略的半樸素貝葉斯。常用的半樸素貝葉斯有兩種,分別是SPODE和TAN。
但獨依賴估計依然無法準確描述實際數據的屬性間複雜依賴關係,它們的依賴關係往往不是一對的,而可能是一對多、多對一的。
我們可以看到,兩種半樸素貝葉斯方法使用簡單的樹形結構來描述屬性依間依賴關係,那麼我們是否可以構造更複雜也更精確的樹形結構或是網型結構來描述來描述屬性間依賴關係呢?答案是肯定的。
貝葉斯網絡,也叫做「信念網」,是一種經典的概率圖模型。它藉助有向無環圖來刻畫屬性之間的依賴關係,並使用條件概率表(CPT)來描述屬性的聯合概率分布。一個貝葉斯網由結構G和參數Θ,即B=<G,Θ>。其中G是以屬性為結點、以直接依賴關係為邊的有向無環圖;Θ是每個屬性的條件概率表。基於貝葉斯網絡,我們可以求得聯合概率分布,其定義為:
貝葉斯網絡有三種典型的變量間依賴關係,分別為同父結構、V型結構和順序結構。
為了更好的分析貝葉斯網絡變量間的條件獨立性,可以使用有向分離,把有向圖轉換成無向圖:
找出有向圖所有的V型結構,在V型結構的父結點之間加上一條五向邊
將所有有向邊改成無向邊
轉換後的無向圖又叫「道德圖」,在道德圖中,如果x和y能被z分開——即刪除了結點z,x與y將被分割為兩個流通分支——則可以判斷:當z已知時x與y條件獨立。
貝葉斯網絡的學習過程分為結構學習與參數學習。當貝葉斯網絡結構已知時,則只需估計每個結點的條件概率表即可(極大似然估計)。但對於複雜的實際數據,我們往往都不知道其網絡結構。這時候我可以通過「評分搜索」的方法,找出結構最恰當的貝葉斯網絡。
評分搜索常用的評分函數通常都基於資訊理論的「最小描述長度」準則,即以最短編碼長度來描述訓練數據(包括描述網絡和編碼數據)的模型。評分函數可寫為:
其中第一項是計算編碼貝葉斯網B所需的字節數,第二項是計算概率分布PB需要用多少字節數來描述D。
當f(θ)=1時,即每個參數用1位元組描述。此時原式相當於AIC評分函數:
當f(θ)=log(m)/2時,則可以得到BIC評分函數:
當f(θ)=0時,原式退化為負對數函數,最小化過程也變成了極大似然估計。
貝葉斯網絡結構學習的過程是NP難問題,因此常用貪心法或限定網絡結構為樹形結構的方法在有限時間內求得近似解。
貝葉斯網絡訓練好後,我們可以進行「推斷」,即通過「證據變量E」來推測「待查詢變量Q」,即計算後驗概率:
然而「精準推斷」也被證明是個NP難問題,因此現實中常常通過「近似推斷」來在有限時間內求得近似解,吉布斯採樣是常用的近似推斷方法:
實質上,吉布斯採樣是在貝葉斯網所有變量的聯合狀態空間與證據E=e一致的子空間中進行「隨機漫步」。由於每一步只依賴前一步的狀態,這又是一個馬爾科夫鏈。
實戰 - pgmpy在Python中可以用來訓練貝葉斯網絡的包挺多,這裡簡要介紹其中口碑較好的pgmpy包。pgmpy可以供用戶手動創建結構已知的貝葉斯網絡,也可提供啟發式算法訓練結構未知的貝葉斯網絡。
對於日常的數據而言,我們往往需要訓練結構未知的貝葉斯網絡。pgmpy中的HillClimbSearch()便可以解決這個問題。
from time import timeimport pandas as pdimport numpy as npfrom pgmpy.estimators import HillClimbSearch, BicScore
data = pd.DataFrame(np.random.randint(0, 5, size=(5000, 7)), columns=list('ABCDEFG'))data['H'] = data['B'] + data['C']data['I'] = data['D'] + data['E'] * data['F']data['J'] = data['A'] * data['B']time1 = time()est = HillClimbSearch(data, scoring_method=BicScore(data))best_model = est.estimate()time2 = time()time2 - time1隨機創建5000行7列的數據框,並按照算式生成3列新數據。以BIC作為評分函數來訓練貝葉斯網絡。模型在76秒後訓練完畢,相對其他模型耗時較多。
def showBN(model,save=False): '''傳入BayesianModel對象,調用graphviz繪製結構圖,jupyter中可直接顯示''' from graphviz import Digraph node_attr = dict( style='filled', shape='box', align='left', fontsize='12', ranksep='0.1', height='0.2' ) dot = Digraph(node_attr=node_attr, graph_attr=dict(size="12,12")) seen = set() edges=model.edges() for a,b in edges: dot.edge(a,b) if save: dot.view(cleanup=True) return dotshowBN(best_model)通過graphviz繪製出貝葉斯網絡,可以看到模型大體上能夠捕捉到變量的依賴關係。但需要注意的是,模型並不總是能夠如此有效,相對多的時候,訓練得到的模型並不能準確捕捉變量的依賴關係。因此嘗試使用訓練得到的貝葉斯網絡來解釋實際問題中的變量關係,似乎並不是一個明智的選擇。
訓練得到貝葉斯網絡後,可以進行對待查詢變量進行推斷。
import pandas as pdfrom pgmpy.models import BayesianModelfrom pgmpy.estimators import MaximumLikelihoodEstimatordata = pd.DataFrame(data={'A': [0, 0, 1], 'B': [0, 1, 0], 'C': [1, 1, 0]})model = BayesianModel([('A', 'C'), ('B', 'C')])cpd_A = MaximumLikelihoodEstimator(model, data).estimate_cpd('A')print(cpd_A)cpd_C = MaximumLikelihoodEstimator(model, data).estimate_cpd('C')print(cpd_C)評價 - 貝葉斯網絡優點:使用圖的形式來描述模型,模型可解釋性很強。
缺點:訓練網絡結構的時間較長,較難用於高維度的數據。
適合數據:標稱型
參考資料:
[1] 《機器學習》 周志華
[2] http://pgmpy.org/estimators.html