IntroductiontoBayesianNetworks

Introduction to Bayesian Networks A Tutorial for the 66th MORS Symposium23-25 June 1998Naval Postgraduate SchoolMonterey,California Dennis M.Buede Joseph A.TatmanTerry A.BresnickOverview Day 1 Motivating Examples Basic Constructs and Operations Day 2 Propagation Algorithms Example Application Day 3 Learning Continuous Variables SoftwareDay One Outline Introduction Example from Medical Diagnostics Key Events in Development Definition Bayes Theorem and Influence Diagrams ApplicationsWhy the Excitement?What are they?Bayesian nets are a network-based framework for representing and analyzing models involving uncertaintyWhat are they used for?Intelligent decision aids,data fusion,3-E feature recognition,intelligent diagnostic aids,automated free text understanding,data miningWhere did they come from?Cross fertilization of ideas between the artificial intelligence,decision analysis,and statistic communitiesWhy the sudden interest?Development of propagation algorithms followed by availability of easy to use commercial software Growing number of creative applicationsHow are they different from other knowledge representation and probabilistic analysis tools?Different from other knowledge-based systems tools because uncertainty is handled in mathematically rigorous yet efficient and simple way Different from other probabilistic analysis tools because of network representation of problems,use of Bayesian statistics,and the synergy between theseExample from Medical DiagnosticsNetwork represents a knowledge structure that models the relationship between medical difficulties,their causes and effects,patient information and diagnostic testsVisit to AsiaTuberculosisTuberculosisor CancerXRay ResultDyspneaBronchitisLung CancerSmokingPatient InformationMedical DifficultiesDiagnostic TestsExample from Medical DiagnosticsRelationship knowledge is modeled by deterministic functions,logic and conditional probability distributionsPatient InformationDiagnostic TestsVisit to AsiaTuberculosisTuberculosisor CancerXRay ResultDyspneaBronchitisLung CancerSmokingTuberPresentPresentAbsentAbsentLung CanPresentAbsentPresentAbsentTub or CanTrueTrueTrueFalseMedical DifficultiesTub or CanTrueTrueFalseFalseBronchitisPresentAbsentPresentAbsentPresent0.900.700.800.10Absent0.l00.300.200.90DyspneaExample from Medical DiagnosticsPropagation algorithm processes relationship information to provide an unconditional or marginal probability distribution for each nodeThe unconditional or marginal probability distribution is frequently called the belief function of that nodeTuberculosisTuberculosisPresentA bsent1.0499.0XR ay R esultXR ay R esultA bnorm alN orm al11.089.0Tuberculosis or C ancerTuberculosis or C ancerTrueFalse6.4893.5Lung C ancerLung C ancerPresentA bsent5.5094.5D yspneaD yspneaPresentA bsent43.656.4BronchitisBronchitisPresentA bsent45.055.0V isit To A siaV isit To A siaV isitN o V isit1.0099.0Sm okingSm okingSm okerN onSm oker50.050.0Example from Medical DiagnosticsAs a finding is entered,the propagation algorithm updates the beliefs attached to each relevant node in the networkInterviewing the patient produces the information that“Visit to Asia”is“Visit”This finding propagates through the network and the belief functions of several nodes are updatedTuberculosisTuberculosisPresentA bsent5.0095.0XR ay R esultXR ay R esultA bnorm alN orm al14.585.5Tuberculosis or C ancerTuberculosis or C ancerTrueFalse10.289.8Lung C ancerLung C ancerPresentA bsent5.5094.5D yspneaD yspneaPresentA bsent45.055.0BronchitisBronchitisPresentA bsent45.055.0V isit To A siaV isit To A siaV isitN o V isit 100 0Sm okingSm okingSm okerN onSm oker50.050.0TuberculosisTuberculosisPresentA bsent5.0095.0XR ay R esultXR ay R esultA bnorm alN orm al18.581.5Tuberculosis or C ancerTuberculosis or C ancerTrueFalse14.585.5Lung C ancerLung C ancerPresentA bsent10.090.0D yspneaD yspneaPresentA bsent56.443.6BronchitisBronchitisPresentA bsent60.040.0V isit To A siaV isit To A siaV isitN o V isit 100 0Sm okingSm okingSm okerN onSm oker 100 0Example from Medical DiagnosticsFurther interviewing of the patient produces the finding“Smoking”is“Smoker”This information propagates through the networkTuberculosisTuberculosisPresentA bsent0.1299.9XR ay R esultXR ay R esultA bnorm alN orm al 0 100Tuberculosis or C ancerTuberculosis or C ancerTrueFalse0.3699.6Lung C ancerLung C ancerPresentA bsent0.2599.8D yspneaD yspneaPresentA bsent52.147.9BronchitisBronchitisPresentA bsent60.040.0V isit To A siaV isit To A siaV isitN o V isit 100 0Sm okingSm okingSm okerN onSm oker 100 0Example from Medical DiagnosticsFinished with interviewing the patient,the physician begins the examinationThe physician now moves to specific diagnostic tests such as an X-Ray,which results in a“Normal”finding which propagates through the networkNote that the information from this finding propagates backward and forward through the arcsTuberculosisTuberculosisPresentA bsent0.1999.8XR ay R esultXR ay R esultA bnorm alN orm al 0 100Tuberculosis or C ancerTuberculosis or C ancerTrueFalse0.5699.4Lung C ancerLung C ancerPresentA bsent0.3999.6D yspneaD yspneaPresentA bsent 100 0BronchitisBronchitisPresentA bsent92.27.84V isit To A siaV isit To A siaV isitN o V isit 100 0Sm okingSm okingSm okerN onSm oker 100 0Example from Medical DiagnosticsThe physician also determines that the patient is having difficulty breathing,the finding“Present”is entered for“Dyspnea”and is propagated through the networkThe doctor might now conclude that the patient has bronchitis and does not have tuberculosis or lung cancerApplicationsIndustrialProcessor Fault Diagnosis-by IntelAuxiliary Turbine Diagnosis-GEMS by GE Diagnosis of space shuttle propulsion systems-VISTA by NASA/RockwellSituation assessment for nuclear power plant-NRCMilitaryAutomatic Target Recognition-MITREAutonomous control of unmanned underwater vehicle-Lockheed MartinAssessment of IntentMedical DiagnosisInternal MedicinePathology diagnosis-Intellipath by Chapman&HallBreast Cancer Manager with IntellipathCommercialFinancial Market AnalysisInformation RetrievalSoftware troubleshooting and advice-Windows 95&Office 97Pregnancy and Child Care-MicrosoftSoftware debugging-American Airlines SABRE online reservation systemDefinition of a Bayesian Network Factored joint probability distribution as a directed graph:structure for representing knowledge about uncertain variables computational architecture for computing the impact of evidence on beliefs Knowledge structure:variables are depicted as nodes arcs represent probabilistic dependence between variables conditional probabilities encode the strength of the dependencies Computational architecture:computes posterior probabilities given evidence about selected nodes exploits probabilistic independence for efficient computationSample Factored Joint DistributionX1X3X2X5X4X6p(x1,x2,x3,x4,x5,x6)=p(x6|x5)p(x5|x3,x2)p(x4|x2,x1)p(x3|x1)p(x2|x1)p(x1)Bayes RuleBased on definition of conditional probabilityp(Ai|E)is posterior probability given evidence Ep(Ai)is the prior probabilityP(E|Ai)is the likelihood of the evidence given Aip(E)is the preposterior probability of the evidence=iiiiiiii)p(AA|p(E)p(AA|p(Ep(E)p(AA|p(EE)|p(Ap(B)A)p(A)|p(Bp(B)B)p(A,B)|p(AA1A2A3A4A5A6EArc Reversal-Bayes RuleX1X3X2X1X3X2X1X3X2X1X3X2p(x1,x2,x3)=p(x3|x1)p(x2|x1)p(x1)p(x1,x2,x3)=p(x3|x2,x1)p(x2)p(x1)p(x1,x2,x3)=p(x3|x1)p(x2,x1)=p(x3|x1)p(x1|x2)p(x2)p(x1,x2,x3)=p(x3,x2|x1)p(x1)=p(x2|x3,x1)p(x3|x1)p(x1)is equivalent tois equivalent toInference Using Bayes TheoremTuber-culosisLungCancerTuberculosisor CancerDyspneaBronchitisLungCancerTuberculosisor CancerDyspneaBronchitisLungCancerTuberculosisor CancerDyspneaLungCancerDyspneaLungCancerDyspneaThe general probabilistic inference problem is to find the probability of an event given a set of evidenceThis can be done in Bayesian nets with sequential applications of Bayes TheoremWhy Not this Straightforward Approach?Entire network must be considered to determine next node to remove Impact of evidence available only for single node,impact on eliminated nodes is unavailable Spurious dependencies between variables normally perceived to be independent are created and calculated Algorithm is inherently sequential,unsupervised parallelism appears to hold most promise for building viable models of human reasoning In 1986 Judea Pearl published an innovative algorithm for performing inference in Bayesian nets that overcomes these difficulties -TOMMORROW!Overview Day 1 Motivating Examples Basic Constructs and Operations Day 2 Propagation Algorithms Example Application Day 3 Learning Continuous Variables SoftwareIntroduction to Bayesian Networks A Tutorial for the 66th MORS Symposium23-25 June 1998Naval Postgraduate SchoolMonterey,California Dennis M.Buede Joseph A.TatmanTerry A.BresnickOverview Day 1 Motivating Examples Basic Constructs and Operations Day 2 Propagation Algorithms Example Application Day 3 Learning Continuous Variables SoftwareOverview of Bayesian Network Algorithms Singly vs.multiply connected graphs Pearls algorithm Categorization of other algorithms Exact SimulationPropagation Algorithm Objective The algorithms purpose is“fusing and propagating the impact of new evidence and beliefs through Bayesian networks so that each proposition eventually will be assigned a certainty measure consistent with the axioms of probability theory.”(Pearl,1988,p 143)DataDataSingly Connected Networks(or Polytrees)Definition:A directed acyclic graph(DAG)in which only one semipath(sequence of connected nodes ignoring direction of the arcs)exists between any two nodes.Do notsatisfydefinitionPolytreestructuresatisfiesdefinitionMultiple parents and/ormultiple childrenBel(x)=p(x|e),the posterior(a vector of dimension m)f(x)g(x)=the term by term product(congruent multiplication)of two vectors,each of dimension mf(x)g(x)=the inner(or dot)product of two vectors,or the matrix multiplication of a vector and a matrixa=a normalizing constant,used to normalize a vector so that its elements sum to 1.0NotationX=a random variable(a vector of dimension m);x=a possible value of Xe=evidence(or data),a vector of dimension mMy|x =p(y|x),the likelihood matrix or conditional probability distributionp(y1|x1)p(y2|x1).p(yn|x1)p(y1|x2)p(y2|x2).p(yn|x2).p(y1|xm)p(y2|xm).p(yn|xm)y=xBi-Directional Propagation in a Chaine+e-XYZp(e+)p(x)p(y)l(y)l(z)l(e-)Each node transmits a pi message to itschildren and a lambda message to its parents.Bel(Y)=p(y|e+,e-)=a a p p(y)T l l(y)wherep p(y)=p(y|e+),prior evidence;a row vectorl l(y)=p(e-|y),diagnostic or likelihood evidence;a column vectorp p(y)=x p(y|x,e+)p(x|e+)=x p(y|x)p p(x)=p p(x)My|xl l(y)=z p(e-|y,z)p(z|y)=z p(e-|z)p(z|y)=z l l(z)p(z|y)=Mz|y l l(z)An Example:Simple Chainp(Paris)=0.9p(Med.)=0.1M TO|SM=M AA|TO =ParisMed.ChalonsDijonNorthCentralSouthStrategicMissionTactical ObjectiveAvenue ofApproach.8 .2.1 .9.5 .4 .1.1 .3 .6ChDiPaMeNo Ce SoChDiSample Chain-Setup(1)Set all lambdas to be a vector of 1s;Bel(SM)=a l(SM)p(SM)p(SM)Bel(SM)l(SM)Paris 0.9 0.9 1.0Med.0.1 0.1 1.0(2)p(TO)=p(SM)MTO|SM;Bel(TO)=a l(TO)p(TO)p(TO)Bel(TO)l(TO)Chalons 0.73 0.73 1.0Dijon 0.27 0.27 1.0(3)p(AA)=p(TO)MAA|TO;Bel(AA)=a l(AA)p(AA)p(AA)Bel(AA)l(AA)North 0.39 0.40 1.0Central 0.35 0.36 1.0South 0.24 0.24 1.0StrategicMissionTactical ObjectiveAvenue ofApproachMAA|TO=MTO|SM=.8 .2.1 .9.5 .4 .1.1 .3 .6Sample Chain-1st Propagation tTRT=05l l().1 .6 t=0(lR)=.8 .2p pt=1p(SM)=p(IR)p(SM)Bel(SM)l(SM)Paris 0.8 0.8 1.0Med.0.2 0.2 1.0p(TO)Bel(TO)l(TO)Chalons 0.73 0.73 1.0Dijon 0.27 0.27 1.0p(AA)Bel(AA)l(AA)North 0.39 0.3 0.5Central 0.35 0.5 1.0South 0.24 0.2 0.6t=1l(AA)=l(TR)Intel.Rpt.TroopRpt.StrategicMissionTactical ObjectiveAvenue ofApproachSample Chain-2nd Propagation tTRT=05l l().1 .6 t=0(lR)=.8 .2p pp(SM)Bel(SM)l(SM)Paris 0.8 0.8 1.0Med.0.2 0.2 1.0t=2p(TO)=p(SM)MTO|SMp(TO)Bel(TO)l(TO)Chalons 0.66 0.66 0.71Dijon 0.34 0.34 0.71t=2l(TO)=MAA|TO l(SM)p(AA)Bel(AA)l(AA)North 0.39 0.3 0.5Central 0.35 0.5 1.0South 0.24 0.2 0.6Intel.Rpt.TroopRpt.StrategicMissionTactical ObjectiveAvenue ofApproachSample Chain-3rd Propagationp(SM)Bel(SM)l(SM)Paris 0.8 0.8 0.71Med.0.2 0.2 0.71t=3l(SM)=MTO|SMl(TO)p(TO)Bel(TO)l(TO)Chalons 0.66 0.66 0.71Dijon 0.34 0.34 0.71t=3p(AA)=p(TO)MAA|TO p(AA)Bel(AA)l(AA)North 0.36 0.25 0.5Central 0.37 0.52 1.0South 0.27 0.23 0.6Intel.Rpt.TroopRpt.StrategicMissionTactical ObjectiveAvenue ofApproachInternal Structure of a Single Node ProcessorProcessor for Node XMessage toParent UMessage fromParent UMX|U lp MX|Uk lk(X)BEL=a p lMessage toChildren of XMessage fromChildren of Xa BEL(X)l1(X)a BEL(X)lN(X).l(X)p(X)lX(U)l1(X)lN(X)p X(U)pN(X)p1(X)PropagationExampleThe example above requires five time periods to reach equilibrium after the introduction of data(Pearl,1988,p 174)“The impact of each new piece of evidence is viewed as a perturbation that propagates throughthe network via message-passing betweenneighboring variables.”(Pearl,1988,p 143DataDataCategorization of Other AlgorithmsExact algorithms on original directed graph(only singly connected,e.g.,Pearl)on related undirected graph Lauritzen&Spiegelhalter Jensen Symbolic Probabilistic Inference on a different but related directed graph using conditioning using node reductionsSimulation algorithms Backward sampling Stochastic simulation Forward sampling Logic sampling Likelihood weighting(With and without importance sampling)(With and without Markov blanket scoring)Decision Making in Nuclear Power Plant Operations“Decision making in nuclear power plant operations is characterized by:Time pressureDynamically evolving scenariosHigh expertise levels on the part of the operatorsMonitorEnvironmentStartAssessment?PropagateEvidenceSituation AwarenessUpdated SituationBelief DistributionAssess SituationAction Required?ProjectEventsChoose ActionIf Situation=SiThen Procedure=PiSituation Assessment(SA)Decision Making1)Monitor the environment2)Determine the need for situation assessment3)Propagate event cues4)Project Events5)Assess Situation6)Make DecisionModel of Situation Assessment andHuman Decision MakingThe Bayesian net situation assessment model provides:Knowledge of the structural relationship among situations,events,and event cuesMeans of integrating the situations and events to form a holistic view of their meaningMechanism for projecting future eventsSteam GeneratorTube RuptureLoss of CoolantAccidentLoss of SecondaryCoolantOtherEmergencySteam LineRadiationPressurizerPressureSteam Gen-erator LevelSteam LineRadiation AlarmPressurizerIndicatorSteam GeneratorIndicatorSituationsEventsSensorOutputsSituation Assessment Bayesian NetInitial Conditions Given EmergencyEmergencyTrueFalse 100 0LOSCTrueFalse17.083.0LOCATrueFalse17.083.0OtherTrueFalse22.078.0SGTRTrueFalse44.056.0PRZ_PressureRapidly DecSlowly DecConst or Inc56.63.5039.9SL_RadiationTrueFalse71.328.7SG_LevelIncreasingNon Increasing62.737.3SLR_AlarmTrueFalse70.929.1PRZ_IndicatorRapidly DecSlowly DecConst or Inc39.730.130.1SG_IndicatorIncreasingNon Increasing60.139.9Situation Assessment Bayesian NetSteam Line Radiation Alarm Goes HighEmergencyTrueFalse 100 0LOSCTrueFalse17.083.0LOCATrueFalse17.083.0OtherTrueFalse26.074.0SGTRTrueFalse55.444.6PRZ_PressureRapidly DecSlowly DecConst or Inc64.43.6032.0SL_RadiationTrueFalse99.60.41SG_LevelIncreasingNon Increasing71.428.6SLR_AlarmTrueFalse 100 0PRZ_IndicatorRapidly DecSlowly DecConst or Inc43.628.228.2SG_IndicatorIncreasingNon Increasing67.132.9EmergencyTrueFalse 100 0LOSCTrueFalse17.083.0LOCATrueFalse17.083.0OtherTrueFalse12.387.7SGTRTrueFalse16.383.7PRZ_PressureRapidly DecSlowly DecConst or Inc37.63.2659.1SL_RadiationTrueFalse2.4597.6SG_LevelIncreasingNon Increasing41.558.5SLR_AlarmTrueFalse 0 100PRZ_IndicatorRapidly DecSlowly DecConst or Inc30.134.934.9SG_IndicatorIncreasingNon Increasing43.256.8Situation Assessment Bayesian NetSteam Line Radiation Alarm Goes LowSimulation of SGTR ScenarioEvent TimelineTimeEvent CuesActions6:30:00Steam generator tube rupture occurs6:30:14Radiation alarmOperator observes that the radioactivityalarm for“A”steam line is on6:30:21Low pressure alarm6:30:34Pressurizer level and pressure aredecreasing rapidlyCharging FCV full open6:30:44Pressurizer pressure and level are stilldecreasingLetdown isolation6:30:54Decrease in over-temperature-deltatemperature limit10%decrease in turbine load6:32:34Decreasing pressurizer pressure andlevel cannot be stopped fromdecreasing.EmergencyManual trip6:32:41Automatic SI actuated6:32:44Reactor is trippedEP-0 Procedure starts6:33:44Very low pressure of FW is presentFW is isolated6:37:04Pressurizer pressure less than 2350 psig PORVs are closed6:37:24Radiation alarm,pressure decrease andSG level increase in loop“A”SGTR is identified and isolatedSimulation of SGTR ScenarioConvergence of Situation DisparitySituation Disparity is defined as follows:SD(t)=|Bel(S(t)-Bel(S(t)|S represents the actual situation S represents the perceived situation00.20.40.60.816:296:306:316:316:326:336:346:356:366:37Overview Day 1 Motivating Examples Basic Constructs and Operations Day 2 Propagation Algorithms Example Application Day 3 Learning Continuous Variables SoftwareIntroduction to Bayesian Networks A Tutorial for the 66th MORS Symposium23-25 June 1998Naval Postgraduate SchoolMonterey,California Dennis M.Buede,dbuedegmu.edu Joseph A.Tatman,Terry A.Bresnick,http:/www.gmu.edu-Depts(Info Tech&Eng)-Sys.Eng.-BuedeOverview Day 1 Motivating Examples Basic Constructs and Operations Day 2 Propagation Algorithms Example Application Day 3 Learning Continuous Variables SoftwareBuilding BN StructuresBayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithmLearning Probabilities from Data Exploit conjugate distributions Prior and posterior distributions in same family Given a pre-defined functional form of the likelihood For probability distributions of a variable defined between 0 and 1,and associated with a discrete sample space for the likelihood Beta distribution for 2 likelihood states(e.g.,head on a coin toss)Multivariate Dirichlet distribution for 3+states in likelihood spaceBeta Distribution1)n(nm/n)m(1variancenmmeanx)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta+-=-=-G GG GG G-10123400.511.5xp(x|m,n)m=1,n=2m=2,n=4m=10,n=20Multivariate Dirichlet Distribution1)m(m)m/m(1mstate i theof variancemmstate i theofmean.xxx)(m).(m)(m)m()m,.,m,m|(xpN1iiN1iiN1iiiithN1iiith1m1-m1mN21N1iiN21DirichletN21+-=GGGG=-=Updating with DirichletChoose prior with m1=m2=mN=1 Assumes no knowledge Assumes all states equally likely:.33,.33,.33 Data changes posterior most quickly Setting mi=101 for all i would slow effect of data downCompute number of records in database in each stateFor 3 state case:99 records in first state,49 in second,99 in third Posterior values of ms:100,50,100 Posterior probabilities equal means:.4,.2,.4 For mi equal 101,posterior probabilities would be:.36,.27,.36Learning BN Structure from DataEntropy Methods Earliest method Formulated for trees and polytreesConditional Independence(CI)Define conditional independencies for each node(Markov boundaries)Infer dependencies within Markov boundaryScore Metrics Most implemented method Define a quality metric to maximize Use greedy search to determine the next best arc to add Stop when metric does not increase by adding an arcSimulated Annealing&Genetic Algorithms Advancements over greedy search for score metricsSample Score Metrics Bayesian score:p(network structure|database)Information criterion:log p(database|network structure and parameter set)Favors complete networks Commonly add a penalty term on the number of arcs Minimum description length:equivalent to the information criterion with a penalty function Derived using coding theoryFeatures for Adding Knowledge to Learning Structure Define Total Order of Nodes Define Partial Order of Nodes by Pairs Define“Cause&Effect”RelationsDemonstration of Bayesian Network Power Constructor Generate a random s