暫時先寫個SVM的一步步的推導，應用場景收毫，模型參數(shù)攻走，優(yōu)缺點等復習完了再好好總結。

一此再、支持向量機（SVM）

1.1昔搂、大致的思路

1.1.1由邏輯回歸，引出SVM输拇。（把邏輯回歸的判別模型變化一下摘符，就是SVM的判別模型）

如上圖，邏輯回歸學到的就是中間的那條線（學習過程就是不斷地調整直線的過程）策吠，強調所有點盡可能地遠離中間那條線逛裤。考慮了全局猴抹，但是也可能使一部分點靠近中間線來換取另外一部分點更加遠離中間線带族。后果就是對于其中一些分類的點如c點，分類正確的確信度并不高蟀给。

由此引出SVM：我只關心局部（不關心已經遠離的點 ）蝙砌，也就是阳堕，我讓距離超平面最近的點的幾何間距最大化，就提高了所有點的確信度择克，我的分類就很可靠了恬总。

1.1.2，對邏輯回歸做一下變化肚邢，引出函數(shù)間隔與幾何間隔

邏輯回歸的判別模型壹堰，取決于θ^Tx（盡管最后是映射到0-1區(qū)間），θ^Tx大于零道偷，說明p>0.5缀旁，是正例。

用w^Tx+b代替θ^Tx勺鸦，并對g(z)做一個簡化并巍，將其簡單映射到類別標簽y=1和y=-1上。

于是换途，暫時可以讓w^Tx+b作為SVM分類器的判別模型懊渡，w^Tx+b大于零，說明是正例军拟，反之為負例剃执。（后面會 對幾何間隔做一個限制，到時就是和1進行比較了懈息。）

這樣肾档，y（w^Tx+b）就能代表分類正確情況下，該樣例的判定類別的確信度辫继，正負例的情況下都是正數(shù)怒见，越大越好。

函數(shù)間隔
對于所有的樣例來說姑宽，自然是確信度遣耍，越大越好。但是上面的y（w^Tx+b）可以通過調整參數(shù) w 和 b讓其無窮大炮车， 這樣不好不好舵变。

幾何間隔
我們真正關心的，其實是“幾何上”的點到平面的距離瘦穆，是可以用幾何知識推理出來的幾何間隔纪隙。而不是一開始人們想當然定義的函數(shù)間隔。

通過幾何與向量的運算扛或，可以得到幾何間隔的表示：

幾何間隔就是函數(shù)間隔除以∥w∥绵咱，而函數(shù)間隔實際上就是，只是人為定義的一個間隔度量告喊，而幾何間隔才是直觀上的點到超平面的距離麸拄。

1.1.3 最優(yōu)化 間隔分類器 （就是找到最優(yōu)的超平面使得幾何間隔最大）

我們想要找到最大的幾何間隔，并且已經默認的是黔姜，所有樣例進行y（w^Tx+b）運算得到的距離拢切，都會大于函數(shù)間隔（定義），所以秆吵，得到目標函數(shù)為：

為了計算方便 淮椰，并且使w和b能夠有唯一的確定值，去去哦們將全局的函數(shù)間隔（分子）定義為1纳寂，并且把目標函數(shù)轉換成二次的凸函數(shù)主穗，得到

至此

• 1、已經得到SVM的判別模型：w^Tx_i + b 毙芜。參數(shù)就是w和b忽媒。
  學習完參數(shù)以后，新來的樣例作為x_i腋粥，得到結果大于1晦雨，說明在超平面上面，所以是正例隘冲。反之亦然闹瞧。

• 2、SVM的初步目標函數(shù)展辞，就是所有樣例的幾何間隔盡可能的大

• 3奥邮、 優(yōu)化方法勒？
  上面的目標函數(shù)并不好求罗珍，所以需要引入對偶問題洽腺，又因為此目標函數(shù)是凸規(guī)劃問題，所以最優(yōu)解（w）滿足KKT條件 是 強對偶條件的 充分必要條件靡砌。

也就是說已脓，求得對偶問題的最優(yōu)解，也就是原問題的最優(yōu)解了通殃。

1.1.4 最優(yōu)解 （也就是找到了最有間隔分類器）

上面引入對偶的優(yōu)點：

