{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import random\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_separator():\n",
    "    p1 = np.array([random(), random()])\n",
    "    p2 = np.array([random(), random()])\n",
    "    \n",
    "    #v is a vector orthogonal to p1->p2\n",
    "    d = (p2[1]-p1[1],p1[0]-p2[0]) \n",
    "\n",
    "    #if angle between d and p1->p2 is less than 90,\n",
    "    #then it is on one side of the line containing p1 and p2.\n",
    "    #Otherwise, it is on the other side.\n",
    "    def sep(p):\n",
    "        v = p-p1\n",
    "        if np.dot(v,d) > 0:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "    return sep\n",
    "\n",
    "def generate_data(n, separator):\n",
    "      \n",
    "    data = []\n",
    "    Y = []\n",
    "    for _ in range(n):\n",
    "        x = np.array([random(), random()])\n",
    "        data.append(np.array([1,x[0],x[1]]))\n",
    "        \n",
    "        Y.append(separator(x))\n",
    "        \n",
    "    return data, Y\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([array([ 1.        ,  0.35013412,  0.04465456]),\n",
       "  array([ 1.        ,  0.23817193,  0.14952078]),\n",
       "  array([ 1.        ,  0.41158375,  0.0374665 ]),\n",
       "  array([ 1.        ,  0.87463945,  0.93374851]),\n",
       "  array([ 1.        ,  0.97438633,  0.97100039]),\n",
       "  array([ 1.        ,  0.58135   ,  0.49672657]),\n",
       "  array([ 1.        ,  0.75894212,  0.57618606]),\n",
       "  array([ 1.        ,  0.10616376,  0.67048477]),\n",
       "  array([ 1.        ,  0.21371601,  0.81160833]),\n",
       "  array([ 1.        ,  0.12049503,  0.47699181])],\n",
       " [1, 1, 1, -1, -1, 1, 1, 1, 1, 1])"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sep = generate_separator()\n",
    "generate_data(10, sep)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def lpa(data,Y):\n",
    "    missed = True\n",
    "    w = np.array([0,0,0])\n",
    "    n = 0\n",
    "    while missed:\n",
    "        missed = False\n",
    "        \n",
    "        for x,y in zip(data,Y):\n",
    "            \n",
    "            c = np.sign(np.dot(w, x))\n",
    "            if c != y:\n",
    "                missed = True\n",
    "                w = w + y*x\n",
    "        n += 1\n",
    "    return w, n\n",
    "\n",
    "def classify(w, x):\n",
    "    return np.sign(np.dot(w, x))\n",
    "        \n",
    "def estimate_E_out(w, sep):\n",
    "    e = 0\n",
    "    for _ in range(500):\n",
    "        x = np.array([random(), random()])\n",
    "        x_ = np.array([1, x[0], x[1]])\n",
    "        if sep(x) != classify(w, x_):\n",
    "            e += 1\n",
    "    return e / 500.\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(192.395, 0.013767999999999926)"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count = 0\n",
    "sum_es = 0\n",
    "for _ in range(1000):\n",
    "    \n",
    "    sep = generate_separator()\n",
    "    w, n = lpa(*generate_data(100, sep))\n",
    "    \n",
    "    sum_es += estimate_E_out(w, sep)\n",
    "    count += n\n",
    "    \n",
    "(count / 1000., sum_es / 1000.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}