Linear Regression

The goal

In supervised learning for continuous outputs, you want a model that maps an input feature vector to a real number:

• •Input (features): a vector x ∈ ℝᵈ
• •Output (target): y ∈ ℝ

Linear regression is the simplest widely useful choice:

• •Model: predict with a linear function of features.

The linear predictive model

For one example with features x, linear regression predicts

ŷ = β₀ + β₁x₁ + β₂x₂ + … + β_d x_d

To keep notation clean, we fold the intercept into the feature vector by adding a constant feature:

• •Define x₀ = 1
• •Define β = [β₀, β₁, …, β_d]ᵀ
• •Define x = [x₀, x₁, …, x_d]ᵀ

Then the prediction becomes a dot product:

ŷ = xᵀβ

From one example to a dataset

Suppose you have n training examples. Stack them into a design matrix X:

• •X ∈ ℝⁿˣᵖ where p = d+1 if you included the intercept column of ones
• •Each row i is xᵢᵀ

Also stack targets into a vector:

• •y ∈ ℝⁿ

Predictions for all examples at once:

ŷ = Xβ

This compact form is the main reason linear regression is such a good “bridge” topic: it connects machine learning, linear algebra, geometry, and optimization.

Why the squared error?

You need a rule for choosing β. Linear regression chooses β to make predictions close to y.

Define residuals:

r = y − Xβ

A natural idea is to minimize total error. But we need a scalar objective. Squared error is the classic choice:

SSE(β) = ∑ᵢ (yᵢ − ŷᵢ)² = ‖y − Xβ‖²

Why square?

• •It penalizes large mistakes more than small ones.
• •It yields a smooth, convex objective (one global minimum).
• •It leads to closed-form solutions via linear algebra.

What you should keep in mind

Linear regression is not “the true relationship is linear.” It’s:

• •“I will approximate the relationship with a linear function of chosen features.”

You can include nonlinear transformations as features (e.g., x², log x), and the model is still linear in β.

The optimization problem

Least squares fitting means choosing β to minimize squared residual length:

minimize over β: J(β) = ‖y − Xβ‖²

This is a geometry problem wearing an optimization costume.

• •Xβ is restricted to lie in the column space of X (all linear combinations of columns).
• •You want the point Xβ in that subspace that is closest to y.

So the fitted predictions Xβ̂ are the orthogonal projection of y onto Col(X).

Expanding the objective (so we can take derivatives)

Write J(β) as a quadratic form:

J(β) = (y − Xβ)ᵀ(y − Xβ)

Expand carefully:

J(β)

= (yᵀ − βᵀXᵀ)(y − Xβ)

= yᵀy − yᵀXβ − βᵀXᵀy + βᵀXᵀXβ

Note that yᵀXβ is a scalar, and equals its transpose:

yᵀXβ = ( yᵀXβ )ᵀ = βᵀXᵀy

So the middle two terms combine:

J(β) = yᵀy − 2βᵀXᵀy + βᵀXᵀXβ

This makes it clear J(β) is a convex quadratic function in β.

The gradient and the normal equations

To minimize J(β), set its gradient to zero.

Using standard matrix calculus results:

∂/∂β (βᵀAβ) = (A + Aᵀ)β, and when A is symmetric: = 2Aβ

Here A = XᵀX, which is symmetric.

Compute the gradient:

∇β J(β)

= ∇β( yᵀy − 2βᵀXᵀy + βᵀXᵀXβ )

= 0 − 2Xᵀy + 2XᵀXβ

Set ∇β J(β) = 0:

2XᵀXβ − 2Xᵀy = 0

Divide by 2:

XᵀXβ = Xᵀy

These are the normal equations.

Solving for β̂

If XᵀX is invertible (full column rank), then

β̂ = (XᵀX)⁻¹ Xᵀ y

This is the classic closed-form least squares solution.

If XᵀX is not invertible (e.g., perfectly collinear features), there are infinitely many solutions that achieve the same minimum SSE. A common choice is the minimum-norm solution via the Moore–Penrose pseudoinverse:

β̂ = X⁺ y

The projection viewpoint (link to prerequisites)

At the optimum, residual r = y − Xβ̂ is orthogonal to the column space of X.

In algebra:

Xᵀ(y − Xβ̂) = 0

which rearranges to the normal equations.

So you can read the normal equations as:

• •“Residuals are perpendicular to every column of X.”

That is exactly the condition for an orthogonal projection.

What least squares is really doing

Least squares chooses β to balance tradeoffs across all points.

• •You generally can’t make all residuals zero unless y lies in Col(X) (perfectly representable).
• •Instead, you choose the closest representable vector Xβ to y.

