Kernel trick — RBF, polynomial আর Mercer-এর অন্তর্দৃষ্টি

পর্ব ২৭ (Support Vector Machine — margin, support vector আর hard margin) আর পর্ব ২৮ (Soft margin — hinge loss, C আর dual problem)-এ SVM একটি সরল রেখা বা সমতল টানে, যার দুই পাশে সবচেয়ে চওড়া ফাঁক। কিন্তু বাস্তবের অনেক ডেটা কোনো সরলরেখায় ভাগ হয় না। এই পর্বের প্রশ্ন: সরল সমতলের সব সুবিধা (convex সমস্যা, একটিই সেরা উত্তর, margin) রেখে কীভাবে বাঁকা সীমানা পাবেন? উত্তরের নাম kernel trick. এর গণিত আপনি আগেই আংশিক দেখেছেন: পর্ব ১০-এ Gram matrix PSD, পর্ব ১৬-এ Lagrange আর dual, আর পর্ব ২৩-এ RBF basis function. চালানো যায় এমন চারটি ব্লক পাতাতেই চলে (ব্রাউজারের Python, scikit-learn 1.8.0); প্রথমবার scikit-learn নামতে প্রায় দশ সেকেন্ড লাগে।

১ · সরলরেখা যেখানে হার মানে — feature map দিয়ে উঁচু মাত্রায় তোলা

গণিতের ভাষায়, একটি feature map φ প্রতিটি ইনপুট x-কে নতুন একটি vector φ(x)-এ নেয়, সাধারণত বেশি মাত্রায়। তারপর সেই নতুন জগতে সাধারণ linear model: f(x) = w·φ(x) + b. w-এর দিক থেকে model linear, তাই শেখানোর সব সুবিধা থাকে; কিন্তু x-এর দিক থেকে f বাঁকা। পর্ব ২৩-এর basis expansion ঠিক এই কাজ করেছিল; পার্থক্য আসবে অংশ ২-এ, যখন φ আর বানাতেই হবে না।

সবচেয়ে ছোট উদাহরণ এক মাত্রায়। নিচের ছবিতে সংখ্যারেখার মাঝখানে নীল, দুই প্রান্তে লাল। একটি বিন্দু (threshold) দিয়ে ভাগ অসম্ভব। কিন্তু φ(x) = (x, x²) নিলে প্রতিটি বিন্দু একটি parabola-র ওপর ওঠে, আর একটি অনুভূমিক রেখা x² = ১.৮ দুই দল আলাদা করে। মূল রেখায় তার মানে “|x| < ১.৩৪ হলে নীল”, অর্থাৎ দুটি threshold.

দুই মাত্রার বিখ্যাত উদাহরণ XOR: (১, ১) আর (−১, −১) এক দল, (১, −১) আর (−১, ১) আরেক দল। কোনো সরলরেখা কাজ করে না, কিন্তু একটি নতুন feature x₁x₂ যোগ করলে প্রথম দলে x₁x₂ = ১, দ্বিতীয় দলে −১: একটি threshold-ই যথেষ্ট। Thomas Cover ১৯৬৫ সালে (IEEE Transactions on Electronic Computers) একটি গণনা দেন যার সারকথা: অনেক বেশি মাত্রায় এলোমেলো বিন্যাসের বিন্দুও সরলরেখায় ভাগ হওয়ার সম্ভাবনা বাড়ে। এর বিপদও আছে, যা অংশ ৬-এ দেখবেন: বেশি মাত্রায় সবকিছু ভাগ করা যায়, noise-ও।

বাজারঘরের সন্দেহজনক অর্ডার

এই পর্বের ডেটা কাল্পনিক, seed দিয়ে বানানো। বাজারঘরের প্রতিটি অর্ডারের দুটি সংখ্যা: x₁ = দামের বিচ্যুতি (গ্রাহকের সাধারণ অর্ডারের তুলনায়, standardize করা), x₂ = সময়ের বিচ্যুতি (তিনি সাধারণত যে সময়ে কেনেন তার তুলনায়)। সাধারণ অর্ডার (০) কেন্দ্রের কাছে জড়ো; প্রতারণার অর্ডার (১) কেন্দ্র থেকে দূরে, যেকোনো দিকে: অস্বাভাবিক বেশি বা কম দাম, রাত তিনটায় বা ভোরে। ফলে প্রতারণার অর্ডার একটি বলয় বানায়, যা কোনো সরলরেখা আলাদা করতে পারে না। ব্লক ১, ৩ আর ৪ এই module থেকে ডেটা নেয়।

