EVIDENCE PROPAGATES THROUGH A NETWORK ALONG PATHS, and whether a path CARRIES influence depends on its shape and on what is already known. There are exactly three ways three nodes can be connected, and each behaves differently. 1. CHAIN (causal or evidential trail) X → Y → Z WITHOUT Y KNOWN: X and Z are DEPENDENT — influence flows through Y. WITH Y KNOWN: X and Z become INDEPENDENT. Y BLOCKS the path. Burglary → Alarm → JohnCalls. Once you know whether the alarm sounded, the burglary tells you nothing more about John's call. 2. COMMON CAUSE (fork) X ← Y → Z WITHOUT Y KNOWN: X and Z are DEPENDENT — they share a cause, so seeing one is evidence for the other. WITH Y KNOWN: they become INDEPENDENT. Y BLOCKS. JohnCalls ← Alarm → MaryCalls. John calling makes Mary calling more likely — but only because both point at the alarm. Once the alarm's state is known, the two calls are unrelated. 3. COMMON EFFECT (collider, or v-structure) X → Y ← Z THIS ONE IS THE REVERSE OF THE OTHER TWO, and it is where mistakes are made. WITHOUT Y KNOWN: X and Z are INDEPENDENT. WITH Y KNOWN: they become DEPENDENT. Y UNBLOCKS the path. Burglary → Alarm ← Earthquake. Burglaries and earthquakes are unrelated events — until the alarm sounds. Then they compete to explain it, and learning about one changes belief in the other. AND THE SAME HOLDS IF ANY DESCENDANT OF Y IS OBSERVED: hearing that John called also unblocks the path, because John's call is evidence about the alarm. THE RULE, stated compactly — a path is BLOCKED by a set of observed variables E if it contains either · a chain or a fork whose middle node IS in E, or · a collider whose middle node and ALL its descendants are NOT in E Two variables are D-SEPARATED given E if EVERY path between them is blocked, and d-separation implies conditional independence. THE ASYMMETRY IS THE WHOLE POINT: for chains and forks, OBSERVING THE MIDDLE NODE CUTS THE CONNECTION. For colliders, observing it CREATES one.

EXPLAINING AWAY (also called INTERCAUSAL REASONING) is the collider case in action: two independent causes of one effect become NEGATIVELY correlated once the effect is observed, because each explains the effect and so reduces the need for the other. WORKED ON THE ALARM NETWORK, with the CPTs from the previous topic (P(B)=0.001, P(E)=0.002, P(A|B,E) = .95/.94/.29/.001): STEP 1 — the prior P(B) = 0.001 (0.1%) STEP 2 — the alarm sounds P(B | a) = 0.3736 (37.4%) A large jump: the alarm is strong evidence, because a false alarm has probability only 0.001. STEP 3 — and now we learn there was also an earthquake P(B | a, e) = 0.0033 (0.33%) THE BELIEF IN A BURGLARY COLLAPSES FROM 37.4% TO 0.33% — a factor of about 113 — WITHOUT ANY NEW INFORMATION ABOUT THE BURGLARY ITSELF. The earthquake explains the alarm, so the burglary is no longer needed as an explanation. THE SAME EFFECT IN THE OTHER DIRECTION: P(E | a) = 0.2310 (23.1%) P(E | a, b) = 0.0020 (0.20%) Learning of the burglary explains away the earthquake just as thoroughly. NOTE WHAT DID NOT HAPPEN: B and E are independent in the prior — no edge connects them, and P(B, E) = P(B)P(E). The dependence appeared ONLY because A was observed. THAT IS WHY THE COLLIDER RULE MATTERS: a naive system that treated "no edge" as "always independent" would get this wrong in exactly the case where it counts. WHY EXPLAINING AWAY IS HARD FOR RULE-BASED SYSTEMS: a production rule fires on its conditions and adds its conclusion. There is no natural mechanism for a NEW FACT TO REDUCE the certainty of an existing conclusion — the MYCIN-style certainty factors of the expert-systems tradition combine evidence but do not properly express competition between causes. Probability theory gets it for free, from the axioms, with no extra machinery. A SECOND FAMOUS INSTANCE — the "wet grass" network: Rain → WetGrass ← Sprinkler Grass is wet. Belief in rain rises. Then you notice the sprinkler is running, and belief in rain falls back toward its prior. Every human does this instantly; encoding it took the field two decades.

