Exercises — Linear regression — normal equation, gradient descent derivation

Bias column ke saath $3+1=4$ columns hain.

• $\mathbf{X}$ ka shape hai $5\times 4$ (rows $=$ points, columns $=$ features$+$bias).
• ${\mathbf{X}}^T$ ka shape hai $4\times 5$, isliye ${\mathbf{X}}^T\mathbf{X}$ hai $(4\times 5)(5\times 4)=4\times 4$.
• ${\mathbf{X}}^T\mathbf{y}$ hai $(4\times 5)(5\times 1)=4\times 1$.
• $\mathbf{w}$ ek $4\times 4$ system solve karta hai isliye yeh $4\times 1$ hai.

Sanity check: $\mathbf{w}$ mein unknowns ki sankhya ($=4$) hamesha $\mathbf{X}$ ke columns ki sankhya ke barabar hoti hai.

(b). (a) absolute error hai — kinks ki wajah se $0$ par iski derivative undefined hoti hai, isliye calculus mushkil ho jaati hai. (c) squared nahi hai, isliye line ke upar aur neeche ke errors cancel ho jaate hain; tumhare paas huge errors ho sakte hain jo sum karke zero ho jaayein. (b) mein squaring har error ko positive banati hai aur ek smooth bowl deti hai jisme slide kiya ja sake.

$\mathbf{X}=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\end{array}\right],\mathbf{y}=\left[\begin{array}{c}1\\ 3\\ 3\end{array}\right]$ ${\mathbf{X}}^T\mathbf{X}$ ka top-left points count karta hai: $1+1+1=3$. Off-diagonal hai $\sum x_i=0+1+2=3$. Bottom-right hai $\sum x_i^2=0+1+4=5$. ${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 3\\ 3& 5\end{array}\right]$ ${\mathbf{X}}^T\mathbf{y}$: pehli entry $\sum y_i=1+3+3=7$; doosri $\sum x_i{y}_i=0\cdot 1+1\cdot 3+2\cdot 3=9$. ${\mathbf{X}}^T\mathbf{y}=\left[\begin{array}{c}7\\ 9\end{array}\right]$

Determinant: $3\cdot 5-3\cdot 3=15-9=6$. $({\mathbf{X}}^T\mathbf{X}{)}^{-1}=\frac{1}{6}\left[\begin{array}{cc}5& -3\\ -3& 3\end{array}\right]$ ${\mathbf{w}}^{\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}1.333\\ 1\end{array}\right]$ Toh $b=\frac{4}{3}\approx 1.333$, $w=1$. Line: $\hat{y}=x+1.333$.

Aankhon se check karo: $x=1$ par yeh $2.333$ predict karta hai (actual $3$), $x=2$ par $3.333$ predict karta hai (actual $3$) — errors balanced hain, jaise least squares demand karta hai.

${\mathbf{w}}_0$ ke saath predictions sab $0$ hain, isliye error $\mathbf{X}{\mathbf{w}}_0-\mathbf{y}=[-1,-3,-3{]}^T$. Gradient $\nabla J=\frac{1}{3}{\mathbf{X}}^T(\mathbf{X}{\mathbf{w}}_0-\mathbf{y})$:

• pehli entry $\frac{1}{3}(-1-3-3)=\frac{-7}{3}=-2.333$
• doosri entry $\frac{1}{3}(0\cdot (-1)+1\cdot (-3)+2\cdot (-3))=\frac{-9}{3}=-3$ ${\mathbf{w}}_1=\left[\begin{array}{c}0\\ 0\end{array}\right]-0.1\left[\begin{array}{c}-2.333\\ -3\end{array}\right]=\left[\begin{array}{c}0.2333\\ 0.3\end{array}\right]$

