25 Jul Foundations of Machine Learning:Assignment 1Instru
Foundations of Machine Learning:Assignment 1Instructor: Prof. Xiangyang JiDue: 2020.03.22Problem 130pts. (Exercise 2.3 in Foundations of Machine Learning) Concentric circles. Let X = R2 and consider theset of concepts of the form c = f(x; y) : x2 + y2 r2g for some real number r. Show that this class can be(; )-PAC-learned from training data of size m (1=)log(1=).Problem 235pts. (Exercise 2.4 in Foundations of Machine Learning) Non-Concentric circles. Let X = R2 and considerthe set of concepts of the form c = fx 2 R2 : jjx x0jj rg for some point x0 2 R2 and real number r.Gertrude, an aspiring machine learning researcher, attempts to show that this class of concepts may be(; )-PAC-learned with sample complexity m (3=)log(3=), but she is having trouble with her proof. Heridea is that the learning algorithm would select the smallest circle consistent with the training data. Shehas drawn three regions r1; r2; r3 around the edge of concept c, with each region having probability =3 (seeFigure 1). She wants to argue that if the generalization error is greater than or equal to , then one of theseregions must have been missed by the training data, and hence this event will occur with probability at most.Can you tell Gertrude if her approach works? If the answer is not, can you modify this approach by drawingmore than three regions as above?1Assignment 1 Problem 2Figure 1: Gertrude’s regions r1; r2; r3.Problem 335pts. (Exercise 2.9 in Foundations of Machine Learning) Consistent hypotheses. In this chapter, weshowed that for a nite hypothesis set H, a consistent learning algorithm A is a PAC-learning algorithm.Here, we consider a converse question. Let Z be a nite set of m labeled points. Suppose that you are givena PAC-learning algorithm A. Show that you can use A and a nite training sample S to nd a hypothesish 2 H that is consistent with Z, with high probability.Note: S represents the training dataset, and Z represents the set of all possible examples in this problem.You should focus on proving S is nite and h is consistent on Z.Problem 4(Challenge, 20pts) Let H be set of all half-planes in R2. We assume that the underlying concept h 2 H.Try to prove that this class can be (; )-PAC-learnable.Page 2 of 2
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Writedemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.