Support Vector Machines: Kernels, Optimization & Classification

TAKEAWAYS:

• SVMs find the optimal hyperplane that maximizes the margin between classes, even in high-dimensional spaces.
• The kernel trick transforms data into higher dimensions without explicitly computing coordinates, enabling non-linear decision boundaries.
• SVMs are robust to overfitting due to their margin maximization principle and work well with small datasets.
• Key parameters: C (regularization), kernel choice (linear, polynomial, RBF), and gamma (for RBF) control model flexibility.
• SVMs excel in binary classification but can be extended to multi-class problems using one-vs-one or one-vs-rest strategies.
• Real-world uses include spam detection (Khalti), medical diagnosis (Nepal’s health apps), and stock prediction (NEPSE).

1. Introduction to Support Vector Machines (SVMs)

SVMs are supervised learning models used for classification and regression. Unlike neural networks or decision trees, SVMs focus on finding the best separating hyperplane between classes while maximizing the margin (distance between the hyperplane and the nearest data points, called support vectors).

Key Concepts

• Hyperplane: A decision boundary in n-dimensional space (e.g., a line in 2D, a plane in 3D).
• Support Vectors: The critical data points closest to the hyperplane that influence its position.
• Margin: The distance between the hyperplane and the nearest support vectors. SVMs aim to maximize this margin for better generalization.

Why Maximize the Margin?

A larger margin reduces the risk of misclassification on new data. Imagine classifying emails as spam (Khalti alerts) or not spam:

• A hyperplane too close to the data (small margin) may misclassify noisy points.
• A hyperplane with a wide margin is more robust to variations in the data.

2. Linear SVM: Hard Margin vs. Soft Margin

Hard Margin SVM

Assumes the data is linearly separable (no overlapping classes). The goal is to find the hyperplane where: $$w^{T}x+b=0$$ where:

• $w$ = weight vector (normal to the hyperplane),
• $b$ = bias term,
• $x$ = input feature vector.

Constraint: All points must satisfy $y_i(w^T{x}_i+b)\ge 1$ (where $y_i\in \{-1,+1\}$).

Problem: Real-world data is rarely perfectly separable. Hard margin SVMs fail if classes overlap.

Soft Margin SVM

Introduces slack variables (${\xi }_i$) to allow some misclassification. The optimization problem becomes: $$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$ subject to: $$y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

• $C$: Regularization parameter (trade-off between margin width and misclassification).
  • Small $C$: Wider margin, more misclassifications (underfitting).
  • Large $C$: Narrow margin, fewer misclassifications (risk of overfitting).

3. Kernel Trick: Handling Non-Linear Data

When data is not linearly separable, SVMs use the kernel trick to map input features into a higher-dimensional space where separation is possible.

How Kernels Work

Instead of computing the dot product $x_i\cdot x_j$ in input space, kernels compute it in a transformed space: $$K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$$ where $\varphi$ is a (possibly infinite-dimensional) transformation.

Common Kernels

Example: Classifying NEPSE stock trends (up/down) based on historical price patterns.

• A polynomial kernel might capture non-linear trends better than a linear model.

4. Dual Formulation and Optimization

The SVM optimization problem can be rewritten in its dual form using Lagrange multipliers: $$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)$$ subject to: $$0\le {\alpha }_i\le C,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

• ${\alpha }_i$: Lagrange multipliers (only support vectors have ${\alpha }_i>0$).
• The decision function becomes: $$f(x)=\text{sign}\left(\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b\right)$$

Worked Example: Binary Classification with RBF Kernel

Scenario: Predicting loan approval (yes/no) based on credit score ($x_1$) and income ($x_2$) using Nepal’s Nabil Bank data.

Data:

Steps:

1. Choose Kernel: RBF ($K(x_i,x_j)=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)$).
2. Select $C$ and $\gamma$: Start with $C=1$, $\gamma =0.1$.
3. Train SVM: Use a solver (e.g., sklearn.SVC) to find ${\alpha }_i$ and $b$.
4. Predict: For a new applicant with credit score 680 and income 3.8 lakhs: $$f(x)=\text{sign}\left(\sum {\alpha }_i{y}_{i}K(x_i,x)+b\right)$$
   • If $f(x)>0$, approve; else, reject.

Visualization:

graph TD
    A["Input Features\n(650, 3.5)"] -->|"RBF Kernel"| B["Transformed Space\n(φ(x))"]
    C["Input Features\n(550, 2.8)"] -->|"RBF Kernel"| D["Transformed Space\n(φ(x))"]
    B -->|"Hyperplane"| E["Decision Boundary"]
    D --> E
    E -->|"f(x) > 0"| F["Approved"]
    E -->|"f(x) ≤ 0"| G["Rejected"]

Key Insight: The RBF kernel implicitly maps the data into a space where a linear separator exists.

5. Multi-Class SVM

SVMs are inherently binary classifiers. For multi-class problems (e.g., Pathao ride type: bike, car, auto), use:

1. One-vs-One (OvO): Train $\frac{k(k-1)}{2}$ classifiers (e.g., 3 classes → 3 classifiers).
2. One-vs-Rest (OvR): Train $k$ classifiers (each vs. all others).

Example: Classifying Daraz product categories (electronics, fashion, groceries).

• OvO: Train "electronics vs. fashion," "electronics vs. groceries," etc.
• OvR: Train "electronics vs. (fashion + groceries)," etc.

6. SVM for Regression (SVR)

Support Vector Regression (SVR) extends SVMs to regression tasks by predicting a continuous output within a margin (ε-insensitive tube).

Optimization Problem: $$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n(|y_i-(w^T{x}_i+b)|-ϵ{)}_{+}$$

• $ϵ$: Width of the tube (controls tolerance for errors).
• $(z{)}_{+}=\max (0,z)$: Only penalizes points outside the tube.

Example: Predicting NTC electricity bill based on usage (kWh) and season.

• Train SVR on historical data to predict future bills within an acceptable error margin.

7. Advantages and Disadvantages of SVMs

8. Real-World Applications

In Nepal

1. Khalti (Digital Payments)

   • Use Case: Fraud detection (classifying transactions as legitimate or fraudulent).
   • How SVM Helps: Trained on historical transaction data with an RBF kernel to detect anomalies in spending patterns.

2. NEPSE (Stock Market Prediction)

   • Use Case: Predicting stock price movements (up/down) based on technical indicators.
   • How SVM Helps: Polynomial kernel captures non-linear relationships between indicators (e.g., moving averages, volume).

3. NTC (Electricity Load Forecasting)

   • Use Case: Predicting peak demand hours to optimize power distribution.
   • How SVM Helps: SVR models historical usage data to forecast demand within a tolerance band.

Globally

1. Google’s Image Recognition

   • Use Case: Classifying images (e.g., cats vs. dogs).
   • How SVM Helps: Early versions used SVMs with custom kernels for feature extraction.

2. WhatsApp Spam Filter

   • Use Case: Flagging spam messages.
   • How SVM Helps: Trained on labeled messages to classify new ones using text features (e.g., keyword frequency).

3. Medical Diagnosis (e.g., Cancer Detection)

   • Use Case: Classifying tumor cells as malignant or benign from MRI scans.
   • How SVM Helps: RBF kernel captures complex patterns in pixel intensities.

9. Exam Tip: How to Score Full Marks

1. Understand the Math:

   • Know the primal and dual formulations of SVM optimization.
   • Be able to derive the decision function $f(x)=\text{sign}(\sum {\alpha }_i{y}_{i}K(x_i,x)+b)$.

2. Kernel Selection:

   • Explain when to use linear, polynomial, or RBF kernels (e.g., RBF for non-linear data).
   • Relate $\gamma$ in RBF to model flexibility (high $\gamma$ = overfitting).

3. Parameter Tuning:

   • Discuss the role of $C$ (trade-off between margin and errors).
   • Mention cross-validation for selecting $C$ and kernel parameters.

4. Practical Scenarios:

   • Link SVMs to real-world problems (e.g., Khalti fraud detection, NEPSE prediction).
   • Show how to interpret support vectors in a trained model.

5. Comparison Tables:

   • Compare SVMs with logistic regression, decision trees, and neural networks in terms of:
     • Assumptions (linearity, separability),
     • Performance (small vs. large datasets),
     • Interpretability.

6. Worked Examples:

   • Solve a binary classification problem step-by-step (e.g., loan approval).
   • Plot the decision boundary for a 2D dataset using a kernel.

10. Common Pitfalls to Avoid

• Ignoring Kernel Choice: Always justify why a kernel (e.g., RBF) is suitable for the data.
• Overfitting: High $C$ or $\gamma$ leads to overfitting; use grid search to tune parameters.
• Scalability: SVMs are slow for datasets with >10,000 samples (use approximations like linear SVM).
• Feature Scaling: SVMs are sensitive to feature scales; normalize data (e.g., using StandardScaler).

11. Summary Table: SVM Variants

12. Visualizing SVM Concepts

Figure 1: Hard Margin vs. Soft Margin

graph TD
    A["Hard Margin\n(No misclassification)"] --> B["Hyperplane\nMaximizes margin"]
    C["Soft Margin\n(Allows errors)"] --> D["Hyperplane\nBalances margin & errors"]
    B -->|"All points satisfy y(w^T x + b) ≥ 1"| E["Perfect separation"]
    D -->|"Some points violate constraint"| F["Slack variables (ξ_i)"]

