模式识别-线性判别函数

模式识别原理华中科技大学图像识别与人工智能研究所2022/12/151线性判别函数

问题描述线性判别函数

如下图:三类的分类问题,它们的边界线就是一个判别函数判别函数包含两类:线性判别函数:线性判别函数广义线性判别函数(所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数)分段线性判别函数非线性判别函数线性分类器的三种典型方法以Fisher准则为代表的传统模式识别方法以感知准则函数为代表的机器自学习方法以支持向量机为代表的统计学习理论。分段线性判别函数:近邻法2022/12/1542022/12/1552022/12/156判别函数的形式模式的特征矢量：判别函数：称为权矢量或系数矢量判别函数的形式增广特征矢量：增广权矢量：判别函数：两类问题线性判别准则决策规则:线性分类器的分类界面分类界面的几何解释线性分类界面H是d维空间中的一个超平面；分类界面将d维空间分成两部分，R1，R2分别属于两个类别；判别函数的权矢量w是一个垂直于分类界面H的矢量，其方向指向区域R1

；偏置w0与原点到分类界面H的距离有关：多类问题（情况一）每一类模式可以用一个超平面与其它类别分开；这种情况可以把c个类别的多类问题分解为c个两类问题解决，需要c个线性分类界面；第i类与其它类别之间的判别函数：（1）二分法多类问题（情况一）判别规则若存在i，使得gi(x)>0，gj(x)<0，j≠i，则判别x属于ωi类；其它情况，拒识。多类问题（情况二）每两个类别之间可以用一个超平面分开；c个类别的问题需要c(c-1)/2个线性分类界面；第i类与第j类之间的判别函数为：多类问题（情况二）判别准则如果对任意j≠i

，有gij(x)≥0

，则决策x属于ωi。其它情况，则拒识。结论：判别区间增大，不确定区间减小IR（2）ωi/ωj二分法多类问题（情况三）情况三是情况二的特例，不存在拒识区域。多类问题（情况三）判别函数c个类别需要c个线性函数：判别准则：（3）最大判别准则结论：无不确定区间例：假设判别函数为：问属于哪一类。解：所以三种方法小结分类方法判别函数个数不确定区难易ωi/ωi二分法ωi/ωj二分法最大判别准则MM(M-1)/2M最多较少没有较难较易较易2022/12/1525判别函数的几何意义2022/12/1526Fisher准则的基本原理2022/12/1527基本参量的定义2022/12/1528基本参量的定义2022/12/1529Fisher线性判别

Fisher线性判别

Fisher线性判别

Fisher线性判别

Fisher线性判别

2022/12/1535Fisher线性判别

2022/12/15372022/12/15382022/12/15392022/12/1540两个问题：（1）构造准则函数（2）如何最快地搜索到使准则函数取极小值的解线性判别函数的学习

问题的提出：假设有一个包含n个样本的集合y1,y2,…,yn,一些标记为ω1,另一些标记为ω2，用这些样本来确定一个判别函数g(x)=atx的权矢量a。在线性可分的情况下，希望得到的判别函数能够将所有的训练样本正确分类；线性不可分的情况下，判别函数产生错误的概率最小。训练样本的规范化非规范化：规范化：最优问题的求解：（1）一个适当的代价函数（准则函数）（2）一个优化算法梯度下降法一次准则函数及梯度下降法

(GradientDescentAlgorithm)感知准则函数（Rosenblatt）

可微函数在某点的梯度是一个向量函数在该点的变化率最大的方向函数的梯度向量定义为

梯度下降法的迭代公式为：

任给定初始权矢量，第k+1次迭代时的权矢量等于第k次的权矢量加上被w（k）错分的样本之和乘以某个系数。

批量修正准则函数的梯度：将梯度下降法应用到一次准则函数中感知器算法把样本集看成不断出现的序列逐一考虑，称为单样本修正法。且令，称为固定增量法。若使得+-+-感知器算法(PerceptronApproach)

算法思想任选一初始增广权矢量用训练样本检验用分类正确否对进行校正对所有训练样本都能正确分类？ENDYesYesNoNo一、感知器算法算法步骤：增广的训练样本集每个类别已知，（1）令步数k=1,增量为正的常数，的各分量为较小的任意值（2）输入训练模式，计算判别函数值（3）调整增广权矢量，规则：（a）如果

（b）如果（c）如果（4）如果k<N，令k=k+1，GOTO（2）如果k=N，则检验对所有训练样本是否都正确分类，是则结束，否则，令k=1，GOTO（2）一、感知器算法收敛定理：如果训练模式是线性可分的，感知器训练算法在有限次迭代后可以收敛到正确的解矢量证明：。。。。。。

一、感知器算法感知器算法在多类问题中的运行步骤：增广的训练样本集每个类别已知，（1）令步数k=1,增量为正的常数，C个权矢量赋任意初值（2）输入符号未规范化的增广训练模式，计算C个判别函数值（3）调整增广权矢量，规则：（a）如果

（b）如果

（4）如果k<N，令k=k+1，GOTO（2）如果k=N，则检验对所有训练样本是否都正确分类，是则结束，否则，令k=1，GOTO（2）感知器算法(批量调整版本)begininitialize,,θ,k0do

kk+1

untilreturnaend例有两类模式的训练样本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用感知器算法求取判别函数，将两类样本分开。解：(1)训练样本分量增广化及符号规范化：

(2)给增广权矢量赋任意初值，取增量=1，57例题:已知训练样本(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,

这里的下标恰是所属类别，各类样本不需符号规范化。58例题:已知训练样本(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)T59例题:已知训练样本(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)T60例题:已知训练样本(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)T61例题:已知训练样本(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-2二次准则函数及其解法

问题：

一次准则函数及其算法（如感知器算法）只适用于线性可分的情况，如果是线性不可分的，分类过程将不收敛?

能否找到一种算法，使之能够测试出模式样本集是否线性可分，并且对线性不可分的情况也能给出“次最优”的解？

如果训练模式是线性不可分不等式组是不一致的，不等式组没解。此时，目标最少的训练模式被错分。（一）最小错分模式数目准则

对线性不可分样本集，求一解矢量使得错分的模式数目最少。

对于两类问题，设n+1维增广训练模式已符号规范化。

如果训练模式是线性可分的，则存在权矢量使不等式组成立。式中是矩阵。

将上面的不等式组写成矩阵方程形式，并引入N

维余量矢量，于是不等式方程组变为（二）最小方差准则及W-H算法

针对方程组,构造方差准则函数

对于,此时的,而对于,此时的。如果方程组有唯一解,说明训练模式集是线性可分的,如果方程组无解,极小点值是最小二乘解。一般情况下使极小等价于误分模式数目最少。

⑴伪逆法

求对的梯度并令其为零，有可得(3-6-12)

当(X’X)-1存在时，

X+=(X’X)-1X’称为X的伪逆(也称广义逆或M-P逆)， 称为的伪逆解。

X’X是(n+1)×(n+1)矩阵，一般是非奇异的。 当(X’X)-1不存在时，可用广义逆法解 这里(X

’X)+为X’X的广义逆矩阵。求解最佳权矢量的方法：⑵梯度法由前述知，的梯度为梯度下降算法迭代公式为Step1.任取Step2.(3-6-13)可以证明，当为任意正的常数，

则该算法使权矢量序列收敛于;满足，也称为MSE解。

此算法的两个性质:1.当时,MSE解等价于Fisher解。

2.令,在样本数时,MSE解以最小均方误差逼近贝叶斯判决函数Step1.任取Step2.此算法通常称为W－H(Widrow－Hoff)算法仿前采用单样本修正法，则式(3-6-