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

CS229機(jī)器學(xué)習(xí)(個人筆記)目錄(1)線性回歸、logistic回歸和一般回歸1(2)判別模型、生成模型與樸素貝葉斯方法10⑶支持向量機(jī)SVM(上)20(4)支持向量機(jī)SVM(下)32(5)規(guī)則化和模型選擇45(6)K-means聚類算法50(7)混合高斯模型和EM算法53(8)EM算法55⑼在線學(xué)習(xí)62(10)主成分分析65(11)獨(dú)立成分分析80(12)線性判別分析91(13)因子分析103(14)增強(qiáng)學(xué)習(xí)H4(15)典型關(guān)聯(lián)分析120(16)偏最小二乘法回歸129這里面的內(nèi)容是我在2011年上半年學(xué)習(xí)斯坦福大學(xué)《機(jī)器學(xué)習(xí)》課程的個人學(xué)習(xí)筆記，內(nèi)容主要來自AndrewNg教授的講義和學(xué)習(xí)視頻。另外也包含來自其他論文和其他學(xué)校講義的一些內(nèi)容。每章內(nèi)容主要按照個人學(xué)習(xí)時的思路總結(jié)得到。由于是個人筆記，里面表述錯誤、公式錯誤、理解錯誤、筆誤都會存在。更重要的是我是初學(xué)者，千萬不要認(rèn)為里面的思路都正確。如果有疑問的地方，請第一時間參考AndrewNg教授的講義原文和視頻，再有疑問的地方可以找一些大牛問問。博客上很多網(wǎng)友提出的問題，我難以回答，因為我水平確實有限，更深層次的內(nèi)容最好找相關(guān)大牛咨詢和相關(guān)論文研讀。如果有網(wǎng)友想在我這個版本基礎(chǔ)上再添加自己的筆記，可以發(fā)送Email給我，我提供原始的worddocx版本。另，本人目前在科苑軟件所讀研，馬上三年了，方向是分布式計算，主要偏大數(shù)據(jù)分布式處理，平時主要玩Hadoop、Pig、Hive>Mahout、NoSQL啥的，關(guān)注系統(tǒng)方面和數(shù)據(jù)庫方面的會議。希望大家多多交流，以后會往博客上放這些內(nèi)容，機(jī)器學(xué)習(xí)會放的少了。Anyway,祝大家學(xué)習(xí)進(jìn)步、事業(yè)成功!對回歸方法的認(rèn)識JerryLead2011年2月27日1摘要本報告是在學(xué)習(xí)斯坦福大學(xué)機(jī)器學(xué)習(xí)課程前四節(jié)加上配套的講義后的總結(jié)與認(rèn)識。前四節(jié)主要講述了回歸問題，屬于有監(jiān)督學(xué)習(xí)中的一種方法。該方法的核心思想是從離散的統(tǒng)計數(shù)據(jù)中得到數(shù)學(xué)模型，然后將該數(shù)學(xué)模型用于預(yù)測或者分類。該方法處理的數(shù)據(jù)可以是多維的。講義最初介紹了一個基本問題，然后引出了線性回歸的解決方法，然后針對誤差問題做了概率解釋。2問題引入假設(shè)有一個房屋銷售的數(shù)據(jù)如下：面積(m9)銷售價錢(萬元)12325015032087160102220這個表類似于北京5環(huán)左右的房屋價錢，我們可以做出一個圖，x軸是房屋的面積。y軸是房屋的售價，如下：如果來了一個新的面積，假設(shè)在銷售價錢的記錄中沒有的，我們怎么辦呢？我們可以用一條曲線去盡量準(zhǔn)的擬合這些數(shù)據(jù)，然后如果有新的輸入過來，我們可以在將曲線上這個點(diǎn)對應(yīng)的值返回。如果用一條直線去擬合，可能是下面的樣子：綠色的點(diǎn)就是我們想要預(yù)測的點(diǎn)。首先給出一些概念和常用的符號。房屋銷售記錄表：訓(xùn)練集(trainingset)或者訓(xùn)練數(shù)據(jù)(trainingdata),是我們流程中的輸入數(shù)據(jù)，一股稱為x房屋銷售價錢：輸出數(shù)據(jù)，一般稱為y擬合的函數(shù)(或者稱為假設(shè)或者模型)：一般寫做y=h(x)訓(xùn)練數(shù)據(jù)的條目數(shù)(drainingset),：一條訓(xùn)練數(shù)據(jù)是由一對輸入數(shù)據(jù)和輸出數(shù)據(jù)組成的輸入數(shù)據(jù)的維度n(特征的個數(shù)，#features)這個例子的特征是兩維的，結(jié)果是一維的。然而回歸方法能夠解決特征多維，結(jié)果是一維多離散值或一維連續(xù)值的問題。3學(xué)習(xí)過程下面是一個典型的機(jī)器學(xué)習(xí)的過程，首先給出一個輸入數(shù)據(jù)，我們的算法會通過一系列的過程得到一個估計的函數(shù)，這個函數(shù)有能力對沒有見過的新數(shù)據(jù)給出一個新的估計，也被稱為構(gòu)建一個模型。就如同上面的線性回歸函數(shù)。輸入數(shù)據(jù)機(jī)」學(xué)習(xí)方法I新盤書|一|估計)數(shù)F]—貨信計I4線性回歸線性回歸假設(shè)特征和結(jié)果滿足線性關(guān)系。其實線性關(guān)系的表達(dá)能力非常強(qiáng)大，每個特征對結(jié)果的影響強(qiáng)弱可以有前面的參數(shù)體現(xiàn)，而且每個特征變量可以首先映射到一個函數(shù)，然后再參與線性計算。這樣就可以表達(dá)特征與結(jié)果之間的非線性關(guān)系.我們用XI,X2..Xn去描述feature里面的分量，比如xl=房間的面積，x2=房間的朝向，等等,我們可以做出一個估計函數(shù)：h[x}-每(x)=00+可為6在這J曲為參數(shù)，在這的意思是調(diào)整feature中每個分量的影響力，就是到底是房屋的面積更重要還是房屋的地段更重要。為了如果我們令X0=1,就可以用向量的方式來表示了：=8,X我們程序也需要一個機(jī)制去評估我們e是否比較好，所以說需要對我們做出的h函數(shù)進(jìn)行評估，一般這個函數(shù)稱為損失函數(shù)(lossfunction)或者錯誤函數(shù)(errorfunction),描述h函數(shù)不好的程度，在下面，我們稱這個函數(shù)為J函數(shù)在這兒我們可以做出下面的一個錯誤函數(shù)：1m?/(6)=彳2(①(丹)-嚴(yán))2minX0這個錯誤估計函數(shù)是去對Mi)的估計值與真實值y(i)差的平方和作為錯誤估計函數(shù)，前面乘上的1/2是為了在求導(dǎo)的時候，這個系數(shù)就不見了。至于為何選擇平方和作為錯誤估計函數(shù)，講義后面從概率分布的角度講解了該公式的來源。如何調(diào)整0以使得J⑻取得最小值有很多方法，其中有最小二乘法（minsquare）,是一種完全是數(shù)學(xué)描述的方法，和梯度下降法.5梯度下降法在選定線性回歸模型后,只需要確定參數(shù)9,就可以將模型用來預(yù)測。然而。需要在J⑹最小的情況下才能確定。因此問題歸結(jié)為求極小值問題，使用梯度下降法.梯度下降法最大的問題是求得有可能是全局極小值，這與初始點(diǎn)的選取有關(guān)。梯度下降法是按下面的流程進(jìn)行的：1）首先對e賦值，這個值可以是隨機(jī)的，也可以讓e是一個全零的向量。2）改變e的值，使得J（O）按梯度下降的方向進(jìn)行減少。梯度方向由J（e）對0的偏導(dǎo)數(shù)確定，由于求的是極小值，因此梯度方向是偏導(dǎo)數(shù)的反方向。結(jié)果為Oj:=Oj+a（y⑴-hg（工（”））工，迭代更新的方式有兩種，一種是批梯度下降，也就是對全部的訓(xùn)練數(shù)據(jù)求得誤差后再對0進(jìn)行更新，另外一種是增量梯度下降，每掃描一步都要對9進(jìn)行更新。前一種方法能夠不斷收斂，后一種方法結(jié)果可能不斷在收斂處徘徊。一般來說，梯度下降法收斂速度還是比較慢的。另一種直接計算結(jié)果的方法是最小二乘法。6最小二乘法將訓(xùn)練特征表示為X矩陣，結(jié)果表示成y向量，仍然是線性回歸模型，誤差函數(shù)不變。那么e可以直接由下面公式得出

0=(XTX)-lXTy.但此方法要求x是列滿秩的，而且求矩陣的逆比較慢。7選用誤差函數(shù)為平方和的概率解釋假設(shè)根據(jù)特征的預(yù)測結(jié)果與實際結(jié)果有誤差加），那么預(yù)測結(jié)果和真實結(jié)果y（i）滿足下式:一般來講，誤差滿足平均值為0的高斯分布，也就是正態(tài)分布。那么x和y的條件概率也就是exp（嚴(yán)一尹工⑴）2exp（嚴(yán)一尹工⑴）2這樣就估計了一條樣本的結(jié)果概率，然而我們期待的是模型能夠在全部樣本上預(yù)測最準(zhǔn)，也就是概率積最大。這個概率積成為最大似然估計。我們希望在最大似然估計得到最大值時確定9o那么需要對最大似然估計公式求導(dǎo)，求導(dǎo)結(jié)果既是t=l這就解釋了為何誤差函數(shù)要使用平方和。當(dāng)然推導(dǎo)過程中也做了一些假定，但這個假定符合客觀規(guī)律。8帶權(quán)重的線'性回歸上面提到的線性回歸的誤差函數(shù)里系統(tǒng)都是1,沒有權(quán)重。帶權(quán)重的線性回歸加入了權(quán)重信息?；炯僭O(shè)是Fit0tominimize ⑴—僅i?⑴產(chǎn).Output尹jt.其中假設(shè)W。）符合公式其中X是要預(yù)測的特征，這樣假設(shè)的道理是離X越近的樣本權(quán)重越大，越遠(yuǎn)的影響越小。這個公式與高斯分布類似，但不一樣，因為W。）不是隨機(jī)變量。此方法成為非參數(shù)學(xué)習(xí)算法，因為誤差函數(shù)隨著預(yù)測值的不同而不同，這樣0無法事先確定，預(yù)測一次需要臨時計算，感覺類似KNN。9分類和對數(shù)回歸一般來說，回歸不用在分類問題上，因為回歸是連續(xù)型模型，而且受噪聲影響比較大.如果非要應(yīng)用進(jìn)入，可以使用對數(shù)回歸。對數(shù)回歸本質(zhì)上是線性回歸，只是在特征到結(jié)果的映射中加入了一層函數(shù)映射，即先把特征線性求和，然后使用函數(shù)g（z）將最為假設(shè)函數(shù)來預(yù)測。g（z）可以將連續(xù)值映射到0和1上。又?jǐn)\回歸的假設(shè)函數(shù)如下，線性回歸假設(shè)函數(shù)只是er。d（力=§（尹］）=1,1+e"工,、10（二）~~'l+e-z對數(shù)回歸用來分類0/1問題，也就是預(yù)測結(jié)果屬于o或者1的二值分類問題。這里假設(shè)了二值滿足伯努利分布，也就是P（y=1|］；。）=he（x）P（y=0|x;0）=1—ho［x}當(dāng)然假設(shè)它滿足泊松分布、指數(shù)分布等等也可以，只是比較復(fù)雜，后面會提到線性回歸的一般形式。與第7節(jié)一樣，仍然求的是最大似然估計，然后求導(dǎo)，得到迭代公式結(jié)果為0j:=%+a -ha（工⑴））工，可以看到與線性回歸類似,只是換成了招（"）），而九八近））實際上就是。7%。）經(jīng)過g（Z）映射過來的。10牛頓法來解最大似然估計第7和第9節(jié)使用的解最大似然估計的方法都是求導(dǎo)迭代的方法，這里介紹了牛頓下降法，使結(jié)果能夠快速的收斂。當(dāng)要求解f（e）=o時，如果f可導(dǎo)，那么可以通過迭代公式』一黑.-> 來迭代求解最小值。當(dāng)應(yīng)用于求解最大似然估計的最大值時，變成求解2'（。）=0的問題.那么迭代公式寫作￡"伊），當(dāng)e是向量時，牛頓法可以使用下面式子表示0:=0-"7▽屋（6）._必⑻nii~其中 是nxn的Hessian矩陣。牛頓法收斂速度雖然很快，但求Hessian矩陣的逆的時候比較耗費(fèi)時間。當(dāng)初始點(diǎn)X0靠近極小值X時，牛頓法的收斂速度是最快的。但是當(dāng)X0遠(yuǎn)離極小值時,牛頓法可能不收斂，甚至連下降都保證不了。原因是迭代點(diǎn)Xk+1不一定是目標(biāo)函數(shù)f在牛頓方向上的極小點(diǎn)。11—音殳線'性模型之所以宓寸數(shù)回歸時使用q[z}= “'14-e~z的公式是由一套理論作支持的。這個理論便是一般線性模型。首先，如果一個概率分布可以表示成P?；〃)=b⑻exp(//7T(y)-a(〃))時，那么這個概率分布可以稱作是指數(shù)分布。伯努利分布，高斯分布，泊松分布，貝塔分布，狄特里特分布都屬于指數(shù)分布.在對數(shù)回歸時采用的是伯努利分布，伯努利分布的概率可以表示成P?；。)=燃1-樹——exp(ylog。+(1-y)log(l-</>))=exp((log g+log(l.其中n=bg(。/(i-。))?得到①= +en這就解釋了對數(shù)回歸時為了要用這個函數(shù)。一般線性模型的要點(diǎn)是ylx；e滿足一個以“為參數(shù)的指數(shù)分布，那么可以求得n的表達(dá)式。2)給定x,我們的目標(biāo)是要確定T(y),大多數(shù)情況下T(y)=y,那么我們實際上要確定的是h(x),而h(x)=Efy|x],(在對數(shù)回歸中期望值是小，因此h是e;在線性回歸中期望值是日，而高斯分布中n=M,因此線性回歸中h=”xl3)n=f)Tx12Softmax回歸最后舉了一個利用一般線性模型的例子。假設(shè)預(yù)測值v有k種可能，即y曰L2，…,k[比如k=3時，可以看作是要將一封未知郵件分為垃圾郵件、個人郵件還是工作郵件這三類。

