Bayes Error Rate and Error Bounds Receiver Operating Characteristics Discrete Features Missing FeaturesExample of Bayes Decision BoundaryBayes Error RateError Bounds for Normal DensitiesChernoff BoundBhattacharya BoundExample of Bhattacharya boundwith normal densitiesReceiver Operating CharacteristicsFour Types of Probability in Two-Class DiscriminationBayes Decision Theory: Discrete FeaturesBayes Decision Theory – Discrete FeaturesIndependent Binary FeaturesBayes discriminant function for Independent Binary Features:Bayesian Decisions for 3-D Binary DataMissing and Noisy FeaturesNoisy FeaturesCSE 555: Srihari 0Bayes Decision TheoryBayes Error Rate and Error Bounds Receiver Operating CharacteristicsDiscrete FeaturesMissing FeaturesCSE 555: Srihari 1Example of Bayes Decision BoundaryTwo Gaussian distributions each with four data pointsx24µ1-2 6 81022∑∑⎟⎟⎠⎞⎜⎜⎝⎛=⎥⎦⎤⎢⎣⎡−=⎟⎟⎠⎞⎜⎜⎝⎛=⎥⎦⎤⎢⎣⎡=22112002 232002/1 63µµµ221121865.0125.1514.3 xxx +−=x1Inverse Matrices∑∑⎟⎟⎠⎞⎜⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛=1-21-12/1002/12/1002 Decision Boundary assumesP(ω1) = P(ω2) = 0.5CSE 555: Srihari 2Bayes Error RateTwo Class CaseMulti-Class CaseComponents of P(error) for equal priorsand non-optimal decision point x*optimalStated for the multidimensionalcase (regions R1and R2not easyto specify)CSE 555: Srihari 3Error Bounds for Normal Densities•Evaluation of Error Integrals difficult•Discontinuous decision regions•Instead, obtain bounds on error rate•Useful inequality in obtaining a bound•Minimum of two integers is smaller than the square root of their product, more generally•Proof:10 and 0,for ],min[1≤≤≥≤−βββbabababbabbbababa≥≥≥≥−ββββ1or )/(or 1)/( then IfCSE 555: Srihari 4Chernoff Bound1( ≤0for )|()|()()( )211211≤≤∫−−βωωωωββββdxxpxpPPerrorPNote that integral is over all space–limits. If conditional probabilities are normal, the integral can beevaluated analytically, yieldingno need to impose integration)(211 )|()|(βββωωkedxxpxp−−=∫CSE 555: Srihari 5Bhattacharya Bound•Special case of Chernoff bound where β = 0.5CSE 555: Srihari 6Chernoff bound is never looser than the Bhattacharya bound.Here Chernoff bound is at β* = 0.66 and is slightly tighterthan the Bhattacharya bound (β = 0.5)Bhattacharya versus Chernoff Error Bounds(as value of βis varied)CSE 555: Srihari 7Example of Bhattacharya boundwith normal densitiesx2k(1/2) = 4.06P(error) < 0.00874µ1-2 6 81022x1∑∑⎟⎟⎠⎞⎜⎜⎝⎛=⎥⎦⎤⎢⎣⎡−=⎟⎟⎠⎞⎜⎜⎝⎛=⎥⎦⎤⎢⎣⎡=22112002 232002/1 63µµµ2CSE 555: Srihari 8Receiver Operating Characteristics•Distance between Gaussian distributions useful in experimental psychology, radar detection, medical diagnosis•Interested in detecting a weak pulse, or dim flash of light•Detector detects a signal whose mean value is µ1when signal is absent and µ2when signal is present),(~)/(2σµωiiNxpCSE 555: Srihari 9Four Types of Probability in Two-Class DiscriminationHit ProbabilityFalse AlarmMissCorrectRejectionDiscriminabilityσµµ||'12−=dWhen no signal present: p(x/ω1) ~ N(µ1,σ 2)When signal present: p(x/ω1) ~ N(µ1,σ 2)Decision threshold determines probabilities of hit and false alarmCSE 555: Srihari 10ROC CurveWhen no signal present: p(x/ω1) ~ N(µ1,σ 2)When signal present: p(x/ω1) ~ N(µ1,σ 2)Decision threshold determines probabilities of hit and false alarmProbability ofFalse AlarmProbabilityof Hitσµµ||'12−=dCSE 555: Srihari 11ROCs need not be symmetric when distributions are not GaussianProbability ofFalse AlarmProbabilityof HitCSE 555: Srihari 12Bayes Decision Theory: Discrete FeaturesCSE 555: Srihari 13Bayes Decision Theory – Discrete Features•Components of x are binary or integer valued, x can take only one of m discrete values v1, v2, …, vm•Probability Density Functions replaced by Probabilities)()|P(xP(x)where)()()|()|(jc1jjωωωωωPxPPxPxPjjj∑===CSE 555: Srihari 14Independent Binary Features2 category problemLet x = [x1, x2, …, xd]twhere each xiis either 0 or 1, with probabilities:pi= p(xi= 1 | ω1)qi= p(xi= 1 | ω2)Assuming Conditional IndependenceiiiixidixixidixiqqxPppxP−=−=−=−=∏∏112111)1()|(and)1()|(ωω( )( )iixiidixiiqpqpxPxP−=−−=∏112111)|()|(ωωCSE 555: Srihari 15Bayes discriminant function for Independent Binary Features:0g(x) if and0 g(x) if decide)(P)(Plnq1p1lnw :andd,...,1i )p1(q)q1(plnw :wherewxw)x(g2121d1iii0iiiii0id1ii≤>+−−==−−=+=∑∑==ωωωωCSE 555: Srihari 16Bayesian Decisions for 3-D Binary Data3,2,1for 5.0 8.05.0)()(21=====iqpPPiiωω 0w333==qp 0)(=xgCSE 555: Srihari 17Missing and Noisy FeaturesFeatures are corrupted by a known noise sourceEx: variability of light source may degrade measurement of lightnessFeatures are missingEx: occlusion prevents measurement of lengthCSE 555: Srihari 18Missing FeatureChoosing mean of missing feature (over all classes)will result in worse performance!Four categories with equal priors and class-conditionaldistributions. Here x1is missing and the other has value x2We want to classify as ω2since it has the largest likelihoodExample of Missing FeatureCSE 555: Srihari 19Missing Feature Analysisgood features xgbad features (unknown or missing) xbMarginalize over all values of missing featureThis is the Bayes Discriminant FunctionCSE 555: Srihari 20Noisy Features•Uncorrupted good features xg•Noise model p(xb|xt)•xt= True value of the Observed value xb•Assume if xtwere known xbwould be independent of wiand xgIntegral is weightedby the noise