【高階統計】高性價比的向量機模型，讓你的資料分析更加高效可靠！

歐幾里得範數

1. 支援向量機的目的是什麼?

對於用於分類的支援向量機來說，給定一個包含正例和反例（正樣本點和負樣本點）的樣本集合，支援向量機的目的是尋找一個超平面來對樣本進行分割，把樣本中的正例和反例用超平面分開，但是不是簡單地分看，

其原則是使正例和反例之間的間隔最大。

超平面是什麼呢？簡單地說，超平面就是平面中的直線在高維空間中的推廣。那麼，對於三維空間，超平面就是平面了。對於更高維的空間，我們只能用公式來表達，而缺少直觀的圖形了。總之，在n維空間中的超平面是n-1維的。

超平面的公式為。公式中的w為可以調整的係數向量，b為bias。注意我們的表達習慣，所有的向量都是列向量，所以在第一項的內積中向量w需要進行轉置。

現在考慮樣本集合{x i，d i}，x i是輸入的特徵，d i是樣本對應的分類。現在規定當樣本x i屬於第一類時，d i為1，當x i屬於第二類時，d i為-1。

那麼，線性可分的意思就是一個超平面可以把兩類樣本完全地分割開來。用公式表達就是：

你現在可能會問，那麼如果不是線性可分的情況應該怎麼辦呢？事實是這些會在後面處理到。在這裡我們首先討論線性可分的情況，然後將其拓展到線性不可分的情況。

現在假設對於線性可分的樣本集，我們有了一個分割超平面，現在我們想透過調整w 0和b 0讓它分割的正樣本和負樣本保持最大的間隔，這樣我們就獲得了最優的超平面。實際上在操作過程中，

我們最大化的是離超平面最近的點到超平面的距離

。也就是說，我們要讓超平面儘量遠離最近的點。

從圖中可見超平面到正樣本最近點的距離和超平面到負樣本最近點的距離是相等的

。這是個巧合麼？

假設我們已經找到了一個超平面，它離正樣本最近點的距離大於離負樣本最近點的距離，那麼這個離超平面最近的點就是負樣本中的最近點。而考慮到我們的目標，我們還會調整超平面的位置使它還可以增大一些，即使這樣會犧牲離正樣本最近點的距離。所以調整到最後的結果肯定是超平面離兩側最近點的距離是等距的。

為了更形象地表現正負樣本的間隔，我們可以在分割超平面的兩側再定義兩個超平面H1和H2（如圖中虛線所示），這兩個超平面分別透過正樣本和負樣本中離分割超平面最近的樣本點（圖中加了外圈）。從以上分析可以知道，超平面H1和H2離分割超平面是等距的。

我們定義超平面H1和H2上面的點叫做支援向量。正負樣本的間隔可以定義為超平面H1和H2之間的間隔，它是分割超平面距最近正樣本點距離和最近負樣本點距離之和。

從圖中可以看出，支援向量對於分割超平面的位置是起到關鍵作用的。在最佳化分割超平面位置之後，支援向量也顯露出來，而支援向量之後的樣本點則對分類並不關鍵。為什麼這樣說呢？因為即使把支援向量以外的樣本點全部刪除，再找到最優的分割超平面，這個超平面的位置跟原先的分割超平面的位置也是一樣的。總結起來就是：

正負樣本的間隔可以定義為超平面H1和H2之間的間隔，它是分割超平面距最近正樣本點距離和最近負樣本點距離之和。

支援向量包含著重構分割超平面所需要的全部資訊!

如何求一點到超平面的距離呢？

現在我們來看看係數向量w 0是什麼含義？回憶一下，w 0實際上是超平面的法向量！

那麼，對於任意一個樣本點x，它可以表示為：

其中x p是x在超平面上的投影，r是x到超平面的幾何距離（幾何間隔）。

設，

現在由定義有g（x p）為0，則有。

現在我們開看，g（x）實際上度量了樣本點x到超平面的距離，在||w 0||恆定的情況下，g（x）絕對值的大小反映了幾何間隔r的大小。我們給g（x）起個名字叫做函式間隔。

2. 樣本點到超平面距離的表示

注意幾何間隔r和函式間隔g(x)都是有正負號的，代表著處於超平面的不同側。

我們已經知道了函式間隔和幾何間隔的表示，現在回到正題，

3. 最大化間隔

我們的目的是最大化支援向量到分割超平面的幾何間隔r，而不是最大化函式間隔g（x），為什麼呢？因為超平面方程的係數可以同比例增大或者減小，而不改變超平面本身。所以||w 0||是不固定的，這就會影響函式間隔g（x）的大小。

