CSC 412 (Lecture 4): Undirected Graphical Models

Raquel Urtasun

University of Toronto

Feb 2, 2016

R Urtasun (UofT) CSC 412 Feb 2, 2016 1 / 37

Today

Undirected Graphical Models:

Semantics of the graph: conditional independence
Parameterization
Clique
Potentials
Gibbs Distribution
Partition function
Hammersley-Clifford Theorem
Factor Graphs
Learning

R Urtasun (UofT) CSC 412 Feb 2, 2016 2 / 37

Directed Graphical Models

Represent large joint distribution using ”local” relationships specified by the

graph
Each random variable is a node
The edges specify the statistical dependencies
We have seen directed acyclic graphs

R Urtasun (UofT) CSC 412 Feb 2, 2016 3 / 37

Directed Acyclic Graphs

Represent distribution of the form

Y
p(y1 , · · · , yN ) = p(yi |yπi )
i

with πi the parents of the node i

Factorizes in terms of local conditional probabilities
Each node has to maintain p(yi |yπi )
Each variable is CI of its non-descendants given its parents

{yi ⊥ yπ̃i |yπi } ∀i

with yπ̃i the nodes before yi that are not its parents
Such an ordering is a ”topological” ordering (i.e., parents have lower
numbers than their children)
Missing edges imply conditional independence

R Urtasun (UofT) CSC 412 Feb 2, 2016 4 / 37

Example

What’s the joint probability distribution?

R Urtasun (UofT) CSC 412 Feb 2, 2016 5 / 37

Internal Representation
For discrete variables, each node stores a conditional probability table (CPT)

R Urtasun (UofT) CSC 412 Feb 2, 2016 6 / 37

Are DGM Always Useful?
Not always clear how to choose the direction for the edges
Example: Modeling dependencies in an image

Figure : Causal MRF or a Markov mesh

Unnatural conditional independence, e.g., see Markov Blanket

mb(8) = {3, 7} ∪ {9, 13} ∪ {12, 4}, parents, children and co-parents
Alternative: Undirected Graphical models (UGMs)
R Urtasun (UofT) CSC 412 Feb 2, 2016 7 / 37
Undirected Graphical Models
Also called Markov random field (MRF) or Markov network
As in DGM, the nodes in the graph represent the variables
Edges represent probabilistic interaction between neighboring variables
How to parametrize the graph?
In DGM we used CPD (conditional probabilities) to represent
distribution of a node given others
For undirected graphs, we use a more symmetric parameterization that
captures the affinities between related variables.

R Urtasun (UofT) CSC 412 Feb 2, 2016 8 / 37

Semantics of the Graph: Conditional Independence

Global Markov Property: xA ⊥ xB |xC iff C separates A from B (no path in

the graph), e.g., {1, 2} ⊥ {6, 7}|{3, 4, 5}

Markov Blanket (local property) is the set of nodes that renders a node t
conditionally independent of all the other nodes in the graph
t ⊥ V \ cl(t)|mb(t)
where cl(t) = mb(t) ∪ t is the closure of node t. It is the set of neighbors,
e.g., mb(5) = {2, 3, 4, 6, 7}.
Pairwise Markov Property
s ⊥ t|V \ {s, t} ⇐⇒ Gst = 0

R Urtasun (UofT) CSC 412 Feb 2, 2016 9 / 37

Dependencies and Examples

Pairwise: 1 ⊥ 7|rest
Local: 1 ⊥ rest|2, 3
Global: 1, 2 ⊥ 6, 7|3, 4, 5

→ See page 119 of Koller and Friedman for a proof

R Urtasun (UofT) CSC 412 Feb 2, 2016 10 / 37
Image Example

Complete the following statements:

Pairwise: 1 ⊥ 7|rest?, 1 ⊥ 20|rest?,1 ⊥ 2|rest?

Local: 1 ⊥ rest|?, 8 ⊥ rest|?
Global: 1, 2 ⊥ 15, 20|?

R Urtasun (UofT) CSC 412 Feb 2, 2016 11 / 37

DGM and UGM

From Directed to Undirected via moralization

From Undirected to Directed via triangulation
See (Kohler and Friedman) book if interested
R Urtasun (UofT) CSC 412 Feb 2, 2016 12 / 37
Not all UGM can be represented as DGM

(a) (b) (c)

Fig. (a) Two independencies: (A ⊥ C |D, B) and (B ⊥ D|A, C )

Can we encode this with a DGM?
Fig. (b) First attempt: encodes (A ⊥ C |D, B) but it also implies that
(B ⊥ D|A) but dependent given both A, C
Fig. (c) Second attempt: encodes (A ⊥ C |D, B), but also implies that B
and D are marginally independent.

R Urtasun (UofT) CSC 412 Feb 2, 2016 13 / 37

Not all DGM can be represented as UGM

Example is the V-structure

Undirected model fails to capture the marginal independence (X ⊥ Y ) that

holds in the directed model at the same time as ¬(X ⊥ Y |Z )

R Urtasun (UofT) CSC 412 Feb 2, 2016 14 / 37

Cliques

A clique in an undirected graph is a subset of its vertices such that every

two vertices in the subset are connected by an edge
→ i.e., the subgraph induced by the clique is complete
The maximal clique is a clique that cannot be extended by including one
more adjacent vertex
The maximum clique is a clique of the largest possible size in a given graph
What are the maximal cliques? And the maximum clique in the figure?

R Urtasun (UofT) CSC 412 Feb 2, 2016 15 / 37

Parameterization of an UGM

y = (y1 , · · · , ym ) the set of all random variables

Unlike DGM, since there is no topological ordering associated with an
undirected graph, we can’t use the chain rule to represent p(y)
Instead of associating conditional probabilities to each node, we associate
potential functions or factors with each maximal clique in the graph
For a clique c, we define the potential function or factor

ψc (yc |θc )

to be any non-negative function, with yc the restriction to a subset of

variables in y
The joint distribution is then proportional to the product of clique potentials
Any positive distribution whose CI are represented with an UGM can be
represented this way (let’s see this more formally)

R Urtasun (UofT) CSC 412 Feb 2, 2016 16 / 37

Factor Parameterization

Theorem (Hammersley-Clifford)
A positive distribution p(y) > 0 satisfies the CI properties of an undirected graph
G iff p can be represented as a product of factors, one per maximal clique, i.e.,
1 Y
p(y|θ) = ψc (yc |θc )
Z (θ)
c∈C

with C the set of all (maximal) cliques of G , and Z (θ) the partition function
defined as XY
Z (θ) = ψc (yc |θc )
y c∈C

Proof.
Can be found in (Koller and Friedman book)

We need the partition function as the potentials are not conditional distributions.
In DGMs we don’t need it
R Urtasun (UofT) CSC 412 Feb 2, 2016 17 / 37
The partition function

The joint distribution is

1 Y
p(y|θ) = ψc (yc |θc )
Z (θ)
c∈C

with the partition function

XY
Z (θ) = ψc (yc |θc )
y c∈C

This is the hardest part of learning and inference. Why?

Factored structure of the distribution makes it possible to more efficiently do
the sums/integrals needed to compute it.

R Urtasun (UofT) CSC 412 Feb 2, 2016 18 / 37

Example

p(y) ∝ ψ1,2,3 (y1 , y2 , y3 )ψ2,3,5 (y2 , y3 , y5 )ψ2,4,5 (y2 , y4 , y5 )

ψ3,5,6 (y3 , y5 , y6 )ψ4,5,6,7 (y4 , y5 , y6 , y7 )

Is this representation unique?

What if I want a pairwise MRF?

R Urtasun (UofT) CSC 412 Feb 2, 2016 19 / 37

Representing Potentials

If the variables are discrete, we can represent the potential or energy

functions as tables of (non-negative) numbers

1
p(A, B, C , D) = ψa,b (A, B)ψb,c (B, C )ψc,d (C , D)ψa,d (A, D)
Z

The potentials are NOT probabilities

They represent compatibility between the different assignments

R Urtasun (UofT) CSC 412 Feb 2, 2016 20 / 37

Factor product

