সমাধান — অধ্যায় ৬.৫ · Decision Trees, Bagging & Random Forests¶

অধ্যায় ফাইল: part-6-statistical-ml/06-05-trees-bagging-random-forests.md (§৭ অনুশীলনী)। চলমান dataset — seed-সূচক 20260619: make_classification(n_samples=600, n_features=20, n_informative=6, n_redundant=2), $70/30$ train–test split ($420$ train, $180$ test)। মূল notation: Gini $G_m=\sum_c\hat p_{mc}(1-\hat p_{mc})$, entropy $H_m=-\sum_c\hat p_{mc}\log_2\hat p_{mc}$, information gain $\Delta=I_{\text{parent}}-\sum_{\text{child}}\frac{N_{\text{child}}}{N}I_{\text{child}}$, bagging $\hat f_{\text{bag}}=\frac1B\sum_b\hat f_b$, $B$টি correlated গাছের গড়ের variance $\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$, OOB। canonical সংখ্যা। test accuracy: full (unpruned) tree $0.733$ (depth $10$, $51$ leaf; bootstrap sd $0.040$); depth-$3$ tree $0.794$; bagging ($B{=}300$) $0.822$; random forest ($B{=}300$) $0.839$, OOB $0.848$। RF n_estimators: $1\to0.711$, $5\to0.806$, $25\to0.844$, $300\to0.839$। feature importance (RF): idx4 $0.164$, idx6 $0.132$, idx15 $0.087$। §ঘ-এর runnable script (seed-সূচক 20260619) উপরের সংখ্যাগুলো পুনরুৎপাদন করে। গাণিতিক প্রশ্নের (৯–১৫) সংখ্যাগুলো স্বয়ংসম্পূর্ণ — অধ্যায়-dataset থেকে স্বাধীন।

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

সমাধান ১ (★)¶

(ক) leaf-prediction। classification-এ একটা leaf সেই leaf-এ পড়া training-বিন্দুদের majority class (সর্বাধিক-সংখ্যক শ্রেণি) দেয়; regression-এ সেই বিন্দুদের response-এর গড় ($\bar y_{\text{leaf}}$)। (প্রমাণ — সমাধান ১৫: এরাই respective loss-এর minimizer।)

(খ) axis-aligned split ও সিঁড়ি-boundary। প্রতিটি split-এর রূপ "$x_j\le t$?" — অর্থাৎ কেবল একটা feature-অক্ষের সমকোণে একটা সীমা টানা। তাই tree-এর গড়া প্রতিটি সীমানা-টুকরো কোনো-না-কোনো অক্ষের সমান্তরাল; একটা তির্যক (যেমন $x_1+x_2=1$) সীমাকে ধরতে অনেকগুলো ছোট অক্ষ-সমান্তরাল ধাপ লাগে — তাই decision boundary সিঁড়ির মতো (staircase), মসৃণ তির্যক রেখা নয়। (LDA-র মসৃণ তির্যক boundary-র সম্পূর্ণ বিপরীত।)

(গ) interpretability। প্রতিটি root→leaf পথ হলো এক সারি if-then শর্তের সংযোগ (AND) — যেমন "$x_4\le0.2$ এবং $x_6>1.1$ ⇒ class 1"। এটা মানুষ সরাসরি পড়তে ও যাচাই করতে পারে, তাই tree-কে "white-box" model বলা হয়।

সমাধান ২ (★)¶

(ক) চরম মান। pure node (সব বিন্দু এক শ্রেণি, ধরা যাক $\hat p=1$): $G=1(1-1)=0$, $H=-1\log_2 1=0$ — উভয় সর্বনিম্ন। $50$–$50$ binary node: $G=2(0.5)(0.5)=0.5$, $H=-2(0.5)\log_2 0.5=1$ — উভয় সর্বোচ্চ (binary-তে)। অর্থাৎ node যত বিশুদ্ধ, দুই measure-ই তত $0$-এর দিকে যায়; যত মিশ্র, তত বড়।

(খ) split-এর লক্ষ্য। split বাছা হয় যেটা children-এ weighted impurity সবচেয়ে কমায় — সমতুল্যভাবে যেটা information gain $\Delta=I_{\text{parent}}-\sum_{\text{child}}\frac{N_{\text{child}}}{N}I_{\text{child}}$ সর্বোচ্চ করে। (impurity কখনো বাড়ানো হয় না; greedy-ভাবে প্রতিটি node-এ স্থানীয়-সেরা split।)

