পাঠ ২৯ · ৪৫-এর মধ্যে · মডিউল ৪
Home / AI Courses / Machine Learning / Kernel trick

Kernel trick — অলৌকিক রূপান্তর

Lift to high-D without ever computing the lift
৮ মিনিট পড়া মাঝারি · Intermediate sklearn

এই পাঠে যা শিখবেন

  • কেন non-linear pattern-এ linear SVM ফেল করে — XOR উদাহরণ
  • Feature mapping $\phi$-এর intuition — low-D non-linear → high-D linear
  • Kernel function কী এবং কেন এটা $\phi$-কে "শর্টকাট" দেয়
  • RBF, polynomial, sigmoid kernel — কোথায় কোনটি
  • $\gamma$ (RBF), $d$ (polynomial) — hyperparameter-এর ভূমিকা

১ · সমস্যা — XOR-এ linear-এর মৃত্যু

৪টি বিন্দু কল্পনা করুন: $(0,0), (1,1)$ class +1; $(0,1), (1,0)$ class −1। ২-D plane-এ এদের মধ্যে দিয়ে কোনো সরল রেখা টানা যায় না — যা +1-গুলোকে এক side-এ, −1-গুলোকে অন্য side-এ রাখে। এটাই বিখ্যাত XOR সমস্যা।

Minsky ও Papert (১৯৬৯) এই সমস্যা দেখিয়ে perceptron-এর সীমা তুলে ধরেন — neural network research-এর দশক-ব্যাপী "AI winter" শুরু হয়। পরে দেখা গেল — সমাধান সরল: data-কে এমন একটা space-এ পাঠাও যেখানে linear separator আছে।

মূল ধারণা

২-D-এ যা non-linearly separable, ৩-D বা ৫-D-এ সেটা প্রায়ই linearly separable। যেমন XOR — যদি একটি নতুন feature $x_3 = x_1 \cdot x_2$ যোগ করি, তবে $(0,0,0)$ ও $(1,1,1)$ class +1; $(0,1,0)$ ও $(1,0,0)$ class -1 — এখন সমতল $x_3 = 0.5$ আলাদা করে দেয়।

২ · Feature mapping $\phi$

একটি function $\phi: \mathbb{R}^d \to \mathbb{R}^D$ (যেখানে $D \gg d$) — যা প্রতিটি data point-কে high-D-এ পাঠায়। SVM তখন সেই high-D space-এ linearly সমাধান করে। উদাহরণ:

$$\phi(x_1, x_2) = (x_1^2, \; x_2^2, \; \sqrt{2} x_1 x_2, \; \sqrt{2} x_1, \; \sqrt{2} x_2, \; 1)$$

এটি ২-D point-কে ৬-D-এ পাঠায়। এই space-এ অনেক non-linear pattern linear হয়ে যায়।

সমস্যা: $\phi(\mathbf{x})$ explicitly compute করা ব্যয়বহুল। RBF kernel-এ $\phi$-এর output অসীম-মাত্রিক — কম্পিউটারে ধরাই সম্ভব নয়।

৩ · Kernel — Magic Shortcut

L27-এ দেখেছেন SVM-এর dual form-এ data শুধুমাত্র dot-product $\mathbf{x}_i^\top \mathbf{x}_j$ হিসেবে আসে। সেটাকে $\phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)$ দিয়ে replace করলেই — high-D-এ SVM হয়ে যায়। কিন্তু আসল চমৎকারিত্ব:

Kernel function:

$$K(\mathbf{x}, \mathbf{x}') = \phi(\mathbf{x})^\top \phi(\mathbf{x}')$$

কিছু $\phi$-এর জন্য $K$ এত সরল যে — $\phi$ explicitly না জেনেই $K$ compute করা যায়। উদাহরণ — উপরের ৬-D mapping-এর জন্য:

