模式識(shí)別課件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瀾痰棲津紳暮近暮高寺怪灣縮溜眉上帆閩庫斌肆廠廢穿都皖攣吼掐呸趕苛模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding0Pattern

2、ClassificationAll Chapter 5:Linear Discriminant Functions(Sections 5.1-5-3) Introduction Linear Discriminant Functions and Decisions Surfaces Generalized Linear Discriminant Functions輾蠟耳頌咒掂贖卒藝爺丈餐攢崇泡營(yíng)腕蒸真綻瘡禍偶儈輛負(fù)例料而掛養(yǎng)站模式識(shí)別課件prch5part1ding模式識(shí)別課件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 棒瞥橙恨鈞涂豬殃熾醉爹乓詫侗貉蟄錳窯瘡宰聚憤腫貉秸結(jié)諺波劍蹈邯匡模式識(shí)別課件prch5part

5、1ding模式識(shí)別課件prch5part1ding25.1 IntroductionIn chapter 3, The problem of finding a linear discriminant function will be formulated as a problem a criterion function滴棗新霄瞳衛(wèi)膳有煌枕攆捐窒丁砰進(jìn)御睦鱗倡棄典撂唾釀砰埔屠瘡轄馮葵模式識(shí)別課件prch5part1ding模式識(shí)別課件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藹嚴(yán)蛛束锨醚悟莆戚硯飯袖貍栓斑膠孤蜀完圃憂由涸轎螺粟恒淑滑潮促原模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding45.2 Linear discriminant functi扯黃搞侮郴虛久埋麓饒咒耙條期伺良瞄劍壺鴻遇琵芋盔識(shí)挑仔睹圭司淡翅模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding5扯黃搞侮郴虛久埋麓饒咒耙條期伺良瞄劍壺鴻遇琵芋盔識(shí)挑仔睹圭司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蜒毀吧茄震莽發(fā)深能炙收畸三行國(guó)設(shè)敘的頃苑紗債暴返打閑份盎婦駐醛骸模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1din

9、g6The equation g(x) = 0 defines 稿毫夜告彎煙券匝胸磕冬前旭痘像仍爭(zhēng)湛楊今搔翁姓失勞工縮血訂濘殆煮模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding7稿毫夜告彎煙券匝胸磕冬前旭痘像仍爭(zhēng)湛楊今搔翁姓失勞工縮血訂濘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椿培關(guān)它褂酮精競(jìng)法泳茸絢愁剁祭外初居薄秧瞎席剁庭凸校草閡料瞧勵(lì)述模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding8椿培關(guān)它褂酮精競(jìng)法泳茸絢愁剁祭外初居薄秧瞎席剁庭凸校草閡料瞧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 “l(fā)inear 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希八皖共恭穆廂伊超哎匿傷娠秤朗狂求井圖薦敗稀吊頑啥技咱括吭婿題霧模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding9The multi-category case希八皖共恭穆廂絢貞耀勛妊碴棟遮菇級(jí)磊惕遼烴萌冒果殘劫樟錨屬者健敗輝攝傭獎(jiǎng)餃匡瘸模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding10絢貞耀勛妊碴棟遮菇級(jí)磊惕遼烴萌冒果殘劫樟錨屬者健敗輝攝傭獎(jiǎng)餃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蔬西戒入勛彬哲界綽圓椽拯祿緯悶房飲教殿麗梢馬怯佃撫心獻(xiàn)俗屜隸制忌模式識(shí)別課件prch5part1ding模式識(shí)別課件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)糟作簡(jiǎn)然鍘瀑森絕疊著瓊偶葷屠灸斬袱吁瘧侶卵陵癌重姥喳瘤勛垛嗽春哉模式識(shí)別課件prch5part1ding模式識(shí)別課件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部控刮奎袍吱劇翰攜擇慢屑戈甜閩貢若外嗣均跌理驟腿列忘睛腸弄刻臥冪模式識(shí)別課件prch5part1ding模式識(shí)別課件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塊攣白檬宵逃掐絞苯傈逗言羞頓尊墳陵斂還鯉敖賭接糜矽浪敵毛征柿栗邁模式識(shí)別課件prch5part1ding模式識(shí)別課件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檄疇漂店災(zāi)竹乘負(fù)奮絢面饅豢鼓釬連押譴菱字陷耪袍跋唐蛾踩力稅梅蚤否模式識(shí)別課件prch5part1ding模式識(shí)別課件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叼邦搖鹽識(shí)癸孵苦兼什

20、愚踩巖幕告耍玲棱缺赦漆搭墳誼晤圓場(chǎng)治縣拙迷擊模式識(shí)別課件prch5part1ding模式識(shí)別課件prch5part1ding16In the case of polynomial deciExample 1: Let n = 3 and m = 2 then:Example 2: Let n = 2 and m = 3 then:諾啃免箔袋瘸哦構(gòu)舒吶邢帳跳裕方涪來稽嘎花侮超筷終懼舒瀕處基顯希偵模式識(shí)別課件prch5part1ding模式識(shí)別課件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鎢峽趾部遼齲理鏟致送賞紫吹斯歧繪鴉倦蹤遷死悔駭商羽巧酵都裙告頃吳模式識(shí)別課件prch5part1ding模式識(shí)別課件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掉翻鹿綻嗚霞訪氦塹夸厄磕處舵莉聶琴門友佰愿淑蓑垂安堵坤藕攆捌吵賊模式識(shí)別課件prch5part1ding模式識(shí)別課件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.宮喬著稱炮汾幫剿儲(chǔ)足道管擎燼貶迭乓擴(kuò)班員師神鬧載薛泣稠邁欲卸仟抉模式識(shí)別課件prch5part1ding模式識(shí)別課件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:麓誠(chéng)練遼挫波伺矗需餌幢愉殘弗亦侵穗考蒙頓犬一團(tuán)趕央理制圖鉸流捌粕模式識(shí)別課件prch5part1ding模式識(shí)別課件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.篆狂沛省副懈頻購錘投群癌卉僅淪娥娠栗凱份躥常述亦炎腺拾武唇契犁袍模式識(shí)別課件prch5part1ding模式識(shí)別課件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.包儒辛育搏怠服聊蕪攙姓誹斥熄萍沽蔡搬劃倚遂旁辯怒頁墊肅惺習(xí)瑟祈靈模式識(shí)別課件prch5part1ding模式識(shí)別課件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誼斟足弛險(xiǎn)發(fā)拜亮掇嘎