বড় ডেটায় kernel — Nyström, random features আর কখন SVM নয়

এই মডিউলে আগের চারটি পর্বে SVM-এর পুরো ভিত তৈরি হচ্ছে: পর্ব ২৭ (Support Vector Machine — margin, support vector আর hard margin), পর্ব ২৮ (Soft margin — hinge loss, C আর dual problem), পর্ব ২৯ (Kernel trick — RBF, polynomial আর Mercer-এর অন্তর্দৃষ্টি) আর পর্ব ৩০ (SVR আর kernel ridge regression — kernel দিয়ে সংখ্যার অনুমান)। সেখানে kernel trick-এর জাদু দেখেছেন: dual শুধু dot product চায়, তাই x_i·x_j-এর জায়গায় k(x_i, x_j) বসালেই অ-রৈখিক সীমা। এই পর্ব সেই জাদুর দাম নিয়ে। দামটা হলো প্রতিটি জোড়ার মিল; n বাড়লে জোড়া বাড়ে n² হারে। তারপর দেখবেন দুটি কৌশল, যা kernel-এর সুবিধা প্রায় রেখে দাম কমায়, আর কখন SVM-কে সরিয়ে অন্য model নেওয়াই বুদ্ধিমানের কাজ। চালানো যায় এমন চারটি ব্লক পাতাতেই চলে (ব্রাউজারের Python, scikit-learn 1.8.0); প্রথমবার scikit-learn নামতে প্রায় দশ সেকেন্ড লাগে। বড় n-এর মাপ এসেছে ডেস্কটপের সত্যিকারের run থেকে।

১ · Kernel-এর দাম — প্রতিটি জোড়ার মিল

n টি সারির জন্য kernel k দিয়ে Gram matrix K হলো n×n, যার (i, j) ঘরে k(x_i, x_j). পর্ব ১০-এ (Positive definite matrix) দেখেছেন, বৈধ kernel-এর K সবসময় positive semidefinite. এখানে আমাদের প্রশ্ন সরল: এই matrix রাখতে কত জায়গা, আর তা দিয়ে শেখাতে কত সময়?

Memory: প্রতিটি float64 সংখ্যা ৮ বাইট, তাই পুরো K রাখতে ৮n² বাইট. Symmetric বলে অর্ধেক রাখলেও ক্রম একই, n². নিচের হিসাব খাতায় করার মতো:

সময়: scikit-learn-এর SVC ভেতরে libsvm চালায় (Chih-Chung Chang আর Chih-Jen Lin-এর library). সে পুরো K বানায় না; dual problem-কে SMO (sequential minimal optimization, John Platt ১৯৯৮) ধরনের পদ্ধতিতে প্রতিবার দুটি α বদলে সমাধান করে, আর দরকারি kernel সারিগুলো একটি cache-এ রাখে (cache_size, ডিফল্ট ২০০ MB). তাতে memory বাঁচে, কিন্তু সময় বাঁচে না: যত বেশি সারি support vector হয়, তত বেশি kernel সারি বারবার হিসাব হয়। scikit-learn-এর নিজের docs বলে, SVC-এর fit time সারির সংখ্যার সঙ্গে অন্তত দ্বিঘাত (quadratic) হারে বাড়ে আর কয়েক দশ হাজার সারির পরে অবাস্তব হতে পারে। সাধারণভাবে বলা হয়, SMO-জাতীয় solver-এর খরচ ডেটা আর C-এর ওপর নির্ভর করে মোটামুটি n² থেকে n³-এর মধ্যে; এটি অভিজ্ঞতার কথা, কোনো নিশ্চিত সূত্র নয়।

Prediction-ও সস্তা নয়: একটি নতুন অর্ডারের score f(x) = ∑ α_iy_ik(x_i, x) + b, যোগফল সব support vector-এর ওপর। Support vector-এর সংখ্যা ডেটার সঙ্গে বাড়ে (ভুল label বা গোলমাল বেশি হলে প্রায় সেই অনুপাতে), তাই বড় ডেটায় model বড়, আর প্রতিটি prediction ধীর।

২ · মেপে দেখা — n দ্বিগুণ হলে fit time কত গুণ

