A BAYESIAN NETWORK (belief network, causal network) is a DIRECTED ACYCLIC GRAPH in which: each NODE is a random variable each DIRECTED EDGE X → Y means X is a PARENT of Y, and is usually read as "X directly influences Y" each node has a CONDITIONAL PROBABILITY TABLE (CPT) giving P(node | parents), one distribution per combination of parent values the graph must be ACYCLIC — no directed cycles THE SEMANTICS, and this single equation is the whole formalism: P(x₁, …, xₙ) = Π P(xᵢ | parents(Xᵢ)) i=1..n THE FULL JOINT DISTRIBUTION IS THE PRODUCT OF THE LOCAL CONDITIONALS. Everything else — every query, every inference algorithm — follows from this. WHAT THE MISSING EDGES ASSERT — the crucial point: A node is CONDITIONALLY INDEPENDENT of its NON-DESCENDANTS GIVEN ITS PARENTS. So the network's content is as much in the ABSENT edges as in the present ones. A missing edge is a claim of conditional independence, and it is what buys the parameter saving. THE STANDARD EXAMPLE — the burglar alarm network: Burglary Earthquake │ │ └────────┬─────────┘ ▼ Alarm ╱ ╲ ▼ ▼ JohnCalls MaryCalls THE STORY: an alarm may be set off by a burglary or by a (minor) earthquake. Two neighbours, John and Mary, may telephone if they hear it. John sometimes confuses the alarm with a ringing telephone; Mary sometimes misses it because she plays loud music. THE CPTs: P(B) = 0.001 P(E) = 0.002 P(A | B, E): B E │ P(A = true) ──────────┼────────────── T T │ 0.95 T F │ 0.94 F T │ 0.29 F F │ 0.001 P(J | A): A=T → 0.90 A=F → 0.05 P(M | A): A=T → 0.70 A=F → 0.01 READ THE ASSERTIONS THE STRUCTURE MAKES: · J and M are CONDITIONALLY INDEPENDENT GIVEN A. Once you know whether the alarm sounded, John's call tells you nothing more about whether Mary will call. · J and M are NOT independent unconditionally — both are more likely when there is a burglary. · B and E are independent of each other (no edge), but become DEPENDENT once A is known — which is the explaining away effect covered in the next topic. · J does not depend directly on B at all: the alarm mediates the influence entirely. COMPUTING A JOINT PROBABILITY — the standard exam calculation. What is the probability that the alarm sounds, both neighbours call, and there is neither a burglary nor an earthquake? P(j, m, a, ¬b, ¬e) = P(j|a) × P(m|a) × P(a|¬b,¬e) × P(¬b) × P(¬e) = 0.90 × 0.70 × 0.001 × 0.999 × 0.998 = 0.000628 So about 0.06% — a false alarm with both neighbours calling is rare but far from impossible. NOTE THE METHOD: read the factors off the graph in topological order, one per variable, each conditioned only on its parents.

WHY BAYESIAN NETWORKS EXIST — count the numbers. THE FULL JOINT DISTRIBUTION over the alarm network's 5 boolean variables: 2^5 = 32 entries, of which 2^5 − 1 = 31 are independent (the last is determined because they sum to 1) THE NETWORK: P(B) 1 number P(E) 1 P(A|B,E) 4 (one per combination of two boolean parents) P(J|A) 2 P(M|A) 2 ─────────────── TOTAL 10 numbers 31 → 10, a saving of two thirds on a tiny network. THE SAVING GROWS EXPLOSIVELY WITH SIZE. In general, if each of n boolean variables has at most k parents: FULL JOINT: 2^n − 1 numbers NETWORK: n × 2^k numbers WORKED, with k = 3 parents at most: n = 10: full joint 1,023 network 10 × 8 = 80 n = 20: full joint 1,048,575 network 20 × 8 = 160 n = 30: full joint 1,073,741,823 network 30 × 8 = 240 n = 100: full joint ≈ 1.27 × 10^30 network 100 × 8 = 800 AT n = 30 THAT IS A BILLION NUMBERS AGAINST 240. And the difference is not merely storage: every one of those numbers would have to be ESTIMATED FROM DATA OR ELICITED FROM AN EXPERT, and no data set determines a billion parameters. THE NETWORK IS LINEAR IN n WHERE THE JOINT IS EXPONENTIAL, provided the number of parents stays bounded. THE CONDITION IS REAL, THOUGH: if a node has many parents its CPT grows as 2^k, so a node with 10 parents needs 1,024 numbers by itself. IN PRACTICE this is handled by · finding a better causal structure (usually the many-parent node indicates a missing intermediate variable) · using a CANONICAL DISTRIBUTION with few parameters — the NOISY-OR model needs only one number per parent instead of 2^k, on the assumption that each cause independently fails to produce the effect CONSTRUCTING A NETWORK — the procedure, and it matters that the order is right: 1. Choose an ORDERING of the variables, X₁ … Xₙ. 2. For i = 1 to n: add Xᵢ to the network choose as parents of Xᵢ the MINIMAL SET of X₁ … Xᵢ₋₁ such that Xᵢ is conditionally independent of the rest given those parents write the CPT ORDERING MATTERS ENORMOUSLY, and this is the most instructive point in the topic. Build the alarm network in the WRONG order — starting from the effects: MaryCalls, JohnCalls, Alarm, Burglary, Earthquake gives a network with MORE edges: J depends on M (because both depend on the unobserved alarm), B depends on A, E depends on both A and B. The result needs 13 numbers instead of 10, and the CPTs are ones no expert can supply — "what is the probability of a burglary given that the alarm sounded and there was no earthquake?" is not knowledge anyone has. ADD THE VARIABLES IN CAUSAL ORDER, CAUSES BEFORE EFFECTS. The result is sparser, and — decisively — the numbers are ones a domain expert can actually state. THAT IS THE PRACTICAL ARGUMENT FOR CAUSAL STRUCTURE: it is not philosophy, it is that causal CPTs are ELICITABLE and diagnostic ones are not. P(alarm | burglary) is a fact about the alarm; P(burglary | alarm) depends on the crime rate.

