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>

output_6_1.png-17.2kB

可以看出 $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的思想:我们知道,使用numpyMATLAB的时候,向量化能产生更简洁、更快速的代码。因此我决定对对上述代码进行一些修改。

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: http://huangweiran.club/2018/01/27/PLA和pocket算法:简单Python实现/