Description

Deliverables:

1. Submit your predictions for the test sets to Kaggle as early as possible. Include your Kaggle scores in your write-up (see below). The Kaggle competition for this assignment can be found at:
   • https://www.kaggle.com/c/cs189-hw4-wine
2. Submit a PDF of your homework, with an appendix listing all your code, to the Gradescope assignment entitled “Homework 4 Write-Up”. In addition, please include, as your solutions to each coding problem, the specific subset of code relevant to that part of the problem. You may typeset your homework in LaTeX or Word (submit PDF format, not .doc/.docx format) or submit neatly handwritten and scanned solutions. Please start each question on a new page. If there are graphs, include those graphs in the correct sections. Do not put them in an appendix. We need each solution to be self-contained on pages of its own.
   • In your write-up, please state with whom you worked on the homework. • In your write-up, please copy the following statement and sign your signature next to it. (Mac Preview and FoxIt PDF Reader, among others, have tools to let you sign a PDF file.) We want to make it extra clear so that no one inadverdently cheats. “I certify that all solutions are entirely in my own words and that I have not looked at another student’s solutions. I have given credit to all external sources I consulted.”
3. Submit all the code needed to reproduce your results to the Gradescope assignment entitled “Homework 4 Code”. Yes, you must submit your code twice: in your PDF write-up following the directions as described above so the readers can easily read it, and once in compilable/interpretable form so the readers can easily run it. Do NOT include any data files we provided. Please include a short file named README listing your name, student ID, and instructions on how to reproduce your results. Please take care that your code doesn’t take up inordinate amounts of time or memory. If your code cannot be executed, your solution cannot be verified.

1          Logistic Regression with Newton’s Method

Consider sample points X₁, X₂,…, X_n ∈ R^d and associated values y₁,y₂,…,y_n ∈ {0,1}, an n × d design matrix X = [X₁ … X_n]^> and an n-vector y = [y₁ … y_n]^>.

If we add `₂-regularization to logistic regression, the cost function is

ⁿ                                           

X

J(w) = λ |w|2 − yi ln si + (1 − yi)ln(1 − si)

i=1

where s_i = s(X_i · w), s(γ) = 1/(1 + e^−γ), and λ > 0 is the regularization parameter. As in lecture, the vector s = [s₁ …         s_n]^> is a useful shorthand.

In this problem, you will use Newton’s method to minimize this cost function on the four-point, two-dimensional training set

                                         

X = 1010 1331,            y = 1001.

You may want to draw these points on paper to see what they look like. The y-vector implies that the first two sample points are in class 1, and the last two are in class 0.

These sample points cannot be separated by a linear decision boundary that passes through the origin. As described in lecture, append a 1 to each X_i vector and use a weight vector w ∈ R³ whose last component is the bias term (the term we call α in lecture).

1. Derive the gradient of the cost function J(w). Your final answer should be a simple matrixvector expression. While you may derive the matrix-vector form by first deriving the components of the gradient vector, do NOT write your answer in terms of these individual components.
2. Derive the Hessian of J(w). Again, your answer should be a simple matrix-vector expression.
3. State the update equation for one iteration of Newton’s method for this problem.

>

4. We are given a regularization parameter of λ = 0.07 and a starting point of w⁽⁰⁾ = ^h−2 1 0ⁱ . For the following four parts, you need only state the final solution. Thus you may derive the solution by hand or implement Newton’s algorithm and report the final result. If you do the latter, you do not need to submit code for this part.
   • State the value of s⁽⁰⁾ (the value of s before any iterations).
   • State the value of w⁽¹⁾ (the value of w after one iteration).
   • State the value of s⁽¹⁾.
   • State the value of w⁽²⁾ (the value of w after two iterations).

2          `<sub>1</sub>– and `₂-Regularization

Consider sample points X₁, X₂,…, X_n ∈ R^d and associated values y₁,y₂,…,y_n ∈ R, an n×d design matrix X = [X₁ … X_n]^> and an n-vector y = [y₁ … y_n]^>. For the sake of simplicity, assume that the sample data has been centered and whitened so that each feature has mean 0 and variance

>

1 and the features are uncorrelated; i.e., X X = nI. For this question, we will not use a fictitious dimension nor a bias term; our linear regression function will output zero for x = 0.

Consider linear least-squares regression with regularization in the `₁-norm, also known as Lasso. The Lasso cost function is

J(w) = |Xw − y|² + λ kwk₁

where w ∈ R^d and λ > 0 is the regularization parameter. Let w^∗ = argmin _w∈Rd J(w) denote the weights that minimize the cost function.