所以我們需要最大化的是幾何間隔r，這等價於我們固定||w 0||，然後最大化函式間隔g（x）。但是實際上我們不會這麼做，通常的處理方法是固定函式間隔g（x）的絕對值為1，然後最小化||w 0||。

我們需要最大化支援向量到分割超平面的距離，當然在最開始我們不知道哪些向量是支援向量。

也就是說我們把支援向量到分割超平面的函式間隔g(x)的絕對值設定為1，然後最小化||w 0||。

現在我們可以正式地表述這個問題了。我們需要最小化||w 0||，也就是最小化超平面權重向量w 0的歐幾里得範數。但是有沒有限定條件呢？還記得上一節最後一句話麼？

4. 正式的表述

所以最小化||w 0||是有限定條件的，如何表述限制條件呢？我們把支援向量對應的g（x）定為+1或者-1（取決於支援向量處於分割超平面的哪一側，也就是說是正樣本還是負樣本），也就表明了對於所有的正樣本點來說，g（x）是>=+1的，而對於負樣本來說，g（x）是<=-1的。

回想g（x）的定義：

，

我們可以把限制條件寫下來：

現在我們可以把上面的問題寫的更簡練：

“也就是說我們把支援向量到分割超平面的函式間隔g(x)設定為1，然後最小化||w 0||”

目標函式:

1/2是為了以後計算方便所加的，N是樣本點的個數。

現在我們的第一個任務結束了，我們把要尋找最優的分割超平面的問題轉化為帶有一系列不等式約束的最佳化問題。這個最最佳化問題被稱作原問題。我們不會直接解它，而是把它轉化為對偶問題進行解決。至於如何將其轉化為對偶問題，這是以後幾節的內容。

限制:

對支援向量機的求解都是將上節說的原問題轉化為對偶問題進行求解的，這些內容都是最最佳化課程中的內容。

等式約束極小的最優性條件

在上節的原問題中，約束條件是包含不等式的，本節先考慮簡單的問題，即

回憶上節的內容，我們的目標是尋找函式在若干約束條件下的最小值。

（1）

其中f（

考慮只包含等式約束的最最佳化問題:

）被稱作目標函式，而下面是一系列的等式約束。回想一下，當沒有任何約束存在的時候，應該怎樣尋找最優點呢？事實上

x

*是最優點的必要條件是：

而如果函式f（

x

）是凸函式的話，這個條件也是充分條件。

插入一個說明，如果函式f（

x

）是一個實值函式，

x

是一個n維向量，那麼f（

x

）對向量

x

的導數被定義為：

回到目前的問題，當我們尋找約束存在時的最優點的時候，約束的存在雖然減小了需要搜尋的範圍，但是卻使問題變得更加複雜。

x

為了形象化地分析這個問題，我們考慮目標函式是 三變數的函式並且只有一個約束的情況：

（2）

從幾何上來看，上面的問題（2）就是從曲面

上來尋找函式

的最小值。假設問題（2）的最優解是

。我們現在做曲面Ω上任一條透過點

為了使問題變得易於處理，我們的方法是把目標函式和約束全部融入一個新的函式，即拉格朗日函式，再透過這個函式來尋找最優點。

的光滑曲線l：

（由於曲線l是在曲面Ω上的，所以自然有

）。

令最優點

對應的t為t*。因為

x

*是曲面Ω上的最優點，所以

x

*也是曲線l上的最優點，所以t*是一元函式

的最優點，所以在這一點它的導數是0。透過鏈式法則我們得到：

這個式子說明了在

x

*這一點，函式

的梯度向量

和曲線l在

x

*處的切線是垂直的。由於曲線l是任意的，所以梯度向量

和曲面Ω是垂直的。

回憶高等數學的結論，

的方向就是曲面Ω的法線方向，所以

和

必然在同一直線的方向上，所以必定存在一個常數μ*，有

。

我們可以把它寫成更加精煉的形式。如果我們構造二元函式

，上面的結論就可以表達為必定存在著常數μ*，使

。

x

關於只有等式約束的拉格朗日函式的引入，也可以參考

我們把構造的函式稱作拉格朗日函式，而其中的μ稱作拉格朗日乘子。

中的兩個變數函式的例子。

以上是一個特殊情形的分析，並且只包含了一個約束。那麼包含等式約束的一般情況，也就是問題（1）來說，我們同樣可以構造拉格朗日函式，不過由於包括多個等式約束，表達稍微不同：

。

也就是說，

維基百科

。那麼

每一個等式約束都對應著一個拉格朗日乘子

*是最優點的必要條件就是，存在相應的拉格朗日乘子

x

