感知机是二分类线性分类模型,其输入为实例的特征向量,输出为实例的类别,取 +1 和 -1 两值。感知机对应于输入空间(特征空间)中将实例划分为正负两例的分离超平面,属于判别模型。 感知机学习旨在求出将训练集进行线性划分的分离超平面,导入基于误分类的损失函数,利用 梯度下降法对损失函数进行极小化,求得感知机模型。感知机由 Rosonblatt 1957 年提出,是神经网络与支持向量机的基础。

一、感知机模型

定义

假设输入空间(特征空间)是 $ X \in R^n $,输出空间是 $ Y={+1,-1} $.输入 $ x\in X $ 表示实例的特征向量,对应于输入(特征)空间的点,输出 $ y \in Y $表示实例的类别。由输入空间到输出空间的如下函数$$ f(x)=sign(w\cdot x + b) $$称为感知机。其中,$ w $、$ b $ 为感知机模型参数,$ w \in R^n $ 叫做权值或者权值向量,$ b \in R $ 叫做偏置,$sign$是符号函数:$$ sign(x)= \begin{cases} +1,\quad x \ge 0 \\ -1, \quad x < 0 \end{cases} $$

感知机是一种线性分类模型,属于判别模型,其假设空间是定义在特征空间的所有线性分类模型或线性分类器,即函数集合$\{f|f(x)=w\cdot x+b\}$

几何解释

感知机模型

感知机模型

二、感知机学习策略

假设训练数据集是线性可分的(存在超平面将数据集的正负实例划分到超平面的两侧),感知机的学习目标是求得一个能够将训练数据集正负实例点完全正确分开的分离超平面,需要确定一个学习策略,即定义(经验)损失函数并将其极小化。

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

损失函数的另一个选择是误分类点到超平面的总距离,这是感知机所采用的,忽略前面的 $w$ 的$L_2$范数,感知机 $sign (w\cdot x+b)$ 学习的损失函数定义为$$ L(w,b)=-\sum\limits_{x_i \in M}y_i(w\cdot x_i +b) $$ 其中,$M$为误分类点的集合,这个损失函数就是感知机学习的经验风险函数。

显然,上述损失函数是非负的,如果没有误分类点,损失函数值为0,并且损失函数 $L(w,b)$ 是 $w,b$的连续可导函数,感知机的学习策略是在假设空间中选取使损失函数 $L(w,b)$ 最小的模型参数 $w,b$。

三、感知机学习算法

感知机学习问题转化为求解损失函数的最优化问题,最优化的方法是随机梯度下降法。感知机的学习算法 是误分类驱动的,具体采用的随机梯度下降。首先,任意选取一个超平面,然后用梯度下降法 不端极小化目标函数,极小化过程中不是一次使所有误分类点的梯度下降,而是一次随机选取误分类点使其梯度下降。

原始形式

输入:训练数据集$ T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$,其中,$x_i\in X=R^n$, $y_i \in Y=\{-1,+1\}, i=1,2,...,N$,学习率 $\eta(0<\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\cdot x_i+b) \le 0$,则更新:$$ w \gets w+\eta y_ix_i \\ b \gets b+\eta y_i $$
  4. 转至2,直至训练集没有误分类点。

解释:当一个实例点被误分类时,即位于分离超平面错误一侧时,则调整 $w,b$ 的值,使分离超平面向该误分类的一侧移动, 以减少该误分类点与超平面的距离,直至超平面越过该误分类点使其被正确分类。

对偶形式

输入:线性可分的数据集$ T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$,其中 $x_i\in X=R^n$, $y_i \in Y=\{-1,+1\}, i=1,2,...,N$,学习率 $\eta(0<\eta\le 1)$;

输出:$\alpha,b$,感知机模型 $f(x)=sign(\sum\limits_{j=1}^N{\alpha_jy_jx_jx+b})$, 其中 $\alpha=(\alpha_1,\alpha_2,…,\alpha_N)^T$

  1. $\alpha \gets 0,b\gets 0$
  2. 在训练集上选取数据$(x_i,y_i)$
  3. 如果 $y_i(\sum\limits_{j=1}^N{\alpha_jy_jx_j\cdot x_i+b}) \le 0 $,则: $$\alpha_i \gets \alpha_i +\eta$$ $$b \gets b+ \eta y_i$$
  4. 转至2,直至训练集没有误分类点。

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

收敛性证明

从训练集线性可分出发,可以证明,具体证明过程从略。