Support Vector Machine

Support Vector Machine (SVM) is a powerful supervised learning algorithm used for both classification and regression tasks. In classification, SVM finds the optimal hyperplane that best separates different classes in the feature space.

What is a Support Vector Machine?

Support Vector Machine (SVM) is a supervised learning algorithm that finds the optimal hyperplane to separate different classes in the feature space.

How SVM Works

SVM works by mapping input features into a high-dimensional space and finding the hyperplane that best separates the classes. The data points closest to the hyperplane are called support vectors, and they play a crucial role in defining the decision boundary.

Setup Rules for the Hard-Margin Derivation

To derive the mathematical formulas for the basic Hard-Margin SVM, we must first establish a strict setup where the following conditions hold true:

• Perfect Linear Separability: We assume the training data is completely clean and can be split cleanly into two groups using a straight line, with no overlapping points.
• The Hyperplane Formula: We define our center decision boundary using the linear matrix equation: $w \cdot x + b = 0$.
• The Classifier Function: We define our decision rule $h(x)$ to output a discrete label based on which side of the line a point falls on:

  $$h(x) = \begin{cases} +1 & \text{if } w \cdot x + b \geq 0 \\ -1 & \text{if } w \cdot x + b < 0 \end{cases}$$

• Symmetric Safety Margins: We assume the empty safety buffer zone extends out by the exact same distance on both the positive side ($+1$) and the negative side ($-1$) of our center line.

Derivation

The Mathematical Bridge: Lagrange Multipliers & The Dual Form

To solve an optimization problem tied down by strict boundary constraints, mathematicians use a technique called Lagrange Multipliers ($\alpha_i \geq 0$). We combine our optimization goal and our boundaries into a single expression called the Lagrangian function ($L$):

To find the absolute best boundary line, we calculate the partial derivatives of $L$ with respect to our main variables ($w$ and $b$) and set them to zero:

Substituting these identities back into our original equation completely eliminates the weight vector $w$. This transforms our system into its mathematical twin, known as the Wolfe Dual Problem:

The Kernel Trick: Unlocking Higher Dimensions

When features are mixed together like a target ring, no straight line can separate them in 2D space. To fix this, we can project our coordinates into a higher dimension where a flat plane can slice them cleanly. However, calculating new coordinates for thousands of points would crash our computer's memory.

Because our Dual equation relies entirely on the dot product $(\mathbf{x_i \cdot x_j})$, we can apply the Kernel Trick. We replace the linear product with a specialized Kernel function $K(x_i, x_j)$:

A Kernel is a mathematical shortcut. It calculates what the geometric relationship between points would be in that infinite higher-dimensional space without ever calculating or storing the complex new coordinates themselves.

Dealing with Real-World Data: Soft-Margin SVM

Up until now, we assumed our data is perfectly clean and can be split with a straight line. But in the real world, data points overlap and mix together. If we try to enforce a hard boundary, the computer will fail or create a messy line that does not generalize well.

Connecting Optimization to Code: Primal Hinge Loss

While the Dual Form is perfect for complex non-linear kernels, implementing a fast Linear Kernel can be done directly in the Primal Form using Gradient Descent. We collapse our soft-margin constraints into a single, codeable Cost Function ($J$) using Hinge Loss and $L_2$ Regularization:

During training, the program checks if a point satisfies the safety boundary condition: $y_i(w \cdot x_i + b) \geq 1$ and compute the partial derivatives to adjust our weights and bias:

NumPy Scratch Implementation

import numpy as np



class SupportVectorMachine_linear:

    def __init__(self, C=1.0, learning_rate=0.01, epochs=1000):
        self.lr = learning_rate
        self.C = C
        self.epochs = epochs
        self.w = None  # Weights
        self.b = None


    def fit(self, X, y):
        # Fit the model to the training data
        n_samples, n_features = X.shape

        self.w = np.random.rand(n_features) * 0.1 #Randomly assigned the weights
        self.b = np.random.rand(1) * 0.1  # Randomly assigned bias

        for epoch in range(self.epochs):
            for i in range(n_samples):
                # Compute the hinge loss
                condition = y[i] * (np.dot(self.w, X[i]) + self.b)
                if condition >= 1:
                    # Update weight
                    self.w -= self.lr * ( 2 * self.w)
                else:
                    # Update weights and bias
                    self.w -= self.lr * (2 * self.w - self.C * y[i] * X[i])
                    self.b += self.lr * (self.C * y[i])
                    

    def predict(self, X):
        # Make predictions on new data
        z = np.dot(X, self.w) + self.b

        return np.sign(z)

Using scikit-learn

from sklearn.svm import SVC

# Initialize linear kernel classifier
clf = SVC(kernel='linear', C=1.0)

# Train the model
clf.fit(X_train, y_train)

# Make class label predictions
predictions = clf.predict(X_test)

Advantages & Disadvantages

Evaluation Metrics for Classification

Ready to explore advanced classification? Check out Supervised Learning overview for more algorithms!