贝叶斯分类算法

SergiosTheodoridis

KonstantinosKoutroumbasVersion2ACourseon1PATTERNRECOGNITIONTypicalapplicationareasMachinevisionCharacterrecognition(OCR)ComputeraideddiagnosisSpeechrecognitionFacerecognitionBiometricsImageDataBaseretrievalDataminingBionformaticsThetask:Assignunknownobjects–patterns–intothecorrectclass.Thisisknownasclassification.2Features:

Thesearemeasurablequantitiesobtainedfromthepatterns,andtheclassificationtaskisbasedontheirrespectivevalues.

Featurevectors:

Anumberoffeatures

constitutethefeaturevector

Featurevectorsaretreatedasrandomvectors.3Anexample:4Theclassifierconsistsofasetoffunctions,whosevalues,computedat,determinetheclasstowhichthecorrespondingpatternbelongsClassificationsystemoverviewsensorfeaturegenerationfeatureselectionclassifierdesignsystemevaluationPatterns5Supervised–unsupervisedpatternrecognition:

ThetwomajordirectionsSupervised:Patternswhoseclassisknowna-prioriareusedfortraining.Unsupervised:Thenumberofclassesis(ingeneral)unknownandnotrainingpatternsareavailable.6CLASSIFIERSBASEDONBAYESDECISIONTHEORYStatisticalnatureoffeaturevectorsAssignthepatternrepresentedbyfeaturevector

tothemostprobableoftheavailableclasses

Thatis

maximum7Computationofa-posterioriprobabilitiesAssumeknowna-prioriprobabilities

Thisisalsoknownasthelikelihoodof8

TheBayesrule(Μ=2)where9TheBayesclassificationrule(fortwoclassesM=2)Given classifyitaccordingtotheruleEquivalently:classify accordingtotheruleForequiprobableclassesthetestbecomes1011Equivalentlyinwords:Dividespaceintworegions

ProbabilityoferrorTotalshadedarea

BayesianclassifierisOPTIMALwithrespecttominimisingtheclassificationerrorprobability!!!!12Indeed:MovingthethresholdthetotalshadedareaINCREASESbytheextra“grey〞area.13TheBayesclassificationruleformany(M>2)classes:Givenclassifyittoif:SuchachoicealsominimizestheclassificationerrorprobabilityMinimizingtheaverageriskForeachwrongdecision,apenaltytermisassignedsincesomedecisionsaremoresensitivethanothers14ForM=2Definethelossmatrix

penaltytermfordecidingclass,

althoughthepatternbelongsto,etc.Riskwithrespectto15Riskwithrespectto

AverageriskProbabilitiesofwrongdecisions,weightedbythepenaltyterms16Chooseandsothatr

isminimizedThenassigntoifEquivalently:

assignxin if :likelihoodratio17If18Anexample:19Thenthethresholdvalueis:Threshold forminimumr20Thusmovestotheleftof(WHY?)21DISCRIMINANTFUNCTIONS

DECISIONSURFACESIf arecontiguous: isthesurfaceseparatingtheregions.Ononesideispositive(+),ontheotherisnegative(-).ItisknownasDecisionSurface+

-22Iff(.)monotonic,theruleremainsthesameifweuse: isadiscriminantfunctionIngeneral,discriminantfunctionscanbedefinedindependentof

theBayesianrule.Theyleadtosuboptimalsolutions,yetifchosenappropriately,canbecomputationallymoretractable.23BAYESIANCLASSIFIERFORNORMALDISTRIBUTIONSMultivariateGaussianpdfcalledcovariancematrix24ismonotonic.Define:

Example:

25

Thatis, isquadraticandthesurfacesquadrics,ellipsoids,parabolas,hyperbolas,

pairsoflines.Forexample:26DecisionHyperplanesQuadraticterms: IfALL (thesame)thequadratictermsarenotofinterest.Theyarenotinvolvedincomparisons.Then,equivalently,wecanwrite: DiscriminantfunctionsareLINEAR

27Letinaddition:

28Nondiagonal:

Decisionhyperplane29MinimumDistanceClassifiersequiprobable

EuclideanDistance:

smaller

MahalanobisDistance:

smaller3031Example:32MaximumLikelihood

ESTIMATIONOFUNKNOWNPROBABILITY

DENSITYFUNCTIONS33

3435

Asymptoticallyunbiasedandconsistent36Example:37MaximumAposterioriProbabilityEstimationInMLmethod,θwasconsideredasaparameterHereweshalllookatθasarandomvectordescribedbyapdfp(θ),assumedtobeknownGiven ComputethemaximumofFromBayestheorem38Themethod:3940Example:41BayesianInference

4243TheaboveisasequenceofGaussiansas

MaximumEntropyEntropy

44Example:

x

isnonzerointheinterval

andzerootherwise.ComputetheMEpdfTheconstraint:LagrangeMultipliers

45

MixtureModels

