Linear regression — normal equation, gradient descent derivation

5.6.1 · Coding › Machine Learning (Aerospace Applications)

Linear regression best-fit line (ya hyperplane) dhundhta hai data ke through, sum of squared errors minimize karke. Aerospace mein, yeh trajectory prediction, sensor calibration, aur control system parameter identification ke liye use hota hai.

Why Linear Regression?

Problem Setup

Vectorized form: Data ko matrix $\mathbf{X}\in {\mathbb{R}}^{n\times d}$ mein stack karo (har row ${\mathbf{x}}_i^T$ hai), targets $\mathbf{y}\in {\mathbb{R}}^n$. Bias ko $\mathbf{w}$ mein absorb karo $\mathbf{X}$ mein 1s ka column add karke. Tab:

Method 1: Normal Equation (Closed-Form Solution)

Derivation from First Principles

Goal: $\mathbf{w}$ dhundho jo $J(\mathbf{w})$ minimize kare, calculus use karke.

Step 1: Cost function expand karo.

Yeh step kyun? Norm ko dot product mein convert karna taaki matrix derivative rules apply kar sakein.

Expand karo:

Kyunki ${\mathbf{y}}^T\mathbf{Xw}$ ek scalar hai, yeh apne transpose ke barabar hai: ${\mathbf{y}}^T\mathbf{Xw}={\mathbf{w}}^T{\mathbf{X}}^T\mathbf{y}$.

Step 2: $\mathbf{w}$ ke respect mein derivative lo aur zero set karo.

Yeh step kyun? Minimum par, gradient zero hota hai (kisi bhi direction mein slope nahi). Hum use karte hain:

• $\frac{\partial }{\partial \mathbf{w}}({\mathbf{a}}^T\mathbf{w})=\mathbf{a}$
• $\frac{\partial }{\partial \mathbf{w}}({\mathbf{w}}^T\mathbf{Aw})=2\mathbf{Aw}$ (symmetric $\mathbf{A}$ ke liye)

Gradient ko zero set karo:

Step 3: $\mathbf{w}$ ke liye solve karo.

Geometric intuition: $\mathbf{X}{\mathbf{w}}^{\ast }$, $\mathbf{y}$ ka orthogonal projection hai $\mathbf{X}$ ke column space par. Error vector $\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast }$, $\mathbf{X}$ ke sabhi columns ke perpendicular hai, isliye ${\mathbf{X}}^T(\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast })=0$.

When to Use Normal Equation

Pros:

• One-shot solution (koi iteration nahi)
• Exact (numerical precision tak)

Cons:

• $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ compute karna $O(d^3)$ hai jahan $d$ feature count hai
• Fail hota hai agar ${\mathbf{X}}^T\mathbf{X}$ singular ho (multicollinearity)
• $d>10,000$ ke liye impractical (aerospace sensor fusion mein common)

Method 2: Gradient Descent (Iterative Optimization)

Derivation from First Principles

Core idea: Ek random $\mathbf{w}$ se shuru karo, baar baar us direction mein step lo jo $J$ ko sabse tezi se decrease kare (negative gradient).

Step 1: $\mathbf{w}$ ke respect mein $J$ ka gradient compute karo.

Pehle se:

Yeh form kyun? $\mathbf{Xw}-\mathbf{y}$ error vector hai (predictions minus actuals). ${\mathbf{X}}^T$ se multiply karna har feature ko weight deta hai uske hisaab se ki usne error mein kitna contribute kiya.

Step 2: Update rule.

Yeh step kyun? Hum gradient ke opposite direction mein move karte hain (downhill). $\alpha$ control karta hai step kitna bada ho — bahut bada ho toh overshoot, bahut chhota ho toh convergence slow hogi.

Step 3: Convergence tak repeat karo.

Convergence criteria:

• $\Vert {\nabla }_{\mathbf{w}}J\Vert <ϵ$ (gradient almost zero)
• $|J_{t+1}-J_t|<ϵ$ (cost decrease karna band ho jaaye)
• Maximum iterations reach ho jaayein

Variants

Worked Examples

Bias column add karo: $\mathbf{X}=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right]$, $\mathbf{y}=\left[\begin{array}{c}2\\ 4\\ 5\end{array}\right]$

${\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]$

Yeh step kyun? Matrix multiplication: $(3\times 2{)}^T(3\times 2)=(2\times 2)$. ${\mathbf{X}}^T\mathbf{y}$ ki pehli entry hai $1\cdot 2+1\cdot 4+1\cdot 5=11$; doosri hai $1\cdot 2+2\cdot 4+3\cdot 5=2+8+15=25$.

Solve karo $\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right]\left[\begin{array}{c}b\\ w\end{array}\right]=\left[\begin{array}{c}11\\ 25\end{array}\right]$:

Inverse: $({\mathbf{X}}^T\mathbf{X}{)}^{-1}=\frac{1}{3\cdot 14-36}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\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]=\frac{1}{6}\left[\begin{array}{c}154-150\\ -66+75\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}4\\ 9\end{array}\right]=\left[\begin{array}{c}0.667\\ 1.5\end{array}\right]$

Result: $b=0.667$, $w=1.5$. Toh $\hat{y}=1.5x+0.667$.

Yeh kyun matter karta hai: Aerospace sensor calibration mein aksar reference measurements par lines fit karni padti hain.

Iteration 0:

• Predictions: $\hat{\mathbf{y}}=\mathbf{X}\left[\begin{array}{c}0\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$
• Error: $\mathbf{Xw}-\mathbf{y}=\left[\begin{array}{c}-2\\ -4\\ -5\end{array}\right]$
• Gradient: $\nabla J=\frac{1}{3}\left[\begin{array}{ccc}1& 1& 1\\ 1& 2& 3\end{array}\right]\left[\begin{array}{c}-2\\ -4\\ -5\end{array}\right]=\frac{1}{3}\left[\begin{array}{c}-11\\ -25\end{array}\right]=\left[\begin{array}{c}-3.667\\ -8.333\end{array}\right]$
• Yeh step kyun? ${\mathbf{X}}^T$ ka shape $(2\times 3)$ hai, error $(3\times 1)$ hai, result $(2\times 1)$ hai. Doosra component: $1\cdot (-2)+2\cdot (-4)+3\cdot (-5)=-2-8-15=-25$.
• Update: ${\mathbf{w}}_1=\left[\begin{array}{c}0\\ 0\end{array}\right]-0.1\left[\begin{array}{c}-3.667\\ -8.333\end{array}\right]=\left[\begin{array}{c}0.367\\ 0.833\end{array}\right]$

Iteration 1:

• $\hat{\mathbf{y}}=\mathbf{X}{\mathbf{w}}_1=\left[\begin{array}{c}0.367+0.833\\ 0.367+1.667\\ 0.367+2.500\end{array}\right]=\left[\begin{array}{c}1.200\\ 2.033\\ 2.867\end{array}\right]$
• Error: $\left[\begin{array}{c}-0.800\\ -1.967\\ -2.133\end{array}\right]$
• Gradient: $\frac{1}{3}\left[\begin{array}{c}-4.900\\ -11.133\end{array}\right]=\left[\begin{array}{c}-1.633\\ -3.711\end{array}\right]$
• Update: ${\mathbf{w}}_2=\left[\begin{array}{c}0.530\\ 1.204\end{array}\right]$

Convergence tak continue karo → $[0.667,1.5{]}^T$ ke paas pahunch jaayega.

Gradient descent kyun? Jab $d=10,000$ ho (jaise spacecraft pose estimation ke liye image features), inverse compute karna infeasible hai, lekin har gradient step fast hota hai.

Common Mistakes

Active Recall

Normal equation aisa hai jaise ek baar mein ruler aur protractor se exact perfect angle aur position calculate karo. Kuch matrix math karo aur ho gaya — ekdum done.

Gradient descent aisa hai jaise ek random line se shuru karo, phir dheere dheere use tilt aur slide karo. Dekho dots kahan hain, pata karo kaun sa direction cheezein worse banata hai, aur opposite direction mein move karo. Yeh baar baar repeat karo, har baar chhota sa adjustment karte hue, jab tak line aur better na ho sake. Zyada time lagta hai lekin kaam karta hai jab "ruler method" bahut complicated ho (jaise agar ek million dots hों).

Aerospace engineers isko use karte hain yeh predict karne ke liye ki plane alag alag speeds par kitna fuel burn karega — speed vs. fuel plot karo, best line dhundho, phir flights plan karne ke liye use karo.

Gradient Descent = "ITERATIVE steps ALPHA tuned"

• Iterative process
• Tiny steps (learning rate $\alpha$)
• Efficient for high dimensions

Connections

• Least Squares Estimation — same MSE criterion, weighted/nonlinear cases ke liye generalized
• Matrix Pseudoinverse — singular ${\mathbf{X}}^T\mathbf{X}$ handle karta hai
• Convex Optimization — kyun gradient descent converge karta hai (MSE convex hai)
• Feature Scaling — GD convergence ke liye zaroori
• Regularization (Ridge, Lasso) — overfitting rokne ke liye penalty term add karta hai
• Kalman Filtering — dynamic systems ke liye recursive least squares (spacecraft tracking)
• Neural Networks — gradient descent backpropagation mein generalize hota hai

Summary

• Normal equation: ${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$ (one-shot, $O(d^3)$, invertibility chahiye)
• Gradient descent: ${\mathbf{w}}_{t+1}={\mathbf{w}}_t-\alpha \nabla J$ (iterative, $O(nd)$ per step, large $d$ ke liye scale karta hai)
• $\frac{1}{2n}\Vert \mathbf{y}-\mathbf{Xw}{\Vert }^2$ minimize karne se derive hota hai $\nabla J=0$ set karke ya $\nabla J$ ke against step lekar
• Key tradeoffs: exact vs. iterative, memory vs. computation, batch vs. stochastic

#flashcards/coding

Linear regression ke liye normal equation kya hai? :: ${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$

$J(\mathbf{w})=\frac{1}{2n}\Vert \mathbf{y}-\mathbf{Xw}{\Vert }^2$ se normal equation derive karo :: Expand karo $\frac{1}{2n}({\mathbf{y}}^T\mathbf{y}-2{\mathbf{w}}^T{\mathbf{X}}^T\mathbf{y}+{\mathbf{w}}^T{\mathbf{X}}^T\mathbf{Xw})$ mein, derivative lo $\frac{\partial J}{\partial \mathbf{w}}=\frac{1}{n}({\mathbf{X}}^T\mathbf{Xw}-{\mathbf{X}}^T\mathbf{y})$, zero set karo: ${\mathbf{X}}^T\mathbf{Xw}={\mathbf{X}}^T\mathbf{y}$, solve karo: ${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$

Concept Map