感知器算法

3.2感知器算法,感知器(Perception)是一个具有单层计算单元的人工神经网络，感知器训练算法就是由这种神经网络演变而来的。一、感知器的概念美国学者F.Rosenblatt于1957年提出了感知器的模型（如下图）：,3.2感知器算法,感知器实质上是一种神经元模型，是一个多输入/单输出的非线性器件。其中，为阈值，为输入，为输出：而且f为一阶跃函数，即：,3.2感知器算法,3.2感知器算法,若令：则：由此可见，它可作为一个分类器，解决两类的分类问题。即：若：则,3.2感知器算法,二、感知器训练算法步骤分别属于或,为确定,执行：给定初始值：赋任意较小的值，选择常数c0;(2)输入训练样本;(3)计算判决函数的值：(4)修正加权向量，修正规则为：,3.2感知器算法,若和，则：若和，则：如果的训练样本的各分量均乘以了(-1)，则修正规则统一为：若，则:,3.2感知器算法,(5)令,返回(2),直到W对所有的训练样本均稳定不变结束。注：c取值选择。通常选择,c值大小会影响收敛的速度和稳定性。算法的物理意义：,+,-,+,-,例3.1：已知两类模式的训练样本（如图）：试用感知器算法求分界面。,接上页,接上页,例3.2：有两类样本1=（x1,x2）=(1,0,1),(0,1,1)2=（x3,x4）=(1,1,0),(0,1,0)解：先求四个样本的增值模式x1=(1,0,1,1)x2=(0,1,1,1)x3=(1,1,0,1)x4=(0,1,0,1)假设初始权向量w(0)=(1,1,1,1)c=1第一次迭代：W(0)Tx1=(1,1,1,1)(1,0,1,1)T=30所以不修正W(0)Tx2=(1,1,1,1)(0,1,1,1)T=30所以不修正W(0)Tx3=(1,1,1,1)(1,1,0,1)T=30所以修正w1W(1)=w(0)-x3=(0,0,1,0)W(1)Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2W(2)=w(1)-x4=(0,-1,1,-1)第一次迭代后,权向量W(2)=(0,-1,1,-1),再进行第2,3,次迭代如下表,直到在一个迭代过程中权向量相同，训练结束。W*=W(5)=(0,1,3,0)判别函数g(x)=-x2+3x3注：感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点。,三、收敛性定理定理：若训练样本是线性可分，则感知器训练算法在有限次迭代后可以收敛到正确的解向量。证明：为了证明该定理，假定：第一，对每一个训练样本都进行归一化处理，变成单位向量，即：;第二，取c=1，W(0)=0;第三，变更感知器训练算法如下：置k=0,W(0)=0,c=1,给较小的正数T，并取00且gj(x)0(j=1,2,c,)，则判：,c类可有c个判别函数，且具有以下性质：,3.4最小平方误差准则函数与H-K算法,把c类问题转化为c个两类问题，分别对c个两类问题进行训练，就可得到c个解向量，进而建立c个判决函数。对两类问题如何选取样本？在除类之外的训练样本中选取适当足够的样本，与的样本一起共同构成训练样本集，利用前面两类问题的H-K算法求解：,3.4最小平方误差准则函数与H-K算法,由训练样本集构成增广矩阵,求伪逆：(2)赋给初值,应使各分量均为正值，选正常数,置;(3)计算：(4)若的负的分量停止变为正或各分量均为负，则线性不可分，中止迭代；否则，若的各,3.4最小平方误差准则函数与H-K算法,量均接近0，即，迭代过程完成，算法结束；否则继续。(5)计算：(6)令，返回(3)在上述算法中，令分别进行c次训练，即可得c个解向量和c个判决函数。,例3：已知三类训练样本试用H-K算法求解向量、。解：,3.5势函数法,特点：可以直接确定判决函数，而且不仅适用于线性分类器，还适合于非线性分类器。基本思想(以两类问题为例)：把类的样本点设想成能源，在该点正电位达到最大值，而随着与该点距离的增大，正电位越来越低。,高,低,低,高,3.5势函数法,同样，把属于类的样本点设想另一种能源，在该点上负电位达到最大值，而随着与该点距离的增大，负电位越来越低。这样，在类型的样本聚集区域形成电位势能的“高地”，而在类型的样本聚集区域形成电位势能的“洼地”。电位为零的等位点的轨迹就可以作为区分界面。,3.5势函数法,一、势函数的概念设表示与之间的电位势函数，它满足三个条件：(1),当且仅当时,达到最大值;(2)当与之间的距离趋近于无穷大时，趋近于0，即：是光滑函数，并且是与之间距离的单调下降函数。,3.5势函数法,积累电位势函数：所有样本点(含的所有点)的电位势函数在任一点产生的电位总和被称为积累电位势函数，表示为。如果能够把样本正确分类，可取为判决函数，即：。的修正：在训练过程中，逐个加入训练样本，根据分类是否正确决定积累电位势函数是否调整。,3.5势函数法,若正确分类，则不变；若错误分类,则被修正。如果所有的训练样本都能被正确分类，稳定不变，则它就是所期望得到的判决函数。这里介绍两类满足条件的电位势函数。第一类势函数：其中在的定义域里是正交函数系。,3.5势函数法,第二类势函数：，且可展成无穷级数，如：(a)(b)(c)(为常数)(可画出在一维特征空间的图像),3.5势函数法,二、训练过程及修正规则：1、修正规则：当输入第k个样本，计算点的积累电位势,修正规则为：(*)定义为：,3.5势函数法,2、势函数法算法步骤：初始化，令；输入样本，取：令，输入样本，计算点的积累电位势函数；