北京大学：《模式识别》课程教学资源（课件讲稿）线性判别函数（第一部分）

1.0引言 分类器 9 第四章线性判别函数 功能结构 92 MAX a(x) 基于样本的Bayes分类 2009-10-27 设计相应 的判别函数。 ■最一般情况下适用的“最 优”分类器：错误幸/风 样本分布的 决策规则： 险最小，对分类器设计 在理论上有指导意义， 训练样本年 统计特征： 判别函数 概率密度函数 决策面方程 获取统计分布及其参数 很困难，实际问题中并 1.0引言 1.1线性判别函数的基本概念 口基于样本的直接确定判别函数方法： 口特点 ■针对各种不同的情况，使用不同的准则函数，设 计出满足这些不同准则要求的分类器。 ■形式最简单 ■这些准则的“最优”并不一定与错误率最小相一致： 次优分类器。 ■容易实现 ■实例：正态分布最小错误率贝叶斯分类器在特殊 ■所需计算量和存储量小 情况下，是线性判别函数gx)尸w(决策面是超 平面)，能否基于样本直接确定w? ■线性判别函数是统计模式识别的基本方法。 选择最佳准则 决策规则 训练样本集 判别酒数 决策面方程 1.1线性判别函数的基本概念 1.1线性判别函数的基本概念 口d维空间中的线性判别函数的一般形式： 口两类问题的分类决策规则 g(x)=g(x)-82() g(x)=w'x+@o; g(x)>0,则决策x∈a, 如果 g(x)<0, 则决策x∈2 其中，x是样本向量，即样本在d维特征空间中 g()=0,可将其任意分类或拒绝 的描述；W是权向量，@是一个常数（闲值权）。 ■gx)=0是分类面（决策面）方程，将特征空间 分成决策区域。 X=[x,x2,x',w=[w,w2,w; ■w是分类面的法向量； ■00是分类面相对于原点的偏移； ■设计线性分类器的关键是给出估计w和w0的准则

第四章 线性判别函数 2009-10-27 2 1.0 引言 基于样本的Bayes分类 器：通过估计类条件概 率密度函数，设计相应 的判别函数。 MAX g1 . . . g2 gc . . . x1 x2 xn a(x)  最一般情况下适用的“最 优”分类器：错误率/风 险最小，对分类器设计 在理论上有指导意义。  获取统计分布及其参数 很困难，实际问题中并 不一定具备获取准确统 计分布的条件。 训练样本集 样本分布的 统计特征： 概率密度函数 决策规则： 判别函数 决策面方程 分类器 功能结构 3 1.0 引言 基于样本的直接确定判别函数方法：  针对各种不同的情况，使用不同的准则函数，设 计出满足这些不同准则要求的分类器。  这些准则的“最优”并不一定与错误率最小相一致： 次优分类器。  实例：正态分布最小错误率贝叶斯分类器在特殊 情况下，是线性判别函数 g(x)=wTx（决策面是超 平面），能否基于样本直接确定w? 训练样本集 决策规则： 判别函数 决策面方程 选择最佳准则 4 1.1 线性判别函数的基本概念  特点  形式最简单；  容易实现；  所需计算量和存储量小；  线性判别函数是统计模式识别的基本方法。 5 1.1 线性判别函数的基本概念  d 维空间中的线性判别函数的一般形式： 其中，x是样本向量，即样本在 d 维特征空间中 的描述；w 是权向量，ω0是一个常数（阈值权）。 0 () ; T g x x   w   12 1 2 , ,... , , ,... ;    T T d d x w   xx x ww w 6 1.1 线性判别函数的基本概念  两类问题的分类决策规则  g(x) = 0 是分类面（决策面）方程，将特征空间 分成决策区域。  w 是分类面的法向量；  ω0 是分类面相对于原点的偏移；  设计线性分类器的关键是给出估计w和ω0的准则。 1 2 ( ) 0, ( ) 0, ( ) 0, g g g             x x x x x 则决策 如果 则决策 可将其任意分类或拒绝 1 2 gg g () () () xxx  

11线性判别函数的基本概念 1.2广义线性判别函数 口线性判别函数的几何意义 口线性判别函数是形式最为简单的判别函数；但是 ■gx)是点x到决策面H的距离的一种代数度量。 它局限性较大，不能用于复杂情况。 方向 ■例：设计一个一维分类器，使其功能为： x=x,+r W g(x)=rlwl: 如果ra 则决策x∈E b≤x≤a 则决策x∈ R1:g>0 ·r是x到H的垂直距离： 一判决函数： ·I,是x在H上的投影向量： g(x)=(x-a(x-b): ·一片是原点到快策面的距离。 一判决规则： R,:g0 则决策xe H:g-0 g(x)≤0，则决策xe, 1.2广义线性判别函数 1.2广义线性判别函数 口对非线性判别函数gx),可通过适当的变换转化 口例：如x=xx了，二次判别函数为 为线性判别函数g(y)。 8(x)=c+Bx+xAx; ■二次判别函数的一般形式 ■定义y=[x,x,x,x,x,则可找到a,ao,使 8(x)=co+cx+cx; 映射X一Y g'(y)=a'y+ao=g(x). 片1「17 「a =x a= = →g)=ay-2ay=8 1.2广义线性判别函数 1.2广义线性判别函数 口任何非线性函数gx)都可通过级数展开转化成高 口一种特殊映射方法：增广样本向量y与增广权 次多项式（逼近），故任何非线性判别函数都可 向量a 转化成广义线性判别函数来处理。 y[-a[], 口问题： L ■实现这种转化的非线性变换可能非常复杂； 口线性判别函数的齐次简化： ■变换空间的维数可能非常高。（维数灾难） g(x)=wx+@o=a'y; ■增广样本向量使特征空间增加了一维，但保持了 样本间的欧氏距离不变，对于分类效果也与原决 策面相同，只是在Y空间中决策面是通过坐标原 点的。 类似于直战方程y一上红☐

7 1.1 线性判别函数的基本概念  线性判别函数的几何意义  g(x) 是点 x 到决策面 H 的距离的一种代数度量。 0 0 , () ; p p r gr r H H r        w xx x w w x x x w 是 到 的垂直距离; 是 在 上的投影向量; 是原点到决策面的距离。 方向 8 1.2 广义线性判别函数  线性判别函数是形式最为简单的判别函数；但是 它局限性较大，不能用于复杂情况。  例：设计一个一维分类器，使其功能为： — 判决函数： — 判决规则： 1 2 b a xb xa x x x          或 则决策 如果 则决策 g( ) ( )( ) x x axb   ； 1 2 ( ) 0, ( ) 0, gx x gx x          则决策 如果 则决策 9 1.2 广义线性判别函数  对非线性判别函数 g(x)，可通过适当的变换转化 为线性判别函数 g’(y)。  二次判别函数的一般形式 3 1 '( ) ( ). T i i i g a y g x   y ay    2 01 2 g( ) x c cx cx   ； 1 10 2 21 2 3 32 y 1 a c y x ac y x ac                     y a ， ； 10 1.2 广义线性判别函数  例：如 x=[x1, x2]T，二次判别函数为  定义 则可找到a，a0，使 ( ) T g x xx x   cB A ； 2 2 1 2 1 2 12 [ , , , , ], T y  x x x x xx 0 '( ) ( ). T g ag y   a y x 11 1.2 广义线性判别函数  任何非线性函数 g(x) 都可通过级数展开转化成高 次多项式（逼近），故任何非线性判别函数都可 转化成广义线性判别函数来处理。  问题：  实现这种转化的非线性变换可能非常复杂；  变换空间的维数可能非常高。（维数灾难） 12 1.2 广义线性判别函数  一种特殊映射方法：增广样本向量 y 与增广权 向量 a  线性判别函数的齐次简化：  增广样本向量使特征空间增加了一维，但保持了 样本间的欧氏距离不变，对于分类效果也与原决 策面相同，只是在Y空间中决策面是通过坐标原 点的。   1,..., ,1 ; 1 T d x x         x y   1 0 0 ,..., , ; T w wd           w a 0 () ; T T g x wx ay    类似于直线方程 y = kx

1.2广义线性判别函数 1.3线性分类器设计步骤 口举例：设在三维空间中一个类别分类问题拟采用 口线性分类器设计任务：给定样本集K,确定线性 二次曲面。如采用广义线性方程求解，试求其广 判别函数gx)=wx的各项系数w. 义样本向量与广义权向量的表达式，及其维数。 口步骤： ■收集一组样本K={,,Xw axi +bxi+cx+drp;+xx;+++h++m= ■按需要确定一个准则函数K,W,其值反映分类 器的性能，其极值解对应于“最好”决策， a=(a.b.c,d.e.f.g,h.l,m)' ■用最优化技术求准则函数J的极值解w*,从而 智 y=(2,2,x,x2,X3x2,,2,1) 确定判别函数，完成分类器设计。 了广义线性 w*=argmaxJ(K,w)方 维数为10 :=g(x)=g'y)=y 判别函数 →对于未知样本x,计算gx),判断其类别。 2.Fisher线性判别(FDA) 2.Fisher线性判别（FDA) 口线性判别函数y=gx)=w: 口图例 ■样本向量x各分量的线性加权； ■样本向量x与权向量w的向量点积； ■如果Iw作1，则视作向量x在向量w上的投影. 口Fisher准则的基本原理：找到一个最合适的投 影轴，使得 ■两类样本在该轴上投影之间的距离尽可能远； ■每一类样本的投影尽可能紧凑； Fisher准则的描述：用投影后数据的统计性质 ◆从而使分类效果为最佳。 均值和离散度的函数作为判别优劣的标准。 2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口符号含义 口d雏空间样本分布的描述量 ■m,m分别表示两类（原始）数据的均值向量； ■各类样本均值向量m ■S,S2分别表示两类（原始）数据的离散度矩阵； ■样本类内离散度矩阵S与总类内离散度矩阵S S=S+S2 ■m,m,分别表示两类（投影后，一维）数据的均 5=(x-mXx-m),i=1.2 5,=P(o)S,+P(@:)S: 值； ■样本类问离散度矩阵了，，=(m-m,m-m ■5，S,分别表示两类（投影后，一维）数据的离 S=P@)P(am-mm-m广 散度 高散度矩阵在形式上与协方差矩阵很相似，但 协方差矩阵是一种期望值，而高散矩阵只是表 示有限个样本在空间分布的高散程度

13 1.2 广义线性判别函数  举例：设在三维空间中一个类别分类问题拟采用 二次曲面。如采用广义线性方程求解，试求其广 义样本向量与广义权向量的表达式，及其维数。 14 1.3 线性分类器设计步骤  线性分类器设计任务：给定样本集 K，确定线性 判别函数 g(x) = wTx 的各项系数 w。  步骤：  收集一组样本 K={x1, x2,…, xN}；  按需要确定一个准则函数 J(K, w)，其值反映分类 器的性能，其极值解对应于“最好”决策。  用最优化技术求准则函数 J 的极值解 w*，从而 确定判别函数，完成分类器设计。 对于未知样本 x，计算 g(x)，判断其类别。 * arg max ( , );  J w w w K 15 2. Fisher线性判别（FDA）  线性判别函数 y = g(x) = wTx ：  样本向量 x 各分量的线性加权；  样本向量 x 与权向量 w 的向量点积；  如果 || w ||=1，则视作向量 x 在向量 w 上的投影。  Fisher准则的基本原理：找到一个最合适的投 影轴，使得  两类样本在该轴上投影之间的距离尽可能远；  每一类样本的投影尽可能紧凑； 从而使分类效果为最佳。 16 2. Fisher线性判别（FDA）  图例 Fisher准则的描述：用投影后数据的统计性质— 均值和离散度的函数作为判别优劣的标准。 17 2. Fisher线性判别（FDA）  符号含义  m1, m2 分别表示两类（原始）数据的均值向量；  S1, S2 分别表示两类（原始）数据的离散度矩阵;  分别表示两类（投影后，一维）数据的均 值；  分别表示两类（投影后，一维）数据的离 散度. 1 2 ~, ~ m m 1 2 S S,   18 2. Fisher线性判别（FDA）  d 维空间样本分布的描述量  各类样本均值向量 mi :  样本类内离散度矩阵 Si 与总类内离散度矩阵Sw:  样本类间离散度矩阵 Sb: 1 1, 2; i i i x i N     x K m ( )( ) , 1, 2; i T i ii i    x x x K S mm 1 2 11 2 2 ; () (); w w P P       S SS S SS 1 21 21 2 1 21 2 ( ) ( )( )( ) ( )( ) ; . T b T b   P P     S m mm m S mmmm 离散度矩阵在形式上与协方差矩阵很相似，但 协方差矩阵是一种期望值，而离散矩阵只是表 示有限个样本在空间分布的离散程度

2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口一维投彩空间(Y空间)样本分布的描述量 口样本x与其投影y的统计量之间的关系： ■各类样本均值： A发三12 ■样本类内离散渡和总类内离散度： =∑wx=wm,i=l2 5=∑0-m,1=1,2 5=+: ■样本类间离散度：S。=(m-m) 5,=(m-m2)2=(wm-w'm) =w (m-m)(m-m2)w=w'S,w; 以上定义描迷d维空间样本点到一个向量投形的分 散情况，因此也就是对时某向量w的投形在w上的 分布。样本离数度的定义与随机变量方差相类似， 2.Fisher?线性判别(FDA) 2.Fisher线性判别（FDA) 口样本x与其投影y的统计量之间的关系： 口评价投影方向w的原则：使原样本向量在该方 S,=∑0y-m 向上的投影能兼顾类间分布尽可能分开，类内样 e到 本投影尽可能密集的要求。 =∑(wx-w'm, 口Fisher准则函数的定义： XEK, 类间离散度☐ 5 =w∑-m,x-m,y Jr(w)=5+5: wS.w wS.w [总类内离散度 -wSw. 口Fisher最佳投影方向的求解： w*=argmaxJ(w). S.=S+S=w(S+S2)w=wS.w. 2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口Fisher准则的合理性 口Fisher最佳投影方向的求解 ■(w)只与投影方向有关，与w大小无关一如 ■求出最佳投影方向上任何一个w即可。 果w是一个最优解，则w也是最优解(k是任 意不为零的常数。) ■(w)有上界，最佳投影方向一定存在！ 口Fisher最佳投影方向的求解要求 J(w)s4(S.) (S)min S=S+S2正定； ■否则，存在投影方向w,使得w'Sw=0: (S)mx,(S)mm分别是矩阵S。,S的最大、最 小特征根。 即，所有数据被投影到一点上！J(w)没有极大 值

19 2. Fisher线性判别（FDA）  一维投影空间(Y空间)样本分布的描述量  各类样本均值：  样本类内离散渡和总类内离散度：  样本类间离散度： 1 , 1, 2; i i i y m yi N      2 ( ) , 1, 2; i i i y S ym i       1 2 ; w S SS     2 1 2 ( ). b S mm      以上定义描述 d 维空间样本点到一个向量投影的分 散情况，因此也就是对某向量 w 的投影在 w 上的 分布。样本离散度的定义与随机变量方差相类似。 20 2. Fisher线性判别（FDA）  样本 x 与其投影 y 的统计量之间的关系： 1 1 , 1, 2; i i T i i T i i y m y i N N        x w x w K  m 2 2 12 1 2 1 21 2 ( )( ) ( )( ) ; b T T T b T T S m m S      w w w w w w m m mmmm    21 2. Fisher线性判别（FDA）  样本 x 与其投影 y 的统计量之间的关系： 2 2 ( ) ( ) ( )( ) ; i i i i y T T i T T i i T i i S S y m                    x x wx wm w x x w w w K K m m   12 12 () . T T w w S S      SS SS   w w w w 22 2. Fisher线性判别（FDA）  评价投影方向 w 的原则：使原样本向量在该方 向上的投影能兼顾类间分布尽可能分开，类内样 本投影尽可能密集的要求。  Fisher 准则函数的定义：  Fisher 最佳投影方向的求解： * arg max ( ). F  J w w w 1 2 () ; T b b F T w S S J S S S    w w w w w    类间离散度 总类内离散度 23 2. Fisher线性判别（FDA）  Fisher 准则的合理性  JF(w) 只与投影方向有关，与 w 大小无关 — 如 果 w 是一个最优解，则 kw 也是最优解（ k 是任 意不为零的常数。）  Fisher 最佳投影方向的求解要求  否则，存在投影方向 w ，使得 即，所有数据被投影到一点上！JF(w) 没有极大 值。 1 2 S SS w   正定； 0 T w w w S  ； 24 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解  求出最佳投影方向上任何一个 w 即可。  JF(w) 有上界，最佳投影方向一定存在！ 分别是矩阵 的最大、最 小特征根。 max min ) () ; ) b F w S J S   w  （ （ max min ), ) b w （ （ S S  b w S S

