সমাধান — অধ্যায় ৬.৬ · Boosting: AdaBoost & Gradient Boosting¶

অধ্যায় ফাইল: part-6-statistical-ml/06-06-boosting-adaboost-gradient.md (§৭ অনুশীলনী)। চলমান dataset — seed-সূচক 20260619 (৬.৫-এর অভিন্ন dataset): make_classification(n_samples=600, n_features=20, n_informative=6, n_redundant=2, class_sep=0.8, flip_y=0.05), $70/30$ train–test split ($420$ train, $180$ test)। মূল notation: additive model $F_T(x)=\sum_t\alpha_t h_t(x)$; AdaBoost weighted error $\varepsilon_t=\sum_i w_i\,\mathbf 1[h_t(x_i)\ne y_i]$, learner-ওজন $\alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}$; reweighting $w_i\leftarrow w_i\exp(\mp\alpha_t)$ (ঠিক/ভুল); gradient-boosting pseudo-residual $r_i=-\big[\partial L/\partial F(x_i)\big]_{F=F_{t-1}}$; আপডেট $F_t=F_{t-1}+\nu\,h_t$, learning rate (shrinkage) $\nu$। canonical সংখ্যা। test accuracy: decision stump (depth-$1$) $0.739$ (weak learner)। AdaBoost (stump base), n_estimators $1\to0.739$, $10\to0.789$, $50\to\mathbf{0.850}$ (চূড়া), $100\to0.794$, $200\to0.783$, $500\to0.778$ (চূড়ার পর পতন)। GradientBoosting ($n{=}200$, lr $0.1$, depth $3$): train $1.000$ / test $0.850$ (overfit-চিহ্ন)। RF ($300$): $0.839$ (তুলনা)। GB learning-rate sweep ($n{=}200$, depth $3$): lr $0.01\to0.794$, $0.05\to0.833$, $0.1\to0.850$, $0.5\to0.844$, $1.0\to0.878$। §ঘ-এর runnable script (seed-সূচক 20260619) উপরের সংখ্যাগুলো পুনরুৎপাদন করে। গাণিতিক প্রশ্নের (৭–৯, ১২–১৩) সংখ্যাগুলো স্বয়ংসম্পূর্ণ — অধ্যায়-dataset থেকে স্বাধীন। সব log natural log ($\ln$)।

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

সমাধান ১ (★)¶

(ক) weak learner-এর আনুষ্ঠানিক সংজ্ঞা। weak learner হলো এমন একটা classifier যার error random guessing-এর চেয়ে ধারাবাহিকভাবে একটু কম — binary-তে random guessing-এর error $0.5$, তাই শর্ত $\varepsilon<0.5$ (chance-এর চেয়ে ভালো, যত সামান্যই হোক)। চলমান উদাহরণে decision stump (depth-$1$) test accuracy $0.739$, অর্থাৎ error $1-0.739=0.261<0.5$ — দুর্বল (একটা মাত্র split, সবেমাত্র data ভাগ করে) কিন্তু chance-এর স্পষ্ট ভালো, তাই বৈধ weak learner। boosting-এর তত্ত্ব বলে এমন weak learner-কে ক্রমিকভাবে যথেষ্ট যোগ করলে যেকোনো-নিম্ন training-error-এর strong learner বানানো সম্ভব।

(খ) পরস্পর-নির্ভর, তাই parallel নয়। boosting-এ গাছগুলো পরস্পর-নির্ভর (sequential/dependent) — $h_t$ গড়তে আগের সমষ্টি $F_{t-1}$-এর তথ্য লাগে: AdaBoost-এ $F_{t-1}$-এর ভুল থেকে reweighted data ($w_i^{(t)}$), gradient boosting-এ $F_{t-1}$-এর residual/negative-gradient ($r_i^{(t)}$)। যেহেতু $h_t$-এর training-target নিজেই $h_{t-1}$ শেষ হওয়ার পর-ই নির্ধারিত হয়, $h_{t-1}$ সম্পূর্ণ না হলে $h_t$ শুরুই করা যায় না — গাছগুলো একটা শৃঙ্খলে বাঁধা, তাই সমান্তরালে (parallel) train করা যায় না। (bagging/RF-এর গাছগুলো স্বাধীন বলে চাইলেই সব একসাথে parallel train করা যায় — সরাসরি বৈসাদৃশ্য।)

(গ) bias কমায়; তাই weak/high-bias base। boosting মূলত bias কমায় (bagging variance কমায় — বিপরীত)। weak/high-bias/low-variance base learner (অগভীর stump) বাছা হয় কারণ প্রতিটি round ক্রমিকভাবে সামান্য সংশোধন যোগ করে ensemble-এর capacity ধীরে-ধীরে বাড়ায়; low-variance base দিয়ে শুরু করলে যোগফল প্রথমে underfit থাকে, তারপর round-এর পর round bias কমে — RF-এর low-bias/high-variance deep tree (যা গড় করে variance কমাতে হয়)-এর ঠিক উল্টো নকশা।

সমাধান ২ (★)¶

