Notes: (1) These questions require thought, but do not require long answers. Please be as concise as possible. (2) If you have a question about this homework, we encourage you to post your question on our Piazza forum, at https://piazza.com/class#fall2012/cs229. (3) If you missed the first lecture or are unfamiliar with the collaboration or honor code policy, please read the policy on Handout #1 (available from the course website) before starting work. (4) For problems that require programming, please include in your submission a printout of your code (with comments) and any figures that you are asked to plot. (5) Please indicate the submission time and number of late dates clearly in your submission.

SCPD students: Please email your solutions to [email protected] with the subject line Problem Set 1 Submission. If you are writing your solutions out by hand, please write clearly and in a reasonably large font using a dark pen to improve legibility.

1.Logistic regression

(a) [10 points] Consider the log-likelihood function for logistic regression:

m

() = Xy⁽ⁱ⁾ logh(x⁽ⁱ⁾) + (1 y⁽ⁱ⁾)log(1 h(x⁽ⁱ⁾))

i=1

Find the Hessian H of this function, and show that for any vector z, it holds true that

z^THz 0.

[Hint: You might want to start by showing the fact that Pi Pj z_ix_ix_jz_j = (x^Tz)²

0.]

Remark: This is one of the standard ways of showing that the matrix H is negative semi-definite, written H 0. This implies that is concave, and has no local maxima other than the global one.^[1] If you have some other way of showing H 0, youre also welcome to use your method instead of the one above.

• [10 points] On the Leland system, the files /afs/ir/class/cs229/ps/ps1/q1x.dat and /afs/ir/class/cs229/ps/ps1/q1y.dat contain the inputs (x⁽ⁱ⁾ R^[2]) and outputs (y⁽ⁱ⁾ {0,1}) respectively for a binary classification problem, with one training example per row. Implement² Newtons method for optimizing (), and apply it to fit a logistic regression model to the data. Initialize Newtons method with = ~0 (the vector of all zeros). What are the coefficients resulting from your fit? (Remember to include the intercept term.)
• [5 points] Plot the training data (your axes should be x₁ and x₂, corresponding to the two coordinates of the inputs, and you should use a different symbol for each point plotted to indicate whether that example had label 1 or 0). Also plot on the same figure the decision boundary fit by logistic regression. (I.e., this should be a straight line showing the boundary separating the region where h(x) > 0.5 from where h(x) 0.)

2. Locally weighted linear regression

Consider a linear regression problem in which we want to weight different training examples differently. Specifically, suppose we want to minimize

.

In class, we worked out what happens for the case where all the weights (the w⁽ⁱ⁾s) are the same. In this problem, we will generalize some of those ideas to the weighted setting, and also implement the locally weighted linear regression algorithm.

• [2 points] Show that J() can also be written

J() = (X ~y)^TW(X ~y)

for an appropriate diagonal matrix W, and where X and ~y are as defined in class. State clearly what W is.

• [7 points] If all the w⁽ⁱ⁾s equal 1, then we saw in class that the normal equation is

X^TX = X^T~y,

and that the value of that minimizes J() is given by (X^TX)¹X^T~y. By finding the derivative J() and setting that to zero, generalize the normal equation to this weighted setting, and give the new value of that minimizes J() in closed form as a function of X, W and ~y.

• [6 points] Suppose we have a training set {(x⁽ⁱ⁾,y⁽ⁱ⁾); i = 1,m} of m independent examples, but in which the y⁽ⁱ⁾s were observed with differing variances. Specifically, suppose that

I.e., y⁽ⁱ⁾ has mean ^Tx⁽ⁱ⁾ and variance (⁽ⁱ⁾)² (where the ⁽ⁱ⁾s are fixed, known, constants). Show that finding the maximum likelihood estimate of reduces to solving a weighted linear regression problem. State clearly what the w⁽ⁱ⁾s are in terms of the (i)s.

• On the Leland computer system, the files /afs/ir/class/cs229/ps/ps1/q2x.dat and /afs/ir/class/cs229/ps/ps1/q2y.dat contain the inputs (x⁽ⁱ⁾) and outputs (y⁽ⁱ⁾) for a regression problem, with one training example per row.
  1. Implement (unweighted) linear regression (y = ^Tx) on this dataset (using the normal equations), and plot on the same figure the data and the straight line resulting from your fit. (Remember to include the intercept term.)
  2. Implement locally weighted linear regression on this dataset (using theweighted normal equations you derived in part (b)), and plot on the same figure the data and the curve resulting from your fit. When evaluating h() at a query point x, use weights

