COMP9417 - Machine Learning Homework 2: Kernel Features & Model Combinations

Introduction

In this homework we first take a closer look at feature maps induced by kernels. We then explore a creative use of the gradient descent method introduced in homework 1. We will show that gradient descent techniques can be used to construct combinations of models from a base set of models such that the combination can outperform any single base model.

Question 1. Kernel Power

Consider the following 2-dimensional data-set, where y denotes the class of each point.

index x1 x2 y
1 1 0 -1
2 0 1 -1
3 0 -1 -1
4 -1 0 +1
5 0 2 +1
6 0 -2 +1
7 -2 0 +1

Throughout 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 copy of 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 the estimated values of ( 1; : : : ;  7). Based on this, which points are the support vectors? What error does 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 (untransformed) 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 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.
• (d) Provide a detailed argument explaining your results in parts (i), (ii) and (iii). Your argument should explain the similarities and differences in the answers found. In particular, is your answer in (iii) worse than in (ii)? Why? To get full marks, be as detailed as possible, and use mathematical arguments 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 Models

In this question, we discuss and implement a gradient descent based algorithm for learning combinations of models, which are generally termed ’ensemble models’. The gradient descent idea is a very powerful one that has been used in a large number of creative ways in machine learning beyond direct minimization 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 learning algorithms2. The idea is to combine the base learners in F in an optimal way to end up with a good learning algorithm. Let `(y; ^y) be a loss function, where y is the target, and ^y is the predicted value.3 Suppose we have data (xi; yi) for i = 1; : : : ; n, which we collect into a single data set D0. We then set the number of desired base learners to T and proceed as follows: ...