作者說(shuō)：我以前一直沒(méi)有真正理解支持向量機(jī)，直到我畫了一張圖。

1. 問(wèn)題

支持向量機(jī)（SVM）旨在解決「分類」問(wèn)題。數(shù)據(jù)通常包含一定數(shù)量的條目/行/點(diǎn)。現(xiàn)在，我們想對(duì)每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行分類。為簡(jiǎn)單起見(jiàn)，我們假設(shè)兩個(gè)類別：「正類」和「負(fù)類」。這或許可以幫助解答以下問(wèn)題：

基于圖像的像素?cái)?shù)據(jù)，判斷這張圖像中是否有貓（有貓則標(biāo)簽為正類）；

基于郵件的主題、發(fā)送者、文本等，判斷該郵件是否為垃圾郵件；

判斷某個(gè)病人是否患有某種疾病。

其精髓在于，當(dāng)我們知道正確答案時(shí)，我們會(huì)想到一些將數(shù)據(jù)分為兩類的規(guī)則（對(duì)于支持向量機(jī)而言，「規(guī)則」是畫一個(gè)平面，一側(cè)的所有點(diǎn)均為「正」，另一側(cè)的所有點(diǎn)均為「負(fù)」）。當(dāng)我們遇到不知道類別的新數(shù)據(jù)點(diǎn)時(shí)，我們使用規(guī)則對(duì)其進(jìn)行分類。分類問(wèn)題嚴(yán)重依賴約束優(yōu)化，同時(shí)也是約束優(yōu)化的一個(gè)直觀示例。大家可以參考以下博客或吳恩達(dá)的文章。

博客地址：https://towardsdatascience.com/lagrange-multipliers-with-pictures-and-code-ace8018dac5e

吳恩達(dá)文章地址：http://cs229.stanford.edu/notes/cs229-notes3.pdf

1.1 圖解

我以前一直沒(méi)有真正理解支持向量機(jī)，直到我畫了一張圖。

我們可以看到特征空間中有一些點(diǎn)。為方便可視化，我們使用一個(gè)可在屏幕上觀看的 2D 特征空間。該空間中散落著一些數(shù)據(jù)點(diǎn)，每個(gè)點(diǎn)具備二元標(biāo)簽（(1/-1）。如下圖所示，我們將綠色點(diǎn)看作正類，紅色點(diǎn)看作負(fù)類，黃色點(diǎn)類別未知。如果讓你猜測(cè)黃色點(diǎn)的標(biāo)簽，你會(huì)怎么選？你可能會(huì)發(fā)現(xiàn)其中一些點(diǎn)并不是那么容易確認(rèn)類別。

圖 1：2-D 分類問(wèn)題。綠色點(diǎn)是正類，紅色點(diǎn)是負(fù)類。你可以猜出黃色點(diǎn)的標(biāo)簽嗎？（繪圖工具：https://github.com/ryu577/pyray）

現(xiàn)在，如果我畫一條紫色線將兩個(gè)類別分割開，那么黃色點(diǎn)屬于哪個(gè)類別就清晰多了（紫色線上方是綠色點(diǎn)，下方是紅色點(diǎn)）。

圖 2：畫一條線，作為將正類標(biāo)簽和負(fù)類標(biāo)簽分割開來(lái)的「規(guī)則」。現(xiàn)在，我們可以使用該規(guī)則標(biāo)注每個(gè)黃色點(diǎn)的類別。

然而，這條線并非唯一。有很多條紫色線可以將綠色點(diǎn)和紅色點(diǎn)完美分割（見(jiàn)下圖）。隨著下圖中紫色線的移動(dòng)，某些黃色點(diǎn)就顯得很微妙了（它們處于紫色線的不同側(cè)，因此它們的類別取決于你選擇使用哪條紫色線）。

圖 3：將紅色點(diǎn)和綠色點(diǎn)完美分割的線有很多條。那么我們應(yīng)該選擇哪一條呢？

問(wèn)題在于，所有候選線中，哪一條是「最優(yōu)」的？有一點(diǎn)很清楚：當(dāng)上圖中的紫色線接近右下角的紅色點(diǎn)（critical point）時(shí)，其泛化效果不好，而當(dāng)它遠(yuǎn)離那個(gè)點(diǎn)時(shí)，其分割效果要好得多。因此，這個(gè)紅色點(diǎn)可以說(shuō)明紫色線的分類效果，因此它是「關(guān)鍵點(diǎn)」。我們可以說(shuō)，遠(yuǎn)離該紅色點(diǎn)的線同樣遠(yuǎn)離所有訓(xùn)練樣本，而靠近該紅色點(diǎn)的線最終的分類效果并不好。因此，離最近的訓(xùn)練樣本較遠(yuǎn)的線才是優(yōu)秀的分類器。

接下來(lái)，我們來(lái)看如何利用數(shù)學(xué)知識(shí)繪制分割線。

2. 繪制分割線

現(xiàn)在我們要（在 2D 空間中）畫一條分割線（在更高維度的空間中，則為分割面）。那么這條線是什么呢？它是具備某種共性的點(diǎn)的無(wú)限集合。這些點(diǎn)滿足一個(gè)特定公式。為了找到這個(gè)公式，我們先從最簡(jiǎn)單的線 x 軸開始。x 軸上所有點(diǎn)的位置向量存在什么共性？v_x = [x,0]，即它們對(duì)應(yīng)的 y 坐標(biāo)均為 0。

也就是說(shuō)，x 軸上每個(gè)點(diǎn)的位置向量與指向 y 軸方向的向量是正交（垂直）的。

這個(gè)說(shuō)法可能看起來(lái)比較晦澀難懂，但是我們必須這么說(shuō)，因?yàn)檫@種現(xiàn)象其實(shí)對(duì)所有線都成立，而并非只適用于 x 軸。我們希望將此說(shuō)法泛化至任意線。現(xiàn)在每次挪動(dòng)一小步，我們來(lái)看看穿過(guò)原點(diǎn)的線（如 x 軸）。如下圖所示，只需將 x 軸旋轉(zhuǎn)一定角度，就可以得到這些線。

