基础 · 03

感知机

最简单的线性分类器——一条线把两类分开。

8 min read

感知机模型

感知机是二分类的线性模型。输入 x∈Rnx \in \mathbb{R}^n，输出 y∈{+1,−1}y \in \{+1, -1\}：

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

几何上，w⋅x+b=0w \cdot x + b = 0 定义了特征空间中的一个超平面（2D 是直线，3D 是平面）。这个超平面把空间分成两半——一半判为 +1+1，另一半判为 −1-1。

ww 是超平面的法向量，决定朝向；bb 是截距，决定平移。

学习策略

前提：训练集线性可分——存在某个超平面能把两类完全分开。

损失函数的设计思路：不能用误分类点的个数（不可导），而用误分类点到超平面的函数距离之和：

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

其中 MM 是当前误分类点的集合。当 xix_i 被误分类时，yi(w⋅xi+b)<0y_i(w \cdot x_i + b) < 0，取负号后为正。所有点分类正确时 L=0L = 0。

学习算法

用随机梯度下降（SGD）。每次随机选一个误分类点 (xi,yi)(x_i, y_i) 更新：

w←w+η yi xiw \leftarrow w + \eta \, y_i \, x_i b←b+η yib \leftarrow b + \eta \, y_i

直觉：如果一个正例被判为负（在超平面错误一侧），把 ww 往 xix_i 方向拉一拉，超平面就转过来了。

迭代 0
w = [0.00, 0.00]b = 0.00
每步选一个误分类点（黄色虚线圈），按 w ← w + η·y·x, b ← b + η·y 更新。紫色线是决策边界 w·x + b = 0。

算法流程：

  1. 初始化 w=0,b=0w = 0, b = 0
  2. 在训练集中找一个误分类点
  3. 按上述公式更新
  4. 重复直到没有误分类点

收敛性

Novikoff 定理：若训练集线性可分，感知机算法在有限步内收敛。

设最优分离超平面的几何间隔为 γ\gamma，数据半径为 R=max⁡i∥xi∥R = \max_i \|x_i\|，则：

迭代次数≤(Rγ)2\text{迭代次数} \leq \left(\frac{R}{\gamma}\right)^2

关键含义：间隔越大收敛越快。这也是 SVM 追求"最大间隔"的理论铺垫。

注意：算法依赖初值和遍历顺序，解不唯一。

对偶形式

设 ww 和 bb 用训练样本的累积更新次数表示：

w=∑i=1Nαi yi xi,b=∑i=1Nαi yiw = \sum_{i=1}^N \alpha_i \, y_i \, x_i, \quad b = \sum_{i=1}^N \alpha_i \, y_i

其中 αi=niη\alpha_i = n_i \eta，nin_i 是第 ii 个样本被用来更新的次数。

判别式变为：

f(x)=sign ⁣(∑i=1Nαi yi (xi⋅x)+b)f(x) = \text{sign}\!\left(\sum_{i=1}^N \alpha_i \, y_i \, (x_i \cdot x) + b\right)

训练只需要 Gram 矩阵 Gij=xi⋅xjG_{ij} = x_i \cdot x_j，不需要显式的 ww。这是核方法的起点——把内积 xi⋅xjx_i \cdot x_j 换成核函数 K(xi,xj)K(x_i, x_j) 就能处理非线性。