দিক	bagging / random forest	boosting
(ক) গাছ গড়ার ক্রম	সমান্তরাল ও স্বাধীন — প্রতিটি গাছ আলাদা bootstrap-এ, পরস্পর-নিরপেক্ষ	ক্রমিক ও নির্ভরশীল — প্রতিটি গাছ আগের সমষ্টির ভুলের উপর গড়া
(খ) base learner	গভীর, low-bias/high-variance tree (গড় করার জন্য)	অগভীর, high-bias/low-variance weak learner (stump, যোগ করার জন্য)
(গ) যে error কমে	মূলত variance (bias প্রায় অপরিবর্তিত)	মূলত bias (ক্রমিকভাবে ভুল সংশোধন)
(ঘ) আরও গাছ যোগের নিরাপত্তা	নিরাপদ — variance শুধু কমে/স্থির, কখনো overfit করায় না	ঝুঁকিপূর্ণ — অতিরিক্ত round training-noise fit করে overfit করাতে পারে

(ঘ)-এর canonical দৃষ্টান্ত: RF n_estimators বাড়ালে accuracy স্যাচুরেট করে স্থির ($25\to0.844\approx300\to0.839$, ৬.৫), কিন্তু AdaBoost $50\to\mathbf{0.850}$ চূড়ার পর পড়ে যায় ($500\to0.778$)। এক বাক্যে: bagging সমান্তরালে গড় করে variance শান্ত করে; boosting ক্রমিকভাবে যোগ করে bias আক্রমণ করে — দুই বিপরীত ensemble-দর্শন, একই base ingredient (tree) দিয়ে।

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

learner-ওজন $\alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}$, $\varepsilon_t$ = weighted error।

(ক) ভালো learner ⇒ বড় $\alpha$ ⇒ বেশি প্রভাব। $\varepsilon_t$ ছোট হলে $\frac{1-\varepsilon_t}{\varepsilon_t}$ বড় (হর ছোট, লব $\to1$), তাই $\log$ বড়, তাই $\alpha_t$ বড়। final additive vote $F_T(x)=\sum_t\alpha_t h_t(x)$-এ বড় $\alpha_t$ মানে ওই learner-এর সিদ্ধান্ত বেশি ওজন পায় — অর্থাৎ ভালো (কম-error) learner final সিদ্ধান্তে বেশি প্রভাব রাখে। স্বজ্ঞাত: যে learner বেশি নির্ভরযোগ্য, তাকে বেশি ভোট-ওজন দেওয়াই যৌক্তিক।

(খ) $\varepsilon_t=0.5$ ⇒ $\alpha_t=0$, কোনো অবদান নয়। $\frac{1-0.5}{0.5}=1$, $\log 1=0$, তাই $\alpha_t=\tfrac12\cdot0=\mathbf{0}$। final vote-এ এই learner-এর পদ $0\cdot h_t(x)=0$ — chance-সমান learner কোনো অবদানই রাখে না। এটা স্বজ্ঞাত: $\varepsilon=0.5$ মানে learner-টা মুদ্রা-নিক্ষেপের চেয়ে ভালো কিছু বলছে না (তথ্যহীন), তাই ensemble-এ তার কথা শোনার কারণ নেই।

(গ) $\varepsilon_t\to0$ ⇒ $\alpha_t\to+\infty$; $\varepsilon_t>0.5$ ⇒ $\alpha_t<0$। প্রায়-নিখুঁত learner ($\varepsilon_t\to0$): $\frac{1-\varepsilon_t}{\varepsilon_t}\to\infty$, তাই $\alpha_t\to+\infty$ — ensemble এমন learner-কে কার্যত একতরফা বিপুল ওজন দেয় (একাই প্রায় সিদ্ধান্ত নেয়)। chance-এর চেয়ে খারাপ learner ($\varepsilon_t>0.5$): $\frac{1-\varepsilon_t}{\varepsilon_t}<1$, তাই $\log<0$, তাই $\alpha_t<0$ (ঋণাত্মক চিহ্ন)। ঋণাত্মক $\alpha_t$ মানে final vote-এ $\alpha_t h_t$ পদটা learner-এর সিদ্ধান্ত উল্টে নেয় — একটা ধারাবাহিকভাবে-ভুল (anti-correlated) learner-ও কাজে লাগে, কারণ তার উত্তর উল্টে দিলে সেটা chance-এর চেয়ে ভালো হয়ে যায়।

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

reweighting: ভুলের জন্য $w_i\leftarrow w_i e^{\alpha_t}$, ঠিকের জন্য $w_i\leftarrow w_i e^{-\alpha_t}$, তারপর normalize।

(ক) ভুল-বিন্দুর ওজন বাড়ানো ⇒ পরের learner সেখানে মন দেয়। পরের weak learner $h_{t+1}$ বাছা হয় weighted error $\sum_i w_i\mathbf 1[h(x_i)\ne y_i]$ সর্বনিম্ন করে। ভুল-শ্রেণিবদ্ধ বিন্দুর ওজন বাড়ালে সেই বিন্দুগুলো এই weighted objective-এ বেশি "দামি" হয়, তাই $h_{t+1}$ তাদের ঠিক করার দিকে অগ্রাধিকার দেয় — অর্থাৎ যেখানে ensemble এখনো দুর্বল (এখনো ভুল করছে) ঠিক সেখানেই পরের learner মনোযোগ দেয়। এভাবে প্রতিটি round আগের round-এর ফাঁক পূরণ করে।

