Kernel Trick in SVM

The Kernel Trick is one of the most important ideas in Non-Linear SVM.

If the data cannot be separated by a straight line in the original space, SVM imagines the data in a higher-dimensional space where it can be separated by a straight line. A kernel helps us do this without explicitly calculating the higher-dimensional coordinates.

---

1. Start with a Simple Problem

Consider a dataset with one feature $x$.

$x$	Class
-3	$+1$
-2	$+1$
-1	$-1$
0	$-1$
1	$-1$
2	$+1$
3	$+1$

On a number line:

Class +1        Class -1          Class +1

 ●   ●            × × ×             ●   ●

-3  -2           -1 0 1             2   3

Here:

• Class $+1$ is on both sides
• Class $-1$ is in the middle

A single straight boundary cannot separate the two classes.

So, this is a non-linear classification problem in the original space.

---

2. The Main Idea: Transform the Feature

Let us create a new feature:

$$\boxed{z=x^2}$$

This is called a feature transformation.

Now calculate $x^2$.

$x$	$z=x^2$	Class
-3	9	$+1$
-2	4	$+1$
-1	1	$-1$
0	0	$-1$
1	1	$-1$
2	4	$+1$
3	9	$+1$

Now look only at the transformed feature:

Class -1                  Class +1

 ×    ×    ×       |       ●   ●   ●   ●
 0    1    1               4   4   9   9
                   ↑
              Decision boundary

Now the classes can be separated by a straight boundary.

This is the important idea:

$$\boxed{ \text{Non-linear in original space} \rightarrow \text{Linear in transformed space} }$$

---

3. What is Feature Mapping?

We can represent the transformation as:

$$\boxed{ \phi(x)=x^2 }$$

Here:

• $x$ = original feature
• $\phi(x)$ = transformed feature

For example:

$$x=3$$

becomes:

$$\phi(3)=3^2=9$$

Similarly:

$$x=-3$$

becomes:

$$\phi(-3)=(-3)^2=9$$

---

4. But Why Do We Need the Kernel Trick?

For a simple example like:

$$\phi(x)=x^2$$

we can easily calculate the transformation.

But imagine data with:

• 100 features,
• thousands of training examples,
• very complex transformations.

The transformed feature space could have:

• thousands,
• millions,
• or even infinitely many dimensions.

Explicitly calculating all these transformed features may be difficult.

This is where the Kernel Trick becomes useful.

---

5. The Important Mathematical Idea

SVM does not always need the actual transformed coordinates.

During training, many calculations involve the dot product:

$$\phi(x_i)^T\phi(x_j)$$

Instead of explicitly calculating:

$$\phi(x_i)$$

and:

$$\phi(x_j)$$

we use a kernel function:

$$\boxed{ K(x_i,x_j)=\phi(x_i)^T\phi(x_j) }$$

This is the Kernel Trick.

---

6. A Simple Mathematical Example

Suppose we choose the feature mapping:

$$\boxed{ \phi(x)= \begin{bmatrix} x\\ x^2 \end{bmatrix} }$$

This transforms a one-dimensional input into a two-dimensional feature space.

Let's take:

$$x=2$$

Then:

$$\phi(2)= \begin{bmatrix} 2\\ 4 \end{bmatrix}$$

Now take:

$$z=3$$

Then:

$$\phi(3)= \begin{bmatrix} 3\\ 9 \end{bmatrix}$$

The dot product in the transformed space is:

$$\phi(2)^T\phi(3)$$ $$= (2)(3)+(4)(9)$$ $$=6+36$$ $$\boxed{42}$$

---

7. The Kernel Does This Directly

Instead of calculating:

$$\phi(2)$$

and:

$$\phi(3)$$

separately, we can define:

$$\boxed{ K(x,z)=xz+x^2z^2 }$$

Now substitute:

$$x=2,\qquad z=3$$ $$K(2,3) = (2)(3)+(2^2)(3^2)$$ $$=6+36$$ $$\boxed{42}$$