2.Fisher?线性判别(FDA) 2.Fisher线性判别（FDA) 口Fisher最佳投影方向的求解 口Fisher最佳投影方向的求解 ■因为S正定，一定存在一个最优化的W,满足 ■采用拉格朗日乘子算法解决带约束的最优化： wSw-l: 定义Lagrange函数 L(w,i)=w"S,w-A(w"S.w-I); wS.w ■无约束最优化：max wS.w 令 等价于带约束的最优化 aL(w,》=S,w-2Sw=0, Ow maxwSw,s.l.wS.w=1. 最优解满足：Sw*-Sw*=0, 2.Fisher线性判别(FDA) 2.Fisher线性判别(FDA) 口Fisher最佳投影方向的求解 口Fisher最佳投影方向的求解 根据类间离散度S。的定义： w*=S(m,-m2)=(S+S2)'(m-m2)片 2w*=S-S,w*=Sn-(m,-m2m,-m2)w*, 注意： (m,-m2)了w*是一个数，记作R m1-m,是一个向量，对与(m,m)平行的向量投影 可使两均值，点的距离最远。但是如从使类间分得较 开，同时又使类内密集程度较高这样一个综合指标 W*= m-m,)=S(m,-m, 来看，则需根据两类样本的分布离散程度对投影方 向作相应的调整，这就体现在对mm2向量按S 作一线性变换，从而使Fisher准则函数达到极值，点 被忽略，因为只关心投影方向 2.Fisher?线性判别(FDA) 2.Fisher线性判别(FDA) 口一维分类问题 例：设两类样本的类内离散矩阵分别 ■当d和N很大时，y近似正态分布，可在Y空 为S1,S,各类样本均值分别为 s 间内用Bayes分类器。 m,-(2,0,m,-(2,2y,试用Fisher?准 则求其决策面方程。 s4周 ■利用先验知识确定一维分类阈值0 Fisher:谁则 为二所+应 人=应士N应=应 =+52=P07 02 一景佳授影 2 N+N, w*=S(m,-m2)= 9][9 [0.5 由于两类样本分布形状是相同的（只是 ■决策规则：对任意x 方向不同)，因此%应为（投影后）两 y=w*x=J y=w*x三y>→IeO 类均值的中点： y<%→X∈02 人-+应=(m+m.- 即0-3）】 2 2 Fisher准刚最佳分界面

25 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解  因为 正定，一定存在一个最优化的 w，满足  无约束最优化： 等价于带约束的最优化 1 T w w w S  ； w S max T b T w S S w w w w max , . . 1. T T b w ww ww S st S  26 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解  采用拉格朗日乘子算法解决带约束的最优化： Lagrange : ( , ) ( 1); T T L SS w ww ww     b w 定义 函数 (,) : 0; b w L S S       w w w w 令 * * 0; b w 最优解满足：S S w w    27 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解 1 1 1 21 2 * * (m m )(m m ) *; b T wb w S  SS S   ww w    根据类间离散度 的定义： 1 2 (m m ) * T 注意： 是一个数，记作 ；  w R 1 1 12 12 ( ) ( ). w w R S S    w mm mm     被忽略，因为只关心投影方向 28 2. Fisher线性判别（FDA）  Fisher 最佳投影方向的求解 1 1 1 2 12 1 2 ( ) ( ) ( ). w S SS   w mm mm      m1-m2 是一个向量，对与 (m1-m2) 平行的向量投影 可使两均值点的距离最远。但是如从使类间分得较 开，同时又使类内密集程度较高这样一个综合指标 来看，则需根据两类样本的分布离散程度对投影方 向作相应的调整，这就体现在对 m1-m2 向量按 Sw -1 作一线性变换，从而使Fisher准则函数达到极值点。 29 2. Fisher线性判别（FDA）  一维分类问题  当 d 和 N 很大时，y 近似正态分布，可在 Y 空 间内用Bayes 分类器。  利用先验知识确定一维分类阈值 y0：  决策规则: 对任意 x 1 2 0 2 m m y     ； 11 2 2 0 1 2 Nm Nm y m N N       ； 0 1 0 2 . T y y y y y          x w x x 30 由于两类样本分布形状是相同的（只是 方向不同），因此 y0 应为（投影后）两 类均值的中点： 12 1 2 0 ( ) 1; 2 2 T m m y        w mm 1 1 2 0.5 0 0 0 () ; 0 0.5 2 1 w S                       w mm 2. Fisher线性判别（FDA） 1 2 2 0 ; 0 2 w S SS         Fisher准则 最佳投影 0 2 1 2 ; (0, 1) 1. T x y y x x               w x 即 Fisher准则最佳分界面

2.Fisher?线性判别(FDA) 3.感知准则函数 口美国学者F.Rosenblatt在I957年提出的一种自学 习判别函数生成方法。 口感知器(perceptron)是一个具有单层计算单元 的人工神经网络，是人工神经元网络中应用最广 泛，影响最大的一种网络雏形。 图中绿线为最佳分界面 口类似于人认知错误、纠正错误、通过自学习改善 自己认识事物本领的过程，使用这种方法的分类 器称为感知器。 口特点：随意确定的判别函数初始值，在对样本分 类训练过程中逐步修正直至最终确定。 3.感知准则函数 3.感知准则函数 口考虑两类问题的齐次线性判别函数gy)=ay. 口基本概念 口基本概念 ■解向量：满足ay>0的权向量a; ■线性可分性：训练样本集中的两类样本在特征空 ■解区：权值空间中所有解向量组成的区域： 间可以用一个线性分界面正确无误地分开。 口在线性可分条件下，对合适的（广义）权向量a 解向量 应有： 如果y∈，则a'y>0 如果y∈，则ay0 i=1...N. 工第一类样本 b第二类杯本 -y如果ye (末规范化 ()规范化 3.感知准则函数 3.感知准则函数 口基本概念 口对于任何一个增广权向量a ■余量（对解区的限制）：解区中所有权向量都是 ■对样本y正确分类，则有：ay>0: 解，但越靠近解区中间的解向量，所得的分类面 ■对样本y错误分类，则有：ay0,要求解向量满足ayb,防止 J.(a)=∑(- 被话分类的规范 求解增广权向量的算法收敛到解区的边界。 化增广样本集 yer yi>o ■恒有JAa)≥0： ■仅当a为解向量，为空集（不存在错分样本）时 Ja=0,即达到极小值， 一确定向量a的问题支为对JAa)求极小值的问题