(খ) $\alpha_t>0$ ⇒ $e^{\alpha_t}>1$, $e^{-\alpha_t}<1$। exponential function কঠোরভাবে বর্ধমান এবং $e^0=1$। তাই $\alpha_t>0\Rightarrow e^{\alpha_t}>e^0=1$ — ভুল-বিন্দুর ওজন $w_i e^{\alpha_t}>w_i$, অর্থাৎ বাড়ে। আর $-\alpha_t<0\Rightarrow e^{-\alpha_t}<e^0=1$ — ঠিক-বিন্দুর ওজন $w_i e^{-\alpha_t}<w_i$, অর্থাৎ কমে। (যেহেতু weak learner-এর $\varepsilon_t<0.5\Rightarrow\alpha_t>0$, প্রতিটি বৈধ round-এ update সত্যিই ভুলের ওজন বাড়ায়, ঠিকের কমায়।)

(গ) "adaptive" ও noise-sensitivity। প্রতিটি round আগের ভুলের দিকে নমুনা-বণ্টন মানিয়ে নেয় (adapts) বলেই এর নাম "adaptive boosting" (AdaBoost) — algorithm নিজে থেকে কঠিন বিন্দুর দিকে ফোকাস সরায়। কিন্তু একই কারণে এটা label-noise/outlier-সংবেদনশীল: একটা mislabeled বিন্দু বা প্রকৃত outlier কোনো weak learner-ই ঠিক করতে পারে না, তাই round-এর পর round সেটা "ভুল" থেকে যায় ও তার ওজন ক্রমাগত বাড়তে থাকে; ensemble শেষে সেই কয়েকটা অসংশোধনযোগ্য বিন্দুর পেছনে অসামঞ্জস্যপূর্ণ ক্ষমতা ঢেলে দেয়, ফলে test-performance পড়ে (canonical চূড়ার-পর-পতন)।

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

(ক) squared loss-এ pseudo-residual = সাধারণ residual। $L(y,F)=\tfrac12(y-F)^2$। $F$-সাপেক্ষে derivative: $$ \frac{\partial L}{\partial F}=\frac{\partial}{\partial F}\Big[\tfrac12(y-F)^2\Big]=\tfrac12\cdot2(y-F)\cdot(-1)=-(y-F). $$ তাই pseudo-residual $$ r_i=-\Big[\frac{\partial L}{\partial F(x_i)}\Big]{F=F(x_i), $$ যা হুবহু সাধারণ }}=-\big[-(y_i-F_{t-1}(x_i))\big]=y_i-F_{t-1residual। তাই squared loss-এর ক্ষেত্রে "fit the residual" আর "fit the negative gradient" সম্পূর্ণ অভিন্ন — এই বিশেষ ক্ষেত্রেই gradient boosting-এর সরলতম ব্যাখ্যা (প্রতিটি গাছ আগের অবশিষ্ট ভুল = residual fit করে)।

(খ) কেন functional gradient descent। সাধারণ gradient descent parameter-space-এ পা ফেলে: $\theta\leftarrow\theta-\nu\nabla_\theta L$ (একটা সসীম-মাত্রিক vector $\theta$ আপডেট হয়)। gradient boosting-এ যে জিনিসটা optimize হচ্ছে সেটা parameter নয়, পুরো function $F$ নিজেই — তাই পা ফেলা হয় function-space-এ: প্রতিটি step একটা নতুন function $h_t$ যোগ করে $F_t=F_{t-1}+\nu h_t$, যেখানে $h_t$ আনুমানিকভাবে negative-gradient দিক ($-\partial L/\partial F$) ধরে। অর্থাৎ "variable" হলো function $F$, "gradient" হলো function-space-এর negative gradient ($\approx$ pseudo-residual) — তাই নাম functional gradient descent (০.৩-এর gradient descent-এর function-space সংস্করণ)।

(গ) AdaBoost = exponential loss-এর gradient boosting। এক শব্দে: exponential loss। AdaBoost হলো exponential loss $L(y,F)=\exp(-yF)$-এর উপর forward stagewise additive modeling, তাই এটাকে gradient boosting-এর একটা বিশেষ ক্ষেত্র (নির্দিষ্ট loss-এর জন্য) হিসেবে দেখা যায় (প্রমাণ — সমাধান ১২)।

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

আপডেট $F_t=F_{t-1}+\nu h_t$, $\nu\in(0,1]$ = learning rate/shrinkage। canonical sweep ($n{=}200$, depth $3$): lr $0.01\to0.794$, $0.05\to0.833$, $0.1\to0.850$, $0.5\to0.844$, $1.0\to0.878$।

(ক) ছোট $\nu$ ⇒ বেশি গাছ লাগে; তাই $0.01\to0.794$। ছোট $\nu$ মানে প্রতিটি গাছের অবদান সংকুচিত — প্রতি step ছোট, তাই loss-floor-এ পৌঁছাতে গাছের সংখ্যা $T$ বেশি লাগে। $\nu=0.01$-এ মাত্র $200$ গাছ floor-এ পৌঁছানোর জন্য যথেষ্ট নয় — ensemble তখনো under-fit (এখনো বাড়ছিল), তাই accuracy মাত্র $0.794$। আরও গাছ ($T$ বড়) দিলে এই lr-এও accuracy উঠত; অর্থাৎ $0.794$ ছোট $\nu$-র সীমাবদ্ধতা নয়, $\nu$-$T$ অমিলের ফল (ছোট $\nu$-র সাথে $T$ বাড়াতে হয়)।

(খ) "$\nu$ ছোট, $T$ বড়" কেন ভালো generalize — shrinkage = regularizer। ছোট $\nu$ + বড় $T$ হলে প্রতিটি গাছ কেবল সামান্য সংশোধন করে, তাই ensemble ধীরে-সাবধানে fit হয় এবং কোনো একক গাছ data-noise-এ overreact করতে পারে না। এটা ঠিক ridge-এর মতো regularizer-আচরণ — প্রতিটি update ছোট রেখে effective complexity নিয়ন্ত্রণে রাখে, ফলে variance কমে ও generalization ভালো হয়। বড় $\nu$ (যেমন $1.0$) উল্টো — প্রতিটি গাছ বড় লাফ দেয়, training-এ দ্রুত fit হয় কিন্তু noise-ও দ্রুত ধরে, তাই overfit-ঝুঁকি বেশি (যদিও এই বিশেষ data-তে $1.0$ ভালো করেছে — পরের অংশ)।

(গ) accuracy একঘেয়ে নয় ⇒ $\nu$ tune করতে হয়। sweep-এ accuracy $\nu$-তে monotone নয় — $0.1\to0.850$ থেকে $0.5\to0.844$-এ সামান্য নেমে আবার $1.0\to0.878$-এ উঠেছে (এই বিশেষ noisy data-তে বড় $\nu$ আকস্মিকভাবে ভালো করেছে)। এটাই মনে করিয়ে দেয় $\nu$ একটা hyperparameter যার কোনো সর্বজনীন "সবসময়-সেরা" মান নেই, এবং এটা $T$-এর সাথে যৌথভাবে (cross-validation দিয়ে) tune করতে হয় — একা $\nu$ বাড়িয়ে বা কমিয়ে নয়। ব্যবহারিক নীতি: ছোট $\nu$ (যেমন $0.05$–$0.1$) নিরাপদ default, কিন্তু তখন $T$ যথেষ্ট বড় রাখতে হবে, আর সেরা ($\nu,T$)-জোড়া CV দিয়ে বেছে নিতে হবে।

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

সমাধান ৭ (★)¶

$\alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}$ (natural log)।

