পাঠ ০২ · ৪৫-এর মধ্যে · মডিউল ১

Home / AI Courses / Machine Learning / ERM

ERM ও Hypothesis class

Empirical Risk Minimization & hypothesis class

৭ মিনিট পড়া মাঝারি · Intermediate গণিতসহ

এই পাঠে যা শিখবেন

True risk বনাম empirical risk — পার্থক্য কেন গুরুত্বপূর্ণ
Hypothesis class — মডেলের "সম্ভাবনার আকাশ"
Empirical Risk Minimization (ERM) — সব supervised ML-এর কেন্দ্রীয় সূত্র
Approximation, Estimation, Optimization error — তিন ধরনের ভুল
NumPy দিয়ে ERM হাতে-কলমে

১ · কেন একটি গাণিতিক কাঠামো দরকার?

L01-এ আমরা দেখলাম — ML উদাহরণ থেকে শেখে। কিন্তু "শেখা" — এর গাণিতিক অর্থ কী? কোন ফাংশন "ভাল"? কোনটি "সবচেয়ে ভাল"? এই প্রশ্নের উত্তর দিতে আমাদের একটি formal framework দরকার।

Vladimir Vapnik (১৯৯৫) এই formalism তৈরি করেছিলেন — যা আজও সব supervised learning-এর ভিত্তি। SVM (L27), Deep Learning, এমনকি GPT-৪ — সবই এই কাঠামোর বিশেষ রূপ।

মূল ধারণা

আমাদের লক্ষ্য — এমন একটি ফাংশন $f$ খুঁজে বের করা যা ভবিষ্যতে ভাল কাজ করবে। কিন্তু আমাদের কাছে শুধু অতীতের ডেটা। কীভাবে অতীত থেকে ভবিষ্যৎ অনুমান?

২ · True risk — আদর্শ লক্ষ্য

ধরুন একটি অজানা probability distributionProbability Distributionএকটি random variable-এর সব সম্ভাব্য মানের সম্ভাবনা describe করে। ML-এ আমরা ধরি data points $(x, y)$ একটি true distribution $\mathcal{D}$ থেকে আসে। $\mathcal{D}$ আছে যেখান থেকে সব $(x, y)$ আসে। যেকোনো ফাংশন $f$-এর true risk:

$$R(f) = \mathbb{E}_{(x,y) \sim \mathcal{D}}[L(f(x), y)]$$

এটি বলে — যদি আমরা $\mathcal{D}$ থেকে অসীম সংখ্যক উদাহরণ নিই, $f$-এর গড় loss কত হবে। এটাই আসল metric — production-এ যা আসবে।

সমস্যা: $\mathcal{D}$ অজানা — আমরা সেটি দেখতে পাই না। আমাদের কাছে শুধু $n$টি sample $\{(x_i, y_i)\}_{i=1}^n$।

ভাবুন — বাংলাদেশের সব মানুষের গড় উচ্চতা জানতে চান। আদর্শ — সবাইকে মাপুন। বাস্তবে — ১০০০ জনের sample থেকে অনুমান। True risk = সবার গড়, empirical risk = sample-এর গড়।

৩ · Empirical risk — যা আমরা মাপতে পারি

Training set-এ গড় loss-কে বলে empirical risk:

$$\hat{R}(f) = \frac{1}{n} \sum_{i=1}^{n} L(f(x_i), y_i)$$

Empirical Risk Minimization (ERM):

$$\hat{f} = \arg\min_{f \in \mathcal{H}} \hat{R}(f)$$

মানে — হাইপোথিসিস ক্লাস $\mathcal{H}$-এর ভেতরে এমন $f$ খুঁজে বের করি যা training set-এ সবচেয়ে কম গড় loss দেয়। সব supervised learning algorithm — Linear Regression, Neural Network, XGBoost — এই formula-এর বিশেষ রূপ।

৪ · Hypothesis class — সম্ভাবনার সেট

