{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Perceptron!\n",
    "---\n",
    "\n",
    "We study this algorithm for historical reasons and because its name is awesome.\n",
    "\n",
    "Recall from lecture that it is the following greedy algorithm:\n",
    "$$ \\theta^{(t+1)} = \\theta^{(t)} + \\alpha \\left(y^{(i)} - h_{\\theta}(x^{(i)})\\right)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib notebook\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation\n",
    "import numpy as np\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.zeros( (6,2) )\n",
    "X[:,1] = 1\n",
    "for i in range(6): X[i,0] = i+1\n",
    "X\n",
    "Y = np.zeros( 6 )\n",
    "for i in range(6): Y[i] = 0 if i < 3 else 1\n",
    "(X,Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.scatter(X[:,0], Y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Update Rule\n",
    "---\n",
    "The update rule for perceptrons! So simple! So wow!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def update(x,y,theta, alpha=1e-1):\n",
    "    prediction = 1 if np.dot(theta,x) > 0 else 0\n",
    "    return theta + alpha*(y - prediction)*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def render_thetas(X, Y, thetas, points):\n",
    "    fig, ax = plt.subplots()\n",
    "    xx = np.arange(1,6, 0.1)\n",
    "\n",
    "    def animate(i):\n",
    "        theta = thetas[i]\n",
    "        yy = theta[0]*xx + theta[1]\n",
    "        ax.clear()\n",
    "        ax.set_title(f\"Iteration {i} Example is point {points[i][0]}\")\n",
    "        ax.plot(xx,yy)\n",
    "        ax.scatter(X[:,0], Y)\n",
    "        ax.scatter(X[:,0],np.array(X@theta > 0, dtype=np.float))\n",
    "        time.sleep(1)\n",
    "        return ax\n",
    "    ani = matplotlib.animation.FuncAnimation(fig, animate, frames=len(thetas), repeat=False)\n",
    "    return ani"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_thetas(X,Y):\n",
    "    theta = 1e-2*np.random.randn( 2 )\n",
    "    thetas = []\n",
    "    points = []\n",
    "    for i in range(50):\n",
    "        idx = i % X.shape[0]\n",
    "        theta = update(X[idx,:], Y[idx], theta, alpha=1e-2)\n",
    "        points.append(X[idx])\n",
    "        thetas.append(theta)\n",
    "    return (thetas, points)\n",
    "thetas, points = build_thetas(X,Y)\n",
    "render_thetas(X, Y, thetas, points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Noisy data\n",
    "---\n",
    "The perceptron will converge a perfect (linear) separator and it handles our \"far away\" sample problem... but what happens when there isn't one?!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Y2 = np.zeros( 6 )\n",
    "for i in range(6): Y2[i] = 0 if i < 3 or i == 5 else 1\n",
    "fig, ax = plt.subplots()\n",
    "ax.scatter(X[:,0], Y2)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What do you think happens now?!?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "thetas2, points2 = build_thetas(X,Y2)\n",
    "render_thetas(X, Y2, thetas2, points2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comments\n",
    "---\n",
    "* That it doesn't get a perfect answer isn't troubling: our linear class can't be perfect on these points! (Although historically, this was quite troubling! Took until the 80s to clear this up.)\n",
    "\n",
    "* What is troubling is that it jumps around forever is slightly concerning. Broadly writ, we'll take the view that this is noise in our data, and we'll talk more about how to handl this next.."
   ]
  },
  {
   "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}