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?

Solution:

: 2, e.g., by eliminating in order $genre(AI)$ , $age(David)$ , $genre(HP6)$ , $genre(TheHelp)$ , $genre(Hugo)$ , $age(Chris)$
: $min(\lfloor {\sqrt {r}\rfloor ,m,n)}$ , which occurs when the $r$ ratings are used to connect each of $\lfloor \sqrt {r}\rfloor$ movies with each of $\lfloor \sqrt {r}\rfloor$ people.
: 0, as the age nodes are disconnected.