(ক) $\varepsilon_t=0.3$। $$ \frac{1-0.3}{0.3}=\frac{0.7}{0.3}=2.333,\quad \ln 2.333=0.8473,\quad \alpha_t=\tfrac12(0.8473)=\mathbf{0.4236}. $$ ধনাত্মক, মাঝারি — error $<0.5$ বলে $\alpha>0$ (final vote-এ অবদান রাখে); চমৎকার-নয় কিন্তু ভালো learner, তাই মাঝারি ওজন।

(খ) $\varepsilon_t=0.1$। $$ \frac{0.9}{0.1}=9,\quad \ln 9=2.1972,\quad \alpha_t=\tfrac12(2.1972)=\mathbf{1.0986}. $$ অনেক বড় — খুব কম-error (ভালো) learner, তাই final vote-এ বিপুল ওজন। (ক)-এর তুলনায় ($0.4236\to1.0986$) দেখায় error কমলে $\alpha$ দ্রুত বাড়ে।

(গ) $\varepsilon_t=0.5$ ও $\varepsilon_t=0.6$। $$ \varepsilon=0.5:\ \frac{0.5}{0.5}=1,\ \ln 1=0,\ \alpha_t=\mathbf{0}\quad(\text{তথ্যহীন, কোনো অবদান নয়}); $$ $$ \varepsilon=0.6:\ \frac{0.4}{0.6}=0.667,\ \ln 0.667=-0.4055,\ \alpha_t=\tfrac12(-0.4055)=\mathbf{-0.2027}\quad(\text{ঋণাত্মক}). $$ চিহ্ন-তুলনা: $\varepsilon=0.5$-এ $\alpha=0$ হলো সীমারেখা — এর নিচে ($\varepsilon<0.5$) $\alpha>0$ (learner-কে যেমন আছে তেমন ভোট দেওয়া হয়), এর উপরে ($\varepsilon>0.5$) $\alpha<0$ (learner chance-এর চেয়ে খারাপ, তাই ensemble তার সিদ্ধান্ত উল্টে নেয়)। অর্থাৎ $\alpha$-এর চিহ্নই বলে দেয় learner-টা chance-এর কোন পাশে।

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

$5$ বিন্দু, প্রাথমিক ওজন $w_i=1/5=0.2$ প্রতিটি; $h_1$ বিন্দু $\#2,\#4$ ভুল করে, $\#1,\#3,\#5$ ঠিক।

(ক) weighted error ও $\alpha_1$। $$ \varepsilon_1=\sum_i w_i\mathbf 1[h_1(x_i)\ne y_i]=w_2+w_4=0.2+0.2=\mathbf{0.4}. $$ $$ \frac{1-0.4}{0.4}=\frac{0.6}{0.4}=1.5,\quad \ln 1.5=0.4055,\quad \alpha_1=\tfrac12(0.4055)=\mathbf{0.2027}. $$

