PLA和pocket算法：简单Python实现
PLA 的 Python实现——机器学习基石作业
机器学习基石（上）第四周的选择题作业里有几个关于PLA的习题需要编程解决（15题-20题），因此在这里我用python3简单实现了PLA算法和pocket算法。
本文使用Jupyter notebook导出markdown文件生成。
from scipy import *
from matplotlib.pyplot import *
数据集是题目中提供的。
data = loadtxt(r'C:\Users\huang\Desktop\Chapter.1\vs code\pla.txt') # load data from txt file
data.shape # the dataset size is 400, with x 4 dimensions and y 1 dimension
(400, 5)
可视化处理
尽管这里并不要求我们这么做，但是得到一个数据集后，很自然的想法就是对它进行可视化。
这里 $x$ 的维数较高，不方便直接进行可视化。但之前我有上过吴恩达的《Machine Learning》课程，里面介绍了一种叫PCA(主成分分析）的方法，可以用于数据降维，从而实现可视化。这里我们就小小地学以致用一下。
# firstly, normalize the data
x = data[:,0:4] # take the input out
x_norm = x.copy() # make sure the base is None
x_mean = x_norm.mean(axis = 0)
x_std = x_norm.std(axis = 0)
x_norm = (x_norm - x_mean)/x_std
# calculate the covariance matrix
x_cov = x_norm.T.dot(x_norm)/400
# do SVD
U, S, V = np.linalg.svd(x_cov)
UReduce = U[:, 0:2] # take the first two dimensions
z = x_norm.dot(UReduce)
z1 = z[where(data[:,-1] == 1)]
z2 = z[where(data[:,-1] == -1)]
fig = figure()
ax = subplot(111)
ax.plot(z1[:,0], z1[:,1],'*',label = '$y = 1$')
ax.plot(z2[:,0], z2[:,1],'r*', label = '$y = -1$')
title('Visualization of Dataset')
ax.legend(loc = 'upper left', fontsize = 'small')
<matplotlib.legend.Legend at 0x20ec4995748>
可以看出 $y$ 为$-1,1$ 的两组点分布区域还是比较分明的。虽然在这个2D图上似乎没有办法找到一条直线把他们完美地分开，但不要忘记这是我们经过降维处理的图像。总之，既然是题目里给的数据集，那肯定是线性可分的了（笑）。
naive PLA algorithm
def PLA(mat):
'''
The function PLA is used to implement the PLA algorithm.
Parameter mat is the matrix of the dataset.
We start from w0 = 0 here.(Asuming sign(0) = -1)
'''
m,n = mat.shape
w = zeros(n) # start from 0
all_correct = False # as a mark to tell if the PLA ends
update_cnt = 0 # counting the number of updating iterations
bias = ones(m)
x_vec = c_[bias,mat] # add the bias terms
while not all_correct:
all_correct = True # after the for-loop if still True, the while-loop will end
for dat in x_vec:
temp = w @ dat[0:-1]
if temp == 0:
# for we consider sign(0) = -1 here
temp = -1
if sign(temp) != sign(dat[-1]):
w += dat[-1] * dat[0:-1] # update the weight
all_correct = False
update_cnt += 1
return w, update_cnt
w, iteration = PLA(data)
print(w,'\n',iteration)
[-3. 3.0841436 -1.583081 2.391305 4.5287635]
45
这样是能够完成简单的PLA算法没有错，但是两重循环的写法并不符合我们vectorization的思想：我们知道，使用numpy和MATLAB的时候，向量化能产生更简洁、更快速的代码。因此我决定对对上述代码进行一些修改。
def new_PLA(mat):
'''
rewrite the naive PLA algorithm using vectorazation.
'''
m,n = mat.shape
w = zeros(n)
bias = ones(m)
x_vec = c_[bias, mat] # add the bias terms
update_cnt = 0
prepos = -1 # the previous position
while True:
out = sign(x_vec[:,0:-1] @ w)
out[out == 0] = -1 # sign(0) = -1 here
false_ind = where(out != sign(x_vec[:,-1]))[0] # indices where PLA is false
if not false_ind.any():
break # no false points
if not false_ind[false_ind > prepos].any():
prepos = -1
pos = false_ind[false_ind > prepos][0]
w += x_vec[pos, -1] * x_vec[pos, 0:-1] # updating the weight
prepos = pos
update_cnt += 1
return w, update_cnt
w1, iteration1 = new_PLA(data)
print(w1,'\n', iteration1)
[-3. 3.0841436 -1.583081 2.391305 4.5287635]
45
两种方法得到了一样的结果，说明应该大体是正确的。不过值得注意的是，这道题中的选项都是范围。
我也在网络上看到别的朋友得到了不一样的结果，有的是 $37$ 次，有的是 $39$ 次。
看了一个朋友的代码后，我发现我们的不同之处在于：我每次更新权重 $w$ 后，下一次的检验是从当前位置的下一个开始的；而他的做法是继续检验当前位置。这是可以理解的做法——因为根据我们的更新公式，我们每次更新只是在缩小 $w$ 和 $x$ 的夹角，但并不能保证当前位置一次就调整完毕了，因此每次更新完继续回到这个点检验是很有道理的。把代码改成这种写法是非常容易的，我这里就不啰嗦了。
不同的方式导致了结果的不同，但大致上都在题中所给的 $31-50$ 次这个范围中。(虽然根据我的检验，好像每次从最开始开始检验需要更新 $60$ 次……）
下一题规定了我们每次检验的方式：随机得到一个顺序，每次检验按照这个顺序进行。
total = 0
m,n = data.shape
for i in range(2000):
rand_per = random.permutation(m)
data_rand = data[rand_per,:]
w, iterations = new_PLA(data_rand)
total += iterations
total/2000
40.1695
data1 = loadtxt(r'C:\Users\huang\Desktop\Chapter.1\vs code\pocket.txt')
test = loadtxt(r'C:\Users\huang\Desktop\Chapter.1\vs code\test.txt')
test.shape
(500, 5)
pocket algorithm
pocket算法运用了贪心的思想：直到产生了错误更少的结果，才进行更新。
def pocket(mat, iter_num = 50):
'''
pocket algorithm implement.
what is different from PLA is that pocket pick a random point each time
and update if the new point causes less mistakes
'''
m,n = mat.shape
w = zeros(n)
bias = ones(m)
x_vec = c_[bias,mat] # add the bias term
out = sign(x_vec[:,0:-1] @ w)
out[out == 0 ] = -1 # for sign(0) = -1 here
pre_error = sum((out - x_vec[:,-1]) != 0) # calculate the error
for i in range(iter_num):
false_id = where(out != x_vec[:,-1])[0] # the indices of mistakes
if not false_id.any():
break
rand_id = false_id[random.randint(len(false_id))] # randomly pick one false point
w += x_vec[rand_id,-1] * x_vec[rand_id,0:-1] # updating the weight
out = sign(x_vec[:,0:-1] @ w)
out[out == 0] = -1
new_error = sum((out - x_vec[:,-1]) != 0)
if new_error < pre_error:
w_pocket = w.copy() # w_pocket's base should not be w
pre_error = new_error
return w_pocket
total = 0
for i in range(2000):
a,b = test.shape
bias = ones(a)
test_vec = c_[bias, test]
rand_per = random.permutation(m)
data_rand = data1[rand_per,:]
w_pocket = pocket(data_rand)
out = sign(test_vec[:,0:-1] @ w_pocket)
out[out == 0] = -1
error = sum((out - test_vec[:,-1]) != 0)
total += error/a
total/2000
0.13328099999999982
下一题要求我们的pocket算法不返回 $w_{pocket}$ ，而返回 $w$，再重复上述步骤，计算平均错误率。
这只需要把pocket函数的返回值修改一下就好了，算出来的结果大概是 $0.36$ 左右。
最后一题要求我们在每次循环 $100$次，而非 $50$ 次，再观察结果。
这只需要在调用pocket函数时，多加上循环次数这个参数即可（因为默认为 $50$ 次):
w_pocket = pocket(data_rand,100)
结果大概是 $0.11$。
This blog is under a CC BY-NC-SA 3.0 Unported License
Link to this article: https://huangweiran.club/2018/09/03/PLA和pocket算法：简单Python实现/