সমাধান — অধ্যায় ৬.৩ · Classification I: LDA, QDA, Naive Bayes & k-NN¶

অধ্যায় ফাইল: part-6-statistical-ml/06-03-classification-lda-qda-nb-knn.md (§৭ অনুশীলনী)। চলমান simulation — seed np.random.default_rng(20260619): $3$টি শ্রেণি, 2D feature, প্রতি শ্রেণিতে $150$টি বিন্দু ($n=450$), শ্রেণিগুলোর covariance অসমান, $70/30$ stratified train–test split। মূল notation: posterior $P(y=c\mid x)=\dfrac{\pi_c f_c(x)}{\sum_l\pi_l f_l(x)}$; LDA শেয়ার-$\Sigma$ (linear boundary), QDA per-class $\Sigma_c$ (quadratic boundary); Naive Bayes $P(x\mid y)=\prod_j P(x_j\mid y)$; k-NN নিকটতম $k$ প্রতিবেশীর ভোট; Bayes error $=\mathbb E_X[1-\max_c P(c\mid X)]$। canonical সংখ্যা (test accuracy): LDA $0.881$; QDA $0.919$ (best); GaussianNB $0.904$; k-NN($5$) $0.896$; k-NN($15$) $0.911$। k-NN বনাম $k$: $1\to0.859$, $3\to0.889$, $5\to0.896$, $15\to0.911$, $25\to0.911$। §ঘ-এর runnable script (seed 20260619) উপরের accuracy পুনরুৎপাদন করে। গাণিতিক প্রশ্নের (৬, ৭, ৯) সংখ্যাগুলো স্বয়ংসম্পূর্ণ — অধ্যায়-dataset থেকে স্বাধীন।

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

সমাধান ১ (★)¶

প্রদত্ত একটি নির্দিষ্ট $x$-এ, একটি নিয়ম $\hat y(x)$ সঠিক হওয়ার সম্ভাবনা ঠিক $P(y=\hat y(x)\mid x)$। এই সম্ভাবনাকে সর্বোচ্চ করতে চাইলে স্পষ্টতই সেই শ্রেণি বাছতে হবে যার posterior সবচেয়ে বড় — অর্থাৎ $$ \hat y(x)=\arg\max_c P(y=c\mid x). $$ এটাই Bayes classifier। যেহেতু প্রতিটি $x$-এ এটি সঠিক-সম্ভাবনা সর্বোচ্চ (তাই ভুল-সম্ভাবনা সর্বনিম্ন) করে, এবং সামগ্রিক ভুল হলো $x$-জুড়ে এই point-wise ভুলের প্রত্যাশা, তাই Bayes classifier সামগ্রিকভাবেও সর্বনিম্ন-ভুল ⇒ 0–1 loss-এ optimal। নির্দিষ্ট $x$-এ এর ভুলের সম্ভাবনা (point-wise Bayes error): $$ P(\hat y(x)\ne y\mid x)=1-\max_c P(y=c\mid x). $$ এর প্রত্যাশা $\mathbb E_X[1-\max_c P(c\mid X)]$ হলো সামগ্রিক Bayes error — অনিবার্য, কারণ এমনকি সত্য posterior জানলেও শ্রেণিগুলোর overlap-জনিত এই ভুল থেকে যায়। (পূর্ণ প্রমাণ → সমাধান ১২।)

সমাধান ২ (★)¶

তিন দৃষ্টান্ত আলাদা হয় কী জিনিস estimate করে তার ভিত্তিতে:

generative — শ্রেণি-শর্তাধীন density $f_c(x)=P(x\mid y=c)$ ও prior $\pi_c$ model করে, তারপর Bayes-নিয়মে posterior $\propto\pi_c f_c(x)$ বের করে। কার্যত $P(x,y)$-র পুরো যৌথ গঠন শেখে — তাই "generative" (চাইলে নতুন data জন্মাতেও পারে)। এই অধ্যায়ে: LDA ($0.881$), QDA ($0.919$), GaussianNB ($0.904$)।
discriminative — $P(x)$ নিয়ে মাথা না ঘামিয়ে সরাসরি $P(y\mid x)$ বা decision boundary শেখে। উদাহরণ: logistic regression (৫.৪) — পরের অধ্যায়ের SVM-ও।
instance-based (memory-based) — কোনো global parameter "fit" করে না; training-বিন্দুগুলো মনে রেখে নতুন $x$-এ স্থানীয় প্রতিবেশীদের দিয়ে সিদ্ধান্ত নেয়। এই অধ্যায়ে: k-NN ($0.896$ at $k{=}5$, $0.911$ at $k{=}15$)।

