感知机

感知机模型

感知机模型是一种二分类的线性判别模型。根据数据特征分为正负两类，是神经网络与支持向量机的基础。

F(x) = sign(w*x +b)  w:权值，b:偏置量

F(x) = 1 (x>=0)

F(x) = -1 (x<0)

根据超平面 w*x +b=0 将数据集分为两类。

感知机学习策略

数据集的线性可分，如果存在超平面w*x +b = 0 可以使得数据集分为两类，则数据集线性可分。即对于y=1的数据集。w*x + b > 0 , 对于y=-1的数据集。w*x + b < 0

感知机的学习目标是学习一个超平面分离正负数据集的参数w和b。

损失函数：误分类的数据到超平面的距离的总和。

       (x , y)到超平面的距离为d = 1/||w|| *|w*x +b|

       ||w|| 是w 的L2范数。

对于所有 误分类点(x , y)来说

-y (w*x +b) >0

损失函数L(w , b) = -sum ( y_i *(w*x_i +b))

求取损失函数最小的模型参数w , b即感知机模型。

感知机学习算法

原始形式

采取随机梯度下降，采用不同的误分类点得到的可能模型不同。

L(w , b) = min -sum ( y_i *(w*x_i +b))

对w求梯度得 -sum(y_i * x_i)

对b求梯度得 -sum(y_i)

随机选取一个误分类点（x0 , y0），更新w , b ,a 为学习率（步长）

w <--- w + a*x0*y0

b <--- b + a*y0

算法

(1)选取初值w0，b0

(2）在训练集中选取数据(x,y)

(3）如果y*(w*x+b)≤0 。w<一w+n*y*x 。 b<一b+n*y,

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

例子1(原始形式)

其中正例x1(3,3) , x2(4,3), 负例 x3(1,1) ，取初始值w0,b0 = 0, n=1。感知机求解迭代如下：

如果y*(w*x+b)≤0  w,b更新。

wß w +y*x

bß b + 1*y,

 

迭代次数	误分类点	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	2x1 + 2x2 - 2
7	x3	(1,1)	-3	x1 +x2 -3
8	0	(1,1)	-3	x1 +x2 -3

输出感知机模型：f(x) = sign(x1+x2-3)

 

对偶形式

将w和b表示为xi和yi的线性组合形式

对于n次误分类点的变更做记录，最后根据线性关系进行计算。求解w和b值。

对于误分类点（xi,yi）逐步修改w和b ，设修改了n次，w和b的增量分别是sum(aixiyi)

和sum(aiyi) 其中ai = ni *步长

算法

(1)w<-0，b<-0

(2)在训练集中选取数据(x，y)

(3)如果y*(sum(ai*yi*xi+b))<=0

       ai<-ai + 步长

b<-b+y*步长

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

例子2（对偶形式）

其中正样本x1(3,3) , x2(4,3), 负样本 x3(1,1) ，

1 取初始值ai=0，i=1,2,3。b=0,步长=1 ,

2计算gram矩阵内积矩阵

Gram = [

x1*x1，x1*x2，x1*x3，

x2*x1，x2*x2，x2*x3

x3*x1，x3*x2，x3*x3

]=[

18,21,6

21,25,7

6,7,2

]

迭代过程

迭代次数	误分类点	a1	a2	a3	b
0	0	0	0	0	0
1	x1	1	0	0	1
2	x3	1	0	1	0
3	x3	1	0	2	-1
4	x3	1	0	3	-2
5	x1	2	0	3	-1
6	x3	2	0	4	-2
7	x3	2	0	5	-3

具体计算过程如下