Bayesian Networks

a joint probability distribution over \(n\) binary variables is a table with \(2^n - 1\) free numbers. at \(n = 30\) that is a billion parameters for a toy problem — nobody can elicit them, store them, or estimate them from data. the bayesian network is the classical answer: encode the independencies of the distribution in a directed acyclic graph, and the joint collapses into a product of small local tables. 𐃏 the graph is simultaneously a data structure for storage, a calculus for reading off independence, and the substrate on which every inference algorithm runs.

from joint distributions to graphs#

everything in probabilistic reasoning reduces to operations on the joint distribution \(P(X_1, \dots, X_n)\): marginalise out what you don’t care about, condition on what you observed. the problem is purely representational — the joint is exponential in \(n\).

the chain rule factorises any joint, with no assumptions, in any variable order:

\begin{equation} P(x_1, \dots, x_n) = \prod_{i=1}^{n} P(x_i \mid x_1, \dots, x_{i-1}). \end{equation}

this trades one big table for \(n\) conditional tables, the last of which is just as big as the joint — no saving yet. the saving comes from conditional independence: if \(X_i\) is independent of most of its predecessors given a few of them (its parents \(\mathbf{U}_i\)), each factor shrinks to \(P(x_i \mid \mathbf{u}_i)\). sparse independence structure is what a bayesian network stores; the graph is nothing but a bookkeeping device for which conditioning variables survived. 𐃏

definition#

a bayesian network over variables \(X_1, \dots, X_n\) is a pair \((G, \Theta)\):

• \(G\) — a directed acyclic graph with one node per variable;
• \(\Theta\) — for each variable \(X\) with parents \(\mathbf{U}\), a conditional probability table (cpt) \(\theta_{x \mid \mathbf{u}} = P(x \mid \mathbf{u})\), one distribution over \(X\) per parent instantiation \(\mathbf{u}\).

the semantics of the graph are the markovian assumptions: every variable is independent of its non-descendants given its parents,

\begin{equation} X \;\perp\; \mathrm{NonDescendants}(X) \;\mid\; \mathrm{Parents}(X), \end{equation}

written collectively as \(\mathrm{Markov}(G)\). from these assumptions and the ordinary chain rule follows the chain rule for bayesian networks:

\begin{equation} P(x_1, \dots, x_n) \;=\; \prod_{i=1}^{n} \theta_{x_i \mid \mathbf{u}_i}, \end{equation}

the joint is the product of one cpt entry per variable. this factorisation is the network’s entire content: a bayesian network is a compact representation of a unique joint distribution.

the sprinkler network#

the running example of the course (and of darwiche’s book): winter makes rain likely and sprinkler use unlikely; either wets the grass; rain alone makes the road slippery.

the parametrisation, writing \(a\) for \(A = \mathrm{true}\) and \(\bar{a}\) for \(A = \mathrm{false}\):

only the true-rows need storing — each row of a cpt is a distribution and must sum to one, so the false-entries are complements. 𐃏 the chain rule then prices any world instantly:

\begin{equation} P(a, \bar{b}, c, d, e) = \theta_a \,\theta_{\bar{b} \mid a}\, \theta_{c \mid a}\, \theta_{d \mid \bar{b}, c}\, \theta_{e \mid c} = (0.6)(0.8)(0.8)(0.8)(0.7) = 0.21504. \end{equation}

how many parameters?#

for a variable with \(d\) states and \(k\) parents of \(d\) states each, the cpt has \(O(d^{k+1})\) entries — exponential in the in-degree, not in \(n\). a network of \(n\) variables with maximum in-degree \(k\) costs \(O(n\, d^{k+1})\) parameters total. the moral: what makes a bayesian network compact is bounded fan-in, and when a node unavoidably has many parents, structured cpt representations (noisy-or, decision trees, rules) replace the exponential table.

independence semantics#

the markovian assumptions are only the axioms. many more independencies follow from them, and the graphoid axioms generate them: symmetry, decomposition, weak union, contraction, and (for strictly positive distributions) intersection. deriving independencies by hand from these axioms is tedious; the point of the graph is that a purely graphical test — d-separation — captures their full inferential power.