সংক্ষেপে: generative ⇒ "প্রতিটি শ্রেণি দেখতে কেমন তা শিখি"; discriminative ⇒ "শ্রেণিগুলো আলাদা করার রেখা শিখি"; instance-based ⇒ "কিছু শিখি না, প্রতিবেশী দেখে ভোট দিই।"

সমাধান ৩ (★)¶

দুই শ্রেণির log-posterior-ratio: $$ \log\frac{P(y=0\mid x)}{P(y=1\mid x)}=\log\frac{\pi_0}{\pi_1}+\log\frac{f_0(x)}{f_1(x)}. $$ Gaussian density বসালে $\log f_c(x)=-\tfrac12\log\lvert\Sigma_c\rvert-\tfrac12(x-\mu_c)^\top\Sigma_c^{-1}(x-\mu_c)+\text{const}$। সমালোচ্য পদ হলো quadratic অংশ $-\tfrac12 x^\top\Sigma_c^{-1}x$।

LDA (শেয়ার $\Sigma_0=\Sigma_1=\Sigma$): দুই শ্রেণিতে $-\tfrac12 x^\top\Sigma^{-1}x$ পদটি অভিন্ন, log-ratio-তে বিয়োগ হয়ে বাতিল হয়ে যায় — অবশিষ্ট থাকে কেবল $x$-এ linear পদ। তাই boundary $\{$log-ratio$=0\}$ একটি hyperplane (linear)।
QDA (ভিন্ন $\Sigma_0\ne\Sigma_1$): এখন quadratic পদ আর অভিন্ন নয়, log-ratio-তে $x^\top(\Sigma_1^{-1}-\Sigma_0^{-1})x$ টিকে থাকে — তাই boundary $x$-এ quadratic (উপবৃত্ত/অধিবৃত্ত/পরাবৃত্ত)।

এক বাক্যে: শেয়ার-$\Sigma$ quadratic পদ বাতিল করে (⇒ linear, LDA); per-class $\Sigma_c$ তা টিকিয়ে রাখে (⇒ quadratic, QDA)।

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

এই dataset-এ QDA কেন জেতে: simulation-এ শ্রেণিগুলোর covariance ইচ্ছাকৃতভাবে অসমান। LDA সব শ্রেণিতে একই $\Sigma$ ধরে — এটি একটি ভুল ধারণা, যা মডেলে একটি ক্রমাগত bias ঢোকায়: সত্য boundary বাঁকানো হলেও LDA সরলরেখা টানতে বাধ্য, তাই কিছু বিন্দু ভুল পাশে পড়ে (accuracy মাত্র $0.881$)। QDA শ্রেণি-প্রতি আলাদা $\Sigma_c$ estimate করে এই ভুল এড়ায়, quadratic boundary দিয়ে সত্য গঠন ধরে — তাই $0.919$, সেরা।

উল্টোদিকে LDA কখন জেতে (bias–variance): QDA শ্রেণি-প্রতি একটি পূর্ণ $\Sigma_c$ ($d(d+1)/2$ parameter প্রতি শ্রেণি) estimate করে — বেশি parameter ⇒ বেশি variance (ছোট নমুনায় $\Sigma_c$ অস্থির)। LDA মাত্র একটিই (পুল-করা) $\Sigma$ estimate করে — অনেক কম parameter ⇒ কম variance। তাই: - নমুনা ছোট হলে, বা feature-মাত্রা বড় হলে, QDA-র variance তার bias-সুবিধাকে ছাপিয়ে যায় — LDA জেতে। - শ্রেণিগুলোর covariance সত্যিই প্রায়-সমান হলে LDA-র শেয়ার-$\Sigma$ ধারণা প্রায় সঠিক (কম bias) এবং কম variance — LDA জেতে।

মোদ্দা: LDA = কম variance + শেয়ার-$\Sigma$-জনিত bias; QDA = কম bias + বেশি variance। এই dataset-এ (বড় নমুনা, সত্যিই ভিন্ন covariance) নমনীয় QDA-ই জয়ী।

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

(ক) conditional independence দাবি করে: শ্রেণি $y$ জানা থাকলে feature-গুলো পরস্পর-স্বাধীন, তাই যৌথ শ্রেণি-শর্তাধীন density প্রান্তিকগুলোর গুণফল: $$ P(x\mid y)=\prod_{j=1}^{d}P(x_j\mid y). $$ এতে প্রতিটি শ্রেণিতে full covariance-এর বদলে শুধু $d$টি একমাত্রিক বিতরণ লাগে — উচ্চ-মাত্রায় বিপুল parameter-সাশ্রয় (low variance)।

