সমাধান — অধ্যায় ৬.৯ · Anomaly Detection, Semi-Supervised & Online Learning (Survey)¶

অধ্যায় ফাইল: part-6-statistical-ml/06-09-anomaly-semisupervised-online.md (§৭ অনুশীলনী)। Part VI-এর সমাপনী অধ্যায়। চলমান dataset — seed-সূচক random_state=20260619: • anomaly: $285$ inlier (কেন্দ্রীয় Gaussian গুচ্ছ) + $15$ ring-outlier (চারপাশে একটা বলয়) = $300$ বিন্দু; contamination $\nu=15/300=0.05$ (৫%); সত্য label inlier $=0$, outlier $=1$। • semi-supervised: make_moons(n_samples=300, noise=0.15), label $\{0,1\}$; মাত্র ~১০% (৩০টা) বিন্দুর label রাখা, বাকি ৯০% অজানা ($-1$)। মূল notation: $D_M^2(x)=(x-\mu)^\top\Sigma^{-1}(x-\mu)\sim\chi^2_p$; anomaly score $s(x)$; contamination $\nu$; graph Laplacian $L=D-W$ ($D_{ii}=\sum_j w_{ij}$); online update $\theta_{t+1}=\theta_t-\eta_t\nabla\ell_t(\theta_t)$, regret $R_T$। canonical সংখ্যা — anomaly ROC AUC: Isolation Forest $1.000$, LOF $1.000$, One-Class SVM $0.941$, Elliptic Envelope (Mahalanobis) $1.000$; IF @ ৫%-cutoff precision $1.00$, recall $1.00$। semi-sup accuracy: labeled-only $0.833$ → LabelSpreading $0.989$ (gain $\approx0.156$)। §ঘ-এর runnable script (seed-সূচক random_state=20260619) উপরের সংখ্যাগুলো পুনরুৎপাদন করে (sklearn-সংস্করণ/optimizer-ভেদে, বিশেষত One-Class SVM ও LabelSpreading-এ, শেষ অঙ্কে সামান্য হেরফের সম্ভব; গল্প অপরিবর্তিত)। গাণিতিক প্রশ্নের (৯–১৪) সংখ্যা স্বয়ংসম্পূর্ণ — অধ্যায়-dataset থেকে স্বাধীন।

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

সমাধান ১ (★)¶

(ক) কী একটা বিন্দুকে anomaly বানায়। দুটো শর্ত একসাথে লাগে: (i) বিন্দুটি rare — অল্পসংখ্যক, গরিষ্ঠ data-র মতো নয়; এবং (ii) data-র মূল গঠন/density থেকে দূরে — স্বাভাবিক-অঞ্চলের বাইরে, "বেমানান"। শুধু বিরল হলেই anomaly নয় (একটা স্বাভাবিক বণ্টনের লেজেও কম বিন্দু থাকে), আবার শুধু আলাদা দেখালেও নয় — দুটো মিলেই সন্দেহ জাগায় যে বিন্দুটি ভিন্ন প্রক্রিয়া থেকে এসেছে।

(খ) novelty বনাম outlier detection। - novelty detection (semi-supervised anomaly): training set ধরা হয় পুরো-স্বাভাবিক/পরিষ্কার; model স্বাভাবিকতার সীমানা শেখে, তারপর নতুন বিন্দু সেই সীমানার বাইরে পড়লে novelty/anomaly বলে। training data-তে দূষণ নেই। - outlier detection (unsupervised): training data-তেই $\nu$ ভগ্নাংশ দূষণ (contamination) মিশে আছে; model গরিষ্ঠ-গঠন থেকে বিচ্যুত বিন্দুকে label ছাড়াই চেনে। এই অধ্যায়ের ring-dataset ঠিক এই দ্বিতীয় ঘরানার (৫% দূষণ মেশানো)।

(গ) contamination $\nu$। এখানে $\nu=15/300=0.05$ (৫%)। $\nu$ আগে-থেকে আন্দাজ জানা থাকলে detector সরাসরি threshold ঠিক করতে পারে: anomaly-score-এর উপরের $\nu$ ভগ্নাংশ বিন্দুকে anomaly বলে ছাঁটে (sklearn-এ contamination=0.05)। অর্থাৎ "কোন cutoff-এ কাটব" — এই কঠিন সিদ্ধান্তটা $\nu$ সরবরাহ করে দেয়।

সমাধান ২ (★)¶

(ক) চারটি পরিবার ও তাদের মাপকাঠি। - (i) fitted বণ্টন-কেন্দ্র থেকে দূরত্ব → statistical (Elliptic Envelope, Mahalanobis $D_M^2$)। - (ii) প্রতিবেশীর তুলনায় কম local density → density (Local Outlier Factor)। - (iii) random বিভাজনে সহজে আলাদা হওয়া (ছোট path) → isolation (Isolation Forest)। - (iv) শেখা স্বাভাবিক-অঞ্চলের সীমানার বাইরে পড়া → boundary (One-Class SVM)।

(খ) statistical-এর অনুমান। Elliptic Envelope ধরে নেয় inlier-রা একটা একক Gaussian/উপবৃত্তীয় গুচ্ছে বসে (mean $\mu$, covariance $\Sigma$)। এই অনুমান ভাঙলে — একাধিক গুচ্ছ (multi-modal), বাঁকা manifold, বা ভারী-লেজ — statistical দুর্বল হয়; তখন density (LOF) বা isolation (IF) বেশি robust, কারণ তারা কোনো global বণ্টন-আকার ধরে না, কেবল local ঘনত্ব বা বিভাজন-সহজতা দেখে।