(খ) unnormalized নতুন ওজন। $e^{\alpha_1}=e^{0.2027}=1.2247$, $e^{-\alpha_1}=0.8165$। - ভুল ($\#2,\#4$): $w_i e^{\alpha_1}=0.2(1.2247)=\mathbf{0.2449}$ প্রতিটি। - ঠিক ($\#1,\#3,\#5$): $w_i e^{-\alpha_1}=0.2(0.8165)=\mathbf{0.1633}$ প্রতিটি।

(গ) normalize ও $0.5$-যাচাই। $$ Z=2(0.2449)+3(0.1633)=0.4898+0.4899\approx\mathbf{0.9798}. $$ normalized ওজন: $$ \text{ভুল প্রতিটি}=\frac{0.2449}{0.9798}=\mathbf{0.2500},\qquad \text{ঠিক প্রতিটি}=\frac{0.1633}{0.9798}=\mathbf{0.1667}. $$ ভুল-বিন্দুর মোট normalized ওজন $=2(0.2500)=\mathbf{0.5}$ ✓ (ঠিক-মোট-ও $3(0.1667)=0.5$)। অর্থাৎ reweight করার পর $h_1$ নতুন বণ্টনে ঠিক $50\%$ weighted error-এ নেমে আসে — AdaBoost-এর একটা পরিচিত ধর্ম: পরের round-এ আগের learner ঠিক chance-সমান, তাই $h_2$-কে $h_1$-এর সাথে স্বতন্ত্র কিছু শিখতেই হয় (নতুন তথ্য যোগ করে)। [এটা সাধারণ ফল — $\sum_{\text{ভুল}}w_ie^{\alpha}=\varepsilon e^{\alpha}=\varepsilon\sqrt{\tfrac{1-\varepsilon}{\varepsilon}}=\sqrt{\varepsilon(1-\varepsilon)}$ এবং $\sum_{\text{ঠিক}}w_ie^{-\alpha}=(1-\varepsilon)\sqrt{\tfrac{\varepsilon}{1-\varepsilon}}=\sqrt{\varepsilon(1-\varepsilon)}$ — দুই দল সমান, তাই normalize করলে প্রতিটি $0.5$।]

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

squared loss $L=\tfrac12(y-F)^2\Rightarrow r_i=y_i-F_{t-1}(x_i)$; target $y=(10,12,20)$, $F_0(x)=\bar y$।

(ক) $F_0$ ও প্রথম-round residual। $$ F_0=\bar y=\frac{10+12+20}{3}=\frac{42}{3}=\mathbf{14}. $$ $$ r^{(1)}=y-F_0=(10-14,\ 12-14,\ 20-14)=\mathbf{(-4,\,-2,\,6)}. $$

(খ) $F_1$ ও দ্বিতীয়-round residual। $h_1=(-4,-4,8)$, $\nu=0.5$: $$ \nu h_1=0.5(-4,-4,8)=(-2,-2,4);\qquad F_1=F_0+\nu h_1=(14-2,\ 14-2,\ 14+4)=\mathbf{(12,\,12,\,18)}. $$ $$ r^{(2)}=y-F_1=(10-12,\ 12-12,\ 20-18)=\mathbf{(-2,\,0,\,2)}. $$

(গ) residual ছোট হয়ে আসছে কেন। $\max\lvert r\rvert$ এক round-এ $6\to2$-এ নামল — প্রতিটি গাছ আগের residual-এর একটা অংশ ($\nu$ দিয়ে সংকুচিত) মুছে দিচ্ছে, তাই যোগফল $F_t$ ক্রমাগত $y$-এর কাছে যাচ্ছে; এটাই boosting-এর "ভুল ধীরে-ধীরে সংশোধন" — functional gradient descent-এর এক-একটা পা, যেখানে প্রতিটি পা loss (অবশিষ্ট residual) আরও কমায়।

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

n_estimators	test accuracy
1	0.739
10	0.789
50	0.850 (চূড়া)
100	0.794
200	0.783
500	0.778

(ক) $1\to50$ বাড়ে — bias↓। শুরুতে boosting ক্রমিকভাবে bias কমায়: একটা stump (depth-$1$) প্রায় কিছুই ধরতে পারে না ($0.739$), কিন্তু এমন অনেক stump-এর ওজনিত যোগফল ধীরে-ধীরে আসল (জটিল) decision boundary ধরে। তাই প্রথম $\sim50$ round-এ ensemble-এর capacity বেড়ে underfit কমে — accuracy $0.739\to0.850$ ওঠে।

(খ) $50$-এর পর পড়ে — overfit, RF-এর বিপরীত। চূড়ার পর bias প্রায় শূন্যে নেমে গেছে, তাই অতিরিক্ত round আর কাজের কিছু শেখে না — বরং ensemble training-data (noise/outlier সমেত) fit করতে থাকে। reweighting-এর কারণে অসংশোধনযোগ্য (mislabeled/outlier) বিন্দুর ওজন round-এর পর round বাড়ে, ensemble তাদের পেছনে অতিরিক্ত ক্ষমতা ঢালে ⇒ overfit, test accuracy পড়ে ($0.850\to0.778$) — এটাই AdaBoost-এর noise-sensitivity। RF-এ গাছগুলো স্বাধীন, গড় করা কেবল variance কমায় (bias বাড়ায় না), তাই আরও গাছ কখনো ক্ষতি করে না — এখানে ক্রমিক-নির্ভরতার কারণেই ক্ষতি হয়।

(গ) n_estimators একটা tune-যোগ্য knob (early stopping দরকার)। যেহেতু accuracy n_estimators-এ একঘেয়ে নয় (স্পষ্ট চূড়া $\approx50$, তারপর পতন), সেরা round একা বাড়িয়ে পাওয়া যায় না — validation/CV দিয়ে চূড়া খুঁজে সেখানে early stopping করতে হয়। এটা RF-এর "যত-বেশি-তত-ভালো (বা সমান)" monotone-নিরাপদ knob-এর সরাসরি বিপরীত: RF-এ গাছ বাড়ানো নিরাপদ, boosting-এ গাছ বাড়ানো নিয়ন্ত্রণ-প্রয়োজনীয়।

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

GradientBoosting ($n{=}200$, lr $0.1$, depth $3$): train $1.000$, test $0.850$; RF($300$) test $0.839$।

(ক) $0.150$ ব্যবধান = overfitting; কেন train $\to0$ error। train $1.000$ বনাম test $0.850$ — এই $0.150$ ব্যবধান overfitting-এর ক্লাসিক চিহ্ন (model training-data-কে যতটা ভালো জানে, অদেখা data-কে ততটা নয়)। যথেষ্ট round ($200$ গাছ) ও যথেষ্ট গভীরতা (depth $3$) থাকলে additive model $F_T=\sum_t\nu h_t$ ক্রমিকভাবে residual মুছতে-মুছতে প্রতিটি training-বিন্দুকে আলাদা করে fit করতে পারে — তাই training-error $\to0$ (এখানে accuracy $1.000$)। boosting-এর এই "যথেষ্ট মন দিলে training হুবহু fit" ক্ষমতাই একই সাথে তার শক্তি ও overfit-ঝুঁকি।

(খ) train $0$ মানেই খারাপ নয় — test দিয়ে বিচার। না, train-error $0$ একা নিন্দনীয় নয়। boosting প্রায়ই train $1.0$-তেও ভালো test দেয় (এটা margin বাড়ায় — সঠিক বিন্দুদের আস্থা বাড়ায়, কেবল মুখস্থ করে না)। আসল বিচার সবসময় test/CV accuracy — আর এখানে GB ($0.850$) RF ($0.839$)-কে সামান্য ($+0.011$) হারায়। অর্থাৎ train $1.000$ দেখে আতঙ্কিত হওয়ার দরকার নেই যদি generalization (test) ভালো থাকে; train-test ব্যবধান কেবল সতর্ক-সংকেত, একক রায় নয়।

(গ) তিনটি regularizer। gradient boosting-এ overfitting ঠেকাতে: (i) learning-rate shrinkage — ছোট $\nu$ (সমাধান ৬); (ii) গাছের গভীরতা/সংখ্যা সীমিত করা + validation-ভিত্তিক early stopping (সেরা round-এ থামা); (iii) subsampling / stochastic gradient boosting — প্রতি round-এ training-row ও/বা feature-এর একটা এলোমেলো উপসেট ব্যবহার (variance↓, গাছ decorrelate)। XGBoost-এ এর সাথে অতিরিক্ত L1/L2 (leaf-weight) penalty-ও যোগ হয়।

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

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

exponential loss $L(y,F)=\exp(-yF(x))$, $y\in\{-1,+1\}$; round $t$-এ স্থির $F_{t-1}$ ধরে $$ (\alpha_t,h_t)=\arg\min_{\alpha,h}\sum_{i=1}^n \exp!\big(-y_i[F_{t-1}(x_i)+\alpha h(x_i)]\big),\qquad w_i^{(t)}=\exp(-y_iF_{t-1}(x_i)),\ h(x_i)\in{-1,+1}. $$

(ক) objective-কে দুই দলে ভাঙা। exponent ভেঙে: $$ \exp!\big(-y_i[F_{t-1}(x_i)+\alpha h(x_i)]\big)=\underbrace{\exp(-y_iF_{t-1}(x_i))}{=\,w_i^{(t)}}\cdot\exp(-\alpha y_i h(x_i)), $$ তাই objective $=\sum_i w_i^{(t)}\exp(-\alpha y_i h(x_i))$। এখন $h(x_i),y_i\in\{-1,+1\}$ বলে $y_ih(x_i)=+1$ (ঠিক-শ্রেণিবদ্ধ) অথবা $-1$ (ভুল)। তাই exponent $-\alpha y_ih(x_i)=-\alpha$ (ঠিক) বা $+\alpha$ (ভুল), এবং $$ \sum_i w_i^{(t)}\exp(-\alpha y_i h(x_i))=e^{-\alpha}!!\sum.\qquad\checkmark $$}}!w_i^{(t)}+e^{\alpha}!!\sum_{\text{ভুল}}!w_i^{(t)

(খ) $\alpha$-সাপেক্ষে minimize ⇒ $\alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}$। $W=\sum_i w_i^{(t)}$ ও weighted error $\varepsilon_t=\frac{\sum_{\text{ভুল}}w_i^{(t)}}{W}$ ধরি, তাই $\sum_{\text{ভুল}}w_i^{(t)}=\varepsilon_t W$ ও $\sum_{\text{ঠিক}}w_i^{(t)}=(1-\varepsilon_t)W$। objective: $$ J(\alpha)=W\big[(1-\varepsilon_t)e^{-\alpha}+\varepsilon_t e^{\alpha}\big]. $$ $\alpha$-সাপেক্ষে derivative শূন্য করি: $$ \frac{dJ}{d\alpha}=W\big[-(1-\varepsilon_t)e^{-\alpha}+\varepsilon_t e^{\alpha}\big]=0\ \Rightarrow\ \varepsilon_t e^{\alpha}=(1-\varepsilon_t)e^{-\alpha}\ \Rightarrow\ e^{2\alpha}=\frac{1-\varepsilon_t}{\varepsilon_t}, $$ তাই $$ \boxed{\ \alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}\ }. $$ (এটা minimum: $\frac{d^2J}{d\alpha^2}=W[(1-\varepsilon_t)e^{-\alpha}+\varepsilon_t e^{\alpha}]>0$, convex।) ∎

(গ) reweighting নিয়ম। আপডেট $F_t=F_{t-1}+\alpha_t h_t$ থেকে পরের round-এর ওজন: $$ w_i^{(t+1)}=\exp(-y_iF_t(x_i))=\exp!\big(-y_i[F_{t-1}(x_i)+\alpha_t h_t(x_i)]\big)=\underbrace{\exp(-y_iF_{t-1}(x_i))}_{w_i^{(t)}}\exp(-\alpha_t y_i h_t(x_i)), $$ অর্থাৎ $w_i^{(t+1)}=w_i^{(t)}\exp(-\alpha_t y_i h_t(x_i))$। এখানে exponent $-\alpha_t y_ih_t(x_i)=-\alpha_t$ যখন ঠিক ($y_ih_t=+1$), $=+\alpha_t$ যখন ভুল ($y_ih_t=-1$)। তাই ভুল-বিন্দু $e^{\alpha_t}$-গুণ ওজন পায় (বাড়ে), ঠিক-বিন্দু $e^{-\alpha_t}$-গুণ (কমে) — normalize করার পর এটাই ঠিক AdaBoost-এর reweighting নিয়ম। অর্থাৎ $\alpha_t$-সূত্র (খ) ও reweighting (গ) দুটোই exponential-loss minimization থেকে স্বাভাবিকভাবে বেরোয় — AdaBoost আলাদা কোনো heuristic নয়, এটা forward stagewise additive modeling-এরই বিশেষ রূপ। $\blacksquare$

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