কথা নয়, মাপ। এই পর্বের ডেটা: বাজারঘরের কাল্পনিক অর্ডার, seed দিয়ে বানানো, কোনো আসল দোকানের নয়। তিনটি feature, সবগুলো z-score: অর্ডারের টাকা, অ্যাকাউন্টের বয়স আর ঠিকানা বদলের প্রবণতা। লক্ষ্য: অর্ডারটি “সন্দেহজনক” ফ্ল্যাগ পাবে কি না। নিয়মটি অ-রৈখিক: স্বাভাবিক অর্ডারের কেন্দ্র থেকে যত দূরে, তত সন্দেহ; সঙ্গে ৫% ভুল label. প্রায় ২৭% অর্ডার ফ্ল্যাগ পায়। কোনো সরলরেখা এমন বৃত্তাকার সীমা আঁকতে পারে না, তাই এটি kernel-এর জন্য উপযুক্ত ডেটা।

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

def make_fraud(n, seed=31):
    rng = np.random.default_rng(seed)
    amount = rng.normal(0, 1, n)                     # অর্ডারের টাকা (z-score)
    age = rng.normal(0, 1, n)                        # অ্যাকাউন্টের বয়স (z-score)
    moves = rng.normal(0, 1, n)                      # ঠিকানা বদল (z-score)
    odd = np.hypot(amount - 0.3, age + 0.2) + 0.4 * moves   # অস্বাভাবিকতা
    y = (odd > 1.8).astype(int)
    flip = rng.random(n) < 0.05                      # ৫% ভুল label
    y[flip] = 1 - y[flip]
    return np.column_stack([amount, age, moves]), y

প্রথম ব্লক n = ২৫০ থেকে ৪,০০০ পর্যন্ত প্রতিবার দ্বিগুণ করে RBF SVC শেখায়, সময় আর support vector গোনে, তারপর log–log স্কেলে একটি সরলরেখা বসিয়ে বৃদ্ধির ঘাত (exponent) বের করে। log(সময়) = k · log(n) + ধ্রুবক হলে সময় ∝ n^k; ঢাল k-ই উত্তর। ছোট n-এ সময় এত কম যে গোলমাল বেশি, তাই ঢাল মাপা হয়েছে শেষ তিনটি বিন্দুতে।

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

sizes = np.array([250, 500, 1000, 2000, 4000])
times, nsv = [], []
for n in sizes:
    X, y = make_fraud(n)
    t0 = time.perf_counter()
    svc = SVC(kernel="rbf", C=1.0, gamma=0.5).fit(X, y)
    times.append(time.perf_counter() - t0)
    nsv.append(svc.n_support_.sum())
    print(f"n = {n:4d}  fit {times[-1]:6.3f} s  support vectors {nsv[-1]:4d}"
          f"  full Gram {8 * n * n / 1e6:6.1f} MB")
k = np.polyfit(np.log(sizes[2:]), np.log(times[2:]), 1)[0]
print(f"fitted growth (n = 1000..4000): time ~ n^{k:.2f}")
big = np.array([1e4, 1e5, 1e6])
print("full Gram at n =", ", ".join(f"{int(m):,}: {8 * m * m / 1e9:,.1f} GB" for m in big))

fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.8))
a1.loglog(sizes, times, "o-", label="measured SVC fit")
a1.loglog(sizes, times[-1] * (sizes / sizes[-1]) ** 2, "k--", lw=1, label="slope 2")
a1.set(xlabel="n (orders)", ylabel="fit time (s)", title="Exact RBF SVC")
a1.legend(fontsize=8)
grid = np.logspace(3, 6, 30)
a2.loglog(grid, 8 * grid ** 2 / 1e9, label="n x n float64 Gram")
a2.axhline(16, color="r", ls=":", label="16 GB laptop RAM")
a2.set(xlabel="n (orders)", ylabel="memory (GB)", title="Gram matrix memory")
a2.legend(fontsize=8)

n =  250  fit  0.014 s  support vectors  106  full Gram    0.5 MB
n =  500  fit  0.014 s  support vectors  194  full Gram    2.0 MB
n = 1000  fit  0.046 s  support vectors  339  full Gram    8.0 MB
n = 2000  fit  0.160 s  support vectors  603  full Gram   32.0 MB
n = 4000  fit  0.516 s  support vectors 1020  full Gram  128.0 MB
fitted growth (n = 1000..4000): time ~ n^1.74
full Gram at n = 10,000: 0.8 GB, 100,000: 80.0 GB, 1,000,000: 8,000.0 GB

