Naive-Bayes课件

COMP24111MachineLearningNaïveBayesClassifierKeChenCOMP24111MachineLearning2Outline•Background•ProbabilityBasics•ProbabilisticClassification•NaïveBayes•Example:PlayTennis•RelevantIssues•ConclusionsCOMP24111MachineLearning3Background•Therearethreemethodstoestablishaclassifiera)ModelaclassificationruledirectlyExamples:k-NN,decisiontrees,perceptron,SVMb)ModeltheprobabilityofclassmembershipsgiveninputdataExample:perceptronwiththecross-entropycostc)MakeaprobabilisticmodelofdatawithineachclassExamples:naiveBayes,modelbasedclassifiers•a)andb)areexamplesofdiscriminativeclassification•c)isanexampleofgenerativeclassification•b)andc)arebothexamplesofprobabilisticclassificationCOMP24111MachineLearning4ProbabilityBasics•Prior,conditionalandjointprobabilityforrandomvariables–Priorprobability:–Conditionalprobability:–Jointprobability:–Relationship:–Independence:•BayesianRule)|,)(121XP(XX|XP2)()()()(XXXPCPC|P|CP)(XP))(),,(22,XP(XPXX11XX)()|()()|()2211122XPXXPXPXXP,XP(X1)()()),()|(),()|(212121212XPXP,XP(XXPXXPXPXXP1EvidencePriorLikelihoodPosteriorCOMP24111MachineLearning5ProbabilityBasics•Quiz:Wehavetwosix-sideddice.Whentheyaretolled,itcouldendupwiththefollowingoccurance:(A)dice1landsonside“3”,(B)dice2landsonside“1”,and(C)Twodicesumtoeight.Answerthefollowingquestions:?equals),(Is8)?),(7)?),(6)?)|(5)?)|(4)?3)?2)?)()1P(C)P(A)CAPCAPBAPACPBAPP(C)P(B)APCOMP24111MachineLearning6ProbabilisticClassification•Establishingaprobabilisticmodelforclassification–Discriminativemodel),,,)(1n1LX(Xc,,cC|CPXX),,,(21nxxxxDiscriminativeProbabilisticClassifier1x2xnx)|(1xcP)|(2xcP)|(xLcPCOMP24111MachineLearning7ProbabilisticClassification•Establishingaprobabilisticmodelforclassification(cont.)–Generativemodel),,,)(1n1LX(Xc,,cCC|PXXGenerativeProbabilisticModelforClass1)|(1cPx1x2xnxGenerativeProbabilisticModelforClass2)|(2cPx1x2xnxGenerativeProbabilisticModelforClassL)|(LcPx1x2xnx),,,(21nxxxxCOMP24111MachineLearning8ProbabilisticClassification•MAPclassificationrule–MAP:MaximumAPosterior–Assignxtoc*if•GenerativeclassificationwiththeMAPrule–ApplyBayesianruletoconvertthemintoposteriorprobabilities–ThenapplytheMAPruleLc,,cccc|cCP|cCP1**,)()(xXxXLicCPcC|PPcCPcC|P|cCPiiiii,,2,1for)()()()()()(xXxXxXxXCOMP24111MachineLearning9NaïveBayes•BayesclassificationDifficulty:learningthejointprobability•NaïveBayesclassification–Assumptionthatallinputattributesareconditionallyindependent!–MAPclassificationrule:for)()|,,()()()(1CPCXXPCPC|P|CPnXX)|,,(1CXXPn)|()|()|()|,,()|()|,,();,,|()|,,,(212122121CXPCXPCXPCXXPCXPCXXPCXXXPCXXXPnnnnnLnnccccccPcxPcxPcPcxPcxP,,,),()]|()|([)()]|()|([1*1***1),,,(21nxxxxCOMP24111MachineLearning10NaïveBayes•NaïveBayesAlgorithm(fordiscreteinputattributes)–LearningPhase:GivenatrainingsetS,Output:conditionalprobabilitytables;forelements–TestPhase:Givenanunknowninstance,Lookuptablestoassignthelabelc*toX’if;inexampleswith)|(estimate)|(ˆ),1;,,1(attributeeachofvalueattributeeveryFor;inexampleswith)(estimate)(ˆofvaluetargeteachFor1SSijkjijkjjjjkiiLiicCxXPcCxXPN,knjXxcCPcCP)c,,c(ccLnnccccccPcaPcaPcPcaPcaP,,,),(ˆ)]|(ˆ)|(ˆ[)(ˆ)]|(ˆ)|(ˆ[1*1***1),,(1naaXLNXjj,COMP24111MachineLearning11Example•Example:PlayTennisCOMP24111MachineLearning12Example•LearningPhaseOutlookPlay=YesPlay=NoSunny2/93/5Overcast4/90/5Rain3/92/5TemperaturePlay=YesPlay=NoHot2/92/5Mild4/92/5Cool3/91/5HumidityPlay=YesPlay=NoHigh3/94/5Normal6/91/5WindPlay=YesPlay=NoStrong3/93/5Weak6/92/5P(Play=Yes)=9/14P(Play=No)=5/14COMP24111MachineLearning13Example•TestPhase–Givenanewinstance,x’=(Outlook=Sunny,Temperature=Cool,Humidity=High,Wind=Strong)–Lookuptables–MAPruleP(Outlook=Sunny|Play=No)=3/5P(Temperature=Cool|Play==No)=1/5P(Huminity=High|Play=No)=4/5P(Wind=Strong|Play=No)=3/5P(Play=No)=5/14P(Outlook=Sunny|Play=Yes)=2/9P(Temperature=Cool|Play=Yes)=3/9P(Huminity=High|Play=Yes)=3/9P(Wind=Strong|Play=Yes)=3/9P(Play=Yes)=9/14P(Yes|x’):[P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes)=0.0053P(No|x’):[P(Sunny|No)P(Cool|No)P(High|No)P(Strong|No)]P(Play=No)=0.0206GiventhefactP(Yes|x’)P(No|x’),welabelx’tobe“No”.COMP24111MachineLearning14Example•TestPhase–Givenanewinstance,x’=(Outlook=Sunny,Temperature=Cool,Humidity=High,Wind=Strong)–Lookuptables–MAPruleP(Outlook=Sunny|Play=No)=3/5P(Temperature=Cool|Play==No)=1/5P(Huminity=High|Play=No)=4/5P(Wind=Strong|Play=No)=3/5P(Play=No)=5/14P(Outlook=Sunny|Play=Yes)=2/9P(Temperature=Cool|Play=Yes)=3/9P(Huminity=High|Play=Yes)=3/9P(Wind=Strong|Play=Yes)=3/9P(Play=Yes)=9/14P(Yes|x’):[P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes)=0.0053P(No|x’):[P(Sunny|No)P(Cool|No)P(High|No)P(Strong|No)]P(Play=No)=0.0206GiventhefactP(Yes|x’)P(No|x’),welabelx’tobe“No”.COMP24111MachineLearning15RelevantIssues•ViolationofIndependenceAssumption–Formanyrealworldtasks,–Nevertheless,naïveBayesworkssurprisinglywellanyway!•ZeroconditionalprobabilityProblem–Ifnoexamplecontainstheattributevalue–Inthisci