Course contentsShow

Basics/Lesson 2 of 11

Linear Regression

The Problem

Linear regression is one of the simplest and most powerful techniques in machine learning.

A classic linear regression problem is predicting the price of a house from its area. The bigger the house, the higher we expect the price to be.

The price is a continuous value, and we need past data to make any assumptions about it. So suppose we have the area and price of a few houses.

If we plot this data, with house area on the x-axis and house price on the y-axis, the data points mostly fall along a straight line. Given this, can we estimate the price of a new house?

This is a supervised regression problem:

It is supervised because the data contains both the inputs and the output labels.
It is regression because the output is a continuous value.

We call this the one-dimensional case because there is only one input, the house area.

Simple One-Dimensional Linear Regression

We start with a dataset of $n$ labeled data points:

(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)

For all $i = 1, \dots, n$ , both $x_i$ and $y_i$ are real values:

$x_i$ is the feature, which here is the house area.
$y_i$ is the label, which here is the house price.

We want to build a model that takes any input $x$ and predicts $y$ .

Since the data mostly falls on a straight line, we can use the equation of a line as our model. Instead of writing it as $ax + b$ , we write:

f(x) = w_0 + w_1 x

Many straight lines are possible, but most of them don't match the data points. Our job is to find the values of $w_0$ and $w_1$ that give us the line that fits best.

Measuring the Error

For the $n$ samples, the model's predicted outputs are:

\begin{bmatrix} f(x_1) \\ f(x_2) \\ \vdots \\ f(x_n) \end{bmatrix} = \begin{bmatrix} w_0 + w_1 x_1 \\ w_0 + w_1 x_2 \\ \vdots \\ w_0 + w_1 x_n \end{bmatrix}

The actual outputs from the training data are $y_1, y_2, \dots, y_n$ .

We want the predicted outputs to be as close as possible to the actual outputs. For the $i$ -th sample, the error is the gap between the two:

e_i = y_i - f(x_i)

On a plot, these errors are the vertical distances between the data points and the line.

We can't just add up the errors and minimize the sum. Some errors are positive and some are negative, so they would cancel each other out. Instead, we square each error.

This gives us the objective function:

\min_{w_0, w_1} \; \frac{1}{2} \sum_{i=1}^{n} e_i^2

The $\frac{1}{2}$ doesn't change the answer, because the values of $w_0$ and $w_1$ that minimize a function also minimize half of it. We add it because it cancels a factor of 2 when we take derivatives.

Substituting $e_i$ , the function we want to minimize is:

f(w_0, w_1) = \frac{1}{2} \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i)^2

Minimizing a Function

Let's first recall how to minimize a function of one variable. Take this function:

g(x) = x^2 + 4x + 5

Take the first derivative: $g'(x) = 2x + 4$ .
Set it to zero: $2x + 4 = 0$ , so $x = -2$ . This is a critical point, where the function can have a local minimum or maximum.
Take the second derivative: $g''(x) = 2$ .
Since $2 > 0$ , the critical point is a local minimum.

The minimum value is $g(-2) = 1$ .

Our objective function is different because it has two variables, $w_0$ and $w_1$ . In this multivariate case, we replace the first and second derivatives with the gradient and the Hessian, which are built from partial derivatives.

The Gradient

First, we take the partial derivative of the objective with respect to each variable. The 2 from the power cancels with the $\frac{1}{2}$ we added earlier:

\frac{\partial f}{\partial w_0} = \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i)

\frac{\partial f}{\partial w_1} = \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i)\, x_i

The gradient is a vector containing all the partial derivatives of a function. It plays the role of the first derivative:

\nabla f = \begin{bmatrix} \dfrac{\partial f}{\partial w_0} \\[8pt] \dfrac{\partial f}{\partial w_1} \end{bmatrix}

The Hessian

The Hessian plays the role of the second derivative. It is a matrix of second-order partial derivatives:

H = \begin{bmatrix} \dfrac{\partial^2 f}{\partial w_0^2} & \dfrac{\partial^2 f}{\partial w_0 \partial w_1} \\[8pt] \dfrac{\partial^2 f}{\partial w_0 \partial w_1} & \dfrac{\partial^2 f}{\partial w_1^2} \end{bmatrix}