বড় n-এ কী হয়, তা ব্রাউজারে মাপা যায় না, ব্রাউজার আটকে যাবে। তাই একই ডেটা-নিয়মে ডেস্কটপে সত্যিকারের run (একটি সাধারণ ল্যাপটপ, Python 3.14.4, scikit-learn 1.9.1, NumPy 2.5.4; একটি run, সাধারণ ফল নয়)। প্রতিটি n-এ exact SVC আর অংশ ৭-এর Nyström + LinearSVC pipeline, আর ২০,০০০ অর্ডারের একটি আলাদা test-এ accuracy:

~/bazarghar-ml$ python scale.py
Python 3.14.4, scikit-learn 1.9.1
      n   model              fit (s)   #SV   test acc
   4,000  exact SVC             0.06    1024  0.9351
   4,000  Nystroem+LinearSVC    0.22       -  0.9381
  16,000  exact SVC             0.92    3459  0.9439
  16,000  Nystroem+LinearSVC    1.69       -  0.9431
  64,000  exact SVC            13.60   13361  0.9449
  64,000  Nystroem+LinearSVC   11.48       -  0.9462
 128,000  exact SVC            54.52   26268  0.9460
 128,000  Nystroem+LinearSVC   27.44       -  0.9458
1,000,000  Nystroem+LinearSVC  394.59       -  0.9477

Exact SVC: n চার গুণ (৪,০০০ থেকে ১৬,০০০) হলে সময় প্রায় ১৫ গুণ; ৬৪,০০০ থেকে ১,২৮,০০০ (দ্বিগুণ) হলে ১৩.৬ থেকে ৫৪.৫ সেকেন্ড, ঠিক চার গুণ, অর্থাৎ ঢাল প্রায় ২. Support vector ২৬,২৬৮, n-এর প্রায় ২০%; এরা সবাই model-এ জমা থাকে। একই ঢালে দশ লাখ সারিতে exact SVC লাগত মোটামুটি ৫৪.৫ × (১০,০০,০০০/১,২৮,০০০)² ≈ ৩,৩০০ সেকেন্ড, প্রায় এক ঘণ্টা; এটি হিসাব, চালানো হয়নি। Nyström + LinearSVC ছোট n-এ বরং ধীর (৪,০০০-এ ০.২২ বনাম ০.০৬), ১৬,০০০ আর ৬৪,০০০-এর মাঝে দুটি সমান হয়, ১,২৮,০০০-এ প্রায় অর্ধেক সময় নেয়। Accuracy সবখানে ০.৯৪–০.৯৫: ৫% label উল্টানো, তাই ০.৯৫-এর কাছে ছাদ। কিন্তু দশ লাখে Nyström + LinearSVC-ও ৩৯৫ সেকেন্ড নিল; কেন, তা নিচের run দেখায়।

দশ লাখ সারিতে সময় কোথায় যায়, তা আলাদা করে মাপা (একই ল্যাপটপ, একটি run): scaling আর Nyström feature এক ধাপে, তারপর একই feature-এ দুটি linear model.

~/bazarghar-ml$ python scale_1m.py
scale + Nystroem features:    3.23 s  Z (1000000, 300), 2.4 GB
SGDClassifier hinge  fit    7.61 s  test acc 0.9425
LinearSVC            fit  402.89 s  test acc 0.9477

Nyström feature বানাতে মাত্র ৩.২ সেকেন্ড, যদিও Z নিজেই ২.৪ GB (প্রথম stepper-এর হিসাবের সঙ্গে হুবহু মেলে)। সময় খেয়েছে LinearSVC: ৪০৩ সেকেন্ড। একই feature-এ SGDClassifier(loss="hinge") শিখেছে ৭.৬ সেকেন্ডে, accuracy ০.৯৪২৫ বনাম ০.৯৪৭৭. অর্থাৎ বড় আর dense feature-এ liblinear-এর নিখুঁত সমাধানের চেয়ে SGD-এর “যথেষ্ট ভালো” সমাধান অনেক সস্তা; দামটি হলো আধা শতাংশ বিন্দুর মতো accuracy আর alpha ও epoch বাছাইয়ের ঝামেলা। এক ঘণ্টার exact SVC-এর জায়গায় প্রায় ১১ সেকেন্ড, একই ডেটা-নিয়মে।

৩ · Kernel ছাড়া SVM — LinearSVC আর SGDClassifier

Kernel-এর খরচ আসে জোড়া থেকে। Kernel না থাকলে, অর্থাৎ সীমাটি x-এর ওপর সরাসরি একটি hyperplane w·x + b হলে, জোড়ার দরকারই নেই। তখন dual-এর বদলে primal সমস্যাটি সরাসরি সমাধান করা যায় (পর্ব ২৮-এ তার রূপ দেখেছেন):

min_{w, b} ½‖w‖² + C ∑_i max(0, 1 − y_i(w·x_i + b))

এখানে y_i হলো −১ বা +১, আর max(0, ১ − margin) হলো hinge loss (পর্ব ০২)। w-তে d টি সংখ্যা, d হলো feature-সংখ্যা। প্রতিটি পূর্ণ পাস ডেটার ওপর একবার যায়, খরচ মোটামুটি n × d, আর ডেটা sparse হলে শুধু অশূন্য ঘরের সংখ্যার সমানুপাতিক। এই খরচ n-এর সঙ্গে রৈখিক।

কোথায় linear SVM সবচেয়ে ভালো কাজ করে? লেখার ডেটায়। Thorsten Joachims ১৯৯৮ সালে (ECML) দেখান, অনেক শব্দের feature-এ লেখার শ্রেণিবিভাগে SVM সে সময়ের অন্য পদ্ধতির চেয়ে ভালো, আর linear kernel-ই প্রায় যথেষ্ট। কারণ: হাজার হাজার মাত্রায় ডেটা প্রায়ই প্রায়-রৈখিকভাবে আলাদা করা যায়, kernel যোগ করে লাভ কম। বাজারঘরের পণ্য-বর্ণনার একটি কাল্পনিক উদাহরণ, পাঁচটি বিভাগ (পোশাক, ইলেকট্রনিক্স, মুদি, বই, প্রসাধনী), TF-IDF শব্দ আর শব্দজোড়া (AI-এর ভিত্তি কোর্সের পর্ব ৬৭-এ TF-IDF আর বাংলা tokenization). বাংলা স্বরচিহ্ন regex-এর \w-এ পড়ে না বলে token ভাঙা হয়েছে ফাঁকা জায়গা দিয়ে (token_pattern=r"\S+"). ডেস্কটপে সত্যিকারের run (একটি run):

~/bazarghar-ml$ python text_svm.py
Python 3.14.4, scikit-learn 1.9.1
train X: 200,000 x 3,269, nonzeros 2,808,934 (0.42963% filled), 22 MB data
a dense 200,000 x 200,000 float64 Gram matrix would need 320 GB
LinearSVC            fit   5.41 s   test accuracy 0.9922
SGDClassifier hinge  fit   1.01 s   test accuracy 0.9923

দুই লাখ বর্ণনার TF-IDF matrix-এ মাত্র ০.৪৩% ঘর অশূন্য, ডেটা মাত্র ২২ MB; অথচ একই সারিসংখ্যায় পুরো Gram matrix ৩২০ GB হতো। LinearSVC ৫.৪ সেকেন্ডে, SGDClassifier ১.০ সেকেন্ডে শেখে, দুটিরই test accuracy ০.৯৯২. সতর্কতা: এই কাল্পনিক বর্ণনা খুব সহজ, প্রতিটি বিভাগের নিজস্ব শব্দ আছে, আর শব্দভান্ডারও ছোট (৩,২৬৯টি কলাম); আসল বর্ণনায় কলাম লাখের ঘরে আর accuracy অনেক কম হবে। কিন্তু মূল কথা টেকে: sparse লেখায় linear SVM-এর খরচ অশূন্য ঘরের সংখ্যার সমানুপাতিক, n²-এর নয়।

৪ · Nyström — কয়েকটি landmark দিয়ে পুরো kernel matrix

n টি বিন্দু থেকে m টি (m ≪ n) landmark বাছুন, সাধারণত এলোমেলোভাবে। তারপর দুটি ছোট matrix:

• C (n×m): প্রতিটি বিন্দুর সঙ্গে প্রতিটি landmark-এর kernel মান, C_ij = k(x_i, l_j).
• W (m×m): landmark-দের নিজেদের Gram matrix, W_jk = k(l_j, l_k); এটি C-এরই কয়েকটি সারি।

K ≈ K̃ = C W⁺ Cᵀ

W⁺ হলো W-এর Moore–Penrose pseudo-inverse (পর্ব ০৯); W উল্টানো গেলে W⁺ = W⁻¹. ফলটি rank m-এর একটি low-rank approximation. এর নাম এসেছে Evert Nyström-এর ১৯৩০ সালের integral equation সমাধানের পদ্ধতি থেকে; kernel machine-এ এটি আনেন Christopher Williams আর Matthias Seeger (NIPS ২০০০ সম্মেলন, প্রকাশ ২০০১)।

