Deriving OLS with Multivariate Calculus

Recommended resources

The freely available resources this lesson will direct you to.

Deriving the least squares estimators of the slope and intercept (simple linear regression)www.youtube.com
Stanford CS229: Machine Learning - Linear Regression and Gradient Descent | Lecture 2 (Autumn 2018)www.youtube.com
Proofs involving ordinary least squaresen.wikipedia.org
5.1 Ordinary Least Squares | A Guide on Data Analysisbookdown.org

Welcome back! In our last lesson, you successfully derived the least squares cost function, $J (β)$ , which provides a quantitative measure of our linear regression model's error. We now have a clear objective: find the parameter vector $β$ that minimizes this function.

Today, we will achieve this objective. Your learning outcome for this lesson is to derive the Ordinary Least Squares (OLS) solution using multivariate calculus by setting the gradient to zero. This is a direct application of the optimization theory you've studied. By finding the point where the cost function's slope is zero in all directions, we will identify the parameters that give the best possible fit to the data according to the least squares criterion.

A Quick Recap: The Optimization Problem

From our previous lesson, we established the cost function for a linear model with parameters $β = [β_{0}, β_{1}, \dots, β_{k}]^{T}$ :

J (β) = \frac{1}{2} i = 1 \sum n (y_{i} - x_{i}^{T} β)^{2}

where $n$ is the number of data points.

Our goal is to find the specific parameter vector, which we'll call $β^$ , that minimizes this function:

β^= ar g β min J (β)

As you know from your study of optimization and calculus, a necessary condition for a minimum of a differentiable, convex function is that its gradient is the zero vector.

Surface and Contour Plots of a Cost Function — As we saw previously, the cost function $J(\boldsymbol{\beta})$ for linear regression is convex, shaped like a bowl. The minimum is the single point at the bottom of the bowl where the gradient is zero.

We will find this minimum by taking the partial derivative of $J (β)$ with respect to each parameter $β_{j}$ , setting each derivative to zero, and solving the resulting system of equations.

1. The Starting Point: Simple Linear Regression

Before tackling the general multivariate case, let's derive the solution for a simple linear regression model with just one feature. Your practical experience has likely involved fitting such models, and deriving the solution from first principles will solidify your theoretical understanding.

The model is: $y^_{i} = β_{0} + β_{1} x_{i}$ .
The cost function is:

J (β_{0}, β_{1}) = \frac{1}{2} i = 1 \sum n (y_{i} - (β_{0} + β_{1} x_{i}))^{2}

To find the optimal $β^_{0}$ and $β^_{1}$ , we must solve the following system of equations:

$\frac{\partial J}{\partial β _{0}} = 0$
$\frac{\partial J}{\partial β _{1}} = 0$

The following video provides a clear, step-by-step derivation of these partial derivatives.

Deriving the least squares estimators of the slope and intercept (simple linear regression)

This video from jbstatistics will walk you through computing the partial derivatives of the simple linear regression cost function. Focus on the application of the power rule and chain rule.

Please watch from 03:16 to 05:09. The first part derives the partial derivative with respect to the intercept (eta_0), and the second part derives it for the slope (eta_1). Note that the video's cost function omits the rac{1}{2} factor, which is fine—it just means their derivatives have a factor of 2 that we won't have.

Let's summarize the results, applying the rules to our version of $J (β_{0}, β_{1})$ .

Partial derivative with respect to $β_{0}$ :
Using the chain rule: $\frac{\partial}{\partial β _{0}} \frac{1}{2} (y_{i} - β_{0} - β_{1} x_{i})^{2} = \frac{1}{2} \cdot 2 \cdot (y_{i} - β_{0} - β_{1} x_{i}) \cdot (- 1)$ .
Summing over all $n$ observations:

\frac{\partial J}{\partial β _{0}} = i = 1 \sum n - (y_{i} - β_{0} - β_{1} x_{i})

Partial derivative with respect to $β_{1}$ :
Similarly, using the chain rule, the derivative of the inner term with respect to $β_{1}$ is $- x_{i}$ .

\frac{\partial J}{\partial β _{1}} = i = 1 \sum n - (y_{i} - β_{0} - β_{1} x_{i}) x_{i}

Setting these two equations to zero gives us a system of two linear equations with two unknowns, $β_{0}$ and $β_{1}$ . Solving this system (as shown in the rest of the jbstatistics video) yields the well-known formulas for the slope and intercept in simple regression.

2. The General Case: Multiple Linear Regression

Now, let's generalize this to the multiple linear regression case, where we have $k$ features and $k + 1$ parameters ( $β_{0}, β_{1}, \dots, β_{k}$ ).

Our model is $y^_{i} = x_{i}^{T} β = \sum_{j = 0}^{k} β_{j} x_{ij}$ , where we define $x_{i 0} = 1$ for all $i$ .
The cost function remains $J (β) = \frac{1}{2} \sum_{i = 1}^{n} (y_{i} - \sum_{j = 0}^{k} β_{j} x_{ij})^{2}$ .

Our goal is to compute the partial derivative $\frac{\partial J}{\partial β _{j}}$ for an arbitrary parameter $β_{j}$ .

The following segment from Andrew Ng's lecture provides an excellent derivation.

Stanford CS229: Machine Learning - Linear Regression and Gradient Descent | Lecture 2 (Autumn 2018)

Watch this clip from the Stanford CS229 lecture on linear regression. Andrew Ng derives the partial derivative of the cost function with respect to a single, arbitrary parameter heta_j (his notation for eta_j). This is the core of today's lesson.

