模式识别6资料课件

模式识别原理华中科技大学图像识别与人工智能研究所图像分析与智能系统研究室曹治国7/27/202314.1IntroductionTheseabass/salmonexample

Stateofnature,prior

Stateofnatureisarandomvariable

ThecatchofsalmonandseabassisequiprobableP(1)=P(2)(uniformpriors)

P(1)+P(2)=1(exclusivityandexhaustivity)7/27/202324.1IntroductionDecisionrulewithonlythepriorinformationDecide1ifP(1)>P(2)otherwisedecide2Useoftheclass–conditionalinformation

p(x|1)andp(x|2)describethedifferenceinlightnessbetweenpopulationsofseaandsalmon7/27/202334.1Introduction7/27/202344.1IntroductionPosterior,likelihood,evidenceP(j|x)=p(x|j).P(j)/P(x)Whereincaseoftwocategories

Posterior=(Likelihood.Prior)/Evidence7/27/202354.1Introduction7/27/202364.1IntroductionDecisiongiventheposteriorprobabilities Xisanobservationforwhich:

ifP(1|x)>P(2|x)Truestateofnature=1 ifP(1|x)<P(2|x)Truestateofnature=2

Decide1ifP(1|x)>P(2|x);

otherwisedecide27/27/202374.1Introductionwheneverweobserveaparticularx,theprobabilityoferroris:

P(error|x)=P(1|x)ifwedecide2 P(error|x)=P(2|x)ifwedecide17/27/202384.2

ContinuousFeaturesGeneralizationoftheprecedingideas

UseofmorethanonefeatureUsemorethantwostatesofnatureAllowingactionsandnotonlydecideonthestateofnatureIntroducealossoffunctionwhichismoregeneralthantheprobabilityoferror7/27/20239Whereincaseofmulti-categories Xisanobservationforwhich:

(1)ifTruestateofnature=i (2)ifTruestateofnature=i(3)ifTruestateofnature=i

(4)ifTruestateofnature=i

7/27/202310一个例子7/27/202311LOSSFUNCTIONLet{1,2,…,c}bethesetof“c”categoriesLet{1,2,…,a}bethesetof“a”

possibleactionsLet(i|j)bethelossincurredfortakingactioniwhenthestateofnatureisjTheposterior,P(j|x),canbecomputedfromBayesformula:Theexpectedlossfromtakingactioniis:fori=1,…,a7/27/202312BAYESRISKAnexpectedlossiscalledarisk.R(i|x)iscalledtheconditionalrisk.Ageneraldecisionruleisafunction(x)thattellsuswhichactiontotakeforeverypossibleobservation.Theoverallriskisgivenby:Ifwechoose(x)sothatR(i(x))isassmallaspossibleforeveryx,theoverallriskwillbeminimized.ComputetheconditionalriskforeveryandselecttheactionthatminimizesR(i|x).ThisisdenotedR*,andisreferredtoastheBayesrisk.TheBayesriskisthebestperformancethatcanbeachieved.7/27/202313BAYESRISK--TWO-CATEGORYCLASSIFICATIONLet1correspondto1,2to2,andij

=(i|j)Theconditionalriskisgivenby:R(1|x)=11P(1|x)+12P(2|x)R(2|x)=21P(1|x)+22P(2|x)Ourdecisionruleis: choose1if:R(1|x)<R(2|x);

otherwisedecide2Thisresultsintheequivalentrule:choose1if:(21-11)P(1|x)>(12-22)P(2|x);otherwisedecide

2Ifthelossincurredformakinganerrorisgreaterthanthatincurredforbeingcorrect,thefactors(21-11)and

(12-22)arepositive,andtheratioofthesefactorssimplyscalestheposteriors.7/27/202314BAYESRISK--LIKELIHOODByemployingBayesformula,wecanreplacetheposteriorsbythepriorprobabilitiesandconditionaldensities:

choose1if:(21-11)p(x|1)P(1)>(12-22)p(x|2)P(2);otherwisedecide

2If21-11ispositive,ourrulebecomes:Ifthelossfactorsareidentical,andthepriorprobabilitiesareequal,thisreducestoastandardlikelihoodratio:7/27/202315BAYESRISK--MINIMUMERRORRATEConsiderasymmetricalorzero-onelossfunction:Theconditionalriskis:

Theconditionalriskistheaverageprobabilityoferror.Tominimizeerror,maximizeP(i|x)—alsoknownasmaximumaposterioridecoding(MAP).7/27/202316BAYESRISK--LIKELIHOODRATIOMinimumerrorrateclassification: chooseiif:P(i|

x)>P(j|

x)forallji7/27/202317例子7/27/202318拒绝判决在C类问题中,a=c+1时,表示拒绝判决7/27/202319拒绝判决7/27/202320MINIMAXCRITERIONDesignourclassifiertominimizetheworstoverallrisk(avoidcatastrophicfailures)Factoroverallriskintocontributionsforeachregion:Usingasimplifiednotation7/27/202321MINIMAXCRITERIONWecanrewritetherisk:NotethatI11=1-I21andI22=1-I12:

Wemakethissubstitutionbecausewewanttheriskintermsoferrorprobabilitiesandpriors.Multiplyout,addandsubtractP121,andrearrange:7/27/202322MINIMAXCRITERIONNoteP1=1-P2:7/27/202323MINIMAXCRITERION当类的概率密度已知,损失函数选定,相对某一取定最佳的后,a、b为常数当发生变化，而不作相应的调整时，R是的线性函数7/27/202324MINIMAXCRITERION曲线：在0~1中任意取不同值按最小损失准则可确定相应的最佳，然后计算出相应的最小平均损失R，得到与R的曲线。虚线：在左边的黑点为时，最小平均损失Ra，此时得到。当变化时，不变，则得到的R为虚线上的点，此时的损失大于曲线时的情况，称为最大可能损失。我们希望变化时，最大可能的损失R最小，则b=0是平行于横轴的直线对应于曲线最大值7/27/202325MINIMAXCRITERION结论：在不精确知道或变动情况时，为使最大的可能损失最小，应该选择最小损失R取最大值时的来设计分类器，此时相对其他在最优设计下的R要大。但当在(0,1)发生变化时，其相应的最大损失为最小。若取0-1损失函数，则平均损失等于最小错误率判决规则的错误率7/27/202326MINIMAXCRITERION算法步骤：（1）按最小损失准则找出对应于（0，1）中的各个不同值的最佳决策类域（2）计算相应各个最佳决策类域的最小平均损失，得R~曲线（3）找出使R取最大值的去构造最小最大损失判决规则（4）若

7/27/202327NEYMAN-PEARSONCRITERION7/27/202328DECISIONSURFACESDefineasetofdiscriminantfunctions:gi(x),i=1,…,cDefineadecisionrule:chooseiif:gi(x)>gj(x)jiForaBayesclassifier,letgi(x)=-R(i|x)becausethemaximumdiscriminantfunctionwillcorrespondtotheminimumconditionalrisk.Fortheminimumerrorratecase,letgi(x)=P(i|x),sothatthemaximumdiscriminantfunctioncorrespondstothemaximumposteriorprobability.Choiceofdiscriminantfunctionisnotunique:multiplyoraddbysamepositiveconstantReplacegi(x)withamonotonicallyincreasing

function,

f(gi(x)).7/27/202329DECISIONSURFACES--NETWORKREPRESENTATIONA

classifiercanbevisualizedasaconnectedgraphwitharcsandweights:7/27/202330DECISIONSURFACES--LOGPROBABILITIESSomemonotonicallyincreasingfunctionscansimplifycalculationsconsiderably:Whataresomeofthereasons(3)isparticularlyuseful?Computationalcomplexity(e.g.,Gaussian)Numericalaccuracy(e.g.,probabilitiestendtozero)Decomposition(e.g.,likelihoodandpriorareseparatedandcanbeweighteddifferently)Normalization(e.g.,likelihoodsarechanneldependent).7/27/202331DECISIONSURFACES--TWO-CATEGORYCASEAclassifierthatplacesapatterninoneoftwoclassesisoftenreferredtoasadichotomizer.Wecanreshapethedecisionrule:Ifweuselogoftheposteriorprobabilities:Adichotomizercanbeviewedasamachinethatcomputesasinglediscriminantfunctionandclassifiesxaccordingtothesign(e.g.,supportvectormachines).7/27/202332DECISIONSURFACES--NORMALDISTRIBUTIONSRecallthedefinitionofanormaldistribution(Gaussian):Mean:Covariance:7/27/202333GAUSSIANCLASSIFIERS--DISCRIMINANTFUNCTIONSRecallourdiscriminantfunctionforminimumerrorrateclassification:Foramultivariatenormaldistribution:7/27/202334GAUSSIANCLASSIFIERS--DISCRIMINANTFUNCTIONSConsiderthecase:i=2I

(statisticalindependence,equalvariance,class-independentvariance)7/27/202335GAUSSIANCLASSIFIERS--DISCRIMINANTFUNCTIONSThediscriminantfunctioncanbereducedto:Sincethesetermsareconstantw.r.t.themaximization:Wecanexpandthis:Thetermxtxisaconstantw.r.t.i,anditiisaconstantthatcanbe

precomputed.7/27/202336GAUSSIANCLASSIFIERS--DISCRIMINANTFUNCTIONSWecanuseanequivalentlineardiscriminantfunction:Decideonthestateofnature:7/27/202337GAUSSIANCLASSIFIERS--DISCRIMINANTFUNCTIONSCase:i=Decideonthestateofnature:7/27/202338GAUSSIANCLASSIFIERS--GENERALCASEwhere:Thedecisionsurfacesdefinedbytheequation:7/27/202339GAUSSIANCLASSIFIERS--IDENTITYCOVARIANCECase:i=2I

Thiscanberewrittenas:7/27/202340GAUSSIANCLASSIFIERS--EQUALCOVARIANCESCase:i=7/27/202341ERRORBOUNDSBayesdecisionruleguaranteeslowestaverageerrorrateClosed-formsolutionfortwo-classGaussiandistributionsFullcalculationforhighdimensionalspacedifficultBoundsprovideawaytogetinsightintoaproblemandengineerbettersolutions.7/27/202342ERRORBOUNDSNeedthefollowinginequality:

Assumeabwithoutlossofgenerality:min[a,b]=b. Also,ab(1-)=(a/b)band(a/b)1. Therefore,b(a/b)b,whichimpliesmin[a,b]ab(1-).7/27/202343ERRORBOUNDSRecall:Notethatthisintegralisovertheentirefeaturespace,notthedecisionregions(whichmakesitsimpler).Iftheconditionalprobabilitiesarenormal,thisexpressioncanbesimplified.7/27/202344ERRORBOUNDS--CHERNOFFBOUNDFORNORMALDENSITIESIftheconditionalprobabilitiesarenormal,ourboundcanbeevaluatedanalytically:

where:Procedure:findthevalueofthatminimizesexp(-k(),andthencomputeP(error)usingthebound.Benefit:one-dimensionaloptimizationusing7/27/202345ERRORBOU