Exercises — Multiple linear regression

The "$+1$" for the intercept column makes the width of $\mathbf{X}$ equal to $n+1=6$.

• $\mathbf{X}$: $200\times 6$ — one row per example, one column per feature (plus the 1's).
• $\mathbf{\beta }$: $6\times 1$ — one weight per column of $\mathbf{X}$.
• $\mathbf{y}$: $200\times 1$ — one true target per example.
• ${\mathbf{X}}^{\top }\mathbf{X}$: $(6\times 200)(200\times 6)=6\times 6$ — a square matrix, the thing we invert.
• ${\mathbf{X}}^{\top }\mathbf{y}$: $(6\times 200)(200\times 1)=6\times 1$ — same shape as $\mathbf{\beta }$, good sanity check.

The trick: in $\mathbf{AB}$ the inner dimensions must match and cancel; the outer two survive. ${\mathbf{X}}^{\top }\mathbf{X}$ being $6\times 6$ (not $200\times 200$) is why the Normal Equation is cheap when features are few.

The sign of a coefficient is its direction of effect.

• ${\beta }_1=+0.5>0$ → raises $\hat{y}$.
• ${\beta }_2=-4<0$ → lowers $\hat{y}$. $\hat{y}=12+0.5(10)-4(2)=12+5-8=9$

Each row of $\mathbf{X}$ is dotted with $\mathbf{\beta }$. Row $i$ = $(1,x^{(i)})$, so the dot product is $1\cdot 3+x^{(i)}\cdot 2=3+2x^{(i)}$. $\hat{\mathbf{y}}=\left[\begin{array}{c}3+2(2)\\ 3+2(4)\\ 3+2(6)\end{array}\right]=\left[\begin{array}{c}7\\ 11\\ 15\end{array}\right]$ Notice: with one real feature this is just Simple Linear Regression written in matrix clothing.

${\mathbf{X}}^{\top }=\left[\begin{array}{ccc}1& 1& 1\\ 2& 4& 6\end{array}\right]$. Each entry of the product is a dot product of two columns of $\mathbf{X}$.

• Top-left = $1^2+1^2+1^2=3$ (just counts the examples, $m=3$).
• Off-diagonal = $2+4+6=12$ (sum of the feature).
• Bottom-right = $2^2+4^2+6^2=4+16+36=56$. ${\mathbf{X}}^{\top }\mathbf{X}=\left[\begin{array}{cc}3& 12\\ 12& 56\end{array}\right]$ For ${\mathbf{X}}^{\top }\mathbf{y}$:
• Top = $8+10+18=36$ (sum of targets).
• Bottom = $2(8)+4(10)+6(18)=16+40+108=164$. ${\mathbf{X}}^{\top }\mathbf{y}=\left[\begin{array}{c}36\\ 164\end{array}\right]$

Inverse of a $2\times 2$ matrix $\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$ is $\frac{1}{ad-bc}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$. Here the determinant is $ad-bc=3(56)-12(12)=168-144=24$. $({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}=\frac{1}{24}\left[\begin{array}{cc}56& -12\\ -12& 3\end{array}\right]$ Multiply by ${\mathbf{X}}^{\top }\mathbf{y}=\left[\begin{array}{c}36\\ 164\end{array}\right]$: ${\beta }_0=\frac{56(36)-12(164)}{24}=\frac{2016-1968}{24}=\frac{48}{24}=2$ ${\beta }_1=\frac{-12(36)+3(164)}{24}=\frac{-432+492}{24}=\frac{60}{24}=2.5$ So $\mathbf{\beta }=\left[\begin{array}{c}2\\ 2.5\end{array}\right]$, i.e. $\hat{y}=2+2.5x$. (Here $m>n$, so this is a genuine least-squares fit, not exact.)

Not invertible. $x_3=3x_1$ is perfect multicollinearity: one column is an exact linear multiple of another. That makes the columns of $\mathbf{X}$ linearly dependent, so ${\mathbf{X}}^{\top }\mathbf{X}$ is singular (determinant $0$) — even though $m\gg n$. Having lots of data cannot cure a redundant column. Geometrically: the model can't tell how to split credit between $x_1$ and $x_3$; infinitely many $({\beta }_1,{\beta }_3)$ pairs give the identical fit. Fixes: (1) drop the redundant column, or (2) add ridge penalty $\lambda \mathbf{I}$ so ${\mathbf{X}}^{\top }\mathbf{X}+\lambda \mathbf{I}$ becomes invertible again. Gradient Descent also converges without ever inverting.

Residuals $=y-\hat{y}$: $(3-2,4-4,5-6)=(1,0,-1)$. $S{S}_{res}=1^2+0^2+(-1{)}^2=2$ Total spread of $\mathbf{y}$ around its mean $\bar{y}=4$: deviations $(-1,0,1)$. $S{S}_{tot}=(-1{)}^2+0^2+1^2=2$ $R^2=1-\frac{2}{2}=0$ An $R^2$ of $0$ means the model does exactly as well as predicting the mean every time — no explanatory power here. See R-squared and Adjusted R-squared.

Ridge replaces ${\mathbf{X}}^{\top }\mathbf{X}$ with ${\mathbf{X}}^{\top }\mathbf{X}+\lambda \mathbf{I}$. Adding $\lambda =1$ to the diagonal: $\left[\begin{array}{cc}2+1& 6\\ 6& 18+1\end{array}\right]=\left[\begin{array}{cc}3& 6\\ 6& 19\end{array}\right]$ Determinant $=3(19)-6(6)=57-36=21\ne 0$. Invertible! The diagonal "bump" lifts the flat direction that made the original singular. That is exactly why Ridge Regression stabilises multicollinear problems.

The model is nonlinear in $x$ but linear in the coefficients ${\beta }_0,{\beta }_1,{\beta }_2$ — and the Normal Equation only cares about linearity in $\mathbf{\beta }$. So treat $x$ and $x^2$ as two separate feature columns: $\mathbf{X}=\left[\begin{array}{ccc}1& 1& 1\\ 1& 2& 4\\ 1& 3& 9\end{array}\right]$ (columns: intercept, $x$, $x^2$). Then $\mathbf{\beta }=({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\top }\mathbf{y}$ works unchanged. That is the whole idea behind Polynomial Regression.

(a) Build the pieces. ${\mathbf{X}}^{\top }\mathbf{X}=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right]$ (since $\sum x=6$, $\sum x^2=1+4+9=14$). ${\mathbf{X}}^{\top }\mathbf{y}=\left[\begin{array}{c}\sum y\\ \sum xy\end{array}\right]=\left[\begin{array}{c}6\\ 1+6+6\end{array}\right]=\left[\begin{array}{c}6\\ 13\end{array}\right]$. Determinant $=3(14)-6(6)=42-36=6$. $\mathbf{\beta }=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]\left[\begin{array}{c}6\\ 13\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}84-78\\ -36+39\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}6\\ 3\end{array}\right]=\left[\begin{array}{c}1\\ 0.5\end{array}\right]$ So $\hat{y}=1+0.5x$ (the red line in the figure). (b) Fitted values at $x=1,2,3$: $1.5,2.0,2.5$. Residuals $y-\hat{y}$: $(1-1.5,3-2.0,2-2.5)=(-0.5,1.0,-0.5)$. Notice they sum to $0$ — the fitted line balances the errors (a property of the least-squares intercept). (c) $\hat{y}(5)=1+0.5(5)=3.5$.

(a) With $m=25<n=40$, ${\mathbf{X}}^{\top }\mathbf{X}$ is singular, so strictly the inverse doesn't exist — a solver returns a pseudoinverse solution (minimum-norm), which is why you still got numbers. It is one of infinitely many perfect-fit answers. (b) More unknowns than equations means the plane can thread exactly through every training point → zero residual → $R^2=1.0$. That's memorisation, not learning: textbook Overfitting. Perfect training fit with few examples is a red flag. (c) (1) Regularise with Ridge Regression to shrink coefficients and pick a stable solution; (2) reduce features / gather more data so $m>n$; (Gradient Descent with early stopping also helps).

The Normal Equation is ::: $\mathbf{\beta }=({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\top }\mathbf{y}$ ${\mathbf{X}}^{\top }\mathbf{X}$ is singular when features are perfectly multicollinear or when ::: there are fewer examples than features ($m<n$) The diagonal fix that restores invertibility is called ridge (add $\lambda \mathbf{I}$) $R^2=0$ means the model does no better than ::: predicting the mean of $y$ every time