ASSIGNMENT 4: MONTE    CARLO    INFERENCE    

CS5340 ASSIGNMENT 4:
MONTE    CARLO    INFERENCE    
1. OVERVIEW
In    this    assignment,    you    will    write    code    to    perform    Monte    Carlo    inference    i.e.    Importance    sampling    
and    Gibbs    sampling. Often,    marginalization    over    large/continuous    probability    distributions    can    
be    intractable.    In    Monte    Carlo    inference,    we    circumvent    this    problem    by    sampling    from    simpler    
proposal    distributions    to    approximate    our    target    distribution,    making    the    problem    much more    
tractable    for    complex    distributions.
References: Lecture    9
Honour    Code.                This    coding    assignment    constitutes    15%    of    your    final    grade    in    CS5340.    Note    that    
plagiarism    will    not    be    condoned!    You    may    discuss    with    your    classmates    and    check    the    internet    
for    references,    but    you    MUST    NOT    submit    code/report    that    is    copied    directly    from    other    sources!
2. SUBMISSION    INSTRUCTIONS
Items    to    be    submitted:
• Source    code (zip    file    containing folders    part1    and    part2):
o part1/main.py– code    for    importance    sampling.
o part2/main.py    – code for    Gibbs    sampling.
• Report    (report.pdf). This    should    describe    your    implementation    and    be    no    more    than    one    
page.
Please    indicate    clearly    your    name    and    student    number    (the    one    that    looks    like    A1234567X)    in    the    
report     as     well     as     the     top     of     your     source     code.     Zip     the     two     files     together     and     name     it     in     the    
following    format:    A1234567X_lab4.zip    (replace    with    your    student    number).
Submit    your    assignment    by    12 November    2023,    2359HRS to    LumiNUS.    25%    of    the    total    score    
will    be    deducted    for    each    day    of    late    submission.
3. GETTING    STARTED
This    assignment    as    well    as     the    subsequent    ones    require    Python    3.5,    or    later. You    need    certain    
python    packages,    which    can    be    installed    using    the    following    command:
 pip install -r requirements.txt
If    you    have    any    issues    with    the    installation,    please    post    them    in    the    forum,    so    that    other    students    
or    the    instructors    can    help    accordingly.
CS5340    Assignment 4 (Semester    1,    AY2023/2024) 2
4. TEST    CASES
To    help    with    your    implementation,    we    have    provided    a    few    sample    inputs.    They    can    be    found    in    
the     data/inputs folder.     The     ground-truth     files     can     be     found     in     data/ground-truth. Your    
predictions    will    be    stored    in    data/predictions. For    test    cases 1    and    2,    the    inputs    will    be    on    the    
example    given    in    Lecture    9:
For     case     3,     we     will     use     a     slightly     larger     graph.    Note     that     the     ground-truth     might     be     slightly    
different    from    your    answers. We    will    assume    a    tolerance    up    to    1    decimal    place. During    grading,    
your     code will     be     evaluated     on    hidden     test     cases on     top     of     the     validation     test     cases we     have    
provided.
Additionally,    we    expect    your    code    to    run    in    a    reasonable    amount    of    time,    any    time within    2-3x    of    
our    timings    below    is    reasonable:
Case 1 2 3
Importance    Sampling 13s 4s 37s
Gibbs    Sampling 12s 2s 39s
Table    1:    Timings    on    i7-6500U    @    2.50GHz.
For    fairness,    we    will    evaluate    your    timings    on    the    same    system.
5. IMPORTANCE    SAMPLING
In    part    1    i.e.    importance    sampling,    you    will    be    provided    with    local    target    conditional    distribution    
�!"�!|�"!% and     local     proposal     conditional     probabilities     i.e.     �!(�!|�"!) where     �! is     are     the    
parents    of    node    �.    In    this assignment,    we    will    assume    our    proposal    distribution    has    the    form    i.e.    
�(�) = ∏ �!"�!.�"!% and     the     target     distribution     has     the     form     �(�) = ∏�!"�!.�"!% .     Each    
sample    is    then    weighted    by    the    ratio    between    #(%)
'(%) to    obtain    the    approximate    distribution. You    are    
CS5340    Assignment 4 (Semester    1,    AY2023/2024) 3
expected     to     return     the     conditional     probability     distribution    �(�(|�)) where     the     nodes     in     the    
graph    are    � = �( ∪ �),    with    �( being    the    query    nodes    and    �) being    the    evidence    nodes.    
Note    that    during    sampling,    students    are    expected    to    perform    sampling    in    a    topological    order    i.e.    
parent    nodes    should    be    sampled    before    child    nodes,    and    the    input    samples    should    be    updated    
with    the    parent    samples    before    sampling    from    the    child    node.
You    will    implement    the    following    functions:
• Performs    sampling    for    a    single    iteration (all    nodes    sampled    once):    _sample_step()[3
points]
o Students    are    expected     to    sample     from     the    local    proposal    distributions     for    each    
node.    Do    not    sample    from    a    joint    proposal    distribution.
o Sampling    should    be    done    in    topological    order.    For    example,    in    the    example    from    
Lecture     9,     sampling     in     the     order    �*, �+, �,, �-, �. would     be     one     way     to     sample    
topologically.
o Once     the     parent     node    is     sampled,     use     the     sample     from     the     parent     node    as     the    
observation    of    the    parent    into    the    child    node’s    probability    distribution.
• Performs     sampling     for    � iterations,     weight     the     samples     and     return     the     approximate    
conditional    probability �(�(|�)):    _get_conditional_probability()[4 points]
o Do    not    compute    the    joint    proposal    distribution    or    joint    target    distribution    to    get    
�(�(|�)) and    �(�(|�)).     You     are     expected     to     take     the     output     these     values     by    
taking    the    scalar    product    of    the    local    proposal/conditional    distribution    values.    
Note    that    we    will    also    provide    evidence    variables,    and    the    graph    structure    must be    updated    with    
the    evidence    variables.    
Hint:    It    might    be    useful    to    create    additional    functions    for    this    part.    Place    these    functions    between    
the    designated    comment    blocks    for    each    file.    
6. GIBBS    SAMPLING
In    part    2    i.e.    Gibbs    sampling,    you    will    be    provided    with    conditional    probabilities    i.e.    �!(�!|� −
{�!}) for     each     node    �! .     You    will     sample     from     the     conditional     distributions     for     each     node,     by    
holding     other    nodes     fixed.     The     samples     are    then     weighted     equally     to    obtain    the     approximate    
distribution �(�(|�)) where    �( are    the    query    nodes    and    �) are    the    evidence    nodes.    
• Performs    sampling    for    a    single    iteration (all    nodes    sampled    once):    _sample_step()[3
points]
o Sampling    should    be    done    like Lecture    9’s    example    on    Gibbs    sampling.
• Performs     sampling     for     � iterations,     and     return     the     approximate     distribution    
_get_conditional_probability()[5 points]
o Students    are    expected     to    reduce     the    proposal    distributions     for    each    node     to    its    
Markov Blanket.
Note    that    we    will    also    provide    evidence    variables,    and    the    graph    structure    must be    updated    with    
the    evidence    variables.    
CS5340    Assignment 4 (Semester    1,    AY2023/2024) 4
Hint:    It    might    be    useful    to    create    additional    functions    for    this    part.    Place    these    functions    between    
the     designated     comment     blocks     for     each     file.     Some     points     are     attributable     to more     efficient    
implementations.