শেখার তত্ত্ব — ERM, generalisation gap, PAC আর VC-এর অন্তর্দৃষ্টি

AI-এর ভিত্তি কোর্সের পর্ব ৫৫-এ hypothesis space, inductive bias আর generalisation-এর ধারণা এসেছিল, পর্ব ৫৬-এ train/validation/test ভাগ, আর পর্ব ৬১-এ bias–variance. এই পর্বের প্রশ্ন: হাতের n-টি উদাহরণে ভালো করা একটি model নতুন ডেটায়ও ভালো করবে, এ কথা কতটা নিশ্চয়তায় বলা যায়, আর তার জন্য কত ডেটা লাগে? চালানো যায় এমন চারটি ব্লক পাতাতেই চলে (ব্রাউজারের Python, NumPy আর SciPy); প্রথমবার প্যাকেজ নামতে কয়েক সেকেন্ড লাগে।

১ · True risk আর empirical risk — আসল ভুল বনাম খাতায় গোনা ভুল

প্রতিটি উদাহরণ একটি জোড়া (x, y): x হলো feature (এখানে অর্ডারের দূরত্ব, km-এ), y হলো label (দেরি হলে ১, না হলে ০)। জোড়াগুলো আসে একটি অজানা distribution D থেকে, অর্থাৎ কোন দূরত্বের অর্ডার কত ঘন ঘন আসে আর কোনটিতে দেরি হয়, তার পুরো সম্ভাবনার ছবি। একটি hypothesis h হলো x থেকে অনুমান দেওয়ার একটি নিয়ম, যেমন “১০ km-এর বেশি হলে দেরি”। সব সম্ভাব্য h-এর যে সংগ্রহ থেকে algorithm বাছাই করতে পারে, সেটি hypothesis class H. প্রতিটি অনুমানের দাম মাপে একটি loss ℓ; classification-এ সবচেয়ে সরলটি 0-1 loss: অনুমান ভুল হলে ১, ঠিক হলে ০.

R(h) = E_(x,y)∼D[ ℓ(h(x), y) ] = P_D( h(x) ≠ y )

R̂_S(h) = (1/n) · ∑_i=1..n ℓ(h(x_i), y_i)

প্রথম লাইনটি true risk: D থেকে নতুন একটি (x, y) টানলে h ভুল করার সম্ভাবনা। E মানে প্রত্যাশিত মান বা গড় (expected value), “∼D” মানে “D থেকে টানা”। দ্বিতীয় লাইনটি empirical risk: হাতের sample S = {(x₁, y₁), …, (x_n, y_n)}-এ ভুলের ভগ্নাংশ। দুটির পার্থক্য R(h) − R̂_S(h)-কে বলে generalisation gap. নীরব শর্ত: S-এর উদাহরণগুলো i.i.d., অর্থাৎ একে অপরের থেকে স্বাধীন আর সবাই একই D থেকে টানা। ঈদের মৌসুমের অর্ডার দিয়ে শেখা model সাধারণ মাসে চালালে এই শর্ত ভাঙে; সে প্রসঙ্গ পর্ব ৫৯ (Distribution shift)-এ।

বাস্তবে D কেউ জানে না। শেখার জন্য আমরা এখানে একটি জানা, পুরোপুরি কাল্পনিক D বানাই, যাতে true risk হুবহু হিসাব করে empirical risk-এর সঙ্গে মেলানো যায়: বাজারঘরের অর্ডারের দূরত্ব x সমানভাবে ০ থেকে ২০ km-এর মধ্যে ছড়ানো (uniform), “আসল” নিয়মে ১২ km-এর বেশি হলে দেরি হয়, কিন্তু রাস্তার অপ্রত্যাশিত ঘটনায় ১০% অর্ডারের label উল্টে যায় (η = ০.১, যাকে label noise বলে)। এই noise-এর কারণে কোনো নিয়মই ১০%-এর কম ভুল করতে পারে না; এই সর্বনিম্ন সম্ভাব্য ভুলের নাম Bayes error.

একটি নির্দিষ্ট h-এর জন্য R̂_S(h) হলো n-টি স্বাধীন ০/১ সংখ্যার গড়, প্রতিটি সম্ভাবনা R(h) নিয়ে ১. তাই ভুলের মোট সংখ্যা Binomial(n, R(h)), গড়ে R̂ ঠিক R(h)-এর সমান (একে বলে unbiased), আর standard deviation √(R(1−R)/n). বৃহৎ সংখ্যার নিয়ম অনুযায়ী n বাড়লে R̂ ক্রমে R-এর কাছে যায়। Binomial আর এই নিয়ম AI-এর ভিত্তি কোর্সের পর্ব ৩৬ আর পর্ব ৩৭-এ আছে। নিচের ব্লক একটি sample-এর চলমান empirical risk আঁকে, আর তারপর প্রতিটি n-এ ২০,০০০টি নতুন sample নিয়ে দেখে ফাঁক কতবার ০.০৫ ছাড়ায়। দ্বিতীয় অংশে দ্রুততার জন্য সরাসরি Binomial থেকে ভুলের সংখ্যা টানা হয়েছে; নির্দিষ্ট h-এ দুটি একই জিনিস।

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(42)
ETA, CUT, T = 0.10, 12.0, 10.0     # লেবেলের গোলমাল, আসল সীমা (km), আমাদের নিয়ম (km)

