Linear Regression

1.1 – What Is Regression?

As with many other foundations of machine learning, the origins of regression reach far back into the past. Francis Galton, Darwin’s cousin and a pioneer of genetics, studied trends in certain biological traits, specifically human height. He realized that nature abhors extremes and that these traits tend to fluctuate around a mean. Even the children of very tall parents tended to be shorter and regress toward that mean.

Nature displays a certain degree of order, and the relationships between different variables can be analyzed. Broadly speaking, regression allows us to uncover that order and predict the value of a variable known as the dependent variable, such as height. This prediction is made from one or more independent variables which, in our example, might include sex and the parents’ heights.

Linear Regression is a technique used in Supervised Learning, since it works with labeled data. Think of it this way: if we want to predict an individual’s height from a variable, we need data from many individuals whose heights are already known.

1.2 – The Linear Regression Model

Let us consider height and try to create an algorithm that can predict a person’s height from a variable that we suspect is related to it: weight.

Our starting point is a set of observations that have already been collected, shown in the graph as points on the plane. This is characteristic of linear regression and, more generally, of machine learning as a whole: we need real-world data to work with.

Mathematically, our goal is to find the value of a parameter, which we will call \( \theta_1\), that multiplies the predictor variable \(x\) “weight.” This parameter weights the relationship between the two variables and is expected to be positive \( \theta_1 > 0\), meaning that it should reflect that greater weight is associated with greater height.

In addition to this parameter, we need to include a second parameter \( \theta_0\), known as the bias, which must also be estimated. It has no direct real-world interpretation because it is not associated with an explanatory variable, unlike \( \theta_1\), which represents the “importance” of the weight variable. This is why we do not call it a predictor. Nevertheless, it is needed to establish a baseline and allows us to refine our predictions further.

Together, these elements define our linear regression model:

$$predictedHeight = \theta_0 + \theta_1weight$$

This expression is an example of a linear equation, an equation that produces a straight line on the plane when plotted.

Its general form is:

$$\hat{y} = \theta_0 + \theta_1 x_1$$

which returns a prediction \(\hat{y}\) of the actual variable we want to predict, \( y \):

Linear Regression Model

Imagine that we have measured the weight and height of a class of 24 students. Our goal is to create a model that quantifies the relationship between these variables and can ultimately be used to make predictions for people other than those same students. In the graph above, you can see the model both in graphical form (a line on the plane) and as a linear equation, and observe how it changes when its two parameters are adjusted. \( \theta_1\) defines the slope of the line, while \( \theta_0\) determines its intercept on the vertical axis. Although it is not directly interpretable, \( \theta_0\) must be taken into account if we want the model—or regression line—to fit the data.

For example, suppose the parameters are \( \theta_0 = \) 100 and \( \theta_1 = \) 0.5. The height estimated by this model for a student weighing 80 kilograms would be:

\( 110 + 0.5 \cdot 80 = 140 \)

1.3 – Multiple Linear Regression

In linear regression, it is common to use more than one predictor variable. Continuing with the previous example, we suspect that age is another important predictor of height, so we can include it in the model:

$$predictedHeight = \theta_0 + \theta_1weight + \theta_2age$$

Regression models that include more than one predictor variable are known as multiple regression models. Each new predictor has a corresponding parameter \( \theta \) that quantifies its contribution. The expression can be generalized as follows for \( j \) predictors:

$$\hat{y} = \theta_0 + \theta_1x_1 + \theta_2x_2 \cdots + \theta_jx_j$$

Although this expression is mathematically precise and simple, its graphical representation is only possible when we have one or two predictors. Visual tools can help us understand the problem intuitively, but in many cases they can also make it considerably more complex, so mathematical expressions are preferable.

Multiple Linear Regression

A model with two parameters would form a plane in three-dimensional space, whereas visualizing three or more predictors would require higher-dimensional spaces that are not intuitive to understand graphically. In this three-dimensional space, the model forms a plane controlled by the parameters. \( \theta_0 \) would be the bias, \( \theta_1 \) the parameter associated with the weight predictor, and \( \theta_2 \) the parameter associated with age. For simplicity, the following examples will use a model with a single predictor plus the bias.

