2015年6月17日 星期三

AI - Ch15 機器學習(3), 樸素貝葉斯分類器 Naive Bayes classifier

 

樸素貝葉斯機率模型簡介
簡單貝氏模型直接假設所有的隨機變數之間具有條件獨立的情況,因此可以直接利用條件機率相乘的方法,計算出聯合機率分布。
$p(X|C) = P(X_1|C)P(X_2|C) ... P(X_d|C)$
其中 $X = [X_1, X_2, ..., X_d]$ 是一個特徵向量,而 $C$ 代表一個特定類別。這個假設看來似乎過強,一般實際世界的資料似乎無法滿足此假設,但由此假設所產生的單純貝氏分類器(naive Bayes classifier)卻是相當有實用性,其辨識效能常常不輸給其它更複雜的辨識器。

貝氏分類器在20世紀60年代初引入到文本信息檢索界中,並仍然是文本分類的一種熱門方法,文本分類是以詞頻為特徵判斷文件所屬類別或其他(如垃圾郵件、合法性、體育或政治等)的問題。通過適當的預處理,它可以與這個領域更先進的方法(如支持向量機)相競爭。

樸素貝葉斯分類器是高度可擴展的,因此需要數量與學習問題中的變量成線性關係的參數。最大似然訓練可以通過評估一個封閉形式的表達式來完成,只需花費線性時間,而不需要其他很多類型的分類器所使用的費時的疊代逼近。




樸素貝葉斯機率模型推導
理論上,機率模型分類器是一個條件機率模型。
$p(C \vert F_1,\dots,F_n)$
獨立的類別變量$C$有若干類別,條件依賴於若干特徵變量 $F_1,F_2,...,F_n$。

但問題在於,如果特徵數量n較大或者每個特徵能取大量值時,基於機率模型列出機率表變得不現實。所以我們修改這個模型使之變得可行。 貝葉斯定理有以下式子:
$p(C \vert F_1,\dots,F_n) = \frac{p(C) \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)}.$
用樸素的語言可以表達為:
$\mbox{posterior} = \frac{\mbox{prior} \times \mbox{likelihood}}{\mbox{evidence}}$

實際中,我們只關心分式中的分子部分,因為分母不依賴於$C$而且特徵$F_i$的值是給定的,於是分母可以認為是一個常數。這樣分子就等價於聯合分布模型。
$p(C \vert F_1, \dots, F_n)$
重複使用鏈式法則,可將該式寫成條件機率的形式,如下所示:
$p(C \vert F_1, \dots, F_n)\,$
$\varpropto p(C) \ p(F_1,\dots,F_n\vert C)$
$\varpropto p(C) \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1)$
$\varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3)$
$\varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ \dots p(F_n\vert C, F_1, F_2, F_3,\dots,F_{n-1}).$

現在「樸素」的條件獨立假設開始發揮作用 : 假設每個特徵$F_i$對於其他特徵$F_j,j\neq i$是條件獨立的。這就意味著
$p(F_i \vert C, F_j) = p(F_i \vert C)\,$

對於$i\ne j$,所以聯合分布模型可以表達為
 $\begin{align}
p(C \vert F_1, \dots, F_n) & \varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots\, \\& \varpropto p(C) \prod_{i=1}^n p(F_i \vert C).\,\end{align}$
這意味著上述假設下,類變量C的條件分布可以表達為:
$p(C \vert F_1,\dots,F_n) = \frac{1}{Z}  p(C) \prod_{i=1}^n p(F_i \vert C)$

其中$Z$(證據因子)是一個只依賴與$F_1,\dots,F_n$等的縮放因子,當特徵變量的值已知時是一個常數。


從機率模型中構造分類器
討論至此為止我們導出了獨立分布特徵模型,也就是樸素貝葉斯機率模型。樸素貝葉斯分類器包括了這種模型和相應的決策規則。一個普通的規則就是選出最有可能的那個:這就是大家熟知的最大後驗機率(MAP)決策準則。相應的分類器便是如下定義的公式:
$\mathrm{classify}(f_1,\dots,f_n) = \underset{c}{\operatorname{argmax}} \ p(C=c) \displaystyle\prod_{i=1}^n p(F_i=f_i\vert C=c).$




[例題1] 樸素貝葉斯分類器
若要判斷新進樣本X「女性、年齣介於31~40之間、上班族、月收入中等者」,會不會辦信用卡。


首先根據這10筆訓練樣本資料求不同分類結果的條件機率


「會辦卡」的機率為0.0111,小於「不會辦卡」的機率0.01875,所以樸素貝氏分類預測新進樣本X不會辦卡。




[例題2] 三個囚犯問題

Question : 三個犯人都住在隔離間,並且都被判處了死刑。法官隨機赦免了其中一個犯人。看守知道誰會被赦免,但不會說。犯人A臉皮厚,讓看守告訴他,B和C誰會被執行死刑。

如果赦免的是B,看守就說C;如果赦免的是C,看守就說B;如果赦免的是A,那麼看守就投硬幣決定說B和C中的一個。看守告訴A,犯人B將會被執行死刑。