d-separation and the three valves#

think of every path between two nodes as a pipe and every intermediate node as a valve. a valve is either open (lets dependence flow) or closed (blocks it), and its behaviour depends on how the path’s edges meet at it:

• sequential (chain) \(X \to W \to Y\): open by default, closed once \(W\) is observed — knowing the intermediate cause screens off the ends. in the sprinkler network, \(A \to C \to E\): once you know it rained, winter tells you nothing more about the road.
• divergent (common cause) \(X \leftarrow W \to Y\): open by default, closed once \(W\) is observed. \(B \leftarrow A \to C\): sprinkler use and rain correlate only through the season.
• convergent (common effect, the collider) \(X \to W \leftarrow Y\): closed by default, opened by observing \(W\) or any descendant of \(W\). \(B \to D \leftarrow C\): sprinkler and rain are independent a priori, but once the grass is seen wet they compete — learning it rained “explains away” the sprinkler. 𐃏

a path is blocked by \(\mathbf{Z}\) if at least one of its valves is closed. disjoint sets \(\mathbf{X}\) and \(\mathbf{Y}\) are d-separated by \(\mathbf{Z}\), written \(\mathrm{dsep}_G(\mathbf{X}, \mathbf{Z}, \mathbf{Y})\), iff every path from \(\mathbf{X}\) to \(\mathbf{Y}\) is blocked by \(\mathbf{Z}\).

testing d-separation in linear time#

enumerating paths is exponential; the practical test is a graph surgery followed by plain reachability: 𐃏

1. prune — repeatedly delete any leaf node not in \(\mathbf{X} \cup \mathbf{Y} \cup \mathbf{Z}\). (an unobserved leaf is a closed convergent valve or an inferentially inert endpoint; removing it can close nothing that was open.)
2. delete — remove every edge leaving a node in \(\mathbf{Z}\). (with sequential and divergent valves closed by observation, only inbound edges of \(\mathbf{Z}\) nodes — the open collider case — survive.)
3. test — \(\mathbf{X}\) and \(\mathbf{Y}\) are d-separated iff they are disconnected in the surgered graph, checkable by depth-first search.

the whole procedure is \(O(n + m)\) in the size of the graph.

soundness, completeness, i-maps#

• soundness: if \(\mathrm{dsep}_G(\mathbf{X}, \mathbf{Z}, \mathbf{Y})\) then \(\mathbf{X} \perp \mathbf{Y} \mid \mathbf{Z}\) in every distribution that factorises over \(G\). d-separation never lies about independence.
• incompleteness: the converse fails — a particular parametrisation may hide extra independencies the graph cannot see (numbers can conspire; e.g. a cpt that ignores one of its parents). so connectedness does not prove dependence.

a dag \(G\) is an i-map (independence map) of a distribution \(P\) if every independence claimed by \(G\) holds in \(P\) — the factorisation guarantees exactly this. it is a minimal i-map if no edge can be removed without breaking the property, and a p-map (perfect map) if additionally every independence in \(P\) is visible as a d-separation. not every distribution has a p-map; the fully connected dag is a trivial (useless) i-map of everything, which is why “sparser is better” has formal content.

markov blankets#

the markov blanket of \(X\) is its parents, its children, and its children’s other parents (spouses). conditioned on its blanket, \(X\) is independent of everything else in the network:

\begin{equation} X \;\perp\; \mathbf{V} \setminus (\{X\} \cup \mathrm{MB}(X)) \;\mid\; \mathrm{MB}(X). \end{equation}

the spouses are the non-obvious members: observing a common child opens the collider, so the other parent becomes relevant and must be conditioned on to seal \(X\) off. the blanket is the theoretical basis of gibbs sampling (each resampling step conditions only on the blanket) and a handy feature-selection notion: the blanket of a class variable is the minimal set of observations worth making.

bayesian networks as classifiers#

naive bayes#

put the class \(C\) on top, one arrow to each attribute:

\begin{equation} P(C, A_1, \dots, A_n) = P( C) \prod_{i=1}^{n} P(A_i \mid C), \end{equation}

