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

《斯坦福大學機器學習課程個人筆記完整版》由會員分享，可在線閱讀，更多相關《斯坦福大學機器學習課程個人筆記完整版（157頁珍藏版）》請在裝配圖網上搜索。

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