$\mathcal{H}$ হলো — মডেলের সম্ভাব্য সব form-এর সেট। উদাহরণ:

Linear: $\mathcal{H} = \{f(x) = w^\top x + b : w \in \mathbb{R}^d, b \in \mathbb{R}\}$
Polynomial degree-৩: $\mathcal{H} = \{a_0 + a_1 x + a_2 x^2 + a_3 x^3\}$
Decision tree depth-৫: সব tree যাদের গভীরতা ≤ ৫।
Neural network: নির্দিষ্ট architecture-এর সব weight combination।

$\mathcal{H}$ বাছাই = মডেল architecture বাছাই। এটি ML-এর সবচেয়ে গুরুত্বপূর্ণ সিদ্ধান্ত।

ERM-এর কাঠামো: true risk minimize করতে চাই, কিন্তু empirical risk minimize করি — একটি hypothesis class-এর ভেতরে।

৫ · কেন এটি কাজ করে — Law of Large Numbers

$n$ বড় হলে empirical risk $\hat{R}(f)$ true risk $R(f)$-এর কাছাকাছি যায়:

$$\hat{R}(f) \xrightarrow{n \to \infty} R(f)$$

এটাই ERM-এর গাণিতিক ন্যায্যতা। Hoeffding inequality আরও বলে — প্রবাবিলিটি ১-δ-এ:

$$|R(f) - \hat{R}(f)| \leq \sqrt{\frac{\log(2|\mathcal{H}|/\delta)}{2n}}$$

এই bound-এর তিন insight: $n$ বাড়লে gap কমে; $|\mathcal{H}|$ বড় হলে gap বাড়ে; কত certain চান (δ ছোট) তত বেশি ডেটা লাগে।

৬ · তিন ধরনের ভুল

আদর্শ ফাংশন $f^*$ (সর্বোত্তম যা সম্ভব) থেকে আমাদের $\hat{f}$ পর্যন্ত — তিনটি error step:

Error decomposition

$$R(\hat{f}) - R(f^*) = \underbrace{R(f_{\mathcal{H}}^*) - R(f^*)}_{\text{Approximation}} + \underbrace{R(\hat{f}_{\mathcal{H}}) - R(f_{\mathcal{H}}^*)}_{\text{Estimation}} + \underbrace{R(\hat{f}) - R(\hat{f}_{\mathcal{H}})}_{\text{Optimization}}$$

Approximation error: $\mathcal{H}$ যথেষ্ট rich না হলে — best $f \in \mathcal{H}$ আদর্শ থেকে দূরে।
Estimation error: Training set ছোট/noisy — তাই empirical optimum সঠিক optimum নয়।
Optimization error: Algorithm (gradient descent ইত্যাদি) সঠিক empirical optimum পৌঁছাতে ব্যর্থ।

৭ · NumPy-তে ERM হাতে-কলমে

একটি linear regression — ERM rough form-এ:

Python · NumPy

import numpy as np

# ১০০টি training উদাহরণ — ground truth: y = 2x + 1 + noise
np.random.seed(42)
X = np.random.uniform(-5, 5, size=(100, 1))
y = 2 * X.squeeze() + 1 + np.random.normal(0, 1, 100)

# Hypothesis class: f(x) = w*x + b — কিছু candidate চেষ্টা
def empirical_risk(w, b, X, y):
    pred = w * X.squeeze() + b
    return np.mean((pred - y) ** 2)   # squared loss

# গ্রিড সার্চে empirical risk minimize
ws = np.linspace(0, 4, 41)
bs = np.linspace(-1, 3, 41)

best = (None, None, np.inf)
for w in ws:
    for b in bs:
        r = empirical_risk(w, b, X, y)
        if r < best[2]: best = (w, b, r)

print(f"ERM solution: w={best[0]:.2f}, b={best[1]:.2f}, R̂={best[2]:.3f}")
print(f"True parameters: w=2.00, b=1.00")

