哈尔滨工业大学：《模式识别》课程教学资源（讲义）第三章 判别函数分类器

第三章判别函数分类器 经过特征抽取之后,一个模式可以用n维特征空间中的一个点X来表示,当特征选择 适当时,可以使同一类模式的特征点在特征空间中某个子区域内分布,另一类模式的特征点 在另一子区域分布(例如苹果和橙子的问题)。这样,我们就可以用空间中的一些超曲面将 特征空间划分为一些互不重叠的子区域,使不同模式的类别在不同的子区域中。这些超曲面 称为判别界面,可以用一个方程来表示:d(X)=0,其中的d(X)是一个从n维空间到 维空间的映射,称为是判别函数( Discriminant function) 在所有的函数形式中,线性函数是一种最简单的形式,下面我们就从线性判别函数入手 来研究判别函数分类器 3.0预备知识 在介绍线性判别函数之前,先来帮助大家复习一下有关于矢量和矩阵的知识 1.矢量 这里的矢量X可以看作是N维欧氏空间中的一个点,用一个列矢量表示: 矩阵 有的时候矩阵可以看作是由若干个矢量构成的: X A是一个MxN的矩阵,其中的X称为是矩阵的行矢量 3.矩阵的秩 矩阵所有行向量中的最大无关组个数称为行秩,矩阵所有列向量中的最大无关组个数称 为列秩。一个矩阵的行秩等于列秩,称为矩阵的秩 4.转置 列矢量W的转置W为一个行矢量,N×M的矩阵A的转置A为一个MxN的矩 阵 5.矢量和矩阵的乘法 设W和X为N维列矢量,A为一个N×M的矩阵。则:

17 第三章 判别函数分类器 经过特征抽取之后，一个模式可以用 n 维特征空间中的一个点 X 来表示，当特征选择 适当时，可以使同一类模式的特征点在特征空间中某个子区域内分布，另一类模式的特征点 在另一子区域分布（例如苹果和橙子的问题）。这样，我们就可以用空间中的一些超曲面将 特征空间划分为一些互不重叠的子区域，使不同模式的类别在不同的子区域中。这些超曲面 称为判别界面，可以用一个方程来表示： d (X) = 0 ，其中的 d (X) 是一个从 n 维空间到一 维空间的映射，称为是判别函数(Discriminant Function)。 在所有的函数形式中，线性函数是一种最简单的形式，下面我们就从线性判别函数入手 来研究判别函数分类器。 3.0 预备知识 在介绍线性判别函数之前，先来帮助大家复习一下有关于矢量和矩阵的知识。 1. 矢量 这里的矢量 X 可以看作是 N 维欧氏空间中的一个点，用一个列矢量表示： 1 2 N x x x     =           X 2. 矩阵 有的时候矩阵可以看作是由若干个矢量构成的： 1 2 T T T M       =         X X A X A 是一个 M N 的矩阵，其中的 T Xi 称为是矩阵的行矢量。 3. 矩阵的秩 矩阵所有行向量中的最大无关组个数称为行秩，矩阵所有列向量中的最大无关组个数称 为列秩。一个矩阵的行秩等于列秩，称为矩阵的秩。 4. 转置 列矢量 W 的转置 WT 为一个行矢量， N M 的矩阵 A 的转置 T A 为一个 M N 的矩 阵。 5. 矢量和矩阵的乘法 设 W 和 X 为 N 维列矢量， A 为一个 N M 的矩阵。则：

1)Wx=∑wx,是一个数值,称为W与X的内积 V1x1w1x2……w1xN 2)wxrw2x1w2x2…w2x ,是一个N×N的矩阵 WNY WNx2 W,u,2 ) WA= ,是一个N维的列矢量 W aiN 6.正交 设W和X为N维列矢量,如果W和X的内积等于零,WX=0,则称W和X正 交,也称W垂直于X。 7.逆矩阵 设A为一个N×N的方阵,A的逆阵用A表示,满足AA=AA=I,I为单位 阵。一个矩阵的逆阵存在条件是,首先是一个方阵,其次是一个满秩矩阵,即矩阵的秩为N 8.矩阵的特征值和特征向量 设A为一个N×N的方阵,如果存在一个数A和一个N维的非零列矢量ξ,使得 1=成立,则称λ为A的特征值,ξ为A属于A的特征向量 一般来说一个矩阵应该有N个特征值(可能相等),对应有N个特征向量 9.矩阵的迹和行列式值 设A为一个NxN的方阵,A的迹为主对角线元素之和:m(A)=∑q:A的行列 式值表示为det(A)。 如果矩阵A有N个特征值,2,…,A,则有m(A)=∑4,deA)=∏ 10.矩阵微分 1)矩阵对数值变量微分 如果矩阵A()=(()的每一个元素a()是变量t的可微函数,则称A(O 可微:

18 1) 1 N T i i i w x = W X =  ，是一个数值，称为 W 与 X 的内积； 2) 1 1 1 2 1 2 1 2 2 2 1 2 N T N N N N N w x w x w x w x w x w x w x w x w x     =           WX ，是一个 N N 的矩阵； 3) 1 1 2 1 1 N i i i N T i i i N i iN i w a w a w a = = =           =                W A ，是一个 N 维的列矢量 6. 正交 设 W 和 X 为 N 维列矢量，如果 W 和 X 的内积等于零， 0 T W X = ，则称 W 和 X 正 交，也称 W 垂直于 X 。 7. 逆矩阵 设 A 为一个 N N 的方阵， A 的逆阵用 −1 A 表示，满足 − − 1 1 AA A A I = = ，I 为单位 阵。一个矩阵的逆阵存在条件是，首先是一个方阵，其次是一个满秩矩阵，即矩阵的秩为 N 。 8. 矩阵的特征值和特征向量 设 A 为一个 N N 的方阵，如果存在一个数  和一个 N 维的非零列矢量 ξ ，使得： Aξ ξ =  成立，则称  为 A 的特征值， ξ 为 A 属于  的特征向量。 一般来说一个矩阵应该有 N 个特征值（可能相等），对应有 N 个特征向量。 9. 矩阵的迹和行列式值 设 A 为一个 N N 的方阵， A 的迹为主对角线元素之和： ( ) 1 N ij i tr a = A =  ； A 的行列 式值表示为 det(A) 。 如果矩阵 A 有 N 个特征值 1 2 , , ,   N ，则有 ( ) 1 N i i tr  = A =  ， 1 det( ) N i i  = A = 。 10. 矩阵微分 1) 矩阵对数值变量微分 如果矩阵 ( ) ( ij ( ))M N t a t  A = 的每一个元素 a (t) ij 是变量 t 的可微函数，则称 A(t) 可微：

da(o d MxN 其结果还是一个M×N的矩阵 2)矩阵函数对矩阵的微分 设X=(x)”MxN元函数f(X)=/(x1,x2…,x12x1,…,xm),定义 f(X)对矩阵X的导数为 MI 其结果是一个M×N的矩阵。 特殊的,函数对一个矢量的微分是一个矢量。 3)常用微分的性质 设X和W是N维的矢量,A是一个MxN维的矩阵 . f(X)=Xw f(x)=w'x. d(x)-w /(x)=xAX, x=(A+AX 31线性判别函数 、两类问题 n维空间中的线性判别函数可以表示为: d(X)=mx+12x2+…+1x+1m=WX0+n 其中X0=(x,x2…,x)为待识模式的特征矢量,W=(m,mn2…,w)称为权矢量 般为了处理方便,我们可以将特征矢量和权矢量改为另外一种方式表示 ⅹ=(x,x2…xn,1)称为增广的特征矢量,W=(1,m2…,n,wn)称为增广的权矢 量。则线性判别函数可以以一种简单的内积形式表示:d(X)=WX。 在二维空间中,判别界面可以用一个直线方程来表示:d(X)=Wx+2x2+y=0