定義6=p（y='；。）那么=1這樣p（y=k；，）=1一￡凄；機(jī)即式子左邊可以有其他的概率表示，因此可以當(dāng)做是k-i維的問題。T（y）這時候一組k-1維的向量,不再是y。即T（y）要給出y=i（i從1到k-1）的概率應(yīng)用于一般線性模型應(yīng)用于一般線性模型pSMpSM=碎7曲7…姆1)=姐―。姆E}…林-工富“E}=姆加0/(加…太￡匕5汕=cxp((T(t/))ilog(Ol)+-log(02)+…+(1-￡普(川))。1。虱姐)=exp((T(t/))ilog(0i/以)+(T(y))2log(曲/以)+…+(T(j/))fc_llog(0i/0k)+log(娟)=b(y)exp(rjl=b(y)exp(rjlT(y)-a(T1))那么—*)

log(d—*)

log(d2/0fc)

T]= . ,log(0l/，k).a(〃)=-bg3QWy)=l 最后求得y=i時y=i時p[y=p[y=，|工;6)仇e3Tx求得期望值he(x)=E[T(y)|x;0]=1)=匕l(fā)[y=k-1]M02Ok-1exp(0.T)￡%cx；.(3)exp(。彳6_2內(nèi)叼呵工)?p(皈巴

.￡，=15(耳工)_那么就建立了假設(shè)函數(shù)，最后就獲得了最大似然估計'⑻=￡logp(y")l”;&)1=1mk/押工⑹=E^nL^r對該公式可以使用i=l1=1\2-,j=le1 /對該公式可以使用梯度下降或者牛頓法迭代求解。解決了多值模型建立與預(yù)測問題。學(xué)習(xí)總結(jié)

該講義組織結(jié)構(gòu)清晰，思路獨(dú)特，講原因，也講推導(dǎo)。可貴的是講出了問題的基本解決思路和擴(kuò)展思路，更重要的是講出了為什么要使用相關(guān)方法以及問題根源。在看似具體的解題思路中能引出更為抽象的一般解題思路，理論化水平很高。該方法可以用在對數(shù)據(jù)多維分析和多值預(yù)測上，更適用于數(shù)據(jù)背后蘊(yùn)含某種概率模型的情景。判別模型、生成模型與樸素貝葉斯方法JerryLead2011年3月5日星期六1判別模型與生成模型上篇報告中提到的回歸模型是判別模型，也就是根據(jù)特征值來求結(jié)果的概率。形式化表示為p(y|x；0),在參數(shù)。確定的情況下，求解條件概率pO\x)0通俗的解釋為在給定特征后預(yù)測結(jié)果出現(xiàn)的概率.比如說要確定一只羊是山羊還是綿羊，用判別模型的方法是先從歷史數(shù)據(jù)中學(xué)習(xí)到模型，然后通過提取這只羊的特征來預(yù)測出這只羊是山羊的概率，是綿羊的概率。換一種思路，我們可以根據(jù)山羊的特征首先學(xué)習(xí)出一個山羊模型，然后根據(jù)綿羊的特征學(xué)習(xí)出一個綿羊模型。然后從這只羊中提取特征，放到山羊模型中看概率是多少，再放到綿羊模型中看概率是多少，哪個大就是哪個.形式化表示為求p(x|y)(也包括p(y)),y是模型結(jié)果，x是特征。利用貝葉斯公式發(fā)現(xiàn)兩個模型的統(tǒng)一性：p(Ny)p(y)

p(工)由于我們關(guān)注的是y的離散值結(jié)果中哪個概率大(比如山羊概率和綿羊概率哪個大),而并不是關(guān)心具體的概率，因此上式改寫為：argmaxp(y|z)argmaxyp(^\y)p(y)

p(工)argmaxp(y|z)argmaxyp(^\y)p(y)

p(工)argm產(chǎn)p(z|y)p?).其中P(X|y)稱為后驗概率，P(y)稱為先驗概率。由p(x|y)*p(y)=p(x,y),因此有時稱判別模型求的是條件概率，生成模型求的是聯(lián)合概率。常見的判別模型有線性回歸、對數(shù)回歸、線性判別分析、支持向量機(jī)、boosting,條件隨機(jī)場、神經(jīng)網(wǎng)絡(luò)等。常見的生產(chǎn)模型有隱馬爾科夫模型、樸素貝葉斯模型、高斯混合模型、LDA、RestrictedBoltzmannMachine等。這篇博客較為詳細(xì)地介紹了兩個模型：2高斯判別分析(Gaussiandiscriminantanalysis)1)多值正態(tài)分布多變量正態(tài)分布描述的是n維隨機(jī)變量的分布情況，這里的p變成了向量，。也變成了矩陣工寫作N@,E)。假設(shè)有n個隨機(jī)變量X1,X2，…，Xna口的第i個分量是E(X,),而卻=Var(X,),詞=Cov(X；,%；).概率密度函數(shù)如下：其中圜(2介/2因1/2CXP(一近-"丁(工-〃))其中圜是E的行列式，工是協(xié)方差矩陣，而且是對稱半正定的。當(dāng)H是二維的時候可以如下圖表示：當(dāng)H是二維的時候可以如下圖表示：… 其中H決定中心位置"決定投影橢圓的朝向和大小。如下圖：10。 10。 1 0.501' 0.5 110.8'0.8 1 ,對應(yīng)的E都不同。2）模型分析與應(yīng)用如果輸入特征x是連續(xù)型隨機(jī)變量，那么可以使用高斯判別分析模型來確定p(x|y)o模型如下：y2Bernoulli(0)x\y=0~"("o,E)11y=1zA17/Z1,E)輸出結(jié)果服從伯努利分布，在給定模型下特征符合多值高斯分布。通俗地講，在山羊模型下，它的胡須長度，角大小，毛長度等連續(xù)型變量符合高斯分布，他們組成的特征向量符合多值高斯分布。這樣，可以給出概率密度函數(shù)：P（y）=P（工以=°）=西金#（工p（Hy=i）=時磊rxp（小一〃j—出））最大似然估計如下：

￡（0,〃o，"i,E）=logIJP（工⑴,嚴(yán);以 ,）f=lm=1。811以1"）1嚴(yán)；"0.〃1,￡）「（，”；0）.i=l注意這里的參數(shù)有兩個n,表示在不同的結(jié)果模型下，特征均值不同，但我們假設(shè)協(xié)方差相同。反映在圖上就是不同模型中心位置不同，但形狀相同。這樣就可以用直線來進(jìn)行分隔判別。0=〃0=〃0==E=5畢{嚴(yán)=D￡乙1{*=。}￡隨1{/=1}5￡（工⑴-〃*）（/）-冉⑴）71=1中是訓(xùn)練樣本中結(jié)果y=l占有的比例.M是y=o的樣本中特征均值。m是y=i的樣本中特征均值。E是樣本特征方差均值。如前面所述,在圖上表示為：

直線兩邊的y值不同，但協(xié)方差矩陣相同，因此形狀相同。M不同，因此位置不同。3)高斯判別分析(GDA)與logistic回歸的關(guān)系將GDA用條件概率方式來表述的話，如下：p?=Xy是Xy是X的函數(shù)，其中都是參數(shù)。進(jìn)一步推導(dǎo)出MynlWOA,"。,"】)』仃焉二兩,這里的。是 ''?的函數(shù)。這個形式就是logistic回歸的形式。也就是說如果p(x|y)符合多元高斯分布，那么p(y|x)符合logistic回歸模型。反之,不成立。為什么反過來不成立呢？因為GDA有著更強(qiáng)的假設(shè)條件和約束。如果認(rèn)定訓(xùn)練數(shù)據(jù)滿足多元高斯分布，那么GDA能夠在訓(xùn)練集上是最好的模型。然而，我們往往事先不知道訓(xùn)練數(shù)據(jù)滿足什么樣的分布，不能做很強(qiáng)的假設(shè)。Logistic回歸的條件假設(shè)要弱于GDA,因此更多的時候采用logistic回歸的方法。例如，訓(xùn)練數(shù)據(jù)滿足泊松分布，”"=0~Poisson(Ao)

