模式识别-第2章 线性判别函数_第二讲.ppt

《模式识别-第2章 线性判别函数_第二讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性判别函数主要内容回顾：线性空间、线性判别函数矩阵分析简介例:求二次型对t的导数其中是n维函数向量是数字矩阵矩阵微分——相对于数量变量的微分例：求函数对的导数矩阵微分——相对于向量变量的微分1，数量函数的导数例：a）行向量对的导数b）列向量对的导数c）二次型对的导数d）数量函数对的导数矩阵微分——相对于向量变量的微分2，函数向量的导数矩阵微分——复合函数微分1，数量函数的求导公式矩阵微分——复合函数微分2，向量函数的求导公式5.2线性判别函数的学习问题的提出：假设有一个包含n个样本的集合y1,y

2、2,…,yn,一些标记为ω1,另一些标记为ω2，用这些样本来确定一个判别函数g(y)=aty的权矢量a。在线性可分的情况下，希望得到的判别函数能够将所有的训练样本正确分类；线性不可分的情况下，判别函数产生错误的概率最小。训练样本的规范化非规范化：规范化：解区域的几何解释(特征空间中）特征空间中：矢量a是垂直于分类界面的矢量：解区域的几何解释(权空间中）权空间中，atyi=0是一个通过原点的超平面，yi是法向量，而a是空间中一个点。边沿裕量b一般求解方法—梯度下降法求解不等式组采用的最优化的方法：定义一个

3、准则函数J(a)，当a是解向量时，J(a)为最小；采用最优化方法求解标量函数J(a)的极小值。最优化方法采用最多的是梯度下降法，设定初始权值矢量a(1)，然后沿梯度的负方向迭代计算：其中η(k)称为学习率，或称步长。一般求解方法—梯度下降法2.3感知器算法(Perceptron)最直观的准则函数定义是最少错分样本数准则：JN(a)=样本集合中被错误分类的样本数；感知器准则以错分样本到判别界面距离之和作为准则：感知器算法(批量调整版本)begininitialize,,θ,k0dokk+1untilr

4、eturnaend感知器算法(固定增量单样本感知器)begininitialize,k0dok(k+1)modnifykismisclassifiedbyathenuntilallpatternsproperlyclassifiedreturnaend例有两类模式的训练样本：ω1：{(1,1),(0,1)}ω2：{(-1,0),(0,-1)}用感知器算法求取判别函数，将两类样本分开。初始权矢量为，第1维为偏置，学习率例2有两类模式的训练样本：ω1：{(1,1),(2,2)}ω2：{(0,0),(1,

5、0)}用感知器算法求取判别函数，将两类样本分开。初始权矢量为，第1维为偏置，学习率感知器算法收敛定理如果训练样本线性可分，固定增量算法给出的权向量序列必定终止于某个解向量每次校正，都使权向量更靠近解区域如果是解向量，随着训练样本的增加有：为错分样本设是解向量则，令为一比例因子，有：感知器算法收敛定理设每次校正后，从到的平方距离减少了感知器算法收敛定理每次校正后，从到的平方距离减少了经过k步校正后经过不超过k0步校正后，校正终止与解向量最接近正交的样本（收敛的难点）感知器算法的特点当样本线性可分情况下，学

6、习率合适时，算法具有收敛性；收敛速度较慢；当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分。感知器算法推广引入边沿裕量引入变增量准则函数的推广感知器算法推广引入边沿裕量比b:感知器算法推广引入变增量可以证明：当样本为线性可分时，如果：则收敛于一个解向量对所有i满足为常数或感知器算法(带裕量，变增量单样本调整)begininitialize,b，，k0dok(k+1)modnifthenuntilallpatternsproperlyclassifiedreturnaend感知器算法推广

7、准则函数的推广错误分类点数感知器判据平方误差判据规范化平方（裕量）误差判据不连续梯度不连续梯度连续克服边界点及

8、

9、y

10、

11、的影响松弛算法松弛算法（relaxationprocedure）规范化平方（裕量）误差判据为满足的样本集当为空时，定义松弛算法(单样本裕量)begininitialize,b，，k0dok(k+1)modnifthenuntilallpatternsproperlyclassifiedreturnaend松弛算法(单样本裕量)——几何解释：到超平面的距离：超平面的单位法向量将移往超

12、平面，移动量为从到超平面距离乘以一个因子松弛算法(单样本裕量)——几何解释过松弛算法(单样本裕量)——几何解释过松弛算法(单样本裕量)——收敛性如果是解区域中的向量，那么每个都更接近如果是解区域中的向量，那么每个都更接近当时，有:在k趋向无穷大时，达到有限值：线性判别问题小结迭代方法：选择适当的曲面J(a)，从曲面上的任一点起始找到合适的路径到达解a。J(a)的求解:梯度下降和牛顿下降问题：已知样本集，求权矢量a，即分类界面J(a)的形式：