Announcements¶

• Remember our in-class test will be on Friday, March 31
• A sample test has been posted online in the Piazza resources tab

Recap from last lecture¶

To describe the orbit of Ceres, Gauss had to construct the equation for its ellipse:

He had many measurements of $(x_1,x_2)$ pairs and had to find the $a_1,\dots ,a_6.$ This is actually a linear system:

According to Newton, this is a consistent linear system. But there are two unappealing options to solve it.

• Take only six independent measurements and try to solve the system with a $6\times 6$ matrix. We will likely get a unique solution. But the solution is likely overfitting to the measurement errors from the six samples.

• Take a larger number of measurements $n$ and construct a $n\times 6$ matrix with all of them. But due to measurement errors, it is unlikely that a single ellipse will go through all of them. We now have an inconsistent system with no solutions.

The key idea is: the fact that our measurements include small, unbiased errors does not make them worthless! We simply need a principled approach to doing the best job we can given the errors in our measurements.

If a system of equations $Ax=b$ has no solutions, that is because $b$ is not in the column space of $A$.

So let's find the closest vector $\hat{b}=A\hat{x}$ that is in the column space and find the solution $x$ to that equation.

(Note that there is a unique closest vector $\hat{b}$, although there might be multiple solutions $\hat{x}$ such that $\hat{b}=A\hat{x}$.)

If A is $m\times n$ and $b$ is in $R^m$, then the general least-squares problem is to find an $\hat{x}$ that makes $\parallel A\hat{x}-b\parallel$ as small as possible. Equivalently, our goal is to minimize the sum of squared error:

where $\hat{b}=A\hat{x}$ contains the estimated values and $b$ contains the measured values.

The best estimated value $\hat{b}$ must be at the orthogonal projection of $b$ onto the subspace $\mathrm{Col}A$. That is the closest vector to the measured value $b$.

Any other vector $v$ will be further away because its distance to $b$ will be the hypotenuse of a right triangle.

24.4 Projection Solves Least Squares¶

The Normal Equations¶

So: how are we going to find this projection $\hat{b}$?

Here is the key idea:

We know that the projection $\hat{b}$ has the property that $\hat{b}-b$ is orthogonal to $\mathrm{Col}A.$

Suppose $\hat{b}$ is ${\text{proj}}_{\mathrm{Col}A}b,$ and that $\hat{x}$ satisfies $A\hat{x}=\hat{b}$.

So $A\hat{x}-b$ is orthogonal to each column of $A$.

If $a_j$ is any column of $A$, then

Now, each $a_j^{\top }$ is a row of $A^{\top }$.

We can collect all of the equations for all the $a_j$ as:

So

So

Looking at this, we see that $A^{\top }b$ is a vector, and $A^{\top }A$ is a matrix, so this is a standard linear system.

This linear system is called the normal equations for $Ax=b.$

It's solution is usually denoted $\hat{x}$.

Theorem. The set of least-squares solutions of $Ax=b$ is equal to the (nonempty) set of solutions of the normal equations $A^{\top }Ax=A^{\top }b.$

Proof.

(1) The set of solutions is nonempty. The matrix on the left has the same column space as $A^{\top }$ and the vector on the right is a vector in the column space of $A^{\top }.$

And, by the arguments above, any least-squares solution of $Ax=b$ must satisfy the normal equations $A^{\top }Ax=A^{\top }b.$

(2) Now let's show that any solution of $A^{\top }Ax=A^{\top }b$ is a least squares solution of $Ax=b$.

If $\hat{x}$ satisfies $A^{\top }Ax=A^{\top }b,$ then $A^{\top }(A\hat{x}-b)=0,$

which shows that $A\hat{x}-b$ is orthogonal to the rows of $A^{\top }$, and so is orthogonal to the columns of $A$.

So the vector $A\hat{x}-b$ is orthogonal to $\mathrm{Col}A$.

So the equation

is a decomposition of $b$ into the sum of a vector in $\mathrm{Col}A$ and a vector orthogonal to $\mathrm{Col}A$.

Since the orthogonal decomposition is unique, $A\hat{x}$ must be the orthogonal projection of $b$ onto the column space of $A$.

So $A\hat{x}=\hat{b}$ and $\hat{x}$ is a least-squares solution.

Example. Find the least squares solution of the inconsistent system $Ax=b$ for

Solution.

We will use the normal equations $A^{\top }A\hat{x}=A^{\top }b.$

So the normal equations are:

We can solve this using row operations, or by inverting $A^{\top }A$.

And we can then solve $A^{\top }A\hat{x}=A^{\top }b$ as

So we conclude that $\hat{x}=\left[\begin{array}{c}1\\ 2\end{array}\right]$ is the vector that minimizes $\parallel Ax-b\parallel .$

More formally,

That is, $\hat{x}$ is the least-squares solution of $Ax=b$.

When the Normal Equations have Multiple Solutions¶

We have seen that the normal equations always have a solution.

Is there always a unique solution?

No, there can be multiple solutions that all minimize $\parallel Ax-b\parallel .$

Let's remind ourselves of what is going on when a linear system has multiple solutions.

We know that a linear system has multiple solutions when there are columns that are not pivot columns.

Equivalently, when $A\hat{x}=\hat{b}$ has multiple solutions, the columns of $A$ are linearly dependent.

Here is a picture of what is going on. In this case, $A$ is $3\times 3$.

But note, that $\mathrm{Col}A$ is only two-dimensional because the three columns are linearly dependent.

Example.

Find a least-squares solution for $Ax=b$ for

Solution. Compute

To solve $A^{T}A\hat{x}=A^{T}b,$ we'll use row reduction. The augmented matrix $\left[A^{T}A\right|A^{T}b]$ is:

In the reduced echelon form matrix, there are 4 column vectors, but only the first three of them are linearly independent and the last one can be written as a linear combination of them.

Hence, the columns of $A^{\top }A$ are linearly dependent. This happens because the columns of $A$ are linearly dependent.

You can see this as follows: if $A$ has a non-trivial null space, then $A^{\top }A$ also has a nontrival null space.

So there is a free variable.

The general solution is then $x_1=3-x_4$, $x_2=-5+x_4$, $x_3=-2+x_4$, and $x_4$ is free.

So the general least-squares solution of $A\hat{x}=b$ has the form

Keep in mind that the orthogonal projection $\hat{b}$ is always unique.

The reason that there are multiple solutions to this least squares problem is that there are multiple ways to construct $\hat{b}$.

The reason that there are multiple ways to construct $\hat{b}$ is that the columns of $A$ are linearly dependent, so any vector in the column space of $A$ can be constructed in multiple ways.

Here is a theorem that allows use to identify when there are multiple least-squares solutions.

Theorem. Let $A$ be an $m\times n$ matrix. The following statements are equivalent:

1. The equation $Ax=b$ has a unique least-squares solution for each $b$ in $R^m.$
2. The columns of $A$ are linearly independent.
3. The matrix $A^{\top }A$ is invertible.

When these statements are true, the least-squares solution $\hat{x}$ is given by:

Finding $\hat{b}$ directly.

When $A^{\top }A$ is invertible, and $\hat{b}$ is unique, we can put together the two equations

and

to get:

Let's stop and look at this another way. Up until now we have seen how to project a point onto a line, or on to a subspace with an orthogonal basis.

Now here is a formula for projection onto a subspace (namely $\mathrm{Col}A$) given an arbitrary basis. This is a general formula that can be very useful.

Lecture 25: Linear Regressions¶

[This lecture is based on Prof. Crovella's CS 132 lecture notes.]

25.1 Least Squares Example¶

Here is a graph showing the number of BU computer science majors over many years, from 2004 to 2017. We'd like to have some estimate of where the numbers might be going.

Modeling the number of students in the CS major is challenging because students enter and leave the major at various points during their undergraduate degree.

Here is the raw data of the number of declared CS majors, broken down into 1st, 2nd, 3rd, and 4th year students.

We will use a simple linear model that we will train on historical data.

Our state variable is

where $x_{i,t}$ is the number of students who are declared CS majors and in their $i$th year at BU, in the fall of year $t$. Our model is a linear dynamical system (or linear recurrence):

Given historical data which are measurements of our state variable from past years, we now know how to estimate $A$ using least squares!

Now, using $A$, we can predict growth into the future via $x_{t+1}=A{x}_t.$

Now, the matrix $A$ captures the complex way that one year's student population relates to the next year's population.

It can be hard to understand what is going on just by looking at the values of $A$.

But, when we look at the plot above, it appears that there is a relatively simple kind of exponential growth going on.

25.2 Modeling via Regression¶

One of the most fundamental kinds of machine learning is the construction of a model that can be used to summarize a set of data.

A model is a concise description of a dataset or a real-world phenomenon.

For example, an equation can be a model if we use the equation to describe something in the real world.

The most common form of modeling is regression, which means constructing an equation that describes the relationships among variables.

For example, we may look at these points and observe that they approximately lie on a line.

So we could decide to model this data using a line.

We may look at these points and decide to model them using a quadratic function.

And we may look at these points and decide to model them using a logarithmic function.

Clearly, none of these datasets agrees perfectly with the proposed model. So the question arises:

How do we find the best linear function (or quadratic function, or logarithmic function) given the data?

The Framework of Linear Models¶

The regression problem has been studied extensively in the field of statistics and machine learning.

Certain terminology is used:

• Some values are referred to as "independent," and
• Some values are referred to as "dependent."

The basic regression task is:

• given a set of independent variables
• and the associated dependent variables,
• estimate the parameters of a model (such as a line, parabola, etc) that describes how the dependent variables are related to the independent variables.

The independent variables are collected into a matrix $X,$ which is called the design matrix.

The dependent variables are collected into an observation vector $y.$

The parameters of the model (for any kind of model) are collected into a parameter vector $\beta .$

25.3 Fitting a Line to Data¶

The first kind of model we'll study is a linear equation:

This is the most commonly used type of model, particularly in fields like economics, psychology, biology, etc.

The reason it is so commonly used is that experimental data often produce points $(x_1,y_1),\dots ,(x_n,y_n)$ that seem to lie close to a line.

The question we must confront is: given a set of data, how should we "fit" the equation of the line to the data?

Our intuition is this: we want to determine the parameters ${\beta }_0,{\beta }_1$ that define a line that is as "close" to the points as possible.

Let's develop some terminology for evaluating a model.

Suppose we have a line $y={\beta }_0+{\beta }_{1}x$. For each data point $(x_j,y_j),$ there is a point $(x_j,{\beta }_0+{\beta }_1{x}_j)$ that is the point on the line with the same $x$-coordinate.

We call $y_j$ the observed value of $y$

and we call ${\beta }_0+{\beta }_1{x}_j$ the predicted $y$-value.

The difference between an observed $y$-value and a predicted $y$-value is called a residual.

There are several ways to measure how "close" the line is to the data.

The usual choice is to sum the squares of the residuals.

(Note that the residuals themselves may be positive or negative -- by squaring them, we ensure that our error measures don't cancel out.)

The least-squares line is the line $y={\beta }_0+{\beta }_{1}x$ that minimizes the sum of squares of the residuals.

The coefficients ${\beta }_0,{\beta }_1$ of the line are called regression coefficients.

Regression is a Least-Squares Problem¶

Let's imagine for a moment that the data fit a line perfectly.

Then, if each of the data points happened to fall exactly on the line, the parameters ${\beta }_0$ and ${\beta }_1$ would satisfy the equations

We can write this system as

where

If the data points don't actually lie exactly on a line,

... then there are no parameters ${\beta }_0,{\beta }_1$ for which the predicted $y$-values in $X\beta$ equal the observed $y$-values in $y$,

... and $X\beta =y$ has no solution.

Now, since the data doesn't fall exactly on a line, we have decided to seek the $\beta$ that minimizes the sum of squared residuals, ie,

This is key: the sum of squares of the residuals is exactly the square of the distance between the vectors $X\beta$ and $y.$

This is a least-squares problem, $Ax=b,$ with different notation.

Computing the least-squares solution of $X\beta =y$ is equivalent to finding the $\beta$ that determines the least-squares line.

Example. Find the equation $y={\beta }_0+{\beta }_{1}x$ of the least-squares line that best fits the data points

Solution. Use the $x$-coordinates of the data to build the design matrix $X$, and the $y$-coordinates to build the observation vector $y$:

Now, to obtain the least-squares line, find the least-squares solution to $X\beta =y.$

We do this by solving the normal equation that we learned last lecture (just with new notation):

So, we compute:

So the normal equations are: