Posted: May 29th, 2015

1 Probabilistic graphical models

1 Probabilistic graphical models
1.1 Inference (undergrads and postgrads)
In lectures, we mainly covered Bayesian networks, one type of probabilistic graphical
model (PGM) using directed acrylic graphs. Your task is to write a program to imple-
ment likelihood weighting (or weighted) sampling, as described in lectures, to perform
inference on an arbitrary Bayesian network. You will need to parse an input text le
that encodes the graph and the conditional probability distributions for each variable
(conditioned on its parents). The format of the le is given in section 1.1.1 below. Two
PGM model les have been dened in this format and can be downloaded, along with
two queries each, at:
https://cs.adelaide.edu.au/users/third/ai/15s1-ai-adelaide/files/infer.zip
PGM 1: student model The rst PGM models a typical university student in
USA. A student has high intelligence has higher chance to score well in SAT test before
entering the university. The grade for university courses depends on the diculty of the
courses and the student’s intelligence. A good grade increases the chance of getting a
good recommendation letter from the teachers. The letter and SAT result may aect
the job that the student may get. Both the job and the grade may aect the student’s
happiness | typically a student is happy if they get a good grade and a dream job. The
PGM’s structure is shown in Figure 1.
PGM 2: car problem model The second PGM is for diagnosing the problem of a
car. The full detail is omitted here, but you can gure out some of its meaning based
1
G
I
J
S
D
H
L
Difficulty Intelligence
Grade
Happy
Letter
SAT
Job
Figure 1: Student model
on its le. Your code should be able to process both PGMs in above format. The grade
of the assignment depends on your results on both PGMs.
1.1.1 Model le format
The graphical model will be specied by a text le with format as in Figure 2 (Left),
where:
N is the number of random variables in the network;
rv are the random variable names (arbitrary alphanumeric strings);
Graph matrix: the matrix of zeros and ones species the directed arcs in the graph;
a one (1) in the i; j entry indicates there is an edge from i to j (so the ith variable
is a parent of the jth variable.
mat are two dimensional arrays of real numbers (in ASCII) that specify the con-
ditional probability table of each random variable conditioned on its parents;
The format of the matrices is a bit subtle, and is illustrated in Figure 2 (Right). If
a node has m parents, then the matrix needs to specify the probability of each outcome
(false; true) conditioned on 2m dierent combinations of parent values, so the matrix
will be 2m 2 (rows columns). Treating false as 0, and true as 1, concatenate the
values of the parents in their numerical order from most signicant bit to least signicant
2
Figure 2: Left: File format; Right: the format of the conditional probability matrices.
Note the numbers in the gure are for illustration purpose, and might be dierent from
the actual numbers in the le. You should use your code to read the le. The right
gure is from the wonderful textbook Probabilistic Graphical Models: Principles and
Techniques. MIT Press, 2009, by D. Koller and N. Friedman.
bit (left to right) to create a row index r. The entry in the rst column, rth row is then
the probability that the variable is false given the values of the other variables (the
entry in the corresponding 2nd column is the probability that the variable is true).
For example in Figure 2 (Right), assume that the variables are ordered as I;D; G; S; L.
G has two parents I and D. P(GjI;D) is represented by mat2 (the 3rd matrix), which
is the 4 3 matrix in the gure. Since I’s order is before D, the row indexing is (i0; d0),
and then (i0; d1) and so on instead of (d0; i0). I has only two values (false or true) thus
denoted as i0; i1. Here G has 3 values thus denoted as g1; g2; g3 (if you want to use
g0; g1; g2 to denote, it is ne too. It won’t aect the code anyway).
Another example is that if A has parents C and F where C is the 3rd variable spec-
ied and F is the 6th, then the (2,0) entry of their matrix represents P(A = falsejC =
true; F = false), and the (0,1) entry represents P(A = truejC = false; F = false).
The format of the query, entered via the console (or read from redirected standard
input) 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 specied. As is normal in Bayesian
3
Case I D G S L J H
1 1 1 2 1 1 0 1
2 0 0 1 0 0 1 0
3 1 0 3 0 0 1 0
4 1 0 1 0 0 1 1
…
Table 1: Samples
inference, variables not included are unobserved and should be marginalised out.
1.2 Learning parameters (postgrads)
This task is for postgrads. Undergrads can choose to do it too for bonus points.
The parameters in a Bayesian network are the conditional probability matrices. If
you have samples from the joint distribution represented by the Bayesian network, you
can estimate (conditional) probabilities of any variable by frequentism. For example, if
you have samples like in Table 1, you can estimate probabilities as follows:
P(D = 1) =
ND=1
Ntotal
P(G = 1jD = 1; I = 0) =
NG=1;D=1;I=0
ND=1;I=0
…
Here ND=1 is the number of samples that D = 1, and Ntotal is the total number of
samples. NG=1;D=1;I=0 is the number of samples that G = 1;D = 1; I = 0, and ND=1;I=0
is the number of samples that D = 1; I = 0.
Your code must be able to read both the PGM model le, and the sample data le,
and use them to produce a new PGM model le. The new PGM model le should be
in the same format as the PGM model le.
The sample data le for learning can be downloaded from
https://cs.adelaide.edu.au/users/third/ai/15s1-ai-adelaide/files/sample.
zip
Note that the Case ID and variables’ names are not included in the sample le.
Assume there are N variables. Each line is a sample vector with N dimensions in the
4
same order of variables as specied in the model le. Note that the old model le and the
new model le shall only dier in the entries of matrices. The rest should not change, as
we are only learning (updating) the parameters (not the graph). In principle, to learn
the parameters does not need to know the mat in the old model le. We allow you to
use the entire old model le for your convenience | if you have a dierent number of
matrices or their sizes are dierent from the ones in the old model le, you must have
done something wrong.
2 Deliverables
2.1 Inference (undergrads and postgrads)
Write your program in Java or C/C++. In the case of Java, name your program
inference.java. Your program must be able to be compiled and run as follows:
$ javac inference.java
$ java inference modelfile.txt queryfile.txt answerfile.txt
In the case of C/C++, you must supply a makele Makele with a rule called
inference to compile your program into a Linux executable binary named inference.bin.
Your program must be able to be compiled and run as follows:
$ make inference
$ ./inference.bin modelfile.txt queryfile.txt answerfile.txt
Output Your code must be able to read the model le, and the query le to produce
an answer le. The answer le should be named as studentanswer.txt for the student
model, and caranswer.txt for the car model. Each query le has two queries. The
(output) answer le should have 2 lines: the rst line is the vector (of the conditional
distribution) of the rst query, and the second is the vector of the second query. Each
vector uses a space to separate the value of each dimension.
NOTE1: If a makle exists, the marking script will assume that the program is
written in C/C++, otherwise Java will be assumed.
NOTE2: modelfile.txt, queryfile.txt, and answerfile.txt are the placehold-
ers for the names of the model le, the query le and the answer le.
5
2.2 Learning (postgrads)
Write your program in Java or C/C++. In the case of Java, name your program
learn.java. Your program must be able to be compiled and run as follows:
$ javac learn.java
$ java learn modelfile.txt samplefile.txt
In the case of C/C++, you must supply a makele Makele with a rule called
learn to compile your program into a Linux executable binary named learn.bin. Your
program must be able to be compiled and run as follows:
$ make learn
$ ./learn.bin modelfile.txt samplefile.txt
Output Your code must be able to read the PGM model le, and the sample data
le to produce a new PGM model le. The new PGM model le should be named as
newmodel.txt following the same format as the old PGM model le.
NOTE1: If a makle exists, the marking script will assume that the program is
written in C/C++, otherwise Java will be assumed.
NOTE2: modelfile.txt and samplefile.txt are the placeholders for the names
of PGM model le, and sample data le.
3 Submission policies
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 les. The SVN key for this submission is 2015/s1/ai/Assignment3.
The link to the Web Submission System used for this assignment is
https://cs.adelaide.edu.au/for/students/automark/
DO NOT use the link: https://cs.adelaide.edu.au/services/websubmission/
4 Grading