[SOLVED] CS189-Homework 4 Logistic Regression with Newton’s Method and Wine Classification with Logistic Regression

Description

1        Logistic Regression with Newton’s Method

Given examples x₁,x₂,…,x_n ∈ R^d and associated labels y₁,y₂,…,y_n ∈ {0,1}, the cost function for unregularized logistic regression is

ⁿ                                           

X

J(w) , −  yi ln si + (1 − yi)ln(1 − si)

i=1

where s_i , s(x_i · w), w ∈ R^d is a weight vector, and s(γ) , 1/(1 + e^−γ) is the logistic function.

Define the n × d design matrix X (whose i^th row is x^>_i ), the label n-vector y , [y₁ … y_n]^>, and s , [s₁ … s_n]^>. For an n-vector a, let lna , [lna₁ … lna_n]^>. The cost function can be rewritten in vector form as J(w) = −y · lns − (1 − y) · ln(1 − s).

Hint: Recall matrix calculus identities_xz y; ∇_xf(y) =

; and(whereC is a constant matrix).

• Derive the gradient ∇_wJ(w) of cost J(w) as a matrix-vector expression. Also derive all intermediate derivatives in matrix-vector form. Do NOT specify them in terms of their individual components.
• Derive the Hessian) for the cost function J(w) as a matrix-vector expression.
• Write the matrix-vector update law for one iteration of Newton’s method, substituting the gradient and Hessian of J(w).
• You are given four examples x₁ = [0.2 3.1]^>,x₂ = [1.0 3.0]^>,x₃ = [−0.2 1.2]^>,x₄ = [1.0 1.1]^> with labels y₁ = 1,y₂ = 1,y₃ = 0,y₄ = 0. These points cannot be separated by a line passing through origin. Hence, as described in lecture, append a 1 to each x_i∈[4] and use a weight vector w ∈ R³ whose last component is the bias term (called α in lecture). Begin

>

with initial weight w⁽⁰⁾ = ^h−1 1 0ⁱ . For the following, state only the final answer with four digits after the decimal point. You may use a calculator or write a program to solve for these, but do NOT submit any code for this part.

• State the value of s⁽⁰⁾ (the initial value of s).
• State the value of w⁽¹⁾ (the value of w after 1 iteration).
• State the value of s⁽¹⁾ (the value of s after 1 iteration).
• State the value of w⁽²⁾ (the value of w after 2 iterations).

2        Wine Classification with Logistic Regression

The wine dataset data.mat consists of 6,497 sample points, each having 12 features. The description of these features is provided in data.mat. The dataset includes a training set of 6,000 sample points and a test set of 497 sample points. Your classifier needs to predict whether a wine is white (class label 0) or red (class label 1).

Begin by normalizing the data with each feature’s mean and standard deviation. You should use training data statistics to normalize both training and validation/test data. Then add a fictitious dimension. Whenever required, it is recommended that you tune hyperparameter values with crossvalidation.

Please set a random seed whenever needed and report it.

Use of automatic logistic regression libraries/packages is prohibited for this question. If you are coding in python, it is better to use scipy.special.expit for evaluating logistic functions as its code is numerically stable, and doesn’t produce NaN or MathOverflow exceptions.

• Batch Gradient Descent Update. State the batch gradient descent update law for logistic regression with `<sub>2</sub> As this is a “batch” algorithm, each iteration should use every training example. You don’t have to show your derivation. You may reuse results from your solution to question 4.1.
• Batch Gradient Descent Code. Choose reasonable values for the regularization parameter and step size (learning rate), specify your chosen values, and train your model from question 3.1. Plot the value of the cost function versus the number of iterations spent in training.
• Stochastic Gradient Descent (SGD) Update. State the SGD update law for logistic regression with `₂ Since this is not a “batch” algorithm anymore, each iteration uses just one training example. You don’t have to show your derivation.
• Stochastic Gradient Descent Code. Choose a suitable value for the step size (learning rate), specify your chosen value, and run your SGD algorithm from question 3.3. Plot the value of the cost function versus the number of iterations spent in training.

