斯坦福大學(xué)機(jī)器學(xué)習(xí)課程個(gè)人筆記完整版

《斯坦福大學(xué)機(jī)器學(xué)習(xí)課程個(gè)人筆記完整版》由會員分享，可在線閱讀，更多相關(guān)《斯坦福大學(xué)機(jī)器學(xué)習(xí)課程個(gè)人筆記完整版（157頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

CS 229 機(jī)器學(xué)習(xí) (個(gè)人筆記) 目錄 (1)線性回歸、logistic回歸和一般回歸 1 (2)判別模型、生成模型與樸素貝葉斯方法 10 (3)支持向量機(jī)SVM（上） 20 (4)支持向量機(jī)SVM（下） 32 (5)規(guī)則化和模型選擇 45 (6)K-means聚類算法 50 (7)混合高斯模型和EM算法 53 (8)EM算法 55 (9)在線學(xué)習(xí) 62 (10)主成分分析 65 (11)獨(dú)立成分分析 80 (12)線性判別分析 91 (13)因子分析 103 (14)增強(qiáng)學(xué)習(xí) 114 (15)典型關(guān)聯(lián)分析 120 (16)偏最小二乘法回歸 129 這里面的內(nèi)容是我在2011年上半年學(xué)習(xí)斯坦福大學(xué)《機(jī)器學(xué)習(xí)》課程的個(gè)人學(xué)習(xí)筆記，內(nèi)容主要來自Andrew Ng教授的講義和學(xué)習(xí)視頻。 另外也包含來自其他論文和其他學(xué)校講義的一些內(nèi)容。每章內(nèi)容主要按照個(gè)人學(xué)習(xí)時(shí)的思路總結(jié)得到。 由于是個(gè)人筆記，里面表述錯(cuò)誤、公式錯(cuò)誤、理解錯(cuò)誤、筆誤都會存在。更重要的是我是初學(xué)者，千萬不要認(rèn)為里面的思路都正確。 如果有疑問的地方，請第一時(shí)間參考Andrew Ng教授的講義原文和 視頻，再有疑問的地方可以找一些大牛問問。 博客上很多網(wǎng)友提出的問題，我難以回答，因?yàn)槲宜酱_實(shí)有限， 更深層次的內(nèi)容最好找相關(guān)大牛咨詢和相關(guān)論文研讀。 如果有網(wǎng)友想在我這個(gè)版本基礎(chǔ)上再添加自己的筆記，可以發(fā)送 Email給我，我提供原始的word docx版本。 另，本人目前在科苑軟件所讀研，馬上三年了，方向是分布式計(jì)算，主要偏大數(shù)據(jù)分布式處理，平時(shí)主要玩Hadoop、Pig、Hive、 Mahout、NoSQL啥的， 關(guān)注系統(tǒng)方面和數(shù)據(jù)庫方面的會議。希望大家多多交流，以后會往博客上放這些內(nèi)容，機(jī)器學(xué)習(xí)會放的少了。 Anyway，祝大家學(xué)習(xí)進(jìn)步、事業(yè)成功！ 對回歸方法的認(rèn)識 JerryLead csxulijie@gmail.com 2011 年 2 月 27 日 1 摘要 本報(bào)告是在學(xué)習(xí)斯坦福大學(xué)機(jī)器學(xué)習(xí)課程前四節(jié)加上配套的講義后的總結(jié)與認(rèn)識。前四節(jié)主要講述了回歸問題，屬于有監(jiān)督學(xué)習(xí)中的一種方法。該方法的核心思想是從離散的統(tǒng)計(jì)數(shù)據(jù)中得到數(shù)學(xué)模型，然后將該數(shù)學(xué)模型用于預(yù)測或者分類。該方法處理的數(shù)據(jù)可以是多維的。 講義最初介紹了一個(gè)基本問題，然后引出了線性回歸的解決方法，然后針對誤差問題做了概率解釋。 2 問題引入 假設(shè)有一個(gè)房屋銷售的數(shù)據(jù)如下： 面積(m^2) 銷售價(jià)錢（萬元） 123 250 150 320 87 160 102 220 … … 這個(gè)表類似于北京 5 環(huán)左右的房屋價(jià)錢，我們可以做出一個(gè)圖，x 軸是房屋的面積。y 軸是房屋的售價(jià)，如下： 如果來了一個(gè)新的面積，假設(shè)在銷售價(jià)錢的記錄中沒有的，我們怎么辦呢？ 我們可以用一條曲線去盡量準(zhǔn)的擬合這些數(shù)據(jù)，然后如果有新的輸入過來，我們可以在將曲線上這個(gè)點(diǎn)對應(yīng)的值返回。如果用一條直線去擬合，可能是下面的樣子： 綠色的點(diǎn)就是我們想要預(yù)測的點(diǎn)。 首先給出一些概念和常用的符號。 房屋銷售記錄表：訓(xùn)練集(training set)或者訓(xùn)練數(shù)據(jù)(training data), 是我們流程中的輸入數(shù)據(jù)，一般稱為 x 房屋銷售價(jià)錢：輸出數(shù)據(jù)，一般稱為 y 擬合的函數(shù)（或者稱為假設(shè)或者模型）：一般寫做 y = h(x) 訓(xùn)練數(shù)據(jù)的條目數(shù)(#training set),：一條訓(xùn)練數(shù)據(jù)是由一對輸入數(shù)據(jù)和輸出數(shù)據(jù)組成的輸入數(shù)據(jù)的維度 n (特征的個(gè)數(shù)，#features) 這個(gè)例子的特征是兩維的，結(jié)果是一維的。然而回歸方法能夠解決特征多維，結(jié)果是一維多離散值或一維連續(xù)值的問題。 3 學(xué)習(xí)過程 下面是一個(gè)典型的機(jī)器學(xué)習(xí)的過程，首先給出一個(gè)輸入數(shù)據(jù)，我們的算法會通過一系列的過程得到一個(gè)估計(jì)的函數(shù)，這個(gè)函數(shù)有能力對沒有見過的新數(shù)據(jù)給出一個(gè)新的估計(jì)，也被稱為構(gòu)建一個(gè)模型。就如同上面的線性回歸函數(shù)。 4 線性回歸 線性回歸假設(shè)特征和結(jié)果滿足線性關(guān)系。其實(shí)線性關(guān)系的表達(dá)能力非常強(qiáng)大，每個(gè)特征對結(jié)果的影響強(qiáng)弱可以有前面的參數(shù)體現(xiàn)，而且每個(gè)特征變量可以首先映射到一個(gè)函數(shù)，然后再參與線性計(jì)算。這樣就可以表達(dá)特征與結(jié)果之間的非線性關(guān)系。 我們用 X1，X2..Xn 去描述 feature 里面的分量，比如 x1=房間的面積，x2=房間的朝向，等等，我們可以做出一個(gè)估計(jì)函數(shù)： θ 在這兒稱為參數(shù)，在這的意思是調(diào)整 feature 中每個(gè)分量的影響力，就是到底是房屋的面積更重要還是房屋的地段更重要。為了如果我們令 X0 = 1，就可以用向量的方式來表示了： 我們程序也需要一個(gè)機(jī)制去評估我們 θ 是否比較好，所以說需要對我們做出的 h 函數(shù)進(jìn)行評估，一般這個(gè)函數(shù)稱為損失函數(shù)（loss function）或者錯(cuò)誤函數(shù)(error function)，描述 h 函數(shù)不好的程度，在下面，我們稱這個(gè)函數(shù)為 J 函數(shù) 在這兒我們可以做出下面的一個(gè)錯(cuò)誤函數(shù)： 這個(gè)錯(cuò)誤估計(jì)函數(shù)是去對 x(i)的估計(jì)值與真實(shí)值 y(i)差的平方和作為錯(cuò)誤估計(jì)函數(shù)，前面乘上的 1/2 是為了在求導(dǎo)的時(shí)候，這個(gè)系數(shù)就不見了。 至于為何選擇平方和作為錯(cuò)誤估計(jì)函數(shù)，講義后面從概率分布的角度講解了該公式的來源。 如何調(diào)整 θ 以使得 J(θ)取得最小值有很多方法，其中有最小二乘法(min square)，是一種完全是數(shù)學(xué)描述的方法，和梯度下降法。 5 梯度下降法 在選定線性回歸模型后，只需要確定參數(shù) θ，就可以將模型用來預(yù)測。然而 θ 需要在 J(θ) 最小的情況下才能確定。因此問題歸結(jié)為求極小值問題，使用梯度下降法。梯度下降法最大的問題是求得有可能是全局極小值，這與初始點(diǎn)的選取有關(guān)。 梯度下降法是按下面的流程進(jìn)行的： 1） 首先對 θ 賦值，這個(gè)值可以是隨機(jī)的，也可以讓 θ 是一個(gè)全零的向量。 2） 改變 θ 的值，使得 J(θ)按梯度下降的方向進(jìn)行減少。 梯度方向由 J(θ)對 θ 的偏導(dǎo)數(shù)確定，由于求的是極小值，因此梯度方向是偏導(dǎo)數(shù)的反方向。 結(jié)果為 迭代更新的方式有兩種，一種是批梯度下降，也就是對全部的訓(xùn)練數(shù)據(jù)求得誤差后再對 θ 進(jìn)行更新，另外一種是增量梯度下降，每掃描一步都要對 θ 進(jìn)行更新。前一種方法能夠不斷收斂，后一種方法結(jié)果可能不斷在收斂處徘徊。 一般來說，梯度下降法收斂速度還是比較慢的。 另一種直接計(jì)算結(jié)果的方法是最小二乘法。 6 最小二乘法 將訓(xùn)練特征表示為 X 矩陣，結(jié)果表示成 y 向量，仍然是線性回歸模型，誤差函數(shù)不變。那么 θ 可以直接由下面公式得出 但此方法要求 X 是列滿秩的，而且求矩陣的逆比較慢。 7 選用誤差函數(shù)為平方和的概率解釋 假設(shè)根據(jù)特征的預(yù)測結(jié)果與實(shí)際結(jié)果有誤差∈(??)，那么預(yù)測結(jié)果??????(i)和真實(shí)結(jié)果??(??)滿足下式： 一般來講，誤差滿足平均值為 0 的高斯分布，也就是正態(tài)分布。那么 x 和 y 的條件概率也就是 這樣就估計(jì)了一條樣本的結(jié)果概率，然而我們期待的是模型能夠在全部樣本上預(yù)測最準(zhǔn)，也就是概率積最大。這個(gè)概率積成為最大似然估計(jì)。我們希望在最大似然估計(jì)得到最大值時(shí)確定 θ。那么需要對最大似然估計(jì)公式求導(dǎo)，求導(dǎo)結(jié)果既是 這就解釋了為何誤差函數(shù)要使用平方和。 當(dāng)然推導(dǎo)過程中也做了一些假定，但這個(gè)假定符合客觀規(guī)律。 8 帶權(quán)重的線性回歸上面提到的線性回歸的誤差函數(shù)里系統(tǒng)都是 1，沒有權(quán)重。帶權(quán)重的線性回歸加入了權(quán)重信息。 基本假設(shè)是 其中假設(shè)??(i)符合公式 其中 x 是要預(yù)測的特征，這樣假設(shè)的道理是離 x 越近的樣本權(quán)重越大，越遠(yuǎn)的影響越小。這個(gè)公式與高斯分布類似，但不一樣，因?yàn)閣(i)不是隨機(jī)變量。 此方法成為非參數(shù)學(xué)習(xí)算法，因?yàn)檎`差函數(shù)隨著預(yù)測值的不同而不同，這樣 θ 無法事先確定，預(yù)測一次需要臨時(shí)計(jì)算，感覺類似 KNN。 9 分類和對數(shù)回歸 一般來說，回歸不用在分類問題上，因?yàn)榛貧w是連續(xù)型模型，而且受噪聲影響比較大。如果非要應(yīng)用進(jìn)入，可以使用對數(shù)回歸。 對數(shù)回歸本質(zhì)上是線性回歸，只是在特征到結(jié)果的映射中加入了一層函數(shù)映射，即先把特征線性求和，然后使用函數(shù) g(z)將最為假設(shè)函數(shù)來預(yù)測。g(z)可以將連續(xù)值映射到 0 和 1 上。 對數(shù)回歸的假設(shè)函數(shù)如下，線性回歸假設(shè)函數(shù)只是??????。 對數(shù)回歸用來分類 0/1 問題，也就是預(yù)測結(jié)果屬于 0 或者 1 的二值分類問題。這里假設(shè)了二值滿足伯努利分布，也就是 當(dāng)然假設(shè)它滿足泊松分布、指數(shù)分布等等也可以，只是比較復(fù)雜，后面會提到線性回歸的一般形式。 與第 7 節(jié)一樣，仍然求的是最大似然估計(jì)，然后求導(dǎo)，得到迭代公式結(jié)果為 可以看到與線性回歸類似，只是??????(i)換成了???(??(??))，而???(??(??))實(shí)際上就是??????(i)經(jīng)過 g(z)映射過來的。 10 牛頓法來解最大似然估計(jì) 第 7 和第 9 節(jié)使用的解最大似然估計(jì)的方法都是求導(dǎo)迭代的方法，這里介紹了牛頓下降法，使結(jié)果能夠快速的收斂。 當(dāng)要求解f(θ) = 0時(shí)，如果 f 可導(dǎo)，那么可以通過迭代公式 來迭代求解最小值。 當(dāng)應(yīng)用于求解最大似然估計(jì)的最大值時(shí)，變成求解?′(??) = 0的問題。 那么迭代公式寫作 當(dāng) θ 是向量時(shí)，牛頓法可以使用下面式子表示 其中 是 nn 的 Hessian 矩陣。 牛頓法收斂速度雖然很快，但求 Hessian 矩陣的逆的時(shí)候比較耗費(fèi)時(shí)間。 當(dāng)初始點(diǎn) X0 靠近極小值 X 時(shí)，牛頓法的收斂速度是最快的。但是當(dāng) X0 遠(yuǎn)離極小值時(shí)，牛頓法可能不收斂，甚至連下降都保證不了。原因是迭代點(diǎn) Xk+1 不一定是目標(biāo)函數(shù) f 在牛頓方向上的極小點(diǎn)。 11 一般線性模型之所以在對數(shù)回歸時(shí)使用 的公式是由一套理論作支持的。 這個(gè)理論便是一般線性模型。 首先，如果一個(gè)概率分布可以表示成 時(shí)，那么這個(gè)概率分布可以稱作是指數(shù)分布。 伯努利分布，高斯分布，泊松分布，貝塔分布，狄特里特分布都屬于指數(shù)分布。 在對數(shù)回歸時(shí)采用的是伯努利分布，伯努利分布的概率可以表示成 其中 得到 這就解釋了對數(shù)回歸時(shí)為了要用這個(gè)函數(shù)。 一般線性模型的要點(diǎn)是 ） 滿足一個(gè)以 為參數(shù)的指數(shù)分布，那么可以求得 的表達(dá)式。 ） 給定 x，我們的目標(biāo)是要確定，大多數(shù)情況下 ，那么我們實(shí)際上要確定的是 ，而 。（在對數(shù)回歸中期望值是 ，因此 h 是；在線性回歸中期望值是 ，而高斯分布中 ，因此線性回歸中 h=）。 ） 12 Softmax 回歸 最后舉了一個(gè)利用一般線性模型的例子。 假設(shè)預(yù)測值 y 有 k 種可能，即 y 比如 時(shí)，可以看作是要將一封未知郵件分為垃圾郵件、個(gè)人郵件還是工作郵件這三類。 定義 那么 這樣 即式子左邊可以有其他的概率表示，因此可以當(dāng)做是 k-1 維的問題。 T(y)這時(shí)候一組 k-1 維的向量，不再是 y。即 T(y)要給出 y=i（i 從 1 到 k-1）的概率 應(yīng)用于一般線性模型 那么 最后求得 而 y=i 時(shí) 求得期望值 那么就建立了假設(shè)函數(shù)，最后就獲得了最大似然估計(jì) 對該公式可以使用梯度下降或者牛頓法迭代求解。 解決了多值模型建立與預(yù)測問題。 學(xué)習(xí)總結(jié) 該講義組織結(jié)構(gòu)清晰，思路獨(dú)特，講原因，也講推導(dǎo)?？少F的是講出了問題的基本解決思路和擴(kuò)展思路，更重要的是講出了為什么要使用相關(guān)方法以及問題根源。在看似具體的解題思路中能引出更為抽象的一般解題思路，理論化水平很高。 該方法可以用在對數(shù)據(jù)多維分析和多值預(yù)測上，更適用于數(shù)據(jù)背后蘊(yùn)含某種概率模型的情景。 判別模型、生成模型與樸素貝葉斯方法 JerryLead csxulijie@gmail.com 2011 年 3 月 5 日星期六 1 判別模型與生成模型 上篇報(bào)告中提到的回歸模型是判別模型，也就是根據(jù)特征值來求結(jié)果的概率。形式化表示為??(??|??; ??)，在參數(shù)??確定的情況下，求解條件概率??(??|??)。通俗的解釋為在給定特征后預(yù)測結(jié)果出現(xiàn)的概率。 比如說要確定一只羊是山羊還是綿羊，用判別模型的方法是先從歷史數(shù)據(jù)中學(xué)習(xí)到模型，然后通過提取這只羊的特征來預(yù)測出這只羊是山羊的概率，是綿羊的概率。換一種思路，我們可以根據(jù)山羊的特征首先學(xué)習(xí)出一個(gè)山羊模型，然后根據(jù)綿羊的特征學(xué)習(xí)出一個(gè)綿羊模型。然后從這只羊中提取特征，放到山羊模型中看概率是多少，再放到綿羊模型中看概率是多少， 哪個(gè)大就是哪個(gè)。形式化表示為求??(??|y)（也包括??(??)），y 是模型結(jié)果，x 是特征。 利用貝葉斯公式發(fā)現(xiàn)兩個(gè)模型的統(tǒng)一性： 由于我們關(guān)注的是 y 的離散值結(jié)果中哪個(gè)概率大（比如山羊概率和綿羊概率哪個(gè)大），而并不是關(guān)心具體的概率，因此上式改寫為： 其中??(??|y)稱為后驗(yàn)概率，??(??)稱為先驗(yàn)概率。 由??(??|y) ? ??(??) = ??(??, ??)，因此有時(shí)稱判別模型求的是條件概率，生成模型求的是聯(lián)合概率。 常見的判別模型有線性回歸、對數(shù)回歸、線性判別分析、支持向量機(jī)、boosting、條件隨機(jī)場、神經(jīng)網(wǎng)絡(luò)等。 常見的生產(chǎn)模型有隱馬爾科夫模型、樸素貝葉斯模型、高斯混合模型、LDA、Restricted Boltzmann Machine 等。 這篇博客較為詳細(xì)地介紹了兩個(gè)模型： http://blog.sciencenet.cn/home.php?mod=space&uid=248173&do=blog&id=227964 2 高斯判別分析（Gaussian discriminant analysis） 1） 多值正態(tài)分布 多變量正態(tài)分布描述的是 n 維隨機(jī)變量的分布情況，這里的μ變成了向量，σ也變成了矩陣Σ。寫作??(??, ??)。假設(shè)有 n 個(gè)隨機(jī)變量??1, ??2, … , ????。μ的第 i 個(gè)分量是E(X??)，而 Σii = Var(????)，Σij = Cov(????, ????)。 概率密度函數(shù)如下： 其中|Σ|是Σ的行列式，Σ是協(xié)方差矩陣，而且是對稱半正定的。 當(dāng)μ是二維的時(shí)候可以如下圖表示： 其中μ決定中心位置，Σ決定投影橢圓的朝向和大小。 如下圖： 對應(yīng)的Σ都不同。 2） 模型分析與應(yīng)用如果輸入特征x是連續(xù)型隨機(jī)變量，那么可以使用高斯判別分析模型來確定p(x|y)。 模型如下： 輸出結(jié)果服從伯努利分布，在給定模型下特征符合多值高斯分布。通俗地講，在山羊模型下，它的胡須長度，角大小，毛長度等連續(xù)型變量符合高斯分布，他們組成的特征向量符合多值高斯分布。這樣，可以給出概率密度函數(shù)： 最大似然估計(jì)如下： 注意這里的參數(shù)有兩個(gè)μ，表示在不同的結(jié)果模型下，特征均值不同，但我們假設(shè)協(xié)方差相同。反映在圖上就是不同模型中心位置不同，但形狀相同。這樣就可以用直線來進(jìn)行分隔判別。 求導(dǎo)后，得到參數(shù)估計(jì)公式： Φ是訓(xùn)練樣本中結(jié)果 y=1 占有的比例。 μ0是 y=0 的樣本中特征均值。 μ1是 y=1 的樣本中特征均值。 Σ是樣本特征方差均值。 如前面所述，在圖上表示為： 直線兩邊的 y 值不同，但協(xié)方差矩陣相同，因此形狀相同。μ不同，因此位置不同。 3） 高斯判別分析（GDA）與 logistic 回歸的關(guān)系將 GDA 用條件概率方式來表述的話，如下： y 是 x 的函數(shù)，其中 都是參數(shù)。 進(jìn)一步推導(dǎo)出 這里的 θ 是 的函數(shù)。 這個(gè)形式就是 logistic 回歸的形式。 也就是說如果 p(x|y)符合多元高斯分布，那么 p(y|x)符合 logistic 回歸模型。反之，不成立。為什么反過來不成立呢？因?yàn)?GDA 有著更強(qiáng)的假設(shè)條件和約束。 如果認(rèn)定訓(xùn)練數(shù)據(jù)滿足多元高斯分布，那么 GDA 能夠在訓(xùn)練集上是最好的模型。然而，我們往往事先不知道訓(xùn)練數(shù)據(jù)滿足什么樣的分布，不能做很強(qiáng)的假設(shè)。Logistic 回歸的條件假設(shè)要弱于 GDA，因此更多的時(shí)候采用 logistic 回歸的方法。 例如，訓(xùn)練數(shù)據(jù)滿足泊松分布， ，那么 p(y|x)也是 logistic 回歸的。這個(gè)時(shí)候如果采用 GDA，那么效果會比較差，因?yàn)橛?xùn)練數(shù)據(jù)特征的分布不是多元高斯分布，而是泊松分布。 這也是 logistic 回歸用的更多的原因。 3 樸素貝葉斯模型 在 GDA 中，我們要求特征向量 x 是連續(xù)實(shí)數(shù)向量。如果 x 是離散值的話，可以考慮采用樸素貝葉斯的分類方法。 假如要分類垃圾郵件和正常郵件。分類郵件是文本分類的一種應(yīng)用。 假設(shè)采用最簡單的特征描述方法，首先找一部英語詞典，將里面的單詞全部列出來。然后將每封郵件表示成一個(gè)向量，向量中每一維都是字典中的一個(gè)詞的 0/1 值，1 表示該詞在郵件中出現(xiàn)，0 表示未出現(xiàn)。 比如一封郵件中出現(xiàn)了“a”和“buy”，沒有出現(xiàn)“aardvark”、“aardwolf”和“zygmurgy”，那么可以形式化表示為： 假設(shè)字典中總共有 5000 個(gè)詞，那么 x 是 5000 維的。這時(shí)候如果要建立多項(xiàng)式分布模型 （二項(xiàng)分布的擴(kuò)展）。 多項(xiàng)式分布（ multinomial distribution ） 某隨機(jī)實(shí)驗(yàn)如果有 k 個(gè)可能結(jié)局 A1 ， A2 ， … ， Ak ，它們的概率分布分別是 p1 ， p2 ， … ， pk ， 那么在 N 次采樣的總結(jié)果中， A1 出現(xiàn) n1 次， A2 出現(xiàn) n2 次， … ， Ak 出現(xiàn) nk 次的這種事件 的出現(xiàn)概率 P 有下面公式： （ Xi 代表出現(xiàn) ni 次） 對應(yīng)到上面的問題上來，把每封郵件當(dāng)做一次隨機(jī)試驗(yàn)，那么結(jié)果的可能性有25000種。意味著 pi 有25000個(gè)，參數(shù)太多，不可能用來建模。 換種思路，我們要求的是 p(y|x)，根據(jù)生成模型定義我們可以求 p(x|y)和 p(y)。假設(shè) x 中的特征是條件獨(dú)立的。這個(gè)稱作樸素貝葉斯假設(shè)。如果一封郵件是垃圾郵件（y=1），且這封郵件出現(xiàn)詞“buy”與這封郵件是否出現(xiàn)“price”無關(guān)，那么“buy”和“price”之間是條件獨(dú)立的。 形式化表示為，（如果給定 Z 的情況下，X 和 Y 條件獨(dú)立）： 也可以表示為： 回到問題中 這個(gè)與 NLP 中的 n 元語法模型有點(diǎn)類似，這里相當(dāng)于 unigram。 這里我們發(fā)現(xiàn)樸素貝葉斯假設(shè)是約束性很強(qiáng)的假設(shè)，“buy”從通常上講與“price”是有關(guān)系，我們這里假設(shè)的是條件獨(dú)立。（注意條件獨(dú)立和獨(dú)立是不一樣的）建立形式化的模型表示： 那么我們想要的是模型在訓(xùn)練數(shù)據(jù)上概率積能夠最大，即最大似然估計(jì)如下： 注意這里是聯(lián)合概率分布積最大，說明樸素貝葉斯是生成模型。 求解得： 最后一個(gè)式子是表示 y=1 的樣本數(shù)占全部樣本數(shù)的比例，前兩個(gè)表示在 y=1 或 0 的樣本中，特征 Xj=1 的比例。 然而我們要求的是 實(shí)際是求出分子即可，分母對 y=1 和 y=0 都一樣。 當(dāng)然，樸素貝葉斯方法可以擴(kuò)展到 x 和 y 都有多個(gè)離散值的情況。對于特征是連續(xù)值的情況，我們也可以采用分段的方法來將連續(xù)值轉(zhuǎn)化為離散值。具體怎么轉(zhuǎn)化能夠最優(yōu)，我們可以采用信息增益的度量方法來確定（參見 Mitchell 的《機(jī)器學(xué)習(xí)》決策樹那一章）。 比如房子大小可以如下劃分成離散值： 4 拉普拉斯平滑 樸素貝葉斯方法有個(gè)致命的缺點(diǎn)就是對數(shù)據(jù)稀疏問題過于敏感。 比如前面提到的郵件分類，現(xiàn)在新來了一封郵件，郵件標(biāo)題是“NIPS call for papers”。我們使用更大的網(wǎng)絡(luò)詞典（詞的數(shù)目由 5000 變?yōu)?35000）來分類，假設(shè) NIPS 這個(gè)詞在字典中的位置是 35000。然而 NIPS 這個(gè)詞沒有在訓(xùn)練數(shù)據(jù)中出現(xiàn)過，這封郵件第一次出現(xiàn)了 NIPS。 那我們算概率的時(shí)候如下： 由于 NIPS 在以前的不管是垃圾郵件還是正常郵件都沒出現(xiàn)過，那么結(jié)果只能是 0 了。 顯然最終的條件概率也是 0。 原因就是我們的特征概率條件獨(dú)立，使用的是相乘的方式來得到結(jié)果。 為了解決這個(gè)問題，我們打算給未出現(xiàn)特征值，賦予一個(gè)“小”的值而不是 0。 具體平滑方法如下： 假設(shè)離散型隨機(jī)變量 z 有{1,2,…,k}個(gè)值，我們用Φ?? = p(z = i)來表示每個(gè)值的概率。假 設(shè)有 m 個(gè)訓(xùn)練樣本中，z 的觀察值是其中每一個(gè)觀察值對應(yīng) k 個(gè)值中的一個(gè)。那么根據(jù)原來的估計(jì)方法可以得到 說白了就是 z=j 出現(xiàn)的比例。 拉普拉斯平滑法將每個(gè) k 值出現(xiàn)次數(shù)事先都加 1，通俗講就是假設(shè)他們都出現(xiàn)過一次。 那么修改后的表達(dá)式為： 每個(gè) z=j 的分子都加 1 ，分母加 k ?？梢? 。 這個(gè)有點(diǎn)像 NLP 里面的加一平滑法，當(dāng)然還有 n 多平滑法了，這里不再詳述。 回到郵件分類的問題，修改后的公式為： 5 文本分類的事件模型 回想一下我們剛剛使用的用于文本分類的樸素貝葉斯模型，這個(gè)模型稱作多值伯努利事件模型（multi-variate Bernoulli event model）。在這個(gè)模型中，我們首先隨機(jī)選定了郵件的類型（垃圾或者普通郵件，也就是 p(y)），然后一個(gè)人翻閱詞典，從第一個(gè)詞到最后一個(gè)詞，隨機(jī)決定一個(gè)詞是否要在郵件中出現(xiàn)，出現(xiàn)標(biāo)示為 1，否則標(biāo)示為 0。然后將出現(xiàn)的詞組成一封郵件。決定一個(gè)詞是否出現(xiàn)依照概率 p(xi|y)。那么這封郵件的概率可以標(biāo)示為 。 讓我們換一個(gè)思路，這次我們不先從詞典入手，而是選擇從郵件入手。讓 i 表示郵件中的第 i 個(gè)詞，xi 表示這個(gè)詞在字典中的位置，那么 xi 取值范圍為{1,2,…|V|}，|V|是字典中詞 的數(shù)目。這樣一封郵件可以表示成，n 可以變化，因?yàn)槊糠忄]件的詞的個(gè)數(shù)不同。然后我們對于每個(gè) xi 隨機(jī)從|V|個(gè)值中取一個(gè)，這樣就形成了一封郵件。這相當(dāng)于重復(fù)投擲|V|面的骰子，將觀察值記錄下來就形成了一封郵件。當(dāng)然每個(gè)面的概率服從 p(xi|y)，而且每次試驗(yàn)條件獨(dú)立。這樣我們得到的郵件概率是。居然跟上面的一樣，那么不同點(diǎn)在哪呢？注意第一個(gè)的 n 是字典中的全部的詞，下面這個(gè) n 是郵件中的詞個(gè)數(shù)。上面 xi 表示一個(gè)詞是否出現(xiàn)，只有 0 和 1 兩個(gè)值，兩者概率和為 1。下面的 xi 表示|V|中的一個(gè)值，|V|個(gè) p(xi|y)相加和為 1。是多值二項(xiàng)分布模型。上面的 x 向量都是 0/1 值，下面的 x 的向量都是字典中的位置。 形式化表示為： m 個(gè)訓(xùn)練樣本表示為： 表示第 i 個(gè)樣本中，共有 ni 個(gè)詞，每個(gè)詞在字典中的編號為。 那么我們?nèi)匀话凑諛闼刎惾~斯的方法求得最大似然估計(jì)概率為 解得， 與以前的式子相比，分母多了個(gè) ni，分子由 0/1 變成了 k。 舉個(gè)例子： X1 X2 X3 Y 1 2 - 1 2 1 - 0 1 3 2 0 3 3 3 1 假如郵件中只有 a，b，c 這三詞，他們在詞典的位置分別是 1,2,3，前兩封郵件都只有 2 個(gè)詞，后兩封有 3 個(gè)詞。 Y=1 是垃圾郵件。 那么， 假如新來一封郵件為 b，c 那么特征表示為{2,3}。 那么 那么該郵件是垃圾郵件概率是 0.6。 注意這個(gè)公式與樸素貝葉斯的不同在于這里針對整體樣本求的????|??=1，而樸素貝葉斯里 面針對每個(gè)特征求的??xj=1|??=1，而且這里的特征值維度是參差不齊的。 這里如果假如拉普拉斯平滑，得到公式為： 表示每個(gè) k 值至少發(fā)生過一次。 另外樸素貝葉斯雖然有時(shí)候不是最好的分類方法，但它簡單有效，而且速度快。  支持向量機(jī)（上） JerryLead csxulijie@gmail.com 2011 年 3 月 12 日星期六 1 簡介 支持向量機(jī)基本上是最好的有監(jiān)督學(xué)習(xí)算法了。最開始接觸 SVM 是去年暑假的時(shí)候，老師要求交《統(tǒng)計(jì)學(xué)習(xí)理論》的報(bào)告，那時(shí)去網(wǎng)上下了一份入門教程，里面講的很通俗，當(dāng)時(shí)只是大致了解了一些相關(guān)概念。這次斯坦福提供的學(xué)習(xí)材料，讓我重新學(xué)習(xí)了一些 SVM 知識。我看很多正統(tǒng)的講法都是從 VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理出發(fā)，然后引出 SVM 什么的，還有些資料上來就講分類超平面什么的。這份材料從前幾節(jié)講的 logistic 回歸出發(fā)，引出了 SVM，既揭示了模型間的聯(lián)系，也讓人覺得過渡更自然。 2 重新審視 logistic 回歸 Logistic 回歸目的是從特征學(xué)習(xí)出一個(gè) 0/1 分類模型，而這個(gè)模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負(fù)無窮到正無窮。因此，使用 logistic 函數(shù)（或稱作 sigmoid 函數(shù)）將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于 y=1 的概率。 形式化表示就是假設(shè)函數(shù) 其中 x 是 n 維特征向量，函數(shù) g 就是 logistic 函數(shù)。 的圖像是 可以看到，將無窮映射到了(0,1)。 而假設(shè)函數(shù)就是特征屬于 y=1 的概率。 當(dāng)我們要判別一個(gè)新來的特征屬于哪個(gè)類時(shí)，只需求???(x)，若大于 0.5 就是 y=1 的類，反之屬于 y=0 類。 再審視一下???(x)，發(fā)現(xiàn)???(x)只和??????有關(guān)，??????>0，那么???(x) > 0.5，g(z)只不過是用來映射，真實(shí)的類別決定權(quán)還在??????。還有當(dāng)?????? ? 0時(shí)，???(x)=1，反之???(x)=0。如果我們只從??????出發(fā)，希望模型達(dá)到的目標(biāo)無非就是讓訓(xùn)練數(shù)據(jù)中 y=1 的特征?????? ? 0，而是 y=0 的特征?????? ? 0。Logistic 回歸就是要學(xué)習(xí)得到θ，使得正例的特征遠(yuǎn)大于 0，負(fù)例的特征遠(yuǎn)小于 0，強(qiáng)調(diào)在全部訓(xùn)練實(shí)例上達(dá)到這個(gè)目標(biāo)。 圖形化表示如下： 中間那條線是?????? = 0，logistic 回顧強(qiáng)調(diào)所有點(diǎn)盡可能地遠(yuǎn)離中間那條線。學(xué)習(xí)出的結(jié)果也就中間那條線?？紤]上面 3 個(gè)點(diǎn) A、B 和 C。從圖中我們可以確定 A 是類別的，然而 C 我們是不太確定的，B 還算能夠確定。這樣我們可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點(diǎn)，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點(diǎn)上達(dá)到最優(yōu)。因?yàn)槟菢拥脑挘沟靡徊糠贮c(diǎn)靠近中間線來換取另外一部分點(diǎn)更加遠(yuǎn)離中間線。我想這就是支持向量機(jī)的思路和 logistic 回歸的不同點(diǎn)，一個(gè)考慮局部（不關(guān)心已經(jīng)確定遠(yuǎn)離的點(diǎn)），一個(gè)考慮全局（已經(jīng)遠(yuǎn)離的點(diǎn)可能通過調(diào)整中間線使其能夠更加遠(yuǎn)離）。這是我的個(gè)人直觀理解。 3 形式化表示 我們這次使用的結(jié)果標(biāo)簽是 y=-1,y=1，替換在 logistic 回歸中使用的 y=0 和 y=1。同時(shí)將 θ替換成 w 和 b。以前的?????? = θ0 + θ1??1 + θ2??2 + ? + θ??????，其中認(rèn)為x0 = 1?，F(xiàn)在我們替換θ0為 b，后面替換θ1??1 + θ2??2 + ? + θ??????為w1??1 + w2??2 + ? + w??????（即??????）。這樣， 我們讓?????? = ?????? + b，進(jìn)一步???(x) = ??(??????) = g(?????? + b)。也就是說除了 y 由 y=0 變?yōu)?y=-1，只是標(biāo)記不同外，與 logistic 回歸的形式化表示沒區(qū)別。再明確下假設(shè)函數(shù) ???,??(x) = ??(?????? + b) 上一節(jié)提到過我們只需考慮??????的正負(fù)問題，而不用關(guān)心 g(z)，因此我們這里將 g(z)做一個(gè)簡化，將其簡單映射到 y=-1 和 y=1 上。映射關(guān)系如下： 1, z ≥ 0 g(z) = { ?1, z < 0 4 函數(shù)間隔（functional margin）和幾何間隔（geometric margin） 給定一個(gè)訓(xùn)練樣本(??(??), ??(??))，x 是特征，y 是結(jié)果標(biāo)簽。i 表示第 i 個(gè)樣本。我們定義函數(shù)間隔如下： ???(i) = ??(??)(??????(??) + ??) 可想而知，當(dāng)??(??) = 1時(shí)，在我們的 g(z)定義中，??????(??) + ?? ≥ 0，???(i)的值實(shí)際上就是 |??????(??) + ??|。反之亦然。為了使函數(shù)間隔最大（更大的信心確定該例是正例還是反例），當(dāng) ??(??) = 1時(shí)，??????(??) + ??應(yīng)該是個(gè)大正數(shù)，反之是個(gè)大負(fù)數(shù)。因此函數(shù)間隔代表了我們認(rèn)為特征是正例還是反例的確信度。 繼續(xù)考慮 w 和 b，如果同時(shí)加大 w 和 b，比如在(??????(??) + ??)前面乘個(gè)系數(shù)比如 2，那么所有點(diǎn)的函數(shù)間隔都會增大二倍，這個(gè)對求解問題來說不應(yīng)該有影響，因?yàn)槲覀円蠼獾氖?????? + ?? = 0，同時(shí)擴(kuò)大 w 和 b 對結(jié)果是無影響的。這樣，我們?yōu)榱讼拗?w 和 b，可能需要加入歸一化條件，畢竟求解的目標(biāo)是確定唯一一個(gè) w 和 b，而不是多組線性相關(guān)的向量。 這個(gè)歸一化一會再考慮。 剛剛我們定義的函數(shù)間隔是針對某一個(gè)樣本的，現(xiàn)在我們定義全局樣本上的函數(shù)間隔 說白了就是在訓(xùn)練樣本上分類正例和負(fù)例確信度最小那個(gè)函數(shù)間隔。 接下來定義幾何間隔，先看圖 假設(shè)我們有了 B 點(diǎn)所在的?????? + ?? = 0分割面。任何其他一點(diǎn)，比如 A 到該面的距離以 ??(??)表示，假設(shè) B 就是 A 在分割面上的投影。我們知道向量 BA 的方向是w（分割面的梯度），單位向量是 。A 點(diǎn)是(??(??), ??(??))，所以 B 點(diǎn)是 x=（利用初中的幾何知識），帶入?????? + ?? = 0得， 進(jìn)一步得到 ??(??)實(shí)際上就是點(diǎn)到平面距離。 再換種更加優(yōu)雅的寫法： 當(dāng)||w|| = 1時(shí)，不就是函數(shù)間隔嗎？是的，前面提到的函數(shù)間隔歸一化結(jié)果就是幾何間隔。他們?yōu)槭裁磿粯幽?？因?yàn)楹瘮?shù)間隔是我們定義的，在定義的時(shí)候就有幾何間隔的色彩。同樣，同時(shí)擴(kuò)大 w 和 b，w 擴(kuò)大幾倍，||w||就擴(kuò)大幾倍，結(jié)果無影響。同樣定義全局的幾何 間隔 5 最優(yōu)間隔分類器（optimal margin classifier） 回想前面我們提到我們的目標(biāo)是尋找一個(gè)超平面，使得離超平面比較近的點(diǎn)能有更大的間距。也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。形象的說，我們將上面的圖看作是一張紙，我們要找一條折線，按照這條折線折疊后，離折線最近的點(diǎn)的間距比其他折線都要大。形式化表示為： 這里用||w||=1 規(guī)約 w，使得?????? + ??是幾何間隔。 到此，我們已經(jīng)將模型定義出來了。如果求得了 w 和 b，那么來一個(gè)特征 x，我們就能夠分類了，稱為最優(yōu)間隔分類器。接下的問題就是如何求解 w 和 b 的問題了。 由于||w|| = 1不是凸函數(shù)，我們想先處理轉(zhuǎn)化一下，考慮幾何間隔和函數(shù)間隔的關(guān)系， ，我們改寫一下上面的式子： 這時(shí)候其實(shí)我們求的最大值仍然是幾何間隔，只不過此時(shí)的 w 不受||w|| = 1的約束了。然而這個(gè)時(shí)候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒法直接代入優(yōu)化軟件里計(jì)算。我們還要改寫。前面說到同時(shí)擴(kuò)大 w 和 b 對結(jié)果沒有影響，但我們最后要求的仍然是 w 和 b 的確定值，不是他們的一組倍數(shù)值，因此，我們需要對???做一些限制，以保證我們解是唯一的。這里為了簡便我們?nèi)??? = 1。這樣的意義是將全局的函數(shù)間隔定義為 1，也即是將離超平面最近的點(diǎn)的距離定義為 。由于求的最大值相當(dāng)于求 的最小值，因此改寫后結(jié)果為： 這下好了，只有線性約束了，而且是個(gè)典型的二次規(guī)劃問題（目標(biāo)函數(shù)是自變量的二次函數(shù)）。代入優(yōu)化軟件可解。到這里發(fā)現(xiàn)，這個(gè)講義雖然沒有像其他講義一樣先畫好圖，畫好分類超平面，在圖上標(biāo) 示出間隔那么直觀，但每一步推導(dǎo)有理有據(jù)，依靠思路的流暢性來推導(dǎo)出目標(biāo)函數(shù)和約束。 接下來介紹的是手工求解的方法了，一種更優(yōu)的求解方法。 6 拉格朗日對偶（Lagrange duality） 先拋開上面的二次規(guī)劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優(yōu)化問題： 目標(biāo)函數(shù)是 f(w)，下面是等式約束。通常解法是引入拉格朗日算子，這里使用β來表示算子，得到拉格朗日公式為 L 是等式約束的個(gè)數(shù)。 然后分別對 w 和β求偏導(dǎo)，使得偏導(dǎo)數(shù)等于 0，然后解出 w 和β??。至于為什么引入拉格朗日算子可以求出極值，原因是 f(w)的 dw 變化方向受其他不等式的約束，dw 的變化方向與 f(w)的梯度垂直時(shí)才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關(guān)系。（參考《最優(yōu)化與 KKT 條件》） 然后我們探討有不等式約束的極值問題求法，問題如下： 我們定義一般化的拉格朗日公式 這里的????和????都是拉格朗日算子。如果按這個(gè)公式求解，會出現(xiàn)問題，因?yàn)槲覀兦蠼獾氖亲钚≈?，而這里的??i(??) ≤ 0，我們可以將????調(diào)整成很大的正值，來使最后的函數(shù)結(jié)果是負(fù)無窮。因此我們需要排除這種情況，我們定義下面的函數(shù)： 這里的 P 代表 primal。假設(shè)??i(??) > 0或者?i(??) ≠ 0，那么我們總是可以調(diào)整????和????來使得????(w)有最大值為正無窮。而只有 g 和 h 滿足約束時(shí)，????(w)為 f(w)。這個(gè)函數(shù)的精妙之處在于???? ≥ 0，而且求極大值。 因此我們可以寫作 這樣我們原來要求的 min f(w)可以轉(zhuǎn)換成求min?? ????(w)了。 我們使用p?來表示min?? ????(w)。如果直接求解，首先面對的是兩個(gè)參數(shù)，而????也是不等式約束，然后再在 w 上求最小值。這個(gè)過程不容易做，那么怎么辦呢？ 我們先考慮另外一個(gè)問題 D 的意思是對偶， 將問題轉(zhuǎn)化為先求拉格朗日關(guān)于 w 的最小值，將α和β看 作是固定值。之后在 求最大值的話： 這個(gè)問題是原問題的對偶問題，相對于原問題只是更換了 min 和 max 的順序，而一般更換順序的結(jié)果是 Max Min(X) <= Min Max(X)。然而在這里兩者相等。用???來表示對偶問題如下： 下面解釋在什么條件下兩者會等價(jià)。假設(shè) f 和 g 都是凸函數(shù)，h 是仿射的（affine， ）。并且存在w 使得對于所有的 i，????(??) < 0。 在這種假設(shè)下，一定存在w?, ???, ???使得w?是原問題的解，???, ???是對偶問題的解。還有另外，w?, ???, ???滿足庫恩-塔克條件（Karush-Kuhn-Tucker, KKT condition），該條件如下： 所以如果w?, ???, ???滿足了庫恩-塔克條件，那么他們就是原問題和對偶問題的解。讓我們再次審視公式（5），這個(gè)條件稱作是 KKT dual complementarity 條件。這個(gè)條件隱含了如果??? > 0，那么????(???) = 0。也就是說，????(???) = 0時(shí)，w 處于可行域的邊界上，這時(shí)才是起作用的約束。而其他位于可行域內(nèi)部（????(???) < 0的）點(diǎn)都是不起作用的約束，其??? = 0。這個(gè) KKT 雙重補(bǔ)足條件會用來解釋支持向量和 SMO 的收斂測試。 這部分內(nèi)容思路比較凌亂，還需要先研究下《非線性規(guī)劃》中的約束極值問題，再回頭看看。KKT 的總體思想是認(rèn)為極值會在可行域邊界上取得，也就是不等式為 0 或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個(gè)元素要么是不等式為 0 的約束，要么是等式約束。對于在可行域邊界內(nèi)的點(diǎn)，對最優(yōu)解不起作用，因此前面的系數(shù)為 0。 7 最優(yōu)間隔分類器（optimal margin classifier）重新回到 SVM 的優(yōu)化問題： 我們將約束條件改寫為： 從 KKT 條件得知只有函數(shù)間隔是 1（離超平面最近的點(diǎn)）的線性約束式前面的系數(shù)???? > 0，也就是說這些約束式????(w) = 0，對于其他的不在線上的點(diǎn)(????(w) < 0)，極值不會在他們所在的范圍內(nèi)取得，因此前面的系數(shù)???? = 0.注意每一個(gè)約束式實(shí)際就是一個(gè)訓(xùn)練樣本。 看下面的圖： 實(shí)線是最大間隔超平面，假設(shè)號的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間隔是 1 的點(diǎn)，那么他們前面的系數(shù)???? > 0，其他點(diǎn)都是???? = 0。這三個(gè)點(diǎn)稱作支持向量。構(gòu)造拉格朗日函數(shù)如下： 注意到這里只有????沒有????是因?yàn)樵瓎栴}中沒有等式約束，只有不等式約束。 下面我們按照對偶問題的求解步驟來一步步進(jìn)行， 首先求解的最小值，對于固定的????， 的最小值只與 w 和 b 有關(guān)。對 w 和 b 分別求偏導(dǎo)數(shù)。 并得到 將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）化簡過程如下： “倒數(shù)第 4 步”推導(dǎo)到“倒數(shù)第 3 步”使用了線性代數(shù)的轉(zhuǎn)置運(yùn)算，由于????和??(??)都是實(shí)數(shù)，因此轉(zhuǎn)置后與自身一樣?！暗箶?shù)第 3 步”推導(dǎo)到“倒數(shù)第 2 步”使用了 (a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運(yùn)算法則。最后一步是上一步的順序調(diào)整。最后得到： 由于最后一項(xiàng)是 0，因此簡化為 這里我們將向量內(nèi)積表示為 此時(shí)的拉格朗日函數(shù)只包含了變量????。然而我們求出了????才能得到 w 和 b。 接著是極大化的過程， 前面提到過對偶問題和原問題滿足的幾個(gè)條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對于所有的i，????(??) < 0。因此，一定存在w?, ???使得w?是原問題的解，???是對偶問題的解。在這里，求????就是求???了。 如果求出了????，根據(jù)即可求出 w（也是w?，原問題的解）。然后 即可求出 b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。 關(guān)于上面的對偶問題如何求解，將留給下一篇中的 SMO 算法來闡明。 這里考慮另外一個(gè)問題，由于前面求解中得到 ?? w = ∑ ??????(??) ??(??) ??=1 我們通篇考慮問題的出發(fā)點(diǎn)是?????? + ??，根據(jù)求解得到的????，我們代入前式得到 也就是說，以前新來的要分類的樣本首先根據(jù) w 和 b 做一次線性運(yùn)算，然后看求的結(jié)果是大于 0 還是小于 0,來判斷正例還是負(fù)例?，F(xiàn)在有了????，我們不需要求出 w，只需將新來的樣本和訓(xùn)練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。那有人會說，與前面所有的樣本都做運(yùn)算是不是太耗時(shí)了？其實(shí)不然，我們從 KKT 條件中得到，只有支持向量的???? > 0，其他情況???? = 0。因此，我們只需求新來的樣本和支持向量的內(nèi)積，然后運(yùn)算即可。這種寫法為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。這是上篇，先寫這么多了。  支持向量機(jī) SVM（下） JerryLead csxulijie@gmail.com 2011 年 3 月 17 日星期四 7 核函數(shù)（Kernels） 考慮我們最初在“線性回歸”中提出的問題，特征是房子的面積 x，這里的 x 是實(shí)數(shù)，結(jié)果 y 是房子的價(jià)格。假設(shè)我們從樣本點(diǎn)的分布中看到 x 和 y 符合 3 次曲線，那么我們希望使用 x 的三次多項(xiàng)式來逼近這些樣本點(diǎn)。那么首先需要將特征 x 擴(kuò)展到三維，然后尋找特征和結(jié)果之間的模型。我們將這種特征變換稱作特征映射（feature mapping）。映射函數(shù)稱作，在這個(gè)例子中 我們希望將得到的特征映射后的特征應(yīng)用于 SVM 分類，而不是最初的特征。這樣，我們需要將前面 公式中的內(nèi)積從，映射到 。 至于為什么需要映射后的特征而不是最初的特征來參與計(jì)算，上面提到的（為了更好地?cái)M合）是其中一個(gè)原因，另外的一個(gè)重要原因是樣例可能存在線性不可分的情況，而將特征映射到高維空間后，往往就可分了。（在《數(shù)據(jù)挖掘?qū)д摗稰ang-Ning Tan 等人著的《支持向量機(jī)》那一章有個(gè)很好的例子說明） 將核函數(shù)形式化定義，如果原始特征內(nèi)積是 ，映射后為，那么定義核函數(shù)（Kernel）為 到這里，我們可以得出結(jié)論，如果要實(shí)現(xiàn)該節(jié)開頭的效果，只需先計(jì)算，然后計(jì)算即可，然而這種計(jì)算方式是非常低效的。比如最初的特征是 n 維的，我們將其 映射到 維，然后再計(jì)算，這樣需要的時(shí)間。那么我們能不能想辦法減少計(jì)算時(shí)間呢？先看一個(gè)例子，假設(shè) x 和 z 都是 n 維的， 展開后，得 這個(gè)時(shí)候發(fā)現(xiàn)我們可以只計(jì)算原始特征 x 和 z 內(nèi)積的平方（時(shí)間復(fù)雜度是 O(n)），就等價(jià)與計(jì)算映射后特征的內(nèi)積。也就是說我們不需要花時(shí)間了。現(xiàn)在看一下映射函數(shù)（n=3 時(shí)），根據(jù)上面的公式，得到 也就是說核函數(shù)只能在選擇這樣的 作為映射函數(shù)時(shí)才能夠等價(jià)于映射后特征的內(nèi)積。 再看一個(gè)核函數(shù) 對應(yīng)的映射函數(shù)（n=3 時(shí)）是 更一般地，核函數(shù) 對應(yīng)的映射后特征維度為。（這個(gè)我一直 沒有理解）。 由于計(jì)算的是內(nèi)積，我們可以想到 IR 中的余弦相似度，如果 x 和 z 向量夾角越小，那么核函數(shù)值越大，反之，越小。因此，核函數(shù)值是和 的相似度。 再看另外一個(gè)核函數(shù) 這時(shí)，如果 x 和 z 很相近（），那么核函數(shù)值為 1，如果 x 和 z 相差很大（），那么核函數(shù)值約等于 0。由于這個(gè)函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(Radial Basis Function 簡稱 RBF)。它能夠把原始特征映射到無窮維。 既然高斯核函數(shù)能夠比較 x 和 z 的相似度，并映射到 0 到 1，回想 logistic 回歸，sigmoid 函數(shù)可以，因此還有 sigmoid 核函數(shù)等等。 下面有張圖說明在低維線性不可分時(shí)，映射到高維后就可分了，使用高斯核函數(shù)。 來自 Eric Xing 的 slides 注意，使用核函數(shù)后，怎么分類新來的樣本呢？線性的時(shí)候我們使用 SVM 學(xué)習(xí)出 w 和 b，新來樣本 x 的話，我們使用來判斷，如果值大于等于 1，那么是正類，小于等于是負(fù)類。在兩者之間，認(rèn)為無法確定。如果使用了核函數(shù)后，就變成了 ，是否先要找到 ，然后再預(yù)測？答案肯定不是了，找 很麻煩，回想我們之前說過的 < ?? ( ) ?? ,??> ??(?? ( ) ?? ,??) 只需將 替換成 ，然后值的判斷同上。 8 核函數(shù)有效性判定 問題：給定一個(gè)函數(shù) K，我們能否使用 K 來替代計(jì)算，也就說，是否能夠找出一個(gè) ，使得對于所有的 x 和 z，都有？比如給出了，是否能夠認(rèn)為 K 是一個(gè)有效的核函數(shù)。 下面來解決這個(gè)問題，給定 m 個(gè)訓(xùn)練樣本，每一個(gè) 對應(yīng)一個(gè)特征向量。那么，我們可以將任意兩個(gè)和 帶入 K 中，計(jì)算得到 。I 可以從 1 到 m，j 可以從 1 到 m，這樣可以計(jì)算出 m*m 的核函數(shù)矩陣（Kernel Matrix）。為了方便，我們將核函數(shù)矩陣和都使用 K 來表示。 如果假設(shè) K 是有效的核函數(shù)，那么根據(jù)核函數(shù)定義 可見，矩陣 K 應(yīng)該是個(gè)對稱陣。讓我們得出一個(gè)更強(qiáng)的結(jié)論，首先使用符號來表示映射函數(shù)的第 k 維屬性值。那么對于任意向量 z，得 最后一步和前面計(jì)算時(shí)類似。從這個(gè)公式我們可以看出，如果 K 是個(gè)有效的核函數(shù)（即和 等價(jià)），那么，在訓(xùn)練集上得到的核函數(shù)矩陣 K 應(yīng)該是半正定的（） 這樣我們得到一個(gè)核函數(shù)的必要條件： K 是有效的核函數(shù) ==> 核函數(shù)矩陣 K 是對稱半正定的。 可幸的是，這個(gè)條件也是充分的，由 Mercer 定理來表達(dá)。 Mercer 定理： 如果函數(shù) K 是 上的映射（也就是從兩個(gè) n 維向量映射到實(shí)數(shù)域）。那么如果 K 是一個(gè)有效核函數(shù)（也稱為 Mercer 核函數(shù)），那么當(dāng)且僅當(dāng)對于訓(xùn)練樣例 ，其相應(yīng)的核函數(shù)矩陣是對稱半正定的。 Mercer 定理表明為了證明 K 是有效的核函數(shù)，那么我們不用去尋找，而只需要在訓(xùn)練集上求出各個(gè)，然后判斷矩陣 K 是否是半正定（使用左上角主子式大于等于零等方法）即可。 許多其他的教科書在 Mercer 定理證明過程中使用了范數(shù)和再生希爾伯特空間等概念，但在特征是 n 維的情況下，這里給出的證明是等價(jià)的。 核函數(shù)不僅僅用在 SVM 上，但凡在一個(gè)模型后算法中出現(xiàn)了，我們都可以常使用去替換，這可能能夠很好地改善我們的算法。 9 規(guī)則化和不可分情況處理（Regularization and the non-separable case） 我們之前討論的情況都是建立在樣例線性可分的假設(shè)上，當(dāng)樣例線性不可分時(shí)，我們可以嘗試使用核函數(shù)來將特征映射到高維，這樣很可能就可分了。然而，映射后我們也不能 100%保證可分。那怎么辦呢，我們需要將模型進(jìn)行調(diào)整，以保證在不可分的情況下，也能夠盡可能地找出分隔超平面。 看下面兩張圖： 可以看到一個(gè)離群點(diǎn)（可能是噪聲）可以造成超平面的移動，間隔縮小，可見以前的模型對噪聲非常敏感。再有甚者，如果離群點(diǎn)在另外一個(gè)類中，那么這時(shí)候就是線性不可分了。 這時(shí)候我們應(yīng)該允許一些點(diǎn)游離并在在模型中違背限制條件（函數(shù)間隔大于 1）。我們設(shè)計(jì)得到新的模型如下（也稱軟間隔）： 引入非負(fù)參數(shù)????后（稱為松弛變量），就允許某些樣本點(diǎn)的函數(shù)間隔小于 1，即在最大間隔區(qū)間里面，或者函數(shù)間隔是負(fù)數(shù)，即樣本點(diǎn)在對方的區(qū)域中。而放松限制條件后，我們需要重新調(diào)整目標(biāo)函數(shù)，以對離群點(diǎn)進(jìn)行處罰，目標(biāo)函數(shù)后面加上的C ∑m??=1 ????就表示離群點(diǎn)越多，目標(biāo)函數(shù)值越大，而我們要求的是盡可能小的目標(biāo)函數(shù)值。這里的 C 是離群點(diǎn)的權(quán)重， C 越大表明離群點(diǎn)對