1.4 – Least Squares

The Linear Regression model produces a prediction that we can compare with the actual values. Naturally, we want our predictions to be as close as possible to the observed data. In mathematical terms, we need to find the values that minimize the difference between the target variable \( y \) and the model’s prediction \( \hat{y} \).

The least squares method is a technique for quantifying this error, or difference, between the two values. The difference between the prediction and the actual value is squared. One reason is that the square of any number is positive, and we want to work with positive differences regardless of whether the model overestimates or underestimates the true value. Another reason is that squaring penalizes larger differences more heavily.

\( (y -\, \hat{y})^2 \)

The difference is calculated for each available instance and then all the differences are added together. Finally, it is also common to divide the total sum by the number \( n \) of instances to obtain the Mean Squared Error (usually abbreviated as MSE):

$$\frac{1}{n} \displaystyle \sum_{i=1}^{n} (y_i -\, \hat{y}_i)^2$$

This quantity is the measure of error that we must minimize to bring our model’s predictions closer to the actual data, hence the name of the method.

Least Squares

By changing the model parameters—the slope and the intercept of the line—we can move farther from or closer to the actual values. The dotted lines represent the differences \( y -\, \hat{y} \) for each of the twenty-four instances \( i \). Adjusting the parameters to shorten these differences produces a lower error.

1.5 – The Loss Function

Least squares is one of many techniques used to quantify prediction error. These techniques fall under what is known as a loss function (also known as an error function or cost function), denoted by \( \mathcal{L}(y, \hat{y}) \). For the least-squares method discussed on the previous page, the loss function would be

$$ \mathcal{L}(y_i, \hat{y}_i) = \frac{1}{n} \displaystyle \sum_{i=1}^{n} (y_i -\, \hat{y}_i)^2$$

Another alternative would be the Sum of Squared Errors:

$$ \mathcal{L}(y_i, \hat{y}_i) = \displaystyle \sum_{i=1}^{n} (y_i -\, \hat{y}_i)^2$$

There is little difference between the two. For now, we will treat them as equivalent.

By measuring how far our model’s predictions are from the correct values, the loss function establishes a quality criterion. Remember that, in much of machine learning, learning means estimating the optimal parameter values. However, for this to truly be machine learning, the optimization must not be performed manually; we need an algorithm that carries out the search automatically.

Loss Function

The graph on the right represents the error function as a color gradient, with values that depend on the two parameters used in the linear regression model. This makes it easy to visualize what we inferred in the previous section: the lowest values of the error function lie in the darkest region, when the parameters are between 110 and 120 for \( \theta_{0} \) and between 0.8 and 0.6 for \( \theta_{1} \). These are the values we are interested in finding in order to obtain an accurate model.

1.6 – The Gradient of the Loss Function

We have a prediction model and a method for evaluating its predictions. But how do we optimize them? How do we choose the parameter values that minimize the error? This is where the gradient of the loss function comes in.

At each point of the function, we can calculate its gradient: its tendency to increase or decrease as we modify the parameters. The gradient is a generalization of what is known in mathematics as the derivative, the rate at which a function changes with respect to a variable. The derivative tells us the function’s tendency—whether its value increases or decreases. The most intuitive example is velocity, which is simply the rate of change of distance traveled with respect to time.

In our example, the loss function \( \mathcal{L} \) depends on two parameters, \( \theta_0 \) and \( \theta_1 \). Its partial derivative is denoted as 

$$ \frac{\partial \mathcal{L}}{\partial \theta_j} $$

for parameter \( j \). This derivative is calculated independently for each parameter—hence the term partial—while treating the remaining parameters as constants. Deriving this expression lies beyond the scope of this tutorial. We will simply state that, when the Mean Squared Error described in the previous section is used as the loss function, the partial derivative of \( \mathcal{L} \) is:

$$ \frac{\partial \mathcal{L}}{\partial \theta_j} = \frac{1}{n} \displaystyle \sum_{i=1}^{n} -2x_i(y_i – \hat{y}_i)$$

