感知机

感知机时用于二分类的线性模型，输入为实例的特征向量，输出为类别，取 {−1,+1}\{-1, +1\} 。相当于在特征空间中找到一个超平面将空间划分。

模型表示

希望得到一个从输入空间到输出空间的函数

f(x)=sign(w⋅x+b)f(x) = \text{sign}(w \cdot x + b)

其中

sign(z)={+1,z≥0−1,z<0\text{sign}(z) = \begin{cases} +1, & z \geq 0 \\ -1, & z < 0 \end{cases}

， ww 为权重向量， bb 为偏置。（为了简便，向量并未加粗表示）

解释： w⋅x+b=0w \cdot x + b = 0 表示超平面， ww 决定了超平面的方向， bb 决定了超平面到原点的距离。

学习策略

数据集的线性可分性

对于感知机来说，首先要保证模型是线性可分的，及对于一个数据集来说，可以将正是锂电和腐蚀锂电完全正确的划分开来。

损失函数

由于我们要最小化损失函数，因此定义的损失函数尽可能是连续可导函数。在这里可以选择误分类点到超平面的距离之和作为损失函数。

对于任意一点 x0x_0 ，其到超平面的距离为

∣w⋅x0+b∣∣∣w∣∣2\frac{|w \cdot x_0 + b|}{||w||_2}

对于误分类的点 xix_i ，有 yi(w⋅xi+b)<0y_i(w \cdot x_i + b) < 0 ，因此可以将损失函数定义为

L(w,b)=−∑xi∈Myi(w⋅xi+b)L(w, b) = - \sum_{x_i \in M} y_i (w \cdot x_i + b)

这里略去了常系数‘1/∣∣w∣∣2‘`1/||w||_2`，‘M‘`M`为误分类点的集合。

学习算法

问题重述：对于训练集

T={(x1,y1),(x2,y2),⋯ ,(xN,yN)}T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}

其中 xi∈Rn‘x_i \in R^n`，‘yi∈{−1,+1}`y_i \in \{-1, +1\} ，希望通过学习得到参数 ww 和 bb ，使得损失函数最小化：

min⁡w,bL(w,b)=−∑xi∈Myi(w⋅xi+b)\min_{w, b} L(w, b) = - \sum_{x_i \in M} y_i (w \cdot x_i + b)

采用随机梯度下降法，首先任选一个超平面，再每次选取一个误分类点使其梯度下降。

损失函数的梯度

∇wL(w,b)=−∑yixi∇bL(w,b)=−∑yi\nabla_wL(w, b) = - \sum y_ix_i\\ \nabla_bL(w, b) = - \sum y_i

每次选择一个误分类点对 w,bw,b更新，由于梯度方向是增长最快的方向，选取梯度的一个分量

wk+1=wk+λyixibk+1=bk+λyiw_{k+1} = w_{k} + \lambda y_ix_i\\ b_{k+1} = b_{k} + \lambda y_i

λ∈(0,1]\lambda \in (0, 1] 表示学习率，这样可以期待损失函数不断减小直到为零

因此感知机学习算法的原始形式：

  1. 选取 w0,b0w_0, b_0
  2. 在训练集中选择数据 (xi,yi)(x_i, y_i)
  3. 若 −yi(wk⋅xi+bk)≥0-y_i(w_k\cdot x_i + b_k) \geq 0则
wk+1=wk+λyixibk+1=bk+λyiw_{k+1} = w_k + \lambda y_ix_i\\ b_{k+1} = b_k + \lambda y_i
  1. 重复直至没有误分类点

收敛性：若线性可分，就必然收敛记 γ=min⁡yi(w⋅xi+b),R=max⁡{∥(xi,1)∥}\gamma = \min y_i(w\cdot x_i + b), R = \max \{\|(x_i, 1)\|\} ，则在训练集上的试错次数 k≤(Rγ)2k \leq \left(\frac{R}{\gamma}\right)^2

对偶形式

实际上如果 w,bw,b 的初值都取 00 ，那么可以得到二者的最终形式就是关于 xiyi,yix_iy_i, y_i 的线性形式。那么我们一开始就如此来表示我们所需要的目标参数

w=∑αixiyib=∑αiyiw = \sum \alpha_i x_iy_i\\ b = \sum \alpha_i y_i

对比原始的学习算法，我们可以将更新步骤改为

ifyi(∑j=1Nαjxj⋅xi+b)≤0αi=αi+λb=b+λyiif \quad y_i(\sum_{j=1}^N\alpha_jx_j\cdot x_i + b) \leq 0\\ \alpha_i = \alpha_i + \lambda\\ b = b+ \lambda y_i

总结

算法迭代的过程本质上是对于一个误分类点，超平面不断地作平移旋转直至将他变为正确分类的点

实例

通过平面上可二分类的两堆点来画出分割的曲线，可以调取机器学习库中的Perceptron模块

clf = Perceptron(
    max_iter=1000,
    eta0=1.0,
    random_state=42
)

clf.fit(X_train, y_train)
clf.predict(X_test)