Naive Bayes Classifier 的原理

Naive Bayes Classifier 的原理
February 19th, 2009Goto commentsLeave a comment
以前讀 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 的特色寫得更明確。
備註
若有 k 個屬性和 c 個類別，只要從 training data 裡估出 k * c 個機率函數，就能估計出所有組合（(2^k - 1) * c）的機率。
祖佑回覆的原文如下（從 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不足

歷史上的今天
Hinet光纖，頹廢生活 - 2007
DRY 的缺點以及測試碼的衝突 - 2011
fcamelAll, Computer Science, Machine Learning
Comments (4)Trackbacks (1)Leave a commentTrackback

Mr. Saturday
March 7th, 2009 at 18:30 | #1 Reply | Quote
哈哈, 我ㄧ直想在 blog 上寫這個東西, 沒想到你先寫掉了
其實從很多應用的角度來看 NBC 會更容易了解 Bayes’ Rule 存在的價值
像是 NLP 裡面如何把 language model 套到公式右邊的其中一項等等
推薦你我之前上課用的講義 http://www.stanford.edu/class/cs229/materials.html

fcamel
March 7th, 2009 at 18:45 | #2 Reply | Quote
謝啦, 最近滿需要惡補 ML 相關知識的, 之後要讀 ML 時來看看。總覺得一個方法需要思考許久, 才能體會一些。

Jerry.Chen
March 8th, 2010 at 19:02 | #3 Reply | Quote
講得很深入,…..有學到許多新東西唷
感謝大大

canonfans
March 1st, 2011 at 14:08 | #4 Reply | Quote
說明很清楚，比學校老師教的還簡單易懂!