Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Chapter 3: Linear Regression

In this chapter, we build linear regression from scratch: first with a single feature, then with multiple features. Along the way, we will see how the model’s parameters, the cost function, and gradient descent work together, and develop the intuition behind each one before turning it into code.

Architecture

architecture of Linear Regression

Linear Regression Model

y^=fw⃗,b(X⃗)=w⃗⋅X⃗+b\hat{y} = f_{\vec{w}, b} (\vec{X}) = \vec{w} \cdot \vec{X} + b
(3.1)

Cost Function

J(w⃗,b)=∑i=1mL(f(w⃗,b)(X⃗),y)+Rw+RbJ(\vec{w}, b) = \sum_{i=1}^{m} L(f(\vec{w}, b)(\vec{X}), y) + R_{w} + R_{b}
(3.2)

here, L is loss function. We can write 1m\frac{1}{m} outside of summation to generalize. I have kept it with Loss function. So in general, the above equation can also be written as:

J(w⃗,b)=1m∑i=1mL(f(w⃗,b)(X⃗),y)+Rw+RbJ(\vec{w}, b) = \frac{1}{m} \sum_{i=1}^{m} L(f(\vec{w}, b)(\vec{X}), y) + R_{w} + R_{b}
(3.3)

Gradient Descent

repeat until convergence {w1=w1−α∂∂w1J(w⃗,b)w2=w2−α∂∂w2J(w⃗,b)...wn=wn−α∂∂wnJ(w⃗,b)b=b−α∂∂bJ(w⃗,b)} simultaneously update\begin{align} & \text{repeat until convergence \{} \\ & w_1 = w_1 - \alpha \frac{\partial}{\partial w_{1}} J(\vec{w}, b) \\ & w_2 = w_2 - \alpha \frac{\partial}{\partial w_{2}} J(\vec{w}, b) \\ & . \\ & . \\ & . \\ & w_n = w_n - \alpha \frac{\partial}{\partial w_{n}} J(\vec{w}, b) \\ \\ \\ & b = b - \alpha \frac{\partial}{\partial b} J(\vec{w}, b) \\ \\ & \text{\}} \text{ simultaneously update} \\ \\ \\ \end{align}
(3.4)

where,
w⃗\vec{w} = weights,
bb = bias,
X⃗\vec{X} = features,
yy = target / output,
y^\hat{y} = prediction,
LL = Loss Function,
JJ = Cost Function
RxR_x = Regularization of XX

Linear Regression Model with Single Feature

FIG
FIG
FIG

Process

FIG

  1. A training set in supervised learning includes both the input features, such as the size of the house and also the output targets, such as the price of the house. The output targets are the right answers to the model we’ll learn from.

  2. To train the model, you feed the training set, both the input features and the output targets to your learning algorithm. Then your supervised learning algorithm will produce some function.

  3. We’ll write this function as lowercase f, where f stands for function. Historically, this function used to be called a hypothesis.

  4. The job with f is to take a new input x and output and estimate or a prediction, y^\hat{y} (“y-hat”). In machine learning, the convention is that y-hat is the estimate or the prediction for y. The function f is called the model. X is called the input or the input feature, and the output of the model is the prediction, y-hat. The model’s prediction is the estimated value of y.

  5. When the symbol is just the letter y, then that refers to the target, which is the actual true value in the training set. In contrast, y-hat is an estimate. It may or may not be the actual true value.

  6. Well, if you’re helping your client to sell the house, well, the true price of the house is unknown until they sell it. Your model f, given the size, outputs the price which is the estimator, that is the prediction of what the true price will be.

  7. Now, when we design a learning algorithm, a key question is, how are we going to represent the function f? Or in other words, what is the math formula we’re going to use to compute f?

  8. For now, let’s stick with f being a straight line.

    • Your function can be written as:

      fw,b(X)=wX+bf_{w,b}(X) = wX + b
      (3.5)

      where w, and b are numbers representing weight and bias which determine the prediction y-hat based on the input feature X.

    • fw,b(X)f_{w,b}(X) means f is a function that takes X as input, and depending on the values of w and b, f will output some value of a prediction y-hat.

    • As an alternative to writing this, fw,b(X)f_{w,b}(X), we can sometimes write it as f(X)f(X).

      f(X)=wX+bf(X) = wX + b
      (3.6)

  9. Let’s plot the training set on the graph where the input feature X is on the horizontal axis and the output target y is on the vertical axis. Remember, the algorithm learns from this data and generates the best-fit line.

