第二节--感知机

第二节–感知机

感知机(perceptron)是二类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别,取+1和-1二值.感知机对应于输入空间(特征空间)中将实例划分为正负两类的分离超平面,属于判别模型.感知机学习旨在求出将训练数据进行线性划分的分离超平面,为此,导入基于误分类的损失函数,利用梯度下降法对损失函数进行极小化,求得感知机模型.感知机学习算法具有简单而易于实现的优点,分为原始形式和对偶形式.感知机预测是用学习得到的感知机模型对新的输入实例进行分类

一.感知机模型

假设输入空间(特征空间)是,输出空间是,输入表示实例的特征变量,对应于输入空间(特征空间)的点;输出表示实例的类别.由输入空间到输出空间的如下函数：

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

感知机是一种线性分类模型,属于判别模型.感知机模型的假设空间时定义在特征空间(linear classification model)或线性分类器(linear classifier),即函数集合

感知机有如下几何解释,线性方程：

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

from IPython.display import Image
Image(filename="./data/2_1.png",width=500)

感知机学习,由训练数据集(实例的特征向量机类别)：

其中,,求得感知机模型.即求得模型参数w,b.感知机预测,通过学习得到的感知机模型.对于新的输入实例给出其对应的输出示例

二.感知机学习策略

1.数据集的线性可分性

给定一个数据集：

其中,如果存在某个超平面S：

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧,即对所有 $y_{i}=+1$ 的实例i,有 $w cdot x_{i}+b>0$ ,多所有 $y_{i}=-1$ 的实例i,有 $w cdot x_{i}+b<0$ ,则称数据集T为线性可分数据集(linearly separable data set);否则,称数据集T线性不可分

2.感知机学习策略

假设训练数据集是线性可分的,感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面.为了找出这样的超平面.即确定感知机模型参数w,b,需要确定一个学习策略.即定义损失函数并将损失函数最小化

损失函数的一个目标选择是误分类点的总数.但是这样的损失函数不是参数w,b的连续可导函数.损失函数的另一个选择是误分类点到超平面S的总距离,这是感知机所采用的.为此首先输入空间中任一点到超平面S的距离

对于误分类的数据来说：

当时,.而当时,.因此误分类点到超平面S的距离是：

假设超平面S的误分类点集合为M,那么所有误分类点到超平面S的总距离为：

不考虑,就得到感知机学习的损失函数

给定训练数据集：

其中,感知机学习的损失函数定义为：

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

显然,损失函数L(w, b)是非负的,如果没有误分类点,损失函数值是0.而且误分类点越少,误分类点离超平面越近,损失函数值就越小.一个特定的样本点的损失函数,在误分类时是参数w,b的线性函数,在正确分类时是0.因此给定训练数据集T,损失函数L(w, b)是w,b的连续可导函数

三.感知机学习算法

感知机学习问题转化为求解损失函数的最优化问题,最优化的方法是随机梯度下降法.具体方法包括原始形式和对偶形式,并证明在训练数据线性可分条件下感知机学习算法的收敛性

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

感知机学习算法是对以下最优化问题的算法,给定一个训练数据集：

其中,,求参数w,b使其为以下损失函数极小化问题的解：

其中M为误分类点的集合

感知机学习算法是误分类驱动的,具体采用随机梯度下降法(stochastic gradient descent).首先任意选取一个超平面,然后用梯度下降法不断地极小化目标函数.极小化过程不是一次使M中所有误分类点的梯度下降,而是一次随机选取一个2误分类点使其梯度下降

假设误分类集合M是固定的,那么损失函数的梯度由：

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

式中是步长,在统计学习中又称为学习率(learning rate).通过迭代可以期待损失函数不断减小,直到为0.综上所述,得到如下算法：

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

输入：训练数据集,其中, 学习率

输出：w,b;感知机模型

选取初值
在训练集中选取数据
如果

转至2,直至训练集中没有误分类点

这种学习算法直观上有如下解释：当一个实例点被误分类,即位于分离超平面的错误一侧时,则调整w,b的值,使分离超平面向该误分类点的一侧移动,以减少该误分类点与超平面间的距离.直至超平面越过该误分类点使其被正确分类

实例1：如下数据集,其正实例点是.试用感知机学习算法的原始形式求感知机模型.这里

from IPython.display import Image
Image(filename="./data/3_1.png",width=500)

解：构建最优化问题

求解w,b,

取初值
对,未能被正确分类,更新w,b

得到线性模型：
对,显然被正确分类,不修改w,b;对被误分类,更新w,b

如此继续下去,直到：

对所有数据点,没有误分类点,损失函数达到极小

分离超平面为：

感知机模型为：

Image(filename="./data/2_3.png")

Image(filename="./data/2_4.png")

迭代次数	误分类点	w	b	w.x+b
0	0	0	0	0
1	x1	(3,3)	1	3x1+3x2+1
2	x3	(2,2)	0	2x1+2x2
3	x3	(1,1)	-1	x1+x2-1
4	x3	(0,0)	-2	-2
5	x1	(3,3)	-1	3x1+3x2-1
6	x3	(2,2)	-2	3x1+3x2-2
7	x3	(1,1)	-3	x1+x2-2
8	x1	(1,1)	-3	x1+x2-3

