第五部分：支持向量機

本部分詳述支持向量機的算法。支持向量機是最好的（許多人相信是最好的）“現(xiàn)成的”監(jiān)督學(xué)習(xí)算法之一别渔。為了講述SVM的故事，我們需要首先討論邊緣空白以及用大的“間隔”分離數(shù)據(jù)的想法惧互。接下來哎媚，我們將討論最優(yōu)邊距分類器，它將要求我們先了解拉格朗日對偶喊儡。我們還將看到核拨与，它提供了一種在非常高維（如無窮維）的特征空間中有效地應(yīng)用SVM的方法，最后艾猜，我們將用SMO算法結(jié)束故事买喧，它給出了SVM的有效實現(xiàn)。

邊緣空白：直覺

我們將通過談?wù)撨吘壙瞻讈黹_始我們關(guān)于SVM的故事箩朴。本節(jié)將給出關(guān)于邊緣空白和對我們預(yù)測的“信心”的直觀理解岗喉；這些想法將在第3節(jié)正式提出。

考慮對數(shù)幾率回歸炸庞，p(y = 1|x;θ)由h(x)=g(θ'x)建模得出钱床。如果h(x)大于等于0.5，將預(yù)測為正例1埠居，或者等價的查牌，僅僅當θ'x大于等于0時。對于一個正例訓(xùn)練樣本滥壕，θ'x越大纸颜，h(x)也會越大，這樣我們的預(yù)測“信心”程度越高绎橘，標簽就是1正例胁孙。因此，非正式地称鳞，我們可以認為我們的預(yù)測是非常有信心的涮较，如果θ'x遠大于0，y=1冈止；反之亦然狂票。給定一個訓(xùn)練集，同樣非正式地熙暴，如果我們能夠找到θ闺属，使得對于所有的正例y=1,θ'x遠大于0慌盯；使得對于所有的負例y=0,θ'x遠小于0，這樣的擬合是非常好的掂器，因為對于所有的訓(xùn)練實例這將反映一個非常自信的分類器亚皂。這似乎是一個不錯的目標，我們很快將使用邊緣空白的概念將這一想法正式化国瓮。

對于不同類型的直觀感受孕讳，考慮下圖，其中x表示正訓(xùn)練實例巍膘，o表示負訓(xùn)練實例厂财，還顯示了判定邊界（這是方程θ'x=0給出的直線，也稱為分離超平面）峡懈，以及被標記為A璃饱、B和C三點。

注意到點A距離決策邊界最遠肪康。如果我們被要求對A處的y值進行預(yù)測荚恶，那么我們似乎應(yīng)該很有信心預(yù)測y=1。相反地磷支，點C非常接近決策邊界谒撼，雖然它位于我們可以預(yù)測y=1的決策邊界一側(cè)，但是似乎只要對決策邊界稍作改變就可能很容易導(dǎo)致預(yù)測為y=0雾狈。因此廓潜，我們對A點的預(yù)測比C點的預(yù)測更有信心。點B介于這兩種情況之間善榛，更廣泛地說辩蛋，我們看到如果一個點遠離分離超平面，那么我們的預(yù)測可能明顯更有信心移盆。同樣悼院，非正式地，我們認為咒循，如果給定一個訓(xùn)練集据途，我們能夠找到一個決策邊界，它允許我們在訓(xùn)練示例上做出所有正確和有信心（意味著遠離決策邊界）的預(yù)測叙甸，那將是不錯的颖医。稍后我們將使用幾何邊距的概念將其正式化。

符號

為了使我們對SVM的討論更容易蚁署，我們首先需要引入一個新的符號來討論分類便脊。我們將考慮使用帶有標簽y和特征x的二元分類問題的線性分類器蚂四。從現(xiàn)在開始光戈，我們將使用y∈{-1,1}（而不是{0,1}）來表示類標簽哪痰。另外，我們不是用向量θ參數(shù)化我們的線性分類器久妆，而是使用參數(shù)w晌杰、b，并將我們的分類器表示為:

如果z大于等于零筷弦，g(z)等于1肋演；否則g(z)等于-1。這種[w烂琴，b]符號表示允許我們明確地將截距項b與其他參數(shù)分開處理爹殊。(我們也放棄了以前讓x0 = 1為輸入特征向量中的額外坐標的約定。)因此奸绷，b扮演先前θ0的角色梗夸，w扮演[θ1,...,θn] '的角色。

還要注意号醉，根據(jù)我們上面對g的定義反症，我們的分類器將直接預(yù)測1或-1(參見感知器算法)，而不首先通過估計y為1的概率的中間步驟(這是對數(shù)幾率回歸所做的)畔派。

函數(shù)間隔和幾何間隔

讓我們先介紹函數(shù)間隔和幾何間隔的概念铅碍。給定一個訓(xùn)練樣本(x(i),y(i))，我們根據(jù)訓(xùn)練樣本定義(w线椰，b)的函數(shù)間隔：

注意胞谈，如果y(i)= 1，那么為了使函數(shù)間隔變大(即憨愉，為了使我們的預(yù)測有信心和正確)呜魄，我們需要(w'x + b)是一個大的正數(shù)。相反地莱衩，如果y(i)= -1爵嗅，然后，為了使函數(shù)間隔變大笨蚁，我們需要(w'x + b)為一個大的負數(shù)睹晒。此外，如果y(i)(w'x + b) > 0括细，那么我們對這個例子的預(yù)測是正確的伪很。因此，大的函數(shù)間隔代表了自信和正確的預(yù)測奋单。

對于上面給出的g選擇的線性分類器(取{-1,1}中的值)锉试，然而，函數(shù)間隔的一個屬性使得它不是一個非常好的置信度量览濒。關(guān)于我們選擇的g函數(shù)呆盖，我們注意到如果我們用2w代替w而用2b替換b拖云，那么因為g(w'x + b)= g(2w'x + 2b)，所以這根本不會改變最后的預(yù)測結(jié)果hw,b(x)应又。因為g僅僅依靠(w'x + b)的符號宙项，而不是幅度。然而株扛，用(2w,2b)代替(w,b)也會導(dǎo)致我們的函數(shù)間隔變?yōu)橹暗膬杀队瓤稹Ｒ虼耍ㄟ^成倍放大w和b的值洞就，我們可以使函數(shù)間隔任意大盆繁，而不會真正改變?nèi)魏斡幸饬x的東西。直觀地說旬蟋，因此強加某種歸一化條件可能是有意義的改基，例如||w||_2 = 1； 也就是說咖为，我們可以用(w / || w ||_2秕狰，b / || w ||_2)代替(w，b)躁染，而是考慮(w / || w ||_2鸣哀，b / || w ||_2)的函數(shù)間隔。 我們稍后再回過頭來看看吞彤。

對于給定訓(xùn)練集S = {(x(i)我衬，y(i))；i = 1,...,m}饰恕，我們將(w挠羔，b)的函數(shù)間隔定義為各個訓(xùn)練樣本中的最小函數(shù)間隔。如下所示：

接下來埋嵌，我們將討論幾何間隔破加。考慮下面的圖片：

上面顯示了對應(yīng)于(w雹嗦，b)的決策邊界以及向量w范舀。請注意，w與分離超平面正交了罪《Щ罚考慮A處的點，其表示具有標簽y(i) = 1的一些訓(xùn)練樣本的輸入x(i)泊藕。它與決策邊界的距離γ(i)由線段AB給出辅辩。

我們怎樣才能找到γ(i)的值？w / || w || 是指向與w相同方向的單位長度向量。由于A表示成x(i)玫锋，因此我們發(fā)現(xiàn)點B由x(i)-γ(i)·w / || w ||給出蛾茉。但這一點位于決策邊界上，決策邊界上的所有點x都滿足方程w'x + b = 0景醇。因此：

進一步可得：

這是針對圖中A的正訓(xùn)練樣本的情況得出的，其中處于決策邊界的“正”側(cè)是好的吝岭。更一般地三痰，我們將訓(xùn)練樣本(x(i)，y(i))的(w窜管，b)的幾何間隔定義為：

請注意散劫，如果|| w || = 1，那么函數(shù)間隔等于幾何間隔 - 這就為我們提供了一種方法來聯(lián)系這兩種不同的間隔概念幕帆。此外获搏，幾何間隔對于重新縮放參數(shù)是不變的; 即，如果我們用2w代替w失乾，用2b代替b常熙，則幾何間隔不會改變。事實上碱茁，這將在以后派上用場裸卫。具體來說，由于參數(shù)縮放的這種不變性纽竣，當試圖將w和b擬合到訓(xùn)練數(shù)據(jù)時墓贿，我們可以對w施加任意縮放約束而不改變?nèi)魏沃匾臇|西。

最后蜓氨，給定訓(xùn)練集S = {(x(i)聋袋，y(i))；i = 1,...,m}穴吹，我們還將(w幽勒，b)相對于S的幾何間隔定義為各個訓(xùn)練樣本中幾何間隔中的最小值：

最優(yōu)間隔分類器

給定一個訓(xùn)練集，從我們之前的討論中可以看出港令，一個自然的需求是試圖找到一個最大化(幾何)間隔的決策邊界代嗤，因為這將反映出對訓(xùn)練集的一個非常有信心的預(yù)測和一個良好的“擬合” “對訓(xùn)練數(shù)據(jù)。具體而言缠借，這將導(dǎo)致分類器用“間隙”(幾何間隔)將正和負訓(xùn)練樣本分開干毅。

現(xiàn)在，我們假設(shè)我們得到一個可線性分離的訓(xùn)練集泼返；即硝逢，可以使用一些分離超平面分離正例和負例。 我們?nèi)绾握业竭_到最大幾何間隔的那個？ 我們可以提出以下優(yōu)化問題：

我們希望最大化γ渠鸽，其中每個訓(xùn)練樣本具有至少γ大小的函數(shù)間隔叫乌。||w|| = 1約束還確保函數(shù)間隔等于幾何間隔，因此我們也保證所有幾何間隔至少為γ徽缚。 因此憨奸，解決該問題將導(dǎo)致(w，b)相對于訓(xùn)練集具有最大可能的幾何間隔凿试。

如果我們能解決上面的優(yōu)化問題排宰，我們就完成了。 但是“||w|| = 1“約束是一個討厭的(非凸的)那婉，這個問題肯定不是我們可以插入標準優(yōu)化軟件來解決的任何格式板甘。所以，讓我們嘗試將問題轉(zhuǎn)化為更好的問題详炬⊙卫啵考慮：

在這里，我們將最大化γ / || w ||呛谜，但函數(shù)間隔都至少為γ在跳，這將給出我們想要的答案。而且隐岛，我們已經(jīng)擺脫了我們不喜歡的約束 || w || = 1硬毕。缺點是我們現(xiàn)在有一個討厭的(再次，非凸)目標函數(shù)礼仗；而且吐咳，我們?nèi)匀粵]有任何可以解決這種形式的優(yōu)化問題的現(xiàn)成軟件驮樊。

