katowice/introAI_Quizzes/Quiz6/Quiz_Perceptron.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-c65163ac4ad64686",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "## Perceptron, zagadnienie dualne i kernel trick!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "## Perceptron, dual space and kernel trick!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-3db41034920be294",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### Wstęp."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "### Introduction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-c6807741c0de771a",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "**Perceptron:**\n",
    "\n",
    "Mamy $m$ przykładów  danych $\\mathbf{x_i}$ i ich klasy  $y_i\\in\\{-1,1\\}$. Chcemy znaleźć klasyfikator liniowy z granica decyzyją:\n",
    "\n",
    "$$ \\mathbf{w} \\cdot\\mathbf{x}-t$$ \n",
    "\n",
    " - jeśli $ \\mathbf{w} \\cdot\\mathbf{x}-t >= 0$ to $\\mathbf{x}$ należy do klasy $y=+1$\n",
    " - jeśli $ \\mathbf{w} \\cdot\\mathbf{x}-t < 0$ to $\\mathbf{x}$ należy do klasy $y=-1$\n",
    " \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "$$\\hat{y} =  \\mathrm{sign} (\\mathbf{w} \\cdot\\mathbf{x}-t)$$\n",
    "\n",
    " \n",
    "Niech dla pewnego przykładu $\\mathbf{x_i}$ z $y_i=+1$ klasyfikator będzie dawał wynik negatywny:\n",
    "\n",
    "$$\\mathbf{w} \\cdot\\mathbf{x}-t<0 $$\n",
    "\n",
    "Dodajmy do wag wektor proporcjonalny do $\\mathbf{x_i}$\n",
    "\n",
    " $\\mathbf{w} \\to \\mathbf{w} + \\eta \\mathbf{x_i}$\n",
    " \n",
    "wtedy  \n",
    "\n",
    "  $(\\mathbf{w} + \\eta \\mathbf{x_i})\\mathbf{x_i} = \\mathbf{w}\\mathbf{x_i} + \\eta  \\underbrace{\\mathbf{x_i}\\mathbf{x_i}}_{>0}$\n",
    "\n",
    "Ostatni wyraz jest zawsze dodatni - czyli możemy liczyć że w jakims momencie poprawimy wynik. \n",
    " \n",
    "W przypadku negatywnego przykładu musimy dodać $ -\\eta \\mathbf{x_i}$, co można zapisać jednym wspólnym wyrażeniem: \n",
    " \n",
    "  $\\mathbf{w} \\to \\mathbf{w} + \\eta y_i\\mathbf{x_i}$\n",
    " \n",
    "\n",
    "**Uwagi:**\n",
    " \n",
    " \n",
    " $\\mathbf{w}\\mathbf{x}+b$ oznacza to samo co  $\\mathbf{w}\\mathbf{x}$, gdzie $w_3=b$ i $x_{i3}=1$.\n",
    " \n",
    " \n",
    " Równoważne postacie algorytmu:\n",
    " \n",
    " - $\\mathbf{w} \\to \\mathbf{w} + y_i\\mathbf{x_i}$ \n",
    " \n",
    " - $\\mathbf{w} \\to \\mathbf{w} + y_i\\mathbf{x_i}$ oraz  $b \\to b+ y_i$; \n",
    " \n",
    "\n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "**Perceptron:**\n",
    "\n",
    "We have $m$ examples of $\\mathbf{x_i}$ data and their $y_i\\in\\{-1,1\\}$ class. We want to find a linear classifier with a decision limit:\n",
    "\n",
    "$$ \\mathbf{w} \\cdot\\mathbf{x}-t$$\n",
    "\n",
    " - if $ \\mathbf{w} \\cdot\\mathbf{x}-t >= 0$ then $\\mathbf{x}$ belongs to $y=+1$ class\n",
    " - if $ \\mathbf{w} \\cdot\\mathbf{x}-t < 0$ then $\\mathbf{x}$ belongs to the $y=-1$ class\n",
    " \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "$$\\hat{y} =  \\mathrm{sign} (\\mathbf{w} \\cdot\\mathbf{x}-t)$$\n",
    "\n",
    " \n",
    "Let $\\mathbf{x_i}$ from $y_i=+1$ give the classifier a negative result:\n",
    "\n",
    "$$\\mathbf{w} \\cdot\\mathbf{x}-t<0 $$\n",
    "\n",
    "Let's add weights to the weights proportional to $\\mathbf{x_i}$\n",
    "\n",
    " $\\mathbf{w} \\to \\mathbf{w} + \\eta \\mathbf{x_i}$\n",
    " \n",
    "then\n",
    "\n",
    "  $(\\mathbf{w} + \\eta \\mathbf{x_i})\\mathbf{x_i} = \\mathbf{w}\\mathbf{x_i} + \\eta  \\underbrace{\\mathbf{x_i}\\mathbf{x_i}}_{>0}$\n",
    "\n",
    "The last word is always positive - that is, we can count on improving the result at some point.\n",
    " \n",
    "In the case of a negative example, we need to add $ -\\eta \\mathbf{x_i}$, which can be written with one common expression:\n",
    " \n",
    "  $\\mathbf{w} \\to \\mathbf{w} + \\eta y_i\\mathbf{x_i}$\n",
    " \n",
    "\n",
    "**Notes:**\n",
    " \n",
    " \n",
    " $\\mathbf{w}\\mathbf{x}+b$ is the same as $\\mathbf{w}\\mathbf{x}$, where $w_3=b$ and $x_{i3}=1$.\n",
    " \n",
    " \n",
    " Equivalent forms of the algorithm:\n",
    " \n",
    " - $\\mathbf{w} \\to \\mathbf{w} + y_i\\mathbf{x_i}$\n",
    " \n",
    " - $\\mathbf{w} \\to \\mathbf{w} + y_i\\mathbf{x_i}$ and $b \\to b+ y_i$;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0e3387a8d1a0a901",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### Dane i funkcje pomocnicze."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "### Data and auxiliary functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-ac6d0b5a01ac4856",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib inline \n",
    "import numpy as np \n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import  clear_output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-5315190b304944a2",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def plot(x,y,w,grid=20):\n",
    "    X,Y = np.meshgrid(*(2*(np.linspace(-2,2,grid),)))\n",
    "    xx = np.stack([X.flatten(),Y.flatten()] ).T\n",
    "    plt.figure(figsize=(6,6))\n",
    "    plt.imshow(np.sign(np.dot(xx,w[:2]).reshape(grid,grid) + w[2]),vmin=0,vmax=1,extent=[-2,2,-2,2],origin='lower')\n",
    "    plt.plot(x[y==-1,0],x[y==-1,1],'bo')\n",
    "    plt.plot(x[y==1,0],x[y==1,1],'ro')\n",
    "    \n",
    "    plt.xlim(-2,2)\n",
    "    plt.ylim(-2,2)\n",
    "\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-49f6dfddc8b71a4b",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def plot_dual(x,y,a,grid=20):\n",
    "    \n",
    "    X,Y = np.meshgrid(*(2*(np.linspace(-2,2,grid),)))\n",
    "    xx = np.stack([X.flatten(),Y.flatten()] ).T\n",
    "    plt.figure(figsize=(6,6))\n",
    "    D = np.array([np.sign(np.sum(a*y*(x.dot(np.append(xi,1)))**2 )) for xi in xx]).reshape(grid,grid)\n",
    "\n",
    "    plt.imshow(D,vmin=0,vmax=1,extent=[-2,2,-2,2],origin='lower')\n",
    "    plt.plot(x[y==-1,0],x[y==-1,1],'bo')\n",
    "    plt.plot(x[y==1,0],x[y==1,1],'ro')\n",
    "    \n",
    "    phi = np.linspace(0,2*np.pi,100)\n",
    "    plt.plot(np.cos(phi),np.sin(phi),'-')\n",
    "    \n",
    "    plt.xlim(-2,2)\n",
    "    plt.ylim(-2,2)\n",
    "\n",
    "\n",
    "    \n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-9f3fece54cfe1ce4",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "x = np.array([[-1.09066101, -0.86272135],\n",
    "       [ 0.58735437,  1.57663515],\n",
    "       [-1.26868118, -0.74413244],\n",
    "       [ 1.22562345,  1.63767613],\n",
    "       [-0.57747687, -0.92826376],\n",
    "       [-0.84670698, -0.87433919],\n",
    "       [-0.87775029, -1.63551329],\n",
    "       [ 0.74052768,  0.93450765],\n",
    "       [-0.34090589, -0.01919098],\n",
    "       [-0.57684532, -1.07264614],\n",
    "       [-1.46026479, -0.49299091],\n",
    "       [ 1.31762568,  1.12592783],\n",
    "       [ 1.17491385,  0.4503533 ],\n",
    "       [ 0.58115165,  0.05114449],\n",
    "       [ 0.75466739,  0.53756566],\n",
    "       [ 0.85182984,  0.16593927],\n",
    "       [-1.09286342, -0.83112391],\n",
    "       [ 0.88414066,  0.34155105],\n",
    "       [-1.34886615, -1.12314569],\n",
    "       [ 1.36318734,  1.76276714]])\n",
    "\n",
    "x += 0.94*np.ones((1,2))\n",
    "x /= 1.3\n",
    "x = np.vstack([x.T,np.ones(x.shape[0])]).T\n",
    "y = np.array([1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0])\n",
    "\n",
    "y[y==0] = -1\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-c17f3b391351b636",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "N = 2\n",
    "w = np.ones(N+1)\n",
    "m = x.shape[0]\n",
    "m,N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-b4839fe76675ad88",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### Perceptron algorytm I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "### Perceptron algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-00b1755cd65c046a",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    " - jesli $\\mathbf{w} = 0 $ to $\\eta$ nie wpływa na prędkość trenowania. \n",
    " - używamy modelu $\\mathbf{w x} = 0$ z ostatnią aktywacją równą zawsze jeden (sztuczny bias).\n",
    " \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    " - if $\\mathbf{w} = 0 $ then $\\eta$ does not affect training speed.\n",
    " - we use the $\\mathbf{w x} = 0$ model with the last activation always equal one (artificial bias)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-00265514a4cea5ac",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#  bias in weights (last feature == 1 )\n",
    "eta = 1\n",
    "w = np.ones(N+1)*0\n",
    "hist  = [ ]\n",
    "OK = False\n",
    "for k in range(35):\n",
    "    OK = True\n",
    "    for xi,yi in zip(x,y): \n",
    "\n",
    "    \n",
    "\n",
    "        if yi*w.dot(xi) <= 0:\n",
    "\n",
    "            w += 0\n",
    "### BEGIN SOLUTION        \n",
    "            w += eta*yi*xi\n",
    "### END SOLUTION        \n",
    "    \n",
    "            clear_output(wait=True)\n",
    "            plot(x,y,w,grid=100)\n",
    "            OK = False\n",
    "            #print(OK,np.sum([ y1*w.dot(xi) != 1 for xi,yi in zip(x,y)]))\n",
    "     \n",
    "        hist.append([k,*list(w)])\n",
    "    if OK:\n",
    "        print(\"OK(\",k,\") \",xi)\n",
    "        break\n",
    "        \n",
    "print(OK,w)\n",
    "# from pprint import pprint \n",
    "# pprint(hist)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-7c34de1a61ae587b",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "np.testing.assert_allclose([-1.26035052, -1.21318978, 2. ],w,rtol=1e-3)\n",
    "\n",
    "np.testing.assert_equal(np.sign(x.dot(w)), y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-a9deb6368bbb7b86",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "#### sklearn SVM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-316953dff5d407d5",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.svm import SVC\n",
    "svm = SVC(kernel=\"linear\", C=120, shrinking=False)\n",
    "svm.fit(x[:,:],y)\n",
    "plot(x,y,np.append(svm.coef_[0][:2],svm.intercept_),grid=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.linalg.norm(svm.coef_[0][:]),svm.intercept_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0c9b954aaca442b3",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### Dual form - algorytm II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-1d2e92d808ab1926",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "Jeśli $\\eta=1$ tj.  $\\mathbf{w} \\to \\mathbf{w} +  \\mathbf{x_i}$\n",
    "\n",
    "i  $\\mathbf{w} = 0 $ na starcie to mamy:\n",
    "$$\\mathbf{w} = \\sum_{i=1}^m \\alpha_i y_i \\mathbf{x_i} $$\n",
    "\n",
    "gdzie $\\alpha$ to liczba pomyłek \"korygowanych\" przez algorytm.\n",
    "\n",
    " - $\\alpha_i$ to \"instance weights\" \n",
    " - wynik zależy od kolejności pętli po przykładach\n",
    " - $\\alpha_i$ są całkowite\n",
    " - klasyfikator zależy od wyrażenia:\n",
    " \n",
    " \n",
    " $$\\hat{y} = \\mathrm{sign} (\\sum_{i=1}^m \\alpha_i y_i \\mathbf{x_i}\\cdot{\\mathbf{x}}) $$\n",
    " \n",
    "**Algorytm**\n",
    " \n",
    " dla każdego źle zaklasyfikowanego przykładu wykonaj:\n",
    " $$\\alpha_i \\to \\alpha_i  + 1 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "### Dual form - algorithm II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "If $\\eta=1$ i.e. $\\mathbf{w} \\to \\mathbf{w} +  \\mathbf{x_i}$\n",
    "\n",
    "and $\\mathbf{w} = 0 $ at the start we have:\n",
    "$$\\mathbf{w} = \\sum_{i=1}^m \\alpha_i y_i \\mathbf{x_i} $$\n",
    "\n",
    "where $\\alpha$ is the number of errors \"corrected\" by the algorithm.\n",
    "\n",
    " - $\\alpha_i$ to \"instance weights\"\n",
    " - the result depends on the order of the loops after the examples\n",
    " - $\\alpha_i$ are complete\n",
    " - the classifier depends on the expression:\n",
    " \n",
    " \n",
    " $$\\hat{y} = \\mathrm{sign} (\\sum_{i=1}^m \\alpha_i y_i \\mathbf{x_i}\\cdot{\\mathbf{x}}) $$\n",
    " \n",
    "**algorithm**\n",
    " \n",
    " for each misclassified example, do:\n",
    " $$\\alpha_i \\to \\alpha_i  + 1 $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#y[10] = -1  # non-separable\n",
    "#y[10] = 1 # separable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-53b3f9fac0178b4f",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time \n",
    "a = np.zeros(x.shape[0])\n",
    "w = np.zeros(N+1)\n",
    "\n",
    "\n",
    "perm = np.random.choice(m,m,replace=False)\n",
    "x = x[perm]\n",
    "y = y[perm]\n",
    "\n",
    "plot(x,y,w)\n",
    "\n",
    "for k in range(5):\n",
    "  \n",
    "    for i,(xi,yi) in enumerate(zip(x,y)): \n",
    "        if yi*np.sum(a*y*x.dot(xi)) <= 0:\n",
    "            a[i] += 0\n",
    "### BEGIN SOLUTION \n",
    "            \n",
    "            a[i] += 1\n",
    "### END SOLUTION        \n",
    "\n",
    "            w = np.dot(a*y,x)\n",
    "            clear_output(wait=True)\n",
    "            \n",
    "            plot(x,y,w)\n",
    "            \n",
    "            print(k,i,w,np.sum(w**2)) \n",
    "            time.sleep(0.2)\n",
    "            \n",
    "        if np.all(np.sign(x.dot(w)) == y):\n",
    "            break\n",
    "    if np.all(np.sign(x.dot(w)) == y):\n",
    "        break\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-30877c8a651a9075",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "w = np.dot(a*y,x)\n",
    "np.testing.assert_equal(np.sign(x.dot(w)), y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-2a0b41182b2e6228",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### Kernel trick!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "### Kernel trick!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "pl",
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-8372ac77bb75f18f",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "Ponieważ algorytm w postaci dualnej zależy tylko do iloczynów $\\mathbf{x_i}\\cdot\\mathbf{x_j}$ to można zauważyć, że np. zastąpienie tego iloczynu pewną funkcją jest ekwiwalentem dodania nowych cech do układu:\n",
    "\n",
    "Na przykład rozważmy:\n",
    "\n",
    "$\\mathbf{x_i}\\cdot\\mathbf{x_j} \\to K(\\mathbf{x_i}\\cdot\\mathbf{x_j}) = (\\mathbf{x_i}\\cdot\\mathbf{x_j})^2$\n",
    "\n",
    "W dwóch wymiarach mamy:\n",
    "\n",
    " $$ (\\mathbf{x_i}\\cdot\\mathbf{x_j})^2 = (x_i x_j + y_i y_j)^2 = x_i^2 x_j^2 + y_i^2 y_j^2 + 2 x_i x_j y_i y_j  $$\n",
    " \n",
    "Weżmy transformację $\\phi(\\mathbf{x}) = (x^2,y^2,\\sqrt{2} x y)$, wtedy:\n",
    "\n",
    "\n",
    "$$ \\phi(\\mathbf{x_i}) \\cdot \\phi(\\mathbf{x_j})  = x_i^2 x_j^2 + y_i^2 y_j^2 + 2 x_i x_j y_i y_j $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "en"
   },
   "source": [
    "Since the algorithm in the dual form depends only on the products of $\\mathbf{x_i}\\cdot\\mathbf{x_j}$, it can be seen that, for example, replacing this product with a certain function is the equivalent of adding new features to the system:\n",
    "\n",
    "For example, consider:\n",
    "\n",
    "$\\mathbf{x_i}\\cdot\\mathbf{x_j} \\to K(\\mathbf{x_i}\\cdot\\mathbf{x_j}) = (\\mathbf{x_i}\\cdot\\mathbf{x_j})^2$\n",
    "\n",
    "In two dimensions we have:\n",
    "\n",
    " $$ (\\mathbf{x_i}\\cdot\\mathbf{x_j})^2 = (x_i x_j + y_i y_j)^2 = x_i^2 x_j^2 + y_i^2 y_j^2 + 2 x_i x_j y_i y_j  $$\n",
    " \n",
    "Let's take the $\\phi(\\mathbf{x}) = (x^2,y^2,\\sqrt{2} x y)$ transformation, then:\n",
    "\n",
    "\n",
    "$$ \\phi(\\mathbf{x_i}) \\cdot \\phi(\\mathbf{x_j})  = x_i^2 x_j^2 + y_i^2 y_j^2 + 2 x_i x_j y_i y_j $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-30fe3f7fa5ed19cb",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "m = 20\n",
    "x = np.random.randn(m,2)/1.\n",
    "y = np.ones(m)\n",
    "w = np.zeros(N+1)\n",
    "y[np.sum(x**2,axis=1)<1.] = -1\n",
    "x = np.vstack([x.T,np.ones(x.shape[0])]).T\n",
    "plot(x,y,w)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-bd9495b7028d54a6",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time \n",
    "a = np.zeros(x.shape[0])\n",
    "w = np.zeros(N+1)\n",
    "\n",
    "perm = np.random.choice(m,m,replace=False)\n",
    "x = x[perm]\n",
    "y = y[perm]\n",
    "\n",
    "plot_dual(x,y,a)\n",
    "\n",
    "for k in range(215):\n",
    "  \n",
    "    for i,(xi,yi) in enumerate(zip(x,y)): \n",
    "        ### BEGIN SOLUTION \n",
    "\n",
    "        if yi*np.sum(a*y*(x.dot(xi))**2 ) <= 0:\n",
    "            a[i] += 1\n",
    "            clear_output(wait=True)\n",
    "            plot_dual(x,y,a,grid=85)\n",
    "            time.sleep(0.01)\n",
    "        ### END SOLUTION \n",
    "        pass    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-379099bad3a483a1",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "yhat=[np.sign(np.sum((ai*yi*np.dot(xi,xj)**2) for ai,yi,xi in zip(a,y,x))) for xj in x]\n",
    "np.testing.assert_array_equal( yhat, y ) "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "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.7.3"
  },
  "nbTranslate": {
   "displayLangs": [
    "en",
    "pl"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "pl",
   "targetLang": "en",
   "useGoogleTranslate": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}