nvidia-AI.summerschool17-no.../teaching-ncso/46-som-full.ipynb

738 lines
1.6 MiB
Text
Raw Permalink Normal View History

2017-09-22 17:38:09 +00:00
{
"metadata": {
"name": "46-som-full"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Title: The Self-Organizing Map Algorithm\n",
"Author: Thomas Breuel\n",
"Institution: UniKL"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"\n",
"from scipy import *\n",
"from pylab import *\n",
"import tables\n",
"def showgrid(data,c=10,r=None):\n",
" if r is None: r = (len(data)+c-1)//c\n",
" for i in range(min(r*c,len(data))):\n",
" subplot(r,c,i+1)\n",
" w = int(sqrt(len(data[i])))\n",
" imshow(data[i].reshape(w,w))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 72
},
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Reading MNIST"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"with tables.openFile(\"mnist.h5\") as db:\n",
" print db\n",
" images = array(db.root.deskewed[:50000])\n",
" labels = array(db.root.labels[:50000])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"mnist.h5 (File) ''\n",
"Last modif.: 'Tue Jun 5 10:16:56 2012'\n",
"Object Tree: \n",
"/ (RootGroup) ''\n",
"/deskewed (EArray(60000, 28, 28), shuffle, zlib(9)) ''\n",
"/images (CArray(60000, 28, 28), shuffle, zlib(9)) ''\n",
"/labels (CArray(60000,), shuffle, zlib(9)) ''\n",
"/test_deskewed (EArray(10000, 28, 28), shuffle, zlib(9)) ''\n",
"/test_images (CArray(10000, 28, 28), shuffle, zlib(9)) ''\n",
"/test_labels (CArray(10000,), shuffle, zlib(9)) ''\n",
"\n"
]
}
],
"prompt_number": 73
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# showing a sample\n",
"gray()\n",
"figsize(10,10)\n",
"showgrid(data,10,10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAJLCAYAAAAVYcl7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsfVlsnNd1/284+76Sw204w01ctC+27MaKbSTO0iRu0rRB\nizY1srRFHwoULtrmoWnTvsR9CLo/FKhRuA0aJH1omiaNndiO7Fi2IlOkJFIkRYrrcDj7vu//B+Vc\n3/k0+wwp/xUeYCCK8/H77vnOveeee5bfEZXL5TKO6IiO6IiO6IiO6IiOqCb1POgBHNERHdERHdER\nHdERvd/pyGA6oiM6oiM6oiM6oiNqQEcG0xEd0REd0REd0REdUQM6MpiO6IiO6IiO6IiO6Iga0JHB\ndERHdERHdERHdERH1ICODKYjOqIjOqIjOqIjOqIG1LbB9PLLL2N6ehqTk5P4m7/5m26O6X1DRzw+\nHPSw8/iw8wcc8fiw0MPO48POH/CLwWNNKrdBhUKhPD4+Xt7a2irncrny6dOny8vLy+3c6n1LRzw+\nHPSw8/iw81cuH/H4sNDDzuPDzl+5/IvBYz1qy8N07do1TExMwOFwQCqV4jd+4zfwP//zP9225R4o\nHfH4cNDDzuPDzh9wxOPDQg87jw87f8AvBo/1qC2DyeVywWazsf8PDw/D5XJVXCMSif6//vzSL/3S\nQ8/jL4IcH3YefxHm6S8Cjw/7PP1F4PEXYZ7+IvBYjyR1v61BjW5KJBaLIZHce4REImE/85TJZKBQ\nKGreo9H33bpHKpVCT8979mM2m617PZFMJoNcLgcAyOVy9jNRLBaDTqere49YLAatVgsAKJfL973f\neDze1D3qXRMKhSrefzweb1qOvOwkEgmkUmnF9+l0Gkqlsu49Gl3TjXskk8kKGWYymaZ5lMvlbI7w\nPxNFo1Ho9fqaf0/fl3/eaYiXI/3b7D3qUTAYrJBjNBqtez0RLzepVHqfDIF7a0ClUtW8R6Pvu3GP\nVCoFqVSKfD7PfpdOp+s+k6iRvjksXdLommq6ptl5KpVKIZPJ7vuZKJlMQq1W171Ho2sSiQQ0Gk1H\n94jFYhCLxRXXt6tvmpUj3b9ZXdLtPSOTydS9nkgmkzG58T/z1EgGjb4vl8tIJBJsX2nnHolEAjKZ\nDLlcruJ3zdBBzlPSsclk8kDmaT1qy2AaGhqC0+lk/3c6nRgeHr7/5hJJw0n3fqGenp6KsWaz2aZ4\nlMvlDY2ZZogWe09PD/u5XC6zydEpSSSSinHG4/GW5NhIAb0fqKenp2KcmUymaR4VCkVDY6UZqnZS\n6ZYMgXuy4McZjUab4k8qlTY0djoh3jgUiUQd8Sw06NLp9EOlb6rpmmbnqUwma7jRtEvdlKFYLK4Y\nZzKZPPB9gx9vN9dcLRLKMZPJNC3DRht9N8bWrIFaj4QGXSKReF/MU5FIxHjs9jytR22F5C5cuID1\n9XVsb28jl8vh29/+Np599tl2bvW+psPgkRc2v9HWMpa6aUT9IsjxsHgkmVRz73ZTZtXo/SjDbihr\nnt6PPHaT3g9r8aCNjG7y2Ez45EHc60HLsBp1W64PikfSo8LDKP85aGrLwySRSPBP//RP+OhHP4pi\nsYgvfelLmJmZqXpdM/dq93t6QWKxuOqLJKLvgdqKvNpzmuFRGIKr9321cBsAZsEXCgX2KZVKLMTA\nW/i1xt/KOIi6JceDlnOta4SLpNo9muWxnffHk0KhYLIhGebzeZRKJYhEIibHWnOgmWfUuqYZ/qqF\n4Fq9pt73JAeJRFJXcbX7jIOepySXWtfwuqYRtTOOZudpJzKqdo1IJEKpVGIfeg/5fJ6d4KvN13bG\n0U19U2uOkQwb5qIIrhHer12d1gx/1UJwrV5T6/tyucxk2dPTw+RZTe+0+4wHMU+FVCwWUSqVWBhU\nKpVWXZvdGAdPovIBmWUikagrIY4HRdFotKHFKhKJMDQ01PQ9q01aYa5LT08P5HI5pFIpenp6UCwW\nkc1mUSgUUCwWW2ekBrlcrqYscpFIBKPR2LXndpMahb3C4XDTPI6MjHQ8FuFJh9zZZOQUi0VkMhnk\n8/munYZ2d3ebmqdms7krz3sQFAwGm+KxE33Dr0Oh17fR9Z1SM7qGxtLX19eVZ/Kk0+mg0+mg1+sh\nkUhQKpUQDAYRCoWQz+e7ond8Pl/TPBoMhraeUU1+h0mRSKSpedrf338gzy+Xy+jp6WF5VWQ8dXOu\nejyepnjs9jzleSgWixCLxZBKpTCZTNBqtUilUkgkEmwt8U6SVqjRPG3Lw0TkcDig0+nY4K9du9bJ\n7QA0P9nJuBD+LZ3oq52O+AnULHWTx2qTlv+dRqOB2WzG6OgoLBYLCoUCvF4vNjc3EY1GkUqlKpRC\nNxZBt2XYzGbTLaKEUJFIhGKxiFwuV1W2BzFPq1G5XEY+n4dCoYBWq4Xdbsfg4CCMRiPi8ThcLhdc\nLhcCgQC7vlt0WDwKqV0Zt8r7QfNXL3wq1DW8DunmHD8MGZLeoDVTLpcxMjKCs2fP4sKFC9Dr9cjn\n83j99dfx9ttvw+/3t5Sw3Yi6xWO18ZBMeI9ZvXHTd2Kx+L68rU6Mr8Nei/xhTS6XQ6VSQS6Xo1gs\nIhAIIJ/PM69cN/aNw+aPZEAes1wuB6PRCLvdjsceewwTExNYXFzE0tISwuEwSqVSV/nlqSODSSQS\n4fLlyzCZTN0aD7sv/SsSiSAWiyEWi9kLKxQKsFgs6O3thVwuh1KphFarRSQSwdbWFtRqNUwmE+x2\nO3p7eyEWixGPx+HxeLC1tcXir4VC4T6j67B4JCJrWKlUYnR0FLOzsxgbG4PVaoVEIoHf78fm5ib2\n9vawt7cHp9OJRCLRMPTRLHWLP2FF2EGd8srlMqv4mp2dhd1uRzgchtvtxubmJnK5HJsn/NgOUob8\nc0iWRqMRx44dw+zsLIaGhlAoFODz+fD2229jfn4e8Xi8ovqkG88+DB6FVCvPjldSnSZm0j0Oeh0S\n9fT0sHA4JfYaDAZoNBoolUp4vV74fD5ks1kUi8Wu5tIctAz5scpkMiiVShw/fhyPPfYYjh07BpVK\nhUKhgJWVFWg0GoTD4a5uON3ikTdspFIp5HI5RCIRZDIZzGYzrFYrBgcHmZeeN4iIn1KphFwuB6/X\nC5fLBafTybwX7wcem6VyuQypVAqFQoHx8XE4HA7k83n4/X5EIhFkMhkWeno/7RmtEu/Bl8vlMJvN\nsNvtmJ6eRk9PD3K5HJxOJ2KxGEqlEhtrN6kjgwnoTABCa55OcvxHLBZDoVCwMBWFqCYnJ3H8+HHo\ndDqYzWYMDg5ic3MTr732Gvr6+jA5OYmnnnoKx48fh1wuh9PpxPz8PF5++WX4fD6WJ9RMpn23Nv9q\n3pdSqQS5XA6DwYDp6Wk8+eSTGBoaQl9fH7RaLRKJBPb393Hnzh3cunULsVgM0WiULQD+FNXuqbdb\ni4hkVi6X2em124YTGUxarRaPPvooLl26hLW1NczNzcHpdCKXy9U9fR4U8Tk8SqUSBoMBY2NjOHv2\nLCYnJ6FQKJDL5VAsFrG/v49CodBVg4kfw0FStYTLas/mPRn8NZ0osIM0wvkcJZKhUqmETCaDXq+H\nw+FAf38/ent7sbCwgEKhgGAw2DTkQStjOQziN53jx4/jzJkz0Gg0EIvFKBaL0Gq1UCgUHRsPtZ7d\nCfGGj0QigVqthsFgYHrhxIkTOH/+PB5//HFIpVJks9n7qsZEIhEKhQIikQjm5uZw5coV+Hw+FItF\n9PT03BfKanXMh7UWKWoil8vR29uLs2fP4vHHH4fH48HS0hJu377dVaOeqJv8Ndq3eA8a7XdyuRx6\nvR4mkwn9/f3o6elBLBbDzZs3kcvlkEwmK5ws3aKOPUwf/vCHIRaL8fu///v43d/93YrveVwKIZ4G\nvQDK8aB/lUolTCYTrFYr1Go11Go1LBYLzGYzjEYjxGIxcrkcDAYDjEYjw3ggV2S5XIZWq0VfXx+M\nRiMKhQISiQS8Xi+8Xi8SicR9
}
],
"prompt_number": 74
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# reshaping into data vectors\n",
"hw = images.shape[1:]\n",
"data = images.reshape(len(images),prod(hw))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 75
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Self-Organizing Map\n",
"==================="
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Self-organizing maps are similar to k-means algorithms: they take in\n",
"a set of data points and generate a set of cluster centers.\n",
"\n",
"But there is an additional constraint on the cluster centers:\n",
"they are assumed to be laid out on a 2D grid, and the cost function\n",
"that we are optimizing takes this into account."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(k-means cost function)\n",
"\n",
"We can think of $k$-means as optimizing a cost function via EM or gradient descent.\n",
"\n",
"For k-means, our cost function is:\n",
"\n",
"$$ E = \\sum_i ||x_i-\\mu_{c(x)}||^2 $$\n",
"\n",
"Here, $\\mu_{c(x)}$ is the center closest to the training vector $x$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(SOM cost function)\n",
"\n",
"With the self-organizing map, we modify this slightly:\n",
"\n",
"$$ E = \\sum_i ~~~ \\sum_j ~~~ \\alpha(j,c(x)) ~~~~ ||x_i-\\mu_j||^2 $$\n",
"\n",
"Here, $c(x) = \\arg\\min ||x-\\mu_j||$\n",
"\n",
"If we choose $\\alpha(j,c(x)) = \\delta(j,c(x))$ then we get the regular $k$-means algorithm.\n",
"\n",
"If we choose $\\alpha(j,c(x)) = \\delta(j,c(x)) + \\beta \\left\\lfloor d(j,c(x))\\leq 1 \\right\\rfloor$,\n",
"where $d(j,c(x))$ is the distance between the closest matching $\\mu_c$ and $j$, then we\n",
"get the self-organizing map (SOM)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(gradient descent)\n",
"\n",
"In the SOM, we require each vector not just to be close to its closest center, but also\n",
"to neighboring centers.\n",
"\n",
"(You can derive the update rules from these cost functions yourself.)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"\n",
"import random as pyrandom\n",
"print data.shape"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(50000, 784)\n"
]
}
],
"prompt_number": 76
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# starting with a random sample of prototypes\n",
"protos = array(pyrandom.sample(data,100))\n",
"protos.shape = (100,784)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 77
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The prototypes have a $10\\times 10$ grid structure, but for other purposes, we just number them $0...99$.\n",
"This function converts between the two views.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"def I(i,j): return i*10+j"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 78
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"showgrid(protos,10,10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAJLCAYAAAAVYcl7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsfVlsnNd59jP7vnKGHA734b5IIrVYlivHchInAYoaTgJk\nQZEaTdoUvShQuECam7Zpb+JcFEW3iwLJhdOgadMAaQxkaRLDSyxb1mqJEkmR4iYuM8PhcPZ9+y/U\n99WZj7ORHNL5HT7AQBRn+M33fuec97zrc2SlUqmEYxzjGMc4xjGOcYxjVIX8g76BYxzjGMc4xjGO\ncYzfdBwbTMc4xjGOcYxjHOMYdXBsMB3jGMc4xjGOcYxj1MGxwXSMYxzjGMc4xjGOUQfHBtMxjnGM\nYxzjGMc4Rh0cG0zHOMYxjnGMYxzjGHWwb4Pp5z//OUZGRjA4OIhvfetbzbyn3xgcy/jhwIddxg+7\nfMCxjB8WfNhl/LDLB/x2yFgVpX0gn8+X+vv7S8vLy6VsNls6depUaWZmZj+X+o3FsYwfDnzYZfyw\ny1cqHcv4YcGHXcYPu3yl0m+HjLWwrwjT1atXMTAwgN7eXqhUKnzhC1/Aj3/842bbch8ojmX8cODD\nLuOHXT7gWMYPCz7sMn7Y5QN+O2SshX0ZTBsbG+jq6uL/d3Z2YmNjo+wzMpns/+vXU0899aGX8bdh\nHD/sMv42zNPfBhk/7PP0t0HG34Z5+tsgYy0oa75bBfUuSlCr1dBoNAAAjUbDP4uIRqMwm81Vr1Hv\n/WZdY2dnB0rl48cRi8Vqfp6gVCqhUqkAACqVin8mJJNJ6PX6mteo95lmXCMWi0GhUPD/U6lUw+Oo\nUqmgVqt3/UxIJBIwGAw1r1HvM824RjQaLZMxkUg0LKNSqeTxF8eUkEqloNPpqv59vfebdY1EIgG5\n/LGfk06na36eIK5F8WcRsVgMJpOp6jXqvd+Ma8RiMajVamSz2bLfNQJx/TV7LZb+7wQp8f1qc2uv\nazGZTO5pnpJc+5mnpVKp7mfS6fSB53I8Hj+QvhHHca/65qj0kVTfJJPJmp8nyGQyXsNyubxsPRPy\n+XzZfrTX95txjXw+D7lcjmKxyL8rFAo1v5Nw0HnayGeacY1K87QW9mUwdXR0YG1tjf+/traGzs7O\nXZ/TaDR1DZVGUKpw3F2ji6/SdSr9rVKpLLvXWCzWkIwqlaquEv5NgEKhKLvPVCrV8Diq1eq6yqMe\nSqUSSqXSvsatUSgUirL7TCQSDcuoVCrrLr5GIXoqJHezIJfLy+4znU43vBbrGTvNRDWZG3kWUufq\ng1qL4lyln8XNDmhMHimkazGZTDY8T1Uq1YHmaaOe9EGhUCjK7nMv+kalUh1Y3xwFpPommUw2JJ9c\nLq9r7OwHos5pFqQGXaFQOJJ5Wg/ieqyGRp5DpXlaC/tKyZ09exYLCwtYWVlBNpvFf/3Xf+H555/f\nz6WOFHtVFP8/yrgXHNU4NnMB7xVHPVePYjOS4jd9njZjk/6gZTzsMf1N1KnNXre/iTI2G78J8h32\nXP2gZTxq/SpiX2auUqnEv/zLv+CTn/wkCoUCvvKVr2B0dHTX5yqF/et9hqIQ9NJqtWUhM+lnS6US\nNBpNzeiFRqMpuyb9nagQKt1rIzJKQ417fV/8jHj/4r3t5Rp7eb/RcTyojDKZDGq1uswDko7VBy1j\nPY9vL+8Xi0UUi0UUCgWUSiUolcqGvMpGvM5Kn2lEPmlaoxLqfabW+6VSCXK5HFqtFnK5fJeBRPOZ\nvLlq67XadxzlWiQdQeMnfVF6SaFQVEyp/KbOU7p/uVyOfD6/630aN7pGrY1pP/dxVPrmsHRJI59p\nRL5KKbi9fqbS+5Q6o3HbzzUaef8o9Gmtz5AuUSqVdY36ZtyHCFnpkNx/mUyGjo6OA12j3q1VWtCk\n7Cr9rlgsVgyzV8LGxkZD39/S0lLzM42iVrrwMBAMBhvyIGUyGVpbWw/0XZXG4yiwtbXVsIw2m61p\n36tQKKBWq9HS0gKdTod0Oo1YLIZwOMzf16xlFwqFGpqnbre7Kd9X6dpS56Pa/ew3yrS5udmQjA6H\nY8/XrgTRmCMjgr6D/qWfyTgW6zz2iu3t7Ybnqd1u3/P1ZTIZNBoNdDodLBYLjEYjjEYjy1AoFJDJ\nZBAKhRCLxZBMJpHL5VAoFJq2Vnd2dhqW0el0NuU7jxqBQKChedpIIGGvqDROh7G1ZzKZhmTczzxt\nBKRvGp2Xe30G9ebpgRKpvb29MJvNUCgUUKlUuHr16kEux/UBhUIB+XyePbxanyXvnaxh+rz4UGUy\nGXK5HNLpNHtYarUaSqWy7oNvtoyV5CBjjjYehUJRsVZClEkqXz1Ue46HLZ/oqQNgr/woapoIhyWj\naPiIUQmj0Yi2tjZ87GMfQ3d3NxYWFjA9PY1bt25VHMNmKLbDHkcpxEgw/T+fz/OrUCiUebwUuVCr\n1VCpVHueA0exDkXjR6VSQaPRQKvVsq6gAmTySlOpFBKJBKLRKHK53C6HbK9otoyk6+RyOex2O7q6\nunDixAmMjo5iaGgIarWajSW/34+rV69iZmYGi4uLiEQiyGazrIuahaOep8DeNs1myHrUMlK0kyIu\npIdoT5F+lrBfvfNBjCHwWI+ITkwtiPtqs3Agg0kmk+GNN95omjVZLBaRy+WgUqlgtVqhVqs5RC8K\nLZPJUCgUkMvlkMlkkM1mkcvldqXz6G+KxSIsFgv6+/sBPKr+j0QiSCQSdZV2s2WsJDOlMkhp02QX\nvVaaJCSTuOE06rlV+/1hyUebJI2lXC5HPB5HNBpteNIT9hNtFN87zDGUggoJOzo6MDo6CrPZjFwu\nh9XVVcTj8bIOsGbhqGWk7plMJgONRgOj0chRDJ1Ox44MIZPJIJlMIhwOI5PJ7Eof1MNhy0c6gAwi\nm80Gh8MBl8sFh8MBvV4PnU4HjUbDczmVSsHn82FhYQEPHz7E5uZmmUOwVxyGPqVCeI/Hg6mpKZw8\neRIejwdOp5M32Hw+D7vdDoVCgY6ODoyNjcHv98Pn82FjYwM7OzvIZrNNcXCOep7Sd4r/ijgMg+Ko\nZBSDBiMjI7h48SKSySR8Ph/u3buH9fX1XTI0w3g4yjEUx0MMKjSy75Gz0EyD/8Cl+s2y3shYyGaz\n0Ov1aG9vh91uL+tcIw9OLpcjmUwiHo9je3sbOzs7yGQyKBQK/JBEZS2TyeByuXD+/HnIZDIkEgnc\nuXMHDx8+rJjLPywZK8lcKpWgVqthsVjYEIzFYtwuToNNHgTdrxiJqzd56qVCDkM+8m41Gg3a29th\ns9mgUqmwsrKCYDDIm85eushqRRvrKfOjLjyXy+UwGAxob2+Hw+FANBrF+++/j0KhgHQ6vcuobwaO\nQkZ6zmQw5fN5mM1mtLS0oK2tDW1tbXC73TCbzTzGxWIRoVAI6+vruHPnDvx+P7fSKxQKVoT1FNth\nyEd6B3hs6FqtVnR3d8Pj8WB0dBS9vb2wWq3Q6XTsxCmVSuRyOSwvL+Py5cvcPUQRmf1GUA8qozSC\nqVAoYDQaMTAwgHPnzmF0dBQ2m42NdoVCAYVCAafTCZPJhPHxcaTTaTx8+BDz8/N444032CmVRkT3\nuxEd5jyt9sxFh1N8PkB1Q+og6/Oo9A11XJ47dw5f+9rXEAgEcOvWLSSTSXi93jLHRKprD2JIHIV8\nYvADKE9/10uDk7O+3zKAajhwhOnjH/84FAoF/uRP/gR//Md/XPZ+NBrln6vxMBFog+nt7YXH48H4\n+DicTiesVisraCr+LhaLSKVS7LGGw2GEQiH2iCh6pFQqYbFY4PF4cOrUKVy4cIG9Qr/fD6/XywZH\nNptFJpPZs4wi90Yl7pdKoMWoVCrR1taG/v5+nDp1CqlUCl6vF3fv3kUgEEBLSws/M/Lgk8kke47p\ndBrxeByZTIaVGhmVYoqoWCwinU4jl8vtWT7gUXu+KGO94mBxYWo0GgwODqK/vx8GgwFKpRIrKyu7\nFFi9CJH050qeUyaT2beMYjtp
}
],
"prompt_number": 79
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's define `argmindist2` because the index calculations require some more complicated reshaping.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"from scipy.spatial.distance import cdist\n",
"\n",
"def argmindist2(x,protos):\n",
" ds = cdist(x.reshape(1,784),protos.reshape(100,784))\n",
" return argmin(ds[0])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 80
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Quick check: the closest prototype to prototype 17 should be... prototype 17.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"argmindist2(protos[17],protos)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 81,
"text": [
"17"
]
}
],
"prompt_number": 81
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The update step updates the best matching prototype and its neighbors\n",
"according to the update rule derived from gradient descent minimization\n",
"of the error, as defined above.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"def update(x,alpha,beta):\n",
" best = argmindist2(x,protos)\n",
" i,j = (best/10,best%10)\n",
" protos[I(i,j)] += alpha*(x-protos[I(i,j)])\n",
" if i>0: protos[I(i-1,j)] += beta*(x-protos[I(i-1,j)])\n",
" if j>0: protos[I(i,j-1)] += beta*(x-protos[I(i,j-1)]) \n",
" if i<9: protos[I(i+1,j)] += beta*(x-protos[I(i+1,j)])\n",
" if j<9: protos[I(i,j+1)] += beta*(x-protos[I(i,j+1)])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 82
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# updates\n",
"for iter,lalpha in enumerate(linspace(log(0.1),log(0.001),100000)):\n",
" if iter%10000==0: sys.stderr.write(\" %d\"%iter)\n",
" i = iter%len(data)\n",
" alpha = exp(lalpha)\n",
" update(data[i],alpha,0.3*alpha)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 0 10000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 20000 30000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 40000 50000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 60000 70000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 80000 90000"
]
}
],
"prompt_number": 83
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(notes on updates)\n",
"\n",
"As usual, we now perform a lot of gradient descent steps.\n",
"\n",
"The `linspace...log` bit is a convenient way of specifying learning rates:\n",
"we want the learning rate to decrease from around 0.1 to around 0.001 as we\n",
"continue training.\n",
"\n",
"The learning rate can be thought of as the length of a _moving average_,\n",
"and a value of 0.001 says that we want to average over about 1000 updates\n",
"to each prototype."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we now look at the output, we see that we get prototypes or cluster centers,\n",
"as we do with k-means, but they are arranged more logically in a grid: similar\n",
"prototypes are closer together.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"showgrid(protos,10,10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAJLCAYAAAAVYcl7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvXmMZFd1P/6pfd+7qnrvnu6eXqZn8WTGEKGvIQiMSZQg\nIyIgCzFgAkIiUWQUGZREcvJHMH8gxPYHAhRZRLJC/mCRolghkQyJBbJCbBbPeNw9vVSvtVfXvr/f\nH/M7d069flX1qupVjz2uI7W6u5b37ufdc889+9VJkiRhRCMa0YhGNKIRjWhEbUl/rwcwohGNaEQj\nGtGIRvR6p5HCNKIRjWhEIxrRiEbUhUYK04hGNKIRjWhEIxpRFxopTCMa0YhGNKIRjWhEXWikMI1o\nRCMa0YhGNKIRdaGRwjSiEY1oRCMa0YhG1IX6Vpiee+45rK6u4vz58/jiF7+o5ZheNzTCeH/Q/Y7x\nfscHjDDeL3S/Y7zf8QFvDoxtSeqD6vW6tLi4KG1vb0vValW6cuWKdOPGjX4u9bqlEcb7g+53jPc7\nPkkaYbxf6H7HeL/jk6Q3B8ZO1JeH6cUXX8TS0hLm5+dhMpnw4Q9/GD/84Q+11uXuKY0w3h90v2O8\n3/EBI4z3C93vGO93fMCbA2Mn6kthOjg4wMzMjPh/enoaBwcHLZ/R6XRv6J+3ve1t9z3GN8M83u8Y\n3wx8+mbAeL/z6ZsB45uBT98MGDuRseO7bajbRdt9Vul7kiR1vF6n9yVJgqRwsgt9nn53uwcANJvN\nls8oXVcNye+j5t7tPqNmDGoxdnpOau7Bn6n8e81mE3p9e91bkqSWzyjdl79PY+31Po1Go+U78jnt\nRDqdTlxbr9efuk+9XofR2H650Pud5qzRaKi6Rieq1WotmBqNRsfPE3F8/G/5+AwGQ9trdHtfi2vQ\nHPLn2AtGzqdyjGrH34nHms3mwM+gXq/3zadAZ5k6iLyh60mSdGotyvm6232U5GkvGOVj6uXe3fDp\n9XpIkgSTySTGSj/txq80Hv75XqmTPKVrd+ND+fuEmzA2m80WjLRf0o+ae8jXYi/74rD4lDBKkgSz\n2Sz+liQJjUbjFM5e+bQT9aUwTU1NYW9vT/y/t7eH6enpU59To7H1Q3Rdg8EAq9WKer0On8+HZrOJ\nSqWCarWKarXa8vDUXpNIkiRVGOm7WpIcX6PRgMfjAQCUSiWBkRasWiaW4+tlHjstLLV46Dr0m/7W\n6XSoVqswm81oNptoNBotC7yX+/BxNptN1Rj1en1XZUXtGOT/96t8t7s+H2ej0VCNr9tG38sYhklK\nio5aPtUC47DxycfZC59qJVPlG7Zer4fJZILJZEKlUoHNZkOj0UCtVkO9Xu9JliqNsxd5w8c3KNE4\njEYjrFYrvF4vvF4vTk5OMDMzg0qlglQqhZOTExQKBdRqtVOGV7frE6ndMwaVp+2up9fr4XA44HQ6\n4fP5kEwmce7cOZTLZWSzWWSzWeTzeTGnahQ++Tz2sha1nkODwQCTyQSr1QqXy4VSqYT5+XkYjUaU\nSiUUCgVks1mUSiWUy2XU63XU6/We8A1FYbp+/To2Njaws7ODyclJ/Mu//AueffbZfi7VN9ECGBsb\nQ6lUwvLyMmq1GrLZLDKZDE5OTlCpVFQzhhLdK4y0wG02G/x+PyqVChYWFiBJEpLJJNLpNHK5nGD8\nfjfls55Hg8EgNm6DwQCj0diykTudTtTrdVSrVYEN6N/bB5w9xl68mlrRvcB31nSv5c2w6az4lMsK\nvtGazWbY7XZYrVbkcjl4PB5UKhWUSiXhjRhU8R8GRr7elN4jjFarFX6/H/Pz85idncX29jYefPBB\npFIpbG9vQ6fToVarCU9Tv1jPmk+5QmixWDA2NoaJiQnMzs5iY2MDb33rW5HJZHBwcIDDw0M0m00U\ni8WevZqc7gVGch44HA74/X6Mj48jkUjg2rVrMBqNyGQyiMViODo6QiqVEnOo5LEehPpSmIxGI77+\n9a/jkUceQaPRwOOPP461tTVNBtSNiEHsdjv8fj/W1tZgMplw7do1VCoVHB8fY2trC9vb28Jq6NUT\nQ3SWGLnFZzAYYLPZEA6Hsbi4CJfLheXlZTSbTWxubmJnZwd7e3vI5XJCmPXD/Grnsdu11bxvNBpP\n/ZhMJpjNZpjNZjgcDlitVlSrVeTzeSGoKRyjRgFRel8txm4Wn9r3+ebCNyY1Fpcaq1PpM1rMoZrP\ncMHDXd58bFrwihKdBZ/yzxAuubFFz6DTtYbJp4MQVyC4p5esdqfTKZQmCuVUq1XNlORhYpRvihyr\n0WiE2+3G1NQULl++jOXlZayurmJsbAzb29uIx+PCaFOzR3T6zFmuRfptMBhgt9vh9XqxuLiI1dVV\nLC0tYWFhAefPn8fh4SEAoFwu4+TkBLVaTdW8DrIWtSLCZzab4fF4MD4+jsXFRZw7dw7VahUXL15E\nvV7H0dERzGaziL6USqVToW9NxiNpGS/gF9bY7civaTAYMD09jXPnzuHBBx8UzJ/P57G9vY1XXnkF\nN27cQCwWQyaTQaVSEWEetaTGytDSPc7djmazGYFAACsrK7hy5QquXbsGvV6PYrGIX/7yl7h58yY2\nNjaQSqVQKBRaQlhqqZdQ5SChKi60yIoltzEpSSS88/k8crkcTk5OhNJEHsJ+2LRer6vGaLFY+oGn\nSCaTCRaLBQ6HQ1y3UqmgWCyiUqmgVqsBGMxzRlSpVFTxqdlsHvhe/Hpk8dntdhiNRuh0OhSLRZRK\nJWGpayVaqtWqKoy0yWtFer0eFosFNpsNNpsNkiQJYVwulzXDWKvVVPNpvzKVyxi5vPF4PMJqt9ls\n0Ov1iMfjiMfjyGQyKBaLIgWgX7xqv9urTFUKp3Blgjz1CwsLWF9fx9vf/nYsLCwgGAzi1q1b+NWv\nfoVf/OIX2NjYQDQaRblc7jn8yO+vhk+1DI3TfhEMBjEzM4OrV6/i6tWrmJubg8vlQiaTwdbWFn7z\nm9/g1q1buH37NjKZjAg/9hp9oWfTbVxa7P3cO+h0OjE7O4ulpSVcvnwZCwsLmJ6eRrVaRTabxfb2\nNm7fvo3XXnsNh4eHiEajKBQKqFQqPaV3dOPTgZI25ufn4Xa7RWzxxRdfHORybYkvALKGpqencfny\nZVy9ehVLS0swmUyIxWJIpVJwu91wuVzIZrMwGo0iLt0PDRujXHgZjUY4HA6EQiFcuHABV65cwaVL\nl4Rb1WKxCO8MbVSDKG1ngY+sWIvFIgTz1NQUgsEgrFYryuUy0uk0jo6OUCqVWpKTtVBIz5JP9Xo9\nvF4vxsfHsbS0hFAohEajgePjY9y+fVtsQv16PdvRWWCkuTAajXA6nZicnMTi4iLsdjv0ej1u376N\nvb09pNNpVCoVAG8sfJxoI5qamsLU1BSmp6dRr9cRj8exu7uLw8NDkSepFQ0Lo3wN8TCOyWRCMBjE\nuXPnsLq6CpPJJPJcEolESyKtFqQ1RrlXSU6kME1NTWF1dRVra2sYGxtDs9lEoVBAMpkUCgQZWP0o\nS5zOkldJqQ8EAlhaWsL6+jouXboEt9uNRqOBTCaDarWKcrncktcLtCZP90JnJWu4Yeb1erGwsIAr\nV67g6tWrmJiYgMvlQjwex8nJicBIqRw8Af6eh+Q4qOeffx5+v1+TwXS7l8FggNPpRDgcxtraGq5d\nu4alpSWMjY0hm82iWCwik8kgn88Li4grW/3ed1gY5W5V8sKMjY1hfn4eFy9exNLSErxeL5LJJFKp\nFFKpFHK5XEvS96BjGCY+js1qtQq36tLSEmZnZ+FyuZDP53F0dIRarYZkMqkY1hp0HGfBp6QwuVwu\nTE5O4sqVKzh//jxMJhP29/cRCoXw61//GhsbGygWi8LTpNW9h4mRrx8KGU9MTODSpUsYHx+Hw+FA\nIBCAzWbDq6++ilQqpdrDp/b+ZyVrgDsYLRaLCOOsr6+j2Wzi4OAARqMRhUIBJycnKJfLbwiMSt4l\nMs6mpqawsrKCS5cutXiXTCaT
}
],
"prompt_number": 84
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's look at the frequencies of the different clusters.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"closest = array([argmindist2(x,protos) for x in data])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 85
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"counts = array([sum(closest==i) for i in range(100)])\n",
"counts = counts*1.0/amax(counts)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 86
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"imshow(counts.reshape(10,10),interpolation='nearest')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 87,
"text": [
"<matplotlib.image.AxesImage at 0x85fcb10>"
]
},
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAkUAAAJICAYAAABv4JAfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFqhJREFUeJzt3emPXgXB/+FP65So1ErElkqnRAKNXUAoixg1GonKYiAE\nGze0RnFJDAkQEv4El/gC6/JKEyJqxKhRlJC+IKhBSBUcF1CMaFotRQSXom2BtsM8L55fmsefYRjs\n3Pfp1OtKJpmbOTnnS0gnH869dNHMzMxMAAD/5RYPPQAA4EggigAAEkUAAJUoAgCoRBEAQCWKAACq\nmjjcEyxatGg+dgAAjMUzfRrRYUdR1Tve8Y75OM2c3H///Z122mlju97+/fvHdq0h/OhHPxrr9fbu\n3duxxx47tuvdcccdY7vWEH7605+O9Xrf+c53uuyyy8ZyrX/+859juc5Qrr322rFe7+mnn27x4vE9\nOXDhhReO7VpDePTRR8d6vV27drVq1aqxXW/16tVju9a4fetb33rGn3n6DAAgUQQAUC3AKFqxYsXQ\nEzgMS5YsGXoCh2Ht2rVDT+A/5PWfC9uLXvSioSf8VxBFjNUxxxwz9AQOgyhauETRwrZs2bKhJ/xX\nWHBRBAAwCqIIACBRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJIgCAShQB\nAFSiCACgEkUAAJUoAgCoRBEAQCWKAACqOUTR1q1bW7t2bWvWrOmTn/zkODYBAIzdrFE0PT3dVVdd\n1datW/v1r3/d1772tR544IFxbQMAGJtZo+gnP/lJp556ai9/+ctbsmRJ73znO7vlllvGtQ0AYGxm\njaJdu3a1evXqQ48nJyfbtWvXyEcBAIzbxGw/XLRo0ZxOcv/99x/6fsWKFa1YseLwVgEAzIPHHnus\nxx57bE7HzhpFq1ataufOnYce79y5s8nJyX877rTTTnuOEwEARm/58uUtX7780OPZXhs969Nn55xz\nTg8++GA7duxo//79ff3rX+/SSy+dv6UAAEeIWe8UTUxM9LnPfa4LLrig6enprrzyytatWzeubQAA\nYzNrFFVddNFFXXTRRePYAgAwGJ9oDQCQKAIAqEQRAEAligAAKlEEAFCJIgCAShQBAFSiCACgEkUA\nAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhEEQBAJYoAACpRBABQiSIA\ngKom5uMkP/7xj+fjNEekPXv2DD1hpF796lcPPWGkzjjjjKEnjNT09PTQE0Zm2bJlQ08YqVe96lVD\nTxipvXv3Dj1hpF72spcNPWGkHnrooaEnDMKdIgCARBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKAS\nRQAAlSgCAKhEEQBAJYoAACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJ\nIgCAShQBAFSiCACgEkUAAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhE\nEQBAJYoAACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJIgCAShQBAFSi\nCACgEkUAAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKCqifk4yUUXXTQfpzkiPfLII0NP\nGKmpqamhJ4zU1VdfPfSEkVq8+Oj9/5q3vvWtQ08Yqd27dw89YaR+9atfDT1hpE4++eShJ4zU9u3b\nh54wiKP3NyoAwHMgigAAEkUAAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgC\nAKhEEQBAJYoAACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJIgCAag5R\ntHPnzt74xje2YcOGTjvttD7zmc+MYxcAwFhNPNsBS5Ys6YYbbujMM89sz549nX322b35zW9u3bp1\n49gHADAWz3qnaOXKlZ155plVLV26tHXr1vXwww+PfBgAwDg9652i/2vHjh397Gc/67zzzvuXf37P\nPfcc+v7EE09s1apV87MOAOAw7N+/vwMHDszp2DlH0Z49e9q0aVNbtmxp6dKl//Kzc88997ktBAAY\ng2OOOaZjjjnm0OO9e/c+47FzevfZgQMHetvb3tZ73vOeLrvsssNfCABwhHnWKJqZmenKK69s/fr1\nXXPNNePYBAAwds8aRXfddVdf+cpX+v73v9/GjRvbuHFjW7duHcc2AICxedbXFL3uda/r6aefHscW\nAIDB+ERrAIBEEQBAJYoAACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJ\nIgCAShQBAFSiCACgEkUAAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVDUxHyfZu3fvfJzmiHTg\nwIGhJ4zU8uXLh54wUr/5zW+GnjBSr33ta4eeMDIHDx4cesJITU1NDT1hpD7ykY8MPWGkbrrppqEn\njNTrX//6oSeMzLe//e1n/Jk7RQAAiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJ\nIgCAShQBAFSiCACgEkUAAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhE\nEQBAJYoAACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJIgCAShQBAFSi\nCACgEkUAAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhEEQBAJYoAACpR\nBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEBVE/NxkgMHDszHaY5If/nLX4aeMFKnnnrq0BNG\nau/evUNPGKk1a9YMPWFkvve97w09YaTe9773DT1hpG644YahJ4zUpk2bhp4wUo8++ujQEwbhThEA\nQKIIAKASRQAAlSgCAKhEEQBAJYoAACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAA\nKlEEAFCJIgCAShQBAFSiCACgEkUAAJUoAgCoRBEAQCWKAAAqUQQAUM0xiqanp9u4cWOXXHLJqPcA\nAAxiTlG0ZcuW1q9f36JFi0a9BwBgEM8aRQ899FC33XZbH/zgB5uZmRnHJgCAsXvWKLr22mv71Kc+\n1eLFXn4EABy9Jmb74a233tqKFSvauHFjP/jBD57xuPvuu+/Q9ytWrOiEE06Yt4EAAP+p3bt39/jj\nj8/p2Fmj6O677+673/1ut912W08++WT/+Mc/2rx5czfddNO/HHf66af/52sBAEbkuOOO67jjjjv0\n+A9/+MMzHjvrc2If+9jH2rlzZ9u3b+/mm2/u/PPP/7cgAgA4GjynFwp59xkAcLSa9emz/+sNb3hD\nb3jDG0a5BQBgMN5SBgCQKAIAqEQRAEAligAAKlEEAFCJIgCAShQBAFSiCACgEkUAAJUoAgCoRBEA\nQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhEEQBAJYoAACpRBABQiSIAgEoUAQBUNTEf\nJ7nnnnvm4zRHpD//+c9DTxipNWvWDD1hpJYtWzb0hJG68cYbh54wMu9973uHnjBSP/zhD4eeMFLX\nXnvt0BNG6mj+s1f1ute9bugJg3CnCAAgUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhEEQBAJYoA\nACpRBABQiSIAgEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJIgCAShQBAFSiCACgEkUA\nAJUoAgCoRBEAQCWKAAAqUQQAUIkiAIBKFAEAVKIIAKASRQAAlSgCAKhEEQBAJYoAACpRBABQiSIA\ngEoUAQBUoggAoBJFAACVKAIAqEQRAEAligAAKlEEAFCJIgCAShQBAFSiCACgEkUAAJUoAgCoRBEA\nQCWKAAAqUQQAUIkiAIBKFAEA
}
],
"prompt_number": 87
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's now display the prototypes of the clusters with intensity\n",
"corresponding to the frequency of assigning characters to that cluster."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"grid = vstack([hstack([protos.reshape(10,10,28,28)[i,j] for j in range(10)]) for i in range(10)])\n",
"scale = vstack([hstack([counts[I(i,j)]*ones((28,28)) for j in range(10)]) for i in range(10)])\n",
"imshow(scale*grid)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 88,
"text": [
"<matplotlib.image.AxesImage at 0x738f750>"
]
},
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAlIAAAJLCAYAAAAsBnggAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvTuTNMlVPn56+t4z8767q8tqdfmFFCAkfPAxUOARyAEi\nMDAIgm8AgYUrfL6ALAV4YBEEBhgY6BsQBAKtWEnLXt/L9L2n/8b+n5qnnzmZVdVdl6zZeiI6eqa7\nuipPZeY5z7lk1uB4PB6tR48ePXr06NGjR2lctd2AHj169OjRo0ePrqInUj169OjRo0ePHmeiJ1I9\nevTo0aNHjx5noidSPXr06NGjR48eZ6InUj169OjRo0ePHmeiJ1I9evTo0aNHjx5nohYi9Y//+I/2\n3e9+17797W/bX//1X9dxiR49evTo0aNHj9YxqHofqcPhYN/5znfsn//5n+1rX/ua/eZv/qb96Ec/\nsl//9V+v8jI9evTo0aNHjx6to/KI1I9//GP71V/9VfvmN79p4/HY/vAP/9D+/u//vurL9OjRo0eP\nHj16tI5R1Sd877337Bvf+Eb2/9e//nX793//95NjBoNB1Zft0aNHjx49evSoDaEEXuVEqihJGgwG\n2bGDwcCurvq697ZwOBxsOBy23Ywe/z/6/kgLfX+kgzr6gu0QoAazq09SKxu0KCtn23OD5VNZPVnK\nyHd/f39y/P39ffDYyonU1772NfvZz36W/f+zn/3Mvv71rz86bjAYNNYBuMEga/j/eDxmL/zfRYCU\nskJ4KrIBRSZJl/DU5OnRo0uAvry6uspebBfu7++z1/F4zHRqV6BBCrURkEvtRFfA8nh9CPm4D8v2\nowZ3GiVSv/Ebv2H/+Z//af/zP/9jX/3qV+1v//Zv7Uc/+lHVlykEHUyj0Si74XyTD4fDyU3qyqBi\nggj5MLhYrq7IFvOe8jyrrskVkidlOfJQxPvtsnxAL+cDUpKzqJFk4zsej7PXcDjM7MJ2u7Xdbmf7\n/d4Oh0NnyBTbPAQrhsOhjUYjGw6HmQyHw8EOh0Mmn1k7fcnktchxAPoPso3H40xGM8tk4z6ELayj\nHysnUqPRyP7mb/7Gfud3fscOh4P9yZ/8ibtir6k6KUya8Xhs0+k0u+HH4zG70dvtNhtYdd3oqsEk\najgc2mQysclkYsPh0K6urjLZMJA4TKmypVCzFmqDF3YHWI4u9BlDvUBVgF1Gl/qhCLz0QYpzqEqk\nKs+l7eIoxng8ttlsZrPZzCaTiY3H40xvmtlJVMqsO+PaI4qTySRztO/v7zO7Bz10buSt6XHCBHE0\nGtlkMrHpdJrZdpBhyKfZJ8hXtb2ofPuDQhcdDGw8Htd6fgA3fD6f283Njc1mM5tOp3Y8Hm29Xtt6\nvbblcmmbzcZ2u12SEydGMjCY5vO5XV9f23g8tsFgYLvdzlarla3Xa9tsNhmZSk02s8fyeYbLS4V5\nIemU5PIQSrdyWDpWq9EFeP0SI8RdASvfp0Sk8tre9doh1ScgGJPJxG5ubuz6+tqm06mNRqPMJtzd\n3dlqtbLtdmv7/T75FBjLCOcawQO8RqPP4ib7/d42m41tNhvbbrdZICHlUhBO5bFs8/ncFouFzefz\njFPc399n/QgbiH68RM7dbtdcsXlKwE2fzWa2WCzs9vbWFouFTSYTOxwOWYqPQ39dCeHC8MKrur6+\ntpubm2wwrdfrk/Cm1k+lIqNHoryaL8CL5HQhMgUZRqPRiScFwIPSyZ6qPCGwtzgej7NxqiH2Lslk\n9pgIwvtFf0IuyJmy0WWUIVH4vwtyAV77UQYBu7BYLLKxyrqyS3ICLN9kMjmJuF1dXWWO9G63O6kZ\n7kq/QrbpdGqLxcJubm5ssVjYbDaz4XB4MgeRnfHqh6tGJ4hU0cJc9TyQ8gKJevbsmc1ms2zC7Ha7\nLK+K/DEPqrYnVF6kBvKBRN3c3Jyk9ZSUpEY6QiSKiwfxOXuEKUbVYuD7v1gs7NmzZ/alL33Jvvzl\nL2fK7aOPPrIPPvjAXr16Za9fv87IFH6fsqzcj0glvPHGG/bGG29k8+vFixf26aefZh4ikLJcgBfR\n4Dm3WCxstVrZarWyly9fZv3XldrEELw0cxflAFi/gGTM53Obz+c2GAyyPtvv949If6py69jUiBuI\nFHQpF193QY96kTa26Tc3Nzafz7NoG6JGulggL5J86T3oBJE6B5wDv7m5sdvbW7u+vrbRaJSxVi+6\nUTdzvRRoH8KbiEYtFgubTqeZbJrfTx1aI4RJwwTQmxipQxXdfD63t956y/7f//t/9iu/8is2mUxs\nMBjYz3/+c3v33Xft5z//eRZ651By6uMRGA6HNp1O7a233rKvfe1rmSJ///33bTwe2yeffHIyPlOV\nC1D5MC5vbm7si1/8on3hC1+wN9980169emUvX760q6urrFB5u9221OrLoVFhs7QNblFwRGM+n9ts\nNstqo7hmliPDXYHWDiESBZLBi6u4+Dp1fcopPZSxwIm5vr62yWRiZnZSQI++bIoMd4JIla3oR+3Q\ndDq16+tre/bsmd3e3mapFJ4wXjF20yji9SnRYGVwfX2dhTb3+71tt9ss/x1LpaQyeTwSpUtaOULY\nNDk819h73uJsNrPnz5/bV7/6Vfv2t7+djcu3337b3njjDZtMJrZcLu3FixdZiihVeGkhKLvnz5/b\nO++8Y8+fP7fnz59nToyZ2atXrzIyhfOkKKcnHxT69fW1ffGLX7R33nnHvvKVr9jLly/txYsXdjgc\n7PXr13Z3dxetqUgBRdJ6oWNSlisE9B3SQjDCg8HA9vt9VlfDNaWpkwyA7QJHopCCZpLBi5BCZLGu\nbMy5EU4EDkCiEI1CyhKybbfbrB9h3zU67F3/0shrJ4hUGfBqBeRQmWiAQG02m5NJo0VoKYKJBnL8\n8Kp4JSIKCXWypCRbXm0Uv1DLZmZZFCOU109FxpARhjJ4/vy5ffGLX7Q33njDFotFls9/9eqV/fKX\nv8wWC6TWb0DIwCJiM5vN7Pb21t566y176623MgX34sULm0wmWQqFz5eSnCH5YIzn87k9e/bM3nzz\nTXvrrbey1cAffvihzWYz2263tlqtkpMLKFMbxY5MirLEgHZ7KT2kvLDdAeyBV3ydMjhigyzFdDrN\nVnEfj8cTooGIW+pkUeXiSBQyMCCJu93upLgc/aj2ry45n9R24szKociRQ0UhGhTccrm01WqVEQ4N\nAbZdO6SKjP+GQsBqBXhVu93uZDUGR9s8Rh7zOOtE7JoekSr627r6rOh5Q21mgOSjSBk1RDc3N/b2\n22/b22+/bV/60pfs9vY2W67sXadN5F2f93hhJYjIFIh/23KEkNd/nGJA6oRTRanLlweOED8VwCCj\nFALRmuPxmOlNb3UXIyWyoXqGU5ZI6fGeSgggMJGK1Q+Fyl4utRlFbasXNEB26dmzZ1ldFEpZYNPx\n4r7kFKbKWRS5Oq/0GROFprwQusWKDDNzSRRPnJRXE+nA4hx4yKvSQdQ2QYQcof+LTtC2COAl0Agb\nSAZSl7PZzJ49e2ZvvPGGvfnmm3Z9fX3yPZ+H31MFe5OcTlEln5ocRdrDeoZJMQrtsfFv2fOmAB1f\nZSJXKQPkF9EoTglxSg9OtRrdtvVmCJ5NwLhEJF+JlEajzNKSj8cel+hocTlIMLYwwpYVmo1pwv49\nqdQeR6NApKbTaRatwQ0HkcKkCd3spgZXaCWBB0Sj4HmwV6UKIbVdzUMkKhR54jy9ekeh87cto4dY\nGowJB8gGPK7xeJyN0dh5UgPXPml4XncgTglFSRTkgRzeIyryzt92xDv2eVmynvq84w2ZEcVHNINr\nalDmkYrTmQcei0yiQBI9EuVlKcrUSOWtmC96z/LOw3Jhhd7t7e3JCj3Utd3d3dnd3d1JJEqL6cu0\n7Rx0PiIVuvHwfnnCYImyhnBTzhMzQBR5N1fkiDkalVqqMoZzo0t5xqBplL2ukkjdHwV9q/ugpI7Q\neIN8/KiKlGTKawvLxI+mUELI
}
],
"prompt_number": 88
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Try to come up with good visualizations like this when presenting your own research results.\n",
"\n",
"Note that only about 1/3 of all clusters are actually strongly used. This means that in order to get the same quantization you get with $k$-means, you'd need to choose about three times as many cluster centers."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Homework:** apply this to text files to obtain topic maps."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Toroidal Updates\n",
"================"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The previous construction causes somewhat distorted maps because\n",
"prototypes near the edges of the map have fewer neighbors that those\n",
"in the center; this causes \"difficult\" cases to be moved to the edge.\n",
"Often we don't want this, and we define neighborhood somewhat differently."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For the following, note how the `mod` function works in Python:\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"-1%10"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 89,
"text": [
"9"
]
}
],
"prompt_number": 89
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our updates now are \"circular\", they wrap around at the edges.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"def I(i,j): \n",
" return (i%10)*10+(j%10)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 90
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Otherwise, the update rule remains the same.\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def update(x,alpha,beta):\n",
" best = argmindist2(x,protos)\n",
" i,j = (best/10,best%10)\n",
" protos[I(i,j)] += alpha*(x-protos[I(i,j)])\n",
" protos[I(i-1,j)] += beta*(x-protos[I(i-1,j)])\n",
" protos[I(i,j-1)] += beta*(x-protos[I(i,j-1)]) \n",
" protos[I(i+1,j)] += beta*(x-protos[I(i+1,j)])\n",
" protos[I(i,j+1)] += beta*(x-protos[I(i,j+1)])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 91
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"# random initialization\n",
"protos = array(pyrandom.sample(data,100))\n",
"protos.shape = (100,784)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 92
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# random prototypes\n",
"showgrid(protos,10,10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAJLCAYAAAAVYcl7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvVeMpOlVPv5UzrErdlXnnCfuzi54gyMgsbZlyQYhY2GD\nERdIyEjYN8Qbry8QQsAFEr5YhIR+vrEwQiDWktfaMGEn90xP51hVXbm6unL+Xwzn7FvfVHdXd1eP\n97/uI7W2d7rq+77zvec974nPkTUajQbO6ZzO6ZzO6ZzO6ZzO6UCS/6If4JzO6ZzO6ZzO6ZzO6eNO\n5wbTOZ3TOZ3TOZ3TOZ3TEXRuMJ3TOZ3TOZ3TOZ3TOR1B5wbTOZ3TOZ3TOZ3TOZ3TEXRuMJ3TOZ3T\nOZ3TOZ3TOR1B5wbTOZ3TOZ3TOZ3TOZ3TEXRig+l//ud/MD4+jpGREfzgBz/o5DN9bOicx08GfdJ5\n/KTzB5zz+EmhTzqPn3T+gF8OHg+kxgmoWq02hoaGGhsbG41yudyYm5trLCwsnORSH1s65/GTQZ90\nHj/p/DUa5zx+UuiTzuMnnb9G45eDx8PoRBGmW7duYXh4GP39/VCpVPit3/ot/Md//EenbblfKJ3z\n+MmgTzqPn3T+gHMePyn0Sefxk84f8MvB42F0IoMpGAyip6eH/9/v9yMYDDZ9RiaT/f/65+WXX/7E\n8/jLsI6fdB5/GeT0l4HHT7qc/jLw+Msgp78MPB5GykP/egAddVEilUoFlUrFv6vV6mc+k8vlYDAY\nDrxGPp8/9O/SazRaTHo56h4AsL+/D4VC0XTfdkjkqxWP7dz7qM904hpS/nK5XNvrqNFooNFonvld\nvLbZbG76N1EA5XI5UqkULBYLGo1G0xrV63UAQCaTeeYarXg47DPJZBJKpbLp8yeVVfqdKJ/PQ6/X\nH/h96d9lMtkzsijKcis5PeoewNP3dBZyChxPDun5pe/3tLKcy+WgUqlQqVSa/q0dUigUvP5KpbJJ\nFgCgWCxCq9Ueeo2jPtOJa+TzecjlH/mqpVKpbTlVKpUsm+LvRIVCATqd7tBrHPWZTlwjm802yWmh\nUOjYudGujMnl8qZDUNQ92WwWer2+aR+Kz3eWZ4a4bq10DV3rOPrmJJ9p5+/SvVgoFA69J5FareZ1\nE38nymazMBqNh15D+hmpzsxmszCZTMe6hpTS6XTTGmaz2UOvdyKDyefzYWdnh/9/Z2cHfr//mc+p\nVKojhe4okh6wR32m0Wi0vTFFUigUTc+az+fb4lGtVp+aR5EOevZWB/BxSMpfLpdrex01Gs2RxoyU\n6vU6arUaqtUqGo0GyuUyisVikxIjY+ooapd3pVLZ9Jz7+/vHktWjFNBx6CA5bMXHceRVoVA0Pecv\nQk6l3lg7e/Q4JFWwuVyuLR6VSuWRxszHgeRyedNzlkqlY8npUcbMx4EUCkXTcxYKhTM9N8T9Rv+t\nVCqo1Wqo1Wr8OdI59Xr9xGcF0UnPjE7rGimJe/GgfXkS4xV4uo7t6pujDKLjEp0dwEfr3YlzUXzO\nowymE6Xkrly5gpWVFWxubqJcLuP//b//hzfeeOMkl+o4nWYDSOnjxmMneQPOZh1FQ0ihUECtVkOl\nUkEulzf9tOKl0/wBv1hZbWcjS3k+yTv4RfAnKq7nQR+3vdhp+jjr1E7R8+aRDlWK6FC0SqVSsY46\nSBedlD4uaygaj8dNOx1FHwcez+KsaIdOFGFSKpX4x3/8R3zhC19ArVbDt771LUxMTDzzuVahxqM+\nI11orVb7TGhdSlqtlsNq0mjTSZ8DQEd4bPfehx08R/39pM/R7jpKU3CH/b3RaEClUkGr1aK3txc+\nnw96vR5ra2uoVqvI5/OoVCrIZDLI5XIcxlYqlajX602bWho1PM5zHJfH06yjTCZjJSxSvV5nnuRy\nOTQaDeRyeRNf4rqedJ3Pai+KJJPJOOpDXjulUyn9RWtEPLbi5aTvuR0ej9ITR/39F3mNduX0l4HH\n48hIq9Qw6Q6LxQK/34+enh6WyUqlgnQ6jc3NTQBgHVSv16FWqyGTyVCv13+hZ0Y7n6G/i5EWoPk9\naDSapnSTlFql5dt5hnZ4POraR/2dPkNrSWtXq9WaeK5Wq6fisZ3nEEnWOCMXUSaTwel0nuoaxwn1\nH+SpnzRkF4vFjvyeTCaDy+U69rUPu1471Ikli0ajbUdAWoVcW30OeGokGI1GOBwOvPTSS7h06RLM\nZjPS6TQWFhawv7+PUqmEeDyOZDKJ/f195PN5FItFfh4Kobeb0jqIAoFA2zw6HI62r3sYNRoNKJXK\nprQSGYmt0gbS7x6X4vH4mctpqz1E3rlCoUCj0WADiowo+l4nqB1ZlclksFgsHbnf86Z0Ot22nNrt\n9ufwRJ2nZDLZNo/HOTfEPSVGlKxWK/x+P6ampjA9Pc0GXLlcRiwWw87ODuLxOBKJBGKxGDKZDIrF\nYpP8HpfaPTO6urpOfA/xOsBHOkP636O+K02pt0uJRKItHj0eT9vXPIxoTUnXUESw0Whw2cdp1kxK\n4XD4UP5OFGEi6u/vh9lshkKhgEqlwq1bt058LXHxyIOtVCqoVqucb271eSLxhSqVSigUCigUiqbP\nneRA6iSPBxEJRCshlj4/CUen7Nyz4E+n08HtdmNmZgavvPIKdDod9vf34XK5UCgUUKvVEA6HEY/H\nkc/nsb29jcXFRRQKBZRKJZTLZdRqNfYwRC/j48IjAPZGRWVVrVah1Wphs9ng8Xggl8uxtraGRCLB\nBc0qlapp89N3xf9+nHgkPuv1OhQKBbRaLaxWK4xGI/R6PZLJJK9luVyGTCZrKsA+bZ0B8Hz2oZQO\nMvjOKg35i+CxXTpt7R1Rp3kUn6Fer0OpVMLj8WB4eBjT09OYnp7G5OQkNBoNR7FTqRSCwSDi8Tgi\nkQg2NzexsrKChYUF1Gq1pgjpx4FHKYm1n+J5KZ6V9N9W60bPpVar26ohldLzkFOqMyuXy1Cr1dBo\nNPB4PLBarVAqlSiXy8hms0gkEtjb22uK5ANnt0dPZTDJZDK88847p/Z6SCFTasNkMsFgMMBoNMJo\nNHJoURRi0aCgcB0VFufzef4pl8unenmd4vGgawPgouhWhqH083TItjpsT/oMneRPLpfDbrdjYmIC\nbrebUzV6vR69vb0cUnW73cjlciiXy9jZ2YHD4UAul0Mmk0EkEkEymUQ6nebP07OehNezWEOKImm1\nWk4FkgLp7+/HyMgIrFYrAGBoaAiRSATxeBzZbBbZbJYjbdI05EnprOSUlC+l5Lq6uuDxeDA4OAi/\n3w+v14tAIIC1tTVsbGwgFouhXq+jWq2iWq2yIj9ttOks9+FB9Lzqs4h+ETy2S61k9CRG/lnwSEaD\n1WqFy+XC+Pg4JiYmMDU1BZvNhnw+j729PZTLZRQKBZZLp9MJp9OJ7u5uOBwOyGQyBAKBtqNhz5NH\nMapC56BcLufzUqPRQKVScXqcfpcalNVqFalUCplMhg2sjwN/UqLn0ul06O7uxuDgIIaHh+Hz+aDT\n6VAsFpFMJrGwsIDl5WUkEgnk8/kz37OnMpiA0ykVWnQSBplMxtGJ3t5eDAwMoK+vD1arFTqdrilV\nI3q8tVoN2WwWyWQSsVgMwWAQoVAIu7u7SKVSTXnPkzzvWSyCmJqp1+scTaPDpZUxRBuE6mVOGz3r\nxHcBNK2fXC5HV1cXpqenYbFYON2mVCrR1dXFHoDH42EF0N/fj97eXuzv7yOVSmF9fR3Ly8tYWlpC\nLpdjr+801Mk1lMvl0Ol0sFgscDgcsFqtaDQa0Gq1sFgsuHTpEl544QXI5XJUKhWkUilEIhEEg0Fs\nbGxgfX0dGxsbSCQSqFQqTSHn00RjOi2nJJsU7dPpdOjp6cHU1BQuX76MqakpjI2NYX19HQ8ePMDN\nmzexsrKCUqmEbDaLdDqNXC6HarXaked5HgYM7avDCoJJbg/z4k9KZ8ljuxGTVtF8qZMG4EgHr93r\nn4ToGnK5nI1yh8OBqakpXLhw
}
],
"prompt_number": 93
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# iterative SOM updates\n",
"for iter,lalpha in enumerate(linspace(log(0.1),log(0.001),100000)):\n",
" if iter%10000==0: sys.stderr.write(\" %d\"%iter)\n",
" i = iter%len(data)\n",
" alpha = exp(lalpha)\n",
" update(data[i],alpha,0.3*alpha)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 0 10000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 20000 30000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 40000 50000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 60000 70000"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
" 80000 90000"
]
}
],
"prompt_number": 94
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# SOM output with toroidal updates\n",
"showgrid(protos,10,10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAJLCAYAAAAVYcl7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsfVtspGd9/jNnz4znfPD4bK93N7s5L0RQtSQFQUiQCgoC\nAaWlAcJBSLSqgipAbUXaixIuEOJ0Uf3hIqUSEr2gIFWNoBeBNgqNWpJCSLLZg70+jccej+fo8djj\n+f4Xy/Pub15/c56xl838pJF37Zlvvud7T8/7/A6vxTAMA0Mb2tCGNrShDW1oQ2to1pO+gaENbWhD\nG9rQhja0m92GhGloQxva0IY2tKENrYUNCdPQhja0oQ1taEMbWgsbEqahDW1oQxva0IY2tBY2JExD\nG9rQhja0oQ1taC1sSJiGNrShDW1oQxva0FpY14Tp6aefxrlz53DmzBl85Stf6ec93TQ2xHhr2K2O\n8VbHBwwx3ip2q2O81fEBrw+MDc3owqrVqrGwsGAsLi4a+/v7xj333GO8/PLL3VzqprUhxlvDbnWM\ntzo+wxhivFXsVsd4q+MzjNcHxmbWlcL0/PPP4/Tp05ibm4PD4cCHPvQh/OhHP+o3lztRG2K8NexW\nx3ir4wOGGG8Vu9Ux3ur4gNcHxmbWFWFaW1vD9PS0+v/U1BTW1tbq3mOxWH6nX7//+79/y2N8PbTj\nrY7x9dBPXw8Yb/V++nrA+Hrop68HjM3M3vSvDazVRY/LeB+GYdTdkzE87aUtu1nacZA2CIyy33Xy\nXbKfnnQfNbtXfRx1+vd+XOOkn8tJ2XAstv+5m6Gf8j39sOFY7MxIbAzDgNV6XfPhveo/+21dEabJ\nyUmsrKyo/6+srGBqaqpvN6WbZH9WqxVWq1X9GwAODg7gcDhgGAYMw0CtVkOtVlP/7vbhHSdGGjvC\ncdhxtGMjUsvfDdoGiVHHIwcyTcc4CMzt4uvXojzodjPrJycxFo/TjntOPQnrBOPvCoHUN+q3Mj7g\n5MYi13ubzQaHwwGHw4GDgwN4PB4YhoH9/X0cHBygWq3Wrf99t24Cnw4ODoxTp04Zi4uLRqVSMQ38\nAtC3l9VqNex2u+FyuQyv12sEAgEjHA4b0WjUiMVihsfjMWKxmBEOh41AIGCMjo4aIyMjhsPhMGw2\nmwHAsFgsHX/vcWLkPXZzn92+BtmOxGK1Wg2r1WpYLBbDZrMZdrvdcDgcht1uN+x2u2Gz2dTfB4F/\nEBglLuKx2WyG2+02vF6vMTo6ql5er9fweDzGyMiIwk+8/cLYLj75jM1e+nuI0Wq1GjabzbBYLKrd\niJsvtqXe5q2+o52/n8RYPO7Xcc+pNzvGTvtIJ38f1DUGORZPAuPNMha5drhcLsPv9xuJRMKYn583\nYrGYce7cOeP06dPGxMSEEQqFDLfbbTgcjp7m2GbWlcJkt9vxrW99Cw899BAODw/x2GOP4fz5891c\nqqlZfrtjt9vtsNvtilk6nU7Y7XbYbDb1d5fLhWq1ioODAxwcHKhrGG1Il43sODDSiNXMWmEwumTS\ng2hHi4kaaLPZYBgGnE6n+h2tVqvh8PAQ+/v7MAwDh4eHaofQD+snRrYBMcndjsViQSAQgNvthsvl\ngtPpVO8/ODhAuVzG9vY2arUadnd3UalUUK1Wm6pR7Vo/21C2n1kbjoyMwGazwW63q/ewvYjTMAxU\nq1UcHh72bZc3qLFoNq74O4umHgDX+6tlACrwcc2pJ2mvB4wnia/bda5TO+51kfOPy+XC6OgogsEg\nvF4vfD4fPB4PyuUyDg8PcXBwULe2DOR+jH6PfF64x8azaBKc0+nEyMgIXC4XRkZG4HA4YLPZAFyf\nxEiW9vf3UalUUKlUFHniIkyo7UJu9b5eMMpJWZIlTsZmC6n+Gfl3ia1dnO08h04w6gusTnIl0WXH\nlm3HdqO8ygXXDE+/2rAdjPpzJ0F3uVzwer0YHR1FIBBAIBBAMBjE6OgovF6vIhWVSgXFYhG5XA5b\nW1tIp9PY2dlBoVBApVJR/bMTXJ1gbEbGzd6ntx/HntvthsfjUaTQ4XDAbrcr0lsul1EqlZDP51Es\nFrG7u6vaUu/TneLr91jUSRFxyz4sxybvQSf1nYy3ZtbvsXgzWrsYf1dxtttPB4GvGclv9P9ubBBj\nsdl1ON86HA41v0ajUXg8HjidTpRKJRQKBWSzWeRyORSLReWa63bOafaZrhQm2tzcHPx+vyI1zz//\nfC+XA1Df8Jy0XS6Xmqw9Ho9ajKxWKw4PD+sWXH5eTnC8nvHbmCb+/SQxmk3Q8j71l/ysPqHzPVy4\nOiGH/cInMdntdrXI8sW2o/pCdZCEaX9/H7u7u2oAlMtl7O3t1SkV+vM4jjaUg5+D1+l0wuv1wu/3\nIxKJIBaLIZFIIJFIYGxsDMFgEIFAAC6XC1arFQcHBygUCtjZ2cHy8jKWlpawuLiI9fV1bG9vY29v\nT5GKZhPeoDASm1n7eTwetasLh8MIh8MIBoPw+/3weDwYGRkBAFSrVRQKBWQyGSSTSWxsbCCZTCKX\ny6FQKODw8LAnxamf/VT+5FiSJJGkXqrYAOqUNBkzIXH1sigNYq652exmw9jteGtmx42x0aZbroXS\nesV5HPgkJrvdjpGREQQCAcRiMUSjUbhcLgBQGzX9GQzKeiJMFosFzzzzDMLhcF9uRoK22WxwOp1K\nhvP5fAgEAmqHC0AFe+3v7yvVQioXvKbNZlNEQt8d8jrHgdFsBy8naDPy04gw0SVkt9sVBqmycSLX\nd8GDwKcvtlxofT6faje/368kVI/HowgvACWn7u7uolgsYmdnBzs7O8hmsyiVSiiXy6hWqwqTXHzb\nIcD9wsgJwuPxIBQKIR6PY3JyEpOTk5iamsL4+Dji8Th8Ph+8Xi8cDoci9Xt7e9jd3UUikcDExAQi\nkQguX76MK1euYHt7G7lc7gjZ7fT+usUoSTjbz+v1IhAIIBwOIxKJYGxsDGNjY4hGowiFQhgdHYXb\n7YbT6QQA5Wqkira6uoqlpSWsrKxgbW0NxWJREeBudn79akP+ZHtKtypVQ6qhVLGpZFNdoopNUk/C\nS9LbrVrY7/m0k+81s0E4H04KYyP7Xceou8/5O7mOAO0pQ5185yDx6aEPHo8H4XAY4+PjGBsbQyAQ\nAADs7e2pdV+u/4MkTT0RJqB/HU4nS1SWvF5v3e6WUly1WkWlUjmi0litVtVR+HuqUPJnJ0pMPzDq\nZIlkUE7QwI1dLJUXfQHVr8G4IJLHcrmMcrmsXFvt7Ox7wacrgk6nEx6PB36/H+FwGNFoFNFoFJFI\nRCkTo6Ojyp3DwV2tVrG3t4disYh0Oq0Uiu3tbWSzWbU46Tt7ef+DxMjn7nQ6MTo6ikgkgsnJSZw6\ndQpzc3OYmZlBIpFAKBRSLmMzd04ikcD09DTC4TBGR0fVhCbdyHp7t3v/3RItSZaonoVCIYyNjWFi\nYgKTk5OYnp7G5OQkwuGwitWSpBeAUnnz+TxWV1cRj8fh9XpRq9Wwubmp+nK3SlO/+qmcY5xOJ9xu\nN9xuN7xer/o3xyYJE9uRhIl9tVAoIJ/Pq11utVqtu9dO73lAERKm1uuOvBcX63GarhI3upd+3tdx\nYNTXTJIGKvf6q5/3NSh8uvLrcDjg8/nU5jSRSMDlcqFSqaBWq9WpwTLcYxDKIdAHhekd73gHbDYb\nPv3pT+OTn/xk19cxU5bos4zH44jFYggGg4pYkF1KBYkKCx8cF1iqE2ZB4a06Uj8wygWXMSFer1e5\nF7lTN3PHyWvwJzuE3P1SxaBLq1gsAoAKpm60w+gFn74T4OJD6XRiYgLj4+NIJBKIRqMIBALwer0q\ncJj3DtxQyPb395HP57G1tYX19XWsr68jmUxiZ2cHuVxOKU7c1RN7K4WpG4xy0JFQkMQHAgFEo1HE\n43HlhhsZGVFKCwkv741Bi3a7HdFoFIZhKDJvtVpRqVSQzWZVu5Hwd9IWzTDqz0dfRHh/brdbkaWZ\nmRnMzc1hfn4eiUQC8Xj8iKok
}
],
"prompt_number": 95
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note how shapes at the right edge of the map are now similar to shapes\n",
"in the same row at the left edge, and the same works for top and bottom too.\n",
"This is a toroidal mapping, and it doesn't have any edges.\n",
"\n",
"It is called _toroidal_ because the map is topologically equivalent to the\n",
"surface of a torus."
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 95
}
],
"metadata": {}
}
]
}