我們繼續(xù)吧鲁驶。 回想一下我們之前的討論贬芥，我們可以在w和b上添加任意縮放約束而不改變?nèi)魏螙|西巨税。 這是我們現(xiàn)在使用的關(guān)鍵想法宜肉。 我們將引入縮放約束即w已球，b相對于訓(xùn)練集的函數(shù)間隔必須為1：

由于將w和b乘以某個常數(shù)導(dǎo)致函數(shù)間隔乘以相同的常數(shù)赁酝，這確實是縮放約束葵姥，并且可以通過重新縮放w象浑，b來滿足蔫饰。將其插入上述問題，并注意到最大化γ/ || w || = 1 / ||w||與最小化||w||^2相同愉豺，我們現(xiàn)在有以下優(yōu)化問題：

我們現(xiàn)在已經(jīng)將問題轉(zhuǎn)化為可以有效解決的形式篓吁。 以上是具有凸二次目標和僅線性約束的優(yōu)化問題。 它的解決方案為我們提供了最佳間隔分類器蚪拦，可以使用商業(yè)二次規(guī)化代碼來解決該優(yōu)化問題杖剪。

雖然我們可以在這里解決問題冻押，但我們要做的是做一個題外話來討論拉格朗日對偶性。 這將導(dǎo)致我們的優(yōu)化問題的雙重形式盛嘿，它將在允許我們使用內(nèi)核獲得最佳間隔分類器以在非常高維空間中有效工作方面發(fā)揮關(guān)鍵作用洛巢。 雙重形式還將允許我們推導(dǎo)出一種有效的算法來解決上述優(yōu)化問題，該算法通常比通用QP軟件做得更好次兆。

