- \n
- Effective in high-dimensional spaces<\/strong>: Particularly useful when the number of dimensions exceeds the number of samples.<\/li>\n\n\n\n
- Memory efficient<\/strong>: Uses a subset of training points in the decision function (called support vectors).<\/li>\n\n\n\n
- Versatile<\/strong>: Different kernel functions can be specified for the decision function. Common kernels include linear, polynomial, RBF (Gaussian), and sigmoid.<\/li>\n<\/ul>\n\n\n\n
2. Mathematical Foundation of SVM<\/h2>\n\n\n\n
Hyperplanes and Support Vectors<\/h3>\n\n\n\n
A hyperplane in an
-dimensional space is a flat affine subspace of dimension
. For a 2D space, the hyperplane is a line. In SVM, we aim to find a hyperplane that maximizes the margin between the two classes. The points lying closest to the hyperplane are called support vectors.<\/p>\n\n\n\n
Margin<\/h3>\n\n\n\n
The margin is the distance between the hyperplane and the closest data points from either class. Maximizing the margin helps improve the model’s generalization ability.<\/p>\n\n\n\n
Mathematical Formulation<\/h3>\n\n\n\n
Given a training dataset
where
and
, the decision function for a linear SVM is:<\/p>\n\n\n\n
<\/p>\n\n\n\n
The goal is to find
and
such that the margin is maximized. This can be formulated as a constrained optimization problem:<\/p>\n\n\n\n
Minimize
<\/p>\n\n\n\n
Subject to
for all
.<\/p>\n\n\n\n
The Dual Problem<\/h3>\n\n\n\n
Using Lagrange multipliers, the above problem can be converted into its dual form, which is easier to solve:<\/p>\n\n\n\n
Maximize:<\/p>\n\n\n\n
<\/p>\n\n\n\n
Subject to:<\/p>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n\n\n\n
where
are the Lagrange multipliers.<\/p>\n\n\n\n
Kernel Trick<\/h3>\n\n\n\n
The kernel trick allows SVM to create non-linear decision boundaries by transforming the input space into a higher-dimensional space where a linear separation is possible. Common kernels include:<\/p>\n\n\n\n
- \n
- Linear Kernel:
<\/li>\n\n\n\n
- Polynomial Kernel:
<\/li>\n\n\n\n
- Radial Basis Function (RBF) Kernel:
<\/li>\n<\/ul>\n\n\n\n
3. Implementing SVM from Scratch<\/h2>\n\n\n\n
Data Preprocessing<\/h3>\n\n\n\n
Before we start coding the SVM, let’s preprocess the data. We’ll use the Iris dataset for simplicity.<\/p>\n\n\n
import<\/span> numpy as<\/span> np\nfrom<\/span> sklearn.datasets import<\/span> load_iris\nfrom<\/span> sklearn.model_selection import<\/span> train_test_split\nfrom<\/span> sklearn.preprocessing import<\/span> StandardScaler\n\n# Load the Iris dataset<\/span>\niris = load_iris()\nX = iris.data[:100<\/span>, :2<\/span>] # We will use only the first two features and two classes for simplicity<\/span>\ny = iris.target[:100<\/span>]\n\n# Convert the labels to {-1, 1}<\/span>\ny = np.where(y == 0<\/span>, -1<\/span>, 1<\/span>)\n\n# Split the data into training and testing sets<\/span>\nX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2<\/span>, random_state=42<\/span>)\n\n# Standardize the features<\/span>\nscaler = StandardScaler()\nX_train = scaler.fit_transform(X_train)\nX_test = scaler.transform(X_test)<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nKernel Functions<\/h3>\n\n\n\n
Let’s implement some kernel functions:<\/p>\n\n\n
def<\/span> linear_kernel<\/span>(x1, x2)<\/span>:<\/span>\n return<\/span> np.dot(x1, x2)\n\ndef<\/span> polynomial_kernel<\/span>(x1, x2, degree=3<\/span>, coef0=1<\/span>)<\/span>:<\/span>\n return<\/span> (np.dot(x1, x2) + coef0) ** degree\n\ndef<\/span> rbf_kernel<\/span>(x1, x2, gamma=0.1<\/span>)<\/span>:<\/span>\n return<\/span> np.exp(-gamma * np.linalg.norm(x1 - x2) ** 2<\/span>)<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nOptimization Problem<\/h3>\n\n\n\n
The optimization problem involves finding the values of $latex \\alpha) that maximize the dual problem. We will use the Sequential Minimal Optimization (SMO) algorithm to solve this.<\/p>\n\n\n\n
Sequential Minimal Optimization (SMO)<\/h3>\n\n\n\n
SMO breaks the problem into smaller subproblems, which are then solved analytically. This approach significantly simplifies the optimization process.<\/p>\n\n\n
class<\/span> SVM<\/span>:<\/span>\n def<\/span> __init__<\/span>(self, kernel=linear_kernel, C=1.0<\/span>, tol=1e-3<\/span>, max_passes=5<\/span>)<\/span>:<\/span>\n self.kernel = kernel\n self.C = C\n self.tol = tol\n self.max_passes = max_passes\n\n def<\/span> fit<\/span>(self, X, y)<\/span>:<\/span>\n n_samples, n_features = X.shape\n self.alpha = np.zeros(n_samples)\n self.b = 0<\/span>\n self.X = X\n self.y = y\n\n passes = 0<\/span>\n while<\/span> passes < self.max_passes:\n num_changed_alphas = 0<\/span>\n for<\/span> i in<\/span> range(n_samples):\n E_i = self._decision_function(X[i]) - y[i]\n if<\/span> (y[i] * E_i < -self.tol and<\/span> self.alpha[i] < self.C) or<\/span> (y[i] * E_i > self.tol and<\/span> self.alpha[i] > 0<\/span>):\n j = np.random.randint(0<\/span>, n_samples)\n while<\/span> j == i:\n j = np.random.randint(0<\/span>, n_samples)\n E_j = self._decision_function(X[j]) - y[j]\n\n alpha_i_old = self.alpha[i]\n alpha_j_old = self.alpha[j]\n\n if<\/span> y[i] != y[j]:\n L = max(0<\/span>, self.alpha[j] - self.alpha[i])\n H = min(self.C, self.C + self.alpha[j] - self.alpha[i])\n else<\/span>:\n L = max(0<\/span>, self.alpha[j] + self.alpha[i] - self.C)\n H = min(self.C, self.alpha[j] + self.alpha[i])\n\n if<\/span> L == H:\n continue<\/span>\n\n eta = 2<\/span> * self.kernel(X[i], X[j]) - self.kernel(X[i], X[i]) - self.kernel(X[j], X[j])\n if<\/span> eta >= 0<\/span>:\n continue<\/span>\n\n self.alpha[j] -= y[j] * (E_i - E_j) \/ eta\n self.alpha[j] = np.clip(self.alpha[j], L, H)\n\n if<\/span> abs(self.alpha[j] - alpha_j_old) < 1e-5<\/span>:\n continue<\/span>\n\n self.alpha[i] += y[i] * y[j] * (alpha_j_old - self.alpha[j])\n\n b1 = self.b - E_i - y[i] * (self.alpha[i] - alpha_i_old) * self.kernel(X[i], X[i]) - y[j] * (self.alpha[j] - alpha_j_old) * self.kernel(X[i], X[j])\n b2 = self.b - E_j - y[i] * (self.alpha[i] - alpha_i_old) * self.kernel(X[i], X[j]) - y[j] * (self.alpha[j] - alpha_j_old) * self.kernel(X[j], X[j])\n\n if<\/span> 0<\/span> < self.alpha[i] < self.C:\n self.b = b1\n elif<\/span> 0<\/span> < self.alpha[j] < self.C:\n self.b = b2\n else<\/span>:\n self.b = (b1 + b2) \/ 2<\/span>\n\n num_changed_alphas += 1<\/span>\n\n if<\/span> num_changed_alphas == 0<\/span>:\n passes += 1<\/span>\n else<\/span>:\n passes = 0<\/span>\n\n def<\/span> _decision_function<\/span>(self, X)<\/span>:<\/span>\n return<\/span> np.dot((self.alpha\n\n * self.y), self.kernel(self.X, X)) + self.b\n\n def<\/span> predict<\/span>(self, X)<\/span>:<\/span>\n return<\/span> np.sign(self._decision_function(X))<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nTraining and Testing the SVM<\/h3>\n\n\n\n
Now, let’s train our SVM model and test it on the test data.<\/p>\n\n\n
# Initialize the SVM with a linear kernel<\/span>\nsvm = SVM(kernel=linear_kernel, C=1.0<\/span>)\n\n# Train the SVM<\/span>\nsvm.fit(X_train, y_train)\n\n# Predict the test data<\/span>\ny_pred = svm.predict(X_test)\n\n# Calculate the accuracy<\/span>\naccuracy = np.mean(y_pred == y_test)\nprint(f'Accuracy: {accuracy * 100<\/span>:.2<\/span>f}<\/span>%'<\/span>)<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n6. Evaluation Metrics<\/h2>\n\n\n\n
While accuracy is a common metric, it’s important to consider other metrics, especially when dealing with imbalanced datasets.<\/p>\n\n\n\n
Precision, Recall, and F1-Score<\/h3>\n\n\n
from<\/span> sklearn.metrics import<\/span> precision_score, recall_score, f1_score\n\nprecision = precision_score(y_test, y_pred)\nrecall = recall_score(y_test, y_pred)\nf1 = f1_score(y_test, y_pred)\n\nprint(f'Precision: {precision:.2<\/span>f}<\/span>'<\/span>)\nprint(f'Recall: {recall:.2<\/span>f}<\/span>'<\/span>)\nprint(f'F1-Score: {f1:.2<\/span>f}<\/span>'<\/span>)<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\nConfusion Matrix<\/h3>\n\n\n\n
A confusion matrix provides a detailed breakdown of prediction results.<\/p>\n\n\n
from<\/span> sklearn.metrics import<\/span> confusion_matrix\n\nconf_matrix = confusion_matrix(y_test, y_pred)\nprint('Confusion Matrix:'<\/span>)\nprint(conf_matrix)<\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>)<\/span><\/small><\/pre>\n\n\n7. Optimizations and Practical Tips<\/h2>\n\n\n\n
Handling Imbalanced Data<\/h3>\n\n\n\n
When dealing with imbalanced data, you can adjust the class weights.<\/p>\n\n\n
class<\/span> SVM<\/span>:<\/span>\n def<\/span> __init__<\/span>(self, kernel=linear_kernel, C=1.0<\/span>, tol=1e-3<\/span>, max_passes=5<\/span>, class_weight=None)<\/span>:<\/span>\n self.kernel = kernel\n self.C = C\n self.tol = tol\n self.max_passes = max_passes\n self.class_weight = class_weight\n\n def<\/span> fit<\/span>(self, X, y)<\/span>:<\/span>\n n_samples, n_features = X.shape\n self.alpha = np.zeros(n_samples)\n self.b = 0<\/span>\n self.X = X\n self.y = y\n\n if<\/span> self.class_weight:\n weight = np.vectorize(self.class_weight.get)(y)\n else<\/span>:\n weight = np.ones(n_samples)\n\n passes = 0<\/span>\n while<\/span> passes < self.max_passes:\n num_changed_alphas = 0<\/span>\n for<\/span> i in<\/span> range(n_samples):\n E_i = self._decision_function(X[i]) - y[i]\n if<\/span> (y[i] * E_i < -self.tol and<\/span> self.alpha[i] < self.C * weight[i]) or<\/span> (y[i] * E_i > self.tol and<\/span> self.alpha[i] > 0<\/span>):\n j = np.random.randint(0<\/span>, n_samples)\n while<\/span> j == i:\n j = np.random.randint(0<\/span>, n_samples)\n E_j = self._decision_function(X[j]) - y[j]\n\n alpha_i_old = self.alpha[i]\n alpha_j_old = self.alpha[j]\n\n if<\/span> y[i] != y[j]:\n L = max(0<\/span>, self.alpha[j] - self.alpha[i])\n H = min(self.C * weight[j], self.C * weight[j] + self.alpha[j] - self.alpha[i])\n else<\/span>:\n L = max(0<\/span>, self.alpha[j] + self.alpha[i] - self.C * weight[j])\n H = min(self.C * weight[j], self.alpha[j] + self.alpha[i])\n\n if<\/span> L == H:\n continue<\/span>\n\n eta = 2<\/span> * self.kernel(X[i], X[j]) - self.kernel(X[i], X[i]) - self.kernel(X[j], X[j])\n if<\/span> eta >= 0<\/span>:\n continue<\/span>\n\n self.alpha[j] -= y[j] * (E_i - E_j) \/ eta\n self.alpha[j] = np.clip(self.alpha[j], L, H)\n\n if<\/span> abs(self.alpha[j] - alpha_j_old) < 1e-5<\/span>:\n continue<\/span>\n\n self.alpha[i] += y[i] * y[j] * (alpha_j_old - self.alpha[j])\n\n b1 = self.b - E_i - y[i] * (self.alpha[i] - alpha_i_old) * self.kernel(X[i], X[i]) - y[j] * (self.alpha[j] - alpha_j_old) * self.kernel(X[i], X[j])\n b2 = self.b - E_j - y[i] * (self.alpha[i] - alpha_i_old) * self.kernel(X[i], X[j]) - y[j] * (self.alpha[j] - alpha_j_old) * self.kernel(X[j], X[j])\n\n if<\/span> 0<\/span> < self.alpha[i] < self.C * weight[i]:\n self.b = b1\n elif<\/span> 0<\/span> < self.alpha[j] < self.C * weight[j]:\n self.b = b2\n else<\/span>:\n self.b = (b1 + b2) \/ 2<\/span>\n\n num_changed_alphas += 1<\/span>\n\n if<\/span> num_changed_alphas == 0<\/span>:\n passes += 1<\/span>\n else<\/span>:\n passes = 0<\/span><\/code><\/span>Code language:<\/span> Python<\/span> (<\/span>python<\/span>
- Memory efficient<\/strong>: Uses a subset of training points in the decision function (called support vectors).<\/li>\n\n\n\n