Taking the partial derivatives of the gradient terms gives:

H = \begin{bmatrix} n & \sum_{i=1}^{n} x_i \\[4pt] \sum_{i=1}^{n} x_i & \sum_{i=1}^{n} x_i^2 \end{bmatrix}

If the Hessian is positive definite, the critical point is a local minimum. A matrix $H$ is positive definite if, for every non-zero vector $v$ :

v^T H v > 0

This is the multivariate version of checking that the second derivative is greater than zero.

Multi-Dimensional Linear Regression

So far we have used a single input. In practice, a house price depends on more than its area.

Suppose the inputs are the house area, the number of bedrooms, the number of toilets, and the number of balconies. The output is still the house price.

The dataset still has $n$ data points $(x_1, y_1), \dots, (x_n, y_n)$ . The difference is that each $x_i$ is now a $d$ -dimensional vector, where $d$ is the number of input features. In this example, $d = 4$ . Each $y_i$ is still a real value.

The model now combines all $d$ features:

f(x_i) = w_0 + w_1 x_i^{(1)} + w_2 x_i^{(2)} + \dots + w_d x_i^{(d)}

The superscripts are the dimensions, so $x_i^{(k)}$ is the $k$ -th feature of the $i$ -th sample. We can write this more compactly as:

f(x_i) = w_0 + \sum_{k=1}^{d} w_k x_i^{(k)}

Vector Form

We can simplify this further using vectors.

Let $w$ be the vector $[w_0, w_1, \dots, w_d]^T$ , which has $d + 1$ values. Each $x_i$ has only $d$ values, so we add a 1 at the start to give it $d + 1$ values too:

x_i = \begin{bmatrix} 1 \\ x_i^{(1)} \\ \vdots \\ x_i^{(d)} \end{bmatrix}

The prediction then becomes a single vector multiplication:

f(x_i) = w^T x_i = x_i^T w

Matrix Form

The error for each sample is the same as before, $e_i = y_i - f(x_i)$ . To handle all $n$ samples at once, we build a matrix $X$ where each row is one data sample:

X = \begin{bmatrix} x_1^T \\ x_2^T \\ \vdots \\ x_n^T \end{bmatrix}

The dimensions work out as follows:

Term	Dimensions
$X$	$n \times (d + 1)$
$w$	$(d + 1) \times 1$
$Xw$	$n \times 1$
$y$	$n \times 1$

The total squared error on the training data is then a function of $w$ :

E(w) = \|Xw - y\|^2

The Closed-Form Solution

To minimize the error, we first expand it:

E(w) = (Xw - y)^T (Xw - y)

Taking the derivative with respect to $w$ gives:

\nabla E(w) = 2X^T (Xw - y)

Setting the derivative to zero gives:

X^T X w = X^T y

Solving for $w$ gives the closed-form solution:

w = (X^T X)^{-1} X^T y

This only works if $X^T X$ is invertible. If it isn't, we use the pseudo-inverse $X^+$ instead:

w = X^+ y

Why We Need Another Approach

The formula gives us the exact answer, but it becomes highly computationally expensive when the dataset is large. For large datasets, we can't find $w$ directly this way, so we need a different approach.

Summary

Concept	Simple linear regression	Multiple linear regression
Inputs	One feature	$d$ features
Model	$f(x) = w_0 + w_1 x$	$f(x_i) = w^T x_i$
Objective	$\frac{1}{2} \sum_{i=1}^{n} (w_0 + w_1 x_i - y_i)^2$	$\lVert Xw - y \rVert^2$

The key ideas are:

Linear regression fits a line to the data to predict a continuous value.
We find the best line by minimizing the sum of squared errors.
Setting the gradient to zero gives us a critical point, and a positive definite Hessian confirms it is a minimum.
The closed-form solution is $w = (X^T X)^{-1} X^T y$ , but it is too expensive for large datasets.

Free preview

That was a free preview lesson.

Enroll to access the full course