# bazar_fraud.py — বাজারঘরের কাল্পনিক সন্দেহজনক অর্ডার (seed দিয়ে বানানো)
import numpy as np

def make_fraud(n=300, seed=29, spread=0.35):
    rng = np.random.default_rng(seed)
    y = (rng.random(n) < 0.4).astype(int)              # 1 = প্রতারণার অর্ডার
    r = np.where(y == 1, rng.normal(2.2, spread, n),   # প্রতারণা: স্বাভাবিক থেকে দূরে, যেকোনো দিকে
                 np.abs(rng.normal(0, 0.8, n)))        # সাধারণ: কেন্দ্রের কাছে
    angle = rng.uniform(0, 2 * np.pi, n)
    X = np.column_stack([r * np.cos(angle),            # x1: দামের বিচ্যুতি (z-score)
                         r * np.sin(angle)])           # x2: সময়ের বিচ্যুতি (z-score)
    return X, y

প্রথম ব্লক তিনটি model তুলনা করে: মূল দুই মাত্রায় linear SVM; φ(x) = (x₁, x₂, x₁² + x₂²) বানিয়ে তিন মাত্রায় linear SVM; আর φ না বানিয়ে SVC(kernel="rbf"). তারপর বাঁ দিকে মূল ডেটা, ডান দিকে “তোলা” ডেটা আঁকে।

import numpy as np
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from bazar_fraud import make_fraud

X, y = make_fraud()
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
lift = lambda A: np.column_stack([A, (A ** 2).sum(axis=1)])   # φ(x) = (x1, x2, x1²+x2²)

flat = SVC(kernel="linear").fit(Xtr, ytr)                     # মূল ২-মাত্রায় সরলরেখা
lifted = SVC(kernel="linear").fit(lift(Xtr), ytr)             # ৩-মাত্রায় সমতল
rbf = SVC(kernel="rbf").fit(Xtr, ytr)                         # φ না বানিয়ে, kernel দিয়ে
print(f"orders: train {len(ytr)}, test {len(yte)}, fraud rate {y.mean():.2f}")
print(f"linear on (x1, x2)        test acc {flat.score(Xte, yte):.3f}")
print(f"linear on (x1, x2, r^2)   test acc {lifted.score(lift(Xte), yte):.3f}")
print(f"SVC rbf on (x1, x2)       test acc {rbf.score(Xte, yte):.3f}")
w, b = lifted.coef_[0], lifted.intercept_[0]
print(f"plane: {w[0]:+.3f} x1 {w[1]:+.3f} x2 {w[2]:+.3f} r^2 {b:+.3f} = 0")
print(f"boundary in x-space: circle r = {np.sqrt(-b / w[2]):.3f} (x1, x2 weights ~ 0)")

fig, ax = plt.subplots(1, 2, figsize=(9, 4))
for k, c in [(0, "tab:blue"), (1, "tab:red")]:
    m = y == k
    ax[0].scatter(X[m, 0], X[m, 1], s=10, c=c, label=["normal", "fraud"][k])
    ax[1].scatter(X[m, 0], (X[m] ** 2).sum(axis=1), s=10, c=c)
ax[0].add_patch(plt.Circle((0, 0), np.sqrt(-b / w[2]), fill=False, ls="--"))
ax[0].set(title="original space: no line works", xlabel="x1 (price deviation)",
          ylabel="x2 (time deviation)", aspect="equal")
ax[1].axhline(-b / w[2], color="k", ls="--", label="separating plane")
ax[1].set(title="lifted: r^2 = x1^2 + x2^2", xlabel="x1", ylabel="r^2")
ax[0].legend(fontsize=8); ax[1].legend(fontsize=8)

orders: train 210, test 90, fraud rate 0.43
linear on (x1, x2)        test acc 0.578
linear on (x1, x2, r^2)   test acc 0.989
SVC rbf on (x1, x2)       test acc 0.989
plane: -0.103 x1 -0.035 x2 +1.345 r^2 -3.010 = 0
boundary in x-space: circle r = 1.496 (x1, x2 weights ~ 0)

২ · Dual শুধু dot product চায় — kernel trick-এর মূল চাল

ব্লক ১-এ φ হাতে বানানো সহজ ছিল, কারণ আমরা জানতাম দূরত্বই আসল কথা। সাধারণভাবে জানা থাকে না, তাই অনেক feature একসঙ্গে চাই: সব দ্বিঘাত পদ, সব ত্রিঘাত পদ… মাত্রা দ্রুত বিস্ফোরিত হয়। এখানেই SVM-এর dual problem সাহায্য করে। পর্ব ২৮-এ soft-margin SVM-এর dual পুরো হিসাবসহ দেখেছেন; এখানে শুধু তার আকারটি দরকার (Lagrange আর dual-এর ভিত্তি পর্ব ১৬-এ):

সর্বোচ্চ করুন ∑_i α_i − ½ ∑_i ∑_j α_i α_j y_i y_j (x_i · x_j)
শর্ত: ০ ≤ α_i ≤ C, ∑_i α_i y_i = ০

অনুমান: f(x) = ∑_i α_i y_i (x_i · x) + b

এখানে α_i প্রতিটি train বিন্দুর Lagrange multiplier, y_i তার শ্রেণি (+১ বা −১), C হলো ভুলের শাস্তির মাপ, আর b সমতলের সরণ। যেসব বিন্দুর α_i > ০, তারাই support vector; বাকিরা অনুমানে কোনো ভূমিকা রাখে না।

লক্ষ করুন: শেখা আর অনুমান, দুই জায়গাতেই ডেটা ঢোকে শুধু জোড়ায় জোড়ায় dot product হিসেবে, কোথাও আলাদা করে x_i-এর কোনো স্থানাঙ্ক লাগে না। তাই φ-এর জগতে কাজ করতে চাইলে x_i·x_j-এর জায়গায় φ(x_i)·φ(x_j) বসালেই হলো। এখন যদি এমন একটি function k পাওয়া যায় যে

k(x, z) = φ(x) · φ(z)

আর k সরাসরি x আর z থেকে সস্তায় হিসাব করা যায়, তবে φ কখনো বানাতে হয় না। এই k-ই kernel, আর বদলটিই kernel trick. শেখার সময় লাগে সব জোড়ার kernel মান, একটি n × n টেবিল K_ij = k(x_i, x_j), যার নাম Gram matrix বা kernel matrix. অনুমানে লাগে নতুন x আর প্রতিটি support vector-এর kernel মান।

একটি সূক্ষ্ম বিষয়: kernel SVM-এ w = ∑α_iy_iφ(x_i) কখনো হাতে আসে না, কারণ φ নেই। তাই linear kernel ছাড়া scikit-learn-এর SVC-তে coef_ পাওয়া যায় না; আছে dual_coef_ (α_iy_i), support_vectors_ আর intercept_. অনুমানের খরচ তাই support vector-এর সংখ্যার সমানুপাতিক।

৩ · Polynomial kernel হাতে খুলে দেখা

সবচেয়ে সহজে যাচাইযোগ্য kernel হলো polynomial kernel: k(x, z) = (x·z + 1)². দাবি: এটি কোনো একটি φ-এর dot product. দুই মাত্রার দুটি vector নিয়ে হাতে খুলে দেখুন:

