Normal equation closed-form solution

2.2.5 · AI-ML › Linear & Logistic Regression

Overview

Normal equation ek analytical closed-form solution provide karta hai linear regression ke liye — yeh optimal parameters directly compute kar leta hai bina kisi iterative optimization ke. Gradient descent ke unlike, yeh $\mathbf{\theta }$ ko ek hi step mein solve karta hai matrix calculus ka use karke.

Ise aise socho jaise ek valley mein sabse neeche ka point dhundhna ho: bahut saare chhote-chhote steps neeche ki taraf lene ki jagah (gradient descent), hum calculus use karke seedha ek hi baar mein bottom pe jump karte hain.

Derivation (First Principles Se)

Step 1: Cost Function Set Up Karo

Linear regression mein $m$ training examples aur $n$ features ke saath:

Cost function (Mean Squared Error) hai:

$\frac{1}{2m}$ kyun? $\frac{1}{2}$ square ke derivative ke saath cancel ho jaata hai (calculus cleaner banta hai), aur $m$ alag-alag dataset sizes ke across normalize karta hai.

Step 2: Matrix Notation Use Karke Vectorize Karo

Design matrix $\mathbf{X}$ construct karte hain (dimensions: $m\times (n+1)$):

1's ka column kyun? Yeh $x_0=1$ feature hai jo ${\theta }_0$ (intercept/bias term) ko multiply karta hai.

Parameter vector $\mathbf{\theta }\in {\mathbb{R}}^{(n+1)}$ aur target vector $\mathbf{y}\in {\mathbb{R}}^m$:

Ab ek hi shot mein saari predictions: $\mathbf{X}\mathbf{\theta }$ $m$ predictions ka vector deta hai.

Cost function ban jaata hai:

Yeh form kyun? Squared error sum $\sum (h-y{)}^2$ exactly error vector ka khud ke saath dot product hai: ${\mathbf{e}}^T\mathbf{e}$.

Step 3: Gradient Lo aur Zero Set Karo

$J$ minimize karne ke liye, humein ${\nabla }_{\mathbf{\theta }}J=0$ chahiye.

Quadratic expand karne par:

Yeh expansion kyun? Hum $(a-b{)}^T(a-b)=a^{T}a-2a^{T}b+b^{T}b$ use karte hain jahan $a=\mathbf{X}\mathbf{\theta }$ aur $b=\mathbf{y}$ hai.

$\mathbf{\theta }$ ke saath gradient lete hain (matrix calculus rules use karke):

Yeh terms kyun?

• ${\nabla }_{\mathbf{\theta }}({\mathbf{\theta }}^T\mathbf{A}\mathbf{\theta })=2\mathbf{A}\mathbf{\theta }$ jab $\mathbf{A}$ symmetric ho
• ${\nabla }_{\mathbf{\theta }}({\mathbf{\theta }}^T\mathbf{b})=\mathbf{b}$
• Constants vanish ho jaate hain

Gradient ko zero set karne par:

Step 4: $\mathbf{\theta }$ Ke Liye Solve Karo

Ise "normal" kyun kehte hain? Linear algebra mein, "normal" ka matlab perpendicular hota hai. Optimum par, residual vector $(\mathbf{X}\mathbf{\theta }-\mathbf{y})$, $\mathbf{X}$ ke column space ke orthogonal (normal) hota hai. Yeh least squares solution hai.

Pseudoinverse ke baare mein important caveat: Jab $\mathbf{X}$ ka full column rank ho (yani ${\mathbf{X}}^T\mathbf{X}$ invertible ho), tab matrix $({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T$ Moore-Penrose pseudoinverse ${\mathbf{X}}^{+}$ ke barabar hoti hai, jo unique least squares solution deti hai. Jab $\mathbf{X}$ rank-deficient ho (singular ${\mathbf{X}}^T\mathbf{X}$), tab yeh formula kaam nahi karta, aur pseudoinverse ko kisi zyada general method se compute karna padta hai jaise SVD (Singular Value Decomposition). Us case mein infinitely many least squares solutions hote hain, aur ${\mathbf{X}}^{+}$ minimum norm wala return karta hai.

Worked Examples

Step 1: $\mathbf{X}$ aur $\mathbf{y}$ construct karo

Yeh structure kyun? Pehla column ${\theta }_0$ ke liye saare 1's hai, doosra column $x$ values hai.

Step 2: ${\mathbf{X}}^T\mathbf{X}$ compute karo

Yeh multiplication kyun? Har element $(i,j)$, ${\mathbf{X}}^T$ ke row $i$ aur $\mathbf{X}$ ke column $j$ ka dot product hai.

Step 3: ${\mathbf{X}}^T\mathbf{y}$ compute karo

Step 4: ${\mathbf{X}}^T\mathbf{X}$ invert karo

2×2 matrix $\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$ ke liye, inverse hai $\frac{1}{ad-bc}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$.

Determinant kyun compute karte hain? Yeh $3(14)-6(6)=42-36=6$ hai, jo ensure karta hai ki matrix invertible hai.

Step 5: $\mathbf{\theta }$ compute karo

Result: ${\theta }_0=2/3\approx 0.67$, ${\theta }_1=3/2=1.5$

Fitted line hai $y=0.67+1.5x$.

Step 1: Design matrix

Teen columns kyun? Column 0, ${\theta }_0$ ke liye hai; column 1, ${\theta }_1$ (feature $x_1$) ke liye; column 2, ${\theta }_2$ (feature $x_2$) ke liye.

Step 2: ${\mathbf{X}}^T\mathbf{X}$

Step 3: ${\mathbf{X}}^T\mathbf{y}$

Yeh numbers kyun? Row 1: $7+10+13=30$. Row 2: $1(7)+2(10)+3(13)=7+20+39=66$. Row 3: $3(7)+4(10)+5(13)=21+40+65=126$.

Step 4: RUKO — pehle invertibility check karo!

Feature columns ko dhyan se dekho: notice karo ki $x_2=x_1+2$ har row ke liye hai. Iska matlab hai ki $\mathbf{X}$ ka column 2, column 1 plus $2\times$ (1's ka column) ke barabar hai:

Columns linearly dependent hain, isliye $\mathbf{X}$ rank-deficient hai ($\text{rank}=2<3$). Isliye ${\mathbf{X}}^T\mathbf{X}$ singular hai — uska determinant $0$ hai aur woh invert nahi ho sakta. Normal equation ka plain formula yahaan apply nahi hota.

Yeh matter kyun karta hai: Kyunki features redundant hain, koi unique $\mathbf{\theta }$ nahi hai. Infinitely many exact solutions hain.

Step 5: Sahi tarike se solve karo. Relationship exactly linear hai ($y=2+2x_1+x_2$ ek valid fit hai), isliye ek perfect (zero-error) fit exist karta hai. For example:

Lekin kyunki $x_2=x_1+2$ hai, hum parameters ke beech weight trade kar sakte hain. Ek aur exact solution:

ruko — constraint ko honest rakhte hain. Koi bhi $\mathbf{\theta }=({\theta }_0,{\theta }_1,{\theta }_2)$ jo ${\theta }_0+3{\theta }_1+\text{(consistent shift)}$ satisfy kare aur targets reproduce kare, woh kaam karta hai. Ise saaf dekhne ka tarika: model mein $x_2=x_1+2$ substitute karo:

Sirf combinations $({\theta }_0+2{\theta }_2)$ aur $({\theta }_1+{\theta }_2)$ determine hote hain; individual values free hain. Data require karta hai $({\theta }_0+2{\theta }_2)=4$ aur $({\theta }_1+{\theta }_2)=3$ ($y=4+3x_1$ se match karte hue), jo infinitely many $\mathbf{\theta }$ deta hai.

Sahi tool: SVD-based pseudoinverse (${\mathbf{X}}^{+}$) use karo, jo in infinitely many mein se minimum-norm solution return karta hai, ya redundant feature $x_2$ hata do aur ek well-posed 2-parameter problem solve karo.

Sabak: ${\mathbf{X}}^T\mathbf{X}$ ko blindly invert karne se pehle hamesha $\mathbf{X}$ ka rank check karo.

Kab Use Karein (aur Kab Nahi)

Normal equation kab use karein:

• $n\le 10,000$ features (matrix inversion tractable hai)
• Small to medium datasets ($m<100,000$)
• Hyperparameters tune kiye bina exact solution chahiye
• Regularization nahi chahiye

Gradient descent kab use karein:

• $n>10,000$ (e.g., image features, text features)
• Bahut bada $m$ (big data scenarios)
• Online learning (data streams mein aata hai)
• Regularization chahiye (Lasso/Ridge) ya doosre constraints

Galti: Normal equation apply karna jab ${\mathbf{X}}^T\mathbf{X}$ singular (non-invertible) ho — exactly wahi jo Example 2 mein hota hai.

Sahi kyun lagta hai: Formula simple lagta hai — bas apna data plug in karo!

Kya galat hota hai:

• Jab $n\ge m$ (examples se zyada features): system under-determined hota hai
• Jab features linearly dependent hain (multicollinearity): $\text{rank}(\mathbf{X})<n+1$
• Example: "price in dollars" aur "price in cents" dono ko alag features ki tarah include karna

Fix:

1. Redundant features hata do (correlation matrix / rank check karo)
2. Regularization use karo (Ridge regression $\lambda \mathbf{I}$ add karta hai taaki ${\mathbf{X}}^T\mathbf{X}+\lambda \mathbf{I}$ invertible ban sake)
3. SVD-based pseudoinverse use karo (numpy ka pinv ya lstsq singular matrices ko gracefully handle karta hai aur minimum-norm solution return karta hai)
4. Zyada data collect karo agar $m<n$ ho

Galti: Feature normalization ke bina normal equation compute karna.

Sahi kyun lagta hai: Normal equation analytical hai — mathematically scaling matter nahi karni chahiye.

Asal mein kya hota hai:

• Matrix inversion mein numerical instability jab features ke scales bahut alag-alag hoon
• ${\mathbf{X}}^T\mathbf{X}$ ill-conditioned ho jaata hai (chhoti si change bahut badi errors cause karti hai)
• Example: feature 1 "age" hai (20-80), feature 2 "income" hai (20,000-200,000)

Fix: Features standardize karo: $x_j:=\frac{x_j-{\mu }_j}{{\sigma }_j}$ normal equation apply karne se pehle.

Implementation Considerations

$({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ explicitly compute karne ki jagah, use karo:

1. QR decomposition: $\mathbf{X}=\mathbf{QR}$, phir $\mathbf{R}\mathbf{\theta }={\mathbf{Q}}^T\mathbf{y}$ solve karo
2. SVD (Singular Value Decomposition): Near-singular aur rank-deficient matrices ko robustly handle karta hai (aur true pseudoinverse define karta hai)
3. Cholesky decomposition: Positive definite ${\mathbf{X}}^T\mathbf{X}$ ke liye faster hai

Kyun? Direct matrix inversion numerically unstable aur computationally expensive hai. Yeh methods inversion avoid karte hue same system solve karte hain.

import numpy as np
 
# Bad: explicit inversion (fails if X^T X is singular)
theta_bad = np.linalg.inv(X.T @ X) @ X.T @ y
 
# Good: use solve (uses LU decomposition internally)
theta_good = np.linalg.solve(X.T @ X, X.T @ y)
 
# Best: use lstsq (uses SVD, handles singular/rank-deficient matrices)
theta_best = np.linalg.lstsq(X, y, rcond=None)[0]

Socho tum ek graph par kuch points ke through sabse acchi straight line draw karne ki koshish kar rahe ho. Tum ek line guess kar sakte ho, measure kar sakte ho ki har point usase kitna door hai, thoda adjust karo, aur yeh karte raho jab tak improve nahi kar sakte (yahi gradient descent hai — bahut saare chhote-chhote adjustments).

Lekin ek clever shortcut hai! Math use karke, tum koi bhi guess kiye bina ek hi baar mein PERFECT line calculate kar sakte ho. Yeh aise hai jaise ek magic formula ho jo EK SAATH saare points dekhe aur exactly figure out kare ki line kahan honi chahiye.

"Normal equation" wahi magic formula hai. Tum apne saare data points ko ek special grid (matrix) mein organize karte ho, in grids ke saath kuch multiply aur divide karte ho, aur answer nikal aata hai — exactly best line!

Pakda kya hai? Yeh magic formula bahut slow ho jaata hai jab tumhare paas BAHUT ZYADA data ya BAHUT SAARI alag-alag measurements (features) hon. Chhote problems ke liye, yeh sabse fast tarika hai. Bahut bade problems ke liye, "guess-and-adjust" method better hai. Aur dhyan rakho: agar tumhari do measurements secretly ek hi cheez hain disguise mein (jaise height inches mein AUR centimeters mein measure karna), toh magic formula confuse ho jaata hai aur ek answer nahi de sakta — infinitely many hain! Pehle duplicate hata do.

"The Transpose Times, Inverse Times, Transpose Y"

$\mathbf{\theta }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$

Ya socho: "X-Transpose-X inverted hota hai, phir X-Transpose-y inserted hoti hai"

Visual: $(XtX{)}^{-1}\cdot Xt\cdot y$ → "sandwiched inverse" pattern.

Connections

• Linear Regression Fundamentals — woh problem jise yeh solve karta hai
• Gradient Descent — iterative alternative
• Ridge Regression — non-invertibility handle karne ke liye $\lambda \mathbf{I}$ add karta hai
• Moore-Penrose Pseudoinverse — singular matrices ke liye generalized inverse (SVD ke zariye)
• QR Decomposition — least squares solve karne ka numerically stable tarika
• Feature Scaling — numerical issues avoid karne ke liye preprocessing
• Polynomial Regression — transformed features ke saath bhi normal equation use karta hai
• Underdetermined vs Overdetermined Systems — kab unique solutions exist karte hain

#flashcards/

Concept Map