Given 3 disjoint set of variables X, Y, Z, and factors ψ1 (X, Y), ψ2 (Y, Z), the
factor product is defined as

ψx,y ,z (X, Y, Z) = ψx,y (X, Y)φy ,z (Y, Z)

R Urtasun (UofT) CSC 412 Feb 2, 2016 21 / 37

Query about probabilities: marginalization

What’s the p(b 0 )? Marginalize the other variables!

R Urtasun (UofT) CSC 412 Feb 2, 2016 22 / 37
Query about probabilities: conditioning

(Original) (Cond. on c 1 )

Conditioning on an assignment u to a subset of variables U can be done by

1 Eliminating all entries that are inconsistent with the assignment
2 Re-normalizing the remaining entries so that they sum to 1

R Urtasun (UofT) CSC 412 Feb 2, 2016 23 / 37

Reduced Markov Networks

Let H be a Markov network over X and let U = u be the context. The

reduced network H[u] is a Markov network over the nodes W = X − U where
we have an edge between X and Y if there is an edge between then in H

If U = Grade?
If U = {Grade, SAT }?

R Urtasun (UofT) CSC 412 Feb 2, 2016 24 / 37

Connections to Statistical Physics

The Gibbs Distribution is defined as

!
1 X
p(y|θ) = exp − E (yc |θc )
Z (θ) c

where E (yc ) > 0 is the energy associated with the variables in clique c
We can convert this distribution to a UGM by

ψ(yc |θc ) = exp (−E (yc |θc ))

High probability states correspond to low energy configurations.

These models are named energy based models

R Urtasun (UofT) CSC 412 Feb 2, 2016 25 / 37

Log Linear Models

Represent the log potentials as a linear function of the parameters

log ψc (yc ) = φc (yc )T θc

The log probability is then

X
log p(y|θ) = φc (yc )T θc − log Z (θ)
c

This is called log linear model

Example: we can represent tabular potentials
T
ψ(ys = j, yt = k) = exp([θst φst ]jk ) = exp(θst (j, k))

with φst (ys , yt ) = [· · · , I (ys = j, yt = k), · · · ) and I the indicator function

R Urtasun (UofT) CSC 412 Feb 2, 2016 26 / 37

Example: Ising model

Captures the energy of a set of interacting atoms.

yi ∈ {−1, +1} represents direction of the atom spin.
The graph is a 2D or 3D lattice, and the energy of the edges is symmetric
e st e −wst
 w 
ψst (ys , yt ) =
e −wst e wst
with wst the coupling strength between two nodes. If not connected wst = 0
Often we assume all edges have the same strength, i.e., wst = J 6= 0
If all weights positive, then neighboring spins likely same spin (ferromagnets,
associative Markov network)
If weights are very strong, then two models, all +1 and all -1
If weights negative, then anti-ferromagnets. Not all the constraints can be
satisfied, and the prob. distribution has multiple modes
Also individual node potentials that encode the bias of the individual atoms
(i.e., external field)
R Urtasun (UofT) CSC 412 Feb 2, 2016 27 / 37
More on Ising Models

Captures the energy of a set of interacting atoms.

yi ∈ {−1, +1} represents direction of the atom spin.
The energy associated is
 
 
1 X1 X 1 1 T T
P(y) = exp  wi,j yi yj + bi yi = exp
 y Wy + b y
Z 2 Z 2
i,j i

The energy can be written as

1
E (y) = − (y − µ)T W(y − µ) + c
2
with µ = −W−1 u, c = 12 µT Wµ
Looks like a Gaussian... but is it?
1
Often modulated by a temperature p(y) = Z exp(−E (y)/T )
T small makes distribution picky

R Urtasun (UofT) CSC 412 Feb 2, 2016 28 / 37

Example: Hopfield networks

A Hopfield network is a fully connected Ising model with a symmetric weight

matrix W = WT
The main application of Hopfield networks is as an associative memory

R Urtasun (UofT) CSC 412 Feb 2, 2016 29 / 37

