第二章 感知机

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取 $+1$ 和 $-1$ 二值。

感知机对应输入空间（特征空间）中将实例划分为正负两类的分离超平面（separating hyperplane），属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面。

导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

2.1 感知机模型

定义2.1（感知机） 假设输入空间（特征空间）是$\chi \subseteq R^n$,输出空间是$Y=\{+1, -1\}$。输入$x \in \chi$表示实例的特征向量，对应于输入空间（特征空间）的点；

输出$y \in Y$表示实例的类别。由输入空间到输出空间的如下函数：

$$f(x) = sign(\omega·x + b) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.1)$$

称为感知机。其中，$\omega$和$b$为感知机模型参数，$\omega \in R^n$叫作全职（weight）或权值向量（weight vector），$b \in R$叫作偏置（bias），$\omega·x$表示$\omega$和$x$的内积。$sign$是符号函数，即

$$sign(x) = \lbrace_{ -1,\ \ x < 0 }^{+1,\ \ x \geq 0} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.2)$$

感知机模型的假设空间定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器（linear classifier），即函数集合：

$$\{f|f(x) = \omega·x + b\}$$

感知机由如下几何解释：线性方程

$$\omega·x + b = 0$$

对应于特征空间$R^n$中的一个超平面$S$,其中$\omega$是超平面的法向量，$b$是超平面的截距。

• 感知机学习，由训练数据集（实力的特征向量及类别）求得感知机模型（2.1），即求得模型参数$\omega,b$。

• 感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。

2.2 感知机学习策略

2.2.1 数据集的线性可分性

定义2.2（数据集的线性可分性） 给定一个数据集

$$T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$

其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$，如果存在某个超平面$S$

$$\omega·x + b = 0$$

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有$y_i=+1$的实例$i$，有$\omega·x + b > 0$，对所有$y_i = -1$的实例$i$，有$\omega·x + b < 0$，则称数据集$T$为线性可分数据集（linearly separable data set）；否则，称数据集$T$线性不可分。

2.2.2 感知机学习策略

为了找出这样的超平面，即确定感知机模型参数$\omega,b$，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。

损失函数的选择是误分类点到超平面$S$的总距离，这是感知机所采用的。

• 假设超平面$s$的误分类点集合为$M$，那么所有误分类点到超平面$S$的总距离为

$$-\frac{1}{||\omega||}\sum\limits_{x_i \in M} y_i(\omega·x_i + b)$$

​ 不考虑$\frac{1}{||\omega||}$，就得到感知机学习的损失函数。

• 感知机$sign(\omega·x + b)$学习的损失函数定义为

$$L(\omega,b) =-\sum\limits_{x_i \in M} y_i(\omega·x_i + b) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.4)$$

​ 这个损失函数就是感知机学习的经验风险函数。

显然，损失函数$L(\omega,b)$是非负的。如果没有误分类点，损失函数值是$0$。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。

一个特定的样本点的损失函数：在误分类时是参数$\omega,b$的线性函数，在正确分类时是$0$。因此，给定训练数据集$T$，损失函数$L(\omega,b)$是$\omega,b$的连续可导函数。

感知机学习的策略是在假设空间中选取使损失函数（2.4）最小的模型参数$\omega,b$，即感知机模型。

2.3 感知机学习算法

感知机学习算法是对以下最优化问题的算法。

$$\min\limits_{\omega,b} L(\omega,b) = - \sum\limits_{x_i \in M} y_i(\omega·x_i + b) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.5)$$

感知机学习算法是误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。首先，任意选取一个超平面$\omega_0,b_0$，然后用梯度下降法不断地极小化目标函数(2.5)。极小化过程中不是一次使$M$中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

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

$$\bigtriangledown_{\omega}L(\omega,b) = - \sum\limits_{x_i \in M}y_i x_i$$ $$\bigtriangledown_{b}L(\omega,b) = - \sum\limits_{x_i \in M}y_i$$

​ 给出。

• 随机取一个误分类点$(x_i,y_i)$，对$\omega,b$进行更新：

  $$\omega \longleftarrow \omega \ + \ \eta y_i x_i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.6)$$ $$b \longleftarrow b\ + \ \eta y_i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.7)$$

式中$\eta(0<\eta \le 1)$是步长，在统计学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数$L(\omega,b)$不断减小，直到为$0$。

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

输入：训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$；学习率$\eta(0<\eta \le 1)$；

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

​ （1）选取初值$\omega_0,b_0$；

​ （2）在训练集中选取数据$(x_i,y_i)$；

​ （3）如果$y_i(\omega·x_i + b) \leq 0$，

$$\omega \longleftarrow \omega \ + \ \eta y_i x_i \\ b \longleftarrow b\ + \ \eta y_i$$

​ （4）转至（2），直至训练集中没有误分类点。

这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整$\omega,b$的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。

2.3.2 算法的收敛性

为了便于叙述与推导，将偏置$b$并入权重向量$\omega$，记作$\hat\omega = (\omega^T,b)^T$，同样也将输入向量加以扩充，加进常数$1$，记作$\hat x=(x^T,1)^T$。这样，$\hat x \in R^{n+1},\hat\omega \in R^{n+1}$。显然，$\hat\omega·\hat x = \omega·x + b$。

定理 2.1（Novikoff） 设训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$，则

​ （1）存在满足条件$||\hat\omega_{opt}||=1$的超平面$\hat\omega_{opt}·\hat x =\omega_{opt}·x+b_{opt} = 0$将训练数据集完全正确分开；且存在$\gamma>0$，对所有$i=1,2,…,N$

$$y_i(\hat\omega_{opt}·\hat x_i) = y_i(\omega_{opt}·x_i+b_{opt}) \geq \gamma \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.8)$$

​ （2）令$R=\max\limits_{1\leq i \leq N}||\hat x_i||$，则感知机算法2.1在训练数据集上的误分类次数$k$满足不等式

$$k \leq(\frac{R}{\gamma})^2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.9)$$

定理表明，误分类的次数$k$是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。

感知机学习算法存在许多解，这些解既依赖与初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。

当训练集线性不可分时，感知机学习算法不收敛，迭代结果会放生震荡。

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

对偶形式的基本想法是，将$\omega$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$\omega$和$b$。

在算法2.1中可假设初始值$\omega_0,b_0$均为0。对误分类点$(x_i,y_i)$通过

$$\omega \longleftarrow \omega \ + \ \eta y_i x_i \\ b \longleftarrow b\ + \ \eta y_i$$

逐步修改$\omega,b$，设修改$n$次，则$\omega,b$关于$(x_i,y_i)$的增量分别是$\alpha_i y_i x_i$和$\alpha_i y_i$，这里$\alpha_i = n_i\eta$，$n_i$是点$(x_i,y_i)$被误分类的次数。最后学习到的$\omega,b$可以分别表示为

$$\omega = \sum\limits_{i=1}^N \alpha_i y_i x_i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.14) \\ b = \sum\limits_{i=1}^N \alpha_i y_i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.15)$$

这里，$\alpha_i \geq 0,i=1,2,…,N$，当$\eta = 1$时，表示第$i$个实例点由与误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。

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

输入：训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$；学习率$\eta(0<\eta \le 1)$；

输出：$\alpha,b$；感知机模型$f(x)=sign(\sum\limits_{j=1}^N \alpha_j y_j x_j · x + b)$，其中$\alpha = (\alpha_1, \alpha_2,…,\alpha_N)^T$。

​ （1）$\alpha \longleftarrow 0, b \longleftarrow 0$；

​ （2）在训练集中选取数据$(x_i,y_i)$；

​ （3）如果$y_i(\sum\limits_{j=1}^N \alpha_j y_j x_j · x + b) \leq 0$，

$$\alpha_i \longleftarrow \alpha_i \ + \ \eta \\ b \longleftarrow b \ + \ \eta y_i$$

​ （4）转至（2）直到没有误分类数据。

对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的$Gram$矩阵（Gram matrix）

$$G = [x_i · x_j]_{N \times N}$$

与原始形式一样，感知机学习算法的对偶形式迭代是收敛的，存在多个解。