{
  "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": "87c6337c-0a3c-4da9-a1be-ca8a306bc199"
      },
      "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": "a8181af5-7ae5-4664-8abd-551066c84606"
      },
      "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 = \"\"\" ecision theory, in its simplest form, deals with choosing among actions based on the desir\u0002ability of their immediate outcomes; that is, the environment is assumed to be episodic.\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the\n",
        "right thing,” but does not operationalize that advice.\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"  Constraints on rational preferences:1. Orderability:  (A ≻ B), (B ≻ A), or (A ∼ B);2.Transitivity:(A ≻ B)∧(B ≻ C) ⇒ (A ≻ C).\n",
        "3. Continuity:A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B. 4. Substitutability: A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B; 1− p,C].\n",
        "5.  Monotonicity: A ≻ B ⇒ (p > q ⇔ [p,A; 1− p,B] ≻ [q,A; 1−q,B]). 6. Decomposability: [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C].\n",
        "Rational preferences lead to utility: Existence of Utility Function:U(A) > U(B) ⇔ A ≻ B and U(A) = U(B) ⇔ A ∼ B.\n",
        "Expected Utility of a Lottery: U([p1,S1;...; pn,Sn]) = ∑_{i}piU(Si).\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\"Typically, we fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible\n",
        "catastrophe” at U(S) = u⊥.\n",
        "expected monetary value (EMV)\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Because the decision problem is sequential, the utility function will depend\n",
        "on a sequence of states and actions—an environment history—rather than on a single state.\n",
        "MDP, and consists of a set of states (with an initial state s0); a set ACTIONS(s) of actions\n",
        "in each state; a transition model P(s′|s,a); and a reward function R(s,a,s′). Methods for\n",
        "solving MDPs usually involve dynamic programming.\n",
        "A policy that depends on the time is called nonstationary.\n",
        "additive discounted rewards: the utility of a history is Additive discounted\n",
        "reward Uh([s0,a0,s1,a1,s2,...]) = R(s0,a0,s1) +γR(s1,a1,s2) +γ^2R(s2,a2,s3) +··· , where the discount factor γ is a number between 0 and 1.\n",
        "When γ is close to 0, rewards in the distant future are viewed as insignificant. When γ is close to 1, an agent is more willing\n",
        "to wait for long-term rewards.When γ is exactly 1, discounted rewards reduce to the special case of purely additive rewards. \"\"\"\n",
        "chapter17_2 =  \"\"\" Algorithms for MDPs: value iteration, policy iteration, and linear programming.\n",
        "Value Iteration:The Bellman equation  is the basis of the value iteration.\n",
        "The basic concept used in showing that value iteration converges is the notion of a contraction.\n",
        " two important properties\n",
        "of contractions:\n",
        "• A contraction has only one fixed point; if there were two fixed points they would not\n",
        "get closer together when the function was applied, so it would not be a contraction.\n",
        "• When the function is applied to any argument, the value must get closer to the fixed\n",
        "point (because the fixed point does not move), so repeated application of a contraction\n",
        "always reaches the fixed point in the limit.\n",
        " The policy iteration algorithm alternates\n",
        "the following two steps, beginning from some initial policy π0:\n",
        "• Policy evaluation: given a policy πi\n",
        ", calculate Ui =U\n",
        "πi Policy evaluation , the utility of each state if πi\n",
        "were to be executed.\n",
        "Policy improvement • Policy improvement: Calculate a new MEU policy πi+1, using one-step look-ahead\n",
        "based on Ui.\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"The value (utility) of a state s: V*(s) = expected utility starting in s and acting optimally\n",
        "▪ The value (utility) of a q-state (s,a):Q*(s,a) = expected utility starting out \n",
        "having taken action a from state s and (thereafter) acting optimally\n",
        "▪ The optimal policy:π*(s) = optimal action from state s\n",
        "Problems with Value Iteration:Problem 1: It’s slow – O(S2A) per iteration\n",
        "Problem 2: The “max” at each state rarely changes\n",
        "Problem 3: The policy often converges long before the values.\n",
        "policy iteration: It’s still optimal! Can converge (much) faster under some conditions\n",
        "Comparison\n",
        "Both value iteration and policy iteration compute the same thing (all optimal values)\n",
        "In value iteration:\n",
        "• Every iteration updates both the values and (implicitly) the policy\n",
        "• We don’t track the policy, but taking the max over actions implicitly recomputes it\n",
        "In policy iteration:\n",
        "• We do several passes that update utilities with fixed policy (each pass is fast \n",
        "because we consider only one action, not all of them)\n",
        "• After the policy is evaluated, a new policy is chosen (slow like a value iteration \n",
        "pass)\n",
        "• The new policy will be better (or we’re done)\n",
        "Utilities are functions from outcomes (states  of the world) to real numbers that describe an agent’s preferences\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"which assigns a single number to express the Utility function desirability of a state\",\n",
        "\"expected utility\" : \"n action given the evidence, EU(a), is just the Expected utility average utility value of the outcomes\",\n",
        "\"value function or ordinal utility function.\": \"As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\",\n",
        "\"preference elicitation\":\"presenting choices to the human and using the Preference elicitation observed preferences to pin down the underlying utility function\",\n",
        "\"Normalized utilities\":\"scale with u⊥ = 0 and u⊤ = 1\",\n",
        "\"standard lottery\":\"[p,u⊤; (1− p),u⊥]\",\n",
        "\"Markovian\":\"the probability of reaching s′ from s depends only on s and not on the history of earlier states.\",\n",
        "\"Markov decision process\":\" a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\",\n",
        "\"optimal policy π∗\":\"a policy that yields the highest expected utility\",\n",
        "\"\":\"\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "3a27dc8b-2e49-4fe3-cf90-87f264d05202"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n ecision theory, in its simplest form, deals with choosing among actions based on the desir\u0002ability of their immediate outcomes; that is, the environment is assumed to be episodic.\nThe MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice. $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n  Constraints on rational preferences:1. Orderability:  (A ≻ B), (B ≻ A), or (A ∼ B);2.Transitivity:(A ≻ B)∧(B ≻ C) ⇒ (A ≻ C).\n3. Continuity:A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B. 4. Substitutability: A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B; 1− p,C].\n5.  Monotonicity: A ≻ B ⇒ (p > q ⇔ [p,A; 1− p,B] ≻ [q,A; 1−q,B]). 6. Decomposability: [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C].\nRational preferences lead to utility: Existence of Utility Function:U(A) > U(B) ⇔ A ≻ B and U(A) = U(B) ⇔ A ∼ B.\nExpected Utility of a Lottery: U([p1,S1;...; pn,Sn]) = ∑_{i}piU(Si).\n \n\n## AIMA Chapter 16.3 Utility Functions\nTypically, we fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible\ncatastrophe” at U(S) = u⊥.\nexpected monetary value (EMV)\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Because the decision problem is sequential, the utility function will depend\non a sequence of states and actions—an environment history—rather than on a single state.\nMDP, and consists of a set of states (with an initial state s0); a set ACTIONS(s) of actions\nin each state; a transition model P(s′|s,a); and a reward function R(s,a,s′). Methods for\nsolving MDPs usually involve dynamic programming.\nA policy that depends on the time is called nonstationary.\nadditive discounted rewards: the utility of a history is Additive discounted\nreward Uh([s0,a0,s1,a1,s2,...]) = R(s0,a0,s1) +γR(s1,a1,s2) +γ^2R(s2,a2,s3) +··· , where the discount factor γ is a number between 0 and 1.\nWhen γ is close to 0, rewards in the distant future are viewed as insignificant. When γ is close to 1, an agent is more willing\nto wait for long-term rewards.When γ is exactly 1, discounted rewards reduce to the special case of purely additive rewards. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Algorithms for MDPs: value iteration, policy iteration, and linear programming.\nValue Iteration:The Bellman equation  is the basis of the value iteration.\nThe basic concept used in showing that value iteration converges is the notion of a contraction.\n two important properties\nof contractions:\n• A contraction has only one fixed point; if there were two fixed points they would not\nget closer together when the function was applied, so it would not be a contraction.\n• When the function is applied to any argument, the value must get closer to the fixed\npoint (because the fixed point does not move), so repeated application of a contraction\nalways reaches the fixed point in the limit.\n The policy iteration algorithm alternates\nthe following two steps, beginning from some initial policy π0:\n• Policy evaluation: given a policy πi\n, calculate Ui =U\nπi Policy evaluation , the utility of each state if πi\nwere to be executed.\nPolicy improvement • Policy improvement: Calculate a new MEU policy πi+1, using one-step look-ahead\nbased on Ui.\n \n\n## Module 8 Lecture Notes\nThe value (utility) of a state s: V*(s) = expected utility starting in s and acting optimally\n▪ The value (utility) of a q-state (s,a):Q*(s,a) = expected utility starting out \nhaving taken action a from state s and (thereafter) acting optimally\n▪ The optimal policy:π*(s) = optimal action from state s\nProblems with Value Iteration:Problem 1: It’s slow – O(S2A) per iteration\nProblem 2: The “max” at each state rarely changes\nProblem 3: The policy often converges long before the values.\npolicy iteration: It’s still optimal! Can converge (much) faster under some conditions\nComparison\nBoth value iteration and policy iteration compute the same thing (all optimal values)\nIn value iteration:\n• Every iteration updates both the values and (implicitly) the policy\n• We don’t track the policy, but taking the max over actions implicitly recomputes it\nIn policy iteration:\n• We do several passes that update utilities with fixed policy (each pass is fast \nbecause we consider only one action, not all of them)\n• After the policy is evaluated, a new policy is chosen (slow like a value iteration \npass)\n• The new policy will be better (or we’re done)\nUtilities are functions from outcomes (states  of the world) to real numbers that describe an agent’s preferences\n \n\n## Module 8 Definitions\n* **Utility function** - which assigns a single number to express the Utility function desirability of a state\n* **Expected utility** - n action given the evidence, EU(a), is just the Expected utility average utility value of the outcomes\n* **Value function or ordinal utility function.** - As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\n* **Preference elicitation** - presenting choices to the human and using the Preference elicitation observed preferences to pin down the underlying utility function\n* **Normalized utilities** - scale with u⊥ = 0 and u⊤ = 1\n* **Standard lottery** - [p,u⊤; (1− p),u⊥]\n* **Markovian** - the probability of reaching s′ from s depends only on s and not on the history of earlier states.\n* **Markov decision process** -  a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\n* **Optimal policy π∗** - a policy that yields the highest expected utility\n* **** - \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 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Model-based reinforcement learning: In these approaches the agent uses a transition\n",
        "learning model of the environment to help interpret the reward signals and to make decisions\n",
        "about how to act. The model may be initially unknown, in which case the agent learns\n",
        "the model from observing the effects of its actions, or it may already be known—for\n",
        "example, a chess program may know the rules of chess even if it does not know how\n",
        "to choose good moves.\n",
        "\n",
        "Model-free reinforcement learning: In these approaches the agent neither knows nor learning learns a transition model for the environment. Instead, it learns a more direct represen\u0002tation of how to behave. This comes in one of two varieties:\n",
        "• Action-utility learning: We introduced action-utility functions in Chapter 17. The Action-utility\n",
        "learning\n",
        "Q-learning most common form of action-utility learning is Q-learning, where the agent learns\n",
        "Q-function a Q-function, or quality-function, Q(s,a), denoting the sum of rewards from state\n",
        "s onward if action a is taken. Given a Q-function, the agent can choose what to do\n",
        "in s by finding the action with the highest Q-value.\n",
        "Policy search • Policy search: The agent learns a policy π(s) that maps directly from states to\n",
        "actions. In the terminology of Chapter 2, this a reflex agent. \"\"\"\n",
        "chapter22_2 =  \"\"\"passive learning agent: a fully observable environment with a small number of\n",
        "actions and states, in which an agent already has a fixed policy π(s) that determines its actions.\n",
        "The agent is trying to learn the utility function Uπ(s)—the expected total discounted reward if policy π is executed beginning in state s.\n",
        "he idea of direct utility estimation is that the utility of a state is defined as the expected Direct utility\n",
        "estimation\n",
        "\n",
        "Reward-to-go total reward from that state onward (called the expected reward-to-go), and that each trial\n",
        "provides a sample of this quantity for each state visited.\n",
        "Adaptive dynamic programming:n adaptive dynamic programming (or ADP) agent takes advantage of the constraints \n",
        "among the utilities of states by learning the transition model that connects them and solv\u0002ing the corresponding Markov decision process using dynamic programming.\n",
        "Temporal-difference learning: Big idea: learn from every experience!\n",
        "Update V(s) each time we experience a transition (s, a, s’, r)\n",
        "Likely outcomes s’ will contribute updates more often\n",
        "Temporal difference learning of values\n",
        "Policy still fixed, still doing evaluation!\n",
        "Move values toward value of whatever successor occurs: running average\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"Active Reinforcement Learning: A passive learning agent has a fixed policy that determines its behavior. An active learning\n",
        "agent gets to decide what actions to take. \n",
        " Temporal-difference Q-learning: The Q-learning method avoids the need for a model by learning an action-utility function\n",
        "Q(s,a) instead of a utility function U(s). Q(s,a) denotes the expected total discounted reward\n",
        "if the agent takes action a in s and acts optimally thereafter. Knowing the Q-function enables\n",
        "the agent to act optimally simply by choosing argmaxa Q(s,a), with no need for look-ahead\n",
        "based on a transition model\"\"\"\n",
        "chapter22_4 =  \"\"\" Generalization in Reinforcement Learning: When the learning agent is responsible for selecting actions while it learns, it must\n",
        "trade off the estimated value of those actions against the potential for learning useful\n",
        "new information. An exact solution for the exploration problem is infeasible, but some\n",
        "simple heuristics do a reasonable job. An exploring agent must also take care to avoid\n",
        "premature death.\n",
        "• In large state spaces, reinforcement learning algorithms must use an approximate func\u0002tional representation of U(s) or Q(s,a) in order to generalize over states. Deep re\u0002inforcement learning—using deep neural networks as function approximators—has\n",
        "achieved considerable success on hard problems.\n",
        "• Reward shaping and hierarchical reinforcement learning are helpful for learning\n",
        "complex behaviors, particularly when rewards are sparse and long action sequences are\n",
        "required to obtain them\n",
        " \"\"\"\n",
        "chapter22_5 =  \"\"\"For this reason, policy search\n",
        "methods often use a stochastic policy representation πθ(s,a), which specifies the probability Stochastic policy\n",
        "of selecting action a in state s. One popular representation is the softmax function: \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"  reinforcement learning:\n",
        "Exploration: you have to try unknown actions to get information\n",
        "Exploitation: eventually, you have to use what you know\n",
        "Regret: even if you learn intelligently, you make mistakes\n",
        "Sampling: because of chance, you have to try things repeatedly\n",
        "Difficulty: learning can be much harder than solving a known MDP\n",
        "Model-Based Learning:Step 1: Learn empirical MDP model\n",
        "Count outcomes s’ for each s, a Normalize to give an estimate of\n",
        "Discover each when we experience (s, a, s’)\n",
        "Step 2: Solve the learned MDP\n",
        "For example, use value iteration, as before \n",
        "What bad about direct evaluation?\n",
        "It wastes information about state connections\n",
        "Each state must be learned separately\n",
        "So, it takes a long time to learn.\n",
        "Temporal difference learning of values:\n",
        "Policy still fixed, still doing evaluation!Move values toward value of whatever successor occurs: running average.\n",
        "TD value leaning is a model-free way to do policy evaluation, mimicking \n",
        "Bellman updates with running sample averages\n",
        "However, if we want to turn values into a (new) policy, we’re sunk\n",
        "\n",
        "Exponential Moving Average:Makes recent samples more important.Decreasing learning rate (alpha) can give converging averages\n",
        "Active Reinforcement Learning: learn the optimal policy / values,Fundamental tradeoff: exploration vs. exploitation\n",
        "This is NOT offline planning! You actually take actions in the world and find out what happens…\n",
        "Q-Learning:Learn Q(s,a) values as you go, off-policy learning\n",
        "Receive a sample (s,a,s’,r)\n",
        "Consider your old estimate:\n",
        "Consider your new sample estimate:\n",
        "Incorporate the new estimate into a running average\n",
        "\n",
        "When to explore?\n",
        "Random actions: explore a fixed amount\n",
        "Better idea: explore areas whose badness is not\n",
        "(yet) established, eventually stop exploring\n",
        "\n",
        " generalize:\n",
        "Learn about some small number of training states from \n",
        "experience\n",
        "Generalize that experience to new, similar situations\n",
        "\n",
        "Linear Value Functions:Advantage: our experience is summed up in a few powerful numbers\n",
        "Disadvantage: states may share features but actually be very different in value!\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"reinforcement learning\" : \" in which an agent interacts with the world and periodically receives rewards that reflect how well it is doing\",\n",
        "\"sparse rewards\":\"in the vast majority of states the agent is given no informative reward signal at all(e.g. chess and racing)\",\n",
        "\"Passive Reinforcement Learning\":\"\",\n",
        "\"direct evaluation\":\"Act according to π Every time you visit a state, write down what the sum of discounted rewards turned out to be, Average those samples\",\n",
        "\"Sample-Based Policy Evaluation\":\" Take samples of outcomes s’ (by doing the action!) and average\",\n",
        "\"Temporal Difference Learning\":\" learn from every experience!Update V(s) each time we experience a transition (s, a, s’, r).Likely outcomes s’ will contribute updates more often\",\n",
        "\"Q-Value Iteration\":\"Start with Q0(s,a) = 0, which we know is right. Given Qk, calculate the depth k+1 q-values for all q-states\",\n",
        "\"Q-Learning\":\"sample-based Q-value iteration\",\n",
        "\"Exploration Functions\":\"Takes a value estimate u and a visit count n, and returns an optimistic utility\",\n",
        "\"Regret\":\" a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5bbb32f6-dd11-4b27-fc9b-c5b51e00949f"
      },
      "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 Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Model-based reinforcement learning: In these approaches the agent uses a transition\nlearning model of the environment to help interpret the reward signals and to make decisions\nabout how to act. The model may be initially unknown, in which case the agent learns\nthe model from observing the effects of its actions, or it may already be known—for\nexample, a chess program may know the rules of chess even if it does not know how\nto choose good moves.\n\nModel-free reinforcement learning: In these approaches the agent neither knows nor learning learns a transition model for the environment. Instead, it learns a more direct represen\u0002tation of how to behave. This comes in one of two varieties:\n• Action-utility learning: We introduced action-utility functions in Chapter 17. The Action-utility\nlearning\nQ-learning most common form of action-utility learning is Q-learning, where the agent learns\nQ-function a Q-function, or quality-function, Q(s,a), denoting the sum of rewards from state\ns onward if action a is taken. Given a Q-function, the agent can choose what to do\nin s by finding the action with the highest Q-value.\nPolicy search • Policy search: The agent learns a policy π(s) that maps directly from states to\nactions. In the terminology of Chapter 2, this a reflex agent. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\npassive learning agent: a fully observable environment with a small number of\nactions and states, in which an agent already has a fixed policy π(s) that determines its actions.\nThe agent is trying to learn the utility function Uπ(s)—the expected total discounted reward if policy π is executed beginning in state s.\nhe idea of direct utility estimation is that the utility of a state is defined as the expected Direct utility\nestimation\n\nReward-to-go total reward from that state onward (called the expected reward-to-go), and that each trial\nprovides a sample of this quantity for each state visited.\nAdaptive dynamic programming:n adaptive dynamic programming (or ADP) agent takes advantage of the constraints \namong the utilities of states by learning the transition model that connects them and solv\u0002ing the corresponding Markov decision process using dynamic programming.\nTemporal-difference learning: Big idea: learn from every experience!\nUpdate V(s) each time we experience a transition (s, a, s’, r)\nLikely outcomes s’ will contribute updates more often\nTemporal difference learning of values\nPolicy still fixed, still doing evaluation!\nMove values toward value of whatever successor occurs: running average\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nActive Reinforcement Learning: A passive learning agent has a fixed policy that determines its behavior. An active learning\nagent gets to decide what actions to take. \n Temporal-difference Q-learning: The Q-learning method avoids the need for a model by learning an action-utility function\nQ(s,a) instead of a utility function U(s). Q(s,a) denotes the expected total discounted reward\nif the agent takes action a in s and acts optimally thereafter. Knowing the Q-function enables\nthe agent to act optimally simply by choosing argmaxa Q(s,a), with no need for look-ahead\nbased on a transition model\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Generalization in Reinforcement Learning: When the learning agent is responsible for selecting actions while it learns, it must\ntrade off the estimated value of those actions against the potential for learning useful\nnew information. An exact solution for the exploration problem is infeasible, but some\nsimple heuristics do a reasonable job. An exploring agent must also take care to avoid\npremature death.\n• In large state spaces, reinforcement learning algorithms must use an approximate func\u0002tional representation of U(s) or Q(s,a) in order to generalize over states. Deep re\u0002inforcement learning—using deep neural networks as function approximators—has\nachieved considerable success on hard problems.\n• Reward shaping and hierarchical reinforcement learning are helpful for learning\ncomplex behaviors, particularly when rewards are sparse and long action sequences are\nrequired to obtain them\n \n\n## Module 9 Lecture Notes\n  reinforcement learning:\nExploration: you have to try unknown actions to get information\nExploitation: eventually, you have to use what you know\nRegret: even if you learn intelligently, you make mistakes\nSampling: because of chance, you have to try things repeatedly\nDifficulty: learning can be much harder than solving a known MDP\nModel-Based Learning:Step 1: Learn empirical MDP model\nCount outcomes s’ for each s, a Normalize to give an estimate of\nDiscover each when we experience (s, a, s’)\nStep 2: Solve the learned MDP\nFor example, use value iteration, as before \nWhat bad about direct evaluation?\nIt wastes information about state connections\nEach state must be learned separately\nSo, it takes a long time to learn.\nTemporal difference learning of values:\nPolicy still fixed, still doing evaluation!Move values toward value of whatever successor occurs: running average.\nTD value leaning is a model-free way to do policy evaluation, mimicking \nBellman updates with running sample averages\nHowever, if we want to turn values into a (new) policy, we’re sunk\n\nExponential Moving Average:Makes recent samples more important.Decreasing learning rate (alpha) can give converging averages\nActive Reinforcement Learning: learn the optimal policy / values,Fundamental tradeoff: exploration vs. exploitation\nThis is NOT offline planning! You actually take actions in the world and find out what happens…\nQ-Learning:Learn Q(s,a) values as you go, off-policy learning\nReceive a sample (s,a,s’,r)\nConsider your old estimate:\nConsider your new sample estimate:\nIncorporate the new estimate into a running average\n\nWhen to explore?\nRandom actions: explore a fixed amount\nBetter idea: explore areas whose badness is not\n(yet) established, eventually stop exploring\n\n generalize:\nLearn about some small number of training states from \nexperience\nGeneralize that experience to new, similar situations\n\nLinear Value Functions:Advantage: our experience is summed up in a few powerful numbers\nDisadvantage: states may share features but actually be very different in value!\n\n\n## Module 9 Definitions\n* **Reinforcement learning** -  in which an agent interacts with the world and periodically receives rewards that reflect how well it is doing\n* **Sparse rewards** - in the vast majority of states the agent is given no informative reward signal at all(e.g. chess and racing)\n* **Passive reinforcement learning** - \n* **Direct evaluation** - Act according to π Every time you visit a state, write down what the sum of discounted rewards turned out to be, Average those samples\n* **Sample-based policy evaluation** -  Take samples of outcomes s’ (by doing the action!) and average\n* **Temporal difference learning** -  learn from every experience!Update V(s) each time we experience a transition (s, a, s’, r).Likely outcomes s’ will contribute updates more often\n* **Q-value iteration** - Start with Q0(s,a) = 0, which we know is right. Given Qk, calculate the depth k+1 q-values for all q-states\n* **Q-learning** - sample-based Q-value iteration\n* **Exploration functions** - Takes a value estimate u and a visit count n, and returns an optimistic utility\n* **Regret** -  a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\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 = \"\"\" use utility theory to represent preferences and reason quantitatively with them.\n",
        "Decision theory = probability theory +utility theory .\n",
        "The fundamental idea of decision theory is that\n",
        "the action that yields the highest expected utility, averaged over all the possible outcomes\n",
        "an agent is rational if and only if it chooses of the action. This is called the principle of maximum expected utility (MEU) \"\"\"\n",
        "chapter12_2 = \"\"\"Variables in probability theory are called random variables, and their names begin with\n",
        "an uppercase letter. A possible world is\n",
        "defined to be an assignment of values to all of the random variables under consideration.\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"This process is called marginalization, or summing out:P(Y) = ∑zP(Y,Z=z)\n",
        "P(Y|z)P(z), obtaining a rule called conditioning: P(Y) = ∑zP(Y|z)P(z).\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\" The property we used in Equation (12.10) is called independence (also marginal inde\u0002pendence and absolute independence). In particular, the weather is independent of one’s\n",
        "dental problems. Independence between propositions a and b can be written as\n",
        "P(a|b)=P(a) or P(b|a)=P(b) or P(a∧b)=P(a)P(b)  \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Such a probability distribution is called a naive Bayes model—“naive” because it is often\n",
        "used (as a simplifying assumption) in cases where the “effect” variables are not strictly inde\u0002pendent given the cause variable. (The naive Bayes model is sometimes called a Bayesian\n",
        "classifier, a somewhat careless usage that has prompted true Bayesians to call it the idiot\n",
        "Bayes model.) In practice, naive Bayes systems often work very well, even when the condi\u0002tional independence assumption is not strictly true.\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" A wumpus-world agent can calculate probabilities for unobserved aspects of the world,\n",
        "thereby improving on the decisions of a purely logical agent. Conditional independence\n",
        "makes these calculations tractable.\"\"\"\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 = \"\"\" The bigram model, for example, approximates the probability of a word given\n",
        "all the previous words P(wn|w1:n−1) by using only the conditional probability of the\n",
        "preceding word P(wn|wn−1).An intuitive way to\n",
        "estimate probabilities is called maximum likelihood estimation or MLE. We get\n",
        "maximum likelihood estimation the MLE estimate for the parameters of an n-gram model by getting counts from a\n",
        "corpus, and normalizing the counts so that they lie between 0 and 1. \"\"\"\n",
        "SLP_chapter3_2 = \"\"\"The best way to evaluate the performance of a language model is to embed it in\n",
        "an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation. Extrinsic evaluation is the only way to know if a particular improvement in a component is really going to help the task at hand.\n",
        "An intrinsic evaluation metric is one that measures the quality of a model independent of any application.\n",
        "For an intrinsic evaluation of a language model we need a test set. As with many\n",
        "of the statistical models in our field, the probabilities of an n-gram model come from\n",
        "training set the corpus it is trained on, the training set or training corpus. We can then measure\n",
        "the quality of an n-gram model by its performance on some unseen data called the\n",
        "test set test set or test corpus.\n",
        "n practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (sometimes called PP for short)\n",
        "of a language model on a test set is the inverse probability of the test set, normalized\n",
        "by the number of words. \"\"\"\n",
        "SLP_chapter3_3 = \"\"\"Sampling from a distribution means to choose random points according to their likelihood.\n",
        " \"\"\"\n",
        "SLP_chapter3_4 = \"\"\"The n-gram model, like many statistical models, is dependent on the training corpus.\n",
        "One implication of this is that the probabilities often encode specific facts about a\n",
        "given training corpus. Another implication is that n-grams do a better and better job\n",
        "of modeling the training corpus as we increase the value of N.\n",
        "How should we deal with this problem when we build n-gram models? One step\n",
        "is to be sure to use a training corpus that has a similar genre to whatever task we are\n",
        "trying to accomplish.t is equally important to get training data in the appropriate dialect or variety,\n",
        "especially when processing social media posts or spoken transcripts.\n",
        "These zeros— things that don’t ever occur in the training set but do occur in\n",
        "the test set—are a problem for two reasons. First, their presence means we are\n",
        "underestimating the probability of all sorts of words that might occur, which will\n",
        "hurt the performance of any application we want to run on this data.\n",
        "Second, if the probability of any word in the test set is 0, the entire probability\n",
        "of the test set is 0. \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" To keep a language model from assigning\n",
        "zero probability to these unseen events, we’ll have to shave off a bit of probability\n",
        "mass from some more frequent events and give it to the events we’ve never seen.\n",
        "smoothing This modification is called smoothing or discounting.Laplace smoothing does not perform well enough to be used \n",
        "in modern n-gram models, but it usefully introduces many of the concepts that we\n",
        "see in other smoothing algorithms, gives a useful baseline, and is also a practical\n",
        "smoothing algorithm for other tasks like text classification\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"Efficiency considerations are important when building language models that use\n",
        "such large sets of n-grams. Rather than store each word as a string, it is generally\n",
        "represented in memory as a 64-bit hash number, with the words themselves stored\n",
        "on disk. Probabilities are generally quantized using only 4-8 bits (instead of 8-byte\n",
        "floats), and n-grams are stored in reverse tries.\n",
        "An n-gram language model can also be shrunk by pruning, for example only\n",
        "storing n-grams with counts greater than some threshold (such as the count threshold\n",
        "of 40 used for the Google n-gram release) or using entropy to prune less-important\n",
        "n-grams (Stolcke, 1998). Another option is to build approximate language models\n",
        "Bloom filters using techniques like Bloom filters\n",
        " Stupid backoff gives up the idea of trying to make the language\n",
        "model a true probability distribution. There is no discounting of the higher-order\n",
        "probabilities. If a higher-order n-gram has a zero count, we simply backoff to a\n",
        "lower order n-gram, weighed by a fixed (context-independent) weight. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Inference by Enumeration \n",
        "Step 1: Select the entries consistent with the evidence\n",
        "Step 2: Sum out H to get joint of Query and evidence\n",
        "Step 3: Normalize\n",
        "Bayes’ Rule:• Lets us build one conditional from its reverse\n",
        "• Often one conditional is tricky but the other one is simple\n",
        "• Foundation of many systems we’ll see later (e.g. ASR, MT)\n",
        "\n",
        "Markov Assumption\n",
        "Problems for MLE:\n",
        "Out of vocabulary items (OOV)\n",
        "<unk> to deal with OOVs\n",
        "Fixed lexicon L of size V\n",
        "Normalize training data by replacing any word not in L with <unk>\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Probabilistic inference:\" : \"compute a desired probability from other known probabilities (e.g. conditional from joint)\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "13473619-b894-4e4f-f42c-587736d0cd76"
      },
      "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 use utility theory to represent preferences and reason quantitatively with them.\nDecision theory = probability theory +utility theory .\nThe fundamental idea of decision theory is that\nthe action that yields the highest expected utility, averaged over all the possible outcomes\nan agent is rational if and only if it chooses of the action. This is called the principle of maximum expected utility (MEU) \n\n## AIMA Chapter 12.2 Basic Probability Notation\nVariables in probability theory are called random variables, and their names begin with\nan uppercase letter. A possible world is\ndefined to be an assignment of values to all of the random variables under consideration.\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nThis process is called marginalization, or summing out:P(Y) = ∑zP(Y,Z=z)\nP(Y|z)P(z), obtaining a rule called conditioning: P(Y) = ∑zP(Y|z)P(z).\n\n\n## AIMA Chapter 12.4 Independence\n The property we used in Equation (12.10) is called independence (also marginal inde\u0002pendence and absolute independence). In particular, the weather is independent of one’s\ndental problems. Independence between propositions a and b can be written as\nP(a|b)=P(a) or P(b|a)=P(b) or P(a∧b)=P(a)P(b)  \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Such a probability distribution is called a naive Bayes model—“naive” because it is often\nused (as a simplifying assumption) in cases where the “effect” variables are not strictly inde\u0002pendent given the cause variable. (The naive Bayes model is sometimes called a Bayesian\nclassifier, a somewhat careless usage that has prompted true Bayesians to call it the idiot\nBayes model.) In practice, naive Bayes systems often work very well, even when the condi\u0002tional independence assumption is not strictly true.\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n A wumpus-world agent can calculate probabilities for unobserved aspects of the world,\nthereby improving on the decisions of a purely logical agent. Conditional independence\nmakes these calculations tractable.\n\n## SLP Chapter 3.1 N-Grams\n The bigram model, for example, approximates the probability of a word given\nall the previous words P(wn|w1:n−1) by using only the conditional probability of the\npreceding word P(wn|wn−1).An intuitive way to\nestimate probabilities is called maximum likelihood estimation or MLE. We get\nmaximum likelihood estimation the MLE estimate for the parameters of an n-gram model by getting counts from a\ncorpus, and normalizing the counts so that they lie between 0 and 1. \n\n## SLP Chapter 3.2 Evaluating Language Models\nThe best way to evaluate the performance of a language model is to embed it in\nan application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation. Extrinsic evaluation is the only way to know if a particular improvement in a component is really going to help the task at hand.\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application.\nFor an intrinsic evaluation of a language model we need a test set. As with many\nof the statistical models in our field, the probabilities of an n-gram model come from\ntraining set the corpus it is trained on, the training set or training corpus. We can then measure\nthe quality of an n-gram model by its performance on some unseen data called the\ntest set test set or test corpus.\nn practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (sometimes called PP for short)\nof a language model on a test set is the inverse probability of the test set, normalized\nby the number of words. \n\n## SLP Chapter 3.3 Sampling sentences from a language model\nSampling from a distribution means to choose random points according to their likelihood.\n \n\n## SLP Chapter 3.4 Generalization and Zeros\nThe n-gram model, like many statistical models, is dependent on the training corpus.\nOne implication of this is that the probabilities often encode specific facts about a\ngiven training corpus. Another implication is that n-grams do a better and better job\nof modeling the training corpus as we increase the value of N.\nHow should we deal with this problem when we build n-gram models? One step\nis to be sure to use a training corpus that has a similar genre to whatever task we are\ntrying to accomplish.t is equally important to get training data in the appropriate dialect or variety,\nespecially when processing social media posts or spoken transcripts.\nThese zeros— things that don’t ever occur in the training set but do occur in\nthe test set—are a problem for two reasons. First, their presence means we are\nunderestimating the probability of all sorts of words that might occur, which will\nhurt the performance of any application we want to run on this data.\nSecond, if the probability of any word in the test set is 0, the entire probability\nof the test set is 0. \n\n## SLP Chapter 3.5 Smoothing\n To keep a language model from assigning\nzero probability to these unseen events, we’ll have to shave off a bit of probability\nmass from some more frequent events and give it to the events we’ve never seen.\nsmoothing This modification is called smoothing or discounting.Laplace smoothing does not perform well enough to be used \nin modern n-gram models, but it usefully introduces many of the concepts that we\nsee in other smoothing algorithms, gives a useful baseline, and is also a practical\nsmoothing algorithm for other tasks like text classification\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nEfficiency considerations are important when building language models that use\nsuch large sets of n-grams. Rather than store each word as a string, it is generally\nrepresented in memory as a 64-bit hash number, with the words themselves stored\non disk. Probabilities are generally quantized using only 4-8 bits (instead of 8-byte\nfloats), and n-grams are stored in reverse tries.\nAn n-gram language model can also be shrunk by pruning, for example only\nstoring n-grams with counts greater than some threshold (such as the count threshold\nof 40 used for the Google n-gram release) or using entropy to prune less-important\nn-grams (Stolcke, 1998). Another option is to build approximate language models\nBloom filters using techniques like Bloom filters\n Stupid backoff gives up the idea of trying to make the language\nmodel a true probability distribution. There is no discounting of the higher-order\nprobabilities. If a higher-order n-gram has a zero count, we simply backoff to a\nlower order n-gram, weighed by a fixed (context-independent) weight. \n\n## Module 10 Lecture Notes\n Inference by Enumeration \nStep 1: Select the entries consistent with the evidence\nStep 2: Sum out H to get joint of Query and evidence\nStep 3: Normalize\nBayes’ Rule:• Lets us build one conditional from its reverse\n• Often one conditional is tricky but the other one is simple\n• Foundation of many systems we’ll see later (e.g. ASR, MT)\n\nMarkov Assumption\nProblems for MLE:\nOut of vocabulary items (OOV)\n<unk> to deal with OOVs\nFixed lexicon L of size V\nNormalize training data by replacing any word not in L with <unk>\n\n## Module 10 Definitions\n* **Probabilistic inference:** - compute a desired probability from other known probabilities (e.g. conditional from joint)\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 = \"\"\" A Bayesian network is a directed graph in which each node is annotated with quantitative\n",
        "probability information. The full specification is as follows:\n",
        "1. Each node corresponds to a random variable, which may be discrete or continuous.\n",
        "2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to\n",
        "node Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a\n",
        "directed acyclic graph, or DAG.\n",
        "3. Each node Xi has associated probability information θ(Xi\n",
        "|Parents(Xi)) that quantifies\n",
        "Parameter the effect of the parents on the node using a finite number of parameters. \"\"\"\n",
        "chapter13_2 = \"\"\" The Semantics of Bayesian Networks:Assume that the Bayes net contains n variables, X1,...,Xn. A generic entry in the joint\n",
        "distribution is then P(X1=x1 ∧ ... ∧ Xn=xn), or P(x1,...,xn) for short. The semantics ofBayes nets defines each entry in the joint distribution as follows:\n",
        "P(x1,...,xn) =n∏i=1θ(xi| parents(Xi)), (13.1)\n",
        "where parents(Xi) denotes the values of Parents(Xi) that appear in x1,...,xn. Thus, each\n",
        "entry in the joint distribution is represented by the product of the appropriate elements of the\n",
        "local conditional distributions in the Bayes net.\n",
        "1. Nodes: First determine the set of variables that are required to model the domain. Now\n",
        "order them, {X1,...,Xn}. Any order will work, but the resulting network will be more\n",
        "compact if the variables are ordered such that causes precede effects.\n",
        "2. Links: For i = 1 to n do:\n",
        "• Choose a minimal set of parents for Xi from X1,...,Xi−1, such that Equation (13.3)\n",
        "is satisfied.\n",
        "• For each parent insert a link from the parent to Xi\n",
        "• CPTs: Write down the conditional probability table, P(Xi|Parents(Xi)). \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"  Not every BN can represent every joint distribution\n",
        "§ The topology enforces certain conditional independencies\n",
        "§ How big is a joint distribution over N \n",
        "Boolean variables?\n",
        "2^N\n",
        "§ How big is an N-node net if nodes \n",
        "have up to k parents?\n",
        "O(N * 2^(k+1)) \n",
        "\n",
        "§ If one or more paths is active, then independence not guaranteed\n",
        "§ if all paths are inactive then independence is guaranteed\n",
        "§ A path is active if each triple is active\n",
        "\n",
        "Inference by Enumeration:General case:\n",
        "§ Evidence variables:  E1...\n",
        "§ Query* variable: Q\n",
        "§ Hidden variables: H1 ... Hr All variables\n",
        "§ Step 1: Select the entries consistent with the evidence\n",
        "§ Step 2: Sum out H to get joint of Query and evidence\n",
        "§ Step 3: Normalize\n",
        "\n",
        "§ Why is inference by enumeration so slow?\n",
        "§ You join up the whole joint distribution before you sum out the hidden variables\n",
        "§ Advanced technique: Variable Elimination\n",
        "§ Interleave joining and marginalizing \n",
        "§ Still NP-hard, but usually much faster than inference by enumeration\n",
        "§ See the textbook for a description\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"A Bayes net \" : \"Topology (graph) + Local Conditional Probabilities\",  \n",
        "\"Inference\":\"calculating some useful quantity from a joint probability distribution\"  \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 803
        },
        "cellView": "form",
        "outputId": "5ff0b303-f978-4e19-aaeb-d76726a3363a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n A Bayesian network is a directed graph in which each node is annotated with quantitative\nprobability information. The full specification is as follows:\n1. Each node corresponds to a random variable, which may be discrete or continuous.\n2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to\nnode Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a\ndirected acyclic graph, or DAG.\n3. Each node Xi has associated probability information θ(Xi\n|Parents(Xi)) that quantifies\nParameter the effect of the parents on the node using a finite number of parameters. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The Semantics of Bayesian Networks:Assume that the Bayes net contains n variables, X1,...,Xn. A generic entry in the joint\ndistribution is then P(X1=x1 ∧ ... ∧ Xn=xn), or P(x1,...,xn) for short. The semantics ofBayes nets defines each entry in the joint distribution as follows:\nP(x1,...,xn) =n∏i=1θ(xi| parents(Xi)), (13.1)\nwhere parents(Xi) denotes the values of Parents(Xi) that appear in x1,...,xn. Thus, each\nentry in the joint distribution is represented by the product of the appropriate elements of the\nlocal conditional distributions in the Bayes net.\n1. Nodes: First determine the set of variables that are required to model the domain. Now\norder them, {X1,...,Xn}. Any order will work, but the resulting network will be more\ncompact if the variables are ordered such that causes precede effects.\n2. Links: For i = 1 to n do:\n• Choose a minimal set of parents for Xi from X1,...,Xi−1, such that Equation (13.3)\nis satisfied.\n• For each parent insert a link from the parent to Xi\n• CPTs: Write down the conditional probability table, P(Xi|Parents(Xi)). \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n  Not every BN can represent every joint distribution\n§ The topology enforces certain conditional independencies\n§ How big is a joint distribution over N \nBoolean variables?\n2^N\n§ How big is an N-node net if nodes \nhave up to k parents?\nO(N * 2^(k+1)) \n\n§ If one or more paths is active, then independence not guaranteed\n§ if all paths are inactive then independence is guaranteed\n§ A path is active if each triple is active\n\nInference by Enumeration:General case:\n§ Evidence variables:  E1...\n§ Query* variable: Q\n§ Hidden variables: H1 ... Hr All variables\n§ Step 1: Select the entries consistent with the evidence\n§ Step 2: Sum out H to get joint of Query and evidence\n§ Step 3: Normalize\n\n§ Why is inference by enumeration so slow?\n§ You join up the whole joint distribution before you sum out the hidden variables\n§ Advanced technique: Variable Elimination\n§ Interleave joining and marginalizing \n§ Still NP-hard, but usually much faster than inference by enumeration\n§ See the textbook for a description\n\n## Module 11 Definitions\n* **A bayes net ** - Topology (graph) + Local Conditional Probabilities\n* **Inference** - calculating some useful quantity from a joint probability distribution\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 = \"\"\"Going from a specific set of observations to a general rule is called induction; from the\n",
        "observations that the sun rose every day in the past, we induce that the sun will come up\n",
        "tomorrow.\n",
        "In supervised learning the agent observes input-output pairs and learns a function that\n",
        "maps from input to output.\n",
        "In unsupervised learning the agent learns patterns in the input without any explicit learning feedback.\n",
        "In reinforcement learning the agent learns from a series of reinforcements: rewards learning and punishments. \"\"\"\n",
        "chapter19_2 = \"\"\"By bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the\n",
        "expected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space.\n",
        "We say that a hypothesis is underfitting when it fails to find a pattern in the data.\n",
        "By variance we mean the amount of change in the hypothesis due to fluctuation in the Variance\n",
        "training data.  We say a function is overfitting the data when it pays too much attention to the particular data set it is trained\n",
        "on, causing it to perform poorly on unseen data.\n",
        "Often there is a bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may gen\u0002eralize better.\n",
        "A decision tree is a representation of a function that maps a vector of attribute values to a single output value—a “decision.”\n",
        "In general, the input and output values can be discrete or continuous, but for now we will\n",
        "consider only inputs consisting of discrete values and outputs that are either true (a positive Positive\n",
        "example) or false (a negative example). We call this Boolean classification.\n",
        "\n",
        " \"\"\"\n",
        "chapter19_3 = \"\"\"  Overfitting becomes more likely as the number of attributes grows, and less likely as we increase the number of training examples.\n",
        "For decision trees, a technique called decision tree pruning combats overfitting. pruning works by eliminating nodes that are not clearly relevant.\n",
        "Decision trees are also unstable in that adding just one new example can change the Unstable\n",
        "test at the root, which changes the entire tree. In Section 19.8.2 we will see that the random\n",
        "forest model can fix some of these issues.\"\"\"\n",
        "chapter19_4 = \"\"\"This process of explicitly penalizing complex hypotheses is called regularization: we’re Regularization\n",
        "looking for functions that are more regular. Note that we are now making two choices: the\n",
        "loss function (L1 or L2), and the complexity measure, which is called a regularization function.\n",
        "Bayesian optimization treats the task of choosing good hyperparameter values as a machine learning problem in itself. \"\"\"\n",
        "chapter19_5 = \"\"\"The unknown word solution for such unknown words is to ignore them.\n",
        "Finally, some systems choose to completely ignore another class of words: stop words \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Wouldn’t it be better if we could somehow use all our data for training and still use all our data for test? We can do this by cross-validation.\n",
        "In cross-validation, we choose a number k, and partition our data into k disjoint subsets called folds. \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "skdRbO7hEjh0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e237dccf-67b1-4e9b-c2d8-82d37d80ef30"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nGoing from a specific set of observations to a general rule is called induction; from the\nobservations that the sun rose every day in the past, we induce that the sun will come up\ntomorrow.\nIn supervised learning the agent observes input-output pairs and learns a function that\nmaps from input to output.\nIn unsupervised learning the agent learns patterns in the input without any explicit learning feedback.\nIn reinforcement learning the agent learns from a series of reinforcements: rewards learning and punishments. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nBy bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the\nexpected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space.\nWe say that a hypothesis is underfitting when it fails to find a pattern in the data.\nBy variance we mean the amount of change in the hypothesis due to fluctuation in the Variance\ntraining data.  We say a function is overfitting the data when it pays too much attention to the particular data set it is trained\non, causing it to perform poorly on unseen data.\nOften there is a bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may gen\u0002eralize better.\nA decision tree is a representation of a function that maps a vector of attribute values to a single output value—a “decision.”\nIn general, the input and output values can be discrete or continuous, but for now we will\nconsider only inputs consisting of discrete values and outputs that are either true (a positive Positive\nexample) or false (a negative example). We call this Boolean classification.\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n  Overfitting becomes more likely as the number of attributes grows, and less likely as we increase the number of training examples.\nFor decision trees, a technique called decision tree pruning combats overfitting. pruning works by eliminating nodes that are not clearly relevant.\nDecision trees are also unstable in that adding just one new example can change the Unstable\ntest at the root, which changes the entire tree. In Section 19.8.2 we will see that the random\nforest model can fix some of these issues.\n\n## AIMA Chapter 5.5 Stochastic Games\nThis process of explicitly penalizing complex hypotheses is called regularization: we’re Regularization\nlooking for functions that are more regular. Note that we are now making two choices: the\nloss function (L1 or L2), and the complexity measure, which is called a regularization function.\nBayesian optimization treats the task of choosing good hyperparameter values as a machine learning problem in itself. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe unknown word solution for such unknown words is to ignore them.\nFinally, some systems choose to completely ignore another class of words: stop words \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Wouldn’t it be better if we could somehow use all our data for training and still use all our data for test? We can do this by cross-validation.\nIn cross-validation, we choose a number k, and partition our data into k disjoint subsets called folds. \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Concept** - definition\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 = \"\"\"generative model like naive Bayes makes use of this likelihood term, which expresses how to generate the features of a document if we knew it was of class c.\n",
        "By contrast a discriminative model in this text categorization scenario attempts to directly compute P(c|d). \n",
        "Components of a probabilistic machine learning classifier A feature representation of the input. For each input observation x\n",
        "(i)\n",
        ", this\n",
        "will be a vector of features [x1, x2,..., xn]. We will generally refer to feature\n",
        "i for input x\n",
        "(j)\n",
        "as x\n",
        "(j)\n",
        "i\n",
        ", sometimes simplified as xi\n",
        ", but we will also see the\n",
        "notation fi\n",
        ", fi(x), or, for multiclass classification, fi(c, x).\n",
        "2. A classification function that computes ˆy, the estimated class, via p(y|x). In\n",
        "the next section we will introduce the sigmoid and softmax tools for classifi\u0002cation.\n",
        "3. An objective function for learning, usually involving minimizing error on\n",
        "training examples. We will introduce the cross-entropy loss function.\n",
        "4. An algorithm for optimizing the o\"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" For example in batch training we compute the gradient over the entire dataset.\n",
        "By seeing so many examples, batch training offers a superb estimate of which di\u0002rection to move the weights, at the cost of spending a lot of time processing every\n",
        "single example in the training set to compute this perfect direction.\n",
        "mini-batch A compromise is mini-batch training: we train on a group of m examples (per\u0002haps 512, or 1024) that is less than the whole dataset. (If m is the size of the dataset,\n",
        "then we are doing batch gradient descent; if m = 1, we are back to doing stochas\u0002tic gradient descent). Mini-batch training also has the advantage of computational\n",
        "efficiency. The mini-batches can easily be vectorized, choosing the size of the mini\u0002batch based on the computational resources. This allows us to process all the exam\u0002ples in one mini-batch in parallel and then accumulate the loss, something that’s not\n",
        "possible with individual or batch training.\n",
        "The weights for\n",
        "features will attempt to perfectly fit details of the training set, in fact too perfectly,\n",
        "modeling noisy factors that just accidentally correlate with the class. This problem is\n",
        "overfitting called overfitting. A good model should be able to generalize well from the training\n",
        "generalize data to the unseen test set, but a model that overfits will have poor generalization.\n",
        " \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f0b53307-607d-4697-c7ce-8ab74a4e39f6"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\ngenerative model like naive Bayes makes use of this likelihood term, which expresses how to generate the features of a document if we knew it was of class c.\nBy contrast a discriminative model in this text categorization scenario attempts to directly compute P(c|d). \nComponents of a probabilistic machine learning classifier A feature representation of the input. For each input observation x\n(i)\n, this\nwill be a vector of features [x1, x2,..., xn]. We will generally refer to feature\ni for input x\n(j)\nas x\n(j)\ni\n, sometimes simplified as xi\n, but we will also see the\nnotation fi\n, fi(x), or, for multiclass classification, fi(c, x).\n2. A classification function that computes ˆy, the estimated class, via p(y|x). In\nthe next section we will introduce the sigmoid and softmax tools for classifi\u0002cation.\n3. An objective function for learning, usually involving minimizing error on\ntraining examples. We will introduce the cross-entropy loss function.\n4. An algorithm for optimizing the o\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n For example in batch training we compute the gradient over the entire dataset.\nBy seeing so many examples, batch training offers a superb estimate of which di\u0002rection to move the weights, at the cost of spending a lot of time processing every\nsingle example in the training set to compute this perfect direction.\nmini-batch A compromise is mini-batch training: we train on a group of m examples (per\u0002haps 512, or 1024) that is less than the whole dataset. (If m is the size of the dataset,\nthen we are doing batch gradient descent; if m = 1, we are back to doing stochas\u0002tic gradient descent). Mini-batch training also has the advantage of computational\nefficiency. The mini-batches can easily be vectorized, choosing the size of the mini\u0002batch based on the computational resources. This allows us to process all the exam\u0002ples in one mini-batch in parallel and then accumulate the loss, something that’s not\npossible with individual or batch training.\nThe weights for\nfeatures will attempt to perfectly fit details of the training set, in fact too perfectly,\nmodeling noisy factors that just accidentally correlate with the class. This problem is\noverfitting called overfitting. A good model should be able to generalize well from the training\ngeneralize data to the unseen test set, but a model that overfits will have poor generalization.\n \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \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 Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 945
        },
        "outputId": "f71e8820-dbdd-48c7-93a0-8caaf26ad40d"
      },
      "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 Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "654809ca-e488-48ad-a056-2b3e0c93febd"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n ecision theory, in its simplest form, deals with choosing among actions based on the desir\u0002ability of their immediate outcomes; that is, the environment is assumed to be episodic.\nThe MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice. $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n  Constraints on rational preferences:1. Orderability:  (A ≻ B), (B ≻ A), or (A ∼ B);2.Transitivity:(A ≻ B)∧(B ≻ C) ⇒ (A ≻ C).\n3. Continuity:A ≻ B ≻ C ⇒ ∃ p [p,A; 1− p,C] ∼ B. 4. Substitutability: A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B; 1− p,C].\n5.  Monotonicity: A ≻ B ⇒ (p > q ⇔ [p,A; 1− p,B] ≻ [q,A; 1−q,B]). 6. Decomposability: [p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C].\nRational preferences lead to utility: Existence of Utility Function:U(A) > U(B) ⇔ A ≻ B and U(A) = U(B) ⇔ A ∼ B.\nExpected Utility of a Lottery: U([p1,S1;...; pn,Sn]) = ∑_{i}piU(Si).\n \n\n## AIMA Chapter 16.3 Utility Functions\nTypically, we fix the utility of a “best possible prize” at U(S) = u⊤ and a “worst possible\ncatastrophe” at U(S) = u⊥.\nexpected monetary value (EMV)\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Because the decision problem is sequential, the utility function will depend\non a sequence of states and actions—an environment history—rather than on a single state.\nMDP, and consists of a set of states (with an initial state s0); a set ACTIONS(s) of actions\nin each state; a transition model P(s′|s,a); and a reward function R(s,a,s′). Methods for\nsolving MDPs usually involve dynamic programming.\nA policy that depends on the time is called nonstationary.\nadditive discounted rewards: the utility of a history is Additive discounted\nreward Uh([s0,a0,s1,a1,s2,...]) = R(s0,a0,s1) +γR(s1,a1,s2) +γ^2R(s2,a2,s3) +··· , where the discount factor γ is a number between 0 and 1.\nWhen γ is close to 0, rewards in the distant future are viewed as insignificant. When γ is close to 1, an agent is more willing\nto wait for long-term rewards.When γ is exactly 1, discounted rewards reduce to the special case of purely additive rewards. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Algorithms for MDPs: value iteration, policy iteration, and linear programming.\nValue Iteration:The Bellman equation  is the basis of the value iteration.\nThe basic concept used in showing that value iteration converges is the notion of a contraction.\n two important properties\nof contractions:\n• A contraction has only one fixed point; if there were two fixed points they would not\nget closer together when the function was applied, so it would not be a contraction.\n• When the function is applied to any argument, the value must get closer to the fixed\npoint (because the fixed point does not move), so repeated application of a contraction\nalways reaches the fixed point in the limit.\n The policy iteration algorithm alternates\nthe following two steps, beginning from some initial policy π0:\n• Policy evaluation: given a policy πi\n, calculate Ui =U\nπi Policy evaluation , the utility of each state if πi\nwere to be executed.\nPolicy improvement • Policy improvement: Calculate a new MEU policy πi+1, using one-step look-ahead\nbased on Ui.\n \n\n## Module 8 Lecture Notes\nThe value (utility) of a state s: V*(s) = expected utility starting in s and acting optimally\n▪ The value (utility) of a q-state (s,a):Q*(s,a) = expected utility starting out \nhaving taken action a from state s and (thereafter) acting optimally\n▪ The optimal policy:π*(s) = optimal action from state s\nProblems with Value Iteration:Problem 1: It’s slow – O(S2A) per iteration\nProblem 2: The “max” at each state rarely changes\nProblem 3: The policy often converges long before the values.\npolicy iteration: It’s still optimal! Can converge (much) faster under some conditions\nComparison\nBoth value iteration and policy iteration compute the same thing (all optimal values)\nIn value iteration:\n• Every iteration updates both the values and (implicitly) the policy\n• We don’t track the policy, but taking the max over actions implicitly recomputes it\nIn policy iteration:\n• We do several passes that update utilities with fixed policy (each pass is fast \nbecause we consider only one action, not all of them)\n• After the policy is evaluated, a new policy is chosen (slow like a value iteration \npass)\n• The new policy will be better (or we’re done)\nUtilities are functions from outcomes (states  of the world) to real numbers that describe an agent’s preferences\n \n\n## Module 8 Definitions\n* **Utility function** - which assigns a single number to express the Utility function desirability of a state\n* **Expected utility** - n action given the evidence, EU(a), is just the Expected utility average utility value of the outcomes\n* **Value function or ordinal utility function.** - As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter\n* **Preference elicitation** - presenting choices to the human and using the Preference elicitation observed preferences to pin down the underlying utility function\n* **Normalized utilities** - scale with u⊥ = 0 and u⊤ = 1\n* **Standard lottery** - [p,u⊤; (1− p),u⊥]\n* **Markovian** - the probability of reaching s′ from s depends only on s and not on the history of earlier states.\n* **Markov decision process** -  a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards\n* **Optimal policy π∗** - a policy that yields the highest expected utility\n* **** - \n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Model-based reinforcement learning: In these approaches the agent uses a transition\nlearning model of the environment to help interpret the reward signals and to make decisions\nabout how to act. The model may be initially unknown, in which case the agent learns\nthe model from observing the effects of its actions, or it may already be known—for\nexample, a chess program may know the rules of chess even if it does not know how\nto choose good moves.\n\nModel-free reinforcement learning: In these approaches the agent neither knows nor learning learns a transition model for the environment. Instead, it learns a more direct represen\u0002tation of how to behave. This comes in one of two varieties:\n• Action-utility learning: We introduced action-utility functions in Chapter 17. The Action-utility\nlearning\nQ-learning most common form of action-utility learning is Q-learning, where the agent learns\nQ-function a Q-function, or quality-function, Q(s,a), denoting the sum of rewards from state\ns onward if action a is taken. Given a Q-function, the agent can choose what to do\nin s by finding the action with the highest Q-value.\nPolicy search • Policy search: The agent learns a policy π(s) that maps directly from states to\nactions. In the terminology of Chapter 2, this a reflex agent. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\npassive learning agent: a fully observable environment with a small number of\nactions and states, in which an agent already has a fixed policy π(s) that determines its actions.\nThe agent is trying to learn the utility function Uπ(s)—the expected total discounted reward if policy π is executed beginning in state s.\nhe idea of direct utility estimation is that the utility of a state is defined as the expected Direct utility\nestimation\n\nReward-to-go total reward from that state onward (called the expected reward-to-go), and that each trial\nprovides a sample of this quantity for each state visited.\nAdaptive dynamic programming:n adaptive dynamic programming (or ADP) agent takes advantage of the constraints \namong the utilities of states by learning the transition model that connects them and solv\u0002ing the corresponding Markov decision process using dynamic programming.\nTemporal-difference learning: Big idea: learn from every experience!\nUpdate V(s) each time we experience a transition (s, a, s’, r)\nLikely outcomes s’ will contribute updates more often\nTemporal difference learning of values\nPolicy still fixed, still doing evaluation!\nMove values toward value of whatever successor occurs: running average\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nActive Reinforcement Learning: A passive learning agent has a fixed policy that determines its behavior. An active learning\nagent gets to decide what actions to take. \n Temporal-difference Q-learning: The Q-learning method avoids the need for a model by learning an action-utility function\nQ(s,a) instead of a utility function U(s). Q(s,a) denotes the expected total discounted reward\nif the agent takes action a in s and acts optimally thereafter. Knowing the Q-function enables\nthe agent to act optimally simply by choosing argmaxa Q(s,a), with no need for look-ahead\nbased on a transition model\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Generalization in Reinforcement Learning: When the learning agent is responsible for selecting actions while it learns, it must\ntrade off the estimated value of those actions against the potential for learning useful\nnew information. An exact solution for the exploration problem is infeasible, but some\nsimple heuristics do a reasonable job. An exploring agent must also take care to avoid\npremature death.\n• In large state spaces, reinforcement learning algorithms must use an approximate func\u0002tional representation of U(s) or Q(s,a) in order to generalize over states. Deep re\u0002inforcement learning—using deep neural networks as function approximators—has\nachieved considerable success on hard problems.\n• Reward shaping and hierarchical reinforcement learning are helpful for learning\ncomplex behaviors, particularly when rewards are sparse and long action sequences are\nrequired to obtain them\n \n\n## Module 9 Lecture Notes\n  reinforcement learning:\nExploration: you have to try unknown actions to get information\nExploitation: eventually, you have to use what you know\nRegret: even if you learn intelligently, you make mistakes\nSampling: because of chance, you have to try things repeatedly\nDifficulty: learning can be much harder than solving a known MDP\nModel-Based Learning:Step 1: Learn empirical MDP model\nCount outcomes s’ for each s, a Normalize to give an estimate of\nDiscover each when we experience (s, a, s’)\nStep 2: Solve the learned MDP\nFor example, use value iteration, as before \nWhat bad about direct evaluation?\nIt wastes information about state connections\nEach state must be learned separately\nSo, it takes a long time to learn.\nTemporal difference learning of values:\nPolicy still fixed, still doing evaluation!Move values toward value of whatever successor occurs: running average.\nTD value leaning is a model-free way to do policy evaluation, mimicking \nBellman updates with running sample averages\nHowever, if we want to turn values into a (new) policy, we’re sunk\n\nExponential Moving Average:Makes recent samples more important.Decreasing learning rate (alpha) can give converging averages\nActive Reinforcement Learning: learn the optimal policy / values,Fundamental tradeoff: exploration vs. exploitation\nThis is NOT offline planning! You actually take actions in the world and find out what happens…\nQ-Learning:Learn Q(s,a) values as you go, off-policy learning\nReceive a sample (s,a,s’,r)\nConsider your old estimate:\nConsider your new sample estimate:\nIncorporate the new estimate into a running average\n\nWhen to explore?\nRandom actions: explore a fixed amount\nBetter idea: explore areas whose badness is not\n(yet) established, eventually stop exploring\n\n generalize:\nLearn about some small number of training states from \nexperience\nGeneralize that experience to new, similar situations\n\nLinear Value Functions:Advantage: our experience is summed up in a few powerful numbers\nDisadvantage: states may share features but actually be very different in value!\n\n\n## Module 9 Definitions\n* **Reinforcement learning** -  in which an agent interacts with the world and periodically receives rewards that reflect how well it is doing\n* **Sparse rewards** - in the vast majority of states the agent is given no informative reward signal at all(e.g. chess and racing)\n* **Passive reinforcement learning** - \n* **Direct evaluation** - Act according to π Every time you visit a state, write down what the sum of discounted rewards turned out to be, Average those samples\n* **Sample-based policy evaluation** -  Take samples of outcomes s’ (by doing the action!) and average\n* **Temporal difference learning** -  learn from every experience!Update V(s) each time we experience a transition (s, a, s’, r).Likely outcomes s’ will contribute updates more often\n* **Q-value iteration** - Start with Q0(s,a) = 0, which we know is right. Given Qk, calculate the depth k+1 q-values for all q-states\n* **Q-learning** - sample-based Q-value iteration\n* **Exploration functions** - Takes a value estimate u and a visit count n, and returns an optimistic utility\n* **Regret** -  a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n use utility theory to represent preferences and reason quantitatively with them.\nDecision theory = probability theory +utility theory .\nThe fundamental idea of decision theory is that\nthe action that yields the highest expected utility, averaged over all the possible outcomes\nan agent is rational if and only if it chooses of the action. This is called the principle of maximum expected utility (MEU) \n\n## AIMA Chapter 12.2 Basic Probability Notation\nVariables in probability theory are called random variables, and their names begin with\nan uppercase letter. A possible world is\ndefined to be an assignment of values to all of the random variables under consideration.\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nThis process is called marginalization, or summing out:P(Y) = ∑zP(Y,Z=z)\nP(Y|z)P(z), obtaining a rule called conditioning: P(Y) = ∑zP(Y|z)P(z).\n\n\n## AIMA Chapter 12.4 Independence\n The property we used in Equation (12.10) is called independence (also marginal inde\u0002pendence and absolute independence). In particular, the weather is independent of one’s\ndental problems. Independence between propositions a and b can be written as\nP(a|b)=P(a) or P(b|a)=P(b) or P(a∧b)=P(a)P(b)  \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Such a probability distribution is called a naive Bayes model—“naive” because it is often\nused (as a simplifying assumption) in cases where the “effect” variables are not strictly inde\u0002pendent given the cause variable. (The naive Bayes model is sometimes called a Bayesian\nclassifier, a somewhat careless usage that has prompted true Bayesians to call it the idiot\nBayes model.) In practice, naive Bayes systems often work very well, even when the condi\u0002tional independence assumption is not strictly true.\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n A wumpus-world agent can calculate probabilities for unobserved aspects of the world,\nthereby improving on the decisions of a purely logical agent. Conditional independence\nmakes these calculations tractable.\n\n## SLP Chapter 3.1 N-Grams\n The bigram model, for example, approximates the probability of a word given\nall the previous words P(wn|w1:n−1) by using only the conditional probability of the\npreceding word P(wn|wn−1).An intuitive way to\nestimate probabilities is called maximum likelihood estimation or MLE. We get\nmaximum likelihood estimation the MLE estimate for the parameters of an n-gram model by getting counts from a\ncorpus, and normalizing the counts so that they lie between 0 and 1. \n\n## SLP Chapter 3.2 Evaluating Language Models\nThe best way to evaluate the performance of a language model is to embed it in\nan application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation. Extrinsic evaluation is the only way to know if a particular improvement in a component is really going to help the task at hand.\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application.\nFor an intrinsic evaluation of a language model we need a test set. As with many\nof the statistical models in our field, the probabilities of an n-gram model come from\ntraining set the corpus it is trained on, the training set or training corpus. We can then measure\nthe quality of an n-gram model by its performance on some unseen data called the\ntest set test set or test corpus.\nn practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (sometimes called PP for short)\nof a language model on a test set is the inverse probability of the test set, normalized\nby the number of words. \n\n## SLP Chapter 3.3 Sampling sentences from a language model\nSampling from a distribution means to choose random points according to their likelihood.\n \n\n## SLP Chapter 3.4 Generalization and Zeros\nThe n-gram model, like many statistical models, is dependent on the training corpus.\nOne implication of this is that the probabilities often encode specific facts about a\ngiven training corpus. Another implication is that n-grams do a better and better job\nof modeling the training corpus as we increase the value of N.\nHow should we deal with this problem when we build n-gram models? One step\nis to be sure to use a training corpus that has a similar genre to whatever task we are\ntrying to accomplish.t is equally important to get training data in the appropriate dialect or variety,\nespecially when processing social media posts or spoken transcripts.\nThese zeros— things that don’t ever occur in the training set but do occur in\nthe test set—are a problem for two reasons. First, their presence means we are\nunderestimating the probability of all sorts of words that might occur, which will\nhurt the performance of any application we want to run on this data.\nSecond, if the probability of any word in the test set is 0, the entire probability\nof the test set is 0. \n\n## SLP Chapter 3.5 Smoothing\n To keep a language model from assigning\nzero probability to these unseen events, we’ll have to shave off a bit of probability\nmass from some more frequent events and give it to the events we’ve never seen.\nsmoothing This modification is called smoothing or discounting.Laplace smoothing does not perform well enough to be used \nin modern n-gram models, but it usefully introduces many of the concepts that we\nsee in other smoothing algorithms, gives a useful baseline, and is also a practical\nsmoothing algorithm for other tasks like text classification\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nEfficiency considerations are important when building language models that use\nsuch large sets of n-grams. Rather than store each word as a string, it is generally\nrepresented in memory as a 64-bit hash number, with the words themselves stored\non disk. Probabilities are generally quantized using only 4-8 bits (instead of 8-byte\nfloats), and n-grams are stored in reverse tries.\nAn n-gram language model can also be shrunk by pruning, for example only\nstoring n-grams with counts greater than some threshold (such as the count threshold\nof 40 used for the Google n-gram release) or using entropy to prune less-important\nn-grams (Stolcke, 1998). Another option is to build approximate language models\nBloom filters using techniques like Bloom filters\n Stupid backoff gives up the idea of trying to make the language\nmodel a true probability distribution. There is no discounting of the higher-order\nprobabilities. If a higher-order n-gram has a zero count, we simply backoff to a\nlower order n-gram, weighed by a fixed (context-independent) weight. \n\n## Module 10 Lecture Notes\n Inference by Enumeration \nStep 1: Select the entries consistent with the evidence\nStep 2: Sum out H to get joint of Query and evidence\nStep 3: Normalize\nBayes’ Rule:• Lets us build one conditional from its reverse\n• Often one conditional is tricky but the other one is simple\n• Foundation of many systems we’ll see later (e.g. ASR, MT)\n\nMarkov Assumption\nProblems for MLE:\nOut of vocabulary items (OOV)\n<unk> to deal with OOVs\nFixed lexicon L of size V\nNormalize training data by replacing any word not in L with <unk>\n\n## Module 10 Definitions\n* **Probabilistic inference:** - compute a desired probability from other known probabilities (e.g. conditional from joint)\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n A Bayesian network is a directed graph in which each node is annotated with quantitative\nprobability information. The full specification is as follows:\n1. Each node corresponds to a random variable, which may be discrete or continuous.\n2. Directed links or arrows connect pairs of nodes. If there is an arrow from node X to\nnode Y, X is said to be a parent of Y. The graph has no directed cycles and hence is a\ndirected acyclic graph, or DAG.\n3. Each node Xi has associated probability information θ(Xi\n|Parents(Xi)) that quantifies\nParameter the effect of the parents on the node using a finite number of parameters. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The Semantics of Bayesian Networks:Assume that the Bayes net contains n variables, X1,...,Xn. A generic entry in the joint\ndistribution is then P(X1=x1 ∧ ... ∧ Xn=xn), or P(x1,...,xn) for short. The semantics ofBayes nets defines each entry in the joint distribution as follows:\nP(x1,...,xn) =n∏i=1θ(xi| parents(Xi)), (13.1)\nwhere parents(Xi) denotes the values of Parents(Xi) that appear in x1,...,xn. Thus, each\nentry in the joint distribution is represented by the product of the appropriate elements of the\nlocal conditional distributions in the Bayes net.\n1. Nodes: First determine the set of variables that are required to model the domain. Now\norder them, {X1,...,Xn}. Any order will work, but the resulting network will be more\ncompact if the variables are ordered such that causes precede effects.\n2. Links: For i = 1 to n do:\n• Choose a minimal set of parents for Xi from X1,...,Xi−1, such that Equation (13.3)\nis satisfied.\n• For each parent insert a link from the parent to Xi\n• CPTs: Write down the conditional probability table, P(Xi|Parents(Xi)). \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n  Not every BN can represent every joint distribution\n§ The topology enforces certain conditional independencies\n§ How big is a joint distribution over N \nBoolean variables?\n2^N\n§ How big is an N-node net if nodes \nhave up to k parents?\nO(N * 2^(k+1)) \n\n§ If one or more paths is active, then independence not guaranteed\n§ if all paths are inactive then independence is guaranteed\n§ A path is active if each triple is active\n\nInference by Enumeration:General case:\n§ Evidence variables:  E1...\n§ Query* variable: Q\n§ Hidden variables: H1 ... Hr All variables\n§ Step 1: Select the entries consistent with the evidence\n§ Step 2: Sum out H to get joint of Query and evidence\n§ Step 3: Normalize\n\n§ Why is inference by enumeration so slow?\n§ You join up the whole joint distribution before you sum out the hidden variables\n§ Advanced technique: Variable Elimination\n§ Interleave joining and marginalizing \n§ Still NP-hard, but usually much faster than inference by enumeration\n§ See the textbook for a description\n\n## Module 11 Definitions\n* **A bayes net ** - Topology (graph) + Local Conditional Probabilities\n* **Inference** - calculating some useful quantity from a joint probability distribution\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\nGoing from a specific set of observations to a general rule is called induction; from the\nobservations that the sun rose every day in the past, we induce that the sun will come up\ntomorrow.\nIn supervised learning the agent observes input-output pairs and learns a function that\nmaps from input to output.\nIn unsupervised learning the agent learns patterns in the input without any explicit learning feedback.\nIn reinforcement learning the agent learns from a series of reinforcements: rewards learning and punishments. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nBy bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the\nexpected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space.\nWe say that a hypothesis is underfitting when it fails to find a pattern in the data.\nBy variance we mean the amount of change in the hypothesis due to fluctuation in the Variance\ntraining data.  We say a function is overfitting the data when it pays too much attention to the particular data set it is trained\non, causing it to perform poorly on unseen data.\nOften there is a bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may gen\u0002eralize better.\nA decision tree is a representation of a function that maps a vector of attribute values to a single output value—a “decision.”\nIn general, the input and output values can be discrete or continuous, but for now we will\nconsider only inputs consisting of discrete values and outputs that are either true (a positive Positive\nexample) or false (a negative example). We call this Boolean classification.\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n  Overfitting becomes more likely as the number of attributes grows, and less likely as we increase the number of training examples.\nFor decision trees, a technique called decision tree pruning combats overfitting. pruning works by eliminating nodes that are not clearly relevant.\nDecision trees are also unstable in that adding just one new example can change the Unstable\ntest at the root, which changes the entire tree. In Section 19.8.2 we will see that the random\nforest model can fix some of these issues.\n\n## AIMA Chapter 5.5 Stochastic Games\nThis process of explicitly penalizing complex hypotheses is called regularization: we’re Regularization\nlooking for functions that are more regular. Note that we are now making two choices: the\nloss function (L1 or L2), and the complexity measure, which is called a regularization function.\nBayesian optimization treats the task of choosing good hyperparameter values as a machine learning problem in itself. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe unknown word solution for such unknown words is to ignore them.\nFinally, some systems choose to completely ignore another class of words: stop words \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Wouldn’t it be better if we could somehow use all our data for training and still use all our data for test? We can do this by cross-validation.\nIn cross-validation, we choose a number k, and partition our data into k disjoint subsets called folds. \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n Your summary here \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\ngenerative model like naive Bayes makes use of this likelihood term, which expresses how to generate the features of a document if we knew it was of class c.\nBy contrast a discriminative model in this text categorization scenario attempts to directly compute P(c|d). \nComponents of a probabilistic machine learning classifier A feature representation of the input. For each input observation x\n(i)\n, this\nwill be a vector of features [x1, x2,..., xn]. We will generally refer to feature\ni for input x\n(j)\nas x\n(j)\ni\n, sometimes simplified as xi\n, but we will also see the\nnotation fi\n, fi(x), or, for multiclass classification, fi(c, x).\n2. A classification function that computes ˆy, the estimated class, via p(y|x). In\nthe next section we will introduce the sigmoid and softmax tools for classifi\u0002cation.\n3. An objective function for learning, usually involving minimizing error on\ntraining examples. We will introduce the cross-entropy loss function.\n4. An algorithm for optimizing the o\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n For example in batch training we compute the gradient over the entire dataset.\nBy seeing so many examples, batch training offers a superb estimate of which di\u0002rection to move the weights, at the cost of spending a lot of time processing every\nsingle example in the training set to compute this perfect direction.\nmini-batch A compromise is mini-batch training: we train on a group of m examples (per\u0002haps 512, or 1024) that is less than the whole dataset. (If m is the size of the dataset,\nthen we are doing batch gradient descent; if m = 1, we are back to doing stochas\u0002tic gradient descent). Mini-batch training also has the advantage of computational\nefficiency. The mini-batches can easily be vectorized, choosing the size of the mini\u0002batch based on the computational resources. This allows us to process all the exam\u0002ples in one mini-batch in parallel and then accumulate the loss, something that’s not\npossible with individual or batch training.\nThe weights for\nfeatures will attempt to perfectly fit details of the training set, in fact too perfectly,\nmodeling noisy factors that just accidentally correlate with the class. This problem is\noverfitting called overfitting. A good model should be able to generalize well from the training\ngeneralize data to the unseen test set, but a model that overfits will have poor generalization.\n \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \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 Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}