Linear Regression

Least squares, its geometry, and regularized regression.

Linear Regression

Fitting a straight line (or plane) to data by least squares: the formulas, the geometry behind them, what goes wrong when assumptions fail, and the regularized and logistic variants.

Simple linear regression

Model – Observe nn pairs (xi,yi)(x_i, y_i) and assume yy depends linearly on one input xx plus random noise εi\varepsilon_i with mean zero. The intercept α\alpha and slope β\beta are unknown.

yi=α+βxi+εiy_i = \alpha + \beta x_i + \varepsilon_i

Least squares – Choose α^,β^\hat\alpha, \hat\beta to minimize the residual sum of squares (RSS), the total squared vertical distance from the points to the line. Each yi−α^−β^xiy_i - \hat\alpha - \hat\beta x_i is a residual.

RSS=∑i=1n(yi−α^−β^xi)2\text{RSS} = \sum_{i=1}^n (y_i - \hat\alpha - \hat\beta x_i)^2

Notation – With means xˉ,yˉ\bar x, \bar y, define the sums of squares and cross-products

Sxx=∑i(xi−xˉ)2,Syy=∑i(yi−yˉ)2,Sxy=∑i(xi−xˉ)(yi−yˉ)S_{xx} = \sum_i (x_i - \bar x)^2, \qquad S_{yy} = \sum_i (y_i - \bar y)^2, \qquad S_{xy} = \sum_i (x_i - \bar x)(y_i - \bar y)

Sample correlation – r=Sxy/SxxSyyr = S_{xy}/\sqrt{S_{xx}S_{yy}}, a number in [−1,1][-1, 1] measuring how close the points are to a line.

Estimates – Setting the derivatives of RSS to zero gives

β^=SxySxx=r sysx,α^=yˉ−β^ xˉ\hat\beta = \frac{S_{xy}}{S_{xx}} = r\,\frac{s_y}{s_x}, \qquad \hat\alpha = \bar y - \hat\beta\,\bar x

where sx,sys_x, s_y are the sample standard deviations. The fitted line always passes through (xˉ,yˉ)(\bar x, \bar y).

Residual error – At the optimum,

RSS=Syy−β^Sxy=Syy(1−r2)\text{RSS} = S_{yy} - \hat\beta S_{xy} = S_{yy}(1 - r^2)

and s2=RSS/(n−2)s^2 = \text{RSS}/(n-2) is an unbiased estimate of the noise variance.

Regressing xx on yy gives slope r sx/syr\,s_x/s_y, which is not 1/β^1/\hat\beta unless the points lie exactly on a line.

Multiple regression (ordinary least squares)

Model – With pp inputs, stack the data into a vector y∈Rny \in \mathbb{R}^n and a design matrix X∈Rn×pX \in \mathbb{R}^{n \times p} whose row ii holds the inputs for observation ii (include a column of ones for an intercept):

y=Xβ+εy = X\beta + \varepsilon

Ordinary least squares (OLS) – Minimize the squared length of the residual vector, ∥y−Xβ∥2=∑i(yi−xi⊤β)2\lVert y - X\beta\rVert^2 = \sum_i (y_i - x_i^\top\beta)^2. Setting the gradient to zero gives the normal equations X⊤Xβ^=X⊤yX^\top X\hat\beta = X^\top y, so when the columns of XX are linearly independent

β^=(X⊤X)−1X⊤y\hat\beta = (X^\top X)^{-1}X^\top y

Numerically, solve with a QR or singular value decomposition rather than inverting X⊤XX^\top X, which squares the sensitivity to rounding error.

Hat matrix – The fitted values are y^=Xβ^=Py\hat y = X\hat\beta = Py with

P=X(X⊤X)−1X⊤P = X(X^\top X)^{-1}X^\top

PP projects any vector onto the column space of XX, the set of all vectors of the form XβX\beta.

Residual maker – M=I−PM = I - P projects onto the directions perpendicular to that space, and produces the residuals: ε^=y−y^=My\hat\varepsilon = y - \hat y = My.

Properties – PP and MM are both symmetric (P⊤=PP^\top = P) and idempotent (P2=PP^2 = P: projecting twice changes nothing). Also PX=XPX = X and MX=0MX = 0, so the residuals depend only on the noise:

ε^=M(Xβ+ε)=Mε\hat\varepsilon = M(X\beta + \varepsilon) = M\varepsilon

X⊤ε^=0X^\top\hat\varepsilon = 0, so the residuals are uncorrelated with every input. Least squares is the orthogonal projection of yy onto the space the inputs can reach.

Variance of the estimate – If the noise has variance σ2\sigma^2, Var⁡(β^)=σ2(X⊤X)−1\operatorname{Var}(\hat\beta) = \sigma^2(X^\top X)^{-1}, with σ2\sigma^2 estimated by RSS/(n−p)\text{RSS}/(n-p).

Gauss–Markov theorem – If the errors have mean zero, constant variance and are uncorrelated, OLS has the smallest variance among all unbiased estimators that are linear in yy (it is the "best linear unbiased estimator", BLUE). If the errors are also normal, OLS equals the maximum likelihood estimate.

Goodness of fit

Decomposition of variation – With an intercept, the total sum of squares TSS=∑i(yi−yˉ)2\text{TSS} = \sum_i (y_i - \bar y)^2 splits into an explained part ESS=∑i(y^i−yˉ)2\text{ESS} = \sum_i (\hat y_i - \bar y)^2 and the residual part: TSS=ESS+RSS\text{TSS} = \text{ESS} + \text{RSS}.

Coefficient of determination – The fraction of variation explained:

R2=1−RSSTSSR^2 = 1 - \frac{\text{RSS}}{\text{TSS}}

For simple linear regression, R2=r2R^2 = r^2.

Adjusted R2R^2 – R2R^2 never decreases when an input is added, even a useless one. The adjusted version penalizes the number of inputs pp:

Rˉ2=1−(1−R2)n−1n−p−1\bar R^2 = 1 - (1 - R^2)\frac{n-1}{n-p-1}

When the assumptions fail

ProblemWhat goes wrongUsual fix
Omitted variable that is correlated with an included inputβ^\hat\beta is biasedinclude it, or use instrumental variables
Highly correlated inputs (multicollinearity)β^\hat\beta is unstable, with large varianceridge regression, or drop or combine inputs
Noise variance changes with xx (heteroscedasticity)standard errors are wrongrobust (White) standard errors, weighted least squares
Errors correlated over timestandard errors are wrongNewey–West standard errors, generalized least squares
Noise in the inputs themselvesβ^\hat\beta is shrunk toward zero (attenuation)instrumental variables, errors-in-variables models

Regularization

Adding a penalty on the size of β\beta trades a little bias for lower variance, with strength set by λ≥0\lambda \ge 0.

MethodMinimizesEffect
Ridge∥y−Xβ∥2+λ∥β∥22\lVert y - X\beta\rVert^2 + \lambda\lVert\beta\rVert_2^2closed form (X⊤X+λI)−1X⊤y(X^\top X + \lambda I)^{-1}X^\top y; shrinks all coefficients and stabilizes correlated inputs
Lasso∥y−Xβ∥2+λ∥β∥1\lVert y - X\beta\rVert^2 + \lambda\lVert\beta\rVert_1no closed form; sets some coefficients exactly to zero
Elastic netboth penaltiessparse, but keeps groups of correlated inputs together

Here ∥β∥22=∑jβj2\lVert\beta\rVert_2^2 = \sum_j\beta_j^2 and ∥β∥1=∑j∣βj∣\lVert\beta\rVert_1 = \sum_j\lvert\beta_j\rvert.

Logistic regression

Model – For a yes/no outcome y∈{0,1}y \in \{0, 1\}, model the probability of "yes" by passing a linear score through the sigmoid σ(z)=1/(1+e−z)\sigma(z) = 1/(1 + e^{-z}), which maps any number into (0,1)(0, 1):

P(y=1∣x)=σ(x⊤β)P(y = 1 \mid x) = \sigma(x^\top\beta)

Fitting – Maximize the likelihood, equivalently minimize the negative log-likelihood, which is convex (bowl-shaped, so it has a single minimum). Its gradient is

X⊤(σ(Xβ)−y)X^\top\big(\sigma(X\beta) - y\big)

There is no closed form, so it is solved with gradient descent or Newton's method (iteratively reweighted least squares).

If a line separates the two classes perfectly, the coefficients grow without bound unless a penalty is added.