Pattern Classi cation by Duda et al.

1 Solutions to Pattern Classification by Duda et @ githubDecember 11, 2018 AbstractThis document contains solutions to selected exercises from the book PatternRecognition by Richard O. Duda, Peter E. Hart and David G. Stork. Although itwas written in 2001, the second edition has truly stood the test of time it s a much-cited, well-written introductory text to the exciting field ofpattern recognition(orsimplymachine learning). At the time of writing, the book has close to 40 000citations according to short chapter summaries are included in this document, they are not in-tended to substitute the book in any way. The summaries will largely be meaninglesswithout the book, which I recommend buying if you re interested in the solutions and notes were typeset in LATEX to facilitate my own learningprocess.

2 Machine learning has rightfully garnered considerable attention in recentyears, and while many online resources are worthwhile it seems reasonable to favorbooks when attempting to learn the material hope you find my solutions helpful if you are stuck. Remember to make anattempt at solving the problems yourself before peeking. More likely than not,the solutions can be improved by a reader such as yourself. If you would like tocontribute, please submit a pull request 1: The front cover of [Duda et al., 2000].1 Contents1 Notes from Pattern Classification Bayesian Decision Theory .. Maximum-likelihood and Bayesian parameter estimation.

3 Nonparametric techniques .. Linear discriminant functions .. Multilayer Neural Networks .. Stochastic methods .. Nonmetric methods .. Algorithm-independent machine learning .. Unsupervised learning and clustering .. 122 Solutions to Pattern Classification Bayesian Decision Theory .. Maximum-likelihood and Bayesian parameter estimation .. Nonparametrix techniques .. Linear discriminant functions .. Multilayer Neural Networks .. Stochastic methods .. Nonmetric methods .. Algorithm-independent machine learning .. Unsupervised learning and clustering.

4 6921 Notes from Pattern Classification Bayesian Decision Theory Bayes theorem isP( j|x) =p(x| j) P( j)p(x)=likelihood Bayes decision rule is to choose the state of nature msuch that m= arg maxjP( j|x). Loss functions (or risk functions) with losses other than zero-one are possible. Ingeneral, we choose the action to minimize the riskR( |x). The multivariate normal density (the Gaussian) is given byp(x| , ) =1(2 )d/2| |1/2exp[ 12(x )T 1(x )].It is often analytically tractable, and closed form discriminant functions exist. If featuresyare missing, we integrate them out (marginalize) using the sum rulep(x) = p(x,y)dy= p(x|y)p(y)dy.

5 InBayesian belief networks, influences are represented by a directed network. IfBis dependent onA, we add a directed edgeA Bto the 2: A Bayesian belief network. The source is Maximum-likelihood and Bayesian parameter estimation Themaximum likelihoodof a distributionp(x| ) is given by = arg max p(D | ),assuming data points and maximizing the log-likelihood, we have = arg max lnp(D | ) = arg max lnn i=1p(xi| ).Analytical solutions exist for the Gaussian. In general a maximum likelihood esti-mate may be biased, in the sense thatEx[ ] = p(x)dx6= .3 In the Bayesian framework, the parameter is expressed by a probability densityfunctionp( ).

6 This is called thepriordistribution of , which is updated when newdata is observed. The result is called theposteriordistribution, given byp( |D) =p(D | )p( )p(D)=p(D | )p( ) p(D | )p( )d .The estimate ofxthen becomesp(x|D) = p(x, |D)d = p(x| ,D)p( |D)d = p(x| )p( |D)d ,which may be interpreted as a weighted average of modelsp(x| ), wherep( |D)is the weight associated with the model. The Bayesian framework is analytically tractable when using Gaussians. For in-stance, we can computep( |D) if we assumep( ) N( 0, 0). The distributionp( ) is called aconjugate priorandp( |D) is areproducing density, since a normalprior transforms to a normal posterior (with different parameters) when new datais observed.

7 In summary the Bayesian framework allows us to incorporate prior information,but the maximum-likelihood approach is simpler. Maximum likelihood gives us anestimate , but the Bayesian framework gives usp( |D) the full distribution. Principal Component Analysis(PCA) yields components useful covariance matrix is diagonalized, and low-variance directions in the hyperellip-soid are eliminated. The computation is often performed using theSingular ValueDecomposition(SVD). Discriminant Analysis(DA) projects to a lower dimensional subspace with optimaldiscrimination(and not representation). Expectation Maximization(EM) is an iterative algorithm for finding the maximum-likelihood when data is missing (or latent).

8 Figure 3: A hidden Markov model. The source is Wikipedia. A discrete, first order, hidden Markov model consists of a transition matrixAand anemission matrixB. The probability of transition from stateito statejis given by4aij, and the probability that stateiemits signaljis given bybij. Three fundamentalproblems related to Markov models are: The evaluation problem - probability thatVTwas emitted, givenAandB. The decoding problem - determine most likely sequence of hidden states T,given emittedVT,AandB. The learning problem - determineAandBgiven training observations ofVTand a coarse Nonparametric techniques Two conceptually different approaches to nonparametric Pattern recognition are: Estimation of densitiesp(x|wj), called thegenerativeapproach.

9 Estimation ofP(wj|x), called thediscriminativeapproach. Parzen-windows (kernel density estimation) is a generative method. It places akernel function :R+ R+on every data pointxito create a density estimatepn(x) =1nn i=11Vn ( x xi phn),where p:Rd R+is thep-norm (which induces the so-calledMinkowski metric)andhn>0 is the bandwidth. k-nearest neighbors is a discriminative method. It uses information about theknearest neighbors of a pointxto computeP(wj|x). This automatically uses moreof the surrounding space when data is sparse, and less of the surrounding spacewhen data is dense. Thek-nearest neighbor estimate is given byP(wj|x) =# samples labeledwjk.

10 Thenearest neighbor methodusesk= 1. It can be shown that the error ratePofthe nearest neighbor method is never more than twice the Bayes error rateP inthe limit of infinite data. More precisely, we haveP P P (2 cc 1P ). In some applications, careful thought must be put into metrics. Examples includeperiodic data onR/Zand image data where the metric should be invariant to smallshifts and rotations. One method to alleviate the problems of using the 2-norm as ametric on images is to introduce thetangent distance. For an imagex , the tangentvector of a transformationF(such as rotation by an angle i) is given byTVi=F(x ; i) x .If several transformations are available, their linear combination may be each test pointx, we search the tangent space for the linear combination mini-mizing the metric.