樸素貝葉斯模型

在上節(jié)介紹的GDA方法中，輸入特征x是連續(xù)型隨機(jī)變量〖灯荩現(xiàn)在我們介紹一個(gè)算法用于處理x是離散值的情況。

我們以郵件分類(lèi)為例來(lái)介紹這個(gè)算法，郵件分類(lèi)問(wèn)題是文本分類(lèi)(text classification)問(wèn)題的一個(gè)子集身坐。這里我們只考慮把郵件分為兩類(lèi)：垃圾郵件(spam email)和非垃圾郵件(non-spam email)。

我們把郵件中所有出現(xiàn)的單詞的集合稱(chēng)為詞匯表(vocabulary)落包。首先我們構(gòu)造特征向量x_i部蛇，x_i的長(zhǎng)度等于詞匯表里單詞的個(gè)數(shù)。如果詞匯表中第i個(gè)單詞出現(xiàn)在某封郵件中咐蝇，那么x_i=1涯鲁，否則x_i=0，比如：

上圖表明這封郵件里包含a和buy這兩個(gè)單詞嘹害，但不包含aardvark撮竿，aardwolf，zygmurgy這三個(gè)單詞笔呀。

構(gòu)建完特征向量后幢踏，我們需要對(duì)p(x|y)進(jìn)行建模。假設(shè)詞匯表里有50000個(gè)單詞许师，那么x是50000維的向量且每個(gè)元素在0和1內(nèi)取值房蝉，這樣可能的結(jié)果就有2⁵⁰⁰⁰⁰種，如果用多項(xiàng)式分布建模的話微渠，就會(huì)有2⁵⁰⁰⁰⁰ - 1個(gè)參數(shù)搭幻，這顯然是個(gè)天文數(shù)字。

為了簡(jiǎn)化問(wèn)題逞盆，我們就需要做一些假設(shè)檀蹋。我們假設(shè)給定y的情況下，x_i之間是條件獨(dú)立的云芦，這個(gè)假設(shè)稱(chēng)為樸素貝葉斯假設(shè)(Naive Bayes assumption)俯逾。舉例來(lái)說(shuō)，如果y=1表示垃圾郵件舅逸，buy是第2087個(gè)單詞桌肴，price是第39831個(gè)單詞，那么在已知該郵件是垃圾郵件的情況下琉历，“buy出現(xiàn)在該郵件中”和“price出現(xiàn)在該郵件中”這兩件事是互不相關(guān)的坠七。用形式化的方法表述就是水醋，p(x₂₀₈₇|y)=p(x₂₀₈₇|y, x₃₉₈₃₁)。注意彪置，我們不是說(shuō)x₂₀₈₇和x₃₉₈₃₁是互相獨(dú)立的拄踪，而是說(shuō)在給定y的情況下x₂₀₈₇和x₃₉₈₃₁是條件獨(dú)立的。

因此我們可以作如下推導(dǎo)：

其中第一個(gè)等號(hào)基于條件概率鏈?zhǔn)椒▌t悉稠，第二個(gè)等號(hào)基于樸素貝葉斯假設(shè)宫蛆。需要說(shuō)明的是，盡管樸素貝葉斯假設(shè)是個(gè)比較強(qiáng)的假設(shè)的猛，但在實(shí)際問(wèn)題中表現(xiàn)的效果很好耀盗。

我們的模型由φ_i|y=1 = p(x_i=1|y=1)，φ_i|y=0 = p(x_i=1|y=0)和φ_y = p(y=1)這三個(gè)參數(shù)決定卦尊，其似然函數(shù)為

通過(guò)最大化似然函數(shù)叛拷，可以求得：

上式中的∧表示邏輯上的與(and)。這個(gè)公式可以從直觀上進(jìn)行解釋?zhuān)热绂?sub>i|y=1就是第j個(gè)單詞出現(xiàn)在垃圾郵件中的次數(shù)除以垃圾郵件的總個(gè)數(shù)岂却。

