09. Bayesian Networks Flashcards
Explain normalisation.
compute distribution on query variable by fixing evidence variables (here: Toothache) and summing over hidden variables (here: Catch).
slide 22
Bayesian Networks
A full joint probability distribution can answer any question about a domain, but …
Independence and conditional independence can greatly …
Bayesian networks are used to …
can become intractably large as the number of variables grows.
reduce the amount of information required to construct the joint probability.
represent dependencies among variables.
Bayesian network
A Bayesian network is a …, where
each node corresponds to a …,
arrows between nodes start at parents,
each node Ni has a conditional probability distribution P(Xi |Parents (Xi )).
directed acyclic graph,
random variable
Compactness of Bayesian Networks
Each conditional probability table (see previous slide) for Boolean Xi with k Boolean parents has
Each row requires one number p for Xi = true (the number for Xi =falseisjust1−p).
If each variable has no more than k parents, the complete network requires …
Thus, the space requirement grows linearly with n, vs. O(2^n) for the full joint distribution.
Burglaryscenario: 1+1+4+2+2=10numbers (vs.25−1=31)
2^k rows for the combinations of parent values.
O(n · 2k ) numbers for n variables.
Determine Conditional Independence in Bayesian Networks
Independence
Variables X and Y are independent
⇔ P(X,Y) = P(X)P(Y) or P(X|Y) = P(X) or P(Y|X) = P(Y) ⇔ Variables X and Y share no common ancestry.
Explain conditional independence.
Conditional Independence
Variables X and Y are conditionally independent given a set of evidences Z
⇔ P(X|Y,Z) = P(X|Z) or P(Y|X,Z) = P(Y|Z)
⇔ every path from X to Y in an undirected Moral graph is blocked by Z (see next slide).
Determine Conditional Independence Graphically (5)
Is a set of nodes x conditionally independent of another set of nodes y given the set of evidences z (proof omitted)?
1 Ancestral subgraph: …
2 Moral graph: …
3 Replace …
4 All paths between any x and y are blocked by z ⇒ …
all nodes x , y , z , and their ancestors.
add links between any unlinked pair of nodes sharing a common child.
all directed links by undirected links.
conditional independence.
Practice for conditional independence
work examples slide 37-40
Typical Inference Tasks
Simple queries: compute probabilities given some evidence, e.g., P((NoGas = true)|(Gauge = empty),(Lights = on),(Starts = false))
Conjunctive queries: …
Optimal decisions: …
Value of information: which evidence to seek next?
Sensitivity analysis: …
Explanation: why do I need a new starter motor?
P(Xj,Xi|E) = P(Xj|Xi,E)P(Xi|E)
decision networks include utility information; probabilistic inference required for P(outcome|action, evidence)
which probability values are most critical?
xxx
review methods of likelihood weighting, rejection sampling, direct sampling, inference by enumeration pseudocode (slide 46-86
