二、核函數(shù)

上一節(jié)我們說到唾糯，在引入對(duì)偶問題與KKT條件以后怠硼，此時(shí)的w為

于是此時(shí)的模型從wx+b轉(zhuǎn)換成了另一個(gè)形式：

以下的核函數(shù)，都是基于上面的式子來說的：

對(duì)于比較簡(jiǎn)單的樣例趾断，比如X = [x₁,x₂]只有兩個(gè)特征，就可以用上一節(jié)的圖中“圈與×”的點(diǎn)很方便的進(jìn)行表示吩愧，也可以很方便的線性可分芋酌。
并且對(duì)于需要預(yù)測(cè)的 x的類別，我們就會(huì)計(jì)算每個(gè)支持向量機(jī)的樣例x⁽ⁱ⁾與x之間的內(nèi)積雁佳。
最終再與正負(fù)1進(jìn)行比較脐帝。

以上都是線性可分時(shí)的情況。

那么線性不可分時(shí)怎么辦呢糖权？怎么把SVM應(yīng)用到線性不可分的情況中呢堵腹？

比如下面舉的例子中，X = [x₁²星澳，x₂²疚顷，x₂]在二維坐標(biāo)系中是線性不可分的，那應(yīng)該怎么辦呢禁偎？就根據(jù)特征構(gòu)造一個(gè)映射函數(shù)Φ(X)腿堤，把特征映射到新的高維的坐標(biāo)系中去，這樣如暖，這個(gè)特征點(diǎn)在新的高維的坐標(biāo)系中就線性可分了笆檀，就可以用SVM進(jìn)行分類了。
于是盒至，此時(shí)模型中酗洒，需要計(jì)算的內(nèi)積士修，就不再是x⁽ⁱ⁾與x了，而是二者的映射函數(shù)之間的內(nèi)積了（因?yàn)橹挥羞@樣樱衷，才能線性可分）：

但是這樣棋嘲，需要每次都實(shí)現(xiàn)計(jì)算一次映射函數(shù)，然后計(jì)算樣例與需要預(yù)測(cè)的樣例的映射函數(shù)之間的內(nèi)積箫老，十分麻煩并且會(huì)維度爆炸封字。
我們又發(fā)現(xiàn)，右邊兩個(gè)映射函數(shù)的結(jié)果耍鬓，可以用一個(gè)x⁽ⁱ⁾與x的式子表示阔籽。而這個(gè)式子，只需要在低維度計(jì)算x⁽ⁱ⁾與x的式子牲蜀，就可以達(dá)到同樣的計(jì)算效果笆制，即二者的wx+b的結(jié)果是一樣一樣的，那么肯定是后者好呀涣达，后者就是核函數(shù)在辆。

先總的概括三步，再分別細(xì)細(xì)的解釋這三步

2.1 核函數(shù)總結(jié)：

• 1. 實(shí)際中度苔，我們會(huì)經(jīng)常遇到線性不可分的樣例匆篓，此時(shí)，我們的常用做法是把樣例特征映射到高維空間中去寇窑，映射到高維空間后鸦概，相關(guān)特征便被分開了，也就達(dá)到了分類的目的甩骏；
• 2. 但進(jìn)一步窗市，如果凡是遇到線性不可分的樣例，一律映射到高維空間饮笛，那么這個(gè)維度大小是會(huì)高到可怕的(甚至?xí)綗o窮維咨察，維度爆炸)。
• 3. 此時(shí)福青，核函數(shù)就隆重登場(chǎng)了摄狱，核函數(shù)絕就絕在它在低維上進(jìn)行計(jì)算，但是和 采用第二步（映射到高維以后進(jìn)行運(yùn)算）計(jì)算得到的結(jié)果是相同的无午，效果也是一樣的二蓝。（這句話是精髓，后面會(huì)解釋指厌。）
     但是刊愚，相比于第二步（映射到高維以后進(jìn)行運(yùn)算），核函數(shù)的優(yōu)點(diǎn)就體現(xiàn)出來了：避免了直接在高維空間中的復(fù)雜運(yùn)算踩验，不需要顯示的寫出映射函數(shù)Φ（高維）鸥诽，大大降低了時(shí)間復(fù)雜度商玫。

2.2 分步講解以上三點(diǎn)

2.2.1 遇到線性不可分的情況

線性不可分?jǐn)?shù)據(jù)

如上圖，此時(shí)是線性不可分的牡借。
如果用X₁和X₂來表示這個(gè)二維平面的兩個(gè)坐標(biāo)的話拳昌，這條二次曲線的實(shí)際方程是如下（加了少量噪聲 生成得到的）：

從上式可以看出，此時(shí)關(guān)于X的多項(xiàng)式是有三個(gè)的：X₁²钠龙，X₂²炬藤，X₂。
原來的特征點(diǎn)碴里，使用二維平面上的坐標(biāo)表示的沈矿，即X = （X₁，X₂）∫б福現(xiàn)在羹膳，我們?cè)囍?strong>將樣例特征映射到高維空間中去”，因?yàn)樯鲜接腥齻€(gè)多項(xiàng)式根竿，所以三個(gè)特征就足夠線性可分了（下面會(huì)解釋）涛菠。
經(jīng)過映射函數(shù)Φ(X)综芥，我們得到了新的特征 X' = （X₁²，X₂²募疮，X₂）涣易，此時(shí)用這三個(gè)特征來簡(jiǎn)歷坐標(biāo)系蚯嫌，那么上面的二維平面圖會(huì)變成這個(gè)樣子：

再旋轉(zhuǎn)：

此時(shí)贬蛙，數(shù)據(jù)是可以通過一個(gè)平面切分開來的室琢，此時(shí)就可以用SVM分類了。

由上冕广，可以得出結(jié)論疏日，也即上面的總結(jié)1：當(dāng)我們遇到線性不可分的樣例時(shí)偿洁，我們的常用做法是把樣例特征映射到高維空間中去撒汉，映射到高維空間后，相關(guān)特征便被分開了涕滋，也就達(dá)到了分類的目的睬辐。

2.2.2、維度爆炸的情況

首先宾肺，上面的線性不可分?jǐn)?shù)據(jù)的圖形是二次曲線中的特例溯饵，一般情況下，二次曲線的方程如下：

也就是說锨用，此時(shí)關(guān)于特征X₁和X₂的多項(xiàng)式丰刊，變?yōu)榱?個(gè)（原始空間的所有特征一階和二階的組合）。那么為了讓這個(gè)曲線中的樣例線性可分增拥，根據(jù) 上一節(jié)的的想法啄巧，就需要將特征映射到一個(gè)5維空間中去寻歧。

這么看似乎沒什么問題，但是秩仆！如果現(xiàn)在原始空間是3維呢码泛？

• 如果映射原始空間的特征的二項(xiàng)式的組合（比如X₁X₁，X₁X₂共有3*3個(gè)） 那么就會(huì)得到一個(gè)9維空間澄耍；
• 如果映射到原始空間特征所有的一階和二階的組合噪珊，就會(huì)得到一個(gè)19維的空間。

假設(shè)現(xiàn)在原始空間有100個(gè)特征呢齐莲？
------------------------------------------------------------------------------------------------
可以看到痢站，這個(gè)數(shù)目，是呈爆炸性增長(zhǎng)的铅搓，這樣下去

• 首先計(jì)算映射函數(shù)Φ(X)就十分困難了：考慮所有的特征組合
• 還會(huì)增加運(yùn)算的復(fù)雜度：兩個(gè)高維（比如10000或無窮）的向量相乘瑟押，耗費(fèi)時(shí)間

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

2.2.3、核函數(shù)的隆重登場(chǎng)

分兩部分進(jìn)行星掰，先解釋第一部分的這句話：在低維上進(jìn)行計(jì)算多望，但是和 采用第二步（映射到高維以后進(jìn)行運(yùn)算）計(jì)算得到的結(jié)果是相同的，效果也是一樣的氢烘。

再解釋第二部分的這句話：避免了直接在高維空間中的復(fù)雜運(yùn)算怀偷，大大降低了時(shí)間復(fù)雜度。

一播玖、與‘’映射到高維以后進(jìn)行計(jì)算‘’的效果相同的核函數(shù)