THE QUERIES A NETWORK ANSWERS: DIAGNOSTIC from effects to causes P(Burglary | JohnCalls) CAUSAL from causes to effects P(JohnCalls | Burglary) INTERCAUSAL between causes of a common effect P(Burglary | Alarm, Earthquake) MIXED a combination P(Alarm | JohnCalls, ¬Earthquake) THE GENERAL FORM of a query: given evidence e about some variables, compute the distribution of a query variable X: P(X | e) = α Σ over the hidden variables y of P(X, e, y) — that is, sum out everything not queried and not observed, then normalise. A WORKED EXACT INFERENCE, by enumeration: P(B | j, m) — the probability of a burglary given both calls = α Σ over e, a of P(b) P(e) P(a|b,e) P(j|a) P(m|a) For B = true: e=T,a=T: .001×.002×.95 ×.90×.70 = 0.000001197 e=T,a=F: .001×.002×.05 ×.05×.01 = 0.00000000005 e=F,a=T: .001×.998×.94 ×.90×.70 = 0.000591 e=F,a=F: .001×.998×.06 ×.05×.01 = 0.00000003 sum ≈ 0.000592 For B = false: e=T,a=T: .999×.002×.29 ×.90×.70 = 0.000365 e=F,a=T: .999×.998×.001×.90×.70 = 0.000628 (the a=F rows contribute ~0.0005 in total) sum ≈ 0.001495 Normalising: 0.000592 / (0.000592 + 0.001495) ≈ 0.284 SO P(Burglary | both neighbours called) ≈ 28%. The prior was 0.1%, so two phone calls raised the belief by a factor of roughly 280 — and it is still much more likely that there was no burglary. THE BASE RATE IS STILL DOING MOST OF THE WORK, which is the lesson of the Bayes topic appearing again in a structured setting. THE COMPLEXITY OF EXACT INFERENCE: · ENUMERATION is exponential in the number of variables · VARIABLE ELIMINATION does better by summing out variables in a good order and caching intermediate factors · for a POLYTREE (singly connected network — at most one undirected path between any two nodes) exact inference is LINEAR in the size of the network · in general, exact inference in Bayesian networks is #P-HARD, which is harder than NP-complete SO THE STRUCTURE DETERMINES THE COST, exactly as the tree-structured CSP result did in the search section — and for the same reason: acyclicity permits a single pass. APPROXIMATE INFERENCE, used when exact is infeasible: DIRECT SAMPLING generate whole samples from the network and count REJECTION SAMPLING generate samples and discard those inconsistent with the evidence — simple and wasteful when the evidence is unlikely LIKELIHOOD WEIGHTING fix the evidence variables and weight each sample by how likely that evidence was MARKOV CHAIN MONTE CARLO wander through the state space, (GIBBS SAMPLING) changing one variable at a time according to its conditional distribution ALL ARE CONSISTENT: the estimate converges to the true probability as the number of samples grows, which is what makes them usable without a correctness proof per query. WHERE BAYESIAN NETWORKS SIT AMONG THE REPRESENTATIONS OF THIS SECTION: semantic nets and frames structure, no uncertainty propositional logic certainty, no structure over objects first-order logic objects and relations, no uncertainty BAYESIAN NETWORKS uncertainty WITH structure, over a fixed set of variables and the remaining gap: Bayesian networks are essentially PROPOSITIONAL — they have variables, not objects and relations. Combining them with first-order expressiveness is the subject of STATISTICAL RELATIONAL LEARNING and remains an active research area, which is worth knowing as the honest edge of the field rather than a settled matter.