Write your solutions to the following problems by either typing them up or handwriting them on another piece of paper. Homeworks are due to Gradescope by 11:59pm PT on the due date. You can use a slip day to extend the deadline by 24 hours. Make sure to correctly assign pages to Gradescope when submitting.

Homework will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically.  You should always explain and justify your conclusions, using sound reasoning.  Your goal should be to convince the reader of your assertions.  If a question does not require explanation, it will be explicitly stated.

Homeworks  should be written  up  and turned  in by each  student  individually.   You  may talk to other students in the class about the problems and discuss solution strategies,  but you should not share any written communication and you should not check answers with classmates. You can tell someone how to do a homework problem, but you cannot show them how to do it.

For each problem you submit, you should cite your sources by including a list of names of other students with whom you discussed the problem. Instructors do not need to be cited.

This homework will be graded out of 48 points. The point value of each problem or sub-problem is indicated by the number of avocados shown.

Note: Problems 2, 3, and 4 refer to a supplemental Jupyter Notebook, which can be found at this link.

Problem 1. Vector Calculus Involving Matrices

Let X  be a fixed matrix of dimension m  × n, and let w⃗  ∈ Rn .  In this problem, you will show that the gradient of w⃗T X T X ⃗w with respect to w⃗ is given by

d 

as we used in Lecture 8.

Let ⃗T1 ,⃗T2 , . . . ,⃗Tm  be the column vectors in Rn  that come from transposing the rows of X . For example,

if X = ], then ⃗T1  =   and ⃗T2  =   .

a)   Show that, for arbitrary X  and w⃗ , we can write

m

w⃗T X T X ⃗w = 之(⃗Ti(T)w⃗)2 .

i=1

Hint:  First, show that we can write w⃗T X T X ⃗w as a dot product of two vectors. Then, try and re-write those vectors in terms of ⃗T1 ,⃗T2 , . . . ,⃗Tm  and w⃗ .

m

w⃗T X T X ⃗w = 之(⃗Ti(T)w⃗)2

i=1

we can apply the chain rule, along with the result of part (a) above, to conclude that

 (w⃗T X T X ⃗w) =  2(⃗ri(T)w⃗)  (⃗ri(T)w⃗)

m

= 工 2(⃗ri(T)w⃗)⃗ri

i=1

b)   Next, show that, for arbitrary X  and w⃗ , we can write

m

2XT X ⃗w = 工 2(⃗ri(T)w⃗)⃗ri

i=1

Hint 1:  Suppose A is a matrix and ⃗v is a vector, and that the product A⃗v is well-defined.  How can we write the product A⃗v as a sum involving the columns of A and elements of ⃗v?

Hint 2:  It is likely that you’ll need to use one of your intermediate results from part (a).

Since you’ve shown that  (w⃗T X T X ⃗w) and 2XT X ⃗w are both equal to the same expression, 之 2(⃗ri(T)w⃗)⃗ri , you have proven that they are equal to one another, i.e. that

d 

as desired.

Problem 2. Billy’s Back!

This problem is formatted slightly differently. It is entirely contained in the supplemental Jupyter Notebook, which can be found at this link. However, you will not submit your code — instead, each subpart tells you what to include in your PDF writeup.

Note that the problem is worth 18 points total, split across 6 parts.

Problem 3. Sums of Residuals

Let’s start by recalling the idea of orthogonality from linear algebra. This will allow us to prove a powerful result regarding linear regression, starting in part (b).

Two vectors are orthogonal if their dot product is 0, i.e. for ⃗a,  ∈ Rn :

⃗aT  = 0  =⇒   ⃗a,  are orthogonal

Orthogonality is a generalization of perpendicularity to multiple dimensions.  (Two orthogonal vectors in 2D meet at a right angle.)

Suppose we want to represent the fact that some vector  is orthogonal to many vectors ⃗a1 , ⃗a2 , ..., ⃗ad  all at once. It turns out that we can do this by creating a new n × d matrix A whose columns are the vectors ⃗a1 , ⃗a2 , ..., ⃗ad , and writing AT  = 0.

For instance, suppose ⃗a1  =  「(l)2 , ⃗a2  =  「(l) , and  =  「(l)1 . Then,

Note that the product AT  involves taking the dot product of each row in AT  with . If AT  is a vector of all 0s, i.e. the 0 vector, then it is the case that  is orthogonal to each row of AT , and hence orthogonal to each column of A .

(We will not use this fact in this class, but if AT  = 0, it also means that  is orthogonal to the column space of A .)

a)   In the example above, verify that  is orthogonal to the columns of A .