সাধারণ রূপে scikit-learn লেখে k(x, z) = (γ·x·z + r)^d, যেখানে d = degree, r = coef0, γ = gamma. r > ০ হলে φ-এ শূন্য থেকে d পর্যন্ত সব ঘাতের পদ থাকে; r = ০ হলে শুধু ঠিক d ঘাতের পদ (homogeneous). মনে রাখার বিষয়: SVC(kernel="poly")-এ ডিফল্ট coef0=0 আর degree=3, তাই ডিফল্ট poly kernel-এ রৈখিক আর দ্বিঘাত পদ নেই। নিচের ব্লক দুটি কাজ করে: হাতের হিসাবটি সংখ্যায় মেলায় (২০০টি বিন্দুর পুরো Gram matrix-সহ), তারপর ২০০টি অর্ডার আর ২০টি feature-এ স্পষ্ট feature বনাম kernel-এর আকার আর সময় মাপে।

import time
import numpy as np
from sklearn.metrics.pairwise import polynomial_kernel
from sklearn.preprocessing import PolynomialFeatures

def phi(v):                                   # (x·z + 1)²-এর ৬টি স্পষ্ট feature
    a, b = v
    r2 = np.sqrt(2)
    return np.array([1, r2 * a, r2 * b, a * a, b * b, r2 * a * b])

x, z = np.array([1.0, 2.0]), np.array([3.0, 1.0])
print("kernel (x.z + 1)^2 =", (x @ z + 1) ** 2)
print("phi(x) . phi(z)    =", round(phi(x) @ phi(z), 10))
rng = np.random.default_rng(29)
X2 = rng.normal(size=(200, 2))
K = polynomial_kernel(X2, degree=2, gamma=1, coef0=1)
P = np.array([phi(v) for v in X2])
print("200 x 200 Gram, max |K - P P^T| =", f"{np.abs(K - P @ P.T).max():.1e}")

def best_ms(f):                               # ৩ বার চালিয়ে সবচেয়ে কম সময়
    out = []
    for _ in range(3):
        t = time.perf_counter(); f(); out.append(time.perf_counter() - t)
    return 1000 * min(out)

X = rng.normal(size=(200, 20))                # ২০০টি অর্ডার, ২০টি feature
print("\ndegree  features  feature MB  explicit ms  kernel ms")
for p in (2, 3, 4):
    F = PolynomialFeatures(degree=p).fit_transform(X)
    t_exp = best_ms(lambda: PolynomialFeatures(degree=p).fit_transform(X) @ F.T)
    t_ker = best_ms(lambda: polynomial_kernel(X, degree=p, gamma=1, coef0=1))
    print(f"{p:6d}  {F.shape[1]:8d}  {F.nbytes / 1e6:10.1f}  {t_exp:11.1f}  {t_ker:9.1f}")

kernel (x.z + 1)^2 = 36.0
phi(x) . phi(z)    = 36.0
200 x 200 Gram, max |K - P P^T| = 2.8e-14

degree  features  feature MB  explicit ms  kernel ms
     2       231         0.4          8.6        1.2
     3      1771         2.8         62.9        2.6
     4     10626         17.0        401.3        2.5

৪ · RBF kernel আর γ — মিল মানে কাছাকাছি থাকা

সবচেয়ে জনপ্রিয় kernel হলো RBF kernel (Gaussian kernel নামেও পরিচিত):

k(x, z) = exp(−γ ‖x − z‖²),   γ > ০

‖x − z‖² হলো দুই বিন্দুর দূরত্বের বর্গ। একই বিন্দুতে k = ১, দূরে গেলে মান শূন্যের দিকে নামে। তাই RBF আসলে “কতটা কাছে” মাপে, AI-এর ভিত্তি কোর্সের পর্ব ৫৭-এর k-NN-এর মতো দূরত্বের ভাবনা। পার্থক্য: k-NN কাছের কয়েকজনের ভোট নেয়, RBF SVM সব support vector-এর ওজনযুক্ত মিল যোগ করে: f(x) = ∑α_iy_i·exp(−γ‖x_i − x‖²) + b. প্রতিটি support vector-এর চারপাশে একটি ঘণ্টার মতো ঢিবি; পর্ব ২৩-এর radial basis function যেমন, তফাত শুধু এই যে কেন্দ্রগুলো এখানে ডেটার বিন্দু নিজেই, আর কোনগুলো থাকবে তা SVM ঠিক করে।

অসীম মাত্রার feature space — কেন বলা হয়