(গ) কেন একাধিক চালানো। প্রতিটি পরিবারের অনুমান ও অন্ধবিন্দু আলাদা — statistical একক-Gaussian ধরে, density local-গঠনে নির্ভর, isolation random-split-এ, boundary kernel/সীমানায়। একটার যে anomaly হাতছাড়া হয় আরেকটা ধরতে পারে; তাই তুলনা/ensemble নির্ভরযোগ্য। canonical-এ এটাই দেখা যায়: IF/LOF/Elliptic AUC $1.000$ কিন্তু OC-SVM $0.941$ — পরিবার-ভেদে এই ring-গঠনে পার্থক্য স্পষ্ট।

সমাধান ৩ (★)¶

(ক) কেন anomaly ছোট path। Isolation Forest random feature + random split দিয়ে data বারবার দু-ভাগ করে যতক্ষণ প্রতিটি বিন্দু একা পাতায় আলাদা না হয়। একটা anomaly বিরল ও বিচ্ছিন্ন — তার চারপাশে ফাঁকা, তাই একটা এলোমেলো split প্রায়ই তাকে দ্রুত বাকিদের থেকে কেটে আলাদা করে (ছোট $h(x)$)। একটা inlier ঘন গুচ্ছের ভেতরে — চারপাশে অনেক প্রতিবেশী, তাকে একা করতে অনেক split লাগে (বড় $h(x)$)।

(খ) score-এর দিক। $s(x)=2^{-\mathbb E[h(x)]/c(n)}$। ছোট $h$ ⇒ exponent $-h/c(n)$ ছোট-ঋণাত্মক (শূন্যের কাছে) ⇒ $s\to 1$। তাই $s\approx1$ = anomaly; গড়-গভীরতার বিন্দুতে $s\approx0.5$, আর গভীরে-যাওয়া inlier-এ $s<0.5$। (উদাহরণ — $c(256)\approx10.24$: $h=3$ ⇒ $s\approx0.82$ (anomaly), $h=12$ ⇒ $s\approx0.44$ (inlier)।)

(গ) কেন এই dataset-এ নিখুঁত। ring-outlier কেন্দ্রীয় গুচ্ছ থেকে দূরে ও পাতলাভাবে ছড়ানো, তাই random split-এ অত্যন্ত দ্রুত isolate হয় (ছোট $h$, উঁচু $s$), আর কেন্দ্রের ঘন inlier-দের আলাদা করতে অনেক split লাগে — দুই দল score-এ পরিষ্কার আলাদা। ফল: ROC AUC $1.000$, এবং ৫%-cutoff-এ ঠিক $15$ ring-বিন্দু ধরা পড়ে ⇒ precision $1.00$, recall $1.00$।

সমাধান ৪ (★)¶

(ক) LOF-মানের অর্থ। - $\mathrm{LOF}(x)\approx1$ — বিন্দুর local density প্রতিবেশীর মতোই ⇒ inlier। - $\mathrm{LOF}(x)\gg1$ — প্রতিবেশীর তুলনায় density অনেক কম (বিন্দুটি আশেপাশে বিরল, কিন্তু তার প্রতিবেশীরা ঘন) ⇒ outlier। - $\mathrm{LOF}(x)<1$ — প্রতিবেশীর চেয়েও ঘন ⇒ গুচ্ছ-কেন্দ্রের বিন্দু।

(খ) কেন local। একটা global density-threshold ধরে নেয় সব জায়গায় একই ঘনত্ব। কিন্তু বাস্তবে একটা ঘন ও একটা পাতলা গুচ্ছ পাশাপাশি থাকতে পারে — global threshold হয় পাতলা গুচ্ছের স্বাভাবিক বিন্দুকে ভুলে outlier বলবে, নয়তো ঘন গুচ্ছের সূক্ষ্ম anomaly মিস করবে। LOF আপেক্ষিক (প্রতিবেশীর-সাপেক্ষ) density দেখে, তাই প্রতিটি অঞ্চলের নিজস্ব স্কেলে বিচার করে — varying-density data-তে এটাই সঠিক।

(গ) কেন ring ধরে। ring-outlier নিজের আশেপাশে পাতলা (নিচু local density), কিন্তু LOF যখন তার density-কে গঠন/নিকট-প্রতিবেশীর density-র সঙ্গে তুলনা করে, অনুপাত বড় হয়ে ওঠে ($\mathrm{LOF}\gg1$) ⇒ সব ring-বিন্দু outlier হিসেবে ধরা পড়ে (canonical AUC $1.000$)।

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

(ক) trivial detector। "সব inlier" detector accuracy $=\dfrac{285}{300}=0.95$ ($95\%$) — চমকপ্রদ উঁচু! কিন্তু সে $TP=0$, recall $=\dfrac{0}{15}=0$ — একটাও anomaly ধরেনি। এই এক সংখ্যাই দেখায় কেন imbalanced সমস্যায় উঁচু accuracy অর্থহীন: গরিষ্ঠ শ্রেণি ($95\%$ inlier) একাই accuracy-কে ফুলিয়ে দেয়, anomaly-detection-এর আসল কাজ (rare ধরা) সম্পূর্ণ ব্যর্থ হলেও।

(খ) precision বনাম recall। - precision $=\dfrac{TP}{TP+FP}$ — "আমি যাদের anomaly বললাম, তাদের কত ভাগ সত্যিই anomaly" (false-alarm-এর বিপরীত)। কম precision = অনেক মিথ্যা-অ্যালার্ম। - recall $=\dfrac{TP}{TP+FN}$ — "সত্যিকার anomaly-র কত ভাগ আমি ধরলাম" (miss-এর বিপরীত)। কম recall = অনেক anomaly হাতছাড়া। এরা rare-শ্রেণির উপর সরাসরি ফোকাস করে (TN গণনায় ঢোকে না), তাই accuracy যেখানে $282$ TN-এ ডুবে যায়, precision/recall সেখানে detector-এর আসল গুণ ধরে।

