Copy_of_NB01_NaiveLearning_PythonBasics.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.4"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {
        "height": "442px",
        "width": "387px"
      },
      "number_sections": false,
      "sideBar": true,
      "skip_h1_title": false,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {
        "height": "calc(100% - 180px)",
        "left": "10px",
        "top": "150px",
        "width": "165px"
      },
      "toc_section_display": true,
      "toc_window_display": true
    },
    "colab": {
      "name": "Copy of NB01_NaiveLearning_PythonBasics.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "toc_visible": true,
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/aedanr/UTS_ML_S19/blob/master/Copy_of_NB01_NaiveLearning_PythonBasics.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "id": "2xcV0BA3Z9UC",
        "colab_type": "text"
      },
      "source": [
        "# 1 Model of Learning Procedure"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "kXnK9eb_Z9UE",
        "colab_type": "text"
      },
      "source": [
        "## Naive Learning"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "dE3dFRDJZ9UF",
        "colab_type": "text"
      },
      "source": [
        "We implement the naive learning scheme. More specifically we want to represent a map from of $X$ to $y$ intuitively -- by using a complete table of all possibilities exhaustively. To make it possible, we limit $X$ to be a discrete 2D tuple -- be one of a dot in a 2D square array, you will see examples shortly -- and $y$ to be 0 or 1. \n",
        "\n",
        "- Build a `Python object` to represent all the possible relationship between $X$ and $y$\n",
        "- Given a training sample, i.e. a pair of $X$ and $y$, the learning-model object can eliminate all the possibilities that are incompatible with the observation.\n",
        "- Given a test sample, i.e. an $X$ without $y$, the learning-model object can return all the possibilities and their respective $y$-values at the test $X$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "4nYeACj9Z9UF",
        "colab_type": "text"
      },
      "source": [
        "### Represent All X-Samples"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "flRkurOVZ9UG",
        "colab_type": "text"
      },
      "source": [
        "#### Attempt Round 1"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [],
        "hidden": true,
        "id": "SwrBiw0XZ9UH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def generate_all_X_space_samples():\n",
        "    \"\"\"\n",
        "    As the function name shows,  here we want to return the \n",
        "    complete set of possible X values. The straightforward \n",
        "    implementation of the X-space is a list of tuples. Let us \n",
        "    consider a simple range: the integers from 0 to N-1, and \n",
        "    use this range for both dimensions. Say N=3, we want to \n",
        "    generate X-samples as\n",
        "    [\n",
        "        (0, 0),\n",
        "        (0, 1),\n",
        "        (0, 2),\n",
        "        (1, 0),\n",
        "        (1, 1),\n",
        "        (1, 2),\n",
        "        (2, 0),\n",
        "        (2, 1),\n",
        "        (2, 2),\n",
        "    ]\n",
        "    \n",
        "    For small N, we can explicitly write out the list, but we need \n",
        "    a program to generate such a list for arbitrary N:\n",
        "    \"\"\"\n",
        "    \n",
        "    # Let's make an empty list\n",
        "    X_space = []\n",
        "    \n",
        "    # Study the elements in the example list, and fill up our\n",
        "    # X_space, e.g. by\n",
        "    X_space.append((0, 0)) # A sample in X is a tuple, so we use \n",
        "    # a pair of parentheses, i.e. the input to the \"append\" function\n",
        "    # is \"(0, 0)\", not \"0, 0\", which will be interpreted as 2 inputs.\n",
        "    X_space.append((0, 1))\n",
        "    X_space.append((0, 2))\n",
        "    # ... you can complete the rest if you wish, but better read on.\n",
        "    # we will use smarter methods.\n",
        "    \n",
        "    # Last but note least, \n",
        "    return X_space"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "xjHxQ3fYZ9UJ",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "In the cell below, experiment with the function `generate_all_X_space_samples` we just defined. You can manipulate the definition of the function  and  observe the change of its behaviour. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "ECU9qLT7Z9UJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X_space = generate_all_X_space_samples()\n",
        "print(X_space)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "Y35dIrvYZ9UP",
        "colab_type": "text"
      },
      "source": [
        "#### Attempt Round 2"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "JmzKwWfZZ9UQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def generate_all_X_space_samples():\n",
        "    \"\"\"\n",
        "    We will use loops to generate the tuples!\n",
        "    \"\"\"\n",
        "    \n",
        "    # Let's make an empty list\n",
        "    X_space = []\n",
        "    \n",
        "    # Simple observation shows the first 3 tuples are (0, j)\n",
        "    # and j is running from 0 to 3 (exclusive, Python convention)\n",
        "    \n",
        "    # This is the perfect case to use a for-loop, so we can write the\n",
        "    # list building program this way:\n",
        "    \n",
        "    # for j in range(3):\n",
        "    #     X_space.append((0, j))\n",
        "    # for j in range(3):\n",
        "    #     X_space.append((1, j))\n",
        "    # for j in range(3):\n",
        "    #     X_space.append((2, j))\n",
        "    \n",
        "    # You may have noticed, the first element in each tuple in those\n",
        "    # loops runs from 0 to 3 (exclusive) as well, and can also be\n",
        "    # managed by a loop\n",
        "    for i in range(3):\n",
        "        for j in range(3):\n",
        "            X_space.append((i, j))\n",
        "    return X_space"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "8vVYt2TGZ9US",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Experiment with the for loop above. Try to generate x spaces of different sizes. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "WLhQGherZ9UT",
        "colab_type": "text"
      },
      "source": [
        "#### Attempt Round 3"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "PIVJDG-YZ9UT",
        "colab_type": "text"
      },
      "source": [
        "We further adjust our implementation in two ways:\n",
        "\n",
        "1. It is natural for the function to be flexible so we can generate different sizes of X conveniently without rewriting the code every time.\n",
        "\n",
        "2. Python provides a more natural way to write loops to generate object collections (e.g. list of objects). \n",
        "\n",
        "Let's try 2 in the cell below and then re-write our X-sample generator."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "0VfgP-D6Z9UU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# 1. building list by appending one element each time\n",
        "my_list_a = []\n",
        "for i in range(5):\n",
        "    my_list_a.append(i**2) # square\n",
        "print(\"List-a of Sqr for [0, 5):\", my_list_a)\n",
        "\n",
        "# 2. Write the message above naturally as python code\n",
        "my_list_b = [i**2 for i in range(5)] # Bracket [..] to construct a list\n",
        "print(\"List-b of Sqr for [0, 5):\", my_list_b)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "GL6HAUugZ9UW",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Try to generate a list of even numbers from 2 to 10 (exclusive)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "llc0VxMkZ9UW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# 3. Powerful generator\n",
        "# The element object can be complex object. \n",
        "# The []-generating loop can be nested.\n",
        "# The generation process can be conditioned, too.\n",
        "\n",
        "my_list_c = [(j, j + i**2) for i in range(10)\n",
        "             if i % 2 == 0\n",
        "             for j in range(100, 600, 100)\n",
        "             if j != 300]\n",
        "print(my_list_c)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "mZyYFslTZ9UY",
        "colab_type": "text"
      },
      "source": [
        "__CAVEAT__: Although looking very neat, internally this kind of generator does not save you any time or space complexity.  It is purely for readability,  so use it only to IMPROVE the readability!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "sd8rfRN_Z9UZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def generate_all_X_space_samples(N):\n",
        "    \"\"\"\n",
        "    Generate complete sample of X-space\n",
        "    :param N: Discrete X-space dimension size. The size is homogeneous\n",
        "      in all dimensions.\n",
        "    :type N: int\n",
        "    \"\"\"\n",
        "    \n",
        "    return [(i, j) for i in range(N)\n",
        "            for j in range(N)]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "ed5O70WpZ9Ud",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "In the cell below, experiment with the new function `generate_all_X_space_samples` we just defined. Please try different X-space sizes and investigate different X-samples."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "4RPcr_APZ9Uf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X = generate_all_X_space_samples(3)\n",
        "print(\"There are {} samples in X-space.\".format(len(X))) # {}-format\n",
        "# is used to inject some information from variables to a string.\n",
        "print(\"All samples:\\n\\t\", X) # \\n: new line, \\t indent\n",
        "\n",
        "# You can also investigate using multiple print's\n",
        "for sample_id in range(len(X)): # Try to figure out the construction\n",
        "    print(\"Sampe {}: {}\".format(sample_id, X[sample_id]))\n",
        "    \n",
        "# You can use [:] indexing to conveniently check a subset of data samples\n",
        "print(\"Sample 1-5 (exc):\", X[1:5])\n",
        "# [:End] means start from 0\n",
        "print(\"Sample 0-3 (exc):\", X[:3])\n",
        "# Similarly, [Start:] means until the end\n",
        "print(\"Sample 3-Last (inc):\", X[3:])\n",
        "# You can use -i (<0 index) to represent \"reversing from the end\"\n",
        "print(\"Last Sample:\", X[-1])\n",
        "print(\"Sample 3-Last (exc):\", X[3:-1])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "Zqfi0AbAZ9Ui",
        "colab_type": "text"
      },
      "source": [
        "#### Attempt Round 4 -- Using Numpy Arrays"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "bqqp3eo8Z9Ul",
        "colab_type": "text"
      },
      "source": [
        "Python list is convenient for us to store and access data samples.  When it comes to doing analysis or machine learning algorithms it is more convenient if we can easily access individual attributes or perform computational operations on specified parts of the data. We will use numpy library, it is designed to manage array data. Numpy arrays can also be easily converted to/from `data frames`, `GPU device arrays`, `images (pixel arrays)`, etc."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "vfOksWAJZ9Ul",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Let us use the numpy library\n",
        "import numpy as np # the \"as\" is optional and to save typing\n",
        "\n",
        "def generate_all_X_space_samples_np(N):\n",
        "    \"\"\"\n",
        "    :param N: X-space will be an N by N discrete-valued array\n",
        "    \"\"\"\n",
        "    \n",
        "    # Let's make an empty list\n",
        "    X_space = np.zeros((N**2, 2)) # the \n",
        "    \n",
        "    # Loop is similar to that in Round2\n",
        "    # except that all samples are created at the\n",
        "    # beginning, and we now use an index to loop over them\n",
        "    index = 0\n",
        "    for i in range(N):\n",
        "        for j in range(N):\n",
        "            X_space[index][0] = i\n",
        "            X_space[index][1] = j\n",
        "            index += 1\n",
        "    return X_space"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "ld3vydRoZ9Un",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X_np = generate_all_X_space_samples_np(3)\n",
        "print(X_np)\n",
        "print(type(X_np)) # Note the type is a np-array\n",
        "# Check out a sample\n",
        "i = 3\n",
        "print(\"An X-Sample[{}]:{}\".format(i, X_np[i]))\n",
        "# Check attribute-0 for all samples\n",
        "j = 0\n",
        "print(\"X-Attribute[{}]:{}\".format(j, X_np[:, j]))\n",
        "# [:, 0]: take from all (:) samples, the attribute-0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "hSbzflF8Z9Up",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Please check (print out) the second (index=1) attribute for samples 1-5 (exclusive). "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "NfZUZ2sBZ9Uq",
        "colab_type": "text"
      },
      "source": [
        "Numpy arrays provide interface to apply computations for all elements. E.g. we may want to scale all elements in $X$ between $[0, 1]$. Numpy arrays provide interface to apply computations for all elements. Using an ordinary Python list,  we need to reconstruct another list to store the result,  and perform the competition element by element."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "JX28fdARZ9Uq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def scale_X_to_0_1(X, N):\n",
        "    \"\"\"\n",
        "    Get a new list scaling the elements in X by 1/N.\n",
        "    \"\"\"\n",
        "    new_list = []\n",
        "    for x in X: # you can iterate over each element (a tuple in x)\n",
        "        # now x is one data sample in X, such as (0, 2)\n",
        "        new_list.append((x[0]/N, x[1]/N))\n",
        "    return new_list"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "zzX_pohdZ9Us",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X = generate_all_X_space_samples(5)\n",
        "X1 = scale_X_to_0_1(X, 5)\n",
        "print(X1)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "RC99NCNAZ9Uv",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# On te other hand, operating on numpy array is much easier\n",
        "X_np = generate_all_X_space_samples_np(5)\n",
        "X1_np = X_np/5\n",
        "print(X1_np)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "TCmptgByZ9Uw",
        "colab_type": "text"
      },
      "source": [
        "Not only the code is more concise. The computation is done internally using fast C implementation, and therefore more efficient."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "p1d-uhXTZ9Ux",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%timeit X1 = scale_X_to_0_1(X, 5)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "71ixssoBZ9Uz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%timeit X1 = X1_np = X_np/5"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "mMWUK_VLZ9U1",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Note the time units $\\mu$s ($10^{-6}$ sec) / ns ($10^{-9}$ sec) used in the measurement above. You can make a larger matrix e.g. using `generate_all_X_space_samples(500)` and compare the difference. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "Ndbxkk4QZ9U1",
        "colab_type": "text"
      },
      "source": [
        "Finally, `numpy` provides an interface to generate this kind of X samples,  by sampling a grid in a multidimensional space. `meshgrid` takes the grid positions at each dimension and returns the grid matrices. In our example, matrix-0 for attribute-1, and matrix-1 for attribute-0 (the order of attributes can be adjusted when we composing the final X, and is not essential). I will not go to details please find more about the function referring to the [doc](https://docs.scipy.org/doc/numpy/reference/generated/numpy.meshgrid.html).\n",
        "\n",
        "Please study the following example for some basic array operations."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "nyQ_sHwhZ9U2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def generate_all_X_space_samples_np(N):\n",
        "    \"\"\"\n",
        "    :param N: X-space will be an N by N discrete-valued array\n",
        "    \"\"\"\n",
        "    X0, X1 = np.meshgrid(np.arange(N), np.arange(N))\n",
        "    # We will have the following for N=3\n",
        "    # X0:      X1:\n",
        "    # 0 1 2    0 0 0\n",
        "    # 0 1 2    1 1 1\n",
        "    # 0 1 2    2 2 2\n",
        "    \n",
        "    # X0, if \"flattened\", becomes\n",
        "    # 0 1 2 0 1 2 0 1 2\n",
        "    \n",
        "    # flattened X0 and X1 if \"stacked\" becomes\n",
        "    # [[0 1 2 0 1 2 0 1 2\n",
        "    #  [0 0 0 1 1 1 2 2 2]]\n",
        "    \n",
        "    # The following matrix, \n",
        "    # [[a b c]\n",
        "    #  [d e f]]\n",
        "    # if \"transposed\" (numpy operator \"T\"), becomes\n",
        "    # [[a d]\n",
        "    #  [b e]\n",
        "    #  [c f]]\n",
        "    return np.stack([X0.flatten(), X1.flatten()]).T"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "5Mm69vxBZ9U8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(generate_all_X_space_samples_np(3))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "XtSGFQFMZ9U_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%timeit generate_all_X_space_samples_np(500)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "uHnO5Qz-Z9VB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%timeit generate_all_X_space_samples(500)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "k7s5Nh6YZ9VE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Finally, we can make version that includes the normalisation \n",
        "# (1/N) in the construction\n",
        "def generate_all_X_space_normalised_samples_np(N):\n",
        "    \"\"\"\n",
        "    :param N: X-space will be an N by N discrete-valued array\n",
        "    \"\"\"\n",
        "    X0, X1 = np.meshgrid(np.arange(N), np.arange(N))\n",
        "    return np.stack([X0.flatten(), X1.flatten()]).T / N"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "0PYGfIiJZ9VI",
        "colab_type": "text"
      },
      "source": [
        "### Represent all possible X-y relations"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "r3ATLIymZ9VI",
        "colab_type": "text"
      },
      "source": [
        "We will create a template from which we can generate objects, which represent  _generic_ relationship from all $X$-samples in to binary $y$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "tad7CNK5Z9VJ",
        "colab_type": "text"
      },
      "source": [
        "#### Initialise the framework"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "sX8x4WRtZ9VJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Let us first prepare the X-space as discrete samples as above. \n",
        "# And before we start building all the possible X-y mappings. \n",
        "# It is sensible to have an idea about how many such \n",
        "# mappings we are going to consider.\n",
        "\n",
        "# So here is our first attempt of making the object template \n",
        "# of the all-inclusive mapping representation.\n",
        "class CompleteDiscrete2DBinaryMapping(object):\n",
        "    \"\"\"\n",
        "    An exhaustive representation of 2D X space to binary targets.\n",
        "    The 2D space is represented using discrete grid points.\n",
        "    \"\"\"\n",
        "    def __init__(self, N):\n",
        "        \"\"\"\n",
        "        Create an object representing all possible mappings from \n",
        "        2D grid points to {0, 1}. \n",
        "        :param N: X-space samples are N by N grid in [0, 1)**2\n",
        "        \"\"\"\n",
        "        self.grid_x = generate_all_X_space_samples_np(N)\n",
        "        self.h_size = 2 ** (N**2)\n",
        "        \n",
        "    def size(self):\n",
        "        \"\"\"\n",
        "        Total number of possible mappings.\n",
        "        \n",
        "        Note this tend to be really large number for any\n",
        "        respectable N.\n",
        "        \"\"\"\n",
        "        return self.h_size"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "FsvSQmi_Z9VL",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "complete_model = CompleteDiscrete2DBinaryMapping(10)\n",
        "print(\"We are going to build {} different mappings.\"\n",
        "       .format(complete_model.size()))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "lx7qXqSVZ9VM",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Please review our discussion in class and figure out why we compute the size of the possible mappings to be $2^{N^2}$? "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "tePUCvahZ9VN",
        "colab_type": "text"
      },
      "source": [
        "So for any respectable problem size,  exclusively consider all possibilities is exceeding the capability of a computer. Can we possibly implement such an object?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "cOkxxCUtZ9VN",
        "colab_type": "text"
      },
      "source": [
        "#### Focus on prediction"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "v4NvFVkOZ9VO",
        "colab_type": "text"
      },
      "source": [
        "Yes and no, we employer implement a representing all possible mappings.  But we cannot wait for it to make any useful predictions,  because it takes very long time to work. The point here we will adopt the _duck-typing_ / interface oriented programming protocol to have some object that works. This way of building programs is widely used in Python (and particularly useful in data science where the storage demand can be very large).\n",
        "\n",
        "Duck-typing: \n",
        "\n",
        "> If something that walks like a duck and the quacks like a duck then it is probably a duck.\n",
        "\n",
        "That is, we focused on how the object will be used and maintaining necessary information in working conditions only. \n",
        "\n",
        "Since we are implementing a data model _family_. At any particular call, we need only to specify the $y$ value (0 or 1) for some $X = (X_1 \\in [0, 1), X_2 \\in [0, 1))$ according to a _particular member_ in this family. That is, we do not need to worry about storing all possible mappings at one time."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "h62mNzRnZ9VO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# To be specific, we just need to implement such a function\n",
        "def predict_according_to_hypothesis(X, hypothesis_id):\n",
        "    \"\"\"\n",
        "    :param X: a data has 2 attributes\n",
        "    :param hypothesis_id: a number in 0..1267650600228229401496703205376 \n",
        "        (e.g. N=10)\n",
        "    NOTE: for stand-alone function (not belonging to any class,\n",
        "        \"unbounded\" is the technical term), we don't have the \"self\"\n",
        "        in the first place in the input argument list.    \n",
        "    \"\"\"\n",
        "    y = 0 # or 1\n",
        "    return y"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "b8148MqEZ9VR",
        "colab_type": "text"
      },
      "source": [
        "#### Predict using one assigned hypothesis"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "7ydIEUiZZ9VR",
        "colab_type": "text"
      },
      "source": [
        "Now we need to solve two problems,\n",
        "1. We need to verify the input X as one of the 2D grid points  according to our problem setting.  If it is not, quantise it to one of them.\n",
        "2. Figure out according to the particular mapping specified by `hypothesis_id` (The technical term of such a hypothetical mapping is a _hypothesis_),  what is the corresponding y value."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "wMXSGtfaZ9VS",
        "colab_type": "text"
      },
      "source": [
        "The first problem can be solved by finding the nearest the neighbour to the input X from all the 2D grid points. This, of course, will remind us the nearest neighbour classifier. There is one essential difference though: there is no training data for our nearest neighbour classifier to refer to, so we have to assign some hypotheses, which leads us to the second problem."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "MK1r3e4iZ9VT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# To compute the nearest neighbour, \n",
        "# please experiment with the following code.\n",
        "X_np = generate_all_X_space_samples_np(2)\n",
        "print(\"2D points\")\n",
        "print(X_np)\n",
        "Xin = np.array((1, 2))\n",
        "print(\"Input X\")\n",
        "print(Xin)\n",
        "print(\"Difference\")\n",
        "print(X_np - Xin)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "5Qus-hq7Z9VW",
        "colab_type": "text"
      },
      "source": [
        "Amazingly, we have implemented the difference between the input $X$ to __each one of the grid points using just one operation__.  This seemingly incompatible substraction has been implemented in numpy using the mechanism _broadcasting_. It allows binary operators to work between one array $A$ of \n",
        "$n_1 \\times n_2 $ and the other $B$ of $n_2$, while considering the larger $A$ to contain $n_1$ small arrays and applying the operation between each of the $n_1$ small arrays and $B$. \n",
        "\n",
        "It also generalises to the case when A is of $n_1 \\times n_2 \\times n_3 \\times n_4$ and B is of $n_3 \\times n_4$. Then we view $A$ as $n_1\\times n_2$ cells and each cell is an $n_3 \\times n_4$ array.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "EpDSTew5Z9VX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# To compute the nearest neighbour\n",
        "diff = X_np - Xin\n",
        "diff_square = diff ** 2 # each element\n",
        "diff_norm2 = diff_square.sum(axis=1) # summing up every row, so now we have \n",
        "# N**2 distances (same number of X-rows) and need only to find the \n",
        "# smallest one."
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "bysiZy6oZ9Va",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(\"The index of the nearest x-grid point is {}\"\n",
        "      .format(np.argmin(diff_norm2))) # argmin returns the index of the \n",
        "# smallest element in an array (take care and read doc for multi-dim arrays)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "-xHSzQ56Z9Vb",
        "colab_type": "text"
      },
      "source": [
        "There we consider what the hypothesis would say about the y value at that particular x-grid point, such as point-3. You may have already guessed as we have totally $N^2$ x-grid points,  and the total number of possible hypotheses is $2^{N^2}$. We are exploring all possible binary combinations with $N^2$ bits. Say, $N=3, N^2=9$, we just count 9-bit binary numbers. And if you ask: what is hypothsis-178’s prediction on the 3rd x-grid point. We can just check the 3rd bit of the binary number corresponding to 178."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "HJYKr8qkZ9Vc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# to convert a number to binary format\n",
        "print(\"{:b}\".format(35))\n",
        "# to specify the number of bits\n",
        "print(\"{:9b}\".format(35))\n",
        "# to specify the number of bits and fill unused bits with 0\n",
        "print(\"{:09b}\".format(35))\n",
        "# to specify the number of bits and fill unused bits with 0\n",
        "# and finally take out the 3rd bit\n",
        "print(\"{:09b}\".format(35) [2])\n",
        "\n",
        "# given N, build the \"formatting\" string (a meta string you use to \n",
        "# format other strings\n",
        "N=3\n",
        "print(\"{:0\" + str(N**2) + \"b}\") # \"+\" concatenates strings"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "a6D-hxKJZ9Ve",
        "colab_type": "text"
      },
      "source": [
        "#### Put everything together"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "K0HimAnwZ9Vf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class CompleteDiscrete2DBinaryMapping(object):\n",
        "    \"\"\"\n",
        "    An exhaustive representation of 2D X space to binary targets.\n",
        "    The 2D space is represented using discrete grid points.\n",
        "    \"\"\"\n",
        "    def __init__(self, N):\n",
        "        \"\"\"\n",
        "        Create an object representing all possible mappings from \n",
        "        2D grid points to {0, 1}. \n",
        "        :param N: X-space samples are N by N grid in [0, 1)**2\n",
        "        \"\"\"\n",
        "        self.grid_x = generate_all_X_space_samples_np(N)\n",
        "        self.dof = N ** 2 # the degrees of freedom is eaqual to the number\n",
        "        # of grid points at which you can freely choose {0/1} as the \n",
        "        # target value. DoF reduces as you start observing data (when you\n",
        "        # observe the target value at a point, you lose the freedom of\n",
        "        # setting it to arbitrary values)\n",
        "        self.h_size = 2 ** self.dof\n",
        "        \n",
        "    def size(self):\n",
        "        \"\"\"\n",
        "        Total number of possible mappings.\n",
        "        \n",
        "        Note this tend to be really large number for any\n",
        "        respectable N.\n",
        "        \"\"\"\n",
        "        return self.h_size\n",
        "    \n",
        "    def predict_according_to_hypothesis(self, X, hypothesis_id):\n",
        "        \"\"\"\n",
        "        Note, when implement as class method, don't miss \"self\"\n",
        "        :param X: a data has 2 attributes\n",
        "        :param hypothesis_id: a number in 0..1267650600228229401496703205376 \n",
        "            (e.g. N=10)\n",
        "        \"\"\"\n",
        "        X = np.array(X) # make the input format more flexible, e.g.\n",
        "        # you can use [0, 2] (Python list), or (0, 1) (Python tuple)\n",
        "        d = ((self.grid_x - X)**2).sum(axis=1)\n",
        "        bit_id = np.argmin(d)\n",
        "        format_string = \"{:0\" + str(self.dof) + \"b}\"\n",
        "        y = int(format_string.format(hypothesis_id) [bit_id])\n",
        "        return y"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "Mfq7GVJtZ9Vh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\n",
        "complete_model = CompleteDiscrete2DBinaryMapping(10)\n",
        "print(\"We are going to build {} different mappings.\"\n",
        "       .format(complete_model.size()))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "XUVNreIjZ9Vk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# This won't stop!\n",
        "for hypothesis_id in range(complete_model.size()):\n",
        "    print(complete_model\n",
        "          .predict_according_to_hypothesis((8, 7), hypothesis_id))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "g20xND5QZ9Vl",
        "colab_type": "text"
      },
      "source": [
        "### Fit to Training Data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "PClZujgHZ9Vl",
        "colab_type": "text"
      },
      "source": [
        "(We will start moving faster from here.) Now suppose we are given training samples in the following format: $\\{x_1 = \\langle(0, 1), 1\\rangle, x_2 = \\langle(3, 4), 0\\rangle\\}$. How would the information affect our belief about the $X$-$y$ mapping?\n",
        "\n",
        "We will introduce a method `fit`, which checks consistency between every hypothesis and the observed data and removes those hypotheses that disagree with the data."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "rZ-sV_cnZ9Vm",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class CompleteDiscrete2DBinaryMapping(object):\n",
        "    def __init__(self, N):\n",
        "        self.grid_x = generate_all_X_space_samples_np(N)\n",
        "        self.dof = N ** 2\n",
        "        self.h_size = 2 ** self.dof\n",
        "        self.inconsistent_hypotheses = []\n",
        "        \n",
        "    def size(self):\n",
        "        return self.h_size\n",
        "    \n",
        "    def predict_according_to_hypothesis(self, X, hypothesis_id):\n",
        "        X = np.array(X)\n",
        "        d = ((self.grid_x - X)**2).sum(axis=1)\n",
        "        bit_id = np.argmin(d)\n",
        "        format_string = \"{:0\" + str(self.dof) + \"b}\"\n",
        "        y = int(format_string.format(hypothesis_id) [bit_id])\n",
        "        return y\n",
        "    \n",
        "    # Let add a `fit` method\n",
        "    def fit(self, X, Y): \n",
        "        \"\"\"\n",
        "        :param X: [M x 2] training data\n",
        "        :param Y: [M] labels\n",
        "        \"\"\"\n",
        "        # Let's check consistency for each training data and each hypothesis \n",
        "        for hid in range(self.h_size):\n",
        "            for x_, y_ in zip(X, Y): \n",
        "                # be careful if the training set contains only 1 sample!\n",
        "                # zip is literally zipping two \"iterables\" so the zipped object\n",
        "                # yield multiple elements in each iteration.\n",
        "                pred = self.predict_according_to_hypothesis(x_, hid)\n",
        "                if pred != y_:\n",
        "                    if hid not in self.inconsistent_hypotheses:\n",
        "                        self.inconsistent_hypotheses.append(hid)\n",
        "                    break # we have determined this hid is bad and no need\n",
        "                    # to continue\n",
        "        \n",
        "        \n",
        "    def predict_trained(self, X):\n",
        "        return [\n",
        "            self.predict_according_to_hypothesis(X, hid)\n",
        "            for hid in range(self.h_size)\n",
        "            if hid not in self.inconsistent_hypotheses\n",
        "        ]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "0WJLUqD1Z9Vn",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Test using the example we have seen in class\n",
        "complete_model = CompleteDiscrete2DBinaryMapping(3)\n",
        "X_trn = [\n",
        "    (0, 2),\n",
        "    (1, 2),\n",
        "    (1, 0),\n",
        "    (1, 1),\n",
        "    (2, 0),\n",
        "    (2, 1),\n",
        "]\n",
        "Y_trn = [0, 0, 1, 1, 1, 1]\n",
        "complete_model.fit(X_trn, Y_trn)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "ksBTxShCZ9Vo",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "complete_model.predict_according_to_hypothesis((0,2), 3)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "DNoRLTpjZ9Vr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Let us use the model to predict\n",
        "complete_model.predict_trained((0, 2))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "lRtiphHRZ9Vt",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Interpret how `predict_trained` works. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "g8xkgg-bZ9Vt",
        "colab_type": "text"
      },
      "source": [
        "__Improvement Idea 1__\n",
        "\n",
        "Let's apply the \"duck-typing\" principle again -- we don't need to explicitly find out all inconsistent hypotheses and exclude them when testing. We can construct hypothesis set that is consistent. \n",
        "\n",
        "\n",
        "__Improvement Idea 2__\n",
        "\n",
        "Try to increase the quantisation number $N$ to $4$ (or $5$ if you are in a more adventurous mood) and see how the model works. Next we will introduce limitations on the possibile hypotheses. See below"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "QA2XX1NlZ9Vu",
        "colab_type": "text"
      },
      "source": [
        "## Data Models (Preview)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "LoLKQRc6Z9Vv",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>PREVIEW EXERCISE</b></span>\n",
        "Figure out how the \"linear\" model below works. Try to introduce a non-trivial threshold when the hypotheses making predictions (See `PREDICTION BY INDIVIDUAL HYPOTHESIS`). "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "YEnmQyGGZ9Vw",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# A Simple Linear Model Family\n",
        "import numpy as np\n",
        "class LinearHypothesisSpace:\n",
        "    def __init__(self, quant_num=3):\n",
        "        self.quant_num = quant_num\n",
        "        grid_x0, grid_x1 = np.meshgrid(np.arange(self.quant_num),\n",
        "                                       np.arange(self.quant_num))\n",
        "        grid_x0 = grid_x0.flatten()\n",
        "        grid_x1 = grid_x1.flatten()\n",
        "        self.grid_x = np.stack([grid_x0, grid_x1]).T\n",
        "\n",
        "        eps_angle = np.pi / 18\n",
        "        angles = np.arange(0, np.pi, eps_angle)\n",
        "        self.hypotheses = np.zeros((2 * len(angles), self.quant_num ** 2),\n",
        "                                   dtype=np.int)\n",
        "        x0 = grid_x0 - (quant_num - 1) / 2\n",
        "        x1 = grid_x1 - (quant_num - 1) / 2\n",
        "        for i, th in enumerate(angles):\n",
        "            w = min(np.tan(th), 9999)\n",
        "            # ** PREDICTION BY INDIVIDUAL HYPOTHESIS **\n",
        "            ya = (x0 * w - x1 > 0).astype(np.int)\n",
        "            yb = 1 - ya\n",
        "            self.hypotheses[2 * i, :] = ya\n",
        "            self.hypotheses[2 * i + 1, :] = yb\n",
        "        self.sele_hypothesis_id = None\n",
        "\n",
        "    def fit(self, x, y):\n",
        "        x_ind = x[:, 0] + self.quant_num * x[:, 1]\n",
        "        pred_trn = self.hypotheses[:, x_ind]\n",
        "        accu_trn = pred_trn == y[np.newaxis, :]  # type: np.ndarray\n",
        "        accu_trn_n = accu_trn.astype(np.float).sum(axis=1)\n",
        "        self.sele_hypothesis_id = np.argmax(accu_trn_n)\n",
        "\n",
        "    def predict_all_X(self, hypothesis_id=-1):\n",
        "        h = self.hypotheses[self.sele_hypothesis_id] \\\n",
        "            if hypothesis_id == -1 \\\n",
        "            else self.hypotheses[hypothesis_id]\n",
        "        return self.grid_x, h"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "H5t4ofYyZ9Vx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "linear_model0 = LinearHypothesisSpace(3)\n",
        "X_trn = np.array([\n",
        "    (0, 2),\n",
        "    (1, 2),\n",
        "    (1, 0),\n",
        "    (1, 1),\n",
        "    (2, 0),\n",
        "    (2, 1),\n",
        "])\n",
        "Y_trn = np.array([0, 0, 1, 1, 1, 1])\n",
        "linear_model0.fit(X_trn, Y_trn)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "w95_VWUVZ9Vy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X_all, y_all = linear_model0.predict_all_X()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "99SHiRQcZ9Vz",
        "colab_type": "text"
      },
      "source": [
        "### Visualing the model behaviour"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "M3kuhqsAZ9Vz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Finally, let us visualise the model behaviour, we will us an interactive \n",
        "# visualision tool.\n",
        "\n",
        "# NOTE drawing graphs is one noticeable difference between running your\n",
        "# Python notebook on cloud (where the computers don't have screens and have\n",
        "# to deliver graphics objects to your browser to render on YOUR screen), and \n",
        "# on local computer (where graphics display natively using graph interface \n",
        "# provided by your local OS). So we make a bit configuration here. \n",
        "#\n",
        "# If the graphs don't work on your computer, try on colab, or you can \n",
        "# change to classical matplotlib library, which is easier to make working.\n",
        "\n",
        "\n",
        "I_AM_RUNNING_THIS_NOTEBOOK_ON_MY_OWN_COMPUTER = True\n",
        "COLAB = not I_AM_RUNNING_THIS_NOTEBOOK_ON_MY_OWN_COMPUTER"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "Q8yJu5MFZ9V2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "if COLAB: # We need to upgrade plotly to 4.0 for it to work with colab\n",
        "    # [as of July 2019] this will obsolete soon when Google upgrades colab\n",
        "    !pip install plotly --upgrade\n",
        "    # Peform the same on your own computer if encountering issues, but only\n",
        "    # do it once and for all. colab is a virtual machine, so you need to\n",
        "    # perform the upgrading each time restarting a session."
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "3lvcI_2IZ9V5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import plotly.graph_objects as go\n",
        "fig = go.Figure(\n",
        "    data=[go.Scatter(\n",
        "        x=X_all[:, 0], \n",
        "        y=X_all[:, 1], \n",
        "        marker_color=y_all,\n",
        "        marker_size=12,\n",
        "        marker_line_width=2,\n",
        "        mode=\"markers\")],\n",
        "    layout_title_text=\"Prediction on a Discretised 2D X-Space\"\n",
        ")\n",
        "if COLAB:\n",
        "    fig.show(renderer=\"colab\")\n",
        "else:\n",
        "    fig.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "gk4yw3H6Z9V6",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Now we can handle decently sized (2D discrete) data space\n",
        "hypothesis_id = 21 # we havn't trained the model, so need to specify which hypo\n",
        "# we want to check\n",
        "linear_model1 = LinearHypothesisSpace(50)\n",
        "X_all, y_all = linear_model1.predict_all_X(hypothesis_id)\n",
        "fig = go.Figure(\n",
        "    data=[go.Scatter(\n",
        "        x=X_all[:, 0], \n",
        "        y=X_all[:, 1], \n",
        "        marker_color=y_all,\n",
        "        marker_size=12,\n",
        "        marker_line_width=2,\n",
        "        mode=\"markers\")],\n",
        "    layout_title_text=\"Prediction on a Discretised 2D X-Space\"\n",
        ")\n",
        "if COLAB:\n",
        "    fig.show(renderer=\"colab\")\n",
        "else:\n",
        "    fig.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "b0wVpzTbZ9V8",
        "colab_type": "text"
      },
      "source": [
        "## Summarise"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "l7J0HAcwZ9V8",
        "colab_type": "text"
      },
      "source": [
        "- We have built a omnipotently useless 2D classifier!\n",
        "- We tried out a linear modeller.\n",
        "- We have learned some useful Python and numpy skills.\n",
        "- We have made nice pictures!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "id": "tqaGfYaXZ9V9",
        "colab_type": "text"
      },
      "source": [
        "# 2 Model Complexity"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "E-HoLYUyZ9V-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Environment and constant preparation\n",
        "import numpy as np\n",
        "from sklearn.datasets import load_iris\n",
        "try:\n",
        "    import plotly.graph_objects as go\n",
        "except:\n",
        "    !pip install plotly==4.1.0\n",
        "from sklearn.tree import DecisionTreeClassifier\n",
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "COLAB = False\n",
        "IRIS_EXPERIMENT_X_SPACE_QUANTISATION_BIN_NUM = 50 # self-interpretation\n",
        "\n",
        "def generate_all_X_space_normalised_samples_np(N):\n",
        "    \"\"\"\n",
        "    :param N: X-space will be an N by N discrete-valued array\n",
        "    \"\"\"\n",
        "    X0, X1 = np.meshgrid(np.arange(N), np.arange(N))\n",
        "    return np.stack([X0.flatten(), X1.flatten()]).T / N"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "A1TqYKplZ9WA",
        "colab_type": "text"
      },
      "source": [
        "We will test models of different complexities on the simplified Iris data."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "R8lP1SocZ9WB",
        "colab_type": "text"
      },
      "source": [
        "## Prepare Iris Data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "fI5QIp49Z9WB",
        "colab_type": "text"
      },
      "source": [
        "Let us first prepare the Iris Data into the simplified format. The simplification steps are\n",
        "1. we consider the problem of detecting Versicolour (as the postitive class, class-1), to make it even simpler, I will consider Setosa as the negative class (class-0)\n",
        "2. we use only the first two attributes\n",
        "3. we will discretise the attributes into 50 \"ticks\" -- This is not necessary for data modelling. This is to be consistent with our experiments on \"how data modelling worked in a grid in the entire X-space\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "txkCWf81Z9WC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# load the data\n",
        "iris_db = load_iris()\n",
        "all_x = generate_all_X_space_normalised_samples_np(\n",
        "    IRIS_EXPERIMENT_X_SPACE_QUANTISATION_BIN_NUM)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "39gYWTRFZ9WE",
        "colab_type": "text"
      },
      "source": [
        "__SHORT-CUT__ The exercises from 2.1.1 to 2.1.4 are for programming skills only. Jump to [2.1.5](#Data-preprocessing-summary) to quickly get preprocessed data, if you want to skip learning programming skills."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "yVnij1rOZ9WF",
        "colab_type": "text"
      },
      "source": [
        "### Exploring the data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "olmMx2xkZ9WF",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:#006000\"><b>EXERCISE</b></span>\n",
        "Follow the following few code cells, experiment with inspecting the dataset. (Adjust the code, observe what you get and try to explain why)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "YlD_r55sZ9WF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# BEGIN Data Inspection"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "GxXcNh6VZ9WI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# load_iris returns an object `iris_db`, but for now, we don't have much \n",
        "# information on the object. We usually start studying unknown objects\n",
        "# in one of the following two steps.\n",
        "\n",
        "# 1. check what is its `type`, and see what the author of the object template \n",
        "# (the class) has to say\n",
        "print(type(iris_db))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "DB2_zyPwZ9WJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Depending on your environment, the result should be something like\n",
        "# <class 'sklearn.utils.Bunch'>\n",
        "# \"Bunch\" is the name of the class, living in the \"utils\" sub-module\n",
        "# which, in turn, is in the \"sklearn\" library.\n",
        "\n",
        "# Now let's get some help of the class. (most popular libraries\n",
        "# are well documented)\n",
        "iris_db?"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "ob12BKCAZ9WK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# As the doc-string doesn't provide much information of this object.\n",
        "# let's try method\n",
        "# 2. duck-typing: check how the object \"quacks\" and \"walks\"\n",
        "dir(iris_db) # dir() lists methods / attributes of an object.\n",
        "\n",
        "# you may find \"DESCR\" to be useful, try to print it out."
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "XCIFftSgZ9WL",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# The most interesting parts of the dataset object are\n",
        "# `data` and `target` of course. Let's check `data`.\n",
        "type(iris_db.data), type(iris_db.target)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "DcCY9rNPZ9WM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# We are familiar with numpy arrays. Perform some standard checks\n",
        "print(iris_db.data.shape, iris_db.target.shape)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "Rpo0ca5-Z9WN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# This looks like 150 data samples with 150 corresponding labels.\n",
        "print(iris_db.data[:10], iris_db.target[:10])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "NY-mZv26Z9WQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# END of Data Inspection"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "qpPpTXpsZ9WS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# just to save typing\n",
        "X, y = iris_db.data, iris_db.target"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "7ZvcHi_cZ9WT",
        "colab_type": "text"
      },
      "source": [
        "### Simplification: Class Setosa vs Versicolor"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "Fc4hL1oZZ9WU",
        "colab_type": "text"
      },
      "source": [
        "Without losing generality, we take a further simplification step by considering only two flower classes. Rather than identifying versicolor from all iris flowers, we distinguish Versicolor from Setosa. Now we take the samples belonging to the first two classes (`target==0` for setosa and `target==1` for versicolor). \n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "Wrd8R5ZIZ9WV",
        "colab_type": "text"
      },
      "source": [
        "#### A note on programming $^{ProgSkill}$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "B5H_DkaBZ9WX",
        "colab_type": "text"
      },
      "source": [
        "(Skip such sections/comments on programming skills (marked with $^{ProgSkill}$) if you feel comfortable to).\n",
        "\n",
        "The hard part is to express an idea in clear and specific terms. It is relatively easy to translate such expressions into any particular programming language. For example, consider the task to take the samples belonging to the first 2 classes and make a subset of the data set.\n",
        "\n",
        "To specify a subset,  we consider the conditions each individual element in the subset should satisfy:  for our task, that is “the target value of this sample is 0 or the target value of this sample is 1”. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "nzJbCBknZ9WY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# So the idea becomes: \n",
        "# for each training sample, (let us identify the training sample \n",
        "# using an index i), \n",
        "# - include the data[i] and the target[i] in the subset, \n",
        "#   if target[i] is 0 or 1.\n",
        "\n",
        "# translating the idea into a program\n",
        "X_sub = []\n",
        "y_sub = []\n",
        "for i in range(len(iris_db.data)): \n",
        "    # [EXERCISE] What does range(len(...)) do \n",
        "    # for an ensemble object? \n",
        "    if iris_db.target[i] == 0 or iris_db.target[i] == 1:\n",
        "        X_sub.append(iris_db.data[i])\n",
        "        y_sub.append(iris_db.target[i])\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "EkNTOpuOZ9WZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Check what we have obtained.\n",
        "print(X_sub[0:5])\n",
        "print(y_sub[0:5])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "6OdPrc8OZ9Wc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# We can organise X_sub and y_sub as numpy arrays.\n",
        "# (so we can access the elements more easily)\n",
        "X_sub = np.array(X_sub)\n",
        "y_sub = np.array(y_sub)\n",
        "print(X_sub[0:5])\n",
        "print(y_sub[0:5])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "TKVQCI7OZ9We",
        "colab_type": "text"
      },
      "source": [
        "Python allows us to express the idea more directly: the for-loop can be constructed using every pair of X and y in the training dataset, without introducing an index. Try the following code block."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "BBEDm4-MZ9We",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Translating the idea into a program\n",
        "X_sub = []\n",
        "y_sub = []\n",
        "for x_, y_ in zip(iris_db.data, iris_db.target): \n",
        "    # [EXERCISE] Print the iteration variables in a zipped list.\n",
        "    # I.e. construct two lists L1 and L2, and make a for loop\n",
        "    # over \"a, b in zip(L1, L2)\", check the values of a and b.\n",
        "    if y_ == 0 or y_ == 1:\n",
        "        X_sub.append(x_)\n",
        "        y_sub.append(y_)\n",
        "X_sub = np.array(X_sub)\n",
        "y_sub = np.array(y_sub)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "Ffe7VZRMZ9Wh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# (*) We can use more \"descriptive\", less \"instructive\" construction\n",
        "X_sub = np.array([x_ for x_, y_ in zip(iris_db.data, iris_db.target)\n",
        "                  if y_ == 0 or y_ == 1])\n",
        "y_sub = np.array([y_ for x_, y_ in zip(iris_db.data, iris_db.target)\n",
        "                  if y_ == 0 or y_ == 1])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "gAkppCrAZ9Wi",
        "colab_type": "text"
      },
      "source": [
        "#### Fast selection using numpy array"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "MIl1hO0tZ9Wi",
        "colab_type": "text"
      },
      "source": [
        "Numpy allows to use boolean conditions as indexes for arrays. Check the [document][bool-ind] for more details.\n",
        "\n",
        "[bool-ind]:https://docs.scipy.org/doc/numpy-1.13.0/user/basics.indexing.html"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "8OPgs9HgZ9Wi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X_sub = X[(y==0) + (y==1)] # \"+\" for boolean OR\n",
        "y_sub = y[(y==0) + (y==1)]\n",
        "\n",
        "# Consolidate following reference to the data\n",
        "X = X_sub\n",
        "y = y_sub"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "4052PFwuZ9Wk",
        "colab_type": "text"
      },
      "source": [
        "### Take the first 2 attributes"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "xLPqWpHIZ9Wk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X = X[:, :2]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "01_K3kGQZ9Wl",
        "colab_type": "text"
      },
      "source": [
        "### Discretise the attributes into 50 \"ticks\" $^{ProgSkill}$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "deeIhx0nZ9Wm",
        "colab_type": "text"
      },
      "source": [
        "We align training samples in the data into grids in X-space. This is mostly for the consistency of demonstration and practice purposes. You can skip this section and the experimental results below would be approximately the same.\n",
        "\n",
        "Simply speaking, it works like as if you ticking the “align to grid” option when organising the icons on your desktop screen. The samples will be “snapped” to the points in a grid in the 2D X-space. This makes the training data part of the “complete X-space points” we will use for demo."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "tvEBy8X7Z9Wm",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "quant_num = IRIS_EXPERIMENT_X_SPACE_QUANTISATION_BIN_NUM\n",
        "\n",
        "# A grid of cells to store the y-values in each area in\n",
        "# X-space. \n",
        "data_bins = [[[] for a1 in range(quant_num)]\n",
        "             for a2 in range(quant_num)]\n",
        "\n",
        "# Decide which bin each training sample belongs to\n",
        "\n",
        "# 1. We want the smallest value of an attribute to be stored in bin[0]\n",
        "#    and largest in bin[49] (say, for 50 bins)\n",
        "attrib0_min_value = X[:,0].min()\n",
        "attrib0_max_value = X[:,0].max() # perform 0-1 normalisation on attribute 0\n",
        "X[:, 0] = (X[:, 0] - attrib0_min_value) / (attrib0_max_value - attrib0_min_value)\n",
        "\n",
        "attrib1_min_value = X[:,1].min()\n",
        "attrib1_max_value = X[:,1].max()\n",
        "X[:, 1] = (X[:, 1] - attrib1_min_value) / (attrib1_max_value - attrib1_min_value)\n",
        "\n",
        "for x_, y_ in zip(X, y):\n",
        "    attrib0_bin_index = int(round(x_[0] * (quant_num - 1)))\n",
        "    attrib1_bin_index = int(round(x_[1] * (quant_num - 1)))\n",
        "    data_bins[attrib0_bin_index][attrib1_bin_index].append(y_)\n",
        "    # print(attrib0_bin_index, attrib1_bin_index)\n",
        "    \n",
        "# now we can arrange the data in a grid\n",
        "X_quant = []\n",
        "y_quant = []\n",
        "for grid_row in range(quant_num):\n",
        "    for grid_col in range(quant_num):\n",
        "        this_bin = data_bins[grid_row][grid_col]\n",
        "        if len(this_bin) > 0:\n",
        "                X_quant.append((grid_row, grid_col))\n",
        "                vote = int(round(np.mean(this_bin))) # if more than one y-value\n",
        "                # has been allocated to this cell (small area in X-space),\n",
        "                # we let them vote and take the majority.\n",
        "                y_quant.append(vote)\n",
        "                \n",
        "X_quant = np.array(X_quant) / quant_num # (0..1)\n",
        "y_quant = np.array(y_quant)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "UzMF05HmZ9Wo",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X = X_quant\n",
        "y = y_quant"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "asuiQiDkZ9Wp",
        "colab_type": "text"
      },
      "source": [
        "### Data preprocessing summary"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "D1hc3pgTZ9Wp",
        "colab_type": "text"
      },
      "source": [
        "Put all preprocessing steps together. Run the two cells below for proprocessed data. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [
          0,
          10
        ],
        "hidden": true,
        "id": "A8cLf1ikZ9Wp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def preproc_data_for_complexity_experiment_quick(iris_db):\n",
        "    \n",
        "    X, y = iris_db.data, iris_db.target\n",
        "    X = X[(y==0) + (y==1)][:, :2]\n",
        "    y = y[(y==0) + (y==1)]\n",
        "    \n",
        "    # normalise to 0-1\n",
        "    X = (X - X.min(axis=0)) / (X.max(axis=0) - X.min(axis=0))\n",
        "    return X, y\n",
        "\n",
        "def quantise_data(X, y, quant_num):\n",
        "    \n",
        "    # merge different y-values in the same cell                 \n",
        "    X = np.round(X  * (quant_num - 1)).astype(np.int)\n",
        "    data_bins = [[[] for a1 in range(quant_num)]\n",
        "             for a2 in range(quant_num)]\n",
        "    for (a1_, a2_), y_ in zip(X, y):\n",
        "        data_bins[a1_][a2_].append(y_)\n",
        "    X_quant = []\n",
        "    y_quant = []\n",
        "    for grid_row in range(quant_num):\n",
        "        for grid_col in range(quant_num):\n",
        "            this_bin = data_bins[grid_row][grid_col]\n",
        "            if len(this_bin) > 0:\n",
        "                    X_quant.append((grid_row, grid_col))\n",
        "                    vote = int(round(np.mean(this_bin))) # if more than one y-value\n",
        "                    # has been allocated to this cell (small area in X-space),\n",
        "                    # we let them vote and take the majority.\n",
        "                    y_quant.append(vote)\n",
        "    X = np.array(X_quant) / quant_num # (0..1)\n",
        "    y = np.array(y_quant)\n",
        "    return X, y"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "d5Vjdt3zZ9Wq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X, y = preproc_data_for_complexity_experiment_quick(iris_db)\n",
        "# you can comment out the following statement if not wanting quantisation\n",
        "X, y = quantise_data(X, y, IRIS_EXPERIMENT_X_SPACE_QUANTISATION_BIN_NUM)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "fxv0mU4JZ9Wt",
        "colab_type": "text"
      },
      "source": [
        "### Visualise the data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "GCZ1t76rZ9Wu",
        "colab_type": "text"
      },
      "source": [
        "We will make a figure showing the training data we had prepared"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [
          0,
          31
        ],
        "hidden": true,
        "id": "YFyeLTHoZ9Wu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "layout = go.Layout(\n",
        "    xaxis=go.layout.XAxis(\n",
        "        range=[0, 1],\n",
        "        showgrid=True,\n",
        "        zeroline=True,\n",
        "        showline=True,\n",
        "        gridcolor='#bdbdbd',\n",
        "        gridwidth=1,\n",
        "        zerolinecolor='#969696',\n",
        "        zerolinewidth=2,\n",
        "        linecolor='#636363',\n",
        "        linewidth=2,\n",
        "        mirror=True,\n",
        "    ),\n",
        "    yaxis=go.layout.YAxis(\n",
        "        range=[0, 1],\n",
        "        showgrid=True,\n",
        "        zeroline=True,\n",
        "        showline=True,\n",
        "        gridcolor='#bdbdbd',\n",
        "        gridwidth=1,\n",
        "        zerolinecolor='#969696',\n",
        "        zerolinewidth=2,\n",
        "        linecolor='#636363',\n",
        "        linewidth=2,\n",
        "        mirror=True,\n",
        "   ),\n",
        "   height=600,\n",
        "   width=600,\n",
        ")\n",
        "\n",
        "fig = go.Figure(\n",
        "    data=[\n",
        "        go.Scatter(\n",
        "            x=all_x[:, 0], \n",
        "            y=all_x[:, 1], \n",
        "            marker_color=\"rgba(0.7, 0.7, 0.7, 0.3)\",\n",
        "            marker_size=6,\n",
        "            marker_line_width=2,\n",
        "            mode=\"markers\",\n",
        "            name=\"'All' X Space Samples\"),\n",
        "        go.Scatter(\n",
        "            x=X[:, 0], \n",
        "            y=X[:, 1], \n",
        "            marker_color=y,\n",
        "            marker_size=12,\n",
        "            marker_line_width=2,\n",
        "            mode=\"markers\",\n",
        "            name=\"Dataset Samples\"), \n",
        "    ],\n",
        "    layout=layout,\n",
        "    layout_title_text=\"Quantized Simplified Iris Data\"\n",
        ")\n",
        "if COLAB:\n",
        "    fig.show(renderer=\"colab\")\n",
        "else:\n",
        "    fig.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "kMCr_UmpZ9Ww",
        "colab_type": "text"
      },
      "source": [
        "## Test model complexity"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "bGTTbUvAZ9Ww",
        "colab_type": "text"
      },
      "source": [
        "We use decision trees for example, where different settings of the maximum depths represent different complexity of the models.  I.e. a decision tree that can build many levels of nodes is capable of fit more varieties in the training data,  while a decision tree with only few levels can only make simple splits in the data space."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "IrLxBSGCZ9Ww",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# This is a replica, FYI. The libraries have been imported above.\n",
        "from sklearn.tree import DecisionTreeClassifier\n",
        "from sklearn.model_selection import train_test_split"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "Kcn2HHWzZ9Wy",
        "colab_type": "text"
      },
      "source": [
        "To demonstrate different challenges posed by the random training set during perform machine learning, we set up two conditions:\n",
        "\n",
        "    i) the number of training data samples is small, for example, we can set it as shown below.\n",
        "    \n",
        "    ii) there is noise in the training samples, so simply fit the training samples to high fidelity won’t work very well.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "cFyRwxwvZ9Wy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "train_num = 40\n",
        "noise = 0.15"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "rHaMkBc9Z9W1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "complex_E_in = []\n",
        "complex_E_out = [] # we cannot compute this, as we don't have the true concept \n",
        "# of Iris data. We can make one up in a later version for experiment. But for now, \n",
        "# let us use the evaluation on held-out test data instead. See below complex_E_test.\n",
        "complex_E_test = []\n",
        "simple_E_in = []\n",
        "simple_E_test = []\n",
        "\n",
        "# We perform multiple rounds of experiments to test the statistics of \n",
        "# E_in and E_test for different models / experiment settings.\n",
        "\n",
        "# Randomly add noise to the data.\n",
        "rng = np.random.RandomState(42)\n",
        "noisy_y = np.array([\n",
        "    y_ if rng.rand() > noise else (1-y_)\n",
        "    for y_ in y\n",
        "])\n",
        "for random_seed in range(500):\n",
        "    # Randomly split training/test data\n",
        "    X_train, X_test, y_train, y_test = train_test_split(\n",
        "        X, noisy_y, train_size=train_num, test_size=len(y)-train_num,\n",
        "        stratify=noisy_y,\n",
        "        random_state=random_seed)\n",
        "    \n",
        "    # Fit a complex model\n",
        "    dt_complex = DecisionTreeClassifier(max_depth=100)\n",
        "    dt_complex.fit(X_train, y_train)\n",
        "    \n",
        "    # Record training and test error\n",
        "    pred_on_X_train = dt_complex.predict(X_train)\n",
        "    E_in = np.sum(pred_on_X_train != y_train) / len(y_train) # error rate\n",
        "    complex_E_in.append(E_in)\n",
        "    pred_on_X_test = dt_complex.predict(X_test)\n",
        "    E_test = np.sum(pred_on_X_test != y_test) / len(y_test) # error rate\n",
        "    complex_E_test.append(E_test)\n",
        "    \n",
        "    # Fit a simple model\n",
        "    dt_simple = DecisionTreeClassifier(max_depth=2)\n",
        "    dt_simple.fit(X_train, y_train)\n",
        "    \n",
        "    # Record training and test error\n",
        "    pred_on_X_train = dt_simple.predict(X_train)\n",
        "    E_in = np.sum(pred_on_X_train != y_train) / len(y_train) # error rate\n",
        "    simple_E_in.append(E_in)\n",
        "    pred_on_X_test = dt_simple.predict(X_test)\n",
        "    E_test = np.sum(pred_on_X_test != y_test) / len(y_test) # error rate\n",
        "    simple_E_test.append(E_test)\n",
        "\n",
        "complex_E_in = np.array(complex_E_in)\n",
        "complex_E_test = np.array(complex_E_test)\n",
        "simple_E_in = np.array(simple_E_in)\n",
        "simple_E_test = np.array( simple_E_test)  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "BsqgcrifZ9W2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(\"Complex Tree average E_in mean {:.3f}, std {:.3f}\"\n",
        "      .format(complex_E_in.mean(), complex_E_in.std()))\n",
        "print(\"Complex Tree average E_out mean {:.3f}, std {:.3f}\"\n",
        "      .format(complex_E_test.mean(), complex_E_test.std()))\n",
        "abs_diff = np.abs(complex_E_in - complex_E_test)\n",
        "print(\"Complex Tree average |E_out - E_in| mean {:.3f}, std {:.3f}\"\n",
        "      .format(abs_diff.mean(), abs_diff.std()))\n",
        "\n",
        "print(\"Simple Tree average E_in mean {:.3f}, std {:.3f}\"\n",
        "      .format(simple_E_in.mean(), simple_E_in.std()))\n",
        "print(\"Simple Tree average E_out mean {:.3f}, std {:.3f}\"\n",
        "      .format(simple_E_test.mean(), simple_E_test.std()))\n",
        "abs_diff = np.abs(simple_E_in - simple_E_test)\n",
        "print(\"Simple Tree average |E_out - E_in| mean {:.3f}, std {:.3f}\"\n",
        "      .format(abs_diff.mean(), abs_diff.std()))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "cQniQXB1Z9W3",
        "colab_type": "text"
      },
      "source": [
        "__Experiment Records__\n",
        "\n",
        "<span style=\"color:green\">__EXERCISE__</span>\n",
        "\n",
        "Please try different experiment settings. Record your findings in the table below (double-click here to edit this cell). Please take notes for the following two topics:\n",
        "1. Why you had chosen the experiment configurations? Why you thought those numbers are worthy exploration?\n",
        "2. What did you expect to find for the parameters *BEFORE* you run the experiments?\n",
        "3. Do the outcomes match your expectation? Explain possible reasons of matching / mismatching. \n",
        "\n",
        "| $N$ | $\\eta$ | $E_{in}^C $  | $E_{test}^C$ | $D^C$  | $E_{in}^S$  | $E_{test}^S$ | $D^S$  | \n",
        "|---|---|---|---|---|---|---|---|\n",
        "| 40 | 0.15 | 0.000  |  0.413  | 0.413   | 0.202   | 0.321   | 0.124 |\n",
        "\n",
        "- $N$: number of training samples\n",
        "- $\\eta$: noise level (probability that in a training sample $(x, y)$, $y$ happens to be the _incorrect_ label for $x$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "id": "Zc83s4unZ9W4",
        "colab_type": "text"
      },
      "source": [
        "# 3 Training"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [],
        "hidden": true,
        "id": "j2ctXmfZZ9W4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Environment and constant preparation\n",
        "%matplotlib inline\n",
        "# renders figures in notebook\n",
        "import numpy as np\n",
        "from PIL import Image # Python Imaging Library - image file manipulation\n",
        "# Image module provides a class used to represent a PIL image, load, rotate, display, etc.\n",
        "from sklearn.model_selection import train_test_split\n",
        "try:\n",
        "    import plotly.graph_objects as go\n",
        "except:\n",
        "    !pip install plotly==4.1.0\n",
        "import matplotlib.pyplot as plt # pyplot module generates interactive plots\n",
        "# 'import pyplot module of matplotlib library under alias plt'\n",
        "import torchvision.datasets as cvdata # import torchvision datasets\n",
        "import torchvision.transforms as transforms # import torchvision transforms\n",
        "# torchvision package contains datasets, model architectures, 'common image \n",
        "# transformations' for computer vision.\n",
        "from pathlib import Path\n",
        "# pathlib.Path class for creating file paths\n",
        "# Creates paths appropriate for different OSs\n",
        "import torch\n",
        "\n",
        "DATA_FOLDER = Path(\"./data\").absolute()\n",
        "# absolute() returns an absolute version of a path\n",
        "DATA_FOLDER.mkdir(parents=True, exist_ok=True) # Create directory with specified path\n",
        "DATA_FOLDER = str(DATA_FOLDER) # create a string with the specified path\n",
        "COLAB = True\n",
        "IRIS_EXPERIMENT_X_SPACE_QUANTISATION_BIN_NUM = 50 # self-interpretation"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "yLMgKkE7Z9W7",
        "colab_type": "text"
      },
      "source": [
        "## 3.1 Preparing Data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "Bi505s6rZ9W7",
        "colab_type": "text"
      },
      "source": [
        "We use data from CIFAR object dataset."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "_VuCE6ygZ9W-",
        "colab_type": "text"
      },
      "source": [
        "### Downloading and Loading Raw Data"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [],
        "hidden": true,
        "id": "8NAsDglPZ9W-",
        "colab_type": "code",
        "outputId": "5c3baa66-b290-4d47-d60c-a2c3c80a1bc6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Download and make dataset\n",
        "transform = transforms.Compose(\n",
        "    [transforms.ToTensor(),\n",
        "     transforms.Normalize((0.5, 0.5, 0.5), (0.5, 0.5, 0.5))])\n",
        "# Compose() combines a list of transforms.\n",
        "# ToTensor() converts a PIL image or numpy.ndarray (HxWxC) in range [0,255] to a \n",
        "# torch.FloatTensor of shape (CxHxW) in range [0.0,1.0].\n",
        "# Normalize(mean, std) normalises each channel of a tensor image.\n",
        "# This creates a transform object called transform that can be applied to images\n",
        "\n",
        "cifar_trainset = cvdata.CIFAR10(\n",
        "    root=DATA_FOLDER, train=True,\n",
        "    download=True, transform=transform)\n",
        "# downloads CIFAR10 training set, transforms, saves to DATA_FOLDER\n",
        "# CIFAR10: 60,000 32x32 colour images; 10 classes each of 6000 images.\n",
        "# 50,000 training images, 10,000 test.\n",
        "\n",
        "cifar_all_trainloader = torch.utils.data.DataLoader(\n",
        "    cifar_trainset, batch_size=64,\n",
        "    shuffle=False, num_workers=6)\n",
        "# Create an object to load training data in batches\n",
        "\n",
        "# take two classes for a subset\n",
        "cifar_classes = ('plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck')\n",
        "\n",
        "# collect samples in an overall array\n",
        "images = []\n",
        "labels = []\n",
        "indexes = []\n",
        "for i, (x, y) in enumerate(cifar_trainset):\n",
        "    if cifar_classes[y] in [\"plane\", \"bird\"]:\n",
        "        images.append(x)\n",
        "        twoclass_label = 1 if cifar_classes[y] == \"plane\" else -1\n",
        "        labels.append(twoclass_label)\n",
        "        indexes.append(i)\n",
        "# collect images in images, labels and indices of training samples in classes \n",
        "# plane and bird\n",
        "        \n",
        "X = torch.stack(images).numpy()\n",
        "# torch.stack takes list of tensors 'images' and concatenates them\n",
        "# .numpy() converts a torch tensor to a numpy array\n",
        "y = np.array(labels)\n",
        "# converts list 'labels' into an array\n",
        "indexes = np.array(indexes)\n",
        "# same for 'indexes'"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Files already downloaded and verified\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "sW8Si4GuZ9XB",
        "colab_type": "text"
      },
      "source": [
        "### Preprocessing (Doing Features)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BNepTlwmavZY",
        "colab_type": "code",
        "outputId": "75610e3c-8c45-4575-87d5-ce51448cee5d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 84
        }
      },
      "source": [
        "print(X.shape)\n",
        "# (10000, 3, 32, 32)\n",
        "print(X[:, 1].shape)\n",
        "# (10000, 32, 32)\n",
        "print(X[:, 1].reshape(X.shape[0], -1).shape)\n",
        "# (10000, 1024)\n",
        "print(X[:, 1].reshape(X.shape[0], -1).sum(axis=1).shape)"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(10000, 3, 32, 32)\n",
            "(10000, 32, 32)\n",
            "(10000, 1024)\n",
            "(10000,)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NGHWuyyaVSUn",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(X_train_init.shape, y_train_init.shape, ind_train_init.shape)\n",
        "print(X_test_init.shape, y_test_init.shape, ind_test_init.shape)\n",
        "print(X_train_loop.shape, y_train_loop.shape, ind_train_loop.shape)\n",
        "print(X_test_loop.shape, y_test_loop.shape, ind_test_loop.shape)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [
          1,
          4,
          7,
          21,
          60,
          63
        ],
        "hidden": true,
        "id": "LkYy47i-Z9XC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Defining processing functions\n",
        "def feature_maker_overall_green(X):\n",
        "    return X[:, 1].reshape(X.shape[0], -1).sum(axis=1)\n",
        "# Takes a subset of X for which the second element is 1, reshapes it to have \n",
        "# first dimension equal to original first dimension, and the remaining dimensions \n",
        "# combined to make the shape compatible with the orignal shape (this is what the \n",
        "# -1 does; i.e. takes (10000 x 32 x 32) and reshapes it to (10000, 32^2)), and \n",
        "# then takes the sum over the second dimension.\n",
        "# Effect is to sum the values of the third and fourth dimensions for each training \n",
        "# sample for which the value of the second dimension is 1 (i.e. G in RGB).\n",
        "\n",
        "def feature_maker_overall_blue(X):\n",
        "    return X[:, 2].reshape(X.shape[0], -1).sum(axis=1)\n",
        "# Same as above but where second dimension value is 2 (B in RGB).\n",
        "\n",
        "def take_a_separable_subset(X, y, original_indexes):\n",
        "    from sklearn.linear_model import LogisticRegression\n",
        "    lr = LogisticRegression(solver='lbfgs')\n",
        "    # added solver='lbfgs' to stop warning messages about default solver\n",
        "    lr.fit(X, y)\n",
        "    pred = lr.predict(X)\n",
        "    pred_prob = lr.predict_log_proba(X)\n",
        "    # was X_train, which was an error\n",
        "    confident_ind = np.logical_or(pred_prob[:, 0] > np.log(0.55),\n",
        "                                  pred_prob[:, 1] > np.log(0.55))\n",
        "    ind = np.logical_and(confident_ind, pred==y)\n",
        "    X_simple = X[ind]\n",
        "    y_simple = y[ind]\n",
        "    original_indexes_simple = original_indexes[ind]\n",
        "    return X_simple, y_simple, original_indexes_simple\n",
        "# Fits a logistic regression to given data and selects and returns subset of \n",
        "# data for which outcome is predicted by LR with probability > 0.55.\n",
        "\n",
        "def prepare_cifar_two_class_data(\n",
        "    X, y, original_indexes,\n",
        "    simple=False,\n",
        "    train_size=1000,\n",
        "    make_feature_1=feature_maker_overall_green, \n",
        "    make_feature_2=feature_maker_overall_blue):\n",
        "    feature1 = make_feature_1(X)\n",
        "    feature2 = make_feature_2(X)\n",
        "    X = np.stack([feature1, feature2], axis=1)\n",
        "    # normalise to -1 to +1\n",
        "    X -= X.min(axis=0)\n",
        "    X /= X.max(axis=0)\n",
        "    X -= 0.5\n",
        "    X *= 2.0\n",
        "    \n",
        "    X_train, X_test, y_train, y_test, ind_train, ind_test = \\\n",
        "        train_test_split(X, y, original_indexes, \n",
        "                         train_size=train_size, test_size=len(y)-train_size)\n",
        "    return X_train, X_test, y_train, y_test, ind_train, ind_test\n",
        "# Creates normalised train-test split with features defined by default \n",
        "# according to the above functions to sum green and blue values.\n",
        "\n",
        "def prepare_cifar_two_class_separable_data(\n",
        "    X, y, original_indexes, train_size=100):\n",
        "    \n",
        "    X_simple, y_simple, indexes_simple = \\\n",
        "        take_a_separable_subset(X, y, original_indexes)\n",
        "    \n",
        "    X_train_simple, X_test_simple, \\\n",
        "    y_train_simple, y_test_simple, \\\n",
        "    ind_train_simple, ind_test_simple = \\\n",
        "        train_test_split(X_simple, y_simple, indexes_simple, \n",
        "                         train_size=train_size, test_size=len(y_simple)-train_size)\n",
        "    # this was len(y_simple)-100, presumably an error\n",
        "    return X_train_simple, X_test_simple, \\\n",
        "        y_train_simple, y_test_simple, \\\n",
        "        ind_train_simple, ind_test_simple\n",
        "# Creates a train-test split for a linearly separable subset of input.\n",
        "    \n",
        "# X_train, X_test, y_train, y_test, ind_train, ind_test = \\\n",
        "#     prepare_cifar_two_class_data(X, y, indexes)\n",
        "# Apply prepare_cifar_two_class_data() to X, y, indexes; i.e. split image data \n",
        "# prepared above into normalised training and test samples.\n",
        "\n",
        "# X_train_simple, X_test_simple, \\\n",
        "# y_train_simple, y_test_simple, \\\n",
        "# ind_train_simple, ind_test_simple = prepare_cifar_two_class_separable_data(\n",
        "#     X_train, y_train, ind_train)\n",
        "# Apply prepare_cifar_two_class_separable_data() to X_train, y_train, ind_train \n",
        "# created immediately above; i.e. from prepared training data, further split into \n",
        "# training and test sets, both of which are linearly separable.\n",
        "\n",
        "def quick_separable_train_sample(n=100):\n",
        "    X_train_simple, X_test_simple, \\\n",
        "    y_train_simple, y_test_simple, \\\n",
        "    ind_train_simple, ind_test_simple = prepare_cifar_two_class_separable_data(\n",
        "        X_train, y_train, ind_train, train_size=n)\n",
        "    \n",
        "    return X_train_simple, y_train_simple, ind_train_simple\n",
        "# Create a train-test split for a linearly separable subset of (presumably \n",
        "# existing objects, which in this case would be the normalised training \n",
        "# created above, assuming that python functions can use objects from outside the \n",
        "# function environment), and return only the training set (so the same as running \n",
        "# the code immediately above this function, but as a function)."
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "MOe9bf1ZZ9XD",
        "colab_type": "text"
      },
      "source": [
        "### Visualisation Functions"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [
          1,
          7
        ],
        "hidden": true,
        "id": "niivdnhdZ9XD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Defining vis-functions\n",
        "def show_cifar_image(img_id):\n",
        "    npimg = ((cifar_trainset[img_id][0].detach().numpy() + 1.0) \\\n",
        "        * 128).astype(np.uint8).transpose((1, 2, 0))\n",
        "    # plt.imshow(npimg, interpolation='nearest') # for larger view\n",
        "    return Image.fromarray(npimg), npimg\n",
        "# Return image from CIFAR given ID.\n",
        "\n",
        "def encode_sample_image(index):\n",
        "    \"\"\"\n",
        "    Generate the resource url to display an image in a webpage.\n",
        "    This is not used in notebooks. But you can take the function\n",
        "    in a standalone Python program as a web-server to visual data models.\n",
        "    \"\"\"\n",
        "    import base64\n",
        "    from io import BytesIO\n",
        "\n",
        "    pil_img = Image.fromarray(((cifar_trainset[index][0].numpy()\n",
        "                                .transpose([1, 2, 0]) + 1.0) * 128).astype(np.uint8))\n",
        "    buff = BytesIO()\n",
        "    pil_img.save(buff, format=\"JPEG\")\n",
        "    new_image_string = base64.b64encode(buff.getvalue()).decode(\"utf-8\")\n",
        "    # print(new_image_string[:100])\n",
        "    return \"\"\"<img src=\"data:image/png;base64,\"\"\" \\\n",
        "        + \"\"\"\"></img>\"\"\"\n",
        "\n",
        "def show_perceptron_model(model, X_train, y_train, indexes_train=[]):\n",
        "    layout = go.Layout(\n",
        "        xaxis=go.layout.XAxis(\n",
        "            range=[-1, 1],\n",
        "            showgrid=True,\n",
        "            zeroline=True,\n",
        "            showline=True,\n",
        "            gridcolor='#bdbdbd',\n",
        "            gridwidth=1,\n",
        "            zerolinecolor='#969696',\n",
        "            zerolinewidth=2,\n",
        "            linecolor='#636363',\n",
        "            linewidth=2,\n",
        "            mirror=True,\n",
        "        ),\n",
        "        yaxis=go.layout.YAxis(\n",
        "            range=[-1, 1],\n",
        "            showgrid=True,\n",
        "            zeroline=True,\n",
        "            showline=True,\n",
        "            gridcolor='#bdbdbd',\n",
        "            gridwidth=1,\n",
        "            zerolinecolor='#969696',\n",
        "            zerolinewidth=2,\n",
        "            linecolor='#636363',\n",
        "            linewidth=2,\n",
        "            mirror=True,\n",
        "       ),\n",
        "       height=600,\n",
        "       width=600,\n",
        "    )\n",
        "\n",
        "    # visualise perceptron model on a grid\n",
        "    x_grid, y_grid = np.meshgrid(np.arange(-1, 1.01, 0.05), np.arange(-1, 1.01, 0.05))\n",
        "    grid_X = np.stack(( x_grid.flatten(), y_grid.flatten()) ).T\n",
        "    grid_pred = model.predict(grid_X)\n",
        "    train_pred = model.predict(X_train)\n",
        "    # model is an input, predict() is presumably the function defined in the \n",
        "    # following block for the class MyPerceptron2D; model must therefore be a \n",
        "    # MyPerceptron2D object.\n",
        "    train_error_num = (train_pred.astype(np.int) != y_train.astype(np.int)).sum()\n",
        "    E_in = train_error_num / len(y_train)\n",
        "\n",
        "    scatter_grid = go.Scatter(\n",
        "        x=grid_X[:, 0], y=grid_X[:, 1], \n",
        "        marker=dict(\n",
        "            size=6,\n",
        "            cmax=1,\n",
        "            cmin=-1,\n",
        "            line_width=1,\n",
        "            color=grid_pred,\n",
        "            colorscale=\"Cividis\",\n",
        "            symbol=\"square\",\n",
        "            opacity=0.5\n",
        "        ),\n",
        "        mode=\"markers\",\n",
        "    #     colorscale=,\n",
        "        name=\"'All' X Space Samples\",\n",
        "        hoverinfo=\"none\")\n",
        "    \n",
        "    contour_grid = go.Contour(\n",
        "        z=grid_pred,\n",
        "        x=grid_X[:, 0], # horizontal axis\n",
        "        y=grid_X[:, 1], # vertical axis\n",
        "        hoverinfo=\"none\",\n",
        "        colorscale=\"Cividis\",\n",
        "        showscale=False\n",
        "    )\n",
        "    \n",
        "    if len(indexes_train) == 0:\n",
        "        scatter_train_text = [\"X:({:.02f}, {:.02f})<br>y:{}, pred:{}\".format(x0, x1, int(y), int(p)) \n",
        "              for (x0, x1), y, p in zip(X_train, y_train, train_pred)] \n",
        "    else:\n",
        "        scatter_train_text = [\"X:({:.02f}, {:.02f})<br>y:{}, pred:{}, ImgID {:d}\"\\\n",
        "                              .format(x0, x1, int(y), int(p), i) \n",
        "                              for (x0, x1), y, p, i in zip(X_train, y_train, train_pred, indexes_train)] \n",
        "        \n",
        "\n",
        "    scatter_train = go.Scatter(\n",
        "        x=X_train[:, 0], y=X_train[:, 1],\n",
        "         marker=dict(\n",
        "             size=12,\n",
        "             cmax=1,\n",
        "             cmin=-1,\n",
        "             color=y_train,\n",
        "             colorscale=\"Cividis\",\n",
        "             line=dict(\n",
        "                 width=2,\n",
        "                 color=[\"green\" if prediction == ground_truth else \"red\"\n",
        "                        for prediction, ground_truth in zip(train_pred, y_train)]\n",
        "             )\n",
        "\n",
        "        ),\n",
        "        mode=\"markers\",\n",
        "        name=\"Dataset Samples\",\n",
        "        text=scatter_train_text,\n",
        "        hoverinfo=\"text\")\n",
        "\n",
        "    fig = go.Figure(\n",
        "        data=[\n",
        "            contour_grid, scatter_train\n",
        "        ],\n",
        "        layout=layout,\n",
        "        layout_title_text=\"Two Object Class 2D Data<br>#.errors={:d}, E_in={:.3f}\"\\\n",
        "            .format(train_error_num, E_in)\n",
        "    )\n",
        "    if COLAB:\n",
        "        fig.show(renderer=\"colab\")\n",
        "    else:\n",
        "        fig.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "bBXfC9TYZ9XF",
        "colab_type": "text"
      },
      "source": [
        "## 3.2 Perceptron Model"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "jP1RKzsQZ9XG",
        "colab_type": "text"
      },
      "source": [
        "The prediction function. A perceptron consists of the weights associated to all data attributes and a bias."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [],
        "hidden": true,
        "id": "cZqtX1_BZ9XG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class MyPerceptron2D:\n",
        "    def __init__(self):\n",
        "        \"\"\"\n",
        "        There are three parameters for a perceptron working on 2D data.\n",
        "        w0, w1: the coefficients of the first and second attribute x0 and x1, respectively\n",
        "        b: the bias\n",
        "        \"\"\"\n",
        "        self.w0 = 1.0\n",
        "        self.w1 = 0\n",
        "        self.b = 0\n",
        "        \n",
        "    def predict(self, x):\n",
        "        \"\"\"\n",
        "        Given a data sample (x0, x1), the perceptron first computes the \n",
        "        \"pre-activation potential\" -- a term borrowed from biological neurons --\n",
        "        using simple linear function:\n",
        "        \n",
        "            pre-activation := w0 * x0 + w1 * x1 + bias\n",
        "        \n",
        "        Note this implementation we accept numpy array as input `x`, where \n",
        "        x is of the format \n",
        "        [[x0, x1] .. for sample-0\n",
        "         [x0, x1] .. for sample-1\n",
        "         [x0, x1] .. for sample-2\n",
        "         ...]\n",
        "         \n",
        "        it contains N samples, each of 2 attributes. As a Numpy array, x provides \n",
        "        convenient access to specific attributes of all samples. We can compute\n",
        "        the pre-activation values of N samples easily as shown in the code.\n",
        "        \n",
        "        The prediction is straightforward given the pre-activation values: it amounts to\n",
        "        determine if the pre-activation is above or below zero.\n",
        "        \"\"\"\n",
        "        prediction = x[:, 0] * self.w0 \\\n",
        "            + x[:, 1] * self.w1 \\\n",
        "            + self.b\n",
        "        \n",
        "        prediction[prediction > 0] = 1\n",
        "        prediction[prediction <= 0] = -1\n",
        "        return prediction\n",
        "    \n",
        "    \n",
        "    def update(self, dw0, dw1, db, verbose=False):\n",
        "        \"\"\"\n",
        "        Incrementally adjust the model parameters\n",
        "        \"\"\"\n",
        "        if verbose:\n",
        "            print(\"Old perceptron:\", self)\n",
        "        self.w0 += dw0\n",
        "        self.w1 += dw1\n",
        "        self.b += db\n",
        "        if verbose: \n",
        "            print(\"New perceptron:\", self)\n",
        "# Use this to test the effect of making incremental adjustments to weights \n",
        "# (and bias).\n",
        "            \n",
        "    def set_param(self, w0, w1, b, verbose=False):\n",
        "        if verbose:\n",
        "            print(\"Old perceptron:\", self)\n",
        "        self.w0 = w0\n",
        "        self.w1 = w1\n",
        "        self.b = b\n",
        "        if verbose: \n",
        "            print(\"New perceptron:\", self)\n",
        "# Use this to set weights (and bias) to specific values.\n",
        "            \n",
        "            \n",
        "    def fit(self, X, y):\n",
        "        raise NotImplementedError\n",
        "    \n",
        "    def __str__(self):\n",
        "        return \"W0:{:.2f}, W1:{:.2f}, b:{:.2f}\".format(self.w0, self.w1, self.b)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "JzcXnyCTZ9XH",
        "colab_type": "text"
      },
      "source": [
        "In the cell below, we construct a perceptron model to perform classification."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "by-hYhBpZ9XH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "X_easy, y_easy, ind_easy = quick_separable_train_sample(20) # take some easy, small samples for experiment\n",
        "first_perceptron = MyPerceptron2D()\n",
        "show_perceptron_model(first_perceptron, X_easy, y_easy, ind_easy)  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "37VuhYRRZ9XJ",
        "colab_type": "code",
        "outputId": "073b1c69-5442-4381-f82b-5c17ee6d1d61",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 49
        }
      },
      "source": [
        "# Hover the cursor on a training sample, it will show the id of \n",
        "# the corresponding image. Use the ID here to show the image.\n",
        "im, imnp = show_cifar_image(26045)\n",
        "im"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAACAAAAAgCAIAAAD8GO2jAAAIN0lEQVR4nE3WS4+mV3EH8H/VOc/z\n3vs20z3jnnG3b+PxDSwhGWJLQbKIokSCLFhFiBWfgG/ALqtIYYPEjj0SWyQEIWwAc7EAgxtmBnvu\ndE/39OXt932u51T9s+ghylnXqVJVLeon8l8/hHV0E0KCIhRwJTPFBEIo3MQdbjQDoBpUg9PcTegg\nAQUEIP7fIwgn6BGigAgIEagoANBEACVEJDz7roAQAEUooAMqdAEgKn+P0GfJAZAQBxFFlBpUHe5C\nBCULOCGugIgToqYOF5ECgIAkRQVUAiICEZIiClEAJEEKSQhMooYQJAZSkAUMCioSQAUJKghAAkXg\nFIBuJBUQEQtKVSGEF7Xk/0YkIkJQJcYoA9MBYxQGIAaFSgcxiBPmMGESuguSOegiFBGAZBARxbP8\nhIrAxYSEwx2EUOIshInYmCwRIhBEXSVBjEpKVvbwRHdRi0ygke5KCp0KiKqJmJMkVV1VmWm8WDFU\n4/XgA5ERNUpQQUGBShJkUgQG6Qxq0cWTSIL3ECfp5m7KQIUpXCCQDNRuhJq4KdxJQbwuroqgIVJU\nPApVYSKECOBkF0QyzHN2mtBdSDExBhUIBAQ9kBCnVsbkMIiJUMSAuCoWBB5EnREWlRAQCsIBV4yB\nLGoZDnMRCPrUqkgpMYlDKC4AeniSMARcs+VspMFJi1Ovk0spcRJEwEnQcVFWqdWgo6JoDeMY6q4/\ncUZB69aDlyfxyjCOQ3jacd50C6R5b6AG8VkMllLv5tZbzp143CojGMbRVZETN8oYAoaUcVEWw2Ii\n4aBpQm7q48c7V3eSDKuufm5aBNORIgZfHRR3qizOtQhnHgAow/q4qJv8cG6ecjw9mZ8+vvvqjRtn\nMlo2izYPG8NZm1oUmxPZHpYfHZ+/s3Xp+urkr/f+kkbrYTAkivPWz7pufaBAPOv9adsVUbIhaPHy\nZMDUHC76/cbOUh/P237c16tp2Yr9pWofN5ng0lSCXRoNfv5kLtSmT2vTjSt9/9tbey/tvri+ut2n\n6sp40Bkt2831GY9ZQ4tBKINMpwNjsU6VaB/u1zHOZn66tnb/VrjxalodPWrDn5dVFtsU/HS/Oujz\ny0P5+LCfWffSxvS9N97au73XnB69fvO1N7evpTCou25UFu++9uJsMDL3LvdVU3dV89xn37j98N7l\nQiNyP7n+/FqDjQd3L998e6toj3MA8f7O5t06peyvro2nzGulloG7W5fffv0VeNpa2xiWRSxGhWgW\nDoblh7/b27tzq66qT+7eW7906b0vvPfg6fHpopLv/uAnQ42X18rXDm79/qPb3/7Fb9/44vv/9i//\nvLs6NXJQFrPRSEA1M2bAVaIKzPoud23v1vq8rbqUfvbzX3/86adxMl00bSoiy+lBzyNHXBkVUXRj\nNitf+aet+dn0+49++aMff/Ufv3Dtxm7Xd6D1qXHTlJJ1tagUsQgazurzg8P9g6PTvceHy2xBcJ7z\n/PLW/cZ9NJrGAIZUKj3HB4fzlWEcR4nCw/Xnv/rl97/33x/857e/842v//v289e63FVtWtT9vF48\nN5tdv7K1uhL/fPvj33z0h2VVzXu5b8UhpRhO+ixtLvZTOxmMVsYjaevNGF6fzuLjk5Pp9mUz75pm\n98VXtq5c/eY/fOnB4fGTs6rSg8Pl/P7J4s5ZddzaF3eee9exvHXywd4f2sRUnX/tK1+Js/Vv/fQ3\nvzuaj6Okjskl9vmTk5O2qwYIb3Mj9vBYFqPRcFF3Z02uza69fPPaDXZ9mi+ruetrk82tzfzB/pNQ\nlodPT/54e2/z0tU3X3hluTztMu/dfdg1zVtrsxdmo1tPT552llOXvEtm2XOfU1ybjKP7ymj4qKrv\nHD8RCW2fyxAmpQq9IHcuzfqHf/v8NJ5XJx8cHg1y96+ff2fn6pUPP7n7P3u371fVTlm8cHn9eHG+\nEXx3dVBKee98sdfUUw1vbm7EO6d1AooyVlU6OF+slMNbdZ2dz8+moQyHVVW5f/To/u3jkxMU0zi4\nNhz96O5B/vTen+7dv/d08bhvtscryz4ftdV+vVwJxUoRniw7MQuCW4dHMvnmf0xEd8ZxZ1jAvcr2\npG/61O9OVmviSdvX2Tqmo2WloZiEsstdzp17LyrizGYSokoQurmTAAky5ATrSYk9te1zVS10ffLO\n9vav/nbw6emiDHp3sd+akgU0w6kUFa/YOl1Egei9CbLC4QoNZgbrFQJEBZkz3QUaS2MW6WJ4sKhv\nVvX2ZDaOg5XBcO/k+GG9zDmDhIpqWBuPau+XzVLomhOyAQ6QmhgIN5g5oTAnwYtuXN/dXv/c1bUg\n3jM8qmqBr41LDSiL4q3NKy+uTEHA3S0vu6pvG0lJuj7kHD2LGdzFDKkXM3FRc+TE3MMdJC3Hz1xa\ne3R2xksbu5Pp9dn4ybJ6sDgvNEwjXpqNj8tw2PZVsyRY1xnmSkc2uF3cSoEIQRAQmMMyASHBDHeh\nx78+3n9QLa+uru5OB+xtQFwbT+dNpTl98vTwpGvVkqaOoNCQTekutAurOAEn5RnnPMP6C9bRjXTQ\n4+2j/f3U71eLpjkfMyZLwyI2Zo/P50dtZW2P7M9gCIeTZgAh4u5KkHRQecFFh9nFcIQm5gLG86Zq\n6qoV/f358ThoDEXUWKd01tXJDC7iLqKIigvqgEKS5jQxUoRKAGLmTjUTN6eLm2YPzHGxOGddibCB\nLBUiQSFmhiASg1CVBNxNAMcz7gqZQfdnBhY6aAbP4g7LcIdncWS32C4XSMkvOBkC1fzChBI8izCD\nEEAFpBOgyjMs5k6cGgckmE0si2fm7J4lm3qmQ0T/FyjT6AwO6kjbAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<PIL.Image.Image image mode=RGB size=32x32 at 0x7F95A8DD9128>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "H9boeydwZ9XK",
        "colab_type": "text"
      },
      "source": [
        "## 3.3 Training Algorithm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "ZCDRv330Z9XK",
        "colab_type": "text"
      },
      "source": [
        "### A Manual \"Training\" Scheme"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "FiQMI3MdZ9XK",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:green\">__EXERCISE__</span>\n",
        "\n",
        "How the perceptron worked on the data? In the cell below, \n",
        "please attempt to modify the parameters of the perceptron model, so the prediction matches the data better."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "3R6auRFhZ9XK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "first_perceptron.update(dw0=0, dw1=0, db=0.05, verbose=True)\n",
        "#first_perceptron.set_param(w0=-0.02, w1=0.08, b=.0, verbose=True)\n",
        "# These two lines originally in notebook.\n",
        "#first_perceptron.set_param(w0=0, w1=1, b=.1, verbose=True)\n",
        "# I added this one; can play around with it without losing original \n",
        "# settings included by Jun.\n",
        "show_perceptron_model(first_perceptron, X_easy, y_easy)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "T99MVK1QZ9XL",
        "colab_type": "text"
      },
      "source": [
        "### Training a Perceptron"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "qdmwFGrmZ9XL",
        "colab_type": "text"
      },
      "source": [
        "The motiviation is as follows:\n",
        "\n",
        "- we need to modify the model parameters when our perceptron makes predictions disagree with the given $y$ for some training data samples.\n",
        "\n",
        "- Now consider an example: `[x0, x1, +1]`, since our perceptron predicted `-1` for `[x0, x1]` (otherwise, we won't consider this data sample now). That is to say, according to our perceptron model:\n",
        "\n",
        "    `a == w0*x0 + w1*x1 + b < 0`\n",
        "    \n",
        "It is natural to take measures to increase `a`. As shown intuitively above, we can update the model parameters to \"rotate\" the classification boundary, so let us consider `w0` and `w1` for now.\n",
        "\n",
        "> (If you feel uncomfortable about leaving `b` behind for now, please check [Chapter1.1 @ Equation 1.2][Abu-Mostafa et al. 2012] for a side note. The note is about treating the bias `b` as a special coefficient `w_b`. So we can bring `b` into the training framework below).\n",
        "\n",
        "- Given a certain step size, say 0.1 -- `dw = (dw0, dw1)` and  $\\sqrt{dw_0^2 + dw_1^2} = 0.1$ -- the most efficient way to let `a == w0*x0 + w1*x1` increase is to arrange `dw0` and `dw1` proportional to `x0` and `x1`.\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "\\frac{dw_0}{dw_1} = \\frac{dx_0}{dx_1}\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "<span style=\"color:green\">__EXERCISE__</span>\n",
        "\n",
        "Sketch an illustration in a 2D plane, draw vectors of `x` and `w`, show why $\\frac{dw_0}{dw_1} = \\frac{dx_0}{dx_1}$ is most efficient given a fixed step size.\n",
        "\n",
        "\n",
        "[Abu-Mostafa et al. 2012]:http://amlbook.com/"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "H-KW0UfsZ9XM",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:green\">__EXERCISE (Main)__</span>\n",
        "\n",
        "Create a perceptron and examine its performance on the training dataset in the cell below (the same as done in the previous section). \n",
        "\n",
        "Then study the code block \"Individual Training Step\" below. Try to get a perceptron with complete fit to the data."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "id": "MrIaN5PzZ9XM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "perceptron_on_train = MyPerceptron2D()\n",
        "show_perceptron_model(perceptron_on_train, X_easy, y_easy)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "w3WQ7JmfZ9XN",
        "colab_type": "text"
      },
      "source": [
        "#### Individual Training Step"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [],
        "hidden": true,
        "id": "loFsNH2IZ9XN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Study Single Step Training\n",
        "\n",
        "# Let the perceptron predict for X-samples and find where it makes mistakes\n",
        "prediction_on_X_easy = perceptron_on_train.predict(X_easy)\n",
        "E_in_index = list(np.nonzero(prediction_on_X_easy != y_easy)[0])\n",
        "print(\"Error-in @\", E_in_index)\n",
        "\n",
        "if len(E_in_index) > 0:\n",
        "    # Take one problematic sample \n",
        "    to_fix_index = E_in_index[0]\n",
        "    to_fix_sign = y_easy[to_fix_index]\n",
        "    dw = X_easy[to_fix_index]\n",
        "\n",
        "    # To normalise the change to our prescribed stepsize 0.1\n",
        "    stepsize = 0.1\n",
        "    dw = dw / np.linalg.norm(dw) * stepsize * to_fix_sign\n",
        "    print(\"Proposed adjustment of w {} (after normalisation), sign {}\"\n",
        "          .format(dw, to_fix_sign))\n",
        "\n",
        "    # Apply the update and show\n",
        "    perceptron_on_train.update(dw0=dw[0], dw1=dw[1], db=0, verbose=True)\n",
        "else:\n",
        "    print(\"Done training\")\n",
        "    \n",
        "show_perceptron_model(perceptron_on_train, X_easy, y_easy)\n",
        "\n",
        "# you may want to check individual samples (see the image) by using\n",
        "# `show_cifar_image` as above. "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "heading_collapsed": true,
        "hidden": true,
        "id": "_RRaRMMZZ9XO",
        "colab_type": "text"
      },
      "source": [
        "#### Training Procedure"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "id": "M76CSQTUZ9XO",
        "colab_type": "text"
      },
      "source": [
        "<span style=\"color:green\">__EXERCISE (Main)__</span>\n",
        "\n",
        "1. Wrap the training code block with a loop to make a working training procedure.\n",
        "2. Copy-and-paste the definition of perceptron below, and provide the implementation of the `fit` method.\n",
        "3. Try `sklearn` perceptron implementation and train the model. Take a note on this common _interface_ of machine learning algorithm design."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dbjVbt8_3oBT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## Block added by me following exercise ##\n",
        "# copied and pasted training step, added while and break so runs until no errors\n",
        "# need to get indentation right\n",
        "\n",
        "class MyPerceptron2D:\n",
        "    def __init__(self):\n",
        "        \"\"\"\n",
        "        There are three parameters for a perceptron working on 2D data.\n",
        "        w0, w1: the coefficients of the first and second attribute x0 and x1, respectively\n",
        "        b: the bias\n",
        "        \"\"\"\n",
        "        self.w0 = 1.0\n",
        "        self.w1 = 0\n",
        "        self.b = 0\n",
        "        \n",
        "    def predict(self, x):\n",
        "        \"\"\"\n",
        "        Given a data sample (x0, x1), the perceptron first computes the \n",
        "        \"pre-activation potential\" -- a term borrowed from biological neurons --\n",
        "        using simple linear function:\n",
        "        \n",
        "            pre-activation := w0 * x0 + w1 * x1 + bias\n",
        "        \n",
        "        Note this implementation we accept numpy array as input `x`, where \n",
        "        x is of the format \n",
        "        [[x0, x1] .. for sample-0\n",
        "         [x0, x1] .. for sample-1\n",
        "         [x0, x1] .. for sample-2\n",
        "         ...]\n",
        "         \n",
        "        it contains N samples, each of 2 attributes. As a Numpy array, x provides \n",
        "        convenient access to specific attributes of all samples. We can compute\n",
        "        the pre-activation values of N samples easily as shown in the code.\n",
        "        \n",
        "        The prediction is straightforward given the pre-activation values: it amounts to\n",
        "        determine if the pre-activation is above or below zero.\n",
        "        \"\"\"\n",
        "        prediction = x[:, 0] * self.w0 \\\n",
        "            + x[:, 1] * self.w1 \\\n",
        "            + self.b\n",
        "        \n",
        "        prediction[prediction > 0] = 1\n",
        "        prediction[prediction <= 0] = -1\n",
        "        return prediction\n",
        "    \n",
        "    \n",
        "    def update(self, dw0, dw1, db, verbose=False):\n",
        "        \"\"\"\n",
        "        Incrementally adjust the model parameters\n",
        "        \"\"\"\n",
        "        if verbose:\n",
        "            print(\"Old perceptron:\", self)\n",
        "        self.w0 += dw0\n",
        "        self.w1 += dw1\n",
        "        self.b += db\n",
        "        if verbose: \n",
        "            print(\"New perceptron:\", self)\n",
        "# Use this to test the effect of making incremental adjustments to weights \n",
        "# (and bias).\n",
        "            \n",
        "    def set_param(self, w0, w1, b, verbose=False):\n",
        "        if verbose:\n",
        "            print(\"Old perceptron:\", self)\n",
        "        self.w0 = w0\n",
        "        self.w1 = w1\n",
        "        self.b = b\n",
        "        if verbose: \n",
        "            print(\"New perceptron:\", self)\n",
        "# Use this to set weights (and bias) to specific values.\n",
        "            \n",
        "            \n",
        "    def fit(self, X, y):\n",
        "      # Let the perceptron predict for X-samples and find where it makes mistakes\n",
        "      while True:\n",
        "        prediction_on_X = self.predict(X)\n",
        "        E_in_index = list(np.nonzero(prediction_on_X != y)[0])\n",
        "#         print(\"Error-in @\", E_in_index)\n",
        "# comment out for running over loop at end\n",
        "        if len(E_in_index) > 0:\n",
        "            # Take one problematic sample \n",
        "            to_fix_index = E_in_index[0]\n",
        "            to_fix_sign = y[to_fix_index]\n",
        "            dw = X[to_fix_index]\n",
        "\n",
        "            # To normalise the change to our prescribed stepsize 0.1\n",
        "            stepsize = 0.1\n",
        "            dw = dw / np.linalg.norm(dw) * stepsize * to_fix_sign\n",
        "#             print(\"Proposed adjustment of w {} (after normalisation), sign {}\"\n",
        "#                   .format(dw, to_fix_sign))\n",
        "# comment out for running over loop at end\n",
        "\n",
        "            # Apply the update and show\n",
        "            self.update(dw0=dw[0], dw1=dw[1], db=0, verbose=False)\n",
        "#             normally verbose=True, changed for running over loop at end\n",
        "        else:\n",
        "#             print(\"Done training\")\n",
        "# comment out for running over loop at end\n",
        "            break\n",
        "\n",
        "#       show_perceptron_model(self, X, y)\n",
        "# comment out for running over loop at end\n",
        "    \n",
        "    def __str__(self):\n",
        "        return \"W0:{:.2f}, W1:{:.2f}, b:{:.2f}\".format(self.w0, self.w1, self.b)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Um9lNO4r4HqC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## Also added by me - test implementation\n",
        "perceptron_on_train = MyPerceptron2D()\n",
        "perceptron_on_train.fit(X_easy, y_easy)\n",
        "show_perceptron_model(perceptron_on_train, X_easy, y_easy)\n",
        "# don't need this line as long as it's in fit()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "code_folding": [],
        "hidden": true,
        "id": "vada6pqoZ9XP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Test sklearn Perceptron\n",
        "from sklearn.linear_model import Perceptron\n",
        "\n",
        "skperceptron = Perceptron()\n",
        "# Perform training here\n",
        "skperceptron.fit(X_easy, y_easy)\n",
        "show_perceptron_model(skperceptron, X_easy, y_easy)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WYta3KLoaAUM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## Also added by me - function for test error\n",
        "def perceptron_test_error(model, X_test, y_test):\n",
        "    test_pred = model.predict(X_test)\n",
        "    test_error_num = (test_pred.astype(np.int) != y_test.astype(np.int)).sum()\n",
        "    E_test = test_error_num / len(y_test)\n",
        "    return E_test"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wEhC329Hc9vK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## Also added by me - run test error function\n",
        "#perceptron_test_error(perceptron_on_train, X_train, y_train)\n",
        "perceptron_test_error(perceptron_on_train, X_easy, y_easy)\n",
        "# should always be zero"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "hidden": true,
        "colab_type": "code",
        "id": "cdJYAqmdZAyT",
        "colab": {}
      },
      "source": [
        "## Also added by me - loop to test effect of training set size\n",
        "\n",
        "train_num = 200\n",
        "\n",
        "E_in = []\n",
        "E_test = []\n",
        "\n",
        "for i in range(500):\n",
        "    # Randomly split training/test data\n",
        "    X_train_init, X_test_init, y_train_init, y_test_init,  \\\n",
        "    ind_train_init, ind_test_init = \\\n",
        "    prepare_cifar_two_class_data(X, y, indexes)\n",
        "\n",
        "    X_train_loop, X_test_loop, \\\n",
        "    y_train_loop, y_test_loop, \\\n",
        "    ind_train_loop, ind_test_loop = prepare_cifar_two_class_separable_data(\n",
        "        X_train_init, y_train_init, ind_train_init, train_size=train_num)\n",
        "\n",
        "    # Fit perceptron\n",
        "    my_perceptron = MyPerceptron2D()\n",
        "    my_perceptron.fit(X_train_loop, y_train_loop)\n",
        "    \n",
        "    # Record training and test error\n",
        "    E_in_i = perceptron_test_error(my_perceptron, X_train_loop, y_train_loop)\n",
        "    E_in.append(E_in_i)\n",
        "    E_test_i = perceptron_test_error(my_perceptron, X_test_loop, y_test_loop)\n",
        "    E_test.append(E_test_i)\n",
        "\n",
        "E_in = np.array(E_in)\n",
        "E_test = np.array(E_test)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "owNsNjGDify6",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(\"E_in mean {:.3f}, std {:.3f}\"\n",
        "      .format(E_in.mean(), E_in.std()))\n",
        "print(\"E_test mean {:.3f}, std {:.3f}\"\n",
        "      .format(E_test.mean(), E_test.std()))\n",
        "abs_diff = np.abs(E_in - E_test)\n",
        "print(\"|E_test - E_in| mean {:.3f}, std {:.3f}\"\n",
        "      .format(abs_diff.mean(), abs_diff.std()))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "hidden": true,
        "colab_type": "text",
        "id": "5LdH4bOvhebC"
      },
      "source": [
        "__Experiment Record__\n",
        "\n",
        "| $N$ |  $E_{test} mean$ | $E_{test} sd $  | \n",
        "|---|---|---|\n",
        "| 10 |  0.077  |  0.068  |\n",
        "| 20 |  0.041  |  0.044  |\n",
        "| 50 |  0.015  |  0.020  |\n",
        "| 100 |  0.005  |  0.008  |\n",
        "\n",
        "- $N$: number of training samples\n",
        "- $E_{test} $: error on test set\n"
      ]
    }
  ]
}