def sample(n):                      # কাল্পনিক বাজারঘর: দূরত্ব 0-20 km, দেরি হলে y = 1
    x = rng.uniform(0, 20, n)
    y = (x > CUT).astype(int)
    flip = rng.random(n) < ETA      # 10% লেবেল উল্টে যায়
    return x, np.where(flip, 1 - y, y)

R = ETA + (1 - 2 * ETA) * abs(T - CUT) / 20     # আসল risk, ঠিক হিসাব
print(f"true risk R(h) = {R:.3f}")

x, y = sample(10_000)
running = np.cumsum((x > T).astype(int) != y) / np.arange(1, 10_001)
for n in (10, 100, 1000, 10_000):
    print(f"n={n:>6}: empirical risk {running[n-1]:.4f}, |gap| {abs(running[n-1] - R):.4f}")

eps = 0.05                          # বারবার নতুন sample: ভুলের সংখ্যা ~ Binomial(n, R)
for n in (10, 100, 300, 1000):
    Rhat = rng.binomial(n, R, 20_000) / n
    p = np.mean(np.abs(Rhat - R) >= eps - 1e-9)
    print(f"n={n:>5}: sd {Rhat.std():.4f} | P(|gap| >= {eps}) {p:.4f}"
          f" | Hoeffding <= {min(1, 2 * np.exp(-2 * n * eps**2)):.4f}")

ns = np.arange(1, 10_001); band = np.sqrt(np.log(2 / 0.05) / (2 * ns))   # 95% Hoeffding
plt.figure(figsize=(6.4, 3.4), layout="constrained")
plt.fill_between(ns, R - band, R + band, color="C0", alpha=0.15, label="Hoeffding 95% band")
plt.semilogx(ns, running, "C0", lw=1, label="empirical risk (one sample)")
plt.axhline(R, color="k", ls="--", lw=1, label="true risk 0.18")
plt.ylim(0, 0.5); plt.xlabel("number of orders n"); plt.ylabel("error rate")
plt.title("Empirical risk settles on the true risk"); plt.legend(fontsize=8)
plt.show()

true risk R(h) = 0.180
n=    10: empirical risk 0.1000, |gap| 0.0800
n=   100: empirical risk 0.1500, |gap| 0.0300
n=  1000: empirical risk 0.1730, |gap| 0.0070
n= 10000: empirical risk 0.1785, |gap| 0.0015
n=   10: sd 0.1215 | P(|gap| >= 0.05) 0.7012 | Hoeffding <= 1.0000
n=  100: sd 0.0384 | P(|gap| >= 0.05) 0.2391 | Hoeffding <= 1.0000
n=  300: sd 0.0220 | P(|gap| >= 0.05) 0.0271 | Hoeffding <= 0.4463
n= 1000: sd 0.0121 | P(|gap| >= 0.05) 0.0001 | Hoeffding <= 0.0135

২ · Hoeffding-এর অসমতা — আগে থেকে ঠিক করা একটি নিয়ম কতটা ভরসার

১৯৬৩ সালে পরিসংখ্যানবিদ Wassily Hoeffding (Journal of the American Statistical Association-এ) দেখান, সীমাবদ্ধ স্বাধীন random variable-এর গড় তার প্রত্যাশিত মান থেকে কতটা দূরে যেতে পারে, তার সম্ভাবনা n বাড়লে সূচকীয় হারে কমে। এমন ফলকে বলে concentration inequality. Learning theory-র ভাষায়:

P( |R̂_S(h) − R(h)| ≥ ε ) ≤ 2 · exp(−2nε²)

এখানে ε (epsilon) হলো সহনীয় ফাঁক, n উদাহরণের সংখ্যা, exp(a) মানে e^a. শর্ত: loss ০ থেকে ১-এর মধ্যে (0-1 loss তাই), উদাহরণগুলো i.i.d., আর h ডেটা দেখার আগে ঠিক করা। ডানদিকটি δ (delta, মেনে নেওয়া ব্যর্থতার সম্ভাবনা) ধরে ε-এর জন্য সমাধান করলে, অন্তত ১ − δ সম্ভাবনায়

|R̂_S(h) − R(h)| ≤ √( ln(2/δ) / (2n) )

একটি পূর্ণ numerical. বাজারঘরের data দল একটি test set-এ ১,০০০টি অর্ডারে model-এর ভুল মাপল ১২.৪%. ৯৫% নিশ্চয়তায় (δ = ০.০৫) আসল ভুল কোথায়? ln(2/0.05) = ln 40 = 3.689; ভাগ 2 × 1000 = 2000; 3.689 / 2000 = 0.001844; বর্গমূল 0.0429. তাই আসল ভুল ১২.৪% ± ৪.৩%, অর্থাৎ ৮.১% থেকে ১৬.৭%-এর মধ্যে, যদি test set সত্যিই অছোঁয়া থাকে। ফাঁক ±২%-এ নামাতে চাইলে n ≥ ln 40 / (2 × 0.02²) = ৪,৬১১.১, তাই ৪,৬১২টি অর্ডার লাগবে। n বাড়ে 1/ε² হারে।

৩ · Empirical risk minimisation আর generalisation gap — বাছাই করলেই আশাবাদ

বাস্তবে আমরা h আগে থেকে ঠিক করি না; ডেটা দেখে শিখি। সবচেয়ে সরল ও মৌলিক শেখার নিয়ম হলো empirical risk minimisation (ERM): H-এর সব নিয়মের মধ্যে train ডেটায় সবচেয়ে কম ভুল যার, সেটিকে বেছে নেওয়া।

ĥ = argmin_{h ∈ H} R̂_S(h)

argmin মানে “যে h-এ মানটি সবচেয়ে ছোট”। MSE বা log loss কমানো, সবই ERM-এর রূপ (কখনো সঙ্গে regularization শাস্তি)। এখন প্রশ্ন: ĥ-এর train ভুল R̂_S(ĥ) কি তার আসল ভুলের ভালো আন্দাজ? উত্তর: না, সাধারণত কম দেখায়। S-এর এলোমেলো সৌভাগ্য যার পক্ষে গেছে, তাকেই বাছা হয়েছে।

ERM ঠিক সেই জায়গা বাছে যেখানে noise সবচেয়ে বেশি সাহায্য করেছে; আর সমান train ভুলের একাধিক t থাকলে কোনটি নেওয়া হবে, সেটিও একটি সিদ্ধান্ত (tie-breaking). এবার গড় দেখি। নিচের ব্লকের প্রথম অংশে H হলো ০ থেকে ২০-এর মধ্যে সমান দূরত্বের কয়েকটি threshold; |H| = ৩, ১১, ২০১ বা ১,০০১. প্রতিটি (|H|, n)-এ ৪০০ বার নতুন sample আর ERM. দ্বিতীয় অংশে চরম একটি H: M-টি কয়েন-ছোড়া নিয়ম, প্রত্যেকের আসল risk ঠিক ০.৫, ভুলের সংখ্যা সরাসরি Binomial(100, 0.5) থেকে।

import numpy as np

rng = np.random.default_rng(42)
ETA, CUT, REPS = 0.10, 12.0, 400
true_risk = lambda t: ETA + (1 - 2 * ETA) * np.abs(t - CUT) / 20

def sample(n):                      # একই কাল্পনিক ডেটা: দূরত্ব, দেরি = 1
    x = rng.uniform(0, 20, n)
    y = (x > CUT).astype(int)
    return x, np.where(rng.random(n) < ETA, 1 - y, y)

def emp_risk(x, y, grid):           # সব threshold-এর empirical risk একবারে
    xs, ys = x[np.argsort(x)], y[np.argsort(x)]
    ones = np.concatenate([[0], np.cumsum(ys)])
    k = np.searchsorted(xs, grid, side="right")      # কতটি x <= t
    return (ones[k] + (len(x) - k) - (ones[-1] - ones[k])) / len(x)

print("A) thresholds, mean of 400 runs: R(h_erm) / gap")
for size in (3, 11, 201, 1001):
    grid = np.linspace(0, 20, size)                  # H = সমান দূরত্বের threshold
    cells = []
    for n in (20, 100, 500):
        res = []
        for _ in range(REPS):
            e = emp_risk(*sample(n), grid)
            j = np.argmin(e)                         # ERM: train-এ সবচেয়ে কম ভুল
            res.append((true_risk(grid[j]), true_risk(grid[j]) - e[j]))
        cells.append("{:.3f}/{:.3f}".format(*np.mean(res, axis=0)))
    print(f"|H|={size:<5} best {true_risk(grid).min():.2f} | n=20 {cells[0]}"
          f"  n=100 {cells[1]}  n=500 {cells[2]}")
print("B) M coin-flip rules (true risk 0.5 each), n = 100")
for M in (1, 10, 100, 1000, 10_000):
    best = rng.binomial(100, 0.5, (200, M)).min(axis=1) / 100
    print(f"M={M:>6}: train error of ERM pick {best.mean():.3f}"
          f" | gap {0.5 - best.mean():.3f} | sqrt(ln M/2n) {np.sqrt(np.log(M) / 200):.3f}")

A) thresholds, mean of 400 runs: R(h_erm) / gap
|H|=3     best 0.18 | n=20 0.192/0.020  n=100 0.180/-0.001  n=500 0.180/-0.001
|H|=11    best 0.10 | n=20 0.130/0.038  n=100 0.100/-0.001  n=500 0.100/0.000
|H|=201   best 0.10 | n=20 0.151/0.065  n=100 0.110/0.013  n=500 0.101/0.002
|H|=1001  best 0.10 | n=20 0.156/0.064  n=100 0.110/0.013  n=500 0.102/0.001
B) M coin-flip rules (true risk 0.5 each), n = 100
M=     1: train error of ERM pick 0.499 | gap 0.001 | sqrt(ln M/2n) 0.000
M=    10: train error of ERM pick 0.427 | gap 0.073 | sqrt(ln M/2n) 0.107
M=   100: train error of ERM pick 0.373 | gap 0.127 | sqrt(ln M/2n) 0.152
M=  1000: train error of ERM pick 0.341 | gap 0.159 | sqrt(ln M/2n) 0.186
M= 10000: train error of ERM pick 0.311 | gap 0.189 | sqrt(ln M/2n) 0.215

এই ফলকে একটি সূত্রে লেখা যায়। ধরুন H-এর সেরা নিয়ম h* (যার R সবচেয়ে কম), আর R* হলো Bayes error (এখানে ০.১০). তাহলে ERM-এর বাড়তি ভুল দুই ভাগে ভাঙে:

R(ĥ) − R* = [ R(h*) − R* ] + [ R(ĥ) − R(h*) ]

মোট বাড়তি ভুল = approximation error + estimation error

প্রথম বন্ধনী approximation error: H-এর ভেতরের সেরাটিও কতটা খারাপ; শুধু H-এর ওপর নির্ভর করে, ডেটার ওপর নয় (|H| = ৩-এ ০.০৮, ১১-এ ০)। দ্বিতীয় বন্ধনী estimation error: সীমিত ডেটার কারণে সেরাটি খুঁজে না পাওয়ার দাম; n বাড়লে কমে, H বড় হলে বাড়ে। AI-এর ভিত্তি কোর্সের পর্ব ৬১-এর bias আর variance-এর সঙ্গে এদের মিল আছে, কিন্তু হুবহু এক নয়: সেটি squared loss-এ একটি বিন্দুতে গড়ের ভাঙন, এটি যেকোনো loss-এ পুরো class-এর ভাঙন।

৪ · Union bound আর সসীম class-এর PAC bound

ERM-এর সমস্যা ছিল: কোন h বাছাই হবে, তা আগে জানি না। সমাধান: H-এর প্রতিটি h-কে একসঙ্গে পাহারা দেওয়া। যদি এক সঙ্গে সব h-এর empirical risk আসলের ε-এর মধ্যে থাকে (একে বলে uniform convergence), তাহলে ERM যেটিই বাছুক, সেটিও ε-এর মধ্যে। হাতিয়ার union bound: কয়েকটি ঘটনার অন্তত একটি ঘটার সম্ভাবনা আলাদা সম্ভাবনাগুলোর যোগফলের বেশি নয়।

P(A₁ ∪ A₂ ∪ … ∪ A_k) ≤ P(A₁) + P(A₂) + … + P(A_k)

এখানে A_j = “j-তম নিয়মের empirical risk আসল থেকে ε বা তার বেশি দূরে” (খারাপ ঘটনা), আর ∪ মানে “অথবা” (union). নিচের stepper পাঁচটি threshold নিয়ে যোগফলটি ধাপে ধাপে গড়ে।

শেষ ধাপের হিসাবটিই সাধারণ রূপে লিখলে পাই এই পর্বের কেন্দ্রীয় উপপাদ্য। |H|-টি নিয়ম, প্রতিটির ব্যর্থতা সর্বোচ্চ 2e^−2nε²; মোট |H| · 2e^−2nε² ≤ δ চাইলে:

এখান থেকে ERM-এর নিশ্চয়তা তিন লাইনে আসে। h* হলো H-এর সেরা নিয়ম। Uniform convergence ঘটলে: R(ĥ) ≤ R̂_S(ĥ) + ε (ĥ-ও H-এর সদস্য) ≤ R̂_S(h*) + ε (ERM train-এ সবচেয়ে কম বাছে) ≤ R(h*) + 2ε (h*-ও H-এর সদস্য)। অর্থাৎ অন্তত ১ − δ সম্ভাবনায় ERM-এর আসল ভুল H-এর সেরার চেয়ে 2ε-এর বেশি খারাপ নয়। বাড়তি ভুল ε′-এর মধ্যে চাইলে তাই ε = ε′/2 বসাতে হয়, যা n-কে চারগুণ করে। এখানে agnostic মানে আমরা ধরে নিইনি যে H-এ নিখুঁত নিয়ম আছে; noise থাকলে কোনোটিই নিখুঁত নয়।

