感知机

发表于 | 更新于: | 分类于 | | 阅读量: 次

感知机是二分类的线性分类模型。

  • 模型：感知机对应于将输入空间(特征空间)中的实例划分为正负两类的分离超平面，属于判别模型。

  • 策略：基于误分类的损失函数

  • 算法：利用梯度下降法对损失函数进行极小化。

感知机学习算法分为原始形式和对偶形式。

感知机于1957年Rosenblatt提出，是神经网络与支持向量机的基础。

本章首先介绍感知机模型；然后叙述感知机的学习策略，特别是损失函数；最后介绍感知机学习算法，包括原始形式和对偶形式，并证明算法的收敛性。

2.1感知机模型

定义2.1(感知机)：假设输入空间(特征空间)是，输出空间是。输入表示实例的特征向量，对应于输入空间(特征空间)的点；输出表示实例的类别。由输入空间到输出空间的如下函数：

称为感知机。其中，w和b为感知机模型参数，叫做权值(weight)或权值向量(weight vector)，叫做偏置(bias),w.x表示w和x的内积，sign是符号函数，即：

感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合{f|f(x)=w.x+b}。

2.1.1感知机的几何意义

线性方程

对应于特征空间中的一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两个部分。位于两个部分的点(特征向量)分别被分为正、负两类。因此，超平面S称为分离超平面。

ch02-1

2.2感知机学习策略

2.2.1数据集的线性可分性

定义2.2(数据集的线性可分性)：给定一个数据集

其中，,，i=1,2,…,N，如果存在某个超平面S：

能够将数据集的正实例点和负实例点完全正确的划分到超平面的两侧，即对所有的实例i，有，对所有的实例i，有。则称数据集T为线性可分数据集；否则，称数据集T线性不可分。

2.2.2感知机学习策略

为了找出感知机模型对应的超平面，需要确定一个学习策略，即定义(经验)损失函数并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数w，b的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。

首先，写出输入空间中任一点到超平面S的距离：

这里，是w的L2范数。

其次，对于误分类的数据来说，

成立。因为当时，，而当时，。因此，误分类点到超平面S的距离是:

这样，假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为:

不考虑$\frac{1}{|w|}$，那就得到感知机学习的损失函数。

给定训练数据集

其中，，，i=1,2,…,N。感知机sign(w.x+b)学习的损失函数定义为:

其中M为误分类的集合。这个损失函数就是感知机学习的经验风险系数。

显然，损失函数L(w,b)是非负的。如果没有误分类点，损失函数值是0。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。

一个特定的样本点的损失函数：在误分类时时参数w，b的线性函数，在正确分类时时0。因此，给定训练数据集T，损失函数L(w,b)是w，b的连续可导函数。

感知机学习的策略是在假设空间中选取使损失函数式(2.4)最小的模型参数w,b,即感知机模型。

2.3感知机学习算法

最优化的方法是随机梯度下降法。本节叙述感知机学习的具体算法，包括原始形式和对偶形式，并证明在训练数据线性可分条件下感知机学习算法的收敛性。

2.3.1感知机学习算法的原始形式

给定一个训练数据集

其中，，，i=1,2,…,N。求参数w，b，使其为一下损失函数极小化问题的解：

其中M为误分类点的集合。

感知机学习算法是误分类驱动的。具体采用随机梯度下降法：

首先，任意选取一个超平面，然后用梯度下降法不断极小化目标函数(2.5)。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合M是固定的，那么损失函数L(w,b)的梯度由：

给出。

随机选取一个误分类点，对w，b进行更新:

式中是步长，也称为学习率(learning rate)。通过迭代可以期待损失函数L(w,b)不断减小，直到为0.

综上所述，得到如下算法：

算法2.1(感知机学习算法的原始形式)

输入:训练数据集，其中，，i=1,2,…,N。学习率;