(খ) feature correlated হলে $\prod_j P(x_j\mid y)$ ভুল ⇒ NB-র probability-estimate বিকৃত (প্রায়ই over-confident, $0$/$1$-এর দিকে ঠেলে দেওয়া)। তবু classification-এ শুধু $\arg\max_c$ গুরুত্বপূর্ণ, সঠিক probability নয়। posterior-গুলোর পরম মান ভুল হলেও তাদের ক্রম (ranking) প্রায়ই ঠিক থাকে — তাই সঠিক শ্রেণিই সর্বোচ্চ posterior পায়, সিদ্ধান্ত ঠিক হয়। উপরন্তু NB-র কম parameter মানে কম variance, যা ছোট নমুনায়/উচ্চ-মাত্রায় বড় সুবিধা। এই dataset-এ GaussianNB ($0.904$) এমনকি LDA ($0.881$)-কেও হারায়: NB শ্রেণি-প্রতি আলাদা (axis-aligned, diagonal) covariance ধরে বলে LDA-র শেয়ার-$\Sigma$-র চেয়ে covariance-ভিন্নতা কিছুটা ধরতে পারে, যদিও off-diagonal correlation উপেক্ষা করে। তাই NB biased কিন্তু কার্যকর — classic "ভুল কিন্তু কাজের" মডেল।

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

সমাধান ৬ (★★) [E-qda-post]¶

দেওয়া: $\pi_0=\pi_1=0.5$; $\mu_0=(1,1)$, $\Sigma_0=I$; $\mu_1=(3,3)$, $\Sigma_1=4I$; বিন্দু $x=(2,2)$।

(ক) density। diagonal covariance বলে $\lvert\Sigma_0\rvert=1\cdot1=1$, $\lvert\Sigma_1\rvert=4\cdot4=16$। Mahalanobis দূরত্ব²: $$ (x-\mu_0)^\top\Sigma_0^{-1}(x-\mu_0)=\frac{(2-1)^2}{1}+\frac{(2-1)^2}{1}=1+1=2, $$ $$ (x-\mu_1)^\top\Sigma_1^{-1}(x-\mu_1)=\frac{(2-3)^2}{4}+\frac{(2-3)^2}{4}=0.25+0.25=0.5. $$ 2D Gaussian $f_c(x)=\dfrac{1}{2\pi\sqrt{\lvert\Sigma_c\rvert}}\exp\!\big(-\tfrac12\cdot\text{Mahal}^2\big)$: $$ f_0=\frac{1}{2\pi\cdot 1}\,e^{-1}=0.15915\times0.36788\approx 0.05855, $$ $$ f_1=\frac{1}{2\pi\cdot 4}\,e^{-0.25}=0.03979\times0.77880\approx 0.03099. $$

(খ) posterior। সমান prior, তাই $\pi_c$ বাতিল: $$ P(y=0\mid x)=\frac{f_0}{f_0+f_1}=\frac{0.05855}{0.05855+0.03099}=\frac{0.05855}{0.08954}\approx \mathbf{0.654}, $$ $$ P(y=1\mid x)=1-0.654=\mathbf{0.346}. $$ $P(0\mid x)>P(1\mid x)$ ⇒ QDA $x$-কে শ্রেণি $0$-তে দেয়।

(গ) LDA-র সাথে বৈসাদৃশ্য। Euclidean দূরত্বে $x=(2,2)$ দুই $\mu$ থেকে সমদূরত্বে: $\lVert x-\mu_0\rVert^2=(2-1)^2+(2-1)^2=2$ এবং $\lVert x-\mu_1\rVert^2=(2-3)^2+(2-3)^2=2$। তাই identity-covariance ধরা একটি নিয়ম (যেমন nearest-centroid, বা শেয়ার-$\Sigma=I$-র LDA) এখানে টাই দেখত — বিন্দুটি ঠিক boundary-তে। কিন্তু QDA জানে শ্রেণি $1$-এর spread অনেক বড় ($\Sigma_1=4I$), তাই তার density প্রতি বিন্দুতে $\sqrt{\lvert\Sigma_1\rvert}=4$ গুণ বেশি ছড়িয়ে "পাতলা"; এই বড় $\lvert\Sigma_1\rvert$ density-কে কমিয়ে দেয় ($\frac{1}{2\pi\cdot4}$ বনাম $\frac{1}{2\pi\cdot1}$)। ফলে সমদূরত্ব সত্ত্বেও ঘন (tight) শ্রেণি $0$-ই বেশি সম্ভাব্য — QDA টাই ভেঙে শ্রেণি $0$ দেয়। এটাই QDA-র অতিরিক্ত ক্ষমতা: শুধু কেন্দ্র থেকে দূরত্ব নয়, প্রতিটি শ্রেণির আকার/ছড়ানোও হিসাবে নেয়।

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

