### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# BAYESIAN NETWORK GRAPHS CSCE 582

GPA 3.61

### View Full Document

## 5

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 134 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 582 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/229593/csce-582-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for BAYESIAN NETWORK GRAPHS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Bayesian Networks and Decision Graphs Chapter 1 Chapter 1 p 113 Two perspectives on probability theory In many domains the probability of an outcome is interpreted as a relative frequency 39 The probability of getting a three by throwing a sixsided die is 16 However we often talk about the probability of an event without being able to specify a frequency for it 39 What is the probability that Denmark wins the world cup in 2010 Such probabilities are called subjective probabilities Chapter 1 p 213 Two perspectives on probability theory In many domains the probability of an outcome is interpreted as a relative frequency 39 The probability of getting a three by throwing a sixsided die is 16 However we often talk about the probability of an event without being able to specify a frequency for it 39 What is the probability that Denmark wins the world cup in 2010 Such probabilities are called subjective probabilities Possible interpretation 39 I receive Dkr 1000 if Denmark wins 39 f draw a red ball I receive Dkr 1000 VVVVVVVVVV AAAAAAAAAA Chapter 1 p 213 Basic probability axioms The set of possible outcomes of an experiment is called the sample space S 39 Throwing a six sided die 1 2 3 4 5 6 39 Will Denmark win the world cup yesno 39 The values in a deck of cards 2 3 4 5 6 7 8 9 10 J Q K A Chapter 1 p 313 Basic probability axioms The set of possible outcomes of an experiment is called the sample space S 39 Throwing a six sided die 1 2 3 4 5 6 39 Will Denmark win the world cup yesno 39 The values in a deck of cards 2 3 4 5 6 7 8 9 10 J Q K A An event 8 is a subset of the sample space 39 The event that we will get an even number when throwing a die 2 4 6 39 The event that Denmark wins yes 39 The event that we will get a 6 or below when drawing a card 2 3 4 5 6 Chapter 1 p 313 Basic probability axioms The set of possible outcomes of an experiment is called the sample space S 39 Throwing a six sided die 1 2 3 4 5 6 39 Will Denmark win the world cup yesno 39 The values in a deck of cards 2 3 4 5 6 7 8 9 10 J Q K A An event 8 is a subset of the sample space 39 The event that we will get an even number when throwing a die 2 4 6 39 The event that Denmark wins yes 39 The event that we will get a 6 or below when drawing a card 2 3 4 5 6 We measure our uncertainty about an experiment by assigning probabilities to each event The probabilities must obey the following axioms 39 PS 1 39 For all events 8 it holds that P8 2 0 0 H61 n52 6 then 1351 U82 P81P82 5 Chapter 1 p 313 Conditional probabilities Every probability is conditioned on a context For example if we throw a dice Psix Psixsymmetric dice In general if A and B are events and PAB x then In the context of B we have that PA 3 Note It is not whenever B we have PA but rather if B and everything else known is irrelevant to A then PA x Definition For two events A and B we have PA m B PltABgt 38 Example PA 4B 246 2 W 2 2 Chapter 1 p 413 Basic probability calculus the fundamental rule Let A B and C be events The fundamental rule PA n B PABPB The fundamental rule conditioned PA BC PAB CPBC Proof Derived directly from the definition of conditional probability Chapter 1 p 513 Basic probability calculus Bayes rule Bayes rule PBA PAIIDZ3LIDB Proof PBAPA PB m A PABPB Bayes rule conditioned HEW PltAlijgt wlcgt Example We have two diseases A1 and A2 that are the only diseases that can cause the symptoms 15 If 39 A1 and A2 are equally likely PA1 PA2 39 PBA1 09 39 PBA2 03 what are then the probabilities PA1B and PA2 lB Chapter 1 p 613 Basic probability calculus Let A B and C be events WWII The fundamental rule PA n B PABPB The conditional fundamental rule PA BC PAB CPBC Chapter 1 p 713 Basic probability calculus Let A B and C be events WWII The fundamental rule PA n B PABPB The conditional fundamental rule PA BC PAB CPBC PBIA M PBAPA PB m A PAlBPB Bayes rule conditioned PBA n C W Conditional independence If PAB n C PAC then PA BC PAC PBC Chapter 1 p 713 Probability calculus for variables A is a variable with states a1 an B is a variable with states b1 bm PA x1 xn is a probability distribution xi 2 2121 xi 1 2A PA 1 PAB is a n x m table containing the numbers Paibj Note 2A PAbj 1 for all bj B 01 02 03 A a1 04 03 06 02 06 07 04 PA B is a n x m table too ZAyB PA B 1 B b1 b2 b3 016 012 012 024 028 008 CL1 CL2 Chapter 1 p 813 The fundamental rule for variables PABPB n x m multiplications PaibjPbj Pa bj b b b b b b l 1 2 3 b1 b2 b3 l 1 2 3 a1 04 03 06 a1 016 012 012 04 04 02 02 06 07 04 02 024 028 008 PAB PB PA B Chapter 1 p 913 The fundamental rule for variables PABPB n x m multiplications Pa39bjPbj Pa39 bj b b b b b b l 1 2 3 b1 b2 b3 l 1 2 3 a1 04 03 06 a1 016 012 012 04 04 02 02 06 07 04 02 024 023 003 PAB PB PA B A is independent of B given C if PAB C PAC39 bl b2 b3 01 a2 01 0406 0406 0406 01 04 06 02 0703 0703 0703 02 07 03 PAB C PAC39 Chapter 1 p 913 Marginalization We have PA B and we need PA b1 b2 b3 G1 016 012 012 gt 04 Q 024 028 008 gt 06 B is marginalized out of PA B 24 01 24 01 A B 01 v A 01 A B 02 v A 01 B 03 016 012 012 04 m4 02 24 02 A B 01 v 24 02 A B 02 v A 02 A B 03 024 028 008 06 Notation PA 2 EB PA B Chapter 1 p 1013 Notation A potential qb is a table of real numbers over a set of variables domqb A table of probabilities is a probability potential Chapter 1 p 1113 Notation A potential qb is a table of real numbers over a set of variables domqb A table of probabilities is a probability potential Multiplication I b1 bg l b1 b2 b1 b2 Ll 2 1 Ll 1 2 CL1 Lg 3 4 Lg 5 6 Lg Chapter 1 p 1113 Notation A potential qb is a table of real numbers over a set of variables domqb A table of probabilities is a probability potential Multiplication I b1 bg l b1 b2 b1 b2 Ll 2 1 Ll 1 2 Ll 2 Lg 3 4 Lg 5 6 Lg Chapter 1 p 1113 Notation A potential qb is a table of real numbers over a set of variables domqb A table of probabilities is a probability potential Multiplication I b1 bg l b1 b2 b1 b2 a1 2 1 a1 1 2 a1 2 2 Lg 3 4 Lg 5 6 Lg Chapter 1 p 1113 Notation A potential qb is a table of real numbers over a set of variables domqb A table of probabilities is a probability potential Multiplication I b1 bg l b1 b2 b1 b2 a1 2 1 a1 1 2 a1 2 2 Lg 3 4 Lg 5 6 Lg 15 Chapter 1 p 1113 Notation A potential qb is a table of real numbers over a set of variables domqb A table of probabilities is a probability potential Multiplication I b1 b2 l b1 b2 b1 b2 a1 2 1 a1 1 2 a1 2 2 a2 3 4 a2 5 6 a2 15 24 Chapter 1 p 1113 Multiplication of potentials b1 b2 b1 b2 b1 b2 a1 1 3 01 6 7 a1 7 a2 4 5 C2 8 9 a2 7 7 1AB 2CB 153147370lt151AyB39lt152CB Chapter 1 p 1213 Multiplication of potentials b1 b2 b1 b2 l b1 b2 a1 1 3 01 6 7 al 6017862 7 a2 4 5 C2 8 9 a2 7 7 1511473 152073 153147370lt151AyB lt52CyB Chapter 1 p 1213 Multiplication of potentials b1 b2 b1 b2 b1 b2 a1 1 3 C1 6 7 all 6017802 21017 2702 a2 4 5 62 8 9 a2 1AB 2CyB 3AyBClt151AB39lt152CB Chapter 1 p 1213 Multiplication of potentials b1 b2 l b1 b2 b1 b2 Ll 1 3 C1 6 7 Ll 6017802 21017 2702 L2 4 5 C2 8 9 a2 24017 3202 7 1A7B 2CB 3A7B7CZ 1A7B39 2C7B Chapter 1 p 1213 Multiplication of potentials l b1 2 b1 b2 i b1 b2 a1 1 3 c1 6 7 a1 601802 2101 2702 L2 4 5 C2 8 9 a2 2401 3202 35014562 1A7B 2CB 3A7B7CZ 1A7B39 2C7B Chapter 1 p 1213 Marginalization of potentials CL1 CL2 Chapter 1 p 1313 Marginalization of potentials b1 b2 0 2 a1 2 3 2 C B Lg 1 4 2 Chapter 1 p 1313 Marginalization of potentials b1 b2 a 5 2 a1 2 3 1 5 B Lg 1 4 2 b b 1 2 a1 2 3 b A Q 1 4 2 Chapter 1 p 1313 Marginalization of potentials b1 b2 a 5 2 a1 2 3 1 5 B Lg 1 4 2 b1 b2 b 2 a1 2 3 b1 A Q 1 4 2 Chapter 1 p 1313 Bayesian Networks and Decision Graphs Chapter 2 Chapter 2 p 136 The grand vision An autonomous selfmoving machine that acts and reasons like a human We are still very far away from achieving this goal Chapter 2 p 236 The grand vision An autonomous selfmoving machine that acts and reasons like a human We are still very far away from achieving this goal Research is going in two directions Robotics Artificial intelligence Chapter 2 p 236 A recent achievement DARPA grand challenge 2005 Competition for autonomous vehicles navigate 132 miles through desert terrain route specified by approx 3000 waypoints 5 out of 23 vehicles completed the task Winner Stanley of Stanford Racing Team in 6h 53m 192 mph 39 7 Pentium M computers 39 Sensors 4 laserrange finders 1 radarsystem 1 stereo camera pair 1 monocular vision system GPS inertial measurement unit wheel speed Chapter 2 7 in 336 Robotics m 39 Visual recognition of objects 39 Recognition of sound patterns 39 Balancing to walk with n legs 39 Positioning in space Criteria of success Real time movement in space Chapter 2 p 436 Robotics m 39 Visual recognition of objects 39 Recognition of sound patterns 39 Balancing to walk with n legs 39 Positioning in space Criteria of success Real time movement in space Scientifically and computationally extremely demanding however 39 basically you construct a machine that behaves like an animal dog ant etc Chapter 2 p 436 Artificial intelligence Areas Complex arithmetic Reduction of mathematical expressions Computations Games chess Type setting Computers can do much of this they do not really require artificial intelligence A particular branch of Al has to do with reasoning Eg Logical reasoning Boolean algebra and its algorithms When a task is understood so much that it can be formalized then it is no longer considered intelligent Chapter 2 p 536 Boolean logic Examples lt rains gt The grass is wet lt rains The grass is wet lt rains gt The grass is wet The grass is not wet It does not rain What if there is uncertainty gt If I take a cup of coffee in the break then I may stay awake during the next lecture Uncertainty can appear and be expressed in several ways 39 Fuzzy concepts large heavy pretty 39 Uncertain information 39 Nondeterministic relations Disease gt Symptoms Treatment gt Result 39 Incomplete knowledgeinformation Chapter 2 p 636 Reasoning under uncertainty Imagine that we extend Boolean algebra with certainty x E 0 1 gt A holds with certainty Combination 39 I take a cup of coffee in the break gt 05 I will stay awake 39 I take a walk in the break gt 08 I will stay awake Suppose that I take a walk as well as have a cup of coffee Then 39 stay awake with certainty f05 08 Chapter 2 p 736 Reasoning under uncertainty Imagine that we extend Boolean algebra with certainty x E 0 1 gt A holds with certainty Combination 39 I take a cup of coffee in the break gt 05 I will stay awake 39 I take a walk in the break gt 08 I will stay awake Suppose that I take a walk as well as have a cup of coffee Then 39 stay awake with certainty f05 08 a gt mb b gt yC a c with certainty g1c y Abduction woman gt 08long hair long hair woman with certainty Chapter 2 p 736 Human wisdom Apply accumulated and processed experience nterpretatwon Learmng lt mtewentm Chapte rp m5 Car start problem In the morning my car will not start The start engine turns but nothing happens The battery is OK The problem may be due to dirty spark plugs or the fuel may be stolen I look at the fuel meter It shows and I therefore expect the spark plugs to be dirty We need to formalize this kind of reasoning o What made me focus upon fuel and spark plugs 0 Why did I look at the fuel meter 0 Why had fuel meter reading an impact on my belief in dirty spark plugs Chapter 2 p 936 The car start problem causally Events 0 Fueyn 0 Clean spark plugsyn o Startyn 0 Fuel meterfullempty Chapter 2 p 1036 The car start problem causally Events 0 Fuelyn 0 Clean spark plugsyn o Startyn 0 Fuel meterfullempty Causal relations Fuel Clean spark plugs Fuel meter Start When I enter the car l have some prior belief on the various events but then startn Chapter 2 p 1036 Direction change of belief Call 39 the direction from n to 3 positive 39 the direction more fuel positive Fuelgt gt Fuel meterUr gt Fuel gtJr Fuel meter Note Fuel metergt gt Fuelgt Chapter 2 p 1136 The reasoning Fuel Clean spark plugs Fuel meter Start Chapter 2 p 1236 The reasoning lt lt Fuel Clean spark plugs Fuel meter Start no Chapter 2 p 1236 The reasoning lt lt Fuel Clean spark plugs Fuel meter Start 1 V 5 Chapter 2 p 1236 Causal networks A causal network is a directed acyclic graph aa 9 39 The nodes are variables with a finite set of states that are mutually exclusive and exhaustive For example yn red blue green 012342 39 The links represent cause effect relations For example Religion Prot Cath Children 01232 4 Muslim All variables are in exactly one state but we may not know which one Chapter 2 p 1336 Reasoning under uncertainty 1 WaterLeve FOOding 39 Ifthere has been a flooding does that tell me something about the amount of rain that has fallen 39 The water level is high If there has been a flooding does that tell me anything new about the amount of rain that has fallen Chapter 2 p 1436 Reasoning under uncertainty 2 Sex man woman Stature lt 168cm 2 168cm 39 If a person has long hair does that say something about hisher stature 39 It is a woman If she has long hair does that say something about her stature Chapter 2 p 1536 Reasoning under uncertainty 3 39 Does salmonella have an impact on Flue 39 If a person is Pale does salmonella then have an impact on Flue Chapter 2 p 1636 Transmission of evidence 1 Relevance changes with evidence HQ 9 9 G Diverging i lt9 Converging Transmission of evidence 2 Can knowledge of A have an impact on our knowledge of J Transmission of evidence 2 Can knowledge of A have an impact on our knowledge of J yes Transmission of evidence 2 Can knowledge of A have an impact on our knowledge of B Transmission of evidence 2 Can knowledge of A have an impact on our knowledge of B yes Transmission of evidence 2 Can knowledge of A have an impact on our knowledge of G Transmission of evidence 2 Can knowledge of A have an impact on our knowledge of G yes Transmission of evidence 3 Is E dseparated from A Quantification of causal networks Religion Children ProtCath 0 1 2 3 gt 4 Muslim 7 7 7 7 The strength of the link is represented by probabilities P0lp P0C P0m P1IP P1C P1m P2IP P2C P2lm P3lp P3C P3m PZ 4 PZ 4C PZ 4lm Chapter 2 p 2036 Quantification of causal networks Religion Prot Cath Muslim Children 01232 4 The strength of the link is represented by probabilities Religion p c m P0p P0c P0m C 0 015 005 005 P1p P1c P1m 9 1 02 01 01 2 E P2p P2c P2m E 2 04 02 01 P3p P3c P3m g 3 02 04 01 P24p P24c PZ4m 24 005 025 035 PChildrenReligion Chapter 2 p 2036 Several parents Salmonella y n Pylyyn g y 0901 0604 39yn L39 n 0802 0109 ylnyn Pnnn PNauseaSalmonellaFlue Chapter 2 p 2136 Bayesian networks A causal network without directed cycles e e e o OK OK OK For each variable A with parents B1 Bn there is a conditional probability table PAB1 Bn 9 a Note Nodes without parents receive a prior distribution Chapter 2 p 2236 Belief updating in Bayesian networks Spark Plugs Chapter 2 p 2336 Belief updating in Bayesian networks Spark Plugs Consider evidence 61 Startn and find 39 PSpark Plugsel 2 39 PFuele1 2 39 PFuelMetere1 2 Chapter 2 p 2336 Belief updating in Bayesian networks Spark Plugs Consider evidence 61 Startn and find 39 PSpark Plugsel 2 39 PFuele1 2 39 PFuelMetere1 2 If we also have evidence egFuel Meter 2 what is 39 PSpark PlugS 1 2 2 PFue 1 2 2 Chapter 2 p 2336 Belief updating in Bayesian networks ll Consider again the network Religion Prot Cath Muslim Children 01232 4 Assume that the probabilities are PReligion 0 00 006m and Religion Religion p c m p c m 0 015 005 005 0 0135 0002 0003 C C 9 1 02 01 01 gt 9 1 018 0004 0006 39C 39C E 2 04 02 01 E 2 036 0008 0006 g 3 02 04 04 g 3 018 0016 0024 2 4 005 025 035 2 4 0045 001 0021 PChildrenReIigion PChildren Religion We want the probability PReligionChidren 3 Chapter 2 p 2436 Belief updating in Bayesian networks Let A B and C be variables The fundamental rule PA B PABPB Marginalization PA 2 EB PAB Bayes rule PABPB PBA 2 PM Chapter 2 p 2436 Belief updating in Bayesian networks ll Religion Prot Cath Muslim Children 01232 4 We can compute PReligionChidren 3 using Bayes rule PReligionChidren 3 P Children 3Religion PReligion ZReligion PReligionChildren 3 Religion p c m 0 0135 0002 0003 Religion C 9 1 018 0004 0006 Conditioning p c m E 2 036 0008 0006 Ch3 082 007 011 g 3 018 0016 0024 PReligionChidren23 Z 4 0045 001 0021 PChildren Religion Chapter 2 p 2436 Normalization Consider the joint probability table PA B C B 51 52 53 A a1 0005005 0050050 005005005 52 01010 01001 020005 Assume evidence 6 A a2 and C 2 c1 What is Chapter 2 p 2536 Normalization Consider the joint probability table PA B C B 51 52 53 A a1 0005005 0050050 005005005 52 01010 01001 020005 Assume evidence 6 A a2 and C 2 c1 What is PBe 010102 2 PBe PIDB 6 Chapter 2 p 2536 Normalization Consider the joint probability table PA B C B 51 52 53 A a1 0005005 0050050 005005005 52 01010 01001 020005 Assume evidence 6 A a2 and C 2 c1 What is PBe 010102 PB Pig 0 1 8 0 2 02502505 Chapter 2 p 2536 Conditional independence A is independent of B 39 Information on B does not change my belief in A PAB PA In the context c PABc PAc 39 A is independent of B given c If the state of B is known then A is independent of C39 PAB C PAB 96 Conditional independence is symmetric PAB C PAB 4 PCAB PC39B Chapter 2 p 2636 Conditional independence An example Turnover in type weekdayshop Type Shirts Jeans Underwear Mo 252 105 063 324 135 081 144 060 036 5 Tu 357149089 459191115 204085051 3 We 399166100 513214128 228095057 3 Th 420175105 540225135 240100060 Fr 462193165 594247149 264110066 8a 270 087 053 270 113 067 120 050 030 PShopShirts Mo 2 PShopMo 2 Chapter 2 p 2736 Conditional independence An example Turnover in type weekdayshop Type Shirts Jeans Underwear Mo 252105063 324 135 081 144 060 036 5 Tu 357149089 459191115 204085051 3 We 399166100 513214128 228095057 3 Th 420175105 540225135 240100060 Fr 462193165 594247149 264110066 8a 270 087 053 270 113 067 120 050 030 PShopShirts Mo PShopMo 2 252 105 063 252 105 063 2 06025015 Chapter 2 p 2736 Conditional independence An example Turnover in type weekdayshop Type Shirts Jeans Underwear Mo 252105063 324 135 081 144 060 036 5 Tu 357149089 459191115 204085051 3 We 399166100 513214128 228095057 3 Th 420175105 540225135 240100060 5 Fr 462193165 594247149 264110066 8a 270 087 053 270 113 067 120 050 030 PShopShirts Mo 252105063 252 105 063 252 324 144105 135 06 063 081 036 2 06025015 2 06025015 PShopMo 12 Chapter 2 p 2736 Bayesian belief updating Find PBa7 fg h Chapter 2 p 2836 Bayesian belief updating 0 9 0 Find PBa fg h 0 6 0 We can if we have access to Pa B C D E fg h PBafgh Z PaBCDEfgh CDE PB7a 7f7g7h PltBlafghgt ngh where Pm mm ZPltBafg h B Chapter 2 p 2836 Joint probabilities PA 9 Calculate PA B C D E PBA PCA 9 PDBC39 PEC39 Chapter 2 p 2936 Joint probabilities 9 Calculate PA B C39 D E PBIA PltCIAgt PA B CDE PEA B CDPA B C39 D Chapter 2 p 2936 Joint probabilities 9 Calculate PA B C39 D E PBIA PltCIAgt PA B CDE PEA B CDPA B C D PEC39PA BC39 D Chapter 2 p 2936 Joint probabilities 9 Calculate PA B C39 D E PBIA PltCIAgt PA B C DE PEA B CDPA B C D PEC39PA BC39 D PEC39PDA B CPA B 0 Chapter 2 p 2936 Joint probabilities 9 Calculate PA B C39 D E PBIA PltCIAgt PA B C39 DE PEA B CDPA B C39 D EICPA7 B C D EICPDA7 B CPA7 B C ECPDB CPA B 0 Chapter 2 p 2936 Joint probabilities 9 Calculate PA B C D E PBIA PltCIAgt HA a mszARQmHARQm E HARQM WPMARCHARQ E Q HMRQHARQ EQH maumAmmAm Chapter 2 p 2936 Joint probabilities 9 Calculate PA B C D E Hmm quotnapmw HA a mszARQMHARQm mCPmaumAmmAm Dmpwcwmam MRQHARQ Chapter 2 p 2936 Joint probabilities Calculate PA B C D E EQHARQm ECPMARQHARQ CPMRQPARQ Q mamammmAmmAm wwmpwmwmam gtmm wmwmmmmm Chapter 2 p 2936 The chain rule Let BN be a Bayesian network overu A1 An Then PW Hi PAz39PaAz397 where PaAi are the parents of Ai 39 P01 is the product of the potentials specified in BN 39 BN is a compact representation of P01 PW HAIL ADPW A PAB C HXEMW PXPaX Chapter 2 p 3036 Evidence I Consider a variable A with five states a1 a2 a3 a4 a5 and with probability 531 2 5 PA x3 1 x4 z391 5 Assume that we get the evidence 6 A is either in state L2 or a4 Then 0 x1 0 x2 x2 1 PA e 0 x3 0 x4 x4 1 0 x5 0 Thus 6 can be represented by a potential 6 01010T and PAe PA 6 Chapter 2 p 3136 Evidence Definition Let A be a variable with n states A finding on A is an n dimensional table with Us and ls Semantics The states marked with a 0 are impossible Theorem Let BN be a Bayesian network overthe universe u A1 An and let 61 62 an be findings Then Hence to find PAe we use Chapter 2 p 3236 Variable elimination PM Do we need P01 2 PABC39DE In order to calculate PAc e 9 PBA PCA Note PAcye 9 e PDBC39 PEC Chapter 2 p 3336 Variable elimination PM Do we need P01 2 PABC39DE In order to e calculate PAce P ABCDe PltBIAgt 3 9 PltCIAgt Note PltAlcyegt Z Z PA B c D e Z Z PecPcAPDc BPAPBA BD BD Chapter 2 p 3336 Variable elimination Do we need P01 2 PABC39DE in order to e calculate PAc e P ABCDe PltBIAgt 3 9 PltCIAgt Note PltAlcyegt BD Chapter 2 p 3336 Variable elimination Do we need P01 2 PABC39DE in order to e calculate PAc e P ABCDe PltBIAgt 3 9 PltCIAgt Note PltAlcyegt ZZPABCD6 PecPcAPDcBPAPBA B D B D P PCAPA Z ZPD07 BPBA B D PecPcAPA Z PBA Z PDc B B D Chapter 2 p 3336 Variable elimination PM Do we need P01 2 PABC39DE in order to e calculate PAc e P ABCDe PltBIAgt 3 9 PltCIAgt Note PltAlcyegt ZZPABCD6 PecPcAPDcBPAPBA B D B D Pe PcAPAZZPDICBPBA B D PecPcAPA Z PBA Z PDc B B D PecPcAPA So instead of constructing a table with 25 entries we only need 2 numbers Chapter 2 p 3336 The Munin network Left Suralls Right Suralls Characteristics gt Approximately 1100 variables gt Each variable has between 2 and 20 states gt 10600 possible state configu rations A system for diagnosing neuromuscular diseases Chapter 2 p 3436 Graphical models Bayesian networks is one example of graphical models Qualitative part A graph With nodes and links Quantitative part A set Of potentials Pros 39 Graphs are excellent for interhuman communication 39 Graphical models can be given a sufficient formal semantics 39 Graphical models can be given a formal semantics so that they can be read by computers Problems 39 The scope of the models 39 The computation task may be intractable Chapter 2 p 3536 Summary What have we considered today 39 Conditional independence A and C are independentgiven B if PAC39 B PAB This is related to serial and diverging connections 39 Bayesian networks A directed acyclic graph where there for each node A with parents B1 Bn is attached a conditional probability table PAB1 Bn 39 The chain rule For a Bayesian network overu A1 An we have PW 1 12 PA PaAz39 39 Evidence If 61 m are findings then n m 21 A P017 6 Pue H PAiPaAi H ej PAe z391 j1 Chapter 2 p 3636 Bayesian Networks and Decision Graphs Chapter 7 Chapter 7 p 127 Learning the structure of a Bayesian network We have gt A complete database of cases over a set of variables We want gt A Bayesian network structure representing the independence properties in the e databas mpr m Bayesian networks from databases Example Transmission of symbol strings PDQl Last 3 ma aab aba abb baa bab bba bbb cm 0017 0021 0019 0019 0045 0068 0045 0068 ab 0033 0040 0037 0038 0011 0016 0010 0015 be 0011 0014 0010 0010 0031 0046 0031 0045 bb 0050 0060 0057 0057 0016 0023 0015 0023 First 2 Consider the model N as representing the database 06606 39 Simpler than the database 39 A representation of the database The chain rule yields the joint probability which we can compare to the actual database PNu PT1T2T3T4T5 PT1PT2T1PT3T2PT4T3PT5T4 Chapter 7 p 327 Bayesian networks from databases Example Transmission of symbol strings PDQl Last3 ma Lab aba abb baa bab bba bbb cm 0017 0021 0019 0019 0045 0068 0045 0068 ab 0033 0040 0037 0038 0011 0016 0010 0015 if ba 0011 0014 0010 0010 0031 0046 0031 0045 bb 0050 0060 0057 0057 0016 0023 0015 0023 Consider the model N as representing the database Last3 aaa Lab aba abb baa bab bba bbb cm 0016 0023 0018 0021 0044 0067 0050 0061 ab 0030 0044 0033 0041 0011 0015 0012 0014 if ba 0010 0016 0012 0014 0029 0045 0033 0041 bb 0044 0067 0059 0061 0016 0023 0017 0021 Are PNLI and PDQl sufficiently identical Chapter 7 p 427 A naive way to look at it Some agent produces samples D of cases from a Bayesian network M over the universe u gt These cases are handed over to you and you should now reconstruct M from the cases Assumptions gt The sample is fair PDQl reflects the distribution determined by M gt All links in M are essential A na39ive procedure 39 For each Bayesian network structure N Calculate the distance between PNLI and PDQl 39 Return the network N that minimizes the distance and where all links are essential But this is hardly feasible Chapter 7 p 527 The space of network structures is huge The number of DAG structures as a function of the number of nodes TL 41 1 z39 n z39 gt m lt 1gt mw gtfltn zgt Some example calculations Nodes Number of DAGs Nodes Number of DAGs 1 1 13 19 1031 2 3 14 14 1036 3 25 15 24 1041 4 543 16 84 1046 5 29281 17 63 1052 6 38106 18 991058 7 11 109 19 33 1065 3 78 1011 20 235 1072 9 12 1015 21 351079 10 42 1018 22 11 1087 11 32 1022 23 70 1094 12 52 1026 24 94 10102 Chapter 7 p 627 Two approaches to structural learning Score based learning gt Produces a series of candidate structures gt Returns the structure with highest score Constraint based learning gt Establishes a set of conditional independence statements for the data gt Builds a structure with dseparation properties corresponding to the independence statements found Chapter 7 p 727 Constraint based learning Some notation gt To denote that A is conditionally independent of B given 26 in the database we shall use Some assumptions 1473795 gt The database is a faithful sample from a Bayesian network M A and B are dseparated given 26 in M if and only if A B26 gt We have an oracle that correctly answers questions of the type Is A B X The algorithm Use the oracle s answers to first establish a skeleton of a Bayesian network gt The skeleton is the undirected graph obtained by removing directions on the arcs Next when the skeleton is found we then start looking for the directions on the arcs Chapter 7 p 827 Finding the skeleton l The idea if there is a link between A and B in M then they cannot be dseparated and as the data is faithful it can be checked by asking questions to the oracle gt The link A B is part of the skeleton if and only if AHA B X for all 6 Assume that the only conditional independence found is A B The skeleton The only possible DAG Assume that the conditional independences found are A B D and C39 D A B GD Chapter 7 p 927 Finding the skeleton The idea if there is a link between A and B in M then they cannot be dseparated and as the data is faithful it can be checked by asking questions to the oracle gt The link A B is part of the skeleton if and only if AHA B X for all 6 Assume that the only conditional independence found is A B The skeleton The only possible DAG Assume that the conditional independences found are A B D and C39 D A B Chapter 7 p 1027 Setting the directions on the links Rule 1 Ifyou have three nodes A B C such that A C39 and B C39 but not A B then intro duce the vstructure A gt C lt B if there exists an 26 possibly empty such that A B X andC39gZX gt 0 G 9 9 Example Assume that we get the independences A B B C A B C B C39 A C39 DA B C DA C39 D A B IB E CD IAE 0 D IBC39 A DE IAE BC39 D IBE A C39 D Chapter 7 p 1127 Setting the directions on the links Rule 1 Ifyou have three nodes A B C such that A C39 and B C39 but not A B then intro duce the vstructure A gt C lt B if there exists an 26 possibly empty such that IA B X andC39gZX s 0 9 BC Example Assume that we get the independences IA B I I A B C I B C39 A IC39DA IBCDA IC39D AB IBECD IAEC39D IBC39 A DE IAE BC39 D IBE A C39 D Chapter 7 p 1227 Setting the directions on the links ll Rule 2 Avoid new vstructures When Rule 1 has been exhausted and you have A gt C B and no link between A and B then direct C gt B Rule 3 Avoid cycles If A gt B introduces a directed cycle in the graph then do A lt B Rule 4 Choose randomly If none of the rules 13 can be applied anywhere in the graph choose an undirected link and give it an arbitrary direction Example Skeleton Rule 1 Rule 4 Chapter 7 p 1327 The rules an overview Rule 1 Find vstructures If you have three nodes A B C such that A C and B C39 but not A B then introduce the vstructure A gt C lt B if there exists an 26 possibly empty such thatIA BX and C 9 X Rule 2 Avoid new vstructures When Rule 1 has been exhausted and you have A gt C B and no link between A and B then direct C gt B Rule 3 Avoid cycles If A gt B introduces a directed cycle in the graph then do A lt B Rule 4 Choose randomly If none of the rules 13 can be applied anywhere in the graph choose an undirected link and give it an arbitrary direction Chapter 7 p 1427 Another example Consider the graph Apply the four rules to learn a Bayesian network structure Chapter 7 p 1527 Another example I Step 1 Rule 1 Another example I Step 1 Rule 1 Step 2 Rule 2 Another example I Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Another example I Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Step 4 Rule 2 Another example I Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Step 4 Rule 2 Step 5 Rule 2 Chapter 7 p 1627 Another example I Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Step 4 Rule 2 Step 5 Rule 2 Step 6 Rule 4 However we are not guaranteed a unique solution Chapter 7 p 1627 Another example Step 1 Rule 1 Step 2 Rule 2 Another example ll Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Another example ll Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Step 4 Rule 4 Another example ll Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Step 4 Rule 4 Step 5 Rule 2 Chapter 7 p 1727 Another example ll Step 1 Rule 1 Step 2 Rule 2 Step 3 Rule 4 Step 4 Rule 4 Step 5 Rule 2 Step 6 Rule 23 Although the solution is not necessarily unique all solutions have the same dseparation properties Chapter 7 p 1727 From independence tests to skeleton Until now we have assumed that all questions of the form Is A B X can be answered allowing us to establish the skeleton However questions come at a price and we would there like to ask as few questions as possible To reduce the number of questions we exploit the following property Theorem The nodes A and B are not linked if and only if A B paA or A B paB It is sufficient to ask questions A B X where X is a subset of A s or B s neighbors a e 9 An active path from A to B must go through a parent of B Chapter 7 p 1827 The PC algorithm The PC algorithm 1 Start with the complete graph 2 i z 0 3 while a node has at least 1 1 neighbors for all nodes A with at least 1 1 neighbors for all neighbors B of A for all neighbor sets 26 such that 2 z and X g nbA B if A B X then remove the link A B and store quotIA B Xquot i z i l 1 Chapter 7 p 1927 Example We start with the complete graph and ask the questions IAB IAC39 IAD A E B C B D IBE 10 D 0 E IDE o e eve The original model The complete graph Chapter 7 p 2027 Example We start with the complete graph and ask the questions IAB IAC39 IAD A E B C B D IBE 0 D 0 E D E o e eve e e e e a a The original model The complete graph We get a yes for A B and B C gt the links A B and B C are therefore removed Chapter 7 p 2127 Example We now condition on one variable and ask the questions IAC39E IAEC39 B C39 D B C39E B D C B DE IBE C B E D 0 BA IC39 D A 0 DB The original model After one iteration Chapter 7 p 2227 Example We now condition on one variable and ask the questions IAC39E IAEC39 B C39 D B C39E B D C B DE IBE C B E D 0 BA IC39 D A 0 D B The original model After one iteration The question 0 D A has the answer quotyesquot gt we therefore remove the link C D Chapter 7 p 2327 Example We now condition on two variable and ask questions like B C D E The original model After two iterations The questions B E 0 D and E A D 0 have the answer yes gt we therefore remove the links B E and A E Chapter 7 p 2427 Example We now condition on three variables but since no nodes have four neighbors we are finished The original model After three iterations The identified set of independence statements are then IAB IBC39 ICDA A E 0 D and B E 0 D They are sufficient for applying rules 14 Chapter 7 p 2527 Real world data The oracle is a statistical test eg conditional mutual information PABX CEA BX Z PX Z PA BX log W X AB A BX e CEA BX 0 However all tests have false positives and false negatives which may provide false re sultscausal relations Similarly false results may also be caused to hidden variables Chapter 7 p 2627 Properties gt If the database is a faithful sample from a Bayesian network and the oracle is reliable then a solution exists gt You can only infer causal relations if no hidden variables exists Chapter 7 p 2727

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.