Perceptron

Table of Contents

1. 感知器(Perceptron)简介

The perceptron algorithm was invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt.

感知器是一个线性分类模型,可用于二类分类(输出只有两类的情况)。感知器是神经网络和支持向量机的基础。

本文主要参考:《统计学习方法, 李航著》

2. 感知器模型定义

设输入空间为 Rn (即 x=(x(1),x(2),,x(n))TRn ),输出空间为 {1,+1} ,由输入空间到输出空间的如下函数:
f(x)=sign(wx+b)={+1ifwx+b>01otherwise
称为 感知器(Perceptron) 。其中, wb 是感知器模型的参数, w=(w(1),w(2),,w(n))TRn 叫作权值向量(weight vector), bR 叫作偏置(bias)。 wx=i=0nw(i)x(i) 即向量的内积(或称点积)运算,它还有其他的记法,如 wx=w,x=wTx

感知器模型的运用过程是:利用给定的训练数据集求出感知器模型的参数 wb ,再对新的输入给出对应的输出类别。

3. 感知器模型的几何解释

感知器模型的几何解释如下:
线性方程:
wx+b=0
对应于输入空间 Rn 中的一个超平面 S ,这个超平面将输入空间划分为“正负”两类,这个超平面称为 分离超平面(Separating Hyperplane)

考虑输入空间为 R2 的简单情况,图 1 中红蓝点分别表示“正负”两种类别,其中两条斜线都是感知器模型的可行解。

perceptron.svg

Figure 1: 感知器模型的几何解释

4. 感知器算法

为了确定感知器模型的参数 wb ,我们需要定义一个学习策略, 即定义一个损失函数,求出当这个损失函数取得最小值时对应的感知器模型参数 wb

4.1. 选择损失函数

如何定义损失函数呢?直观的方法是计算训练数据集在模型中的错误分类点的数量。但是,这个损失函数不是参数 wb 的连续可导函数,不易优化。感知器选择了另外的损失函数: 训练数据集在模型中的错误分类点到分离超平面的总距离。

我们知道,输入空间 Rn 中任一点 x 到分离超平面的距离为:
1w|wx+b|

特别地,当输入空间为 R2 时,这就是点到线的距离公式 d=|ax0+by0+c|a2+b2 ;当输入空间为 R3 时,这就是点到平面的距离公式 d=|Ax0+By0+Cz0+D|A2+B2+C2

由于距离公式中含有绝对值符号,不便于计算。考虑到,对于错误分类点 xi 有:当 wxi+b>0 时, yi=f(xi)=1 ;当 wxi+b<0 时, yi=f(xi)=+1 。所以错误分类点 xi 来说,总有: yi(wxi+b)>0 ,利用这个性质可以去掉距离公式中的绝对值符号。即,错误分类点 xi 到分离超平面的距离也可表示为:
1wyi(wxi+b)

假设分离超平面 S 下的训练数据集的错误分类点为集合 M ,则所有错误分类点到超平面 S 的总距离为:
1wxiMyi(wxi+b)

不考虑 1w (对于线性可分的数据集,我们的目标是使损失函数为 0,所以可以省略了这个正系数,这时,优化过程中的损失函数不会严格等于错误分类点到分离超平面的总距离),得到的就是感知器使用的损失函数。

感知器的损失函数定义为:
L(w,b)=xiMyi(wxi+b)
其中, M 为训练数据集中错误分类点的集合。

4.2. 感知器参数迭代过程

通过上面的分析,我们可知感知器学习算法对应于下面的最优化问题:
给定一个训练数据集
T={(x1,y1),(x2,y2),,(xN,yN)}
其中, xiRn,yi{+1,1} ,求 wb 使得下面损失函数取得最小值。
L(w,b)=xiMyi(wxi+b)
其中, M 为训练数据集中错误分类点的集合。

我们使用“梯度下降法(Gradient descent)”解决这个最优化问题。
这里,直接利用“梯度下降法”的结论公式:
θnew=θoldμf(θold)=θoldμfθ|θ=θold,μ>0
其中 μ>0 称为步长,也可称为学习率。这是一个迭代式,在迭代过程中使损失函数不断减小。

对于这个最优化问题,假设错误分类点集合 M 是固定的,损失函数 L(w,b)=xiMyi(wxi+b) 的梯度为:
wL(w,b)=L(w,b)w=xiMyixi,bL(w,b)=L(w,b)b=xiMyi

将上面式子代入到“梯度下降法”的公式中,得到参数 w,b 的迭代策略:
{wnewwoldμ(xiMyixi)=wold+μxiMyixibnewboldμ(xiMyi)=bold+μxiMyi

随着迭代的进行,错误分类点会减小,直到没有错误分类点,迭代结束,这时损失函数(错误分类点到分类超平面的总距离)为 0。

说明:上面式子中,每次对 w,b 进行更新时,所有的错误分类点都参与了计算。在实际运用时,也可以只随机地选取一个错误分类点 (xi,yi)w,b 进行更新(这就是 随机梯度下降法 ),即对参数 w,b 采用下面的迭代策略 :
{wnewwold+μyixibnewbold+μyi

4.2.1. 感知器参数 w,b 的迭代过程演示

在图 2 中,假设虚线是对参数 w,b 进行 t 次迭代后得到的方程: x(1)+x(2)0.5=0 ,即有 w(t)=(11),b(t)=0.5
图中,训练集中有两个点被错误地分类 (x,y)=((0.4,0.05)T,+1)(x,y)=((0.2,0.75)T,1) ,所以我们还需要进一步迭代 w,b ,设步长 μ=0.7 ,则有:
{w(t+1)=w(t)+0.7(+1)(0.40.05)+0.7(1)(0.20.75)=(1.420.51)b(t+1)=b(t)+0.7(+1)+0.7(1)=0.5
所以,更新后得到的新的方程(图中的实线)为: 1.42x(1)+0.51x(2)0.5=0 ,至此,所有的点都被正确地分类,算法结束。

perceptron_w_b.png

Figure 2: 感知器参数 w,b 的迭代过程

注:上面实例摘自:Pattern Recognition, 4th, by Sergios Theodoridis, Section 3.3 The Perceptron Algorithm

4.3. 感知器算法描述

前面已经完整地介绍了感知器算法,现在总结如下。

感知器学习算法的原始形式:
感知器模型: y=f(x)=sign(wx+b)={+1ifwx+b>01otherwise
输入:线性可分的训练数据集 T={(x1,y1),(x2,y2),,(xN,yN)} ,其中 xiRn,yi{+1,1},i=1,2,,N ,学习率 μ(0<μ1)
输出:感知器模型参数 w,b
w,b 的求解过程如下:
(1) 选取初值 w0,b0
(2) 在训练数据集中选取数据 (xi,yi)
(3) 如果 yi(wxi+b)0 (即它是一个错误分类点),则按下面方法更新 w,b
{ww+μyixibb+μyi
(4) 转至(2),直到没有错误分类点。

说明:上面算法,在某一次具体的迭代中,没有让所有的错误分类点都参与迭代,即没有采用式子 {wnewwold+μxiMyixibnewbold+μxiMyi ,而是随机选取一个错误分类点参与迭代,这样实现更简单。

4.4. 感知器算法应用实例(利用训练数据集求出模型的参数)

实例:假设训练数据集有两个正实例点(应该分到+1 类的点)A、B分别为: x1=(3,3)T,x2=(4,3)T ,和一个负实例点(应该分到-1 类的点)C为: x3=(1,1)T ,利用感知器学习算法的原始形式求感知器模型。
解:
(1) 取学习率 μ=1 ,参数 w0,b0 分别取初值 (0,0)T,0
(2) 对于正实例点 A,计算得 yi(w0xi+b0)=0 ,故它没有被正确地分类,更新 w,b
{w1w0+1×(+1)×(3,3)T=(3,3)Tb1b0+1×(+1)=1
(3) 对于正实例点 A、B,计算得 yi(w1xi+b1)>0 被正确分类,不用更新 w,b ,对于负实例点 C,计算得 yi(w1xi+b1)<0 ,故它没有被正确地分类,更新 w,b
{w2w1+1×(1)×(1,1)T=(2,2)Tb2b1+1×(1)=0
如此继续下去,直到得到 w7=(1,1)T,b7=3
具体迭代过程如下:

Table 1: 感知器参数迭代求解过程
迭代次数 错误分类点 w b wx+b
0   (0,0)T 0 0
1 A (3,3)T 1 3x(1)+3x(2)+1
2 C (2,2)T 0 2x(1)+2x(2)
3 C (1,1)T -1 x(1)+x(2)1
4 C (0,0)T -2 -2
5 A (3,3)T -1 3x(1)+3x(2)1
6 C (2,2)T -2 2x(1)+2x(2)2
7 C (1,1)T -3 x(1)+x(2)3
8 Nil      

此时,对 A、B、C 三个实例点都有 yi(w7xi+b7)>0 ,没有错误分类点,损失函数达到最小。
所以,我们得到的分离超平面为:
x(1)+x(2)3=0
感知器模型为:
f(x)={+1ifx(1)+x(2)3>01otherwise

perceptron_example.png

Figure 3: 不同的迭代策略可能得到不同的感知器模型

上面的迭代过程中,错误分类点先后取的是 A、C、C、C、A、C、C;在迭代过程中,还可以依次取错误分类点 A、C、C、C、B、C、C、C、A、C、C,那么得到的分离超平面为: 2x(1)+x(2)5=0
可见, 采用不同的初值,或当存在多个错误分类点时采用不同策略选取错误分类点来更新参数,感知机学习算法得到的解可能不同。

4.5. 感知器算法的收敛性

Novikoff 于 1962 年证明了感知机算法的收敛性。 即对于线性可分的数据,利用感知器算法经过有限次迭代,一定可以得到训练数据集的分离超平面。 其具体证明过程可以参考:《统计学习方法, 李航著》

5. 感知器推广

前面介绍的感知器只能把完全线性可分的数据分为两个种类。

袋式算法(Pocket Algorithm)可以处理线性不可分的数据集。
Kesler 结构把感知器推广到了“多个种类”的分类问题。

6. 感知器表示神经元

感知器可以形象地表示为图 4 所示(图中偏置 b 有时也写为 w0 ,右子图中,把激活函数(Activation function) f 运算整合到了一起),这就是神经元(Neuron)的基本模型。

perceptron_neuron.png

Figure 4: 感知器可以表示神经元

7. 感知器算法的对偶形式

感知器的基本知识点已经介绍完了,下面介绍感知器算法的对偶形式。它是感知机算法原始形式的另外一种表达形式,之所以介绍它是因为它有一个特点——“训练感知器模型时只要用到训练数据集实例间的内积形式”,利用这个特点,我们可以把 Kernel Method 应用到感知器(这又称为Kernel perceptron ),使感知器能够处理线性不可分数据。(说明:本文仅仅简单地介绍感知器算法的对偶形式,并不会介绍 Kernel perceptron)。

说明:在 约束 最优化问题中,我们有时通过求解其“拉格朗日对偶问题”来求解原问题。但感知器是无约束最优化问题(由前面的介绍可知,感知器的损失为: L(w,b)=xiMyi(wxi+b) ,并没有其他约束条件),因而感知器损失优化问题并没有对应的“拉格朗日对偶问题”存在。所以感知器算法的“对偶形式”仅仅是感知机算法原始形式的另外一种表达形式,并不是感知器“拉格朗日对偶问题”的解的形式。

7.1. 感知器算法对偶形式

在感知器算法的原始形式中,不失一般性,可以假设 w,b 的初始值都是 0。对于某一个错误分类点 (xi,yi) 来说,它会以下面的公式来更新参数 w,b :
{ww+μyixibb+μyi
假设这个错误分类点在更新 w,b 时一共被使用了 ki 次,则错误分类点 (xi,yi) 对参数 w,b 的贡献为 kiμyixi 。如果记 αi=kiμ0 ,则每个训练数据对参数 w,b 的贡献可以记为 αiyixi 的形式,从而参数 w,b 可以由下式得到:
{w=i=1Nαiyixib=i=1Nαiyi
其中,αi0,i=1,2,,N, N 为训练数据的总数。

利用上面的结论,我们把感知器算法的原始形式表述为下面形式(即感知器算法的对偶形式)。
感知器学习算法的对偶形式描述如下:
感知器模型:
f(x)=sign(wx+b)=sign(w,x+b)=sign(i=1Nαiyixi,x+b)=sign(i=1Nαiyixi,x+b)
输入:线性可分的训练数据集 T={(x1,y1),(x2,y2),,(xN,yN)} ,其中 xiRn,yi{+1,1},i=1,2,,N ,学习率 μ(0<μ1)
输出:感知器模型参数 α=(α1,α2,,αN)T,b
α,b 的求解过程如下:
(1) α=(α1,α2,,αN)T(0,0,,0)T,b0
(2) 在训练数据集中选取数据 (xi,yi)
(3) 如果 yi(j=1Nαjyjxj,xi+b)0 (即它是一个错误分类点),则按下面方法更新 αi,b
{αiαi+μbb+μyi
(4) 转至(2),直到没有错误分类点。

7.2. 感知器算法对偶形式的特点

感知器算法的对偶形式中,训练数据仅以“内积”的形式(即 xj,xi )出现。 利用这个特点我们可以把 Kernel Method 应用到感知器(本文不介绍)。

7.3. Gram Matrix

为了方便使用感知器算法的对偶形式,我们可以提前把训练数据集中所以训练数据间的“内积”计算出来。这个矩阵就是格拉姆矩阵(Gram Matrix)。

对于 n 个向量 x1,x2,,xn, 它对应的 Gram Matrix 定义为:
G=(x1,x1x1,x2x1,xnx2,x1x2,x2x2,xnxn,x1xn,x2xn,xn)

显然,Gram Matrix 是一个对称矩阵(因为 xi,xj=xj,xi )。

7.3.1. Gram Matrix 计算实例

x1=(3,3)T,x2=(4,3)T,x3=(1,1)T ,计算它的 Gram Matrix。

直接套用 Gram Matrix 定义式,可得:
G=(x1,x1x1,x2x1,x3x2,x1x2,x2x2,x3x3,x1x3,x2x3,x3)=(1821621257672)

7.4. 实例:感知器算法对偶形式

实例(这个例子的数据集和前面介绍感知器算法原始形式时的例子是相同的):假设训练数据集有两个正实例点(应该分到+1 类的点)A、B分别为: x1=(3,3)T,x2=(4,3)T ,和一个负实例点(应该分到-1 类的点)C为: x3=(1,1)T ,利用感知器学习算法的对偶形式求感知器模型。
解:
(1) 取 α1=α2=α3=0,b=0,μ=1
(2) 计算数据集对应的 Gram 矩阵:
G=(1821621257672)
(3) 随机选择一个点 xi ,判断 yi(j=13αjyjxj,xi+b)0 是否成立,如果成立(说明它是一个错误分类点),则按下面方法更新 αi,b
{αiαi+1bb+yi
反复迭代,直到没有错误分类点。具体迭代过程(共迭代了 7 次)如表 2 所示。

Table 2: 感知器算法对偶形式参数求解迭代过程
  0 1 2 3 4 5 6 7
    x1 x3 x3 x3 x1 x3 x3
α1 0 1 1 1 2 2 2 2
α2 0 0 0 0 0 0 0 0
α3 0 0 1 2 2 3 4 5
b 0 1 0 -1 0 -1 -2 -3

(4) 由计算出来的 α1=2,α2=0,α3=5,b=3 ,可得 w=i=13αiyixi=2x1+0x25x3=(1,1)T ,从而感知器为:
f(x)=sign(x(1)+x(2)3)

Author: cig01

Created: <2015-06-06 Sat>

Last updated: <2017-12-23 Sat>

Creator: Emacs 27.1 (Org mode 9.4)