拉格朗日對偶

讓我們暫時擱置SVM和最大間隔分類器稿茉，并討論解決約束優(yōu)化問題。

考慮以下形式的問題：

你們中的一些人可能還記得拉格朗日乘數(shù)的方法如何用來解決它芥炭。在這種方法中漓库，我們將拉格朗日定義為：

在這兒，βi稱為拉格朗日乘子蚤认。然后我們會找到并將偏導(dǎo)數(shù)設(shè)為零：

來解w和β米苹。

在本節(jié)中糕伐，我們將此概括為約束優(yōu)化問題砰琢，其中我們可能存在不等式以及等式約束。 由于時間限制良瞧，我們不能真正在本節(jié)課中詳細的研究拉格朗日對偶理論陪汽，但我們將給出主要思想和結(jié)果，然后將應(yīng)用于我們的最優(yōu)間隔分類器的優(yōu)化問題褥蚯。

考慮以下內(nèi)容挚冤，我們將其稱為原始優(yōu)化問題：

為了解決這個問題，我們首先定義廣義拉格朗日量：

這兒赞庶，αi’训挡、βi’是拉格朗日乘子∑缜浚考慮下面等式：

這里澜薄，“P”下標代表“原始”。讓我們給一些w摊册， 如果w違反任何原始約束(即肤京，對于某些 i，gi(w)> 0或hi(w)不等于0)茅特，那么你應(yīng)該能夠驗證：

相反忘分，如果對于特定的w值確實滿足約束，則θP(w)= f(w)白修。因此:

