Due:  Friday, February 24th by 11:59pm

Homework submission:  Please submit your homework as a pdf on Canvas.

Problem 1 (Training Error vs. Test Error, ESL 2.9, 20 points)

In this problem, we want to use the least squares estimator to illustrate the point that the trainning error is generally an underestimate of the prediction error (or test error).

Consider a linear regression model with p parameters,

y = Xβ + ϵ, where ϵi  N(0,σ2 ).

We fit the model by least squares to a set of trainning data (x1 ,y1 ), . . . , (xN ,yN ) drawn independently from a population.  Let βˆ be the least squares estimate obtained from the training data.  Suppose we have some test data (1 , y˜1 ), ··· , (M , y˜M ) (N ≥ M > p) drawn at random from the same population as the training data.  If Rtr (β) =  对(yi − βT xi )2  and Rte (β) =  对(y˜i − βT i )2 , prove that

E[Rtr (βˆ)] ≤ E[Rte (βˆ)],

where the expectations are over all that is random in each expression.

Problem 2 (kNN-Regression, 20 points)

Suppose that the true relationship between x and y is given by

Yi  = f(Xi ) + ϵi ,   i = 1, 2, . . . ,n,

where ϵi  is white noise (independent) with E[ϵi] = 0 and Var[ϵ]i  = σ 2 .  Consider the generic kNN regression model

fˆ(x) =      工    yi ,                                                                      (1)

xi ∈Nk (x)

where Nk (x) is the neighborhood of x defined by the k closest points x, in the training sample.  Assuming x is not random, derive an expression of prediction error using squared error loss, i.e., compute and simplify

E[(Y − fˆk (x0 ))2 |X = x0].

Note that x0  is a single query point (or test point).

Problem 3 (K-Means Clustering Proof, 20 points)

Consider the traditional k-means clustering algorithm and let d(xi ,xj ) be squared Euclidean distance.  Prove the following identity:

   工    工  d(xi ,xj ) = |Nℓ | 工  d(xi , xk ),

C(i)=k C(j)=ℓ                                       C(i)=k

More specifically, prove

 Ck C k (xim − xjm )2  = 2 Ck (xim − km )2

where

km  =  Ck xim .

Note:

• The syntax C(i) = k, or equivalently {i : C(i) = k}, represents the set of all indices (or observations) having cluster assignment k .  The symbol |Nk | represents the number of elements in set {i : C(i) = k}. For example, suppose our data matrix consists of n = 10 observations and each observation (or row) is assigned to K = 3 clusters

Case:  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Cluster Assignment:  {3, 1, 3, 1, 2, 2, 2, 1, 3, 2}

Then

{i : C(i) = 1} = {2, 4, 8}    |N1 | = 3

{i : C(i) = 2} = {5, 6, 7, 10} |N2 | = 4

{i : C(i) = 3} = {1, 3, 9}    |N3 | = 3

Problem 4 (PCA, LDA and Logistic Regression, 20 points)

The zipcode data are high dimensional, and hence linear discriminant analysis suffers from high variance.  Using the training and test data for the 3s, 5s, and 8s, compare the following procedures:

1.  LDA on the original 256 dimensional space.

2.  LDA on the leading 49 principle components of the features.

3.  Multiple linear logistic regression (multinomial regression) using the same filtered data as in the previous question.

Note:

•  For all the above exercises, use R or Python functions to perform the PCA, LDA and multinomial regression, i.e., there is no need to manually code these procedures.

•  For all the above exercises, compare the procedures with respect to training and test misclassification error. You need to report both training and test misclassification error in your submission.

• When evaluating the test error based on the filtered trained model, don’t forget to first project the test features onto space generated by the leading 49 principle components.  In R use the predict() function.

• The data of interest is already split into a training and testing set.