FIG

f(X)=wX+bf(X) = wX + b is making predictions for the value of y using a straight-line function of X.

You may ask, why are we choosing a linear function, where linear function is just a fancy term for a straight line instead of some non-linear function like a curve or a parabola? Well, sometimes you want to fit more complex non-linear functions as well, like a curve like this.

This particular model has a name. It’s called Linear Regression. More specifically, it’s Linear Regression with one variable where the phrase one variable means that there’s a single input variable or feature X, namely the size of the house. Another name for a linear model with one input variable is univariate linear regression, where uni means one in Latin, and where variate means variable.

Cost Function

FIG
FIG
FIG

Intuition

FIG

Simplified (bias = 0)

FIG
FIG
FIG
Solution to Exercise 3.1

d. When the cost JJ is at or near a minimum.

Explaination: The goal of linear regression is to find the parameters w or w and b that results in the smallest possible value for the JJ.

Full Version

FIG
FIG
FIG
FIG
FIG

Gradient Descent

FIG

Example of Gradient Descent - Moving Down the Hill

Gradient Descent Algorithm & Its Implementation

FIG
FIG

Intuition

Derivative Intuition
FIG
Learning Rate Intuition
FIG
FIG
FIG

Gradient Descent for Linear Regression Model

FIG
Action
FIG

To be more precise, this gradient descent process is called batch gradient descent. The term batch gradient descent refers to the fact that on every step of gradient descent, we’re looking at all of the training examples, instead of just a subset of the training data.

Implementation Code

Look at Lab: Linear Regression with One Feature

Linear Regression Model with Multiple Features

Let’s extend linear regression to handle multiple input features.

Called Multiple Linear Regression! (not multivariate regression - it’s something else)

Multiple Features

Size in feet2feet^2 (X1X_1)Number of Bedrooms (X2X_2)Number of Floors (X3X_3)Age of home in years (X4X_4)Price ()in) in 1000’s (y)
21045145460
14163240232
15323230315
8522136178
...............

we’re going to use the variables X1X_1, X2X_2, X3X_3 and X4X_4, to denote the four features.

To refer to specific values, we use two indices: xj(i)x_{j}^{(i)} where ii denotes ithi^{th} training example and jj denotes feature.

For example:

X⃗(2)=[14163240]\vec{X}^{(2)} = \begin{bmatrix} 1416 & 3 & 2 & 40\end{bmatrix}
(3.18)

Vectorization

vectorization will both make your code shorter and also make it run much more efficiently.

w⃗=[w1w2w3]\vec{w} = \begin{bmatrix} w_1 & w_2 & w_3 \end{bmatrix}
(3.23)
b is a numberb \text{ is a number}
(3.24)
X⃗=[X1X2X3]\vec{X} = \begin{bmatrix} X_1 & X_2 & X_3 \end{bmatrix}
(3.25)
fw⃗,b(X⃗)=w1X1+w2X2+w3X3+bf_{\vec{w}, b} (\vec{X}) = w_1 X_1 + w_2 X_2 + w_3 X_3 + b
(3.26)

In python and numpy, we can write code like this:

import numpy as np

w = np.array([1.0, 2.5, -3.5])
b = 4
X = np.array([10, 20, 30])

In python, indexing starts at 0. So X0,X1,X2X_0, X_1, X_2

Without Vectorization

fw⃗,b(X⃗)=w1X1+w2X2+w3X3+bf_{\vec{w}, b} (\vec{X}) = w_1 X_1 + w_2 X_2 + w_3 X_3 + b
(3.27)
f = w[0] * X[0] + w[1] * X[1] + w[2] * X[2] + b

The math uses x1,x2,x3x_1, x_2, x_3, but Python indexes from 0, so the code uses X[0], X[1], X[2].

what if number of inputs (n) would be 100 or 1000? We can loop it !

In mathematics, we could use summation to add all the products of wjw_j and XjX_j

fw⃗,b(X⃗)=∑j=1nwjXj+bf_{\vec{w}, b} (\vec{X}) = \sum_{j=1}^{n} w_j X_j + b
(3.28)

