10701 15781 Machine Learning Spring 2006 Homework 4 Due Wednesday April 5 beginning of the class Please refer your questions to TAs 1 20 points Learning Theory Andreas 1 You have learned that the VC dimension is a measure of the size of continuous hypothesis spaces For discrete hypothesis spaces the bounds measure this size using log2 H In the case of a finite hypothesis space H show that V C H log2 H Hint if you are lucky what is the minimum number of hypothesis that you need to shatter k points 2 Consider the space H of arbitrary triangles in the plane i e each hypothesis c H is determined by three points x1 x2 x3 R2 which are the corners of the triangle these corners can coincide or be all on one line i e the triangles can be degenerate All points within the convex hull of x1 x2 x3 are labeled positive everything outside is labeled negative What is the VC dimension of this hypothesis class Prove your claim by showing tight upper and lower bounds on the VC dimension 3 In this question we will see why the VC dimension of a hypothesis space is a notion of worst case complexity for learning arbitrary concepts More precisely we have a learner with arbitrary learning algorithm and a space H of hypotheses h assigning labels to every instance X i e h X We will assume consistency i e the target function target concept c X is contained in the hypothesis space H The learner selects training examples xi X and the teacher provides its label c xi The learner continues asking queries until it has determined exactly which one of the hypotheses in H is the target concept c Show that in the worst case i e if an adversary chooses c H based on the learner s queries so far and tries to maximize the number of queries the learner needs to make the learner needs at least VC H queries to identify the target concept More formally define MinQueries c H to be the minimum number of queries by the learning algorithm necessary to guarantee that the target concept c H can be learned exactly We are interested in the worst case number of queries WorstQueries H where WorstQueries H max MinQueries c H c H Show that VC H WorstQueries H Hint Consider the largest subset S X of instances X which can be shattered by H and show that in the worst case the learner will be forced to query each instance x S separately 1 Figure 1 Bayes net for explaining away question 4 Now in the same setting as part 3 consider that a friend instead of an adversary chooses the target concept c H and the friend wishes to minimize the number of learning queries Is it possible in general that fewer queries than VC H suffice to exactly identify the target concept More formally define BestQueries H min MinQueries c H c H Does it still hold that BestQueries H VC H for any class of hypotheses H Justify your answer 2 10 points Explaining Away Anton The Flu Allergy Sinus Bayes network has been upgraded to handle bird flu Fig 1 Each variable can be either true T or false F Here are the conditional probability tables P F lu T 0 4 P A T 0 3 P S T F lu F A F 0 1 P S T F lu F A T 0 5 P S T F lu T A F 0 6 P S T F lu T A T 0 9 1 Calculate P F lu T S T and P F lu T S T A T show your calculations not only the answers You will see that P F lu T S T P F lu T P F lu T S T A T P F lu T S T so the extra evidence about allergy explains away flu as a possible reason of the sinus inflammation 2 Show that explaining away can also work in the opposite direction Construct a CPT for P S F lu A such that P F lu T S T A T P F lu T S T P F lu T Do not change priors P F lu and P S Show the new CPT and calculations for P F lu T S T A T and P F lu T S T 2 a b Figure 2 Bayes nets for question 3 3 15 points BN Representation Anton In this question you will see that the same distribution can be represented by Bayes networks with different structures You are given the BN from Fig 2 a Each variable can be either true T or false F Conditional probability tables CPTs are P A T P B T A T 3 10 17 P B T A F 25 8 25 16 P C T A T B F 21 17 1 1 P C T A F B T P C T A F B F 17 2 P C T A T B T 1 Show that this probability distribution can be represented using a Bayes network with only 2 edges shown in Figure 2 b What are the corresponding CPTs Show your calculations of joint distributions over A B and C for the old and new networks 2 Prove that this probability distribution cannot be represented using a Bayes net with less than 2 edges Hint Think of the independence assumptions 4 15 points Inference Jure Here is a secret plan Don t tell anyone First I will assassinate the Grand Duke Next while posing as a member of the aristocracy I will get close to the King When the moment is right he will die The military will be eating out of my hand and the clergy will not dare to move against me Then with the aid of powerful but expendable friends the conquest of the world can begin But before your friendly TA can proceed with it he must graduate To asses the situation his first step obviously was to build a graphical model as shown on figure 3 The variables being 3 The Force Knowledge Graduate Free Food Money Power World Domination Figure 3 World Domination network Graduate G Free Food FF The Force TF Knowledge K Money M Power R and World Domination WD All these variables are binary valued T F The conditional probability tables are P G T T F T F F T 0 9 P G T T F T F F F 0 5 P G T T F F F F T 0 7 P G T T F F F F F 0 3 P F F T T F T 0 8 P F F T T F F 0 6 P T F T 0 1 P K T G T 0 7 P K T G F 0 6 P R T M T 0 7 P R T M F 0 1 P M T G T 0 6 P …
View Full Document
Unlocking...