Note: You may use any programming language and plotting software to complete Ex- ercise 2.  However, Python is recommended.  Please submit your code for full credit (answers and plots without code will only receive half credit).

Exercise  1 [40 points].  Mathematical Background

1.  (5 points) Let x e Rn and A, B e Rn xn . What is an equivalent expression to (xT AB)T ?

2.  (5 points) Consider the set of points }x e R2  : lxlp  = 1I.

(a) Plot this set of points for p = 2. This is the unit sphere in L2 .

(b)  On the same figure, plot the unit sphere in L1 .

(c) Again on the same plot, do the same for p = o.

(d) What do you notice about the unit spheres as p increases from 1 to o?

3.  (5 points) Let x, y e Rn .

(a) Express lx - yl2(2)  using the dot product.

(b) If you have not already done so in part (a), simplify your answer above as the

sum of three terms.

4.  (20 points) Consider the multivariate quadratic function     f (x) = xT  –0(1)   1(4)! x + – !2(1) T x + 1

(a) What is the gradient Vf (x)?

(b) What is the Hessian V2 f (x)?

(c) Is f (x) a convex function? Why or why not? (Hint┌ you may use any tool needed to calculate eigenvalues.)

5.  (5 points) Suppose we are solving a minimization problem. In class, we discussed two different examples of a type of iterative optimization algorithm called m之n| s|步+|| ,|i|← 。|s:  (1) steepest descent (gradient descent), and (2) Newton’s method.  In gradient descent, at every iteration n we need to calculate the gradient Vf evaluated at xn  in order to compute the next guess xn+1  = xn - αVf(xn ). When using Newton’s method to minimize a function f, at every iteration in addition to Vf(xn ) what additional information about f at xn  do we need to calculate in order to compute xn+1?  What are the advantages and disadvantages of using this extra information?

Exercise  2 [60 points].  Logistic Regression

1.  (10 points) Recall that in logistic regression, we have the model P (y = 1|x; θ) = g(θT x) =

(a)  Suppose x, θ e R. Plot hθ (x) = g(θT x) for θ = 1, 2, and 5 on the same plot. How does the shape of g change as θ increases? What is the shape of hθ (x) = g(θT x) in the limit θ → o?

(b) When the training data are linearly separable (there exists a line/hyperplane that

perfectly separates the labeled data into different classes), we will maximize the likelihood of the data when θ is chosen so that any positive distance from the decision boundary corresponds to P (y = 1|x; θ) = 1 and any negative distance corresponds to P (y = 1|x; θ) = 0. Another way to say this is that we want to find θ such that g(θT x) = 1 whenever θT x > 0, and g(θT x) = 0 whenever θT x < 0. What θ gives this model? (Hint: see plots above.)

● Note  this  shows  logistic  regression  does  not  converge  when  the training  data are  linearly  separable.   In practice, data are rarely lin- early separable, but there are also different ways to modify logistic regression to take the separable case into account, which we will return to when we discuss regularization.

2.  (20 points) Recall that for m datapoints (x(i), y(i)), where x e Rn  is the feature vector, y  e }0, 1I is the class label, and i = 1, ..., m is the index of the datapoint, the log likelihood for logistic regression is

m

l(θ) =       y(i) log hθ (x(i)) + (1 - y(i)) log(1 - hθ (x(i)))

i=1

where hθ (x(i)) = g(θT x(i)).

(a) Let m =  1 so that we consider only the log likelihood of the single datapoint

(x, y). Use the known fact that g\ (z) = g(z)(1 - g(z)) to show that

∂ 

Note that this gives us the jth  element of the gradient Vθ l.