Ordinary Least Squares

Using linear algebra to generalize the simple linear regression model.

Data 100/Data 200, Fall 2020 @ UC Berkeley

Anthony D. Joseph and Fernando Pérez

Content credit: Suraj Rampure, Ani Adhikari, Deborah Nolan, Joseph Gonzalez

LECTURE 13

Recap: Simple Linear Regression

Simple Linear Regression

In the last lecture, we re-introduced the simple linear regression model from Data 8.

​

• Our loss function was squared loss, and so our objective function was mean squared error (MSE).
• To solve for the optimal parameters (also known as coefficients or weights), we minimized MSE by hand using calculus.

​

​

• These are parameter estimates.
• We also looked at r, the correlation coefficient, and its relation to �the optimal coefficients.

​

​

Multiple Regression

We also extended this model to account for multiple features.

​

​

• We learned about multiple R², an extension of the correlation coefficient r to multiple features.
• Our loss function yet again was squared loss.
• We didn’t minimize MSE by hand – we abstracted away the process of determining the theta values.
• Lastly, we introduced RMSE as a method of comparing model performance.

Today, we will learn how to find the optimal parameters (“thetas”) for �multiple regression, for any number of features.

Each xj is a separate feature.

Agenda

• Use vector dot products to define the multiple regression model.
• Formulate the problem statement using vector norms.
• Use a geometric derivation to solve for the optimal t (which is now a vector).
• Explore properties of residuals.
• Understand when a unique solution exists.

​

Lots of linear algebra!

• There is a resources post on Piazza if you need a refresher.
• We will try and take things slowly.

Linear algebra formulation

Dot products

The dot product of two vectors and is defined as follows:

​

​

​

• An alternate way of writing a dot product: .
• This is the form we will use primarily moving forward.
• The dot product between two vectors is a scalar, not another vector.
• The dot product is only defined for two vectors of the same length.
• The dot product is a special case of the inner product.

​

​

Multiple regression as a dot product

We previously stated that the multiple regression model was of the form

​

​

​

This can be restated as a dot product between two vectors.

Even though they don’t have arrows on top of them, x and θ are still vectors!

scalar

Design matrix

Our mean squared error involves all observations at once, so it may be valuable to express our model in terms of all observations, instead of just one observation. One step in that process is stacking all of our observations together into a design matrix. With n observations:

Columns correspond to features.

e.g. feature 1, for all data points

Rows correspond to observations.

e.g. all features for data point 3

Here, n = 708, and p = 3.

• Each of the 4 columns corresponds to a different feature.
• Each of the 708 rows corresponds to a different data point.

Example design matrix

Multiple regression as a matrix multiplication

This allows us to express our linear model on our entire dataset (not just one observation) as

​

​

​

​

​

​

​

​

Note: This means that represents an n-length vector containing all of our true y values.

​

​

​

​

​

​

​

Vector with dimensions n x 1.

Vector with dimensions (p + 1) x 1.

Matrix with dimensions n x (p + 1).

Multiple regression as a matrix multiplication

Moving forward:

• or just simply will represent row i of our design matrix. Rows are observations / data points.
• will represent column j of our design matrix. Columns are features.

​

​

​

​

​

​

Multiple regression as a matrix multiplication

For instance, to compute the predicted output for the second observation:

​

Or, more compactly:

​

​

​

​

X2 is a vector, not a matrix. That is why it is transposed.

Example

Consider the following design matrix and value of θ.

The predicted response (output) for the second observation:

​

Example

Consider the following design matrix and value of θ.

The predicted response vector:

​

Summary of notation

When looking at a single observation, our model is

​

​

• x is a vector of size p + 1.
• is a scalar.
• is a vector of size p + 1.

​

​

​

​

​

In many settings, we assume that we have only p (and not p + 1) columns. One of those p columns may be “1” for each observation.

When looking at multiple observations, our model is

​

​

• is a matrix of size n x (p + 1).
• is a vector of size n (i.e. ).
• is a vector of size p + 1.

Problem statement

Vector norms

• The norm of a vector is some measure of that vector’s size.
• More formal definitions exist, but we don’t really need them in Data 100.
• The two norms we need to know are the L1 and L2 norms (surprise surprise!).
• L2 will be used today.
• L1 will appear a few lectures from now.

​

Consider the vector:

​

L2 vector norm:

​

​

​

L1 vector norm:

L2 vector norm

• The L2 vector norm can be thought of as the “length” of a vector.
• It is a generalization of the Pythagorean theorem into n dimensions.

​

​

• The “distance” between two vectors is the L2 norm of their difference.
• For instance, if a and b are two vectors of the same length, then their distance is

​

• Note, the square of the L2 norm of a vector is the sum of the squares of the vector’s elements:

Residuals

Residuals are defined as being the difference between an actual and predicted value, in the regression context.

• We use the letter e to denote residuals. The residual i is

​

• The MSE of a model is equal to the mean of the squares of its residuals:

The red dotted lines represent residuals.

Residual vector

We can stack all n residuals into a vector, called the residual vector, e:

​

​

​

​

​

​

The residual vector is the “difference” between the two vectors containing our true y values and predicted y values.

Mean squared error, again

We are choosing our loss to be squared loss. This means, the average loss across our dataset is mean squared error.

​

​

​

We can write this in terms of the norm of the residual vector!

This is the residual vector!

Optimization procedure

As we did in the last lecture, we note that the value of theta that minimizes is the same value that minimizes

​

​

Therefore, our goal is to find the value of that minimizes the squared L2 norm of the residual vector. In other words, we want the “distance” between and to be minimized.

​

There are two ways we can determine the optimal here.

• Using calculus, like we’ve done earlier.
• Requires a lot of matrix calculus. Out of scope, but here’s a link if you’re interested.
• Using a geometric argument. This is what we’ll do here.

Geometric derivation

A linear combination of columns

The linear model represents as a linear combination of the columns of .

Span

Our prediction is a linear combination of the columns of X.

• The set of all possible linear combinations of the columns of X is called the span of the columns of X (denoted ).
• Also called the column space.
• Intuitively, this is all of the vectors you can “reach” using the columns of X.
• Since each column of X has length n, is a subspace of .
• Our goal is to find the vector in that is closest to .

Recall, this is the residual vector,

.

​

Our goal is to minimize the L2 norm of the residual vector, i.e. we want our predictions to be “as close” to our true y values as possible.

How do we minimize this distance – the norm of the residual vector (squared)?

How do we minimize this distance – the norm of the residual vector (squared)?

The vector in span(X) that is closest to Y is the orthogonal projection of Y onto span(X).

We will not prove this: see Khan Academy.

How do we minimize this distance – the norm of the residual vector (squared)?

The vector in span(X) that is closest to Y is the orthogonal projection of Y onto span(X).

Thus, we should choose the θ that makes the residual vector orthogonal to span(X).

Orthogonality

We say two vectors are orthogonal if and only if their dot product is 0.

• This is a generalization of the notion of two vectors in 2D being perpendicular.

​

​

Suppose a vector is orthogonal to the span of the columns of a matrix.

• This is true if and only if it is orthogonal to each column individually. (proof)
• Let . Suppose v is orthogonal to the span of the columns of M. Then:

Let . Suppose v is orthogonal to the span of the columns of M.

v is orthogonal to each column of M separately.

(Note, each column of M has length n, and v also has length n).

This product encapsulates all d of the equations on the left into a single equation. The quantity on the right is the zero vector (d-length vector full of 0s).

Residuals are orthogonal to the span of X

We want the θ such that the residual vector is orthogonal to .

​

By the definition of orthogonality:

​

Rearranging:

​

The normal equation:

​

Assuming is full rank:

Still the zero vector!

This result is so important, it deserves its own slide.

It is the least squares estimate for θ.

Summary

1. Choose a model. We chose the multiple linear regression model, formulated using a matrix.

​

​

2. Choose a loss function. We chose squared loss, and hence our average loss was

​

​

​

3. Minimize average loss to determine optimal model parameters. Done!

Residuals

Residual plots

Residual plots can tell us about the quality of our model.

• In the simple linear regression case, with only one independent variable, we typically plot residuals vs. x.
• More generally, a residual plot is of residuals vs. fitted values.

​

Properties:

• A good residual plot has no pattern. This means that our model represents the relationship in the data well.
• If you see a curve, it is a sign that transformations or additional variables could help.
• A good residual plot also has a similar vertical spread throughout the entire plot.
• If this is not the case, the accuracy of the predictions is not reliable.

No pattern, even spread.

Clear quadratic relationship in the residuals.

No clear relationship, but uneven spread.

Residuals are orthogonal to the span of X

When using the optimal parameter vector, our residuals are orthogonal to .

​