"W=1~Poisson(%),那么p(y?X)也是logistic回歸的。這個時候如果采用GDA,那么效果會比較差，因為訓(xùn)練數(shù)據(jù)特征的分布不是多元高斯分布，而是泊松分布。這也是logistic回歸用的更多的原因。3樸素貝葉斯模型在GDA中，我們要求特征向量x是連續(xù)實數(shù)向量。如果x是離散值的話，可以考慮采用樸素貝葉斯的分類方法。假如要分類垃圾郵件和正常郵件。分類郵件是文本分類的一種應(yīng)用。假設(shè)采用最簡單的特征描述方法，首先找一部英語詞典，將里面的單詞全部列出來。然后將每封郵件表示成一個向量，向量中每一維都是字典中的一個詞的0/1值，1表示該詞在郵件中出現(xiàn)，0表示未出現(xiàn)。比如一封郵件中出現(xiàn)了"a"和"buy",沒有出現(xiàn)"aardvark"、"aardwolf”和"zygmurgy”,那么可以形式化表示為：00100010aardvarkaardwolfbuyzygmurgy假設(shè)字典中總共有5000個詞，那么x是5000維的。這時候如果要建立多項式分布模型多項式分布(multinomialdistribution)某隨機(jī)實驗如果有k個可能結(jié)局Al,A2,...,Ak,它們的概率分布分別是Pl,P2,...,Pk,那么在N次采樣的總結(jié)果中，A1出現(xiàn)nl次，A2出現(xiàn)n2次，的出現(xiàn)概率P相卜面公式：(Xi代表出現(xiàn)ni次)-,Ak出現(xiàn)nk次的這種事件,—屋J…產(chǎn)尸(X1=-…，Xk=Tk)='"21Pkwhen￡3ii=notherwise.對應(yīng)到上面的問題上來，把每封郵件當(dāng)做一次隨機(jī)試驗，那么結(jié)果的可能性有25。。。種。意味著pi有25。。。個，參數(shù)太多，不可能用來建模。換種思路，我們要求的是p(y|x)，根據(jù)生成模型定義我們可以求p(x|y)和p(y)0假設(shè)x中的特征是條件獨(dú)立的。這個稱作樸素貝葉斯假設(shè)。如果一封郵件是垃圾郵件(y=l),且這封郵件出現(xiàn)詞“buy”與這封郵件是否出現(xiàn)"price"無關(guān)，那么"buy"和"price”之間是條件獨(dú)立的。形式化表示為,(如果給定Z的情況下，X和丫條件獨(dú)立)：P(X|Z)=P(X|Y,Z)也可以表示為：P(X,Y|Z)=P(X|Z)P(Y|Z)回到問題中p3，..250000⑼=pCnW)p(g|y，x\)p(工3?,1i,辦)…p(^oooo\y,工1,???，工」制)=P(皿MP(12?)P(13?)…P(N5000o|y)n=Ijp(四?)這個與NLP中的n元語法模型有點(diǎn)類似，這里相當(dāng)于unigram.這里我們發(fā)現(xiàn)樸素貝葉斯假設(shè)是約束性很強(qiáng)的假設(shè)，"buy”從通常上講與"price"是有關(guān)系，我們這里假設(shè)的是條件獨(dú)立。(注意條件獨(dú)立和獨(dú)立是不一樣的)建立形式化的模型表示：0tiy=i=p(陽=i|y=1)0iiy=o=p?=01y=1)%=p(y=1)那么我們想要的是模型在訓(xùn)練數(shù)據(jù)上概率積能夠最大，即最大似然估計如下：m￡(。1/,廂=0,廂=1)=口以工⑴,嚴(yán)).i=l注意這里是聯(lián)合概率分布積最大，說明樸素貝葉斯是生成模型。求解得：=1八/=1}6g~ ￡2―{嚴(yán)=1}*"-￡蠹1{/=0}一， ￡隨1{嚴(yán)=1}弧= 最后一個式子是表示y=i的樣本數(shù)占全部樣本數(shù)的比例，前兩個表示在y=i或0的樣本中，特征Xj=l的比例.然而我們要求的是p（x\y=i）p（!/=i）p\y=if）= = （II-ilv=1））——=i） （FTi川川y=］））p（y=1）+（ntiP（ri4=o））p（y=。）'立阡是求出分子即可，分母對y=i和y=o都一樣。當(dāng)然，樸素貝葉斯方法可以擴(kuò)展到x和y都有多個離散值的情況。對于特征是連續(xù)值的情況，我們也可以采用分段的方法來將連續(xù)值轉(zhuǎn)化為離散值。具體怎么轉(zhuǎn)化能夠最優(yōu)，我們可以采用信息增益的度量方法來確定（參見Mitchell的《機(jī)器學(xué)習(xí)》決策樹那一章I比如房子大小可以如下劃分成離散值：Livingarea（sq.feet）<400400-800800-12001200-1600>1600I2 3 4 54拉普拉斯平滑樸素貝葉斯方法有個致命的缺點(diǎn)就是對數(shù)據(jù)稀疏問題過于敏感。比如前面提到的郵件分類，現(xiàn)在新來了一封郵件，郵件標(biāo)題是"NIPScallforpapers"0我們使用更大的網(wǎng)絡(luò)詞典（詞的數(shù)目由5000變?yōu)?5000）來分類，假設(shè)NIPS這個詞在字典中的位置是35000.然而NIPS這個詞沒有在訓(xùn)練數(shù)據(jù)中出現(xiàn)過，這封郵件第一次出現(xiàn)了NIPS.那我們算概率的時候如下：的5000g￡i=[ =1八嚴(yán)=[}C>35000|j/=0=嚴(yán)="1{工^000=1八*=0}￡31{4"=。}由于NIPS在以前的不管是垃圾郵件還是正常郵件都沒出現(xiàn)過，那么結(jié)果只能是0了。顯然最終的條件概率也是0.p(y=i|])= n3P(工加=i)p(u=1) H3p(詞v=i)p(g=D+FIMpMy=o)p(y=o)oo,原因就是我們的特征概率條件獨(dú)立，使用的是相乘的方式來得到結(jié)果。為了解決這個問題，我們打算給未出現(xiàn)特征值，賦予一個"小"的值而不是0。具體平滑方法如下：假設(shè)離散型隨機(jī)變量z有｛1,2，…,k｝個值，我們用0,=p(z=i)來表示每個值的概率。假設(shè)有m個訓(xùn)練樣本中，z的觀察值是｛J" 二｝其中每一個觀察值對應(yīng)k個值中的個。那么根據(jù)原來的估計方法可以得到機(jī)=-m 說白了就是Z=j出現(xiàn)的比例.拉普拉斯平滑法將每個k值出現(xiàn)次數(shù)事先都加1,通俗講就是假設(shè)他們都出現(xiàn)過一次。那么修改后的表達(dá)式為：小_￡颶1卜("=，｝+1如一 E -每個z刁的分子都加1,分母加k?？梢?這個有點(diǎn)像NLP里面的加一平滑法，當(dāng)然還有n多平滑法了，這里不再詳述.回到郵件分類的問題，修改后的公式為：6j\u=i0j|y=O￡圈i{率=1八嚴(yán)=i}+6j\u=i0j|y=O￡乙1{*=1}+2￡二1{]'=1A嚴(yán)=0}+1￡乙1{/)=0}+25文本分類的事件模型回想一下我們剛剛使用的用于文本分類的樸素貝葉斯模型，這個模型稱作多值伯努利事件模型(multi-variateBernoullieventmodel工在這個模型中,我們首先隨機(jī)選定了郵件的類型(垃圾或者普通郵件，也就是p(y)),然后一個人翻閱詞典，從第一個詞到最后一個詞，隨機(jī)決定一個詞是否要在郵件中出現(xiàn)，出現(xiàn)標(biāo)示為1,否則標(biāo)示為0.然后將出現(xiàn)的詞組成一封郵件。決定一個詞是否出現(xiàn)依照概率p(xi|y)。那么這封郵件的概率可以標(biāo)示為p(y)n『iP(g|y”讓我們換一個思路，這次我們不先從詞典入手，而是選擇從郵件入手。讓i表示郵件中的第i個詞，xi表示這個詞在字典中的位置，那么xi取值范圍為｛1,2,...|V|｝,|V|是字典中詞的數(shù)目。這樣一封郵件可以表示成(工12,????Tn),n可以變化，因為每封郵件的詞的個數(shù)不同。然后我們對于每個xi隨機(jī)從|V|個值中取一個，這樣就形成了一封郵件.這相當(dāng)于重復(fù)投擲IV|面的骰子，將觀察值記錄下來就形成了一封郵件。當(dāng)然每個面的概率服從p(x“y),而且每次試驗條件獨(dú)立。這樣我們得到的郵件概率是p(y)II：=iP(』W)。居然跟上面的一樣，那么不同點(diǎn)在哪呢？注意第一個的n是字典中的全部的詞，下面這個n是郵件中的詞個數(shù).上面xi表示一個詞是否出現(xiàn)，只有0和1兩個值，兩者概率和為1,下面的xi表示|V|中的一個值，|V|個p(xi|y)相加和為1.是多值二項分布模型。上面的x向量都是0/1值，下面的x的向量都是字典中的位置。形式化表示為：m個訓(xùn)練樣本表示為：｛(工⑺/⑴)；'=1 巾｝...Z(0(i) (i)\工⑴=(11,12?????xnt)

?、疟硎镜趇個樣本中，共有ni個詞，每個詞在字典中的編號為勺.那么我們?nèi)匀话凑諛闼刎惾~斯的方法求得最大似然估計概率為m?？沙穑踶=l)--山即州1=1嚴(yán)/ni \=n(11夕(工,尿廂=。，加=|)卜(/‘例)?—I』 ) 解得，如!/=1=￡隗￡21{斕=1嚴(yán)=1}￡隨i{y⑴二1}小帆y=O=￡3￡21{?0八/=0}￡31{*=0}小弧=m 與以前的式子相比，分母多了個ni,分子由0/1變成了k.舉個例子：XIX2X3Y12-121-013203331假如郵件中只有a,b,c這三詞，他們在詞典的位置分別是1,2,3,前兩封郵件都只有2個詞，后兩封有3個詞。Y=1是垃圾郵件。那么，1+0 113①①2g1 ①3gi=g2+0221①l|y=0=『①21y=0=g，①31y=0=g11ey=i=2，ey=o=2假如新來一封郵件為b,(:那么特征表示為｛2,3｝。

那么n,aP(x,y=i)p(x={2,3}|y=l)p(y=1)P(y=1|X)=F5-=―P(x={2.3}) ①21y=1①31y=1①y=l ①2|y=仲31y=1中y=l+621y=0中31y=06y=00.2?0.6?0.5= =0.60.2*0.6*0.5+0.4*0.2*0.5那么該郵件是垃圾郵件概率是0.6。注意這個公式與樸素貝葉斯的不同在于這里針對整體樣本求的中心=1,而樸素貝葉斯里面針對每個特征求的中xj=l|y=1I而且這里的特征值維度是參差不齊的。這里如果假如拉普拉斯平滑，得到公式為：<Pk\y=l=0kly=0=￡31{/)=1}叫+|二