所有參數(shù)確定后忿薇，對(duì)一個(gè)新特征x作預(yù)測(cè)，我們可以計(jì)算出：

根據(jù)p(y=1|x)是否大于0.5來(lái)判斷新郵件是否是垃圾郵件躏哩。

最后署浩，盡管上面我們的x取值只是0或1，但實(shí)際上可以把它擴(kuò)展到多個(gè)離散值的情況扫尺。另外即使x是連續(xù)取值的筋栋，我們可以通過(guò)離散化(discretize)，即按一定的區(qū)間將連續(xù)值映射到離散值正驻，然后應(yīng)用樸素貝葉斯算法弊攘。

比如對(duì)于房?jī)r(jià)預(yù)測(cè)問(wèn)題，我們可以按照上表把住房面積按一定區(qū)間離散化姑曙，如果住房面積是890襟交，那么對(duì)應(yīng)的特征值x_i就是3。一般來(lái)說(shuō)伤靠，如果連續(xù)型隨機(jī)變量不能用多元正態(tài)分布建模(不能使用GDA)捣域，那么將其離散化并采用樸素貝葉斯建模是一個(gè)更好的算法。

拉普拉斯平滑處理

樸素貝葉斯算法對(duì)大多數(shù)問(wèn)題都有很好的表現(xiàn)宴合，但是我們還需要對(duì)其作一些修正使得它在文本分類(lèi)問(wèn)題中表現(xiàn)地更出色焕梅。

假設(shè)NIPS是詞匯表里的第35000個(gè)單詞，但是這個(gè)單詞從未在訓(xùn)練數(shù)據(jù)中出現(xiàn)過(guò)形纺，因此：

所以預(yù)測(cè)一個(gè)包含單詞NIPS的郵件是否為垃圾郵件丘侠，我們計(jì)算得到：

這是由于每一項(xiàng)乘積里都有p(x₃₅₀₀₀|y) = 0徒欣，因此分子分母都為0逐样，這使得我們無(wú)法進(jìn)行計(jì)算。

這個(gè)問(wèn)題從廣義上來(lái)講就是，僅僅因?yàn)橐粋€(gè)事件沒(méi)有在訓(xùn)練集中出現(xiàn)就預(yù)測(cè)它的概率為0不是一個(gè)好主意脂新。對(duì)于φ_i = p(z=i)挪捕，之前根據(jù)最大似然估計(jì)的結(jié)果為：

為了避免某些φ_j等于0，我們可以使用拉普拉斯平滑處理(Laplace smoothing)争便，修正參數(shù)如下：

我們?cè)谠瓍?shù)基礎(chǔ)上级零，分子上加了1，分母上加了k滞乙。注意修正之后奏纪，所有
φ_j之和仍然為1(j從1到k取值)。并且所有的φ_j都不為0斩启，解決了之前的問(wèn)題序调。

將拉普拉斯平滑處理代入到樸素貝葉斯算法，我們得到修正后的參數(shù)：

文本分類(lèi)的事件模型

樸素貝葉斯算法在很多文本分類(lèi)問(wèn)題中都表現(xiàn)地不錯(cuò)兔簇，但還有個(gè)與之相關(guān)的算法表現(xiàn)地更出色发绢。

在文本分類(lèi)的特定領(lǐng)域，樸素貝葉斯算法使用的是多元伯努利事件模型(multi-variate Bernoulli event model)垄琐。在該模型中边酒，我們假設(shè)下一封郵件的發(fā)送方是隨機(jī)的發(fā)送者(可能是垃圾郵件制造者或者是正常發(fā)件人)，然后發(fā)送方遍歷整個(gè)字典狸窘，然后決定是否將單詞i寫(xiě)到郵件中墩朦，每個(gè)單詞i寫(xiě)入的概率p(x_i=1|y) = φ_i|y互相獨(dú)立。因此朦前，這封郵件出現(xiàn)的概率為：

