Skip to content

感知机

1 模型

感知机是二分类模型，模型对应分离超平面 \(w \cdot x + b=0\) $$ f(x)=sign(w \cdot x + b) $$

2 策略

2.1 极小化损失函数

损失函数为： $$ L(w,b)=-\underset{x_i \in M}{\Sigma}y_i(w \cdot x_i + b) $$ 求 w 和 b，使其为损失函数极小化问题的解： $$ \underset{w,b}{min}L(w,b)=-\underset{x_i\in M}{\Sigma}y_i(w \cdot x_i+b) $$

2.2 随机梯度下降法

\[ min f(x), x \in \Omega \\[5pt] \nabla_w L(w,b) = -\underset{x_i \in M}{\Sigma} y_i x_i, \nabla_b L(w,b)=-\underset{x_i \in M}{\Sigma}y_i \\[5pt] x_{t+1} = x_t - y\cdot \nabla f(x) |_{x=x_t} \]
  • 随机选取分类点 \((x_i, y_i)\)
  • 如果 \(y_i(w_k x_i + b_k) \le 0\)，\(w \leftarrow w + \eta y_i x_i\)，\(b \leftarrow b+ \eta y_i\)，其中 \(0 \lt \eta \le 1\) 为步长
  • 返回第二步继续循环，直到训练集中没有误分类的点

3 算法

3.1 感知机的原始形式

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

输入：线性可分的训练数据集 \(T={(x_1, y_1),(x_2,y_2),...,(x_N,y_N)}\)，其中 \(x_i \in \mathcal{X} = \mathbb{R}^n\)，\(y_i \in \mathcal{Y} = \{-1, +1\}\)，\(i=1,2,...N\)；学习率 \(\eta (0 \lt \eta \le 1)\)；

输出：\(w,b\)；感知机模型 \(f(x)=sign(w \cdot x + b)\)。

  1. 选取初值 \(w_0, b_0\)；

  2. 在训练集中选取数据 \((x_i,y_i)\)；

  3. 如果 \(y_i(w_k x_i + b_k) \le 0\)， $$ w \leftarrow w + \eta y_i x_i \\[5pt] b \leftarrow b+ \eta y_i $$

  4. 转至 2 ，直至训练集中没有误分类点.

3.2 Novikoff 定理

设训练数据集 \(T={(x_1, y_1),(x_2,y_2),...,(x_N,y_N)}\) 是线性可分的，其中\(x_i \in \mathcal{X} = \mathbb{R}^n\)，\(y_i \in \mathcal{Y} = \{-1, +1\}\)，\(i=1,2,...N\)，则

  1. 存在满足条件 \(||\hat{w}_{opt}||=1\) 的超平面 \(\hat{w}_{opt} \cdot \hat{x} = w_{opt} \cdot x + b_{opt} = 0\) 将训练数据集完全正确分开；且存在 \(\gamma \gt 0\)，对所有的 \(i = 1, 2, ... ,N\)

    \[ y_i( \hat{w}_{opt} \cdot \hat{x})=y_i (w_{opt} \cdot x_i+b_{opt}) \ge \gamma \]

  2. 令 \(R = \underset{1 \le i \le N}{max} || \hat{x}_i ||\)，则感知机算法在训练数据集上的误分类次数 k 满足不等式 $$ k \le \left(\frac{R}{\gamma} \right)^2 $$

3.3 感知机的对偶形式

感知机学习算法的对偶形式

输入：线性可分的训练数据集 \(T={(x_1, y_1),(x_2,y_2),...,(x_N,y_N)}\)，其中 \(x_i \in \mathcal{X} = \mathbb{R}^n\)，\(y_i \in \mathcal{Y} = \{-1, +1\}\)，\(i=1,2,...N\)；学习率 \(\eta (0 \lt \eta \le 1)\)；

输出：\(\alpha, b\)；感知机模型 \(f(x) = sign \left(\underset{j=1}{\overset{N}{\Sigma}}\alpha_jy_jx_j\cdot x+b \right)\)，其中 \(\alpha = (\alpha_1, \alpha_2,...,\alpha_N)^T\)

  1. \(\alpha \leftarrow 0, b\leftarrow 0\)；

  2. 在训练集中选取数据 \((x_i,y_i)\)；

  3. 如果 \(y_i\left(\underset{j=1}{\overset{N}{\Sigma}}\alpha_jy_jx_j\cdot x+b \right) \le 0\)， $$ \alpha \leftarrow \alpha + \eta \ b \leftarrow b+ \eta y_i $$

  4. 转至 2 直到没有误分类数据

Gram 矩阵：预先将训练集中实例间的内积计算出来并以矩阵的形式存储 $$ \bold G = [x_i \cdot x_j]_{N\times N} $$