因此妒峦，對于滿足原始約束的所有w，θP與我們的問題中的目標具有相同的值兵睛，并且如果違反約束則為正無窮大舟山。因此绸狐，如果我們考慮最小化問題：

我們看到它與我們原始問題是同一個問題，并且具有相同的解決方案累盗。為了以后的使用寒矿，我們還將目標的最優(yōu)值定義為:

我們稱之為原始問題的解。

現(xiàn)在我們再來看一個稍微不同的問題若债，我們定義：

這兒D下標代表對偶問題符相。還要注意，在θP的定義中蠢琳，我們對α啊终、β進行了優(yōu)化(最大化)，在這里我們相對于w做最小化傲须。
我們現(xiàn)在可以提出對偶優(yōu)化問題：

這與上面所述的原始問題完全相同蓝牲，只是現(xiàn)在交換了“max”和“min”的順序。我們還定義了對偶問題的最優(yōu)值：

原始和對偶問題是如何相關(guān)的泰讽？ 很容易證明這一點：

但是例衍，在某些條件下，我們會有:

這樣我們就可以解決對偶問題來代替原始問題已卸，讓我們看看這些條件是什么佛玄。

假設(shè)f和gi是凸的，hi是仿射的累澡。進一步假設(shè)約束gi是(嚴格地)可行的梦抢；這意味著存在一些w使得所有i的gi(w)<0。

在我們的上述假設(shè)下愧哟，肯定存在w*奥吩、α*、β*蕊梧，使得w*是原始問題的解霞赫，α*、β*是對偶問題的解望几，而且p* = d* = L (w*绩脆，α*，β*)橄抹。 此外靴迫，w*、α*和β*滿足Karush-Kuhn-Tucker(KKT)條件楼誓，如下：

此外玉锌，如果某些w*、α*疟羹、β*滿足KKT條件主守，那么它也是原始和對偶問題的解決方案禀倔。

我們請注意等式(5)，這被稱為KKT對偶互補條件参淫。具體來說救湖，它暗示如果αi*> 0，那么gi(w*)= 0涎才。(即鞋既，“gi(w)≤0”約束是有效的，這意味著它保持平等而不是不等式耍铜。)稍后 邑闺，這將是證明SVM只有少量“支持向量”的關(guān)鍵；當我們討論SMO算法時棕兼，KKT對偶互補條件也將為我們提供收斂性測試陡舅。

最優(yōu)間隔分類器

以前，我們提出了以下(原始)優(yōu)化問題來找到最優(yōu)間隔分類器：

我們可以將約束寫成：

我們對每個訓(xùn)練樣本都有一個這樣的約束伴挚。 請注意KKT對偶互補條件靶衍，我們將只有 αi>0 用于函數(shù)間隔恰好等于1的訓(xùn)練樣例≌吕穑考慮下圖摊灭，其中分離超平面的最大間隔為用實線表示咆贬。

間隔最小的點恰好是最接近決策邊界的點败徊；這里，這些是位于與決策邊界平行的虛線上的三個點（一個負面和兩個正面示例）掏缎。 因此皱蹦，在我們的優(yōu)化問題的最優(yōu)解決方案中，只有三個αi眷蜈，即對應(yīng)于這三個訓(xùn)練樣本的αi將是非零的沪哺。 這三個點在這個問題中被稱為支持向量，支持向量的數(shù)量可以比訓(xùn)練集的數(shù)量小得多的事實將在以后有用酌儒。

讓我們繼續(xù)辜妓， 展望未來，當我們開發(fā)問題的對偶形式時忌怎，需要注意的一個關(guān)鍵想法是我們將嘗試僅根據(jù)輸入特征空間中各點之間的內(nèi)積<x(i),x(j)>來編寫算法籍滴。 當我們應(yīng)用內(nèi)核技巧時，根據(jù)這些內(nèi)積表達我們的算法這一事實將是關(guān)鍵榴啸。

當我們?yōu)閮?yōu)化問題構(gòu)造拉格朗日時孽惰，我們得到：

注意，只有“αi”但沒有“βi”拉格朗日乘子鸥印，因為問題只有不等式約束勋功。

讓我們找到問題的對偶形式坦报。 要做到這一點，我們需要首先最小化L(w狂鞋，b片择，α)相對于w和b(對于固定α)，得到對偶形式骚揍，我們將對L求導(dǎo)(相對于w和b)构回，然后令導(dǎo)數(shù)為零。 我們有：

進一步可得：

對b求導(dǎo)：

如果我們在等式(9)中采用w的定義并將其插回拉格朗日(等式8)疏咐，并簡化纤掸，我們得到:

但是根據(jù)公式(10)，最后一項必須為零浑塞，因此我們得到:

