problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5c8980bd",
   "metadata": {},
   "source": [
    "# AOS1 - Assignment\n",
    "## Improving the accuracy and speed of support vector machines\n",
    "\n",
    "Authors : Mathilde Rineau, Rémy Huet\n",
    "\n",
    "### Abstract\n",
    "\n",
    "The paper \"Improving the Accuracy and Speed of Support Vector Machines\" by Burges and Schölkopf is investigating a method to improve ht speed an accuracy of a support vector machine.\n",
    "\n",
    "As the authors say, SVM are wildly used for several applications.\n",
    "To improve this method, the authors make the difference between two types of improvements to achieve :\n",
    "- improving the generalization performance;\n",
    "- improving the speed in test phase.\n",
    "\n",
    "The authors propose and combine two methods to improve SVM performances : the \"virtual support vector\" method and the \"reduced set\" method.\n",
    "With those two improvements, they announce a machine much faster (22 times than the original one) and more precise (1.1% vs 1.4% error) than the original one.\n",
    "\n",
    "In this work, we will describe and program the two techniques they are used to see if these method are working as they say."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12aaeba6",
   "metadata": {},
   "source": [
    "### First part : tests with a vanilla SVM\n",
    "\n",
    "In this first part, we will use a vanilla SVM on the MINST dataset with the provided params.\n",
    "We will observe the error of the SVM and the time for the test phase to compare them with the improved version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9f152334",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We will work on the mnist data set\n",
    "# We load it from fetch_openml\n",
    "from sklearn.datasets import fetch_openml\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "X, y = fetch_openml('mnist_784', version=1, return_X_y=True, as_frame=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "855cdb06",
   "metadata": {},
   "source": [
    "We do some inspection on the dataset :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "708c8ea1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We print the caracteristics of X and Y\n",
    "print(X.shape)\n",
    "print(y.shape)\n",
    "# Values taken by y\n",
    "print(np.unique(y))\n",
    "\n",
    "image = np.reshape(X[0], (28, 28))\n",
    "plt.imshow(image, cmap='gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e49be54",
   "metadata": {},
   "source": [
    "The dataset contains 70k samples of 784 features.\n",
    "The classes are 0 to 9 (the digits on the images).\n",
    "\n",
    "The features are the pixels of a 28 x 28 image that we can retrieve using numpy's reshape function.\n",
    "\n",
    "For example, the 1st image is a 5."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60f31892",
   "metadata": {},
   "source": [
    "With our dataset, we can generate a training dataset and a testing dataset.\n",
    "As in the article, we will use 60k samples as training samples and 10k as testing.\n",
    "\n",
    "We split the dataset using the `train_test_split` function from `sklearn`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4d3fa1c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We divide the data set in two parts: train set and test set\n",
    "# According to the recommended values the train set's size is 60000 and the test set's size is 10000\n",
    "from sklearn.model_selection import train_test_split\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, train_size=60000, test_size=10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0532cc1",
   "metadata": {},
   "source": [
    "From the article, we retrieve the parameters of the SVM used.\n",
    "We get C = 10, and a polynomial kernel of degree 5.\n",
    "Coefficients `gamma` and `coef0` are respectively equals to 1 and 0.\n",
    "\n",
    "We can now train a SVM with these params on the training dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d809fc87",
   "metadata": {},
   "outputs": [],
   "source": [
    "# First, we perform a SVC without preprocessing or improving in terms of accuracy or speed\n",
    "from sklearn.svm import SVC\n",
    "# we perform the default SVC, with the hyperparameter C=10 and a polynomial kernel of degree 5\n",
    "# according to the recommandations\n",
    "svc = SVC(C=10, kernel = 'poly', degree = 5, gamma=1, coef0=0)\n",
    "svc.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8cf4850",
   "metadata": {},
   "source": [
    "Using the previously trained SVM, we make a prediction on the test dataset.\n",
    "\n",
    "One of the measured performance of the SVM in this article is the speed of the test phase.\n",
    "We thus measure it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8cb28178",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "start = time.time()\n",
    "# We predict the values for our test set\n",
    "y_pred = svc.predict(X_test)\n",
    "end = time.time()\n",
    "\n",
    "# We predict 10 times to have a mean elapsed time\n",
    "\n",
    "print(f'Elapsed time : {end - start}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90f08e8b",
   "metadata": {},
   "source": [
    "Of course the prediction time varies between two splits of the dataset and two executions, but we will retain that is is close from 70s.\n",
    "\n",
    "Using `y_test` the real classes of the `X_test` samples and `y_pred` the predicted classes from the SVM, we can compute the confusion matrix and the error to see the how good the predictions are."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c1248238",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We compute the confusion matrix\n",
    "from sklearn.metrics import ConfusionMatrixDisplay, classification_report, accuracy_score\n",
    "\n",
    "disp = ConfusionMatrixDisplay.from_predictions(y_test, y_pred)\n",
    "disp.figure_.suptitle('Confusion matrix for the vanilla SVM')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba4e38ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We print the classification report\n",
    "print(classification_report(y_test, y_pred))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "947b0895",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We print the accuracy of the SVC and the error rate\n",
    "acc = accuracy_score(y_test, y_pred)\n",
    "\n",
    "print(\"Accuracy: \", acc)\n",
    "print(\"Error rate: \", (1-acc) * 100, \"%\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f780139",
   "metadata": {},
   "source": [
    "As earlier, the values are affected by the selection of the training and testing dateset. Wi will retain a value of 3 % for the error.\n",
    "\n",
    "The method described py the authors relies on the support vectors of the previously trained SVM.\n",
    "We will thus do some inspection on them before going further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81b09df7",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_vects = svc.support_vectors_\n",
    "\n",
    "print(s_vects.shape)\n",
    "\n",
    "v = s_vects[0]\n",
    "v_index = svc.support_[0]\n",
    "v_class = y_train[v_index]\n",
    "print(v_index)\n",
    "print(v_class)\n",
    "\n",
    "print(f'Class of the first support vector : {v_class}')\n",
    "img = np.reshape(v, (28, 28))\n",
    "plt.imshow(img, cmap='gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14cb2622",
   "metadata": {},
   "source": [
    "There are around 7500 support vectors in the SVM.\n",
    "\n",
    "Each support vector is a sample of `X_train`. We can thus retrieve its class using its index on the train dataset, and display it as an image as above."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa1d441f",
   "metadata": {},
   "source": [
    "### Implementing the \"Virtual Support Vectors\" method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e648133",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "def right_side_rescaling(support_vectors):\n",
    "    #n,m = support_vectors.shape\n",
    "    n_square = np.array(support_vectors.shape)\n",
    "    n = int(sqrt(int(n_square)))\n",
    "    m = n\n",
    "    #print(n,m)\n",
    "    support_vector_lin =support_vectors.reshape((-1, n*m))\n",
    "    #print(support_vector_lin.shape)\n",
    "    temp = support_vector_lin[0][0]\n",
    "    for i in range (n*m-2):\n",
    "        #print(support_vector_lin[0][i])\n",
    "        support_vector_lin[0][i] = support_vector_lin[0][i+1]\n",
    "    support_vector_lin[0][n*m-1] = temp  \n",
    "    support_vectors = support_vector_lin.reshape(n,m)\n",
    "    return support_vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c402cf0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def left_side_rescaling(support_vectors):\n",
    "    #n,m = support_vectors.shape\n",
    "    n_square = np.array(support_vectors.shape)\n",
    "    n = int(sqrt(int(n_square)))\n",
    "    m = n\n",
    "    #print(n,m)\n",
    "    support_vector_lin =support_vectors.reshape((-1, n*m))\n",
    "    #print(support_vector_lin.shape)\n",
    "    temp = support_vector_lin[0][n*m-1]\n",
    "    for i in range (n*m-1,0,-1):\n",
    "        #print(support_vector_lin[0][i])\n",
    "        support_vector_lin[0][i] = support_vector_lin[0][i-1]\n",
    "    support_vector_lin[0][0] = temp  \n",
    "    support_vectors = support_vector_lin.reshape(n,m)\n",
    "    return support_vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cfc96a3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_side_rescaling(support_vectors):\n",
    "    #n,m = support_vectors.shape\n",
    "    n_square = np.array(support_vectors.shape)\n",
    "    n = int(sqrt(int(n_square)))\n",
    "    m = n\n",
    "    #print(n,m)\n",
    "    support_vector_lin =support_vectors.reshape((-1, n*m))\n",
    "    #print(support_vector_lin.shape)\n",
    "    #saving of the first line\n",
    "    temp = []\n",
    "    for j in range(m):\n",
    "        temp.append(support_vector_lin[0][j])\n",
    "    print(temp)\n",
    "    for i in range ((n-1)*m):\n",
    "        #print(\"i: \",i)\n",
    "        #print(support_vector_lin[0][i])\n",
    "        support_vector_lin[0][i] = support_vector_lin[0][i+m]\n",
    "    index = 0\n",
    "    #print(temp[1])\n",
    "    for k in range((n-1)*m,n*m):\n",
    "        support_vector_lin[0][k]=temp[index]\n",
    "        #print(\"temp: \",temp[index])\n",
    "        index+=1\n",
    "    support_vectors = support_vector_lin.reshape(n,m)\n",
    "    return support_vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e90e0d37",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bottom_side_rescaling(support_vectors):\n",
    "    #n,m = support_vectors.shape\n",
    "    n_square = np.array(support_vectors.shape)\n",
    "    n = int(sqrt(int(n_square)))\n",
    "    m = n\n",
    "    #print(n,m)\n",
    "    support_vector_lin =support_vectors.reshape((-1, n*m))\n",
    "    #saving of the last line\n",
    "    temp = []\n",
    "    for j in range((n-1)*m,n*m):\n",
    "        temp.append(support_vector_lin[0][j])\n",
    "    #print(temp)\n",
    "    for i in range((n-1)*m-1,-1,-1):\n",
    "        support_vector_lin[0][i+m] = support_vector_lin[0][i]\n",
    "    index = 0\n",
    "    for k in range(m):\n",
    "        support_vector_lin[0][k]=temp[index]\n",
    "        index+=1   \n",
    "    support_vectors = support_vector_lin.reshape(n,m)\n",
    "    return support_vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44b4c207",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(type(svc.support_vectors_))\n",
    "n = sqrt(784) \n",
    "n,m = svc.support_vectors_.shape\n",
    "print(svc.support_vectors_[i].shape)\n",
    "s_vects_right = []\n",
    "s_vects_left = []\n",
    "s_vects_top = []\n",
    "s_vects_bottom = []\n",
    "for i in range(n):\n",
    "    #print(np.array(svc.support_vectors_[i]))\n",
    "    s_vects_right.append(bottom_side_rescaling(np.array(svc.support_vectors_[i])))\n",
    "    s_vects_left.append(bottom_side_rescaling(np.array(svc.support_vectors_[i])))\n",
    "    s_vects_top.append(bottom_side_rescaling(np.array(svc.support_vectors_[i])))\n",
    "    s_vects_bottom.append(bottom_side_rescaling(np.array(svc.support_vectors_[i])))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c2840b0",
   "metadata": {},
   "source": [
    "We have shift the support vectors in the four directions so we have four new dataset which contains respectively the data shifted to the right, to the left, to the top and to the bottom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e8dad5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_vects_shifted = []\n",
    "s_vects_shifted.append(s_vects_right)\n",
    "s_vects_shifted.append(s_vects_left)\n",
    "s_vects_shifted.append(s_vects_top)\n",
    "s_vects_shifted.append(s_vects_bottom)\n",
    "\n",
    "#print(s_vects_shifted)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c9480d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "#What can we use for shifted y_train ?\n",
    "svc = SVC(C=10, kernel = 'poly', degree = 5, gamma=1, coef0=0)\n",
    "svc.fit(s_vects_shifted, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49407e07",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "78ff2a7d75990e26f7862f23aec114522929670ec71bbfd9a70bdb18a9100993"
  },
  "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}