(গ) ROC AUC। ROC AUC = threshold না বেছেই detector-এর ranking-গুণ: একটা random anomaly-কে একটা random inlier-এর চেয়ে উঁচু anomaly-score দেওয়ার সম্ভাবনা। $1.0$ = নিখুঁত পৃথকীকরণ (সব anomaly সব inlier-এর উপরে), $0.5$ = এলোমেলো। canonical-এ IF/LOF/Elliptic $1.000$ = এই ring-গঠনে নিখুঁত আলাদা; OC-SVM $0.941$ = খুব ভালো কিন্তু সামান্য overlap (কিছু anomaly-score কিছু inlier-score-এর নিচে পড়ে) — boundary-পরিবার এখানে অন্যদের চেয়ে একটু পিছিয়ে।

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

(ক) তিন অনুমান। - smoothness — কাছাকাছি দুই বিন্দুর label সম্ভবত এক (ছোট পরিবর্তনে label বদলায় না)। - cluster — একই গুচ্ছের বিন্দু সম্ভবত একই শ্রেণি; অর্থাৎ decision boundary কম-ঘনত্বের অঞ্চল দিয়ে যায়, ঘন গুচ্ছের মাঝখান দিয়ে নয় (low-density separation)। - manifold — data একটা নিম্ন-মাত্রিক বাঁকা manifold-এ বসে, আর label সেই manifold বরাবর মসৃণভাবে বদলায় (Euclidean-এ কাছে নয়, manifold-এ কাছে — যা গুরুত্বপূর্ণ; ৬.৮-এর সরাসরি যোগ)।

(খ) make_moons-এ কোনটা। দুটোই দৃঢ়ভাবে প্রযোজ্য: cluster/low-density-separation — দুই চাঁদের মাঝে একটা স্পষ্ট কম-ঘনত্বের ফাঁক, boundary সেখানে বসা উচিত; এবং manifold — প্রতিটি চাঁদ একটা বাঁকা (প্রায় ১D) গঠন, label সেই বাঁক বরাবর স্থির। সরল Euclidean-boundary দুই চাঁদের বাঁক উপেক্ষা করে ভুল করে; manifold/cluster-সচেতন পদ্ধতি ঠিক করে।

(গ) $0.156$ লাফের অর্থ। labeled-only ($0.833$) কেবল ৩০টা বিন্দু দেখে একটা সরল boundary টানে — চাঁদের পুরো বাঁকা আকৃতি বা মাঝের ফাঁক জানে না। unlabeled ২৭০টা বিন্দু যোগ করলে তারা গঠন ফাঁস করে দেয়: চাঁদের সম্পূর্ণ আকৃতি ও মাঝের কম-ঘনত্ব-ফাঁক দৃশ্যমান হয়, তাই LabelSpreading boundary-কে সঠিক ফাঁকে বসায় ⇒ $0.989$। এটাই semi-supervised-এর মূল প্রমাণ: label-হীন data-ও গঠন দিয়ে শেখায়, যদি গঠন label-সম্পর্কিত হয়।

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

(ক) কেন কাছের বিন্দু একই label। label propagation-এ একটা বিন্দুর label তার edge-যুক্ত প্রতিবেশীদের label-এর (similarity $w_{ij}$-ভারিত) গড় হিসেবে ক্রমাগত আপডেট হয় — তাপ যেমন গরম-থেকে-ঠান্ডায় ছড়িয়ে সমান হয়। বড় $w_{ij}$ (কাছের জোড়া) মানে দৃঢ় টান, তাই দৃঢ়-সংযুক্ত বিন্দুরা একে অপরের label টেনে নিয়ে প্রায় একই মানে পৌঁছায় — হুবহু "কাছের ⇒ একই label" (smoothness)।

(খ) Laplacian-অমসৃণতা। $f^\top L f=\tfrac12\sum_{ij}w_{ij}(f_i-f_j)^2$ বড় হয় ঠিক তখনই যখন edge-যুক্ত (কাছের, বড় $w_{ij}$) বিন্দুর label $f_i,f_j$ খুব ভিন্ন। propagation কার্যত এটি ছোট করে, অর্থাৎ কাছের বিন্দুর label মেলায় — এটাই smoothness/cluster অনুমানের সরাসরি গাণিতিক রূপ (ঘন অঞ্চলে $w_{ij}$ বড় বলে সেখানে label বদলালে penalty বেশি, তাই boundary কম-ঘনত্বে সরে যায়)।

(গ) propagation বনাম spreading। label propagation — unnormalized Laplacian, হার্ড clamping (জানা label কখনো বদলায় না)। label spreading — normalized Laplacian $\mathcal L=D^{-1/2}LD^{-1/2}$ + soft clamping (একটা $\alpha$ দিয়ে জানা label সামান্য বদলাতে দেয়)। ফলে spreading label-noise/ভুল-label-এ বেশি robust। এই অধ্যায়ে LabelSpreading $0.989$ পায়।

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

(ক) দুই সুবিধা। (i) মেমরি/scalability — প্রতি ধাপে কেবল একটা (বা ছোট mini-batch) বিন্দু লাগে, পুরো dataset একসাথে রাখতে হয় না; তাই বিশাল বা অসীম স্রোতেও চলে। (ii) adaptivity — $\theta$ ক্রমাগত আপডেট হয়, তাই data-বণ্টন সময়ের সঙ্গে সরলে (concept drift) model আপনাআপনি নতুন বণ্টনে মানিয়ে নেয় (batch model পুরোনো data-তে আটকে থাকত)।

(খ) regret-এর অর্থ। $R_T=\sum_{t=1}^T\ell_t(\theta_t)-\min_{\theta^\*}\sum_{t=1}^T\ell_t(\theta^\*)$ মাপে — online learner-এর (যে প্রতি ধাপে কেবল অতীত দেখে $\theta_t$ বাছল) মোট ক্ষতি, বিয়োগ পুরো sequence আগে-থেকে-জেনে বাছা সেরা একক স্থির $\theta^\*$-এর মোট ক্ষতি। অর্থাৎ "online বলে, সেরা hindsight-কৌশলের তুলনায়, কতটা পিছিয়ে রইলাম"।

(গ) sublinear regret। $R_T$ sublinear ($o(T)$, যেমন online GD-তে $\eta_t\propto1/\sqrt t$ হলে $O(\sqrt T)$) মানে $R_T$ $T$-এর চেয়ে ধীরে বাড়ে, তাই $\dfrac{R_T}{T}\to0$ ($T\to\infty$)। এই average regret $\to0$ মানে প্রতি-ধাপে গড়ে learner asymptotically সেরা স্থির কৌশলের সমান-ভালো হয়ে যায় — যদিও সে কখনো ভবিষ্যৎ data আগে দেখেনি। এটাই "ভালো online algorithm"-এর সংজ্ঞা।

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

সমাধান ৯ (★★) — Mahalanobis, diagonal Σ¶

$p=2$, $\mu=(0,0)$, $\Sigma=\begin{pmatrix}4&0\\0&1\end{pmatrix}$, বিন্দু $x=(3,2)$।

(ক) $\Sigma^{-1}$ ও $D_M^2$। diagonal বলে inverse element-wise reciprocal: $$ \Sigma^{-1}=\begin{pmatrix}1/4&0\0&1\end{pmatrix}=\begin{pmatrix}0.25&0\0&1\end{pmatrix}. $$ $$ D_M^2(x)=(x-\mu)^\top\Sigma^{-1}(x-\mu)=\begin{pmatrix}3&2\end{pmatrix}\begin{pmatrix}0.25&0\0&1\end{pmatrix}\begin{pmatrix}3\2\end{pmatrix}=0.25\cdot 3^2+1\cdot 2^2=2.25+4=\mathbf{6.25}. $$

(খ) χ²-cutoff। $5\%$ স্তরে $\chi^2_{2,0.95}=5.991$। যেহেতু $D_M^2=6.25>5.991$ ⇒ বিন্দুটি anomaly হিসেবে flag হবে। p-value $=P(\chi^2_2>6.25)\approx \mathbf{0.044}$ ($<0.05$, তাই ৫% স্তরে সদ্য-বিচ্যুত)।

(গ) কেন Euclidean ভুল। plain Euclidean দূরত্ব $\lVert x-\mu\rVert=\sqrt{3^2+2^2}=\sqrt{13}\approx3.61$ সব অক্ষকে সমান ধরত। কিন্তু $x$-অক্ষে spread বেশি ($\sigma_x=\sqrt4=2$), তাই $x$-coordinate $3$ আসলে মাত্র $3/2=1.5\sigma_x$ দূরে — অথচ $y$-coordinate $2$ পুরো $2\sigma_y$ দূরে। $\Sigma^{-1}$ প্রতিটি অক্ষকে তার নিজ variance দিয়ে ভাগ করে "কত standard-deviation দূরে" মাপে; তাই অসম-variance (ও correlated) data-তে Mahalanobis সঠিক, Euclidean নয়।

সমাধান ১০ (★★) — Mahalanobis, correlated Σ¶

$p=2$, $\mu=(0,0)$, $\Sigma=\begin{pmatrix}1&0.8\\0.8&1\end{pmatrix}$, বিন্দু $x=(2,-1)$।

(ক) $\det\Sigma$ ও $\Sigma^{-1}$। $$ \det\Sigma=1\cdot1-0.8\cdot0.8=1-0.64=0.36. $$ $2\times2$ inverse সূত্র ($\Sigma^{-1}=\frac{1}{\det}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$): $$ \Sigma^{-1}=\frac{1}{0.36}\begin{pmatrix}1&-0.8\-0.8&1\end{pmatrix}\approx\begin{pmatrix}2.778&-2.222\-2.222&2.778\end{pmatrix}. $$

(খ) $D_M^2$ ও cutoff। $x-\mu=(2,-1)$: $$ D_M^2=2.778\cdot 2^2 \;+\; 2\cdot(-2.222)\cdot(2)(-1)\;+\;2.778\cdot(-1)^2 =11.11+8.89+2.78=\mathbf{22.78}. $$ (মাঝের পদ: off-diagonal $-2.222$ দু-বার, $x_1 x_2=(2)(-1)=-2$ গুণ ⇒ $2\cdot(-2.222)\cdot(-2)=+8.89$।) যেহেতু $22.78\gg\chi^2_{2,0.99}=9.210$ (এমনকি $\gg5.991$) ⇒ জোরালোভাবে flag (p-value $\approx0$)।