Caption: Hard margin fails if classes overlap; soft margin introduces slack variables.

Figure 2: Kernel Trick in Action

graph TD
    A["Original Space\n(Non-linear)"] -->|"RBF Kernel"| B["Transformed Space\n(Linear)"]
    B --> C["Hyperplane\nSeparates classes"]
    C --> D["Decision Boundary\nin original space"]

Caption: The RBF kernel maps non-linear data to a higher dimension where a linear separator exists.

Figure 3: Support Vectors in a Trained SVM

graph TD
    A["Data Points"] --> B["Support Vectors\n(α_i > 0)"]
    B --> C["Define Hyperplane"]
    D["Non-Support Vectors\n(α_i = 0)"] -->|"Ignored"| C

Caption: Only support vectors influence the decision boundary.

13. Real Picture: SVM Decision Boundary

14. Worked Example: Traffic Light Control (Nepal Context)

Problem: Optimize traffic light timings at a Kathmandu intersection to minimize wait time using SVM.

Data:

• Features: $x_1$ = vehicle count (main road), $x_2$ = pedestrian count.
• Target: $y$ = optimal green light duration (seconds).

Steps:

1. Preprocess: Normalize $x_1$ and $x_2$ (e.g., divide by max values).
2. Train SVR:
   • Kernel: RBF ($\gamma =0.5$).
   • $C=10$ (allow some errors).
3. Predict: For $x_1=45$ vehicles, $x_2=12$ pedestrians: $$\text{Green duration}=\text{SVR}(45,12)\approx 30\text{ seconds}$$ Why SVM?

• Captures non-linear relationships between traffic flow and optimal timing.
• Robust to noisy sensor data (e.g., sudden pedestrian surges).

15. Code Example: SVM in Python (Scikit-Learn)

from sklearn import svm
from sklearn.datasets import make_classification

# Generate synthetic data
X, y = make_classification(n_samples=100, n_features=2, n_classes=2, n_clusters_per_class=1)
clf = svm.SVC(kernel='rbf', C=1.0, gamma=0.7)

# Train
clf.fit(X, y)

# Predict
print(clf.predict([[1.5, 2.0]]))  # Output: [1] or [-1]

Output: The model predicts the class of a new point using the trained RBF kernel.

16. Key Formulas to Memorize

1. Decision Function: $$f(x)=\text{sign}\left(\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b\right)$$
2. RBF Kernel: $$K(x_i,x_j)=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)$$
3. Soft Margin Optimization: $$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$
4. SVR Loss: $$L_{ϵ}(y,f(x))=\max (0,|y-f(x)|-ϵ)$$

17. Common Exam Questions and Answers

Q1: Why is the kernel trick important in SVMs? A:

• Allows SVMs to handle non-linear decision boundaries without explicitly computing high-dimensional transformations.
• Kernels compute dot products in the transformed space efficiently (e.g., RBF kernel avoids explicit mapping).

Q2: How does the parameter $C$ affect SVM performance? A:

• Small $C$: Wider margin, more training errors (underfitting).
• Large $C$: Narrow margin, fewer training errors (risk of overfitting).
• Optimal $C$: Found via cross-validation (e.g., $C\in \{0.1,1,10\}$).

Q3: Compare SVM and logistic regression.

Q4: How would you classify handwritten digits (MNIST) using SVM? A:

1. Flatten images into feature vectors (e.g., 28×28 = 784 dimensions).
2. Use an RBF kernel to capture complex patterns.
3. Train a one-vs-rest SVM for 10 classes.
4. Tune $C$ and $\gamma$ via grid search.

18. Final Checklist for Exam Preparation

• Understand hard vs. soft margin and when to use each.
• Know the dual formulation and role of Lagrange multipliers.
• Memorize common kernels and their use cases.
• Practice parameter tuning ($C$, $\gamma$) on synthetic data.
• Relate SVMs to real-world problems (e.g., Khalti, NEPSE).
• Implement SVM in Python using sklearn and visualize decision boundaries.

19. Real Picture: SVM in Action (Khalti Fraud Detection)

20. Conclusion

SVMs are powerful tools for classification and regression, especially when:

• Data is high-dimensional (e.g., text, images).
• Classes are non-linearly separable (use kernels).
• You need a robust model with clear margins.

Key Takeaway: Master the math behind kernels, parameter tuning, and real-world applications to excel in exams and projects. Practice implementing SVMs on datasets like NEPSE stock data or Khalti transaction logs to solidify your understanding.