{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "## Perceptron\r\n",
    "\r\n",
    "> This notebook is a part of [AI for Beginners Curricula](http://github.com/microsoft/ai-for-beginners). Visit the repository for complete set of learning materials.\r\n",
    "\r\n",
    "As we have discussed, perceptron allows you to solve **binary classification problem**, i.e. to classify input examples into two classes - we can call them **positive** and **negative**.\r\n",
    "\r\n",
    "First, let's import some required libraries."
   ],
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "source": [
    "import pylab\r\n",
    "from matplotlib import gridspec\r\n",
    "from sklearn.datasets import make_classification\r\n",
    "import numpy as np\r\n",
    "from ipywidgets import interact, interactive, fixed\r\n",
    "import ipywidgets as widgets\r\n",
    "import pickle\r\n",
    "import os\r\n",
    "import gzip\r\n",
    "\r\n",
    "# pick the seed for reproducability - change it to explore the effects of random variations\r\n",
    "np.random.seed(1)\r\n",
    "import random"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Toy Problem\r\n",
    "\r\n",
    "To begin with, let's start with a toy problem, where we have two input features. For example, in medicine we may want to classify tumours into benign and malignant, depending on its size and age.\r\n",
    "\r\n",
    "We will generate a random classification dataset using `make_classification` function from SciKit Learn library:"
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "source": [
    "n = 50\r\n",
    "X, Y = make_classification(n_samples = n, n_features=2,\r\n",
    "                           n_redundant=0, n_informative=2, flip_y=0)\r\n",
    "Y = Y*2-1 # convert initial 0/1 values into -1/1\r\n",
    "X = X.astype(np.float32); Y = Y.astype(np.int32) # features - float, label - int\r\n",
    "\r\n",
    "# Split the dataset into training and test\r\n",
    "train_x, test_x = np.split(X, [ n*8//10])\r\n",
    "train_labels, test_labels = np.split(Y, [n*8//10])\r\n",
    "print(\"Features:\\n\",train_x[0:4])\r\n",
    "print(\"Labels:\\n\",train_labels[0:4])"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Features:\n",
      " [[-1.7441838  -1.3952037 ]\n",
      " [ 2.5921783  -0.08124504]\n",
      " [ 0.9218062   0.91789985]\n",
      " [-0.8437018  -0.18738253]]\n",
      "Labels:\n",
      " [-1 -1  1 -1]\n"
     ]
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Let's also plot the dataset:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "source": [
    "def plot_dataset(suptitle, features, labels):\r\n",
    "    # prepare the plot\r\n",
    "    fig, ax = pylab.subplots(1, 1)\r\n",
    "    #pylab.subplots_adjust(bottom=0.2, wspace=0.4)\r\n",
    "    fig.suptitle(suptitle, fontsize = 16)\r\n",
    "    ax.set_xlabel('$x_i[0]$ -- (feature 1)')\r\n",
    "    ax.set_ylabel('$x_i[1]$ -- (feature 2)')\r\n",
    "\r\n",
    "    colors = ['r' if l>0 else 'b' for l in labels]\r\n",
    "    ax.scatter(features[:, 0], features[:, 1], marker='o', c=colors, s=100, alpha = 0.5)\r\n",
    "    fig.show()\r\n",
    "\r\n",
    "plot_dataset('Training data', train_x, train_labels)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stderr",
     "text": [
      "<ipython-input-4-ade59d2ee664>:11: UserWarning: Matplotlib is currently using module://ipykernel.pylab.backend_inline, which is a non-GUI backend, so cannot show the figure.\n",
      "  fig.show()\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/png": "[encoded data, 21032 characters]",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     }
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Perceptron\r\n",
    "\r\n",
    "Since perceptron is a binary classifier, for each input vector $x$ the output of our perceptron would be either +1 or -1, depending on the class. The output will be computed using the formula\r\n",
    "\r\n",
    "$$y(\\mathbf{x}) = f(\\mathbf{w}^{\\mathrm{T}}\\mathbf{x})$$\r\n",
    "\r\n",
    "where $\\mathbf{w}$ is a weight vector, $f$ is a step activation function:\r\n",
    "$$\r\n",
    "f(x) = \\begin{cases}\r\n",
    "         +1 & x \\geq 0 \\\\\r\n",
    "         -1 & x < 0\r\n",
    "       \\end{cases} \\\\\r\n",
    "$$\r\n",
    "\r\n",
    "However, a generic linear model should also have a bias, i.e. ideally we should compute $y$ as $y=f(\\mathbf{w}^{\\mathrm{T}}\\mathbf{x})+\\mathbf{b}$. To simplify our model, we can get rid of this bias term by adding one more dimension to our input features, which always equals to 1:"
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "source": [
    "pos_examples = np.array([ [t[0], t[1], 1] for i,t in enumerate(train_x) \r\n",
    "                          if train_labels[i]>0])\r\n",
    "neg_examples = np.array([ [t[0], t[1], 1] for i,t in enumerate(train_x) \r\n",
    "                          if train_labels[i]<0])\r\n",
    "print(pos_examples[0:3])"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[[ 0.92180622  0.91789985  1.        ]\n",
      " [-1.06435513  1.49764717  1.        ]\n",
      " [ 0.32839951  2.25677919  1.        ]]\n"
     ]
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Training Algorithm\r\n",
    "\r\n",
    "In order to train the perceptron, we need to find out weights $\\mathbf{w}$ that will minimize the error. The error is defined using **perceptron criteria**:\r\n",
    "\r\n",
    "$$E(\\mathbf{w}) = -\\sum_{n \\in \\mathcal{M}}\\mathbf{w}^{\\mathrm{T}}\\mathbf{x}_{n}t_{n}$$\r\n",
    " \r\n",
    "  * $t_{n} \\in \\{-1, +1\\}$ for negative and positive training samples, respectively\r\n",
    "  * $\\mathcal{M}$ - a set of wrongly classified examples\r\n",
    "  \r\n",
    "We will use the process of **graident descent**. Starting with some initial random weights $\\mathbf{w}^{(0)}$, we will adjust weights on each step of the training using the gradient of $E$:\r\n",
    "\r\n",
    "$$\\mathbf{w}^{\\tau + 1}=\\mathbf{w}^{\\tau} - \\eta \\nabla E(\\mathbf{w}) = \\mathbf{w}^{\\tau} + \\eta \\mathbf{x}_{n} t_{n}$$\r\n",
    "\r\n",
    "where $\\eta$ is a **learning rate**, and $\\tau\\in\\mathbb{N}$ - number of iteration.\r\n",
    "\r\n",
    "Let's define this algorithm in Python:"
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "source": [
    "def train(positive_examples, negative_examples, num_iterations = 100):\r\n",
    "    num_dims = positive_examples.shape[1]\r\n",
    "    \r\n",
    "    # Initialize weights. \r\n",
    "    # We initialize with 0 for simplicity, but random initialization is also a good idea\r\n",
    "    weights = np.zeros((num_dims,1)) \r\n",
    "    \r\n",
    "    pos_count = positive_examples.shape[0]\r\n",
    "    neg_count = negative_examples.shape[0]\r\n",
    "    \r\n",
    "    report_frequency = 10\r\n",
    "    \r\n",
    "    for i in range(num_iterations):\r\n",
    "        # Pick one positive and one negative example\r\n",
    "        pos = random.choice(positive_examples)\r\n",
    "        neg = random.choice(negative_examples)\r\n",
    "\r\n",
    "        z = np.dot(pos, weights)   \r\n",
    "        if z < 0: # positive example was classified as negative\r\n",
    "            weights = weights + pos.reshape(weights.shape)\r\n",
    "\r\n",
    "        z  = np.dot(neg, weights)\r\n",
    "        if z >= 0: # negative example was classified as positive\r\n",
    "            weights = weights - neg.reshape(weights.shape)\r\n",
    "            \r\n",
    "        # Periodically, print out the current accuracy on all examples \r\n",
    "        if i % report_frequency == 0:             \r\n",
    "            pos_out = np.dot(positive_examples, weights)\r\n",
    "            neg_out = np.dot(negative_examples, weights)        \r\n",
    "            pos_correct = (pos_out >= 0).sum() / float(pos_count)\r\n",
    "            neg_correct = (neg_out < 0).sum() / float(neg_count)\r\n",
    "            print(\"Iteration={}, pos correct={}, neg correct={}\".format(i,pos_correct,neg_correct))\r\n",
    "\r\n",
    "    return weights"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Now let's run the training on our dataset:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "source": [
    "wts = train(pos_examples,neg_examples)\r\n",
    "print(wts.transpose())"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Iteration=0, pos correct=0.2631578947368421, neg correct=0.6190476190476191\n",
      "Iteration=10, pos correct=0.8947368421052632, neg correct=0.8571428571428571\n",
      "Iteration=20, pos correct=0.8421052631578947, neg correct=1.0\n",
      "Iteration=30, pos correct=0.8947368421052632, neg correct=0.9523809523809523\n",
      "Iteration=40, pos correct=0.8947368421052632, neg correct=0.9523809523809523\n",
      "Iteration=50, pos correct=0.9473684210526315, neg correct=0.9047619047619048\n",
      "Iteration=60, pos correct=0.8947368421052632, neg correct=0.9523809523809523\n",
      "Iteration=70, pos correct=0.8947368421052632, neg correct=0.9047619047619048\n",
      "Iteration=80, pos correct=0.8947368421052632, neg correct=0.6190476190476191\n",
      "Iteration=90, pos correct=0.8421052631578947, neg correct=1.0\n",
      "[[-0.66042328  4.90850882 -1.        ]]\n"
     ]
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "As you can see, initial accuracy is around 50%, but it quickly increases to higher values close to 90%.\r\n",
    "\r\n",
    "Let's visualize how classes are separated. Our classification function looks like $\\mathbf{w}^Tx$, and it is greater than 0 for one class, and is below 0 for another. Thus, class separation line is defined by $\\mathbf{w}^Tx = 0$. Since we have only two dimensions $x_0$ and $x_1$, the equation for the line would be $w_0x_0+w_1x_1+w_2 = 0$ (remember that we have explicitly defined an extra dimension $x_2=1$). Let's plot this line:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "source": [
    "def plot_boundary(positive_examples, negative_examples, weights):\r\n",
    "    if np.isclose(weights[1], 0):\r\n",
    "        if np.isclose(weights[0], 0):\r\n",
    "            x = y = np.array([-6, 6], dtype = 'float32')\r\n",
    "        else:\r\n",
    "            y = np.array([-6, 6], dtype='float32')\r\n",
    "            x = -(weights[1] * y + weights[2])/weights[0]\r\n",
    "    else:\r\n",
    "        x = np.array([-6, 6], dtype='float32')\r\n",
    "        y = -(weights[0] * x + weights[2])/weights[1]\r\n",
    "\r\n",
    "    pylab.xlim(-6, 6)\r\n",
    "    pylab.ylim(-6, 6)                      \r\n",
    "    pylab.plot(positive_examples[:,0], positive_examples[:,1], 'bo')\r\n",
    "    pylab.plot(negative_examples[:,0], negative_examples[:,1], 'ro')\r\n",
    "    pylab.plot(x, y, 'g', linewidth=2.0)\r\n",
    "    pylab.show()"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "source": [
    "plot_boundary(pos_examples,neg_examples,wts)"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/png": "[encoded data, 7508 characters]",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     }
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Evaluate on Test Dataset\r\n",
    "\r\n",
    "In the beginning, we have put apart some data to the test dataset. Let's see how accurate our classifier is on this test dataset. In order to do this, we also expand the test dataset with an extra dimension, multiply by weights matrix, and make sure that the obtained value is of the same sign as the label (+1 or -1). We then add together all boolean values and divide by the length of test sample, to obtain the accuracy:"
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "source": [
    "def accuracy(weights, test_x, test_labels):\r\n",
    "    res = np.dot(np.c_[test_x,np.ones(len(test_x))],weights)\r\n",
    "    return (res.reshape(test_labels.shape)*test_labels>=0).sum()/float(len(test_labels))\r\n",
    "\r\n",
    "accuracy(wts, test_x, test_labels)"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "metadata": {},
     "execution_count": 10
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Observing the training process\r\n",
    "\r\n",
    "We have seen before how the accuracy decreases during training. It would be nice to see how the separation line behaves during training. The code below will visualize everything on one graph, and you should be able to move the slider to \"time-travel\" through the training process. "
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "source": [
    "def train_graph(positive_examples, negative_examples, num_iterations = 100):\r\n",
    "    num_dims = positive_examples.shape[1]\r\n",
    "    weights = np.zeros((num_dims,1)) # инициализируем веса\r\n",
    "    \r\n",
    "    pos_count = positive_examples.shape[0]\r\n",
    "    neg_count = negative_examples.shape[0]\r\n",
    "    \r\n",
    "    report_frequency = 15;\r\n",
    "    snapshots = []\r\n",
    "    \r\n",
    "    for i in range(num_iterations):\r\n",
    "        pos = random.choice(positive_examples)\r\n",
    "        neg = random.choice(negative_examples)\r\n",
    "\r\n",
    "        z = np.dot(pos, weights)   \r\n",
    "        if z < 0:\r\n",
    "            weights = weights + pos.reshape(weights.shape)\r\n",
    "\r\n",
    "        z  = np.dot(neg, weights)\r\n",
    "        if z >= 0:\r\n",
    "            weights = weights - neg.reshape(weights.shape)\r\n",
    "            \r\n",
    "        if i % report_frequency == 0:             \r\n",
    "            pos_out = np.dot(positive_examples, weights)\r\n",
    "            neg_out = np.dot(negative_examples, weights)        \r\n",
    "            pos_correct = (pos_out >= 0).sum() / float(pos_count)\r\n",
    "            neg_correct = (neg_out < 0).sum() / float(neg_count)\r\n",
    "            snapshots.append((np.copy(weights),(pos_correct+neg_correct)/2.0))\r\n",
    "\r\n",
    "    return np.array(snapshots)\r\n",
    "\r\n",
    "snapshots = train_graph(pos_examples,neg_examples)\r\n",
    "\r\n",
    "def plotit(pos_examples,neg_examples,snapshots,step):\r\n",
    "    fig = pylab.figure(figsize=(10,4))\r\n",
    "    fig.add_subplot(1, 2, 1)\r\n",
    "    plot_boundary(pos_examples, neg_examples, snapshots[step][0])\r\n",
    "    fig.add_subplot(1, 2, 2)\r\n",
    "    pylab.plot(np.arange(len(snapshots[:,1])), snapshots[:,1])\r\n",
    "    pylab.ylabel('Accuracy')\r\n",
    "    pylab.xlabel('Iteration')\r\n",
    "    pylab.plot(step, snapshots[step,1], \"bo\")\r\n",
    "    pylab.show()\r\n",
    "def pl1(step): plotit(pos_examples,neg_examples,snapshots,step)"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "source": [
    "interact(pl1, step=widgets.IntSlider(value=0, min=0, max=len(snapshots)-1))"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "version_major": 2,
       "version_minor": 0,
       "model_id": "8561af1ae77c421f9ca068fe0bdac566"
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=6), Output()), _dom_classes=('widget-interact…"
      ]
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "<function __main__.pl1(step)>"
      ]
     },
     "metadata": {},
     "execution_count": 12
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Limitations of the Perceptron\r\n",
    "\r\n",
    "As you have seen above, perceptron is a **linear classifier**. It can distinguish between two classes well if they are **linearly separable**, i.e. can be separated by a straight line. Otherwise, perceptron training process will not converge.\r\n",
    "\r\n",
    "A most obvious example of a problem that cannot be solved by a perceptron is so-called **XOR problem**. We want our perceptron to learn the XOR boolean function, which has the following truth table:\r\n",
    "\r\n",
    "|   | 0 | 1 |\r\n",
    "|---|---|---|\r\n",
    "| 0 | 0 | 1 | \r\n",
    "| 1 | 1 | 0 |\r\n",
    "\r\n",
    "Let's try and do that! We will manually populate all positive and negative training samples, and then call our train function defined above:"
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "source": [
    "pos_examples_xor = np.array([[1,0,1],[0,1,1]])\r\n",
    "neg_examples_xor = np.array([[1,1,1],[0,0,1]])\r\n",
    "\r\n",
    "snapshots_xor = train_graph(pos_examples_xor,neg_examples_xor,1000)\r\n",
    "def pl2(step): plotit(pos_examples_xor,neg_examples_xor,snapshots_xor,step)"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "source": [
    "interact(pl2, step=widgets.IntSlider(value=0, min=0, max=len(snapshots)-1))"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "version_major": 2,
       "version_minor": 0,
       "model_id": "8f45bf78e4c8471fbc6eea233dde2bf6"
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=6), Output()), _dom_classes=('widget-interact…"
      ]
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "<function __main__.pl2(step)>"
      ]
     },
     "metadata": {},
     "execution_count": 14
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "As you can see from the graph above, the accuracy never goes above 75%, because it is impossible to draw a straight line in such a way as to get all possible examples right.\r\n",
    "\r\n",
    "The XOR problem is a classical example of perceptron limitations, and it was pointed out by Marvin Minsky and Seymour Papert in 1969 in their book [Perceptrons](https://en.wikipedia.org/wiki/Perceptrons_(book)). This observation limited research in the area of neural networks for almost 10 years, even though - and we will see this in the next section of our course - multi-layered perceptrons are perfectly capable of solving such problems.\r\n",
    "\r\n",
    "## Complex Example - MNIST\r\n",
    "\r\n",
    "Even though perceptron cannot solve XOR problem, it can solve many more complex problems, such as handwritten character recognition.\r\n",
    "\r\n",
    "A dataset that is often used when mastering machine learning is called [MNIST](https://en.wikipedia.org/wiki/MNIST_database). It has been created by Modified National Institute of Standards and Technology, and contains a training set of 60000 handwritten digits, collected from around 250 students and employees of the institute. There is also a test dataset of 10000 digits, collected from different individuals.\r\n",
    "\r\n",
    "All digits are represented by grayscale images of size 28x28 pixels.\r\n",
    "\r\n",
    "> MNIST Dataset is available as a training competition on [Kaggle](https://www.kaggle.com/c/digit-recognizer), a site that hosts machine learning competitions and contests. Once you learn how to classify MNIST digits, you can submit your solution to Kaggle to see how it is rated among other participants. \r\n",
    "\r\n",
    "We start by loading MNIST dataset:"
   ],
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "source": [
    "# If you are not running this notebook from a cloned repository, you may need to grab the binary dataset file first\r\n",
    "# !wget https://github.com/microsoft/AI-For-Beginners/blob/main/data/mnist.pkl.gz?raw=true\r\n",
    "# In this case correct the link to the dataset below as well.\r\n",
    "\r\n",
    "with gzip.open('../../data/mnist.pkl.gz', 'rb') as mnist_pickle:\r\n",
    "    MNIST = pickle.load(mnist_pickle)"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Let's now plot the dataset:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "source": [
    "print(MNIST['Train']['Features'][0][130:180])\r\n",
    "print(MNIST['Train']['Labels'][0])\r\n",
    "features = MNIST['Train']['Features'].astype(np.float32) / 256.0\r\n",
    "labels = MNIST['Train']['Labels']\r\n",
    "fig = pylab.figure(figsize=(10,5))\r\n",
    "for i in range(10):\r\n",
    "    ax = fig.add_subplot(1,10,i+1)\r\n",
    "    pylab.imshow(features[i].reshape(28,28))\r\n",
    "pylab.show()"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[  0   0 188 255  94   0   0   0   0   0   0   0   0   0   0   0   0   0\n",
      "   0   0   0   0   0   0   0   0   0   0   0 191 250 253  93   0   0   0\n",
      "   0   0   0   0   0   0   0   0   0   0   0   0   0   0]\n",
      "1\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/png": "[encoded data, 25144 characters]",
      "text/plain": [
       "<Figure size 720x360 with 10 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     }
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Because perceptron is a binary classifier, we will limit our problem to recognizing only two digits. The function below will populate positive and negative sample arrays with two given digits (and will also show samples of those digits for clarity)."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "source": [
    "def set_mnist_pos_neg(positive_label, negative_label):\r\n",
    "    positive_indices = [i for i, j in enumerate(MNIST['Train']['Labels']) \r\n",
    "                          if j == positive_label]\r\n",
    "    negative_indices = [i for i, j in enumerate(MNIST['Train']['Labels']) \r\n",
    "                          if j == negative_label]\r\n",
    "\r\n",
    "    positive_images = MNIST['Train']['Features'][positive_indices]\r\n",
    "    negative_images = MNIST['Train']['Features'][negative_indices]\r\n",
    "\r\n",
    "    fig = pylab.figure()\r\n",
    "    ax = fig.add_subplot(1, 2, 1)\r\n",
    "    pylab.imshow(positive_images[0].reshape(28,28), cmap='gray', interpolation='nearest')\r\n",
    "    ax.set_xticks([])\r\n",
    "    ax.set_yticks([])\r\n",
    "    ax = fig.add_subplot(1, 2, 2)\r\n",
    "    pylab.imshow(negative_images[0].reshape(28,28), cmap='gray', interpolation='nearest')\r\n",
    "    ax.set_xticks([])\r\n",
    "    ax.set_yticks([])\r\n",
    "    pylab.show()\r\n",
    "    \r\n",
    "    return positive_images, negative_images"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "We will start by trying to classify between 0 and 1:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "source": [
    "pos1,neg1 = set_mnist_pos_neg(1,0)"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWAAAACqCAYAAACTZZUqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAI8UlEQVR4nO3dS6hV1R8H8H3kKuHzopZIiIgEooYRUYN0IGoZCkqiGSIiDq5Y6ERwEBENGog5UtTIBtee+IAok3yEICImSoMiqFEiKb3z+iqse/+TKP6steUc9z33dzz38xl+WXedlZ77ddPae69aX19fAcDAGxK9AIDBSgEDBFHAAEEUMEAQBQwQRAEDBOloZHCtVnPPGk3V19dXG+jP9L2m2cq+166AAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCNLQoZzce06cOJHN582bl2Rr1qzJjt23b1+/romBM3bs2CQbOXJkduwLL7xQ15xPPPFENt+1a1eS9fT0ZMcePXo0yfr6Bt/ZqK6AAYIoYIAgChggiAIGCGITro2cPHkyyZ588sns2N7e3iQbjJsg96JRo0Yl2TPPPJMd+8477yRZR0dzfu0nTpyYZJMmTcqO7e7uTrKtW7dmx3733XeV1tXKXAEDBFHAAEEUMEAQBQwQRAEDBKk1svNdq9Vsk7eAl156KZu//PLLSTZ06NDs2P379yfZunXrsmNv3rzZwOqq6evrqw3Yh/2jVb/XnZ2d2fztt99OskWLFjV5Nc33ww8/ZPMlS5Yk2TfffJMde/Xq1X5dU38p+167AgYIooABgihggCAKGCCITbgWt3Tp0iR7//33s2OHDRuWZF9++WV27Jw5c5Ls2rVrjS2uCWzC/WfhwoXZ/MiRIwO8ktazYcOGbL5nz54BXkl9bMIBtBgFDBBEAQMEUcAAQRQwQBAvZG8RZS+ufuWVV5Isd7dDURTFr7/+mmS5x5OLojXueOA/s2fPTrItW7YErOT/bdq0KckuX76cHbt58+YkKztBuapt27Zl819++SXJDhw40JQ19AdXwABBFDBAEAUMEEQBAwTxKHKAxx9/PMnefPPN7NiZM2fWPe+qVauS7IMPPqh/YS1gsD6KfPDgwSR79tlnK897/vz5JPv888/r/vk33ngjyb766qvs2BEjRiTZ2LFjs2NzG2O534tGHTp0KMmWL19eed6qPIoM0GIUMEAQBQwQRAEDBFHAAEE8itxEq1evzubd3d1JVnY3Su6U1xMnTmTHHj16tIHVEaFWy9/kMWRItWuh3B0wRVEUP/74Y5J99tlnlT6rzI0bN+rKiqIoPv300yR77LHHsmMb+bOZNm1aki1evDg79vDhw3XP2yyugAGCKGCAIAoYIIgCBgjiUeR+MmHChCQ7fvx4dmzu8eKyv4d9+/Yl2dq1axtc3b2j3R9FnjVrVjb/4osvKs07efLkbH7p0qVK8w6kZcuWZfOq7/Mte8y/q6ur0ryN8CgyQItRwABBFDBAEAUMEEQBAwTxKPJd6OzsTLJjx44l2YwZM+qes+yU4o8++qjuOWh9U6ZMqTxHT09Pkt2+fbvyvNHOnDmTzXP/vaNHj272cgaEK2CAIAoYIIgCBgiigAGC2IS7C7nTXxs5vThn0qRJ2bxsc4570++//155jnPnziXZb7/9VnneaFeuXMnmR44cSbKVK1fWPe/TTz+dzUeOHJlk169fr3ve/uAKGCCIAgYIooABgihggCDeB3wH48ePz+a5p94eeeSRuuc9e/Zsks2dOzc79s8//6x73nbQTu8Dzj2t9e2332bHPvDAA5U+qx3eB1xm0aJFSfbxxx9XnnfcuHFJ1qzNTO8DBmgxChggiAIGCKKAAYIoYIAgHkW+g507d2bz3Mm2ubtJyt5vOn/+/CQbbHc7DAYdHemvV9W7HQaj77//PnoJTeMKGCCIAgYIooABgihggCA24f6Re+x46tSpdf987lDErVu3ZsfacBsccu/+fffdd7NjV61a1eTV0IpcAQMEUcAAQRQwQBAFDBBEAQMEGXR3QZQ9Cvree+8l2aOPPpod+8cffyTZ+vXrk+zw4cMNro520tvbm2THjx/Pjq16F8SBAweyee6x94E++bdenZ2d2by7u7vSvHv27Mnm/XFCdVWugAGCKGCAIAoYIIgCBggy6E5F7urqyua7du2qe45Tp04lWdmpxjSmnU5FzhkzZkw2P3nyZJI1ctJ2mfPnzyfZli1b6l5Ds9x///1J9vrrr2fHrl69uu55b926lWTTp0/Pjr148WLd81blVGSAFqOAAYIoYIAgChggiAIGCNLWd0E8//zzSbZ79+7s2FGjRiVZ2anGK1asSLIrV640uDpy2v0uiDKzZ89OsrLv6owZMyp91unTp7P5xo0b6/r5np6ebD5s2LAku++++7Jjc48XP/zww3V9/p0cOnQoyZYvX1553qrcBQHQYhQwQBAFDBBEAQMEaYtNuLLHOy9cuJBkU6ZMqXveZcuWZfMPP/yw7jlozGDdhMvJbfYWRVG89dZbSTZixIhmL+dfP/30UzYfPnx4kg3kuoqiKFauXJlk+/fvH9A15NiEA2gxChggiAIGCKKAAYIoYIAgbXEq8pIlS7J5I3c85IwePbrSz0MVZbv3Dz74YJJt37692cv5V+5l6s109erVJCs7WOGTTz5p9nL6lStggCAKGCCIAgYIooABgrTFJtzt27ezeW9vb5INGZL/N+fvv/9OsoceeqjawqAJ9u7dm2QLFizIjl24cGGzl9Nvbty4kc2fe+65JDt27FizlzMgXAEDBFHAAEEUMEAQBQwQRAEDBGmLF7KX+frrr5OsoyN/48drr72WZLmTW2kuL2S/O2WnD8+fPz/JnnrqqezYF198MclqtfSvo6wzcmN37NiRHfvqq68m2V9//ZUdm3sU+V7jhewALUYBAwRRwABBFDBAkLbehOPeYxOOdmQTDqDFKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCdDQ4/ueiKC42YyFQFMXkoM/1vaaZSr/XDR1LD0D/8b8gAIIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYL8D+KUFeSspSmeAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {}
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "source": [
    "def plotit2(snapshots_mn,step):\r\n",
    "    fig = pylab.figure(figsize=(10,4))\r\n",
    "    ax = fig.add_subplot(1, 2, 1)\r\n",
    "    pylab.imshow(snapshots_mn[step][0].reshape(28, 28), interpolation='nearest')\r\n",
    "    ax.set_xticks([])\r\n",
    "    ax.set_yticks([])\r\n",
    "    pylab.colorbar()\r\n",
    "    ax = fig.add_subplot(1, 2, 2)\r\n",
    "    ax.set_ylim([0,1])\r\n",
    "    pylab.plot(np.arange(len(snapshots_mn[:,1])), snapshots_mn[:,1])\r\n",
    "    pylab.plot(step, snapshots_mn[step,1], \"bo\")\r\n",
    "    pylab.show()\r\n",
    "def pl3(step): plotit2(snapshots_mn,step)\r\n",
    "def pl4(step): plotit2(snapshots_mn2,step)    "
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "source": [
    "snapshots_mn = train_graph(pos1,neg1,1000)    \r\n",
    "interact(pl3, step=widgets.IntSlider(value=0, min=0, max=len(snapshots_mn) - 1))"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "version_major": 2,
       "version_minor": 0,
       "model_id": "afbc754ef0d04c95a1af039574b46a6b"
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=66), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "<function __main__.pl3(step)>"
      ]
     },
     "metadata": {},
     "execution_count": 21
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Please note how accuracy goes up to almost 100% very fast.\r\n",
    "\r\n",
    "Please, move the slider to some position towards the end of the training, and observe the weight matrix plotted on the left. This matrix will allow you to understand how perceptron actually works. You can see the high weight values in the middle of the field, which correspond to pixels that are typically present for digit 1, and low negative values by the sides, where parts of 0 digit are. So, if the digit presented to the perceptron is in fact 1, middle part of it will be mupliplied by high values, producing positive result. On the contrary, when perceptron observes 0, corresponding pixels will be multiplied by negative numbers.\r\n",
    "\r\n",
    "> You may notice that if we give our perceptron a digit 1 slightly shifted horizontally, so that its pixels occupy the place where there are vertical parts of 0, we may receive incorrect result. Since the nature of our MNIST dataset is such that all digits are centered and positioned properly, and perceptron relies on this to distinguish between digits.\r\n",
    "\r\n",
    "Now let's try different digits: "
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "source": [
    "pos2,neg2 = set_mnist_pos_neg(2,5)"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWAAAACqCAYAAACTZZUqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAI90lEQVR4nO3dT4hVZR8H8HPfphJxLKzQippFZIOGTFEZFNEuxE3YIjAKFxYoKkqMItGqiCjEhSARWRkVgqCbyAKFslqJC/9ubKOgKP6JcuHoQPfdvBAvz+/Uvc2993e98/ksvzxzzsPM8cvB8zznNJrNZgVA7/0newIA05UCBkiigAGSKGCAJAoYIIkCBkgy1M7gRqNhzRpd1Ww2G70+p+uabqu7rt0BAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyQZyp5ANz3yyCNF9sQTT/Ts/CtXrgzz559/vsi2bt0ajj18+HCR7d+/Pxx74cKF1icHLRgdHS2ytWvXhmNvv/32Ips7d244dunSpS3P4dChQ0W2Z8+ecOy+ffuK7OjRoy2fq9fcAQMkUcAASRQwQBIFDJBEAQMkaTSbzdYHNxqtD+6huiet0WqBBQsWdHs6Xffdd9+FeTtPlvtVs9ls9Pqc/Xpdd8vw8HCYv/fee0X22muvFdmsWbNaPlejEf852+mddkxMTBTZ7t27w7ErVqzoyhwidde1O2CAJAoYIIkCBkiigAGSDMRW5E8++STMB+GBW2TRokXZU+AmMTIyUmQ//vhjOPaBBx5o6ZjffvttmE9OThZZrx/CPfbYY0X28ssvh2N///33IhsfHw/H3rhxY2oTq+EOGCCJAgZIooABkihggCQKGCDJQKyCgOkuehl6VVXV119/XWQPPvhgODZambBr164ie/XVV8Of//PPP/9uij0RbZNevnx5OHbZsmVFNnPmzHCsVRAAA0YBAyRRwABJFDBAkoF4H/Drr78e5h999FGPZ9Ib586dC/NWt5L2M+8D/nfqrvXo30bd9uAvv/yyyNavX19kV65caW9yeB8wQL9RwABJFDBAEgUMkEQBAyQZiFUQs2fPDvOjR48WWTsrBU6ePBnmn376aZH99ttvRbZjx46Wz9UOqyA6q1+v63ZcvHgxzO+6664i+/zzz8OxGzZsKLLopeW0zyoIgD6jgAGSKGCAJAoYIMlAvA/4jz/+CPMXX3yxyOq+oPzVV18V2c6dO8Ox0VbMuuNCpy1ZsqTI7rjjjnBs9JA9ethWVVN/4HbnnXcW2dBQXDHRvC5fvjyl89+M3AEDJFHAAEkUMEASBQyQRAEDJBmIrcjtqHtaPNUnwNH24Llz507pmHX2798f5i+88EJXztdLtiL/pe5Lxz/88EORPfXUUy0f95Zbbml57L333ltkq1atCsdGebQVuqqq6vr160X28ccfh2PHx8eLrFtfKe4WW5EB+owCBkiigAGSKGCAJAOxFbkd7TxsGxkZCfO33367yIaHh//1nP7OTz/9VGQrVqzoyrnoL3XXVDsP3L755psiW7lyZTh206ZNRXbPPfe0PK923HbbbUW2Zs2acOylS5eK7J133pnyHPqBO2CAJAoYIIkCBkiigAGSTLudcO04cuRImD/66KMdP9fExESYR+9YnZyc7Pj5+4WdcH+59dZbwzzaCfnss8+2fNxGI/4Vt9oFhw4dCvNjx461PIeXXnqpyOp2qZ4/f77IHn/88XDshQsXWp5DL9kJB9BnFDBAEgUMkEQBAyRRwABJpt1W5DrRE+dou2QnRCsetmzZEo4d5BUP/L26v/1bb71VZAcOHAjHRtf11atXw7HRl8Hff//9Ijtz5kz48+2IVm1EK36qKn4n8UMPPRSO7ddVEHXcAQMkUcAASRQwQBIFDJDEQ7j/id6FOn/+/K6ca86cOUUWfaQQIj///HORLVy4MBwbfYDz2rVr4dhOPFxrVbTtuW4r9OXLl4vs7NmzHZ9TBnfAAEkUMEASBQyQRAEDJFHAAEmm3SqI0dHRMO/Gl4brvsDczkvwoRW//vpr9hRCdf/e7r///paPcfjw4SI7ffr0v55TP3EHDJBEAQMkUcAASRQwQJKBfgg3NjZWZHv27AnHjoyMdPz8b775ZpjfuHGj4+eCfrRz584wnzVrVsvH2Lt3b6em03fcAQMkUcAASRQwQBIFDJBEAQMkGehVEM8880yRdWO1Q1VV1YkTJ4rs4MGDXTlX9KXbqqqqhx9+uCvnO3/+fJFduXKlK+fi5rVhw4Yie/LJJ8Ox0Xb8HTt2hGM/++yzqU2sj7kDBkiigAGSKGCAJAoYIMlAP4TrpeirtFu3bg3HHjlyZErnqtvGuW7duikdt873339fZMuWLQvHTkxMdGUO9I/nnnsuzLds2VJkjUYjHHv16tUie/fdd8Oxk5OTbczu5uIOGCCJAgZIooABkihggCQKGCDJQK+CiLbQRk9fq6qqhoeHO37+pUuXtpVna+d3MzQ00JfOtDRz5swiW7NmTZGNj4+HPx9tL65bwbBx48YiO3PmzD9NceC4AwZIooABkihggCQKGCBJI/qP89rBjUbrg/vUL7/8EuZPP/10j2fSG9GDyKqKt33Wje3lV2mbzWa8d7WLbrbrevHixUV23333hWOjv90bb7wRjl27dm2RLViwoM3Z/b8PPvggzDdv3jyl495s6q5rd8AASRQwQBIFDJBEAQMkUcAASabdftJXXnklzLdt21ZkdS+ernsheq9cv349zA8cOFBkdU+bjx8/3tE50Tvz5s0rsi+++CIce+3atSK7++67w7Gtrog6depUmEdfNf7www9bOuZ05Q4YIIkCBkiigAGSKGCAJNNuK3I76t7bO3v27CJbvXp1kW3fvr3jc6qq+i8P93LLcLfYivzPxsbGiqxui/2MGTOKrO5LxdHXuqNrKnrYVlVVdfbs2TDHVmSAvqOAAZIoYIAkChggiQIGSGIVBH3FKggGkVUQAH1GAQMkUcAASRQwQBIFDJBEAQMkUcAASRQwQBIFDJBEAQMkUcAASRQwQBIFDJBEAQMkUcAASYbaHH+pqqrT3ZgIVFU1knRe1zXdVHtdt/VCdgA6x39BACRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyT5L95QHHzClR5NAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {}
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "source": [
    "snapshots_mn2 = train_graph(pos2,neg2,1000)\r\n",
    "interact(pl4, step=widgets.IntSlider(value=0, min=0, max=len(snapshots_mn2) - 1))"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "version_major": 2,
       "version_minor": 0,
       "model_id": "bf6f25d14c3b4d548ac026af97f70e2a"
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=66), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "<function __main__.pl4(step)>"
      ]
     },
     "metadata": {},
     "execution_count": 23
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Discussion\r\n",
    "\r\n",
    "For some reason, 2 and 5 are not as easily separable. Even though we get relatively high accuracy (above 85%), we can clearly see how perceptron stops learning at some point.\r\n",
    "\r\n",
    "To understand why this happens, we can try to use [Principal Component Analysis](https://en.wikipedia.org/wiki/Principal_component_analysis) (PCA). It is a machine learning technique used to lower the dimensionality of the input dataset, in such a way as to obtain the best separability between classes. \r\n",
    "\r\n",
    "In our case, an input image has 784 pixels (input features), and we want to use PCA to reduce the number of parameter to just 2, so that we can plot them on the graph. Those two parameters would be a linear combination of original features, and we can view this procedure as \"rotating\" our original 784-dimensional space and observing it's projection to our 2D-space, until we get the best view that separates the classes."
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "source": [
    "from sklearn.decomposition import PCA\r\n",
    "\r\n",
    "def pca_analysis(positive_label, negative_label):\r\n",
    "    positive_images, negative_images = set_mnist_pos_neg(positive_label, negative_label)\r\n",
    "    M = np.append(positive_images, negative_images, 0)\r\n",
    "\r\n",
    "    mypca = PCA(n_components=2)\r\n",
    "    mypca.fit(M)\r\n",
    "    \r\n",
    "    pos_points = mypca.transform(positive_images[:200])\r\n",
    "    neg_points = mypca.transform(negative_images[:200])\r\n",
    "\r\n",
    "    pylab.plot(pos_points[:,0], pos_points[:,1], 'bo')\r\n",
    "    pylab.plot(neg_points[:,0], neg_points[:,1], 'ro')"
   ],
   "outputs": [],
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "source": [
    "pca_analysis(1,0)"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWAAAACqCAYAAACTZZUqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAI8UlEQVR4nO3dS6hV1R8H8H3kKuHzopZIiIgEooYRUYN0IGoZCkqiGSIiDq5Y6ERwEBENGog5UtTIBtee+IAok3yEICImSoMiqFEiKb3z+iqse/+TKP6steUc9z33dzz38xl+WXedlZ77ddPae69aX19fAcDAGxK9AIDBSgEDBFHAAEEUMEAQBQwQRAEDBOloZHCtVnPPGk3V19dXG+jP9L2m2cq+166AAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCNLQoZzce06cOJHN582bl2Rr1qzJjt23b1+/romBM3bs2CQbOXJkduwLL7xQ15xPPPFENt+1a1eS9fT0ZMcePXo0yfr6Bt/ZqK6AAYIoYIAgChggiAIGCGITro2cPHkyyZ588sns2N7e3iQbjJsg96JRo0Yl2TPPPJMd+8477yRZR0dzfu0nTpyYZJMmTcqO7e7uTrKtW7dmx3733XeV1tXKXAEDBFHAAEEUMEAQBQwQRAEDBKk1svNdq9Vsk7eAl156KZu//PLLSTZ06NDs2P379yfZunXrsmNv3rzZwOqq6evrqw3Yh/2jVb/XnZ2d2fztt99OskWLFjV5Nc33ww8/ZPMlS5Yk2TfffJMde/Xq1X5dU38p+167AgYIooABgihggCAKGCCITbgWt3Tp0iR7//33s2OHDRuWZF9++WV27Jw5c5Ls2rVrjS2uCWzC/WfhwoXZ/MiRIwO8ktazYcOGbL5nz54BXkl9bMIBtBgFDBBEAQMEUcAAQRQwQBAvZG8RZS+ufuWVV5Isd7dDURTFr7/+mmS5x5OLojXueOA/s2fPTrItW7YErOT/bdq0KckuX76cHbt58+YkKztBuapt27Zl819++SXJDhw40JQ19AdXwABBFDBAEAUMEEQBAwTxKHKAxx9/PMnefPPN7NiZM2fWPe+qVauS7IMPPqh/YS1gsD6KfPDgwSR79tlnK897/vz5JPv888/r/vk33ngjyb766qvs2BEjRiTZ2LFjs2NzG2O534tGHTp0KMmWL19eed6qPIoM0GIUMEAQBQwQRAEDBFHAAEE8itxEq1evzubd3d1JVnY3Su6U1xMnTmTHHj16tIHVEaFWy9/kMWRItWuh3B0wRVEUP/74Y5J99tlnlT6rzI0bN+rKiqIoPv300yR77LHHsmMb+bOZNm1aki1evDg79vDhw3XP2yyugAGCKGCAIAoYIIgCBgjiUeR+MmHChCQ7fvx4dmzu8eKyv4d9+/Yl2dq1axtc3b2j3R9FnjVrVjb/4osvKs07efLkbH7p0qVK8w6kZcuWZfOq7/Mte8y/q6ur0ryN8CgyQItRwABBFDBAEAUMEEQBAwTxKPJd6OzsTLJjx44l2YwZM+qes+yU4o8++qjuOWh9U6ZMqTxHT09Pkt2+fbvyvNHOnDmTzXP/vaNHj272cgaEK2CAIAoYIIgCBgiigAGC2IS7C7nTXxs5vThn0qRJ2bxsc4570++//155jnPnziXZb7/9VnneaFeuXMnmR44cSbKVK1fWPe/TTz+dzUeOHJlk169fr3ve/uAKGCCIAgYIooABgihggCDeB3wH48ePz+a5p94eeeSRuuc9e/Zsks2dOzc79s8//6x73nbQTu8Dzj2t9e2332bHPvDAA5U+qx3eB1xm0aJFSfbxxx9XnnfcuHFJ1qzNTO8DBmgxChggiAIGCKKAAYIoYIAgHkW+g507d2bz3Mm2ubtJyt5vOn/+/CQbbHc7DAYdHemvV9W7HQaj77//PnoJTeMKGCCIAgYIooABgihggCA24f6Re+x46tSpdf987lDErVu3ZsfacBsccu/+fffdd7NjV61a1eTV0IpcAQMEUcAAQRQwQBAFDBBEAQMEGXR3QZQ9Cvree+8l2aOPPpod+8cffyTZ+vXrk+zw4cMNro520tvbm2THjx/Pjq16F8SBAweyee6x94E++bdenZ2d2by7u7vSvHv27Mnm/XFCdVWugAGCKGCAIAoYIIgCBggy6E5F7urqyua7du2qe45Tp04lWdmpxjSmnU5FzhkzZkw2P3nyZJI1ctJ2mfPnzyfZli1b6l5Ds9x///1J9vrrr2fHrl69uu55b926lWTTp0/Pjr148WLd81blVGSAFqOAAYIoYIAgChggiAIGCNLWd0E8//zzSbZ79+7s2FGjRiVZ2anGK1asSLIrV640uDpy2v0uiDKzZ89OsrLv6owZMyp91unTp7P5xo0b6/r5np6ebD5s2LAku++++7Jjc48XP/zww3V9/p0cOnQoyZYvX1553qrcBQHQYhQwQBAFDBBEAQMEaYtNuLLHOy9cuJBkU6ZMqXveZcuWZfMPP/yw7jlozGDdhMvJbfYWRVG89dZbSTZixIhmL+dfP/30UzYfPnx4kg3kuoqiKFauXJlk+/fvH9A15NiEA2gxChggiAIGCKKAAYIoYIAgbXEq8pIlS7J5I3c85IwePbrSz0MVZbv3Dz74YJJt37692cv5V+5l6s109erVJCs7WOGTTz5p9nL6lStggCAKGCCIAgYIooABgrTFJtzt27ezeW9vb5INGZL/N+fvv/9OsoceeqjawqAJ9u7dm2QLFizIjl24cGGzl9Nvbty4kc2fe+65JDt27FizlzMgXAEDBFHAAEEUMEAQBQwQRAEDBGmLF7KX+frrr5OsoyN/48drr72WZLmTW2kuL2S/O2WnD8+fPz/JnnrqqezYF198MclqtfSvo6wzcmN37NiRHfvqq68m2V9//ZUdm3sU+V7jhewALUYBAwRRwABBFDBAkLbehOPeYxOOdmQTDqDFKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCKGCAIAoYIIgCBgiigAGCdDQ4/ueiKC42YyFQFMXkoM/1vaaZSr/XDR1LD0D/8b8gAIIoYIAgChggiAIGCKKAAYIoYIAgChggiAIGCKKAAYL8D+KUFeSspSmeAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {}
    },
    {
     "output_type": "display_data",
     "data": {
      "image/png": "[encoded data, 14112 characters]",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     }
    }
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "source": [
    "pca_analysis(2,5)"
   ],
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWAAAACqCAYAAACTZZUqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAI90lEQVR4nO3dT4hVZR8H8HPfphJxLKzQippFZIOGTFEZFNEuxE3YIjAKFxYoKkqMItGqiCjEhSARWRkVgqCbyAKFslqJC/9ubKOgKP6JcuHoQPfdvBAvz+/Uvc2993e98/ksvzxzzsPM8cvB8zznNJrNZgVA7/0newIA05UCBkiigAGSKGCAJAoYIIkCBkgy1M7gRqNhzRpd1Ww2G70+p+uabqu7rt0BAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyQZyp5ANz3yyCNF9sQTT/Ts/CtXrgzz559/vsi2bt0ajj18+HCR7d+/Pxx74cKF1icHLRgdHS2ytWvXhmNvv/32Ips7d244dunSpS3P4dChQ0W2Z8+ecOy+ffuK7OjRoy2fq9fcAQMkUcAASRQwQBIFDJBEAQMkaTSbzdYHNxqtD+6huiet0WqBBQsWdHs6Xffdd9+FeTtPlvtVs9ls9Pqc/Xpdd8vw8HCYv/fee0X22muvFdmsWbNaPlejEf852+mddkxMTBTZ7t27w7ErVqzoyhwidde1O2CAJAoYIIkCBkiigAGSDMRW5E8++STMB+GBW2TRokXZU+AmMTIyUmQ//vhjOPaBBx5o6ZjffvttmE9OThZZrx/CPfbYY0X28ssvh2N///33IhsfHw/H3rhxY2oTq+EOGCCJAgZIooABkihggCQKGCDJQKyCgOkuehl6VVXV119/XWQPPvhgODZambBr164ie/XVV8Of//PPP/9uij0RbZNevnx5OHbZsmVFNnPmzHCsVRAAA0YBAyRRwABJFDBAkoF4H/Drr78e5h999FGPZ9Ib586dC/NWt5L2M+8D/nfqrvXo30bd9uAvv/yyyNavX19kV65caW9yeB8wQL9RwABJFDBAEgUMkEQBAyQZiFUQs2fPDvOjR48WWTsrBU6ePBnmn376aZH99ttvRbZjx46Wz9UOqyA6q1+v63ZcvHgxzO+6664i+/zzz8OxGzZsKLLopeW0zyoIgD6jgAGSKGCAJAoYIMlAvA/4jz/+CPMXX3yxyOq+oPzVV18V2c6dO8Ox0VbMuuNCpy1ZsqTI7rjjjnBs9JA9ethWVVN/4HbnnXcW2dBQXDHRvC5fvjyl89+M3AEDJFHAAEkUMEASBQyQRAEDJBmIrcjtqHtaPNUnwNH24Llz507pmHX2798f5i+88EJXztdLtiL/pe5Lxz/88EORPfXUUy0f95Zbbml57L333ltkq1atCsdGebQVuqqq6vr160X28ccfh2PHx8eLrFtfKe4WW5EB+owCBkiigAGSKGCAJAOxFbkd7TxsGxkZCfO33367yIaHh//1nP7OTz/9VGQrVqzoyrnoL3XXVDsP3L755psiW7lyZTh206ZNRXbPPfe0PK923HbbbUW2Zs2acOylS5eK7J133pnyHPqBO2CAJAoYIIkCBkiigAGSTLudcO04cuRImD/66KMdP9fExESYR+9YnZyc7Pj5+4WdcH+59dZbwzzaCfnss8+2fNxGI/4Vt9oFhw4dCvNjx461PIeXXnqpyOp2qZ4/f77IHn/88XDshQsXWp5DL9kJB9BnFDBAEgUMkEQBAyRRwABJpt1W5DrRE+dou2QnRCsetmzZEo4d5BUP/L26v/1bb71VZAcOHAjHRtf11atXw7HRl8Hff//9Ijtz5kz48+2IVm1EK36qKn4n8UMPPRSO7ddVEHXcAQMkUcAASRQwQBIFDJDEQ7j/id6FOn/+/K6ca86cOUUWfaQQIj///HORLVy4MBwbfYDz2rVr4dhOPFxrVbTtuW4r9OXLl4vs7NmzHZ9TBnfAAEkUMEASBQyQRAEDJFHAAEmm3SqI0dHRMO/Gl4brvsDczkvwoRW//vpr9hRCdf/e7r///paPcfjw4SI7ffr0v55TP3EHDJBEAQMkUcAASRQwQJKBfgg3NjZWZHv27AnHjoyMdPz8b775ZpjfuHGj4+eCfrRz584wnzVrVsvH2Lt3b6em03fcAQMkUcAASRQwQBIFDJBEAQMkGehVEM8880yRdWO1Q1VV1YkTJ4rs4MGDXTlX9KXbqqqqhx9+uCvnO3/+fJFduXKlK+fi5rVhw4Yie/LJJ8Ox0Xb8HTt2hGM/++yzqU2sj7kDBkiigAGSKGCAJAoYIMlAP4TrpeirtFu3bg3HHjlyZErnqtvGuW7duikdt873339fZMuWLQvHTkxMdGUO9I/nnnsuzLds2VJkjUYjHHv16tUie/fdd8Oxk5OTbczu5uIOGCCJAgZIooABkihggCQKGCDJQK+CiLbQRk9fq6qqhoeHO37+pUuXtpVna+d3MzQ00JfOtDRz5swiW7NmTZGNj4+HPx9tL65bwbBx48YiO3PmzD9NceC4AwZIooABkihggCQKGCBJI/qP89rBjUbrg/vUL7/8EuZPP/10j2fSG9GDyKqKt33Wje3lV2mbzWa8d7WLbrbrevHixUV23333hWOjv90bb7wRjl27dm2RLViwoM3Z/b8PPvggzDdv3jyl495s6q5rd8AASRQwQBIFDJBEAQMkUcAASabdftJXXnklzLdt21ZkdS+ernsheq9cv349zA8cOFBkdU+bjx8/3tE50Tvz5s0rsi+++CIce+3atSK7++67w7Gtrog6depUmEdfNf7www9bOuZ05Q4YIIkCBkiigAGSKGCAJNNuK3I76t7bO3v27CJbvXp1kW3fvr3jc6qq+i8P93LLcLfYivzPxsbGiqxui/2MGTOKrO5LxdHXuqNrKnrYVlVVdfbs2TDHVmSAvqOAAZIoYIAkChggiQIGSGIVBH3FKggGkVUQAH1GAQMkUcAASRQwQBIFDJBEAQMkUcAASRQwQBIFDJBEAQMkUcAASRQwQBIFDJBEAQMkUcAASYbaHH+pqqrT3ZgIVFU1knRe1zXdVHtdt/VCdgA6x39BACRRwABJFDBAEgUMkEQBAyRRwABJFDBAEgUMkEQBAyT5L95QHHzClR5NAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {}
    },
    {
     "output_type": "display_data",
     "data": {
      "image/png": "[encoded data, 15032 characters]",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     }
    }
   ],
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "As you can see, 0 and 1 can be clearly separated by a straight line. This indicates that in the original 784-dimensional space dots corresponding to digits are also linearly separable. In the case of 2 and 5, we cannot find the good projection that will separate the digits clearly, and thus there are some cases of wrong classification.\r\n",
    "\r\n",
    "> Later on this course we will learn how to create non-linear classifiers using Neural Networks, and how to deal with a problem of digits not being properly aligned. Very soon we will reach above 99% accuracy in MNIST digit classification, while classifying them into 10 different classes.\r\n",
    "\r\n",
    "## Takeaway\r\n",
    "\r\n",
    " * We have leart about the simplest neural network architecture - one-layer perceptron.\r\n",
    " * We have implemented the perceptron \"by hand\", using simple training procedure based on gradient descent\r\n",
    " * Despite simplicity, one-layered perceptron can solve rather complex problems of handwritten digit recognition\r\n",
    " * One-layered perceptron is a liner classifier, and thus it provides the same classification power as logistic regression.\r\n",
    " * In the sample space, perceptron can separate two classes of input data using hyperplane."
   ],
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Credits\r\n",
    "\r\n",
    "This notebook is a part of [AI for Beginners Curricula](http://github.com/microsoft/ai-for-beginners), and has been prepared by [Dmitry Soshnikov](http://soshnikov.com). It is inspired by Neural Network Workshop at Microsoft Research Cambridge. Some code and illustrative materials are taken from presentations by [Katja Hoffmann](https://www.microsoft.com/en-us/research/people/kahofman/), [Matthew Johnson](https://www.microsoft.com/en-us/research/people/matjoh/) and [Ryoto Tomioka](https://www.microsoft.com/en-us/research/people/ryoto/), and from [NeuroWorkshop](http://github.com/shwars/NeuroWorkshop) repository."
   ],
   "metadata": {}
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3.8.0 64-bit (conda)"
  },
  "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.8.0"
  },
  "livereveal": {
   "start_slideshow_at": "selected"
  },
  "interpreter": {
   "hash": "16aeaa504b544176258e5caf576fc030dfd6fff62d0c15825e7863ff13e121ff"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}