斯坦福大學機器學習課程個人筆記完整版

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