Classifier Combination for BiometricsVoting Example (1)Candidate ACandidate BCandidate CVoter 1Voter 2Voter NABC• Each candidate is a class.• Each voter is a classifier.• The voting problem is to define the type of voter’s output and to combine the results of the vote.Voting Example (2)Majority voting:each voter can vote for one candidate; candidate with biggest number of votes wins.Suppose:200 voters – A > C > B195 voters – B > C > A20 voters – C > B > AIs C the worst candidate? Consider candidates in pairs:C and A : 215 voters for C and 200 for AC and B : 220 voters for C and 195 for BVoting Example (3)Borda ( 18thcentury) count:Each voter gives to the first choice candidate 2 points, 1 point to second choice and 0 for third choice candidate.In our example:A – 400 points, B – 410 and C – 435 points.Approval voting :Each voter gives one point to every candidate he approves, and no points for others.Voting Example (4)• Additional modifications:• See http://en.wikipedia.org/wiki/Category:Voting_systems• Multi-stage votes• Confidence vote• Main problem with defining voting methods:What is the ‘true class’ or ‘true candidate’ ?Combination ProblemsClassifiercombinationOther fusionapplication(combining non-classifierexpert estimates – non-generic application problems)Non-ensemblecombinationsClassifierEnsembles(large number of automatically generated classifiers of the same type)Large number of classesSmall number of classes(Easily solved by constructing a secondary classifier in a score space)• Verification Problems• Identification Problems• Biometric Applications• Handwriting ApplicationsMulti-Biometrics Single biometric may not be  Secure Provide sufficient coverage Accurate EfficientFusionMultiple TokensMultiple ModesMultiple MatchersMultiple SensorsMultiple FingersMultiple SamplesCombination of biometric matchersFingerprint matchingHand geometry matchingSignature matchingAlice Bob :2612 :Alice Bob :0.310.45 :Alice Bob :5.547.81 :Alice Bob :0.950.11 :Combination algorithm• Criteria for classifier combination- performance on training/testing sets.• Classifiers can produce different types of scores – integers, floatsTypes of classifiers and type conversion• Combination methods usually accept input of one type.• If combined classifiers produce different type of input, then conversion is required.Example of scoresOutput Type IIIType IIType IConfidence scoresRankingOne class is chosenS(C1)=.4S(C2)=.3….S(Ck)=.05…..S(Cn)=0S(C1)=n-1S(C2)=n-2….S(Ck)=n-k…..S(Cn)=0S(C1)=1S(C2)=0….S(Ck)=0…..S(Cn)=0Combination algorithmsCombination algorithmsOutput valuesClass ranking with confidencescoreClass rankingThe single classSum rule,Neural network.Type IIIBorda countType IIMajority voteType ICombination for identification task•Typical combination method – sum rule:• The person is identified as c, where)()(ijjjiwswS∑=α)(maxargiiwSc=Combination for verification task• It is assumed that there are two classes: person to be verify and all other persons.• Typical combination rule for verification: findand see if for some predefined threshold )()( wswSjjj∑=αθ>)(wSθClassifiers’ score conversion• Scores reflect– Distance measures, confidence values, and beliefs– Typically, represent the distance of a pattern from its prototype in some feature space using some metric• Scores across classifiers are at a different scale• Integration of classifier output with other modules becomes ad hoc• Need for the probability of correctnessScore normalization:ClassifierImageClassesS1S2SnP1P2PnNormalizationClass score example (1)• Teacher A and Teacher B want to evaluate the proficiency of nstudents in Math.• Both teachers give an exam to the students and evaluate their responses.• Student S scores the highest on A’s evaluation: 80%• Student S scores the highest on B’s evaluation: 90% • In the analogy:• Teachers are classifiers• Students are the pattern classes• Input patterns are the examsClass score example (2)• Question 1: Is S the most proficient in Math in the class?• Question 2: Is the opinion of B about Omega’s proficiency stronger than the opinion A has of Omega’s proficiency?• Question 3: Given that A gave 80% as the highest score, what is the probability that he is correct in choice of best student?• Answer 1: If S can consistently rank first over many exams of “same” difficulty• Answer 2: Study the grading behavior of the teachers over many exams• Answer 3: Use rankings, not scores. Derive the probability of correctness from scoreUsing rankings instead of scoresRanked lexiconwith distance scoresBryant 1.5Boston 1.8Bidwell 2.6James 4.7Buffalo 8.9..SignalBostonBuffaloWilliamsvilleBidwellJamesByrant..ContextLexiconWord Recognition EngineBryant 2.5Boston 2.8Bidwell 3.6James 5.7Buffalo 9.9..Rankings can be more reliable than scores.Deriving probabilities (1)• Find the a posteriori probabilitiesCLASSIFIER C (Type III)Input patternxN332211s , .. , ,,Nsssωωωω)|( xPiω1)|P(classifier by the returned scores theare ]1,0[N)1(i classes theare 1i=∈=∑=xsNiii……ωω• Instead of consider or even )|( xPiω),,|(1 cissP…ω)|(iisPωDeriving probabilities (2)•Two probability density functions could be used for score normalization:))(|),((iiwxtswxCp==- score distribution when truth of the input pattern is the same as class wi))(|),((iiwxtswxCp≠=- score distribution when truth of the input pattern is different from the class wiDeriving probabilities (3)Using these two distributions we can map the recognizer’s score into probability that word is recognized correctly:)),(())(())(|),(()),(|)((iiiiiiwxCpwxtPwxtwxCpwxCwxtP====and))(())(|),(())(())(|),(()),((iiiiiiiwxtPwxtwxCpwxtPwxtwxCpwxCp≠≠+===Histograms to derive probabilities00.050.10.150.20.25ScoresProbabilityCorrect scores Incorrect scores))(|),((iiwxtswxCp==Correct scores distribution is same as ))(|),((iiwxtswxCp≠=Incorrect scores distribution is same asUsing logistic function for score normalizationbasesf++=11)(Logistic function:• f(s) has a range between 0 and 1. Thus it is convenient candidate for modeling probabilities.• We need to find parameters a and b, such that f(s) most closelycoincides with • Finding parameters statistically from given training samples iscalled regression.)|( sPωSummary of Approaches to Score Normalization1. Use rankings instead of