12. Suppose you have a relational probabilistic model for movie prediction, which represents P(likes(P, M) ∣ age(P), genre(M))

where age(P) and genre(M) are a priori independent.

(a) What is the treewidth of the ground belief network (after pruning irrelevant variables)

for querying age(Sam) given the following observations?

Person Movie likes Sam Hugo yes Chris Hugo no Sam The Help no Sam Harry Potter 6 yes Chris Harry Potter 6 yes Chris AI no Chris The Help no David AI yes David The Help yes

(b) 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? [Hint: The treewidth depends on the structure of the observations; think about how the observations can be structured to maximize the treewidth.]

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