PLA和pocket算法：简单Python实现

# PLA 的 Python实现——机器学习基石作业

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)


## 可视化处理

# 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>


## 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


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


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


w_pocket = pocket(data_rand,100)


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实现/