Support Vector Machines Svm Kernel Classifiers

# Support Vector Machines: SVM & Kernel Classifiers

## Introduction & Motivation

Support Vector Machines: maximum margin linear classifier. Non-linear via kernel trick. Hard or soft margin; C parameter controls trade-off. Applications: classification, regression, anomaly detection.

Motivation: Optimal separating hyperplane; theoretical guarantees.

Applications: Classification, nonlinear problems.

---

## Core Concepts & Theory

### Maximum Margin

Distance between hyperplane and nearest points.

### Support Vectors

Training points that define margin.

### Kernel Trick

Implicit high-dimensional feature space.

---

## Mathematical Formulation

SVM objective (primal):
$$\min_{w, b} \frac{1}{2}\|w\|^2 + C\sum_i \max(0, 1 - y_i(w^T\phi(x_i) + b))$$

SVM objective (dual):
$$\max_{\alpha} \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j k(x_i, x_j)$$

Decision function:
$$f(x) = ext{sign}\left(\sum_i \alpha_i y_i k(x_i, x) + b ight)$$

---

## Advanced Theory & Extensions

### One-Class SVM

Anomaly detection; outlier detection.

### SVM Regression

ε-insensitive loss.

### Multi-class SVM

One-vs-Rest or One-vs-One.

---

## Computational Considerations

Training: O(N²) to O(N³) depending on solver.

Prediction: O(support_vectors·feature_dim).

Kernel computation: O(feature_dim) or O(feature_dim²).

---

## Practical Implementation Strategies

### Kernel Selection

Linear, RBF, polynomial; domain choice.

### Hyperparameter Scaling

Normalize features; affects kernel.

### Soft Margin

C parameter; outlier tolerance.

---

## Benchmark Datasets & Evaluation

Binary Classification: Cancer diagnosis.

Multi-class: Iris, handwriting recognition.

Imbalanced: Different class weights.

---

## Key Challenges & Limitations

### Computational Cost

O(N³) training; large datasets problematic.

### Kernel Selection

Manual choice; sensitive to performance.

### Interpretability

Black-box; support vector explanation only.

---

## Hyperparameter Tuning

C (regularization): 0.001-1000; soft margin trade-off.

Kernel: Linear, RBF, polynomial; domain-specific.

Gamma (RBF): 0.0001-10; kernel width.

---

## Real-World Applications & Case Studies

Text Classification: Document categorization.

Image Recognition: Image classification tasks.

Anomaly Detection: Outlier/novelty detection.

---

## Integration with Other Methods

SVM + Ensemble → voting classifier.

SVM + Feature Selection → dimensionality reduction.

---

## Summary & Key Takeaways

Support Vector Machines via maximum margin and kernel methods enable robust nonlinear classification with strong theoretical guarantees.

Principles:
1. Margin: maximum distance.
2. Support vectors: boundary-defining points.
3. Kernel trick: implicit feature space.
4. Soft margin: tolerance for errors.
5. Duality: efficient optimization.

---

---

## Appendix: Practical Labs

### Lab 1: Linear SVM Margin

import numpy as np

def compute_svm_margin(w, X, y):
 """Compute SVM margin"""
 # Distances to hyperplane
 distances = np.abs(X @ w) / (np.linalg.norm(w) + 1e-8)
 
 # Margin: minimum distance to support vectors
 margins = (y * (X @ w)) / (np.linalg.norm(w) + 1e-8)
 margin = np.min(margins)
 
 return margin

# Test
np.random.seed(42)
w = np.random.randn(10)
X = np.random.randn(100, 10)
y = np.random.choice([-1, 1], 100)

margin = compute_svm_margin(w, X, y)

assert np.isfinite(margin), "Margin finite"
print("✓ SVM margin working")

if __name__ == "__main__":
 print("Lab 1: SVMMargin - PASSED")

### Lab 2: Kernel Trick

import numpy as np

def rbf_kernel(X1, X2, gamma=0.1):
 """RBF kernel for SVM"""
 distances_sq = np.sum((X1[:, None, :] - X2[None, :, :]) ** 2, axis=2)
 K = np.exp(-gamma * distances_sq)
 return K

# Test
np.random.seed(42)
X1 = np.random.randn(20, 5)
X2 = np.random.randn(15, 5)

K = rbf_kernel(X1, X2)

assert K.shape == (20, 15), "Kernel shape"
assert np.all(K >= 0) and np.all(K <= 1), "Kernel in [0,1]"
print("✓ RBF kernel working")

if __name__ == "__main__":
 print("Lab 2: RBFKernel - PASSED")

### Lab 3: Support Vector Identification

import numpy as np

def identify_support_vectors(alpha, tolerance=1e-5):
 """Identify support vectors from dual solution"""
 # Support vectors: non-zero alpha
 support_vectors = np.where(np.abs(alpha) > tolerance)[0]
 
 # Margin support vectors: 0 < alpha < C (assuming C implicit)
 # Margin vectors: 0 < alpha_i < 1 (assuming C=1)
 margin_vectors = np.where((alpha > tolerance) & (alpha < 1 - tolerance))[0]
 
 return support_vectors, margin_vectors

# Test
np.random.seed(42)
alpha = np.random.rand(100) * 0.5 # Random alphas in [0, 0.5]

support_vectors, margin_vectors = identify_support_vectors(alpha)

assert len(support_vectors) >= 0, "Support vectors found"
assert len(margin_vectors) <= len(support_vectors), "Margin subset"
print("✓ Support vector identification working")

if __name__ == "__main__":
 print("Lab 3: SupportVectors - PASSED")

### Lab 4: Hinge Loss

import numpy as np

def hinge_loss(y_true, y_pred, C=1.0):
 """Compute SVM hinge loss"""
 # Margin violations
 losses = np.maximum(0, 1 - y_true * y_pred)
 
 # Average loss
 avg_loss = np.mean(losses)
 
 # Regularization (implicit in the problem)
 regularization = 0 # L2 on weights handled separately
 
 total_loss = avg_loss + regularization
 
 return total_loss

# Test
np.random.seed(42)
y_true = np.random.choice([-1, 1], 100)
y_pred = np.random.randn(100)

loss = hinge_loss(y_true, y_pred)

assert loss >= 0, "Loss non-negative"
assert np.isfinite(loss), "Loss finite"
print("✓ Hinge loss working")

if __name__ == "__main__":
 print("Lab 4: HingeLoss - PASSED")