模式識別課件prch5part1ding.ppt

PatternClassificationAllmaterialsintheseslidesweretakenfromPatternClassification 2nded byR O Duda P E HartandD G Stork JohnWiley Sons 2000withthepermissionoftheauthorsandthepublisher Chapter5 LinearDiscriminantFunctions Sections5 1 5 3 IntroductionLinearDiscriminantFunctionsandDecisionsSurfacesGeneralizedLinearDiscriminantFunctions 2 5 1Introduction Inchapter3 theunderlyingprobabilitydensitieswereknown Thetrainingsamplewasusedtoestimatetheparametersoftheseprobabilitydensities ML MAPestimations Inthischapter weonlyknowtheproperformsforthelineardiscriminantfunctions andusesamplestoestimatethevaluesofparametersforthediscriminantfunctions similartonon parametrictechniquesTheymaynotbeoptimal buttheyareverysimpleandeasytocomputetheyarechosenascandidatesforinitialandtrialclassifiersespeciallyintheabsenceofinformation 3 Theproblemoffindingalineardiscriminantfunctionwillbeformulatedasaproblemacriterionfunction 4 5 2Lineardiscriminantfunctionsanddecisionssurfaces Definition Itisafunctionthatisalinearcombinationofthecomponentsofxg x wtx w0 1 wherewistheweightvectorandw0thebias thresholdweight Atwo categoryclassifierwithadiscriminantfunctionoftheform 1 usesthefollowingrule Decide 1ifg x 0and 2ifg x w0and 2otherwiseIfg x 0 xisassignedtoeitherclass 5 6 Theequationg x 0definesthedecisionsurfacethatseparatespointsassignedtothecategory 1frompointsassignedtothecategory 2Wheng x islinear thedecisionsurfaceisahyperplaneAlgebraicmeasureofthedistancefromxtothehyperplane 7 8 Inconclusion alineardiscriminantfunctiondividesthefeaturespacebyahyperplanedecisionsurfaceTheorientationofthesurfaceisdeterminedbythenormalvectorwandthelocationofthesurfaceisdeterminedbythebias 9 Themulti categorycaseWedefineclineardiscriminantfunctionsandassignxto iifgi x gj x j i incaseofties theclassificationisundefinedInthiscase theclassifierisa linearmachine Alinearmachinedividesthefeaturespaceintocdecisionregions withgi x beingthelargestdiscriminantifxisintheregionRiForatwocontiguousregionsRiandRj theboundarythatseparatesthemisaportionofhyperplaneHijdefinedby gi x gj x wi wj tx wi0 wj0 0wi wjisnormaltoHijand 10 11 Itiseasytoshowthatthedecisionregionsforalinearmachineareconvex thisrestrictionlimitstheflexibilityandaccuracyoftheclassifier 12 5 3GeneralizedLinearDiscriminantFunctions DecisionboundarieswhichseparatebetweenclassesmaynotalwaysbelinearThecomplexityoftheboundariesmaysometimesrequesttheuseofhighlynon linearsurfacesApopularapproachtogeneralizetheconceptoflineardecisionfunctionsistoconsiderageneralizeddecisionfunctionas g x w1f1 x w2f2 x wNfN x wN 1 1 wherefi x 1 i Narescalarfunctionsofthepatternx x Rn EuclideanSpace 13 Introducingfn 1 x 1weget Thislatterrepresentationofg x impliesthatanydecisionfunctiondefinedbyequation 1 canbetreatedaslinearinthe N 1 dimensionalspace N 1 n g x maintainsitsnon linearitycharacteristicsinRn 14 Themostcommonlyusedgeneralizeddecisionfunctionisg x forwhichfi x 1 i N arepolynomialsQuadraticdecisionfunctionsfora2 dimensionalfeaturespace 15 Forpatternsx Rn themostgeneralquadraticdecisionfunctionisgivenby Thenumberoftermsattheright handsideis ThisisthetotalnumberofweightswhicharethefreeparametersoftheproblemIfforexamplen 3 thevectoris10 dimensionalIfforexamplen 10 thevectoris66 dimensional 16 Inthecaseofpolynomialdecisionfunctionsoforderm atypicalfi x isgivenby Itisapolynomialwithadegreebetween0andm Toavoidrepetitions werequesti1 i2 im whereg0 x wn 1 isthemostgeneralpolynomialdecisionfunctionoforderm 17 Example1 Letn 3andm 2then Example2 Letn 2andm 3then 18 Thecommonlyusedquadraticdecisionfunctioncanberepresentedasthegeneraln dimensionalquadraticsurface g x xTAx xTb cwherethematrixA aij thevectorb b1 b2 bn Tandc dependsontheweightswii wij wiofequation 2 IfAispositivedefinitethenthedecisionfunctionisahyperellipsoidwithaxesinthedirectionsoftheeigenvectorsofAInparticular ifA In Identity thedecisionfunctionissimplythen dimensionalhypersphere 19 IfAisnegativedefinite thedecisionfunctiondescribesahyperboloidInconclusion itisonlythematrixAwhichdeterminestheshapeandcharacteristicsofthedecisionfunction 20 Problem Considera3dimensionalspaceandcubicpolynomialdecisionfunctionsHowmanytermsareneededtorepresentadecisionfunctionifonlycubicandlinearfunctionsareassumedPresentthegeneral4thorderpolynomialdecisionfunctionfora2dimensionalpatternspaceLetR3betheoriginalpatternspaceandletthedecisionfunctionassociatedwiththepatternclasses 1and 2be forwhichg x 0ifx 1andg x 0ifx 2Rewriteg x asg x xTAx xTb cDeterminetheclassofeachofthefollowingpatternvectors 1 1 1 1 10 0 0 1 2 0 21 PositiveDefiniteMatricesAsquarematrixAispositivedefiniteifxTAx 0forallnonzerocolumnvectorsx ItisnegativedefiniteifxTAx 0forallnonzerox Itispositivesemi definiteifxTAx 0 Andnegativesemi definiteifxTAx 0forallx Thesedefinitionsarehardtocheckdirectlyandyoumightaswellforgetthemforallpracticalpurposes 22 Moreusefulinpracticearethefollowingproperties whichholdwhenthematrixAissymmetricandwhichareeasiertocheck TheithprincipalminorofAisthematrixAiformedbythefirstirowsandcolumnsofA So thefirstprincipalminorofAisthematrixAi a11 thesecondprincipalminoristhematrix 23 ThematrixAispositivedefiniteifallitsprincipalminorsA1 A2 AnhavestrictlypositivedeterminantsIfthesedeterminantsarenon zeroandalternateinsigns startingwithdet A1 0 thenthematrixAisnegativedefiniteIfthedeterminantsareallnon negative thenthematrixispositivesemi definiteIfthedeterminantalternateinsigns startingwithdet A1 0 thenthematrixisnegativesemi definite 24 Tofixideas considera2x2symmetricmatrix Itispositivedefiniteif det A1 a11 0det A2 a11a22 a12a12 0Itisnegativedefiniteif det A1 a110Itispositivesemi definiteif det A1 a11 0det A2 a11a22 a12a12 0Anditisnegativesemi definiteif det A1 a11 0det A2 a11a22 a12a12 0 25 Exercise1 Checkwhetherthefollowingmatricesarepositivedefinite negativedefinite positivesemi definite negativesemi definiteornoneoftheabove 26 SolutionsofExercise1 A1 2 0A2 8 1 7 0 AispositivedefiniteA1 2A2 2x 8 16 0 Aisnegativesemi positiveA1 2A2 8 4 4 0 AisnegativedefiniteA1 2 0A2 6 16 10 0 Aisnoneoftheabove 27 Exercise2 LetComputethedecisionboundaryassignedtothematrixA g x xTAx xTb c inthecasewherebT 1 2 andc 3Solvedet A I 0andfindtheshapeandthecharacteristicsofthedecisionboundaryseparatingtwoclasses 1and 2Classifythefollowingpoints xT 0 1 xT 1 1 28 SolutionofExercise2 1 2 Thislatterequationisastraightlinecolineartothevector 29 Thislatterequationisastraightlinecolineartothevector Theellipsisdecisionboundaryhastwoaxes whicharerespectivelycolineartothevectorsV1andV23 X 0 1 T g 0 1 10 x 1