19 ( ) ( ) ij M N d t d a t dt dt    =     A 其结果还是一个 M N 的矩阵。 2) 矩阵函数对矩阵的微分 设 ( ij)M N x  X = ， M N 元函数 f f x x x x x ( ) , , , , , , X = ( 11 12 12 21 mn ) ，定义 f (X) 对矩阵 X 的导数为： 11 1 1 N ij M N M MN f f x x df f d x f f x x               = =                      X 其结果是一个 M N 的矩阵。 特殊的，函数对一个矢量的微分是一个矢量。 3) 常用微分的性质 设 X 和 W 是 N 维的矢量， A 是一个 M N 维的矩阵， i. ( ) T f X X W = ， df ( ) d = X W X ； ii. ( ) T f X W X = ， df ( ) d = X W X ； iii. ( ) T f X X AX = ， ( ) ( ) T df d = + X A A X X 。 3.1 线性判别函数 一、两类问题 n 维空间中的线性判别函数可以表示为： ( 0 1 1 2 2 1 0 0 1 ) T n n n n d w x w x w x w w X W X = + + + + = + + + 其中 0 1 2 ( , , , ) T n X = x x x 为待识模式的特征矢量， 0 1 2 ( , , , ) T W = w w wn 称为权矢量。 一般为了处理方便，我们可以将特征矢量和权矢量改为另外一种方式表示： ( 1 2 , , , ,1) T n X = x x x 称为增广的特征矢量， ( 1 2 1 , , , , ) T W = w w w wn n+ 称为增广的权矢 量。则线性判别函数可以以一种简单的内积形式表示： ( ) T d X W X = 。 在二维空间中，判别界面可以用一个直线方程来表示： ( ) 1 1 2 2 3 d w x w x w X = + + = 0 ；

在三维空间中,判别界面为一个平面;在高维空间中,判别界面为一个超平面 当我们已知线性判别函数的权矢量W时,可以构造这样一个分类器: >0.X∈ d(x)=wX<0, XeQ =0,拒识 但模式X处在分类界面上时,d(X)=0,这是一种极端情况,可以采用两种办法来处 理,一种是认为它既不属于Ω1类,也不属于92,拒绝识别:另一种办法是认为X∈91。 对于线性判别函数来说,权向量在线性空间中是一个垂直于分类界面的矢量 、多类问题 设有M个类别Ω21,92,…1,模式X为n维空间中的矢量 情况一:每一类模式可以用一个超平面与其它类别分开,即可用线性判别函数将属于Ω,和 不属于Ω类的模式(记为Ω2.)分开。这种情况可以把M个类别的多类问题分解为M个两 类问题解决,需要M个判别函数。此时判别函数为 d, (X)=W'x==o, XEs. <0.Xg 例如在二维空间中的三类问题,判别函数分别为 d1(X)=-x+x2,d2(X)=x+x2-5,d3(X)=-x2+1 分类器可以按照如下规则设计: 当d(X)≥0,而d2(X)<0且d3(X)<0时,判别X∈92 当d2(X)20,而d1(X)<0且d3(X)<0时,判别X∈92;

20 在三维空间中，判别界面为一个平面；在高维空间中，判别界面为一个超平面。 当我们已知线性判别函数的权矢量 W 时，可以构造这样一个分类器： ( ) 1 2 0, 0, 0, T d    =     = X X W X X 拒识 但模式 X 处在分类界面上时， d (X) = 0 ，这是一种极端情况，可以采用两种办法来处 理，一种是认为它既不属于 1 类，也不属于 2 ，拒绝识别；另一种办法是认为 X1。 对于线性判别函数来说，权向量在线性空间中是一个垂直于分类界面的矢量。 二、多类问题 设有 M 个类别 1 2 , , ,   M ，模式 X 为 n 维空间中的矢量。 情况一：每一类模式可以用一个超平面与其它类别分开，即可用线性判别函数将属于 i 和 不属于 i 类的模式（记为 i ）分开。这种情况可以把 M 个类别的多类问题分解为 M 个两 类问题解决，需要 M 个判别函数。此时判别函数为： ( ) 0, 0, T i i i i d   = =    X X W X X 例如在二维空间中的三类问题，判别函数分别为： d x x 1 1 2 (X) = − + ， d x x 2 1 2 (X) = + −5， d x 3 2 (X) = − +1 类别一 类别二 x1 x2 类别三 IR IR IR IR d3 (X)=0 d2 (X)=0 d1 (X)=0 分类器可以按照如下规则设计： 1. 当 d1 (X)  0 ，而 d2 (X)  0 且 d3 (X)  0 时，判别 X1 ； 2. 当 d2 (X)  0 ，而 d1 (X)  0 且 d3 (X)  0 时，判别 X2 ；

3.当d3(X)20,而d1(X)0 d13(X)=-1,得d31(X) d2(X)=-1,得d2( 可见d3(X)≥0.,=12,所以可以判别X=(4,3)∈g3。 情况三:在情况一和情况二中都存在着拒识区域。拒识区域的存在,对某些问题来说是必要

21 3. 当 d3 (X)  0 ，而 d1 (X)  0 且 d2 (X)  0 时，判别 X3 ； 4. 其它情况，拒识（对应 IR 区域）。 情况二：每两类之间可以用一个超平面分开，但是不能用来把其余类别分开。这是需要将 M 个类别的多类问题转化为 ( ) 2 1 2 C M M M = − 个  i j 两类问题。判别函数为： ( ) T ij ij d X W X = ，i j M , 1,2, , = ，i j  其中： d d ij ji (X X ) = − ( ) 。分类器可以采用如下规则：如果 ( ) 0 ij d X  ， j i ，则 决策 Xi 。 在这种情况下，同样存在着拒识区域，例如图中的阴影区域， d12 (X)  0 ，d31 (X)  0 ， d23 (X)  0 ，所以它不属于任何一个类别。 类别二 类别三 类别一 d12(X)=0 d13(X)=0 d23(X)=0 + - + - + - 例 3.1：一个三类问题，有三个判别函数： d x x 12 1 3 (X) = − − +5 ， d x 13 1 (X) = − +3，d x x 23 1 2 (X) = − + 现有模式 (4,3) T X = ，判别它属于哪一类？ 带入三个判别函数： d12 (X) = −2 ，得 d21 (X) =  2 0 ； d13 (X) = −1 ，得 d31 (X) = 1 0 ； d23 (X) = −1 ，得 d32 (X) = 1 0 。 可见 3 ( ) 0, 1,2 j d j X  = ，所以可以判别 ( ) 3 4,3 T X =  。 情况三：在情况一和情况二中都存在着拒识区域。拒识区域的存在，对某些问题来说是必要

的,而对某些问题来说是不必要的。情况三是情况二的一个特例,在这种情况下不存在拒识 区域 类别二 类别三 首先我们需要对M个类别分别M个线性函数 d(X)=WX=W1x+12x2+…+12x+1x+),i=1,2,…,M, 然后按照如下的规则作出判别: d(X)=max{a(x)},则Xe9 这样构造的分类器也称为是最大值分类器。它也可以看作是一种特殊形式的情况二的分 类器,第i类与第j类之间的判别函数可以写成: d,(x)=d,(x)-d,(x)=(w-W) 1.…·M,i≠ 实际上,情况三的分类器我们在距离分类器中已经遇到过,使用欧氏距离的独立标准样 本距离分类器就是一个最大值分类器。 有21,92,…,M个类别,其标准样本分别为T1T2,…,TM,我们可以定义第i类 的函数为:d(X)=-d(XT),d(X)经过简化之后可以变为一个线性函数 NxT)=-(-4)=-1x-Ty(x-T 首先考虑到开方的单调性,可以去掉开方,对比较大小不会产生任何影响,则 d,(X)=-(X-T)(X-T)=(X'X-2T'X+T T) 其次考虑到XX在每一类别的判别函数中都存在且相等,也可以简化掉,对比较大小 不会产生影响,则 d(X)=2TXTT=2∑x-∑ 对比一下线性判别函数,令:W=21y,j=1…,N,W0+=∑,则d(X)可

22 的，而对某些问题来说是不必要的。情况三是情况二的一个特例，在这种情况下不存在拒识 区域。 类别二 类别三 类别一 d12(X)=0 d13(X)=0 d23(X)=0 首先我们需要对 M 个类别分别 M 个线性函数： ( ) 1 1 2 2 ( 1) T i i i i iN N i N d w x w x w x w X W X = = + + + + + ，i M =1, 2, , ， 然后按照如下的规则作出判别： ( )  ( ) 1 max i j j M d d   X X = ，则 Xi 。 这样构造的分类器也称为是最大值分类器。它也可以看作是一种特殊形式的情况二的分 类器，第 i 类与第 j 类之间的判别函数可以写成： ( ) ( ) ( ) ( ) T ij i j i j d d d X X X W W X = − = − ，i j M , 1, , = ，i j  。 实际上，情况三的分类器我们在距离分类器中已经遇到过，使用欧氏距离的独立标准样 本距离分类器就是一个最大值分类器。 有 1 2 , , ,   M M 个类别，其标准样本分别为 1 2 , , , T T TM ，我们可以定义第 i 类 的函数为： d d i i (X X T ) = − ( , )， di (X) 经过简化之后可以变为一个线性函数。 ( ) ( ) ( ) ( ) ( ) 1 2 1 2 2 1 , N T i i j ij i i j d d x t = X X T X T X T = − = − − = − − −  首先考虑到开方的单调性，可以去掉开方，对比较大小不会产生任何影响，则： ( ) ( ) ( ) ( 2 ) T T T T i i i i i i d X X T X T X X T X T T = − − − = − − + 其次考虑到 T X X 在每一类别的判别函数中都存在且相等，也可以简化掉，对比较大小 不会产生影响，则： ( ) 2 1 1 2 2 N N T T i i i i ij j ij j j d t x t = = X T X T T = − = −   对比一下线性判别函数，令： 2 w t ij ij = ， j N =1, , ， 2 ( 1) 1 N i N ij j w t + = = − ，则 di (X) 可

以看作是一个线性函数。判别界面也是一个超平面 d(x)=d(x)-d(x)=(T-m)x-2(mrr)=0 其中=TT表示T的模长的平方。分类界面的超平面刚好是垂直于T和T的连 线,并且平分两点之间的连线。(首先垂直于矢量T-T,其次经过点(T+T,))。 经过上述分析我们可以看出,线性分类器可以用于处理线性可分的两类问题或多类问 题,而类别之间的线性可分的条件是:各个类别的区域为互不相交的凸集(如不是凸集,则 包含此集合的最小凸集因满足互不相交) 在线性可分的条件下,都可以用一系列的线性函数实现分类器。这样的线性函数并不是 唯一的,可能存在无穷多个。下面的问题就是如何得到这样一个或一组线性函数,这就是下 面要讨论的线性分类器的训练问题。 32两类别问题线性判别函数的学习 我们先来介绍一种最简单的情况,用线性函数来判别两类问题。 问题的表达 现有M个训练样本,分为两个集合,1类的训练样本集{X,X2…,X}和92类的 训练样本集{XX2…Xn}要求一个向量W,使d(X)=WX能够区分921和2, 即对于X∈g1,有WX≥0:对于X∈Ω,有WX<0,所以有 XW≥0,X2W≥0,…,XW≥0 XW≥0,-X22W≥0.…,-XW≥0 x(+1 L+1)2 L+1)N 写成矩阵形式:XW≥0,其中X称为增广矩阵,0为零矢量 由此可见,求取权向量的问题已经转化为了求解线性不等式组的问题。这个解只有在线 性可分的条件下才存在,并且也不唯一。下面我们介绍几种求解上述线性不等式组的算法。 、感知器算法 求解线性不等式方程组,不可能用一个公式来求得,必须要有一个迭代搜索的过程。下

