Exercises — Ordinary least squares derivation

WHAT we do: just count rows and columns.

• Feature block (no bias): $4\times 2$ — four points, two features.
• $X$ (bias glued on): $4\times 3$ — the extra column of $1$s is the third column.
• $\theta$: $3\times 1$ — one number per column of $X$ (${\theta }_0$ for the bias, then ${\theta }_1,{\theta }_2$).
• $y$: $4\times 1$ — one target per data point.
• $X^{T}X$: $X^T$ is $3\times 4$, times $X$ which is $4\times 3$, gives $\boxed{3\times 3}$.

WHY it's square: $X^{T}X$ is always $(n+1)\times (n+1)$. That is why we can ask whether it is invertible at all — only square matrices have inverses.

• $X$ holds the given data (fixed once your dataset is chosen).
• $\theta$ holds the unknowns you solve for.
• Number of unknowns $=n+1=6$: one weight per feature (${\theta }_1\dots {\theta }_5$) plus the intercept ${\theta }_0$.

Step 1 — build $X$ and $y$ (first column is the bias $1$s): $X=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\end{array}\right],y=\left[\begin{array}{c}1\\ 3\\ 3\end{array}\right]$ Step 2 — $X^{T}X$ (WHY: the normal equation needs it): $X^{T}X=\left[\begin{array}{cc}3& 3\\ 3& 5\end{array}\right],X^{T}y=\left[\begin{array}{c}7\\ 9\end{array}\right]$ (Top-left $=1+1+1=3$; the $3$s are $0+1+2$; bottom-right $=0+1+4=5$. For $X^{T}y$: $1+3+3=7$ and $0+3+6=9$.) Step 3 — invert. $\det =3\cdot 5-3\cdot 3=6$. $(X^{T}X{)}^{-1}=\frac{1}{6}\left[\begin{array}{cc}5& -3\\ -3& 3\end{array}\right]$ Step 4 — solve ${\theta }^{\ast }=(X^{T}X{)}^{-1}{X}^{T}y$: ${\theta }^{\ast }=\frac{1}{6}\left[\begin{array}{cc}5& -3\\ -3& 3\end{array}\right]\left[\begin{array}{c}7\\ 9\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}35-27\\ -21+27\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}8\\ 6\end{array}\right]=\left[\begin{array}{c}4/3\\ 1\end{array}\right]$ Answer: ${\theta }_0=4/3$, ${\theta }_1=1$, so $\hat{y}=\frac{4}{3}+x$. At $x=1$: $\hat{y}=7/3\approx 2.33$.

Look at the fitted line in the figure below — it splits the gap between the point at $(1,3)$ (above) and the trend, exactly the balancing act least squares performs.

Predictions: $\hat{y}=X{\theta }^{\ast }=(\frac{4}{3},\frac{4}{3}+1,\frac{4}{3}+2)=(\frac{4}{3},\frac{7}{3},\frac{10}{3})$. Residuals $r=\hat{y}-y=(\frac{4}{3}-1,\frac{7}{3}-3,\frac{10}{3}-3)=(\frac{1}{3},-\frac{2}{3},\frac{1}{3})$. Check $X^{T}r$:

• Row of $1$s: $\frac{1}{3}-\frac{2}{3}+\frac{1}{3}=0$. ✓
• Row of $x$'s $(0,1,2)$: $0\cdot \frac{1}{3}+1\cdot (-\frac{2}{3})+2\cdot \frac{1}{3}=-\frac{2}{3}+\frac{2}{3}=0$. ✓

Geometric meaning: the residual vector is perpendicular to every column of $X$ — the leftover error points straight out of the space of fittable lines, so no adjustment of $\theta$ can shrink it. That perpendicularity is literally why it's called the "normal" equation.

Look for a linear dependence among columns. Call them $c_0=(1,1,1)$, $c_1=(2,3,4)$, $c_2=(5,7,9)$. Test $c_2=a{c}_0+b{c}_1$: solving $5=a+2b$, $7=a+3b$ gives $b=2,a=1$; check the third row $1+2\cdot 4=9$. ✓ So $c_2=c_0+2c_1$ exactly — the columns are linearly dependent, meaning $X$ does not have full column rank. Therefore $\det (X^{T}X)=0$ and the inverse does not exist. The cost has infinitely many minimisers (any shift of $\theta$ along the dependence direction leaves $X\theta$ unchanged). Cure: drop the redundant feature, or add regularisation (Ridge Regression).

