# Linear Separator 線性分類器

## 前言
常常看到機器學習的相關課程在介紹線性分類器(Linear Separator)時，在當下總是覺得講得很有道理，但是總覺得哪裡怪怪的，重新仔細的檢驗之後，才發覺這些教學課程省略許多細節，因此在此重新用我自己所理解的方式闡述一次，目標放在只用高中生的學識也能理解，如有錯誤，歡迎指教。

## 本文
如果我們今天想要做一個二元分類器(Binary Classifier)，來判斷某一筆資料$X=(x_1, x_2, ...., x_n)$是否屬於該分類 (true or false)，舉例來說，若有一個二元分類器能夠判斷某人是否為男人或女人，假設每個人的資訊含有(年齡,身高,體重,胸圍,腰圍,臀圍,肩寬)，有7維資料，而這個線性能夠根據這些資訊判斷某個人的性別。

線性分類器就是要訓練出一組權重$W=(w_1，w_2,....,w_n)$，對資料$X$線性組合相乘後，$WX >= t$, 代表屬於該分類(true), $WX < t$，代表不屬於該分類(false)。

其中t為一個門檻值，也是可以訓練的，因此我們可以用一個小技巧將此門檻值設為$w_0$，也就是現在要訓練的權重為$W=(w_0,w_1,w_2,....,w_n)$，

而資料點也新增一個維度值都為$1$,也就是$X=(1, x_1, x_2, ...., x_n)$，以上述的例子而言，每筆資料也都變成8維資料，(1,年齡,身高,體重,胸圍,腰圍,臀圍,肩寬)，也就是把原式改成$WX >=0$，代表屬於該分類，原式$WX<0$，代表不屬於該分類。

若將所有資料點$X$置於$n+1$維度的座標系上，$WX=0$所代表的是一個超平面(hyperplane)，將這些資料點分割成一邊是true，一邊是false。

若$n=1$，$WX=0$ 代表一條直線；

若$n=2$，$WX=0$ 代表一個平面；$n$超過$2以後比較難用幾何意義來形容或視覺化$。

很顯然的，$WX=0$ 必定通過原點 $(0,0,0,0,.......)$。

對於$n=1$ 與$n=2$ 的狀況，分別嘗試以圖表示如下:

### 直線的情況

$n=1$，假設想要區分一個 NOT 函式 (function)，輸入1時，判定成false；輸入0，判定成true， 如同我們前面所提到對於每個資料點增加多1維為1的資料。

因此新資料點為(1,1) 在圖上用紅色$-$號表示false，與(1,0)，在圖上用綠色$+$號表示 true，有一條斜線$x_0-2x_1=0$，將(1,0) 帶入$WX=1$ 大於等於0，將(1,1) 帶入$WX=-1$ 小於$0$, 因此這個WX符合我們先前的定義, 而邊界這條$WX=0$恰好區分這兩個區域, 我們稱這條線為Decision Boundary。


### 平面的情況

在$n=2$ 的情況，資料為3維，我們以AND function為例，true的case為(1,1,1)，false的case為(1,0,1)，(1,1,0)，(1,0,0)。

有一個平面 $-4x_0 + 3x_1 + 3x_2 = 0$，分別將4個資料點帶入，也符合我們前面的定義, 因此為Decision Boundary。因此$-4x_0 + 3x_1 + 3x_2$ 為該AND function的Linear Separator。


但有可能這個hyperplane一開始並不一定恰好可以分類這些資料點，因此有人想出怎麼調整這個平面讓他逐漸符合Decision Boundary。

這個演算法稱為感知器演算法 (Perceptron Algorithm)。

### 感知器演算法

演算法大致上如下:

若一true資料點代入WX < 0，被分類為false，以幾何意義來看代表，由於WX通過原點，W可以視為其法向量，而$WX$為其W向量與X向量的內積

由於 $WX = |W||X|cosA$，其中$A$為兩個向量之間的夾角，

若$W$正確分類$X$為true，則其法向量必與$X$向量夾角小於90度；

反之，$W$正確分類$X$為false，則其法向量必與$X$向量夾角大於90度

因此一個true資料點若分類到false，我們希望讓該法向量旋轉到從大於90度，轉變成小於90度。

(cos0 到 cos180 為從 1到-1的值域)

因此我們希望更新$W$讓$WX$大於舊的$WX$，新的線法向量與資料向量的角度就會變小了，因此採用以下的公式。

$W' = W+\alpha*X，\alpha > 0$

證明如下:

$W'X = (W+\alpha*X)X= WX +\alpha XX = WX+\alpha|X|^2$，

由於$\alpha > 0$，因此$W'X >WX$，我們就可以讓該直線轉向趨於接近分類正確的角度。

若資料點是false，但錯誤分類到true，

$W' = W - \alpha*X，\alpha > 0$，依此類推

針對每一個資料點都做一次，直到每個點都符合分類正確後演算法停止，最後的$W$則代表我們找到了Decision Boundary，而該$W$也就是符合這些資料點的線性分類器之權重。

然而這是針對資料點是線性可分的狀況，線性分類器才能夠完全正確分類。

像XOR這個function，是無法使用線性分類完美分類的，之後有機會此筆記會再更新說明一下。