সমাধান — অধ্যায় ৫.৮ · Cross-Validation & Model Validation¶
অধ্যায়
part-5-modeling/05-08-cross-validation-model-validation.md-এর section ৭-এর সব অনুশীলনীর পূর্ণ সমাধান। চলমান dataset — seednp.random.default_rng(20260619), \(n=120\): \(x\sim\text{Uniform}(-3,3)\); সত্যিকারের ফাংশন \(f(x)=x^3-3x\); \(y_i=f(x_i)+\varepsilon_i\), \(\varepsilon_i\sim\mathcal N(0,3^2)\) — irreducible variance \(\sigma^2=9\)। Polynomial degree \(d=1,\dots,10\)। প্রতিটি সংখ্যাগত ফলnumpy/scikit-learnদিয়ে যাচাই করা হয়েছে — §ঘ-এর runnable script এ-ই data-generation-ক্রমে নিচের canonical সংখ্যা পুনরুৎপাদন করে। canonical সংখ্যা: train MSE \(d{=}1\to22.08\), \(d{=}3\to9.59\), \(d{=}10\to9.12\) (একঘেয়ে ↓); 10-fold CV \(d{=}1\to22.68\), \(d{=}3\to10.15\) (MIN), \(d{=}10\to10.90\) (U-আকার); LOOCV সর্বনিম্ন \(d{=}3\to10.18\); one-SE: সেরা CV \(10.15\), \(\text{SE}\approx0.85\), threshold \(\approx11.0\) → বাছা degree \(3\); test MSE (deg \(3\), স্বাধীন test-set) \(9.71\approx\sigma^2=9\)। মূল সূত্র: training error \(\frac1n\sum_i(y_i-\hat f(x_i))^2\); \(K\)-fold \(\text{CV}_{(K)}=\frac1K\sum_k\text{MSE}_k\); LOOCV \(\text{CV}_{(n)}=\frac1n\sum_i(y_i-\hat f^{(-i)}(x_i))^2\); linear-smoother shortcut \(\frac1n\sum_i\big(\frac{y_i-\hat y_i}{1-S_{ii}}\big)^2\); optimism \(\frac{2\sigma^2\operatorname{df}}{n}\)।
ক · ধারণাগত (conceptual)¶
৭.১ ★ — কেন training error model-complexity বাছতে পারে না (optimism)¶
(ক) শুধু training error দেখে বাছলে যে degree-এ train MSE সর্বনিম্ন সেটাই নির্বাচিত হতো — চলমান উদাহরণে train MSE একঘেয়ে কমে (\(22.08\to9.59\to9.12\)), তাই সবচেয়ে জটিল মডেল \(d{=}10\) বেছে নিতে হতো। কিন্তু 10-fold CV সেখানে সবচেয়ে বেশি (\(10.90\)), সর্বনিম্ন \(d{=}3\)-এ (\(10.15\)) — অর্থাৎ \(d{=}10\) overfit, নতুন data-তে খারাপ। সঠিক বাছাই \(d{=}3\)। training error model-complexity বাছার অযোগ্য কারণ সে complexity বাড়ার সাথে সবসময় কমতেই থাকে (কখনো বাড়ে না), তাই কোনো "সর্বোত্তম" বিন্দু চিহ্নিত করে না।
(খ) একই data-তে parameter fit করলে model সেই বিশেষ sample-এর random ওঠানামাকেও আংশিক ধরে ফেলে — fit ঐ sample-এর দিকে "ঝুঁকে" যায়। তাই সেই sample-এ মাপা error প্রকৃত (নতুন data-র) error-এর চেয়ে কৃত্রিমভাবে কম — এটাই optimism। আনুষ্ঠানিকভাবে (§৭.১৩) optimism \(=\frac{2\sigma^2\operatorname{df}}{n}>0\), তাই \(\mathbb E[\overline{\text{err}}]<\text{Err}_{\text{in}}\) সর্বদা।
(গ) \(d{=}10\)-এ train MSE \(=9.12<\sigma^2=9\) — অর্থাৎ model residual-এর গড়-বর্গ irreducible noise-এর নিচে নামিয়েছে। এটা অসম্ভব যদি model শুধু signal ধরত (signal নিখুঁত ধরলেও residual-variance \(=\sigma^2\) থাকার কথা)। তাই \(\text{train MSE}<\sigma^2\) মানে model noise-এর কিছু অংশকেও "signal" ভেবে fit করছে — overfitting-এর সরাসরি লক্ষণ। সেই অতিরিক্ত-fit নতুন data-তে কাজে আসে না, তাই honest error (CV \(10.90\)) \(\sigma^2\)-এর উপরে।
৭.২ ★ — train / validation / test-এর তিন ভূমিকা¶
(ক) - training set — এখানে model-এর parameter (\(\hat\beta\), polynomial coefficient) শেখা হয় (fit)। - validation set — এখানে tuning parameter / model বাছা হয় (degree, bandwidth \(h\), penalty \(\lambda\), কোন মডেল-পরিবার) — training-এ দেখা হয়নি এমন data-তে কোন setting সবচেয়ে ভালো generalize করে দেখা। - test set — সম্পূর্ণ আলাদা, একবার মাত্র ব্যবহৃত; চূড়ান্ত (বাছা) মডেলের generalization error-এর নিরপেক্ষ অনুমান দেয়।
(খ) test set "একবার, একদম শেষে" ব্যবহার করতে হয় কারণ — যদি test error দেখে বারবার model বদলানো/টিউন করা হয়, তবে test set কার্যত আরেকটা validation set হয়ে যায়: আমরা পরোক্ষে test-এর দিকে fit করছি। তখন test error আর honest থাকে না, optimistic হয় (information leakage); আসল-জগতে মডেল প্রত্যাশার চেয়ে খারাপ করবে। একবার-ব্যবহারই test-এর নিরপেক্ষতা রক্ষা করে।
(গ) cross-validation হলো validation set-এর বিকল্প। আলাদা একটা validation-অংশ স্থায়ীভাবে কেটে রাখার বদলে, CV পুরো training data-কে \(K\)টা fold-এ ভাগ করে পালাক্রমে প্রতিটাকে validation হিসেবে ব্যবহার করে — ফলে (i) প্রতিটা বিন্দু একবার validation, একবার-নয়-একাধিকবার training-এ আসে, data-র সদ্ব্যবহার হয়; (ii) tuning-সিদ্ধান্ত একটামাত্র (হয়তো ভাগ্যবশত সহজ/কঠিন) validation-split-এর ওপর নির্ভর করে না। data কম হলে এই সুবিধা বড়। (test set তবু আলাদা রাখা ভালো, যদি সম্ভব হয়।)
৭.৩ ★★ — K-fold cross-validation কীভাবে কাজ করে¶
(ক) \(K\)-fold CV-তে model fit হয় ঠিক \(K\) বার (প্রতিটা fold একবার করে held-out, বাকি \(K-1\) fold-এ একটা fit)। প্রতিটা data-বিন্দু ঠিক একবার held-out (validation) হিসেবে ব্যবহৃত হয় (সে যে fold-এ আছে, সেই fold যখন held-out), আর \(K-1\) বার training-এ থাকে। তাই প্রতিটা বিন্দুর জন্য ঠিক একটা out-of-sample prediction পাওয়া যায়।
(খ) দেওয়া ১০টা fold-MSE: \(9.8,\ 10.4,\ 9.1,\ 11.2,\ 10.0,\ 9.6,\ 10.9,\ 10.3,\ 9.5,\ 10.7\)। $\(\sum_k\text{MSE}_k=9.8+10.4+9.1+11.2+10.0+9.6+10.9+10.3+9.5+10.7=101.5,\)$ $\(\text{CV}_{(10)}=\frac{101.5}{10}=\boxed{10.15}.\)$ (canonical degree-\(3\) মান।)
(গ) \(\text{CV}_{(10)}=10.15>\) train MSE \(=9.59\) কারণ CV প্রতিবার আগে-না-দেখা fold-এ (held-out) error মাপে — সেখানে optimism নেই, model সেই বিন্দুগুলোতে fit হয়নি। train MSE optimistic-ভাবে ছোট (model নিজের training-noise-ও ধরেছে)। তাই test error-এর সৎ অনুমান হলো CV (\(10.15\)) — যা যথাযথভাবে \(\sigma^2=9\)-এর সামান্য উপরে (irreducible \(9\) \(+\) সামান্য estimation variance)।
৭.৪ ★★ — LOOCV ও linear-smoother shortcut¶
(ক) সরাসরি LOOCV-তে model \(n\) বার re-fit করতে হয় (প্রতিটা বিন্দু একবার বাদ দিয়ে \(n-1\) বিন্দুতে fit)। বড় \(n\)-এ এটা ব্যয়বহুল — \(n\)টা পূর্ণ OLS-fit (প্রতিটায় matrix-inversion) মানে প্রায় \(n\times\) একটা fit-এর খরচ।
(খ) shortcut-এর বড় সুবিধা: linear smoother-এ (\(\hat{\mathbf y}=S\mathbf y\)) মাত্র একবার পূর্ণ-data fit করলেই হয় — তা থেকে \(\hat y_i\) ও \(S_{ii}\) (leverage) পেয়ে গেলে সব leave-one-out residual বন্ধ-রূপে \(\frac{y_i-\hat y_i}{1-S_{ii}}\); কোনো re-fit লাগে না। তাই \(n\)টা fit-এর বদলে একটা fit \(+\) \(n\)টা সরল ভাগ — বিশাল সাশ্রয় (§৭.১৪-এ সূত্র প্রমাণিত)।
(গ) \(n=4\), \(r=(2.0,-1.0,1.5,-0.5)\), \(S_{ii}=(0.5,0.25,0.4,0.2)\)। প্রতিটা পদ \(\big(\frac{r_i}{1-S_{ii}}\big)^2\):
| \(i\) | \(r_i\) | \(1-S_{ii}\) | \(r_i/(1-S_{ii})\) | বর্গ |
|---|---|---|---|---|
| 1 | \(2.0\) | \(0.50\) | \(4.000\) | \(16.000\) |
| 2 | \(-1.0\) | \(0.75\) | \(-1.333\) | \(1.778\) |
| 3 | \(1.5\) | \(0.60\) | \(2.500\) | \(6.250\) |
| 4 | \(-0.5\) | \(0.80\) | \(-0.625\) | \(0.391\) |
৭.৫ ★★ — CV-এর bias–variance \(K\)-এর সাথে (কেন \(K=5/10\), LOOCV নয়)¶
(ক) ছোট \(K\) (\(=5\)): প্রতিটা training-set মাত্র \(\tfrac45 n\) বিন্দুর — পূর্ণ data-র চেয়ে ছোট, তাই model সামান্য দুর্বল, তার error একটু বড় দেখায়। ফলে CV প্রকৃত (full-\(n\)) error-কে সামান্য over-estimate করে — অর্থাৎ upward / pessimistic bias (test error-কে একটু বেশি ভেবে দেখায়)।
(খ) LOOCV (\(K=n\)): প্রতিটা training-set \(n-1\) বিন্দুর (প্রায় পুরো data), তাই বাছা fit প্রায় full-data fit ⇒ bias প্রায় শূন্য। কিন্তু \(n\)টা leave-one-out fit একে অন্যের প্রায় অভিন্ন (শুধু এক বিন্দুর ফারাক) ⇒ তাদের held-out error একসাথে ওঠে-নামে, অর্থাৎ গভীরভাবে correlated। কেন correlated estimate-এর গড় বেশি variance বহন করে: \(n\)টা চলকের গড়ের variance \(=\frac1{n^2}\big(\sum_i\operatorname{Var}+\sum_{i\ne j}\operatorname{Cov}\big)\); স্বাধীন হলে cross-term শূন্য, variance \(\propto1/n\) হারে কমত; কিন্তু উচ্চ positive correlation থাকলে cross-term বড় থাকে, variance আর \(1/n\) হারে কমে না — তাই LOOCV-গড় বেশি variance বহন করে।
(গ) চলমান উদাহরণে 10-fold CV ও LOOCV একই degree বাছে — \(d{=}3\), মান যথাক্রমে \(10.15\) ও \(10.18\) (প্রায় সমান)। এটা বলে দেয়: model-selection-সিদ্ধান্তের জন্য \(K=10\)-ই যথেষ্ট — LOOCV-র বাড়তি গণনা-খরচ এখানে কোনো ভিন্ন/ভালো সিদ্ধান্ত দেয় না। তাই বাস্তবে \(5\)/\(10\)-fold পছন্দনীয়: bias সামান্য বাড়িয়ে variance ও খরচ অনেক কমায়, অথচ একই model বাছে।
৭.৬ ★★ — one-standard-error rule প্রয়োগ¶
(ক) CV-min নিয়ম যে degree-এ CV সর্বনিম্ন সেটা বাছে — table-এ সর্বনিম্ন \(10.15\) at \(d{=}3\), তাই CV-min বাছে \(d=3\)।
(খ) one-SE rule: সর্বনিম্ন CV-এর সাথে তার SE যোগ করে threshold: $\(\text{threshold}=\text{CV}_{\min}+\text{SE}_{\min}=10.15+0.85=11.0.\)$ এখন threshold \(\le11.0\)-এর নিচে থাকা সবচেয়ে সরল (ছোট \(d\)) model বাছি। \(d{=}1\) (\(22.68\)), \(d{=}2\) (\(22.55\)) — দুটোই \(\gg11.0\), বাদ। \(d{=}3\) (\(10.15<11.0\)) — threshold-এর নিচে এবং সবচেয়ে ছোট এমন degree। তাই one-SE rule-ও বাছে \(d=3\)।
(গ) CV-গড় নিজে একটা noisy estimate (প্রতিটার একটা SE আছে); দুটো model-এর CV যদি এক SE-এর মধ্যে থাকে, তারা পরিসংখ্যানগতভাবে আলাদা নয় — কার্যত সমান-ভালো। one-SE rule বলে: এমন "সমান-ভালো" model-গুলোর মধ্যে সবচেয়ে সরলটা নাও (Occam/parsimony) — কারণ অতিরিক্ত জটিলতা পরিমাপযোগ্য উন্নতি দিচ্ছে না, শুধু variance/overfit-ঝুঁকি বাড়াচ্ছে। তাই one-SE rule সাধারণত CV-min-এর সমান বা সরলতর model বাছে — generalization-এ এটি বেশি robust (এখানে অবশ্য দুটোই \(d{=}3\), কারণ U-আকার এখানে তীক্ষ্ণ)।
৭.৭ ★★ — CV দিয়ে যেকোনো tuning parameter বাছা¶
(ক) CV-ভিত্তিক tuning-এর সাধারণ recipe: candidate-মানের একটা grid নাও (যেমন \(d\in\{1,\dots,10\}\), বা \(h\)/\(\lambda\)-এর একটা পরিসর); প্রতিটা মান \(\theta\)-এর জন্য \(K\)-fold CV-error হিসাব করো (পালাক্রমে fold held-out, বাকিতে fit-করে predict); যে \(\theta\) CV-error সর্বনিম্ন করে (বা one-SE-rule অনুযায়ী যথেষ্ট-সরল) সেটাই বাছো।
(খ) CV এই সবকটা (\(h\), df, \(\lambda\), degree) একই ভাবে handle করে কারণ সে model-কে একটা black box হিসেবে দেখে — শুধু "এই setting-এ fit করে held-out data-তে কত error" মাপে। model-এর ভেতরের রূপ (rৈখিক না kernel না spline, এর likelihood বা effective df কী) জানার দরকার নেই; fit-করে-predict করার ক্ষমতা থাকলেই CV প্রযোজ্য। তাই degree/\(h\)/df/\(\lambda\) — সব এক অভিন্ন কাঠামোয়।
(গ) CV-র AIC/BIC-র চেয়ে বেশি general হওয়ার কারণ: AIC/BIC-র দুটো জিনিস লাগে — (i) একটা likelihood (\(-2\log L\)), (ii) parameter-গণনা / effective df (\(p\) বা \(\operatorname{tr}(S)\))। অনেক model-এ (random forest, kNN, custom black-box) এ দুটোর একটাও স্পষ্ট নয়। CV-র এর কোনোটাই লাগে না — শুধু predict করতে পারলেই হয়। তাই CV সর্বত্র খাটে; বিনিময়ে CV বেশি গণনা-ব্যয়বহুল (\(K\)টা fit), AIC/BIC একটা fit-এই উত্তর দেয় (likelihood-ভিত্তিক হলে)।
খ · গণনামূলক (computational)¶
৭.৮ ★ — fold-MSE থেকে CV-গড় ও SE হাতে¶
পাঁচটা fold-MSE: \(8.5,\ 11.0,\ 9.5,\ 12.0,\ 10.0\)।
(ক) \(\sum=8.5+11.0+9.5+12.0+10.0=51.0\); \(\ \text{CV}_{(5)}=\dfrac{51.0}{5}=\boxed{10.2}\)।
(খ) গড় \(10.2\) থেকে deviation (বিচ্যুতি): \(-1.7,\ 0.8,\ -0.7,\ 1.8,\ -0.2\); বর্গ: \(2.89,\ 0.64,\ 0.49,\ 3.24,\ 0.04\); বর্গ-যোগ \(=7.30\)। $\(s^2=\frac{7.30}{5-1}=1.825,\quad s=1.351,\quad \text{SE}=\frac{s}{\sqrt5}=\frac{1.351}{2.2361}=\boxed{0.604}.\)$
(গ) one-SE threshold \(=\text{CV}+\text{SE}=10.2+0.604=\boxed{10.80}\)। (এর নিচে থাকা সবচেয়ে সরল model-ই one-SE-পছন্দ হতো।)
৭.৯ ★ — optimism সংখ্যায় (train vs CV gap)¶
(ক) optimism gap \(=\text{CV}-\text{train}\):
| \(d\) | train MSE | \(\text{CV}_{(10)}\) | gap |
|---|---|---|---|
| 1 | \(22.08\) | \(22.68\) | \(0.60\) |
| 3 | \(9.59\) | \(10.15\) | \(0.56\) |
| 10 | \(9.12\) | \(10.90\) | \(1.78\) |
(খ) gap সবচেয়ে বড় \(d{=}10\)-এ (\(1.78\))। প্রত্যাশিত — §৭.১৩-এর optimism \(=\frac{2\sigma^2\operatorname{df}}{n}\) অনুযায়ী optimism \(\operatorname{df}=d+1\)-এর সমানুপাতী, তাই সবচেয়ে নমনীয় model (\(d{=}10\), \(\operatorname{df}=11\)) সবচেয়ে বেশি optimistic: সে training-noise সবচেয়ে বেশি ধরে, তাই train কৃত্রিম-ভাবে সবচেয়ে ছোট আর gap সবচেয়ে বড়। যাচাই: \(\frac{2\cdot9\cdot11}{120}=1.65\approx1.78\) (sample-fluctuation-সহ চমৎকার মিল); \(d{=}3\): \(\frac{2\cdot9\cdot4}{120}=0.60\approx0.56\); \(d{=}1\): \(\frac{2\cdot9\cdot2}{120}=0.30\) (observed \(0.60\) — ছোট-\(\operatorname{df}\)-এ sample-noise তুলনায় বড়)।
(গ) \(d{=}10\)-এ train \(9.12<\sigma^2=9\) কিন্তু CV \(10.90>\sigma^2\) — এই ফাঁক (\(10.90-9.12=1.78\)) overfitting-এর মূল্য মাপছে: model noise-কে signal ভেবে fit করায় train কমেছে, কিন্তু সেই অতিরিক্ত-fit নতুন data-তে কাজে আসেনি, উল্টো variance এনে honest error বাড়িয়েছে। এই gap-ই optimism (training-error যত কম দেখাচ্ছে, test-error তত বেশি)।
৭.১০ ★★ — honest test error যাচাই (CV বনাম held-out test)¶
(ক) test error-এর decomposition: \(\text{Err}=\sigma^2+\text{bias}^2+\text{variance of }\hat f\)। সত্য \(f(x)=x^3-3x\) একটা cubic, তাই degree-\(3\) model সঠিকভাবে-specified ⇒ bias \(\approx0\); বাকি থাকে irreducible \(\sigma^2=9\) \(+\) সামান্য estimation variance (সসীম \(n=120\)-এ coefficient-অনুমানের অনিশ্চয়তা)। তাই test MSE \(=9.71=9+0.71\) — \(\sigma^2\)-এর খুব কাছে, একটু উপরে (ঐ \(0.71\) estimation variance)।
(খ) degree-\(3\)-এর 10-fold CV ছিল \(10.15\), স্বাধীন test MSE \(9.71\) — দুটো কাছাকাছি। এটা নিশ্চিত করে CV সত্যিই test/generalization error-এর সৎ অনুমান দিচ্ছে। (CV সামান্য বেশি, \(10.15>9.71\), কারণ CV-fit ছোট training-set \(\tfrac9{10}n\)-এ — §৭.৫(ক)-এর সামান্য pessimistic bias; দিক ও মাত্রা দুটোই প্রত্যাশিত।)
(গ) \(d{=}10\) overfit, তার CV \(10.90>10.15\)। তাই একই স্বাধীন test-এ তার MSE \(\sigma^2=9\)-এর আরও উপরে যেত (আনুমানিক \(\approx10.9\), CV-র কাছাকাছি) — অতিরিক্ত estimation variance generalization খারাপ করে। অর্থাৎ test-set-ও CV-র সিদ্ধান্তই সমর্থন করত: \(d{=}3\) ভালো, \(d{=}10\) খারাপ।
৭.১১ ★★ — LOOCV shortcut বড় উদাহরণে (leverage-এর ভূমিকা)¶
\(r=(3.0,-2.0,1.0,-4.0,2.5)\), \(S_{ii}=(0.10,0.30,0.50,0.20,0.40)\)।
(ক)–(খ) প্রতিটা পদ \(\big(\frac{r_i}{1-S_{ii}}\big)^2\):
| \(i\) | \(r_i\) | \(1-S_{ii}\) | \(r_i/(1-S_{ii})\) | বর্গ |
|---|---|---|---|---|
| 1 | \(3.0\) | \(0.90\) | \(3.333\) | \(11.111\) |
| 2 | \(-2.0\) | \(0.70\) | \(-2.857\) | \(8.163\) |
| 3 | \(1.0\) | \(0.50\) | \(2.000\) | \(4.000\) |
| 4 | \(-4.0\) | \(0.80\) | \(-5.000\) | \(25.000\) |
| 5 | \(2.5\) | \(0.60\) | \(4.167\) | \(17.361\) |
(গ) বিন্দু \(3\)-এর residual ছোট (\(r_3=1.0\)) কিন্তু leverage বড় (\(S_{33}=0.50\)), তাই হর \(1-S_{ii}=0.50\) ছোট ⇒ contribution \(4.0\) — কাঁচা residual-বর্গ (\(1.0\))-এর চারগুণ। shortcut high-leverage বিন্দুর leave-one-out error-কে এভাবে "বড় করে দেখায়"। যুক্তিসঙ্গত কেন: high-leverage বিন্দু fit-কে নিজের দিকে বেশি টানে (fit তার \(y\)-মানের কাছাকাছি বসে); তাকে বাদ দিলে prediction বেশি বদলায়, তাই তার প্রকৃত leave-one-out error বড় — shortcut ঠিক সেটাই ধরে। (নিম্ন-leverage বিন্দু বাদ দিলে fit সামান্যই বদলায়, তাই তার গুণক \(\approx1\)।)
৭.১২ ★★ — AIC/BIC বনাম CV¶
\(\text{AIC}=n\log(\widehat{\text{RSS}}/n)+2p\), \(\ \text{BIC}=n\log(\widehat{\text{RSS}}/n)+p\log n\), \(p=d+1\), \(n=120\)।
(ক) প্রথম পদ \(n\log(\text{RSS}/n)\) degree বাড়ালে কমে, কারণ বেশি-নমনীয় model train-RSS একঘেয়ে কমায় (train MSE \(22.08\to9.59\to9.12\), তাই \(\log(\text{RSS}/n)\) কমে)। জটিলতাকে শাস্তি দেয় দ্বিতীয় পদ (\(2p\) বা \(p\log n\)), যা \(p=d+1\)-এর সাথে বাড়ে। দুই পদের যোগফল U-আকার — সর্বনিম্নই বাছা criterion।
(খ) BIC-penalty \(p\log n=p\log120\approx p\cdot4.79\) বনাম AIC-penalty \(2p\)। যেহেতু \(\log120\approx4.79>2\), BIC বেশি কড়া — প্রতিটা অতিরিক্ত parameter-কে বেশি শাস্তি দেয়। তাই BIC সাধারণত সরলতর model বাছে। (তত্ত্ব: BIC consistent — সত্য model candidate-এ থাকলে \(n\to\infty\)-এ সেটাই বাছে; AIC prediction-অনুকূল কিন্তু বড় model-এর দিকে সামান্য ঝুঁকতে পারে।)
(গ) এখানে সত্য \(f\) নিজেই cubic, তাই \(d{=}3\)-এ bias প্রায় শূন্য এবং তার বেশি degree শুধু variance/penalty বাড়ায় — train-fit-এর উন্নতি \(d{=}3\)-এর পরে নগণ্য, কিন্তু penalty বাড়তেই থাকে। ফলে AIC, BIC, এবং CV — তিনটাই (train-fit ও penalty/held-out-error-এর ভারসাম্যে) \(d{=}3\)-কেই সেরা পায়; তাই একমত হওয়া প্রত্যাশিত। এরা ভিন্ন উত্তর দিত যদি: (i) সত্য \(f\) কোনো degree-এ ঠিক না বসত (misspecified — তখন bias কখনো শূন্য হয় না, criterion-গুলোর penalty-ভর ভিন্ন বলে ভিন্ন degree বাছত); বা (ii) \(n\) ছোট হতো (তখন AIC বেশি, BIC কম degree-এর দিকে টানত — penalty-পার্থক্য তীব্র)।
গ · প্রমাণভিত্তিক (proof-based)¶
৭.১৩ ★★★ — optimism \(=\frac{2\sigma^2\operatorname{df}}{n}\) প্রমাণ (linear smoother)¶
ধরা: \(y_i=f(x_i)+\varepsilon_i\), \(\varepsilon_i\) স্বাধীন, \(\mathbb E[\varepsilon_i]=0\), \(\operatorname{Var}(\varepsilon_i)=\sigma^2\); linear smoother \(\hat{\mathbf y}=S\mathbf y\) (\(S\) fixed, \(\mathbf y\)-নিরপেক্ষ)। \(y_i^{\text{new}}\) = একই \(x_i\)-তে স্বাধীন নতুন observation (\(\mathbb E[y_i^{\text{new}}]=f(x_i)\), \(\operatorname{Var}=\sigma^2\), সব fit-data থেকে স্বাধীন)।
(ক) স্থির \(i\)-এর জন্য: যেকোনো random \(a\) ও \(\hat y_i\)-এ $\(\mathbb E[(a-\hat y_i)^2]=\operatorname{Var}(a)+\operatorname{Var}(\hat y_i)+(\mathbb E a-\mathbb E\hat y_i)^2-2\operatorname{Cov}(a,\hat y_i).\)$ \(a=y_i^{\text{new}}\) ও \(a=y_i\) — দুজনের গড় \(f(x_i)\) ও variance \(\sigma^2\) অভিন্ন, তাই প্রথম তিন পদ একই; বিয়োগে শুধু covariance-পদ বাঁচে: $\(\mathbb E[(y_i^{\text{new}}-\hat y_i)^2]-\mathbb E[(y_i-\hat y_i)^2]=-2\operatorname{Cov}(y_i^{\text{new}},\hat y_i)+2\operatorname{Cov}(y_i,\hat y_i)=2\operatorname{Cov}(y_i,\hat y_i),\)$ যেহেতু \(y_i^{\text{new}}\) fit-data থেকে স্বাধীন ⇒ \(\operatorname{Cov}(y_i^{\text{new}},\hat y_i)=0\)।
(খ) \(\hat y_i=\sum_j S_{ij}y_j\), এবং স্বাধীনতায় \(\operatorname{Cov}(y_i,y_j)=\sigma^2\delta_{ij}\): $\(\operatorname{Cov}(y_i,\hat y_i)=\operatorname{Cov}\Big(y_i,\sum_j S_{ij}y_j\Big)=\sum_j S_{ij}\operatorname{Cov}(y_i,y_j)=\sum_j S_{ij}\sigma^2\delta_{ij}=\sigma^2 S_{ii}.\)$
(গ) এবার \(\frac1n\sum_i\) নিয়ে: $\(\text{op}=\text{Err}_{\text{in}}-\mathbb E[\overline{\text{err}}]=\frac1n\sum_i\Big(\mathbb E[(y_i^{\text{new}}-\hat y_i)^2]-\mathbb E[(y_i-\hat y_i)^2]\Big)=\frac1n\sum_i 2\sigma^2 S_{ii}=\frac{2\sigma^2}{n}\sum_i S_{ii}=\frac{2\sigma^2}{n}\operatorname{tr}(S).\)$ \(\operatorname{df}=\operatorname{tr}(S)\) বসিয়ে \(\boxed{\text{op}=\dfrac{2\sigma^2\operatorname{df}}{n}}\)। ∎
ব্যাখ্যা: polynomial-OLS-এ \(S\) একটা projection, \(\operatorname{tr}(S)=p=d+1\); তাই optimism degree-এর সাথে রৈখিকভাবে বাড়ে — training error ঠিক \(\frac{2\sigma^2\operatorname{df}}{n}\) পরিমাণে test error-কে under-estimate করে। এই অভিন্ন রাশিই Mallows' \(C_p\) / AIC-এর "\(+2\operatorname{df}\)" penalty-র উৎস: \(\text{Err}_{\text{in}}\approx\overline{\text{err}}+\frac{2\sigma^2\operatorname{df}}{n}\) — train-fit-কে complexity-penalty দিয়ে সংশোধন করে test error আন্দাজ। চলমান উদাহরণে যাচাই: \(d{=}3\) ⇒ op \(=\frac{2\cdot9\cdot4}{120}=0.60\), যা observed gap \(0.56\)-এর কাছাকাছি (§৭.৯)।
৭.১৪ ★★★ — LOOCV linear-smoother shortcut সূত্র প্রমাণ¶
ধরা ধর্ম (OLS-সহ অনেক linear smoother-এ সত্য): বিন্দু \(i\)-এর \(y_i\)-কে তার leave-one-out prediction \(\hat y_i^{(-i)}\equiv\hat f^{(-i)}(x_i)\) দিয়ে প্রতিস্থাপন করে পূর্ণ-data smoother চালালে \(i\)-তম fitted মান অপরিবর্তিত: $\(\hat y_i^{(-i)}=\sum_{j\ne i}S_{ij}y_j+S_{ii}\,\hat y_i^{(-i)}.\tag{\)\ast\(}\)$
(ক) \((\ast)\) থেকে \(\hat y_i^{(-i)}\) আলাদা: $\(\hat y_i^{(-i)}-S_{ii}\hat y_i^{(-i)}=\sum_{j\ne i}S_{ij}y_j\ \Rightarrow\ \hat y_i^{(-i)}(1-S_{ii})=\sum_{j\ne i}S_{ij}y_j\ \Rightarrow\ \hat y_i^{(-i)}=\frac{\sum_{j\ne i}S_{ij}y_j}{1-S_{ii}}.\)$
(খ) পূর্ণ-data fit: \(\hat y_i=\sum_j S_{ij}y_j=\sum_{j\ne i}S_{ij}y_j+S_{ii}y_i\) ⇒ \(\sum_{j\ne i}S_{ij}y_j=\hat y_i-S_{ii}y_i\)। বসিয়ে: $\(\hat y_i^{(-i)}=\frac{\hat y_i-S_{ii}y_i}{1-S_{ii}},\qquad y_i-\hat y_i^{(-i)}=y_i-\frac{\hat y_i-S_{ii}y_i}{1-S_{ii}}=\frac{y_i(1-S_{ii})-(\hat y_i-S_{ii}y_i)}{1-S_{ii}}.\)$
(গ) লব সরল করি: $\(y_i(1-S_{ii})-\hat y_i+S_{ii}y_i=y_i-S_{ii}y_i-\hat y_i+S_{ii}y_i=y_i-\hat y_i.\)$ তাই $\(y_i-\hat y_i^{(-i)}=\frac{y_i-\hat y_i}{1-S_{ii}},\qquad \text{CV}_{(n)}=\frac1n\sum_i\big(y_i-\hat y_i^{(-i)}\big)^2=\boxed{\frac1n\sum_{i=1}^n\Big(\frac{y_i-\hat y_i}{1-S_{ii}}\Big)^2}.\)$ ∎
GCV-সম্পর্ক: এই সূত্রে প্রতিটা leverage \(S_{ii}\)-কে তাদের গড় \(\bar S=\operatorname{tr}(S)/n\) দিয়ে প্রতিস্থাপন করলে পাওয়া যায় Generalized Cross-Validation: $\(\text{GCV}=\frac1n\sum_i\Big(\frac{y_i-\hat y_i}{1-\operatorname{tr}(S)/n}\Big)^2=\frac{\tfrac1n\sum_i(y_i-\hat y_i)^2}{(1-\operatorname{tr}(S)/n)^2}.\)$ GCV leverage-অসমতার প্রতি কম সংবেদনশীল ও rotation-invariant — LOOCV-র একটা সুবিধাজনক সন্নিকর্ষ, বিশেষত smoothing-spline (\(\lambda\)) tuning-এ বহুল-ব্যবহৃত (৫.৭-এর effective df \(\operatorname{tr}(S)\) এখানে সরাসরি ঢোকে)।
ঘ · কোডিং (Python)¶
৭.১৫ ★★★ — পূর্ণ degree-selection pipeline¶
নিচের script seed-সহ চালালে উপরের সব canonical সংখ্যা পুনরুৎপাদন করে (train MSE, 10-fold CV \(+\) SE, LOOCV-shortcut, one-SE rule, স্বাধীন test)।
import numpy as np
from sklearn.model_selection import KFold
# ---------- 1. canonical data ----------
rng = np.random.default_rng(20260619)
n = 120
x = rng.uniform(-3, 3, n)
f = x**3 - 3*x # সত্য ফাংশন
y = f + rng.normal(0, 3, n) # sigma^2 = 9 (irreducible)
sigma2 = 9.0
degrees = range(1, 11)
def design(x, d):
# columns [1, x, x^2, ..., x^d]
return np.vander(np.asarray(x, float), d + 1, increasing=True)
def ols_fit(X, y):
beta, *_ = np.linalg.lstsq(X, y, rcond=None)
return beta
# ---------- 1. train MSE (পূর্ণ-data fit) ----------
print("degree | train MSE")
train_mse = {}
for d in degrees:
X = design(x, d)
yhat = X @ ols_fit(X, y)
train_mse[d] = np.mean((y - yhat)**2)
print(f" {d:2d} | {train_mse[d]:7.4f}")
# একঘেয়ে কমে -> train error দেখলে ভুলভাবে d=10 বাছা হয়
print("train-MSE-min degree (ভুল বাছাই):",
min(degrees, key=lambda d: train_mse[d])) # -> 10
# d=1->22.08, d=3->9.59, d=10->9.12 (canonical)
# ---------- 2. 10-fold CV (+ fold-জুড়ে SE) ----------
kf = KFold(n_splits=10, shuffle=True, random_state=20260619)
print("\ndegree | CV10 | SE")
cv10, se10 = {}, {}
for d in degrees:
fold_mse = []
for tr, te in kf.split(x):
Xtr, Xte = design(x[tr], d), design(x[te], d)
beta = ols_fit(Xtr, y[tr])
fold_mse.append(np.mean((y[te] - Xte @ beta)**2))
fold_mse = np.array(fold_mse)
cv10[d] = fold_mse.mean()
se10[d] = fold_mse.std(ddof=1) / np.sqrt(len(fold_mse))
print(f" {d:2d} | {cv10[d]:7.4f} | {se10[d]:.3f}")
d_cvmin = min(degrees, key=lambda d: cv10[d])
print("CV-min degree:", d_cvmin) # -> 3 (U-আকার)
# d=1->~22.7, d=3->~10.15 (MIN), d=10->~10.9 ; SE(d=3)~0.85 (canonical)
# ---------- 3. LOOCV (linear-smoother shortcut, একবার fit) ----------
print("\ndegree | LOOCV (shortcut)")
loocv = {}
for d in degrees:
X = design(x, d)
XtX_inv = np.linalg.inv(X.T @ X)
H = X @ XtX_inv @ X.T # hat / smoother matrix S
yhat = H @ y
Sii = np.diag(H)
loocv[d] = np.mean(((y - yhat) / (1 - Sii))**2)
print(f" {d:2d} | {loocv[d]:7.4f}")
print("LOOCV-min degree:", min(degrees, key=lambda d: loocv[d])) # -> 3
# d=3 -> ~10.18 (canonical min)
# --- যাচাই: সরাসরি leave-one-out (প্রতি বিন্দু re-fit) == shortcut ---
d_chk = 3
X = design(x, d_chk)
direct = np.empty(n)
for i in range(n):
m = np.ones(n, bool); m[i] = False
beta = ols_fit(X[m], y[m])
direct[i] = (y[i] - X[i] @ beta)**2
print(f"direct LOOCV (d={d_chk}) = {direct.mean():.4f} "
f"vs shortcut = {loocv[d_chk]:.4f} (অভিন্ন)")
# ---------- 4. one-standard-error rule ----------
thr = cv10[d_cvmin] + se10[d_cvmin] # 10.15 + 0.85 ≈ 11.0
d_1se = next(d for d in degrees if cv10[d] <= thr) # সবচেয়ে ছোট d
print(f"\none-SE threshold = {thr:.3f} -> বাছা degree = {d_1se}") # -> 3
# ---------- 5. honest test (স্বাধীন test-set) ----------
rng_test = np.random.default_rng(99999) # সম্পূর্ণ আলাদা state
n_test = 2000
x_te = rng_test.uniform(-3, 3, n_test)
y_te = (x_te**3 - 3*x_te) + rng_test.normal(0, 3, n_test)
beta3 = ols_fit(design(x, d_1se), y) # পূর্ণ training data-তে fit
test_mse = np.mean((y_te - design(x_te, d_1se) @ beta3)**2)
print(f"\nবাছা degree {d_1se}: test MSE = {test_mse:.4f} "
f"(sigma^2 = {sigma2}; CV ছিল {cv10[d_1se]:.4f})")
# test MSE ≈ 9.71 ≈ sigma^2=9 -> CV ছিল test error-এর সৎ অনুমান (canonical)
প্রত্যাশিত output (canonical, seed-সাপেক্ষ): train MSE — \(d{=}1\to22.08\), \(d{=}3\to9.59\), \(d{=}10\to9.12\) (একঘেয়ে কমে, তাই train-min ভুলভাবে \(d{=}10\)); 10-fold CV — \(d{=}1\to22.68\), \(d{=}3\to10.15\) (MIN, SE \(\approx0.85\)), \(d{=}10\to10.90\) (U-আকার), CV-min \(=d{=}3\); LOOCV-shortcut — min \(d{=}3\to10.18\), এবং direct leave-one-out মান shortcut-এর সাথে অভিন্ন; one-SE threshold \(=10.15+0.85=11.0\) ⇒ বাছা \(d{=}3\); honest test MSE (deg \(3\)) \(\approx9.71\approx\sigma^2=9\) ⇒ CV (\(10.15\)) ছিল test error-এর সৎ অনুমান। দ্রষ্টব্য: fold-শাফল ও test-state-এর random_state-এর ওপর শেষ দশমিক সামান্য বদলাতে পারে, কিন্তু সব সিদ্ধান্ত (train-min \(=10\), CV/LOOCV/one-SE-min \(=3\), test \(\approx\sigma^2\)) ও গল্প অপরিবর্