23 以看作是一个线性函数。判别界面也是一个超平面： ( ) ( ) ( ) ( ) ( ) 1 2 2 0 2 T ij i j i j i j d d d X X X T T X T T = − = − − − = 其中 2 T T T T i i i = 表示 Ti 的模长的平方。分类界面的超平面刚好是垂直于 Ti 和 Tj 的连 线，并且平分两点之间的连线。（首先垂直于矢量 T T i j − ，其次经过点 ( ) 1 2 T T i j + ）。 经过上述分析我们可以看出，线性分类器可以用于处理线性可分的两类问题或多类问 题，而类别之间的线性可分的条件是：各个类别的区域为互不相交的凸集（如不是凸集，则 包含此集合的最小凸集因满足互不相交）。 在线性可分的条件下，都可以用一系列的线性函数实现分类器。这样的线性函数并不是 唯一的，可能存在无穷多个。下面的问题就是如何得到这样一个或一组线性函数，这就是下 面要讨论的线性分类器的训练问题。 3.2 两类别问题线性判别函数的学习 我们先来介绍一种最简单的情况，用线性函数来判别两类问题。 一、问题的表达 现有 M 个训练样本，分为两个集合， 1 类的训练样本集 X X X 1 2 , , , L 和 2 类的 训练样本集 X X X L L M + + 1 2 , , ,  。要求一个向量 W ，使 ( ) T d X W X = 能够区分 1 和 2 ， 即对于 X1 ，有 0 T W X  ；对于 X2 ，有 0 T W X  ，所以有： 1 2 0, 0, , 0 T T T X W X W X W    L 1 2 0, 0, , 0 T T T −  −  −  X W X W X W L L M + + 即： 1 11 12 1 1 1 2 1 ( 1)1 ( 1)2 ( 1) 1 1 2 1 0 1 0 1 0 1 0 T N T L L L LN L T L L L L N L T M M M MN M x x x w x x x w x x x w x x x w + + + + +                               =       − − − − −                          −     − − − −         X X W X X 写成矩阵形式： XW 0  ，其中 X 称为增广矩阵， 0 为零矢量。 由此可见，求取权向量的问题已经转化为了求解线性不等式组的问题。这个解只有在线 性可分的条件下才存在，并且也不唯一。下面我们介绍几种求解上述线性不等式组的算法。 二、感知器算法 求解线性不等式方程组，不可能用一个公式来求得，必须要有一个迭代搜索的过程。下