*，使得以下兩個式子成立：

（實際上就是原問題（1）的約束條件換了種寫法）

這兩個式子就是最優點的必要條件，當然如果函式是凸函式的話，這兩個式子也是充分條件。

現在我們的目標達到了，也就是把目標函式和一系列的等值約束融合到了一個函式（拉格朗日函式）裡面，這樣只需要解（3）和（4）這兩個式子就可以找到最優點，其優點是不言而喻的。而在下一節中我們將會討論包含不等式約束的最最佳化問題。

μ

我們首先要引入包含不等式約束的最佳化問題，標準形式如下：

（1）

f（x）是目標函式，而後面分別是一系列的不等式約束和等式約束。

我們首先明確幾個概念：

可行點（可行解）：所有滿足約束的點x。

可行域：所有可行點組成的點集，記為R。正式寫出來就是：

最優點（最優解）：滿足約束（也就是處於可行域之內）並且使目標函式達到最小的點，記為x*。

最優值：如果找到了x*，p* = f（x*） 就是最優值。

明確了這些概念以後我們就接著說下面的內容了。

與上節所說的只包含等式約束的情況類似，我們定義拉格朗日函式如下：

我們來看看，這與上節的拉格朗日函式有什麼不同？多了一系列的不等式約束對應的項，所以也多了一系列的拉格朗日乘子。在這裡需要強調的是，所有的λi必須是大於等於0的（也即是不等式約束對應的乘子要求大於等於0，我們記為

尋找最優值的下界

≥0，意思是每個都λi≥0）。至於為什麼要這樣要求，後面自然可以看出來。

接下來我們定義一個重要的函式，我們定義

λ

如下：

（2）

所以拉格朗日對偶函式

就是把

看成x的函式所找到的最小值。找到這個最小值有什麼意義呢？

我們先把結論寫下來，這個結論十分重要，是本節論述的目的：

拉格郎日對偶函式(the Lagrange dual function)

（3）

那麼如何證明（3）呢？

這個證明步驟十分簡潔。假設x*是原問題（1）中的最優解，也就是f（x*） = p*。

最後兩行的推導是考慮到x*是在可行域R內的，所以肯定有，當然前提是

對偶函式產生了原問題(1)最優值p*的一個下界，也就是說，對於任意的λ≥0和任意的μ來說，有:

≥0，這也就是為什麼在一開始要做這個規定的原因了。

λ

我們如何理解這個不等式(3)呢?下面給出兩個直觀的解釋:

我們首先重寫問題（1），就是把問題（1）換個更加緊湊的方式來表達，首先我們定義示性函式：

同樣我們也可以定義另外一個示性函式：

有了這兩個示性函式的幫助，現在我們可以把問題（1）重新寫成一個沒有約束的形式：

（4）

我們來看看這個最佳化問題（4）和問題（1）是等價的麼？我們可以把（4）的後面兩大項看做是對違反約束條件的x的懲罰函式。

起的作用是對違反不等式約束的x進行“無限的”懲罰，也就一旦

，懲罰就等於無窮大。而

起的作用是對違反等式約束的x進行懲罰，一旦

，懲罰就為無窮大。這樣對（4）中目標函式的最佳化跟對（1）中目標函式在約束條件下的最佳化就是同一回事，是不是？也就是說，（1）和（4）這兩個問題是等價的問題，但是在（4）中約束被融合到目標函式中來了。

現在我們再回頭看看（2），也就是拉格朗日對偶函式，它也是個最佳化問題，我們對比它所最佳化的函式和（4）中所最佳化的函式，把它們重寫在一起：

（2）中的目標函式

（4）中的目標函式

可見在問題（2）和問題（4）中，我們最佳化的目標函式區別在於懲罰項不同，（4）中的懲罰項是無限的，就是說一旦違反約束，就施加無窮大的懲罰；而在（2）中我們的懲罰項是線性的，就是說隨著g i（x）和h i（x）的不同，懲罰項是線性變化的。所以（2）和（4）中需要最佳化的目標函式有很大的不同，用（2）來逼近（4）是很不準確的。但是我們可以看出，對於任意的u，任意的

解釋一:線性逼近的解釋

≥0和任意的

λ

來說都有：

（我們把λ限制為大於等於0了）

所以在任意點，（2）中的目標函式的值都是小於（4）中的目標函式的值，所以（2）中找到的最優值肯定是小於（4）中找到的最優值的。再結合前面說的（1）和（4）是等價的問題，所以不等式（3）是成立的。

μ

我們首先可以看出：

為什麼會有這個結果呢？當x滿足約束的時候，也就是對所有的i來說有

並且

，如果我們想透過調整