The metres column and the feet column are scalar multiples of each other, so they count as one independent direction. With the bias that gives $\text{rank}(X)=2$, but $X$ has $3$ columns — so it is rank-deficient ($\text{rank}<n+1$). This is the "perfectly correlated features" failure (°C vs °F is the same story). $X^{T}X$ is singular; use Feature Scaling won't save you — you must remove one of the duplicated features or regularise.

New cost: $J(\theta )=\frac{1}{2m}[(X\theta -y{)}^T(X\theta -y)+\lambda {\theta }^T\theta ]$. Gradient (using the same rules from the parent: ${\partial }_{\theta }({\theta }^{T}A\theta )=2A\theta$, ${\partial }_{\theta }(a^T\theta )=a$): ${\nabla }_{\theta }J=\frac{1}{m}[X^{T}X\theta -X^{T}y+\lambda \theta ].$ Set to zero: $X^{T}X\theta +\lambda \theta =X^{T}y\Rightarrow (X^{T}X+\lambda I)\theta =X^{T}y$. $\boxed{{\theta }^{\ast }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y}$ Why invertible: $X^{T}X$ is always positive semi-definite (eigenvalues $\ge 0$). Adding $\lambda I$ bumps every eigenvalue up by $\lambda >0$, so none is zero — the matrix becomes positive definite and always invertible. See Ridge Regression.

WHAT: the probability of one point is the Gaussian density $p(y_i\mid x_i,\theta )=\frac{1}{\sqrt{2\pi }\sigma }\exp \left(-\frac{(y_i-{\theta }^T{x}_i{)}^2}{2{\sigma }^2}\right).$ WHY log: the full likelihood is the product over all $m$ points; taking $\log$ turns the product into a sum we can differentiate, and $\log$ is increasing so the maximiser is unchanged. $\log \mathcal{L}=-m\log (\sqrt{2\pi }\sigma )-\frac{1}{2{\sigma }^2}{\sum }_{i=1}^m(y_i-{\theta }^T{x}_i{)}^2.$ Only the last term depends on $\theta$, and it carries a minus sign. So maximising $\log \mathcal{L}$ = minimising ${\sum }_i(y_i-{\theta }^T{x}_i{)}^2$ — the least-squares sum. Hence OLS is maximum likelihood under Gaussian noise. See Maximum Likelihood Estimation.

WHY QR: because $Q^{T}Q=I$, the messy $X^{T}X$ collapses: $X^{T}X=(QR{)}^T(QR)=R^T{Q}^{T}QR=R^{T}R.$ Plug into $X^{T}X\theta =X^{T}y$: $R^{T}R\theta =R^T{Q}^{T}y$. Cancel the invertible $R^T$ from the left: $\boxed{R\theta =Q^{T}y}.$ Because $R$ is triangular you solve by back-substitution — no inverse, and it is numerically far kinder (no squaring of the condition number). See QR Decomposition and Pseudoinverse. Numeric check: for the 2.1 data a QR factorisation gives $Q^{T}y$ and an upper-triangular $R$ whose back-substitution yields $\theta =(4/3,1)$ — identical to the direct-inverse answer, as it must (both solve the same linear system). ✓

Here $X=\left[\begin{array}{cc}1& 2\end{array}\right]$ is $1\times 2$: fewer rows than columns ($m<n+1$). Now $X^{T}X$ is $2\times 2$ but singular; instead $X{X}^T$ (a $1\times 1$ number) is invertible. The correct Moore–Penrose pseudoinverse is the right form: $\theta =X^T(X{X}^T{)}^{-1}y.$ Compute $X{X}^T=1^2+2^2=5$, so $(X{X}^T{)}^{-1}=\frac{1}{5}$, and $y=5$: $\theta =\left[\begin{array}{c}1\\ 2\end{array}\right]\cdot \frac{1}{5}\cdot 5=\left[\begin{array}{c}1\\ 2\end{array}\right].$ Check: $X\theta =1\cdot 1+2\cdot 2=5=y$ ✓, and among the infinitely many $\theta$ that hit the point, this one has the smallest $\Vert \theta \Vert$ — the minimum-norm solution the pseudoinverse always picks.

Exercise 2.1 fitted line ::: $\hat{y}=\frac{4}{3}+x$ Why is $X^{T}X$ always square ::: it is $(n+1)\times (n+1)$, so we can ask if it inverts Condition for $(X^{T}X{)}^{-1}$ to exist ::: $X$ has full column rank (independent columns) Ridge normal equation ::: $\theta =(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$ QR-reduced system ::: $R\theta =Q^{T}y$, solved by back-substitution Wide-matrix ($m<n+1$) solution ::: $\theta =X^T(X{X}^T{)}^{-1}y$