1.1 直觀了解一下核函數(shù)

核函數(shù)的定義：計(jì)算兩個(gè)向量在隱式映射過后的空間中的內(nèi)積的函數(shù)叫做核函數(shù)(Kernel Function)椎工。

看不懂沒關(guān)系，舉幾個(gè)核函數(shù)的例子先直觀了解一下：

甚至把上式 中的數(shù)字1 去掉也是一個(gè)核函數(shù)蜀踏。

1.2 不采用核函數(shù)的情況下维蒙，SVM的表達(dá)

如2.2.1小節(jié)，我們希望將得到的特征映射后的特征應(yīng)用于SVM分類果覆，而不是最初的特征颅痊。這樣我們需要將判別模型中w^Tx+b公式中的內(nèi)積從<x⁽ⁱ⁾,x>映射到<Φ(x⁽ⁱ⁾),Φ(x)>。其中x⁽ⁱ⁾是支持向量局待，x是需要判別的樣本斑响。

將核形式化定義，如果原始特征內(nèi)積是<x,z>钳榨，映射后為<Φ(x),Φ(z)>舰罚，那么定義核（Kernel）為

至此，我們可以得出結(jié)論薛耻，如果要實(shí)現(xiàn)2.2.1小節(jié)的效果营罢，只需計(jì)算出Φ(x)，然后計(jì)算Φ(x)^TΦ(z)即可饼齿。

然而饲漾，這種計(jì)算方式是非常低效的瘟滨。
比如最初的特征是n維的，我們將其映射到n²維能颁，然后再計(jì)算杂瘸，這樣為我們需要O(n²)的時(shí)間。
for i in range(n²)：
---- x_i*z_i（n²次）

1.3 采用核函數(shù)的情況下伙菊，有什么效果

上面講到败玉，單純的先把特征映射到高維再計(jì)算內(nèi)積的方式是十分耗時(shí)間的，那么能不能想辦法镜硕，減少計(jì)算時(shí)間呢运翼？

舉個(gè)栗子：

假設(shè)x和z都是n維的

展開后，得

這個(gè)時(shí)候發(fā)現(xiàn)我們可以只計(jì)算原始特征x和z內(nèi)積的平方（時(shí)間復(fù)雜度是O(n) 兴枯。血淌。。for i in range（n）财剖。悠夯。。）躺坟，就等價(jià)與計(jì)算映射后特征的內(nèi)積沦补。

是不是很有意思？

也就是說咪橙，用不同的計(jì)算方法夕膀，取得了相同的結(jié)果。（一個(gè)映射到高維以后做內(nèi)積美侦，一個(gè)（核函數(shù)）直接在原來的低維空間中進(jìn)行運(yùn)算）产舞。而這里的K(x,z)就是一個(gè)核函數(shù)。核函數(shù)的優(yōu)越可見一斑菠剩。

現(xiàn)在看一下映射函數(shù)（n=3時(shí)）易猫，根據(jù)上面的公式，得到

說明赠叼，一個(gè)核函數(shù)只能對(duì)應(yīng)著一個(gè)映射函數(shù)擦囊。上面的這個(gè)核函數(shù)只有選擇上面的這個(gè)映射函數(shù)時(shí)违霞，才能夠等價(jià)嘴办。

再比如，另一個(gè)核函數(shù)

對(duì)應(yīng)的映射函數(shù)（n=3時(shí)）是

更一般的买鸽，核函數(shù)

對(duì)應(yīng)的映射后特征維度為

綜上涧郊，就是前面所說的：

• 1、核函數(shù)在在低維上進(jìn)行計(jì)算眼五，但是和 采用第二步（映射到高維以后進(jìn)行運(yùn)算）計(jì)算得到的結(jié)果是相同的

• 2妆艘、因?yàn)樽罱K計(jì)算的結(jié)果是相同的彤灶， 而判別模型就是求得內(nèi)積的結(jié)果以后和1比較大小，所以最終用SVM判斷的效果也是一樣的批旺。