In code

f = 0
for j in range(0, n, 1):
	f = f + w[j] * X[j]
	
f = f + b

With Vectorization

This is the math expression of the function f,

fw⃗,b(X⃗)=w⃗⋅X⃗+bf_{\vec{w}, b} (\vec{X}) = \vec{w} \cdot \vec{X} + b
(3.29)

in Code:

import numpy as np

f = np.dot(w, X) + b

This NumPy dot function is a vectorized implementation of the dot product operation between two vectors and especially when n is large, this will run much faster than the two previous code examples.

What are the benefits?

Example

FIG
FIG

Using a vectorized implementation, you should get a much more efficient implementation of linear regression. Maybe the speed difference won’t be huge if you have 16 features, but if you have thousands of features and perhaps very large training sets, this type of vectorized implementation will make a huge difference in the running time of your learning algorithm. It could be the difference between codes finishing in one or two minutes, versus taking many hours to do the same thing.

To recap, vectorization makes your code shorter, so hopefully easier to write and easier for you or others to read, and it also makes it run much faster.

Gradient Descent for Multiple Linear Regression

Previous NotationVector Notation
Parametersw1,...,wnw_1, ..., w_n and bw⃗=[w1...wn]\vec{w} = \begin{bmatrix} w_1 & ... & w_n \end{bmatrix} and b is still a number
Modelfw⃗,b(X⃗)=w1X1+...+wnXn+bf_{\vec{w},b} (\vec{X}) = w_1 X_1 + ... + w_n X_n + bfw⃗,b(X⃗)=w⃗⋅X⃗+bf_{\vec{w}, b} (\vec{X}) = \vec{w} \cdot \vec{X} + b
Cost FunctionJ(w1,...,wn,b)J(w_1, ..., w_n, b)J(w⃗,b)J(\vec{w}, b)
Gradient DescentSee (1) belowSee (2) below

(1) Gradient Descent in previous notation:

repeat{wj=wj−α∂∂wjJ(w1,...,wn,b)b=b−α∂∂bJ(w1,...,wn,b)}\begin{align} \text{repeat\{} \\ w_j = w_j - \alpha \frac{\partial}{\partial w_j} J(w_1, ..., w_n, b) \\ b = b - \alpha \frac{\partial}{\partial b} J(w_1, ..., w_n, b) \\ \text{\}} \end{align}
(3.30)

(2) Gradient Descent in Vector Notation:

repeat{wj=wj−α∂∂wjJ(w⃗,b)b=b−α∂∂bJ(w⃗,b)}\begin{align} \text{repeat\{} \\ w_j = w_j - \alpha \frac{\partial}{\partial w_j} J(\vec{w}, b) \\ b = b - \alpha \frac{\partial}{\partial b} J(\vec{w}, b) \\ \text{\}} \end{align}
(3.31)

Let’s look at how gradient descent works for multiple features

We know that how it works for single feature:

repeat{w=w−α1m∑i=1m(fw,b(X(i))−y(i))X(i)b=b−α1m∑i=1m(fw,b(X(i))−y(i))} simultaneously update w, b\begin{align} \text{repeat\{} \\ w = w - \alpha \frac{1}{m} \sum_{i=1}^{m} (f_{w,b} (X^{(i)}) - y^{(i)}) X^{(i)} \\ b = b - \alpha \frac{1}{m} \sum_{i=1}^{m} (f_{w,b} (X^{(i)}) - y^{(i)}) \\ \\ \text{\}} \text{ simultaneously update w, b} \\ \end{align}
(3.32)

Now, here is the new notation when we have nn features.

