{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Aryan_Singh_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/",
          "height": 0
        },
        "outputId": "ad60a16f-2b40-4e74-f385-3ffebbd58af7"
      },
      "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": 58,
      "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/",
          "height": 0
        },
        "outputId": "05d5e45f-9623-4305-da6f-0f9a9ad686df"
      },
      "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": 59,
      "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": 60,
      "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 = \"\"\" We will say that the probability of reaching state s' by completing action a is \\\n",
        "              \"\"\"  + sample_equation + \"\"\". An agents preferences are expressed by a utility function \\\n",
        "                  which assigns a value of desirability to each state. Expected utility of an action is \\\n",
        "                  the average utility of all next states times the probability of reaching them with an \\\n",
        "                  action. MEU says an agent should choose the action that maximizes EU. \"\"\"\n",
        "chapter16_2 =  \"\"\" We think of outcomes for actions as a lottery, which have outcomes Si associated \\\n",
        "                   probabilities pi. Each outcome can either be an atomic state or another lottery. \\\n",
        "                   These lotteries must obey the axioms of orderability, transitivity, continuity \\\n",
        "                   (A > B > C then there exists p s.t. B = [p; A, 1-p; C]), substitutability, \\\n",
        "                   monotonicity (A > B -> p > q iff [p; A, 1-p; B] > [q; A, 1-q; B]), and decomposability. \\\n",
        "                   These axioms of utility theory being satisfied imply there exists a utility function \\\n",
        "                   consistent with the preferences. The actual number of the utility does not matter, \\\n",
        "                   as long as it is consistent relatively.\"\"\"\n",
        "chapter16_3 =  \"\"\" Finding a utility function has a process called preference elicitation, in which \\\n",
        "                   choices are presented and the answers are used to define the function. Normalized \\\n",
        "                   utilities are between 0 and 1, but there is no absolute scale. We can assess the \\\n",
        "                   utility of any lottery by choosing between it and [p, U*; 1-p; U^] where U* is the \\\n",
        "                   best possible utility and U^ the worst, and we adjust p until we get indifference. \\\n",
        "                   The value of a statistical life is estimated for the utility of a human. Money \\\n",
        "                   is a good example since more money is monotonically preferred, but the utility \\\n",
        "                   function here has diminishing returns, meaning it is logarithmic. We can have \\\n",
        "                   risk-averse (positive insurance premium) and risk-seeking (negative) sections \\\n",
        "                   of the utility function for behavior. Oftentimes, we have to choose the action \\\n",
        "                   to maximize ESTIMATED expected utility with an unbiased estimator. The problem \\\n",
        "                   with this is that since we always maximize we favor positive errors and generate \\\n",
        "                   bias. Decision theory is normative saying how agents should act but descriptive \\\n",
        "                   theory states how they do act. The certainty affect says people are strongly \\\n",
        "                   attracted to certain gains. People also have ambiguity aversion. The anchoring \\\n",
        "                   effect is one that frames estimates by making relative judgements rather than absolute.\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" With sequential decision problems, the utility function depends on an environment \\\n",
        "                  history rather than a single state. For these we assume each transition has a bounded \\\n",
        "                  reward. We cannot have a fixed action sequence solution with a stochastic environemnt, \\\n",
        "                  so our solution must be a policy. Optimal policies have the highest expected utility. To \\\n",
        "                  evaluate utility we must consider the time horizon, and a policy that depends on time left \\\n",
        "                  is called nonstationary. To calculate utility of state sequences we use additive discounted \\\n",
        "                  rewards (bounds infinite sequences too). A policy guaranteed to reach a terminal state is \\\n",
        "                  called proper. Then, we can get the utility of a policy given a starting state. The optimal \\\n",
        "                  policy takes the argmax of the utilities with respect to all policies in a given state. Thus, \\\n",
        "                  we can derive the bellman equation which defines the utility of a state by the utilies of its \\\n",
        "                  neighbors with an optimal policy on them. The Q value of the expected utility of a given action \\\n",
        "                  in a given state, and the max Q value by action is the utility of a state. Shaping theorem says \\\n",
        "                  we can add any y*f(s')-f(s) to the reward and get a still valid reward function. We can represent \\\n",
        "                  small MDPs with Q value tables, but larger ones need dynamic decision networks. \"\"\"\n",
        "chapter17_2 =  \"\"\" Value iteration utilizes the Bellman Equations to solve MDPs. We initialize arbitrary values \\\n",
        "                   for each state, and then perform bellman updates until we converge. This convergence is true \\\n",
        "                   due to contraction, since the values always geet closer together. Policy iteration involves \\\n",
        "                   alternating beetween evaluation in which we calculate the utility of each state given the \\\n",
        "                   current policy and then improvement where a new policy is calculated based on these updates \\\n",
        "                   utilities. Asynchronous policy iteration updates only a certain subset of states. We can also \\\n",
        "                   use linear programming which the utilities as variables. Online algorithms like expectimax \\\n",
        "                   essentially compute at each step instead of precomputing. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" QALY is a quality adjusted life year. \"\"\"\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",
        "\"micromort\": \"one in a million chance of death\",\n",
        "\"certainty equivalent\": \"value will accept in lieu of a lottery\",\n",
        "\"insurance premium\": \"difference between EMV and certianty equivalent\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 61,
      "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": 1052
        },
        "outputId": "72376c8e-d035-4009-9826-dd3c9ec0bbe0"
      },
      "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": 62,
      "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 We will say that the probability of reaching state s' by completing action a is                $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ . An agents preferences are expressed by a utility function                   which assigns a value of desirability to each state. Expected utility of an action is                   the average utility of all next states times the probability of reaching them with an                   action. MEU says an agent should choose the action that maximizes EU. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n We think of outcomes for actions as a lottery, which have outcomes Si associated                    probabilities pi. Each outcome can either be an atomic state or another lottery.                    These lotteries must obey the axioms of orderability, transitivity, continuity                    (A > B > C then there exists p s.t. B = [p; A, 1-p; C]), substitutability,                    monotonicity (A > B -> p > q iff [p; A, 1-p; B] > [q; A, 1-q; B]), and decomposability.                    These axioms of utility theory being satisfied imply there exists a utility function                    consistent with the preferences. The actual number of the utility does not matter,                    as long as it is consistent relatively.\n\n## AIMA Chapter 16.3 Utility Functions\n Finding a utility function has a process called preference elicitation, in which                    choices are presented and the answers are used to define the function. Normalized                    utilities are between 0 and 1, but there is no absolute scale. We can assess the                    utility of any lottery by choosing between it and [p, U*; 1-p; U^] where U* is the                    best possible utility and U^ the worst, and we adjust p until we get indifference.                    The value of a statistical life is estimated for the utility of a human. Money                    is a good example since more money is monotonically preferred, but the utility                    function here has diminishing returns, meaning it is logarithmic. We can have                    risk-averse (positive insurance premium) and risk-seeking (negative) sections                    of the utility function for behavior. Oftentimes, we have to choose the action                    to maximize ESTIMATED expected utility with an unbiased estimator. The problem                    with this is that since we always maximize we favor positive errors and generate                    bias. Decision theory is normative saying how agents should act but descriptive                    theory states how they do act. The certainty affect says people are strongly                    attracted to certain gains. People also have ambiguity aversion. The anchoring                    effect is one that frames estimates by making relative judgements rather than absolute.\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n With sequential decision problems, the utility function depends on an environment                   history rather than a single state. For these we assume each transition has a bounded                   reward. We cannot have a fixed action sequence solution with a stochastic environemnt,                   so our solution must be a policy. Optimal policies have the highest expected utility. To                   evaluate utility we must consider the time horizon, and a policy that depends on time left                   is called nonstationary. To calculate utility of state sequences we use additive discounted                   rewards (bounds infinite sequences too). A policy guaranteed to reach a terminal state is                   called proper. Then, we can get the utility of a policy given a starting state. The optimal                   policy takes the argmax of the utilities with respect to all policies in a given state. Thus,                   we can derive the bellman equation which defines the utility of a state by the utilies of its                   neighbors with an optimal policy on them. The Q value of the expected utility of a given action                   in a given state, and the max Q value by action is the utility of a state. Shaping theorem says                   we can add any y*f(s')-f(s) to the reward and get a still valid reward function. We can represent                   small MDPs with Q value tables, but larger ones need dynamic decision networks. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value iteration utilizes the Bellman Equations to solve MDPs. We initialize arbitrary values                    for each state, and then perform bellman updates until we converge. This convergence is true                    due to contraction, since the values always geet closer together. Policy iteration involves                    alternating beetween evaluation in which we calculate the utility of each state given the                    current policy and then improvement where a new policy is calculated based on these updates                    utilities. Asynchronous policy iteration updates only a certain subset of states. We can also                    use linear programming which the utilities as variables. Online algorithms like expectimax                    essentially compute at each step instead of precomputing. \n\n## Module 8 Lecture Notes\n QALY is a quality adjusted life year. \n\n## Module 8 Definitions\n* **Micromort** - one in a million chance of death\n* **Certainty equivalent** - value will accept in lieu of a lottery\n* **Insurance premium** - difference between EMV and certianty equivalent\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 =  \"\"\" Each of the n levers has an unknown proobability distribution of winnings \\\n",
        "                   and we must play by selecting levers. Do we explore or exploit? A common \\\n",
        "                   example is a one armed bandit that gives reward R0, R1, R2, ... but costs \\\n",
        "                   y on eahc pull. Our stopping time is the number of times we should pull. The \\\n",
        "                   value of pulling the reward arm T times over the value of the constant arm \\\n",
        "                   T times is the Gittins index. We can use UCB to establish a confidence interval \\\n",
        "                   for the value of an arm and choose the arm with the highest upper bound. Thomson \\\n",
        "                   sampling chooses an arm randomly accoring to the probability that it is optimal. \\\n",
        "                   A BSP is a generalization in which each arm is a full MDP. An optimal policy in \\\n",
        "                   a given arm unaffected by the cost of giving up another arm is called dominating.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" RL is where an agent interacts with the world and periodically gets rewards. Model \\\n",
        "                   based RL is an approach in which an agent used a transition model of the environment \\\n",
        "                   to help make decisions. Model free RL has Q learning where an agent learns a Q function \\\n",
        "                   by moving through the environment or policy search where the agent learns a policy. \"\"\"\n",
        "chapter22_2 =  \"\"\" Passive learning agents are when we try to learn a utility function from a policy. Direct \\\n",
        "                   utility estimation involves keeping a running average of the reward for each state in a \\\n",
        "                   table and then seeing that with infinite trials it will converge. ADP learns the transition \\\n",
        "                   model and then uses DP to solve the MDP. Temporal difference learning applies an update \\\n",
        "                   U(s) = U(s) + a[R + yU(s') - U(s)] where a is the learning rate. \"\"\"\n",
        "chapter22_3 =  \"\"\" In active RL we decide which actions to take. First, we learn a model of the environment. \\\n",
        "                   In order the balance the tradeoff between explore and exploit, we use a GLIE scheme. An \\\n",
        "                   example of this is choosing a random action at time step t with probability 1/t. Alternavitely, \\\n",
        "                   we can use an exploration function that causes a random action to be taken if it has not \\\n",
        "                   been tried enough. Bayesian RL uses probability to estimate what the true model may be to \\\n",
        "                   avoid catastrophe. Robust control theory uses a set of possible models and returns the best \\\n",
        "                   mode in the worst case action for each. Q learning method avoid the neeed for the model \\\n",
        "                   by learning their q function. Thus, by using the TD update to the q function we derive a \\\n",
        "                   model free update. SARSA is similar to Q learning but updates by the action taken not just \\\n",
        "                   the best hypothetical action, penalizing bad exploration.\"\"\"\n",
        "chapter22_4 =  \"\"\" In order to approximate some of these methods, we can update parameters after each trial. \\\n",
        "                   For direct utility estimation, we use the Widrow Hoff rule and update the parameters of our \\\n",
        "                   supervised learning problem from states to rewards. For TD and Q learning, we can similarly \\\n",
        "                   update the parameters of our utility function with the same update rules. Catastrophic forgetting \\\n",
        "                   is when because gooo behavior is learned, any deviation from it is not learned so catastrophic \\\n",
        "                   actions can be taken. Experience replay solves this by making sure that these deviations are \\\n",
        "                   relived. Deep RL uses nonlinear function approximators like neural networks for their utility \\\n",
        "                   approximations. Reward shaping involves supplying an agent with intermediate rewards for progress. \\\n",
        "                   Hierarchical RL breaks down action sequences into smaller pieces until learnable.\"\"\"\n",
        "chapter22_5 =  \"\"\" Policy search involves changing a policy as long as performance improves. These methods \\\n",
        "                   often use stochastic policy representations which specify probabilities of taking actions in \\\n",
        "                   certain states. Then we can approximate the gradient of a policy and use REINFORCE \\\n",
        "                   to adjust the policy and optimize it. However, too compare two different policies \\\n",
        "                   the best way is correlation sampling, generating samples in advance and then playing the \\\n",
        "                   same way.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 63,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 891
        },
        "cellView": "form",
        "outputId": "87538a88-62a8-4401-e6a0-60ede5b0772f"
      },
      "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": 64,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Each of the n levers has an unknown proobability distribution of winnings                    and we must play by selecting levers. Do we explore or exploit? A common                    example is a one armed bandit that gives reward R0, R1, R2, ... but costs                    y on eahc pull. Our stopping time is the number of times we should pull. The                    value of pulling the reward arm T times over the value of the constant arm                    T times is the Gittins index. We can use UCB to establish a confidence interval                    for the value of an arm and choose the arm with the highest upper bound. Thomson                    sampling chooses an arm randomly accoring to the probability that it is optimal.                    A BSP is a generalization in which each arm is a full MDP. An optimal policy in                    a given arm unaffected by the cost of giving up another arm is called dominating.\n\n## AIMA Chapter 22.1 Learning from Rewards\n RL is where an agent interacts with the world and periodically gets rewards. Model                    based RL is an approach in which an agent used a transition model of the environment                    to help make decisions. Model free RL has Q learning where an agent learns a Q function                    by moving through the environment or policy search where the agent learns a policy. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Passive learning agents are when we try to learn a utility function from a policy. Direct                    utility estimation involves keeping a running average of the reward for each state in a                    table and then seeing that with infinite trials it will converge. ADP learns the transition                    model and then uses DP to solve the MDP. Temporal difference learning applies an update                    U(s) = U(s) + a[R + yU(s') - U(s)] where a is the learning rate. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n In active RL we decide which actions to take. First, we learn a model of the environment.                    In order the balance the tradeoff between explore and exploit, we use a GLIE scheme. An                    example of this is choosing a random action at time step t with probability 1/t. Alternavitely,                    we can use an exploration function that causes a random action to be taken if it has not                    been tried enough. Bayesian RL uses probability to estimate what the true model may be to                    avoid catastrophe. Robust control theory uses a set of possible models and returns the best                    mode in the worst case action for each. Q learning method avoid the neeed for the model                    by learning their q function. Thus, by using the TD update to the q function we derive a                    model free update. SARSA is similar to Q learning but updates by the action taken not just                    the best hypothetical action, penalizing bad exploration.\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n In order to approximate some of these methods, we can update parameters after each trial.                    For direct utility estimation, we use the Widrow Hoff rule and update the parameters of our                    supervised learning problem from states to rewards. For TD and Q learning, we can similarly                    update the parameters of our utility function with the same update rules. Catastrophic forgetting                    is when because gooo behavior is learned, any deviation from it is not learned so catastrophic                    actions can be taken. Experience replay solves this by making sure that these deviations are                    relived. Deep RL uses nonlinear function approximators like neural networks for their utility                    approximations. Reward shaping involves supplying an agent with intermediate rewards for progress.                    Hierarchical RL breaks down action sequences into smaller pieces until learnable.\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\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 = \"\"\" It is hard to quantify uncertainty due to laziness \\\n",
        "                  meaning it is too much work to list all exceptions, \\\n",
        "                  theoretical ignorance meaning there is no complete \\\n",
        "                  theory, or practical ignorance. Decision theory is \\\n",
        "                  probability theory and utility theory combined. \"\"\"\n",
        "chapter12_2 = \"\"\" Formal language of probability. Unconditional or \\\n",
        "                  prior probabilities mean there are no other givens. \\\n",
        "                  Posterior probability happens with givens. \"\"\"\n",
        "chapter12_3 = \"\"\" Probabalistic infernce is the computation of \\\n",
        "                  posterior probabilitiies given evidencee. \"\"\"\n",
        "chapter12_4 = \"\"\" Independence means P(a|b) = P(a). \"\"\"\n",
        "chapter12_5 = \"\"\" Bayes rule states P(A|B) = P(B|A)P(B)/P(A). \\\n",
        "                  This allows us to switch between the causal and \\\n",
        "                  diagnostic direction. Conditional independence \\\n",
        "                  is P(X,Y|Z) = P(X|Z)P(Y|Z) and P(X|Y,Z) = P(X|Z). \\\n",
        "                  \"\"\"\n",
        "chapter12_6 = \"\"\" Naive bayes models say P(Cause, e) = \\\n",
        "                  P(Cause) * PROD P(e | Cause). These tend to \\\n",
        "                  be overconfident due to the assumption of \\\n",
        "                  independnce of effect variables. \"\"\"\n",
        "chapter12_7 = \"\"\" Wumpus world derivation with probabilities. \"\"\"\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 = \"\"\" We can estimate the probability of the next word using counts \\\n",
        "                     from a corpus.\"\"\"\n",
        "SLP_chapter3_2 = \"\"\" End-to-end eval of a language model is called extrinsic evaluation. \\ \n",
        "                     Instrinsic eval is quality independent of application. Perplexity is the \\\n",
        "                     inverse probability of a test set. Lower perplexity is better. \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Sampling from a language model is generating sentences according \\\n",
        "                     to model liklihood. \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" One problem is that if the probability of any word is 0, the probability \\\n",
        "                     of the test set is 0, meaning infinite perplexity. We can add a <UNK> for \\\n",
        "                     OOV words. When we dont have a vocab, we can say that <UNK> is all words \\\n",
        "                     that appear less than n times. \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Laplace smoothing adds 1 to all n-gram counts. K-smoothing is a generalization \\\n",
        "                     where we add k instead of 1. In backoff we use n-grams but if insufficient \\\n",
        "                     we use n-1 grams. In interpolation, we mix probability estimates from \\\n",
        "                     all n-gram estimators. We can also do a weighted average of these, or Katz \\\n",
        "                     backoff with discounting.\"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Stupid backoff sees if a n-gram has zero count we go to n-1 and discount.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 65,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1200
        },
        "cellView": "form",
        "outputId": "d979dedc-a686-4f2a-a5ee-6294cf51534c"
      },
      "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": 66,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n It is hard to quantify uncertainty due to laziness                   meaning it is too much work to list all exceptions,                   theoretical ignorance meaning there is no complete                   theory, or practical ignorance. Decision theory is                   probability theory and utility theory combined. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Formal language of probability. Unconditional or                   prior probabilities mean there are no other givens.                   Posterior probability happens with givens. \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Probabalistic infernce is the computation of                   posterior probabilitiies given evidencee. \n\n## AIMA Chapter 12.4 Independence\n Independence means P(a|b) = P(a). \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes rule states P(A|B) = P(B|A)P(B)/P(A).                   This allows us to switch between the causal and                   diagnostic direction. Conditional independence                   is P(X,Y|Z) = P(X|Z)P(Y|Z) and P(X|Y,Z) = P(X|Z).                   \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Naive bayes models say P(Cause, e) =                   P(Cause) * PROD P(e | Cause). These tend to                   be overconfident due to the assumption of                   independnce of effect variables. \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Wumpus world derivation with probabilities. \n\n## SLP Chapter 3.1 N-Grams\n We can estimate the probability of the next word using counts                      from a corpus.\n\n## SLP Chapter 3.2 Evaluating Language Models\n End-to-end eval of a language model is called extrinsic evaluation. \\ \n                     Instrinsic eval is quality independent of application. Perplexity is the                      inverse probability of a test set. Lower perplexity is better. \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Sampling from a language model is generating sentences according                      to model liklihood. \n\n## SLP Chapter 3.4 Generalization and Zeros\n One problem is that if the probability of any word is 0, the probability                      of the test set is 0, meaning infinite perplexity. We can add a <UNK> for                      OOV words. When we dont have a vocab, we can say that <UNK> is all words                      that appear less than n times. \n\n## SLP Chapter 3.5 Smoothing\n Laplace smoothing adds 1 to all n-gram counts. K-smoothing is a generalization                      where we add k instead of 1. In backoff we use n-grams but if insufficient                      we use n-1 grams. In interpolation, we mix probability estimates from                      all n-gram estimators. We can also do a weighted average of these, or Katz                      backoff with discounting.\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Stupid backoff sees if a n-gram has zero count we go to n-1 and discount.\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Term** - your definition here\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 = \"\"\" Bayesian networks are digraphs where each node \\ \n",
        "                  corresponds to a random variable that has \\\n",
        "                  probability info that quantifies the effects of the \\\n",
        "                  parents on the node. \"\"\"\n",
        "chapter13_2 = \"\"\" The syntax of the Bayes net is a DAG. It is a \\\n",
        "                  correct representation of the domain iff each node \\\n",
        "                  is conditionally independent of all predecessors in \\\n",
        "                  a topological ordering given its parents. Context-specific \\\n",
        "                  independence is when a variable is conditionally independent \\\n",
        "                  of some parents given specific values of others. To handle \\\n",
        "                  continuous variables we can discretize them. A network with \\\n",
        "                  both types is calledd a hybrid Bayesian network. \"\"\"\n",
        "chapter13_3 = \"\"\" Enumeration ask is an algorithm that evaluates expression \\\n",
        "                  trees using recursive techniques. With variable elimination \\\n",
        "                  we can factorize this approach using pointwise products. \\\n",
        "                  If the network is a tree the time complexity of exact \\\n",
        "                  inference is linear. Clustering nodes together can turn a \\\n",
        "                  bayes net into a polytree structure.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 67,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 515
        },
        "cellView": "form",
        "outputId": "0dbf2d0b-fd6b-4d34-ef96-05a3f1e1136f"
      },
      "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": 68,
      "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 Bayesian networks are digraphs where each node \\ \n                  corresponds to a random variable that has                   probability info that quantifies the effects of the                   parents on the node. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The syntax of the Bayes net is a DAG. It is a                   correct representation of the domain iff each node                   is conditionally independent of all predecessors in                   a topological ordering given its parents. Context-specific                   independence is when a variable is conditionally independent                   of some parents given specific values of others. To handle                   continuous variables we can discretize them. A network with                   both types is calledd a hybrid Bayesian network. \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Enumeration ask is an algorithm that evaluates expression                   trees using recursive techniques. With variable elimination                   we can factorize this approach using pointwise products.                   If the network is a tree the time complexity of exact                   inference is linear. Clustering nodes together can turn a                   bayes net into a polytree structure.\n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\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 = \"\"\" Any compoenent of an agent can be improved with ML.\"\"\"\n",
        "chapter19_2 = \"\"\" Supervised learning gives data and labels and \\\n",
        "                  learns patterns between them. We must draw a \\\n",
        "                  function from a hypothesis space to approximate \\\n",
        "                  f(X) = y. y is the ground truth. We evaluate h \\\n",
        "                  by using a test set. A hypothesis is consistent if \\\n",
        "                  h(x) = f(x) for x in train set. Underfitting is when \\\n",
        "                  no pattern is found but overfitting is when it fits \\\n",
        "                  too closely on training and does poorly on testing. \\\n",
        "                  In Bayes terms, h* = argmax_h P(data|h)P(h).\"\"\"\n",
        "chapter19_3 = \"\"\" B(x) is the entropy of a rv with \\\n",
        "                  true with probability x. Then, if p is the number of positive exmaples \\\n",
        "                  and n negative, the entropy of the output variance is B(p / (p+n)). \\\n",
        "                  Then, the gain of attribute A is B(A) - Remainder(A) where the remainder \\\n",
        "                  is sum_E |E|/|A| B(E) where E is the subset of the training set. Gain \\\n",
        "                  measures importance. \\\n",
        "                  \\\n",
        "                  Pruning for decision trees combats overfitting where we replace test \\\n",
        "                  nodes as leaves if they are irrelevant (Gain = 0). We can use significance \\\n",
        "                  testing to see when a gain is important. We can deal with continuous values \\\n",
        "                  using a split point and doing an inequality test on the value of an attribute. \\\n",
        "                  Splitting can also be done through equalities rather than inequality testing. \"\"\"\n",
        "chapter19_4 = \"\"\" In ML, you need a train set to train candidtae models, a validation set to \\\n",
        "                  choose the best model, and a test set to do a final unbiased eval of the model. \\\n",
        "                  K-fold cross validation allows us to reuse data across training and validation but \\\n",
        "                  not at the same time. We can do cross validation on different size models \\\n",
        "                  to select which is best. A model that fits all training data has interpolated the data, \\\n",
        "                  and this starts to approach overfitting. Instead of minimizing error, we often \\\n",
        "                  minimize a loss function that is more in line with utility. \\\n",
        "                  \\\n",
        "                  A learning problem is realizable if the hypothesis space actually contains the true \\\n",
        "                  function f. Regularization is the process of explicity penalizinig complex hypotheses, \\\n",
        "                  and we can call cost the empirical loss plus some factor time the complexity. Both \\\n",
        "                  of these can be measured in bits. Hyperparameter tuning is often most feasible with \\\n",
        "                  hand tuning. If there are only a few, then grid search can even be attempted. For \\\n",
        "                  large amounts of hyperparameters, random sampling can be tried as well. Bayesian \\\n",
        "                  optimization makes the task of tuning hyperparameters an ML task itself, while \\\n",
        "                  population based training uses random search in generations.\"\"\"\n",
        "chapter19_5 = \"\"\" Any hypothesis that is consistent with a sufficiently large set of training examples must be \\\n",
        "                  probably approximately correct. For PAC theorems with booolean functions, the error is the \\\n",
        "                  probability of misclassification. The number of required examples for the hypothesis to be \\\n",
        "                  approximately correct is the sample complexity of the learning algorithm. \\\n",
        "                  \\\n",
        "                  PAC learning can also be applied to decision lists, which are a series of tests, \\\n",
        "                  each of which iss a conjunction of literals. k-DL is used for a decision list \\\n",
        "                  with up to k conjunctions. The number of possible hypotheses is 2^O(n^klog(n^k)) \\\n",
        "                  with n attributes. To learn a list we append together tests that satisfy \\\n",
        "                  some disjoing subsets of the training data until empty when we get no.\"\"\"\n",
        "chapter19_6 = \"\"\" Linear regression involves fitting a line by minimizing empircal loss. We \\\n",
        "                  do this by setting the partial derivatives of the loss to 0 and solving \\\n",
        "                  for the weights. Instead of having to solve derivatives, we can use gradient \\\n",
        "                  descent to update the weights by some learning rate. We can do this example \\\n",
        "                  by example or use batches of example. Stochastic gradient descent randomly \\\n",
        "                  selects a small number of training examples called minibatches. This can be \\\n",
        "                  extended to multiple variables with an n element vector and taking gradients \\\n",
        "                  similarly. It is common to regularize these to avoid overfitting. L1 regularization \\\n",
        "                  often sets many weights to 0, creating a sparse model. Linear regression can also \\\n",
        "                  be used for classificaiton treating the line as a decision line. This uses a \\\n",
        "                  perceptron learning rule. Oftentime, a logistic regression performs better. \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Bag of words is an unordered set of words without position \\\n",
        "                     only frequency. In Naive Bayes we classify by choosing the max \\\n",
        "                     probability class. \"\"\"\n",
        "slp_chapter4_2 = \"\"\" In order to train this classifier we simply use counts as probabilities. \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Worked example. \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Binary NB only uses whether a word occurs in a doc or not. \\\n",
        "                     Can prepend NOT for negation to create new words.\"\"\"\n",
        "slp_chapter4_5 = \"\"\" Naive Bayes can also be used for spam dtection. \"\"\"\n",
        "slp_chapter4_6 = \"\"\" We can extrapolate word probabilities in NB to sentence \\\n",
        "                     probabilities. \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Human defined labels for evaluation are called gold labels. \\\n",
        "                     Accuracy is a bad metric for biased classes, and we use precision \\\n",
        "                     ratio of true positives to labeled positives or recall ratio of \\\n",
        "                     true positives to true positives plus false negatives. F-measure \\\n",
        "                     combines these. \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Test sets vs dev sets vs train sets. \"\"\"\n",
        "slp_chapter4_9 = \"\"\" We can test whether the effect size is statistically significant \\\n",
        "                     to see if a classifier is better than another. Parametric tests \\\n",
        "                     assume the statistic is normal or otherwise distributed for our p value. \\\n",
        "                     Bootstrap testing draws smaller sample from a larger one and creates \\\n",
        "                     many virtual test sets. \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Representational harms demean a social group. These can occur due \\\n",
        "                      to biases in data or biases in human labeling. A model card \\\n",
        "                      gives information about a model. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Decision trees map a vector of attribute values \\\n",
        "                  to a single output value. When learning a decision \\\n",
        "                  tree, we test the most important attribute first \\\n",
        "                  and then solve smaller subproblems. We measure \\\n",
        "                  importance using entropy. Less entropy means more \\\n",
        "                  information, and entropy is the sum over all values \\\n",
        "                  of probabilities times the negative log_2 of \\\n",
        "                  probabilities.  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"bias\" : \"tendency of predictive hypothesis to deviate from \\\n",
        "          the expected value over different training sets\",    \n",
        "\"variance\" : \"the amount of change in the hypothesis from fluctuation in training data\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 69,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1817
        },
        "cellView": "form",
        "outputId": "134a3ed2-bb6c-4d4a-eef6-d1fcbe72fbc1"
      },
      "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": 70,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Any compoenent of an agent can be improved with ML.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Supervised learning gives data and labels and                   learns patterns between them. We must draw a                   function from a hypothesis space to approximate                   f(X) = y. y is the ground truth. We evaluate h                   by using a test set. A hypothesis is consistent if                   h(x) = f(x) for x in train set. Underfitting is when                   no pattern is found but overfitting is when it fits                   too closely on training and does poorly on testing.                   In Bayes terms, h* = argmax_h P(data|h)P(h).\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n B(x) is the entropy of a rv with                   true with probability x. Then, if p is the number of positive exmaples                   and n negative, the entropy of the output variance is B(p / (p+n)).                   Then, the gain of attribute A is B(A) - Remainder(A) where the remainder                   is sum_E |E|/|A| B(E) where E is the subset of the training set. Gain                   measures importance.                                     Pruning for decision trees combats overfitting where we replace test                   nodes as leaves if they are irrelevant (Gain = 0). We can use significance                   testing to see when a gain is important. We can deal with continuous values                   using a split point and doing an inequality test on the value of an attribute.                   Splitting can also be done through equalities rather than inequality testing. \n\n## AIMA Chapter 5.5 Stochastic Games\n In ML, you need a train set to train candidtae models, a validation set to                   choose the best model, and a test set to do a final unbiased eval of the model.                   K-fold cross validation allows us to reuse data across training and validation but                   not at the same time. We can do cross validation on different size models                   to select which is best. A model that fits all training data has interpolated the data,                   and this starts to approach overfitting. Instead of minimizing error, we often                   minimize a loss function that is more in line with utility.                                     A learning problem is realizable if the hypothesis space actually contains the true                   function f. Regularization is the process of explicity penalizinig complex hypotheses,                   and we can call cost the empirical loss plus some factor time the complexity. Both                   of these can be measured in bits. Hyperparameter tuning is often most feasible with                   hand tuning. If there are only a few, then grid search can even be attempted. For                   large amounts of hyperparameters, random sampling can be tried as well. Bayesian                   optimization makes the task of tuning hyperparameters an ML task itself, while                   population based training uses random search in generations.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Any hypothesis that is consistent with a sufficiently large set of training examples must be                   probably approximately correct. For PAC theorems with booolean functions, the error is the                   probability of misclassification. The number of required examples for the hypothesis to be                   approximately correct is the sample complexity of the learning algorithm.                                     PAC learning can also be applied to decision lists, which are a series of tests,                   each of which iss a conjunction of literals. k-DL is used for a decision list                   with up to k conjunctions. The number of possible hypotheses is 2^O(n^klog(n^k))                   with n attributes. To learn a list we append together tests that satisfy                   some disjoing subsets of the training data until empty when we get no.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Linear regression involves fitting a line by minimizing empircal loss. We                   do this by setting the partial derivatives of the loss to 0 and solving                   for the weights. Instead of having to solve derivatives, we can use gradient                   descent to update the weights by some learning rate. We can do this example                   by example or use batches of example. Stochastic gradient descent randomly                   selects a small number of training examples called minibatches. This can be                   extended to multiple variables with an n element vector and taking gradients                   similarly. It is common to regularize these to avoid overfitting. L1 regularization                   often sets many weights to 0, creating a sparse model. Linear regression can also                   be used for classificaiton treating the line as a decision line. This uses a                   perceptron learning rule. Oftentime, a logistic regression performs better. \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Bag of words is an unordered set of words without position                      only frequency. In Naive Bayes we classify by choosing the max                      probability class. \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n In order to train this classifier we simply use counts as probabilities. \n\n## SLP Chapter 4.3 Worked Example\n Worked example. \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Binary NB only uses whether a word occurs in a doc or not.                      Can prepend NOT for negation to create new words.\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Naive Bayes can also be used for spam dtection. \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n We can extrapolate word probabilities in NB to sentence                      probabilities. \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Human defined labels for evaluation are called gold labels.                      Accuracy is a bad metric for biased classes, and we use precision                      ratio of true positives to labeled positives or recall ratio of                      true positives to true positives plus false negatives. F-measure                      combines these. \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Test sets vs dev sets vs train sets. \n\n## SLP Chapter 4.9 Statistical Significance Testing\n We can test whether the effect size is statistically significant                      to see if a classifier is better than another. Parametric tests                      assume the statistic is normal or otherwise distributed for our p value.                      Bootstrap testing draws smaller sample from a larger one and creates                      many virtual test sets. \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Representational harms demean a social group. These can occur due                       to biases in data or biases in human labeling. A model card                       gives information about a model. \n\n## Module 12 Lecture Notes\n Decision trees map a vector of attribute values                   to a single output value. When learning a decision                   tree, we test the most important attribute first                   and then solve smaller subproblems. We measure                   importance using entropy. Less entropy means more                   information, and entropy is the sum over all values                   of probabilities times the negative log_2 of                   probabilities.  \n\n## Module 12 Definitions\n* **Bias** - tendency of predictive hypothesis to deviate from           the expected value over different training sets\n* **Variance** - the amount of change in the hypothesis from fluctuation in training data\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 = \"\"\" The sigmoid function maps a real value between 0 and 1. Our \\\n",
        "                     decision boundary we say if P(Y=1|x) = sigmoid(w*x+b) is more than .5  we say \\\n",
        "                     yes else no where .5 is the decision boundary.\"\"\"\n",
        "slp_chapter5_2 = \"\"\" We learn the weights and bias through supervised classiciation in which \\\n",
        "                     we know the label for each observatiion x. Then, we measure loss of predictions \\\n",
        "                     and update parameters. \"\"\"\n",
        "slp_chapter5_3 = \"\"\" The cross entropy loss function prefers the correct classs of labels to be more \\\n",
        "                     likely. p(y|x) = y_hat ^ y * (1 - y_hat) ^ (1-y). We can also do logs, and since \\\n",
        "                     we want to maximize this liklihood we negate it for loss.\"\"\"\n",
        "slp_chapter5_4 = \"\"\" With gradient descent we want the weights that minimize the loss function. We \\\n",
        "                     find the gradient of the loss d/dw and then move the weights by negative that \\\n",
        "                     times a learning rate. \"\"\"\n",
        "slp_chapter5_5 = \"\"\" In order to avoid overfitting the weights, we can regularize the training data. \\\n",
        "                     Regularization subtracts a term proprotional to weight size, penalizing large \\\n",
        "                     weights. L2 does squares while L1 (lasso) absoslute value. \"\"\"\n",
        "slp_chapter5_6 = \"\"\" For multinomial regression we can use softmax, a generalization of sigmoid \\\n",
        "                     that takes exp(xi) / sum exp(xi). We need separate weight vectors for each class \\\n",
        "                     CE loss is the sum of the logs of each class weighted by their prob given the \\\n",
        "                     input. \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" The sigmoid activation can be replaced by tanh or ReLU, each \\\n",
        "                     having their own advanategs with outliers and derivatives. \"\"\"\n",
        "slp_chapter7_2 = \"\"\" A perceptron fires based on whether w*x+b >0 or not. XOR \\\n",
        "                     requires more than one perceptron as it is not linearly separable. \\\n",
        "                     Two layers change the space to make it linearly separable. \"\"\"\n",
        "slp_chapter7_3 = \"\"\" The feedforward network is multilayer with no cycles and passes \\\n",
        "                     outputs forward. It computes using 2D matrices of weights by layer. \\\n",
        "                     If the hidden layer activations were linear it could just be written \\\n",
        "                     as a one layer network.\"\"\"\n",
        "slp_chapter7_4 = \"\"\" We can use these networks for NLP by passing in a vector of \\\n",
        "                     hand designed features. We cana also learn features by using concatenated \\\n",
        "                     embeddings of the n words.\"\"\"\n",
        "slp_chapter7_5 = \"\"\" Neural language models hold longer histories than n-gram models. These \\\n",
        "                     also learn embeddings instead of true words so they do better with unseen data. \\ \n",
        "                     For this, we create one hot vectors given indices and then multiply them \\\n",
        "                     by embedding matrices. Then we pass this result to hidden layers and apply \\\n",
        "                     softmax. \"\"\"\n",
        "slp_chapter7_6 = \"\"\" We train these neural nets by using loss functions and using gradient descent \\\n",
        "                     as before, but this time we use backpropagation to update weights over intermediate \\\n",
        "                     layers in the network. We can represent networks as computation graphs \\\n",
        "                     and update by partial derivatives of the activation functions.  \"\"\"\n",
        "slp_chapter7_7 = \"\"\" This techniqu above can be applied to a neural language model to learn \\\n",
        "                     embeddings and hidden layer weight. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 71,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1304
        },
        "cellView": "form",
        "outputId": "de18fd4a-3825-4752-f6b9-bb198c2e59e6"
      },
      "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": 72,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n The sigmoid function maps a real value between 0 and 1. Our                      decision boundary we say if P(Y=1|x) = sigmoid(w*x+b) is more than .5  we say                      yes else no where .5 is the decision boundary.\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n We learn the weights and bias through supervised classiciation in which                      we know the label for each observatiion x. Then, we measure loss of predictions                      and update parameters. \n\n## SLP Chapter 5.3 The cross-entropy loss function\n The cross entropy loss function prefers the correct classs of labels to be more                      likely. p(y|x) = y_hat ^ y * (1 - y_hat) ^ (1-y). We can also do logs, and since                      we want to maximize this liklihood we negate it for loss.\n\n## SLP Chapter 5.4 Gradient Descent\n With gradient descent we want the weights that minimize the loss function. We                      find the gradient of the loss d/dw and then move the weights by negative that                      times a learning rate. \n\n## SLP Chapter 5.5 Regularization\n In order to avoid overfitting the weights, we can regularize the training data.                      Regularization subtracts a term proprotional to weight size, penalizing large                      weights. L2 does squares while L1 (lasso) absoslute value. \n\n## SLP Chapter 5.6 Multinomial logistic regression\n For multinomial regression we can use softmax, a generalization of sigmoid                      that takes exp(xi) / sum exp(xi). We need separate weight vectors for each class                      CE loss is the sum of the logs of each class weighted by their prob given the                      input. \n\n## SLP Chapter 7.1 Units\n The sigmoid activation can be replaced by tanh or ReLU, each                      having their own advanategs with outliers and derivatives. \n\n## SLP Chapter 7.2 The XOR problem\n A perceptron fires based on whether w*x+b >0 or not. XOR                      requires more than one perceptron as it is not linearly separable.                      Two layers change the space to make it linearly separable. \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n The feedforward network is multilayer with no cycles and passes                      outputs forward. It computes using 2D matrices of weights by layer.                      If the hidden layer activations were linear it could just be written                      as a one layer network.\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n We can use these networks for NLP by passing in a vector of                      hand designed features. We cana also learn features by using concatenated                      embeddings of the n words.\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Neural language models hold longer histories than n-gram models. These                      also learn embeddings instead of true words so they do better with unseen data. \\ \n                     For this, we create one hot vectors given indices and then multiply them                      by embedding matrices. Then we pass this result to hidden layers and apply                      softmax. \n\n## SLP Chapter 7.6 Training Neural Nets\n We train these neural nets by using loss functions and using gradient descent                      as before, but this time we use backpropagation to update weights over intermediate                      layers in the network. We can represent networks as computation graphs                      and update by partial derivatives of the activation functions.  \n\n## SLP Chapter 7.7 Training the neural language model\n This techniqu above can be applied to a neural language model to learn                      embeddings and hidden layer weight. \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\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 = \"\"\" Probabalistic language models predict the next word given \\ \n",
        "                     some preceding context. We assign conditional probabilities \\\n",
        "                     to every possible next word. We use perplexity to evaluate. \"\"\"\n",
        "slp_chapter9_2 = \"\"\" We use RNNs as networks that have cycles and these build the \\\n",
        "                     basis for future LSTMs. With these, we can compute hidden layers \\\n",
        "                     given the value of the hidden layer previously, giving a form of \\\n",
        "                     memory. This is the same as feed forward except we add Uh_t-1 to \\\n",
        "                     Wx_t when evaluating the hidden layer. To train these, we \\\n",
        "                     conduct backprop through time. \"\"\"\n",
        "slp_chapter9_3 = \"\"\" RNNs don't have the limit problems of n-gram models, and we still \\\n",
        "                     pass in a series of word embeddings each represented as a one-hot \\\n",
        "                     vector of size |V| x 1. Instead of giving predictions to train \\\n",
        "                     the RNN we always give it the correct history, called teacher forcing.\"\"\"\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 = \"\"\" We can group meanings of words by semantics. Lemma is the base \\\n",
        "                     of a word and every variation is called a sense. We can also \\\n",
        "                     group words by relatedness or connotation. \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Vector semantics is how we can represent word meaning in NLP. \\\n",
        "                     Vectors for representing these words are embeddings. \"\"\"\n",
        "slp_chapter6_3 = \"\"\" We can use term-document matrices to represent frequencies \\\n",
        "                     of words on documents. We can graph these as points in n \\\n",
        "                     dimensional space. Information retrival is the task of \\\n",
        "                     finding a document best matching a query. We can also create \\\n",
        "                     term term matrices that show how often terms appear together \\\n",
        "                     in some context. \"\"\"\n",
        "slp_chapter6_4 = \"\"\" To measure similarity of words we measure their dot product. \\\n",
        "                     We first normalize the vectors and then take the dot product \\\n",
        "                     or take the dot product and divide by the norm of each.  \"\"\"\n",
        "slp_chapter6_8 = \"\"\" SGNS is a method for computing embeddings in word2vec. \\\n",
        "                     We can take a sigmoid of the dot product of a target \\\n",
        "                     word paired with a candidate and in skip gram we can multiply \\\n",
        "                     these together for other context words. There are other \\\n",
        "                     types of static embeddings as well. \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Embeddings have the semantic property of depending on \\\n",
        "                      window size. Two wordss have first order co-occurence if they \\\n",
        "                      are typically near each other. Second order if they have similar \\\n",
        "                      neighbors. We can also use embeddings to see how meaning changes \\\n",
        "                      over time. \"\"\"\n",
        "slp_chapter6_11 = \"\"\" These embeddings also reproduce biases that were latent in the \\ \n",
        "                      text. This could create an allocational harm, giving different \\\n",
        "                      resources to different groups. These actually amplify bias. \\\n",
        "                      There are techniques of debiasing that can be used. \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Vector models are evaluated using similarity scores \\\n",
        "                      assigned by humans. There exist datasets with these values. \\\n",
        "                      Additionally, similarity tasks and analogy tasks can be used. \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 73,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1153
        },
        "outputId": "869ac57b-9b4c-414f-9ff7-0497531987f3"
      },
      "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": 74,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Probabalistic language models predict the next word given \\ \n                     some preceding context. We assign conditional probabilities                      to every possible next word. We use perplexity to evaluate. \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n We use RNNs as networks that have cycles and these build the                      basis for future LSTMs. With these, we can compute hidden layers                      given the value of the hidden layer previously, giving a form of                      memory. This is the same as feed forward except we add Uh_t-1 to                      Wx_t when evaluating the hidden layer. To train these, we                      conduct backprop through time. \n\n## SLP Chapter 9.3 RNNs as Language Models\n RNNs don't have the limit problems of n-gram models, and we still                      pass in a series of word embeddings each represented as a one-hot                      vector of size |V| x 1. Instead of giving predictions to train                      the RNN we always give it the correct history, called teacher forcing.\n\n## SLP Chapter 6.1 Lexical Semantics\n We can group meanings of words by semantics. Lemma is the base                      of a word and every variation is called a sense. We can also                      group words by relatedness or connotation. \n\n## SLP Chapter 6.2 Vector Semantics\n Vector semantics is how we can represent word meaning in NLP.                      Vectors for representing these words are embeddings. \n\n## SLP Chapter 6.3 Words and Vectors\n We can use term-document matrices to represent frequencies                      of words on documents. We can graph these as points in n                      dimensional space. Information retrival is the task of                      finding a document best matching a query. We can also create                      term term matrices that show how often terms appear together                      in some context. \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n To measure similarity of words we measure their dot product.                      We first normalize the vectors and then take the dot product                      or take the dot product and divide by the norm of each.  \n\n## SLP Chapter 6.8 Word2vec\n SGNS is a method for computing embeddings in word2vec.                      We can take a sigmoid of the dot product of a target                      word paired with a candidate and in skip gram we can multiply                      these together for other context words. There are other                      types of static embeddings as well. \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Embeddings have the semantic property of depending on                       window size. Two wordss have first order co-occurence if they                       are typically near each other. Second order if they have similar                       neighbors. We can also use embeddings to see how meaning changes                       over time. \n\n## SLP Chapter 6.11 Bias and Embeddings\n These embeddings also reproduce biases that were latent in the \\ \n                      text. This could create an allocational harm, giving different                       resources to different groups. These actually amplify bias.                       There are techniques of debiasing that can be used. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Vector models are evaluated using similarity scores                       assigned by humans. There exist datasets with these values.                       Additionally, similarity tasks and analogy tasks can be used. \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\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": 7795
        },
        "id": "T3cm1WV542_a",
        "outputId": "64b40e04-6ba8-4885-9ab1-c9c461643625"
      },
      "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": 76,
      "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 We will say that the probability of reaching state s' by completing action a is                $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ . An agents preferences are expressed by a utility function                   which assigns a value of desirability to each state. Expected utility of an action is                   the average utility of all next states times the probability of reaching them with an                   action. MEU says an agent should choose the action that maximizes EU. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n We think of outcomes for actions as a lottery, which have outcomes Si associated                    probabilities pi. Each outcome can either be an atomic state or another lottery.                    These lotteries must obey the axioms of orderability, transitivity, continuity                    (A > B > C then there exists p s.t. B = [p; A, 1-p; C]), substitutability,                    monotonicity (A > B -> p > q iff [p; A, 1-p; B] > [q; A, 1-q; B]), and decomposability.                    These axioms of utility theory being satisfied imply there exists a utility function                    consistent with the preferences. The actual number of the utility does not matter,                    as long as it is consistent relatively.\n\n## AIMA Chapter 16.3 Utility Functions\n Finding a utility function has a process called preference elicitation, in which                    choices are presented and the answers are used to define the function. Normalized                    utilities are between 0 and 1, but there is no absolute scale. We can assess the                    utility of any lottery by choosing between it and [p, U*; 1-p; U^] where U* is the                    best possible utility and U^ the worst, and we adjust p until we get indifference.                    The value of a statistical life is estimated for the utility of a human. Money                    is a good example since more money is monotonically preferred, but the utility                    function here has diminishing returns, meaning it is logarithmic. We can have                    risk-averse (positive insurance premium) and risk-seeking (negative) sections                    of the utility function for behavior. Oftentimes, we have to choose the action                    to maximize ESTIMATED expected utility with an unbiased estimator. The problem                    with this is that since we always maximize we favor positive errors and generate                    bias. Decision theory is normative saying how agents should act but descriptive                    theory states how they do act. The certainty affect says people are strongly                    attracted to certain gains. People also have ambiguity aversion. The anchoring                    effect is one that frames estimates by making relative judgements rather than absolute.\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n With sequential decision problems, the utility function depends on an environment                   history rather than a single state. For these we assume each transition has a bounded                   reward. We cannot have a fixed action sequence solution with a stochastic environemnt,                   so our solution must be a policy. Optimal policies have the highest expected utility. To                   evaluate utility we must consider the time horizon, and a policy that depends on time left                   is called nonstationary. To calculate utility of state sequences we use additive discounted                   rewards (bounds infinite sequences too). A policy guaranteed to reach a terminal state is                   called proper. Then, we can get the utility of a policy given a starting state. The optimal                   policy takes the argmax of the utilities with respect to all policies in a given state. Thus,                   we can derive the bellman equation which defines the utility of a state by the utilies of its                   neighbors with an optimal policy on them. The Q value of the expected utility of a given action                   in a given state, and the max Q value by action is the utility of a state. Shaping theorem says                   we can add any y*f(s')-f(s) to the reward and get a still valid reward function. We can represent                   small MDPs with Q value tables, but larger ones need dynamic decision networks. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value iteration utilizes the Bellman Equations to solve MDPs. We initialize arbitrary values                    for each state, and then perform bellman updates until we converge. This convergence is true                    due to contraction, since the values always geet closer together. Policy iteration involves                    alternating beetween evaluation in which we calculate the utility of each state given the                    current policy and then improvement where a new policy is calculated based on these updates                    utilities. Asynchronous policy iteration updates only a certain subset of states. We can also                    use linear programming which the utilities as variables. Online algorithms like expectimax                    essentially compute at each step instead of precomputing. \n\n## Module 8 Lecture Notes\n QALY is a quality adjusted life year. \n\n## Module 8 Definitions\n* **Micromort** - one in a million chance of death\n* **Certainty equivalent** - value will accept in lieu of a lottery\n* **Insurance premium** - difference between EMV and certianty equivalent\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Each of the n levers has an unknown proobability distribution of winnings                    and we must play by selecting levers. Do we explore or exploit? A common                    example is a one armed bandit that gives reward R0, R1, R2, ... but costs                    y on eahc pull. Our stopping time is the number of times we should pull. The                    value of pulling the reward arm T times over the value of the constant arm                    T times is the Gittins index. We can use UCB to establish a confidence interval                    for the value of an arm and choose the arm with the highest upper bound. Thomson                    sampling chooses an arm randomly accoring to the probability that it is optimal.                    A BSP is a generalization in which each arm is a full MDP. An optimal policy in                    a given arm unaffected by the cost of giving up another arm is called dominating.\n\n## AIMA Chapter 22.1 Learning from Rewards\n RL is where an agent interacts with the world and periodically gets rewards. Model                    based RL is an approach in which an agent used a transition model of the environment                    to help make decisions. Model free RL has Q learning where an agent learns a Q function                    by moving through the environment or policy search where the agent learns a policy. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Passive learning agents are when we try to learn a utility function from a policy. Direct                    utility estimation involves keeping a running average of the reward for each state in a                    table and then seeing that with infinite trials it will converge. ADP learns the transition                    model and then uses DP to solve the MDP. Temporal difference learning applies an update                    U(s) = U(s) + a[R + yU(s') - U(s)] where a is the learning rate. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n In active RL we decide which actions to take. First, we learn a model of the environment.                    In order the balance the tradeoff between explore and exploit, we use a GLIE scheme. An                    example of this is choosing a random action at time step t with probability 1/t. Alternavitely,                    we can use an exploration function that causes a random action to be taken if it has not                    been tried enough. Bayesian RL uses probability to estimate what the true model may be to                    avoid catastrophe. Robust control theory uses a set of possible models and returns the best                    mode in the worst case action for each. Q learning method avoid the neeed for the model                    by learning their q function. Thus, by using the TD update to the q function we derive a                    model free update. SARSA is similar to Q learning but updates by the action taken not just                    the best hypothetical action, penalizing bad exploration.\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n In order to approximate some of these methods, we can update parameters after each trial.                    For direct utility estimation, we use the Widrow Hoff rule and update the parameters of our                    supervised learning problem from states to rewards. For TD and Q learning, we can similarly                    update the parameters of our utility function with the same update rules. Catastrophic forgetting                    is when because gooo behavior is learned, any deviation from it is not learned so catastrophic                    actions can be taken. Experience replay solves this by making sure that these deviations are                    relived. Deep RL uses nonlinear function approximators like neural networks for their utility                    approximations. Reward shaping involves supplying an agent with intermediate rewards for progress.                    Hierarchical RL breaks down action sequences into smaller pieces until learnable.\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n It is hard to quantify uncertainty due to laziness                   meaning it is too much work to list all exceptions,                   theoretical ignorance meaning there is no complete                   theory, or practical ignorance. Decision theory is                   probability theory and utility theory combined. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Formal language of probability. Unconditional or                   prior probabilities mean there are no other givens.                   Posterior probability happens with givens. \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Probabalistic infernce is the computation of                   posterior probabilitiies given evidencee. \n\n## AIMA Chapter 12.4 Independence\n Independence means P(a|b) = P(a). \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes rule states P(A|B) = P(B|A)P(B)/P(A).                   This allows us to switch between the causal and                   diagnostic direction. Conditional independence                   is P(X,Y|Z) = P(X|Z)P(Y|Z) and P(X|Y,Z) = P(X|Z).                   \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Naive bayes models say P(Cause, e) =                   P(Cause) * PROD P(e | Cause). These tend to                   be overconfident due to the assumption of                   independnce of effect variables. \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Wumpus world derivation with probabilities. \n\n## SLP Chapter 3.1 N-Grams\n We can estimate the probability of the next word using counts                      from a corpus.\n\n## SLP Chapter 3.2 Evaluating Language Models\n End-to-end eval of a language model is called extrinsic evaluation. \\ \n                     Instrinsic eval is quality independent of application. Perplexity is the                      inverse probability of a test set. Lower perplexity is better. \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Sampling from a language model is generating sentences according                      to model liklihood. \n\n## SLP Chapter 3.4 Generalization and Zeros\n One problem is that if the probability of any word is 0, the probability                      of the test set is 0, meaning infinite perplexity. We can add a <UNK> for                      OOV words. When we dont have a vocab, we can say that <UNK> is all words                      that appear less than n times. \n\n## SLP Chapter 3.5 Smoothing\n Laplace smoothing adds 1 to all n-gram counts. K-smoothing is a generalization                      where we add k instead of 1. In backoff we use n-grams but if insufficient                      we use n-1 grams. In interpolation, we mix probability estimates from                      all n-gram estimators. We can also do a weighted average of these, or Katz                      backoff with discounting.\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Stupid backoff sees if a n-gram has zero count we go to n-1 and discount.\n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Bayesian networks are digraphs where each node \\ \n                  corresponds to a random variable that has                   probability info that quantifies the effects of the                   parents on the node. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The syntax of the Bayes net is a DAG. It is a                   correct representation of the domain iff each node                   is conditionally independent of all predecessors in                   a topological ordering given its parents. Context-specific                   independence is when a variable is conditionally independent                   of some parents given specific values of others. To handle                   continuous variables we can discretize them. A network with                   both types is calledd a hybrid Bayesian network. \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Enumeration ask is an algorithm that evaluates expression                   trees using recursive techniques. With variable elimination                   we can factorize this approach using pointwise products.                   If the network is a tree the time complexity of exact                   inference is linear. Clustering nodes together can turn a                   bayes net into a polytree structure.\n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Any compoenent of an agent can be improved with ML.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Supervised learning gives data and labels and                   learns patterns between them. We must draw a                   function from a hypothesis space to approximate                   f(X) = y. y is the ground truth. We evaluate h                   by using a test set. A hypothesis is consistent if                   h(x) = f(x) for x in train set. Underfitting is when                   no pattern is found but overfitting is when it fits                   too closely on training and does poorly on testing.                   In Bayes terms, h* = argmax_h P(data|h)P(h).\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n B(x) is the entropy of a rv with                   true with probability x. Then, if p is the number of positive exmaples                   and n negative, the entropy of the output variance is B(p / (p+n)).                   Then, the gain of attribute A is B(A) - Remainder(A) where the remainder                   is sum_E |E|/|A| B(E) where E is the subset of the training set. Gain                   measures importance.                                     Pruning for decision trees combats overfitting where we replace test                   nodes as leaves if they are irrelevant (Gain = 0). We can use significance                   testing to see when a gain is important. We can deal with continuous values                   using a split point and doing an inequality test on the value of an attribute.                   Splitting can also be done through equalities rather than inequality testing. \n\n## AIMA Chapter 5.5 Stochastic Games\n In ML, you need a train set to train candidtae models, a validation set to                   choose the best model, and a test set to do a final unbiased eval of the model.                   K-fold cross validation allows us to reuse data across training and validation but                   not at the same time. We can do cross validation on different size models                   to select which is best. A model that fits all training data has interpolated the data,                   and this starts to approach overfitting. Instead of minimizing error, we often                   minimize a loss function that is more in line with utility.                                     A learning problem is realizable if the hypothesis space actually contains the true                   function f. Regularization is the process of explicity penalizinig complex hypotheses,                   and we can call cost the empirical loss plus some factor time the complexity. Both                   of these can be measured in bits. Hyperparameter tuning is often most feasible with                   hand tuning. If there are only a few, then grid search can even be attempted. For                   large amounts of hyperparameters, random sampling can be tried as well. Bayesian                   optimization makes the task of tuning hyperparameters an ML task itself, while                   population based training uses random search in generations.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Any hypothesis that is consistent with a sufficiently large set of training examples must be                   probably approximately correct. For PAC theorems with booolean functions, the error is the                   probability of misclassification. The number of required examples for the hypothesis to be                   approximately correct is the sample complexity of the learning algorithm.                                     PAC learning can also be applied to decision lists, which are a series of tests,                   each of which iss a conjunction of literals. k-DL is used for a decision list                   with up to k conjunctions. The number of possible hypotheses is 2^O(n^klog(n^k))                   with n attributes. To learn a list we append together tests that satisfy                   some disjoing subsets of the training data until empty when we get no.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Linear regression involves fitting a line by minimizing empircal loss. We                   do this by setting the partial derivatives of the loss to 0 and solving                   for the weights. Instead of having to solve derivatives, we can use gradient                   descent to update the weights by some learning rate. We can do this example                   by example or use batches of example. Stochastic gradient descent randomly                   selects a small number of training examples called minibatches. This can be                   extended to multiple variables with an n element vector and taking gradients                   similarly. It is common to regularize these to avoid overfitting. L1 regularization                   often sets many weights to 0, creating a sparse model. Linear regression can also                   be used for classificaiton treating the line as a decision line. This uses a                   perceptron learning rule. Oftentime, a logistic regression performs better. \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Bag of words is an unordered set of words without position                      only frequency. In Naive Bayes we classify by choosing the max                      probability class. \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n In order to train this classifier we simply use counts as probabilities. \n\n## SLP Chapter 4.3 Worked Example\n Worked example. \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Binary NB only uses whether a word occurs in a doc or not.                      Can prepend NOT for negation to create new words.\n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Naive Bayes can also be used for spam dtection. \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n We can extrapolate word probabilities in NB to sentence                      probabilities. \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Human defined labels for evaluation are called gold labels.                      Accuracy is a bad metric for biased classes, and we use precision                      ratio of true positives to labeled positives or recall ratio of                      true positives to true positives plus false negatives. F-measure                      combines these. \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Test sets vs dev sets vs train sets. \n\n## SLP Chapter 4.9 Statistical Significance Testing\n We can test whether the effect size is statistically significant                      to see if a classifier is better than another. Parametric tests                      assume the statistic is normal or otherwise distributed for our p value.                      Bootstrap testing draws smaller sample from a larger one and creates                      many virtual test sets. \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Representational harms demean a social group. These can occur due                       to biases in data or biases in human labeling. A model card                       gives information about a model. \n\n## Module 12 Lecture Notes\n Decision trees map a vector of attribute values                   to a single output value. When learning a decision                   tree, we test the most important attribute first                   and then solve smaller subproblems. We measure                   importance using entropy. Less entropy means more                   information, and entropy is the sum over all values                   of probabilities times the negative log_2 of                   probabilities.  \n\n## Module 12 Definitions\n* **Bias** - tendency of predictive hypothesis to deviate from           the expected value over different training sets\n* **Variance** - the amount of change in the hypothesis from fluctuation in training data\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n The sigmoid function maps a real value between 0 and 1. Our                      decision boundary we say if P(Y=1|x) = sigmoid(w*x+b) is more than .5  we say                      yes else no where .5 is the decision boundary.\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n We learn the weights and bias through supervised classiciation in which                      we know the label for each observatiion x. Then, we measure loss of predictions                      and update parameters. \n\n## SLP Chapter 5.3 The cross-entropy loss function\n The cross entropy loss function prefers the correct classs of labels to be more                      likely. p(y|x) = y_hat ^ y * (1 - y_hat) ^ (1-y). We can also do logs, and since                      we want to maximize this liklihood we negate it for loss.\n\n## SLP Chapter 5.4 Gradient Descent\n With gradient descent we want the weights that minimize the loss function. We                      find the gradient of the loss d/dw and then move the weights by negative that                      times a learning rate. \n\n## SLP Chapter 5.5 Regularization\n In order to avoid overfitting the weights, we can regularize the training data.                      Regularization subtracts a term proprotional to weight size, penalizing large                      weights. L2 does squares while L1 (lasso) absoslute value. \n\n## SLP Chapter 5.6 Multinomial logistic regression\n For multinomial regression we can use softmax, a generalization of sigmoid                      that takes exp(xi) / sum exp(xi). We need separate weight vectors for each class                      CE loss is the sum of the logs of each class weighted by their prob given the                      input. \n\n## SLP Chapter 7.1 Units\n The sigmoid activation can be replaced by tanh or ReLU, each                      having their own advanategs with outliers and derivatives. \n\n## SLP Chapter 7.2 The XOR problem\n A perceptron fires based on whether w*x+b >0 or not. XOR                      requires more than one perceptron as it is not linearly separable.                      Two layers change the space to make it linearly separable. \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n The feedforward network is multilayer with no cycles and passes                      outputs forward. It computes using 2D matrices of weights by layer.                      If the hidden layer activations were linear it could just be written                      as a one layer network.\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n We can use these networks for NLP by passing in a vector of                      hand designed features. We cana also learn features by using concatenated                      embeddings of the n words.\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Neural language models hold longer histories than n-gram models. These                      also learn embeddings instead of true words so they do better with unseen data. \\ \n                     For this, we create one hot vectors given indices and then multiply them                      by embedding matrices. Then we pass this result to hidden layers and apply                      softmax. \n\n## SLP Chapter 7.6 Training Neural Nets\n We train these neural nets by using loss functions and using gradient descent                      as before, but this time we use backpropagation to update weights over intermediate                      layers in the network. We can represent networks as computation graphs                      and update by partial derivatives of the activation functions.  \n\n## SLP Chapter 7.7 Training the neural language model\n This techniqu above can be applied to a neural language model to learn                      embeddings and hidden layer weight. \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Probabalistic language models predict the next word given \\ \n                     some preceding context. We assign conditional probabilities                      to every possible next word. We use perplexity to evaluate. \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n We use RNNs as networks that have cycles and these build the                      basis for future LSTMs. With these, we can compute hidden layers                      given the value of the hidden layer previously, giving a form of                      memory. This is the same as feed forward except we add Uh_t-1 to                      Wx_t when evaluating the hidden layer. To train these, we                      conduct backprop through time. \n\n## SLP Chapter 9.3 RNNs as Language Models\n RNNs don't have the limit problems of n-gram models, and we still                      pass in a series of word embeddings each represented as a one-hot                      vector of size |V| x 1. Instead of giving predictions to train                      the RNN we always give it the correct history, called teacher forcing.\n\n## SLP Chapter 6.1 Lexical Semantics\n We can group meanings of words by semantics. Lemma is the base                      of a word and every variation is called a sense. We can also                      group words by relatedness or connotation. \n\n## SLP Chapter 6.2 Vector Semantics\n Vector semantics is how we can represent word meaning in NLP.                      Vectors for representing these words are embeddings. \n\n## SLP Chapter 6.3 Words and Vectors\n We can use term-document matrices to represent frequencies                      of words on documents. We can graph these as points in n                      dimensional space. Information retrival is the task of                      finding a document best matching a query. We can also create                      term term matrices that show how often terms appear together                      in some context. \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n To measure similarity of words we measure their dot product.                      We first normalize the vectors and then take the dot product                      or take the dot product and divide by the norm of each.  \n\n## SLP Chapter 6.8 Word2vec\n SGNS is a method for computing embeddings in word2vec.                      We can take a sigmoid of the dot product of a target                      word paired with a candidate and in skip gram we can multiply                      these together for other context words. There are other                      types of static embeddings as well. \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Embeddings have the semantic property of depending on                       window size. Two wordss have first order co-occurence if they                       are typically near each other. Second order if they have similar                       neighbors. We can also use embeddings to see how meaning changes                       over time. \n\n## SLP Chapter 6.11 Bias and Embeddings\n These embeddings also reproduce biases that were latent in the \\ \n                      text. This could create an allocational harm, giving different                       resources to different groups. These actually amplify bias.                       There are techniques of debiasing that can be used. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Vector models are evaluated using similarity scores                       assigned by humans. There exist datasets with these values.                       Additionally, similarity tasks and analogy tasks can be used. \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}