কেন কাজ করে? RBF kernel-এর Gram matrix-এর eigenvalue সাধারণত দ্রুত ছোট হয়ে যায়: কয়েকটি বড় দিকেই প্রায় সব তথ্য, বাকিরা প্রায় শূন্য। তাই একটি ছোট rank-এর matrix K-কে ভালোভাবে ধরতে পারে। Eckart–Young (পর্ব ০৯) বলে সেরা rank-m approximation আসে K-এর সবচেয়ে বড় m টি eigenvalue থেকে; কিন্তু তা পেতে পুরো K লাগে। Nyström সেই সেরার একটি সস্তা আন্দাজ, যা K-এর মাত্র m টি কলাম দেখে।

নিচে চারটি বিন্দুতে পুরো হিসাব, যাতে সূত্রটি হাতে ধরা যায়। এক-মাত্রার বিন্দু x = ০, ১, ২, ৩, RBF kernel k(a, b) = exp(−γ(a − b)²), γ = ০.৫; landmark হলো x = ১ আর x = ২.

K̃ থেকে feature — linear model-এর জন্য

K̃ বানিয়ে লাভ নেই, সেটিও n×n. আসল কৌশল হলো প্রতিটি বিন্দুর জন্য m টি সংখ্যার একটি feature:

φ(x) = W^−½ c(x),   যেখানে c(x) = (k(x, l₁), …, k(x, l_m))

তাহলে φ(x)·φ(y) = c(x)ᵀ W⁻¹ c(y) = K̃(x, y). অর্থাৎ φ-এর ওপর সাধারণ dot product-ই Nyström kernel. এখন যেকোনো linear model (LinearSVC, logistic regression, ridge) এই n×m feature-এ চালান: kernel-এর অ-রৈখিকতা আছে, জোড়ার খরচ নেই। scikit-learn-এর Nystroem ঠিক এই কাজ করে: fit-এ এলোমেলো m টি সারি বেছে W-এর SVD থেকে W^−½ (normalization_) রাখে, খুব ছোট singular value-কে ১০⁻¹²-এ আটকে; transform-এ C × W^−½ ফেরত দেয়। খরচ: C বানাতে n·m·d, W-এর SVD m³, গুণ n·m²; memory n·m.

৫ · Nyström হাতে-কলমে — নিজে লেখা, Nystroem আর সেরা সম্ভব

দ্বিতীয় ব্লক ১,০০০টি অর্ডারের পুরো Gram matrix বানায় (এই আকারে তা সস্তা, শুধু তুলনার জন্য), তারপর m বাড়িয়ে তিনটি আপেক্ষিক Frobenius ভুল মাপে: নিজে লেখা Nyström (scipy.linalg.pinv দিয়ে), scikit-learn-এর Nystroem (Z Zᵀ দিয়ে K̃), আর Eckart–Young-এর সেরা rank-m, যা K-এর eigenvalue থেকে আসে। পরের ব্লক এই ব্লকের ফল ব্যবহার করে, তাই দুটি একই namespace-এ চলে।

import numpy as np
from scipy.linalg import eigh, pinv
from sklearn.kernel_approximation import Nystroem
from sklearn.metrics.pairwise import rbf_kernel
from bazar_fraud import make_fraud

X, y = make_fraud(1000, seed=2)
gamma = 0.5
K = rbf_kernel(X, gamma=gamma)                   # পুরো 1000 × 1000 Gram
normK = np.linalg.norm(K)                        # Frobenius norm
lam = eigh(K, eigvals_only=True)[::-1]           # eigenvalue, বড় থেকে ছোট
rng = np.random.default_rng(0)

def nystrom_own(m):
    idx = rng.choice(len(X), m, replace=False)   # m টি landmark
    C = rbf_kernel(X, X[idx], gamma=gamma)       # n × m
    W = C[idx]                                   # m × m
    return C @ pinv(W) @ C.T                     # K ≈ C W⁺ Cᵀ

ms = [5, 10, 25, 50, 100, 200, 400]
err_ny = []
print("  m   own Nystrom  sklearn  best rank-m (SVD)")
for m in ms:
    e_own = np.linalg.norm(K - nystrom_own(m)) / normK
    Z = Nystroem(gamma=gamma, n_components=m, random_state=0).fit_transform(X)
    e_sk = np.linalg.norm(K - Z @ Z.T) / normK
    e_best = np.sqrt(np.sum(lam[m:] ** 2)) / normK   # Eckart–Young সীমা
    err_ny.append(e_sk)
    print(f"{m:4d}   {e_own:.4f}      {e_sk:.4f}   {e_best:.4f}")
