第2章
感知机

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和−1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的输入实例进行分类。感知机在1957年由Rosenblatt提出，是神经网络与支持向量机的基础。

本章首先介绍感知机模型；然后叙述感知机的学习策略，特别是损失函数；最后介绍感知机学习算法，包括原始形式和对偶形式，并证明算法的收敛性。

2.1　感知机模型

定义2.1（感知机） 假设输入空间（特征空间）是 X ⊆ R ⁿ ，输出空间是 Y ={+1,−1}。输入 x ∈ X 表示实例的特征向量，对应于输入空间（特征空间）的点；输出 y ∈ Y 表示实例的类别。由输入空间到输出空间的如下函数

称为感知机。其中， w 和 b 为感知机模型参数， w ∈ R ⁿ 叫作权值（weight）或权值向量（weight vector）， b ∈ R 叫作偏置（bias）， w · x 表示 w 和 x 的内积。sign是符号函数，即

感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器（linear classifier），即函数集合{ f|f （ x ）= w · x + b }。

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

对应于特征空间 R ⁿ 中的一个超平面 S ，其中 w 是超平面的法向量， b 是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面 S 称为分离超平面（separating hyperplane），如图2.1所示。

感知机学习由训练数据集（实例的特征向量及类别）

T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}

其中， x _i ∈ X = R ⁿ ， y _i ∈ Y ={+1,−1}， i =1,2,…, N ，求得感知机模型（式（2.1）），即求得模型参数 w ， b 。感知机预测通过学习得到的感知机模型，对新的输入实例给出其对应的输出类别。

2.2　感知机学习策略

2.2.1　数据集的线性可分性

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

T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}

其中， x _i ∈ X = R ⁿ ， y _i ∈ Y ={+1,−1}， i =1,2,…, N ，如果存在某个超平面 S

w · x + b =0

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

2.2.2　感知机学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面，即确定感知机模型参数 w ， b ，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数 w ， b 的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面 S 的总距离，这是感知机所采用的。为此，首先写出输入空间 R ⁿ 中任一点 x ₀ 到超平面 S 的距离：

这里，‖ w ‖是 w 的 L ₂ 范数。

其次，对于误分类的数据（ x _i , y _i ），

− y _i （ w · x _i + b ）>0

成立。因为当 w · x _i + b >0时， y _i =−1；而当 w · x _i + b <0时， y _i =+1。因此，误分类点 x _i 到超平面 S 的距离是

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

不考虑 ，就得到感知机学习的损失函数 ^[1] 。

给定训练数据集

T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}

其中， x _i ∈ X = R ⁿ ， y _i ∈ Y ={+1,−1}， i =1,2,…, N 。感知机sign（ w · x + b ）学习的损失函数定义为

其中， M 为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。

显然，损失函数 L （ w,b ）是非负的。如果没有误分类点，损失函数值是0。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。一个特定的样本点的损失函数在误分类时是参数 w ， b 的线性函数，在正确分类时是0。因此，给定训练数据集 T ，损失函数 L （ w,b ）是 w ， b 的连续可导函数。

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

2.3　感知机学习算法

感知机学习问题转化为求解损失函数式（2.4）的最优化问题，最优化的方法是随机梯度下降法。本节叙述感知机学习的具体算法，包括原始形式和对偶形式，并证明在训练数据线性可分条件下感知机学习算法的收敛性。

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

感知机学习算法是对以下最优化问题的算法。给定一个训练数据集

T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}

其中， x _i ∈ X = R ⁿ ， y _i ∈ Y ={−1,1}， i =1,2,…, N ，求参数 w ， b ，使其为以下损失函数极小化问题的解：

其中， M 为误分类点的集合。

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

假设误分类点集合 M 是固定的，那么损失函数 L （ w,b ）的梯度由

给出。

随机选取一个误分类点（ x _i , y _i ），对 w,b 进行更新：

式中 η （0< η ≤1）是步长，在机器学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数 L （ w,b ）不断减小，直到为0。综上所述，得到如下算法：

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

输入：训练数据集 T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}，其中 x _i ∈ X = R ⁿ ， y _i ∈ Y ={−1,+1}， i =1,2,…, N ；学习率 η （0< η ≤1）。

输出： w ， b ；感知机模型 f （ x ）=sign（ w · x + b ）。

（1）选取初值 w ₀ , b ₀ ；

（2）在训练集中选取数据（ x _i , y _i ）；

（3）如果 y _i （ w · x _i + b ）≤0，则

w←w + ηy _i x _i

b←b + ηy _i

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

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

算法2.1是感知机学习的基本算法，对应于后面的对偶形式，称为原始形式。感知机学习算法简单且易于实现。

