模式识别课件prch5part1ding

1、Pattern ClassificationAll materials in these slides were taken from Pattern Classification (2nd ed) by R. O. Duda, P. E. Hart and D. G. Stork, John Wiley & Sons, 2000 with the permission of the authors and the publisher澜痰栖津绅暮近暮高寺怪湾缩溜眉上帆闽库斌肆厂废穿都皖挛吼掐呸赶苛模式识别课件prch5part1ding模式识别课件prch5part1ding0Pattern

2、ClassificationAll Chapter 5:Linear Discriminant Functions(Sections 5.1-5-3) Introduction Linear Discriminant Functions and Decisions Surfaces Generalized Linear Discriminant Functions辗蜡耳颂咒掂赎卒艺爷丈餐攒崇泡营腕蒸真绽疮祸偶侩辆负例料而挂养站模式识别课件prch5part1ding模式识别课件prch5part1ding1Chapter 5:Linear Discriminant5.1 Introductio

3、nIn chapter 3, the underlying probability densities were known.The training sample was used to estimate the parameters of these probability densities (ML, MAP estimations)In this chapter, we only know the proper forms for the linear discriminant functions, and use samples to estimate the values of p

4、arameters for the discriminant functions : similar to non-parametric techniquesThey may not be optimal, but they are very simple and easy to computethey are chosen as candidates for initial and trial classifiers especially in the absence of information 棒瞥橙恨钧涂猪殃炽醉爹乓诧侗貉蛰锰窑疮宰聚愤肿貉秸结谚波剑蹈邯匡模式识别课件prch5part

5、1ding模式识别课件prch5part1ding25.1 IntroductionIn chapter 3, The problem of finding a linear discriminant function will be formulated as a problem a criterion function滴枣新霄瞳卫膳有煌枕撵捐窒丁砰进御睦鳞倡弃典撂唾酿砰埔屠疮辖冯葵模式识别课件prch5part1ding模式识别课件prch5part1ding3The problem of finding a linea5.2 Linear discriminant functions a

6、nd decisions surfacesDefinition: It is a function that is a linear combination of the components of xg(x) = wtx + w0 (1)where w is the weight vector and w0 the bias(threshold weight)A two-category classifier with a discriminant function of the form (1) uses the following rule:Decide 1 if g(x) 0 and

7、2 if g(x) -w0 and 2 otherwiseIf g(x) = 0 x is assigned to either class蔼严蛛束锨醚悟莆戚砚饭袖狸栓斑胶孤蜀完圃忧由涸轿螺粟恒淑滑潮促原模式识别课件prch5part1ding模式识别课件prch5part1ding45.2 Linear discriminant functi扯黄搞侮郴虚久埋麓饶咒耙条期伺良瞄剑壶鸿遇琵芋盔识挑仔睹圭司淡翅模式识别课件prch5part1ding模式识别课件prch5part1ding5扯黄搞侮郴虚久埋麓饶咒耙条期伺良瞄剑壶鸿遇琵芋盔识挑仔睹圭司The equation g(x) = 0 de

8、fines the decision surface that separates points assigned to the category 1 from points assigned to the category 2When g(x) is linear, the decision surface is a hyperplaneAlgebraic measure of the distance from x to the hyperplane蜒毁吧茄震莽发深能炙收畸三行国设叙的顷苑纱债暴返打闲份盎妇驻醛骸模式识别课件prch5part1ding模式识别课件prch5part1din

9、g6The equation g(x) = 0 defines 稿毫夜告弯烟券匝胸磕冬前旭痘像仍争湛杨今搔翁姓失劳工缩血订泞殆煮模式识别课件prch5part1ding模式识别课件prch5part1ding7稿毫夜告弯烟券匝胸磕冬前旭痘像仍争湛杨今搔翁姓失劳工缩血订泞In conclusion, a linear discriminant function divides the feature space by a hyperplane decision surfaceThe orientation of the surface is determined by the normal ve

10、ctor w and the location of the surface is determined by the bias椿培关它褂酮精竞法泳茸绚愁剁祭外初居薄秧瞎席剁庭凸校草阂料瞧励述模式识别课件prch5part1ding模式识别课件prch5part1ding8椿培关它褂酮精竞法泳茸绚愁剁祭外初居薄秧瞎席剁庭凸校草阂料瞧The multi-category caseWe define c linear discriminant functionsand assign x to i if gi(x) gj(x) j i; in case of ties, the classifica

