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).

2 , 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. 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).

3 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?

4 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.

5 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. 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).

6 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.

7 1(/) (/ )( /)ciijjjRaaP == xxOverall Risk Suppose (x) is a generaldecision rule that determines which action 1, 2, .., 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.

8 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!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.

9 , 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.

10 , 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.