Naive Bayes Classifier 的原理

以前讀 Bayesian probability 時一直有個疑問，為什麼要這樣繞彎來計算？這疑問在讀 Naive Bayes Classifier 時更大了。

假設輸入為屬性 A1、A2、A3 和類別 C1, C2，為什麼不從 training data 裡直接計算出 P(C1 | A1, A2, A3) ？如下所示：

P(C1 | A1, A2, A3) = P(A1, A2, A3, C1) / P(A1, A2, A3) — (1)
P(A1, A2, A3, C1) = N(A1, A2, A3, C1) / N(U)
P(A1, A2, A3) = N(A1, A2, A3) / N(U)

其中 N(.) 表示計算出現次數，U 是宇集。或是更直接一點，直接算數量：

P(C1 | A1, A2, A3) = N(A1, A2, A3, C1) / N(A1, A2, A3) — (2)

可是 Naive Bayes Classifier 卻採用下面這種繞彎的方式子計算：

P(C1 | A1, A2, A3) = P(A1, A2, A3 | C1) * P(C1) / P(A1, A2, A3) — (3)

顯然 (2) 看來直接易懂，為什麼 Naive Bayes Classifier 要用 (3) 的算法呢？畢竟等式右邊各項，也是用 N(.) / N(U) 組出來的。

今天想了許久，終於想通了！關鍵在於 training data 不見得能完整涵蓋所有可能。比方從來沒出現過 (A1, A2, C1) 或 (A1, A2, C2) ，在這種情況下，無法從 training data 裡直接用計數的方式求出 P(C1 | A1, A2) 和 P(C2 | A1, A2) 。於是疑問轉成：「為何 Naive Bayes Classifier 可以計算沒出現過的組合？」

先從定義來看：

P(C1 | A1, A2) = P(A1, A2 | C1) * P(C1) / P(A1, A2)

由於 P(C1 | A1, A2) 和 P(C2 | A1, A2) 的分母一樣，分母可以忽略不算（事實上也算不出來），所以問題簡化為計算上式分子的值。P(C1) 或 P(C2) 可從 training data 裡算估出，但在沒有 P(A1, A2) 的情況下，難道 P(A1, A2 | C1) 可以估的出來？

答案是：「在 conditional independence 的假設下可以！」

假設 A1, A2 在 C1 發生的情況下為 conditional independence，則可得到如下的結果：

P(A1, A2 | C1) = P(A1 | C1) * P(A2 | C1)

原本要求 A1, A2 在 C1 條件下同時出現的機率，成功地轉換為計算各別在 C1 條件下的機率！於是在 A1, …, Ak 對 Ci 都具有 conditional independence 的假設下，只要 training data 內可估出全部的 P(Aj | Ci)，就能計算各種 Aj 組合的條件機率！

結論

相較於直接在 training data 內算次數猜類別，Naive Bayes Classifier 的特色是用極少的機率函數 [*1] 表示出所有屬性組合的機率。但是前提是 conditional independence 的假設要成立。若 Ai 和 Aj 有關聯性 ( Ai and Aj are correlate ），會算出錯誤的數據，這時可能得用 Bayesian network。

更新 (2009-02-21)

經祖佑 [*2] 說明，在這補充幾點：

• 我誤用 missing value 一詞，文中已改正為「training data 不完備」。
• 修改結論，將 Naive Bayes Classifier 的特色寫得更明確。

備註

1. 若有 k 個屬性和 c 個類別，只要從 training data 裡估出 k * c 個機率函數，就能估計出所有組合（(2^k - 1) * c）的機率。
2. 祖佑回覆的原文如下（從 BBS 複製過來的，排版有點亂）：
   

   一點個人感想

   NBC假設conditional independence的優勢是
   把很大的機率表拆成許多小的機率表相乘，所以減少了機率參數
   因此減少了training data的需求量，或反過來說讓同一筆training data資料意義變大
   而文中所提的”missing value”只是這個優勢下的一個特例而已
   事實上就算完全沒有”missing value”的情況，NBC還是可能有他的優勢存在

   因為自己說要舉例，所以只好舉例
   假設要判斷一部動畫camel喜不喜歡
   觀察的attribute是有沒有蘿莉跟有沒有身材好的女角
   同樣一筆training data [(有蘿莉，沒身材好的女角) => camel喜歡]
   在沒有假設conditional independence的情況下
   就只代表(有，無)這樣的組合camel可能會喜歡
   但是在假設conditional independence的情況下
   代表的是”有蘿莉=>camel可能會喜歡”以及”沒身材好的女角=>camel可能會喜歡”
   所以說同一筆資料的information變大

   但是很明顯的這樣假設的危險就在於也許camel只是不喜歡蘿莉身材好XD
   所以(無蘿莉，無身材好的女角)可能在NBC會被誤判成camel喜歡
   這就是有denpendency的情況下，錯誤假設造成的謬誤
   順帶一提的是我覺得missing value這個詞很怪XD
   因為有另一類問題是在處理某input attribute不存在的情況
   例如training data出現(有蘿莉，”不知道”) => camel喜歡這樣的情況

   前文所說的missing value與其說是missing value
   不如說是training data不足