mirror of
https://github.com/saymrwulf/nvidia-AI.summerschool17-notebooks.git
synced 2026-11-20 09:52:58 +00:00
312 lines
249 KiB
Text
312 lines
249 KiB
Text
|
|
{
|
||
|
|
"metadata": {
|
||
|
|
"name": "19-mlp-background"
|
||
|
|
},
|
||
|
|
"nbformat": 3,
|
||
|
|
"nbformat_minor": 0,
|
||
|
|
"worksheets": [
|
||
|
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Title: MLP Background\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": [
|
||
|
|
"Multilayer Perceptrons"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(multi-layer networks)\n",
|
||
|
|
"\n",
|
||
|
|
"So far...\n",
|
||
|
|
"\n",
|
||
|
|
"- individual neurons can implement logic gates\n",
|
||
|
|
"- we can group together neurons in layers\n",
|
||
|
|
"- each layer consists of gates that compute in parallel\n",
|
||
|
|
"- can perform arbitrary computations with single layer recurrent networks\n",
|
||
|
|
"- can perform linear classification (perceptron learning, logistic regression)\n",
|
||
|
|
"\n",
|
||
|
|
"Disadvantages of recurrent networks:\n",
|
||
|
|
"\n",
|
||
|
|
"- potentially unbounded latency\n",
|
||
|
|
"- hard to program\n",
|
||
|
|
"- hard to apply machine learning to"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(multi-layer networks)\n",
|
||
|
|
"\n",
|
||
|
|
"Solution:\n",
|
||
|
|
"\n",
|
||
|
|
"- stack multiple perceptron layers on top of each other\n",
|
||
|
|
"\n",
|
||
|
|
"What boolean functions can we compute with a fixed number of layers and polynomial units? \n",
|
||
|
|
"\n",
|
||
|
|
"- circuit complexity\n",
|
||
|
|
"- common complexity class of log-depth, polynomial-sized circuits\n",
|
||
|
|
"\n",
|
||
|
|
"What decision regions can we compute with a fixed number of layers and polynomial units? \n",
|
||
|
|
"\n",
|
||
|
|
"- machine learning"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(circuit complexity in TOC)\n",
|
||
|
|
"\n",
|
||
|
|
"- layers of gates (AND/OR/NOT/NAND...)\n",
|
||
|
|
"- each layer operates fully parallel\n",
|
||
|
|
"- complexity is given by depth (=delay), number of gates, and fan-in/fan-out\n",
|
||
|
|
"- for each input size $N$, we construct a circuit sufficient for solving problems of size $N$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(complexity of the parity function)\n",
|
||
|
|
"\n",
|
||
|
|
"$\\pi\\not\\in AC^0$\n",
|
||
|
|
"\n",
|
||
|
|
"$AC^0$ = polynomial size, unlimited fan-in, AND+OR, depth $O(1)$, NOT gates at input\n",
|
||
|
|
"\n",
|
||
|
|
"$\\pi\\in NC^1$\n",
|
||
|
|
"\n",
|
||
|
|
"$NC^1$ = polynomial size, polylogarithmic depth, AND/OR/NOT gates"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(what happens in real neural networks?)\n",
|
||
|
|
"\n",
|
||
|
|
"- fixed latency in many computational tasks $\\rightarrow$ feed forward operations\n",
|
||
|
|
"\n",
|
||
|
|
"- variable latency in many $\\rightarrow$ recurrent operations\n",
|
||
|
|
"\n",
|
||
|
|
"What can we do with feed-forward networks?"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Linearly Nonseparable Problem)\n",
|
||
|
|
"\n",
|
||
|
|
"Many problems are not linearly separable. These cannot be solved with a single layer of perceptrons. To solve these, we need _multi-layer perceptrons_.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"xs = rand(1000,2)\n",
|
||
|
|
"ys = 1*((xs[:,0]>0.3)!=(xs[:,1]>0.4))\n",
|
||
|
|
"plot(xs[ys==0,0],xs[ys==0,1],'b.')\n",
|
||
|
|
"plot(xs[ys==1,0],xs[ys==1,1],'r.')"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 290,
|
||
|
|
"text": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x10638110>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD9CAYAAABHnDf0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztfX2MVtW19xoF73UKMgMDgvPMhWFGpvI1kECoGstQbSho\nlKQlwf4xo5VnGiNt9Y/7XtOmGdomA2n/aExrMiXxeiN2kiImF5MyxrQONApKrxrsFVPQO2OAG31R\nnimN5oWhrveP45k5c+acffbH2l/Ps3/JRMY55+y1117rt9f+WrsOERECAgICAqoK19gWICAgICCA\nHoHcAwICAqoQgdwDAgICqhCB3AMCAgKqEIHcAwICAqoQgdwDAgICqhCF5P6d73wHbrzxRli1alXu\nM9///vfh5ptvhs7OTnjrrbdIBQwICAgIEEchuT/44IPw4osv5v798OHD8N5778GZM2dg37598PDD\nD5MKGBAQEBAgjkJyv+OOO6CxsTH37y+88AL09PQAAMCGDRtgbGwMPvroIzoJAwICAgKEoTznfv78\neWhpaZn4vVQqwblz51Q/GxAQEBCggBkUH0lnMKirq5v2TNb/CwgICAgohkyWGOXIvbm5Gc6ePTvx\n+7lz56C5uTnzWUTM/9myBRAAcP16wEqF/aznP319ffLvb9wY6QkAcPt2q/UolxE2bkTYsgWhUpn6\nty1bIinXr5/+NzJdEPxs3DihTdi+3WO7MFA3VnuLtn2RbJS64JXb1R9ZKJP7vffeC8888wwAALz2\n2mvQ0NAAN954o/iHBgcBtm8HeOklgIYGVbHsobcXoKsLYOtWgLEx+u/X10f/Xb8eYN8++u8L4PRp\ngKNHAYaGomon4UtzyqhTdxNToahuX/5y1Dbz5wN88EHx91jtnQRP27Nk6+0F+I//4NNvby/ATTcB\nzJ0L8PWvZz/PK3fVAQuwY8cOXLRoEc6cORNLpRI+9dRTODAwgAMDAxPPPPLII9jW1oarV6/GN954\nI/M7HEVNolxG3LgRccsWxEqF/z0XsHEjIkD0s3175iN9fX1y3y6XEW+/HXHhQsQdO6zraMuWqJrr\n18uLIK0LIlQqUTOJyM/RxBMQMWVqXRTVbc6cyXqUSsXfo2hvHtki/fZx6TfZFgCRa6S/SSm3DQhx\nZ/I9YjnyCxIRUMR70rDdMXBY0vDwsNy3k3qZP19eR0SQIcY0pHVBgDxTKTIhEbIQMWXTumhqiuSq\nr0ccHY3+H6vuyfbW6WaRfoe59Bu3RfInrWcKO7WJ6iJ3la5WpWOggE5LSurlrrtIwxFTfWK5jLho\nEWJjY1QFmw6XZypFJiTSxCaiRtm2Gx2NIvaY2BH53Uenm2XpN6+OlQritm2ICxbQ6VnVRnnbg/e5\n6iJ3FYKMvampKZrC8HFqJw9JvRB3IklnbW2datzd3XTEnx5G5xGDic6mVIpkmDNnKsGZmn6gAiXR\n8tY97zld7UbZ4YqUJaNTlQ4yS3/VRe4qiFv59tutT1v4hKSzJlUnMgPE49jJYfTatfnPmRiA5ZmI\nC8N4kehv7txiffKCt+55z+lqN5Pz5rw2WvS+TAeZpb/qI3eWdYuwiK+rKIaRdNa0cfPOAPE4djyM\nvu8+fsOnHDnkleGaichEf9u2mZIuH7p0arLD5bVR1vuyHWSW/qqP3FnWzcsitsMvW1AcG6eNm1eV\nacNUESNZpq5oUJeJUExNqE6P2EItux0FsvRXfeTOslqdFm17tw0FLC0qpw2TVwzK3SkugEL9qtMj\nAW5DhGaqj9xZVqvTom3vtqGAI2zIK4bJxTITEFW/znjCx1jFR5lFwUMzsR6qj9xtwRFi5AJrf5gD\nbCg7neMb0s0gqn6d8YSPsYqPMouCx+Yn9RDInQaOECMXqsQLfFJ5FlSbQWfn5mPH6aPMouCx+cmN\nDXLcGa7ZixEnDPn2t6NkFy4nRInhUJ4ZFTQ0ABw44IfKs1DUDEW5aHTm4fElx08S8+dHP3Pm2JZE\nH3hsPm47WdQhIsq/LlBQXR0YKkoOXV1RdiGASKMHDlgVhwtjYxFz+NIZVSmKmsFH07IJX/XV2xsl\nKauvj4iZyiVluZMkn7tRqGow730fo+C4+/cMupzAFLLkZzWDj6ZlE77qK84+CRDZiKxrpu1LGlKT\nORIgKapcnprKTmaCM2+C1PWJ3yraQuD7UoGo/K6blmvo6YlORdvOPSQKqrWCtH3Jcqdf5J6sdWOj\nWu4Z31ZrLDOiat+SfJ8455lx+GpCLLgUO7jU+YvohdWJi3wnbV+1Qe5xrRsbp2Z6EoGvYZRlRkk6\nXFbObJH3t23zswli+GpCLLhEqC51nlR6EflO2r5qg9yr0at4oVp3xdAsnTeb19DjYuPc4ZQOSxVt\nuhS12oIIoeo+dBXfRyMbv1HKR9XRqHynNsjdB5hgCpkyFEOQSiVyOFEDTRZbKtGqJK9KoupxKWq1\nBZHYwfVDV5TyUcWTKt8J5O4KTDCFTBkEIYiMgdo4oCOqHpemAXyA64eubLWnrrgukLsryLsBghIy\n1ptiZlNTETozL+YN30XV49Jsn0s3VeWBauFQ9NsmvyEDXXFdIPc8mJ5QNXFJSNJ6Jevn+1QES36X\nyFoUMrcAubRm4LJd6daTrhFDIPc8yFqbrCWYHhNK1q/omrSWFn23FOrId+4SwalA5hYglwjV5Sku\n3XqKgwrqy2UCuSNme7istclagumwUbJ+eWKmI8dk9akIVEe+c5cITgWVivgtQC4Rqqj5m+yUqfRU\nJDO1LQZyR8zWqizZuuQxLBB3JnG144PARfc7qpTBUq2o0ye/2dNjhjBc2Rilc11Dtn6875rslKn0\nVCQzNXVUJ7mreDjl3qVqGfNzIK726Cjf/Y4qZVA6ffKbpgjD1Y1RLIiYskrZvO+6HkPxTAao5vMv\nQnWSuytJPFwY8zvQweiccUpXT8XpTRGGiXKoyxAxZRNtYNKmZMAzGaBCDzwy+kvurNq50q27IIdH\nuWUozlipOL3Iu1SXeOsCdRkiptzdLZ/Ay4UdSxQuw6MvFXrgkdFfcufZ02ZqEjUPLliqQ7llihzF\n0hkrKVAQgO5BFeX3RUyZpRtRmdLPmxiIUtgUS19xHe66i28BPH6+VJrcicaTRM9fche7TDDStANT\nFMZhuYMRcRSCM1bGQHGZtWpStSLY6oBYuhGVKf28iYFopYLY2qq2pZelNxUdxD88SfT8JXcer05b\nmY0pilrsUBIQIV8XBjq8EJU1y/Rkk6rxgiICTcrd2spnyizdtLRM7qriOYidroPOkVrSVVXPFLKo\nRrQOrJ1oLPhB7uVyFNrMnSs2kZe2MhtjeBcWVS2hxvu1KcgyvUpFLqkaL1Q7y3I5cjmA6GAUxSHq\n5Dd4Oot0HXQGAOmRlEq7sKimqA5Jv+nunkyX8fbbYnX3g9x5z1YXsYmN0NCFRVVLqOF+bRryTM/l\n0Uqy/bZto03O1dSEeMMNeneLyMq2fj3i/fer3erE0655dUjqff58eR35Qe68Z6tdZBOXvZcXHJ7U\n0RENG5uaJofbtdCv8ZKMj6OYdPtRmHL8jWQEn3c5GmsxlSoVU/KbyTMaceQOEC166kAeXSX1Hi+c\nzpiRnRSOlTDOD3KvVCINb9smNsceQAOOTjN5Re0//3OkfpUtcTKwQaC88YSLcUcRdMYlsavGl6MV\nLTinF1OpprPy2iWejopHLTqQR1dJvVcqU6P3tJysSQ0/yJ0X1RAluwiOTjO+MUlkZwM1GdsgUN54\nIsQdU5F2VdaCc9ZiatZJaBnktUscMfMmYZNBHl3lHczLkif5t1mzpgZS1UXuAXrA0WmOjkYRu8jO\nBmoytkGgvPGEjrjDx6mePOQtOOteTM37pulRZxJZB/PyJi4qlej/z5s33ZcCufsGhz1a1BmpybjW\nBm4+TvXkwbW2s6lbGb/IekcbuQ8NDWFHRwe2t7fj3r17p/39woULuHnzZuzs7MQVK1bg008/nV2Q\niIA2iE+mTBU5q8ijXXNo11Bk
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 290
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Early Perceptron Proposal)\n",
|
||
|
|
"\n",
|
||
|
|
"Two layers:\n",
|
||
|
|
"\n",
|
||
|
|
"- first layer is fixed, local feature extractors\n",
|
||
|
|
"- second layer is trainable, linear threshold units for classification\n",
|
||
|
|
"\n",
|
||
|
|
"Standard construction for many pattern recognition and machine learning systems.\n",
|
||
|
|
"\n",
|
||
|
|
"How powerful are such systems?\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"fig(\"perceptrons-idea\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAbIAAADlCAIAAAC57eWwAAAAA3NCSVQICAjb4U/gAAAgAElEQVR4\nXuzdR5NkR9XGcSQG77333nvhQQIknAQIEwQSbPgCECxgwYKPQIRWBEtcAIFRIKwQwnvv7Yv33iP8\n++v5E6lSdVVNtakezcy9i4pbmSePec5zTua91SOddIUrXOG///2vz+maEJgQmBCYEIDASVNPnHgw\nITAhMCEwi8BJvkydceLEhMCEwITAQODkCYsJgQmBCYEJgVkEpofoiQ8TAhMCEwKXQWA6LU6EmBCY\nEJgQmNrixIEJgQmBCYHlCEynxeXYTDMTAhMCJyQCU1s8IdM+BT0hMCGwHIGpLS7HZpqZEJgQOCER\nmNriCZn2KegJgQmB5QhMbXE5NtPMhMCEwAmJwNQWT8i0T0FPCEwILEfg0PKp42Rm/NPGk07a+peO\nB3kt/FeVs27MChy8ewcJxWRr1wjMsWghT7YzbaHYrn040RYe/23xP//5z7///e8rHr4OPrv//Oc/\nEZTpf/3rXyeffPKcD2Yj9JWudKWJxwefnWPCIobgCVcxBE8W+ozheG4WzcgvE1u4dhrcjsAhIAK0\nCXV7/BUnxlxyySVXvepVD74tAvZvf/vboUOH0PQvf/nLla985atd7WoQNg52aP/jH/+I8de85jV9\n3Z6eaeTEQWCuEqtKbEFgLPKJRS43o1rdVLARCYVQ3eDUFvdIm0PQB6VNRtfQO9TwHjVe3paL6OpX\nv/qBNZ1aXmdA932N2RgMYfgAnID7q1zlKnqlEe615BjalqpPDufzMeT55Y2i+QPPv/71r2gQY90j\nj33U12tc4xq21RBu3JJrXetaA3MsUr9tvaOEqXJN2dlFureaYA93x+VRsegOrCcy9/e///1Pf/qT\nbcZ9nc7WjbKdGeNo/rhPwFTP2m6OoeZSmOpWfz9IhHfB8mNiidQHY584MzoaCtlB+zrGZ4OqFWJd\nJ5skdVW80jGPIVJdTjJ1CMqYfTnx5thyo6bW5/Bcs/jhD3/oqccIOl7nOtfBaay96U1vGs7I2gnR\nrGNjxeCGzME/5u8F8F/96ldOLje+8Y15XkR70XbCrh380Q29Sxk4zFYlzmiLpgj3wOHG4Oh3bnou\n2Xo8OTzu0iWdH9FviJ2wIO808OPtkXmn8e9F3lbsbKgDunBRd8DsP/7xj7joK80+fSWGoNqlFjm2\nbsLxfuHmvxevDmwt/8UroumouBfMNbheYc3B2I8nNLv5wx/+YOOMVNqix23E+81vfgN8X8dZEvF+\n97vfoZYeimy64fSScXepmdrijnFrQ0bWX/ziFz/72c98OjcZvPa1r42FWO7SMvBYK6T95z//+a9/\n/WtMveUtb3m9611PH8RpAje5yU1ue9vboq96GEeGHXtz9BYI5+gZP34sS/2f//xnr787DwqskyDa\njA31e9/7HqY5m9uAb33rW+Oe7fbiiy9GuRve8IbWGnSDftqipnnd6173dre73fWvf303+manxenM\nuD5pjn5brI/weKRt3Og1zc5+jtiIaSjjMw0r+suatMhWwu5nV+WPpqbl4d+3v/1tO7YHnzvc4Q4+\nOwyiuEGz2uUvf/nLW9ziFne/+929MveCvIMVn3/wgx+Y+ulPf/r9739fc3ERcM2aXj+Fx67kwmTN\nAj4rMJe+ubVjdoyvme4NobfQjYXxNuizw6CmputpiF/84hdtq3hi3PaJJHiFcr7e7GY3u8997qMn\nGnGQ9Kkt3uAGN7jjHe9ooVU//vGPL7zwQkwzftppp5HEvfE0vQzhoDi6uG0oHTtVe/TbIhJoNFJY\nj5t9xWZ71GXM2hvd2Crdi7AHT7urXoMNsu7eJaPoRWGqejYx6Gb9N3eI5c8daKPKTa9ycJEGzQ7n\n+EDGrM+eoFHTtswxB8Cao+WW+PRKkYdI6atmipp8trGPP7OgAa29jiSG+vQwtNMsHqPy4J3tFDI1\n944SaOVOQudiNB6GIJ2dNU7nUX94XOhGLS8yEEAPI1hkBBR45fO73/2uSO2mPsXluRjz3d/qVrfC\njdvf/vY6HZrd/OY3VxQKxOZqS3Yw7NhIw+9///vvfOc7Dps2WpTDLk8zlNzznvf0jDKHMOu148rq\nxOHe6pI50AqUAJStZw23JFK7qSR8ankVg37x29/+Vsdxo2v83+ELmUotJRqQbfPe9763vVSvSS0N\nrrZHmkuz3Kd5NRbN1oUpZwvteubtV9cvfOELzncaJQo6AzokItmnP/3pb3zjGyh+17ve9R73uAe+\n3uhGN8LgO9/5ztbipbMhrnsO8tWUpxsUt7Gn2XHA3v65z31OLCxqo0zP/p64js/HloxeUDcEdZTw\nKUfG5aspeIKujdCGIX2EzXZ5bCTvEri8z7bFoceSowIL/wVSaLwtQJ5It/z2dzYEkNOgT4PC+clP\nfqJ5mX3Pe94j+2eeeSY6WY4PaP+Rj3wEIHe5y11OOeUUzQ4tPYt0VATR6aefrl0a/9rXvoZOKPq+\n973vaU97Go4h1Y9+9KNvfetbX/3qV8855xzd1k9kvXYMnBzo3l5SvRwV3C5XRg/0/+WCK0jQeX6g\nYNBW5sIVHOptnYb49a9/Xfu4733vixmohhySrQnqRxhvBCFUjkaDMbqnzkKJhoUiKGX/lOMqR77n\nzhTLckAtD63yWSelRFNDuC9/+ct80B/vdKc7ceM2t7lNvRixeE4/cptFVtu1Ea8RXSjOvTqgGzKu\n9meaNUQ6bfieiez5luuhjgNM6AWDo0erwpehtOtx8Ipd1sDrvpOLe4HLuAsgUglM8Cpm96CTcQL2\nFXhKq0/4qG14gogwmZopx2pDxo8KaAXY7798cGlhbQO2c7zq6GdcKxcvh92g0Cc+8QmdUSw21PYA\n+yt8sMUgiERNEucdEtWI3neve90rdikBQIGIXfTzqaYwSqO00MmxHo1mHkecIR73uMfRzIqrouNG\nXyF5tHADXT6MVB4VT+L2QZ8Wo8hsXckExmCPTLsISGdv4hDClKOflmHc1ufxQcEQsMpjAib1BI0W\nGgraKRWlRdjG6KolxcJ1irmzhnzQ70JELPSDCf2yhVL4pFmjF5r2G4s6HI/SCp4V5jjMc3p8Ijpy\nUzUoiLhKglo32EwznZagu5dHDgIhUJED4SjyYx3Q1pcBr0R3uINGr2jhYOOpID036BFALuOABaYp\nCyHma13vHe94R1nABxsh+fpsnsweHtf3bV8kueHiAJ95LnHuq3OBY5Ejoc/EtEgEiDPOdALUv5wD\nZByxtTzk0eZ8dcSjh0J8xjpioOAwrCADEzJKBifhZop+hvRBs5pmgHimcdRQHWgMtwqHTomgh+a6\n0r7gsAslPQ0IxFpuA41Lu9CzL0sOtC3GEp8ywXs38qHvOF7JnCdldH/Qgx704Ac/WNo8onZYINZz\n693udjcpxxhPE9JvHNXA1wOvpkmnoyUZLdIUAbnHLQJoug5e8uEiySIn+YavVFHrEOr51yFOI3Ph\nk2qs2eGujqa8+UDSWcZWj5rEmBZjva9TkoVuUNY7dWFSiLjMkeQqKJQHTnPYuDDJr+P5MSEDE71A\nAasBHbC90HnZYVxyZdwWImUwdEKURyjJgo0QPjAxQsD1yle+Um07LlkFc/VDDIA9iLSR1JVw4CCR\nESD+yFrd0FcJlW4slVY0EL5gEVssUlyfwmcx6u+gsCmK4vDj09bz02c/+1kLzT7ykY/s52aqtD/3\n1iIeijpBe3tjBH8Iu/S+b37zm4gHzDPOOINLHq7NOkmA1PnRFHO6LVu6qnQAbc0a2RCeXJKs2iLc\nxH78t0W5dLXzY0y7HBQcDyXe5VWIvGK559NOeahgXHaRTO+QxUc/+tEf/vCHpVy/kOP6nYOGrDs7\nPO95z/McjRP3u9/9aGBC4XlTgxkPf/jDLen0xw12Xd3UnUemZQJRTCGl3opD7mnr9ZZUKU5Pc+iL\njnRyUgF7mY3ZcqkAaKaES254
|
||
|
|
"prompt_number": 294,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0xf7de450>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 294
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Multilayer Perceptrons)\n",
|
||
|
|
"\n",
|
||
|
|
"Current multilayer perceptrons:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ y = \\phi(A\\cdot x + a) $$\n",
|
||
|
|
"$$ z = \\phi(B\\cdot y + b) $$\n",
|
||
|
|
"\n",
|
||
|
|
"Note that this can be converted into a single-layer recurrent network:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ y = \\phi(M \\cdot {x \\choose 0} + m) $$\n",
|
||
|
|
"$$ {0 \\choose z} = \\phi(M \\cdot y + m) $$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Book: Perceptrons)\n",
|
||
|
|
"\n",
|
||
|
|
"- primary point: when designing neural network architectures, you need to think about the complexity of the problem you want to solve\n",
|
||
|
|
"- illustrated this with the fact that a two layer network (like the one above) needs exponentially many units to compute connectedness\n",
|
||
|
|
"- book unintentionally contributed to killing interest in neural networks for many years\n",
|
||
|
|
"\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"fig(\"perceptrons-cover\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAATgAAAHGCAYAAADg55cDAAAABHNCSVQICAgIfAhkiAAAIABJREFU\neF7svS2MZcmSJnhnFVIHSKkDJAhQIECBGKlAtPRAggYBnrQJGiQYUGCkfcMKNCiwoOCDDwwoMOCB\nkaZWeiBXWpAjNUjQIEBLU2BBgAIBStoLCgRIECDBbSmkHfvM3fx8x46Zu9+IrPd63+apijznHv8z\nNzf73Mz/zr/7f+Xafb4+c+AzBz5z4K+QA//LX2GdPlfpMwc+c+AzB5QDnwHusyB85sBnDvzVcuAz\nwP3VNu3nin3mwGcOfAa4zzLwmQOfOfBXy4HPAPdX27SfK/aZA5858BngPsvAZw585sBfLQc+A9xf\nbdN+rthnDnzmwEnEgv/0f/wnfX17djvk0OnhsDucnrZ4B/l9dna2e3h42J3hLT0jHuK3dxImETW9\n5ZPdNV/JDnHxfDqRZpRnCwf9RIen70Grsa0T04CqMi+e89xj+nSdarv4+E+hcyQEs3Vd8dG1/XNl\nImvLTLa4PC+raNf/L1+mHzN16MkT0g/514kzo9fHyvN+t99dyH/7i/3uze2b3X/73/5bt5odC+56\ndyVK/3B1tbu6kvtDvdffyPX8/Hx3dnGxivPq1WF3f3+50/vh1e7y8l4ASe7yG3mcX14u7yQMcZD/\n/Su5S3nZ/ULKQVmIi/xwv5S71FXfGy1PuouycR4AMy2vvrdno8HCuSw8G+3gmdWX6zb73nh9JfxC\n/ZC3tYHl+6Q72s54XNtU8+H3tc2Z/oge0GR/xrsuD1QWkrZnOWGZGMgG8vNtf3kvMjWQJYQj3qHe\nuV1fScdQ+FHkHXfjD+LZe/Ak/l11xvSF8kFbWptGd2tjy9fiZ+85P/De6ES9mu6aDif3y1pf3E2e\nQdvh8rTxNtKzxj9Kr/J95G/ffqO2O7t6ozoBkMP1r//6r12A+3fRToa/++9/pwx6+/Vh9/jxw+7k\nw8nu8YvH3cmJGHz7kt/jS/n9SAagdM8a56PEfVHuMLkeP8rzC3nW7rvSYs/8DvmCZuSD9FLW42Nw\nr/nvxBDccUeL30+5kMdT01p5NQ/ww2gHn1Y8k7ppfX5Z85Lj4BkX1115jXTGz4gnGa/8e24TtB3a\nA22Ai9rKymt1cXxFeOO/8W7EA8ujlpflvZITS0Oy0WSohnlaIGtebmbEwvJRWSWemyyvZLLy0bcN\nl8NtZjLt23ZDp5N9i+91IqqPygfSm15ae0ImT4qu4m6X/TYdbvUTfW16xW0LuYTu1TyUz5Fug3f2\n3trI/fZYkNJleEF5nj2IMSL1lNvu9fvT3fdvbnd/+7d/mzZxCnAAm5+++GmTkBnFAMdEaqJPARwz\nkslxrMxj7708RjT06hmF8TsDaAZre47uI1r+HOGet6O2HvHA08w8OSbsz1H3f+NlNLAyEHLgxqCW\ngZ6Ctkv/nGpnwOqBtlcG5/Hilxe7cxlCAMCdvn+9+38GLmo4BofCHs6uBPXvVqjPlVcA+1jISsEt\nAhok6CmxV3q2rjw4eCvOlO0pdw9ynMdMC/eGbXxY77eFMe+OpWWG3ufEYRotn2PqH7Ub0zMKnx0i\nG+VjZXp5ZBn1fIo6I87H2ioqO5P7qLyIJq87jjavhwxi3mJbAU+VtSj9qgjfWXkZDXRV86R0sBTZ\nY9pgh5cnybOlkXw+fvFx9/OpAI+8/0rmCOCi/s3f/E0qzSnAnd/d7e5lCMgjcMup59ZZWHa3hooa\njPMdgVsmoCMA5XAPbE9xV3tWTRTGSjDzPBKs54BVBCw9RTwGiLzie6B27m3LOurkvGWXWem99sza\nIpLDnmXeAxpOF8kS64Qvw8f3+hPxs77z3hT/tufVkJKka7o9knmj07dXRF8W18v5jNz7+gZ09sAN\nyVOAu8cA7u5294H89o0ACpCuEHgkFJkijhjMgJg9Z4ITKatXAp9nT3kysJmhy8rtCXYE8BnQ+zI/\nBdBFfBy160z7ZZZ5ZJV7HvQAvmfpZG3vFdUr5YivGfCM0vn2meHbZJsOra9BPqkhE9VpxriJwDgD\n8J5+O7ptjFWtwosxc9JZVFhwNv68ArZIGCJ0Hpe9iuF7lyOTL9GfAkAjizOzKo8V6KjRj61oj5Zj\n8/Lx2fXsWTucLhN2diO9zGR1iPKKwLXXXgiLLEN+59vhEwLNsU3A1hWee3/I21tjUXyON0NPF9xm\nMpgAz6fQFKXRyaB6nd6zkMVEpBbc4VxmUCPrzXpFye/xUAubVYYOI1JffIbBM24gg/AsvZklN5M+\nskyO7QhGeUThTJsB8FgOCpepbTfjpL124HQMHmy1Wd19PlGZEYBGdYgstF6bRfzgPJrmEC88+I2s\n2Rl5pTgm97Py7+Nn6WbzAynHxD2yehr92Dp200Tt1SEqBbhVmplGjeLMpHsKxzgNl5G5JF7RPJMy\npfDxot9eKTyIZSAV1bsXd2SVsFXTs3oi3kWAPQPiUd2zd5kszPCnJ0fHCHwPzLjdevF8O8zw6Qg9\n+LWtqeeq2ydPP9P+mb5PEJMC3NXtlS4TUZO4zpa2WdNquTW3MptN/XOY/plfP3LlonDv+liPH1kU\nkSVi745xwbK8JY9Q2COeZjyI6InK69V7pg174BvR4DulY+JEQj3TllEdffv2ZGYgZ7xGbEPiBA+j\nSYEJ/W1r3GbizsT5ta25Lm8m+ATP4phOIAW4m+vd7qWAmx+H+xQm8Qyjnxyn57b1LI5RgZmVN0r3\njPBfTdhmXe9jXWCzfBiw2HqOng1kvAs6spR6VidbY6Pyj7EAO2353LY6Nv0xSt4TwWPLfYY4f5Kk\nPAaJLWmjKwQ47MW7vrnZ/ekflgE9zYiFCr8jyy0aK8l63WMUjRXBK5LPn2mwZ0/XLJ2cN+cV0cDK\n8pT8ffpRPUetm4VzvlmdIr75d54+DyZRO5gccXtG4NZrQ0/HqBwuk3kS8aEnqx6Mn9JeXOYIXL1r\nS78ZmPxOgBGgfRJwnJXvY3Qi4ye957piu9yT1sFh8/HN9bWYgm+VV23BoE0qEAdXC/l8g4wU0LsN\no98mYHyvZfgdFn41dq9R/SJIJtv3cKt8Kr3Ru9ntX1y2lpXxgIjy9Fr7rNoqWI1uvZ+Vsym78tXP\naPOCUUQJ6+vb2nWuKf+zTpjeZzPsnq4NbT35y1xWl4bXimXPmmQyv1XcQI65+I3bW90za2dfPc/j\niOcz4LaSk4yHkewP4mbuZVd/Onw9mzgMJLTgsJn8Uiy4t69HCFXDRz1RJjST2R8TLQO6DPBCJQ8K\ntHhdwDuGUAcUs65CRK8XWl9Xr/i+Lhw/Up6Mp5mCzSjaLKtGCunrOsPHLE/P20w2ZjvEER88XyOe\nZODO7/0sZQRQ/l2vDtxRZu0UlRl1OD79MYbHSEbgaY4W+oZ7Uf/9//nv9aSF+9PFgmuFkVvZHVgd\nUfc5/P8/HAjcGd0cLpd5AP73xtKpHQID8Epp/fDJeHhGixgBqEYKPJNWNrYeIZ9aH5xa8Pjiw+YA\nhy2YSbwTiWdX5REOY9CDD9wWp8wai4TId1hZpxWCT62rllfrtrK8KJzTz3Qsn1rgf/N//2b3P/7X\n/9HNNlzoa2NwEWM2p3i4BvrUlTg6v2w85uiMPnGCf6t0HVPN3thXJx89hSa46LAIDW2/eYLBAEbu\nUCKvSF3Fmh2r87QhnUsLhQ+tqQxIOY9K+5JHPcbF4rBsSBBOy+CTclbgNhj7Mitqys2M6p3UJxrn\ns/b4S4DbrNiGAIfZCYzBhRcPJEuE1ujMmNkByFkqSci94K2OTOKe1j9zHlxupgSj9x7YR/FZaSet\niy57RuX58F6dewVxPr3xwV55orAvxcJRK4fqDj3G1hs9HkqshQ9mMch7xOdxLZUzs3Iq2KSKxXSy\nHNgYlrdCnLyCTv1DmcgraK8GtjWvBXylVpbGpVvFAcZF8eoRYkYDmkaPMrKjyWodTh5ftlZj4G/D\nD5LGLDAFPTnyjEEaYfrHnQaN
|
||
|
|
"prompt_number": 295,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0x119572d0>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 295
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Does it matter?)\n",
|
||
|
|
"\n",
|
||
|
|
"- neural networks that everybody uses were/are fully connected and adjust weights in every layer, so reasoning doesn't apply\n",
|
||
|
|
"- (but complexity result probably is still true)\n",
|
||
|
|
"- worst case complexity results are not useful because brains/networks don't solve problems perfectly, they only need to solve \"many of\" the cases"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Complexity Theory for Learning)\n",
|
||
|
|
"\n",
|
||
|
|
"- large number of results on \"learnability\" and \"complexity of learning problems\"\n",
|
||
|
|
"- theory has been used to justify algorithms like support vector machines\n",
|
||
|
|
"- learning algorithms are applied without actually checking the conditions for learnability anyway\n",
|
||
|
|
"- as a result, most applications of machine learning are \"heuristic\": you try it out and see how well it works"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Summary"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Summary)\n",
|
||
|
|
"\n",
|
||
|
|
"- McCulloch-Pitts neurons as abstraction of biological neurons\n",
|
||
|
|
"- linear threshold units\n",
|
||
|
|
"- equivalence of linear threshold units to logic gates\n",
|
||
|
|
"- feed-forward and recurrent networks\n",
|
||
|
|
"- computational universality of neural systems via Rule 110\n",
|
||
|
|
"- linear separability, non-separable problems, XOR, connectedness\n",
|
||
|
|
"- computational circuit complexity, depth, fan-in/out, size\n",
|
||
|
|
"- complexity considerations for learnability"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(After we have examined machine learning and neural networks in more detail, you may want to re-read this chapter.)"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {}
|
||
|
|
}
|
||
|
|
]
|
||
|
|
}
|