￡3￡21{貨="/=0}+<Pk\y=l=0kly=0=E^l{^=0}n,+|V| ?表示每個k值至少發(fā)生過一次。另外樸素貝葉斯雖然有時候不是最好的分類方法，但它簡單有效，而且速度快。支持向量機(jī)（上）JerryLead2011年3月12日星期六1簡介支持向量機(jī)基本上是最好的有監(jiān)督學(xué)習(xí)算法了。最開始接觸SVM是去年暑假的時候，老師要求交《統(tǒng)計學(xué)習(xí)理論》的報告，那時去網(wǎng)上下了一份入門教程，里面講的很通俗，當(dāng)時只是大致了解了一些相關(guān)概念.這次斯坦福提供的學(xué)習(xí)材料，讓我重新學(xué)習(xí)了一些SVM知識.我看很多正統(tǒng)的講法都是從VC維理論和結(jié)構(gòu)風(fēng)險最小原理出發(fā)，然后引出SVM什么的，還有些資料上來就講分類超平面什么的。這份材料從前幾節(jié)講的logistic回歸出發(fā)，引出了SVM,既揭示了模型間的聯(lián)系，也讓人覺得過渡更自然.2重新審視logistic回歸Logistic回歸目的是從特征學(xué)習(xí)出一個0/1分類模型，而這個模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負(fù)無窮到正無窮。因此，使用logistic函數(shù)（或稱作sigmoid函數(shù)）將自變量映射到（0,1）上,映射后的值被認(rèn)為是屬于y=l的概率。形式化表示就曷取設(shè)函數(shù)T1用（工）=g（8］）=.,_ort^1+e0工其中X是n維特征向量，函數(shù)g就是logistic函數(shù)。g(z)=1g(z)=的圖像是：'：?：J：：：可以看到，將無窮映射到了(0,1)。而假設(shè)函數(shù)就是特征屬于y=i的概率。P(y=l\x;0)=h0(x)P(y=oIx;0)=1-he(x)當(dāng)我們要判別一個新來的特征屬于哪個類時，只需求也(X),若大于0.5就是y=l的類,反之屬于y=o類。再審視一下he(x),發(fā)現(xiàn)自0只和。丁》有關(guān),0rx>O,那么hg(x)>0.5,g(z)只不過是用來映射，真實的類別決定權(quán)還在。還有當(dāng)?0時，he(x)=l,反之九"x)=0。如果我們只從出發(fā)，希望模型達(dá)到的目標(biāo)無非就是讓訓(xùn)練數(shù)據(jù)中y=l的特征?0,而是y=0的特征0Tx?0.Logistic回歸就是要學(xué)習(xí)得到。，使得正例的特征遠(yuǎn)大于0,負(fù)例的特征遠(yuǎn)小于0,強(qiáng)調(diào)在全部訓(xùn)練實例上達(dá)到這個目標(biāo)。圖形化表示如下：XA,中間那條線是。7X=0,logistic回顧強(qiáng)調(diào)所有點(diǎn)盡可能地遠(yuǎn)離中間那條線。學(xué)習(xí)出的結(jié)果也就中間那條線?？紤]上面3個點(diǎn)A、B和C。從圖中我們可以確定A是x類別的，然而C我們是不太確定的，B還算能夠確定。這樣我們可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點(diǎn)，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點(diǎn)上達(dá)到最優(yōu)。因為那樣的話，要使得一部分點(diǎn)靠近中間線來換取另外一部分點(diǎn)更加遠(yuǎn)離中間線。我想這就是支持向量機(jī)的思路和logistic回歸的不同點(diǎn)，一個考慮局部(不關(guān)心已經(jīng)確定遠(yuǎn)離的點(diǎn))，一個考慮全局(已經(jīng)遠(yuǎn)離的點(diǎn)可能通過調(diào)整中間線使其能夠更加遠(yuǎn)離\這是我的個人直觀理解。3形式化表示我們這次使用的結(jié)果標(biāo)簽是y=-l,y=l,替換在logistic回歸中使用的y=0和y=l。同時將0替換成w和b.以前的。TX=00+01X1+02X2H 1-0nXn,其中認(rèn)為Xo=1.現(xiàn)在我們替換為b,后面替換91X1+02%2+…+ "為W1X1+W2X2+…+WnXn(即W「X1這樣，我們讓。Tx=wTx+b,進(jìn)一步也(x)=g(0Tx)=g(wTx+b).也就是說除了y由y=0變?yōu)閥=-l,只是標(biāo)記不同外，與logistic回歸的形式化表示沒區(qū)別。再明確下假設(shè)函數(shù)hwj>(x)=g(wTx+b)上一節(jié)提到過我們只需考慮的正負(fù)問題,而不用關(guān)心g（z）,因此我們這里將g（z）做一個簡化，將其簡單映射到y(tǒng)=-i和y=i上。映射關(guān)系如下：1,z>0g（z）={-1,z<04函數(shù)間隔（functionalmargin）和幾何間隔（geometricmargin）給定一個訓(xùn)練樣本（X<0,y（*））,X是特征，y是結(jié)果標(biāo)簽.i表示第i個樣本。我們定義函數(shù)間隔如下：y（i）=y（i）（WTX（i）+b）可想而知，當(dāng)y（i）=1時，在我們的g⑵定義中,wTx（^+b>0,加）的值實際上就是|WG（，）+bI。反之亦然。為了使函數(shù)間隔最大（更大的信心確定該例是正例還是反例），當(dāng)y（i）=1時，w7xa）+b應(yīng)該是個大正數(shù)，反之是個大負(fù)數(shù)。因此函數(shù)間隔代表了我們認(rèn)為特征是正例還是反例的確信度。繼續(xù)考慮w和b,如果同時加大W和b,比如在（wTx（i）+b）前面乘個系數(shù)比如2,那么所有點(diǎn)的函數(shù)間隔都會增大二倍，這個對求解問題來說不應(yīng)該有影響，因為我們要求解的是wTx+b=0,同時擴(kuò)大W和b對結(jié)果是無影響的。這樣，我們?yōu)榱讼拗芖和b,可能需要加入歸一化條件，畢竟求解的目標(biāo)是確定唯——個W和b,而不是多組線性相關(guān)的向量。這個歸一化一會再考慮。剛剛我們定義的函數(shù)間隔是針對某一個樣本的，現(xiàn)在我們定義全局樣本上的函數(shù)間隔7=min針）.說白了就是在訓(xùn)練樣本上分類正例和負(fù)例確信度最小那個函數(shù)間隔。接下來定義幾何間隔，先看圖假設(shè)我們有了B點(diǎn)所在的w"+b=0分割面。任何其他一點(diǎn)，比如A到該面的距離以Y?）表示，假設(shè)B就是A在分割面上的投影。我們知道向量BA的方向是w（分割面的梯度），單位向量是llwll.A點(diǎn)是（x（i）,y（i））,所以B點(diǎn)是x=Yllwll（利用初中的幾何知識），帶入+b=0得，wT（x（i）-y⑴7T+b=0||w||進(jìn)一步得到IIMI\llwll/Mily&）實際上就是點(diǎn)到平面距離。再換種更加優(yōu)雅的寫法：當(dāng)l|w||=1時，不就是函數(shù)間隔嗎？是的，前面提到的函數(shù)間隔歸一化結(jié)果就是幾何問隔。他們?yōu)槭裁磿粯幽兀恳驗楹瘮?shù)間隔是我們定義的，在定義的時候就有幾何間隔的色彩.同樣，同時擴(kuò)大W和b,W擴(kuò)大幾倍，||w||就擴(kuò)大幾倍，結(jié)果無影響。同樣定義全局的幾何間隔5最優(yōu)間隔分類器(optimalmarginclassifier)回想前面我們提到我們的目標(biāo)是尋找一個超平面，使得離超平面比較近的點(diǎn)能有更大的間距.也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。形象的說，我們將上面的圖看作是一張紙，我們要找一條折線，按照這條折線折疊后，離折線最近的點(diǎn)的間距I：匕其他折線都要大。形式化表示為：max7Mb7s.t. +6)27，i=1,...,ml|w||=1- 這里用||W||=1規(guī)約W,使得+b是幾何間隔。到此，我們已經(jīng)將模型定義出來了。如果求得了W和b,那么來一個特征X,我們就能夠分類了，稱為最優(yōu)間隔分類器。接下的問題就是如何求解W和b的問題了。由于||W||=1不是凸函數(shù)，我們想先處理轉(zhuǎn)化一下，考慮幾何間隔和函數(shù)間隔的關(guān)系，丫=扁，我們改寫一下上面的式子：Am/皿網(wǎng)s.t.y⑴儂7⑴+b)N%i=1,...,m這時候其實我們求的最大值仍然是幾何間隔，只不過此時的W不受||w||=1的約束了。然而這個時候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒法直接代入優(yōu)化軟件里計算。我們還要改寫。前面說到同時擴(kuò)大W和b對結(jié)果沒有影響，但我們最后要求的仍然是W和b的確定值，不是他們的一組倍數(shù)值，因此，我們需要對P做一些限制，以保證我們解是唯一的。這里為了簡便我們?nèi)=1.這樣的意義是將全局的函數(shù)間隔定義為1,也即是將離超平面最近的點(diǎn)的距離定義為而.由于求向的最大值相當(dāng)于求的最小值，因此改寫后結(jié)果為：min%w.b引s.t./(『工⑴+b)21,*=1,...,m這下好了，只有線性約束了，而且是個典型的二次規(guī)劃問題(目標(biāo)函數(shù)是自變量的二次函數(shù)X代入優(yōu)化軟件可解。到這里發(fā)現(xiàn)，這個講義雖然沒有像其他講義一樣先畫好圖，畫好分類超平面，在圖上標(biāo)示出間隔那么直觀，但每一步推導(dǎo)有理有據(jù)，依靠思路的流暢性來推導(dǎo)出目標(biāo)函數(shù)和約束。接下來介紹的是手工求解的方法了，一種更優(yōu)的求解方法。6拉格朗日對偶(Lagrangeduality)先拋開上面的二次規(guī)劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優(yōu)化問題：minw/(w)s.t.hi(w)=0,，=1,…1.目標(biāo)函數(shù)是f(w),下面是等式約束。通常解法是引入拉格朗日算子，這里使用P來表示算子，得到拉格朗日公式為I￡(叫戶)=/(w)+￡8ih￡w)i=lL是等式約束的個數(shù)。然后分別對w和P求偏導(dǎo),使得偏導(dǎo)數(shù)等于0,然后解出w和P，.至于為什么引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關(guān)系.(參考《最優(yōu)化與KKT條件》)然后我們探討有不等式約束的極值問題求法，問題如下：

