{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy_of_Template_for_CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "42b37a3c-b9ea-4042-d142-62dd9f170ddf"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b579762a-ff71-4a92-f2f5-c08df512f765"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n",
        "\n",
        "action = argmax EU (a|e)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 =  \"\"\" \n",
        "We can think of the set of outcomes for each action as a lottery—think of each action as a ticket. \n",
        "\n",
        "Orderability: Given any two lotteries, a rational agent must either prefer one to the other or else rate the two as equally preferable. \n",
        "\n",
        "Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C,\n",
        "then the agent must prefer A to C.\n",
        "\n",
        "Continuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1 − p.\n",
        "\n",
        "Substitutability: If an agent is indifferent between two lotteries A and B, then the\n",
        "agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries.\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "\n",
        "If we want to build a decision-theoretic system that helps the agent make decisions or acts on his or her behalf, we must first work out what the agent’s utility function is. This process, often called preference elicitation.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "We assume for now that the environment is fully observable, so that the agent always knows where it is.\n",
        "\n",
        "We will assume that transitions are Markovian in the sense of Chapter 15, that is, the probability of reaching s\u0002 from s depends only on s and not on the history of earlier states. \n",
        "\n",
        "To sum up: a sequential decision problem for a fully observable, stochastic environment\n",
        "with a Markovian transition model and additive rewards is called a Markov decision process,\n",
        "\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\" \n",
        "Bellman equation: the utility of a state is the immediate reward for that state plus the expected discounted utility of the next state, assuming that the agent chooses the optimal action\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "\"utility function\" : \"assigns a single number to express the desirability of a state.\",\n",
        "\"expected utility\" : \"The expected utility of an action given the evi- dence, EU (a|e), is just the average utility value of the outcomes\",\n",
        "\"Probability theory\": \"describes what an agent should believe on the basis of evidence\",\n",
        "\"Expert systems\": \"incorporate utility information have additional capabilities compared with pure inference systems.\",\n",
        "\"Markov decision process\": \"To sum up: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\",\n",
        "\"Bellman equation\": \"he utility of a state is the immediate reward for that state plus the expected discounted utility of the next state, assuming that the agent chooses the optimal action\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 966
        },
        "outputId": "df28c549-0996-475f-d0ed-033bcb2343d5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Bellman equation' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n\naction = argmax EU (a|e)\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nWe can think of the set of outcomes for each action as a lottery—think of each action as a ticket. \n\nOrderability: Given any two lotteries, a rational agent must either prefer one to the other or else rate the two as equally preferable. \n\nTransitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C,\nthen the agent must prefer A to C.\n\nContinuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1 − p.\n\nSubstitutability: If an agent is indifferent between two lotteries A and B, then the\nagent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries.\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \n\nIf we want to build a decision-theoretic system that helps the agent make decisions or acts on his or her behalf, we must first work out what the agent’s utility function is. This process, often called preference elicitation.\n\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nWe assume for now that the environment is fully observable, so that the agent always knows where it is.\n\nWe will assume that transitions are Markovian in the sense of Chapter 15, that is, the probability of reaching s\u0002 from s depends only on s and not on the history of earlier states. \n\nTo sum up: a sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a Markov decision process,\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \nBellman equation: the utility of a state is the immediate reward for that state plus the expected discounted utility of the next state, assuming that the agent chooses the optimal action\n\n \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - assigns a single number to express the desirability of a state.\n* **Expected utility** - The expected utility of an action given the evi- dence, EU (a|e), is just the average utility value of the outcomes\n* **Probability theory** - describes what an agent should believe on the basis of evidence\n* **Expert systems** - incorporate utility information have additional capabilities compared with pure inference systems.\n* **Markov decision process** - To sum up: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\n* **Bellman equation** - he utility of a state is the immediate reward for that state plus the expected discounted utility of the next state, assuming that the agent chooses the optimal action\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "Policy iteration: alternates between calculating the utilities of states under the current policy and improving the current policy with respect to the current utilities.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" \n",
        "The task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the environment.\n",
        "\n",
        "A utility-based agent learns a utility function on states and uses it to select actions that maximize the expected outcome utility.\n",
        "\n",
        "A Q-learning agent learns an action-utility function, or Q-function, giving the ex- pected utility of taking a given action in a given state.\n",
        "\n",
        "A reflex agent learns a policy that maps directly from states to actions.\n",
        "\n",
        " \"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "The passive learning task is similar to the policy evaluation task, part of the policy iteration algorithm \n",
        "\n",
        "An adaptive dynamic programming (or ADP) agent takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solv- ing the corresponding Markov decision process using a dynamic programming method.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "After experimenting with minor variations, from the 276th trial onward it sticks to that policy, never learning the utilities of the other states and never finding the optimal route via (1,2), (1,3), and (2,3). We call this agent the greedy agent.\n",
        "\n",
        "Technically, any such scheme needs to be greedy in the limit of infinite exploration, or GLIE. \n",
        "\n",
        "Q-learning, which learns an action-utility representation instead of learning utilities.\n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "One way to handle such problems is to use function approximation, which simply means using any sort of representation for the Q-function other than a lookup table. \n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter22_5 =  \"\"\" \n",
        "policy search is the simplest of all the methods in this chapter: the idea is to keep twiddling the policy as long as its performance improves, then stop.\n",
        "\n",
        "For this reason, policy search methods often use a stochastic policy representation πθ (s, a), which specifies the probability of selecting action a in state s. One popular representation is the softmax function.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\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",
        "\"Policy iteration\" : \"it alternates between calculating the utilities of states under the current policy and improving the current policy with respect to the current utilities.\",\n",
        "\"reinforcement learning\": \"The task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the environment.\",\n",
        "\"policy search\": \"the idea is to keep twiddling the policy as long as its performance improves, then stop.\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 815
        },
        "cellView": "form",
        "outputId": "2ab6b60f-e8b4-4cdd-f3aa-00cb73ab2e7f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nPolicy iteration: alternates between calculating the utilities of states under the current policy and improving the current policy with respect to the current utilities.\n\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n \nThe task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the environment.\n\nA utility-based agent learns a utility function on states and uses it to select actions that maximize the expected outcome utility.\n\nA Q-learning agent learns an action-utility function, or Q-function, giving the ex- pected utility of taking a given action in a given state.\n\nA reflex agent learns a policy that maps directly from states to actions.\n\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nThe passive learning task is similar to the policy evaluation task, part of the policy iteration algorithm \n\nAn adaptive dynamic programming (or ADP) agent takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solv- ing the corresponding Markov decision process using a dynamic programming method.\n\n\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nAfter experimenting with minor variations, from the 276th trial onward it sticks to that policy, never learning the utilities of the other states and never finding the optimal route via (1,2), (1,3), and (2,3). We call this agent the greedy agent.\n\nTechnically, any such scheme needs to be greedy in the limit of infinite exploration, or GLIE. \n\nQ-learning, which learns an action-utility representation instead of learning utilities.\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \nOne way to handle such problems is to use function approximation, which simply means using any sort of representation for the Q-function other than a lookup table. \n\n\n\n \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Policy iteration** - it alternates between calculating the utilities of states under the current policy and improving the current policy with respect to the current utilities.\n* **Reinforcement learning** - The task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the environment.\n* **Policy search** - the idea is to keep twiddling the policy as long as its performance improves, then stop.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \n",
        "- Laziness: It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n",
        "- Theoretical ignorance: Medical science has no complete theory for the domain.\n",
        "- Practical ignorance: Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\" \n",
        "A fully specified probability model associates a numerical probability P (ω) with each possible world.\n",
        "\n",
        "Variables in probability theory are called random variables and their names begin with an uppercase letter. Thus, in the dice example, Total and Die1 are random variables. Every random variable has a domain—the set of possible values it can take on.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_3 = \"\"\" \n",
        "In this section we describe a simple method for probabilistic inference—that is, the compu- tation of posterior probabilities for query propositions given observed evidence.\n",
        "\n",
        "This process is called marginalization, or summing out—because we sum up the probabilities for each possible value of the other variables, thereby taking them out of the equation.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        "The property we used in Equation (13.10) is called independence (also marginal in- dependence and absolute independence). \n",
        "\n",
        " \"\"\"\n",
        "chapter12_5 = \"\"\" \n",
        "\n",
        "P(b|a) = P(a|b)P(b)/P(a)\n",
        "\n",
        "This equation is known as Bayes’ rule (also Bayes’ law or Bayes’ theorem). \n",
        "\n",
        "Bayes’ rule allows unknown probabilities to be computed from known conditional probabilities, usually in the causal direction. Applying Bayes’ rule with many pieces of evidence runs into the same scaling problems as does the full joint distribution.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "Conditional independence brought about by direct causal relationships in the domain might allow the full joint distribution to be factored into smaller, conditional distri- butions. The naive Bayes model assumes the conditional independence of all effect variables, given a single cause variable, and grows linearly with the number of effects.\n",
        "\n",
        " \"\"\"\n",
        "chapter12_7 = \"\"\" \n",
        "A wumpus-world agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" \n",
        "A model of the probability distribution of n-letter sequences is thus called an n-gram model.\n",
        "\n",
        "An n-gram model is defined as a Markov chain of order n − 1.\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" \n",
        "\n",
        "text classification, also known as categorization: given a text of some kind, decide which of a predefined set of classes it belongs to.\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" \n",
        "\n",
        "Information retrieval: is the task of finding documents that are relevant to a user’s need for information. \n",
        "\n",
        "A corpus of documents. Each system must decide what it wants to treat as a document: a paragraph, a page, or a multipage text.\n",
        "\n",
        "Queries posed in a query language. A query specifies what the user wants to know. The query language can be just a list of words, such as [AI book];\n",
        "\n",
        "A result set. This is the subset of documents that the IR system judges to be relevant to the query.\n",
        "\n",
        "A presentation of the result set. This can be as simple as a ranked list of document titles or as complex as a rotating color map of the result set projected onto a three- dimensional space, rendered as a two-dimensional display.\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" \n",
        "\n",
        "Information extraction is the process of acquiring knowledge by skimming a text and look- ing for occurrences of a particular class of object and for relationships among objects.\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" \n",
        "This modification is called smoothing or discounting. In this section and the fol- lowing ones we’ll introduce a variety of ways to do smoothing: Laplace (add-one) smoothing, add-k smoothing, stupid backoff, and Kneser-Ney smoothing.\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" \n",
        "Stupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. \n",
        " \"\"\"\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",
        "\"n-gram model\" : \"A model of the probability distribution of n-letter sequences is thus called an n-gram model.\",\n",
        "\"text classification\": \"also known as categorization: given a text of some kind, decide which of a predefined set of classes it belongs to.\",\n",
        "\"Information retrieval\": \"the task of finding documents that are relevant to a user’s need for information. \",\n",
        "\"Information extraction\": \"the process of acquiring knowledge by skimming a text and look- ing for occurrences of a particular class of object and for relationships among objects.\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e8b55058-bdb6-4356-c4a0-6898adea6062"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n- Laziness: It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n- Theoretical ignorance: Medical science has no complete theory for the domain.\n- Practical ignorance: Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \nA fully specified probability model associates a numerical probability P (ω) with each possible world.\n\nVariables in probability theory are called random variables and their names begin with an uppercase letter. Thus, in the dice example, Total and Die1 are random variables. Every random variable has a domain—the set of possible values it can take on.\n\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \nIn this section we describe a simple method for probabilistic inference—that is, the compu- tation of posterior probabilities for query propositions given observed evidence.\n\nThis process is called marginalization, or summing out—because we sum up the probabilities for each possible value of the other variables, thereby taking them out of the equation.\n\n \n\n## AIMA Chapter 12.4 Independence\n \nThe property we used in Equation (13.10) is called independence (also marginal in- dependence and absolute independence). \n\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n\nP(b|a) = P(a|b)P(b)/P(a)\n\nThis equation is known as Bayes’ rule (also Bayes’ law or Bayes’ theorem). \n\nBayes’ rule allows unknown probabilities to be computed from known conditional probabilities, usually in the causal direction. Applying Bayes’ rule with many pieces of evidence runs into the same scaling problems as does the full joint distribution.\n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nConditional independence brought about by direct causal relationships in the domain might allow the full joint distribution to be factored into smaller, conditional distri- butions. The naive Bayes model assumes the conditional independence of all effect variables, given a single cause variable, and grows linearly with the number of effects.\n\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n \nA wumpus-world agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable.\n\n\n\n## SLP Chapter 3.1 N-Grams\n \nA model of the probability distribution of n-letter sequences is thus called an n-gram model.\n\nAn n-gram model is defined as a Markov chain of order n − 1.\n\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n\ntext classification, also known as categorization: given a text of some kind, decide which of a predefined set of classes it belongs to.\n\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n \n\nInformation retrieval: is the task of finding documents that are relevant to a user’s need for information. \n\nA corpus of documents. Each system must decide what it wants to treat as a document: a paragraph, a page, or a multipage text.\n\nQueries posed in a query language. A query specifies what the user wants to know. The query language can be just a list of words, such as [AI book];\n\nA result set. This is the subset of documents that the IR system judges to be relevant to the query.\n\nA presentation of the result set. This can be as simple as a ranked list of document titles or as complex as a rotating color map of the result set projected onto a three- dimensional space, rendered as a two-dimensional display.\n\n \n\n## SLP Chapter 3.4 Generalization and Zeros\n \n\nInformation extraction is the process of acquiring knowledge by skimming a text and look- ing for occurrences of a particular class of object and for relationships among objects.\n\n \n\n## SLP Chapter 3.5 Smoothing\n \nThis modification is called smoothing or discounting. In this section and the fol- lowing ones we’ll introduce a variety of ways to do smoothing: Laplace (add-one) smoothing, add-k smoothing, stupid backoff, and Kneser-Ney smoothing.\n\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n \nStupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. \n \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **N-gram model** - A model of the probability distribution of n-letter sequences is thus called an n-gram model.\n* **Text classification** - also known as categorization: given a text of some kind, decide which of a predefined set of classes it belongs to.\n* **Information retrieval** - the task of finding documents that are relevant to a user’s need for information. \n* **Information extraction** - the process of acquiring knowledge by skimming a text and look- ing for occurrences of a particular class of object and for relationships among objects.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" \n",
        "Bayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely.\n",
        "\n",
        "This is the most common name, but there are many synonyms, including belief network, probabilistic net- work, causal network, and knowledge map. In statistics, the term graphical model refers to a somewhat broader class that includes Bayesian networks. An extension of Bayesian networks called a decision network or influence diagram is covered in Chapter 16.\n",
        "\n",
        "The conditional distributions in Figure 14.2 are shown as a conditional probability table, or CPT. (This form of table can be used for discrete variables; other representations, including those suitable for continuous variables, are described in Section 14.2.) Each row in a CPT contains the conditional probability of each node value for a conditioning case.\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\" \n",
        "The compactness of Bayesian net- works is an example of a general property of locally structured (also called sparse) systems.\n",
        "\n",
        "This phenomenon is quite general and is related to the distinction between causal and diagnostic models intro- duced in Section 13.5.1 (see also Exercise 8.13). \n",
        "\n",
        "Another important independence property is implied by the topological semantics: a node is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\" \n",
        "\n",
        "Usually, such relationships are describable by a canonical distribution that fits some standard pattern. In such cases, the complete table can be specified by naming the pattern and perhaps supplying a few parameters—much easier than supplying an exponential number of parameters.\n",
        "\n",
        "The simplest example is provided by deterministic nodes.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian network\" : \"A Bayesian network is a directed acyclic graph whose nodes correspond to random variables; each node has a conditional distribution for the node, given its parents.\",    \n",
        "\"conditional independence\": \"Bayesian networks provide a concise way to represent conditional independence rela- tionships in the domain.\",\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 736
        },
        "cellView": "form",
        "outputId": "9431f77a-91e7-4027-b690-c3b682856fde"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Bayesian network' is too long!\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \nBayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely.\n\nThis is the most common name, but there are many synonyms, including belief network, probabilistic net- work, causal network, and knowledge map. In statistics, the term graphical model refers to a somewhat broader class that includes Bayesian networks. An extension of Bayesian networks called a decision network or influence diagram is covered in Chapter 16.\n\nThe conditional distributions in Figure 14.2 are shown as a conditional probability table, or CPT. (This form of table can be used for discrete variables; other representations, including those suitable for continuous variables, are described in Section 14.2.) Each row in a CPT contains the conditional probability of each node value for a conditioning case.\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \nThe compactness of Bayesian net- works is an example of a general property of locally structured (also called sparse) systems.\n\nThis phenomenon is quite general and is related to the distinction between causal and diagnostic models intro- duced in Section 13.5.1 (see also Exercise 8.13). \n\nAnother important independence property is implied by the topological semantics: a node is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket. \n\n\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n\nUsually, such relationships are describable by a canonical distribution that fits some standard pattern. In such cases, the complete table can be specified by naming the pattern and perhaps supplying a few parameters—much easier than supplying an exponential number of parameters.\n\nThe simplest example is provided by deterministic nodes.\n\n\n \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Bayesian network** - A Bayesian network is a directed acyclic graph whose nodes correspond to random variables; each node has a conditional distribution for the node, given its parents.\n* **Conditional independence** - Bayesian networks provide a concise way to represent conditional independence rela- tionships in the domain.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" \n",
        "We will see in Chapter 19 that we can also do analytical or deductive learning: going from a known general rule to a new rule that is logically entailed, but is useful because it allows more efficient processing.\n",
        "\n",
        "In reinforcement learning the agent learns from a series of reinforcements—rewards or punishments. \n",
        "\n",
        "In supervised learning the agent observes some example input–output pairs and learns a function that maps from input to output.\n",
        "\n",
        " \"\"\"\n",
        "chapter19_2 = \"\"\" \n",
        "When the output y is one of a finite set of values (such as sunny, cloudy or rainy), the learning problem is called classification, and is called Boolean or binary classification if there are only two values.\n",
        "\n",
        "When y is a number (such as tomorrow’s temperature), the learning problem is called regression. \n",
        "\n",
        " \"\"\"\n",
        "chapter19_3 = \"\"\" \n",
        "A decision tree represents a function that takes as input a vector of attribute values and returns a “decision”—a single output value. \n",
        "\n",
        "This problem is called overfitting. A general phenomenon, overfitting occurs with all types of learners, even when the target function is not at all random.\n",
        "\n",
        "We can answer this question by using a statistical significance test. Such a test begins by assuming that there is no underlying pattern (the so-called null hypothesis).\n",
        "\n",
        "Missing data: In many domains, not all the attribute values will be known for every example. The values might have gone unrecorded, or they might be too expensive to obtain.\n",
        "\n",
        "Multivalued attributes: When an attribute has many possible values, the information gain measure gives an inappropriate indication of the attribute’s usefulness.\n",
        " \"\"\"\n",
        "chapter19_4 = \"\"\" \n",
        "To make that precise we need to define “future data” and “best.” We make the stationarity assumption: that there is a probability distribution over examples that remains stationary over time.\n",
        "\n",
        "We can squeeze more out of the data and still get an accurate estimate using a technique called k-fold cross-validation.\n",
        " \"\"\"\n",
        "chapter19_5 = \"\"\" \n",
        "The underlying principle is that any hypothesis that is seri- ously wrong will almost certainly be “found out” with high probability after a small number of examples, because it will make an incorrect prediction. Thus, any hypothesis that is consis- tent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct.\n",
        "\n",
        "Any learning algorithm that returns hypotheses that are probably approximately correct is called a PAC learning algorithm; we can use this approach to provide bounds on the performance of various learning algorithms.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter19_6 = \"\"\" \n",
        "the class of linear functions of continuous-valued inputs\n",
        "\n",
        "The task of finding the hw that best fits these data is called linear regression.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" \n",
        "multinomial naive Bayes classifier, so called be- cause it is a Bayesian classifier that makes a simplifying (naive) assumption about how the features interact.\n",
        "\n",
        "We represent a text document as if it were a bag-of-words, that is, an unordered set of words with their position ignored, keeping only their frequency in the document.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_2 = \"\"\" \n",
        "Finally, some systems choose to completely ignore another class of words: stop words, very frequent words like the and a.\n",
        "\n",
        "The solution for such unknown words is to ignore them—remove them from the test document and not include any probability for them at all.\n",
        " \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" \n",
        "multinomial naive Bayes or binary NB. The variant uses the same Eq. 4.10 except that for each document we remove all duplicate words before concatenating them into the single big document.\n",
        " \"\"\"\n",
        "slp_chapter4_5 = \"\"\" \n",
        "Consider the task of spam detection, deciding if a particular piece of email is an example of spam (unsolicited bulk email) — and one of the first applications of naive Bayes to text classification\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_6 = \"\"\" \n",
        "Since the likelihood features from the naive Bayes model assign a probability to each word P(word|c), the model also assigns a probability to each sentence:\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_7 = \"\"\" \n",
        "We also need to know whether the email is actually spam or not, i.e. the human-defined labels for each document that we are trying to match. We will refer to these human labels as the gold labels.\n",
        "\n",
        "Precision measures the percentage of the items that the system detected (i.e., the system labeled as positive) that are in fact positive (i.e., are positive according to the human gold labels).\n",
        "\n",
        "Recall measures the percentage of items actually present in the input that were correctly identified by the system.\n",
        " \"\"\"\n",
        "slp_chapter4_8 = \"\"\" \n",
        " we use the training set to train the model, then use the development test set (also called a devset) to perhaps tune some parameters,\n",
        "  \"\"\"\n",
        "slp_chapter4_9 = \"\"\" \n",
        "We say that a result (e.g., “A is better than B”) is statistically significant if the δ we saw has a probability that is below the threshold and we therefore reject this null hypothesis.\n",
        "\n",
        "There are two common non-parametric tests used in NLP: approximate ran- domization (Noreen, 1989) and the bootstrap test.\n",
        " \"\"\"\n",
        "slp_chapter4_10 = \"\"\" \n",
        "One class of harms is representational harms\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"supervised learning.\" : \"If the available feedback provides the correct answer for example inputs, then the learn- ing problem is called supervised learning.\",    \n",
        "\"classification\": \"The task is to learn a function y = h(x). Learning a discrete-valued function is called classification;\",\n",
        "\"regression\": \"learning a continuous function \",\n",
        "\"Ockham’s razor\": \"Inductive learning involves finding a hypothesis that agrees well with the examples. Ockham’s razor suggests choosing the simplest consistent hypothesis. \",\n",
        "\"Decision trees\": \"Decision trees can represent all Boolean functions.\",\n",
        "\"Computational learning theory\": \"Computational learning theory analyzes the sample complexity and computational complexity of inductive learning. There is a tradeoff between the expressiveness of the hypothesis language and the ease of learning.\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0327661d-76b3-4839-ba15-bb9345fecd5d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Computational learning theory' is too long!\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n \nWe will see in Chapter 19 that we can also do analytical or deductive learning: going from a known general rule to a new rule that is logically entailed, but is useful because it allows more efficient processing.\n\nIn reinforcement learning the agent learns from a series of reinforcements—rewards or punishments. \n\nIn supervised learning the agent observes some example input–output pairs and learns a function that maps from input to output.\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nWhen the output y is one of a finite set of values (such as sunny, cloudy or rainy), the learning problem is called classification, and is called Boolean or binary classification if there are only two values.\n\nWhen y is a number (such as tomorrow’s temperature), the learning problem is called regression. \n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nA decision tree represents a function that takes as input a vector of attribute values and returns a “decision”—a single output value. \n\nThis problem is called overfitting. A general phenomenon, overfitting occurs with all types of learners, even when the target function is not at all random.\n\nWe can answer this question by using a statistical significance test. Such a test begins by assuming that there is no underlying pattern (the so-called null hypothesis).\n\nMissing data: In many domains, not all the attribute values will be known for every example. The values might have gone unrecorded, or they might be too expensive to obtain.\n\nMultivalued attributes: When an attribute has many possible values, the information gain measure gives an inappropriate indication of the attribute’s usefulness.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nTo make that precise we need to define “future data” and “best.” We make the stationarity assumption: that there is a probability distribution over examples that remains stationary over time.\n\nWe can squeeze more out of the data and still get an accurate estimate using a technique called k-fold cross-validation.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe underlying principle is that any hypothesis that is seri- ously wrong will almost certainly be “found out” with high probability after a small number of examples, because it will make an incorrect prediction. Thus, any hypothesis that is consis- tent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct.\n\nAny learning algorithm that returns hypotheses that are probably approximately correct is called a PAC learning algorithm; we can use this approach to provide bounds on the performance of various learning algorithms.\n\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nthe class of linear functions of continuous-valued inputs\n\nThe task of finding the hw that best fits these data is called linear regression.\n\n\n\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n \nmultinomial naive Bayes classifier, so called be- cause it is a Bayesian classifier that makes a simplifying (naive) assumption about how the features interact.\n\nWe represent a text document as if it were a bag-of-words, that is, an unordered set of words with their position ignored, keeping only their frequency in the document.\n\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \nFinally, some systems choose to completely ignore another class of words: stop words, very frequent words like the and a.\n\nThe solution for such unknown words is to ignore them—remove them from the test document and not include any probability for them at all.\n \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \nmultinomial naive Bayes or binary NB. The variant uses the same Eq. 4.10 except that for each document we remove all duplicate words before concatenating them into the single big document.\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n \nConsider the task of spam detection, deciding if a particular piece of email is an example of spam (unsolicited bulk email) — and one of the first applications of naive Bayes to text classification\n\n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n \nSince the likelihood features from the naive Bayes model assign a probability to each word P(word|c), the model also assigns a probability to each sentence:\n\n \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n \nWe also need to know whether the email is actually spam or not, i.e. the human-defined labels for each document that we are trying to match. We will refer to these human labels as the gold labels.\n\nPrecision measures the percentage of the items that the system detected (i.e., the system labeled as positive) that are in fact positive (i.e., are positive according to the human gold labels).\n\nRecall measures the percentage of items actually present in the input that were correctly identified by the system.\n \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n \n we use the training set to train the model, then use the development test set (also called a devset) to perhaps tune some parameters,\n  \n\n## SLP Chapter 4.9 Statistical Significance Testing\n \nWe say that a result (e.g., “A is better than B”) is statistically significant if the δ we saw has a probability that is below the threshold and we therefore reject this null hypothesis.\n\nThere are two common non-parametric tests used in NLP: approximate ran- domization (Noreen, 1989) and the bootstrap test.\n \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n \nOne class of harms is representational harms\n \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Supervised learning.** - If the available feedback provides the correct answer for example inputs, then the learn- ing problem is called supervised learning.\n* **Classification** - The task is to learn a function y = h(x). Learning a discrete-valued function is called classification;\n* **Regression** - learning a continuous function \n* **Ockham’s razor** - Inductive learning involves finding a hypothesis that agrees well with the examples. Ockham’s razor suggests choosing the simplest consistent hypothesis. \n* **Decision trees** - Decision trees can represent all Boolean functions.\n* **Computational learning theory** - Computational learning theory analyzes the sample complexity and computational complexity of inductive learning. There is a tradeoff between the expressiveness of the hypothesis language and the ease of learning.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" \n",
        "Logistic regression solves this task by learning, from a training set, a vector of weights and a bias term. \n",
        "\n",
        "The bias term, also called the intercept, is another real number that’s added to the weighted inputs.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" \n",
        "In the next section we’ll introduce the loss function that is commonly used for logistic regression and also for neural networks, the cross-entropy loss.\n",
        "\n",
        "The standard algorithm for this is gradient descent; we’ll introduce the stochastic gradient descent algorithm in the following section.\n",
        " \"\"\"\n",
        "slp_chapter5_3 = \"\"\" \n",
        "This is called conditional maximum likelihood estimation: we choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x.\n",
        "\n",
        "The resulting loss function is the negative log likelihood loss, generally called the cross-entropy loss.\n",
        " \"\"\"\n",
        "slp_chapter5_4 = \"\"\" \n",
        "For logistic regression, this loss function is conveniently convex.\n",
        "\n",
        "The learning rate η is a hyperparameter that must be adjusted. \n",
        " \"\"\"\n",
        "slp_chapter5_5 = \"\"\" \n",
        "This problem is called overfitting. A good model should be able to generalize well from the training data to the unseen test set, but a model that overfits will have poor generalization\n",
        "\n",
        "L1 regularization is a linear function of the weight values, named after the L1 norm ||W||1, the sum of the absolute values of the weights, or Manhattan distance\n",
        " \"\"\"\n",
        "slp_chapter5_6 = \"\"\" \n",
        "In such cases we use multinomial logistic regression, also called softmax re- gression (or, historically, the maxent classifier).\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" \n",
        "At its heart, a neural unit is taking a weighted sum of its inputs, with one addi- tional term in the sum called a bias term.\n",
        "\n",
        "Finally, instead of using z, a linear function of x, as the output, neural units apply a non-linear function f to z. We will refer to the output of this function as the activation value for the unit, a. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_2 = \"\"\" \n",
        "\n",
        "This example was first shown for the perceptron, which is a very simple neural unit that has a binary output and does not have a non-linear activation function.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_3 = \"\"\" \n",
        "Let’s now walk through a slightly more formal presentation of the simplest kind of neural network, the feedforward network.\n",
        "\n",
        "For historical reasons multilayer networks, especially feedforward networks, are sometimes called multi-layer perceptrons (or MLPs);\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" \n",
        "As our second application of feedforward networks, let’s consider language model- ing\n",
        "\n",
        "Forward inference is the task, given an input, of running a forward pass on the network to produce a probability distribution over possible outputs, in this case next words.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_6 = \"\"\" \n",
        "we’ll need a loss function that models the distance between the system output and the gold output, and it’s common to use the loss function used for logistic regression, the cross-entropy loss.\n",
        "\n",
        "to find the parameters that minimize this loss function, we’ll use the gradient descent optimization algorithm introduced in Chapter 5.\n",
        "\n",
        "The answer is the algorithm called error backpropagation or backward differentiation.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter7_7 = \"\"\" \n",
        "The cross-entropy loss that is used in neural networks is the same one we saw for logistic regression.\n",
        "\n",
        "Assume this is a hard classification task, meaning that only one class is the correct one, and that there is one output unit in y foreachclass. \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"Logistic regression\": \"a supervised machine learning classifier that extracts real-valued features from the input, multiplies each by a weight, sums them, and passes the sum through a sigmoid function to generate a probability. A threshold is used to make a decision.\",    \n",
        "\"Multinomial logistic regression\": \"uses the softmax function to compute proba- bilities.\",\n",
        "\"cross-entropy loss\": \"The weights (vector w and bias b) are learned from a labeled training set via a loss function, such as the cross-entropy loss, that must be minimized.\",\n",
        "\"Regularization\": \"is used to avoid overfitting.\",\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "30d53116-2484-44f1-e9e6-e4127f7f7dd0"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Logistic regression' is too long!\nWARNING: Your definition of 'cross-entropy loss' is too long!\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nLogistic regression solves this task by learning, from a training set, a vector of weights and a bias term. \n\nThe bias term, also called the intercept, is another real number that’s added to the weighted inputs.\n\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nIn the next section we’ll introduce the loss function that is commonly used for logistic regression and also for neural networks, the cross-entropy loss.\n\nThe standard algorithm for this is gradient descent; we’ll introduce the stochastic gradient descent algorithm in the following section.\n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \nThis is called conditional maximum likelihood estimation: we choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x.\n\nThe resulting loss function is the negative log likelihood loss, generally called the cross-entropy loss.\n \n\n## SLP Chapter 5.4 Gradient Descent\n \nFor logistic regression, this loss function is conveniently convex.\n\nThe learning rate η is a hyperparameter that must be adjusted. \n \n\n## SLP Chapter 5.5 Regularization\n \nThis problem is called overfitting. A good model should be able to generalize well from the training data to the unseen test set, but a model that overfits will have poor generalization\n\nL1 regularization is a linear function of the weight values, named after the L1 norm ||W||1, the sum of the absolute values of the weights, or Manhattan distance\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n \nIn such cases we use multinomial logistic regression, also called softmax re- gression (or, historically, the maxent classifier).\n\n \n\n## SLP Chapter 7.1 Units\n \nAt its heart, a neural unit is taking a weighted sum of its inputs, with one addi- tional term in the sum called a bias term.\n\nFinally, instead of using z, a linear function of x, as the output, neural units apply a non-linear function f to z. We will refer to the output of this function as the activation value for the unit, a. \n\n\n \n\n## SLP Chapter 7.2 The XOR problem\n \n\nThis example was first shown for the perceptron, which is a very simple neural unit that has a binary output and does not have a non-linear activation function.\n\n \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n \nLet’s now walk through a slightly more formal presentation of the simplest kind of neural network, the feedforward network.\n\nFor historical reasons multilayer networks, especially feedforward networks, are sometimes called multi-layer perceptrons (or MLPs);\n\n \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n \nAs our second application of feedforward networks, let’s consider language model- ing\n\nForward inference is the task, given an input, of running a forward pass on the network to produce a probability distribution over possible outputs, in this case next words.\n\n \n\n## SLP Chapter 7.6 Training Neural Nets\n \nwe’ll need a loss function that models the distance between the system output and the gold output, and it’s common to use the loss function used for logistic regression, the cross-entropy loss.\n\nto find the parameters that minimize this loss function, we’ll use the gradient descent optimization algorithm introduced in Chapter 5.\n\nThe answer is the algorithm called error backpropagation or backward differentiation.\n\n \n\n## SLP Chapter 7.7 Training the neural language model\n \nThe cross-entropy loss that is used in neural networks is the same one we saw for logistic regression.\n\nAssume this is a hard classification task, meaning that only one class is the correct one, and that there is one output unit in y foreachclass. \n\n \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Logistic regression** - a supervised machine learning classifier that extracts real-valued features from the input, multiplies each by a weight, sums them, and passes the sum through a sigmoid function to generate a probability. A threshold is used to make a decision.\n* **Multinomial logistic regression** - uses the softmax function to compute proba- bilities.\n* **Cross-entropy loss** - The weights (vector w and bias b) are learned from a labeled training set via a loss function, such as the cross-entropy loss, that must be minimized.\n* **Regularization** - is used to avoid overfitting.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" \n",
        "We instantiate this intuition by using perplexity to measure the quality of a language model.\n",
        " \"\"\"\n",
        "slp_chapter9_2 = \"\"\" \n",
        "In this section, we consider a class of recurrent networks referred to as Elman Networks (Elman, 1990) or simple recurrent net- works. \n",
        "\n",
        "This general approach is commonly referred to as Backpropaga- tion Through Time \n",
        "\n",
        " \"\"\"\n",
        "slp_chapter9_3 = \"\"\" \n",
        "we always give the model the correct history sequence to predict the next word (rather than feeding the model its best case from the previous time step) is called teacher forcing.\n",
        "\n",
        "Weight tying is a method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers\n",
        " \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" \n",
        "In this section we summarize some of these desiderata, drawing on results in the linguistic study of word meaning, which is called lexical semantics;\n",
        "\n",
        "Here the form mouse is the lemma, also called the citation form.\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter6_2 = \"\"\" \n",
        "Vectors semantics is the standard way to represent word meaning in NLP, helping us model many of the aspects of word meaning we saw in the previous section. \n",
        "\n",
        "Vectors for representing words are called embeddings (although the term is sometimes more strictly applied only to dense vectors like word2vec (Section 6.8),\n",
        " \"\"\"\n",
        "slp_chapter6_3 = \"\"\" \n",
        "In a term-document matrix, each row represents a word in the vocabulary and each column represents a document from some collection of documents.\n",
        "\n",
        "Information retrieval (IR) is the task of finding the document d from the D documents in some collection that best matches a query q.\n",
        " \"\"\"\n",
        "slp_chapter6_4 = \"\"\" \n",
        "The cosine—like most measures for vector similarity used in NLP—is based on the dot product operator from linear algebra, also called the inner product\n",
        "\n",
        "This raw dot product, however, has a problem as a similarity metric: it favors long vectors.\n",
        " \"\"\"\n",
        "slp_chapter6_8 = \"\"\" \n",
        "We now introduce a more powerful word representation: embeddings, short dense vectors.\n",
        "\n",
        "In this section we introduce one method for computing embeddings: skip-gram with negative sampling, sometimes called SGNS.\n",
        " \"\"\"\n",
        "slp_chapter6_10 = \"\"\" \n",
        "Two words have first-order co-occurrence (sometimes called syntagmatic association) \n",
        " \"\"\"\n",
        "slp_chapter6_11 = \"\"\" \n",
        "For example African-American names like ‘Leroy’ and ‘Shaniqua’ had a higher GloVe cosine with unpleasant words while European-American names (‘Brad’, ‘Greg’, ‘Courtney’) had a higher cosine with pleasant words. These problems with embeddings are an example of a repre- sentational harm \n",
        " \"\"\"\n",
        "slp_chapter6_12 = \"\"\" \n",
        "Nonetheless it is useful to have intrinsic evaluations. The most common metric is to test their performance on similarity, computing the correlation between an algorithm’s word similarity scores and word similarity ratings assigned by humans.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"BPTT\" : \"RNNs can be trained with a straightforward extension of the backpropagation algorithm, known as backpropagation through time (BPTT).\",    \n",
        "\"vanishing gradients\": \"Simple recurrent networks fail on long inputs because of problems like vanishing gradients;\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "909ab257-9581-4e7d-ad13-960c3081f49c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n \nWe instantiate this intuition by using perplexity to measure the quality of a language model.\n \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n \nIn this section, we consider a class of recurrent networks referred to as Elman Networks (Elman, 1990) or simple recurrent net- works. \n\nThis general approach is commonly referred to as Backpropaga- tion Through Time \n\n \n\n## SLP Chapter 9.3 RNNs as Language Models\n \nwe always give the model the correct history sequence to predict the next word (rather than feeding the model its best case from the previous time step) is called teacher forcing.\n\nWeight tying is a method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers\n \n\n## SLP Chapter 6.1 Lexical Semantics\n \nIn this section we summarize some of these desiderata, drawing on results in the linguistic study of word meaning, which is called lexical semantics;\n\nHere the form mouse is the lemma, also called the citation form.\n\n \n\n## SLP Chapter 6.2 Vector Semantics\n \nVectors semantics is the standard way to represent word meaning in NLP, helping us model many of the aspects of word meaning we saw in the previous section. \n\nVectors for representing words are called embeddings (although the term is sometimes more strictly applied only to dense vectors like word2vec (Section 6.8),\n \n\n## SLP Chapter 6.3 Words and Vectors\n \nIn a term-document matrix, each row represents a word in the vocabulary and each column represents a document from some collection of documents.\n\nInformation retrieval (IR) is the task of finding the document d from the D documents in some collection that best matches a query q.\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n \nThe cosine—like most measures for vector similarity used in NLP—is based on the dot product operator from linear algebra, also called the inner product\n\nThis raw dot product, however, has a problem as a similarity metric: it favors long vectors.\n \n\n## SLP Chapter 6.8 Word2vec\n \nWe now introduce a more powerful word representation: embeddings, short dense vectors.\n\nIn this section we introduce one method for computing embeddings: skip-gram with negative sampling, sometimes called SGNS.\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \nTwo words have first-order co-occurrence (sometimes called syntagmatic association) \n \n\n## SLP Chapter 6.11 Bias and Embeddings\n \nFor example African-American names like ‘Leroy’ and ‘Shaniqua’ had a higher GloVe cosine with unpleasant words while European-American names (‘Brad’, ‘Greg’, ‘Courtney’) had a higher cosine with pleasant words. These problems with embeddings are an example of a repre- sentational harm \n \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \nNonetheless it is useful to have intrinsic evaluations. The most common metric is to test their performance on similarity, computing the correlation between an algorithm’s word similarity scores and word similarity ratings assigned by humans.\n \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Bptt** - RNNs can be trained with a straightforward extension of the backpropagation algorithm, known as backpropagation through time (BPTT).\n* **Vanishing gradients** - Simple recurrent networks fail on long inputs because of problems like vanishing gradients;\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "3435a849-1f5e-46ae-8005-c840aaff3f92"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Bellman equation' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n\naction = argmax EU (a|e)\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nWe can think of the set of outcomes for each action as a lottery—think of each action as a ticket. \n\nOrderability: Given any two lotteries, a rational agent must either prefer one to the other or else rate the two as equally preferable. \n\nTransitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C,\nthen the agent must prefer A to C.\n\nContinuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1 − p.\n\nSubstitutability: If an agent is indifferent between two lotteries A and B, then the\nagent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries.\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \n\nIf we want to build a decision-theoretic system that helps the agent make decisions or acts on his or her behalf, we must first work out what the agent’s utility function is. This process, often called preference elicitation.\n\n\n \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nWe assume for now that the environment is fully observable, so that the agent always knows where it is.\n\nWe will assume that transitions are Markovian in the sense of Chapter 15, that is, the probability of reaching s\u0002 from s depends only on s and not on the history of earlier states. \n\nTo sum up: a sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a Markov decision process,\n\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n \nBellman equation: the utility of a state is the immediate reward for that state plus the expected discounted utility of the next state, assuming that the agent chooses the optimal action\n\n \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - assigns a single number to express the desirability of a state.\n* **Expected utility** - The expected utility of an action given the evi- dence, EU (a|e), is just the average utility value of the outcomes\n* **Probability theory** - describes what an agent should believe on the basis of evidence\n* **Expert systems** - incorporate utility information have additional capabilities compared with pure inference systems.\n* **Markov decision process** - To sum up: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\n* **Bellman equation** - he utility of a state is the immediate reward for that state plus the expected discounted utility of the next state, assuming that the agent chooses the optimal action\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nPolicy iteration: alternates between calculating the utilities of states under the current policy and improving the current policy with respect to the current utilities.\n\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n \nThe task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the environment.\n\nA utility-based agent learns a utility function on states and uses it to select actions that maximize the expected outcome utility.\n\nA Q-learning agent learns an action-utility function, or Q-function, giving the ex- pected utility of taking a given action in a given state.\n\nA reflex agent learns a policy that maps directly from states to actions.\n\n \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \nThe passive learning task is similar to the policy evaluation task, part of the policy iteration algorithm \n\nAn adaptive dynamic programming (or ADP) agent takes advantage of the constraints among the utilities of states by learning the transition model that connects them and solv- ing the corresponding Markov decision process using a dynamic programming method.\n\n\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nAfter experimenting with minor variations, from the 276th trial onward it sticks to that policy, never learning the utilities of the other states and never finding the optimal route via (1,2), (1,3), and (2,3). We call this agent the greedy agent.\n\nTechnically, any such scheme needs to be greedy in the limit of infinite exploration, or GLIE. \n\nQ-learning, which learns an action-utility representation instead of learning utilities.\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \nOne way to handle such problems is to use function approximation, which simply means using any sort of representation for the Q-function other than a lookup table. \n\n\n\n \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Policy iteration** - it alternates between calculating the utilities of states under the current policy and improving the current policy with respect to the current utilities.\n* **Reinforcement learning** - The task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the environment.\n* **Policy search** - the idea is to keep twiddling the policy as long as its performance improves, then stop.\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n- Laziness: It is too much work to list the complete set of antecedents or consequents needed to ensure an exceptionless rule and too hard to use such rules.\n- Theoretical ignorance: Medical science has no complete theory for the domain.\n- Practical ignorance: Even if we know all the rules, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.\n\n \n\n## AIMA Chapter 12.2 Basic Probability Notation\n \nA fully specified probability model associates a numerical probability P (ω) with each possible world.\n\nVariables in probability theory are called random variables and their names begin with an uppercase letter. Thus, in the dice example, Total and Die1 are random variables. Every random variable has a domain—the set of possible values it can take on.\n\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \nIn this section we describe a simple method for probabilistic inference—that is, the compu- tation of posterior probabilities for query propositions given observed evidence.\n\nThis process is called marginalization, or summing out—because we sum up the probabilities for each possible value of the other variables, thereby taking them out of the equation.\n\n \n\n## AIMA Chapter 12.4 Independence\n \nThe property we used in Equation (13.10) is called independence (also marginal in- dependence and absolute independence). \n\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n \n\nP(b|a) = P(a|b)P(b)/P(a)\n\nThis equation is known as Bayes’ rule (also Bayes’ law or Bayes’ theorem). \n\nBayes’ rule allows unknown probabilities to be computed from known conditional probabilities, usually in the causal direction. Applying Bayes’ rule with many pieces of evidence runs into the same scaling problems as does the full joint distribution.\n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nConditional independence brought about by direct causal relationships in the domain might allow the full joint distribution to be factored into smaller, conditional distri- butions. The naive Bayes model assumes the conditional independence of all effect variables, given a single cause variable, and grows linearly with the number of effects.\n\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n \nA wumpus-world agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable.\n\n\n\n## SLP Chapter 3.1 N-Grams\n \nA model of the probability distribution of n-letter sequences is thus called an n-gram model.\n\nAn n-gram model is defined as a Markov chain of order n − 1.\n\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n\ntext classification, also known as categorization: given a text of some kind, decide which of a predefined set of classes it belongs to.\n\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n \n\nInformation retrieval: is the task of finding documents that are relevant to a user’s need for information. \n\nA corpus of documents. Each system must decide what it wants to treat as a document: a paragraph, a page, or a multipage text.\n\nQueries posed in a query language. A query specifies what the user wants to know. The query language can be just a list of words, such as [AI book];\n\nA result set. This is the subset of documents that the IR system judges to be relevant to the query.\n\nA presentation of the result set. This can be as simple as a ranked list of document titles or as complex as a rotating color map of the result set projected onto a three- dimensional space, rendered as a two-dimensional display.\n\n \n\n## SLP Chapter 3.4 Generalization and Zeros\n \n\nInformation extraction is the process of acquiring knowledge by skimming a text and look- ing for occurrences of a particular class of object and for relationships among objects.\n\n \n\n## SLP Chapter 3.5 Smoothing\n \nThis modification is called smoothing or discounting. In this section and the fol- lowing ones we’ll introduce a variety of ways to do smoothing: Laplace (add-one) smoothing, add-k smoothing, stupid backoff, and Kneser-Ney smoothing.\n\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n \nStupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. \n \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **N-gram model** - A model of the probability distribution of n-letter sequences is thus called an n-gram model.\n* **Text classification** - also known as categorization: given a text of some kind, decide which of a predefined set of classes it belongs to.\n* **Information retrieval** - the task of finding documents that are relevant to a user’s need for information. \n* **Information extraction** - the process of acquiring knowledge by skimming a text and look- ing for occurrences of a particular class of object and for relationships among objects.\n\n\n## WARNING: Your definition of 'Bayesian network' is too long!\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \nBayesian networks can represent essentially any full joint probability distribution and in many cases can do so very concisely.\n\nThis is the most common name, but there are many synonyms, including belief network, probabilistic net- work, causal network, and knowledge map. In statistics, the term graphical model refers to a somewhat broader class that includes Bayesian networks. An extension of Bayesian networks called a decision network or influence diagram is covered in Chapter 16.\n\nThe conditional distributions in Figure 14.2 are shown as a conditional probability table, or CPT. (This form of table can be used for discrete variables; other representations, including those suitable for continuous variables, are described in Section 14.2.) Each row in a CPT contains the conditional probability of each node value for a conditioning case.\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \nThe compactness of Bayesian net- works is an example of a general property of locally structured (also called sparse) systems.\n\nThis phenomenon is quite general and is related to the distinction between causal and diagnostic models intro- duced in Section 13.5.1 (see also Exercise 8.13). \n\nAnother important independence property is implied by the topological semantics: a node is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket. \n\n\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n\nUsually, such relationships are describable by a canonical distribution that fits some standard pattern. In such cases, the complete table can be specified by naming the pattern and perhaps supplying a few parameters—much easier than supplying an exponential number of parameters.\n\nThe simplest example is provided by deterministic nodes.\n\n\n \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Bayesian network** - A Bayesian network is a directed acyclic graph whose nodes correspond to random variables; each node has a conditional distribution for the node, given its parents.\n* **Conditional independence** - Bayesian networks provide a concise way to represent conditional independence rela- tionships in the domain.\n\n\n## WARNING: Your definition of 'Computational learning theory' is too long!\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n \nWe will see in Chapter 19 that we can also do analytical or deductive learning: going from a known general rule to a new rule that is logically entailed, but is useful because it allows more efficient processing.\n\nIn reinforcement learning the agent learns from a series of reinforcements—rewards or punishments. \n\nIn supervised learning the agent observes some example input–output pairs and learns a function that maps from input to output.\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nWhen the output y is one of a finite set of values (such as sunny, cloudy or rainy), the learning problem is called classification, and is called Boolean or binary classification if there are only two values.\n\nWhen y is a number (such as tomorrow’s temperature), the learning problem is called regression. \n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nA decision tree represents a function that takes as input a vector of attribute values and returns a “decision”—a single output value. \n\nThis problem is called overfitting. A general phenomenon, overfitting occurs with all types of learners, even when the target function is not at all random.\n\nWe can answer this question by using a statistical significance test. Such a test begins by assuming that there is no underlying pattern (the so-called null hypothesis).\n\nMissing data: In many domains, not all the attribute values will be known for every example. The values might have gone unrecorded, or they might be too expensive to obtain.\n\nMultivalued attributes: When an attribute has many possible values, the information gain measure gives an inappropriate indication of the attribute’s usefulness.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nTo make that precise we need to define “future data” and “best.” We make the stationarity assumption: that there is a probability distribution over examples that remains stationary over time.\n\nWe can squeeze more out of the data and still get an accurate estimate using a technique called k-fold cross-validation.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe underlying principle is that any hypothesis that is seri- ously wrong will almost certainly be “found out” with high probability after a small number of examples, because it will make an incorrect prediction. Thus, any hypothesis that is consis- tent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct.\n\nAny learning algorithm that returns hypotheses that are probably approximately correct is called a PAC learning algorithm; we can use this approach to provide bounds on the performance of various learning algorithms.\n\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nthe class of linear functions of continuous-valued inputs\n\nThe task of finding the hw that best fits these data is called linear regression.\n\n\n\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n \nmultinomial naive Bayes classifier, so called be- cause it is a Bayesian classifier that makes a simplifying (naive) assumption about how the features interact.\n\nWe represent a text document as if it were a bag-of-words, that is, an unordered set of words with their position ignored, keeping only their frequency in the document.\n\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n \nFinally, some systems choose to completely ignore another class of words: stop words, very frequent words like the and a.\n\nThe solution for such unknown words is to ignore them—remove them from the test document and not include any probability for them at all.\n \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \nmultinomial naive Bayes or binary NB. The variant uses the same Eq. 4.10 except that for each document we remove all duplicate words before concatenating them into the single big document.\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n \nConsider the task of spam detection, deciding if a particular piece of email is an example of spam (unsolicited bulk email) — and one of the first applications of naive Bayes to text classification\n\n \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n \nSince the likelihood features from the naive Bayes model assign a probability to each word P(word|c), the model also assigns a probability to each sentence:\n\n \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n \nWe also need to know whether the email is actually spam or not, i.e. the human-defined labels for each document that we are trying to match. We will refer to these human labels as the gold labels.\n\nPrecision measures the percentage of the items that the system detected (i.e., the system labeled as positive) that are in fact positive (i.e., are positive according to the human gold labels).\n\nRecall measures the percentage of items actually present in the input that were correctly identified by the system.\n \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n \n we use the training set to train the model, then use the development test set (also called a devset) to perhaps tune some parameters,\n  \n\n## SLP Chapter 4.9 Statistical Significance Testing\n \nWe say that a result (e.g., “A is better than B”) is statistically significant if the δ we saw has a probability that is below the threshold and we therefore reject this null hypothesis.\n\nThere are two common non-parametric tests used in NLP: approximate ran- domization (Noreen, 1989) and the bootstrap test.\n \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n \nOne class of harms is representational harms\n \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Supervised learning.** - If the available feedback provides the correct answer for example inputs, then the learn- ing problem is called supervised learning.\n* **Classification** - The task is to learn a function y = h(x). Learning a discrete-valued function is called classification;\n* **Regression** - learning a continuous function \n* **Ockham’s razor** - Inductive learning involves finding a hypothesis that agrees well with the examples. Ockham’s razor suggests choosing the simplest consistent hypothesis. \n* **Decision trees** - Decision trees can represent all Boolean functions.\n* **Computational learning theory** - Computational learning theory analyzes the sample complexity and computational complexity of inductive learning. There is a tradeoff between the expressiveness of the hypothesis language and the ease of learning.\n\n\n## WARNING: Your definition of 'Logistic regression' is too long!\nWARNING: Your definition of 'cross-entropy loss' is too long!\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nLogistic regression solves this task by learning, from a training set, a vector of weights and a bias term. \n\nThe bias term, also called the intercept, is another real number that’s added to the weighted inputs.\n\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nIn the next section we’ll introduce the loss function that is commonly used for logistic regression and also for neural networks, the cross-entropy loss.\n\nThe standard algorithm for this is gradient descent; we’ll introduce the stochastic gradient descent algorithm in the following section.\n \n\n## SLP Chapter 5.3 The cross-entropy loss function\n \nThis is called conditional maximum likelihood estimation: we choose the parameters w,b that maximize the log probability of the true y labels in the training data given the observations x.\n\nThe resulting loss function is the negative log likelihood loss, generally called the cross-entropy loss.\n \n\n## SLP Chapter 5.4 Gradient Descent\n \nFor logistic regression, this loss function is conveniently convex.\n\nThe learning rate η is a hyperparameter that must be adjusted. \n \n\n## SLP Chapter 5.5 Regularization\n \nThis problem is called overfitting. A good model should be able to generalize well from the training data to the unseen test set, but a model that overfits will have poor generalization\n\nL1 regularization is a linear function of the weight values, named after the L1 norm ||W||1, the sum of the absolute values of the weights, or Manhattan distance\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n \nIn such cases we use multinomial logistic regression, also called softmax re- gression (or, historically, the maxent classifier).\n\n \n\n## SLP Chapter 7.1 Units\n \nAt its heart, a neural unit is taking a weighted sum of its inputs, with one addi- tional term in the sum called a bias term.\n\nFinally, instead of using z, a linear function of x, as the output, neural units apply a non-linear function f to z. We will refer to the output of this function as the activation value for the unit, a. \n\n\n \n\n## SLP Chapter 7.2 The XOR problem\n \n\nThis example was first shown for the perceptron, which is a very simple neural unit that has a binary output and does not have a non-linear activation function.\n\n \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n \nLet’s now walk through a slightly more formal presentation of the simplest kind of neural network, the feedforward network.\n\nFor historical reasons multilayer networks, especially feedforward networks, are sometimes called multi-layer perceptrons (or MLPs);\n\n \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n \nAs our second application of feedforward networks, let’s consider language model- ing\n\nForward inference is the task, given an input, of running a forward pass on the network to produce a probability distribution over possible outputs, in this case next words.\n\n \n\n## SLP Chapter 7.6 Training Neural Nets\n \nwe’ll need a loss function that models the distance between the system output and the gold output, and it’s common to use the loss function used for logistic regression, the cross-entropy loss.\n\nto find the parameters that minimize this loss function, we’ll use the gradient descent optimization algorithm introduced in Chapter 5.\n\nThe answer is the algorithm called error backpropagation or backward differentiation.\n\n \n\n## SLP Chapter 7.7 Training the neural language model\n \nThe cross-entropy loss that is used in neural networks is the same one we saw for logistic regression.\n\nAssume this is a hard classification task, meaning that only one class is the correct one, and that there is one output unit in y foreachclass. \n\n \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Logistic regression** - a supervised machine learning classifier that extracts real-valued features from the input, multiplies each by a weight, sums them, and passes the sum through a sigmoid function to generate a probability. A threshold is used to make a decision.\n* **Multinomial logistic regression** - uses the softmax function to compute proba- bilities.\n* **Cross-entropy loss** - The weights (vector w and bias b) are learned from a labeled training set via a loss function, such as the cross-entropy loss, that must be minimized.\n* **Regularization** - is used to avoid overfitting.\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n \nWe instantiate this intuition by using perplexity to measure the quality of a language model.\n \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n \nIn this section, we consider a class of recurrent networks referred to as Elman Networks (Elman, 1990) or simple recurrent net- works. \n\nThis general approach is commonly referred to as Backpropaga- tion Through Time \n\n \n\n## SLP Chapter 9.3 RNNs as Language Models\n \nwe always give the model the correct history sequence to predict the next word (rather than feeding the model its best case from the previous time step) is called teacher forcing.\n\nWeight tying is a method that dispenses with this redundancy and uses a single set of embeddings at the input and softmax layers\n \n\n## SLP Chapter 6.1 Lexical Semantics\n \nIn this section we summarize some of these desiderata, drawing on results in the linguistic study of word meaning, which is called lexical semantics;\n\nHere the form mouse is the lemma, also called the citation form.\n\n \n\n## SLP Chapter 6.2 Vector Semantics\n \nVectors semantics is the standard way to represent word meaning in NLP, helping us model many of the aspects of word meaning we saw in the previous section. \n\nVectors for representing words are called embeddings (although the term is sometimes more strictly applied only to dense vectors like word2vec (Section 6.8),\n \n\n## SLP Chapter 6.3 Words and Vectors\n \nIn a term-document matrix, each row represents a word in the vocabulary and each column represents a document from some collection of documents.\n\nInformation retrieval (IR) is the task of finding the document d from the D documents in some collection that best matches a query q.\n \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n \nThe cosine—like most measures for vector similarity used in NLP—is based on the dot product operator from linear algebra, also called the inner product\n\nThis raw dot product, however, has a problem as a similarity metric: it favors long vectors.\n \n\n## SLP Chapter 6.8 Word2vec\n \nWe now introduce a more powerful word representation: embeddings, short dense vectors.\n\nIn this section we introduce one method for computing embeddings: skip-gram with negative sampling, sometimes called SGNS.\n \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \nTwo words have first-order co-occurrence (sometimes called syntagmatic association) \n \n\n## SLP Chapter 6.11 Bias and Embeddings\n \nFor example African-American names like ‘Leroy’ and ‘Shaniqua’ had a higher GloVe cosine with unpleasant words while European-American names (‘Brad’, ‘Greg’, ‘Courtney’) had a higher cosine with pleasant words. These problems with embeddings are an example of a repre- sentational harm \n \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \nNonetheless it is useful to have intrinsic evaluations. The most common metric is to test their performance on similarity, computing the correlation between an algorithm’s word similarity scores and word similarity ratings assigned by humans.\n \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Bptt** - RNNs can be trained with a straightforward extension of the backpropagation algorithm, known as backpropagation through time (BPTT).\n* **Vanishing gradients** - Simple recurrent networks fail on long inputs because of problems like vanishing gradients;\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "HFWXtfHJx99_"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}