搜索

CS 486 解题想法


发布时间: 2022-11-24 18:44:00    浏览次数:30 次

分享时间:2022-11-24 18:44:00
数据来源:网络
提取密码:在线浏览
文件类型:文章

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.
免责声明 CS 486 解题想法,资源类别:文本, 浏览次数:30 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:44:00。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://segmentfault.com/a/1190000042895559