Python機器學習EP. 2 感知器perceptron learning algorithm

哈囉，各位好，我是Teresa，本集的重點是二元分類問題，會說明感知器以及PLA演算法。以下先讓我們回顧上集說了什麼吧～

EP.1回顧

在機器學習中，為了找到一個最適合的假說，存在著演算法(Learning Algorithm A)和假說集合(Hypothesis Set H)。演算法A 從大量資料集合D 進行觀察，接著從假說集合H 中挑選一個最符合我們期望的函式g。

上集提到的例子是如果銀行想要做出一個機器學習來判斷：當客戶申請核發信用卡時，銀行應不應該發卡給該客戶。由這個例子我們可以清楚的知道此機器學習需要提供的答案只有兩種：發卡或是不發卡。這類型的問題我們可以稱為二元分類問題。從客戶提交的申請資料x中經過函式g，來得到y（發卡）或是n（不發卡）的結果。

完整筆記可點此連結

感知器假設集（Perceptron Hypothesis Set）

銀行從過往的經驗中掌握了客戶的屬性資料，如：性別、年齡、職業、薪資、信用狀況……。這些資料都可以轉換成以下式子。

銀行也能針對這些屬性資料進行重要性的排序，給予權重，例如：薪資權重給2，信用狀況如是負債權重給-1等等。

銀行會設立一個門檻值T(threshold)，當上述條件的總分大於門檻值，才會發卡給客戶，反之，則不發卡。雖然有機率總分會剛好等於門檻值，但機率非常小，可忽略不管。

為了方便識別，我們將輸出的結果y(發卡、不發卡、忽略不計)轉為符號表示，這樣的符號在機器學習裡被稱為label。

從算式中，我們很難直接知道畫面看起來是什麼樣子，如果應用在二維平面上，會如下圖，有一條直線將畫面切割成兩個平面，而資料中的點會落在線的兩側，一側為正；一側為負。而機器學習所期望的目標便是找出一條直線，能將不同的label正確劃分在兩個平面上。這樣的感知器便被稱作二元線性分類器(Linear Binary Classifiers)。

（圖片來源：課程截圖）

感知器學習演算法（PLA）

感知器中的所有集合H，代表了平面上許多不同條的直線。

那我們該如何判斷哪條線是我們的最合適的結果呢？這時PLA演算法能回答這個問題。

機器學習從大量資料中觀察後，會從所有假設集合H中學到一個函式g。

我們當然會希望這個g越接近我們想要的目標函數f 越好，

但事實上我們並不曉得目標函數 f 會是什麼樣子。

不過，我們仍可以使用我們已知的資料來判定g是不是最好的線。

假設我們所輸入的資料 x 輸入到函式 f(x) 後都可以得到一個輸出結果 y。

如果機器學習的函式 g，能讓我們從資料集中所輸入的資料 x其輸出結果 y 與 f(x) 完全一致，這時我們就可以說 函式g 是一條適合的線。

在平面上的線有無窮多條，我們無法一一做判別，PLA演算法的核心價值便是逐漸修正。

在取得一條初始線段g0的情況下，找到一個判別錯誤的點，將線段旋轉讓點符合正確的平面，最終會找到一條線gf，讓所有的點都在正確的平面上。

演算法流程如下：

1. 將權重W初始化為W0= 0
2. 搜尋所有二維平面上的點，找出輸出結果與真實label不符合的資料
   1. 若此點存在，執行步驟1，重新執行步驟2
   2. 若此點不存在，停止執行此程式。

將所找到的點標記為

權重更新的公式如下：

左圖：

如果sign( ) = -1，但事實上 y = +1，代表：W和X的夾角過大，W需要向 X 旋轉

右圖：

如果sign( ) = +1，但事實上 y = -1，代表：W和X的夾角過小，W需要向X 的反向旋轉

PLA演算法原則雖然簡單，但仍須要解決以下兩個問題：

1. 演算法什麼時候會停下來、真的會停下來嗎？
2. 如果停下來了，所找到的 gf 真的會接近我們所想要的 f 嗎？

Guarantee of PLA

若要PLA演算法停止，訓練集中的所有樣本必須是線性可分的(linear separable)：

必須存在至少一條線，能讓線切割出的平面全為紅點或藍點。

Non-Separable Data

PLA演算法的優缺點

優點：

1. 實做簡單
2. 適用於任何維度

缺點：

1. 資料必須是線性可分的，但無法事前判別
2. 因為時間複雜度高，也可能耗費很長的執行時間
3. 雜訊(noise)或輸入錯誤，產生線性不可分的資料，導致PLA演算法無法停止。

為了避免PLA演算法無法停止的狀況發生，我們捨棄找一條不犯錯的線，但能找錯誤率最低的線。

最接近此目的的演算法Pocket，屬於PLA演算法的變形，流程如下：

1. 將權重W初始化為W0= 0
2. 搜尋所有二維平面上的點，找出輸出結果與真實label不符合的資料
   1. 若此點存在，執行步驟1後，計算錯誤總數，若總數小於上次的紀錄，則更新紀錄和權重。
   2. 若此點不存在，停止執行此程式。
3. 執行前，設定終止條件，如：執行次數；錯誤總數低於多少時停止……。

機器學習EP. 2 感知器與PLA演算法的介紹就到此結束囉～如果喜歡或想追蹤我更多筆記，可以加入程式小白的 JS Python 學習群的社團。社團中也會有其他學習夥伴和你一起討論、交流、互動哦！