Probabilistic graphical models

Exact and approximate inference

22-808: Generative models
Sharif University of Technology
Fall 2025

Fatemeh Seyyedsalehi
The inference problem
 Inference: answering conditional or marginal
probabilities in a joint distribution
 The graph structure and CPDs (in BNs) or potential functions
(in MRFs) are known.
 Example:

𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷 𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿 = 1 = ?
𝑝𝑝 𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼 = 1 = ?
𝑝𝑝 𝑆𝑆𝑆𝑆𝑆𝑆 = ?

Koller Book
2
The inference problem
 Notation:
 Colored nodes: observed random variables
 White nodes: latent/hidden/unobserved random variables
 Others not in a circle: parameters of CPDs
a b
𝒙𝒙𝟐𝟐 𝒙𝒙𝟏𝟏

𝒙𝒙𝟑𝟑 𝒙𝒙𝟒𝟒

c 𝒙𝒙𝟓𝟓
𝒙𝒙𝟔𝟔

3
The inference problem
 Consider the following joint distribution
𝑝𝑝(𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥6 )
over discrete random variables with k possible values.
𝒙𝒙𝟐𝟐 𝒙𝒙𝟏𝟏
 An inference query:
𝒙𝒙𝟑𝟑 𝒙𝒙𝟒𝟒
𝑝𝑝 𝑥𝑥2 𝑥𝑥4 = 𝑥𝑥4 = ?
𝒙𝒙𝟓𝟓
 A naïve solution: 𝒙𝒙𝟔𝟔
𝑝𝑝(𝑥𝑥2 , 𝑥𝑥4 )
𝑝𝑝 𝑥𝑥2 𝑥𝑥4 = 𝑥𝑥4 =
∑𝑥𝑥2 𝑝𝑝(𝑥𝑥2 , 𝑥𝑥4 )

𝑝𝑝 𝑥𝑥2 , 𝑥𝑥4 = � � � � 𝑝𝑝(𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 )

𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6

4
The inference problem
 However, this distribution is factorized
Over this graph and we have:
𝒙𝒙𝟐𝟐 𝒙𝒙𝟏𝟏

𝑝𝑝 𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥6 = 𝒙𝒙𝟑𝟑 𝒙𝒙𝟒𝟒

𝑝𝑝 𝑥𝑥2 𝑝𝑝 𝑥𝑥1 𝑝𝑝 𝑥𝑥3 𝑥𝑥1 , 𝑥𝑥2 𝑝𝑝 𝑥𝑥5 𝑥𝑥4 , 𝑥𝑥3 𝑝𝑝(𝑥𝑥6 |𝑥𝑥5 )
𝒙𝒙𝟓𝟓
𝒙𝒙𝟔𝟔
 A better solution:
𝑝𝑝 𝑥𝑥2 , 𝑥𝑥4 = � � � � 𝑝𝑝(𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 )
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6

= � � � � 𝑝𝑝 𝑥𝑥2 𝑝𝑝 𝑥𝑥1 𝑝𝑝 𝑥𝑥3 𝑥𝑥1 , 𝑥𝑥2 𝑝𝑝 𝑥𝑥5 𝑥𝑥4 , 𝑥𝑥3 𝑝𝑝(𝑥𝑥6 |𝑥𝑥5 )
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6

5
The inference problem
 A better solution:
𝑝𝑝 𝑥𝑥2 , 𝑥𝑥4 = � � � � 𝑝𝑝(𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 )
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6

= � � � � 𝑝𝑝 𝑥𝑥2 𝑝𝑝 𝑥𝑥1 𝑝𝑝 𝑥𝑥3 𝑥𝑥1 , 𝑥𝑥2 𝑝𝑝 𝑥𝑥5 𝑥𝑥4 , 𝑥𝑥3 𝑝𝑝(𝑥𝑥6 |𝑥𝑥5 )
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6
4
 𝑂𝑂(𝑘𝑘 ) computation !

Distributive law: If 𝑋𝑋 ∉ 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝜙𝜙1 ) then ∑𝑋𝑋 𝜙𝜙1 𝜙𝜙2 = 𝜙𝜙1 ∑𝑋𝑋 𝜙𝜙2

 Therefore, we can perform summation over the product of

only a subset of factors
6
The inference problem
 A better solution:
𝑝𝑝 𝑥𝑥2 , 𝑥𝑥4 = � � � � 𝑝𝑝(𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 )
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6

= � � � � 𝑝𝑝 𝑥𝑥2 𝑝𝑝 𝑥𝑥1 𝑝𝑝 𝑥𝑥3 𝑥𝑥1 , 𝑥𝑥2 𝑝𝑝 𝑥𝑥5 𝑥𝑥4 , 𝑥𝑥3 𝑝𝑝(𝑥𝑥6 |𝑥𝑥5 ) =
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6

𝑝𝑝(𝑥𝑥2 ) � 𝑝𝑝 𝑥𝑥1 � 𝑝𝑝 𝑥𝑥3 𝑥𝑥1 , 𝑥𝑥2 � 𝑝𝑝 𝑥𝑥5 𝑥𝑥4 , 𝑥𝑥3 � 𝑝𝑝(𝑥𝑥6 |𝑥𝑥5 )
𝑥𝑥1 𝑥𝑥3 𝑥𝑥5 𝑥𝑥6
 𝑂𝑂(4𝑘𝑘 3 ) computation !

7
Variable elimination
 Generally, when a distribution is factorized, Variable
elimination algorithm can decrease the computational
complexity.

 Variable elimination algorithm for exact inference:

 We select an elimination order of random variables
 For each random variable, all factors containing that variable
are removed from the set of factors and multiplied
 The selected random variable is summed out from the product
of factors and a new factor is obtained
 The resulted factor is multiplied to others and algorithm is
continued.
8
Exact inference: variable elimination
Example

9
Exact inference: variable elimination
Example

10
Exact inference: variable elimination
Example

11
Exact inference: variable elimination
Example

12
Exact inference: variable elimination
 In each elimination step, we need 𝑂𝑂(𝑘𝑘 𝑚𝑚 ) computations
where 𝑚𝑚 is the number of variables is the product of
factors containing the variable
 𝑘𝑘 is the size of the largest scope of random variables
 With a system with 𝑛𝑛 random variables, we need 𝑂𝑂(𝑛𝑛𝑘𝑘 𝑚𝑚 )
computations

13
Inference algorithms
 Exact inference :
 Variable elimination
 Can be applied on any graph
 Responds only one query
 Message passing
 Sum-product
 Only for trees
 Junction tree
 Can be applied on any graph

 In many real-world applications these algorithms are

computationally too complex to be applied

14
Inference algorithms
 Approximate inference:
 Deterministic approximation
 Variational inference
 Stochastic simulation/sampling methods

15
Variational inference
 The calculus of variations (or variational calculus) is a field
of mathematical analysis that uses variations, which are
small changes in functions and functionals, to find
maxima and minima of functionals
 Functionals: functions of functions 

 Variational Bayesian methods are a family of techniques

for approximating intractable integrals arising in Bayesian
inference and machine learning.

16
Variational inference
 Generally, consider two sets of random variables in a joint
distribution 𝑝𝑝:
 𝑋𝑋: Observed random variables
 Z: Latent random variables
calculate 𝑝𝑝(𝑍𝑍|𝑋𝑋)?

𝑝𝑝(𝑋𝑋,𝑍𝑍)
 𝑝𝑝 𝑍𝑍 𝑋𝑋 = , where 𝑝𝑝(𝑋𝑋) = ∫ 𝑝𝑝(𝑋𝑋, 𝑍𝑍)
𝑝𝑝(𝑋𝑋)
 We usually have the joint distribution 𝑝𝑝(𝑋𝑋, 𝑍𝑍).
 However, calculating the marginal distribution 𝑝𝑝(𝑋𝑋) is
interactable.

17
Variational inference
 Generally, consider two sets of random variables in a joint
distribution 𝑝𝑝:
 𝑋𝑋: Observed random variables
 Z: Latent random variables
calculate 𝑝𝑝(𝑍𝑍|𝑋𝑋)?

 Solution: we select a family distribution 𝑄𝑄 in which the