圖 4：旋轉(zhuǎn) x 軸可以得到穿過(guò)原點(diǎn)的任意線。這些線上的每個(gè)點(diǎn)都與橙色向量相垂直。

隨著線的變化，與線相垂直的向量也在變化，但是所有線上每個(gè)點(diǎn)的位置向量都與某個(gè)向量垂直。我們把這個(gè)與線垂直的向量叫做 w。當(dāng)我們改變 w 時(shí)，就可以捕捉到所有此類線。

注意，對(duì)于任意給定線而言，存在多個(gè) w 值。如果我們將向量 w 擴(kuò)展或縮小一定數(shù)值，該線上每個(gè)點(diǎn)的位置向量仍與向量 w 垂直。

圖 5：擴(kuò)大或縮小正交 w 向量。

為什么不把 w 向量限制在大小為 1 呢？下文中，我們將 w 向量的大小設(shè)為 1。

現(xiàn)在我們已經(jīng)將穿過(guò)原點(diǎn)的所有線都參數(shù)化了。那么那些沒(méi)有穿過(guò)原點(diǎn)的線呢？我們將穿過(guò)原點(diǎn)的線移動(dòng)一定量，即在該線法向量 w 的方向上移動(dòng) b。現(xiàn)在，w 與該線上每個(gè)點(diǎn)的位置向量的點(diǎn)積不為零，而是常量 b（參見(jiàn)下圖）。w 向量是從原點(diǎn)指向紫色線的單位向量，且與紫色線垂直。A 即紫色線上與原點(diǎn)最接近的點(diǎn)。假設(shè) OA 的距離是 -b。現(xiàn)在，考慮兩個(gè)隨機(jī)點(diǎn) B 和 C（分別是圖中綠色點(diǎn)和橙色點(diǎn)）。將 OB 或 OC 與單位向量 w 相乘，分別得到三角形 OAB 和 OAC 的底。 在這兩種情況中，OA 為 -b。由于這兩個(gè)點(diǎn)只是紫色線上的任意點(diǎn)，我們可以推斷出，紫色線上的所有點(diǎn)均滿足 w^T x+b=0（其中 x 表示紫色線上點(diǎn)的位置向量）。

圖 6：未穿過(guò)原點(diǎn)的線。

如果我們將不在該線上的點(diǎn)應(yīng)用于上述公式呢？得到的結(jié)果不是零，而是從該點(diǎn)到紫色線的垂直距離（對(duì)于紫色線上的點(diǎn)而言也是如此，所以它們所對(duì)應(yīng)的公式結(jié)果為零）。我們需要注意：這個(gè)結(jié)論僅適用于 |w|=1 的情況。下圖清晰說(shuō)明了這一結(jié)果。B 為不屬于紫色線的任意點(diǎn)，B』』 為從 B 到紫色線的垂點(diǎn)，B』 為從 B 到 w 向量的垂點(diǎn)。從 B 到紫色線的垂直距離為 BB』』。但是由于 A-B』-B-B』』 是一個(gè)矩形，因此該垂直距離等于 AB』=OB』-OA。現(xiàn)在，OB』 是 B 的位置向量與 w 的點(diǎn)積。因此，如果 x 是 B 的位置向量，則 |OB』| = w^T x。這意味著 |AB』|=w^T x-(-b)（OA=-b）。因此從點(diǎn) B 到紫色線的距離是：|AB』|=w^T x+b（該公式恰好是紫色線的公式）。

圖 7：將不在紫色線上的點(diǎn)應(yīng)用于紫色線公式會(huì)發(fā)生什么？我們得到該點(diǎn)與紫色線之間的垂直距離。

注意，在 w 指向方向一側(cè)的所有點(diǎn)（如圖 7 中的點(diǎn) B）到紫色線的垂直距離為正值，而另一側(cè)點(diǎn)的垂直距離為負(fù)值。