Watch the segment from 22:49 to 32:40. Pay close attention to how the chain rule is applied and how only the term involving eta_j (or heta_j) survives the differentiation inside the summation. He first derives it for a single training example and then re-introduces the summation over all examples, which leads to the final gradient update rule.

Let's formalize the result from the video. To find the partial derivative of $J (β)$ with respect to a specific parameter $β_{j}$ , we again apply the chain rule:

Derivative of the outer square function:
$\frac{\partial J}{\partial β _{j}} = \frac{1}{2} \sum_{i = 1}^{n} 2 (y_{i} - x_{i}^{T} β) \cdot \frac{\partial}{\partial β _{j}} (y_{i} - x_{i}^{T} β)$
Derivative of the inner term:
The inner term is $y_{i} - (β_{0} x_{i 0} + β_{1} x_{i 1} + \dots + β_{j} x_{ij} + \dots + β_{k} x_{ik})$ . When we differentiate this with respect to $β_{j}$ , only the $β_{j} x_{ij}$ term is non-zero. The derivative is simply $- x_{ij}$ .
Combining them:
$\frac{\partial J}{\partial β _{j}} = i = 1 \sum n (y_{i} - x_{i}^{T} β) \cdot (- x_{ij}) = - i = 1 \sum n (y_{i} - x_{i}^{T} β) x_{ij}$

This single, powerful equation gives us the partial derivative for any parameter $β_{j}$ .

Test your understanding!

Look at the final expression for $\frac{\partial J}{\partial β _{j}}$ . The term $(y_{i} - x_{i}^{T} β)$ is the residual for the $i$ -th data point. The term $x_{ij}$ is the value of the $j$ -th feature for that same data point.

Can you provide an intuitive explanation for why the gradient involves the product of the residual and the feature value? What does it mean if this sum is large and positive?

Show answer

The term $\sum_{i = 1}^{n} (y_{i} - x_{i}^{T} β) x_{ij}$ represents a weighted sum of the residuals, where the weights are the feature values $x_{ij}$ . This term is essentially the covariance between the feature $j$ and the model's errors.

If this sum is large and positive, it means that when the feature $x_{j}$ is large and positive, the residual $(y_{i} - y^_{i})$ also tends to be large and positive (i.e., the model is under-predicting). To correct this, we need to increase the model's prediction. Since $x_{ij}$ is positive, increasing the corresponding parameter $β_{j}$ will increase the prediction $y^_{i}$ . The gradient descent update rule $β_{j} := β_{j} - α \frac{\partial J}{\partial β _{j}}$ would become $β_{j} := β_{j} + α (positive value)$ , which correctly increases $β_{j}$ .

Conversely, if the sum is large and negative, the model tends to over-predict when $x_{j}$ is large, and the update rule will correctly decrease $β_{j}$ . When the sum is zero, there is no systematic correlation between feature $j$ and the error, indicating we are at an optimum with respect to $β_{j}$ .

3. The Result: A System of Normal Equations

To find the minimum of $J (β)$ , we must set the partial derivative with respect to every parameter $β_{j}$ to zero. This gives us a system of $k + 1$ equations:

⎩ ⎨ ⎧ \frac{\partial J}{\partial β _{0}} = - \sum_{i = 1}^{n} (y_{i} - x_{i}^{T} β) x_{i 0} = 0 \frac{\partial J}{\partial β _{1}} = - \sum_{i = 1}^{n} (y_{i} - x_{i}^{T} β) x_{i 1} = 0 ⋮ \frac{\partial J}{\partial β _{k}} = - \sum_{i = 1}^{n} (y_{i} - x_{i}^{T} β) x_{ik} = 0

This system of simultaneous linear equations is known as the Normal Equations.

For a more formal, textual derivation of this system, you can refer to the following resource.

Proofs involving ordinary least squares

The Wikipedia page 'Proofs involving ordinary least squares' provides a concise, formal derivation of the Normal Equations by setting the partial derivatives to zero, just as we have done.

Read the section named "Derivation of the normal equations". This text formalizes the steps we've just discussed, showing how setting the partial derivatives of the sum of squared residuals to zero leads directly to the Normal Equations.

This system of equations represents the solution. Any vector $β^$ that satisfies these $k + 1$ equations is a vector that minimizes the sum of squared errors.

Conclusion

In this lesson, you have successfully used multivariate calculus to find the conditions that the optimal OLS parameters must satisfy. By leveraging your knowledge of optimization, you've transformed the abstract goal of "fitting the best line" into a concrete mathematical problem and solved it.

Key Takeaways:

The minimum of the convex cost function $J (β)$ occurs where its gradient with respect to $β$ is the zero vector.
The partial derivative of the cost function with respect to a single parameter $β_{j}$ is $\frac{\partial J}{\partial β _{j}} = - \sum_{i = 1}^{n} (y_{i} - x_{i}^{T} β) x_{ij}$ .
Setting all $k + 1$ partial derivatives to zero yields a system of $k + 1$ linear equations in the $k + 1$ unknown parameters $β_{j}$ .
This resulting system is known as the Normal Equations.

Preview of the Next Lesson:
We have derived the system of Normal Equations. While one could solve this system using techniques like substitution or elimination, doing so by hand becomes extremely tedious for more than a couple of features. A far more elegant and powerful approach exists using the language of linear algebra. In the next lesson, we will express the Normal Equations in matrix form and derive the famous closed-form OLS solution: $β^= (X^{T} X)^{- 1} X^{T} y$ .