The normal equations

The normal equations are a mathematical formulation used in linear regression to find the best-fitting line (or hyperplane) through a set of data points. They provide a way to directly compute the parameters (coefficients) of a linear model.

1. Overview of Linear Regression

In linear regression, we aim to model the relationship between a dependent variable y and one or more independent variables (features) x1​, x2​,…, xp​. The model can be expressed in the following linear form:

y=θ0​+θ1​x1​+θ2​x2​+…+θp​xp​

Where:

• θ₀​ is the intercept,
• θ1​,…,θp​ are the coefficients for the independent variables.

2. Objective of Linear Regression

The goal is to find the coefficients θ (represented as a vector) such that the predicted values y^​ minimize the sum of the squared differences between the observed values y and the predicted values y^​:

J(θ)=∑i=1n​(y(i)−y^​(i))2=∑i=1n​(y(i)−θTx(i))2

Where x(i) is the feature vector for the i-th observation, and y^​(i)=θTx(i).

3. Deriving the Normal Equations

To minimize the cost function J(θ), we perform gradient descent or directly derive the normal equations. The derivation involves taking the gradient of the cost function and setting it to zero.

Step 1: Matrix Formulation

Let X be the design matrix where each row corresponds to a training example and each column corresponds to a feature:

X=​11⋮1​x11​x21​⋮xn1​​x12​x22​⋮xn2​​……⋱…​x1p​x2p​⋮xnp​​​

The vector of outputs y can be represented as:

y=​y(1)y(2)⋮y(n)​​

And the parameters can be represented as a vector:

θ=​θ0​θ1​⋮θp​​​

Step 2: Cost Function in Matrix Form

The cost function can now be expressed in matrix form as:

J(θ)=(y−Xθ)T(y−Xθ)=yTy−2θTXTy+θTXTXθ

Step 3: Gradient Calculation

We take the gradient with respect to θ:

∇J(θ)=−2XTy+2XTXθ

Step 4: Setting Gradient to Zero

Setting the gradient to zero for minimization:

−2XTy+2XTXθ=0

This simplifies to:

XTXθ=XTy

This is the normal equation. If XTX is invertible, we can solve for θ:

θ=(XTX)−1XTy

4. Properties of the Normal Equations

• Efficiency: The normal equation provides a closed-form solution, which can be computed in one step rather than iteratively.
• Computational Complexity: The computation of (XTX)−1 can be computationally expensive for large datasets, leading to potential numerical stability issues.

5. Applications

The normal equations are used in:

• Linear Regression: To find the optimal parameters.
• Machine Learning Models: Many models leverage linear algebra formulations similar to the normal equations.

6. Limitations

While the normal equations are powerful, they have limitations:

• Inversion Problems: If XTX is singular (non-invertible), it leads to issues. This can occur when there is multicollinearity among features.
• Scalability: For very large datasets, iterative approaches such as gradient descent may be preferred due to computational constraints in computing the inverse.

Conclusion

The normal equations provide a foundational method for performing linear regression, allowing practitioners to derive model parameters efficiently when applicable conditions are met. More intricate formulations and algorithms can build upon this foundation for complex models and tasks in machine learning.