,

with a bandwidth parameter = 0.8. (Again, remember to include the intercept term.)

• [3 points] Repeat (ii) four times, with = 0.1,0.3,2 and 10. Comment briefly on what happens to the fit when is too small or too large.

3. ] Poisson regression and the exponential family (a) [5 points] Consider the Poisson distribution parameterized by :

.

Show that the Poisson distribution is in the exponential family, and clearly state what are b(y), , T(y), and a().

• Consider performing regression using a GLM model with a Poisson response variable. What is the canonical response function for the family? (You may use the fact that a Poisson random variable with parameter has mean .)
• For a training set {(x⁽ⁱ⁾,y⁽ⁱ⁾); i = 1,,m}, let the log-likelihood of an example be logp(y⁽ⁱ⁾|x⁽ⁱ⁾;). By taking the derivative of the log-likelihood with respect to _j, derive the stochastic gradient ascent rule for learning using a GLM model with Poisson responses y and the canonical response function.
• Consider using GLM with a response variable from any member of the exponential family in which T(y) = y, and the canonical response function for the family. Show that stochastic gradient ascent on the log-likelihood logp(~y|X,) results in the update rule _i := _i (h(x) y)x_i.

4. [15 points] Gaussian discriminant analysis

Suppose we are given a dataset {(x⁽ⁱ⁾,y⁽ⁱ⁾); i = 1,,m} consisting of m independent examples, where x⁽ⁱ⁾ Rⁿ are n-dimensional vectors, and y⁽ⁱ⁾ {0,1}. We will model the joint distribution of (x,y) according to:

Here, the parameters of our model are , , ₀ and ₁. (Note that while therere two different mean vectors ₀ and ₁, theres only one covariance matrix .)

• [5 points] Suppose we have already fit , , ₀ and ₁, and now want to make a prediction at some new query point x. Show that the posterior distribution of the label at x takes the form of a logistic function, and can be written

,

where is some appropriate function of ,,₀,₁. (Note: To get your answer into the form above, for this part of the problem only, you may have to redefine the x⁽ⁱ⁾s to be n + 1-dimensional vectors by adding the extra coordinate = 1, like we did in class.)

• [10 points] For this part of the problem only, you may assume n (the dimension of x) is 1, so that = [²] is just a real number, and likewise the determinant of is given by || = ². Given the dataset, we claim that the maximum likelihood estimates of the parameters are given by

m

1

m

i=1

The log-likelihood of the data is

m

i=1

By maximizing with respect to the four parameters, prove that the maximum likelihood estimates of , ₀,₁, and are indeed as given in the formulas above. (You may assume that there is at least one positive and one negative example, so that the denominators in the definitions of ₀ and ₁ above are non-zero.)

(c) Without assuming that n = 1, show that the maximum likelihood estimates of ,₀,₁, and are as given in the formulas in part (b). [Note: If youre fairly sure that you have the answer to this part right, you dont have to do part (b), since thats just a special case.]

5. Linear invariance of optimization algorithms

Consider using an iterative optimization algorithm (such as Newtons method, or gradient descent) to minimize some continuously differentiable function f(x). Suppose we initialize the algorithm at x⁽⁰⁾ = ~0. When the algorithm is run, it will produce a value of x Rⁿ for each iteration: x⁽¹⁾,x⁽²⁾,.

Now, let some non-singular square matrix A Rⁿⁿ be given, and define a new function g(z) = f(Az). Consider using the same iterative optimization algorithm to optimize g (with initialization z⁽⁰⁾ = ~0). If the values z⁽¹⁾,z⁽²⁾, produced by this method necessarily satisfy z⁽ⁱ⁾ = A¹x⁽ⁱ⁾ for all i, we say this optimization algorithm is invariant to linear reparameterizations.

• [9 points] Show that Newtons method (applied to find the minimum of a function) is invariant to linear reparameterizations. Note that since z⁽⁰⁾ = ~0 = A¹x⁽⁰⁾, it is sufficient to show that if Newtons method applied to f(x) updates x⁽ⁱ⁾ to x⁽ⁱ⁺¹⁾, then Newtons method applied to g(z) will update z⁽ⁱ⁾ = A¹x⁽ⁱ⁾ to z⁽ⁱ⁺¹⁾ = A¹x⁽ⁱ⁺¹⁾.^[3]
• [3 points] Is gradient descent invariant to linear reparameterizations? Justify youranswer.