দেওয়া: $\pi_{\text{spam}}=0.4,\ \pi_{\text{ham}}=0.6$; $P(x_1{=}1\mid\text{spam})=0.8,\ P(x_1{=}1\mid\text{ham})=0.1$; $P(x_2{=}1\mid\text{spam})=0.2,\ P(x_2{=}1\mid\text{ham})=0.7$। নতুন email: $x_1=1$ ("free" আছে), $x_2=0$ ("meeting" নেই)। তাই $P(x_2{=}0\mid c)=1-P(x_2{=}1\mid c)$।

conditional independence ধরে শ্রেণি-প্রতি unnormalized score $\pi_c\,P(x_1{=}1\mid c)\,P(x_2{=}0\mid c)$: $$ \text{spam: } 0.4\times 0.8\times(1-0.2)=0.4\times0.8\times0.8=\mathbf{0.256}, $$ $$ \text{ham: } 0.6\times 0.1\times(1-0.7)=0.6\times0.1\times0.3=\mathbf{0.018}. $$ normalize: $$ P(\text{spam}\mid x)=\frac{0.256}{0.256+0.018}=\frac{0.256}{0.274}\approx \mathbf{0.934},\qquad P(\text{ham}\mid x)=\frac{0.018}{0.274}\approx 0.066. $$ $P(\text{spam}\mid x)\approx0.93\gg P(\text{ham}\mid x)$ ⇒ email-টি spam শ্রেণিভুক্ত। ("free" শব্দটি ($0.8$ বনাম $0.1$) সিদ্ধান্তে প্রবল ভূমিকা রাখল; "meeting"-এর অনুপস্থিতি spam-এর অনুকূলে গেল কারণ ham-এ "meeting" বেশি থাকে।)

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

$k$	accuracy
1	0.859
3	0.889
5	0.896
15	0.911
25	0.911

(ক) সর্বোচ্চ accuracy $0.911$, পাওয়া যায় $k=15$ (এবং $k=25$)-এ।

(খ) $k=1\to15$ পর্যন্ত accuracy একঘেয়ে বাড়ে ($0.859\to0.889\to0.896\to0.911$)। - ছোট $k$ (যেমন $k=1$): classifier প্রতিটি training-বিন্দুর (এবং তার noise-এর) সাথে boundary-কে মানিয়ে নেয় — অত্যন্ত wiggly, low bias কিন্তু high variance; noise-কে signal ভেবে fit করে বলে test accuracy দুর্বল ($0.859$)। - $k$ বাড়ানো: বেশি প্রতিবেশীর গড়/ভোট নেওয়ায় boundary মসৃণ হয়, একক noisy বিন্দুর প্রভাব কমে — variance↓, accuracy↑।

এটি ৬.১-এর bias–variance tradeoff-এর সরাসরি উদাহরণ, যেখানে $k$ একটি capacity-knob (ছোট $k$ = বেশি capacity/flexibility, বড় $k$ = কম)।

(গ) $k=15$ ও $25$ উভয়েই $0.911$ — উন্নতি থেমে গেছে। খুব বড় $k$-তে নতুন বিন্দুর সিদ্ধান্তে দূরের, অপ্রাসঙ্গিক প্রতিবেশীরাও ভোট দেয়, তাই স্থানীয় গঠন ঝাপসা হয়ে bias বাড়তে থাকে; চূড়ান্তে $k=n$ হলে সব বিন্দুর সিদ্ধান্ত একই (majority class), accuracy পড়ে যায়। তাই accuracy-বনাম-$k$ একটি U-আকার (এখানে চূড়ার সমতল অংশ $k\in[15,25]$) — bias (বড় $k$) ও variance (ছোট $k$)-এর ভারসাম্যের ফল।

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

unit-hypercube $[0,1]^p$, uniform data; মোট আয়তনের ভগ্নাংশ $r$ ধরা একটি ঘনক-প্রতিবেশের বাহু-দৈর্ঘ্য $\ell$ সমীকরণ $\ell^p=r$ থেকে $\ell=r^{1/p}$। $r=0.01$ ($1\%$):

$p$	$\ell=0.01^{1/p}$
1	$0.01$
2	$0.10$
10	$0.63$
100	$0.955$