inference query is tractable. Then we find the best
approximate of 𝑝𝑝 in 𝑄𝑄.

18
Variational inference
 Solution: we select a family distribution 𝑄𝑄 in which the
inference query is tractable. Then we find the best
approximate of 𝑝𝑝 in 𝑄𝑄.
 Converting inference to optimization over a functional
(variational calculus)
 A family distribution 𝑄𝑄
 A similarity metric between 𝑝𝑝 and 𝑞𝑞
 KL-divergence

𝑞𝑞 𝑄𝑄
𝑝𝑝

19
Variational inference
 Kullback-Leibler divergence between two distribution:
𝑝𝑝 𝑥𝑥
𝐾𝐾𝐾𝐾(𝑝𝑝 ∥ 𝑞𝑞) = � 𝑝𝑝 𝑥𝑥 log 𝑑𝑑𝑑𝑑
𝑞𝑞 𝑥𝑥
 This is positive for any two distributions

 𝐾𝐾𝐾𝐾(𝑝𝑝| 𝑞𝑞 = 0 if and only if 𝑝𝑝 ≡ 𝑞𝑞

 It is not symmetric
 we call it divergence not distance

20
KL-divergence
 Suppose 𝑝𝑝 is the target distribution we want to
approximate it,

 I-projection: 𝐾𝐾𝐾𝐾(𝑞𝑞 ∥ 𝑝𝑝)

 M-projection: 𝐾𝐾𝐾𝐾(𝑝𝑝 ∥ 𝑞𝑞)

 Obviously, when 𝑝𝑝 ∉ 𝑄𝑄 the result of following

optimizations is different
min 𝐾𝐾𝐾𝐾(𝑝𝑝 ∥ 𝑞𝑞)
𝑞𝑞
min 𝐾𝐾𝐾𝐾(𝑞𝑞 ∥ 𝑝𝑝)
𝑞𝑞

21
KL-divergence
 𝑝𝑝 is a mixture of gaussian, 𝑄𝑄 is the family of gaussian
distributions.

M-projection I-projection
min 𝐾𝐾𝐾𝐾(𝑝𝑝 ∥ 𝑞𝑞) min 𝐾𝐾𝐾𝐾(𝑞𝑞 ∥ p)
𝑞𝑞 𝑞𝑞

Bishop Book
22
Variational inference
 In variational inference: I-projection
 Because of the computational complexity of 𝑝𝑝.

 We should solve the following optimization to find the best 𝑞𝑞:

min 𝐾𝐾𝐾𝐾(𝑞𝑞(𝑍𝑍) ∥ 𝑝𝑝(𝑍𝑍|𝑋𝑋))

𝑞𝑞

𝑞𝑞(𝑍𝑍) 𝑞𝑞 𝑍𝑍 𝑝𝑝(𝑋𝑋)
𝐾𝐾𝐾𝐾 𝑞𝑞(𝑍𝑍) ∥ 𝑝𝑝(𝑍𝑍|𝑋𝑋) = � 𝑞𝑞 𝑍𝑍 log 𝑑𝑑𝑑𝑑 = � 𝑞𝑞 𝑍𝑍 log 𝑑𝑑𝑍𝑍
𝑝𝑝(𝑍𝑍|𝑋𝑋) 𝑝𝑝(𝑍𝑍, 𝑋𝑋)
𝑞𝑞 𝑍𝑍 𝑝𝑝(𝑋𝑋) 𝑞𝑞 𝑍𝑍
= � 𝑞𝑞 𝑍𝑍 log 𝑑𝑑𝑍𝑍 = � 𝑞𝑞 𝑍𝑍 log 𝑑𝑑𝑍𝑍 + � 𝑞𝑞 𝑍𝑍 log 𝑝𝑝 𝑋𝑋 𝑑𝑑𝑑𝑑
𝑝𝑝(𝑍𝑍, 𝑋𝑋) 𝑝𝑝(𝑍𝑍, 𝑋𝑋)
= 𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋 + log 𝑝𝑝(𝑥𝑥)

23
Variational inference

 𝐾𝐾𝐾𝐾 𝑞𝑞(𝑍𝑍) ∥ 𝑝𝑝(𝑍𝑍|𝑋𝑋) = 𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋 + log 𝑝𝑝(𝑥𝑥)

 Two facts:
 𝐾𝐾𝐾𝐾 𝑞𝑞(𝑍𝑍) ∥ 𝑝𝑝(𝑍𝑍|𝑋𝑋) > 0 → log 𝑝𝑝(𝑥𝑥) > −𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋

Evidence lower bound (ELBO)

 log 𝑝𝑝(𝑥𝑥) < 0 → 𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋 > 𝐾𝐾𝐾𝐾 𝑞𝑞(𝑍𝑍) ∥ 𝑝𝑝(𝑍𝑍|𝑋𝑋)

24
Variational inference
 log 𝑝𝑝(𝑥𝑥) < 0 → 𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋 > 𝐾𝐾𝐾𝐾 𝑞𝑞(𝑍𝑍) ∥ 𝑝𝑝(𝑍𝑍|𝑋𝑋)

The upper bound

 In variational inference, we minimize the above upper

bound

argmin 𝐾𝐾𝐾𝐾(𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝(𝑍𝑍, 𝑋𝑋))

𝑞𝑞∈𝑄𝑄

25
Variational mean filed approximation
 A common type of variational Bayes

Mean-field assumption: the unknown variables can be

partitioned so that each partition is independent of the
others

26
Variational mean filed approximation
Naïve mean field: the family distribution 𝑄𝑄 is fully factorized
as follows:
𝑞𝑞 𝑍𝑍 = � 𝑞𝑞𝑖𝑖 (𝑧𝑧𝑖𝑖 )
𝑖𝑖

 Variational mean field inference:

argmin 𝐾𝐾𝐾𝐾(𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝(𝑍𝑍, 𝑋𝑋)) = argmin 𝐾𝐾𝐾𝐾(𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝(𝑍𝑍, 𝑋𝑋))

𝑞𝑞∈𝑄𝑄 𝑞𝑞1 ,𝑞𝑞2 ,..,𝑞𝑞𝑛𝑛

27
Variational mean filed approximation
Naïve mean field: the family distribution 𝑄𝑄 is fully factorized
as follows:
𝑞𝑞 𝑍𝑍 = � 𝑞𝑞𝑗𝑗 (𝑧𝑧𝑗𝑗 )
𝑗𝑗

 We iteratively optimizing over one coordinate (factor) at a

time, as follows,

𝜕𝜕𝜕𝜕𝜕𝜕(𝑞𝑞 𝑍𝑍 ∥𝑝𝑝(𝑍𝑍,𝑋𝑋))
= 0 to obtain 𝑞𝑞𝑗𝑗∗
𝜕𝜕𝑞𝑞𝑗𝑗

28
Variational mean filed approximation

In variational naïve mean field inference, optimum factors

are obtained as follows :
log 𝑞𝑞𝑗𝑗∗ (𝑧𝑧𝑗𝑗 ) ∝ Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍)
As each 𝑞𝑞𝑗𝑗∗ (𝑧𝑧𝑗𝑗 ) depends on others, 𝑞𝑞−𝑗𝑗 :
1. We initialize 𝑞𝑞𝑗𝑗∗ s
2. We iteratively update each 𝑞𝑞𝑗𝑗∗ until convergence!

