xbe.at

Machine learning / Classification and clustering

Response:

8 min read, 17 sections

Contents
  1. The Kernel Trick Fundamentals
  2. Mathematical Foundation of Kernels
  3. Implementing Custom Kernel SVM
  4. Support Vector Optimization
  5. Feature Space Transformation
  6. Response:
  7. Decision Boundary Construction
  8. Real-world Example: Nonlinear Classification
  9. Results for Nonlinear Classification
  10. Kernel Selection and Parameter Tuning
  11. Memory Efficient Implementation
  12. Multi-class SVM Strategy
  13. Response:
  14. Real-world Example: Image Classification
  15. Advanced Kernel Operations
  16. Performance Analysis and Visualization
  17. Additional Resources

The Kernel Trick Fundamentals

The kernel trick enables Support Vector Machines to operate in high-dimensional feature spaces without explicitly computing the coordinates of data points in that space. This transformation allows SVMs to find nonlinear decision boundaries by implicitly mapping input data to higher dimensions.

import numpy as np

def linear_kernel(x1, x2):
    return np.dot(x1, x2)

def polynomial_kernel(x1, x2, degree=3):
    return (1 + np.dot(x1, x2)) ** degree

def rbf_kernel(x1, x2, gamma=0.1):
    return np.exp(-gamma * np.linalg.norm(x1 - x2) ** 2)

Mathematical Foundation of Kernels

The kernel function represents an inner product in the transformed feature space, allowing efficient computation without explicit transformation. This is expressed through Mercer's theorem and the kernel matrix properties.

# Mathematical representation of kernel function
"""
$$K(x,y) = \langle \phi(x), \phi(y) \rangle$$

where:
$$\phi: \mathcal{X} \rightarrow \mathcal{H}$$ 
is the mapping from input space to feature space
"""

def compute_kernel_matrix(X, kernel_func):
    n_samples = X.shape[0]
    K = np.zeros((n_samples, n_samples))
    for i in range(n_samples):
        for j in range(n_samples):
            K[i,j] = kernel_func(X[i], X[j])
    return K

Implementing Custom Kernel SVM

A complete implementation of a Support Vector Machine classifier using custom kernels, showcasing the core optimization problem and decision function computation for binary classification tasks.

class CustomKernelSVM:
    def __init__(self, kernel='rbf', C=1.0, max_iter=1000):
        self.kernel = kernel
        self.C = C
        self.max_iter = max_iter
        self.alpha = None
        self.support_vectors = None
        
    def kernel_function(self, x1, x2):
        if self.kernel == 'rbf':
            return rbf_kernel(x1, x2)
        elif self.kernel == 'linear':
            return linear_kernel(x1, x2)
        return polynomial_kernel(x1, x2)

Support Vector Optimization

The optimization process in SVM involves finding the optimal hyperplane by solving the dual optimization problem, which maximizes the margin while minimizing classification errors through quadratic programming.

def fit(self, X, y):
    n_samples = X.shape[0]
    K = np.zeros((n_samples, n_samples))
    
    # Compute kernel matrix
    for i in range(n_samples):
        for j in range(n_samples):
            K[i,j] = self.kernel_function(X[i], X[j])
    
    # Solve quadratic programming problem
    from scipy.optimize import minimize
    
    def objective(alpha):
        return 0.5 * np.sum((alpha * y).reshape(-1,1) * 
               (alpha * y) * K) - np.sum(alpha)
    
    constraints = {'type': 'eq', 'fun': lambda x: np.sum(x * y)}
    bounds = [(0, self.C) for _ in range(n_samples)]
    
    result = minimize(objective, np.zeros(n_samples), 
                     bounds=bounds, constraints=constraints)
    self.alpha = result.x

Feature Space Transformation

The kernel function implicitly maps data points to a higher-dimensional feature space where linear separation becomes possible, enabling the SVM to capture complex nonlinear relationships in the original input space.

import matplotlib.pyplot as plt

def visualize_feature_space_transformation(X, y):
    # Original space
    plt.figure(figsize=(12, 5))
    plt.subplot(121)
    plt.scatter(X[y==1][:,0], X[y==1][:,1], c='b', label='Class 1')
    plt.scatter(X[y==-1][:,0], X[y==-1][:,1], c='r', label='Class -1')
    plt.title('Original Space')
    
    # Transformed feature space using RBF kernel
    K = np.zeros((X.shape[0], X.shape[0]))
    for i in range(X.shape[0]):
        for j in range(X.shape[0]):
            K[i,j] = rbf_kernel(X[i], X[j])
    
    from sklearn.decomposition import PCA
    pca = PCA(n_components=2)
    X_transformed = pca.fit_transform(K)
    
    plt.subplot(122)
    plt.scatter(X_transformed[y==1][:,0], X_transformed[y==1][:,1], 
               c='b', label='Class 1')
    plt.scatter(X_transformed[y==-1][:,0], X_transformed[y==-1][:,1], 
               c='r', label='Class -1')
    plt.title('Transformed Feature Space')
    plt.tight_layout()
    plt.show()

