1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 24Milos [email protected] Sennott SquareBayesian belief networksCS 1571 Intro to AIM. HauskrechtAdministration• Homework assignment 10 is out and due next week• Final exam:– December 11, 2006– 12:00-1:50pm, 5129 Sennott Square2CS 1571 Intro to AIM. HauskrechtModeling uncertainty with probabilities• Knowledge based system era (70s – early 80’s)– Extensional non-probabilistic models– Solve the space, time and acquisition bottlenecks in probability-based models – froze the development and advancement of KB systems and contributed to the slow-down of AI in 80s in general • Breakthrough (late 80s, beginning of 90s)– Bayesian belief networks• Give solutions to the space, acquisition bottlenecks• Partial solutions for time complexities• Bayesian belief networkCS 1571 Intro to AIM. HauskrechtBayesian belief networks (BBNs)Bayesian belief networks.• Represent the full joint distribution over the variables more compactly with a smaller number of parameters. • Take advantage of conditional and marginal independencesamong random variables• A and B are independent• A and B are conditionally independent given C)()(),( BPAPBAP=)|()|()|,( CBPCAPCBAP=)|(),|( CAPBCAP=3CS 1571 Intro to AIM. HauskrechtAlarm system example.• Assume your house has an alarm system against burglary. You live in the seismically active area and the alarm system can get occasionally set off by an earthquake. You have two neighbors, Mary and John, who do not know each other. If they hear the alarm they call you, but this is not guaranteed. • We want to represent the probability distribution of events:– Burglary, Earthquake, Alarm, Mary calls and John callsBurglaryJohnCallsAlarmEarthquakeMaryCallsCausal relationsCS 1571 Intro to AIM. HauskrechtBayesian belief network.Burglary EarthquakeJohnCallsMaryCallsAlarmP(B)P(E)P(A|B,E)P(J|A)P(M|A)1. Directed acyclic graph• Nodes = random variablesBurglary, Earthquake, Alarm, Mary calls and John calls• Links = direct (causal) dependencies between variables.The chance of Alarm is influenced by Earthquake, The chance of John calling is affected by the Alarm4CS 1571 Intro to AIM. HauskrechtBayesian belief network.2. Local conditional distributions • relate variables and their parentsBurglary EarthquakeJohnCallsMaryCallsAlarmP(B)P(E)P(A|B,E)P(J|A)P(M|A)CS 1571 Intro to AIM. HauskrechtBayesian belief network.Burglary EarthquakeJohnCalls MaryCallsAlarmB E T FT T 0.95 0.05T F 0.94 0.06F T 0.29 0.71F F 0.001 0.999P(B)0.001 0.999P(E)0.002 0.998A T FT 0.90 0.1F 0.05 0.95A T FT 0.7 0.3F 0.01 0.99P(A|B,E)P(J|A)P(M|A)T F T F5CS 1571 Intro to AIM. HauskrechtBayesian belief networks (general)Two components:• Directed acyclic graph– Nodes correspond to random variables – (Missing) links encode independences• Parameters– Local conditional probability distributionsfor every variable-parent configuration))(|(iiXpaXPABMJE),(SSBΘ=)(iXpa- stand for parents of XiWhere:B E T FT T 0.95 0.05T F 0.94 0.06F T 0.29 0.71F F 0.001 0.999P(A|B,E)CS 1571 Intro to AIM. HauskrechtFull joint distribution in BBNsFull joint distribution is defined in terms of local conditional distributions (obtained via the chain rule):))(|(),..,,(,..121∏==niiinXpaXXXX PPMABJE====== ),,,,( FMTJTATETBPExample:)|()|(),|()()( TAFMPTATJPTETBTAPTEPTBP =========Then its probability is:Assume the following assignmentof values to random variablesFMTJTATETB===== ,,,,6CS 1571 Intro to AIM. HauskrechtBayesian belief networks (BBNs)Bayesian belief networks • Represent the full joint distribution over the variables more compactly using the product of local conditionals. • But how did we get to local parameterizations?Answer:• Graphical structure encodes conditional and marginal independences among random variables• A and B are independent• A and B are conditionally independent given C• The graph structure implies the decomposition !!!)()(),( BPAPBAP=)|()|()|,( CBPCAPCBAP=)|(),|( CAPBCAP=CS 1571 Intro to AIM. HauskrechtIndependences in BBNs3 basic independence structures:BurglaryJohnCallsAlarmBurglaryAlarmEarthquakeJohnCallsAlarmMaryCalls1. 2. 3.7CS 1571 Intro to AIM. HauskrechtIndependences in BBNs1. JohnCalls is independent of Burglary given AlarmBurglaryJohnCallsAlarmBurglaryAlarmEarthquakeJohnCallsAlarmMaryCalls1. 2. 3.)|(),|( AJPBAJP=)|()|()|,( ABPAJPABJP=CS 1571 Intro to AIM. HauskrechtIndependences in BBNs2. Burglary is independent of Earthquake (not knowing Alarm) Burglary and Earthquake become dependent given Alarm !!BurglaryJohnCallsAlarmJohnCallsAlarmMaryCalls1. 3.)()(),( EPBPEBP=BurglaryAlarmEarthquake2.8CS 1571 Intro to AIM. HauskrechtIndependences in BBNs3. MaryCalls is independent of JohnCalls given AlarmBurglaryJohnCallsAlarmBurglaryAlarmEarthquake1. 2.JohnCallsAlarm3.MaryCalls)|(),|( AJPMAJP=)|()|()|,( AMPAJPAMJP=CS 1571 Intro to AIM. HauskrechtIndependences in BBN• BBN distribution models many conditional independence relations among distant variables and sets of variables• These are defined in terms of the graphical criterion called d-separation• D-separation and independence– Let X,Y and Z be three sets of nodes– If X and Y are d-separated by Z, then X and Y are conditionally independent given Z• D-separation :– A is d-separated from B given C if every undirected path between them is blocked with C• Path blocking– 3 cases that expand on three basic independence structures9CS 1571 Intro to AIM. HauskrechtUndirected path blockingA is d-separated from B given C if every undirected path between them is blocked• 1. Path blocking with a linear substructureZ in CXYX in A Y in BZCS 1571 Intro to AIM. HauskrechtUndirected path blockingA is d-separated from B given C if every undirected path between them is blocked• 2. Path blocking with the wedge substructureZ in CXYX in AY in BZ10CS 1571 Intro to AIM. HauskrechtUndirected path blockingA is d-separated from B given C if every undirected path between them is blocked• 3. Path blocking with the vee substructureZ or any of its descendants not in CXYX in A Y in BZCS 1571 Intro to AIM. HauskrechtIndependences in BBNs• Earthquake and Burglary are independent given MaryCalls ?BurglaryJohnCallsAlarmEarthquakeMaryCallsRadioReport11CS 1571 Intro to AIM. HauskrechtIndependences in BBNs•