print("feature matrix Z:", Z.shape, f"{Z.nbytes / 1e6:.1f} MB vs K {K.nbytes / 1e6:.1f} MB")

  m   own Nystrom  sklearn  best rank-m (SVD)
   5   0.4635      0.5645   0.2986
  10   0.3870      0.4926   0.1589
  25   0.1821      0.1676   0.0590
  50   0.0598      0.0668   0.0191
 100   0.0266      0.0215   0.0032
 200   0.0099      0.0088   0.0001
 400   0.0036      0.0026   0.0000
feature matrix Z: (1000, 400) 3.2 MB vs K 8.0 MB

৬ · Random Fourier features — cos দিয়ে kernel-এর নমুনা

Nyström ডেটা থেকে landmark নেয়। Ali Rahimi আর Benjamin Recht ২০০৭ সালে (NIPS, “Random Features for Large-Scale Kernel Machines”) সম্পূর্ণ অন্য পথ দেখান: ডেটা না দেখেই এলোমেলো feature বানানো, যাদের dot product গড়ে kernel-এর সমান। এই প্রবন্ধ ২০১৭ সালে NIPS-এর “test of time” পুরস্কার পায় বলে জানা যায়।

ভিত্তি হলো Bochner-এর উপপাদ্য: k(x, y) যদি শুধু x − y-এর ওপর নির্ভর করে (shift-invariant) আর বৈধ kernel হয়, তবে সেটি একটি সম্ভাবনা বণ্টন p(ω)-এর Fourier রূপ, অর্থাৎ k(x, y) = E_ω[cos(ωᵀ(x − y))]. RBF kernel exp(−γ‖x − y‖²)-এর জন্য p(ω) হলো N(0, 2γI), একটি Gaussian. প্রত্যাশা (expectation)-কে D টি নমুনার গড় দিয়ে আন্দাজ করলেই random Fourier features:

z(x) = √(2/D) · cos(ωᵀx + b),   ω ~ N(0, 2γI),   b ~ U(0, 2π)

এখানে D টি ω (প্রতিটি d-মাত্রার) আর D টি b একবার এলোমেলোভাবে টানা হয়, সব সারির জন্য একই। b-এর ভূমিকা: দুটি cos-এর গুণফলকে cos(ωᵀ(x − y))-এ আনা, কারণ b-এর ওপর গড় নিলে cos(ωᵀ(x + y) + 2b) পদটি শূন্য হয়ে যায়। তাই E[z(x)·z(y)] = k(x, y), আর গড়টি D টি স্বাধীন পদের, ফলে ভুলের standard deviation কমে প্রায় 1/√D হারে, যেমন যেকোনো Monte Carlo অনুমানে। ভুল অর্ধেক করতে D চার গুণ।

scikit-learn-এর RBFSampler হুবহু এই সূত্র (source-এ random_weights_ = √(2γ) × standard normal, random_offset_ = U(0, 2π), শেষে √(2/D) দিয়ে গুণ)। সাবধান: তার ডিফল্ট gamma=1.0, যেখানে SVC-এর ডিফল্ট gamma="scale"; একই γ নিজে বসান। তৃতীয় ব্লক প্রথমে একটি জোড়ার kernel D বাড়িয়ে আন্দাজ করে, তারপর পুরো Gram matrix-এর ভুল মেপে আগের ব্লকের Nyström-এর সঙ্গে একটি ছবিতে রাখে।

import matplotlib.pyplot as plt
from sklearn.kernel_approximation import RBFSampler

def rff_own(X, D, seed=0):
    r = np.random.default_rng(seed)
    w = r.normal(0, np.sqrt(2 * gamma), size=(X.shape[1], D))   # ω ~ N(0, 2γI)
    b = r.uniform(0, 2 * np.pi, D)                               # b ~ U(0, 2π)
    return np.sqrt(2 / D) * np.cos(X @ w + b)                    # n × D

x, z = X[0:1], X[5:6]
print(f"one pair: exact k = {rbf_kernel(x, z, gamma=gamma)[0, 0]:.4f}")
for D in [10, 100, 1000, 10000]:
    F = rff_own(np.vstack([x, z]), D)
    print(f"  D = {D:5d}: z(x).z(y) = {F[0] @ F[1]:.4f}")

err_rff, err_rbs = [], []
for D in ms:
    F = rff_own(X, D)
    err_rff.append(np.linalg.norm(K - F @ F.T) / normK)
    Z = RBFSampler(gamma=gamma, n_components=D, random_state=0).fit_transform(X)
    err_rbs.append(np.linalg.norm(K - Z @ Z.T) / normK)
print("  D   own RFF  RBFSampler  (Nystroem, same m)")
for D, a, b, c in zip(ms, err_rff, err_rbs, err_ny):
    print(f"{D:4d}   {a:.4f}   {b:.4f}      {c:.4f}")

fig, ax = plt.subplots(figsize=(6.5, 4))
ax.loglog(ms, err_ny, "o-", label="Nystroem (sklearn)")
ax.loglog(ms, err_rff, "s-", label="random Fourier (own)")
ax.loglog(ms, err_rbs, "^--", label="RBFSampler (sklearn)")
ax.loglog(ms, err_rff[0] * np.sqrt(ms[0] / np.array(ms)), "k:", label="1/sqrt(D) slope")
ax.set(xlabel="number of components (m or D)", ylabel="relative Frobenius error",
       title="Approximating a 1000 x 1000 RBF Gram matrix")
ax.legend(fontsize=8)

one pair: exact k = 0.5353
  D =    10: z(x).z(y) = 0.1721
  D =   100: z(x).z(y) = 0.4380
  D =  1000: z(x).z(y) = 0.5609
  D = 10000: z(x).z(y) = 0.5326
  D   own RFF  RBFSampler  (Nystroem, same m)
   5   1.2347   1.4729      0.5645
  10   0.8171   1.0489      0.4926
  25   0.7994   0.6469      0.1676
  50   0.3917   0.4554      0.0668
 100   0.3011   0.3507      0.0215
 200   0.2509   0.2403      0.0088
 400   0.1894   0.1938      0.0026

৭ · আনুমানিক kernel + linear model বনাম exact SVC

এখন আসল পরীক্ষা: approximation দিয়ে শেখানো classifier কি exact SVC-এর মতো ভালো? চতুর্থ ব্লক ৪,০০০টি অর্ডারে পাঁচটি model শেখায়, প্রতিটির আগে StandardScaler একই pipeline-এ (AI-এর ভিত্তি কোর্সের পর্ব ৬৪: scaler শুধু train-এ শেখে)। Kernel দূরত্বভিত্তিক, তাই scaling না করলে বড় এককের feature-ই সব ঠিক করে দেয়। তারপর একটি আলাদা, তালাবন্ধ ৪,০০০ অর্ডারের test-এ accuracy, fit আর predict-এর সময়। γ = ০.৫ আর C = ১ ইচ্ছা করে সবার জন্য এক রাখা হয়েছে, যাতে তুলনাটি শুধু approximation-এর; বাস্তবে এগুলো cross-validation দিয়ে বাছবেন (AI-এর ভিত্তি কোর্সের পর্ব ৬৬)।

import time
import numpy as np
from sklearn.kernel_approximation import Nystroem, RBFSampler
from sklearn.linear_model import SGDClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC, LinearSVC
from bazar_fraud import make_fraud

X, y = make_fraud(4000)                          # train: ৪,০০০ অর্ডার
Xte, yte = make_fraud(4000, seed=7)              # তালাবন্ধ test
g, D = 0.5, 300
models = {
    "linear SVM only": LinearSVC(C=1.0),
    "exact RBF SVC": SVC(kernel="rbf", C=1.0, gamma=g),
    "Nystroem+LinearSVC": make_pipeline(Nystroem(gamma=g, n_components=D, random_state=0),
                                        LinearSVC(C=1.0)),
    "Nystroem+SGD hinge": make_pipeline(Nystroem(gamma=g, n_components=D, random_state=0),
                                        SGDClassifier(loss="hinge", alpha=1e-4, random_state=0)),
    "RBFSampler+LinearSVC": make_pipeline(RBFSampler(gamma=g, n_components=D, random_state=0),
                                          LinearSVC(C=1.0)),
}
print(f"base rate (flagged) = {yte.mean():.3f}")
print("model                  fit s  predict s  test acc")
for name, m in models.items():
    pipe = make_pipeline(StandardScaler(), m)
    t0 = time.perf_counter(); pipe.fit(X, y); t1 = time.perf_counter()
    acc = pipe.score(Xte, yte); t2 = time.perf_counter()
    print(f"{name:21s} {t1 - t0:6.3f}  {t2 - t1:8.3f}   {acc:.4f}")
svc = models["exact RBF SVC"]
print(f"exact SVC keeps {svc.n_support_.sum()} support vectors; "
      f"Nystroem keeps {D} landmarks")

