SVM, Classification & Decision Boundaries: Algorithms, Math & Real-World Use

TAKEAWAYS:

• SVMs maximize the margin between classes using support vectors, making them robust to overfitting and effective in high-dimensional spaces.
• Kernel tricks (linear, polynomial, RBF) enable SVMs to classify non-linear data without explicitly transforming features.
• Soft-margin SVMs balance margin width and misclassification errors via a regularization parameter $C$.
• k-NN vs. SVM: k-NN is instance-based and sensitive to noise, while SVM learns a global decision boundary.
• Real-world use: Khalti uses SVM for fraud detection, and NEPSE applies classification to predict stock trends.

1. Classification Techniques: Overview

Classification algorithms assign labels to data points based on learned patterns. Key types:

• Supervised: Requires labeled training data (e.g., SVM, decision trees).
• Unsupervised: No labels (e.g., clustering).
• Semi-supervised: Mix of labeled/unlabeled data.

classDiagram
    class Classification {
        +Supervised: SVM, Decision Trees
        +Unsupervised: k-Means
        +Semi-Supervised: Self-Training
    }
    class SVM {
        +Maximizes Margin
        +Uses Kernels
    }
    class DecisionTree {
        +Splits on Features
        +Prone to Overfitting
    }
    Classification <|-- SVM
    Classification <|-- DecisionTree

2. Support Vector Machines (SVM): Core Concepts

2.1 Hard-Margin SVM

• Goal: Find the hyperplane that maximizes the margin between classes.
• Support Vectors: Data points closest to the hyperplane (critical for defining the boundary).
• Mathematical Formulation: For linearly separable data, solve: $$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{subject to}{y}_i(w\cdot x_i+b)\ge 1\forall i$$
  • $w$: Weight vector (normal to hyperplane).
  • $b$: Bias term.
  • $y_i$: Class label ($+1$ or $-1$).

Worked Example: Linear SVM in 2D Given dataset:

1. Plot data (IMAGE: "SVM 2D classification example" | Points colored by class).
2. Find support vectors: The two closest points to the hyperplane (e.g., $(2,3)$ and $(3,1)$).
3. Compute $w$ and $b$:
   • Use the dual formulation: $$w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i,{\alpha }_i\ge 0$$
   • Solve for ${\alpha }_i$ using quadratic programming.

2.2 Soft-Margin SVM

• Allows misclassifications via slack variables ${\xi }_i\ge 0$.
• Objective: $$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$
  • $C$: Regularization parameter (trade-off between margin width and errors).

Graph of $C$'s Effect: Caption: As $C$ increases, the model fits training data tightly but risks overfitting.

3. Kernel Trick for Non-Linear Data

When data isn’t linearly separable, SVMs use kernels to map features into higher dimensions implicitly.

Example: RBF Kernel for Circle Separation

graph LR
    A["Input Space (2D)"] -->|"RBF Kernel"| B["Feature Space (∞D)"]
    B --> C["Linear Separator"]

4. SVM vs. Other Classifiers

Worked Example: k-NN vs. SVM on Traffic Data

• Scenario: Predicting Kathmandu traffic congestion (high/low) based on time and location.
• k-NN: Classifies based on 5 nearest historical routes (sensitive to outliers like protests).
• SVM: Learns a global boundary (e.g., "congestion > 70% when time > 8 AM and location = Ring Road").
• Result: SVM generalizes better to unseen routes.

5. Real-World Applications

5.1 Fraud Detection (Khalti)

• Problem: Identify fraudulent transactions in real-time.
• Solution: SVM with RBF kernel to classify transactions as "legitimate" or "fraud."
• Why SVM?:
  • Handles high-dimensional features (e.g., transaction amount, time, location).
  • Robust to overfitting with limited labeled fraud data.

5.2 Medical Diagnosis (Nepalese Hospitals)

• Problem: Predict diabetes risk from patient records (glucose, BMI, age).
• Solution: SVM with polynomial kernel to model non-linear relationships.
• Example:

  from sklearn.svm import SVC
  model = SVC(kernel='poly', degree=3, C=1.0)
  model.fit(X_train, y_train)  # X_train: [glucose, BMI, age]
  

5.3 Stock Prediction (NEPSE)

• Problem: Classify stocks as "buy," "hold," or "sell" based on historical trends.
• Solution: SVM with RBF kernel trained on technical indicators (e.g., moving averages).
• Visualization: Caption: SVM predicts upward trend at $t=4$ based on past patterns.

6. Advantages and Limitations

When to Use SVM?

• Small to medium-sized datasets.
• Clear margin of separation exists (or can be found via kernels).
• Need for interpretability (support vectors highlight critical data).

7. Exam Tip: How to Score Full Marks

1. Define Key Terms Clearly:
   • "Support vectors are the data points closest to the decision boundary that define the margin."
2. Show Math for Hard-Margin SVM:
   • Write the primal/dual optimization problems and explain Lagrange multipliers (${\alpha }_i$).
3. Compare Algorithms:
   • Use a table (as above) and one concrete example (e.g., "k-NN fails on noisy traffic data, but SVM succeeds").
4. Kernel Trick:
   • Explain why you’d use RBF for non-linear data (e.g., "RBF implicitly maps data to infinite dimensions").
5. Real-World Tie-In:
   • Link SVM to one Nepali application (e.g., "Ncell could use SVM to classify call patterns as spam").

Common Pitfalls:

• Forgetting to mention support vectors in SVM explanations.
• Confusing soft-margin ($C$) with kernel parameters ($\gamma$ in RBF).
• Not plotting data for 2D examples (examiners expect visuals!).