Description
Lab 3 Hidden Markov Model
Suppose that a Mars rover is wandering in a region which is modeled as a grid of width 12 and height 8, as
shown in Fig 1. We do not know the exact location of the rover over time. Instead, we only get some noisy
observations about the rover from a sensor. In this lab, we use hidden Markov model to track the rover’s
movement over time.
The rover’s position at time i = 0, 1, 2, . . . is modeled as a random vector (xi
, yi) ∈ {0, 1, . . . , 11} ×
{0, 1, . . . , 7}. For example, (x2, y2) = (5, 4) means that at time step 2, the rover is in column 5, row 4
illustrated as a blue circle in Fig 1. The movement of the rover is quite predictable. At each time step, it
makes one of the five actions: it stays put, goes left, goes up, goes right, or goes down.
0 1 2 3 4 5 6 7 8 9 10 11
0
1
2
3
4
5
6
7
A
Figure 1: A wandering rover (blue circle) in a grid of width 12 and height 8.
The action of the rover at any time i depends on its previous action as well as its current location. Given
that the rover’s current location is not at the boundary of the grid, its action is simple: if the rover’s previous
action was a movement (left, up, right, or down), the rover moves in the same direction with probability 0.9
and stays put with probability 0.1; if the rover’s previous action was to stay, it stays again with probability
0.2, and moves with each direction (left, up, right, or down) with probability 0.2. The rover’s action can be
shown by a transition diagram in Fig. 2a.
In the case that the rover is on the boundary of the grid, the rover’s behavior should adjust such that it
will not go outside the region, and meanwhile the behavior should also be consistent with the non-boundary
case. For example, when the rover is in location A in Fig. 1, the rover cannot go higher. Therefore, there are
only four possible actions: it stays, goes left, goes right, or goes down. Based on its previous action, those
probabilities may need to be re-normalized such that they sum to 1. Specifically, if the rover’s previous action
was to go left, the rover moves in the same direction with probability 0.9 and stays put with probability 0.1;
if the rover’s previous action was to go up, it stays at A with probability 1 (due to re-normalization); if the
rover’s previous action was to stay, it stays again with probability 0.25, and moves with each direction (left,
right, or down) with probability 0.25 (due to re-normalization). The resulting transition diagram is depicted
in Fig. 2b.
Since the rover’s behavior at any time i depends on its previous action as well as its current location, we
model the rover’s hidden state zi at time i as a super variable that includes both the rover’s location (xi
, yi)
and its most recent action ai
, i.e., zi = ((xi
, yi), ai), where ai
is a random variable that takes the value from
1
left right
down
up
stay
0.2
0.2
0.2
0.2
0.2
0.1
0.1
0.9
0.1
0.1
0.9
0.9
0.9
(a) Transition diagram if the rover is not on the boundary
left right
down
up
stay
1/4
1/4
1/4
1/4
1
0.9
0.1
0.1
0.9
(b) Transition diagram if the rover is at A
Figure 2: Transition diagrams of rover’s behavior
{stay, left, up, right, down}. Pay attention that although we use subscript i in ai
, it actually represents the
action of the rover at time i − 1 (most recent action).
(a) Hidden state of the rover, blue circle indicates the current location (xi, yi), and the arrow indicates the most recent action ai.
(b) Observation (ˆxi, yˆi), whose value is taken
from one of the five possible locations (green
circles) with equal probability, given the true
location shown in the left figure.
Figure 3: Hidden state and observation.
We do not directly observe the rover’s hidden state zi = ((xi
, yi), ai) as shown in Fig. 3a. Instead, we have
access to a noisy sensor that puts a uniform distribution on the valid grid positions within one grid cell of the
rover’s current true position, as shown in Fig. 3b.
Note that when the rover is on the boundary, the possible
locations of the observation should adjust such that the observation is in the region. We do not directly
observe the rover’s action from the sensor, either. In words, at time i the observation is represented by
random variable (ˆxi
, yˆi) ∈ {0, 1, . . . , 11} × {0, 1, . . . , 7}, and (ˆxi
, yˆi) is uniformly distributed over the possible
locations determined by zi
.
Lastly, we assume that the rover’s initial position (x0, y0) is equally likely to be any of the grid locations,
and its initial action a0 is stay.
Download hmm.zip under Files/Labs/Lab2 Part2/ on Quercus and unzip the file. File rover.py contains
functions for generating the initial distribution, the transition probabilities given a current hidden state, and
the observation probabilities given a current hidden state. Thus you do not need to re-write these. File
2
test.txt contains the data for Question 1. File test missing.txt contains the data for Questions 2, 3, 4, and
5.
In both test.txt and test missing.txt, the first three columns correspond to the hidden states, and the last
two columns correspond to the observations.
To help you understand what the code does, we provide a visualization tool in inference.py, which can be
turned on by setting enable graphics to True.
Note that whether you use the visualization will not affect
the grading. When you run inference.py, three panes will pop up. The left pane shows the true state of the
rover, including location and the most recent action, represented by an arrow. The middle pane shows the
observed position of the rover, with red signifying the missing data.
The right pane shows the estimated
state of the rover as well as the marginal distribution by grey level. After you implement your inference
algorithms, the right pane will automatically show the results.
Please follow the questions below and complete the file inference.py. This is the only file you need to modify.
Questions
1. (a) Write down the formulas of the forward-backward algorithm to compute the marginal distribution
p(zi
|(ˆx0, yˆ0), . . . ,(ˆxN−1, yˆN−1)) for i = 0, 1, . . . , N − 1. The formulas include the initializations of
the forward and backward messages, the recursion relations of the messages, and the computation
of the marginal distribution based on the messages.
(b) Complete function forward backward in file inference.py to implement the forward-backward algorithm. Now use the data (ˆx0, yˆ0), . . . ,(ˆx99, yˆ99) in test.txt to determine the marginal distribution of
zi at time i = 99, i.e., p(z99|(ˆx0, yˆ0), . . . ,(ˆx99, yˆ99)). Only include states with non-zero probability
in your answer.
Sanity check: The marginal distribution of the state at time i = 1 is
p(z1|(ˆx0, yˆ0), . . . ,(ˆx99, yˆ99)) = (
0.5 if z1 = ((6, 5), down),
0.5 if z1 = ((6, 5),right).
(1)
2. Some of the observations were lost when they were transmitted from Mars to earth. Modify function
forward backward so that it can handle missing observations. In a list of observations, a missing observation is represented by None in inference.py. Now use the data in test missing.txt to determine the
marginal distribution at time i = 30, i.e., p(z30|(ˆx0, yˆ0), . . . ,(ˆx99, yˆ99)) with missing observations. Only
include states with non-zero probability in your answer.
Sanity check: The mode of this marginal distribution p(z30|(ˆx0, yˆ0), . . . ,(ˆx99, yˆ99)) should be ((6,7),right)
with probability 0.91304.
3. (a) Instead of computing the marginal distributions, we now seek the most likely sequence of the
states via the Viterbi algorithm. Write down the formulas of the Viterbi algorithm using zi and
(ˆxi
, yˆi), i = 0, . . . , N −1. The formulas include the initialization of the messages and the recursion
of the messages in the Viterbi algorithm.
(b) Complete the function Viterbi in file inference.py to implement the Viterbi algorithm. Your implementation should be able to handle missing observations. Use the data in test missing.txt to
determine the last 10 hidden states of the most likely sequence (i.e., i = 90, 91, 92, . . . , 99) based
on the MAP estimate obtained from the algorithm.
Sanity check: For the MAP sequence, the last 3 states, i.e., the states at i = 97, 98, 99 are:
((8,7),left), ((7,7),left), ((6,7),left).
4. Let z˜i
, i = 0, 1, . . . , 99 be the estimate obtained from Question 3 by Viterbi algorithm, which corresponds to the most probable sequence given the observations:
{z˜0, . . . , z˜99} = arg max
z0,…,z99
p(z0, . . . , z99|(ˆx0, yˆ0), . . . ,(ˆx99, yˆ99)). (2)
3
Let zˇi
, i = 0, 1, . . . , 99 be the set of the states obtained from Question 2 by forward-backward algorithm,
which are individually the most probable at each time step, corresponding to the maximization of the
marginal distribution in Question 2, i.e.,
zˇi = arg max
zi
p(zi
|(ˆx0, yˆ0), . . . ,(ˆx99, yˆ99)), i = 0, . . . , 99. (3)
To compare z˜i and zˇi
, we let z˙ i
, i = 0, 1, . . . , 99 be the true hidden states, and define the error
probabilities of z˜i and zˇi
, respectively, as
P˜
e = 1 −
P99
i=0 I(z˜i = z˙ i)
100
, (4)
Pˇ
e = 1 −
P99
i=0 I(zˇi = z˙ i)
100
, (5)
where I(·) is the indicator function, i.e., I(X) = 1, if X is true; otherwise I(X) = 0. Please compute
and compare P˜
e and Pˇ
e for the data in test missing.txt.
5. Although the states zˇi
, i = 0, 1, . . . , 99, obtained from (3), are individually the most probable states,
the sequence zˇ0, zˇ1, . . . , zˇ99 may not representant a valid sequence. By a valid sequence, we mean that
the rover can behave physically as the sequence zˇ0, zˇ1, . . . , zˇ99 as described by the Markov transition
diagram of Fig. 2. For example,
.
.
. (6)
zˇi = ((1,1),stay) (7)
zˇi+1 = ((1,1),left) (8)
.
.
. (9)
is not a valid sequence because the transition from state ((1,1),stay) at time step i to state ((1,1),left) at
time step i+ 1 is impossible according to the transition model. Please check zˇ0, zˇ1, . . . , zˇ99 in Question
4 to see whether or not it is a valid sequence. If not, please find a small segment zˇi
, zˇi+1 that violates
the transition model for some time step i.
We thank Prof. Greg Wornell of MIT in creating this lab.
4
