WIXLIB

Sonka: Pattern Recognition Class36Bayes classifier behavior is determined by1) conditional density p(x wi)2) a priori probability P(wi)Normal (Gaussian) probability density function wasstudied extensivelyWhy normal?- it is well behaved and analytically tractable- it is an apprpriate model for values randomly distributedaround mean µ.

Sonka: Pattern Recognition Class37Gaussian models for p(x w1)- multidimensional Gaussian distributionx is a d-dimensional vector d 1µ is the mean vectorΣ is the covariance matrix d dÎ complete specification of p(x)using d d(d 1)/2 parametersHaving class-specific mean vectors µi and class-specificcovariance matrices Σi, class-dependent density functionsp(x wi) can be calculated.How to estimate mean vectors µi and covariance matricesΣi? It will come later when we discuss training.

Sonka: Pattern Recognition Class38Discriminant functions in this case:i-th class:gi(x) P(wi x)Classification . finding the largest discriminationfunction:More generally, any monotonically increasing function ofgi(x) can be used as a valid discrimination function.Assuming equal a priori probabilities,andP(wi x) p(x wi)gi(x) log[p(x wi)]Let’s assume equal Σ for all classes, different meanvectors µ.General multivariate normal density:p(x) 1/((2π)d/2 1/2) exp[-1/2 (x-µ)T Σ-1 (x-µ)]Î

Sonka: Pattern Recognition Class39Îgi’(x) -1/2 (x-µi)T Σ-1 (x-µi) - (d/2)log(2π) - (1/2)log Σ class-independent biases can be eliminatedWhat remains is the squared distance of feature vector xfrom the i-th mean vector µi weighted by the inverse ofthe covariance matrixFor Σ I , Euclidean norm results.g’i(x) is largest if (x-µi)T Σ-1 (x-µi) is smallest. minimum distance concept for the same Σ for allclasses .Linear discriminant functionsgi(x) wiT x wi0wi0 -1/2 µiT µiandThus, µi is a template for class wi.wi µi

Sonka: Pattern Recognition Class401-D case:2-D and 3-D cases:Î linear discrimination functions.(However, Σ I is not necessary to achieve lineardiscriminant functions.)

Sonka: Pattern Recognition Class41

Sonka: Pattern Recognition Class42ΣI Σ covariance matrices identical but arbitrarygi’(x) - (x-µi)T Σ-1 (x-µi)Î measure squaredMahalanobis distance (x-µi)T Σ-1 (x-µi)from x to to each of the mean vectorsassign class according to the nearest mean

Sonka: Pattern Recognition Class43Generalized result . Σi is class dependent ( arbitrary)gi(x) -1/2(x-µi)T Σi-1 (x-µi) - (d/2)log(2π) - (1/2)log Σi

Sonka: Pattern Recognition Class44or, using the Bayes formula:gi(x) log[P(wi x)p(x)] log[p(x wi)] log[P(wi)]If components are uncorrelated with equal variance σ2,i.e.,Σi σ2 Iand after eliminating the class-independent bias log(Σi),gi(x) -(1/(2σ2))(x-µi)T (x-µi) log[P(wi)]In that case, loci of constant x-µi 2 are hyperspheres,each centered at the class mean µi.

Sonka: Pattern Recognition Class45Previously, Σ I, now assume:unequal variancesuncorrelated componentsThe covariance matrix for class i:Σi σ112 0 00 σ2220 00 00 0 0Σ-1i 1/σ112 0 . 000 1/σ2220 0. 00 0. 00 0 01/σdd2. 00. 0. 0σdd2Thus, the decision rule yields a weighted distanceclassifier . more emphasis on features with smaller σii2.Decision surfaces are hyperellipses (hyperquadrics).

Sonka: Pattern Recognition Class46

Sonka: Pattern Recognition Class47

Sonka: Pattern Recognition Class48

Sonka: Pattern Recognition Class49Bayes decision theory – discrete featuresuntil now, feature vector x was from Rdfrequently, x can only have one of m discrete valuesÎ probability density functions is singular and integrals p(x wj) dxmust be replaced by summation over all values of x indiscrete distributionΣ P(x wj)Bayes formula then uses probabilities instead ofprobability densities:P(wj x) P(x wj) P(wj) / P(x)whereP(x) Σj 1 c P(x wj) P(wj)

Sonka: Pattern Recognition Class50Definition of conditional risk remains unchangedÎ so the fundamental Bayes decision rule is still thesame.Extensions:How to determine parameters of the probability densityfunctions (PDF)?May be based on training samples from a training set H.(Coming soon)Maximum likelihood classification is not the only one.A) Nearest neighbor classificationB) Decision TreesC) Unsupervised learning approaches

