School of Computer Science
The University of Adelaide
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 2
m 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.
2.3 Deliverables
Implement random forest for wine quality prediction in either C/C++, Java or Python.
C++. In the case of C/C++, you must supply a makefile (Makefile) with a rule called inference to compile your
program into a Linux executable named inference.bin. Your program must be able to be compiled and run as follows:
$ make inference
$ ./inference.bin [graphfile] [queryfile]
JAVA. In the case of JAVA, you must write your program in the file inference.java. Your program must be able to be
compiled and run as follows:
$ javac inference.java
$ java inference [graphfile] [queryfile]
Python. In the case of Python, write you program in the file inference.py. Your program must be able to be run as
follows:
$ python inference.py [graphfile] [queryfile]
At the moment, only an older version of Python (version 2.7.5) is supported on the school servers. If you are not
familiar enough with this version of Python, PLEASE DO NOT USE PYTHON for the assignment.
1.3 Expected run time
Your program must be able to terminate within 1 minutes on the server.
1.4 Web Submission Instructions
You must submit your program on the Computer Science Web Submission System. This means you must create the
assignment under your own SVN repository to store the submission files.
The SVN key for this submission is
2021/s1/ai/assignment3
The link to the Web Submission System used for this assignment is:
https://cs.adelaide.edu.au/services/websubmission/
After submit your codes through SVN, navigate to 2021, Semester 1, Artificial Intelligence, Assignment 3 (for COMP
SCI 3007 7059 students). Then, click Tab “Make Submission" for this assignment and indicate that you agree to the
declaration. The automark script will then evaluate your codes.
1.5 Assessment
Your code will be compiled and run, testing its outputs for the two networks with several queries each. Two example
queries have been provided to you. Since the results are stochastic, the query answers will not be exact and will
vary from run to run. The answers will therefore be tested against a tolerance of ±1 (i.e. your answers must be
within 1% of the true values), so you must ensure convergence to this level of precision (by giving more samples).
If it passes all tests you will get 10% of the overall course mark. The objective of the tests is to check for the correct
operation of your implementation. Hence, the basis of the assessment is to compare your results against the
expected results.
Although it is an auto-assessment, I will randomly pick up some codes to check manually.
3. Part-of-Speech Tagging – Viterbi (5 marks)
In this part, you will do POS tagging via Viterbi algorithm for the sentence Janet will back the bill. This is the example
in our lecture and also in the textbook here (https://web.stanford.edu/~jurafsky/slp3/8.pdf).
The transition probabilities computed from the WSJ corpus without smoothing are in the table below. Rows are
labelled with the conditioning event; e.g., P( VB |MD ) is 0.7968.
The Observation likelihoods computed from the WSJ corpus without smoothing are in the following table：
The computation for the three columns are shown in the following figure:
3.1 The task
In this task, you need to calculate v3(3). Note that the computation of v1(1) to v1(7) and v2(2) are provided in the
lecture slides and the textbook. To compute v3(3) you first need to compute v2(1), v2(3), v2(4) ,v2(5), v2(6), v2(7).
For PG students, you need to further calculate v4(7). Note that to compute v4(7), you need to know v3(1) to v3(7).
3.2 Deliverable
You will provide your exact working for the computation of v2(1), v2(3), v2(4) ,v2(5), v2(6), v2(7) and v3(3) into a
report in pdf format. You need to write the detailed process and the results. Using equations provided by your text
editor. Hand-written equations (e.g., in image format) will not be marked.
Please submit the pdf to MyUni, Assignment 3
3.3 Assessment
Use correct equation, correct value to compute, and get correct results.
UG: 5 marks for v3(3), include intermediate results
PG: 2 marks for v3(3), 3 marks for v4(7), include intermediate results.