Normal equation hai ${\mathbf{X}}^T\mathbf{X}{\mathbf{w}}^{\ast }={\mathbf{X}}^T\mathbf{y}$. Rearrange karo: ${\mathbf{X}}^T\mathbf{y}-{\mathbf{X}}^T\mathbf{X}{\mathbf{w}}^{\ast }=0\Rightarrow {\mathbf{X}}^T(\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast })=0\Rightarrow {\mathbf{X}}^T\mathbf{r}=0.$ Matlab (figure dekho): $\mathbf{X}{\mathbf{w}}^{\ast }$, $\mathbf{X}$ ke columns se bane flat plane par $\mathbf{y}$ ka shadow (projection) hai. Bacha hua $\mathbf{r}$ us plane se seedha bahar point karta hai — possible mein se sabse chhota bacha hua. Koi bhi doosra $\mathbf{w}$ zyada lamba residual chhod deta hai.

Column 3 $=2\times$ column 2, isliye columns linearly dependent hain. Tab ${\mathbf{X}}^T\mathbf{X}$ singular hai (determinant $0$) aur $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ exist nahi karta — normal equation ke infinitely many solutions hain. Geometrically woh "plane" jo columns span karte hain ek lower dimension mein collapse ho jaata hai, isliye $\mathbf{y}$ ka projection well-defined hai lekin coordinates $\mathbf{w}$ jo usse reach karte hain unique nahi hain. Yeh multicollinearity hai. Fixes: ek redundant feature drop karo, ya Ridge add karo jo ${\mathbf{X}}^T\mathbf{X}$ ko ${\mathbf{X}}^T\mathbf{X}+\lambda I$ se replace karta hai ($\lambda >0$ ke liye hamesha invertible), ya Matrix Pseudoinverse use karo jo minimum-norm solution deta hai.

$J$ ki second derivative (Hessian) hai $\frac{1}{n}{\mathbf{X}}^T\mathbf{X}$. Kisi bhi nonzero direction $\mathbf{v}$ ke liye, ${\mathbf{v}}^T{\mathbf{X}}^T\mathbf{Xv}=\Vert \mathbf{Xv}{\Vert }^2\ge 0$, aur yeh $>0$ hota hai jab columns independent hon. Ek matrix jisme sab positive curvatures hon woh positive definite hai, isliye $J$ strictly convex hai — ek single bowl. Har downhill path same bottom tak pahunchta hai, isliye gradient descent yahan kisi fake local minimum mein stuck nahi ho sakta.

$\mathbf{X}=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right]$, $\mathbf{y}=[2,2,4{]}^T$. ${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right]$, det $=42-36=6$. ${\mathbf{X}}^T\mathbf{y}$: $\sum y_i=8$; $\sum x_i{y}_i=2+4+12=18$. ${\mathbf{w}}^{\ast }=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]\left[\begin{array}{c}8\\ 18\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}112-108\\ -48+54\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}4\\ 6\end{array}\right]=\left[\begin{array}{c}0.667\\ 1\end{array}\right]$ Toh $b=\frac{2}{3},w=1$. (ii) Kyunki $J$ strictly convex hai (L3.3) aur ${\mathbf{X}}^T\mathbf{X}$ invertible hai, gradient descent kaafi chhote $\alpha$ ke saath same unique minimum $[0.667,1{]}^T$ par converge karta hai. Dono methods agree karne chahiye — woh same equation solve karte hain, ek jump mein, ek walk karke.

Har direction mein curvature us feature ke $\sum x^2$ se set hoti hai. $1$ vs $10,000$ ranges ke saath bowl ek lamba patla canyon hai: chhote feature ke across steep, bade wale ke along almost flat. Ek single learning rate $\alpha$ itni chhoti honi chahiye ki steep wall ko overshoot na kare — isliye flat floor ke saath barely move karta hai. Result: zig-zagging, glacial convergence. Scaling (jaise mean subtract karo, std se divide karo) sab $\sum x^2$ ko comparable banata hai, canyon ko ek round bowl mein badal deta hai jahan ek $\alpha$ har direction mein kaam karta hai. Normal equation immune hai (koi $\alpha$ nahi), jo ek reason hai ki chhote $d$ ke liye yeh convenient hai.