31 2. Fisher线性判别（FDA） 32 3. 感知准则函数  美国学者 F.Rosenblatt 在1957年提出的一种自学 习判别函数生成方法。  感知器（perceptron） 是一个具有单层计算单元 的人工神经网络，是人工神经元网络中应用最广 泛，影响最大的一种网络雏形。  类似于人认知错误、纠正错误、通过自学习改善 自己认识事物本领的过程，使用这种方法的分类 器称为感知器。  特点：随意确定的判别函数初始值，在对样本分 类训练过程中逐步修正直至最终确定。 33 3. 感知准则函数  考虑两类问题的齐次线性判别函数  基本概念  线性可分性：训练样本集中的两类样本在特征空 间可以用一个线性分界面正确无误地分开。 在线性可分条件下，对合适的（广义）权向量 a 应有：  样本的规范化：将第二类样本取其反向向量 1 2 , 0; , 0; T T       y ay y ay 如果 则 如果 则 1 2         y y y y y 如果 = 如果 0 1,..., . T i a y  i N () . T g y ay  34 3. 感知准则函数  基本概念  解向量：满足 aT y‘> 0 的权向量a；  解区：权值空间中所有解向量组成的区域； 35 3. 感知准则函数  基本概念  余量（对解区的限制）：解区中所有权向量都是 解，但越靠近解区中间的解向量，所得的分类面 离各类样本越远（最近距离越远），对将来的样 本错分的可能性越小。 引入余量 b > 0 ，要求解向量满足 aTy≥b，防止 求解增广权向量的算法收敛到解区的边界。 36 3. 感知准则函数  对于任何一个增广权向量 a  对样本 y 正确分类，则有：aTy>0；  对样本 y 错误分类，则有：aTy<0；（错分条件）  定义准则函数 JP(a) （感知准则函数）：  恒有 JP(a)≥0；  仅当 a 为解向量，Yk为空集（不存在错分样本）时， JP(a)=0，即达到极小值。 确定向量 a 的问题变为对 JP(a) 求极小值的问题。 () ( ) k T P Y J    y a ay 被错分类的规范 化增广样本集 

