Linear Models

Full derivations from loss function through closed-form solution, gradient, and probabilistic interpretation.

Table of contents

1. Linear regression (OLS)
2. Ridge regression
3. Lasso regression
4. Elastic Net
5. Logistic regression
6. Multiclass: softmax regression
7. Generalized linear models (overview)
8. Code examples

1. Linear regression (OLS)

1.1 Model

Given features $\mathbf{x} \in \mathbb{R}^p$ (we prepend 1 for intercept so $\mathbf{x} \in \mathbb{R}^{p+1}$) and scalar target $y \in \mathbb{R}$:

Stacked over $n$ samples: $\hat{\mathbf{y}} = \mathbf{X}\mathbf{w}$, where $\mathbf{X} \in \mathbb{R}^{n \times (p+1)}$.

1.2 Objective: residual sum of squares

Expanded:

1.3 Normal equations (closed-form solution)

Gradient w.r.t. $\mathbf{w}$ (using matrix calculus identities):

Setting to zero:

These are the normal equations. If $\mathbf{X}^\top\mathbf{X}$ is invertible (columns of $\mathbf{X}$ linearly independent):

The Hessian $\nabla^2 \text{RSS} = 2\mathbf{X}^\top\mathbf{X} \succeq 0$ (PSD) confirms this is a global minimum. Strictly so if $\mathbf{X}$ has full column rank.

1.4 Geometric interpretation

$\hat{\mathbf{y}} = \mathbf{X}\mathbf{w}^\star = \mathbf{X}(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top\mathbf{y} =: \mathbf{H}\mathbf{y}$.

$\mathbf{H} = \mathbf{X}(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top$ is the hat/projection matrix. It is idempotent ($\mathbf{H}^2=\mathbf{H}$) and orthogonal projection onto column space of $\mathbf{X}$.

Residual vector: $\mathbf{r} = \mathbf{y}-\hat{\mathbf{y}} = (\mathbf{I}-\mathbf{H})\mathbf{y}$, which is orthogonal to column space of $\mathbf{X}$: $\mathbf{X}^\top\mathbf{r} = \mathbf{0}$.

1.5 MLE derivation

Assume $y_i = \mathbf{x}_i^\top\mathbf{w} + \varepsilon_i$, $\varepsilon_i \sim \mathcal{N}(0,\sigma^2)$ i.i.d.

Log-likelihood:

Maximizing over $\mathbf{w}$: same as minimizing $\sum(y_i-\mathbf{x}_i^\top\mathbf{w})^2$ = OLS. So OLS = MLE under Gaussian noise assumption.

1.6 Gauss-Markov theorem

OLS estimator is the Best Linear Unbiased Estimator (BLUE): among all linear estimators that are unbiased, OLS has minimum variance.

Conditions: $\mathbb{E}[\boldsymbol{\varepsilon}]=\mathbf{0}$, $\text{Var}(\boldsymbol{\varepsilon})=\sigma^2\mathbf{I}$ (homoscedastic, uncorrelated errors).

1.7 When OLS fails

1.8 Evaluating regression models

Mean Squared Error (MSE): $\frac{1}{n}\sum(y_i-\hat{y}_i)^2$. Same units as $y^2$. Root MSE (RMSE): $\sqrt{\text{MSE}}$. Same units as $y$. Mean Absolute Error (MAE): $\frac{1}{n}\sum|y_i-\hat{y}_i|$. More robust to outliers. R² (coefficient of determination):

Fraction of variance explained. $R^2=1$ is perfect fit. Adding irrelevant features can only increase (or keep equal) $R^2$ — use adjusted $R^2$ to account for model complexity.

2. Ridge regression

2.1 Objective and motivation

Adding L2 penalty to OLS:

where $\mathbf{w}_{-0}$ excludes the intercept (common convention; center features to avoid penalizing intercept).

2.2 Closed-form solution

Gradient:

where $\mathbf{D} = \operatorname{diag}(0, 1, \ldots, 1)$ (no penalty on intercept).

Setting to zero:

$\lambda\mathbf{D}$ adds to the diagonal → always invertible for $\lambda > 0$. Solves multicollinearity.

2.3 SVD analysis (why Ridge shrinks)

Let $\mathbf{X} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top$ (thin SVD). Then:

Compare OLS: factor $\frac{\sigma_j^2}{\sigma_j^2+\lambda}$ vs. 1. Ridge shrinks each component by $\frac{\sigma_j^2}{\sigma_j^2+\lambda} < 1$, with more shrinkage for small $\sigma_j$ (low-variance directions = unstable OLS directions).

2.4 Bayesian view

Ridge is MAP with Gaussian prior $\mathbf{w} \sim \mathcal{N}(\mathbf{0}, \frac{\sigma^2}{\lambda}\mathbf{I})$:

2.5 Choosing $\lambda$

Cross-validation is the standard approach. sklearn.linear_model.RidgeCV does LOO-CV efficiently via the hat matrix.

3. Lasso regression

3.1 Objective

No closed form (L1 is non-differentiable at zero). Solved by coordinate descent or proximal gradient.

3.2 Why Lasso induces sparsity (geometric argument)

Consider contours of RSS (ellipses in 2D) intersecting the constraint region:

• L2 constraint: $\|\mathbf{w}\|^2 \leq t$ — a smooth ball. Contours typically touch the ball interior → non-sparse.
• L1 constraint: $\|\mathbf{w}\|_1 \leq t$ — a diamond with sharp corners at axes. Contours often touch a corner → one coordinate exactly zero = sparsity.

3.3 Coordinate descent for Lasso

Update one coordinate at a time, holding others fixed. Let $r_j^{(i)} = y_i - \sum_{k \neq j} w_k x_{ik}$ be the partial residual. Then:

where soft-thresholding (ST):

Intuition: if the correlation of feature $j$ with partial residual is small (below threshold), set $w_j = 0$.

3.4 Lasso path (LARS algorithm)

As $\lambda$ decreases from $\|\frac{1}{n}\mathbf{X}^\top\mathbf{y}\|_\infty$ to 0:

• Start: $\mathbf{w} = \mathbf{0}$.
• First variable enters the model when its correlation with current residual exceeds threshold.
• LARS (Least Angle Regression) computes the entire regularization path at cost of one OLS fit.

3.5 Bayesian view

Lasso is MAP with Laplace (double-exponential) prior:

which has heavier tails than Gaussian → accommodates more extreme values in some components and zeros in others.

4. Elastic Net

4.1 Objective

Or parameterized with $\alpha \in [0,1]$ and overall penalty $\lambda$:

$\alpha=1$ = Lasso, $\alpha=0$ = Ridge. sklearn uses this parameterization.

4.2 Advantages over Lasso

• Handles groups of correlated features: Lasso picks one arbitrarily; ElasticNet can retain all.
• The L2 component ensures uniqueness of solution.
• Sparsity still encouraged by L1.

5. Logistic regression

5.1 From regression to classification

Linear regression for binary labels $y \in \{0,1\}$ is poor: predictions can go outside $[0,1]$, squared loss is not ideal for probabilities.

Logistic regression models the log-odds (logit) as a linear function:

Solving for the probability:

5.2 Sigmoid function properties

• $\sigma(-\infty)=0$, $\sigma(0)=0.5$, $\sigma(+\infty)=1$.
• Derivative: $\sigma'(z) = \sigma(z)(1-\sigma(z))$. (Proof: apply quotient rule.)
• Symmetric: $1-\sigma(z) = \sigma(-z)$.

5.3 Negative log-likelihood (cross-entropy loss)

For binary labels, the Bernoulli likelihood of one sample:

Log-likelihood over all $n$ samples:

Cross-entropy loss = negative log-likelihood:

5.4 Gradient derivation

Gradient of loss for one sample $i$:

Step 1 (chain rule through sigmoid):

Proof:

(Uses $\sigma'=\sigma(1-\sigma)$.)

Step 2: $\frac{\partial z_i}{\partial \mathbf{w}} = \mathbf{x}_i$.

Combined (averaged):

Elegant: same form as linear regression gradient but with $\mathbf{p} = \sigma(\mathbf{X}\mathbf{w})$ instead of $\mathbf{X}\mathbf{w}$.

5.5 Hessian (confirms convexity)

Since $p_i(1-p_i) > 0$, $\mathbf{W}\succ 0$, and $\mathbf{X}^\top\mathbf{W}\mathbf{X} \succeq 0$ (PSD). So logistic regression loss is convex (strictly, if $\mathbf{X}$ full column rank).

5.6 Optimization

No closed-form. Use:

• Gradient descent / mini-batch SGD (scale to huge datasets).
• Newton-Raphson / IRLS: $\mathbf{w}_{t+1} = \mathbf{w}_t - (\nabla^2\mathcal{L})^{-1}\nabla\mathcal{L}$. Equivalent to iteratively reweighted least squares. Converges quadratically near optimum.
• L-BFGS: quasi-Newton, efficient for medium-sized data.

5.7 Decision boundary

Predict class 1 if $P(y=1|\mathbf{x}) \geq 0.5$, i.e., if $\mathbf{w}^\top\mathbf{x} \geq 0$.

Decision boundary: the hyperplane $\mathbf{w}^\top\mathbf{x} = 0$. Logistic regression is a linear classifier.

The threshold 0.5 is not always optimal: in imbalanced problems or asymmetric costs, choose threshold via ROC analysis.

5.8 Regularized logistic regression

Add L2: $\mathcal{L}_\text{Ridge} = \mathcal{L} + \frac{\lambda}{2n}\|\mathbf{w}\|^2$. sklearn uses $C = 1/\lambda$ (larger $C$ = less regularization).

6. Multiclass: softmax regression

6.1 Model

For $K$ classes, assign one weight vector $\mathbf{w}_k \in \mathbb{R}^p$ per class. Let $\mathbf{W} \in \mathbb{R}^{K\times p}$.

Softmax function turns logits $\mathbf{z} = \mathbf{W}\mathbf{x}$ into probabilities:

Numerical stability: subtract $\max_j z_j$ before exponentiating (doesn't change softmax, avoids overflow).

6.2 Categorical cross-entropy loss

With one-hot encoding $\mathbf{e}_k$ for class $k$, this simplifies to $-\frac{1}{n}\sum_i \log P(y=y_i|\mathbf{x}_i)$.

6.3 Gradient

Same "prediction minus target" structure as binary logistic.

6.4 Binary vs multiclass approaches

7. Generalized linear models (overview)

GLMs unify many models: linear regression, logistic regression, Poisson regression, etc.

A GLM has three components:

1. Random component: $y \sim$ exponential family with mean $\mu$.
2. Systematic component: $\eta = \mathbf{w}^\top\mathbf{x}$ (linear predictor).
3. Link function $g$: $g(\mu) = \eta$.

8. Code examples

See the classical_examples/ directory (created with ML_NOTES.md) for:

Sklearn cheatsheet for linear models

from sklearn.linear_model import (
    LinearRegression,
    Ridge, RidgeCV,
    Lasso, LassoCV,
    ElasticNet, ElasticNetCV,
    LogisticRegression,
)

# Ridge with CV-selected alpha
model = RidgeCV(alphas=[0.1, 1.0, 10.0], cv=5)
model.fit(X_train, y_train)
print(model.alpha_)  # best alpha

# Lasso (coordinate descent)
lasso = LassoCV(cv=5, max_iter=10_000)
lasso.fit(X_train, y_train)
print(lasso.alpha_)
print(np.sum(lasso.coef_ != 0))  # number of nonzero (selected) features

# Logistic regression (C = 1/lambda, larger = less regularization)
clf = LogisticRegression(C=1.0, penalty='l2', solver='lbfgs', max_iter=1000)
clf.fit(X_train, y_train)
clf.predict_proba(X_test)  # calibrated probabilities

*File: notes/03_linear_models.md — next: notes/04_optimization.md*