人工智能_贝叶斯网络.ppt

1,ArtificialIntelligence:BayesianNetworks,2,GraphicalModels,Ifnoassumptionofindependenceismade,thenanexponentialnumberofparametersmustbeestimatedforsoundprobabilisticinference.Norealisticamountoftrainingdataissufficienttoestimatesomanyparameters.Ifablanketassumptionofconditionalindependenceismade,efficienttrainingandinferenceispossible,butsuchastrongassumptionisrarelywarranted.Graphicalmodelsusedirectedorundirectedgraphsoverasetofrandomvariablestoexplicitlyspecifyvariabledependenciesandallowforlessrestrictiveindependenceassumptionswhilelimitingthenumberofparametersthatmustbeestimated.BayesianNetworks:Directedacyclicgraphsthatindicatecausalstructure.MarkovNetworks:Undirectedgraphsthatcapturegeneraldependencies.,3,BayesianNetworks,DirectedAcyclicGraph(DAG)NodesarerandomvariablesEdgesindicatecausalinfluences,4,ConditionalProbabilityTables,Eachnodehasaconditionalprobabilitytable(CPT)thatgivestheprobabilityofeachofitsvaluesgiveneverypossiblecombinationofvaluesforitsparents(conditioningcase).Roots(sources)oftheDAGthathavenoparentsaregivenpriorprobabilities.,Burglary,Earthquake,Alarm,JohnCalls,MaryCalls,5,CPTComments,Probabilityoffalsenotgivensincerowsmustaddto1.Examplerequires10parametersratherthan251=31forspecifyingthefulljointdistribution.NumberofparametersintheCPTforanodeisexponentialinthenumberofparents(fan-in).,6,JointDistributionsforBayesNets,ABayesianNetworkimplicitlydefinesajointdistribution.,Example,Thereforeaninefficientapproachtoinferenceis:1)Computethejointdistributionusingthisequation.2)Computeanydesiredconditionalprobabilityusingthejointdistribution.,7,NaveBayesasaBayesNet,NaveBayesisasimpleBayesNet,Y,X1,X2,Xn,PriorsP(Y)andconditionalsP(Xi|Y)forNaveBayesprovideCPTsforthenetwork.,8,IndependenciesinBayesNets,IfremovingasubsetofnodesSfromthenetworkrendersnodesXiandXjdisconnected,thenXiandXjareindependentgivenS,i.e.P(Xi|Xj,S)=P(Xi|S)However,thisistoostrictacriteriaforconditionalindependencesincetwonodeswillstillbeconsideredindependentiftheirsimplyexistssomevariablethatdependsonboth.Forexample,BurglaryandEarthquakeshouldbeconsideredindependentsincetheybothcauseAlarm.,9,IndependenciesinBayesNets,IfremovingasubsetofnodesSfromthenetworkrendersnodesXiandXjdisconnected,thenXiandXjareindependentgivenS,i.e.P(Xi|Xj,S)=P(Xi|S)However,thisistoostrictacriteriaforconditionalindependencesincetwonodeswillstillbeconsideredindependentiftheirsimplyexistssomevariablethatdependsonboth.Forexample,BurglaryandEarthquakeshouldbeconsideredindependentsincetheybothcauseAlarm.,P(Xi|Xj,S)=P(Xi|S),isequivalenttoP(Xi,Xj|S)=P(Xi|S)P(Xj|S)Howtoprove?,10,IndependenciesinBayesNets,IfremovingasubsetofnodesSfromthenetworkrendersnodesXiandXjdisconnected,thenXiandXjareindependentgivenS,i.e.P(Xi|Xj,S)=P(Xi|S)However,thisistoostrictacriteriaforconditionalindependencesincetwonodeswillstillbeconsideredindependentiftheirsimplyexistssomevariablethatdependsonboth.Forexample,BurglaryandEarthquakeshouldbeconsideredindependentsincetheybothcauseAlarm.,11,IndependenciesinBayesNets(cont.),Unlessweknowsomethingaboutacommoneffectoftwo“independentcauses”oradescendentofacommoneffect,thentheycanbeconsideredindependent.Forexample,ifweknownothingelse,EarthquakeandBurglaryareindependent.However,ifwehaveinformationaboutacommoneffect(ordescendentthereof)thenthetwo“independent”causesbecomeprobabilisticallylinkedsinceevidenceforonecausecan“explainaway”theother.Forexample,ifweknowthealarmwentoffthatsomeonecalledaboutthealarm,thenitmakesearthquakeandburglarydependentsinceevidenceforearthquakedecreasesbeliefinburglary.andviceversa.,12,BayesNetInference,Givenknownvaluesforsomeevidencevariables,determinetheposteriorprobabilityofsomequeryvariables.Example:GiventhatJohncalls,whatistheprobabilitythatthereisaBurglary?,Burglary,Earthquake,Alarm,JohnCalls,MaryCalls,?,Johncalls90%ofthetimethereisanAlarmandtheAlarmdetects94%ofBurglariessopeoplegenerallythinkitshouldbefairlyhigh.However,thisignoresthepriorprobabilityofJohncalling.,13,BayesNetInference,Example:GiventhatJohncalls,whatistheprobabilitythatthereisaBurglary?,Burglary,Earthquake,Alarm,JohnCalls,MaryCalls,?,Johnalsocalls5%ofthetimewhenthereisnoAlarm.Soover1,000daysweexpect1BurglaryandJohnwillprobablycall.However,hewillalsocallwithafalsereport50timesonaverage.Sothecallisabout50timesmorelikelyafalsereport:P(Burglary|JohnCalls)0.02,14,BayesNetInference,Example:GiventhatJohncalls,whatistheprobabilitythatthereisaBurglary?,Burglary,Earthquake,Alarm,JohnCalls,MaryCalls,?,ActualprobabilityofBurglaryis0.016sincethealarmisnotperfect(anEarthquakecouldhavesetitofforitcouldhavegoneoffonitsown).Ontheotherside,eveniftherewasnotanalarmandJohncalledincorrectly,therecouldhavebeenanundetectedBurglaryanyway,butthisisunlikely.,15,TypesofInference,16,SampleInferences,Diagnostic(evidential,abductive):Fromeffecttocause.P(Burglary|JohnCalls)=0.016P(Burglary|JohnCallsMaryCalls)=0.29P(Alarm|JohnCallsMaryCalls)=0.76P(Earthquake|JohnCallsMaryCalls)=0.18Causal(predictive):FromcausetoeffectP(JohnCalls|Burglary)=0.86P(MaryCalls|Burglary)=0.67Intercausal(explainingaway):Betweencausesofacommoneffect.P(Burglary|Alarm)=0.376P(Burglary|AlarmEarthquake)=0.003Mixed:Twoormoreoftheabovecombined(diagnosticandcausal)P(Alarm|JohnCallsEarthquake)=0.03(diagnosticandintercausal)P(Burglary|JohnCallsEarthquake)=0.017,17,SampleInferences,Diagnostic(evidential,abductive):Fromeffecttocause.P(Burglary|JohnCalls)=0.016P(Burglary|JohnCallsMaryCalls)=0.29P(Alarm|JohnCallsMaryCalls)=0.76P(Earthquake|JohnCallsMaryCalls)=0.18Causal(predictive):FromcausetoeffectP(JohnCalls|Burglary)=0.86P(MaryCalls|Burglary)=0.67Intercausal(explainingaway):Betweencausesofacommoneffect.P(Burglary|Alarm)=0.376P(Burglary|AlarmEarthquake)=0.003Mixed:Twoormoreoftheabovecombined(diagnosticandcausal)P(Alarm|JohnCallsEarthquake)=0.03(diagnosticandintercausal)P(Burglary|JohnCallsEarthquake)=0.017,Assignment:Calculatetheseresults!,18,ProbabilisticInferenceinHumans,Peoplearenotoriouslybadatdoingcorrectprobabilisticreasoningincertaincases.Oneproblemistheytendtoignoretheinfluenceofthepriorprobabilityofasituation.,19,MontyHallProblem,1,2,3,OneLineDemo:/crypto/Monty/monty.html,20,MultiplyConnectedNetworks,Networkswithundirectedloops,morethanonedirectedpathbetweensomepairofnodes.,Ingeneral,inferenceinsuchnetworksisNP-hard.Somemethodsconstructapolytree(s)fromgivennetworkandperforminferenceontransformedgraph.,21,NodeClustering,Eliminateallloopsbymergingnodestocreatemeganodesthathavethecross-productofvaluesofthemergednodes.,Numberofvaluesformergednodeisexponentialinthenumberofnodesmerged.Stillreasonablytractableformanynetworktopologiesrequiringrelativelylittlemergingtoeliminateloops.,22,BayesNetsApplications,MedicaldiagnosisPathfindersystemoutperformsleadingexpertsindiagnosisoflymph-nodedisease.MicrosoftapplicationsProblemdiagnosis:printerproblemsRecognizinguserintentsforHCITextcategorizationandspamfilteringStudentmodelingforintelligenttutoringsystems.,23,StatisticalRevolution,AcrossAItherehasbeenamovementfromlogic-basedapproachestoapproachesbasedonprobabilityandstatistics.StatisticalnaturallanguageprocessingStatisticalcomputervisionStatisticalrobotnavigationStatisticallearningMostapproachesarefeature-basedand“propositional”anddonothandlecomplexrelationaldescriptionswithmultipleentitieslikethosetypicallyrequiringpredicatelogic.,Structured(Multi-Relational)Data,Inmanydomains,dataconsistsofanunboundednumberofentitieswithanarbitrarynumberofpropertiesandrelationsbetweenthem.SocialnetworksBiochemicalcompoundsWebsites,25,BiochemicalData,PredictingmutagenicitySrinivasanet.al,1995,Web-KBDatasetSlattery&Craven,1998,Faculty,GradStudent,ResearchProject,Other,CollectiveClassification,Traditionallearningmethodsassumethatobjectstobeclassifiedareindependent(thefirst“i”inthei.i.d.assumption)Instructureddata,theclassofanentitycanbeinfluencedbytheclassesofrelatedentities.Needtoassignclassestoallobjectssimultaneouslytoproducethemostprobableglobally-consistentinterpretation.,LogicalAIParadigm,RepresentsknowledgeanddatainabinarysymboliclogicsuchasFOPC.+Richrepresentationthathandlesarbitrarysetsofobjects,withproperties,relations,quantifiers,etc.Unabletohandleuncertainknowledgeandprobabilisticreasoning.,ProbabilisticAIP