Homework 6 ESE 402/542 Due December 1, 2019 at 11:59pm Type or scan your answers as a single PDF file and submit on Canvas. Problem 1. Principal Component Analysis. Consider the following dataset: x y...

Homework 6
ESE 402/542
Due December 1, 2019 at 11:59pm
Type or scan your answers as a single PDF file and submit on Canvas.
Problem 1. Principal Component Analysis. Consider the following dataset:
x y
0 1
1 1
2 1
2 3
3 2
3 3
4 5
(a) Standardize the data and derive the two principal components in sorted order. What
is the new transformed dataset using the first principal component?
(b) Repeat the previous analysis but this time do not standardize the original data. Is
Principal Component Analysis scale invariant?
Problem 2. k-means is sub-optimal. Recall that in class we defined the k-means problem
as the task of minimizing the k-means objective:
min
c1,c2,··· ,ck
n∑
i=1
||xi − c(xi)||22, (1)
where c(xi) is the closest center to xi. In this problem, we aim to show that the k-means
algorithm does not always find the best solution of the above problem. For every numbe
t > 1, show that there exists an instance of the k-means problem for which the k-means
algorithm (might) find a solution whose objective value is at least t×OPT, where OPT is
the minimum k-means objective. In other words, you should find a set of points x1, · · · , xn
for which the k-means algorithm may (if initialized badly) output a set of centers whose
objective value is at least a factor t of the optimal value of problem (1).
1
Problem 3. Polynomial Regression. Load the dataset poly data.csv. The first column is a
vector of predictors x and the second column is a vector of responses y. Suppose we believe
it was generated by some polynomial of the predictors with Gaussian e
or, and we would
like to recover the true coefficients of the underlying process. A polynomial regression can be
estimated by including all powers of x as predictors in the model. For example, to estimate
a quadratic regression, we include the predictors x and x2 as well as t the intercept.
(a) Pick a set of polynomial models. Compute the k-fold cross validation e
or with respect
to mean squared e
or for each of these models. Report the value of k that you use
and plot the cross-validation e
or as a function of polynomial power.
(b) Choose a model from your initial set, and re-run on the entire data set. Report the
coefficients and make a scatter plot of x and y with your fitted polynomial. Justify
your selection.
Problem 4. Extra Credit Load the Labeled Faces in the Wild dataset from sklearn. You
can load this data as follows:
from sklearn.datasets import fetch lfw people
faces = fetch lfw people(min faces per person=60)
For this exercise, we will use PCA on image data, in particular pictures of faces, to ex-
tract features.
(a) Perform PCA on the dataset to find the first 150 components. Since this is a large
dataset, you should use randomized PCA instead, which can also be found on sklearn.
Show the eigenfaces associated with the first 1 through 25 principal components.
(b) Using the first 150 components you found, reconstruct a few faces of your choice and
compare them with the original input images.
2