ML-II[BAI702] Module-5

What Are Graphical Models?

 Graphical Models (Probabilistic Graphical Models) combine statistics + graph
theory.
 They represent probability distributions using graphs.
 Very powerful tools used in many ML algorithms.
Types of Graphical Models
There are two main types:
1. Directed Graphical Models → Bayesian Networks
2. Undirected Graphical Models → Markov Random Fields (MRFs)
This chapter focuses mainly on directed graphs.
Components of a Graphical Model
Nodes
 Each node represents a random variable.
 Here, all variables are assumed discrete (continuous ones are discretised).
Links/Edges
 Represent dependencies.
 Directed edges indicate conditional relationships.
 If two nodes are connected: It indicates a dependency.
 If two nodes are not connected directly: It suggests conditional independence,
but only if there is no indirect path.
Figure 16.1:
Left: A → B
Represents dependence of B on A.
 Joint probability factorizes as:
 P(a,b) = P(b|a) P(a)
Figure 16.1:
Right: B ← A → C
 A is a common parent of B and C.
Meaning:

Dept. of AI, VCET Puttur 1

ML-II[BAI702] Module-5

 Both B and C depend on A

 B and C have no direct edge
Therefore,
 They are not fully independent
 But they become conditionally independent given A P(b,c|a) = P(b|a)P(c|a)
 This is the classic conditional independence pattern in Bayesian networks.
Conditional Probability Tables (CPTs)
 Every node must have a CPT.
 For nodes with parents → P(node | parents)
 For nodes without parents → P(node)
To compute joint probabilities like P(a, b) we use CPTs such as:
 P(a)
 P(b | a)

16.1 BAYESIAN NETWORKS

 A Bayesian Network (BN) is a directed acyclic graph (DAG) where:
 Nodes = random variables (discrete in this book).
 Directed edges = conditional dependence (not causal in the usual sense).
 A BN is a graph + a set of conditional probability tables (CPTs) for each node.
Links & Independence:
 If two nodes are not directly connected, they may still influence each other
through another node.
 Therefore, we talk about conditional independence:
 Example from Figure 16.1: C is conditionally independent of B given A.
 If A → B, the graph encodes the factorization:P(a,b)=P(b|a)P(a)

Dept. of AI, VCET Puttur 2

ML-II[BAI702] Module-5

CPTs (Conditional Probability Tables):

 Each node has a table that specifies: P(variable∣its parents)
 Some nodes may be observed, some hidden (latent).
16.1.1 Example: Exam Fear

Figure 16.2
The Bayesian network has four binary variables:
 B – Was the course Boring?
 R – Did you Revise?
 A – Did you Attend lectures?
 S – Will you be Scared before the exam?
Links (edges):
 B → R, B → A (Boring course influences whether you revise/attend)
 R → S, A → S (Both revision and attendance influence fear)
Each node has a conditional probability table (CPT).
Inference Types
There are two types:
1. Top-down inference (Prediction):
Observations are at the top of the graph; outcome is at the bottom.
Example: Predicting whether you will be scared.
2. Bottom-up inference (Diagnosis):
Observations are at the bottom; need to infer hidden causes.
Example: If you look scared, was it because you didn’t revise or didn’t attend?

Dept. of AI, VCET Puttur 3

ML-II[BAI702] Module-5

Computing the Probability of Being Scared

Goal is to compute:

Using the graph, this joint probability factors as:

So,

If some observations are known

Conditional independence allows simplification.
Example
You didn’t attend (A = F), but you did revise (R = T):
Then B becomes irrelevant, because S only depends on R and A.
From the CPT of S,
P(s|R=T, A=F)=0.8
If only B is known (course was boring)
Substitute values into Equation (16.1):

Backwards inference
Suppose you see the student scared and want to infer causes:
 Find probability student revised given they are scared:

Similarly for attendance:

Dept. of AI, VCET Puttur 4

ML-II[BAI702] Module-5