(গ) Gini বনাম entropy। দুই measure একই monotone আচরণ দেখায় (বিশুদ্ধতায় $0$, $50$–$50$-তে চূড়া, একই দিকে বাড়ে-কমে), তাই কোন split সেরা সে-বিষয়ে প্রায় সবসময় একমত (সমাধান ১০-এ হাতে-গুনে দেখানো)। Gini-তে logarithm লাগে না বলে গণনায় সামান্য সস্তা — তাই CART/scikit-learn-এ Gini default (criterion='gini')।

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

(ক) কেন deep tree training-এ নিখুঁত। leaf-সংখ্যা বাড়লে প্রতিটি leaf কম-সংখ্যক বিন্দু ধরে; গাছ যথেষ্ট গভীর হলে চরমে প্রতি leaf-এ ১টা (বা একই-শ্রেণির কয়েকটা) বিন্দু — তখন গাছ প্রতিটি training-বিন্দুর label হুবহু মুখস্থ করে (noise সমেত), তাই training accuracy প্রায় $100\%$। চলমান উদাহরণে depth $10$, $51$ leaf-ই এই অতি-নমনীয়তার লক্ষণ।

(খ) high variance ও sd $0.040$। "high variance" = training-set সামান্য বদলালে গাছের গঠন ও prediction অনেক বদলায়। চলমান উদাহরণে $420$ training-বিন্দু বারবার bootstrap-resample করে গাছ গড়লে test accuracy sd $0.040$ নিয়ে ঘোরে — অর্থাৎ একই অন্তর্নিহিত data থেকে আলাদা নমুনায় গাছ স্থিতিশীল নয়; এই $\pm0.04$ ওঠানামাই high variance-এর সরাসরি, পরিমাণগত প্রমাণ।

(গ) pruning ($0.733\to0.794$) bias–variance ভাষায়। depth $10\to3$ করলে গাছের capacity কমে: variance অনেক কমে (অগভীর গাছ resample-এ অনেক বেশি স্থিতিশীল), bias সামান্য বাড়ে (কম leaf, কম-সূক্ষ্ম partition)। এখানে variance-পতন bias-বৃদ্ধিকে ছাপিয়ে যায়, তাই net test accuracy বাড়ে ($0.733\to0.794$, $+0.061$) — ৬.১-এর bias–variance tradeoff-এর ক্লাসিক উদাহরণ, এবং pruning-এর মূল যুক্তি।

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

(ক) স্বাধীন estimator। $B$টি স্বাধীন estimator (প্রতিটি variance $\sigma^2$) হলে গড়ের variance $=\frac{\sigma^2}{B}$ (স্বাধীন rv-র গড়ের সূত্র)। তাই $B\to\infty$-এ variance $\to0$ — যথেষ্ট গড় করলে noise সম্পূর্ণ মুছে যেত।

(খ) correlated estimator। বাস্তবে গাছগুলো একই data-র bootstrap বলে correlated (correlation $\rho>0$)। তখন গড়ের variance $\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$ (প্রমাণ — সমাধান ১৪)। $B\to\infty$-এ দ্বিতীয় পদ $\frac{1-\rho}{B}\sigma^2\to0$, কিন্তু থাকে $\rho\sigma^2$ — একটা floor। $\rho\sigma^2$ পদটা $B$-নিরপেক্ষ, তাই কেবল গাছ বাড়িয়ে এটা দূর করা যায় না।

(গ) bagging-এর সীমাবদ্ধতা ও RF-এর প্রেরণা। যেহেতু variance $\rho\sigma^2$-এর নিচে নামে না, গাছগুলো বেশি correlated ($\rho$ বড়) হলে bagging-এর variance-হ্রাস সীমিত — যত গাছই যোগ করি floor একই থাকে। তাই variance আরও কমাতে হলে $\sigma^2$ বা $B$ নয়, $\rho$ কমাতে হবে; random forest ঠিক এটাই করে (feature-subsampling দিয়ে গাছ decorrelate করে), যা পরের সমাধানের বিষয়।

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

(ক) feature-subsampling ও $\rho$। RF প্রতিটি split-এ এলোমেলো $m=\sqrt{p}$টি feature থেকে সেরা split খোঁজে। এতে গাছগুলো আলাদা-আলাদা feature-সেট ব্যবহার করতে বাধ্য হয়, তাই একে অন্যের চেয়ে আলাদা — pairwise correlation $\rho$ কমে। subsampling না থাকলে (bagging) একটা খুব-শক্তিশালী feature প্রায় সব গাছের root-এ বসত, ফলে গাছগুলো একইরকম হত (উচ্চ $\rho$) — feature-subsampling এই "প্রভাবশালী-feature-এর একনায়কত্ব" ভাঙে।

(খ) floor নামা। variance-সূত্র $\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$-এ floor $=\rho\sigma^2$। $\rho$ ছোট হলে floor ছোট, তাই $B$ বাড়ালে variance bagging-এর floor-এরও নিচে নামতে পারে — RF-এর variance-floor bagging-এর floor-এর নিচে (সমাধান ১১-গ-তে $\rho{=}0.5$ বনাম $\rho{=}0.05$-এ পরিমাণগত তুলনা)।

(গ) canonical সঙ্গতি। চলমান উদাহরণে bagging $0.822$, RF $0.839$ — এই $+0.017$ উন্নতি ঠিক decorrelation-লাভ: কম $\rho$ ⇒ গড় করার পর কম residual variance ⇒ বেশি accuracy। $p=20$-এ default $m=\sqrt{20}\approx4$ feature প্রতি split — যথেষ্ট subsampling যাতে $\rho$ কমে, তবু যথেষ্ট feature যাতে প্রতিটি গাছ অর্থবহ থাকে।

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

(ক) OOB-অনুপাত। একটা নির্দিষ্ট বিন্দু একটা size-$n$ bootstrap-এ একবার তোলায় নির্বাচিত-না-হওয়ার সম্ভাবনা $1-\frac1n$; $n$বার স্বাধীন তোলায় কখনো-না-আসার সম্ভাবনা $(1-\frac1n)^n$। $n\to\infty$-এ এটা $e^{-1}\approx0.368$-এ যায় (standard limit)। তাই প্রতিটি গাছের জন্য গড়ে $\approx36.8\%$ ($\approx37\%$) বিন্দু OOB, বাকি $\approx63.2\%$ in-bag।

(খ) কেন honest। OOB বিন্দুগুলো ওই গাছের bootstrap-নমুনায় ছিল না, তাই গাছ তাদের training-এ দেখেনি। তাদের উপর prediction-এ তাই data-leak নেই — held-out test-বিন্দুর মতোই নিরপেক্ষ। প্রতিটি বিন্দুর OOB-prediction নিতে কেবল সেই গাছগুলোর ভোট নেওয়া হয় যারা তাকে দেখেনি; সব বিন্দুর OOB-prediction একসাথে নিলে পুরো training-set-এর উপর একটা প্রায়-unbiased generalization-error পাওয়া যায়।

(গ) canonical ও সুবিধা। OOB accuracy $0.848$ আর held-out test accuracy $0.839$ — দুটোই একই (অদেখা) data-র উপর error মাপছে, তাই কাছাকাছি (পার্থক্য $0.009$, sd $0.040$-এর তুলনায় তুচ্ছ)। ব্যবহারিক সুবিধা: OOB বিনামূল্যে আসে (training-এরই পার্শ্বফল) — আলাদা validation set আলাদা করে রাখার বা $k$-fold CV-র অতিরিক্ত গণনা-খরচ ছাড়াই RF-এর accuracy অনুমান ও hyperparameter (যেমন $m$, max_depth) tuning করা যায়।

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

(ক) $0.164$-এর অর্থ। importance normalize-করা (সব feature-এর যোগ $1$), তাই idx4-এর $0.164$ = সব গাছ জুড়ে মোট impurity-হ্রাসের $16.4\%$ এসেছে idx4-এর split-গুলো থেকে — অর্থাৎ সিদ্ধান্তে idx4-এর আপেক্ষিক অবদান, সরাসরি "accuracy-র $16.4\%$" নয়।

(খ) informative-feature চেনা। informative feature-রা label-এর সাথে প্রকৃত সম্পর্ক রাখে বলে তারা split-এ বেশি impurity কমায়, তাই বড় importance পায় (idx4, idx6 শীর্ষে — এরা $6$টি informative feature-এর মধ্যে)। pure-noise feature-রা কম কমায়, তাই নিচে। redundant feature (informative-এর linear combination) informative-এর correlated, তাই তারা importance "ভাগ করে নেয়" — কোনো একক feature-এর importance তার সত্যিকার গুরুত্বের চেয়ে সামান্য কম দেখাতে পারে (correlated-feature-dilution)।