29
Variational mean filed approximation
In variational naïve mean field inference, optimum factors
are obtained as follows:

log 𝑞𝑞𝑗𝑗∗ (𝑧𝑧𝑗𝑗 ) ∝ Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍)

 Proof:
𝑞𝑞(𝑍𝑍)
𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋 = � 𝑞𝑞 𝑍𝑍 log 𝑑𝑑𝑑𝑑
𝑝𝑝(𝑍𝑍, 𝑋𝑋)
𝑞𝑞(𝑍𝑍)
= Ε𝑞𝑞 𝑍𝑍 log = Ε𝑞𝑞 𝑍𝑍 log 𝑞𝑞(𝑍𝑍) − Ε𝑞𝑞 𝑍𝑍 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍)
𝑝𝑝(𝑋𝑋, 𝑍𝑍)
1 2

30
Variational mean filed approximation
proof cont.
 We know,
𝑞𝑞 𝑍𝑍 = � 𝑞𝑞𝑖𝑖 (𝑧𝑧𝑖𝑖 ) → log 𝑞𝑞(𝑍𝑍) = � log 𝑞𝑞𝑖𝑖 (𝑧𝑧𝑖𝑖 )
𝑖𝑖 𝑖𝑖
 Therefore,
1: Ε𝑞𝑞 𝑍𝑍 log 𝑞𝑞(𝑍𝑍) = ∑𝑖𝑖 Ε𝑞𝑞𝑖𝑖 𝑧𝑧𝑖𝑖 log 𝑞𝑞𝑖𝑖 (𝑧𝑧𝑖𝑖 )

 Also,
