上一章我們介紹了SVM算法的意義，SVM是large-margin算法，旨在找到一條能夠完全區(qū)分訓練集而且擁有最大margin值的直線。在這一章節(jié)里，我們將推導(dǎo)margin的計算方式和SVM最終要解決的問題的方程表達式。

任意點到?jīng)Q策邊界距離（1） － 初步表達式

上章節(jié)我們提到，margin值就是所有數(shù)據(jù)點到?jīng)Q策邊界的距離里面的最小值，所以首先我們要計算平面內(nèi)任意一點到?jīng)Q策邊界的距離。為了使得表述和理解更簡單，在下面的所有推導(dǎo)中，我們都采用二維平面內(nèi)的數(shù)據(jù)作為例子去做解釋。二維平面得到的結(jié)論可以推廣到任意維度的空間當中。

上圖是一個在上一章節(jié)用過的二維數(shù)據(jù)集例子。在圖中，紅色的數(shù)據(jù)點是需要計算到?jīng)Q策邊界距離的點，我們標注其為X。X1為決策邊界上的點。注意，這里的X1跟坐標軸上的x1不一樣，這里的X1是一個點，也是一個擁有兩個維度的向量。坐標軸上的x1是兩個維度對應(yīng)的值的大小，是標量。圖中的distance是我們需要計算的距離，該線段與決策邊界垂直且與點X相交。

現(xiàn)在，假定圖中的決策邊界是由特征權(quán)重向量W和偏差值b決定的，既對于任意數(shù)據(jù)點，h(X) = sign(W^TX + b)，該分類器是一個線性分類器(linear classifier)。對于任意數(shù)據(jù)X，當W^TX + b > 0的時候預(yù)測該點為正類，當W^TX + b < 0的時候預(yù)測該點為負類。當W^TX + b = 0的時候，該點正好落在決策邊緣上，此時分類器將其預(yù)測為正類來打破平衡(tie-break)。因此，我們很容易得到?jīng)Q策邊界的方程為W^TX + b = 0。

為了計算點X到?jīng)Q策邊界的距離，我們做了一條輔助線，這條輔助線穿過點X和決策邊界上的一點X1。根據(jù)高中幾何知識我們知道X到?jīng)Q策邊緣的距離D，是向量X X1長度在垂直于決策邊界方向上的投影，既Distance = ||X - X1||cos(a)，a為向量XX1與垂直于決策邊界方向的夾角。

此時，要計算Distance大小我們有兩個方法，第一個方法是計算角度a以及||X - X1||的大小，第二個方法是找到一個垂直于決策邊界的向量，假設(shè)是P。則距離

對于以上的公式推導(dǎo)，我們將會在下面演示。

根據(jù)經(jīng)驗而言，求法向量P往往比求角度a要簡單一些，所以我們在這里采用第二種方法。由于我們最終需要用權(quán)重向量W和偏差b來表示距離大小，所以上面公式的是距離的初步表達式，我們還需要進行進一步推算。

任意點到?jīng)Q策邊界距離（2） － 初步表達式的證明

剛剛我們提到了第二種計算距離的方法，并給出了計算公式，現(xiàn)在我們要證明計算公式的正確性。

首先根據(jù)向量相乘公式我們知道，兩個向量相乘等于向量長度的乘積再與向量夾角余弦值的乘積。既

任意點到?jīng)Q策邊界距離（3） － 找到跟決策邊界垂直的向量P

在前面我們介紹并推導(dǎo)了任意點到?jīng)Q策邊界距離的初步表達式?，F(xiàn)在，我們要找到公式當中的向量P，一個垂直于決策邊界的向量。

我們把方程組中的上下兩式相減得到 W^T (X1 - X2) = 0。向量相乘等于零說明向量方向互相垂直。因此我們可以得到W^T ⊥ (X1 - X2)。由于X1和X2都落在決策邊界上，所以，(X1 - X2)的方向就是決策邊界的方向。因此W^T就是我們要找的垂直于決策邊界的向量P。

任意點到?jīng)Q策邊界距離（4）－ 最終表達式

上面我們得到了垂直于決策邊界的向量 W^T，現(xiàn)在我們把W^T代入到前面的得到的距離初步表達式當中，

我們把W^T放到后面的括號里面：

因為X1是決策邊界上的一點，所以有

把上式代入Distance公式當中得到

為了讓式子看著更簡單，我們把||W^T||換成||W||，因為
W的長度與其轉(zhuǎn)置的長度一樣。

這個距離公式還存在一個問題，就是W^TX + b的值有可能為負，這樣算出來的距離就會為負值，這不符合我們常規(guī)當中對距離大小的認識，我們常識當中總認為距離是非負的。因此我們在W^TX + b外面加上一個絕對值符號，確保其非負。下面就是任意點X到?jīng)Q策邊界的距離最終表達式：

Margin表達式的推導(dǎo)