(গ) bias (পক্ষপাত) ও permutation importance। impurity-based importance high-cardinality / many-split-সম্ভব (continuous বা বহু-level categorical) feature-কে অযথা বেশি গুরুত্ব দেয় — শুধু বেশি split-সুযোগ থাকায় তারা আকস্মিকভাবে impurity-হ্রাসের ভাগ পায়, সত্যিকার গুরুত্ব ছাড়াই। permutation importance বিকল্পটি ভালো: একটা feature-এর মান এলোমেলোভাবে অদলবদল (permute) করে দেখা হয় test/OOB-accuracy কতটা পড়ে — সত্যিই গুরুত্বপূর্ণ feature permute করলে accuracy অনেক পড়ে; এটা split-গণনার পক্ষপাত এড়ায়।

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

(ক) দ্রুত উন্নতি ($1\to25$)। শুরুতে ($B$ ছোট) variance-সূত্রের $\frac{1-\rho}{B}\sigma^2$ পদ ($1/B$ হারে) দ্রুত নামে — অল্প গাছ গড় করলেই variance অনেকটা পড়ে, তাই accuracy $0.711\to0.844$ দ্রুত ওঠে।

(খ) স্যাচুরেশন ($25\to300$)। $B$ বড় হলে $\frac{1-\rho}{B}\sigma^2\to0$, variance তার floor $\rho\sigma^2$-এ পৌঁছে যায়। তখন আরও গাছ যোগ করলে variance প্রায় আর কমে না, তাই accuracy কার্যত সমতল: $0.844$ ($B{=}25$) ও $0.839$ ($B{=}300$) — পার্থক্যটা সত্যিকার উন্নতি নয়, নমুনা-ওঠানামা।

(গ) আরও গাছ overfit করায় না। প্রতিটি গাছ স্বাধীন bootstrap + feature-subset-এ গড়া; গড় করা কেবল variance কমায়, কখনো bias বাড়ায় না, আর বেশি গাছ মানে শুধু গড়ে আরও বিন্দু (variance floor-এ স্থির)। তাই n_estimators একটা "যত-বেশি-তত-ভালো (বা সমান)" knob — boosting-এর বিপরীতে এখানে গাছ বাড়ালে overfit-ঝুঁকি নেই, কেবল গণনা-খরচ বাড়ে। (boosting-এ গাছ ক্রমিকভাবে error fit করে বলে অতিরিক্ত গাছ overfit করাতে পারে — ৬.৬।)

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

সমাধান ৯ (★)¶

node: $6$A, $4$B, মোট $N=10$; $\hat p_A=0.6,\ \hat p_B=0.4$।

(ক) Gini। $$ G=\hat p_A(1-\hat p_A)+\hat p_B(1-\hat p_B)=0.6(0.4)+0.4(0.6)=0.24+0.24=\mathbf{0.48}. $$

(খ) entropy। $\log_2 0.6=-0.737,\ \log_2 0.4=-1.322$, তাই $$ H=-(0.6\log_2 0.6+0.4\log_2 0.4)=-(0.6(-0.737)+0.4(-1.322))=0.442+0.529=\mathbf{0.971}. $$

(গ) $9$A–$1$B। $\hat p_A=0.9$: $G=0.9(0.1)+0.1(0.9)=0.09+0.09=\mathbf{0.18}<0.48$। node বেশি বিশুদ্ধ (এক শ্রেণির স্পষ্ট প্রাধান্য) ⇒ impurity কম — impurity-র অর্থের সাথে সঙ্গতিপূর্ণ (যত একপেশে, তত $0$-এর কাছে)।

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

parent: $6$A–$4$B, $N=10$, $G_{\text{parent}}=0.48$, $H_{\text{parent}}=0.971$ (সমাধান ৯)।

(ক) Gini-gain।

Split 1 — বাঁ $[4\text{A},0\text{B}]$ ($N_L=4$), ডান $[2\text{A},4\text{B}]$ ($N_R=6$): $$ G_L=0\ (\text{pure}),\quad G_R=2\cdot\tfrac26\cdot\tfrac46=2(0.333)(0.667)=0.444. $$ weighted child Gini $=\tfrac4{10}(0)+\tfrac6{10}(0.444)=0.267$; তাই $$ \Delta_{\text{Gini}}^{(1)}=0.48-0.267=\mathbf{0.213}. $$