[Continuing with the remaining slides...]

Response:

Decision Boundary Construction

The decision boundary in kernel SVMs is constructed using the support vectors and their corresponding weights, creating a nonlinear separator in the original input space through the kernel mapping and optimization of the dual form.

def decision_function(self, X):
    y_pred = np.zeros(X.shape[0])
    for i in range(X.shape[0]):
        s = 0
        for alpha, sv, sv_y in zip(self.alpha, 
                                 self.support_vectors, 
                                 self.support_vector_labels):
            s += alpha * sv_y * self.kernel_function(X[i], sv)
        y_pred[i] = s + self.bias
    return y_pred

Real-world Example: Nonlinear Classification

Implementation of kernel SVM for a real-world nonlinear classification problem, demonstrating data preprocessing, model training, and evaluation on a complex dataset with overlapping classes.

import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

# Generate nonlinear dataset
X, y = make_moons(n_samples=300, noise=0.3, random_state=42)
X = StandardScaler().fit_transform(X)
X_train, X_test, y_train, y_test = train_test_split(X, y, 
                                                    test_size=0.2, 
                                                    random_state=42)

# Initialize and train custom SVM
svm = CustomKernelSVM(kernel='rbf', C=1.0)
svm.fit(X_train, 2*y_train - 1)  # Convert to {-1, 1} labels

Results for Nonlinear Classification

# Evaluate model performance
from sklearn.metrics import accuracy_score, classification_report

y_pred = np.sign(svm.decision_function(X_test))
accuracy = accuracy_score((2*y_test - 1), y_pred)

print(f"Accuracy: {accuracy:.4f}")
print("\nClassification Report:")
print(classification_report((2*y_test - 1), y_pred))

# Visualize decision boundary
def plot_decision_boundary(X, y, model, title):
    h = 0.02
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    Z = model.decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    plt.contourf(xx, yy, Z, cmap=plt.cm.RdBu, alpha=0.3)
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.RdBu)
    plt.title(title)
    plt.show()

Kernel Selection and Parameter Tuning

The choice of kernel function and its parameters significantly impacts SVM performance. This implementation demonstrates cross-validation for kernel selection and hyperparameter optimization using grid search.

from sklearn.model_selection import GridSearchCV
from sklearn.svm import SVC

def optimize_kernel_parameters(X, y):
    param_grid = {
        'C': [0.1, 1, 10],
        'kernel': ['rbf', 'polynomial'],
        'gamma': ['scale', 'auto', 0.1, 1],
        'degree': [2, 3, 4]  # for polynomial kernel
    }
    
    svm = SVC()
    grid_search = GridSearchCV(svm, param_grid, cv=5, 
                             scoring='accuracy', n_jobs=-1)
    grid_search.fit(X, y)
    
    return grid_search.best_params_, grid_search.best_score_

Memory Efficient Implementation

Large-scale SVM implementation using chunking and working set selection to handle memory constraints when dealing with large datasets through incremental optimization.

class LargeScaleSVM:
    def __init__(self, kernel='rbf', C=1.0, chunk_size=1000):
        self.kernel = kernel
        self.C = C
        self.chunk_size = chunk_size
        
    def fit_chunk(self, X_chunk, y_chunk, alpha_chunk):
        n_samples = X_chunk.shape[0]
        K = np.zeros((n_samples, n_samples))
        
        for i in range(n_samples):
            for j in range(n_samples):
                K[i,j] = self.kernel_function(X_chunk[i], X_chunk[j])
        
        # Optimize alpha for current chunk
        def objective(alpha):
            return 0.5 * np.sum((alpha * y_chunk).reshape(-1,1) * 
                   (alpha * y_chunk) * K) - np.sum(alpha)
        
        constraints = {'type': 'eq', 
                      'fun': lambda x: np.sum(x * y_chunk)}
        bounds = [(0, self.C) for _ in range(n_samples)]
        
        result = minimize(objective, alpha_chunk, 
                         bounds=bounds, constraints=constraints)
        return result.x

Multi-class SVM Strategy

Implementation of multi-class classification using kernel SVM through one-vs-one and one-vs-rest strategies, showcasing the voting mechanism for final class prediction.

class MultiClassSVM:
    def __init__(self, kernel='rbf', C=1.0, strategy='ovo'):
        self.kernel = kernel
        self.C = C
        self.strategy = strategy
        self.classifiers = []
        
    def fit_ovr(self, X, y):
        self.classes = np.unique(y)
        for class_i in self.classes:
            y_binary = np.where(y == class_i, 1, -1)
            svm = CustomKernelSVM(kernel=self.kernel, C=self.C)
            svm.fit(X, y_binary)
            self.classifiers.append(svm)
    
    def predict(self, X):
        if self.strategy == 'ovr':
            scores = np.array([clf.decision_function(X) 
                             for clf in self.classifiers])
            return self.classes[scores.argmax(axis=0)]

[Continuing with the remaining slides...]

Response:

Real-world Example: Image Classification

Implementation of kernel SVM for image classification tasks, demonstrating feature extraction, dimensionality reduction, and kernel selection for optimal performance on visual data.