前面我們推導(dǎo)了任意點到?jīng)Q策平面的距離表達式，下面我們要把問題回歸到SVM，推導(dǎo)Margin值的表達式。
在上一章節(jié)我們提到，SVM的前提是要把訓練集無錯誤地分開，也就是說，對于所有訓練數(shù)據(jù)X, W^TX + b 于這個點的分類值y_n必須是同號，即y_n (W^TX + b) > 0。
因為y_n只有兩個值，+1和-1, 我們可以把距離公式當中的絕對值符號去掉，但是要添加一個條件：

s.t. 后面的是等式成立的條件，這也是SVM的前提。
我們已經(jīng)知道，Margin值就是所有點Distance的最小值，因此我們得到Margin的表達式：

Margin表達式的簡化

上面我們得到了Margin的表達式，然而要得到上面表達式的最大值仍然有點復(fù)雜，不便于計算，因此我們還需要對表達式進行進一步的簡化，以方便計算。

通過觀察上面的表達式，我們可以把1 / ||W||提到min函數(shù)的前面去，因為1 / ||W||跟n并無關(guān)系，margin公式轉(zhuǎn)換成了：

現(xiàn)在再次觀察新的margin表達式，容易看出我們或許可以嘗試對公式當中min后面的式子進行簡化。假若我們能夠把后面的min值簡化成一個常數(shù)，甚至讓后面的min值簡化成1，那么margin表達式就會剩下一個 1 / ||W||，計算量將會大大減少。

事實上，我們確實可以把表達式當中的min值簡化成1。在說明白這個道理之前，先看一個例子。

對于平面內(nèi)任意決策邊界，W^TX + b ＝ 0?，F(xiàn)在讓其W和b同時放大三倍，既 3W^TX + 3b ＝ 0?？梢院苋菀字?，放大三倍之后的決策邊界跟放大之前的決策邊界是同一條邊界，因此我們可以知道，對W和b同時進行縮放，不會影響決策邊界的位置。

現(xiàn)在我們回到剛剛的margin表達式，我們可以對決策邊界參數(shù)做一個特殊的縮放，假設(shè)縮放倍數(shù)為n，使得其永遠滿足以下條件：

剛剛提到，對決策邊界參數(shù)同時做相同倍數(shù)的縮放不影響決策邊界的位置，因此，W^TX + b ＝ 0 與 nW^TX + nb ＝ 0是同一條直線。所以可以得到相同的結(jié)論：

因此我們可以對margin表達式再次簡化為：

把最小化條件放松

上面我們得到了簡化的margin表達式及其成立條件，表達式只是剩下一個1 / ||W||，已經(jīng)足夠簡單。然而，在讓表達式簡單的同時，我們卻把s.t.后面的條件變得更復(fù)雜了：

原來的條件是一個不等式，現(xiàn)在變成了一個最小化問題，問題變得更加復(fù)雜了，所以現(xiàn)在我們要做的就是把最小化條件放松，使條件再次變成一個不等式。關(guān)于為什么不等式條件會比最小化條件容易解決，我們會在以后的章節(jié)有所解釋。現(xiàn)在我們暫且認同這一點。

現(xiàn)在我們嘗試把原來的最小化條件放松成以下條件：

現(xiàn)在用反證法證明新條件是舊條件的充分條件
假設(shè)一個最大的margin值對應(yīng)的最優(yōu)解為(W, b)，假設(shè)這個最優(yōu)解滿足 ：

此時這個最優(yōu)解滿足新的不等式條件，但是不滿足舊的最小化條件。
此時可以把不等式兩邊同時除以1.1，使其與原來的不等式條件一致：

這時的最優(yōu)解就變成了(W / 1.1, b / 1.1)。

把新的參數(shù)代入margin：

我們發(fā)現(xiàn)，當W變成W / 1.1的時候，||W||的值會變小，margin的值就會更大，解比原來的W更優(yōu)。因此這與原來假設(shè)的(W, b)是最優(yōu)解相互矛盾。

所以，我們可以下結(jié)論，當(W, b)為最優(yōu)解時，最小化條件和不等式條件是互為充要條件，可以作出最小化條件放松的操作。

現(xiàn)在，我們得到了更簡單的margin計算方程，這里把最小化條件去掉了：

margin最大化問題

上面我們得到了margin的計算表達式，現(xiàn)在可以得到我們需要優(yōu)化的模型：

總結(jié)

在這一章節(jié)里，主要講解了如何計算平面內(nèi)任意一點到?jīng)Q策邊界的距離，之后還推導(dǎo)了margin最大化問題的模型。在后面的章節(jié)里，將會繼續(xù)介紹如何解決這一章得到的最大化問題，從而得到最優(yōu)解。

引用

本章節(jié)某些內(nèi)容引用了臺灣大學林軒田老師Standard_Large-Margin_Problem一章節(jié)課件內(nèi)容