Sonka: Pattern Recognition Class51Chapter 3Supervised LearningMaximum likelihood classificationP(wi x) p(x wi) P(wi)requires knowledge ofp(x wi), P(wi), calways easy for P(wi), cfrequently difficult for p(x wi), especially ifdimensionality is high Î never enough samples. If we can assume that the distribution is normalÆ Gaussian densities, we need µi, Σi for each classÆ much simpler than estimating an unknown function.This information must be derived from the training set.Assume that the FORM of densities is known, then wehave to ESTIMATE the density parameters.

Sonka: Pattern Recognition Class52Parameter EstimationA) Maximum likelihood estimationassuming that parameters are fixed but unknownB) Bayesian estimationassumes random variables with known a prioridistributions

Sonka: Pattern Recognition Class53Maximum Likelihood EstimationTraining set in the form of c subsets H1, H2, ., HcSamples are assumed to be generated by the densityfunction for class i . probability density p(x wi).Let the set of parameters to be estimated be denoted ΘiIn the Gaussian case, Θi [µi, Σi].Let’s denote the parameter dependency p(x wi,Θi).where Θi is unknown but fixed . not a random vectorAdditionally, assume that Hi givesno information about Θj if i jÎ we can work with each class separately.

Sonka: Pattern Recognition Class54Î we have c separate problems as follows (we canremove class dependency from notation, since problemsare separated):A set of H training samples drawn independently fromthe probability density p(x Θ) and the goal is to estimatethe unknown parameter vector Θ.General case is described on p. 86-87, but special Gaussian case is more frequently used Gaussian caseConsider samples drawn from a multivariate normalpopulation with mean µ and covariance matrix Σ.A) Only µ is unknownµ 1/n Σk 1n xkÎ maximum likelihood estimate for the unknownpopulation mean is the arithmetic average of trainingsamples.In n-D . µ is centroid of a cloud of samples.

Sonka: Pattern Recognition ClassB) µ and Σ are unknownThis is a more usual case than case A.Univariate case . estimate µ and σ2ε 1/n Σk 1n xk (same as before)Îσ2 1/n Σ k 1n (xk - µ)2Multivariate case estimate µ and Σε 1/n Σk 1n xk (same as before)ÎΣ 1/n Σ k 1n (xk - µ)(xk - µ)T55

Sonka: Pattern Recognition Class56BiasThe maximum-likelihood estimate of σ2 is biasedÎ the expected value over all data sets is not equal truevarianceCheck the above statement for n 1:Σ 1/n Σ k 1n (xk - µ)(xk - µ)T 0while the entire distribution has a non-zero covariancematrix Î result cannot be trusted for small values of nSuch estimators are asymptotically unbiased givecorrect results for large-enough training sets.Elementary unbiased estimator:Σunbiased 1/(n-1) Σ k 1n (xk - µ)(xk - µ)TIf estimator is unbiased for all distributions (like the oneright above) Î absolutely unbiased estimatorExistence of 2 estimators Æ neither of them is perfect

Sonka: Pattern Recognition Class57Another problem is that if we have an unreliable modelfor underlying distributions, the classifier based onmaximum likelihood will not be optimal Î modelselection is crucial.Bayesian Parameter EstimationObjective: Given Hi, form P(wi x, Hi)(obviously, a posteriori probability depends on thetraining set)Using the Bayes formula, the BEST density parameter ischosen based on the maximum a posteriori probability ofthe parameter.However, reaching the solution in a general case is notstraightforward.In special cases of Normal distribution, the situation ismuch easier

Sonka: Pattern Recognition Class58A) Known Σ, unknown µHow to calculate µi for class i from the training set?a) Max. likelihood: Use the recursive formula:µ i(k 1) 1/(k 1) [k µ i(k) xk 1]b) Using the Bayes approach:assume the a priori covariance matrix for class i:known Σi (1/a) σiThen, the recursive formulaµi(k 1) [(a k)/(a k 1)]µi(k) [1/(a k 1)]xk 1Parameter a represents the confidence in the a prioriestimate of µ. In training, it specifies the number of stepsin which we believe more in the a priori estimate than inthe measured mean.For a 0, µ mean(x)B) Unknown Σ, known µ

Sonka: Pattern Recognition Class59a) Max. likelihood; recursive formula:Σi(k 1) 1/(k 1) [k Σi(k) (xk 1 - µi)(xk - µi)T]b) Bayes approach:Let K be the number of samples in the trainingset. Let Φi(0) be the a priori estimate of the covariancematrix. Let Σi(K) be calculated as in a) above.Then,Φi(K) [b Φi(0) K Σi(K)] / [b K]and Φi(K) is considered the Bayes estimate of Σi(K).Parameter b represents the confidence in the a prioriestimate of Σ.

