统计学习方法-感知机

1.感知机模型

感知机是一种二分类的线性分类模型，是神经网络和支持向量机的基础，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值
感知机是通过划分一个超平面把不同类别的数据分开，可以理解为一条直线划分开一个二维平面中不同类型数据一样，属于线性模型，针对现实生活中很多复杂的非线形问题，单独的一个感知机是没有办法解决的，可以通过多个单层感知机相互连接传递信息构建一定规则的结构（多层感知机）就可以优化这个问题，单层感知机是线性模型，多层感知机是非线性模型。

2.感知机学习策略

2.1数据集的线性可分性

给定一个数据集
$T=(x_1,y_1),(x_2,y_2),.....,(x_N,y_N)其中x_i\in X=R^n,y_i\in Y=+1,-1,i=1,2,....,N,$

如果存在某个超平面S：wx+b=0,且能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，及对所有的
$y_i$= +1的实例 i，有w$x_i$+b>0
$y_i$= -1的实例 i，有w*$x_i$+b<0
则称数据T为线形可分数据集

2.2感知机的学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面，即需要我们去确定感知机模型参数w,b,我们需要确定一个学习策略，即定义经验损失函数，并将损失函数极小化。
损失函数的一个自然选择是误分类点的总数，但是，这样的损失函数不是参数w,b的连续可导函数，不易优化
损失函数的另外一个选择是误分类点到超平面的总距离，这是感知机所采用的。
首先写出输出空间$R^n$中任一点$x_0$到超平面S的距离：
$\frac{1}{||w||}|w\ast x_0+b|$,
这里||w||是w的$L_2$范数，典型应用在欧式距离，可用于优化正则化项，避免过拟合.
对于误分类的数据（$x_i$,$y_i$)来说：$-y_i$(w*$x_i$+b)>0
因为当
$w{x}_i+b>0,yi=-1$
$w{x}_i+b<0,yi=+1$
此时我们可以得到误分类点的$x_i$到超平面的距离：$-\frac{1}{||w||}|w\ast x_0+b|$，假定超平面S的误分类点集合为M，那么所有的误分类点到超平面S的总距离为：
$-\frac{1}{||w||}{\sum }_{x_iϵM}{y}_i|w\ast x_0+b|$
不考虑$\frac{1}{||w||}$,我们就得到感知机学习的损失函数
L(w,b)=${\sum }_{x_iϵM}{y}_i|w\ast x_0+b|$
注意：
损失函数L(w,b)是非负的
没有误分类点，损失函数值是0
误分类点越少，误分类点离超平面越近，损失函数值越小
损失函数L(w,b)是参数w,b的线性可导函数

3.感知机学习算法

原始形式：

代码实现：

import numpy as  np
def Perceptron(x,y,w,b,eta):
    m,n = x.shape
    falg = True
    while falg:
        falg = False
        for i in range(m):
            if y[i]*(w.dot(x[i])+b) <= 0:
                w = w + eta*y[i]*x[i]
                b= b + eta*y[i]
                print(w,b)
                falg = True
                break
    return w,b

if __name__ == '__main__':
    x = np.array([[3,3],
                [4,3],
                [1,1]])
    y = np.array([1,1,-1])
    m,n = x.shape
    w = np.zeros(n)
    b = 0
    eta = 1
    w,b = Perceptron(x,y,w,b,eta)

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

结果；

[3. 3.] 1
[2. 2.] 0
[1. 1.] -1
[0. 0.] -2
[3. 3.] -1
[2. 2.] -2
[1. 1.] -3

1
2
3
4
5
6
7
8

对偶形式：
对偶形式和原始形式并没有本质区别，那么它的意义在哪里呢，样本点的特征向量以内积的形式存在于感知机对偶形式的训练算法中，如果事先计算好所有的内积，也就是Gram矩阵，就可以大大地加快速度

import numpy as np
def Perceptron_dual(x,y,nn,eta):
    m,n = x.shape
    Gram = np.zeros((m,m))
    for i in range(m):
        for j in range(m):
            Gram[i][j] = x[i].dot(x[j])
    bool = True
    while bool:
        bool = False
        for i in range(m):
            data = 0
            for j in range(m):
                data = data + nn[j]*eta*y[j]*Gram[i][j]+nn[j]*eta*y[j]
            if y[i]*(data) <= 0:
                nn[i] = nn[i]+1
                bool = True
                break
    return nn

# 设置初始值
x = np.array([[3,3],[4,3],[1,1]])
y = np.array([1,1,-1])
m,n = x.shape
nn = np.zeros(m)
eta = 1 # 学习率

nn = Perceptron_dual(x, y, nn, eta)
print(nn)
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

结果：

[2. 0. 5.]
1