2: Ε𝑞𝑞 𝑍𝑍 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍) = Ε𝑞𝑞𝑗𝑗 𝑧𝑧𝑗𝑗 Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍)

31
Variational mean filed approximation
proof cont.
 Therefore,
𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋
= � Ε𝑞𝑞𝑖𝑖 𝑧𝑧𝑖𝑖 log 𝑞𝑞𝑖𝑖 (𝑧𝑧𝑖𝑖 ) − Ε𝑞𝑞𝑗𝑗 𝑧𝑧𝑗𝑗 Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍)
𝑖𝑖
 and

𝜕𝜕 𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋
𝜕𝜕𝑞𝑞𝑗𝑗
𝜕𝜕 ∫𝑧𝑧 𝑞𝑞𝑗𝑗 𝑧𝑧𝑗𝑗 −Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝 𝑋𝑋, 𝑍𝑍 + log 𝑞𝑞𝑗𝑗 (𝑧𝑧𝑗𝑗 ) 𝑑𝑑𝑧𝑧𝑗𝑗 + 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑗𝑗
=
𝜕𝜕𝑞𝑞𝑗𝑗

32
Variational mean filed approximation
proof cont.
 According to “Euler–Lagrange equation” we can write,

𝜕𝜕𝜕𝜕𝜕𝜕 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋 𝜕𝜕𝑞𝑞𝑗𝑗 (𝑧𝑧𝑗𝑗 ) −Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝 𝑋𝑋, 𝑍𝑍 + log 𝑞𝑞𝑗𝑗 (𝑧𝑧𝑗𝑗 )
=
𝜕𝜕𝑞𝑞𝑗𝑗 𝜕𝜕𝑞𝑞𝑗𝑗

 Remember the goal is:

𝑞𝑞𝑗𝑗∗ = argmin 𝐾𝐾𝐾𝐾 𝑞𝑞 𝑍𝑍 ∥ 𝑝𝑝 𝑍𝑍, 𝑋𝑋
𝑞𝑞𝑗𝑗
 Therefore:
𝜕𝜕 𝑞𝑞𝑗𝑗 (𝑧𝑧𝑗𝑗 ) Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍) − log 𝑞𝑞𝑗𝑗 (𝑧𝑧𝑗𝑗 )
=0
𝜕𝜕𝑞𝑞𝑗𝑗
→ log 𝑞𝑞𝑗𝑗∗ (𝑧𝑧𝑗𝑗 ) = Ε𝑞𝑞−𝑗𝑗 log 𝑝𝑝(𝑋𝑋, 𝑍𝑍) + 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐

33
Inference algorithms
 Approximate inference:
 Deterministic approximation
 Variational inference
 Stochastic simulation/sampling methods

34
Sampling based approximation
 Consider the following set of i.i.d. samples from the
distribution 𝑝𝑝(𝑥𝑥):
𝐷𝐷 = {𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 }

Monte Carlo method: for an arbitrary function 𝑓𝑓(𝑥𝑥) of

random variable 𝑥𝑥 , we can estimate Ε𝑝𝑝 [𝑓𝑓] as follows
(empirical expectation),
𝑛𝑛
1
Ε𝑝𝑝 𝑓𝑓 = � 𝑓𝑓(𝑥𝑥 𝑖𝑖 )
𝑛𝑛
𝑖𝑖=1

35
 Sampling based approximation