Split 2 — বাঁ $[3\text{A},1\text{B}]$ ($N_L=4$), ডান $[3\text{A},3\text{B}]$ ($N_R=6$): $$ G_L=2\cdot\tfrac34\cdot\tfrac14=0.375,\quad G_R=2(0.5)(0.5)=0.5. $$ weighted $=\tfrac4{10}(0.375)+\tfrac6{10}(0.5)=0.15+0.30=0.45$; তাই $$ \Delta_{\text{Gini}}^{(2)}=0.48-0.45=\mathbf{0.03}. $$

(খ) information gain (entropy)।

Split 1: $H_L=0$; $H_R=-(\tfrac26\log_2\tfrac26+\tfrac46\log_2\tfrac46)=-(0.333(-1.585)+0.667(-0.585))=0.528+0.390=0.918$। weighted $=0.6(0.918)=0.551$; $\text{IG}^{(1)}=0.971-0.551=\mathbf{0.42}$।

Split 2: $H_L=-(\tfrac34\log_2\tfrac34+\tfrac14\log_2\tfrac14)=-(0.75(-0.415)+0.25(-2))=0.311+0.5=0.811$; $H_R=1$ ($3$–$3$)। weighted $=0.4(0.811)+0.6(1)=0.324+0.6=0.924$; $\text{IG}^{(2)}=0.971-0.924=\mathbf{0.046}$।

(গ) বাছাই। Split 1 বাছা হবে — উভয় measure-এ gain অনেক বড় ($\Delta_{\text{Gini}}:0.213\gg0.03$; $\text{IG}:0.42\gg0.046$), কারণ Split 1 একটা সম্পূর্ণ pure child ($4$A–$0$B) বানায়, impurity সবচেয়ে কমায়। দুই impurity-measure একই split-এ একমত (সমাধান ২গ-র সাধারণ নিয়মের নিশ্চিতকরণ)।

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

$\sigma^2=1$; $V(B)=\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$।

(ক) $\rho=0.5$। $$ V(1)=0.5+\tfrac{0.5}{1}=\mathbf{1.0},\quad V(10)=0.5+\tfrac{0.5}{10}=\mathbf{0.55},\quad V(100)=0.5+\tfrac{0.5}{100}=\mathbf{0.505}. $$

(খ) floor। $B\to\infty$: $\frac{1-\rho}{B}\sigma^2\to0$, তাই floor $=\rho\sigma^2=\mathbf{0.5}$। $V(100)=0.505$, যা floor-এর $\frac{0.505-0.5}{0.5}=1\%$ মধ্যে — তাই $B=100$ কার্যত floor-এ পৌঁছে দেয়; এর পরে আরও গাছে variance-এ নগণ্য লাভ (n_estimators-স্যাচুরেশনের গাণিতিক ব্যাখ্যা, সমাধান ৮)।

(গ) $\rho=0.05$ (RF-সদৃশ)। $$ \text{floor}=\rho\sigma^2=\mathbf{0.05},\qquad V(100)=0.05+\tfrac{0.95}{100}=0.05+0.0095=\mathbf{0.0595}. $$ bagging-এর $V(100)=0.505$-এর তুলনায় RF-এর $0.0595$ প্রায় $1/8.5$ গুণ variance — কেবল $\rho$ $0.5\to0.05$ নামিয়েই। এটাই random forest-এর মূল শক্তি: $\sigma^2$ বা $B$ নয়, $\rho$ আক্রমণ করে variance নাটকীয়ভাবে কমানো।

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

(ক) OOB-অনুপাত। $$ (1-\tfrac15)^5=0.8^5=0.328,\quad (1-\tfrac1{100})^{100}=0.366,\quad (1-\tfrac1{600})^{600}=0.368. $$ দ্রুত $e^{-1}=0.368$-এ স্থির; তাই প্রতিটি গাছে গড়ে $\approx36.8\%$ ($\approx37\%$) বিন্দু OOB।

(খ) $n_{\text{train}}=420$। OOB গড়ে $\approx0.368\times420\approx\mathbf{155}$ বিন্দু; in-bag (স্বতন্ত্র) $\approx0.632\times420\approx\mathbf{265}$ বিন্দু (with-replacement বলে কিছু বিন্দু একাধিকবার, কিন্তু স্বতন্ত্র in-bag $\approx63\%$)।

(গ) $m=\sqrt p$। $p=20$: $m=\sqrt{20}=4.47\to\mathbf{4}$ feature প্রতি split (scikit-learn floor/sqrt default)। $m=p=20$ নিলে প্রতিটি split সব feature দেখে — তখন আর feature-subsampling নেই, RF bagging-এ পরিণত হয় (গাছগুলো আবার বেশি correlated, $\rho$ বড়; সমাধান ৫ক)।

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

মডেল	test accuracy
single full tree (depth 10)	0.733
single tree depth 3	0.794
RF, $B=1$	0.711
RF, $B=5$	0.806
RF, $B=25$	0.844
bagging, $B=300$	0.822
RF, $B=300$	0.839
RF OOB ($B=300$)	0.848

(ক) $B=1$ RF ($0.711$) < full tree ($0.733$)। $B=1$-এ RF একটাই গাছ, কিন্তু সেটা একটা single bootstrap-নমুনায় ($\approx265$ স্বতন্ত্র বিন্দু, পুরো $420$ নয়) এবং প্রতি split-এ কেবল $m=\sqrt p\approx4$ feature দেখে গড়া — কম-data, সীমিত-feature-পছন্দ ⇒ একটা সাধারণ full tree (যে পুরো $420$ ও সব $20$ feature পায়)-এর চেয়েও দুর্বল। ensemble-এর গড়-লাভ এখনো শুরু হয়নি; randomization শুধু একক গাছকে দুর্বল করেছে, ক্ষতিপূরণকারী গড় নেই।

(খ) লাভ-বিভাজন। single best tree (depth-3, $0.794$) → RF-$300$ ($0.839$): মোট লাভ $0.839-0.794=\mathbf{0.045}$। এর মধ্যে — bagging-অংশ (variance-হ্রাস, গড়): $0.822-0.794=0.028$; decorrelation-অংশ (feature-subsampling, $\rho$↓): $0.839-0.822=0.017$। অর্থাৎ লাভের প্রায় দুই-তৃতীয়াংশ গড়-করা থেকে, এক-তৃতীয়াংশ decorrelation থেকে।

(গ) OOB ($0.848$) > test ($0.839$)। এটা OOB-কে অবিশ্বাস্য করে না — দুটোই একই সত্য generalization-accuracy-র চারপাশে নমুনা-অনুমান, ভিন্ন (অদেখা) উপসেটের উপর মাপা। full tree-এর bootstrap sd $0.040$ দেখায় এ ধরনের accuracy-পরিমাপে $\pm0.04$ ওঠানামা স্বাভাবিক; তাই $0.848$ বনাম $0.839$-এর $0.009$ ব্যবধান এই গোলমালের অনেক ভেতরে — দুটোই কার্যত একই সত্য-হারের অনুমান।

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

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

দেওয়া: $\operatorname{Var}(\hat f_b)=\sigma^2$ সবার জন্য, $\operatorname{Cov}(\hat f_b,\hat f_{b'})=\rho\sigma^2$ for $b\ne b'$ (কারণ $\operatorname{Corr}=\rho$ ⇒ $\operatorname{Cov}=\rho\sqrt{\sigma^2}\sqrt{\sigma^2}=\rho\sigma^2$)।

(ক) দ্বৈত-যোগ ভাঙা। variance-এর bilinearity থেকে $$ \operatorname{Var}!\Big(\tfrac1B\sum_{b=1}^B\hat f_b\Big)=\tfrac1{B^2}\sum_{b=1}^B\sum_{b'=1}^B\operatorname{Cov}(\hat f_b,\hat f_{b'}). $$ এই $B\times B$ যোগে: - diagonal ($b=b'$): $B$টি পদ, প্রতিটি $\operatorname{Cov}(\hat f_b,\hat f_b)=\operatorname{Var}(\hat f_b)=\sigma^2$ — মোট $B\sigma^2$। - off-diagonal ($b\ne b'$): $B^2-B=B(B-1)$টি পদ, প্রতিটি $\rho\sigma^2$ — মোট $B(B-1)\rho\sigma^2$।

(খ) বসিয়ে সরলীকরণ। $$ \operatorname{Var}(\hat f_{\text{bag}})=\tfrac1{B^2}\big[B\sigma^2+B(B-1)\rho\sigma^2\big] =\tfrac{\sigma^2}{B}+\tfrac{B-1}{B}\rho\sigma^2. $$ এখন $\frac{B-1}{B}=1-\frac1B$, তাই $$ =\tfrac{\sigma^2}{B}+\rho\sigma^2-\tfrac{\rho\sigma^2}{B} =\rho\sigma^2+\tfrac{1-\rho}{B}\sigma^2.\qquad\blacksquare $$

(গ) $B\to\infty$ ও RF। দ্বিতীয় পদ $\frac{1-\rho}{B}\sigma^2\to0$, তাই $\operatorname{Var}(\hat f_{\text{bag}})\to\rho\sigma^2$ — একটা ধনাত্মক floor (যখন $\rho>0$) যা $B$-নিরপেক্ষ। স্বজ্ঞা: গড় করা estimator-গুলোর "স্বাধীন/idiosyncratic" অংশ মুছে দেয় ($1/B$ পদ), কিন্তু তাদের ভাগাভাগি-করা (correlated) অংশ মোছে না — সেটাই $\rho\sigma^2$ হয়ে টিকে থাকে। তাই variance আরও কমাতে হলে গাছ বাড়িয়ে নয়, $\rho$ কমিয়ে; random forest feature-subsampling দিয়ে ঠিক এই $\rho$ পদটাই আক্রমণ করে (যে কারণে RF-এর floor bagging-এর floor-এর নিচে — সমাধান ১১গ)।

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

একটা স্থির leaf-এ পড়া training-বিন্দু $\{(x_i,y_i):i\in\text{leaf}\}$, $N=\lvert\text{leaf}\rvert$; tree সবাইকে একটাই মান $c$ দেয়।

(ক) Regression — squared loss। $L(c)=\sum_{i\in\text{leaf}}(y_i-c)^2$। $$ \frac{dL}{dc}=\sum_{i}-2(y_i-c)=-2\Big(\sum_i y_i-Nc\Big)=0\ \Rightarrow\ \sum_i y_i=Nc\ \Rightarrow\ c=\tfrac1N\sum_{i\in\text{leaf}}y_i=\bar y_{\text{leaf}}. $$ $\frac{d^2L}{dc^2}=2N>0$ ⇒ convex ⇒ এই critical point global minimum। তাই optimal leaf-prediction = response-গড়।

(খ) Classification — 0–1 loss। সব বিন্দুকে একই class $c$ দিলে ভুল-গণনা $L(c)=\sum_{i\in\text{leaf}}\mathbf 1[y_i\ne c]=N-n_c$, যেখানে $n_c=$ leaf-এ class $c$-এর বিন্দু-সংখ্যা। $L(c)$ সর্বনিম্ন হয় যখন $n_c$ সর্বোচ্চ, অর্থাৎ $c=\arg\max_c n_c=$ majority class (সর্বাধিক-সংখ্যক শ্রেণি)। তাই optimal leaf-prediction = majority vote।

(গ) স্বজ্ঞা। leaf-এর ভেতরে আর কোনো splitting-feature বাকি নেই (গাছ এই অঞ্চলকে আর ভাঙছে না), তাই সব বিন্দু decision-এর দৃষ্টিতে "একইরকম"; তখন সেরা একক উত্তর = বিন্দুদের কেন্দ্রীয় প্রবণতা — squared loss-এ যা mean (গড়), 0–1 loss-এ যা mode (majority)। দুই ফল একই নীতির দুই রূপ: "আর কোনো তথ্য না থাকলে, loss-অনুযায়ী কেন্দ্রীয় সারসংক্ষেপটাই predict করো।" $\blacksquare$

ঘ · কোডিং (Python)¶

সমাধান ১৬ (★★★) — পূর্ণ runnable script¶

নিচের script seed-সূচক 20260619 দিয়ে §৭-এর সব canonical সংখ্যা পুনরুৎপাদন করে। (সংখ্যাগুলো scikit-learn-এর সাধারণ সংস্করণে স্থিতিশীল; ক্ষুদ্র সংস্করণ-ভেদে শেষ অঙ্কে সামান্য হেরফের সম্ভব, কিন্তু গল্প — full tree দুর্বল ও অস্থির → pruning সাহায্য করে → bagging গড় করে variance কমায় → RF decorrelate করে আরও কমায় → OOB ≈ test → কয়েকটি informative feature প্রাধান্য — অপরিবর্তিত।)

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import BaggingClassifier, RandomForestClassifier
from sklearn.metrics import accuracy_score

SEED = 20260619

# --- canonical dataset ---
X, y = make_classification(
    n_samples=600, n_features=20, n_informative=6, n_redundant=2,
    random_state=SEED,
)
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.30, random_state=SEED,
)
print(f"train={Xtr.shape[0]}, test={Xte.shape[0]}")          # 420, 180