(গ) কেন বিশাল। Euclidean দূরত্ব $\sqrt{2^2+(-1)^2}=\sqrt5\approx2.24$ — মোটেই খুব দূরে নয়। কিন্তু $\Sigma$-তে দুই feature দৃঢ়-positively correlated (off-diagonal $0.8$), অর্থাৎ data সাধারণত একসাথে বাড়ে বা একসাথে কমে। বিন্দু $(2,-1)$ ঠিক উল্টো প্যাটার্ন (একটা ধনাত্মক, একটা ঋণাত্মক) — correlation-অক্ষ বরাবর বহু-$\sigma$ দূরে। $\Sigma^{-1}$-এর বড় ঋণাত্মক off-diagonal এই "correlation-বিরোধী" গঠন ধরে $D_M^2$-কে ফুলিয়ে তোলে — তাই Euclidean-এ কাছে হলেও Mahalanobis-এ চরম anomaly।

সমাধান ১১ (★★) — imbalanced confusion matrix¶

$300$ বিন্দু, $15$ সত্য anomaly ($285$ inlier); detector $15$টিকে anomaly বলল, যার $12$ সত্য + $3$ ভুল। (anomaly = positive)

(ক) confusion matrix। - $TP=12$ (সত্য anomaly সঠিকভাবে ধরা)। - $FP=3$ (inlier-কে ভুলে anomaly বলা)। - $FN=15-12=3$ (সত্য anomaly miss)। - $TN=285-3=282$ (inlier সঠিকভাবে inlier)।

	predicted anomaly	predicted inlier
actual anomaly	$TP=12$	$FN=3$
actual inlier	$FP=3$	$TN=282$

(খ) তিন metric। $$ \text{precision}=\frac{TP}{TP+FP}=\frac{12}{12+3}=\frac{12}{15}=\mathbf{0.80},\qquad \text{recall}=\frac{TP}{TP+FN}=\frac{12}{12+3}=\frac{12}{15}=\mathbf{0.80}, $$ $$ \text{accuracy}=\frac{TP+TN}{300}=\frac{12+282}{300}=\frac{294}{300}=\mathbf{0.98}. $$

(গ) কেন precision/recall স্পষ্ট ছবি। canonical IF-এর precision/recall দুটোই $1.00$ ($TP=15,FP=0,FN=0$) — এই detector-এর $0.80$ সরাসরি বলে "৮০% অ্যালার্ম সত্য, ৮০% anomaly ধরা, তাই ২০% miss + ২০% false alarm"। অথচ accuracy দিয়ে দুজনকে আলাদা করা কঠিন: IF-এর accuracy $\frac{15+285}{300}=1.00$, এই detector-এর $0.98$ — প্রায় একই, কারণ বিশাল $TN$ ($\approx282$) দুজনেরই accuracy ফুলিয়ে দেয়। তাই rare-শ্রেণিতে precision/recall ভেদ ধরে, accuracy নয়।

সমাধান ১২ (★★) — online gradient step¶

model $f(x)=\theta x$, loss $\ell_t(\theta)=\tfrac12(\theta x_t-y_t)^2$, gradient $\nabla\ell_t=(\theta x_t-y_t)x_t$, update $\theta_{t+1}=\theta_t-\eta\nabla\ell_t$; $\theta_0=0$, $\eta=0.1$; স্রোত $(2,4),(1,3)$।

(ক) ধাপ ১ — বিন্দু $(x_1,y_1)=(2,4)$। - prediction $=\theta_0 x_1=0\cdot 2=0$। - error $=\theta_0 x_1-y_1=0-4=-4$। - gradient $=(\theta_0 x_1-y_1)x_1=(-4)(2)=-8$। - $\theta_1=\theta_0-\eta\cdot\text{grad}=0-0.1\cdot(-8)=\mathbf{0.8}$।

(খ) ধাপ ২ — বিন্দু $(x_2,y_2)=(1,3)$, নতুন $\theta_1=0.8$। - prediction $=\theta_1 x_2=0.8\cdot 1=0.8$। - error $=0.8-3=-2.2$। - gradient $=(-2.2)(1)=-2.2$। - $\theta_2=\theta_1-0.1\cdot(-2.2)=0.8+0.22=\mathbf{1.02}$।

(গ) দিক ও চরিত্র। $\theta$ $0\to0.8\to1.02$ — সত্যিকার ঢালের ($y\approx2x$ হলে $\theta\approx2$) দিকে ক্রমশ বাড়ছে; আরও বিন্দু এলে $\theta$ $2$-এর দিকে যেতে থাকবে। মূল চরিত্র: প্রতিটি observation আসামাত্র $\theta$ আপডেট হয় (পুরো data একসাথে দরকার নেই) — এটাই online/streaming learning: incremental ও drift-সচেতন (নতুন data সঙ্গে সঙ্গে $\theta$-কে নাড়ায়)।

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

সমাধান ১৩ (★★★) — Mahalanobis $\to\chi^2_p$¶

দাবি: $X\sim\mathcal N_p(\mu,\Sigma)$, $\Sigma$ positive-definite ⇒ $D_M^2(X)=(X-\mu)^\top\Sigma^{-1}(X-\mu)\sim\chi^2_p$।

(ক) whitening — $Z=\Sigma^{-1/2}(X-\mu)\sim\mathcal N_p(0,I)$। $\Sigma$ symmetric positive-definite, তাই eigen-decomposition $\Sigma=Q\Lambda Q^\top$ ($\Lambda$ ধনাত্মক-diagonal) থেকে একটা symmetric square-root $\Sigma^{1/2}=Q\Lambda^{1/2}Q^\top$ আছে ($\Sigma^{1/2}\Sigma^{1/2}=\Sigma$, এবং $\Sigma^{-1/2}=Q\Lambda^{-1/2}Q^\top$, symmetric)। সংজ্ঞা $Z=\Sigma^{-1/2}(X-\mu)$ — একটা affine রূপান্তর, তাই $Z$ Gaussian। mean ও covariance: $$ \mathbb E[Z]=\Sigma^{-1/2}\,\mathbb E[X-\mu]=\Sigma^{-1/2}\cdot 0=0, $$ $$ \mathrm{Cov}(Z)=\Sigma^{-1/2}\,\mathrm{Cov}(X-\mu)\,\Sigma^{-1/2}=\Sigma^{-1/2}\,\Sigma\,\Sigma^{-1/2} =\Sigma^{-1/2}\,\Sigma^{1/2}\Sigma^{1/2}\,\Sigma^{-1/2}=I_p. $$ তাই $Z\sim\mathcal N_p(0,I_p)$ — "whitened" (uncorrelated, unit-variance)।

(খ) $D_M^2=Z^\top Z$। যেহেতু $\Sigma^{-1/2}$ symmetric এবং $\Sigma^{-1/2}\Sigma^{-1/2}=\Sigma^{-1}$: $$ Z^\top Z=\big(\Sigma^{-1/2}(X-\mu)\big)^\top\big(\Sigma^{-1/2}(X-\mu)\big) =(X-\mu)^\top\Sigma^{-1/2}\Sigma^{-1/2}(X-\mu)=(X-\mu)^\top\Sigma^{-1}(X-\mu)=D_M^2(X). $$ আর $Z^\top Z=\sum_{k=1}^p Z_k^2$।

(গ) χ²-উপসংহার। $\mathrm{Cov}(Z)=I_p$ ⇒ $Z_1,\dots,Z_p$ পরস্পর uncorrelated; jointly-Gaussian-এ uncorrelated $\Rightarrow$ স্বাধীন, এবং প্রতিটি $Z_k\sim\mathcal N(0,1)$। সংজ্ঞা-অনুযায়ী $p$টি স্বাধীন standard-normal-এর বর্গের যোগফল $\chi^2_p$: $$ D_M^2(X)=\sum_{k=1}^p Z_k^2\sim\chi^2_p.\qquad\blacksquare $$ এক বাক্যে তাৎপর্য: যেহেতু স্বাভাবিক বিন্দুর $D_M^2$ ঠিক $\chi^2_p$ মেনে চলে, $P(\chi^2_p>c)=\alpha$ থেকে পাওয়া cutoff $c$ (যেমন $p=2,\ \alpha=0.05$-এ $c=5.991$) এমন anomaly-threshold দেয় যাতে স্বাভাবিক বিন্দুর মাত্র $\alpha$ ভগ্নাংশ ভুলে flag হয় — অর্থাৎ একটা নিয়ন্ত্রিত false-positive হার (প্রশ্ন ৯–১০-এর χ²-cutoff-এর বৈধতা)।

সমাধান ১৪ (★★★) — label propagation = graph-Laplacian-অমসৃণতা¶

$L=D-W$ ($W$ symmetric, $W_{ij}=w_{ij}\ge0$; $D$ diagonal, $D_{ii}=\sum_j w_{ij}$)। দাবি: $f^\top L f=\tfrac12\sum_{ij}w_{ij}(f_i-f_j)^2$।

(ক) বিস্তার। ডান দিক থেকে শুরু করে বাঁ দিকে পৌঁছাই: $$ \tfrac12\sum_{i=1}^n\sum_{j=1}^n w_{ij}(f_i-f_j)^2 =\tfrac12\sum_{ij}w_{ij}\big(f_i^2-2f_if_j+f_j^2\big) =\tfrac12\sum_{ij}w_{ij}f_i^2-\sum_{ij}w_{ij}f_if_j+\tfrac12\sum_{ij}w_{ij}f_j^2. $$ প্রথম পদ: $\tfrac12\sum_i\big(\sum_j w_{ij}\big)f_i^2=\tfrac12\sum_i D_{ii}f_i^2=\tfrac12 f^\top D f$। তৃতীয় পদ: index-নাম বদলে ($i\leftrightarrow j$) ও $W$ symmetric বলে একই $=\tfrac12 f^\top D f$। দুটো মিলে $f^\top D f$। মাঝের পদ: $\sum_{ij}w_{ij}f_if_j=f^\top W f$। তাই $$ \tfrac12\sum_{ij}w_{ij}(f_i-f_j)^2=f^\top D f-f^\top W f=f^\top(D-W)f=f^\top L f.\qquad\blacksquare $$

(খ) PSD ও null-space। ডান রূপে প্রতিটি পদ $w_{ij}(f_i-f_j)^2\ge0$ (যেহেতু $w_{ij}\ge0$ ও বর্গ $\ge0$), তাই যোগফল $f^\top L f\ge0$ সব $f$-এর জন্য ⇒ $L$ positive-semidefinite। সমতা ($f^\top L f=0$) ঠিক তখনই যখন প্রতিটি edge-যুক্ত জোড়ায় ($w_{ij}>0$) $f_i=f_j$ — অর্থাৎ $f$ প্রতিটি connected component-এ ধ্রুবক (graph connected হলে $f$ সর্বত্র ধ্রুবক, যা $L\mathbf 1=0$ eigenvector-এর সঙ্গে সঙ্গতিপূর্ণ)।

(গ) কেন smoothness/cluster বাস্তবায়িত হয়। penalty $w_{ij}(f_i-f_j)^2$ $w_{ij}$-ভারিত — কাছের/দৃঢ়-সংযুক্ত জোড়ায় ($w_{ij}$ বড়) label ভিন্ন হলে penalty সবচেয়ে বড়। তাই $f^\top L f$ ছোট-করা minimizer কাছের বিন্দুর label মেলায় (smoothness) এবং ঘন গুচ্ছ একই label-এ রাখে (cluster)। label কেবল সেখানে সস্তায় বদলাতে পারে যেখানে $w_{ij}$ ছোট — অর্থাৎ কম-ঘনত্বের ফাঁক; তাই learned boundary স্বাভাবিকভাবে কম-ঘনত্ব-অঞ্চলে বসে (low-density separation), যা semi-supervised-এর মূল লক্ষ্য।