回想一下借跪，我們通過最小化L相對于w和b來得到上面的等式。將這與約束αi≥0(我們一直有)和約束(10)放在一起酌壕，我們得到以下對偶優(yōu)化問題：

你還應(yīng)該能夠驗證在我們的優(yōu)化問題中確實滿足p* = d*和KKT條件(等式3~7)所需的條件掏愁。 因此，我們可以解決對偶問題代替解決原始問題卵牍。 具體來說果港，在上面的對偶問題中，我們有一個最大化問題糊昙，其中參數(shù)是αi辛掠。 我們稍后將討論我們將用于解決對偶問題的特定算法，但是如果我們確實能夠解決它(即释牺，找到最大化受到約束的W(α)的α)萝衩，那么我們可以使用等式(9)返回并找到作為α的函數(shù)的最優(yōu)w。找到w*后没咙，通過考慮原始問題猩谊，找到截距項b的最優(yōu)值也是很容易的：

在繼續(xù)之前，讓我們更仔細地看一下等式(9)祭刚，它給出了w的最佳值(α的最佳值)牌捷。 假設(shè)我們將模型的參數(shù)擬合到訓(xùn)練集，現(xiàn)在希望在新點x進行預(yù)測涡驮。 然后暗甥，我們將計算w'x + b，并且當且僅當大于零時遮怜，預(yù)測y = 1淋袖。 但是使用(9)，這個數(shù)量也可以寫成：

因此锯梁，如果我們找到αi即碗，為了進行預(yù)測焰情，我們必須計算僅依賴于x和訓(xùn)練集中的點之間的內(nèi)積的量。 此外剥懒，我們之前看到除了支持向量之外内舟，αi都將為零。 因此初橘，上面總和中的許多式子將為零验游，我們確實只需要找到x和支持向量之間的內(nèi)積(其中通常只有一小部分)，以便計算(13)并做預(yù)測保檐。

通過檢查優(yōu)化問題的對偶形式耕蝉，我們獲得了對問題結(jié)構(gòu)的重要洞察，并且還能夠僅根據(jù)輸入特征向量之間的內(nèi)積來編寫整個算法夜只。 在下一節(jié)中垒在，我們將利用此屬性將內(nèi)核應(yīng)用于我們的分類問題。 由此產(chǎn)生的算法扔亥，支持向量機场躯，將能夠在高維空間中有效地學(xué)習(xí)。

核

回到我們對線性回歸的討論中旅挤，我們遇到了一個問題踢关，其中輸入x是房子的居住面積，我們考慮使用特征x粘茄、x^2和x^3進行回歸以獲得立方函數(shù)签舞。 為了區(qū)分這兩組變量，我們將“原始”輸入值稱為問題的輸入屬性attributes(在本例中為x驹闰，居住面積)瘪菌。當它被映射到一組新的集合然后傳遞給學(xué)習(xí)算法時撒会，我們將這些新集稱為輸入特征features嘹朗。(不幸的是，不同的作者使用不同的術(shù)語來描述這兩件事诵肛，但我們會嘗試在這些注釋中使用這個術(shù)語屹培。)我們還將φ表示特征features映射，該映射從屬性attributes映射到特征features怔檩。 例如褪秀，在我們的例子中，我們有：

我們可能不想使用使用原始輸入屬性attributesx來應(yīng)用SVM薛训，而是使用某些特征features φ(x)來學(xué)習(xí)媒吗。 為此，我們只需要檢查我們之前的算法乙埃，并用φ(x)替換其中的x闸英。

由于算法可以完全根據(jù)內(nèi)積<x锯岖，z>編寫，這意味著我們將用<φ(x)甫何，φ(z)>替換所有這些內(nèi)積出吹。 具體來說，給定特征映射φ辙喂，我們定義相應(yīng)的內(nèi)核：

然后捶牢，之前在我們的算法中有<x，z>的地方巍耗，我們可以簡單地用K(x秋麸，z)替換它，我們的算法現(xiàn)在將使用特征φ學(xué)習(xí)炬太。

現(xiàn)在竹勉，給定φ，我們可以通過找到φ(x)和φ(z)并取其內(nèi)積來輕松計算K(x娄琉，z)次乓。 但更有趣的是，通常孽水，K(x票腰，z)的計算成本可能非常低廉，即使φ(x)本身的計算成本非常高(可能因為它是一個極高的維度向量)女气。在這樣的設(shè)置中杏慰，通過在我們的算法中使用計算K(x，z)的有效方法炼鞠，我們可以得到SVM在φ給出的高維特征空間中學(xué)習(xí)缘滥，但是不必明確地找到或表示向量φ(x)。
我們來看一個例子吧谒主。 假設(shè)x,z∈Rn朝扼，并考慮：

我們也可以這樣寫：

因此，我們看到K(x霎肯，z)=φ(x)'φ(z)擎颖，其中給出了特征映射φ(此處針對n = 3的情況)：