在 w 指向方向一側(cè)的所有點(diǎn)均得到正類標(biāo)簽 (t_i=1)，而另一側(cè)的所有點(diǎn)均得到負(fù)類標(biāo)簽 (t_i=-1)。因此，如果我們將這些標(biāo)簽與垂直距離相乘，則所有點(diǎn)調(diào)整后的垂直距離均為正，前提是這些點(diǎn)均被紫色線正確分類（即具備正類標(biāo)簽的點(diǎn)在線一側(cè)，具備負(fù)類標(biāo)簽的點(diǎn)在另一側(cè)）。

3. 最佳分割線

現(xiàn)在到了 SVM 的重點(diǎn)了。我們將任意點(diǎn)到分割線的調(diào)整后垂直距離叫做「間距」（margin）。那么，對(duì)于任意給定分割線，所有點(diǎn)均具備間距（如果點(diǎn)被分割線正確分類，則間距為正，反之則間距為負(fù)）。我們想獲取將正類和負(fù)類完美分割的線。也就是說(shuō)，間距越大越好，即使是對(duì)于鄰近界限（分割平面）的點(diǎn)。

那么，最大化所有間距（甚至是最接近分割線的點(diǎn)的間距）的分割平面應(yīng)該能夠很好地分割這些點(diǎn)。現(xiàn)在，給出 (w,b)，第 i 個(gè)點(diǎn)的間距為：

間距公式。

其中 x_i 表示特征空間中的位置向量，t_i 表示標(biāo)簽：1 為正類，-1 為負(fù)類。

所有點(diǎn)中的最小間距為：

公式 1：所有點(diǎn)中的最小間距。

我們想讓 (w,b) 最大化上述最小間距。也就是：

即我們想讓 (w,b) 滿足 |w|=1，且最大化間距：

公式 2：SVM 目標(biāo)函數(shù)。

注意：如果這條線沒(méi)有分離數(shù)據(jù)，那么對(duì)于 (w,b)，某些點(diǎn)的間距

間距公式。

為負(fù)。且這些點(diǎn)中的其中一個(gè)會(huì)在第一次最小化中「脫穎而出」，這意味著 (w,b) 無(wú)法在第二次 arg max 時(shí)勝出。因此，該公式保證了勝出的 (w,b) 能夠分割數(shù)據(jù)。

公式 2 是一個(gè)優(yōu)化問(wèn)題，涉及最小化和最大化（mini-max）。解決一級(jí)優(yōu)化總比二級(jí)優(yōu)化要簡(jiǎn)單。因此，我們嘗試將公式 2 轉(zhuǎn)化為約束優(yōu)化問(wèn)題。

我們用 γ 表示所有點(diǎn)的最小間距。

公式 3：約束。

最終得到的優(yōu)化問(wèn)題為：

公式 4：SVM 優(yōu)化問(wèn)題。

上述優(yōu)化問(wèn)題具備二次/線性約束和線性目標(biāo)函數(shù)。我們可以使用二次規(guī)劃求解器（quadratic programming solver）和最優(yōu)分割線/平面 (w,b) 解決該問(wèn)題。

現(xiàn)在，我們來(lái)試著進(jìn)一步簡(jiǎn)化該問(wèn)題。我們發(fā)現(xiàn)可以去除 γ。其代價(jià)是，我們必須放棄 w^T w = 1 這一要求。但這是值得的。我們使用 γ 將約束分割為兩部分，得到：

公式 5：使用 γ 分割分割平面公式。

現(xiàn)在，使

引入新的 w 變量。

為兩側(cè)取絕對(duì)值：

取絕對(duì)值。

我們之前要求 |w|=1。這意味著：

因此，公式 3 變成了：

公式 5 和公式 6 使公式 4 中的優(yōu)化問(wèn)題變成了：

現(xiàn)在，優(yōu)化問(wèn)題有了一個(gè)丑陋的目標(biāo)函數(shù)。但是最大化 1/|w| 等同于最小化 |w|，等同于最小化 |w|2。添加 1/2 使得計(jì)算更加簡(jiǎn)單。

因此，上述優(yōu)化問(wèn)題變?yōu)椋?/p>

公式 7

現(xiàn)在，該優(yōu)化問(wèn)題具備二次目標(biāo)函數(shù)和線性約束（線性約束二次規(guī)劃，LCQP）。使用二次規(guī)劃求解器即可解決該問(wèn)題。

現(xiàn)在，我們知道如何通過(guò)解決優(yōu)化問(wèn)題找出最優(yōu)分割線了。透過(guò)表面查看解決這類優(yōu)化問(wèn)題的真正機(jī)制，會(huì)幫助我們對(duì)該問(wèn)題了解更多，具備更強(qiáng)大的洞察和見(jiàn)解。

責(zé)任編輯：xj

原文標(biāo)題：透過(guò)現(xiàn)象看本質(zhì)，圖解支持向量機(jī) SVM

文章出處：【微信公眾號(hào)：新機(jī)器視覺(jué)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。