Description

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, you’re 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² Newton’s method for optimizing ℓ(θ), and apply it to fit a logistic regression model to the data. Initialize Newton’s 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 there’re two different mean vectors µ₀ and µ₁, there’s 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

φ µ0 µ1 Σ

= = = =

1 y(i) = 1 m X {                      } i=1 m                      { (i) = 0}x(i) 1 y i=1 m                          { (i) = 0} 1 y Pi=1 m                      { (i) = 1}x(i) 1 y i=1 1 y Pmi=1 { (i) = 1} 1 Xm    (i) − µy(i))(x(i) − µy(i))T (x

1

m

i=1

The log-likelihood of the data is

m

ℓ(φ,µ0,µ1,Σ)	=	logYp(x(i),y(i);φ,µ0,µ1,Σ) i=1
	=	m logYp(x(i)|y(i);µ0,µ1,Σ)p(y(i);φ).

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 you’re fairly sure that you have the answer to this part right, you don’t have to do part (b), since that’s just a special case.]

5.  Linear invariance of optimization algorithms

Consider using an iterative optimization algorithm (such as Newton’s 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^n×n 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 Newton’s 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 Newton’s method applied to f(x) updates x⁽ⁱ⁾ to x⁽ⁱ⁺¹⁾, then Newton’s 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.