nvidia-AI.summerschool17-no.../teaching-ncso/12-linear-threshold-classification.ipynb

177 lines
20 KiB
Text
Raw Permalink Normal View History

2017-09-22 17:38:09 +00:00
{
"metadata": {
"name": "12-linear-threshold-classification"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Title: Linear Threshold Units\n",
"Author: Thomas M. Breuel\n",
"Institution: UniKL"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"\n",
"from pylab import *\n",
"from IPython.core.display import Image \n",
"def fig(x): return Image(filename=\"Figures/\"+x+\".png\") \n",
"from pylab import *\n",
"def figs(*args):\n",
" for i,f in enumerate(args):\n",
" subplot(1,len(args),i+1)\n",
" axis(\"off\")\n",
" fig = imshow(imread(\"Figures/\"+f+\".png\"))\n",
" \n",
"from scipy import linalg"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 267
},
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Neurons as Linear Decision Makers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before embarking in more detail on learning algorithms, let's take a general look at neurons as classifiers or decision makers."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(McCulloch-Pitts Neurons)\n",
"\n",
"Recall that we arrived at the McCulloch-Pitts model as a simplified model of the computation performed by neurons.\n",
"\n",
"Component-wise notation:\n",
"\n",
"$$ y_k = \\phi(\\sum_{j=1}^m w_{kj}x_j+x_0) $$\n",
"\n",
"Matrix notation:\n",
"\n",
"$$ y = \\phi(W \\cdot x + x_0) $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(Linear Decisions)\n",
"\n",
"For many kinds of problems, linear decision rules are common, and these map well onto McCulloch-Pitts neurons.\n",
"\n",
"That is, rules of the form: accept if $x_1 + 0.7 x_2 \\leq 1.1$ .\n",
"\n",
"The reason is that a lot of decision rules are really rules based on costs, and costs are of the form $\\hbox{quantity} \\times \\hbox{unit cost}$.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(Perceptrons)\n",
"\n",
"Here is an example of this.\n",
"\n",
"The _decision rule_ is \n",
"\n",
"$$D(x) = \\left\\lfloor {1 \\choose 0.7} \\cdot {x_1 \\choose x_2} \\leq 1.1 \\right\\rfloor$$\n",
"\n",
"This is obviously the same form as for a McCulloch-Pitts neuron with a Heaviside function as the nonlinearity.\n",
"\n",
"These kinds of linear decision units are called _perceptrons_.\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"\n",
"xs = rand(100,2)\n",
"ys = 1*(xs[:,0]+0.7*xs[:,1]>1.1)\n",
"plot(xs[ys==0,0],xs[ys==0,1],'b.')\n",
"plot(xs[ys==1,0],xs[ys==1,1],'r.')\n",
"plot([0,1.1/0.7],[1.1,0],color='green')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 284,
"text": [
"[<matplotlib.lines.Line2D at 0x1021a190>]"
]
},
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD9CAYAAABHnDf0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtUU2e6P/BvEI7FVlGRQSUwyE3uYahA0VZivUfqcTml\nh9bTUWsxERxLO22dmdrjpbNQO61rvGFiq7aO4rKjU+0AUrUaq3jBNv6AAazUgwWp9YgVddRCAu/v\nD0YqF5MQdvYtz2ctVk2z2fsbdvaTd7/vu3cUjDEGQgghsuImdABCCCHco+JOCCEyRMWdEEJkiIo7\nIYTIEBV3QgiRISruhBAiQzaL+0svvQRfX1/ExMR0+/zOnTuhUqkQGxuLMWPGoKysjPOQhBBCesZm\ncZ87dy6Kiooe+nxQUBC+/PJLlJWV4e2338b8+fM5DUgIIaTnbBb3p556CoMGDXro88nJyfDy8gIA\nJCUl4fLly9ylI4QQ4hBO+9y3bNkCjUbD5SoJIYQ4wJ2rFR09ehRbt25FcXFxt88rFAquNkUIIS7F\nkbvEcNJyLysrQ0ZGBj777DOrXTiMMdH/LF26VPAMlJMyUk7Kef/HUb0u7rW1tZg5cyZ27NiBkJCQ\n3q6OEEIIB2x2yzz//PM4duwYGhoa4O/vj+XLl8NsNgMAtFotVqxYgRs3bmDBggUAAA8PD5SUlDg3\nNSGEEKtsFvddu3ZZff7DDz/Ehx9+yFkgoanVaqEj2IVyckcKGQHKyTWp5HSUgvWmU6cnG1IoetV/\nRAghrsjR2km3HyCEEBmi4k4IITJExZ0QQmSIijshhMgQFXdCCJEhKu6EECJDVNwJIUSGqLgTQogM\nUXEnhBAZouJOCCEyRMWdEEJkiIo7IYTIEK/Ffd2ZdWhpbeFzk4QQ4pJ4Le57q/biiS1PwHTFxOdm\nCSHE5fBa3I2zjchKyMLUnVORXZSN2023+dw8IYS4DF6Lu0KhwJy4OajIrMDNppuIzI3Ep1Wf0n3e\nCSGEY4J+WYfxkhG6fB3CvMOwQbMBAV4BfEQhhBDJkOSXdagD1SjVlSJheALiDfF4/+T7sLRahIxE\nCCGyIJqv2au+Xo3Mwkxcu3MNhlQDkpRJfMQihBBRc7TlLpriDgCMMeSV5+H1Q69jZsRM5DydA69H\nvPiIRwghoiTJbpnOFAoFZsXOQmVmJSytFkTmRmL3P3fTgCshhPSQqFrunRXXFkNXoINygBIbNRsR\nNCjISekIIUScZNFy72xMwBiY5pug/qUaiR8kYuXxlWhuaRY6FiGEiJ6oW+4PqrlRg6zCLNTerIU+\nVY8nA57kMB0hhIiTLAZUbWGMYU/lHmR/ng1NqAarJ6zGYM/BHCUkhBDxkWW3TGcKhQJpUWmozKzE\nI+6PIHJjJHaU7aABV0II6URSLffOSupLoM3XwtvTG7nTchHmHcbp+gkhRGhOa7m/9NJL8PX1RUxM\nzEOXWbRoEUJDQ6FSqXDu3Lkeh3BUol8izmachSZUg9FbRmO5cTmaLE28bZ8QQsTKZnGfO3cuioqK\nHvp8YWEhvv32W1RXV2Pz5s1YsGABpwFtcXdzx2vJr8GkNeHcD+eg0qtwtOYorxkIIURsbBb3p556\nCoMGDXro85999hlmz54NAEhKSkJjYyOuXr3KXUI7BXgFYF/6PqyasAqz983G7H2zce3ONd5zEEKI\nGPR6QLW+vh7+/v7tj5VKJS5fvtzb1TpsRvgMVGRWwNvTG9GborH13FYacCWEuBx3LlbSuXgqFIpu\nl1u2bBkA4B//AFpa1Bg+XI28PGDgQC5S/Kx/3/5YM3kNXox9Edp8LT76fx9Bn6pHpE8ktxsihBCO\nGY1GGI3GXq/Hrtkyly5dwjPPPIPy8vIuz+l0OqjVaqSnpwMAwsPDcezYMfj6+nbc0AMjvmo1cOxY\n2/9PSwM++aSXr8KKltYWbPpqE5YfWw7t41q89dRb8PTwdN4GCSGEQ4LNc58+fTq2b98OADh9+jQG\nDhzYpbB31q9f238TEoDNm3ubwLo+bn2wMHEhSnWluHD9AmI2xeDgxYPO3aiYzZ/f9umq0QCNjUKn\nIYQ4ic2W+/PPP49jx46hoaEBvr6+WL58OcxmMwBAq9UCABYuXIiioiI8+uij2LZtG+Lj47tu6IFP\nn8bGthqzeTP3XTK2FFYXIqswC8nKZKyZvAZDHxvKbwCh8XnaRAjpNZe4/QBX7prvYsWxFdhybgve\nGfcO5j8+H24KSV2s6ziNBjhwoO206eBB/j9dgbZP9gsX2k7hnDHoQoiMUHF3QPnVcmjztWBgMKQa\nEOsbK3Qk5xPytOm+B88ehg4FqqqowBPyEC5xbxmuxfjG4MRLJzA3bi4mbJ+ANw+9iTvNd4SO5VwD\nB7Z1xQhZTO8PugDADz+0fdgQQjjl0i33B13911W8dvA1FNcWY4NmA1LDUoWOJF+NjUBERFthF7J7\niBAJcOluGS67cA9dPITMwkyofFVYO2Ut/Ab4cRfUDi7THS2G7iFCJMClu2UuXGjrwj1woPdn+BOD\nJ6JMV4YInwio9CqsO7MOLa0t3AS1A5evRdTE0D1EiIzJorhzPW/e08MT74x7B8fnHsfeqr14YssT\nMF0x9X7FduDzGgBCiHzJolvGmWf4jDF8XPoxFh9ejOejn8c7495B/779ud3IA6i3ghDyIJfuc+dD\nw90GvHHoDRz+38NYN2UdZoTPeOg9dIhMucyACBETKu48MV4yQpevQ5h3GDZoNiDAK0DoSIQvdHUv\nEYBLD6jySR2oRqmuFAnDExBviMf7J9+HpdUidCzCBxoQIRJCLfdeqL5ejczCTFy7cw2GVAOSlElC\nRyLORAMiRADULSMQxhjyyvPw+qHXMTNiJnKezoHXI15CxyKEyAR1ywhEoVBgVuwsVGZWwtJqQWRu\nJHb/c7csP8gIIdJBLXeOFdcWQ1egg3KAEhs1GxE0KEjoSKQ3aIYMERi13EViTMAYmOaboP6lGokf\nJGLl8ZVobmkWOhZxlMtcMkzkhoq7E3j08cDiJxfjbMZZHK89jnhDPE7UnhA6FnGEPTNk6NutiAhR\nt4yTMcawp3IPsj/PhiZUg9UTVmOw52ChYxF72TNDhua/EyeibhmRUigUSItKQ2VmJR5xfwSRGyOx\no2yHS37QSZI9Nzij+e9EhKjlzrOS+hJo87Xw9vRG7rRchHmHdXiexu8kiOa/Eyeiee4SYmm1YN2Z\ndcg5noPfJv4Wv3/y9+jr3hcAneETQjqibhkJcXdzx2vJr8GkNeHcD+eg0qtgvGQEQGf4hBBuUMtd\nBPad34dFBxZh3IhxeDvxPfwx24fO8AkhAGTQcnfl2WQzwmegIrMC3p7eGJMXjSl/2AovL/ogBODa\nbwxCekE0LXfqa25jumKCNl8LT3dP6FP1iPSJFDqSsOiNQVyc5Fvu1NfcJn5YPE7PO43nop5Dykcp\nWHJkCe6Z7wkdSzj0xiDEIaJpudNssq6+v/09souyYbpiQu60XEwKniR0JP7RG4O4OJoKKWOF1YXI\nKsxCsjIZayavwdDHhgodiRDCE8l3y5CH04RqUJFZgQCvAMRsioH+Kz1aWavQsQghIkYtd4kpv1oO\nbb4WAKBP1SPWN1bgRIQQZ3Jay72oqAjh4eEIDQ3F6tWruzzf0NCAKVOmIC4uDtHR0fjoo496HILY\nL8Y3BideOoE5cXMwYfsEvHnoTdxpviN0LEKIyFhtube0tGDkyJE4fPgw/Pz8kJCQgF27diEiIqJ9\nmWXLlqGpqQkrV65EQ0MDRo4ciatXr8Ld3b3jhqjlzrmr/7qK1w6+huLaYmzQbEBqWKpdv0f3ryFE\nOpzSci8pKUFISAgCAwPh4eGB9PR07N+/v8Myw4YNw61btwAAt27dgre3d5fCTpzD9zFf7Jy5Ex88\n8wFe/fxVPPvJs6i/VW/z9wT5/gm6GIkQXlmtwvX19fD3929/rFQqcebMmQ7LZGRk4Omnn8bw4cNx\n+/ZtfGLlIpNly5a1/1utVkOt
}
],
"prompt_number": 284
},
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Linear Threshold Units as Measures of Similarity"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(linear threshold units as measures of similarity)\n",
"\n",
"Assume both inputs and weights are normalized.\n",
"\n",
"$$ ||w||=1, ||x||=1 $$\n",
"\n",
"The dot product becomes the cosine of the angle, the _cosine similarity_ between the vectors $w$ and $x$:\n",
"\n",
"$$ y_l = w\\cdot x = cos \\angle(w,x) $$\n",
"\n",
"Alternatively, we also get a relation to the Euclidean distance:\n",
"\n",
"$$ ||w-x||^2 = w^2 - 2w\\cdot x + x^2 = 2-2w\\cdot x $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(pattern recognition)\n",
"\n",
"Perceptrons therefore detect pattern as follows:\n",
"\n",
"- store normalized target patterns in the weights $w$ of each neuron\n",
"- normalize the input vectors $x$\n",
"- an output value above some threshold indicates that the pattern is likely present\n",
"\n",
"This is implicitly the basis of much of machine learning, and it explains why perceptrons and \"neural networks\" with McCulloch-Pitts neurons are so successful."
]
}
],
"metadata": {}
}
]
}