SVM(Support Vector Machines)

我們在一個分類問題中，我們需要找到一個超平面(Hyperplane)來分隔不同的類別，就如同圖中的線，但能分隔不同的類別的超平面有無限多個(圖中就有3個)，我們希望得到的是最右圖那一條線，他的margin(邊界)(灰色區(qū)域)越大越好，意思就是這條線離所有的點(diǎn)越遠(yuǎn)越好，這樣的好處是能容忍的測量誤差大，不容易o(hù)verfitting。

這邊與PLA不同的是，我們不將bias轉(zhuǎn)成 $w_0$ 以及加上 $x_0=1$ 。

$x(x_n)$ 表示空間中的某個座標(biāo)，x'表示在平面上的某個座標(biāo)，我們假設(shè)有一個平面是 $w^T x'+b$ ，假設(shè)兩個剛好在平面上的兩個點(diǎn)x',x''，表示 $w^T x'=-b$ 而且 $w^T x''=-b$ ，那麼 $w^T(x''-x')=0$ 。

而(x''-x')是一個向量，那 $w^T(x''-x')=0$ 表示 $w$ 是(x''-x')的法向量，則x到平面的距離distance(x,h)就是(x-x')向量到w方向的投影，得到的距離會再加上絕對值避免負(fù)值。

$distance=cos\theta ||(x-x')||$
$= | \ \frac{w^T (x-x')}{||w|| \ ||(x-x')||} ||(x-x')|| \ | = | \ \frac{w^T (x-x')}{||w||} \ | = | \ \frac{w^T x + b}{||w||} \ |$

我們希望最後找到的這個預(yù)測的值是與y同(正負(fù))號的，，然而margin(邊界)代表的最小值，我們要找到能讓邊界最大的w跟b為解。

假設(shè)我們找到一個解為，但同時也為解，括號內(nèi)可以任意縮放，這邊的w、b為常數(shù)(不是未知數(shù))，這樣我們還是有無限多組解，我們希望只要找到唯一的一組。
現(xiàn)在我們限制條件進(jìn)行放縮只能是讓它跟相乘會是 1，也就是，這樣原本的 margin(b,w) 就是可以轉(zhuǎn)換成的長度。
變成求滿足(1) max 及 (2) min 這兩個條件的w、b。

我們放鬆條件使讓我們方便求解。
變成求滿足(1) max 及 (2) min 這兩個條件的w、b，但放鬆條件會不會讓我們得到不同的解(w,b)。
使min 成立的w中能使最大的那個會不會與使min 成立的w中能使最大的那個相同? 答案是兩個最佳解相同。

如果現(xiàn)在找到的解(w,b)是最佳解， $y_n (w^T x_n + b) > 1.126$ ，因爲(wèi)是最優(yōu)解，所以當(dāng)前的(w,b)一定是讓 $\frac{ 1 }{||w||}$ 的值最大的解，此時我們可以縮放w跟b同除1.126，會得到 $y_n ( \frac{w^T}{1.126} x_n + \frac{1.126}) = 1$ ，而此時的w應(yīng)該能比原本的1.126w得到更大的 $\frac{ 1 }{||w||}$ ，那麼原先假設(shè)不成立。同理可證，在 $y_n (w^T x_n + b) = 1$ 不等於1時的(w,b)均不是最優(yōu)解。