Monte Carlo method: for an arbitrary function 𝑓𝑓(𝑥𝑥) of
random variable 𝑥𝑥 , we can estimate Ε𝑝𝑝 [𝑓𝑓] as follows
(empirical expectation),
𝑛𝑛
1
Ε𝑝𝑝 𝑓𝑓 = � 𝑓𝑓(𝑥𝑥 𝑖𝑖 )
𝑛𝑛
𝑖𝑖=1

 Marginal probability: p x1 = k → 𝑓𝑓 = 𝐼𝐼(𝑥𝑥1 = 𝑘𝑘)

 Mean of a distribution: 𝑓𝑓 = 𝑥𝑥
 …

36
Forward sampling in a BN
Given a BN, and number of samples 𝑁𝑁
Choose a topological order on variables: 𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑀𝑀
For 𝑖𝑖 = 1 to 𝑁𝑁
For 𝑗𝑗 = 1 to 𝑀𝑀
 Sample 𝑥𝑥𝑗𝑗𝑖𝑖 from the distribution 𝑝𝑝(𝑥𝑥𝑗𝑗 |𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑥𝑥𝑗𝑗 )
Add 𝑥𝑥1𝑖𝑖 , 𝑥𝑥2𝑖𝑖 , … , 𝑥𝑥𝑀𝑀
𝑖𝑖
to the sample set

37
Forward sampling in a BN
 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝐷𝐷 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑝𝑝(𝐷𝐷)
 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝐼𝐼 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑝𝑝 𝐼𝐼
 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝐺𝐺 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑝𝑝(𝐺𝐺|𝐷𝐷, 𝐼𝐼)
 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝑆𝑆 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑝𝑝(𝑆𝑆|𝐼𝐼)
 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝐿𝐿 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑝𝑝(𝐿𝐿|𝐺𝐺)

38 Koller Book
Forward sampling in a BN
 Problems:
 When the evidence rarely happens, we would need lots of
samples, and most would be wasted
 Overall probability of accepting a sample rapidly decreases
when the number of observed variables and states that those
variables can take increases
 This approach is very slow and rarely used in practice.

39
Importance sampling
 When sampling from the target distribution 𝑝𝑝 is hard, we use a
proposal distribution 𝑞𝑞
 𝑞𝑞 should dominates 𝑝𝑝 → 𝑞𝑞 𝑥𝑥 > 0 whenever 𝑝𝑝 𝑥𝑥 > 0

 We sample from the proposal distribution 𝑞𝑞 and consider a

weight for each sample:
𝑝𝑝 𝑥𝑥
Ε𝑝𝑝 𝑓𝑓 = � 𝑓𝑓 𝑥𝑥 𝑝𝑝 𝑥𝑥 𝑑𝑑𝑑𝑑 = � 𝑓𝑓 𝑥𝑥 𝑞𝑞 𝑥𝑥 𝑑𝑑𝑑𝑑
𝑞𝑞 𝑥𝑥
𝑛𝑛
𝑝𝑝 𝑥𝑥 𝑖𝑖
1
Ε𝑝𝑝 𝑓𝑓 ≃ � 𝑓𝑓 𝑥𝑥 𝑖𝑖 𝑥𝑥 𝑖𝑖 ∼ 𝑞𝑞 𝑥𝑥
𝑛𝑛 𝑞𝑞 𝑥𝑥 𝑖𝑖
𝑖𝑖=1
𝑛𝑛
𝑝𝑝 𝑥𝑥 𝑖𝑖
1
Ε𝑝𝑝 𝑓𝑓 ≃ � 𝑓𝑓 𝑥𝑥 𝑖𝑖 𝑤𝑤(𝑥𝑥 𝑖𝑖 ) 𝑤𝑤(𝑥𝑥 𝑖𝑖 ) =
𝑛𝑛 𝑞𝑞 𝑥𝑥 𝑖𝑖
𝑖𝑖=1

40
Importance sampling
 Importance sampling depends on how well 𝑞𝑞 matches 𝑝𝑝.
 For mismatch distributions, weights may be dominated by few
samples having large weights, with the remaining weights
being relatively insignificant
 It is common that 𝑃𝑃(𝒙𝒙)𝑓𝑓(𝒙𝒙) is strongly varying and has a
