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

...wd......wd......wd...CS229機(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)容主要來(lái)自AndrewNg教授的講義和學(xué)習(xí)視頻。另外也包含來(lái)自其他論文和其他學(xué)校講義的一些內(nèi)容。每章內(nèi)容主要按照個(gè)人學(xué)習(xí)時(shí)的思路總結(jié)得到。由于是個(gè)人筆記，里面表述錯(cuò)誤、公式錯(cuò)誤、理解錯(cuò)誤、筆誤都會(huì)存在。更重要的是我是初學(xué)者，千萬(wàn)不要認(rèn)為里面的思路都正確。如果有疑問(wèn)的地方，請(qǐng)第一時(shí)間參考AndrewNg教授的講義原文和視頻，再有疑問(wèn)的地方可以找一些大牛問(wèn)問(wèn)。博客上很多網(wǎng)友提出的問(wèn)題，我難以答復(fù)，因?yàn)槲宜酱_實(shí)有限，更深層次的內(nèi)容最好找相關(guān)大牛咨詢和相關(guān)論文研讀。如果有網(wǎng)友想在我這個(gè)版本根基上再添加自己的筆記，可以發(fā)送Email給我，我提供原始的worddocx版本。另，本人目前在科苑軟件所讀研，馬上三年了，方向是分布式計(jì)算，主要偏大數(shù)據(jù)分布式處理，平時(shí)主要玩Hadoop、Pig、Hive、Mahout、NoSQL啥的，關(guān)注系統(tǒng)方面和數(shù)據(jù)庫(kù)方面的會(huì)議。希望大家多多交流，以后會(huì)往博客上放這些內(nèi)容，機(jī)器學(xué)習(xí)會(huì)放的少了。Anyway，祝大家學(xué)習(xí)進(jìn)步、事業(yè)成功！對(duì)回歸方法的認(rèn)識(shí)JerryLeadcsxulijie@gmail2011年2月27日1摘要本報(bào)告是在學(xué)習(xí)斯坦福大學(xué)機(jī)器學(xué)習(xí)課程前四節(jié)加上配套的講義后的總結(jié)與認(rèn)識(shí)。前四節(jié)主要講述了回歸問(wèn)題，屬于有監(jiān)視學(xué)習(xí)中的一種方法。該方法的核心思想是從離散的統(tǒng)計(jì)數(shù)據(jù)中得到數(shù)學(xué)模型，然后將該數(shù)學(xué)模型用于預(yù)測(cè)或者分類。該方法處理的數(shù)據(jù)可以是多維的。講義最初介紹了一個(gè)基本問(wèn)題，然后引出了線性回歸的解決方法，然后針對(duì)誤差問(wèn)題做了概率解釋。2問(wèn)題引入假設(shè)有一個(gè)房屋銷售的數(shù)據(jù)如下：面積(m^2)銷售價(jià)人民幣〔萬(wàn)元〕12325015032087160102220……這個(gè)表類似于北京5環(huán)左右的房屋價(jià)人民幣，我們可以做出一個(gè)圖，x軸是房屋的面積。y軸是房屋的售價(jià)，如下：如果來(lái)了一個(gè)新的面積，假設(shè)在銷售價(jià)人民幣的記錄中沒(méi)有的，我們?nèi)艉无k呢我們可以用一條曲線去盡量準(zhǔn)的擬合這些數(shù)據(jù)，然后如果有新的輸入過(guò)來(lái)，我們可以在將曲線上這個(gè)點(diǎn)對(duì)應(yīng)的值返回。如果用一條直線去擬合，可能是下面的樣子：綠色的點(diǎn)就是我們想要預(yù)測(cè)的點(diǎn)。首先給出一些概念和常用的符號(hào)。房屋銷售記錄表：訓(xùn)練集(trainingset)或者訓(xùn)練數(shù)據(jù)(trainingdata),是我們流程中的輸入數(shù)據(jù)，一般稱為x房屋銷售價(jià)人民幣：輸出數(shù)據(jù)，一般稱為y擬合的函數(shù)〔或者稱為假設(shè)或者模型〕：一般寫(xiě)做y=h(x)訓(xùn)練數(shù)據(jù)的條目數(shù)(#trainingset),：一條訓(xùn)練數(shù)據(jù)是由一對(duì)輸入數(shù)據(jù)和輸出數(shù)據(jù)組成的輸入數(shù)據(jù)的維度n(特征的個(gè)數(shù)，#features)這個(gè)例子的特征是兩維的，結(jié)果是一維的。然而回歸方法能夠解決特征多維，結(jié)果是一維多離散值或一維連續(xù)值的問(wèn)題。3學(xué)習(xí)過(guò)程下面是一個(gè)典型的機(jī)器學(xué)習(xí)的過(guò)程，首先給出一個(gè)輸入數(shù)據(jù)，我們的算法會(huì)通過(guò)一系列的過(guò)程得到一個(gè)估計(jì)的函數(shù)，這個(gè)函數(shù)有能力對(duì)沒(méi)有見(jiàn)過(guò)的新數(shù)據(jù)給出一個(gè)新的估計(jì)，也被稱為構(gòu)建一個(gè)模型。就如同上面的線性回歸函數(shù)。4線性回歸線性回歸假設(shè)特征和結(jié)果滿足線性關(guān)系。其實(shí)線性關(guān)系的表達(dá)能力非常強(qiáng)大，每個(gè)特征對(duì)結(jié)果的影響強(qiáng)弱可以有前面的參數(shù)表達(dá)，而且每個(gè)特征變量可以首先映射到一個(gè)函數(shù)，然后再參與線性計(jì)算。這樣就可以表達(dá)特征與結(jié)果之間的非線性關(guān)系。我們用X1，X2..Xn去描述feature里面的分量，比方x1=房間的面積，x2=房間的朝向，等等，我們可以做出一個(gè)估計(jì)函數(shù)：θ在這兒稱為參數(shù)，在這的意思是調(diào)整feature中每個(gè)分量的影響力，就是到底是房屋的面積更重要還是房屋的地段更重要。為了如果我們令X0=1，就可以用向量的方式來(lái)表示了：我們程序也需要一個(gè)機(jī)制去評(píng)估我們?chǔ)仁欠駥?duì)比好，所以說(shuō)需要對(duì)我們做出的h函數(shù)進(jìn)展評(píng)估，一般這個(gè)函數(shù)稱為損失函數(shù)〔lossfunction〕或者錯(cuò)誤函數(shù)(errorfunction)，描述h函數(shù)不好的程度，在下面，我們稱這個(gè)函數(shù)為J函數(shù)在這兒我們可以做出下面的一個(gè)錯(cuò)誤函數(shù)：這個(gè)錯(cuò)誤估計(jì)函數(shù)是去對(duì)x(i)的估計(jì)值與真實(shí)值y(i)差的平方和作為錯(cuò)誤估計(jì)函數(shù)，前面乘上的1/2是為了在求導(dǎo)的時(shí)候，這個(gè)系數(shù)就不見(jiàn)了。至于為何選擇平方和作為錯(cuò)誤估計(jì)函數(shù)，講義后面從概率分布的角度講解了該公式的來(lái)源。若何調(diào)整θ以使得J(θ)取得最小值有很多方法，其中有最小二乘法(minsquare)，是一種完全是數(shù)學(xué)描述的方法，和梯度下降法。5梯度下降法在選定線性回歸模型后，只需要確定參數(shù)θ，就可以將模型用來(lái)預(yù)測(cè)。然而θ需要在J(θ)最小的情況下才能確定。因此問(wèn)題歸結(jié)為求極小值問(wèn)題，使用梯度下降法。梯度下降法最大的問(wèn)題是求得有可能是全局極小值，這與初始點(diǎn)的選取有關(guān)。梯度下降法是按下面的流程進(jìn)展的：首先對(duì)θ賦值，這個(gè)值可以是隨機(jī)的，也可以讓?duì)仁且粋€(gè)全零的向量。改變?chǔ)鹊闹担沟肑(θ)按梯度下降的方向進(jìn)展減少。梯度方向由J(θ)對(duì)θ的偏導(dǎo)數(shù)確定，由于求的是極小值，因此梯度方向是偏導(dǎo)數(shù)的反方向。結(jié)果為迭代更新的方式有兩種，一種是批梯度下降，也就是對(duì)全部的訓(xùn)練數(shù)據(jù)求得誤差后再對(duì)θ進(jìn)展更新，另外一種是增量梯度下降，每掃描一步都要對(duì)θ進(jìn)展更新。前一種方法能夠不斷收斂，后一種方法結(jié)果可能不斷在收斂處徘徊。一般來(lái)說(shuō)，梯度下降法收斂速度還是對(duì)比慢的。另一種直接計(jì)算結(jié)果的方法是最小二乘法。6最小二乘法將訓(xùn)練特征表示為X矩陣，結(jié)果表示成y向量，仍然是線性回歸模型，誤差函數(shù)不變。那么θ可以直接由下面公式得出但此方法要求X是列滿秩的，而且求矩陣的逆對(duì)比慢。7選用誤差函數(shù)為平方和的概率解釋假設(shè)根據(jù)特征的預(yù)測(cè)結(jié)果與實(shí)際結(jié)果有誤差∈(??)，那么預(yù)測(cè)結(jié)果??????(i)和真實(shí)結(jié)果??(??)滿足下式：一般來(lái)講，誤差滿足平均值為0的高斯分布，也就是正態(tài)分布。那么x和y的條件概率也就是這樣就估計(jì)了一條樣本的結(jié)果概率，然而我們期待的是模型能夠在全部樣本上預(yù)測(cè)最準(zhǔn)，也就是概率積最大。這個(gè)概率積成為最大似然估計(jì)。我們希望在最大似然估計(jì)得到最大值時(shí)確定θ。那么需要對(duì)最大似然估計(jì)公式求導(dǎo)，求導(dǎo)結(jié)果既是這就解釋了為何誤差函數(shù)要使用平方和。當(dāng)然推導(dǎo)過(guò)程中也做了一些假定，但這個(gè)假定符合客觀規(guī)律。8帶權(quán)重的線性回歸上面提到的線性回歸的誤差函數(shù)里系統(tǒng)都是1，沒(méi)有權(quán)重。帶權(quán)重的線性回歸參加了權(quán)重信息。基本假設(shè)是其中假設(shè)??(i)符合公式其中x是要預(yù)測(cè)的特征，這樣假設(shè)的道理是離x越近的樣本權(quán)重越大，越遠(yuǎn)的影響越小。這個(gè)公式與高斯分布類似，但不一樣，因?yàn)閣(i)不是隨機(jī)變量。此方法成為非參數(shù)學(xué)習(xí)算法，因?yàn)檎`差函數(shù)隨著預(yù)測(cè)值的不同而不同，這樣θ無(wú)法事先確定，預(yù)測(cè)一次需要臨時(shí)計(jì)算，感覺(jué)類似KNN。9分類和對(duì)數(shù)回歸一般來(lái)說(shuō)，回歸不用在分類問(wèn)題上，因?yàn)榛貧w是連續(xù)型模型，而且受噪聲影響對(duì)比大。如果非要應(yīng)用進(jìn)入，可以使用對(duì)數(shù)回歸。對(duì)數(shù)回歸本質(zhì)上是線性回歸，只是在特征到結(jié)果的映射中參加了一層函數(shù)映射，即先把特征線性求和，然后使用函數(shù)g(z)將最為假設(shè)函數(shù)來(lái)預(yù)測(cè)。g(z)可以將連續(xù)值映射到0和1上。對(duì)數(shù)回歸的假設(shè)函數(shù)如下，線性回歸假設(shè)函數(shù)只是??????。對(duì)數(shù)回歸用來(lái)分類0/1問(wèn)題，也就是預(yù)測(cè)結(jié)果屬于0或者1的二值分類問(wèn)題。這里假設(shè)了二值滿足伯努利分布，也就是當(dāng)然假設(shè)它滿足泊松分布、指數(shù)分布等等也可以，只是對(duì)比復(fù)雜，后面會(huì)提到線性回歸的一般形式。與第7節(jié)一樣，仍然求的是最大似然估計(jì)，然后求導(dǎo)，得到迭代公式結(jié)果為可以看到與線性回歸類似，只是??????(i)換成了???(??(??))，而???(??(??))實(shí)際上就是??????(i)經(jīng)過(guò)g(z)映射過(guò)來(lái)的。10牛頓法來(lái)解最大似然估計(jì)第7和第9節(jié)使用的解最大似然估計(jì)的方法都是求導(dǎo)迭代的方法，這里介紹了牛頓下降法，使結(jié)果能夠快速的收斂。當(dāng)要求解f(θ)=0時(shí)，如果f可導(dǎo)，那么可以通過(guò)迭代公式來(lái)迭代求解最小值。當(dāng)應(yīng)用于求解最大似然估計(jì)的最大值時(shí)，變成求解?′(??)=0的問(wèn)題。那么迭代公式寫(xiě)作當(dāng)θ是向量時(shí)，牛頓法可以使用下面式子表示其中是n×n的Hessian矩陣。其中牛頓法收斂速度雖然很快，但求Hessian矩陣的逆的時(shí)候?qū)Ρ认臅r(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一般線性模型之所以在對(duì)數(shù)回歸時(shí)使用的公式是由一套理論作支持的。這個(gè)理論便是一般線性模型。首先，如果一個(gè)概率分布可以表示成時(shí)，那么這個(gè)概率分布可以稱作是指數(shù)分布。伯努利分布，高斯分布，泊松分布，貝塔分布，狄特里特分布都屬于指數(shù)分布。在對(duì)數(shù)回歸時(shí)采用的是伯努利分布，伯努利分布的概率可以表示成其中得到這就解釋了對(duì)數(shù)回歸時(shí)為了要用這個(gè)函數(shù)。一般線性模型的要點(diǎn)是〕滿足一個(gè)以為參數(shù)的指數(shù)分布，那么可以求得的表達(dá)式。〕給定x，我們的目標(biāo)是要確定，大多數(shù)情況下，那么我們實(shí)際上要確定的是，而。〔在對(duì)數(shù)回歸中期望值是，因此h是；在線性回歸中期望值是，而高斯分布中，因此線性回歸中h=〕。〕12Softmax回歸最后舉了一個(gè)利用一般線性模型的例子。假設(shè)預(yù)測(cè)值y有k種可能，即y比方時(shí)，可以看作是要將一封未知郵件分為垃圾郵件、個(gè)人郵件還是工作郵件這三類。定義那么這樣即式子左邊可以有其他的概率表示，因此可以當(dāng)做是k-1維的問(wèn)題。T(y)這時(shí)候一組k-1維的向量，不再是y。即T(y)要給出y=i〔i從1到k-1〕的概率應(yīng)用于一般線性模型那么最后求得而y=i時(shí)求得期望值那么就建設(shè)了假設(shè)函數(shù)，最后就獲得了最大似然估計(jì)對(duì)該公式可以使用梯度下降或者牛頓法迭代求解。解決了多值模型建設(shè)與預(yù)測(cè)問(wèn)題。學(xué)習(xí)總結(jié)該講義組織構(gòu)造清晰，思路獨(dú)特，講原因，也講推導(dǎo)?？少F的是講出了問(wèn)題的基本解決思路和擴(kuò)展思路，更重要的是講出了為什么要使用相關(guān)方法以及問(wèn)題根源。在看似具體的解題思路中能引出更為抽象的一般解題思路，理論化水平很高。該方法可以用在對(duì)數(shù)據(jù)多維分析和多值預(yù)測(cè)上，更適用于數(shù)據(jù)背后蘊(yùn)含某種概率模型的情景。判別模型、生成模型與樸素貝葉斯方法JerryLeadcsxulijie@gmail2011年3月5日星期六1判別模型與生成模型上篇報(bào)告中提到的回歸模型是判別模型，也就是根據(jù)特征值來(lái)求結(jié)果的概率。形式化表示為??(??|??;??)，在參數(shù)??確定的情況下，求解條件概率??(??|??)。通俗的解釋為在給定特征后預(yù)測(cè)結(jié)果出現(xiàn)的概率。比方說(shuō)要確定一只羊是山羊還是綿羊，用判別模型的方法是先從歷史數(shù)據(jù)中學(xué)習(xí)到模型，然后通過(guò)提取這只羊的特征來(lái)預(yù)測(cè)出這只羊是山羊的概率，是綿羊的概率。換一種思路，我們可以根據(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)心具體的概率，因此上式改寫(xiě)為：其中??(??|y)稱為后驗(yàn)概率，??(??)稱為先驗(yàn)概率。由??(??|y)???(??)=??(??,??)，因此有時(shí)稱判別模型求的是條件概率，生成模型求的是聯(lián)合概率。常見(jiàn)的判別模型有線性回歸、對(duì)數(shù)回歸、線性判別分析、支持向量機(jī)、boosting、條件隨機(jī)場(chǎng)、神經(jīng)網(wǎng)絡(luò)等。常見(jiàn)的生產(chǎn)模型有隱馬爾科夫模型、樸素貝葉斯模型、高斯混合模型、LDA、RestrictedBoltzmannMachine等。這篇博客較為詳細(xì)地介紹了兩個(gè)模型：:///home.php?mod=space&uid=248173&do=blog&id=2279642高斯判別分析〔Gaussiandiscriminantanalysis〕多值正態(tài)分布多變量正態(tài)分布描述的是n維隨機(jī)變量的分布情況，這里的μ變成了向量，σ也變成了矩陣Σ。寫(xiě)作??(??,??)。假設(shè)有n個(gè)隨機(jī)變量??1,??2,…,????。μ的第i個(gè)分量是E(X??)，而Σii=Var(????)，Σij=Cov(????,????)。概率密度函數(shù)如下：其中|Σ|是Σ的行列式，Σ是協(xié)方差矩陣，而且是對(duì)稱半正定的。當(dāng)μ是二維的時(shí)候可以如以以下列圖表示：其中μ決定中心位置，Σ決定投影橢圓的朝向和大小。如以以下列圖：對(duì)應(yīng)的Σ都不同。模型分析與應(yīng)用如果輸入特征x是連續(xù)型隨機(jī)變量，那么可以使用高斯判別分析模型來(lái)確定p(x|y)。模型如下：輸出結(jié)果服從伯努利分布，在給定模型下特征符合多值高斯分布。通俗地講，在山羊模型下，它的胡須長(zhǎng)度，角大小，毛長(zhǎng)度等連續(xù)型變量符合高斯分布，他們組成的特征向量符合多值高斯分布。這樣，可以給出概率密度函數(shù)：最大似然估計(jì)如下：注意這里的參數(shù)有兩個(gè)μ，表示在不同的結(jié)果模型下，特征均值不同，但我們假設(shè)協(xié)方差一樣。反映在圖上就是不同模型中心位置不同，但形狀一樣。這樣就可以用直線來(lái)進(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用條件概率方式來(lái)表述的話，如下：y是x的函數(shù)，其中 都是參數(shù)。進(jìn)一步推導(dǎo)出這里的這里的θ是的函數(shù)。這個(gè)形式就是logistic回歸的形式。也就是說(shuō)如果p(x|y)符合多元高斯分布，那么p(y|x)符合logistic回歸模型。反之，不成立。為什么反過(guò)來(lái)不成立呢因?yàn)镚DA有著更強(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，那么效果會(huì)對(duì)比差，因?yàn)橛?xùn)練數(shù)據(jù)特征的分布不是多元高斯分布，而是泊松分布。這也是logistic回歸用的更多的原因。3樸素貝葉斯模型在GDA中，我們要求特征向量x是連續(xù)實(shí)數(shù)向量。如果x是離散值的話，可以考慮采用樸素貝葉斯的分類方法。假設(shè)要分類垃圾郵件和正常郵件。分類郵件是文本分類的一種應(yīng)用。假設(shè)采用最簡(jiǎn)單的特征描述方法，首先找一部英語(yǔ)詞典，將里面的單詞全部列出來(lái)。然后將每封郵件表示成一個(gè)向量，向量中每一維都是字典中的一個(gè)詞的0/1值，1表示該詞在郵件中出現(xiàn)，0表示未出現(xiàn)。比方一封郵件中出現(xiàn)了“a〞和“buy〞，沒(méi)有出現(xiàn)“aardvark〞、“aardwolf〞和“zygmurgy〞，那么可以形式化表示為：假設(shè)字典中總共有5000個(gè)詞，那么x是5000維的。這時(shí)候如果要建設(shè)多項(xiàng)式分布模型〔二項(xiàng)分布的擴(kuò)展〕?！捕?xiàng)分布的擴(kuò)展〕。多項(xiàng)式分布〔multinomialdistribution〕某隨機(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次〕對(duì)應(yīng)到上面的問(wèn)題上來(lái)，把每封郵件當(dāng)做一次隨機(jī)試驗(yàn)，那么結(jié)果的可能性有25000種。意味著pi有25000個(gè)，參數(shù)太多，不可能用來(lái)建模。換種思路，我們要求的是p(y|x)，根據(jù)生成模型定義我們可以求p(x|y)和p(y)。假設(shè)x中的特征是條件獨(dú)立的。這個(gè)稱作樸素貝葉斯假設(shè)。如果一封郵件是垃圾郵件〔y=1〕，且這封郵件出現(xiàn)詞“buy〞與這封郵件是否出現(xiàn)“price〞無(wú)關(guān)，那么“buy〞和“price〞之間是條件獨(dú)立的。形式化表示為，〔如果給定Z的情況下，X和Y條件獨(dú)立〕：也可以表示為：回到問(wèn)題中這個(gè)與NLP中的n元語(yǔ)法模型有點(diǎn)類似，這里相當(dāng)于unigram。這里我們發(fā)現(xiàn)樸素貝葉斯假設(shè)是約束性很強(qiáng)的假設(shè)，“buy〞從通常上講與“price〞是有關(guān)系，我們這里假設(shè)的是條件獨(dú)立?！沧⒁鈼l件獨(dú)立和獨(dú)立是不一樣的〕建設(shè)形式化的模型表示：那么我們想要的是模型在訓(xùn)練數(shù)據(jù)上概率積能夠最大，即最大似然估計(jì)如下：注意這里是聯(lián)合概率分布積最大，說(shuō)明樸素貝葉斯是生成模型。求解得：最后一個(gè)式子是表示y=1的樣本數(shù)占全部樣本數(shù)的比例，前兩個(gè)表示在y=1或0的樣本中，特征Xj=1的比例。然而我們要求的是實(shí)際是求出分子即可，分母對(duì)y=1和y=0都一樣。當(dāng)然，樸素貝葉斯方法可以擴(kuò)展到x和y都有多個(gè)離散值的情況。對(duì)于特征是連續(xù)值的情況，我們也可以采用分段的方法來(lái)將連續(xù)值轉(zhuǎn)化為離散值。具體若何轉(zhuǎn)化能夠最優(yōu)，我們可以采用信息增益的度量方法來(lái)確定〔參見(jiàn)Mitchell的《機(jī)器學(xué)習(xí)》決策樹(shù)那一章〕。比方房子大小可以如下劃分成離散值：4拉普拉斯平滑樸素貝葉斯方法有個(gè)致命的缺點(diǎn)就是對(duì)數(shù)據(jù)稀疏問(wèn)題過(guò)于敏感。比方前面提到的郵件分類，現(xiàn)在新來(lái)了一封郵件，郵件標(biāo)題是“NIPScallforpapers〞。我們使用更大的網(wǎng)絡(luò)詞典〔詞的數(shù)目由5000變?yōu)?5000〕來(lái)分類，假設(shè)NIPS這個(gè)詞在字典中的位置是35000。然而NIPS這個(gè)詞沒(méi)有在訓(xùn)練數(shù)據(jù)中出現(xiàn)過(guò)，這封郵件第一次出現(xiàn)了NIPS。那我們算概率的時(shí)候如下：由于NIPS在以前的不管是垃圾郵件還是正常郵件都沒(méi)出現(xiàn)過(guò)，那么結(jié)果只能是0了。顯然最終的條件概率也是0。原因就是我們的特征概率條件獨(dú)立，使用的是相乘的方式來(lái)得到結(jié)果。為了解決這個(gè)問(wèn)題，我們打算給未出現(xiàn)特征值，賦予一個(gè)“小〞的值而不是0。具體平滑方法如下：假設(shè)離散型隨機(jī)變量z有{1,2,…,k}個(gè)值，我們用Φ??=p(z=i)來(lái)表示每個(gè)值的概率。假設(shè)有m個(gè)訓(xùn)練樣本中，z的觀察值是其中每一個(gè)觀察值對(duì)應(yīng)k個(gè)值中的一個(gè)。那么根據(jù)原來(lái)的估計(jì)方法可以得到說(shuō)白了就是z=j出現(xiàn)的比例。拉普拉斯平滑法將每個(gè)k值出現(xiàn)次數(shù)事先都加1，通俗講就是假設(shè)他們都出現(xiàn)過(guò)一次。那么修改后的表達(dá)式為：每個(gè)每個(gè)z=j的分子都加1，分母加k?？梢?jiàn)這個(gè)有點(diǎn)像NLP里面的加一平滑法，當(dāng)然還有n多平滑法了，這里不再詳述?；氐洁]件分類的問(wèn)題，修改后的公式為：5文本分類的事件模型回想一下我們剛剛使用的用于文本分類的樸素貝葉斯模型，這個(gè)模型稱作多值伯努利事件模型〔multi-variateBernoullieventmodel〕。在這個(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ù)不同。然后我們對(duì)于每個(gè)xi隨機(jī)從|V|個(gè)值中取一個(gè)，這樣就形成了一封郵件。這相當(dāng)于重復(fù)投擲|V|面的骰子，將觀察值記錄下來(lái)就形成了一封郵件。當(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è)詞在字典中的編號(hào)為。那么我們?nèi)匀话凑諛闼刎惾~斯的方法求得最大似然估計(jì)概率為解得，與以前的式子相比，分母多了個(gè)ni，分子由0/1變成了k。舉個(gè)例子：X1X2X3Y12-121-013203331假設(shè)郵件中只有a，b，c這三詞，他們?cè)谠~典的位置分別是1,2,3，前兩封郵件都只有2個(gè)詞，后兩封有3個(gè)詞。Y=1是垃圾郵件。那么，假設(shè)新來(lái)一封郵件為b，c那么特征表示為{2,3}。那么那么該郵件是垃圾郵件概率是0.6。注意這個(gè)公式與樸素貝葉斯的不同在于這里針對(duì)整體樣本求的????|??=1，而樸素貝葉斯里面針對(duì)每個(gè)特征求的??xj=1|??=1，而且這里的特征值維度是參差不齊的。這里如果假設(shè)拉普拉斯平滑，得到公式為：表示每個(gè)k值至少發(fā)生過(guò)一次。另外樸素貝葉斯雖然有時(shí)候不是最好的分類方法，但它簡(jiǎn)單有效，而且速度快。支持向量機(jī)〔上〕JerryLeadcsxulijie@gmail2011年3月12日星期六1簡(jiǎn)介支持向量機(jī)基本上是最好的有監(jiān)視學(xué)習(xí)算法了。最開(kāi)場(chǎng)接觸SVM是去年暑假的時(shí)候，教師要求交《統(tǒng)計(jì)學(xué)習(xí)理論》的報(bào)告，那時(shí)去網(wǎng)上下了一份入門(mén)教程，里面講的很通俗，當(dāng)時(shí)只是大致了解了一些相關(guān)概念。這次斯坦福提供的學(xué)習(xí)材料，讓我重新學(xué)習(xí)了一些SVM知識(shí)。我看很多正統(tǒng)的講法都是從VC維理論和構(gòu)造風(fēng)險(xiǎn)最小原理出發(fā)，然后引出SVM什么的，還有些資料上來(lái)就講分類超平面什么的。這份材料從前幾節(jié)講的logistic回歸出發(fā)，引出了SVM，既提醒了模型間的聯(lián)系，也讓人覺(jué)得過(guò)渡更自然。2重新審視logistic回歸Logistic回歸目的是從特征學(xué)習(xí)出一個(gè)0/1分類模型，而這個(gè)模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負(fù)無(wú)窮到正無(wú)窮。因此，使用logistic函數(shù)〔或稱作sigmoid函數(shù)〕將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于y=1的概率。形式化表示就是假設(shè)函數(shù)其中x是n維特征向量，函數(shù)g就是logistic函數(shù)。的圖像是可以看到，將無(wú)窮映射到了(0,1)。而假設(shè)函數(shù)就是特征屬于y=1的概率。當(dāng)我們要判別一個(gè)新來(lái)的特征屬于哪個(gè)類時(shí)，只需求???(x)，假設(shè)大于0.5就是y=1的類，反之屬于y=0類。再審視一下???(x)，發(fā)現(xiàn)???(x)只和??????有關(guān)，??????>0，那么???(x)>0.5，g(z)只不過(guò)是用來(lái)映射，真實(shí)的類別決定權(quán)還在??????。還有當(dāng)???????0時(shí)，???(x)=1，反之???(x)=0。如果我們只從??????出發(fā)，希望模型到達(dá)的目標(biāo)無(wú)非就是讓訓(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)槟菢拥脑?，要使得一局部點(diǎn)靠近中間線來(lái)?yè)Q取另外一局部點(diǎn)更加遠(yuǎn)離中間線。我想這就是支持向量機(jī)的思路和logistic回歸的不同點(diǎn)，一個(gè)考慮局部〔不關(guān)心已經(jīng)確定遠(yuǎn)離的點(diǎn)〕，一個(gè)考慮全局〔已經(jīng)遠(yuǎn)離的點(diǎn)可能通過(guò)調(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)。也就是說(shuō)除了y由y=0變?yōu)閥=-1，只是標(biāo)記不同外，與logistic回歸的形式化表示沒(méi)區(qū)別。再明確下假設(shè)函數(shù)???,??(x)=??(??????+b)上一節(jié)提到過(guò)我們只需考慮??????的正負(fù)問(wèn)題，而不用關(guān)心g(z)，因此我們這里將g(z)做一個(gè)簡(jiǎn)化，將其簡(jiǎn)單映射到y(tǒng)=-1和y=1上。映射關(guān)系如下：1, z≥0g(z)={ ?1, z<04函數(shù)間隔〔functionalmargin〕和幾何間隔〔geometricmargin〕給定一個(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)為特征是正例還是反例確實(shí)信度。繼續(xù)考慮w和b，如果同時(shí)加大w和b，比方在(??????(??)+??)前面乘個(gè)系數(shù)比方2，那么所有點(diǎn)的函數(shù)間隔都會(huì)增大二倍，這個(gè)對(duì)求解問(wèn)題來(lái)說(shuō)不應(yīng)該有影響，因?yàn)槲覀円蠼獾氖??????+??=0，同時(shí)擴(kuò)大w和b對(duì)結(jié)果是無(wú)影響的。這樣，我們?yōu)榱讼拗苭和b，可能需要參加歸一化條件，畢竟求解的目標(biāo)是確定唯一一個(gè)w和b，而不是多組線性相關(guān)的向量。這個(gè)歸一化一會(huì)再考慮。剛剛我們定義的函數(shù)間隔是針對(duì)某一個(gè)樣本的，現(xiàn)在我們定義全局樣本上的函數(shù)間隔說(shuō)白了就是在訓(xùn)練樣本上分類正例和負(fù)例確信度最小那個(gè)函數(shù)間隔。接下來(lái)定義幾何間隔，先看圖假設(shè)我們有了B點(diǎn)所在的??????+??=0分割面。任何其他一點(diǎn)，比方A到該面的距離以??(??)表示，假設(shè)B就是A在分割面上的投影。我們知道向量BA的方向是w〔分割面的梯度〕，單位向量是。A點(diǎn)是(??(??),??(??))，所以B點(diǎn)是x=〔利用初中的幾何知識(shí)〕，帶入??????+??=0得，進(jìn)一步得到??(??)實(shí)際上就是點(diǎn)到平面距離。再換種更加優(yōu)雅的寫(xiě)法：當(dāng)||w||=1時(shí)，不就是函數(shù)間隔嗎是的，前面提到的函數(shù)間隔歸一化結(jié)果就是幾何間隔。他們?yōu)槭裁磿?huì)一樣呢因?yàn)楹瘮?shù)間隔是我們定義的，在定義的時(shí)候就有幾何間隔的色彩。同樣，同時(shí)擴(kuò)大w和b，w擴(kuò)大幾倍，||w||就擴(kuò)大幾倍，結(jié)果無(wú)影響。同樣定義全局的幾何間隔5最優(yōu)間隔分類器〔optimalmarginclassifier〕回想前面我們提到我們的目標(biāo)是尋找一個(gè)超平面，使得離超平面對(duì)比近的點(diǎn)能有更大的間距。也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。形象的說(shuō)，我們將上面的圖看作是一張紙，我們要找一條折線，按照這條折線折疊后，離折線最近的點(diǎn)的間距比其他折線都要大。形式化表示為：這里用||w||=1規(guī)約w，使得??????+??是幾何間隔。到此，我們已經(jīng)將模型定義出來(lái)了。如果求得了w和b，那么來(lái)一個(gè)特征x，我們就能夠分類了，稱為最優(yōu)間隔分類器。接下的問(wèn)題就是若何求解w和b的問(wèn)題了。由于||w||=1不是凸函數(shù)，我們想先處理轉(zhuǎn)化一下，考慮幾何間隔和函數(shù)間隔的關(guān)系，，我們改寫(xiě)一下上面的式子：這時(shí)候其實(shí)我們求的最大值仍然是幾何間隔，只不過(guò)此時(shí)的w不受||w||=1的約束了。然而這個(gè)時(shí)候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒(méi)法直接代入優(yōu)化軟件里計(jì)算。我們還要改寫(xiě)。前面說(shuō)到同時(shí)擴(kuò)大w和b對(duì)結(jié)果沒(méi)有影響，但我們最后要求的仍然是w和b確實(shí)定值，不是他們的一組倍數(shù)值，因此，我們需要對(duì)???做一些限制，以保證我們解是唯一的。這里為了簡(jiǎn)便我們?nèi)???=1。這樣的意義是將全局的函數(shù)間隔定義為1，也即是將離超平面最近的點(diǎn)的距離定義為。由于求的最大值相當(dāng)于求的最小值，因此改寫(xiě)后結(jié)果為：這下好了，只有線性約束了，而且是個(gè)典型的二次規(guī)劃問(wèn)題〔目標(biāo)函數(shù)是自變量的二次函數(shù)〕。代入優(yōu)化軟件可解。到這里發(fā)現(xiàn)，這個(gè)講義雖然沒(méi)有像其他講義一樣先畫(huà)好圖，畫(huà)好分類超平面，在圖上標(biāo)示出間隔那么直觀，但每一步推導(dǎo)有理有據(jù)，依靠思路的流暢性來(lái)推導(dǎo)出目標(biāo)函數(shù)和約束。接下來(lái)介紹的是手工求解的方法了，一種更優(yōu)的求解方法。6拉格朗日對(duì)偶〔Lagrangeduality〕先拋開(kāi)上面的二次規(guī)劃問(wèn)題，先來(lái)看看存在等式約束的極值問(wèn)題求法，比方下面的最優(yōu)化問(wèn)題：目標(biāo)函數(shù)是f(w)，下面是等式約束。通常解法是引入拉格朗日算子，這里使用β來(lái)表示算子，得到拉格朗日公式為L(zhǎng)是等式約束的個(gè)數(shù)。然后分別對(duì)w和β求偏導(dǎo)，使得偏導(dǎo)數(shù)等于0，然后解出w和β??。至于為什么引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時(shí)才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關(guān)系?！矃⒖肌蹲顑?yōu)化與KKT條件》〕然后我們探討有不等式約束的極值問(wèn)題求法，問(wèn)題如下：我們定義一般化的拉格朗日公式這里的????和????都是拉格朗日算子。如果按這個(gè)公式求解，會(huì)出現(xiàn)問(wèn)題，因?yàn)槲覀兦蠼獾氖亲钚≈?，而這里的??i(??)≤0，我們可以將????調(diào)整成很大的正值，來(lái)使最后的函數(shù)結(jié)果是負(fù)無(wú)窮。因此我們需要排除這種情況，我們定義下面的函數(shù)：這里的P代表primal。假設(shè)??i(??)>0或者?i(??)≠0，那么我們總是可以調(diào)整????和????來(lái)使得????(w)有最大值為正無(wú)窮。而只有g(shù)和h滿足約束時(shí)，????(w)為f(w)。這個(gè)函數(shù)的精妙之處在于????≥0，而且求極大值。因此我們可以寫(xiě)作這樣我們?cè)瓉?lái)要求的minf(w)可以轉(zhuǎn)換成求min??????(w)了。我們使用p?來(lái)表示min??????(w)。如果直接求解，首先面對(duì)的是兩個(gè)參數(shù)，而????也是不等式約束，然后再在w上求最小值。這個(gè)過(guò)程不容易做，那么若何辦呢我們先考慮另外一個(gè)問(wèn)題D的意思是對(duì)偶， 將問(wèn)題轉(zhuǎn)化為先求拉格朗日關(guān)于w的最小值，將α和β看作是固定值。之后在 求最大值的話：這個(gè)問(wèn)題是原問(wèn)題的對(duì)偶問(wèn)題，相對(duì)于原問(wèn)題只是更換了min和max的順序，而一般更換順序的結(jié)果是MaxMin(X)<=MinMax(X)。然而在這里兩者相等。用???來(lái)表示對(duì)偶問(wèn)題如下：下面解釋在什么條件下兩者會(huì)等價(jià)。假設(shè)f和g都是凸函數(shù)，h是仿射的〔affine，〕。并且存在w使得對(duì)于所有的i，????(??)<0。在這種假設(shè)下，一定存在w?,???,???使得w?是原問(wèn)題的解，???,???是對(duì)偶問(wèn)題的解。還有另外，w?,???,???滿足庫(kù)恩-塔克條件〔Karush-Kuhn-Tucker,KKTcondition〕，該條件如下：所以如果w?,???,???滿足了庫(kù)恩-塔克條件，那么他們就是原問(wèn)題和對(duì)偶問(wèn)題的解。讓我們?cè)俅螌徱暪健?〕，這個(gè)條件稱作是KKTdualcomplementarity條件。這個(gè)條件隱含了如果???>0，那么????(???)=0。也就是說(shuō)，????(???)=0時(shí)，w處于可行域的邊界上，這時(shí)才是起作用的約束。而其他位于可行域內(nèi)部〔????(???)<0的〕點(diǎn)都是不起作用的約束，其???=0。這個(gè)KKT雙重補(bǔ)足條件會(huì)用來(lái)解釋支持向量和SMO的收斂測(cè)試。這局部?jī)?nèi)容思路對(duì)比凌亂，還需要先研究下《非線性規(guī)劃》中的約束極值問(wèn)題，再回頭看看。KKT的總體思想是認(rèn)為極值會(huì)在可行域邊界上取得，也就是不等式為0或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個(gè)元素要么是不等式為0的約束，要么是等式約束。對(duì)于在可行域邊界內(nèi)的點(diǎn)，對(duì)最優(yōu)解不起作用，因此前面的系數(shù)為0。7最優(yōu)間隔分類器〔optimalmarginclassifier〕重新回到SVM的優(yōu)化問(wèn)題：我們將約束條件改寫(xiě)為：從KKT條件得知只有函數(shù)間隔是1〔離超平面最近的點(diǎn)〕的線性約束式前面的系數(shù)????>0，也就是說(shuō)這些約束式????(w)=0，對(duì)于其他的不在線上的點(diǎn)(????(w)<0)，極值不會(huì)在他們所在的范圍內(nèi)取得，因此前面的系數(shù)????=0.注意每一個(gè)約束式實(shí)際就是一個(gè)訓(xùn)練樣本?？聪旅娴膱D：實(shí)線是最大間隔超平面，假設(shè)×號(hào)的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間隔是1的點(diǎn)，那么他們前面的系數(shù)????>0，其他點(diǎn)都是????=0。這三個(gè)點(diǎn)稱作支持向量。構(gòu)造拉格朗日函數(shù)如下：注意到這里只有????沒(méi)有????是因?yàn)樵瓎?wèn)題中沒(méi)有等式約束，只有不等式約束。下面我們按照對(duì)偶問(wèn)題的求解步驟來(lái)一步步進(jìn)展，首先求解的最小值，對(duì)于固定的????，的最小值只與w和b有關(guān)。對(duì)w和b分別求偏導(dǎo)數(shù)。并得到將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值〔目標(biāo)函數(shù)是凸函數(shù)〕化簡(jiǎn)過(guò)程如下：“倒數(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)為哪一項(xiàng)0，因此簡(jiǎn)化為這里我們將向量?jī)?nèi)積表示為表示為此時(shí)的拉格朗日函數(shù)只包含了變量????。然而我們求出了????才能得到w和b。接著是極大化的過(guò)程，前面提到過(guò)對(duì)偶問(wèn)題和原問(wèn)題滿足的幾個(gè)條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對(duì)于所有的i，????(??)<0。因此，一定存在w?,???使得w?是原問(wèn)題的解，???是對(duì)偶問(wèn)題的解。在這里，求????就是求???了。如果求出了????，根據(jù)即可求出w〔也是w?，原問(wèn)題的解〕。然后即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。關(guān)于上面的對(duì)偶問(wèn)題若何求解，將留給下一篇中的SMO算法來(lái)說(shuō)明。這里考慮另外一個(gè)問(wèn)題，由于前面求解中得到??w=∑??????(??)??(??)??=1我們通篇考慮問(wèn)題的出發(fā)點(diǎn)是??????+??，根據(jù)求解得到的????，我們代入前式得到也就是說(shuō)，以前新來(lái)的要分類的樣本首先根據(jù)w和b做一次線性運(yùn)算，然后看求的結(jié)果是大于0還是小于0,來(lái)判斷正例還是負(fù)例?，F(xiàn)在有了????，我們不需要求出w，只需將新來(lái)的樣本和訓(xùn)練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。那有人會(huì)說(shuō)，與前面所有的樣本都做運(yùn)算是不是太耗時(shí)了其實(shí)不然，我們從KKT條件中得到，只有支持向量的????>0，其他情況????=0。因此，我們只需求新來(lái)的樣本和支持向量的內(nèi)積，然后運(yùn)算即可。這種寫(xiě)法為下面要提到的核函數(shù)〔kernel〕做了很好的鋪墊。這是上篇，先寫(xiě)這么多了。支持向量機(jī)SVM〔下〕JerryLeadcsxulijie@gmail2011年3月17日星期四7核函數(shù)〔Kernels〕考慮我們最初在“線性回歸〞中提出的問(wèn)題，特征是房子的面積x，這里的x是實(shí)數(shù)，結(jié)果y是房子的價(jià)格。假設(shè)我們從樣本點(diǎn)的分布中看到x和y符合3次曲線，那么我們希望使用x的三次多項(xiàng)式來(lái)逼近這些樣本點(diǎn)。那么首先需要將特征x擴(kuò)展到三維，然后尋找特征和結(jié)果之間的模型。我們將這種特征變換稱作特征映射〔featuremapping〕。映射函數(shù)稱作，在這個(gè)例子中我們希望將得到的特征映射后的特征應(yīng)用于SVM分類，而不是最初的特征。這樣，我們需要將前面公式中的內(nèi)積從，映射到。至于為什么需要映射后的特征而不是最初的特征來(lái)參與計(jì)算，上面提到的〔為了更好地?cái)M合〕是其中一個(gè)原因，另外的一個(gè)重要原因是樣例可能存在線性不可分的情況，而將特征映射到高維空間后，往往就可分了?！苍凇稊?shù)據(jù)挖掘?qū)д摗稰ang-NingTan等人著的《支持向量機(jī)》那一章有個(gè)很好的例子說(shuō)明〕將核函數(shù)形式化定義，如果原始特征內(nèi)積是，映射后為，那么定義核函數(shù)〔Kernel〕為到這里，我們可以得出結(jié)論，如果要實(shí)現(xiàn)該節(jié)開(kāi)頭的效果，只需先計(jì)算，然后計(jì)算即可，然而這種計(jì)算方式是非常低效的。比方最初的特征是n維的，我們將其映射到維，然后再計(jì)算，這樣需要的時(shí)間。那么我們能不能想方法減少計(jì)算時(shí)間呢先看一個(gè)例子，假設(shè)x和z都是n維的，展開(kāi)后，得這個(gè)時(shí)候發(fā)現(xiàn)我們可以只計(jì)算原始特征x和z內(nèi)積的平方〔時(shí)間復(fù)雜度是O(n)〕，就等價(jià)與計(jì)算映射后特征的內(nèi)積。也就是說(shuō)我們不需要花時(shí)間了?，F(xiàn)在看一下映射函數(shù)〔n=3時(shí)〕，根據(jù)上面的公式，得到也就是說(shuō)核函數(shù)只能在選擇這樣的作為映射函數(shù)時(shí)才能夠等價(jià)于映射后特征的內(nèi)積。再看一個(gè)核函數(shù)對(duì)應(yīng)的映射函數(shù)〔n=3時(shí)〕是更一般地，核函數(shù) 對(duì)應(yīng)的映射后特征維度為?！策@個(gè)我一直沒(méi)有理解〕。由于計(jì)算的是內(nèi)積，我們可以想到IR中的余弦相似度，如果x和z向量夾角越小，那么核函數(shù)值越大，反之，越小。因此，核函數(shù)值是和的相似度。再看另外一個(gè)核函數(shù)這時(shí)，如果x和z很相近〔〕，那么核函數(shù)值為1，如果x和z相差很大〔〕，那么核函數(shù)值約等于0。由于這個(gè)函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(RadialBasisFunction簡(jiǎn)稱RBF)。它能夠把原始特征映射到無(wú)窮維。既然高斯核函數(shù)能夠?qū)Ρ葂和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。下面有張圖說(shuō)明在低維線性不可分時(shí)，映射到高維后就可分了，使用高斯核函數(shù)。來(lái)自EricXing的slides注意，使用核函數(shù)后，若何分類新來(lái)的樣本呢線性的時(shí)候我們使用SVM學(xué)習(xí)出w和b，新來(lái)樣本x的話，我們使用來(lái)判斷，如果值大于等于1，那么是正類，小于等于是負(fù)類。在兩者之間，認(rèn)為無(wú)法確定。如果使用了核函數(shù)后，就變成了，是否先要找到，然后再預(yù)測(cè)答案肯定不是了，找很麻煩，回想我們之前說(shuō)過(guò)的<??<??()??,??>??(??()??,??)8核函數(shù)有效性判定問(wèn)題：給定一個(gè)函數(shù)K，我們能否使用K來(lái)替代計(jì)算，也就說(shuō)，是否能夠找出一個(gè)，使得對(duì)于所有的x和z，都有比方給出了，是否能夠認(rèn)為K是一個(gè)有效的核函數(shù)。下面來(lái)解決這個(gè)問(wèn)題，給定m個(gè)訓(xùn)練樣本，每一個(gè)對(duì)應(yīng)一個(gè)特征向量。那么，我們可以將任意兩個(gè)和帶入K中，計(jì)算得到。I可以從1到m，j可以從1到m，這樣可以計(jì)算出m*m的核函數(shù)矩陣〔KernelMatrix〕。為了方便，我們將核函數(shù)矩陣和都使用K來(lái)表示。如果假設(shè)K是有效的核函數(shù)，那么根據(jù)核函數(shù)定義可見(jiàn)，矩陣K應(yīng)該是個(gè)對(duì)稱陣。讓我們得出一個(gè)更強(qiáng)的結(jié)論，首先使用符號(hào)來(lái)表示映射函數(shù)的第k維屬性值。那么對(duì)于任意向量z，得最后一步和前面計(jì)算時(shí)類似。從這個(gè)公式我們可以看出，如果K是個(gè)有效的核函數(shù)〔即和等價(jià)〕，那么，在訓(xùn)練集上得到的核函數(shù)矩陣K應(yīng)該是半正定的〔〕這樣我們得到一個(gè)核函數(shù)的必要條件：K是有效的核函數(shù)==>核函數(shù)矩陣K是對(duì)稱半正定的?？尚业氖?，這個(gè)條件也是充分的，由Mercer定理來(lái)表達(dá)。Mercer定理：如果函數(shù)K是上的映射〔也就是從兩個(gè)n維向量映射到實(shí)數(shù)域〕。那么如果K是一個(gè)有效核函數(shù)〔也稱為Mercer核函數(shù)〕，那么當(dāng)且僅當(dāng)對(duì)于訓(xùn)練樣例，其相應(yīng)的核函數(shù)矩陣是對(duì)稱半正定的。Mercer定理說(shuō)明為了證明K是有效的核函數(shù)，那么我們不用去尋找，而只需要在訓(xùn)練集上求出各個(gè)，然后判斷矩陣K是否是半正定〔使用左上角主子式大于等于零等方法〕即可。許多其他的教科書(shū)在Mercer定理證明過(guò)程中使用了范數(shù)和再生希爾伯特空間等概念，但在特征是n維的情況下，這里給出的證明是等價(jià)的。核函數(shù)不僅僅用在SVM上，但凡在一個(gè)模型后算法中出現(xiàn)了，我們都可以常使用去替換，這可能能夠很好地改善我們的算法。9規(guī)則化和不可分情況處理〔Regularizationandthenon-separablecase〕我們之前討論的情況都是建設(shè)在樣例線性可分的假設(shè)上，當(dāng)樣例線性不可分時(shí)，我們可以嘗試使用核函數(shù)來(lái)將特征映射到高維，這樣很可能就可分了。然而，映射后我們也不能100%保證可分。那若何辦呢，我們需要將模型進(jìn)展調(diào)整，以保證在不可分的情況下，也能夠盡可能地找出分隔超平面?？聪旅鎯蓮垐D：可以看到一個(gè)離群點(diǎn)〔可能是噪聲〕可以造成超平面的移動(dòng)，間隔縮小，可見(jiàn)以前的模型對(duì)噪聲非常敏感。再有甚者，如果離群點(diǎn)在另外一個(gè)類中，那么這時(shí)候就是線性不可分了。這時(shí)候我們應(yīng)該允許一些點(diǎn)游離并在在模型中違背限制條件〔函數(shù)間隔大于1〕。我們?cè)O(shè)計(jì)得到新的模型如下〔也稱軟間隔〕：引入非負(fù)參數(shù)????后〔稱為松弛變量〕，就允許某些樣本點(diǎn)的函數(shù)間隔小于1，即在最大間隔區(qū)間里面，或者函數(shù)間隔是負(fù)數(shù)，即樣本點(diǎn)在對(duì)方的區(qū)域中。而放松限制條件后，我們需要重新調(diào)整目標(biāo)函數(shù)，以對(duì)離群點(diǎn)進(jìn)展處分，目標(biāo)函數(shù)后面加上的C∑m??=1????就表示離群點(diǎn)越多，目標(biāo)函數(shù)值越大，而我們要求的是盡可能小的目標(biāo)函數(shù)值。這里的C是離群點(diǎn)的權(quán)重，C越大說(shuō)明離群點(diǎn)對(duì)目標(biāo)函數(shù)影響越大，也就是越不希望看到離群點(diǎn)。我們看到，目標(biāo)函數(shù)控制了離群點(diǎn)的數(shù)目和程度，使大局部樣本點(diǎn)仍然遵守限制條件。模型修改后，拉格朗日公式也要修改如下：這里的????和????都是拉格朗日乘子，回想我們?cè)诶窭嗜諏?duì)偶中提到的求法，先寫(xiě)出拉格朗日公式〔如上〕，然后將其看作是變量w和b的函數(shù)，分別對(duì)其求偏導(dǎo)，得到w和b的表達(dá)式。然后代入公式中，求帶入后公式的極大值。整個(gè)推導(dǎo)過(guò)程類似以前的模型，這里只寫(xiě)出最后結(jié)果如下：此時(shí)，我們發(fā)現(xiàn)沒(méi)有了參數(shù)????，與之前模型唯一不同在于????又多了????≤C的限制條件。需要提醒的是，b的求值公式也發(fā)生了改變，改變結(jié)果在SMO算法里面介紹。先看看KKT條件的變化：第一個(gè)式子說(shuō)明在兩條間隔線外的樣本點(diǎn)前面的系數(shù)為0，離群樣本點(diǎn)前面的系數(shù)為C，而支持向量〔也就是在超平面兩邊的最大間隔線上〕的樣本點(diǎn)前面系數(shù)在(0,C)上。通過(guò)KKT條件可知，某些在最大間隔線上的樣本點(diǎn)也不是支持向量，相反也可能是離群點(diǎn)。10坐標(biāo)上升法〔Coordinateascent〕在最后討論W(α)的求解之前，我們先看看坐標(biāo)上升法的基本原理。假設(shè)要求解下面的優(yōu)化問(wèn)題：這里W是α向量的函數(shù)。之前我們?cè)诨貧w中提到過(guò)兩種求最優(yōu)解的方法，一種是梯度下降法，另外一種是牛頓法?，F(xiàn)在我們?cè)僦v一種方法稱為坐標(biāo)上升法〔求解最小值問(wèn)題時(shí)，稱作坐標(biāo)下降法，原理一樣〕。方法過(guò)程：最里面語(yǔ)句的意思是固定除????之外的所有????(??≠)，這時(shí)W可看作只是關(guān)于????的函數(shù)，那么直接對(duì)????求導(dǎo)優(yōu)化即可。這里我們進(jìn)展最大化求導(dǎo)的順序i是從1到m，可以通過(guò)更改優(yōu)化順序來(lái)使W能夠更快地增加并收斂。如果W在內(nèi)循環(huán)中能夠很快地到達(dá)最優(yōu)，那么坐標(biāo)上升法會(huì)是一個(gè)很高效的求極值方法。下面通過(guò)一張圖來(lái)展示：橢圓代表了二次函數(shù)的各個(gè)等高線，變量數(shù)為2，起始坐標(biāo)是(2,-2)。圖中的直線式迭代優(yōu)化的路徑，可以看到每一步都會(huì)向最優(yōu)值前進(jìn)一步，而且前進(jìn)路線是平行于坐標(biāo)軸的，因?yàn)槊恳徊街粌?yōu)化一個(gè)變量。11SMO優(yōu)化算法〔Sequentialminimaloptimization〕SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對(duì)線性SVM和數(shù)據(jù)稀疏時(shí)性能更優(yōu)。關(guān)于SMO最好的資料就是他本人寫(xiě)的《SequentialMinimalOptimizationAFastAlgorithmforTrainingSupportVectorMachines》了。我拜讀了一下，下面先說(shuō)講義上對(duì)此方法的總結(jié)。首先回到我們前面一直懸而未解的問(wèn)題，對(duì)偶函數(shù)最后的優(yōu)化問(wèn)題：要解決的是在參數(shù)*??1,??2,…,????+上求最大值W的問(wèn)題，至于??(??)和y(??)都是數(shù)。C由我們預(yù)先設(shè)定，也是數(shù)。按照坐標(biāo)上升的思路，我們首先固定除??1以外的所有參數(shù)，然后在??1上求極值。等一下，這個(gè)思路有問(wèn)題，因?yàn)槿绻潭??1以外的所有參數(shù)，那么??1將不再是變量〔可以由其他值推出〕，因?yàn)閱?wèn)題中規(guī)定了因此，我們需要一次選取兩個(gè)參數(shù)做優(yōu)化，比方??1和??2，此時(shí)??2可以由??1和其他參數(shù)表示出來(lái)。這樣回帶到W中，W就只是關(guān)于??1的函數(shù)了，可解。這樣，SMO的主要步驟如下：意思是，第一步選取一對(duì)和，選取方法使用啟發(fā)式方法〔后面講〕。第二步，固定除和之外的其他參數(shù)，確定W極值條件下的，由表示。SMO之所以高效就是因?yàn)樵诠潭ㄆ渌麉?shù)后，對(duì)一個(gè)參數(shù)優(yōu)化過(guò)程很高效。下面討論具體方法：假設(shè)我們選取了初始值滿足了問(wèn)題中的約束條件。接下來(lái)，我們固定，這樣W就是和的函數(shù)。并且和滿足條件：由于都是固定值，因此為了方面，可將等式右邊標(biāo)記成實(shí)數(shù)值。當(dāng)和 異號(hào)時(shí)，也就是一個(gè)為1，一個(gè)為-1時(shí)，他們可以表示成一條直線，斜率為1。如以以下列圖：C??2C??2??1L1L2H2(ζ,0)(??,???ζ)??1???2=ζ??1???2=ζ(??ζ,??)?ζ)C 橫軸是，縱軸是，和既要在矩形方框內(nèi)，也要在直線上，因此，同理，當(dāng)和 同號(hào)時(shí)，，然后我們打算將用表示：然后反代入W中，得展開(kāi)后W可以表示成。其中a,b,c是固定值。這樣，通過(guò)對(duì)W進(jìn)展求導(dǎo)可以得到，然而要保證滿足 ，我們使用表示求導(dǎo)求出來(lái)的，然而最后的，要根據(jù)下面情況得到：這樣得到后，我們可以得到的新值。下面進(jìn)入Platt的文章，來(lái)找到啟發(fā)式搜索的方法和求b值的公式。這篇文章使用的符號(hào)表示有點(diǎn)不太一樣，不過(guò)實(shí)質(zhì)是一樣的，先來(lái)熟悉一下文章中符號(hào)的表示。文章中定義特征到結(jié)果的輸出函數(shù)為??()原始的優(yōu)化問(wèn)題為：求導(dǎo)得到：經(jīng)過(guò)對(duì)偶后為：s.t.s.t.這里與W函數(shù)是一樣的，只是符號(hào)求反后，變成求最小值了。和()是一樣的，都表示第i個(gè)樣本的輸出結(jié)果〔1或-1〕。經(jīng)過(guò)參加松弛變量后，模型修改為：由公式〔7〕代入〔1〕中可知，這個(gè)過(guò)程和之前對(duì)偶過(guò)程一樣。重新整理我們要求的問(wèn)題為：與之對(duì)應(yīng)的KKT條件為：這個(gè)KKT條件說(shuō)明，在兩條間隔線外面的點(diǎn)，對(duì)應(yīng)前面的系數(shù)????為0，在兩條間隔線里面的對(duì)應(yīng)????為C，在兩條間隔線上的對(duì)應(yīng)的系數(shù)????在0和C之間。將我們之前得到L和H重新拿過(guò)來(lái)：之前我們將問(wèn)題進(jìn)展到這里，然后說(shuō)將??1用??2表示后代入W中，這里將代入Ψ中，得其中這里的??1?和??2?代表某次迭代前的原始值，因此是常數(shù)，而??1和??2是變量，待求。公式〔24〕中的最后一項(xiàng)為哪一項(xiàng)常數(shù)。由于??1和??2滿足以下公式因?yàn)榈闹凳枪潭ㄖ?，在迭代前后不?huì)變。那么用s表示 ，上式兩邊乘以時(shí)，變?yōu)椋浩渲写搿?4〕中，得這時(shí)候只有是變量了，求導(dǎo)如果的二階導(dǎo)數(shù)大于0〔凹函數(shù)〕，那么一階導(dǎo)數(shù)為0時(shí)，就是極小值了。假設(shè)其二階導(dǎo)數(shù)為0〔一般成立〕，那么上式化簡(jiǎn)為：將w和v代入后，繼續(xù)化簡(jiǎn)推導(dǎo)，得〔推導(dǎo)了六七行推出來(lái)了〕我們使用來(lái)表示：通常情況下目標(biāo)函數(shù)是正定的，也就是說(shuō)，能夠在直線約束方向上求得最小值，并且。那么我們?cè)凇?0〕兩邊都除以可以得到這里我們使用表示優(yōu)化后的值，是迭代前的值， 。與之前提到的一樣不是最終迭代后的值，需要進(jìn)展約束：那么在特殊情況下，可能不為正，如果核函數(shù)K不滿足Mercer定理，那么目標(biāo)函數(shù)可能變得非正定，可能出現(xiàn)負(fù)值。即使K是有效的核函數(shù)，如果訓(xùn)練樣本中出現(xiàn)一樣的特征x，那么仍有可能為0。SMO算法在不為正值的情況下仍有效。為保證有效性，我們可以推導(dǎo)出就是的二階導(dǎo)數(shù)，，沒(méi)有極小值，最小值在邊緣處取到〔類比〕，時(shí)更是單調(diào)函數(shù)了，最小值也在邊緣處取得，而的邊緣就是L和H。這樣將和分別代入中即可求得的最小值，相應(yīng)的還是也可以知道了。具體計(jì)算公式如下：至此，迭代關(guān)系式除了b的推導(dǎo)式以外，都已經(jīng)推出。b每一步都要更新，因?yàn)榍懊娴腒KT條件指出了和的關(guān)系，而和b有關(guān)，在每一步計(jì)算出后，根據(jù)KKT條件來(lái)調(diào)整b。b的更新有幾種情況：來(lái)自羅林開(kāi)的ppt這里的界內(nèi)指，界上就是等于0或者C了。前面兩個(gè)的公式推導(dǎo)可以根據(jù)和對(duì)于有 的KKT條件推出。這樣全部參數(shù)的更新公式都已經(jīng)介紹完畢，附加一點(diǎn)，如果使用的是線性核函數(shù)，我們就可以繼續(xù)使用w了，這樣不用掃描整個(gè)樣本庫(kù)來(lái)作內(nèi)積了。w值的更新方法為：根據(jù)前面的公式推導(dǎo)出。12SMO中拉格朗日乘子的啟發(fā)式選擇方法終于到了最后一個(gè)問(wèn)題了，所謂的啟發(fā)式選擇方法主要思想是每次選擇拉格朗日乘子的時(shí)候，優(yōu)先選擇樣本前面系數(shù)0<????<??的????作優(yōu)化〔論文中稱為無(wú)界樣例〕，因?yàn)樵诮缟稀????為0或C〕的樣例對(duì)應(yīng)的系數(shù)????一般不會(huì)更改。這條啟發(fā)式搜索方法是選擇第一個(gè)拉格朗日乘子用的，比方前面的??2。那么這樣選擇的話，是否最后會(huì)收斂可幸的是Osuna定理告訴我們只要選擇出來(lái)的兩個(gè)????中有一個(gè)違背了KKT條件，那么目標(biāo)函數(shù)在一步迭代后值會(huì)減小。違背KKT條件不代表0<????<??，在界上也有可能會(huì)違背。是的，因此在給定初始值????=0后，先對(duì)所有樣例進(jìn)展循環(huán)，循環(huán)中碰到違背KKT條件的〔不管界上還是界內(nèi)〕都進(jìn)展迭代更新。等這輪過(guò)后，如果沒(méi)有收斂，第二輪就只針對(duì)0<????<??的樣例進(jìn)展迭代更新。在第一個(gè)乘子選擇后，第二個(gè)乘子也使用啟發(fā)式方法選擇，第二個(gè)乘子的迭代步長(zhǎng)大致正比于|E1?E2|，選擇第二個(gè)乘子能夠最大化|E1?E2|。即當(dāng)E1為正時(shí)選擇負(fù)的絕對(duì)值最大的E2，反之，選擇正值最大的E2。最后的收斂條件是在界內(nèi)〔0<????<??〕的樣例都能夠遵循KKT條件，且其對(duì)應(yīng)的????只在極小的范圍內(nèi)變動(dòng)。至于若何寫(xiě)具體的程序，請(qǐng)參考JohnC.Platt在論文中給出的偽代碼。13總結(jié)這份SVM的講義重點(diǎn)概括了SVM的基本概念和基本推導(dǎo)，中規(guī)中矩卻又讓人醍醐灌頂。起初讓我最頭疼的是拉格朗日對(duì)偶和SMO，后來(lái)逐漸明白拉格朗日對(duì)偶的重要作用是將w的計(jì)算提前并消除w，使得優(yōu)化函數(shù)變?yōu)槔窭嗜粘俗拥膯我粎?shù)優(yōu)化問(wèn)題。而SMO里面迭代公式的推導(dǎo)也著實(shí)讓我花費(fèi)了不少時(shí)間。比照這么復(fù)雜的推導(dǎo)過(guò)程，SVM的思想確實(shí)那么簡(jiǎn)單。它不再像logistic回歸一樣企圖去擬合樣本點(diǎn)〔中間加了一層sigmoid函數(shù)變換〕，而是就在樣本中去找分隔線，為了評(píng)判哪條分界限更好，引入了幾何間隔最大化的目標(biāo)。之后所有的推導(dǎo)都是去解決目標(biāo)函數(shù)的最優(yōu)化上了。在解決最優(yōu)化的過(guò)程中，發(fā)現(xiàn)了w可以由特征向量?jī)?nèi)積來(lái)表示，進(jìn)而發(fā)現(xiàn)了核函數(shù)，僅需要調(diào)整核函數(shù)就可以將特征進(jìn)展低維到高維的變換，在低維上進(jìn)展計(jì)算，實(shí)質(zhì)結(jié)果表現(xiàn)在高維上。由于并不是所有的樣本都可分，為了保證SVM的通用性，進(jìn)展了軟間隔的處理，導(dǎo)致的結(jié)果就是將優(yōu)化問(wèn)題變得更加復(fù)雜，然而驚奇的是松弛變量沒(méi)有出現(xiàn)在最后的目標(biāo)函數(shù)中。最后的優(yōu)化求解問(wèn)題，也被拉格朗日對(duì)偶和SMO算法化解，使SVM趨向于完美。另外，其他很多議題如SVM背后的學(xué)習(xí)理論、參數(shù)選擇問(wèn)題、二值分類到多值分類等等還沒(méi)有涉及到，以后有時(shí)間再學(xué)吧。其實(shí)樸素貝葉斯在分類二值分類問(wèn)題時(shí)，如果使用對(duì)數(shù)比，那么也算作線性分類器。規(guī)則化和模型選擇〔Regularizationandmodelselection〕JerryLeadcsxulijie@gmail2011年3月24日星期四1問(wèn)題模型選擇問(wèn)題：對(duì)于一個(gè)學(xué)習(xí)問(wèn)題，可以有多種模型選擇。比方要擬合一組樣本點(diǎn)，可以使用線性回歸(y=??????)，也可以用多項(xiàng)式回歸(y=??????1~??)。那么使用哪種模型好呢〔能夠在偏差和方差之間到達(dá)平衡最優(yōu)〕還有一類參數(shù)選擇問(wèn)題：如果我們想使用帶權(quán)值的回歸模型，那么若何選擇權(quán)重w公式里的參數(shù)τ形式化定義：假設(shè)可選的模型集合是Μ=*??1,??2,…,????+，比方我們想分類，那么SVM、logistic回歸、神經(jīng)網(wǎng)絡(luò)等模型都包含在M中。1穿插驗(yàn)證〔Crossvalidation〕我們的第一個(gè)任務(wù)就是要從M中選擇最好的模型。假設(shè)訓(xùn)練集使用S來(lái)表示如果我們想使用經(jīng)歷風(fēng)險(xiǎn)最小化來(lái)度量模型的好壞，那么我們可以這樣來(lái)選擇模型：使用S來(lái)訓(xùn)練每一個(gè)????，訓(xùn)練出參數(shù)后，也就可以得到假設(shè)函數(shù)????！脖确?，線性模型中得到????后，也就得到了假設(shè)函數(shù)???(x)=??????〕選擇錯(cuò)誤率最小的假設(shè)函數(shù)。遺憾的是這個(gè)算法不可行，比方我們需要擬合一些樣本點(diǎn)，使用高階的多項(xiàng)式回歸肯定比線性回歸錯(cuò)誤率要小，偏差小，但是方差卻很大，會(huì)過(guò)度擬合。因此，我們改良算法如下：從全部的訓(xùn)練數(shù)據(jù)S中隨機(jī)選擇70%的樣例作為訓(xùn)練集??train，剩余的30%作為測(cè)試集??CV。在??train上訓(xùn)練每一個(gè)????，得到假設(shè)函數(shù)???。在??CV上測(cè)試每一個(gè)???，得到相應(yīng)的經(jīng)歷錯(cuò)誤 。選擇具有最小經(jīng)歷錯(cuò)誤?????CV(???)的???作為最正確模型。這種方法稱為hold-outcrossvalidation或者稱為簡(jiǎn)單穿插驗(yàn)證。由于測(cè)試集是和訓(xùn)練集中是兩個(gè)世界的，因此我們可以認(rèn)為這里的經(jīng)歷錯(cuò)誤?????CV(???)接近于泛化錯(cuò)誤〔generalizationerror〕。這里測(cè)試集的比例一般占全部數(shù)據(jù)的1/4-1/3。30%是典型值。還可以對(duì)模型作改良，中選出最正確的模型????后，再在全部數(shù)據(jù)S上做一次訓(xùn)練，顯然訓(xùn)練數(shù)據(jù)越多，模型參數(shù)越準(zhǔn)確。簡(jiǎn)單穿插驗(yàn)證方法的弱點(diǎn)在于得到的最正確模型是在70%的訓(xùn)練數(shù)據(jù)上選出來(lái)的，不代表在全部訓(xùn)練數(shù)據(jù)上是最正確的。還有當(dāng)訓(xùn)練數(shù)據(jù)本來(lái)就很少時(shí)，再分出測(cè)試集后，訓(xùn)練數(shù)據(jù)就太少了。我們對(duì)簡(jiǎn)單穿插驗(yàn)證方法再做一次改良，如下：將全部訓(xùn)練集S分成k個(gè)不相交的子集，假設(shè)S中的訓(xùn)練樣例個(gè)數(shù)為m，那么每一個(gè)子集有m/k個(gè)訓(xùn)練樣例，相應(yīng)的子集稱作{??1,??2,…,????}。每次從模型集合M中拿出來(lái)一個(gè)????，然后在訓(xùn)練子集中選擇出k-1個(gè){??1,??2,?????1,????+1…,????}〔也就是每次只留下一個(gè)????〕，使用這k-1個(gè)子集訓(xùn)練????后，得到假設(shè)函數(shù)?????。最后使用剩下的一份????作測(cè)試，得到經(jīng)歷錯(cuò)誤?????j(???j)。由于我們每次留下一個(gè)????〔j從1到k〕，因此會(huì)得到k個(gè)經(jīng)歷錯(cuò)誤，那么對(duì)于一個(gè)????，它的經(jīng)歷錯(cuò)誤是這k個(gè)經(jīng)歷錯(cuò)誤的平均。選出平均經(jīng)歷錯(cuò)誤率最小的????，然后使用全部的S再做一次訓(xùn)練，得到最后的???。這個(gè)方法稱為k-foldcrossvalidation〔k-折疊穿插驗(yàn)證〕。說(shuō)白了，這個(gè)方法就是將簡(jiǎn)單穿插驗(yàn)證的測(cè)試集改為1/k，每個(gè)模型訓(xùn)練k次，測(cè)試k次，錯(cuò)誤率為k次的平均。一般講k取值為10。這樣數(shù)據(jù)稀疏時(shí)基本上也能進(jìn)展。顯然，缺點(diǎn)就是訓(xùn)練和測(cè)試次數(shù)過(guò)多。極端情況下，k可以取值為m，意味著每次留一個(gè)樣例做測(cè)試，這個(gè)稱為leave-one-outcrossvalidation。如果我們創(chuàng)造了一種新的學(xué)習(xí)模型或者算法，那么可以使用穿插驗(yàn)證來(lái)對(duì)模型進(jìn)展評(píng)價(jià)。比方在NLP中，我們將訓(xùn)練集中分出一局部訓(xùn)練，一局部做測(cè)試。2特征選擇〔Featureselection〕特征選擇嚴(yán)格來(lái)說(shuō)也是模型選擇中的一種。這里不去辨析他們的關(guān)系，重點(diǎn)說(shuō)明問(wèn)題。假設(shè)我們想對(duì)維度為n的樣本點(diǎn)進(jìn)展回歸，然而，n可能大多以至于遠(yuǎn)遠(yuǎn)大于訓(xùn)練樣例數(shù)m。但是我們感覺(jué)很多特征對(duì)于結(jié)果是無(wú)用的，想剔除n中的無(wú)用特征。n個(gè)特征就有2??種去除情況〔每個(gè)特征去或者保存〕，如果我們枚舉這些情況，然后利用穿插驗(yàn)證逐一考察在該情況下模型的錯(cuò)誤率，太不現(xiàn)實(shí)。因此需要一些啟發(fā)式搜索方法。第一種，前向搜索：初始化特征集F為空。掃描i從1到n，如果第i個(gè)特征不在F中，那么將特征i和F放在一起作為????〔即????=??∪*i+〕在只使用????中特征的情況下，利用穿插驗(yàn)證來(lái)得到????的錯(cuò)誤率。從上步中得到的n個(gè)????中選出錯(cuò)誤率最小的????，更新F為????。如果F中的特征數(shù)到達(dá)了n或者預(yù)設(shè)定的閾值〔如果有的話〕，那么輸出整個(gè)搜索過(guò)程中最好的F，沒(méi)到達(dá)轉(zhuǎn)到2前向搜索屬于wrappermodelfeatureselection。Wrapper這里指不斷地使用不同的特征集來(lái)測(cè)試學(xué)習(xí)算法。前向搜索說(shuō)白了就是每次增量地從剩余未選中的特征選出一個(gè)參加特征集中，待到達(dá)閾值或者n時(shí)，從所有的F中選出錯(cuò)誤率最小的。既然有增量加，那么也會(huì)有增量減，后者稱為后向搜索。先將F設(shè)置為{1,2,..,n}，然后每次刪除一個(gè)特征，并評(píng)價(jià)，直到到達(dá)閾值或者為空，然后選擇最正確的F。這兩種算法都可以工作，但是計(jì)算復(fù)雜度對(duì)比大。時(shí)間復(fù)雜度為O(n+(n?1)+(n?2)+?+1)=O(??2)。第二種，過(guò)濾特征選擇〔Filterfeatureselection〕：過(guò)濾特征選擇方法的想法是針對(duì)每一個(gè)特征????，i從1到n，計(jì)算????相對(duì)于類別標(biāo)簽y的信息量S(i)，得到n個(gè)結(jié)果，然后將n個(gè)S(i)按照從大到小排名，輸出前k個(gè)特征。顯然，這樣復(fù)雜度大大降低，為O(n)。那么關(guān)鍵問(wèn)題就是使用什么樣的方法來(lái)度量S(i)，我們的目標(biāo)是選取與y關(guān)聯(lián)最密切的一些????。而y和????都是有概率分布的。因此我們想到使用互信息來(lái)度量S(i)，對(duì)于????是離散值的情況更適用，不是離散值，將其轉(zhuǎn)變?yōu)殡x散值，方法在第一篇《回歸認(rèn)識(shí)》中已經(jīng)提到。互信息〔Mutualinformation〕公式：當(dāng)????是0/1離散值的時(shí)候，這個(gè)公式如上。很容易推廣到????是多個(gè)離散值的情況。這里的??(????,??)，??(????)和??(y)都是從訓(xùn)練集上得到的。假設(shè)問(wèn)這個(gè)MI公式若何得來(lái)，請(qǐng)看它的KL距離〔Kullback-Leibler〕表述：也就是說(shuō)，MI衡量的是????和y的獨(dú)立性。如果它倆獨(dú)立〔??(????,??)=??(????)??(y)〕，那么KL距離值為0，也就是說(shuō)????和y不相關(guān)了，可以去除????。相反，如果兩者密切相關(guān)，那么MI值會(huì)很大。在對(duì)MI進(jìn)展排名后，最后剩余的問(wèn)題就是若何選擇k值〔前k個(gè)????〕。我們繼續(xù)使用穿插驗(yàn)證的方法，將k從1掃描到n，取最大的F。不過(guò)這次復(fù)雜度是線性的了。比方，在使用樸素貝葉斯分類文本的時(shí)候，詞表長(zhǎng)度n很大。使用filter特征選擇方法，能夠增加分類器的精度。3貝葉斯統(tǒng)計(jì)和規(guī)則化〔Bayesianstatisticsandregularization〕題目有點(diǎn)繞，說(shuō)白了就是要找更好的估計(jì)方法來(lái)減少過(guò)度擬合情況的發(fā)生?；貞浺幌?，線性回歸中使用的估計(jì)方法是最小二乘法，logistic回歸是條件概率的最大似然估計(jì)，樸素貝葉斯是聯(lián)合概率的最大似然估計(jì)，SVM是二次規(guī)劃。以前我們使用的估計(jì)方法是最大似然估計(jì)〔比方在logistic回歸中使用的〕：注意這里的最大似然估計(jì)與維基百科中的表述:///wiki/%E6%9C%80%E5%A4%A7%E5%90%8E%E9%AA%8C%E6%A6%82%E7%8E%87有些出入，是因?yàn)榫S基百科只是將樣本〔觀察數(shù)據(jù)〕記為X，然后求P(X)的最大概率。然而，對(duì)于我們這里的樣本而言，分為特征x和類標(biāo)簽y。我們需要具體計(jì)算P(X)。在判別模型〔如logistic回歸〕中，我們對(duì)待P(X)=P(x,y)=P(y|x)P(x)，而P(x)與θ獨(dú)立無(wú)關(guān)，因此最后的argmaxP(X)由argmaxP(y|x)決定，也就是上式??ML。嚴(yán)格來(lái)講??ML并不等于樣本X的概率，只是P(X)決定于??ML，??ML最大化時(shí)P(X)也最大化。在生成模型，如樸素貝葉斯中，我們對(duì)待P(X)=P(y)P(x|y)，也就是在某個(gè)類標(biāo)簽y下出現(xiàn)特征x的概率與先驗(yàn)概率之積。而P(x|y)在x各個(gè)分量是條件獨(dú)立情況下可以以概率相乘方式計(jì)算出，這里基本沒(méi)有參數(shù)θ。因此最大似然估計(jì)直接估計(jì)P(x,y)即可，變成了聯(lián)合分布概率。在該上式中，我們視參數(shù)θ為未知的常數(shù)向量。我們的任務(wù)就是估計(jì)出未知的θ。從大范圍上說(shuō)，最大似然估計(jì)對(duì)待θ的視角稱為頻率學(xué)派〔frequentiststatistics〕，認(rèn)為θ不是隨機(jī)變量，只是一個(gè)未知的常量，因此我們沒(méi)有把p(??(??)|??(??);θ)寫(xiě)成p(??(??)|??(??),θ)。另一種視角稱為貝葉斯學(xué)派〔Bayesian〕，他們對(duì)待θ為隨機(jī)變量，值未知。既然θ為隨機(jī)變量，那么θ不同的值就有了不同的概率p(θ)〔稱為先驗(yàn)概率〕，代表我們對(duì)特定的θ的相信度。我們將訓(xùn)練集表示成S=*(??(??),??(??))+，i從1到m。我們首先需要求出θ的后驗(yàn)概率：這個(gè)公式的推導(dǎo)其實(shí)對(duì)比蹊蹺。第一步無(wú)可厚非，第二步中先看分子，分子中p(S|θ)最完整的表達(dá)方式是(∏m??=1??(??(??)|??(??),??))??(??(??))。由于在分母中也會(huì)出現(xiàn)??(??(??))，所以??(??(??))會(huì)被約掉。當(dāng)然作者壓根就沒(méi)有考慮??(??(??))，因?yàn)樗麑?duì)待P(S)的觀點(diǎn)就是x->y，而不是(x,y)。再來(lái)看分母，分母寫(xiě)成這種形式后，意思是對(duì)所有的??可能值做積分。括號(hào)里面的意思是∏m??=1??(??(??)|??(??))，然后將其展開(kāi)成分母的模樣，從宏觀上理解，就是在求每個(gè)樣例的概率時(shí)，先以一定的概率確定??，然后在??(??)和??的作用下再確定??(??)的概率。而如果讓我推導(dǎo)這個(gè)公式,我可能會(huì)這樣寫(xiě)分母p(S)=∫??(??(??|??)??(??))????，這樣推導(dǎo)出的結(jié)果是p(S)=∫??(∏m??=1??(??(??)|??(??),??))??(??)????。我不知道自己的想法對(duì)不對(duì)，分歧在于若何對(duì)待??，作者是為每個(gè)樣例都重新選定??，而我是對(duì)總體樣本選擇一個(gè)??。后記：我看了AndrewNG的教學(xué)視頻，發(fā)現(xiàn)視頻上的結(jié)果和講義上的不一致，應(yīng)該講義上由于筆誤寫(xiě)錯(cuò)了，正確的分母是p(S)=∫??(∏m??=1??(??(??)|??(??),??))??(??)????p(??(??)|??(??),θ)在不同的模型下計(jì)算方式不同。比方在貝葉斯logistic回歸中，其中，p的表現(xiàn)形式也就是伯努利分布了。在θ是隨機(jī)變量的情況下，如果新來(lái)一個(gè)樣例特征為x，那么為了預(yù)測(cè)y。我們可以使用下面的公式：p(θ|S)由前面的公式得到。假假設(shè)我們要求期望值的話，那么套用求期望的公式即可：大多