One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§12.2 — two coins behind one lamp
Two fair coins are tossed separately, so their results are independent. A lamp lights whenever at least one coin shows heads. You cannot see the coins, only the lamp, and the lamp is lit.
Find(a) What is the probability that coin 2 shows heads?
Given
$p(\text{heads})=\tfrac12$ for each coin, tossed independently
the lamp lights if and only if at least one coin shows heads
observed: the lamp is lit
Hint 1/4
Ask which outcomes of the two coins are still possible once you know the lamp is lit.
Seeing a common effect of two independent causes changes what we believe about each: the lamp alone moves coin 2 from $1/2$ to $2/3$.
A solar-powered sensor at a field station sends one packet every night, and tonight none arrived. A low battery or radio interference can each stop a packet, and on a normal night each happens $1$ time in $10$. Then a storm report says the radio band was jammed all night: should the technician worry more or less about the battery?
By the end you can put numbers on it: out of $1000$ nights with a lost packet the battery is low on about $597$, and out of $1000$ such nights with a storm, on only about $174$.
In 60 seconds
A graphical model writes a joint distribution as a product that a graph dictates: one factor $p(x_j\mid\mathrm{pa}_j)$ per node of a directed graph, one potential per maximal clique of an undirected one. The same graph tells which variables are independent given which.
an undirected graph with non-negative potentials; $\psi_c=e^{-E(x_c)}$ gives the
Three most common mistakes
Treating an observed head-to-head node as a blocker. Observing $c$ in $a\to c\leftarrow b$, or any of $c$, makes $a$ and $b$ dependent: a lost packet couples the battery and the interference.
Dividing $n_{jc}$ by $n$ instead of $n_c$. $\hat\theta_{jc}=n_{jc}/n_c$ is a rate inside class $c$; only the class share $\hat\pi_c=n_c/n$ uses $n$.
Leaving the co-parents out of a directed Markov blanket, or adding them to an undirected one. Directed: parents, children and the children's other parents. Undirected: the neighbours only.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has graphical models as its tenth item and names naive Bayes in its eleventh; the lecture slides teach both in chapter 12.
How much time do you have?
10 minutes
The three procedures of the section: write a factorization, decide independence by d-separation, train and use naive Bayes.
The 60-second card · Directed graphs: one factor per node · D-separation: when every path is blocked · Naive Bayes · Formula card
45 minutes
Every block once with its first worked example, then naive Bayes from fully worked to bare.
The 60-second card · Directed graphs: one factor per node · Three ways two arrows meet · D-separation: when every path is blocked · Naive Bayes · The Markov blanket · Markov random fields · Image denoising · Scaffolding comes off · Formula card
full read
Adds the proofs, the look-alike pairs, a full exam-style question and mixed practice where you pick the method yourself.
The opening pages · Recall first · Directed graphs: one factor per node · Three ways two arrows meet · D-separation: when every path is blocked · Naive Bayes · The Markov blanket · Markov random fields · Image denoising · Look-alike pairs · Method boxes · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Write the joint distribution of a directed acyclic graph as a product of parent conditionals, count its free numbers, and draw a sample by .
Decide what observing the middle node does in the tail-to-tail, head-to-tail and head-to-head graphs, and compute an explaining-away posterior by enumeration.
Apply d-separation to decide whether $A\perp\!\!\!\perp B\mid C$ in a directed graph, checking every path.
Train a by maximum likelihood, with counts for Bernoulli features and class means and variances for Gaussian ones, and classify a new point.
Find the Markov blanket of a node in a directed graph and compute $p(x_i\mid x_{j\ne i})$ from the blanket's factors alone.
List the cliques and maximal cliques of an undirected graph, write its factorization with potentials and $Z$, and read by separation.
Write the energy of the image-denoising model and run coordinate-wise updates until a full sweep changes nothing.
Syllabus coverage
covered
Probabilistic graphical models — covered
Directed acyclic graphs and the factorization of the joint
the chain rule as the complete graph
parameter counts
ancestral sampling
undirected graphs, cliques and potentials
The lecturer's chapter title. The chapter moves from directed to undirected models, and so does this section.
covered
Inference in graphical models — covered
Conditional independence read off the graph: the three-node rules, d-separation, Markov blankets and separation in undirected graphs. Posteriors by enumeration and explaining away, the naive Bayes posterior, and the most probable image by coordinate-wise energy descent.
Several blocks share this token; the explaining-away example is where it first appears.
covered
Learning in graphical models — covered
Maximum likelihood for a naive Bayes classifier: counts for Bernoulli features, class means and variances for Gaussian ones, and the Lagrange multiplier behind the class shares.
The STARS weekly list names naive Bayes in its eleventh item, beside restricted Boltzmann machines; the chapter 12 slides teach it here, so this section covers it.
off syllabus
Pseudo-counts against zero counts — off syllabus
Adding one imaginary success and one imaginary failure to every naive Bayes count, so that no estimate is exactly $0$ or $1$.
Further reading, not on the slides. It appears in one interleaved question, where it links naive Bayes with the Beta prior of the Bayesian estimation section.
off syllabus
Gaussian naive Bayes and logistic regression — off syllabus
With one variance shared by both classes, the naive Bayes log-odds is linear in $x$.
Further reading, used in one interleaved question only.
Recall first
Conditional probability and Bayes' rule
$p(a\mid b)=\dfrac{p(a,b)}{p(b)}$ for $p(b)>0$, and $p(a\mid b)=\dfrac{p(b\mid a)\,p(a)}{\sum_{a'}p(b\mid a')\,p(a')}$.
Every posterior on this page, from explaining away to naive Bayes, is this formula.
Summing out
$p(a)=\sum_b p(a,b)$, and $p(a\mid e)=\sum_b p(a,b\mid e)$; for a continuous $b$ the sum is an integral.
Inference by enumeration sums the joint over every variable that was not observed.
Independence
$a$ and $b$ are independent when $p(a,b)=p(a)\,p(b)$ for every pair of values.
Conditional independence is the same test inside the distribution given $c$.
Maximum likelihood estimates
$\hat\theta=\arg\max_\theta\sum_i\log p(x_i\mid\theta)$. Bernoulli: successes over trials. Gaussian: $\hat\mu=\frac1n\sum_ix_i$ and $\hat\sigma^2=\frac1n\sum_i(x_i-\hat\mu)^2$.
Naive Bayes is trained with exactly these estimates, one class at a time.
Lagrange multipliers
To maximize $f(\pi)$ subject to $g(\pi)=0$, solve $\nabla f=\lambda\nabla g$ together with $g(\pi)=0$.
The class shares must add up to $1$, and the multiplier enforces it.
Gaussian naive Bayes multiplies one such density per feature.
Try it yourself first (2 questions)
1§12.1 — the size of a full joint table
A lab stores the joint distribution of $10$ binary sensor readings as one full table, with a probability for every combination of values.
Find(a) How many numbers in the table can be chosen freely?
Given
$10$ sensors, each reading $0$ or $1$
the table lists every combination
Hint 1/4
First count the combinations of values, then ask whether all of them are free.
Hint 2/4
$D$ binary variables have $2^D$ combinations; the probabilities add up to $1$.
Hint 3/4
With $D=10$: $2^{10}=1024$ cells, one of them fixed by the other $1023$.
Hint 4/4
The table has $1023$ free numbers.
Show solution
Count the cells, then subtract the one cell that the sum-to-one rule fixes.
Cells
$$2^{10}=1024$$
Each variable doubles the number of value combinations.
Free cells
$$1024-1=1023$$
The cells add up to $1$, so the last one follows from the others.
Answer $$\boxed{1023}$$
Check
Check on $2$ variables: $2^2-1=3$ free numbers, for example $p(00)$, $p(01)$, $p(10)$, with $p(11)$ fixed by the rest.
A full joint table doubles with every new variable; that growth is what graphs are for.
2§12.2 — Bayes' rule for a fire alarm
A building's alarm rings on $90$ of every $100$ days with a fire and, falsely, on $5$ of every $100$ days without one. Fires happen on $1$ day in $100$.
Find(a) The alarm rings. What is the probability of a fire?
Given
$p(\text{fire})=0.01$
$p(\text{alarm}\mid\text{fire})=0.9$
$p(\text{alarm}\mid\text{no fire})=0.05$
Hint 1/4
You need the share of ringing alarms that come from real fires.
Hint 2/4
With $F$ = fire and $A$ = alarm: $$p(F\mid A)=\frac{p(A\mid F)\,p(F)}{p(A\mid F)\,p(F)+p(A\mid\bar F)\,p(\bar F)}$$
Hint 3/4
Numerator $0.9\times0.01=0.009$; the other term is $0.05\times0.99=0.0495$.
Hint 4/4
$0.009/0.0585\approx0.154$.
Show solution
Bayes' rule with the law of total probability in the denominator; the question gives exactly the pieces it needs.
training size; points of class $c$; points of class $c$ with $x_j=1$
$n_{jc}$ is counted inside class $c$ only.
$I(\cdot)$
indicator
$1$ if the statement inside is true, else $0$
$\theta^{I(x=1)}(1-\theta)^{I(x=0)}$ picks $\theta$ or $1-\theta$.
$M,\ \ x_c,\ \ \psi_c$
M; x c; psi c
the set of maximal cliques; the variables of clique $c$; its potential
$\psi_c\ge0$, but it is not a probability.
$Z$
Z
$\sum_x\prod_{c\in M}\psi_c(x_c)$, the normalizing constant
A sum over every configuration: $2^D$ terms for $D$ binary nodes.
$E(\cdot),\ \ \beta,\ \ \eta,\ \ h$
E; beta; eta; h
energy with $\psi=e^{-E}$; neighbour, data and bias weights in denoising
Lower energy means higher probability.
Conventions used here
Binary coding.
$1$ means the event happens and $0$ that it does not. In denoising, pixels take $+1$ (white) and $-1$ (black).
The factors and counts are written for these codes.
What 'dependent' means.
When a rule says two variables are dependent, it means: dependent for some choice of the tables, not necessarily for every choice. Independence read off the graph holds for every choice.
The graph knows which factors exist, not their numbers; special numbers can hide a dependence.
Paths ignore direction.
A path is a chain of edges walked either way along an arrow. Directions matter only when we check how the two arrows meet at each node of the path.
Information flows against arrows too, as explaining away shows.
Descendants.
$\mathrm{de}(v)$ holds the children of $v$, their children, and so on, but not $v$ itself.
The head-to-head rule asks about $v$ and $\mathrm{de}(v)$ separately.
Cliques have at least two nodes.
As in the lecture, a clique lists two or more nodes. A single node is trivially fully connected, and some books count it too.
Counts of cliques differ between books for this reason only.
Sampling from a uniform number.
To draw $x$ with $p(x=1)=q$ from $u$ uniform on $[0,1)$, set $x=1$ if $u<q$. With more than two values, cut $[0,1)$ into consecutive pieces in the listed order.
Fixing the rule makes every sampling example checkable.
Sweeps in denoising.
A sweep visits pixels row by row, left to right, and uses each new value at once. If both values give the same energy, the pixel keeps its value.
The order changes intermediate images, and the tie rule keeps the energy strictly falling.
Logs and decimals.
$\log$ is the natural logarithm, except $\log_2$ in the one mutual information question, which follows the feature selection section and counts bits. Numbers are computed from unrounded values and shown to three or four decimals.
Posteriors near $0$ or $1$ need the digits.
12.1Directed graphs: one factor per node
Draw the arrows, and the joint distribution becomes one small factor per node: fewer numbers to store, estimate and sample from.
The probability review handles any joint table; the trouble is its size, which doubles with every new variable.
Solvable with what we have
compute $p(L=1\mid F=1)$ once someone hands us the full table of the five sensor variables
reverse a conditional with Bayes' rule
get a marginal by summing the table
Not solvable yet
store that table cheaply: $31$ numbers for five binary variables, $1\,048\,575$ for twenty
estimate $31$ numbers from a few weeks of nights, when most combinations never occur
say which variables are irrelevant to a question without doing the sums
draw a random night without listing all $32$ cells
Keep only the marginal rates, $p(L=1)=0.1$, $p(F=1)=0.1517$, $p(S=1)=0.1526$, and multiply them as if the variables were independent: $p(L=1,F=1,S=1)\approx0.0023$, about $23$ nights in $10\,000$.
Why it fails
A low battery almost always loses the packet, and a lost packet almost always sends the SMS, so the three come together far more often than chance. The linked model below gives about $860$ nights in $10\,000$.
TheoremFactorization of a directed acyclic graph
Conditions
the graph is directed and acyclic: no path that follows the arrows returns to its start
$\mathrm{pa}_j$ is the set of parents of $x_j$; a root has none and contributes $p(x_j)$
each factor is a conditional distribution: for every value of $\mathrm{pa}_j$ it sums to $1$ over $x_j$ (integrates, for a continuous $x_j$)
The joint probability of all $D$ variables is a product with one factor per node: the probability of that node's value given the values of its parents. Arrows decide what each factor is conditioned on, and a missing arrow is a condition that was dropped.
Where the product comes from, and why cycles are forbidden
Order the nodes so that parents come before children; acyclicity guarantees such an order. The chain rule in that order is exact for any joint: $p(x_1, \allowbreak \dots, \allowbreak x_D)=\prod_jp(x_j\mid x_1, \allowbreak \dots, \allowbreak x_{j-1})$.
The graph states which earlier variables each $x_j$ still depends on: its parents. Dropping the others from each condition turns the chain rule into the product in the box.
The chain rule itself is the complete graph: node $j$ has every earlier node as a parent, $D(D-1)/2$ arrows in all. Every arrow removed from it is one conditional independence added.
The product is a valid distribution: sum first over a node with no children, whose factor adds up to $1$ and disappears, then repeat. A directed cycle has no such node to start from.
The sensor model as a graph. Each node stores one table, $\textcolor{#8250df}{p(x_j\mid\mathrm{pa}_j)}$, whose size is fixed by its parents, so the model needs $1+2+1+4+2=10$ numbers instead of the $31$ of a full table.
Looks like this, but is not
Any directed graph gives a valid factorization, cycles included: for $a\to b\to a$, take $p(a\mid b)\,p(b\mid a)$.
Let each variable copy the other with probability $0.9$. The four products are $0.81$, $0.01$, $0.01$ and $0.81$, which add up to $1.64$, not $1$. Without a parents-first order there is no node to sum out first.
A low battery, a lost packet and an SMS on the same night
The sensor's graph is $W\to L\to F\leftarrow R$ and $F\to S$, with the tables below. Find $p(L=1,F=1,S=1)$, and compare it with the product of the three marginal rates, $0.1\times0.1517\times0.1526$.
Find$p(L=1,F=1,S=1)$ and its ratio to the independence guess.
Sum the factored joint over the two variables nobody asked about, $W$ and $R$; each sum then acts only on the factors that contain its variable, so we never write the $32$-cell table.
The product of marginals ignores both links, $L\to F$ and $F\to S$.
Answer $$\boxed{\begin{aligned}&p(L=1,F=1,S=1)\\ &=0.0860\\ &\text{about }37\times\text{ the guess}\end{aligned}}$$
Check
Bayes-reversal route: $p(L=1\mid F=1)=0.597$ and $p(F=1,S=1)=0.1517\times0.95=0.1441$, so $0.597\times0.1441=0.0860$.
This closes the opening problem: $10$ numbers give $0.086$, while multiplying the marginals gave $0.0023$.
The factorization and the count for a six-node graph
Graph $G$ has the arrows $x_1\to x_2$, $x_1\to x_3$, $x_6\to x_3$, $x_2\to x_4$, $x_3\to x_4$ and $x_4\to x_5$. Write $p(x_1,\dots,x_6)$ and count its free numbers when all six variables are binary, and again when $x_1$ takes three values.
case 1: all binary; case 2: $x_1\in\{1,2,3\}$, the rest binary
Solution
Read the parents node by node from the arrows that point in; the count then follows factor by factor, which is far less error-prone than counting cells of the full table.
Test the rule on the complete graph over $3$ binary nodes, which is the chain rule: $1+2+4=7=2^3-1$, exactly the full table, as it must be.
Count parent configurations, not parents: a factor's size is the product of its parents' numbers of values, times one less than its own.
Drawing one night from the sensor model
Use the sensor tables and the uniform numbers $u_W=0.62$, $u_R=0.07$, $u_L=0.30$, $u_F=0.41$, $u_S=0.97$ to draw one night $(\hat W, \allowbreak \hat R, \allowbreak \hat L, \allowbreak \hat F, \allowbreak \hat S)$ by ancestral sampling.
Parents first: $W$ and $R$ are roots, $L$ needs $W$, $F$ needs $L$ and $R$, and $S$ needs $F$. Any order with parents before children works; this one is $W,R,L,F,S$.
The factorization gives this night the probability $0.5\times0.1\times0.95\times0.5\times0.05=0.0012$: rare, as it needs interference ($1$ night in $10$) and a failed SMS ($1$ in $20$).
Ancestral sampling needs only the factors and a parents-first order; it never builds the joint table.
Checkpoint
§12.1 — reading the joint off a graph
A directed graph $G$ on six variables has exactly six arrows: $x_1\to x_2$, $x_1\to x_3$, $x_6\to x_3$, $x_2\to x_4$, $x_3\to x_4$ and $x_4\to x_5$.
Find(a) Which product is $p(x_1,\dots,x_6)$ for this graph?
12.2Three ways two arrows meet: blocked, blocked, opened
Observing the middle node blocks tail-to-tail and head-to-tail connections but opens a head-to-head one: that is explaining away.
A missing arrow drops a condition from a factor; to see what that means for independence, we start with three nodes and two arrows.
TheoremConditional independence in the three three-node graphs
Conditions
$a\perp\!\!\!\perp b\mid c$ means $p(a,b\mid c)=p(a\mid c)\,p(b\mid c)$ for all values of $a$ and $b$ and every $c$ with $p(c)>0$
'dependent' means dependent for some choice of the tables (see the conventions)
$$\boxed{\begin{aligned}&a\leftarrow c\rightarrow b:\ a\perp\!\!\!\perp b\mid c\\ &\qquad\text{dependent without }c\\ &a\rightarrow c\rightarrow b:\ a\perp\!\!\!\perp b\mid c\\ &\qquad\text{dependent without }c\\ &a\rightarrow c\leftarrow b:\ a\perp\!\!\!\perp b\\ &\qquad\text{dependent given }c\end{aligned}}$$
When $c$ is a common parent or a link in a chain, $a$ and $b$ share information through $c$, and knowing $c$ cuts that channel. When $c$ is a common child, often called a , $a$ and $b$ have nothing in common until $c$ is observed; then each becomes evidence about the other.
Three short computations
Tail-to-tail, $p(a,b,c)=p(c)p(a\mid c)p(b\mid c)$. Dividing by $p(c)$ leaves $p(a\mid c)p(b\mid c)$. Without $c$, $p(a,b)=\sum_cp(c)p(a\mid c)p(b\mid c)$ is a mixture, which does not factor in general.
Head-to-tail, $p(a,b,c)=p(a)p(c\mid a)p(b\mid c)$. Bayes' rule turns $p(a)p(c\mid a)/p(c)$ into $p(a\mid c)$, so $p(a,b\mid c)=p(a\mid c)p(b\mid c)$. Without $c$, $p(a,b)=p(a)\sum_cp(c\mid a)p(b\mid c)$ still depends on $a$ through the sum.
Head-to-head, $p(a,b,c)=p(a)p(b)p(c\mid a,b)$. Summing over $c$ removes the last factor, so $p(a,b)=p(a)p(b)$. Given $c$, $p(a,b\mid c)=p(a)p(b)p(c\mid a,b)/p(c)$ keeps $a$ and $b$ together inside $p(c\mid a,b)$.
The middle node $\textcolor{#d1690a}{c}$ is observed in all three graphs. It $\textcolor{#8250df}{\text{blocks}}$ the tail-to-tail and head-to-tail connections and opens the head-to-head one; with $c$ unknown, each verdict flips.
Looks like this, but is not
No arrow joins $W$ and $F$ in $W\to L\to F$, so a cloudy day tells nothing about the packet.
An arrow is a direct dependence only; information also travels along paths. Clouds raise the chance of a low battery and so of a lost packet: $p(F=1\mid W=1)=0.194$ against $p(F=1\mid W=0)=0.110$. Only once $L$ is known does $W$ stop mattering.
evidence
p(L = 1)
per 1000
nothing
$0.100$
$100$
$F=1$
$0.597$
$597$
$F=1$, $R=1$
$0.174$
$174$
$F=1$, $R=0$
$0.833$
$833$
$F=1$ is a lost packet, $R=1$ a storm, $R=0$ a night without interference. The lost packet raises both causes; learning that one cause happened takes most of the suspicion off the other, and ruling it out puts the suspicion back.
Two thermometers and one heater: dependent, until the heater is known
A heater is on ($c=1$) or off with probability $0.5$ each. Two thermometers $a$ and $b$ each read 'warm' with probability $0.9$ when the heater is on and $0.2$ when it is off, independently given $c$. Show that $a$ and $b$ are dependent, and independent given $c$.
Find$p(a=1,b=1)$ against $p(a=1)p(b=1)$, then the same test given $c=1$.
Check $c=0$ as well: $p(a=1,b=1\mid c=0)=0.04=0.2\times0.2$. Both values of $c$ pass, which is what independence given $c$ requires.
A common parent makes its children look related; conditioning on the parent removes the resemblance.
Is the battery low? A lost packet, then a storm report
In the sensor model, $L$ (low battery) and $R$ (interference) are the two parents of $F$ (lost packet): $L\to F\leftarrow R$. Find $p(L=1)$, then $p(L=1\mid F=1)$, then $p(L=1\mid F=1,R=1)$.
FindThe three beliefs in a low battery.
Given
$p(L=1)=0.1$ (after summing out the weather), $p(R=1)=0.1$
The cells $p(L)p(R)p(F=1\mid L,R)$ are $0.9(0.9)(0.02)$, $0.9(0.1)(0.5)$, $0.1(0.9)(0.9)$ and $0.1(0.1)(0.95)$, for $(L,R)=(0,0), \allowbreak (0,1), \allowbreak (1,0), \allowbreak (1,1)$.
Average check: $p(R=1\mid F=1)=0.0545/0.1517=0.359$, and $0.3593(0.1743)+0.6407(0.8333)=0.597$, back to $p(L=1\mid F=1)$.
Four cells for $p(F=1)$, then two for each conditional.
This answers the opening question: the storm explains the lost packet away, and the battery drops from about $597$ in $1000$ back to $174$.
Checkpoint
§12.2 — a chain with its middle node observed
In the sensor model the weather $W$ affects the packet $F$ only through the battery: $W\to L\to F$ (the interference $R$ is the other parent of $F$). A technician already knows the battery is low, $L=1$.
Find(a) The technician then learns whether the day was cloudy. What happens to $p(F=1\mid L=1,W)$?
Given
$W\to L\to F\leftarrow R$
$p(F=1\mid L=1)=0.9(0.9)+0.1(0.95)=0.905$
observed: $L=1$
Hint 1/4
Ask through which nodes the weather can reach the packet.
Hint 2/4
Head-to-tail at $L$: $W\perp\!\!\!\perp F\mid L$.
Hint 3/4
With $L=1$ fixed, $p(F=1\mid L=1,W)=\sum_Rp(R)p(F=1\mid L=1,R)=0.9(0.9)+0.1(0.95)$ for either $W$.
Hint 4/4
It stays $0.905$ whatever the weather.
Show solution
Use the head-to-tail rule rather than enumerating: $W$ reaches $F$ only through $L$.
Where W enters
$$p(F\mid L,W)=\sum_Rp(R)\,p(F\mid L,R)$$
No factor of $F$ contains $W$; only $L$ and $R$ do.
Both values of W
$$p(F=1\mid L=1,W=1)=p(F=1\mid L=1,W=0)=0.905$$
The weather has nowhere else to act.
Answer $$\boxed{0.905\ \text{in both cases}}$$
Check
Without $L$ the weather does matter: $p(F=1\mid W=1)=0.194$ and $p(F=1\mid W=0)=0.110$.
Once the middle of a chain is known, the far end tells nothing new.
⚠ Treating an observed head-to-head node as a blocker
in two of the three graphs, observing the middle node does block
right$$a\perp\!\!\!\perp b\mid c\ \text{does not imply }a\perp\!\!\!\perp b\ \text{(two thermometers)}$$
12.3D-separation: when every path is blocked
Check every path between two sets; if the observed set blocks each one, the sets are conditionally independent.
A longer path is a string of three-node pieces, so the three rules of the previous block, applied node by node, decide any graph.
DefinitionBlocked paths and d-separation
Conditions
$A$, $B$, $C$ are disjoint sets of nodes; $C$ is observed
a path is any chain of edges from a node of $A$ to a node of $B$, walked either way along the arrows
$\mathrm{de}(v)$ is the set of descendants of $v$
$$\boxed{\begin{aligned}&\text{a path is blocked at }v\text{ if}\\ &\text{(1) }v\text{ is head-to-tail or}\\ &\qquad\text{tail-to-tail, and }v\in C\\ &\text{(2) }v\text{ is head-to-head, }v\notin C,\\ &\qquad\mathrm{de}(v)\cap C=\varnothing\\ &\text{all paths blocked}\\ &\qquad\Rightarrow\ A\perp\!\!\!\perp B\mid C\end{aligned}}$$
A path carries dependence unless one node on it stops the flow. A head-to-tail or tail-to-tail node stops it when the node is observed; a head-to-head node stops it unless the node or something below it is observed. If every path from $A$ to $B$ is stopped, $C$ d-separates $A$ from $B$, and $A$ and $B$ are independent given $C$.
Why the rules are the three-node rules, node by node (sketch)
Each interior node of a path sees two arrows, so it is one of the three graphs of the previous block. Rule (1) is the tail-to-tail and head-to-tail result; rule (2) is the head-to-head one.
A descendant of a collider carries information about it: if $c\to d$ and $d$ is observed, then $d$ acts as a noisy reading of $c$, and a reading of the common child couples its parents.
One blocking node is enough for a path, but every path must be blocked, because dependence can travel along any open one. The full proof that d-separation implies conditional independence for every choice of tables is longer and is not needed here.
Is $\textcolor{#1f6feb}{x_2}$ independent of $\textcolor{#1f6feb}{x_3}$ given $\textcolor{#d1690a}{x_1}$ and $\textcolor{#d1690a}{x_5}$? The $\textcolor{#8250df}{\text{upper path}}$ is blocked at $x_1$, but the $\textcolor{#d1690a}{\text{lower path}}$ is open, because the collider $x_4$ has an observed child.
Looks like this, but is not
Observing more variables can only make things more independent, so if $x_2\perp\!\!\!\perp x_3\mid x_1$ then also $x_2\perp\!\!\!\perp x_3\mid\{x_1,x_5\}$.
Observing $x_5$ opens the collider $x_4$ above it, and the lower path starts to carry dependence. Adding a node to $C$ can block a chain and open a collider at the same time.
Two paths between x2 and x3, and what observing x5 does
In graph $G$, decide whether $x_2\perp\!\!\!\perp x_3\mid x_1$, and whether $x_2\perp\!\!\!\perp x_3\mid\{x_1,x_5\}$.
FindBoth verdicts, with the blocking node of each path.
Same pattern as the sensor: $L$ and $R$ are independent, but not given $F$ or given $F$'s child $S$.
For two roots, look for colliders: each is closed until it or one of its descendants is observed.
Checkpoint
§12.3 — one true statement about graph G
Graph $G$ has the arrows $x_1\to x_2$, $x_1\to x_3$, $x_6\to x_3$, $x_2\to x_4$, $x_3\to x_4$ and $x_4\to x_5$. Exactly one of the statements below follows from d-separation.
right$$x_6\to x_3\leftarrow x_1,\ C=\varnothing:\ \text{blocked, so }x_6\perp\!\!\!\perp x_1$$
12.4Naive Bayes: a star-shaped graph that learns by counting
A classifier whose graph is a star: the label is each feature's only parent, so training is counting and prediction is one product per class.
So far the graph was given; now we choose one on purpose, a star around the class label, and the independences it states make learning a matter of counting.
TheoremNaive Bayes: model, decision and maximum likelihood estimates
Conditions
features $x=(x_1,\dots,x_D)$, label $y\in\{1,\dots,C\}$ with $p(y=c)=\pi_c$
the features are conditionally independent given $y$: arrows $y\to x_j$ only, none between features
The posterior of a class is its share times the probability of each observed feature under that class, rescaled so the classes add up to $1$. Trained by maximum likelihood, a share is the fraction of training points in the class, and a feature rate is the fraction of that class's points that show the feature.
The likelihood splits along the graph
By the factorization, $L(\theta,\pi)=\prod_ip(y_i\mid\pi)\prod_jp(x_{ij}\mid y_i,\theta_j)$, so $l=\sum_cn_c\log\pi_c+\sum_{i,j,c}I(y_i=c)\log p(x_{ij}\mid y_i=c,\theta_{jc})$: one sum for the shares and one term per feature and class.
Shares: maximize $\sum_cn_c\log\pi_c$ subject to $\sum_c\pi_c=1$. The Lagrange condition $n_c/\pi_c=\lambda$ gives $\pi_c=n_c/\lambda$, and adding over $c$ gives $\lambda=n$.
Bernoulli rates: the $\theta_{jc}$ term is $n_{jc}\log\theta_{jc}+(n_c-n_{jc})\log(1-\theta_{jc})$. Its derivative vanishes at $\hat\theta_{jc}=n_{jc}/n_c$.
Gaussian features split the same way, class by class: $\hat\mu_{jc}$ is the class mean of feature $j$, and $\hat\sigma^2_{jc}$ its average squared deviation, divided by $n_c$.
The graph of naive Bayes: $\textcolor{#1f6feb}{y}$ is the only parent of each observed feature $\textcolor{#d1690a}{x_j}$, and the $\textcolor{#8250df}{\text{missing edges}}$ between features are the naive assumption. So $p(x,y)=p(y)\prod_jp(x_j\mid y)$.
Looks like this, but is not
Naive Bayes assumes that the features are independent of each other.
It assumes independence given $y$. Without $y$ the star is tail-to-tail at $y$, so the features are dependent: in the trained e-mail model 'prize' and 'outside sender' each appear in $40$ e-mails out of $100$, but together in about $24$, not $16$.
Training on ten e-mails: maximum likelihood is counting
Ten labelled e-mails are described by three binary features. Fit a Bernoulli naive Bayes classifier by maximum likelihood.
Find$\hat\pi_c$ and $\hat\theta_{jc}$ for $c=1,2$ and $j=1,2,3$.
Given
features: $x_1$ = the word 'prize' appears, $x_2$ = a link, $x_3$ = sender outside the university
Moving any estimate away from its count ratio lowers the log-likelihood: at the estimates it is $-23.04$, and with $\theta_{11}=0.5$ instead of $0.75$ it drops to $-23.57$.
Training naive Bayes is one pass of counting; the Lagrange multiplier in the proof only explains why the shares divide by $n$.
Classifying two new e-mails with the trained model
With the estimates of the previous example, find $p(y=1\mid x)$ for $x=(1,0,1)$ and for $x=(0,1,0)$.
FindThe two posteriors of spam.
Given
$\hat\pi=(0.4,\ 0.6)$
$\hat\theta_{\cdot1}=(0.75,\ 0.75,\ 0.75)$
$\hat\theta_{\cdot2}=(1/6,\ 1/2,\ 1/6)$
Solution
Score each class with $\hat\pi_c\prod_j$ ($\hat\theta_{jc}$ or $1-\hat\theta_{jc}$), then divide by the sum of the scores; this is Bayes' rule with the factored likelihood.
Log-odds route for the first e-mail: $\log\frac{0.05625}{0.00833}=\log6.75=1.910$, and $1/(1+e^{-1.910})=0.871$.
Absent features vote too, through $1-\hat\theta_{jc}$; dropping them changes the answer.
Gaussian naive Bayes: temperature says healthy, vibration says worn
Four healthy motors had (temperature, vibration) readings $(40,2)$, $(42,3)$, $(44,3)$, $(46,4)$; four worn ones had $(48,5)$, $(50,6)$, $(52,7)$, $(54,6)$, in degrees Celsius and mm/s. Fit a Gaussian naive Bayes model with equal shares and classify a motor at $(46,5)$.
Estimate a mean and a variance per class and feature, then compare log-densities: equal shares cancel, and logs turn the product into a sum of per-feature votes.
Conditional independence makes the votes add in the log-odds.
Answer $$\boxed{p(\text{worn}\mid x)=0.802}$$
Check
Direct densities: healthy $0.07254\times0.01033=0.000750$, worn $0.01464\times0.2076=0.00304$, and $0.00304/(0.00304+0.00075)=0.802$.
Each Gaussian feature votes with the difference of squared distances divided by twice its variance, so a precise feature outvotes a vague one.
Checkpoint
§12.4 — one Bernoulli rate from counts
A mail filter is trained on $40$ e-mails. $10$ of them are spam, and $8$ of those spam e-mails contain a link; $6$ of the $30$ other e-mails contain a link too.
Find(a) What is the maximum likelihood estimate of $\theta_{\text{link},1}=p(\text{link}\mid\text{spam})$?
Given
$n=40$; spam $n_1=10$, not spam $n_2=30$
link in spam: $8$; link in not spam: $6$
Hint 1/4
Decide which e-mails the rate is a fraction of.
Hint 2/4
$\hat\theta_{jc}=n_{jc}/n_c$.
Hint 3/4
$n_{jc}=8$ spam e-mails with a link, out of $n_c=10$ spam e-mails.
Hint 4/4
$\hat\theta=8/10=0.8$.
Show solution
The rate is counted inside the class, so only the $10$ spam e-mails matter.
12.5The Markov blanket: parents, children and co-parents
Parents, children and co-parents: once they are known, the rest of a directed graph tells a node nothing more.
D-separation answers questions about any sets; one question comes up so often that it has its own answer: which nodes make the rest of the graph irrelevant to one node?
TheoremThe Markov blanket in a directed graph
Conditions
the joint factorizes as $\prod_kp(x_k\mid\mathrm{pa}_k)$
the co-parents of $x_i$ are the other parents of $x_i$'s children
To predict one node from all the others, keep only its own factor and the factors of its children; every other factor cancels. Those factors mention the parents, the children and the children's other parents, so this set, the blanket, is all we need to know.
Cancel every factor that does not contain the node
Write $p(x_i\mid x_{j\ne i})=p(x)\big/\sum_{x_i}p(x)$ and substitute the factorization on top and below.
A factor $p(x_k\mid\mathrm{pa}_k)$ with $x_i$ neither equal to $x_k$ nor in $\mathrm{pa}_k$ does not change with $x_i$: it comes out of the sum below and cancels with its copy on top.
What survives is $p(x_i\mid\mathrm{pa}_i)$ and one factor for each child $x_k$; a child's factor also contains the child's other parents. Those variables form the blanket.
The blanket of $\textcolor{#1f6feb}{x_3}$ in graph $G$: parents $x_1$, $x_6$, child $x_4$ and co-parent $x_2$, all $\textcolor{#8250df}{\text{purple}}$. The grandchild $x_5$ is outside, though it lies below $x_3$.
Looks like this, but is not
The Markov blanket of a node is the set of nodes joined to it by an arrow.
Co-parents have no arrow to the node, yet they matter: in $L\to F\leftarrow R$, once $F$ is known, learning $R$ moves the belief in $L$ from $0.597$ to $0.174$. The blanket of $L$ is $\{W,F,R\}$, not $\{W,F\}$.
The battery given everything else: which factors survive
In the sensor model, find $p(L=1\mid W=1,R=0,F=1,S)$ for $S=1$ and for $S=0$.
FindThe two conditionals.
Given
$W\to L\to F\leftarrow R$, $F\to S$
$p(L=1\mid W=1)=0.15$; $p(F=1\mid L,R=0)=0.9$ if $L=1$ and $0.02$ if $L=0$
$p(S=1\mid F=1)=0.95$
Solution
Use the blanket formula: only the factors that contain $L$ survive, so the tables of $W$, $R$ and $S$ are never needed.
Factors that contain L
$$p(L\mid W)\ \text{and}\ p(F\mid L,R)$$
$L$'s own factor and the factor of its only child $F$.
$$p(L=1\mid\cdot)=\frac{0.135}{0.135+0.017}=0.888\ \ \text{for }S=1\text{ and for }S=0$$
$p(S\mid F)$ has no $L$ in it, so it cancels; the value of $S$ cannot matter.
Answer $$\boxed{\begin{aligned}&p(L=1\mid\text{the rest})=0.888\\ &\text{for }S=0\text{ and for }S=1\end{aligned}}$$
Check
Keep $S$ in: with $S=1$, $\frac{0.15(0.9)(0.95)}{0.15(0.9)(0.95)+0.85(0.02)(0.95)}=0.12825/0.1444=0.888$; the factor $0.95$ cancels, as the blanket says.
$S$ lies below $L$, but once $F$ is known it has nothing left to say about $L$.
Three blankets in graph G
Find the Markov blankets of $x_3$, $x_4$ and $x_1$ in graph $G$.
The probability of a configuration is proportional to a product of non-negative scores, one per maximal clique, and $Z$ rescales the products into probabilities; with $\psi_c=e^{-E(x_c)}$ this is a Boltzmann distribution. Independence is plain separation: observed nodes cut every path through them, so a node given its neighbours is independent of the rest.
Separation from the factorization, and the cost of Z
If $x_i$ and $x_j$ are not neighbours, no clique contains both, so each potential holds at most one of them. Given all other nodes, $p(x)$ splits into a factor with $x_i$ times a factor with $x_j$, and $p(x_i,x_j\mid\text{rest})=p(x_i\mid\text{rest})\,p(x_j\mid\text{rest})$.
The potentials that contain $x_i$ contain only $x_i$ and its neighbours, so given the neighbours all other factors cancel from $p(x_i\mid\text{rest})$: the blanket is the neighbours.
A potential on a smaller clique can be multiplied into any maximal clique that contains it without changing $p(x)$; that is why maximal cliques are enough.
For $D$ binary nodes, $Z$ has $2^D$ terms: $64$ for six nodes, about $10^{3010}$ for a $100\times100$ binary image.
Graph $H$ with its $\textcolor{#8250df}{\text{three maximal cliques}}$ shaded: two triangles and the edge $x_5x_6$. The joint is $\frac1Z\,\psi_{123}\,\psi_{345}\,\psi_{56}$; $x_3$ and $x_5$ sit in two cliques each.
Looks like this, but is not
A maximal clique is a clique of the largest size in the graph.
Maximal means no node can be added, not biggest. In $H$, $\{x_5,x_6\}$ is maximal: adding $x_3$ or $x_4$ breaks full connection. It has two nodes while the triangles have three.
x1 x2 x3
product
probability
$000$, $111$
$3\cdot3=9$
$9/32$ each
$001$, $110$
$3\cdot1=3$
$3/32$ each
$011$, $100$
$1\cdot3=3$
$3/32$ each
$010$, $101$
$1\cdot1=1$
$1/32$ each
Rows are grouped by how many neighbour pairs agree: two, one, one, none. The products add up to $Z=32$, and a configuration where both pairs agree is $9$ times as probable as one where neither does.
Cliques, blanket and factorization of a bow-tie graph
The undirected graph $H$ has the edges $x_1x_2$, $x_1x_3$, $x_2x_3$, $x_3x_4$, $x_3x_5$, $x_4x_5$ and $x_5x_6$. List its cliques and maximal cliques, write the factorization, give the Markov blanket of $x_3$, and decide whether $x_1\perp\!\!\!\perp x_6\mid x_3$.
FindCliques, maximal cliques, $p(x)$, $\mathrm{MB}(x_3)$ and one independence verdict.
Count check on the maximal cliques: every edge must lie in at least one of them, and the triangles hold $3+3=6$ edges plus the edge $x_5x_6$, all $7$.
In an undirected graph, independence is plain separation: remove the observed nodes and see whether the two sets are still connected.
Normalizing a three-node chain, and checking separation with numbers
Three binary nodes form the chain $x_1 - x_2 - x_3$. Both potentials give $3$ to agreeing neighbours and $1$ to disagreeing ones. Find $Z$, $p(1,1,1)$, and check $x_1\perp\!\!\!\perp x_3\mid x_2$ numerically.
Find$Z$, $p(1,1,1)$, and the separation check at $x_2=1$.
Given
$\psi_{12}(a,b)=\psi_{23}(a,b)=3$ if $a=b$, $1$ if $a\ne b$
$x_1,x_2,x_3\in\{0,1\}$
Solution
With only $8$ configurations we list them all; the products fall into four groups by how many neighbours agree.
right$$\mathrm{MB}(x_2)=\{x_1,x_3\}\ \text{in }H\text{: its neighbours}$$
12.7Image denoising: lower the energy one pixel at a time
An undirected grid cleans a noisy black-and-white image: lower the energy one pixel at a time until a full sweep changes nothing.
Neighbouring pixels of an image are the natural undirected graph, and a potential that rewards agreement turns 'clean images are smooth' into a probability.
MethodThe denoising and the coordinate-wise update
Conditions
$y_i\in\{-1,+1\}$: pixel $i$ of the noisy image, observed; $x_i\in\{-1,+1\}$: pixel $i$ of the clean image, unknown
$i\sim j$ runs over neighbouring pairs (up, down, left, right), each pair once
$\beta>0$ rewards agreeing neighbours, $\eta>0$ rewards agreeing with the reading, $h$ biases toward one colour
$a_j$ is the vote of pixel $j$; if $a_j=0$ the pixel keeps its value
The energy is low when neighbouring pixels agree and when each pixel agrees with its reading, so the most probable clean image has the lowest energy. One pixel at a time takes the value with the lower energy; the energy never rises, and a sweep with no change marks a local maximum of the probability.
Only one pixel's terms change, so the rule is a sign
The maximal cliques are the neighbour pairs $\{x_i,x_j\}$ and the pairs $\{x_i,y_i\}$; the energy has one term per clique, and the bias $hx_i$ can be merged into the pair with $y_i$.
Collect the terms with $x_j$: $E=x_j\big(h-\beta\sum_{k\sim j}x_k-\eta y_j\big)+\text{(rest)}$. So $E(x_j=+1)-E(x_j=-1)=2\big(h-\beta\sum_kx_k-\eta y_j\big)$, negative exactly when the vote $\beta\sum_kx_k+\eta y_j-h$ is positive.
Each update keeps or lowers $E$, and $E$ takes finitely many values, so the sweeps stop. The final image cannot be improved by changing one pixel, but a better image that needs several changes at once may exist.
This is the lecture's coordinate-wise descent on the energy; many books call it .
Each unknown clean pixel $x_i$ is linked to its four neighbours and to its own $\textcolor{#d1690a}{\text{noisy reading }y_i}$. The two kinds of clique give the two sums of the energy: $\textcolor{#8250df}{-\beta\sum x_ix_j}$ and $\textcolor{#8250df}{-\eta\sum x_iy_i}$.
Looks like this, but is not
Every pixel ends up with the colour of the majority of its neighbours.
The reading votes too, with weight $\eta$. With $\beta=1$ and $\eta=1.5$, an edge pixel with two white neighbours and one black keeps its black reading: $1\cdot(2-1)+1.5\cdot(-1)=-0.5<0$.
Which of two 2 by 2 images is more probable?
A noisy $2\times2$ image has three white pixels and a black one in the bottom right: $y=\begin{smallmatrix}+1&+1\\+1&-1\end{smallmatrix}$. With $\beta=1$, $\eta=1.5$, $h=0$, compare the energy of $x=y$ with that of the all-white $x$, and say how much more probable the better one is.
Find$E(x,y)$ for both candidates and the ratio of their probabilities.
Given
$y$: rows $(+1,+1)$ and $(+1,-1)$
$\beta=1$, $\eta=1.5$, $h=0$
neighbour pairs: the two rows and the two columns, $4$ pairs
Solution
Evaluate the two sums of the energy separately, neighbour pairs and pixel-reading pairs, because each candidate wins one of them.
Pixel rule for the corner: its two neighbours say $+1$ with weight $\beta\cdot2=2$, its reading says $-1$ with weight $1.5$; $2-1.5>0$, so white wins, as the energies say.
A lone pixel that disagrees with its neighbours is cheaper to flip than to keep, once $\beta\times(\text{agreeing neighbours})$ exceeds $\eta$.
A full sweep on a 4 by 4 image
The noisy image $y$ below should be two black columns and two white ones, but two pixels were flipped. Starting from $x=y$, run coordinate-wise updates with $\beta=1$, $\eta=1.5$, $h=0$, row by row, until a sweep changes nothing. Track the energy.
FindThe final image, the pixels that changed, and the energies.
update: $x_j=+1$ if $\beta\sum_{k\sim j}x_k+\eta y_j>0$, $-1$ if $<0$
Solution
Only pixels whose neighbours disagree with them can change, so we check those first; the others keep their value because $\beta\sum x_k$ and $\eta y_j$ point the same way.
Start
$$E(y,y)=-\beta(6)-\eta(16)=-6-24=-30$$
Of the $24$ neighbour pairs, $15$ agree and $9$ disagree, so $\sum x_ix_j=6$; every pixel matches its reading, so $\sum x_iy_i=16$.
Direct energy of the final image: $20$ neighbour pairs agree and $4$ disagree across the middle, so $\sum x_ix_j=16$; $14$ pixels match their readings and $2$ do not, so $\sum x_iy_i=12$; $E=-16-1.5(12)=-34$.
$16$ pixel checks per sweep, two sweeps.
Coordinate-wise updates fix isolated flips in one sweep; a second sweep is needed only to confirm that nothing else moves.
Checkpoint
§12.7 — one pixel's update
In the denoising model with $\beta=1$, $\eta=1.5$ and $h=0$, an interior pixel currently equals its black reading, $x_j=y_j=-1$. Its four neighbours are white, white, white and black.
Find(a) What does one coordinate-wise update do to this pixel, and to the energy?
Given
neighbours $+1,\ +1,\ +1,\ -1$
$x_j=y_j=-1$
$\beta=1$, $\eta=1.5$, $h=0$
Hint 1/4
Compare the energy with $x_j=+1$ and with $x_j=-1$, everything else fixed.
Hint 2/4
$x_j=+1$ exactly when $\beta\sum_{k\sim j}x_k+\eta y_j-h>0$.
Hint 3/4
$\sum_kx_k=+1+1+1-1=2$ and $\eta y_j=1.5\times(-1)$, so the vote is $2-1.5$.
Hint 4/4
The vote is $0.5>0$: the pixel turns white and $E$ drops by $1$.
Show solution
Use the pixel rule instead of recomputing the whole energy: only the terms with $x_j$ change.
Step through coordinate-wise denoising of a $5\times5$ image with $\beta=1$, $\eta=1.5$, $h=0$. Dots on the $\textcolor{#d1690a}{\text{observed }y}$ mark the four pixels flipped by noise; the $\textcolor{#8250df}{\text{outlined}}$ pixel is the one just updated, and each frame prints the energy.
At the edges
sweep 1, pixel (2, 3) a wrong move
Two noisy neighbours outvote the pixel's correct white reading, so it turns black. Sweep 2 undoes it once the neighbours are fixed: a greedy step can go wrong and still end well.
sweep 3 no change
The energy is $-55.5$, the energy of the clean image; here the local minimum is the clean image, which is not guaranteed in general.
Deciding A independent of B given C in a directed graph
A question gives a directed graph and asks whether $A\perp\!\!\!\perp B\mid C$.
List the paths
Every chain of edges from a node of $A$ to a node of $B$, walked either way, never visiting a node twice.
Classify the nodes
At each interior node, the two arrows of the path meet head-to-tail, tail-to-tail or head-to-head.
Mark blocked paths
Blocked if some node is head-to-tail or tail-to-tail and in $C$, or head-to-head with neither it nor a descendant in $C$.
Conclude
All paths blocked: $A\perp\!\!\!\perp B\mid C$. One open path: dependent in general.
Where it goes wrong
Stopping after the first blocked path.
Checking the head-to-head node but not its descendants.
Treating an unobserved head-to-head node as open.
A posterior by enumeration in a small network
A few binary nodes with tables, some observed, and one query such as $p(L=1\mid F=1)$.
Factor
Write the joint as the product of parent conditionals.
Fix the evidence
Put the observed values into every factor.
Sum out
For each value of the query, add the product over the unobserved variables; a factor without a summed variable moves outside that sum.
Normalize
Divide each result by their total.
Where it goes wrong
Summing over an observed variable instead of fixing it.
Dropping a prior factor, such as $p(R)$, from some terms but not from others.
Stopping before the division, which leaves the joint $p(\text{query},\text{evidence})$.
Training and using Bernoulli naive Bayes
Binary features, labelled training rows, and a new row to classify.
Count
$n_c$ per class and $n_{jc}$ per feature inside each class.
Estimate
$\hat\pi_c=n_c/n$ and $\hat\theta_{jc}=n_{jc}/n_c$.
Score
$\hat\pi_c$ times, for each feature, $\hat\theta_{jc}$ if $x_j=1$ and $1-\hat\theta_{jc}$ if $x_j=0$.
Normalize and decide
Divide the scores by their sum and predict the largest.
Where it goes wrong
Dividing $n_{jc}$ by $n$.
Leaving out the factors of absent features.
A zero count makes $\hat\theta_{jc}$ exactly $0$ or $1$ and can force a posterior of $0$.
Coordinate-wise denoising by hand
A small $\pm1$ image, the weights $\beta$, $\eta$, $h$, and a request to clean it.
Start
Set $x=y$.
Vote
For pixel $j$, compute $\beta\sum_{k\sim j}x_k+\eta y_j-h$ with the current neighbours.
Set
$x_j=+1$ if the vote is positive, $-1$ if negative, unchanged at $0$; use the new value at once.
Sweep and stop
Visit every pixel in order; stop after a sweep with no change.
Where it goes wrong
Using the old neighbour values for a whole sweep.
Moving toward the higher energy.
Leaving out the reading $y_j$.
Chain: the observed middle node silences the far end
In $W\to L\to F$ (sensor tables), compare $p(F=1\mid L=1,W=1)$ with $p(F=1\mid L=1,W=0)$.
FindThe two conditionals.
Given$p(F=1\mid L=1)=0.9(0.9)+0.1(0.95)=0.905$ after summing out $R$
The four probabilities $3/8, \allowbreak 1/8, \allowbreak 1/8, \allowbreak 3/8$ add to $1$.
Undirected potentials are normalized once, globally, by $Z$.
A directed factor is already a probability; an undirected potential is a score until the whole product is divided by $Z$.
How to tell them apart
Arrows: multiply the conditionals. No arrows: multiply the potentials, then divide by their sum over every configuration.
Scaffolding comes off
The common skeleton
Count $n_c$ for each class and $n_{jc}$ for each feature inside each class.
Estimate $\hat\pi_c=n_c/n$ and $\hat\theta_{jc}=n_{jc}/n_c$.
Score each class: $\hat\pi_c$ times $\hat\theta_{jc}$ for every $x_j=1$ and $1-\hat\theta_{jc}$ for every $x_j=0$.
Divide the scores by their sum and predict the largest.
1 · fully worked
Two alarms, eight checks: train, then classify one machine
Eight past checks recorded two alarms, $x_1$ (over-temperature) and $x_2$ (over-current), and the finding $y=1$ (fault) or $y=2$ (no fault). Fault: $(1,1)$, $(1,0)$, $(0,1)$. No fault: $(0,0)$, $(1,0)$, $(0,0)$, $(0,1)$, $(0,0)$. Classify a machine with $x=(1,0)$.
Find$p(y=1\mid x)$ and the decision.
Given
fault, $y=1$: $(1,1)$, $(1,0)$, $(0,1)$
no fault, $y=2$: $(0,0)$, $(1,0)$, $(0,0)$, $(0,1)$, $(0,0)$
new machine $x=(1,0)$
Solution
Count, estimate, score, normalize: the four lines of the method box, in order.
The over-temperature alarm points to a fault, but the silent over-current alarm and the larger share of healthy machines point the other way.
Answer $$\boxed{\begin{aligned}&p(\text{fault}\mid x)=\tfrac{5}{11}\approx0.455\\ &\text{predict no fault}\end{aligned}}$$
Check
Log-odds route: $\log(3/5)+\log\frac{2/3}{1/5}+\log\frac{1/3}{4/5}=-0.511+1.204-0.875=-0.182$, and $1/(1+e^{0.182})=0.455=5/11$.
One feature pointing to a class is not enough; the prior and the absent features vote as well.
2 · you write the reasoning
Easier: the estimates are given, so only scoring is left. Two classes with $\hat\pi=(0.5,0.5)$, $\hat\theta_{\cdot1}=(0.8,\ 0.3)$, $\hat\theta_{\cdot2}=(0.2,\ 0.6)$, and a new point $x=(1,1)$. For each line, write why it is allowed.
$$\text{score}_1=0.5\times0.8\times0.3=0.12$$
reasoning
Class 1: its share times $\hat\theta_{11}$ for $x_1=1$ times $\hat\theta_{21}$ for $x_2=1$.
$$\text{score}_2=0.5\times0.2\times0.6=0.06$$
reasoning
The same product with the class 2 estimates.
$$p(y=1\mid x)=\frac{0.12}{0.12+0.06}=\frac23$$
reasoning
The scores are proportional to the posteriors, so dividing by their sum gives probabilities.
$$\hat c=1$$
reasoning
The larger posterior wins; equal shares mean only the feature rates decided.
3 · find the buried error
Harder, and the solution below hides two errors. Twelve past checks with three alarms: fault ($y=1$): $(1,1,0)$, $(1,1,0)$, $(1,0,1)$, $(1,1,0)$, $(0,0,0)$; no fault ($y=2$): $(0,0,1)$, $(0,1,1)$, $(1,0,1)$, $(0,0,1)$, $(0,1,0)$, $(0,0,1)$, $(0,0,0)$. A student classifies $x=(1,1,0)$.
The rate of the second alarm in class 1 is divided by all $12$ checks: $\hat\theta_{21}=3/12$. Three of the $5$ fault rows have $x_2=1$, so $\hat\theta_{21}=3/5$.
$n$ is the number printed at the top of the data, and the class shares in step 1 did divide by it.
right
$\hat\theta_{\cdot1}=(4/5,\ 3/5,\ 1/5)$.
⚠ step 4
For $x_3=0$ both scores multiply by $\hat\theta_{3c}$ instead of $1-\hat\theta_{3c}$: $1/5$ and $5/7$ should be $4/5$ and $2/7$.
Writing the product as $\prod_j\hat\theta_{jc}$ for every feature is the habit from features that are all $1$.
right
Scores $\tfrac5{12}\cdot\tfrac45\cdot\tfrac35\cdot\tfrac45=0.16$ and $\tfrac7{12}\cdot\tfrac17\cdot\tfrac27\cdot\tfrac27=0.0068$, so $p(y=1\mid x)=0.959$ and the decision flips to class 1.
4 · the bare problem
§12.4 — naive Bayes from data to decision
A pipe monitor logs three binary signals: $x_1$ humidity alarm, $x_2$ pressure drop, $x_3$ night-time reading. Ten past readings were labelled leak ($y=1$) or no leak ($y=2$).
Find
(a) Estimate $\hat\pi_c$ and $\hat\theta_{jc}$ by maximum likelihood.
A close call; the pressure drop alone is not enough against the silent humidity alarm and the larger no-leak share.
Answer $$\boxed{\begin{aligned}&p(\text{leak}\mid x)=\tfrac{9}{19}\approx0.474\\ &\text{predict no leak}\end{aligned}}$$
Check
Log-odds check: $\log\frac{0.4}{0.6}+\log\frac{1/4}{5/6}+\log\frac{3/4}{1/6}+\log1=-0.405-1.204+1.504=-0.105$, and $1/(1+e^{0.105})=0.474$.
A feature with the same rate in every class cancels from the decision; check for it before multiplying.
Full exam-style question
A server room: factorization, independence, blanket and explaining awayexam format
A server can lose power ($P=1$) because of a grid outage ($G=1$) or a worn UPS battery ($U=1$). A power loss can cause a disk error ($K=1$) and triggers a monitoring alert ($M=1$). The graph is $G\to P\leftarrow U$, $P\to K$, $P\to M$.
(a) Write the joint and count its free numbers against a full table.
Structure first, numbers last: (a) to (c) need only the graph, and (d) and (e) need only the four cells of $p(G)p(U)p(P=1\mid G,U)$, because $K$ and $M$ sum to $1$ when unobserved.
The cells $p(G)p(U)p(P=1\mid G,U)$ are $0.9(0.9)(0.001)$, $0.9(0.1)(0.3)$, $0.1(0.9)(0.05)$ and $0.1(0.1)(0.95)$; $K$ and $M$ are summed out and vanish.
Only the cells with $U=0$ remain; $p(U=0)$ cancels. Ruling out one cause makes the other the explanation.
Answer $$\boxed{\begin{aligned}&\text{(a) }10\text{ vs }31\\ &\text{(b) }G\perp\!\!\!\perp U;\ \text{not given }M;\\ &\qquad K\perp\!\!\!\perp M\mid P\\ &\text{(c) }\{P,G\}\\ &\text{(d) }0.335\qquad\text{(e) }0.847\end{aligned}}$$
Check
(e) the other way: with $U=1$ the outage becomes less likely, $0.1(0.95)/(0.1(0.95)+0.9(0.3))=0.260$. The answer to (d), $0.335$, lies between $0.260$ and $0.847$ because it is their average weighted by $p(U\mid P=1)$.
Four products for (d), two for (e).
In an exam, settle the graph questions before any arithmetic: they decide which factors the numbers even need.
Practice
A · concept 4 questions
1§12.4 — what naive Bayes really assumes
A classmate's summary sheet says: 'Naive Bayes assumes that the features are independent of each other.'
Find(a) Is the statement true or false?
Given
naive Bayes graph: $y\to x_j$ for every $j$, no edges between features
e-mail model: $\hat\pi=(0.4,\ 0.6)$; $\hat\theta_{1c}=\hat\theta_{3c}=(3/4,\ 1/6)$ for $c=1,2$
Hint 1/4
Separate two claims: independence once the label is known, and independence with the label unknown.
Hint 2/4
Tail-to-tail at $y$: $x_j\perp\!\!\!\perp x_k\mid y$, but dependent in general without $y$.
Hint 3/4
In the e-mail model $p(x_1=1)=p(x_3=1)=0.4(0.75)+0.6(1/6)=0.4$ and $p(x_1=1,x_3=1)=0.4(0.75)^2+0.6(1/6)^2=0.242$.
Hint 4/4
$0.242\ne0.4\times0.4=0.16$, so the statement is false.
Show solution
One pair of values that breaks the product settles it, so we compute a single cell.
Given $y$ the features multiply; then sum over $y$.
Compare
$$0.2417\ne0.4^2=0.16$$
A mixture of products is not a product.
Answer $$\boxed{\text{False}}$$
Check
Given $y=1$ the product does hold: $0.75\times0.75=0.5625=p(x_1=1,x_3=1\mid y=1)$.
'Naive' is about the features given the class, never about the features alone.
2§12.2 — can observing a node create dependence?
In the sensor model the battery $L$ and the interference $R$ are independent before anything is observed. A student claims that observing a third variable can never make two independent variables dependent.
Find(a) Is the student's claim true or false?
Given
$W\to L\to F\leftarrow R$, $F\to S$
$p(W=1)=0.5$, $p(R=1)=0.1$; $p(L=1\mid W)=0.15$ if $W=1$, $0.05$ if $W=0$
Multiplying every potential by $10$ multiplies $Z$ by $100$ and leaves every probability unchanged, so the scale of a table carries no meaning.
Directed factors are normalized locally; undirected potentials only globally, through $Z$.
B · computation 8 questions
1§12.1 — counting the numbers of a greenhouse model
A greenhouse model has a three-valued season, which affects rain and whether the pump runs; rain and the pump decide whether the soil is moist, and the soil decides whether the plants show stress.
Find
(a) Write the factorization.
(b) Count the free numbers, and compare with a full table.
Plausibility: every draw took a common branch (mild $0.5$, no rain $0.7$, moist soil $0.8$, no stress $0.95$) except the pump's even split, so a fairly large probability for a five-variable day is expected.
A sample never needs the joint table, only the right row of each factor.
3§12.2 — a flat cake: explaining away in numbers
A cake does not rise ($N=1$). Two independent causes are possible: old yeast ($Y=1$) and a cold oven ($O=1$).
Find
(a) Find $p(Y=1\mid N=1)$.
(b) Find $p(Y=1\mid N=1,O=1)$ and $p(Y=1\mid N=1,O=0)$.
The colliders are $x_3$ on the first path and $x_4$ on the second; the other nodes, $x_1$ and $x_3$ respectively, are unobserved and not head-to-head, so they pass.
An exact check with random tables for $G$ confirms all three: the first two joint tables factor, the third does not.
One observed descendant can open several colliders at once.
5§12.5 — the packet given its blanket
In the sensor model the technician knows it was a sunny day ($W=0$), the battery was fine ($L=0$), there was interference ($R=1$), and no SMS arrived ($S=0$).
Find
(a) Find $p(F=1\mid W=0,L=0,R=1,S=0)$.
(b) Would the answer change on a cloudy day?
Given
$W\to L\to F\leftarrow R$, $F\to S$
$p(W=1)=0.5$, $p(R=1)=0.1$; $p(L=1\mid W)=0.15$ if $W=1$, $0.05$ if $W=0$
Answer $$\boxed{\begin{aligned}&p(F=1\mid\cdot)=0.048\\ &\text{unchanged by }W\end{aligned}}$$
Check
Contrast: had the SMS arrived, $p(F=1\mid L=0,R=1,S=1)=0.475/0.48=0.990$.
A missing alert is strong evidence that the packet arrived, even on an interference night.
6§12.4 — the Lagrange multiplier behind the class shares
Twenty drone flights are labelled with one of three modes: $10$ survey, $6$ delivery, $4$ test. A GPS dropout occurred in $1$, $3$ and $3$ flights of these modes.
Find
(a) Maximize $\sum_cn_c\log\pi_c$ subject to $\sum_c\pi_c=1$ with a Lagrange multiplier.
(b) Give $\hat\pi$ and $\hat\theta_{1c}$ for the dropout feature.
Given
$n=20$; $n_1=10$, $n_2=6$, $n_3=4$
flights with a dropout: $n_{11}=1$, $n_{12}=3$, $n_{13}=3$
Hint 1/4
Only the class-share part of the log-likelihood depends on $\pi$; handle the constraint with a multiplier.
Hint 2/4
Set $\partial/\partial\pi_c$ of $\sum_cn_c\log\pi_c-\lambda(\sum_c\pi_c-1)$ to zero: $n_c/\pi_c=\lambda$.
Hint 3/4
$\pi_c=n_c/\lambda$ and $\sum_c\pi_c=1$ give $\lambda=n=20$; the counts are $10,6,4$ and $1,3,3$.
Hint 4/4
$\hat\pi=(0.5,\ 0.3,\ 0.2)$ and $\hat\theta_{1c}=(0.1,\ 0.5,\ 0.75)$.
Show solution
The constraint couples the shares, so they need a multiplier; each rate has no constraint and just a derivative.
At $x=14$ the densities are $\mathcal N(14\mid10,4)=0.0270$ and $\mathcal N(14\mid16,1)=0.0540$, a ratio of exactly $1:2$.
Equal distance from two means does not mean a tie: the narrower class falls off faster.
8§12.6 — Z for a square of four binary nodes
Four binary nodes sit on a square $x_1-x_2-x_3-x_4-x_1$. Each of the four edge potentials gives $2$ to agreeing neighbours and $1$ to disagreeing ones.
Find
(a) Find $Z$ and $p(1,1,1,1)$.
(b) Check $x_1\perp\!\!\!\perp x_3\mid\{x_2,x_4\}$ at $x_2=x_4=1$ with numbers.
Given
$\psi(a,b)=2$ if $a=b$, $1$ if $a\ne b$, on each of the four edges
$x_j\in\{0,1\}$
Hint 1/4
Group the $16$ configurations by how many of the four edges disagree.
Hint 2/4
$Z=\sum_x\prod_{\text{edges}}\psi$; a configuration with $k$ disagreeing edges scores $2^{4-k}$.
Hint 3/4
Around a square the value changes an even number of times: $2$ configurations have $k=0$, $12$ have $k=2$, and $2$ have $k=4$.
Hint 4/4
$Z=2(16)+12(4)+2(1)=82$; $p(1,1,1,1)=16/82$; given $x_2=x_4=1$, $p(x_1=1,x_3=1)=16/25=(4/5)^2$.
Show solution
Going around a square, the colour changes an even number of times, so only $k=0,2,4$ disagreements occur.
Z
$$Z=2\cdot2^4+12\cdot2^2+2\cdot2^0=32+48+2=82$$
$2$ constant colourings, $2$ alternating ones, and the other $12$ have two disagreeing edges.
Condition on $(x_2,x_4)$: equal values give $(4+1)(4+1)=25$, unequal give $(2+2)(2+2)=16$, so $Z=2(25)+2(16)=82$.
Separation in the graph shows up in the numbers as a sum that splits into a product.
C · exam level 5 questions
1§12.7 — the first sweep on a 3 by 3 image
A noisy $3\times3$ image is cleaned with $\beta=1$, $\eta=1.5$, $h=0$, starting from $x=y$ and sweeping row by row, left to right, with each new value used at once.
Find(a) Which pixels change during the first sweep?
Consequence check: $x_2$ and $x_4$ share no potential, and every path between them passes $x_1$ or $x_3$, so $x_2\perp\!\!\!\perp x_4\mid\{x_1,x_3\}$, as separation says.
The missing edge is what the factorization encodes: no potential ever holds both $x_2$ and $x_4$.
3§12.4 — a posterior where the prior matters
A bank's naive Bayes filter sorts card payments into routine ($y=1$) and suspicious ($y=2$) using two binary features: $x_1$ = paid abroad, $x_2$ = new device. The trained estimates are below.
The SMS is a noisy view of $F$, so both computations sum over $F$.
Hint 2/4
$p(L=1\mid e)=\sum_Fp(L=1, \allowbreak F, \allowbreak e)\big/\sum_{L,F}p(L, \allowbreak F, \allowbreak e)$, with every factor of the sensor model.
Hint 3/4
$p(L=1,S=1)=0.1\,(0.905\cdot0.95+0.095\cdot0.01)=0.0861$ and $p(S=1)=0.1526$; with $R=1$: $0.01(0.95\cdot0.95+0.05\cdot0.01)=0.00903$ against $0.09(0.5\cdot0.95+0.5\cdot0.01)=0.0432$.
Hint 4/4
$0.564$, then $0.173$.
Show solution
$S$ is a descendant of the collider $F$, so it behaves like a weaker observation of $F$; enumeration over $F$ handles it.
Both are a little below their $F$-observed versions, $0.597$ and $0.174$, because an SMS is slightly weaker evidence than a lost packet.
Observing a descendant of a collider opens it too, just less strongly.
5§12.3 — another true statement about graph G
Graph $G$ has the arrows $x_1\to x_2$, $x_1\to x_3$, $x_6\to x_3$, $x_2\to x_4$, $x_3\to x_4$ and $x_4\to x_5$. Exactly one statement below follows from d-separation.
The exact check on a model with random tables agrees with all four verdicts.
Observing a collider or its descendant is the usual way a 'false' statement fails.
D · interleaved 4 questions
1§12.1 — a hidden label behind one reading
A two-component Gaussian mixture has a hidden label $z$ and a reading $x$: first $z$ is drawn, then $x$ from the component $z$ picks. The components are $\mathcal N(0,1)$ and $\mathcal N(4,1)$ with shares $0.3$ and $0.7$.
Find
(a) Draw the graph, write $p(z,x)$, and draw one sample $(z,x)$.
At $x=1$ in (a), both densities equal $e^{-1/2}/\sqrt{2\pi}$, so the posterior is $0.5$, as a boundary requires.
With one shared variance, Gaussian naive Bayes and logistic regression have the same form; they differ in how the coefficients are fitted.
3§12.4 — an inside sender the spam class never showed
In a new sample, all $4$ spam e-mails came from outside the university, so $\hat\theta_{31}=1$. A new e-mail with 'prize' and a link comes from inside: $x=(1,1,0)$.
Find
(a) Find $p(\text{spam}\mid x)$ with maximum likelihood estimates.
(b) Replace every $\hat\theta_{jc}$ by its posterior mean under $\mathrm{Beta}(1,1)$ and recompute.
Log-odds route: $\log\frac{0.4}{0.6}+\log\frac{2/3}{1/4}+\log\frac{2/3}{1/2}+\log\frac{1/6}{3/4}=-0.405+0.981+0.288-1.504=-0.641$, and $1/(1+e^{0.641})=0.345$.
Pseudo-counts are the Beta prior at work: they keep a small sample from ruling anything out.
4§12.4 — are naive Bayes features redundant?
Feature selection by maximum relevance and minimum redundancy penalizes the mutual information between selected features. Take the trained e-mail model and the features $x_1$ ('prize') and $x_3$ (outside sender).
Find
(a) Find the joint table of $(x_1,x_3)$ under the model.
(b) Find $I(x_1;x_3)$.
(c) Since naive Bayes assumes conditional independence, is the redundancy term zero?
same variance in both classes; with different variances, divide each square by twice its own variance and add $\frac12\log(\sigma^2_{j1}/\sigma^2_{j2})$
$x_i,y_i\in\{-1,+1\}$; each neighbour pair once; stop after a sweep with no change
Check yourself
Close the page and write down from memory:
the factorization of a directed graph and how to count its numbers;
the three three-node graphs and what observing the middle node does in each;
the two blocking rules of d-separation;
the naive Bayes posterior and its two maximum likelihood estimates;
the directed and the undirected Markov blanket;
the undirected factorization with Z;
the denoising energy and the pixel update rule.
Then reopen the page and compare; whatever is missing is your reread list.
Write the joint of a given directed graph, count its free numbers, and draw one sample from given uniforms?
c-factorization
Say what observing the middle node does in each three-node graph, and compute an explaining-away posterior?
c-three-graphs
List every path between two sets and decide each by the two blocking rules?
c-d-separation
Train Bernoulli or Gaussian naive Bayes from a table and classify a new point?
c-naive-bayes
Name a node's Markov blanket and compute its conditional from the blanket's factors alone?
c-markov-blanket
List cliques and maximal cliques, write the factorization with Z, and normalize a tiny model?
c-mrf
Evaluate the denoising energy and run the pixel updates to a stop?
c-denoising
Glossary (26 terms)
olasılıksal grafik model
A joint distribution described by a graph whose nodes are random variables and whose missing links state conditional independences.
directed acyclic graphyönlü döngüsüz çizge
A graph with arrows in which no path that follows the arrows comes back to where it started.
Bayesian networkBayes ağı
A directed graphical model: a directed acyclic graph with one factor $p(x_j\mid\mathrm{pa}_j)$ per node.
parentebeveyn
A node with an arrow into $x_j$; the parents form $\mathrm{pa}_j$.
descendant
A child of a node, a child of that child, and so on down the arrows.
factorizationçarpanlara ayırma
Writing a joint distribution as a product of smaller factors dictated by a graph.
ancestral sampling
Drawing a sample from a directed model by sampling every node after its parents, from the row of its table that the parents' values pick.
conditional independencekoşullu bağımsızlık
$a\perp\!\!\!\perp b\mid c$: once $c$ is known, $a$ tells nothing more about $b$; $p(a,b\mid c)=p(a\mid c)p(b\mid c)$.
tail-to-tail
A node on a path with both arrows leaving it, as $c$ in $a\leftarrow c\rightarrow b$.
head-to-tail
A node on a path with one arrow in and one arrow out, as $c$ in $a\rightarrow c\rightarrow b$.
head-to-head
A node on a path where both arrows point in, as $c$ in $a\rightarrow c\leftarrow b$; often called a collider.
collider
A head-to-head node on a path; it blocks the path unless it or one of its descendants is observed.
explaining away
Two independent causes of an observed effect become dependent: confirming one cause makes the other less likely.
d-separation
$C$ d-separates $A$ from $B$ when every path between them is blocked by $C$; it implies $A\perp\!\!\!\perp B\mid C$.
Markov blanket
The smallest set of nodes that, once known, makes a node independent of all others: parents, children and co-parents in a directed graph, neighbours in an undirected one.
co-parent
Another parent of one of a node's children.
naive Bayes classifiernaif Bayes sınıflandırıcısı
A classifier that treats the features as independent once the class is known, and predicts the class with the largest posterior.
Markov random fieldMarkov rastgele alanı
An undirected graphical model: the joint is a product of potentials on the maximal cliques, divided by $Z$.
cliqueklik
A set of nodes in which every pair is joined by an edge; here, of at least two nodes.
maximal cliquemaksimal klik
A clique that no further node can join while staying fully connected.
potential functionpotansiyel fonksiyonu
A non-negative function of a clique's variables; it scores configurations but is not a probability.
partition functionbölüşüm fonksiyonu
The normalizing constant $Z$, the sum of the product of potentials over every configuration.
Boltzmann distributionBoltzmann dağılımı
A distribution of the form $e^{-E(x)}/Z$: lower energy, higher probability.
energy functionenerji fonksiyonu
The function $E$ with $\psi=e^{-E}$; a sum of one term per clique.
image denoisinggörüntü gürültü giderme
Recovering a clean image from a noisy one, here as the most probable image under an undirected grid model.
iterated conditional modes
The common name of the lecture's coordinate-wise descent: set one variable at a time to its best value given the others.
What comes next
§13 · Restricted Boltzmann machines and deep learning
Here every potential was given, and every unknown was either summed out or set one pixel at a time. Next, an undirected graph gets a layer of hidden units, and its potentials are learned from data.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides and lecture notes, chapter 12: Probabilistic graphical models Scope, order of topics and notation (pa_j, the three-node graphs, the sets A, B, C, x_j, y, C, pi_c, theta_jc, n_c, n_jc, I, M, x_c, psi_c, Z, E, x_i, y_i) follow these materials; all explanations, data, figures and exercises here are original.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights, the weekly topic list and the recommended books.
textbookD. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques, MIT Press, 2009 Recommended in the syllabus; the lecture's overview figure comes from it.
textbookC. M. Bishop, Pattern Recognition and Machine Learning, Springer Recommended in the syllabus; the lecture's image denoising figures come from it, and the energy of the denoising model on this page has the same form.
standard resultBayes' rule, maximum likelihood, Lagrange multipliers and the Gaussian density Standard results used in the derivations. Every number and figure on this page was computed for it.