機器學習_學習筆記系列(06)：線性分類(Linear Classification)和感知器(Perceptron)
不知道大家還記不記得，在之前我們有介紹一個非常簡單的機器學習演算法：感知器(Perceptron)，而感知器其就是一個非常經典的線性分類演算法
感知器(Perceptron)
之前在介紹感知器的時候，我們的演算法如下：
其中h(x)就是我們的假設方程式，w就是指權重(為向量)，x就是我們輸入的資料(為向量)。另外右上角的T就是transpose，對矩陣做轉置，sign的意思就是當括號裡面數值大於0他就會等於+1，小於0他就會等於-1。
那我們現在有了前幾個章節的基礎後，我們能不能提出一些更專業的問題像是，怎麼確保Ein和Eout很接近，還有怎麼讓Ein變小。
我們知道在線性模型當中，其VC Dimension dvc=d+1，(d:維度)，所以我們可以根據VC Generalization bound列出：
(big O：就是指複雜度)，所以我們可以看到，當樣本數量N越大，我們的Ein就會越來越接近Eout。
那如何讓Ein很小呢？如果我們拿到的資料是線性可分的，也就是說一定找的到一條線將圈圈和叉叉分開來。所以這代表了我們找到完美的解，使Ein(w*)=0，這裡*是指假設的意思。
但實際上很多情況我們拿到的資料都是線性不可分的，那要怎麼在這種情況下，還是能找到一個最佳的解，讓分類錯誤的點數降到最低，也就是讓我們Ein最低呢？
所以這裡我們引入一個最佳化的方程式
我們先由內往外看，sign(wx)不等於y，這裡可以理解成，這個點分類錯了，他原本(y)要為+1(圈圈)，但是現在sign(wx)為-1(叉叉)，而雙括號的意思就是指裡面的式子成立就會等於1，不是則等於0。所以Ein我們可以把他看成，計算所有分類錯誤的點的個數，然後再除以全部數據點的個數(N)，也就是錯誤率的意思啦！
那這裡的min就是指最小化的意思，所以這個式子代表的就是，我們希望我們分類錯誤率達到最低。
那在每一次迴圈當中，我們更新權重w的方法如下：
w(t+1)=w(t)+y*x
t代表更新的次數，w(t)就是這次的權重值，w(t+1)代表下一次更新的權重值。
另外這裡我們要注意到如果我們輸入資料是二維的，在執行演算法時，我們會在x前補1，讓我們的輸入資料變成三維。
也就是原本資料是[0.2 0.8]補上1後變成[1 0.2 0.8]。這樣做的原因是我們把原本的偏差b納入權重w裡面了。原本是w1*x1+w2*x2+b，現在變成w1*x1+w2*x2+w0，所以我們必須在輸入資料前面補上1，如此一來，帶入[1 0.2 0.8]到方程式才會等於，0.2*w1+0.8*w2+w0。
所以這裡可以理解成，輸入資料x如果是圈圈(y=+1)，sign(w*x)應該要為+1，但是現在電腦分類錯了，使得sign(w*x)為-1，這代表我們現在的權重w(t)乘上輸入資料x小於0，所以我們讓w(t)加上y*x，在下一次計算中，會使得h(x)=sign(w*x+y*x*x)
這裡可以看到h(x)和上一次的差別就是多了y*x*x，相信到這裡大家就能理解為什麼演算法要這樣設計，因為y是+1，x*x一定是正數，所以sign裡面的值會在每一次更新中越來越大值到他超過0為止。相反的如果輸入資料x為叉叉(y=-1)，sign裡面的值就會越來越小直到其小於0為止。
那整個演算法流程如下：
Python Sample Code
有上上述的演算法，我們就可以用Python把他實現化
Github:
Reference：
[1] Abu-Mostafa, Y. S., Magdon-Ismail, M., & Lin, H. T. (2012). Learning from data (Vol. 4). New York, NY, USA:: AMLBook.
[2] 台大資工 林軒田 教授, 機器學習基石(上), Coursera
***本系列完全沒有開任何營利***
作者：劉智皓
linkedin: CHIH-HAO LIU
