Bayesian network is a simple, graphical notation for conditional independence assertions, and hence for compact specification of full joint distributions

• Syntax:

  • A set of nodes, one per variable

  • A directed, acyclic graph (link ~= “directly influences”)

  • A conditional distribution for each node given its parent

    

In the simplest case, conditional distribution is represented by a conditional probability table (CPT) giving the distribution over $X_i$ for each combination of parent values.

Example

with CPT

Compactness

• A CPT for Boolean $X_i$ with $k$ Boolean parents has $2^k$ rows for the combinations of parent values
• Each row requires one number $p$ for $X_i = true$(so the number for false is 1-p)
• If each variable has no more than $k$ parents, the complete network requires $O(n\cdot2^k)$ numbers

Global semantics

Local semantics

Markov blanket

Constructing Bayesian Networks

• Need a method such that a series of locally testable assertions of conditional independence guarantees the required global semantics

  1. Choose an ordering of variables $X_1, \dots, X_n$
  2. see below, denote $X_i$ with X[i]

  for i from range(1 to n):
  	add X[i] to the network
  	select parents from X[1],....X[i-1] such that 
  	P(X[i] | Parents(X[i])) == P(X[i] | X[1], ..., X[i-1])
  

• This choice of parents guarantees the global semantics: