sheet01_solution1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c8bd2687",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "58f810e20f7e7ebbafecc0c340f8d947",
     "grade": false,
     "grade_id": "cell-175c5b8f652e026d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Exercise Sheet 01: Concept Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfe7b582",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "2a7d49ae4e29f414cdbe6c774113a12b",
     "grade": false,
     "grade_id": "cell-0779efa0bccb27ae",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Introduction\n",
    "\n",
    "This is the first official exercise sheet. The homework sheets will usually be available at the beginning of the week and are supposed to be solved in groups of three. They have to be handed in before the next practice session. The exercises are then presented to your tutor in a small feedback session. To acquire the admission for the final exam, you will have to pass $N-1$ of the weekly provided exercise sheets.\n",
    "\n",
    "Sign up for a group on Stud.IP (See `Participants` -> `Functions/Groups`). The times mentioned there are the times for the feedback session of your group. If none of them fits, send any of the tutors an e-mail so we can try to arrange something.\n",
    "\n",
    "Your group will have a group folder in Stud.IP under `Documents`. Upload your solutions there to hand them in.\n",
    "\n",
    "All exercise sheets will use [Jupyter Notebooks](http://jupyter-notebook.readthedocs.org/en/latest/notebook.html). To be able to run these on your system, you will need to install Python and a few packages. We suggest the newest version of Python 3 and installing the conda environment as explained in the practice session and in the file \"ml-install.txt\" (found on Stud.IP in the \"Documents\" section in the Folder \"Exercises\". This was also part of Sheet 00.\n",
    "\n",
    "This week's sheet should be solved and handed in before the end of **Tuesday, April 27th, 2021**. \n",
    "Please upload your results to your group's Stud.IP folder. In case you cannot do this first sheet (due to technical or organizational problems) please upload a description of your problem instead. Your tutor will help you to solve the problems in the first feedback session and you may hand in this sheet together with the second sheet one week later."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bb66bd2",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3445e4bfe7f8596d188e405492a7bb10",
     "grade": false,
     "grade_id": "cell-d0903956896707a2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Assignment 1: Candidate Elimination (by Hand) [6 Points]\n",
    "\n",
    "Candidate Elimination is a learning algorithm that, in each step, tries to generate a description which is consistent with all previously observed examples in a training set. That description could hypothetically then be used to classify examples outside the training set.\n",
    "\n",
    "Consider the following situation:\n",
    "\n",
    "Earl and Fran have made it their mission to visit as many amusement parks as possible after the pandemic. However, to maximize their enjoyment and not have any unnecessary arguments break out, they make a list of previous park visits and if they would go there again, to have a few criteria to decide if a park is worth their time.\n",
    "\n",
    "This is the set of attributes along with their possible values Earl and Fran came up with:\n",
    "\n",
    "| Attribute           | driving distance | ticket price      | rollercoasters | dinosaurs |\n",
    "|---------------------|------------------|-------------------|----------------|-----------|\n",
    "| **Possible Values** | short / far      | cheap / expensive | many / none    | yes / no  |\n",
    "\n",
    "This is Earl and Fran's accumulated data from previous visits. The list will allow you to come to a learning decision which properties have to be fulfilled such that the two will enjoy a visit to an amusement park.\n",
    "\n",
    "| Sample No. | driving distance | ticket price | rollercoasters | dinosaurs | go again? |\n",
    "|------------|------------------|--------------|----------------|-----------|-----------|\n",
    "| 1          | far              | cheap        | many           | no        | yes       |\n",
    "| 2          | short            | expensive    | many           | no        | yes       |\n",
    "| 3          | far              | expensive    | none           | yes       | no        |\n",
    "| 4          | short            | cheap        | none           | yes       | no        |\n",
    "| 5          | short            | cheap        | many           | yes       | yes       |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d65bceb1",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0b4703448c8b663770de21b564adc7d3",
     "grade": false,
     "grade_id": "cell-f5cd6d758c895950",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "**a)** Apply Candidate Elimination to the samples 1-5 below and provide the version space boundaries $S_n$ and $G_n$ after each new training sample.  "
   ]
  },
  {
   "cell_type": "raw",
   "id": "ad16b5d9",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ada5bc9c567910968637a1eb2570d738",
     "grade": true,
     "grade_id": "cell-ab417b404920afe1",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "G0 = {<?, ?, ?, ?>}                      S0 = { <ø, ø, ø, ø>} \n",
    "\n",
    "G1 = {<?, ?, ?, ?>}                      S1 = {<far, cheap, many, no>} \n",
    "\n",
    "G2 = {<?, ?, ?, ?>}                      S2 = {<?, ?, many, no>}\n",
    "\n",
    "G3 = { <?, ?, many, ?> , <?, ?, ?, no> } S3 = {<?, ?, many, no>}\n",
    "\n",
    "G4 = { <?, ?, many, ?> , <?, ?, ?, no>}  S4 = {<?, ?, many, no>}\n",
    "\n",
    "G5 = { <?, ?, many, ?> }                 S5 = {<?, ?, many, ?>}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eed3e223",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5cd47301fa3634fba84344fd78bfdc05",
     "grade": false,
     "grade_id": "cell-e5db1c57702dcd02",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "**b)** Provide the complete version space bounded by $S_2$ and $G_2$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90c0d6fd",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "bc20c4edb1006df2e6741d2b0f3f3471",
     "grade": true,
     "grade_id": "cell-ef42d1e895e9cff6",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "\n",
    "< ?, ? many, no>, < ?, ? many, ?>, < ?, ? ?, no>,  < ?, ? ?, ?>, \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d43ad798",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "456f728ea77936ea39878de7fec2f127",
     "grade": false,
     "grade_id": "cell-2375670feb946ca2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "**c)** To what kind of amusement park should Earl and Fran go?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8187064a",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "7201025262854ebb6de52f98775a5d85",
     "grade": true,
     "grade_id": "cell-8aa8761eb3b1780c",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "To a park with many rollercoasters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76f7917a",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "04546761beb70df65e9f34a7e7cd7bb2",
     "grade": false,
     "grade_id": "cell-c0e07cdee1f5cee5",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Assignment 2: Candidate Elimination (in Python) [10 Points]\n",
    "\n",
    "Now let's get to real fun part: Programming our first machine learning algorithm!\n",
    "\n",
    "But first some general remarks on coding style:\n",
    "\n",
    "In general, try to write code that's consistent with [PEP8](https://www.python.org/dev/peps/pep-0008/), the offical Python Style Guide. Have a look a the [Google Style Guide](https://google.github.io/styleguide/pyguide.html) as well. It's based on PEP8 and has some nice examples. As a bonus always document your function and classes with docstrings. It is best practice to stick to some docstring convention for example [Google's](http://sphinxcontrib-napoleon.readthedocs.io/en/latest/example_google.html). This has the big advantages that it allows for automated generation of documentation. We will follow that convention in the code we provide you, so you know what kind of objects to expect and what to return.\n",
    "\n",
    "If, during the programming tasks, you run into a `NameError`, make sure that you executed all prior code cells beforehand. Later cells might rely on variables and function from prior cells. To see all currently defined variables you can make use of the `%whos` [magic function](https://github.com/lmmx/devnotes/wiki/IPython-'magic'-function-documentation#whos) anywhere in code cells. Additionally, it is sometimes handy to run all cells from the beginning by opeining the command palette typing `run all cells`. Moreover, using <kbd>b</kbd> to add new cells below and <kbd>a</kbd> for adding new cells above your current cell will make your life often easier. Finally, using <kbd>l</kbd>  to show line numbers is helpful for locating errors from error messages.\n",
    "\n",
    "In the following Python code we have provided the building blocks for the `CANDIDATE-ELIMINATION` algorithm and put them together in a single function. Now you have to fill those building blocks with actual code. There are places marked with \n",
    "\n",
    "```python\n",
    "# YOUR CODE HERE\n",
    "``` \n",
    "\n",
    "where you have to add some code to make the code work. Finish the code to automate the decision making for Earl and Fran!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee1a0616",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "bfa9e6e6",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "0229c6d379732875bc56908b36338d2b",
     "grade": true,
     "grade_id": "ex2_solution1",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def is_consistent(h, datum):\n",
    "    \"\"\"\n",
    "    Checks if a general hypothesis is consistent with a datum.\n",
    "    \n",
    "    Args:\n",
    "        h (tuple): Hypothesis.\n",
    "        datum (dict): Datum with values and target.\n",
    "        \n",
    "    Returns:\n",
    "        bool: Whether the hypothesis correctly predicts the target value.\n",
    "    \"\"\"\n",
    "    \n",
    "    for i in range(0,len(h)):\n",
    "        if not((h[i] == datum['values'][i]) | (h[i] == '?')):\n",
    "            return bool(1-datum[\"target\"])\n",
    "        \n",
    "    return datum[\"target\"]\n",
    "    \n",
    "\n",
    "assert is_consistent(('far', 'cheap', '?', 'no'), {'values': ('far', 'cheap', 'many', 'no' ), 'target': True })\n",
    "\n",
    "#is_consistent(('far', 'cheap', '?', 'no'), {'values': ('far', 'cheap', 'many', 'no' ), 'target': True })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2c73f530",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9f735cab47c40fb4f3472bc874c1ec11",
     "grade": true,
     "grade_id": "ex2_solution2",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def is_more_general_or_equal(h1, h2):\n",
    "    \"\"\"\n",
    "    Checks whether hypothesis h1 is more general than hypothesis h2 or equally general.\n",
    "    \n",
    "    Args:\n",
    "        h1 (tuple): Hypothesis 1.\n",
    "        h1 (tuple): Hypothesis 2.\n",
    "    \n",
    "    Returns:\n",
    "        bool: True if the predicate is satisfied.\n",
    "    \"\"\"\n",
    "    for i in range(0, len(h1)):\n",
    "        if not((h1[i] == h2[i]) | (h1[i] == '?')):\n",
    "            return False\n",
    "        \n",
    "    return True\n",
    "    \n",
    "assert is_more_general_or_equal(('?', '?', '?', '?'), ('far', 'cheap', 'many', 'no'))\n",
    "assert not is_more_general_or_equal(('?', '?', 'many', 'no'), ('far', 'cheap', 'many', '?'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "34822295",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "df8deb87e361b57ada1647006d5dfd95",
     "grade": true,
     "grade_id": "ex2_solution3",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def is_more_specific_or_equal(h1, h2):\n",
    "    \"\"\"\n",
    "    Checks whether hypothesis h1 is more specific than hypothesis h2 or equally specific.\n",
    "    \n",
    "    Args:\n",
    "        h1 (tuple): Hypothesis 1.\n",
    "        h1 (tuple): Hypothesis 2.\n",
    "    \n",
    "    Returns:\n",
    "        bool: True if the predicate is satisfied.\n",
    "    \"\"\"\n",
    "    return is_more_general_or_equal(h2, h1)\n",
    "    \n",
    "assert is_more_specific_or_equal(('?', '?', 'many', 'no'), ('?', '?', 'many', '?'))\n",
    "assert is_more_specific_or_equal(('?', '?', 'many', 'no'), ('?', '?', 'many', 'no'))\n",
    "assert is_more_specific_or_equal(('?', '?', '?', '?'), ('?', '?', '?', '?'))\n",
    "assert not is_more_specific_or_equal(('?', 'cheap', 'many', 'no'), ('far', '?', '?', '?'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "e9cef509",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3e2ad6068aeecde99a45a7a94847dcdc",
     "grade": true,
     "grade_id": "ex2_solution4",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def generalize_minimally(h, datum):\n",
    "    \"\"\"Generalize hypothesis h so it becomes consitent with the datum.\n",
    "    \n",
    "    Args:\n",
    "        h (tuple): The hypothesis to be generalized.\n",
    "        datum (tuple): Attribute values of a datum. The datum is assumed to have a positive target value.\n",
    "    \n",
    "    Returns:\n",
    "        tuple: The generalized hypothesis.\n",
    "    \"\"\"\n",
    "    \"\"\"\n",
    "    h = list(h)\n",
    "    output = []\n",
    "    for i in range(0, len(h)):\n",
    "        if(h[i] != datum[i]):\n",
    "            if(h[i] == '0'):\n",
    "                output.append(datum[i])\n",
    "            else:\n",
    "                \n",
    "                output.append('?')\n",
    "        else:\n",
    "            output.append(h[i])\n",
    "    \n",
    "    print(\"generalize_minimally: \", output)\n",
    "    return tuple(output)\n",
    "    \"\"\"\n",
    "    h = list(h)\n",
    "    output = []\n",
    "    for i in range(0, len(h)):\n",
    "        if(h[i] == datum[i] or h[i] == '0'):\n",
    "\n",
    "            output.append(datum[i])\n",
    "\n",
    "        else:\n",
    "            output.append('?')\n",
    "    \n",
    "    #print(\"generalize_minimally: \", output)\n",
    "    return tuple(output)\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "    \n",
    "assert generalize_minimally(('?', '?', 'many', 'no'), ('short', 'cheap', 'many', 'yes')) == ('?', '?', 'many', '?')\n",
    "assert generalize_minimally(('0', '0', '0', '0'), ('short', 'cheap', 'many', 'yes')) == ('short', 'cheap', 'many', 'yes')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5b61da72",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "928a71ea77289f29e5d20103aa5b685d",
     "grade": true,
     "grade_id": "ex2_solution5",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def specialize_minimally(h, datum, attr_values):\n",
    "    \"\"\"\n",
    "    Generate all consistent minimal specialization of hypothesis h.\n",
    "    \n",
    "    Args:\n",
    "        h (tuple): The hypothesis to be specialized.\n",
    "        datum (tuple): Attribute values of a datum. The datum is assumed to have a negative target value.\n",
    "        attr_values (tuple of tuples): All possible attribute values for each attribute.\n",
    "    \n",
    "    Returns:\n",
    "        tuple of tuples: Tuple of the specialized hypotheses.\n",
    "    \"\"\"\n",
    "    output = []\n",
    "    for i in range(0, len(h)):\n",
    "        if(h[i] == '?' and datum[i] != '?'):\n",
    "            newSpecialization = []\n",
    "            for j in range(0, len(h)):\n",
    "                if j == i:\n",
    "                    if datum[i] == attr_values[i][0]:\n",
    "                        newSpecialization.append(attr_values[i][1])\n",
    "\n",
    "                    else:\n",
    "                        newSpecialization.append(attr_values[i][0])\n",
    "\n",
    "                else:\n",
    "\n",
    "                    newSpecialization.append(h[j])\n",
    "\n",
    "\n",
    "            output.append(tuple(newSpecialization))   \n",
    "            \n",
    "    #print(\"specialize_minimally: \", output)\n",
    "    return tuple(output)\n",
    "\n",
    "attr_values = (('short', 'far'), ('cheap', 'expensive'), ('many', 'none'), ('yes', 'no'))\n",
    "assert specialize_minimally(('?', '?', 'many', 'no'), ('short', 'cheap', 'many', 'no'), attr_values) == (('far', '?', 'many', 'no'), ('?', 'expensive', 'many', 'no'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3731b7b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "113fceeb10337e3cec2bd17e71f3a3e2",
     "grade": false,
     "grade_id": "cell-eed96524af5d38e7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Now check that the algorithm works in the intended way by excecuting the cells below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "a6e7db64",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "05fafec19305a3fd93d0444af9a92260",
     "grade": false,
     "grade_id": "cell-5ff73aa56439d69d",
     "locked": true,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def eliminate_candidates(data, attr_values):\n",
    "    \"\"\"\n",
    "    Candidate elimination algorithm printing its progress at each step.\n",
    "    \n",
    "    Args:\n",
    "        data (list of dicts): The dataset.\n",
    "        attr_values (tuple of tuples): All possible attribute values for each attribute in the data.\n",
    "        \n",
    "    Returns:\n",
    "        tuple: The general and the specific boundary of the version space.\n",
    "    \"\"\"\n",
    "    # Initialize general and specific boundary.\n",
    "    \n",
    "    # Maximally general hypothesis.\n",
    "    general_boundary = [tuple('?') * len(attr_values)]\n",
    "    # Maximally specific hypothesis.\n",
    "    specific_boundary = [tuple('0') * len(attr_values)]\n",
    "    \n",
    "    # Fit the version space to the data.\n",
    "    for datum in data:\n",
    "        if datum['target']:\n",
    "            # If the sample is classified as positive...\n",
    "            \n",
    "            # Remove all inconsistent hypotheses from G.\n",
    "            general_boundary = [g for g in general_boundary if is_consistent(g, datum)]\n",
    "            \n",
    "            for s in specific_boundary:\n",
    "                # Remove all inconsistent hypothesis from S.\n",
    "                if not is_consistent(s, datum):\n",
    "                    specific_boundary.remove(s)\n",
    "\n",
    "                    # Add to S all minimal generalizations s. In this case only one.\n",
    "                    s_generalized = generalize_minimally(s, datum['values'])\n",
    "                    # Add the new hypothesis to the specific boundary, if it is not more general \n",
    "                    # than the general boundary. We do not need to check for consistency again\n",
    "                    # as the hypothesis was constructed in such a way that it must be consistent.\n",
    "                    if any(is_more_general_or_equal(g, s_generalized) for g in general_boundary):\n",
    "                        specific_boundary.append(s_generalized)\n",
    "\n",
    "            # Remove from S any hypothesis that is more general than another hypothesis in S.\n",
    "            for s in specific_boundary:\n",
    "                if any(is_more_general_or_equal(s, s2) \n",
    "                       and not s == s2 for s2  \n",
    "                       in specific_boundary):\n",
    "                    \n",
    "                    specific_boundary.remove(s)\n",
    "\n",
    "        else:\n",
    "            # If the sample is classified as negative...\n",
    "            \n",
    "            # Remove all inconsistent hypotheses from S.\n",
    "            specific_boundary = [s for s in specific_boundary if is_consistent(s, datum)]\n",
    "            for g in general_boundary:\n",
    "                # Remove all inconsistent hypotheses from G.\n",
    "                if not is_consistent(g, datum):\n",
    "                    general_boundary.remove(g)\n",
    "\n",
    "                    # Add to G all minimal specializations of g.\n",
    "                    for specialized_g in specialize_minimally(g, datum['values'], attr_values):\n",
    "                        # Add the new specialized hypothesis to the general boundary, if it is not more \n",
    "                        # specific than the specific boundary.\n",
    "                        # We do not need to check for consistency again\n",
    "                        # as the hypothesis was constructed in such a way that it must be consistent.\n",
    "                        if any(is_more_specific_or_equal(s, specialized_g) for s in specific_boundary):\n",
    "                                \n",
    "                                general_boundary.append(specialized_g)\n",
    "                \n",
    "                # Remove from G any hypothesis that is less general than another hypothesis in G.\n",
    "                for g in general_boundary:\n",
    "                    if any(is_more_specific_or_equal(g, g2) \n",
    "                           and not g == g2 for g2 \n",
    "                           in general_boundary):\n",
    "                        \n",
    "                        general_boundary.remove(g)\n",
    "        \n",
    "        # Print progress of algorithm at each iteration.\n",
    "        print('Sample: {} {}\\nG: {}\\nS: {}\\n'.format('+' if datum['target'] else '-', datum['values'],\n",
    "                                                     general_boundary, specific_boundary))\n",
    "        \n",
    "    return general_boundary, specific_boundary\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "bb65f56b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "065173df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sample: + ('far', 'cheap', 'many', 'no')\n",
      "G: [('?', '?', '?', '?')]\n",
      "S: [('far', 'cheap', 'many', 'no')]\n",
      "\n",
      "Sample: + ('short', 'expensive', 'many', 'no')\n",
      "G: [('?', '?', '?', '?')]\n",
      "S: [('?', '?', 'many', 'no')]\n",
      "\n",
      "Sample: - ('far', 'expensive', 'none', 'yes')\n",
      "G: [('?', '?', 'many', '?'), ('?', '?', '?', 'no')]\n",
      "S: [('?', '?', 'many', 'no')]\n",
      "\n",
      "Sample: - ('short', 'cheap', 'none', 'yes')\n",
      "G: [('?', '?', 'many', '?'), ('?', '?', '?', 'no')]\n",
      "S: [('?', '?', 'many', 'no')]\n",
      "\n",
      "Sample: + ('short', 'cheap', 'many', 'yes')\n",
      "G: [('?', '?', 'many', '?')]\n",
      "S: [('?', '?', 'many', '?')]\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([('?', '?', 'many', '?')], [('?', '?', 'many', '?')])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "attr_values = (('short', 'far'), ('cheap', 'expensive'), ('many', 'none'), ('yes', 'no'))\n",
    "\n",
    "# samples\n",
    "data = [ \n",
    "    {'values': ('far',   'cheap',     'many', 'no' ), 'target': True },\n",
    "    {'values': ('short', 'expensive', 'many', 'no' ), 'target': True },\n",
    "    {'values': ('far',   'expensive', 'none', 'yes'), 'target': False},\n",
    "    {'values': ('short', 'cheap',     'none', 'yes'), 'target': False},\n",
    "    {'values': ('short', 'cheap',     'many', 'yes'), 'target': True }\n",
    "]\n",
    "\n",
    "eliminate_candidates(data, attr_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b7ae827",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f0c236e39672214b868e7126f82e45ed",
     "grade": false,
     "grade_id": "ex2_test",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d828c88e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c12cda74",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "da9a6906",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0712de6217ad4c4517b45ce204574302",
     "grade": false,
     "grade_id": "cell-e8704cc99397489d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Assignment 3: Inductive Bias [4 Points]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56f94504",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fd0acfdf4a321604a638f246e6929f77",
     "grade": false,
     "grade_id": "cell-0cac3f19657cf08e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "**a)** What is an inductive bias? Describe the concept in your own words! Why do we need it?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02e89799",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "15b3628f689236ea808512a2b7c2e976",
     "grade": true,
     "grade_id": "cell-ef3d6719a20fcc57",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "A fundamental a priori assumption or set of assumptions that the learner makes about the target function that enables it to generalize beyond the training data."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4e702e6",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b92b9dc60ffc40224adcdf36cc5242e1",
     "grade": false,
     "grade_id": "cell-d2f09c6e12b491df",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "**b)** Describe and compare the inductive bias for the learning algorithms you heard about in the lecture (Candidate Elimination and Find-S)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9474946d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "44a1a3d34646896580136d5a6853d431",
     "grade": true,
     "grade_id": "cell-4ebc56901ad0ad00",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "In Candidate-Elimination, the target concept c is contained in the hypothesis space H. While in the Find-S, the target concept can be described in its hypothesis space. Since only positive examples are taken into account, the negative examples have no influence. Therefore Find-S has a stronger bias."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit Metadata",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}