Complexity
The number of calculations grows quickly with more nodes:
 For N binary nodes, exact inference has cost O(2N).
 Hence, inference on Bayesian networks is NP-hard (actually #P-hard, an even
harder category).
However, for a polytree (where there is only one path between any two nodes),
computations are linear.
Variable elimination algorithm
This is sometimes known as the variable elimination algorithm, which is a variation
on the bucket elimination algorithm. The idea is to convert the conditional
probability tables into what are called λ tables, which simply list all of the possible
values for all variables, and which initially contain the conditional probabilities.
For example, the λ table for the ‘S’ variable in Figure 16.2 is:

Each variable (B, R, A, S) has its own table.

If I see you looking scared outside the exam (so that S is true), then I can eliminate
it from the graph by removing from each table all rows that have S false in them,
and deleting the S column. This simplifies things a little, but I have to do rather
more in order to compute the probability of you having attended lectures. I don’t
know whether you revised or not, and I don’t know if you found the lectures boring,
so I have to marginalise over these variables. The order in which we marginalise

Dept. of AI, VCET Puttur 5

ML-II[BAI702] Module-5

doesn’t change the correctness (although more advanced algorithms can improve
the speed by taking advantage of conditional independence) so we’ll pick R first. To
eliminate it from the graph, we have to find all of the λ tables that contain it (there
will be two of them containing R: the one for R itself and the one that we have just
modified to remove S). To remove R, we have to add together the products of the λ
values that correspond to places where the other values match. So to complete the
entry where B is true and A is false, we have to multiply together the values where
B, A, R are respectively true, false, true in the two tables and then add to that the
product of where B, A, R are respectively true, false, false. In other words:

Dept. of AI, VCET Puttur 6

ML-II[BAI702] Module-5

Compute Final Probability of Target Variable

For variable X (e.g., A):

From the final λ-table:

 Multiply entries with P(x=true) and P(x=false).
 Normalize.

Dept. of AI, VCET Puttur 7

ML-II[BAI702] Module-5

16.1.2 Approximate Inference

 You have already seen that exact inference in Bayesian networks is extremely
expensive.
 Variable elimination may require exponential time because real Bayesian
networks often contain many nodes and are not simple polytrees.
 Therefore, for any reasonably sized Bayesian network, exact inference becomes
impractical.
MCMC for Bayesian Networks
The main idea:
Approximate inference is done by sampling the hidden variables many times and
estimating probabilities using the sample frequencies.
Steps:
1. Sample values for hidden nodes
2. Compute probabilities or weights of samples
3. Repeat many times
4. Estimate posterior probabilities by frequencies
As number of samples increases, the estimates converge toward true probabilities.
How sampling works (Prediction case)
Using the example Bayesian network in Figure 16.2 (Exam Fear):
To generate a sample:
1. Sample B from P(b)
2. Sample R from P(r | b sample value)
3. Sample A from P(a | b sample value)
4. Sample S from P(s | r, a sample values)
This gives you one sample for (B, R, A, S). If you generate many such samples, the
frequency of “S = true” in your samples will approximate P(S = true). This is
basically forward sampling through the network.
Rejection Sampling
 This section that forward sampling requires selecting rows from CPTs based on
previously sampled values.
 But humans would often answer queries simply by counting matching cases
from their past experience.
➡ So this section introduces rejection sampling as an analogy:

Dept. of AI, VCET Puttur 8

ML-II[BAI702] Module-5

 Sample values for all variables independently.

 Reject any sample that contradicts known evidence.
 Keep only the samples that match the evidence.
This is simpler computationally but may require many samples if evidence is rare.
Likelihood Weighting
To avoid too many rejected samples:
 For any variable that we already have evidence for,
 We do not sample it,
 Instead, we weight the sample by the probability of that evidence.
Example:
If you sampled B = true, and you know that R = true (given as evidence),
You weight the sample by:
P(r = true | B = true) = 0.3
This keeps all samples but gives higher weight to those consistent with evidence.
Gibbs Sampling — Best MCMC for Bayesian Networks
This says:
“However, we can do rather better than this by using the full MCMC framework.”
This is where Gibbs sampling becomes the main technique.
Main idea:
1. Start with random assignments for all variables (or fixed assignments for
evidence variables)
2. Repeatedly resample one variable at a time, conditioned on:
 its parents
 its children
 the other parents of its children