minu,f(w)s.t.5,(w)<0,i==0,i=1,...,Z.我們定義一般化的拉格朗日公式k I￡(叫a,乃)=f(w)+工 +￡8冉(⑼.<=1 <=1這里的ai和氏都是拉格朗日算子。如果按這個公式求解，會出現(xiàn)問題，因為我們求解的是最小值，而這里的gi(w)W0,我們可以將a,調(diào)整成很大的正值，來使最后的函數(shù)結(jié)果是負(fù)無窮。因此我們需要排除這種情況，我們定義下面的函數(shù)：0p(w)=max￡(w,a,/?).Qt0：Qi>Q這里的P代表primal.假設(shè)i(w)>0或者h(yuǎn),(W)40,那么我們總是可以調(diào)整a，和0f來使得Or(w)有最大值為正無窮。而只有g(shù)和h滿足約束時，。心)為f(w)o這個函數(shù)的精妙之處在于a1>0,而且求極大值。因此我們可以寫作0f/(w)ifwsatisfiesprimalconstraintsIocotherwise.這樣我們原來要求的minf(w)可以轉(zhuǎn)換成求minw0p(w)了。min^p(w)=minmaxC(w.a,(3),w wa90:ai>O我們使用P*來表示mi5J7(w)。如果直接求解，首先面對的是兩個參數(shù)，而即也是不等式約束，然后再在w上求最小值。這個過程不容易做，那么怎么辦呢？我們先考慮另問題班我們先考慮另問題班(a,8)=minC(w.a,0).D的意思是對偶， ev(a.3)將問題轉(zhuǎn)化為先求拉格朗日關(guān)于w的最小值，將a和B看作是固定值。之后〃「(0?功 在求最大值的話：maxM(a.0)=maxmin￡(w,a,5).>0 ：Qi>0w這個問題是原問題的對偶問題，相對于原問題只是更換了min和max的順序，而一般更換順序的結(jié)果是MaxMin(X)<=MinMax(X).然而在這里兩者相等。用d*來表示對偶問題如下：(T=maxmin￡(w,a,13)<minmaxC(w,a,3)=p*.aj3:a.>0W wa,0:a,>O ,下面解釋在什么條件下兩者會等價.假設(shè)f和g都是凸函數(shù)，h是仿射的(affine,thereexistsn,.b,.sothathi(w)= \并且存在w使得對于所有的i,g,(w)<0.在這種假設(shè)下，一定存在w*,a?,B，使得w*是原問題的解,a*，B.是對偶問題的解。還有P=d=C(W,a,i3?另外，w*,a*,夕*滿足庫恩-塔克條件(Karush-Kuhn-Tucker,KKTcondition),該條件如下：二￡W**a*,/r)OWj=0,i=1,.…,71⑶■)a*./3*)明—0,1=1,.(4)=0,i=1,...,k⑸仇(始*)<0,t=1,...,k(6)*a>0,1=1,...,k⑺所以如果w*,a，］，滿足了庫恩-塔克條件，那么他們就是原問題和對偶問題的解。讓我們再次審視公式(5),這個條件稱作是KKTdualcomplementarity條件。這個條件隱含了如果a->0,那么g,(w*)=0,也就是說，gi(w*)=0時，w處于可行域的邊界上，這時才是起作用的約束。而其他位于可行域內(nèi)部(gi(卬*)<0的)點(diǎn)都是不起作用的約束，其a?=0。這個KKT雙重補(bǔ)足條件會用來解釋支持向量和SM0的收斂測試。這部分內(nèi)容思路比較凌亂，還需要先研究下《非線性規(guī)劃》中的約束極值問題，再回頭看看。KKT的總體思想是認(rèn)為極值會在可行域邊界上取得，也就是不等式為0或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個元素要么是不等式為。的約束，要么是等式約束.對于在可行域邊界內(nèi)的點(diǎn)，對最優(yōu)解不起作用，因此前面的系數(shù)為7最優(yōu)間隔分類器(optimalmarginclassifier)重新回到SVM的優(yōu)化問題：s.t.y⑴(Jh⑴+昉21,i=1,...,m我們將約束條件改寫為：gi(w)=—y⑴(tr,工⑴4-b)4-1<0.從KKT條件得知只有函數(shù)間隔是1(離超平面最近的點(diǎn))的線性約束式前面的系數(shù)即>0,也就是說這些約束式g,(w)=0,對于其他的不在線上的點(diǎn)?,(w)<0),極值不會在他們所在的范圍內(nèi)取得，因此前面的系數(shù)a,=0.注意每一個約束式實際就是一個訓(xùn)練樣本?？聪旅娴膱D：XXX實線是最大間隔超平面，假設(shè)X號的是正例，圓圈的是負(fù)例.在虛線上的點(diǎn)就是函數(shù)間隔是1的點(diǎn)，那么他們前面的系數(shù)a,>0,其他點(diǎn)都是ai=0.這三個點(diǎn)稱作支持向量。構(gòu)造拉格朗日函數(shù)如下：1 小￡(w,b,a)=—||w||2—at[4"(“Jh⑴+b)—1].i=l注意到這里只有即沒有火是因為原問題中沒有等式約束，只有不等式約束。下面我們按照對偶問題的求解步驟來一步步進(jìn)行，d"=maxmin￡(w,a,/3)a,0：QLi>Qw首先求解b'0'的最小值，對于固定的ai,￡(U，-h,°'的最小值只與w和b有關(guān)。對w和b分別求偏導(dǎo)數(shù).mVw￡(w,fe,a)=it?- 6，％")=0i=lq TTlb,a)=￡qy⑴=0.?=i 并得到

將上式帶回到拉格朗日函數(shù)中得到，此時得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）化簡過程如下：m￡(w,b,a)=-||iv||2一2叫'⑴(w‘”)+b)—1]i=lmm m-Waiy^b+W%

i=l i=lmW七'")”)-t=lma’y⑴卬了”)i=l-Waty^b+{a,

i=l i=lm m mmi=l i=l i=l i=1m m-Waiy^b+W%

i=l i=lmW七'")”)-t=lma’y⑴卬了”)i=l-Waty^b+{a,

i=l i=lm m mmi=l i=l i=l i=1m m-WQJ⑴力+￡Qji=l f=lm m-gw「Wa"。”)一"Wa""

i=l i=lm1=1w

i=lTOC\o"1-5"\h\zm m m m=-^2勺、⑴(”))72°^嚴(yán)”)一bW/y⑴+乏片

Z=1 i=l i=l i=lm m m=—；W%'(。(義⑴)‘%'")%。)一bW々y⑴+

i=l,/=l i=l i=lm m m=W七一gWy")y")4a/(""))'X。)一bW戊少⑴

i=l Z=lj=l i=l"倒數(shù)第4步"推導(dǎo)到"倒數(shù)第3步”使用了線性代數(shù)的轉(zhuǎn)置運(yùn)算，由于匹和y。都是實數(shù)，因此轉(zhuǎn)置后與自身一樣。"倒數(shù)第3步"推導(dǎo)到"倒數(shù)第2步"使用了(a+b+c+..J(a+b+c+...)=aa+ab+ac+ba+bb+bc+...的乘法運(yùn)算法則。最后一步是上一步的順序調(diào)整。最后得到：TOC\o"1-5"\h\zm [m m￡(w,b,a)=Qt— /)中4引工⑴)「工⑶—6^^?=1 /tj=i i=l 由于最后一項是o,因此簡化為\o"CurrentDocument"m [m￡(w,fe,a)=)：s——^2/VafajS"))'i=l ij=l這里我們將向量內(nèi)積 表示為「 卜此時的拉格朗日函數(shù)只包含了變量即.然而我們求出了ai才能得到w和b。d*=maxmin￡(w.a,3)接著是極大化的過程 ^：a,>0w ,\o"CurrentDocument"m ]mmaxaW"(a)=￡6-1￡嚴(yán)嚴(yán)°色行⑴,工⑺).i=l tj=lS.t.Qi>0,i=1,...,TTlm⑴=0,1=1前面提到過對偶問題和原問題滿足的幾個條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對于所有的i,g,(w)<0.因此，一定存在w，,a，使得w?是原問題的解，a"是對偶問題的解。在這里，求a，就是求a?了。mw=):qy⑴工⑴.如果求出了ai,根據(jù) 三1 即可求出w(也是w*,原問題的解1然后b*=maXj：*)=] *⑴+min^y⑻=1儲7Hb*=即可求出b.即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。關(guān)于上面的對偶問題如何求解，將留給下一篇中的SM。算法來闡明。這里考慮另外一個問題，由于前面求解中得到mw=^aty（i）x（i）i=l我們通篇考慮問題的出發(fā)點(diǎn)是Wr+b,根據(jù)求解得到的a,,我們代入前式得到6“%⑴）I+bm=）：。毋,）（工⑴，工）+b.?=1也就是說，以前新來的要分類的樣本首先根據(jù)W和b做一次線性運(yùn)算，然后看求的結(jié)果是大于0還是小于0,來判斷正例還是負(fù)例?，F(xiàn)在有了即，我們不需要求出W,只需將新來的樣本和訓(xùn)練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。那有人會說，與前面所有的樣本都做運(yùn)算是不是太耗時了？其實不然，我們從KKT條件中得到，只有支持向量的a,>0,其他情況a,=0。因此，我們只需求新來的樣本和支持向量的內(nèi)積，然后運(yùn)算即可。這種寫法為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。這是上篇，先寫這么多了。支持向量機(jī)SVM（下）JerryLead2011年3月17日星期四7核函數(shù)（Kernels）考慮我們最初在“線性回歸”中提出的問題，特征是房子的面積X,這里的X是實數(shù)，結(jié)果y是房子的價格。假設(shè)我們從樣本點(diǎn)的分布中看到X和y符合3次曲線，那么我們希望使用x的三次多項式來逼近這些樣本點(diǎn)。那么首先需要將特征x擴(kuò)展到三維（x,/,/：,然后尋找特征和結(jié)果之間的模型。我們將這種特征變換稱作特征映射（featuremapping入映射函數(shù)稱作小，在這個例子中X力（X）=X2.X3.我們希望將得到的特征映射后的特征應(yīng)用于SVM分類，而不是最初的特征。這樣，我們需要將前面卬、+力公式中的內(nèi)積從＜/），%＞,映射到＜Mx⑴），。（乃＞。至于為什么需要映射后的特征而不是最初的特征來參與計算，上面提到的（為了更好地擬合）是其中一個原因，另外的一個重要原因是樣例可能存在線性不可分的情況，而1號待征映射到高維空間后，往往就可分了。（在《數(shù)據(jù)挖掘?qū)д摗稰ang-NingTan等人著的《支持向量機(jī)》那一章有個很好的例子說明）將核函數(shù)形式化定義，如果原始特征內(nèi)積是＜X,Z＞,映射后為＜0（x）"（z）＞,那么定義核函數(shù)（Kernel）為K（x,z）=（p（x）T（p（z）到這里，我們可以得出結(jié)論，如果要實現(xiàn)該節(jié)開頭的效果，只需先計算。（X）,然后計算0（x）“⑵即可，然而這種計算方式是非常低效的。比如最初的特征是n維的，我們將其映射到M維，然后再計算，這樣需要。（公說時間。那么我們能不能想辦法減少計算時間呢？先看一個例子，假設(shè)x和z都是n維的，K（x,z）=（xrz）2展開后，得

