Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Written HW 7: CS 188 Fall 2018 Introduction To Artificial Intelligence

    Uploaded by

    arkaprava paul
    This document is a homework assignment for CS 188 Introduction to Artificial Intelligence at UC Berkeley in Fall 2018. It includes questions on variable elimination in Bayes nets and sampling methods like Gibbs sampling and likelihood-weighted sampling. Students are instructed to complete the questions, then complete a self-assessment of their original answers on a second submission.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Written HW 7: CS 188 Fall 2018 Introduction To Artificial Intelligence

    Uploaded by

    arkaprava paul
    31 views6 pages
    This document is a homework assignment for CS 188 Introduction to Artificial Intelligence at UC Berkeley in Fall 2018. It includes questions on variable elimination in Bayes nets and sampling methods like Gibbs sampling and likelihood-weighted sampling. Students are instructed to complete the questions, then complete a self-assessment of their original answers on a second submission.

    Original Description:

    Original Title

    CS_188_Fall_2018_Written_HW7.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is a homework assignment for CS 188 Introduction to Artificial Intelligence at UC Berkeley in Fall 2018. It includes questions on variable elimination in Bayes nets and sampling methods like Gibbs sampling and likelihood-weighted sampling. Students are instructed to complete the questions, then complete a self-assessment of their original answers on a second submission.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    31 views6 pages

    Written HW 7: CS 188 Fall 2018 Introduction To Artificial Intelligence

    Uploaded by

    arkaprava paul
    This document is a homework assignment for CS 188 Introduction to Artificial Intelligence at UC Berkeley in Fall 2018. It includes questions on variable elimination in Bayes nets and sampling methods like Gibbs sampling and likelihood-weighted sampling. Students are instructed to complete the questions, then complete a self-assessment of their original answers on a second submission.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 6

    CS 188 Introduction to

    Fall 2018 Artificial Intelligence Written HW 7


    Due: Monday 10/22/2018 at 11:59pm (submit via Gradescope).
    Leave self assessment boxes blank for this due date.
    Self assessment due: Monday 10/29/2018 at 11:59pm (submit via Gradescope)
    For the self assessment, fill in the self assessment boxes in your original submission (you can
    download a PDF copy of your submission from Gradescope – be sure to delete any extra title pages
    that Gradescope attaches). For each subpart where your original answer was correct, write “correct.”
    Otherwise, write and explain the correct answer. Do not leave any boxes empty.
    If you did not submit the homework (or skipped some questions) but wish to receive credit for the self-
    assessment, we ask that you first complete the homework without looking at the solutions, and then
    perform the self assessment afterwards.
    Policy: Can be solved in groups (acknowledge collaborators) but must be written up individually
    Submission: Your submission should be a PDF that matches this template. Each page of the PDF should
    align with the corresponding page of the template (page 1 has name/collaborators, question 1 begins on page
    2, etc.). Do not reorder, split, combine, or add extra pages. The intention is that you print out the
    template, write on the page in pen/pencil, and then scan or take pictures of the pages to make your submission.
    You may also fill out this template digitally (e.g. using a tablet.)

    First name

    Last name

    SID

    Collaborators

    1
    Q1. Variable Elimination
    (a) For the Bayes’ net below, we are given the query P (A, E | +c). All variables have binary domains. Assume we
    run variable elimination to compute the answer to this query, with the following variable elimination ordering:
    B, D, G, F .

    Complete the following description of the factors generated in this process:


    After inserting evidence, we have the following factors to start out with:

    P (A), P (B|A), P (+c), P (D|A, B, +c), P (E|D), P (F |D), P (G| + c, F )

    When eliminating B we generate a new factor f1 as follows:


    X
    f1 (A, +c, D) = P (b|A)P (D|A, b, +c)
    b

    This leaves us with the factors:

    P (A), P (+c), P (E|D), P (F |D), P (G| + c, F ), f1 (A, +c, D)

    When eliminating D we generate a new factor f2 as follows:

    This leaves us with the factors:

    When eliminating G we generate a new factor f3 as follows:

    This leaves us with the factors:

    2
    When eliminating F we generate a new factor f4 as follows:

    This leaves us with the factors:

    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    (b) Write a formula to compute P (A, E | +c) from the remaining factors.

    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    3
    (c) Among f1 , f2 , f3 , f4 , which is the largest factor generated, and how large is it? Assume all variables have binary
    domains and measure the size of each factor by the number of rows in the table that would represent the factor.

    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    (d) Find a variable elimination ordering for the same query, i.e., for P (A, E | +c), for which the maximum size
    factor generated along the way is smallest. Hint: the maximum size factor generated in your solution should
    have only 2 variables, for a size of 22 = 4 table. Fill in the variable elimination ordering and the factors
    generated into the table below.

    Variable Eliminated Factor Generated

    For example, in the naive ordering we used earlier, the first row in this table would have had the following two
    entries: B, f1 (A, +c, D).
    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    4
    Q2. Bayes Nets: Sampling
    Consider the following Bayes Net, where we have observed that B = +b and D = +d.

    P (D|A, C)
    +a +c +d 0.6
    P (B|A) P (C|B) +a +c −d 0.4
    P (A) +a +b 0.8 +b +c 0.1 +a −c +d 0.1
    A B C D +a 0.5 +a −b 0.2 +b −c 0.9 +a −c −d 0.9
    −a 0.5 −a +b 0.4 −b +c 0.7 −a +c +d 0.2
    −a −b 0.6 −b −c 0.3 −a +c −d 0.8
    −a −c +d 0.5
    −a −c −d 0.5

    (a) Consider doing Gibbs sampling for this example. Assume that we have initialized all variables to the values
    +a, +b, +c, +d. We then unassign the variable C, such that we have A = +a, B = +b, C = ?, D = +d.
    Calculate the probabilities for new values of C at this stage of the Gibbs sampling procedure.

    P (C = +c at the next step of Gibbs sampling) =

    P (C = −c at the next step of Gibbs sampling) =

    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    (b) Consider a sampling scheme that is a hybrid of rejection sampling and likelihood-weighted sampling. Under
    this scheme, we first perform rejection sampling for the variables A and B. We then take the sampled values for
    A and B and extend the sample to include values for variables C and D, using likelihood-weighted sampling.
    (i) Below is a list of candidate samples. Mark the samples that would be rejected by the rejection sampling
    portion of the hybrid scheme.
    2 −a −b
    2 +a +b
    2 +a −b
    2 −a +b

    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    5
    (ii) To decouple from part (i), you now receive a new set of samples shown below. Fill in the weights for these
    samples under our hybrid scheme.
    Weight

    −a +b −c +d

    +a +b −c +d

    +a +b −c +d

    −a +b +c +d

    +a +b +c +d

    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    (iii) Use the weighted samples from part (ii) to calculate an estimate for P (+a| + b, +d).

    The estimate of P (+a| + b, +d) is


    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    (c) We now attempt to design an alternative hybrid sampling scheme that combines elements of likelihood-weighted
    and rejection sampling. For each proposed scheme, indicate whether it is valid, i.e. whether the weighted samples
    it produces correctly approximate the distribution P (A, C| + b, +d).
    (i) First collect a likelihood-weighted sample for the variables A and B. Then switch to rejection sampling for
    the variables C and D. In case of rejection, the values of A and B and the sample weight are thrown
    away. Sampling then restarts from node A.
    # Valid # Invalid
    (ii) First collect a likelihood-weighted sample for the variables A and B. Then switch to rejection sampling for
    the variables C and D. In case of rejection, the values of A and B and the sample weight are retained.
    Sampling then restarts from node C.
    # Valid # Invalid
    Self assessment If correct, write “correct” in the box. Otherwise, write and explain the correct answer.

    You might also like