which needs \(O(|C| + n\,|C|\,|A|)\) parameters instead of \(O(|C|\,|A|^n)\) — linear in \(n\). classification is a maximum a posteriori query, \(\hat{c} = \arg\max_c P( c) \prod_i P(a_i \mid c)\), computed in log-space to dodge underflow when \(n\) is large (a bag-of-words spam filter multiplies thousands of tiny probabilities). the assumption that attributes are independent given the class is usually false, which makes naive bayes systematically over-confident: its posteriors saturate towards 0 and 1. fine for picking the argmax, dangerous when the probability itself matters (medical diagnosis).

tree-augmented naive bayes#

tan relaxes the independence assumption one notch: on top of the class arrows, the attributes are allowed a tree of edges among themselves, chosen to maximise conditional mutual information \(I(A_i; A_j \mid C)\) — a chow–liu construction. each attribute then has at most two parents (the class and one attribute), so parameters stay small while the worst naive-bayes violations get patched. further relaxations (ban, gbn) trade more structure for more data hunger.

gaussian bayesian networks#

continuous variables break the table representation, but the machinery survives if every cpt is a linear gaussian model:

\begin{equation} X \mid \mathbf{u} \;\sim\; \mathcal{N}\!\left(\beta_0 + \boldsymbol{\beta}^{\top} \mathbf{u},\; \sigma^2\right), \end{equation}

the child’s mean is linear in its parents and its variance is constant. a network whose cpds are all linear gaussian defines a joint multivariate gaussian, and vice versa — every multivariate gaussian factorises as a gaussian bayesian network in any variable ordering. 𐃏 inference stays closed-form (conditioning and marginalising gaussians yields gaussians), which is what makes kalman filters exact, and it is the setting for gaussian belief propagation on the approximate inference page.

a note on causality#

the arrows of a bayesian network are not causal claims — any dag consistent with the distribution’s independencies is an equally valid i-map, and reversing edges (with recomputed cpts) can represent the same joint. that said, networks built along causal directions are the ones humans can elicit (“rain causes wet grass” has a natural cpt; the reverse does not), tend to be sparsest, and are the only ones that answer interventional questions correctly: setting \(\mathrm{do}(D = d)\) — forcing the grass wet — severs \(D\) from its parents and, unlike conditioning on \(D = d\), licenses no inference back up to rain. observation flows both ways along edges; intervention only flows down the causal ones.

results#

curated statements worth having at your fingertips:

• chain rule for bayesian networks — if \(P\) satisfies \(\mathrm{Markov}(G)\), then \(P(x_1, \dots, x_n) = \prod_i \theta_{x_i \mid \mathbf{u}_i}\).
• parameter complexity — a network of \(n\) variables, each with \(\le d\) states and \(\le k\) parents, has \(O(n\, d^{k+1})\) parameters.
• soundness of d-separation — \(\mathrm{dsep}_G(\mathbf{X}, \mathbf{Z}, \mathbf{Y}) \implies \mathbf{X} \perp \mathbf{Y} \mid \mathbf{Z}\) for every \(P\) factorising over \(G\).
• incompleteness of d-separation — there exist \(G, P\) with \(P\) faithful to the factorisation where \(\mathbf{X} \perp \mathbf{Y} \mid \mathbf{Z}\) holds yet \(\mathbf{X}, \mathbf{Y}\) are d-connected.
• d-separation complexity — decidable in \(O(n + m)\) by pruning + edge deletion + reachability.
• markov blanket — \(\mathrm{MB}(X) = \mathrm{Parents}(X) \cup \mathrm{Children}(X) \cup \mathrm{Spouses}(X)\) renders \(X\) independent of the rest of the network.
• gaussian correspondence — linear gaussian networks \(\equiv\) multivariate gaussians.

see also#

• exact inference — variable elimination and the jointree algorithm on these networks
• approximate inference — sampling when exact is too expensive
• markov networks — the undirected cousins
• markov chains and hidden markov models — bayesian networks unrolled over time
• learning graphical models — estimating the cpts and the structure from data
• modeling and reasoning with bayesian networks — darwiche’s book, the canonical reference for this material