from sklearn.decomposition import PCA
from skimage.feature import hog
from sklearn.preprocessing import StandardScaler

class ImageSVM:
    def __init__(self, kernel='rbf', C=1.0, n_components=100):
        self.kernel = kernel
        self.C = C
        self.n_components = n_components
        self.pca = PCA(n_components=n_components)
        self.scaler = StandardScaler()
        
    def extract_features(self, images):
        # Extract HOG features
        features = []
        for img in images:
            fd = hog(img, orientations=8, pixels_per_cell=(16, 16),
                    cells_per_block=(1, 1))
            features.append(fd)
        return np.array(features)
    
    def fit(self, X, y):
        # Feature extraction and preprocessing
        X_features = self.extract_features(X)
        X_scaled = self.scaler.fit_transform(X_features)
        X_pca = self.pca.fit_transform(X_scaled)
        
        # Train SVM
        self.svm = CustomKernelSVM(kernel=self.kernel, C=self.C)
        self.svm.fit(X_pca, y)

Advanced Kernel Operations

Advanced kernel operations including kernel alignment, multiple kernel learning, and kernel matrix optimization for improved classification performance.

def compute_kernel_alignment(K1, K2):
    """
    Compute alignment between two kernel matrices
    $$A(K_1, K_2) = \frac{\langle K_1, K_2 \rangle_F}
    {\sqrt{\langle K_1, K_1 \rangle_F \langle K_2, K_2 \rangle_F}}$$
    """
    return np.sum(K1 * K2) / np.sqrt(np.sum(K1 * K1) * np.sum(K2 * K2))

class MultipleKernelLearning:
    def __init__(self, kernels, C=1.0):
        self.kernels = kernels
        self.C = C
        self.kernel_weights = None
    
    def optimize_kernel_weights(self, X, y):
        n_kernels = len(self.kernels)
        K_list = [kernel(X) for kernel in self.kernels]
        
        def objective(weights):
            K = sum(w * K for w, K in zip(weights, K_list))
            return -compute_kernel_alignment(K, np.outer(y, y))
        
        constraints = {'type': 'eq', 'fun': lambda x: np.sum(x) - 1}
        bounds = [(0, 1) for _ in range(n_kernels)]
        
        result = minimize(objective, np.ones(n_kernels)/n_kernels, 
                         bounds=bounds, constraints=constraints)
        return result.x

Performance Analysis and Visualization

Comprehensive analysis of kernel SVM performance including ROC curves, learning curves, and decision boundary visualization for different kernel functions.

from sklearn.metrics import roc_curve, auc
from sklearn.model_selection import learning_curve

def analyze_svm_performance(X, y, svm_model):
    # Generate learning curves
    train_sizes, train_scores, test_scores = learning_curve(
        svm_model, X, y, cv=5, n_jobs=-1,
        train_sizes=np.linspace(0.1, 1.0, 10))
    
    # Plot learning curves
    plt.figure(figsize=(10, 5))
    plt.subplot(121)
    plt.plot(train_sizes, np.mean(train_scores, axis=1), 
             label='Training score')
    plt.plot(train_sizes, np.mean(test_scores, axis=1), 
             label='Cross-validation score')
    plt.title('Learning Curves')
    plt.xlabel('Training examples')
    plt.ylabel('Score')
    plt.legend()
    
    # Generate ROC curve
    y_score = svm_model.decision_function(X)
    fpr, tpr, _ = roc_curve(y, y_score)
    roc_auc = auc(fpr, tpr)
    
    plt.subplot(122)
    plt.plot(fpr, tpr, label=f'ROC curve (AUC = {roc_auc:.2f})')
    plt.plot([0, 1], [0, 1], 'k--')
    plt.title('ROC Curve')
    plt.xlabel('False Positive Rate')
    plt.ylabel('True Positive Rate')
    plt.legend()
    plt.tight_layout()
    plt.show()

Additional Resources

More in Classification and clustering

  1. The Kernel Trick Enabling Robust Machine Learning Models4 min

    The Kernel Trick is a fundamental concept in machine learning, particularly in algorithms like Support Vector Machines (SVM) and Kernel PCA. It allows us to...

  2. Random Forest Regressor Explained with Python10 min

    Random Forest Regressor is an ensemble learning method used for prediction tasks. It combines multiple decision trees to create a robust and accurate model....

  3. The Power of Decision Trees in AI17 min

    A decision tree is a hierarchical model that makes sequential decisions based on feature values, splitting the data into increasingly homogeneous subsets....

  4. Preventing Overfitting in Decision Trees with CCP10 min

    Decision trees are powerful machine learning algorithms, but they have a tendency to overfit the training data. This means they can capture noise and create...

  5. Time Complexity of K-Means Clustering in Python9 min

    K-means clustering is a popular unsupervised machine learning algorithm used for partitioning a dataset into K distinct, non-overlapping subgroups or...

  6. Predicting Premier League Winner with Random Forest7 min

    Predicting the winner of the Premier League using machine learning has become an exciting application of data science in sports. This presentation focuses on...