3.感知准则函数 3.感知准则函数 口梯度下降算法求解：对（迭代）向量沿某函数 算法(step by step) 的负梯度方向修正，可较快到达该函数极小值。 任意给定一向量 1.初值：任意给定一向量初始 初始值a1) 值a(1): VJ,(a)= 6J,(a) ak+1= a(k)+rX Sum oa 2.送代：第k什1次迭代时的 权向量a(k+1)等于第k次 (被错分类的所有样本) 的权向量a(加上被错分 a(k+1)=a(k)-r7J,(a) 类的所有样本之和与的乘 所有样本 正确分类 =a(k)+n∑y 积： Y 3.终止：对所有样本正确分类。 得到合理的a 被权向量a(k)搭 完成 分类的样本集 、分类器设计 3.感知准则函数 3.感知准则函数 口固定增量法与可变增量法 口单样本修正法的收敛性讨论 口批量样本修正法与单样本修正法 ■感知准则函数方法的思路是：先随意找一个初始 ■单样本修正法：样本集视为不 向量(1)，然后用训练样本集中的每个样本来计 断重复出现的序列，逐个样本 算。若发现一个y出现ay0。当然，修改后的a(k+1)还可以使某 then a(k+1)=a(k)+y,(r=1). 些y出现a(+1)y<0的情况。理论证明，只要 训练样本集线性可分，无论(1)的初值是什么， ■批量样本修正法：样本成批或y 经过有限次叠代，都可收敛。 全部检查后，修正权向量： 41 3.感知准则函数 口总结 ■感知准则函数方法只是对线性可分样本集有效， 而对线性不可分的样本集，该算法不能收敛。 ■对感知准则函数的讨论是很初步的，而且只讨论 了线性可分的情况。但这种利用错误提供的信 息，进行自修正的思想是非常重要的， ■只解决线性分类的感知器称为单层感知器，由它 基础上发展起来的多层感知器在原理上能解决非 线性分类、多类划分，以及非线性拟和非线性映 射等多种功能

37 3. 感知准则函数  梯度下降算法求解：对（迭代）向量沿某函数 的负梯度方向修正，可较快到达该函数极小值。 ( ) ( ) ( ); k p p Y J J       y a a y a ( 1) ( ) ( ) () . k k p k Y k k rJ k r       y aa a a y 被权向量a(k)错 分类的样本集 38 3. 感知准则函数  算法 (step by step) 1. 初值: 任意给定一向量初始 值 a(1)； 2. 迭代: 第 k+1 次迭代时的 权向量 a(k+1) 等于第 k 次 的权向量 a(k) 加上被错分 类的所有样本之和与rk的乘 积； 3. 终止: 对所有样本正确分类。 任意给定一向量 初始值a(1) a(k+1)= a(k)+ rk×Sum (被错分类的所有样本) 所有样本 正确分类 得到合理的a 完成 分类器设计 N Y 39 3. 感知准则函数  固定增量法与可变增量法  批量样本修正法与单样本修正法  单样本修正法：样本集视为不 断重复出现的序列，逐个样本 检查，修正权向量；  批量样本修正法：样本成批或 全部检查后，修正权向量； T ( if ( ) 0 then ( 1) ( ) 1). i i k k y y r k   k  a a  a 40 3. 感知准则函数  单样本修正法的收敛性讨论  感知准则函数方法的思路是：先随意找一个初始 向量 a(1)，然后用训练样本集中的每个样本来计 算。若发现一个 y 出现 aTy0。当然，修改后的 a(k+1) 还可以使某 些 y 出现 a(k+1)Ty <0 的情况。理论证明，只要 训练样本集线性可分，无论 a(1) 的初值是什么， 经过有限次叠代，都可收敛。 41 3. 感知准则函数  总结  感知准则函数方法只是对线性可分样本集有效， 而对线性不可分的样本集，该算法不能收敛。  对感知准则函数的讨论是很初步的，而且只讨论 了线性可分的情况。但这种利用错误提供的信 息，进行自修正的思想是非常重要的。  只解决线性分类的感知器称为单层感知器，由它 基础上发展起来的多层感知器在原理上能解决非 线性分类、多类划分，以及非线性拟和非线性映 射等多种功能