perceptron.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# We'll use the PyPlot (matplotlib) plotting library:\n",
    "# It works exactly as it would in Python.\n",
    "using PyPlot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: you can add text written in Markdown to this notebook to explain your work and your conclusions by adding a new cell (using the \"+\" icon on the toolbar), and setting it to be a markdown cell (by toggling the \"Code\" dropdown on the toolbar to say \"Markdown\" instead). \n",
    "\n",
    "For examples of how to use Markdown, look at the examples in this notebook, or [this cheatsheet](https://github.com/adam-p/markdown-here/wiki/Markdown-Cheatsheet)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generate data\n",
    "Generate 50 random datapoints in 2 dimensions.\n",
    "Note that the last column is fixed at 1 to capture the offset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# don't change this: it sets the random number generator, \n",
    "# so everyone in the class will have consistent results\n",
    "srand(17)\n",
    "\n",
    "# set dimensions\n",
    "n = 50\n",
    "d = 2\n",
    "# generate input: the rows of X are the data points\n",
    "# notice the last column encodes the offset\n",
    "X = [randn(n, d) ones(n)]\n",
    "\n",
    "# Generate the target function w♮\n",
    "# Store the correct decision for each datapoint in y\n",
    "w♮ = randn(d+1)\n",
    "y = sign(X*w♮);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# plot data points X and color according to y\n",
    "clf()\n",
    "hold(true)\n",
    "axis(\"off\")\n",
    "for i=1:n\n",
    "    plot(X[i,1], X[i,2], y[i]==1 ? \"ro\" : \"bd\")\n",
    "end\n",
    "\n",
    "# set figure limits\n",
    "ylim([-2,2])\n",
    "xlim([-2,2])\n",
    "savefig(\"perceptron_data_hw1.eps\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "\"\"\"\n",
    "This function takes data points X, plots them, and colors them correctly according to y.\n",
    "This function also plots the line w'*x = 0.\n",
    "We are plotting just the first two dimensions of x; \n",
    "the last (offset) coordinate of w sets the offset of the line from the origin.\n",
    "\"\"\"\n",
    "function plot_perceptron(X,y,w)\n",
    "    # plot data points X and color according to y\n",
    "    clf()\n",
    "    hold(true)\n",
    "    axis(\"off\")\n",
    "    for i=1:n\n",
    "        plot(X[i,1], X[i,2], y[i]==1 ? \"ro\" : \"bd\")\n",
    "    end\n",
    "    \n",
    "    # plot vector w\n",
    "    x1samples = [minimum(X[:,1]), maximum(X[:,1])]\n",
    "    if w[2]!=0\n",
    "        plot(x1samples, [-(w[1]*x1 + w[3])/w[2] for x1 in x1samples], color=\"black\")\n",
    "    end\n",
    "    \n",
    "    # set figure limits\n",
    "    ylim([-2,2])\n",
    "    xlim([-2,2])\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Double check our function by plotting the points with the truth vector \n",
    "plot_perceptron(X,y,w♮)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# a) Code the missing parts of the Perceptron algorithm\n",
    "Inputs to Perceptron are: \n",
    "* required arguments:\n",
    "    * X = data points\n",
    "    * Y = true values\n",
    "* optional arguments:\n",
    "    * maxsteps = maximum number of updates to w (default: 100)\n",
    "    * w = initial guess of w (default: random)\n",
    "\n",
    "Perceptron should start with the input guess of w, make at most maxsteps updates, and return the final w."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "function perceptron(X,y;\n",
    "                    maxsteps=100, # \n",
    "                    w = rand(size(X,2))) # initial guess for w\n",
    "    \n",
    "    ## YOUR CODE HERE ##\n",
    "    \n",
    "    return w\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# b) Run perceptron on linearly separable data set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "w_final = perceptron(X,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# c) Run perceptron on data sets of size n = 20, 100, and 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# d) Run perceptron on data set of size n = 1000 with dimension d = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# e) Run perceptron on dataset from (d) 100 times.\n",
    "Plot a histogram for the number of updates that the algorithm takes to converge.\n",
    "\n",
    "For this portion, make sure your perceptron implementation picks the next consideration point x(t) randomly instead of deterministically."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# g) Add an outlier. What happens?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# (re)generate data with same random seed\n",
    "srand(17)\n",
    "# set dimensions\n",
    "n = 50\n",
    "d = 2\n",
    "# generate input\n",
    "X = [randn(n, d) ones(n)]\n",
    "w♮ = randn(d+1)\n",
    "y = sign(X*w♮);\n",
    "y[1] *= -1 # flip classification of the first data point\n",
    "\n",
    "# run the perceptron and see what happens\n",
    "perceptron(X,y,maxsteps=50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# h) Try out one idea to fix perceptron"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.4.6",
   "language": "julia",
   "name": "julia-0.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.4.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}