SVM(Support Vector Machines)

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

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

$x(x_n)$ 表示空間中的某個座標，x'表示在平面上的某個座標，我們假設有一個平面是 $w^T x'+b$ ，假設兩個剛好在平面上的兩個點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方向的投影，得到的距離會再加上絕對值避免負值。

$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同(正負)號的，，然而margin(邊界)代表的最小值，我們要找到能讓邊界最大的w跟b為解。

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

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

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