Linear regression — normal equation, gradient descent derivation: Question bank

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

Yeh bank un galat-fahmiyon ko dhundta hai jo real bugs banati hain: gradient mein sign errors, yeh sochna ki normal equation hamesha kaam karti hai, aur $α$ kya karta hai yeh confuse karna. Har item ek one-line reveal hai — answer cover karo, pehle guess karo, phir check karo. Har answer sirf verdict nahi balki reasoning explain karta hai.

Parent: Linear Regression (parent topic).

True ya false — justify karo

Errors ko square karna sirf ek convenience hai; hum absolute value use kar sakte hain aur same line mil sakti hai.

False. Squared error har jagah differentiable hai aur ek smooth quadratic bowl deta hai jiska unique minimum hota hai; absolute error mein zero par ek kink hota hai aur generally ek alag line deta hai (median-like fit), same nahi.

Cost

J (w) = \frac{1}{2 n} ∥ y - Xw ∥^{2}

convex hai, isliye koi bhi local minimum global minimum hai.

True.

J

ek quadratic bowl hai (iska Hessian

\frac{1}{n} X^{T} X

positive semi-definite hai), isliye isme koi alag local minima nahi hain jisme trap ho sako — dekho Convex Optimization.

Normal equation kisi bhi dataset par valid answer deta hai.

False. Iske liye

X^{T} X

invertible hona chahiye; perfectly correlated features (multicollinearity) ke saath ya features se kam samples hone par,

X^{T} X

singular ho jaata hai aur plain inverse exist nahi karta — tumhe Matrix Pseudoinverse chahiye.

Gradient descent aur normal equation same data par alag answers par converge karte hain.

False. Dono same convex

J

minimize karte hain, isliye (healthy

α

aur enough iterations ke saath) dono same

w^{*}

par land karte hain. Dono mein fark yeh hai ki kaise pahunchte hain, kahan nahi.

Cost mein factor

\frac{1}{2 n}

change kar deta hai ki kaunsa

w

optimal hai.

False.

J

ko kisi bhi positive constant se multiply karna pura bowl vertically scale karta hai lekin iska lowest point move nahi hota; minimizing

w

unchanged rehta hai. Yeh constant sirf gradient ko rescale karta hai (aur effectively

α

ko rescale karta hai).

Optimum par, error vector

y - X w^{*}

har column of

X

ke perpendicular hota hai.

True. Normal equation

X^{T} (y - X w^{*}) = 0

literally kehti hai ki residual ka har feature column ke saath zero dot product hai — yahi Least Squares Estimation ki geometric heart hai.

Bada learning rate

α

hamesha gradient descent ko minimum tak faster pahunchata hai.

False. Bahut bada

α

har step mein minimum ko overshoot karta hai, isliye cost oscillate ya diverge hoti hai. Ek sweet spot hota hai; usse aage, bada slow ya fatal hota hai.

Stochastic gradient descent (SGD) exact same path follow karta hai jaise full-batch gradient descent, bas faster.

False. SGD har step mein ek sample ka noisy gradient use karta hai, isliye iska path true descent direction ke around zig-zag karta hai; yeh per step faster hai lekin exactly settle hone ki jagah minimum ke paas jitter karta rehta hai.

Error dhundo

Ek student update aisa likhta hai

w_{t + 1} = w_{t} + \frac{α}{n} X^{T} (X w_{t} - y)

Sign galat hai — yeh minus hona chahiye. Gradient add karna uphill chalta hai, har step cost badhata hai; descend karne ke liye tumhe gradient ke against step lena hoga.

Koi gradient ko

\frac{1}{n} X^{T} (y - Xw)

compute karta hai aur phir update mein isse subtract karta hai.

Yahan do galtiyan cancel nahi hoti — yeh residual

(y - Xw)

hai, true error ka negative, isliye unka "gradient" pehle se wrong sign mein hai; isse subtract karna uphill chadata hai. Correct gradient

(Xw - y)

use karta hai.

Ek student kehta hai "

X^{T} X

d \times d

hai, isliye ise invert karne ki cost

O (n^{3})

hai."

Cost

O (d^{3})

hai,

O (n^{3})

nahi — jo matrix invert ho rahi hai uska size feature count

d

ke equal hai, samples ki number

n

se independent.

Code raw features fit karta hai jahan altitude 10,000s mein hai aur Mach number 1 ke paas hai, gradient descent use karte hue, aur yeh "converge nahi ho raha."

Features wildly different scales par hain, isliye cost bowl ek stretched ravine hai aur ek single

α

dono directions ke liye suit nahi kar sakta. Pehle Feature Scaling apply karo; normal equation isse immune hoti kyunki yeh ek hi shot mein solve karti hai.

Ek student pseudoinverse solution likhta hai lekin

X

mein ones ka column add karna bhool jaata hai.

Ones column ke bina koi bias term nahi hota, fitted line ko origin se guzarne par force karta hai. Koi bhi data jiska best line nonzero intercept wali ho, usski fitting kharaab hogi.

"Main SGD ka update

w_{t + 1} = w_{t} - α (x_{i}^{T} w_{t} - y_{i}) x_{i}

same

α

ke saath use karunga jo maine full-batch GD ke liye use kiya tha."

SGD gradients noisier hote hain aur typically chhota (often decaying)

α

chahiye; batch

α

reuse karna aksar SGD ko bounce karwata hai aur kabhi settle nahi hone deta.

Why questions

Hum gradient ke andar

X

ko transpose (

X^{T}

) kyun karte hain?

Kyunki gradient ek

d

-vector hona chahiye, har weight ke liye ek number;

X^{T}

n

-dimensional error vector ko feature space mein wapas map karta hai, har feature ka total error mein contribution sum karta hai.

Derivation mein

y^{T} Xw

w^{T} X^{T} y

ke equal kyun allow kiya jaata hai?

Dono

1 \times 1

scalars hain, aur ek scalar apne transpose ke barabar hota hai;

y^{T} Xw

ka transpose lena product ko reverse karke

w^{T} X^{T} y

deta hai, jo isliye same number hai.

Gradient ko zero set karna ek minimum kyun dhundta hai, maximum nahi?

Kyunki

J

ek convex bowl hai (positive semi-definite Hessian

\frac{1}{n} X^{T} X

), isliye iska ekmaatra stationary point har direction mein upar curve karta hai — minimum, kabhi maximum ya saddle nahi.

Jab

d

large ho (jaise aerospace sensor fusion mein thousands of features) toh normal equation ki jagah gradient descent kyun prefer karein?

Normal equation ka

O (d^{3})

matrix inversion prohibitively expensive ho jaata hai; har gradient step sirf

O (n d)

ka hota hai, jo high-dimensional problems ke liye iteration bahut sasta banata hai.

Regularization term (Ridge) add karna singular

X^{T} X

ko kyun rescue karta hai?

Ridge

λ I

add karta hai,

(X^{T} X + λ I)

deta hai jo

λ > 0

ke liye hamesha invertible hai; yeh weights ko bhi shrink karta hai overfitting rokne ke liye — dekho Regularization (Ridge, Lasso).

Geometric picture

X w^{*}

y

ka "projection" kyun kehti hai?

Xw

sirf

X

ke column space mein points tak pahunch sakta hai;

y

ke sabse kareeb wala aisa point us space par

y

se daali gayi perpendicular ka foot hai — exactly ek orthogonal projection.

Hum fixed number of iterations run karne ki jagah

∣ J_{t + 1} - J_{t} ∣ < ϵ

monitor kyun karte hain?

Ek flattening cost signal karta hai ki hum already bottom ke paas hain, isliye hum early stop kar sakte hain aur computation bacha sakte hain, instead of us region mein wastefully iterate karne ke jahan

w

barely change hota hai.

Edge cases

Agar sab data points pehle se ek line par exactly hain toh normal equation kya deta hai?

Woh line exactly return karta hai, aur residual

y - X w^{*}

zero vector hota hai — fit perfect hai cost

J = 0

ke saath.

Agar gradient descent mein

α = 0

set karo toh kya hota hai?

Update

w_{t + 1} = w_{t}

ban jaata hai, isliye weights kabhi move nahi karte; tum random initialization par hamesha ke liye stuck reh jaate ho.

Tumhare paas do identical feature columns hain (perfect duplication). Kya break hota hai aur kya kaam karta rehta hai?

X^{T} X

singular ho jaata hai isliye plain inverse fail karta hai, lekin pseudoinverse ya gradient descent phir bhi ek valid (though non-unique) minimizing

w

return karte hain — bahut saare weight combinations same predictions dete hain.

Jab exactly ek data point aur ek feature-plus-bias ho (

n = 1

d = 2

) toh fit kya hota hai?

System under-determined hai: infinitely many lines ek single point se guzarti hain, isliye

X^{T} X

singular hai aur koi unique solution nahi hai — pseudoinverse minimum-norm wala choose karta hai.

Agar har target value

y_{i}

same constant

c

ho, toh fitted model kaisa dikhta hai?

Optimal line flat hai: features par weight(s) zero ho jaate hain aur bias

c

ban jaata hai, isliye

\overset{y}{^} = c

har jagah zero residual ke saath.

Jab gradient descent iterations

\to \infty

hoon valid small

α

ke saath,

w_{t}

kis value ki taraf approach karta hai?

Yeh exact normal-equation solution

w^{*} = (X^{T} X)^{- 1} X^{T} y

par converge karta hai, kyunki dono same convex cost minimize karte hain.

Mini-batch gradient descent kya ban jaata hai jab batch size

b

full sample count

n

ke barabar ho?

Yeh ordinary full-batch gradient descent ban jaata hai — "batch" poora dataset hai, har step mein exact (non-noisy) gradient deta hai.

Recall Quick self-test

Is poore topic mein sabse common sign bug hai::: update $+$ ki jagah $-$ ke saath likhna, ya $(Xw - y)$ ki jagah $(y - Xw)$ use karna — dono uphill chadhte hain. Normal equation exactly tab fail hoti hai jab::: $X^{T} X$ singular ho (multicollinearity ya $n < d$ ). Feature scaling matter karta hai::: gradient descent ke liye (stretched ravines), normal equation ke liye nahi.