Please complete the exercises below.

This homework is due Wednesday, Feb 21, at 8:00 am.  Please upload your solution as a pdf file on Courseworks.

Late assignments: For assignments that are submitted within 24 hours of deadline, your grade on the assignment will be calculated by your actual grade on the assignment  ×70%.  No assignments will be accepted after 24 hours past the original deadline unless under extenuating circumstances.

Problem 1:  Risk (30 points)

The following questions all consider a binary classifier f : Rd  → {−1, 1}.

(a) To calculate the risk R(f), what function(s) do you need to know, and why? An acceptable answer can write down the form of risk R(f) and describe the components.

(b)  Do most machine learning algorithms use risk R(f) or empirical risk R(ˆ)n (f)? Please explain.

(c)  If the training data {(˜(x)1 , ˜(y)1 ), ··· , (˜(x)n , ˜(y)n )} for a fixed classifier f are n i.i.d.  draws from the true underlying distribution of the data, what is

nl R(f) − R(ˆ)n (f)'?

Please make a simple argument; no proof is required.

Note: You may assume that R(f) is well behaved such that questions of convergence are all appropriately satisfied. You may also use results from elementary probability.

(d)  Under the usual 0 − 1 loss, what is the range of R(f)?  With this answer, interpret R(f) in words as a probability (one sentence will suffice).

(e) Training procedure 1 chooses linear classifier f1  entirely at random. Now the risk R(f1 ) is a random variable (a function of the random linear classifier f1 ). What is E[R(f1 )] under the 0 − 1 loss?

(f) Training procedure 2 uses the Perceptron to choose a linear classifier f2  according to a training set {(˜(x)1 , ˜(y)1 ), ··· , (˜(x)n , ˜(y)n )} drawn i.i.d. from the true underlying distribution. By analogy to the previous part, you can consider that training procedure 2 chooses linear classifiers f2  better than entirely at random. Do you expect E[R(f2 )] to be larger or smaller than E[R(f1 )], again under the same 0 − 1 loss?

Problem 2:  Bayes Classifier (35 points)

Consider the binary classification problem with the training data set {(x(˜)1 , ˜(y)1 ), (x(˜)2 , ˜(y)2 ), ··· , (x(˜)n , ˜(y)n )}. For

each observation, the class label ˜(y)i  ∈ {+1, −1}, and the feature x(˜)i  ∈ R2 .  We write x(˜)i  = (˜(x) , ˜(x)).

(a) Assume that we know the class-conditional distributions of the data: p(x|y = +1) is Gaussian with mean vector µ+  and covariance matrix Σ+  and p(x|y = −1) is Gaussian with mean vector µ−  and covariance matrix Σ − . Write down the maximum likelihood estimators of µ+ ,µ − , Σ+ , Σ − .