1. 感知机原理（Perceptron）
2. 感知机(Perceptron)基本形式和对偶形式实现
3. 支持向量机（SVM）拉格朗日对偶性（KKT）
4. 支持向量机（SVM）原理
5. 支持向量机（SVM）软间隔
6. 支持向量机（SVM）核函数
1. 前言
今天终于能把感知机的实现补上了，感知机的原理在1. 感知机原理（Perceptron）中已经详尽的介绍，今天就是对感知机的两种实现方式，进行讲解。
2. 感知机实现
2.1 原始形式算法
假设读者们已经了解了感知机的原始形式的原理（不熟悉的请看1. 感知机原理（Perceptron）原始形式），下面是原始形式的步骤，方便对照后面的代码。
原始形式的步骤：
输入：训练数据集(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)})，(y_iin{{-1,+1}})，学习率(eta(0<eta<1))
输出：(w,b)；感知机模型(f(x)=sign(wcdot {x}+b))
- 赋初值 (w_0,b_0)
- 选取数据点((x_i,y_i))
- 判断该数据点是否为当前模型的误分类点，即判断若(y_i(wcdot {x_i}+b)<=0)则更新
- 转到2，直到训练集中没有误分类点
主要实现代码GitHub：
def fit(self, X, y):
# 初始化参数w，b
self.w = np.zeros(X.shape[1])
self.b = 0
# 记录所有error
self.errors_ = []
for _ in range(self.n_iter):
errors = 0
for xi, yi in zip(X, y):
update = self.eta * (yi - self.predict(xi))
self.w += update * xi
self.b += update
errors += int(update != 0.0)
if errors == 0:
break
self.errors_.append(errors)
return self
2.2 对偶形式算法
假设读者们已经了解了感知机的对偶形式的原理（不熟悉的请看1. 感知机原理（Perceptron）对偶形式），下面是对偶形式的步骤，方便对照后面的代码。
对偶形式的步骤：
由于(w,b)的梯度更新公式：
我们的(w,b)经过了(n)次修改后的，参数可以变化为下公式，其中(alpha = ny)：
这样我们就得出了感知机的对偶算法。
输入：训练数据集(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)})，(y_iin{{-1,+1}})，学习率(eta(0<eta<1))
输出：(alpha,b)；感知机模型(f(x)=sign(sum_{j=1}^nalpha_jy_jx_jcdot {x}+b))
其中(alpha=(alpha_1,alpha_2,...,alpha_n)^T)
- 赋初值 (alpha_0,b_0)
- 选取数据点((x_i,y_i))
- 判断该数据点是否为当前模型的误分类点，即判断若(y_i(sum_{j=1}^nalpha_jy_jx_jcdot {x_i}+b)<=0)则更新
- 转到2，直到训练集中没有误分类点
为了减少计算量，我们可以预先计算式中的内积，得到Gram矩阵
主要实现代码GitHub：
def fit(self, X, y):
"""
对偶形态的感知机
由于对偶形式中训练实例仅以内积的形式出现
因此，若事先求出Gram Matrix，能大大减少计算量
"""
# 读取数据集中含有的样本数,特征向量数
n_samples, n_features = X.shape
self.alpha, self.b = [0] * n_samples, 0
self.w = np.zeros(n_features)
# 计算Gram_Matrix
self.calculate_g_matrix(X)
i = 0
while i < n_samples:
if self.judge(X, y, i) <= 0:
self.alpha[i] += self.eta
self.b += self.eta * y[i]
i = 0
else:
i += 1
for j in range(n_samples):
self.w += self.alpha[j] * X[j] * y[j]
return self
3. 小结
感知机算法是一个简单易懂的算法，自己编程实现也不太难。前面提到它是很多算法的鼻祖，比如支持向量机算法，神经网络与深度学习。因此虽然它现在已经不是一个在实践中广泛运用的算法，还是值得好好的去研究一下。感知机算法对偶形式为什么在实际运用中比原始形式快，也值得好好去体会。