犯人A興奮不已,覺得自己生存的幾率從1/3提升到了1/2,因為原來是A,B,C三個人有一個人被赦免,現在是A,C兩個人有一個被赦免。



A將此告訴了C,C同樣興奮不已,他認為:A生存的幾率仍然是1/3,而C卻有了2/3的幾率被赦免。

問題是,他們說的對呢?看守的回答又是如何影響A被釋放的概率呢?


Answer : 首先,根據題意,看守是不會說假話的,因此,B是不可能被釋放的,在知道了看守的回答之後,B被釋放的概率是0。
我們首先定義隨機事件:

  • A:A被釋放。
  • B:看守說B會被處決。
  • C:C被釋放

我們需要知道後驗概率$P(A|B)$,逆向的概率不是很直觀,於是我們用貝葉斯定理。

  • $P(A)$表示A被釋放的先驗概率,等於 1/3。
  • $P(B|A)$表示法官選中了A的前提下看守說B被處決的概率,是1/2。
  • $P(B)$的概率,也就是「看守說 B會被處決」這一事件的概率,這一事件的成立只可能可能來自兩個原因:A被釋放,看守丟硬幣丟到了B;或者是C被釋放,看守說B會被處決。
於是我們得到:$P(B) = P(A) \times P(B|A) + P(C) \times P(B|C)$。其中,$P(B|C)$表示C被釋放的前提下看守說B被處決的概率,是1。

相應的,在知道B被處決的情況下,C被釋放的概率就是$P(C|B)=1-P(A|B)$,因為不是A就是C被釋放。所以在知道B被處決的情況下,C被釋放的幾率是2/3。

計算結束,我們發現C是對的,看守的話並沒有提供給A任何關於他被釋放的信息。當然,如果看守用別的方法來選擇說誰會被處決,那麼「B被處決」這句話可能就和「A被釋放」相關了。

總之,這個故事告訴我們,看似相關的隨機事件不一定能影響彼此發生的概率。換句話說,C認為看守告訴A 「B會被處決」 這件事情和 「A被釋放」 這件事情是獨立的($P(A|B)=P(A)$)。意思是看守沒有告訴A任何他想知道的信息。在這個問題中,反直覺的地方在於「B會被處決」和「A被釋放」居然是無關的。




最大期望演算法 (Expectation-maximization algorithm, EM)
最大期望演算法是一個在已知部分相關變量的情況下,估計未知變量的疊代技術。EM演算法的應用非常廣泛,特別是在人工智慧領域中的分群(Clustering),貝氏網路的學習(Bayesian Network),以及隱馬可夫模型 (Hidden Markov Model)的學習上,都有強大的應用。

EM演算法可以總結成下列公式:
$ h^{t+1} = \arg\max_h \; \sum_z P(Z=z | x, h^t) L(x,Z=z|h^t)$
x表示能夠觀察到的不完整的變量值,用z表示無法觀察到的變量值,這樣 x 和 z 一起組成了完整的數據。

EM的算法流程如下:
  • 初始化分布參數
  • 重複直到收斂
    • E步驟:估計未知參數Z的期望值,給出當前的參數估計。也就是算式 $\sum_z P(Z=z | x, h^t) L(x,Z=z|h^t)$ 意義。
    • M步驟:重新估計分布參數,尋找一個讓條件熵最大化的機率模型h,給出未知變量的期望估計,也就是 $\arg\max_h(...)$ 的步驟。



[用心去感覺] EM算法的感覺
可以有一些比較形象的比喻說法把這個算法講清楚。比如說食堂的大師傅炒了一份菜,要等分成兩份給兩個人吃,顯然沒有必要拿來天平一點一點的精確的去稱分量,最簡單的辦法是先隨意的把菜分到兩個碗中,然後觀察是否一樣多,把比較多的那一份取出一點放到另一個碗中,這個過程一直迭代地執行下去,直到大家看不出兩個碗所容納的菜有什麼分量上的不同為止。

EM算法就是這樣,假設我們估計知道A和B兩個參數,在開始狀態下二者都是未知的,並且知道了A的信息就可以得到B的信息,反過來知道了B也就得到了A。可以考慮首先賦予A某種初值,以此得到B的估計值,然後從B的當前值出發,重新估計A的取值,這個過程一直持續到收斂為止。 





References

交大胡毓志教授人工智慧講義

南台科技大學 - 第五章 資料分類法
http://faculty.stust.edu.tw/~jehuang/DMCourse/ch5-7.html

陳鍾誠的網站 - EM 演算法 (Estimation Maximization)
http://ccckmit.wikidot.com/st:em

Wiki - 最大期望算法
https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E6%9C%9F%E6%9C%9B%E7%AE%97%E6%B3%95

Wiki - 樸素貝葉斯分類器
https://zh.wikipedia.org/wiki/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%86%E7%B1%BB%E5%99%A8

5-5 Naive Bayes Classifiers (單純貝氏分類器)
http://mirlab.org/jang/books/dcpr/prNbc.asp?title=5-5%20Naive%20Bayes%20Classifiers%20(%B3%E6%AF%C2%A8%A9%A4%F3%A4%C0%C3%FE%BE%B9)&language=chinese






技術提供:Blogger.