next up previous
Next: Bagging and Boosting [4 Up: MLA_Exercises_2009 Previous: Inference in Factor Graphs

Bonus example: Moral graph [3* P]

Recall that the factor graph associated with an undirected graph has one factor for each potential defined on the graph. Assume that there are no potentials associated with non-maximal cliques.

Let $ G$ be a polytree, and let $ G_M$ be its moral graph. Let $ F$ denote the factor graph associated with $ G$ , and let $ F_M$ denote the graph associated with $ G_M$ . For every node $ x_i$ in $ G$ with no parents, add a factor $ f_i$ to $ F_M$ that is connected to the node $ x_i$ . Prove that $ F$ and $ F_M$ are identical, i.e., the factor graph associated with the moral graph of a polytree is the same as the factor graph associated with the polytree, modulo the single-variable factors. (Hint: Use induction. Work through the nodes in a topological order, building $ G_M$ , $ F_M$ and $ F$ .)



Haeusler Stefan 2010-01-26