We get exactly the same result!

Therefore:

$$\boxed{ K(x,z)=\phi(x)^T\phi(z) }$$

---

8. Why is This Called a "Trick"?

Because we get the result of calculations in a higher-dimensional space:

$$\phi(x)$$

without explicitly creating all the transformed features.

So the SVM behaves as if it is working in a higher-dimensional space.

Original Data
     x
     │
     │
     ▼
Kernel Function
     │
     │
     ▼
Effect of Higher-Dimensional
Feature Space
     │
     ▼
Linear SVM

That is why it is called the:

$$\boxed{\text{Kernel Trick}}$$

---

9. A More Visual 2-Dimensional Example

Consider this dataset:

                ○ ○ ○ ○ ○

            ○               ○

                 ● ●
                 ● ●

            ○               ○

                ○ ○ ○ ○ ○

Suppose:

• ● = Class 0
• ○ = Class 1

The Class 0 points are in the center.

The Class 1 points surround them.

Can a straight line separate them?

$$\boxed{\text{No}}$$

---

Add a New Dimension

Suppose we calculate:

$$\boxed{ z=x_1^2+x_2^2 }$$

This measures the squared distance of a point from the origin.

Now the data is represented using:

$$(x_1,x_2,z)$$

where:

$$z=x_1^2+x_2^2$$

Points near the center have small values of $z$.

Points far from the center have large values of $z$.

Therefore, in the higher-dimensional space, it may become possible to separate the classes using a plane.

Higher-dimensional idea:

        Class 1
           ○ ○ ○

------------------------  ← Linear separating plane

           ● ●
        Class 0

When we look back at the original two-dimensional space, the boundary may appear as a:

$$\boxed{\text{circle}}$$

---

10. Common Kernel Functions

1. Linear Kernel

$$\boxed{ K(x_i,x_j)=x_i^Tx_j }$$

Used when the data is approximately linearly separable.

No complicated transformation is needed.

---

2. Polynomial Kernel

$$\boxed{ K(x_i,x_j) = (x_i^Tx_j+c)^d }$$

This allows SVM to learn polynomial-shaped boundaries.

For example:

• quadratic boundaries,
• cubic boundaries.

---

3. RBF Kernel

The Radial Basis Function (RBF) kernel is very popular.

$$\boxed{ K(x_i,x_j) = \exp(-\gamma\|x_i-x_j\|^2) }$$

It can handle complex non-linear patterns.

The basic idea is:

Points that are close together are considered more similar.

---

11. Simple Comparison

Without Kernel

Input Data
     ↓
Try to draw a straight line
     ↓
Cannot separate the classes

With Kernel

Input Data
     ↓
Kernel Function
     ↓
Conceptually map to a higher dimension
     ↓
Find a linear separating hyperplane
     ↓
Appears as a curved boundary
in the original space

---

12. The Most Important Formula

The key formula students should remember is:

$$\boxed{ K(x_i,x_j) = \phi(x_i)^T\phi(x_j) }$$

where:

• $x_i,x_j$ are original data points.
• $\phi(x)$ represents transformation into a higher-dimensional feature space.
• $K(x_i,x_j)$ calculates the dot product in that feature space.

---

Final Summary

Problem

Data cannot be separated by a straight line.

⬇️

Solution

Conceptually transform the data:

$$\boxed{x\rightarrow\phi(x)}$$

⬇️

In the New Space

Find a linear separating hyperplane.

⬇️

Kernel Trick

Instead of explicitly calculating $\phi(x)$, use:

$$\boxed{ K(x_i,x_j)=\phi(x_i)^T\phi(x_j) }$$

---

⭐ 

The Kernel Trick allows an SVM to find a linear separation in a higher-dimensional feature space without explicitly calculating the coordinates of that higher-dimensional space.

The key idea to remember:

Non-linear boundary in original space⟺Linear boundary in a transformed feature space