例2.1 如图2.2所示的训练数据集，其正实例点是 x ₁ =（3,3） ^T ， x ₂ =（4,3） ^T ，负实例点是 x ₃ =（1,1） ^T ，试用感知机学习算法的原始形式求感知机模型 f （ x ）=sign（ w · x + b ）。这里， w =（ w ⁽¹⁾ , w ⁽²⁾ ） ^T ， x =（ x ⁽¹⁾ , x ⁽²⁾ ） ^T 。

解 构建最优化问题：

按照算法2.1求解 w ， b ， η =1。

（1）取初值 w ₀ =0， b ₀ =0；

（2）对 x ₁ =（3,3） ^T ， y ₁ （ w ₀ · x ₁ + b ₀ ）=0，未能被正确分类，更新 w,b ：

w ₁ = w ₀ + y ₁ x ₁ =（3,3） ^T , b ₁ = b ₀ + y ₁ =1

得到线性模型：

w ₁ · x + b ₁ =3 x ⁽¹⁾ +3 x ⁽²⁾ +1

（3）对 x ₁ , x ₂ ，显然， y _i （ w ₁ · x _i + b ₁ ）>0，被正确分类，不修改 w,b ；对 x ₃ =（1,1） ^T ， y ₃ （ w ₁ · x ₃ + b ₁ ）<0，被误分类，更新 w,b ：

w ₂ = w ₁ + y ₃ x ₃ =（2,2） ^T , b ₂ = b ₁ + y ₃ =0

得到线性模型：

w ₂ · x + b ₂ =2 x ⁽¹⁾ +2 x ⁽²⁾

如此继续下去，直到

w ₇ =（1,1） ^T , b ₇ =−3

w ₇ · x + b ₇ = x ⁽¹⁾ + x ⁽²⁾ −3

对所有数据点 y _i （ w ₇ · x _i + b ₇ ）>0，没有误分类点，损失函数达到极小。

分离超平面为 x ⁽¹⁾ + x ⁽²⁾ −3=0，感知机模型为 f （ x ）=sign（ x ⁽¹⁾ + x ⁽²⁾ −3）。

迭代过程见表2.1。

这是在计算中误分类点先后取 x ₁ ， x ₃ ， x ₃ ， x ₃ ， x ₁ ， x ₃ ， x ₃ 得到的分离超平面和感知机模型。如果在计算中误分类点依次取 x ₁ ， x ₃ ， x ₃ ， x ₃ ， x ₂ ， x ₃ ， x ₃ ， x ₃ ， x ₁ ， x ₃ ， x ₃ ，那么得到的分离超平面是2 x ⁽¹⁾ + x ⁽²⁾ −5=0。

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

2.3.2　算法的收敛性

现在证明，对于线性可分数据集，感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。

为了便于叙述与推导，将偏置 b 并入权重向量 w ，记作 ，同样也将输入向量加以扩充，加进常数1，记作 。这样 ， 。显然， 。

定理2.1（Novikoff） 设训练数据集 T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}是线性可分的，其中 x _i ∈ X = R ⁿ ， y _i ∈ Y ={−1,+1}， i =1,2,…, N ，则

（1）存在满足条件 的超平面 将训练数据集完全正确分开；且存在 γ >0，对所有 i =1,2,…, N ，有

（2）令 ，则感知机算法2.1在训练数据集上的误分类次数 k 满足不等式

证明 （1）由于训练数据集是线性可分的，按照定义2.2，存在超平面可将训练数据集完全正确分开，取此超平面为 ，使 。由于对有限的 i =1,2,…, N ，均有

所以存在

使

（2）感知机算法从 开始，如果实例被误分类，则更新权重。令 是第 k 个误分类实例之前的扩充权重向量，即

则第 k 个误分类实例的条件是

若（ x _i , y _i ）是被 误分类的数据，则 w 和 b 的更新是

w _k ← w _{k− 1} + ηy _i x _i

b _k ← b _{k− 1} + ηy _i

即

下面推导不等式（2.12）及不等式（2.13）：

由式（2.11）及式（2.8）得：

由此递推即得不等式（2.12）：

由式（2.11）及式（2.10）得：

结合不等式（2.12）及式（2.13）即得：

于是

定理表明，误分类的次数 k 是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。但是例2.1说明，感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。这就是第7章将要讲述的线性支持向量机的想法。当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生振荡。

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

现在考虑感知机学习算法的对偶形式。感知机学习算法的原始形式和对偶形式与第7章中支持向量机学习算法的原始形式和对偶形式相对应。

对偶形式的基本想法是：将 w 和 b 表示为实例 x _i 和标记 y _i 的线性组合的形式，通过求解其系数而求得 w 和 b 。不失一般性，在算法2.1中可假设初始值 w ₀ , b ₀ 均为0。对误分类点（ x _i , y _i ）通过

w←w + ηy _i x _i

b←b + ηy _i