Compare your plot here with that of question 3.2. Which method converges more quickly? Briefly describe what you observe.

• Instead of using a constant step size (learning rate) in SGD, you could use a step size that slowly shrinks from iteration to iteration. Run your SGD algorithm from question 3.3 with a step size _t = δ/t where t is the iteration number and δ is a hyperparameter you select empirically. Mention the value of δ chosen. Plot the value of cost function versus the number of iterations spent in training.

How does this compare to the convergence of your previous SGD code?

• Kaggle. Train your best classifier on the entire training set and submit your prediction on the test sample points to Kaggle. As always for Kaggle competitions, you are welcome to add or remove features, tweak the algorithm, and do pretty much anything you want to improve your Kaggle leaderboard performance except that you may not replace or augment logistic regression with a wholly different learning algorithm. Your code should output the predicted labels in a CSV file.

Report your Kaggle username and your best score, and briefly describe what your best classifier does to achieve that score.

3        A Bayesian Interpretation of Lasso

Suppose you are aware that the labels y_i∈[n] corresponding to sample points x_i∈[n] ∈ R^d follow the density law ,w) , √1            e−(y−w·x)²/(2σ²) f(y|x

σ    2π

where σ > 0 is a known constant and w ∈ R^d is a random parameter. Suppose further that experts have told you that

• each component of w is independent of the others, and
• each component of w has the Laplace distribution with location 0 and scale being a known constant b. That is, each component w_i obeys the density law f(w_i) = e^−|wi|/b/(2b).

Assume the outputs y_i∈[n] are independent from each other.

Your goal is to find the choice of parameter w that is most likely given the input-output examples (x_i,y_i)_i∈[n]. This method of estimating parameters is called maximum a posteriori (MAP); Latin for “maximum [odds] from what follows.”

1. Derive the posterior probability density law f(w|(x_i,y_i)_i∈[n]) for w up to a proportionality constant by applying Bayes’ Theorem and using the densities f(y_i|x_i,w) and f(w). Don’t try to derive an exact expression for f(w|(x_i,y_i)_i∈[n]), as it is very involved.
2. Define the log-likelihood for MAP as `(w) , ln f(w|x_i∈[n],y_i∈[n]). Show that maximizing the MAP log-likelihood over all choices of w is the same as minimizing ^Pn_i=1(y_i −w·x_i)² +λkwk₁ where kwk₁ = ^Pd_j=1 |w_j| and λ is a constant.

4        `<sub>1</sub>-regularization, `₂-regularization, and Sparsity

You are given a design matrix X (whose i^th row is sample point x^T_i ) and an n-vector of labels y , [y₁ … y_n]^T. For simplicity, assume X is whitened, so X^>X = nI. Do not add a fictitious dimension/bias term; for input 0, the output is always 0. Let x_∗i denote the i^th column of X.

1. The `_p-norm for w ∈ R^d is defined as ||w||_p = (^P_i^d₌₁ |w_i|^p)^1p , where p > 0. Plot the isocontours with w ∈ R², for the following:

(a) `<sub>0.5</sub>           (b) `₁           (c) `₂

Use of automatic libraries/packages for computing norms is prohibited for the question.

2. Show that the cost function for `₁-regularized least squares, J₁(w) , kXw − yk² + λkwk₁ (where λ > 0), can be rewritten as J₁(w) = kyk² ) where f(·, ·) is a suitable function whose first argument is a vector and second argument is a scalar.
3. Using your solution to part 2, derive necessary and sufficient conditions for the i^th component of the optimizer w^∗ of J₁(·) to satisfy each of these three properties: w^∗_i > 0,w^∗_i = 0, and w^∗_i < 0.
4. For the optimizer w^# of the `₂-regularized least squares cost function J₂(w) , kXw − yk² + λkwk² (where λ > 0), derive a necessary and sufficient condition for w^#_i = 0, where w^#_i is the ith component of w^#.
5. A vector is called sparse if most of its components are 0. From your solution to part 3 and 4, which of w^∗ and w^# is more likely to be sparse? Why?