输出:w,b;感知机模型sign(w.x+b)

  1. 选取初值w0，b0

  2. 在训练集中随机选取选取数据

  3. 如果,注意：这里条件包含了等于0的情况

  4. 转置2，直至训练集中没有误分类点。

以上学习算法直观上有如下解释：

当一个实例点被误分类，即位于分离超平面的错误一面时，则调整w，b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

如下图所示:xi为误分类点，S为原分离超平面，w为S的法向量，S’为使用xi更新后的分离超平面，w’=w+yixi为S‘的法向量。从图中可以很直观的看到xi离S’的距离更近了。

ch02-2

注意：感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。（解不唯一）

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
class perceptron(object):
    '''实现感知机的原始形式,使用随机梯度下降算法进行求解.'''
    def __init__(self,eta=0.001,n_iter=5000):
        self.eta = eta #学习速率
        self.n_iter=n_iter #最大迭代次数

    def fit(self, X,y):
        '''输入特征以及标签向量'''
        self.errors_ = []
        m,n = X.shape
        self._W = np.zeros(n+1) #初始化为0
        dataset_size = m
        #随机选取一个被错误分类的样本点
        for i in range(self.n_iter):
            errors = 0
            for xi,label in zip(X,y):
                self._error = label*(np.dot(xi,self._W[1:])+self._W[0]) #距离
                if self._error <= 0:
                    #误分类样本的距离
                    update = self.eta*label #b的更新量
                    self._W[1:] += update*xi #w的更新量
                    self._W[0] += update
                    print self._W
                    errors += 1
            self.errors_.append(errors)
            print("误分类的样本数为:%d" % (errors))  

    def predict(self,x):
        return np.where((np.dot(x,self._W[1:])+self._W[0])>=0.0,1,-1)

2.3.2算法的收敛性

令,。这样，。显然，。

定理2.1(Novikoff) 假设训练数据集是线性可分的，其中，，i=1,2,…,N。则

  1. 存在满足条件=1的超平面使得将训练数据集完全正确分开；且存在$\gamma>0$,对所有i=1,2,…,N(被正确分类的样本点)：

  2. 令，则感知机算法2.1在训练数据集上的误分类次数k满足不等式：

证明：

  1. 由于训练数据集是线性可分的，按照定义2.2，存在超平面可将训练数据集完全正确分开，取此超平面为，使=1。由于对有限的i=1,2,…,N，均有

    所以存在：

    使。

  2. 感知机算法从开始，如果实例被误分类，则更新权重。令是第k个误分类实例之前的扩充权重向量，即。

    则第k个误分类实例的条件是:

    若是被误分类的数据，则w和b的更新是:

即：

下面推导两个不等式：

1.

​ 由式(2.11)及式(2.8)得：

​ 由此递推即得不等式(2.12)：

2.

​ 由式(2.11)及式(2.10)得

​ 结合不等式(2.12)及式(2.13)即得:

​ 于是：

定理证明，误分类的次数k是有上界的。经过有限次搜索(搜索次数由误分类次数决定)可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。

当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

2.3.3感知机学习算法的对偶形式

对偶形式的基本想法是：将w和b表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得w和b。

不失一般性，在算法2.1中，令w0,b0初始化为0。对误分类点通过：

逐步修改w，b，设修改n次，则w，b关于的增量分别是和，这里。这样，从学习过程不难看出，最后学习到的w,b可以分别表示为:

这里,i=1,2,…,N，当时，表示第i个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类，换句话来说，这样的实例对学习结果影响最大。

算法2.2(感知机学习算法的对偶形式)

输入：线性可分的数据集，其中，，i=1,2,…,N，学习率；

输出：,b;感知机模型.其中。

  2. 在训练集中选取数据

  3. 如果

  4. 转至2直到没有误分类数据。

对偶形式中训练实例仅以内积的形式出现。