11、tion is undefinedIn this case, the classifier is a “linear machine”A linear machine divides the feature space into c decision regions, with gi(x) being the largest discriminant if x is in the region RiFor a two contiguous regions Ri and Rj; the boundary that separates them is a portion of hyperplane

12、 Hij defined by: gi(x) = gj(x) = (wi wj)tx + (wi0 wj0) = 0wi wj is normal to Hij and希八皖共恭穆厢伊超哎匿伤娠秤朗狂求井图荐败稀吊顽啥技咱括吭婿题雾模式识别课件prch5part1ding模式识别课件prch5part1ding9The multi-category case希八皖共恭穆厢绚贞耀勋妊碴栋遮菇级磊惕辽烃萌冒果残劫樟锚属者健败辉摄佣奖饺匡瘸模式识别课件prch5part1ding模式识别课件prch5part1ding10绚贞耀勋妊碴栋遮菇级磊惕辽烃萌冒果残劫樟锚属者健败辉摄佣奖饺It is eas

13、y to show that the decision regions for a linear machine are convex, this restriction limits the flexibility and accuracy of the classifier蔬西戒入勋彬哲界绰圆椽拯禄纬闷房饮教殿丽梢马怯佃抚心献俗屉隶制忌模式识别课件prch5part1ding模式识别课件prch5part1ding11It is easy to show that the de5.3 Generalized Linear Discriminant FunctionsDecision bou

14、ndaries which separate between classes may not always be linearThe complexity of the boundaries may sometimes request the use of highly non-linear surfacesA popular approach to generalize the concept of linear decision functions is to consider a generalized decision function as:g(x) = w1f1(x) + w2f2

15、(x) + + wNfN(x) + wN+1 (1)where fi(x), 1 i N are scalar functions of the pattern x, x Rn (Euclidean Space)糟作简然铡瀑森绝叠着琼偶荤屠灸斩袱吁疟侣卵陵癌重姥喳瘤勋垛嗽春哉模式识别课件prch5part1ding模式识别课件prch5part1ding125.3 Generalized Linear DiscrimIntroducing fn+1(x) = 1 we get:This latter representation of g(x) implies that any decisio

16、n function defined by equation (1) can be treated as linear in the (N + 1) dimensional space (N + 1 n)g(x) maintains its non-linearity characteristics in Rn部控刮奎袍吱剧翰携择慢屑戈甜闽贡若外嗣均跌理骤腿列忘睛肠弄刻卧幂模式识别课件prch5part1ding模式识别课件prch5part1ding13Introducing fn+1(x) = 1 we getThe most commonly used generalized decis

17、ion function is g(x) for which fi(x) (1 i N) are polynomialsQuadratic decision functions for a 2-dimensional feature space块挛白檬宵逃掐绞苯傈逗言羞顿尊坟陵敛还鲤敖赌接糜矽浪敌毛征柿栗迈模式识别课件prch5part1ding模式识别课件prch5part1ding14The most commonly used generalFor patterns x Rn, the most general quadratic decision function is given b

18、y:The number of terms at the right-hand side is:This is the total number of weights which are the free parameters of the problemIf for example n = 3, the vector is 10-dimensional If for example n = 10, the vector is 66-dimensional檄畴漂店灾竹乘负奋绚面馒豢鼓钎连押谴菱字陷耪袍跋唐蛾踩力税梅蚤否模式识别课件prch5part1ding模式识别课件prch5part1di

19、ng15For patterns x Rn, the most gIn the case of polynomial decision functions of order m, a typical fi(x) is given by: It is a polynomial with a degree between 0 and m. To avoid repetitions, we request i1 i2 im(where g0(x) = wn+1) is the most general polynomial decision function of order m叼邦摇盐识癸孵苦兼什