解釋二:交換max和min的次序

和

λ

讓

變大怎麼辦呢？只有讓

μ

全部為0（注意

λ

只能大於等於0），這樣就消去了小於0的項，至於

，無論

λ

怎麼變都是沒有影響的。所以當x屬於可行域的時候上式的結果是f（x）。如果x違反了約束呢？在做sup運算的時候只需要對滿足

和

的項對應的乘子定為+∞，而把其他的項對應的乘子設為0，就可以讓整個式子的結果變為無窮大。

所以我們可以看出來，在問題（1）中的帶約束的最佳化問題和直接最佳化是一回事，也就是說：

現在我們把inf和sup兩個運算子調換次序，顯然有：

我們重寫（2）式：

（2）

可以看出結論了，也就是

μ

≥0時（3）式成立：

（3）

好了，費了半天的勁我們說明了一個問題，就是不等式（3）是怎麼來的。

總結一下，不等式（3）用文字敘述就是：

λ

至於我們得到這個結果有什麼用，下節再說。

如果我們把拉格朗日函式看做是x的函式，然後取下確界(注意:是在整個定義域裡取下確界，而不是僅僅在可行域裡取值，也就是說取下確界時對x是沒有約束的)，那麼得到的結果就是原最佳化問題(1)的最優值的一個下界。

回憶上一節，對如下的原問題：

（1）

我們定義了拉格朗日對偶函式：

然後我們證明了：，其中p*是原問題的最優值。

對偶問題

。既然我們找到了一個下界，顯然我們要找到它最好的下界。什麼是最好的下界的？顯然就是所有下界當中最大的那一個。所以我們要把

最大化，當然我們還要記得我們需要限制

。我們把要最佳化的函式和約束條件正式寫下來就是：

（2）

也就是說我們找到了原問題最優值的一個下界

顯然，對偶問題的最優值d*就是我們可以獲得的p*的最優下界，也就是所有下界中離p*最近的一個，它們的關係是：

（3）

我們把這個不等式叫做

與原問題(1)相對應，我們把上面的問題(2)稱作拉格朗日對偶問題(Lagrange dual problem)。

。

順其自然，我們可以引出一個重要的概念，對偶間隙，其定義為，用文字敘述就是原問題的最優值與透過拉個郎日對偶函式獲得的其最好（最大）的下界之差。由不等式（3）可以看出，對偶間隙肯定是大於等於0的。

那麼有沒有可能在某種情況下，對偶間隙消失了呢？也就是說對偶問題的最優值與原問題的最優值相等了呢？

我們將要敘述一下Slater條件：

弱對偶性質(Weak Duality)

存在x滿足：

Slater條件即是說存在x，使不等式約束中的“小於等於號”要嚴格取到“小於號”。

可以證明，對於凸最佳化問題（關於凸最佳化問題，請參考

Slater條件:

），如果Slater條件滿足了，則：

這種情況稱為

維基百科

強對偶性質(Strong Duality)。

如果對偶間隙消失了，也就是說，如果對偶問題存在著最優點

下面的問題是，如果對偶間隙消失了，會發生什麼有趣的現象呢?

並且使其對應的最優值

等於p*，這時會發生什麼情況呢？還記得上一節我們證明

的過程麼：

（4）

在對偶間隙消失的情況下，中間所有的不等號都要變成等號：

（5）

注意，（5）中的

λ*,μ*

和

λ

都加了星號，表示它們是對偶問題的最優點。（5）中有兩個重要的等號，已經加了標記。

我們能得出什麼結論？

1。我們先來看等號1：

它說明了原問題的最優點x*是使取得最小值的點。

2。 我們再來看等號2：

它說明了：

由於我們限制了每一個λi≥0，所以上式中每一項都是非正的。這樣我們又可以得出結論：

（6）

等式（6）被稱作是

μ

，我們可以把它換種寫法：

或者寫成它的等價形式（逆否命題）：

也就是說，只要一個不為0，另一個就必為0！

互補性條件有著重要的意義。它說明了當

時，x*是處於可行域的內部的，這時不等式約束並不起作用，此時

；而

的點肯定是可行域邊界的點（

）。也就是說 只有積極約束才有不為0的對偶變數。而這在支援向量機中有著重要的意義。回想在第一節我們最後的結論，支援向量機尋找最大間隔超平面可以歸結為一個最佳化問題：

互補性條件

目標函式:

那麼哪些不等式約束對應著不為0的對偶變數呢？顯然，只有當

時，這個約束對應的對偶變數才可能不為0，而

意味著什麼？意味著這個約束對應的樣本點x i是支援向量！也就是說：

限制: