Ordinary least squares derivation

2.2.3 · AI-ML › Linear & Logistic Regression

Overview

Ordinary Least Squares (OLS) ek analytical method hai jo linear regression mein optimal parameters dhundne ke liye squared residuals ke sum ko minimize karta hai. Gradient descent (jo iterative hota hai) ke unlike, OLS humein calculus ke zariye ek closed-form solution deta hai.

Socho: "Hum model ko galat hone ke liye quadratically punish karte hain, isliye woh badi galtiyon ko fix karne ki sabse zyada koshish karta hai."

The Setup: Hum Kya Optimize Kar Rahe Hain?

Problem Statement

Diya gaya hai:

• Training data: $\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$ jahan $x_i\in {\mathbb{R}}^n$, $y_i\in \mathbb{R}$
• Model: ${\hat{y}}_i={\theta }^T{x}_i={\theta }_0+{\theta }_1{x}_{i1}+\cdots +{\theta }_n{x}_{in}$

Dhundna hai: Parameter vector $\theta \in {\mathbb{R}}^{n+1}$ jo cost function ko minimize kare:

$J(\theta )=\frac{1}{2m}{\sum }_{i=1}^m(h_{\theta }(x_i)-y_i{)}^2$

$\frac{1}{2m}$ kyun?

• $m$ examples pe average karta hai (cost ko alag dataset sizes mein comparable banata hai)
• $\frac{1}{2}$, $x^2$ ki derivative ke saath cancel ho jaata hai (convenience ke liye, optimal $\theta$ nahi badalta)

Matrix Formulation

Sab kuch matrices mein daal do (yahan linear algebra ki power enter hoti hai):

