模式识别 一次准则函数及梯度下降法课件

13.5一次准则函数及梯度下降法3.5.1感知器算法(PerceptronApproach)任选一初始增广权矢量用训练样本检验分类是否正确对所有训练样本都正确分类？YesENDYesNo对权值进行校正No感知器算法流程图流程:13.5一次准则函数及梯度下降法3.5.1感知器算法(P23.5一次准则函数及梯度下降法3.5.1感知器算法(PerceptronApproach)23.5一次准则函数及梯度下降法3.5.1感知器算法(P3

(3)调整增广权矢量，规则是

--如果和，则

--如果和，则

--如果和，或和，则

(4)如果k<N，令k=k+1，返至⑵。如果k=N，检验判别函数对是否都能正确分类。若是，结束；若不是,令k=1，返至⑵。3(3)调整增广权矢量，规则是(4)如果4权空间中感知器算法权矢量校正过程示意图)(ikxr+-)(ikxr)(kwr)1(+kwr)(jkxr+-)(jkxr-)(kwr)1(+kwr4权空间中感知器算法权矢量校正过程示意图)(ikxr+-)(5二、收敛定理：

如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正确的解矢量。。证明思路：

如果第k+1次迭代生成的权矢量比第k次迭代生成的权矢量更接近解矢量，则收敛，即：5二、收敛定理：。证明思路：6、

、

6、、7

(1)训练样本分量增广化及符号规范化。7(1)训练样本分量增广化及符号规范化。8

89

91010112.用感知器算法求解向量,训练样本为:w1:{(0,0,0)T,(1,0,0)T,(1,0,1)T,(1,1,0)T}w2:{(0,0,1)T,(0,1,1)T,(0,1,0)T,(1,1,1)T}作业设两类样本的类内离差矩阵分别为:试用Fisher准则求其决策面方程。112.用感知器算法求解向量,训练样本为:作业设两类样本的123.5.2一次准则函数及梯度下降法一、梯度下降法采用梯度下降法沿负梯度方向，选择适当的步长进行搜索，求解函数的极小值点。

第三章判别域代数界面方程法123.5.2一次准则函数及梯度下降法一、梯度下降法131314增广权矢量的修正迭代公式为：令k=1/2，求得准则函数的梯度其中符号函数14增广权矢量的修正迭代公式为：令k=1/2，求得准则函15增广权矢量修正迭代公式：称为单样本修正，实际也可构造批量修正：式中的是被错分类的模式集。15增广权矢量修正迭代公式：称为单样本修正，实际也可构造批量1616173.5.3感知器训练算法在多类问题中的应用判别规则：

对于c类问题，应建立c个判别函数：

di(x)=wi’xi(i=1,2,…,c)

如果xi，则有wi’x>wj’x(ji)

因此判别规则是

若di(x)>dj(x)ji则判xi

第三章判别域代数界面方程法173.5.3感知器训练算法在多类问题中的应用判别规则：18(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，选择正常数，置步数k=1。算法步骤：(2)输入已知类别的增广训练模式xk，计算c个判别函数

di(xk)=wi’xk(i=1,2,…,c)(3)修正权矢量，修正规则是：

if(xki)and(di(xk)>dj(xk))(ji)then

wi(k+1)=wi(k)(i=1,2,…,c)(正确分类)

if(xki)and(di(xk)dl(xk))(li)then

wi(k+1)=wi(k)+xk

wl(k+1)=wl(k)-xk

wj(k+1)=wj(k)(ji,l)18(1)赋初值,分别给c个权矢量wi(i=1,2,…,c19(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，选择正常数，置步数k=1。算法步骤：(2)输入已知类别的增广训练模式xk，计算c个判别函数di(xk)=wi’xk(i=1,2,…,c)(4)ifk<N,令k=k+1,返至⑵；

ifk=N，检验判别函数是否对都能正确分类，若是，结束；否则，令k=1，返至⑵。(3)修正权矢量。19(1)赋初值,分别给c个权矢量wi(i=1,2,…,c20例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

（2）运用感知器训练算法。置k=1，增量=1，赋初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,进行迭代运算：解:（1）训练样本分量增广化。将训练样本变成增广训练模式：x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,

这里的下标恰是所属类别，各类样本不需符号规范化。20例题:已知训练样本(0,0)T1，(1,1)T221例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=1,xk=x11,因为d1(x1)=d2(x1)=0，d1(x1)=d3(x1)=0，错分，所以:w1(2)=w1(1)+x1=(0,0,1)Tw2(2)=w2(1)-x1=(0,0,-1)Tw3(2)=w3(1)-x1=(0,0,-1)Tk=2,xk=x22,因为d2(x2)=-1<d1(x2)=1，d2(x2)=d3(x2)=-1，错分，所以w1(3)=w1(2)-x2=(-1,-1,0)Tw2(3)=w2(2)+x2=(1,1,0)T

w3(3)=w3(2)-x2=(-1,-1,-2)T21例题:已知训练样本(0,0)T1，(1,1)T222例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=3,xk=x33,因为d3(x3)=-2<d1(x3)=0，d3(x3)=d2(x3)=0，错分，所以w1(4)=w1(3)-x3=(0,-2,-1)Tw2(4)=w2(3)-x3=(2,0,-1)T

w3(4)=w3(3)+x3=(-2,0,-1)Tk=4,xk=x11,因为d1(x1)=d2(x1)=-1，d1(x1)=d3(x1)=-1，错分，所以w1(5)=w1(4)+x1=(0,-2,0)Tw2(5)=w2(4)-x1=(2,0,-2)T

w3(5)=w3(4)-x1=(-2,0,-2)T22例题:已知训练样本(0,0)T1，(1,1)T223例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=5,xk=x22,因为d2(x2)=0>d1(x2)=-2，d2(x2)=0>d3(x2)=-4，正确，所以w1(6)=w1(5)=(0,-2,0)Tw2(6)=w2(5)=(2,0,-2)T

w3(6)=w3(5)=(-2,0,-2)Tk=6,xk=x33,因为d3(x3)=0>d1(x3)=-2，d3(x3)=0>d2(x3)=-4，正确，所以w1(7)=w1(6)=(0,-2,0)Tw2(7)=w2(6)=(2,0,-2)T

w3(7)=w3(6)=(-2,0,-2)T23例题:已知训练样本(0,0)T1，(1,1)T224例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=7,xk=x11,因为d1(x1)=0>d2(x1)=-2，d1(x1)=0>d3(x1)=-2，正确，三个权矢量不再变化，因此可以确定所有训练样本均已被正确分类，由此得到三个解矢量：w1*=w1(5)，w2*=w2(5)，w3*=w3(5)同时可得三个判别函数: d1(x)=-2x2 d2(x)=2x1-2 d3(x)=-2x1-224例题:已知训练样本(0,0)T1，(1,1)T2253.5一次准则函数及梯度下降法3.5.1感知器算法(PerceptronApproach)任选一初始增广权矢量用训练样本检验分类是否正确对所有训练样本都正确分类？YesENDYesNo对权值进行校正No感知器算法流程图流程:13.5一次准则函数及梯度下降法3.5.1感知器算法(P263.5一次准则函数及梯度下降法3.5.1感知器算法(PerceptronApproach)23.5一次准则函数及梯度下降法3.5.1感知器算法(P27

(3)调整增广权矢量，规则是

--如果和，则

--如果和，则

--如果和，或和，则

(4)如果k<N，令k=k+1，返至⑵。如果k=N，检验判别函数对是否都能正确分类。若是，结束；若不是,令k=1，返至⑵。3(3)调整增广权矢量，规则是(4)如果28权空间中感知器算法权矢量校正过程示意图)(ikxr+-)(ikxr)(kwr)1(+kwr)(jkxr+-)(jkxr-)(kwr)1(+kwr4权空间中感知器算法权矢量校正过程示意图)(ikxr+-)(29二、收敛定理：

如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正确的解矢量。。证明思路：

如果第k+1次迭代生成的权矢量比第k次迭代生成的权矢量更接近解矢量，则收敛，即：5二、收敛定理：。证明思路：30、

、

6、、31

(1)训练样本分量增广化及符号规范化。7(1)训练样本分量增广化及符号规范化。32

833

93410352.用感知器算法求解向量,训练样本为:w1:{(0,0,0)T,(1,0,0)T,(1,0,1)T,(1,1,0)T}w2:{(0,0,1)T,(0,1,1)T,(0,1,0)T,(1,1,1)T}作业设两类样本的类内离差矩阵分别为:试用Fisher准则求其决策面方程。112.用感知器算法求解向量,训练样本为:作业设两类样本的363.5.2一次准则函数及梯度下降法一、梯度下降法采用梯度下降法沿负梯度方向，选择适当的步长进行搜索，求解函数的极小值点。

第三章判别域代数界面方程法123.5.2一次准则函数及梯度下降法一、梯度下降法371338增广权矢量的修正迭代公式为：令k=1/2，求得准则函数的梯度其中符号函数14增广权矢量的修正迭代公式为：令k=1/2，求得准则函39增广权矢量修正迭代公式：称为单样本修正，实际也可构造批量修正：式中的是被错分类的模式集。15增广权矢量修正迭代公式：称为单样本修正，实际也可构造批量4016413.5.3感知器训练算法在多类问题中的应用判别规则：

对于c类问题，应建立c个判别函数：

di(x)=wi’xi(i=1,2,…,c)

如果xi，则有wi’x>wj’x(ji)

因此判别规则是

若di(x)>dj(x)ji则判xi

第三章判别域代数界面方程法173.5.3感知器训练算法在多类问题中的应用判别规则：42(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，选择正常数，置步数k=1。算法步骤：(2)输入已知类别的增广训练模式xk，计算c个判别函数

di(xk)=wi’xk(i=1,2,…,c)(3)修正权矢量，修正规则是：

if(xki)and(di(xk)>dj(xk))(ji)then

wi(k+1)=wi(k)(i=1,2,…,c)(正确分类)

if(xki)and(di(xk)dl(xk))(li)then

wi(k+1)=wi(k)+xk

wl(k+1)=wl(k)-xk

wj(k+1)=wj(k)(ji,l)18(1)赋初值,分别给c个权矢量wi(i=1,2,…,c43(1)赋初值,分别给c个权矢量wi(i=1,2,…,c)赋任意的初值，选择正常数，置步数k=1。算法步骤：(2)输入已知类别的增广训练模式xk，计算c个判别函数di(xk)=wi’xk(i=1,2,…,c)(4)ifk<N,令k=k+1,返至⑵；

ifk=N，检验判别函数是否对都能正确分类，若是，结束；否则，令k=1，返至⑵。(3)修正权矢量。19(1)赋初值,分别给c个权矢量wi(i=1,2,…,c44例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

（2）运用感知器训练算法。置k=1，增量=1，赋初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,进行迭代运算：解:（1）训练样本分量增广化。将训练样本变成增广训练模式：x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,

这里的下标恰是所属类别，各类样本不需符号规范化。20例题:已知训练样本(0,0)T1，(1,1)T245例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=1,xk=x11,因为d1(x1)=d2(x1)=0，d1(x1)=d3(x1)=0，错分，所以:w1(2)=w1(1)+x1=(0,0,1)Tw2(2)=w2(1)-x1=(0,0,-1)Tw3(2)=w3(1)-x1=(0,0,-1)Tk=2,xk=x22,因为d2(x2)=-1<d1(x2)=1，d2(x2)=d3(x2)=-1，错分，所以w1(3)=w1(2)-x2=(-1,-1,0)Tw2(3)=w2(2)+x2=(1,1,0)T

w3(3)=w3(2)-x2=(-1,-1,-2)T21例题:已知训练样本(0,0)T1，(1,1)T246例题:已知训练样本(0,0)T1，(1,1)T2，(-1,1)T3,

试求解向量w1、w2和w3。

k=3,xk=x33,因为d3(x3)=-2<d1(x3)=0，d3(x3)=d2(x3)=0，错分，所以w1(4)=w1(3)-x3=(0,-2,-1)Tw2(4)=w2(3)-x3=(2,0,-1)T

w3(4)=w3(3)+x3=(-2,0,-1)Tk=4,xk=x11,因为d1(x1)=d2(x1)=-1，d1(x1)=d3(x1)=-1，错分，所以w1(5)=w1(4)+x1=(0,-2,0)Tw2(5)=w2(4)-x1=(2,0,-2)T

w3(5)=