Assumeparametricmodeling,i.e.,Thegoalistoestimate givenasetWhynotML?Asbefore?46Thisisanonlinearproblemduetothemissinglabelinformation.Thisisatypicalproblemwithanincompletedataset.TheExpectation-Maximisation(EM)algorithm.Generalformulation

whichare

notobserveddirectly.

Weobserve

amanytoonetransformation47LetWhatweneedistocomputeBut arenotobserved.HerecomestheEM.Maximizetheexpectationoftheloglikelihood

conditionedontheobservedsamplesandthecurrentiterationestimateof48Thealgorithm:E-step:M-step:ApplicationtothemixturemodelingproblemCompletedataObserveddata

Assumingmutualindependence49UnknownparametersE-stepM-step

50NonparametricEstimation

51ParzenWindowsDividethemultidimensionalspaceinhypercubes52DefineThatis,itis1insideaunitsidehypercubecenteredat0

Theproblem:Parzenwindows-kernels-potentialfunctions53Meanvalue

Henceunbiasedinthelimit54VarianceThesmallerthehthehigherthevarianceh=0.1,N=1000h=0.8,N=100055h=0.1,N=10000ThehighertheNthebettertheaccuracy56If

asymptoticallyunbiasedThemethodRemember:

57CURSEOFDIMENSIONALITYInallthemethods,sofar,wesawthatthehighestthenumberofpoints,

N,thebettertheresultingestimate.Ifintheone-dimensionalspaceaninterval,filledwith

N

points,isadequately(forgoodestimation),inthetwo-dimensionalspacethecorrespondingsquarewillrequireN2

andintheℓ-dimensionalspacetheℓ-dimensionalcubewillrequireNℓpoints.Theexponentialincreaseinthenumberofnecessarypointsinknownasthecurseofdimensionality.Thisisamajorproblemoneisconfrontedwithinhighdimensionalspaces.58NAIVE–BAYESCLASSIFIERLetandthegoalistoestimate i=1,2,…,M.Fora“good〞estimateofthepdfonewouldneed,say,Nℓpoints.Assumex1,x2,…,xℓmutuallyindependent.Then:Inthiscase,onewouldrequire,roughly,Npointsforeachpdf.Thus,anumberofpointsoftheorderN·ℓwouldsuffice.ItturnsoutthattheNaïve–Bayesclassifierworksreasonablywellevenincasesthatviolatetheindependenceassumption.59KNearestNeighborDensityEstimationInParzen:ThevolumeisconstantThenumberofpointsinthevolumeisvaryingNow:Keepthenumberofpoints

constantLeavethevolumetobevarying

60

61TheNearestNeighborRuleChoosekoutoftheNtrainingvectors,identifytheknearestonestoxOutofthesekidentifykithatbelongtoclassωi

Thesimplestversion

k=1!!!ForlargeNthisisnotbad.Itcanbeshownthat:

ifPBistheoptimalBayesianerrorprobability,then:62

ForsmallPB:63Voronoitesselation64BayesProbabilityChainRuleAssumenowthattheconditionaldependenceforeachxi

islimitedtoasubsetofthefeaturesappearingineachoftheproductterms.Thatis: where

BAYESIANNETWORKS65Forexample,ifℓ=6,thenwecouldassume: Then:TheaboveisageneralizationoftheNaïve–Bayes.FortheNaïve–Bayestheassumptionis:Ai=Ø,fori=1,2,…,ℓ66AgraphicalwaytoportrayconditionaldependenciesisgivenbelowAccordingtothisfigurewehavethat:x6isconditionallydependentonx4,x5.x5

on

x4

x4

on

x1,x2x3

on

x2x1,x2

areconditionally

independentonothervariables.Forthiscase:67BayesianNetworksDefinition:ABayesianNetworkisadirectedacyclic

graph(DAG)wherethenodescorrespondtorandomvariables.Eachnodeisassociatedwithasetofconditionalprobabilities(densities),p(xi|Ai),wherexi

isthevariableassociatedwiththenodeandAi

isthesetofitsparentsinthegraph.ABayesianNetworkisspecifiedby:Themarginalprobabilitiesofitsrootnodes.Theconditionalprobabilitiesofthenon-rootnodes,giventheirparents,forALLpossiblecombinations.68ThefigurebelowisanexampleofaBayesianNetworkcorrespondingtoaparadigmfromthemedicalapplicationsfield.ThisBayesiannetworkmodelsconditionaldependenciesforanexampleconcerningsmokers(S),tendenciestodevelopcancer(C)andheartdisease(H),togetherwithvariablescorrespondingtoheart(H1,H2)andcancer(C1,C2)medicaltests.69OnceaDAGhasbeenconstructed,thejointprobabilitycanbeobtainedbymultiplyingthemarginal(rootnodes)andtheconditional(non-rootnodes)probabilities.Training:Onceatopologyisgiven,probabilitiesareestimatedvia