K(x,z)=(xrK(x,z)=(xrz)2=EXiXjZiZj

i=lj=lnn=勺)(ZiZ/)=i=l/=1這個時候發(fā)現(xiàn)我們可以只計算原始特征x和z內(nèi)積的平方(時間復(fù)雜度是0(n)),就等價與計算映射后特征的內(nèi)積.也就是說我們不需要花0(十：時間了.現(xiàn)在看一下映射函數(shù)(n=3時)，根據(jù)上面的公式，得到"1工I12工113工21112T2工213工311工312工3T3也就是說核函數(shù)K(x,z)=(x7z)2只能在選擇這樣的小作為映射函數(shù)時才能夠等價于映射后特征的內(nèi)積。再看一個核函數(shù)K(x,z)=(xTz4-c)2n n=￡(工+￡(V%皿)(V%q)+C2.2=1 ，=1 對應(yīng)的映射函數(shù)(n=3時)是0(工)=工由口上2工113叼11工212工213工311工312工313\/2ci\0(工)=，n+d、更一般地，核函數(shù)K(X,Z)=(xTz+c)d對應(yīng)的映射后特征維度為Id4(這個我一直沒有理解\由于計算的是內(nèi)積，我們可以想到IR中的余弦相似度，如果X和Z向量夾角越小，那么核函數(shù)值越大，反之，越小。因此，核函數(shù)值是0(》￥口。9)的相似度。再看另外一個核函數(shù)K(x,z)K(x,z)=expII工一Z/

2a2這時，如果X和Z很相近(llx-z||?O),那么核函數(shù)值為1,如果X和Z相差很大(llx-zll?o),那么核函數(shù)值約等于0,由于這個函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(RadialBasisFunction簡稱RBF)O它能夠把原始特征映射到無窮維。既然高斯核函數(shù)能夠比較x和z的相似度，并映射到。到1,回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。F面有張圖說明在低維線性不可分時，映射到高維后就可分了，使用高斯核函數(shù)。注意，使用核函數(shù)后，怎么分類新來的樣本呢？線性的時候我們使用SVM學(xué)習(xí)出w和b,新來樣本x的話，我們使用x+味判斷，如果值大于等于1,那么是正類，小于等于是負(fù)類。在兩者之間，認(rèn)為無法確定。如果使用了核函數(shù)后，X+6就變成了/o(x)+b,是否先要找到Mx),然后再預(yù)測？答案肯定不是了，找。(X)很麻煩，回想我們之前說過的m=)：0婚⑴+b.i=l<”),%> K(/),x) 只需將替換成，然后值的判斷同上.8核函數(shù)有效性判定問題：給定一個函數(shù)K,我們能否使用K來替代計算0(X)T?(Z),也就說，是否能夠找出f0,使得對于所有的X和Z,都有K(X,Z)=。(幻丁巾⑵？比如給出了K(x,z)=(xTz)2,是否能夠認(rèn)為K是一個有效的核函數(shù)。下面來解決這個問題，給定m個訓(xùn)練樣本｛“⑴,x⑵，…,每一個丫⑴對應(yīng)一個特征向量。那么,我們可以將任意兩個小和X。帶入K中，計算得到心=K(”),W)).?可以從1到m,j可以從1到m,這樣可以計算出m*m的核函數(shù)矩陣(KernelMatrix1為了方便，我們將核函數(shù)矩陣和K(x,z鄴使用K來表示。如果假設(shè)K是有效的核函數(shù)，那么根據(jù)核函數(shù)定義Ka= =。（”））%（*。））=。（丫。））%（*?））=K（x"x⑴）=Ka可見，矩陣K應(yīng)該是個對稱陣。讓我們得出一個更強(qiáng)的結(jié)論，首先使用符號機(jī)（X屎表示映射函數(shù)0（x）的第k維屬性值。那么對于任意向量z,得zTKz=V2X2ZiKijZj=￡￡ （工⑴）T°（工⑶）Zj?j=￡￡Zf￡ ⑴）。k（工⑴）Zj*jk=￡￡￡力加工⑷）如（工⑺為kij=￡（￡.（工"）））>o.最后一步和前面計算K（%z）=。％）2時類似。從這個公式我們可以看出，如果K是個有效的核函數(shù)（即K（x,z麗0（x）7。⑵等價），那么，在訓(xùn)|練集上得到的核函數(shù)矩陣K應(yīng)該是半正定的（KW0）這樣我們得到一個核函數(shù)的必要條件：K是有效的核函數(shù)==>核函數(shù)矩陣K是對稱半正定的?？尚业氖?，這個條件也是充分的，由Mercer定理來表達(dá)。Mercer定理：如果函數(shù)K是眼nx那t快上的映射（也就是從兩個n維向量映射到實數(shù)域\那么如果K是一個有效核函數(shù)（也稱為Mercer核函數(shù)），那么當(dāng)且僅當(dāng)對于訓(xùn)練樣例1X⑴，X（2），…,X（m）］,其相應(yīng)的核函數(shù)矩陣是對稱半正定的。 Mercer定理表明為了證明K是有效的核函數(shù)，那么我們不用去尋找。，而只需要在訓(xùn)練集上求出各個K",然后判斷矩陣K是否是半正定（使用左上角主子式大于等于零等方法）即可。許多其他的教科書在Mercer定理證明過程中使用了1.2范數(shù)和再生希爾伯特空間等概念，但在特征是n維的情況下，這里給出的證明是等價的。核函數(shù)不僅僅用在SVM上，但凡在一個模型后算法中出現(xiàn)了<X.Z>,我們都可以常使用K（x,z法替換，這可能能夠很好地改善我們的算法。9規(guī)貝(］化和不可分,情況處理(Regularizationandthenon-separablecase)我們之前討論的情況都是建立在樣例線性可分的假設(shè)上，當(dāng)樣例線性不可分時，我們可以嘗試使用核函數(shù)來將特征映射到高維，這樣很可能就可分了。然而，映射后我們也不能100%保證可分.那怎么辦呢，我們需要各模型進(jìn)行調(diào)整，以保證在不可分的情況下，也能夠盡可能地找出分隔超平面。看下面兩張圖：可以看到一個離群點(diǎn)（可能是噪聲）可以造成超平面的移動，間隔縮小，可見以前的模型對噪聲非常敏感。再有甚者，如果離群點(diǎn)在另外一個類中，那么這時候就是線性不可分了。這時候我們應(yīng)該允許一些點(diǎn)游離并在在模型中違背限制條件（函數(shù)間隔大于11我們設(shè)計得到新的模型如下（也稱軟間隔）：1 二min”力+i=ls.t.y⑴工⑴+b）21—i=&20,i=引入非負(fù)參數(shù)U后（稱為松弛變量），就允許某些樣本點(diǎn)的函數(shù)間隔小于1,即在最大間隔區(qū)間里面，或者函數(shù)間隔是負(fù)數(shù)，即樣本點(diǎn)在對方的區(qū)域中。而放松限制條件后，我們需要重新調(diào)整目標(biāo)函數(shù)，以對離群點(diǎn)進(jìn)行處罰，目標(biāo)函數(shù)后面加上的C 匕就表示離群點(diǎn)越多，目標(biāo)函數(shù)值越大，而我們要求的是盡可能小的目標(biāo)函數(shù)值。這里的C是離群點(diǎn)的權(quán)重，C越大表明離群點(diǎn)對目標(biāo)函數(shù)影響越大，也就是越不希望看到離群點(diǎn)。我們看到，目標(biāo)函數(shù)控制了離群點(diǎn)的數(shù)目和程度，使大部分樣本點(diǎn)仍然遵守限制條件。模型修改后，拉格朗日公式也要修改如下：I mm m￡（w,b,^,a,r）=-w14-C-57a, +6）-1+々］一辱f=lt=l t=l這里的a,和人都是拉格朗日乘子，回想我們在拉格朗日對偶中提到的求法，先寫出拉格朗日公式(如上)，然后將其看作是變量W和b的函數(shù)，分別對其求偏導(dǎo)，得到W和b的表達(dá)式。然后代入公式中，求帶入后公式的極大值。整個推導(dǎo)過程類似以前的模型，這里只寫出最后結(jié)果如下：m 〔mmaxQW(a)=￡%-]￡y⑴嚴(yán)i=l >J=1s.t.0<a,<C,i=1,...,mm￡3嚴(yán)=0,i=l此時，我們發(fā)現(xiàn)沒有了參數(shù)L,與之前模型唯一不同在于斯又多了ai<c的限制條件。需要提醒的是，b的求值公式也發(fā)生了改變，改變結(jié)果在SMO算法里面介紹。先看看KKT條件的變化:=0=>y⑴(tv，工⑴+b)21(14)oii=C=>y⑴(uZz")-|-fe)<1(15)0<ai<C=>+6)=1.(16)第一個式子表明在兩條間隔線外的樣本點(diǎn)前面的系數(shù)為0,離群樣本點(diǎn)前面的系數(shù)為C,而支持向量(也就是在超平面兩邊的最大間隔線上)的樣本點(diǎn)前面系數(shù)在(0,C)上.通過KKT條件可知，某些在最大間隔線上的樣本點(diǎn)也不是支持向量，相反也可能是離群點(diǎn)。坐標(biāo)上升法(Coordinateascent)在最后討論W(a)的求解之前，我們先看看坐標(biāo)上升法的基本原理。假設(shè)要求解下面的優(yōu)化問題：maxlV(ai,Q2,???,?m).a這里W是a向量的函數(shù)。之前我們在回歸中提到過兩種求最優(yōu)解的方法，一種是梯度下降法，另夕1種是牛頓法?，F(xiàn)在我們再講一種方法稱為坐標(biāo)上升法(求解最小值問題時,稱作坐標(biāo)下降法，原理一樣I方法過程：Loopuntilconvergence:Fori=1,?..,m,{cti：=argmaxd.W(ai,...,a,_i,a,,ai+1,...,am).)If最里面語句的意思是固定除a,之外的所有ajOH),這時W可看作只是關(guān)于a,的函數(shù)，那么直接對a，求導(dǎo)優(yōu)化即可。這里我們進(jìn)行最大化求導(dǎo)的順序i是從1到m,可以通過更改優(yōu)化順序來使W能夠更快地增加并收斂。如果W在內(nèi)循環(huán)中能夠很快地達(dá)到最優(yōu)，那么坐標(biāo)上升法會是一個很高效的求極值方法。下面通過一張圖來展示：橢圓代表了二次函數(shù)的各個等高線，變量數(shù)為2,起始坐標(biāo)是(2,-2).圖中的直線式迭代優(yōu)化的路徑，可以看到每一步都會向最優(yōu)值前進(jìn)一步，而且前進(jìn)路線是平行于坐標(biāo)軸的，因為每一步只優(yōu)化一個變量。SMO優(yōu)化算法(Sequentialminimaloptimization)SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對線性SVM和數(shù)據(jù)稀疏時性能更優(yōu)。關(guān)于SMO最好的資料就是他本人寫的《SequentialMinimalOptimizationAFastAlgorithmforTrainingSupportVectorMachines》了。我拜讀了一下，下面先說講義上對此方法的總結(jié)。首先回到我們前面一直懸而未解的問題，對偶函數(shù)最后的優(yōu)化問題：m [mmaxQW（a）=^2Q?-2^2嚴(yán)!/"45（1"\工0，）i=l ij=l.t.0< <C,i=1,...,mm￡%嚴(yán)=o,要解決的是在參數(shù)*ai,a2，…,a.+上求最大值W的問題，至于x（'）和y（，嘟是已知數(shù)。C由我們預(yù)先設(shè)定，也是已知數(shù)。按照坐標(biāo)上升的思路，我們首先固定除a1以外的所有參數(shù)，然后在ai上求極值。等一下，這個思路有問題，因為如果固定a1以外的所有參數(shù)，那么a】將不再是變量（可以由其他值推出）,因為問題中規(guī)定了msy。，=嚴(yán).4=2因此，我們需要一次選取兩個參數(shù)做優(yōu)化，比如a1和a2,此時a2可以由ai和其他參數(shù)表示出來。這樣回帶到W中，W就只是關(guān)于a1的函數(shù)了，可解。這樣,SMO的主要步驟如下：Repeattillconvergence{Selectsomepairsandotjtoupdatenext（usingaheuristicthattriestopickthetwothatwillallowustomakethebiggestprogresstowardstheglobalmaximum）.ReoptimizeIV（a）withrespecttoa?andQj,whileholdingalltheotherajt，s（k#fixed.} 意思是，第一步選取一對田和陽,選取方法使用啟發(fā)式方法（后面講X第二步，固定除。和為之外的其他參數(shù)，確定W極值條件下的田，為由為表示。SM。之所以高效就是因為在固定其他參數(shù)后，對一個參數(shù)優(yōu)化過程很高效。下面討論具體方法：假設(shè)我們選取了初始值{心,的，…,4}滿足了問題中的約束條件.接下來，我們固定口3,?4，…,?n],這樣W就是由和《2的函數(shù)。并且由和a?滿足條件：m嚴(yán)+。2嚴(yán)=i=3由于｛心44，…,即腳是已知固定值，因此為了方面，可將等式右邊標(biāo)記成實數(shù)值Jai嚴(yán)+a2y⑵=C當(dāng)yd知y⑵異號時，也就是一個為1,一個為-1時，他們可以表示成一條直線，斜率為.如下圖：c橫軸是小,縱軸是a?,小和a?既要在矩形方框內(nèi)，也要在直線上，因此L—max(O,a2—即)，H—min(C,C+a2—%)同理，當(dāng)yd知y⑵同號時，L=max(O,a2+ar-C)tH=min(C,a2+a。然后我們打算將小用a?表示：m= 。2嚴(yán)加”然后反代入W中，得卬(3,9,??.,％)=卬((4-02即)嚴(yán),02,?…%).展開后w可以表示成aa22+ba2+co其中a,b,c是固定值。這樣，通過對W進(jìn)行求導(dǎo)可以得到,然而要保證滿足L<a2<H,我們使用aznewMdipped表示求導(dǎo)求出來的,然而最后的,要根據(jù)下面情況得到：（H if0『叫undipped>"a罰=） unclippedh￡gundipped、〃IL ifa”sdwd<「 這樣得到a/ew后，我們可以得到巴的新值ajew。下面進(jìn)入Platt的文章，來找到啟發(fā)式搜索的方法和求b值的公式。這篇文章使用的符號表示有點(diǎn)不太一樣，不過實質(zhì)是一樣的，先來熟悉一下文章中符號的表示。文章中定義特征到結(jié)果的輸出函數(shù)為X。⑴與我們之前的實質(zhì)是一致的。原始的優(yōu)化問題為：min|||wj|2subjectto/（港區(qū)—b）>1,V/,（3）求導(dǎo)得到：N升=2ygK、6=+?%—匕forsomecrk>0.i=i（7）經(jīng)過對偶后為：min甲（a）=min；￡￡yty,優(yōu)?用）a,%-￡a,,

a am>i ，=ia,>0,V/,s.t.NZw=o-這里與w函數(shù)是一樣的，只是符號求反后，變成求最小值了。y和y（）是一樣的，都表示第i個樣本的輸出結(jié)果（1或一11經(jīng)過加入松弛變量6后，模型修改為：NTOC\o"1-5"\h\zminj|H|2+Cysubjectto-6)1-V/, (8)血 ，=]0Wa,4CV/. (9)由公式(7)代入(1)中可知，NU=2y/x^ixj,x)-b, (10)這個過程和之前對偶過程一樣.重新整理我們要求的問題為：.VN Nmin甲(〃)=min：22/匕K優(yōu),司)%%-a a,=1>1 叫0<az<C,V/t (11)N2”,=0?J=1 與之對應(yīng)的KKT條件為：a,=0oyjuj>1,0<生.<C=/必=1, (12)a,=C=yiuj<1.這個KKT條件說明，在兩條間隔線外面的點(diǎn)，對應(yīng)前面的系數(shù)矽為0,在兩條間隔線里面的對應(yīng)a，為C,在兩條間隔線上的對應(yīng)的系數(shù)a，在0和C之間。將我們之前得到L和H重新拿過來：TOC\o"1-5"\h\zL=max(0.a2H=mln(C,C+a2-ai). (13)L=max(0,a2+ai-Cj,//=min(C。？+aj. (14)之前我們將問題進(jìn)行到這里，然后說將a?用a2表示后代入W中，這里將代入?yún)n中，得甲=；見裙+ +yai%+y2a2V2-4-。2+史2?， (24)

K“=K(&充J(25)N(25)匕=2匕a；%=ut+b'-yxa\Kh-y2a\K2i,2這里的ai*和a2*代表某次迭代前的原始值，因此是常數(shù)，而a1和a2是變量，待求。公式（24）中的最后一項是常數(shù)。由于a1和a2滿足以下公式n%即*+y2a2*=一W%/*=%即+y2a2i=3因為aj（i>2）的值是固定值，在迭代前后不會變。那么用s表示必丫2,上式兩邊乘以乂時，變?yōu)椋篴1+sa2=a\+sa'2=w. （26）其中nW=f1=3代入（24）中，得甲=g廝（W-5a2）2+J +s42（卬一5a2）a2 （勿+%（卬一sa2）%一卬+sa2+%a2V2-a2+匕…?這時候只有電是變量了，求導(dǎo) =-s/C|?（w-set））+Km（x2—K\?a?+5K（w—sex^）—y?q+s+%'2—1=0-（28）da? — - - - 如果甲的