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 publisherChapter 2 (part 3)Bayesian Decision Theory (Sections 2-6,2-9) Discriminant Fu

2、nctions for the Normal Density Bayes Decision Theory Discrete FeaturesPattern Classification, Chapter 2 (Part 3)2Discriminant Functions for the Normal DensityWe saw that the minimum error-rate classification can be achieved by the discriminant functiongi(x) = ln P(x | i) + ln P(i)Case of multivariat

3、e normal)(lnln212ln2)()(21)(1iiiitiiPdxxxgPattern Classification, Chapter 2 (Part 3)3Case i = 2I (I stands for the identity matrix) What does “i = 2I” say about the dimensions?What about the variance of each dimension?normEuclidean thedenotes where)(ln2)(:osimplify tcan weThus)(lnln212ln2)()(21)(in

4、oft independen are ln (d/2) and both :Note221iiiiiiiitiiPxgPdxxxgiPattern Classification, Chapter 2 (Part 3)4We can further simplify by recognizing that the quadratic term xtx implicit in the Euclidean norm is the same for all i.)category!th for the threshold thecalled is ()(ln21 ; :wherefunction)nt

5、 discrimina(linear )(02020iiiitiiiiitiiPwwxgwxwPattern Classification, Chapter 2 (Part 3)5A classifier that uses linear discriminant functions is called “a linear machine”The decision surfaces for a linear machine are pieces of hyperplanes defined by:gi(x) = gj(x)The equation can be written as: wt(x

6、-x0)=0Pattern Classification, Chapter 2 (Part 3)6The hyperplane separating Ri and Rjalways orthogonal to the line linking the means!)()()(ln)(21220jijijijiPPx)(21 then )()( 0jijiPPifxPattern Classification, Chapter 2 (Part 3)7Pattern Classification, Chapter 2 (Part 3)8Pattern Classification, Chapter

7、 2 (Part 3)9Pattern Classification, Chapter 2 (Part 3)10Case i = (covariance of all classes are identical but arbitrary!)Hyperplane separating Ri and Rj(the hyperplane separating Ri and Rj is generally not orthogonal to the line between the means!).()()()(/ )(ln)(21and)(Where0)(equation theHas100tji

8、jitjijijijiPPxwxxw1Pattern Classification, Chapter 2 (Part 3)11Pattern Classification, Chapter 2 (Part 3)12Pattern Classification, Chapter 2 (Part 3)13Case i = arbitrary The covariance matrices are different for each categoryThe decision surfaces are hyperquadratics(Hyperquadrics are: hyperplanes, p

9、airs of hyperplanes, hyperspheres, hyperellipsoids, hyperparaboloids, hyperhyperboloids)(Plnln2121 w w21W :wherewxwxWx)x(g iii1iti0ii1ii1ii0itiiti Pattern Classification, Chapter 2 (Part 3)14Pattern Classification, Chapter 2 (Part 3)15Pattern Classification, Chapter 2 (Part 3)16Bayes Decision Theory

10、 Discrete FeaturesComponents of x are binary or integer valued, x can take only one of m discrete values v1, v2, , vm concerned with probabilities rather than probability densities in Bayes Formula:cjjjjjjPPPPPPP1)()|()(where)()()|()|(xxxxxPattern Classification, Chapter 2 (Part 3)17Bayes Decision T

11、heory Discrete FeaturesConditional risk is defined as before: R(a|x)Approach is still to minimize risk:)|(minarg*xiiRaaPattern Classification, Chapter 2 (Part 3)18Bayes Decision Theory Discrete FeaturesCase of independent binary features in 2 category problemLet x = x1, x2, , xd t where each xi is e

12、ither 0 or 1, with probabilities:pi = P(xi = 1 | 1)qi = P(xi = 1 | 2)Pattern Classification, Chapter 2 (Part 3)19Bayes Decision Theory Discrete FeaturesAssuming conditional independence, P(x|i) can be written as a product of component probabilities:dixiixiidixixidixixiiiiiiiqpqpPPqqPppP112111211111)|()|(:bygiven ratio likelihood a yielding)1 ()|(and)1 ()|(xxxxPattern Classification, Chapter 2 (Part 3)20Bayes Decision Theory Discrete FeaturesTaking our likelihood ratio)()(ln11ln)1 (ln)(:yields)()(ln)|()|(ln)(31 Eq. intoit plugging and11)|()|(21121211121ppqpxqpxgppppgqpqpPPdiiiiiiid