Perceptron
Table of Contents
1. 感知器(Perceptron)简介
The perceptron algorithm was invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt.
感知器是一个线性分类模型,可用于二类分类(输出只有两类的情况)。感知器是神经网络和支持向量机的基础。
本文主要参考:《统计学习方法, 李航著》
2. 感知器模型定义
设输入空间为
称为 感知器(Perceptron) 。其中,
感知器模型的运用过程是:利用给定的训练数据集求出感知器模型的参数
3. 感知器模型的几何解释
感知器模型的几何解释如下:
线性方程:
对应于输入空间
考虑输入空间为
Figure 1: 感知器模型的几何解释
4. 感知器算法
为了确定感知器模型的参数
4.1. 选择损失函数
如何定义损失函数呢?直观的方法是计算训练数据集在模型中的错误分类点的数量。但是,这个损失函数不是参数
我们知道,输入空间
特别地,当输入空间为
由于距离公式中含有绝对值符号,不便于计算。考虑到,对于错误分类点
假设分离超平面
不考虑
感知器的损失函数定义为:
其中,
4.2. 感知器参数迭代过程
通过上面的分析,我们可知感知器学习算法对应于下面的最优化问题:
给定一个训练数据集
其中,
其中,
我们使用“梯度下降法(Gradient descent)”解决这个最优化问题。
这里,直接利用“梯度下降法”的结论公式:
其中
对于这个最优化问题,假设错误分类点集合
将上面式子代入到“梯度下降法”的公式中,得到参数
随着迭代的进行,错误分类点会减小,直到没有错误分类点,迭代结束,这时损失函数(错误分类点到分类超平面的总距离)为 0。
说明:上面式子中,每次对
4.2.1. 感知器参数 的迭代过程演示
在图 2 中,假设虚线是对参数
图中,训练集中有两个点被错误地分类
所以,更新后得到的新的方程(图中的实线)为:
Figure 2: 感知器参数
注:上面实例摘自:Pattern Recognition, 4th, by Sergios Theodoridis, Section 3.3 The Perceptron Algorithm
4.3. 感知器算法描述
前面已经完整地介绍了感知器算法,现在总结如下。
感知器学习算法的原始形式:
感知器模型:
输入:线性可分的训练数据集
输出:感知器模型参数
(1) 选取初值
(2) 在训练数据集中选取数据
(3) 如果
(4) 转至(2),直到没有错误分类点。
说明:上面算法,在某一次具体的迭代中,没有让所有的错误分类点都参与迭代,即没有采用式子
4.4. 感知器算法应用实例(利用训练数据集求出模型的参数)
实例:假设训练数据集有两个正实例点(应该分到+1 类的点)A、B分别为:
解:
(1) 取学习率
(2) 对于正实例点 A,计算得
(3) 对于正实例点 A、B,计算得
如此继续下去,直到得到
具体迭代过程如下:
迭代次数 | 错误分类点 | |||
---|---|---|---|---|
0 | 0 | 0 | ||
1 | A | 1 | ||
2 | C | 0 | ||
3 | C | -1 | ||
4 | C | -2 | -2 | |
5 | A | -1 | ||
6 | C | -2 | ||
7 | C | -3 | ||
8 | Nil |
此时,对 A、B、C 三个实例点都有
所以,我们得到的分离超平面为:
感知器模型为:
Figure 3: 不同的迭代策略可能得到不同的感知器模型
上面的迭代过程中,错误分类点先后取的是 A、C、C、C、A、C、C;在迭代过程中,还可以依次取错误分类点 A、C、C、C、B、C、C、C、A、C、C,那么得到的分离超平面为:
可见, 采用不同的初值,或当存在多个错误分类点时采用不同策略选取错误分类点来更新参数,感知机学习算法得到的解可能不同。
4.5. 感知器算法的收敛性
Novikoff 于 1962 年证明了感知机算法的收敛性。 即对于线性可分的数据,利用感知器算法经过有限次迭代,一定可以得到训练数据集的分离超平面。 其具体证明过程可以参考:《统计学习方法, 李航著》
5. 感知器推广
前面介绍的感知器只能把完全线性可分的数据分为两个种类。
袋式算法(Pocket Algorithm)可以处理线性不可分的数据集。
Kesler 结构把感知器推广到了“多个种类”的分类问题。
6. 感知器表示神经元
感知器可以形象地表示为图 4 所示(图中偏置
Figure 4: 感知器可以表示神经元
7. 感知器算法的对偶形式
感知器的基本知识点已经介绍完了,下面介绍感知器算法的对偶形式。它是感知机算法原始形式的另外一种表达形式,之所以介绍它是因为它有一个特点——“训练感知器模型时只要用到训练数据集实例间的内积形式”,利用这个特点,我们可以把 Kernel Method 应用到感知器(这又称为Kernel perceptron ),使感知器能够处理线性不可分数据。(说明:本文仅仅简单地介绍感知器算法的对偶形式,并不会介绍 Kernel perceptron)。
说明:在 约束 最优化问题中,我们有时通过求解其“拉格朗日对偶问题”来求解原问题。但感知器是无约束最优化问题(由前面的介绍可知,感知器的损失为:
7.1. 感知器算法对偶形式
在感知器算法的原始形式中,不失一般性,可以假设
假设这个错误分类点在更新
其中,
利用上面的结论,我们把感知器算法的原始形式表述为下面形式(即感知器算法的对偶形式)。
感知器学习算法的对偶形式描述如下:
感知器模型:
输入:线性可分的训练数据集
输出:感知器模型参数
(1)
(2) 在训练数据集中选取数据
(3) 如果
(4) 转至(2),直到没有错误分类点。
7.2. 感知器算法对偶形式的特点
感知器算法的对偶形式中,训练数据仅以“内积”的形式(即
7.3. Gram Matrix
为了方便使用感知器算法的对偶形式,我们可以提前把训练数据集中所以训练数据间的“内积”计算出来。这个矩阵就是格拉姆矩阵(Gram Matrix)。
对于
显然,Gram Matrix 是一个对称矩阵(因为
7.3.1. Gram Matrix 计算实例
设
直接套用 Gram Matrix 定义式,可得:
7.4. 实例:感知器算法对偶形式
实例(这个例子的数据集和前面介绍感知器算法原始形式时的例子是相同的):假设训练数据集有两个正实例点(应该分到+1 类的点)A、B分别为:
解:
(1) 取
(2) 计算数据集对应的 Gram 矩阵:
(3) 随机选择一个点
反复迭代,直到没有错误分类点。具体迭代过程(共迭代了 7 次)如表 2 所示。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
0 | 0 | 1 | 2 | 2 | 3 | 4 | 5 | |
0 | 1 | 0 | -1 | 0 | -1 | -2 | -3 |
(4) 由计算出来的