第四部分：生成學(xué)習(xí)算法
到目前為止，我們主要討論了直接對p(y|x;θ)建模的學(xué)習(xí)算法，即y的條件分布。 例如，對數(shù)幾率回歸將p(y|x;θ)建模為h(x)= g(θ'x)其中g(shù)是Sigmoid函數(shù)。 在本文中，我們將討論一種不同類型的學(xué)習(xí)算法。
考慮一個分類問題，我們希望根據(jù)動物的某些特征來學(xué)習(xí)區(qū)分大象(y = 1)和狗(y = 0)。 給定訓(xùn)練集，像對數(shù)幾率回歸或感知機算法(基本上)的算法試圖找到一條直線 (即決定邊界)將大象和狗分開。 然后，為了將新動物分類為大象或狗，它檢查新動物落入決定邊界的哪一側(cè)，并相應(yīng)地進行預(yù)測。
這是一種不同的方法。 首先，看大象，我們可以建立一個大象看起來像什么的模型。 然后，看著狗，我們可以建立一個單獨的模型，看看狗的樣子。 最后，為了對新動物進行分類，我們可以將新動物與大象模型相匹配，并將其與狗模型相匹配，以查看新動物是否更像大象或更像我們在訓(xùn)練集中看到的狗。
嘗試直接學(xué)習(xí)p(y|x)的算法(例如對數(shù)幾率回歸)，或試圖直接從輸入X的空間到目標(biāo)值{0,1}學(xué)習(xí)映射的算法(例如感知器算法)稱為判別學(xué)習(xí)算法。 在這里，我們將討論試圖對p(x|y) ( p(y) )建模的算法，這些算法稱為生成學(xué)習(xí)算法。 例如，如果y指明是狗(0)還是大象(1)，則p(x|y=0)對狗的特征分布建模, p(x|y = 1)則對大象特征分布建模。
在對p(y) (稱為類先驗)和p(x | y)進行建模之后，我們的算法可以使用貝葉斯公式導(dǎo)出給定x的y后驗分布：
這里，分母由p(x)= p(x | y = 1)p(y = 1)+ p(x | y = 0)p(y = 0)給出。 實際上，如果為了進行預(yù)測而計算p(y|x)，那么我們實際上并不需要計算分母，因為:
高斯判別分析
樸素貝葉斯
在高斯判別分析中，特征向量x是連續(xù)的實值向量。 現(xiàn)在讓我們討論一種不同的學(xué)習(xí)算法，其中xj是離散值的。
請考慮使用機器學(xué)習(xí)構(gòu)建垃圾郵件過濾器。 在這里，我們希望根據(jù)消息是未經(jīng)請求的商業(yè)(垃圾郵件)電子郵件還是非垃圾郵件來對郵件進行分類。在學(xué)會這樣做之后，我們可以讓我們的郵件閱讀器自動過濾掉垃圾郵件，并可能將它們放在一個單獨的郵件文件夾中。 對電子郵件進行分類是文本分類的眾多廣泛問題的其中一個示例。
假設(shè)我們有一個訓(xùn)練集(一組標(biāo)記為垃圾郵件或非垃圾郵件的電子郵件)。 我們將通過指定用于表示電子郵件的特征xj來開始構(gòu)建我們的垃圾郵件過濾器。
我們將通過特征向量表示電子郵件，其長度等于字典中的字?jǐn)?shù)。 具體來說，如果電子郵件包含字典的第j個單詞，那么我們將設(shè)置xj = 1; 否則我們讓xj = 0。例如，矢量：
表示一封郵件包含'a'、'buy'，不包含'aardvark'、'aardwolf'、'zygmurgy'。編碼到特征向量中的單詞集稱為詞匯表，因此x的維度等于詞匯表的大小。
選擇了我們的特征向量后，我們現(xiàn)在想要建立一個生成模型。 所以，我們必須對p(x|y)建模。 但是，如果我們有一個50000字的詞匯，那么x∈{0,1} 50000（x是0和1的50000維向量），如果我們用多項式分布對x建模會有2250000可能的結(jié)果，然后我們最終得到一個(2^250000-1)維參數(shù)向量， 這顯然是太多的參數(shù)。
為了對p(x|y)建模，我們做了一個很強的假設(shè)。我們假設(shè)給定y條件下xi在是獨立的。這個假設(shè)稱為樸素貝葉斯假設(shè)，相應(yīng)的算法稱為樸素貝葉斯分類器。比如，如果y=1表示垃圾郵件；'buy'是第2087 word，'price'是第39831 word；然后假設(shè)我告訴你y=1(特定的電子郵件是垃圾郵件)，然后了解x2087(郵件中是否出現(xiàn)“buy”)將不會影響你對x39831價值的看法(是否出現(xiàn)“price”)。 更正式地說，這可以寫成p(x2087|y)= p(x2087|y,x39831)。(注意，這與說x2087和x39831是獨立的不一樣,這應(yīng)該表示為“p(x2087)= p(x2087 | x39831)”; 相反，我們只是假設(shè)x2087和x39831在給定y條件上是獨立的。)
現(xiàn)在可以得到：
第一個等式僅僅來自概率的通常屬性，第二個等式使用獨立性假設(shè)。 我們注意到，即使Naive Bayes假設(shè)是一個非常強的假設(shè)，所得到的算法在許多問題上也能很好地工作。
我們的模型通過[φj| y=1] = p(xj=1|y=1)，[φj|y=0] = p(xj = 1|y = 0)，并且φy= p(y = 1)來參數(shù)化。 像往常一樣，給定訓(xùn)練集{(x(i)，y(i)); i= 1,...,m}，我們可以寫下數(shù)據(jù)的聯(lián)合似然：
最大化這個給出最大似然估計：
參數(shù)具有非常自然的解釋。 例如，φj|y = 1只是單詞j出現(xiàn)的垃圾郵件(y = 1)中的一部分。
在擬合了所有這些參數(shù)之后，為了對具有x特征的新示例進行預(yù)測，我們就可以簡單地進行計算：
并選擇具有較高后驗概率的類別。
最后，我們注意到雖然我們已經(jīng)開發(fā)了樸素貝葉斯算法，主要是針對特征xj是二元值的問題的情況，但是對于xj可以取值{1,2,...,kj}很簡單。在這里，我們只是將p(xj | y)建模為多項式而不是伯努利。實際上，即使一些原始輸入屬性(例如，房屋的生活區(qū)域，如我們之前的例子中)是連續(xù)值的，將它離散化是很常見的 - 也就是說，將它變成一組離散值然后應(yīng)用樸素貝葉斯。比如，如果我們使用xj表示居住面積，我們可能類似下面的方式離散化居住面積：
因此，對于居住面積為890平方英尺的房屋，我們將相應(yīng)特征xj的值設(shè)置為3。然后我們可以應(yīng)用樸素貝葉斯算法，并使用多項分布模型p(xj | y)，如前所述。當(dāng)原始的連續(xù)值屬性沒有通過多元正態(tài)分布很好地建模時，對特征進行離散化并使用樸素貝葉斯(而不是GDA)通常會產(chǎn)生更好的分類器。
拉普拉斯平滑
正如我們所描述的，樸素貝葉斯算法對于許多問題將工作得相當(dāng)好，但是有一個簡單的改變使它工作得更好，特別是對于文本分類。讓我們簡要地討論一下算法當(dāng)前形式的一個問題，然后討論如何修復(fù)它。
考慮垃圾郵件/電子郵件分類，假設(shè)在完成CS229并在項目上做了出色的工作后，你決定在2003年6月左右向NIPS會議提交你所做的工作以供發(fā)布。因為你最后在電子郵件中討論了這個會議，所以你也開始收到帶有“nips”這個詞的信息。但是這是你的第一篇NIPS論文，直到現(xiàn)在，你還沒有看到任何包含“nips”這個詞的電子郵件；尤其是“nips”從來沒有出現(xiàn)在你的垃圾郵件/非垃圾郵件的訓(xùn)練集中。假定“nips”是字典中的第35000個單詞，你的樸素貝葉斯垃圾郵件過濾器因此選擇了參數(shù)φ35000|y的最大似然估計:
因為它從來沒有在垃圾郵件或非垃圾郵件的訓(xùn)練示例中看到過“nips”，所以它認(rèn)為在兩種類型的電子郵件中看到它的概率為零。因此，當(dāng)試圖確定這些包含“nips”的消息之一是否是垃圾郵件時，計算類后驗概率，并獲得：
因為p(x35000|y) = 0，所以我們算法獲得了0/0，對于這種情況不知道該如何預(yù)測。
更廣泛地陳述這個問題，從統(tǒng)計學(xué)上講，僅僅因為你之前在有限的訓(xùn)練集中沒有見過它，所以在統(tǒng)計學(xué)上估計某個事件的概率為零是個壞主意?？紤]估計多項式隨機變量z的平均值的問題，變量z取{1,...,k}。我們可以用φj= p(z = j)參數(shù)化我們的多項式。 給定一組m獨立觀察{z(1),...,z(m)}，最大似然估計由下面得出：
正如我們之前看到的，如果我們使用這些最大似然估計，那么某些φj可能最終為零，這是一個問題。 為了避免這種情況，我們可以使用拉普拉斯平滑，如下所示：
注意，φj(j=1,...,m)和為1仍然成立，這是一個理想的屬性，因為φj是對我們知道必須總和為1的概率的估計。此外，對于j的所有值，φj不等于0，解決了我們的概率被估計為零的問題。 在某些條件下，可以證明拉普拉斯平滑實際上給出了φj的最優(yōu)估計。
返回我們的樸素貝葉斯分類器，使用拉普拉斯平滑，我們因此獲得以下參數(shù)估計：