RBF-এর φ কেমন? ধরুন এক মাত্রায় x আর z. exp(−γ(x − z)²) = exp(−γx²) · exp(−γz²) · exp(২γxz). শেষ অংশটি Taylor series-এ খুললে ∑_n (২γ)ⁿ xⁿ zⁿ / n!, অর্থাৎ সব ঘাতের polynomial পদ, প্রতিটি ওজনসহ। তাই φ(x)-এর অসীমসংখ্যক উপাদান: exp(−γx²)·√((২γ)ⁿ/n!)·xⁿ, n = ০, ১, ২, … . কোনো কম্পিউটার এই φ বানাতে পারে না, কিন্তু kernel-এর মান একটি exp. এজন্যই বলা হয় RBF-এর feature space অসীম মাত্রার। এর একটি পরিণতি (Ingo Steinwart ২০০১ সালে এই ধরনের kernel-কে “universal” বলে প্রমাণ দেন, নির্দিষ্ট শর্তে): যথেষ্ট ডেটা আর ঠিক γ হলে RBF প্রায় যেকোনো মসৃণ সীমানার কাছাকাছি যেতে পারে। একই কারণে সাবধানতা: সে noise-এর চারপাশেও সীমানা আঁকতে পারে।

৫ · Mercer-এর শর্ত — কোন “মিল” সত্যিই kernel

এবার উল্টো প্রশ্ন। যেকোনো “মিল”-এর function লিখে SVC-তে দিলেই কি চলবে? না। k(x, z) = φ(x)·φ(z) হলে Gram matrix K = ΦΦᵀ, যেখানে Φ-এর সারিগুলো φ(x_i). পর্ব ১০-এ দেখেছেন, এমন matrix সবসময় positive semidefinite (PSD): যেকোনো c-এর জন্য cᵀKc = ‖Φᵀc‖² ≥ ০. তিনটি কারণে এই শর্ত অপরিহার্য:

• জ্যামিতি: φ-এর জগতে দূরত্বের বর্গ ‖φ(x) − φ(z)‖² = k(x, x) + k(z, z) − ২k(x, z). PSD না হলে কোনো জোড়ায় এটি ঋণাত্মক হতে পারে, যা অসম্ভব দূরত্ব।
• Optimization: Dual-এর দ্বিঘাত অংশ αᵀ(yyᵀ ∘ K)α (∘ মানে ঘরে ঘরে গুণ)। K PSD হলে সমস্যাটি convex, একটিই সেরা উত্তর (পর্ব ১২)। না হলে solver আটকে যেতে পারে বা যেকোনো একটি উত্তর দেয়।
• Margin: ‖w‖² = αᵀ(yyᵀ ∘ K)α. PSD না হলে “margin”-এর বর্গ ঋণাত্মক হওয়া সম্ভব, তখন পুরো ধারণাটিই ভাঙে।

২ × ২ matrix-এ যাচাই খুব সহজ, তাই পরীক্ষায় প্রায়ই আসে। নিচে একটি বৈধ kernel আর একটি অবৈধ “মিল”:

নতুন kernel বানানোর নিয়ম

প্রতিবার Mercer প্রমাণ না করে, জানা kernel থেকে নতুন kernel বানানো যায়। k₁ আর k₂ বৈধ হলে নিচেরগুলোও বৈধ:

নিচের ব্লক বাজারঘরের ৪০টি অর্ডারে তিনটি পরিচিত kernel, দুটি অবৈধ “মিল” (ঋণাত্মক দূরত্ব আর tanh), আর যোগ, গুণ, গুণিতক ও বিয়োগে বানানো kernel-এর সবচেয়ে ছোট eigenvalue দেখে। প্রতিসম matrix-এর জন্য scipy.linalg.eigh ব্যবহার করা হয়েছে, যা eigenvalue ছোট থেকে বড় ক্রমে দেয়।

import numpy as np
from scipy.linalg import eigh
from sklearn.metrics.pairwise import (euclidean_distances, linear_kernel,
                                      polynomial_kernel, rbf_kernel, sigmoid_kernel)
from bazar_fraud import make_fraud

