Ordinary Least Squares (OLS) › Formula

The core of OLS lies in its elegant mathematical formulation. We'll break down the mathematics step by step, starting with the intuitive approach and building up to the matrix notation.

OLS seeks to minimize the sum of squared errors (SSE) between observed values and predicted values:

$$\text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

where:

• $y_i$ is the observed target value for the $i$-th data point
• $\hat{y}_i$ is the predicted target value for the $i$-th data point
• $n$ is the number of data points

The predicted value comes from the linear model:

$$\hat{y}_i = \beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip}$$

where:

• $\beta_0$ is the intercept
• $\beta_1, \beta_2, \ldots, \beta_p$ are the coefficients for the $p$ features
• $x_{i1}, x_{i2}, \ldots, x_{ip}$ are the feature values for the $i$-th data point

Let's walk through, step by step, how we derive the equations that allow us to solve for the optimal coefficients in OLS regression. This process is rooted in calculus: to find the minimum of a function (in this case, the sum of squared errors), we set its derivatives with respect to each parameter to zero. These resulting equations are called the normal equations.

Step 1: Write the Sum of Squared Errors (SSE)Link Copied

Recall that the OLS objective is to minimize the sum of squared errors between the observed values $y_i$ and the predicted values $\hat{y}_i$:

$$\text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

where

$$\hat{y}_i = \beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip}$$

Step 2: Take Partial Derivatives with Respect to Each CoefficientLink Copied

To find the values of $\beta_0, \beta_1, \ldots, \beta_p$ that minimize SSE, we take the partial derivative of SSE with respect to each coefficient and set it to zero. This is because the minimum (or maximum) of a differentiable function occurs where its derivative is zero.these are known as the critical points, and for the SSE (which is a convex function in this case), setting the derivatives to zero guarantees we find the global minimum.

Step 2.1: For the Intercept $\beta_0$:Link Copied

Let's derive the process of taking the derivative of the sum of squared errors (SSE) with respect to the intercept $\beta_0$ in detail.

Recall the SSE:

$$\text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

where

$$\hat{y}_i = \beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip}$$

So, explicitly, the SSE can be written as:

$$\text{SSE} = \sum_{i=1}^n \left[y_i - (\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip})\right]^2$$

We want to find the value of $\beta_0$ that minimizes SSE. To do this, we take the partial derivative of SSE with respect to $\beta_0$:

$$\frac{\partial \text{SSE}}{\partial \beta_0} = \frac{\partial}{\partial \beta_0} \sum_{i=1}^n \left[y_i - (\beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip})\right]^2$$

Since the sum is over $i$, and $\beta_0$ appears in every term, we can bring the derivative inside the sum:

$$= \sum_{i=1}^n \frac{\partial}{\partial \beta_0} \left[y_i - (\beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip})\right]^2$$

Let us denote the prediction error for the $i$-th data point as:

$$e_i = y_i - (\beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip}) = y_i - \hat{y}_i$$

So each term inside the sum is $e_i^2$. The derivative of $e_i^2$ with respect to $\beta_0$ is:

By the chain rule: $\frac{d}{d\beta_0} e_i^2 = 2 e_i \cdot \frac{d e_i}{d\beta_0}$

But $e_i = y_i - \beta_0 - \beta_1 x_{i1} - \cdots - \beta_p x_{ip}$, so

$$\frac{d e_i}{d\beta_0} = -1$$

Therefore,

$$\frac{d}{d\beta_0} e_i^2 = 2 e_i \cdot (-1) = -2 e_i$$

Putting this back into the sum, we have:

$$\frac{\partial \text{SSE}}{\partial \beta_0} = \sum_{i=1}^n -2 (y_i - \hat{y}_i)$$

Or, equivalently,

$$\frac{\partial \text{SSE}}{\partial \beta_0} = -2 \sum_{i=1}^n (y_i - \hat{y}_i)$$

To find the minimum, we set this derivative equal to zero:

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

Dividing both sides by $-2$ (which does not affect the equality), we get:

$$\sum_{i=1}^n (y_i - \hat{y}_i) = 0$$

This equation tells us that, at the minimum, the sum of the residuals (the differences between the observed values and the predicted values) is zero.

Now, let's substitute the explicit form of $\hat{y}_i$ back in:

$$\sum_{i=1}^n \left[y_i - (\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip})\right] = 0$$

Or, written out:

$$\sum_{i=1}^n (y_i - \beta_0 - \beta_1 x_{i1} - \beta_2 x_{i2} - \cdots - \beta_p x_{ip}) = 0$$

This is the normal equation for the intercept $\beta_0$ in OLS regression. It states that, at the optimal values of the coefficients, the sum of the residuals is zero.

Step 2.2: For Each Slope Coefficient $\beta_j$ (where $j = 1, 2, \ldots, p$):Link Copied

Now, let's derive the process of taking the partial derivative of the sum of squared errors (SSE) with respect to a generic slope coefficient $\beta_j$ (where $j = 1, 2, \ldots, p$):

Recall the sum of squared errors:

$$\text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

where the predicted value for observation $i$ is:

$$\hat{y}_i = \beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip}$$

We want to compute the partial derivative of SSE with respect to $\beta_j$:

$$\frac{\partial \text{SSE}}{\partial \beta_j} = \frac{\partial}{\partial \beta_j} \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

Let's break this down step by step:

1. Apply the linearity of differentiation (the derivative of a sum is equal to the sum of the derivatives for each term):
   The derivative of a sum is the sum of the derivatives, so we can write:

   $$\frac{\partial \text{SSE}}{\partial \beta_j} = \sum_{i=1}^n \frac{\partial}{\partial \beta_j} (y_i - \hat{y}_i)^2$$

2. Apply the chain rule to each term:
   For each $i$, $(y_i - \hat{y}_i)^2$ is a function of $\beta_j$ through $\hat{y}_i$. The chain rule gives:

   $$\frac{\partial}{\partial \beta_j} (y_i - \hat{y}_i)^2 = 2 (y_i - \hat{y}_i) \cdot \frac{\partial}{\partial \beta_j}(y_i - \hat{y}_i)$$

   Since $y_i$ does not depend on $\beta_j$, its derivative is zero. The derivative of $-\hat{y}_i$ with respect to $\beta_j$ is $-x_{ij}$, because:

   $$\frac{\partial}{\partial \beta_j} \hat{y}_i = \frac{\partial}{\partial \beta_j} \left( \beta_0 + \beta_1 x_{i1} + \cdots + \beta_j x_{ij} + \cdots + \beta_p x_{ip} \right ) = x_{ij}$$

   Therefore,

   $$\frac{\partial}{\partial \beta_j}(y_i - \hat{y}_i) = -x_{ij}$$

   So, the derivative for each term is:

   $$2 (y_i - \hat{y}_i) \cdot (-x_{ij}) = -2 (y_i - \hat{y}_i) x_{ij}$$

3. Sum over all observations:
   Putting this back into the sum, we have:

   $$\frac{\partial \text{SSE}}{\partial \beta_j} = \sum_{i=1}^n -2 (y_i - \hat{y}_i) x_{ij}$$

   Or, equivalently,

   $$\frac{\partial \text{SSE}}{\partial \beta_j} = -2 \sum_{i=1}^n (y_i - \hat{y}_i) x_{ij}$$

4. Set the derivative to zero to find the minimum:
   To find the value of $\beta_j$ that minimizes the SSE, set the derivative equal to zero:

   $$-2 \sum_{i=1}^n (y_i - \hat{y}_i) x_{ij} = 0$$

   Dividing both sides by $-2$ (which does not affect the equality), we get:

   $$\sum_{i=1}^n (y_i - \hat{y}_i) x_{ij} = 0$$

   This equation tells us that, at the minimum, the sum of the residuals (errors) weighted by the value of feature $j$ for each observation is zero. In other words, the residuals are orthogonal (uncorrelated) to each feature in the model.

5. Substitute the explicit form of $\hat{y}_i$:
   Recall that $\hat{y}_i = \beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip}$. Plugging this in, we get:

   $$\sum_{i=1}^n \left[ y_i - (\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \cdots + \beta_p x_{ip}) \right ] x_{ij} = 0$$

   Or, written out more explicitly:

   $$\sum_{i=1}^n (y_i - \beta_0 - \beta_1 x_{i1} - \beta_2 x_{i2} - \cdots - \beta_p x_{ip}) x_{ij} = 0$$

This is the normal equation for the slope coefficient $\beta_j$ in OLS regression. It states that, at the optimal values of the coefficients, the sum of the residuals weighted by the corresponding feature values is zero for each feature. This property is fundamental to the OLS solution and ensures that the model's errors are, on average, uncorrelated with each predictor.