这是在计算中误分类点先后取得到的分离超平面和感知机模型.如果在计算中误分类点依次取,那么得到的分离超平面是$2

可见,感知机学习算法由于采用不同的初值或选取不同的误分类点,解可以不同

2.算法的收敛性

对于线性可分数据集感知学习算法原始形式收敛,即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型

误分类的次数k是有上界的,经过有限次搜索可以找到将训练集数据完全正确分开的分离超平面

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

对偶形式的基本想法是,将w和b表示为实例x_和标记y_的线性组合的形式.通过求解其系数而求得w和b,不失一般性.在原始形式的算法中可假设初始值均为0,对误分类点通过：

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

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

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

输入：线性可分的数据集,其中学习率

输出：a,b;感知机模型

其中

在训练集中选取数据
如果

转置2,直到没有误分类数据

对偶形式中训练实例仅以内积的形式出现,为了方便,可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储,这个存储就是所谓的Gram矩阵(Gram matrix)

实例2：正样本点是负样本点是,试用感知机学习算法对偶形式求感知机模型

解：

取
计算Gram矩阵
误分条件

参数更新
迭代,过程如下图
分离超平面：

感知机模型：

与原始形式一样,感知机学习算法的对偶形式迭代是收敛的,存在多个解

四.感知机实现

当实例点被误分类,即位于分离超平面的错误侧,则调整w,b的值,使分离超平面向该无分类点的一侧移动,直至误分类点被正确分类

拿出iris数据集中两个分类的数据和[speal length,speal width]作为特征

1.自定义感知机

%matplotlib inline
import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt

# load iris
iris=load_iris()
df=pd.DataFrame(iris.data,columns=iris.feature_names)
df["label"]=iris.target

df.columns=["sepal length","sepal width","petal length","petal width","label"]
df.label.value_counts()

2    50
1    50
0    50
Name: label, dtype: int64

plt.scatter(df[:50]["sepal length"],df[:50]["sepal width"],label="0")
plt.scatter(df[50:100]["sepal length"],df[50:100]["sepal width"],label="1")
plt.xlabel("sepal length")
plt.ylabel("sepal width")
plt.legend()

<matplotlib.legend.Legend at 0x25ffdd3b6a0>

data=np.array(df.iloc[:100,[0,1,-1]])

X,y=data[:,:-1],data[:,-1]

y=np.array([1 if i==1 else -1 for i in y])

# 数据线性可分,二分类数据
# 此处为一元一次线性方程
class Model(object):
    def __init__(self):
        self.w=np.ones(len(data[0])-1,dtype=np.float32)
        self.b=0
        self.l_rate=0.1
        
    def sign(self,x,w,b):
        y=np.dot(x,w)+b
        return y
    
    # 随机梯度下降法
    def fit(self,X_train,y_train):
        is_wrong=False
        while not is_wrong:
            wrong_count=0
            for d in range(len(X_train)):
                X=X_train[d]
                y=y_train[d]
                if y*self.sign(X,self.w,self.b)<=0:
                    self.w=self.w+self.l_rate*np.dot(y,X)
                    self.b=self.b+self.l_rate*y
                    wrong_count+=1
            if wrong_count==0:
                is_wrong=True
        return "Perceptron Model!"
    
    def score(self):
        pass

perceptron=Model()
perceptron.fit(X,y)

'Perceptron Model!'

x_points=np.linspace(4,7,10)
y_=-(perceptron.w[0]*x_points+perceptron.b)/perceptron.w[1]
plt.plot(x_points,y_)

plt.plot(data[:50,0],data[:50,1],"bo",color="blue",label="o")
plt.plot(data[50:100,0],data[50:100,1],"bo",color="orange",label="l")
plt.xlabel("sepal length")
plt.ylabel("sepal width")
plt.legend()

<matplotlib.legend.Legend at 0x25fff517fd0>

2.sklearn Perceptron

from sklearn.linear_model import Perceptron

clf=Perceptron(fit_intercept=False,max_iter=1000,shuffle=False)
clf.fit(X,y)

E:Anacondaenvsmytensorflowlibsite-packagessklearnlinear_modelstochastic_gradient.py:183: FutureWarning: max_iter and tol parameters have been added in Perceptron in 0.19. If max_iter is set but tol is left unset, the default value for tol in 0.19 and 0.20 will be None (which is equivalent to -infinity, so it has no effect) but will change in 0.21 to 1e-3. Specify tol to silence this warning.
  FutureWarning)





Perceptron(alpha=0.0001, class_weight=None, early_stopping=False, eta0=1.0,
      fit_intercept=False, max_iter=1000, n_iter=None, n_iter_no_change=5,
      n_jobs=None, penalty=None, random_state=0, shuffle=False, tol=None,
      validation_fraction=0.1, verbose=0, warm_start=False)

# weight assigned to the features
print(clf.coef_)

[[  74.6 -127.2]]

print(clf.intercept_)

[0.]

x_ponits = np.arange(4, 8)
y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)

plt.plot(data[:50, 0], data[:50, 1], 'bo', color='blue', label='0')
plt.plot(data[50:100, 0], data[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

<matplotlib.legend.Legend at 0x25fff8b8a90>