Derivative of the Loss Function

This graph shows the same loss function \( \mathcal{L} \) from the previous sections, this time with respect to parameter \( \theta_1 \), while holding the other parameter, \( \theta_0 \), fixed at 110. For each parameter value, we see not only the value of  \( \mathcal{L} \) (in magenta), but also the gradient of the loss function as a slope or derivative \( \frac{\partial \mathcal{L}}{\partial \theta_j} \) (in purple). In practice, we do not know the shape of the loss function, but we can calculate its value—and therefore its derivative—for a specific parameter value and use it to infer the function’s direction. We can see that the point we want to reach, where \( \mathcal{L} \) is minimized, is the point at which the derivative is close to 0 and the curve is flat. Clearly, if the derivative is positive, we must reduce the parameter value to reach that minimum. If the derivative is negative, we must increase it.

1.7 – Gradient Descent

Our goal is to modify the parameters so that the loss function is as small as possible. From the gradient calculation in the previous section, we know that the parameter value we seek is the one for which the partial derivative of the loss function with respect to that parameter is as close as possible to 0. We simply need to follow the gradient until we reach that point.

In machine learning, this process is carried out by an algorithm known as Gradient Descent, which can be described as follows: our model begins with random parameter values. We calculate the derivative of the loss function at that point, which tells us the direction in which the error changes, and determine whether the parameter value should be increased or decreased. We define the new parameter value \( \theta_j’  \) as the previous value \( \theta_j \) minus an amount determined by the gradient of the loss function.

\( \theta_j’ = \theta_j -\, \alpha \frac{\partial \mathcal{L}}{\theta_j} \)

If the derivative is negative, the new value is therefore slightly greater than the previous one, as explained in the preceding section.

We almost never reach the optimal parameter values in a single step. This update is repeated in a loop, for every parameter each time, until we eventually find the values that minimize the loss function. The value \( \alpha \) is a hyperparameter known as the learning rate and simply determines the size of the parameter update at each iteration. This hyperparameter is very important because it directly affects the number of steps required to reach the minimum error. A poorly chosen learning rate can make learning either too slow or too fast and unstable.

Gradient Descent

Click anywhere on the graph and the algorithm will repeatedly update the values of both parameters until it reaches the point of minimum error—the “bottom” of the map. You can see the path followed by the iterations: the gradient descent. When the descent ends, you can see the final error value and the number of iterations required to reach the bottom. You can also modify the learning rate \( \alpha \) for parameter \( \theta_1 \). If \( \alpha \) is too low, many more steps will be required to reach the minimum (the graph limits the number of steps to 400). If it is too high, the algorithm may never fully converge to the minimum. \( \alpha \) is therefore a hyperparameter that must be selected manually in advance. Typical values usually range from 0.01 to 0.1.

1.8 – Stochastic Gradient Descent

We have described gradient descent as an iterative process in which the following steps are repeated: a) compute the differences between the predictions and the actual values; b) calculate the partial derivatives of those errors with respect to each parameter; and c) update the parameters using those derivatives, scaled by the learning rate.

There are two alternatives to this process with regard to the first step. The difference lies in the amount of data used to calculate those differences. In the previous examples, we assumed that the entire dataset was used, an approach known as Batch Gradient Descent. By contrast, Stochastic Gradient Descent, or SGD (Stochastic Gradient Descent), is the strategy of calculating the error from a single randomly selected data point. Because this estimate does not exactly reflect the overall state of the optimization across the entire dataset, the updates are usually noisier and the trajectory may appear more erratic. Its advantage is the speed of each iteration, especially with extremely large datasets. Using SGD generally requires even more careful tuning of the learning rate, and lower values are commonly used than with Batch Gradient Descent.

In practice, the usual approach is a compromise between these two extremes: using batches, or mini-batches, of data to calculate the error, achieving a balance between stability and optimization speed.

Stochastic Gradient Descent

We can clearly see how updating the parameters by estimating the gradient from a single data point results in noisier updates.

1.9 – Normal Equations