This special set is called the Markov blanket.
Probability in Bayesian Networks

Dept. of AI, VCET Puttur 9

ML-II[BAI702] Module-5

FIGURE 16.4: To show the Markov blanket of a node in a Bayesian Network. This
figure shows:
 One central node (say X)
 Light grey nodes: parents and children of X
 Dark grey nodes: co-parents of its children (other parents of the child nodes)
 All nodes outside this set are unshaded (not relevant)
This forms a “blanket” around X.
Gibbs Sampling Algorithm
The textbook gives pseudocode for Gibbs sampling for the exam fear network:

For the example, a sample distribution (based on 500 samples, with 10 iterations of
each chain) is:

Dept. of AI, VCET Puttur 10

ML-II[BAI702] Module-5

Meaning:
 Randomly initialize B, R, A, S.
 Sweep through each variable (B then R then A then S).
 Update each variable using its conditional probability given its Markov blanket.
 After many iterations, the distribution converges.
At the end, sample frequencies for each possible combination of (b, r, a, s) is shown.
For example:
 (1,0,0,1) has probability 0.274
 (1,1,0,0) has probability 0.052
 etc.
This is the approximate inference solution.
16.1.3 Making Bayesian Networks
What the problem is
To use a Bayesian Network, you need two things:
1. Graph structure (which variable depends on which)
2. Conditional Probability Tables (CPTs)
But constructing the network itself—its structure and CPTs—is very difficult.
Why constructing Bayesian networks is hard

