10708 Probabilistic Graphical Models: Final ExamDue Dec 10th by Noon electronically to [email protected] or paper version to MichelleMartin, or by fax to 412-268-3431,Your final must be done individually. You may not discuss the questions with anyone otherthan Carlos or the TAs (you are free to ask us questions by e-mail or in person if you arehaving problems with a question). The exam is open book, but not open-Google, i.e., youcan use any materials we discussed in class or linked to from the class website. You arenot allowed to look at other sources. However, you may use a calculator or Matlab to donumerical computations, if necessary. Each question has the name of one of the TAs besideit, to whom you should direct any inquiries regarding the question. Please submit your finalin two parts, one for each TA. Also, please put the TA’s name on top of the final.If you hand in your assignment early, you can get bonus points.Handin BonusMonday, Dec 8, 2pm 3 ptsTuesday, Dec 9, 2pm 2 ptsYou may NOT use late days on the final.1 Short answers [Amr] [6 pts]1. For each of the following questions, answer true of false justifying your answer in (1-3sentences).(a) i. G1is I-equivalent to G2ii. G1is I-equivalent to G3iii. If G1is a perfect map for P, then G3is an I-map for P(b) If G1is a perfect map for P, given a infinite samples, D, from P:i. ScoreML(G1; D) = ScoreML(G2; D)ii. ScoreML(G1; D) < ScoreML(G3; D)iii. ScoreBIC(G1; D) = ScoreBIC(G2; D)1Figure 1: Graphs used in question 1iv. ScoreBIC(G1; D) < ScoreBIC(G3; D)(c) Let K be a cluster graph for a distribution P (i.e. it satisfies the generalizedrunning intersection and family preservation properties). If K happens to be atree, then K is a clique tree as well for P. (hint: either provide a counter exampleor show that the generalized RIP reduces to RIP in this case)2 Structure Learning in Undirected Models [Dhruv] [12pts]For this problem, assume that you have i.i.d. data sampled from a distribution P (X ). P isrepresented by a Markov Random Field whose graph structure is unknown. However, youdo know that each node has at most d neighbors.1. Show why knowing the Markov blanket of each node is sufficient for determining thegraph structure.2. For any node X and its Markov blanket MB(X), we know thatP |= (X ⊥ X − {X} − MB(X)|MB(X)).Briefly, why might you need a lot of data to test for this conditional independencedirectly?3. For disjoint sets of variables A and B, let conditional entropy be defined as,H(A|B) = −Xa,bP (A = a, B = b) log P (A = a|B = b)2Prove that for any node X, H(X|MB(X)) = H(X|X − {X}).4. For disjoint sets of variables A, B and C, we have thatH(A|B, C) ≤ H(A|B).In other words, information never hurts. Prove that MB(X) = argminYH(X|Y).5. Using the intuition developed in the previous parts, describe a structure learning al-gorithm for Markov Random Fields, assuming the constraint that each node has atmost d neighbors. Your algorithm should run in O(nndc) time, where n is the numberof nodes in your model, and c is the complexity of computing the conditional entropyH(X|Y), when |Y| ≤ d.6. If we removed the constraint that each node have at most d neighbors and insteadchanged our optimization problem to include a penalty term, MB(X) = argminY{H(X|Y)+|Y |}, how would the time complexity of the algorithm change?3 Trading Inference Accuracy vs. Efficiency [Amr 16pts]Note: Nearly half of this problem is marked as extra credit.As we know from class, compact representation does not translate into efficient inference. Fortrees, the cost of inference is linear in the size of the factors. For loopy graphs, we can eitherconvert it to a clique tree and then use belief propagation, or just run the belief propagationalgorithm on the loopy graph(which is equivalent to first constructing a bipartite factor graphas we discussed in class, and then running BP on it.) In the former case, inference is exact butits cost is exponential in the largest clique size. In the later case inference is approximate,but its cost is linear in the size of the largest factor. The above two solutions comprisestwo extremes in the space of efficiency vs. exactness. In both cases inference is carried viaBP over a given graph: in clique trees, the graph vertices correspond to maximal cliques,while in factor graphs, the graph vertices correspond to factors and singleton variables inthe original network. Region graphs generalize the above two solutions by filling the gapbetween them, and allowing for trading efficiency vs. exactness. In this question we willexplore this connection in more details.Region Graphs (K&F 10.3): Recall that a region graph is a directed acyclic graph withvertices correspond to regions which are subsets of the variables. If an edge exists fromregion r to region r0then scope[r0] ⊂ scope[r]. Each factor φ in the original network isassigned to a top-most region r such that Scope[φ]⊂ scope[r]. The region graph is calibratedvia a message-passing algorithm similar to BP. The exact message passing rules are givenin 10.37 in (K&F). Upon calibration, the belief of each region is computed using 10.36 in(K&F).3(a) T1(b) The split operator: AB ⊥ EF |CDFigure 23.1 Clique trees and factor graphs as region graphs1. Represent the clique tree T1in Figure 2a as a region graph R1? (Hint: the regiongraph has two levels)2. T1can be calibrated using BP as follows. First pick a root, then pass messages upwardfrom leaves to root using BP (i.e. sum-product), and finally pass messages downwardfrom root to leaves using BP. Similarly R1can be calibrated using message passingas in 10.37 in K&F. If we initialize all messages in R1to 1, show that there exists aschedule of sending messages that 1) will converge in only one pass, and 2) will achievethe same final beliefs over all cliques and sepsets as in T1. (Hint: it is easier to find aschedule of sending messages over R1that parallel the messages sent during calibratingthe clique tree)3. Given a clique tree T with cliques C and sepsets S, sketch a scheme of representing itas an equivalent region graph R. (hint: generalize your solution to part 1). If T hasN cliques, how many regions and edges does R contain?4. Given a factor graph, show how to represent it as a region graph. (hint: this is easy)We can also show that loopy belief propagation is equivalent to running the regiongraph’s message-passing algorithm over the above representation (You do NOT haveto show that).3.2 Building region
View Full Document
Unlocking...