EXACT INFERENCE: INFERENCE BY ENUMERATION Write the query as a sum over the hidden variables of products of CPT entries, and evaluate it: P(X | e) = α Σ over y of Π P(vᵢ | parents(Vᵢ)) ✔ correct and simple ✘ exponential in the number of variables, and it recomputes the same subexpressions repeatedly VARIABLE ELIMINATION Sum out the hidden variables one at a time, storing each intermediate result as a FACTOR so it is computed once. Effectively dynamic programming on the enumeration sum. ✔ far better in practice — often orders of magnitude ✘ the cost depends critically on the ELIMINATION ORDER, and finding the optimal order is itself NP-hard. Heuristics (eliminate the variable with fewest neighbours first) work well. CLUSTERING / JOIN-TREE (junction-tree) ALGORITHMS Merge nodes into clusters until the network is a polytree, then propagate messages between clusters. This is what production systems use when many queries are asked of one network, because the expensive step is done once. THE COMPLEXITY RESULTS worth quoting: · for a POLYTREE (singly connected — at most one undirected path between any two nodes) exact inference is LINEAR in the size of the network · for a general (multiply connected) network, exact inference is #P-HARD — strictly harder than NP-complete THE STRUCTURE, NOT THE SIZE, DETERMINES TRACTABILITY. Same lesson as tree-structured CSPs and the same reason: acyclicity permits a single pass with no backtracking. APPROXIMATE INFERENCE — used when the network is too tangled: DIRECT (PRIOR) SAMPLING Sample each variable in topological order from its CPT given its already-sampled parents. Count the fraction of samples matching the query. ✔ trivially simple; converges to the true distribution ✘ cannot condition on evidence REJECTION SAMPLING Generate samples as above and THROW AWAY any that contradict the evidence. ✘ WASTEFUL IN EXACTLY THE CASES YOU CARE ABOUT. If the evidence has probability 0.001, then 999 of every 1,000 samples are discarded, so 1,000,000 samples yield about 1,000 usable ones. Rare evidence is common in diagnosis, which makes this method largely unusable there. LIKELIHOOD WEIGHTING FIX the evidence variables at their observed values, sample only the rest, and WEIGHT each sample by the product of the CPT entries for the fixed evidence. ✔ no samples are wasted ✘ if the evidence is unlikely, most weights are tiny and a few samples dominate, so the variance is high MARKOV CHAIN MONTE CARLO — GIBBS SAMPLING Start from any state consistent with the evidence, then repeatedly pick a non-evidence variable and resample it from its distribution given its MARKOV BLANKET (its parents, its children, and its children's other parents). Count the states visited. ✔ handles unlikely evidence well, and is the workhorse in practice ✘ successive samples are correlated, so convergence must be monitored; and it needs a BURN-IN period before the samples are representative ALL THREE SAMPLING METHODS ARE CONSISTENT: the estimate approaches the true probability as the sample count grows. That is the guarantee that makes them usable without a per-query proof — you trade an exact answer for a bounded-error answer and a knob controlling the error. THE MARKOV BLANKET, worth defining precisely because it is examined: a node is CONDITIONALLY INDEPENDENT OF EVERYTHING ELSE IN THE NETWORK given its parents, its children, and its children's other parents. Note that the children's other parents are included — that is the collider rule again, since observing a child unblocks the path to its co-parents.

WHERE THE NUMBERS COME FROM: ELICITATION FROM EXPERTS feasible for causal CPTs, as the previous topic argued, and hopeless for diagnostic ones LEARNING FROM DATA count frequencies where the data is complete; use EXPECTATION-MAXIMISATION where variables are hidden LEARNING THE STRUCTURE search over graphs, scoring each by how well it fits the data with a penalty for complexity. Much harder than learning the parameters, and the result is rarely uniquely determined by the data — several structures often fit equally well. THE PRACTICAL WARNING: a network's conclusions are only as good as its CPTs, and a confidently wrong prior produces a confidently wrong posterior. The base-rate result from the Bayes topic is the demonstration — get the prevalence wrong by a factor of ten and the diagnosis changes completely. WHAT BELIEF NETWORKS DO WELL, and where they stop: THEY DO WELL AT · combining several uncertain pieces of evidence coherently · reasoning in BOTH directions — causes to effects and effects to causes — with one model · explaining away, which no rule-based scheme handles · saying HOW CONFIDENT the conclusion is, not merely what it is · remaining INSPECTABLE: the graph and the CPTs are readable, so a clinician can check why a conclusion was reached — the explainability the AI applications topic identified as a regulatory requirement WHERE THEY STOP · they are essentially PROPOSITIONAL: variables, not objects and relations. You cannot say "every patient has some symptom" — each patient needs their own network. · the structure is FIXED in advance, so a cause nobody modelled cannot be inferred · continuous variables need discretisation or special distributions · exact inference is #P-hard in general · they model a SNAPSHOT; representing change over time needs DYNAMIC BAYESIAN NETWORKS, of which a HIDDEN MARKOV MODEL is the simplest case THE COMPARISON THAT CLOSES THIS SECTION — the five representations of ACtE0903, each with what it buys and what it cannot say: semantic nets / frames structure and inheritance; NO uncertainty, NO negation or quantification propositional logic sound proof, decidable; NO objects, NO quantification, NO uncertainty first-order logic objects, relations, quantifiers; NO uncertainty, only SEMI-decidable Bayes' rule evidence updates belief; NO structure — two variables at a time BELIEF NETWORKS uncertainty WITH structure over many variables; propositional, fixed structure, #P-hard exactly NO REPRESENTATION DOMINATES. Each gains expressiveness in one direction and pays in tractability or in what it can state at all — which is the four-properties trade-off from the first topic of this section, holding all the way through. THE PROFESSIONAL SKILL IS CHOOSING PER KIND OF KNOWLEDGE, and real systems combine several.