注意，雖然計算高維φ(x)需要O(n^2)時間观游，但是計算K(x搂捧，z)僅需要O(n)時間，n為輸入屬性的維度懂缕。

對于內(nèi)核允跑，也要考慮：

這對應(yīng)于特征映射，并且參數(shù)c控制xi(一次項)和xixj(二次項)項之間的相對加權(quán)。n==3特征映射如下所示：

更廣泛的說聋丝，內(nèi)核：

對應(yīng)于映射到特征空間(n+d,d)的特征荤崇。然而，盡管在這個O(n^d)維空間中工作潮针，計算K(x术荤，z)仍然只需要O(n)時間，因此我們永遠不需要在這個非常高維的特征空間中明確地表示特征向量每篷。

現(xiàn)在瓣戚，讓我們談?wù)剝?nèi)核略有不同的觀點。 直觀地焦读，(并且這種直覺有問題但是沒有關(guān)系)子库，如果φ(x)和φ(z)靠得很近，那么我們可能期望K(x矗晃，z)=φ(x)'φ(z)很大仑嗅。 相反，如果φ(x)和φ(z)相距很遠 - 比如幾乎彼此正交 - 則K(x张症，z)=φ(x)'φ(z)將很小仓技。 因此，我們可以將K(x俗他，z)視為對φ(x)和φ(z)有多相似的一些測量脖捻，或者x和z有多相似。

鑒于這種直覺兆衅，假設(shè)對于你正在研究的一些學(xué)習(xí)問題地沮，你已經(jīng)提出了一些函數(shù)K(x，z)羡亩，你認為它可能是x和z相似程度的合理量度摩疑。 例如，也許你選擇了:

這是x和z相似性的合理度量畏铆，當x和z接近時接近1雷袋，當x和z相距很遠時接近0。我們可以將這個K定義用作SVM中的內(nèi)核嗎及志？ 在這個特定的例子中片排，答案是肯定的。(這個內(nèi)核稱為高斯內(nèi)核速侈，對應(yīng)于無限維特征映射φ。)但更廣泛地說迫卢，給定一些函數(shù)K倚搬，我們?nèi)绾闻袛嗨欠袷且粋€有效的內(nèi)核; 也就是說，我們可以判斷是否有一些特征映射φ使得所有x,z的K(x乾蛤，z)=φ(x)'φ(z)每界？

現(xiàn)在假設(shè)K確實是對應(yīng)于某些特征映射φ的有效內(nèi)核捅僵。 現(xiàn)在，考慮一些有限的m點集合(不一定是訓(xùn)練集){x(1),...,x(m)}眨层，并且定義m×m矩陣K庙楚，使得其(i，j)元素-由Kij = K(x(i)趴樱，x(j))給出馒闷， 該矩陣稱為核矩陣。 請注意叁征，由于它們之間存在明顯的密切關(guān)系纳账，我們已經(jīng)重載了符號并使用K來表示內(nèi)核函數(shù)K(x，z)和內(nèi)核矩陣K捺疼。

現(xiàn)在疏虫，如果K是有效的核，則Kij = K(x(i)啤呼，x(j))=φ(x(i))'φ(x(j))=φ(x(j))'φ(x (i))= K(x(j)卧秘，x(i))= Kji，因此K必須是對稱的官扣。 讓φ_k(x)表示向量φ(x)的第k個坐標斯议，我們發(fā)現(xiàn)對于任何向量z，我們都有：

上面倒數(shù)第二步使用了與問題集1 -- Q1中相同的技巧醇锚。 由于z是任意的哼御，這表明K是半正定(K≥0)的。

因此焊唬，我們已經(jīng)證明恋昼，如果K是有效內(nèi)核(即，如果它對應(yīng)于某些特征映射φ)赶促，則相應(yīng)的核矩陣K∈Rm×m是對稱的半正定液肌。 更一般地說，這不僅是K成為有效內(nèi)核(也稱為Mercer內(nèi)核)的必要條件鸥滨，也是充分條件嗦哆。 以下結(jié)果歸功于Mercer。

給定函數(shù)K婿滓，除了試圖找到與其對應(yīng)的特征映射φ之外老速，該定理因此提供了另一種測試它是否是有效內(nèi)核的方法。

