সমাধান — অধ্যায় ৬.১ · Learning Theory: Bias–Variance, Generalization & Overfitting¶

অধ্যায় ফাইল: part-6-statistical-ml/06-01-learning-theory.md (§৭ অনুশীলনী)। চলমান simulation — seed np.random.default_rng(20260619): সত্য ফাংশন $f(x)=\sin(2\pi x)$, $x\sim\text{Uniform}(0,1)$, noise $\varepsilon\sim\mathcal N(0,\sigma^2)$ with $\sigma=0.3$ (তাই irreducible $\sigma^2=0.09$), $n=40$, $\text{reps}=300$, complexity = polynomial degree $d$। মূল প্রতীক: true risk $R(h)=\mathbb E[\ell(h(x),y)]$; empirical risk $\hat R_n(h)=\frac1n\sum_i\ell(h(x_i),y_i)$; ERM $\hat h=\arg\min_{h\in\mathcal H}\hat R_n(h)$; generalization gap $R(\hat h)-\hat R_n(\hat h)$; point-wise decomposition $\mathbb E[(\hat f-f)^2]=\mathrm{Bias}^2+\mathrm{Var}+\sigma^2$; VC dimension $d_{\mathrm{VC}}$। canonical সংখ্যা (point-wise গড়, bias²/var/total): $d{=}1\to 0.156/0.015/0.261$; $d{=}3\to 0.003/0.009/\mathbf{0.102}$ (MIN); $d{=}9\to 0.000/0.104/0.194$; $d{=}11\to 0.053/21.09/21.23$; $\sigma^2=0.09$। finite-$\mathcal H$ Hoeffding bound ($\delta=0.05$): $\lvert\mathcal H\rvert{=}1000,n{=}100\to 0.230$; $n{=}1000\to 0.073$; $\lvert\mathcal H\rvert{=}10^6,n{=}1000\to 0.094$। 2D linear classifier $d_{\mathrm{VC}}=3$। §ঘ-এর runnable script (seed 20260619) উপরের bias²/variance ও Hoeffding-সংখ্যা পুনরুৎপাদন করে।

ক · ধারণাগত (conceptual)¶

সমাধান ১ (★)¶

true risk $R(h)=\mathbb E_{(x,y)\sim P}[\ell(h(x),y)]$ — পুরো (অজানা) data-distribution $P$-র উপর প্রত্যাশিত loss; অর্থাৎ মডেল $h$ অসংখ্য নতুন, অদেখা উদাহরণে গড়ে কত ভুল করবে। এটাই আমরা আসলে minimize করতে চাই।
empirical risk $\hat R_n(h)=\frac1n\sum_{i=1}^n\ell(h(x_i),y_i)$ — শুধু হাতে-থাকা $n$টি নমুনার উপর গড় loss; $P$ অজানা বলে $R$-এর জায়গায় এটিই বাস্তবে minimize করি (ERM)।
দুটোর ফাঁক $R(\hat h)-\hat R_n(\hat h)$-কে generalization gap বলে। এই gap ছোট থাকলে empirical risk minimize করাটা true risk minimize করারই ভালো বিকল্প হয়; gap বড় হলে (overfit) মডেল কাগজে ভালো, বাস্তবে খারাপ। পুরো learning theory আসলে এই gap-কে bound করার বিজ্ঞান।

সমাধান ২ (★)¶

training error optimistic কারণ একই data দু-বার ব্যবহৃত হয় — প্রথমে $\hat h$ বাছতে/fit করতে, তারপর সেই $\hat h$-এর error মাপতে। যেহেতু $\hat h=\arg\min_{h}\hat R_n(h)$ ঐ বিশেষ নমুনার উপর সবচেয়ে ভালো, সে নমুনার signal-এর পাশাপাশি তার random ওঠানামার দিকেও কিছুটা ঝুঁকে যায়; ফলে সেই নমুনায় মাপা error কৃত্রিমভাবে কম। আনুষ্ঠানিকভাবে $\mathbb E[\hat R_n(\hat h)]\le \mathbb E[R(\hat h)]$ — অর্থাৎ গড়ে train error true risk-কে under-estimate করে। (এক বাক্যে: "যে data-তে fit, সেই data-তে test" বলেই double-use।)

সমাধান ৩ (★)¶

ERM: hypothesis class $\mathcal H$ দেওয়া থাকলে ERM সেই $h$ বাছে যা empirical risk সর্বনিম্ন করে: $$ \hat h=\arg\min_{h\in\mathcal H}\hat R_n(h)=\arg\min_{h\in\mathcal H}\frac1n\sum_{i=1}^n\ell(h(x_i),y_i). $$ $\mathcal H$ বড় করলে $\hat R_n(\hat h)$ বাড়তে পারে না: ধরুন $\mathcal H_1\subseteq\mathcal H_2$। $\mathcal H_2$-তে minimize করার সময় $\mathcal H_1$-এর প্রতিটি $h$ এখনো প্রার্থী, পাশাপাশি আরও বিকল্প আছে; বেশি বিকল্পের উপর minimum কেবল সমান বা ছোট হতে পারে। তাই $\min_{\mathcal H_2}\hat R_n\le\min_{\mathcal H_1}\hat R_n$ — capacity বাড়ালে empirical risk একঘেয়ে নামে (এটাই train error-কে model-selection-এর জন্য অকেজো করে, কারণ সে সবসময় সবচেয়ে বড় $\mathcal H$ বাছতে চাইবে)।

সমাধান ৪ (★★)¶

complexity বাড়লে —

(ক) bias কমে। বেশি-flexible মডেল সত্য $f$-কে ঘনিষ্ঠভাবে ধরতে পারে, তাই গড়-প্রেডিকশন $\mathbb E[\hat f]$ সত্যের কাছে যায়। canonical: $d{=}1$-এ $\mathrm{Bias}^2=0.156$ (সরলরেখা $\sin$-কে ধরতে পারে না) → $d{=}9$-এ $0.000$।

(খ) variance বাড়ে। বেশি parameter মানে fit নমুনার noise-এর প্রতি বেশি সংবেদনশীল, নমুনা-বদলে $\hat f$ অনেক ওঠানামা করে। canonical: $d{=}1$-এ $\mathrm{Var}=0.015$ → $d{=}9$-এ $0.104$ → $d{=}11$-এ বিস্ফোরণ $21.09$।

(গ) irreducible $\sigma^2$ অপরিবর্তিত। এটি data-র noise, মডেলের সাথে সম্পর্কহীন; যত ভালো মডেলই হোক $\sigma^2=0.09$ floor থেকেই যায়। canonical: চার degree-এই total-এর মধ্যে একই $0.09$ অন্তর্ভুক্ত।

তাই trade-off: bias↓ কিনতে variance↑ মূল্য দিতে হয়; সর্বোত্তম complexity সেই বিন্দু যেখানে $\text{bias}^2+\text{var}$ সর্বনিম্ন।

সমাধান ৫ (★★)¶

training error একঘেয়ে নামে কারণ (সমাধান ৩) capacity বাড়ালে ERM-minimum কেবল ছোট হয় — train error কখনো বাড়ে না, তাই কোনো অভ্যন্তরীণ সর্বনিম্ন বিন্দু নেই।

test error U-আকৃতির কারণ $R=\text{bias}^2+\text{var}+\sigma^2$, যেখানে দুটি পদ বিপরীত দিকে চলে: বাঁ-প্রান্তে (ছোট $d$) bias² বড় → underfit; ডান-প্রান্তে (বড় $d$) variance বড় → overfit; মাঝে যোগফল সর্বনিম্ন। canonical টেবিল থেকে:

$d$	$\text{bias}^2$	var	$\sigma^2$	total
1	0.156	0.015	0.09	0.261
3	0.003	0.009	0.09	0.102
9	0.000	0.104	0.09	0.194
11	0.053	21.09	0.09	21.23

সর্বনিম্ন total $d{=}3$-এ ($0.102$)। সেই বিন্দুতে bias² ($0.003$) ও variance ($0.009$) দুটোই ছোট ও প্রায় ভারসাম্যে — bias যথেষ্ট কমে গেছে অথচ variance এখনো ফাটেনি। $d{=}3$ থেকে ডানে গেলে bias আর তেমন কমে না কিন্তু variance দ্রুত বাড়ে, তাই total ওঠে — এটাই U-এর ডান বাহু (চরমে $d{=}11$, total $21.23$)।

খ · গণনামূলক (computational)¶

সমাধান ৬ (★) [E-bias-var]¶

প্রতিটি total $=\text{bias}^2+\text{var}+\sigma^2$, $\sigma^2=0.09$:

$d$	যোগফল	total
1	$0.156+0.015+0.09$	$\boxed{0.261}$
3	$0.003+0.009+0.09$	$\boxed{0.102}$
9	$0.000+0.104+0.09$	$\boxed{0.194}$
11	$0.053+21.09+0.09$	$\boxed{21.233\approx 21.23}$

চারটিই canonical টেবিলের total-কলামের সাথে মেলে। লক্ষণীয়: $d{=}3$ সর্বনিম্ন; $d{=}11$-এ total প্রায় পুরোটাই variance ($21.09$) থেকে আসছে — সম্পূর্ণ overfit।

সমাধান ৭ (★) [E-fit]¶

$d$	$\text{bias}^2$	var	লেবেল	যুক্তি
1	0.156	0.015	underfit	উচ্চ bias², নিম্ন var — মডেল অতি-সরল, $f$-এর গঠন ধরছে না
3	0.003	0.009	সেরা (best)	bias² ও var দুটোই ছোট — ভারসাম্য-বিন্দু
9	0.000	0.104	overfit (শুরু)	bias² কার্যত শূন্য কিন্তু var বড় — noise ধরা শুরু
11	0.053	21.09	overfit (চরম)	var বিস্ফোরিত; এমনকি bias²-ও ফিরে বেড়েছে (অস্থির high-degree fit)

মূল pattern: underfit ⇒ bias-প্রধান, overfit ⇒ variance-প্রধান, সেরা ⇒ দুটোই ছোট। ($d{=}11$-এ bias² ফিরে বাড়ার কারণ — চরম-অস্থির high-degree polynomial গড়েও সত্য $f$ থেকে দূরে সরে যায়, ফলে test-grid-গড়ে $\mathbb E[\hat f]$-ও বিচ্যুত।)

সমাধান ৮ (★★) [E-hoeffding]¶

bound: $\text{gap}(M,n)=\sqrt{\dfrac{\ln M+\ln(2/\delta)}{2n}}$, $\delta=0.05\Rightarrow \ln(2/\delta)=\ln 40=3.6889$।

(ক) $M=1000,\ n=100$: $\ln 1000=6.9078$. $$ \text{gap}=\sqrt{\frac{6.9078+3.6889}{200}}=\sqrt{\frac{10.5967}{200}}=\sqrt{0.052983}=\boxed{0.230}. $$

(খ) $M=1000,\ n=1000$: $$ \text{gap}=\sqrt{\frac{10.5967}{2000}}=\sqrt{0.0052983}=\boxed{0.0728\approx 0.073}. $$

(গ) $M=10^6,\ n=1000$: $\ln 10^6=13.8155$. $$ \text{gap}=\sqrt{\frac{13.8155+3.6889}{2000}}=\sqrt{\frac{17.5044}{2000}}=\sqrt{0.0087522}=\boxed{0.0936\approx 0.094}. $$

যা শিখলাম: - (ক)→(খ): $n$ $10$ গুণ বাড়ালে bound $0.230\to0.073$, অর্থাৎ ঠিক $\sqrt{10}\approx3.16$ গুণ কমল — gap $\propto 1/\sqrt n$। data বাড়ানো gap কমানোর সবচেয়ে নির্ভরযোগ্য উপায়। - (খ)→(গ): $\lvert\mathcal H\rvert$ $1000\to10^6$ অর্থাৎ $1000$ গুণ বাড়লেও bound কেবল $0.073\to0.094$ — সামান্য, কারণ $\lvert\mathcal H\rvert$ $\ln$-এর ভেতরে বসে। অর্থাৎ hypothesis-class অনেক বড় হলেও কেবল লগারিদমিক দাম — তবে অসীম $\mathcal H$-এ এই $\ln\lvert\mathcal H\rvert$-কে VC-dimension প্রতিস্থাপন করতে হয়।

সমাধান ৯ (★★) [E-scaling]¶

$M=1000,\ \delta=0.05$, চাই $\text{gap}\le 0.05$: $$ \sqrt{\frac{\ln 1000+\ln 40}{2n}}\le 0.05 \;\Longrightarrow\; \frac{10.5967}{2n}\le 0.0025 \;\Longrightarrow\; n\ge \frac{10.5967}{0.005}=2119.3. $$ তাই $n\approx 2120$ (অর্থাৎ $\gtrsim 2.1\times10^3$) নমুনা লাগবে। (যাচাই: $n=2119$-এ gap $=\sqrt{10.5967/4238}=\sqrt{0.0025004}=0.05000$.)

$n$ ও $\lvert\mathcal H\rvert$-এর ভূমিকা কেন আলাদা: bound-এ $n$ হরে বর্গমূলের ভেতরে ($\propto 1/\sqrt n$) — তাই gap অর্ধেক করতে $n$ চার-গুণ লাগে, কিন্তু gap নিশ্চিতভাবে শূন্যে যায়। অন্যদিকে $\lvert\mathcal H\rvert$ exponent-এর ভেতরে (Hoeffding-এ $e^{-2nt^2}$, union bound-এ $\times\lvert\mathcal H\rvert$), তাই log নিলে তার দাম কেবল $\ln\lvert\mathcal H\rvert$ — লগারিদমিক, অত্যন্ত সস্তা। সারকথা: capacity দ্বিগুণ-তিনগুণ হলে সামান্য বেশি data লাগে, কিন্তু capacity অসীম হলে (যেমন সব 2D-রেখা) finite-$\mathcal H$ যুক্তি ভেঙে পড়ে — সেখানেই VC-তত্ত্ব দরকার।

গ · প্রমাণভিত্তিক (proof-based)¶

সমাধান ১০ (★★)¶

স্থির $x_0$, লিখি $\hat f=\hat f(x_0)$, $f=f(x_0)$, $\bar f=\mathbb E[\hat f]$; $y=f+\varepsilon$ with $\mathbb E[\varepsilon]=0,\ \mathrm{Var}(\varepsilon)=\sigma^2,\ \varepsilon\perp\hat f$। $$ y-\hat f=(f+\varepsilon)-\hat f=\underbrace{(f-\bar f)}{\text{ধ্রুবক}}+\underbrace{(\bar f-\hat f)}+\varepsilon. $$ বর্গ করে expectation নিই; তিনটি পদের তিনটি cross-term ধরে ধরে দেখি: $$ \mathbb E[(y-\hat f)^2]=\mathbb E\big[(f-\bar f)^2+(\bar f-\hat f)^2+\varepsilon^2+2(\cdots)\big]. $$ - $\mathbb E[(f-\bar f)^2]=(f-\bar f)^2=\mathrm{Bias}^2$ (ধ্রুবক)। - $\mathbb E[(\bar f-\hat f)^2]=\mathrm{Var}(\hat f)$ (সংজ্ঞা)। - $\mathbb E[\varepsilon^2]=\mathrm{Var}(\varepsilon)=\sigma^2$। - cross-terms: $2(f-\bar f)\,\mathbb E[\bar f-\hat f]=0$ (যেহেতু $\mathbb E[\hat f]=\bar f$); $2(f-\bar f)\,\mathbb E[\varepsilon]=0$; $2\,\mathbb E[(\bar f-\hat f)\varepsilon]=2\,\mathbb E[\bar f-\hat f]\,\mathbb E[\varepsilon]=0$ (স্বাধীনতা ও $\mathbb E[\varepsilon]=0$)।

তাই $$ \mathbb E[(y-\hat f(x_0))^2]=\big(f(x_0)-\mathbb E[\hat f(x_0)]\big)^2+\mathrm{Var}(\hat f(x_0))+\sigma^2=\mathrm{Bias}^2+\mathrm{Var}+\sigma^2.\qquad\blacksquare $$ এটি ৪.৪-এর "estimator-এর MSE = bias² + variance"-এর সাথে অভিন্ন; পার্থক্য শুধু এখানে অতিরিক্ত irreducible $\sigma^2$ যোগ হয় কারণ লক্ষ্য $f$ নয়, noisy $y$।

সমাধান ১১ (★★)¶

ধরি $\ell\in[0,1]$, তাই প্রতিটি $\ell(h(x_i),y_i)\in[0,1]$ এবং $\mathbb E[\hat R_n(h)]=R(h)$।

ধাপ ১ — এক স্থির $h$। Hoeffding (3.1, $a_i=0,b_i=1$) দেয় $$ P\big(R(h)-\hat R_n(h)\ge t\big)\le e^{-2nt^2}. $$

ধাপ ২ — union bound সব $h\in\mathcal H$-এ। "অন্তত একটি $h$-এর জন্য gap $\ge t$" ঘটনার probability প্রতিটির probability-র যোগফলের চেয়ে বড় নয়: $$ P\Big(\exists h\in\mathcal H:\ R(h)-\hat R_n(h)\ge t\Big)\le\sum_{h\in\mathcal H}P\big(R(h)-\hat R_n(h)\ge t\big)\le \lvert\mathcal H\rvert\,e^{-2nt^2}. $$

ধাপ ৩ — $\delta$ ধরে $t$-এর জন্য সমাধান। ডান পক্ষকে $\delta$ ধরি: $$ \lvert\mathcal H\rvert\,e^{-2nt^2}=\delta \;\Longrightarrow\; e^{-2nt^2}=\frac{\delta}{\lvert\mathcal H\rvert} \;\Longrightarrow\; t=\sqrt{\frac{\ln\lvert\mathcal H\rvert+\ln(1/\delta)}{2n}}. $$ তাই $1-\delta$ probability-তে একসাথে সব $h$-এর জন্য $R(h)\le \hat R_n(h)+\sqrt{\frac{\ln\lvert\mathcal H\rvert+\ln(1/\delta)}{2n}}$। (দুই-পাশের $\lvert R-\hat R_n\rvert$ চাইলে উপর-ও-নিচ দুই tail-এ union করতে $\delta\to\delta/2$, যা $\ln(1/\delta)\to\ln(2/\delta)$ দেয় — §৭-এর সূত্র, যেখান থেকে $0.230$ ইত্যাদি।) $\blacksquare$

সমাধান ১২ (★★★)¶

(ক) $d_{\mathrm{VC}}\ge 3$: একটি অ-সমরেখ (non-collinear) ত্রিভুজের তিন শীর্ষ নিন, যেমন $A=(0,0),\ B=(1,0),\ C=(0,1)$। এই $3$ বিন্দুর $2^3=8$টি ±labeling-এর প্রতিটি একটি সরলরেখা (half-plane $\text{sign}(w^\top x+b)$) দিয়ে আলাদা করা যায়: - সব $+$ বা সব $-$ — পুরো তল এক পাশে রাখা রেখা। - ঠিক একটি বিন্দু আলাদা — সেই বিন্দুকে বাকি দুটো থেকে আলাদা করা যায় কারণ অ-সমরেখ ত্রিভুজে যেকোনো এক শীর্ষ অন্য দুইয়ের সংযোগ-রেখার একপাশে একা থাকতে পারে। - ঠিক দুটি বিন্দু আলাদা — আগের ক্ষেত্রের পরিপূরক (রেখার অন্য পাশ)।

সব $8$টি বিন্যাস সম্ভব ⇒ এই $3$ বিন্দু shatter হয় ⇒ $d_{\mathrm{VC}}\ge 3$।

(খ) $d_{\mathrm{VC}}<4$: দেখাতে হবে যেকোনো $4$ বিন্দুর অন্তত একটি labeling আলাদা করা যায় না। দুই ক্ষেত্র (সাধারণ অবস্থানে; সমরেখা-ক্ষেত্র আরও সহজ): - ক্ষেত্র ১ — একটি বিন্দু বাকি তিনটির convex hull-এর ভিতরে (Radon partition)। ভিতরের বিন্দুকে $+$, বাইরের তিনটিকে $-$ করুন। কোনো half-plane এই ভিতরের বিন্দুকে তিন কোণ থেকে আলাদা করতে পারে না — কারণ সে তিনটির উত্তল সংযোগের ভিতরে, তাই যে কোনো half-plane যা ভিতরের বিন্দু ধরে তা অন্তত একটি কোণও ধরবে। - ক্ষেত্র ২ — চারটি একটি উত্তল চতুর্ভুজ $P_1P_2P_3P_4$ (ক্রমে)। বিপরীত শীর্ষ-জোড়াকে একই রঙ দিন: $P_1,P_3$ → $+$; $P_2,P_4$ → $-$ (XOR/checkerboard)। এই বিন্যাস কোনো সরলরেখা দিয়ে আলাদা করা যায় না — কারণ কর্ণ $P_1P_3$ ও $P_2P_4$ পরস্পরছেদী, তাই $\{P_1,P_3\}$-কে $\{P_2,P_4\}$ থেকে আলাদা করতে চাইলে রেখাটিকে দুই ছেদী কর্ণের মাঝ দিয়ে দুইবার যেতে হতো — একটি সরলরেখা পারে না।

উভয় ক্ষেত্রে একটি "খারাপ" labeling আছে ⇒ কোনো $4$ বিন্দু shatter হয় না ⇒ $d_{\mathrm{VC}}<4$।

(ক)+(খ) ⇒ $\boxed{d_{\mathrm{VC}}=3}$ for 2D linear classifiers। (সাধারণভাবে $\mathbb R^p$-এ half-space-এর $d_{\mathrm{VC}}=p+1$ — এখানে $p=2$।) $\blacksquare$

সমাধান ১৩ (★★)¶

No-Free-Lunch স্বজ্ঞা। input-space $\mathcal X$-এ $N$টি বিন্দু; এর $m$টি training-এ দেখা (label জানা), বাকি $N-m$টি অদেখা। আমরা চাই অদেখা বিন্দুতে label বলতে।

কোনো inductive bias না ধরলে, সম্ভাব্য target-function = $\mathcal X$ থেকে $\{0,1\}$-এ সব mapping; দেখা $m$টি বিন্দুর label fix করার পরও অদেখা $N-m$টি বিন্দুর label স্বাধীনভাবে যেকোনো কিছু — মোট $2^{N-m}$টি function এখনো training data-র সাথে সম্পূর্ণ সঙ্গতিপূর্ণ। যদি এই সব function-কে সমান-সম্ভাব্য ধরি, তবে যেকোনো নির্দিষ্ট অদেখা বিন্দুতে label $0$ ও $1$ ঠিক অর্ধেক-অর্ধেক function-এ ঘটে — তাই training data অদেখা label সম্পর্কে আক্ষরিক অর্থে কিছুই বলে না (posterior = prior)। ফলে যেকোনো learner-এর অদেখা-বিন্দু-accuracy গড়ে ঠিক $50\%$ — random guessing-এর সমান।

generalization তখনই সম্ভব যখন আমরা কিছু function-কে অন্যদের চেয়ে সম্ভাব্যতর ধরি — অর্থাৎ একটা inductive bias / prior আরোপ করি (যেমন "সত্য $f$ মসৃণ", "সরল", "low-degree polynomial", "কাছের বিন্দুর label কাছাকাছি")। এই অনুমানই অদেখা বিন্দুতে দেখা label থেকে তথ্য "বহন" করতে দেয়। সারকথা: assumption ছাড়া শেখা যায় না; ভালো শেখা = problem-এর সাথে মানানসই assumption বাছা। (এটাই hypothesis class $\mathcal H$ বাছার গভীর কারণ — $\mathcal H$ নিজেই একটি inductive bias.)

ঘ · কোডিং (coding)¶

সমাধান ১৪ (★★) [E-sim] — bias–variance simulation¶

নিচের script seed 20260619 দিয়ে point-wise $\mathrm{Bias}^2$, $\mathrm{Var}$, total হিসাব করে এবং canonical সংখ্যা পুনরুৎপাদন করে।

import numpy as np

rng = np.random.default_rng(20260619)

# --- সত্য সেটআপ ---
f = lambda x: np.sin(2*np.pi*x)      # সত্য ফাংশন
sigma = 0.3                           # noise sd  -> sigma^2 = 0.09
n, reps = 40, 300
degrees = [1, 3, 9, 11]

# point-wise bias/variance মাপার জন্য স্থির ঘন test-grid (noise-মুক্ত f এখানে জানা)
x_grid = np.linspace(0, 1, 200)
f_grid = f(x_grid)

print(f"{'deg':>4} | {'bias^2':>8} | {'var':>9} | {'total':>9}")
print("-"*40)
for d in degrees:
    preds = np.empty((reps, x_grid.size))     # প্রতিটি rep-এ grid-prediction
    for r in range(reps):
        x = rng.uniform(0, 1, n)
        y = f(x) + rng.normal(0, sigma, n)
        coef = np.polyfit(x, y, d)            # degree-d polynomial OLS fit
        preds[r] = np.polyval(coef, x_grid)
    mean_pred = preds.mean(axis=0)            # E[f_hat] (grid-জুড়ে)
    bias2 = np.mean((mean_pred - f_grid)**2)  # point-wise গড় bias^2
    var   = np.mean(preds.var(axis=0))        # point-wise গড় variance
    total = bias2 + var + sigma**2            # + irreducible
    print(f"{d:>4} | {bias2:8.3f} | {var:9.3f} | {total:9.3f}")

প্রত্যাশিত আউটপুট (canonical, seed 20260619):

 deg |   bias^2 |       var |     total
----------------------------------------
   1 |    0.156 |     0.015 |     0.261
   3 |    0.003 |     0.009 |     0.102
   9 |    0.000 |     0.104 |     0.194
  11 |    0.053 |    21.090 |    21.233

পর্যবেক্ষণ: $d{=}3$-এ total সর্বনিম্ন ($0.102$) — সেরা ভারসাম্য। $d{=}1$ underfit (bias² বড়)। $d{=}9$-এ bias² কার্যত শূন্য কিন্তু variance বেড়েছে। $d{=}11$-এ variance বিস্ফোরণ ($21.09$) — high-degree polynomial training-noise-এ অস্থিরভাবে দুলে; এটাই overfitting-এর চরম রূপ। (random-seed/grid-density-ভেদে শেষ-দশমিকে সামান্য হেরফের হতে পারে, কিন্তু পুরো U-আকার ও variance-বিস্ফোরণ স্থিতিশীল।)

সমাধান ১৫ (★★) [E-hoeffding] — finite-$\mathcal H$ bound¶

import numpy as np

def finite_h_bound(M, n, delta=0.05):
    """uniform finite-hypothesis generalization gap (two-sided)."""
    return np.sqrt((np.log(M) + np.log(2/delta)) / (2*n))

# --- §৭ প্রশ্ন ৮-এর তিনটি জোড়া পুনরুৎপাদন ---
print(f"{'M':>9} {'n':>6} | bound")
for M, n in [(1000, 100), (1000, 1000), (10**6, 1000)]:
    print(f"{M:>9} {n:>6} | {finite_h_bound(M, n):.3f}")

# --- M স্থির, n বাড়ালে bound ~ 1/sqrt(n) ---
print("\nM = 1000 স্থির, n বাড়ছে:")
for n in [50, 100, 500, 1000, 5000]:
    print(f"  n={n:>5}: bound = {finite_h_bound(1000, n):.4f}")

প্রত্যাশিত আউটপুট:

        M      n | bound
     1000    100 | 0.230
     1000   1000 | 0.073
  1000000   1000 | 0.094

M = 1000 স্থির, n বাড়ছে:
  n=   50: bound = 0.3255
  n=  100: bound = 0.2302
  n=  500: bound = 0.1029
  n= 1000: bound = 0.0728
  n= 5000: bound = 0.0326

পর্যবেক্ষণ: তিনটি জোড়া ঠিক $0.230,\ 0.073,\ 0.094$ দেয় (canonical)। $n$ স্থির-$M$-এ $50\to5000$ ($100$ গুণ) যেতে bound $0.3255\to0.0326$, অর্থাৎ প্রায় $10$ গুণ কমে — ঠিক $\sqrt{100}=10$, নিশ্চিত করে gap $\propto 1/\sqrt n$। log–log অক্ষে আঁকলে bound বনাম $n$ একটি $-\tfrac12$-ঢালের সরলরেখা দেয়। তুলনায় $M$ $1000\to10^6$ ($1000$ গুণ) কেবল $0.073\to0.094$ বাড়ায় — capacity-র দাম লগারিদমিক।

সমাধান-সারাংশ। শেখা = empirical risk minimize করে true risk-এর কাছে পৌঁছানো; train error optimistic বলে generalization-gap-ই আসল উদ্বেগ। gap দুই দিক থেকে বাঁধা — (i) bias–variance: complexity-র U-curve (canonical min $d{=}3$, total $0.102$); (ii) capacity-bound: finite-$\mathcal H$ Hoeffding ($0.230\to0.073$ as $n{\times}10$; $\lvert\mathcal H\rvert$-এর লগারিদমিক দাম) ও অসীম-$\mathcal H$-এ VC dimension ($2$D linear $\to d_{\mathrm{VC}}=3$)। আর No-Free-Lunch মনে করিয়ে দেয়: inductive bias ছাড়া এর কিছুই কাজ করে না। এই কাঠামোই Part VI-এর সব পদ্ধতির (regularization, classifier, ensemble, EM, dim-reduction) তাত্ত্বিক ভিত্তি।

\(d\)	যোগফল	total
1	\(0.156+0.015+0.09\)	\(\boxed{0.261}\)
3	\(0.003+0.009+0.09\)	\(\boxed{0.102}\)
9	\(0.000+0.104+0.09\)	\(\boxed{0.194}\)
11	\(0.053+21.09+0.09\)	\(\boxed{21.233\approx 21.23}\)