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