感知机

感知机

感知机是二分类的线性分类模型。输入是实例的特征向量，输出为实例的类别。

感知机对应于输入空间（特征向量）中将实例划分为正负两类的分离超平面，属于判别模型。

感知机学习旨在求出将训练数据进行线性划分的分离超平面。为此：

• 导入基于误分类的损失函数

• 利用梯度下降法对损失函数进行极小化

• 求得感知机模型

感知机模型

由输入空间到输出空间的如下函数

$$f(x) = sign(w\cdot x + b)$$

称为感知机。$w,b$ 为感知机模型参数，$w\in \R^n$ 叫作权值（weight）或权向量（weight vector），$b \in \R$ 叫作偏置（bias）。$\operatorname*{sign} $ 是符号函数，即

$$\operatorname*{sign} (x) = \begin{equation} \left\{ \begin{aligned} +1,\hspace{2em} x \geqslant0 \\ -1, \hspace{2em} x < 0 \\ \end{aligned} \right. \end{equation}$$

感知机是一种线性分类模型，属于判别模型。

感知机学习策略

思路

• 感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面

• 为了找出这样的超平面，即确定感知机参数 $w,b$

• 需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化

损失函数的选择

• 一个自然选择是误分类点的总数，但是这样的损失函数不是参数 $w,b$ 的连续可导函数，不易优化

• 另一个选择是误分类点到超平面 $S$ 的总距离

损失函数

• 输入空间 $\R^n$ 中任一点 $x_0$ 到超平面 $S$ 的距离：

  $$\frac{1}{||w||}|w\cdot x_0 +b| \hspace{3em} ||w|| 是w的L_2范数$$
• 对于误分类数据样本 $(x_i,y_i)$ 来说

• $$-y_i(w\cdot x_i + b) > 0 \hspace{2em} 成立$$
• 因此，误分类点 $x_i$ 到超平面 $S$ 的距离是

  $$-\frac{1}{||w||}y_i(w\cdot x+b)$$
• 假设超平面 $S$ 的误分类点集合为 $M$ ，那么所有误分类点到超平面 $S$ 的总距离为

  $$-\frac{1}{||w||} \sum\limits_{x_i \in M} y_i(w\cdot x_i+b)$$
• 不考虑 $\frac{1}{||w||}$，就得到感知机学习的损失函数。感知机 $\operatorname*{sign}(w\cdot x+b)$ 学习的损失函数定义为

• $$L(w,b) = - \sum\limits_{x_i \in M} y_i(w\cdot x_i+b)$$

感知机学习算法

• 假设误分类点集合 $M$ 是固定的，那么损失函数 $L(w,b)$ 的梯度为

  $$\nabla_wL(w,b) = - \sum\limits_{x_i \in M} y_ix_i \\ \nabla_bL(w,b) = - \sum\limits_{x_i \in M} y_i$$
• 随机选取一个误分类点 $(x_i,y_i)$ 对 $w,b$ 进行更新

  $$w \leftarrow w + \eta y_i x_i \\ b \leftarrow b + \eta y_i$$

感知机学习算法原始形式

• 输入

  • 训练数据集

  • 学习率

• 输出

  • $w,b$

  • 感知机模型 $f(x) = \operatorname{sign}(w\cdot x + b)$

• 算法步骤

  • 选取初值 $w_0,b_0$

  • 在训练集中选取数据 $(x_i,y_i)$

  • 如果 $y_i(w\cdot x + b) < 0$

    • 更新参数

    • $$w \leftarrow w + \eta y_i x_i \\ b \leftarrow b + \eta y_i$$
  • 转至第二步，直至训练集中没有误分类点

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