{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Lab 7: Kernels, Support Vector Machines" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part I: Kernels \n", "\n", "#### Exercise 1. A complex dataset\n", "\n", "Consider the dataset given below. We want to learn a classifier for this data, by relying on the $\\ell_2$ loss. " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAVcklEQVR4nO3dbYxcV33H8d/PcSN1eS5ZQNjxLlAohCqp6iUVqA+haRXTCoWokZqwUqQUZLklFbygSmhahBRZVYUq8QJoZEUoL2I1Qi20QE3SigioGqiyrpwHExKZEDsmL9gQVASpCo7/fXFnyHg8u3tn586955z7/Ugj78xc7/7vPPzvuf/zcB0RAgDkb0fXAQAAmkFCB4BCkNABoBAkdAAoBAkdAAqxs6s/fNFFF8Xy8nJXfx4AsnT06NFnImJx0nOdJfTl5WWtra119ecBIEu2T270HCUXACgECR0ACkFCB4BCkNABoBAkdAAoRL8S+uHD0vKytGNH9e/hw11HBACN6U9CP3xY2r9fOnlSiqj+3b+fpI580CDBFvqT0G+9VXruuXMfe+656nEgdTRIUEN/EvqpU9M9DqSEBglq6E9C37NnuseBlNAgQQ39SegHD0oLC+c+trBQPQ6kjgYJauhPQl9dlQ4dkpaWJLv699Ch6nEgdTRIUEN/ErpUJe8nn5TOnq3+JZn3R+4jRGZpkOS07znFmqKI6OS2d+/eAFpx110RCwsR1fiQ6rawUD1eupz2PadYOyRpLTbIq66eb9/KykqwfC5asbxcDfMbt7RUnamVLKd9zynWDtk+GhErk57rV8kF/dTnESI57XtOsSaKhI7y9XmESE77nlOsiSKho3x9HiGS077nFGuiSOgoX5+HrOa07znFmig6RQEgI3SKAkAPkNABoBAkdAAoBAkdAApBQgeAQpDQAaAQ/U3orOoGoDA7uw6gE8PrMw4v6TW8PqPEJAYA2epnC53rMwIv4Gy1GP1sobOqG1DhbLUotVrotvfZfsz2Cdu3THj+Zba/aPtB28dt39h8qA1iVbdu0BJMD2erRdkyodu+QNKnJL1L0iWSrrd9ydhmH5D0rYi4TNIVkv7O9oUNx9ocVnVr37AlePJkdS2aYUuQpN4tzlaLUqeFfrmkExHxRET8VNLdkq4e2yYkvcS2Jb1Y0rOSzjQaaZNY1a19tATTxNlqUeok9F2Snhq5f3rw2KhPSnqLpKclPSzpgxFxdvwX2d5ve8322vr6+jZDbggXjG4XLcE0cbZalDoJ3RMeG19z9ypJxyS9VtKvSfqk7Zee958iDkXESkSsLC4uThkqskZLME2crRalTkI/Lenikfu7VbXER90o6XODi1KfkPRdSW9uJkQUoY8twVw6gTlbLUadhP6ApDfaft2go/M6SV8Y2+aUpCslyfarJf2KpCeaDBSZ61tLkE5gdGDLhB4RZyTdJOleSY9K+mxEHLd9wPaBwWa3SXqH7YclfUXSzRHxzLyCRqb61BKkEzh/uZxhjeASdMA87NhRtczH2dUBDWkbn3AlVSXCBM4quQQd0DY6gfOW6RkWCR2Yhz52Apck02G2JHRgHvrWCbyV3OrRmZ5hkdBTktuHHpvrUyfwZnIc8ZPpGRYJPRU5fuiBOnKsR2d6hsUol1QsL1dJfNzSUtW6A3LFiJ9GMcolB5l2wgBbyrQenSMSeir40KNUmdajc0RCTwUfepQq03p0jvp5CboUDT/ct95alVn27KmSOR96lGB1lc9yC0joKeFDD2AGlFwAoBAkdBSFuVnoM0ouKMb4AnnDuVkSlSz0Ay30Omj2ZSHHCYlAk/JK6F0kVqbkZ4O5Wei7fBJ6V4mVZl82mJuFvssnoXeVWGn2ZYO5Wei7fBJ6V4mVZl82mJCIvssnoXeVWGn2ZYUlyNFn+ST0rhIrzT4AmchnHHqXa50wJR9ABvJpoUucT2MumGaAUuSV0IGGZTXNgCMPtkBCR69lM80gqyMPukJCR69lM80gmyMPukRCR69lM80gmyMPukRCR5aaKidnM80gmyMPukRCR3aaLCdnM80gmyMPukRC75EUB0lsJ6amy8mzjIZt7TXN5siDTkVEJ7e9e/cG2nPXXRELCxFVm7a6LSxUj+cWk33u/xne7HbiHkrxNUX5JK3FBnnV1fPtW1lZibW1tU7+dh8tL1eliXFLS1WrtAvbjSmVfUklDvSL7aMRsTLpOUouPZHiIIntxpRKOTnF17RoKdYME9OfhN7zD0OKgyS2G1Mq5eQUX9NiMbGqno1qMfO+tVpDp9iZ5EuQYkzDuJaWqpr80tLG8aQaf5GWliZ3nCwtdR1Z67RJDb0fCZ0PQ0TUT1RtSi2maZN0avEXK5We8ARsltD70Sm6Y0f19o+zq7FqwAAdnYnijfk5OkUpdqImOjoTlUpPeOL6kdD5MKAmjv2JSqUnPHG1ErrtfbYfs33C9i0bbHOF7WO2j9v+WrNhzogPQ6NKHjDEsT9hXOBmS1vW0G1fIOlxSb8v6bSkByRdHxHfGtnm5ZLul7QvIk7ZflVEfH+z38vEojwNR4+NTr1fWCjr+Hj4cDdXOgTq2KyGXiehv13SxyLiqsH9j0hSRPzNyDZ/Jum1EfFXdYMioeeJvimgW7N2iu6S9NTI/dODx0a9SdIrbH/V9lHbN2wQyH7ba7bX1tfX68SOxNBpCMxgzvXKOgndEx4bb9bvlLRX0h9KukrSX9t+03n/KeJQRKxExMri4uLUwaJ7KXcallzbRwFamO1aJ6GflnTxyP3dkp6esM09EfGTiHhG0tclXdZMiEhJqp2GzAxH8lq4jGCdhP6ApDfafp3tCyVdJ+kLY9v8i6Tfsr3T9oKk35D0aGNRIhmpDhjikptIXgv1yp1bbRARZ2zfJOleSRdI+kxEHLd9YPD87RHxqO17JD0k6aykOyLikcaiRFJWV7tP4OOo7SN5e/ZMHlHQYL1yy4QuSRFxRNKRscduH7v/cUkfbywyYAotfFeA2Rw8OHnMb4P1yrxnitILVoQm3sZUa/vAz7VRr9xo1a5532ZebZG1S4vQ5NvIyofoAxW52iIzXIrA2whMp8zVFukFK0KpbyPVQHQh34Se8gwX1Fbi28iYeHQl34Q+z14wmletKbEzkzHx6Eq+CX1ePcY0r1rV1kSlNo/RpZaRkL58O0XnhV664rS95C8fIcxTmZ2i80Lzqjhtl0BKLCMhDyT0cSX20vVc28foVNe7QflI6ONoXhWni2N0U1dLo38e0yChj6N5VZxcj9H0z2NadIqiF3K8Tiidq5hkpmuKzgsJHdjcjh1Vy3ycXZVy0E+MculSQUXQgnZlKl3tN/3zmNpGq3bN+zbzaos5KGhFyBx2ZR6rLXa53zm85mifNlltkYQ+T0tL534bh7elpa4jm1rquzKv5Nf1frMkMMZtltCpoc9TQUXQ1HdlXh2Iqe83+ocaelcKKoKmvivzmjyU+n4Do0jo85TrAOgJUt+VeSXe1PcbGEVCn6eCJil1sSvTjC6ZV+It6C1EH2xUXJ/3rRedoti27XRy0oGIJDX8wdQmnaK00JGk7ayQ2NT6KU3r6/h9qPX1G0jomItZk1gpqxizHkvPtbx2MwkdjWsiiZUyuoTL0fVcyy0TEjoa10QSa2N0SRulkFLONLBNLbdMSOhoXBNJbN6jS6Y9i9hu8i/lTAPb1Pa41416S+d9Y5RLubqeLl/HNDHOsqwA67GgzVEuTP1H49q+KPN2TDOlf9ZlBXJcix3pYuo/WpXDZJxpSiGzlpBSHU6J8pDQMRepJ7FpSpvUwZELEjp6aZqzCNZzQS52dh0A0JXV1XpnDsNtqIMjdbTQgRpSLyH1DuspTEQLHUBexodRDScRSL0/0vajhc7RHCgH6ylsqPyE3pfVkThooS9YT2FD5Sf0PhzN+3LQAiTGkW6i/ITeh6N5gQet0k84kti/JILYBsaRbmyjNQFGb5L2SXpM0glJt2yy3dskPS/p2q1+Z2trueSwsMis7Mn7aHcd2baUvv5JEvuXRBAz6PHlqbTJWi51kvkFkr4j6fWSLpT0oKRLNtjuPklHkkrouX9w60j0oLXd71yiu3OOWfJJEvuXRBDYjlkT+tsl3Tty/yOSPjJhuw9J+oCkO5NK6BHlH80TPGjNElLqJxyzvtxJ7F8SQWA7NkvodWrouyQ9NXL/9OCxn7O9S9I1km7f7BfZ3m97zfba+vp6jT/dkNJnhSS4GtYsZf3U+7xm7bJIYv+SCAJNq5PQPeGx8YVHPyHp5oh4frNfFBGHImIlIlYWFxdrhohaEjtozdIXnXqf16z97EnsXxJBoGl1EvppSReP3N8t6emxbVYk3W37SUnXSvq07fc0ESDyNEsDMMETjnPM2rhNYv+SCAJN2/ICF7Z3Snpc0pWSvifpAUnvjYjjG2x/p6QvRcQ/bvZ7ucBF2XK4yMV2lbxvSN9MF7iIiDOSbpJ0r6RHJX02Io7bPmD7QLOhohQpNgCbGnad4r4BUo0W+rzQQkebaFWjFFyCDr1X4GRa4DwkdPRCH1aAAEjo6AWGXaMPSOjoBYZdow9I6OgFRqagD7gEHXqj7kWhgVzRQgeAQpDQAaAQJPRRuV7BBQBEDf0F41MJh9fllCi8AsgCLfQhphICyBwJfYiphAAyR0IfYiphK1LrpkgtHmAWJPQhphLO3bCb4uTJ6gKWw26KrpJoavEAs2L53FGHD1c181Onqpb5wYN0iDZoeblKmuOWlqqr5rUttXiAOjZbPpeEjtbs2FG1hMfZ1aVQ+x4PUAfroSMJs3ZTNF3vptsEpSGhozWzdFPMo95NtwlKQ0JHa2ZZ8XAe0wRYgRGloYaOLFDvBirU0NGYrsZtU+8GtkZCR21djtum3g1sjYSO2rpc7oZ6d8KYbpsMauiojTo2zjO+SqlUnTpxtJ0bauhoBHVsnIdVSpNCQkdt1LFxHlYpTQoJHbVRx8Z5OG1LCgkdU1ldrRauOnu2+pdk3nOctiWFhA5g+zhtSwoJHcBsOG07V4fDOLlINAA0peOLzdNCB4CmdDyMk4QOAE3peBgnCR0AmtLxME4SOgA0peNhnCR0AGhKx8M4GeUCAE1aXe1s6CYtdAAoBAm9bawdDWBOaiV02/tsP2b7hO1bJjy/avuhwe1+25c1H2oBurzkD4DibZnQbV8g6VOS3iXpEknX275kbLPvSvqdiLhU0m2SDjUdaBFYOxrAHNVpoV8u6UREPBERP5V0t6SrRzeIiPsj4oeDu9+UtLvZMAdyL1ewdjSAOaqT0HdJemrk/unBYxt5n6QvT3rC9n7ba7bX1tfX60cplVGuYO1oAHNUJ6F7wmMTL0Rq+52qEvrNk56PiEMRsRIRK4uLi/WjlMooV7B2dJpyP/MDBuok9NOSLh65v1vS0+Mb2b5U0h2Sro6IHzQT3ogSyhWsHZ2eEs78gAHHpMu4j25g75T0uKQrJX1P0gOS3hsRx0e22SPpPkk3RMT9df7wyspKrK2t1Y90ebn6so1bWqrWYAa2g88VMmP7aESsTHpuyxZ6RJyRdJOkeyU9KumzEXHc9gHbBwabfVTSKyV92vYx21Nk6pooV2AeSjjzAwZqTf2PiCOSjow9dvvIz++X9P5mQxszLEvcemv1Zduzp0rmlCswiz17JrfQ6ahGhvKaKcqlrtA0zvxQkLwSOtA0OqpREFZbBDpcHQ9oEi10ACgECR0oHROneoOSC1Cy4cSp4Szr4cQpiTJTgWihAyUrYckM1EZCB0rGxKleIaEDJWOFz14hoQMlY+JUr5DQgZIxcapXGOUClI6JU71BCx0ACkFCB4BCkNABoBAkdAAoBAkdAApBQgeAQpDQAaAQJHQAKAQJPTWsXQ1gm5gpmhLWrgYwA1roKWHtagAzIKGnhLWrAcyAhJ4S1q4GMAMSekpYuxrADEjoKWHtagAzYJRLali7GsA20UIHgEKQ0AGgECR0ACgECR0ACkFCB4BCOCK6+cP2uqSTM/6aiyQ900A485J6fBIxNiH1+KT0Y0w9PimdGJciYnHSE50l9CbYXouIla7j2Ejq8UnE2ITU45PSjzH1+KQ8YqTkAgCFIKEDQCFyT+iHug5gC6nHJxFjE1KPT0o/xtTjkzKIMesaOgDgBbm30AEAAyR0AChEFgnd9j7bj9k+YfuWCc+/2fY3bP+f7Q8nGN+q7YcGt/ttX5ZgjFcP4jtme832b6YU38h2b7P9vO1r24xv8Le3eg2vsP0/g9fwmO2PphTfSIzHbB+3/bU246sTo+2/GHn9Hhm817+UUHwvs/1F2w8OXsMb24qtlohI+ibpAknfkfR6SRdKelDSJWPbvErS2yQdlPThBON7h6RXDH5+l6T/SjDGF+uFPpVLJX07pfhGtrtP0hFJ1yb4Gl4h6UttxjVlfC+X9C1Jewb3X5VajGPbv1vSfSnFJ+kvJf3t4OdFSc9KurCL93zSLYcW+uWSTkTEExHxU0l3S7p6dIOI+H5EPCDpZ4nGd39E/HBw95uSdicY449j8CmV9CJJbfaWbxnfwJ9L+idJ328xtqG6MXalTnzvlfS5iDglVd+bBGMcdb2kf2glskqd+ELSS2xbVSPoWUlnWoxxUzkk9F2Snhq5f3rwWCqmje99kr4814jOVytG29fY/rakf5X0Jy3FJtWIz/YuSddIur3FuEbVfZ/fPjgd/7Ltt7YTmqR68b1J0itsf9X2Uds3tBZdpfZ3xfaCpH2qDuBtqRPfJyW9RdLTkh6W9MGIONtOeFvL4YpFnvBYSmMta8dn+52qEnqr9WnVjDEiPi/p87Z/W9Jtkn5v3oEN1InvE5Jujojnq8ZR6+rE+N+q1tn4se0/kPTPkt4478AG6sS3U9JeSVdK+kVJ37D9zYh4fN7BDUzzXX63pP+MiGfnGM+4OvFdJemYpN+V9AZJ/277PyLiR3OOrZYcWuinJV08cn+3qqNjKmrFZ/tSSXdIujoiftBSbENTvYYR8XVJb7B90bwDG6gT34qku20/KelaSZ+2/Z5WoqtsGWNE/Cgifjz4+YikX0jsNTwt6Z6I+ElEPCPp65La7KCf5nN4ndott0j14rtRVdkqIuKEpO9KenNL8W2t6yJ+jY6KnZKekPQ6vdBR8dYNtv2Y2u8U3TI+SXsknZD0jlRfQ0m/rBc6RX9d0veG91OIb2z7O9V+p2id1/A1I6/h5ZJOpfQaqioVfGWw7YKkRyT9akqv4WC7l6mqTb8owff47yV9bPDzqwffk4vajHOzW/Ill4g4Y/smSfeq6oX+TEQct31g8Pzttl8jaU3SSyWdtf0hVb3Tcz8NqhOfpI9KeqWqVqUknYkWV22rGeMfSbrB9s8k/a+kP47BpzaR+DpVM8ZrJf2p7TOqXsPrUnoNI+JR2/dIekjSWUl3RMQjbcRXN8bBptdI+reI+ElbsU0R322S7rT9sKoSzc1Rne0kgan/AFCIHGroAIAaSOgAUAgSOgAUgoQOAIUgoQNAIUjoAFAIEjoAFOL/AduZjPJAC6CMAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "from scipy.io import loadmat\n", "pointsClass1 = loadmat('KernelPointsEx1class1.mat')['PointsEx1class1']\n", "pointsClass2 = loadmat('KernelPointsEx1class2.mat')['PointsEx1class2']\n", "\n", "\n", "plt.scatter(pointsClass1[:,0], pointsClass1[:,1], c='r')\n", "plt.scatter(pointsClass2[:,0], pointsClass2[:,1], c='b')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.1 Gradient updates on the dual formulation\n", "\n", "Start by generating polynomial features using the function 'sklearn.preprocessing.PolynomialFeatures' from scikit learn. By relying on the kernel trick, starting from the $\\ell_2$ (OLS) loss, derive the dual formulation (optimization problem on the coefficients $\\lambda_i$ that are used to express the weight vector $\\beta$ as the combination $\\beta$). Once you have that loss, find the optimal coefficients $\\lambda^*$ through gradient updates. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# put your code here \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.2 Final Models\n", "\n", "Using the optimal coefficients, derive the classifier $y(\\mathbf{x}) = \\mathbf{\\beta}^T\\mathbf{\\phi}(\\mathbf{x})$, expressing the weight vector $\\mathbf{\\beta}$ as the combination $\\mathbf{\\beta} = \\sum_{i=1}^N \\lambda_i^* \\mathbf{\\phi}(\\mathbf{x}^{(i)})$. Then display the boundary by using meshgrid. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 2 A disconnected dataset. \n", "\n", "We want to make the problem a little more difficult. Use your implementation of descent algorithm to learn a classifier for the dataset below. Progressively increase the number of features (i.e. increase the degree) and keep in mind that there is often and efficient way to compute the Kernel matrix. " ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAZUklEQVR4nO3dXYhd13UH8P+ShCBDUsdE05RKnhk12E2U1i5o4lDT0KSm9UehpuCA7cEBkyJE6pC+yYkhFMxA85YH2zXCFD/MgDCpSRxILEpLnIDjxqPij8jCZiLH46mgkZNCwXkwslYfzh376s6955577/5Ya+//Dy7ynbme2bPPOevsvfbHEVUFERH5tyd3AYiIKAwGdCKiQjCgExEVggGdiKgQDOhERIXYl+sXHzhwQJeWlnL9eiIil86cOfO2qs4P+162gL60tISNjY1cv56IyCUReXPU95hyISIqBAM6EVEhGNCJiArBgE5EVAgGdCKiQhQb0NfXgaUlYM+e5t/19dwlsoN1Ex/rmHIoMqCvrwPHjgFvvgmoNv8eO5b3orJygVusm9KwjikXybV97vLyssaah7601FxEgxYXgV/+MsqvbLVzgf/2tx98bW4OOHkSWFlJWxZrdVMi1jHFJCJnVHV52PeKbKFvbU329dgefPDKYA407x98MH1ZrNVNiSzXsZWe4rSsld9aeaCqWV5Hjx7VWBYXVZvO7pWvxcVov7KVyPDyiKQvS+66WVtrfpdI8+/aWprfm1LuOh5lbU11bu7KMs3N+TkG1sqfqzwANnREXC0yoFs78JYu8Jx1Y+24xGL177R0Hk7DWvlzlae6gK5qqyVo7QLPVTfWLsiYLJ1/Oyz1FKdhrfy5ytMW0IscFLVofb3JmW9tAQsLwOpq+gHR3PbsaU75QSLA5cvpy1Mb74O11sqfqzzVDYpatLLSHOTLl5t/awvmQHMjm+TrFNbqajO7qt/cXPN1D6yV31p5AAZ0SsjiBVCTlZVmquziYtMrWlzMM3V2WtbKb608QKHz0Mkupp6IZtOWcsn2gAuq08oKAzhRLEy5EBEVggGdqmRuhR9RAEy5UHUG99bZ2TwLYDqIfGMLnapjaW8dopAY0Mdg17w8ljfPIpoFA3oL7mtdJi5wolIxoLdg17xMXOBEpWJAb8GueZksrvAjCoEBvQW75uWKvbcOx14oBwb0Fuya0zQ49kK5MKC3YNecpsGxF8qFm3MRBcZ93ykm7odOlBDHXupjZcyEAd0rK2cQ7eJy7IXn09RMjZmMejZd7FfsZ4oWzdpDSmkXi88UHamy8yn0sUn9rFzwmaKFsfZwRfKtovNpcGM2oOk9zTLZIfWYSTE5dPYKe3KseGLll6uiFXQxZiBZGjNxE9BN5alyS30GsfLLZikiRRbj3mVpzMRNQOfc3j6pzyBWftmsRKQEvcAY9y5T61VGJdf7XwBuBfAagE0ADwz5/lUAvg/gJQBnAdw37mdOOigqMnzgQWT6wQXXUo66sfLLl3sUN9HAbAnjv5hlUFRE9gJ4HcBfAtgG8AKAu1X11b7PfAPAVap6QkTme8H/91T13VE/d9JB0YrGbexh5VNsCc+x9fWmc7m11bTMV1d9rf6edVD0RgCbqnq+F6BPAbhj4DMK4CMiIgA+DOA3AC7NUOZdrPQKq8TKp9gSDszG3pgtpy4B/SCAt/reb/e+1u9hAJ8CcAHAKwC+pqq7JuyIyDER2RCRjYsXL05UUFN5qtqw8im2igZmY+oS0GXI1wbzNLcAeBHA7wP4EwAPi8jv7PqfVE+q6rKqLs/Pz09Y1LLvrOax8pOpcoYoe4FBdAno2wCu6Xt/CE1LvN99AJ7q5ew3AbwB4JNhikhUD/MzRGPdbdgLDKLLoOg+NIOiNwP4bzSDoveo6tm+z/wzgP9R1X8UkY8D+C8AN6jq26N+LleKEu1mevw5xjJLmthMg6KqegnA/QBOAzgH4ElVPSsix0XkeO9jDwG4SUReAfDvAE60BXMiGs70ok2uRzCv08IiVf2Bql6nqp9Q1dXe1x5T1cd6/31BVf9KVf9YVf9IVddiFro6VSZV62R6bND03YYARytFq2U+qRpY5Tcv02ODpu82BDCg21dTN7e2m9cQpscGTd9tCOAj6Oyr6XlmpkcECYD/ZZYFaBsU3Ze6MDShhYXhQa7Ebi5ztPatrDCAG8aUi3Wxu7mWctbM0ZJjFi4lBvQQYh7JmElVazlrJzlaCxeuCxVVlJlLadQ2jLFfxTxT1PN+nKkfhthF7m1cx/B8uJOqrKJSXkrgM0Uj8jyQV9OAayCeD3dSlVVUykupmGeKmuR5II8564l5Pty7xEyJFFVR41m5lNwH9OxpOitHchpOctaWeD7cV4id9C2moroxcymNysXEfoXIoZtI05koxAyM56yt8X643xc76VtMRXWX6lJCSw7ddUA3M6bHoFiVIg53iufEFlFR9rQFdNeDohzTI5pSZYOWJSl2ULSyNB0VJPvYj5mkL4XkOqDznCSPTCxCMb0L2BSy3yFtcJ1yAbhXEPnDbEdglT1JqS3l4j6gE3nDsZ/AKrtDFptDJ/KIYz+BVbaIqQ0DOoXFXOZYHPsJjHfI9zGgU7ggbGK0z77SxiOz4x3yA6MmqMd+FbPbonchV/SZWelFZsVabFTRIia0LCxiC92b0CmNkM8sTZnLZGpnMhbqK2YPbmWlGQC9fLn5t9buzqhIH/vFFvoUYuyPEXIJeKoWeoX7hMzESn2xBxcE2EIvRMjW9I6QA0qpcpkx6qFkVuqrktkoOTtDDOiexLggQgbhVKN9lQSGYKzUVwWzUXLPC2BA9yTGBRE6CKfIZVYQGIKapb5CNjcrmI2SvTM0KhcT++U+h55jVN1KLjQ31sNkpq2vGPVc+GyUFLsSo9T90LPJGVAKvyA6Yz1MZpr64iDmxFJUWVtA514u06hs7wiqFDedmViKfcK4l0toVgaZiGLiWMXEcq8CZkCfBk90qkEFg5gx5FzjxIA+DZ7oVIPczU2aGAP6NEo80S0sDXes2OrjknpXGNCnVdKJnns1hHOsPkOKvbN2w1kuxFk7M2L1GVHJo+hmnuUiIreKyGsisikiD4z4zOdF5EUROSsiz85SYEqMs3ZmwuozIvsyzfzGBnQR2QvgEQC3ATgC4G4ROTLwmY8CeBTA36jqpwF8MXxRd6u8dxUOZ+3MhNU3hRgXL++snVroNwLYVNXzqvougFMA7hj4zD0AnlLVLQBQ1V+FLeZuzFsGxFk7M2H1TSjWxcs7a6eAfhDAW33vt3tf63cdgKtF5EcickZEvhSqgKOwdxVQibN2EmL1TSjWxcs76/hBURH5IoBbVPXveu/vBXCjqn617zMPA1gGcDOADwH4KYC/VtXXB37WMQDHAGBhYeHom8NGkjriqmQip2JevOvrzY1ha6tpma+uFndnnXVQdBvANX3vDwG4MOQzz6jqO6r6NoAfA7hh8Aep6klVXVbV5fn5+W6lH4G9KyKnYl68JU0nnkKXgP4CgGtF5LCI7AdwF4CnBz7zPQCfE5F9IjIH4LMAzoUt6pWq711xRJi8qv7ijWdsQFfVSwDuB3AaTZB+UlXPishxETne+8w5AM8AeBnAzwA8rqo/j1fsyvOWHBEmz6q+eOPiwiKPuJKFxqkgl1yrthz6vtSFoQA435baDK6Y3OnBAQzqheNeLrPKkcvmiHCr6ocXOKe3Wgzos8iVy+ag0kgcXgB7cBVjQJ9FrpYQB5VGYuMU7MFVjIOis+DqJnN4SFDNroO14jNFY2FLyBweErAHVzEG9Fkwl20OD0lPjBWTqUebqx/dnoKqZnkdPXpUi7C2prq4qCrS/Lu2lrtE1eMhiWBtTXVuTrXJaDWvubl4lZv69zkCYENHxFXm0IlovNSL2bh4biTm0IloNqmnQjqeepkzU1REQGeqjSiy1KPNTke3c6+DcB/Qc1cgURVSjzY7Hd3OvQ7CfUDPXYFEVUg9FdLp1MvcmSL3g6JcSELUwx0Ws0sxllv0oKjTVFsVOLaRkPXcYyUnQ/ZM0aj5jLFfoeahc7qqTTwuiS0uXlnZO6/Fxdwlq+5kiL0OAi3z0N0HdFUuJLHIcnyZhJtzS2R4hYvkLlk5J4MRbQHdfQ6dbCphbMPVHleWF+KUcDIYUnQOnWwqYWzD1Qyq7MnbFiWcDE4woFMUluNLV7mnoE3E8jS/Ek4GJxjQJ1DJQH0QluNLV+4aljF2WAyhhJPBCQb0jqzPCrMoRXyJeZNlwzIgqzebwjCgd+Qqn1qJ2DdZNiwHsItqHme5dMSBenssT+yYmtXVnq6m/JSNs1wCcJdPrYCrQcsuLOf12EV1gQG9I+ZT7SnuJms5aBZ39ywTA3pHzKfaU9xN1nLQLO7uWSYG9AlwoN6W4m6yloNmcXfPMjGgF6imyQhF3WQtB83i7p5l2pe7ABTW4GSEnXE1gNeeeTsHyOIsF6Aph5Wy0FCctliYIqfyEdH7OG2xIpbH1cggT/k5T2XNhAG9MJbH1Xg9GmN53vsgT2XNiAG9MFbH1bxdj1XcfCzPex/kqawZMaB35OUCtzoZwdP16O3mMzVP+TlPZc2Ig6IdcBuL2XnaC6eagWVPf6inskY286CoiNwqIq+JyKaIPNDyuc+IyHsicue0hbXIU+vSKsu5/UHVNAat5ueG8VTWjMYGdBHZC+ARALcBOALgbhE5MuJz3wJwOnQhx4mdDqnmAo/I0/Xo6eYzE6v5uWE8lXWIZCnbUU+P3nkB+FMAp/vefx3A14d87h8A/D2AJwDcOe7nHj16NMgTsNfWVOfmrnyY+Nxc2Kez86HlYaytNXUm0vwb8hiFlOKconqEPp8AbOioeD3qG+9/ALgTwON97+8F8PDAZw4CeBbA3raADuAYgA0AGwsLC9P9NQNSBFte4PXxcvMh+0LHqLaA3iWHLsMa9gPvvw3ghKq+N6Y3cFJVl1V1eX5+vsOvHi9FOsR5b4+mUNQeMZRVypRtl71ctgFc0/f+EIALA59ZBnBKRADgAIDbReSSqn43RCHbLCwMH/wOne/kNhZENI1UMQroNsvlBQDXishhEdkP4C4AT/d/QFUPq+qSqi4B+A6Ar6QI5oCvwTaKy8taAfJp2vMraYwalYvRK3PftwN4HcAvADzY+9pxAMeHfPYJJBwUVWW+kzjOQXHNen6FjFFoyaFzYREVgetOKCZL5xd3W6Tica0AxeTl/GJApyJUsxiIsvByfjGgUxE4OE4xeTm/GNCpCFbXCnDmTRmsnl+DOChKFAl36aQYOChKlAF36aTUGNBpeswntPIyMyIonhNZdVn6T7TbYD5h57E+APMJPSmXfJvAcyI7ttBpOswnjGViZkTKFjPPiewY0Gk6VeYTJpN9ZkTqh6PynMiOAb00qVpkXlZaZJZ1G97ULWaeE9kxoJckZYvMRD6BWqVuMfOcyI4BPbWYLeiULbLs+QQaK3WLmedEfqO2YYz9Crl9rhux93gVGf6sK5EwP79iLrdo5p7CU7F+rDHLM0VjvaoM6LEfgMqnWUfhOi5aj07GeDjWbQGdS/9T2rOnOUcGiTSjZrPiWvMoLO2FTXF5ONZc+m9F7JxmqBwmV/tdgbPx6uH9WDOgp5RiFsCs8+RSz112gLPx6uH9WDOgp+RhFgBX++3C2Xj18H6smUOnK8XO8zu1vt7c07a2mtba6qqt+zCFY/1YM4dO3Xnvc0aSdcVnYLGHSLwPwXg+1q4DuvcTxyTvfU5qFXuIhEMwmY2azxj7Nes8dA/zRd3i3OVoclctl0L4hxIXFpk5cXJfoeSGhUZI7MXEXKzcLkS4aAvoblMuJuaLsn9JE7AwgSj2EAmHYEZLES7cBnQTJ46FK5TcsNAIiT1EwiGY0VKEC7cB3cSJY+EK7YojyNlZaITEXgrhYalFLknCxahcTOxXiM25sqevzSTyx7CQvO0i+wGNy8th8MzyKRQqXKDEQVETvFyhHm48XupyRpYDjnfWT6FQ5WNAj8nDFeph6oHBm46HQ0sfMHgK7RJ7lguX/tfAw56gxrYc4E7E/hg7haLh0v/amRhBHsPCiGEfTmDyx9gplAUDeg08TD0wdtPxNIGJGsZOoSwY0GthfcchYzcdtvb8MXYKZcGATpOLNafd0E2HrT2fDJ1CWXQK6CJyq4i8JiKbIvLAkO+viMjLvddzInJD+KKSCZVsd8DWHnk0NqCLyF4AjwC4DcARAHeLyJGBj70B4M9V9XoADwE4GbqgRfO0irOi0cLaW3vkz74On7kRwKaqngcAETkF4A4Ar+58QFWf6/v88wAOhSxk0Qbnx+20eAGbEYSjhURmdUm5HATwVt/77d7XRvkygB/OUqiqeGvxcrSQyKwuAV2GfG3oaiQR+QKagH5ixPePiciGiGxcvHixeylL5q3Fy9HCunhKB1KngL4N4Jq+94cAXBj8kIhcD+BxAHeo6q+H/SBVPamqy6q6PD8/P015h3J9znlr8XK0sB6VDIAXZdSeADsvNHn28wAOA9gP4CUAnx74zAKATQA3jft5O69Qe7lY35BnLPd/ABXLw+YoFcIsTyxS1UsA7gdwGsA5AE+q6lkROS4ix3sf+yaAjwF4VEReFJFkm7R4S0HvwhZvUtl6cx67kd7SgeR/t0UPGwlSBwm2NszWGfLaC2ML3SSU+EzRHd5S0DREolxttt6c124kB8CDi95RGxXpY7+YQ6f3JWoJZuvNee5GclP4YFI84MJ9C50p6ClZyukmytVm68157kZyuWwwfEh0RzznJmRtOlqigJctg5DjF1u6YQcQ8s/JVTV8SDTFYW2wK2HeLFsGIeUvLiwPGfLPyVk1fEg0xWExp8tcbTjWbtgzCvnn5Kwa5tBLlbs7bDGny7xZOIXNHw/55+SsmhTjfQzoqVnIX3M6Wtks3rBnEPLPyV01sdstDOipWZiTzKlB4YTobYXusRV2ww755xRWNbuNysXEflWbQ7eYvw6hxhx4iKRorFG6wo5HyD/He9WgJYcuzffTW15e1o2NZFu+2LG01KRZBi0uNn0wjwYf0gE0zZ7SW/0hjmWJ5wNFJSJnVHV52PeYchmH3eHxLKSRcggxwlbYACblxYDeJsYAZon561qDUogRttyjdFQUBvQ2sVqepU3RqzUohehteemx5Z5qS50woLepteU5KS9BKbQQvS0PPTYLU22pEw6KtuGAVXfr603PZWuraZmvrtoKSjQ9XgemcFB0WrW2PKdRWhqJPsCeqhtuA3qSlJ6H7jBRbLWOkTjkMqAnTemx5UltahgsZE/VDZcBvdZpz2RMLYOF7Km64TKgM6VHJqRqWVjoBbCn6oLLgM6UHpmQomVRSy+AgnAZ0JnSIxNStCwKzC/m6nBY6OhEL8OoXbtiv2bdbdH7jmmlSXU8TB33FM8zK2x3zlyPgLPwVL4UTyxyG9BrYiqIDZHqYrFwUQ4tVMyDw8fJuf69McrAgD6G5YBpMogNSHWxWLgok/NwAkwgV4fDQkcnVBnaArrLHHpI1secPKRQU806qnJ2U2FTBnNNaLAwkSJFGaoP6NYDpocglupisXBRZlHQlMFcExosTKRIUoZRTffYLyspFwtdsTYe0gxV59BpYrlSnBZSqyHKAObQR7MeML0EsSpnuRBl0BbQq98+18PjMLkzLRHtaNs+d1/qwlizExgtB8yVFVvlISKbqg/oAAMmEZWh+lkuRESlYEAnIioEAzoRUSEY0ImICsGATkRUiGzz0EXkIoA3s/xyuw4AeDt3IQxivQzHehmu9HpZVNX5Yd/IFtBpNxHZGLVgoGasl+FYL8PVXC9MuRARFYIBnYioEAzotpzMXQCjWC/DsV6Gq7ZemEMnIioEW+hERIVgQCciKgQDegYicquIvCYimyLywJDvr4jIy73XcyJyQ45ypjauXvo+9xkReU9E7kxZvly61IuIfF5EXhSRsyLybOoy5tDhOrpKRL4vIi/16uW+HOVMatSTL/iK8wKwF8AvAPwBgP0AXgJwZOAzNwG4uvfftwH4z9zltlAvfZ/7DwA/AHBn7nJbqBcAHwXwKoCF3vvfzV1uI/XyDQDf6v33PIDfANifu+wxX2yhp3cjgE1VPa+q7wI4BeCO/g+o6nOq+r+9t88DOJS4jDmMrZeerwL4VwC/Slm4jLrUyz0AnlLVLQBQ1Rrqpku9KICPiIgA+DCagH4pbTHTYkBP7yCAt/reb/e+NsqXAfwwaolsGFsvInIQwN8CeCxhuXLrcr5cB+BqEfmRiJwRkS8lK10+XerlYQCfAnABwCsAvqaql9MULw8+sSg9GfK1oXNHReQLaAL6n0UtkQ1d6uXbAE6o6ntNo6sKXeplH4CjAG4G8CEAPxWR51X19diFy6hLvdwC4EUAfwHgEwD+TUR+oqr/F7ls2TCgp7cN4Jq+94fQtCCuICLXA3gcwG2q+utEZcupS70sAzjVC+YHANwuIpdU9btJSphHl3rZBvC2qr4D4B0R+TGAGwCUHNC71Mt9AP5JmyT6poi8AeCTAH6WpojpMeWS3gsArhWRwyKyH8BdAJ7u/4CILAB4CsC9hbey+o2tF1U9rKpLqroE4DsAvlJ4MAc61AuA7wH4nIjsE5E5AJ8FcC5xOVPrUi9baHotEJGPA/hDAOeTljIxttATU9VLInI/gNNoRur/RVXPisjx3vcfA/BNAB8D8GivNXpJC989rmO9VKdLvajqORF5BsDLAC4DeFxVf56v1PF1PF8eAvCEiLyCJkVzQlVL3laXS/+JiErBlAsRUSEY0ImICsGATkRUCAZ0IqJCMKATERWCAZ2IqBAM6EREhfh/Lh1VErq0arcAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "from scipy.io import loadmat\n", "pointsClass1 = loadmat('KernelPointsEx2class1.mat')['PointsEx2class1']\n", "pointsClass2 = loadmat('KernelPointsEx2class2.mat')['PointsEx2class2']\n", "\n", "\n", "plt.scatter(pointsClass1[:,0], pointsClass1[:,1], c='r')\n", "plt.scatter(pointsClass2[:,0], pointsClass2[:,1], c='b')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 3. From polynomial fesatures to the Gaussian kernel\n", "\n", "Use your gradient descent iterations on the $\\mathbf{\\lambda}_i$ to learn a classifier for the dataset below by relying on the Gaussian kernel. " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD7CAYAAAB68m/qAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAc6klEQVR4nO2df6hl1XXHv2ucDvQ1aZTONDSj896kaJMRYqlP00gDpv1DnT9qAxY00wgSGCY/SvpHQVOhDZSh7R+F0BojIkGKj0qxkphiTAshScGa+AbUaEQ7muQ5seCzCS3oH6m6+se5b+a+6z3nnnvO/rHW3t8PHGbuveedu+86e3/32muvvY+oKgghhPhnT+4CEEIICQMFnRBCCoGCTgghhUBBJ4SQQqCgE0JIIVDQCSGkEBYKuoh8WUReEZGnWz4XEfk7ETktIk+JyG+FLyYhhJBF9PHQ7wVwbcfn1wG4eHIcB/Cl8cUihBCyLHsXnaCq3xGRtY5TrgfwD9qsUHpMRM4XkV9T1f/quu7+/ft1ba3rsoQQQmY5derUq6p6YN5nCwW9BwcBvDT1+szkvU5BX1tbw+bmZoCvJ4SQehCRH7d9FmJSVOa8N3c/ARE5LiKbIrK5vb0d4KsJIYTsEELQzwC4aOr1hQBenneiqt6tquuqun7gwNwRAyGEkIGEEPSHANw8yXb5bQD/syh+TgghJDwLY+gi8o8ArgawX0TOAPgLAL8AAKp6F4CHARwFcBrA6wBuiVVYQggh7fTJcrlpwecK4NPBSkQIIWQQXClKSEVsbABra8CePc2/Gxu5S0RCEiJtkRDigI0N4Phx4PXXm9c//nHzGgCOHctXLhIOeuiEVMLtt58T8x1ef715n5QBBZ1kJWgIIGI8oYRQxdbWcu8TfzDkQrIRNAQQMZ5QSqji0KGm7PPeJ2UguR4Svb6+rlz6Xzdra/MFZnUV+NGPcl4s2aWTMtsxAcDKCnD33b46ptoRkVOquj7vM4ZcSDaChgAixhNKCVUcO9aI9+oqINL8m1LMSwhbWYeCXhHWGlTbUH9QCCDoxZJdOjnHjjWjirfeav5NKebHjzcjHdVzYavcdbA0KOgBsSaY01hsUCdPNkP+aVZWmvfzXizZpU3XmZAwwyYRqprluPzyy7Uk7rtPdWVFtZHL5lhZad63wOrq7rLtHKurect1331NGUSaf0fZK+jF4l/aep0Jicj8+ieSu2T+ALCpLbrKSdFAWJ8427OnaUKziDTDb5KeWHVmY6PxfLe2mrDQyZP5Jz2ttw9PcFI0AdYnzkqKA5dCjDpjMbQGxA1bkXNUK+ihY5fWBZMNyh4x6ozVWHXuDJtqaIvFxD5yxtBjxC49xEMjhpjJAGLUGcaqywcdMfQqBT3WBCEFMyNOjR+62FYnv0k4ugS9yklRThAWBpdAnoWmKB9Ois5gPd5NlsRq4DgDjFXXTZWCzgnCwrCeYpSYXKtBSX6qFHR6MYXBIVdV1LK6dghVCjpAL6YoOOSqBqt59laoVtBJQUQectEjtAOnS7qhoJMyiDTkoke4m9ydG6dLuqGgZyR34yCLoUd4DgudW47pElfttC1BPfZR2m6Ly+JhZWlsPKwF4srLc1hYtJS63Vhsp+BKUXtYaBw5Cd5QIvUOtd+naax0bikdAYv3v0vQq1wpaoHaV6sG3U414vJIrrw8R41b4Fpsp1wpapDaU6eDTm5FDHRzzcI5aswO9dZOKeiZqLFxTBO0oUROffC2ZiHWJF6NnZu7dtoWi4l91B5DV/UxKRiLoDF0i4HOTFicxPOOtXYKTooSiwRrKI5ULLY4sG8rny5BZ8iFZMuzDRbKcBILSJHHzYU3dcMsl8phFkc6UmSJ1JiJUhvMciGtcCVkOlJ4z5Ym8VytsCwECnrlcIiejhQpcFaiTxa2CaiRXoIuIteKyHMiclpEbpvz+btE5Gsi8qSIPCMit4QvKomBtzzbpTHkJqbyni2kWXLkl4eFgi4i5wH4IoDrABwBcJOIHJk57dMAfqCqlwG4GsDfisi+wGUlEbA0RA+OMTfRivecAo788tDHQ78SwGlVfVFVfw7gfgDXz5yjAN4pIgLgHQB+CuCNoCUlUShaZAy6iRa85xSkHPkZGoRlp4+gHwTw0tTrM5P3prkDwPsBvAzg+wA+q6oV7EhSBsWKDN3EbKQa+RkbhGWnj6DLnPdmcx2vAfAEgPcA+E0Ad4jIL7/tQiLHRWRTRDa3t7eXLCohS1L8BIFdUo38DA7CstJH0M8AuGjq9YVoPPFpbgHw4GQh02kAPwTwvtkLqerdqrququsHDhwYWuZkWBvKWSuPeYqeILBPipFfikGYq3bXtoR05wCwF8CLAA4D2AfgSQCXzpzzJQCfn/z/3QB+AmB/13WtL/23tprcWnncYG0jDhKU2FsdWGx3GLuXC4CjAJ4H8AKA2yfvnQBwYvL/9wD4VzTx86cB/NGia1oXdGt7YlgrDwkH+5zhxBZci+1utKDHOKwLupWns1gtTwiCbs6VQRFDfK1FD9AbMW+/xXZHQR+AtZ7ZWnnGEkzIMiliqK8t7b6WhsX7Q0EfgDXPyVp5xhKsoWRqcaG+1qIHSM5hsd1R0AdiLbZprTxjCCZkmRQx1Nda8QBLqluhsWYbCjoxBz30BgseoIUykP50CTp3WyRZCJYininXPNTXWth6gYtzCqJN6WMf9NAJs1xslIFxfF+gw0Mv6olFGxuNV7G11azuPnmyoH1JCJkh1NOm+JQjX1TxxCJu0kNqI1SohDsklEMxgu4xDuhqjwjvFGjsUPuYxI7jF2h6u7TFYmIfoWPo3uKAzCxISKHGtpLy2EWhps8Kaoihe4sDeiuvawo1dqgYekwKNX1Wqoihe4sDWn32QpHDY6vGHomFlMdFFGp6sxQj6B4q9zQhn70QSoSLnVgu+EEX1p82VbDpbdIWi4l91J6HHiq2GDJG6SEmOwgGcrMR2/QW1gKkBlz6b5MQlTGkCHubWF6KGlu+EWKZvtZ+moJeMCFFuFgP3RHsd/oTq75avwddgl5MDL1WQsYovU0sl0axcxiRiDHh6v0eUNCdE1KEvU0sWyLExLTHxXE5iTHh6v4etLnusQ+GXMJhfYgYDSM/PFQst+g5jAjEiKF7uAdgDJ0Uh6EZsVCxXM5hLE/oPt3DPegSdIZcSHSiLFYyNDYOFcvlHMbyhM7DD30Pki/Ua1P62Ac99DqI5kgbGhuH9OqMRJGqJtQ9iFX3UcNeLsQm0fbyMLRJiIc9VUh6YlXRKvZyITaJtpeHofgEs4PIPHLsY0NBN0wJG2VF28vDmIpa31OFpCfHPjYU9BZyi2noBQ65fk9UR3qMiua+waR4sgwi24LrsQ/Lk6IWMuJCT7Tl/D3mJvpyG2QEMW1p7j4VQAybgnnoy2EhF5V7tETEqUFi9kOO+7jq6BJ0ZrnMYc+epkrPItKM7lMQcobcwu8xhVODxEzsMZQ0RBbALJclsbApf8j4m4XfYwqnBomZNcEnC5UBBX0OFjLiQiZxWPg9pnBqkJj9UK4+jnPTgWmLxcQ+LMfQVcubICrt94zGoUFKi6Ezbj8MMIZOSBlsbDTb1WxtNd7zyZPhct5jXnsejNsPoyuGTkEnPkmtPiQ4Tuems8NJUVIW3h8rQwC4nZs2TS9BF5FrReQ5ETktIre1nHO1iDwhIs+IyLfDFpOQKQxtnUuG43Ru2jQLBV1EzgPwRQDXATgC4CYROTJzzvkA7gTw+6p6KYA/DF9UQiYwx64IjG3HUwR9PPQrAZxW1RdV9ecA7gdw/cw5HwPwoKpuAYCqvhK2mGQsRaWHORmrF2XzSHBTs7D0EfSDAF6aen1m8t40lwC4QES+JSKnROTmeRcSkeMisikim9vb28NKTJYmR8g5qpg5GKszzE+y0JbPuHOgCZ/cM/X64wD+fuacOwA8BuCXAOwH8J8ALum6rvU89JJIvXVJkvxi43nkTreLIQ7AyGeKngFw0dTrCwG8POecR1T1NVV9FcB3AFw2tJMhYUkdck4yZ2l8rM4wP8lBH0F/HMDFInJYRPYBuBHAQzPnfBXAh0Vkr4isAPgggGfDFrU8UsVYU4ecKWZuwvxkQinzHQsFXVXfAPAZAN9AI9L/pKrPiMgJETkxOedZAI8AeArA99CEaJ6OV2z/pIyxpg45U8xchPnJhKLmO9piMbGP2mPoOeLaqULObvfoCGwk42F+MsHbfAf4gIvdWGhoIR9gYZHsNl62AI56oey2LQxvbZGCPoWVduvNK3DFkJvs5IZYqb8l4eTWn4WCPoWVm8eGGZEhN9mJm2al/paEt7bYJejVbc5lJQODy54jMuQmO5nJtVJ/S6KktlidoFtqt8ZTqf0y5CY7SUuxVH9TkCqdMEZbzJIK2ea6xz5qj6GTiAy9yQ5mG2uqv55/a8yygzH03Thot2QsBd/kgn/aLjzPF8Qse5eg84lFxD58OlGVeH6iUcyy84lFxC9FLeMjy+B5viBX2SnoleJm7wo+ncgEOeqLk3nquWQre1ssJvZR+9L/nLiabHKSH14yOeuL5/mCWGUHY+hkmrW1JnIxy+pqk7JlCleF7Ye3KYECb4FrGEMfiZvwRE9cLU6xNO4OUBE8Tgm4qi+10+a6xz68hFxchSd64i4dzMK4O1BFcGd79VnmkgFDLsMpcbi54yVOzzWurPhd7pyEQBXBYyoe64stGHIZQYnDzZL2rkhGoIqQIp0tdIiQ9cURba577MNLyIXDzcVYiIjMI2i5AlWE2CG8EkOEZDfg0v/hsIF0Y9U+wcsV8IIxO0A6IOVDQR+JVQ/UAlYFJEq5HFQEpu3Hw8rtp6A7wUqFWYbkAtLTSLUKm9UO1juWRqJdgs5JUSN4zE8GEu9ZsYSRPO8DMgZLafsl4WYHijalj33QQ9+NV88qqeeyhJEseVSp8TjSs46lER/oodvHa3pk0pS2JYxUc6odn4QVHi8jvioE3cPSfS8VZh7JBGRJI1HY7OGhLc7DTSirzXWPfaQKuXgZenspZxT6xgiqNpJ/vN8+K6Es1Jzl4ik2baXCJGXZVp7CSFXeiPh4aouW6RL04vdy8bh3RgjcbNFqbbMcblwSjVrbYmiq3svFc2x6KK5SIK3NBhvKT/Mab26jxraYmuIF3c1kRkAMadJirLVyIx2Mq065JzW2xdQUL+g1pq8Z0aR+WGvlQzuYwO60q065J6nbYmkjnF60BddjHzUsLMo1t+Zu8snSJOSQVIwI6RuWFrJ4xHtGTReoOcslF7kfrFtqZV6WQX3Fsn8UoQd11ykbo2T7UdAzkLtCWXJ6c5GsY4vgTrNTHkfJI5wuQS8+bTEXTNHKT7KMyEhf5Cb11CDWsmFDMjptUUSuFZHnROS0iNzWcd4VIvKmiNwwtLClYC15o0aSTQ5HmtjNuXWB9wlFa3PtyWhz3XcOAOcBeAHAewHsA/AkgCMt530TwMMAblh03dJDLhwy5ydp2KugGFcpdbegW7ILjAm5iMiHAHxeVa+ZvP7cpCP4q5nz/gTA/wG4AsC/qOoDXdctPeQCcMicGy76HEbJ4YoSGBtyOQjgpanXZybvTX/BQQAfBXDX0ELmJsYQs6Td/jwOwWtcgxACV+sYyC729jhH5rw369Z/AcCtqvqmyLzTJxcSOQ7gOAAcMhRMnvXkdlblAWz8gG/7HDtmv4zWOHRovoduqMmSFvp46GcAXDT1+kIAL8+csw7gfhH5EYAbANwpIn8weyFVvVtV11V1/cCBA8NKHIESV+WFJKt9PA4NnFPthGIB9BH0xwFcLCKHRWQfgBsBPDR9gqoeVtU1VV0D8ACAT6nqV0IXNhYeh5gpdS6ofZYpuLUNTSrpXFKFqioxZ1raZkunDwBHATyPJtvl9sl7JwCcmHPuvXCW5ZJ7EdCypM5CCGafZQtu6cYYTP3wnMVh0Jy7ymbZruBK0W4sV655pNa5YPZZtuCWlvtZ6lzUX52dxZg5z+LBrhT0HljvlafJoXNB7LNswS21ekudi9oyzRCMmfMsHuzaJejFb5/bF08phjlWoQaxz7IFtzQ7Z2zpr8d5n2mMmfMs3u1KQXeIJZ1bimULbimR3JjRrQpiX4yZ8yze7cqQi1M8hYh24bbgOr7sAX+7h1jvIixWBQ92BWPo+bBYaUkGIigF61YcrNu1S9C5fW5EuJcIOQs3SCGBGL19LhkGV6AawcIKFu+zbcQFFPSIsA0bwMpqU/ezbcQDFPSIsA0PILQ3bWWYZDWtgxQFBT0i1tuwhUjE2woU2pu2MkyylIJJyqVttjT2wSyXvJhMz4qxTM/D0j8yGKvtKyZg2uJuaqwEs5jUuRjrwU32XCQEtd7aLkGvLuRiZY4sN1YiEbuIMelQeagjdVgt5fdZmR4xRZvSxz5yeegmPdMMmLSDZ5fL4LAvtTlTf5/VDb66CFFNUErIJYQxPFaCGJjVToPCuBCjxkzdaZf+fWMJVU2KEPRQxvBWCWISRTs9CvJYjFaq1M5L6u8z2o+2EqqaFCHooYzhrRK4wopxU3cqRod9NXjMnvyHUNWkCEEP2WY8VQJXWPBUx3YqQyqHhd89h9Jj6DGJoRH00CMYg0TEgqc6pqIMVaSQShZYSVI7LyU4S7E6JsbQIxiDRMRCrzumUxnbGYxVMlZyE8SsxsxymaKE3r9oLAjSmNaYe4RhoUMk2avBIroE3dXCIk/P/awSC4t4xmygk3s3NZOrveojdzUYgytBJw7I3euO6VTaOoOjR9Msf/SsJAVhfVO9Ttpc99hHLZtzEWfMxvU++cl0YSQLISuiqrbDu+Aj6IhrNjaaDTq2thpv9eTJdJ5/6kfH5fytxAVdj6CjoBPb5H4w6549ja88i0gTViIkMXymKLHBkK34cm+pFyqube5pIqREKOgkDUP3Lc6d+RFihsz4ns3sawqiLbge+/A8KWp5wkTVaPmG5lhbyM0ea1ALv6EFzsP6A6UsLLKA9QZgtnxDV2uY/UFLYHiliuG+hrTQJegMuSxJ7pDuIsyWb2gs2sJipXksE6cYG4ePGBPJHdFiuCcwbUof+/DqoRt2tlTVcPlK8LR3WPa3jPntke2W00PPsRukuVDkAMCQSzisD1FNl6+UFjXEyEN/e+QbmrOfTVlXS/Inqhb00BpivWJEK59zMQ5a/JTDoATflevWpjSjaUdnSUYLOoBrATwH4DSA2+Z8fgzAU5PjUQCXLbpmCkGPua+xZW0LXr6UvVgE4wYvfkp1KEmJZkj508yGIgcwStABnAfgBQDvBbAPwJMAjsyccxWACyb/vw7AdxddN4WgF9wW0pLKkJE6juDFT93BWR4SjiDlTytJC8YK+ocAfGPq9ecAfK7j/AsA/GTRdVMIekm9clZSGTJSq4tS/JTDNOtDwhGk+mkl9YtjBf0GAPdMvf44gDs6zv/T6fPbDnrojkhlyEgdB+sBUY0zn5ajn+0S9D556DIv23HuiSIfAfAJALe2fH5cRDZFZHN7e7vHV4/D4r7GLvNuUxky0n7gFusBSU/IrfrN7ubQpvQ7B3qGXAB8AE2s/ZJF19REHrqqrdGq62FfCkNGNJClenAWk4Uifcg56sPIkMteAC8COIxzk6KXzpxzCE0GzFWLrrdzeM1DHwOH/j3wJnJDy+u6dyc55+dGCXrz9zgK4PmJB3775L0TAE5M/n8PgJ8BeGJytH7hzlGjoHOStjDGiHLo3j1gR+itT82BWw891lGjoNNDL4wxNzRk7x7Q2+fAoR857dQl6NycKyHFTs65nOkNwJidrUJOAAfckc3s5m7GsLpnHD30xBQ3nK3ZpRvjoYe0W0Bvn2FB+4Aeuh1Cpk6ZoGaXbsyQK6SLF9Dbj5Q5ShJBQSfjCL2htqfwzVhRDtW7B4zlFRsWrIU21z32UWvIpThCzvTWHL4ZC7NcqgEMuZSDOQc2pEsXOHxjzlYxCRjLKy4sWBEUdEcEX24cQvFCxoIDhm/MLs0mJCZtrnvsgyGX5Qmax24xvBHwBzLnf4Lz+Inz4kcBXFhUBkFTyiwqXsBOJmn63RDVSfE3FjvtJYhd/BydRYjvpKAXQlANtppwHKiVJeuvhqhOqr9J8DzSmIIYs/g5+rpQ30lBL4SgldCihx6QZA12iB1T/U3ETjuFfWP6HDmqf6jvpKAXRDCvaEyLdBLYTFLMIaqT6m8iqlYKQYz5HTkGqKG+k4JO5jM0jltaYHMMlj30iPcqhSDGrGr00CnoRHV4rewj1B4n8SzH0Hf+LkIHmUoQY/XvjKFT0P0SslUMcc361mSvcX2rWS4R8dj3zlJilos0n6dnfX1dNzc3s3x3VeyssJlegbmyMnzxz9pas0pnltXVZlnhmL/Zs6fRhllEmmWLxBQbG80i3q2tZvOukye5qjQFInJKVdfnfkZBL5whAtzFkA6ir1CHLishBdIl6FUs/a9qT49ZQu+GOGSpf989WbnVHyGjKF7Qq9/TI8YG18vu3tRXqM0+BoYQHxQv6DU/fwGADa93GaFOvNVf1aM3UhzFC3roiIM7rHi9BvdkrX70FhF2lHkoXtC9PVIrSkMwKKYWqH70Fgl2lPkoXtAtRBz6woaQlupHb4jjQLCjzEfxgm4l4tAHNoS0eBu9AWEFOJYDwY4yI20rjmIfXCn6dlJuGGRo0WFQlvldMVY7xrRr6PLGWpjrdcGvF8Cl/z5IuT9GjmXbsTuRoVukhCpTbLuGrh+xHIgStgWwDAXdCakaQg4PKsVvy+0Zxv7+0AIc+wESJY4ALUBBd0SKhpBjL+gUYpv7IUyxvz+0DelJ+6RL0IufFPVGigzDHJOBKSbKck9yxv7+0BlbnhIGSD8o6BWSI5UzhdjmTlGN/f0xBJhLFAqjzXWPfTDkkpfUMc5Uw/vcsdvc30/KB9wPnViA+2cTMp6u7XP3pi4MqZdjxyjghMSEMXRCCCkECjohhBQCBZ0QQgqBgk4IIYVAQSeEkELIlrYoItsA5jzivSr2A3g1dyEMQ/t0Q/t0U6p9VlX1wLwPsgk6AURksy2flNA+i6B9uqnRPgy5EEJIIVDQCSGkECjoebk7dwGMQ/t0Q/t0U519GEMnhJBCoIdOCCGFQEFPgIhcKyLPichpEbltzufHROSpyfGoiFyWo5y5WGSfqfOuEJE3ReSGlOXLTR/7iMjVIvKEiDwjIt9OXcac9Ghf7xKRr4nIkxP73JKjnElo21eXR5gDwHkAXgDwXgD7ADwJ4MjMOVcBuGDy/+sAfDd3uS3ZZ+q8bwJ4GMANucttyT4AzgfwAwCHJq9/NXe5jdnnzwD8zeT/BwD8FMC+3GWPcdBDj8+VAE6r6ouq+nMA9wO4fvoEVX1UVX82efkYgAsTlzEnC+0z4Y8B/DOAV1IWzgB97PMxAA+q6hYAqGpNNupjHwXwThERAO9AI+hvpC1mGijo8TkI4KWp12cm77XxCQBfj1oiWyy0j4gcBPBRAHclLJcV+tSfSwBcICLfEpFTInJzstLlp4997gDwfgAvA/g+gM+q6ltpipcWPuAiPjLnvbmpRSLyETSC/jtRS2SLPvb5AoBbVfXNxsmqij722QvgcgC/B+AXAfyHiDymqs/HLpwB+tjnGgBPAPhdAL8O4N9E5N9V9X8jly05FPT4nAFw0dTrC9F4CrsQkQ8AuAfAdar634nKZoE+9lkHcP9EzPcDOCoib6jqV5KUMC997HMGwKuq+hqA10TkOwAuA1CDoPexzy0A/lqbIPppEfkhgPcB+F6aIqaDIZf4PA7gYhE5LCL7ANwI4KHpE0TkEIAHAXy8Eq9qmoX2UdXDqrqmqmsAHgDwqUrEHOhhHwBfBfBhEdkrIisAPgjg2cTlzEUf+2yhGb1ARN4N4DcAvJi0lImghx4ZVX1DRD4D4BtoZuS/rKrPiMiJyed3AfhzAL8C4M6JF/qGVrKpUE/7VEsf+6jqsyLyCICnALwF4B5VfTpfqdPRs/78JYB7ReT7aEI0t6pqibswcqUoIYSUAkMuhBBSCBR0QggpBAo6IYQUAgWdEEIKgYJOCCGFQEEnhJBCoKATQkghUNAJIaQQ/h8ErJ+G8H2BJgAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "from scipy.io import loadmat\n", "pointsClass1 = loadmat('KernelPointsEx3class1.mat')['PointsEx3class1']\n", "pointsClass2 = loadmat('KernelPointsEx3class2.mat')['PointsEx3class2']\n", "\n", "\n", "plt.scatter(pointsClass1[:,0], pointsClass1[:,1], c='r')\n", "plt.scatter(pointsClass2[:,0], pointsClass2[:,1], c='b')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part II : Maximizing the margin\n", "\n", "#### Exercise 1. The hinge loss\n", "\n", "Consider the dataset below. We would like to learn a classifier for this dataset that maximizes the margin (i.e. such that the distance between the closest points to the plane is maximized). We have seen that one can solve this problem by means of the constrained formulation\n", "\n", "\\begin{align*}\n", "\\min_{\\mathbf{\\beta}} \\quad & \\|\\mathbf{\\beta}\\|^2 \\\\\n", "\\text{subject to} \\quad & y(\\mathbf{x}^{(i)})t^{(i)} \\geq 1 \n", "\\end{align*}\n", "\n", "where $y(\\mathbf{x}^{(i)}) = \\mathbf{\\beta}^T\\mathbf{x}^{(i)} + \\beta_0$. We might sometimes want to use a (softer) unconstrained formulation. in particular, when selecting this option, we can use the following function known as the _Hinge loss_ \n", "\n", "\\begin{align*}\n", "\\max(0, 1-t^{(i)}y(\\mathbf{x}^{(i)})) = \\max(0, 1-t^{(i)}(\\mathbf{\\beta}^T\\mathbf{x}^{(i)}+\\beta_0))\n", "\\end{align*}\n", "\n", "For such a loss, we can derive a softer, unconstrained version of the problem as \n", "\n", "\\begin{align*}\n", "\\min_{\\mathbf{\\beta}} \\quad & \\|\\mathbf{\\beta}\\|^2 + \\frac{C}{N}\\sum_{i=1}^N \\max(0, 1-t^{(i)}(\\mathbf{\\beta}^T\\mathbf{x}^{(i)}+\\beta_0))\n", "\\end{align*}\n", "\n", "In short we penalize a point, only if this point lies on the wrong side of the plane." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD6CAYAAACxrrxPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAT7UlEQVR4nO3db4hld33H8fd3N13ootXgTqXdzeyskqhbMNKMsS2VxgpNYqFBSCFxUAiWJdWID2O71BZkqYUWtES7LCEV2aWhaKoRoqEgasGmzSzkj2tQ1jXZLClkUqWl5kHY7LcP7p119nrnzpk7957zO+e8XzDM3nuPd3453vs5v/8nMhNJUvvtaroAkqTZMNAlqSMMdEnqCANdkjrCQJekjjDQJakjtgz0iHggIl6MiO9t8npExN9HxNmIeCoifnP2xZQkbeWqCsd8AbgP+OImr98KXDv8eRfwD8PfE+3bty+XlpYqFVKSNHD69OmXMnNh3GtbBnpmficiliYcchvwxRysUHosIl4fEb+Wmf816X2XlpZYXV3d6s9LkjaIiOc2e20Wfej7gec3PL4wfG5cQY5ExGpErK6trc3gT0uS1s0i0GPMc2P3E8jME5m5nJnLCwtjWwySpCnNItAvANdseHwAeGEG7ytJ2oZZBPrDwIeGs11+C/ifrfrPJUmzt+WgaET8E3ATsC8iLgB/CfwSQGYeBx4B3gecBV4G7ppXYSVJm6syy+XOLV5P4KMzK5HUNadOwdGjcP48LC7CsWOwstJ0qdRBVeahS5rWqVNw5Ai8/PLg8XPPDR6Doa6Zc+m/NE9Hj/48zNe9/PLgeWnGDHRpns6f397z0g4Y6NI8LS5u73lpBwz0tjl1CpaWYNeuwe9Tp5oukSY5dgz27r3yub17B89LM2agt8n6ANtzz0HmzwfYDPVyrazAiRNw8CBEDH6fOOGAqOYiBrMO67e8vJxuzrVNS0uDEB918CA8+2zdpZHUgIg4nZnL416zht4mDrBJmsBAbxMH2CRNYKC3iQNskiYw0NvEATZJE7j0v21WVgxwSWNZQ5ekjjDQVS4XUUnbYqCrTC6imi8vlp1koKtM7lI4P14sO8tAV5lcRDU/Xiw7y0BXmVxENT9eLDvLQFeZXEQ1P14sO8tAV5lcRDU/Xiw7y4VFKpeLqOZj/Zx64+rOMdClPvJi2Ul2uUjjOE9bLWQNXRq1Pk97fWrf+jxtsFarollDl0Y5T1stZaBPYrO7n5ynrZYy0Dfj8uj+cp62WspA34zN7v5ynrZaykDfTNua3XYPzY6LmtRSznLZzOLioJtl3POlcVbG7DlPWy1kDX0zbWp22z0kCQN9c21qdjfdPWR3j1QEu1wmaUuzu8nuIbt7pGJYQ++CJruH7O6ZH1s+2iYDvQua7B5qurunq1wHoSlEZm59UMQtwGeB3cD9mfnpkddfB5wEFhl04/xtZv7jpPdcXl7O1dXVacutUiwtje/uOXgQnn227tJ0h+dVm4iI05m5PO61LWvoEbEb+BxwK3AYuDMiDo8c9lHg+5l5PXAT8HcRsWdHpVY7tGk2UJvY8tEUqnS53AiczcxzmfkK8CBw28gxCbw2IgJ4DfAT4OJMS6oytWk2UJu4/YCmUCXQ9wPPb3h8YfjcRvcBbwNeAJ4GPp6Zl2ZSQpVvZWXQDXDp0uC3Yb5ztnw0hSqBHmOeG+14vxl4Avh14B3AfRHxK7/wRhFHImI1IlbX1ta2WVSpR2z5aApVAv0CcM2GxwcY1MQ3ugt4KAfOAj8G3jr6Rpl5IjOXM3N5YWFh2jJL/WDLR9tUJdAfB66NiEPDgc47gIdHjjkPvBcgIt4IvAU4N8uCSpIm23KlaGZejIh7gEcZTFt8IDPPRMTdw9ePA58CvhARTzPoork3M1+aY7klSSMqLf3PzEeAR0aeO77h3y8AfzDbokmStsOVopLUEQa6NC33WlFh3G1Rmoa7TKpA1tClabjLpApkoEvTcK8VFchAl6bhXisqkIE+Dw6WdZ97rahABvqseWOC+SjtIuleKypQpRtczENnb3DhjQlmb3RGCQxqwwaoemhHN7jQNjlYNnvOKNEclNbomwUDfdZKHyxr46fYi6RmrKs9owb6rJU8WNbWT3HpF0m1TlcbfQb6rJU8WNbWT3HJF0m1UlcbfQb6PJR6Y4K2fopLvkiqlbra6DPQ+6TNn+JSL5Jqpa42+gz0Punqp1japq42+txtsU/WP61Hjw66WRYXB2He9k+xNIWVle599A30vunip1gSYJeLJHWGgS5JHWGgl6aNKzklFcE+9JJ4WzNJO2ANvSRtXckpqQgGeknaupJTUhEM9JK0eSWnpMYZ6CVxJaekHTDQS9LV9cjSDjjxqzoDvTRuQiVdVuoW/qVeZAx0la/Ub4/mrsSJX6VeZMCbRKt03iC613btGoTmqIhBI7YJTd8H3ptEq71KrKKpNiVO/Cp5drGBrrKV/O3R3JU48avEi8w6A11lK/nbo7krceJXiReZdQa6ylbyt0e1KG3iV4kXmXVuzqWyeZclFajU+8QY6Cpfqd8eqTCVulwi4paI+EFEnI2IT2xyzE0R8UREnImIb8+2mJLaxuUD9dsy0CNiN/A54FbgMHBnRBweOeb1wOeBP8rM3wD+ePZFVWP8ZmqbSl5802VVaug3Amcz81xmvgI8CNw2cswHgIcy8zxAZr4422KqMX4zNQWXDzSjSqDvB57f8PjC8LmNrgOujohvRcTpiPjQuDeKiCMRsRoRq2tra9OVuI+arCH7zdQUXD7QjCqBHmOeG12MexVwA/CHwM3AX0TEdb/wP8o8kZnLmbm8sLCw7cL2UtM1ZL+ZmoLLB5pRJdAvANdseHwAeGHMMd/IzJ9l5kvAd4DrZ1PEnmu6huw3U1Nw+UAzqgT648C1EXEoIvYAdwAPjxzzVeDdEXFVROwF3gU8M9uiNqTpAcGma8h+MzWFkhffdNmW89Az82JE3AM8CuwGHsjMMxFx9/D145n5TER8A3gKuATcn5nfm2fBazG60996dwfU98lcXBy/tVtdNWQX9mhKLh+on9vnTtL0Ppng9rFSC5w6VV+dx+1zp9V0dwfYdpUK1/S8hY3aFeh192eXMiBY2u5Eki5ret7CRu0J9CYugw4IStpCCQ35de0J9CYug3Z3SNpCKQ15aFOgN3UZtLtD0gQlNeTbE+glXQYlaaikhnx7Ar2ky6AkbVBKQ749gV7SZVCSCtSuOxa59EySNtWeGrok7UDT2zLVoV01dEmaQgnbMtXBGrqkzitpNec8Geh16kObTypQSas558lAr0tJO/hIPdOXZSwGel360uaTCtSXZSwGel360uZT6/ShJ7Avy1ic5VKXpu88JI3Rl9kf0I9lLNbQ69KXNp9axZ7AbjHQ69KXNp9axZ7AbrHLpU59aPOpVewJ7BZr6FKP2RPYLQa61GP2BNZr3jOK7HKRes6ewHrUMaPIGrok1aCOGUUGuiTVoI4ZRQa6JNWgjv1kDHRJqkEdM4oMdEmqQR0zipzlIkk1mfeMImvobdSH7fEkbZuB3jbeKEMtYJ2jGQZ627g9ngpnnaM57Qz0Pl/+3R5PhbPO0Zz2BXrpl/95X2z6cnPEjupDXcQ6R3PaF+glX/7ruNi4PV5rlV4XmRXrHM2pFOgRcUtE/CAizkbEJyYc986IeDUibp9dEUeUfPmv42Lj9nitVXJdZJbaWufoROspMyf+ALuBHwFvAvYATwKHNznum8AjwO1bve8NN9yQUzl4MHNQwbny5+DB6d5vliLGly2i6ZKpAHV+PE6eHHwlIga/T56c/d8o+e9v18mTmXv3Xvn/y969ZZYbWM1NcrVKDf1G4GxmnsvMV4AHgdvGHPcx4MvAizu7xGyh5Mu/bU1NUNfHo4SunZUVePZZuHRp8Lv0BmRXWk9VAn0/8PyGxxeGz10WEfuB9wPHJ71RRByJiNWIWF1bW9tuWQdK7nIo+WKjxtX18ehKONWp5J7c7agS6DHmuRx5/Bng3sx8ddIbZeaJzFzOzOWFhYWKRRyj1Mt/yRcbNa6uj0dXwqlOXWlcV9nL5QJwzYbHB4AXRo5ZBh6MCIB9wPsi4mJmfmUWhWwVb/+iCer4eHjj5+07duzKuwlBOxvXVWrojwPXRsShiNgD3AE8vPGAzDyUmUuZuQR8CfhIL8NcKoA9f9vXlcb1ljX0zLwYEfcAjzKYyfJAZp6JiLuHr0/sN5dUr/UQOnp00M2yuDgI87aFU9260LiOwSyY+i0vL+fq6mojf1tS2U6d8oK0mYg4nZnL415zP3RJRVmfdrnen70+7RIM9a20b+m/pE5z2uX0DHRJRXHa5fQMdElF6cqc8CYY6JKK4rTL6RnokorSlTnhTXCWi6TidGFOeBOsoUtSRxjokjQDJdwgwy4XSdqhUhZDWUOXpB0qZTFUNwK9hLaOpN4qZTFU+wO9hPttSeq1UhZDtT/QS2nrSOqtUhZDtT/QS2nrSOqtUhZDtT/QS2nrqAgOp6gpJdzquP2BXkpbR40rfTjFi43mrf2BXkpbR40reTil9IuNusFb0Kkzdu0ahOWoiEEzuElLS4MQH3Xw4KB5LlU16RZ07a+hS0MlD6c4dq86GOjqjJKHU0q+2Kg7DHR1RsnDKSVfbNQdbs6lTil1H+31Mh09OuhmWVwchHmJZVV7GehSTUq92Kg77HKRpI4w0CVdoU8LoLr232qXi6TLSrlRQx26+N/qwiJJl/VpAVRb/1tdWCSpkjoXQDXd3dHFxV4GuqTL6loAVcLeNl1c7GWgS7qsrgVQJWyk1sXFXga6pMvqWm1bQndHySuLp+WgqKTatXVAsgQOiqq3mh5403hd7O4ogYGuziph4E3jdbG7owSVulwi4hbgs8Bu4P7M/PTI6yvAvcOH/wf8aWY+Oek97XLRvNmsVxftqMslInYDnwNuBQ4Dd0bE4ZHDfgz8Xma+HfgUcGJnRZZ2roSBN6lOVbpcbgTOZua5zHwFeBC4beMBmfndzPzp8OFjwIHZFlPavjrmGdtHr5JUCfT9wPMbHl8YPreZDwNfH/dCRByJiNWIWF1bW6teSjWujcE174E3++hVmiqBHmOeG9vxHhHvYRDo9457PTNPZOZyZi4vLCxUL6Ua1dbgmvfAWwmLY6SNthwUjYjfBv4qM28ePv4zgMz865Hj3g78C3BrZv5wqz/soGh7OLg43q5dgwvcqAi4dKn+8qgfdjoP/XHg2og4FBF7gDuAh0f+wCLwEPDBKmGudnFwcbwu7gWidtsy0DPzInAP8CjwDPDPmXkmIu6OiLuHh30SeAPw+Yh4IiKseneIwTWei2NUmkoLizLzkcy8LjPfnJnHhs8dz8zjw3//SWZenZnvGP6MbQ6onQyu8VwcU7Y2DuTvlCtFtSWDa3MrK4NxhEuXBr/rPCd9DKyq2jqQv1NuziW10Ojt02DQavJCO9DlgXw355I6ximTk/V1IN9Al1qor4FVVV8H8g10qYX6GlhV9XUg30CXWqivgVVVXwfyr2q6AJK2bz2Yjh4ddLMsLg7CvOuBtR0rK/07Hwa61FJ9DCxNZpeLOmvaedrO71ZbGeiamyaDcdqFJX1dkKJucGGR5qLphS/TLizp8oIUdcOkhUUGuuai6WCcdmtbt8RV6Vwpqto1vfBl2nnazu9Wmxnomoumg3HaedrO71abGeiai6aDcdqFJX1dkDLKmT7tZB+65ubUKRe+tFHTA9qazEFRSZU1PaCtyRwUlVRZ0wPamp6BLukKTQ9oa3oGuqQrND2grekZ6D3gjAVthzN92svdFjtudMbC+t4k4BdUm3Mnx3ayht5x3ntS6g8DveOcsSD1h4Hecc5YkPrDQO84ZyxI/WGgd5wzFqT+cJZLDzhjQeoHa+iS1BEGuiR1hIEuSR1hoEtSRxjoktQRjd3gIiLWgDHb6HfaPuClpgtRKM/NZJ6fyfp0fg5m5sK4FxoL9D6KiNXN7jTSd56byTw/k3l+BuxykaSOMNAlqSMM9HqdaLoABfPcTOb5mczzg33oktQZ1tAlqSMMdEnqCAN9xiLiloj4QUScjYhPjHl9JSKeGv58NyKub6KcTdnq/Gw47p0R8WpE3F5n+ZpW5fxExE0R8UREnImIb9ddxqZU+G69LiK+FhFPDs/NXU2Us1GZ6c+MfoDdwI+ANwF7gCeBwyPH/A5w9fDftwL/0XS5Szo/G477JvAIcHvT5S7p/ACvB74PLA4f/2rT5S7o3Pw58DfDfy8APwH2NF32On+soc/WjcDZzDyXma8ADwK3bTwgM7+bmT8dPnwMOFBzGZu05fkZ+hjwZeDFOgtXgCrn5wPAQ5l5HiAz+3KOqpybBF4bEQG8hkGgX6y3mM0y0GdrP/D8hscXhs9t5sPA1+daorJseX4iYj/wfuB4jeUqRZXPz3XA1RHxrYg4HREfqq10zapybu4D3ga8ADwNfDwzL9VTvDJ4x6LZijHPjZ0XGhHvYRDovzvXEpWlyvn5DHBvZr46qGj1SpXzcxVwA/Be4JeBf4+IxzLzh/MuXMOqnJubgSeA3wfeDPxrRPxbZv7vnMtWDAN9ti4A12x4fIBBbeEKEfF24H7g1sz875rKVoIq52cZeHAY5vuA90XExcz8Si0lbFaV83MBeCkzfwb8LCK+A1wPdD3Qq5ybu4BP56AT/WxE/Bh4K/Cf9RSxeXa5zNbjwLURcSgi9gB3AA9vPCAiFoGHgA/2oFY1asvzk5mHMnMpM5eALwEf6UmYQ4XzA3wVeHdEXBURe4F3Ac/UXM4mVDk35xm0XIiINwJvAc7VWsqGWUOfocy8GBH3AI8yGJV/IDPPRMTdw9ePA58E3gB8flgLvZg92SWu4vnprSrnJzOfiYhvAE8Bl4D7M/N7zZW6HhU/O58CvhARTzPoork3M/uypS7g0n9J6gy7XCSpIwx0SeoIA12SOsJAl6SOMNAlqSMMdEnqCANdkjri/wElRT6PIwfQEwAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "from scipy.io import loadmat\n", "pointsClass1 = loadmat('KernelPointsEx4class1.mat')['PointsEx4class1']\n", "pointsClass2 = loadmat('KernelPointsEx4class2.mat')['PointsEx4class2']\n", "\n", "\n", "plt.scatter(pointsClass1[:,0], pointsClass1[:,1], c='r')\n", "plt.scatter(pointsClass2[:,0], pointsClass2[:,1], c='b')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.1 \n", "\n", "Start by completing the function below which should return the value and gradient of the hinge loss at a point $\\mathbf{x}^{(i)}$. What is the gradient of the hinge loss?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def HingeLoss(x):\n", " \n", " '''Returns the value and gradient of the hinge \n", " loss at the point x'''\n", " \n", " \n", " \n", " return value, gradient" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.2\n", "\n", "Once you have the function, implement a function HingeLossSVC that takes as innput a starting weight vector $\\mathbf{\\beta}$ and intercept $\\beta_0$ as well as the set of training points and a value for the parameter $C$ and returns the maximum margin classifier. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def HingeLossSVC(beta_init, beta0_init training, C):\n", " \n", " '''Returns the maximal margin classifier for the \n", " training dataset'''\n", " \n", " \n", " \n", " \n", " \n", " return beta, beta0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 2. \n", "\n", "We now would like to find a maximal margin classifier based on the Gaussian kernel. Write the dual formulation and use the Kernel trick to replace the inner product of the feature vectors with the (Gaussian) Kernel matrix. The dual formulation is quadratically constrained program. In order to solve this problem, we will rely on the [CVXOPT](https://cvxopt.org/) library. You can install this library from the terminal using the line 'pip install cvxopt' \n", "\n", "CVXOPT provides a [quadratic solver](https://cvxopt.org/examples/tutorial/qp.html) which is defined by means of 6 matrices $Q, p, G, h, A, b$ which define the problem to be solved as \n", "\n", "\\begin{align*}\n", "\\text{minimize} \\quad & \\frac{1}{2} \\mathbf{x}^T\\mathbf{P}\\mathbf{x} + \\mathbf{q}^T\\mathbf{x}\\\\\n", "\\text{subject to}\\quad & \\mathbf{G}\\mathbf{x} \\preceq h\\\\\n", "&\\mathbf{A}\\mathbf{x} = \\mathbf{b}\n", "\\end{align*}\n", "\n", "Here the notation $\\mathbf{x}\\preceq 0$ is used to indicate that every entry of the vector $\\mathbf{x}$ has to be non negative" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 2.1 The gaussian kernel \n", "\n", "Start by providing the definition of the Gaussian kernel in order to define the matrix $\\mathbf{P}$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "\n", "def GaussianKernel(training, sigma):\n", " \n", " '''should return the kernel matrix K whose \n", " entry K_ij is defined as K(x_i, x_j) = exp(-||x_i - x_j||^2/(2*sigma^2))'''\n", " \n", " \n", " return K" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 2.2 Solving the QCQP\n", "\n", "Relying on the dual formulation and on the Gaussian kernel, provide a sensible definition for each of the matrices $Q, p, G, h, A, b$ and solve the quadratic program using CVXOPT." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "from cvxopt import matrix, solvers" ] } ], "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.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }