1CSE190a Fall 06Pattern classificationBiometricsCSE 190-aLecture 3Pattern ClassificationPattern Classification, Chapter 13An Example• “Sorting incoming Fish on a conveyor according to species using optical sensing”Sea bassSpeciesSalmonPattern Classification, Chapter 14• Problem Analysis• Set up a camera and take some sample images to extract features• Length• Lightness• Width• Number and shape of fins• Position of the mouth, etc…• This is the set of all suggested features to explore for use in our classifier!Pattern Classification, Chapter 15Pattern Classification, Chapter 16• Classification• Select the length of the fish as a possible feature for discrimination2Pattern Classification, Chapter 17ClassificationSelect the length of the fish as a possible feature for discriminationPattern Classification, Chapter 18The length is a poor feature alone!Select the lightness as a possible feature.Pattern Classification, Chapter 19Pattern Classification, Chapter 110• Adopt the lightness and add the width of the fishFish xT= [x1, x2]LightnessWidthPattern Classification, Chapter 111Pattern Classification, Chapter 112• We might add other features that are not correlated with the ones we already have. A precaution should be taken not to reduce the performance by adding such “noisy features”• Ideally, the best decision boundary should be the one which provides an optimal performance such as in the following figure:3Pattern Classification, Chapter 113Pattern Classification, Chapter 114• However, our satisfaction is premature because the central aim of designing a classifier is to correctly classify novel input Issue of generalization!Pattern Classification, Chapter 115Bayesian Decision TheoryContinuous Features (Sections 2.1-2.2) Pattern Classification, Chapter 117Introduction• The sea bass/salmon example• State of nature, prior• State of nature is a random variable• The catch of salmon and sea bass is equiprobable• P(ω1), P(ω2) Prior probabilities• P(ω1) = P(ω2) (uniform priors)• P(ω1) + P( ω2) = 1 (exclusivity and exhaustivity)Pattern Classification, Chapter 118• Decision rule with only the prior information• Decide ω1if P(ω1) > P(ω2) otherwise decide ω2• Use of the class–conditional information• P(x | ω1) and P(x | ω2) describe the difference in lightness between populations of sea-bass and salmon4Pattern Classification, Chapter 119Pattern Classification, Chapter 120• Posterior, likelihood, evidence• P(ωj| x) = (P(x | ωj) * P (ωj)) / P(x) (BAYES RULE)• In words, this can be said as:Posterior = (Likelihood * Prior) / Evidence• Where in case of two categories ∑===21)()|()(jjjjPxPxPωωPattern Classification, Chapter 121Pattern Classification, Chapter 122• Intuitive decision rule given the posterior probabilities:Given x:if P(ω1| x) > P(ω2| x) True state of nature = ω1if P(ω1| x) < P(ω2| x) True state of nature = ω2Why do this?: Whenever we observe a particular x, the probability of error is :P(error | x) = P(ω1| x) if we decide ω2P(error | x) = P(ω2| x) if we decide ω1Pattern Classification, Chapter 123• Since decision rule is optimal for each feature value X, there is not better rule for all x.Pattern Classification, Chapter 124Bayesian Decision Theory – Continuous FeaturesGeneralization of the preceding ideas• Use of more than one feature• Use more than two states of nature• Allowing actions and not only decide on the state of nature• Introduce a loss of function (more general than the probability of error)• Allowing actions other than classification primarily allows the possibility of rejection• Refusing to make a decision in close or bad cases!• Letting loss function state how costly each action taken is5Pattern Classification, Chapter 125• Let X be a vector of features.• Let {ω1, ω2,…, ωc} be the set of c states of nature (or “classes”)• Let {α1, α2,…, αa} be the set of possible actions• Let λ(αi| ωj) be the loss for action αiwhen the state of nature is ωjBayesian Decision Theory – Continuous FeaturesPattern Classification, Chapter 126What is the Expected Loss for action αi?R(αi| x) is called the Conditional Risk (or Expected Loss)∑===cj1jjjii)x|(P)|()x|(RωωαλαFor any given x the expected loss isPattern Classification, Chapter 127Overall riskR = Sum of all R(αi| x) for i = 1,…,aMinimizing R Minimizing R(αi| x) for i = 1,…, afor i = 1,…,aConditional risk∑===cj1jjjii)x|(P)|()x|(RωωαλαPattern Classification, Chapter 128Given a measured feature vector x, which actiion should we take?Select the action αifor which R(αi| x) is minimumR is minimum and R in this case is called the Bayes risk = best performance that can be achieved!Pattern Classification, Chapter 129Two-Category Classificationα1: deciding ω1α2: deciding ω2λij= λ(αi|ωj)loss incurred for deciding ωiwhen the true state of nature is ωjConditional risk:R(α1| x) = λ11P(ω1| x) + λ12P(ω2| x)R(α2| x) = λ21P(ω1 | x) + λ22P(ω2| x) Pattern Classification, Chapter 130Our rule is the following:if R(α1| x) < R(α2| x) λ11P(ω1| x) + λ12P(ω2| x) < λ21P(ω1 | x) + λ22P(ω2| x)action α1: “decide ω1” is takenThis results in the equivalent rule :decide ω1if:(λ21-λ11) P(x | ω1) P(ω1) >(λ12-λ22) P(x | ω2) P(ω2)and decideω2otherwise6Pattern Classification, Chapter 131x (λ21-λ11)x (λ12-λ22)Pattern Classification, Chapter 132Two-Category Decision Theory: Chopping Machineα1= chop α2= DO NOT chop ω1 = NO hand in machineω2= hand in machineλ11 = λ(α1|ω1) = $ 0.00λ12 = λ(α1|ω2) = $ 100.00λ21 = λ(α2|ω1) = $ 0.01λ22 = λ(α1|ω1) = $ 0.01Therefore our rule becomes(λ21-λ11) P(x | ω1) P(ω1) > (λ12-λ22) P(x | ω2) P(ω2)0.01 P(x | ω1) P(ω1) > 99.99 P(x | ω2) P(ω2)Pattern Classification, Chapter 133x 0.01x 99.99α1= chop α2= DO NOT chop ω1= NO hand in machineω2= hand in machinePattern Classification, Chapter 134Exercise to do at home!!Select the optimal decision where:Ω= {ω1, ω2}P(x | ω1) N(2, 0.5) (Normal distribution)P(x | ω2) N(1.5, 0.2)P(ω1) = 2/3P(ω2) = 1/3⎥⎦⎤⎢⎣⎡=λ4321 Pattern Classification, Chapter 135Minimum-Error-Rate Classificationrevisited• Actions are decisions on classesIf action αiis taken and the true state of nature is ωjthenthe decision is correct if i = j and in error if i ≠j• Seek a decision rule that minimizes the probability of