X, _ = make_fraud(n=40)                       # ৪০টি অর্ডার, ২টি feature

def check(name, K):                           # প্রতিসম? সবচেয়ে ছোট eigenvalue কত?
    lam = eigh(K, eigvals_only=True)          # ছোট থেকে বড় ক্রমে
    sym = np.allclose(K, K.T)
    verdict = "PSD" if lam[0] > -1e-9 * lam[-1] else "NOT PSD"
    print(f"{name:22s} symmetric={sym}  min eig {lam[0]:+.2e}  {verdict}")

K_lin = linear_kernel(X)
K_poly = polynomial_kernel(X, degree=3, gamma=1, coef0=1)
K_rbf = rbf_kernel(X, gamma=0.5)
check("linear  x.z", K_lin)
check("poly    (x.z + 1)^3", K_poly)
check("rbf     gamma=0.5", K_rbf)
print("-- not kernels --")
check("minus distance", -euclidean_distances(X))
check("tanh(2 x.z - 1)", sigmoid_kernel(X, gamma=2, coef0=-1))
print("-- building new kernels --")
check("rbf + poly", K_rbf + K_poly)
check("rbf * linear (entry)", K_rbf * K_lin)
check("3 * rbf", 3 * K_rbf)
check("rbf - poly", K_rbf - K_poly)
print("rank of linear Gram:", np.linalg.matrix_rank(K_lin), "of", len(X))

linear  x.z            symmetric=True  min eig -1.63e-14  PSD
poly    (x.z + 1)^3    symmetric=True  min eig -5.79e-13  PSD
rbf     gamma=0.5      symmetric=True  min eig +6.50e-10  PSD
-- not kernels --
minus distance         symmetric=True  min eig -8.58e+01  NOT PSD
tanh(2 x.z - 1)        symmetric=True  min eig -1.79e+01  NOT PSD
-- building new kernels --
rbf + poly             symmetric=True  min eig +7.41e-10  PSD
rbf * linear (entry)   symmetric=True  min eig +6.31e-10  PSD
3 * rbf                symmetric=True  min eig +1.95e-09  PSD
rbf - poly             symmetric=True  min eig -1.82e+03  NOT PSD
rank of linear Gram: 2 of 40

৬ · বাজারঘরের ডেটায় তিন kernel আর γ–C-এর ছক

এবার একটু কঠিন ডেটা: একই কাল্পনিক বাজারঘর, কিন্তু প্রতারণার বলয় চওড়া (spread=0.7), তাই কিছু প্রতারণা সাধারণ অর্ডারের মধ্যে ঢুকে পড়েছে। নিচের ব্লক পাঁচটি SVC-র decision boundary আঁকে (linear, degree ২-এর poly, আর তিনটি γ-তে RBF), তারপর RBF-এর জন্য γ আর C-এর ৬ × ৬ grid search চালায়, ৫-fold cross-validation-এ, শুধু train ভাগে (AI-এর ভিত্তি কোর্সের পর্ব ৬৬)। C ছোট মানে ভুলের শাস্তি কম, তাই চওড়া margin আর সরল সীমানা; C বড় মানে প্রায় প্রতিটি train বিন্দু ঠিক করার চেষ্টা।

import numpy as np
import matplotlib.pyplot as plt
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.svm import SVC
from bazar_fraud import make_fraud

X, y = make_fraud(n=300, seed=7, spread=0.7)          # এবার দুই দল খানিকটা মেশানো
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
g = np.linspace(-3.5, 3.5, 150)
xx, yy = np.meshgrid(g, g)
grid_pts = np.c_[xx.ravel(), yy.ravel()]
models = {"linear": SVC(kernel="linear"), "poly d=2": SVC(kernel="poly", degree=2, coef0=1),
          "rbf gamma=0.01": SVC(gamma=0.01), "rbf gamma=1": SVC(gamma=1), "rbf gamma=100": SVC(gamma=100)}
