感知机是二分类的线性模型，是神经网络和SVM的基础。输入特征 x ∈ X x∈X x∈X，输出 y = { + 1 , − 1 } y = \{+1 , -1\} y={+1,−1}
那么感知机算法可以表示为 f ( x ) = s i g n ( w ⋅ x + b ) f(x) = sign(w·x+b) f(x)=sign(w⋅x+b)，相当于一个简单的线性函数
其中 s i g n ( a ) = { + 1 , if a ≥ 0 − 1 , if a<0 sign(a)= \begin{cases} +1, & \text {if a$\geq$0} \\ -1, & \text{if a<0} \end{cases} sign(a)={+1,−1,if a≥0if a<0
数据的线性可分性：存在 w ⋅ x + b = 0 w·x+b = 0 w⋅x+b=0能将数据集中的正负样本分开。说人话就是能找到一条直线将两组不同的点分开。
在这里，感知机的数据集假设为线性可分的，即表示在一堆坐标点中，总能找到一条线将正副样本给分开，并且一般能找到多条线满足要求，如下图所示。
损失函数若选取误分类点的个数，则对于 w w w和 b b b而言不连续可导，不易优化
所以，选取误分类点到超平面S的总距离作为损失函数，即
−
1
∣
∣
w
∣
∣
∑
x
i
∈
M
y
i
(
w
⋅
x
i
+
b
)
-\frac{1}{||w||}\displaystyle\sum_{x_i∈M}y_i(w·x_i+b)
−∣∣w∣∣1xi∈M∑yi(w⋅xi+b)，最终不考虑
1
∣
∣
w
∣
∣
\frac{1}{||w||}
∣∣w∣∣1，即得到最终的损失函数：
L
(
w
,
b
)
=
−
∑
x
i
∈
M
y
i
(
w
⋅
x
i
+
b
)
L(w,b) = -\displaystyle\sum_{x_i∈M}y_i(w·x_i+b)
L(w,b)=−xi∈M∑yi(w⋅xi+b)
推导：某一点到S的距离为
−
1
∣
∣
w
∣
∣
∣
w
⋅
x
0
+
b
∣
-\frac{1}{||w||}|w·x_0+b|
−∣∣w∣∣1∣w⋅x0+b∣，而误分类数据会有
−
y
i
(
w
⋅
x
i
+
b
)
>
0
-y_i(w·x_i+b)>0
−yi(w⋅xi+b)>0，所以上上式可以转化为
−
1
∣
∣
w
∣
∣
y
i
(
w
⋅
x
i
+
b
)
-\frac{1}{||w||}y_i(w·x_i+b)
−∣∣w∣∣1yi(w⋅xi+b)，总距离：
−
1
∣
∣
w
∣
∣
∑
x
i
∈
M
y
i
(
w
⋅
x
i
+
b
)
-\frac{1}{||w||}\displaystyle\sum_{x_i∈M}y_i(w·x_i+b)
−∣∣w∣∣1xi∈M∑yi(w⋅xi+b)
L ( w , b ) L(w,b) L(w,b)非负，没有误分类点则为0
使用随机梯度下降(SGD)来优化参数，算法如下：
选取初值 w 0 w_0 w0， b 0 b_0 b0
在训练集中选取数据 ( x i , y i ) (x_i,y_i) (xi,yi)
如果 y i ( w ⋅ x i + b ) ≤ 0 y_i(w·x_i+b)\leq 0 yi(w⋅xi+b)≤0，则有：
w = w + η y i x i w = w+\eta y_ix_i w=w+ηyixi
b = b + η y i b = b + \eta y_i b=b+ηyi
转至2，直到没有误分类点
其中 η \eta η为学习率， w w w和 b b b的梯度通过对损失函数 L ( w , b ) L(w,b) L(w,b)求导而来
import numpy as np
import matplotlib.pyplot as plt
x_true = np.array([[3,3],[4,3]])
x_false = np.array([[1,1]])
y = [1]* len(x_true) + [-1] * len(x_false)
x_all = np.vstack([x_true,x_false])
w = np.array([0,0])
lr = 1
b = 0
i = 0
#循环判断每一个样本有没有误分类，有则更新参数重新开始判断
while i<len(x_all):
if y[i]*(w.dot(x_all[i].T)+b) <= 0:
w = w + lr * y[i] * x_all[i]
b = b + lr * y[i]
i = 0
print('w = {},b = {}'.format(w,b))
else:
i += 1
print('平面S为：{:.2f}x1 + {:.2f}x2 {} = 0'.format(w[0],w[1], str(b) if b < 0 else '+'+str(b)))
plot_x = [0,1,2,3,4,5]
plot_y = [-(x*w[0]+b)/w[1] for x in plot_x]
plt.figure(figsize =(10,10))
plt.scatter([x[0] for x in x_true], [x[1] for x in x_true] , c = 'blue')
plt.scatter([x[0] for x in x_false], [x[1] for x in x_false] , c = 'red')
plt.plot(plot_x , plot_y , c = 'black')
# plt.text(0.5,4.5,'Func:{:.2f}x1 + {:.2f}x2 {} = 0'.format(w[0],w[1], str(b) if b < 0 else '+'+str(b)),fontsize=15,color = "green",style = "italic")
plt.xlim(0, 5.0) #坐标轴
plt.ylim(0, 5.0)
plt.xlabel('x1',fontsize = 16)
plt.ylabel('x2',fontsize = 16)
plt.pause(0.001)
plt.show()
实现结果：
w w w和 b b b变化过程以及最终的平面S：
换一组更复杂的数据测试：
对偶形式是将原始形式中的 w w w和 b b b表示为 x i x_i xi和 y i y_i yi的线性组合，即
{ w = ∑ i = 1 N n i y i x i b = ∑ i = 1 N n i y i \begin{cases} w =\displaystyle\sum_{i = 1}^Nn_i y_ix_i \\b = \displaystyle\sum_{i=1}^Nn_i y_i \end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧w=i=1∑Nniyixib=i=1∑Nniyi
n i n_i ni值越大，表示这个样本被误分类的次数越多，就意味着这个点离我们所需要的超平面越近，左移一点或者右移一点就会误分类，对于SVM而言，这个点极有可能就是支持向量
根据原始形式， f ( x ) = s i g n ( w x + b ) = s i g n ( ∑ j = 1 N n j y j x j ⋅ x + ∑ i = 1 N n i y j ) f(x) = sign(wx+b) = sign(\displaystyle\sum_{j=1}^Nn_j y_jx_j·x+\displaystyle\sum_{i=1}^Nn_i y_j) f(x)=sign(wx+b)=sign(j=1∑Nnjyjxj⋅x+i=1∑Nniyj)
从之前的的优化 w w w和 b b b，变成了优化 n n n
误分类的判断条件也变成了 y i ( ∑ j = 1 N n j y j x j ⋅ x + ∑ i = 1 N n i y j ) < 0 y_i(\displaystyle\sum_{j=1}^Nn_j y_jx_j·x+\displaystyle\sum_{i=1}^Nn_i y_j)<0 yi(j=1∑Nnjyjxj⋅x+i=1∑Nniyj)<0
《统计学习方法》中将 n i n_i ni用 α i \alpha_i αi表示
选取初值 α \alpha α， b b b
在训练集中选取数据 ( x i , y i ) (x_i,y_i) (xi,yi)
如果 y i ( ∑ j = 1 N α j y j x j ⋅ x i + b ) ≤ 0 y_i(\displaystyle\sum_{j=1}^N\alpha_jy_jx_j·x_i+b)\leq 0 yi(j=1∑Nαjyjxj⋅xi+b)≤0，则有：
α = α + η \alpha = \alpha+\eta α=α+η
b = b + η y i b = b + \eta y_i b=b+ηyi
转至2，直到没有误分类点
在对偶形式中，样本以内积的形式计算，如果以内积矩阵形式存储，则会大大缩短计算时间，即Gram矩阵：
G
=
[
x
i
⋅
x
j
]
G = [x_i·x_j]
G=[xi⋅xj]，代码可以表示成Gram = x.dot(x.T)
import numpy as np
import matplotlib.pyplot as plt
x_true = np.array([[3, 3], [4, 3]])
x_false = np.array([[1, 1]])
x_all = np.vstack([x_true,x_false])
y = [1]*len(x_true) + [-1] * len(x_false)
n = len(x_all)
a = np.zeros(n)
b = 0
lr = 1
Gram = x_all.dot(x_all.T) #计算G
i = 0
#循环判断每一个样本有没有误分类，有则更新参数重新开始判断
while i < n:
error = 0
for j in range(n):
error += a[j] * y[j] * Gram[j,i]
if y[i] * (error + b) <= 0: #有负样本
a[i] += lr
b += lr * y[i]
print('a = {},b = {}'.format(a,b))
i = 0
else:
i += 1
w = np.zeros(2)
for j in range(n):
w += a[j] * y[j] * x_all[j]
print('平面S为：{:.2f}x1 + {:.2f}x2 {} = 0'.format(w[0],w[1], str(b) if b < 0 else '+'+str(b)))
plot_x = [0,1,2,3,4,5]
plot_y = [-(x*w[0]+b)/w[1] for x in plot_x]
plt.figure(figsize =(10,10))
plt.scatter([x[0] for x in x_true], [x[1] for x in x_true] , c = 'blue')
plt.scatter([x[0] for x in x_false], [x[1] for x in x_false] , c = 'red')
plt.plot(plot_x , plot_y , c = 'black')
plt.xlim(0, 5.0) #坐标轴
plt.ylim(0, 5.0)
plt.xlabel('x1',fontsize = 16)
plt.ylabel('x2',fontsize = 16)
plt.pause(0.001)
plt.show()
实验结果：
其中 a a a和 b b b的变化过程，以及最终的平面S：
本为初学者，难免有错误，有问题欢迎评论区指出或私信。
联系方式：1759412770@qq.com ; zn1759412770@163.com