SVM, KERNELS.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SVM"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SVM is a widely-used classification algorithm that can be used in both linear and nonlinear cases. It finds the decision boundary/hyperplane that best separates the two classes by maximizing the margin between them."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img title=\"svm\" alt=\"text\" src=\"Images\\svm.png\"  width=\"300\">"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1: Collecting Data "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "* The first step is to collect data that contains features and their corresponding labels. Here, the ‘features’ refer to the attributes of each sample that we will use to classify it, and ‘labels’ represent the target variable that we want to predict based on those features."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2: Preparing Data"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next, we need to split the data into training and testing sets. The training set is used to train our SVM model while the test set is used for evaluating its performance."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.3,random_state=42)\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3: Defining the Hyperparameters"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hyperparameters are the parameters that are not learned during training, such as the type of kernel function (e.g., linear, polynomial, or radial basis function), regularization strength, and margin width. We need to define these hyperparameters before training our model."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4: Training the Model"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Training the SVM involves finding the optimal hyperplane/decision boundary that maximizes the margin between classes. This can be done using optimization tools such as quadratic programming."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SVM Optimization Objective\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the standard objective function(also known as the primal problem):"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img title=\"svm\" alt=\"text\" src=\"Images\\svm objective.jpg\" width=\"500\">\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "minimize: ½ ||w||^2 + C∑i=1n max(0, yi(wi . xi + b) – 1)\n",
    "```\n",
    "subject to: y ∈ {-1, 1}\n",
    "\n",
    "In this equation, w represents the weights assigned to each feature, b is the bias term, C is a regularization parameter, xi is a data point, and yi is the class label (-1 or 1).\n",
    "\n",
    "The first term (½ ||w||^2) represents the Euclidean norm of the weight vector. We want to minimize this to prevent overfitting. The second term represents the hinge loss. We aim to minimize this while satisfying the constraints on yi.\n",
    "\n",
    "To implement this in code, we can use Python's scikit-learn library. Here is some sample code to create an SVM with maximum margin using scikit-learn:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import svm\n",
    "import numpy as np\n",
    "\n",
    "# Create the training data\n",
    "X = np.array([[1, 2], [5, 8], [1.5, 1.8], [8, 8], [1, 0.6], [9,11]])\n",
    "\n",
    "# Class labels\n",
    "y = [0, 1, 0, 1, 0, 1]\n",
    "\n",
    "# Create the SVM model\n",
    "clf = svm.SVC(kernel='linear', C=1.0)\n",
    "\n",
    "# Train the model\n",
    "clf.fit(X, y)\n",
    "\n",
    "# Print the support vectors\n",
    "print(clf.support_vectors_)\n",
    "\n",
    "# Get the indices of the support vectors\n",
    "print(clf.support_)\n",
    "\n",
    "# Print the number of support vectors for each class\n",
    "print(clf.n_support_)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or implementing from scratch using this code:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SVM from scratch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class SVM:\n",
    "    def __init__(self, lr=0.001, lambda_param=0.01, iters=1000):\n",
    "        self.lr = lr\n",
    "        self.lambda_param = lambda_param\n",
    "        self.w = None\n",
    "        self.iters = iters\n",
    "        self.b = None\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        # Initialize parameters\n",
    "        _, n_features = X.shape\n",
    "        self.w = np.zeros(n_features)\n",
    "        self.b = 0\n",
    "        \n",
    "        # Gradient descent\n",
    "        for _ in range(self.iters):\n",
    "            for index, sample in enumerate(X):\n",
    "                condition = y[index] * (np.dot(sample, self.w) - self.b) >= 1\n",
    "                if condition:\n",
    "                    self.w -= self.lr * (2 * self.lambda_param * self.w)\n",
    "                else:\n",
    "                    self.w -= self.lr * (2 * self.lambda_param * self.w - np.dot(sample, y[index]))\n",
    "                    self.b -= self.lr * y[index]\n",
    "                \n",
    "    def predict(self, X):\n",
    "        approx = np.dot(X, self.w) - self.b\n",
    "        return np.sign(approx)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kernels"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Introduction for kernels:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kernel is a method of using a linear classifier to solve a non-linear problem"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "it's function is to take data as input and transform it into the required form. Different SVM algorithms use different types of kernel functions. These functions can be different types. For example linear, nonlinear, polynomial, radial basis function (RBF), and sigmoid.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The most used type of kernel function for svm is RBF. Because it has localized and finite response along the entire x-axis.\n",
    "The kernel functions return the inner product between two points in a suitable feature space. Thus by defining a notion of similarity, with little computational cost even in very high-dimensional spaces."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Types of kernels"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Polynomial kernel"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Polynomial kernal used in Support Vector Machines (SVMs) to extend the model's functionality to deal with non-linearly separable datasets. It is one of the most commonly used kernels, along with the Radial Basis Function (RBF) kernel.\n",
    "\n",
    "In polynomial kernel, every data point is transformed from the original feature space to a high dimensional feature space using a polynomial function. The degree of the polynomial determines the number of dimensions in the new feature space.\n",
    "\n",
    "The kernel function computes the dot product of two transformed data points in the high dimensional space, allowing SVM to find a hyperplane that separates the transformed points as far apart as possible. The polynomial kernel has a parameter called the degree, which specifies the complexity of the decision boundary. As the degree increases, the polynomial function becomes more complex and can fit more intricate shapes.\n",
    "\n",
    "Here is the mathematical expression for polynomial kernel:\n",
    "\n",
    "```\n",
    "K(x, z) = (x . z + c)^d\n",
    "\n",
    "```\n",
    "\n",
    "where x and z are two data vectors in the original feature space, . is the dot product operator, d is the degree of the polynomial, and c is an optional constant added to the dot product to control the smoothness of the decision boundary.\n",
    "\n",
    "In summary, the polynomial kernel is a useful tool for SVMs to handle non-linearly separable datasets by transforming the data into a high dimensional feature space. It uses a polynomial function to measure the similarity between two data points and find a decision boundary that maximizes the margin between classes.\n",
    "<img title=\"svm\" alt=\"text\" src=\"Images\\poly.png\" width=\"500\">"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Polynomial kernel using python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def polynomial_kernel(x, y, p=3):\n",
    "    return (1 + np.dot(x, y)) ** p\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### RBF kernel"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Radial Basis Function (RBF) kernel is one of the most commonly used kernels in SVM. RBF kernel maps data points to an infinite-dimensional feature space where it becomes easier to separate them using a linear hyperplane. It is also known as Gaussian Kernel due to its similarity measure that resembles the probability density function of a Gaussian distribution.\n",
    "\n",
    "The RBF kernel formula is defined as:\n",
    "\n",
    "\n",
    "```\n",
    "K(x, xi) = exp(-gamma * ||x - xi||^2)\n",
    "\n",
    "```\n",
    "where x and xi are two data points, ||x - xi|| represents the Euclidean distance between these points and gamma is a hyperparameter that determines the width of the kernel.\n",
    "\n",
    "The RBF kernel has several advantages over other kernels such as polynomial kernel:\n",
    "\n",
    "Non-linear separation: As mentioned earlier, the RBF kernel can map data into an infinite-dimensional feature space which makes it capable of separating non-linearly separable datasets more easily.\n",
    "\n",
    "Flexibility: By tuning the hyperparameters, the RBF kernel can be adjusted to fit different types of datasets.\n",
    "\n",
    "Robustness: RBF kernel can handle noise and outliers effectively due to its smoothness nature.\n",
    "\n",
    "\n",
    "<img title=\"svm\" alt=\"text\" src=\"Images\\RBF kernel.jpeg\" width=\"500\">"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### RBF kernel using python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rbf_kernel(x, y, gamma=0.1):\n",
    "    diff = x - y\n",
    "    return np.exp(-gamma * np.dot(diff, diff))\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Sigmoid kernel"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Sigmoid kernel is a non-linear kernel function used in Support Vector Machines (SVMs) for binary classification tasks. It is defined as:\n",
    "\n",
    "```\n",
    "K(x, y) = tanh(α(x·y) + c)\n",
    "\n",
    "```\n",
    "where x, y are input data instances and α and c are hyperparameters.\n",
    "\n",
    "The sigmoid kernel maps the original data instances into a higher-dimensional feature space where the instances become separable by a linear decision boundary. \n",
    "\n",
    "In summary, the sigmoid kernel is a non-linear kernel function used in SVMs that maps input data instances into a higher-dimensional feature space. However, it has some disadvantages compared to other kernels and should be used carefully.\n",
    "\n",
    "<img title=\"svm\" alt=\"text\" src=\"Images\\sigmoid.png\" width=\"500\">"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Sigmoid kernel using python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sigmoid_kernel(x, y, alpha=0.01, c=0):\n",
    "    return np.tanh(alpha * np.dot(x, y) + c)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparisons"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Advantages and disadvantages:\n",
    "\n",
    "1. Polynomial kernel:\n",
    "The polynomial kernel is an extension of the linear kernel and can handle nonlinear problems. The degree parameter is used to control the degree of the polynomial.\n",
    "Advantages:\n",
    "\n",
    "Works well with complex, multiclass data.\n",
    "Can learn complex decision boundaries.\n",
    "Disadvantages:\n",
    "\n",
    "Too much use of the degree parameter can lead to overfitting.\n",
    "High computational complexity for large datasets.\n",
    "\n",
    "2. RBF kernel:\n",
    "Radial basis function (RBF) kernel is a popular kernel in SVM that can easily segregate non-linearly separable data points.\n",
    "Advantages:\n",
    "\n",
    "Effective in high-dimensional space.\n",
    "It can handle a varied range in the similarity criterion between two data samples\n",
    "Disadvantages:\n",
    "\n",
    "Difficult to interpret the results of this kernel method.\n",
    "The gamma parameter selection has significant influence on good prediction accuracy.\n",
    "\n",
    "3. Sigmoid kernel:\n",
    "The sigmoid function applies a hyperbolic tangent to the dot product between two vectors, scaled by an additional parameter C.\n",
    "Advantages:\n",
    "\n",
    "Can be useful in neural network architectures.\n",
    "Can detect local structures within the data\n",
    "Disadvantages:\n",
    "\n",
    "Tends to be sensitive to parameter-tuning requiring careful selection of 'C' and kernel parameters.\n",
    "Can be unstable and produce variable results depending on random re-sampling of training data."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SVM is a powerful machine learning algorithm that can be used for both classification and regression tasks. It works well in cases where there is no clear or simple separation between classes. Additionally, its optimization problem guarantees a global optimum solution.\n",
    "\n",
    "Kernels play a crucial role in SVM by allowing non-linear classification boundaries via a transformation. This transformation maps the input features to a higher dimensional feature space where the data may be linearly separable. Popular kernel functions include polynomial, Gaussian RBF, and sigmoid kernels.\n",
    "\n",
    "Overall, SVM is widely used in various applications such as image classification, text classification, and bioinformatics."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}