COMP9417 - Machine LearningHomework 2: Kernel Features & Model CombinationsIntroduction In this homework we first take a closer look at feature maps induced by kernels. We then ex-plore a creative use of the gradient descent method introduced in homework 1. We will show that gradientdescent techniques can be used to construct combinations of models from a base set of models such that thecombination can outperform any single base model.Points Allocation There are a total of 28 marks.What to Submit A single PDF file which contains solutions to each question. For each question, provide your solutionin the form of text and requested plots. For some questions you will be requested to provide screenshots of code used to generate your answer — only include these when they are explicitly asked for. .py file(s) containing all code you used for the project, which should be provided in a separate .zipfile. This code must match the code provided in the report. You may be deducted points for not following these instructions. You may be deducted points for poorly presented/formatted work. Please be neat and make yoursolutions clear. Start each question on a new page if necessary.1 You cannot submit a Jupyter notebook; this will receive a mark of zero. This does not stop you fromdeveloping your code in a notebook and then copying it into a .py file though, or using a tool such asnbconvert or similar. We will set up a Moodle forum for questions about this homework. Please read the existing questionsbefore posting new questions. Please do some basic research online before posting questions. Pleaseonly post clarification questions. Any questions deemed to be fishing for answers will be ignoredand/or deleted. Please check Moodle announcements for updates to this spec. It is your responsibility to check forannouncements about the spec. Please complete your homework on your own, do not discuss your solution with other people in thecourse. General discussion of the problems is fine, but you must write out your own solution andacknowledge if you discussed any of the problems in your submission (including their name(s) andzID). As usual, we monitor all online forums such as Chegg, StackExchange, etc. Posting homework ques-tions on these site is equivalent to plagiarism and will result in a case of academic misconduct. You may not use SymPy or any other symbolic programming toolkits to answer the derivation ques-tions. This will result in an automatic grade of zero for the relevant question. You must do thederivations manually.When and Where to Submit Due date: Week 7, Monday March 27th, 2023 by 5pm. Please note that the forum will not be activelymonitored on weekends. Late submissions will incur a penalty of 5% per day from the maximum achievable grade. For ex-ample, if you achieve a grade of 80/100 but you submitted 3 days late, then your final grade will be80? 3× 5 = 65. Submissions that are more than 5 days late will receive a mark of zero. Submission must be made on Moodle, no exceptions.Page 2Question 1. Kernel PowerConsider the following 2-dimensional data-set, where y denotes the class of each point.index x1 x2 y1 1 0 -12 0 1 -13 0 -1 -14 -1 0 +15 0 2 +16 0 -2 +17 -2 0 +1Throughout this question, you may use any desired packages to answer the questions.(a) Use the transformation x = (x1, x2) 7→ (1(x), 2(x)) where 1(x) = 2x22 ? 4x1 + 1 and 2(x) =x21 ? 2x2 ? 3. What is the equation of the best separating hyper-plane in the new feature space?Provide a plot with the data set and hyperplane clearly shown.What to submit: a single plot, the equation of the separating hyperplane, a screen shot of your code, a copyof your code in your .py file for this question.(b) Fit a hard margin linear SVM to the transformed data-set in the previous part1. What are theestimated values of (1, . . . , 7). Based on this, which points are the support vectors? What errordoes your computed SVM achieve?What to submit: the indices of your identified support vectors, the train error of your SVM, the computed’s (rounded to 3 d.p.), a screen shot of your code, a copy of your code in your .py file for this question.(c) Consider now the kernel k(x, z) = (2+x>z)2. Run a hard-margin kernel SVM on the original (un-transformed) data given in the table at the start of the question. What are the estimated values of(1, . . . , 7). Based on this, which points are the support vectors? What error does your computedSVM achieve?What to submit: the indices of your identified support vectors, the train error of your SVM, the computed’s (rounded to 3 d.p.), a screen shot of your code, a copy of your code in your .py file for this question.(d) Provide a detailed argument explaining your results in parts (i), (ii) and (iii). Your argumentshould explain the similarities and differences in the answers found. In particular, is your answerin (iii) worse than in (ii)? Why? To get full marks, be as detailed as possible, and use mathematicalarguments or extra plots if necessary.What to submit: some commentary and/or plots. If you use any code here, provide a screen shot of your code,and a copy of your code in your .py file for this question.Question 2. Gradient Descent for Learning Combinations of ModelsIn this question, we discuss and implement a gradient descent based algorithm for learning combina-tions of models, which are generally termed ’ensemble models’. The gradient descent idea is a verypowerful one that has been used in a large number of creative ways in machine learning beyond directminimization of loss functions as in the previous question.The Gradient-Combination (GC) algorithm can be described as follows: Let F be a set of base learningalgorithms2. The idea is to combine the base learners in F in an optimal way to end up with a good1If you are using the SVC class in sklearn, to get a hard-margin svm, you need to set the hyper parameter C to be very large.2For example, you could take F to be the set of all regression models with a single feature, or alternatively the set of all regressionmodels with 4 features, or the set of neural networks with 2 layers etc.Page 3learning algorithm. Let `(y, y?) be a loss function, where y is the target, and y? is the predicted value.3Suppose we have data (xi, yi) for i = 1, . . . , n, which we collect into a single data set D0. We then setthe number of desired base learners to T and proceed as follows:(I) Initialize f0(x) = 0 (i.e. f0 is the zero function.)(II) For t = 1, 2, . . . , T :(GC1) Compute:rt,i = ? ??f(xi)n∑j=1`(yj , f(xj))∣∣∣∣f(xj)=ft?1(xj), j=1,...,nfor i = 1, . . . , n. We refer to rt,i as the i-th pseudo-residual at iteration t.(GC2) Construct a new pseudo data set, Dt, consisting of pairs: (xi, rt,i) for i = 1, . . . , n.(GC3) Fit a model to Dt using our base class F . That is, we solveht = argminf∈Fn∑i=1`(rt,i, f(xi))(GC4) Choose a step-size. This can be done by either of the following methods:(SS1) Pick a fixed step-size t = (SS2) Pick a step-size adaptively according tot = argminn∑i=1`(yi, ft?1(xi) + ht(xi)).(GC5) Take the stepft(x) = ft?1(x) + tht(x).(III) return fT .We can view this algorithm as performing (functional) gradient descent on the base class F . Note thatin (GC1), the notation means that after taking the derivative with respect to f(xi), set all occurencesof f(xj) in the resulting expression with the prediction of the current model ft?1(xj), for all j. Forexample:??xlog(x+ 1)∣∣∣∣x=23=1x+ 1∣∣∣∣x=23=124.(a) Consider the regression setting where we allow the y-values in our data set to be real numbers.Suppose that we use squared error loss `(y, y?) = 12 (y? y?)2. For round t of the algorithm, show thatrt,i = yi ? ft?1(xi). Then, write down an expression for the optimization problem in step (GC3)that is specific to this setting (you don’t need to actually solve it).What to submit: your working out, either typed or handwritten.(b) Using the same setting as in the previous part, derive the step-size expression according to theadaptive approach (SS2).What to submit: your working out, either typed or handwritten.3Note that this set-up is general enough to include both regression and classification algorithms.Page 4(c) We will now implement the gradient-combination algorithm on a toy dataset from scratch, and wewill use the class of decision stumps (depth 1 decision trees) as our base class (F), and squared errorloss as in the previous parts.4. The following code generates the data and demonstrates plottingthe predictions of a fitted decision tree (more details in q2.py):51 np.random.seed(123)2 X, y = f_sampler(f, 160, sigma=0.2)3 X = X.reshape(-1,1)45 fig = plt.figure(figsize=(7,7))6 dt = DecisionTreeRegressor(max_depth=2).fit(X,y) # example model7 xx = np.linspace(0,1,1000)8 plt.plot(xx, f(xx), alpha=0.5, color=’red’, label=’truth’)9 plt.scatter(X,y, marker=’x’, color=’blue’, label=’observed’)10 plt.plot(xx, dt.predict(xx.reshape(-1,1)), color=’green’, label=’dt’) # plottingexample model11 plt.legend()12 plt.show()13The figure generated isYour task is to generate a 5 x 2 figure of subplots showing the predictions of your fitted gradient-combination model. There are 10 subplots in total, the first should show the model with 5 baselearners, the second subplot should show it with 10 base learners, etc. The last subplot should bethe gradient-combination model with 50 base learners. Each subplot should include the scatter of4In your implementation, you may make use of sklearn.tree.DecisionTreeRegressor, but all other code must be yourown. You may use NumPy and matplotlib, but do not use an existing implementation of the algorithm if you happen to find one.5Although we will not cover decision trees until week 4, we are treating the decision tree as a black box algorithm that can be calledusing the sklearn implementation. For more on using sklearn models, see Lab 1.Page 5data, as well as a plot of the true model (basically, the same as the plot provided above but withyour fitted model in place of dt). Comment on your results, what happens as the number of baselearners is increased? You should do this two times (two 5x2 plots), once with the adaptive stepsize, and the other with the step-size taken to be = 0.1 fixed throughout. There is no need tosplit into train and test data here. Comment on the differences between your fixed and adaptivestep-size implementations. How does your model perform on the different x-ranges of the data?What to submit: two 5 x 2 plots, one for adaptive and one for fixed step size, some commentary, and a screenshot of your code and a copy of your code in your .py file.(d) Repeat the analysis in the previous question but with depth 2 decision trees as base learners in-stead. Provide the same plots. What do you notice for the adaptive case? What about the non-adaptive case? What to submit: two 5 x 2 plots, one for adaptive and one for fixed step size, some commen-tary, and a copy of your code in your .py file.(e) Now, consider the classification setting where y is taken to be an element of {?1, 1}. We considerthe following classification loss: `(y, y?) = log(1 + e?yy?). For round t of the algorithm, what is theexpression for rt,i? Write down an expression for the optimization problem in step (GC3) that isspecific to this setting (you don’t need to actually solve it).What to submit: your working out, either typed or handwritten.(f) Using the same setting as in the previous part, write down an expression for t using the adaptiveapproach in (SS2). Can you solve for t in closed form? Explain.What to submit: your working out, either typed or handwritten, and some commentary.(g) In practice, if you cannot solve for t exactly, explain how you might implement the algorithm.Assume that using a constant step-size is not a valid alternative. Be as specific as possible in youranswer. What, if any, are the additional computational costs of your approach relative to using aconstant step size ?What to submit: some commentary.
...