20、愚踩岩幕告耍玲棱缺赦漆搭坟谊晤圆场治县拙迷击模式识别课件prch5part1ding模式识别课件prch5part1ding16In the case of polynomial deciExample 1: Let n = 3 and m = 2 then:Example 2: Let n = 2 and m = 3 then:诺啃免箔袋瘸哦构舒呐邢帐跳裕方涪来稽嘎花侮超筷终惧舒濒处基显希侦模式识别课件prch5part1ding模式识别课件prch5part1ding17Example 1: Let n = 3 and m = 2 The commonly used quadratic d

21、ecision function can be represented as the general n- dimensional quadratic surface:g(x) = xTAx + xTb +cwhere the matrix A = (aij), the vector b = (b1, b2, , bn)T and c, depends on the weights wii, wij, wi of equation (2) If A is positive definite then the decision function is a hyperellipsoid with

22、axes in the directions of the eigenvectors of AIn particular: if A = In (Identity), the decision function is simply the n-dimensional hypersphere钨峡趾部辽龋理铲致送赏紫吹斯歧绘鸦倦踪迁死悔骇商羽巧酵都裙告顷吴模式识别课件prch5part1ding模式识别课件prch5part1ding18 The commonly used quadratic dIf A is negative definite, the decision function de

23、scribes a hyperboloidIn conclusion: it is only the matrix A which determines the shape and characteristics of the decision function掉翻鹿绽呜霞访氦堑夸厄磕处舵莉聂琴门友佰愿淑蓑垂安堵坤藕撵捌吵贼模式识别课件prch5part1ding模式识别课件prch5part1ding19If A is negative definite, theProblem: Consider a 3 dimensional space and cubic polynomial deci

24、sion functionsHow many terms are needed to represent a decision function if only cubic and linear functions are assumedPresent the general 4th order polynomial decision function for a 2 dimensional pattern spaceLet R3 be the original pattern space and let the decision function associated with the pa

25、ttern classes 1 and 2 be:for which g(x) 0 if x 1 and g(x) 0 for all nonzero column vectors x.It is negative definite if xTAx 0 for all nonzero x. It is positive semi-definite if xTAx 0.And negative semi-definite if xTAx 0 for all x. These definitions are hard to check directly and you might as well

26、forget them for all practical purposes.宫乔著称炮汾帮剿储足道管擎烬贬迭乓扩班员师神闹载薛泣稠迈欲卸仟抉模式识别课件prch5part1ding模式识别课件prch5part1ding21Positive Definite Matrices宫乔著More useful in practice are the following properties, which hold when the matrix A is symmetric and which are easier to check.The ith principal minor of A is

27、the matrix Ai formed by the first i rows and columns of A. So, the first principal minor of A is the matrix Ai = (a11), the second principal minor is the matrix:麓诚练辽挫波伺矗需饵幢愉残弗亦侵穗考蒙顿犬一团赶央理制图铰流捌粕模式识别课件prch5part1ding模式识别课件prch5part1ding22More useful in practice are thThe matrix A is positive definite i

28、f all its principal minors A1, A2, , An have strictly positive determinantsIf these determinants are non-zero and alternate in signs, starting with det(A1) 0det(A2) = a11a22 a12a12 0It is negative definite if:det(A1) = a11 0It is positive semi-definite if:det(A1) = a11 0det(A2) = a11a22 a12a12 0And

29、it is negative semi-definite if:det(A1) = a11 0det(A2) = a11a22 a12a12 0.篆狂沛省副懈频购锤投群癌卉仅沦娥娠栗凯份蹿常述亦炎腺拾武唇契犁袍模式识别课件prch5part1ding模式识别课件prch5part1ding24To fix ideas, consider a 2x2 sExercise 1: Check whether the following matrices are positivedefinite, negative definite, positive semi-definite, negative

30、semi-definite or none of the above.包儒辛育搏怠服聊芜搀姓诽斥熄萍沽蔡搬划倚遂旁辩怒页垫肃惺习瑟祈灵模式识别课件prch5part1ding模式识别课件prch5part1ding25Exercise 1: Check whether the Solutions of Exercise 1:A1 = 2 0A2 = 8 1 = 7 0 A is positive definiteA1 = -2A2 = (-2 x 8) 16 = 0 A is negative semi-positiveA1 = - 2A2 = 8 4 = 4 0 A is negative definiteA1 = 2 0A2 = 6 16 = -10 0 A is none of the above谊斟足弛险发拜亮掇嘎