ঘ · কোডিং (Python)¶

সমাধান ১৫ (★★★) — চারটি anomaly detector + ROC AUC¶

# 06-09 — চারটি anomaly detector এক ring-dataset-এ: ROC AUC তুলনা (+ IF precision/recall).
# seed-সূচক random_state=20260619 — 285 inlier (কেন্দ্রীয় Gaussian) + 15 ring-outlier; contamination ν=0.05.
import numpy as np
from sklearn.ensemble import IsolationForest
from sklearn.neighbors import LocalOutlierFactor
from sklearn.svm import OneClassSVM
from sklearn.covariance import EllipticEnvelope
from sklearn.metrics import roc_auc_score, precision_score, recall_score

SEED = 20260619
rng = np.random.default_rng(SEED)

# ----- canonical dataset: 285 inlier + 15 ring-outlier -----
n_in, n_out = 285, 15
inliers = rng.normal(0.0, 1.0, size=(n_in, 2))            # কেন্দ্রীয় Gaussian গুচ্ছ
r       = 5.0 + rng.normal(0.0, 0.3, size=n_out)          # বলয়-ব্যাসার্ধ ~5
theta   = rng.uniform(0.0, 2*np.pi, size=n_out)
outliers = np.column_stack([r*np.cos(theta), r*np.sin(theta)])  # চারপাশে ring
X = np.vstack([inliers, outliers])
y_true = np.r_[np.zeros(n_in), np.ones(n_out)].astype(int)       # inlier=0, outlier=1
NU = 0.05                                                        # contamination = 15/300

def auc_of(name, score):
    """score: বড় = বেশি-anomaly; roc_auc_score(y_true, score)।"""
    a = roc_auc_score(y_true, score)
    print(f"{name:16s}: ROC AUC = {a:.3f}")
    return a

# ----- 1. Isolation Forest (isolation / short path) -----
iso = IsolationForest(contamination=NU, random_state=SEED).fit(X)
auc_of("IsolationForest", -iso.score_samples(X))     # canonical 1.000
pred_iso = (iso.predict(X) == -1).astype(int)        # -1 = outlier → 1
print(f"   IF @5%-cutoff: precision = {precision_score(y_true, pred_iso):.2f}, "
      f"recall = {recall_score(y_true, pred_iso):.2f}")   # canonical 1.00 / 1.00

# ----- 2. Local Outlier Factor (density) -----
lof = LocalOutlierFactor(contamination=NU)
lof.fit_predict(X)
auc_of("LOF", -lof.negative_outlier_factor_)         # canonical 1.000

# ----- 3. One-Class SVM (boundary) -----
ocsvm = OneClassSVM(nu=NU, gamma="scale").fit(X)
auc_of("OneClassSVM", -ocsvm.decision_function(X))   # canonical 0.941

# ----- 4. Elliptic Envelope (statistical / Mahalanobis) -----
ell = EllipticEnvelope(contamination=NU, random_state=SEED).fit(X)
auc_of("EllipticEnvelope", -ell.score_samples(X))    # canonical 1.000

print("\n=> isolation/density/statistical (IF, LOF, Elliptic) নিখুঁত 1.000; "
      "boundary (OneClassSVM) সামান্য পিছিয়ে 0.941 — এই ring-গঠনে।")

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

IsolationForest : ROC AUC = 1.000
   IF @5%-cutoff: precision = 1.00, recall = 1.00
LOF             : ROC AUC = 1.000
OneClassSVM     : ROC AUC = 0.941
EllipticEnvelope: ROC AUC = 1.000

=> isolation/density/statistical (IF, LOF, Elliptic) নিখুঁত 1.000; boundary (OneClassSVM) সামান্য পিছিয়ে 0.941 — এই ring-গঠনে।

পাঠ। 1. Isolation Forest — নিখুঁত (isolation)। AUC $1.000$, ৫%-cutoff precision/recall $1.00$ — ring-outlier বিরল ও বিচ্ছিন্ন বলে random split-এ দ্রুত isolate হয় (ছোট path, উঁচু score)। 2. LOF — নিখুঁত (density)। AUC $1.000$ — ring-বিন্দুর local density প্রতিবেশী/কেন্দ্রের তুলনায় অনেক কম ($\mathrm{LOF}\gg1$), তাই সব ধরা পড়ে। 3. Elliptic Envelope — নিখুঁত (statistical)। AUC $1.000$ — inlier-গুচ্ছ সত্যিই একটা Gaussian, তাই Mahalanobis $D_M^2$ ring-বিন্দুকে স্পষ্ট বড় দূরত্বে ফেলে (χ²-cutoff সঠিক কাজ করে)। 4. One-Class SVM — সামান্য দুর্বল (boundary)। AUC $0.941$ — এই বলয়-আকৃতির স্বাভাবিক/অস্বাভাবিক বিন্যাসে RBF-boundary নিখুঁতভাবে আলাদা করতে পারে না (কিছু score-overlap); boundary-পরিবার এখানে অন্যদের চেয়ে পিছিয়ে।

মূল শিক্ষা: detector-এর পরিবার-অনুমান data-র গঠনের সঙ্গে মিললে নিখুঁত ফল (এখানে isolation/density/statistical তিনটিই); না-মিললে (boundary/OC-SVM এই ring-এ) পিছিয়ে পড়ে — তাই একাধিক পরিবার চালিয়ে AUC-তে তুলনা করা ভালো অভ্যাস, আর imbalanced বলে accuracy নয়, ROC AUC / precision / recall দেখা।