This is why linear regression is both:

• •An optimization algorithm: minimize SSE
• •A linear algebra operation: projection onto a subspace

The intercept as a constant feature

Including an intercept means adding a column of ones:

X = [ 1 | feature columns ]

This matters because without an intercept, the model is forced to go through the origin in feature space (in 1D, the line must pass through (0,0)). In real data, that constraint is often unjustified and increases error.

Shapes and dimensions (so you don’t get lost)

It helps to keep a mental “type system” for linear regression:

• •X: n × p (n examples, p features including intercept)
• •β: p × 1
• •y: n × 1
• •Xβ: n × 1
• •XᵀX: p × p
• •Xᵀy: p × 1

If you ever feel stuck, check dimensions first.

Geometry: column space and projections

The set of all predictions the model can make is

{ Xβ : β ∈ ℝᵖ } = Col(X)

That is a subspace of ℝⁿ (or an affine subspace if you treat the intercept differently; with the column-of-ones trick, it’s still a linear subspace in ℝⁿ).

The fitted predictions are

ŷ = Xβ̂ = Proj_{Col(X)}(y)

The residual vector

r = y − ŷ

is orthogonal to Col(X).

When does (XᵀX)⁻¹ exist?

(XᵀX) is invertible iff the columns of X are linearly independent (full column rank). Practically, it can fail for several reasons:

• •Perfect multicollinearity: one feature is an exact linear combination of others.
• •Too many features: p > n guarantees rank ≤ n < p, so not invertible.
• •Redundant intercept: e.g., you accidentally include two constant columns.

Even if it exists, it can be numerically unstable if XᵀX is ill-conditioned.

Practical numerical note: don’t literally invert

Although the formula β̂ = (XᵀX)⁻¹Xᵀy is conceptually important, computing the inverse explicitly is usually a bad idea numerically.

Common stable approaches:

This lesson focuses on the conceptual math; just remember that implementations often use QR/SVD under the hood.

Centering and scaling (feature preprocessing)

Least squares itself doesn’t require scaling, but conditioning and interpretation improve when you:

• •center features (subtract mean)
• •scale features (divide by standard deviation)

Centering also interacts with the intercept:

• •If each non-intercept feature has mean 0, then β₀ becomes the mean of y (when the model includes only intercept) and is often more interpretable.

A note on “linear”

Linear regression is linear in parameters β, not necessarily linear in raw input.

Example: If you use features [1, x, x²], predictions are

ŷ = β₀ + β₁x + β₂x²

This is a quadratic curve in x, but still a linear regression model because it is a linear combination of features with coefficients β.

Using the model to predict

After fitting β̂, predictions for a new example xₙₑw are

ŷₙₑw = xₙₑwᵀ β̂

For a batch of new examples Xₙₑw:

ŷₙₑw = Xₙₑw β̂

Interpreting coefficients (carefully)

If feature xⱼ increases by 1 (holding other features fixed), the prediction changes by βⱼ.

That “holding fixed” clause is crucial: in correlated data, changing one feature while keeping others constant may describe a scenario that doesn’t naturally occur.

Common evaluation metrics

Since the training objective is SSE, related metrics are common:

• •MSE = (1/n)‖y − Xβ̂‖²
• •RMSE = √MSE
• •MAE = (1/n)∑ᵢ |yᵢ − ŷᵢ| (not the training objective here, but popular)

R² as “variance explained” (intuition)

Define:

• •SSE = ∑ᵢ (yᵢ − ŷᵢ)²
• •SST = ∑ᵢ (yᵢ − ȳ)² where ȳ is mean of y

Then

R² = 1 − SSE/SST

Interpretation:

• •R² = 0 means “no better than predicting the mean.”
• •R² = 1 means perfect fit.

Be cautious: R² always (weakly) increases when you add features, even useless ones. This is one reason regularization (like ridge regression) matters later.

Overfitting and generalization

Linear regression can still overfit when:

• •you add too many features
• •you add high-degree polynomial features
• •you have limited data with noisy targets

Least squares will chase patterns in the sample even if they are not stable.

The usual fix is to evaluate on held-out data (validation/test) and/or add regularization.

Why linear regression is foundational

Linear regression is a gateway to many later ideas:

• •Gradient descent: minimizing a convex objective
• •Regularization: ridge/lasso as modified least squares
• •Probabilistic modeling: with Gaussian noise assumptions, least squares becomes maximum likelihood
• •Generalized linear models: logistic regression changes the output link but keeps linear predictors
• •Neural networks: last layer often is linear; training uses similar principles

If you understand linear regression deeply—especially the projection view—you’re set up to understand a lot of ML with much less memorization.