(ক) উপরের সারণি: $p{=}1\Rightarrow\ell=0.01$; $p{=}2\Rightarrow\ell=0.01^{0.5}=0.1$; $p{=}10\Rightarrow\ell=0.01^{0.1}\approx0.631$; $p{=}100\Rightarrow\ell=0.01^{0.01}\approx0.955$।

(খ) $p=10$-এই কেবল $1\%$ data ঘিরতে প্রতিটি অক্ষে পরিসরের $63\%$ লাগে, $p=100$-এ প্রায় পুরো পরিসর ($95.5\%$) — অর্থাৎ "নিকটতম $1\%$" প্রতিবেশীও আর স্থানীয় থাকে না, প্রায় গোটা space জুড়ে ছড়ানো। উচ্চ-মাত্রায় প্রায় সব বিন্দু-জোড়ার দূরত্ব প্রায় সমান হয়ে পড়ে (distance concentration), তাই "নিকটতম" আর "দূরতম" প্রতিবেশীর পার্থক্য মুছে যায় — k-NN-এর প্রতিবেশী-ভোট অর্থহীন হতে থাকে। এটাই curse of dimensionality: দূরত্ব-নির্ভর পদ্ধতিগুলো মাত্রা বাড়লে দ্রুত ভেঙে পড়ে, এবং ঘনত্ব ভালোভাবে estimate করতে প্রয়োজনীয় নমুনা মাত্রার সাথে ঘাতীয়ভাবে (exponentially) বাড়ে।

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

সমাধান ১০ (★★) [P-lda-disc]¶

শ্রেণি-শর্তাধীন Gaussian, শেয়ার $\Sigma$: $$ f_c(x)=\frac{1}{(2\pi)^{d/2}\lvert\Sigma\rvert^{1/2}}\exp!\Big(-\tfrac12(x-\mu_c)^\top\Sigma^{-1}(x-\mu_c)\Big). $$ Bayes-নিয়মে শ্রেণি বাছা $\arg\max_c \pi_c f_c(x)$, যা $\arg\max_c \log\big(\pi_c f_c(x)\big)$-এর সমতুল্য। তাই সংজ্ঞা $\delta_c(x):=\log\pi_c+\log f_c(x)$: $$ \delta_c(x)=\log\pi_c-\tfrac{d}{2}\log(2\pi)-\tfrac12\log\lvert\Sigma\rvert-\tfrac12(x-\mu_c)^\top\Sigma^{-1}(x-\mu_c). $$ quadratic পদ খুলি: $$ (x-\mu_c)^\top\Sigma^{-1}(x-\mu_c)=\underbrace{x^\top\Sigma^{-1}x}_{\text{সব }c\text{-তে অভিন্ন}}-2x^\top\Sigma^{-1}\mu_c+\mu_c^\top\Sigma^{-1}\mu_c. $$ $-\tfrac{d}{2}\log(2\pi)$, $-\tfrac12\log\lvert\Sigma\rvert$ এবং $-\tfrac12 x^\top\Sigma^{-1}x$ — তিনটিই $c$-নিরপেক্ষ (শেয়ার-$\Sigma$ ও $x$-মাত্র), তাই $\arg\max_c$-এ অপ্রাসঙ্গিক; বাদ দিলে $$ \boxed{\;\delta_c(x)=x^\top\Sigma^{-1}\mu_c-\tfrac12\mu_c^\top\Sigma^{-1}\mu_c+\log\pi_c\;} $$ যা $x$-এ affine/linear ($w_c^\top x+b_c$ আকারে, $w_c=\Sigma^{-1}\mu_c$, $b_c=-\tfrac12\mu_c^\top\Sigma^{-1}\mu_c+\log\pi_c$)। দুই শ্রেণির boundary $\{\delta_0(x)=\delta_1(x)\}$ ⇒ $(w_0-w_1)^\top x+(b_0-b_1)=0$ — একটি hyperplane। অতএব LDA একটি linear classifier। $\blacksquare$

সমাধান ১১ (★★★) [P-qda-disc]¶

এবার শ্রেণি-প্রতি আলাদা $\Sigma_c$। আগের মতোই $\delta_c(x)=\log\pi_c+\log f_c(x)$, কিন্তু এখন normalizing const-ও $c$-নির্ভর ($\lvert\Sigma_c\rvert$): $$ \delta_c(x)=\log\pi_c-\tfrac{d}{2}\log(2\pi)-\tfrac12\log\lvert\Sigma_c\rvert-\tfrac12(x-\mu_c)^\top\Sigma_c^{-1}(x-\mu_c). $$ $-\tfrac{d}{2}\log(2\pi)$ পদটি (একমাত্র সত্যিকার $c$-নিরপেক্ষ পদ) ফেলে দিলে: $$ \boxed{\;\delta_c(x)=-\tfrac12\log\lvert\Sigma_c\rvert-\tfrac12(x-\mu_c)^\top\Sigma_c^{-1}(x-\mu_c)+\log\pi_c\;} $$ quadratic পদ খুললে $-\tfrac12(x-\mu_c)^\top\Sigma_c^{-1}(x-\mu_c)=-\tfrac12 x^\top\Sigma_c^{-1}x+x^\top\Sigma_c^{-1}\mu_c-\tfrac12\mu_c^\top\Sigma_c^{-1}\mu_c$। এখানে $-\tfrac12 x^\top\Sigma_c^{-1}x$ পদটি $\Sigma_c$-এর মাধ্যমে $c$-নির্ভর, তাই আর সব শ্রেণিতে অভিন্ন নয় — বাদ পড়ে না। ফলে $\delta_c(x)$ একটি quadratic ফর্ম $x$-এ।

দুই শ্রেণির boundary $\delta_0(x)=\delta_1(x)$ ⇒ $$ -\tfrac12 x^\top(\Sigma_0^{-1}-\Sigma_1^{-1})x+\big(\Sigma_0^{-1}\mu_0-\Sigma_1^{-1}\mu_1\big)^\top x+\text{const}=0, $$ যেখানে $x^\top(\Sigma_0^{-1}-\Sigma_1^{-1})x$ একটি অশূন্য quadratic পদ — তাই boundary সাধারণভাবে quadratic (matrix $\Sigma_0^{-1}-\Sigma_1^{-1}$-এর eigenvalue-চিহ্ন অনুযায়ী উপবৃত্ত/অধিবৃত্ত/পরাবৃত্ত)।

LDA-তে পতন: যদি $\Sigma_0=\Sigma_1=\Sigma$, তবে $\Sigma_0^{-1}-\Sigma_1^{-1}=0$ — quadratic পদ বিলুপ্ত, $-\tfrac12\log\lvert\Sigma_c\rvert$-ও অভিন্ন; boundary linear হয়ে ঠিক সমাধান ১০-এর LDA-তে ফিরে আসে। অর্থাৎ LDA হলো QDA-র বিশেষ ক্ষেত্র যেখানে সব শ্রেণির covariance সমান। $\blacksquare$

সমাধান ১২ (★★) [P-bayes-opt]¶

binary $y\in\{0,1\}$, 0–1 loss। যেকোনো নিয়ম $g:\mathcal X\to\{0,1\}$-এর জন্য একটি নির্দিষ্ট $x$-এ শর্তাধীন ভুল: $$ P(g(X)\ne Y\mid X=x)=1-P(Y=g(x)\mid X=x). $$ (কারণ ভুল না-হওয়া মানে $Y=g(x)$।) এই ভুল সর্বনিম্ন করতে $P(Y=g(x)\mid x)$ সর্বোচ্চ করা চাই, যা ঘটে যখন $$ g^*(x)=\arg\max_{c\in{0,1}}P(Y=c\mid x)\quad(\text{Bayes rule}). $$ স্পষ্টভাবে, $g^\*(x)=1$ যদি $P(Y=1\mid x)\ge\tfrac12$, নইলে $0$; তখন শর্তাধীন ভুল $=1-\max\{P(0\mid x),P(1\mid x)\}=\min\{P(0\mid x),P(1\mid x)\}$ — অন্য যেকোনো $g$-এর শর্তাধীন ভুলের চেয়ে ছোট-বা-সমান।

সামগ্রিক risk। total error $x$-জুড়ে শর্তাধীন error-এর প্রত্যাশা: $$ P(g(X)\ne Y)=\mathbb E_X\big[P(g(X)\ne Y\mid X)\big]. $$ যেহেতু integrand প্রতিটি $x$-এ $g=g^\*$-এ সর্বনিম্ন, এবং প্রত্যাশা হলো অঋণাত্মক-ওজনের গড় (যা point-wise সর্বনিম্নতা সংরক্ষণ করে), তাই $g^\*$ সামগ্রিক risk-ও সর্বনিম্ন করে। অতএব Bayes classifier optimal, এবং তার অপরিহার্য অবশিষ্ট ভুল $$ R^*=\mathbb E_X\big[1-\max_c P(Y=c\mid X)\big] $$ হলো Bayes error — কোনো classifier (এমনকি সত্য posterior জানা থাকলেও) এর নিচে নামতে পারে না। $\blacksquare$

ঘ · কোডিং (coding)¶