significant proportion of its mass concentrated in a small
region
 The problem is more severe if none of the samples falls in the
regions where 𝑃𝑃(𝒙𝒙)𝑓𝑓(𝒙𝒙) is large.

41
Bishop Book
Problems of naïve Monte Carlo method
 Direct sampling: only when we can sample from 𝑝𝑝(𝑥𝑥)
 Wasteful for rare evidences

 Importance sampling: when the proposal 𝑞𝑞(𝑥𝑥) is very

different from 𝑝𝑝 𝑥𝑥 most samples have very low weights.
 In fact, finding a good proposal 𝑞𝑞(𝑥𝑥) that is similar to
𝑝𝑝 𝑥𝑥 usually requires knowledge of the analytic form of
𝑝𝑝 𝑥𝑥 that is not available

42
Markov chain Monte Carlo (MCMC)
 Using an adaptive distribution 𝑞𝑞(𝑥𝑥′|𝑥𝑥) instead of a fixed
distribution 𝑞𝑞 𝑥𝑥 , where 𝑥𝑥 is the last accepted sample
and 𝑥𝑥′ is the new sample.
 During sampling process the proposal distribution changes as a
function of previous sampled data

43 Bishop Book
Markov chain Monte Carlo (MCMC)
 Different methods
 Metropolis-Hastings
 Gibbs sampling

44
Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings
 Sample from 𝑞𝑞(𝑥𝑥 ′ |𝑥𝑥), where 𝑥𝑥 is the previous sample
 As 𝑥𝑥 changes, 𝑞𝑞 𝑥𝑥 ′ 𝑥𝑥 can also change
 Accept this new sample with following probability

′ ⁄ ′
′
𝑝𝑝 𝑥𝑥 𝑞𝑞(𝑥𝑥 |𝑥𝑥) importance
𝐴𝐴 𝑥𝑥 𝑥𝑥 = min(1, )
⁄
𝑝𝑝 𝑥𝑥 𝑞𝑞(𝑥𝑥|𝑥𝑥′)

 The acceptance rate 𝐴𝐴 𝑥𝑥 ′ 𝑥𝑥 guarantees that after sufficiently

many draws, samples are generated from the target
distribution 𝑝𝑝(𝑥𝑥)
 Burn-in samples: samples generated in initial iterations and are not
from 𝑝𝑝(𝑥𝑥)

45
Markov chain Monte Carlo (MCMC)
Metropolis-Hastings algorithm:
Initialize starting point: 𝑥𝑥 0 , set t=0
Repeat until convergence: Burn-in samples

Sample 𝑥𝑥 ∗ ∽ 𝑞𝑞 𝑥𝑥 ∗ 𝑥𝑥
′ ⁄𝑞𝑞(𝑥𝑥 ′ |𝑥𝑥)
𝑝𝑝 𝑥𝑥
𝐴𝐴 𝑥𝑥 ∗ 𝑥𝑥 = min(1, )
𝑝𝑝 𝑥𝑥 ⁄𝑞𝑞(𝑥𝑥|𝑥𝑥′)
Sample 𝑢𝑢 ∽ 𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢 (0,1)
If 𝑢𝑢 < 𝐴𝐴 𝑥𝑥 ∗ 𝑥𝑥 :
𝑥𝑥 𝑡𝑡+1 = 𝑥𝑥 ∗
Else:
𝑥𝑥 𝑡𝑡+1 = 𝑥𝑥 𝑡𝑡
Discard Burn-in samples

46
Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings example:
 The proposal distribution 𝑞𝑞(𝑥𝑥 ′ |𝑥𝑥) is a gaussian distribution
 The true distribution 𝑝𝑝(𝑥𝑥) is a bimodal with two peaks!

47 Jin Young Choi - SNU

Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings example:

48 Jin Young Choi - SNU

Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings example:

49 Jin Young Choi - SNU

Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings example:

50 Jin Young Choi - SNU

Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings example:

51 Jin Young Choi - SNU

Markov chain Monte Carlo (MCMC)
 Metropolis-Hastings example:

52 Jin Young Choi - SNU

Next topic
 Probabilistic graphical models
 Learning

53