Applied Machine Learning in Python 6 - support vector machines

Linear line separation

以下的兩個feature如果使用某個linear line function (e.g. x1 = x2) 就可以classify:

在x1-x2=0這條線上方的 point都被classify成黑色，下方都被classify成黃色，相當於以下的linear model:

利用classifier margin來判斷classifier好壞

把decision boundary等量往垂直方向展開，直到抵達第一個training point，此時的面積稱為classifier margin:

下面這個decision boundary較上面為佳，因為有較寬大的classifier margin:

Linear Support Vector Machine

擁有最大classifier margin的 linear classifier稱為 Linear Support Vector Machine (LSVM)，或稱為support vector machine with linear kernel。

所以linear support vector machine的objective function就是要maximize 這個classifier margin。

LSVM也是有regularization可以使用，control parameter稱為C。
C越大，regularization越少，所以越有可能overfitting，即便可能不會找到最大的classifier margin的係數組合。

下途中，右圖是C值大，所以盡量fit training set，左圖則是C小，不過兩者的classifier margin都很小:

Kernelized Support Vector Machines

如果dataset不linear separable怎麼辦? SVM有辦法辦到嗎?

首先SVM可以用在both classification and regression，在此只提classification。
簡單來說SVM就是把dataset的dimensionality提升，提升之後有可能可以進行linear classification。

假設有以下1-D dataset，這個無法用linear classifier把兩個classes分開:

但是如果我們把Xi map成 (Xi, Xi^2) ，等於把feature space提升到了2D，則在此2D feature space此兩個classes 是linear separable。這是純粹數學性的操作，我們並沒有捏造或是臆測任何新的data information，相當聰明。

如果投影(inverse function)回去1D空間，則此decision boundary是一個non-linear boundary"

當然2D dataset 也可以map到3D feature space在做linear classification:

轉換過後，可以用一個linear hyperplane在垂直z軸的方向上隔開兩個classes:

如果投影回去2D空間，此decision boundary相當於一個橢圓。

Radial Basis Function kernel

kernel是一個function，用來衡量一個data point在不同feature space中的相似度。

RBF是一個kernel定義如下:

白話文就是 兩個data point x和x' 在transformed到feature space中的similarity，事實上就是某種distnace function，但是不是線性的。

以下是一個轉換的示意圖:

也是要找到decision boundary maximizes classifier margin。

kernelized SVM 的演算法事實上不需要真的把data points transform到higher feature space，而是只要藉由計算kernel function的值(提高維度之後此data point與目前維度的相似度) 就能找出decision boundary。所以feature transformation是implicit，並非真的去實作的。

RBF kernel parameters

第一個是gamma (kernel width)，這控制了單一data point的影響程度 :

gamma越小，代表input space中的x和x'之間的similarity在feature space中跟距離平方衰減的越慢，也就是在feature space中x和x'不用太靠近也會被視為是同一個class。反之，gamma大則x和x'在feature space中需要非常靠近才會被視為高度similarity。

不過注意gamma是kernel parameter，通常會跟model regularization parameter C 一起調整。
gamma如果大，則C對model結果不會有什麼影響，但是gamma如果小的話，C對SVM的影響就類似對LSVM的影響。

Data normalization matters!!!!

SVM對data scale非常敏感，記得一定要做normalization。