COMP9417 - Machine Learning

Introduction In this homework we first continue our exploration of bias, variance and MSE of estimators. We will show that MLE estimators are not unnecessarily unbiased, which might affect their performance in small samples.  We then delve into kernel methods:  first by kernelizing a popular algorithm used in unsupervised learning, known as K-means.  We then look at Kernel SVMs and compare them to fitting linear SVMs with feature transforms.

Points Allocation There are a total of 28 marks.

• Question 1 a): 2 marks

• Question 1 b): 2 marks

• Question 1 c): 4 marks

• Question 2 a): 1 mark

• Question 2 b): 1 mark

• Question 2 c): 2 marks

• Question 2 d): 2 marks

• Question 2 e): 2 marks

• Question 2 f): 3 marks

• Question 2 g): 2 marks

• Question 3 a): 1 mark

• Question 3 b): 1 mark

• Question 3 c): 1 mark

• Question 3 d): 1 mark

• Question 3 e): 3 marks

What to Submit

•  A single PDF file which contains solutions to each question. For each question, provide your solution in the form of text and requested plots. For some questions you will be requested to provide screen shots of code used to generate your answer — onlyinclude 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 .zip file. This code must match the code provided in the report.

• You maybe deducted points for not following these instructions.

•  You may be deducted points for poorly presented/formatted work.  Please be neat and make your solutions clear. Start each question on a new page if necessary.

•  You cannot submit a Jupyter notebook; this will receive a mark of zero. This does not stop you from developing your code in a notebook and then copying it into a .py file though, or using a tool such as

nbconvert or similar.

•  We will setup a Moodle forum for questions about this homework. Please read the existing questions before posting new questions. Please do some basic research online before posting questions. Please only post clarification questions.  Any questions deemed to be fishing for answers will be ignored and/or deleted.

•  Please check Moodle announcements for updates to this spec.  It is your responsibility to check for announcements about the spec.

•  Please complete your homework on your own, do not discuss your solution with other people in the course. General discussion of the problems is fine, but you must write out your own solution and acknowledge if you discussed any of the problems in your submission (including their name(s) and zID).

•  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 the derivations manually.

When and Where to Submit

•  Due date: Week 8, Monday July 15th, 2024 by 5pm. Please note that the forum will not be actively monitored 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 be

80 - 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.

Question 1. Maximum Likielihood Estimators and their Bias

Let X1, . . . , Xn  i.d. N (μ, σ2 ). Recall that in Tutorial 2 we showed that the MLE estimators of μ, σ 2 were

^(μ)MLE  and^(σ)M(2)LE where

^(μ)MLE  = X ,       and

In this question, we will explore these estimators in more depth.

(a)  Find the bias and variance of both^(μ)MLE  and^(σ)M(2)LE . Hint: You may use without proof the fact that

What to submit: the bias and variance of the estimators, along with your working.

(b)  Your friend tells you that they have a much better estimator for σ 2, namely:

Discuss whether this estimator is better or worse than the MLE estimator:

Be sure to include a detailed analysis of the bias and variance of both estimators, and describe what happens to each of these quantities (for each of the estimators) as the sample size n increases (use plots). For your plots, you can assume that σ = 1.

What to submit: the bias and variance of the new estimator. A plot comparing the bias of both estimators as a function of the sample size n, a plot comparing the variance of both estimators as a function of the sample size n, use labels/legends in your plots. A copy of the code used here in solutions.py

(c)  Compute and then plot the MSE of the two estimators considered in the previous part.  For your plots, you can assume that σ = 1. Provide some discussion as to which estimator is better (accord- ing to their MSE), and what happens as the sample size n gets bigger.  What to submit: the MSEs of the two variance estimators. A plot comparing the MSEs of the estimators as a function of the sample size n, and some commentary. Use labels/legends in your plots. A copy of the code used here in solutions.py

Question 2. A look at clustering algorithms

Note:  Using an existing/online implementation of the algorithms described in this question will result in a grade of zero. You may use code from the course with reference.

The K-means algorithm is the simplest and most intuitive clustering algorithm available. The algorithm takes two inputs: the (unlabeled) data X1, . . . , Xn  and a desired number of clusters K.  The goal is to identify K groupings (which we refer to as clusters), with each group containing a subset of the original data points. Points that are deemed similar/close to each other will be assigned to the same grouping. Algorithmically, given a set number of iterations T, we do the following:

1.  Initialization: start with initial set of K-means (cluster centers): μ , μ , . . . , μ .

2.  For t = 1, 2, 3, . . . , T:

•  For i = 1, 2, . . . , n: Find nearest mean to Xi by solving

• For k = 1, . . . , K : set

Ck(t)  = {Xi such that ki  = k}

(a)  Consider the following data-set of n = 5 points in R2 :

You run K-means on this dataset with K = 2 and initial cluster centers μ  = (5, 2)T , μ = (4, 5)T . Compute the cluster centers at the next two iterations: μ , μ and μ , μ by hand. Be sure to show your working.

What to submit: your cluster centers and any working, either typed or handwritten.

(b)  Your friend tells you that they are working on a clustering problem at work.  You ask for more details and they tell you they have an unlabelled dataset with p =  10000 features and they ran K-means clustering using Euclidean distance.  They identified 52 clusters and managed to define labellings for these clusters based on their expert domain knowledge. What do you think about the usage of K-means here? Do you have any criticisms?

What to submit: some commentary.

(c)  Consider the data and random clustering generated using the following code snippet:

The random clustering plot is displayed here:

Implement K-means clustering from scratch on this dataset.  Initialize the following two cluster centers:

and run for 10 iterations. In your answer, provide a plot of your final clustering (after 10 iterations)

similar to the randomly labeled plot, except with your computed labels in place of random labelling. Do you think K-means does a good job on this data?  Provide some discussion on what you ob-

serve. What to submit: some commentary, a single plot, a screen shot of your code and a copy of your code in your .py file.

(d)  You decide to extend your implementation by considering a feature transformation which maps

2-dimensional points (x1 , x2 ) into 3-dimensional points of the form (x1(2), x2(2) , √2x1 x2 ).  Run your

K-means algorithm (for 10 iterations) on the transformed data with cluster centers:

Note for reference that the nearest mean step of the algorithm is now:

where φ(x) = (x1(2), x2(2) , √2x1 x2 )T . In your answer, provide a plot of your final clustering using the code provided in (c) as a template. Provide some discussion on what you observe. What to submit: a single plot, a screen shot of your code and a copy of your code in your .py file, some commentary.

(e)  You recall (from lectures perhaps) that directly applying a feature transformation to the data can be computationally intractable, and can be avoided if we instead write the algorithm in terms of

a function h that satisfies:  h(x, xI ) = (φ(x), φ(xI )〉.  Show that the nearest mean step in (1) can be re-written as:

where T1  and T2  are two separate terms that may depend on Ck(t—1), h(Xi , Xj ) and h(Xj , Xl ) for Xj , Xl  ∈ Ck(t—1) . The expressions should not depend on φ . What to submit: your full working.

(f)  With your answer to the previous part, you design a new algorithm: Given data X1, . . . , Xn, the number of clusters K, and the number of iterations T:

1.  Initialization: start with initial set of K clusters: C1(0) , C2(0) , . . . , C .

2.  For t = 1, 2, 3, . . . , T :

• For i = 1, 2, . . . , n: Solve

• For k = 1, . . . , K, set

Ck(t)  = {Xi such that ki  = k}.

The goal of this question is to implement this new algorithm from scratch using the same data generated in part (c). In your implementation, you will run the algorithm two times: first with the function:

h1 (x, xI ) = (1 + (x, xI〉),

and then with the function

h2 (x, xI ) = (1 + (x, xI〉)2 .

For your initialization (both times), use the provided initial clusters, which can be loaded in by running inital clusters  =  np .load(’init clusters .npy’). Run your code for at most 10 iterations, and provide two plots, one for h1  and another for h2 . Discuss your results for the two functions.  What to submit:  two plots, your discussion, a screen shot of your code and a copy of your code in your .py file.

(g)  The initializations of the algorithms above were chosen very specifically, both in part (d) and (f). Investigate different choices of intializations for your implemented algorithms.  Do your results look similar, better or worse? Comment on the pros/cons of your algorithm relative to K-means, and more generally as a clustering algorithm.  For full credit, you need to provide justification in the form of a rigorous mathematical argument and/or empirical demonstration.  What to submit: your commentary.

Question 3. Kernel Power

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