1 & x_{11} & x_{12} & \cdots & x_{1n} \\ 1 & x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{m1} & x_{m2} & \cdots & x_{mn} \end{bmatrix}_{m \times (n+1)}, \quad y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \ y_m \end{bmatrix}_{m \times 1}, \quad \theta = \begin{bmatrix} \theta_0 \\ \theta_1 \\ \vdots \\ \theta_n \end{bmatrix}_{(n+1) \times 1}$$ **1s ka column kyun?** Yeh bias term $\theta_0$ (intercept) hai. Isse $X$ mein add karke, hum bias aur weights ko uniformly handle karte hain: $\hat{y} = X\theta$. Ab hamari cost ban jaati hai: $$J(\theta) = \frac{1}{2m} \|X\theta - y\|^2 = \frac{1}{2m}(X\theta - y)^T(X\theta - y)$$ ## First Principles se Derivation ### Step 1: Squared Error Expand Karo $$J(\theta) = \frac{1}{2m}(X\theta - y)^T(X\theta - y)$$ Ise $(A - B)^T(A - B) = A^TA - A^TB - B^TA + B^TB$ use karke expand karte hain: $$J(\theta) = \frac{1}{2m}\left[(X\theta)^T(X\theta) - (X\theta)^Ty - y^T(X\theta) + y^Ty\right]$$ **Yeh step kyun?** Differentiate karne ke liye humein saare $\theta$ terms explicitly dekhne hain. Kyunki $(X\theta)^Ty$ ek scalar hai, yeh apne transpose $y^T(X\theta)$ ke barabar hai: $$J(\theta) = \frac{1}{2m}\left[\theta^TX\theta - 2y^TX\theta + y^Ty\right]$$ ### Step 2: Gradient Lo Minimize karne ke liye, humein $\nabla_\theta J(\theta) = 0$ chahiye. > [!definition] Matrix Calculus Rules Jo Humein Chahiye > 1. $\frac{\partial}{\partial \theta}(a^T\theta) = a$ (linear term) > 2. $\frac{\partial}{\partial \theta}(\theta^TA\theta) = 2A\theta$ (quadratic term, jab $A$ symmetric ho) > 3. $\frac{\partial}{\partial \theta}(c) = 0$ (constant term) In rules ko apply karte hain: $$\nabla_\theta J(\theta) = \frac{1}{2m}\left[2X^TX\theta - 2X^Ty + 0\right] = \frac{1}{m}\left[X^TX\theta - X^Ty\right]$$ **2 kyun aata hai?** Quadratic form $\theta^TX\theta$ differentiate hoke $2X^TX\theta$ deta hai (dono sides symmetrically contribute karti hain). ### Step 3: Gradient Ko Zero Set Karo $$\frac{1}{m}\left[X^TX\theta - X^Ty\right] = 0$$ $$X^TX\theta = X^Ty$$ > [!formula] Normal Equation > $$\boxed{\theta^* = (X^TX)^{-1}X^Ty}$$ Yeh linear regression ka **analytical solution** hai. Matrix $(X^TX)^{-1}X^T$ ko ==Moore-Penrose pseudoinverse== kehte hain. **"Normal" kyun?** Geometry mein, "normal" ka matlab perpendicular hota hai. Optimum pe, residual vector $(X\theta^* - y)$, $X$ ke column space ke **orthogonal** hota hai. Isliye $X^T(X\theta^* - y) = 0$. ## Worked Examples > [!example] Example 1: Simple Linear Regression (1D) > **Setup**: $y = \theta_0 + \theta_1 x$ fit karo data pe: $(1, 2), (2, 4), (3, 5)$ **Step 1**: Matrices banao $$X = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}, \quad y = \begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix}$$ **Step 2**: $X^TX$ compute karo $$X^TX = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}$$ **Yeh step kyun?** Normal equation ke liye $X^TX$ ko invert karna hai. **Step 3**: $X^Ty$ compute karo $$X^Ty = \begin{bmatrix} 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix} = \begin{bmatrix} 11 \ 25 \end{bmatrix}$$ **Step 4**: $X^TX$ invert karo $$\text{det}(X^TX) = 3(14) - 6(6) = 42 - 36 = 6$$ $$(X^TX)^{-1} = \frac{1}{6}\begin{bmatrix} 14 & -6 \\ -6 & 3 \end{bmatrix} = \begin{bmatrix} 7/3 & -1 \\ -1 & 1/2 \end{bmatrix}$$ **Step 5**: Solve karo $$\theta^* = \begin{bmatrix} 7/3 & -1 \ -1 & 1/2 \end{bmatrix} \begin{bmatrix} 11 \\ 25 \end{bmatrix} = \begin{bmatrix} 77/3 - 25 \\ -11 + 25/2 \end{bmatrix} = \begin{bmatrix} 2/3 \\ 3/2 \end{bmatrix}$$ > **Answer**: $\theta_0 = 2/3$, $\theta_1 = 3/2$, isliye $\hat{y} = \frac{2}{3} + \frac{3}{2}x$ > > **Verification**: $x=2$ daalo: $\hat{y} = 2/3 + 3 = 3.67$ (actual $y=4$ ke karib ✓) > > [!example] Example 2: $(X^TX)$ Invertible Kyun Nahi Ho Sakta > **Scenario**: 3 data points, 2 features, lekin feature 2 = $2 \times$ feature 1 (==multicollinearity==) > $$X = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 2 & 4 \\ 1 & 3 & 6 \end{bmatrix}$$ **Compute karo**: $$X^TX = \begin{bmatrix} 3 & 6 & 12 \\ 6 & 14 & 28 \\ 12 & 28 & 56 \end{bmatrix}$$ **Determinant check karo**: Row 3 = 2 × Row 2, isliye matrix **singular** hai (det = 0). **Yeh kyun matter karta hai**: Jab features linearly dependent hote hain, toh infinitely many $\theta$ cost minimize karte hain. Problem ==ill-posed== ho jaati hai. **Solution**: ==Regularization== use karo (Ridge/Lasso) ya redundant features hatao. ## Common Mistakes > [!mistake] Mistake 1: Bias Column Bhool Jaana > **Galat soch**: "Main sirf apne features wala $X$ use karunga, algorithm intercept khud figure out kar lega." **Kyun sahi lagta hai**: Basic algebra mein hum $y = mx + b$ alag se likhte hain. **Fix**: Linear algebra formulation mein bias ko explicitly 1s ke column ke roop mein chahiye. Iske bina, teri line **origin se force hogi** (underfitting). **Test**: $y = 2x + 3$ data ko bias ke bina fit karo. $\theta_1 \approx 2.something$ milega lekin predictions ~3 off hongi. > [!mistake] Mistake 2: OLS Use Karna Jab $m < n$ Ho (Underdetermined System) > **Galat soch**: "Zyada features = better model, 10 data points ke liye 100 features add karta hoon." **Kyun sahi lagta hai**: Zyada parameters zyada patterns capture karenge. **Reality**: Jab $m < n+1$, $X^TX$ singular ho jaata hai (saare $\theta$ uniquely solve karne ke liye enough equations nahi hain). ==Overfitting== hoti hai — model noise memorize kar leta hai. **Fix**: Regularization use karo ya features ko $n < m$ tak reduce karo. > [!mistake] Mistake 3: Yeh Maanna Ki OLS Hamesha Gradient Descent Se Faster Hai > **Galat soch**: "Closed form = instant solution." **Reality**: $X^TX$ invert karna $O(n^3)$ hai aur store karna $O(n^2)$. $n > 10,000$ features ke liye, yeh iterative methods se **slower aur zyada memory-intensive** hai. **Rule of thumb**: OLS tab use karo jab $n < 1000$ aur data memory mein fit ho. Warna, gradient descent ya stochastic variants use karo. ## Jab Normal Equation Fail Hoti Hai $(X^TX)$ invertible hai **agar aur sirf agar** $X$ ka ==full column rank== ho (saare columns linearly independent hon). **Failure cases**: 1. **Redundant features**: Do features perfectly correlated hain (jaise temperature °C aur °F mein) 2. **Features samples se zyada**: $n > m$ (underdetermined) 3. **Duplicate rows**: Same data point repeat hua **Detection**: `np.linalg.matrix_rank(X.T @ X)` compute karo. Agar rank $< n+1$, toh problem hai. **Fixes**: - Correlated features hatao (correlation matrix check karo) - ==Regularization== add karo: $\theta^* = (X^TX + \lambda I)^{-1}X^Ty$ (Ridge regression) - Dimensionality reduction use karo (PCA) ## Computational Considerations ### Complexity Analysis | Operation | Complexity | Kyun? | |-----------|--------|---| | $X^TX$ | $O(mn^2)$ | $m \times n$ ko $n \times m$ se multiply karo | | $(X^TX)^{-1}$ | $O(n^3)$ | Gaussian elimination ya LU decomposition | | $(X^TX)^{-1}X^Ty$ | $O(n^2m)$ | Matrix-vector multiplications | | **Total** | $O(mn^2 + n^3)$ | $n$ bada ho toh $n^3$ dominate karta hai | **Gradient Descent se comparison**: - GD: $O(kmn)$ jahan $k$ = iterations (typically $k \ll n$) - GD tab jeetta hai jab $n > 1000$ ya data RAM mein fit na ho ### Numerical Stability > [!intuition] Direct Inversion Kyun Fail Ho Sakti Hai > Even jab $(X^TX)$ theoretically invertible ho, floating-point arithmetic ise **numerically singular** bana sakti hai agar: > - Features ke scales bahut alag hain (jaise age years mein vs. income dollars mein) > - $X^TX$ ka condition number high hai (matrix "nearly" singular hai) **Better approach**: Direct inversion ki jagah ==QR decomposition== ya ==SVD== use karo. Libraries jaise `numpy.linalg.lstsq` yeh automatically karti hain. ```python # Bad: theta = np.linalg.inv(X.T @ X) @ X.T @ y # Good: theta = np.linalg.lstsq(X, y, rcond=None)[0] ``` ## Geometric Interpretation Solution $\theta^*$ prediction vector $X\theta^*$ ko $y$ ka $X$ ke column space pe **orthogonal projection** banata hai. **Kyun?** Residual $e = y - X\theta^*$, $X$ ke har column ke perpendicular hai: $$X^T e = X^T(y - X\theta^*) = 0$$ Yahi toh hamari normal equation hai! Geometrically, hum $X$ ke column space mein target $y$ ke **sabse karib point** dhundh rahe hain. > [!mnemonic] OLS Steps ke liye "PLOT" > - **P**roblem: $X$, $y$ set up karo (bias mat bhoolo!) > - **L**inear algebra: $X^TX$ aur $X^Ty$ compute karo > - **O**ptimize: $(X^TX)\theta = X^Ty$ solve karo > - **T**est: Invertibility check karo aur data pe validate karo ## Connections - [[Linear Regression Fundamentals]] — woh model jo yeh solve karta hai - [[Gradient Descent]] — OLS ka iterative alternative - [[Ridge Regression]] — non-invertibility fix karne ke liye $\lambda I$ add karta hai - [[Maximum Likelihood Estimation]] — OLS, Gaussian noise ke under MLE hai - [[QR Decomposition]] — normal equations solve karne ka numerically stable tarika - [[Pseudoinverse]] — singular matrices ke liye matrix inverse generalize karta hai - [[Feature Scaling]] — $X^TX$ mein numerical issues prevent karta hai - [[Bias-Variance Tradeoff]] — OLS ka zero bias hota hai lekin high variance ho sakta hai --- > [!recall]- 12-Saal Ke Bacche Ko Samjhao > Socho tum ek graph pe kuch dots ke through "best-fit" straight line draw karne ki koshish kar rahe ho. Kaise pata chalega ki teri line "best" hai? Ek tarika hai ki har dot apni line se kitna door hai yeh measure karo (inhe "errors" ya "mistakes" kehte hain). Agar koi dot line ke upar hai, toh upar measure karo; neeche hai toh neeche. Lekin problem yeh hai: kuch mistakes positive hain (upar) aur kuch negative (neeche), toh yeh cancel ho sakte hain even agar teri line bahut buri ho! Isliye, hum saari mistakes ko **square** karte hain. Ab har mistake positive hai (kyunki negative × negative = positive). Hum saari squared mistakes add karte hain aur us total ko jitna ho sake chhota karne ki koshish karte hain. Yahi toh "least squares" part hai! "Ordinary" part ka matlab sirf yeh hai ki hum normal math use kar rahe hain (kuch fancy nahi). Aur yahan cool baat yeh hai: ek magic formula hai jo bina guessing ke perfect line **turant** de deta hai. Yeh exam se pehle answer key paane jaisa hai! Hum kuch matrix math (numbers ki tables ke saath fancy multiplication) use karte hain exact slope aur intercept dhundne ke liye jo total squared error ko smallest possible banaye. Woh formula hai $(X^TX)^{-1}X^Ty$ — scary lagta hai, lekin matlab sirf yeh hai: "Apne data ko ek special tarike se mix karo aur perfect answer nikal aata hai!" Yeh isliye kaam karta hai kyunki hum calculus use karke dhundh rahe hain ki error kahaan sabse minimum hai — jaise kisi valley ki tali dhundna. Us tali mein, agar kisi bhi direction mein ek chhota sa step lo, error badhne lagti hai. Isliye humein pata chalta hai ki best line mil gayi. --- #flashcards/ai-ml Ordinary Least Squares (OLS) method kya hai? :: Ek analytical approach jo optimal linear regression parameters dhundne ke liye squared residuals ke sum ko minimize karta hai, calculus ke zariye closed-form solution $\theta^* = (X^TX)^{-1}X^Ty$ deta hai. OLS mein absolute values ki jagah residuals ko square kyun karte hain? ::: (1) Squaring sign cancellation khatam karta hai, (2) badi errors ko zyada penalize karta hai (outlier sensitivity), (3) calculus ke liye differentiable cost function milti hai, aur (4) Gaussian noise ke under maximum likelihood estimation ke corresponding hai. Normal Equation kya hai? ::: $\theta^* = (X^TX)^{-1}X^Ty$, linear regression ka closed-form solution jo cost function ka gradient zero set karke milta hai. "Normal" isliye kehte hain kyunki residual vector, X ke column space ke orthogonal (normal) hota hai. Design matrix X mein 1s ka column kyun add karte hain? ::: Bias term (intercept) $\theta_0$ ko matrix formulation mein incorporate karne ke liye, taaki bias aur weights ko equation $\hat{y} = X\theta$ mein uniformly handle kar sakein. $(X^TX)$ kab invertible nahi hota? ::: Jab X ka full column rank nahi hota: (1) redundant/correlated features, (2) samples se zyada features ($n > m$), ya (3) duplicate data points. Isse system underdetermined ho jaata hai jisme infinitely many solutions hote hain. Normal Equation se OLS solve karne ki computational complexity kya hai? ::: $O(mn^2 + n^3)$, $O(n^3)$ matrix inversion step dominate karta hai. $X^TX$ compute karne mein $O(mn^2)$ aur final multiplication mein $O(n^2m)$ lagta hai. OLS ki jagah gradient descent kab use karna chahiye? ::: Jab $n > 1000$ features hon (inversion expensive ho jaata hai), data memory mein fit na ho, ya online learning chahiye. Gradient descent ki complexity $O(kmn)$ hai jahan $k$ iterations hain, large $n$ ke liye typically bahut faster. $X^T(y - X\theta^*) = 0$ ka geometrically kya matlab hai? ::: Residual vector $e = y - X\theta^*$, X ke column space ke orthogonal hai. Prediction $X\theta^*$, y ka X ke column space pe orthogonal projection hai — us space mein y ke sabse karib point. $(X^TX)^{-1}$ directly compute karna theoretically invertible hone pe bhi numerically kyun fail ho sakta hai? ::: Alag scales wale features ya high condition number floating-point precision limits ki wajah se matrix ko numerically singular bana sakte hain. Behtar hai QR decomposition ya SVD use karo (jaise `np.linalg.lstsq`). Ridge regression non-invertibility problem kaise fix karta hai? ::: Regularization term add karta hai: $\theta^* = (X^TX + \lambda I)^{-1}X^Ty$. $\lambda I$ term ensure karta hai ki $(X^TX + \lambda I)$ hamesha invertible (positive definite) ho, even jab $X^TX$ singular ho. Multicollinearity kya hai aur yeh OLS kyun todta hai? ::: Jab features linearly dependent hote hain (ek ko doosron ke combination se likha ja sake), to $X^TX$ singular ho jaata hai. Isse infinitely many optimal solutions banta hai, problem ill-posed ho jaati hai. $\frac{\partial}{\partial \theta}(\theta^TX\theta) = 2X^TX\theta$ kyun hota hai, derive karo ::: Maano $A = X^TX$ (symmetric). Expand karo: $\theta^TA\theta = \sum_i \sum_j \theta_i A_{ij} \theta_j$. $\frac{\partial}{\partial \theta_k}$ lete hain toh $\sum_j A_{kj}\theta_j + \sum_i A_{ik}\theta_i = 2\sum_j A_{kj}\theta_j = 2(A\theta)_k$ milta hai kyunki $A$ symmetric hai. Isliye $\nabla_\theta(\theta^TA\theta) = 2A\theta$. ## 🖼️ Concept Map ```mermaid flowchart TD OLS[Ordinary Least Squares] -->|minimize karta hai| COST[Cost function J theta] COST -->|sum hai| SQ[Squared residuals] SQ -->|sign cancel avoid karta hai| WHY[Squaring rationale] WHY -->|barabar hai| MLE[Max likelihood under Gaussian] COST -->|likha jaata hai| MAT[Matrix form X theta minus y] MAT -->|add karta hai| BIAS[Column of 1s for intercept] MAT -->|terms expand karo| EXP[Expanded quadratic] EXP -->|gradient zero set karo| GRAD[Gradient of J] GRAD -->|solve hota hai| NEQ[Normal equations] NEQ -->|closed-form| SOL[theta equals XtX inv Xt y] OLS -->|alternative hai| GD[Gradient descent iterative] SOL -->|optimal params deta hai| LR[Linear regression] ```