{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8c9b35de",
   "metadata": {},
   "source": [
    "Title: Perceptrons\n",
    "Author: Thomas Breuel\n",
    "Institution: UniKL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "125054ea",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\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": "d3043a99",
   "metadata": {},
   "source": [
    "# Linear Classification Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15f4a222",
   "metadata": {},
   "source": [
    "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "62465467",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "53"
      ]
     },
     "execution_count": 2,
     "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": 6,
   "id": "bad1ec9e",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "47 53\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAT8AAAE1CAYAAACRPefNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3V1sVNe5N/C/gxHQKGogpFFi+xVh28VOCCZHcAitgodG\nnu3iyL1ILpz3tG9CqcvJKTbpXeOxhSmBQu7McI5CpIQqaYOoyIXTGZjapIytBLCjEIEaUORYJMf4\nqFFpQckpwtiT9V44GI89H3v27I+19vr/JAtmvL1n7e3xM2utZ32UCCEEiIg0c4ffBSAi8gODHxFp\nicGPiLTE4EdEWmLwIyItMfgRkZbyBr+f/vSnuO+++/DII49kPaatrQ1VVVWora3FRx995GgBiYjc\nkDf4bd68GYlEIuv3jx07hk8//RTDw8N49dVX8fzzzztaQCIiN+QNfo8//jgWL16c9fvvvPMOnn32\nWQDAunXrcO3aNXzxxRfOlZCIyAVF9/mNjY2hoqJi+nF5eTkuX75c7GmJiFxV6sRJZs+QKykpmXNM\npueIiJxgZ5Zu0TW/srIyjI6OTj++fPkyysrKMh4rhAjs144dO3wvg2zXFwmHIYA5Xx2m6fv18HcX\nnC+7ig5+TU1NeOONNwAAZ86cwd1334377ruv2NNSAJSOj2d8ft6NGx6XhGiuvM3eZ555Bv39/bhy\n5QoqKiqwc+dOTExMAAC2bt2KTZs24dixY6isrMSdd96JQ4cOuV5oUsPkggUZn08tXOhxSYjmyhv8\nDh8+nPckBw4ccKQwKguFQn4XwVV2ri/c1obIyAh2j4xMP9duGGhobXWwZMXj705PJaKYRnMhL1RS\nUlT7nNQ0EI+jLxrFvBs3kFq4EPWtrdjQ2Oh3sShA7MYWBj8iUprd2MK5vUSkJUfG+ZHeBuJx9O7f\nj9LxcUwuWIBwWxubti7Q6T57ca0MflSUgXgcf9q+PS2pEfnm/278YeoUAGby+j77ybNrFR7x8KUc\nEYv1i3A4IurqdohwOCJisX6/iySlSDgsBDDnq8M0HX+t/lhMtBtG2uu0G4boj8Ucfy3ZeHmf/Vbo\ntdqNLaz5ZRCPD2D79j9hZGT39HMjIxEAQGPjBr+KJSUvBzL37t+fVhsAgN0jI+iMRgNX+5lNpwHj\nXl0rEx4Z7N/fmxb4AGBkZDei0T6fSiQvLwcy6xQAZtNpwLhX18rgl8H4eOYK8Y0b8zwuifzCbW2I\nGEbac+2GgXoXBjLrFABm8/I++82ra2WzN4MFCyYzPr9wYcrjkjjP6YTBrZ/tnDGQucGlgcyqzBhx\ng5f32W9eXSsHOWeQqc/PMNrR3d2gdJ9fxiyaYcDs7lbmj4gzRmg2zvBwWDw+gGi0DzduzMPChSm0\nttYrHfiAqaWkXurtnfN8p2liV46tCohkZje2sNmbRWPjBuWD3Ww6JwyIZmPCQyM6JwyIZmPw04hO\nGUOifNjnpxkmDChomPAgIi0plfCIxwewf38vxsdLsWDBJNrawoFLLhCR3DwPfpw3qx9dV2IhuXke\n/LLPm+1k8AsgnZZiIrV4nu3lvFm9ZFuJpS8a9alERFM8r/kFed4szWV3YDWbyu7T/R57Hvza2sIY\nGYnMmTfb2trgdVHIA3YGVrOp7D7eY/izknMs1i9Ms0PU1e0QptnBVZIDLNPqyy/mWX1Zp1WL/RKk\ne2w3jPky1CWI82YpMzvLE3EOsvt4j7mwAXlgQ2NjQU0pzkF2H+8x5/aShDgH2X28x5zeRpLiHGT3\nBeUec24vEWnJbmxhs5eItMTgR0RaYvAjIi1xqAtRAOg+Vc0OBj8ixXGqmj1s9hIpjivn2MPgR6Q4\nTlWzh8GPSHGcqmYPgx+R4jhVzR7O8CAKgKBMVbND2elt3MmNiIqh1NaVt3AnNyLyi699ftl3cuvz\nqUREpAtfa37cyU1unDVAMnH6/ehr8ONObvLirAGSSa73o12+Nnvb2sIwjEjac1M7udX7VCK6hbMG\nyI6BeBwdpomuUAgdpomBeNyR87rxfvS15ncrqRGNduLGjXlYuDCF1tYGJjskIOusATbF5eVma8GN\n96PvCxtwJzc5yThrgE1xuWWrnXVGo0X/ftx4P+Zt9iYSCVRXV6Oqqgr79u2b8/0rV66goaEBq1ev\nxsqVK/Hb3/7WdmFIHjLOGmBTXG5uthbceD/mrPmlUils27YNJ06cQFlZGdauXYumpibU1NRMH3Pg\nwAE8+uij+M1vfoMrV65gxYoV+PGPf4zSUt8rlVQEO/vtuk3WpjhNcbO14Mb7MWeEGhoaQmVlJZYt\nWwYAaG5uRk9PT1rwu//++3H+/HkAwJdffol77rmHgS8gCt1v120yNsXptnBbGyIjI2m183bDQIND\nrQWn3485o9TY2BgqKiqmH5eXl2NwcDDtmJaWFvzgBz/AAw88gK+++gp/+MMfHCsc0Uxu/3FRcWRs\nLeSSM/iVlJTkPcGePXuwevVqJJNJjIyMoL6+HufOncNdd90159iurq7p/4dCIYRCoYILTPpS7Y9L\nR160FpLJJJLJZNHnyRn8ysrKMDo6Ov14dHQU5eXlacecOnUKkcjUWD3DMPDggw/ik08+wZo1a+ac\nb2bwI7JDtqY4eW92xWnnzp22zpMz27tmzRoMDw/js88+w82bN3HkyBE0NTWlHVNdXY0TJ04AAL74\n4gt88sknWL58ua3CENFcbg0c1l3Oml9paSkOHDgA0zSRSqWwZcsW1NTU4ODBgwCArVu3or29HZs3\nb0ZtbS2+/vprvPzyy1iyZIknhScKOo5tdI/v6/kRuSUIs0E6TBMv9fbOeb7TNLErkfChRPJRcj0/\nIrcEpcbEsY3u4R4eFEhBmQ3CsY3uYfCjQApKjUnGaYZBwWYvBVJQakwc2+geJjw0FIREQD6Z+vza\nDQMN3d2Bu1bdMeFBlgQlEZCP6jUmHT6g/CZtzY9bWrqDQyfkl/EDyjBgstaaUaBqftzS0j1BSQQE\nmZuLgtJtUmZ7uaWle4KSCAgyfkB5Q8rgxy0t3cOhE/LjB5Q3pGz2cktL96ieCNAB1y30hpQJj0x9\nfobRju5u7uxGehiIx9E34wOqnh9QWdlNeEgZ/ICpABiN9s3Y0rKegY+I5ghc8CMissJubJEy4UFE\n5DYGPyLSEoMfEWmJwY+ItMTgR0RaYvAjIi0x+BGRlhj8iEhLUs7tpdy41iFR8Rj8FMO1DomcwWav\nYrjWIZEzGPwUw7UOiZzBZq9iuNahnLjhkHoY/BTT1hbGyEhkzlqHra0NPpZKb7rsiBc0Si5ppXu2\nk2sdFs/Jmhp3xPOXcru32Q1gzHZOXacu1+oGp2tq3HBIUcIjM18qFusXhtEuADH9ZRjtIhbrz3ue\ncDiS9nO3vkyzw83iU4BEwuG5byBAdJhmQefpj8VEJBwW/2/xYhEBRH+R5yN77IYxX2p+2YdrdOat\n0TDbScVyoqaWsfb4zb8bwA2HVOBL8CsmgDHbScVyYmvIjBuLA3hm8WL0/eu/ckc8B7idQfcl+BUT\nwJjt1Idbb34ntobMVntcsWoVupjkKJoXGXRfgl8xAexWszga7ZyR7eSWlkHj5ps/297FwFTm1kqw\n5cbi7spYsx4ZQWc06lztz+G+x6xmv1Qs1i9Ms0PU1e0QptlhKdlB+nAqKWFVfywm2g0j7bXaDUP0\nx2KWj38xx/FUmB11dRl//zvq6uYcazeM+TbUhcM1KBevh48UWtPIVntkP58zvKhZc4YHScnrZqWd\nYLuhsdH1YKfrtDkn+mXzYfAjKXnx5p9Jxj48nafNeVGzVnJ6G+lhIB5H34w3f72LzcpMgabdMNDQ\n3e1boOG0OWuUm95GcpGxeeVFs3LmawFy9eFx2py7GPxI6+bVTF4GWytkbIoHCRczpayZzr5o1KcS\nEfBNv6dhpD3Xbhio57Q5R7DmR2xeQd5mPyBXUzxIGPxcotKag7o3r2Ru9svWFA+SwAc/K0HI6UCl\n2pqDXg8rkY0nU6lIOoEOflaCkBuBqpglu/yge/OKzX495U14JBIJVFdXo6qqCvv27ct4TDKZxKOP\nPoqVK1ciFAo5XUbbrGzz6MZWkCquObihsRG7Egl0JZPYlUhoE/gANvt1lTP4pVIpbNu2DYlEAhcu\nXMDhw4dx8eLFtGOuXbuGX/ziF/jjH/+Iv/zlLzh69KirBS6ElSDkRqDimoNqYVZVTzmbvUNDQ6is\nrMSyZcsAAM3Nzejp6UFNTc30MW+99RaeeuoplJeXAwCWLl3qXmkLZCUIuRGouOagWnRv9usqZ/Ab\nGxtDRUXF9OPy8nIMDg6mHTM8PIyJiQls3LgRX331FbZv346f/OQnGc/X1dU1/f9QKOR6E9lKEHIj\nUHHNQfUwq6qOZDKJZDJZ9HlyBr+SkpK8J5iYmMDZs2fx7rvv4vr161i/fj0ee+wxVFVVzTl2ZvDz\ngpUg5Fag4pJdRM4biMdxYtZ4zJ02z5Uz+JWVlWF0dHT68ejo6HTz9paKigosXboUixYtwqJFi7Bh\nwwacO3cuY/Dzg5UgxEBFJL9c4zHtyJnwWLNmDYaHh/HZZ5/h5s2bOHLkCJqamtKO+dGPfoT33nsP\nqVQK169fx+DgIB566CHbBSIiyiTbeEy7ctb8SktLceDAAZimiVQqhS1btqCmpgYHDx4EAGzduhXV\n1dVoaGjAqlWrcMcdd6ClpYXBj4gcl208pl1cz4+IlJBtfcMSwFZs4aouRKSEbOMx7dK25qfSwgNE\nNCXT6t51Tz5pK7ZoGfwyzec1jAi6u00GQCLF2I0tWjZ73ZjPS0RqCfSqLtmouPBAEMi4YCjpS8vg\nx4UHvCfzgqGkJy2bvW1tYRhGJO25qfm89T6VKPi4TwjJRsuaHxce8B4XDCXZaBn8AM7n9RoXDCXZ\naBv8dCDTWEbd9wmh4riRLGPwCyjZNlHigqFkl1vJMi0HOevANDvQ2/tShuc7kUjs8qFERPZkm9Pb\naZrYlUhwkDOl41hGCgq3kmVs9gaUDGMZOaiZnOBWsozBL6D83kSJg5rJKW4ly9jnF2Dx+ACi0b4Z\nYxnrPUt25OunISpEptVcbn2I2o0trPkFmJ9jGTmomZzkxu56THiQKziomWTH4EeuyLbqbj0HNZMk\n2OdHrsnVT0PkFLuxhcGPKCB0HVrEhIdLZJofS5QNhxYVjsEvB9nmxxJlk229xM5olMEvCyY8cuBe\nH6QKDi0qHINfDpwfS6rg0KLCMfjl4Nb82Hh8AKbZgVCoC6bZgXh8oKjzEXFoUeHY55eDG/Nj2Y9I\nbuB6iYXjUJc8nJ4fq/M6e7oOxSB3caiLS5yeH6trPyKHYpBs2OfnMRnW2fMDt64k2TD4eUzXPYOD\nMhRjIB5Hh2miKxRCh2liIB73u0hkE5u9HtN1z+AgDMVg0z1YmPAgT2QKHO2GgYbubmUCBxdolRMT\nHiS1IAzFCErTnaYw+JFn3FiN10tBaLrTbVoHP67Y4rwg31O3NtIhf2gb/DjTwjqrAS3o9zQITXea\nQXjEw5eyJByOCEDM+TLNDr+LJpVYrF8YRnvaPTKMdhGL9c85lveU/GA3tmg7zk/XmRaFKmRZL9Xu\nKcfs6U3bZq+uMy0KVUhAU+me2h2zx/nJAeJwDTQrD1/KkszNuRczNud0VkhTVqV7GgmH514UIDpM\nM+vP9Mdiot0w0o5vNwzRH4t5WHKazW5s0bbmp+tMi0IVsqyXSvfUzpg9p5aKZ+1RDtoGP8D5FVuC\nqNCApso9tTNmz4lBzpwiVzjXPiwcroFm5eFLEeWVqQn7Yp4mrJ2mshvn0ImVrga7sUXrmh/py86Y\nPScGOXOKXGHc3JWOwY+0Veh0OycGOXOKXGHc/LBg8KNAcTuZUOz8ZE6RK4yrHxb52sXHjx8XK1as\nEJWVlWLv3r1ZjxsaGhLz5s0Tb7/9dsbvW3gpoqKoMhSlPxYTHaYpdtTViQ7TlK58MrHSN2s3tuRc\nzy+VSmHFihU4ceIEysrKsHbtWhw+fBg1NTVzjquvr8e3vvUtbN68GU899dScc3E9P3Jb0Nbb45CY\nKQPxOPpmdDXUz+pqcGU9v6GhIVRWVmLZsmUAgObmZvT09MwJftFoFE8//TQ++OCDggtA5JQgJRM4\nJOY2t5ZCyxn8xsbGUFFRMf24vLwcg4ODc47p6enBn//8Z3zwwQcoKSnJer6urq7p/4dCIYRCIXul\nJsogSMkEN7Ocqksmk0gmk0WfJ2fwyxXIbnnhhRewd+/e6apnrurnzOBH5LQgJRNkqcXK2PSeXXHa\nuXOnrfPkDH5lZWUYHR2dfjw6Oory8vK0Yz788EM0NzcDAK5cuYLjx49j/vz5aGpqslUgIruCtN6e\nDLXYwDe9c2VDJiYmxPLly8WlS5fE+Pi4qK2tFRcuXMh6/HPPPcdsL5ED7MxAcZoqs1HsxpacNb/S\n0lIcOHAApmkilUphy5YtqKmpwcGDBwEAW7du9SA8E+lHhlqsLE1vt3DrSs0EeY8NcpYqQ4e4dSXl\nFfQ9NshZQUogZcKan4tkq2WZZgd6e1/K8HwnEoldPpSIZJdvgLEMWPOTjIy1LNX22CD/qb7Xci7a\nbmDktkI2/vGKSntseIWbGOmLNT+XyFjLKmRJeh0Efhwb5cTg5xIZa1kq7bHhBZ2nkMk4c8NrDH4u\nkbWW5dQeG7Ilc+wI+ji2bFjjncLg55Ig17JkTObYIcMUMj/oXOOdicHPRarsZFao7MmcTqWuN+jj\n2LLRtcY7G4MfFUzGZI4dMkwh84OuNd7ZGPw0VUyfnYzJHLuCPI4tG11rvLMx+Gmo2D47WZM5ZI2u\nNd7ZOL1NQ05Mc4vHBxCN9s1I5tQr1d9HwcHpbWSZE312QU3mkD4Y/ALEaj9ekPrsiOxi8AuIQvrx\n2GdHxD6/wCi0H499dhQU7PPTXKH9eOyzI90x+AUE+/HUxoUGbvPqXjD4BQT78dTFhQZu8/JesM8v\nQNiPpyZVNgrygp17wT4/Yj+eorjQwG1e3gsuY0/kMy40cJuX94LBj8hn4bY2RAwj7bl2w0C9ZgsN\nAN7eC/b5EUlAhS0ivVLovbAbWxj8iEhpdmMLm71EpCUGPyLSEoe6SCIIu6ERqYTBz2fx+AA6O4/g\n4sX/xY0bFQB+AGBDzpWVGSiJisfg56Pby1D954xnp4Jett3QgrJtJJHfpO3zi8cHYJodCIW6YJod\niMcH/C6S4zJtAQnsBtAHIPOKLNm3jexzqZREwSRlzU+X2k22ZaiAqaCXaUWWoGwbSeQ3KWt+utRu\nsi1DBaS+WZGl3vLPcOkqosJIGfx0qd20tYVhGJG05xYu/Hf8y7/8Fd3dDRlruZl+JlugJKLspGz2\nTtVuBgD0YqqIkwDCgavd3Apu0WjnjGWo/m/Opn3mn8kcKIkoOymnt3V1/Rd27z6PyclXpp8rLf13\nRCKr0NX1H24VUVkc+kI6C9R6fqdP/09a4AOAyclXcOZMp08lkpcuySEip7HPT3G6JIeInCZl8GNG\n0zp+UBDZI2XwY0bTOn5QENkjZZ8fM5rWcdc2InukzPbKStasKndtI51xJWeXZcqqGkYE3d0mAw2R\njxj8XGaaHejtfSnD851IJHb5UCLKRdZaOjkvUOP8ZMSsqjo49pGssJTtTSQSqK6uRlVVFfbt2zfn\n+7///e9RW1uLVatW4fvf/z7Onz/veEH9xqyqOjj2kazIG/xSqRS2bduGRCKBCxcu4PDhw7h48WLa\nMcuXL8fAwADOnz+Pzs5O/PznP3etwH7h8Bt1sJZOVuRt9g4NDaGyshLLli0DADQ3N6Onpwc1NTXT\nx6xfv376/+vWrcPly5edL6nPOPxGHW7U0gficfTu34/S8XFMLliAcFubtvvqBkXe4Dc2NoaKiorp\nx+Xl5RgcHMx6/GuvvYZNmzY5UzrJNDZuYLBTgNNjHwficfxp+3bsHhmZfi7yzf8ZANWVN/iVlJRY\nPtnJkyfx+uuv4/3338/4/X/7t80YHBzB5OQduPfeCnR1tTgWTJjdo1ucrqX37t+fFvgAYPfICDqj\nUQY/HySTSSSTyaLPkzf4lZWVYXR0dPrx6OgoysvL5xx3/vx5tLS0IJFIYPHixRnPNTj4AEZGDgEA\nPv8c2L7dmQwcs3u38UNgipO19NLx8YzPz7txw5HzU2FCoRBCodD04507d9o7kchjYmJCLF++XFy6\ndEmMj4+L2tpaceHChbRjPv/8c2EYhjh9+nTW8wAQgJjzZZod+YqQVzgcce3cKonF+oVhtKfdA8No\nF7FYv99FyysW6xfhcETU1e0Q4XBEqjJHwuG5by5AdJimI+fvj8VEJBwWO+rqRCQcFv2xmCPn1YWF\nMJb556wcdOzYMfHd735XGIYh9uzZI4QQ4pVXXhGvvPKKEEKILVu2iCVLlojVq1eL1atXi7Vr12Ys\nYKYAVVe3w1bBZ6qr2+HauVWi6oeA7EG7PxYT7YaRdlNfNAxHglSmc7c7dG5duBr8nMCan/tU/RBQ\n4ffXH4uJDtMUO+rqRIdpOhac3K5V6sBu8PN0hodhZM/AFdNXxZVNpqg6EFuFcXkbGhtdSW6wP9E/\nnga/7m4zYwau2IQFx+BNUfVDQNWg7YTJBQsyPp9auNDjkmjI4RpoVrleSoVmjypisX5hmh2irm6H\nMM0OafrNcsnc5/eiEmUvlpv9ibqwG8akWNhAhWaPKrweiO3E0BqVau5Oz/S49bOd0Sjm3biB1MKF\naGht5fhBD0gR/HRu9qjMyfGVKsyecWumh1v9iX5QahqgwzXQrHK9lM7NHj8VO7ZOt+4KZmZz82vY\njt0wJkXNT6VmT1A4UWvTrbuCmdncVJsGKEXwA9Ro9gRJ9jXvOi3/HnTrrmBmNjfVPhyk3Loyk3h8\nAKbZgVCoC6bZgXh8wO8iKc2JWptuaxyG29oQMYy059oNA/WtrT6VSC6qfThIU/PLhQsXOM+JWluu\n7oogLrDAzGxu4bY2REZG0pq+7YaBBlk/HBzue8yqmJfSrWPdC24mmWSfq0vucWsaYC52Y4sSNT/d\nOta94GaSyYn+RFKTSsN2lAh+TjTRgtgMK5ZbSSZ+WJEKlAh+xc5ZZZ+ht3TLApOalAh+xTbR2Azz\nlqoLLJBelAh+QHFNNDbDvMVB66SCkm+yJe6/UEkJPHqpOUyzA729L815fvHiZ7B2rcH+PyKF2Y0t\nygxyLkamwbhAO65efR69vS9h+/Y/cdA0kWa0qPkBU0mPaLQPQ0P/jatX/w+AegC3a3um2YlEYpdv\n5SNSiUyrt9iNLcr0+RXrVp9hKNSF/v6uOd9n/x+RNUHZxF2LZu9MHIZBVJxsq7f0RaM+lcge7YKf\nbpPxiZym2uot2WjT7L2FwzCIimN39RaZ+gkBDYMfwLUDiYphZ/UWGfsJtcn2knc4j9o+2WpH2QzE\n4+ibsbRXfZ6lvTpMEy/19s55vtM0sSuRKKoszPaSFDiP2j4Za0fZFLp6i4z9hNolPMhd2edR9/lU\nInUEJYuaiYyrPDP4kaM4j9o+GWtHTpFxCwA2e8lRHEdpn4y1I6fIuAWAlMGPHebq4nJW9im3B0aB\nZFvlWbrgxw5ztXEcpX0y1o6CTLqhLtmWn+LCA0SUiRJLWlnZc5cd5kTkBU+bvbdWU8nVjGWHORF5\nwZehLrnGfXHhAefE4wMwzQ5LNW4i3fiW8MjWjGWHuTOYOCLKzdOEB3D7pVRMYKg0BIeJI9KFUnN7\nVRz3pVpNiokjotw87fOrq+uCaXaiu1u9Zqxqc1aZOCLKzdOaXzLZ5eXLOUq1mhRnWhDlJt0MD1mp\nVpNi4ogoN+lmeMgqU5+fYbQr2YQnChK7sYXBrwC39v69XZOqZ+Aj8hmDHxFpSYm5vUREsmDCQ2Eq\nDbomkm1zJgY/Rak26Jr0JuPmTHmbvYlEAtXV1aiqqsK+ffsyHtPW1oaqqirU1tbio48+cryQKkgm\nk56+nteDrr2+Pi8F+doAOa5Pxs2Zcga/VCqFbdu2IZFI4MKFCzh8+DAuXryYdsyxY8fw6aefYnh4\nGK+++iqef/55VwssK6/fYF4PupbhD8gtQb42QI7rk3FzppzBb2hoCJWVlVi2bBnmz5+P5uZm9PT0\npB3zzjvv4NlnnwUArFu3DteuXcMXX3zhXokJgHqDrklvMm7OlDP4jY2NoaKiYvpxeXk5xsbG8h5z\n+fJlh4tJs3HdQ1KJjFtXQuRw9OhR8bOf/Wz68Ztvvim2bduWdsyTTz4p3nvvvenHTzzxhPjwww/n\nnAtT61nxi1/84pfjX3bkzPaWlZVhdHR0+vHo6CjKy8tzHnP58mWUlZXNORcHOBORTHI2e9esWYPh\n4WF89tlnuHnzJo4cOYKmpqa0Y5qamvDGG28AAM6cOYO7774b9913n3slJiJyQM6aX2lpKQ4cOADT\nNJFKpbBlyxbU1NTg4MGDAICtW7di06ZNOHbsGCorK3HnnXfi0KFDnhSciKgothrLORw/flysWLFC\nVFZWir1792Y8prW1VVRWVopVq1aJs2fPOl0EV+W7vt/97ndi1apV4pFHHhHf+973xLlz53wopT1W\nfndCCDE0NCTmzZsn3n77bQ9LVzwr13fy5EmxevVq8fDDD4u6ujpvC1ikfNf3t7/9TZimKWpra8XD\nDz8sDh065H0hbdq8ebP4zne+I1auXJn1mELjiqPBb3JyUhiGIS5duiRu3rwpamtrxYULF9KOicfj\n4oc//KEQQogzZ86IdevWOVkEV1m5vlOnTolr164JIabejKpcn5Vru3Xcxo0bRWNjozh69KgPJbXH\nyvVdvXpVPPTQQ2J0dFQIMRUsVGHl+nbs2CF+9atfCSGmrm3JkiViYmLCj+IWbGBgQJw9ezZr8LMT\nVxxd2CDo4wKtXN/69evx7W9/G8DU9aky7MfKtQFANBrF008/jXvvvdeHUtpn5freeustPPXUU9NJ\nvaVLl/pRVFusXN/999+PL7/8EgDw5Zdf4p577kFpqRozXB9//HEsXrw46/ftxBVHg1/QxwVaub6Z\nXnvtNWzatMmLohXN6u+up6dnehbP1I58arByfcPDw/jHP/6BjRs3Ys2aNXjzzTe9LqZtVq6vpaUF\nH3/8MR4hzAO6AAACFUlEQVR44AHU1taiu7vb62K6xk5ccTTsW/1jELOGvajyR1RIOU+ePInXX38d\n77//voslco6Va3vhhRewd+/e6fXTZv8eZWbl+iYmJnD27Fm8++67uH79OtavX4/HHnsMVVVVHpSw\nOFaub8+ePVi9ejWSySRGRkZQX1+Pc+fO4a677vKghO4rNK44GvycHBcoIyvXBwDnz59HS0sLEolE\nzqq6TKxc24cffojm5mYAwJUrV3D8+HHMnz9/zvAnGVm5voqKCixduhSLFi3CokWLsGHDBpw7d06J\n4Gfl+k6dOoVIZGpWkGEYePDBB/HJJ59gzZo1npbVDbbiimM9kkKIiYkJsXz5cnHp0iUxPj6eN+Fx\n+vRpZRICQli7vs8//1wYhiFOnz7tUyntsXJtMz333HNKZXutXN/FixfFE088ISYnJ8U///lPsXLl\nSvHxxx/7VOLCWLm+X/7yl6Krq0sIIcRf//pXUVZWJv7+97/7UVxbLl26ZCnhYTWuOFrzC/q4QCvX\n9+tf/xpXr16d7hebP38+hoaG/Cy2JVauTWVWrq+6uhoNDQ1YtWoV7rjjDrS0tOChhx7yueTWWLm+\n9vZ2bN68GbW1tfj666/x8ssvY8mSJT6X3JpnnnkG/f39uHLlCioqKrBz505MTEwAsB9XPNvDg4hI\nJtzDg4i0xOBHRFpi8CMiLTH4EZGWGPyISEsMfkSkpf8PFgUZtzLBZBsAAAAASUVORK5CYII=\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# linear classification problem\n",
    "figsize(5,5)\n",
    "d0 = data[labels==False]\n",
    "d1 = data[labels]\n",
    "plot(d0[:,0],d0[:,1],\"bo\")\n",
    "plot(d1[:,0],d1[:,1],\"ro\")\n",
    "print len(d0),len(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7278614f",
   "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": 5,
   "id": "0ccb193d",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "47 53\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAT8AAAE1CAYAAACRPefNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtcVHX+P/AXCuGlvKcZsKkDCioCiZGWgBpz8LLUZmva\nVqZGagleMlMGFlS8kHkBNC+75Za1rn1t90fNKIIpkIVgaFppRqy2yG5tlmZbgYif3x8kicwMM2fO\nOZ9zeT8fDx4PGM6c8z7D8J7P/ePFGGMghBCDacM7AEII4YGSHyHEkCj5EUIMiZIfIcSQKPkRQgyJ\nkh8hxJBaTX7Tp09Hr169EBoa6vCY5ORkBAUFISwsDMeOHZM0QEIIkUOryW/atGnIz893+Ps9e/bg\niy++QGVlJbZt24bZs2dLGiAhhMih1eQ3cuRIdO3a1eHv3377bUydOhUAEBUVhYsXL+Lrr7+WLkJC\nCJGBx21+NTU1CAgIaPrZ398f586d8/S0hBAiK28pTnLjDDkvL68Wx9h7jBBCpCBmlq7HJT8/Pz9U\nV1c3/Xzu3Dn4+fnZPZYxpuqvhqsNiNgSgb99/De3n5uens49fjm/xNyfxWwGA1p8pQoC9/uhv51+\nvsTyOPklJCTgtddeAwAcPnwYXbp0Qa9evTw9LRdtvNpgQ/wGPL//efxc/zPvcDTPu67O7uNta2sV\njoSQllqt9k6ZMgXFxcU4f/48AgICsHTpUtTX1wMAZs6ciXHjxmHPnj0IDAxEx44dsX37dtmDllP0\nHdEY5jcM60rXwRJt4R2Opl3x9bX7eEO7dgpHQogdTCEKXspj//zun6x7VndWc6nG5eccPHhQvoBU\nQMz9FVutLMVkYgxo+lpiMrFiq1X6AD1AfzttE5tbvH55suy8vLw8qp8rbcm7S/DV/77C9vu1XZLl\nrcRmQ2FuLtrW1qKhXTvEJSUhevx43mERHRGbWyj5OXCp7hKCNwbjnSnvYOjtQ3mHQwhxQGxuobm9\nDnTy7YTlo5Zj3r55mkrahBDXUMnPiYarDYj8UyRS7k3B7wf9nnc4qlVis6EgJwfedXW44usLc3Iy\nVW1lYKTX2Z17FZtbJBnkrFdt27TFemE9puVNw28H/BbtvKmX8kYlNhv2zZ2LFVVVTY9Zfvlejn9M\nIyWA6yn9OvOk2L163tfiGgUvJQmrtZiZzRYWE5POeiYNYI//KZF3SKpkMZub9eZe+0oVBMmvZa/3\nOEWFvcdyUPJ15s3dexWbW6jNzw6brQRz5+5DQUEmiosz8N/XbXi96nXs+Mc/eIemOkoOZC7IyWlW\nGgCAFVVVKMzNlfxaamOkAeNK3SslPztycgpQVbXi1wcumHC1Yg6WFC7lF5RKKTmQ2UgJ4EZGGjCu\n1L1S8rOjrs5OU2iJBd90qcKx/9BirdczJyfDYjI1eyzFZEJcUpLk1zJSAriRkq8zb0rdK3V42OHr\ne6Xlg3WdEXguGvP3zcfBqQc1u0qN1B0G156bdt1A5niZBjKbk5NhqapqVvVNMZkQr8MEcCMlX2fe\nlLpXGupix7U2v+urviZTCtZtiEPauXlIj0nHgyEPcoxQHLu9aCYThOxszfwT0YwRciOa4SExm60E\nubmFqK1ti3btGpCUFIfx46Nx4MwBJL6TiJNPn4Svt/1qmFqlCgIyCwpaPJ4mCFjuZKsCQtSMxvlJ\nbPz4aIwfH93i8dF9RyO0Zyiyy7Kx6J5FHCITz8gdBoTciDo8RFgTtwYvvP8Cvv6ftvYqMXKHASE3\nouQnQlD3IDwR/gTSDqbxDsUtRuoxJKQ11OYn0sXaiwjeGIz8R/MRfls473BcRh0GRG+ow4ODLR9u\nwa5Pd+HA4wc0O/SFEK3T1JJWNlsJBCEVsbEZEIRU2GwlPMLw2JN3PonzP51H3uk83qEQQtykeG+v\nvTF0VVWNe2XY611VM+823lhnXofZttkYGzhWc0NflGLUlViIyolaDkGEa5cymy32FmxggpCqVCiS\nm/DXCWzN+2t4h6FKRl6JhShDbBpTvNprd94sgNratgpHIp0X417E6kOr8d8f/8s7FNUx8kosRN0U\nr/banTcLoF27BoUjkc6AHgPwWNhjSC9Kx+bxm3mHoypiB1ZTVVl+Rn+NFU9+yclmVFVZWsybTUqK\nVzoUSf0x+o8I3hSMpyOfRmivUN7hqIaYgdVGWrWYF3qNwWclZ6u1mAlCKouJSWeCkMqs1mKlwpDV\nxrKNbMyrY9jVq1d5h6IaYvbuNdKqxbzo6TUWm8a4zO11NG9W62ZGzsRLH74E6+dW/HbAb3mHowpi\nlieiOcjyo9eYFjaQ1LWhL0l7kyAECrip7U28Q1KF6PHj3apK0Rxk+dFrTHN7JScECgjqHoRN5Zt4\nh6JZNAdZfvQa0/Q2WXx2/jOM3D4Sp545hR4devAOR5NoDrL89PIa09xelZmbPxdXrl7BpnFUAiRE\nTpT8VOa7n79D8MZgHJh6AIN7DuYdDiG6pamFDYygW/tuSItOw4J9CwyV9AnRCkp+MpoVOQvVl6qx\np3IP71AIITegaq/M9lTuwYJ9C/Dx7I/h09aHdzhEp4w8VY02MFKpsYFjkVOWg80fbkZyVDLvcIgO\n0VQ1cajaKzMvLy+sNa9FZkkmvv3pW97hEB2ilXPEoeSngEE9B2HSoElYWryUdyhEh2iqmjiU/BSS\nEZuBnZ/sxKlvTvEOhegMTVUTh5KfQnp06AHLSAueLXiWdyhEZ2iqmjjU26ugyw2XEbo5FBuEDRgb\nNJZ3OERH9DJVTQzNzvCw2UqQk1OAujpv+PpeQXKyWZfLXV1j/dyKRYWLcHzWcRr6QogENDnURU87\nublqfNB45JTlYGvFVsy5aw7vcAgxLK5tfjk5Bc0SHwBUVa1Abm4hp4jk5+XlhXXCOiwrXobvfv6O\ndziEGBbXkp8ed3JzxeCeg/HQwIewrHgZNsRv4B2OQ0aeNUDUR+r3I9fkp8ed3Fy1NHYpBr40ELMi\nZyG4RzDvcFqgWQNETZy9H8XiWu1NTjbDZLI0e6xxJ7c4ThEp59aOt2LxPYuxsGAh71DsolkDRIwS\nmw2pgoCM2FikCgJKbDZJzivH+5Frye9ap0Zubhpqa9uiXbsGJCXF67az40ZJUUnYUrEFBVUFMJvM\nvMNpRq2zBqgqrl5y1hbkeD9yX9hArzu5ueKmtjfhxbgXsWDfAnw06yN4t+H+52iixlkDVBVXN0el\ns7TcXI//PnK8H1ut9ubn5yM4OBhBQUHIyspq8fvz588jPj4e4eHhGDx4MP7yl7+IDsaIEgYkoNfN\nvfCnij/xDqUZNc4aoKq4uslZW5Dj/ei0qNHQ0IA5c+Zg//798PPzw7Bhw5CQkICQkJCmYzZu3IiI\niAisWrUK58+fx4ABA/Doo4/C21s9pRg18/LywnphPeJ2xGFK6BR0adeFd0gAxO23Kze1VsVJIzlr\nC3K8H51mqPLycgQGBqJPnz4AgMmTJyMvL69Z8uvduzdOnDgBALh06RK6d+9Oic9NQ3oNwQPBD2B5\nyXKsNa/lHU4Td/fblZsaq+LkV+bkZFiqqpqVzlNMJsRLVFuQ+v3oNEvV1NQgICCg6Wd/f3+UlZU1\nOyYxMRGjR4/G7bffjh9++AFvvvmmZMEZyfJRyzFw00DMHDoT/bv35x2OKsn9z0U8o8bagjNOk5+X\nl1erJ1i5ciXCw8NRVFSEqqoqxMXF4fjx47jllltaHJuRkdH0fWxsLGJjY90OWK96duyJ5+95Hs8V\nPoe8yXm8w1Elrf1zGZEStYWioiIUFRV5fiLmRGlpKRMEoennlStXstWrVzc7ZuzYsezQoUNNP48e\nPZodOXKkxblauRRhjNXW17J+2f1YYVUh71AI0QyxucVpb29kZCQqKytx9uxZXL58Gbt27UJCQkKz\nY4KDg7F//34AwNdff43Tp0+jX79+nmdlA/L19sWLcS9i/r75uHLV/uwXYjxyDRw2vNay4549e1j/\n/v2ZyWRiK1euZIwxtmXLFrZlyxbGGGPffPMNmzBhAhsyZAgbPHgwe+ONNyTNzkZz9epVFvuXWLbl\nyBbeoRAVKLZaWYrJxBjQ9JViMrFiq5V3aKohNrdwX8+PtPTRVx8h/vV4nJ5zGp3bdeYdjmbpYTZI\nqiAgs6CgxeNpgoDl+fkcIlIfTa7nR+wLvy0cE/pPQOZ7mVgTt4Z3OJqkl9kgNLZRPrSHh0pljs7E\n9mPb8cV3X/AORZP0MhuExjbKh5KfSt12821YOGIhFhUu4h2KJumlxKTGaYZ6QdVeFZt39zyEbArB\nwTMHMarvKN7haIpeSkw0tlE+1OGhcrtP7kZmSSYqnqpA2zbSrHCth46A1thr80sxmRCfna27ezU6\nze7eRpxjjCHmLzF4POxxPHnnkx6fz25HgMkEQYdJQcvbORrhA0oqonOL56NsXOPupazWYmY2W1hM\nTDozmy3Mai2WKTL1+7DmQ3bbi7ex72u/9/hcFrO52Zixa1+p183kIXzR2D73iE1jqmzzM+KWls4M\nvX0oxgaOxcr3VmL1fas9OpdeOgL0TM5FQcmvVNnba8QtLVuzYvQK/Pnon/HPC//06Dx66QjQM/qA\nUoYqk59Rt7R0pvctvbFg+AKPh77Q0An1ow8oZaiy2mvkLS2dmX/3fIRsCkHx2WLE9IkRdQ4aOqF+\ntG6hMlTZ22uvzc9kSkF2tnF2dnNk1ye7kPV+Fo4kHpFs6AtRHy33VCtNd0NdbLYS5OYWXrelZZzh\nEx/QOPTl3u33YkbEDEyPmM47HEK4013yI44dqTmC+/92P07POY1bfFuumE2IkYjNLars8CDODfMb\nhjhTHFYdWsU7FEI0i0p+GlVzqQZhW8Lw4VMfok+XPrzDIYQbKvkZjF8nP8yNmovn9z/POxRCNImS\nn4Y9O+JZlFaX4tC/DvEOhRDNoeSnYR18OiDrvizMy5+Hq+wq73AI0RRKfho3efBk+LT1wY7jO3iH\nQoimUIeHDpSdK8ODbz6I03NO4+abbuYdDiGKog4PA4vyj8LovqOR9X4W71AI0Qwq+WmQzVaCnJwC\n1NV5w9f3CpKTzQgb2Q/hW8JR8VQF7uhyB+8QCVEMzfAwCPvzni3IzhZwpOMBnP72NHZO3MkxQkKU\nRdVeg3C21uFzI57DoX8dwgfVH3CKjhDtoOSnMc7WOux4U0esGrOKhr4Q4gJKfhrT2lqHj4Q+Ai8v\nL7xx4g0lwzK8EpsNqYKAjNhYpAoCSmw23iGRVqhyMVPiWHKyGVVVlhZrHSYlxQMA2ni1wQZhAybt\nnoQHQx5Ex5s68grVMOzuiPfL97QGn3ppssPDXm+nkdb6c2Wtw0feegT9u/dHRmwGnyBVTsqtIVMF\nAZkFBS0eTxMELM/P9zRU0gqxuYVbyU9sAqOd3Rrvs7V7XX3fakRsjcCMiBkI6BygUGTaIHVJjTYc\n0ihRG16KcP2lrNZiZjKlNNs61mRKcWlvXrPZYm/bWSYIqXKGr0lpB9LYH976A+8wVEeqvYuLrVZm\nMZvZ4127MgvAimkvZC7EpjEuHR6ebE1JO7u5btE9i1B0tgiHzx3mHYqqSFFSu1Z6zCwowKsXLiAT\nwD4AJb/8nnbEUz8u1V5PEhjt7Oa6m2+6GSvHrMS8/HkonVEKLy8v3iGpghRbQ9rdWBzAlK5dUXjX\nXbQjngSkbJe1h0vy8ySBtdbbSZp7dMijyC3Pxc5PduKR0Ed4h+MWud78UmwN6aj0OGDIEGRQJ4fH\nlOhB55L8PElg1xr6c3PTruvtpC0tHbk29GXKW1PwQPAD6ODTgXdILpHzze9o72KgsefWlWRLG4vL\ny27JuqoKabm50pX+JG57dOjGS1mtxUwQUllMTDoThFSXOjuIeA//38NsadFS3mG4TKpOCVcVW60s\nxWRqdq0Uk4kVW60uH7/EyfHEPekxMXb//ukxMS2OFZvGuA11cWW4BpFO1n1ZuHPbnZgeMR3+nfx5\nh9MqpYePuFvScFR6pHY+aShRsqYZHgZxR5c7MCtyFlLeTcFrv3uNdzitUrpaKSbZRo8fL3uyk7vR\nX62kaJdtDSU/A1l8z2IM2DgA5TXluMvvLt7hOKXEm/96amzDM/K0OSVK1pqc3kbE235sO/587M84\nNO2Q6oe+lNhsKLzuzR8nY7XSXqJJMZkQn53NLdHQtDnXaG56G+FjavhU5Jbn4s1P38TDgx9uelyN\n1SslqpXXXwtQVxseTZuTFyU/g2nj1QYb4jfg8X88joQBCWjv097Q1avrKZlsXaHGqrie0Hp+BhR9\nRzSG+Q3DutJ1ABz3dBbm5vIIj/zCnJwMi8nU7DGaNicdKvkZ1Av3vYBhfxqGaRHTqHoF9Vb7AXVV\nxfWEkp9M1L7mYN+ufZE4NBGWAxb4Gbx6peZqv9qq4roifgy2exS8VDNWazEzmy0sJiadmc0WuzNJ\nXDnG3WuKXbJLSd/Xfs96v9ibbdu1wdCzFZSeTUKkJTa36Lrk58rCp3Isjup4ya40VZX+Ovl2wvJR\ny/GX439B5oYNSNu40ZDVK6r2G1OrHR75+fkIDg5GUFAQsrKy7B5TVFSEiIgIDB48GLGxsVLHKJor\n6wZ6sragI1pac/CJ8Cfwv8v/w3/7/ozl+fnIKCrC8vx8wyQ+gHpVjcpp8mtoaMCcOXOQn5+PkydP\nYufOnTh16lSzYy5evIhnnnkG77zzDj755BPs3r1b1oDd4UoSkiNRaWnNwbZt2mK9sB6L9i9C7RVj\nlnSoV9WYnFZ7y8vLERgYiD59+gAAJk+ejLy8PISEhDQd89e//hUTJ06Ev3/jZPkePXrIF62bXElC\nciQqra05GNsnFhG3RWB96XosGbmEdziKo15VY3Ka/GpqahAQ8OvmN/7+/igrK2t2TGVlJerr6zFq\n1Cj88MMPmDt3Lh577DG758vIyGj6PjY2VvYqsitJSI5EpcU1B9fErUHUn6PwRPgT6H1Lb97hKI56\nVbWjqKgIRUVFHp/HafJzZe5nfX09jh49infffRc//fQThg8fjrvvvhtBQUEtjr0++SnBlSQkV6LS\n2pJdpm4mTI+YjtSDqXg54WXe4RBiV4nNhv03jMdcKvJcTpOfn58fqqurm36urq5uqt5eExAQgB49\neqB9+/Zo3749oqOjcfz4cbvJjwdXkpDWEpVcLCMtCN4UjGP/OYaI3hG8wyGkGWfjMcVw2uERGRmJ\nyspKnD17FpcvX8auXbuQkJDQ7Jj7778fhw4dQkNDA3766SeUlZVh4MCBogMi/HRu1xlLY5di/r75\ntAIPUR1H0zDFcpr8vL29sXHjRgiCgIEDB+Lhhx9GSEgItm7diq1btwIAgoODER8fjyFDhiAqKgqJ\niYmU/DRsRsQMXKi9gH989g/eoRDSjKPxmGLRen6khQNnDiDxnUScfPokfL3tj4EjRGmO1jf0AkTl\nFlrVhbQwuu9ohPYMRXZZNu9QCGniaDymWIYt+al94QHeKr+txPCXh+PTpz9Fr5t78Q6HEAD2V/eO\nmTBBVG4xZPKzN5/XZLIgO1ugBHidhQULcanuErb9dhvvUAhxSGxuMWS1V475vHqUGp2Kt0+/jY++\n+oh3KIRIzpDJT0sLD/DUpV0XpMekSzb0pcRmQ6ogICM2FqmCgBKbTYIoCRFH10taOaKlhQd4Sxya\niE1HNiHvdB4eCH5A9HnUvGAoMSZDlvySk80wmSzNHmuczxvHKSL18m7jjfXCeiwsWIi6K+LHWdE+\nIURtDFny0+LCAzzFmeIQcmsIcstzsXDEQlHnoAVDidoYMvkBNJ/XXS/GvYh7XrkHj4c9jp4de7r9\nfFowlKiNIau9RmGzlUAQUhEbmwFBSIXNViL6XAN6DMBjYY8hvShd1PNpwVDiCTk6ywxb8tM7OfYm\n+WP0HxG8KRhPRz6N0F6hbj2XFgwlYsnWWebx1kkuUvBShDFmNlvsbUjGBCHVo/NuLNvIxrw6hl29\nelWiSAlxrrXd9cTmFqr26pRcYxlnRs7Ef/73H1g/t3p0HkJcJVdnGVV7dUqusYzebbyxzrwOSXuT\nIAQKuKntTQ6PLbHZUHDDqrtUzSXukq2zTMriqTMKXoowRxunL5Fs4/Rxb4xj6z5Y5/D3xVZri43Q\nUwy0ETqRjr330pLr3ktic4shFzYwCputBLm5hdeNZYyTbHjPZ+c/w8jtI3HqmVPo0aHljn2O1l5L\nEwQsz8+XJAZiHPZWc7lWixCbWyj5EdGS9yajgTVg07hNLX6XERuLjOLilo/HxCBDgp23CLmGVnUh\nikuPScf/ffp/+OS/n7T4HQ1qJmpHyY+I1r1Dd6RGp2LBvgUtPnlpUDNRO6r2Eo/UN9QjdHMo1prX\nYnz/5j25ztppCJEKtfkRbvZU7sGCfQvw8eyP4dPWh3c4hmXUoUVicwuN82sF7fXRurGBY5FTloPN\nH25GclQy73AMidZLFMGD4TduUfBSkrE/Vi5FsrFyevLJ15+wW1+4lZ3/8TzvUAyptSlgeiY2t1CH\nhxO014frBvUchEmDJmFp8VLeoRgSrZfoPkp+TtBeH+7JiM3Azk924tQ3p3iHYjg0tMh9lPyckGt+\nrJTr7KlJjw49YBlpwbMFz/IOxXBoaJH7qMPDieRkM6qqLDfs75uCpKR40eeUY509NXl62NPY/OFm\n7K3ci7FBY3mHYxi0XqL7aKhLK6SeHysIqSgoyLTzeBry85d7EqpqWD+3YlHhIhyfdbzZ0BejDsUg\n8qKhLjKReq8PI7Qjjg8aj+yybGyt2Io5d80BQEMxiPpQm5/CjLBnsJeXF9aZ12FZ8TJ89/N3AGjr\nSqI+lPwUZpQ9g0N7hWLiwIlYVrwMgH6GYsixkQ7hg6q9CjPSnsHLYpdh4EsDMStyli6GYlDVXV+o\nw4PIau0Ha3Hw7EEs6jy7ReJIMZkQn52tmcRBC7SqE3V4EFVKikrClootqI3ygZCdremhGHqpupNG\nlPyIrG5qexNejHsRC/YtwEezPtJUsruRHqru5FeG7vDQ60wLnuy9pgkDEtDr5l74U8WfeIfnEZpF\noS+GLfnpfaaFlFxd1svZa7peWI+4HXGYEjoFXdp1USx2KdEsCp2RaFWZVil4KZeYzRZ7KwAxQUjl\nHZqquLOsV2uv6VPvPMUW7Fug9C0QnRObWwxb7TXCTAspuLOsV2uv6fJRy/HqR6/i828/lz5QEWjM\nnrEZttprhJkWUnDnQ6K117Rnx554/p7n8Vzhc8ibnCddkCKIHbNH85N1ROISqEMKXsol9qtzS2iV\n5hu40zzgymtaW1/L+mX3Y4VVhUreRgtiVj4utlpZisnU7PgUk4kVW60KRk5uJDa3GLbkZ6SZFp5w\nZ1kvV15TX29frIlbg/n75uPYzGPwbsPnLShmzJ6j+clpublulf6o9KgOhk1+gPQrtuiRux8Srrym\nvwv+HXLKcvDy0ZcxM3Km5DG7QsyYPSkGOdMUOffJ9mEhcQnUIQUvRTTg6L+Psl5rerGLP1/kcn17\nVdglrVRhpdgkyMgbDYnhSlOD2Nxi2N5ewldE7whM6D8Bme+1XNhVCdHjxzdOtxMEZMTEIE0QWp1n\nLMUgZ5oi5x45l0IzdLWX8JU5OhODXxqMmUNnIrBboOLXjx4/3q3qkxSDnGmKnHvk/LCg5Ee4ue3m\n27BwxEIsKlyEvz/8d0nOKXdngrsJ80bm5GRYqqparm5DU+TskvXDorV68d69e9mAAQNYYGAgW716\ntcPjysvLWdu2bdlbb71l9/cuXIoY0M/1P7M+G/qwA/884PG5tDIUpdhqZamCwNJjYliqIKguPjVx\npW1WbG5xup5fQ0MDBgwYgP3798PPzw/Dhg3Dzp07ERIS0uK4uLg4dOjQAdOmTcPEiRNbnIvW8yOO\n7D65G5klmah4qgJt24ifYaO39fZoSEyjEpsNhdc1NcTd0NQgy3p+5eXlCAwMRJ8+fQAAkydPRl5e\nXovkl5ubi4ceeghHjhxxOwBCJoZMRE5ZDrZ/tB1P3vmk6PPoqTOBhsT8ytOmBkecJr+amhoEBAQ0\n/ezv74+ysrIWx+Tl5eHAgQM4cuQIvLy8HJ4vIyOj6fvY2FjExsaKi5roipeXF9YL6zFh5wRMGjQJ\nnXw7iTqPnjoTpBpQrUdFRUUoKiry+DxOk5+zRHbNvHnzsHr16qaip7Pi5/XJj5DrDb19KMYGjsXK\n91Zi9X2rRZ1DT50JainFqrHqfWPBaenSpaLO4zT5+fn5obq6uunn6upq+Pv7NzumoqICkydPBgCc\nP38ee/fuhY+PDxISEkQFRIxrxegVGLx5MJ4a+hT6de3n9vP1tN6eGkqxuq96O+sNqa+vZ/369WNn\nzpxhdXV1LCwsjJ08edLh8U888QT19hKPZBZnsom7JvIOgzsxM1CkppXZKGJzi9OSn7e3NzZu3AhB\nENDQ0IAZM2YgJCQEW7duBQDMnMlnXibRrwXDFyBkUwiKzxYjpk8M73C4UUMpVi1Vb7nQ1pUG4+qS\n9Dzt+mQXst7PwpHEIx4NfSGe0crQIbG5heb2Gsi1PTYKCjJRXJyBgoJMzJ27T3UbN00aNAntfdrj\n1eOv8g7F0PS+YROV/GSktlKWIKSioKDlQgKCkIb8/OUcInLsSM0R3P+3+3F6zmnc4nsL73AMq7UB\nxmpAm5arjBp3h9PSviXD/IYhzhSHVYdWYeWYlbzDMSy5BhirAVV7ZeLOxj9K0dq+JStHr8S2im04\ne/GsbNegTYyMi0p+MlFjKcudJenVwK+TH+ZGzcXz+5/Hrod2SX5+3Y9jI05R8pOJGktZWty35NkR\nzyJ4YzAO/esQ7v3NvZKe28hTyNQ4c0NplPxkotZSllT7lijVmdPBpwOy7svCvPx5KE8sRxsv6Vpq\n9D6OzREq8Tai5CcTLZayXKV0Z87kwZORU56DHcd3YGr4VMnOq4YpZDwYucTbjEQzTFql4KWIzNzZ\ny1cqh6sPs9vX3s5+qPtBsnOqYQoZD+kxMXanraXHxPAOTRSxuYVKfsRtPDpzovyjMKrPKGS9n4Xl\no6QZk6iGKWQ8GLXEeyNKfgblSZsdr86cVWNWIXxrOJ6MeBJ3dLlDknPqeRybI3pa+ssTlPwMyNM2\nO16dOQEzWg8PAAAUxUlEQVSdA5B0VxIWv7sYOyfulPVaembUEu+NaHqbAUkxzc1mK0FubuF1nTlx\ninTm/Hj5RwRvCsauh3ZhRMAI2a9H1I+mtxGXSdFmJ9WQGXd1vKkjVo1ZhXn583D4ycOSDn0hxkLv\nHB2x2UogCKmIjc2AIKQ6XK1FjQOw3fFI6CPw8vLCGyfe4B0K0TAq+emEO+14ah2A7ao2Xm2wQdiA\nSbsn4cGQB9Hxpo68QyIaRG1+OuFuOx6vNjspPfLWI+jfvT8yYjN4h0I4ojY/g3O3HY9Xm52UVt+3\nGhFbIzAjYgYCOge0/gRCrkPJTye03o4nxm86/wbPDHsGS95dgtcffJ13OB6hhQZ+pdhrIdEMk1Yp\neClDslqLmcmU0mzGksm0hFmtxbxDk9UPdT8wv7V+rLS6lHcootmbZpdigGl29oh5LcTmFmrz0xE9\ntOOJ8drx1/DSkZdQOqMUXl5evMNxm1Y2ClKCmNeC2vyILtrxxHh0yKPILc/Fzk924pHQR3iH4zaj\nLq1lj5KvBY3zI5rXxqsN1gvrsXj/YvxU/xPvcNxGCw38SsnXgpIf0YV7f3MvhgcMx4sfvMg7FLfp\nfYtIdyj5WlCbH9GNsxfPYui2oTg+6zj8O/nzDsctWtgiUinuvhZicwslP6IrlgMWVH9fjdd+9xrv\nUIhCxOYWqvYSXVl8z2Ls/+d+lNeU8w6FqBwlP6Irt/jeghWjV2D+vvlU0yBOUfJTCVdXZCGtmxo+\nFT/X/4w3P32TdyhExWicH2c2WwnS0nbh1Kn/obY2AMBoANFOV1ZWattIrWrj1QYb4jfg8X88joQB\nCWjv0553SESNRM0LEUHBS2mGvSlpQAoDih3uhmZ/GluK7qexifHQmw+xzOJM3mEQmYnNLaqt9hqh\nGpiTU9BsTb1GKwAUArC/Iou951RVrUBubqFMUWrXC/e9gPWH1+PfP/ybdyhEhVRZ7VV6U2xeHC1D\nBTQmPXsrsvDYNlKr+nbti8ShibAcsGD7/dt5h0NURpUlP6OUbhwtQwU0/LKycpzLz9Hz0lWeWHLv\nEuR/kY+Kf1fwDoWojCqTn1FKN8nJZphMlmaPtWs3C3fe+RWys+PtlnLtPcdRoiRAJ99OWD5qOebt\nm0dDX0gzqqz2NpZuSgAUoDHEKwDMuivdXEtuublp1y1D9YjTqr3959hPlKTRtPBp2Fi+EbtP7sbv\nB/2edzhEJVQ5vS0j4yWsWHECV65saXrM23sWLJYhyMh4Wq4QNYuGvrTu4JmDmP72dJx65hTaeRtv\ntRQ909V6fqWl/26W+ADgypUtOHw4jVNE6mWUziFPjeo7ChG3RWB96XosGbmEdzhEBajNT+OM0jkk\nhTVxa7C2dC3+88N/eIdCVECVyY96NF1HHxSuM3UzYXrEdKQeTOUdClEBVSY/6tF0HX1QuMcy0oI9\nlXtw7D/HeIdCOFNlmx/1aLouOdmMqipLs6pv4wdFPMeo1Ktzu85YGrsU8/fNx8GpBzW54RGRhip7\ne9VKrb2qRt21TayGqw24c9udSI9Jx4MhD/IOh3iIVnKWmb1eVZPJguxsgRKNBh04cwCJ7yTi5NMn\n4ettf9Mcog20krPMqFdVW1pbGGN039EI7RmK7LJsThES3lTZ5qdG1KuqHa6OfVwTtwbDXx6OqWFT\n0evmXorHSfhyqeSXn5+P4OBgBAUFISsrq8Xv33jjDYSFhWHIkCG45557cOLECckD5Y16VbXD1VJ6\nUPcgTA2firSDNHjeiFpNfg0NDZgzZw7y8/Nx8uRJ7Ny5E6dOnWp2TL9+/VBSUoITJ04gLS0NTz31\nlGwB80LDb7TDnVJ6WnQa8k7n4aOvPpI7LKIyrVZ7y8vLERgYiD59+gAAJk+ejLy8PISEhDQdM3z4\n8Kbvo6KicO7cOekj5YyG32iHO6X0Lu26ICMmA/P3zceBxw84HPpSYrOhICcH3nV1uOLrC3NysmH3\n1dWLVpNfTU0NAgICmn729/dHWVmZw+NffvlljBs3TproVGb8+GhKdhrg7tjHxKGJ2HRkE/JO5+GB\n4Ada/L7EZsO+uXOxoqqq6THLL99TAtSuVpOfO4NADx48iFdeeQXvv/++3d//4Q/TUFZWhStX2uDW\nWwOQkZEoWTJR6xg8ojx3S+nebbyxXliP2bbZGBs4tsXQl4KcnGaJDwBWVFUhLTeXkh8HRUVFKCoq\n8vg8rSY/Pz8/VFdXN/1cXV0Nf3//FsedOHECiYmJyM/PR9euXe2eq6zsdlRVNS4n/uWXwNy50qw+\nQiub/Io+BBq5W0qPM8Uh5NYQ5JbnYuGIhc1+511XZ/c5bWtrPYqRiBMbG4vY2Nimn5cuXSruRK3t\ncFRfX8/69evHzpw5w+rq6lhYWBg7efJks2O+/PJLZjKZWGlpqdMdlprvUsYc7lDmLrPZItu5tUTL\nO7tZrcXMbLawmJh0ZjZbuMT82Tefse5Z3dnX//u62eMWs7nlmwtgqYIgyXWLrVZmMZtZekwMs5jN\nrNhqleS8RuFCGrP/PFcO2rNnD+vfvz8zmUxs5cqVjDHGtmzZwrZs2cIYY2zGjBmsW7duLDw8nIWH\nh7Nhw4bZDdBegoqJSRcV+PViYtJlO7eWaPVDQE1Je17+PDbLOqvZY8VWK0sxmZq9qEtMJkmSlL1z\np0h0bqOQNflJgUp+8tPqh4Ca/n7f/fQd67mmJzvx1YlmjxdbrSxVEFh6TAxLFQTJkpPcpUojEJv8\nFJ3hYTI57oHzpK2KVjZppNWB2GqaPdO1fVf8MfqPmL9vPgofK2zq8IseP16Wzg1qT+RH0eSXnS3Y\n7YHztMOCxuA10uqHgNqS9szImXjpw5dg/dyK3w74razXuuJrf1GFhna0z4jsJC6BOuTsUmqq9mid\n1VrMBCGVxcSkM0FI1UxnR8s2vyVcY99buZcF5QSxuit1sl5HzvZEoxCbxlSxsIGaqj1ap/RAbCmG\n1qix5B4fGI/AboHYVL4J84fPb3pc6pke156blpuLtrW1aGjXDvFJSTR+UAkSJ2GHnF2KSn7apKZe\nWjmc/O9J1uOFHuybH79hjFHPrCt4DNsRm8ZUkfzUWO0xAk/H1hnhQytpTxJ72vY0Y4x6ZlvD68NB\nbPJTRbVXjdUevZNiVowRmivSY9IRsikEsyNnU89sK7Q2DVAVyQ+gRQOU5njNuzSX/w5q66WVQ/cO\n3ZEanYoF+xZgmO9Ndo+hntlGWvtw0Mwy9q0tS07cI0WpzShrHM6OnI1/ff8vdHp8BCwmU7PfpZhM\niEtK4hSZumht2I5qSn7O0MIF0pOi1OasuUJPCyz4tPXBOmEdFuxbgJfWr0Xaps3UM2uHOTkZlqqq\nZlXfFJMJ8Wr9cJC47dEhTy5lhIZ1pcnZyaTHXuCrV68yYYfAsg9n8w5F1eSaBuiM2NyiiZKfERrW\nlSZnJ5MU7Ylq4+XlhbXmtRj16ij8IfQP6N6hO++QVEmuaYBy0ETyk6KKpqdqmFTk6mTS64fVoJ6D\nMGnQJCwtXoqcsTm8wyEe0kTy83TOKrUZKkvPvcAZsRlNQ19Cbg1p/QlEtbx+qTPLfyGRu6pfY7OV\nIDe38LoqWpzLiUsQUlFQkGnn8TTk5y8XHROxz96HjcmUguxsfYzdXF+6HoX/LMSeP+zhHQqB+Nyi\niZIf4FkVTa/VMLXS+6D1Z+56Bps/3Iy9lXsxNmgs73CISJop+XnCUcmva9cpGDbMRO1/xG3vnH4H\nz+9/HsdnHYdPWx/e4Ria2NyimUHOnrA3GBdIwYULs1FQkIm5c/fRoGnilgn9J8Cvkx+2VmzlHQoR\nyRAlP+DXNsPy8n/hwoXfAIgD8Gtpj9r/iLs+/vpjjHltDD6b8xm6te/GOxxFqWkTd923+XnqWpth\nbGwGioszWvye2v+Iu0J7hWLiwIlYVrwMG+I38A5HMXrZxN0Q1d7r6XkYBlHesthleOPjN/DZ+c94\nh6IYR6u3FObmcopIHMMlP6NMxifKuLXjrVh8z2IsLFjY+sE6obXVWxwxTLX3Gr0PwyDKS4pKwpaK\nLSioKoDZZOYdjuzErt6ipnZCANpY2IAQtft/p/4fG7RpEKtvqOcdiuzEbLok5yrPYnOLYXp7iXKM\nOI+aMYb7dtyHh0Iewuxhs0WfR3WlIwdKbDYUXrfpUlwrS3ulCgIyCwpaPJ4mCFien+9RLNTbS1TB\nqPOovby8sF5Yj7gdcZgSOgVd2nVx+xxa6kV1d/UWNbYTGq7Dg8jL8XJWhZwiUs6QXkNw/4D7sbxE\n3HhRvfSi2qPGVZ4p+RFJGX0e9fJRy/HqR6/i828/d/u5aiwdScWcnKy6LQCo2kskZfRxlL1u7oVF\n9yzCc4XPIW9ynlvPVWPpSCqq3Jzd464WF7lzKU/3kyX80B7MjNXW17J+2f1YYVWhW88T04tKdLSM\nvVEbzPWCxlECvt6+WBO3BvP3zcexmcfg3ca1fzNVlo50THVDXWjhUaIHjDGMenUUpgyegpmRM3mH\no2uaWNLKlT13jd5gTvTh2tCX9KJ0fF/7Pe9wiB2KVnuvrabirBpr9AZzoh8RvSMwof8EZL6XiTVx\na3iHQ27AZaiLs3FftPCAdGy2EghCqkslbiKPzNGZ2H5sO7747gveoZAbcOvwcFSNpQZzaVDHkTrc\ndvNtWDhiIRYVLsLfH/4773DIdRTt8AB+vZQWOzC0NGeVOo7Uo/ZKLUI2heCVhFcwqu8o3uHojqbm\n9rqz565aaK0kRR1H6tHOu13T0JeKpyrQtg39DdRA0Ta/mJgMCEKaJvdv1dqcVeo4UpeJIRPRybcT\ntn+0nXco5BeKlvyKijKUvJyktFaSSk42o6rK0mLjcK2VuPXi2tCXCTsnYNKgSejk24l3SIanuhke\naqW1khR1HKnP0NuHIj4wHivfW4nV963mHY7hqW6Gh1rZa/MzmVI0WYUn/Pz7h38jdHMojiQeQb+u\n/XiHowticwslPzdc2/v315JUHCU+4rYVJStw7Ktj2D1pN+9QdIGSHyEa8XP9zwjZFIJXH3gVMX1i\neIejeZqY20sIAdr7tEfWfVmYv28+Gq6qs83YCKjkp2FaGnRNmmOM4d7t92JGxAxMj5jOOxxFyLU5\nk6YGORPPaW3QNWnOy8sLG4QNuP9v9+P3A3+PW3xv4R2SrNS4OVOr1d78/HwEBwcjKCgIWVlZdo9J\nTk5GUFAQwsLCcOzYMcmD1IKioiJFr6f0oGul709JvO5tmN8wxJnisOrQKlmvo4a/nRo3Z3Ka/Boa\nGjBnzhzk5+fj5MmT2LlzJ06dOtXsmD179uCLL75AZWUltm3bhtmzxe9ZqmVKv8GUHnSthn8gufC8\nt5WjV2JbxTacvXhWtmuo4W+nxs2ZnCa/8vJyBAYGok+fPvDx8cHkyZORl9d8U5a3334bU6dOBQBE\nRUXh4sWL+Prrr+WLmADQ3qBrYp9fJz/MjZqL5/c/zzsUWalxcyanya+mpgYBAQFNP/v7+6OmpqbV\nY86dOydxmORGtO6hfjw74lmUVpfivS/f4x2KbNS4daXTbY92797Nnnzyyaafd+zYwebMmdPsmAkT\nJrBDhw41/TxmzBhWUVHR4lxoXM+KvuiLvuhL8i8xnPb2+vn5obq6uunn6upq+Pv7Oz3m3Llz8PPz\na3EuGuZCCFETp9XeyMhIVFZW4uzZs7h8+TJ27dqFhISEZsckJCTgtddeAwAcPnwYXbp0Qa9eveSL\nmBBCJOC05Oft7Y2NGzdCEAQ0NDRgxowZCAkJwdatWwEAM2fOxLhx47Bnzx4EBgaiY8eO2L59uyKB\nE0KIR0RVlp3Yu3cvGzBgAAsMDGSrV6+2e0xSUhILDAxkQ4YMYUePHpU6BFm1dn+vv/46GzJkCAsN\nDWUjRoxgx48f5xClOK787RhjrLy8nLVt25a99dZbCkbnOVfu7+DBgyw8PJwNGjSIxcTEKBugh1q7\nv2+++YYJgsDCwsLYoEGD2Pbt25UPUqRp06axnj17ssGDBzs8xt28Imnyu3LlCjOZTOzMmTPs8uXL\nLCwsjJ08ebLZMTabjY0dO5Yxxtjhw4dZVFSUlCHIypX7++CDD9jFixcZY41vRq3cnyv3du24UaNG\nsfHjx7Pdu3dziFQcV+7vwoULbODAgay6upox1pgstMKV+0tPT2eLFy9mjDXeW7du3Vh9fT2PcN1W\nUlLCjh496jD5ickrki5soPdxga7c3/Dhw9G5c2cAjfenlWE/rtwbAOTm5uKhhx7CrbfeyiFK8Vy5\nv7/+9a+YOHFiU6dejx49eIQqiiv317t3b1y6dAkAcOnSJXTv3h3e3tqY4Tpy5Eh07drV4e/F5BVJ\nk5/exwW6cn/Xe/nllzFu3DglQvOYq3+7vLy8plk8jTvyaYMr91dZWYnvvvsOo0aNQmRkJHbs2KF0\nmKK5cn+JiYn49NNPcfvttyMsLAzZ2dlKhykbMXlF0rTv6j8Du2HYi1b+idyJ8+DBg3jllVfw/vvv\nyxiRdFy5t3nz5mH16tVNq2jc+HdUM1fur76+HkePHsW7776Ln376CcOHD8fdd9+NoKAgBSL0jCv3\nt3LlSoSHh6OoqAhVVVWIi4vD8ePHccst+lhUwd28Imnyk3JcoBq5cn8AcOLECSQmJiI/P99pUV1N\nXLm3iooKTJ48GQBw/vx57N27Fz4+Pi2GP6mRK/cXEBCAHj16oH379mjfvj2io6Nx/PhxTSQ/V+7v\ngw8+gMXSOCvIZDKhb9++OH36NCIjIxWNVQ6i8opkLZKMsfr6etavXz925swZVldX12qHR2lpqWY6\nBBhz7f6+/PJLZjKZWGlpKacoxXHl3q73xBNPaKq315X7O3XqFBszZgy7cuUK+/HHH9ngwYPZp59+\nyili97hyf/Pnz2cZGRmMMca++uor5ufnx7799lse4Ypy5swZlzo8XM0rkpb89D4u0JX7W7ZsGS5c\nuNDULubj44Py8nKeYbvElXvTMlfuLzg4GPHx8RgyZAjatGmDxMREDBw4kHPkrnHl/lJSUjBt2jSE\nhYXh6tWreOGFF9CtWzfOkbtmypQpKC4uxvnz5xEQEIClS5eivr4egPi8othKzoQQoia0hwchxJAo\n+RFCDImSHyHEkCj5EUIMiZIfIcSQKPkRQgzp/wNDKZqBIPBQ2wAAAABJRU5ErkJggg==\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "figsize(5,5)\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",
    "print len(d0),len(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e2e649a",
   "metadata": {},
   "source": [
    "Note that these decision boundaries are linear, by construction.  \n",
    "\n",
    "We have seen another problem 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.  However, in this case, the class conditional densities aren't normal at all, they are uniform densities over quadrilateral regions.\n",
    "\n",
    "How do we find these decision boundaries automatically?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09ec5370",
   "metadata": {},
   "source": [
    "(augmented vectors)\n",
    "\n",
    "To simplify computations, we would like to use homogeneous coordinates.\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 \\leq d$$\n",
    "\n",
    "and as class 1:\n",
    "\n",
    "$$a \\cdot x \\gt d$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "338eff70",
   "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 \\leq 0$$\n",
    "\n",
    "and\n",
    "\n",
    "$$a \\cdot x \\gt 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": "6c0a6937",
   "metadata": {},
   "source": [
    "# The Perceptron Learning Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6aa16ce3",
   "metadata": {},
   "source": [
    "(sample correction)\n",
    "\n",
    "We want $a \\cdot x \\gt 1$ for all samples in class 1.  Now, assume that this isn't working for some sample $x$, $a \\cdot x \\leq 0$ even though it should be $\\gt 0$.  How do we fix that?\n",
    "\n",
    "Actuall, the solution is fairly simple:\n",
    "\n",
    "- When $a \\cdot x \\leq 0$ when it should be $\\gt 0$, we add \"a little bit of $x$\" to $a$.  \n",
    "- That is, we update $a \\rightarrow a + \\epsilon x$.  \n",
    "\n",
    "Then, next time, $(a + \\epsilon x) \\cdot x = a \\cdot x + \\epsilon ||x||^2 > a \\cdot x$.\n",
    "\n",
    "- For the other case, we subtract a little bit of $x$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9ce59e1",
   "metadata": {},
   "source": [
    "(flipping class 0 to class 1)\n",
    "\n",
    "Notice that the two cases are symmetrical.\n",
    "\n",
    "Instead of considering two classes, we can simplify the problem further by flipping the sign of $x$ for all the samples in class $0$.  \n",
    "\n",
    "Then, we require for all samples in the transformed problem that $a \\cdot x \\gt 0$.\n",
    "\n",
    "(Remember that we have also augmented the data vector)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36da9bd1",
   "metadata": {},
   "source": [
    "(perceptron learning algorithm)\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\\\\}$\n",
    "- replace all the $x_i$ with augmented vectors $x_i \\rightarrow (1,x_i)$\n",
    "- 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$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6962925d",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "augmented = concatenate([ones((100,1)),data],axis=1)\n",
    "flipped = augmented.copy()\n",
    "flipped[labels==False] = -flipped[labels==False]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "30f18793",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.13934384,  0.75032961,  0.04619536])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = random_sample((3))\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "c7d9f1ed",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n"
     ]
    }
   ],
   "source": [
    "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "35313c4a",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-4.8606561592 7.22012563323 3.4123797405\n"
     ]
    }
   ],
   "source": [
    "d,a0,a1 = a\n",
    "print d,a0,a1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52f2cfbf",
   "metadata": {},
   "source": [
    "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": 12,
   "id": "06e4a623",
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "47 53\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAT8AAAE1CAYAAACRPefNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtYVHX+B/A3N69Z4a0UKOWAghdA07xAghpz8JJtaWll\nm6ZmpqCVF4aBBbcUtCsMlbTbvc2ttS3bGSXUBBYvYNpPK6wUzdDKYtPVckUu398fBorMDDNnzv18\nXs/D88Bw5pzPGYbPfO9fH8YYAyGEGIyv0gEQQogSKPkRQgyJkh8hxJAo+RFCDImSHyHEkCj5EUIM\nqc3k9+CDD+K6667D4MGDnR6TkpKC8PBwREdH47PPPhM1QEIIkUKbyW/27NkoLCx0+vtNmzbh8OHD\nOHToEF5++WUsWLBA1AAJIUQKbSa/W265BYGBgU5//9FHH+GBBx4AAIwYMQKnT5/GyZMnxYuQEEIk\n4HWb34kTJxASEtL8c3BwMI4fP+7taQkhRFL+YpzkyhlyPj4+rY5x9BghhIhByCxdr0t+QUFBqK6u\nbv75+PHjCAoKcngsY0yXXw2NDegxsQeKDhcpHotUX5mZmR4/x2IygQGtvtJ5XvH78fbetPSl9/sT\nyuvkN2XKFLz55psAgN27d+Paa6/Fdddd5+1pNcXXxxexN8Qiuyxb6VBUxb+21uHjfufPyxwJIa21\nWe295557UFJSgpqaGoSEhGDlypWoq6sDAMyfPx8TJ07Epk2bEBYWhs6dO+O1116TPGg1GtxzMN48\n9SbKj5djRPAIpcNRhfr27R0+3tChg8yRENJam8lv/fr1bZ4kPz9flGC0bNzYcejZqSeyy7Lx4YwP\nlQ5HdAkJCR4/x5SSAktVFVZVVTU/lsZxSEpOFjEy7wm5Ny3R+/0J5cO8qTR7ciEfH6/q51pwru4c\nQnNDse2P2zCw50Clw1GFUrsdW6xW+J0/j4YOHZCYnIwxkyYpHRbREaG5hZKfyFb/ezW+qvkKb97x\nptKhEGIIlPxU4vT50+DyOOx9aC/6XNtH6XAI0T1KfiqSujUVv174FfkTjdEWWmq3oygvD/61tahv\n3x6mlBSq2krASK+zJ/cqOLcwmch4KcX9cPYHFpgTyH48+6PSoUiuxGZjaRzHGND8lcZxrMRmk+x6\nFpOJZcbHM4vJJNl11Ebu11lJnt6r0NxCyc8Jm62EmUwWFh+fyUwmC7PZSjx6/gLbAmbeapYoOvWw\nmEwt3qRNX+k8L/q1jJQAriTn66w0T+9VaG4RZXqb3tjtpVi8+GNUVa1qfqyqygIAmDRpjFvnWDZ6\nGYb/ZThWxK7ANR2ukSRONZBzIHNRXl6LYTMAsKqqChlWq26rf02MNGBcrnulxUwdyMsrapH4AKCq\nahWs1i1un6NvYF8khSXhpU9fEjs8VZFzILOREsCVjDRgXK57peTnQG2t4wLx+fN+Hp0nNS4VueW5\n+F/d/8QIS5VMKSmwcFyLx9I4DokSDGQ2UgK4kpyvs9Lkuleq9jrQvn29w8c7dGjw6DyDeg7C8N7D\n8dr/vYZHhj8iRmheE7vHsOm5GZcNZE6SaCCzVmaMSEHO11lpst2rNw2TnpDxUl6z2UoYx6W1aG/l\nOLPHnR6MMbbzu52sz/N9WF1DnQSRekYPHQYlNhtL53mWGR/P0nleU7ETaQjNLTTOzwm7vRRW6xac\nP++HDh0akJyc6HZnx5USXk/A3KFzMTNqpshReiad5/FkUVGrxzN4Hk+42KqAEDUTmluo2uvEpElj\nBCe7K5njzHi86HHcO/he+Poo18xq5A4DQq5EHR4yMHEmtPNrB9s3NkXjMHKHASFXouQnAx8fH5jj\nzMguy1a06m+kHkNC2kJtfjJpaGzAgBcHoGByARL6JCgWBy0xRfSGFjbQgFf2vYL3Kt/DxzM/VjoU\nQnRDU8nPbi9FXl4Ramv90b59PVJSTKJ1LqjZhYYL4PI4fDj9Q9zU+yalwyFEFzTT2yvGvFmtaufX\nDo+NfAw5O3Lwj7v+oXQ4sjHSUkxEQ7wbXui+pkuZTBZHCzYwnk+XKxRFna09y3qs7cG++vkrpUOR\nhR4GVhN1E5rGZO/tFWverFZd1e4qLBy+EGt3rlU6FFk4W4lli9WqUESEXCR7tVesebNaljwiGWF5\nYViZsBLBVwcrHY6khA6spqqy9Iz+Gsue/FJSTKiqsrRo8+O4NCQnJ8kdimK6duyK2UNm45ldz+A5\n/jmlw5GUkIHVpXY7Pl68uEWJ0fL790b655QSvcZQZmEDm62E8Xw6i4/PZDyfLmjBAK07/t/jLDAn\nkP38289KhyIpR21+5jba/Iy0arFS9PQaC01jisztFXPerFYFXR2EqQOmwlphxcqElUqHIxkhyxPR\nHGTp0WtMCxsoavno5Rj96mgsHbUUXdp3UTocyYyZNMmjqhTNQZYevcY0t1dR4d3CMa7vOLy892Wl\nQ1EVmoMsPXqNaXqb4j774TNMXj8ZR1KOoL2/409jI6I5yNLTy2usqeltpKUJf5uAOyPuxLyb5ikd\nCiGaIzS3ULVXBcxxZqzduRYNjcYZ60iI0ij5qcAtN9yCnp17YkPlBqVDIcQwKPmpgFoWOyXESCj5\nqcSk8EloZI0oPEwbCRHPldrtSOd5ZCUkIJ3nUWq3Kx2S6tE4P5Xw8fFBalwqssuyMSF8gtLhEA2h\nqWrCUMlPRe4eeDdOnD2BHd/tUDoUoiG0co4wlPxUxN/XH8tGL0N2WbbSoRANoalqwlDyU5lZMbOw\n74d9OHDygNKhEI2gqWrCUPJTmQ7+HbBk5BLklOUoHQrRCJqqJgzN8FChM7VnEJobivK55eC6cm0/\ngRieXqaqCaHZ6W1G3cmtLemfpKPmXA3WTV6ndCiEqJomk5+jndw4zoLcXN7wCfDn335G//z++PKR\nL9GrSy+lwyFEtTQ5tzcvr6hF4gOAqqpVsFq3KBSRevTo3AMzo2biud36XuaeEKUoOsjZ6Du5tWXp\n6KUYUjAE5jgzAjsGyn59o29wQ9RF7PejosmPdnJz7YZrbsBt/W7DC3teQPqYdFmvTbMGiJq4ej8K\nJnzbEM84upTNVsI4Lq3FHiocZzbkhkbOVP5UyXo+1ZP9duE3Wa+rpw1uiHxKbDZmMZlYZnw8s5hM\nom1O7+r9KDSNKVrya+rUsFozcP68Hzp0aEBycpLhOzsuF9kjErEhsfjrvr8iZUSKbNdV66wBqoqr\nl5S1BSnej4ovbEA7ubXNHGfG1Pem4uFhD6OdXztZrqnGWQNUFVc3Z3OMM6xWr/8+Urwf2+ztLSws\nREREBMLDw7FmzZpWv6+pqUFSUhJiYmIwaNAgvP7664KDIY4NDxqOft364Z3P35HtmmqcNUAT+NVN\nytqCFO9HlyW/hoYGLFq0CFu3bkVQUBCGDx+OKVOmIDIysvmY/Px8DBkyBNnZ2aipqUH//v0xc+ZM\n+PsrXqjUFXOcGYs2L8Ifo/8IXx/pRygJ2W9XamqtipOLpKwtSPF+dJmhKioqEBYWhj59+gAAZsyY\ngY0bN7ZIfr169cKBAxcn4Z85cwbdunWjxCeBcX3HoUu7Lvjwqw9xZ+SdslzT0/12pabGqji5xJSS\nAktVVYvSeRrHIUmk2oLY70eXWerEiRMICQlp/jk4OBjl5eUtjpk3bx7GjRuH3r174+zZs3jvvfdE\nC45c0rTU/eqy1bgj4g74+PgoHZLspP7nIt5RY23BFZfJz51/sNWrVyMmJgbFxcWoqqpCYmIi9u/f\njy5durQ6Nisrq/n7hIQEJCQkeBywkd0ecTssn1iw7eg23Bp6q9LhyE5r/1xGJEdtobi4GMXFxd6f\nyNU4mF27djH+snFdq1evZjk5OS2OmTBhAisrK2v+edy4cWzPnj2tztXGpYibXv/sdTbujXFKh0GI\nagjNLS5bzocNG4ZDhw7h22+/xYULF/Duu+9iypQpLY6JiIjA1q1bAQAnT57E119/jdDQUO+zMnHo\n3sH34vAvh1FxokLpUIhMaHMiabis9vr7+yM/Px88z6OhoQFz5sxBZGQkCgoKAADz589HWloaZs+e\njejoaDQ2NmLt2rXo2rWrLMEbUYBfAJaOWorssmx8MP0DpcMhEqOxjdJRfD0/4rlzdefQN7cvtj+w\nHQN6DFA6HNXSw2yQdJ7Hk0VFrR7P4Hk8UUjbnALCcwuNSdGgTgGdkHJzCtbsWIM3/vCG0uGokl5K\nTDS2UTq0h4dGLbx5IWzf2HDs9DGlQ1ElvcwGobGN0qHkp1HXdrgWc4fOxdO7nlY6FFXSS4lJjdMM\n9YKqvRr26MhHMeCFAcgYk4GenXsqHY6q6KXERGMbpUMdHhq3wL4AXTt2xapxq9o++Hd66Ahoi6M2\nvzSOQ1Juru7u1eg0uYER8d6RU0dw819uxpHFR3B1+6vbPN5hRwDHgddhUtDydo5G+IASi+6SH21p\n6b77/nkfonpGYUXcijaPpaET6mekDygx6Gqoi6MtLauqLABACdCB1NhUmN42IWVECjoGdHR5rF46\nAvRMykVBySWq7O2lLS09M/i6wRjWexhe/7/X2zxWLx0BekYfUPJQZfKjLS09Z44z46mdT6G+0fGO\neE1o6IT60QeUPFRZ7aUtLT03OmQ0Qq4JwbtfvIv7ou5zehwNnVA/WrdQHqrs8HDU5sdxacjNpZ3d\nXCk8XIhlW5Zh/8P7ZVnqnkhHyz3VctNlb6/VuuWyLS0TKfG1gTGGm16+CSsTVuK2/rcpHQ4hstBd\n8iPCvPfle3h+9/PY8eAOQy51T4xHaG6hupHOTI2cippzNSg9Vqp0KISoGiU/nfHz9cPy2OXILstW\nOhRCVI2Snw7dH3U/vvjpC+z7YZ/SoRCiWpT8dKi9f3s8Nuox5JTlKB0KIapFyU+nHrrpIWz/dju+\n+c83SodCiCpR8tOpq9pdhYXDF2LtjrVKh0KIKtFQFx37z7n/INwajgMLDiD46mClwyFEEjTUhbTS\nrVM3zIqZhWd3Pat0KISoDpX8NMiTtQ6PnzmOqJeicCj5ELp16iZzpIRIT1fr+RHnPF3rMPjqYNwZ\neSesFVZkJWTJFSYhqkfVXo0Rstbh8tjleGHPC/j1wq9Sh0eIZlDy0xghax3269YPY/uMxct7X5Yq\nLEI0h5Kfxghd69AcZ8azu55Fbb3jVYKJd0rtdqTzPLISEpDO8yi125UOibSB2vw0JiXFhKoqS6u1\nDpOTk1w+b0ivIRjUcxDeOvAW5g6dK3WYhuJww6Hfv6c1+NRLk729Rt/ZTehahyXflmDev+bh4MKD\n8PM19pYAYm4NSTviKUtzvb1CExjt7HbxPoXc65gbx6B7p+54/+D7uHvg3RJEpg1il9RowyGNYjK5\n/FI2WwnjuDQGsOYvjktjNltJm+cxmSwtntf0xfPpUoavGx999RGLWRfDGhsblQ5FMRaTqfUbCGDp\nPO/ReUpsNmYxmdgfAwOZBWAlXp6PCCM0jSnS4eHN1pS0s5t3JvWbhPrGenxc9bHSoShGjJJaU+nx\nyaIivHHqFJ4E8DGApiVkaUc89VOk2utNAqOd3bzj6+OL1NhU5JTlICnMdSeJXomxNaTDjcUB3BMY\niC0330w74olAzHZZRxRJft4kMKG9neSS6YOmI317OnZV78KokFFKh+OUVG9+MbaGdFZ67B8VhSzq\n5PCaHD3oiiQ/bxJYU0O/1ZpxWW8nbWnpCX9ffywbvQzZZdn46J6PlA7HISnf/M72LgYu9ty6k2xp\nY3FpOSxZV1Uhw2oVr/QnctujU1deymYrYTyfzuLjMxnPp7vV2UHEc+7COXb909ezz09+rnQoDonV\nKeGuEpuNpXFci2ulcRwrsdncPt7s4njimcz4eId//8z4+FbHCk1jig11ETpcg4ijY0BHLB6xGDll\nOXj7zreVDqcVuYePeFrScFZ6pHY+cchRsqYZHga2YNgCcHkcjp46ir6BfZUOpwW5q5VCku2YSZMk\nT3ZSN/qrlRjtsm2h5Gdg13S4Bg/d9BCe2vkUXpz0otLhtCDHm/9yamzDM/K0OTlK1pqc3kbE89Nv\nPyEiPwKVCytx/VXXKx1OC6V2O7Zc9uZPlLBa6SjRpHEcknJzFUs0NG3OPZqb3kbUoWfnnrh38L14\n/G/J6PvPM6qqXslRrbz8WoC62vBo2py0KPkR3HJ+KGYfm4fvSxtx7e//V0apXl1OzmTrDjVWxfWE\n1vMj+LzgXUz7qhEvDr/02KqqKmyxWpULilxs9+S4Fo/RtDnxUMmPwL+2Fis+A8Y/ACzZDXSqu/i4\nkapXauxVVWNVXE8o+UlES2sO1rdvj4E/AyOPA68OARZVXHzcKNUrNfeqqq0qrie6T37uJCGxE5XW\n1hxsGlZi/ncVpt8FzP8UyOwr3bAStZFlKhVRHV0nP3eSkBSJyvmSXRmqTH5N/+A2qxU+rBzT7gnG\n4/fkGOYfn3pVjanNDo/CwkJEREQgPDwca9ascXhMcXExhgwZgkGDBiEhIUHsGAVzZ91Ab9YWdEaL\naw6OmTQJTxQW4uXk93BoVAPiJk5QOiTZUK+qMblMfg0NDVi0aBEKCwtRWVmJ9evX4+DBgy2OOX36\nNBYuXIh//etf+OKLL7BhwwZJA/aEO0lIikSl5TUHbw29FZ0COuGjr9W52osUqFfVmFxWeysqKhAW\nFoY+ffoAAGbMmIGNGzciMjKy+Zh33nkHU6dORXBwMACge/fu0kXrIXeSkBSJSstrDvr4+MAcZ0Z2\nWTZu7387fHx8lA5JctSrakwuk9+JEycQEhLS/HNwcDDKy8tbHHPo0CHU1dVh7NixOHv2LBYvXoz7\n77/f4fmysrKav09ISJC8iuxOEpIiUWl9zcE7Iu+A5RMLtn+7HeP6jlM6HFlQr6p2FBcXo7i42Ovz\nuEx+7nzq19XVYd++fdi2bRvOnTuHUaNGYeTIkQgPD2917OXJTw7uJCGpEpWWl+zy9fHFitgVyC7L\nNkzyI9pQardj6xXjMVcKPJfL5BcUFITq6urmn6urq5urt01CQkLQvXt3dOzYER07dsSYMWOwf/9+\nh8lPCe4kIS0nKqncF3UfMosz8en3n2JY72FKh0OIy/GYQrjs8Bg2bBgOHTqEb7/9FhcuXMC7776L\nKVOmtDjm9ttvR1lZGRoaGnDu3DmUl5djwIABggMi6tDOrx0eH/U4ssuylQ6FEADOx2MK5TL5+fv7\nIz8/HzzPY8CAAZg+fToiIyNRUFCAgoICAEBERASSkpIQFRWFESNGYN68eZT8dGLu0Lko+64MX9V8\npXQohDgdjykUredHXHqi5AkcOX0Er93+mtKhEINztr6hDyAot9CqLsSlRTcvwkdff4Tv/vud0qEQ\ng3M2HlMow5b8tLTwgNKWbVmGCw0XkJuUq3QoxOAcre4dP3myoNxiyOTnaD4vx1mQm8tTAnTg+7Pf\nY9CLg/D1oq/Ro3MPpcMhpAWhucWQ1V4p5vPqWe8uvXHXwLuQV5GndCiEiMaQyU+LCw8obfno5Xhp\nz0s4U3tG8DlK7Xak8zyyEhKQzvMotdtFjJAQz+h6SStntLzwgFK4rhwSuUQUfFqAZbHLPH6+mhcM\nJcZkyJJfSooJHGdp8djF+byJCkWkDamxqXhu93M4X+/5OnfOBqjSPiFEKYYs+Wl94QGlRF8fjSG9\nhuCN/3sD84fN9+i5tGAoURtDJj+A5vMKZY4z44EPH8CcoXPg7+v+24cWDCVqY8hqr1HY7aXg+XQk\nJGSB59Nht5d6fc64G+LQu0tv/OPLf3j0PFowlHhDis4yw5b89E7KTZTMcWaYt5kxY9AMtxc7pQVD\niVCSdZYxmch4KcIYM5ksDGCtvng+3etzNzY2suiXopnta5sIkRLimsVkav1GBlg6zzPGhOcWqvbq\nlJRjGX18fJAal0rLXRFZSNVZRslPp6QeyzhtwDT8+OuP+Pexfzs9hgY1EzFI1lkmZvHUFRkvRRhj\nNlsJ47i0FjUFjjMzm61EtGsUfFrAJrw9weHvSmw2lsZxLaopaRzHSmxUVSaecfReMl/2XhKaWwy5\nsIFR2O2lsFq3XDaWMVHU4T219bUIzQuF/V47Yq6PafE7Z2uvZfA8nigsFC0GYgyOVnNp6uwQmlso\n+RGvPL3zaXz6/af4+7S/t3g8KyEBWSUlrY7Pio9Hlgg7bxHShFZ1IYqYf9N8bDu6DYd/OdzicRrU\nTNSOkh/xSpf2XbBg2AKs3bG2xeM0qJmoHVV7iddqztWgn7UfvnjkC/Tu0rv5cVftNISIhdr8iKKW\nFC6Bv68/njY9rXQohlVqt6Poig29jfBhQ8lPIrTXh3uq/1uN6HXROJxyGF07dlU6HMNxOAWM48Dn\n5uo+AVLykwDt9eGZBzc+iD7X9sGf4v+kdCiGY+ShRdTbKwHa68MzK2JXIL8iH79d+E3pUAyH1kv0\nHCU/F2ivD8/0794fY24cg7/s+4vSoRgODS3yHCU/F6SaHyvFOntqYY4z45ldz+BCwwWlQzEUGlrk\nOVrPz4WUFBOqqixXtPmlITk5SfA5pVxnTw1u6n0TIrtH4u0Db+PBIQ8qHY5h0HqJnqMOjzaIPT+W\n59NRVPSkg8czUFj4hDehqsb2o9vxsP1hVD5SCT/fS00ERh2KQaQlNLdQya8NYu/1YYR2xIQ+CQjs\nEIgPvvoA0wZMA0BbVxL1oTY/mRlhz2AfHx+Y48zILstu/kSmrSuJ2lDyk5lR9gy+rf9tOF9/HluO\nXBwWpJehGLRAq35QtVdmRtkz2NfHF6mxF5e6N3EmXQzFoKq7vlCHB5FMXUMdwq3h+Pu0v+PC/v+0\nShxpHIckDU2/MvIsCjWjDg+iOgF+AVg2ehmyy7KxccZGANoeiqGXqju5iJIfkdSDQx7EE6VP4Iuf\nvsCYSZM0leyupIeqO7nE0NVeWrFFfI5e0wNX70BlTSXeuuMtpcPziqM2P61V3fWIqr0e0vtMCzG5\n+yHh7DVd/Uwsnj70NI6eOoq+gX3lDF1UNItCZwTt+SaAjJdyi8lkcbQJPOP5dKVDUxXHW2CmOdwC\n09Vrmro1lT1if0SBOyB6JzS3GHacnxFmWojBk2W9XL2mS0YswfrP1+PkrycliVMIGrNnbIat9hph\npoUYPPmQcPWaXnfVdbhn8D14vvx5ZI/PFjVGIYSO2aP5yToicgnUKRkv5RbH1Tmzw+qckXnSPNDW\na3r01FHWdU1Xdvp/p+W+jVYsJlPrmwJYOs87fU6JzcbSOK7F8Wkcx0psNhkjJ1cSmlsMW/IzykwL\nb3myrFdbr2mfa/tgYvhEvLjnRZhvMctzA04IGbPnbH5yhtXqUemPSo/qYNjkB4i/Yoseefoh0dZr\nmhqbivFvjseSkUvQMaCjJDG7Q8iYPTEGOdMUOc9J9mEhcgnUKRkvRVRuyvopLL88X9EYHFVhzW1U\nYYVUlaU4h5G409QgNLcYuuRHlGGOM2PGhhl46KaHEOAXoEgMQsbsmVJSYKmqaj3I2YOl4mmKnGfE\nampwhJIfkd3I4JHoG9gXf//i77g/+n7F4vB0up0Yg5xpipxnpPywoORHFGGOM+PRjx/FfVH3wddH\nvOGmUncmeDs/WYzSo5FI+mHRVr148+bNrH///iwsLIzl5OQ4Pa6iooL5+fmx999/3+Hv3bgUMZDG\nxkY2tGAo+/Dgh6KdUytDUUpsNpbO8ywzPp6l87zq4lMTd9pmheYWlwsbNDQ0oH///ti6dSuCgoIw\nfPhwrF+/HpGRka2OS0xMRKdOnTB79mxMnTq11bnUuLABUdaGyg14eufT2DVnF3x8fLw+n97W26Mh\nMReV2u3YcllTQ+IVTQ2SLGxQUVGBsLAw9OnTBwAwY8YMbNy4sVXys1qtmDZtGvbs2eNxAMS47oi4\nA5ZPLCj+thhj+471+nx66kygITGXSLUUmsvkd+LECYSEhDT/HBwcjPLy8lbHbNy4EZ988gn27Nnj\n8hM8Kyur+fuEhAQkJCQIi5rogp+vH1bErkB2WbYoyU9PnQlS9nJqXXFxMYqLi70+j8vk505VZMmS\nJcjJyWkueroqfl6e/AgBgJlRM5FZnIm93+/FTb1v8upceupMUEspVo1V7ysLTitXrhR0HpfJLygo\nCNXV1c0/V1dXIzg4uMUxe/fuxYwZMwAANTU12Lx5MwICAjBlyhRBARFjaefXDo+PehzZZdnYcPcG\nr86lp/X21FCK1X3V21VvSF1dHQsNDWVHjx5ltbW1LDo6mlVWVjo9ftasWdTbSzz2a+2vrMfaHuzg\nzweVDkU1hMxAEZtWZqMIzS0uS37+/v7Iz88Hz/NoaGjAnDlzEBkZiYKCAgDA/PnzZUjPRO86t+uM\nRTcvwtoda/Hq7a8qHY4qqKEUq5aqt1QMvYeHEal135Jf/vcLwvLCsP/h/Qi5JqTtJxDJaWXoEO3h\nQdqk5n1LunbsigeHPIhndj2D55OeVzQWcpGeOpAcoZKfhNRWyuL5dBQVPeng8QwUFj6hQEQtfX/2\newx6cRC+Sf4G3Tt1VzocgrYHGKsBlfxURo2lLLXvW9K7S29MGzANeeV5+PPYPysdDoF0A4zVwLAb\nGEnNk41/5KKFfUuWxy7HS5++hLO1Z2W5Hm1iZFxU8pOIGktZnixJr5SwrmEY33c8CvYWYOnopZJe\nS/fj2IhLlPwkosZSllb2LUmNS8WkdyYh+eZktPd3PNhXDEaeQqbGmRtyo+QnEbWWssTat0TKzpyY\n62MQfV003tj/Bh666SFRzumI3sexOUMl3oso+UlEK6UsIeTozDHHmTF742w8OORB+PtK8zZVwxQy\nJRi5xHs5Sn4S0uvucM47czJEu99bbrwF1191PTZUbsCMQTNEOeeV9D6OzRmjlnivRMmPeEyuzhxz\nnBmWTyyYPnC6KIudXkkNU8iUYNQS75Uo+RmUN212cnXmTAyfiLRP0rD58GZMDJ8o6rmb6HkcmzNG\nLfFeiZKfAXnbZidXZ46Pjw9SY1ORXZYtWfIzIqOWeK9E09sMSIxpbnZ7KazWLZd15iRK0r5Z31iP\n/vn98cYf3kDcDXGin59oH01vI24To81Ors4cf19/LB+9HDllObDda5P8esQ4aHqbjtjtpeD5dCQk\nZIHn02EqJei5AAAUM0lEQVS3lzo8To0DsF15IOYB7PthHw6cPKB0KERHqOSnE56046l1ALYzHfw7\nYMnIJcgpy8E7U99ROhyiE9TmpxOetuPJ1WYnljO1ZxCaG4ryueXgunJKh0NUhNr8DM7TdjytDcC+\nuv3VeHjYw3hq51NYN3md0uEQHaDkpxNaa8cTYvGIxeif3x+Z8Zno1aWX0uGIihYauESu14KSn05o\nrR1PiB6de2Bm1Ew8t/s5rE1cq3Q4oqGFBi6R87WgNj8d0Vo7nhDf/fc7DCkYgsPJhxHYMVDpcESh\nlY2C5CDktaA2P6K5djwhbrjmBtzW7za8sOcFpI9JVzocUdBCA5fI+VrQOD+iOStiV8BaYcW5unNK\nhyIKWmjgEjlfC0p+RHMie0QiNiQWf933V6VDEYUpJQUWruXwnTSOQ6LBFhoA5H0tqM2PaNKeE3sw\n9b2pOJxyGO382ikdjte0sEWkXDx9LYTmFkp+RLNuffNWzIyaiVkxs5QOhShIaG6hai/RLHOcGWt2\nrEEja1Q6FKJBlPyIZo3rOw5d2nXBh199qHQoRIOo2qsSUu6GpmcfHPwAq8tWo2JuhSRL3RP1o3F+\nGmW3lyIj410cPPgrzp8PATAOwBiXKytTorzk9ojbYfnEgm1Ht+HW0FuVDodoCZOJjJfSDJuthHFc\nGgPYZV9pDChhAGM8n+7WczgujdlsJQrcgTq8/tnrbNwb45QOgyhEaG5RbZufuwtzapmjLSCBVQC2\nAHC8IovzbSO3SBSl+t07+F4c/uUwKk5UKB0K0RBVVnvl2BRbDZwtQwVcTHqOVmSRa9tILQnwC8DS\nUUuRXZaND6Z/oHQ4RCNUWfIzSunG2TJUQMPvK7Ikuv0cPS1dJcScoXOws3onKn+uVDoUohGqTH5G\nKd2kpJjAcZYWj3Xo8DCGDv0RublJDku5jp7jLFEaSaeATki5OQVrdqxROhSiEaqs9l4s3ZQCKMLF\nEOsBmHRXumlKblZrxmXLUN3rsmrv+DmOE6XRLLx5Ibg8DsdOH8ON196odDhE5VQ5zi8r60WsWnUA\n9fWXliv3938YFksUsrIekSpEzaKhL5es2LoC5+rOwTrBqnQoRCa6Gue3a9f3LRIfANTXr8Pu3RkK\nRaReRukcctejIx/FgBcGIGNMBnp27ql0OETFqM1P44zSOeSu66+6HtMHTUduea7SoRCVU2Xyox5N\n99EHRWvLRi9DwacFOFN7RulQiIqpMvlRj6b76IOitdDAUPBhPF7a85LSoRAVU2WHB2CMzXjE4KjN\nj+PSnA6VMYrPT34O09smHEk5go4BHZUOh0iIFjOVgVp7VemDwrHb1t+GiWETsWD4AqVDIRKi5Ccx\nxyUsC3JzeUo0KrWzeidm/nMmvkn+Bv6+qhzYQERAKzlLjHpVtcVuL8XKuZvwy7eNGHr/NF0ujEG8\nQx+HbqJeVe1oUUo/EofPE5chZfHFDa+plE6auFXyKywsREREBMLDw7FmTeu5k3/7298QHR2NqKgo\nxMbG4sCBA6IHqjTqVdWOFqX0wzzQGIAjfqOolE5aaDP5NTQ0YNGiRSgsLERlZSXWr1+PgwcPtjgm\nNDQUpaWlOHDgADIyMvDQQw9JFrBSaPiNdrQspfsAZanALdn433lq5SGXtFntraioQFhYGPr06QMA\nmDFjBjZu3IjIyMjmY0aNGtX8/YgRI3D8+HHxI1UYLSigHa1K6ZVTgXHp+F/Po4LPWWq3oygvD/61\ntahv3x6mlBTD7qurF20mvxMnTiAkJKT55+DgYJSXlzs9/pVXXsHEiRPFiU5lJk0aQ8lOA1JSTKiq\nslyq+jI/9PgmDA3814LOV2q34+PFi7Gqqqr5Mcvv31MC1K42k58nO2Jt374dr776Knbs2OHw9/fd\nNxvl5VWor/dFjx4hyMqaJ1oyUesYPCI/R6X0hxc+hkWHZmHfD/swtNdQj85XlJfXIvEBwKqqKmRY\nrZT8FFBcXIzi4mKvz9Nm8gsKCkJ1dXXzz9XV1QgODm513IEDBzBv3jwUFhYiMDDQ4bnKy3ujquo1\nAMCxY8DixeKsPkIrm1xCHwIXOSqlH9n1GHLKcvDeXe95dC7/2lqHj/udPy84PiJcQkICEhISmn9e\nuXKlsBO1tcNRXV0dCw0NZUePHmW1tbUsOjqaVVZWtjjm2LFjjOM4tmvXLqfnAXDFLmXM6Q5lnjKZ\nLJKdW0u0vLObzVbCTCYLi4/PZCaTRZKYz9aeZd3Xdmdf13zt0fMsJlPrNxfA0nlelLhKbDZmMZlY\nZnw8s5hMrMRmE+W8RuFGGnP8PHcO2rRpE+vXrx/jOI6tXr2aMcbYunXr2Lp16xhjjM2ZM4d17dqV\nxcTEsJiYGDZ8+HCHATpKUPHxmYICv1x8fKZk59YSrX4IyJm0M7dnsjkb53j0nBKbjaVxXIsX1cxx\noiQpR+dOE+ncRiFp8hMDlfykp9UPATn/fjW/1bDAnEBW/d9qj55XYrOxdJ5nmfHxLJ3nRUtOUpcq\njUBo8pN1hgfHWVqtPpKcnATAu7aqVr17V5zbKLQ6EFvO2TPdOnXDrJhZeHbXs3iWf9bt542ZNEmS\nzg1qT1SOrMkvN5d3OE7O2w4LGoN3kVY/BORO2o+NegxRL0XBcosF3Tp1k+Qa7qpv397h4w0dOsgc\niQGJXAJ1ytWlqNoqHputhPF8OouPz2Q8n66Zzo7WbX5mSWOfs3EOy9yeKdn53SVle6JRCE1jqljY\ngBYNEI/cA7HFGFqjRMl9eexyxL4ai6Wjl+Kqdle5/TyxZ3o0PTfDaoXf+fNo6NABScnJNH5QBqpI\nflptqzI6McdXyp20+3Xrh7F9xuLlvS/jsVGPufUcqWZ6SNWeqARNTQMUuQTqlKtLKVHtId6PrdN6\nc8W+7/exoGeC2Pm6824dTz2zrik1bEdoGlNFyY86LOQnRqlN680VQ3oNwaCeg/DWgbcwd+jcNo+n\nnlnXtDYNUBXJD6BFA+TmfGXqDLf/DnporjDHmTHvX/MwO2Y2/HxdJ23qmXVNax8OmlngzG4vBc+n\nIyEhCzyfTsuSe0mMUpse1jgcc+MYdO/UHe8ffL/NY00pKbBwXIvH0jgOicnJUoWnKVr7cFBNyc8V\nWrhAfGKU2lw1V2hlgQUfHx+Y48z4U/GfcNeAu1yuYkQ9s66ZUlJgqapqUfVN4zgkqfXDQeS2R6e8\nuZTWG9bVSMpOJq0tsNDQ2MAGvTiIbT60WelQNE+qaYCuCM0tmij5ab1hXY2k7GQSoz1RTr4+vkiN\nTUV2WTaSwtQ9G0bttDRsRxPJT4wqmlaqYXKSqpNJix9W0wdNR8b2DOys3onRIaOVDofIQBPJz9s5\nq9RmKC8t9gL7+/pj2ehlyC7Lxr/u+ZfS4RAZ+PxeZ5b+QgJ3VW9it5fCat1yWRUt0e3ExfPpKCp6\n0sHjGSgsfEJwTMQxRx82HJeG3Fx1j908X38efXP7omhmEQZfN1jpcIibhOYWTZT8AO+qaFqshmmZ\nVgetd/DvgCUjliBnRw7+dufflA6HSEwzJT9vOCv5BQbeg+HDOWr/I83O1J5BaG4oKuZVIDQwVOlw\niBuE5hbNDHL2hqPBuEAaTp1agKKiJ7F48cc0aJoAAK5ufzXmD5uPp3Y+pXQoRGKGKPkBl9oMKyq+\nw6lTNwBIBHCptEftf6TJT7/9hIj8CFQurMT1V12vdDiqpKbVW3Tf5uetpjbDhIQslJRktfo9tf+R\nJj0798R9Uffhud3PYc2ta5QOR3X0som7Iaq9l9PiMAwiv6WjluKv+/6K0+dPKx2K6jhbvWWL1apQ\nRMIYLvnpYTI+kd6N196Iyf0m44WKF5QORXW0tnqLM4ap9jbR6jAMIr8VsSsw9o2xeHTUo+gU0Enp\ncFRD6OotamonBKCNhQ0IUcof/v4Hlrc7T+kwVEXIpktSrvIsNLcYpreXyEdP86grTlTgrn/chcPJ\nhxHgFyD59VRXOnKi1G7HlsuW9kpsY2mvdJ7Hk0VFrR7P4Hk8UVjoVSzU20tUQW/zqG8OuhlhXcPw\nzufv4IGYByS9lpZ6UT1dvUWN7YSG6/Ag0nK+nNUWhSLynjnOjDU71qCRNUp6Hb30ojqixlWeKfkR\nUelxHvX4vuPRuV1nbPxqo6TXUWPpSCxq3AKAqr1EVHocR9m01H12WTb+EPEHl0vde0ONpSOxqHIL\nAK+7WtzkyaW83U+WKEevezA3NDawiPwItrVqq2TXENKLSnS0jL3eGsyNRq/jKH19fLEidgWyy7Ix\nPnS8JNdQZelIx1Q31IUWHiVqdaHhAsLywvD+3e9jeNBwpcMhv9PEklbu7LmrxwZzog/t/Nph6eil\nyC7LVjoUIgJZq71Nq6m4qsbqscGc6MfcoXOx6t+rcPDng4jsEal0OMQLigx1cTXuixYeEI/dXgqe\nT3erxE3c0ymgE5JvTsaaHbTUldYp1uHhrBqr1wZzuVHHkXQWDl+IMGsYvvvvd7jhmhuUDocIJGuH\nB3DpUlrswNDSnFXqOJLW8i3Lcb7+PPIm5CkdiuFpam6vJ3vuqoXWSlLUcSStR0c+ioEvDkTGmAz0\n6NxD6XCIALK2+cXHZ4HnM1S/f6sjWpuzSh1H0urVpRfuHng3cstzlQ6FCCRrya+4OEvOy4lKayWp\nlBQTqqosrTYO11qJW82WjV6GEX8dgeWxy3F1+6uVDod4SHUzPNRKayUp6jiSHteVg4kzYd2n67A8\ndrnS4RAPqW6Gh1o5avPjuDRNVuGJeA6cPICkt5NwZPERdPDX/gIEWiQ0t1Dy80DT3r+XSlKJlPgI\nJr8zGZP7TcbDwx5WOhRDouRHiEJ2fLcD939wP75J/gb+vtSSJDdNzO0lRI9ib4hF8NXBeO/L95QO\nhXiASn4apqVB13q3+dBmrNi6Avsf3i/ZYqdaJ9XmTJoa5Ey8p7VB13qXFJaEtE/SYD9kx+R+k5UO\nR3XUuDlTm9XewsJCREREIDw8HGvWOJ7MnZKSgvDwcERHR+Ozzz4TPUgtKC4ulvV6cg+6lvv+5CTG\nvfn4+CA1NhXZZdmqq+Go4W+nxs2ZXCa/hoYGLFq0CIWFhaisrMT69etx8ODBFsds2rQJhw8fxqFD\nh/Dyyy9jwYIFkgasVnK/weQedK2GfyCpiHVv0wZMw0+//YR/f/dvUc4nFjX87dS4OZPL5FdRUYGw\nsDD06dMHAQEBmDFjBjZubLmD1UcffYQHHri4n+mIESNw+vRpnDx5UrqICQDtDbo2Aj9fPywfvZwW\nO3VAjZszuUx+J06cQEhISPPPwcHBOHHiRJvHHD9+XOQwyZVo3UN1+mP0H3Hg5AF89oMxm3+cUePW\nlS63PdqwYQObO3du889vvfUWW7RoUYtjJk+ezMrKypp/Hj9+PNu7d2+rc+Hielb0RV/0RV+ifwnh\nsrc3KCgI1dXVzT9XV1cjODjY5THHjx9HUFBQq3OprRGYEGJsLqu9w4YNw6FDh/Dtt9/iwoULePfd\ndzFlypQWx0yZMgVvvvkmAGD37t249tprcd1110kXMSGEiMBlyc/f3x/5+fngeR4NDQ2YM2cOIiMj\nUVBQAACYP38+Jk6ciE2bNiEsLAydO3fGa6+9JkvghBDiFUGVZRc2b97M+vfvz8LCwlhOTo7DY5KT\nk1lYWBiLiopi+/btEzsESbV1f2+//TaLiopigwcPZqNHj2b79+9XIEph3PnbMcZYRUUF8/PzY++/\n/76M0XnPnfvbvn07i4mJYQMHDmTx8fHyBuiltu7v559/ZjzPs+joaDZw4ED22muvyR+kQLNnz2Y9\ne/ZkgwYNcnqMp3lF1ORXX1/POI5jR48eZRcuXGDR0dGssrKyxTF2u51NmDCBMcbY7t272YgRI8QM\nQVLu3N/OnTvZ6dOnGWMX34xauT937q3puLFjx7JJkyaxDRs2KBCpMO7c36lTp9iAAQNYdXU1Y+xi\nstAKd+4vMzOTpaamMsYu3lvXrl1ZXV2dEuF6rLS0lO3bt89p8hOSV0Rd2EDv4wLdub9Ro0bhmmuu\nAXDx/rQy7MedewMAq9WKadOmoUcPbe1b4c79vfPOO5g6dWpzp1737t2VCFUQd+6vV69eOHPmDADg\nzJkz6NatG/z9tTHD9ZZbbkFgYKDT3wvJK6ImP72PC3Tn/i73yiuvYOLEiXKE5jV3/3YbN25snsWj\npQn87tzfoUOH8Msvv2Ds2LEYNmwY3nrrLbnDFMyd+5s3bx6+/PJL9O7dG9HR0cjN1c/+I0Lyiqhp\n391/BnbFsBet/BN5Euf27dvx6quvYseOHRJGJB537m3JkiXIyclpXkXjyr+jmrlzf3V1ddi3bx+2\nbduGc+fOYdSoURg5ciTCw8NliNA77tzf6tWrERMTg+LiYlRVVSExMRH79+9Hly5dZIhQep7mFVGT\nn5jjAtXInfsDgAMHDmDevHkoLCx0WVRXE3fube/evZgxYwYAoKamBps3b0ZAQECr4U9q5M79hYSE\noHv37ujYsSM6duyIMWPGYP/+/ZpIfu7c386dO2GxXJwVxHEc+vbti6+//hrDhg2TNVYpCMororVI\nMsbq6upYaGgoO3r0KKutrW2zw2PXrl2a6RBgzL37O3bsGOM4ju3atUuhKIVx594uN2vWLE319rpz\nfwcPHmTjx49n9fX17LfffmODBg1iX375pUIRe8ad+3v00UdZVlYWY4yxH3/8kQUFBbH//Oc/SoQr\nyNGjR93q8HA3r4ha8tP7uEB37u/Pf/4zTp061dwuFhAQgIqKCiXDdos796Zl7txfREQEkpKSEBUV\nBV9fX8ybNw8DBgxQOHL3uHN/aWlpmD17NqKjo9HY2Ii1a9eia9euCkfunnvuuQclJSWoqalBSEgI\nVq5cibq6OgDC84psKzkTQoia0B4ehBBDouRHCDEkSn6EEEOi5EcIMSRKfoQQQ6LkRwgxpP8Hw2v6\nu1f4T6QAAAAASUVORK5CYII=\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# perceptron result\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",
    "print len(d0),len(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18fc1fab",
   "metadata": {},
   "source": [
    "That has worked rather well, but it leaves open a number of questions:\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": "e5e9efed",
   "metadata": {},
   "source": [
    "# Discriminative vs Generative Learning Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8aafc60",
   "metadata": {},
   "source": [
    "We have now seen two fundamentally different kinds of learning algorithms.\n",
    "\n",
    "The Gaussian parametric classifier is a _generative learning algorithm_ because we are trying to estimate the class conditional densities used to generate the samples.\n",
    "\n",
    "Generative learning algorithms attempt to estimate $p(x|c)$.\n",
    "\n",
    "The perceptron learning algorithm is a _discriminative learning algorithm_ because it attempts to optimize parameters in order to achieve the best discrimination of samples in different classes.\n",
    "\n",
    "Discriminative learning algorithms attempt to estimate $P(c|x)$ or discriminant functions $g_c(x)$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e12b255",
   "metadata": {},
   "source": [
    "# The Perceptron Criterion Function"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e76f0bf1",
   "metadata": {},
   "source": [
    "(criterion functions)\n",
    "\n",
    "In the perceptron learning algorithm, we made a change to the weight vector every time a sample was misclassified.\n",
    "\n",
    "In essence, we have been trying to _minimize the number of misclassified samples_\n",
    "\n",
    "We call the number of misclassified samples $J(w) = \\hbox{\\# misclassified samples}$ a _criterion function_.\n",
    "\n",
    "Discriminative learning algorithms are frequently expressed in terms of optimization of criterion functions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad3b5264",
   "metadata": {},
   "source": [
    "(optimization algorithms)\n",
    "\n",
    "The number of misclassified samples is an inconvenient criterion function because it is piecewise constant (it is a collection of step functions), so its gradient is either zero or infinity.\n",
    "\n",
    "Most numerical optimization algorithms use gradients in some form."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c122708",
   "metadata": {},
   "source": [
    "(perceptron criterion function)\n",
    "\n",
    "A better function is to sum up the total amount \n",
    "by which samples on the wrong side of the decision boundary are misclassified.\n",
    "\n",
    "This is zero when the data is separated, but positive if any samples are misclassified.\n",
    "\n",
    "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 < 0\\\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c212cc2",
   "metadata": {},
   "source": [
    "(gradient descent optimization)\n",
    "\n",
    "We can optimize this function by _gradient descent_.\n",
    "That is, we iteratively update the weight vector $w$ by \n",
    "adding a small multiple of the negative of the\n",
    "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": "5ccc3618",
   "metadata": {},
   "source": [
    "(stochastic vs batch gradient descent)\n",
    "\n",
    "This is a _batch update_ rule; that is, we add up all the gradients\n",
    "for each misclassified samples, and only then update the total weight vector.\n",
    "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,\n",
    "this is also called the single sample correction algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89a2f6ca",
   "metadata": {},
   "source": [
    "# Optional Notes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a2ad9ce",
   "metadata": {},
   "source": [
    "## Proof of Convergence"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a0c9e9d",
   "metadata": {},
   "source": [
    "Let's consider a particularly simple case for the single sample\n",
    "correction perceptron learning algorithm: the case where $\\eta = 1$.  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. \n",
    "\n",
    "We also assume that the training vectors are linearly independent."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "967db1d7",
   "metadata": {},
   "source": [
    "Assume that we're updating the weight vector in a sequence of updates; \n",
    "we number the updates as $\\tau=1,2,...$ (we don't need to worry about \n",
    "the vectors that are classified correctly).\n",
    "Let $\\hat{w}$ be a solution vector.\n",
    "Consider now the distance of $w(\\tau+1)$ from some multiple of the solution vector:\n",
    "\n",
    "$$w(\\tau+1) - \\alpha \\hat{w} = (w(\\tau)-\\alpha \\hat{w}) + x_\\tau$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f5f060d",
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d604966f",
   "metadata": {},
   "source": [
    "We know that $w(\\tau) \\cdot x_\\tau\\lt0$ 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||$$\n",
    "\n",
    "We also know that $\\hat{w}\\cdot x_\\tau>0$ (because $\\hat{w}$) is a solution.\n",
    "So, we can choose some $\\alpha$ such that we get a provable reduction\n",
    "in the distance of the weight vector from the true vector.  To choose that, let...\n",
    "\n",
    "$$ \\beta^2 = \\max_i ||x_i||^2$$\n",
    "\n",
    "$$ \\gamma = \\min \\hat{w} x_i $$\n",
    "\n",
    "(This is greater than zero for all vectors.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16c9e9cb",
   "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": "460d7e72",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "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 ||x_i||^2 ||\\hat{w}||^2}{\\min (x_i\\cdot \\hat{w})^2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d066ede",
   "metadata": {},
   "source": [
    "## Non-Separable Case"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a699f0b3",
   "metadata": {},
   "source": [
    "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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f00895cc",
   "metadata": {},
   "source": [
    "## Multi-Class Case"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58cc0320",
   "metadata": {},
   "source": [
    "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": "c83dbc78",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}