base rate (flagged) = 0.268
model                  fit s  predict s  test acc
linear SVM only        0.009     0.002   0.7750
exact RBF SVC          0.527     0.482   0.9345
Nystroem+LinearSVC     0.697     0.334   0.9360
Nystroem+SGD hinge     0.481     0.332   0.9277
RBFSampler+LinearSVC   0.290     0.046   0.9355
exact SVC keeps 1024 support vectors; Nystroem keeps 300 landmarks

৮ · কখন SVM নয় — সিদ্ধান্তের মানচিত্র

SVM একটি চমৎকার যন্ত্র, কিন্তু সব কাজের নয়। নিচের টেবিল কয়েকটি সাধারণ পরিস্থিতি আর যুক্তিসঙ্গত প্রথম পছন্দ দেখায়; এগুলো অভিজ্ঞতার নিয়ম, প্রমাণিত সূত্র নয়, আর শেষ কথা সবসময় আপনার ডেটায় cross-validation.

সম্ভাবনা নিয়ে আলাদা কথা। পর্ব ২৬-এ দেখেছেন, SVM-এর decision function সম্ভাবনা নয়। SVC(probability=True) দিলে libsvm ভেতরে ৫-fold cross-validation চালিয়ে Platt scaling শেখে; scikit-learn-এর docs সতর্ক করে যে এতে fit ধীর হয় আর predict_proba কখনো predict-এর সঙ্গে না-ও মিলতে পারে। বড় ডেটায় এটি প্রায় পাঁচ গুণ বাড়তি fit. সম্ভাবনা লাগলে CalibratedClassifierCV আলাদা ভাগে, অথবা এমন model যার log loss সরাসরি শেখা।

Tabular ডেটা। বাজারঘরের অর্ডারের টেবিলে জেলা, courier, পেমেন্টের ধরন, পণ্যের বিভাগ: অনেক categorical feature, ভিন্ন একক, missing মান। Kernel SVM-এর জন্য সবকিছু one-hot আর scale করতে হয়, আর RBF-এর একটি γ সব feature-এর দূরত্বকে একভাবে ধরে। গাছভিত্তিক gradient boosting এসব প্রায় নিজেই সামলায়, আর অনেক প্রকাশিত তুলনা আর প্রতিযোগিতার অভিজ্ঞতায় মাঝারি থেকে বড় tabular ডেটায় সে প্রায়ই সবচেয়ে ভালো ফল দেয়; তবে এটি সব ডেটায় সত্য নয়। বিস্তারিত পর্ব ৩৬ (XGBoost, LightGBM আর CatBoost — পার্থক্য আর হাতে-কলমে) আর পর্ব ৩৮ (Tabular ডেটায় model বাছাই — tree, linear না neural, আর tuning-এর বাজেট)-এ।

নিচে বাজারঘরের তিনটি কাল্পনিক পরিস্থিতিতে ধাপে ধাপে সিদ্ধান্ত। প্রতিটিতে প্রথমে আকার আর memory হিসাব, তারপর প্রয়োজন, তারপর পছন্দ।

৯ · AI-এর যুগে — বড় ডেটার kernel কোড যাচাই

AI assistant-কে “fraud detection-এর জন্য SVM লিখে দাও” বললে প্রায়ই সে SVC() লিখে দেয়, ডেটা কত বড় না জেনেই। কোডটি ছোট নমুনায় চলে, তারপর আসল ডেটায় ঘণ্টার পর ঘণ্টা আটকে থাকে। পরিচিত ভুলগুলো:

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

• n² × ৮ বাইট নিজে হিসাব করেছি, আর n দ্বিগুণ করে fit time মেপে ঢাল দেখেছি
• সব model-এ একই γ আর C, অথবা প্রতিটির জন্য আলাদা CV, আর সেটি লিখে রেখেছি
• StandardScaler pipeline-এর ভেতরে, শুধু train-এ শেখানো
• ছোট নমুনায় পুরো K-এর সঙ্গে approximation-এর আপেক্ষিক ভুল মেপেছি
• একটি সরল baseline (linear বা boosting) একই fold-এ, কয়েকটি seed-এ তুলনা করেছি
• সম্ভাবনা লাগলে আলাদা ভাগে calibration করে reliability diagram দেখেছি
• Class আর argument-এর নাম নিজের version-এর docs-এ মিলিয়েছি, আর কোনো আসল গ্রাহকের ডেটা AI-তে পেস্ট করিনি