Perceptron Learning Algorithm (PLA)
根據林軒田教授的機器學習基石課程，實作一下這個基礎的機器學習演算法。 我們探討的是監督式學習 (Supervised learning) 大架構下的二元分類 (YES/NO) 問題。
Perceptron ⇔ linear (Binary) Classifiers
我們有一組訓練資料 D，包含數據 Xn 和對應的 Yn (在這裡就是 1, -1)；Hypothesis set H 代表全部可能的解 (無限多條線)，經過演算法 A，從 H 找到一個可能的 g 與我們的目標函數 f 相近。
這個演算法的主要兩大步驟：找到錯誤的點，進行向量修正。
詳細課程可以參考教授的講解！！其中 naive cycle 是常用的作法。
這方法只適用於 linear separable PLA。
除此以外，當資料中有雜訊也無法使用這個方式，目前在線性問題上較好的解是用 Pocket PLA。
向量修正那一步
「進行向量修正」寫成一行是 w ← w + y·x，把分錯那個點的座標乘上它的標籤（+1 或 -1），加到權重向量上面。分類的依據是內積 w·x 的正負號，所以這一步真正動到的是內積。
把修正後的權重拿去算同一個點，得到的是 (w + y·x)·x，展開就是 w·x + y·(x·x)。x·x 是這個點到原點距離的平方，不會是負的，再乘上標籤，正例的內積往上加、負例往下減，兩邊都朝自己該去的方向移動一段。分界線是垂直於 w 的那條線，w 轉了多少，線就跟著轉多少。
移動一次不保證那個點就分對了。原本的 w·x 如果離零很遠，加一次 x·x 未必翻得過去，得等下一輪再挑到它；更常見的是這個點修好了，線轉過去的同時把原本站對邊的其他點掃到錯的那一側，下一輪換那些點來要求修正。
這一步有兩件事沒有做。加上去的量是 x·x，只跟這個點離原點多遠有關，跟它錯得多嚴重無關，差一點點分錯的點和遠遠站在另一邊的點，推的力道一樣大。分對的點則完全不出力，w 一動也不動。scikit-learn 的文件描述 Perceptron 的預設行為時寫：「It updates its model only on mistakes.」
Linear separable PLA
首先整理一下資料。把原始格式如 ['x0\ty0\tz0\nx1\ty1\tz1\nx2\ty2\tz2\n....'] 轉換為 array([[(x0, y0), z0], [(x1, y1), z1], [(x2, y2), z2].....]) 的格式。
import matplotlib.pyplot as plt
import numpy as np
# import data
train_data = open('PLA_train.txt','r')
pla_data = train_data.read()
pla_data = pla_data.split('\n')
nums1 = 0
# figure
fig = plt.figure()
ax = fig.add_subplot(111)
ax.set_xlim(-0.5,0.5)
ax.set_ylim(-0.5,0.5)
# data type
for i in pla_data:
pla_data[nums1] = i.split('\t')
pla_data[nums1] = [float(x) for x in pla_data[nums1]]
pla_data[nums1] = [(pla_data[nums1][0], pla_data[nums1][1]),
pla_data[nums1][2]]
if pla_data[nums1][1] == 1:
ax.plot(pla_data[nums1][0][0],pla_data[nums1][0][1],'bo')
elif pla_data[nums1][1] == -1:
ax.plot(pla_data[nums1][0][0],pla_data[nums1][0][1],'rx')
nums1 += 1
pla_data = np.asarray(pla_data)
print(pla_data)
train_data.close()
NAIVE PLA 實作，畫線則是用 ax + by = 0。
# naive LS PLA
def LS_pla(datas):
w = np.zeros(2)
error = 1
while error:
error = 0
for x,s in datas:
x = np.array(x)
y = w.T.dot(x)
try:
ax.lines.remove(lines[0])
except:
pass
xline = np.linspace(-0.5,0.5)
lines = ax.plot(xline, -xline*w[0]/w[1])
plt.pause(0.1)
if np.sign(y) != np.sign(s):
w += s * x
error = 1
if not error:
break
return w
W = LS_pla(pla_data)
print(W)
plt.ion()
plt.show()
最終結果
收斂的前提
「這方法只適用於 linear separable」這句話後面有一條證明。維基百科寫的是：「If the training set is linearly separable, then the perceptron is guaranteed to converge after making finitely many mistakes.」Cornell CS4780 的講義寫，資料線性可分時 PLA 會在有限次更新內找到一條把兩類分開的線，資料不可分的話它會一直跑下去。
有限是多少次，講義也給了。先把資料縮放到單位球裡面，更新次數的上界是 1/γ²；γ 一般叫做 margin，量的是理想的那條分界線離最近的資料點有多遠。這個式子裡面沒有資料筆數。一百個點和一百萬個點，只要最窄的那條走廊一樣寬，上界就是同一個數；反過來，兩類靠得越近，γ 越小，1/γ² 抬得越高，一樣是可分的資料，可以慢到跑不完。
保證裡只有「會停」這件事。能把兩類分開的線通常有無限多條，PLA 最後停在哪一條取決於挑點的順序，線與線之間好壞的差別它沒有處理，這一塊由後來的 linear support-vector machine 補上。維基百科寫的是：「it may still pick any solution and problems may admit many solutions of varying quality」。
換一份沒辦法用一條線切開的資料，每一輪照樣挑得到分錯的點，照樣把 y·x 加上去，只是這個來回不會結束。維基百科寫的是：「In case the training set D is not linearly separable, i.e. if the positive examples cannot be separated from the negative examples by a hyperplane, then the algorithm would not converge since there is no solution.」沒有一個 w 能讓所有點同時滿足，演算法就永遠找得到下一個要修的點。
不會停之外還有一件事，權重不會一路變好。每一次修正都只對當下挑到的那個點負責，把它扳回正確的一側，順手把別的點推到錯的一側，所以第 1000 輪手上那條線跟第 999 輪比可能更差，多跑幾輪不等於拿到比較好的答案，隨手在某個輪數收工，拿到的就是那一輪的那條線。
Pocket PLA
Pocket PLA 是一個貪婪演算法，把最好的權重握在手上繼續往下算，每次都會比較看有沒有比手上的好。停止方式則是讓它運行一定次數，或是多久沒有變更好等等。這裡暫不詳述。
Pocket 的代價
握著最好的那一組是要付成本的。naive PLA 一輪只看一個點，Pocket 每更新一次都得拿整份資料重算一遍錯誤數，才知道新的那組有沒有比手上的好，一輪的開銷從一個點變成整份資料。維基百科對它找到的解寫的是「appear purely stochastically」，不會隨著訓練逐步逼近，也不保證在指定的步數內出現，所以停下來的時機只能訂在跑滿幾輪、或是多久沒有進步。
後來的更新規則
分錯才動、動的幅度跟錯多少無關，這兩件事讓 PLA 每一輪的計算很省，也讓它在有雜訊的資料上交不出穩定的答案。今天在用的線性分類器多半把這兩件事一起換掉了。
scikit-learn 目前的 Perceptron 是 SGDClassifier 的包裝，文件上寫：「Perceptron() is equivalent to SGDClassifier(loss=“perceptron”, eta0=1, learning_rate=“constant”, penalty=None)」。PLA 那條規則變成了 loss 的一個值。
scikit-learn 的 SGD 文件列了幾個常見的損失函數。perceptron 是 max(0, -y·f(x))，只要分對，不管離邊界多近，損失都是 0，這個點就不出力；hinge 是 max(0, 1 - y·f(x))，要分對而且離邊界一個單位以上才歸零，貼著邊界的點還在出力，margin 從這裡進到目標函數裡；log loss 是 log(1 + exp(-y·f(x)))，這個函數在任何地方都不等於零，連分得很開的點都還留著一點梯度，錯得越多梯度越接近滿格。
更新規則換掉之後，停下來的判斷也跟著換。找不到分錯的點這個條件，在不可分的資料上永遠不會成立，取而代之的是損失不再明顯下降、或是跑滿設定的輪數。scikit-learn 的 Perceptron 目前預設 max_iter=1000、tol=0.001，用的是後面這一種。
