Normal Equation for Linear Regression

1. From Iteration to a Direct Solution

Gradient descent is like walking down a hill blindfolded, taking small steps in the steepest direction until you reach the bottom. The Normal Equation, in contrast, is like using a mathematical formula to instantly calculate the exact coordinates of the lowest point on that hill.

The central idea comes from calculus. To find the minimum of a function, you can take its derivative with respect to the parameters, set the derivative to zero, and solve for the parameters. The Normal Equation is the result of performing this operation on the Mean Squared Error (MSE) cost function for linear regression.

As Professor Ng outlines, performing this derivation with matrix calculus gives us a beautiful, closed-form solution.

2. The Normal Equation Formula

The final result of that derivation is the Normal Equation:

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

This single line of linear algebra gives us the optimal parameter vector $\theta$ that minimizes the cost function. Let's break it down:

• $\theta$: The vector of model parameters we want to find (e.g., $[{\theta }_0,{\theta }_1,...,{\theta }_n]$).
• $y$: The vector of target values from our training data, with shape $(m,1)$, where $m$ is the number of samples.
• $X$: This is the design matrix containing the input features. It has a very specific and important structure. For $m$ training samples and $n$ features, $X$ is an $m\times (n+1)$ matrix. $$X=\left(\begin{array}{ccccc}1& x_1^{(1)}& x_2^{(1)}& \dots & x_n^{(1)}\\ 1& x_1^{(2)}& x_2^{(2)}& \dots & x_n^{(2)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_1^{(m)}& x_2^{(m)}& \dots & x_n^{(m)}\end{array}\right)$$ The crucial part is the first column of ones. This is how we account for the bias term (or intercept), ${\theta }_0$, because ${\theta }_0\times 1={\theta }_0$. Forgetting this column is one of the most common implementation mistakes!
• $X^T$: The transpose of the design matrix.
• $(X^{T}X{)}^{-1}$: The inverse of the matrix product $X^{T}X$.

3. Implementing the Normal Equation from Scratch

Now, let's translate this formula into Python code. Since you're proficient with NumPy, you'll see how elegantly its linear algebra capabilities map to this equation.

We'll follow a clear, practical demonstration.

Let's consolidate those steps into our own code.

Step 1: Generate Data

First, we create some synthetic data to work with.

import numpy as np
import matplotlib.pyplot as plt

# Generate 100 data points
X = 2 * np.random.rand(100, 1)
# Linear equation: y = 4 + 3x + noise
y = 4 + 3 * X + np.random.randn(100, 1)

plt.scatter(X, y)
plt.xlabel("Feature (x)")
plt.ylabel("Target (y)")
plt.title("Synthetic Linear Data")
plt.grid(True)
plt.show()

Step 2: Construct the Design Matrix $X_b$

This is where we add the column of ones to X for the bias term ${\theta }_0$. We use np.c_, a handy NumPy tool for concatenating arrays column-wise.

# Add x0 = 1 to each instance
X_b = np.c_[np.ones((100, 1)), X]

# Let's inspect the first 5 rows
print("First 5 rows of X_b:")
print(X_b[:5])

You should see that the first column is all ones, and the second column contains our original feature values from X.

Step 3: Calculate $\theta$ using the Normal Equation

Now for the main event. We translate $\theta =(X^{T}X{)}^{-1}{X}^{T}y$ into a single line of NumPy.

# Calculate theta_best using the Normal Equation formula
theta_best = np.linalg.inv(X_b.T @ X_b) @ X_b.T @ y

print(f"Optimal theta values (theta_0, theta_1): {theta_best.ravel()}")

You should get values very close to our original parameters, [4, 3]. The small difference is due to the random noise we added to y.

Step 4: Make Predictions

With our optimal theta_best vector, we can now make predictions on new data points. Remember, we also have to add the bias term to our new data before predicting.

# Let's predict values for x=0 and x=2
X_new = np.array([[0], [2]])

# Add the bias term (column of ones) to our new data
X_new_b = np.c_[np.ones((2, 1)), X_new]

# Make predictions
y_predict = X_new_b @ theta_best

print(f"\nPredictions for x=0 and x=2:\n{y_predict}")

# Plot the regression line
plt.scatter(X, y)
plt.plot(X_new, y_predict, "r-", label="Predictions")
plt.xlabel("Feature (x)")
plt.ylabel("Target (y)")
plt.title("Linear Regression with Normal Equation")
plt.legend()
plt.grid(True)
plt.show()

Conclusion

Congratulations! You have successfully implemented a completely different method for training a linear regression model. Unlike the iterative process of gradient descent, the Normal Equation provides a direct, analytical solution.

Key Takeaways:

• The Normal Equation is a closed-form formula, $\theta =(X^{T}X{)}^{-1}{X}^{T}y$, that solves for the optimal linear regression parameters analytically.
• It is a non-iterative method, meaning you don't need to choose a learning rate, worry about the number of iterations, or perform feature scaling.
• A critical implementation step is adding a column of ones to the feature matrix X to create the design matrix X_b, which accounts for the bias/intercept term ${\theta }_0$.
• The core of the implementation relies on standard linear algebra operations: matrix transposition, multiplication, and inversion, which are efficiently handled by NumPy.

Preview of the Next Lesson:
The Normal Equation seems incredibly direct and convenient. This raises an obvious question: if we have this powerful tool, why did we spend so much time learning about gradient descent? In the next lesson, we will answer exactly that by exploring the computational and practical trade-offs between gradient descent and the Normal Equation, helping you understand when to use each method.