লক্ষ্য: $\sum_i L(y_i,F(x_i))$-কে প্রতিটি বিন্দুর prediction $F(x_i)$-এর সাপেক্ষে minimize।

(ক) negative gradient = residual (squared loss)। $L=\tfrac12(y-F)^2$: $$ g_i=\frac{\partial L}{\partial F(x_i)}=\frac{\partial}{\partial F}\Big[\tfrac12(y_i-F(x_i))^2\Big]=-(y_i-F(x_i)), $$ তাই $$ -g_i=y_i-F(x_i)=\textbf{residual}. $$ অর্থাৎ যে দিকে গেলে squared loss দ্রুততম কমে (negative gradient), সেটা ঠিক residual-এর দিক। সাধারণ gradient descent এই বিন্দু-গুলোতে করত $F(x_i)\leftarrow F(x_i)-\nu g_i=F(x_i)+\nu(y_i-F(x_i))$।

(খ) point-wise gradient generalize করে না; tree তা সমাধান করে। সমস্যা: $-g_i$ কেবল $n$টি training-বিন্দুতে সংজ্ঞায়িত — এটা $\{(x_1,-g_1),\dots,(x_n,-g_n)\}$, একটা নতুন $x$-এ এর কোনো মান নেই। তাই point-wise update দিয়ে নতুন data-তে predict করা যায় না (model generalize করে না)। gradient boosting এই pseudo-residual-জোড়াগুলোতে একটা regression tree $h_t$ fit করে: গাছটা $-g_i$-এর একটা smooth, পুরো input-space-এ সর্বত্র-সংজ্ঞায়িত আনুমানিকতা $h_t(x)\approx-g(x)$ দেয়। এতে point-wise negative-gradient একটা function-এ রূপান্তরিত হয়, তাই negative-gradient দিকে পা ফেলা যায় শুধু training-বিন্দুতে নয়, সমগ্র input-space-এ — এটাই "function-space-এ পা ফেলা" বনাম "point-wise update"-এর পার্থক্য।

(গ) $F_t=F_{t-1}+\nu h_t$ = functional gradient descent-এর এক step; $\nu$ = step size। যেহেতু $h_t\approx-g$ (negative-gradient-এর tree-আনুমানিকতা), আপডেট $$ F_t=F_{t-1}+\nu h_t\approx F_{t-1}-\nu g $$ হলো function $F$-কে (আনুমানিক) negative-gradient দিকে $\nu$-আকারের একটা পা ফেলা — অর্থাৎ function-space-এ steepest descent, তাই functional gradient descent। এখানে learning rate $\nu$ ঠিক সাধারণ gradient descent-এর (০.৩-এর) step size / learning rate parameter-এর ভূমিকা পালন করে: ছোট $\nu$ ⇒ ছোট সতর্ক পা (বেশি step/গাছ লাগে কিন্তু বেশি স্থিতিশীল ও ভালো generalize করে), বড় $\nu$ ⇒ বড় লাফ (কম গাছ লাগে কিন্তু overshoot/overfit-ঝুঁকি)। $\blacksquare$

ঘ · কোডিং (Python)¶

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

নিচের script seed-সূচক 20260619 দিয়ে §৭-এর সব canonical সংখ্যা পুনরুৎপাদন করে। সব estimator-এ একই random_state=20260619। (সংখ্যাগুলো একটা নির্দিষ্ট scikit-learn সংস্করণে স্থিতিশীল; ক্ষুদ্র সংস্করণ-ভেদে — বিশেষত AdaBoost-এর default base-estimator/algorithm পরিবর্তনের কারণে — শেষ অঙ্কে হেরফের সম্ভব, কিন্তু গল্প — stump দুর্বল → AdaBoost ক্রমে bias কমিয়ে $\approx50$ round-এ চূড়া তারপর overfit → GB train $1.0$/test $0.85$ → lr–$T$ tradeoff → RF তুলনীয় — অপরিবর্তিত।)

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 (
    AdaBoostClassifier, GradientBoostingClassifier, 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,
    class_sep=0.8, flip_y=0.05, 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. baseline decision stump (weak learner) ---
stump = DecisionTreeClassifier(max_depth=1, random_state=SEED).fit(Xtr, ytr)
acc_stump = accuracy_score(yte, stump.predict(Xte))
print(f"stump (depth-1) : acc={acc_stump:.3f}")              # ~0.739  (weak: err 0.261 < 0.5)

# --- 2. AdaBoost n_estimators sweep (peak then decline) ---
print("AdaBoost n_estimators sweep:")
for B in [1, 10, 50, 100, 200, 500]:
    ab = AdaBoostClassifier(n_estimators=B, random_state=SEED).fit(Xtr, ytr)
    print(f"  B={B:>3}: acc={accuracy_score(yte, ab.predict(Xte)):.3f}")
# 1->0.739, 10->0.789, 50->0.850 (peak), 100->0.794, 200->0.783, 500->0.778

# --- 3. GradientBoosting (default) : train >> test = overfit ---
gb = GradientBoostingClassifier(
    n_estimators=200, learning_rate=0.1, max_depth=3, random_state=SEED,
).fit(Xtr, ytr)
print(f"GB(200,lr0.1,d3) : train={accuracy_score(ytr, gb.predict(Xtr)):.3f}, "
      f"test={accuracy_score(yte, gb.predict(Xte)):.3f}")    # train 1.000, test 0.850

# --- 4. GB learning-rate sweep (nu–T tradeoff) ---
print("GB learning-rate sweep (n=200, depth 3):")
for lr in [0.01, 0.05, 0.1, 0.5, 1.0]:
    g = GradientBoostingClassifier(
        n_estimators=200, learning_rate=lr, max_depth=3, random_state=SEED,
    ).fit(Xtr, ytr)
    print(f"  lr={lr:<4}: acc={accuracy_score(yte, g.predict(Xte)):.3f}")
# 0.01->0.794, 0.05->0.833, 0.1->0.850, 0.5->0.844, 1.0->0.878

# --- 5. RandomForest comparison (bagging: variance↓) ---
rf = RandomForestClassifier(n_estimators=300, random_state=SEED).fit(Xtr, ytr)
print(f"RF(300)          : test={accuracy_score(yte, rf.predict(Xte)):.3f}")  # ~0.839

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

train=420, test=180
stump (depth-1) : acc=0.739
AdaBoost n_estimators sweep:
  B=  1: acc=0.739
  B= 10: acc=0.789
  B= 50: acc=0.850
  B=100: acc=0.794
  B=200: acc=0.783
  B=500: acc=0.778
GB(200,lr0.1,d3) : train=1.000, test=0.850
GB learning-rate sweep (n=200, depth 3):
  lr=0.01: acc=0.794
  lr=0.05: acc=0.833
  lr=0.1 : acc=0.850
  lr=0.5 : acc=0.844
  lr=1.0 : acc=0.878
RF(300)          : test=0.839

পাঠ-সারাংশ। (i) decision stump একটা মাত্র split-এ মাত্র $0.739$ (error $0.261<0.5$) — বৈধ কিন্তু দুর্বল weak learner। (ii) AdaBoost ক্রমিকভাবে bias কমায়: $1\to0.739$ থেকে $50\to\mathbf{0.850}$ (চূড়া), কিন্তু এর পর training-noise fit করতে গিয়ে overfit করে, accuracy পড়ে ($500\to0.778$) — RF-এর monotone-নিরাপদ curve-এর বিপরীতে এখানে early stopping দরকার। (iii) GradientBoosting train $1.000$ কিন্তু test $0.850$ — $0.150$ ব্যবধান overfit-চিহ্ন, তবু test-এ RF ($0.839$)-কে সামান্য হারায় (generalization-ই আসল বিচার)। (iv) lr sweep $\nu$–$T$ tradeoff দেখায় — ছোট $\nu=0.01$-এ $200$ গাছ যথেষ্ট নয় ($0.794$, underfit), $\nu$ বাড়লে accuracy ওঠে কিন্তু monotone নয় ($1.0\to0.878$), তাই $\nu$ ও $T$ যৌথভাবে tune করতে হয়। (v) RF ($0.839$) boosting-এর পাশে দাঁড়ায় — দুই বিপরীত পথ (bagging variance↓ বনাম boosting bias↓) একই dataset-এ তুলনীয় accuracy দেয়, কিন্তু RF গাছ-বাড়ানোয় নিরাপদ, boosting নিয়ন্ত্রণ-প্রয়োজনীয়।