# 人工智能代写 | Artificial Intelligence Assignment 3

1. Introduction
This assignment has two parts: Probability Graph Model (Section 2) and Part-of-Speech Tagging (Section 3). Both
UG and PG students need to finish both parts. In part one, you are expected to perform approximate inference on
a given PGM using C++/Java/Python and submit the codes to the Web Submission system. In part two, you are
expected to provide your work for the required computation in a pdf and submit the pdf in MyUni, Assignment 3.

2. Probability Graph Model (10 marks)
Your task is to perform approximate inference on a probabilistic graphical model (PGM) of Boolean random
variables using likelihood weighted sampling, as described in lecture. You will work on two networks (Burglar and
Fire). The networks and example queries are provided in the textual files attached on MyUni and will be described
in the later section.

2.1 The task
You need to write a program (C++/Java/Python) to parse the input file of network and to create and populate an
internal data structure of the PGM. The program also need to parse the input query file correctly and evaluate the
conditional probability distribution of the query variable, given the evidence. The result must be written as two
decimal values corresponding to the values of P(QueryVar=true|…) and P(QueryVar=false|…) onto the standard
output stream, separated by white space. For example:
0.872 0.128
Note that if you write anything else before these two numbers, automark will interpret that output as the answer,
almost certainly resulting in a test failure.

2.2 File Format
The format of the network file is:
N

rv0 rv1 … rvN-1
0 0 1 … 0
1 0 0 … 1

0 1 1 … 0

mat0

mat1

matN-1

 N is the number of random variables in the network;

 rv* are the random variable names (arbitrary alphanumeric strings);
 The matrix of zeros and ones specifies the directed arcs in the graph; a ‘1’ in the (i, j) entry indicates there
is an edge from i to j, so the i-th variable is a parent of the j-th variable.
 mat are two dimensional arrays of real numbers (in ASCII) that specify the conditional probability table of
each random variable conditioned on its parents; If a node has m parents, then the matrix needs to specify
the probability of each outcome (true, false) conditioned on 2m different combinations of parent values, so
the matrix will be 2m x 2 (rows x columns). Treating true as 1, and false as 0, concatenate the values of the
parents in their numerical order from most significant bit to least significant bit (left to right) to create a
row index r. The entry in the first column, r-th row is then the probability that the variable is true given the
values of the other variables (the entry in the corresponding 2nd column is the probability that the variable
is false). Thus, the first row of the matrix corresponds to all conditioning variables taken the value false (r
= 000… 0), and the last row has all conditioning variables true (r = 111 …1).
For example if the variable A has parents C and F where C is the 3rd variable specified and F is the 6th, then
C,F = 00, 01, 10, 11 correspnd to row r = 0, 1, 2, 3 of the table. The CPT entries for P(A|C,F) entries will be:

The format of the query file is:

P(rvQ | rvE1=val, rvE2=val, …)

where rvQ is the name of the query variable, and rvEx are the names of the evidence variables with their respective
true/false values specified. E-mail: itcsdx@outlook.com  微信:itcsdx 