• 3幌陕、但是，相比于第二步（映射到高維以后進(jìn)行運(yùn)算）汽煮，核函數(shù)的優(yōu)點(diǎn)就體現(xiàn)出來了：避免了直接在高維空間中的復(fù)雜運(yùn)算搏熄，不需要顯示的寫出映射函數(shù)Φ（高維），大大降低了時(shí)間復(fù)雜度暇赤。

1.4 幾個(gè)核函數(shù)

通常人們會(huì)從一些常用的核函數(shù)中選擇（根據(jù)問題和數(shù)據(jù)的不同心例，選擇不同的參數(shù)，實(shí)際上就是得到了不同的核函數(shù)）鞋囊，例如：

• 1止后、多項(xiàng)式核

上面所舉的例子也就是多項(xiàng)式核，而且這個(gè)核所對(duì)應(yīng)的映射實(shí)際上是可以寫出來的溜腐，該空間的維度是C^d_m+d译株，其中m 是原始空間的維度。

• 2挺益、高斯核

因?yàn)檫@個(gè)函數(shù)類似于高斯分布古戴，所以稱為高斯核函數(shù)，也叫做徑向基函數(shù)(Radial Basis Function 簡(jiǎn)稱RBF)矩肩。它能夠把原始特征映射到無窮維现恼。

不過，如果?σ選得很大的話黍檩，高次特征上的權(quán)重實(shí)際上衰減得非巢媾郏快，所以實(shí)際上（數(shù)值上近似一下）相當(dāng)于一個(gè)低維的子空間刽酱；反過來喳逛，如果?σ選得很小，則可以將任意的數(shù)據(jù)映射為線性可分——當(dāng)然棵里，這并不一定是好事润文，因?yàn)殡S之而來的可能是非常嚴(yán)重的過擬合問題。不過殿怜，總的來說典蝌，通過調(diào)控參數(shù)?σ，高斯核實(shí)際上具有相當(dāng)高的靈活性头谜，也是使用最廣泛的核函數(shù)之一骏掀。

如下所示的例子便是把低維線性不可分的數(shù)據(jù)通過高斯核函數(shù)映射到了高維空間：

• 3、線性核

這實(shí)際上就是原始空間中的內(nèi)積。這個(gè)核存在的主要目的是使得“映射后空間中的問題”和“映射前空間中的問題”兩者在形式上統(tǒng)一起來了(意思是說截驮，咱們有的時(shí)候笑陈，寫代碼，或?qū)懝降臅r(shí)候葵袭，只要寫個(gè)模板或通用表達(dá)式涵妥，然后再代入不同的核，便可以了坡锡，于此妹笆，便在形式上統(tǒng)一了起來，不用再分別寫一個(gè)線性的娜氏，和一個(gè)非線性的)拳缠。

即 ，不用再寫一下線性的SVM贸弥，再寫一個(gè)非線性的SVM了窟坐，只需要寫同樣的代碼，前者用線性核绵疲，后者用別的核就行了哲鸳。

2.3 使用核函數(shù)以后，怎么分類新來的樣本呢盔憨？

只需要將原來的內(nèi)積替換成核函數(shù)就行了徙菠。值的判別也是同1進(jìn)行比較。

2.4 核函數(shù)的有效性判定

詳細(xì)參考Jerrylead的第八小節(jié) 郁岩。

問題：給出了一個(gè) 函數(shù)K婿奔，我們能否認(rèn)為K是一個(gè)有效的核函數(shù)，或者說问慎，能夠找到一個(gè)映射函數(shù)Φ萍摊，使得對(duì)于所有的x和z，都有

證明：
如果假設(shè)K是有效地核函數(shù)如叼，那么根據(jù)核函數(shù)定義：

可見冰木，矩陣K應(yīng)該是個(gè)對(duì)稱陣。讓我們得出一個(gè)更強(qiáng)的結(jié)論笼恰，那么對(duì)于任意向量z踊沸，有

最后一步，是因?yàn)?i 和 j 是同屬性的社证，相當(dāng)于x^Tx逼龟。從這個(gè)公式我們可以看出，如果K是個(gè)有效的核函數(shù)猴仑，那么审轮，在訓(xùn)練集上得到的核函數(shù)矩陣K應(yīng)該是半正定的。

這樣我們得到一個(gè)核函數(shù)的必要條件：

K是有效的核函數(shù) ==> 核函數(shù)矩陣K是對(duì)稱半正定的辽俗。

可幸的是疾渣，這個(gè)條件也是充分的，由Mercer定理來表達(dá)崖飘。

簡(jiǎn)而言之就是：
核函數(shù)矩陣K是對(duì)稱半正定的K是有效的核函數(shù) ==> K是有效的核函數(shù)

寫在最后：核函數(shù)不僅僅用在SVM上榴捡，但凡在一個(gè)模型后算法中出現(xiàn)了了<x,z>，我們都可以常使用K(x,z)去替換朱浴，這可能能夠很好地改善我們的算法吊圾。

三、規(guī)則化和不可分情況的處理

3.1翰蠢、什么情況下才是不可分项乒？

我們之前討論過：

• 樣例線性可分時(shí)可以直接使用SVM進(jìn)行分類
• 當(dāng)樣例線性不可分時(shí)（比如同心圓的情況），使用核函數(shù)來將特征映射到高維梁沧，這樣很可能就可分了檀何。

然而，映射后我們也不能100%保證可分廷支。如下圖：

上圖中频鉴，有‘背叛’點(diǎn)出現(xiàn)，那么映射到三維恋拍，四維以后垛孔，也不一定能保證可分。如果非要給映射到非常高的維度施敢，也許最終可分了周荐，但是可過擬合了。這也不是我們想要的結(jié)果僵娃。

那怎么辦呢羡藐，我們需要將模型進(jìn)行調(diào)整（加入松弛變量ξ），以保證在不可分的情況下悯许，也能夠盡可能地找出分隔超平面仆嗦。

3.2 調(diào)整模型，使之能夠容忍不好歸類的因子-- 軟間隔

3.2.1 之前的模型的缺點(diǎn)

之前討論過的模型中先壕，是想找到一個(gè)絕對(duì)正確的平面能夠分類出所有的正負(fù)例瘩扼，但是，這種太‘硬’的做法可能取得反效果垃僚。如下圖所示：

可以看到一個(gè)離群點(diǎn)（可能是噪聲）可以造成超平面的移動(dòng)集绰，間隔縮小，可見以前的模型對(duì)噪聲非常敏感谆棺。
再有甚者栽燕，如果離群點(diǎn)在另外一個(gè)類中罕袋，如上上圖所示，那么這時(shí)候就是線性不可分了碍岔。

3.3.2 調(diào)整模型浴讯，實(shí)現(xiàn)軟間隔

為了避免上述情況的發(fā)生，我們應(yīng)該允許一些點(diǎn)游離并在在模型中違背限制條件（限制條件：函數(shù)間隔必須大于1）蔼啦。于是我們?cè)O(shè)計(jì)得到新的模型如下（也稱軟間隔）

原約束條件右邊等于1榆纽，說明，必須必須大于1捏肢，不能接受背叛（x點(diǎn)出現(xiàn)在了圈點(diǎn)內(nèi)）的情況奈籽。這種情況，有兩個(gè)缺點(diǎn)鸵赫，一是分隔超平面容易受離群點(diǎn)的影響衣屏，二是甚至不可分。

現(xiàn)在約束條件右邊變成了1-ξ辩棒，且每個(gè)樣例的ξ>=0勾拉，也就是說允許出現(xiàn)離群點(diǎn)了（函數(shù)間隔可以小于1了）。甚至當(dāng) ξ 足夠大時(shí)盗温，可能1-ξ<0藕赞，間隔變?yōu)樨?fù)數(shù)，也就是說可以出現(xiàn)背叛點(diǎn)了卖局。

但是斧蜕，不能慣著那些不安分的點(diǎn)，所以在 目標(biāo)函數(shù)后面加上Cξ（大于0）砚偶，最小化目標(biāo)函數(shù)的情況下批销，就是表明一種態(tài)度，最好不要出現(xiàn)這種情況染坯，但是出現(xiàn)了我也能忍均芽，但是我會(huì)盡力壓制。所以被稱為軟間隔单鹿。

松弛變量ξ是為了糾正或約束少量“不安分”或脫離集體不好歸類的因子掀宋。

3.3.3 修改以后的模型 的對(duì)偶形式：

模型加入松弛變量以后，拉格朗日公式（加入約束條件）也要修改如下：

按照我們?cè)诶窭嗜諏?duì)偶中提到的求法仲锄，定義函數(shù)θ^p使之合理劲妙，再變成對(duì)偶問題θ^d，最里面的參數(shù)就變成了w儒喊、b和ξ镣奋。分別對(duì)w、b和ξ求 偏導(dǎo)怀愧，代入公式中就得到了min L侨颈。然后就是求max了余赢。這里只寫出最后結(jié)果如下：

此時(shí)我們發(fā)現(xiàn)沒有了參數(shù)ξ，與之前的模型不同之處在于0<=α 變成了0<=α<=C哈垢。為什么會(huì)這樣勒妻柒？

前面所說，為得到最小值温赔，對(duì)w蛤奢、b和ξ分別求偏導(dǎo)鬼癣，并另之為0（這也是KKT的第一個(gè)條件）陶贼。得到

又因?yàn)樗沙谧兞肯禂?shù) r 是大于等于零的，所以有α<=C待秃。于是得到約束條件的第一個(gè)式子拜秧。

------------------------------------------------------------------------------------
之前說過，當(dāng)目標(biāo)函數(shù)是凸規(guī)劃問題的時(shí)候==>

x * 滿足KKT條件 是 強(qiáng)對(duì)偶條件（對(duì)偶問題的解等于原問題的解）的充要條件章郁。
即枉氮，若d* = p* <==> x * 滿足KKT條件
------------------------------------------------------------------------------------

也就是說，只有當(dāng) x * 滿足KKT條件時(shí)暖庄，才能有d* = p聊替，化成對(duì)偶問題才有意義。那么此時(shí)培廓，就要讓上述的最優(yōu)解 α 向量滿足KKT條件.

其中第一條偏導(dǎo)數(shù)為零比較好解釋惹悄。
由第三個(gè)條件 αigi=0 可以得到

α_i作為樣例的系數(shù)，取不同的值 時(shí)肩钠，代表著不同的樣例位置泣港。比如之前問題中，α_i=0時(shí)价匠，說明樣例在間隔平面內(nèi)部当纱。α_i>0時(shí)，說明在間隔平面上踩窖，是支持向量坡氯。

這里也一樣：
α_i=0時(shí)：

α_i=C時(shí)：

0<α_i<C時(shí)：

簡(jiǎn)單些就是：

注意：當(dāng)ξ>0時(shí)，說明此時(shí)就出現(xiàn)‘不安分’的點(diǎn)了洋腮，因?yàn)榇藭r(shí)約束條件--函數(shù)間隔小于1廉沮。

上圖中

• 第一種情況，α_i=0徐矩，ξ=0滞时，說明該樣例點(diǎn)在界內(nèi)煤杀，正常的點(diǎn)被正確分類吃粒。
• 第二種情況，0<α_i<C扛伍，ξ=0，說明α_i是支持向量窒百，該樣例點(diǎn)在邊界上黍判。
• 第三種情況，α_i<0篙梢，ξ>0顷帖，此時(shí)約束條件--函數(shù)間隔小于1，說明該樣例點(diǎn)或者在兩條邊界之間渤滞，或者在錯(cuò)誤的陣營(yíng)中贬墩。

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

至此，算是得到了軟間隔的SVM的目標(biāo)函數(shù)妄呕，并且此時(shí)的 α 向量滿足KKT條件陶舞，是對(duì)偶問題的最優(yōu)解，也是原問題的最優(yōu)解

3.4绪励、懸而未決的問題

不論是‘硬’間隔的目標(biāo)函數(shù)肿孵，還是軟間隔的目標(biāo)函數(shù)，我們都得到了預(yù)測(cè)新來樣例的方法：用判別模型wx+b和1比較疏魏。

后來通過引入對(duì)偶問題停做，我們發(fā)現(xiàn)，可以不用計(jì)算w大莫，直接用α就可以進(jìn)行判別蛉腌。

所以呢，怎么求α葵硕？