在課堂上凸主，我們還簡要介紹了其他幾個內(nèi)核示例橘券。 例如，考慮數(shù)字識別問題，其中給定手寫數(shù)字(0-9)的圖像(16×16像素)旁舰，我們必須弄清楚它是哪個數(shù)字锋华。使用簡單的多項式核K(x，z)=(x'z)^d或高斯核箭窜，SVM能夠在這個問題上獲得極好的性能毯焕。這是特別令人驚訝的，因為輸入屬性x僅是圖像像素強度值的256維向量磺樱，并且系統(tǒng)沒有關(guān)于視覺的先驗知識纳猫，或者甚至關(guān)于哪些像素與哪些像素相鄰。

內(nèi)核用于支持向量機的應(yīng)用應(yīng)該已經(jīng)很清楚了坊罢，因此我們不會在這里花太多時間续担。 但請記住，內(nèi)核的概念比SVM具有更廣泛的適用性活孩。 具體來說物遇，如果你有任何學(xué)習(xí)算法用輸入屬性向量之間的內(nèi)積<x，z>來編寫憾儒，那么用K(x询兴，z)替換它，其中K是一個內(nèi)核起趾，你可以“神奇地”允許你算法在對應(yīng)于K的高維特征空間中有效地工作诗舰。例如，該核技巧可以與感知器一起應(yīng)用以導(dǎo)出核感知器算法训裆。我們將在本課程后面看到的許多算法也適用于這種方法眶根，后者被稱為“核技巧”。

正規(guī)化和線性不可分的情況

到目前為止所講的SVM的推導(dǎo)都是假設(shè)數(shù)據(jù)是線性可分的边琉。 雖然通過φ將數(shù)據(jù)映射到高維特征空間通常會增加數(shù)據(jù)可分離的可能性属百，但我們無法保證它始終如此。此外变姨，在某些情況下族扰，不清楚找到的分離超平面是否的確正是我們想要做的，因為這可能容易受到異常值的影響定欧。例如渔呵，下圖左邊顯示了一個最佳邊距分類器，當在左上角區(qū)域添加一個異常值時(右圖)砍鸠，它會使決策邊界產(chǎn)生戲劇性的擺動扩氢，并且得到的分類器要小得多邊緣空白。

為了使算法適用于非線性可分離數(shù)據(jù)集以及對異常值不太敏感睦番，我們重新配置我們的優(yōu)化(使用?1正則化)类茂，如下所示：

因此耍属，現(xiàn)在允許樣本具有小于1的函數(shù)間隔托嚣，并且如果樣本具有函數(shù)間隔1-ξi(ξ> 0)巩检，則我們將目標函數(shù)的成本增加Cξi。參數(shù)C控制了使||w||^2變小(我們之前看到的使邊距變大)和確保大多數(shù)示例具有至少1的功能邊界的雙重目標之間的相對權(quán)重示启。

和以前一樣兢哭，我們可以形成拉格朗日：

這里，αi和ri是我們的拉格朗日乘數(shù)(約束為≥0)夫嗓。 我們不會再詳細討論對偶的推導(dǎo)迟螺，但是在將w和b的導(dǎo)數(shù)設(shè)置為零之后，將它們替換回來并簡化舍咖，我們得到以下問題的對偶形式：

和以前一樣矩父，我們也可以用公式(9)中給出的αi表示w，這樣在求解對偶問題后排霉，我們可以繼續(xù)使用公式(13)來進行預(yù)測窍株。 注意，有點令人驚訝的是攻柠，在加上l1正則化時球订，對偶問題的唯一變化是原來的約束0≤αi現(xiàn)在變?yōu)?≤αi≤C。b*的計算也必須修改(方程式11不再有效)瑰钮；請參閱下一節(jié)冒滩。

此外，KKT對偶互補條件(在下一節(jié)中將有助于測試SMO算法的收斂)是：

現(xiàn)在浪谴，剩下的就是給出一個實際解決對偶問題的算法开睡，我們將在下一節(jié)中介紹。

SMO算法

SMO(順序最小優(yōu)化)算法提供了一種有效的方法來解決由SVM的推導(dǎo)引起的對偶問題苟耻。 部分是為了激發(fā)SMO算法篇恒，部分是因為它本身很有趣，讓我們首先來討論坐標上升算法梁呈。

坐標上升算法

考慮嘗試解決無約束的優(yōu)化問題：

在這里婚度，我們將W視為參數(shù)一些αi的函數(shù)，現(xiàn)在忽略此問題與SVM之間的任何關(guān)系官卡。 我們已經(jīng)看到了兩種優(yōu)化算法蝗茁，漸變上升和牛頓方法。 我們將在這里考慮的新算法稱為坐標上升：

因此寻咒，在該算法的最內(nèi)層循環(huán)中哮翘，除了αi其余的參數(shù)都看成定值，并且僅針對參數(shù)αi重新優(yōu)化W毛秘。在這里給出的這個方法的版本中饭寺，內(nèi)循環(huán)以α1机久、α2、...αm掂恕、α1庇绽、α2、...的順序重新優(yōu)化變量(一個更復(fù)雜的版本可能會選擇其他排序员凝；例如署驻，我們可以根據(jù)在W(α)中獲得最大增長的來選擇下一個變量更新。)

當函數(shù)W碰巧具有這樣的形式健霹，即內(nèi)循環(huán)中的“arg max”可以有效地執(zhí)行時旺上，坐標上升可以是相當有效的算法。 這是一張坐標上升的圖片：

圖中的橢圓是我們想要優(yōu)化的二次函數(shù)的輪廓糖埋。 坐標上升初始化為(2宣吱，-2)，并且圖中還繪制了它到達全局最大值的路徑瞳别。 請注意征候，在每個步驟中，坐標上升采用與其中一個軸平行的步長洒试，因為一次只優(yōu)化一個變量倍奢。

SMO

我們通過SMO算法的推導(dǎo)來結(jié)束對SVM的討論。 一些細節(jié)將留給作業(yè)垒棋，而對于其他人卒煞，可以參考課堂上發(fā)表的論文摘錄。

這是我們想要解決的(對偶)優(yōu)化問題：

假設(shè)我們有一組滿足約束條件的αi(18-19)叼架。 現(xiàn)在畔裕，假設(shè)我們想要(α2,...,αm)固定，并采取坐標上升步驟乖订，并相對于α1重新優(yōu)化目標扮饶。 我們可以取得任何進展嗎? 答案是否定的，因為約束(19)確保了這一點:

或者乍构，通過將兩邊乘以y(1)甜无，我們等效地具有:

(這一步使用了y(1)∈{-1,1}，因此(y(1))^2 = 1的事實哥遮。)因此岂丘，α1完全由其他αi確定，如果我們要保持α2,...,αm固定眠饮，那么我們就不能在不違反優(yōu)化問題中的約束(19)的情況下對α1進行任何改變奥帘。

因此，如果我們想要更新αi仪召，我們必須同時更新它們中的至少兩個以便保持滿足約束寨蹋。 這激發(fā)了SMO算法松蒜，它簡單地執(zhí)行以下操作：

為了測試該算法的收斂性，我們可以檢查KKT條件(方程14-16)是否滿足于某個tol已旧。 這里秸苗，tol是收斂容差參數(shù)，并且通常設(shè)置為約0.01至0.001评姨。

SMO是一種有效算法的關(guān)鍵原因是可以非常有效地計算對αi难述、αj的更新萤晴。 現(xiàn)在讓我們簡要概述一下推導(dǎo)有效更新的主要思路吐句。

假設(shè)我們目前有一些αi的設(shè)置滿足約束條件(18-19)，并假設(shè)我們決定保持α3,...,αm固定店读，并且想要相對于α1和α2重新優(yōu)化W(α1,α2,...,αm)(受約束條件限制)嗦枢。 從(19)開始，我們要求:

由于右側(cè)是固定的(因為我們已經(jīng)固定了α3,...,αm)屯断，我們可以讓它用常數(shù)ζ表示：

因此文虏，我們可以如下描述對α1和α2的約束：

根據(jù)約束(18)，我們知道α1和α2必須位于所示的框[0殖演，C]×[0氧秘，C]內(nèi)。 還繪制了線α1y(1)+α2y(2)=ζ趴久，我們知道α1和α2必須位于其上丸相。還要注意，從這些約束中彼棍，我們知道L≤α2≤H灭忠；否則，(α1座硕，α2)不能同時滿足框和直線約束弛作。在這個例子中，L = 0华匾。但是根據(jù)線α1y(1)+α2y(2)=ζ的樣子映琳，這并不一定是這種情況；但更一般地說蜘拉，在α2的允許值上會有一些下限L和一些上限H萨西，這將確保α1，α2位于框[0诸尽，C]×[0原杂，C]內(nèi)。

使用等式(20)您机，我們也可以將α1寫為α2的函數(shù)：

(自己檢查這個推導(dǎo)穿肄；我們再次使用y(1)∈{-1,1}這樣的事實年局，使得(y(1))^2 = 1。)因此咸产，可以寫出目標W(α):

將α3,...,αm看作常數(shù)矢否，你應(yīng)該能夠驗證這只是α2中的一些二次函數(shù)。對于某些適當?shù)腶脑溢、b和c僵朗，這也可以以aα2^2+bα2+ c的形式表示。如果我們忽略“框”約束(18)(或等效地屑彻，L≤α2≤H)验庙，那么我們可以通過將其導(dǎo)數(shù)設(shè)置為零并求解來輕松地最大化該二次函數(shù)。我們將

并將其在[L搏恤，H]中“剪切”來找到所得到的最優(yōu)值违寿。

最后，找到了α_new2熟空，我們可以使用等式(20)返回并找到α_new1的最佳值藤巢。

還有一些非常簡單的細節(jié)，但我們將讓你在Platt的論文中了解：一個是用于選擇下一個αi息罗，αj進行更新的啟發(fā)式選擇掂咒；另一種是在運行SMO算法時如何更新b。