{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "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 2\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": "29c32833-9c1f-413b-e33d-17829964a86a"
      },
      "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": null,
      "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": "43e3a710-2733-48e6-d796-33fc17e38d32"
      },
      "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": null,
      "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 = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "* Utility function U(s): single number -> desirability of a state\n",
        "* Expected utility EU(a): avg utility value of outcomes weighted by prob outcome occurs\n",
        "* MEU: rational agent should choose the action to maximize EU\n",
        " \"\"\"  + '\\n' + sample_equation\n",
        "chapter16_2 =  \"\"\"\n",
        "* A > B: agent prefers A over B\n",
        "* A ~ B: agent indifferent between A and B\n",
        "* A >~ B: agent prefers A over B | indifferent between A and B\n",
        "* Orderability\n",
        "\t* given two lotteries\n",
        "\t* must either prefer one lottery  or see them as equally preferable\n",
        "\t* only one of (A > B), (B > A), (A ~ B) holds\n",
        "* Transitivity: \n",
        "\t* given three lotteries\n",
        "\t* prefers A to B & B to C -> must prefer A to C\n",
        "\t* (A > B) ∧ (B > C) -> (A > C)\n",
        "* Continuity\n",
        "\t* A > B > C\n",
        "\t* prob. P that agent indifferent between getting\n",
        "\t\t* B for sure\n",
        "\t\t* the lottery that yields A with prob p and C with prob 1 - p\n",
        "* Substitutability\n",
        "\t* agent indifferent between A and B ->\n",
        "\t* agent indifferent between two more complex lotteries\n",
        "\t\t* same but B is substituted for A in one of them\n",
        "\t* regardless of probs and other outcomes\n",
        "* Monotonicity\n",
        "\t* A and B: same two possible outcomes\n",
        "\t* agent prefers A to B -> \n",
        "\t* must prefer lottery with higher prob for A (vice versa)\n",
        "* Decomposability\n",
        "\t* compound lotteries ->\n",
        "\t* reduced to simpler ones (laws of prob)\n",
        "\t* “no fun in gambling”\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "* Framing effect: ppl prefer a medical procedure with \n",
        "  * 90% survival rate >>> 10% death rate\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "* Environment history: a sequence of states and actions\n",
        "* Solutions to MDPs usually involve dynamic programming\n",
        "* Optimal policy yields highest expected utility\n",
        "* Q-function (action-utility function) Q(s, a) -> EU of taking action a at state s\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "* Algorithms\n",
        "\t* value iteration\n",
        "\t* policy iteration\n",
        "\t* linear programming\n",
        "\t* Monte Carlo planning (different solution from previous 3)\n",
        "* Policy iteration\n",
        "\t* policy evaluation\n",
        "\t\t* given policy, calculate utility of each state if policy executed\n",
        "\t* policy improvement\n",
        "\t\t* calculate new MEU policy using one-step look-ahead\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "* p(s’ | s, a): the probability of arriving in state s’ \n",
        "  * even that we are in state s and we selected action a\n",
        "* transitions are Markovian: prob of arriving in s’ only depends on s \n",
        "  * (not history of earlier states)\n",
        "* Rewards can be positive or negative (but bounded by max value) \n",
        "* Rewards are additive\n",
        "* MDP: sequential decision problem + fully observable environment +\n",
        "  * stochastic tradition model + additive rewards\n",
        "* MDPs: non-deterministic search problems\n",
        "* Expectimax search to solve MDPs\n",
        "* To solve an MDP: \n",
        "  * set of states + set of actions + transition function T(s, a, s’) + \n",
        "  * reward function R(s, a, s’) + initial state + terminal states (optional)\n",
        "* Policy π(s) = a; solution to an MDP\n",
        "* We need to compute the expected utility of all possible paths generated by a policy\n",
        "* Discounting: values of rewards decay exponentially\n",
        "* Utility = sum of (discounted) rewards\n",
        "* Value iteration: update values and the policy in each iteration; doesn’t track policy\n",
        "* Policy iteration: update utilities with fixed policy for several passes; \n",
        "  * choose a better new policy or terminate\n",
        "* To compute optimal values: value iteration/policy iteration\n",
        "* To compute values for a particular policy: policy iteration\n",
        "* Turn values into a policy: policy extraction\n",
        "* Maximum expected utility (MEU): a rational event should choose an action \n",
        "  * that maximizes its EU given its knowledge\n",
        "* Axiom of Transitivity: (A > B) ^ (B > C) -> (A > C)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"stochastic\": \"randomly determined\",\n",
        "\"policy\": \"a mapping from a state to an action to take in that state\",\n",
        "\"nonstationary\": \"policy that depends on the time\",\n",
        "\"proper policy\": \"guaranteed to reach a terminal state\",\n",
        "\"max norm\": \"measures length of vector by |value| if its biggest component\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\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
        },
        "outputId": "3e0fc6b1-0bd9-4274-c322-0fadbfb1e0d7"
      },
      "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",
        "module8_sections = [\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",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_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(' ')) > 25):\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",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n* Utility function U(s): single number -> desirability of a state\n* Expected utility EU(a): avg utility value of outcomes weighted by prob outcome occurs\n* MEU: rational agent should choose the action to maximize EU\n \n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n* A > B: agent prefers A over B\n* A ~ B: agent indifferent between A and B\n* A >~ B: agent prefers A over B | indifferent between A and B\n* Orderability\n\t* given two lotteries\n\t* must either prefer one lottery  or see them as equally preferable\n\t* only one of (A > B), (B > A), (A ~ B) holds\n* Transitivity: \n\t* given three lotteries\n\t* prefers A to B & B to C -> must prefer A to C\n\t* (A > B) ∧ (B > C) -> (A > C)\n* Continuity\n\t* A > B > C\n\t* prob. P that agent indifferent between getting\n\t\t* B for sure\n\t\t* the lottery that yields A with prob p and C with prob 1 - p\n* Substitutability\n\t* agent indifferent between A and B ->\n\t* agent indifferent between two more complex lotteries\n\t\t* same but B is substituted for A in one of them\n\t* regardless of probs and other outcomes\n* Monotonicity\n\t* A and B: same two possible outcomes\n\t* agent prefers A to B -> \n\t* must prefer lottery with higher prob for A (vice versa)\n* Decomposability\n\t* compound lotteries ->\n\t* reduced to simpler ones (laws of prob)\n\t* “no fun in gambling”\n\n## AIMA Chapter 16.3 Utility Functions\n\n* Framing effect: ppl prefer a medical procedure with \n  * 90% survival rate >>> 10% death rate\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n* Environment history: a sequence of states and actions\n* Solutions to MDPs usually involve dynamic programming\n* Optimal policy yields highest expected utility\n* Q-function (action-utility function) Q(s, a) -> EU of taking action a at state s\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n* Algorithms\n\t* value iteration\n\t* policy iteration\n\t* linear programming\n\t* Monte Carlo planning (different solution from previous 3)\n* Policy iteration\n\t* policy evaluation\n\t\t* given policy, calculate utility of each state if policy executed\n\t* policy improvement\n\t\t* calculate new MEU policy using one-step look-ahead\n\n\n## Module 8 Lecture Notes\n\n* p(s’ | s, a): the probability of arriving in state s’ \n  * even that we are in state s and we selected action a\n* transitions are Markovian: prob of arriving in s’ only depends on s \n  * (not history of earlier states)\n* Rewards can be positive or negative (but bounded by max value) \n* Rewards are additive\n* MDP: sequential decision problem + fully observable environment +\n  * stochastic tradition model + additive rewards\n* MDPs: non-deterministic search problems\n* Expectimax search to solve MDPs\n* To solve an MDP: \n  * set of states + set of actions + transition function T(s, a, s’) + \n  * reward function R(s, a, s’) + initial state + terminal states (optional)\n* Policy π(s) = a; solution to an MDP\n* We need to compute the expected utility of all possible paths generated by a policy\n* Discounting: values of rewards decay exponentially\n* Utility = sum of (discounted) rewards\n* Value iteration: update values and the policy in each iteration; doesn’t track policy\n* Policy iteration: update utilities with fixed policy for several passes; \n  * choose a better new policy or terminate\n* To compute optimal values: value iteration/policy iteration\n* To compute values for a particular policy: policy iteration\n* Turn values into a policy: policy extraction\n* Maximum expected utility (MEU): a rational event should choose an action \n  * that maximizes its EU given its knowledge\n* Axiom of Transitivity: (A > B) ^ (B > C) -> (A > C)\n\n\n## Module 8 Definitions\n* **Stochastic** - randomly determined\n* **Policy** - a mapping from a state to an action to take in that state\n* **Nonstationary** - policy that depends on the time\n* **Proper policy** - guaranteed to reach a terminal state\n* **Max norm** - measures length of vector by |value| if its biggest component\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "* N-armed bandit\n",
        "\t* n levers\n",
        "\t* each lever -> fixed unknown prob distribution of winnings\n",
        "* Exploitation of current best action -> maximize short-term reward\n",
        "* Exploration of previously unknown states -> \n",
        "\t* gain info leading a change in policy\n",
        "\t* greater rewards in future\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "* Action-utility learning: Q-learning (most common)\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "* Passive learning agent: fixed policy that determines it behavior\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "* Active learning agent: gets to decide what action to take\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\"\"\"\n",
        "chapter22_5 =  \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "* Exploration: try unknown actions to get information\n",
        "* Exploitation: use what you know\n",
        "* Regret: make mistakes even if learn intelligently\n",
        "* Sampling: try things repeatedly because of change\n",
        "* Difficulty: learning is much harder than solving MDP\n",
        "* Basic idea of reinforcement learning:\n",
        "\t* receive feedback in the form of rewards\n",
        "\t* utility defined by reward function\n",
        "\t* must learn to act to maximize expected rewards\n",
        "\t* all learning based on observed samples of outcomes\n",
        "* Direct evaluation: compute values for each state s under policy π\n",
        "\t* Pros: \n",
        "\t\t* easy to understand; \n",
        "\t\t* doesn’t require any knowledge of T, R\n",
        "\t\t* eventually computes the correct average values\n",
        "\t* Cons:\n",
        "\t\t* wastes information about state connections\n",
        "\t\t* each state must be learned separately\n",
        "\t\t* takes a long time to learn\n",
        "* Temporal difference learning\n",
        "  * update V(s) each time there’s a transition (s, a, s’, r)\n",
        "* Problems with TD value learning: sunk if want to turn values into a (new) policy\n",
        "* Q-learning\n",
        "\t* receive a sample (s, a, s’, r)\n",
        "\t* consider old estimate Q(s, a)\n",
        "\t* consider new sample estimate\n",
        "\t* incorporate the new estimate into a running average\n",
        "* Off-policy learning: q-learning converges to optimal policy even acting suboptimally\n",
        "* Not possible to learn about every single state in reality\n",
        "\t* too many states to visit in training\n",
        "\t* too many states for q-tables in memory\n",
        "* Solution: to generalize\n",
        "\t* learn small no. of training states from experience\n",
        "\t* generalize exp. to new, similar situations\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"regret\" : \"a measure of total mistake cost (diff between expected rewards)\",\n",
        "\"reinforcement learning\": \"agent interacts with world & receives rewards periodically\",\n",
        "\"reward-to-go\": \"expected total reward from a state onward\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "80eee020-ff40-4320-a921-2119cc133fe1"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n* N-armed bandit\n\t* n levers\n\t* each lever -> fixed unknown prob distribution of winnings\n* Exploitation of current best action -> maximize short-term reward\n* Exploration of previously unknown states -> \n\t* gain info leading a change in policy\n\t* greater rewards in future\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n* Action-utility learning: Q-learning (most common)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n* Passive learning agent: fixed policy that determines it behavior\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n* Active learning agent: gets to decide what action to take\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n\n## Module 9 Lecture Notes\n\n* Exploration: try unknown actions to get information\n* Exploitation: use what you know\n* Regret: make mistakes even if learn intelligently\n* Sampling: try things repeatedly because of change\n* Difficulty: learning is much harder than solving MDP\n* Basic idea of reinforcement learning:\n\t* receive feedback in the form of rewards\n\t* utility defined by reward function\n\t* must learn to act to maximize expected rewards\n\t* all learning based on observed samples of outcomes\n* Direct evaluation: compute values for each state s under policy π\n\t* Pros: \n\t\t* easy to understand; \n\t\t* doesn’t require any knowledge of T, R\n\t\t* eventually computes the correct average values\n\t* Cons:\n\t\t* wastes information about state connections\n\t\t* each state must be learned separately\n\t\t* takes a long time to learn\n* Temporal difference learning\n  * update V(s) each time there’s a transition (s, a, s’, r)\n* Problems with TD value learning: sunk if want to turn values into a (new) policy\n* Q-learning\n\t* receive a sample (s, a, s’, r)\n\t* consider old estimate Q(s, a)\n\t* consider new sample estimate\n\t* incorporate the new estimate into a running average\n* Off-policy learning: q-learning converges to optimal policy even acting suboptimally\n* Not possible to learn about every single state in reality\n\t* too many states to visit in training\n\t* too many states for q-tables in memory\n* Solution: to generalize\n\t* learn small no. of training states from experience\n\t* generalize exp. to new, similar situations\n\n\n## Module 9 Definitions\n* **Regret** - a measure of total mistake cost (diff between expected rewards)\n* **Reinforcement learning** - agent interacts with world & receives rewards periodically\n* **Reward-to-go** - expected total reward from a state onward\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"\n",
        "* Uncertainty due to\n",
        "\t* partial observability\n",
        "\t* nonderterminism\n",
        "\t* adversaries\n",
        "* Decision theory = probability theory + utility theory\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "* Sample space: set of all possible worlds\n",
        "* Possible worlds are mutually exclusive and exhaustive\n",
        "\t* two PWs cannot both be the case\n",
        "\t* one PW must be the case\n",
        "* Unconditional/prior probability\n",
        "\t* degrees of belief in propositions\n",
        "\t* in the absence of any other info\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\"\"\"\n",
        "chapter12_4 = \"\"\"\"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "* P(X, Y|Z) = P(X|Z)P(Y|Z)\n",
        "\t* conditional indecencies of X and Y\n",
        "\t* given a third variable Z\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "* Naive Bayes is naive because\n",
        "\t* often used as a simplifying assumption \n",
        "\t* in case where effect variables !strictly independent given cause variable\n",
        "\t* sometimes called a Bayesian classifier\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\"\"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\"\n",
        "* bigram: looks one word into the past\n",
        "* n-gram: looks n - 1 words into the past\n",
        "* probability of w1 occurring after the w2\n",
        "\t* count(w2 w1) / count(w2)\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "* intrinsic evaluation: measures quality of a model (independent of any application)\n",
        "* perplexity (PP): inverse prob of test set normalized by no. of words\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "* Sampling: choose random points according to likelihood\n",
        "\"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "* n-gram is dependent on training corpus\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "* keeps lang model from assigning 0 prob to unseen events\n",
        "* called smoothing or discounting\n",
        "* Laplace smoothing: \n",
        "\t* adding 1 to all n-gram counts\n",
        "\t* before normalize into probabilities\n",
        "\t* 0 -> 1, 1 -> 2, etc.\n",
        "\t* also called add-one smoothing\n",
        "* Add-k smoothing\n",
        "\t* move less of mobility mass from seen to unseen\n",
        "\t* add a fractional count k instead of 1\n",
        "* backoff\n",
        "\t* use trigram if evidence is sufficient\n",
        "\t* otherwise use bigram/unigram\n",
        "\t* no evidence of higher gram -> backoff to lower gram\n",
        "* interpolation\n",
        "\t* mix probability estimates from all n-gram estimators\n",
        "\t* weighing & combining tri, bi, uni-gram counts\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "* Stupid backoff\n",
        "\t* does not produce a probability distribution\n",
        "\t* no discounting of higher-order probabilities\n",
        "\t* higher gram has zero count -> backoff to lower gram\n",
        "\t\t* weighted by a fixed (context-independent) weight\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "* P(a | b) = P(a, b) / P(b)\n",
        "* Product rule: P(y)P(x | y) = P(x, y)\n",
        "* Chain rule: P(x1, x2, x3) = P(x1)P(x2 | x1)P(x3 | x1, x2)\n",
        "* Bayes’ rule: P(x | y) = P(y | x) / P(y) * P(x)\n",
        "\t* build one conditional from its reverse\n",
        "\t* helpful when one condition is tricky but the other is simple\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e0ea6921-f4e1-4294-eecb-c4b60f74d80b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n* Uncertainty due to\n\t* partial observability\n\t* nonderterminism\n\t* adversaries\n* Decision theory = probability theory + utility theory\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n* Sample space: set of all possible worlds\n* Possible worlds are mutually exclusive and exhaustive\n\t* two PWs cannot both be the case\n\t* one PW must be the case\n* Unconditional/prior probability\n\t* degrees of belief in propositions\n\t* in the absence of any other info\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n\n## AIMA Chapter 12.4 Independence\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n* P(X, Y|Z) = P(X|Z)P(Y|Z)\n\t* conditional indecencies of X and Y\n\t* given a third variable Z\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n* Naive Bayes is naive because\n\t* often used as a simplifying assumption \n\t* in case where effect variables !strictly independent given cause variable\n\t* sometimes called a Bayesian classifier\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\n\n* bigram: looks one word into the past\n* n-gram: looks n - 1 words into the past\n* probability of w1 occurring after the w2\n\t* count(w2 w1) / count(w2)\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n* intrinsic evaluation: measures quality of a model (independent of any application)\n* perplexity (PP): inverse prob of test set normalized by no. of words\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n* Sampling: choose random points according to likelihood\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n* n-gram is dependent on training corpus\n\n\n## SLP Chapter 3.5 Smoothing\n\n* keeps lang model from assigning 0 prob to unseen events\n* called smoothing or discounting\n* Laplace smoothing: \n\t* adding 1 to all n-gram counts\n\t* before normalize into probabilities\n\t* 0 -> 1, 1 -> 2, etc.\n\t* also called add-one smoothing\n* Add-k smoothing\n\t* move less of mobility mass from seen to unseen\n\t* add a fractional count k instead of 1\n* backoff\n\t* use trigram if evidence is sufficient\n\t* otherwise use bigram/unigram\n\t* no evidence of higher gram -> backoff to lower gram\n* interpolation\n\t* mix probability estimates from all n-gram estimators\n\t* weighing & combining tri, bi, uni-gram counts\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n* Stupid backoff\n\t* does not produce a probability distribution\n\t* no discounting of higher-order probabilities\n\t* higher gram has zero count -> backoff to lower gram\n\t\t* weighted by a fixed (context-independent) weight\n\n\n## Module 10 Lecture Notes\n\n* P(a | b) = P(a, b) / P(b)\n* Product rule: P(y)P(x | y) = P(x, y)\n* Chain rule: P(x1, x2, x3) = P(x1)P(x2 | x1)P(x3 | x1, x2)\n* Bayes’ rule: P(x | y) = P(y | x) / P(y) * P(x)\n\t* build one conditional from its reverse\n\t* helpful when one condition is tricky but the other is simple\n\n\n## Module 10 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "* Bayesian network\n",
        "\t* represents \n",
        "\t\t* dependencies among variables\n",
        "\t\t* conditional independence relationships of a domain\n",
        "\t\t* essentially any full joint probability distribution\n",
        "\t* can be very concise\n",
        "\t* a directed graph; each node annotated with quantitative prob info\n",
        "\t* arrow from node X to node Y -> X is a parent of Y\n",
        "\t* no directed cycles -> a DAG\n",
        "\t* each node has info quantifies effect of parents on the node\n",
        "\t\t* a finite number of parameters\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "* Syntax: a DAG with some local prob info attached to each node\n",
        "* Semantics: how syntax corresponds to a joint distribution over variables\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "* Probabilistic inference system\n",
        "\t* compute posterior prob distribution for a set of query variables\n",
        "\t* given some observed event \n",
        "\t\t* assignment of values to a set of evidence variables\n",
        "* Polytrees (singly connected networks)\n",
        "\t* exact inference -> takes time linear in the size of the network\n",
        "* Random sampling e.g. likelihood weighting, Markov chain Monte Carlo\n",
        "\t* give reasonable estimate of true posterior probs in network\n",
        "\t* can deal with much larger networks\n",
        "* Bayes nets capture probabilistic influences\n",
        "* Casual networks \n",
        "\t* capture casual relationships\n",
        "\t* predict effects of interventions and observations\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "* Conditional independence: basic and robust from knowledge about uncertain environments\n",
        "* Check if two variables are independent in a given BN\n",
        "\t* analyze the graph\n",
        "\t* two nodes are connected by an undirected path not blocked by a shaded node \n",
        "    * -> conditionally independent\n",
        "* Inference: calculate useful quantity from a joint probability distribution\n",
        "* Inference by enumeration\n",
        "\t* 1. select entries consistent with evidence\n",
        "\t* 2. sum out H to get joint of query and evidence\n",
        "\t* 3. normalize\n",
        "\t* slow: join up whole joint distribution before summing out hidden values\n",
        "* Variable elimination: interleaves joining and marginalizing (NP-hard/must faster)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "   \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "54e2e4b1-5888-4782-8e98-5aba540a04e3"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n* Bayesian network\n\t* represents \n\t\t* dependencies among variables\n\t\t* conditional independence relationships of a domain\n\t\t* essentially any full joint probability distribution\n\t* can be very concise\n\t* a directed graph; each node annotated with quantitative prob info\n\t* arrow from node X to node Y -> X is a parent of Y\n\t* no directed cycles -> a DAG\n\t* each node has info quantifies effect of parents on the node\n\t\t* a finite number of parameters\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n* Syntax: a DAG with some local prob info attached to each node\n* Semantics: how syntax corresponds to a joint distribution over variables\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n* Probabilistic inference system\n\t* compute posterior prob distribution for a set of query variables\n\t* given some observed event \n\t\t* assignment of values to a set of evidence variables\n* Polytrees (singly connected networks)\n\t* exact inference -> takes time linear in the size of the network\n* Random sampling e.g. likelihood weighting, Markov chain Monte Carlo\n\t* give reasonable estimate of true posterior probs in network\n\t* can deal with much larger networks\n* Bayes nets capture probabilistic influences\n* Casual networks \n\t* capture casual relationships\n\t* predict effects of interventions and observations\n\n\n## Module 11 Lecture Notes\n\n* Conditional independence: basic and robust from knowledge about uncertain environments\n* Check if two variables are independent in a given BN\n\t* analyze the graph\n\t* two nodes are connected by an undirected path not blocked by a shaded node \n    * -> conditionally independent\n* Inference: calculate useful quantity from a joint probability distribution\n* Inference by enumeration\n\t* 1. select entries consistent with evidence\n\t* 2. sum out H to get joint of query and evidence\n\t* 3. normalize\n\t* slow: join up whole joint distribution before summing out hidden values\n* Variable elimination: interleaves joining and marginalizing (NP-hard/must faster)\n\n\n## Module 11 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "* Machine learning can improve any component of an agent program\n",
        "\t* which component to improve\n",
        "\t* what prior knowledge the agent has (influences the model it builds)\n",
        "\t* what data and feedback on data is available\n",
        "* Induction: a specific set of observations -> a general rule\n",
        "\t* inductive conclusions may be incorrect\n",
        "\t* deductive conclusions always correct if premises are connect\n",
        "* Classification: output is one of a finite set of values (e.g. sunny/cloudy)\n",
        "* Regression: output is a number (e.g. tor’s temperature as an integer)\n",
        "* Supervised learning\n",
        "\t* agent observes input-output pairs\n",
        "\t* learns a function that maps input -> output\n",
        "* Unsupervised learning\n",
        "\t* agent learns patterns in the input w/o explicit feedback\n",
        "\t* e.g. clustering\n",
        "* Reinforcement learning\n",
        "\t* agent learns from a series of rewards and punishments (reinforcements)\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\"\n",
        "* Bias:\n",
        "\t* tendency of predictive hypothesis\n",
        "\t\t* to deviate from expected value\n",
        "\t\t\t* when averaged over diff training sets\n",
        "\t* often results from restrictions by hypothesis space\n",
        "* Underfitting: when hypothesis fails to find pattern in data\n",
        "* Variance: \n",
        "\t* amount of change in hypothesis\n",
        "\t* due to fluctuation in training data\n",
        "* Overfitting\n",
        "\t* performs well on training data, poorly on unseen data\n",
        "* Bias-variance tradeoff\n",
        "\t* complex, low-bias hypotheses (fit training data well & simpler)\n",
        "\t* simpler, low-variance hypothesis (generalize better)\n",
        "* Ockham’s razor\n",
        "\t* “plurality [of entities] should not be posited without necessity” \n",
        "\t* shaves off dubious explanations\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\"\n",
        "* Decision tree\n",
        "\t* a vector of attribute values -> a single output value (decision)\n",
        "* Entropy\n",
        "\t* a measure of uncertainly of a random variable\n",
        "\t* more information -> less entropy\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\"\n",
        "* Stationarity assumption\n",
        "\t* future examples will be like the past\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\"\n",
        "* Probably approximately correct (PAC)\n",
        "\t* any hypothesis that is\n",
        "\t\t* consistent w/ a sufficiently large training set\n",
        "\t* is unlikely to be seriously wrong\n",
        "\"\"\"\n",
        "chapter19_6 = \"\"\"\n",
        "* Linear regression\n",
        "\t* the task of finding the linear function that best fits the data\n",
        "* Gradient descent\n",
        "\t* minimizing loss\n",
        "\t* step size (learning rate)\n",
        "\t\t* fixed constant | decay over time\n",
        "* Batch/deterministic gradient descent \n",
        "\t* epoch: a step covering all training examples\n",
        "* Stochastic gradient descent (SGD)\n",
        "\t* a faster variant\n",
        "\t* randomly selects a small no. of training examples at each step\n",
        "\t* also called online gradient descent\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "* compute most probable class c hat of document d\n",
        "\t* choose class with highest product of\n",
        "\t\t* prior probability of the class P(c)\n",
        "\t\t* likelihood of the document P(d|c)\n",
        "* naive Bayes assumption\n",
        "\t* probabilities P(fi|c): independent given the class c\n",
        "\t* hence can be naively multiplied\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\"\n",
        "* unknown words\n",
        "\t* in test data but not in vocabulary (did not occur in training data)\n",
        "* stop words\n",
        "\t* very frequent e.g. “the”, “a”\n",
        "\"\"\"\n",
        "slp_chapter4_3 = \"\"\"\"\"\"\n",
        "slp_chapter4_4 = \"\"\"\n",
        "* binary NB\n",
        "\t* binary multinomial naive Bayes\n",
        "\t* whether a words occurs or not > frequency\n",
        "\t* word count in each document -> 1 (improves performance)\n",
        "* sentiment lexicons\n",
        "\t* lists of words pre-annotated w/ positive/negative sentiment\n",
        "\"\"\"\n",
        "slp_chapter4_5 = \"\"\"\n",
        "* Spam detection\n",
        "\t* likely sets or words/phrases as features\n",
        "\t\t* “100% guaranteed”\n",
        "\t* other not purely linguistics features\n",
        "\t\t* unbalanced “head” tags in HTML\n",
        "* language id\n",
        "\t* what language given text is written in\n",
        "\"\"\"\n",
        "slp_chapter4_6 = \"\"\"\"\"\"\n",
        "slp_chapter4_7 = \"\"\"\n",
        "* Gold labels: human-defined labels\n",
        "* Confusion matrix\n",
        "\t* evaluates a system for detecting things\n",
        "\t* how a system performs w/ respect to gold labels\n",
        "\t* two dimensions: system output, gold labels\n",
        "* Precision\n",
        "\t* % of items the system detected that are in fact positive\n",
        "\t\t* system labels positive\n",
        "\t\t* human gold labels positive\n",
        "\t\t* (true positives) / (true positives + false positives)\n",
        "* Recall\n",
        "\t* % of items actually present in input that were correctly identified by system\n",
        "\t* (true positives) / (ture positives + false negatives)\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\"\"\"\"\n",
        "slp_chapter4_9 = \"\"\"\n",
        "* δ(x) = M(A, x)− M(B, x)\n",
        "\t* δ(x) : effect size\n",
        "\t* M(A, x): score system A gets on test set x\n",
        "\t* bigger δ: A seems to be way better than B\n",
        "\t* small δ: A seems to be only a little better than B\n",
        "* H0 : δ(x) ≤ 0\n",
        "\t* null hypothesis\n",
        "\t* A is no better than B\n",
        "* H1 : δ(x) > 0\n",
        "\t* A is better\n",
        "* p-value\n",
        "\t* P(δ(X) ≥ δ(x)|H0 is true)\n",
        "\t* H0 is true -> prob seeing δ(x) we saw or one even greater\n",
        "\t* prob we see δ(x)  assuming A not better than B\n",
        "* Statistically significant\n",
        "\t* δ has prob below threshold (e.g. 0.05, 0.01)\n",
        "\t* -> reject null hypothesis \n",
        "\"\"\"\n",
        "slp_chapter4_10 = \"\"\"\n",
        "* Representational harms\n",
        "\t* system demeans a social group\n",
        "\t* e.g. by perpetuating negative stereotypes \n",
        "* model card\n",
        "\t* characteristics of a machine learning model\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "* Machine learning\n",
        "\t* parameters (probabilities)\n",
        "\t* structure (BN graphs)\n",
        "\t* hidden concepts (clustering)\n",
        "* Classification\n",
        "\t* Spam detection (document -> spam/ham)\n",
        "\t* OCR (images -> characters)\n",
        "\t* Medical diagnosis (symptoms -> diseases)\n",
        "\t* Fraud detection (account activity -> fraud/no fraud)\n",
        "* NB: assume all features are indecent effects of label\n",
        "* Laplace smoothing: pretend saw everything one more time than actually did\n",
        "* Properties of perceptrons\n",
        "\t* Separability: whether some parameters get training set perfectly correct\n",
        "\t* Convergence: training separable -> perceptron will eventually converge\n",
        "\t* Mistake bound: max no. of mistakes related to margin/degree of separability\n",
        "* Problems with perceptron\n",
        "\t* Noise: data not separable -> weights might thrash\n",
        "\t* Mediocre generalization: gives a “barely” separating solution\n",
        "\t* Overtraining: a kind of overfitting\n",
        "* Fixing perceptron\n",
        "\t* adjust weight update\n",
        "* Maximum step size\n",
        "\t* example labeled incorrectly if updates too large\n",
        "\t* may not have enough features\n",
        "\t* solution: cap max possible step with a constant\n",
        "* Naive Bayes\n",
        "\t* builds a model training data\n",
        "\t* gives prediction probabilities\n",
        "\t* strong assumptions about feature independency\n",
        "\t* one pass through data (counting)\n",
        "* Perceptrons / MIRA\n",
        "\t* less assumptions about data\n",
        "\t* mistake-driven learning\n",
        "\t* multiple passes through data (prediction)\n",
        "\t* more accurate\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"classification\" : \"given input, predict labels\",\n",
        "\"overtraining\": \"test/held-out accuracy rises then falls\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "21235cdb-73a8-4798-dd47-43212d2ab04f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n* Machine learning can improve any component of an agent program\n\t* which component to improve\n\t* what prior knowledge the agent has (influences the model it builds)\n\t* what data and feedback on data is available\n* Induction: a specific set of observations -> a general rule\n\t* inductive conclusions may be incorrect\n\t* deductive conclusions always correct if premises are connect\n* Classification: output is one of a finite set of values (e.g. sunny/cloudy)\n* Regression: output is a number (e.g. tor’s temperature as an integer)\n* Supervised learning\n\t* agent observes input-output pairs\n\t* learns a function that maps input -> output\n* Unsupervised learning\n\t* agent learns patterns in the input w/o explicit feedback\n\t* e.g. clustering\n* Reinforcement learning\n\t* agent learns from a series of rewards and punishments (reinforcements)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n* Bias:\n\t* tendency of predictive hypothesis\n\t\t* to deviate from expected value\n\t\t\t* when averaged over diff training sets\n\t* often results from restrictions by hypothesis space\n* Underfitting: when hypothesis fails to find pattern in data\n* Variance: \n\t* amount of change in hypothesis\n\t* due to fluctuation in training data\n* Overfitting\n\t* performs well on training data, poorly on unseen data\n* Bias-variance tradeoff\n\t* complex, low-bias hypotheses (fit training data well & simpler)\n\t* simpler, low-variance hypothesis (generalize better)\n* Ockham’s razor\n\t* “plurality [of entities] should not be posited without necessity” \n\t* shaves off dubious explanations\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n* Decision tree\n\t* a vector of attribute values -> a single output value (decision)\n* Entropy\n\t* a measure of uncertainly of a random variable\n\t* more information -> less entropy\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n* Stationarity assumption\n\t* future examples will be like the past\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n* Probably approximately correct (PAC)\n\t* any hypothesis that is\n\t\t* consistent w/ a sufficiently large training set\n\t* is unlikely to be seriously wrong\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n* Linear regression\n\t* the task of finding the linear function that best fits the data\n* Gradient descent\n\t* minimizing loss\n\t* step size (learning rate)\n\t\t* fixed constant | decay over time\n* Batch/deterministic gradient descent \n\t* epoch: a step covering all training examples\n* Stochastic gradient descent (SGD)\n\t* a faster variant\n\t* randomly selects a small no. of training examples at each step\n\t* also called online gradient descent\n\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n* compute most probable class c hat of document d\n\t* choose class with highest product of\n\t\t* prior probability of the class P(c)\n\t\t* likelihood of the document P(d|c)\n* naive Bayes assumption\n\t* probabilities P(fi|c): independent given the class c\n\t* hence can be naively multiplied\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n* unknown words\n\t* in test data but not in vocabulary (did not occur in training data)\n* stop words\n\t* very frequent e.g. “the”, “a”\n\n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n* binary NB\n\t* binary multinomial naive Bayes\n\t* whether a words occurs or not > frequency\n\t* word count in each document -> 1 (improves performance)\n* sentiment lexicons\n\t* lists of words pre-annotated w/ positive/negative sentiment\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n* Spam detection\n\t* likely sets or words/phrases as features\n\t\t* “100% guaranteed”\n\t* other not purely linguistics features\n\t\t* unbalanced “head” tags in HTML\n* language id\n\t* what language given text is written in\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n* Gold labels: human-defined labels\n* Confusion matrix\n\t* evaluates a system for detecting things\n\t* how a system performs w/ respect to gold labels\n\t* two dimensions: system output, gold labels\n* Precision\n\t* % of items the system detected that are in fact positive\n\t\t* system labels positive\n\t\t* human gold labels positive\n\t\t* (true positives) / (true positives + false positives)\n* Recall\n\t* % of items actually present in input that were correctly identified by system\n\t* (true positives) / (ture positives + false negatives)\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n* δ(x) = M(A, x)− M(B, x)\n\t* δ(x) : effect size\n\t* M(A, x): score system A gets on test set x\n\t* bigger δ: A seems to be way better than B\n\t* small δ: A seems to be only a little better than B\n* H0 : δ(x) ≤ 0\n\t* null hypothesis\n\t* A is no better than B\n* H1 : δ(x) > 0\n\t* A is better\n* p-value\n\t* P(δ(X) ≥ δ(x)|H0 is true)\n\t* H0 is true -> prob seeing δ(x) we saw or one even greater\n\t* prob we see δ(x)  assuming A not better than B\n* Statistically significant\n\t* δ has prob below threshold (e.g. 0.05, 0.01)\n\t* -> reject null hypothesis \n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n* Representational harms\n\t* system demeans a social group\n\t* e.g. by perpetuating negative stereotypes \n* model card\n\t* characteristics of a machine learning model\n\n\n## Module 12 Lecture Notes\n\n* Machine learning\n\t* parameters (probabilities)\n\t* structure (BN graphs)\n\t* hidden concepts (clustering)\n* Classification\n\t* Spam detection (document -> spam/ham)\n\t* OCR (images -> characters)\n\t* Medical diagnosis (symptoms -> diseases)\n\t* Fraud detection (account activity -> fraud/no fraud)\n* NB: assume all features are indecent effects of label\n* Laplace smoothing: pretend saw everything one more time than actually did\n* Properties of perceptrons\n\t* Separability: whether some parameters get training set perfectly correct\n\t* Convergence: training separable -> perceptron will eventually converge\n\t* Mistake bound: max no. of mistakes related to margin/degree of separability\n* Problems with perceptron\n\t* Noise: data not separable -> weights might thrash\n\t* Mediocre generalization: gives a “barely” separating solution\n\t* Overtraining: a kind of overfitting\n* Fixing perceptron\n\t* adjust weight update\n* Maximum step size\n\t* example labeled incorrectly if updates too large\n\t* may not have enough features\n\t* solution: cap max possible step with a constant\n* Naive Bayes\n\t* builds a model training data\n\t* gives prediction probabilities\n\t* strong assumptions about feature independency\n\t* one pass through data (counting)\n* Perceptrons / MIRA\n\t* less assumptions about data\n\t* mistake-driven learning\n\t* multiple passes through data (prediction)\n\t* more accurate\n\n\n## Module 12 Definitions\n* **Classification** - given input, predict labels\n* **Overtraining** - test/held-out accuracy rises then falls\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"\n",
        "* Sigmoid\n",
        "\t* logistic function\n",
        "\t* σ(z) = 1 / (1 + exp(-z))\n",
        "\t* real-valued number -> range [0, 1]\n",
        "\t* 1−σ(x) = σ(−x)\n",
        "\"\"\"\n",
        "slp_chapter5_2 = \"\"\"\"\"\"\n",
        "slp_chapter5_3 = \"\"\"\n",
        "* Loss function\n",
        "\t* how close classifier output (yˆ) is to correct output (y) \n",
        "\t* L(yˆ, y) = How much ˆy differs from the true y\n",
        "\"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "* Convex function\n",
        "\t* one minimum\n",
        "\t* no local minima to get stuck in\n",
        "\t* gradient descent from any point -> find minimum\n",
        "* Gradient: a vector in direction of greatest increase in function\n",
        "* Stochastic gradient descent\n",
        "\t* minimize loss function\n",
        "\t\t* compute its graduate after each training example\n",
        "\t\t* nudge θ in opposite direction of gradient\n",
        "\t* an online algorithm\n",
        "\t\t* processes its input example by example\n",
        "\t\t* rather than waiting until sees entire input\n",
        "\"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "* L2 regularization\n",
        "\t* a quadratic function of weight values\n",
        "\t* Euclidean distance\n",
        "\t* ridge regression\n",
        "* L1 regularization\n",
        "\t* a liner function of weight values\n",
        "\t* Manhattan distance\n",
        "\t* lasso regression\n",
        "\"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "* also called softmax regression/maxent classifier\n",
        "* one-hot vector\n",
        "\t* one value = 1, rest = 0\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\n",
        "* Unit (neural unit): building block of a neural network\n",
        "* ReLU\n",
        "\t* rectified linear unit\n",
        "\t* y = max(z,0)\n",
        "\t* z if z > 0 else 0\n",
        "\"\"\"\n",
        "slp_chapter7_2 = \"\"\"\"\"\"\n",
        "slp_chapter7_3 = \"\"\"\n",
        "* FNN: a  multilayer network\n",
        "\t* units connected, no cycles\n",
        "\t* output from units in each layer ->units in next higher layer\n",
        "\t* no outputs passed back to lower layers\n",
        "\"\"\"\n",
        "slp_chapter7_4 = \"\"\"\n",
        "* Error backpropagation\n",
        "\t* or backward differentiation\n",
        "\t* compute gradients of loss function for a network\n",
        "\"\"\"\n",
        "slp_chapter7_5 = \"\"\"\n",
        "* Language modeling\n",
        "\t* predict next words from prior word context\n",
        "* Pretrained embeddings / learn embeddings from scratch\n",
        "* Neural language models\n",
        "\t* neural network as probabilistic classifier\n",
        "\t* computer prob of the next word given previous n words\n",
        "\"\"\"\n",
        "slp_chapter7_6 = \"\"\"\n",
        "* Dropout\n",
        "\t* randomly drop some units & their connections\n",
        "* Tuning hyperparameters\n",
        "\t* parameters\n",
        "\t\t* weights W & biases b (learned by gradient descent)\n",
        "\t* hyperparameters\n",
        "\t\t* things choses by algorithm designer\n",
        "\t\t* learning rate, mini-batch size\n",
        "\t\t* model architecture\n",
        "\t\t\t* no. of layers, no. of hidden nodes per layer\n",
        "\t\t\t* activation functions, etc.\n",
        "\"\"\"\n",
        "slp_chapter7_7 = \"\"\"\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "* Classifier components\n",
        "\t* feature representation of the input\n",
        "\t* classification function to compute estimated class y hat via p(y | x)\n",
        "\t* objective function for learning (minimize error on training examples)\n",
        "\t* algorithm (optimize objective function)\n",
        "* We want the loss to be\n",
        "\t* smaller if model’s estimate is close to correct\n",
        "\t* bigger if confused\n",
        "* Gradient descent: finds a minimum of function by figuring out the direction \n",
        "  * where function’s slope rises most steeply, and move in opposite direction\n",
        "* Overfitting: poor generalization/performance on unseen test set\n",
        "* Softmax function: a generalization of sigmoid function\n",
        "* Activation functions: sigmoid, relu, tanh\n",
        "* Feed-forward neural network: multiplayer, fully-connected, no cycles\n",
        "* Training Neural nets\n",
        "\t* loss function (cross-entropy loss)\n",
        "\t* optimization algorithm (gradient descent)\n",
        "\t* a way to compute gradient of loss function (error propagation)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"regularization\" : \"a way to penalize large weights\",\n",
        "\"computation graph\": \"represents process of computing a mathematical expression\"\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b4c6b9f0-ce28-4fe3-d6f9-dea5affd602a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n* Sigmoid\n\t* logistic function\n\t* σ(z) = 1 / (1 + exp(-z))\n\t* real-valued number -> range [0, 1]\n\t* 1−σ(x) = σ(−x)\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n* Loss function\n\t* how close classifier output (yˆ) is to correct output (y) \n\t* L(yˆ, y) = How much ˆy differs from the true y\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n* Convex function\n\t* one minimum\n\t* no local minima to get stuck in\n\t* gradient descent from any point -> find minimum\n* Gradient: a vector in direction of greatest increase in function\n* Stochastic gradient descent\n\t* minimize loss function\n\t\t* compute its graduate after each training example\n\t\t* nudge θ in opposite direction of gradient\n\t* an online algorithm\n\t\t* processes its input example by example\n\t\t* rather than waiting until sees entire input\n\n\n## SLP Chapter 5.5 Regularization\n\n* L2 regularization\n\t* a quadratic function of weight values\n\t* Euclidean distance\n\t* ridge regression\n* L1 regularization\n\t* a liner function of weight values\n\t* Manhattan distance\n\t* lasso regression\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n* also called softmax regression/maxent classifier\n* one-hot vector\n\t* one value = 1, rest = 0\n\n\n## SLP Chapter 7.1 Units\n\n* Unit (neural unit): building block of a neural network\n* ReLU\n\t* rectified linear unit\n\t* y = max(z,0)\n\t* z if z > 0 else 0\n\n\n## SLP Chapter 7.2 The XOR problem\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n* FNN: a  multilayer network\n\t* units connected, no cycles\n\t* output from units in each layer ->units in next higher layer\n\t* no outputs passed back to lower layers\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n* Error backpropagation\n\t* or backward differentiation\n\t* compute gradients of loss function for a network\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n* Language modeling\n\t* predict next words from prior word context\n* Pretrained embeddings / learn embeddings from scratch\n* Neural language models\n\t* neural network as probabilistic classifier\n\t* computer prob of the next word given previous n words\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n* Dropout\n\t* randomly drop some units & their connections\n* Tuning hyperparameters\n\t* parameters\n\t\t* weights W & biases b (learned by gradient descent)\n\t* hyperparameters\n\t\t* things choses by algorithm designer\n\t\t* learning rate, mini-batch size\n\t\t* model architecture\n\t\t\t* no. of layers, no. of hidden nodes per layer\n\t\t\t* activation functions, etc.\n\n\n## SLP Chapter 7.7 Training the neural language model\n\n\n## Module 13 Lecture Notes\n\n* Classifier components\n\t* feature representation of the input\n\t* classification function to compute estimated class y hat via p(y | x)\n\t* objective function for learning (minimize error on training examples)\n\t* algorithm (optimize objective function)\n* We want the loss to be\n\t* smaller if model’s estimate is close to correct\n\t* bigger if confused\n* Gradient descent: finds a minimum of function by figuring out the direction \n  * where function’s slope rises most steeply, and move in opposite direction\n* Overfitting: poor generalization/performance on unseen test set\n* Softmax function: a generalization of sigmoid function\n* Activation functions: sigmoid, relu, tanh\n* Feed-forward neural network: multiplayer, fully-connected, no cycles\n* Training Neural nets\n\t* loss function (cross-entropy loss)\n\t* optimization algorithm (gradient descent)\n\t* a way to compute gradient of loss function (error propagation)\n\n\n## Module 13 Definitions\n* **Regularization** - a way to penalize large weights\n* **Computation graph** - represents process of computing a mathematical expression\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\"\"\"\"\n",
        "slp_chapter9_2 = \"\"\"\n",
        "* RNN\n",
        "\t* any network w/ a cycle within its network connections\n",
        "\t* value of some unit is (in)directly dependent on \n",
        "\t\t* its own earlier outputs as an input\n",
        "\t* powerful, hard to reason about and to train\n",
        "\"\"\"\n",
        "slp_chapter9_3 = \"\"\"\n",
        "* Train RNN as LM\n",
        "\t* training material: a corpus of text\n",
        "\t* predict next word at each time step t\n",
        "\t* minimize error using cross-entropy as loss function\n",
        "* Teacher forcing\n",
        "\t* given correct history sequence, predict next word\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\"\n",
        "* Word similarity\n",
        "\t* ask humans to judge how similar two words are\n",
        "* Semantic frame\n",
        "\t* a set of words ->\n",
        "\t* denote perspectives/participants in a specific type of event\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\"\n",
        "* represent word meaning in NLP\n",
        "* cosine similarity\n",
        "\t* use embeddings to compute semantic similarity\n",
        "\"\"\"\n",
        "slp_chapter6_3 = \"\"\"\n",
        "* Term-document matrix\n",
        "\t* row: a word in the vocab\n",
        "\t* column: a document from a collection of documents\n",
        "\t* cell: no. times a word (row) occurs in a document (column)\n",
        "* Information retrieval\n",
        "\t* find the document d from D documents\n",
        "\t\t* that best matches a query q\n",
        "* Term-term matrix \n",
        "\t* also word-word matrix/term-context matrix\n",
        "\t* columns labeled by words\n",
        "\t* dimension: |V|×|V|\n",
        "\t* cell: no. of times row (target) word and column (context) word co-occur\n",
        "\"\"\"\n",
        "slp_chapter6_4 = \"\"\"\n",
        "* raw dot product favors long vectors\n",
        "* normalized dot product = cosine of angle between two vectors\n",
        "\"\"\"\n",
        "slp_chapter6_8 = \"\"\"\n",
        "* static embeddings\n",
        "\t* one fixed embedding for each word\n",
        "\"\"\"\n",
        "slp_chapter6_10 = \"\"\"\n",
        "* First-order co-occurrence\n",
        "\t* also syntagmatic association\n",
        "\t* two words are typically nearby each other\n",
        "\t* e.g. “wrote” -> “book” or “poem”\n",
        "* Second-order co-occurrence\n",
        "\t* two words have similar neighbors\n",
        "\t* e.g. “wrote” -> “said” or “remarked”\n",
        "\"\"\"\n",
        "slp_chapter6_11 = \"\"\"\n",
        "* Allocational harm\n",
        "\t* system allocates resources unfairly to diff groups\n",
        "\t* e.g. “father“ -> “doctor“, “mother“ -> “nurse“\n",
        "* Embeddings amplify bias\n",
        "\"\"\"\n",
        "slp_chapter6_12 = \"\"\"\n",
        "* Similarity\n",
        "\t* compute correlation between scores by algorithm and by humans\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "* Neural LMs > n-gram LMs:\n",
        "\t* no need for smoothing\n",
        "\t* handle much longer histories\n",
        "\t* generalize over contexts of similar words\n",
        "\t* much higher predictive accuracy\n",
        "\t* but -> slower to train\n",
        "* Neural LMs\n",
        "\t* input: k-gram of words w1:k\n",
        "\t* output: probability distribution over next word\n",
        "* Word meaning representation\n",
        "\t* synonyms (similar meanings)\n",
        "\t* antonyms (opposite meanings)\n",
        "\t* connotations (positive or negative)\n",
        "\t* semantics roles (purchasing -> buy, sell, pay)\n",
        "\t* entailment\n",
        "* Term-document matrix\n",
        "\t* two row vectors -> how similar two words are\n",
        "\t* length: no. of documents \n",
        "* Term-term matrix\n",
        "\t* every word: row vector\n",
        "\t* every word: column vector\n",
        "\t* length: size of vocabulary \n",
        "\t* also called term-context matrix\n",
        "\t* how often a word1 appear in a context window surrounding a word2\n",
        "* TF-IDF: term frequency* inverse document frequency\n",
        "* Co-occurrence matrix: long & sparse\n",
        "* Word2Vec\n",
        "\t* learn embeddings in the process of word prediction\n",
        "\t* train a classifier to predict neighboring words\n",
        "\t* fast, east to train (>>> SVD)\n",
        "* Negative sampling: probability of neighboring words to be high and random inrelevant words to be low\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"term frequency\" : \"how often a word occurred in a document\",   \n",
        "\" inverse document frequency\": \"1/(no. of documents a word occurred in)\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7c1e2c00-1358-40cd-986f-f4ee89b8ca01"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n* RNN\n\t* any network w/ a cycle within its network connections\n\t* value of some unit is (in)directly dependent on \n\t\t* its own earlier outputs as an input\n\t* powerful, hard to reason about and to train\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n* Train RNN as LM\n\t* training material: a corpus of text\n\t* predict next word at each time step t\n\t* minimize error using cross-entropy as loss function\n* Teacher forcing\n\t* given correct history sequence, predict next word\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n* Word similarity\n\t* ask humans to judge how similar two words are\n* Semantic frame\n\t* a set of words ->\n\t* denote perspectives/participants in a specific type of event\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n* represent word meaning in NLP\n* cosine similarity\n\t* use embeddings to compute semantic similarity\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n* Term-document matrix\n\t* row: a word in the vocab\n\t* column: a document from a collection of documents\n\t* cell: no. times a word (row) occurs in a document (column)\n* Information retrieval\n\t* find the document d from D documents\n\t\t* that best matches a query q\n* Term-term matrix \n\t* also word-word matrix/term-context matrix\n\t* columns labeled by words\n\t* dimension: |V|×|V|\n\t* cell: no. of times row (target) word and column (context) word co-occur\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n* raw dot product favors long vectors\n* normalized dot product = cosine of angle between two vectors\n\n\n## SLP Chapter 6.8 Word2vec\n\n* static embeddings\n\t* one fixed embedding for each word\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n* First-order co-occurrence\n\t* also syntagmatic association\n\t* two words are typically nearby each other\n\t* e.g. “wrote” -> “book” or “poem”\n* Second-order co-occurrence\n\t* two words have similar neighbors\n\t* e.g. “wrote” -> “said” or “remarked”\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\n* Allocational harm\n\t* system allocates resources unfairly to diff groups\n\t* e.g. “father“ -> “doctor“, “mother“ -> “nurse“\n* Embeddings amplify bias\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n* Similarity\n\t* compute correlation between scores by algorithm and by humans\n\n\n## Module 13 Lecture Notes\n\n* Classifier components\n\t* feature representation of the input\n\t* classification function to compute estimated class y hat via p(y | x)\n\t* objective function for learning (minimize error on training examples)\n\t* algorithm (optimize objective function)\n* We want the loss to be\n\t* smaller if model’s estimate is close to correct\n\t* bigger if confused\n* Gradient descent: finds a minimum of function by figuring out the direction \n  * where function’s slope rises most steeply, and move in opposite direction\n* Overfitting: poor generalization/performance on unseen test set\n* Softmax function: a generalization of sigmoid function\n* Activation functions: sigmoid, relu, tanh\n* Feed-forward neural network: multiplayer, fully-connected, no cycles\n* Training Neural nets\n\t* loss function (cross-entropy loss)\n\t* optimization algorithm (gradient descent)\n\t* a way to compute gradient of loss function (error propagation)\n\n\n## Module 14 Definitions\n* **Term frequency** - how often a word occurred in a document\n* ** inverse document frequency** - 1/(no. of documents a word occurred in)\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": "fad55224-3cf9-41c2-d7ea-568d824e8df8"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n* Utility function U(s): single number -> desirability of a state\n* Expected utility EU(a): avg utility value of outcomes weighted by prob outcome occurs\n* MEU: rational agent should choose the action to maximize EU\n \n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n* A > B: agent prefers A over B\n* A ~ B: agent indifferent between A and B\n* A >~ B: agent prefers A over B | indifferent between A and B\n* Orderability\n\t* given two lotteries\n\t* must either prefer one lottery  or see them as equally preferable\n\t* only one of (A > B), (B > A), (A ~ B) holds\n* Transitivity: \n\t* given three lotteries\n\t* prefers A to B & B to C -> must prefer A to C\n\t* (A > B) ∧ (B > C) -> (A > C)\n* Continuity\n\t* A > B > C\n\t* prob. P that agent indifferent between getting\n\t\t* B for sure\n\t\t* the lottery that yields A with prob p and C with prob 1 - p\n* Substitutability\n\t* agent indifferent between A and B ->\n\t* agent indifferent between two more complex lotteries\n\t\t* same but B is substituted for A in one of them\n\t* regardless of probs and other outcomes\n* Monotonicity\n\t* A and B: same two possible outcomes\n\t* agent prefers A to B -> \n\t* must prefer lottery with higher prob for A (vice versa)\n* Decomposability\n\t* compound lotteries ->\n\t* reduced to simpler ones (laws of prob)\n\t* “no fun in gambling”\n\n## AIMA Chapter 16.3 Utility Functions\n\n* Framing effect: ppl prefer a medical procedure with \n  * 90% survival rate >>> 10% death rate\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n* Environment history: a sequence of states and actions\n* Solutions to MDPs usually involve dynamic programming\n* Optimal policy yields highest expected utility\n* Q-function (action-utility function) Q(s, a) -> EU of taking action a at state s\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n* Algorithms\n\t* value iteration\n\t* policy iteration\n\t* linear programming\n\t* Monte Carlo planning (different solution from previous 3)\n* Policy iteration\n\t* policy evaluation\n\t\t* given policy, calculate utility of each state if policy executed\n\t* policy improvement\n\t\t* calculate new MEU policy using one-step look-ahead\n\n\n## Module 8 Lecture Notes\n\n* p(s’ | s, a): the probability of arriving in state s’ \n  * even that we are in state s and we selected action a\n* transitions are Markovian: prob of arriving in s’ only depends on s \n  * (not history of earlier states)\n* Rewards can be positive or negative (but bounded by max value) \n* Rewards are additive\n* MDP: sequential decision problem + fully observable environment +\n  * stochastic tradition model + additive rewards\n* MDPs: non-deterministic search problems\n* Expectimax search to solve MDPs\n* To solve an MDP: \n  * set of states + set of actions + transition function T(s, a, s’) + \n  * reward function R(s, a, s’) + initial state + terminal states (optional)\n* Policy π(s) = a; solution to an MDP\n* We need to compute the expected utility of all possible paths generated by a policy\n* Discounting: values of rewards decay exponentially\n* Utility = sum of (discounted) rewards\n* Value iteration: update values and the policy in each iteration; doesn’t track policy\n* Policy iteration: update utilities with fixed policy for several passes; \n  * choose a better new policy or terminate\n* To compute optimal values: value iteration/policy iteration\n* To compute values for a particular policy: policy iteration\n* Turn values into a policy: policy extraction\n* Maximum expected utility (MEU): a rational event should choose an action \n  * that maximizes its EU given its knowledge\n* Axiom of Transitivity: (A > B) ^ (B > C) -> (A > C)\n\n\n## Module 8 Definitions\n* **Stochastic** - randomly determined\n* **Policy** - a mapping from a state to an action to take in that state\n* **Nonstationary** - policy that depends on the time\n* **Proper policy** - guaranteed to reach a terminal state\n* **Max norm** - measures length of vector by |value| if its biggest component\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n* N-armed bandit\n\t* n levers\n\t* each lever -> fixed unknown prob distribution of winnings\n* Exploitation of current best action -> maximize short-term reward\n* Exploration of previously unknown states -> \n\t* gain info leading a change in policy\n\t* greater rewards in future\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n* Action-utility learning: Q-learning (most common)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n* Passive learning agent: fixed policy that determines it behavior\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n* Active learning agent: gets to decide what action to take\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n\n## Module 9 Lecture Notes\n\n* Exploration: try unknown actions to get information\n* Exploitation: use what you know\n* Regret: make mistakes even if learn intelligently\n* Sampling: try things repeatedly because of change\n* Difficulty: learning is much harder than solving MDP\n* Basic idea of reinforcement learning:\n\t* receive feedback in the form of rewards\n\t* utility defined by reward function\n\t* must learn to act to maximize expected rewards\n\t* all learning based on observed samples of outcomes\n* Direct evaluation: compute values for each state s under policy π\n\t* Pros: \n\t\t* easy to understand; \n\t\t* doesn’t require any knowledge of T, R\n\t\t* eventually computes the correct average values\n\t* Cons:\n\t\t* wastes information about state connections\n\t\t* each state must be learned separately\n\t\t* takes a long time to learn\n* Temporal difference learning\n  * update V(s) each time there’s a transition (s, a, s’, r)\n* Problems with TD value learning: sunk if want to turn values into a (new) policy\n* Q-learning\n\t* receive a sample (s, a, s’, r)\n\t* consider old estimate Q(s, a)\n\t* consider new sample estimate\n\t* incorporate the new estimate into a running average\n* Off-policy learning: q-learning converges to optimal policy even acting suboptimally\n* Not possible to learn about every single state in reality\n\t* too many states to visit in training\n\t* too many states for q-tables in memory\n* Solution: to generalize\n\t* learn small no. of training states from experience\n\t* generalize exp. to new, similar situations\n\n\n## Module 9 Definitions\n* **Regret** - a measure of total mistake cost (diff between expected rewards)\n* **Reinforcement learning** - agent interacts with world & receives rewards periodically\n* **Reward-to-go** - expected total reward from a state onward\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n* Uncertainty due to\n\t* partial observability\n\t* nonderterminism\n\t* adversaries\n* Decision theory = probability theory + utility theory\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n* Sample space: set of all possible worlds\n* Possible worlds are mutually exclusive and exhaustive\n\t* two PWs cannot both be the case\n\t* one PW must be the case\n* Unconditional/prior probability\n\t* degrees of belief in propositions\n\t* in the absence of any other info\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n\n## AIMA Chapter 12.4 Independence\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n* P(X, Y|Z) = P(X|Z)P(Y|Z)\n\t* conditional indecencies of X and Y\n\t* given a third variable Z\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n* Naive Bayes is naive because\n\t* often used as a simplifying assumption \n\t* in case where effect variables !strictly independent given cause variable\n\t* sometimes called a Bayesian classifier\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\n\n* bigram: looks one word into the past\n* n-gram: looks n - 1 words into the past\n* probability of w1 occurring after the w2\n\t* count(w2 w1) / count(w2)\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n* intrinsic evaluation: measures quality of a model (independent of any application)\n* perplexity (PP): inverse prob of test set normalized by no. of words\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n* Sampling: choose random points according to likelihood\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\n* n-gram is dependent on training corpus\n\n\n## SLP Chapter 3.5 Smoothing\n\n* keeps lang model from assigning 0 prob to unseen events\n* called smoothing or discounting\n* Laplace smoothing: \n\t* adding 1 to all n-gram counts\n\t* before normalize into probabilities\n\t* 0 -> 1, 1 -> 2, etc.\n\t* also called add-one smoothing\n* Add-k smoothing\n\t* move less of mobility mass from seen to unseen\n\t* add a fractional count k instead of 1\n* backoff\n\t* use trigram if evidence is sufficient\n\t* otherwise use bigram/unigram\n\t* no evidence of higher gram -> backoff to lower gram\n* interpolation\n\t* mix probability estimates from all n-gram estimators\n\t* weighing & combining tri, bi, uni-gram counts\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n* Stupid backoff\n\t* does not produce a probability distribution\n\t* no discounting of higher-order probabilities\n\t* higher gram has zero count -> backoff to lower gram\n\t\t* weighted by a fixed (context-independent) weight\n\n\n## Module 10 Lecture Notes\n\n* P(a | b) = P(a, b) / P(b)\n* Product rule: P(y)P(x | y) = P(x, y)\n* Chain rule: P(x1, x2, x3) = P(x1)P(x2 | x1)P(x3 | x1, x2)\n* Bayes’ rule: P(x | y) = P(y | x) / P(y) * P(x)\n\t* build one conditional from its reverse\n\t* helpful when one condition is tricky but the other is simple\n\n\n## Module 10 Definitions\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n* Bayesian network\n\t* represents \n\t\t* dependencies among variables\n\t\t* conditional independence relationships of a domain\n\t\t* essentially any full joint probability distribution\n\t* can be very concise\n\t* a directed graph; each node annotated with quantitative prob info\n\t* arrow from node X to node Y -> X is a parent of Y\n\t* no directed cycles -> a DAG\n\t* each node has info quantifies effect of parents on the node\n\t\t* a finite number of parameters\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n* Syntax: a DAG with some local prob info attached to each node\n* Semantics: how syntax corresponds to a joint distribution over variables\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n* Probabilistic inference system\n\t* compute posterior prob distribution for a set of query variables\n\t* given some observed event \n\t\t* assignment of values to a set of evidence variables\n* Polytrees (singly connected networks)\n\t* exact inference -> takes time linear in the size of the network\n* Random sampling e.g. likelihood weighting, Markov chain Monte Carlo\n\t* give reasonable estimate of true posterior probs in network\n\t* can deal with much larger networks\n* Bayes nets capture probabilistic influences\n* Casual networks \n\t* capture casual relationships\n\t* predict effects of interventions and observations\n\n\n## Module 11 Lecture Notes\n\n* Conditional independence: basic and robust from knowledge about uncertain environments\n* Check if two variables are independent in a given BN\n\t* analyze the graph\n\t* two nodes are connected by an undirected path not blocked by a shaded node \n    * -> conditionally independent\n* Inference: calculate useful quantity from a joint probability distribution\n* Inference by enumeration\n\t* 1. select entries consistent with evidence\n\t* 2. sum out H to get joint of query and evidence\n\t* 3. normalize\n\t* slow: join up whole joint distribution before summing out hidden values\n* Variable elimination: interleaves joining and marginalizing (NP-hard/must faster)\n\n\n## Module 11 Definitions\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n* Machine learning can improve any component of an agent program\n\t* which component to improve\n\t* what prior knowledge the agent has (influences the model it builds)\n\t* what data and feedback on data is available\n* Induction: a specific set of observations -> a general rule\n\t* inductive conclusions may be incorrect\n\t* deductive conclusions always correct if premises are connect\n* Classification: output is one of a finite set of values (e.g. sunny/cloudy)\n* Regression: output is a number (e.g. tor’s temperature as an integer)\n* Supervised learning\n\t* agent observes input-output pairs\n\t* learns a function that maps input -> output\n* Unsupervised learning\n\t* agent learns patterns in the input w/o explicit feedback\n\t* e.g. clustering\n* Reinforcement learning\n\t* agent learns from a series of rewards and punishments (reinforcements)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n* Bias:\n\t* tendency of predictive hypothesis\n\t\t* to deviate from expected value\n\t\t\t* when averaged over diff training sets\n\t* often results from restrictions by hypothesis space\n* Underfitting: when hypothesis fails to find pattern in data\n* Variance: \n\t* amount of change in hypothesis\n\t* due to fluctuation in training data\n* Overfitting\n\t* performs well on training data, poorly on unseen data\n* Bias-variance tradeoff\n\t* complex, low-bias hypotheses (fit training data well & simpler)\n\t* simpler, low-variance hypothesis (generalize better)\n* Ockham’s razor\n\t* “plurality [of entities] should not be posited without necessity” \n\t* shaves off dubious explanations\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n* Decision tree\n\t* a vector of attribute values -> a single output value (decision)\n* Entropy\n\t* a measure of uncertainly of a random variable\n\t* more information -> less entropy\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n* Stationarity assumption\n\t* future examples will be like the past\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n* Probably approximately correct (PAC)\n\t* any hypothesis that is\n\t\t* consistent w/ a sufficiently large training set\n\t* is unlikely to be seriously wrong\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n* Linear regression\n\t* the task of finding the linear function that best fits the data\n* Gradient descent\n\t* minimizing loss\n\t* step size (learning rate)\n\t\t* fixed constant | decay over time\n* Batch/deterministic gradient descent \n\t* epoch: a step covering all training examples\n* Stochastic gradient descent (SGD)\n\t* a faster variant\n\t* randomly selects a small no. of training examples at each step\n\t* also called online gradient descent\n\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n* compute most probable class c hat of document d\n\t* choose class with highest product of\n\t\t* prior probability of the class P(c)\n\t\t* likelihood of the document P(d|c)\n* naive Bayes assumption\n\t* probabilities P(fi|c): independent given the class c\n\t* hence can be naively multiplied\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\n* unknown words\n\t* in test data but not in vocabulary (did not occur in training data)\n* stop words\n\t* very frequent e.g. “the”, “a”\n\n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\n* binary NB\n\t* binary multinomial naive Bayes\n\t* whether a words occurs or not > frequency\n\t* word count in each document -> 1 (improves performance)\n* sentiment lexicons\n\t* lists of words pre-annotated w/ positive/negative sentiment\n\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\n* Spam detection\n\t* likely sets or words/phrases as features\n\t\t* “100% guaranteed”\n\t* other not purely linguistics features\n\t\t* unbalanced “head” tags in HTML\n* language id\n\t* what language given text is written in\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\n* Gold labels: human-defined labels\n* Confusion matrix\n\t* evaluates a system for detecting things\n\t* how a system performs w/ respect to gold labels\n\t* two dimensions: system output, gold labels\n* Precision\n\t* % of items the system detected that are in fact positive\n\t\t* system labels positive\n\t\t* human gold labels positive\n\t\t* (true positives) / (true positives + false positives)\n* Recall\n\t* % of items actually present in input that were correctly identified by system\n\t* (true positives) / (ture positives + false negatives)\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\n* δ(x) = M(A, x)− M(B, x)\n\t* δ(x) : effect size\n\t* M(A, x): score system A gets on test set x\n\t* bigger δ: A seems to be way better than B\n\t* small δ: A seems to be only a little better than B\n* H0 : δ(x) ≤ 0\n\t* null hypothesis\n\t* A is no better than B\n* H1 : δ(x) > 0\n\t* A is better\n* p-value\n\t* P(δ(X) ≥ δ(x)|H0 is true)\n\t* H0 is true -> prob seeing δ(x) we saw or one even greater\n\t* prob we see δ(x)  assuming A not better than B\n* Statistically significant\n\t* δ has prob below threshold (e.g. 0.05, 0.01)\n\t* -> reject null hypothesis \n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\n* Representational harms\n\t* system demeans a social group\n\t* e.g. by perpetuating negative stereotypes \n* model card\n\t* characteristics of a machine learning model\n\n\n## Module 12 Lecture Notes\n\n* Machine learning\n\t* parameters (probabilities)\n\t* structure (BN graphs)\n\t* hidden concepts (clustering)\n* Classification\n\t* Spam detection (document -> spam/ham)\n\t* OCR (images -> characters)\n\t* Medical diagnosis (symptoms -> diseases)\n\t* Fraud detection (account activity -> fraud/no fraud)\n* NB: assume all features are indecent effects of label\n* Laplace smoothing: pretend saw everything one more time than actually did\n* Properties of perceptrons\n\t* Separability: whether some parameters get training set perfectly correct\n\t* Convergence: training separable -> perceptron will eventually converge\n\t* Mistake bound: max no. of mistakes related to margin/degree of separability\n* Problems with perceptron\n\t* Noise: data not separable -> weights might thrash\n\t* Mediocre generalization: gives a “barely” separating solution\n\t* Overtraining: a kind of overfitting\n* Fixing perceptron\n\t* adjust weight update\n* Maximum step size\n\t* example labeled incorrectly if updates too large\n\t* may not have enough features\n\t* solution: cap max possible step with a constant\n* Naive Bayes\n\t* builds a model training data\n\t* gives prediction probabilities\n\t* strong assumptions about feature independency\n\t* one pass through data (counting)\n* Perceptrons / MIRA\n\t* less assumptions about data\n\t* mistake-driven learning\n\t* multiple passes through data (prediction)\n\t* more accurate\n\n\n## Module 12 Definitions\n* **Classification** - given input, predict labels\n* **Overtraining** - test/held-out accuracy rises then falls\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n* Sigmoid\n\t* logistic function\n\t* σ(z) = 1 / (1 + exp(-z))\n\t* real-valued number -> range [0, 1]\n\t* 1−σ(x) = σ(−x)\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n* Loss function\n\t* how close classifier output (yˆ) is to correct output (y) \n\t* L(yˆ, y) = How much ˆy differs from the true y\n\n\n## SLP Chapter 5.4 Gradient Descent\n\n* Convex function\n\t* one minimum\n\t* no local minima to get stuck in\n\t* gradient descent from any point -> find minimum\n* Gradient: a vector in direction of greatest increase in function\n* Stochastic gradient descent\n\t* minimize loss function\n\t\t* compute its graduate after each training example\n\t\t* nudge θ in opposite direction of gradient\n\t* an online algorithm\n\t\t* processes its input example by example\n\t\t* rather than waiting until sees entire input\n\n\n## SLP Chapter 5.5 Regularization\n\n* L2 regularization\n\t* a quadratic function of weight values\n\t* Euclidean distance\n\t* ridge regression\n* L1 regularization\n\t* a liner function of weight values\n\t* Manhattan distance\n\t* lasso regression\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n* also called softmax regression/maxent classifier\n* one-hot vector\n\t* one value = 1, rest = 0\n\n\n## SLP Chapter 7.1 Units\n\n* Unit (neural unit): building block of a neural network\n* ReLU\n\t* rectified linear unit\n\t* y = max(z,0)\n\t* z if z > 0 else 0\n\n\n## SLP Chapter 7.2 The XOR problem\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n* FNN: a  multilayer network\n\t* units connected, no cycles\n\t* output from units in each layer ->units in next higher layer\n\t* no outputs passed back to lower layers\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\n* Error backpropagation\n\t* or backward differentiation\n\t* compute gradients of loss function for a network\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\n* Language modeling\n\t* predict next words from prior word context\n* Pretrained embeddings / learn embeddings from scratch\n* Neural language models\n\t* neural network as probabilistic classifier\n\t* computer prob of the next word given previous n words\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\n* Dropout\n\t* randomly drop some units & their connections\n* Tuning hyperparameters\n\t* parameters\n\t\t* weights W & biases b (learned by gradient descent)\n\t* hyperparameters\n\t\t* things choses by algorithm designer\n\t\t* learning rate, mini-batch size\n\t\t* model architecture\n\t\t\t* no. of layers, no. of hidden nodes per layer\n\t\t\t* activation functions, etc.\n\n\n## SLP Chapter 7.7 Training the neural language model\n\n\n## Module 13 Lecture Notes\n\n* Classifier components\n\t* feature representation of the input\n\t* classification function to compute estimated class y hat via p(y | x)\n\t* objective function for learning (minimize error on training examples)\n\t* algorithm (optimize objective function)\n* We want the loss to be\n\t* smaller if model’s estimate is close to correct\n\t* bigger if confused\n* Gradient descent: finds a minimum of function by figuring out the direction \n  * where function’s slope rises most steeply, and move in opposite direction\n* Overfitting: poor generalization/performance on unseen test set\n* Softmax function: a generalization of sigmoid function\n* Activation functions: sigmoid, relu, tanh\n* Feed-forward neural network: multiplayer, fully-connected, no cycles\n* Training Neural nets\n\t* loss function (cross-entropy loss)\n\t* optimization algorithm (gradient descent)\n\t* a way to compute gradient of loss function (error propagation)\n\n\n## Module 13 Definitions\n* **Regularization** - a way to penalize large weights\n* **Computation graph** - represents process of computing a mathematical expression\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\n* RNN\n\t* any network w/ a cycle within its network connections\n\t* value of some unit is (in)directly dependent on \n\t\t* its own earlier outputs as an input\n\t* powerful, hard to reason about and to train\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\n* Train RNN as LM\n\t* training material: a corpus of text\n\t* predict next word at each time step t\n\t* minimize error using cross-entropy as loss function\n* Teacher forcing\n\t* given correct history sequence, predict next word\n\n\n## SLP Chapter 6.1 Lexical Semantics\n\n* Word similarity\n\t* ask humans to judge how similar two words are\n* Semantic frame\n\t* a set of words ->\n\t* denote perspectives/participants in a specific type of event\n\n\n## SLP Chapter 6.2 Vector Semantics\n\n* represent word meaning in NLP\n* cosine similarity\n\t* use embeddings to compute semantic similarity\n\n\n## SLP Chapter 6.3 Words and Vectors\n\n* Term-document matrix\n\t* row: a word in the vocab\n\t* column: a document from a collection of documents\n\t* cell: no. times a word (row) occurs in a document (column)\n* Information retrieval\n\t* find the document d from D documents\n\t\t* that best matches a query q\n* Term-term matrix \n\t* also word-word matrix/term-context matrix\n\t* columns labeled by words\n\t* dimension: |V|×|V|\n\t* cell: no. of times row (target) word and column (context) word co-occur\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\n* raw dot product favors long vectors\n* normalized dot product = cosine of angle between two vectors\n\n\n## SLP Chapter 6.8 Word2vec\n\n* static embeddings\n\t* one fixed embedding for each word\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\n* First-order co-occurrence\n\t* also syntagmatic association\n\t* two words are typically nearby each other\n\t* e.g. “wrote” -> “book” or “poem”\n* Second-order co-occurrence\n\t* two words have similar neighbors\n\t* e.g. “wrote” -> “said” or “remarked”\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\n* Allocational harm\n\t* system allocates resources unfairly to diff groups\n\t* e.g. “father“ -> “doctor“, “mother“ -> “nurse“\n* Embeddings amplify bias\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\n* Similarity\n\t* compute correlation between scores by algorithm and by humans\n\n\n## Module 13 Lecture Notes\n\n* Classifier components\n\t* feature representation of the input\n\t* classification function to compute estimated class y hat via p(y | x)\n\t* objective function for learning (minimize error on training examples)\n\t* algorithm (optimize objective function)\n* We want the loss to be\n\t* smaller if model’s estimate is close to correct\n\t* bigger if confused\n* Gradient descent: finds a minimum of function by figuring out the direction \n  * where function’s slope rises most steeply, and move in opposite direction\n* Overfitting: poor generalization/performance on unseen test set\n* Softmax function: a generalization of sigmoid function\n* Activation functions: sigmoid, relu, tanh\n* Feed-forward neural network: multiplayer, fully-connected, no cycles\n* Training Neural nets\n\t* loss function (cross-entropy loss)\n\t* optimization algorithm (gradient descent)\n\t* a way to compute gradient of loss function (error propagation)\n\n\n## Module 14 Definitions\n* **Term frequency** - how often a word occurred in a document\n* ** inverse document frequency** - 1/(no. of documents a word occurred in)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}