• Since our predicted response is in , it is orthogonal to the residuals.
• This is true, no matter what the features of model are.

​

• When our model contains an intercept term, things become slightly more interesting!

We denote this column with . �

Since , it is also true that

​

​

Why?

Properties when our model has an intercept term

When our linear model has an intercept term (i.e. when our design matrix has a column of all 1s), the following properties hold true:

• The sum of the residuals is 0.
• The mean of the residuals is also 0!
• This is why the positive and negative residuals cancel out in any residual plot where the (linear) model contains an intercept term, even if the model is terrible.
• The average true y value is equal to the average predicted y value.
• This follows from the property above.

​

These properties are true when there is an intercept term, and not necessarily when there isn’t. You will prove them in a homework.

Existence of a unique solution

Does a solution always exist?

• For all models so far, our goal has been to determine the value of θ that minimizes some average loss.
• The minimum value of both mean squared error and mean absolute error is 0.

​

​

• This means, there is always at least one model parameter that minimizes average loss.

Does a unique solution always exist?

• Constant model with squared loss:
• Any set of values has a unique mean.
• Thus, in this case, a unique solution always exists.
• Simple linear model with squared loss:
• Any set of non-constant* values has a unique mean, SD, and correlation coefficient.
• Constant model with absolute loss:
• This is unique when there is an odd number of y values.
• But, from Lecture 11, when there is an even number of y values, there are infinitely many solutions!
• Recall, in such a case, any value of θ between the “middle two” values minimized MAE.

Understanding the solution matrices

Typically, n is much larger than p.

Understanding the solution matrices

Typically, n is much larger than p.

Understanding the solution matrices

The Normal Equation:

​

​

​

​

​

​

Our optimal parameter vector can be thought of as the solution to a set of p + 1 equations, with p + 1 unknowns.

Does a unique solution always exist?

Let’s consider our optimal θ for the multiple linear regression model:

​

​

• As mentioned previously, at least one solution always exists.
• Intuitively, we can always draw a line of best fit for a given set of data. There may be multiple lines that are “equally good”.
• When does a unique solution for exist?
• When is invertible. If it is not invertible, a unique solution does not exist.
• In such a case, there will be infinitely many values of theta that minimize average squared loss.
• If there are infinitely many “optimal” choices of coefficients, it’s unclear which to use.
• We want a unique solution.

Invertibility of

When is XTX invertible?

• XTX is invertible if and only if it is full rank.
• The shape of XT is (p + 1) x (p + 1). Invertibility is only defined for square matrices.
• The rank of a matrix is the number of linearly independent columns (or rows) it contains.
• This is one of several conditions of the “invertible matrix theorem.”
• XTX and X have the same rank.
• The proof is beyond the scope of this class.
• The maximum possible rank of XT is p + 1.
• Thus, XTX is invertible if and only if X has rank p + 1 (full column rank).
• That is, a unique solution for the least squares estimate exists if and only if all columns of X are linearly independent.

Invertibility of

When does our design matrix not have full column rank?

• When some features in our design matrix are linear combinations of other features.
• If “Width”, “Height”, and “Perimeter” are all columns, will not have full rank, since Perimeter = 2 * Width + 2 * Height (linear combination).
• When we discuss one-hot encoding, this is something to be aware of.
• When our design matrix has more columns than rows (i.e. it is “fat”).
• In the normal setting, n > p + 1 (we typically have more observations than features).

n

p + 1

Since the row rank and column rank of a matrix are equal, rank(X) ≤ min(n, p+1).

If n < p + 1, then the column rank cannot possibly be p + 1, meaning it cannot be full column rank.

Summary, what’s next

Summary

• We defined the multiple linear regression model in terms of matrices.

​

• We used a geometric argument to derive the optimal parameter vector , that minimizes average squared loss. This value is called the least squares estimate.

​

• We discussed residuals and their properties.
• We explored when a unique solution for exists, and when one does not.

Moving forward

Think of this lecture as the third in a trilogy of lectures that establish the foundations of regression. From here, we will cover:

• Feature engineering.
• The process of extracting and creating more sophisticated features from our data.
• The Bias-Variance tradeoff.
• Discussing this idea of a “true model,” and where the errors in our predictions come from.
• Regularization and Cross-Validation.
• Making our models more “general”, by updating our objective function.
• Gradient descent.
• Minimizing average loss using numerical methods.
• Logistic regression.
• What if we want to predict categories (1 and 0), instead of numbers?