Suppose we’d like to fit the model \(\boxed{h(x_i) = w_0 + w_1 x_i + w_2 x_i^2}\) by minimizing mean squared error. We use an observation vector \(\vec y \in \mathbb{R}^n\), but instead of using the regular design matrix \(X\),
6 pts It turns out that \(\text{colsp}(Z) = \text{colsp}(X)\). To show this, fill in the blanks below to express \(\vec z^{(2)}\) (the third column of \(Z\)) as a linear combination of \(X\)’s columns. Each box should be filled with an expression involving \(\bar{x}\), \(n\), and/or constants.
(6 pts) In this part only, assume that the values \(x_1, x_2, …, x_n\) are each either 1 or 0. For some specific values \(x_1, x_2, …, x_n\), the matrix \(P\) that projects vectors in \(\mathbb{R}^n\) onto \(\text{colsp}(Z)\) is given by
What is the rank of \(Z\)? Give your answer as an integer. \(\text{rank}(Z) = \_\_\_\_\_\_\)
Which specific values of \(x_1, x_2, …, x_n\) result in \(P\) being the matrix above? Give your answer as a list of values, in the order \(x_1\), then \(x_2\), then \(x_3\), etc. (If there are multiple possible answers, just give one.)
Solution
First, \(\text{rank}(Z) = 2\). We’re told in part a) that \(\text{colsp}(Z) = \text{colsp}(X)\), so \(\text{rank}(Z) = \text{rank}(X)\). I find it easier to think in terms of \(X\) since the numbers are more straightforward.
Remember, throughout this part, that each \(x_i\) is either 1 or 0! This means that the column \(\vec x^{(1)} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\) is made up of 1’s and 0’s, and the column \(\vec x^{(2)} = \begin{bmatrix} x_1^2 \\ x_2^2 \\ \vdots \\ x_n^2 \end{bmatrix}\) is made up of 1’s and 0’s in the same positions, since \(1^2 = 1\) and \(0^2 = 0\).
So, \(X\) only really has two unique columns, and its rank is 2. But since \(\text{rank}(Z) = \text{rank}(X)\), we have \(\text{rank}(Z) = 2\). \(Z\) doesn’t have any repeated columns, but as we showed above, it’s still the case that one of \(Z\)’s columns is a linear combination of the other two.
The only case in which \(\text{rank}(Z) = 1\) is if all of the \(x_i\) are the same, but the matrix \(P\) tells us that that is not the case.
Let’s now look at the matrix \(P\). Notice that rows 1, 2, and 4 of \(P\) are identical, as are rows 3 and 5. Let’s imagine some vector \(\vec y \in \mathbb{R}^5\). What would multiplying \(P\) by \(\vec y\) give us?
We know from Chapter 1 that the mean is the constant that minimizes mean squared error. Here, it appears that the prediction returned in \(\vec y\) is not always the same, but is one of two possibilities — rows 1, 2, and 4 have the same prediction, and rows 3 and 5 have the same prediction. This hints to us that rows 1, 2, and 4 come from the same \(x_i\) value, and rows 3 and 5 come from the same \(x_i\) value, and the optimal prediction is some conditional mean. This resembles Lab 9, Activity 2, on one hot encoding with beef, chicken, and fish.
The above observation alone is enough information to answer the question. The two possible answers are \(\boxed{x_1 = 1, x_2 = 1, x_3 = 0, x_4 = 1, x_5 = 0}\) and \(\boxed{x_1 = 0, x_2 = 0, x_3 = 1, x_4 = 0, x_5 = 1}\).
Let’s dive deeper into the math to confirm this. Let’s start with what \(X\) would have had to be. (We can work with \(X\) instead of \(Z\) since both have the same column spaces, so projecting onto either column space will give us the same result; \(X\) is just easier to work with.) And, let’s drop \(\vec x^{(2)}\) from \(X\), since including it will prevent \(X^TX\) from being invertible while not changing \(\text{colsp}(X)\).
Note that I arbitrarily picked \(x_1 = x_2 = x_4 = 1\) and \(x_3 = x_5 = 0\), but we could reverse the 1’s and 0’s and \(P\) would turn out to be the same.
The formula for the projection matrix is \(P = X (X^TX)^{-1}X^T\). I won’t include all of the algebra here, but if you work out \(P = X (X^TX)^{-1}X^T\), you’ll find that \(P\) is indeed the matrix provided in the problem.
Here’s one final interpretation of what’s going on. Suppose the optimal parameters for this \(X\) and some \(\vec y\) are \(\vec w^{\ast} = \begin{bmatrix} w_0^{\ast} \\ w_1^{\ast} \end{bmatrix}\), which would lead to a hypothesis function of
$$ h(x_i) = w_0^* + w_1^* x_i $$
This hypothesis function only returns one of two values:
If \(x_i = 1\), then \(h(1) = w_0^{\ast} + w_1^{\ast}\)
If \(x_i = 0\), then \(h(0) = w_0^{\ast}\)
So, \(w_0^{\ast}\) is the mean of the \(y\)’s when \(x_i = 0\), and \(w_0^{\ast} + w_1^{\ast}\) is the mean of the \(y\)’s when \(x_i = 1\). This is exactly what we see in the matrix \(P\).
6 pts Let \(\vec \beta^{\ast} = \begin{bmatrix} \beta_0^{\ast} \\ \beta_1^{\ast} \\ \beta_2^{\ast} \end{bmatrix}\) be a solution to the normal equations for \(Z\) and \(\vec y\). Show that
$$ \beta_0^* = \bar{y} - \beta_2^* \sigma_x^2 $$
where \(\sigma_x^2 = \frac{1}{n} \sum_{i=1}^n (x_i - \bar{x})^2\) is the variance of the \(x\)’s, and \(\bar{y}\) is the mean of the \(y\)’s. Hint: Use the fact that \(\sum_{i = 1}^n (x_i - \bar{x}) = 0\). What is the error vector? Is it orthogonal to something useful?
Solution
The error vector is \(\vec e = \vec y - Z\vec \beta^{\ast}\). As we studied in depth, the error vector is orthogonal to every vector in \(\text{colsp}(Z)\), i.e. every linear combination of the columns of \(Z\). \(Z\) has a column of all 1’s, so the error vector is orthogonal to that, too.
$$ (\vec y - Z\vec \beta^*) \cdot \vec 1 = 0 $$
We’ll proceed by expanding \(Z \vec \beta^{\ast}\) and then plugging the result into the above. This will allow us to solve for \(\beta^{\ast}_0\).
Suppose we fit a multiple linear regression model with an intercept term that predicts the height of a wolverine given its weight and color. The model is fit by minimizing mean squared error.
a)
2 pts If we one hot encode the color feature without dropping any categories, the design matrix \(X\) has 6 columns.
How many unique colors are there? Give your answer as an integer with no variables.
There are \(\_\_\_\_\_\_\) unique colors.
Solution
The 6 columns are:
1 intercept column
1 weight column
1 column for each color after one hot encoding without dropping any categories
So the number of unique colors is
$$ 6 - 2 = \boxed{4} $$
b)
4 pts Assume that not all wolverines in the dataset have the same weight, and that there is at least one wolverine with each color.
What impact would dropping one of the color categories’ columns from the design matrix \(X\) have? Select all that apply.
It would decrease the rank of \(X\).
It would guarantee that \(X\) invertible.
It would guarantee that \(X^TX\) invertible.
It would guarantee the existence of a unique optimal parameter vector \(\vec w^{\ast}\).
It would change \(\text{nullsp}(X)\).
It would change \(\text{colsp}(X)\).
Solution
It would change \(\text{colsp}(X)\).
By dropping one of the color categories’ columns from the design matrix \(X\), we guarantee that the columns of \(X\) are linearly independent. As discussed in the course notes, when one hot encoding, the sum of all 4 color columns is equal to the intercept column (of all ones); by dropping one of the 4 color columns, we don’t lose any information but remove the linear dependence. (The other assumptions in the problem help guarantee this, too — for instance, if all of the wolverines in the dataset have the same weight, then the weight column is a scalar multiple of the intercept column.)
With that in mind, let’s look at the options:
It would decrease the rank of \(X\). False: \(\text{colsp}(X)\) doesn’t change, so \(\text{rank}(X)\) doesn’t change.
It would guarantee that \(X\) is invertible. False: \(X\) is not necessarily square!
It would guarantee that \(X^TX\) is invertible. True: If \(X\)’s columns are linearly independent, then \(X^TX\) is invertible, since \(\text{rank}(X) = \text{rank}(X^TX) = \text{# columns in } X^TX\).
It would gaurantee the existence of a unique optimal parameter vector \(\vec w^{\ast}\). True: If \(X\)’s columns are linearly independent, there is a unique \(\vec w^{\ast}\).
It would change \(\text{nullsp}(X)\): True. With the redundant column, \(X\) has a non-trivial null space, but without it, \(X\)’s null space is \(\lbrace \vec 0 \rbrace\).
It would change \(\text{colsp}(X)\): False, as discussed above.
Suppose we’d like to fit a multiple linear regression model without an intercept term to predict the number of fans in attendance at a Michigan football home game given various features.
For each row in the dataset, the corresponding feature vector is \(\vec x_i = \begin{bmatrix} \text{tempF}_i \\ \text{tempC}_i \\ \text{night}_i \\ \text{day}_i \end{bmatrix}\), where:
\(\text{tempF}_i\) is the temperature, in degrees Fahrenheit, at kickoff for game \(i\)
\(\text{tempC}_i\) is the temperature, in degrees Celsius, at kickoff for game \(i\)
\(\text{night}_i\) is 1 if game \(i\) is a night game and 0 otherwise
\(\text{day}_i\) is 0 if game \(i\) is a night game and 1 otherwise
We find optimal model parameters, \(\vec w^{\ast} = \begin{bmatrix} w_1^{\ast} \\ w_2^{\ast} \\ w_3^{\ast} \\ w_4^{\ast} \end{bmatrix}\), by solving the normal equation.
a)
4 pts The first two rows of the dataset have the following information:
Game 1: 77 degrees Fahrenheit, 25 degrees Celsius, not night game, 102,111 fans
Game 2: 59 degrees Fahrenheit, 15 degrees Celsius, night game, 101,982 fans
Write the first two rows of the design matrix, \(X\). Your answer should be a matrix with two rows and no variables.
\(X = \_\_\_\_\_\_\)
Solution
Each row of the design matrix is just the feature vector for that game:
where \(\text{tempC}_i = \frac{5}{9} (\text{tempF}_i - 32)\).
b)
4 pts Suppose \(\vec w’\) is one solution to the normal equation for this model. Which option describes the complete set of solutions to the normal equation?
If we add any vector in \(\text{nullsp}(X)\) to one solution of the normal equation, we get another solution. So we just need to find a non-zero vector in \(\text{nullsp}(X)\).
For any row of \(X\), the following two statements must be true:
In order to write this as a linear combination of \(X\)’s columns, the 32 needs to come from a vector that is “constant” across all rows. Fortunately, that’s true of the sum of the night and day columns, since \(\text{night}_i + \text{day}_i = 1\) for all rows. So, this means
6 pts First, assume \(h(\vec x_i)\) is the model at the top of the page.
What is the largest possible rank of the design matrix, \(X\)? (Note that we’re asking about the full design matrix, not just its first two rows.)
\(\text{largest possible value of }\text{rank}(X) = \_\_\_\_\_\_\)
True or False: The sum of the errors of the model’s predictions is 0.
True False
True or False: The sum of the errors of the model’s predictions on just the rows of the dataset corresponding to night games is 0.
True False
Solution
True False
Let \(\vec e = \vec y - X \vec w^{\ast}\) be the error vector. Since \(\vec w^{\ast}\) satisfies the normal equation, \(\vec e\) is orthogonal to every column of \(X\), and to every linear combination of those columns.
The largest possible rank of \(X\) is 3, which happens when the tempF, tempC, and night columns are linearly independent. When the day column is added, the columns become linearly dependent. (Equivalently, the tempF, night, and day columns are linearly independent, but linearly dependent with the tempC column.)
This is true. Even though there is no explicit intercept term (and thus, no column of all ones), the all-ones vector is still in \(\text{colsp}(X)\), because the night and day columns add up to 1 for each row.
After removing the day column, what is the largest possible rank of the new design matrix?
\(\text{largest possible value of }\text{rank}(\text{new design matrix}) = \_\_\_\_\_\_\)
True or False: The sum of the errors of the new model’s predictions is 0.
True False
True or False: The sum of the errors of the new model’s predictions on just the rows of the dataset corresponding to night games is 0.
True False
Solution
True False
Let \(\vec e_{\text{new}}\) be the error vector for the new model.
After removing the day column, the new design matrix has 3 columns, and there is no longer a forced linear dependence among them. So the largest possible rank is still 3. What’s new now is that \(X\)’s columns are all linearly independent, meaning there is a unique solution to the normal equation.
This is false. The normal equations still tell us that \(\vec e_{\text{new}}\) is orthogonal to each column of the new design matrix, but there is no guarantee that the all-ones vector is in the column space anymore. So the errors are not guaranteed to sum to 0.
This is true. The night indicator column is still present in the new design matrix, so \(\vec e_{\text{new}}\) is orthogonal to that column. Therefore, the sum of the errors over the night-game rows is still 0.
Suppose we’d like to fit a multiple linear regression model without an intercept term to predict an apartment’s monthly rent (in hundreds of dollars) using various features.
For apartment \(i\), the corresponding feature vector is \(\vec x_i = \begin{bmatrix} \text{bedrooms}_i & K_i & C_i & N_i \end{bmatrix}^T\), where \(\text{bedrooms}_i\) is the number of bedrooms in apartment \(i\), and \(K_i\), \(C_i\), and \(N_i\) are one hot encoded features for the Kerrytown, Central Campus, and North Campus neighborhoods, respectively.
The model is fit by minimizing mean squared error. All rows of the dataset are shown to the right. The model’s predictions, \(h(x_i)\), are shown, along with the true rents, \(y_i\). Several values are missing.
is \(\begin{bmatrix} 4 & 1 & 0 & 0 \end{bmatrix}\).
Find all four missing values in the table. Show your work, and write your final answers in the boxes provided. Your answers should be integers with no variables. Hint: Think about orthogonality.
Solution
For clarity, let’s start by writing out the full design matrix \(X\).
First, let’s take the dot product of the error vector with the second column of \(X\), the one hot encoded column for Kerrytown. We know this dot product must be \(0\).
Intuitively, this says that the errors for Kerrytown apartments must sum to \(0\). Since there is only one Kerrytown apartment, this means that its prediction must be correct.
Similarly, if we take the dot product of the error vector with the third column of \(X\), this tells us that the errors for the Central Campus apartments must sum to \(0\).
but this is not enough information to determine the values of (iii) and (iv). To get another equation, we can set the dot product of the error vector with the first column of \(X\) to \(0\).
Let \(X\) be the corresponding \(5 \times 3\) design matrix and \(\vec y \in \mathbb{R}^5\) be the corresponding observation vector. Suppose the matrix \(P\) that projects onto the column space of \(X\) is
4 ptsIn parts a) and b) only, suppose the projection of \(\vec y\) onto \(\text{colsp}(X)\) is \(\vec p = \begin{bmatrix} 3 \\ 3 \\ 3 \\ 3 \\ 3 \end{bmatrix}\). There are infinitely many such vectors \(\vec y\). State one possible vector \(\vec y\)whose five components are all different. Give your answer as a vector with no variables.
one possible vector \(\vec y =\) ______
Solution
For any vector \(\vec y\), multiplying by \(P\) averages the first four components of \(\vec y\) and leaves the fifth component unchanged:
We want this to equal \(\begin{bmatrix} 3 \\ 3 \\ 3 \\ 3 \\ 3 \end{bmatrix}\), so the first four components of \(\vec y\) need to have average 3, and the fifth component needs to be 3.
The first four components have average 3, and all five components are different. There are infinitely many possible answers, though.
b)
3 pts Let \(\vec y\) and \(\vec p \) be as defined in part (a). True or false: \(X^T (\vec p - \vec y) = \vec 0\).
True False
Solution
True False
This is true. If \(\vec p\) is the projection of \(\vec y\) onto \(\text{colsp}(X)\), then the error vector \(\vec y - \vec p\) is orthogonal to every vector in \(\text{colsp}(X)\). This is how we arrived at the normal equations, \(X^TX \vec w = X^T \vec y\). Here, this means
$$ X^T(\vec y - \vec p) = \vec 0 $$
Multiplying by \(-1\) gives
$$ X^T(\vec p - \vec y) = \vec 0 $$
For the rest of the problem, suppose that both \(\vec w^{\ast} = \begin{bmatrix} 2 \\ 3 \\ 1 \end{bmatrix}\) and \(\vec w’ = \begin{bmatrix} 3 \\ 1 \\ 0 \end{bmatrix}\) are both optimal parameter vectors that minimize mean squared error.
c)
4 pts Which of these vectors are in \(\text{nullsp}(X)\)? Select all that apply.
Where did this come from? The fact that \(\vec w’\) and \(\vec w^{\ast}\) are both optimal parameter vectors means that they both result in the same projection of \(\vec y\) onto \(\text{colsp}(X)\), so
$$ X \vec w^* = X \vec w' $$
But, this means \(X(\vec w’ - \vec w^{\ast}) = \vec 0\), which says that \(\vec w’ - \vec w^{\ast}\) is in \(\text{nullsp}(X)\).
Also, \(P\) projects onto \(\text{colsp}(X)\), and \(P\) has rank 2. Therefore \(\text{rank}(X)=2\) (the logic behind this is described here). Since \(X\) has 3 columns, the rank-nullity theorem gives
Among the listed choices, the vectors in this span are \(\begin{bmatrix} 1 \\ -2 \\ -1 \end{bmatrix}\) and \(\begin{bmatrix} -2 \\ 4 \\ 2 \end{bmatrix}\).
The rank-nullity logic wasn’t strictly necessary to answer the question; I’ve included it here for completeness, as it fully justifies why none of the other listed vectors are in \(\text{nullsp}(X)\).
The information stated below, above part **d), is the same as the information stated on the previous page. It’s provided for your convenience.**
Recall, \(X\) is a \(5 \times 3\) design matrix for the model
Additionally, \(\vec y \in \mathbb{R}^5\) is an observation vector, both \(\vec w^{\ast} = \begin{bmatrix} 2 \\ 3 \\ 1 \end{bmatrix}\) and \(\vec w’ = \begin{bmatrix} 3 \\ 1 \\ 0 \end{bmatrix}\) are both optimal parameter vectors that minimize mean squared error, and the matrix \(P\) that projects onto the column space of \(X\) is
8 pts Find one possible design matrix \(X\), consistent with all of the information above. Show your work, and \(\boxed{\text{circle}}\) your final answer, which should be a matrix with no variables.
Solution
Since \(P\) projects onto \(\text{colsp}(X)\), we need \(\text{colsp}(X) = \text{colsp}(P)\). Notice that the result \(P \vec y\) for any vector \(\vec y \in \mathbb{R}^5\) will have equal first four components (resulting from averaging the original first four components of \(\vec y\)) and the fifth component will be unchanged. If we think of the space of possible values of \(P \vec y\), we realize that any \(P \vec y\) is of the form
$$ \begin{bmatrix} a \\\\ a \\\\ a \\\\ a \\\\ b \end{bmatrix} = a \begin{bmatrix} 1 \\\\ 1 \\\\ 1 \\\\ 1 \\\\ 0 \end{bmatrix} + b \begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 1 \end{bmatrix} $$
Now, the problem boils down to finding a design matrix \(X\) with the above column space, that also meets the other requirements. Here are the other relevant requirements:
Since the model has an intercept term, the first column of \(X\) should be \(\vec 1 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}\).
From part c), we need \(\begin{bmatrix} 1 \\ -2 \\ -1 \end{bmatrix} \in \text{nullsp}(X)\).
If the columns of \(X\) are \(\vec x^{(0)}\), \(\vec x^{(1)}\), and \(\vec x^{(2)}\) (we’re told \(X\) has 3 columns), the first requirement states
let’s just pick \(\vec x^{(1)} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix}\). Since \(\vec x^{(0)} - \vec x^{(1)} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}\), we have accomplished the goal of finding a design matrix \(X\) with the desired column space. With our choices of \(\vec x^{(0)}\) and \(\vec x^{(1)}\) out of the way, \(\vec x^{(2)}\) is fully determined for us:
This design matrix has a column space of \(\text{span} \left( \left\lbrace \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix}\right\rbrace \right)\), which is the same as the column space of \(P\). It also has the required null space, which is why it would be wrong to just pick, say,
Suppose we’d like to fit a multiple linear regression model to predict \(\texttt{cost}_i\), the cost in dollars of parking in an Ann Arbor parking garage, using \(\texttt{hours}_i\), the number of hours parked.
For each row \(i\), the corresponding augmented feature vector is \(\text{Aug}(\vec x_i) = \begin{bmatrix} 1 & \texttt{hours}_i & \max(0,\texttt{hours}_i-2) \end{bmatrix}^T\) so the model is of the form
The model is fit by minimizing mean squared error.
a)
4 pts Suppose the dataset has four rows, and the number of hours parked in those rows is
\(3\), \(0\), \(5\), and \(1\), respectively. Write the first four rows of the design matrix \(X\). Your answer should be a matrix with four rows and no variables.
\(X =\) ______
Solution
Each row is the transpose of the augmented feature vector
2 pts Give a one-sentence English explanation of the meaning of \(w_2\).
Solution
The coefficient \(w_2\) is the change in the hourly slope after 2 hours; after the first 2 hours, each additional hour changes the predicted cost by \(w_1+w_2\) dollars instead of \(w_1\) dollars.
c)
6 pts Once again, suppose the dataset has four rows. In each of the following subparts, we provide the number of hours parked in the dataset. Find the rank of the design matrix \(X\) in each case. Fill in each blank with an integer with no variables.
(2 pts) \(3\), \(0\), \(5\), and \(1\)\(\text{rank}(X) = \_\_\_\_\_\_\)
(2 pts) \(2\), \(0\), \(2\), and \(1\)\(\text{rank}(X) = \_\_\_\_\_\_\)
(2 pts) \(3\), \(4\), \(5\), and \(6\)\(\text{rank}(X) = \_\_\_\_\_\_\)
Solution
This feature engineering setup is an example of the multiple linear regression design matrices from Chapter 7.2.