CPSC 522 — Spring 2012
Assignment 3

CPSC 522 — Spring 2012
Assignment 3

Due: 12:30 p.m., Friday 10 February 2012

Question 1

Consider the following belief net:

\includegraphics{ah-multi-bel-net}

Consider the query: $P(G|F=true,H=false)$. For the elimination ordering, $B,D,E,A,C$ give all of factors created in VE. For each factor created, specify which factors were removed, and what variable was summed out. You do not need to consider any numerical values.

Consider using recursive conditioning for the same query, assuming that the variable were split in the order $G,C,A,E,D,B$. What values are used from the cache in this computation? Do any of the assignments disconnect the graph? If so, which ones?

Question 2

Suppose we have a relational probabilistic model for movie prediction, where we represent

  \[ P(likes(P,M)|age(P),genre(M)) \]    

What is the treewidth of the ground belief network (after pruning irrelevant variables) for querying $age(Sam)$ given the following observations?

Person

Movies

likes

Sam

Hugo

yes

Chris

Hugo

no

Sam

The Help

no

Sam

Harry Potter 6

yes

Chris

Harry Potter 6

yes

Chris

AI

no

David

AI

yes

David

The Help

yes

For the same probabilistic model, for $m$ movies, $n$ people and $r$ ratings, what is the worst-case treewidth of the corresponding graph (after pruning irrelevant variables), where only ratings are observed? (Here is it worst over the set of all observations).

For the same probabilistic model, for $m$ movies, $n$ people, and $r$ ratings, what is the worst-case treewidth of the corresponding graph, where the some ratings but all of the genres are observed?

Question 3

For this question you should use AILog (see http://artint.info/code/ailog/ailog_man.html).

Consider the electrical domain of Figure 5.2 of the textbook. Using the relations of Example 12.11 of the textbook and the probabilities of the AIspace “electrical diagnosis problem”, write an AILog program that computes the same posterior probabilities as the belief network. Make the rules as general as possible, so that your axiomatization can be applied to different configurations.

You need to hand in a documented program and evidence that it works.

Question 4

How long did the assignment take? What did you learn? Was it reasonable? What suggestions do you have to improve the assignment?

CPSC 522 — Spring 2012
Assignment 3