我們?cè)俳榻B另一個(gè)模型介杆，稱(chēng)之為多項(xiàng)式事件模型(multinomial event model)。這個(gè)模型引入了一套不同的符號(hào)和特征韭寸，x_i表示郵件里第i個(gè)單詞的在字典中的位置春哨，x_i在1到|V|中取值，|V|是詞匯表(字典)的大小恩伺。一封由n個(gè)單詞組成的郵件由長(zhǎng)度為n的向量表示(x₁, x₂, ..., x_n)赴背。比如，某封郵件的開(kāi)頭為"A NIPS ..."晶渠，那么x₁=1(a是字典里第1個(gè)單詞)凰荚，x₂=35000(NIPS是字典里第35000個(gè)單詞)。

在多項(xiàng)式事件模型中褒脯，我們?nèi)噪S機(jī)選擇發(fā)送者(和多元伯努利事件模型一樣便瑟，概率是p(y))，然后發(fā)送者根據(jù)多項(xiàng)式分布決定第一個(gè)單詞x₁出來(lái)(概率是p(x₁|y))番川，再以同樣的方式?jīng)Q定后續(xù)的單詞x₂, ..., x_n到涂，直到選出n個(gè)單詞構(gòu)成這封郵件脊框。因此，在該模型下郵件出現(xiàn)的概率為：

注意這個(gè)公式和在多元伯努利事件模型下推導(dǎo)出來(lái)的公式非常類(lèi)似践啄，但實(shí)際上這里的每一項(xiàng)都表示不同的含義浇雹，尤其是x_i|y現(xiàn)在服從多項(xiàng)式分布，而不是伯努利分布屿讽。

該模型的參數(shù)和之前一樣昭灵，它們是 φ_k|y=1 = p(x_j=k|y=1)，φ_k|y=0 = p(x_j=k|y=0)和φ_y = p(y)伐谈。注意對(duì)于任意的j烂完，p(x_j|y)的值都是一樣的，也就是說(shuō)單詞在郵件中出現(xiàn)的位置與概率無(wú)關(guān)诵棵。

給定訓(xùn)練數(shù)據(jù)集(x⁽ⁱ⁾, y⁽ⁱ⁾)窜护，其似然函數(shù)為：

通過(guò)最大化似然函數(shù)，可以求得：

應(yīng)用拉普拉斯平滑非春，我們?cè)诜肿由霞?柱徙，在分母上加|V|，修正后的參數(shù)為：

盡管樸素貝葉斯算法不是最好的分類(lèi)算法奇昙，但它的效果卻是驚人地好护侮。由于它的簡(jiǎn)單和易于實(shí)現(xiàn)的特性，我們通常把它作為首選試驗(yàn)的算法储耐。

總結(jié)

• 在分類(lèi)問(wèn)題中常用的分類(lèi)算法是樸素貝葉斯算法羊初，模型需要滿(mǎn)足樸素貝葉斯假設(shè)，即給定y的情況下什湘，x_i之間是條件獨(dú)立的
• 如果x是連續(xù)型隨機(jī)變量长赞，可以通過(guò)離散化后應(yīng)用樸素貝葉斯算法；對(duì)于某些不能使用GDA建模的模型闽撤，該方法是一個(gè)更好的算法
• 為了解決樸素貝葉斯算法中某些參數(shù)為0導(dǎo)致預(yù)測(cè)失效得哆，可以采用拉普拉斯平滑對(duì)參數(shù)修正
• 文本分類(lèi)的兩種事件模型：多元伯努利事件模型和多項(xiàng)式事件模型，后者通常效果更好

參考資料

• 斯坦福大學(xué)機(jī)器學(xué)習(xí)課CS229講義 pdf
• 網(wǎng)易公開(kāi)課：機(jī)器學(xué)習(xí)課程 雙語(yǔ)字幕視頻 上 下