逐步修改 w ， b ，设修改 n 次，则 w ， b 关于（ x _i , y _i ）的增量分别是 α _i y _i x _i 和 α _i y _i ，这里 α _i = n _i η,n _i 是点（ x _i , y _i ）被误分类的次数。这样，从学习过程不难看出，最后学习到的 w,b 可以分别表示为

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

下面对照原始形式来叙述感知机学习算法的对偶形式。

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

输入：线性可分的数据集 T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}，其中 x _i ∈ R ⁿ ， y _i ∈{−1,+1}， i =1,2,…, N ；学习率 η （0< η ≤1）。

输出： α,b ；感知机模型 ，其中 α =（ α ₁ , α ₂ ,…, α _N ） ^T 。

（1） α ←0， b← 0；

（2）在训练集中选取数据（ x _i , y _i ）；

（3）如果 ，则

α _i ← α _i + η

b←b + ηy _i

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

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

G =[ x _i · x _j ] _N×N

例2.2 数据同例2.1，正样本点是 x ₁ =（3,3） ^T ， x ₂ =（4,3） ^T ，负样本点是 x ₃ =（1,1） ^T ，试用感知机学习算法对偶形式求感知机模型。

解 按照算法2.2，

（1）取 α _i =0， i =1,2,3， b =0， η =1；

（2）计算Gram矩阵：

（3）误分条件

参数更新：

α _i ← α _i +1, b ← b + y _i

（4）迭代，过程从略，结果列于表2.2；

（5）

w =2 x ₁ +0 x ₂ −5 x ₃ =（1,1） ^T

b =−3

分离超平面为

x ⁽¹⁾ + x ⁽²⁾ −3=0

感知机模型为

f （ x ）=sign（ x ⁽¹⁾ + x ⁽²⁾ −3）

对照例2.1，结果一致，迭代步骤也是互相对应的。

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

本章概要

1．感知机是根据输入实例的特征向量 x 对其进行二类分类的线性分类模型：

f （ x ）=sign（ w · x + b ）

感知机模型对应于输入空间（特征空间）中的分离超平面 w · x + b =0。

2．感知机学习的策略是极小化损失函数：

损失函数对应于误分类点到分离超平面的总距离。

3．感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。

4．当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数 k 满足不等式

当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。

继续阅读

感知机最早在1957年由Rosenblatt提出 ^[1] 。Novikoff ^[2] ，Minsky与Papert ^[3] 等人对感知机进行了一系列理论研究。感知机的扩展学习方法包括口袋算法（pocket algorithm） ^[4] 、表决感知机（voted perceptron） ^[5] 、带边缘感知机（perceptron with margin） ^[6] 。关于感知机的介绍可进一步参考文献 [7] 和文献 [8] 。

习题

2.1 Minsky与Papert指出：感知机因为是线性模型，所以不能表示复杂的函数，如异或（XOR）。验证感知机为什么不能表示异或。

2.2 模仿例题2.1，构建从训练数据集求解感知机模型的例子。

2.3 证明以下定理：样本集线性可分的充分必要条件是正实例点集所构成的凸壳 ^[2] 与负实例点集所构成的凸壳互不相交。

参考文献

［1］ ROSENBLATT F. The perceptron：a probabilistic model for information storage and organization in the Brain[J]. Psychological Review, 1958, 65(6)：386–408.

［2］ NOVIKOFF A B. On convergence proofs on perceptrons[C]//Polytechnic Institute of Brooklyn. Proceedings of the Symposium on the Mathematical Theory of Automata. 1962：615–622.

［3］ MINSKY M L, Papert S A. Perceptrons[M]. Cambridge, MA：MIT Press. 1969.

［4］ GALLANT S I. Perceptron-based learning algorithms[J]. IEEE Transactions on Neural Networks, 1990, 1(2)：179–191.

［5］ FREUND Y, SCHAPIRE R E. Large margin classification using the perceptron algorithm[C]//Proceedings of the 11th Annual Conference on Computational Learning Theory(COLT’98). ACM Press, 1998.

［6］ LI Y Y, Zaragoza H, Herbrich R, et al. The perceptron algorithm with uneven margins[C]//Proceedings of the 19th International Conference on Machine Learning. 2002：379–386.

［7］ WIDROW B, LEHR M A.30 years of adaptive neural networks：perceptron, madaline, and backpropagation[J]. Proceedings of the IEEE, 1990, 78(9)：1415–1442.

［8］ CRISTIANINI N, SHAWE-TAYLOR J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge University Press, 2000.

---

[1] 第7章中会介绍 y ( w · x + b )称为样本点的函数间隔。

[2] 设集合 S ⊂ R ⁿ 是由 R ⁿ 中的 k 个点所组成的集合，即 S ={ x ₁ , x ₂ ,…, x _k }，定义 S 的凸壳conv( S )为

M+kHUnGvIR04VYaGoD19o01PkUSadVggnNaDya+Z9CsOAGKwJkbMDKD1JHS+y7xa