## Description

Notes: • Please keep in mind the collaboration policy as speciﬁed in the course syllabus. If you discuss questions with others you must write their names on your submission, and if you use any outside resources you must reference them. Do not look at each others’ writeups, including code. • InstructionsforhowtogetﬁlesfromtheSVNrepositoryareavailableonthecoursewebsite and on Piazza. • Homework(inhardcopy)isdueatthebeginningoflecture. Inaddition,yourcodesubmission for Problem 2 must also be timestamped before lecture begins. • Please comment your code properly. • There are 4 problems on 2 pages in this homework. • Keep in mind that problems and exercises are distinct in LFD. Problems:

1. (10points)Repeattheproblemofapplyinggradientdescenttominimize Ein onthetraining dataset(cleveland.train)fromHomework3,butthistimescalethefeaturesbysubtracting the mean and dividing by the standard deviation for each of the features in advance of calling the learning algorithm (you may ﬁnd the matlab function zscore useful). Experiment with the learning rate η (you may want to start by trying different orders of magnitude),thistimeusingatolerance(howclosetozeroyouneedeachelementofthegradientto beinordertoterminate)of10−6. Reporttheresultsintermsofnumberofiterationsuntilthe algorithm terminates, and also the ﬁnal Ein. How does this compare to the Ein of glmfit? You do not need to submit any code for this problem. 2. (60 points) For this problem, you will be doing LFD Problem 4.4 parts (a) through (d) with some changes / help / instructions / requirements. First, you can ﬁnd headers for all the code you need to implement in your SVN repository for the class. There is also a matlab script called run expts.m which you can use as an example for how to run your code to return the results we want. Second, read Problem 4.3 carefully. You can (and will need to) use the recurrence deﬁned there as well as the formula in 4.3(e). (a) In addition to answering the question about why we need to normalize f, also prove that the term to normalize by isqPQ q=0 1 2q+1 (hint: use the formula in 4.3(e)). 1

(b) Answer the question. For your implementation, we suggest you use glmfit with the additional options ’normal’,’constant’,’off’. (c) Answer the question (hint: use the formula in 4.3(e)). (d) Implement the framework and answer the questions, with the modiﬁcation that you only need to look at Qf ∈ {5,10,15,20},N ∈ {40,80,120},σ2 ∈ {0,0.5,1.0,1.5,2.0}. Compute both the median and the mean of the overﬁt measure applied to many (at least 500) different datasets for each choice of parameters, and report how these measuresvaryasafunctionofthecomplexityofthetruehypothesis,thenumberoftraining examples,andthelevelofstochasticnoise(uselinegraphs). Explainyourobservations, and also comment on the differences you observe between the mean and median measures. 3. (15 points) LFD Exercise 4.4 4. (15 points) LFD Problem 4.8