সমাধান ১৩ (★★) [E-fit] — চারটি classifier fit ও তুলনা¶

import numpy as np
from sklearn.discriminant_analysis import (
    LinearDiscriminantAnalysis, QuadraticDiscriminantAnalysis)
from sklearn.naive_bayes import GaussianNB
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split

# ---- চলমান dataset: 3 শ্রেণি, 2D, প্রতি শ্রেণিতে 150, অসমান covariance ----
rng = np.random.default_rng(20260619)
n_per = 150
means = [np.array([0.0, 0.0]),
         np.array([3.0, 1.0]),
         np.array([1.0, 3.5])]
covs = [np.array([[1.0,  0.3], [0.3, 1.0]]),   # শ্রেণি 0
        np.array([[1.5, -0.6], [-0.6, 0.7]]),  # শ্রেণি 1 (ভিন্ন আকার)
        np.array([[0.6,  0.2], [0.2, 1.8]])]   # শ্রেণি 2 (ভিন্ন আকার)

X = np.vstack([rng.multivariate_normal(means[c], covs[c], size=n_per)
               for c in range(3)])
y = np.concatenate([np.full(n_per, c) for c in range(3)])

# 70/30 stratified split
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.30, stratify=y, random_state=20260619)

def test_acc(model):
    model.fit(Xtr, ytr)
    return model.score(Xte, yte)

print(f"LDA         : {test_acc(LinearDiscriminantAnalysis()):.3f}")   # ~0.881
print(f"QDA         : {test_acc(QuadraticDiscriminantAnalysis()):.3f}")# ~0.919 (best)
print(f"GaussianNB  : {test_acc(GaussianNB()):.3f}")                   # ~0.904
print(f"kNN (k=5)   : {test_acc(KNeighborsClassifier(5)):.3f}")        # ~0.896
print(f"kNN (k=15)  : {test_acc(KNeighborsClassifier(15)):.3f}")       # ~0.911

print("\nk-NN accuracy বনাম k:")
for k in [1, 3, 5, 15, 25]:
    print(f"  k={k:2d} : {test_acc(KNeighborsClassifier(k)):.3f}")
# প্রত্যাশিত: 1→0.859, 3→0.889, 5→0.896, 15→0.911, 25→0.911

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

LDA         : 0.881
QDA         : 0.919   <- সেরা
GaussianNB  : 0.904
kNN (k=5)   : 0.896
kNN (k=15)  : 0.911

k-NN accuracy বনাম k:
  k= 1 : 0.859
  k= 3 : 0.889
  k= 5 : 0.896
  k=15 : 0.911
  k=25 : 0.911

ব্যাখ্যা। QDA সেরা ($0.919$) কারণ dataset-এর তিন শ্রেণির covariance অসমান (covs-এ স্পষ্ট ভিন্ন আকার/কাত) — quadratic boundary সেই ভিন্নতা ধরতে পারে। LDA সবচেয়ে দুর্বল ($0.881$) কারণ শেয়ার-$\Sigma$ ধরা এখানে ভুল (bias আরোপ করে, সব শ্রেণিকে একই-আকার ধরে সরলরেখা টানে)। GaussianNB ($0.904$) শ্রেণি-প্রতি diagonal covariance ধরে, তাই covariance-ভিন্নতা কিছুটা ধরে LDA-কে ছাড়িয়ে যায়, যদিও off-diagonal correlation উপেক্ষা করে QDA-কে ধরতে পারে না। k-NN ছোট $k$-তে noisy ($k{=}5\to0.896$), বড় $k$-তে স্থিতিশীল ($k{=}15\to0.911$)। (সুনির্দিষ্ট মান sklearn/NumPy সংস্করণ ও split-বাস্তবায়নে সামান্য বদলাতে পারে; অনুপাত — QDA সর্বোচ্চ, LDA সর্বনিম্ন, NB মাঝে, k-NN $k$-তে উন্নত — অপরিবর্তিত থাকবে।)

সমাধান ১৪ (★★) [E-boundary] — decision boundary ও accuracy-বনাম-$k$ plot¶

import numpy as np
import matplotlib.pyplot as plt
from sklearn.discriminant_analysis import (
    LinearDiscriminantAnalysis, QuadraticDiscriminantAnalysis)
from sklearn.naive_bayes import GaussianNB
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split

# ---- dataset (সমাধান ১৩-এর অনুরূপ) ----
rng = np.random.default_rng(20260619)
n_per = 150
means = [np.array([0.,0.]), np.array([3.,1.]), np.array([1.,3.5])]
covs  = [np.array([[1.,.3],[.3,1.]]),
         np.array([[1.5,-.6],[-.6,.7]]),
         np.array([[.6,.2],[.2,1.8]])]