$$K(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^\top \mathbf{x}' + 1)^2$$

চেক করে দেখুন — দু'পাশই extend করলে মিলে যায়। অর্থাৎ ৬টা multiplication-এর কাজ ১টা dot-product + ১টা square দিয়ে। এটাই kernel trick।

ভাবুন ঢাকা থেকে নিউইয়র্ক যাবেন। সরল পথ — পশ্চিম দিকে ১২,৫০০ কিমি বিমান। কিন্তু earth round, সেই দূরত্ব সরাসরি measure করতে পৃথিবীর geometry বোঝা লাগে। আপনার দরকার শুধু "শেষ দূরত্ব" — মাঝখানের ভ্রমণ-পথ নয়। Kernel trick তেমনই — high-D-এ যাত্রা না করেই শেষ "দূরত্ব" (dot-product) compute করে।

৪ · জনপ্রিয় kernel-গুলো

(ক) Linear kernel:

$$K(\mathbf{x}, \mathbf{x}') = \mathbf{x}^\top \mathbf{x}'$$

সাধারণ SVM-ই এটা — কোনো mapping নেই। Text-এ TF-IDF feature-এর সাথে দারুণ।

(খ) Polynomial kernel:

$$K(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^\top \mathbf{x}' + c)^d$$

$d$ — degree (২, ৩, ৪)। NLP, image-এ feature interaction ধরে। বড় $d$-এ overfit risk।

(গ) RBF (Gaussian) kernel — সবচেয়ে জনপ্রিয়:

$$K(\mathbf{x}, \mathbf{x}') = \exp\left(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2\right)$$

$\gamma$ — kernel-এর "width"-এর বিপরীত। বড় $\gamma$ = খুব সংকীর্ণ, প্রতিটি point নিজস্ব bubble-এ — overfit। ছোট $\gamma$ = wide, smooth — underfit।

চমৎকার তথ্য: RBF kernel-এর implicit $\phi$ অসীম-মাত্রিক (Taylor expansion-এ সব পদ আছে)। তাই RBF SVM যেকোনো smooth boundary approximate করতে পারে — universal approximator।

(ঘ) Sigmoid kernel:

$$K(\mathbf{x}, \mathbf{x}') = \tanh(\kappa \mathbf{x}^\top \mathbf{x}' + \theta)$$

Neural network-এর সাথে সাদৃশ্য। কিন্তু সব $(\kappa, \theta)$-এ Mercer-valid নয় — সাবধান।

Kernel — non-linear → linear (high-D-এ) φ: R² → R³ (or higher) আগে — 2-D non-linear × × × × × × + + + + + + + + + কোনো সরল রেখা নেই φ → add x₁²+x₂² পরে — 3-D linear linear plane × × × × × + + + + + + + এক plane দু'class আলাদা
Kernel-এর জাদু — ২-D-তে non-linear (concentric circles) ৩-D-তে linearly separable হয়ে যায়। SVM এই $\phi$ explicitly compute করে না — শুধু $K$।

৫ · Mercer's theorem — কোনটা valid kernel

যেকোনো function $K(\mathbf{x}, \mathbf{x}')$-কে kernel বলা যায় না। Valid kernel হওয়ার শর্ত (Mercer ১৯০৯):

  • Symmetric: $K(\mathbf{x}, \mathbf{x}') = K(\mathbf{x}', \mathbf{x})$।
  • Positive semi-definite: যেকোনো finite set-এ Gram matrix $K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)$ PSD।

যদি এই শর্ত পূরণ হয় — তবে $K$-এর জন্য কোনো না কোনো $\phi$ existence guaranteed (সম্ভবত অসীম-মাত্রিক)। সেটাই Mercer-এর গ্যারান্টি — গণিতবিদরা $\phi$ না দেখিয়েই বলে দিতে পারেন।

৬ · scikit-learn-এ kernel ব্যবহার

Python · sklearn 
import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_circles
from sklearn.model_selection import cross_val_score

# concentric circle data — purely non-linear
X, y = make_circles(n_samples=300, noise=0.1,
                    factor=0.4, random_state=0)

# linear vs RBF
for kernel in ["linear", "poly", "rbf"]:
    if kernel == "poly":
        clf = SVC(kernel=kernel, degree=3, C=1)
    else:
        clf = SVC(kernel=kernel, C=1)
    score = cross_val_score(clf, X, y, cv=5).mean()
    print(f"{kernel:>7} kernel: CV accuracy = {score:.3f}")

    


    

      Linear kernel এ accuracy প্রায় ০.৫০ (random) — কারণ circle-এর data linearly inseparable। RBF এ ০.৯৫+, polynomial মাঝামাঝি। এটাই kernel-এর শক্তি।
    


    
৭ · RBF-এর $\gamma$ ও $C$ — দুই dial


    
    
      
  • ছোট $\gamma$: kernel wide — neighbor influence দূর পর্যন্ত — smooth boundary, underfit risk।
    • 
      
  • বড় $\gamma$: kernel narrow — প্রতিটি training point নিজস্ব dome — sharp boundary, overfit risk।
    • 
      
  • $C$ ও $\gamma$ একসাথে tune: grid: $\{C\} \times \{\gamma\}$ — log-scale।
    • 
    


    

      

        
        Python · sklearn
      

      
from sklearn.model_selection import GridSearchCV

param_grid = {
    "C":     [0.1, 1, 10, 100],
    "gamma": [0.01, 0.1, 1, 10],
}
gs = GridSearchCV(SVC(kernel="rbf"), param_grid,
                  cv=5, n_jobs=-1)
gs.fit(X, y)
print(f"best (C, gamma): {gs.best_params_}")
print(f"best CV score: {gs.best_score_:.3f}")

      

        
        
      

      

    


    
৮ · কখন কোন kernel?

    
    
      
  • Linear: high-dim sparse (text TF-IDF, ১০০K+ feature, ১M sample)।
    • 
      
  • RBF: medium-dim dense (১০-১০০ feature, ১K-১০K sample) — default first try।
    • 
      
  • Polynomial (d=2,3): NLP, যেখানে feature-interaction জরুরি কিন্তু RBF overfit।
    • 
      
  • Custom kernel: string kernel (DNA), graph kernel — domain-specific।
    • 
    


    

      RBF-এর computational cost — $O(n^2)$ training, $O(n_{sv} \cdot d)$ inference। ১০০K sample-এর বেশি হলে SVM-RBF practical না — তখন XGBoost বা NN ভাল।
    


  


  

    
    
  


  
  

    
 ভাবনার প্রশ্ন

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        RBF kernel-এর implicit feature space "অসীম-মাত্রিক" — এটা কী মানে এবং কেন overfitting হয় না?
      
      

        

          এই প্রশ্নের উত্তর kernel theory-র সবচেয়ে সুন্দর insights-এর একটি — অসীম capacity, তবু practical regularization।
        

        

          "অসীম-মাত্রিক" — গাণিতিক অর্থ:
        

        

          RBF kernel: $K(\mathbf{x}, \mathbf{x}') = e^{-\gamma \|\mathbf{x} - \mathbf{x}'\|^2}$। Taylor expansion করলে:
        

        

          $$e^{-\gamma\|\mathbf{x}-\mathbf{x}'\|^2} = e^{-\gamma\|\mathbf{x}\|^2}e^{-\gamma\|\mathbf{x}'\|^2}\sum_{k=0}^{\infty}\frac{(2\gamma \mathbf{x}^\top\mathbf{x}')^k}{k!}$$
        

        
    
          
  • প্রতিটি $k$-th term-এ data-এর $k$-degree polynomial appears।
    • 
          
  • সব degree-এ feature implicitly থাকে — অর্থাৎ $\phi(\mathbf{x})$-এর সব polynomial coefficient।
    • 
          
  • Hilbert space (অসীম-মাত্রিক)।
    • 
        

        

          Naive expectation: অসীম capacity = অবশ্যই overfit। সব training point মুখস্থ করতে কোনো বাধা নেই।
        

        

          কেন তা ঘটে না — তিনটি reason:
        

        

          (১) Norm-এ regularization:
        

        
    
          
  • SVM objective: $\tfrac{1}{2}\|\mathbf{w}\|_{\mathcal{H}}^2$ — Hilbert space-এর norm।
    • 
          
  • $\mathbf{w} = \sum_i \alpha_i y_i \phi(\mathbf{x}_i)$ — তাই $\|\mathbf{w}\|^2 = \sum_{i,j} \alpha_i \alpha_j y_i y_j K(\mathbf{x}_i, \mathbf{x}_j)$।
    • 
          
  • Norm minimization = "smoothest" function in RKHS।
    • 
        

        

          (২) Effective dimension:
        

        
    
          
  • VC dimension formal-এ অসীম।
    • 
          
  • কিন্তু margin-bound: effective $\leq R^2/\gamma_{\text{margin}}^2$।
    • 
          
  • "Available" capacity finite — data-এর geometry-নির্ভর।
    • 
        

        

          (৩) Representer theorem:
        

        
    
          
  • Solution সবসময় training point-গুলোর span-এ থাকে — মোট $n$-D subspace।
    • 
          
  • "অসীম" capacity-এ access নেই — কেবল $n$-D-এর।
    • 
        

        

          $\gamma$-এর role:
        

        
    
          
  • $\gamma$ বড় → kernel narrow → প্রতিটি SV নিজস্ব tiny dome → Gram matrix প্রায় identity → effective overfit।
    • 
          
  • $\gamma$ ছোট → wide → SVs-এর influence বহুদূর → smooth function।
    • 
          
  • তাই $\gamma$ tune করা = capacity control।
    • 
        

        

          Connection to neural networks:
        

        
    
          
  • Wide neural network, NTK regime — RBF-like kernel।
    • 
          
  • ২০১৮-পরবর্তী research দেখায় SVM-RBF আর ultra-wide NN-এ similar inductive bias।
    • 
          
  • "Implicit regularization" — DL-এও এটাই deep mystery।
    • 
        

        

          মূল উপলব্ধি: "অসীম-মাত্রিক" ভয়ংকর শোনালেও — norm-এ regularization এবং representer theorem effective capacity finite রাখে। এটাই kernel methods-এর elegance: theoretically powerful, practically tame। আজকের NN আজও এই insight-এর dance করছে।
        

      

    


    

      
        প্র ০২
        Kernel trick শুধু SVM-এ নয় — অন্য কোথায় kernel ব্যবহার হয়? "Kernelization" সাধারণ কৌশল কী?
      
      

        

          চমৎকার চিন্তা — kernel trick একটি general algorithmic trick। যেকোনো algorithm যা data-কে শুধু dot-product হিসেবে access করে — সেটা kernelize করা যায়।
        

        

          Kernelization recipe:
        

        
    
          
  1. Algorithm-এ data কোথায় dot-product হিসেবে appear করে identify।
    2. 
          
  2. প্রতিটি $\mathbf{x}^\top \mathbf{x}'$ → $K(\mathbf{x}, \mathbf{x}')$।
    3. 
          
  3. Algorithm এখন non-linear — কোনো explicit $\phi$ দরকার নেই।
    4. 
        

        

          (১) Kernel PCA (Schölkopf et al., ১৯৯৮):
        

        
    
          
  • PCA — covariance-এর eigen-decomposition।
    • 
          
  • Kernel PCA — Gram matrix-এর eigen-decomposition।
    • 
          
  • Non-linear dimensionality reduction।
    • 
          
  • Manifold unfold করতে ব্যবহার।
    • 
        

        

          (২) Kernel Ridge Regression:
        

        
    
          
  • Ridge: $\hat{\mathbf{w}} = (X^\top X + \alpha I)^{-1} X^\top y$।
    • 
          
  • Kernel Ridge: $\hat{\boldsymbol{\alpha}} = (K + \alpha I)^{-1} y$।
    • 
          
  • Non-linear regression। Gaussian process-এর সাথে close।
    • 
        

        

          (৩) Gaussian Process:
        

        
    
          
  • Bayesian non-parametric regression।
    • 
          
  • Kernel = covariance function।
    • 
          
  • Function-space-এ posterior।
    • 
          
  • BO (Bayesian optimization)-এ ব্যবহৃত।
    • 
        

        

          (৪) Kernel k-Means:
        

        
    
          
  • K-means-এ centroid-distance — dot-product-এর term।
    • 
          
  • Kernelize → non-linear cluster shape।
    • 
          
  • Spectral clustering-এর কাছাকাছি।
    • 
        

        

          (৫) Kernel Perceptron:
        

        
    
          
  • Perceptron update — data dot-product।
    • 
          
  • Kernelize → non-linear perceptron।
    • 
          
  • Online learning।
    • 
        

        

          (৬) Kernel CCA (Canonical Correlation):
        

        
    
          
  • দু'টি view-এর relation ধরে।
    • 
          
  • Multimodal learning।
    • 
        

        

          (৭) Kernel-based two-sample test (MMD):
        

        
    
          
  • Maximum Mean Discrepancy — দু'টি distribution-এর kernel-distance।
    • 
          
  • Domain adaptation, GAN evaluation-এ ব্যবহার।
    • 
        

        

          Modern resurgence:
        

        
    
          
  • Random Fourier features (Rahimi-Recht, ২০০৭) — kernel computation $O(n^2)$ থেকে $O(nd)$ approximate।
    • 
          
  • Neural Tangent Kernel (NTK) — wide NN ≈ kernel method।
    • 
          
  • Transformer attention — soft-kernel আকারে interpret করা যায়।
    • 
        

        

          সীমা:
        

        
    
          
  • $O(n^2)$ Gram matrix — million-sample-এ inefficient।
    • 
          
  • Inference-এ সব support vector কম্পিউট — slow।
    • 
          
  • Hyperparameter sensitive।
    • 
          
  • Categorical/structured data-এ kernel design কঠিন (string kernel exception)।
    • 
        

        

          মূল উপলব্ধি: Kernel trick একটি "linguistic shift" — algorithm-কে dot-product-এর ভাষায় লিখলে, যেকোনো similarity function-এ generalize করা যায়। আজকের attention mechanism-ও এই lineage-এর — query-key dot-product-ই কর্নেল-সদৃশ similarity score।
        

      

    


    

      
        প্র ০৩
        Kernel methods বনাম Deep learning — কোন situation-এ আজও SVM-RBF Deep net-কে হারায়?
      
      

        

          ২০১২-এর AlexNet-এর পর "DL সর্বত্র জিতে" এই narrative প্রভাবশালী। কিন্তু বাস্তবতা সূক্ষ্মতর — kernel methods আজও কিছু niche-এ unbeaten।
        

        

          SVM-RBF still wins:
        

        

          (১) ছোট sample, high feature dim:
        

        
    
          
  • Bioinformatics: ১০০ patient, ১০,০০০ gene expression।
    • 
          
  • Drug discovery: ৫০০ molecule, ১,০০০ descriptor।
    • 
          
  • Material science।
    • 
          
  • DL এ data hunger; kernel-এ regularization built-in।
    • 
        

        

          (২) Tabular structured data (small-medium):
        

        
    
          
  • < ১০K row, < ১০০ feature।
    • 
          
  • SVM-RBF, XGBoost competitive — DL সাধারণত কম performant।
    • 
          
  • সর্বশেষ benchmark (Grinsztajn et al., ২০২২): "Trees beat NN on tabular"।
    • 
        

        

          (৩) Reliable uncertainty:
        

        
    
          
  • Gaussian process — kernel-based — calibrated uncertainty।
    • 
          
  • DL উপায় (MC dropout, deep ensemble) ব্যয়বহুল ও কম reliable।
    • 
          
  • BO, active learning-এ GP standard।
    • 
        

        

          (৪) Theoretical guarantees:
        

        
    
          
  • SVM-এ generalization bound formal।
    • 
          
  • Convex objective — global optimum।
    • 
          
  • DL-এ এমন guarantee নেই।
    • 
        

        

          (৫) Domain-specific kernel:
        

        
    
          
  • Graph kernel — molecular property prediction।
    • 
          
  • String kernel — DNA/protein sequence।
    • 
          
  • Tree kernel — parse tree similarity।
    • 
        

        

          (৬) Edge / embedded:
        

        
    
          
  • Inference-এ ৫০ KB memory।
    • 
          
  • Deployment to microcontroller।
    • 
        

        

          (৭) Anomaly detection:
        

        
    
          
  • One-class SVM আজও strong baseline।
    • 
          
  • Data-poor failure detection।
    • 
        

        

          DL clearly wins:
        

        
    
          
  • Image: ImageNet-scale data + GPU।
    • 
          
  • NLP: massive corpus + transformer।
    • 
          
  • Speech, video — multimodal large-scale।
    • 
          
  • Generative tasks।
    • 
        

        

          Hybrid approach (modern):
        

        
    
          
  • Pre-trained DL embedding + linear/SVM classifier — best of both worlds।
    • 
          
  • BERT embed + LinearSVC — text classification-এর strong baseline।
    • 
          
  • Vision feature (ResNet penultimate) + RBF SVM — small-data-এ ভাল।
    • 
        

        

          Bangladesh AI startup-এর জন্য lesson:
        

        
    
          
  • ছোট label budget? — kernel + transfer learning embedding।
    • 
          
  • Tabular fraud/credit? — XGBoost first, SVM challenger।
    • 
          
  • Image/text-এ scale চাইলে — pre-trained model + fine-tune।
    • 
          
  • "DL সবসময় best" — outdated belief।
    • 
        

        

          মূল উপলব্ধি: Hype চক্রে "old methods dead" narrative ভ্রান্তিকর। প্রতিটি family-র নিজ niche আছে। ভাল ML engineer choice তাঁর data-r geometry-র সাথে match করেন — fashion-এর সাথে নয়। SVM আজও defensible, কখনো optimal — ভুলে যাওয়ার মত technique নয়।
        

      

    


    

      
        প্র ০৪
        "Curse of kernelization" — large-scale-এ kernel SVM ব্যবহার্যতা হারায়। কী practical workaround আছে?
      
      

        

          একদম সঠিক observation। Kernel SVM-এর scaling — তার সবচেয়ে দুর্বল দিক। কিন্তু গত ২০ বছরে অনেক workaround এসেছে।
        

        

          সমস্যার নাটক:
        

        
    
          
  • Gram matrix $K \in \mathbb{R}^{n \times n}$ — $n = 1$M হলে $10^{12}$ entry — ৪ TB memory!
    • 
          
  • Training $O(n^2)$ থেকে $O(n^3)$ — million-row-এ ঘণ্টার পর ঘণ্টা।
    • 
          
  • Inference $O(n_{sv})$ — $n_{sv}$ অনেক হলে slow।
    • 
        

        

          (১) Stochastic / online SVM:
        

        
    
          
  • SGDClassifier(loss="hinge") — primal-এ SGD।
    • 
          
  • $O(n)$ scaling। কিন্তু linear-only।
    • 
          
  • Pegasos algorithm (Shalev-Shwartz, ২০০৭)।
    • 
        

        

          (২) Random Fourier features (RFF):
        

        
    
          
  • Rahimi-Recht (২০০৭, NeurIPS test-of-time award)।
    • 
          
  • RBF kernel ≈ random projection + cos/sin।
    • 
          
  • $\phi_{RFF}(\mathbf{x}) \in \mathbb{R}^D$ explicit, $D \ll n$।
    • 
          
  • Linear SVM on $\phi_{RFF}(\mathbf{x})$ ≈ RBF SVM।
    • 
          
  • Million-row scalable।
    • 
        

        

          (৩) Nyström approximation:
        

        
    
          
  • $n$ point থেকে $m$ landmark random সেলেক্ট।
    • 
          
  • $K \approx C M^{-1} C^\top$ যেখানে $C \in \mathbb{R}^{n \times m}$।
    • 
          
  • $O(nm^2)$ — fast, memory-friendly।
    • 
          
  • Williams-Seeger (২০০১)।
    • 
        

        

          (৪) Subsampling:
        

        
    
          
  • Train kernel SVM on random ১০% — accuracy slight drop, time ১০× faster।
    • 
          
  • "Core-set" selection — important point ধরে।
    • 
        

        

          (৫) Approximate kernels:
        

        
    
          
  • FastFood (Le et al., ২০১৩) — $O(n d \log d)$।
    • 
          
  • Orthogonal random feature।
    • 
        

        

          (৬) Distributed training:
        

        
    
          
  • ThunderSVM (GPU)।
    • 
          
  • LIBSVM-MPI।
    • 
          
  • Spark MLlib LinearSVM।
    • 
        

        

          (৭) GPU acceleration:
        

        
    
          
  • cuML SVM (RAPIDS) — sklearn API।
    • 
          
  • ১০-৫০× speedup।
    • 
        

        

          (৮) Replace with tree ensemble:
        

        
    
          
  • XGBoost, LightGBM — non-linear, scalable।
    • 
          
  • Practical সমাধান million-row tabular-এ।
    • 
        

        

          (৯) Replace with neural network:
        

        
    
          
  • Wide network ≈ kernel।
    • 
          
  • SGD + GPU — natural scaling।
    • 
        

        

          Practical decision tree:
        

        
    
          
  • $n < 10$K: full kernel SVM।
    • 
          
  • $n \in [10$K, $100$K]: Nyström বা RFF + LinearSVM।
    • 
          
  • $n > 100$K: SGD-Hinge (linear), XGBoost, NN।
    • 
          
  • Streaming data: online SGD।
    • 
        

        

          Bangladesh-এর reality:
        

        
    
          
  • Telecom CDR — billion records — RFF + Linear।
    • 
          
  • Hospital EMR — ১০K — pure kernel SVM ভাল।
    • 
          
  • e-commerce reviews — million — SGD-hinge।
    • 
        

        

          মূল উপলব্ধি: "Kernel SVM doesn't scale" — একটি half-truth। RFF, Nyström, GPU, online SGD — অনেক escape hatch। কিন্তু মূলত: scaling চাইলে — kernel-এর elegance ছেড়ে approximation মেনে নিতে হয়। এটাই "Vapnik vs Hinton" debate-এর core: theoretical purity বনাম empirical scale।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হিসাব করুন: $\mathbf{x} = (1, 2)$, $\mathbf{x}' = (3, 1)$। RBF kernel-এ $\gamma = 0.5$ হলে $K(\mathbf{x}, \mathbf{x}')$ কত?
        
    
          
          
    
            
      
              
    • $\|\mathbf{x} - \mathbf{x}'\|^2 = (1-3)^2 + (2-1)^2 = 4 + 1 = 5$।
      • 
              
    • $K = e^{-0.5 \cdot 5} = e^{-2.5} \approx 0.0821$।
      • 
              
    • Interpretation: দু'টি point মাঝারি দূরে — kernel score ছোট।
      • 
            
    
          
    
        
    
      
    2. 

      
  2. 
        NumPy-তে চেষ্টা: RBF kernel matrix নিজে compute করুন এবং sklearn-এর সাথে match করান।
        
    
          
          
    
            
    import numpy as np
from sklearn.metrics.pairwise import rbf_kernel

X = np.array([[1, 2], [3, 1], [0, 0]])
gamma = 0.5

# নিজে
diffs = X[:, None, :] - X[None, :, :]
sq = np.sum(diffs ** 2, axis=-1)
K_manual = np.exp(-gamma * sq)

# sklearn
K_sklearn = rbf_kernel(X, gamma=gamma)

print("manual:\n", K_manual)
print("\nsklearn:\n", K_sklearn)
print("\nmatch:", np.allclose(K_manual, K_sklearn))
    
          
    
        
    
      
    3. 

      
  3. 
        ভাবুন: Daraz-এ user-product recommendation-এ আপনি similarity score চান। কোন kernel বাছবেন এবং কেন?
        
    
          
          
    
            
      
              
    • Cosine kernel ($\mathbf{x}^\top \mathbf{x}' / \|\mathbf{x}\|\|\mathbf{x}'\|$) — purchase history sparse vector-এ আদর্শ; magnitude-invariant (heavy buyer-এর সাথে light buyer compare)।
      • 
              
    • Linear kernel — user/product embedding যদি pre-normalized।
      • 
              
    • RBF — সাধারণত অপ্রয়োজনীয় recommendation-এ; cosine simpler ও interpretable।
      • 
              
    • Domain kernel — "category overlap" custom kernel — Bangladesh fashion vs electronics।
      • 
              
    • Practice: matrix factorization (SVD/ALS) + কর্নেল pre-train embedding।
      • 
            
    
          
    
        
    
      
    4. 
    

  


  
  

    
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

    

    

      কোড রানার কাজ না করলে? Google Colab ব্যবহার করুন।
    

  








  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 পূর্ববর্তী পাঠ

    
পাঠ ২৮ · Soft-margin SVM