最近在看台大林轩田老师的课，这个感知学习算法(Perception Learning Algorithm)有点意思，好像也是现在比较火的深度学习的起源点，下面就来说一下我自己的理解． $ $

原理

pla(Perceptron Learning Algorithm)是一种二分类得方法.根据数据是否线性可分该方法又分为navie pla 和pocket pla.其实这个东西和逻辑回归很相似.问题也很简单,假设我们有这两类点,如何用一条直线把它们分开

point
我们看一下PLA是怎么做的吧:
其实它就是拟合了如下方程:

\[ h(x)=sign(\omega_{0}+\omega_{1}x_{1}+\omega_{2}x_{2})\\ \\ signx=\left\{\begin{matrix} -1& &x<0 \\ 0& &x=0 \\ 1& &x>0 \end{matrix}\right. \]

瞬间是不是回到逻辑回归了，就是映射函数不一样而已
这里想重点说一下它的迭代公式:

\[ \omega_{t+1}\leftarrow \omega_{t}+y_{n(t)}x_{n(t)} \]

以二维平面为例(该算法可以拓展到高维空间),\(\omega\)代表分类直线(其实是与分类直线的法向量相关的向量),后面那一项也是一个向量(就是某个点以及分类标签构成的一个向量),两者相加其实就是使得分类直线朝着使得该点分类正确的方向旋转和平移.
逻辑回归中我们是求偏导得到的迭代公式.

想要知道更加详细的证明还是去看林老师的课吧
这里说一下结论：
navie pla: 一定会收敛，使数据分开
pocket pla: 无法收敛，是个NP问题，只能求得相对好的分类结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
# encoding=utf8
import numpy as np
import matplotlib.pyplot as plt
import random
class Perceptron:
    def __init__(self):
        self.datas,self.lables=self.load_data()
        self.num_samples,self.num_features=self.datas.shape
        self.w=np.ones((self.num_features,1))
    def calculate_error(self,vector):
        X=self.datas
        y=self.lables
        w=vector
        N=self.num_samples
        false_data=0
        for i in range(0,N):
            if(np.sign(np.dot(X[i,:],w))!=y[i][0]):
                false_data+=1
        return false_data
    # 数据线性可分
    def navie_pla(self):
        X=self.datas
        y=self.lables
        w=self.w
        N=self.num_samples
        while True:
            false_data=0
            for i in range(0,N):
                if(np.sign(np.dot(X[i,:],w))!=y[i][0]):
                    x=X[i,:].reshape(3,1)
                    w+=y[i][0]*x
                    false_data+=1
            if(false_data==0):
                break
        self.w=w
    # 数据有杂音,不完全线性可分
    def pocket_pla(self,max_iter):
        # TODO
        X=self.datas
        y=self.lables
        w=self.w
        N=self.num_samples
        false_data=self.calculate_error(w)
        for i in range(0,max_iter):
            rand_sort = range(N)
            rand_sort = random.sample(rand_sort,N)
            for j in rand_sort:
                if(np.sign(np.dot(X[j,:],w))!=y[j][0]):
                    x=X[j,:].reshape(3,1)
                    tmp_w=w+0.01*y[j][0]*x
                    tmp_false_data=self.calculate_error(tmp_w)
                    # print tmp_false_data
                    if(tmp_false_data<=false_data):
                        w=tmp_w
                        false_data=tmp_false_data
                        print false_data
                    break
        print false_data
        self.w=w
    def load_data(self):
        data=np.loadtxt('pla_nonlinear_data.txt')
        # data=np.loadtxt('pla_linear_data.txt')
        points=data[:,:-1]
        lables=data[:,-1:]
        # 在点中插入一列1
        points=np.insert(points,0,1,axis=1)
        return points, lables
    def plot2D(self):
        xy=self.datas[:,1:]
        lable=self.lables
        N=self.num_samples
        # 画点
        for i in xrange(N):
            if int(lable[i, 0]) == -1:
                plt.plot(xy[i, 0], xy[i, 1], 'ro')
            elif int(lable[i, 0]) == 1:
                plt.plot(xy[i, 0], xy[i, 1], 'bo')
        # 画线
        theta=self.w.reshape((3,))
        min_x = min(xy[:, 0])
        max_x = max(xy[:, 0])
        y_min_x = float(-theta[0] - theta[1] * min_x) / theta[2]
        y_max_x = float(-theta[0] - theta[1] * max_x) / theta[2]
        plt.plot([min_x, max_x], [y_min_x, y_max_x], '-g')
        # plt.axis([-6,6,-6,6])
        plt.xlabel('x'); plt.ylabel('y')
        plt.show()
if __name__ == '__main__':
    p=Perceptron()
    p.pocket_pla(1000)
    # p.navie_pla()
    p.plot2D()

还是给出图形结果吧!
navie pla:

pocket pla:

对于线性可分的数据，navie pla 完全可以分类正确，不过对于非线性可分的数据，pocket pla并没有给我们找到最优的结果(黑色的线是最好的结果)．
还有就是navie pla与\(\omega\)的初始值无关，但是pocket pla却有关，因为我把\(\omega\)初始化为０，结果没有初始为１好

数据下载:Data