X = np.vstack([rng.multivariate_normal(means[c], covs[c], n_per) for c in range(3)])
y = np.concatenate([np.full(n_per, c) for c in range(3)])
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=.30,
                                      stratify=y, random_state=20260619)

# ---- grid ----
x_min, x_max = X[:,0].min()-1, X[:,0].max()+1
y_min, y_max = X[:,1].min()-1, X[:,1].max()+1
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 400),
                     np.linspace(y_min, y_max, 400))
grid = np.c_[xx.ravel(), yy.ravel()]

models = [
    ("LDA (linear)",          LinearDiscriminantAnalysis()),
    ("QDA (quadratic)",       QuadraticDiscriminantAnalysis()),
    ("GaussianNB",            GaussianNB()),
    ("kNN (k=5, wiggly)",     KNeighborsClassifier(5)),
    ("kNN (k=15, smooth)",    KNeighborsClassifier(15)),
]

fig, axes = plt.subplots(2, 3, figsize=(15, 9))
axes = axes.ravel()
for ax, (name, clf) in zip(axes, models):
    clf.fit(Xtr, ytr)
    Z = clf.predict(grid).reshape(xx.shape)
    ax.contourf(xx, yy, Z, alpha=0.3, cmap="viridis")
    ax.scatter(Xtr[:,0], Xtr[:,1], c=ytr, s=12, edgecolor="k",
               linewidth=0.3, cmap="viridis")
    ax.set_title(f"{name}  acc={clf.score(Xte,yte):.3f}")
    ax.set_xticks([]); ax.set_yticks([])

# শেষ ঘরে: accuracy বনাম k
ks = [1, 3, 5, 15, 25]
accs = [KNeighborsClassifier(k).fit(Xtr,ytr).score(Xte,yte) for k in ks]
ax = axes[5]
ax.plot(ks, accs, "o-")
for k, a in zip(ks, accs):
    ax.annotate(f"{a:.3f}", (k, a), textcoords="offset points", xytext=(0,6))
ax.set_xlabel("k"); ax.set_ylabel("test accuracy")
ax.set_title("k-NN: accuracy বনাম k")
plt.tight_layout()
plt.savefig("06-03-decision-boundaries.png", dpi=130)
print("accuracy বনাম k:", dict(zip(ks, [round(a,3) for a in accs])))
# প্রত্যাশিত ~ {1:0.859, 3:0.889, 5:0.896, 15:0.911, 25:0.911}

যা দেখা যায়। - LDA: শ্রেণিগুলোর মধ্যে boundary সরলরেখা-খণ্ড (linear) — শেয়ার-$\Sigma$-র সরাসরি ফল; অসমান-আকার শ্রেণিগুলোকে সরলরেখায় আলাদা করতে গিয়ে কিছু ভুল। - QDA: boundary স্পষ্ট বাঁকানো (quadratic) — প্রতিটি শ্রেণির আকার অনুসরণ করে, তাই সর্বোচ্চ accuracy। - GaussianNB: boundary বাঁকানো কিন্তু axis-aligned (diagonal covariance বলে উপবৃত্তগুলো অক্ষ-সমান্তরাল), QDA-র কাত-উপবৃত্তের চেয়ে কম নমনীয়। - k-NN: $k=5$-এ boundary খাঁজকাটা/wiggly (high variance-এর চাক্ষুষ রূপ), $k=15$-এ অনেক মসৃণ। - accuracy-বনাম-$k$ লাইন: $0.859\to0.911$ উঠে $k\ge15$-এ থিতু — bias–variance tradeoff-এর U-আকার (ছোট $k$ = high variance, বড় $k$ = bias বাড়তে শুরু)।

canonical সংখ্যার সারণি (দ্রুত-রেফারেন্স)¶

classifier	test accuracy
LDA (shared $\Sigma$)	0.881
QDA (per-class $\Sigma_c$)	0.919
GaussianNB	0.904
k-NN ($k=5$)	0.896
k-NN ($k=15$)	0.911

$k$	1	3	5	15	25
accuracy	0.859	0.889	0.896	0.911	0.911

\(p\)	\(\ell=0.01^{1/p}\)
1	\(0.01\)
2	\(0.10\)
10	\(0.63\)
100	\(0.955\)

classifier	test accuracy
LDA (shared \(\Sigma\))	0.881
QDA (per-class \(\Sigma_c\))	0.919
GaussianNB	0.904
k-NN (\(k=5\))	0.896
k-NN (\(k=15\))	0.911