OLS ও Normal Equations
এই পাঠে যা শিখবেন
- OLS-এর গাণিতিক formulation — matrix form-এ MSE
- Normal Equations-এর derivation — calculus + linear algebra
- Single-feature ও multi-feature — দু'টোই দেখা
- NumPy দিয়ে নিজে implement, sklearn-এর সাথে মিল যাচাই
১ · কেন closed-form দরকার
L09-এ আমরা grid search দিয়ে $w, b$ খুঁজেছি — slow। এখানে আমরা গণিতের সাহায্যে — exactly এক step-এ — best parameters পাব। এটাই OLSOrdinary Least Squares (OLS)Linear regression-এ MSE-কে minimize করে $w, b$ বের করার গাণিতিক পদ্ধতি। Carl Friedrich Gauss এবং Adrien-Marie Legendre স্বাধীনভাবে আবিষ্কার করেন (১৭৯৫–১৮০৫)।।
Loss surface convex (bowl-shaped) — তাই global minimum আছে। সেই minimum-এ gradient = ০। সেই equation solve করলেই answer।
২ · Single-feature derivation
Loss:
$$L(w, b) = \frac{1}{N} \sum_{i=1}^{N} (y_i - w x_i - b)^2$$
Minimum-এ $\partial L / \partial w = 0$ এবং $\partial L / \partial b = 0$।
(ক) $b$-র সাপেক্ষে partial derivative:
$$\frac{\partial L}{\partial b} = -\frac{2}{N} \sum (y_i - w x_i - b) = 0$$
$$\Rightarrow \bar{y} = w \bar{x} + b \quad \Rightarrow \quad b = \bar{y} - w \bar{x}$$
(খ) $w$-র সাপেক্ষে partial derivative:
$$\frac{\partial L}{\partial w} = -\frac{2}{N} \sum x_i (y_i - w x_i - b) = 0$$
উপরের $b$ substitute করে সরল করলে:
$$w = \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2}$$
ভাষায় — $w$ = covariance$(x, y)$ / variance$(x)$।
৩ · Multi-feature — matrix form
Multi-feature-এ — separate equations কষ্টদায়ক। Linear algebra সরাসরি সমাধান দেয়।
Design matrix $X \in \mathbb{R}^{N \times (n+1)}$ — প্রতিটি row একটি sample, প্রথম column সব ১ (bias-এর জন্য):
$$X = \begin{bmatrix} 1 & x_{11} & \cdots & x_{1n} \\ 1 & x_{21} & \cdots & x_{2n} \\ \vdots & & & \vdots \\ 1 & x_{N1} & \cdots & x_{Nn} \end{bmatrix}, \quad \mathbf{w} = \begin{bmatrix} b \\ w_1 \\ \vdots \\ w_n \end{bmatrix}$$
Predictions: $\hat{\mathbf{y}} = X \mathbf{w}$।
Loss vector form-এ:
$$L(\mathbf{w}) = \frac{1}{N} \| \mathbf{y} - X \mathbf{w} \|^2 = \frac{1}{N} (\mathbf{y} - X \mathbf{w})^\top (\mathbf{y} - X \mathbf{w})$$
$\mathbf{w}$-র সাপেক্ষে gradient:
$$\nabla_{\mathbf{w}} L = -\frac{2}{N} X^\top (\mathbf{y} - X \mathbf{w}) = 0$$
সরল করলে — Normal Equation:
$$\boxed{X^\top X \mathbf{w} = X^\top \mathbf{y}}$$
যদি $X^\top X$ invertible হয়:
$$\mathbf{w}^* = (X^\top X)^{-1} X^\top \mathbf{y}$$
৪ · জ্যামিতিক ব্যাখ্যা — projection
Normal Equation-এর geometric অর্থ — $\mathbf{y}$-কে column space of $X$-এ project করা। $X \mathbf{w}^*$ হলো $\mathbf{y}$-এর সবচেয়ে কাছের point in column space। Residual $(\mathbf{y} - X \mathbf{w}^*)$ — column space-এর সাথে orthogonal — এই কারণেই "Normal" (perpendicular) নাম।
৫ · NumPy দিয়ে — শূন্য থেকে
import numpy as np
# Data
X_raw = np.array([500, 800, 1200, 1500, 2000, 2500])
y = np.array([25, 40, 55, 70, 95, 120])
# Design matrix — bias column যোগ
X = np.column_stack([np.ones_like(X_raw), X_raw])
print("Design matrix X:\n", X)
# Normal equation
w = np.linalg.inv(X.T @ X) @ X.T @ y
print(f"\nb = {w[0]:.4f}")
print(f"w = {w[1]:.4f}")
# Prediction
y_hat = X @ w
mse = np.mean((y - y_hat) ** 2)
print(f"MSE = {mse:.4f}")৬ · Multi-feature example
import numpy as np
# Synthetic — house price, ৩ features
np.random.seed(0)
N = 100
area = np.random.uniform(500, 3000, N)
bedrooms = np.random.randint(1, 6, N)
age = np.random.uniform(0, 30, N)
# True model: price = 0.05*area + 5*bedrooms - 0.5*age + 10 + noise
y = 0.05*area + 5*bedrooms - 0.5*age + 10 + np.random.normal(0, 3, N)
# Design matrix
X = np.column_stack([np.ones(N), area, bedrooms, age])
# OLS
w = np.linalg.inv(X.T @ X) @ X.T @ y
print(f"intercept = {w[0]:.4f} (true 10)")
print(f"area = {w[1]:.4f} (true 0.05)")
print(f"bedrooms = {w[2]:.4f} (true 5)")
print(f"age = {w[3]:.4f} (true -0.5)")৭ · Numerical issue — কেন np.linalg.solve
Direct inversion ($X^\top X)^{-1}$ — slow ও numerically unstable। Better:
import numpy as np
X = np.array([[1, 500], [1, 800], [1, 1200], [1, 1500], [1, 2000], [1, 2500]])
y = np.array([25, 40, 55, 70, 95, 120])
# (ক) Direct inversion — avoid in production
w1 = np.linalg.inv(X.T @ X) @ X.T @ y
# (খ) np.linalg.solve — better numerically
w2 = np.linalg.solve(X.T @ X, X.T @ y)
# (গ) np.linalg.lstsq — best (uses SVD, handles singular)
w3, *_ = np.linalg.lstsq(X, y, rcond=None)
print("Direct inv:", w1)
print("Solve :", w2)
print("Lstsq :", w3)np.linalg.lstsq — production-grade। SVD ব্যবহার করে — singular matrix-এও pseudo-inverse দিয়ে answer। sklearn ভেতরে এটাই use।
৮ · কোথায় OLS fail করে
- Multicollinearity: দু'টি feature highly correlated — $X^\top X$ near-singular, inverse blow up। Solution: Ridge (L15)।
- $N < n$: Rows কম, columns বেশি — $X^\top X$ singular। Solution: regularization বা feature selection।
- Big features ($n > 10^4$): $O(n^3)$ — slow। Solution: SGD।
- Outliers: Squared loss — outlier dominate। Solution: Huber loss, RANSAC।
- Non-linear data: Linear assumption fail। Solution: feature engineering, kernel methods।
np.linalg.lstsq বা scipy.linalg.lstsq।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ "$X^\top X$ singular" — মানে কী? কখন এটা ঘটে? Ridge regression কীভাবে এই সমস্যা solve করে?
Singular matrix — linear algebra-র classical সমস্যা। Real-world ML-এ frequent।
Singular matrix কী:
- Determinant = ০।
- Inverse exist করে না।
- Rows/columns linearly dependent।
$X^\top X$ singular হওয়ার কারণ:
- Perfect multicollinearity: দু'টি feature exactly redundant। যেমন "weight in kg" ও "weight in pounds" — proportional।
- $N < n$: Sample-এর চেয়ে বেশি feature। Equations underdetermined।
- Constant feature: কোনো column-এ সব values same। Variance ০।
- Dummy variable trap: One-hot-এর সব columns রাখলে — sum = ১ = bias column।
Practical detection:
- Condition number — large মানে near-singular।
- VIF (Variance Inflation Factor) > ১০ — multicollinearity warning।
- Correlation matrix — pairwise detect।
- Determinant অথবা rank check।
Ridge regression solution:
$$\mathbf{w}_{\text{Ridge}} = (X^\top X + \lambda I)^{-1} X^\top \mathbf{y}$$
- $\lambda I$ — diagonal-এ small positive number যোগ।
- $X^\top X + \lambda I$ — guaranteed invertible (positive definite)।
- Numerically stable।
- Bonus: weights shrink — overfitting reduce।
কেন কাজ করে — geometrically:
- $X^\top X$-এর smallest eigenvalues ≈ ০ → unstable।
- $\lambda I$ — সব eigenvalues-এ $\lambda$ যোগ।
- Smallest eigenvalue এখন $\geq \lambda$।
- Inverse stable, answer reasonable।
$\lambda$ choice:
- $\lambda \to 0$ — OLS-এ ফিরে যাওয়া।
- $\lambda \to \infty$ — সব weights ০।
- Sweet spot: cross-validation।
বিকল্প solutions:
- Pseudo-inverse: SVD-ভিত্তিক — singular case handle।
- Feature selection: Redundant feature drop।
- PCA: Decorrelated features বানানো।
- Lasso: Automatic feature selection (L15)।
মূল উপলব্ধি: Singular matrix — feature redundancy-এর গাণিতিক symptom। Ridge — universal regularization tool। Real ML-এ যেকোনো linear model production-এ pure OLS-এর জায়গায় Ridge default করা wise।
প্র ০২ "Normal Equation $O(n^3)$" — practical মানে কী? ১,০০০, ১০,০০০, ১,০০,০০০ features-এ runtime কেমন? Alternative কী?
Computational complexity — production ML-এর make-or-break factor।
Normal Equation breakdown:
- $X^\top X$ — $O(N n^2)$ multiplications।
- Inverse — $O(n^3)$।
- $X^\top \mathbf{y}$ — $O(Nn)$।
- Final multiply — $O(n^2)$।
- Total: $O(N n^2 + n^3)$।
Practical timings (rough):
- $n = 100$: instant ($\sim 10^6$ flops)।
- $n = 1{,}000$: seconds ($\sim 10^9$ flops)।
- $n = 10{,}000$: minutes ($\sim 10^{12}$ flops)।
- $n = 100{,}000$: hours/days। Memory-ও blow up।
Memory:
- $X^\top X$ — $n \times n$ matrix।
- $n = 10^5$ → $10^{10}$ floats × 8 bytes = ৮০ GB।
- RAM-এ fit না — bottleneck।
Alternatives:
(১) Iterative methods:
- Gradient descent — $O(N n)$ per iteration।
- Conjugate gradient — exact in $\leq n$ iterations, $O(N n)$ each।
- Memory: $O(n)$ — much better।
(২) Stochastic methods:
- SGD — $O(n)$ per step (one sample)।
- Streaming data compatible।
- Convergence noisier but practical।
(৩) Sparse linear algebra:
- Text features — mostly ০।
- Sparse storage — memory ৯৯% reduce।
- Sparse OLS solvers — much faster।
(৪) Matrix factorization:
- QR decomposition — $O(N n^2)$, no inverse।
- SVD — most stable, slightly slower।
- Cholesky — $O(n^3 / 3)$ if positive definite।
(৫) Distributed computing:
- Spark MLlib — partition data across nodes।
- Each node compute partial $X^\top X$।
- Aggregate — sum partials।
- Final inverse on driver।
Modern reality:
- Most production: SGD with momentum।
- Closed-form: small/medium problems।
- Hybrid: closed-form for warm start, SGD for fine-tune।
scikit-learn rule of thumb:
- $n < 10^3$: OLS।
- $n \in [10^3, 10^4]$: Ridge with closed-form।
- $n > 10^4$: SGD।
মূল উপলব্ধি: Beautiful math + slow algorithm = academic interest। Production ML scaling considerations dominant। Closed-form pedagogically essential কিন্তু rarely deployed at scale।
প্র ০৩ "Residual $(\mathbf{y} - X\mathbf{w}^*)$ orthogonal to columns of $X$" — এই geometric property-র AI implication কী? Neural networks-এ analog কী?
Linear algebra-র এই subtle property — ML-এর deep theoretical foundation।
Orthogonality condition:
- $X^\top (\mathbf{y} - X\mathbf{w}^*) = 0$।
- $\mathbf{r} = \mathbf{y} - X\mathbf{w}^*$ — residual।
- $X^\top \mathbf{r} = 0$ — প্রতিটি feature-এর সাথে residual orthogonal।
Geometric interpretation:
- $\mathbf{y}$ — N-D space-এ point।
- Column space of $X$ — n-D subspace।
- $X\mathbf{w}^*$ — $\mathbf{y}$-এর projection on subspace।
- Residual — perpendicular drop।
- "Closest point" property।
Statistical interpretation:
- Residual contains information NOT explained by features।
- Orthogonality — model has extracted all linear signal।
- Remaining noise — by design unrelated to features।
Implications:
(১) Optimal "in linear sense":
- OLS extracts maximum linear information।
- If residual still correlated with feature — non-linearity present।
- "Adding feature won't help linearly"।
(২) Residual analysis:
- Plot residual vs each feature।
- Pattern visible — model misspecification।
- Pure random — model adequate।
(৩) Hypothesis testing:
- $t$-tests on coefficients valid।
- Confidence intervals computable।
- F-test for overall fit।
Neural network analog:
- Convergence: Gradient ≈ ০ at minimum — analog of orthogonality।
- Critical points: Loss landscape geometry।
- Information bottleneck: Layer extracts relevant features।
- Lottery ticket hypothesis: Optimal subnetwork discovery।
Theoretical extensions:
- Hilbert space: Infinite-dimensional generalization।
- Reproducing Kernel Hilbert Space (RKHS): Kernel methods foundation।
- Function approximation theory: Best approximation in subspace।
Practical use:
- Gram-Schmidt: Orthogonalize features for stable computation।
- QR decomposition: Solve OLS without inverting।
- Boosting: Each weak learner fit residual।
মূল উপলব্ধি: Orthogonality — linear regression-এর deep mathematical structure। Boosting (L23), kernel methods (L29), ও আধুনিক self-supervised learning-এর foundation এই concept-এ।
প্র ০৪ OLS-এর coefficients-এ standard error থাকে — তার মানে কী? "$p$-value < 0.05" সিদ্ধান্ত নেওয়া কতটা trustworthy?
Statistical inference — OLS-এর underappreciated দিক। ML practitioners often skip; statisticians overemphasize।
Standard error:
- প্রতিটি coefficient $w_j$ — point estimate।
- Different sample → different estimate।
- Standard error — estimate-এর variability।
OLS coefficient distribution:
- Under standard assumptions — Gaussian residuals।
- $\hat{\mathbf{w}} \sim \mathcal{N}(\mathbf{w}, \sigma^2 (X^\top X)^{-1})$।
- Each coefficient — Gaussian around true value।
$t$-statistic:
- $t = \hat{w}_j / \text{SE}(\hat{w}_j)$।
- $|t|$ large → $w_j \neq 0$ likely।
- $p$-value — null hypothesis ($w_j = 0$) সত্য হলে এই extreme observation-এর probability।
"$p < 0.05$" interpretation:
- "Less than 5% chance to see this extreme if $w_j$ truly ০"।
- Common threshold for "statistically significant"।
- Reject null hypothesis।
সাবধানতা — কখন trustworthy:
(১) Assumptions valid?
- Linearity — relationship truly linear?
- Homoscedasticity — variance constant?
- Normality — residuals normal?
- Independence — observations independent?
(২) Multiple testing:
- ২০ features test — পাঁচটায় false positive expected at 5% threshold।
- Bonferroni correction: threshold / number of tests।
- FDR (Benjamini-Hochberg) — modern alternative।
(৩) Sample size:
- Small N — power low, false negatives common।
- Large N — even tiny effect "significant"।
- Effect size > $p$-value।
(৪) Causal vs predictive:
- "Significant coefficient" ≠ "causal"।
- Confounding, reverse causality possible।
- RCT or causal inference framework needed for causal claims।
ML perspective:
- Predictive ML — prediction accuracy matters।
- Statistical significance — secondary।
- Cross-validation > $p$-value for ML evaluation।
Real-world implications:
- Medical research — replication crisis partially due to $p$-hacking।
- Pre-registration trends — protect against false discoveries।
- Bayesian alternatives — credible intervals more interpretable।
scikit-learn vs statsmodels:
- scikit-learn — ML focus, no $p$-values default।
- statsmodels — full statistical inference।
- Choose tool based on goal।
মূল উপলব্ধি: OLS-এর coefficients-এর uncertainty quantifiable — কিন্তু interpretation careful। "Significant" mathematically ≠ "important" practically। Statistical literacy = ML literacy-র অপরিহার্য অংশ।
অনুশীলন
-
হিসাব করুন: Data: $x = [1, 2, 3, 4]$, $y = [2, 4, 6, 8]$।
- $\bar{x}, \bar{y}$ কত?
- OLS দিয়ে $w, b$ কত?
- Predicted line কী?
- $\bar{x} = 2.5$, $\bar{y} = 5$।
- $w = \frac{\sum (x_i - 2.5)(y_i - 5)}{\sum (x_i - 2.5)^2} = \frac{10}{5} = 2$।
- $b = \bar{y} - w\bar{x} = 5 - 2 \cdot 2.5 = 0$।
- Line: $y = 2x$ — perfect fit।
-
NumPy: উপরের data-তে normal equation দিয়ে যাচাই করুন।
import numpy as np x = np.array([1, 2, 3, 4]) y = np.array([2, 4, 6, 8]) X = np.column_stack([np.ones_like(x), x]) w = np.linalg.lstsq(X, y, rcond=None)[0] print(w) # [0., 2.] -
চিন্তা: $X^\top X$-এর determinant ০-র কাছাকাছি — কী symptom এটা data-তে? কীভাবে আপনি diagnose করবেন?
Multicollinearity বা $N < n$ situation। Diagnose: VIF computation, correlation matrix, condition number check। Fix: drop redundant feature, Ridge regression, PCA।
আরও পড়ুন
- পাঠ ১১ · Gradient descent প্রয়োগ পরবর্তী পাঠ Closed-form-এর বিকল্প — iterative learning।
- পাঠ ০৯ · Linear Regression আগের পাঠ Concept revisit।
- পাঠ ১৫ · Ridge ও Lasso এই পাঠের সাথে সম্পর্কিত Singular matrix সমস্যা solve।
- সব AI Courses ABCL TECH Python, ML, DL, NLP, CV, GenAI, RL, MLOps।