Machine Learning II BAI702
MODULE 5
[Link] a Hidden Markov Model (HMM). Apply the roles of transition probabilities, observation
probabilities, and initial state probabilities with example….10
The Hidden Markov Model is one of the most popular graphical models. It is used in speech
processing and in a lot of statistical work. The HMM generally works on a set of temporal
data. At each clock tick the system moves into a new state, which can be the same as the
previous one. Its power comes from the fact that it deals with situations where you have
a Markov model, but you do not know exactly which state of the Markov model you are
in—instead, you see observations that do not uniquely identify the state. This is where the
hidden in the title comes from. Performing inference on the HMM is not that computationally
expensive, which is a big improvement over the more general Bayesian network. The
applications that it is most commonly applied to are temporal: a set of measurements made
at regular time intervals, which comprise the observations of the state. In fact, the HMM is
the simplest dynamic Bayesian network, a Bayesian network that deals with sequential (often
time-series) data. Figure 16.6 shows the HMM as a graphical model.
The example that we will use is this: As a caring teacher I want to know whether or
not you are actually working towards the exam. I know from Chapter 12 that there are
four things that you do in the evenings (go to the pub, watch TV, go to a party, study)
and I want to work out whether or not you are studying. However, I can’t just ask you,
because you would probably lie to me. So all I can do is try to make observations about your
behaviour and appearance. Specifically, I can probably work out if you look tired, hungover,
scared, or fine. I want to use these observations to try to work out what you did last night.
The problem is that I don’t know why you look the way you do, but I can guess by assigning
probabilities to those things. So if you look hungover, then I might give probability 0.5 to
the guess that you went to the pub last night, 0.25 to the guess that you went to a party, 0.2
to watching TV, and 0.05 to studying. In fact, we will use these the other way round, using the probability
that you look hungover given what you did last night. These are known as
observation or emission probabilities.
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
[Link] the structure of a Bayesian [Link] is a probability distribution represented using a
BN? Illustrate with exam fever example…10
To start with, we will consider directed graphs, and make one restriction to them, namely
that they must not contain cycles, that is, there cannot be any loops in the graphs. These
graphs go by the rather unlovely name of DAGs: directed, acyclic graphs, but for graphical
models, when they are paired with the conditional probability tables, they are called
Bayesian networks. In order to see what we can do with such a network, we need an example.
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
Example: Exam Fear
Figure 16.2 shows a graph with a full set of distribution tables specified. It is a handy guide
to whether or not you will be scared before an exam based on whether or not the course was
boring (‘B’), which was the key factor you used to decide whether or not to attend lectures
(‘A’) and revise (‘R’). We can use it to perform inference in order to decide the likelihood
of you being scared before the exam (‘S’). There are two kinds of inferences, depending on
whether the observations that are made come from the top of the graph or the bottom. If
we have a set of observations that can be used to predict an unknown outcome, then we are
doing top-down inference or prediction, whereas if the outcome is known, but the causes are
hidden, then we are doing bottom-up inference or diagnosis. Either way, we are working out
the values of the hidden (unknown) nodes given information about the observed nodes. For
the example in Figure 16.2 we will start by predicting whether or not you will be scared
before the exam, so it is the outcome that is hidden.
In order to compute the probability of being scared, we need to compute P(b, r, a, s),
where the lower-case letters indicate particular values that the upper-case variables can
take. The wonderful thing about the graphical model is that we can read the conditional
probabilities from the graph—if there is no direct link, then variables are conditionally
independent given a node that is already included, so those variables are not needed. For
this reason, the computation we need for Figure 16.2 is:
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
If we know particular values for the three observable nodes, then we can plug them in
and work out the probability. In fact, the conditional independence gives us even more: if I
know both whether or not you attended lectures and whether or not you revised, then I don’t
need to know if the course was boring, since there is no direct connection between ‘B’ and
‘S’. Suppose that you didn’t attend lectures, but did revise. In that case, the probability
of you being scared can be read off the final distribution table as 0.8. The power of the
graphical model is when you don’t have full information. It is possible to marginalise over
any of those variables by summing up the values. So suppose that you know that the course
was boring, and want to work out how likely it is that you will be scared before the exam.
In that case you can ignore the P(b) terms, and just need to sum up the probabilities for r
and a using Equation (16.1):
The backwards inference, or diagnosis, can also be useful. Suppose that I see you looking
very scared outside the exam. You look vaguely familiar, but I’m not sure whether or not
you came to the lectures. I might want to work out why you are scared—was it because
you didn’t come to the lectures, or because you didn’t revise? To perform this calculation
I need to use Bayes’ rule to turn the conditional probabilities around, just as was done for
the Bayes’ classifier in Chapter 7. So the computations that I need are (where P(s) is the
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
normalising constant found by summing over all values of r, a, and b, i.e., Equation
[Link] the Forward Algorithm for computing the likelihood of an observation sequence in an HMM.
Explain each step clearly….10
every possible sequence of states to find out the most likely
one based on what I actually saw. Note that I have used O to denote the whole sequence of
observations that I made. In the same way, is an entire sequence of possible states (this
is a change in notation from the rest of the methods we have looked at, but it is consistent
with the way that other authors describe HMMs). This can be written as:
The r index here describes a possible sequence of states, so 1 is one sequence, 2
another, and so [Link]’ll consider this in a minute, but first we will use the Markov property
to write:
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
ssible sequences of hidden states. If there are N hidden states then there are NT possible
sequences, and for each one we have to compute a product of T probabilities. Not only will
these probabilities be incredibly small, but the computational cost of getting them will be
astronomical: O(NT T).
Fortunately, the Markov property comes to our rescue again. Since the probability of
each state only depends on the data at the current and previous timestep (o(t), !(t), !(t−1))
we can build up our computation of P(O) one timestep at a time. This is known as the
forward trellis by some people, since it looks like a garden trellis in Figure 16.8. To construct
the trellis we introduce a new variable
i(t) that describes the probability that at time t
the state is !i and that the first (t − 1) steps all matched the observations o(t):
to state j, so if there are N states, then it is of size N ×N; bi(o) is the transition probability
of emitting observation o in state i, so it is of size N ×O, where O is the number of different
observations that there are (four in the example). It will be useful to introduce four more
variables, all of which are probabilities that are conditioned on the observation sequence
and the model:
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
[Link] the Viterbi Algorithm. How does it differ from the Forward Algorithm? Illustrate with a
simple example….10
The next problem that we want to solve is the decoding problem of working out the hidden
states: I can use my model of how students are expected to behave and match them with my
observations to guess what you have been doing each evening. The algorithm is known as
the Viterbi algorithm after its creator, although he actually derived it for error correction, a
completely different application! We want to work out the i,t variable. This requires finding
the maximum probability of any path that gets us to state i at time t that has the right
observations for the sequence up to t; apart from being a maximisation instead of a sum, it
is pretty similar to the forward algorithm.
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
[Link] Kalman Filter Algorithm….10
The Kalman filter (named for E. Kalman; although he was not the original inventor he did
do quite a lot of work on it) is a recursive estimator. It makes an estimate of the next step,
then computes an error term based on the value that was actually produced in the next
step, and tries to correct it. It then uses both of those to make the next prediction, and
iterates this procedure. It can be seen as a simple cycle of predict-correct behaviour, where
the error at each step is used to improve the estimate at the next iteration. The Kalman
filter can be represented by the graphical model shown in Figure 16.10.
Much of the jargon that is associated with the Kalman filter is familiar to us: the state,
which is hidden, consists of the variables that we want to know, which we see through noisy
observations over time. There is a transition model that tells us how states change from one
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
to another, and an observation model (also called the sensor model here) that tells us how
states lead to observations.
The underlying idea is that there is some time-varying process that is generating a
set of noisy outputs, where there are two sources of noise: process noise, which represents
A representation of the Kalman filter with time derivatives (such as for
tracking) as a graphical model.
the fact that the process changes over time, but we don’t know how, and observation (or
measurement) noise, which is the errors that are made in the readings. Both are assumed to
be independent of each other, and zero mean Gaussians. We write the process as a stochastic
difference equation in x, which has n dimensions:
xt+1 = Axt + But + wt,
where At is an n×n matrix that represents the non-driven part of the underlying process,
B is an n × l matrix that represents the driving force, and u is the l-dimensional driving
force. w is the process noise, which is assumed to be zero mean with standard deviation Q.
The observations that we make are m-dimensional:
yt = Hxt + vt,
where m×n matrix H describes how measurements of the state are measured, and v is the
measurement noise, which is also assumed to be zero mean, but with standard deviation R.
As an example of this, consider a particle moving at a constant speed in one dimension.
The state is two dimensional, consisting of the position and velocity of the particle (so
x = [x, x˙ ]T ). Since there is no driving force the next term is But = 0. The process equation
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
is then derived by using Newton’s laws of motion (so xt+1 = xt + tx˙ t, and since we are
making indexing by time, t = 1, and the velocity is constant):
We can observe the position of the particle, up to measurement noise, but not the
velocity, and so the measurement equation is:
The principal simplifying assumptions of the Kalman filter are that the process is linear
and that all of the distributions are Gaussian with constant covariance. Since the convolution
of Gaussians is also Gaussian, this means that we can put them together to form new
Graphical Models 345
Gaussians, and so the model stays well behaved. This was a significant advantage over previous
methods of tracking, which tended to stop working fairly quickly, since the estimates
broke down because the probability distribution stopped being [Link] assume that
both the transition model and the observation model are Gaussians with means based on the
previous observations, and fixed covariances Q and R which can be written mathematically
as (with the same parameters as the state and measurement update equations):
P(xt+1|xt) = N(xt+1|Axt,Q)
P(zt|xt) = N(zt|Hxt,R).
Having described the set-up, what do we do? The basic idea is to make a prediction
and then correct it when the next observation is available, i.e., at the next timestep. We
will use ˆx and ˆy as the estimates, so ˆyt+1 = HAˆxt+1 and so the error is yt+1 − ˆyt+1;
that is the difference between what was actually observed and what we predicted (without
measurement noise). Since this is a probabilistic process with Gaussian distributions, we
can also keep a predicted covariance matrix that goes with it: ˆt+1 = AtAT +Q (which
is E[(xk − ˆxk)(xk − ˆxk)T ]). The Kalman filter weights these error computations by how
much trust the filter currently has in its predictions; these weights are known as the Kalman
gain and are computed by:
This equation comes from minimising the mean-square error; we will not derive it, but
the Further Reading section gives further references for you to follow up if you wish. Using
it, the update for the estimate is:
xt+1 = ˆxt+1 +Kt+1 (zt+1 −Hˆxt+1)
All that is then required is to update the covariance estimate:
t+1 = (I −Kt+1H)ˆt+1,
where I is the identity matrix of the relevant size. Putting these equations together leads
to a simple algorithm.
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
[Link] Particle Filter………………………..10
As well as the linearity of the function, the Kalman filter also assumes that the distributions
are Gaussian, so that they can be convolved and stay as Gaussians. In order to get around
this problem, we return to the methods that have underpinned many of the algorithms in
this chapter: sampling. The particular sampling technique that we will use is the samplingimportance-
resampling algorithm of Section 15.3, which forms the basis of the particle filter,
or condensation method. This is a relatively recent development, and has been finding many
successful applications in tracking, including in image and signal analysis. The idea is to
use sampling to keep track of the state of the probability distribution. This is known as
sequential sampling, since we are using a set of samples for time t to estimate the process at
time t + 1, and then resampling from there.
One benefit of sampling methods is that we don’t have to hold on to the Markov assumption.
In tracking, prior history can be useful, which means that the Markov assumption is
a bad one. The proposal distribution is generally written as q(xt+1|x0:t, y0:t) to make this
dependence clear, and the proposal distribution that is generally used in the estimated transition
probabilities p(ˆxt+1|x0:t, y01:t), since it is a simple distribution that is related to the
process. With this decided, there is very little else to the basic particle filter: a schematic
of one iteration of the particle filter is shown in Figure 16.16. The basic algorithm is given
next, followed by some points about the implementation and some examples.
Soumya L [Link] Professor,CSE(AI & ML)
Machine Learning II BAI702
A schematic of one iteration of a particle filter. A set of random particle
positioned have importance weights computed according to the distribution, and then new
particles are created and modified based on these weights, and the estimated distribution
is updated.
Soumya L [Link] Professor,CSE(AI & ML)