为了方便，预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵：

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
class myperceptron():
     """Perceptron Classifie 应用在二分类上.此代码实现了感知器算法的对偶形式"""
     def __init__(self, eta=0.01, n_iter=10):
         '''
         eta:学习速率
         n_iter:最大迭代次数
         '''
         self.eta = eta
         self.n_iter = n_iter


     def fit(self, X, y):
         self.alpha = np.zeros(X.shape[0]) #将权重初始化为0或一个极小的随机数
         self.b = 0
         self.errors_ = []
         self.train_X = X
         self.train_y = y
         #迭代所有的训练样本
         for _ in range(self.n_iter):
             errors = 0
             for i, (xi,target) in enumerate(zip(X,y)):
                 flag = ((self.alpha*y).T.dot(X).dot(xi)+self.b)*target
                 if flag > 0:
                    continue
                 self.alpha[i] += self.eta #更新所有的alpha向量
                 self.b += self.eta*target
                 #print self.alpha,self.b #输出信息，对照书中的例子来验证算法
                 errors += 1 #表示xi样本被错误分类了
             self.errors_.append(errors)
         return self

     def net_input(self, X):
         '''Calculate net input'''
         #return np.dot(X, self.w_[1:]) + self.w_[0]
         return X.dot((self.alpha*self.train_y).T.dot(self.train_X))+self.b

     def predict(self, X):
         return np.where(self.net_input(X)>=0.0, 1, -1)

2.4 扩展(核感知器)

核感知器可用于求解数据集为非线性可分的情况。核感知器由感知器的对偶形式延伸而来，决策函数表示为:

其中，X’为新实例(向量)，K为核函数,函数相当于输入空间到特征空间的映射，此处的特征空间与输入空间是不等价的，它通常比输入空间具有更高的维度。

上述决策函数的形式演变推导:

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
import numpy as np
from numpy import linalg

def linear_kernel(x1,x2):
    #相当于没有核函数(李航书中的普通对偶形式)
    return np.dot(x1,x2)

def polynomial_kernel(x1,x2,p=3):
    #多项式核
    return (1+np.dot(x1,x2))**p

def gaussian_kernel(x1,x2,sigma=5.0):
    #高斯核
    return np.exp(-linalg.norm(x1-x2)**2/(2*(sigma**2)))

class KernelPerceptron(object):
    def __init__(self, eta=1.0, n_iter=1, kernel=linear_kernel):
        self.kernel = kernel
        self.eta = eta
        self.n_iter = n_iter

    def fit(self, X, y):
        n_samples, n_features = X.shape
        self.alpha = np.zeros(n_samples, dtype=np.float64)
        self.b = 0
        #Gram Matrix
        K = np.zeros((n_samples, n_samples))
        for i in range(n_samples):
            for j in range(n_samples):
                K[i,j] = self.kernel(X[i],X[j])

        for t in range(self.n_iter):
            for i in range(n_samples):
                if np.sign(np.sum(K[:,i]*self.alpha*y)+self.b)!=y[i]: #这里的判断条件跟前面的对偶形式的判断条件不一样
                    self.alpha[i] += self.eta
                    self.b += self.eta*y[i]
                    print(self.alpha,self.b)

        #support vectors
        sv = self.alpha>1e-5
        ind = np.arange(len(self.alpha))[sv]
        self.alpha = self.alpha[ind]
        self.sv = X[ind]
        self.sv_y = y[ind]
        print("%d support vectors out of %d points" % (len(self.alpha),n_samples))

    def project(self, X):
        y_predict = np.zeros(len(X))
        for i in range(len(X)):
            s = 0
            for a, sv_y, sv in zip(self.alpha, self.sv_y, self.sv):
                s+= a*sv_y*self.kernel(X[i],sv)
            y_predict[i] = s
        return y_predict

    def predict(self, X):
        X = np.atleast_2d(X)
        n_samples,n_features = X.shape
        return np.sign(self.project(X))

更多关于核函数的知识在SVM算法中会涉及