Step 3: The System of Equations: The Normal EquationsLink Copied

We now have $p+1$ equations (one for each coefficient, including the intercept) in $p+1$ unknowns:

• One equation from setting the derivative with respect to $\beta_0$ to zero
• $p$ equations from setting the derivatives with respect to each $\beta_j$ to zero

These equations are called the normal equations. Solving this system gives us the OLS estimates for all coefficients.

In summary:
For the intercept:

$$\sum_{i=1}^n (y_i - \beta_0 - \beta_1 x_{i1} - \cdots - \beta_p x_{ip}) = 0$$

For each coefficient $\beta_j$:

$$\sum_{i=1}^n (y_i - \beta_0 - \beta_1 x_{i1} - \cdots - \beta_p x_{ip})x_{ij} = 0$$

This system of equations forms the foundation for the matrix solution that follows, and helps explain how OLS "balances" the errors across data points and features to find the best-fitting line or hyperplane.

The system of normal equations we derived above can be written much more compactly and powerfully using matrix notation. Matrix notation makes the equations easier to manipulate and reveals the underlying structure of the OLS solution.especially when dealing with multiple features.

Let's define the key components:

• $X$ is the design matrix of shape $(n, p+1)$, where $n$ is the number of observations and $p$ is the number of features. The first column of $X$ is all ones to account for the intercept term, and the remaining columns contain the values of each feature for every observation.
• $y$ is the target vector of length $n$, containing the observed values of the dependent variable.
• $\beta$ is the coefficient vector of length $p+1$, which includes the intercept ($\beta_0$) and one coefficient for each feature.

In matrix notation, the model is written as:

$$y = X\beta + \epsilon$$

where $\epsilon$ is the vector of errors (residuals).

The Normal Equations in Matrix FormLink Copied

Recall that, for each coefficient, we set the derivative of the sum of squared errors to zero. In matrix terms, this yields the normal equations:

$$X^T X \beta = X^T y$$

In this expression:

• $X^T X$ is a $(p+1) \times (p+1)$ matrix known as the Gram matrix. It summarizes the relationships (covariances) between all pairs of features, including the intercept.
• $X^T y$ is a $(p+1)$-dimensional vector that captures the relationship between each feature (and the intercept) and the target variable.

Solving for the OLS CoefficientsLink Copied

To find the vector of coefficients $\beta$ that minimizes the sum of squared errors, we solve the normal equations for $\beta$:

$$\hat{\beta} = (X^T X)^{-1} X^T y$$

Let's break down each component of this solution:

• $X^T X$ (Gram matrix): This matrix encodes how each feature relates to every other feature (including itself). If two features are highly correlated, the corresponding off-diagonal entry will be large.
• $(X^T X)^{-1}$ (Inverse of Gram matrix): This step "untangles" the relationships between features, allowing us to isolate the effect of each one. The inverse exists only if the features are not perfectly collinear (i.e., no feature is an exact linear combination of others).
• $X^T y$ (Feature-target cross-product): This vector measures how each feature (and the intercept) is associated with the target variable across all observations.
• Matrix multiplication $(X^T X)^{-1} X^T y$: This operation combines all the above information to yield the set of coefficients that minimize the sum of squared errors. Each coefficient in $\hat{\beta}$ represents the estimated effect of its corresponding feature on the target, holding all other features constant.

Matrix Notation BenefitsLink Copied

This matrix formulation provides the foundation for efficient computation and for extending OLS to more complex models. It allows us to:

• Solve for all coefficients at once, regardless of the number of features
• Generalize easily to multiple regression, polynomial regression, and regularized models
• Use powerful linear algebra libraries for fast computation, even with large datasets

The OLS closed-form solution in matrix notation is:

$$\hat{\beta} = (X^T X)^{-1} X^T y$$

This formula gives us the unique set of coefficients that minimize the sum of squared errors, provided that $X^T X$ is invertible (i.e., the features are linearly independent).

The OLS solution is unique if $X^TX$ is invertible (i.e., the features are not perfectly correlated), and it globally minimizes the sum of squared errors. The solution is a linear function of the target values, and, under the Gauss-Markov assumptions, provides unbiased estimates of the true coefficients.

The condition that $X^TX$ must be invertible determines whether the solution is unique. This matrix is invertible when:

• The number of observations is greater than or equal to the number of features
• No feature is a perfect linear combination of other features (no multicollinearity)
• No feature is constant (all features have some variation)