• 1度液、對偶問題往往更容易求解
• 2、可以自然的引入核函數(shù)画舌，進而推廣到非線性分類問題堕担。
• 3、 將w的計算提前并消除w曲聂，最終使得優(yōu)化函數(shù)變?yōu)槔窭嗜粘俗拥膯我粎?shù)優(yōu)化問題

---------------------------------------------------------------------------------------------

實線是最大間隔超平面霹购，假設×號的是正例，圓圈的是負例朋腋。在虛線上的點就是函數(shù)間隔是1的點齐疙，他們前面的系數(shù)α_i>0膜楷，這三個點被稱作 支持向量。

----------------------------------------------------------------------------------------------

開始求解目標函數(shù)（也是一般利用對偶求解目標函數(shù)的步驟）

• 1贞奋、 先把上面目標函數(shù) 構造成拉格朗日函數(shù)L
• 2赌厅、根據(jù)題意，得到原問題的對偶問題d=max min L
• 3轿塔、最里面的先求特愿，所以先求L的最小值，此時max中的參數(shù)是固定的
  L對w和b求偏導數(shù)勾缭，解得

此時求得w和b（用α表示）揍障，也就是min L的解已經求出，帶回對偶形式俩由，接著解max毒嫡，并且此時只有一個參數(shù)α了，解出α采驻，對偶問題就能完美解決了审胚。

即參數(shù)w用α表示的形式。b可以先不用管礼旅，因為將上式帶入max中后 膳叨，利用KKT的第三個條件，即可消去關于b的多項式痘系。

• 4菲嘴、將上式子帶回L中，就得到了min L

由于最后一項是0汰翠，因此簡化為

• 5龄坪、求 max （min L）
  min L已經求得（就是上式），接著就是最大化過程 max （min L）

至此复唤，若是 求出了α健田，則對偶問題完美解決了，又因為前面的充要條件佛纫，也就說明妓局，原問題完美解決了。

• 6呈宇、假設α 已經求出好爬。
  其實 α 的求出也有些復雜，所以需要用后面的SMO算法求得甥啄，現(xiàn)在為了快速理解 SVM存炮，先假設 α已經求出。

• 7、α已經求出穆桂，解用α表示宫盔。

假設求得了α_i 就能根據(jù)求導得到的結果

求得w，然后就能得到b享完。

b 就是 距離超平面最近的正的函數(shù)間隔要等于離超平面最近的負的函數(shù)間隔飘言。 （其實，由前面的那個x和圈的圖驼侠，可以認為b就是截距，這個截距b等于上下兩條虛線的截距的平均值谆吴。）

注意倒源，這里的w，b句狼，alpha都是 向量笋熬，都是m維的向量

----------------------------------------------------------------------------------------------

1.1.5 、對‘引入對偶問題的第三個優(yōu)點的解釋’ ： 可以將w的計算提前并消除w

目標函數(shù)的解已經求得腻菇，最終目標還是判別樣例的標簽胳螟！

由于前面求解中得到

用α_i代替w帶入判別模型w^Tx+b启具，得到：

也就是說层宫，利用判別模型對新來樣本進行判別時，要先求得參數(shù) w蛛勉，b丘薛，再做一次線性運算 w^Tx+b嘉竟，根據(jù)結果的正負來判斷正負例。

優(yōu)點一
現(xiàn)在有了alpha洋侨，不需要求出w（后面會說舍扰，b=w^Tx - y，這幾個都是向量）

優(yōu)點二
另外希坚，那有人會說边苹，與前面所有的樣本都做運算是不是太耗時了？其實不然裁僧，我們從KKT條件中得到个束，只有支持向量的α_i>0 （不等于零）其他情況α_i是等于零的。比如锅知，像前面那個x和圈的圖播急，新來的樣本只需要和三個支持向量做運算即可。

由此可以看到售睹，求出α_i以后桩警，只需要利用支持向量，就可以來判斷新來的樣例是正例還是負例了昌妹。也許這也是是為什么叫支持向量機吧捶枢。

經過上述所有這些東西握截，便得到了一個maximum margin hyper plane classifier，這就是所謂的支持向量機（Support Vector Machine）烂叔。 支持向量機器是最大化間隔超平面分類器谨胞。。wx+b

上面這個公式蒜鸡，為下面要提到的核函數(shù)（kernel）做了很好的鋪墊胯努。

1.2、核函數(shù)的登場

1.2.1逢防、核函數(shù)總結：

• 1. 實際中叶沛，我們會經常遇到線性不可分的樣例，此時忘朝，我們的常用做法是把樣例特征映射到高維空間中去灰署，映射到高維空間后，相關特征便被分開了局嘁，也就達到了分類的目的溉箕；
• 2. 但進一步，如果凡是遇到線性不可分的樣例悦昵，一律映射到高維空間肴茄，那么這個維度大小是會高到可怕的(甚至會到無窮維，維度爆炸)但指。

（比如就是將原始空間特征的一階二階所有的組合作為新空間的維度独郎，X=(x1,x2)就會變成了 5維，X=(x1,x2x,x3)就會變成19維枚赡，當然不是唯一的氓癌，可以有很多別的映射函數(shù)，比如一階二階三階的贫橙，一般多項式的各種映射函數(shù)贪婉。）

• 3. 此時，核函數(shù)就隆重登場了卢肃，核函數(shù)絕就絕在它在低維上進行計算疲迂，但是和 采用第二步（映射到高維以后進行運算）計算得到的結果是相同的，效果也是一樣的莫湘。
     但是尤蒿，相比于第二步（映射到高維以后進行運算），核函數(shù)的優(yōu)點就體現(xiàn)出來了：避免了直接在高維空間中的復雜運算幅垮，不需要顯示的寫出映射函數(shù)Φ（高維）腰池，大大降低了時間復雜度。

1.2.2、核函數(shù)的使用：

怎么讓SVM利用核函數(shù)進行分類呢示弓？

只需要將原來的內積替換成核函數(shù)就行了讳侨。值的判別也是同1進行比較。

1.2.2奏属、核函數(shù)的判定（即怎么判斷一個核函數(shù)是有效的）：

根據(jù)核函數(shù)的定義跨跨，交換內積前后順序，可以推出核函數(shù)矩陣是半正定的囱皿，
又因為勇婴，又Mercer定理（矩陣核函數(shù)是半正定的，那么K是一個有效核函數(shù)嘱腥。）

1.3 軟間隔的提出（從理想到現(xiàn)實）

1.3.1 從理想到現(xiàn)實

至此討論的都是理想狀況：

• 樣例線性可分時可以直接使用SVM進行分類
• 當樣例線性不可分時（比如同心圓的情況）咆耿，使用核函數(shù)來將特征映射到高維，這樣很可能就可分了爹橱。

但是也會出現(xiàn)不理想的情況：

• 離群點導致平面受到影響：

• 背叛點導致不可分：

此時就需要調整模型了，讓模型能夠容忍這些‘不安分’的點窄做，從理想狀況接近現(xiàn)實愧驱。

1.3.2 調整模型（加入松弛變量）

然后根據(jù)引入對偶問題中的做法，得到最終的需要優(yōu)化的結果椭盏，也是最接近現(xiàn)實的目標函數(shù)：

最優(yōu)解必須滿足KKT條件组砚，而原問題已經做了調整，所以最優(yōu)解α 滿足的KKT條件也需要進行調整掏颊，得到結果如下：

至此糟红，算是得到了軟間隔的SVM的目標函數(shù)，并且此時的 α 向量滿足KKT條件乌叶，是對偶問題的最優(yōu)解盆偿，也是原問題的最優(yōu)解

現(xiàn)在是一步到位，認為α 向量是最優(yōu)解准浴，所以得到了其相應的KKT條件事扭。但事實是，此時α 向量一定不是最優(yōu)解乐横，求解目標函數(shù)的過程中求橄， 就是調整α 向量中的各個參數(shù)，讓其滿足KKT條件的過程葡公。

1.4 SMO算法

1.4.1 選取 α₁ 和 α₂ 以后罐农，更新這兩個參數(shù)

• 1、 將拉格朗日公式用α₁ 和 α₂ 表示
• 2催什、因為此時α₁ 和 α₂增加了一個約束條件涵亏，所以需要更新上下界，為后期求出這兩個參數(shù)以后，做限制準備溯乒。
• 3夹厌、接著求解，α₁ 用α₂ 表示裆悄，得到只含有α₂ 的函數(shù)
• 4矛纹、 對α₂ 求導，得到α₂ 的解光稼，再根據(jù)2所說滿足上下界
• 5或南、 α₁ 的解用α₂的解表示

1.4.2 怎么選取這兩個參數(shù)？

-------------------------------------------------------------------------------------