共计 12799 个字符，预计需要花费 32 分钟才能阅读完成。
CS 486
CS 486/686 Assignment 2
Winter 2022
(130 marks)
Blake VanBerlo
Due Date: 11:59 PM ET on Wednesday, March 2, 2022
Changes
- v1.1: in Q2 description, updated probability of unintended action to (1?γ)/3 – v1.2:
in Q2 description, updated example for robot transition probabilities
1
CS 486/686 Winter 2022 Assignment 2
Academic Integrity Statement
If your written submission on Learn does not include this academic integrity statement with
your signature (typed name), we will deduct 5 marks from your final assignment mark.
I declare the following statements to be true:
The work I submit here is entirely my own.
I have not shared and will not share any of my code with anyone at any point.
I have not posted and will not post my code on any public or private forum or website.
I have not discussed and will not discuss the contents of this assessment with anyone
at any point.
I have not posted and will not post the contents of this assessment and its solutions
on any public or private forum or website.
I will not search for assessment solutions online.
I am aware that misconduct related to assessments can result in significant penalties,
possibly including failure in the course and suspension. This is covered in Policy 71:
https://uwaterloo.ca/secretar…
Failure to accept the integrity policy will result in your assignment not being graded.
By typing or writing my full legal name below, I confirm that I have read and understood
the academic integrity statement above.
Blake VanBerlo 2022 v1.2 Page 2 of 11
CS 486/686 Winter 2022 Assignment 2
Instructions
Submit any written solutions in a file named writeup.pdf to the A2 Dropbox on Learn.
If your written submission on Learn does not contain one file named writeup.pdf, we
will deduct 5 marks from your final assignment mark.
Submit any code to Marmoset at https://marmoset.student.cs.u…
Grades for the programming component are determined by the unit tests in the“As-
signment 2 (Final)”project on Marmoset The“Assignment 2 (Weeks 1 & 2)”and
“Assignment 2 (Week 3)”projects contain ungraded public test suites meant to help
you debug, and they are only temporarily available.
No late assignment will be accepted. This assignment is to be done individually.
I strongly encourage you to complete your write-up in LaTeX, using this source file.
If you do, in your submission, please replace the author with your name and student
number. Please also remove the due date, the Instructions section, and the Learning
goals section. Thanks!
Lead TAs:
– Question 1: Kelechi Ogueji (kelechi.ogueji@uwaterloo.ca)
– Question 2: Steven Lawrence (steven.lawrence@uwaterloo.ca)
The TAs’office hours will be scheduled on MS Teams.
Learning goals
Inference in Bayesian Networks
Define factors. Manipulate factors using the operations restrict, sum out, multiply and
normalize.
Trace the execution of and implement the variable elimination algorithm for calculating
a prior or a posterior probability given a Bayesian network.
Inference in Hidden Markov Models
Construct a hidden Markov model given a complex scenario.
Perform filtering and smoothing by executing the forward-backward algorithm.
Blake VanBerlo 2022 v1.2 Page 3 of 11
CS 486/686 Winter 2022 Assignment 2 - Independence and Inference in Bayesian Networks
(30 marks) - Recall that random variables X and Y are conditionally independent, given a third
variable Z if and only if:
P (X|Y ∧ Z) = P (X|Z) (1)
P (Y |X ∧ Z) = P (Y |Z) (2)
P (X ∧ Y |Z) = P (X|Z)P (Y |Z) (3)
Show that Equation 3 follows from Equations 1 and 2. Justify each step of your proof.
Hint: you may find some of the probability rules from Lecture 6 to be useful.
Marking Scheme: (6 marks)
(4 marks) Correct proof
(2 marks) Each step is justified - Not all the random variables in a Bayesian networks are always required to answer a
probabilistic query. In fact, all variables that are not ancestors of query variables or
evidence variables are irrelevant to the query. Let Q = {Q1, . . . , Qm} be the set of
query variables and e = {e1, . . . , en} be the set of evidence variables. Prove that the
Variable Elimination Algorithm (VEA) returns the same distribution for some query
P (Q|E) if all irrelevant variables are pruned from the Bayesian network.
Hint: try a direct proof. Show that a particular ordering of hidden variable elimination
results in the same final distribution returned by the normalization operation.
Marking Scheme: (10 marks)
(8 marks) Correct proof
(2 marks) Proof is succinct and easy to understand - Below is a Bayesian network that appears in a recent review of uncertainties in Bayesian
networks with discrete variables Rohmer, (2020). The network is a probabilistic model
of brain cancer diagnosis. Note that the example is meant to be illustrative, as the
network is simple and the conditional probability tables are fictional. The random
Blake VanBerlo 2022 v1.2 Page 4 of 11
CS 486/686 Winter 2022 Assignment 2
variables are defined below:
Random Variable Definition
MC Metastatic cancer
B Brain tumour
CT CT scan is positive for brain tumour
SH Severe headache
ISC Increased serum calcium
C Patient falls into coma
Execute the Variable Elimination Algorithm to determine the probability that a pa-
tient has a brain tumour, given that their blood work shows an increased calcium
concentration, and they do not report having severe headaches. Eliminate variables
in reverse alphabetical order. For example, you would eliminate MC before ISC and
CT before C.
You may denote False as 0 and True as 1. First, define your factors and write them
in tabular format. For example, write a factor containing random variables A and B
as follows:
f1(A, B):
A B Value - 0 0.6
- 1 0.4
- 0 0.8
- 1 0.4
Write out each VEA operation, along with the factor that is produced by the operation.
For example, if you were to restrict f1(A,B) to A = 0, you would write:
?Blake VanBerlo 2022 v1.2 Page 5 of 11
CS 486/686 Winter 2022 Assignment 2
Restrict f1(A, B) to A=0 to produce f2(B).
f2(B):
B Value - 0.6
- 0.4
Hint: before you start executing VEA, apply what you proved in part (b) of this
question to simplify the problem.
Marking Scheme: (14 marks)
(4 marks) Initial factor definition
(6 marks) Correct VEA operations
(2 marks) Correct final answer
(2 marks) Correct formatting of factors and VEA operations
Blake VanBerlo 2022 v1.2 Page 6 of 11
CS 486/686 Winter 2022 Assignment 2 - Robot Localization as a Hidden Markov Model
(100 marks)
You will implement the forward backward algorithm to perform inference in a complex grid
environment. We will model the robot’s interactions with the environment as a hidden
Markov model (HMM). Given a description of the environment, you will implement the
transition and sensor probability distributions. You will also implement forward recursion,
backward recursion, and the Forward-Backward Algorithm (FBA). The goal is to apply FBA
to infer the robot’s location at some timestep, given a series of actions and observations.
2.1 The Robot Environment
Let’s consider a complex robot localization problem. This problem is similar to an example
in one of our course textbooks:“Artificial Intelligence: a Modern Approach”by Russell and
Norvig (see Figure 1). In the 3rd edition, check out section 15.3.2, page 582, Figure 15.7. In
the 4th edition, check out section 14.3.2, page 477, Figure 14.7.
Figure 1: The robot grid environment from“Artificial Intelligence: a Modern Approach”. The
robot is in state 31.
A robot is in a grid environment and it has a correct map of the environment. We will use
(y, x) or (row, column) to refer to each cell. y is the row value starting with y = 0 at the
top. x is the column value starting with x = 0 at the left.
The robot has four available actions: Up, Right, Down, and Left. Each action is intended
to move the robot by 1 cell in the corresponding direction. Unfortunately, the robot’s
navigational system is broken. When it executes an action, it will move in the intended
direction with probability γ. The robot moves in one of the other directions with probability
(1 ? γ)/3. For example, if γ = 0.85, and the robot executes the Right action, it will move
right with probability 0.85, left with probability 0.05, up with probability 0.05, and right
with probability 0.05. If the robot is in a cell adjacent to a wall and it moves in the direction
of that wall, it remains in the same location. As an example, consider the grid environment
in Figure 2: if the robot is in state 0 and tries to move right, then it transitions to state 1
with probability 0.85, state 7 with probability 0.05, and stays in state 0 with probability 0.1
(because moving left or up results in the robot remaining stationary).
Blake VanBerlo 2022 v1.2 Page 7 of 11
CS 486/686 Winter 2022 Assignment 2
(a) The current state (b) The robot’s belief of its current state
Figure 2: Visualization of a grid environment. Each empty cell is a possible location that the
robot can be in. The red cell denotes the current location of the robot. The grid environment with
the robot’s belief of its location overlaid onto each empty cell. The darker the green, the higher
the probability that the robot assigns to that cell.
The robot’s task is to determine its current location. To do this, the robot will make use
of four noisy sensors that report whether there is an inner or outer wall in each of the four
directions (up, right, left, down). At each time step, the robot receives a sensor reading,
which is an integer in {0, 1}. If we convert the integer to a 4-bit binary number, then each
bit gives the presence (bit 1) or absence (bit 0) of a wall in the up, right, down, and left
directions respectively. For example, the integer 9 corresponds to the binary number 1001.
The leftmost digit 1 indicates that there is a wall above the agent. The second digit 0 from
the left indicates that there is no wall to the right of the agent. The third digit 0 from the
left indicates that there is no wall below the agent. The rightmost digit 1 indicates that
there is a wall to the left of the agent.
Each sensor is noisy and flips the bit with a probability of 0 ≤ ? ≤ 1. The errors occur
independently for the four sensor directions. For instance, suppose that the correct sensor
reading is 1001 and the actual sensor reading is 1110. The sensors were correct in one
direction and incorrect in three directions. The probability of observing this sensor reading
is (1? ?)?3.
The robot starts at an unknown location. At time step 0, we will assume a uniform distri-
bution over all the empty cells.
We can model the robot’s situation as a HMM. Figure 3 gives a Bayesian network represent-
ing the scenatio. The states correspond to the location of the robot and the observations
Blake VanBerlo 2022 v1.2 Page 8 of 11
CS 486/686 Winter 2022 Assignment 2
correspond to the 4-bit sensor reading. Since the robot has the choice of selecting different
actions, the robot’s next state depends on the current state and the action taken during
the current timestep. So the transition probability distribution is P (Sk+1|Sk ∧ Ak). The
sensor probability distribution is P (Ok|Sk). Both can be specified given the above problem
description.
S0 S1 S2 St?2 St?1
A0 A1 A2 At?2
. . . . . .
. . .
. . .
O0 O1 O2 Ot?1 Ot?1
Figure 3: A Bayesian network representing the HMM for the robot localization problem with t
timesteps
2.2 Locating the Robot with FBA
You will implement the forward backward algorithm (FBA) to perform inference in the robot
environment introduced above.
We have provided four python files. Please read the detailed comments in the provided files
carefully. - env.py: Contains a base Environment class. Do not change this file.
- grid env.py: Contains a GridEnvironment class that extends the base Environment,
implementing the dynamics from the robot environment. You must
implement the create_trans_probs() and create_obs_probs()
methods in the GridEnvironment class. Do not change the
function signatures. Do not change anything else in this file! - fba.py: Contains empty functions for FBA operations. You will implement
all of the functions in this file. Do not change the function
signatures. - robot.py: Provides a demonstration of how to define a GridEnvironment object
and visualize the robot’s state and belief. Feel free to change this file
as you desire.
Blake VanBerlo 2022 v1.2 Page 9 of 11
CS 486/686 Winter 2022 Assignment 2
Please complete the following tasks. - Implement the empty functions in grid_env.py and fba.py. Zip and submit these
two files on Marmoset.
Marking Scheme: (90 marks)
Unit tests:
create_trans_probs
(1 public test + 4 secret tests) * 3 marks = 15 marks
create_obs_probs
(1 public test + 4 secret tests) * 3 marks = 15 marks
forward_recursion
(1 public test + 4 secret tests) * 4 marks = 20 marks
backward_recursion
(1 public test + 4 secret tests) * 5 marks = 25 marks
? fba
(1 public test + 4 secret tests) * 3 marks = 15 marks - Once you have implemented the functions, you can play with the robot environment.
In robot.py, we have provided some code to create the robot environment. Add the
code for running FBA, and then run the code to complete the following activities.
We highly recommend using the provided visualize_state() and visualize_belief()
functions to visualize the robot’s location and the robot’s beliefs.
(a) For each value of ? in {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8,
0.9, 1.0}, execute at least 10 trials of FBA, using a different random seed for each
trial number. So in total, you will execute at least 11 × 10 = 110 trials. In each
trial, the robot executes the following 10 actions: Right, Right, Up, Up, Up, Up,
Left, Right, Down, Right. Compute the robot’s belief distribution for its location
at the final timestep, k = 9. Use the environment from the textbook (Figure 1)
Setting the initial state to 31 and γ = 0.85.
Plot the maximum probability in the robot’s belief distribution, averaged across
each trial, against the value of ?. Your x-axis should be ? and your y-axis should
be the average of the maximum probability across the trials for each value of ?.
In no more than 4 sentences, explain what your experiment indicates about the
effect of the sensor noise (?) on the robot’s confidence in its location.
Marking Scheme: (5 marks)
(3 marks) Reasonably correct plot.
Blake VanBerlo 2022 v1.2 Page 10 of 11
CS 486/686 Winter 2022 Assignment 2
(2 marks) Reasonable conclusion based on the plot.
(b) For each value of γ in {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}, execute at least - trials of FBA, using a different random seed for each trial number. So in total,
you will execute at least 11 × 10 = 110 trials. In each trial, the robot executes
the following 10 actions: Right, Right, Up, Up, Up, Up, Left, Right, Down, Right.
Compute the robot’s belief distribution for its location at the final timestep, k = 4.
Use the environment from the textbook (Figure 1) Setting the initial state to 31
and ? = 0.2.
Plot the maximum probability in the robot’s belief distribution, averaged across
each trial, against the value of γ. Your x-axis should be γ and your y-axis should
be the average of the maximum probability across the trials for each value of γ.
In no more than 4 sentences, explain what your experiment indicates about the
effect of the action noise (γ) on the robot’s confidence in its location at timestep
k = 4.
Marking Scheme: (5 marks)
(3 marks) Reasonably correct plot.
(2 marks) Reasonable conclusion based on the plot.
正文完
