Uncertainty 2

29 flashcards · Mathematics · by J M COOPER

1. What is a Bayesian network? Describe its syntax.

   A simple, graphical notation for conditional independence assertions and hence for compact specification of full joint distributions. Syntax: a set of nodes, one per variable a directed, acyclic graph (link ≈ “directly influences”) a conditional distribution for each node given its parents: P(Xi|Parents(Xi)) In the simplest case, conditional distribution represented as a conditional probability table (CPT) giving the distribution over Xi for each combination of parent values

2. Given Boolean Xi with k Boolean parents, if each variable has no more than k parents, how many numbers would the complete network require? (In big O)

   O(n · 2k) I.e., grows linearly with n, vs. O(2n) for the full joint distribution

3. Describe the relationships between the four variables.

   Weather is independent of the other variables Toothache and Catch are conditionally independent given Cavity

4. How many rows would a CPT for Boolean Xi with k Boolean parents have?

   A CPT for Boolean Xi with k Boolean parents has 2k rows for the combinations of parent values. Each row requires one number p for Xi = true (the number for Xi = false is just 1 − p)

5. How can we reduce the size of a Bayesian network's CPT?

   Instead of free distributions, often canonical (parameterised) distributions are suggested. Deterministic nodes are the simplest case: X = f(Parents(X)) for some function f E.g., Boolean functions NorthAmerican ⇔ Canadian ∨ US ∨ Mexican E.g., numerical relationships among continuous variables ∂Level / ∂t = inflow + precipitation - outflow - evaporation

6. In Bayesian networks, what does CPT stand for?

   conditional probability table

7. I’m at work, neighbour John calls to say my alarm is ringing, but neighbour Mary doesn’t call. Sometimes it’s set off by minor earthquakes. Is there a burglar? Variables: Burglar, Earthquake, Alarm, JohnCalls, MaryCalls Network topology reflects “causal” knowledge: – A burglar can set the alarm off – An earthquake can set the alarm off – The alarm can cause Mary to call – The alarm can cause John to call Construct a bayesian network with conditional probability tables. (Choose any reasonable pr…

8. How is the size of a CPT related to the number of its parents?

   CPT grows exponentially with number of parents CPT becomes infinite with continuous-valued parent or child

9. How does one construct a Bayesian network such that a series of locally testable assertions of conditional independence guarantees the required global semantics? (pseudocode)

   1. Choose an ordering of variables X1, . . . , Xn 2. For i = 1 to n add Xi to the network select parents from X1, . . . , Xi−1 such that P(Xi|Parents(Xi)) = P(Xi|X1, . . . , Xi−1) This choice of parents guarantees the global semantics:

10. What does ⇔ mean?

    material equivalence, if and only if

11. What is a Markov blanket?

    Each node is conditionally independent of all others given its Markov blanket: parents + children + children’s parents

12. What is global semantics?

    “Global” semantics defines the full joint distribution as the product of the local conditional distributions.

13. What is local semantics?

    Local semantics: each node is conditionally independent of its nondescendants given its parents Theorem: Local semantics ⇔ global semantics

14. What is a leak node?

    It is common to associate a "leak" node with a noisy-or CPD, which is like a parent that is always on. This can account for all other unmodelled causes which might turn the node on.

15. How do Bayesian nets allow us to approximate inference?

    Approximate inference by stochastic simulation Approximate inference by Markov chain Monte Carlo

16. What is θ?

    Theta (lowercase)

17. What is a Noisy-OR distribution and why would one be used?

    Noisy-OR distributions model multiple noninteracting causes - a generalization of the logical OR. Three assumptions: 1. All possible causes Ui for a event X are listed (you can add a leak node) 2. Negated causes ¬Ui do not have any influence on X 3. Independent failure probability qi for each cause alone. Number of parameters linear in number of parents - make CPT more compact eg (as opposed to what though?)

18. What are Bayesian networks good for?

    Bayes nets provide a natural representation for (causally induced) conditional independence Topology + CPTs = compact representation of joint distribution Generally easy for (non)experts to construct

19. What is stochastic simulation?

    A stochastic simulation is a simulation that traces the evolution of variables that can change stochastically (randomly) with certain probabilities.

20. What kinds of queries can a bayesian network answer?

    Simple queries: compute posterior marginal P(Xi|E = e) e.g., P(NoGas|Gauge = empty, Lights = on, Starts = false) Conjunctive queries: P(Xi, Xj|E = e) = P(Xi|E = e)P(Xj|Xi, E = e) Optimal decisions: decision networks include utility information; probabilistic inference required for P(outcome|action, evidence) Value of information: which evidence to seek next? Sensitivity analysis: which probability values are most critical? Explanation: why do I need a new starter motor?

21. What is the big O in space and time of recursive depth first enumeration in a Bayesian network?

    O(n) space, O(dn) time

22. Infer by enumeration: Simple query on the burglary network (B|j, m) 2. Rewrite full joint entries using product of CPT entries: P(B|j, m)

    Simple query on the burglary network:P(B|j, m) = P(B, j, m)/P(j, m) = αP(B, j, m) = α Σe Σa P(B, e, a, j, m) Rewrite full joint entries using product of CPT entries: P(B|j, m) = α Σe Σa P(B)P(e)P(a|B, e)P(j|a)P(m|a) = αP(B) Σe P(e) Σa P(a|B, e)P(j|a)P(m|a)

23. What is inference by variable elimination?

    A generic algorithm for inference which eliminates one by one those variables which are irrelevant for the query.

24. What is a pointwise product?

    The pointwise product of two functions is another function, obtained by multiplying the image (the subset of a function's codomain which is the output of the function from a subset of its domain) of the two functions at each value in the domain.

25. Why is enumeration inefficient?

    Enumeration is inefficient: repeated computation e.g., computes P(j|a)P(m|a) for each value of e

26. How do we sum out a variable from a product of factors?

    Summing out a variable from a product of factors: move any constant factors outside the summation add up submatrices in pointwise product of remaining factors

27. Infer by variable elimination P(B|j, m)

28. Write a variable elimination algorithm.

29. Write an enumeration algorithm for a Bayesian network.