repeat{w1=w1−α1m∑i=1m(fw⃗,b(X⃗(i))−y(i))x1(i)w2=w2−α1m∑i=1m(fw⃗,b(X⃗(i))−y(i))x2(i)...wn=wn−α1m∑i=1m(fw⃗,b(X⃗(i))−y(i))xn(i)b=b−α1m∑i=1m(fw⃗,b(X⃗(i))−y(i))}simultaneously update\begin{align} & \text{repeat\{} \\ & w_1 = w_1 - \alpha \frac{1}{m} \sum_{i=1}^{m} (f_{\vec{w},b} (\vec{X}^{(i)}) - y^{(i)}) x_1^{(i)} \\ & w_2 = w_2 - \alpha \frac{1}{m} \sum_{i=1}^{m} (f_{\vec{w},b} (\vec{X}^{(i)}) - y^{(i)}) x_2^{(i)} \\ & . \\ & . \\ & . \\ & w_n = w_n - \alpha \frac{1}{m} \sum_{i=1}^{m} (f_{\vec{w},b} (\vec{X}^{(i)}) - y^{(i)}) x_n^{(i)} \\ \\ \\ \\ & b = b - \alpha \frac{1}{m} \sum_{i=1}^{m} (f_{\vec{w},b} (\vec{X}^{(i)}) - y^{(i)}) \\ \\ & \text{\}} \text{simultaneously update} \\ \\ \\ \end{align}
(3.33)

If you implement this, you get gradient descent for multiple regression.

Alternative of Gradient Descent - Normal Equation

There is an alternative way to find ww and bb for linear regression, called the normal equation.

the normal equation method, it turns out to be possible to use an advanced linear algebra library to just solve for w and b all in one go without iterations. Though it works only for Linear Regression

Normal Equation:

Disadvantages?

Feature Scaling

With just a few tricks such as picking and scaling features appropriately and also choosing the learning rate alpha appropriately, you’d really make this work much better.

feature scaling enable gradient descent to run much faster.

Let’s start by taking a look at the relationship between the size of a feature that is how big are the numbers for that feature and the size of its associated parameter.

FIG

So how does this relate to gradient descent?

FIG

So to recap, when you have different features that take on very different ranges of values, it can cause gradient descent to run slowly but re scaling the different features so they all take on comparable range of values. can speed up gradient descent significantly.

How to do Feature Scaling?

feature scaling is to take features that take on very different ranges of values and scale them to have comparable ranges of values to each other.

Method 1: Divide by Max Value
n1≤Xn≤n2n_1 \le X_n \le n_2
(3.34)
Xn,scaled=Xnn2X_{n, scaled} = \frac{X_n}{n_2}
(3.35)
FIG
Method 2: Mean Normalization

What this looks like is, you start with the original features and then you re-scale them so that both of them are centered around zero. Whereas before they only had values greater than zero, now they have both negative and positive values that may be usually between negative one and plus one.

To Apply Mean Normalization:

  1. First find the average, also called the mean of XnX_n , let’s call it μn\mu_n

  2. Note: n1≤Xn≤n2n_1 \le X_n \le n_2

  3. Apply Feature Scaling:

    Xn,scaled=Xn−μnn2−n1X_{n, scaled} = \frac{X_n - \mu_n}{n_2 - n_1}
    (3.36)
FIG
Method 3: Z-Score Normalization

To implement a Z-score normalization,

  1. you first calculate the mean μ\mu, as well as the standard deviation σ\sigma of each feature.

  2. Apply Feature Scaling:

    Xn,scaled=Xn−μnσnX_{n, scaled} = \frac{X_n - \mu_n}{\sigma_n}
    (3.37)
FIG

Thumb Rule

As a rule of thumb, when performing feature scaling, you might want to aim for getting the features to range from maybe anywhere around negative one to somewhere around plus one for each feature X.

For Example, if the features ranges from:

  1. −3≤Xj≤+3-3 \le X_j \le +3

  2. −0.3≤Xj≤0.3-0.3 \le X_j \le 0.3 All of these are completely acceptable.

If you have a feature:

  1. 0≤Xj≤30 \le X_j \le 3

  2. −2≤Xj≤0.5-2 \le X_j \le 0.5
    You can re-scale it if you want, but if you don’t re-scale it, it should work okay too. (No harm)

But if you have feature:

  1. −100≤Xj≤100-100 \le X_j \le 100 --> Too Large

  2. −0.001≤Xj≤0.001-0.001 \le X_j \le 0.001 --> Too Small You’re probably better off re-scaling this feature XjX_j so that it ranges from something closer to -1 to +1.

Finally, what if your feature x5x_5, such as measurements of a hospital patients by the temperature ranges from 98.6-105 degrees Fahrenheit? 98.6≤Xj≤10598.6 \le X_j \le 105

There’s almost never any harm to carrying out feature re-scaling. When in doubt, I encourage you to just carry it out.