面先以一种比较直观的方式来介绍一下感知器算法。 首先我们先来看一下分类界面WX=0,分类界面与权矢量W垂直,现在我们要求 W,实际上关心的是它的方向,而不是关心它的长度。其次这个分类界面是一个经过坐标 原点的超平面。如下图所示。 W(k+1 开始的时候,我们不知道w的值是多少,可以先随便设一个不全为零的初始值w(0), 这样可以得到一个初始的分类界面w(0)X=0:然后从训练样本集中拿出一个样本Y进 行训练,将Y带入到辨别函数,计算W(0)Y,如果大于等于0,说明现在的分类界面已 经能够正确分类Y,不需要任何调整,可以从训练样本集中取出下一个样本进行训练,如 果小于0,说明现在的分类界面不能够正确分类Y,需要对分类界面W(0)X=0进行调 整 所谓对分类界面进行调整,就是要调整权向量W(O),我们可以按照下面的方式进行 调整:W()=W(O)+Y,从图中可以看出来新的分类界面W(1)X=0已经能够正确分 类样本Y了。这就是感知器算法的主要思想,如果分类界面能够正确分类当前的训练样本 时,不需要对其进行调整:如果分类错误时,需要进行调整,调整后的权向量是将原来的权 向量与当前的训练样本相加得到的。 图中所表示的情况是经过一次调整,新的分类界面就可以正确分类训练样本,在某些情 况下,只经过一次调整并不一定就能够达到目的,需要多次进行调整,但是如果按照上面的 方法进行调整,总是向着好的方向发展。因为我们可以看到: W(k+l)Y=(w(k)+Y)Y=w(k)Y+Y'Y=w(k)Y+y'2W(k)Y 前面的讨论都是以一种形式化的方式给出了感知器算法的思想,下面我们从一个规范的 数学方法来推导出感知器算法。 首先我们把求解线性不等式组的问题等价为一个最优化的问题,定义一个准则函数:

24 面先以一种比较直观的方式来介绍一下感知器算法。 首先我们先来看一下分类界面 0 T W X = ，分类界面与权矢量 W 垂直，现在我们要求 W ，实际上关心的是它的方向，而不是关心它的长度。其次这个分类界面是一个经过坐标 原点的超平面。如下图所示。 W(k) Y W(k+1) + - + - 开始的时候，我们不知道 W 的值是多少，可以先随便设一个不全为零的初始值 W(0) ， 这样可以得到一个初始的分类界面 (0 0 ) T W X = ；然后从训练样本集中拿出一个样本 Y 进 行训练，将 Y 带入到辨别函数，计算 (0) T W Y ，如果大于等于 0，说明现在的分类界面已 经能够正确分类 Y ，不需要任何调整，可以从训练样本集中取出下一个样本进行训练，如 果小于 0，说明现在的分类界面不能够正确分类 Y ，需要对分类界面 (0 0 ) T W X = 进行调 整。 所谓对分类界面进行调整，就是要调整权向量 W(0) ，我们可以按照下面的方式进行 调整： W W Y (1 0 ) = + ( ) ，从图中可以看出来新的分类界面 (1 0 ) T W X = 已经能够正确分 类样本 Y 了。这就是感知器算法的主要思想，如果分类界面能够正确分类当前的训练样本 时，不需要对其进行调整；如果分类错误时，需要进行调整，调整后的权向量是将原来的权 向量与当前的训练样本相加得到的。 图中所表示的情况是经过一次调整，新的分类界面就可以正确分类训练样本，在某些情 况下，只经过一次调整并不一定就能够达到目的，需要多次进行调整，但是如果按照上面的 方法进行调整，总是向着好的方向发展。因为我们可以看到： ( ) ( ( ) ) ( ) ( ) ( ) 2 1 T T T T T T W Y W Y Y W Y Y Y W Y Y W Y k k k k k + = + = + = +  前面的讨论都是以一种形式化的方式给出了感知器算法的思想，下面我们从一个规范的 数学方法来推导出感知器算法。 首先我们把求解线性不等式组的问题等价为一个最优化的问题，定义一个准则函数：

其中ⅹ是我们已知的,由训练样本集构成的增广矩阵,w是我们所有求的权值向量 当W满足不等式组时,J(WX)达到最小值0。计算J/(WX)对W的偏导数 ow=2(xsgn(w'x)-x) 其中:sgn(Wx)=1wx≥0 . WX<O 安、0W0不可能直接进行求解(解不唯一),但是我们可以采用最优化方法中的梯度下 法来迭代求取W的值。迭代算法可以表示为: w(1)=W w(k+1)=W(k)-C W=w(k 其中W为一个随机的初始值,C为一个常数。 梯度下降法的思路也比较简单,俗称为瞎子下山法,在W(k)这一点上沿着这一点梯 度的正方向前进,可以使J上升的最快,因此,沿着梯度的负方向前进,可以使J下降的 最快。常数C用来控制下降的速度,应该选择一个比较合适的值,太小则收敛速度太慢 太大则容易不收敛。 由于 aW:(Xsgn(W)-xI0, WX20 所以完整的感知器算法如下 1.初始化,置W(1)为一个小的随机数,不能为0矢量 2.在第k步输入训练样本X。,按照如下公式修正权值W W(k+1)、jw(k) w(k)X4≥0 W(k)+CX&, W(k)X<0 3.重复第2步,直到所有训练样本被正确识别 例3.2 可以证明,当训练样本集满足线性可分条件时,感知器算法经过有限步迭代收敛。 、最小均方误差算法LMSE) 感知器算法只有当模式类别线性可分的条件下才能在有限步收敛,在线性不可分的情况 下,算法会来回摆动,始终不收敛。同时在线性可分的情况下,也不可能预先知道达到收敛 所需要的步数。因此,当迭代多次还不收敛时,我们无法判断类别是否线性可分。 下面介绍一种称为最小均方误差法,可以避免上述问题。此方法也称为 Ho-Kashyap算 法(H-K算法)。 首先我们把求解线性不等式组XW≥0的问题等价转换为求解线性方程组XW=B的

25 ( ) ( ) 1 , 2 T T J W X W X W X = − 其中 X 是我们已知的，由训练样本集构成的增广矩阵， W 是我们所有求的权值向量。 当 W 满足不等式组时， J (W X, ) 达到最小值 0。计算 J (W X, ) 对 W 的偏导数： ( ( ) ) 1 sgn 2 J T = −  X W X X W 其中： ( ) 1, 0 sgn 1, 0 T T T   =  −  W X W X W X 0 J = W 不可能直接进行求解（解不唯一），但是我们可以采用最优化方法中的梯度下 降法来迭代求取 W 的值。迭代算法可以表示为： ( ) ( ) ( ) ( ) 0 1 1 k J k k C =  =      + = −        W W W W W W W ， 其中 W0 为一个随机的初始值， C 为一个常数。 梯度下降法的思路也比较简单，俗称为瞎子下山法，在 W(k ) 这一点上沿着这一点梯 度的正方向前进，可以使 J 上升的最快，因此，沿着梯度的负方向前进，可以使 J 下降的 最快。常数 C 用来控制下降的速度，应该选择一个比较合适的值，太小则收敛速度太慢， 太大则容易不收敛。 由于 ( ( ) ) 1 0, 0 sgn 2 , 0 T T T J   = − =   −  W X X W X X W X W X ，所以完整的感知器算法如下： 1. 初始化，置 W(1) 为一个小的随机数，不能为 0 矢量； 2. 在第 k 步输入训练样本 Xk ，按照如下公式修正权值 W： ( ) ( ) ( ) ( ) ( ) , 0 1 , 0 T k T k k k k k k C k   + =   +   W W X W W X W X 3. 重复第 2 步，直到所有训练样本被正确识别。 例 3.2 可以证明，当训练样本集满足线性可分条件时，感知器算法经过有限步迭代收敛。 二、最小均方误差算法(LMSE) 感知器算法只有当模式类别线性可分的条件下才能在有限步收敛，在线性不可分的情况 下，算法会来回摆动，始终不收敛。同时在线性可分的情况下，也不可能预先知道达到收敛 所需要的步数。因此，当迭代多次还不收敛时，我们无法判断类别是否线性可分。 下面介绍一种称为最小均方误差法，可以避免上述问题。此方法也称为 Ho-Kashyap 算 法（H-K 算法）。 首先我们把求解线性不等式组 XW 0 的问题等价转换为求解线性方程组 XW B= 的

问题,其中B=(b,b2…bn),b≥0。一般情况下M>N+1,X为一个Mx(N+1)阶 的长方阵,所以W无解,只能求取一个近似解。 定义一个误差矢量e=XW-B,建立一个优化的准则函数: J(W, B)=5e=lXw-Bl=3(XW-B)(XW-B) 我们所有求的近似解应满足J(WB)=min,即误差矢量的模最小。OJ_=0且 =0是的W即为所求的解向量。先来求J(W,B)对W的梯度: J(W, B)=3(XW-B)(XW-B 5(wX b) (W'X,-b,)X,=X'(XW-B 0,则 X(XW-B)=XXW-XB=0,即:XxW=XB。 其中XX为一个NxN的方阵,当XX非奇异时(当M比较大时,很容易成立) XX)存在,则: 记:x=(xXx)x,称为X的伪逆矩阵。W=XB.X可以通过X计算得到, 现在如果我们知道B,则可求得W。但B也是一个为止变量。下面来求 B ∑(WX-b)=-(XW-B) 如果直接求解=0,则B是W的函数,所以不可能直接求得B和W,还是需要 个迭代算法来求解。下面还是使用梯度下降法来迭代求解B: B(k+1)=B(k)-C B(K)+C(XW-B(k)) 一般来说,我们选择0<C≤1,由于我们的寻优结果需要满足条件:b≥0,i=1,…,M, 而XW-B(k)有可能大于0也可能小于0,所以上述梯度下降法的迭代规则应修改为

26 问题，其中 ( 1 2 , , , ) T M B = b b b ， 0 i b  。一般情况下 M N +1，X 为一个 M N  + ( 1) 阶 的长方阵，所以 W 无解，只能求取一个近似解。 定义一个误差矢量 e XW B = − ，建立一个优化的准则函数： ( ) ( ) ( ) 1 1 1 2 2 , 2 2 2 T J W B e XW B XW B XW B = = − = − − 我们所有求的近似解应满足 J (W B, min ) = ，即误差矢量的模最小。 0 J = W 且 0 J = B 是的 W 即为所求的解向量。先来求 J (W B, ) 对 W 的梯度： ( ) ( ) ( ) ( ) 2 1 1 1 , 2 2 M T T i i i J b = W B XW B XW B W X = − − = −  ( ) ( ) 1 M T T i i i i J b =  = − = −   W X X X XW B W 令： 0 J = W ，则： ( ) 0 T T T X XW B X XW X B − = − = ，即： T T X XW X B = 。 其中 T X X 为一个 N N 的方阵，当 T X X 非奇异时（当 M 比较大时，很容易成立）， ( ) 1 T − X X 存在，则： ( ) 1 T T − W X X X B = 记： ( ) 1 T T −  X X X X = ，称为 X 的伪逆矩阵。  W X B = 。  X 可以通过 X 计算得到， 现在如果我们知道 B ，则可求得 W 。但 B 也是一个为止变量。下面来求 J B ： ( ) ( ) 1 M T i i i J b =  = − − = − −   W X XW B B 如果直接求解 0 J = B ，则 B 是 W 的函数，所以不可能直接求得 B 和 W ，还是需要一 个迭代算法来求解。下面还是使用梯度下降法来迭代求解 B ： ( ) ( ) ( ) 1 ( ) ( ( )) k J k k C k C k =    + = − = + −      B B B B B XW B B 一般来说，我们选择 0 1   C ，由于我们的寻优结果需要满足条件： 0, 1, , i b i M  = ， 而 XW B− (k ) 有可能大于 0 也可能小于 0，所以上述梯度下降法的迭代规则应修改为：