(দ্রষ্টব্য: sklearn-সংস্করণ-ভেদে, বিশেষত One-Class SVM-এ, শেষ অঙ্কে সামান্য হেরফের সম্ভব; কিন্তু গল্প — IF/LOF/Elliptic $\approx1.0$ বনাম OC-SVM $\approx0.94$ — অপরিবর্তিত।)

সমাধান ১৬ (★★★) — semi-supervised label spreading¶

# 06-09 — semi-supervised: unlabeled data কতটা সাহায্য করে (make_moons)।
# seed-সূচক random_state=20260619 — 300 বিন্দু, মাত্র ~10% (30টা) label রাখা।
import numpy as np
from sklearn.datasets import make_moons
from sklearn.semi_supervised import LabelSpreading
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

SEED = 20260619
rng = np.random.default_rng(SEED)

# ----- canonical dataset: দুই বাঁকা চাঁদ -----
X, y = make_moons(n_samples=300, noise=0.15, random_state=SEED)

# ----- ~10% label রাখা, বাকি অজানা (-1) -----
n_lab = 30
labeled = rng.choice(len(X), size=n_lab, replace=False)
y_train = np.full(len(X), -1)          # -1 = অজানা label
y_train[labeled] = y[labeled]

# ----- (1) labeled-only: শুধু 30টা labeled বিন্দুতে kNN -----
clf = KNeighborsClassifier(n_neighbors=5).fit(X[labeled], y[labeled])
acc_lab = accuracy_score(y, clf.predict(X))
print(f"labeled-only (kNN, 30 labels) : accuracy = {acc_lab:.3f}")   # canonical 0.833

# ----- (2) LabelSpreading: labeled + unlabeled সব দিয়ে graph-diffusion -----
ls = LabelSpreading(kernel="knn", n_neighbors=10).fit(X, y_train)
acc_ls = accuracy_score(y, ls.transduction_)
print(f"LabelSpreading (270 unlabeled): accuracy = {acc_ls:.3f}")    # canonical 0.989

print(f"\n=> unlabeled যোগে gain = {acc_ls - acc_lab:+.3f} "
      f"(গঠন/manifold label ছড়াতে সাহায্য করল)।")

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

labeled-only (kNN, 30 labels) : accuracy = 0.833
LabelSpreading (270 unlabeled): accuracy = 0.989

=> unlabeled যোগে gain = +0.156 (গঠন/manifold label ছড়াতে সাহায্য করল)।

পাঠ। 1. labeled-only সীমিত ($0.833$)। মাত্র ৩০টা বিন্দু দেখে kNN একটা স্থানীয় boundary টানে — দুই চাঁদের পুরো বাঁকা আকৃতি বা মাঝের কম-ঘনত্ব-ফাঁক জানে না, তাই বাঁকের কাছে ভুল করে। 2. LabelSpreading বড় উন্নতি ($0.989$)। ২৭০টা unlabeled বিন্দু চাঁদের সম্পূর্ণ manifold/cluster-গঠন ও মাঝের ফাঁক ফাঁস করে; graph-diffusion ($L=D-W$) জানা label edge বরাবর ছড়িয়ে boundary-কে সঠিক কম-ঘনত্ব-অঞ্চলে বসায়। 3. $+0.156$ লাফ = semi-supervised-এর প্রমাণ। label-হীন data-ও গঠন দিয়ে শেখাল — কারণ এখানে গঠন (চাঁদের manifold, দুই চাঁদের ফাঁক) সরাসরি label-সম্পর্কিত (cluster/manifold অনুমান বৈধ)।

মূল শিক্ষা: unlabeled data বিনামূল্যে নয়-বরং তথ্যপূর্ণ — যখন cluster/manifold/smoothness অনুমান data-তে সত্য, তখন বহু unlabeled বিন্দু অল্প label-কে শক্তিশালী করে (এখানে $0.833\to0.989$); label propagation/spreading এই গঠন-জ্ঞানকে graph-Laplacian-diffusion দিয়ে কাজে লাগায়।

(দ্রষ্টব্য: seed/সংস্করণ-ভেদে শেষ অঙ্কে সামান্য হেরফের সম্ভব; কিন্তু গল্প — labeled-only-র তুলনায় LabelSpreading-এ স্পষ্ট, বড় উন্নতি — অপরিবর্তিত।)

	predicted anomaly	predicted inlier
actual anomaly	\(TP=12\)	\(FN=3\)
actual inlier	\(FP=3\)	\(TN=282\)

সমাধান — অধ্যায় ৬.৯ · Anomaly Detection, Semi-Supervised & Online Learning (Survey)¶

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

সমাধান ১ (★)¶

সমাধান ২ (★)¶

সমাধান ৩ (★)¶

সমাধান ৪ (★)¶

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

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

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

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

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

সমাধান ৯ (★★) — Mahalanobis, diagonal Σ¶

সমাধান ১০ (★★) — Mahalanobis, correlated Σ¶

সমাধান ১১ (★★) — imbalanced confusion matrix¶

সমাধান ১২ (★★) — online gradient step¶

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

সমাধান ১৩ (★★★) — Mahalanobis \(\to\chi^2_p\)¶

সমাধান ১৪ (★★★) — label propagation = graph-Laplacian-অমসৃণতা¶

ঘ · কোডিং (Python)¶

সমাধান ১৫ (★★★) — চারটি anomaly detector + ROC AUC¶

সমাধান ১৬ (★★★) — semi-supervised label spreading¶