The kernel trick — Hinglish notes

2.4.3 · AI-ML › SVM, Naive Bayes & Probabilistic Models

WHY hume iska zaroorat hai?

WHAT hai problem? Ek linear SVM ek separating hyperplane $w^{⊤} x + b = 0$ dhundtha hai. Lekin concentric circles jaisa data (inner class vs outer ring) ko koi bhi straight line separate nahi kar sakti.

WHY lifting help karti hai? Agar hum $x_{1}^{2} + x_{2}^{2}$ (origin se distance-squared) jaisi ek feature add karein, toh inner points ko ek chotti value milti hai aur outer ring ko ek badi value — ab us nayi axis par ek flat threshold unhe perfectly separate kar deta hai.

HOW bina cost explode kiye? $n$ features par ek degree- $d$ polynomial map mein $O (n^{d})$ nayi features hoti hain. Unhe explicitly compute karna expensive hai (ya infinite-dimensional!). Kernel trick isse sidestep karti hai: SVM ka math sirf dot products $⟨ x_{i}, x_{j} ⟩$ use karta hai, toh agar hum $⟨ ϕ (x_{i}), ϕ (x_{j})⟩$ ko ek shortcut function se cheaply compute kar sakein, toh hum $ϕ (x)$ kabhi bhi nahi banaate.

Dual form: jahan dot products aate hain

Yeh kyun matter karta hai: training data sirf inner product $⟨ x_{i}, x_{j} ⟩$ ke roop mein appear hota hai. Prediction bhi purely dot products hai: $f (x) = sign (\sum_{i} α_{i} y_{i} ⟨ x_{i}, x ⟩ + b) .$

Toh har $⟨ x_{i}, x_{j} ⟩$ ko $K (x_{i}, x_{j}) = ⟨ ϕ (x_{i}), ϕ (x_{j})⟩$ se replace karo aur tumhe free mein ek nonlinear SVM mil jaata hai.

SCRATCH SE ek kernel derive karna

Chalo prove karte hain ki polynomial kernel ek bade space mein ek dot product hai. 2D inputs $x = (x_{1}, x_{2})$ , $z = (z_{1}, z_{2})$ lo aur function $K (x, z) = (x^{⊤} z)^{2} .$

Step 1 — expand karo. Kyun? Hum dekhna chahte hain ki kya yeh $ϕ (x)^{⊤} ϕ (z)$ ke roop mein factor hota hai. $(x_{1} z_{1} + x_{2} z_{2})^{2} = x_{1}^{2} z_{1}^{2} + 2 x_{1} x_{2} z_{1} z_{2} + x_{2}^{2} z_{2}^{2} .$

Step 2 — dot product ke roop mein regroup karo. Kyun? Terms ko group karo taaki har summand (function of $x$ ) $\times$ (same function of $z$ ) ho. $= (x_{1}^{2}) (z_{1}^{2}) + (2 x_{1} x_{2}) (2 z_{1} z_{2}) + (x_{2}^{2}) (z_{2}^{2}) .$

Step 3 — $ϕ$ padho. Kyun? Yeh ab literally $ϕ (x)^{⊤} ϕ (z)$ hai jahan $ϕ (x) = (x_{1}^{2}, 2 x_{1} x_{2}, x_{2}^{2}) .$

Kab ek function $K$ ek valid kernel hai? Mercer's theorem ke anusaar: tabhi jab $K$ symmetric ho aur Gram matrix $[K (x_{i}, x_{j})]$ har dataset ke liye positive semidefinite ho. PSD guarantee karta hai ki koi feature map $ϕ$ exist karti hai.

Common kernels

RBF infinite-dimensional kyun hai? $e^{2 γ x^{⊤} z}$ ko Taylor series $\sum_{k} \frac{( 2 γ x ^{⊤} z ) ^{k}}{k !}$ ke roop mein expand karo: isme har degree ke polynomial terms hain. Har degree features add karti hai, isliye $ϕ$ mein infinitely many features hain — explicitly compute karna impossible hai, kernel ke roop mein evaluate karna trivial hai. Isliye kernel trick sirf convenient nahi, balki essential hai.

Worked examples

Common mistakes (steel-manned)

Recall Feynman: ek 12 saal ke bachche ko samjhao

Socho tum ek circle ke andar red marbles aur bahar blue marbles ko alag karne ki koshish kar rahe ho, sab ek table par flat rakhe hain. Koi seedhi stick unhe split nahi kar sakti. Ab table ke beech ko pahad ki tarah upar uthao — reds oopar uthte hain, blues neeche rehte hain. Ab ek flat card unke beech slide kar sakta hai! Kernel trick ek jaadu ki ruler hai jo batata hai ki marbles uthane ke baad kitne door honge, bina kabhi pahad banaye. Tumhe answer free mein milta hai.

Recall

Kernel trick kya hai?

⟨ ϕ (x), ϕ (z)⟩

ko ek cheap function

K

se compute karna bina high-dimensional feature map

ϕ

banaye.

Kernels ko SVM mein plug in kyun kar sakte hain?

Dual SVM aur uski prediction training points ko SIRF dot products

⟨ x_{i}, x_{j} ⟩

ke through use karti hai, jise hum

K

se replace karte hain.

2D mein

K = (x^{⊤} z)^{2}

ke liye feature map bolo.

ϕ (x) = (x_{1}^{2}, 2 x_{1} x_{2}, x_{2}^{2})

Mercer's condition batao.

K

ek valid kernel hai tabhi jab woh symmetric ho aur uska Gram matrix har dataset ke liye positive semidefinite ho.

RBF kernel likho.

K (x, z) = exp (- γ ∥ x - z ∥^{2})

RBF feature space infinite-dimensional kyun hai?

Uska Taylor expansion har degree ke polynomial terms contain karta hai, jo infinitely many features add karta hai.

Bade

γ

ka RBF mein kya effect hota hai?

Similarity distance ke saath fast decay karti hai → har point isolated → overfitting / wiggly boundary.

Polynomial kernel formula aur uska feature-space size?

K = (x^{⊤} z + c)^{d}

;

O (n^{d})

size ka finite feature space.

Connections

Support Vector Machines — dual form jo dot products expose karta hai
Soft-margin SVM — jahan se $C$ aur $α_{i}$ aate hain
Mercer's Theorem — kernels ke liye validity condition
RBF Kernel — infinite-dimensional lift
Gaussian Naive Bayes — contrast: probabilistic vs margin-based
Overfitting and Regularization — $γ$ , $C$ tuning karna