Gradient lo aur zero set karo. Extra term $\lambda \mathbf{w}$ contribute karta hai: $\frac{1}{n}{\mathbf{X}}^T(\mathbf{Xw}-\mathbf{y})+\lambda \mathbf{w}=0.$ $n$ se multiply karo aur $\mathbf{w}$ group karo: $({\mathbf{X}}^T\mathbf{X}+n\lambda I)\mathbf{w}={\mathbf{X}}^T\mathbf{y}\Rightarrow {\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}+n\lambda I{)}^{-1}{\mathbf{X}}^T\mathbf{y}.$ Kyunki ${\mathbf{X}}^T\mathbf{X}$ ke eigenvalues $\ge 0$ hain, $n\lambda I$ ($\lambda >0$) add karne se har eigenvalue $n\lambda >0$ se upar shift ho jaata hai — koi bhi zero nahi ho sakta, isliye matrix invertible hai chahe L3.2 ki multicollinearity ho. Regularization (Ridge, Lasso) dekho.

Normal equation out hai: ${\mathbf{X}}^T\mathbf{X}$ ($50,000\times 50,000$) form karna aur invert karna $O(d^3)\approx 1.25\times 10^{14}$ operations plus $2.5\times 10^9$ memory entries cost karta hai — infeasible hai, aur yeh live stream ingest nahi kar sakta. Full batch GD har step mein $2,000,000$ rows touch karta hai — per iteration expensive hai. Sahi choice hai mini-batch / SGD: har step ek small batch use karta hai (jaise 256 rows), cost $O(bd)$ per step, aur yeh naturally real time mein stream consume karta hai. Trade-off: noisier steps, isliye decaying $\alpha$ use karo. Yeh exactly wahi setting hai Kalman Filtering aur online estimators ke behind, aur mini-batch GD Neural Networks ka workhorse hai same scaling reason ke liye.

$\mathbf{X}=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right]$, $\mathbf{y}=[1,2,2{]}^T$. ${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right]$ (det $6$). ${\mathbf{X}}^T\mathbf{y}$: $\sum y=5$, $\sum x_i{y}_i=1+4+6=11$. ${\mathbf{w}}^{\ast }=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]\left[\begin{array}{c}5\\ 11\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}70-66\\ -30+33\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}4\\ 3\end{array}\right]=\left[\begin{array}{c}0.667\\ 0.5\end{array}\right]$ (ii) Predictions $\hat{y}=0.5x+0.667$: $x=1,2,3$ par $1.167,1.667,2.167$ dete hain. Residuals $\mathbf{r}=\mathbf{y}-\hat{\mathbf{y}}=[-0.167,0.333,-0.167{]}^T$. $\Vert \mathbf{r}{\Vert }^2=0.0278+0.1111+0.0278=0.1667$. Cost $J=\frac{1}{2\cdot 3}(0.1667)=0.02778$. (iii) ${\mathbf{X}}^T\mathbf{r}$: pehli entry $-0.167+0.333-0.167=0$; doosri $-0.167+0.667-0.5=0$. ✓ Residual dono columns ke saath orthogonal hai, projection picture confirm ho gayi.

Convergence ke liye contraction factor ki magnitude $<1$ chahiye: $\left|1-\frac{\alpha }{n}\sum x_i^2\right|<1\Rightarrow 0<\frac{\alpha }{3}(14)<2\Rightarrow \alpha <\frac{6}{14}=\mathrm{0.4286.}$ Iske upar, $\alpha \approx 0.4286$ bina shrink hue oscillate karta hai, aur $\alpha >0.4286$ diverge karta hai — har step pehle se zyada overshoot karta hai. Safe rule: $\alpha <\frac{2n}{\sum x_i^2}$ (general mein, $\alpha <2/{\lambda }_{\max }$ Hessian ka).

Normal equation solution hai ::: ${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$ Gradient descent diverge karta hai jab $\alpha$ exceed kare ::: Hessian $\frac{1}{n}{\mathbf{X}}^T\mathbf{X}$ ka $2/{\lambda }_{\max }$ Ridge hamesha invertible rehta hai kyunki yeh add karta hai ::: $n\lambda I$, jo har eigenvalue ko zero se upar lift karta hai Optimum par residual hota hai ::: $\mathbf{X}$ ke har column ke saath orthogonal (${\mathbf{X}}^T\mathbf{r}=0$)