10701/15781 Machine Learning, Spring 2006: Homework 4Due: Wednesday, April 5, beginning of the class.Please refer your questions to TAs.1 [20 points] Learning Theory [Andreas]1. You have learned that th e VC d imen s ion is a measure of the size of continuous hypothesisspaces. For discrete hypothesis spaces, the bounds measure this size u sing log2|H|. In thecase of a finite hypothesis space H, show that V C(H) ≤ log2|H|. (Hint: if you are lucky,what is the minimum nu mber 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 isdetermined by three points x1, x2, x3∈ R2, which are the corners of the triangle (thesecorners can coincide or be all on one line, i.e. the triangles can be degenerate). All pointswithin the convex hull of x1, x2, x3are labeled positive, everything outside is labeled negative.What is the VC dimension of this hypothesis class? Prove your claim by showin g tight upperand lower bounds on the VC dimen s ion.3. In th is question, we will see why the VC-dimension of a hypothesis space is a notion of worstcase complexity for learning arbitrary concepts.More precisely, we h ave a learner (with arbitrary learning algorithm), and a space H ofhypotheses h, ass ignin g labels to every instance X, i.e. h : X → {+, −}. We will assumeconsistency, i.e. the target function (target concept) c : X → {+, −} is contained in thehypothesis space H. The learner selects training examples xi∈ X, and the teacher providesits label c(xi). The learner continues asking queries, until it has determined exactly whichone of the hypotheses in H is the target concept c.Show that in the worst case (i.e. if an ad versary chooses c ∈ H based on the learner’squeries so far and tries to maximize the number of queries the learner needs to make), thelearner needs at least VC(H) queries to identify the tar get concept. More formally, defineMinQueries(c, H) to be the minimum number of queries by the learning algorithm necessaryto guarantee th at the target concept c ∈ H can be learned exactly. We are interested in theworst case number of queries, WorstQueries(H), whereWorstQueries(H) = maxc∈H[MinQueries(c, H)].Show that VC(H) ≤ WorstQueries(H). H i nt: Consider the largest subset S ⊂ X of instancesX which can be shattered by H, and show that in the worst case the learner will be forced toquery each instance x ∈ S separately.1Figure 1: Bayes net for “explaining away” question.4. Now (in the s ame setting as part 3.), consider that a friend instead of an ad versary choosesthe 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 th e targetconcept?More formally, defineBestQueries(H) = minc∈H[MinQueries(c, H)].Do es it still hold that BestQueries(H) ≥ VC(H) for any class of hyp otheses H? Justify youranswer.2 [10 points] Explaining Away [Anton]The “Flu - Allergy - Sinus” Bayes network has been upgraded to handle bird flu (Fig. 1). Eachvariable can be either true (T ) or false (F ). Here are the conditional probability tables:P (F lu = T ) = 0.4, P (A = T ) = 0.3P (S = T |F lu = F, A = F ) = 0.1, P (S = T |F lu = F, A = T ) = 0.5P (S = T |F lu = T, A = F ) = 0.6, P (S = T |F lu = T, A = T ) = 0.91. CalculateP (F lu = T |S = T ) and P (F lu = T |S = T, A = T )(show your calculations, not only the answers).You will see thatP (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 sinusinflammation.2. Show that explaining away can also work in the opposite direction. Construct a CPT forP (S|F lu, A) such thatP (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 forP (F lu = T |S = T, A = T ) and P (F lu = T |S = T ).2(a) (b)Figure 2: Bayes nets for question 33 [15 points] BN Representation [Anton]In this question you will see that the same distribution can be represented by Bayes networks withdifferent s tructu res. You are given the BN from Fig. 2(a). Each variable can be either true (T ) orfalse (F ). Conditional probability tables (CPTs) areP (A = T ) =310P (B = T |A = T ) =1725, P (B = T |A = F ) =825P (C = T |A = T, B = T ) =1617, P (C = T |A = T, B = F ) =12P (C = T |A = F, B = T ) =12, P (C = T |A = F, B = F ) =1171. Show that this probability distribution can be represented using a Bayes network with only2 edges s hown in Figure 2(b). What are the corresponding CPTs? Show your calculation s ofjoint d istributions 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 lessthan 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, whileposing as a member of the aristocracy, I will get c lose to the King. W hen the moment is right, hewill die. The military will be eating out of my hand and the clergy will not dare to move againstme. 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, hisfirst step, obvious ly, was to build a graphical model, as shown on figure 3. The variables b eing:3The ForceGraduateFree FoodMoneyPowerWorld DominationKnowledgeFigure 3: World Domination network.Graduate (G), Free Food (FF), The Force (TF), Knowledge (K), Money (M), Power (R) and WorldDomination (WD). All these variables are binary valued {T, F }. The conditional probability tablesare:P (G = T |T F = T, F F = T ) = 0.9, P (G = T |T F = T, F F = F ) = 0.5P (G = T |T F = F, F F = T ) = 0.7, P (G = T |T F = F, F F = F ) = 0.3P (F F = T |T F = T ) = 0.8, P (F F = T |T F = F ) = 0.6P (T F = T ) = 0.1P (K = T |G = T ) = 0.7, P (K = …
View Full Document
Unlocking...