感知机是一种线性分类模型，属于判别模型。几何解释：$w \cdot x + b = 0$可以看成是一个超平面，其中$w$是超平面的法向量，$b$是超平面的截距，这个超平面把特征空间划分为两部分。
学习策略
因为感知机是一个线性分类器，所以学习的目标是求得能将两类点分离的超平面。这需要定义一个损失函数，并且将损失函数极小化。直观来说，损失函数可以定义为误分类的点的数量，但是这样的损失函数不是参数$w$、$b$的连续可导函数，无法优化。损失函数的另一个选择是误分类点到超平面的总距离。输入空间中任意一点$x_0$到分离超平面的距离为$\frac{1}{|w|}|w \cdot x_0 + b|$，考虑到对于误分类的数据点$(x_i, y_i)$来说，有$-y_i(w \cdot x_i + b) > 0$，因此所有误分类点到超平面的总距离可以写成$-\frac{1}{|w|} \sum_{x_i \in M} y_i(w \cdot x_i + b)$，不考虑$\frac{1}{|w|}$，损失函数就可以写成
其中$M$是误分类点的集合。
学习算法
原始形式
根据损失函数分别计算参数$w$和$b$的梯度：
随机梯度下降算法：随机选取误分类点$(x_i, y_i)$，对$w$，$b$进行更新（$w$和$b$的初值都为0）：
对偶形式
从上面更新$w$和$b$的式子可以看到，最终的$w$和$b$的值取决于误分类点。因此最终的$w$和$b$可以写成如下形式：
其中$\alpha_i = n_i \eta_i$，其中$n_i$是点$i$用于更新的次数。因此求解$w$和$b$转变成了求解参数参数向量$\alpha$。初始时可以设置$\alpha$向量为0向量，b也设置为0，然后对于随机选取的点$(x_i, y_i)$，如果有$y_i(\sum_{j=1}^N \alpha_j y_j x_j \cdot x_i + b) \leq 0$，则进行以下更新：
对偶形式中，需要计算向量$x$之间的内积，因此可以提前算出来，并以矩阵的形式存储，这个矩阵也称为Gram矩阵。
代码实现
下面用python实现三维空间上的感知机算法，即输入空间是3维的，感知机方程则表示三维空间中的一个平面。代码中随机生成一个三维平面，接着随机生成平面两侧的数据点用于感知机算法的拟合，然后分别用accuracy、precision、recall来评判拟合的效果，以及用可视化的方式来展示拟合的状态。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
47class Perceptron:
def __init__(self):
pass
def fit(self, X, y, n_iterations=1000, learning_rate=1):
"""感知机训练算法的原始形式
Args:
X: 输入的特征
y: 输入的标签{-1, 1}
n_iterations: 算法迭代次数
learning_rate: 学习速率
"""
n, m = X.shape
self.w, self.b = np.zeros((3, 1)), 0
for i in tqdm(range(n_iterations)):
idx = np.random.randint(0, n)
if y[idx] * (np.vdot(self.w, X[idx].reshape(3, 1)) + self.b) <= 0:
self.w += learning_rate * y[idx] * X[idx].reshape(3, 1)
self.b += learning_rate * y[idx]
def fit_dual(self, X, y, n_iterations=1000, learning_rate=1):
"""感知机训练算法的对偶形式"""
n, m = X.shape
self.alpha, self.b = np.zeros((n, 1)), 0
self.gram = np.zeros((n, n))
# 计算Gram相关性矩阵
for i in range(0, n):
self.gram[i][i] = 1
for j in range(i + 1, n):
self.gram[i][j] = self.gram[j][i] = np.vdot(X[i].reshape(3, 1), X[j].reshape(3, 1))
for i in tqdm(range(n_iterations)):
idx = np.random.randint(0, n)
if y[idx] * (sum(self.alpha * y * self.gram[:, idx].reshape(-1, 1)) + self.b) <= 0:
self.alpha[idx][0] += learning_rate
self.b += learning_rate * y[idx]
self.w = sum(self.alpha * y * X).reshape(-1, 1)
def predict(self, X):
"""预测"""
y = (np.dot(X, self.w) + self.b).reshape(-1, 1)
n, _ = y.shape
for i in range(n):
y[i][0] = sign(y[i][0])
return y
最后程序输出的accuracy、precision、recall都可以达到1.0，说明拟合效果很好。下图展示了拟合的效果，其中黄色的平面代表用于生成随机数的平面，绿色的平面代表拟合的平面。不同类的数据点都分布于平面的两侧。
完整代码在这里。
总结
本文实现了输入空间是三维的感知机算法，实现了原始形式的学习算法和对偶形式的学习算法。对于更高维的输入，也可以采取类似的方式实现。