13-perceptrons.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6532c5a0",
   "metadata": {},
   "source": [
    "Title: Perceptrons and Perceptron Learning Algorithm\n",
    "Author: Thomas Breuel\n",
    "Institution: UniKL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7db641ab",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "import scipy,pylab,numpy\n",
    "from numpy import *\n",
    "from scipy import *\n",
    "from pylab import *\n",
    "from urllib import urlopen\n",
    "from gzip import GzipFile\n",
    "from scipy.spatial import distance\n",
    "from scipy.spatial.distance import cdist"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e4e7abf",
   "metadata": {},
   "source": [
    "Linear Classification Problem\n",
    "==============================\n",
    "\n",
    "Let's start by generating a simple linear classification problem.  That is, a problem in which the optimal decision boundary is known to be linear.  We're also generating a problem in which the samples are perfectly linearly separable.  This is the exception rather than the rule.\n",
    "\n",
    "In a Bayesian framework, this means that $P(\\omega|x)$ is either 0 or 1 for any $x$.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "052479f7",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = random_sample((100,2))\n",
    "labels = (data[:,0]*0.7+data[:,1]*0.4>0.5)\n",
    "sum(labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5b96bce9",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "45 55\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD9CAYAAABHnDf0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X1sVVW+N/BvpQ1t1IsgypWeJshuI0WlmNQLjLE9zKTd\nHXqnk6iJNXOfx2GQ6RDpEWf+cKYvoYD6APePJ+3pk7k412GiKMHoHzXdcCg4nJ5EgRJx4F4hpJ6B\nsdSXiEL0Ki3luJ8/sC+nPa/77Je11/5+EiI93eyzunr87bV/a63fztN1XQcREUnlJqcbQERE5mNw\nJyKSEIM7EZGEGNyJiCTE4E5EJCEGdyIiCaUN7r/61a+wYMEC3H///UmPCQQCKCsrQ0VFBT744ANT\nG0hERNlLG9zXrl2LUCiU9Pv79+/HRx99hMHBQbz00kvYsGGDqQ0kIqLspQ3uDz/8MObOnZv0+2+/\n/TaefPJJAMCKFStw5coVfP755+a1kIiIspZzzn14eBglJSUTX/t8Ply8eDHX0xIRUQ7yzTjJ9AoG\neXl5M45J9BoREaVnpEpMziP34uJiDA0NTXx98eJFFBcXJzxW13X+0XVs3rzZ8TaI8od9wb5gX6T+\nY1TOwb2hoQGvvPIKAODYsWO47bbbsGDBglxPS0REOUiblnniiSfQ39+PS5cuoaSkBFu2bMHY2BgA\noKmpCWvWrMH+/ftRWlqKm2++Gbt377a80URElFra4L537960J+nu7jalMV7h9/udboIw2BeTROuL\niKahr6sL+aOjuD57NmoDAVTV19vy3qL1hRvl6bkkdbJ5o7y8nPJHRF5md6CNaBoOPvMMXohGJ15r\nVRSonZ22BXi6wWjsNGW1DJFMnByxJmvPjED7w9+taldfV1fc+wHAC9Eo2oNBzwR30T4H2WJwJ5rC\niUCajhOBNn90NOHrs0ZGLHk/0Yj4OcgWC4cRTZEskB4KBh1qkTOB9vrs2QlfjxUWWvaeIhHxc5At\nBneiKUQcsToRaGsDAbQqStxrLYqCmuZmy95TJCJ+DrLFtAwJy4mcp4gj1tpAAK3RaNxIskVRUGdh\noB3v5/ZgELNGRhArLERdc7NrUhK5EvFzkC0GdxKSUzlPJwJpOk4F2qr6es8E8+lE/Bxki0shSUht\nqorn+/pmvN6uqtiWogS1GSKahkNTAmmNh0asNEmUzwGXQpJUnMx5ennESpPc/jnghCoJSYacJ5GT\nGNxJSF5frUGUK+bcSVii5DyJnGQ0djK4G6BpEXR19WF0NB+zZ19HIFCL+voqp5tFRBJicLeJpkXw\nzDMHEY2+MPFaYeEGlJePYdu2/80gT0SmMho7mXPPUldXX1xgB4CRkT/igw/uwjPPHISmRRxqGRHR\nJAb3LI2OJls9OgvR6AsIBg/Z2h4nRDQNbaqKDr8fbaqKiKY53SQimobr3LM0e/b1JN+JAQBGRmbZ\n1xgHyFAtT1ZuL1FL5mJwz1IgUItotHVaaqYFQB0AoLAw5ki77MI632IS9aIr4gVHxDZZgcHdgH/6\npyu45ZZf4Ntv/we6fieA/wWgCorSgubmOqebZykZquXJSMSLrogXHBHbZBUG9yxMrpT5fxOvFRX9\nBosXvwaf7xCam+ukXy3DnaNiEvGiK+IFR8Q2TZXorsIoBvcsJFopc/Xqf8Dna0cotM2hVtlLhmp5\nMhLxoiviBUfENo1LdVdhBIN7FpKtlJF9EnUqr9f5zoWVuV4RL7oiXnBEbNO4ZHcVLxo8H4N7FpKt\nlJF9EnU6t1fLc4LVuV4RL7oiXnBEbNO4ZHcVhs9n6tkkl2iljBcmUSl3duR6RbvoinjBEbFN45Ld\nVRjF4J6F8cnSYLAdIyOzUFgY88QkKuVO5FyvlUS74ABitglIflcBg3l3Bvcs1ddXMZhT1kTO9ZIY\nkt1V/J9//VdD52PhMCIbJMq5tygK6jo7hRxFkjhYFZJIcKxPT0YwuBMRSYglf4mIaAKDOxGRhBjc\niYgkxKWQ5BivlF4lcgKDu8n48OzMeKn0KpETGNxNlOjh2dFoKwAwwE8jeulVIrdjzt1EiUoCe+W5\nqtny6nZ8IrukDe6hUAhLlixBWVkZduzYMeP7ly5dQl1dHZYvX4777rsPf/nLX6xopyuwJHDmuB2f\nyFopg3ssFsPGjRsRCoVw5swZ7N27F2fPno07pru7Gw888AD+9re/IRwO43e/+x2uX0/2EGm5sSRw\n5moDAbQqStxrLYqCGgFKr5I9IpqGNlVFh9+PNlVFRNOcbpJUUubcBwYGUFpaikWLFgEAGhsb0dPT\ng/Ly8olj7rrrLpw+fRoA8PXXX+P2229Hfr43U/ksCZw5kUuvkvXcMqHu5hVdKaPw8PAwSkpKJr72\n+Xw4fvx43DHr16/Hj3/8YyxcuBDffPMN3njjjaTn6+jomPi73++H3+831mpBsSRwdkQtvUq5ySQg\numFC3akLUDgcRjgczvk8KYN7Xl5e2hO8+OKLWL58OcLhMKLRKGpqanDq1CnceuutM46dGtxlxZLA\nznHzKEsWyQLif584gU+OHp343Xz76acJ/71IE+pOXYCmD3y3bNli6Dwpg3txcTGGhoYmvh4aGoLP\n54s75r333kNr643lfoqi4O6778a5c+dQWVlpqEFERrjlNl92yQLi4zt3Yt/VqxOvPV5UlPDfizSh\n7vYVXSknVCsrKzE4OIgLFy7g2rVr2LdvHxoaGuKOWbJkCQ4fPgwA+Pzzz3Hu3DksXrzYuhZTUpoW\ngaq2we/vgKq2QdMiTjfJNsmCyqFg0KEWeVOygFg+JbADwNNXr+I30wK8aBPqbl/RlXLknp+fj+7u\nbqiqilgshnXr1qG8vBy7du0CADQ1NaGlpQVr165FRUUFvv/+e+zcuRPz5s2zpfE0yesbqNw+ypJF\n0oA47esqAK8tXox2n0/YCXWRH6adEd0mNr6VJ9XWtuqAPuOPqrY53TRbtNbWzvzhAb1NVZ1umqf0\n9/bqLYoS9zv4dVGR3u/S301/b6/epqr65upqvU1V9f7eXtvbYDR2enPNooS8voHK9aMsSSRa4lqx\nciUO7tmDKhf+bty8oovBXRJe30DFdfPiSBQQIw8+yN+NzfiYPUkkyrkrSgs6O7nOnsjN+AxVgqZF\nEAwemrKBqoaBncjlGNxTYI11kgk3a3mL0dgpfc7d60sESS7crEWZkr6eO2usk0xE36zFSo/ikH7k\n7vUlgiQXkTdr8a5CLNKP3L2+RJDkIvKWeNHvKrxG+uAeCNRCUVrjXrtRY73GoRaRk9KlDURPK4j8\nkBOR7yq8SPq0DGus07h0aQM3pBVE3qwl8l2FJ5lQ+iAjNr4VUULp6s+wPk1uEtWV+YOiOFKPRSZG\nY6f0I3eicenSBkwr5EbkuwovYnAnz0iXNmBaIXduLrQlG+knVInGpZuMFHmykihbnig/IAOZSyjY\nuZ0+omk4NCVtUDMtbZDu+0RGGf2cG46dJub9U7LxraTT29uvK0pL3DyforTovb39TjctZ4km4Vo4\nCUeSyeVzbjR2Mi3jAjKXUODGF/ICJz7nDO4uIHMJBa5QIS9w4nPO4O4CMpdQ4AoV8gInPucM7g7S\ntAhUtQ1+fwdUtQ2aFkl4nMwlFLhChbzAic8517k7JJs68zKXUODGF/ICJz7nXArpEFVtQ1/f8wle\nb0cotM2BFhGRiIzGTqZlHCLzJCkROY/B3SEyT5ISkfMY3B0i8yQpETmPOXcHaVoEweChKZOkNVJM\nkhKReYzGTgZ3IgvYWS+H5GY0dnIpJJHJ3PBEJxHxgmguBncXkLkipIyS1RFpDwYZrJLgBdF8DO6C\ny2azE4mB9XKyJ/oF0Y13FQzugkteEbKdwV1QrJeTPZEviG69q+BSSMFxs5P7sF5O9kS+ILq1LDVH\n7oLjZif3Yb2c7NUGAmiNRuOCaIuioE6AC6LIdxWpMLgLLhCoRTTaGpeaubHZqc7BVlE6fFB0dkS+\nIIp8V5FK2nXuoVAImzZtQiwWw1NPPYXnnntuxjHhcBjPPvssxsbGMH/+fITD4ZlvxHXuhnGzE4nO\njROOmUqUc29RFNR1dtryM1qyiSkWi+Gee+7B4cOHUVxcjAcffBB79+5FeXn5xDFXrlzBQw89hIMH\nD8Ln8+HSpUuYP3++aQ0kIrElnHBUFKg2BT87OPngdEs2MQ0MDKC0tBSLFi0CADQ2NqKnpycuuL/+\n+ut49NFH4fP5ACBhYCcieYm+jNEMbkyzpVwtMzw8jJKSkomvfT4fhoeH444ZHBzEV199hdWrV6Oy\nshKvvvqqNS0lIiFZMeEY0TS0qSo6/H60qSoimmb4XF6VcuSel5eX9gRjY2M4efIk3nnnHXz33XdY\ntWoVVq5cibKyshnHdnR0TPzd7/fD7/dn3WAiEovZE45uXVdulnA4nHDeMlspg3txcTGGhoYmvh4a\nGppIv4wrKSnB/PnzUVRUhKKiIlRVVeHUqVNpgzuRVWSe3BOR2csYvZDmSWX6wHfLli2GzpMyuFdW\nVmJwcBAXLlzAwoULsW/fPuzduzfumJ///OfYuHEjYrEYRkdHcfz4cfz2t7811BiiXHl91OcEs5cx\nunVduWhSBvf8/Hx0d3dDVVXEYjGsW7cO5eXl2LVrFwCgqakJS5YsQV1dHZYtW4abbroJ69evx9Kl\nS21pPNF0Xh/1OcXMCUe3risXDeu5k1SeXbYM//e//mvG6x3V1egwIY9J1nN6XbloWM+dPC+iafjk\no48Sfs+KUR9z+9YQebeqmzC4kzT6urrw9NWraAUwtY5mU1ERfmFyjRLm9lPL9cLnxnXlomFwJ2nk\nj45ivChDO4BZAGIAsHix6YGCuf3keOETA0v+kjTGJ+KqAGwD0PHDf++ctnzXDFzRkZxbS+TKhsGd\npGFnHXWu6EiOFz4xMC1D0rBzIk7k+uNO44VPDFwKSWSQk5UCRcaljOaypOSvmRjcibyDF77ksl1J\n5Irg3tvbj66uPoyO5mP27OsIBGo9+dAJTYuwH4g8yEjte1dsYnrmmYNxj4uLRlsBwFOBTdMi7Aci\nj7JzCa2tq2WmBrTxr4PBQ3Y2wXFdXX3sByKPsnMlkeOrZUZGZjndBFuNjibucq/1A6XG0gZysnMl\nkePBvbAw5nQTbDV79vWEr3utHyg57vCUl51LaG0N7orSGpeSUJQWNDfX2dkExwUCtYhG2Q+UHEsb\nyMvOvRi2BvfOThXBYDtGRmahsDCG5uY6z00ijv+8Xu8HSo47POVmV1E0W4N7fX0VgxjYD7nwQi6a\nOzzJDI7n3Iky5ZVcNEsbkBm4QzUD3HQkhjZVxfN9fTNeb1dVbAuFHGhRblLdhXCHJ41zxSYmN+Km\nI3HIlItOdxfCh1VQrljyNw07Nh1pWgSq2ga/vwOq2gZNiwh1PlHIlItmzXOyGkfuaVi96cjsOwOZ\n7zRkykXLdBdCYmJwT8PqTUfJ7wzaDQVjs88nEpkenCzTXQiJicE9Das3HZl9ZyB7eQNZctEy3YWQ\nmBjc07B605HZdwYsb+AOMt2FkJi4FNJhiXLkitKCzk5jFxCzz0dEznLFwzoY3BPTtAiCwUNT7gxq\ncgrEZp+PyGtE2gnN4E5EZAIjT0uyktHYyXXuRERTyLIHgROqRFkS6ZadzCfLHgQGd6IseKV4mZfJ\nsgfBsbSMrFvkSW6y3LJTcrWBAFoVJe61FkVBjcv2IDgycpd5i7xsWBEzniy37JScLHsQHAnuMm+R\nlwkvwjPJcstuJhnnIGTYCe1IcJd9i7wseBGeiWUD4nEOQlyOBHdukXeHTz/9NuHrn3zyPza3RByy\n3LKbhQ/zFpcjwd3qYlxW8GLu+ZNPPkn4+qeffmpzS4wx8jvLJMUgwy27WTgHIa60wT0UCmHTpk2I\nxWJ46qmn8NxzzyU87sSJE1i1ahXeeOMNPPLIIynPaXUxLrN5Nff8z/98G778shXA1NRMCxYsmONU\nkzJm5HfGFEP2OAchMD2F69ev64qi6OfPn9evXbumV1RU6GfOnEl43OrVq/X6+nr9zTffTHiuNG8l\ntAceWKcDrTqw+Yf/9uuArqtqm9NNs1Rt7fjP2vbDz96mA/2u+LlvtF2f8SdV21tra2f+A0BvU1Ub\nW+4u/b29eouixPXXHxRF7+/tdbpp0jAaO1OO3AcGBlBaWopFixYBABobG9HT04Py8vK444LBIB57\n7DGcOHHC9IuP0+kQTYvg7NkCAM9PefXGCFD2CeAb6bOZFSZFTp+NMzJpzxRD9jgHIa6UwX14eBgl\nJSUTX/t8Phw/fnzGMT09PfjrX/+KEydOIC8vz7TGiZAO6erqw8jIH6e9+gKAdsh45zn9Yvpv/1aM\nY8fckT6bysikPVMMxnAOQkwpg3smgXrTpk3Yvn37ROUyPUX1so6Ojom/+/1++P3+lOcWYSleshFg\nYeHHaG5eZ0sb7JLsYtrZqboioE9lZNKeyxxJBOFwGOFwOOfzpAzuxcXFGBoamvh6aGgIPp8v7pj3\n338fjY2NAIBLly7hwIEDKCgoQENDw4zzTQ3umRBhPXyyEeDSpbe4LuClI8LF1CxGJu2zSTHIuHGH\nxDB94LtlyxZD50kZ3CsrKzE4OIgLFy5g4cKF2LdvH/bu3Rt3zN///veJv69duxY/+9nPEgZ2I0RY\nD59sBLh16+O2tcEuIlxMzVRfX5X1RSmTFANX1ZAbpAzu+fn56O7uhqqqiMViWLduHcrLy7Fr1y4A\nQFNTk6WNE2E9vBXLNq2cJM7l3CJcTN2AG3fIFUxds5OC0bfq7b2x9K66erOuqm16b2+/yS2zV29v\nv64oLXGr7RSlxZSfK9dzJ/73f3B9n5ttc3V1wiWTm6urnW6a9Pp7e/XW2lp9c3W13lpb64kll0Zj\np/DBXTZG1l/beW7ZLqZW4Hp4ZyRaU9/igTX1RmMnH9ZhMyvz2mac20ie2mu4qsYZbk6HOTEBz+Bu\nMyvz2syZ28NLG3dEWhXk1k1mTk3AM7jbSNMi+OKLz1BYuCFuY5RZk8QiTEB7hRc27oi2Ksitm8yc\nuuNgcLfJ5Aah/wQQwY0drh9j6dJbsHXr46akQtxWkI3EJloaxK3pMKfuOBjcbRK/QagKQBVGRoA7\n7jB3gxBz5mQW0dIgbk2HOXXHweBuE9k2CJH8REyDuDEd5tQdB4O7TTjZSW7j1jSIaJy648j7YR2l\n5cYLi3lVoqJcitKCzk7mxElcEU3DoSlBqcYFaRDZGI2dDO420rQIgsFDUyY7axjYiSglBnciIgkZ\njZ03WdAWIiJyGIM7EZGEGNyJiCTE4E5EJCEGdyIiCXETE5HJRKqkSN7F4E5kItEqKZL7TB8cGMV1\n7kQmalNVPN/XN+P1dlXFtlDIgRaRmyQaHOQBXOdO5DTRKimSuyQqs2wUgzuRiUSspEjukWxwYASD\nO5GJagMBtCpK3GstioIaCyopRjQNbaqKDr8fbaqKiKaZ/h5kr1xy7NNxQpXIRHaVd+XErZwSlVk2\nihOqJCRNi6Crqw+jo/mYPfs6AoFaVtCcghO38ppeZvn5gwcNxU6O3Ek4iWrfR6OtAGA4wLvpYpHJ\nOnlO3Mpr+tOmns/LM3QeBncSTvzzZm+IRl9AMGjsebNWXCyskmm6hRO3lA4nVCWlaRGoahv8/g6o\nahs0LeJ0kzJm9vNmk18sDhk6n5USLYV7IRrFoWAw7jU7J27JnThyl5CbRqqJmP28WTc9nDzTdItT\nz+Uk92Bwl5DZaY1UrMhlBwK1iEZbZzxvtrm5ztD53PRw8mzSLdNzs0RTMbhLyK6RarI7hBMn/htH\nj35iOOCPHxsMtk953qzxB4mbfbGwUqKlcC2KgjqmWyhLDO4SsmukmuwOYefOx3H16r4pr2WfEqqv\nrzLtLsPsi4WVmG4hs3Cdu4QSjagVpQWdneYGNL+/A/39HQm+0/HDn0mq2o5QaJtp703kFUZjJ0fu\nErJrpJrsDgGYeYcg4uQlkcwY3CVlZlojmUS57KKiJly9+osZx05PCblpUxGRGzG4S8bOoJnoDmHl\nygrs2XMQ0ejke06fvHT7Uk0iN2DOXSKJc+2t6OxUbQ2amhZBMHhoSkqoJu79VbUNfX3Pz/h3zMsT\nzWQ0dma0QzUUCmHJkiUoKyvDjh07Znz/tddeQ0VFBZYtW4aHHnoIp0+fzrohlDtRdmLW11chFNqG\ncLgDodC2GRcWN20qInKrtGmZWCyGjRs34vDhwyguLsaDDz6IhoYGlJeXTxyzePFiRCIRzJkzB6FQ\nCL/+9a9x7NgxSxtOM7klaLppUxGRW6UduQ8MDKC0tBSLFi1CQUEBGhsb0dPTE3fMqlWrMGfOHADA\nihUrcPHiRWtaSym5JWgGArVQlNa4127k5WscahGRfNKO3IeHh1FSUjLxtc/nw/Hjx5Me//LLL2PN\nmjUJv9fR0THxd7/fD7/fn3lLKS237MR006YiIruFw2GEw+Gcz5N2QvWtt95CKBTCn/70JwDAnj17\ncPz4cQSnVakDgCNHjuDpp5/Gu+++i7lz58a/ESdUbZFuMpOI3MWyTUzFxcUYGhqa+HpoaAg+n2/G\ncadPn8b69esRCoVmBHayjx3r24lIfGlz7pWVlRgcHMSFCxdw7do17Nu3Dw0NDXHHfPzxx3jkkUew\nZ88elJaWWtZYIiLKTNqRe35+Prq7u6GqKmKxGNatW4fy8nLs2rULANDU1IStW7fi8uXL2LBhAwCg\noKAAAwMD1raciIiS4iYmIpJSJs+idQMWDvMQ1mUhSi3TZ9HKjMHdZViXhSi9ZM+ibQ8GPRPc+YBs\nlxGlxABlz80PLXebTJ9FKzOO3F3GLSUGnGYkdWVluot3XPbK5lm0svJccHd7vtotJQacZCSQmh18\np3/OvvjiM0Sj/xl3jFUPLSc+ixYAoNtk+lv19vbrtbWtenX1Zr22tlXv7e23vA29vf26orTogD7x\nR1FabHlvsyT+Gf7gqp/BarW1rXH9M/5HVdtM/TfJJPodFRb+Rgf6Z5y/unpzDj8ppdLf26u3qaq+\nubpab1NVvb+31+kmGWI0TDsycnfqFjV5vto9oyfWZUnPSOrKzHRXos/ZyMgfAbQDiP898Y7LOlX1\n9Z6ZPE3EkeDuVJCVJV8tc4kBM9JmRlJXZqa7kn3OCgs/xtT5PBGLupE8HAnuTgVZ5qvFZtYdnZHq\nmGZW1Ez2OVu69BbccQfvuMgejgR3p4KsW0riWk3USWWz7uiMpK7MTHcl+5xt3fq4EP1M3uBIcHcq\nyDJfLfaSPDPv6IykrsxKd/FzRiJwrLYM6447Q+SHU4vcNqJMWFHPxnW1ZWSeFBSZyJPKTJuRm4lW\nz8Zzm5i8TuRJZaYzSESZjsZFq2fD4O4xoo+OeUdHIslmNC5aPRsGd4/h6Jgoc9mMxkWrZ8Pg7kEc\nHRNlJpvRuGj1bBjciYiSyGY0Pj6Sbw8GMWtkBLHCQtQ1NztWAoGP2SMiSiJRzr1FUVDX2Wlb0DYa\nOxnciYhSiGgaDk0ZjdfYPBpncCciMkD0B2m7bhMTEZHTRNt4ZCaO3IkEYHUxN1GLxTmtTVXxfF/f\njNfbVRXbQiEHWjQTR+5ELmV1MTdRisWJmP4QbeORmRjciRxm9cNrRHgCmajpD9E2HpnpJqcbQOR1\nVhZz07QITpwYsuz8mUq20/NQMGhbGxKpDQTQqihxr7UoCmokeJA2R+5EDrOqmNt4Ouby5RJLzp8N\nUdMf0zceffHNNxjVdfz13/8dfV1dQqSOjGJwJ3KYVcXcJtMxEQCtAJwrFidy+mP8Qdqipo6MYnAn\ncphVxdwm0z3j52kHMAtz555DZ+cGW/Lt45OoXwwP4zdFRfiPq1cnvudk3ZVERCvZmysGdyIBWFHM\nLT7dU4XxIP8v/2LPROr0kXAEwONFRVhYWopbFi50tO5KIqKmjoxicBcc1yeTUU7X7p8+Eq4CUHX1\nKtoXLhRmDflUIqeOjGBwF5go65PJnZyu3e+2kbBoJXtzxeAuMBHWJ5O7OVm7320jYdFK9uaKwV1g\nIj/MmigdN46Ex1fOyIDBXWAiP8yaKB3ZRsJuk3aHaigUwpIlS1BWVoYdO3YkPCYQCKCsrAwVFRX4\n4IMPTG+kbMLhcEbHBQK1UJTWuNduTIjVWNAqZ2TaF14gY19U1ddjWyiEjnAY20KhjAO7jH1ht5TB\nPRaLYePGjQiFQjhz5gz27t2Ls2fPxh2zf/9+fPTRRxgcHMRLL72EDRs2WNpgGWT6wa2vr0JnpwpV\nbUd1dQdUtR2dnXI9zJr/E09iX0xiX+QuZVpmYGAApaWlWLRoEQCgsbERPT09KC8vnzjm7bffxpNP\nPgkAWLFiBa5cuYLPP/8cCxYssK7VHsKHWRORESlH7sPDwygpmaxL4fP5MDw8nPaYixcvmtxMIiLK\nRsqRe15eXkYnmV5IPtm/y/R8XrBlyxanmyAM9sUk9sUk9kVuUgb34uJiDA1NlgsdGhqCz+dLeczF\nixdRXFw841x8ChMRkX1SpmUqKysxODiICxcu4Nq1a9i3bx8aGhrijmloaMArr7wCADh27Bhuu+02\n5tuJiByWcuSen5+P7u5uqKqKWCyGdevWoby8HLt27QIANDU1Yc2aNdi/fz9KS0tx8803Y/fu3bY0\nnIiIUtBNduDAAf2ee+7RS0tL9e3btyc8prm5WS8tLdWXLVumnzx50uwmCCNdX+zZs0dftmyZfv/9\n9+s/+tGP9FOnTjnQSntk8rnQdV0fGBjQZ82apb/11ls2ts4+mfTDkSNH9OXLl+v33nuvXl1dbW8D\nbZSuL7744gtdVVW9oqJCv/fee/Xdu3fb30ibrF27Vr/zzjv1++67L+kx2cZNU4P79evXdUVR9PPn\nz+vXrl3TKyoq9DNnzsQdo2ma/tOf/lTXdV0/duyYvmLFCjObIIxM+uK9997Tr1y5ouv6jQ+6l/ti\n/LjVq1fr9fX1+ptvvulAS62VST9cvnxZX7p0qT40NKTr+o0AJ6NM+mLz5s3673//e13Xb/TDvHnz\n9LGxMSeaa7lIJKKfPHkyaXA3EjdNfYbq1HXxBQUFE+vip0q2Ll42mfTFqlWrMGfOHAA3+kLWJaSZ\n9AUABIMFcVc9AAACrklEQVRBPPbYY7jjjjscaKX1MumH119/HY8++ujEwoX58+c70VTLZdIXd911\nF77++msAwNdff43bb78d+flyVkx5+OGHMXfu3KTfNxI3TQ3uXBc/KZO+mOrll1/GmjVr7Gia7TL9\nXPT09EzscJZx2Wwm/TA4OIivvvoKq1evRmVlJV599VW7m2mLTPpi/fr1+PDDD7Fw4UJUVFSgs7PT\n7mYKw0jcNPUyaPa6eDfL5mc6cuQI/vznP+Pdd9+1sEXOyaQvNm3ahO3btyMvLw/6jXShDS2zVyb9\nMDY2hpMnT+Kdd97Bd999h1WrVmHlypUoKyuzoYX2yaQvXnzxRSxfvhzhcBjRaBQ1NTU4deoUbr31\nVhtaKJ5s46apwd3MdfFul0lfAMDp06exfv16hEKhlLdlbpZJX7z//vtobGwEAFy6dAkHDhxAQUHB\njKW3bpZJP5SUlGD+/PkoKipCUVERqqqqcOrUKemCeyZ98d5776G19UbhPEVRcPfdd+PcuXOorKy0\nta0iMBQ3TZsR0HV9bGxMX7x4sX7+/Hl9dHQ07YTq0aNHpZ1EzKQv/vGPf+iKouhHjx51qJX2yKQv\npvrlL38p5WqZTPrh7Nmz+k9+8hP9+vXr+rfffqvfd999+ocffuhQi62TSV88++yzekdHh67ruv7Z\nZ5/pxcXF+pdffulEc21x/vz5jCZUM42bpo7cuS5+UiZ9sXXrVly+fHkiz1xQUICBgQEnm22JTPrC\nCzLphyVLlqCurg7Lli3DTTfdhPXr12Pp0qUOt9x8mfRFS0sL1q5di4qKCnz//ffYuXMn5s2b53DL\nrfHEE0+gv78fly5dQklJCbZs2YKxsTEAxuNmnq5LmNwkIvI4U1fLEBGRGBjciYgkxOBORCQhBnci\nIgkxuBMRSYjBnYhIQv8fpo3US/mibPUAAAAASUVORK5CYII=\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plotting the data points\n",
    "cla()\n",
    "d0 = data[labels==False]\n",
    "d1 = data[labels]\n",
    "plot(d0[:,0],d0[:,1],\"bo\")\n",
    "plot(d1[:,0],d1[:,1],\"ro\")\n",
    "savefig(\"tmp.png\")\n",
    "print len(d0),len(d1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bba2915",
   "metadata": {},
   "source": [
    "If we are only given this data (but not the equation generating it), how can we recover the decision rule?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88d333a4",
   "metadata": {},
   "source": [
    "We can visually read off the equation for the decision boundary.  It should run from (0.15,1.0) to about (0.7,0.0).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "764e4b49",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "43 57"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD9CAYAAABHnDf0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlcVXX6B/DPZVHJBVHcWBS8UGAmWpiACrjdi1xEE1NQ\ny30cS7FmahpZRsyldKYFscUmRU1F3Aq9VxEtARcQmxqbqZlCRgvtl2VqNuWC+P394YhcuPdyl7Of\n5/168SrgcM7jUZ577vf7fJ+vhjHGQAghRFHcxA6AEEII9yi5E0KIAlFyJ4QQBaLkTgghCkTJnRBC\nFIiSOyGEKJDN5D5z5kx069YNDz30kNVj0tPTERoaioiICHz66aecB0gIIcRxNpP7jBkzUFxcbPX7\n+/btw+nTp1FdXY133nkH8+bN4zxAQgghjrOZ3IcOHQofHx+r39+zZw+mTZsGABg0aBCuXLmCCxcu\ncBshIYQQh3m48sPnz59HYGBgw+cBAQE4d+4cunXrZnacRqNx5TKEEKJazjYRcHlCtemFrSVyxpjs\nP+rq65C4JRG/2fsb3L5926lzLF68WPQ/h1Q+6F7QvVDTvcjU6cCAZh9Zer3Vn3GFS8nd398ftbW1\nDZ+fO3cO/v7+LgUkZR5uHtiWsg2V5yrxSsUrYodDCJERXXo6MrVas69laLUYtWABL9dzaVgmOTkZ\na9asQWpqKiorK9GxY8dmQzJK0751exjTjIheFw2tjxaPhT8mdkiEEBmINRgAANl5eXC/fh31bdog\nYcGChq9zzWZyT0tLQ1lZGS5evIjAwEAsWbIEdXV1AIC5c+ciMTER+/btQ0hICNq2bYv8/HxegpSa\nQO9AFKUWIWFLAgI6BGCg/0C7fzY+Pp6/wGSG7sU9dC/uUfK9iDUYeEvmTWmYqwM79lxEo3F5/EiK\niv5dhKf2PYWKWRXo6d1T7HAIIQrjSu6kFaouGBs2Fr+P/j0MWw24euOq2OEQQkgDenJ3EWMMT+17\nCmevnMXetL3wcHNpGoMQQhrQk7uINBoN8kbngTGG9P3pin0RI4TICyV3Dni4eWD749tx5JsjyD2R\nK3Y4hBBCyZ0rHVp3gDHNiD8f/zP2fLlH7HAIISpHY+4cqzpfBcNWAw5MPYCHezwsdjhExcpNJpSs\nXg2PGzdwq3Vr6NLTLZbh2Xsc4V5L996V3Emzfxx71P9RvG14G8kFyaicXYmADgFih0RUqNxkwoGF\nC7G8pqbha5n/+//GycPe4wj3eL/3TAACXUZSVh5dySLeimBXr18VOxQzZUYjy9Tp2OK4OJap07Ey\no1HskAgPMnU6xoBmH1l6vVPHEe7Zc+9dyZ305M6T52OeR/WlaqTtSsMHqR9IokSSntLUw+PGDbPP\nywGUADhXWYksvb7h7X/T4+5yv36d/yBVju97TxOqPNFoNHgz8U3cqL+B3x34ndjhAABKVq82S+wA\nsLymBgfz8kSKiHCt3GRCll6PM599hizcSerlAA4AWAZgw08/YVlJCQ4sXIhykwm3Wre2eJ76Nm2E\nC1ql+L73lNx55OnuiR2P78CHZz5E3gnxEyg9pSnb3Xdmy0pKsPHyZSzDnaReCGB5k2PvvqgL3amQ\n3MP3vRd/rEDhOrbpCGOaEYPXD0Zvn94w3C/e8Ac9pSmbxXdmACZ6eAC3bjU73v36dcE7FZJ7+L73\nlNwFEOwTjF0TdyF5WzIOPXEIEd0jBLlu0zIrv+hoZNbUmCWADK0WCfSUpgjW3pm5tW8PXL7c7Ot3\nX9SF7FRIzPF57ym5CyQ6MBpvJL6BMQVjUDm7En7t/Xi9nrXJU/+pU5FdWUlPaQpk7Z1Z++BgZHbq\nZPZvYa6XF3DunNnkKlEWWsQksBVHVmDXv3ahfHo52rZqy9t1svR6LCspafb1bL0eS4uLebsuEY+l\nF/QMrRYJuXdaYhzMy8N/v/0W354+jaevXUPs/47J1Gqhz82lBC9BtIhJRhYNWYTqS9WYvHsydk/c\nDXc3d16uQ5On6tPSGG6swYAsvR6F//iH2c8tr6lBdl4eJXeFoeQuMI1Gg7VJa5GwOQHPH3wer+pf\n5eU6NHmqTi2N4dKLvnpQKaQIWrm3wq6Ju7Cveh/eOvkWL9egEjdiiVpe9O/W++fExyNLr0e5ySR2\nSIKjJ3eR+Hj5wDTZhCH5QxDsE4yEkAROz08lbsQSXXq64iumaCX2HTShKrJj3xzDY4WP4cMnP8RD\n3R4SOxyiAuUmEw42etEfpbAXfSUVE9CEqowN7jkYrye83lAi2b1dd0GvT+1e1Ufpde00r3AHJXcJ\nmPzQZJy+dBrJBckonV6K+zzvE+S69PZVOqT+Iiv1+BpTy7xCi1xpWWkvgS4ja7dv32ZP7H6CjS8c\nz+pv1wtyTbW0e5V6m+Myo5FlaLVmfwcZWq1k4pR6fE1ZineRhOO1xZXcScldQq7XXWex+bHs+ZLn\neb3O3WQ3zdvbYnJfHBfH6/WFJIfEJPUXWanHZ0mZ0ciy9Hq2OC6OZen1kvr7doQruZOGZSSktUdr\n7J64G9HrohHaKRRzHpnD+TUaD8VkWTlGSW9frbU5ltKiHamPEUs9PkuUPq9gD6pzl5jO93WGabIJ\n2YezcbDmIOfnb5zsdAAym3xfabXwckhMUh8jlnp8xDJK7hIU2jkU2x/fjim7p+Dz7z/n9NyNk10s\nAD2AbADTvb2RrdcjQWE9RuSQmKS+4Ezq8RHLaFhGomJ7xeJV/atIKkhC5axKdGvXjZPzNk12sf/7\nyI6Kkl0NsD3ksGhH6gvOpB4fsUzVi5hMpnKsXl2CGzc80Lr1LaSn62AwxLb8gwJaXLoYB04fwOFp\nh+Hl6eXy+Wx1DlTqL6vSF+0Q5XIld6o2uZtM5Vi48ABqau5tQKbVZiI3Vy+pBM8Yw5TdU3Dr9i1s\nm7ANbhrXR9Io2REiD5TcnaDXZ6GkZJmFr2ejuHipCBFZd/3WdYzcNBKxvWKxYsQKscMhhAjEldyp\n2gnVGzcsTzdcv85Pf3VXtPFog/cnvY/tn29H/qf5YodDCJEB1U6otm7dfMNgAGjTpl7gSOzTpW0X\nGCcbEbchDr069sLw4OFih0SIJMmpVQKfVJvc09N1qKnJbDLmnoEFC+xvvSv0hGyYbxi2pWxD6q5U\nlE0vQ5hvGG/XIkSOqF/SPaodcwfuJOe8vIO4ft0dbdrUY8GCUXYnZzEnZDf8fQOWli9F5axKdGnb\nhddrESInSmr3C/A85l5cXIywsDCEhoZi5cqVzb5/8eJFJCQkoH///ujbty82bNjgVCBiMBhiUVy8\nFKWlOSguXupQUl69usQssQNATc1y5OVxv6q0qen9pyO1byrGFY7D9VvSWWlJ+EG7CtlPDiuShWJz\nWKa+vh7z58/HoUOH4O/vj4EDByI5ORnh4eENx6xZswYDBgzASy+9hIsXL+KBBx7A1KlT4eGh7BEf\nsSdklw5birRdaZhZNBNbxm+BRqMR5LpEWDTM4Bg5rEgWis0n96qqKoSEhCAoKAienp5ITU1FUVGR\n2TE9evTA1atXAQBXr15F586dFZ/YAfEnZN00btgwdgPOXDmDxaWLBbmmkkn16dha47ODeXkiRSRt\n1CrhHptZ+Pz58wgMDGz4PCAgACdOnDA7Zs6cORg+fDj8/Pzw888/Y/v27RbPlZOT0/D/8fHxiI+P\ndz5qCeBiQhZwbVLWy9MLRalFiHo3CiGdQvBkxJMOXZvcIeWnYxpmcIzcWyWUlpaitLSUk3PZTO72\nvNVfsWIF+vfvj9LSUtTU1GDUqFE4deoU2rdvb3Zc4+SuBHcTcF5edqMJ2QSHxu0tTcrW1GSanb8l\nXdt2hXGyEfEb4tHLuxfiguIc+FMQQNptgWmYwXFybvfb9MF3yZIlTp/LZnL39/dHbW1tw+e1tbUI\nCAgwO+b48ePIzLyTkLRaLYKDg/Hll18iMjLS6aDkwmCIdakyxvqkbLZD5+3TpQ+2pmzFxJ0TcWTG\nEdzf+X6nY1IjKT8dy6HxmRypoRbeZnKPjIxEdXU1zp49Cz8/PxQWFqKgoMDsmLCwMBw6dAiDBw/G\nhQsX8OWXX6J37968Bq0UXE7Kjuw9EsuHL4dhqwEVsyrge5+vq+E5TK6/MFJ+Opb7MIMUSXkYjlMt\nbdW0b98+dv/99zOtVstWrFjBGGPs7bffZm+//TZjjLEffviBJSUlsX79+rG+ffuyLVu2cLpVlJLp\ndJmWdi9jen2W0+f8w8E/sCHrh7Drddc5jLRlctjOzhol7blJWianbQNdyZ20h6qIjMYyptVmmP0b\n02oXMaOxzOlz1t+uZymFKWzq7qns9u3bHEZrm5x+YSxRyp6bpGWL4+Jks3ewK7lT+TWLEsbFpGxT\nbho3bHpsE+I3xGNp+VL8Ke5PXIVrk5THre0h50k44hgpD8NxiZK7yFydlLXkPs/7sCdtT0OJ5OSH\nJnN6fkvU8gtD5E8tk9SU3BWqe7vuME42YvjG4ejp3RNDeg7h9XpK/YWR6yQxsU4tk9SqbhymBgdO\nH8C0D6bh6MyjCOkUwuu1lLbDU9OqinIAb3h5wS8kBG179KBET3hHOzERm97++G28VvkaKmZVoJNX\nJ7HDkY3GHQbLARwA0HhVQqZWC72C954l4qOdmIhNv438LZLuT0LK9hTcrL8pdjiy0XiSuATmiR1Q\nV48XqfbeIdbRmLtKrBq5CinbU/Cbvb9B/th86iJph8aTxNZ+UeRSDeQK1Sz6URh6clcJdzd3bBm/\nBf/8/p946ehLYocjC407DFruAaqOaiC1daZUyrsUenJXkbat2jaUSGp9tJjUd5LYIUla46qKH86d\nw2//8x+8fe1aw/eVUA1kD7mvYXCEkt6lUHJXGb/2ftibthcj3xuJnt49ER0YLXZIktZ4cVO5yaT4\n8jlL1LSGQcodQh1FyV1gQm+qbUlE9whsHLcR47ePx7GZx9Dbhxq92UOtq1jlvobBkbUKSnqXQsld\nQFz0b+dKYmgiModmNnSR7Nimo6DXJ/Ih50U/jg6zKOpdCge9bVok0GUkj48ukK5K35/ORmwcwW7e\nuilaDITwxdGGdlLrEOpK7qQndwGJvam2Ja/qXsW4wnGYZ5qHv475K5VIqpgSWy04Oswi53cpTVFy\nF5DYm2pb4u7mjoKUAgzNH4pVx1bhhSEviBaLo5SYjMSipCqRxpwZZlHM3AqH7yCsEugyksdH/3au\n1P5UywJeDWA7Pt8hdih2kfPmIFJTZjSyiZ07s8UAywRYmQz78VsjtWEWR7mSO+nJXUB89G/nSkCH\nAOxJ3QPdZh16evfEo/6Pih2STUoqWRPT3Sf2wh9/bPha5v/+Gwt5Vok0pqRhFkdRchcYH/3buTKg\nxwCsS16HcdvGoWJWBXp17CV2SFYpqWRNTBZfJAFk405yl2WVSBOKGWZxELUfIGaSH0jGHwb/AYat\nBvx0/Sexw7FKUSVrIrL6Iok7teyjZFLLTpqj5E6aWThoIeKC4jBx50TU1deJHY5Fjfu+3EXJyHHW\nXiT/7euLBGpnLGuC9XPX6TJFXZVJHHPr9i0kFySjp3dPvGV4S5IlkkrbHEQMlqpkMrRaSuwSIYvN\nOoB7l9FqM5Gbq6cEL3FXb1zFkPVDMC1iGn4f83uxw+GVmssq6UVSumSX3AFAr89GcfFSvi9NXPTN\nT98gel003kh8A+PCxokdDi8s1njTLkuEB44+RLiS3EWrlnFmVaYUmm6pTU/vnihKLcLoLaMR0CEA\nkX6RYofEOSqrJEIQeqGYaMnd0VWZQjTdohcPyyL9IvHXMX9tKJEM9A4UOyROqb2sUs1DUkIS+iFC\nlOSu1WZgwYIEh35m9eoSs8QOADU1y5GXl81JApZSx0YpGhc2DjWXapBUkISjM46ifev2YofEGb7L\nKqWcPJXadkCKhH6IECy56/Wurcrku+kW3y8eSvC76N/hq0tfYdLOSdiTtgcebspYA8dnv3KpJ08a\nkhKO0GszBPvtdHXylO+mW1Ls2Cg1Go0Ga0avgWGrAc8UP4O80XmSLJF0FJ9L1KWePNU+JCUkoTc9\nkc2jV3q6DjU1mWZP184M71gjxY6NUuTp7okdj+/A4PWDsfrEaiyMWih2SJzga4m61JMnrfQVjtB9\nbmST3PluusX3i4eSeLfxhnGyETHrYtDbpzfGPDBG7JAkS+rJU+5b6MmNkH1uBKtzF+AyLjOZypGX\nd7DRi8coGm+34cS5E0gqSELJ1BIM6DFA7HAkSQ4rQGkRk3TJYhGTHJI7cdzOL3bi2QPPomJWBQI6\nBIgdjiRR8iTOouRORLXy6Eps+3wbjsw4gnat2okdDiGKQcmdiIoxhjl75+D7X77H+5Peh7ubdCuM\npFxzTkhTlNyJ6Orq65CwJQEPdX0Irye8LnY4FlEPGSI3ruRO6udOOOHp7omdj+/EgZoDeKPqDbHD\nschazfnBvDyRIiKEPy0m9+LiYoSFhSE0NBQrV660eExpaSkGDBiAvn37Ij4+nusYiUz4ePnANNmE\nZUeWYV/1PrHDaUbqNeeEcMlmnXt9fT3mz5+PQ4cOwd/fHwMHDkRycjLCw8Mbjrly5QqefvppHDhw\nAAEBAbh48SLvQRPp6u3TG7sn7sbYbWNx8ImDiOgeIXZIDaRQc05j/vyhe2vOZnKvqqpCSEgIgoKC\nAACpqakoKioyS+5bt25FSkoKAgLulMH5+vryF61InO0WqdYuk9GB0cgbnYcxBWNQObsSfu39xA4J\ngPgLdqTeZ0bO6N42ZzO5nz9/HoGB99q7BgQE4MSJE2bHVFdXo66uDsOGDcPPP/+MhQsX4oknnmh2\nrpycnIb/j4+Pl83wjbPdItXeZXJS30k4fek0xhSMQfn0crRt1VbskARf/t2U1PvMyJlS7m1paSlK\nS0s5OZfN5G5PU6i6ujp88skn+PDDD/Hrr78iOjoaUVFRCA0NNTuucXKXE2e7RUqly6SY7x4yhmag\n+lI1puyegl0Td0miRFLI5d9N0Zg/f5Ryb5s++C5ZssTpc9lM7v7+/qitrW34vLa2tmH45a7AwED4\n+vrCy8sLXl5eiI2NxalTp5old7lytlukFLpMiv3uQaPR4J0x70D3ng4vHHoBf9H9hfdrSpkUxvyV\niu5tczarZSIjI1FdXY2zZ8/i5s2bKCwsRHJystkxY8eOxdGjR1FfX49ff/0VJ06cQJ8+fXgNWkjO\ndouUQpdJ6+8eDgoWQyv3Vtg9aTf2frUXaz9eK9h17VVuMiFLr0dOfDyy9HqUm0y8XUuXno5Mrdbs\naxlaLUZRky6X0b1tzuaTu4eHB9asWQO9Xo/6+nrMmjUL4eHhWLv2zi/p3LlzERYWhoSEBPTr1w9u\nbm6YM2eOopK7s90ipdBlUgrvHgCgk1cnmCabMGT9EAR1DII+RM/ZuV2pkBB6Ek7sMX8lo3trAROA\nQJfhjdFYxvT6LBYXt5jp9VnMaCzj9ee4otNlMoA1+9DrswSN464jXx9hXVZ1Yf+48A9OzldmNLIM\nrdbsD5eh1bIyo9Gun8/U6ZrfHIBl6fWcxEeIq1zJnZTcFcxoLGNabYZZ7tJqFwn+ItPY5lObWa/X\nerH/+/n/XD6Xq8l5cVycxZ9fHBfncmxqUGY0skydji2Oi2OZOp3dL6rEfq7kTtls1kEcx/cGJ9bY\nqtCZ0m8KTl86jeSCZJROL8V9nvc5fR1XKyRoEs55VFcuAxy+yFgl0GWIBFh+t5Bh9m7h9u3bbOru\nqSylMIXV3653+lquPrlbGtZZ5MCwjpq5cu/pid9+ruROenInnLKnvl+j0eDdMe9i1HujsOjDRVg5\n0nLPopa4uuKUJuGc5+y7JnriFw4ld8Ipeyt0Wnu0xvuT3kfUuiiEdgrF7IdnO3wtLpKzmIua5MzZ\nIS2lrCSVA0ruLVBrfxhnOVLf3/m+zjBNNmFo/lAEdwzGiN4jHL4eJWf+2CozdfZdk1JWksoBJXcb\nxF7hKUeO1vff3/l+bJ+wHY/veByl00vRp4vlNRLU8U9YLQ2fOPuuiSaxBcTh2L9VAl2Gc1KrE5cL\nZ+r7N/59Iwt+PZhd+O+FZt9ztZ6dOI6vNQA0ie0YV3InPbnbIJUVnnJjMMQ6/M7myYgnUX2pGmO3\njcVHT34EL0+vhu/ROK3w+Bo+EXsSW03vACm52yCF/jBq8mL8izh96TSmF01HQUoB3DRuKDeZcPrk\nSeQAuAVAB+DuywaN0/KHz+ETseZJ1FapQ3uo2pCeroNWm2n2tTvjx6NEikjZNBoN8sfm49zVc8g+\nnN3wy7jt8mXkAFgG4ACA8v8dT+O0/FFiIy617aFLT+5NNK2OmTrVH5WVwq7wVLM2Hm3wwaQPELUu\nCp9VFWFv019GANkAigXcQUmNxB4+4YPaKnUouTdirTomN1dPCV1AXdp2gWmyCZEX+uFwEDDsrPn3\nv/HxwazcXFknGjmQQpkpl2PkqqvU4XBi1yqBLuMyqo7hn9FYxnS6TBYXt5jpdJk2K2mmTHiEdX0O\n7N+dqWujGnFdJSXHSh1Xcic9uTdC1TH8cnTdwG+mL8GV1TNgmPIDKt8FfH8VdkNrIi6uq6SUONRk\nCyX3Rqg6hl+O7it755cuH4uKFuDh3/yIKf9+FKPnP6PYX0Zijo8xcikMNQmFqmUa4bs6xmQqh16f\nhfj4HOj1WTCZylv+IQVx5p1RrMGAI2tPIypGj2/mdMXQxES+wiMSo7oxco7Rk3sjfPY/p1YGzr8z\nctO4YeO4jRi2cRhyynKwJN75HeHlSE0Lbxpzteun6nE49m+VQJeRNJqsdX1nqO9+/o4FvR7ENv19\nE8+RSofaWy+UGY0sS69ni+PiWJZer5o/912u5E56cheIEidrHe2Y6eo7o27tusE02YT4DfHo1bEX\nYnsp/x2P2lsvqGmMnGuU3AUixGStkO2JnR1mcqbvTGN9uvTBlvFbMHHHRByZcQShnUOdPpccqG3h\nDeEOJXeBONoK11FCj+k7WvnCpVHaUVg6bCkMWw2omFWBzvd15vV6YqJJReIsSu4CsWdIwpUnb6GT\nrdjDTHMemYOvLn2F8dvHo2RqCVp7WE6CckeTiup0dxLdFZTcBWRrSMLVJ2+hk60U1gSsHLkSE7ZP\nwJy9c7Bx3EZoNBrBri0UtS284YqcK4wad69c3vLh1nE4sWuVQJeRNVeraYSuxnG18oUrv9z8hUW+\nE8leLH1R0OsS6ZJ7hVHjjVJcyZ305G6F0HunuvrkzfeYflN8rglwxH2e92FP6h5ErYtCSKcQpD2U\nJuj1ifTIvcLI2iS6w+fh5CwKI8aCI1eHOcRItq5WvnClR/seMKYZMWLTCPT07onBPQeLHRIRkdwr\njKxNojuMw3cTVgl0Gc6IseBIKsMccra/ej/r/pfu7PSPp8UOhYiIr/1fhdJ4WMmV3ElP7haIUQki\nlWEOOUsIScCfYv/UUCLp4+Uj2LXlPIGnNHKvMGo8iY4DB5w+DyV3C8SqBJHKMIeczRs4D9WXqpGy\nPQXFU4vRyr0V79dU296cUqeECqO7K3OXuVABpmGMMQ5jsnwRjQYCXIYzlsbctdoM5ObSk7Qc1N+u\nx/jt49HZqzPWJa/jvUQyS6/HspKSZl/P1uuxtLiY12sTZXMld9KTuwWuDJEIXWVDmnN3c8eW8VsQ\nmx+Ll4++jEVDFzl8DkeGWeQ+gUeUiZK7Fc4MkVBbX+lo16od9qbtRfS6aGg7aTHxwYl2/6yjwyzU\nIoBIkew365DSBhjWWwAcFCkidfPv4I89aXvw9L6nUXmu0u6fs1YnfTAvz+LxuvR0ZGq1Zl/L0Gox\nSiYTeESZZP3kLrUnZbH7rZDm+nfvjw1jN+CxwsdwfOZxBPsEt/gzjg6zKGECT6qoCsl5sk7uYnYm\ntEQK/VZIc4b7DcgYkgHDVgOOzzqOjm062jzemWEW6jvOPapCck2LwzLFxcUICwtDaGgoVq5cafW4\nkydPwsPDA7t37+Y0QFuk9qTM9x6sxHkLBi3AyN4jMWH7BNTV19k8loZZpMHR4TFizuaTe319PebP\nn49Dhw7B398fAwcORHJyMsLDw5sd98ILLyAhIcFq2Q4fVSRSe1KmhUjS9pr+NYzdNhZP7XsK7yS9\nY7VEkoZZpIGqkFxjM7lXVVUhJCQEQUFBAIDU1FQUFRU1S+55eXmYMGECTp48afVcfIyNC90syx60\nEEm63N3cUZBSgKH5Q/GX43/B84Oft3osDbOIj6qQXGMzuZ8/fx6BgYENnwcEBODEiRPNjikqKsJH\nH32EkydPWn0aqqnxBJDzv8/ibY6N2/uUT0/KxFHtW7eHcbIRUe9GQdtJi/Hh48UOiVgh9zYCzigt\nLUVpaSkn57KZ3O1Z2ffMM8/g5ZdfblhJZX01VU6zr1gaG3e0AoaelLmjlgVYAR0CUJRahIQtCQjs\nEIiB/gPFDolYwNfwmJQrcOLj4xEfH9/w+ZIlS5w/ma2uYhUVFUzfqJPaihUr2Msvv2x2THBwMAsK\nCmJBQUGsXbt2rGvXrqyoqMjsGAB2dVk0GstY584TBe/ISKx1pcxQdFfKD/71AfN7xY+dvXxW7FCI\nQOS2kUcLKdr2z9r6Zl1dHevduzc7c+YMu3HjBouIiGBffPGF1eOnT5/Odu3aZTHAltrZ3ksuiy0m\n97i4xU7/IUnLxGhzLAWvHn+V9X2zL7ty7YrYoRAByK0dsCvJ3eawjIeHB9asWQO9Xo/6+nrMmjUL\n4eHhWLt2LQBg7ty5dr9DyM3V2xwbv1eznmXx56lWnF9SKysVyjNRz6D6UjUm7ZwE42QjPNxkvfSD\ntEBNFTgt/ksePXo0Ro8ebfY1a0k9Pz/f6nlaGhu/l1x0ADIBSKcCRg2kVlYqFI1Gg9WjV2NMwRgs\n2L8Abya+qciNtskdaqrAkUxvmXvJJRaAHkA2gBz4+qZSq10BqHkBloebBwonFOLoN0fxeuXrYodD\neFBuMiFLr8cP58/jt15eZt9T6gI1yfRzpx7q4jOZypGXd7DR0NkoVd37r698jZj1MXgz8U2MDRsr\ndjiEI03bGJQDeMPLC34hIWjn54dREl6g5ko/d8kkd4CSCxHfyfMnkbg1EcVTivGI3yNih0M4IOfN\nVBSzWQf2vNoaAAASw0lEQVTVrBOxDfQfiLVJazF221hUzKpAoHdgyz9EJE1Nk6iNSWbMnRCpGB8+\nHgsHLURSQRJ+vvGz2OEQF6lpErUxSu6EWPBczHMY5D8IqbtSceu25UoiIg9q7fIpqTF3QqSkrr4O\nhq0GPOD7APJGU5tZOSs3mXCwURsDKU+iNqaYCVVCpOan6z8hZn0M5j4yF+mD0sUOh8iMq31sFDOh\nSojUeLfxhmmyCTHrYtDbpzeS7k8SOyQiE2LvJEVj7oS0IKhjEHZP2o0ZRTPw9+/+LnY4RCbE3kmK\nkjshdogKiMKbiW8iuSAZ56+eFzscIgNil2BScifETo8/+DjmRc7DmIIx+O/N/4odDpE4sUswKbkT\n4oA/DvkjBvQYgMm7JqP+trKbqhHXiF2CSdUyhDjoZv1NJGxOQET3CLymf03scIiEuVqCSaWQhAjs\n8rXLiFkfgwWPLsBTA58SOxyiUFQKSYjAfLx8YJpswuD1gxHcMRijQ0e3/EOECEiVT+5q2Qia8O94\n7XGM2zYOh548hH7d+okdDlEYenJ3gKW+8TU1dzapoARPHBUTGIPchFyMKRiDylmV6NG+h9ghEQJA\nhdUy9/ZqvaemZjny8g6KFBGRu7SH0jB7wGwkb0vGLzd/ETscQgCoMLmrdSNowq+s2Cz06dIHT7z/\nBG6z22KHQ4j6krtaN4Im/NJoNHgn6R38eO1HvHDoBbHDIUR9yV3NG0ETfrX2aI3dE3ej6N9FeOdv\n74gdDlE51VbL0F6thC/VP1ZjaP5QbHpsE3RandjhEBmjRUyESMyRr48gZXsKPpr2Efp27St2OESm\nXMmdqhuWIUQIQ3sNxav6VzGmYAwu/PeC2OEQFaInd5mjBVnSllOag/2n96N0Wim8PL3EDofIDA3L\nCERqidTSgiytNhO5uXpK8BLBGMPU96fiZv1NFE4ohJuG3iwT+1Fyd5IjyVqKiVSvz0JJyTILX89G\ncfFSESIilly/dR0jN43E0F5D8dKIl8QORzZc3X9UCaj9gBMcbUNgfWVrtmjJnRZkyUMbjzb4IPUD\nRL0bhdBOoZg5YKbYIUme2PuPKoFq3yM62oZAiomUFmTxy2Qqh16fhfj4HOj1WTCZyp0+l+99vjBN\nNmHRh4vw4X8+5DBKZRJ7/1ElUO2Tu6PJWoqJND1dh5qazCZDRRlYsCBBtJiUgo8Gcw/4PoDCCYWY\nuGMiyqaXIbxLOCexKpHY+48qgWqTu6PJWoqJ9G6SycvLbrQgK4EmUznA1zBcfFA8/jzqzzBsNaBy\ndiW6tu3qaqiKJPb+o0qg2uTuaLKWaiI1GGJFj0GJ+ByGm9Z/GqovVWPctnH4aNpHaONBCaspXXo6\nMmtqzIZmMrRaJAi0/6gSqDa5O5OsKZGqB9/DcC8OexGnL53G9A+mY2vKViqRbOLupGl2o/1HExzc\nf1TtVF0KSYg1lktfM5Cby927tWt11zB803CM7D0SS4dR6Sppjtc69+LiYjzzzDOor6/H7Nmz8cIL\n5u1Mt2zZglWrVoExhvbt2+Ott95Cv37m241RcpcXqS3WEosQDea+/+V7RL0bhcVxizGt/zROz03k\nz6XcyWy4desW02q17MyZM+zmzZssIiKCffHFF2bHHD9+nF25coUxxtj+/fvZoEGDmp2nhcsQCTEa\ny5hWm8EA1vCh1WYwo7FM7NAU64vvv2BdVnVhh88cFjsUIjGu5E6bA31VVVUICQlBUFAQPD09kZqa\niqKiIrNjoqOj4e3tDQAYNGgQzp0759yrDJEE2oZQeOFdwlGQUoBJOyfhy4tf8nadcpMJWXo9cuLj\nkaXXo9xk4u1aRHw2J1TPnz+PwMDAhs8DAgJw4sQJq8evW7cOiYmJFr+Xk5PT8P/x8fGIj493LFIi\nCCku1lKDEb1HYMXwFQ0lkr73+XJ6flrxKQ+lpaUoLS3l5Fw2k7tGo7H7RIcPH8b69etx7Ngxi99v\nnNyJdElxsZZazHp4FqovVeOxwsdw6IlDaO1hudbbGdZWfGbn5VFyl5CmD75Llixx+lw2h2X8/f1R\nW1vb8HltbS0CAgKaHffZZ59hzpw52LNnD3x8fJwOhoiPtiEU14oRK9C9XXfM3DOT0yIEWvGpPjaf\n3CMjI1FdXY2zZ8/Cz88PhYWFKCgoMDvmm2++wfjx47F582aEhITwGizhn1QXa6mFm8YNm8ZtQvzG\neLxY9iIWxy/m5Ly04lN9WiyF3L9/f0Mp5KxZs7Bo0SKsXbsWADB37lzMnj0b77//Pnr27AkA8PT0\nRFVVlflFqBSSEId899/vEPVuFJYPX44p/aa4fD5LY+4ZWi0ScnNpWEbCqJ87IQr0z+//ieEbh2PX\nxF0Y2muoy+crN5lwsNGKz1G04lPyKLkTolAlNSV48v0ncXTmUYR0omFPtaENsglRKJ1WhyXxS2DY\nasCla5fEDofICD25EyIDz5U8h4+//RglT5SglXsrscMhAqFhGUIUrv52PSbsmIAOrTtgw9gNDq1B\nIfJFwzKEKJy7mzs2P7YZn3//OZYfWd7yDxDVU20/d3IHdYCUj7at2mJv2l5ErYtCSKcQpPZNFTsk\nImGU3FWMj31CCb96tO+BvWl7MXLTSPT07omYwBixQyJOKDeZULJ6NTxu3MCt1q2hS0/nvizV6X6S\nDhDoMsRBOl2mWWvfux96fZbYoZEWmL4yse5/6c5qLtWIHQpxUJnRyDK0WrNfugytlpUZjc2OdSV3\n0pi7ismhA6TJVA69Pgvx8TnQ67NgMpWLHZIkJIYmImtoFgxbDbh87bLY4RAHWGvidjAvj9Pr0LCM\nikm9AyQNG9n29KNPo/pSNSbsmID9U/ZTiaRMCNXEjZ7cVUzqHSBp45CWvaJ7BW0922KeaR6VG8uE\nUE3c6MndRXKuNpF6B0gxho3k9vfp7uaOrSlbEZsfi5XHVuKPQ/4odkikBbr0dGTW1DRv4rZgAafX\noeTuAiUMGxgMsZKN1dVhI0cTtVz/Ptu1atdQIqn10eLxBx8XOyRiw92qmOxGTdwS+Gji5sKkr90E\nuozgqNqEX5Y3615k12bdzmz0Lfe/z0//71Pmu8qXVdRWiB2K7JQZjSxTp2OL4+JYpk5nsXJFDK7k\nTnpyd4Ecqk3kzJVhI+vj9dlWf17uf5/9u/dH/th8jC8cj+OzjiOoY5DYIcmCUveXpeTugpaGDeQ2\nfitFzg4bOZOopV49ZI+k+5PwwuAXYNhqwPGZx+HdxlvskCRPqfvLUnJ3QXq6DjU1mWZPiF5ecxEV\nFSHb8VulcCZRW/r7vFM9lMB5fHxKH5SO6kvVeHzH4zBNNsHT3VPskCRNqfvLUnJ3gcEQi5Mn/4lV\nqybh2rVwAPW4dm0KNm8+gD17PkFNzbtmx7c0LEBP+txxJlFLvXrIXhqNBq8nvI7kgmTM3z8fbxve\npi6SNih1f1lK7i6qqPgW164Vmn2tpiYWPj5pFo+3NixAT/rccjZRS7l6yBEebh4onFCIIflD8ErF\nK3gu5jmxQ5IsoUoThUbJ3UXWxnYBy6sFrQ0LODMBSGxTSqJ2VvvW7WFMMyJ6XTS0Plo8Fv6Y2CFJ\nkmCliQKj5O4ia2O7wcHt0KmT/cMCcq3UoKEkaQv0DkRRahEStiQgoEMABvoPFDskSYo1GGSfzJui\n5O4ia2O7L744CYD9wwJyrNSgoSR5eMTvEbw75l2MKxyHilkV6OndU+yQiABomz0OmEzlyMs72CiJ\nj3I4uVlKlFptBnJzpTuhp9dnoaRkmYWvZ6O4eKkIERFbXq14FRv+vgFHZx5Fh9YdxA6H2MGV3ElP\n7hzgYmxXjpUach1KUqtno57FVz9+hUk7J2Fv2l54uNGvv5LR366EyG0CUI5DSWqm0WiQNzoPSQVJ\nWFi8EGtGr6ESSQWjlr/EaVJvGUya83T3xPYJ21F2tgy5J3LFDofwiMbcOaTGyhEu5huI8L6+8jVi\n1sfgLcNbSH4gWexwiBWu5E5K7hyxPCGaidxcPSU7IklV56tg2GrAgakH8HCPh8UOh1hAyV0CqHKE\nCI2Ld4q7vtiFhcULUTm7EgEdAniKlDiLqmUkgCpHiJC4WmOQ0icFNZdrkLQ1CUdmHEH71u05j5WI\ngyZUOUKVI0RIzdtVlKOmRoMnnlgHvT4LJlO53ed6PuZ5DPQfiLRdaai/Tf9elYKSO0eocoQIyfyd\nYjmAAwCW4fLljSgpWYaFCw/YneA1Gg3eTHwT129dx+9KfsdHuEQENCzDETkuQiLyZf5OsQSAa03n\nPN09sXPiTsSsi8GaqjWY/+h87oIloqDkziG5LUIi8mXe04ib+Z6ObTrCNNmEmPUxCO4YDMP9ymqk\npTY0LEOIDBkMscjN1UOvz4aPz78tHuPMfE+wTzB2T9yN6UXTceq7U66GSUREyV1gpaWlYocgGXQv\n7nHmXhgMsSguXor33nuK0/me6MBovJH4BsYUjMG3P3/r1DlcQf8uuNFici8uLkZYWBhCQ0OxcuVK\ni8ekp6cjNDQUERER+PTTTzkPUknoH+49dC/uceVeNH6Kj4vLgV6f7XI30YkPTsRvI3+LMQVj8MvN\nX5w+jzPo3wU3bI6519fXY/78+Th06BD8/f0xcOBAJCcnIzw8vOGYffv24fTp06iursaJEycwb948\nVFZW8h44IeQePuZ7Fg1ZhOpL1Zi8ezJ2T9wNdzdasyEnNp/cq6qqEBISgqCgIHh6eiI1NRVFRUVm\nx+zZswfTpk0DAAwaNAhXrlzBhQsX+IuYECIIjUaDtUlr8fONn/H8wefFDoc4itmwY8cONnv27IbP\n33vvPTZ//nyzY5KSktixY8caPh8xYgT7+OOPzY4BQB/0QR/0QR9OfDjL5rCMvb2em/Y+aPpzSu8r\nQwghUmNzWMbf3x+1tbUNn9fW1iIgIMDmMefOnYO/vz/HYRJCCHGEzeQeGRmJ6upqnD17Fjdv3kRh\nYSGSk817PycnJ2PTpk0AgMrKSnTs2BHdunXjL2JCCCEtsjks4+HhgTVr1kCv16O+vh6zZs1CeHg4\n1q5dCwCYO3cuEhMTsW/fPoSEhKBt27bIz88XJHBCCCE2OD1ab8H+/fvZAw88wEJCQtjLL79s8ZgF\nCxawkJAQ1q9fP/bJJ59weXlJaelebN68mfXr14899NBDLCYmhp06dUqEKIVhz78Lxhirqqpi7u7u\nbNeuXQJGJyx77sXhw4dZ//792YMPPsji4uKEDVBALd2LH374gen1ehYREcEefPBBlp+fL3yQApgx\nYwbr2rUr69u3r9VjnMmbnCX3W7duMa1Wy86cOcNu3rzJIiIi2BdffGF2jMlkYqNHj2aMMVZZWckG\nDRrE1eUlxZ57cfz4cXblyhXG2J1/5Gq+F3ePGzZsGDMYDGznzp0iRMo/e+7F5cuXWZ8+fVhtbS1j\n7E6CUyJ77sXixYvZH//4R8bYnfvQqVMnVldXJ0a4vCovL2effPKJ1eTubN7krP0A1cTfY8+9iI6O\nhre3N4A79+LcuXNihMo7e+4FAOTl5WHChAno0qWLCFEKw557sXXrVqSkpDQULvj6+ooRKu/suRc9\nevTA1atXAQBXr15F586d4eGhvF6HQ4cOhY+Pj9XvO5s3OUvu58+fR2BgYMPnAQEBOH/+fIvHKDGp\n2XMvGlu3bh0SExOFCE1w9v67KCoqwrx58wDYX4IrN/bci+rqaly6dAnDhg1DZGQk3nvvPaHDFIQ9\n92LOnDn4/PPP4efnh4iICOTm5godpiQ4mzc5exnkqiZeCRz5Mx0+fBjr16/HsWPHeIxIPPbci2ee\neQYvv/xyw36RTf+NKIU996Kurg6ffPIJPvzwQ/z666+Ijo5GVFQUQkNDBYhQOPbcixUrVqB///4o\nLS1FTU0NRo0ahVOnTqF9e/VtBehM3uQsuVNN/D323AsA+OyzzzBnzhwUFxfbfFsmZ/bci7/97W9I\nTU0FAFy8eBH79++Hp6dns7JbubPnXgQGBsLX1xdeXl7w8vJCbGwsTp06pbjkbs+9OH78ODIz73S7\n1Gq1CA4OxpdffonIyEhBYxWb03mTkxkBxlhdXR3r3bs3O3PmDLtx40aLE6oVFRWKnUS05158/fXX\nTKvVsoqKCpGiFIY996Kx6dOnK7Zaxp578a9//YuNGDGC3bp1i/3yyy+sb9++7PPPPxcpYv7Ycy+e\nffZZlpOTwxhj7LvvvmP+/v7sxx9/FCNc3p05c8auCVVH8iZnT+5UE3+PPffixRdfxOXLlxvGmT09\nPVFVVSVm2Lyw516ohT33IiwsDAkJCejXrx/c3NwwZ84c9OnTR+TIuWfPvcjIyMCMGTMQERGB27dv\nY9WqVejUqZPIkXMvLS0NZWVluHjxIgIDA7FkyRLU1dUBcC1vahhT6AAnIYSoGO3ERAghCkTJnRBC\nFIiSOyGEKBAld0IIUSBK7oQQokCU3AkhRIH+H4x7Bqc4LACrAAAAAElFTkSuQmCC\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cla()\n",
    "d0 = data[labels==False]\n",
    "d1 = data[labels]\n",
    "xlim((0,1)); ylim((0,1))\n",
    "plot(d0[:,0],d0[:,1],\"bo\")\n",
    "plot(d1[:,0],d1[:,1],\"ro\")\n",
    "plot([0.15,0.72],[1.0,0.0],\"g\") # guess\n",
    "savefig(\"tmp.png\")\n",
    "print len(d0),len(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a57893c",
   "metadata": {},
   "source": [
    "(Linear Decision Boundaries)\n",
    "\n",
    "Note that these decision boundaries are linear, by construction.  \n",
    "\n",
    "We have seen other problems with linear decision boundaries, namely the decision boundaries in some cases where the class conditional densities are normal and all the covariance matrices are equal.  \n",
    "\n",
    "However, in this case, the class conditional densities aren't normal at all, they are uniform densities over quadrilateral regions.\n",
    "\n",
    "Some problems involving Gaussian densities yield linear decision boundaries, but linear decision boundaries are optimal for many other problems.\n",
    "\n",
    "How do we find these decision boundaries automatically?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c77f7a6b",
   "metadata": {},
   "source": [
    "(Decision Rules)\n",
    "\n",
    "A linear decision boundary is given by a formula of the form:\n",
    "\n",
    "$$a_1 x_1 + ... + a_n x_n = d$$\n",
    "\n",
    "We can write this as\n",
    "\n",
    "$$a \\cdot x = d $$\n",
    "\n",
    "With this, we classify as class 0:\n",
    "\n",
    "$$a \\cdot x \\lt d$$\n",
    "\n",
    "and as class 1:\n",
    "\n",
    "$$a \\cdot x \\geq d$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b9ac9f0",
   "metadata": {},
   "source": [
    "(Augmented Vectors)\n",
    "\n",
    "However, it turns out to be inconvenient to have the $d$ in all our equations; we therefore turn this inhomogeneous problem into a homogeneous one by transforming the vectors.\n",
    "\n",
    "$$ x \\rightarrow (1,x) $$\n",
    "\n",
    "$$ a \\rightarrow (-d,x) $$\n",
    "\n",
    "Now we can write for our decision problem:\n",
    "\n",
    "$$ a \\cdot x \\lt 0$$\n",
    "\n",
    "and\n",
    "\n",
    "$$a \\cdot x \\geq 0$$\n",
    "\n",
    "Therefore, for any inhomogeneous linear decision problem, we can construct an equivalent homogeneous one by simply adding a column of 1's to the data vector"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8c650eb",
   "metadata": {},
   "source": [
    "# The Perceptron Learning Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17cad8be",
   "metadata": {},
   "source": [
    "(Perceptron Correction)\n",
    "\n",
    "We want $a \\cdot x > 0$ for all samples in class 1.  Now, assume that this isn't working for some sample $x$, $a \\cdot x \\lt 0$ even though it should be $> 0$.  How do we fix that?\n",
    "\n",
    "Actuall, the solution is fairly simple:\n",
    "\n",
    "- When $a \\cdot x < 0$ when it should be $> 0$, we add \"a little bit of $x$\" to $a$.  \n",
    "- That is, we update $a \\rightarrow a + \\epsilon x$.  \n",
    "Then, next time, $(a + \\epsilon x) \\cdot x = a \\cdot x + \\epsilon ||x||^2 > a \\cdot x$.\n",
    "- For the other case, we subtract a little bit of $x$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed28ef19",
   "metadata": {},
   "source": [
    "(Halfspace Learning)\n",
    "\n",
    "But notice that the two cases are symmetrical; instead of considering two classes, we can simplify the problem further by flipping the sign of all the samples in class $0$.  Then, we require for all samples in the transformed problem that $a \\cdot x > 0$ (remember that we also augmented the data vector).\n",
    "\n",
    "So, the perceptron learning algorithm is:\n",
    "\n",
    "- given input samples $\\{x_1,...,x_N\\} \\subseteq R^n$ and corresponding classifications $\\{c_1,...,c_N\\} \\subseteq \\{0,1\\}$, first replace all the $x_i$ with augmented vectors $x_i \\rightarrow (1,x_i)$\n",
    "- then, for every sample for which $c_i=0$, negate the corresponding $x_i$, that is $x_i \\rightarrow -x_i$\n",
    "- pick a random starting vector $a$\n",
    "- repeatedly iterate through the training samples $x_i$\n",
    "  - if $a \\cdot x_i > 0$ then continue\n",
    "  - otherwise update $a$ according to $a \\rightarrow a + \\epsilon x_i$\n",
    "  - stop if there are no more updates\n",
    "\n",
    "Actually, it turns out that we can just use $\\epsilon = 1$.\n",
    "\n",
    "Let's see whether this works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "3d80c776",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# augmenting the original vectors\n",
    "augmented = concatenate([ones((100,1)),data],axis=1)\n",
    "flipped = augmented.copy()\n",
    "flipped[labels==False] = -flipped[labels==False]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "e602dbb2",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.75842167,  0.94856581,  0.80291539])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# random initialization of weight vector\n",
    "a = random_sample((3))\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8b13c589",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 27) (1, 17) (2, 16) (3, 4) (4, 14) (5, 13) (6, 6) (7, 2) (8, 4) (9, 12) (10, 14) (11, 9) (12, 4) (13, 4) (14, 10) (15, 14) (16, 6) (17, 4) (18, 5) (19, 4) (20, 10) (21, 12) (22, 8) (23, 6) (24, 4) (25, 5) (26, 4) (27, 4) (28, 4) (29, 6) (30, 10) (31, 10) (32, 6) (33, 6) (34, 4) (35, 4) (36, 4) (37, 6) (38, 5) (39, 4) (40, 4) (41, 0)\n"
     ]
    }
   ],
   "source": [
    "# perceptron learning\n",
    "for epoch in range(100):\n",
    "    nchanged = 0\n",
    "    for i in range(len(flipped)):\n",
    "        if dot(a,flipped[i])>0: continue\n",
    "        a += flipped[i]\n",
    "        nchanged += 1\n",
    "    print (epoch,nchanged),\n",
    "    if nchanged==0: break\n",
    "print"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "dd572cdf",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-8.24157833466 11.586087424 6.41877706797\n"
     ]
    }
   ],
   "source": [
    "# result of learning\n",
    "d,a0,a1 = a\n",
    "print d,a0,a1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0519a68",
   "metadata": {},
   "source": [
    "(reconstructing the linear equation)\n",
    "\n",
    "The linear equation is now:\n",
    "\n",
    "$$a_0 x + a_1 y + d = 0$$\n",
    "\n",
    "For $x=0$:\n",
    "\n",
    "$$y = -\\frac{d}{a_1}$$\n",
    "\n",
    "For $y=0$:\n",
    "\n",
    "$$x = -\\frac{d}{a_0}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "2de454cb",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "45 55\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD9CAYAAABHnDf0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtcVHX+P/DXcBHIu4I3oNTBFEzRfhSiCWjBIRG8plBr\naWBoKZptW3FZUbM1tW8BdsHVzFIR0xScsRFNgTUR3CwtcV1jtZBcF7fcboIwnN8fBgnMDDPDOedz\nzpn38/HgEQxnznl7mN7ncz6X99HwPM+DEEKIqjixDoAQQojwKLkTQogKUXInhBAVouROCCEqRMmd\nEEJUiJI7IYSoULvJ/cknn0Tfvn0xYsQIs9skJydjyJAhCAwMxOeffy5ogIQQQmzXbnKfN28eDAaD\n2d8fOHAAX3/9NS5cuICNGzdi4cKFggZICCHEdu0m9/Hjx6Nnz55mf19QUIAnnngCABAcHIzr16/j\n6tWrwkVICCHEZh3uc6+uroavr2/zzz4+Prh8+XJHd0sIIaQDXITYSesKBhqNps02pl4jhBDSPnuq\nxHS45e7t7Y2qqqrmny9fvgxvb2+T2/I8r6qvdZ+uw6h3RuHnup9tet/y5cuZxy6XLzoXdC7oXFj+\nsleHk3tsbCzef/99AMCJEyfQo0cP9O3bt6O7VYTnQp7D6H6jMWfvHDTyjazDIYSQZu0m9/j4eIwd\nOxbnz5+Hr68v3n33XeTk5CAnJwcAMGnSJAwePBh+fn5ISkrCW2+9JXrQcqHRaPB29Nv4zy//wfKi\n5azDIYSQZu32uefm5ra7kw0bNggSjBK5ubjho9kfIXhTMAI8AxA/Ir7d94SHh4sfmELQufid3M5F\niV6PwqwsuNTVocHNDZHJyQiNjpbk2HI7F0qk4TvSqWPLgTSaDvUfyd2Zq2fw4PsPQv+oHvd73886\nHKIyUifaEr0eB5cswerKyubXUrVacJmZkiV4cou9uZOSu4AKzhfgaf3TOJF4Aj7dfFiHQ+zEssVq\nLh6pE20ax+HlwsI2r6dzHFZZWNSoJnL5HNibOwWZCkluiR0ai3M15zBl5xT8bd7fcIfrHaxDIjYy\nmUh/+55Vgi/MymoRDwCsrqxEena2aDG51NWZfN25tlaU48mNHD8HtqLCYQL707g/YbjXcMzdN5dm\n0CiQuUR6KDubUURsEm2Dm5vJ143u7qIdU07k+DmwFSV3gWk0GmyM2YiqH6uwsngl63CIjeTYYmWR\naCOTk5Gq1bZ4LUWrRcTixaIdU07k+DmwFXXLiMDdxR37Zu/D/ZvuR4BXAGYNn8U6JEVi0ecpxxZr\nZHIyUisrW7QkU7RaRImYaJvOc3p2Npxra2F0d0fU4sWK6ZLoKDl+DmzGS0TCQ8nG51c+5z3XevIn\nq0+yDkVxinU6PkWr5Xmg+StFq+WLdTrJj/uSBMe1Jq40juOXh4XxaRzHPB61k9PnwN7cSbNlRPbR\nuY+wxLAEZYllGNB1AOtwFIPlbI0SvR6HbmuxRjhQi5X8Ti6fA5otI1PT/afjXM05TN05FcVzi+Hh\n6sE6JEVg2ecZGh1NyZwo/nNAA6oSSBmfgiG9h+DJgicd8u7FHqro8ySEIUruEtBoNNgUswn/+uFf\nWP231azDUQRHn61BSEdRn7uErvx0BcGbgvE69zpmBMxgHY7syaXPkxCWqPyAhPT6EmRlFaKuzgVu\nbg1ITo5EdHSoVe89deUUuG0cCv9QiNH9R4scKSFE6Si5S0SvL8GSJQdRWfl794q7+0L4+9dj1arH\nrUryuyt2Y9nBZShLLEP/rv3FDJcQonD25k7qc7dRVlZhi8QOALW1b+Pzz/tjyZKD0OtL2t3HzICZ\nSLw3EdPypqG2QTkr3gghykHJ3UZ1deZmjzqjsnI1srMPWbWf9NB03NXjLiQWJCrujqZEr0caxyEj\nPBxpHIcSvZ51SISQVmieu43c3BrM/MYIAKitdbZqPxqNBlumbEHYe2FYc2wNXhr/kkARiksN1fLU\nSi4laok8UHK3UXJyJCorU1t1zaQAiAIAuLsbrd7XHa53YN/sfQjeFAx/L39MHTZV2GBFwKL8LGmf\nXC+6crzgyDEmMVByt0O3btfRpctj+OWXn8HzfQDMARAKrTYFixdH2bQv727e2Dt7LybtmIRBPQYh\nsF+gKDELRQ3V8tRIjhddOV5w5BiTWKjP3QZNM2U+//xN/PzzdvB8Pjw8nDF8+HZwXDoyM6OsnhJ5\nu/u870P2w9mYsnMKrv58VYTIhUMrR+VJjhddOdZEl2NMtxNyPIta7jYwNVPmxo134OOTDoNhVYf2\nHXdPHCpqKjB913QcefwI3FxMJ1HWWJSfJe2T40VXjhccOcbUxNJdhT0oudvA3EwZawdR25MRnoGK\nmgo8pXsK7015DxqNRpD9CsnR63x3hJh9vXK86MrxgiPHmJqYu6t4xc79UXK3gbmZMrYMolripHHC\n1qlbMX7LeKw/vh7Pj3tekP0KTenV8lgQu69XjhddOV5w5BhTE3N3FXbvT9C9qZypmTL2DKJa0rlT\nZ+TH5WPM5jEY5jkMMUNjBNs3YUeKAU+5XXTleMGRY0xNzN1V2IuSuw2aBkuzs9NRW+sMd3cjFi+2\nbxDVEt/uvvho1keIyY3BJ49/ghF9Rwi6fyI9Off1ikluFxxAnjEB5u8qYGe/OyV3G0VHhwqezE0J\n9rlVPTJ2ZyzKE8vh1dlL9GMS8ci5r5fIg7m7ir9MnmzX/qhwmMylfJKCY98ew+HHD6OTcyfW4RA7\nmepzT9FqEZWZKctWJJEPqgqpUo18I2bsmoFeHr2wKWaTLGfQEOtQfXpiD0ruKvbzzZ/xwLsP4PHA\nx7EsZBnrcAghEqKSvyrWpVMX5MflY/3x9Thw4QDrcAghCkDJXSHu6nEXds/ajbn75qKipoJ1OIQQ\nmaPkriBjfcdifeR6xOTG4Nqv11iHQwiRMepzV6AXDr+AsstlKJxTqOgZNI5SepWQjqABVZnoyMOz\nrWVsNGJa3jT069IPOZNzFDmDxuRyfK0WHE0NJKQFSu4yYOrh2VptKjIzOcET/E91P2Hsu2Mx/975\nSA5OFnTfUkjjOLxcWNjm9XSOwyqDgUFEhMgTzZaRAVMlgW15rqoturp1xf74/fjLsb/g4NcHBd+/\n2Bx1OT4hUmk3uRsMBgwbNgxDhgzBq6++2ub3165dQ1RUFEaNGoV77rkH7733nhhxKoLYJYFbG9hj\nID585EPM2TsH/7j2D1GOIRZajk+IuCwmd6PRiEWLFsFgMKCiogK5ubk4d+5ci202bNiA0aNH44sv\nvkBRURGee+45NDSYe4i0uoldEtiUB+58AGseWoOY3Bh8f+N70Y4jtMjkZKRqtS1eS9FqESGD0qtE\nGkI+dYi0ZbFwWHl5Ofz8/DBw4EAAQFxcHPLz8+Hv79+8Tf/+/XHmzBkAwI8//ojevXvDxcUx65FJ\nURLYlCdHP4mzNWfxyIePwPCYAa7OrqIeTwhyLr1KxKeUZ5kqeUaXxSxcXV0NX1/f5p99fHxQVlbW\nYpv58+dj4sSJGDBgAH766Sfs2rXL7P4yMjKavw8PD0d4eLh9UcuUVCWBTVn70FrE7ozFEsMSvBX9\nlujHE4JcS6+SjrEmIcrxgd6tsboAFRUVoaioqMP7sZjcrZli98orr2DUqFEoKipCZWUlIiIicPr0\naXTt2rXNtrcnd7WSqiRwa85OzsidkYuQzSF4s/xNPHP/M5LHwJqSW1lqYS4hfnXyJL4rLW3+2/xy\n5YrJ98tpQJ3VBah1w3fFihV27cdicvf29kZVVVXzz1VVVfDx8WmxzfHjx5GamgoA0Gq1GDRoEM6f\nP4+goCC7AiL26+bWDfvj92Ps5rEY6jkUDw1+iHVIklHKbb7amUuIs9euRd6NG82vzfbwMPl+OQ2o\nK31Gl8UB1aCgIFy4cAGXLl3CzZs3kZeXh9jY2BbbDBs2DIcPHwYAXL16FefPn8fgwYPFi5iYpdeX\nYGHcu+h3LArRm6di457trEOSjLmkcig7m1FEjslcQvS/LbEDwDM3bmBBqwQvtwF1pc/osthyd3Fx\nwYYNG8BxHIxGIxISEuDv74+cnBwAQFJSElJSUjBv3jwEBgaisbERa9euRa9evSQJnvyuzQKqqnFY\ndCMZ3V16YPYU9bdcld7KUguzCbHVz6EAtg8ejHQfH9kOqMv5YdrWaHday8MPP4yHH364xWtJSUnN\n33t6emL//v3CR0Zs0mYB1an5qO9zFs/wizEjhoOLk7pnMCm9laUWphJikocHHmvVcgeAPj4+sl6N\nrPQZXer+P96BmFxAVbgejUN0WHZwGbIezpI+KAkpvZWlFqYSYuCYMTi4bRtCFfi3UfKMLkruKmFy\nAVWjC0ZXTsOhf+mQ8/ccJAUltd1GJZTeylITUwmx5L776G8jMSocphKmi5alIDMzCneP6Y8HtjyA\nnTN2YsKgCQyjJITYiqpCEuj1JcjOPnTbAqqI5jn3Ry4eQfyeeHz65Kfw6+XHOFJCiLUouVsgRY11\nJXj75NvILs9GaUIpurt3Zx0OsRMt1nIs9uZO1fe5m+quqKy8tejK0RL8wvsW4mzNWcTticP++P2q\nn0GjRrRYi1hL9fXcpayxrgRvRL2BhsYGPH/oedahEDvIfbEWVXqUD9U33aSusS53Lk4u2DVzF4I3\nBWO413Ak3pvIOiRiAzkv1qK7CnlRfcudRY11uevp0RP74/cj9UgqSr4pYR0OsYGcF2vJ/a7C0ag+\nuScnR0KrTW3x2q0a6xGMIpKHoZ5DsW3aNsz6cBb+9cO/WIcjmfa6DeTerSDnh5zI+a7CEam+W4Zl\njXW5i9BGIC00DTG5MShNKEU3t26sQxJVe90GSuhWkPNiLTnfVTgkXiISHorYoLGxkV+gW8BHb4/m\nG4wNrMMRVWpkJM8Dbb7SOM6q3xPLinU6PkWrbXHuXtJq+WKdjnVoimZv7lR9y51YptFokBWVBW4b\nhxc/eRHrItaxDkk07XUbULdCx8j5rsIRUXIncHV2xYePfIgxm8dguNdwzB01l3VIomiv24C6FTpO\nyYW21Eb1A6rEOr3v6I2CuAL86dCfcOzbY6zDEUV7g5FyHqwkxFYOUX5ADaQqoWD42oB5+fNQmlCK\ngT0GCr5/U6RcTl+i1+PQbd0GEa26Ddr7PSH2svdzbnfuFLDf3yIJD6U6Ol0xr9WmtBjn02pTeJ2u\nWJTjvV76Oj/irRH8j7U/irL/25kahEuhQTiiMh35nNubOym5K0BkZKqpSRw8x6WJcrzGxkY+sSCR\nj82N5Y2NRlGO0YRmqBBH0JHPub25k/rcFUDqEgoajQZvTnoT/6v9H1I+SRHlGE1ohgpxBCw+55Tc\nFYBFCYVOzp2we9ZufFjxIT44/YFox6EZKsQRsPicU3JnSK8vAcelITw8AxyXBr3edJ0XViUUPO/w\nREFcAZ4rfA6lVaWiHINmqBBHwOJzTrNlGDH9WLxUZGZyJmfBWHrKkuix/lOP+fvn40TiCdzZ/U7B\n908zVIgjsPdzTk9iUhiOS0Nh4csmXk+HwbCKQUSWvXb8NXxw5gMce/IYunTqwjocQhyGvbmTumUY\nUVqd+WUhy3Bv/3vx+N7H0cg3sg6HENIOSu6MKK3OvEajwdvRb6Pm1xr8+eifWYdDCGkHJXdGlFhn\n3s3FDXtm7cH2L7djx5c7WIdDCLGA+twZYjlI2hFfXv0SE9+fCF28DsE+wazDIUTVaECVSKrgfAEW\n6heiLLEMPt18WIcjO1LWyyHqZm/upJK/xC6xQ2NxruYcpuycgpK5JejcqTPrkGRDCU90kiO6IAqL\nWu4KIFVFSFvxPI+5+XPxa/2vyJuZBycNDeEAQBrH4eXCwjavp3McVhkMDCKSP5MXRK0WXGamwyd4\narmrlKnFTpWVtwZiWSd4jUaDnMk5mLh1IlYWr0RGeAbTeOSC6uXYrjArq0ViB4DVlZVIz86WRXJX\n4l0FJXeZy8oqbJHYAaCycjWys9OZJ3cAcHdxx97Ze3H/pvsR4BWAWcNnsQ6JOaqXYzs5XxCV2s1G\n99Eyp4TFTn279EV+XD6eOfAM/v7d31mHwxzVy7GdnC+I5u4qDmVnM4rIOtRylzmlLHYa1W8UNk7e\niGl503Ai4QS8u3mzDokZelC07SKTk5FaWdkiiaZotYiSwQVRzncVllByl7nk5EhUVqa2KjCWgsWL\noxhGZdo0/2k4d+0cpuZNRcncEni4erAOiRl6ULRt5HxBlPNdhSXtzpYxGAxYunQpjEYjEhMT8cIL\nL7TZpqioCM8++yzq6+vh6emJoqKitgei2TJ2U9JiJ57n8Ye9f0Aj34gd03dAo9GwDolIQIkDjtYy\n1eeeotUiSqKZPKIsYjIajRg6dCgOHz4Mb29v3HfffcjNzYW/v3/zNtevX8e4ceNw8OBB+Pj44Nq1\na/D09BQsQKI8N+pvIHxrOCYPmYz0sHTW4RCROcI0RpZlqUWZClleXg4/Pz8MHDgQABAXF4f8/PwW\nyX3Hjh2YMWMGfHxurVI0ldiJY/Fw9cC+2fsQvCkYAV4BmBEwg3VIRERyn8YoBCV2s1mcLVNdXQ1f\nX9/mn318fFBdXd1imwsXLuD777/HhAkTEBQUhA8+EO+RbEQ5+nftj31x+7BAvwCfX/mcdThERGIM\nOJbo9UjjOGSEhyON41Ci19u9L0dlseVuTX9pfX09Tp06hU8++QS//vorQkJCMGbMGAwZMqTNthkZ\nGc3fh4eHIzw83OaAiXLc2/9evB39NqbsnIKyxDL079qfdUhEBEIPOCp1XrlQioqKTI5b2spicvf2\n9kZVVVXzz1VVVc3dL018fX3h6ekJDw8PeHh4IDQ0FKdPn243uRPHMDNgJipqKjAtbxqK5hbB3UX8\nGQZqHtyTI6GnMTpCN48lrRu+K1assGs/FpN7UFAQLly4gEuXLmHAgAHIy8tDbm5ui22mTJmCRYsW\nwWg0oq6uDmVlZVi2bJldwRB1Sg9NR0VNBRIKErBt2jZRZ9A4equPBaGnMSp1XrncWEzuLi4u2LBh\nAziOg9FoREJCAvz9/ZGTkwMASEpKwrBhwxAVFYWRI0fCyckJ8+fPR0BAgCTBE2XQaDTYMmULQt8L\nxZpja/DS+JdEO5ajt/pYEXLAUanzyuWGqkISyVT/WI3gTcHYMGkDpg6bKsoxnh05Eq9/+WWb1zPC\nwpAhQD8mER/reeVyQ1Uhiex5d/PG3tl7MWnHJAzqMQiB/QIF3X+JXo/vvv7a5O/EaPVR37445Lxa\nVUmo5U4kl/dVHl44/ALKEsvQt0tfwfabxnGILCzEQQC319FM8vDAYx9+KGhycISFOx1BFz7hUMud\nKMbse2aj4tqtGTRHnzgKNxfTfay2cqmrQ1NRhnQAzgCMADB4sOCJhfr2zaNBbXmgkr+EieVhyzGg\n6wA8pXtKsDu6poG4UACrAGT89t8+PsI/45VmdJin1BK5akPJnTDhpHHC1qlb8eXVL7Hu+DpB9ill\nHXWa0WEeXfjkgbplCDOdO3VGQXwBgjcFY5jnMMQOje3Q/qQciJNz/XHW6MInDzSgSpgru1yGybmT\nceTxIxjRdwTrcKzGslKgnNFURmGJUvJXSJTciSU7vtyB1COpKE8sh1dnL9bhkA6iC595ts4kUkRy\n1+mKkZVViLo6F7i5NSA5OVK2D50Qk15fQufBhNQjqSj5pgSH5xwWbAYNIXJizxRauxvGvEQA8Fpt\nCg/wzV9abQqv0xVLFYIs6HTFdB7MMDYa+ak7p/Lz9s3jGxsbWYdDiOBSIyP5Fv/z//aVxnFm32Nv\nmpZ0tsztzwFt+jk7+5CUITCXlVVI58EMJ40TPpj2AU5dOYXXT7zOOhxCBCflTCLms2Vqa51ZhyCp\nujrTp9zRzoM5XTp1QUF8AcZsGoNhnsMwacgk1iExQSs81UnKmUTMk7u7u5F1CJJyc2sw+bqjnQdL\n7ux+J/bM2oMpO6fg6BNHMbzPcNYhSYpWeKqXpFNo7e07shVM9rm/5HB9zab73B3vPFhj6xdb+cGZ\ng/maX2pYhyIpe/pliXIU63R8Gsfxy8PC+DSO44t1Oovb25umJW25Z2ZyyM5OR22tM9zdjVi8OMrh\nZok0/Xsd/TxY4/HAx3G25ixm7pqJwjmF6OTciXVIkqAVnuom1cO2aZ47kTVjoxHT8qahX5d+yJmc\ng78dOKD6vug0jsPLhYVtXk/nOKwyGBhERFiiqpBElZydnLF9+naMe3cclmxJQtdXjqi+L5pKGxAh\nUMvdCrToiL1L1y9hxLqh2J13E1zLgoOKbdFamhFDKzxJE2q5i0SvL8GSJQdbzE2vrEwFAErwEhrY\nYyAe+SoAc6Z/gZItwLBrv/9OiX3R7c2IkapflqgXlfxthxSLjvT6EnBcGsLDM8BxadDrS2S1P7kY\nUNsHrx4CYuKB7z1+f12J1Qap5jkRG7Xc2yH2oiOh7wzUfKcRmZyMg0sqMeV8JR55BDBsA5YPUmZf\nNM2IIWKjlns7xF50JPSdgZrLG4RGR4PLzISbJhJV3Xoh5ClfxZaRpZrnRGyU3NuRnBwJrTa1xWta\nbQoWL44QZP9C3xmovbxBaHQ0VhsO4u/rL+LGiK740usS65DsIuVTo4hjom6Zdoi96EjoOwNHKW/Q\nza0b9sfvx9jNY3F377sRoRXmYisVKZ8aRRyUXeta7SDhoRRF6HIEjlbeoOhiEd9nXR/+/LXzrEMh\nRBT25k6a5y4Den0JsrMP3XZnENGhOwOh9yd3m05twrrj63Ai4QR6evRkHQ5RATlV5VTEk5gouROx\nLDUsxdmas/j4sY/h4kS9jcR+9jwtSUz25k4aUCWqsD5yPZw1znj24LOsQyEKp5Y1CJTciSq4OLkg\nb2YeDv/rMN75+zuiHqtEr0caxyEjPBxpHIcSvV7U4xFpqWUNAt2/EtXo7t4d++P3Y9y743B377sx\ncdBEwY9BD9JQP7WsQWDWclfrEnnCll8vP+TOyMWjex7F199/Lfj+1XLLTsxTyxoEJi13NS+RVxsl\nVsScOGgiMsIzEJMbg9KEUvRw7yHYvtVyy07MU8saBCbJ3fwS+XTZJw5HouSL8IKgBThbcxZxu+Og\ne1Qn2AwatdyyC0lO0waFooaqnEy6ZdS+RF4tlF6n5nXudRh5I54/9Lxg+1TLLbtQmsYgXi4sREZx\nMV4uLMTBJUtokFkGmLTcHWWJvNJdufKLyde/++5niSOxj4uTC3bN3IUxm8dguNdwJN6b2OF9quWW\nXSjmxiDSs7Md9pzIBZPknpwcicrK1BatwlvFuKJYhGMVJfY9d9R3331n8vUrV65IHIl9mv5m3Z0i\n8cyVpbj2z1/xYlyyxfdY08Wghlt2odAYhHy1m9wNBgOWLl0Ko9GIxMREvPDCCya3O3nyJEJCQrBr\n1y5Mnz7d4j7FLsYlNCX3PXdEv3498N//pgK4vWsmBX37dmcVktXa/M3+GYs04zR4deqDhOlxJt9D\n0xxtR2MQMmap8ExDQwOv1Wr5ixcv8jdv3uQDAwP5iooKk9tNmDCBj46O5nfv3i1o8Rs5GD06gQdS\neWD5b/8t5gGe57g01qGJKjKy6d+a9tu/PY0HihXx774VO9/y6/5svvOfPPn/1f7P5HtSIyP5tm8C\nn8ZxEkevHMU6HZ+i1bY4Xy9ptXyxTsc6NNWwN3dabLmXl5fDz88PAwcOBADExcUhPz8f/v7+LbbL\nzs7GzJkzcfLkScEvPqy7Q/T6Epw75wrg5dtevdVqV/sA8K3us4OK6j5rYnLQvvwZdAvcivg98SiI\nK4CzU8u/H3Ux2I7GIOTLYnKvrq6Gr69v888+Pj4oKytrs01+fj6OHDmCkydPQqPRCBacHLpDsrIK\nUVv7dqtXVwNIhxrvPFtfTP/wB2+cOKGM7rPbmR601+CeqgjUNpThhcMvYH3k+ha/pS4G+9AYhDxZ\nTO7WJOqlS5dizZo1zZXLeAvVyzIyMpq/Dw8PR3h4uMV9y2E+vLlpm+7u32Lx4gRJYpCKuYtpZian\niIR+O3OD9ksWRSFk4h8RvCkYw72GY97oec2/j0xORmplZYs+9xStMp/RSpSrqKgIRUVFHd6PxeTu\n7e2Nqqqq5p+rqqrg4+PTYpvPPvsMcXG3BqiuXbuGjz/+GK6uroiNjW2zv9uTuzXkMB/e3LTNgIAu\nikt47ZHDxVQo7Q3aF8QVIOy9MAzpPQQP3PkAANu6GNS4cIfIQ+uG74oVK+zbkaUO+fr6en7w4MH8\nxYsX+bq6OrMDqk3mzp3L79mzR7BBAZODYhIPZDrSk43CwpabPN9hYctZhyaKjy98zPdb34+/+MNF\nm95nahAxhQYRiUjsyZ08386AqouLCzZs2ACO42A0GpGQkAB/f3/k5OQAAJKSkuy7olhJDvPhxZi2\nKeYgcUf27WiLy6L8ovDiuBcRkxuD408eR1e3rla9jxbuEEUQ+CJjlr2H0uluTb0LC1vOc1ya4lvM\npu8EUgT5d3V03450l9KksbGRn18wn4/ZEcM3GBuses/ysDCTUyaXh4WJGiu5ddeUGhnJLw8L41Mj\nIx3ibsne3Cn75K42YnY1CbFvtV1MrVHXUMeHbQnjXzj0glXb03x4Nhy1O8ze3EkP65CYmIPEQuw7\nOjpUcYOnHdXJuRN2z9qN4E3BCPAKwOOBj1vcnmbVsKHk7jAWA/CU3CUmZr+2o/WZC8nzDk8UxBVg\nwtYJ8Ovlh7G+Y81u60gLd+Q0K0ipi8yYlbUQ+A7CLAkPJVs6XTE/enQC7+6+QJR+bUfsMxea/p96\nvv/6/vw3179hHQpzcusGUWp3WEfjtjd3UstdIr8vENoEoAS3Vrh+i4CALli5crYgXSFKK8gmR5OG\nTMJzIc8hNjcWx548hi6durAOiRm5dYMotTuM1R0HJXeJtFwgFAogFLW1gJeXsAuEHLHPXGjLQpbh\nbM1ZzNk7B3tm7YGThtmjhpmSWzeIUrvDWJW1oOQuETmstiXW0Wg0eDv6bTz0wUNIP5qO1RNXt/8m\nFZJjrR0l1rFhdcdByV0iNNipLG4ubvho1ke4f9P9GO41HI+OeJR1SJJTajeI3LC649D81mEvuqbC\nYo7KVFFNsKuXAAATlklEQVQurTYFmZnUJy5nX179Eg++/yD2x+9HsE8w63AkV6LX49BtSSlCAd0g\namNv7qTkLiG9vgTZ2YduG+yMoMSuAPvP78cC/QKcSDgB3+6+7b+BEAFRcidERGs/XYudX+3E3+b9\nDZ07dWYdDnEglNwJERHP85ibPxe/3PwFux7Z5bAzaIj07M2d9AklxAoajQY5k3Pw3U/fYUWxnfW1\nCZEQJXdCrOTu4o69s/di6xdbkfdVHutwCLGIkjshNujbpS/y4/Kx6ONFOFkt/APhCREKJXdCbBTY\nLxAbJ2/EtLxpqP6xmnU4hJhEA6qE2OmVv72Cvf/Yi+K5xbjD9Y7m1+VUSZEon725k1aoEmKnlx54\nCRU1FXgy/0nkzsiFRqNhV96VqEbrxoG9qOVOSAfUNtQi7L0wTB4yGelh6UjjOLxcWNhmu3SOwyqD\ngUGERElMNQ40ALXcCZGau4s79s3e1/wUJ7lVUiTKYqrMsr1oQJWQDurftT/2xe3DAv0CVPUyndxZ\nVlIkymGucWAPSu6ECODe/vfineh3oLuvEkvuuavF71K0WkSIUEmxRK9HGschIzwcaRyHEr1e8GMQ\naXWkj7016pYhRCAzAmagoqYCua7b8OKRh+D+a71o5V1p4FadTJVZthcNqBJZ0utLkJVViLo6F7i5\nNSA5OVIRFTR5nkf8nng4Ozlj27Rt0Gg0ohyHBm7Vq3WZ5ZcPHqQBVaIOpmrfV1amAoDdCV6qi4VG\no8GWKVsQ+l4o/nLsL0gZn2LzPqyZJ08Dt+rV+mlTL9vZQKDkTmSn5fNmb6msXI3sbPueNyvGxcIS\nD1cP5MflI3hTMPw9/THNf5rV77W2u0WOj8Aj8kIDqiql15eA49IQHp4BjkuDXl/COiSrCf28WfMX\ni0N27c8aA7oOwN7Ze/GU7il88e8vrH6fqalwqysrcSg7u8VrkcnJSNVqW7wm1sAtUSZquauQ1C1V\noQn9vFlWDycPGhCEDQ9vwNSdU1GWWIa+Xfq2+x5ru1tYPZeTKAcldxUSulvDEjH6spOTI1FZmdrm\nebOLF0fZtT+WDyeffc9sVFyrwLS8aTjyxBG4u1juNrGlu6V13ywht6PkrkJStVTN3SGcPPkVSku/\nszvhN22bnZ1+2/Nm7X+QuNAXC1stD1uOipoKPLX/KWydutXiDBpTU+FStFpEUXcLsREldxWSqqVq\n7g5h7drZuHEj77bXbO8Sio4OFewuQ+iLha2cNE7YOnUrxm8Zj3XH1+FP4/5kdlvqbiGC4SUi4aEc\nnk5XzGu1KTzAN39ptS/xOl2xoMcJC1ve4hi/f7V9nePSBD22ElX9r4of8NoAPv8f+axDIQpib+6k\nlrsKSdVSNXeHALS9QxB78FIJfLr54KNZHyEmNwafPP4JRvQdwTokomKU3FVKyG4Nc0z1ZXt4JOHG\njcfabNu6S0ipK1A7KtgnGG9EvYHYnbEoSyxDn859WIdEVIqSu8pImTRN3SGMGROIbdsOorLy92O2\nHrxU+lTNjnp0xKOoqKnAjF0zcHjOYbi5CFcsipAmVFtGRUwlTa02FZmZnKRJU68vQXb2odu6hCJa\nHJ/j0lBY+HKb93FcOgyGVZLFyVIj34iZu2aih3sPbI7dLFoNGqJ89uZOq1aoGgwGDBs2DEOGDMGr\nr77a5vfbt29HYGAgRo4ciXHjxuHMmTM2B0I6jsVKTFOio0NhMKxCUVEGDIZVbS4srBYVyYmTxgnv\nT3sfp66cwv+V/h/rcIgKtZvcjUYjFi1aBIPBgIqKCuTm5uLcuXMtthk8eDBKSkpw5swZpKen46mn\nnhItYGKeUpImy0VFctKlUxcUxBfgtdLXoP8n1WInwmo3uZeXl8PPzw8DBw6Eq6sr4uLikJ+f32Kb\nkJAQdO/eHQAQHByMy5cvixMtsUgpSTM5ORJabWqL1271y0cwioidO7vfiT2z9mBe/jyc/c9Z1uEQ\nFWl3QLW6uhq+vr7NP/v4+KCsrMzs9ps3b8akSZNM/i4jI6P5+/DwcISHh1sfKWkX65WY1mK9qEhu\nQnxD8Frka80zaDzv8GQdEmGoqKgIRUVFHd5PuwOqe/bsgcFgwF//+lcAwLZt21BWVobsVlXqAODo\n0aN45pln8Omnn6Jnz54tD0QDqpJobzCTyNeLh19E6eVSHJpzCJ2cO7EOh8iEvbmz3Za7t7c3qqqq\nmn+uqqqCj49Pm+3OnDmD+fPnw2AwtEnsRDpSzG8n4njlwVcwdedUPHPgGWycvJFm0JAOabfPPSgo\nCBcuXMClS5dw8+ZN5OXlITY2tsU23377LaZPn45t27bBz89PtGAJUTMnjRO2T9+OsstlyCrLYh0O\nUbh2W+4uLi7YsGEDOI6D0WhEQkIC/P39kZOTAwBISkrCypUr8cMPP2DhwoUAAFdXV5SXl4sbOSEq\n1NWtKwriCxCyOQRDPYciyk9e4yVEOWgREyEydOzbY5ieNx3Fc4vh7+XPOhxFsuZZtEogWp87kR9H\nrcviSB648wGsjViLmNwYlCWWofcdvVmHpCjWPotWzajlrjByKTFApPHHwj/i839/DsNjBrg6u7IO\nRzHSOA4vFxa2eT2d47DKYGAQkf1ELT9A5EMuJQaI7ex5aPmrD70KDxcPJBuSqXFkA2ufRatm1C2j\nMEopMcCaPV1XYnZ32VsJ09nJGTtm7MDYzWPx5sk3sej+RYLEo3a2PItWrRwuuSu9v1opJQZYsieR\nCl2GuPXnrKbm36is3NRiG2sfWt7NrRsK4gswdvNYDO09FBFaxyvTYCt6Fi3YPWZPpyvmIyNT+bCw\n5XxkZKrgj4AzxfTj51IkObZQpHqEnpJFRqaafPyfpUf92fMec0z9jdzdF/BAcZv9h4Utt3q/RReL\n+D7r+vDnr523OSZHVKzT8Wkcxy8PC+PTOI4v1ulYh2QXe9M0k5Y7q4c1mO+vbr/1JBdUl6V99nRd\nCdndZepzVlv7NoB0AC3/TrbccYUNDMPqiasRkxuDEwkn0NODVoJbEhod7TAzY0xhktxZJVm19Fer\nucSAEN1m9nRdCdndZe5z5u7+LW4fz7OnqFvivYk4W3MWs3bPwoFHD9AMGmIWk+TOKslSf7W8CXVH\nZ091TCErapr7nAUEdIGXV8fvuNZFrENMbgyWFS5D9sNtC/gRAjBK7qySrFJK4opNroPKQt3R2dN1\nJWR3l7nP2cqVswU5zy5OLtg5YyfGbB6Dd/7+DhYELejwPon6MEnurJIs9VfL++HUQt7R2dN1JVR3\nlxSfs+7u3bE/fj8eePcB3N37bkwcNFGwfRN1YLZCleqOsyHnh1PLOTa5OnrxKOL2xOHYvGMY0nsI\n63Acnhj1bBRXW0bNg4JyJudBZeo2s92EQROwMnwlYnfGojShFD3ce7AOyWHJrZ6Nwy1icnRyHlSm\nbjP7JAUl4auarxC3Ow66R3VwcaL/rYVkbWu8MCurRWIHgNWVlUjPzqbkTsQn99Yx3dHZ53XudUza\nPgl/LPwj3oh6g3U4qmFLa1xu9WwouTsYah2rk4uTC/Jm5mHM5jEY/tlwzP9/81mHpAq2tMblVs+G\nkrsDotaxOvX06In98fsxfst43N37boQNDGMdkuLZ0hqXWz0bSu6EqMjdve/G9unbMXv3bBxPOI7B\nPQezDknRbGmNN7Xk07Oz4VxbC6O7O6IWL2ZWAoEe1kGICr1Z/ibe+vtbKE0oRTe3bqzDUSxTfe4p\nWi2iMjMlS9r25k5K7oSo1NP6p/HN/75BQVwBnJ3YT3VVqhK9Hodua41HSNwap+ROCGmh3liPqO1R\nGN1vNNZHrmcdjmzJ/UHailvERAgRl6uzKz585EMEbwrGcK/hmDd6HuuQZEduC4+ERC13QmRAzGJu\n/7j2D4zJCcHdn8fgjmuDZVUsjjUlPEibWu6EKJTYxdwqy/6DOwxROBl8CPikFLg+kEmxODl2f8ht\n4ZGQKLkTwpjYD6/JyirElWO5QH0mEB8DbD4u+RPI5Nr9IbeFR0JyYh0AIY5OzGJuen0JTp6suvVD\nWTJwOQSY8RigMUpaLM7cSs9D2WwfNhKZnIxUrbbFaylaLSJU8CBtarkTwphYxdyaunt++MH3t1c0\nwIENwJxI4MEUuDt36tD+bSHX7o/WC49qfvoJdTyPI+vWoTArSxZdR/ai5E4IY2IVc/u9u6cEQCqA\n1YCxE5C3By5P+yFgxNMd2r8t5Nz90fQgbbl2HdmLkjshjIlVzO337p6m/aQDcEZP9/N4ecwbyLj4\nPGZWRWOs79gOHceSpkHUmupqLPDwwDs3bjT/jmXdFVPkVrK3oyi5EyIDYhRza9ndE4qmJH///el4\neuYTGHjBCzN3zURpQinu6nGXoMcG2g6ilgCY7eGBAX5+6DJgANO6K6bItevIXjSgKnN6fQk4Lg3h\n4RnguDTo9SWsQyIKkZwcCa02tcVrt7p7IgAAk4ZMwh/H/hGxO2Px882fBT9+65ZwKIC8GzfQZcAA\nrDIYZJXYAXl3HdmDWu4yJueHWRP5s6a759kxz+JszVnM2TsHe2btgZNGuPae0lrCcivZ21G0QlXG\n6IHRRAp1DXV46IOHEHpXKFZPXN3+G6ykhNWfrbEuEmYKrVBVITk/zJqoh5uLGz6a9RGCNwUjwDMA\nj418TJD9KrEl3DRzRg0oucuYnB9mTdTFq7MXCuILMHHrRPj18kOwT3CH9ym3h1c4HL4dH3/8MT90\n6FDez8+PX7NmjcltFi9ezPv5+fEjR47kT506ZXIbKw7lMI4ePWrVdjpdMa/VpvAA3/yl1b7E63TF\n4gYoIWvPhSOQw7ko+EcBP+C1Afy3179lGocczoVc2Js7LY6eGI1GLFq0CAaDARUVFcjNzcW5c+da\nbHPgwAF8/fXXuHDhAjZu3IiFCxeKeClSh6KiIqu2i44ORWYmB45LR1hYBjguHZmZ6nqYtbXnwhHI\n4VzEDI3BkuAlmLJzCn65+QuzOORwLpTOYrdMeXk5/Pz8MHDgQABAXFwc8vPz4e/v37xNQUEBnnji\nCQBAcHAwrl+/jqtXr6Jv377iRe1A6GHWRGrPj30eZ2vO4ol9T2DXI7sEnUFDpGPxr1ZdXQ1fX9/m\nn318fFBdXd3uNpcvXxY4TEKIVDQaDTZO3ogrP1/B6hLhZs8QaVlsuWs0Gqt2wreapmPufdbuzxGs\nWLGCdQiyQefid3I7F8dxHH/Gn5kcW27nQmksJndvb29UVVU1/1xVVQUfHx+L21y+fBne3t5t9tX6\nAkAIIUQ8FrtlgoKCcOHCBVy6dAk3b95EXl4eYmNjW2wTGxuL999/HwBw4sQJ9OjRg/rbCSGEMYst\ndxcXF2zYsAEcx8FoNCIhIQH+/v7IyckBACQlJWHSpEk4cOAA/Pz80LlzZ2zZskWSwAkhhFgg6IRM\nXrh58WrQ3rnYtm0bP3LkSH7EiBH82LFj+dOnTzOIUhrWfC54nufLy8t5Z2dnfs+ePRJGJx1rzsPR\no0f5UaNG8cOHD+fDwsKkDVBC7Z2LmpoanuM4PjAwkB8+fDi/ZcsW6YOUyLx58/g+ffrw99xzj9lt\nbM2bgib3hoYGXqvV8hcvXuRv3rzJBwYG8hUVFS220ev1/MMPP8zzPM+fOHGCDw4OFjIE2bDmXBw/\nfpy/fv06z/O3PuiOfC6atpswYQIfHR3N7969m0Gk4rLmPPzwww98QEAAX1VVxfP8rQSnRtaci+XL\nl/Mvvvgiz/O3zkOvXr34+vp6FuGKrqSkhD916pTZ5G5P3hR0Auvt8+JdXV2b58Xfzty8eLWx5lyE\nhISge/fuAG6dC7VOIbXmXABAdnY2Zs6cCS8vLwZRis+a87Bjxw7MmDGjeeKCp6cni1BFZ8256N+/\nP3788UcAwI8//ojevXvDxUWdFVPGjx+Pnj17mv29PXlT0ORO8+J/Z825uN3mzZsxadIkKUKTnLWf\ni/z8/OYVzmqcNmvNebhw4QK+//57TJgwAUFBQfjggw+kDlMS1pyL+fPn4+zZsxgwYAACAwORmZkp\ndZiyYU/eFPQyKPS8eCWz5d909OhRvPvuu/j0009FjIgda87F0qVLsWbNmubypq0/I2pgzXmor6/H\nqVOn8Mknn+DXX39FSEgIxowZgyFDhkgQoXSsORevvPIKRo0ahaKiIlRWViIiIgKnT59G165dJYhQ\nfmzNm4ImdyHnxSudNecCAM6cOYP58+fDYDBYvC1TMmvOxWeffYa4uDgAwLVr1/Dxxx/D1dW1zdRb\nJbPmPPj6+sLT0xMeHh7w8PBAaGgoTp8+rbrkbs25OH78OFJTbz2cRqvVYtCgQTh//jyCgoIkjVUO\n7Mqbgo0I8DxfX1/PDx48mL948SJfV1fX7oBqaWmpagcRrTkX33zzDa/VavnS0lJGUUrDmnNxu7lz\n56pytow15+HcuXP8gw8+yDc0NPC//PILf8899/Bnz55lFLF4rDkXzz77LJ+RkcHzPM//+9//5r29\nvfn//ve/LMKVxMWLF60aULU2bwracqd58b+z5lysXLkSP/zwQ3M/s6urK8rLy1mGLQprzoUjsOY8\nDBs2DFFRURg5ciScnJwwf/58BAQEMI5ceNaci5SUFMybNw+BgYFobGzE2rVr0atXL8aRiyM+Ph7F\nxcW4du0afH19sWLFCtTX1wOwP29K9pg9Qggh0qFanoQQokKU3AkhRIUouRNCiApRcieEEBWi5E4I\nISpEyZ0QQlTo/wOzmpxO7USaaQAAAABJRU5ErkJggg==\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plotting the learned decision boundary\n",
    "cla()\n",
    "d0 = data[labels==False]\n",
    "d1 = data[labels]\n",
    "xlim((0,1)); ylim((0,1))\n",
    "plot(d0[:,0],d0[:,1],\"bo\")\n",
    "plot(d1[:,0],d1[:,1],\"ro\")\n",
    "plot([0,-d/a0],[-d/a1,0],\"g\")\n",
    "savefig(\"tmp.png\")\n",
    "print len(d0),len(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e86e70bd",
   "metadata": {},
   "source": [
    "(Open Questions)\n",
    "\n",
    "That has worked rather well, but it leaves open a number of questions:a\n",
    "\n",
    "- Is the algorithm guaranteed to stop?\n",
    "- How do we deal with more than two classes?\n",
    "- What is the error rate?\n",
    "- How does it relate to the c.c.d. $p(x|c)$?\n",
    "- What happens when the data isn't linearly separable?\n",
    "- It's fairly easy to show that the algorithm converges if the data is linearly separable. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ce42919",
   "metadata": {},
   "source": [
    "# Criterion Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ec59845",
   "metadata": {},
   "source": [
    "(Separating Plane via Criterion Function)\n",
    "\n",
    "Let's say we know the data is separable and we want to find a weight vector that separates the samples.  We can do this by defining an objective function $J(w)$ and then minimizing $J(w)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb0eb565",
   "metadata": {},
   "source": [
    "(Minimum Error Criterion Function)\n",
    "\n",
    "The obvious objective function to use is $J(w) = \\hbox{# misclassified samples}$.  That function is zero when $w$ separates the two classes, and positive otherwise.  Unfortunately, that is a stepwise constant function, which is hard to optimize."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "107c5dff",
   "metadata": {},
   "source": [
    "(Perceptron Criterion Function)\n",
    "\n",
    "\n",
    "A better function is to sum up the total amount by which samples on the wrong side of the decision boundary are misclassified.  This is zero when the data is separated, but positive if any samples are misclassified.  In formulas:\n",
    "\n",
    "$$J_p(w) = \\sum_{i\\in{\\cal E}_w} -w\\cdot x_i$$\n",
    "\n",
    "where\n",
    "\n",
    "$${\\cal E}_w = \\\\{ i | w \\cdot x \\lt 0\\\\}$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a7e3801",
   "metadata": {},
   "source": [
    "(Gradient Descent)\n",
    "\n",
    "We can optimize this function by gradient descent.  That is, we iteratively update the weight vector $w$ by adding a small multiple of the negative of the gradient $\\nabla J_p(w)$ to it.  What is the gradient?\n",
    "\n",
    "$$\\nabla J_p(w) = \\nabla \\sum_{i\\in{\\cal E}_w} -w\\cdot x_i = \\sum_{i\\in{\\cal E}_w} -x_i$$\n",
    "\n",
    "Therefore, our update rule becomes:\n",
    "\n",
    "$$ w \\leftarrow w + \\eta \\sum_{i\\in{\\cal E}_w} x_i$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e10ef3a5",
   "metadata": {},
   "source": [
    "(Batch vs Sample Correction)\n",
    "\n",
    "This is a batch update rule; that is, we add up all the gradients for each misclassified samples, and only then update the total weight vector. That is inefficient and turns out to be unnecessary in this case anyway.\n",
    "\n",
    "A stochastic gradient descent rule updates after every misclassified sample via\n",
    "\n",
    "$$ w \\leftarrow w + \\eta x_i $$\n",
    "\n",
    "In the case of perceptron learning, this is also called the single sample correction algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1e2eded",
   "metadata": {},
   "source": [
    "# Proof of Convergence"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b73d9a63",
   "metadata": {},
   "source": [
    "Let's consider a particularly simple case for the single sample correction perceptron learning algorithm: the case where $\\eta = 1$.  \n",
    "\n",
    "Proving convergence for that case shows that for any separable learning problem, there exists a known sequence of $\\eta$ (namely all 1s) that make perceptron learning converge.  We also assume that the training vectors are linearly independent."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bdab11a",
   "metadata": {},
   "source": [
    "Assume that we're updating the weight vector in a sequence of updates; we number the updates as $\\tau=1,2,...$ (we don't need to worry about the vectors that are classified correctly).  Let $\\hat{w}$ be a solution vector.  Consider now the distance of $w(\\tau+1)$ from some multiple of the solution vector (any such multiple is itself a solution):\n",
    "\n",
    "$$w(\\tau+1) - \\alpha \\hat{w} = (w(\\tau)-\\alpha \\hat{w}) + x_\\tau$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b97f7a3c",
   "metadata": {},
   "source": [
    "Now square both sides:\n",
    "\n",
    "$$||w(\\tau+1) - \\alpha \\hat{w}||^2 = ||(w(\\tau)-\\alpha \\hat{w}) + x_\\tau||^2 = ||w(\\tau)-\\alpha \\hat{w}||^2 - 2(w(\\tau)-\\alpha\\hat{w})\\cdot x_\\tau+||x_\\tau^2||$$\n",
    "\n",
    "$$ = ||w(\\tau)-\\alpha \\hat{w}||^2 - 2 w(\\tau)\\cdot x_\\tau - 2 \\alpha\\hat{w} \\cdot x_\\tau + ||x_\\tau^2||$$\n",
    "\n",
    "We know that $w(\\tau) \\cdot x_\\tau \\lt 0$ because it was misclassified, so\n",
    "\n",
    "$$||w(\\tau+1) - \\alpha \\hat{w}||^2 \\leq ||w(\\tau)-\\alpha \\hat{w}||^2 - 2 \\alpha\\hat{w} \\cdot x_\\tau + ||x_\\tau^2||$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "964e2f78",
   "metadata": {},
   "source": [
    "We also know that $\\hat{w}\\cdot x_\\tau>0$ (because $\\hat{w}$) is a solution.  \n",
    "\n",
    "So, we can choose some $\\alpha$ such that we get a provable reduction in the distance of the weight vector from the true vector.  To choose that, let's bound $||x_\\tau^2|| and $\\hat{w}\\cdot x_\\tau$ above and below, respectively.\n",
    "\n",
    "$$ \\beta^2 = \\max_i ||x_i||^2$$\n",
    "\n",
    "$$ \\gamma = \\min_i \\hat{w} \\cdot x_i $$\n",
    "\n",
    "(This is greater than zero for all vectors.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98e091a0",
   "metadata": {},
   "source": [
    "Now:\n",
    "\n",
    "$$||w(\\tau+1f) - \\alpha \\hat{w}||^2 \\leq ||w(\\tau)-\\alpha \\hat{w}||^2 - 2 \\alpha\\gamma + \\beta^2$$\n",
    "\n",
    "If we choose $\\alpha = \\frac{\\beta^2}{\\gamma}$, then\n",
    "\n",
    "$$||w(\\tau+1) - \\alpha \\hat{w}||^2 \\leq ||w(\\tau)-\\alpha \\hat{w}||^2 - \\beta^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a50e45ce",
   "metadata": {},
   "source": [
    "This means that after $k$ steps, we have a reduction by $k\\beta^2$ in the error.  Since the distance can't become negative, we have a bound on the number of corrections of:\n",
    "\n",
    "$$\\hat{k} = \\frac{||w(1) - \\alpha \\hat{w}||^2}{\\beta^2}$$\n",
    "\n",
    "Let's pick $w(1)=0$, then we get:\n",
    "\n",
    "$$\\hat{k} = \\frac{\\alpha^2 ||\\hat{w}||^2}{\\beta^2} = \\frac{\\beta^2 ||\\hat{w}||}{\\gamma^2} = \\frac{\\max_i ||x_i||^2 ||\\hat{w}||^2}{(\\min_i \\hat{w}\\cdot x_i)^2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9424b5cd",
   "metadata": {},
   "source": [
    "Non-Separable Case\n",
    "===================\n",
    "\n",
    "If classes are not separable, things get more difficult.  In fact, it's not even clear what kind of solution we are looking for in that case.\n",
    "\n",
    "The most obvious solution we might want, the solution that has the minimum number of samples \"on the wrong side\" of the decision boundary is computationally hard to find.\n",
    "\n",
    "There are, however, other kinds of criteria we might apply:\n",
    "\n",
    "- Minimize the perceptron criterion function.\n",
    "- Find a good \"least square approximation\", that is, try to minimize $\\sum_i |a\\cdot x_i - c_i|^2$ (note that we cannot use the sign flip in this case).\n",
    "- Find a good \"least square approximation\", for some other objective function, as in $\\sum_i f(a \\cdot x_i - c_i)$ (note that we cannot use the sign flip in this case).\n",
    "\n",
    "Multi-Class Case\n",
    "=================\n",
    "\n",
    "There are several different approaches we can take to the multiclass case:\n",
    "\n",
    "- We can transform the classification problem into $n$ 1-vs-rest problems; then, we get $n$ linear functions $g_c(x) = a_c \\cdot x$.  We can treat these functions as discriminant functions and use the decision rule $D(x) = \\arg\\max_c g_c(x) = \\arg\\max_i a_i \\cdot x$.\n",
    "- We can train $n \\choose 2$ different dichotomies for classes.  These dichotomies are not going to be entirely consistent, but we can treat them as a corrupted binary vector of the true dichotomies and perform \"error correction\".\n",
    "- We can encode the the $n \\choose 2$ dichotomies in a single binary classification problem via Kessler's construction.  That is, let $a = (a_1,...,a_M)$.  we write down for each input vector $x_i$ a series of outputs of different classification problems (Kessler's construction.  This is another way of expressing the previous approach.\n",
    "- We can consider the classifier as a map from $R^n \\rightarrow \\{0,1\\}^M$, where the output vectors are binary vectors of the special form $y_i = (\\delta_{1,c_i},...,\\delta_{M,c_i})$ (i.e., all zero except for a 1 in position $c$).  Then, we minimize $e = \\sum_i |A \\cdot x_i - y_i|^2$.\n",
    "- We can consider any sufficiently large and complete collection of binary classifiers on the original data (these might include training, say, {8,9,0} vs the rest); this collection then gives us as output a binary vector of classification results.  Instead of trying to write rules manually for mapping these binary vectors into output classes, we can simply use them as input vectors for another classifier.  This is called stacking of classifiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "756215e7",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}