感知器(Perceptron)1957年提出,是一种广泛使用的线性分类器。感知器可谓是最简单的人工神经网络,只有一个神经元。
1. 概述
感知器是对生物神经元的简单数学模拟,有与生物神经元相对应的部件,如权重(突触)、偏置(阈值)及激活函数(细胞体),输出为 +1 或-1。
感知器是一种简单的两类线性分类模型。(分段函数)
2 参数学习
感知器学习算法也是一个经典的线性分类器的参数学习算法。
给定N个样本的训练集:,其中
,感知器学习算法试图找到一组参数
,使得对于每个样本
有
感知器的学习算法是一种错误驱动的在线学习算法。先初始化一个权重向量(通常是全零向量),然后每次分错一个样本
时,即
,就用这个样本来更新权重。
根据感知器的学习策略,可以反推出感知器的损失函数为:
采用随机梯度下降,其每次更新的梯度为
图3.5给出了感知器参数学习的更新过程,其中红色实心点为正例,蓝色空心点为负例。黑色箭头表示权重向量,红色虚线箭头表示权重的更新方向。
3 感知器的收敛性
Novikoff [1963]证明对于两类问题,如果训练集是线性可分的,那么感知器算法可以在有限次迭代后收敛。然而,如果训练集不是线性分隔的,那么这个算法则不能确保会收敛。
当数据集是两类线性可分时,对于训练集,其中
为样本的增广特征向量,
,那么存在一个正的常数
和权重向量
,并且
,对所有
都满足
。我们可以证明如下定理。
定理3.1–感知器收敛性:给定一个训练集
, 假设
是训练集中最大的特征向量的模,
如果训练集 线性可分,感知器学习算法3.1的权重更新次数不超
过
证明. 感知器的权重向量的更新方式为
其中表示第k个错误分类的样本。
因为初始权重向量为0,在第次更新时感知器的权重向量为
分别计算的上下界:
(1)的上界为:
(2)的下界为:
两个向量内机的平方一定小于等于这两个向量的模的乘积
由公式(3.8)和(3.94),得到
取最左和最右的两项,进一步得到,。然后两边除以
,最终得到
因此,在线性可分的条件下,算法3.1会在 步内收敛。
虽然感知器在线性可分的数据上可以保证收敛,但其存在以下不足之处:
- 在数据集线性可分时,感知器虽然可以找到一个超平面把两类数据分开, 但并不能保证能其泛化能力。
- 感知器对样本顺序比较敏感。每次迭代的顺序不一致时,找到的分割超平面也往往不一致。
- 如果训练集不是线性可分的,就永远不会收敛[Freund and Schapire, 1999]。