Carnegie Mellon University10 601homework5_sol

10-601 Machine Learning: Homework 5 Due 5 p.m. Wednesday, February 25, 2015 Instructions • Late homework policy: Homework is worth full credit if submitted before the due date, half credit during the next 48 hours, a ...

10-601 Machine Learning: Homework 5 Due 5 p.m. Wednesday, February 25, 2015 Instructions • Late homework policy: Homework is worth full credit if submitted before the due date, half credit during the next 48 hours, and zero credit after that. You must turn in at least n−1 of the n homeworks to pass the class, even if for zero credit. • Collaboration policy: Homeworks must be done individually, except where otherwise noted in the assignments. \Individually" means each student must hand in their own answers, and each student must write and use their own code in the programming parts of the assignment. You may collaborate with others on this problem set and consult external sources. However, you must write your own solutions and fully list your collaborators/external references for each problem. We will be assuming that, as participants in a graduate course, you will be taking the responsibility to make sure you personally understand the solution to any work arising from such collaboration. • Online submission: You must submit your solutions online on autolab. We recommend that you use LATEX to type your solutions to the written questions, but we will accept scanned solutions as well. On the Homework 4 autolab page, you can download the template, which is a tar archive containing a blank placeholder pdf for the written questions and one Octave source file for each of the programming questions. Replace each pdf file with one that contains your solutions to the written questions and fill in each of the Octave source files with your code. When you are ready to submit, create a new tar archive of the top-level directory and submit your archived solutions online by clicking the \Submit File" button. You should submit a single tar archive identical to the template, except with each of the Octave source files filled in and with the blank pdf replaced by your solutions for the written questions. You are free to submit as many times as you like (which is useful since you can see the autograder feedback immediately). DO NOT change the name of any of the files or folders in the submission template. In other words, your submitted files should have exactly the same names as those in the submission template. Do not modify the directory structure. Problem 1: VC Dimension Recall that we call a set of points shattered by a class of functions H if all possible f−1; +1g labelings of the points can be produced by some function in H. The Vapnik-Chervonenkis (VC) dimension is the size of the largest set of points that can be shattered by the hypothesis space. See the lecture notes, video, and recitation video for more information. In this problem, we will explore the hypothesis space where each hypothesis is a combination of two simpler hypotheses. More precisely, given two hypotheses h1 and h2, we define h = h1 \ h2 as a new hypothesis that labels an example +1 only if both h1 and h2 give the label +1, otherwise, it is labeled −1. We can extend this to sets of hypotheses: given two sets of hypotheses H1 and H2, define H∗ = fh1 \h2 : h1 2 H1; h2 2 H2g as the set of all intersections of hypothesis pairs from the two classes H1 and H2. As an example, let H1 be the set of classifiers in R that assigns the label +1 if the example is larger than some threshold a. Let H2 be the set of classifiers in R that assigns the label +1 if the example is smaller than some threshold b. Then H∗ would be the set of all intervals (a; b) in R that assigns +1 if the example is inside the interval. Another example is when H1 and H2 is the set of all (axis-aligned) squares in R2, H∗ is 1the set of all axis-aligned rectangles. This example is illustrated below. On the left, we have a single square classifier h1; in the middle we again have a square classifier h2; and on the right, we have h1 \ h2, which is a rectangle classifier