Sonka: Pattern Recognition Class60C) Unknown Σ, unknown µ (most often the case)a) Max. likelihood; recursive formula:µi(k 1) 1/(k 1) [k µi(k) xk 1]Σi(k 1) 1/k [(k-1) Σi(k) (xk 1 - µi(k 1))(xk 1 - µi(k 1))T k(µi(k) - µi(k 1))( µi(k) - µi(k 1))T ]b) Bayes approach:Let K be the number of samples in the training set.Let µi(0) be the a priori estimate of the mean vector forclass i.Let Φi(0) be the a priori estimate of the covariancematrix.

Sonka: Pattern Recognition Class61Using µi(K) and Σi(K) calculated according to themaximum likelihood formulae in A) and B), respectively:Μi(K) [a µi(0) K µi(K)] / [a K]Φi(K) [1/ (b K)]{ b Φi(0) a µi(0) µi(0)T (K-1) Σi(K) K µi(K) µi(K)T - (a K) Μi(K) Μi(K)T }Μi(K) is considered the Bayes estimate of µi(K).Φi(K) is considered the Bayes estimate of Σi(K).Parameters a,b represent the confidence in the a prioriestimates of µ and Σ.

Sonka: Pattern Recognition Class62When do Maximum Likelihood and Bayes methodsdiffer?- identical for infinite numbers of training samples- but # of training samples is finite, so which approch isbetter and when?Criteria:- computational complexity(Max. likelihood is easier differential calculus, nomultidimensional integration as may be needed by Bayestechniques)- interpretability(max. likelihood gives single best model,Bayesian methods give a weighted average ofmodels more difficult to understand)- confidence in prior informatione.g., in form of p(x wi,Θi) Bayesian methods usemore such a priori informationÎ if a priori information is reliable,Bayesian approach is typically betterÎ Max Likelihood and Bayesian approaches areidentical for uniform priors no specific prior info

Sonka: Pattern Recognition Class63Sources of error in final classification system:1) Bayes (or Indistinguishability) errorerror due to overlapping densities p(x wi)Æ can never be eliminated2) Model errorerror caused by having an incorrect modelÎ better model is needed but is it known?model error in maximum likelihoodand Bayes methods rarely differ3) Estimation errorconsequence of having a finite sampleÆ can be decreased by increasing the training sampleThere are theoretical and methodological argumentssupporting Bayesian methods- but in reality, maximum likelihood estimation is simplerand leads to classifiers nearly as accurate as the moredifficult-to-design Bayes classifiers.

Sonka: Pattern Recognition Class64Problems of Dimensionality- classification problems with tens or hundreds offeatures are common- let’s assume that no features are intentionally redundantÆ how classification accuracy depends ondimensionality and amount of training dataÆ what is computational complexity of classifier design

Sonka: Pattern Recognition Class65A) Accuracy, dimension, training sample size- the most useful are features for which the differencebetween means is large relative to the standard deviationsÎ Mahalanobis distance r is used, the larger the distance,the better classificationr2 (µ1 - µ2)T Σ-1 (µ1 - µ2)so for conditionally independent case whenΣ diag (σ12, σ22, , σd2) squared Mahalanobis distance isr2 Σi 1d [ (µi1 - µi2) / σi ]2Î each feature contributes to an increase of r2 improve classification- but it also says that no feature is useless as long as itsmeans differ BUT

Sonka: Pattern Recognition Class66 BUT beyond certain point, adding new features frequentlycauses decrease of performance, not improvement.B) Computational Complexitygi(x) -1/2(x-µi)T Σi-1 (x-µi) - (d/2)log(2π) - (1/2)log Σi O(dn) O(nd2) O(1) O(d2n)Î this is done for each classÆ Overall complexity for Bayes learning O(cd2n)Î earlier we saw that we need large training samplesÆ obvious “cost” associated with large n

Sonka: Pattern Recognition Class67Æ Classification complexity is much lower[computing (x-µi) ] Î O(d) complexity linearplusmultiplication of inverse covariance matrix by separationvector O(d2)plusdo it for all c classes for small “c” it is still O(d2)Î MUCH less costly than learning

Sonka: Pattern Recognition Class68C) OverfittingIf a number of available samples is not sufficient, thenumber of features may be too large to be supported bythe small sample set Î overfitting occurs, classifierdoes not generalize, rather it memorizes the training set.Solutions:- reduce dimensionality of feature set- remove features- combine features (K-L transform)- assume that all c classes have the same covariancematrix and pool available data- improve estimate of Σ

Sonka: Pattern Recognition Class69Problems of Parametric Approaches:- the form of the distribution is not known- the form of the distribution does not fit knownestimation approachesNonparametric Approaches1) Direct estimation of p(x wi)based on a generalized multidimensionalhistogram2) Direct estimation of P(wj x)3) Transform of the Feature Spacehope that learning will be easier in the transformedspace

Sonka: Pattern Recognition Class70Nonparametric Density Estimationdivide the feature space in regions Rvector x falling in region R .P(x R) R p(x’)dx’ POver R, P represents smoothed measure of density p(x).Assuming that p(x) is constant over R, estimating Presults in the estimate of p(x).

Sonka: Pattern Recognition Class71Assume n independently drawn samples of PDF p(x) thatcharacterize class wi - samples are available in thetraining set Hi.Probability that k out of n of these samples fall intoregion R is given by binomial distribution for large“n”, the binomials peak strongly at true probability.

Sonka: Pattern Recognition ClassExample:6 coins - how many heads .P(0 of 6) 1/64P(1 of 6) 6/64P(2 of 6) 15/64P(3 of 6) 20/64P(4 of 6) 15/64P(5 of 6) 6/64P(6 of 6) 1/64Obviously, assuming P 1/2 µ 6P 3σ2 nP (1-P) 6 (1/2) (1 - 1/2) 3/272

Sonka: Pattern Recognition Class73P(k of n vectors R) is large for k nP. It is smallotherwise. Let’s not consider the small numbers .Therefore, it is likely that the observed number of vectorsfalling into region R is only the result of the mean therefore, kobserved nP.Thus, estimate for P:P kobserved/nTherefore, for class wi, using training set Hi, if n samplesfall in region R with volume Vn,we estimate the PDF as

Sonka: Pattern Recognition Class74pn(x) kn / (n Vn)We are interested in convergence of p(x) as n .Volume V of the region R cannot be too small since thenthe estimates p(x) would vary from region to region . weneed the smoothing effect.What is the optimal size? 2 strategies:1) shrinking regions . Parzen windows2) growing regions . Nearest neighbor method

Sonka: Pattern Recognition Class75Parzen WindowsLet the regions Rn be d-dimensional hypercubes withedge-dimension hn. Let Vn (hn)d be centered at x.Using d-dimensional step function, the d-dimensionalfeature space is divided into the hypercube and the rest ofspace thus facilitating to count the samples in regions R.

Sonka: Pattern Recognition Class76Training set with n samples . the number of samples inthe hypercube region centered at x is(for “0” outside of the cube and “1” inside of the cube)If we view φ as an interpolation function for pn(x) anddefinepn(x) can be calculated as

Sonka: Pattern Recognition Class77If hn is large . heavy smoothing, insensitive to localvariations in xIf hn is small . sharp peaks of δn(x) at x 0, if the trainingset is not infinite, we have not covered entire Rd .erroneous estimates of pn(x) . erroneous results.

Sonka: Pattern Recognition Class78

Sonka: Pattern Recognition Class79

Sonka: Pattern Recognition ClassÎ many samples are required to get a good estimate80

Sonka: Pattern Recognition Class81How to shrink the regions?E.g., using iteration-driven volume determination, selectstarting volume V0, shrink with increased number ofsamples in the training setVn V0 / sqrt(n)However, again, everything depends on the selection ofV0. Additionally, if data do not cover the feature spaceequally, many regions will not contain samples and theestimate of p(x) will be erroneous.Î no single size is optimal

Sonka: Pattern Recognition Class82Maybe, the region size should be a function of the sampledata:k-NN Nonparametric Estimation1) form some number of regions, each centered around alocation x Rd.Then, increase region’s size until it contains kn nearestneighbor samples, kn is a function of n.If the density around x is high - the region will be smalland vice versa.Important . we are using single-class training sets Hi

Sonka: Pattern Recognition Class83Direct estimation of P(wi x)suppose we captured ki samples from class wi inregion R with volume V joint probability pn(x,wi)k total number of samples in all classes in volume V

Sonka: Pattern Recognition Class84NNR Nearest neighbor rulekeep in memory all samples from the training set1-N

Sonka: Pattern Recognition Class 29 Then, the expected classification risk (conditional risk) for feature vector x is: R(αi x) Σj 1 c λ(αi wj) P(wj x) For each particular observation x, the classification risk can be minimized by choosing action ai that minimizes the conditional risk. for 2 classes action dependent on x [action α(x) ]