(i) Exact inference is already hard

 Earlier we learned that exact inference is NP-hard (actually #P-hard).
 Therefore searching for the best graph structure is even worse.
(ii) Huge number of possible graphs
 With N variables, the number of possible directed acyclic graphs (DAGs) is
enormous.
 Example:
 For just 3 variables (A, B, C) → already 7 possible graphs without even
considering all combinations.
 For 10 variables → about 10¹⁸ possible graphs.
 So we cannot search all possibilities.
(iii) Hidden (latent) variables worsen the problem
 Real networks usually include hidden nodes → search space grows much more.
How people try to construct networks
1. Usually: Experts draw the network by hand

Dept. of AI, VCET Puttur 11

ML-II[BAI702] Module-5

 Very common in practice.

 But:
 Time-consuming
 Subjective
 If the expert’s assumptions don’t match real data, inference is useless.
Automatic structure learning
1. Use search algorithms (hill climbing, etc.)
 Define an objective function to score graphs:
 Must balance:
 Good fit to data
 Simplicity (Occam’s Razor)
 Common scoring functions:
 MDL (Minimum Description Length)
 Other information-theoretic measures.
 Local search (hill climbing) is used because global search is impossible.
Why not genetic algorithms?
A GA would generate hundreds of graphs each iteration.
For each graph you must run inference → extremely expensive.
So GA becomes impractical.
A practical compromise
Instead of learning the full structure, you:
 Fix the graph structure (drawn by a domain expert)
 Use data to estimate the CPTs
This is still challenging but much more feasible.
Learning CPTs when all variables are observed
If there are no hidden nodes, compute parameters by maximum likelihood:

 Each CPT can be learned independently by:

 Counting frequencies of each combination

Dept. of AI, VCET Puttur 12

ML-II[BAI702] Module-5

 Normalizing them into probabilities

Issue
 With small datasets, some combinations may not appear → probability = 0.
 Fix: Add priors and apply Bayes’ rule.
Learning CPTs with hidden nodes
 When hidden variables exist, the previous method fails because their values are
unknown.
Solution: EM Algorithm
 Use inference to estimate hidden node values.
 Then maximize likelihood to update parameters.
 Repeat until convergence.
This is exactly the Expectation–Maximization (EM) method
Note:
 Building a Bayesian Network structure is extremely hard.
 Search space is enormous, and inference itself is NP-hard.
 Practical approach:
 Experts design the graph manually
 Data is used to learn CPTs
 If hidden variables exist → apply EM algorithm (Expectation-
Maximization).
16.2 MARKOV RANDOM FIELDS(MRFs)
 An MRF is an undirected graphical model (unlike Bayesian networks which
have directed edges).
 Bayesian networks use directed edges and thus have asymmetry (parent →
child).
 If we remove arrows, we get an undirected graphical model, called a Markov
Random Field (MRF).
 In an MRF, conditional independence is simpler:
 Two nodes are conditionally independent given a third node if every path
between them passes through that third node.
 The name comes from the Markov property:
 The state of a node depends only on the states of its immediate neighbours.
Use of MRFs

Dept. of AI, VCET Puttur 13

ML-II[BAI702] Module-5

 Useful especially in image processing, because nearby pixels tend to be

correlated.
 Inference is still #P-hard, so not computationally trivial.
Example: Image Denoising using an MRF
Setup
We have:
 A noisy binary image I with pixels in {–1, 1}
 An ideal underlying image I′ that we want to recover
 that we want to recover
Two assumptions:
1. Each pixel Ixi,xj is correlated with the true pixel I′ xi,xj
2. Each pixel is correlated with its neighbours (up, down, left, right, etc.).
These assumptions match an MRF:
Pixels depend only on neighbours → distant pixels are conditionally independent
given neighbours.
Energy Function
Physicists use an energy formulation (from the Ising model):

 First term: encourages neighbouring pixels to have similar values

 Second term: encourages the denoised pixel to match the ideal image
 Lower energy = better image
MRF Image Denoising Algorithm
For each pixel in I:
1. Compute the energy if the pixel = –1
2. Compute the energy if the pixel = +1
3. Choose the value that gives lower energy
4. Move to the next pixel
5. Repeat until values stop changing

Dept. of AI, VCET Puttur 14

ML-II[BAI702] Module-5

Figure 16.5
 Top-left: original map
 Top-right: 10% noisy version
 Bottom: denoised image using MRF with parameters η=2.1,ζ=1.5
 Error reduces from 10% → <1%, though fine edges get smoothed.

Dept. of AI, VCET Puttur 15

ML-II[BAI702] Module-5

Note:
 MRFs use undirected edges, unlike Bayesian networks.
 Conditional independence in MRFs:
→ A node depends only on its neighbours (Markov property).
 Widely used for image denoising and spatial modeling.
 The classic example uses an energy minimization framework.
 Inference in general MRFs remains computationally hard.
16.3 HIDDEN MARKOV MODELS (HMMS)
A Hidden Markov Model (HMM) is a dynamic Bayesian network used for sequential
(time-series) data where the true states are hidden, but we receive observations
related to those states.
Figure 16.6 shows the model “unrolled in time”: each hidden state produces an
observation, and each state depends only on the previous state (Markov property).

Key Components of an HMM

An HMM contains:
1. Hidden States
Examples here: TV, Pub, Party, Study.
At each time step t, the true state is ω(t).
2. Observations
What you actually see: tired, hungover, scared, fine.
At each time step t, you observe o(t).
3. Transition Probabilities
Probability of going from state i to state j:

Each row sums to 1.

Shown in Figure 16.7.

Dept. of AI, VCET Puttur 16

ML-II[BAI702] Module-5

4. Emission (Observation) Probabilities

Probability of observing symbol ok when in state j:
Bj(ok) = P(ok | ωj)

5. Initial State Probabilities

πi​ = P(ωi(0))
These three sets (π, a, b) define an HMM.
Assumption:
The Markov chain is ergodic (all states can eventually reach all other states).
Example
 Hidden states (what the student did last night): TV, Pub, Party, Study.
 Observations (how the student looks in class): Tired, Hungover, Scared, Fine.
Given:
Transition probability table (Fig. 16.7)
Observation probability table (Fig. 16.7)
Goal:
Infer what the student has been doing on previous nights based on their
appearance.

Dept. of AI, VCET Puttur 17

ML-II[BAI702] Module-5

Evaluation Problem — How likely is the observation sequence?

Given a sequence such as: (tired, scared, fine, hungover,etc…)
 Compute: P(O) = probability that the HMM generated these observations
 Naively, this requires summing over all possible state sequences (exponential:
NT)
 To avoid this, we use the:
1. Forward Algorithm
2. Viterbi Algorithm
3. Baum–Welch (Forward–Backward) Algorithm
16.3.1 The Forward Algorithm
We are given an HMM defined by:
 Hidden states: ω₁, ω₂, …, ω_N
 Observations: o(1), o(2), …, o(T)
 Transition probabilities: aᵢⱼ = P(ωⱼ(t) | ωᵢ(t–1))
 Observation/emission probabilities: bⱼ(oₖ ) = P(observation oₖ | state ωⱼ)
 Initial state probabilities: πᵢ = P(state starts at ωᵢ)
 The goal of the forward algorithm is:
➜ Compute P(O), the probability that the given sequence of observations O is
generated by the HMM.
Need for the Forward Algorithm
Brute force method:

 Ωᵣ is a possible state sequence

 If there are N hidden states and T time steps, the number of state sequences is
Nᵀ

Dept. of AI, VCET Puttur 18

ML-II[BAI702] Module-5

 This is exponential & infeasible

 Therefore, we need a dynamic programming method → the Forward Algorithm.
 This is exponential & infeasible
Therefore, we need a dynamic programming method → the Forward Algorithm.

Core idea
The Markov property says:
 The probability at time t depends only on time t–1, not earlier times.
 So instead of summing over all full paths, we build probability step-by-step
using a forward trellis.
Define the Forward Variable α

Interpretation:
Probability of seeing the first t observations AND ending up in state j at time t.
Forward Algorithm Steps
Step 1: Initialise
 At time t=0:

This uses:
 initial state probability πᵢ
 emission probability of the first observation
Step 2: Induction (Recursion)

Dept. of AI, VCET Puttur 19

ML-II[BAI702] Module-5

 For time t = 1 … T,

Step 3: Termination
Total probability of the observation sequence:

Dept. of AI, VCET Puttur 20

ML-II[BAI702] Module-5

Computational Complexity
 Forward Algorithm:

 Brute-force method:

→ Drastic improvement.
16.3.2 The Viterbi Algorithm
 The Viterbi algorithm solves the decoding problem in a Hidden Markov Model
(HMM): Given an observation sequence, what is the single most likely sequence
of hidden states that produced it?
 It finds the path with maximum probability, unlike the forward algorithm,
which sums probabilities over all paths.
Main Idea
For each time step t and state i, compute:
 δᵢ(t) – the highest probability of any path that ends in state i at time t
 φᵢ(t) – a pointer storing which previous state gave that maximum
These values form the Viterbi trellis, illustrated in Figure 16.9 (which shows the
best-scoring transitions for the first three observations).

Initialization
For the first observation o0:

Dept. of AI, VCET Puttur 21

ML-II[BAI702] Module-5

Recursion
For each time step and state:

This step builds the trellis as shown in Figure 16.9.

Termination
The most likely final state:
qT* = arg maxᵢ δi(T)
Backtracking
Recover the most likely hidden path:

This backtracking follows the arrows in the Viterbi trellis of Figure 16.9.

Note:
 The Viterbi algorithm is very similar to the forward algorithm, except:
 Forward algorithm sums probabilities.
 Viterbi takes the maximum.
 It gives the single best explanation of the observations.

Dept. of AI, VCET Puttur 22

ML-II[BAI702] Module-5

 In the example, even the best path had a very small probability (~10-9), which is
normal because probabilities multiply and shrink quickly.
16.3.3 The Baum–Welch or Forward–Backward Algorithm
The Baum–Welch algorithm is an EM (Expectation–Maximization) method used to
learn the parameters of a Hidden Markov Model (HMM) when only the observation
sequences are available.
It estimates the three sets of HMM parameters:
 πi = initial state probabilities
 ai,j = transition probabilities between states
 bj(ok) = observation (emission) probabilities
It is called Forward–Backward because it uses both forward probabilities (α) and
backward probabilities (β).
Note:
α: Alpha
β: Beta
Goal
Given only observations, learn the best values of:
 π (initial state distribution)
 A (transition matrix)
 B (emission matrix)
This is an unsupervised learning problem.
Key Idea
1. E-step:
 Estimate the expected counts of transitions and state occupancies using α
(forward) and β (backward).
2. M-step:
 Re-estimate π, A, B using these expected counts.
This iterative process improves model likelihood until convergence.

Important quantities
1. Forward probability αi,t
Probability of generating observations up to time t and being in state i.

Dept. of AI, VCET Puttur 23

ML-II[BAI702] Module-5

2. Backward probability βi,t

Probability of generating observations from t+1 to T, given state i at time t.
3. ξi,j,t (MOST important quantity)
Probability of being in state i at time t and j at time t+1:

The denominator is a normalizing constant.

Parameter Re-estimation Formulas

Initial state probabilities:

Transition probabilities:

Observation (emission) probabilities:

Numerator uses only those times where observation was ok.

Note:

 The algorithm may not find a global optimum, but works well in practice.
 Probabilities can become extremely small → scaling (normalization) is used
(variable c).

Dept. of AI, VCET Puttur 24

ML-II[BAI702] Module-5

Intuition
 α runs forward from the beginning of the sequence.
 β runs backward from the end.
 Combining α and β at each position gives expected state transitions.
 These expected counts are used to recompute HMM probabilities.
 Iteration increases the likelihood of the observed data.

Python implementation:

Dept. of AI, VCET Puttur 25

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 26

ML-II[BAI702] Module-5

We can’t really use this algorithm very well on the simple example, since we would
need rather more data to do justice to the training. However, if we do apply it and
then compute the Viterbi path, then it gives the same answer as with the invented
data.
One final thing to mention with the HMM is that there are ways to deal with
the fact that the probabilities get so small, which can cause round-off errors inside
the computer. One approach is to renormalise the α values by dividing by the sum
of the α values for each time step. If the same values are used in the β calculation as
well, then they cancel out beautifully in the final calculations and things work very
well. This is the c variable in the following code for the forward algorithm:

16.4 TRACKING METHODS

Tracking means keeping track of where something is and how it moves over time.
Humans and animals naturally do this—e.g., watching a predator’s movement.
Machines also need to track objects (radar, robots, navigation, etc.).
In machine learning and graphical models, tracking is used to continuously update
and predict a changing probability distribution.
There are two major tracking methods:
1. Kalman Filter
 Used when the system is linear and the noise is Gaussian.
 Works in a predict–correct cycle:

Dept. of AI, VCET Puttur 27

ML-II[BAI702] Module-5

 Predict the next state (position/velocity, etc.).

 Observe the actual noisy measurement.
 Correct the estimate based on the difference.
 Very efficient and widely used in tracking moving objects, robotics, navigation,
etc.
2. Particle Filter
 Used when the system is non-linear or when noise is not Gaussian.
 Represents the state with many random samples (particles).
 Each particle predicts a possible next state.
 Particles are weighted based on how well they match the new observation.
 Particles with higher weight survive; others are removed (resampling).
 Good for complicated tracking problems where the Kalman filter fails.

16.4.1 The Kalman Filter

The Kalman filter is a recursive estimator used for tracking and state estimation. It
repeatedly performs:
1. Predict
Estimate the next state using the system’s dynamics.
2. Correct (Update)
Compare the prediction to the actual noisy measurement, compute the error, and
adjust the estimate.
This predict–correct cycle repeats at every time step.

Dept. of AI, VCET Puttur 28

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 29

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 30

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 31

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 32

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 33

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 34

ML-II[BAI702] Module-5

16.4.2 The Particle Filter

Dept. of AI, VCET Puttur 35

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 36

ML-II[BAI702] Module-5

Dept. of AI, VCET Puttur 37

ML-II[BAI702] Module-5

Note:

For detailed explanation, refer the text book.

Dept. of AI, VCET Puttur 38