Bayesian Decision Theory - gatech.edu

1 Bayesian Decision TheoryChapter2 (Duda, Hart & Stork)CS 7616 -Pattern RecognitionHenrik I ChristensenGeorgia Tech. Bayesian Decision Theory Design classifiers to recommend decisionsthat minimize some total expected risk . The simplest riskis the classification error ( , costs are equal). Typically, the riskincludes the costassociated with different State of nature (random variable): , 1for sea bass, 2for salmon Probabilities P( 1)and P( 2)(priors): , prior knowledge of how likely is to get a sea bass or a salmon Probability density function p(x) (evidence): , how frequently we will measure a pattern with feature value x( , xcorresponds to lightness) Terminology (cont d) Conditional probability density p(x/ j)(likelihood) : , how frequently we will measure a pattern with feature value xgiven that the pattern belongs to class , lightness distributionsbetween salmon/sea-basspopulationsTerminology (cont d) Conditional probability P( j /x) (posterior) : , the probability that the fish belongs to class jgiven measurement Rule Using Prior ProbabilitiesDecide 1ifP( 1)> P( 2);otherwise decide 2orP(error) = min[P( 1), P( 2)] Favours the most likely class.

2 This rule will be making the same Decision all times. , optimum if no other information is available1221()()()Pif we decidePerrorPif we decide = Decision Rule Using Conditional Probabilities Using Bayes rule, the posterior probability of category jgiven measurement x is given by:where ( , scale factor sum of probs = 1)Decide 1 if P( 1/x) > P( 2 /x);otherwise decide 2orDecide 1 if p(x/ 1)P( 1)>p(x/ 2)P( 2)otherwise decide 2(/)()(/)()jjjpxPlikelihoodpriorPxpxevid ence ==21()(/ ) ( )jjjpxpxP == Decision Rule Using Conditional pdf(cont d)1221()()33PP ==P( j /x)p(x/ j)Probability of Error The probability of error is defined as:or What is the average probability error? The Bayes rule is optimum, that is, it minimizes the average probability error!1221(/)(/)(/)PxifwedecidePerror xPxifwedecide = ()(,)(/)()PerrorPerrorxdxPerrorxpxdx == P(error/x) = min[P( 1/x), P( 2/x)]Where do Probabilities Come From?

3 There are two competitive answers to this question:(1)Relative frequency(objective) approach. Probabilities can only come from experiments.(2) Bayesian (subjective) approach. Probabilities may reflect degree of belief and can be based on (objective approach) Classify cars whether they are more or less than $50K: Classes: C1if price > $50K, C2if price <= $50K Features: x, the heightof a car Use the Bayes rule to compute the posterior probabilities: We need to estimate p(x/C1), p(x/C2), P(C1), P(C2)(/)()(/)()iiipx C PCPC xpx=Example (cont d) Collect data Ask drivers how much their car was and measure height. Determine priorprobabilities P(C1), P(C2) , 1209 samples: #C1=221 #C2=98812221() () (cont d) Determine class conditional probabilities (likelihood) Discretize car height into bins and use normalized histogram(/)ipx CExample (cont d) Calculate the posterior probabilityfor each bin:111112 2( )()(/ )( )()( )() * * * +===+(/)iPC xA More General Theory Use more than one features.

4 Allow more than two categories. Allow actionsother than classifying the input to one of the possible categories ( , rejection). Employ a more general error function ( , risk function) by associating a cost ( loss function) with each error ( , wrong action).Terminology Features form a vector A finite set of ccategories 1, 2, .., c Bayes rule ( , using vector notation): A finite set ofl actions 1, 2, .., l A lossfunction ( i/ j) the costassociated with taking action iwhen the correct classification category is jdR x(/)()(/)()jjjpPPp =xxx1()( / ) ( )cjjjwhereppP == xxConditional Risk (or Expected Loss) Suppose we observe x and take action i Suppose that the cost associated with taking action iwith jbeing the correct category is ( i/ j) The conditional risk(or expected loss) with taking action iis:1(/) (/ )( /)ciijjjRaaP == xxOverall Risk Suppose (x) is a generaldecision rule that determines which action 1, 2.

5 , l to take for every x; then the overall risk is defined as: The optimumdecision rule is the Bayes rule (()/)()RRapd= xxxxOverall Risk (cont d) The Bayes Decision rule minimizes Rby:(i) Computing R( i/x)for every igiven an x(ii) Choosing the action i with the minimum R( i/x) The resulting minimum overall risk is called Bayes riskand is the best ( , optimum) performance that can be achieved: *mi nRR=Example: Two-category classification Define 1: decide 1 2: decide 2 ij = ( i/ j) The conditional risks are:1(/) (/ )( /)ciijjjRaaP == xx(c=2)Example: Two-category classification (cont d) Minimum risk Decision rule:or( , using likelihood ratio) or>thresholdlikelihood ratioSpecial Case:Zero-One Loss Function Assign the same loss to all errors: The conditional risk corresponding to this loss function:Special Case:Zero-One Loss Function (cont d) The Decision rule becomes: In this case, the overall risk is the average probability error!

6 OrorExample21()/()aPP =212 22121 11()()()()bPP = ( Decision regions)Decide 1 if p(x/ 1)/p(x/ 2)>P( 2 )/P( 1)otherwise decide 2 Assuming zero-oneloss:12 21 >>assume:Assuming generalloss:Discriminant Functions A useful way to represent classifiers is throughdiscriminantfunctionsgi(x), i= 1, .. , c, where a feature vector xis assigned to class iif:gi(x) > gj(x)for all ji Discriminants for Bayes Classifier Assuming a general loss function:gi(x)=-R( i / x) Assuming the zero-one loss function:gi(x)=P( i / x)Discriminants for Bayes Classifier (cont d) Is the choice of giunique? Replacing gi(x)with f(gi(x)), where f()is monotonically increasing, does not change the classification results.(/)()()()()(/)()()ln(/)ln()iiiii iiiipPgpgp Pgp P ===+xxxxxxxgi(x)=P( i/x)we ll use thisform extensively!Case of two categories More common to use a single discriminant function (dichotomizer) instead of two: Examples:121122() ( /) ( /)(/ )( )() lnln(/ ) ( )gPPpPgpP = =+xxxxxxDecision Regionsand Boundaries Decision rules divide the feature space in Decision regionsR1, R2.

7 , Rc,separated by Decision boundary is defined by:g1(x)=g2(x) Discriminant Function for Multivariate Gaussian Density Consider the following discriminant function:()ln(/)ln()iiigp P =+xxN( , )p(x/ i)Multivariate Gaussian Density:Case I i= 2(diagonal) Features are statistically independent Each feature has the same variancefavours the a-priorimore likely categoryMultivariate Gaussian Density:Case I (cont d)wi=))Multivariate Gaussian Density:Case I (cont d) Properties of Decision boundary: It passes through x0 It is orthogonal to the line linking the means. What happens when P( i)= P( j)? If P( i)= P( j), then x0shifts away from the most likely category. If is very small, the position of the boundary is insensitive to P( i) andP( j) ))Multivariate Gaussian Density:Case I (cont d)If P( i)= P( j), then x0shifts away from the most likely category. Multivariate Gaussian Density:Case I (cont d)If P( i)= P( j), then x0shifts away from the most likely category.

8 Multivariate Gaussian Density:Case I (cont d)If P( i)= P( j), then x0shifts away from the most likely category. Multivariate Gaussian Density:Case I (cont d) Minimum distance classifier When P( i) are equal, then:2()||||iig = xxmaxMultivariate Gaussian Density:Case II i= Multivariate Gaussian Density:Case II (cont d)Multivariate Gaussian Density:Case II (cont d) Properties of hyperplane ( Decision boundary): It passes through x0 It is notorthogonal to the line linking the means. What happens when P( i)= P( j)? If P( i)= P( j), then x0shifts away from the most likely category. Multivariate Gaussian Density:Case II (cont d)If P( i)= P( j), then x0shifts away from the most likely category. Multivariate Gaussian Density:Case II (cont d)If P( i)= P( j), then x0shifts away from the most likely category. Multivariate Gaussian Density:Case II (cont d) Mahalanobis distance classifier When P( i) are equal, then:maxMultivariate Gaussian Density:Case III i= ,hyperplanes, pairs of hyperplanes, hyperspheres, hyperellipsoids, hyperparaboloidsetc.

9 Hyperquadrics;Example -Case IIIP( 1)=P( 2) Decision boundary:boundary doesnotpass throughmidpoint of 1, 2 Multivariate Gaussian Density:Case III (cont d)non-lineardecisionboundariesMultivaria te Gaussian Density:Case III (cont d) More examples Error Bounds Exact error calculations could be difficult easier to estimate error bounds!or min[P( 1/x), P( 2/x)]P(error) Error Bounds (cont d) If the class conditional distributions are Gaussian, thenwhere:||Error Bounds (cont d) The Chernoffbound corresponds to that minimizese- ( ) This is a 1-D optimization problem, regardless to the dimensionality of the class conditional boundloose boundtight boundError Bounds (cont d) Bhattacharyyabound Approximate the error bound using = Easier to compute than Chernoff error but looser. The Chernoff and Bhattacharyya bounds will not be good bounds if the distributions are ( )= () Bhattacharyyaerror: receiver operating Characteristic (ROC) Curve Every classifier employs some kind of a threshold.

10 Changing the threshold affects the performance of the system. ROC curves can help us evaluate system performance for ()/()aPP =212 22121 11()()()()bPP = Example: Person Authentication Authenticate a person using biometrics ( , fingerprints). There are two possible distributions ( , classes): Authentic(A) and Impostor(I)IAExample: Person Authentication (cont d) Possible decisions: (1) correct acceptance (true positive): X belongs to A, and we decide A (2) incorrect acceptance(false positive): X belongs to I, and we decide A (3) correct rejection (true negative): X belongs to I, and we decide I (4) incorrect rejection(false negative): X belongs to A, and we decide IIAfalse positivecorrect acceptancecorrect rejectionfalse negativeError vs ThresholdROCF alse Negatives vs Positives Next Lecture Linear Classification Methods Hastie et al, Chapter 4 Paper list will available by Weekend Bidding to start on MondayBayes Decision Theory : Case of Discrete Features Replace with See section (/)jpd xx(/)jP xxMissing Features Consider a Bayes classifier using uncorrupted data.