l 1 」

b)           Suppose  is a vector in Rn  containing the value 1 for each element, i.e.   =    1    「.1(.).  .

lb1」

Hint:  This subpart should not take much time, so let us know if you’re stuck on it.  Try making up an example  and see what T  evaluates to, before generalizing your result to arbitrary .

c)   Now, consider the multiple regression scenario where X  is a n × (d + 1) design matrix, ⃗y ∈ Rn

is an observation vector, and w *  ∈ R(d+1)  is the optimal parameter vector.

Show that the error vector, ⃗y − X ⃗w* , is orthogonal to the columns of X .

Hint:  Again, this should not take very long.  Start with the normal equations, X T X ⃗w*  = X T ⃗y, use the distributive property of matrix multiplication, and use what you learned in part (a).

d)   We define the ith residual to be the difference between the actual and predicted values for individual i in our data set. In other words, the ith residual ei  is

ei  = yi − H* (⃗xi ) = (⃗y − X ⃗w* )i

(Note that (⃗y − X ⃗w* )i  is referring to element i of the vector ⃗y − X ⃗w* .  Also, we use the letter e for residuals because residuals are also known as errors.)

Using what you learned in parts (a), (b), and (c), show that the residuals  of a multiple  linear regression prediction rule with an intercept term sums to 0, i.e. that 对 ei  = 0.

Note:  If you want to see an example of this fact, look at the “Supplement for Problem 3” portion of the supplemental Jupyter Notebook, which can be found at this link.

e)   Now suppose our multiple linear regression prediction rule does not have an intercept term, i.e. that our prediction rule is of the form H(⃗x) = w1 x(1) + w2 x(2) + ... + wd x(d) .

1. Is it still guaranteed that 对 ei  = 0? Why or why not?

2. Is it still possible that 对 ei  = 0?  If you believe the answer is yes, come up with a simple example where a prediction rule without an intercept has residuals that sum to 0. If you believe the answer is no, state why.

Problem 4. Least Absolute Deviation Regression for Multiple Variables

In Lectures 8, 9, and  10, we explored least squares regression and derived the general solution for least squares regression with multiple parameters, also known as the normal equations:

X T X ⃗w*  = X T ⃗y,

where X  is the design matrix, ⃗y is the observation vector, and w⃗ is the parameter vector.

In this problem, we are going to try and expand our concept of least absolute deviation (LAD) regression from Homework 3 to accommodate linear prediction rules with two features.

This time, instead of data in R2 , you will be given data in R3 . Now that we have added an extra dimension to our data, we are no longer solving for a regression line, but rather a regression plane of the form H(⃗x) = w0 +w1 x(1) +w2 x(2) . In order to use notation that is more convenient and more similar to what you’ve seen in earlier coursework, let’s suppose we’re trying to find a regression plane of the form

z = H(x,y) = ax + by + c

When performing LAD regression, our loss function is absolute loss.  That means that we’re trying to find the a , b, and c that together minimize mean absolute error,

Rabs (a,b,c) =   |zi − (axi + byi + c)|

(Here, zi  represents the ith output value.)

We will adopt a strategy similar to Homework 3 to solve for the LAD regression plane. Recall the theorem from last week: If you have a data set with n data points in Rk , where k ≤ n, then one of the optimal LAD regression prediction rules must pass through k data points.

Since our data will be in R3 , we will generate all possible unique triplets of points and calculate the coefficients a , b, and c that define a plane of the form z = ax + by + c that goes through the three points in our triplet. Then we’ll just select which a,b,c triplet among these finite options has the smallest value of Rabs (a,b,c). This is guaranteed by the theorem to be an optimal LAD regression plane.

a)   Before implementing the above strategy in code, let’s get familiar with the process by doing an example by hand. Let’s say we have three points, A =  「(l) , B =  「(l)1 , and C =  「(l)2 .

Given these three points in R3 , compute the equation of the plane going through them, giving your answer in the form z = ax + by + c .

Note:  You may need to review some concepts from multivariable calculus (i.e. Math 20C) to do this problem. Here is a nice summary and some examples, obtained from MIT OpenCourseWare under a Creative Commons License.

Hint:  After reading the linked notes, a good first step may be to compute A⃗B, the difference between points A and B, and A⃗C, the difference between the points A and C, and take their cross product.

b)   Now, we’ll find the LAD regression plane, again for Billy’s tip dataset that you worked on in Problem 2.

Recall from the problem description the procedure outlined to generate an optimal LAD regression plane.   In the supplemental Jupyter Notebook, found at  this  link, we’ve already defined several functions for you: