{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS 521 Midterm 1 Notes",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a7d76528-e2fe-4b2a-cded-0740eeeaa893"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 111,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4bcd12f7-58be-4e03-d7b2-117061c095b7"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 112,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 113,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "- Aristotle was first to explore rationality. \n",
        "- Rene Descartes: I think therefore I am. \n",
        "- David Hume: induction\n",
        "  \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "- Searle: weak AI (act as if intelligent) vs strong AI (actually inteligent)\n",
        "- Turing and Hubert Dreyfus believe human behavior is too complex to be captured by formal set of rules.\n",
        "- Embodied cognitition: must study brain and body together\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "- Searle: biological naturalism\n",
        "- Can machines have consiousness?\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "- Agent acts only on things it has perceived in past, nothing it hasn't perceived. \n",
        "- Agent's behavior is described by the agent function \"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "- A rational agent selects an action to maximize its performance measure given its percept sequence and any other built-in knowledge\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "- First define task environment per PEAS \n",
        "- Fully observable vs partially observable (or unobservable if no sensors) \n",
        "- Single-agent vs multiagent \n",
        "- Deterministic vs nondeterministic \n",
        "     - Stochastic if probabilities, nondeterministic if possibilities aren't listed with probabilities \n",
        "- Epsisodic vs sequential (independent tasks vs dependent tasks) \n",
        "- Static vs dynamic (semidynamic if environment doesn't change but performance score does ie chess) \n",
        "- Discrete vs continuous (time and state) \n",
        "- Known vs unknown (outcomes are given for all actions) \n",
        "     - A game can be fully observable but unknown if you see everything but don't know how to play it \n",
        "- Hardest: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "- agent = architecture + program\n",
        "- table-driven agent: rational but impractical due to size\n",
        "- simple reflex agent: works on current percept only\n",
        "- randomization can help escape loops\n",
        "- model-based agent: maintains internal state that depends on the percept history and reflects some unobserved stuff of current state\n",
        "     - transition model and sensor model\n",
        "     - ex: autonomous car\n",
        "- goal-based agent: search and planning\n",
        "- utility-based agent: maximize utility\n",
        "- learning agent: uses feedback from a critic to determine how to act in the future\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "AI Philosophy \n",
        "- Rene Descartes: I think therefore I am (dualism) \n",
        "- 17th and 18th century automatons (test intelligence with language)\n",
        "- Turing: Can machines think to the point humans cant tell the difference\n",
        "- John Searle: The Chinese Room\n",
        "     - Turing Test can be completed with just symbol manipulation\n",
        "     - Brains cause minds and computers can't have minds\n",
        "- Daniel Dennett: Brain in a vat (no difference between brain and processor)\n",
        "\n",
        "Agents\n",
        "- Easiest task environment: static, fully observable, deterministic, discrete\n",
        "- Reflex agents only act based on current percept (Roomba)\n",
        "- Problem solving agents work ahead (puzzle)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"Turing Test\" : \"Do people consider a machine human in language?\",\n",
        "\"agent\" : \"anything that can perceive through sensors and act through actuators in an environment\",\n",
        "\"rational agent\" : \"agent that acts to achieve the best (expected) outcome\",\n",
        "\"dualism\" : \"mind is separate from body\",\n",
        "\"materialism\" : \"the mind is the brain operating per the laws of physics\",\n",
        "\"percept\" : \"what the agent's sensors perceive\",\n",
        "\"percept sequence\" : \"complete history of all the agent has ever perceived\",\n",
        "\"agent function\": \"maps a percept sequence to an action\",\n",
        "\"agent program\" : \"the concrete implementation of the agent function\",\n",
        "\"performance measure\" : \"how good of a state the agent is in\",\n",
        "\"task environment\" : \"the problems agents solve\",\n",
        "\"PEAS\" : \"Performance measure, Environment, Actuators, Sensors\",\n",
        "\"actuator\" : \"how the agent performs an action\",\n",
        "\"agent architecture\" : \"physical part of agent\"\n",
        "}"
      ],
      "execution_count": 114,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a5cadba9-a704-4020-c0e5-8e6d353df540"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 115,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n- Aristotle was first to explore rationality. \n- Rene Descartes: I think therefore I am. \n- David Hume: induction\n  \n\n## AIMA Chapter 27.1 The Limits of AI\n\n- Searle: weak AI (act as if intelligent) vs strong AI (actually inteligent)\n- Turing and Hubert Dreyfus believe human behavior is too complex to be captured by formal set of rules.\n- Embodied cognitition: must study brain and body together\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n- Searle: biological naturalism\n- Can machines have consiousness?\n\n\n## AIMA 2.1 Agents and Environments\n \n- Agent acts only on things it has perceived in past, nothing it hasn't perceived. \n- Agent's behavior is described by the agent function \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- A rational agent selects an action to maximize its performance measure given its percept sequence and any other built-in knowledge\n\n\n## AIMA 2.3 The Nature of Environments\n\n- First define task environment per PEAS \n- Fully observable vs partially observable (or unobservable if no sensors) \n- Single-agent vs multiagent \n- Deterministic vs nondeterministic \n     - Stochastic if probabilities, nondeterministic if possibilities aren't listed with probabilities \n- Epsisodic vs sequential (independent tasks vs dependent tasks) \n- Static vs dynamic (semidynamic if environment doesn't change but performance score does ie chess) \n- Discrete vs continuous (time and state) \n- Known vs unknown (outcomes are given for all actions) \n     - A game can be fully observable but unknown if you see everything but don't know how to play it \n- Hardest: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown\n\n\n## AIMA 2.4 The Structure of Agents\n\n- agent = architecture + program\n- table-driven agent: rational but impractical due to size\n- simple reflex agent: works on current percept only\n- randomization can help escape loops\n- model-based agent: maintains internal state that depends on the percept history and reflects some unobserved stuff of current state\n     - transition model and sensor model\n     - ex: autonomous car\n- goal-based agent: search and planning\n- utility-based agent: maximize utility\n- learning agent: uses feedback from a critic to determine how to act in the future\n\n\n## Module 1 Lecture Notes\n\nAI Philosophy \n- Rene Descartes: I think therefore I am (dualism) \n- 17th and 18th century automatons (test intelligence with language)\n- Turing: Can machines think to the point humans cant tell the difference\n- John Searle: The Chinese Room\n     - Turing Test can be completed with just symbol manipulation\n     - Brains cause minds and computers can't have minds\n- Daniel Dennett: Brain in a vat (no difference between brain and processor)\n\nAgents\n- Easiest task environment: static, fully observable, deterministic, discrete\n- Reflex agents only act based on current percept (Roomba)\n- Problem solving agents work ahead (puzzle)\n\n\n## Module 1 Definitions\n* **Turing test** - Do people consider a machine human in language?\n* **Agent** - anything that can perceive through sensors and act through actuators in an environment\n* **Rational agent** - agent that acts to achieve the best (expected) outcome\n* **Dualism** - mind is separate from body\n* **Materialism** - the mind is the brain operating per the laws of physics\n* **Percept** - what the agent's sensors perceive\n* **Percept sequence** - complete history of all the agent has ever perceived\n* **Agent function** - maps a percept sequence to an action\n* **Agent program** - the concrete implementation of the agent function\n* **Performance measure** - how good of a state the agent is in\n* **Task environment** - the problems agents solve\n* **Peas** - Performance measure, Environment, Actuators, Sensors\n* **Actuator** - how the agent performs an action\n* **Agent architecture** - physical part of agent\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "- print(\"%s can speak %d languages\" % (\"C3PO\",6000))\n",
        "- referential equality: is\n",
        "- Shallow copy: x[:]\n",
        "- Slicing is zero indexed and [1:-1:2] gets the every other from the first index to second to last index\n",
        "- li.sort() is in place, sorted(li) is a copy\n",
        "- defaultdict automatically initializes nonexistent dictionary values\n",
        "- Counters are defaultdicts for counting keys\n",
        "- No function overloading\n",
        "- *args: accept a variable # of non-keyword arguments \n",
        "- **kwargs: accept a variable # of keywork arguments \n",
        "- Can put a dictionary as a function parameter to make it updateable \n",
        "- Duck typing\n",
        "- Dictionary comprehension: {k:v for k,v in li}\n",
        "- Set comprehension: {x for x in li}\n",
        "- Generators use yield, pause, and resume again when called next \n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 116,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 443
        },
        "outputId": "70c3e18a-adf1-46ef-c048-c2a11168ffa7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 117,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\n- print(\"%s can speak %d languages\" % (\"C3PO\",6000))\n- referential equality: is\n- Shallow copy: x[:]\n- Slicing is zero indexed and [1:-1:2] gets the every other from the first index to second to last index\n- li.sort() is in place, sorted(li) is a copy\n- defaultdict automatically initializes nonexistent dictionary values\n- Counters are defaultdicts for counting keys\n- No function overloading\n- *args: accept a variable # of non-keyword arguments \n- **kwargs: accept a variable # of keywork arguments \n- Can put a dictionary as a function parameter to make it updateable \n- Duck typing\n- Dictionary comprehension: {k:v for k,v in li}\n- Set comprehension: {x for x in li}\n- Generators use yield, pause, and resume again when called next \n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "- States\\n\n",
        "- Initial state\\n\n",
        "- Actions\\n\n",
        "- Transition model\\n\n",
        "- Goal state\\n\n",
        "- Action cost\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 118,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 585
        },
        "outputId": "d61f629a-2cbc-4e17-d5d9-9098b759c292"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 119,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n\n- States\n\n- Initial state\n\n- Actions\n\n- Transition model\n\n- Goal state\n\n- Action cost\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 120,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 339
        },
        "cellView": "form",
        "outputId": "f8d1810e-883c-4fc8-f561-7a154ba596ec"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 121,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "- Use minimax for perfect info, zero-sum games\\n\n",
        "- Game elements:\\n\n",
        "   - initial state\\n\n",
        "   - terminal states\\n\n",
        "   - whose turn it is\\n\n",
        "   - set of legal moves\\n\n",
        "   - transition model\\n\n",
        "   - utility function\\n\n",
        "- Minimax is DFS\\n\n",
        "- Time complexity: O(b^m)\\n\n",
        "- Space complexity: O(bm) if all actions at once, O(m) if one action at a time (generator)\\n\n",
        "Expectimax:\\n\n",
        "- Time complexity: O(b^m * n^m) where n is number of distinct dice rolls\\n\n",
        "- Partially observable\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 122,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 965
        },
        "outputId": "dca1bed0-6ee5-44f7-ea06-7bb0a2086ed4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 123,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n\n- Use minimax for perfect info, zero-sum games\n\n- Game elements:\n\n   - initial state\n\n   - terminal states\n\n   - whose turn it is\n\n   - set of legal moves\n\n   - transition model\n\n   - utility function\n\n- Minimax is DFS\n\n- Time complexity: O(b^m)\n\n- Space complexity: O(bm) if all actions at once, O(m) if one action at a time (generator)\n\nExpectimax:\n\n- Time complexity: O(b^m * n^m) where n is number of distinct dice rolls\n\n- Partially observable\n\n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "- X is set of variables {X_1,...,X_n}\n",
        "- D is set of domains {D_1,...,D_n} \n",
        "- C is set of constraints st C_j is <scope, rel>\n",
        "   - scope is the variables that are part of the constraint\n",
        "   - rel is the values the variables can take on\n",
        "- CSPs are NP-complete in general but there are faster subproblems\n",
        "- simplest CSPs have variables that have discrete and finite domains\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- CSP algorithm can generate successors by either choosing a new variable assignment or making inference\n",
        "/n\n",
        "AC-3: has queue of arcs to consider\n",
        "- Initially: queue has all arcs in CSP\n",
        "- Pops off an aribtrary arc (X_i,X_j) and makes X_i arc-consistent wrt X_j\n",
        "- If D_i becomes smaller, add all arcs (X_k, X_i) where X_k is a neighbor of X_i and not X_j\n",
        "- If D_i is now empty, return failure\n",
        "- If D_i is not empty, repeat the above\n",
        "- Return result once queue is empty\n",
        "\n",
        "- AC-3 runtime is O(cd^3) where c = # of binary constraints and d = max domain\n",
        "   - Checking arc consistency takes O(d^2) and each constraint c can be added in the queue d^2 times\n",
        "\n",
        "Path consistency:\n",
        "- Need path consistency to solve map coloring problems (stronger than arc consistency)\n",
        "- {X_i,X_j} are path consistent wrt X_m if each consistent assignment , there is also an assignment to X_m that satisfies constraints of {X_i,X_m} and {X_m,X_j}\n",
        "\n",
        "K-conistency:\n",
        "- k=1: given the empty set, we can make any set of one variable consistent (node consistency)\n",
        "- k=2: arc consistency\n",
        "- k=3: path consistency\n",
        "- k-consistency is to induction as strong k-consistency is to strong induction\n",
        "- strongly n-consistent: takes O(n^2*d) time and exponential space\n",
        "\n",
        "Global constraints\n",
        "- In Alldiff, if m variables are involved in the constraint with n possible distinct values st m>n, then no solution\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Backtracking search:\n",
        "  - Repeatedly choose unassigned variable.\n",
        "  - Extend the solution into each of the variable's possible values\n",
        "  - If solved, return solution. Else if fails, go back to previous state.\n",
        "  - If no value works, return failure.\n",
        "- Backtracking search keeps only one representation of a state/assignment instead of creating new ones\n",
        "- Can improve by using domain-independent heuristics, unlike uninformed search\n",
        "Variable and value ordering:\n",
        "- Choose the variable with the fewest legal values (MRV)\n",
        "- Choose variable that affects the most unassigned variables (degree) as a tiebreaker \n",
        "- Choose the value to try per the least-constraining-value heuristic\n",
        "Interleaving search and inference:\n",
        "- AC-3 is pure inference\n",
        "- Forward checking algorithm\n",
        "   - Assign variable X\n",
        "   - Establish arc consistency for X\n",
        "      - for each unassigned variable Y neighboring X, delete values from domain inconsistent with the assignment of X\n",
        "      - backtrack if failure reported\n",
        "- Best to combine MRV heuristic with forward checking\n",
        "- Forward checking only looks one variable ahead\n",
        "- Maintaining Arc Consistency (MAC) algorithm\n",
        "   - Assign variable X_i\n",
        "   - Run AC-3 with the queue initialized as the arcs (X_j,X_i) for all unnassigned neighbors X_j of X_i\n",
        "   - backtrack if failure reported\n",
        "- MAC recursively propagates constraints when changes are made to the domains of variables, unlike forward checking\n",
        "Intelligent backtracking:\n",
        "- Backtracking search algorithms use chronological backtracking\n",
        "- Intelligent backtracking backtracks to variable that might fix the problem\n",
        "- Keep track of the conflict set (see glossary) for the value of the domain that made the search impossible\n",
        "- Then backjumps (see glossary) \n",
        "- Backjumping method is implemented by modifying backtrack to accumulate the conflict set while checking for a legal value to assign\n",
        "- The conflict set is naturally provided by forward checking\n",
        "   - If X=x deletes value from Y's domain, add x to Y's conflict set\n",
        "- Forward checking or stronger (like MAC) means you already eliminate all possible backjump paths (so don't need to backjump ever)\n",
        "- Something called conflict-directed backjumping but I doubt it will be on test\n",
        "Constraint learning:\n",
        "- avoid again running into issues that led us to failure\n",
        "- Use constraint learnings to get the no-good set\n",
        "- Add a new constraint that forbids this combination of no-good assignments\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "- Local search algorithms for CSPs can be useful\n",
        "- Ex. for each column on a board, move the piece to the square that yields the least number of constraints (min-conflicts heuristic)\n",
        "- Runtime of min-conflicts is about independent of problem size\n",
        "- Other techniques\n",
        "  - Plateu search: allows sideways moves to another state with the same score\n",
        "  - Tabu search\n",
        "  - Constraint weighting\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "- A constraint graph is a tree when any 2 variables are connected by only one path\n",
        "- Any tree-structured CSP can be solved in linear time wrt the # of variables!!!\n",
        "- New notion of consistency: directional arc consistency (DAC)\n",
        "- Tree CSP Solver algorithm\n",
        "  1. topologically sorting it st DAC is maintained - O(nd^2) time\n",
        "  2. choose variables from start of list to end\n",
        "- Two ways to reduce constraint graph to tree: removing nodes or collapsing nodes together\n",
        "1. Cutset conditioning:\n",
        "- Assign values to some variables so the unassigned variables form a tree\n",
        "- Then solve through the above method\n",
        "- Works for binary CSPs\n",
        "- Algorithm\n",
        "   1. Choose the cycle subset S (see glossary)\n",
        "   2. For each possible assignment to the variables in the cycle subset S st all constraints on S are satisfied:\n",
        "      - Remove newly-inconsistent values from the remaining unassigned values\n",
        "      - If remaining CSP has a solution, return that solution and the assignment for S\n",
        "- O(d^c * (n-c)d^2) for cycle cutset size c\n",
        "   - d^c combinations for values in S, (n-c) remaining variables, and d^2 checks for each\n",
        "2. Tree decomposition:\n",
        "- Transform CSP into tree st each node is now a set of variables\n",
        "- 3 requirements\n",
        "   a. Every variable in original problem appears in at least one tree node\n",
        "   b. If two variables are connected by a constraint, they must appear together (along with constraint) in at least one tree node\n",
        "   c. If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes\n",
        "      - the variable must be the same across all nodes in the tree\n",
        "- Can use the TreeCSPSolver algorithm in O(nd^2) time, where n = # tree nodes and d = largest domain size (set of tuples of values)\n",
        "- Goal: make subproblems as small as possible (minimize tree width)\n",
        "- Solve problem in O(nd^{w+1}) time for w=tree width\n",
        "- CSPs with constraint graphs of bounded tree width are solvable in polytime!!!\n",
        "- Finding min tree width is NP-hard but there are heuristics\n",
        "- Tree decomposition is usually faster than cutset conditioning, but it takes exponential in w memory while cutset takes linear memory\n",
        "Value symmetry:\n",
        "- If 3 variables need to all be different values and there are d values each can be, there are d! ways to assign the values\n",
        "- This is value symmetry\n",
        "- Reduce the search space by introducing a symmetry-breaking constraint so only 1 of the d! solutions are possible\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "- CSPs are good for identification (find goal, don't care about path)\n",
        "- CSPs automatically prune all branches that violate a constraint\n",
        "- If discrete variables wit hfinite domains, then there are O(d^n) complete assignments where d is domain size\n",
        "- AC-3 is O(Nd^3) for planar graphs since # of arcs is linear in the number of nodes\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"a problem where each variable has a value that satsifies all its constraints\",\n",
        "\"consistent assignment\" : \"assignment that is valid (doesn't violate constraints)\",\n",
        "\"complete assignment\" : \"every variable has a value\",\n",
        "\"solution\" : \"complete and consistent assignment\",\n",
        "\"constraint graph\" : \"nodes = variables, edges = constraints\",\n",
        "\"precedence constraint\" : \"one task must occur before another\",\n",
        "\"disjunctive constraint\" : \"x or y must occur\",\n",
        "\"preference constraint\" : \"soft constraint that is nice if it could occur but not necessary\",\n",
        "\"unary constraint\" : \"restricts the value of only one variable\",\n",
        "\"binary constraint\" : \"constraint on two variables\",\n",
        "\"binary CSP\" : \"onl has unary and binary constraints\",\n",
        "\"global constraint\": \"constraint with any number of variables\",\n",
        "\"constraint hypergraph\" : \"ordinary nodes and hypernodes for n-ary constraints\",\n",
        "\"constraint propagation\" : \"eliminate inconsistent values for current nodes and neighbors\",\n",
        "\"local consistency\" : \"eliminate inconsistent values of a variable\",\n",
        "\"node-consistent\" : \"if all the variable's possible values satisfies its unary constraints\",\n",
        "\"arc consistent\" : \"if all the variable's possible values satisfies its binary constraints\",\n",
        "\"path consistency\" : \"the variables in the middle are consistent with the binary variable assignment\",\n",
        "\"k-consistency\" : \"given consisistent assignments for a set of k-1 variables, the k-th variable can be assigned consistently\",\n",
        "\"strongly k-consistent\" : \"CSP that is k-consistent, k-1 consistent,...,1-consistent\",\n",
        "\"minimum-remaining-values (MRV) heuristic\" : \"choose the variable with fewest remaining possible values to explore\",\n",
        "\"degree heuristic\" : \"reduce branching factor by exploring variable with most constraints on unassigned variables\",\n",
        "\"least-constraining-value heuristic\" : \"chooses value that eliminates the least choices for neighboring variabels\",\n",
        "\"forward checking\" : \"algorithm that establishes arc consistency for a variable X whenever it is assigned\",\n",
        "\"chronological backtracking\" : \"backtrack to most recent decision\",\n",
        "\"conflict set\" : \"set of assignments that conflict with some value of the impossible variable\",\n",
        "\"backjumping\" : \"backtracks to the most recent assignment in the conflict set\",\n",
        "\"constraint learning\" : \"find the minimum set of variables from the conflict set that causes a failure\",\n",
        "\"no-good\" : \"the minimum set of variables from constraint learning and their values\",\n",
        "\"min-conflicts heuristic\" : \"change the value of the local area to one that yields the min number of conflicts with other variables\",\n",
        "\"tabu search\" : \"maintaining a list of recently visited states and prohibiting algorithm to return to them\",\n",
        "\"constraint weighting\" : \"focus search on the important constraints\",\n",
        "\"independent subproblems\" : \"solutions for these don't affect each other\",\n",
        "\"connected components\" : \"self explanatory\",\n",
        "\"directional arc consistency (DAC)\" : \"for an ordering of variables, the current variable is arc-consistent with every higher order variables\",\n",
        "\"cutset conditioning\" : \"cut CSP into a tree to solve it faster\",\n",
        "\"cycle subset\" : \"a subset of the CSPs variables st removing them turns the remaining variables into a tree\",\n",
        "\"tree decomposition\" : \"turn CSP into tree by making each node a set of variables\",\n",
        "\"tree width\" : \"the size of the largest node in a tree decomposition minus 1, min width across all decompositions\",\n",
        "\"value symmetry\" : \"variables need to be different but there are many different assignments that satisfy this\",\n",
        "\"symmetry-breaking constraint\" : \"added constraint that forces only a subset of those solutions to be valid (ie ordering)\"\n",
        "}\n"
      ],
      "execution_count": 124,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a1e50bff-dabb-409a-f45c-b38d3cead0ef"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 125,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- X is set of variables {X_1,...,X_n}\n- D is set of domains {D_1,...,D_n} \n- C is set of constraints st C_j is <scope, rel>\n   - scope is the variables that are part of the constraint\n   - rel is the values the variables can take on\n- CSPs are NP-complete in general but there are faster subproblems\n- simplest CSPs have variables that have discrete and finite domains\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- CSP algorithm can generate successors by either choosing a new variable assignment or making inference\n/n\nAC-3: has queue of arcs to consider\n- Initially: queue has all arcs in CSP\n- Pops off an aribtrary arc (X_i,X_j) and makes X_i arc-consistent wrt X_j\n- If D_i becomes smaller, add all arcs (X_k, X_i) where X_k is a neighbor of X_i and not X_j\n- If D_i is now empty, return failure\n- If D_i is not empty, repeat the above\n- Return result once queue is empty\n\n- AC-3 runtime is O(cd^3) where c = # of binary constraints and d = max domain\n   - Checking arc consistency takes O(d^2) and each constraint c can be added in the queue d^2 times\n\nPath consistency:\n- Need path consistency to solve map coloring problems (stronger than arc consistency)\n- {X_i,X_j} are path consistent wrt X_m if each consistent assignment , there is also an assignment to X_m that satisfies constraints of {X_i,X_m} and {X_m,X_j}\n\nK-conistency:\n- k=1: given the empty set, we can make any set of one variable consistent (node consistency)\n- k=2: arc consistency\n- k=3: path consistency\n- k-consistency is to induction as strong k-consistency is to strong induction\n- strongly n-consistent: takes O(n^2*d) time and exponential space\n\nGlobal constraints\n- In Alldiff, if m variables are involved in the constraint with n possible distinct values st m>n, then no solution\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktracking search:\n  - Repeatedly choose unassigned variable.\n  - Extend the solution into each of the variable's possible values\n  - If solved, return solution. Else if fails, go back to previous state.\n  - If no value works, return failure.\n- Backtracking search keeps only one representation of a state/assignment instead of creating new ones\n- Can improve by using domain-independent heuristics, unlike uninformed search\nVariable and value ordering:\n- Choose the variable with the fewest legal values (MRV)\n- Choose variable that affects the most unassigned variables (degree) as a tiebreaker \n- Choose the value to try per the least-constraining-value heuristic\nInterleaving search and inference:\n- AC-3 is pure inference\n- Forward checking algorithm\n   - Assign variable X\n   - Establish arc consistency for X\n      - for each unassigned variable Y neighboring X, delete values from domain inconsistent with the assignment of X\n      - backtrack if failure reported\n- Best to combine MRV heuristic with forward checking\n- Forward checking only looks one variable ahead\n- Maintaining Arc Consistency (MAC) algorithm\n   - Assign variable X_i\n   - Run AC-3 with the queue initialized as the arcs (X_j,X_i) for all unnassigned neighbors X_j of X_i\n   - backtrack if failure reported\n- MAC recursively propagates constraints when changes are made to the domains of variables, unlike forward checking\nIntelligent backtracking:\n- Backtracking search algorithms use chronological backtracking\n- Intelligent backtracking backtracks to variable that might fix the problem\n- Keep track of the conflict set (see glossary) for the value of the domain that made the search impossible\n- Then backjumps (see glossary) \n- Backjumping method is implemented by modifying backtrack to accumulate the conflict set while checking for a legal value to assign\n- The conflict set is naturally provided by forward checking\n   - If X=x deletes value from Y's domain, add x to Y's conflict set\n- Forward checking or stronger (like MAC) means you already eliminate all possible backjump paths (so don't need to backjump ever)\n- Something called conflict-directed backjumping but I doubt it will be on test\nConstraint learning:\n- avoid again running into issues that led us to failure\n- Use constraint learnings to get the no-good set\n- Add a new constraint that forbids this combination of no-good assignments\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- Local search algorithms for CSPs can be useful\n- Ex. for each column on a board, move the piece to the square that yields the least number of constraints (min-conflicts heuristic)\n- Runtime of min-conflicts is about independent of problem size\n- Other techniques\n  - Plateu search: allows sideways moves to another state with the same score\n  - Tabu search\n  - Constraint weighting\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- A constraint graph is a tree when any 2 variables are connected by only one path\n- Any tree-structured CSP can be solved in linear time wrt the # of variables!!!\n- New notion of consistency: directional arc consistency (DAC)\n- Tree CSP Solver algorithm\n  1. topologically sorting it st DAC is maintained - O(nd^2) time\n  2. choose variables from start of list to end\n- Two ways to reduce constraint graph to tree: removing nodes or collapsing nodes together\n1. Cutset conditioning:\n- Assign values to some variables so the unassigned variables form a tree\n- Then solve through the above method\n- Works for binary CSPs\n- Algorithm\n   1. Choose the cycle subset S (see glossary)\n   2. For each possible assignment to the variables in the cycle subset S st all constraints on S are satisfied:\n      - Remove newly-inconsistent values from the remaining unassigned values\n      - If remaining CSP has a solution, return that solution and the assignment for S\n- O(d^c * (n-c)d^2) for cycle cutset size c\n   - d^c combinations for values in S, (n-c) remaining variables, and d^2 checks for each\n2. Tree decomposition:\n- Transform CSP into tree st each node is now a set of variables\n- 3 requirements\n   a. Every variable in original problem appears in at least one tree node\n   b. If two variables are connected by a constraint, they must appear together (along with constraint) in at least one tree node\n   c. If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes\n      - the variable must be the same across all nodes in the tree\n- Can use the TreeCSPSolver algorithm in O(nd^2) time, where n = # tree nodes and d = largest domain size (set of tuples of values)\n- Goal: make subproblems as small as possible (minimize tree width)\n- Solve problem in O(nd^{w+1}) time for w=tree width\n- CSPs with constraint graphs of bounded tree width are solvable in polytime!!!\n- Finding min tree width is NP-hard but there are heuristics\n- Tree decomposition is usually faster than cutset conditioning, but it takes exponential in w memory while cutset takes linear memory\nValue symmetry:\n- If 3 variables need to all be different values and there are d values each can be, there are d! ways to assign the values\n- This is value symmetry\n- Reduce the search space by introducing a symmetry-breaking constraint so only 1 of the d! solutions are possible\n\n\n## Module 6 Lecture Notes\n\n- CSPs are good for identification (find goal, don't care about path)\n- CSPs automatically prune all branches that violate a constraint\n- If discrete variables wit hfinite domains, then there are O(d^n) complete assignments where d is domain size\n- AC-3 is O(Nd^3) for planar graphs since # of arcs is linear in the number of nodes\n\n\n## Module 6 Definitions\n* **Csp** - a problem where each variable has a value that satsifies all its constraints\n* **Consistent assignment** - assignment that is valid (doesn't violate constraints)\n* **Complete assignment** - every variable has a value\n* **Solution** - complete and consistent assignment\n* **Constraint graph** - nodes = variables, edges = constraints\n* **Precedence constraint** - one task must occur before another\n* **Disjunctive constraint** - x or y must occur\n* **Preference constraint** - soft constraint that is nice if it could occur but not necessary\n* **Unary constraint** - restricts the value of only one variable\n* **Binary constraint** - constraint on two variables\n* **Binary csp** - onl has unary and binary constraints\n* **Global constraint** - constraint with any number of variables\n* **Constraint hypergraph** - ordinary nodes and hypernodes for n-ary constraints\n* **Constraint propagation** - eliminate inconsistent values for current nodes and neighbors\n* **Local consistency** - eliminate inconsistent values of a variable\n* **Node-consistent** - if all the variable's possible values satisfies its unary constraints\n* **Arc consistent** - if all the variable's possible values satisfies its binary constraints\n* **Path consistency** - the variables in the middle are consistent with the binary variable assignment\n* **K-consistency** - given consisistent assignments for a set of k-1 variables, the k-th variable can be assigned consistently\n* **Strongly k-consistent** - CSP that is k-consistent, k-1 consistent,...,1-consistent\n* **Minimum-remaining-values (mrv) heuristic** - choose the variable with fewest remaining possible values to explore\n* **Degree heuristic** - reduce branching factor by exploring variable with most constraints on unassigned variables\n* **Least-constraining-value heuristic** - chooses value that eliminates the least choices for neighboring variabels\n* **Forward checking** - algorithm that establishes arc consistency for a variable X whenever it is assigned\n* **Chronological backtracking** - backtrack to most recent decision\n* **Conflict set** - set of assignments that conflict with some value of the impossible variable\n* **Backjumping** - backtracks to the most recent assignment in the conflict set\n* **Constraint learning** - find the minimum set of variables from the conflict set that causes a failure\n* **No-good** - the minimum set of variables from constraint learning and their values\n* **Min-conflicts heuristic** - change the value of the local area to one that yields the min number of conflicts with other variables\n* **Tabu search** - maintaining a list of recently visited states and prohibiting algorithm to return to them\n* **Constraint weighting** - focus search on the important constraints\n* **Independent subproblems** - solutions for these don't affect each other\n* **Connected components** - self explanatory\n* **Directional arc consistency (dac)** - for an ordering of variables, the current variable is arc-consistent with every higher order variables\n* **Cutset conditioning** - cut CSP into a tree to solve it faster\n* **Cycle subset** - a subset of the CSPs variables st removing them turns the remaining variables into a tree\n* **Tree decomposition** - turn CSP into tree by making each node a set of variables\n* **Tree width** - the size of the largest node in a tree decomposition minus 1, min width across all decompositions\n* **Value symmetry** - variables need to be different but there are many different assignments that satisfy this\n* **Symmetry-breaking constraint** - added constraint that forces only a subset of those solutions to be valid (ie ordering)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "- KBA algorithm\n",
        "   - given background knowledge base\n",
        "   - with new percept, add sentences to KB\n",
        "   - get optimal action to take from KB\n",
        "   - tell agent actuators what to do\n",
        "   - return action\n",
        "   \"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "- Think Wampus World\n",
        "- Remember task environment PEAS\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "- Logic's symantics defines the truth of each sentecne wrt each possible world\n",
        "- If a sentence alpha is true in model m, m satisfies or is a model of alpha\n",
        "- alpha logically entails beta iff M(alpha) is a subset of M(beta)\n",
        "- want inference algorithms to be sound-preserving and complete\n",
        "- If KB is true in real world, then any sentence alpha derived from KB by sound inference is also true\n",
        "\"\"\"\n",
        "chapter7_4 = r\"\"\"\n",
        "- Conjunction is and $\\wedge$\n",
        "- Disjunction is or $\\vee$\n",
        "- Inference procedure: build new sentences from existing KB until we have the info needed\n",
        "\"\"\"\n",
        "chapter7_5 = r\"\"\"\n",
        "- See paper for logical equivalence and inference rules\n",
        "- Deduction theorem: $\\alpha \\models \\beta$ iff $\\alpha \\Rightarrow \\beta$ is valid\n",
        "- Satisfiability problem (SAT) is NP-complete\n",
        "- $\\alpha$ is valid iff $\\neg alpha$ is unsatisfiable\n",
        "- $\\alpha \\models \\beta$ iff $(\\alpha \\wedge \\neg \\beta )$ is unsatisfiable\n",
        "Inference and proofs:\n",
        "- Can use search algorithms to find a sequence of steps to constitute a proof:\n",
        "   - Initial state: initial KB\n",
        "   - Actions: all the relevant inference rules that can be applied to sentences\n",
        "   - Result: add the bottom half of the inference rule to the KB\n",
        "   - Goal: get to the state we are trying to prove\n",
        "- Searching for proofs is alternative to enumerating models\n",
        "- In most cases, finding a proof can be more efficient because hte proof can ignore irrelevant propositions, irregardless of their number\n",
        "- Monotonicity means sentences from inference rules do not invalidate previous info\n",
        "Proof by resolution\n",
        "- Resolution lets you get complete inference algorithm with a complete search algorithm\n",
        "- Resolution rule only lets you remove one literal at a time\n",
        "- The bottom half of the resolution rule must not have any duplicates (called factoring)\n",
        "- Every sentence of propositional logic is logically equivalent to a conjunction of clauses\n",
        "- CNF procedure:\n",
        "   1. Biconditional elimination\n",
        "   2. Implication elimination\n",
        "   3. Move negations inwards threw double-negation elimination and De Morgan\n",
        "   4. Distribute V over $\\wedge$\n",
        "- Use proof by contradiction to show $KB \\models \\alpha$\n",
        "   - Show $KB \\wedge \\neg \\alpha$ is unsatisfiable by assuming it is satisfiable.\n",
        "- Resolution algorithm:\n",
        "   1. Convert $KB \\models \\neg \\alpha$ to CNF\n",
        "   2. Apply resolution rule to resulting clauses\n",
        "   3. Resolve every pair that contains complementary literals to produce a new clause\n",
        "      - Note that a pair can result in more than one new clause\n",
        "   4. If the new clause isn't present, add it to the set\n",
        "   5. Continue until either\n",
        "      - No new clauses are added (KB doesn't entail $\\alpha$ since no contradiction)\n",
        "      - Two clauses resolve to yield the empty clause (contradiction) so KB entails $\\alpha$\n",
        "   - Note you can disregard any clause with two complementary literals\n",
        "- The resolution closure is finite because the factoring step means only a finite number of new clauses can be created\n",
        "   - So resolution algorithm always terminates\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = r\"\"\"\n",
        "Horn clauses and definite clauses:\n",
        "- All definite and goal clauses are Horn clauses (see glossary)\n",
        "- Resolving a Horn clause yields a Horn clause\n",
        "- KBs with only definite clauses are interesting:\n",
        "   1. Every definite clause can be written as (conjunction of positive literals) $\\Rightarrow$ negative literal\n",
        "   2. Inference with Horn clauses can be done through forward- and backward-chaining algorithms/n\n",
        "   3. Deciding entailment with Horn clauses can be done in time linear wrt KB size\n",
        "Forward and backward chaining:\n",
        "- Forward chaining\n",
        "   - Starts with KB and makes inferences to grow KB until target query is found, else returns false/n\n",
        "   - Linear time\n",
        "   - Data-driven reasoning\n",
        "- Backward chaining\n",
        "   - Starts with possibly true query and works backwards until LHS of implication can be proven true\n",
        "   - Linear time but usually faster than forward chaining\n",
        "   - Goal-directed reasoning\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"what the agent knows\",\n",
        "\"sentence\" : \"a fact\",\n",
        "\"knoweldge representation language\" : \"representing knowledge in specific language\",\n",
        "\"axiom\" : \"a sentence given by the problem\",\n",
        "\"declarative\" : \"add sentences to KB one-by-one until agent knows how to work in environment\",\n",
        "\"procedural\" : \"good behaviors are encoded into the program\",\n",
        "\"possible world\" : \"possibility that could be true given current knowledge base\",\n",
        "\"model\" : \"the mathematical abstraction of a possible world\",\n",
        "\"logical inference\" : \"use entailment to get conclusions\",\n",
        "\"model checking\" : \"check M(KB) is a subset of M(alpha)\",\n",
        "\"sound- or truth-preserving\" : \"inference algorithm that only ouputs entailed sentences\",\n",
        "\"completeness\" : \"property of inference algorithm to derive all entailed sentences\",\n",
        "\"theorem proving\" : \"using inference logic on KB to create proof of target sentence\",\n",
        "\"logical equivalence\" : \"sentences are logically equivalent if true exclusively in the same models\",\n",
        "\"satisfiability\" : \"can assign values (model) st sentence is true\",\n",
        "\"monotonicity\" : \"the set of entailed sentences only increases as KB grows\",\n",
        "\"resolution\" : \"the one inference rule needed to yield a complete inference algorithm when paired with complete search algorithm\",\n",
        "\"CNF\" : \"sentence that is a conjunction of clauses which are disjunctions of literals\",\n",
        "\"resolution closure\" : \"the set of clauses at the end of the resolution algorithm\",\n",
        "\"ground resolution theoren\" : \"unsatisfiable set of clauses will result in an empty set resolution closure\",\n",
        "\"definite clause\" : \"disjunction of literals with only one positive\",\n",
        "\"horn clause\" : \"disjunction of literals with at most one positive\",\n",
        "\"goal clause\" : \"disjunction of literals with no positive\",\n",
        "\"body\" : \"LHS of special definite clause implication (conjunction of positive literals)\",\n",
        "\"head\" : \"RHS of special definite clause implication (one negative literal)\",\n",
        "\"fact\" : \"single positive literal\",\n",
        "\"data-driven\" : \"starts with known data, adds premises as percepts come in, and makes conclusions using them\",\n",
        "\"goal-directed\" : \"good for answering questions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 126,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c6ae35a0-64a9-4c39-fbd1-d4e5236a7287"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 127,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n- KBA algorithm\n   - given background knowledge base\n   - with new percept, add sentences to KB\n   - get optimal action to take from KB\n   - tell agent actuators what to do\n   - return action\n   \n\n## AIMA Chapter 7.2 The Wumpus World\n\n- Think Wampus World\n- Remember task environment PEAS\n\n\n## AIMA Chapter 7.3 Logic\n\n- Logic's symantics defines the truth of each sentecne wrt each possible world\n- If a sentence alpha is true in model m, m satisfies or is a model of alpha\n- alpha logically entails beta iff M(alpha) is a subset of M(beta)\n- want inference algorithms to be sound-preserving and complete\n- If KB is true in real world, then any sentence alpha derived from KB by sound inference is also true\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- Conjunction is and $\\wedge$\n- Disjunction is or $\\vee$\n- Inference procedure: build new sentences from existing KB until we have the info needed\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- See paper for logical equivalence and inference rules\n- Deduction theorem: $\\alpha \\models \\beta$ iff $\\alpha \\Rightarrow \\beta$ is valid\n- Satisfiability problem (SAT) is NP-complete\n- $\\alpha$ is valid iff $\\neg alpha$ is unsatisfiable\n- $\\alpha \\models \\beta$ iff $(\\alpha \\wedge \\neg \\beta )$ is unsatisfiable\nInference and proofs:\n- Can use search algorithms to find a sequence of steps to constitute a proof:\n   - Initial state: initial KB\n   - Actions: all the relevant inference rules that can be applied to sentences\n   - Result: add the bottom half of the inference rule to the KB\n   - Goal: get to the state we are trying to prove\n- Searching for proofs is alternative to enumerating models\n- In most cases, finding a proof can be more efficient because hte proof can ignore irrelevant propositions, irregardless of their number\n- Monotonicity means sentences from inference rules do not invalidate previous info\nProof by resolution\n- Resolution lets you get complete inference algorithm with a complete search algorithm\n- Resolution rule only lets you remove one literal at a time\n- The bottom half of the resolution rule must not have any duplicates (called factoring)\n- Every sentence of propositional logic is logically equivalent to a conjunction of clauses\n- CNF procedure:\n   1. Biconditional elimination\n   2. Implication elimination\n   3. Move negations inwards threw double-negation elimination and De Morgan\n   4. Distribute V over $\\wedge$\n- Use proof by contradiction to show $KB \\models \\alpha$\n   - Show $KB \\wedge \\neg \\alpha$ is unsatisfiable by assuming it is satisfiable.\n- Resolution algorithm:\n   1. Convert $KB \\models \\neg \\alpha$ to CNF\n   2. Apply resolution rule to resulting clauses\n   3. Resolve every pair that contains complementary literals to produce a new clause\n      - Note that a pair can result in more than one new clause\n   4. If the new clause isn't present, add it to the set\n   5. Continue until either\n      - No new clauses are added (KB doesn't entail $\\alpha$ since no contradiction)\n      - Two clauses resolve to yield the empty clause (contradiction) so KB entails $\\alpha$\n   - Note you can disregard any clause with two complementary literals\n- The resolution closure is finite because the factoring step means only a finite number of new clauses can be created\n   - So resolution algorithm always terminates\n\n\n## Module 7 Lecture Notes\n\nHorn clauses and definite clauses:\n- All definite and goal clauses are Horn clauses (see glossary)\n- Resolving a Horn clause yields a Horn clause\n- KBs with only definite clauses are interesting:\n   1. Every definite clause can be written as (conjunction of positive literals) $\\Rightarrow$ negative literal\n   2. Inference with Horn clauses can be done through forward- and backward-chaining algorithms/n\n   3. Deciding entailment with Horn clauses can be done in time linear wrt KB size\nForward and backward chaining:\n- Forward chaining\n   - Starts with KB and makes inferences to grow KB until target query is found, else returns false/n\n   - Linear time\n   - Data-driven reasoning\n- Backward chaining\n   - Starts with possibly true query and works backwards until LHS of implication can be proven true\n   - Linear time but usually faster than forward chaining\n   - Goal-directed reasoning\n\n\n## Module 7 Definitions\n* **Knowledge base** - what the agent knows\n* **Sentence** - a fact\n* **Knoweldge representation language** - representing knowledge in specific language\n* **Axiom** - a sentence given by the problem\n* **Declarative** - add sentences to KB one-by-one until agent knows how to work in environment\n* **Procedural** - good behaviors are encoded into the program\n* **Possible world** - possibility that could be true given current knowledge base\n* **Model** - the mathematical abstraction of a possible world\n* **Logical inference** - use entailment to get conclusions\n* **Model checking** - check M(KB) is a subset of M(alpha)\n* **Sound- or truth-preserving** - inference algorithm that only ouputs entailed sentences\n* **Completeness** - property of inference algorithm to derive all entailed sentences\n* **Theorem proving** - using inference logic on KB to create proof of target sentence\n* **Logical equivalence** - sentences are logically equivalent if true exclusively in the same models\n* **Satisfiability** - can assign values (model) st sentence is true\n* **Monotonicity** - the set of entailed sentences only increases as KB grows\n* **Resolution** - the one inference rule needed to yield a complete inference algorithm when paired with complete search algorithm\n* **Cnf** - sentence that is a conjunction of clauses which are disjunctions of literals\n* **Resolution closure** - the set of clauses at the end of the resolution algorithm\n* **Ground resolution theoren** - unsatisfiable set of clauses will result in an empty set resolution closure\n* **Definite clause** - disjunction of literals with only one positive\n* **Horn clause** - disjunction of literals with at most one positive\n* **Goal clause** - disjunction of literals with no positive\n* **Body** - LHS of special definite clause implication (conjunction of positive literals)\n* **Head** - RHS of special definite clause implication (one negative literal)\n* **Fact** - single positive literal\n* **Data-driven** - starts with known data, adds premises as percepts come in, and makes conclusions using them\n* **Goal-directed** - good for answering questions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "b4fe83d6-07cb-4dfa-94de-b781f9709bda"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 128,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n- Aristotle was first to explore rationality. \n- Rene Descartes: I think therefore I am. \n- David Hume: induction\n  \n\n## AIMA Chapter 27.1 The Limits of AI\n\n- Searle: weak AI (act as if intelligent) vs strong AI (actually inteligent)\n- Turing and Hubert Dreyfus believe human behavior is too complex to be captured by formal set of rules.\n- Embodied cognitition: must study brain and body together\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n- Searle: biological naturalism\n- Can machines have consiousness?\n\n\n## AIMA 2.1 Agents and Environments\n \n- Agent acts only on things it has perceived in past, nothing it hasn't perceived. \n- Agent's behavior is described by the agent function \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n- A rational agent selects an action to maximize its performance measure given its percept sequence and any other built-in knowledge\n\n\n## AIMA 2.3 The Nature of Environments\n\n- First define task environment per PEAS \n- Fully observable vs partially observable (or unobservable if no sensors) \n- Single-agent vs multiagent \n- Deterministic vs nondeterministic \n     - Stochastic if probabilities, nondeterministic if possibilities aren't listed with probabilities \n- Epsisodic vs sequential (independent tasks vs dependent tasks) \n- Static vs dynamic (semidynamic if environment doesn't change but performance score does ie chess) \n- Discrete vs continuous (time and state) \n- Known vs unknown (outcomes are given for all actions) \n     - A game can be fully observable but unknown if you see everything but don't know how to play it \n- Hardest: partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, unknown\n\n\n## AIMA 2.4 The Structure of Agents\n\n- agent = architecture + program\n- table-driven agent: rational but impractical due to size\n- simple reflex agent: works on current percept only\n- randomization can help escape loops\n- model-based agent: maintains internal state that depends on the percept history and reflects some unobserved stuff of current state\n     - transition model and sensor model\n     - ex: autonomous car\n- goal-based agent: search and planning\n- utility-based agent: maximize utility\n- learning agent: uses feedback from a critic to determine how to act in the future\n\n\n## Module 1 Lecture Notes\n\nAI Philosophy \n- Rene Descartes: I think therefore I am (dualism) \n- 17th and 18th century automatons (test intelligence with language)\n- Turing: Can machines think to the point humans cant tell the difference\n- John Searle: The Chinese Room\n     - Turing Test can be completed with just symbol manipulation\n     - Brains cause minds and computers can't have minds\n- Daniel Dennett: Brain in a vat (no difference between brain and processor)\n\nAgents\n- Easiest task environment: static, fully observable, deterministic, discrete\n- Reflex agents only act based on current percept (Roomba)\n- Problem solving agents work ahead (puzzle)\n\n\n## Module 1 Definitions\n* **Turing test** - Do people consider a machine human in language?\n* **Agent** - anything that can perceive through sensors and act through actuators in an environment\n* **Rational agent** - agent that acts to achieve the best (expected) outcome\n* **Dualism** - mind is separate from body\n* **Materialism** - the mind is the brain operating per the laws of physics\n* **Percept** - what the agent's sensors perceive\n* **Percept sequence** - complete history of all the agent has ever perceived\n* **Agent function** - maps a percept sequence to an action\n* **Agent program** - the concrete implementation of the agent function\n* **Performance measure** - how good of a state the agent is in\n* **Task environment** - the problems agents solve\n* **Peas** - Performance measure, Environment, Actuators, Sensors\n* **Actuator** - how the agent performs an action\n* **Agent architecture** - physical part of agent\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n- print(\"%s can speak %d languages\" % (\"C3PO\",6000))\n- referential equality: is\n- Shallow copy: x[:]\n- Slicing is zero indexed and [1:-1:2] gets the every other from the first index to second to last index\n- li.sort() is in place, sorted(li) is a copy\n- defaultdict automatically initializes nonexistent dictionary values\n- Counters are defaultdicts for counting keys\n- No function overloading\n- *args: accept a variable # of non-keyword arguments \n- **kwargs: accept a variable # of keywork arguments \n- Can put a dictionary as a function parameter to make it updateable \n- Duck typing\n- Dictionary comprehension: {k:v for k,v in li}\n- Set comprehension: {x for x in li}\n- Generators use yield, pause, and resume again when called next \n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n\n- States\n\n- Initial state\n\n- Actions\n\n- Transition model\n\n- Goal state\n\n- Action cost\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n\n- Use minimax for perfect info, zero-sum games\n\n- Game elements:\n\n   - initial state\n\n   - terminal states\n\n   - whose turn it is\n\n   - set of legal moves\n\n   - transition model\n\n   - utility function\n\n- Minimax is DFS\n\n- Time complexity: O(b^m)\n\n- Space complexity: O(bm) if all actions at once, O(m) if one action at a time (generator)\n\nExpectimax:\n\n- Time complexity: O(b^m * n^m) where n is number of distinct dice rolls\n\n- Partially observable\n\n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n- X is set of variables {X_1,...,X_n}\n- D is set of domains {D_1,...,D_n} \n- C is set of constraints st C_j is <scope, rel>\n   - scope is the variables that are part of the constraint\n   - rel is the values the variables can take on\n- CSPs are NP-complete in general but there are faster subproblems\n- simplest CSPs have variables that have discrete and finite domains\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- CSP algorithm can generate successors by either choosing a new variable assignment or making inference\n/n\nAC-3: has queue of arcs to consider\n- Initially: queue has all arcs in CSP\n- Pops off an aribtrary arc (X_i,X_j) and makes X_i arc-consistent wrt X_j\n- If D_i becomes smaller, add all arcs (X_k, X_i) where X_k is a neighbor of X_i and not X_j\n- If D_i is now empty, return failure\n- If D_i is not empty, repeat the above\n- Return result once queue is empty\n\n- AC-3 runtime is O(cd^3) where c = # of binary constraints and d = max domain\n   - Checking arc consistency takes O(d^2) and each constraint c can be added in the queue d^2 times\n\nPath consistency:\n- Need path consistency to solve map coloring problems (stronger than arc consistency)\n- {X_i,X_j} are path consistent wrt X_m if each consistent assignment , there is also an assignment to X_m that satisfies constraints of {X_i,X_m} and {X_m,X_j}\n\nK-conistency:\n- k=1: given the empty set, we can make any set of one variable consistent (node consistency)\n- k=2: arc consistency\n- k=3: path consistency\n- k-consistency is to induction as strong k-consistency is to strong induction\n- strongly n-consistent: takes O(n^2*d) time and exponential space\n\nGlobal constraints\n- In Alldiff, if m variables are involved in the constraint with n possible distinct values st m>n, then no solution\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktracking search:\n  - Repeatedly choose unassigned variable.\n  - Extend the solution into each of the variable's possible values\n  - If solved, return solution. Else if fails, go back to previous state.\n  - If no value works, return failure.\n- Backtracking search keeps only one representation of a state/assignment instead of creating new ones\n- Can improve by using domain-independent heuristics, unlike uninformed search\nVariable and value ordering:\n- Choose the variable with the fewest legal values (MRV)\n- Choose variable that affects the most unassigned variables (degree) as a tiebreaker \n- Choose the value to try per the least-constraining-value heuristic\nInterleaving search and inference:\n- AC-3 is pure inference\n- Forward checking algorithm\n   - Assign variable X\n   - Establish arc consistency for X\n      - for each unassigned variable Y neighboring X, delete values from domain inconsistent with the assignment of X\n      - backtrack if failure reported\n- Best to combine MRV heuristic with forward checking\n- Forward checking only looks one variable ahead\n- Maintaining Arc Consistency (MAC) algorithm\n   - Assign variable X_i\n   - Run AC-3 with the queue initialized as the arcs (X_j,X_i) for all unnassigned neighbors X_j of X_i\n   - backtrack if failure reported\n- MAC recursively propagates constraints when changes are made to the domains of variables, unlike forward checking\nIntelligent backtracking:\n- Backtracking search algorithms use chronological backtracking\n- Intelligent backtracking backtracks to variable that might fix the problem\n- Keep track of the conflict set (see glossary) for the value of the domain that made the search impossible\n- Then backjumps (see glossary) \n- Backjumping method is implemented by modifying backtrack to accumulate the conflict set while checking for a legal value to assign\n- The conflict set is naturally provided by forward checking\n   - If X=x deletes value from Y's domain, add x to Y's conflict set\n- Forward checking or stronger (like MAC) means you already eliminate all possible backjump paths (so don't need to backjump ever)\n- Something called conflict-directed backjumping but I doubt it will be on test\nConstraint learning:\n- avoid again running into issues that led us to failure\n- Use constraint learnings to get the no-good set\n- Add a new constraint that forbids this combination of no-good assignments\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n- Local search algorithms for CSPs can be useful\n- Ex. for each column on a board, move the piece to the square that yields the least number of constraints (min-conflicts heuristic)\n- Runtime of min-conflicts is about independent of problem size\n- Other techniques\n  - Plateu search: allows sideways moves to another state with the same score\n  - Tabu search\n  - Constraint weighting\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n- A constraint graph is a tree when any 2 variables are connected by only one path\n- Any tree-structured CSP can be solved in linear time wrt the # of variables!!!\n- New notion of consistency: directional arc consistency (DAC)\n- Tree CSP Solver algorithm\n  1. topologically sorting it st DAC is maintained - O(nd^2) time\n  2. choose variables from start of list to end\n- Two ways to reduce constraint graph to tree: removing nodes or collapsing nodes together\n1. Cutset conditioning:\n- Assign values to some variables so the unassigned variables form a tree\n- Then solve through the above method\n- Works for binary CSPs\n- Algorithm\n   1. Choose the cycle subset S (see glossary)\n   2. For each possible assignment to the variables in the cycle subset S st all constraints on S are satisfied:\n      - Remove newly-inconsistent values from the remaining unassigned values\n      - If remaining CSP has a solution, return that solution and the assignment for S\n- O(d^c * (n-c)d^2) for cycle cutset size c\n   - d^c combinations for values in S, (n-c) remaining variables, and d^2 checks for each\n2. Tree decomposition:\n- Transform CSP into tree st each node is now a set of variables\n- 3 requirements\n   a. Every variable in original problem appears in at least one tree node\n   b. If two variables are connected by a constraint, they must appear together (along with constraint) in at least one tree node\n   c. If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes\n      - the variable must be the same across all nodes in the tree\n- Can use the TreeCSPSolver algorithm in O(nd^2) time, where n = # tree nodes and d = largest domain size (set of tuples of values)\n- Goal: make subproblems as small as possible (minimize tree width)\n- Solve problem in O(nd^{w+1}) time for w=tree width\n- CSPs with constraint graphs of bounded tree width are solvable in polytime!!!\n- Finding min tree width is NP-hard but there are heuristics\n- Tree decomposition is usually faster than cutset conditioning, but it takes exponential in w memory while cutset takes linear memory\nValue symmetry:\n- If 3 variables need to all be different values and there are d values each can be, there are d! ways to assign the values\n- This is value symmetry\n- Reduce the search space by introducing a symmetry-breaking constraint so only 1 of the d! solutions are possible\n\n\n## Module 6 Lecture Notes\n\n- CSPs are good for identification (find goal, don't care about path)\n- CSPs automatically prune all branches that violate a constraint\n- If discrete variables wit hfinite domains, then there are O(d^n) complete assignments where d is domain size\n- AC-3 is O(Nd^3) for planar graphs since # of arcs is linear in the number of nodes\n\n\n## Module 6 Definitions\n* **Csp** - a problem where each variable has a value that satsifies all its constraints\n* **Consistent assignment** - assignment that is valid (doesn't violate constraints)\n* **Complete assignment** - every variable has a value\n* **Solution** - complete and consistent assignment\n* **Constraint graph** - nodes = variables, edges = constraints\n* **Precedence constraint** - one task must occur before another\n* **Disjunctive constraint** - x or y must occur\n* **Preference constraint** - soft constraint that is nice if it could occur but not necessary\n* **Unary constraint** - restricts the value of only one variable\n* **Binary constraint** - constraint on two variables\n* **Binary csp** - onl has unary and binary constraints\n* **Global constraint** - constraint with any number of variables\n* **Constraint hypergraph** - ordinary nodes and hypernodes for n-ary constraints\n* **Constraint propagation** - eliminate inconsistent values for current nodes and neighbors\n* **Local consistency** - eliminate inconsistent values of a variable\n* **Node-consistent** - if all the variable's possible values satisfies its unary constraints\n* **Arc consistent** - if all the variable's possible values satisfies its binary constraints\n* **Path consistency** - the variables in the middle are consistent with the binary variable assignment\n* **K-consistency** - given consisistent assignments for a set of k-1 variables, the k-th variable can be assigned consistently\n* **Strongly k-consistent** - CSP that is k-consistent, k-1 consistent,...,1-consistent\n* **Minimum-remaining-values (mrv) heuristic** - choose the variable with fewest remaining possible values to explore\n* **Degree heuristic** - reduce branching factor by exploring variable with most constraints on unassigned variables\n* **Least-constraining-value heuristic** - chooses value that eliminates the least choices for neighboring variabels\n* **Forward checking** - algorithm that establishes arc consistency for a variable X whenever it is assigned\n* **Chronological backtracking** - backtrack to most recent decision\n* **Conflict set** - set of assignments that conflict with some value of the impossible variable\n* **Backjumping** - backtracks to the most recent assignment in the conflict set\n* **Constraint learning** - find the minimum set of variables from the conflict set that causes a failure\n* **No-good** - the minimum set of variables from constraint learning and their values\n* **Min-conflicts heuristic** - change the value of the local area to one that yields the min number of conflicts with other variables\n* **Tabu search** - maintaining a list of recently visited states and prohibiting algorithm to return to them\n* **Constraint weighting** - focus search on the important constraints\n* **Independent subproblems** - solutions for these don't affect each other\n* **Connected components** - self explanatory\n* **Directional arc consistency (dac)** - for an ordering of variables, the current variable is arc-consistent with every higher order variables\n* **Cutset conditioning** - cut CSP into a tree to solve it faster\n* **Cycle subset** - a subset of the CSPs variables st removing them turns the remaining variables into a tree\n* **Tree decomposition** - turn CSP into tree by making each node a set of variables\n* **Tree width** - the size of the largest node in a tree decomposition minus 1, min width across all decompositions\n* **Value symmetry** - variables need to be different but there are many different assignments that satisfy this\n* **Symmetry-breaking constraint** - added constraint that forces only a subset of those solutions to be valid (ie ordering)\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n- KBA algorithm\n   - given background knowledge base\n   - with new percept, add sentences to KB\n   - get optimal action to take from KB\n   - tell agent actuators what to do\n   - return action\n   \n\n## AIMA Chapter 7.2 The Wumpus World\n\n- Think Wampus World\n- Remember task environment PEAS\n\n\n## AIMA Chapter 7.3 Logic\n\n- Logic's symantics defines the truth of each sentecne wrt each possible world\n- If a sentence alpha is true in model m, m satisfies or is a model of alpha\n- alpha logically entails beta iff M(alpha) is a subset of M(beta)\n- want inference algorithms to be sound-preserving and complete\n- If KB is true in real world, then any sentence alpha derived from KB by sound inference is also true\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n- Conjunction is and $\\wedge$\n- Disjunction is or $\\vee$\n- Inference procedure: build new sentences from existing KB until we have the info needed\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n- See paper for logical equivalence and inference rules\n- Deduction theorem: $\\alpha \\models \\beta$ iff $\\alpha \\Rightarrow \\beta$ is valid\n- Satisfiability problem (SAT) is NP-complete\n- $\\alpha$ is valid iff $\\neg alpha$ is unsatisfiable\n- $\\alpha \\models \\beta$ iff $(\\alpha \\wedge \\neg \\beta )$ is unsatisfiable\nInference and proofs:\n- Can use search algorithms to find a sequence of steps to constitute a proof:\n   - Initial state: initial KB\n   - Actions: all the relevant inference rules that can be applied to sentences\n   - Result: add the bottom half of the inference rule to the KB\n   - Goal: get to the state we are trying to prove\n- Searching for proofs is alternative to enumerating models\n- In most cases, finding a proof can be more efficient because hte proof can ignore irrelevant propositions, irregardless of their number\n- Monotonicity means sentences from inference rules do not invalidate previous info\nProof by resolution\n- Resolution lets you get complete inference algorithm with a complete search algorithm\n- Resolution rule only lets you remove one literal at a time\n- The bottom half of the resolution rule must not have any duplicates (called factoring)\n- Every sentence of propositional logic is logically equivalent to a conjunction of clauses\n- CNF procedure:\n   1. Biconditional elimination\n   2. Implication elimination\n   3. Move negations inwards threw double-negation elimination and De Morgan\n   4. Distribute V over $\\wedge$\n- Use proof by contradiction to show $KB \\models \\alpha$\n   - Show $KB \\wedge \\neg \\alpha$ is unsatisfiable by assuming it is satisfiable.\n- Resolution algorithm:\n   1. Convert $KB \\models \\neg \\alpha$ to CNF\n   2. Apply resolution rule to resulting clauses\n   3. Resolve every pair that contains complementary literals to produce a new clause\n      - Note that a pair can result in more than one new clause\n   4. If the new clause isn't present, add it to the set\n   5. Continue until either\n      - No new clauses are added (KB doesn't entail $\\alpha$ since no contradiction)\n      - Two clauses resolve to yield the empty clause (contradiction) so KB entails $\\alpha$\n   - Note you can disregard any clause with two complementary literals\n- The resolution closure is finite because the factoring step means only a finite number of new clauses can be created\n   - So resolution algorithm always terminates\n\n\n## Module 7 Lecture Notes\n\nHorn clauses and definite clauses:\n- All definite and goal clauses are Horn clauses (see glossary)\n- Resolving a Horn clause yields a Horn clause\n- KBs with only definite clauses are interesting:\n   1. Every definite clause can be written as (conjunction of positive literals) $\\Rightarrow$ negative literal\n   2. Inference with Horn clauses can be done through forward- and backward-chaining algorithms/n\n   3. Deciding entailment with Horn clauses can be done in time linear wrt KB size\nForward and backward chaining:\n- Forward chaining\n   - Starts with KB and makes inferences to grow KB until target query is found, else returns false/n\n   - Linear time\n   - Data-driven reasoning\n- Backward chaining\n   - Starts with possibly true query and works backwards until LHS of implication can be proven true\n   - Linear time but usually faster than forward chaining\n   - Goal-directed reasoning\n\n\n## Module 7 Definitions\n* **Knowledge base** - what the agent knows\n* **Sentence** - a fact\n* **Knoweldge representation language** - representing knowledge in specific language\n* **Axiom** - a sentence given by the problem\n* **Declarative** - add sentences to KB one-by-one until agent knows how to work in environment\n* **Procedural** - good behaviors are encoded into the program\n* **Possible world** - possibility that could be true given current knowledge base\n* **Model** - the mathematical abstraction of a possible world\n* **Logical inference** - use entailment to get conclusions\n* **Model checking** - check M(KB) is a subset of M(alpha)\n* **Sound- or truth-preserving** - inference algorithm that only ouputs entailed sentences\n* **Completeness** - property of inference algorithm to derive all entailed sentences\n* **Theorem proving** - using inference logic on KB to create proof of target sentence\n* **Logical equivalence** - sentences are logically equivalent if true exclusively in the same models\n* **Satisfiability** - can assign values (model) st sentence is true\n* **Monotonicity** - the set of entailed sentences only increases as KB grows\n* **Resolution** - the one inference rule needed to yield a complete inference algorithm when paired with complete search algorithm\n* **Cnf** - sentence that is a conjunction of clauses which are disjunctions of literals\n* **Resolution closure** - the set of clauses at the end of the resolution algorithm\n* **Ground resolution theoren** - unsatisfiable set of clauses will result in an empty set resolution closure\n* **Definite clause** - disjunction of literals with only one positive\n* **Horn clause** - disjunction of literals with at most one positive\n* **Goal clause** - disjunction of literals with no positive\n* **Body** - LHS of special definite clause implication (conjunction of positive literals)\n* **Head** - RHS of special definite clause implication (one negative literal)\n* **Fact** - single positive literal\n* **Data-driven** - starts with known data, adds premises as percepts come in, and makes conclusions using them\n* **Goal-directed** - good for answering questions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}