Example: Potts Model
Multiple discrete states yi ∈ {1, 2, · · · , K }
Common to use  J 
e 0 0
ψst (ys , yt ) =  0 eJ 0
0 0 eJ
If J > 0 neighbors encourage to have the same label
Phase transition: change of behavior, J = 1.44 in example

Figure : Sample from a 10-state Potts model of size 128 × 128 for (a) J = 1.42,
(b) J = 1.44, (c) J = 1.46
R Urtasun (UofT) CSC 412 Feb 2, 2016 30 / 37
More on Potts
Used in image segmentation: neighboring pixels are likely to have the same
discrete label and hence belong to the same segment

1 Y Y
p(y|x, θ) = ψi (yi |x) ψi,j (yi , yj )
Z
i i,j

R Urtasun (UofT) CSC 412 Feb 2, 2016 31 / 37

Example: Gaussian MRF
Is a pairwise MRF
Y Y
p(y|θ) ∝ ψst (ys , yt ) ψt (yt )
s∼t t
 
1
ψst (ys , yt ) = exp − ys Λst yt
2
 
1 2
ψt (yt ) = exp − Λtt yt + ηt yt
2
The joint distribution is then
 
1
p(y|θ) ∝ exp η T y − yT Λy
2

This is a multivariate Gaussian with Λ = Σ−1 and η = Λµ

If Λst = 0 (structural zero), then no pairwise connection and by factorization
theorem
ys ⊥ yt |y−(st) ⇐⇒ Λst = 0
UGM are sparse precision matrices. Used for structured learning
R Urtasun (UofT) CSC 412 Feb 2, 2016 32 / 37
Factor Graphs

A factor graph is a graphical model representation that unifies directed and

undirected models
It is an undirected bipartite graph with two kinds of nodes.
Round nodes represent variables,
Square nodes represent factors
and there is an edge from each variable to every factor that mentions it.
Represents the distribution more uniquely than a graphical model

R Urtasun (UofT) CSC 412 Feb 2, 2016 33 / 37

Factor Graphs for Directed Models

One factor per CPD (conditional distribution) and connect the factor to all
the variables that use the CPD

R Urtasun (UofT) CSC 412 Feb 2, 2016 34 / 37

Learning using Gradient methods
MRF in log-linear form
!
1 X
T
p(y|θ) = exp θc φc (yc )
Z (θ) c

Given training examples y(i) , the scaled log likelihood is

" #
1 X (i) 1 X X
T (i) (i)
`(θ) = − log p(y |θ) = − θc φc (yc ) + log Z (θ)
N N c
i i

Since MRFs are in the exponential family, this function is convex in θ

We can find the global maximum, e.g., via gradient descent
 
∂` 1 X ∂
= −φc (yc(i) ) + log Z (i) (θ)
∂θc N ∂θc
i

The first term is constant for each iteration of gradient descent, it is called
the empirical means
R Urtasun (UofT) CSC 412 Feb 2, 2016 35 / 37
Moment Matching
 
∂` 1 X ∂
= −φc (yc(i) ) + log Z (i) (θ)
∂θc N ∂θc
i
The derivative of the log partition function w.r.t. θc is the expectation of
the c’th feature under the model
∂ log Z (θ) X
= φc (y)p(y|θ) = E [φc (y)]
∂θc y

Thus the gradient of the log likelihood is

" #
∂` 1 X (i)
= − φc (yc ) + E [φc (y)]
∂θc N
i

The second term is the contrastive term or unclamped term and requires
inference in the model (it has to be done for each step in gradient descent)
Dif. of the empirical distrib. and model’s expectation of the feature vector
∂`
= −Epemp [φc (y)] + Ep(·|θ) [φc (y)]
∂θc
At the optimum the moments are matched (i.e., moment matching)
R Urtasun (UofT) CSC 412 Feb 2, 2016 36 / 37
Approximated Methods

In UGM, no closed form solution to the ML estimate of the parameters,

need to do gradient-based optimization
Computing each gradient step requires inference → very expensive (NP-hard
in general)
Many approximations exist: stochastic approaches, pseudo likelihood, etc

R Urtasun (UofT) CSC 412 Feb 2, 2016 37 / 37