mirror of
https://github.com/saymrwulf/nvidia-AI.summerschool17-notebooks.git
synced 2026-11-21 09:54:43 +00:00
790 lines
244 KiB
Text
790 lines
244 KiB
Text
|
|
{
|
||
|
|
"metadata": {
|
||
|
|
"name": "128-linear-to-nonlinear"
|
||
|
|
},
|
||
|
|
"nbformat": 3,
|
||
|
|
"nbformat_minor": 0,
|
||
|
|
"worksheets": [
|
||
|
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Title: Converting Nonlinear Classification Problems to Linear Ones\n",
|
||
|
|
"Author: Thomas Breuel\n",
|
||
|
|
"Institution: UniKL"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"from pylab import *\n",
|
||
|
|
"from numpy import *\n",
|
||
|
|
"def plotfun(f):\n",
|
||
|
|
" image = zeros((100,100))\n",
|
||
|
|
" for i in range(100):\n",
|
||
|
|
" for j in range(100):\n",
|
||
|
|
" image[i,j] = f(i/100.0,j/100.0)\n",
|
||
|
|
" imshow(image)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 2
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Nonlinear Classification Problem"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Let's consider now a non-linear classification problem. Here, the decision boundary is described by a quadratic equation."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"data = random.uniform(size=(50,2))\n",
|
||
|
|
"lo = ((data[:,0]-0.5)**2+(data[:,1]-0.5)**2<0.15)\n",
|
||
|
|
"hi = logical_not(lo)\n",
|
||
|
|
"sum(lo)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 3,
|
||
|
|
"text": [
|
||
|
|
"20"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 3
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"figsize(5,5)\n",
|
||
|
|
"plot(data[lo,0],data[lo,1],'bo')\n",
|
||
|
|
"plot(data[hi,0],data[hi,1],'ro')"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 4,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x42bb350>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAT8AAAE1CAYAAACRPefNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAG6FJREFUeJzt3W9sU9fdB/BvwFGCKtaW0qGSRGJcRyQUEpjCgE5NTav4\npmTLJNoXqbSpyzIWMRHTveqe/BGhBQp9lziP9FCpZVpRI6puUqoYjIHhWLQkQTClU0FV6sGWZBpb\nNhBoLP/c87wIMTF2bMe+/+/3I1mKb25vzjXpN/fcc8/v5AghBIiIbGaJ3g0gItIDw4+IbInhR0S2\nxPAjIlti+BGRLTH8iMiWUobfz372M6xatQobN25ccB+Px4Pi4mKUl5fjj3/8o6INJCJSQ8rwq6+v\nh9/vX/D7p06dwtdff43h4WG899572LNnj6INJCJSQ8rwe/755/Hkk08u+P1PP/0Ur7/+OgBg69at\nuHPnDm7duqVcC4mIVJD1Pb+xsTEUFRVF3xcWFmJ0dDTbwxIRqcqhxEEenSGXk5MTt0+ibURESshk\nlm7WV34FBQUYGRmJvh8dHUVBQUHCfYUQln3t378/6fdb3G4IIO7VKsu6t12J8zPzS+tz6+vtRYvb\njf0vvIAWtxt9vb2WOj+tX5nK+sqvtrYWXV1dqKurQ39/P5544gmsWrUq28NajmNyMuH2pRMTGreE\n9BTy+XBm3z4cCoej21oefF1ZU6NXs2wpZfi99tpr6Ovrw/j4OIqKinDgwAFMT08DABobG7Fz506c\nOnUKTqcTjz32GI4fP656o81oJi8v4fZIfr7GLSE9BTo7Y4IPAA6Fw2jzehl+GksZft3d3SkP0tXV\npUhjzMzlciX9vtvjQUs4HPOL3yxJqG5qUrllykh1fmam5bnp0QOw8r9dNhQZ8KDUv2Bzf9XbvF4s\nnZhAJD8f1U1Npvlrb+X/gbQ8Nz16AFb+t8tGjsjmjuFiflBOTlY3J4msINE9v2ZJQnVHh2n+EBpN\nptnC8CPSWMjnw9l5PYAqE/UAjIjhR0S2lGm2sKoLEdkSw4+IbImjvRYX8vkQ6OyEY3ISM3l5cHs8\nvL+kAH6u5meo8OMvlLI4m0Ad/FwtQmgk1Y/q6+0VzZIkBBB9NUuS6Ovt1aiF1tPidsd8nnOvVlnW\nu2mmxs/VWDKNMcPc81to2s9Zr1enFpkf5xOrg5+rNRgm/PgLpTzOJ1YHP1drMEz48RdKeW6PBy2S\nFLOtWZJQZZL5xEbFz9UaDDPgYfaJ/0Zk9vnERpXsc+WgnXkYaoYHp/2QkrQOooSjwJIEmfN2VcXp\nbUTz6BFErbKMg4FA3PY2WcbbSVZApOxwehvRPHo8PcBBO3Nh+JEl6RFEHLQzF4YfWZIeQWT0UeCQ\nz4dWWUa7y4VWWUbI59O7SboyzGgvkZL0eHrAyKPrnJIXjwMeZFl8euAhKw/GZJotvPIjy6qsqbFt\n2D2KgzHxeM+PyAY4GBOP4UdkA0YfjNED7/kR2YRV74FyhgeRzjivVx8c8CDSER8lMR/e8yNSAIvx\nmg/Dj0gBfJTEfBh+RArgoyTmw/AjUgAfJTEfjvYSKcSqj5IYHR91ISJbYjFTIqJFYPgRkS0x/IjI\nlhh+RGRLnN5GhuLzhdDZGcDkpAN5eTPweNyoqanUu1lkQQw/MgyfL4R9+84gHD4U3RYOtwAAA5AU\nZ7lHXVhZw7xkuRWBwMEE29vg97+tQ4vIDFjVBaysYXaTk4l/HScmlmrcErIDSw14sLKGueXlzSTc\nnp8f0bglZAeWCj9W1jA3j8cNSWqJ2SZJzWhqqtKpRWRllur2srKGuc0Nani9bZiYWIr8/Aiamqo5\n2EGqsNSAR6J7fs2ShOqODt7zI7Io0xQ2UHs0lpU1iOzFFOHX19sbPxorSZB5ZUZEGTJFVReOxhKR\nUaQMP7/fj5KSEhQXF+Po0aNx3x8fH0d1dTU2bdqEDRs24De/+c2Cx+JorHn4fCHIcitcrnbIcit8\nvpDeTSJSVNLR3kgkgr179+LcuXMoKCjAli1bUFtbi9LS0ug+XV1d2Lx5M9555x2Mj49j3bp1+PGP\nfwyHI/7QHI01B04zIztIeuU3ODgIp9OJNWvWIDc3F3V1dejp6YnZ55lnnsHdu3cBAHfv3sVTTz2V\nMPgArnNgFp2dgZjgA4Bw+BC83rM6tYhIeUmv/MbGxlBUVBR9X1hYiIGBgZh9du/ejRdffBGrV6/G\nvXv38PHHHy94vLlBjbZ5o7HVNhyNNXrlktlpZiEAAcz+iswAcHOaGVlK0vDLyclJeYDDhw9j06ZN\nCAaDCIfDqKqqwtDQEJYvXx63b3t7OwBg6bZtcLlccLlcGTXazMzQpbx7dxTAGQDzr/5acO/eP3Rq\nEdFDwWAQwWAw+wOJJC5duiRkWY6+P3z4sDhy5EjMPi+//LK4ePFi9P2LL74oLl++HHesFD/KNtzu\nFgGIuJcst+rdtKjNm3+ZsI3f/e4v9W4aUZxMsyXpPb+KigoMDw/j5s2bmJqawsmTJ1FbWxuzT0lJ\nCc6dOwcAuHXrFr766iusXbs2+1S2KDNULvnWt55OuH358sTbicwoabfX4XCgq6sLsiwjEomgoaEB\npaWlOHbsGACgsbERzc3NqK+vR3l5Ob755hu8++67WLFihSaNNyMzVC4xQxuJsmWpub1mkOienyQ1\no6PDOBP4zdBGojmmmN7G8Jvl84Xg9Z6dV7mkynChYoY2EgEMPyKyKVPM7SUiMgqGHxHZkqUqOROR\ndahd+5PhR0SGo8VKjOz2EpHhaFH7k+FHRIajRe1Phh8RGY4WtT8ZfhSHVZxJb1rU/uSAB8UwQ8kt\nsj4tan9yhgfFkOVWBAIHE2xvg9//tg4tIkqOMzxIEWYouUWkBIYfxWA5K7ILhh/F8HjckKSWmG2S\n1IympiqdWkSkDt7zozgsZ0VmwpJWRGRLHPAgIloEhh8R2RLDj4hsiTM8iCgltWvr6YHhR0RJaVFb\nTw/s9hJRUlrU1tMDw4+IktKitp4eGH5ElJQWtfX0wPAjoqS0qK2nB87wIFPz+ULo7AxgctKBvLwZ\neDxuTsVTQcjnw9l5tfWqFK6tlw1ObyPbSVR4VZJa0NEhMwBthNPbyHY6OwMxwQcA4fAheL1ndWoR\nmQnDj0yLhVcpGww/Mi0WXqVsMPzItFh4lbKh+4CHFecMknZYeJVMOdqbcM6gJEHu6GAAElFaTDna\na9U5g0RkfLqGn1XnDBKR8ekafladM0hExqdr+Fl1ziARGZ8hRnuNOmeQiIzPlKO9RETZMuVoLxGR\nXhh+RGRLXMCIyIZYB5HhR2Q7ieoghsOzc6TtFIDs9hLZDOsgzmL4EdkM6yDOYvgR2QzrIM5KGX5+\nvx8lJSUoLi7G0aNHE+4TDAaxefNmbNiwAS6XS+k2EpGCWAdxVtKHnCORCNatW4dz586hoKAAW7Zs\nQXd3N0pLS6P73LlzB9///vdx5swZFBYWYnx8HCtXroz/QXzImcgwrFQHMdNsSTraOzg4CKfTiTVr\n1gAA6urq0NPTExN+H330EV555RUUFhYCQMLgIyJjqampNG3YKSVp+I2NjaGoqCj6vrCwEAMDAzH7\nDA8PY3p6Gjt27MC9e/ewb98+/OQnP0l4vPb29ujXLpeLXWQiWrRgMIhgMJj1cZKGX05OTsoDTE9P\n4+rVqzh//jzu37+P7du3Y9u2bSguLo7bd374ERFl4tELpwMHDmR0nKThV1BQgJGRkej7kZGRaPd2\nTlFREVauXIlly5Zh2bJlqKysxNDQUMLwIyIyiqSjvRUVFRgeHsbNmzcxNTWFkydPora2NmafH/3o\nR7h48SIikQju37+PgYEBrF+/XtVGExFlK+mVn8PhQFdXF2RZRiQSQUNDA0pLS3Hs2DEAQGNjI0pK\nSlBdXY2ysjIsWbIEu3fvZvgRkeGxnh8RmRrr+RERLYItqrpwYXQiepTlwy/hwugPvmYAEtmX5e/5\ntcoyDgYCcdvbZBlv+/2at8cu
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 4
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We obviously can't solve this problem with a linear classifier. We could solve it with a quadratic discriminant function\n",
|
||
|
|
"\n",
|
||
|
|
"$$g(x,y) = a x^2 + b y^2 + c xy + d x + e y + f$$\n",
|
||
|
|
"\n",
|
||
|
|
"Here we use the decision function:\n",
|
||
|
|
"\n",
|
||
|
|
"$$D(x,y) = \\left\\lfloor g(x,y) > 0 \\right\\rfloor$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Linear Classifiers on Nonlinear Transformations of the Data"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Optimizing non-linear discriminant functions can be quite difficult.\n",
|
||
|
|
"However, there is a simpler approach that often works,\n",
|
||
|
|
"an extension of a previous trick we used.\n",
|
||
|
|
"\n",
|
||
|
|
"In order to turn an inhomogeneous problem $a\\cdot x > b$ into a homogeneous\n",
|
||
|
|
"problem $a\\cdot x > 0$, we remapped the feature space as $ x \\rightarrow (1,x) $.\n",
|
||
|
|
"\n",
|
||
|
|
"Let's try a more complicated remapping.\n",
|
||
|
|
"\n",
|
||
|
|
"Map the original values $(x,y)$ into a feature space $(x^2,y^2,xy,x,y,1)$\n",
|
||
|
|
"and then perform linear classification in this higher dimensional space."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"def phi(v):\n",
|
||
|
|
" x,y = v\n",
|
||
|
|
" return array([x**2,y**2,x*y,x,y,1])"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 7
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Let's try this out; let's transform the input data into the higher dimensional feature space. We apply the usual sign flip to use the perceptron learning algorithm below.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"vs = array([phi(v) for v in data])\n",
|
||
|
|
"vs[lo] = -vs[lo]"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 8
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"For completeness, here is a function that gives us the decision boundary.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"def f(x,y):\n",
|
||
|
|
" return (a[0]*x**2+a[1]*y**2+a[2]*x*y+a[3]*x+a[4]*y+a[5]>0)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 9
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Now let's run the perceptron learning algorithm in this larger feature space.\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"a = random.uniform(size=6)\n",
|
||
|
|
"for epoch in range(100):\n",
|
||
|
|
" for i in range(len(vs)):\n",
|
||
|
|
" if dot(a,vs[i])<0: a += vs[i]"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 10
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"If we transform back now, we see that using a linear learning algorithm, we have managed to solve a non-linear classification problem."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"plotfun(f)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAE0CAYAAACigc+fAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3V1sW/X9x/G3E+fRjp1nu0naho6macpTEWzSNE1AlU6a\nVtYNhjYmqBBjF2gSTLvZ3bQbGrSLjW1cITRFm8TDFasQf7RVqGgTgw2VCcbKUmjTpmnsPDixY+fB\nsXP+F805ODRp0tTOsX/+vCRLjes439Mmn5xzfr/f9+exLMtCRMQAFW4XICKSLwo0ETGGAk1EjKFA\nExFjKNBExBgKNBExxg0F2ptvvklvby979+7l2WefzVdNIiJb4tnqPLRsNsu+ffs4efIknZ2d3H33\n3bz00kvs378/3zWKiGzKls/Q/vnPf3LzzTfT3d1NVVUV3//+9/nzn/+cz9pERK6Ld6ufODo6ys6d\nO52Pu7q6eO+991a9xuPxbL0yEZFrWOvicsuBttmw2g10r/y5O+fPpjgF3ONyDYV0Ch1fqTqFOcc2\nvPKwvb3O67YcaJ2dnYyMjDgfj4yM0NXVddXrujHnH1VE3NHN6pOhvAfaXXfdxdmzZxkeHqajo4NX\nXnmFl156aatvJ4ax8JDByxJVZKm84ferYJkqlqhiCQ/qpyBr23Kgeb1efv/73/ONb3yDbDbL448/\nvuYIZ/eNVFcCut0uoMC6t/h5Fh5iNDNBG3GCN1yHjxRtTNDGBNWkb/j9bN15e6fi0+12AS7Y8rSN\nTb25x8MvCvXmUtQyeDnLXs6yl8t03PD7tTC18m5n8ZHKQ4VSyn5JngcFxGyL1LBALYvUbOnzM3iJ\nEnIeNyqDlwAJgsS3HGhVLFHLArUs6LLVUAo0WVOcIBHCTNC2pc/PUskEbaTw5aWeBWqJECZLJTUs\nbuk9mpgmTIQwEQWaoRRosqY4QS6wm0+5eUufb+FZuYVflZd6FqhljB1M0koFy1t6j52MUE2adsa3\n/B5S3BRoZSiDlxQ+UvjWDRw7PBIEtrm6tWWpJEvlli+BAaZoIUKYeuaoJHvV31eSxUcKP0mqWLqR\ncsUlCrQytEQVE7QxSiezNKz5mmmaiibM8iWFj0t0MUf9mmdotSzQyShdXFKglSgFWhmyA22InnXv\nkS1TgYVZS9eS+Jmjft1R1wAJKsnSyiQNzG5zdZIPCjQDzVFPnCAJAmuG0hz1RAhf85LTRBYe59J1\nLfPUMUEb59jDFC1rvqaBWQIkFHhFSoFmoCR+LtHFRXat+cObwUucIAvUulBd8VqiinHaWaRm3ZHU\nLi6xmwsKtCKlQCtx9qVh7pnYLA1cpoNP6CWj/+JNW6KKKVrWPTuDK2d5QeKEiK56voLllf8FTQdx\nk77bS1iaaqZpIkYz89Q5z0/RQoxmltVhPe/s6Sy5o63VpGkmRhPT1DHvYnWiQCth9s39c+xhmibn\n+QVqSeI37qZ+MYgTdCYN23yk2MM56phXoLlMgVYi7M4VuZeQszQwTjsj7GSSVherKx9z1DNH/arn\nGpilnjmamMZLxnm+kqzTIUS2hwKtRMQJMkHbqvs7i9Qwxg7d3HeZfaZcSXbVlJAgcadDiFYmbA8F\nWomw792c5ybnuWUqmKdOgeYyO9BmaVh1htbJKF4ytDLpYnXlRYFWZDJ4V/pB1K66qT9Oe946V0h+\nZal0lpLl8pIhQIIACSfoPFhOxw9diuafAq3I2F0lxthBmmrn+WJaVymbk8TPKJ2kqXYuOStYdjp+\nNDHtcoXmUaAVmXnqGGMHZ9i/6jd+PjtXyPaw145GCDvz07xkyFJJA7MKtAJQoLnEwkMKH0n8q+Y0\nxWhmnHbiBK8aTZPSksF71cRmLxkmaHNWGqi7R34p0FyyTAUxmrlEFzGanefnqCdGs87GDGX/v8OV\naTfq7pFfCjSXLFPBFC2cYw8X2eU8b+ExstOFXGEH2gyNTNGi7h55pkDbZrM0kCDANE1cpoMEAZ2N\nlZllKpwpN/ZKjyR+Z8+E3Kkfcn0UaNvMnk92iS7iBPPWc19KT253jzhBdnGReuYUaDdAgbYN7G4Y\ny1QwQyMj7OR/7HO7LHFZbnePFD7qmCdMZNX9NA+W08lDNqZA2wZJ/E5XjFE687LxrphlnjoihPGS\nWdWLrZEZmonRyIyL1ZUOBdo2sOcjnWMPszSQxO92SVJk7F2tZmlYtYHLbi7gJaNA2yQFWh7lbt2W\nu2wpRjNj7OACu9VwUdaUptrpb5eriiWCxGkmhpcMVSytuWOVXKGfrjxKU80krVdtsGtfbqrholyv\n3IaSdueOAAm3yypaCrQ8sketPuXmVW1+0lSzQK3mlsl1SxBwflH2MEQd8wq0a1Cg3SALj9MdY5om\nxmknQnjV7H+RrbK/t5L4CRInQIJq0k7HDk3xWE2BdoPsmd8RwkQJMUGb+pNJ3tnfZ/YkXLtjh5+k\n26UVFQXaDbLwON9oF9mlrhhSEPb3WYKAc/bfyIwC7QsUaFs0Rz0pfCQIOJeYmo4hhWLhcUZCPViM\n046fJGmq8ZPER0qjnyjQtixOkFE6uUwHU7QozGTb2C2/s1SSIEAno1STVqChQNsyezj9f+xzFhuL\nbAd7NH2SVuIEqSZ91cbH5UqBdh3mqCdOkAQBLtHFNE26XybbLndtcAofEcLUsEgLU07HjnJd+6lA\nuw5J/Fyii4vsYoZG9fgX19lLpuaop4PL7OYCDcyW7eWnAm0Dub8NZ2ngMh18Qq+WMElRsOepjdPO\nElUEibOTEbfLco1+KjewQC0xmp25ZlrCJFK8FGgbsLeVO8ceZ2qGljCJFCcF2hpyu2ZM00SUEBfZ\npakZUtSyVDrLpGpYpIqlslsapUBbQ27XDHs5k0YzpdjZg1YZvE5njham3C5rWynQ1pDbNSNKiAVq\nFWhS9OxGolO0sIdzzlSOcqJAW6GuGVLq7KVRCQL4SBEkjp+k05mjHPb+VKCtUNcMMYm9kmWOeqcz\nRxPTbpdVcAq0FeqaISZJEGCOeqKEyFJJA7MKtHKgrhliIvsXsr2Q3d6Z3UcKP0ljLz/LPtDUNUNM\nZt9KAZilgU5G6eKSsYG24ZT3kZER7r33Xg4cOMAtt9zCb3/7WwBisRj9/f309PRw+PBhZmZKc5st\n+17Df7iFUTq1k7kYJbfT7Sf0EiFs9L3hDQOtqqqKX//613z88ce8++67PP/885w5c4aBgQH6+/sZ\nGhri0KFDDAwMbEe9eWfhIYOXJarIUqlVAGKcZSqc7/FlKoz+Ht8w0MLhMHfccQcAfr+f/fv3Mzo6\nyokTJzh27BgAx44d47XXXitspSIiG7iue2jDw8N88MEHfOUrXyEajRIKhQAIhUJEo6XTYC63g4bO\nyqSc2GdrWSrxYFHBstsl5dWmAy2ZTPLAAw/w3HPP0dDQsOrvPB4PHs/aoXAq58/dKw+3JfE7m/+O\n0kmcoNsliRScvQKmmjRxgis9ZGIlMUAwvPLYyKYCbWlpiQceeIBHHnmEo0ePAlfOyiKRCOFwmLGx\nMdrb29f83Hs2Ve72speInGMPszRoZFPKgj2FY546EgS4ifM0MFsSgdbN6pOht9d53Yb30CzL4vHH\nH6evr4+nn37aef7+++9ncHAQgMHBQSfoitUyFSxSQxI/MZoZYwcX2M047cxR73Z5IgWXwetMU7Kv\nTLJUul1WXnksy7pm8/G///3vfP3rX+e2225zLiuPHz/Ol7/8ZR566CEuXrxId3c3r776Ko2Njavf\n3OPhF4Wr/bqk8K30H7jSQWOMHUQIq1mjlKUQUW7lI27jQ2fSbSn5JVdOtr5ow0vOr33taywvr33j\n8OTJkzdc2HaxGzWeZS/TNLFArQYDRAxTNisFMnhJ4meCNmZp2PgTRAxm/zxM0koGr9ORo9R3iyqb\nQBORz9lXLFkqnW4cYSIKNBEpPfb2d5O0Mkc91aRpZ7zk56UZHWgZvKTwkcJHlJCRozoiW5GlkiyV\nLFJDCp8xrbKMDjR73s0onUQJ
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 11
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"One-Dimensional Analog"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Here is a simple one-dimensional analog.\n",
|
||
|
|
"Let's say you want to discriminate values in the range $[0,1]$\n",
|
||
|
|
"from values outside that range.\n",
|
||
|
|
"There is no linear function $f(x)=ax$ such that $ax>0$ iff $x\\in[0,1]$.\n",
|
||
|
|
"There is a quadratic function, namely $f(x) = x (1-x)$.\n",
|
||
|
|
"\n",
|
||
|
|
"But we can also remap $\\xi = (\\xi_0,\\xi_1) = (x,x^2)$, and in that\n",
|
||
|
|
"new space, there is a linear function, namely $f(\\xi) = (1,-1) \\cdot \\xi$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"xs = linspace(-1.5,1.5,100)\n",
|
||
|
|
"figsize(6,6)\n",
|
||
|
|
"axvline(x=0,color='black')\n",
|
||
|
|
"axhline(y=0,color='black')\n",
|
||
|
|
"plot(xs,xs**2,'b')\n",
|
||
|
|
"plot(xs,xs,'r')"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 11,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x4ca8c10>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAFtCAYAAAAAmAHJAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtcVWW6B/DfDmgKNS+ToAETJaiIyCWMLgfDC6KoDHbx\nUo6kHqOL2f1o00WsNK3MMsxMzVErL1koU2iZta0kZBI6NcEk2pCAwilN89Ik6Dp/vG3abG5777XW\nXrff9/Pxk8Bir3e3lg8Pz3rf57VJkiSBiIgs4zytB0BERL7FwE9EZDEM/EREFsPAT0RkMQz8REQW\nw8BPRGQxsgJ/VVUVBg8ejOjoaPTv3x9Llixpdozdbkfnzp0RHx+P+Ph4PPXUU3JOSUREMvnL+eaA\ngAAsXrwYcXFxOHnyJK644gqkpqYiKiqqyXHXXXcd8vPzZQ2UiIiUISvj79GjB+Li4gAAHTt2RFRU\nFA4dOtTsOK4RIyLSD1kZv7PKykqUlpYiKSmpyedtNhsKCwsRGxuLkJAQPPfcc+jXr1+zY4iIyHNe\nJdaSAk6cOCFdccUVUl5eXrOv/fzzz9KpU6ckSZKkgoICKTIystkxCg1Dt+bMmaP1EFRj5vcmSbw3\njc7s78/b+1P2rJ76+nrccMMNmDRpEjIzM5t9vVOnTggMDAQAjBw5EvX19Th69Kjc0xIRkZdkBX5J\nkjBt2jT069cP9957b4vH1NXVNf4qUlxcDEmS0K1bNzmnJSIiGWTV+Hfv3o3XX38dAwYMQHx8PABg\n/vz5OHjwIAAgOzsbmzdvxrJly+Dv74/AwEBs2LBB/qgNJiUlReshqMbM780KzH79zP7+vGWTJO2n\n3NhsNs78IV3ivUl65u39yZW7REQWw8BPRGQxDPxERBbDwE9EZDEM/EREFsPAT0RkMQz8REQWw8BP\nRGQxDPxERBbDwE9EZDEM/EREFsPAT0RkMQz8REQWw8BPRGQxDPxERBajm8B/6JDWIyAiMo5z57z/\nXt0E/txcrUdARGQc27Z5/7262YHr4oslVFYCHTpoPRqi33EHLtKrIUOAjz82+A5cycnA6tVaj4KI\nSP9KS4GKCu+/XzeB/4EHgMWLgbNntR4JEZG+LVoEzJzp/ffrJvBfcw3QvTuwdavWIyEi0q/qaqCg\nAJg+3fvX0E3gt9lE1r9okdYjISLSryVLgMmTgS5dvH8N3TzclSQJDQ1ARASwYQNw1VVaj4qID3dJ\nX06cAMLDgS++AC67zPv7UzcZPwD4+wP33susn4ioJatWAUOHiqAvh64yfgA4eVL8RCsqEtk/kZaY\n8ZNe1NcDvXoBb78NDBwoPmeKjB8AOnYEsrOB55/XeiRERPqxaZMI/I6gL4fuMn4AqK0FoqKAffvE\nTB8irTDjJz2QJCA+Hpg/H0hP//3zpsn4AaBHD+Cmm4ClS7UeCRGR9nbsABoagJEjlXk9XWb8APDt\nt2I1b2UlEBiozbiImPGTHqSmArfcAtx6a9PPmyrjB4A+fYBrr2UbByKytpISoLwcuPlm5V5Ttxk/\nABQWApMmiVq/v78GAyPLY8ZPWrv5ZlHff+ih5l8zXcYPiDYOISFi+hIRkdV89x3w/vvAbbcp+7q6\nDvwAMHs2sGCBeKpNRGQlixaJ6e2dOyv7urICf1VVFQYPHozo6Gj0798fS5YsafG4mTNnIjIyErGx\nsSgtLfXoHOnp4mn2Bx/IGSkRkbHU1QHr1wP33KP8a8sK/AEBAVi8eDG++eYbFBUVYenSpSgvL29y\nTEFBAfbv34+Kigq8+uqruOOOOzw6h80GzJolsn4iIqtYsgSYMAEIDlb+tWUF/h49eiAuLg4A0LFj\nR0RFReGQy+a5+fn5yMrKAgAkJSXh2LFjqKur8+g848cD//43sGePnNESERnDzz8Dy5cDDz6ozusr\nNlemsrISpaWlSEpKavL5mpoahIWFNX4cGhqK6upqBLv8GMvJyWn8e0pKClJSUho/DggQ/wMWLgTe\neUepERMR6dOrrwLDhwOXX97083a7HXa7XfbrKxL4T548iRtvvBEvvvgiOnbs2OzrrtONbDZbs2Oc\nA39Lpk4FnnxSzGeNipI1XCIi3fr1V7EbYUFB86+5JsVz58716hyyZ/XU19fjhhtuwKRJk5CZmdns\n6yEhIaiqqmr8uLq6GiEhIR6fJzAQuPtukfUTEZnVmjXAgAFAbKx655AV+CVJwrRp09CvXz/ce++9\nLR6TkZGBtWvXAgCKiorQpUuXZmUed911F/D3v4s2DkREZtPQIJLbRx5R9zyyVu5+9tlnGDRoEAYM\nGNBYvpk/fz4OHjwIAMjOzgYAzJgxA9u3b0eHDh2wevVqJCQkNB2EB6vPHn5Y7EKTm+vtqIncx5W7\n5Etvvike6u7a5d7x3t6fum7Z0JK6OlHjLysTXTyJ1MTAT75y7pwo8SxaBKSlufc9pmzZ0JLgYNG/\nZ/FirUdCRKScv/8duOACMZtHbYbL+AHg4EHRtKiiAujWTcWBkeUx4ydfkCQgKUm0qLn+eve/zzIZ\nPwD86U9AZibw0ktaj4SISL6dO8V+4y1MjFSFITN+QLRq/q//Ag4cADp1UmlgZHnM+MkXUlKAadOA\nv/zFs++zVMYPAL17A8OGcXtGIjK2Tz8FqquBiRN9d07DZvwA8M03wJAhomd1hw4qDIwsjxk/qW34\ncNGPbNo0z7/Xchk/AERHi315ly/XeiRERJ4rKhJla09LPHIZOuMHgC+/FD37DxwALrxQ4YGR5THj\nJzWNGgWMGQPcfrt332/JjB8A4uKAgQOBlSu1HgkRkfv27gW++gqYMsX35zZ8xg8AX3wBjB0L7N8P\n/OEPCg6MLI8ZP6ll7Fhg8GBg5kzvX8OyGT8AJCYCMTHAa69pPRIiovZ9+aXYWGr6dG3Ob4qMHxD/\nE2+8kVk/KYsZP6nh+uuBQYOAVpoau83SGT8gljsz6ycivfvySzGb57fmxZowTcYPMOsn5THjJ6Up\nle0DzPgBMOsnIn3TQ7YPmCzjB5j1k7KY8ZOSlMz2AWb8jRxZ/6pVWo+EiOh3esn2ARNm/ABQXCx+\nsu7fLzY2IPIWM35SSkaG6C2mVLYPMONv4sorgYQE9vAhIn0oLgZKSrxvzaA0U2b8gPi1auRI0cMn\nMFDRlyYLYcZPShgxAvjzn4E77lD2dZnxu4iLA669lv36iUhbu3cD//qXd22X1WLajB/4vV///v3c\npYu8w4yf5Bo6FLj5ZnUCPzP+FkRHi//p3JuXiLRgtwPffw9Mnqz1SJoydcYPiE0Orr0WqKgAunRR\n5RRkYsz4yVuSJDaKys5Wb6MVZvyt6N1bTKN67jmtR0JEVrJtG/DTT6LMozemz/gB8atWQgJQVgYE\nB6t2GjIhZvzkjXPngCuuAB5/XPTdVwsz/jZceikwaRLw9NNaj4SIrGDzZsDfH8jM1HokLbNExg8A\ndXVAv35AaSnwpz+peioyEWb85KmGBjGxJDcXSE1V91zM+NsRHCxWzT3xhNYjISIzW7sWuOQSYNgw\nrUfSOstk/IB40NK7N/DZZ0CfPqqfjkyAGT954j//EbFl/XrgmmvUPx8zfjd07Qo88ADw6KNaj4SI\nzGjZMiA21jdBXw5LZfwAcPq0yPrfeUc0cyNqCzN+ctfx4yK27NwJ9O/vm3NqkvFPnToVwcHBiImJ\nafHrdrsdnTt3Rnx8POLj4/HUU0/JOZ0iAgOBOXOA2bPFAgsiIiU8+yyQnu67oC+HrIz/008/RceO\nHTF58mR8/fXXzb5ut9vx/PPPIz8/v+1B+DiramgQF+fFF4G0NJ+dlgyIGT+54/BhEVN8PWtQk4w/\nOTkZXbt2bfMYPf6j8fcH5s8HZs0SCy2IiOR44glgyhTjTBVX9eGuzWZDYWEhYmNjkZ6ejrKyMjVP\n55GxY8XuXOvXaz0SIjKyigrgrbeAhx/WeiTu81fzxRMSElBVVYXAwEBs27YNmZmZ2LdvX4vH5uTk\nNP49JSUFKSkpag4NNhuwcCFw
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 11
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"In this graph, think of the curve not as a plot of a function of one variable,\n",
|
||
|
|
"but instead as set of points in 2D that happens to have a simple correspondence\n",
|
||
|
|
"to points on the $x$ axis.\n",
|
||
|
|
"By making that set curved, we can now \"cut off\" a region that, when mapped back to the\n",
|
||
|
|
"$x$ axis corresponds to the interval $[0,1]$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"The Kernel Trick"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"If we carry out the perceptron learning algorithm in terms of nonlinear functions of the input $\\phi(x)$,\n",
|
||
|
|
"then there is only one statement actually involving the data:\n",
|
||
|
|
"\n",
|
||
|
|
"$\\hbox{if } a\\cdot \\phi(x) \\lt 0 \\hbox{ then } a \\leftarrow a+\\phi(x)$\n",
|
||
|
|
"\n",
|
||
|
|
"This comprises the comparison and the weight update."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(rewriting the dot product)\n",
|
||
|
|
"\n",
|
||
|
|
"Note that all we ever add to the weight vector $a$ is copies of $\\phi(x)$, where $x$ is\n",
|
||
|
|
"a training sample.\n",
|
||
|
|
"\n",
|
||
|
|
"$a = \\sum_j \\lambda_j \\phi(x_j)$\n",
|
||
|
|
"\n",
|
||
|
|
"Remember that all the training samples are known.\n",
|
||
|
|
"If we plug this in above, we get for training sample $x_i$:\n",
|
||
|
|
"\n",
|
||
|
|
"$\\hbox{if } \\sum\\lambda_j \\phi(x_j) \\cdot \\phi(x_i)\\lt 0 \\hbox{ then } a \\leftarrow a+\\phi(x_i)$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(updating the lambda)\n",
|
||
|
|
"\n",
|
||
|
|
"Instead of updating the weight vector, we can therefore also simply keep track of how often we added $\\phi(x_i)$ to the weight vector:\n",
|
||
|
|
"\n",
|
||
|
|
"$\\hbox{if } \\sum \\lambda_j \\phi(x_j) \\cdot \\phi(x_i)\\lt 0 \\hbox{ then } \\lambda_i \\leftarrow \\lambda_i+1 $\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(using the inner product)\n",
|
||
|
|
"\n",
|
||
|
|
"Looking at the first expression, we don't even need to evaluate the dot product again and again.\n",
|
||
|
|
"All we really need to keep track of is the value $K_{ji} = \\phi(x_j)\\cdot\\phi(x_i)$.\n",
|
||
|
|
"\n",
|
||
|
|
"$\\hbox{if } \\sum \\lambda_j K_{ji}\\lt 0 \\hbox{ then } \\lambda_i \\leftarrow \\lambda_i+1 $"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(implicit high dimensional space)\n",
|
||
|
|
"\n",
|
||
|
|
"That is very nice because we can use a function $\\phi(x)$ that transforms into a very high dimensional\n",
|
||
|
|
"space, but we never need to represent the values in that space. All we need to do is define the\n",
|
||
|
|
"values of the dot products.\n",
|
||
|
|
"\n",
|
||
|
|
"We define these values in terms of a _kernel function_:\n",
|
||
|
|
"\n",
|
||
|
|
"$$k(u,v) = \\phi(u) \\cdot \\phi(v)$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"# kernel function\n",
|
||
|
|
"def k(u,v):\n",
|
||
|
|
" return dot(phi(u),phi(v))"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 12
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"In fact, we can precompute all the dot products:\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"n = len(data)\n",
|
||
|
|
"ks = zeros((n,n))\n",
|
||
|
|
"for i in range(n):\n",
|
||
|
|
" for j in range(n):\n",
|
||
|
|
" ks[i,j] = k(data[i],data[j])"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 13
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Now, with these ideas, we can write the kernelized perceptron learning algorithm as follows:\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"c = zeros(len(vs))\n",
|
||
|
|
"for epoch in range(1000):\n",
|
||
|
|
" for i in range(n):\n",
|
||
|
|
" sign = (dot(c,ks[:,i])>=0)\n",
|
||
|
|
" if lo[i] and not sign: c[i] += 1\n",
|
||
|
|
" elif not lo[i] and sign: c[i] -= 1"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 14
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"c[:10]"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 15,
|
||
|
|
"text": [
|
||
|
|
"array([ 2., -29., -26., -63., -1., -141., 322., -397., 102., 230.])"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 15
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We can express the discriminant function directly in terms of the kernel and the $\\lambda_i$:\n",
|
||
|
|
"\n",
|
||
|
|
"$$g(x) = \\sum \\lambda_i k(v_i,x) >0$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"def g(x,y):\n",
|
||
|
|
" kv = [k(data[i],array([x,y])) for i in range(n)]\n",
|
||
|
|
" return dot(c,kv)>0\n",
|
||
|
|
"clf(); plotfun(g)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAE0CAYAAACigc+fAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3VtsHOX9xvHv2uvj+ri2dzexE5tATOKEQ2goEhclEDlI\niKQpSVFLFSJE6QWqBAip4q7qDXHERQltrxBCFkgErvgjRFGJUKJWHFpkKihNlUBix3a8a8fr9dle\n73r+F/EMNvHZXs/uu89HspRM1t7fJPaTmXnf9/d6LMuyEBExQI7bBYiIrBcFmogYQ4EmIsZQoImI\nMRRoImIMBZqIGGNNgfbhhx+yY8cOtm/fzsmTJ9erJhGRVfGsdh5aMpnk1ltv5cyZM9TW1nL33Xfz\n1ltvsXPnzvWuUURkWVZ9hfbPf/6TW265hYaGBvLy8vjFL37B//3f/61nbSIiK+Jd7Sd2d3ezZcsW\n5/d1dXV8/vnnc17j8XhWX5mIyCLmu7lcdaAtP6zqgYaZXzfM+rUpzgL7XK4hlc6i88tUZzHn3Npn\nPmzn5n3VqgOttraWzs5O5/ednZ3U1dXN88oGzPlLFRF3NDD3Ymj+QFv1M7S9e/dy8eJF2tvbicfj\nvP322xw6dGi1X05EZM1WfYXm9Xr585//zIMPPkgymeTJJ59cYISzYfXVZYQGtwtIsQa3C0ixBrcL\nSKEGtwvYcKuetrGsL+7xAL9P1ZcXkaz1h3kHBbRSQESMoUATEWMo0ETEGAo0ETGGAk1EjKFAExFj\nKNBExBgKNBExhgJNRIyhQBMRYyjQRMQYCjQRMYYCTUSMoUATEWMo0ETEGAo0ETGGAk1EjKFAExFj\nKNBExBgKNBExhgJNRIyhQBMRYyjQRMQYCjQRMYYCTUSM4XW7AMkuOUyTxxR5TOHhxp2v19s0OTPv\nloeFJ+XvJ+5SoMmGKmKcGvqooY984il/v1F8M+9WQ5z8lL+fuEuBJhuqkAlChNnORXyMpvz9+qkC\nIEaFAi0LKNBkVbwkKGSCQibIYXrZn1fNNYJECBLZkEDzkmCIMgYpZxTfsj8vgXfm7AqZ1qPmjKFA\nk1Wxr7Q20bOiW0cfo9TQRx5TKazue3aduSSZpGDZnzdCCWFChAmt6PPEXQo0WZUixtlEDzs5v6Ir\nrVySzqDARihkgk30UM21FV1p9VFDklyuUa1AyyAKNHEUMoGPUXyMLjkC6SdKgF7KGaSYsQ2qcOVy\nSZJLkgImV/R5CbwEiTCKjzGKb/hzC8/M35SPCQrXq1xZIwWaOHyMUkcXtXQv+VysmDH8RDfsSmuj\n2VegBUzOO5iQJJduaummVoGWRhRo4ihhhDq62MU3eEks+loPFjlMb8hcMjfYz96CROadvzZFHnB9\n9NQeSRX3KdCyUB5TlDFEGUNzbsUC9OInSj5xckm6WKH7PFiL/h3kME0V/TTQPueWe5ICZ1Q1oR+v\nDae/8SyUxxQ19FFPB+UMOseLGaOcwRVNw8hWHiyq6MdLghBh53iMCq6wlTGKFWgu0N+44ea7NSxk\nggC9bOMSAXpdrC5z5TBNBTEqiM05HiHIOEWECTm3pXB9EGGaHC2/SjEFmuHKGcRPdM4Pnv18qJAJ\nFyszUxHjhAiTwDtnukeMCqL4iVHhYnXmU6AZrpxB6ulgK1ecY7kkKWFEgZYC9ry3UoZJkusc76Ce\nBF4FWoop0AyxUBeLKvrZzFUaaHevuCyST5x84lQyMOf4FHkMUs4Alc6xaXJI4GWKPC2vWicKNEMs\n1MUiQC9lDLlYmcD3V8o/HBG1O4HMN3lXVk6BZoiFulgUMEkR4y5WJgBlDJFPfM6I6Agl5JJkmFIF\n2jpRoGUYD5bT5WL2LP2N7mIhK2P/m83mY3RmNmDZnInMU+Q5nT40KroyCrQMk8M0fqKECM8Zudzo\nLhaydvZ8QIDNXHWOD1DpdPpQoK2MAi3DeLDwE2Ubl6ijyzm+0V0sZO3sQKtkYM6IaCdbiJNPLwEN\nFqyQAi1DFDOGj1HKGCJEGD9RPezPcDlMU8DkDZ1AqugnRJgxihmmdMGOH3IjBVqGKGeQWrrZzFWq\n6KeEEbdLkhSxu54UM8ZVNtNFnQJtmZa8nu3s7OT+++9n165d7N69m1deeQWAaDRKc3MzjY2NHDhw\ngFgstsRXkrWwh/138x9q6daDf4PZXU928x+2cmXOeltZnMeyrEX7v4TDYcLhMHfeeScjIyP86Ec/\n4t133+X111+nurqa3/3ud5w8eZKBgQFaWlrmfnGPB/h9Kus3TgGTlDNIGUNzRr7q6KKBdmrpdrE6\n2Whd1NFBPZ1sYZByhijT1RoAf2C+6FryljMUChEKhQAoKSlh586ddHd3895773Hu3DkAjh8/zr59\n+24INFk5ey1gPR1z5o+VMqxnZlnIvjIvY4grbKWDegXaIlb0DK29vZ0vv/ySe+65h0gkQjAYBCAY\nDBKJRFJSYLawO2L4GCVEmEYu6DmZUMowpQwTJEICL1H8DFDpdO7QtI65lh1oIyMjHDlyhFOnTlFa\nWjrnzzwez8zt5XzOzvp1w8yHzGav/fMTJUiEGvqW7Bgr2cWef3gz31HMmBNs4xS5XdoGaZ/5WNyy\nAm1qaoojR45w7NgxDh8+DFy/KguHw4RCIXp6eggEAgt89r5llZvN7PlI27jkzPTXfDKZzQ40+xnr\nJbYxTlEWBVoDcy+Gzs37qiVHOS3L4sknn6SpqYlnn33WOX7o0CFaW1sBaG1tdYJOlseDRR5TTpfY\nAL1soZPNXKWcwaxvgS1zebAoZZgQYbZyxVkpYt+SljJMMWNZ/x/hkqOc//jHP/jJT37C7bff7txW\nnjhxgh//+Mc8+uijXLlyhYaGBt555x0qKub2etIo58JymHa6YwToZRM9hAjruZksaYJCZ2nUCCXO\n8UHKne4d5q8wmH+Uc8lAWwsF2sK8JNjORbZzkTq6KGKcQib07EyWlCTXWbw+e9+CbmpnvqO2z1lK\nZaZVTtuQ9VXApLOhr90dw16gLLIcuSSdDaFnG6eIIsaN3VpwORRoG6ycwZmbhTA19GnGv8g6UqBt\nMHui5HYuqjuGyDpToKVIPnHntmD2iOUmeqjmGqUMu1idmKiQCaroZytXsrZLhwItReyW2HV0zWkP\nU8mAljBJSqhLhwItZeztzHZyfs5UjB9u+iuyXkoYoZgxNnMVLwmGKSVMyO2yNpQCLUXsHcu9JPSc\nTDaEB4tckuSSpJIBttAJkFVdOkyffSeSlezBp118Qx1dWTOariu0dWbfUnpJ6PZSXJOtXToUaOtI\nXTMk3WRblw4F2jpS1wxJN9nWpUOBtkb27WUeU3O6ZlRzze3SRJwuHaUM42OUMYoZoJI4+TPTuvOM\nuv1UoK2RvU/m7K4ZP9whWyQd2HcQSXIpZ9DpzBEn3+3S1o0CbY3sS3p741+7a4ZIurEDbfb+FDEq\nFGiirhmSeWZ36Ujg5SqbyWHa7bLWlQJtldQ1QyT9KNBWSV0zRNKPAm0F7FtMH6PqmiEZLY8pKohR\nRxdR/DPf1b6MH/FUoK2A3c2glm6q6FfXDMlYRYyziR4KmKSHTXRTyxjFCrRsUsIIdXSxi2/IJ65l\nTZKx7PZWQSIUMc4YxVxlc8ZvrqJAW4I9w7qMITZzFT9R8olrmznJaHZnDsBZd2wCBdoSihgnRJh6\nOqiin3IGjfnHFzGNAm0JBUwSoJftXNQAgBjJvlrzksDC43TkyEQKNJEsZw92AUTxE8VPjIolPis9\nKdBEslwJI9TSTQUx2mkggVeBZhIPljNZ1seoRjTFaIUz+7BXc40xijN6HwIF2jzyiVPNNWroc9Zo\naiWASPpToM0jjykC9HIL3xIkQiETCjSRDKBAm0cO0/gYpZprVNHvdjkiG8aed1lD38yNaCFT5Lld\n1rIp0ETEYTddKGZsppdMiAEq3S5r2RRoIuIoY4hixggSIZckw5Qq0DKRBwsfo5Qwgp8oFcT03Eyy\njj267yVBIRMZt8RPgTbDbqVd
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 16
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We can also reconstruct the original parameter values directly.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"a = sum([c[i] * phi(data[i]) for i in range(n)],axis=0)\n",
|
||
|
|
"a"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 17,
|
||
|
|
"text": [
|
||
|
|
"array([-26.50513205, -25.7265693 , -3.92491033, 28.34359676,\n",
|
||
|
|
" 27.40297646, -10. ])"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 17
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We see that these parameters give us the same decision region as before."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"plotfun(f)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAE0CAYAAACigc+fAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3VtsHOX9xvHv2uvj+ri2dzexE5tATOKEQ2goEhclEDlI\niKQpSVFLFSJE6QWqBAip4q7qDXHERQltrxBCFkgErvgjRFGJUKJWHFpkKihNlUBix3a8a8fr9dle\n73r+F/EMNvHZXs/uu89HspRM1t7fJPaTmXnf9/d6LMuyEBExQI7bBYiIrBcFmogYQ4EmIsZQoImI\nMRRoImIMBZqIGGNNgfbhhx+yY8cOtm/fzsmTJ9erJhGRVfGsdh5aMpnk1ltv5cyZM9TW1nL33Xfz\n1ltvsXPnzvWuUURkWVZ9hfbPf/6TW265hYaGBvLy8vjFL37B//3f/61nbSIiK+Jd7Sd2d3ezZcsW\n5/d1dXV8/vnnc17j8XhWX5mIyCLmu7lcdaAtP6zqgYaZXzfM+rUpzgL7XK4hlc6i88tUZzHn3Npn\nPmzn5n3VqgOttraWzs5O5/ednZ3U1dXN88oGzPlLFRF3NDD3Ymj+QFv1M7S9e/dy8eJF2tvbicfj\nvP322xw6dGi1X05EZM1WfYXm9Xr585//zIMPPkgymeTJJ59cYISzYfXVZYQGtwtIsQa3C0ixBrcL\nSKEGtwvYcKuetrGsL+7xAL9P1ZcXkaz1h3kHBbRSQESMoUATEWMo0ETEGAo0ETGGAk1EjKFAExFj\nKNBExBgKNBExhgJNRIyhQBMRYyjQRMQYCjQRMYYCTUSMoUATEWMo0ETEGAo0ETGGAk1EjKFAExFj\nKNBExBgKNBExhgJNRIyhQBMRYyjQRMQYCjQRMYYCTUSM4XW7AMkuOUyTxxR5TOHhxp2v19s0OTPv\nloeFJ+XvJ+5SoMmGKmKcGvqooY984il/v1F8M+9WQ5z8lL+fuEuBJhuqkAlChNnORXyMpvz9+qkC\nIEaFAi0LKNBkVbwkKGSCQibIYXrZn1fNNYJECBLZkEDzkmCIMgYpZxTfsj8vgXfm7AqZ1qPmjKFA\nk1Wxr7Q20bOiW0cfo9TQRx5TKazue3aduSSZpGDZnzdCCWFChAmt6PPEXQo0WZUixtlEDzs5v6Ir\nrVySzqDARihkgk30UM21FV1p9VFDklyuUa1AyyAKNHEUMoGPUXyMLjkC6SdKgF7KGaSYsQ2qcOVy\nSZJLkgImV/R5CbwEiTCKjzGKb/hzC8/M35SPCQrXq1xZIwWaOHyMUkcXtXQv+VysmDH8RDfsSmuj\n2VegBUzOO5iQJJduaummVoGWRhRo4ihhhDq62MU3eEks+loPFjlMb8hcMjfYz96CROadvzZFHnB9\n9NQeSRX3KdCyUB5TlDFEGUNzbsUC9OInSj5xckm6WKH7PFiL/h3kME0V/TTQPueWe5ICZ1Q1oR+v\nDae/8SyUxxQ19FFPB+UMOseLGaOcwRVNw8hWHiyq6MdLghBh53iMCq6wlTGKFWgu0N+44ea7NSxk\nggC9bOMSAXpdrC5z5TBNBTEqiM05HiHIOEWECTm3pXB9EGGaHC2/SjEFmuHKGcRPdM4Pnv18qJAJ\nFyszUxHjhAiTwDtnukeMCqL4iVHhYnXmU6AZrpxB6ulgK1ecY7kkKWFEgZYC9ry3UoZJkusc76Ce\nBF4FWoop0AyxUBeLKvrZzFUaaHevuCyST5x84lQyMOf4FHkMUs4Alc6xaXJI4GWKPC2vWicKNEMs\n1MUiQC9lDLlYmcD3V8o/HBG1O4HMN3lXVk6BZoiFulgUMEkR4y5WJgBlDJFPfM6I6Agl5JJkmFIF\n2jpRoGUYD5bT5WL2LP2N7mIhK2P/m83mY3RmNmDZnInMU+Q5nT40KroyCrQMk8M0fqKECM8Zudzo\nLhaydvZ8QIDNXHWOD1DpdPpQoK2MAi3DeLDwE2Ubl6ijyzm+0V0sZO3sQKtkYM6IaCdbiJNPLwEN\nFqyQAi1DFDOGj1HKGCJEGD9RPezPcDlMU8DkDZ1AqugnRJgxihmmdMGOH3IjBVqGKGeQWrrZzFWq\n6KeEEbdLkhSxu54UM8ZVNtNFnQJtmZa8nu3s7OT+++9n165d7N69m1deeQWAaDRKc3MzjY2NHDhw\ngFgstsRXkrWwh/138x9q6daDf4PZXU928x+2cmXOeltZnMeyrEX7v4TDYcLhMHfeeScjIyP86Ec/\n4t133+X111+nurqa3/3ud5w8eZKBgQFaWlrmfnGPB/h9Kus3TgGTlDNIGUNzRr7q6KKBdmrpdrE6\n2Whd1NFBPZ1sYZByhijT1RoAf2C+6FryljMUChEKhQAoKSlh586ddHd3895773Hu3DkAjh8/zr59\n+24INFk5ey1gPR1z5o+VMqxnZlnIvjIvY4grbKWDegXaIlb0DK29vZ0vv/ySe+65h0gkQjAYBCAY\nDBKJRFJSYLawO2L4GCVEmEYu6DmZUMowpQwTJEICL1H8DFDpdO7QtI65lh1oIyMjHDlyhFOnTlFa\nWjrnzzwez8zt5XzOzvp1w8yHzGav/fMTJUiEGvqW7Bgr2cWef3gz31HMmBNs4xS5XdoGaZ/5WNyy\nAm1qaoojR45w7NgxDh8+DFy/KguHw4RCIXp6eggEAgt89r5llZvN7PlI27jkzPTXfDKZzQ40+xnr\nJbYxTlEWBVoDcy+Gzs37qiVHOS3L4sknn6SpqYlnn33WOX7o0CFaW1sBaG1tdYJOlseDRR5TTpfY\nAL1soZPNXKWcwaxvgS1zebAoZZgQYbZyxVkpYt+SljJMMWNZ/x/hkqOc//jHP/jJT37C7bff7txW\nnjhxgh//+Mc8+uijXLlyhYaGBt555x0qKub2etIo58JymHa6YwToZRM9hAjruZksaYJCZ2nUCCXO\n8UHKne4d5q8wmH+Uc8lAWwsF2sK8JNjORbZzkTq6KGKcQib07EyWlCTXWbw+e9+CbmpnvqO2z1lK\nZaZVTtuQ9VXApLOhr90dw16gLLIcuSSdDaFnG6eIIsaN3VpwORRoG6ycwZmbhTA19GnGv8g6UqBt\nMHui5HYuqjuGyDpToKVIPnHntmD2iOUmeqjmGqUMu1idmKiQCaroZytXsrZLhwItReyW2HV0zWkP\nU8mAljBJSqhLhwItZeztzHZyfs5UjB9u+iuyXkoYoZgxNnMVLwmGKSVMyO2yNpQCLUXsHcu9JPSc\nTDaEB4tckuSSpJIBttAJkFVdOkyffSeSlezBp118Qx1dWTOariu0dWbfUnpJ6PZSXJOtXToUaOtI\nXTMk3WRblw4F2jpS1wxJN9nWpUOBtkb27WUeU3O6ZlRzze3SRJwuHaUM42OUMYoZoJI4+TPTuvOM\nuv1UoK2RvU/m7K4ZP9whWyQd2HcQSXIpZ9DpzBEn3+3S1o0CbY3sS3p741+7a4ZIurEDbfb+FDEq\nFGiirhmSeWZ36Ujg5SqbyWHa7bLWlQJtldQ1QyT9KNBWSV0zRNKPAm0F7FtMH6PqmiEZLY8pKohR\nRxdR/DPf1b6MH/FUoK2A3c2glm6q6FfXDMlYRYyziR4KmKSHTXRTyxjFCrRsUsIIdXSxi2/IJ65l\nTZKx7PZWQSIUMc4YxVxlc8ZvrqJAW4I9w7qMITZzFT9R8olrmznJaHZnDsBZd2wCBdoSihgnRJh6\nOqiin3IGjfnHFzGNAm0JBUwSoJftXNQAgBjJvlrzksDC43TkyEQKNJEsZw92AUTxE8VPjIolPis9\nKdBEslwJI9TSTQUx2mkggVeBZhIPljNZ1seoRjTFaIUz+7BXc40xijN6HwIF2jzyiVPNNWroc9Zo\naiWASPpToM0jjykC9HIL3xIkQiETCjSRDKBAm0cO0/gYpZprVNHvdjkiG8aed1lD38yNaCFT5Lld\n1rIp0ETEYTddKGZsppdMiAEq3S5r2RRoIuIoY4hixggSIZckw5Qq0DKRBwsfo5Qwgp8oFcT03Eyy\njj267yVBIRMZt8RPgTbDbqVd
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 18
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Other Kernels"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"There is no real reason to construct kernels from a $\\phi(x)$ function; we can actually just construct kernels directly. Each choice of a kernel function determines a particular feature space.\n",
|
||
|
|
"\n",
|
||
|
|
"A commonly used kernel is the Gaussian kernel:\n",
|
||
|
|
"\n",
|
||
|
|
"$$k(u,v) = c \\cdot e^{-\\frac{||u-v||^2}{2\\sigma^2}}$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"# Gaussian kernel\n",
|
||
|
|
"def k(u,v,sigma=0.1):\n",
|
||
|
|
" d2 = sum((u-v)**2)\n",
|
||
|
|
" return exp(-d2/2/sigma**2)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 19
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Let's look at this kernel directly.\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"def h(x,y): return k(array([x,y]),array([0.5,0.5]))\n",
|
||
|
|
"plotfun(h)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAE0CAYAAACigc+fAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztnV2MJFd5/p9z6qtndjdYILwrWPNfRGzMmu/YQeIimFgL\nEsKOg4lJiIyFSHIRRQKEBJFyEeUi9lpEARO4QgitQAKsXBAHEZRYyBYRmASZJIhYMkIs2Tj2XuA4\neHemu77O/+LUqX7r7fdUVc9Mz+70nEc60z311VXdXb9+3vd8KWOMQVBQUNAaSF/pEwgKCgraKwWg\nBQUFrY0C0IKCgtZGAWhBQUFrowC0oKCgtVEAWlBQ0NpoV0D71re+hRtvvBHXX389Hnjggb06p6Cg\noKAdSe20HVpVVXj1q1+NRx55BC9/+ctxyy234Ctf+Qpe85rX7PU5BgUFBY3Sjh3av/zLv+BXf/VX\ncerUKSRJgt/93d/F3/3d3+3luQUFBQUtpXinOz799NO47rrr2v9PnjyJ73//+51tlFI7P7OgoKCg\nHknB5Y6BNh5W/w/Aqeb5KfJ8XfQogFuv8DmsUo8iXN9B1aNYn2s73xSnx8Stdgy0l7/85bhw4UL7\n/4ULF3Dy5Elhy1NYnzc1KCjoyugUumZIBtqOc2g333wzfvKTn+D8+fPI8xxf+9rXcMcdd+z0cEFB\nQUG71o4dWhzH+OxnP4t3vvOdqKoKH/rQhzw1nKd2fnYHQqeu9AmsWKeu9AmsWKeu9AmsUKeu9Ans\nu3bcbGPUwZUC8OerOnxQUNCh1V+IlQKhp0BQUNDaKAAtKChobRSAFhQUtDYKQAsKClobBaAFBQWt\njQLQgoKC1kYBaEFBQWujALSgoKC1UQBaUFDQ2igALSgoaG0UgBYUFLQ2CkALCgpaGwWgBQUFrY0C\n0IKCgtZGAWhBQUFrowC0oKCgtVEAWlBQ0NooAC0oKGhtFIAWFBS0NgpACwoKWhsFoAUFBa2NAtCC\ngoLWRgFoQUFBa6MAtKCgoLVRAFpQUNDaKAAtKChobRSAFhQUtDYKQAsKClobBaAFBQWtjQLQgoKC\n1kYBaEFBQWujALSgoKC1UQBaUFDQ2igALSgoaG0UgBYUFLQ2CkALCgpaGwWgBQUFrY0C0IKCgtZG\nAWhBQUFro/hKn0DQYZBa4bHNCo8ddNAUgBa0QimsFmbuNQwC2IKAALSglUph9VALMAuaKwAtaKR2\nAqX9AJp7nZ0ogHDdFIAWNEI7BdOqQUZfZ9nXMuwxaB0UgBY0Qlcz0Nx57QRMAWbrpgC0IAyDZ69C\nx70EHIfRTkPiZV8n6GpWANqh1xhY7RXM9tqx7RY2uucYobLhIGqwYe2FCxfw9re/HTfddBNe+9rX\n4jOf+QwA4LnnnsOZM2dwww034B3veAeef/75lZ9s0KrkYKM9ZS9ANPQay5S9BOzQ6wQdJA0CLUkS\nfOpTn8KPf/xjPP744/jc5z6HJ598EmfPnsWZM2fw1FNP4bbbbsPZs2f343yDdiXpJlZk3TLHWKbs\nFYT24lyWPf4qYBq0Kg0C7cSJE3jjG98IADh69Che85rX4Omnn8bDDz+Me++9FwBw77334utf//pq\nzzRoj0RvSgqbZbSs01oVyFbp7CQYB5hd7Voqh3b+/Hn88Ic/xFve8hZcvHgRx48fBwAcP34cFy9e\nXMkJBu2ldntTXk039m5ef2xuTHKv9ZLHCNpPjQbapUuXcNddd+HBBx/EsWPHOuuUUlDK9wV7lDw/\n1ZSg1UuCzhgI7LSC4GqAHJUvqe9cl28f+ijJXSM/RqhEWK3ON6Vfo4BWFAXuuusu3HPPPbjzzjsB\nWFf27LPP4sSJE3jmmWdw7bXXeva+ddTpBu2laLgkrRvabychaB8o9lvG89y1V/NdH23P5oOT5Np8\nrxe0dzqFrhl6TNxq8BtojMGHPvQhnD59Gh/5yEfa5XfccQfOnTsHADh37lwLuqArpb1KiksJfV8u\nypf4X6ayYNn81zKVEGOuZydh9NjXC9pvKWNM70/KP//zP+M3fuM38PrXv74NK++//378+q//Ou6+\n+27813/9F06dOoWHHnoI11xzTffgSgH485WdfBDgDy13Gzoue4M7QCyrodfZSSjn9qlH7ktdmfR6\nY0LRvn2Da9t7/QUkdA0CbTcKQNsP+WrvhmDkq32kTmNsDeUy2y67n4PSsl/TZfbj2/qgNHQs3361\nsG3Q7iQDLfQUOLBaNsTpyxtJ68fmxWiSfOg1pOVDSXqFfiCMcU1jRF/Dne+yAJOuk+bsglNbtQLQ\nDqSWyY0NAYsfj64fgpR0jDGv7TsPaV1fEh/wh3kRus5qqOaSd4Oibm3ox6Lv2O64YXSP/VAA2oHU\nWPdEt/dt6zuW9izn2wwddzfuERjnknhYpwbW8/21sN45Q0P+58cdOj9+XQFmq1YA2oFSnxtCz7I+\np+RL6PscGj8HzZZT7UdXIQcrX7jninN7QBcsvuVuH6kD+xjXSCW9/wFuq1AA2oHR2DCzL7Ts+5/v\n5+u25As1+467aqBJDksKN33hZy0cQ5F1fc7Md20SsEL4uWoFoB0YDYWZY2HHITUEJF8o6su3LZOH\n2wu5sJCeJ22ywV2XrymHgxrdVnqvadenPufV59LGNicJWlYBaFelpBtlKMwcm6QfAyOfGxwC17Jh\n607EQeCcFQeXb7kLMQ3bVlruIEePoSHDjz7SUFUCl/Q5BNe2FwpAu+rkc1l9EBgTRlLH1be8L6Tk\n29BjSEDzwW+nYaiU3Of5MadaWM5BNyYs5SGnLzyVwEn/5+Kg5EAN2okC0K5K9YWWfLs+AC4TLtJa\nTV8+zVfzKeXb+kLZnfYqqNHvxqjc6/JtKQDd8TiwqDsDO8ZYhwZhPdh6Dj0fnIPGKgDtqtEySfSh\nMJMvo+v6wksOLGm5dIwrDTTJudFtpTDSgUyRdRSOzkEptr/k5Ph7SbcbCj+phkAYNKQAtKtGy4Zi\nfaFcX7g5FFpK22jPOmm573zo8v0GGgWbIo8UNhL8JHhJTUTcdprtQ1+Lb8tFPwfpeoLGKADtqtCy\n7mwozPTBzOe4+P4SqKSwVApFpeMB3RtWWt4nms+q2XIpB0a3paEldV4120ahC0sKHqnGVApx3X40\nf7eM6+Lv3dD2QVwBaFdUfa6Kb8OXSceQ3JcvNOSuijs0VyJh+yGgSeFs3/X2Qc3nlIaW+YBmhGW8\nKHZMCkEKY19FAg8z+XLf9VFxxxbANkYBaFdUY2E2BmhDeS5AhpnPuUWkDAHN9/p918lBLInCRwoz\nJddkPI99QKuaQs+JvzaFmVQpwCsTaNjoCz/5tToFmO1UAWhXRD4Hw7cZ42R8MOF5Kgla0vZuGQWa\nz4lJyyXnR89TWtbn0Hy5rWXCzD7HRisHpH2UsA0HjfRIc23S58f3UZCh5tsvSFIA2r5ryJXxbfqW\nAcOuixcfxCLhGJGwTnodaT2F107Dzj6Q+ZZT1yUBStqGOi9eKrKOuzd+LrQGVbNl/LrcI79uX/hJ\ngReg5lMA2hXRss6Mr+P/9yX8h8JCyYnx/fq2kdZLr+U757GiIKIaCiN9Ls2FmO5Rcm5uHYWZhgxI\nnlfjyziEqDPrg1WA2TIKQNt3DYWPPufiWz6UoPc5K+rM+pzYkFPjx/C9Hr9GKSyVJCX6qXyhJQca\nL/QcOeh8oWiFxXyYOx/qzij46DJfSCktl8AWYDakALSrRkNhpm/5UHKfAoeu9+XIfICLetb78mx0\nOT13KST2SQonqXh4aYRlFRYh586Pr1fsuUY3NKWQ4pJCTVpJAPLolvWBKwBsWQWgXTXqCzN5DkbK\ni3FIcEDx2soI9uP3hZZ8vSuxsJ3PldH1/Ho4gH2SwkV6o1ek+Go2S7ZdhTnMKOjcOVGwuWYbJTl/\nnvty//P8GQ0/6f++vNmYfFpQnwLQ9k1jHQnIesmZuUefM/OFgz4nxl0YhRmFGnVjHGocZtwJKnIZ\nZL2iz4W3wcAew1BgNEBr73Xq
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 20
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We precompute all the dot products, as before.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"n = len(data)\n",
|
||
|
|
"ks = zeros((n,n))\n",
|
||
|
|
"for i in range(n):\n",
|
||
|
|
" for j in range(n):\n",
|
||
|
|
" ks[i,j] = k(data[i],data[j])"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 21
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Let's look at the dot products."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imshow(ks)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 22,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0x45cb450>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAEyCAYAAAB02CyCAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvcmPJEl+7/cxM19izbUqq7qrlxrODDlD6ZEXArpK70Lw\nLyDP5L8hQGfe+T/wUdCFBwI8CIKuJHTiAHwS+Mjp6e7qriWXyAgPX23RwcwiPKMiIpeqrh6N6gdY\nmkeku4e5udnXfrsJ55zjI32kj/SRfgdI/tgN+Egf6SN9pPdFHwHtI32kj/Q7Qx8B7SN9pI/0O0Mf\nAe0jfaSP9DtDHwHtI32kj/Q7Qx8B7SN9pI/0O0PvBGj/+I//yC9+8Qt+/vOf89d//dfvq00f6SN9\npI/0MHIPJK21++lPf+p+/etfu7Zt3R//8R+7f/3Xf71xDvCxfCwfy8fyg5RtlPBA+ud//md+9rOf\n8fz5cwD+4i/+gr//+7/nl7/85Y3z/pdQ/yMDfsKXvOIJrznjFU8459FDf36DxJYSnxtu9sO2c/fd\nV4YSjwEsYHr1/wH8ZyDdKAmg3y7HI3h+Bj85gy8f+/r5E/j2HL565cuvX8FvXsPr2Tv2zfug/xP4\nH3+YWw8H8OkT+PQMnj3xx8+eQFHCi1fwXSgvXsGr8623OKDgGa94xis+5fXq+BWPeMETXnDGdzzh\nBU+45PDuzycVHDzx5TDUB2fweASfOnhmQ+3gUwv/fg7/9Q3819e+/r/fwLdz1mOnP54cfvzEOh7f\nnZ79Yc0Xf1TzxX+q+OKPKj7/TzWjI8PX/zLgm18N+fpXQ775lwH/8X/9M7r9n+583/RpxvCPpgz/\naMLgv58w/CNfmv+npPqXgupXi1AXtL+p79Xm+9G2eRrr/3nrFQ8GtBcvXvD555+vPn/22Wf80z/9\n01vnXYcB1OJoyQBI6RhRcsg1BoVFYlCr4vaCzG20OSjcxndqS4H1oDK9483rLb5DLW/ft39uvA+h\n7t/TgbXQdlDWMC/hsoBRDpcL/3nZ+P8bC0JAqiCRoVa+tkCHx8hY683fi8f3myjvSkIJRCoQmVzX\nmcR1Fte6m7VzoDU0LSwrWCzhau6PixKqet0XO8gi6UioyVkyYs6UIQ3XTFkyomZAS4p9yLiyBkwL\nbQVNAdUAlh3MHQwtpA6kA+fgVQGXJSwaqDrQNmBYAiqUeOwsGO2L7dXbSAlEKiGT6zqTuMeKbiio\nnGNeOK5eWaqF5vpVSnGpqBeSrhHcNxbIGbCVwcw15qJDf9/QHiZ03zXo8xZzrbGVxWkHsv+uYxsF\nWHCtxXUWWovr/Pu+FyUSksSP+VjLMF9f77jkfr+wJiHuNjj+9/ATL6kDkAlyGo6YkdPQkNOS0ZCv\nilmBzH0ovjXBTc7sRqvxAJYDWa8GaEPpQm1610UgE73Puzhh0zsvfu4DiwNjoGrgegl5Ckr4SX2x\ngDfX/vuyBW38/4YpjPN1meTQCSiAZSwOtAOa0P5+3X+WD0CJQE4T5EGCivWBwhZ+ktiF9vUcnAng\nvqxgVvjJbvFAdnkN86XvK71jsuMBrSGnYExGh8RikMw44JJDFoypHzKunAPTeTCrF34yOQcyB+HA\nOKgdFA6uHHw/hxdzOC+haKEzICRkKWQDX/JQGw1tDU3t69ZBu/0ZRSIR0xRxkCJDLQ5S3HFJc5gw\nt4rsQoKDTLa8+Srj6kVKcaFolvL+gKYttjDoNx3tqAYFrnO0Lxrar2v06w4z17jOISTIsX/H8iBB\nTlPkQYJrLXausfMOu9DYub4/oKWJX+hHA+Ar6P4d1H61/4MB7dmzZ3zzzTerz9988w2fffbZW+ed\n8Ye+bcwYc4wDBtRktExZsGRMyYglYxyCjvSBgBZpG9cUa4F/5BwYAqNQAEqgCqUHPlvZ3r64APA8\n1BH4dO+czRIArW48NybFGuDmJVwVHtCqxgOalDDM4HAIJ2NfjsdQKz+JLvGTq42/X+IRToU2dLw7\noD2/9Yw+iUQgJ4rkUUbyOCM588VcdujXLfp1Aw5cbaF00HSwrEEtfJNb4zm2xcJzbLEvdpBBUpNR\nMEIEMGvC5zkTFoyoyfaMqz3PZzV0le9vAsDZzINZE8BsBrx2njt7XcBFBLTIYadetB5NfBlPoGuh\nLGCpAjh2u9uQCMQkQT7KkY8HyDNfnEqplWJhBVxCO7MkrWT2MuX6ZUJxmdCWEnHP9+e0wywM+k3r\nwUw7D3DnHd3Lhu5Ni10YXGs99zhWyJMMdZaTnOWosxxbGszrBvO6AdngGusX4PtQqmA8gKMxHP0P\ncPif/WeA//K/be+qe/7Eiv7kT/6Ef/u3f+Orr77i008/5e/+7u/427/927fOe82ZbxvHVDf4sIYE\nzTWHJOgVmFUMH9CaCDzbuLQ+9QFtDExDIXwv8JO/6d23f//+vfvlee+4z72JLd/ZNYDJwJlFbq1q\n/MQuaigjoAUO7WgEZwfwySE8PYRlAgPnJ0OHn1hY4Jq1GN0B70PH8fxeZ4vUc2jJ45T08wHZFwPS\nL4bo72vEwK+wtraImfYiXeTQLNAYKBrQnefSqupWQLMBwBaM0KgVt1aTU5FTMaAmR98b0CKHVgdm\nO3BrbRI4M+DS+TVx6Hy7rxuYN/64C+8vTWE4hOkUDg7h4AjaxotQhPs2e95T6jk0+XiA+nyM+sIX\nt0xp5pL5HNorRzE3yLlgOVOUM0V5rWhKuef5dlDnsIVGnwtc57AB3MzcYK47zEyvODSUQI4T1GlG\n8mxI+sWQ5IsRdtGhRwqkFz3t9R7A3kVZ4qWR4wmcHcLjQzgc773kwYCWJAl/8zd/w5/+6Z9ijOGv\n/uqv3jIIALziCQBjlhxyTU67EjnHLEm84mcFZpJ7sqUr2gVmm8AWAW0EHABHvXMMntUpeduQsIvz\n61MErqhn65/bA8cIaLoneqaJ/9xq6EIxFjIFg8ChnR3AZyfw/BSuE/8zXeASsije9sGs4sdwNRSJ\nRE0UyeOM7PMB+c/H5H8wop36trnaYq46dCbAOg9oFmi0B/Sk8HpG3UHX+XqPyBk5MoOiJqdgRILG\nkNCh0CR0JJj79kUUOWPdVV7sLKUHs8T54RTtP60O3KX2wKwNiKQHaBM4PoaTUw/WuCB6VlDulkpE\n5NAeD1Cfj1A/PyD5gwPsd4rmN9BeWYpLg/haw0voGuFLLelqgbX30x1GDs11DjPXyDcSkUsPTLXF\nNaFuLSJXiLHygPbZgPRnY9Lfn2KvWhDCnzvXiFcPkLrSxHNkJ2N4cgTPTuF0uveSBwMawJ/92Z/x\nZ3/2Z3vPecNjwANWToNlTkbLhIJjrtAkNOSUjMhoSdBI7A3DwP2MBPsUBlGHluFFzjEe1KJoVuNH\n52bn7wPIze/voLAwJoid7e3nDhJfpgM4HcPTA/j8BCYpVM4zZOfOK6dXloEGL3am7LfibicRnuNm\n7Y9c73gnJQI5VqjjlORpTvqlBzUcXpQ575AThUikB4u280BAw9oaCG9bAbdT5NCanWfsf9K3qfcO\no+L+oZQLr9DOcxiNPZd2fAx5CV0DTQnlwE9eJcNPu95wcpBIxDhBHmfIp0PUl2PUz6cY52jODZ3p\n0Jct+tcN5ut315c67XDaYJe330uMBHKokEcpyVlO8vmI7GdjzHmCLTT2okV+nyCyBxhkUuXVLQcj\nD2RPjzyntofeCdDuQyaIAkvGKzFTk7BgSkeKwjBmiUExpAqraoomWR3vJ7HleBOI4qSvWU/4uGoX\n4fuo1M+2XL95r13WzvvQthfdu5913mJ2XcHrOQxSr1dbJPCdgws8h9ZGDu0KWOC5s/bebZM4Mjpy\nNBmanI4MjUHSktCQ0pKsylbq7EoH031bI4cSIQTtVxXd1xX6dRtElj5Hu7kgbIr174ui64TaqOP7\nNBv1O5JznsusKijmnlsT0ltOu8r//DQHcQQj5TnztgvcXhe4dYtbaOybGvNtiRgqEGC+WmK+XmJf\n17iHKN3fBxmHXRrMRYt+USNG
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 22
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Now we run the perceptron learning algorithm on these dot products again.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"c = zeros(len(vs))\n",
|
||
|
|
"for epoch in range(1000):\n",
|
||
|
|
" for i in range(n):\n",
|
||
|
|
" sign = (dot(c,ks[:,i])>=0)\n",
|
||
|
|
" if lo[i] and not sign: c[i] += 1\n",
|
||
|
|
" elif not lo[i] and sign: c[i] -= 1"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 23
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"def g(x,y):\n",
|
||
|
|
" kv = [k(data[i],array([x,y])) for i in range(n)]\n",
|
||
|
|
" return dot(c,kv)>0\n",
|
||
|
|
"plotfun(g)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAE0CAYAAACigc+fAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3V1sW/d9//E3JeqJjxL1QMqiLdmJHT8kadwmLdCLzW2g\nBBgaz2vSpN2QGl26XQwDlqJAsruiGBbb6MWSrrsqgkBogKa56oIiCzajiLEhbYfC3dp/6sxOZMmS\nLFIPpEiRlESROv8L65xIjawHiuQhDz8vgKh8Sh9+j2B+ch5+v+/PZRiGgYiIAzTZXYCISLko0ETE\nMRRoIuIYCjQRcQwFmog4hgJNRBxjX4H2zjvvcPz4cY4ePcqlS5fKVZOISElcpY5DKxaL3HfffVy+\nfJmBgQEeeeQRfvzjH3PixIly1ygisisln6H993//N/feey9DQ0O0tLTw1a9+lX/9138tZ20iInvi\nLvUvTk1NcfDgQevP0WiUX/3qV5ve43K5Sq9MRGQbW11clhxouw+rQWBo/eehDT87xbvAGZtrqKR3\n0fHVq3dxzrGNrb9MV7Z8V8mBNjAwwMTEhPXniYkJotHoFu8cwjm/VBGxxxCbT4a2DrSS76E9/PDD\n3Lhxg7GxMfL5PD/5yU84e/ZsqbsTEdm3ks/Q3G43P/jBD3j88ccpFos899xzd3nCOVR6dXVhyO4C\nKmzI7gIqbMjuAipoyO4Cqq7kYRu72rnLBXynUrsXkYb13S0fCmimgIg4hgJNRBxDgSYijqFAExHH\nUKCJiGMo0ETEMRRoIuIYCjQRcQwFmog4hgJNRBxDgSYijqFAExHHUKCJiGMo0ETEMRRoIuIYCjQR\ncQwFmog4hgJNRBxDgSYijqFAExHHKHnVJ2kMTawRIE2ANB5yZd13Dg9pAqQIYrDbhatF7k6BJtty\nYRAiwSDj9DJb1n3P0Mc4gyzip0hzWfctjUmB1qCaWMOFgYvtVzFsYZVu5hlijEPcKmsNHnJk8DFN\n/6Y61mhar0xnbbI3CrQG1EqeLpKESNDB0rbvbabIAFN4yZa9Di9ZokwCd0LM/N8EIRKEyOAr+2eK\nsynQGlALq/QyyxFG6SK57XtdGPjIVCTQfGQYYIpOFqyzsQJuRjnCCm0KNNkzBZrDuSnQwipuCtY2\nP4v0McNBJuhhzrba2lmmneVNNRRws0QHC3SSwUcBN6u0WGdwIttRoDlckBS9zNLNvLWtjRX6maad\nZRsr25r5EOIIo3jJMksvs/SSw2N3aVIHFGgOFyTFIOMc5qa1rYk1OliqyUBrYs26t9dFkmaKLOJX\noMmuKNAcwk3BuoRrYs3a3scMYeKEidtY3e65MOhgiQ6WaCW/PgIuALB+dO26/JS7UqA5RDvLRIjR\nzzSt5K3tPcwRIG1jZaUzH14ABEgTI0KMCCu02VyZ1CoFmkN0sEQ/05zg2qYnki2s0sKqjZWVzgy0\nLpIESFOkmTl6FGhyVwq0OuamgJcsXrKEidPHDEFSZZ+iZJcm1mhjhTZW6CJJmDhZvCQIrR+1V4Nv\nZRMFWh0zz2AGmCJMnBCJuj0b24l5BtrGCtP0M8UAOTwKNNlEgVbHzEA7xnX6mLGmMzmReY8wTJwO\nlsjh4TYH9IBANlGg1ZmN3S96mCNCDC/ZTQNnnciFQTNF4M4DggGmKOBmgU7SBFjEb3OFUgsUaHVm\nY/eLfqYJkqrJ8WSV5CNDlEn8LDLBQatjh4gCrU64MGhijVbyFet+US885PCQo59pAFIEiRNWlw5R\noNWLIClCJOhmvmLdL+qROROihVV16RAFWr0wv7iDjFes+0U9CpKimSJdJNWlQxRotayZotUpo5t5\nDnCbQcbtLqummJefIRLq0iEKtFrmI7Pea2KWCLG6ncJUDerSIaBAq2lmR9d7+RAv2R27yzYydekQ\nUKDVnI1dM8wuGRFi1hgs2Zq6dAgo0GrOxq4ZfczQRdKxo/8rRV06GpcCrcZs7JoRJEULq5v6m8nO\n1KWjcSnQaoDTu2ZUm7p0NC4FWg1opK4Z1aYuHY1lx7ukExMTfOELX+DUqVPcf//9fP/73wcgkUgw\nPDzMsWPHeOyxx1hYWKh4sU61sWvGUW7Qy6zjJ5tXi3lP8gTXrGX7dAnvXC7DMLa94xyLxYjFYjz0\n0ENkMhk+85nP8NOf/pTXXnuNnp4eXnjhBS5dukQymeTixYubd+5yAd+pZP116w+7ZpizAIKk7C7N\nsWboW/8tD1KkGQADFymCpAloiEdd+S5bRdeOl5yRSIRIJAKAz+fjxIkTTE1N8dZbb3HlyhUAzp8/\nz5kzZz4RaHJ36ppRfRu7dGxc2PgWhxhnUIHmAHu6hzY2NsZvfvMbPve5zxGPxwmHwwCEw2Hi8fpY\nVchu6pphnz/s0gGwSgsF3CQIkaTL2m527djP2DXX+l4qeYlbjjqdZNeBlslkePLJJ3nllVfw+zf3\nnnK5XOuXl1t5d8PPQ+uvxqWuGbXFnGFwDx/Rycf3gZfosLp3rNJS0r59ZOgiSYhExUKtHHXWh7H1\n1/Z2FWirq6s8+eSTPPvss5w7dw64c1YWi8WIRCJMT0/T19d3l799ZlflNgp1zagtZqC1scIBblvb\nE4S4yWEW8ZccFObUtSOMVmymRznqrA9DbD4ZurLlu3YMNMMweO655zh58iTPP/+8tf3s2bOMjIzw\n4osvMjIyYgWdfJK6ZtQuFwZ+FvGzuGm7lywZfMzRU3IYhUjQzzSDjFfsqfXd6jS7jRQabGTWjk85\n/+u//os/+qM/4sEHH7QuKy9cuMBnP/tZnn76aW7dusXQ0BBvvvkmnZ2dm3eup5zAnbOyjV0zIsTo\nY8busmQbi/iJEWGafvK0lrSPLpL0M02EWMUuOe9W5zzdzNLLPN0V+Vz7bf2Uc8dA2w8F2h0HuM0x\nrm/qmtHGit1lyTYKuFmiY1+T2lvJW40GKjUf9251jnKEGxzlJocr8rn2K3HYhuxeM0XaWKGd5U2X\nGOqaUX/cFLa8FK01d6szi5cUQTL4rG4jzr7HdocCrYxaWKWPGWtpOVMnC+qaIVVlPnzykLO6jWwc\nluJUCrQyMqcwHeUGPcxZ290U1DVDqipAGg85wsStZpcKNNmknWWrK8ZWZ1tmtwyzbY2IXVpYtV69\nzFrrlmbxksHn2MtPBdoemOOKBpja8myrlTwhEprCJDXDHGcH4GeRKQaYJKpAk4/nAp7i/S3HFVVj\nqovIXpiB1skC3cxbzS6dutK8Am3dxu4Xd2us2McMIRK0ktfTSqkbTazRxBodLNHLLEcYxUeGNAFS\nBB01+NY5R7JPG7tfmP3o/5CHHEFSOgOTumQ+hW9jhSApbnGIHB4FWr3b6tKwhVV1vxBHM/+NdzOP\nlyxZvEwxYHdZZdWQgbZVF4Rmiup+IVLnGjLQtuqC4MJQ9wuROtcwgdbEmjUupxpdEERqmdlk1EuW\nIs3WqLV61zCBZj7h6WXWWllJN/elUbWzbHXunbW+Gb113/m2YQLNXP3nKDfoIlnRDggita6DJSLE\n6GQBHxkKuJmjx+6y9s3Rgbax+4XZ8SJMXPfJpOFt7NKRp3V9BGaALF6Waa/bVeYdHWgbu1/0MUMv\ns1rAV+QP+MgwwBSt5IkTZpp+Zum1u6ySOD7QzO4XYeLWQwER+Zj51D9CjDZWyOFRoNUiFwZtrGg4\nhsg23BSsp/0ecnX95L++H2mIiGygQBMRx3DcJefGrhk9zNHLrBYkEdklP4tEmcTARYogaQLk8Nhd\n1q45LtA2ds3oZ5ogKTVcFNklcy2CAGlucYhxBhVodmpijSApokxyiFs0saYBtCK7ZI5NCxOngJsE\nIZJ0sUbTeo8al90lbstxgbZGEwlCfMQ95PAQIkEXSTpYsrs0kbphdrq9h4/wkLOCbYkOu0vblmMD\nbYU2UgQ5wigdLCnQRPbADDSzGeQoR9a/RQq0qjJwrZ80+8nhoYskUSbtLkukrrgwrMtPDzmSdDFJ\n1O6ydqRhGyLiGAo0EXEMx11y
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 24
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Note that we really only need to compute the kernel function for vectors that make a non-zero contribution to the discriminant function; this can result in substantial savings.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"len(c),sum(c!=0)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 25,
|
||
|
|
"text": [
|
||
|
|
"(50, 16)"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 25
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Complexity of Decision Regions"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"However, we have a problem now. The decision region shown above is \n",
|
||
|
|
"very complicated, far more than it should be.\n",
|
||
|
|
"We have seen effects like this as overtraining.\n",
|
||
|
|
"\n",
|
||
|
|
"The reason is that the feature space induced by the Gaussian kernel\n",
|
||
|
|
"is very high dimensional and many different sets of points are separable in it.\n",
|
||
|
|
"We can control this in one of two ways.\n",
|
||
|
|
"\n",
|
||
|
|
"- First, we can adjust the $\\sigma$ parameter; \n",
|
||
|
|
"larger $\\sigma$ correspond to smoother decision boundaries. \n",
|
||
|
|
"- Second, we can limit the number of vectors that make non-zero \n",
|
||
|
|
"contributions to the discriminant function.\n",
|
||
|
|
"\n",
|
||
|
|
"Support vector machine learning algorithms take both approaches."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# kernel learning with larger sigma\n",
|
||
|
|
"def k(u,v,sigma=0.5):\n",
|
||
|
|
" d2 = sum((u-v)**2)\n",
|
||
|
|
" return exp(-d2/2/sigma**2)\n",
|
||
|
|
"n = len(data)\n",
|
||
|
|
"ks = zeros((n,n))\n",
|
||
|
|
"for i in range(n):\n",
|
||
|
|
" for j in range(n):\n",
|
||
|
|
" ks[i,j] = k(data[i],data[j])\n",
|
||
|
|
"c = zeros(len(vs))\n",
|
||
|
|
"for epoch in range(1000):\n",
|
||
|
|
" for i in range(n):\n",
|
||
|
|
" sign = (dot(c,ks[:,i])>=0)\n",
|
||
|
|
" if lo[i] and not sign: c[i] += 1\n",
|
||
|
|
" elif not lo[i] and sign: c[i] -= 1\n",
|
||
|
|
"print len(c),sum(c!=0)\n",
|
||
|
|
"def g(x,y):\n",
|
||
|
|
" kv = [k(data[i],array([x,y])) for i in range(n)]\n",
|
||
|
|
" return dot(c,kv)>0\n",
|
||
|
|
"plotfun(g)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stdout",
|
||
|
|
"text": [
|
||
|
|
"50 29\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATQAAAE0CAYAAACigc+fAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3VtsXNXd/vHv2OPzKT7NTOJJ7BgSEodTaFIkVFW8RA4S\nImlK0rSlChGlcFFVBYTU9q7qDXHERUlLrxBCFkiEXKURoqiNUBAVhxaFCt42fUNxbGzHMz6MTzM+\njGe8/xd479r/jA+xPd4za56PZMkeT8a/HduP99prrd/2WJZlISJigDy3CxARWS8KNBExhgJNRIyh\nQBMRYyjQRMQYCjQRMcaaAu2dd95h165d7Nixg9OnT69XTSIiq+JZ7Tq0ZDLJbbfdxsWLF2loaGD/\n/v288cYb7N69e71rFBFZkVWfof3tb3/j1ltvpampiYKCAn7wgx/wxz/+cT1rExG5Kd7V/sPe3l62\nbt3qfBwMBvn4448XPMfj8ay+MhGRJaQaXK460FYeVo1A09z7TfPeN8Ul4H6Xa0inS+j4stUlzDm2\nzrk323spn7XqQGtoaKC7u9v5uLu7m2AwmOKZTZjznyoi7mhi4clQ6kBb9TW0ffv28cUXX9DZ2Uk8\nHufNN9/k8OHDq305EZE1W/UZmtfr5aWXXuLBBx8kmUzyxBNPLDLD2bT66rJCk9sFpFmT2wWkWZPb\nBaRRk9sFbLhVL9tY0Yt7PMCv0/XyIpKzfpNyUkA7BUTEGAo0ETGGAk1EjKFAExFjKNBExBgKNBEx\nhgJNRIyhQBMRYyjQRMQYCjQRMYYCTUSMoUATEWMo0ETEGAo0ETGGAk1EjKFAExFjKNBExBgKNBEx\nhgJNRIyhQBMRYyjQRMQYCjQRMYYCTUSMoUATEWMo0ETEGAo0ETGGAk1EjKFAExFjKNBExBgKNBEx\nhgJNRIyhQBMRYyjQRMQYCjQRMYbX7QIkexQwQyVjVDJGEdNul7Mm41QwRiXjVLhdiqwjBZqsWAEz\n1DNAI11UMep2OWvSQ5AuGhVohlGg5TgPFh4s8phd9rnFTOGjn2Y68NG/AdWljweLUaoI41/2udbc\n/9KsrtBkPAVajitmihoi1BChgJllnxsgRDFTG1Rd+lQxSiNdKxo6j1NBhBqGqVaoZTgFWo6zQ6qZ\nDkqZWPK5+SQpJ2pMoOWTpJ6BZZ8bIgDACJvSXZaskQLNcF4SFDCDl0TKz1czjJ8w2/iKcqIbXJ17\nSplYNsBt+SQZo5IB6kmSf8PnZ8kjgZcZCnQG5zIFmuGqGKWeAWoZSvn5cqLUM7DscDOXlRMlSA9e\nEikDa5oiBqhngHomKHWhQrEp0AxnXyvazrWUn/eSoJgpBdoSyogRpGfRPwpRysknyTgVCjSXKdCy\nWD5JipimmKlFh5Q++vETxk94g6szRyFxColTyVjKz5cRm1udV7no92GaIqYoZpqidJaa8xRoWayA\nGXz0EyBEGbGUz6ljcNFfRFkf9vo8gC1cT/mcAerpYzMD1G9kaTlHgZbF7F+kHXxBHYOLPkfDyfSy\nvw/VDKecNAD4gh1MUKpASzMFWpYoZYIyYgtm5sqI4SdMNcM6C3NRHrMUMb3kmrY6BtnCdWYocB5L\nkk+MMqKUL3hcVk+BliWqGKWBXgKEnMcKiVNDxIh1YaarYpRtfLXgD88UxfTSQA9BBdo6WTbQuru7\neeyxx+jv78fj8fDUU0/x85//nEgkwve//326urpoamri3LlzbNqkhYfpYs9W3sb/OY/dzLYlcVcl\nY1QwvmDZxxiVJMlnkDrtKV0nHsuyrKWeEAqFCIVC3H333USjUb7xjW9w/vx5Xn31Verq6vjFL37B\n6dOnGR4epq2tbeGLezzAr9NZv3GKmKaKUSoZWzBjFqSHJjppoNfF6mQ9TVBKF4100cgoVQseH6OS\nUaqw8LhYYSb7Damia9kztEAgQCDw9daP8vJydu/eTW9vLxcuXOC9994D4OTJk9x///03BJrcvBIm\nCRCikS5KmHQer2Bc18kMY89SFzG9YDlHPz6nE8hikwyS2k1dQ+vs7OTTTz/l3nvvJRwO4/d/3anA\n7/cTDmud01rkMYsHizJiBAixk6s5tRUpFxUwQy1DNyzYLWWCKOX0sRkP/z0LmSXP6fwhqa040KLR\nKEePHuXMmTNUVCwc73s8nrnhZSqX5r3fNPcm8xUSp5phaojgJ0w9A4su0BTz2TsTAOea2yx5cz1R\naohS7mZ5Lumce1vaigJtZmaGo0ePcuLECY4cOQJ8fVYWCoUIBAL09fXh8/kW+df3r6jcXGavY2qm\nAz9hyohp7VgOKydKA71sYsQ5G0vgpYNmpinK0UBrYuHJ0Hspn7VsoFmWxRNPPEFLSwvPPPOM8/jh\nw4dpb2/nl7/8Je3t7U7QydJSdb+oYBwf/Wyle9EFspI7ipmimKkFPwsJvExSwgibiFKu7h6LWHaW\n869//Svf/va3ufPOO51h5alTp/jmN7/J8ePH+eqrrxZdtqFZzhvVMnRD94siptlMHwFCum4mKSXJ\nJ0SAPjYTxq/uHqud5fzWt77F7GzqdU4XL15ce105JlX3izxmKWFSC2RlUXnMUkOEEiapZljdPRah\nnQIboJC4M4xQ9wtZDQ8WJUxSwiSFxJ3uHsDcT1axhp8o0DaEvRQjQAgf/VpPJmsyv7tHJWNzP1kB\ntSZCgbYh7I6nu7miZoqyZvO7e1Qy5myfUqAp0NKmkDhlxCgjRgO91DNAJWPkk3S7NMly87t72PeE\niFG24HraBKU3PJYLFGhpYt9NKUgPdQxSzfCCVd8i66GESTbTRxHTxCl0Hg8RoIegAk3WRzFTbKaP\n3VyhgnHymFVXDFl39h9OP+EFW6IKiTNOhXMLvlyhQFtHBczMzT2NOVuYlur3L7JWHqyUlzGqGWYr\n3QCMUsUYlTlxtqZAW0f2xdpGuvDRTxWjmgAQV9jrHSsZ4yu20UWjAk1Wxu6UYa8za6YDH/1ulyU5\nrIJxKhjHT5gEXiLUMEy18R07FGhrZK/grmaYegYIENKKf8kY9s/nLXxJKRNOsE1S4nZpaaFAWyP7\nB2Y712igl3KiCjTJGPbPp90JuYPmuf0GCjSZx+6aYXdFCNLj9LASyRQeLGf4WUaMCUoZppo4hXM3\nOCwwavipQFulKkbn+h0MsJm+RW/0K5Ip7EmrJPlUMep07Ji/fi3bKdBWyZ5FaqbD2XguksnsQJt/\nf4oRNinQclWqrhmazZRskU/S2Y6XwMt1thi32FuBdhPUNUMksynQboK6ZohkNgXaMtQ1Q0xUwAyb\nGCFIDxFq5n7Cy7J+xlOBtgx1zRATze/S0cdmemlgglIFmunUNUNMNL9LRwmTTFDKdbZkfRtvBdoy\nPFjkMYuXhLpmiDHmd+moZIwGekngZYRNjFHJOBXLvEJmUqCJ5Dh7squCcbrZSheNCjTT2B00vCSc\n90VMVMoEpUywmT4sPESocbukVVOgpVBInGqGqSHiNGrUcFMk8ynQUrC3iDTTgZ8wZcS05kwkCyjQ\n5tjDywJmqGIUH/1spZs6Bt0uTWTDeElQwiTlREngZYYCkuS7XdaKKdDmeLCoIUI9A/joZzN92nAu\nOcduulDEtNONw75DezZQoM2xG+E100GQHkqYVKBJzqlkjELi1DHIVXYySYkCLRt5sChlwjlLE8lF\ndjeZMmKECGTdtePsXhYsIjKPAk1EjJHzQ85SJigjRiVjzs0kRHKdfS+CACGS5BOjjCjlzFDgdmlL\nyvlAq2KUBnrZwnVqGaKcqNslibjOniSDr+/x2UsDPQQVaJnOnqa+jf9TJw2ROXagbWKEWoZIks8g\ndRm/xzPnA23+gloR+S/7D3wBM1mzn1mTAiJijJw8Q/NgOX3O8klmxV8eEVleTgZaOVGnm0YDvVQx\n6nZJIrIOcjLQyogRpIdmOqhgXDObIobIyUArZoo6BmmkS33ORJbhwaKIaefuZzMUMENBRt5QJScD\nTURWzu4PmCSfKkadLhxxCt0u
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 26
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": []
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {}
|
||
|
|
}
|
||
|
|
]
|
||
|
|
}
|