感知机
感知机模型
感知机模型是一种二分类的线性判别模型。根据数据特征分为正负两类，是神经网络与支持向量机的基础。
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 ( yi *(w*xi +b))
求取损失函数最小的模型参数w , b即感知机模型。
感知机学习算法
原始形式
采取随机梯度下降，采用不同的误分类点得到的可能模型不同。
L(w , b) = min -sum ( yi *(w*xi +b))
对w求梯度得 -sum(yi * xi)
对b求梯度得 -sum(yi)
随机选取一个误分类点（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 |
具体计算过程如下
