Visual walkthrough — Linear regression — normal equation, gradient descent derivation

5.6.1 · D2 · Coding › Machine Learning (Aerospace Applications) › Linear regression — normal equation, gradient descent deriva

Yeh page normal equation ko ek picture ek time pe rebuild karta hai, dots ki ek scatter se shuru karke ek single formula tak pahunchta hai:

$${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}.$$

Yahan har symbol use hone se pehle earn kiya jaata hai. Agar aapne kabhi matrix, dot product, ya derivative nahi dekha, toh line one se shuru karo — hum sab kuch build karte hain.

---

Step 1 — Dots aur woh line jo hum dhundh rahe hain

KYA. Humein measurements di gayi hain. Har measurement ek pair hai: ek input $x_i$ (maan lo, altitude) aur ek output $y_i$ (maan lo, fuel-burn rate). Chhota $i$ sirf ek naam-tag hai: $i=1$ pehla dot hai, $i=2$ doosra, aur aise $i=n$ tak (total $n$ dots hain).

Hum ek line chahte hain

$$\hat{y}=wx+b.$$

• $\hat{y}$ (padho "y-hat") line ki prediction hai — woh height jo line input $x$ pe claim karti hai.
• $w$ slope hai: line kitni steeply utha karti hai. $x$ ko 1 badlao, $\hat{y}$ $w$ se badlega.
• $b$ bias (ya intercept) hai: line ki height jahan $x=0$ ho.

LINE kyun? Kyunki yeh sabse simple honest guess hai: constant slope, koi curves nahi. Isse mushkil sab kuch iske upar build hota hai.

PICTURE. Blue mein dots, ek candidate line yellow mein. Har dot ke liye, dot aur line ke beech ka vertical red gap error hai — wahan line kitni galat hai.

---

Step 2 — Total galti measure karna: hum square kyun karte hain

KYA. Dot $i$ ke liye error hai $e_i=y_i-{\hat{y}}_i$ (true height minus predicted height). Hum saare errors jod lete hain — lekin squared:

$$J(w,b)=\frac{1}{2n}\sum _{i=1}^n\underset{\text{ek red gap}}{\underbrace{(y_i-{\hat{y}}_i)}}{}^2.$$

Symbols padhna:

• ${\sum }_{i=1}^n$ ka matlab hai "har dot ke liye $1$ se $n$ tak ye add karo".
• $(y_i-{\hat{y}}_i{)}^2$ ek red gap hai, squared — hamesha positive.
• $\frac{1}{2n}$ ek tidy-up factor hai: $n$ se divide karne se yeh ek average ban jaata hai, aur $\frac{1}{2}$ ek $2$ cancel karega jo baad mein differentiate karne pe aata hai. Yeh sirf minimum ki value badalta hai, minimum kahan baith hai nahi.
• $J$ total badness score hai. Chhota $J$ = behtar line.

SQUARE kyun, seedha add kyun nahi? Do reasons hain, dono figure mein dikhaye. (1) Line ke upar ka dot positive gap rakhta hai, neeche wala negative gap — agar hum unhe raw jodein, woh cancel ho jaenge aur ek buri line zero score kar sakti thi. Squaring har gap ko positive banati hai. (2) Squared curve smooth hai (ek parabola), toh calculus — jise hर jagah slopes chahiye — cleanly kaam karta hai.

PICTURE. Left: raw gaps cancel ho rahe hain (bura). Right: har gap ek red square mein badal raha hai jiska area penalty hai; bade gaps chhote walon se bahut zyada punish hote hain.

---

Step 3 — Saare dots ko ek matrix mein pack karna

KYA. $\sum$ baar baar likhna clumsy hai. Hum data ko ek matrix $\mathbf{X}$ aur ek vector $\mathbf{y}$ mein stack karte hain.

• Ek vector numbers ka ek column hai, e.g. $\mathbf{y}=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$ — har row pe ek target.
• Ek matrix numbers ki ek grid hai. Hum $\mathbf{X}$ ko har dot ke liye ek row ke saath banate hain. Bias $b$ ko bhi capture karne ke liye, hum saamne $1$s ka ek column chipka dete hain:

$$\mathbf{X}=\left[\begin{array}{cc}1& x_1\\ 1& x_2\\ ⋮& ⋮\\ 1& x_n\end{array}\right],\mathbf{w}=\left[\begin{array}{c}b\\ w\end{array}\right].$$

Ab $\mathbf{Xw}$ — matrix times vector — ek saath predictions ka poora column hai. Product ki row $i$ hai $1\cdot b+x_i\cdot w=b+w{x}_i={\hat{y}}_i$. $1$s ka column hi hai jo $b$ ko ek real column banata hai taaki woh multiplication mein saath aaye.

KYUN. Taaki puri cost ek clean object ban jaaye:

$$J(\mathbf{w})=\frac{1}{2n}\Vert \mathbf{y}-\mathbf{Xw}{\Vert }^2.$$

Yahan $\Vert \mathbf{v}{\Vert }^2$ (squared norm) ka matlab hai "$\mathbf{v}$ ki entries ke squares jodo" — exactly hamara sum of squared gaps, ab ek symbol mein.

PICTURE. Left pe dot-by-dot table boxed grid $\mathbf{X}$ mein collapse ho raha hai, $1$s ka column highlighted, arrow $\mathbf{Xw}=\hat{\mathbf{y}}$ ki taraf.

---

Step 4 — Poori geometry ek flat sheet mein rehti hai

KYA. Yeh picture hai jo formula ko inevitable banati hai. $\mathbf{y}$ ko space mein ek single arrow socho (har dot ke liye ek axis — $n$ axes). Har possible line jo hum draw kar sakte hain koi $\mathbf{Xw}$ deti hai, ek aur arrow. Jab hum dials $b$ aur $w$ ghoomte hain, $\mathbf{Xw}$ ki tip origin se ek flat sheet sweep karti hai: $\mathbf{X}$ ki column space ($\mathbf{X}$ ke columns ke saare combinations).

ISKA MATLAB KYUN. Hamara target arrow $\mathbf{y}$ almost kabhi us sheet pe nahi hota (real data perfectly fit nahi hota line mein). Toh "best line" = "sheet pe woh point jo $\mathbf{y}$ ke sabse paas ho". Is space mein distance exactly $\Vert \mathbf{y}-\mathbf{Xw}\Vert$ hai — hamara error. Squared error minimize karna = sheet pe closest point dhundhna.

PICTURE. Green sheet column space hai. $\mathbf{y}$ (blue) uske upar float kar raha hai. Candidate predictions $\mathbf{Xw}$ sheet pe rehte hain.

---

Step 5 — Closest point = perpendicular giraa do

KYA. Bahar ke kisi point se flat sheet pe closest point seedha neeche giraakar milta hai — sheet ke perpendicular. Us perpendicular ke paaon ko $\mathbf{X}{\mathbf{w}}^{\ast }$ bolo. Bacha hua arrow,

$$\mathbf{r}=\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast },$$

residual (red), sheet ke perpendicular hona chahiye.

KYUN. Agar residual sheet ke saath thoda bhi jhuk raha ho, toh hum us direction mein thoda slide karke closer aa sakte the — matlab hum abhi minimum pe nahi hote. True minimum pe residual seedha bahar ki taraf point karta hai. Yeh geometrically "derivative bottom pe zero hai" ka twin hai.

Poori sheet ke perpendicular hone ka matlab hai $\mathbf{X}$ ke har column ke perpendicular. Zero dot product perpendicular matlab hai, toh:

$${\mathbf{X}}^T(\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast })=0.$$

${\mathbf{X}}^T\mathbf{r}$ ki har entry $\mathbf{X}$ ka ek column $\mathbf{r}$ ke saath dotted hai; sab ko zero set karna kehta hai $\mathbf{r}\perp$ har column.

PICTURE. Red residual green sheet se right-angle mark pe milta hai; $\mathbf{X}$ ke yellow columns sheet mein flat hain, har ek residual ke $90^{\circ }$ pe.

---

Step 6 — Calculus se same answer (slope-is-zero view)

KYA. Step 5 ko algebra se re-derive karte hain, taaki dono pictures agree karein. Step 3 ke dot-product facts use karke cost expand karo:

$$J(\mathbf{w})=\frac{1}{2n}(\underset{\text{const}}{\underbrace{{\mathbf{y}}^T\mathbf{y}}}-\underset{\text{linear in }\mathbf{w}}{\underbrace{2{\mathbf{w}}^T{\mathbf{X}}^T\mathbf{y}}}+\underset{\text{quadratic in }\mathbf{w}}{\underbrace{{\mathbf{w}}^T{\mathbf{X}}^T\mathbf{Xw}}}).$$

KYUN. Dials $\mathbf{w}$ ka function ke roop mein, yeh ek bowl hai (ek paraboloid) — quadratic term guarantee karta hai ki yeh upar curve karta hai. Ek bowl ka exactly ek lowest point hota hai, aur bottom pe uski slope har direction mein zero hoti hai. Har-direction-mein-slope gradient ${\nabla }_{\mathbf{w}}J$ hai: ek vector jiske entries partial derivatives hain (har dial ko nudge karne pe $J$ ki sensitivity). Ise $0$ set karo:

$${\nabla }_{\mathbf{w}}J=\frac{1}{n}({\mathbf{X}}^T\mathbf{X}\mathbf{w}-{\mathbf{X}}^T\mathbf{y})=0⟹{\mathbf{X}}^T\mathbf{X}\mathbf{w}={\mathbf{X}}^T\mathbf{y}.$$

Yeh normal equation Step 5 ke identical hai (${\mathbf{X}}^T(\mathbf{y}-\mathbf{Xw})=0$ expand karo). Geometry aur calculus same line pe aakar milte hain.

PICTURE. $(b,w)$ plane ke upar bowl-shaped cost surface; ek ball single bottom ki taraf roll karti hai jahan tangent plane flat hai.

---

Step 7 — Winning dials ke liye solve karo

KYA. ${\mathbf{X}}^T\mathbf{X}\mathbf{w}={\mathbf{X}}^T\mathbf{y}$ se, left pe matrix ko uske inverse $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ se multiply karke undo karo (matrix version of dividing):

Worked check (parent ka Example 1). Data $(1,2),(2,4),(3,5)$:

$${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right],{\mathbf{X}}^T\mathbf{y}=\left[\begin{array}{c}11\\ 25\end{array}\right],{\mathbf{w}}^{\ast }=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]\left[\begin{array}{c}11\\ 25\end{array}\right]=\left[\begin{array}{c}0.667\\ 1.5\end{array}\right].$$

Toh $b=\frac{2}{3}\approx 0.667$, $w=1.5$: fitted line hai $\hat{y}=1.5x+0.667$.

PICTURE. Teen dots solved yellow line ke saath, residuals dikhaye, aur fitted numbers label kiye.

---

Step 8 — Degenerate case: jab inverse mar jaata hai

KYA. Upar ka sab kuch $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ ke exist hone pe depend karta tha. Yeh fail hota hai jab $\mathbf{X}$ ke do columns same information carry karte hain — e.g. altitude metres mein aur altitude feet mein. Tab green sheet squash ho jaati hai: infinitely many lines best ke liye tie karti hain, aur ${\mathbf{X}}^T\mathbf{X}$ singular ho jaata hai (koi inverse nahi).

KYUN TOOT TA HAI. Geometrically columns parallel hain, toh "sheet" actually ek patla slab hai — perpendicular ka paaon unique nahi hai. Algebraically $\det ({\mathbf{X}}^T\mathbf{X})=0$, aur aap divide nahi kar sakte.

Fix. Moore–Penrose pseudoinverse ${\mathbf{X}}^{+}$ use karo, jo sabse chhota valid $\mathbf{w}$ choose karta hai, ya ek $\lambda$ nudge add karo (dekho ridge regression): $({\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I}{)}^{-1}$, jo $\lambda >0$ ke liye hamesha invertible hota hai. Saath hi, bahut alag feature scales numerically ${\mathbf{X}}^T\mathbf{X}$ ko almost singular banate hain — Feature Scaling se thik hota hai.

PICTURE. Left: healthy full sheet, unique foot. Right: collapsed slab, tied feet ki ek poori line — ambiguity.

---

Ek-picture summary

Dots → squared gaps → column-space sheet → perpendicular giraa do → normal equation → solved line. Ek figure, poora safar.

Recall Feynman retelling — ise ek story ki tarah bolo

Humne kuch dots scatter kiye aur unse guzarne wali sabse seedhi, sabse fair line chahte the. "Fair" ka matlab tha: har dot pe kitna off hai yeh jodo, lekin har miss ko square karo taaki ups aur downs chhup ke cancel na ho sakein aur math smooth rahe. Humne saare dots ko ek grid $\mathbf{X}$ mein pack kiya ($1$s ke ek column ke saath taaki line ki height $b$ free mein saath aa jaaye) aur saare answers ko ek column $\mathbf{y}$ mein. Phir aaya woh khoobsurat trick: $\mathbf{y}$ ko ek arrow socho, aur har possible line ko ek flat sheet pe padi ek arrow. Best line $\mathbf{y}$ ka us sheet pe shadow hai — tum seedhe neeche giraate ho, aur bacha hua error sheet ke bilkul perpendicular point karta hai. "Har column ke perpendicular" symbols mein likha jaata hai ${\mathbf{X}}^T(\mathbf{y}-\mathbf{Xw})=0$, jo rearrange hoke banta hai ${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$. Calculus agree karta hai: cost ek bowl hai, aur bowl ka bottom wahan hota hai jahan har slope zero ho — same equation. Ek hi catch hai jab do columns same baat kehte hain; tab sheet collapse ho jaati hai, inverse mar jaata hai, aur hum pseudoinverse ya ek tiny ridge nudge pe lean karte hain. Hamare teen dots ke liye isne $\hat{y}=1.5x+0.667$ nikala, bina kisi guessing ke.

Recall Quick self-test

Hum errors ko raw add karne ki jagah square kyun karte hain? ::: Taaki positive aur negative gaps cancel na ho sakein, aur taaki cost ek smooth parabola/bowl ho jisme har jagah derivatives hon. ${\mathbf{X}}^T(\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast })=0$ geometrically kya matlab hai? ::: Residual (error arrow) $\mathbf{X}$ ke har column ke, yaani poori column-space sheet ke, perpendicular hai. $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ kab exist nahi karta? ::: Jab $\mathbf{X}$ ke columns redundant hon (multicollinearity), ${\mathbf{X}}^T\mathbf{X}$ ko singular bana dete hain. Data $(1,2),(2,4),(3,5)$ ke liye, normal equation kaunsi line deta hai? ::: $\hat{y}=1.5x+0.667$.