That’s it for feature scaling! With this little technique, you’ll often be able to get gradient descent to run much faster.

Is Gradient Descent Converging?

With or without feature scaling, when you run gradient descent, how can you know, how can you check if gradient descent is really working? If it is finding you the global minimum or something close to it. let’s take a look at how to recognize if gradient descent is converging!

When running gradient descent, how can you tell if it is converging? That is, whether it’s helping you to find parameters close to the global minimum of the cost function.

Objective of Gradient Descent:

min⁡w⃗,b  J(w⃗,b)\min_{\vec{w}, b} \; J(\vec{w}, b)
(3.38)
FIG

If gradient descent is working properly, then the cost J should decrease after every single iteration.

Another useful thing that this plot can tell you is that if you look at this curve, by the time you reach maybe 300 iterations also, the cost J is leveling off and is no longer decreasing much. After 400 iterations, it looks like the curve has flattened out. This means that gradient descent has more or less converged because the curve is no longer decreasing.

Looking at this learning curve, you can try to spot whether or not gradient descent is converging. By the way, the number of iterations that gradient descent takes to converge can vary a lot between different applications. In one application, it may converge after just 30 iterations. For a different application, it could take 1,000 or 100,000 iterations. It turns out to be very difficult to tell in advance how many iterations gradient descent needs to converge, which is why you can create a graph like this, a learning curve.

Ways to find out model is done training?

  1. you can create a graph of learning curve.

  2. Another way to decide when your model is done training is with an automatic convergence test.

Automatic Convergence Test

Let ϵ\epsilon “epsilon” be 10-3 (or 0.001)

If the cost J(w⃗,b)J(\vec{w}, b) decreases by ≤ϵ\le \epsilon in one iteration, declare convergence.

In practice, choosing the right threshold ϵ\epsilon is difficult.

In practice, looking at the learning curve is usually more reliable than relying on an automatic convergence test.

Choosing the Learning Rate

Your learning algorithm will run much better with an appropriate choice of learning rate. If it’s too small, it will run very slowly and if it is too large, it may not even converge.

Concretely, if you plot the cost for a number of iterations and notice that the costs sometimes goes up and sometimes goes down, you should take that as a clear sign that gradient descent is not working properly.

FIG

A Common Bug: Wrong Sign

In code you may be doing:

w1=w1+αd1w_1 = w_1 + \alpha d_1
(3.39)

but you should use minus sign

w1=w1−αd1w_1 = w_1 - \alpha d_1
(3.40)

This is because having the derivative term moves your cost J further from the global minimum instead of closer.

Feature Engineering

The choice of features can have a huge impact on your learning algorithm’s performance. In fact, for many practical applications, choosing or engineering the right features is a critical step to making the algorithm work well.

FIG

Let’s say:

Model : fw⃗,b(X⃗)=w1X1+w2X2+bf_{\vec{w}, b} (\vec{X}) = w_1 X_1 + w_2 X_2 +b This model might work okay.

But here’s another option for how you might choose a different way to use these features in the model that could be even more effective. You might notice that the area of the land can be calculated as the frontage or width times the depth.

X3=X1×X2X_3 = X_1 \times X_2
(3.41)

You may have an intuition that the area of the land is more predictive of the price, than the frontage and depth as separate features.

New Model:

fw⃗,b(X⃗)=w1X1+w2X2+w3X3+bf_{\vec{w}, b}(\vec{X}) = w_1 X_1 + w_2 X_2 + w_3 X_3 + b
(3.42)

What we just did, creating a new feature is an example of what’s called feature engineering, in which you might use your knowledge or intuition about the problem to design new features usually by transforming or combining the original features of the problem in order to make it easier for the learning algorithm to make accurate predictions.

Full Implementation

Look at Lab: Linear Regression with Multiple Feature

Summary

Linear Regression is probably the single most widely used learning algorithm in the world today.

Solution to Exercise 3.2

False - Doubling the learning rate may result in a learning rate that is too large, and cause gradient descent to fail to find the optimal values for the parameters w, and b.

References
  1. Ng, Dr. A. (2022). Machine Learning Specialization. Coursera. https://www.coursera.org/specializations/machine-learning-introduction
AI from First Principles
Chapter 2: Introduction to Machine Learning
AI from First Principles
Lab: Linear Regression with one feature