COMP9417代做、代写Python语言编程

日期：2024-07-16 09:43

COMP9417 - Machine Learning

Homework 3: MLEs and Kernels

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 — only include these when they are explicitly asked for.

1• .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 may be 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 set up 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 questions

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

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 example,

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.

Page 2Question 1. Maximum Likielihood Estimators and their Bias

Let X1, . . . , Xn

i.i.d. ∼ N(µ, σ

2

). Recall that in Tutorial 2 we showed that the MLE estimators of µ, σ

2 were

µˆMLE and σˆ

2

MLE where

µˆMLE = X, and σˆ

2

MLE =

1

n

Xn

i=1

(Xi − X)

2

.

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

(a) Find the bias and variance of both µˆMLE and σˆ

2

MLE

. Hint: You may use without proof the fact that

var

1

σ

2

Xn

i=1

(Xi − X)

2

!

= 2(n − 1)

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

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 (according

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): µ

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

(2)

2 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:

1 import matplotlib.pyplot as plt

2 import numpy as np

3 from sklearn import datasets

4

5 X, y = datasets.make_circles(n_samples=200, factor=0.4, noise=0.04, random_state=13)

6 colors = np.array([’orange’, ’blue’])

7

8 np.random.seed(123)

9 random_labeling = np.random.choice([0,1], size=X.shape[0], )

10 plt.scatter(X[:, 0], X[:, 1], s=20, color=colors[random_labeling])

11 plt.title("Randomly Labelled Points")

12 plt.savefig("Randomly_Labeled.png")

13 plt.show()

14

The random clustering plot is displayed here:

1Recall that for a set S, |S| denotes its cardinality. For example, if S = {4, 9, 1} then |S| = 3.

2The notation in the summation here means we are summing over all points belonging to the k-th cluster at iteration t, i.e. C

(t)

k

.

Page 4Implement 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 observe.

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

ki = arg min

k∈{1,...,K}

. 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

Page 5a function h that satisfies: h(x, x0

) = hφ(x), φ(x

0

)i. Show that the nearest mean step in (1) can be

re-written as:

ki = arg min

k∈{1,...,K}

h(Xi

, Xi) + T1 + T2

,

where T1 and T2 are two separate terms that may depend on C

(t−1)

k

, h(Xi

, Xj ) and h(Xj , X`) for

Xj , X` ∈ C

(t−1)

k

. 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: C

(0)

1

, C(0)

2

, . . . , C(0)

K .

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

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

ki = arg min

k∈{1,...,K}

h(Xi

, Xi) + T1 + T2

.

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

C

(t)

k = {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, x0

) = (1 + hx, x0

i),

and then with the function

h2(x, x0

) = (1 + hx, x0

i)

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.

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

Page 6Throughout 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) = 2x

2

2 − 4x1 + 1 and φ2(x) =

x

2

1 − 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) You wish to fit a hard margin SVM using the SVC class in sklearn. However, the SVC class only

fits soft margin SVMs. Explain how one may still effectively fit a hard margin SVM using the SVC

class. What to submit: some commentary.

(c) Fit a hard margin linear SVM to the transformed data-set in part (a). 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) 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.

(e) 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.

Page 7