সমাধান — অধ্যায় ৬.৪ · Classification II: SVM & Kernel Methods¶

অধ্যায় ফাইল: part-6-statistical-ml/06-04-svm-kernel-methods.md (§৭ অনুশীলনী)। চলমান dataset — seed-সূচক 20260619: make_moons ($n=300$, $\text{noise}=0.25$), $70/30$ train–test split ($210$ train, $90$ test)। মূল notation: separating hyperplane $w^\top x+b=0$, label $y_i\in\{-1,+1\}$, geometric margin $2/\lVert w\rVert$, slack $\xi_i\ge0$, penalty $C$, dual coefficient $\alpha_i$, RBF kernel $K(x,x')=\exp(-\gamma\lVert x-x'\rVert^2)$, hinge loss $\max(0,\,1-y_i f(x_i))$, $f(x)=w^\top x+b$। canonical সংখ্যা। kernel-ভেদে (test accuracy, #SV): Linear $0.811$ (74); RBF $C{=}1$: $0.900$ (63); RBF $C{=}10$: $0.944$ (45, সেরা); Poly deg3: $0.833$। $C$-sweep (RBF): $0.1\to0.833/121$, $1\to0.900/63$, $10\to0.944/45$, $100\to0.933/37$। $\gamma$-sweep (RBF, $C$ স্থির): $0.1\to0.800$, $5\to0.956$, $20\to0.956/132$। §ঘ-এর runnable script (seed-সূচক 20260619) উপরের সংখ্যাগুলো পুনরুৎপাদন করে। গাণিতিক প্রশ্নের (৬, ৭, ১০–১২) সংখ্যাগুলো স্বয়ংসম্পূর্ণ — অধ্যায়-dataset থেকে স্বাধীন।

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

সমাধান ১ (★)¶

(ক) কেন max-margin generalization-এর পক্ষে। linearly separable হলে অসংখ্য hyperplane training-data-তে শূন্য-ভুল করে, কিন্তু তারা সমান "নিরাপদ" নয়। যে boundary দুই শ্রেণির নিকটতম বিন্দু থেকে যত দূরে (চওড়া margin), নতুন বা সামান্য-সরে-যাওয়া (noisy) বিন্দু সেই boundary-র ভুল পাশে পড়ার সম্ভাবনা তত কম। অর্থাৎ চওড়া margin = boundary-র চারপাশে একটি "নিরাপত্তা-অঞ্চল", যা train-থেকে-test-এ স্থানান্তরে সিদ্ধান্ত-স্থিতিশীল রাখে — ভালো generalization।

(খ) ৬.১-এর সংযোগ। সম্ভাব্য (সব শূন্য-ভুল) boundary-গুলোর মধ্যে সবচেয়ে "সরল/স্থিতিশীল"টা বাছাই করা একধরনের capacity নিয়ন্ত্রণ/regularization (৬.১): margin সর্বোচ্চ করা = $\lVert w\rVert$ সর্বনিম্ন করা = মডেলের কার্যকর-জটিলতা সীমিত করা, যা variance কমায়। তাই max-margin নিজেই একটি অন্তর্নির্মিত regularizer।

সমাধান ২ (★)¶

(ক) সংজ্ঞা। support vector হলো সেই training-বিন্দু যাদের dual coefficient $\alpha_i>0$। জ্যামিতিকভাবে এরা margin-এর উপর বসে, বা (soft-margin-এ) margin-এর ভিতরে/ভুল পাশে — অর্থাৎ ঠিক যেসব বিন্দু boundary-কে "ঠেলে ধরে রাখে"।

(খ) non-SV মুছলে boundary অপরিবর্তিত। decision function $$ f(x)=\sum_{i}\alpha_i y_i\,K(x_i,x)+b $$ -এ যাদের $\alpha_i=0$ (অর্থাৎ non-support-vector) তারা যোগফলে কোনো অবদানই রাখে না। তাই এমন একটি বিন্দু মুছে আবার train করলে সমাধান ($\alpha,b,w$) ও $f$ অপরিবর্তিত — boundary নড়ে না। বিপরীতে support vector-এর $\alpha_i>0$, তারা $f$-এ সক্রিয়; একটি SV মুছলে optimal সমাধান বদলে boundary সরে যেতে পারে। (পূর্ণ যুক্তি — KKT complementary slackness — সমাধান ১১।)

(গ) canonical। RBF($C{=}10$)-এ $210$টি training-বিন্দুর মধ্যে মাত্র $45$টি support vector — boundary মোট data-র এক-পঞ্চমাংশেরও কম বিন্দু-নির্ভর। এটাই SVM-এর sparsity: সিদ্ধান্ত-সীমা অল্প কয়েকটি গুরুত্বপূর্ণ বিন্দু দিয়েই সম্পূর্ণরূপে নির্ধারিত।

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

(ক) দুই loss-এর আকৃতি (margin $m=y_i f(x_i)$-এর ফাংশন হিসেবে): - 0–1 loss: একটি ধাপ — $m\le0$ (ভুল পাশে) হলে মান $1$, $m>0$ (সঠিক পাশে) হলে $0$। boundary-তে ($m=0$) লাফ। - hinge loss $\max(0,1-m)$: $m\ge1$ হলে শূন্য (margin-এর নিরাপদ বাইরে); $m<1$ হলে রৈখিকভাবে $1-m$ বাড়ে (slope $-1$), $m=0$-তে মান $1$, $m<0$-তে আরও বেশি। অর্থাৎ hinge হলো 0–1 loss-এর একটি উপরের উত্তল আবরণ।

(খ) কেন hinge, সরাসরি 0–1 নয়। 0–1 loss অবিচ্ছিন্ন নয়, non-convex, এবং gradient প্রায় সর্বত্র শূন্য (ধাপ-ফাংশন) — তাই সরাসরি minimize করা NP-কঠিন, gradient-ভিত্তিক optimization অচল। hinge হলো এর convex surrogate (উপরের সীমা): উত্তল ও piecewise-linear বলে দক্ষভাবে minimize করা যায়, এবং $m\ge1$ না হওয়া পর্যন্ত শাস্তি দিয়ে সরাসরি margin-কে পুরস্কৃত করে (শুধু সঠিক-শ্রেণিবিন্যাস নয়, নিরাপদ margin-সহ সঠিকতা)।

(গ) সঠিক পাশে থেকেও শাস্তি। $0<m<1$ মানে বিন্দু সঠিক পাশে কিন্তু margin-এর ভিতরে — তখনও hinge $=1-m>0$ শাস্তি দেয়। ঠিক এই বিন্দুরাই (margin-এর উপর বা ভিতরে, এবং ভুল-পাশের বিন্দুরা) support vector — যাদের $\alpha_i>0$। সুতরাং "অশূন্য hinge loss" আর "support vector হওয়া" হাত ধরাধরি করে চলে।

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

(ক) kernel trick-এর সারকথা। SVM-এর dual সমস্যায় (এবং decision function-এ) training-বিন্দুরা কেবল inner product $x_i^\top x_j$ আকারে ঢোকে — কোথাও আলাদা করে $x_i$ লাগে না। তাই যদি আমরা প্রতিটি inner product $x_i^\top x_j$-কে একটি ফাংশন $K(x_i,x_j)=\phi(x_i)^\top\phi(x_j)$ দিয়ে প্রতিস্থাপন করি, গণনা অবিকল অপরিবর্তিত থাকে — অথচ গোপনে আমরা $\phi$-দ্বারা সংজ্ঞায়িত এক উচ্চমাত্রিক feature-space-এ linear boundary বসাচ্ছি, $\phi$ কখনো স্পষ্টভাবে গণনা না করেই। শুধু $K$ জানাই যথেষ্ট।

(খ) RBF-এর অন্তর্নিহিত মাত্রা। RBF kernel $K(x,x')=\exp(-\gamma\lVert x-x'\rVert^2)$-এর সংশ্লিষ্ট feature-space অসীম-মাত্রিক — exponential-এর Taylor-বিস্তারে সব ক্রমের বহুপদ-পদ থাকে, তাই $\phi(x)$ অসীম উপাংশের। তবু $K$ মূল-space-এ একটি সরল scalar সূত্র (শুধু একটি দূরত্ব ও একটি exponential), তাই $\phi$ কখনো না বানিয়েই $K$ গণনাযোগ্য — এটিই kernel trick-এর মূল শক্তি: অসীম-মাত্রিক ক্ষমতা, সসীম গণনায়।

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

(ক) Mercer-শর্ত। $K(x,x')$ একটি valid kernel হতে হলে দুটো শর্ত: (i) symmetric, $K(x,x')=K(x',x)$; এবং (ii) যেকোনো সসীম বিন্দু-সেট $\{x_1,\dots,x_n\}$-এর জন্য gram matrix $K_{ij}=K(x_i,x_j)$ অবশ্যই positive semi-definite (PSD) — অর্থাৎ যেকোনো বাস্তব ভেক্টর $c$-এর জন্য $c^\top K c\ge0$। এটিই Mercer-শর্ত।

(খ) কেন অপরিহার্য। PSD হওয়া নিশ্চিত করে যে $K(x,x')=\phi(x)^\top\phi(x')$ রূপে কোনো feature map $\phi$ আদৌ বিদ্যমান (Mercer-উপপাদ্য)। যদি $K$ PSD না হয়, কোনো $\phi$-inner-product রূপ নেই — তখন SVM-এর dual আর উত্তল (convex) quadratic program থাকে না, optimization-এর সমাধান অর্থ হারায় (নেতিবাচক eigenvalue ⇒ unbounded/অসংজ্ঞায়িত)। তাই valid kernel না হলে গোটা kernel-যুক্তি ভেঙে পড়ে।

(গ) যোগ/গুণফলও valid। valid kernel-এর gram matrix PSD; এবং রৈখিক বীজগণিতের ফল — দুটো PSD matrix-এর যোগফল PSD, এবং element-wise (Hadamard/Schur) গুণফলও PSD থাকে। তাই দুই valid kernel-এর যোগফল ও গুণফলও valid kernel — এভাবে সরল kernel থেকে জটিল kernel গড়া যায়।

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

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

দেওয়া: $w=(0.6,\,0.8)$, $b=-1$।

(ক) $\lVert w\rVert$। $$ \lVert w\rVert=\sqrt{0.6^2+0.8^2}=\sqrt{0.36+0.64}=\sqrt{1}=\mathbf{1}. $$

(খ) margin। geometric margin (পূর্ণ রাস্তার প্রস্থ): $$ \frac{2}{\lVert w\rVert}=\frac{2}{1}=\mathbf{2}. $$

(গ) scale দ্বিগুণ করলে। $w\to(1.2,1.6)$, $b\to-2$ নিলে hyperplane $\{x:1.2x_1+1.6x_2-2=0\}$ আর $\{x:0.6x_1+0.8x_2-1=0\}$ অভিন্ন সেট (সমীকরণ scale-invariant — উভয় পক্ষকে $2$ দিয়ে ভাগ করলেই মূলটা ফিরে আসে)। কিন্তু এখন $\lVert w\rVert=\sqrt{1.2^2+1.6^2}=\sqrt{1.44+2.56}=\sqrt{4}=2$, তাই সূত্র "margin"$=2/2=1$ দেখায় — অর্ধেক! অর্থাৎ margin-এর সংখ্যাগত মান $w$-এর scale-এর উপর নির্ভর করে, যদিও boundary একই। এই দ্ব্যর্থতা দূর করতেই SVM একটি canonical scale স্থির করে: নিকটতম বিন্দুতে $y_i(w^\top x_i+b)=1$ ধরা হয় (অর্থাৎ $\min_i y_i f(x_i)=1$), যাতে margin দ্ব্যর্থহীনভাবে $2/\lVert w\rVert$ হয় এবং "margin সর্বোচ্চ করা" একটি সুসংজ্ঞায়িত সমস্যা থাকে।

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

দেওয়া: $x=(1,2)$, $x'=(2,0)$, $K(x,x')=\exp(-\gamma\lVert x-x'\rVert^2)$।

(ক) squared দূরত্ব। $$ \lVert x-x'\rVert^2=(1-2)^2+(2-0)^2=(-1)^2+2^2=1+4=\mathbf{5}. $$

(খ) $\gamma=0.2$: $$ K(x,x')=\exp(-0.2\times5)=\exp(-1)\approx\mathbf{0.368}. $$

(গ) $\gamma=5$: $$ K(x,x')=\exp(-5\times5)=\exp(-25)\approx1.4\times10^{-11}\approx\mathbf{0}. $$ বড় $\gamma$-তে একই দূরত্বের ($\lVert x-x'\rVert^2=5$) দুই বিন্দুর "মিল" প্রায় শূন্যে নেমে যায় — অর্থাৎ kernel-এর "প্রভাব-ব্যাসার্ধ" সংকীর্ণ, প্রতিটি training-বিন্দু কেবল তার অতি-নিকটবর্তী এলাকাকেই প্রভাবিত করে (সংকীর্ণ "টিলা")। এই স্থানীয়তাই কেন বড় $\gamma$ = বেশি capacity = বেশি wiggly boundary (over-fit-প্রবণ): boundary প্রতিটি বিন্দুকে আলাদাভাবে আঁকড়ে ধরতে পারে।

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

$C$	accuracy	#SV
0.1	0.833	121
1	0.900	63
10	0.944	45
100	0.933	37

(ক) $C$ বাড়লে #SV কমে। বড় $C$ মানে slack-এর (margin-লঙ্ঘনের) শাস্তি বেশি, তাই optimizer যত কম লঙ্ঘন সম্ভব ততই চায় ⇒ margin সরু হয় ⇒ margin-এর উপর/ভিতরে কম বিন্দু পড়ে ⇒ #SV কমে ($121\to63\to45\to37$)। ছোট $C$-তে উল্টো — চওড়া margin, বেশি বিন্দু margin-এর ভিতরে, তাই বেশি SV।

(খ) সর্বোচ্চ ও পতন। সর্বোচ্চ test accuracy $0.944$ at $C=10$। $C=100$-এ accuracy সামান্য পড়ে ($0.944\to0.933$): অতি-কঠোর margin (প্রায় hard-margin) training-data-র noise-কেও আঁকড়ে ধরে — এটি over-fit-এর লক্ষণ (training-এ আরও ভালো, কিন্তু test-এ সামান্য খারাপ)।

(গ) দুই চরম। - $C\to0$: slack প্রায় বিনামূল্যে ⇒ margin অতি-চওড়া, বহু লঙ্ঘন সহ্য ⇒ boundary খুব সরল, high bias / low variance (under-fit)। - $C\to\infty$: কোনো লঙ্ঘন সহ্য নয় ⇒ hard-margin SVM-এ পরিণত, margin অতি-সরু ⇒ low bias / high variance (over-fit, separable না হলে অসম্ভবও হতে পারে)।

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

$\gamma$	accuracy	#SV
0.1	0.800	—
5	0.956	—
20	0.956	132

(ক) ছোট $\gamma$। $\gamma=0.1$ মানে প্রশস্ত (wide) RBF kernel — প্রতিটি বিন্দুর প্রভাব দূর পর্যন্ত ছড়ায়, তাই decision function প্রায় ধ্রুবক-ঢালু, boundary প্রায় মসৃণ/linear হয়ে পড়ে। make_moons-এর বাঁকানো আকৃতি এই প্রায়-সরল boundary ধরতে পারে না ⇒ under-fit, accuracy মাত্র $0.800$ (linear SVM-এর $0.811$-এর কাছাকাছি, যা প্রত্যাশিত)।

(খ) $\gamma$ বড় করার সংকেত। $\gamma=5$-এ accuracy লাফিয়ে $0.956$ — kernel এখন যথেষ্ট সংকীর্ণ যে moons-এর বাঁক ধরতে পারে। কিন্তু $\gamma=20$-তে accuracy আর বাড়ে না ($0.956$), অথচ #SV বিপুল বেড়ে $132$ ($210$ training-এর অর্ধেকের বেশি!)। এত বেশি SV মানে boundary কার্যত প্রতিটি বিন্দুকে আলাদাভাবে ঘিরছে — high variance, over-fit-এর আগাম সংকেত: এই dataset-এ test-accuracy এখনো না পড়লেও, আরও noisy/বড় test-set-এ সাধারণীকরণ দুর্বল হতো।

(গ) $\gamma$ বনাম $C$। $\gamma$ RBF-kernel-এর প্রস্থ/স্থানীয়তা নিয়ন্ত্রণ করে — boundary কতটা wiggly হতে পারে (feature-space-এর কার্যকর-আকৃতি)। $C$ margin-লঙ্ঘনের শাস্তি নিয়ন্ত্রণ করে — কত বিন্দু margin-এর ভুল পাশে সহ্য করা হবে। দুটোই capacity বাড়ায় কিন্তু ভিন্ন প্রক্রিয়ায়, তাই এদের একসঙ্গে (grid/cross-validation-এ) tune করতে হয়।

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

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

canonical scale-এ ধরা হয় দুই margin-প্রান্ত-সমতল: $w^\top x+b=+1$ (এক শ্রেণির নিকটতম বিন্দু) ও $w^\top x+b=-1$ (অন্য শ্রেণির)।

(ক) প্রান্ত-সমতল-দূরত্ব। একটি বিন্দু $x_0$ থেকে hyperplane $w^\top x+b=0$-এর লম্ব-দূরত্ব $\dfrac{\lvert w^\top x_0+b\rvert}{\lVert w\rVert}$। আরও সরাসরি, দুটো সমান্তরাল সমতল $w^\top x+b=c$ ও $w^\top x+b=c'$-এর মধ্যবর্তী লম্ব-দূরত্ব $$ \frac{\lvert c-c'\rvert}{\lVert w\rVert}. $$ এখানে $c=+1$, $c'=-1$, তাই পূর্ণ margin (দুই প্রান্ত-সমতলের মধ্যে দূরত্ব) $$ \frac{\lvert 1-(-1)\rvert}{\lVert w\rVert}=\frac{2}{\lVert w\rVert}. \qquad\blacksquare $$ (কেন্দ্রীয় hyperplane $w^\top x+b=0$ ঠিক মাঝখানে, তাই প্রতিটি শ্রেণির margin $1/\lVert w\rVert$, মোট $2/\lVert w\rVert$।)

(খ) উদ্দেশ্যে রূপান্তর। margin $=2/\lVert w\rVert$ সর্বোচ্চ করা $\Leftrightarrow$ $\lVert w\rVert$ সর্বনিম্ন করা $\Leftrightarrow$ $\tfrac12\lVert w\rVert^2$ সর্বনিম্ন করা (বর্গ ও $\tfrac12$ একঘেয়ে-বর্ধমান রূপান্তর, $\arg\min$ অপরিবর্তিত; quadratic রাখলে gradient মসৃণ)। সব training-বিন্দু সঠিক পাশে ও margin-এর বাইরে রাখার শর্ত $y_i(w^\top x_i+b)\ge1$। তাই hard-margin SVM-এর primal: $$ \min_{w,b}\ \tfrac12\lVert w\rVert^2 \quad\text{s.t.}\quad y_i(w^\top x_i+b)\ge1\ \ \forall i, $$ একটি উত্তল quadratic program। $\blacksquare$

সমাধান ১১ (★★★) [P-dual-sv]¶

hard-margin SVM-এর Lagrangian: $$ \mathcal L(w,b,\alpha)=\tfrac12\lVert w\rVert^2-\sum_i\alpha_i\big[y_i(w^\top x_i+b)-1\big],\qquad \alpha_i\ge0, $$ এবং KKT-শর্তের অংশ — stationarity $\partial\mathcal L/\partial w=0\Rightarrow w=\sum_i\alpha_i y_i x_i$, এবং complementary slackness: $$ \alpha_i\big[\,y_i(w^\top x_i+b)-1\,\big]=0\quad\forall i . $$

(ক) margin-এর বাইরে ⇒ $\alpha_i=0$। যদি বিন্দু $i$ margin-এর কঠোরভাবে বাইরে থাকে, তবে $y_i(w^\top x_i+b)>1$, অর্থাৎ বর্গাকার-বন্ধনী $y_i(w^\top x_i+b)-1>0$ — অশূন্য। complementary slackness-এ গুণফল শূন্য হতে হলে অন্য গুণনীয়কটি অবশ্যই শূন্য: $\alpha_i=0$। অর্থাৎ margin-এর নিরাপদ বাইরের প্রতিটি বিন্দুর dual coefficient শূন্য।

(খ) $\alpha_i>0$ ⇒ margin-এ। বিপরীতে যদি $\alpha_i>0$, তবে গুণফল শূন্য রাখতে বর্গাকার-বন্ধনী $=0$ হতেই হবে: $y_i(w^\top x_i+b)=1$ — অর্থাৎ বিন্দুটি ঠিক margin-সীমার উপর। এমন বিন্দুই support vector।

(গ) $w$ ও $f$ কেবল SV-নির্ভর। stationarity থেকে $w=\sum_i\alpha_i y_i x_i$; কিন্তু (ক)-অনুসারে non-SV-দের $\alpha_i=0$, তাই তারা এই যোগফলে বাদ পড়ে — কেবল support vector ($\alpha_i>0$) অবদান রাখে। ফলে $$ w=\sum_{i:\,\alpha_i>0}\alpha_i y_i x_i,\qquad f(x)=w^\top x+b=\sum_{i:\,\alpha_i>0}\alpha_i y_i\,x_i^\top x+b , $$ সম্পূর্ণরূপে support vector দিয়ে নির্ধারিত। এটিই SVM-এর sparsity, এবং সমাধান ২-এর "non-SV মুছলে boundary অপরিবর্তিত" দাবির আনুষ্ঠানিক ভিত্তি। (kernel-যুক্ত রূপে $x_i^\top x$ স্থলে $K(x_i,x)$।) $\blacksquare$

সমাধান ১২ (★★) [P-kernel-valid]¶

ধরুন $K(x,x')=\phi(x)^\top\phi(x')$ কোনো feature map $\phi$-এর জন্য।

(ক) gram matrix PSD। যেকোনো বিন্দু-সেট $x_1,\dots,x_n$ ও বাস্তব সহগ $c_1,\dots,c_n$-এর জন্য: $$ \sum_{i=1}^n\sum_{j=1}^n c_i c_j K(x_i,x_j) =\sum_{i,j} c_i c_j\,\phi(x_i)^\top\phi(x_j) =\Big(\sum_i c_i\phi(x_i)\Big)^{!\top}\Big(\sum_j c_j\phi(x_j)\Big) =\Big\lVert\sum_i c_i\phi(x_i)\Big\rVert^2\ge0 . $$ এটি একটি ভেক্টরের norm-বর্গ, তাই সর্বদা অঋণাত্মক। সুতরাং gram matrix $K_{ij}=K(x_i,x_j)$ positive semi-definite। (symmetry স্পষ্ট: $\phi(x_i)^\top\phi(x_j)=\phi(x_j)^\top\phi(x_i)$।) $\blacksquare$

(খ) Mercer (যথেষ্টতা)। উল্টো দিকও সত্য: Mercer-উপপাদ্য বলে, $K$ symmetric ও PSD হলে একটি (সম্ভবত অসীম-মাত্রিক) feature map $\phi$ সর্বদা বিদ্যমান যাতে $K(x,x')=\phi(x)^\top\phi(x')$। তাই "symmetric + gram-PSD" শুধু প্রয়োজনীয় নয়, যথেষ্ট শর্তও — valid kernel হওয়ার সম্পূর্ণ চরিত্রায়ন। (এ-কারণেই RBF/polynomial-এর জন্য $\phi$ স্পষ্ট না লিখেও আমরা নিশ্চিত যে তারা বৈধ feature-space-এ inner product।)

ঘ · কোডিং (coding)¶

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

import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

# ---- চলমান dataset: make_moons, n=300, noise=0.25, 70/30 split ----
SEED = 20260619
X, y = make_moons(n_samples=300, noise=0.25, random_state=SEED)
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.30, random_state=SEED)   # 210 train, 90 test

def report(name, clf):
    clf.fit(Xtr, ytr)
    acc = clf.score(Xte, yte)
    nsv = clf.support_.size
    print(f"{name:24s}: acc={acc:.3f}   #SV={nsv}")
    return clf

report("Linear SVM",        SVC(kernel="linear", C=1))          # ~0.811, 74 SV
report("RBF SVM (C=1)",     SVC(kernel="rbf",    C=1))           # ~0.900, 63 SV
report("RBF SVM (C=10)",    SVC(kernel="rbf",    C=10))          # ~0.944, 45 SV (সেরা)
report("Polynomial (deg3)", SVC(kernel="poly",   degree=3, C=1)) # ~0.833

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

Linear SVM              : acc=0.811   #SV=74
RBF SVM (C=1)           : acc=0.900   #SV=63
RBF SVM (C=10)          : acc=0.944   #SV=45     <- সেরা
Polynomial (deg3)       : acc=0.833

ব্যাখ্যা। make_moons দুই অর্ধচন্দ্রাকৃতি শ্রেণি তৈরি করে যারা একে অপরের সঙ্গে জড়িয়ে থাকে — linearly inseparable। তাই linear SVM সবচেয়ে দুর্বল ($0.811$): একটিমাত্র সরলরেখা দিয়ে বাঁকানো সীমানা ধরা অসম্ভব, অনেক বিন্দু ভুল পাশে পড়ে (এবং margin-এর ভিতরে অনেক বিন্দু ⇒ ৭৪টি SV)। RBF SVM অসীম-মাত্রিক feature-space-এ গিয়ে বাঁকানো boundary আঁকতে পারে, তাই অনেক ভালো; $C$ বাড়িয়ে $10$ করলে margin সরু হয়ে boundary moons-এর আকৃতি আরও ভালো অনুসরণ করে — RBF($C{=}10$) সেরা ($0.944$, ৪৫ SV)। polynomial (deg 3) কিছুটা nonlinearity আনে ($0.833$) কিন্তু moons-এর আকৃতির জন্য RBF-এর মতো উপযুক্ত নয়। (সুনির্দিষ্ট মান sklearn/NumPy সংস্করণ ও default-gamma বাস্তবায়নে সামান্য বদলাতে পারে; অনুপাত — linear সর্বনিম্ন, RBF$C{=}10$ সর্বোচ্চ, poly মাঝে — অপরিবর্তিত থাকবে।)

সমাধান ১৪ (★★★) [E-tune-boundary] — $C$–$\gamma$ tune, boundary ও support vector¶

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

SEED = 20260619
X, y = make_moons(n_samples=300, noise=0.25, random_state=SEED)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.30, random_state=SEED)

# ---- (ক) C-sweep (RBF) ----
print("C-sweep (RBF):")
for C in [0.1, 1, 10, 100]:
    clf = SVC(kernel="rbf", C=C).fit(Xtr, ytr)
    print(f"  C={C:5}: acc={clf.score(Xte,yte):.3f}  #SV={clf.support_.size}")
# প্রত্যাশিত: 0.1->0.833/121, 1->0.900/63, 10->0.944/45, 100->0.933/37

# ---- (খ) gamma-sweep (RBF, C স্থির) ----
print("gamma-sweep (RBF, C=1):")
for g in [0.1, 5, 20]:
    clf = SVC(kernel="rbf", C=1, gamma=g).fit(Xtr, ytr)
    print(f"  gamma={g:<4}: acc={clf.score(Xte,yte):.3f}  #SV={clf.support_.size}")
# প্রত্যাশিত: 0.1->0.800, 5->0.956, 20->0.956/132

# ---- (গ) সেরা মডেলের boundary + support vectors ----
best = SVC(kernel="rbf", C=10).fit(Xtr, ytr)          # canonical সেরা ~0.944
x_min, x_max = X[:,0].min()-0.5, X[:,0].max()+0.5
y_min, y_max = X[:,1].min()-0.5, X[:,1].max()+0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 400),
                     np.linspace(y_min, y_max, 400))
Z = best.decision_function(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

plt.figure(figsize=(7, 6))
plt.contourf(xx, yy, Z, levels=[-1e9, 0, 1e9], alpha=0.15, colors=["#3b6", "#b63"])
plt.contour(xx, yy, Z, levels=[-1, 0, 1],            # margin-সীমা ও boundary
            linestyles=["--", "-", "--"], colors="k")
plt.scatter(Xtr[:,0], Xtr[:,1], c=ytr, s=18, cmap="coolwarm", edgecolor="k", linewidth=0.3)
# support vector চিহ্নিত (বৃত্তায়িত)
sv = best.support_vectors_
plt.scatter(sv[:,0], sv[:,1], s=130, facecolors="none", edgecolors="lime", linewidth=1.4,
            label=f"support vectors (#SV={best.support_.size})")
plt.title(f"RBF SVM (C=10)  test acc={best.score(Xte,yte):.3f}")
plt.legend(loc="lower right"); plt.xticks([]); plt.yticks([])
plt.tight_layout(); plt.savefig("06-04-svm-boundary.png", dpi=130)

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

C-sweep (RBF):
  C=  0.1: acc=0.833  #SV=121
  C=    1: acc=0.900  #SV=63
  C=   10: acc=0.944  #SV=45
  C=  100: acc=0.933  #SV=37
gamma-sweep (RBF, C=1):
  gamma=0.1 : acc=0.800
  gamma=5   : acc=0.956
  gamma=20  : acc=0.956  #SV=132

যা দেখা যায়। - $C$-sweep: $C$ বাড়ার সঙ্গে #SV একঘেয়ে কমে ($121\to63\to45\to37$) — margin সরু হওয়ার সরাসরি ফল; accuracy $0.1\to10$-এ বাড়ে ($0.833\to0.944$), কিন্তু $C=100$-এ সামান্য পড়ে ($0.933$ — over-fit)। - $\gamma$-sweep: ছোট $\gamma$ ($0.1$) boundary প্রায়-linear ⇒ under-fit ($0.800$); $\gamma=5$-এ boundary moons ধরে ($0.956$); $\gamma=20$-এ accuracy না বেড়ে #SV বিস্ফোরিত ($132$) — over-fit-এর সংকেত। - boundary-চিত্র: কঠিন রেখা ($Z=0$) decision boundary, ছেদরেখা ($Z=\pm1$) দুই margin-সীমা; support vector-গুলো (সবুজ বৃত্ত) ঠিক margin-সীমার উপর বা ভিতরে বসে — যা প্রশ্ন ২ ও ১১-এর তত্ত্ব চাক্ষুষভাবে নিশ্চিত করে (boundary কেবল এই অল্প কয়েকটি বিন্দু-নির্ভর)।

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

classifier	test accuracy	#SV
Linear SVM	0.811	74
RBF SVM ($C=1$)	0.900	63
RBF SVM ($C=10$)	0.944	45
Polynomial (deg 3)	0.833	—

$C$ (RBF)	0.1	1	10	100
accuracy	0.833	0.900	0.944	0.933
#SV	121	63	45	37

$\gamma$ (RBF, $C$ স্থির)	0.1	5	20
accuracy	0.800	0.956	0.956
#SV	—	—	132

কুইক-গণনা	মান
margin ($w=(0.6,0.8)$)	$2/\lVert w\rVert=2$
RBF $K$, $x=(1,2),x'=(2,0),\gamma=0.2$	$\exp(-1)\approx0.368$
hard-margin demo (3 SV)	margin $\approx2.678$

কুইক-গণনা	মান
margin (\(w=(0.6,0.8)\))	\(2/\lVert w\rVert=2\)
RBF \(K\), \(x=(1,2),x'=(2,0),\gamma=0.2\)	\(\exp(-1)\approx0.368\)
hard-margin demo (3 SV)	margin \(\approx2.678\)

classifier	test accuracy	#SV
Linear SVM	0.811	74
RBF SVM (\(C=1\))	0.900	63
RBF SVM (\(C=10\))	0.944	45
Polynomial (deg 3)	0.833	—

সমাধান — অধ্যায় ৬.৪ · Classification II: SVM & Kernel Methods¶

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

সমাধান ১ (★)¶

সমাধান ২ (★)¶

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

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

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

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

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

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

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

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

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

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

সমাধান ১১ (★★★) [P-dual-sv]¶

সমাধান ১২ (★★) [P-kernel-valid]¶

ঘ · কোডিং (coding)¶

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

সমাধান ১৪ (★★★) [E-tune-boundary] — \(C\)–\(\gamma\) tune, boundary ও support vector¶

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