Transcript GRAPHICAL MODELS

GRAPHICAL MODELS
Directed - Bayes Nets
Undirected - Markov Random
Fields
Gibbs Random Fields
Causal graphs and causality
Graphical Model Technology
• B-Course: Server at Helsinki University
• Bayes Net: Kevin Murphy’s package (EM
oriented)
• Course code directory (MCMC-oriented)
• Genie (Carnegie- Mellon University)
• Numerous commercial and academic packages
of varying quality
Graphical Model Technology
• Inference model, directed:
The pdf of a variable C is chosen from CPT
(Conditional Probability Table)
set depending on values of parent variables.
• Inference model, undirected:
The pdf of a variable is chosen from CPT set
depending on values of all neighbours.
.. Inference model, GRF
The pdf of a variable is the product of a number of
‘energy functions’ involving cliques containing node.
Bayes’ Net (BN)
Directed Graph, No cycles.
Sample can be generated
along edges, each variable
can be sampled when its
parents are sampled
Useful for engineered systems,
diagnostic systems…
Conditional Probability Table-CPT
Complex BN application:
Situation Awareness
QuickTime™ and a
decompressor
are needed to see this picture.
R Suzic, thesis 2006
A part of the human fysiology: Bayes net describing
Markov Random Fields
Common in Imaging:
Distribution of node
conditional on the rest of
the nodes is the same as
distribution of node
conditional on neighbors-MARKOV property
Gibbs sampling: sample unknown nodes
conditional on neighbors: MCMC with acceptance
probability 1!
Segmentation in MR- MRF
sampling
Clustering (in spectrum)to get prel
segmentation. Smoothing with MRF
removes ‘pepper and salt’.
From BN to MRF
A BN can be changed to
an equivalent MRF by
MORALIZATION: Find unmarried
parents and marry them.
The MRF graph can however
describe a larger set of pdfs.
The opposite way is not possible:
Many MRFs have no equivalent BN
From BN to MRF
Exact inference in BN
is possible by
transforming
moralized graph to
junction tree: Every
edge in left graph must
live in some node of
right tree. Feasible only
if node sets are small
Moralized graph from BN
Junction tree or
tree-decomposition
Gibbs Random Field (GRF)
Maximal cliques C of G:
{i,h,g,e}, {e,f,d}, {e,c},{d,b},{c,b,a}.
G:
A GRF is a probability distribution over
node values that falls apart into
CLIQUE ENERGY FUNCTIONS
GRF:s are MRF:s!!
(see proof by Cheung in course pack)
Graphical Model Technology
• Train model using historic/simulation data
Where are the edges?
Which are the dependencies?
• Use model: From partial set of variables,
infer values of missing variables
• Flexible, Intuitive -- but Error Prone!
Learning Graphical model
from Data, MCMC style
• Decide on model type (BN, MRF, Chain Graph)
• If directed, decide ordering of Nodes to prevent
comparing equivalent models
• Find appropriate formula for computing Bayes’
factor in favor of edge present.
• Run MCMC: in each step propose to delete/add
edge, decide acceptance or not of proposal.
• Trace is sample of posterior graph structure.
Learning Graphical model
from Data, EM style
• Inference of most likely tree model is easy
• (Chow Liu, 1968): Use Dirichlet Prior
dependency test, select largest Bayes’
factor edge which does not create cycle,
and include it.
• This is essentially Kruskal’s algorithm
for shortest spanning tree.
Graph learning:
M3 vs M4,
M3’ vs M4’
Causal Inference:
M4’ vs M4’’
(Unreliable!)
Causality Reasoning
M4’: A dependent on B, but
given C, A and B are independent
AB|C, not AB
M4’’: A independent of B, but
given C, A dependent on B
not AB|C, AB
Does this suggest that C causes A and B in M4’,
and C is caused by A and B in M4’’??
Can be decided from observational data!
Testing Treatment
T --> R
Simple model. Is there an edge between
T (treatment) and R (recovery)?
But what about Gender perspective?
Simpson’s Paradox
A more useful model was:
S -> T -> R <- S, where S is sex