大數(shù)據(jù)全集svm推導(dǎo)支持向量機(jī)因其英文名為故一般簡稱SVM通俗來講它是

類一個(gè)線性分類器的學(xué)習(xí)目標(biāo)便是要在n維的數(shù)據(jù)空間中找到一個(gè)超平（hyper這個(gè)超平面的方程可以表示為（wTT代表轉(zhuǎn)置）：logistic（或稱作sigmoid函數(shù)）將自變量映射到(0,1)y=1的概率。其中x是nglogistic 的圖像y=1y=1y=0此外，只和有關(guān)，>0，那么，而g(z)只是用來映射，真實(shí)的類別決定權(quán)還是在于。再者，當(dāng)時(shí)，=1，反之=0。如果我們只從出y=1的特征y=0的特征Logistic00接下來，嘗試把logistic回歸做個(gè)變形。首先，將使用的結(jié)果y=0和y=1替換y=-1,y=1，然后將 （）中的替換為b，最后 。也就是說除了y由y=0變?yōu)閥=-1外，線性分類函數(shù)跟logistic回歸的形式 y=-1y=1y全是-1，另一邊所對應(yīng)y1。 ，與這里定義y(w^xb)y(w^xb)，對我們要優(yōu)化的式子max1/||w||=y(wTx+b)=yf(x)中的Y1和-1嗎？yfunctionalmargin的非負(fù)性？真是這樣的么？當(dāng)然不是，見本文評論下第43樓）。x的類別賦為-1f(x)0則將x1FunctionalmarginGeometrical的正負(fù)性來判定或表示分類的正確性。于此，我們便引出了函數(shù)間隔（functionalmargin）定義函數(shù)間隔（用表示）為而超平面(w，b)T中所有樣本點(diǎn)(xi，yi)的函數(shù)間隔最小值（其中，x是特征，y是結(jié)果，i表示第i個(gè)樣本），便為超平面(w,b)關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔：=mini(i=1，...n)f(x)2倍（雖然此時(shí)超平面沒有改變），所以只有函數(shù)間隔w加些約束條件，從而引出真正定義點(diǎn)到超平面的距離--幾何間隔（geometricalmargin）的概念。xx0，w是垂直于超平面的一個(gè)向量，為樣本x到超平面的距離，如下圖所示：其中||w||為w的二階范數(shù)（范數(shù)是一個(gè)類似 又由于x0是超平面上的點(diǎn)，滿足f(x0)=0，代入超平面的方程 的兩邊同時(shí)乘以，再根據(jù) γy*(wx+b)=y*f(x)實(shí)際上就是|f(x)|，只是人為定義的一個(gè)間隔度量，而幾何間隔 umMarginClassifier的定間隔越大，分類的確信度也越大。所以，為了使得分類的確信度盡量高，需要讓所選擇的超平面能夠最大化這個(gè)間隔Gap的一半?？梢缘缺壤乜s放w的長度和b的值，這樣可以使 即函數(shù)間 可以在超平面保持不變的情況下被取得任意大。但幾何間隔因?yàn)槌?ummarginclassifier）的目標(biāo)函數(shù)可以定義為其中，s.t.subjectto回顧下幾何間隔的定義可知：如果令函數(shù)間隔 等于1（之所以下第42樓回復(fù)），則有=1/||w||且 化這個(gè)1/||w||值，而1/||w||便是幾何間隔。如下圖所示，中間的實(shí)線便是尋找到的最優(yōu)超平面（OptimalHyper 虛線邊界的距離相等，這個(gè)距離便是幾何間隔，兩條虛線間隔邊界之間的距離等于2，滿足（還記得我們把functionalmargin定為1了嗎？上節(jié)中：處于方便推導(dǎo)和 。 由分母變成分子，從而也有原來的max問題變?yōu)閙in問題，很明顯，兩者問題等價(jià)）：QP(QuadraticProgramming)優(yōu)化包進(jìn)行求解。一言以蔽之：在一此外，由于這個(gè)問題的特殊結(jié)構(gòu)，還可以通過日對偶性（LagrangeDuality）變換(dualvariable)（dualproblem）那什么是日對偶性呢？簡單來講通過給每一個(gè)約束條件加上一個(gè)日乘（Lagrangemultiplier），定義日函數(shù)（通過日函數(shù)將約束條件融合到目標(biāo)容易驗(yàn)證，當(dāng)某個(gè)約束條件不滿足時(shí)，例如，那么顯然有，亦即最初要最小化的量。（當(dāng)然，這里也有約束條件，就是≥0,i=1,…,n），因?yàn)槿绻s束條件沒有得到滿足，會等于無窮大，自然不會是我們所要求的最小值。這里 表示這個(gè)問題的最優(yōu)值，且和最初的問題是等價(jià)的。如果直接求解，那么換言之之所以從minmax的原始問題轉(zhuǎn)化為maxmin的對偶問題一者因?yàn)槭堑慕平?，二者，轉(zhuǎn)化為對偶問題后，更容易求解。下面可以先求L對w、b的極小，再求L對的極大KKT條件。 KKTx*必須滿足下面的條KKT條件的（Slaterconditionf和gi也都是可微的，即L對w和b都可導(dǎo)），因此現(xiàn)在我們便轉(zhuǎn)化為求解第二個(gè)問題。也就是說，原始問題通過滿足KKT條件，已經(jīng)轉(zhuǎn)化成了對偶問題。而求解這個(gè)對偶學(xué)習(xí)問題，分為3個(gè)步驟：首先要讓L(w，b，a)關(guān)于w和 b最小化，然后求對的極大，最后利用SMO算法求解對偶問題中的日乘子。 L關(guān)于 w和 b最小化，我們分別對w，b求偏導(dǎo)數(shù)，即令?L/?w和?L/?b等于零（對w求導(dǎo)結(jié)果的解釋請看本文評論下第45樓回復(fù)）：jerrylead所說：“4步”推導(dǎo)到“3步”使用了線性代數(shù)的轉(zhuǎn)置運(yùn)算，由于aiyi都是實(shí)數(shù)，因此轉(zhuǎn)置后與自身一樣?！?步”推導(dǎo)到“2步”使用了從上面的最后一個(gè)式子，我們可以看出，此時(shí)的日函數(shù)只包含了一個(gè)變量，那就是（求出了便能求出w，和b，由此可見，上文第1.2節(jié)提出來的 也就可以輕而易舉的求出來了）和b，得到的日函數(shù)式子已經(jīng)沒有了變量w，b，只有。從上面的式子得到 ，根據(jù) 即可求出w，然后通

在求得L(w,b,a)關(guān)于w和 b最小化，以及對的極大之后，最后一步則可以利用SMO算法求解對偶問題中的 日乘子。 上求最大值W的問題至 有趣的形式。首先就是關(guān)于我們的hyperne，對于一個(gè)數(shù)據(jù)點(diǎn)x進(jìn)行分類，實(shí)際上是通過把x帶入到 可（表示向量內(nèi)積），這一點(diǎn)至關(guān)重要，是之后使用Kernel進(jìn)行非線廣的基本前SupportingVector也在這里顯示出來——Supporting2.1.1Lagrangemultiplierxi0的（functionalmargin1），而對于非支持向量來說，functionalmargin1，因此紅顏色部分是大于零的，而又是非負(fù)的，為了滿足最大化，必須等于0。這也就SupportingVector的點(diǎn)的局限性。從1.5到上述所有這些東西，便得到了一個(gè) ummarginhyprner，這就是所謂的支持向量uppotVtorMachne當(dāng)然到目前為止我們的M還比較弱只能處理線性的情況過在得到了對偶dual形式之后通過l推廣到非線性的況就變成了一件非常容易的事情了(相信你還記得本節(jié)開頭所說的通過求解對偶問題得到最優(yōu)解，這就是線性可分條件下支持向量機(jī)的對偶算法，這樣做的優(yōu)點(diǎn)在于：一者對偶問題往往更容易求解；二者可以自然的引入核函數(shù)，進(jìn)而推廣到非線性分類問題)。咋處理呢？對于非線性的情況，SVM的處理方法是選擇一個(gè)核函數(shù)κ(?,?)，通過將數(shù)據(jù)映射到空間，來解決在原始空間中線性不可分的問題。。具體來說，性不可分的情況下，支持向量機(jī)首先在低中完成計(jì)算，然后通過核函數(shù)將輸入空間映射到特征空間，最終在特征空間中構(gòu)造出最優(yōu)分離超平面，從而把平面上本身不好分的非線性數(shù)據(jù)分開。如圖7-7所示，一堆數(shù)據(jù)在二無法劃分，從而映射到三里劃分：而在我們遇到核函數(shù)之前，如果用原始的方法，那么在用線性學(xué)習(xí)器學(xué)個(gè)非線性關(guān)?：X->F是從輸入空間到某個(gè)特征空間的映射，這意味著建立非線性學(xué)習(xí)器分為 ，這里φ是從X到內(nèi)積特征空間F的映射關(guān)于新的坐標(biāo)Z，這正是一個(gè) ne的方程！也就是說，如果我們做一個(gè)Kernel的細(xì)節(jié)之前，不妨再來看看這個(gè)例子映射過后的直觀例子。當(dāng)然，你我可能無法把5畫出來，不過由于我這里生成數(shù)據(jù)的時(shí)候就是用了特殊的情形，具體來說，我這里的超平面實(shí)際的方程是這個(gè)樣子（圓心在X2軸上的一個(gè)正圓）：因此我只需要把它映射到Z1=X21,Z2=X22,Z3=X2這樣一個(gè)三 以通過一個(gè)平面來分開的(pluskid：下面的gif動(dòng)畫，先用 Imagemagick拼貼成)：而其中的可以通過求解如下dual問題而得到的 腦把原來的數(shù)據(jù)映射到新空間中，再做線性SVM即可。不過事實(shí)上沒有這么簡單！其實(shí)么我們會得到19維的新空間，這個(gè)數(shù)目是呈性增長的，這給 大的，而且如果遇到無窮維的情況，就根本無從計(jì)算了。所以就需要Kernel出馬了，而 即是到前面說的 的映射，因此映射過后的內(nèi)積為 的結(jié)果是相等的，那么區(qū)別在于什么地方呢一個(gè)是映射到空間中，然后再根據(jù)內(nèi)積的進(jìn)行計(jì)算（說明：上面之中，最后的兩個(gè)式子，第一個(gè)算式，是帶內(nèi)積的完全平方式，可以回憶剛才提到的映射的維度，法已經(jīng)無法計(jì)算的情況下，后法卻Function)，例如，在剛才的例子中，我們的核函數(shù)為：核函數(shù)能簡化映射空間中的內(nèi)積運(yùn)算——?jiǎng)偤谩芭銮伞盨VM里需要計(jì)算的其 由如下dual問題計(jì)算而得這樣一來計(jì)算的問題就算解決了，避開了直接在空間中進(jìn)行計(jì)算，而結(jié)果卻是等價(jià)來，如果對于任意一個(gè)映射，想要構(gòu)造出對應(yīng)的核函數(shù)就很了。（R1，d2）。該空間的維度是，其中是原始空間的維度 的權(quán)重實(shí)際上衰減得非?？?，所以實(shí)際上（數(shù)值上近似一下）相當(dāng)于一個(gè)低維的數(shù)之一。下圖所示的例子便是把低維線性不可分的數(shù)據(jù)通過核函數(shù)映射到了高線性這實(shí)際上就是原始空間中的內(nèi)積這個(gè)核存的主要目的是使得映射后空間中的問題和映射前空間中的問題兩者在形式上統(tǒng)一起來了意思是說，咱們有的時(shí)候，寫代碼，或?qū)懙臅r(shí)候，只要寫個(gè)模板或通用表達(dá)式，映射到空間中去(如上文2.2節(jié)最開始的那幅圖所示，映射到空間后，相關(guān)但進(jìn)一步，如果凡是遇到線性不可分的樣例，一律映射到空間，那么這個(gè)維大小是會高到可怕的(19維乃至無窮維的例子)現(xiàn)在了上，也就如上文所說的避免了直接在空間中的復(fù)雜計(jì)算。最后這里的一個(gè)例子舉例說明下核函數(shù)解決非線性問題的直觀效果來把羊群圍起來但是應(yīng)該建在哪里呢？你很可能需要依據(jù)牛群和狼群的位置建SVMOK，不再做過多介紹了，對核函數(shù)有進(jìn)一步的，還此文outliers用Kernel方法對原來的線性SVM進(jìn)行了推廣，使得非線性的的情況也能處理。雖然通過映射將原始數(shù)據(jù)映射到空間之后，能夠線性分隔的概率大大增加，但是對于某正常位置很遠(yuǎn)的數(shù)據(jù)點(diǎn)，我們稱之為outlier，在我們原來的SVM模型里，outlier的存在有可能造成很大的影響，因?yàn)槌矫姹旧砭褪菙?shù)幾個(gè)supportvector組成的，如果這些supportvector里又存在outlier的話，其影響就很大了。例如下圖：用黑圈圈起來的那個(gè)藍(lán)點(diǎn)是一個(gè)outlier，它偏離了自己原本所應(yīng)該在的那個(gè)半空間，outlier的出現(xiàn)，導(dǎo)算精確坐標(biāo)），marginoutlier再往右上移動(dòng)一些距離的話，無法構(gòu)造出能將數(shù)據(jù)分開的超平面來。outlier支持向量SV，同時(shí)，對于不同的支持向量，日參數(shù)的值也不同，如此篇 ScaleMachineLearning》中的下圖所示：個(gè)數(shù)，即數(shù)據(jù)集大小；對于outline數(shù)據(jù)和內(nèi)部的數(shù)據(jù)值為1/L。請參看本文參考51條。outlier其中稱為松弛變量(slackvariable)，對應(yīng)數(shù)據(jù)點(diǎn)允許偏離的functionalmargin的量。當(dāng)然，如果我們運(yùn)行任意大的話，那任意的超平面都是符合條件的了。所以，我們在原來的目標(biāo)函數(shù)后面加上一項(xiàng)，使得這些的總和也要最小：其中是一個(gè)參數(shù)，用于控制目標(biāo)函數(shù)中兩項(xiàng)（“尋找margin最大的超平面”和“保證數(shù)據(jù)點(diǎn)偏差量最小”）之間的權(quán)重。注意，其中是需要優(yōu)化的變量（之一），而是用之前的方法將限制或約束條件加入到目標(biāo)函數(shù)中得到新的日函數(shù)如下所示分析方法和前面一樣，轉(zhuǎn)換為另一個(gè)問題之后，我們先讓針對、和最小化 帶回并化簡，得到和原來一樣的目標(biāo)函數(shù)不過，由于我們得到而又有（作為Lagrange的條件），因此有，所以整個(gè)dual問題現(xiàn)在寫作把前后的結(jié)果對比一下（錯(cuò)誤修正DualformulationMinimize可以看到唯一的區(qū)別就是現(xiàn)在dualvariable多了一個(gè)上限。而Kernel化的非線性形式也是一樣的，只要把換成即可。這樣一來，一個(gè)完整的，可以處理線性和非線性并能噪音和outliers的支持向量機(jī)才終于介紹完畢了。行文至此，可以做個(gè)小結(jié)，確的說，SVM它本質(zhì)上即是一個(gè)分類方法，用w^T+b定義分類函數(shù)，于是求w、b，為尋最大間隔，引出1/2||w||^2，繼而引入日因子，化為對日乘子a的求解（求解過程中會涉及到一系列最優(yōu)化或凸二次規(guī)劃等問題），w.baaSMO，至于核函數(shù)，是為正如在他的著作《數(shù)理統(tǒng)計(jì)學(xué)簡史》的第4章、最小二乘法中所講：在科研3.13.2mercer3.33.43.5節(jié)、SMO3.6SVM這個(gè)感知機(jī)算法是1956年，年代久遠(yuǎn)，依然影響著，當(dāng)然，可以肯定的是，下面，舉個(gè)例子。如下圖所示，憑我們的可以看出，圖中的紅線是最優(yōu)超平面，藍(lán)次呢？Novikoff定理告訴我們當(dāng)間隔是正的時(shí)候感知機(jī)算在有限次數(shù)的迭代中收斂也 Novikoff定理如果分類超平面存在,僅需在序列 可知,迭代次數(shù)與對應(yīng)大分類間隔。OK1.3.2節(jié)開頭的內(nèi)容么？如下：“上的對應(yīng)的為x0，由于w是垂直于超平面的一個(gè)向量，為樣本x到分類間隔的距離，我們有”大分類間隔超平面。此外，Novikoff定理的證明請見這里。、MercerMercer定理：如果函數(shù)K是 上的映射（也就是從兩個(gè)n維向量映射到Mercer定理，先要了解什么是半正定矩陣，要了解什么是半正定矩陣，先正如@Copper_PKUSVM的分類效果中起了重要的作用，最后這里有個(gè)tutorial。在本文1.0節(jié)有這么一句話“支持向量機(jī)(SVM)是90年代中期發(fā)展起來的基于統(tǒng)計(jì)學(xué)習(xí)理論的一種F中選L(Y,f(X))。常用的損失函數(shù)有以下幾種（基本自《統(tǒng)計(jì)學(xué)習(xí)方法》SVM，boosting，LR等算法，可能會有不同收獲”。OK，關(guān)于統(tǒng)計(jì)學(xué)習(xí)方法的問題，請參看此文consistencyofclassificationmethodsbasedonconvexriskminimization》。各種算法中常率的“”此外還有另外一篇Statisticalysisofsomemulti-categorylargeSVM使用的損失函數(shù)分析的很透徹。既然本節(jié)開始之前提到了最小二乘法，那么下面《正態(tài)分布的前世今生》里的內(nèi)容有效的最小二乘法是勒讓德在1805年的，基本思想就是認(rèn)為測量中有誤差，所以勒讓德 中對最小二乘法的優(yōu)良性做了幾點(diǎn)說明 止某一個(gè)誤差取得支配地位,求解 。最小二乘法之后很快得到了大家的認(rèn)可接受，并迅速的在數(shù)據(jù)分析實(shí)踐中被廣泛使用不過歷史上又有人把最小二乘法的發(fā)明歸功于這又是怎么一回事呢在1809年也了最小二乘法，并且聲稱自己已經(jīng)使用這個(gè)方法多年發(fā)明了小行星定位的數(shù)。什么是一元線性模型呢？請?jiān)试S我這里的內(nèi)容，先來梳理下幾個(gè)基本概念對于二線性是一條直線；對于三線性是一個(gè)平面，對于空間線性（Xn，Yn）n個(gè)點(diǎn)，可以使用無數(shù)條曲線來擬合。要求樣本回歸函數(shù)盡最常用的是普通最小二乘法（OrdinaryLeastSquare，OLS）：所選擇的回歸模型應(yīng)ei為樣本（Xi,Yi）的誤差。Q：Q0SVM問題何等相似，尤其是定義損失函數(shù)，而后通過偏導(dǎo)求得極值。 請參看的《數(shù)理統(tǒng)計(jì)學(xué)簡史》的第4章、最小二乘法1998年，Research的JohnC. tt在 AFastAlgorithmforTrainingSupportVectorMachines》中提出針對上述問題的解法：SMO算法，它很快便成為最快的二次規(guī)劃優(yōu)化算法，特別是在針對線性SVM和數(shù)據(jù)稀疏時(shí)性能接下來，咱們便參考John 注：這個(gè)u與我們之前定義 實(shí)質(zhì)是一樣的 通過引入日乘子轉(zhuǎn)換為對偶問題后，得：且min轉(zhuǎn)化為max的問題，且yi也與之前 后，模型修改為下面要解決的問題是：在上求上述目標(biāo)函數(shù)的最小值。為了求解這些乘子，每次從中任意抽取兩個(gè)乘子和，然后固定和以外的其它乘子，使得目標(biāo)函數(shù)只是關(guān)于和的函數(shù)。這樣，不斷的從一堆乘子中任意抽為了解決這個(gè)子問題，首要問題便是每次如何選取和。實(shí)際上，其中一個(gè)乘子是違KKT條件最嚴(yán)重的，另外一個(gè)乘子則由另一個(gè)約束條件選取。根據(jù)KKT條件可以得出目標(biāo)函數(shù)中取值的意義這里的還是日乘子對于第1種情況，表明是正常分類，在間隔邊界內(nèi)部（我們知道正確分類的點(diǎn)）；對于第2種情況，表明了是支持向量，在間隔邊界上對于第3種情況，表明了是在兩條間隔邊界之間KKT3個(gè)條件都得滿足，以下幾種情況出現(xiàn)將會出現(xiàn)<=1但是<C則是不滿足的，而原本>=1但 >0則是不滿足的，而原 =1但 =0或 =C則表明不滿足的，而原本應(yīng)該是 KKT條件的此外，更新的同時(shí)還要受到第二個(gè)約束條件的限制， 因此，如果假設(shè)選擇的兩個(gè)乘子和，它們在更新之前分別是、，更新之后 ，那么更新前后的值需要滿足以下等式才能保證和為0的約束：其中，是常數(shù)兩個(gè)因子不好同時(shí)求解，所以可先求第二個(gè)乘子的解（），得到的解（）之后，再用的解（）表示的解（）。為了求 和這兩個(gè)約束條件，求取的取值范圍。當(dāng)y1!=y2時(shí)，根據(jù) 有，，如下圖所示：當(dāng)y1=y2時(shí)同樣根據(jù) 所以有，，如下圖所示：如此，根據(jù)y1和y2異號或同號，可得 的上下界分別為 因此可以用