Stepper-এর simulation সংখ্যাগুলো এই ছোট স্ক্রিপ্টের সত্যিকারের run থেকে (ডেস্কটপ, Python 3.14.4, NumPy 2.5.4; একটি local run):

~/bazarghar-ml$ python union_check.py
true risks: [0.42 0.26 0.1  0.26 0.42]
n=200: P(bad) each h = [0.0048 0.0017 0.0001 0.0016 0.005 ]
       P(any h bad) = 0.0121   union bound = 0.1832
n=265: P(bad) each h = [0.0011 0.0002 0.     0.0001 0.0009]
       P(any h bad) = 0.0022   union bound = 0.0499

আলাদা ব্যর্থতাও ০.০৩৬৬-এর অনেক নিচে, কারণ Hoeffding সবচেয়ে খারাপ ক্ষেত্র R = ০.৫ ধরে নেয়।

PAC — “সম্ভবত প্রায় সঠিক”

১৯৮৪ সালে Leslie Valiant Communications of the ACM-এ “A Theory of the Learnable” প্রবন্ধে শেখার একটি সংজ্ঞা দেন, যা পরে PAC learning (Probably Approximately Correct) নামে পরিচিত হয়। মোটামুটি: একটি class H শেখা যায়, যদি এমন একটি algorithm থাকে যে যেকোনো ε, δ আর যেকোনো D-এর জন্য, যথেষ্ট n (যা ১/ε, ১/δ-এ বহুপদী হারে বাড়ে) উদাহরণ পেলে, অন্তত ১ − δ সম্ভাবনায় (“probably”) এমন h দেয় যার ভুল ε-এর মধ্যে (“approximately correct”). প্রয়োজনীয় ন্যূনতম n-কে বলে sample complexity. সংজ্ঞার খুঁটিনাটি বই ভেদে একটু আলাদা; এখানে মূল ভাবটুকু।

দুটি পরিস্থিতি আলাদা করা দরকার। Realizable ক্ষেত্রে ধরে নেওয়া হয় H-এর কোনো নিয়মের ভুল শূন্য (noise নেই)। তখন যুক্তি সহজ: R(h) > ε এমন একটি “খারাপ” h n-টি উদাহরণের সবগুলোতে ঠিক হওয়ার সম্ভাবনা সর্বোচ্চ (1 − ε)ⁿ ≤ e^−εn; union bound দিয়ে |H| e^−εn ≤ δ, অর্থাৎ n ≥ (ln|H| + ln(1/δ)) / ε. লক্ষ করুন, এখানে ε-এর বর্গ নেই। |H| = ১,০০০, ε = δ = ০.০৫ হলে realizable-এ (6.908 + 2.996) / 0.05 = ১৯৮.১ → ১৯৯, আর agnostic সূত্রে ২,১২০: noise থাকলে প্রায় এগারো গুণ ডেটা।

৫ · কত ডেটা লাগবে — sample-size calculator আর simulation দিয়ে যাচাই

সূত্রটি দিয়ে একটি ছোট calculator, তারপর যাচাই: bound-এর n-এ কি সত্যিই সব নিয়ম একসঙ্গে ε-এর মধ্যে থাকে, আর আসলে কত কম ডেটায় চলে? যাচাইয়ের জন্য H = ২০১টি threshold (০.১ km পরপর), ε = δ = ০.০৫, প্রতিটি n-এ ১,০০০ বার নতুন sample, আর প্রতিবার সব ২০১টি নিয়মের মধ্যে সবচেয়ে বড় |R̂ − R|.

import math
import numpy as np

def n_needed(H, eps, delta):        # Hoeffding + union bound, সসীম H
    return math.ceil((math.log(H) + math.log(2 / delta)) / (2 * eps**2))

print("  eps  delta |   |H|=10  |H|=1000  |H|=10^6")
for eps in (0.1, 0.05, 0.01):
    for delta in (0.05, 0.01):
        row = [n_needed(H, eps, delta) for H in (10, 1000, 10**6)]
        print(f"{eps:5} {delta:6} | " + " ".join(f"{v:>9,}" for v in row))

rng = np.random.default_rng(42)     # যাচাই: |H| = 201 threshold, eps = delta = 0.05
ETA, CUT, EPS = 0.10, 12.0, 0.05
grid = np.linspace(0, 20, 201)
R = ETA + (1 - 2 * ETA) * np.abs(grid - CUT) / 20
def worst_dev(n):                   # সব h-এর মধ্যে সবচেয়ে বড় |Rhat - R|
    x = rng.uniform(0, 20, n); y = (x > CUT).astype(int)
    y = np.where(rng.random(n) < ETA, 1 - y, y)
    xs, ys = x[np.argsort(x)], y[np.argsort(x)]
    ones = np.concatenate([[0], np.cumsum(ys)])
    k = np.searchsorted(xs, grid, side="right")
    Rhat = (ones[k] + (n - k) - (ones[-1] - ones[k])) / n
    return np.max(np.abs(Rhat - R))

print("bound says n >=", n_needed(201, EPS, 0.05))
for n in (100, 200, 400, 800, n_needed(201, EPS, 0.05)):
    devs = np.array([worst_dev(n) for _ in range(1000)])
    print(f"n={n:>5}: P(some h off by >= {EPS}) = {np.mean(devs >= EPS):.3f}")

  eps  delta |   |H|=10  |H|=1000  |H|=10^6
  0.1   0.05 |       300       530       876
  0.1   0.01 |       381       611       956
 0.05   0.05 |     1,199     2,120     3,501
 0.05   0.01 |     1,521     2,442     3,823
 0.01   0.05 |    29,958    52,984    87,522
 0.01   0.01 |    38,005    61,031    95,570
bound says n >= 1799
n=  100: P(some h off by >= 0.05) = 0.955
n=  200: P(some h off by >= 0.05) = 0.685
n=  400: P(some h off by >= 0.05) = 0.278
n=  800: P(some h off by >= 0.05) = 0.036
n= 1799: P(some h off by >= 0.05) = 0.000

৬ · অসীম class আর VC dimension — shattering-এর ছবি

সব threshold নিলে, অর্থাৎ যেকোনো বাস্তব সংখ্যা t, H অসীম, আর ln|H| = ∞. কিন্তু অংশ ৩-এ ২০১ আর ১,০০১টি threshold-এ প্রায় একই gap এসেছিল। কারণ n-টি বিন্দুতে t কোন দুটি বিন্দুর মাঝে পড়ছে, শুধু তাতেই অনুমান বদলায়, তাই সর্বোচ্চ n + ১ রকম labeling সম্ভব। ডেটার চোখে H-এর কার্যকর আকার হলো n-টি বিন্দুতে সে কত রকম labeling বানাতে পারে। এই সংখ্যাকে বলে growth function.

এই ধারণার সবচেয়ে পরিচিত মাপ VC dimension, Vladimir Vapnik আর Alexey Chervonenkis-এর নামে। মূল কাজটি ১৯৭১ সালের একটি প্রবন্ধে (রুশ থেকে ইংরেজি অনুবাদে) পরিচিতি পায়, যদিও এর সূচনা ১৯৬০-এর দশকের শেষে। সংজ্ঞাটি দুই ধাপে:

• Shattering: m-টি বিন্দুর একটি সেটকে H “shatter” করে, যদি ওই বিন্দুগুলোর 2^m-টি সম্ভাব্য +/− labeling-এর প্রতিটির জন্য H-এ এমন একটি h থাকে যা ঠিক সেই labeling দেয়।
• VC dimension: সবচেয়ে বড় m, যার জন্য অন্তত একটি m-বিন্দুর সেট আছে যা H shatter করে।

এক মাত্রায় threshold-এর VC dimension ১: একটি বিন্দুকে + বা − দুটোই বানানো যায়, কিন্তু দুটি বিন্দু a < b-তে “a-তে +, b-তে −” কোনো x > t নিয়ম দিতে পারে না। দুই মাত্রায় সরলরেখা দিয়ে ভাগ, অর্থাৎ linear classifier h(x) = sign(w · x + b), কতগুলো বিন্দু shatter করতে পারে?

চারটি বিন্দু কেন পারে না? সবচেয়ে বিখ্যাত উদাহরণ XOR: একটি বর্গের চার কোণ, কর্ণের দুই প্রান্তে একই label. কোনো রেখাই দুই কর্ণকে আলাদা করতে পারে না। কিন্তু VC dimension ৩ প্রমাণ করতে দেখাতে হয় যে যেকোনো চারটি বিন্দুতেই অন্তত একটি labeling অসম্ভব। দুটি ক্ষেত্র: চারটি বিন্দু উত্তল অবস্থানে (চতুর্ভুজ) থাকলে কর্ণের জোড়া দুটিকে আলাদা করা যায় না; আর একটি বিন্দু বাকি তিনটির ত্রিভুজের ভেতরে থাকলে “ভেতরেরটি +, বাকিরা −” অসম্ভব। এর সাধারণ রূপ Radon-এর উপপাদ্য (১৯২১): d মাত্রায় যেকোনো d + ২টি বিন্দুকে এমন দুই দলে ভাগ করা যায় যাদের উত্তল আবরণ পরস্পরকে ছেদ করে, তাই তাদের কোনো hyperplane আলাদা করতে পারে না।

ছবিতে চোখে দেখা দাবি এবার কোড দিয়ে যাচাই করি। একটি labeling রেখা দিয়ে আলাদা করা যায় কি না, তা একটি linear programming (LP) প্রশ্ন: এমন w₁, w₂, b আছে কি, যাতে প্রতিটি বিন্দুতে y_i(w · x_i + b) ≥ ১? (w আর b-কে ধনাত্মক সংখ্যায় গুণ করা যায় বলে ≥ ১ লেখায় ক্ষতি নেই।) SciPy-র linprog বলে দেয় সমাধান আছে কি না। ব্লকটি পাঁচটি বিন্যাসের সব labeling পরীক্ষা করে।

import itertools
import numpy as np
from scipy.optimize import linprog

def separable(X, y):                # w·x + b দিয়ে কি y (+1/−1) আলাদা করা যায়?
    A = -y[:, None] * np.column_stack([X, np.ones(len(X))])
    res = linprog(np.zeros(3), A_ub=A, b_ub=-np.ones(len(X)),
                  bounds=[(None, None)] * 3, method="highs")
    return res.status == 0          # 0 = সমাধান আছে, 2 = অসম্ভব

def check(name, X):
    X = np.array(X, dtype=float)
    bad = []
    for labels in itertools.product([-1, 1], repeat=len(X)):
        if not separable(X, np.array(labels)):
            bad.append("".join("+" if v > 0 else "-" for v in labels))
    total = 2 ** len(X)
    print(f"{name:<22} {total - len(bad):>2}/{total} labelings separable"
          + (" -> SHATTERED" if not bad else f"; fail: {' '.join(bad)}"))

check("3 points, triangle", [(1, 1), (4, 1), (2.5, 3.5)])
check("3 points, on a line", [(1, 1), (2, 2), (3, 3)])
check("4 points, XOR square", [(0, 0), (1, 1), (0, 1), (1, 0)])
check("4 points, convex kite", [(0, 1), (2, 0), (4, 1), (2, 3)])
check("4 points, one inside", [(0, 0), (4, 0), (2, 3), (2, 1)])

3 points, triangle      8/8 labelings separable -> SHATTERED
3 points, on a line     6/8 labelings separable; fail: -+- +-+
4 points, XOR square   14/16 labelings separable; fail: --++ ++--
4 points, convex kite  14/16 labelings separable; fail: -+-+ +-+-
4 points, one inside   14/16 labelings separable; fail: ---+ +++-

VC dimension d সসীম হলে growth function আর 2ⁿ-এর মতো বাড়ে না, বড়জোর n^d-এর মতো বাড়ে (Sauer–Shelah lemma, ১৯৭২ সালের কাছাকাছি কয়েকজন আলাদাভাবে প্রমাণ করেন)। তখন ln|H|-এর জায়গায় মোটামুটি d · ln n বসে (ধ্রুবক বই ভেদে আলাদা, তাই O দিয়ে):

R(h) ≤ R̂_S(h) + O( √( (d · ln(n/d) + ln(1/δ)) / n ) ), সব h ∈ H-এর জন্য একসঙ্গে

Binary classification-এ 0-1 loss-এর ক্ষেত্রে একটি গভীর ফল বলে: H PAC-শেখার যোগ্য ঠিক তখনই, যখন তার VC dimension সসীম (Blumer, Ehrenfeucht, Haussler আর Warmuth-এর ১৯৮৯ সালের কাজের সঙ্গে এই সংযোগ সাধারণত যুক্ত করা হয়; অনেক বই একে “fundamental theorem of statistical learning” বলে)।

৭ · Bias–complexity trade-off, no free lunch আর অন্য মাপকাঠি

H বড় বা নমনীয় হলে approximation error কমে (সেরা নিয়মটি আসলের কাছে আসে), কিন্তু estimation error বাড়ে (√(ln|H|/n) বা √(d/n)-এর মতো)। H ছোট হলে উল্টো। এই টানাপোড়েনকে Shalev-Shwartz আর Ben-David-এর বই Understanding Machine Learning (২০১৪) bias–complexity trade-off বলে। AI-এর ভিত্তি কোর্সের পর্ব ৬১-এর U-আকৃতির validation curve এই একই ছবির অভিজ্ঞতামূলক রূপ।

No free lunch-এর সঙ্গে সংযোগ। AI-এর ভিত্তি কোর্সের পর্ব ৫৫-এ Wolpert-এর (১৯৯৬) no free lunch ফল এসেছে: সব সম্ভাব্য লক্ষ্য-ফাংশনকে সমান ধরলে কোনো learning algorithm গড়ে অন্যটির চেয়ে ভালো নয়। Learning theory এর একটি রূপ দেয়: H যদি সব সম্ভাব্য নিয়ম হয় (অসীম VC dimension), তাহলে কোনো algorithm-ই সব D-তে অল্প ডেটায় নিশ্চয়তা দিতে পারে না; কোনো না কোনো D-তে সে ব্যর্থ হবে। তাই H সীমিত করা, অর্থাৎ inductive bias বেছে নেওয়া, শেখার পূর্বশর্ত। কোন bias ঠিক, তা আসে সমস্যার জ্ঞান থেকে।