fig, axes = plt.subplots(2, 3, figsize=(11, 7))
for ax, (name, m) in zip(axes.ravel(), models.items()):
    m.fit(Xtr, ytr)
    ax.contourf(xx, yy, m.decision_function(grid_pts).reshape(xx.shape) > 0, alpha=0.25, cmap="coolwarm")
    ax.scatter(Xtr[:, 0], Xtr[:, 1], c=ytr, s=6, cmap="coolwarm")
    ax.set_title(f"{name}: train {m.score(Xtr, ytr):.2f}, test {m.score(Xte, yte):.2f}", fontsize=9)
    print(f"{name:14s} train {m.score(Xtr, ytr):.3f}  test {m.score(Xte, yte):.3f}  SV {m.n_support_.sum()}")

gammas, Cs = np.logspace(-2, 3, 6), np.logspace(-2, 3, 6)
gs = GridSearchCV(SVC(kernel="rbf"), {"gamma": gammas, "C": Cs}, cv=5).fit(Xtr, ytr)
S = gs.cv_results_["mean_test_score"].reshape(len(Cs), len(gammas))   # সারি = C, কলাম = gamma
ax = axes[1, 2]
im = ax.imshow(S, origin="lower", cmap="viridis", vmin=0.5, vmax=1)
ax.set(xticks=range(6), xticklabels=[f"{v:g}" for v in gammas], yticks=range(6),
       yticklabels=[f"{v:g}" for v in Cs], xlabel="gamma", ylabel="C", title="5-fold CV accuracy")
fig.colorbar(im, ax=ax); fig.subplots_adjust(wspace=0.35, hspace=0.35)
best = {k: float(v) for k, v in gs.best_params_.items()}
print("best", best, f"CV {gs.best_score_:.3f}  test {gs.score(Xte, yte):.3f}")
print("CV rows=C, cols=gamma:\n", np.round(S, 2))

linear         train 0.600  test 0.600  SV 171
poly d=2       train 0.886  test 0.956  SV 66
rbf gamma=0.01 train 0.610  test 0.611  SV 168
rbf gamma=1    train 0.914  test 0.878  SV 78
rbf gamma=100  train 0.995  test 0.856  SV 189
best {'C': 0.1, 'gamma': 1.0} CV 0.876  test 0.878
CV rows=C, cols=gamma:
 [[0.6  0.6  0.6  0.6  0.6  0.6 ]
 [0.6  0.78 0.88 0.6  0.6  0.6 ]
 [0.6  0.83 0.86 0.87 0.83 0.6 ]
 [0.8  0.86 0.84 0.86 0.84 0.59]
 [0.84 0.84 0.81 0.87 0.84 0.59]
 [0.85 0.83 0.84 0.87 0.84 0.59]]

Chih-Wei Hsu, Chih-Chung Chang আর Chih-Jen Lin (LIBSVM-এর লেখকরা) তাঁদের বহুল ব্যবহৃত “A Practical Guide to Support Vector Classification” নির্দেশিকায় ঠিক এই ক্রম সুপারিশ করেন: feature scale করুন, প্রথমে RBF চেষ্টা করুন, C আর γ সূচকীয় ধাপে (যেমন C-এর জন্য ২^−৫ থেকে ২^১৫, γ-এর জন্য ২^−১৫ থেকে ২^৩) cross-validation-এ খুঁজুন, তারপর সেরার চারপাশে সূক্ষ্ম grid. Feature অনেক বেশি হলে (যেমন লেখার শব্দ) linear kernel প্রায়ই সমান ভালো আর অনেক দ্রুত।

৭ · Representer theorem আর vector ছাড়া ডেটার kernel

অংশ ২-এ দেখেছেন, SVM-এর উত্তর f(x) = ∑α_iy_ik(x_i, x) + b, অর্থাৎ train বিন্দুগুলোর kernel-এর একটি ওজনযুক্ত যোগফল। এটি SVM-এর কাকতালীয় গুণ নয়। Representer theorem বলে: যদি loss শুধু train বিন্দুতে f-এর মানের ওপর নির্ভর করে, আর তার সঙ্গে ‖f‖²-এর মতো একটি বাড়ন্ত regularization শাস্তি থাকে, তবে kernel-এর feature space-এ সেরা f সবসময় f(x) = ∑_i c_i k(x_i, x) আকারের। George Kimeldorf আর Grace Wahba ১৯৭১ সালে spline-এর প্রসঙ্গে এর একটি রূপ দেন; Bernhard Schölkopf, Ralf Herbrich আর Alex Smola ২০০১ সালে সাধারণ রূপটি প্রকাশ করেন।

এর মানে বিশাল: অসীম মাত্রার জগতেও খুঁজতে হয় শুধু n টি সংখ্যা c₁ … c_n. Hinge loss দিলে SVM (অনেক c শূন্য, তাই sparse); বর্গ-ভুল দিলে kernel ridge regression, যার উত্তর c = (K + λI)⁻¹y একটি linear system থেকে আসে (পর্ব ৩০, SVR আর kernel ridge regression); PCA-তে বসালে kernel PCA (পর্ব ৪১); আর Gaussian process-এর গড় অনুমানও একই আকারের (পর্ব ৪৬)। পর্ব ১৭-এর ridge-এর সঙ্গে সম্পর্কও এখানেই।

যেখানে vector-ই নেই — string আর graph kernel

Kernel trick-এর একটি কম আলোচিত শক্তি: ডেটা সংখ্যার vector না হলেও চলে, শুধু দুটি বস্তুর মধ্যে একটি বৈধ মিলের function লাগে। বাজারঘরের পণ্যের বর্ণনা ধরুন, যেমন “সুতি শাড়ি লাল” আর “লাল সুতি থ্রি-পিস”. একটি সহজ string kernel: দুটি লেখায় সাধারণ অক্ষর-ত্রয়ী (character 3-gram) কতবার আছে, তার গণনার dot product. এটি বৈধ, কারণ φ হলো “প্রতিটি সম্ভাব্য ৩-অক্ষরের টুকরো কতবার আছে” তার vector; তবে kernel সেই বিশাল vector না বানিয়ে শুধু দুটি লেখার মিলে যাওয়া টুকরো গোনে। David Haussler ১৯৯৯ সালে গঠনযুক্ত ডেটার জন্য convolution kernel-এর কাঠামো দেন, আর Huma Lodhi ও সহকর্মীরা ২০০২ সালে (JMLR) ফাঁক রেখে মেলানো subsequence kernel দিয়ে লেখার শ্রেণিবিভাগ দেখান। Protein-এর ক্রম আর অণুর graph-এর জন্যও এমন kernel আছে। scikit-learn-এ SVC(kernel="precomputed")-এ নিজের Gram matrix দেওয়া যায়, শুধু তখন PSD-এর দায় আপনার।

৮ · AI-এর যুগে — kernel-এর কোড আর দাবি যাচাই

AI assistant-কে “SVM দিয়ে classifier বানাও” বললে সে প্রায় নিশ্চিতভাবে চলনসই কোড দেয়। সমস্যা থাকে সূক্ষ্ম জায়গায়: scaling, grid-এর পরিসর, কোন ডেটায় মাপা হলো, আর kernel সম্পর্কে আত্মবিশ্বাসী কিন্তু ভুল কথা। পরিচিত ভুলগুলো:

AI-এর দেওয়া kernel কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Scaler আর SVC একই Pipeline-এ, আর split সবার আগে হয়েছে
• γ আর C log-মাপের grid-এ খোঁজা, সেরা মান কিনারায় নয়
• রিপোর্টে CV score আর তালাবন্ধ test আলাদা; train accuracy-কে ফল বলা হয়নি
• একটি সরল baseline (linear বা logistic) আর কয়েকটি seed-এর সঙ্গে তুলনা আছে
• নিজের kernel হলে সবচেয়ে ছোট eigenvalue দেখে PSD যাচাই করেছি
• Kernel-এর সূত্র (যেমন poly-র coef0) একটি ছোট উদাহরণে হাতে হিসাব করে মিলিয়েছি
• SVC-র decision_function-কে সম্ভাবনা বলা হয়নি (পর্ব ২৬), আর কোনো আসল গ্রাহকের ডেটা AI-তে পেস্ট করিনি