CSE 291d Midterm Exam Thursday February 15 2007 Student ID Note do not write your actual name INSTRUCTIONS There are six problems for a total of one hundred 100 points If necessary the blank side of each page can be used to show your work Where appropriate show work for partial credit Question Score Max 1 Conditional independence 20 2 Markov blankets 20 3 Inference with sigmoid CPT 15 4 Polytrees 15 5 Naive Bayes model 15 6 Maximum likelihood parameter estimation 15 Total 100 1 1 Conditional independence For the belief network shown below indicate whether the following statements of conditional independence are true T or false F A B C F D G E H P D H P D E H P A F C P A C P F C P C D A P C A P D A P C D G P C G P D G P B G P B P A P A E B P G P G H P F H A P F A P H A P F G H A P F A P G A P H A P F H G P F G P H G 2 2 Markov blankets A B C E D F For the above belief network consider the following statements of conditional independence Indicate the largest subset of nodes S A B C D E F for which each statement is true Note that one possible answer is the empty set S or S whichever notation you prefer The first two have been done as examples P A P A S S B P A C P A S S B C E P A C D P A S P D P D S P D A P D S P D A F P D S P D A C F P D S P B P B S P B E P B S P B C E P B S P E P E S P A B P A B S 3 3 Inference with sigmoid CPT X Y Variables X 0 1 Y 0 1 Z 0 1 Sigmoid CPT Z P Z 1 X x Y y 1 e wx x wy y 1 Parameters wx wy Consider the above belief network with binary random variables and sigmoid CPT Suppose that the prior probabilities satisfy 0 P X 1 1 0 P Y 1 1 In other words both X and Y have some probability of being either zero or one Likewise in the sigmoid CPT suppose that the weights satisfy wx 0 wy 0 wx wy 0 Note the opposite signs of the weights For each of the following pairs indicate whether the probability on the left is equal greater than or less than the probability on the right P X 1 P X 1 Y 1 P X 1 P X 1 Z 1 P Y 1 P Y 1 Z 1 P Z 1 X 0 Y 0 P Z 1 X 0 Y 1 P Z 1 X 1 Y 0 P Z 1 X 0 Y 1 P Z 1 X 0 Y 0 P Z 1 X 1 Y 1 P Y 0 Z 1 P Y 0 Z 1 X 1 P X 1 P Y 0 P Z 1 P X 1 Y 0 Z 1 4 4 Polytrees In the figure below circle the DAGs that are polytrees In the other DAGs shade in one node that could be instantiated to induce a polytree by the method of cutset conditioning 5 5 Naive Bayes model Y X1 X2 X3 Xn a For the belief network shown above express the joint distribution P Y X1 X2 Xn in terms of the conditional probability tables P Y and P Xi Y b Compute the posterior probability P Y y X1 X2 Xn in terms of these same CPTs 6 c Consider a complete data set of N examples assumed to consist of i i d samples drawn from the joint distribution of this belief network Let N y count the number of examples with Y y and let Ni x y count the number of examples with Xi x and Y y Express the maximum likelihood ML estimates for P Y y and P Xi x Y y in terms of these counts It is only necessary to state your answers not to derive them d Consider the belief network shown on the right with the same connectivity but opposite directionality in the edges of its DAG Y X 1 X 2 X 3 Y X n X 1 X 2 X 3 X n i Indicate one statement of conditional independence that is satisfied by the model on the left but not the model on the right ii Indicate one statement of conditional independence that is satisfied by the model on the right but not the model on the left 7 6 Maximum likelihood parameter estimation X1 X2 X3 Xn Y Consider the above belief network with nonnegative random variables Xi 0 and binary random variable Y 0 1 Also consider the following conditional probability table n X P Y 1 X1 x1 Xn xn exp wi xi i 1 which is parameterized in terms of the nonnegative weights wi 0 A useful shorthand for the above CPT is simply x P Y 1 X x e w a Consider a data set of i i d examples xt yt Tt 1 Compute the conditional log likelihood of the data set T X log P Y yt X xt L t 1 in terms of the weight vector w Note you will want to simplify your expression as much as possible for the next part of this question 8 b As shorthand in this problem let pt P Y 1 X xt Show that the gradient of the conditional log likelihood from part a is given by T X pt yt L xt w 1 p t t 1 Note show all of your intermediate steps very clearly to receive full credit 9
View Full Document
Unlocking...