# --- 1. single decision tree: full (unpruned) vs depth-3 ---
full = DecisionTreeClassifier(random_state=SEED).fit(Xtr, ytr)
acc_full = accuracy_score(yte, full.predict(Xte))
print(f"full tree : acc={acc_full:.3f}, depth={full.get_depth()}, "
      f"leaves={full.get_n_leaves()}")                       # ~0.733, 10, 51

d3 = DecisionTreeClassifier(max_depth=3, random_state=SEED).fit(Xtr, ytr)
acc_d3 = accuracy_score(yte, d3.predict(Xte))
print(f"depth-3   : acc={acc_d3:.3f}")                       # ~0.794  (pruning helps)

# --- 2. bagging (300 unpruned trees) ---
bag = BaggingClassifier(
    estimator=DecisionTreeClassifier(random_state=SEED),
    n_estimators=300, random_state=SEED,
).fit(Xtr, ytr)
acc_bag = accuracy_score(yte, bag.predict(Xte))
print(f"bagging   : acc={acc_bag:.3f}")                      # ~0.822

# --- 3. random forest (300) with OOB ---
rf = RandomForestClassifier(
    n_estimators=300, oob_score=True, random_state=SEED,
).fit(Xtr, ytr)
acc_rf = accuracy_score(yte, rf.predict(Xte))
print(f"RF(300)   : test={acc_rf:.3f}, OOB={rf.oob_score_:.3f}")  # ~0.839, ~0.848

# --- 4. n_estimators curve (gain saturates, never hurts) ---
print("n_estimators curve:")
for B in [1, 5, 25, 300]:
    rfB = RandomForestClassifier(n_estimators=B, random_state=SEED).fit(Xtr, ytr)
    print(f"  B={B:>3}: acc={accuracy_score(yte, rfB.predict(Xte)):.3f}")
# 1->0.711, 5->0.806, 25->0.844, 300->0.839

# --- 5. feature importance (top 3) ---
imp = rf.feature_importances_
top3 = np.argsort(imp)[::-1][:3]
print("top-3 importances:")
for j in top3:
    print(f"  idx{j}: {imp[j]:.3f}")
# idx4 ~0.164, idx6 ~0.132, idx15 ~0.087

# --- 6. (optional) bootstrap sd of single full tree => high variance ---
rng = np.random.default_rng(SEED)
n = Xtr.shape[0]
accs = []
for _ in range(30):
    idx = rng.integers(0, n, size=n)            # bootstrap resample of train
    t = DecisionTreeClassifier(random_state=SEED).fit(Xtr[idx], ytr[idx])
    accs.append(accuracy_score(yte, t.predict(Xte)))
print(f"single-tree bootstrap sd = {np.std(accs):.3f}")      # ~0.040  (high variance)

প্রত্যাশিত আউটপুট (সারসংক্ষেপ):

train=420, test=180
full tree : acc=0.733, depth=10, leaves=51
depth-3   : acc=0.794
bagging   : acc=0.822
RF(300)   : test=0.839, OOB=0.848
n_estimators curve:
  B=  1: acc=0.711
  B=  5: acc=0.806
  B= 25: acc=0.844
  B=300: acc=0.839
top-3 importances:
  idx4: 0.164
  idx6: 0.132
  idx15: 0.087
single-tree bootstrap sd = 0.040

পাঠ-সারাংশ। (i) single full tree training-এ প্রায়-নিখুঁত হলেও test-এ মাত্র $0.733$ ও bootstrap sd $0.040$ — high variance; depth-$3$-এ ছেঁটে $0.794$ (variance↓, bias সামান্য↑, net লাভ)। (ii) bagging $300$টি গাছ গড় করে $0.822$ — গড়-করা variance কমায়, কিন্তু গাছগুলো correlated বলে floor-এ আটকায়। (iii) random forest feature-subsampling ($m=\sqrt{20}\approx4$) দিয়ে গাছ decorrelate করে $0.839$ — bagging-এর চেয়ে $+0.017$, এবং OOB $0.848$ বিনামূল্যে validation দেয় (≈ test)। (iv) n_estimators বাড়ালে gain দ্রুত উঠে স্যাচুরেট করে ($1\to0.711$ … $25\to0.844\approx300\to0.839$) — আরও গাছ কখনো ক্ষতি করে না। (v) importance কয়েকটি informative feature-কে (idx4, idx6, idx15) সঠিকভাবে শীর্ষে তোল