৮ · বড় model, double descent আর classical গল্পের সীমা

আধুনিক neural network-এ parameter প্রায়ই উদাহরণের চেয়ে বহুগুণ বেশি (overparameterization), train ভুল প্রায় শূন্য, তবু নতুন ডেটায় ভালো করে। ২০১৭ সালে Zhang, Bengio, Hardt, Recht আর Vinyals (ICLR) দেখান, ছবির ডেটাসেটে label পুরো এলোমেলো করে দিলেও বড় network train ভুল প্রায় শূন্যে নামাতে পারে। অর্থাৎ তাদের H এত নমনীয় যে class-ভিত্তিক bound সেখানে ১-এর বেশি হয়ে যায়, কিছুই বলে না। অথচ আসল label-এ একই network ভালো generalise করে। তাহলে পার্থক্য H-এ নয়, ডেটা আর শেখার পদ্ধতিতে।

এর একটি সম্পর্কিত পর্যবেক্ষণ double descent, AI-এর ভিত্তি কোর্সের পর্ব ৬১-এ সংক্ষেপে এসেছে: Belkin, Hsu, Ma আর Mandal (২০১৯, PNAS) দেখান, জটিলতা বাড়ালে test ভুল প্রথমে U-এর মতো চলে, ডেটা ঠিক মুখস্থ করার সীমার কাছে চূড়ায় ওঠে, তারপর আরও বড় model-এ আবার নামতে পারে। আলোচিত ব্যাখ্যাগুলো এখনো সক্রিয় গবেষণার বিষয়:

• Implicit regularization: gradient descent নিজেই অনেক সম্ভাব্য সমাধানের মধ্যে “সরল” কিছু বাছে, যদিও H বিশাল।
• Norm বা margin-ভিত্তিক মাপ: parameter-এর সংখ্যা নয়, weight-এর আকার বা margin দিয়ে জটিলতা মাপলে কিছু ক্ষেত্রে অর্থপূর্ণ bound পাওয়া যায়।
• Benign overfitting: কিছু তাত্ত্বিক মডেলে (Bartlett ও সহকর্মীদের ২০২০ সালের কাজসহ) দেখানো হয়েছে, noise মুখস্থ করেও নির্দিষ্ট শর্তে test ভুল ভালো থাকতে পারে।

বাস্তবের শিক্ষা: (১) train ভুল প্রমাণ নয়; (২) একই ডেটায় যত বেশি জিনিস বাছবেন, তত বেশি আশাবাদ; (৩) test set একবারের জন্য, আর তার আকার থেকে ±সীমা হিসাব করুন; (৪) i.i.d. ভাঙলে (সময়ের সঙ্গে বদল, মৌসুম) সব নিশ্চয়তা ভাঙে, আর তখন পর্ব ৫৯ (Distribution shift)-এর কৌশল লাগে।

৯ · AI-এর যুগে — learning theory-র দাবি আর AI-এর হিসাব যাচাই

AI assistant learning theory-র সূত্র আত্মবিশ্বাসের সঙ্গে লেখে, আর চিহ্নগুলো নির্ভুল দেখায় বলে ভুল ধরা কঠিন। ML কোডেও সে এমন ভুল করে যা এই পর্বের তত্ত্বের সরাসরি লঙ্ঘন।

AI-এর দেওয়া তত্ত্ব আর কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• সূত্রের প্রতিটি চিহ্নের মানে লিখেছি, আর ln বনাম log₂, ε বনাম ε² মিলিয়েছি
• সবচেয়ে ছোট একটি ক্ষেত্রে (যেমন |H| = ১০) হাতে হিসাব করে AI-এর সংখ্যার সঙ্গে মিলিয়েছি
• শর্তগুলো (i.i.d., আগে থেকে ঠিক করা h, সীমাবদ্ধ loss) আমার ডেটায় খাটে কি না ভেবেছি
• ডেটা আগে ভাগ করেছি, test set তালা দেওয়া, আর তাতে মাত্র একবার মেপেছি
• কোডে কতগুলো জিনিস বাছাই হলো (model, feature, threshold) গুনেছি, আর সেই অনুযায়ী আশাবাদ ধরেছি
• ফলাফল কয়েকটি seed বা fold-এ আর একটি সরল baseline-এর সঙ্গে তুলনা করেছি; class imbalance থাকলে শুধু accuracy দেখিনি
• কোনো আসল গ্রাহকের ব্যক্তিগত ডেটা AI-তে পেস্ট করিনি