ERM solution true-এর কাছাকাছি কিন্তু ঠিক সমান নয় — কারণ noise আছে এবং grid coarse। এটাই estimation error-এর demonstration। L10-এ আমরা closed-form (normal equation) দিয়ে exact solution বের করব।

৮ · ERM-এর সীমাবদ্ধতা

ERM সরাসরি apply করলে — overfitting হয়। কারণ মডেল training set-এর প্রতিটি noise-ও fit করার চেষ্টা করে। তাই বাস্তবে আমরা regularized ERM ব্যবহার করি:

$$\hat{f} = \arg\min_{f \in \mathcal{H}} \hat{R}(f) + \lambda \cdot \text{complexity}(f)$$

Ridge (L2), Lasso (L1) — এই পদ্ধতি (L15-এ বিস্তারিত)। আজকের সব production model — XGBoost, neural network — এই pattern অনুসরণ করে।

ERM "ML-এর সমীকরণ"। Loss function আলাদা (L13 — cross-entropy), $\mathcal{H}$ আলাদা (L19 — tree, L27 — SVM), optimization আলাদা (L11 — gradient descent) — কিন্তু চিন্তার কাঠামো একই। এই formalism মাথায় রাখলে যেকোনো নতুন algorithm দ্রুত বুঝবেন।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ "যদি আমরা সব training data-এ ০ ভুল পাই, তাহলে কি best মডেল পেলাম?" — এই দাবির ভুল কোথায়? Vapnik কেন বলেছিলেন "do not solve a more general problem as an intermediate step"?

এটি ML-এর সবচেয়ে সাধারণ ভুল ধারণা — এবং Vapnik-এর গভীর insight।

মূল ভুল:

Training-এ ০ loss = empirical risk minimum — কিন্তু আমরা true risk চাই।
একটি sufficiently flexible $\mathcal{H}$ — যেমন nearest neighbor — সবসময় training-এ ০ loss পেতে পারে।
কিন্তু সেটা মুখস্থ — শেখা নয়। নতুন ডেটায় random এর মতো performance।

Vapnik-এর insight:

আমরা চাই — generalization ভাল করুক এমন function।
"Density estimation" বা "input distribution learning" আগে করা — তারপর classification — অপ্রয়োজনীয় কাজ।
Direct goal — boundary শেখা (classification-এ), value predict (regression-এ)।
"Unnecessary general problem" = অতিরিক্ত complexity = অতিরিক্ত variance।

SVM-এর উৎস:

Vapnik এই philosophy থেকে SVM তৈরি — শুধু "support vectors"-এর জন্য optimization।
সব training points fit করার চেষ্টা না — শুধু margin তৈরির জন্য critical points।
L27-৩০-এ এর গভীর তত্ত্ব।

আধুনিক প্রতিধ্বনি:

Deep Learning-এ "double descent" — অনেক বেশি parameters সত্ত্বেও generalization আসে।
Belkin et al. (২০১৯) দেখাল — overparameterization-এ implicit regularization কাজ করে।
Vapnik-এর classical theory-এর modern rethinking চলছে।

মূল উপলব্ধি: Training error ০ — আদর্শ নয়, বিপদসংকেত। True objective generalization — যা আমরা সরাসরি মাপতে পারি না, কিন্তু validation set ব্যবহার করে অনুমান করি (L03)।

প্র ০২ একই ডেটাসেটে দু'জন ML engineer কাজ করছেন — একজন linear hypothesis class বেছেছেন, অন্যজন depth-১০ decision tree। কোনটা "ভাল"? — উত্তর কেন "depends on data" — এবং কোন factors-এ?

ML-এ "best model" বলে কিছু নেই — শুধু "best for this data and this constraint"। হাইপোথিসিস ক্লাস বাছাই = ডেটার সাথে match করা।

Linear-এর সুবিধা:

Low variance: সামান্য parameter — ছোট ডেটায়ও stable।
Interpretable: coefficient সরাসরি বলে — কোন feature কত প্রভাব।
Fast: training ও inference দু'টোই দ্রুত।
Mathematically tractable: closed-form solution থাকে (L10)।

Depth-১০ tree-এর সুবিধা:

Non-linear: জটিল pattern ধরতে পারে — feature interactions automatic।
Mixed types: categorical ও numerical handle করতে পারে।
No scaling needed: feature normalization বাধ্যতামূলক না।
Handles missing values gracefully।

কোনটি ভাল — কোন factors-এ?

ডেটার পরিমাণ: ১০০ rows — linear। ১০K+ rows — tree বা ensemble।
Feature সংখ্যা: ৫-১০ feature ও linear relationship — linear। ৫০+ feature ও interaction expected — tree।
সম্পর্কের প্রকৃতি: y = 2x+3 — linear। y = if(x>5) then... — tree।
Interpretability requirement: healthcare, banking — linear preferred (regulatory)।
Noise level: বেশি noise — linear (low variance)।
Extrapolation: training range-এর বাইরে predict করা — linear ভাল (tree constant)।

প্র্যাক্টিকাল কৌশল:

সবসময় linear baseline — quick reality check।
তারপর tree — কত improvement।
৫-১০% improvement = সম্ভবত complexity worth it।
< ২% improvement = linear-এ থাকুন।

মূল উপলব্ধি: Hypothesis class-এর "ভাল-মন্দ" ডেটার সাথে যৌথ। "No Free Lunch theorem" (Wolpert ১৯৯৬) প্রমাণ করে — সব problem-এ best algorithm বলে কিছু নেই।

প্র ০৩ "Approximation error, Estimation error, Optimization error" — এই তিনটি কীভাবে কমাবেন? কোনটা কমাতে গিয়ে কোনটা বাড়তে পারে?

এই decomposition বুঝলে — যেকোনো ML system debug করতে পারবেন। প্রতিটি error-এর আলাদা remedy ও tradeoff।

(১) Approximation error কমানো:

সমস্যা: $\mathcal{H}$ যথেষ্ট rich না — true function ধরতে পারে না।
সমাধান:
- Larger model (linear → polynomial → NN)।
- Feature engineering (L08) — input space-কে rich করা।
- Kernel methods (L29) — implicit nonlinearity।
- Deep learning — hierarchical representation।
Tradeoff: Larger $\mathcal{H}$ → estimation error বাড়ে → বেশি ডেটা লাগে।

(২) Estimation error কমানো:

সমস্যা: ডেটা ছোট/noisy — empirical optimum true থেকে দূরে।
সমাধান:
- আরও ডেটা — সবসময় #1।
- Regularization (L15) — implicit smaller $\mathcal{H}$।
- Data augmentation।
- Cross-validation (L05) — robust estimation।
- Ensemble (L21) — variance reduction।
Tradeoff: Strong regularization → approximation error বাড়ে।

(৩) Optimization error কমানো:

সমস্যা: Algorithm সঠিক minimum পৌঁছায় না।
সমাধান:
- Better optimizer (Adam, L-BFGS)।
- Better learning rate schedule।
- Better initialization।
- আরো epochs।
- Convex formulation (যেখানে সম্ভব)।
Tradeoff: Strong optimization + complex $\mathcal{H}$ → overfitting দ্রুত আসে।

একটি লুকানো paradox:

Deep learning-এ — optimization "imperfect" থাকা সাহায্য করে! SGD-এর noise = implicit regularization।
Perfect optimization = perfect training fit = overfitting।
"Stop training early" (early stopping) — তাই কাজ করে।

Practical decomposition:

Train accuracy < Target = approximation বা optimization issue।
Train high, validation low = estimation issue (overfitting)।
Train fluctuates wildly = optimization issue।

মূল উপলব্ধি: Error decomposition একটি diagnostic tool। কোন error dominate করছে — সেটা চিনলে exact intervention জানা যায়।

প্র ০৪ একটি গভীর প্রশ্ন: "যদি $\mathcal{H}$ infinite (যেমন সব continuous function), Hoeffding bound কি কাজ করে? VC dimension কেন আবিষ্কার?"

এটি statistical learning theory-র heart। উত্তর — না, এবং এই কারণেই Vapnik-Chervonenkis dimension আবিষ্কার।

সমস্যা:

আমাদের bound: $|R - \hat{R}| \leq \sqrt{\frac{\log(2|\mathcal{H}|/\delta)}{2n}}$
$|\mathcal{H}| = \infty$ হলে — bound vacuous (অসীম)।
কিন্তু linear function-এর hypothesis class infinite — এবং কাজ করে। তাই bound অপর্যাপ্ত।

মূল insight:

Important — কতগুলো function বা না, বরং তারা training data-এ "কতগুলো ভিন্ন behavior" দেখাতে পারে।
$n$টি point-এ infinite function থাকতে পারে কিন্তু labeling মাত্র $2^n$।
আসলে অনেক কম — কারণ class restricted।

VC Dimension (১৯৭১):

Definition: $\mathcal{H}$ সর্বোচ্চ কতগুলো point "shatter" করতে পারে — মানে সব $2^n$ labeling realize করতে পারে।
২-D linear classifier — VC dim = ৩।
Polynomial degree-$d$ — VC dim ≈ $d+1$।
Decision tree depth-$d$ — VC dim ≈ $2^d$।
Neural network — VC dim জটিল, parameter সংখ্যার সাথে scale।

VC Bound:

$$|R(f) - \hat{R}(f)| \leq O\left(\sqrt{\frac{\text{VC}(\mathcal{H}) \cdot \log n}{n}}\right)$$

$|\mathcal{H}|$-এর জায়গায় VC dim — finite hypothesis class-এও infinite।
"Effective complexity" পরিমাপ।

আধুনিক বিকল্প:

Rademacher complexity: data-dependent measure — ভাল bound।
PAC-Bayes: Bayesian framework — modern bound।
NTK theory: infinite-width neural network — kernel পদ্ধতিতে analyze।

Deep Learning paradox:

আধুনিক NN-এর VC dim — billions।
Classical theory predicts disastrous overfitting।
বাস্তবে — generalize করে।
"Rethinking generalization" (Zhang et al. ২০১৭) — এই paradox-এর famous paper।
উত্তর এখনো গবেষণায় — implicit bias of SGD, lottery ticket, etc.।

মূল উপলব্ধি: ML theory আবিষ্কার, অপরিবর্তিত নয়। Classical bounds practical insight দেয়, কিন্তু DL যুগের পুরো ব্যাখ্যা এখনো অসমাপ্ত গবেষণা।

অনুশীলন

হিসাব করুন: Training set $\{(1, 2), (2, 4), (3, 5)\}$ ও model $f(x) = 1.5x$. Empirical risk (squared loss) কত?
- $f(1) = 1.5$, error = $(1.5 - 2)^2 = 0.25$
- $f(2) = 3$, error = $(3 - 4)^2 = 1$
- $f(3) = 4.5$, error = $(4.5 - 5)^2 = 0.25$
- $\hat{R} = (0.25 + 1 + 0.25)/3 = 0.5$
NumPy চেষ্টা: উপরের ERM grid search চালান। ws ও bs-এর resolution বাড়ালে (১০০ → ২০০) কী হয়? Grid বাড়ানোর সুবিধা ও খরচ?

সুবিধা: অধিক exact solution — true (2, 1)-এর কাছে।

খরচ: Computation $O(n^2)$ — ২০০×২০০ = ৪০K evaluation। L11-এ gradient descent এই inefficiency-র সমাধান।
চিন্তা: একটি hypothesis class বাছার আগে কোন ৩টি প্রশ্ন করবেন? (এই পাঠের প্র ০২ কনসেপ্ট থেকে)
- (১) আমার কত ডেটা — ছোট ডেটায় simple class।
- (২) Feature ও label-এর সম্পর্ক কেমন — linear না non-linear?
- (৩) Interpretability দরকার কি — banking/healthcare হলে preferred।