In the following steps, we will show that whitened training data decouples the features, so that w^∗_i is determined by the i^th feature alone (i.e., column i of the design matrix X), regardless of the other features. This is true for both Lasso and ridge regression.

1. We use the notation X_∗i to denote column i of the design matrix X, which represents the i^th Write J(w) in the following form for appropriate functions g and f.

d

X

J(w) = g(y) +           f(X_∗i,w_i,y,λ)

i=1

2. If w^∗_i > 0, what is the value of w^∗_i ?
3. If w^∗_i < 0, what is the value of w^∗_i ?
4. Considering parts 2 and 3, what is the condition for w^∗_i to be zero?
5. Now consider ridge regression, which uses the `₂ regularization term λ |w|². How does this change the function f(·) from part 1? What is the new condition in which w^∗_i = 0? How does it differ from the condition you obtained in part 4?

3          Regression and Dual Solutions

1. For a vector w, derive ∇ |w|⁴. Then derive ∇_w |Xw − y|⁴.
2. Consider sample points X₁, X₂,…, X_n ∈ R^d and associated values y₁,y₂,…,y_n ∈ R, an n × d design matrix X = [X₁ … X_n]^> and an n-vector y = [y₁ … y_n]^>, and the regularized regression problem

w^∗ = argmin |Xw − y|⁴ + λ |w|²,

w∈Rd

which is similar to ridge regression, but we take the fourth power of the error instead of the squared error. (It is not possible to write the optimal solution w^∗ as the solution of a system of linear equations, but it can be found by gradient descent or Newton’s method.)

Show that the optimum w^∗ is unique. By setting the gradient of the objective function to zero, show that w^∗ can be written as a linear combination w^∗ = ^Pn_i=1 a_iX_i for some scalars a₁,…,a_n. Write the vector a of dual coefficients in terms of X, y, λ, and the optimal solution w∗.

3. Consider the regularized regression problem

n

1

∗ X > ,y_i) + λ |w|2 w = argmin L(w X_i

w∈Rd             n i=1

where the cost function L is convex in its first argument. Prove that the optimal solution has the form w^∗ = ^Pn_i=1 a_iX_i. If the cost function is not convex, does the optimal solution always have the form w^∗ = ^Pn_i=1 a_iX_i? Justify your answer.

4          Wine Classification with Logistic Regression

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

For this homework, you need to do the following.

1. Derive and write down the batch gradient descent update equation for logistic regression with `₂ (Not Newton’s method, but the slower batch gradient descent.)

Choose a reasonable regularization parameter value and a reasonable learning rate. Run your algorithm and plot the cost function as a function of the number of iterations. (As this is batch descent, one “iteration” should use every sample point once.)

2. Derive and write down the stochastic gradient descent update equation for logistic regression with `₂ Choose a suitable learning rate. Run your algorithm and plot the cost function as a function of the number of iterations—where now each “iteration” uses just one sample point.

Comment on the differences between the convergence of batch and stochastic gradient descent.

3. Instead of a constant learning rate , repeat part 2 where the learning rate decreases as ∝ 1/t for the t^th Plot the cost function vs. the number of iterations. Is this strategy better than having a constant ?
4. Finally, train your classifier on the entire training set. Submit your results to Kaggle. Your classifier, when given the test points, should output a CSV file. (There is a sample one on Kaggle.) You’ll upload this CSV file to Kaggle where it’ll be scored with both a public test set, and a private test set. You will be able to see only your public score. You can only submit twice per day, so get started early! In your writeup, for this problem, report your Kaggle username, the best score you achieved on Kaggle, and a short writeup describing what you did to achieve that score.

IMPORTANT: Do NOT use any software package for logistic regression that you didn’t write yourself!

5          Real World Spam Classification

Motivation: After taking CS 189 or CS 289A, students should be able to wrestle with “real-world” data and problems. These issues might be deeply technical and require a theoretical background, or might demand specific domain knowledge. Here is an example that a past TA encountered.

Daniel (a past CS 189 TA) interned as an anti-spam product manager for an email service provider. His company uses a linear SVM to predict whether an incoming spam message is spam or ham. He notices that the number of spam messages received tends to spike upwards a few minutes before and after midnight. Eager to obtain a return offer, he adds the timestamp of the received message, stored as number of milliseconds since the previous midnight, to each feature vector for the SVM to train on, in hopes that the ML model will identify the abnormal spike in spam volume at night. To his dismay, after testing with the new feature, Daniel discovers that the linear SVM’s success rate barely improves.

Why can’t the linear SVM utilize the new feature well, and what can Daniel do to improve his results? Daniel is unfortunately limited to only a quadratic kernel. This is an actual interview question Daniel received for a machine learning engineering position!

Write a short explanation. This question is open ended and there can be many correct answers.