10-701/15-781, Fall 2006, FinalDec 15, 5:30pm-8:30pm• There are 9 questions in this exam (15 pages including this cover sheet).• If you need more room to work out your answer to a question, use the back of the pageand clearly mark on the front of the page if we are to look at what’s on the back.• This exam is open book and open notes. Computers, PDAs, cell phones are not allowed.• You have 3 hours. Best luck!Name:Andrew ID:Q Topic Max. Score Score1 Short Questions 202 Instance-Based Learning 73 Computational Learning Theory 94 Gaussian Mixture Models 105 Bayesian Networks 106 Hidden Markov Models 127 Dimensionality Reduction 88 Graph-Theoretic Clustering 89 MDPs and Reinforcement Learning 16Total 10011 Short Questions (20pts, 2pts each)(a) True or False. The ID3 algorithm is guaranteed to find the optimal decision tree.(b) True or False. Consider a continuous probability distribution with density f() that is nonzeroeverywhere. The probability of a value x is equal to f(x).(c) True or False. In a Bayesian network, the inference results of the junction tree algorithm arethe same as the inference results of variable elimination.(d) True or False. If two random variable X and Y are conditionally independent given anotherrandom variable Z, then in the corresponding Bayesian network, the nodes for X and Y ared-separated given Z.(e) True or False. Besides EM, gradient descent can be used to perform inference or learning ona Gaussian mixture model.(f) In one sentence, characterize the differences between maximum likelihood and maximum aposteriori approaches.(g) In one sentence, characterize the differences between classification and regression.(h) Give one similarity and one difference between feature selection and PCA.(i) Give one similarity and one difference between HMM and MDP.(j) For each of the following datasets, is it appropriate to use HMM? Provide a brief reasoning foryour answer.• Gene sequence dataset.• A database of movie reviews (eg., the IMDB database).• Stock market price dataset.• Daily precipitation data from the Northwest of the US.22 Instance-Based Learning (7pts)1. Consider the following training set in the 2-dimensional Euclidean space:x y Class−1 1 −0 1 +0 2 −1 −1 −1 0 +1 2 +2 2 −2 3 +Figure 1 shows a visualization of the data.−2 −1 0 1 2 3−2−101234xyFigure 1: Dataset for Problem 2(a) (1pt) What is the prediction of the 3-nearest-neighbor classifier at the point (1,1)?(b) (1pt) What is the prediction of the 5-nearest-neighbor classifier at the point (1,1)?(c) (1pt) What is the prediction of the 7-nearest-neighbor classifier at the point (1,1)?32. Consider the two-class classification problem. At a data p oint x, the true conditional proba-bility of a class k, k ∈ {0, 1} is pk(x) = P (C = k|X = x).(a) (2pts) The Bayes error is the probability that an optimal Bayes classifier will misclassifya randomly drawn example. In terms of pk(x), what is the Bayes error E∗at x?(b) (2pts) In terms of pk(x) and pk(x0) when x0is the nearest neighbor of x, what is the1-nearest-neighbor error E1NNat x?Note that asymptotically as the number of training examples grows, E∗≤ E1NN≤ 2E∗.43 Computational Learning Theory (9pts, 3pts each)In class we discussed different formula to provide a bound on the number of training examplessufficient for successful learning under different learning models.m ≥1²(ln(1/δ) + ln |H|) (1)m ≥12²2(ln(1/δ) + ln |H|) (2)m ≥1²(4 log2(2/δ) + 8V C(H) log2(13/²)) (3)Pick the appropriate one of the above formula to estimate the number of training examplesneeded for the following machine learning tasks. Briefly explain your choice.1. Consider instances X containing 5 Boolean variables, {X1, X2, X3, X4, X5}, and responses Yare (X1∧ X4) ∨ (X2∧ X3). We try to learn the function f : X → Y using a 2-layered neuralnetwork.2. Consider instances X containing 5 Boolean variables, {X1, X2, X3, X4, X5}, and responses Yare (X1∧ X4) ∨ (X2∧ X3). We try to learn the function f : X → Y using a “depth-2 decisiontrees”. A “depth-2 decision tree” is a tree with four leaves, all distance 2 from the root.3. Consider instances X containing 5 Boolean variables, {X1, X2, X3, X4, X5}, and responses Yare (X1∧X4)∨(¬X1∧X3). We try to learn the function f : X → Y using a “depth-2 decisiontrees”. A “depth-2 decision tree” is a tree with four leaves, all distance 2 from the root.54 Gaussian Mixture Model (10pts)Consider the labeled training points in Figure 2, where ‘+’ and ‘o’ denote positive and negativelabels, respectively. Tom asks three students (Yifen, Fan and Indra) to fit Gaussian Mixture Modelson this dataset.0 1 2 3 4 5012345X1X2Figure 2: Dataset for Gaussian Mixture Model1. (4pts) Yifen and Fan decide to use one Gaussian distribution for positive examples and onedistribution for negative examples. The darker ellipse indicates the positive Gaussian distri-bution contour and the lighter ellipse indicates the negative Gaussian distribution contour.0 1 2 3 4 5012345X1X20 1 2 3 4 5012345X1X2Yifen’s model Fan’s modelWhose model would you prefer for this dataset? What causes the difference between thesetwo models?62. (6pts) Indra decides to use two Gaussian distributions for positive examples and two Gaussiandistributions for negative examples. He uses EM algorithm to iteratively update parametersand also tries different initializations. The left column of Figure 3 shows 3 different initial-izations and the right column shows 3 possible models after the first iteration. For eachinitialization on the left, draw an arrow to the model on the right that will result after thefirst EM iteration. Your answer should consist of 3 arrows, one from each initialization.0 1 2 3 4 5012345X1X20 1 2 3 4 5012345X1X20 1 2 3 4 5012345X1X20 1 2 3 4 5012345X1X20 1 2 3 4 5012345X1X20 1 2 3 4 5012345X1X2(a) Initialization (b) After first iterationFigure 3: Three different initializations and models after the first iteration.75 Bayesian Networks (10pts)The figure below shows a Bayesian network with 9 variables, all of which are binary.1. (3pts) Which of the following statements are always true for this Bayes net?(a) P (A, B|G) = P (A|G)P (B|G);(b) P (A, I) = P (A)P (I);(c) P (B, H|E, G) = P (B|E, G)P(H|E, G);(d) P (C|B, F ) = P (C|F ).2. (2pts) What is the number of independent parameters in this graphical model?3. (3pts) The computational complexity of a graph elimination algorithm is determined by
View Full Document
Unlocking...