Perceptron(感知机)

综述

所谓的“感知机”这个名词显得有点名不副实,因为我实在没觉得它的机制和感知不感知有什么联系,容易误导不明真相的群众。

其实不过就是二类分类的线性分类模型,一种将实例划分成为正负两类的判别模型。得到实例的输入之后,再输出值(只能是+1和-1这两个值)。

感知机学习的终极目标就是通过训练样本最终找到一个能将正负类型隔开的一个超平面。

直观的几何理解:

分类

理论定义

假设输入空间(特征空间)是 \(X \subset R^n\) ,输出空间是\(Y \in {+1, -1}\)。 输入\(x \in X\) 表示实例的特征向量,对应于输入空间(特征空间)的点;输出\(y \in Y\)表示实例的类别。 由输入空间到输出空间当然如下函数成为感知机。

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

其中,

(1) w,b为感知机模型参数,sign()为符号函数

(2) x - 空间中的一个点,它是一个n维向量:\( (x^{(1)}, x^{(2)}, …, x^{(n)}) \)

(3) y - 对应于x的分类,取值{-1,1},一般认为当x在超平面S上时取+1(与S法向量同方向);反之则取-1

(4) w - 权值(weight)或权值向量(weight vector)

(5) b - 偏置(bias)

(6) \(w \cdot x\) 表示 向量w 和 x的内积.

(7) sign() - 符号函数,即

$$sign(x) = \begin{equation}\begin{cases} 1, x \geq 0 \\
0, x < 0 \end {cases} \end{equation}$$

!注意:这里的x,w其实都是向量而非单变量!每一个x都代表空间中的一个点,以三维空间为例,\(x_0 = ( x^{(1)}, x^{(2)}, x^{(3)})\),此处的\( x^{(1)}, x^{(1)}, x^{(1)}\)对应于高中数学中见到的x,y,z。此处的y并非是x,y,z中的y,它只是用来表示点x所属的分类,可以记为任何字母,比如c。

详细的几何解释:

分类

感知机的学习策略:

这里有一个前提假设——假设训练数据集是线性可分的。

感知机学习的目标是求一个能将训练集正负实例点完全正确分开的分离超平面。即确定感知机模型参数w, b。

为了实现此目标我们需要确定一个学习策略,即定义一个经验损失函数,并使其损失极小化。

此时最容易想到的损失函数就是错误分类点的总数(设所有误分类的点集合为M),即:

$$L(w,b) = |M|$$

但是显然,这个损失函数与参数w,b并无直接相关,我们不太容易通过正常的方法来建立起它和w,b之间的关系并找到最终所需要的超平面,所以将这个损失函数暂时放到一边。

关于损失函数的另一个选择是所有误分类点到超平面S的总距离。首先,根据所学的数学知识,显然空间中的一点$x_0$到超平面S的距离表示为:

$$\frac{1}{||w||}|w \cdot x_0 + b|$$

此处的||w|| 是w的L_2范式,即 \(||w|| = \sqrt{w_1^2 + w_2^2 + … \quad} \)

不难发现,对于被错误分类的数据 \((x_0,y_0)\) 来说, \(y_0(w \cdot x_0 + b) \leq 0\) 恒成立。因为对于被错误分类分类的点,

(1) 当 \((w \cdot x_0 + b) > 0\) 时,\(y = -1\),此时 \( y_0(w \cdot x_0 + b) = -1(w \cdot x_0 + b) < 0 \);

(2) 当 \((w \cdot x_0 + b) < 0\) 时,同理可知, \(y_0(w \cdot x_0 + b) < 0\) 也成立;

(3) 当 \((w \cdot x_- + b) = 0\) 时,点位于超平面上,也属于不能被正确分类。(其实=0时还有另一种情况)

因此对于错误分类的点来说,\(y_0(w \cdot x_0 + b) \leq 0\) 恒成立。

设误分类点的集合为M,则所有无分类点到S的总距离为:

$$\frac{1}{||w||}\sum_{x_i \in M}y_i(w \cdot x + b)$$

得到新的损失函数:

$$L(w,b) = -\frac{1}{||w||} \sum_{x_{i} \in M} y_{i}(w \cdot x_i + b)$$

显然,此L(w, b) >= 0 恒成立(距离), 当其为0时就算找到了可以适合训练数据的超平面。 明显,损失函数L(w,b)是w,b的线性函数,而且是w,b的连续可导函数。

因此我们就决定使用它了!但是这里,我们不考虑\( \frac{1}{||w||} \)(我猜可能是因为考虑到这样求梯度比较方便),稍微修改之后选定最终的损失函数为:

损失函数:

$$ L(w,b) = - \sum_{x_{i} \in M} y_{i}(w \cdot x_i + b) $$

感知机学习算法

采用随机梯度下降法(stochastic gradient desecent)。

首先,任意选取一个超平面$ w_0, b_0 $,然后使用梯度下降法不断地极小化目标函数,极小化的过程是每次随机选取M中的一个点来使其梯度下降。

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

$$\nabla_w L(w,b) = - \sum_{x_i \in M}\quad y_ix_i \\
\nabla_b L(w,b) = -\sum_{x_i \in M}\quad y_i$$

每次随机从M中选取一个分类点(x_i, y_i),对w, b进行更新:

$$w = w + ry_ix_i \\
b = b + ry_i$$

其中r(0 < r)

通过这种迭代可以期待损失函数不断减小,直到最终为0.(前提是数据集确实线性可分)

一个简单的训练案例如下:

正分类点:\( {x_0 = (3,3)^T, (y_0 = +1)} \);

负分类点:\( {x_1 = (1,1)^T, (y_1 = -1)} \);

学习率: r = 1;

初始值随机挑选:

\( w = (2,2)^T \);

\( b = -2 \);

带入判断公式:\( y_0(w \cdot x_0 + b) \),发现\( x_1 \)属于误分类点(因为带入判断公式后求出的值

$$w = w + rx_1y_1 = (2,2)^T + 1\times(-1)\times(1,1) = (1,1)^T \\
b = b + ry_1 = -2 + 1 \times (-1) = -3$$

至此得到最终的超平面S:

$$x^{(1)} + x^{(2)} -3 = 0$$

分类超平面

简而言之:

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

  • 感知机模型:

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

  • 训练数据集:

$$T = {(x_1, y_1),(x_2, y_2),\quad …\quad, (x_n, y_n)}$$

其中\(x_i \in R^n,\quad y_i \in {-1, +1}\); 学习率r

  • 输入:

w, b;

  • 步骤:

(1) 随机选取初始值\(w_0, b_0\)

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

(3) 如果\( y_i(wx_i + b) \leq 0 \) (误分类点),则:

$$w = w + ry_ix_i \\
b = b + ry_i$$

(4) 转(2),直至训练集中没有误分类点