{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "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": "4bded847-a031-4234-e60b-abac45be61fc"
      },
      "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": 1,
      "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": "1375bb33-f612-4802-e736-ac5af9b5cb22"
      },
      "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": 2,
      "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": 3,
      "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 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "MARKOV DECISION PROCESS (\"MDP\") has the following components: \\n\n",
        "- set of states $s \\in S$ \\n\n",
        "- set of actions $a \\in A$ \\n\n",
        "- a transition function $T(s,a,s')$, the probability that executing action $a$ in $s$ will lead to $s'$: $P(s' | s, a)$ \\n\n",
        "- a reward function $R(s,a,s')$\\n\n",
        "- an initial state $s_0$\\n\n",
        "- **Optionally**, one or more terminal states \\n\n",
        "SOLUTION = POLICY: \\n\n",
        "In search problems, a solution was a sequence of actions. Because of the non-determinism in MDPs, solution to an MDP is a **policy** \\n\n",
        "- Policy $\\pi(s) = a$ and $\\pi^*(s)$ denotes the **optimal policy**\\n \n",
        "Even though the policy told me to go right here, there’s no guarantee that me picking the action Right will result in me moving right. It’s stochastic! \\\n",
        "Even if the **same policy** is executed multiple times by the agent, this may lead to different sequence of states and actions (**environment history**), and thus a **different score** under the reward function. \\n\n",
        "Therefore we need to compute the **expected utility** of all the possible paths generated by a policy. \\n\n",
        "SEQUENCES OF REWARDS \\n\n",
        "- Finite horizons: Fixed time (**N** actions) after which the game ends and the agent gets no additional score. Policies that depend on time are called\n",
        "**nonstationary**. \\n\n",
        "- Infinite horizons: With no fixed time limit, there is no reason to behave differently in the same state at different times. The optimal policy is **stationary**. \\n\n",
        "OPTIMAL QUANTITIES \\n\n",
        "- The value (utility) of a state s: $V*(s) =$ expected utility starting in s and acting optimally $= \\max_{a} Q*(s,a)$ \\n\n",
        "- The value (utility) of a q-state (s,a): $Q*(s,a) = $ expected utility starting out having taken action a from state s and (thereafter) acting optimally $= \\sum_{s'} T(s, a, s')[R(s,a,s') + \\gamma V*(s')]$\\n\n",
        "- Combining the two is the **BELLMAN EQUATION**: $V^*(s) = \\max_{a} \\sum_{s'} T(s, a, s') [R(s,a,s') + \\gamma V^*(s')]$ \\n\n",
        "TIME-LIMITED VALUES: \n",
        "- Key idea: time-limited values. Define $V_{k}(s)$ to be the optimal value of $s$ if the game ends in $k$ more time steps. \\n\n",
        "**VALUE ITERATION**\n",
        "- Start with $V_{0} = 0$: no time steps left means an expected reward sum of 0 \n",
        "- Given vector of $V_{k}(s)$ values, do one ply of expectimax from each state: $V_{k+1} \\leftarrow \\max_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\\n \n",
        "- Repeat until convergence\n",
        "- Complexity of each iteration: $O(S^2A)$ \\n\n",
        "**POLICY EVALUATION** \n",
        "- Do what $\\pi$ says to do. Then the tree would be simpler - only one action per state\n",
        "- Compute the utility of a state $s$ under a fixed (generally non-optimal) policy\n",
        "- $V_{\\pi}(s)=$ expected total discounted rewards starting in $s$ and following $\\pi$ \n",
        "- $V_{\\pi}(s) = \\sum_{s'}T(s, \\pi(s),s')[R(s,\\pi(s),s') + \\gamma V_{\\pi}(s')]$\n",
        "- Efficiency: $O(S^2)$ per iteration\n",
        "- How do we calculate the V's for a fixed policy $\\pi$? Idea 1: turn recursive Bellman equations into updates. **Idea 2**: Bellman equations are just a linear system. Solve with Matlab \n",
        "**COMPUTING ACTIONS FROM Q-VALUES**\n",
        "- Completely trivial: $\\pi^*(s) = arg \\max_{a} Q^*(s,a)$. Actions are easier to select from Q-values than values. \n",
        "Probmes with Value Iteration\n",
        "1. It's slow - $O(S^2A)$ per iteration\n",
        "2. The max at each state rarely changes\n",
        "3. The policy often converges long before the values\n",
        "- Policy iteration is much faster - using the one-step look-ahead: \\n\n",
        "  $\\pi_{i+1}(s) = arg \\max_{a} \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V^{\\pi_{i}}(s')]$ \\n\n",
        "Comparison\n",
        "- Both value iteration and policy iteration compute the same thing (all optimal values)\n",
        "- In **value iteration**, every iteration updates both the values and (implicity) the policy\n",
        "- We do not track the policy, but taking the max over actions implicitly recomputes it\n",
        "- In **policy iteration**, we do several passes that update utilities with fixed policy (each pass is fast 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 pass)\n",
        "- The new policy will be better (or we are done)\n",
        "- Both are dynamic programs for solving MDPs\n",
        "- You want to:\n",
        "  Compute optimal values: use value iteration or policy iteration \\n\n",
        "  Compute values for a particular policy: use policy evaluation \\n\n",
        "  Turn your values into a policy: use policy extraction (one-step look-ahead)\n",
        "Maximum Expected Utility\n",
        "- For average-case expectimax reasoning, we need **magnitudes** to be meaningful (recall the $x^2$ example)\n",
        "Rational Preferences\n",
        "- Orderability: $(A \\succ B) \\lor (B \\succ A) \\lor (A \\sim B)$\n",
        "- Transitivity: $(A \\succ B) \\land (B \\succ C) \\Rightarrow (A \\succ C)$\n",
        "- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p, A: 1-p, C] \\sim B$\n",
        "- Substitutability: $A \\sim B \\Rightarrow [p, A; 1-p,C] \\sim [p,B; 1-p, C] $\n",
        "- Monotonicity: $A \\succ B \\Rightarrow (p \\geq q \\Leftrightarrow [p,A;1-p,B] \\succcurlyeq [q,A; 1-q,B])$ \\n\n",
        "Questions \\n\n",
        "Which of the following statements is true of a Markov decision process or MDP? \\n\n",
        "- A solution or policy must specify what the agent should do for all states that it can reach. \\n\n",
        "  Discounted reward is not absolutely necessary, proper policy might not always exist - see for example Figure 17.2 bottom right. \\n\n",
        "- An MDP is defined for a fully observable, stochastic environment. \\n\n",
        "  Discounted reward is not absolutely necessary, proper policy might not always exist - see for example Figure 17.2 bottom right. \\n\n",
        "Select all the following components that the policy iteration algorithm equation takes into account. \\n\n",
        "- The probability of entering a state S’ from state S after performing action A \\n\n",
        "  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration. \\n\n",
        "- All of the actions A that an agent can take. \\n\n",
        "  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration.  \\n\n",
        "- The utility associated with a state S. \\n\n",
        "  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration.  \\n\n",
        "Policy is implicitly updated in value iteration. \\n\n",
        "- True \\n\n",
        "  Policy corresponds to the action paired with the max Q-value. \\n\n",
        "Compared to value iteration, policy iteration often converges in fewer iterations but is more costly (i.e. greater time complexity) per iteration. \\n\n",
        "- True \\n\n",
        "  Policy iteration converges in fewer iterations, but takes O(|S|^3) per iteration, whereas value iteration takes O(|A|*|S|^2). \\n\n",
        "The utility function estimate must be completely accurate in order to get an optimal policy.? \\n\n",
        "- False \\n\n",
        "  The utility is a human defined function to evaluate the state and thus it cannot be completely correct. But it could still obtain an optimal policy as long as it describes the state properly. \\n\n",
        "Policy is explicitly updated in value iteration. \\n\n",
        "- False \\n\n",
        "  Policy is implicitly updated in value iteration, see textbook section 17.2. \\n\n",
        "What is the principle of MEU? \\n\n",
        "- An agent should maximize the weighted average of their utilities.\\n  \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\" : \"Maps from outcome (states of the world) to real numbers that describe an agen's preferences\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"Principle of Maximum Expected Utility\" : \"A rational agent should choose the action that **maximizes its expected utility, given its knowledge**\",\n",
        "\"MEU Principle\": \"Given any preferences satisfying these constraints, there exists a real-valued function U such that $U(A) \\geq U(B) \\Leftrightarrow A \\succurlyeq B$\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 235,
      "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": "4a00bcc4-28d8-4933-96de-283cb69b8d9e"
      },
      "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": 236,
      "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 Chapter 16.1 summary.  $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 Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nMARKOV DECISION PROCESS (\"MDP\") has the following components: \n\n- set of states $s \\in S$ \n\n- set of actions $a \\in A$ \n\n- a transition function $T(s,a,s')$, the probability that executing action $a$ in $s$ will lead to $s'$: $P(s' | s, a)$ \n\n- a reward function $R(s,a,s')$\n\n- an initial state $s_0$\n\n- **Optionally**, one or more terminal states \n\nSOLUTION = POLICY: \n\nIn search problems, a solution was a sequence of actions. Because of the non-determinism in MDPs, solution to an MDP is a **policy** \n\n- Policy $\\pi(s) = a$ and $\\pi^*(s)$ denotes the **optimal policy**\n \nEven though the policy told me to go right here, there’s no guarantee that me picking the action Right will result in me moving right. It’s stochastic! Even if the **same policy** is executed multiple times by the agent, this may lead to different sequence of states and actions (**environment history**), and thus a **different score** under the reward function. \n\nTherefore we need to compute the **expected utility** of all the possible paths generated by a policy. \n\nSEQUENCES OF REWARDS \n\n- Finite horizons: Fixed time (**N** actions) after which the game ends and the agent gets no additional score. Policies that depend on time are called\n**nonstationary**. \n\n- Infinite horizons: With no fixed time limit, there is no reason to behave differently in the same state at different times. The optimal policy is **stationary**. \n\nOPTIMAL QUANTITIES \n\n- The value (utility) of a state s: $V*(s) =$ expected utility starting in s and acting optimally $= \\max_{a} Q*(s,a)$ \n\n- The value (utility) of a q-state (s,a): $Q*(s,a) = $ expected utility starting out having taken action a from state s and (thereafter) acting optimally $= \\sum_{s'} T(s, a, s')[R(s,a,s') + \\gamma V*(s')]$\n\n- Combining the two is the **BELLMAN EQUATION**: $V^*(s) = \\max_{a} \\sum_{s'} T(s, a, s') [R(s,a,s') + \\gamma V^*(s')]$ \n\nTIME-LIMITED VALUES: \n- Key idea: time-limited values. Define $V_{k}(s)$ to be the optimal value of $s$ if the game ends in $k$ more time steps. \n\n**VALUE ITERATION**\n- Start with $V_{0} = 0$: no time steps left means an expected reward sum of 0 \n- Given vector of $V_{k}(s)$ values, do one ply of expectimax from each state: $V_{k+1} \\leftarrow \\max_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n \n- Repeat until convergence\n- Complexity of each iteration: $O(S^2A)$ \n**POLICY EVALUATION** \n- Do what $\\pi$ says to do. Then the tree would be simpler - only one action per state\n- Compute the utility of a state $s$ under a fixed (generally non-optimal) policy\n- $V_{\\pi}(s)=$ expected total discounted rewards starting in $s$ and following $\\pi$ \n- $V_{\\pi}(s) = \\sum_{s'}T(s, \\pi(s),s')[R(s,\\pi(s),s') + \\gamma V_{\\pi}(s')]$\n- Efficiency: $O(S^2)$ per iteration\n- How do we calculate the V's for a fixed policy $\\pi$? Idea 1: turn recursive Bellman equations into updates. **Idea 2**: Bellman equations are just a linear system. Solve with Matlab \n**COMPUTING ACTIONS FROM Q-VALUES**\n- Completely trivial: $\\pi^*(s) = arg \\max_{a} Q^*(s,a)$. Actions are easier to select from Q-values than values. \nProbmes with Value Iteration\n1. It's slow - $O(S^2A)$ per iteration\n2. The max at each state rarely changes\n3. The policy often converges long before the values\n- Policy iteration is much faster - using the one-step look-ahead: \n\n  $\\pi_{i+1}(s) = arg \\max_{a} \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V^{\\pi_{i}}(s')]$ \n\nComparison\n- Both value iteration and policy iteration compute the same thing (all optimal values)\n- In **value iteration**, every iteration updates both the values and (implicity) the policy\n- We do not track the policy, but taking the max over actions implicitly recomputes it\n- In **policy iteration**, we do several passes that update utilities with fixed policy (each pass is fast 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 pass)\n- The new policy will be better (or we are done)\n- Both are dynamic programs for solving MDPs\n- You want to:\n  Compute optimal values: use value iteration or policy iteration \n\n  Compute values for a particular policy: use policy evaluation \n\n  Turn your values into a policy: use policy extraction (one-step look-ahead)\nMaximum Expected Utility\n- For average-case expectimax reasoning, we need **magnitudes** to be meaningful (recall the $x^2$ example)\nRational Preferences\n- Orderability: $(A \\succ B) \\lor (B \\succ A) \\lor (A \\sim B)$\n- Transitivity: $(A \\succ B) \\land (B \\succ C) \\Rightarrow (A \\succ C)$\n- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p, A: 1-p, C] \\sim B$\n- Substitutability: $A \\sim B \\Rightarrow [p, A; 1-p,C] \\sim [p,B; 1-p, C] $\n- Monotonicity: $A \\succ B \\Rightarrow (p \\geq q \\Leftrightarrow [p,A;1-p,B] \\succcurlyeq [q,A; 1-q,B])$\nQuestions \n\nWhich of the following statements is true of a Markov decision process or MDP? \n\n- A solution or policy must specify what the agent should do for all states that it can reach. \n\n  Discounted reward is not absolutely necessary, proper policy might not always exist - see for example Figure 17.2 bottom right. \n\n- An MDP is defined for a fully observable, stochastic environment. \n\n  Discounted reward is not absolutely necessary, proper policy might not always exist - see for example Figure 17.2 bottom right. \n\nSelect all the following components that the policy iteration algorithm equation takes into account. \n\n- The probability of entering a state S’ from state S after performing action A \n\n  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration. \n\n- All of the actions A that an agent can take. \n\n  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration.  \n\n- The utility associated with a state S. \n\n  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration.  \n\nPolicy is implicitly updated in value iteration. \n\n- True \n\n  Policy corresponds to the action paired with the max Q-value. \n\nCompared to value iteration, policy iteration often converges in fewer iterations but is more costly (i.e. greater time complexity) per iteration. \n\n- True \n\n  Policy iteration converges in fewer iterations, but takes O(|S|^3) per iteration, whereas value iteration takes O(|A|*|S|^2). \n\nThe utility function estimate must be completely accurate in order to get an optimal policy.? \n\n- False \n\n  The utility is a human defined function to evaluate the state and thus it cannot be completely correct. But it could still obtain an optimal policy as long as it describes the state properly. \n\nPolicy is explicitly updated in value iteration. \n\n- False \n\n  Policy is implicitly updated in value iteration, see textbook section 17.2. \n\nWhat is the principle of MEU? \n\n- An agent should maximize the weighted average of their utilities.\n  \n\n\n## Module 8 Definitions\n* **Utility function** - Maps from outcome (states of the world) to real numbers that describe an agen's preferences\n* **Expected utility** - your definition here\n* **Principle of maximum expected utility** - A rational agent should choose the action that **maximizes its expected utility, given its knowledge**\n* **Meu principle** - Given any preferences satisfying these constraints, there exists a real-valued function U such that $U(A) \\geq U(B) \\Leftrightarrow A \\succurlyeq B$\n* **Etc.** - your definition here\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 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "Reinforcement Learning Important Ideas:\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\n",
        "Basic idea:\n",
        "- Receive feedback in the form of **rewards**\n",
        "- Agent's utility is defined by the reward function\n",
        "- Must (learn to) act so as to **maximize expected rewards**\n",
        "- All learning is based on observed sampels of outcomes \\n\n",
        "MDP vs Reinforcement Learning\n",
        "In MDP: \\n\n",
        "- A set of states $s \\in S$\n",
        "- A set of actions (per state) A \n",
        "- A model $T(s,a,s')$\n",
        "- A reward function $R(s,a,s')$\n",
        "- Looking for a policy $\\pi(s)$ \\n\n",
        "Reinforcement learning: do not know T or R \\n\n",
        "- We do not know which states are good or what the actions do \\n\n",
        "- Must actually try actions and states out to learn \\n\n",
        "Model-Based Learning (Try to learn the probability, i.e. the Model)\n",
        "- Learn an approximate modle based on experiences \\n\n",
        "- Solve for values as if the learned model were correct \\n\n",
        "- Step 1: Learn empirical MDP model \\n\n",
        "  Count outcomes $s'$ for each $s, a$ \\n\n",
        "  Normalize to give an estimate of $\\hat{T}(s,a,s')$ \\n\n",
        "  Discover each $\\hat{R}(s,a,s')$ where we experience $(s,a,s')$ \\n\n",
        "- Step 2: Solve the learned MDP, for example, by using value iteration \\n\n",
        "  Train and test \\n\n",
        "Model-Free Learning \n",
        "- Input: a fixed policy $\\pi(s)$\n",
        "- Do not know the transitions $T(s,a,s')$\n",
        "- Do not know the rewards $R(s,a,s')$\n",
        "- Goal is to learn the state values\n",
        "- Learner is along for the ride. No choice about what actions to take. Just excute the policy and learn from experience \\n\n",
        "Direct Evaluation\n",
        "- Compute values for each state under $\\pi$ \n",
        "- Act according to $\\pi$ \n",
        "- Every time you visit a state, write what the sum of discounted rewards turned out to be\n",
        "- Average those samples \\n\n",
        "- Good about Direct Evaluation: easy to understand, does not require knowledge of T and R. Eventually compultes the correct average values\n",
        "- Problems with Direct Evaluation: wastes information about state connections, each state must be learned separately, takes long time \\n\n",
        "Why not use Policy Evaluation?\n",
        "- Simplified Bellman updates calculate $V$ for a fixed policy\n",
        "- Key problem: we cannot update $V$ without knowing $T$ and $R$\n",
        "One Step further: Sample-Based Policy Evaluation\n",
        "- We want to improve our estimate of $V$ by computing these averages: \\n\n",
        "  $V^{\\pi}_{k+1} \\leftarrow \\sum_{s'}T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V^{\\pi}_{k}(s')]$\n",
        "- Idea: take samples of outcomes $s'$ by doing the action and average: \\n\n",
        "  sample1 $= R(s,\\pi(s),s'_{1} + \\gamma V^{\\pi}_{k}(s'_1))$ \\n\n",
        "  sample2 $= R(s,\\pi(s),s'_{2} + \\gamma V^{\\pi}_{k}(s'_2))$ \\n\n",
        "  sampleN $= R(s,\\pi(s),s'_{n} + \\gamma V^{\\pi}_{k}(s'_n))$ \\n\n",
        "  $V^{\\pi}_{k+1} \\leftarrow (1/n) \\sum_{i} sample_i$ \\n\n",
        "**TEMPORAL DIFFERENCE LEARNING**\n",
        "- Big idea: learn from every experience. Update $V(s)$ each time we experience a transition $(s,a,s',r)$ \\n\n",
        "- Likely outcomes $s'$ will contribute updates more often \\n\n",
        "- Policy still fixed, still doing evaluation. Move values toward value of whatever successor occurs: running average. \\n\n",
        "  Sample of $V(s)$: sample $= R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')$ \\n\n",
        "  Update to $V(s)$: $V^{\\pi}(s) \\leftarrow (1-a)V^{\\pi}(s) + (a)$ sample \\n\n",
        "  Same update: $V(s)$: $V^{\\pi}(s) \\leftarrow V^{\\pi}(s) + (a)$ $($ sample $-V^{\\pi}(s))$ \\n\n",
        "Exponential Moving Average\n",
        "- Exponential moving average is the running interpolation update: $x_n = (1-a) \\cdot x_{n-1} + a \\cdot x_n $ \\n\n",
        "- Makes recent samples more important \\n\n",
        "- Decreasing learning rate (alpha) can give converging averages \\n\n",
        "Problems with Temporal Value Learning \n",
        "- TD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages\n",
        "- However, if we want to turn values into a (new) policy, we are sunk: \\n\n",
        "  $\\pi(s) = arg \\max_{a} Q(s,a)$ \\n\n",
        "  $Q(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V(s')]$\\n\n",
        "  Still need the $T$ here. \\n\n",
        "  Idea: learn Q-values, not values \\n\n",
        "  Make action selection model-free too! \\n\n",
        "**ACTIVE REINFORCEMENT LEARNING**\n",
        "- Full reinforcement learning: optimal policies \n",
        "- You do not know the transitions $T$ \\n\n",
        "- You do not know the rewards $R$ \\n\n",
        "- You choose the actions now \\n\n",
        "- Goal: learn the optimal policy and values \\n\n",
        "- In this case, learner makes choices. Fundamental tradeoff: exploration vs exploitation \\n\n",
        "- This is NOT offline planning. You actually take actions in the world and find out what happens \\n\n",
        "- Learn $Q(s,a)$ value as you go \\n\n",
        "  Receive a sample $(s,a,s',r) \\n\n",
        "  Consider your old estimate $Q(s,a)$ \\n\n",
        "  Consider your new sample estimate: \\n\n",
        "  $ sample = R(s,a,s') + \\gamma \\max_{a'} Q(s',a')$ \\n\n",
        "- Formula: \\n\n",
        "  $Q(s,a) \\leftarrow (1-a) Q(s,a) + (a)[sample]$ \\n\n",
        "**Q-LEARNING PROPERTIES**\n",
        "- Amazing result: Q-learning converges to optimal policy, even if you're acting suboptimally\n",
        "- This is called off-policy learning \n",
        "- Caveats: \\n\n",
        "  You have to explore enough \\n\n",
        "  You have to eventually make the learning rate small enough \\n\n",
        "  ... but not decrease it too quickly \\n\n",
        "  Basically, in the limit, it does not matter how you select actions \\n\n",
        "Exploration vs Exploitation \n",
        "Schemes for forcing exploration\n",
        "- Random action ($\\epsilon$-greedy) \\n\n",
        "- Problem with random actions:\n",
        "  You do eventually explore the space, but keep thrashing around once learning is done \\n\n",
        "  One solution: lower $\\epsilon$ over time\n",
        "- Exploration function: takes a value estimate $u$ and a visit count $n$, and returns an optimistic utility: \\n\n",
        "  $f(u,n) = u + k/n $ /n\n",
        "  Regular Q-update: $Q(s,a) \\leftarrow a R(s,a,s') + \\gamma \\max_{a'} Q(s',a')$ \\n\n",
        "  Modified Q-update: $Q(s,a) \\leftarrow a R(s,a,s') + \\gamma \\max_{a'}f(Q(s',a'), N(s',a'))$ \\n\n",
        "Regret\n",
        "- Even if you learn the optimal policy, you still make mistakes along the way! \\n\n",
        "- Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards \\n\n",
        "- Minimizing regret goes beyond learning to be optimal – it requires optimally learning to be optimal \\n\n",
        "- Example: random exploration and exploration functions both end up optimal, but random exploration has higher regret \\n\n",
        "Approximate Q-Learning\n",
        "- Sliding scale\n",
        "- Adjust weights\n",
        "- There is no guarantee that it will always find the optimal policy. \\n\n",
        "Questions \\n\n",
        "Which of the following is given to the agent when using passive reinforcement learning? Check all that apply. \\n\n",
        "- All of the states that can be reached by the agent. \\n\n",
        "  The goal of passive reinforcement learning is to compute values for each state under policy π, the transition and reward are not required for direction evaluation. \\n\n",
        "- The agent’s policy π. \\n\n",
        "  The goal of passive reinforcement learning is to compute values for each state under policy π, the transition and reward are not required for direction evaluation. \\n\n",
        "Direct utility estimation computes a Utility function U by considering the connection between the utility of a state and the utility of its successor states. \\n\n",
        "- False \\n\n",
        "  Direct utility estimation only use the sample transitions. \\n\n",
        "Which of the following is true of both adaptive dynamic programming (ADP) learning and temporal-difference (TD) learning? \\n\n",
        "- The utility of a state is adjusted locally to agree with the utility of at least one successor state. \\n\n",
        "  The utility of a state is adjusted locally to agree with the utility of at least one successor state. \\n\n",
        "Which of the following equations are updates for TD Q-learning?  Check all that apply. \\n\n",
        "- Q(s,a)←Q(s,a)+α(R(s)+γmaxa′Q(s′,a′)−Q(s,a)) \\n\n",
        "What is this equation $$U(s)=R(s)+\\gamma \\max _{a} \\sum_{s^{\\prime}} P\\left(s^{\\prime} \\mid s, a\\right) U\\left(s^{\\prime}\\right)$$ ? \\n\n",
        "- The Bellman equation \\n\n",
        "Q-learning with linear function approximation (weighted linear function of a set of features) will always converge to the optimal policy. \\n\n",
        "- False \\n\n",
        "  It is possible for Q learning with linear function approximation to converge to the optimal policy, but there is no guarantee that it always finds such an optimal policy. For example, consider the problem where the true Q-function is a quadratic function. Q(s, a) where a= 0 or 1 and s can be any real number and the true function is Q(s,0) = s^2 and Q(s,1) = 3s^4 for all s. Then if our function approximator is linear Q(s,a) = k*s + l*a + b, then there exists no k,l, and b that can represent the true Q function because we are trying to fit a linear to a quadratic function. \\n\n",
        "In reinforcement learning, a deterministic policy is \\n\n",
        "- A mapping from states to actions \\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Deterministic Policy\" : \"A mapping from states to actions\",\n",
        "}"
      ],
      "execution_count": 241,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "6c1c879a-26fc-4b40-921b-bc731119fe42"
      },
      "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": 242,
      "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 Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\nReinforcement Learning Important Ideas:\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\nBasic idea:\n- Receive feedback in the form of **rewards**\n- Agent's utility is defined by the reward function\n- Must (learn to) act so as to **maximize expected rewards**\n- All learning is based on observed sampels of outcomes \n\nMDP vs Reinforcement Learning\nIn MDP: \n\n- A set of states $s \\in S$\n- A set of actions (per state) A \n- A model $T(s,a,s')$\n- A reward function $R(s,a,s')$\n- Looking for a policy $\\pi(s)$ \n\nReinforcement learning: do not know T or R \n\n- We do not know which states are good or what the actions do \n\n- Must actually try actions and states out to learn \n\nModel-Based Learning (Try to learn the probability, i.e. the Model)\n- Learn an approximate modle based on experiences \n\n- Solve for values as if the learned model were correct \n\n- Step 1: Learn empirical MDP model \n\n  Count outcomes $s'$ for each $s, a$ \n\n  Normalize to give an estimate of $\\hat{T}(s,a,s')$ \n\n  Discover each $\\hat{R}(s,a,s')$ where we experience $(s,a,s')$ \n\n- Step 2: Solve the learned MDP, for example, by using value iteration \n\n  Train and test \n\nModel-Free Learning \n- Input: a fixed policy $\\pi(s)$\n- Do not know the transitions $T(s,a,s')$\n- Do not know the rewards $R(s,a,s')$\n- Goal is to learn the state values\n- Learner is along for the ride. No choice about what actions to take. Just excute the policy and learn from experience \n\nDirect Evaluation\n- Compute values for each state under $\\pi$ \n- Act according to $\\pi$ \n- Every time you visit a state, write what the sum of discounted rewards turned out to be\n- Average those samples \n\n- Good about Direct Evaluation: easy to understand, does not require knowledge of T and R. Eventually compultes the correct average values\n- Problems with Direct Evaluation: wastes information about state connections, each state must be learned separately, takes long time \n\nWhy not use Policy Evaluation?\n- Simplified Bellman updates calculate $V$ for a fixed policy\n- Key problem: we cannot update $V$ without knowing $T$ and $R$\nOne Step further: Sample-Based Policy Evaluation\n- We want to improve our estimate of $V$ by computing these averages: \n\n  $V^{\\pi}_{k+1} \\leftarrow \\sum_{s'}T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V^{\\pi}_{k}(s')]$\n- Idea: take samples of outcomes $s'$ by doing the action and average: \n\n  sample1 $= R(s,\\pi(s),s'_{1} + \\gamma V^{\\pi}_{k}(s'_1))$ \n\n  sample2 $= R(s,\\pi(s),s'_{2} + \\gamma V^{\\pi}_{k}(s'_2))$ \n\n  sampleN $= R(s,\\pi(s),s'_{n} + \\gamma V^{\\pi}_{k}(s'_n))$ \n\n  $V^{\\pi}_{k+1} \\leftarrow (1/n) \\sum_{i} sample_i$ \n\n**TEMPORAL DIFFERENCE LEARNING**\n- Big idea: learn from every experience. Update $V(s)$ each time we experience a transition $(s,a,s',r)$ \n\n- Likely outcomes $s'$ will contribute updates more often \n\n- Policy still fixed, still doing evaluation. Move values toward value of whatever successor occurs: running average. \n\n  Sample of $V(s)$: sample $= R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')$ \n\n  Update to $V(s)$: $V^{\\pi}(s) \\leftarrow (1-a)V^{\\pi}(s) + (a)$ sample \n\n  Same update: $V(s)$: $V^{\\pi}(s) \\leftarrow V^{\\pi}(s) + (a)$ $($ sample $-V^{\\pi}(s))$ \n\nExponential Moving Average\n- Exponential moving average is the running interpolation update: $x_n = (1-a) \\cdot x_{n-1} + a \\cdot x_n $ \n\n- Makes recent samples more important \n\n- Decreasing learning rate (alpha) can give converging averages \n\nProblems with Temporal Value Learning \n- TD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages\n- However, if we want to turn values into a (new) policy, we are sunk: \n\n  $\\pi(s) = arg \\max_{a} Q(s,a)$ \n\n  $Q(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V(s')]$\n\n  Still need the $T$ here. \n\n  Idea: learn Q-values, not values \n\n  Make action selection model-free too! \n\n**ACTIVE REINFORCEMENT LEARNING**\n- Full reinforcement learning: optimal policies \n- You do not know the transitions $T$ \n\n- You do not know the rewards $R$ \n\n- You choose the actions now \n\n- Goal: learn the optimal policy and values \n\n- In this case, learner makes choices. Fundamental tradeoff: exploration vs exploitation \n\n- This is NOT offline planning. You actually take actions in the world and find out what happens \n\n- Learn $Q(s,a)$ value as you go \n\n  Receive a sample $(s,a,s',r) \n\n  Consider your old estimate $Q(s,a)$ \n\n  Consider your new sample estimate: \n\n  $ sample = R(s,a,s') + \\gamma \\max_{a'} Q(s',a')$ \n\n- Formula: \n\n  $Q(s,a) \\leftarrow (1-a) Q(s,a) + (a)[sample]$ \n\n**Q-LEARNING PROPERTIES**\n- Amazing result: Q-learning converges to optimal policy, even if you're acting suboptimally\n- This is called off-policy learning \n- Caveats: \n\n  You have to explore enough \n\n  You have to eventually make the learning rate small enough \n\n  ... but not decrease it too quickly \n\n  Basically, in the limit, it does not matter how you select actions \n\nExploration vs Exploitation \nSchemes for forcing exploration\n- Random action ($\\epsilon$-greedy) \n\n- Problem with random actions:\n  You do eventually explore the space, but keep thrashing around once learning is done \n\n  One solution: lower $\\epsilon$ over time\n- Exploration function: takes a value estimate $u$ and a visit count $n$, and returns an optimistic utility: \n\n  $f(u,n) = u + k/n $ /n\n  Regular Q-update: $Q(s,a) \\leftarrow a R(s,a,s') + \\gamma \\max_{a'} Q(s',a')$ \n\n  Modified Q-update: $Q(s,a) \\leftarrow a R(s,a,s') + \\gamma \\max_{a'}f(Q(s',a'), N(s',a'))$ \n\nRegret\n- Even if you learn the optimal policy, you still make mistakes along the way! \n\n- Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards \n\n- Minimizing regret goes beyond learning to be optimal – it requires optimally learning to be optimal \n\n- Example: random exploration and exploration functions both end up optimal, but random exploration has higher regret \n\nApproximate Q-Learning\n- Sliding scale\n- Adjust weights\n- There is no guarantee that it will always find the optimal policy. \n\nQuestions \n\nWhich of the following is given to the agent when using passive reinforcement learning? Check all that apply. \n\n- All of the states that can be reached by the agent. \n\n  The goal of passive reinforcement learning is to compute values for each state under policy π, the transition and reward are not required for direction evaluation. \n\n- The agent’s policy π. \n\n  The goal of passive reinforcement learning is to compute values for each state under policy π, the transition and reward are not required for direction evaluation. \n\nDirect utility estimation computes a Utility function U by considering the connection between the utility of a state and the utility of its successor states. \n\n- False \n\n  Direct utility estimation only use the sample transitions. \n\nWhich of the following is true of both adaptive dynamic programming (ADP) learning and temporal-difference (TD) learning? \n\n- The utility of a state is adjusted locally to agree with the utility of at least one successor state. \n\n  The utility of a state is adjusted locally to agree with the utility of at least one successor state. \n\nWhich of the following equations are updates for TD Q-learning?  Check all that apply. \n\n- Q(s,a)←Q(s,a)+α(R(s)+γmaxa′Q(s′,a′)−Q(s,a)) \n\nWhat is this equation $$U(s)=R(s)+\\gamma \\max _{a} \\sum_{s^{\\prime}} P\\left(s^{\\prime} \\mid s, a\right) U\\left(s^{\\prime}\right)$$ ? \n\n- The Bellman equation \n\nQ-learning with linear function approximation (weighted linear function of a set of features) will always converge to the optimal policy. \n\n- False \n\n  It is possible for Q learning with linear function approximation to converge to the optimal policy, but there is no guarantee that it always finds such an optimal policy. For example, consider the problem where the true Q-function is a quadratic function. Q(s, a) where a= 0 or 1 and s can be any real number and the true function is Q(s,0) = s^2 and Q(s,1) = 3s^4 for all s. Then if our function approximator is linear Q(s,a) = k*s + l*a + b, then there exists no k,l, and b that can represent the true Q function because we are trying to fit a linear to a quadratic function. \n\nIn reinforcement learning, a deterministic policy is \n\n- A mapping from states to actions \n\n\n\n## Module 9 Definitions\n* **Deterministic policy** - A mapping from states to actions\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "Uncertainty\n",
        "- Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms) \\n\n",
        "- Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present) \\n\n",
        "- Model: Agent knows something about how the known variables relate to the unknown variables \\n\n",
        "What Probabilities are about?\n",
        "Like logical assertions, probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is. \\n\n",
        "In probability theory, the possible worlds are called the sample space, and they mutually exclusive and exhaustive. \\n\n",
        "A fully specified probability model associates a probability P(𝑤) with each possible world 𝑤 \\n\n",
        "Axioms of Probability\n",
        "- The probability of any possible world is between 0 and 1\n",
        "- The total probability of the set of all possible world is 1 \\n\n",
        "Probabilistic Models: \n",
        "- (Random) variables with domains\n",
        "- Assignments are called outcomes\n",
        "- Joint distributions: say whether assignments (outcomes) are likely\n",
        "- Normalized: sum to 1.0\n",
        "- Ideally: only certain variables directly interact \\n\n",
        "Marginal Distributions\n",
        "- Marginal distributions are sub-tables which eliminate variables\n",
        "- Marginalization (summing out): Combine collapsed rows by adding \\n\n",
        "  $P(t) = \\sum_{s}P(t,s)$ \\n\n",
        "  $P(s) = \\sum_{t}P(t,s)$ \\n\n",
        "- Takes $d^n$ to fully map out these tables \n",
        "Conditional Probabilities\n",
        "- A simple relation between joint and conditional probabilities \\n\n",
        "  $P(a|b) = P(a,b)/P(b)$ \\n\n",
        "Probabilistic Inference \n",
        "- Probabilistic inference: compute a desired probability from other known probabilities (e.g. conditional from joint) \\n\n",
        "Inference by Enumeration \n",
        "- General Cases \\n\n",
        "  Evidence variables: $E_1, ..., E_k = e_1, ... e_k$ \\n\n",
        "  Query variable: $Q$ \\n\n",
        "  Hidden variables: $H_1,..., H_r$ \\n\n",
        "- Step 1: Select the entries consistent with the evidence \\n\n",
        "  Step 2: Sum out H to get joint of Query and Evidence \\n\n",
        "  $P(Q,e_1,...,e_k) = \\sum_{h_1,...,h_k} P(Q,h_1,...,h_k,e_1,...,e_k)$ \\n\n",
        "  Step 3: Normalize \\n\n",
        "  $1/Z$ \\n\n",
        "  $Z = \\sum_{q}P(Q,e_1,...,e_k)$\\n\n",
        "  $P(Q|e_1,...,e_k) = (1/Z)P(Q,e_1,...,e_k)$ \\n\n",
        "Product Rule \\n\n",
        "$P(y)P(x|y) = P(x,y)$ \\n\n",
        "Chain Rule \\n\n",
        "$P(x_1,x_2,...,x_n) = \\prod_{i}P(x_i | x_1,...,x_{i-1})$ \\n\n",
        "Bayes's Rule \\n\n",
        "$P(x,y) = P(x|y)P(y) = P(y|x)P(x)$ \\n\n",
        "Probabilistic Language Modeling\n",
        "- Goal: compute the probability of a sentence or sequence of words \\n\n",
        "  P(W) = P(w1,w2,w3,w4,w5...wn) \\n\n",
        "- Related task: probability of an upcoming word \\n\n",
        "  P(w5|w1,w2,w3,w4) \\n\n",
        "- A model that computes either of these \\n\n",
        "  P(W) or P(wn|w1,w2...wn-1) is called a language model \\n\n",
        "- **Uses the Chain Rule** \\n\n",
        "N-Gram Models\n",
        "- In general this is an insufficient model of language because language has long-distance dependencies \\n\n",
        "Questions \\n\n",
        "Which of the following must be true of the probabilities of two events, A and B, if A is independent of B? \\n\n",
        "- P(A | B) = P(A) \\n\n",
        "- P(B | A) = P(B) \\n\n",
        "- P(A ∨ B) = P(A) + P(B) - P(A ∧ B) \\n\n",
        "- P(A ∧ B) = P(A) P(B) \\n\n",
        "Which of the following are equivalent to the joint probability P(X1,X2,X3,X4)? Check all that apply. \\n\n",
        "- P(X2,X1)P(X3|X2,X1)P(X4|X3,X2,X1) \\n\n",
        "- P(X1|X2,X3,X4)P(X4)P(X3|X4)P(X2|X3,X4) \\n \n",
        "- P(X1)P(X2|X1)P(X3|X2,X1)P(X4|X3,X2,X1) \\n\n",
        "In a bigram model, one assumes that words w{i} and w{i - 2} are independent for i > 2. \\n\n",
        "- True \\n\n",
        "  Bigram model only considers the w{i - 1}. \\n\n",
        "When we compute a tri-gram, we normalize the following to add up to 1: \\n\n",
        "- the probabilities of all words w given w{i - 1}, w{i - 2} \\n\n",
        "  Trigram model considers the previous two words. \\n\n",
        "How can we estimate the probability of a sentence P(w1, w2, …, wN)?  \\n\n",
        "- By applying the chain rule. \\n\n",
        "What is the effect of the Markov assumption in n-gram language models? \\n\n",
        "- It makes it possible to estimate the probabilities from data. \\n\n",
        "  N-gram could learn the conditional probability from the document. \\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 243,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "4e71d283-ef5d-4b22-85ca-ad01f7e008c3"
      },
      "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": 244,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \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 Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nUncertainty\n- Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms) \n\n- Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present) \n\n- Model: Agent knows something about how the known variables relate to the unknown variables \n\nWhat Probabilities are about?\nLike logical assertions, probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is. \n\nIn probability theory, the possible worlds are called the sample space, and they mutually exclusive and exhaustive. \n\nA fully specified probability model associates a probability P(𝑤) with each possible world 𝑤 \n\nAxioms of Probability\n- The probability of any possible world is between 0 and 1\n- The total probability of the set of all possible world is 1 \n\nProbabilistic Models: \n- (Random) variables with domains\n- Assignments are called outcomes\n- Joint distributions: say whether assignments (outcomes) are likely\n- Normalized: sum to 1.0\n- Ideally: only certain variables directly interact \n\nMarginal Distributions\n- Marginal distributions are sub-tables which eliminate variables\n- Marginalization (summing out): Combine collapsed rows by adding \n\n  $P(t) = \\sum_{s}P(t,s)$ \n\n  $P(s) = \\sum_{t}P(t,s)$ \n\n- Takes $d^n$ to fully map out these tables \nConditional Probabilities\n- A simple relation between joint and conditional probabilities \n\n  $P(a|b) = P(a,b)/P(b)$ \n\nProbabilistic Inference \n- Probabilistic inference: compute a desired probability from other known probabilities (e.g. conditional from joint) \n\nInference by Enumeration \n- General Cases \n\n  Evidence variables: $E_1, ..., E_k = e_1, ... e_k$ \n\n  Query variable: $Q$ \n\n  Hidden variables: $H_1,..., H_r$ \n\n- Step 1: Select the entries consistent with the evidence \n\n  Step 2: Sum out H to get joint of Query and Evidence \n\n  $P(Q,e_1,...,e_k) = \\sum_{h_1,...,h_k} P(Q,h_1,...,h_k,e_1,...,e_k)$ \n\n  Step 3: Normalize \n\n  $1/Z$ \n\n  $Z = \\sum_{q}P(Q,e_1,...,e_k)$\n\n  $P(Q|e_1,...,e_k) = (1/Z)P(Q,e_1,...,e_k)$ \n\nProduct Rule \n\n$P(y)P(x|y) = P(x,y)$ \n\nChain Rule \n\n$P(x_1,x_2,...,x_n) = \\prod_{i}P(x_i | x_1,...,x_{i-1})$ \n\nBayes's Rule \n\n$P(x,y) = P(x|y)P(y) = P(y|x)P(x)$ \n\nProbabilistic Language Modeling\n- Goal: compute the probability of a sentence or sequence of words \n\n  P(W) = P(w1,w2,w3,w4,w5...wn) \n\n- Related task: probability of an upcoming word \n\n  P(w5|w1,w2,w3,w4) \n\n- A model that computes either of these \n\n  P(W) or P(wn|w1,w2...wn-1) is called a language model \n\n- **Uses the Chain Rule** \n\nN-Gram Models\n- In general this is an insufficient model of language because language has long-distance dependencies \n\nQuestions \n\nWhich of the following must be true of the probabilities of two events, A and B, if A is independent of B? \n\n- P(A | B) = P(A) \n\n- P(B | A) = P(B) \n\n- P(A ∨ B) = P(A) + P(B) - P(A ∧ B) \n\n- P(A ∧ B) = P(A) P(B) \n\nWhich of the following are equivalent to the joint probability P(X1,X2,X3,X4)? Check all that apply. \n\n- P(X2,X1)P(X3|X2,X1)P(X4|X3,X2,X1) \n\n- P(X1|X2,X3,X4)P(X4)P(X3|X4)P(X2|X3,X4) \n \n- P(X1)P(X2|X1)P(X3|X2,X1)P(X4|X3,X2,X1) \n\nIn a bigram model, one assumes that words w{i} and w{i - 2} are independent for i > 2. \n\n- True \n\n  Bigram model only considers the w{i - 1}. \n\nWhen we compute a tri-gram, we normalize the following to add up to 1: \n\n- the probabilities of all words w given w{i - 1}, w{i - 2} \n\n  Trigram model considers the previous two words. \n\nHow can we estimate the probability of a sentence P(w1, w2, …, wN)?  \n\n- By applying the chain rule. \n\nWhat is the effect of the Markov assumption in n-gram language models? \n\n- It makes it possible to estimate the probabilities from data. \n\n  N-gram could learn the conditional probability from the document. \n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "Conditional Independence\n",
        "- X and Y are **independent** if: \\n\n",
        "  For all $x, y$, $P(x,y) = P(x)P(y)$ \\n\n",
        "- X and Y are **conditionally independent** given Z \\n\n",
        "  For all $x, y, z$, $P(x,y|z) = P(x|y)P(y|z)$ \\n\n",
        "- Unconditional (absolute) independence very rare, and it doesn’t help us make inferences about other variables. \\n\n",
        "- Conditional independence is our most basic and robust form of knowledge about uncertain environments. \\n\n",
        "- X is conditionally independent of Y given Z, if and only if: \\n\n",
        "  For all $x, y, z$, $P(x,y|z) = P(x|z)P(y|z)$ \\n\n",
        "  or equivalently, if and only if: \\n\n",
        "  For all $x, y, z$, $P(x|z,y) = P(x|z)$ (Knowing y does not matter...) \\n\n",
        "Bayes Nets Assumptions \\n\n",
        "$P(x_i | x_1,...,x_{i-1}) = P(x_i | parents(X_i))$ \\n\n",
        "$P(x,y,z) = P(x)P(y|x)P(z|y)$ \\n\n",
        "D-separation \\n\n",
        "- Study independence properties for triples \\n\n",
        "- Analyze complex cases in terms of member triples \\n\n",
        "Reachability \\n\n",
        "- if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent \\n\n",
        "- **Almost works, but not quite** \\n\n",
        "**ACTIVE / INACTIVE PATHS** \\n\n",
        "Question: Are X and Y conditionally independent given evidence variables {Z}? \\n\n",
        "- Yes, if X and Y “d-separated” by Z \\n\n",
        "- Consider all (undirected) paths from X to Y \\n\n",
        "- No active paths = independence! \\n\n",
        "A path is active if each triple is active: \\n\n",
        "- Causal chain A → B → C where B is unobserved (either direction) \\n\n",
        "- Common cause A ← B → C where B is unobserved \\n\n",
        "- Common effect (aka v-structure) \\n\n",
        "  A → B ← C where B or one of its descendants is observed \\n\n",
        "- **All it takes to block a path is a single inactive segment** \\n\n",
        "Questions \\n\n",
        "The conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of all of the other variables (nodes). \\n\n",
        "- False \\n\n",
        "  Based on its ancestors(parents), see textbook 14.1 \\n\n",
        "Every variable in a Bayes net is independent of all of its descendants given its children. \\n\n",
        "- False \\n\n",
        "  It is independent given its parent. \\n\n",
        "Which of the following is true of locally structured (sparse) systems? Select all that apply. \\n\n",
        "- The structure grows linearly in complexity (rather than exponentially). \\n\n",
        "  Textbook section 14.2, definition of locally structured (sparse) systems. \\n\n",
        "More than one Bayesian network can be used to represent the same joint distribution. \\n\n",
        "- True \\n\n",
        "If two variables (nodes) X and Y in a Bayesian network do not share a path, which of the following must be true? \\n\n",
        "- X and Y are conditionally independent. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 245,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "99705fa8-0642-4a76-ae62-8ec8b2055152"
      },
      "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": 246,
      "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 Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\nConditional Independence\n- X and Y are **independent** if: \n\n  For all $x, y$, $P(x,y) = P(x)P(y)$ \n\n- X and Y are **conditionally independent** given Z \n\n  For all $x, y, z$, $P(x,y|z) = P(x|y)P(y|z)$ \n\n- Unconditional (absolute) independence very rare, and it doesn’t help us make inferences about other variables. \n\n- Conditional independence is our most basic and robust form of knowledge about uncertain environments. \n\n- X is conditionally independent of Y given Z, if and only if: \n\n  For all $x, y, z$, $P(x,y|z) = P(x|z)P(y|z)$ \n\n  or equivalently, if and only if: \n\n  For all $x, y, z$, $P(x|z,y) = P(x|z)$ (Knowing y does not matter...) \n\nBayes Nets Assumptions \n\n$P(x_i | x_1,...,x_{i-1}) = P(x_i | parents(X_i))$ \n\n$P(x,y,z) = P(x)P(y|x)P(z|y)$ \n\nD-separation \n\n- Study independence properties for triples \n\n- Analyze complex cases in terms of member triples \n\nReachability \n\n- if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent \n\n- **Almost works, but not quite** \n\n**ACTIVE / INACTIVE PATHS** \n\nQuestion: Are X and Y conditionally independent given evidence variables {Z}? \n\n- Yes, if X and Y “d-separated” by Z \n\n- Consider all (undirected) paths from X to Y \n\n- No active paths = independence! \n\nA path is active if each triple is active: \n\n- Causal chain A → B → C where B is unobserved (either direction) \n\n- Common cause A ← B → C where B is unobserved \n\n- Common effect (aka v-structure) \n\n  A → B ← C where B or one of its descendants is observed \n\n- **All it takes to block a path is a single inactive segment** \n\nQuestions \n\nThe conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of all of the other variables (nodes). \n\n- False \n\n  Based on its ancestors(parents), see textbook 14.1 \n\nEvery variable in a Bayes net is independent of all of its descendants given its children. \n\n- False \n\n  It is independent given its parent. \n\nWhich of the following is true of locally structured (sparse) systems? Select all that apply. \n\n- The structure grows linearly in complexity (rather than exponentially). \n\n  Textbook section 14.2, definition of locally structured (sparse) systems. \n\nMore than one Bayesian network can be used to represent the same joint distribution. \n\n- True \n\nIf two variables (nodes) X and Y in a Bayesian network do not share a path, which of the following must be true? \n\n- X and Y are conditionally independent. \n\n\n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "Naive Bayes \\n\n",
        "- Assume all features are independent effects of the label \\n\n",
        "  $P(Y | F_{0,0},...,F_{15,15})$ proportional to $P(Y) \\prod_{i,j}P(F_{i,j} |Y)$ \\n\n",
        "General Naive Bayes \\n\n",
        "- $P(Y,F_1,...,F_n) = P(Y) \\prod_{i}P(F_i|Y)$ \\n\n",
        "  |Y| x |F| to the n values -> n x |F| x |Y| parameters \\n\n",
        "- We only have to specify how each feature depends on the class \\n\n",
        "- Total number of parameters is linear in number of features \\n\n",
        "- Model is very simplistic, but often works anyway \\n\n",
        "What do we need in order to use Naive Bayes? \n",
        "- Inference method (we just saw this part) \\n\n",
        "- Estimates of local conditional probability tables \\n\n",
        "Important Concepts\n",
        "- Data: labeled instances, e.g. emails marked spam/ham \\n\n",
        "  Training set \\n\n",
        "  Held out (dev) set \\n\n",
        "  Test set\n",
        "- Features: attribute-value pairs which characterize each x \\n\n",
        "- Experimentation cycle \\n\n",
        "  Learn parameters (e.g. model probabilities) on training set \\n\n",
        "  (Tune hyperparameters on held-out set) \\n\n",
        "  Compute accuracy of test set \\n\n",
        "  Very important: never “peek” at the test set! \\n\n",
        "- Evaluation \\n\n",
        "  Accuracy: fraction of instances predicted correctly \\n\n",
        "- Overfitting and generalization \\n\n",
        "  Want a classifier which does well on test data \\n\n",
        "  Overfitting: fitting the training data very closely, but not generalizing well \\n\n",
        "- **To generalize better: we need to smooth or regularize the estimates** \\n\n",
        "Parameter Estimation\n",
        "- Estimating the distribution of a random variable\n",
        "- Empirically: use training data (learning!) \\n\n",
        "  E.g.: for each outcome x, look at the empirical rate of that value: \\n\n",
        "  $P_{ML}(x) = count(x) / total samples$ \\n\n",
        "  This is the estimate that maximizes the likelihood of the data \\n\n",
        "  $L_(x,theta) = \\prod_{i} P_{theta}(x_i)$ \\n\n",
        "  $theta_{ML} = arg \\max_{theta} \\prod_{i} P_{theta}(X_i)$ \\n\n",
        "Laplace Smoothing \\n\n",
        "- Pretend you saw every outcome once more than you actually did \\n\n",
        "  $P_{LAP}(x) = (c(x) + 1) / (\\sum_{x}[c(x) + 1])$ \\n\n",
        "  $P_{LAP}(x) = (c(x) + 1) / (N + |X|])$ \\n\n",
        "- Pretend you saw every outcome k extra times \\n\n",
        "  $P_{LAP}(x) = (c(x) + k) / (N + k|X|])$ \\n\n",
        "Tuning on Held-out Data \\n\n",
        "- Parameters: the probabilities P(X|Y), P(Y) \n",
        "- Hyperparameters: e.g. the amount / type of smoothing to do, k, α \\n\n",
        "- Tune hyperparameters on different data \\n\n",
        "- For each value of the hyperparameters, train and test on the held-out data \\n\n",
        "PERCEPTRON \\n\n",
        "- Notational Changes \\n\n",
        "  $\\sum_{j} w_j x_j = w \\cdot x$ \\n\n",
        "- With bias term $b$ \\n\n",
        "  $\\sum_{j} w_j x_j = w \\cdot x + b$ \\n\n",
        "Learning weights from examples\n",
        "- Perceptions can be used for all kinds of classification problems \\n\n",
        "- Think of the inputs as features representing something we want to classify \\n\n",
        "- The feature values for inputs are fixed, but we can choose different weight vectors. Depending on the weight vector that we pick, we will get a different classifier \\n\n",
        "Weight Updates \n",
        "- Start with weights = 0 \\n\n",
        "- For each training instance \\n\n",
        "  Classify with current weights \\n\n",
        "  If correct (i.e., y=y*), no change! \\n\n",
        "  If **WRONG**: adjust the weight vector \\n\n",
        "- If wrong, adjust the weight vector by **adding or subtracting the feature fector** \\n\n",
        "  $w = w + y* \\cdot f$\n",
        "Multiclass Decision Rule \\n\n",
        "- If we have multiple classes: \\n\n",
        "  A weight vector for each class \\n\n",
        "  Score (activation) of a class y \\n\n",
        "  $w_y \\cdot f(x)$ \\n\n",
        "  Prediction highest score wins \\n\n",
        "  $y = arg \\max_{y} w_y \\cdot f(x)$\n",
        "Updating Weights in Multiclass Perceptron \\n\n",
        "- Start with all weights = 0 \\n\n",
        "- Pick up training examples one by one \\n\n",
        "- Predict with current weights \\n\n",
        "  $y = arg \\max_{y} w_y \\cdot f(x)$ \\n\n",
        "- If correct, no change! \\n\n",
        "- If wrong: lower score of wrong answer, raise score of right answer \\n\n",
        "  $w_y = w_y - f(x)$ \\n\n",
        "  $w_{y^*} = w_{y^*} + f(x)$\n",
        "Properties of Perceptrons \n",
        "- Separability: true if some parameters get the training set perfectly correct \\n\n",
        "- Convergence: if the training is separable, perceptron will eventually converge (binary case) \\n\n",
        "- Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability \\n\n",
        "Problems with Perceptron\n",
        "- Noise: if the data isn’t separable, weights might thrash \\n\n",
        "- Mediocre generalization: finds a “barely” separating solution \\n\n",
        "- Overtraining: test / held-out accuracy usually rises, then falls \\n\n",
        "Fixing the Perceptron \\n\n",
        "- MIRA = Margin Infused Relaxed Algorithm \\n\n",
        "- Choose an update size that fixes the current mistake... ... but, minimizes the change to w \\n\n",
        "  $w_y = w_y - tau f(x)$ \\n\n",
        "  $w_{y^*} = w_{y^*} + tau f(x)$\n",
        "- Support Vector Machines \\n\n",
        "  Maximizing the margin: good according to intuition, theory, practice Only support vectors matter; other training examples are ignorable \\n\n",
        "  Support vector machines (SVMs) find the separator with max margin \\n\n",
        "  Basically, SVMs are MIRA where you optimize over all examples at once \\n\n",
        "Non-Linear Separators\n",
        "- Kenel trick\n",
        "- General idea: the original feature space can always be mapped to some higher-dimensional feature space where the training set is separable \\n\n",
        "CLASSIFICATION COMPARISON \\n\n",
        "Naive Bayes \\n\n",
        "- Builds a model training data \\n\n",
        "- Gives prediction probabilities \\n\n",
        "- Strong assumptions about feature independence • One pass through data (counting) \\n\n",
        "Perceptrons / MIRA \\n\n",
        "- Makes less assumptions about data \\n\n",
        "- Mistake-driven learning \\n\n",
        "- Multiple passes through data (prediction) \\n\n",
        "- Often more accurate \\n\n",
        "Questions \\n\n",
        "The Naive Bayes model is “naive” because it assumes that the features are conditionally independent of each other, given the class. \\n\n",
        "- True \\n\n",
        "Write down the form of the joint probability model P(X1,X2,X3,Y) for this data using the Naive Bayes assumption. (Y is the class) \\n\n",
        "- P(Y)P(X_1|Y)P(X_2|Y)P(X_3|Y) \\n\n",
        "  In naive bayes, the features are conditionally independent of each other, given the class. \\n\n",
        "In the perceptron training algorithm, weights are updated after every training instance. \\n\n",
        "- False \\n\n",
        "  Training is error-driven - weights are only updated when the predicted label is incorrect. \\n\n",
        "Consider a two-dimensional data distribution where points belonging to class A are arranged around the origin in a circle with radius ra, and points belonging to class B are arranged around the origin in a circle with radius rb, where ra<rb \\n\n",
        "- can separate the two classes if we use feature augmentation. \\n\n",
        "  If we augment the input with the features x2,y2, and a bias term, the problem becomes linearly separable. Decaying the learning rate will ensure that the weight vector converges, but since the unaugmented data is not linearly separable, this will still fail to separate the classes. Changing the order in which the instances are fed into the perceptron will not allow the perceptron to find a separating boundary. \\n\n",
        "For which of the following datasets would a single perceptron be unable to find a separating boundary (assuming we do not add additional features to the data): \\n\n",
        "- Class A: {(0,0), (1,1)}; Class B: {(0,1), (1,0)} \\n\n",
        "  The correct answer corresponds to the XOR problem, which is not linearly separable. All other options are linearly separable. \\n\n",
        "Given a non-random dataset, the perceptron algorithm guarantees that the weight vector will converge after a finite number of training iterations. \\n\n",
        "- False \\n\n",
        "  This is only true if the dataset is linearly separable. If it is not, the weight vector may fluctuate infinitely. The fluctuation can be remedied by techniques such as learning rate decay, but the basic perceptron algorithm is not guaranteed to converge. \\n\n",
        "The inference procedure for the perceptron classification algorithm is best summarized as: \\n\n",
        "- Compute a weighted sum, then apply a threshold. \\n\n",
        "  First, we compute the dot product of the weight vector and the input vector (that is, a weighted sum of the input features), and then threshold this value to output either true or false. If you picked the \"datum separatus\" option, you should consider transferring to Hogwarts. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 247,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9b13b71b-2d70-4976-c9e2-706d56940a4c"
      },
      "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": 248,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## 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 Your summary here \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\nNaive Bayes \n\n- Assume all features are independent effects of the label \n\n  $P(Y | F_{0,0},...,F_{15,15})$ proportional to $P(Y) \\prod_{i,j}P(F_{i,j} |Y)$ \n\nGeneral Naive Bayes \n\n- $P(Y,F_1,...,F_n) = P(Y) \\prod_{i}P(F_i|Y)$ \n\n  |Y| x |F| to the n values -> n x |F| x |Y| parameters \n\n- We only have to specify how each feature depends on the class \n\n- Total number of parameters is linear in number of features \n\n- Model is very simplistic, but often works anyway \n\nWhat do we need in order to use Naive Bayes? \n- Inference method (we just saw this part) \n\n- Estimates of local conditional probability tables \n\nImportant Concepts\n- Data: labeled instances, e.g. emails marked spam/ham \n\n  Training set \n\n  Held out (dev) set \n\n  Test set\n- Features: attribute-value pairs which characterize each x \n\n- Experimentation cycle \n\n  Learn parameters (e.g. model probabilities) on training set \n\n  (Tune hyperparameters on held-out set) \n\n  Compute accuracy of test set \n\n  Very important: never “peek” at the test set! \n\n- Evaluation \n\n  Accuracy: fraction of instances predicted correctly \n\n- Overfitting and generalization \n\n  Want a classifier which does well on test data \n\n  Overfitting: fitting the training data very closely, but not generalizing well \n\n- **To generalize better: we need to smooth or regularize the estimates** \n\nParameter Estimation\n- Estimating the distribution of a random variable\n- Empirically: use training data (learning!) \n\n  E.g.: for each outcome x, look at the empirical rate of that value: \n\n  $P_{ML}(x) = count(x) / total samples$ \n\n  This is the estimate that maximizes the likelihood of the data \n\n  $L_(x,theta) = \\prod_{i} P_{theta}(x_i)$ \n\n  $theta_{ML} = arg \\max_{theta} \\prod_{i} P_{theta}(X_i)$ \n\nLaplace Smoothing \n\n- Pretend you saw every outcome once more than you actually did \n\n  $P_{LAP}(x) = (c(x) + 1) / (\\sum_{x}[c(x) + 1])$ \n\n  $P_{LAP}(x) = (c(x) + 1) / (N + |X|])$ \n\n- Pretend you saw every outcome k extra times \n\n  $P_{LAP}(x) = (c(x) + k) / (N + k|X|])$ \n\nTuning on Held-out Data \n\n- Parameters: the probabilities P(X|Y), P(Y) \n- Hyperparameters: e.g. the amount / type of smoothing to do, k, α \n\n- Tune hyperparameters on different data \n\n- For each value of the hyperparameters, train and test on the held-out data \n\nPERCEPTRON \n\n- Notational Changes \n\n  $\\sum_{j} w_j x_j = w \\cdot x$ \n\n- With bias term $b$ \n\n  $\\sum_{j} w_j x_j = w \\cdot x + b$ \n\nLearning weights from examples\n- Perceptions can be used for all kinds of classification problems \n\n- Think of the inputs as features representing something we want to classify \n\n- The feature values for inputs are fixed, but we can choose different weight vectors. Depending on the weight vector that we pick, we will get a different classifier \n\nWeight Updates \n- Start with weights = 0 \n\n- For each training instance \n\n  Classify with current weights \n\n  If correct (i.e., y=y*), no change! \n\n  If **WRONG**: adjust the weight vector \n\n- If wrong, adjust the weight vector by **adding or subtracting the feature fector** \n\n  $w = w + y* \\cdot f$\nMulticlass Decision Rule \n\n- If we have multiple classes: \n\n  A weight vector for each class \n\n  Score (activation) of a class y \n\n  $w_y \\cdot f(x)$ \n\n  Prediction highest score wins \n\n  $y = arg \\max_{y} w_y \\cdot f(x)$\nUpdating Weights in Multiclass Perceptron \n\n- Start with all weights = 0 \n\n- Pick up training examples one by one \n\n- Predict with current weights \n\n  $y = arg \\max_{y} w_y \\cdot f(x)$ \n\n- If correct, no change! \n\n- If wrong: lower score of wrong answer, raise score of right answer \n\n  $w_y = w_y - f(x)$ \n\n  $w_{y^*} = w_{y^*} + f(x)$\nProperties of Perceptrons \n- Separability: true if some parameters get the training set perfectly correct \n\n- Convergence: if the training is separable, perceptron will eventually converge (binary case) \n\n- Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability \n\nProblems with Perceptron\n- Noise: if the data isn’t separable, weights might thrash \n\n- Mediocre generalization: finds a “barely” separating solution \n\n- Overtraining: test / held-out accuracy usually rises, then falls \n\nFixing the Perceptron \n\n- MIRA = Margin Infused Relaxed Algorithm \n\n- Choose an update size that fixes the current mistake... ... but, minimizes the change to w \n\n  $w_y = w_y - tau f(x)$ \n\n  $w_{y^*} = w_{y^*} + tau f(x)$\n- Support Vector Machines \n\n  Maximizing the margin: good according to intuition, theory, practice Only support vectors matter; other training examples are ignorable \n\n  Support vector machines (SVMs) find the separator with max margin \n\n  Basically, SVMs are MIRA where you optimize over all examples at once \n\nNon-Linear Separators\n- Kenel trick\n- General idea: the original feature space can always be mapped to some higher-dimensional feature space where the training set is separable \n\nCLASSIFICATION COMPARISON \n\nNaive Bayes \n\n- Builds a model training data \n\n- Gives prediction probabilities \n\n- Strong assumptions about feature independence • One pass through data (counting) \n\nPerceptrons / MIRA \n\n- Makes less assumptions about data \n\n- Mistake-driven learning \n\n- Multiple passes through data (prediction) \n\n- Often more accurate \n\nQuestions \n\nThe Naive Bayes model is “naive” because it assumes that the features are conditionally independent of each other, given the class. \n\n- True \n\nWrite down the form of the joint probability model P(X1,X2,X3,Y) for this data using the Naive Bayes assumption. (Y is the class) \n\n- P(Y)P(X_1|Y)P(X_2|Y)P(X_3|Y) \n\n  In naive bayes, the features are conditionally independent of each other, given the class. \n\nIn the perceptron training algorithm, weights are updated after every training instance. \n\n- False \n\n  Training is error-driven - weights are only updated when the predicted label is incorrect. \n\nConsider a two-dimensional data distribution where points belonging to class A are arranged around the origin in a circle with radius ra, and points belonging to class B are arranged around the origin in a circle with radius rb, where ra<rb \n\n- can separate the two classes if we use feature augmentation. \n\n  If we augment the input with the features x2,y2, and a bias term, the problem becomes linearly separable. Decaying the learning rate will ensure that the weight vector converges, but since the unaugmented data is not linearly separable, this will still fail to separate the classes. Changing the order in which the instances are fed into the perceptron will not allow the perceptron to find a separating boundary. \n\nFor which of the following datasets would a single perceptron be unable to find a separating boundary (assuming we do not add additional features to the data): \n\n- Class A: {(0,0), (1,1)}; Class B: {(0,1), (1,0)} \n\n  The correct answer corresponds to the XOR problem, which is not linearly separable. All other options are linearly separable. \n\nGiven a non-random dataset, the perceptron algorithm guarantees that the weight vector will converge after a finite number of training iterations. \n\n- False \n\n  This is only true if the dataset is linearly separable. If it is not, the weight vector may fluctuate infinitely. The fluctuation can be remedied by techniques such as learning rate decay, but the basic perceptron algorithm is not guaranteed to converge. \n\nThe inference procedure for the perceptron classification algorithm is best summarized as: \n\n- Compute a weighted sum, then apply a threshold. \n\n  First, we compute the dot product of the weight vector and the input vector (that is, a weighted sum of the input features), and then threshold this value to output either true or false. If you picked the \"datum separatus\" option, you should consider transferring to Hogwarts. \n\n\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 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\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 = \"\"\"\n",
        "Classifier Components\n",
        "1. Training Corpus of M observations input/output pairs (x,y) \\n\n",
        "2. A feature representation of the input. For each input observation $x^i$, this will be a vector of features $[x_1,x_2,...,x_n]$ \\n\n",
        "3. A classification function that computes the estimated class $\\hat{y}$ via $p(y|x)$ \\n\n",
        "4. An objective function for learning, usually involving minimizing error on training examples \\n\n",
        "5. An algorithm for optimizing the objective function \\n\n",
        "Logistic Regression\n",
        "- From a training set, a vector of **weights** and a **bias term** \\n\n",
        "  $z = \\sum_{i} w_i x_i + b$ \\n\n",
        "  $z = w \\cdot x + b$ \\n\n",
        "Sigmoid Function\n",
        "- $f(x) = 1 / (1+e^{-x})$ \\n\n",
        "- $P(y=1) = sigmoid(w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$ \\n\n",
        "- $\\hat{y} = 1$ if $P(y=1 | x) > 0.5$ and $0$ otherwise \\n\n",
        "- Reason for having is to avoid step change in classification function \\n\n",
        "Learning in logistic regression\n",
        "- We learn the parameters (weights + bias) via learning. \\n\n",
        "- An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss. \\n\n",
        "- An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function \\n\n",
        "**Loss Functions** \\n\n",
        "- We need to determine for some observation $x$ how close the classifier output $\\hat{y} = sigmoid(w \\cdot x + b)$ is to the correct output $y$, which is 0 or 1 \\n\n",
        "- One example is the mean squared error \\n\n",
        "- We use a loss function that prefers the correct class labels of the training example to be more likely. \\n\n",
        "- Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. \\n\n",
        "- The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss \\n\n",
        "Loss on all training examples \\n\n",
        "$log p(training labels) = log \\prod^{m}_{i=1}p(y^{i}|x^{i})$ \\n\n",
        "$= \\sum^{m}_{i=1} log p(y^i | x^i)$ \\n\n",
        "$= -\\sum^{m}_{i=1} L_{CE}(\\hat{y}^i | y^i)$ \\n\n",
        "Finding good parameters \\n\n",
        "$theta = arg \\min_{theta} (1/m) \\sum^{m}_{i=1} L_{CE}(y^i,x^i,theta)$ \\n\n",
        "Gradient Descent \\n\n",
        "- a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction. \\n\n",
        "Global vs Local Minimums \\n\n",
        "- For logistic regression, this loss function is conveniently convex. \\n\n",
        "- A convex function has just one minimum, so there are no local minima to get stuck in. \\n\n",
        "- **THIS IS WHY THE CROSS-ENTROPY LOSS IS CHOSEN**\n",
        "How much should we update the parameter by? \\n\n",
        "- The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η. \\n\n",
        "- A higher/faster learning rate means that we should move w more on each step. \\n\n",
        "The Gradient \\n\n",
        "- The derivative of this function for one observation vector x for a single weight wj is: \\n\n",
        "  $del L_{CE}(w,b) / del w_j = [s(w \\cdot x + b) - y] x_j$ \\n\n",
        "- The gradient is a very intuitive value: the difference between the true y and our estimate for x, multiplied by the corresponding input value xj \\n\n",
        "Regularization \\n\n",
        "- Overfitting is a problem with many machine learning models. Overfitting results in poor generalization and poor performance on unseen test set. \\n\n",
        "- In logistic regression, if a feature only occurs in one class then it will get a high weight. Sometimes we are just modelling noisy factors that just accidentally correlate with the class. \\n\n",
        "- Regularization is a way to penalize large weights. A regularization term is added to the loss function. \\n\n",
        "- Lasso regression uses L1 regularization \\n\n",
        "- Ridge regression uses L2 regularization \\n\n",
        "Multinomial logistic regression \\n\n",
        "- Instead of binary classification, we often want more than two classes. For sentiment classification we might extend the class labels to be positive, negative, and neutral. \\n\n",
        "- We want to know the probability of y for each class c ∈ C, p(y = c|x). \\n\n",
        "- To get a proper probability, we will use a generalization of the sigmoid function called the softmax function  \\n\n",
        "  $softmax(z_i) = e^{z_j} / (\\sum^{k}_{j=1} e^{z_j})$ for $1 \\leq i \\leq k$ \\n\n",
        "Softmax \\n\n",
        "- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of values normalized into probabilities: \\n\n",
        "  $softmax(z) = [e^{z_1} / (\\sum^{k}_{i=1}e^{z_i}),e^{z_2} / (\\sum^{k}_{i=1}e^{z_i}),...,e^{z_k} / (\\sum^{k}_{i=1}e^{z_i})]$ \\n\n",
        "- For example, for this input: \\n\n",
        "  $z = [0.6, 1.1, -1.5, 1.2, 3.2, -1.1]$ \\n\n",
        "  Softmax $= [0.056, 0.090, 0.007, 0.099, 0.74, 0.010]$ \\n\n",
        "  $z = 3.2$ is chosen \\n\n",
        "Neural Networks \\n\n",
        "Sigmoid smoothness is crucial \\n\n",
        "- Smoothness of σ means that small changes in the weights wj and in the bias b will produce a small change the output from the neuron \\n\n",
        "- Δoutput is a linear function of the changes Δwj and Δb \\n\n",
        "- This makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output \\n\n",
        "Neural Networks Activation Functions \\n\n",
        "- Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z \\n\n",
        "- The output of this function is called the activation value for the unit, represented by the variable a. The output of a neural network is called y, so if the activation of a node is the final output of a network then \\n\n",
        "- $y = a = f(z)$ \\n\n",
        "- There are 3 commonly used non-linear functions used for f: The sigmoid function, The tanh function, The rectified linear unit ReLU \\n \n",
        "Questions \\n\n",
        "Which of the following are true about linear classifiers? Please check all that apply. \\n\n",
        "- When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output. \\n\n",
        "- They can be used for both regression and classification. \\n\n",
        "Which of the following best characterizes the difference between parametric and nonparametric models? \\n\n",
        "- A parametric model has a fixed size on the number of parameters. \\n\n",
        "When performing k-means clustering, each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration. \\n\n",
        "- False \\n\n",
        "  This is only true of agglomerative clustering.  \\n\n",
        "For linearly separable data, there exists only one decision boundary that separates the classes. \\n\n",
        "- False \\n\n",
        "  There could be multiple boundaries, but their performance may vary. \\n\n",
        "Is it possible that the assignment of observations to clusters do not change between successive iterations in K-Means? \\n\n",
        "- Yes \\n\n",
        "  When approaching the converge point, the state may not change. \\n\n",
        "Relative to single-layer perceptrons, neural networks gain their power from \\n\n",
        "- stacking of layers \\n\n",
        "  Multi-layer architecture of neural network provides enough parameters to get better performance on the task.  \\n\n",
        "In neural networks, nonlinear activation functions: Please check all that apply. \\n\n",
        "- Help to learn nonlinear decision boundaries. \\n\n",
        "- Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 249,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7b5411dc-81e0-4080-b4a0-e61146b012f3"
      },
      "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": 250,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \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 Your summary here \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\nClassifier Components\n1. Training Corpus of M observations input/output pairs (x,y) \n\n2. A feature representation of the input. For each input observation $x^i$, this will be a vector of features $[x_1,x_2,...,x_n]$ \n\n3. A classification function that computes the estimated class $\\hat{y}$ via $p(y|x)$ \n\n4. An objective function for learning, usually involving minimizing error on training examples \n\n5. An algorithm for optimizing the objective function \n\nLogistic Regression\n- From a training set, a vector of **weights** and a **bias term** \n\n  $z = \\sum_{i} w_i x_i + b$ \n\n  $z = w \\cdot x + b$ \n\nSigmoid Function\n- $f(x) = 1 / (1+e^{-x})$ \n\n- $P(y=1) = sigmoid(w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$ \n\n- $\\hat{y} = 1$ if $P(y=1 | x) > 0.5$ and $0$ otherwise \n\n- Reason for having is to avoid step change in classification function \n\nLearning in logistic regression\n- We learn the parameters (weights + bias) via learning. \n\n- An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss. \n\n- An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function \n\n**Loss Functions** \n\n- We need to determine for some observation $x$ how close the classifier output $\\hat{y} = sigmoid(w \\cdot x + b)$ is to the correct output $y$, which is 0 or 1 \n\n- One example is the mean squared error \n\n- We use a loss function that prefers the correct class labels of the training example to be more likely. \n\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. \n\n- The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss \n\nLoss on all training examples \n\n$log p(training labels) = log \\prod^{m}_{i=1}p(y^{i}|x^{i})$ \n\n$= \\sum^{m}_{i=1} log p(y^i | x^i)$ \n\n$= -\\sum^{m}_{i=1} L_{CE}(\\hat{y}^i | y^i)$ \n\nFinding good parameters \n\n$theta = arg \\min_{theta} (1/m) \\sum^{m}_{i=1} L_{CE}(y^i,x^i,theta)$ \n\nGradient Descent \n\n- a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction. \n\nGlobal vs Local Minimums \n\n- For logistic regression, this loss function is conveniently convex. \n\n- A convex function has just one minimum, so there are no local minima to get stuck in. \n\n- **THIS IS WHY THE CROSS-ENTROPY LOSS IS CHOSEN**\nHow much should we update the parameter by? \n\n- The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η. \n\n- A higher/faster learning rate means that we should move w more on each step. \n\nThe Gradient \n\n- The derivative of this function for one observation vector x for a single weight wj is: \n\n  $del L_{CE}(w,b) / del w_j = [s(w \\cdot x + b) - y] x_j$ \n\n- The gradient is a very intuitive value: the difference between the true y and our estimate for x, multiplied by the corresponding input value xj \n\nRegularization \n\n- Overfitting is a problem with many machine learning models. Overfitting results in poor generalization and poor performance on unseen test set. \n\n- In logistic regression, if a feature only occurs in one class then it will get a high weight. Sometimes we are just modelling noisy factors that just accidentally correlate with the class. \n\n- Regularization is a way to penalize large weights. A regularization term is added to the loss function. \n\n- Lasso regression uses L1 regularization \n\n- Ridge regression uses L2 regularization \n\nMultinomial logistic regression \n\n- Instead of binary classification, we often want more than two classes. For sentiment classification we might extend the class labels to be positive, negative, and neutral. \n\n- We want to know the probability of y for each class c ∈ C, p(y = c|x). \n\n- To get a proper probability, we will use a generalization of the sigmoid function called the softmax function  \n\n  $softmax(z_i) = e^{z_j} / (\\sum^{k}_{j=1} e^{z_j})$ for $1 \\leq i \\leq k$ \n\nSoftmax \n\n- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of values normalized into probabilities: \n\n  $softmax(z) = [e^{z_1} / (\\sum^{k}_{i=1}e^{z_i}),e^{z_2} / (\\sum^{k}_{i=1}e^{z_i}),...,e^{z_k} / (\\sum^{k}_{i=1}e^{z_i})]$ \n\n- For example, for this input: \n\n  $z = [0.6, 1.1, -1.5, 1.2, 3.2, -1.1]$ \n\n  Softmax $= [0.056, 0.090, 0.007, 0.099, 0.74, 0.010]$ \n\n  $z = 3.2$ is chosen \n\nNeural Networks \n\nSigmoid smoothness is crucial \n\n- Smoothness of σ means that small changes in the weights wj and in the bias b will produce a small change the output from the neuron \n\n- Δoutput is a linear function of the changes Δwj and Δb \n\n- This makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output \n\nNeural Networks Activation Functions \n\n- Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z \n\n- The output of this function is called the activation value for the unit, represented by the variable a. The output of a neural network is called y, so if the activation of a node is the final output of a network then \n\n- $y = a = f(z)$ \n\n- There are 3 commonly used non-linear functions used for f: The sigmoid function, The tanh function, The rectified linear unit ReLU \n \nQuestions \n\nWhich of the following are true about linear classifiers? Please check all that apply. \n\n- When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output. \n\n- They can be used for both regression and classification. \n\nWhich of the following best characterizes the difference between parametric and nonparametric models? \n\n- A parametric model has a fixed size on the number of parameters. \n\nWhen performing k-means clustering, each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration. \n\n- False \n\n  This is only true of agglomerative clustering.  \n\nFor linearly separable data, there exists only one decision boundary that separates the classes. \n\n- False \n\n  There could be multiple boundaries, but their performance may vary. \n\nIs it possible that the assignment of observations to clusters do not change between successive iterations in K-Means? \n\n- Yes \n\n  When approaching the converge point, the state may not change. \n\nRelative to single-layer perceptrons, neural networks gain their power from \n\n- stacking of layers \n\n  Multi-layer architecture of neural network provides enough parameters to get better performance on the task.  \n\nIn neural networks, nonlinear activation functions: Please check all that apply. \n\n- Help to learn nonlinear decision boundaries. \n\n- Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable. \n\n\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 = \"\"\"\n",
        "Questions \\n\n",
        "Which of the following is not a common benefit of using log probabilities instead of probabilities with a Categorical distribution? \\n\n",
        "- A log probability representation of a categorical distribution is more efficient to sample. \\n\n",
        "Markov models are stationary because probabilities assigned to a sequence are invariant with respect to shifts in data [train, validation, test, etc.] \\n\n",
        "- False \\n\n",
        "  The stationary distribution of a Markov chain describes the distribution of Xt after a sufficiently long time that the distribution of Xt does not change any longer. \\n\n",
        "Cross Entropy: \\n\n",
        "- is an upper bound on the entropy. The more accurate a model is, the lower the cross entropy. \\n\n",
        "  Definition of cross-entropy \\n\n",
        "Vector representations of words using term-document matrices and word-word matrices can account for polysemy. \\n\n",
        "- False \\n\n",
        "  This vector representation could only compare words that have similar meaning, but it cannot handle the problem that single word has multiple meanings (polysemy). \\n\n",
        "How many tokens would the following sentence be broken into: \\n\n",
        "- 24 \\n\n",
        "Suppose you are building an n-gram model for a corpus with a vocabulary of size V and a total of T tokens. The running time to build this model depends on \\n\n",
        "- n and T \\n\n",
        "What is the purpose of Laplace smoothing? \\n\n",
        "- to account for unseen words. \\n\n",
        "  Without smoothing, the probabilities of these unseen words will be zero. \\n\n",
        "When generating random text, given some context C, an n-gram model cannot generate a next token T if the model never saw the context-token pair (C, T) during training. \\n\n",
        "- True \\n\n",
        "  N-gram models used for generation draw the next word at random (proportional to their conditional probability tables). If a word doesn't occur with the context in training, then it isn't included in its conditional probability table and therefore won't be generated. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 251,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c56953e9-474d-44ef-e6b0-398c20a768cb"
      },
      "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": 252,
      "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\nClassifier Components\n1. Training Corpus of M observations input/output pairs (x,y) \n\n2. A feature representation of the input. For each input observation $x^i$, this will be a vector of features $[x_1,x_2,...,x_n]$ \n\n3. A classification function that computes the estimated class $\\hat{y}$ via $p(y|x)$ \n\n4. An objective function for learning, usually involving minimizing error on training examples \n\n5. An algorithm for optimizing the objective function \n\nLogistic Regression\n- From a training set, a vector of **weights** and a **bias term** \n\n  $z = \\sum_{i} w_i x_i + b$ \n\n  $z = w \\cdot x + b$ \n\nSigmoid Function\n- $f(x) = 1 / (1+e^{-x})$ \n\n- $P(y=1) = sigmoid(w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$ \n\n- $\\hat{y} = 1$ if $P(y=1 | x) > 0.5$ and $0$ otherwise \n\n- Reason for having is to avoid step change in classification function \n\nLearning in logistic regression\n- We learn the parameters (weights + bias) via learning. \n\n- An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss. \n\n- An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function \n\n**Loss Functions** \n\n- We need to determine for some observation $x$ how close the classifier output $\\hat{y} = sigmoid(w \\cdot x + b)$ is to the correct output $y$, which is 0 or 1 \n\n- One example is the mean squared error \n\n- We use a loss function that prefers the correct class labels of the training example to be more likely. \n\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. \n\n- The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss \n\nLoss on all training examples \n\n$log p(training labels) = log \\prod^{m}_{i=1}p(y^{i}|x^{i})$ \n\n$= \\sum^{m}_{i=1} log p(y^i | x^i)$ \n\n$= -\\sum^{m}_{i=1} L_{CE}(\\hat{y}^i | y^i)$ \n\nFinding good parameters \n\n$theta = arg \\min_{theta} (1/m) \\sum^{m}_{i=1} L_{CE}(y^i,x^i,theta)$ \n\nGradient Descent \n\n- a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction. \n\nGlobal vs Local Minimums \n\n- For logistic regression, this loss function is conveniently convex. \n\n- A convex function has just one minimum, so there are no local minima to get stuck in. \n\n- **THIS IS WHY THE CROSS-ENTROPY LOSS IS CHOSEN**\nHow much should we update the parameter by? \n\n- The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η. \n\n- A higher/faster learning rate means that we should move w more on each step. \n\nThe Gradient \n\n- The derivative of this function for one observation vector x for a single weight wj is: \n\n  $del L_{CE}(w,b) / del w_j = [s(w \\cdot x + b) - y] x_j$ \n\n- The gradient is a very intuitive value: the difference between the true y and our estimate for x, multiplied by the corresponding input value xj \n\nRegularization \n\n- Overfitting is a problem with many machine learning models. Overfitting results in poor generalization and poor performance on unseen test set. \n\n- In logistic regression, if a feature only occurs in one class then it will get a high weight. Sometimes we are just modelling noisy factors that just accidentally correlate with the class. \n\n- Regularization is a way to penalize large weights. A regularization term is added to the loss function. \n\n- Lasso regression uses L1 regularization \n\n- Ridge regression uses L2 regularization \n\nMultinomial logistic regression \n\n- Instead of binary classification, we often want more than two classes. For sentiment classification we might extend the class labels to be positive, negative, and neutral. \n\n- We want to know the probability of y for each class c ∈ C, p(y = c|x). \n\n- To get a proper probability, we will use a generalization of the sigmoid function called the softmax function  \n\n  $softmax(z_i) = e^{z_j} / (\\sum^{k}_{j=1} e^{z_j})$ for $1 \\leq i \\leq k$ \n\nSoftmax \n\n- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of values normalized into probabilities: \n\n  $softmax(z) = [e^{z_1} / (\\sum^{k}_{i=1}e^{z_i}),e^{z_2} / (\\sum^{k}_{i=1}e^{z_i}),...,e^{z_k} / (\\sum^{k}_{i=1}e^{z_i})]$ \n\n- For example, for this input: \n\n  $z = [0.6, 1.1, -1.5, 1.2, 3.2, -1.1]$ \n\n  Softmax $= [0.056, 0.090, 0.007, 0.099, 0.74, 0.010]$ \n\n  $z = 3.2$ is chosen \n\nNeural Networks \n\nSigmoid smoothness is crucial \n\n- Smoothness of σ means that small changes in the weights wj and in the bias b will produce a small change the output from the neuron \n\n- Δoutput is a linear function of the changes Δwj and Δb \n\n- This makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output \n\nNeural Networks Activation Functions \n\n- Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z \n\n- The output of this function is called the activation value for the unit, represented by the variable a. The output of a neural network is called y, so if the activation of a node is the final output of a network then \n\n- $y = a = f(z)$ \n\n- There are 3 commonly used non-linear functions used for f: The sigmoid function, The tanh function, The rectified linear unit ReLU \n \nQuestions \n\nWhich of the following are true about linear classifiers? Please check all that apply. \n\n- When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output. \n\n- They can be used for both regression and classification. \n\nWhich of the following best characterizes the difference between parametric and nonparametric models? \n\n- A parametric model has a fixed size on the number of parameters. \n\nWhen performing k-means clustering, each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration. \n\n- False \n\n  This is only true of agglomerative clustering.  \n\nFor linearly separable data, there exists only one decision boundary that separates the classes. \n\n- False \n\n  There could be multiple boundaries, but their performance may vary. \n\nIs it possible that the assignment of observations to clusters do not change between successive iterations in K-Means? \n\n- Yes \n\n  When approaching the converge point, the state may not change. \n\nRelative to single-layer perceptrons, neural networks gain their power from \n\n- stacking of layers \n\n  Multi-layer architecture of neural network provides enough parameters to get better performance on the task.  \n\nIn neural networks, nonlinear activation functions: Please check all that apply. \n\n- Help to learn nonlinear decision boundaries. \n\n- Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable. \n\n\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": "93b08754-623c-43c2-cf3d-a17ea89c5f2c"
      },
      "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": 253,
      "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 Chapter 16.1 summary.  $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 Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n \nMARKOV DECISION PROCESS (\"MDP\") has the following components: \n\n- set of states $s \\in S$ \n\n- set of actions $a \\in A$ \n\n- a transition function $T(s,a,s')$, the probability that executing action $a$ in $s$ will lead to $s'$: $P(s' | s, a)$ \n\n- a reward function $R(s,a,s')$\n\n- an initial state $s_0$\n\n- **Optionally**, one or more terminal states \n\nSOLUTION = POLICY: \n\nIn search problems, a solution was a sequence of actions. Because of the non-determinism in MDPs, solution to an MDP is a **policy** \n\n- Policy $\\pi(s) = a$ and $\\pi^*(s)$ denotes the **optimal policy**\n \nEven though the policy told me to go right here, there’s no guarantee that me picking the action Right will result in me moving right. It’s stochastic! Even if the **same policy** is executed multiple times by the agent, this may lead to different sequence of states and actions (**environment history**), and thus a **different score** under the reward function. \n\nTherefore we need to compute the **expected utility** of all the possible paths generated by a policy. \n\nSEQUENCES OF REWARDS \n\n- Finite horizons: Fixed time (**N** actions) after which the game ends and the agent gets no additional score. Policies that depend on time are called\n**nonstationary**. \n\n- Infinite horizons: With no fixed time limit, there is no reason to behave differently in the same state at different times. The optimal policy is **stationary**. \n\nOPTIMAL QUANTITIES \n\n- The value (utility) of a state s: $V*(s) =$ expected utility starting in s and acting optimally $= \\max_{a} Q*(s,a)$ \n\n- The value (utility) of a q-state (s,a): $Q*(s,a) = $ expected utility starting out having taken action a from state s and (thereafter) acting optimally $= \\sum_{s'} T(s, a, s')[R(s,a,s') + \\gamma V*(s')]$\n\n- Combining the two is the **BELLMAN EQUATION**: $V^*(s) = \\max_{a} \\sum_{s'} T(s, a, s') [R(s,a,s') + \\gamma V^*(s')]$ \n\nTIME-LIMITED VALUES: \n- Key idea: time-limited values. Define $V_{k}(s)$ to be the optimal value of $s$ if the game ends in $k$ more time steps. \n\n**VALUE ITERATION**\n- Start with $V_{0} = 0$: no time steps left means an expected reward sum of 0 \n- Given vector of $V_{k}(s)$ values, do one ply of expectimax from each state: $V_{k+1} \\leftarrow \\max_{a} \\sum_{s'} T(s,a,s')[R(s,a,s') + \\gamma V_{k}(s')]$\n \n- Repeat until convergence\n- Complexity of each iteration: $O(S^2A)$ \n**POLICY EVALUATION** \n- Do what $\\pi$ says to do. Then the tree would be simpler - only one action per state\n- Compute the utility of a state $s$ under a fixed (generally non-optimal) policy\n- $V_{\\pi}(s)=$ expected total discounted rewards starting in $s$ and following $\\pi$ \n- $V_{\\pi}(s) = \\sum_{s'}T(s, \\pi(s),s')[R(s,\\pi(s),s') + \\gamma V_{\\pi}(s')]$\n- Efficiency: $O(S^2)$ per iteration\n- How do we calculate the V's for a fixed policy $\\pi$? Idea 1: turn recursive Bellman equations into updates. **Idea 2**: Bellman equations are just a linear system. Solve with Matlab \n**COMPUTING ACTIONS FROM Q-VALUES**\n- Completely trivial: $\\pi^*(s) = arg \\max_{a} Q^*(s,a)$. Actions are easier to select from Q-values than values. \nProbmes with Value Iteration\n1. It's slow - $O(S^2A)$ per iteration\n2. The max at each state rarely changes\n3. The policy often converges long before the values\n- Policy iteration is much faster - using the one-step look-ahead: \n\n  $\\pi_{i+1}(s) = arg \\max_{a} \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V^{\\pi_{i}}(s')]$ \n\nComparison\n- Both value iteration and policy iteration compute the same thing (all optimal values)\n- In **value iteration**, every iteration updates both the values and (implicity) the policy\n- We do not track the policy, but taking the max over actions implicitly recomputes it\n- In **policy iteration**, we do several passes that update utilities with fixed policy (each pass is fast 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 pass)\n- The new policy will be better (or we are done)\n- Both are dynamic programs for solving MDPs\n- You want to:\n  Compute optimal values: use value iteration or policy iteration \n\n  Compute values for a particular policy: use policy evaluation \n\n  Turn your values into a policy: use policy extraction (one-step look-ahead)\nMaximum Expected Utility\n- For average-case expectimax reasoning, we need **magnitudes** to be meaningful (recall the $x^2$ example)\nRational Preferences\n- Orderability: $(A \\succ B) \\lor (B \\succ A) \\lor (A \\sim B)$\n- Transitivity: $(A \\succ B) \\land (B \\succ C) \\Rightarrow (A \\succ C)$\n- Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p, A: 1-p, C] \\sim B$\n- Substitutability: $A \\sim B \\Rightarrow [p, A; 1-p,C] \\sim [p,B; 1-p, C] $\n- Monotonicity: $A \\succ B \\Rightarrow (p \\geq q \\Leftrightarrow [p,A;1-p,B] \\succcurlyeq [q,A; 1-q,B])$\nQuestions \n\nWhich of the following statements is true of a Markov decision process or MDP? \n\n- A solution or policy must specify what the agent should do for all states that it can reach. \n\n  Discounted reward is not absolutely necessary, proper policy might not always exist - see for example Figure 17.2 bottom right. \n\n- An MDP is defined for a fully observable, stochastic environment. \n\n  Discounted reward is not absolutely necessary, proper policy might not always exist - see for example Figure 17.2 bottom right. \n\nSelect all the following components that the policy iteration algorithm equation takes into account. \n\n- The probability of entering a state S’ from state S after performing action A \n\n  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration. \n\n- All of the actions A that an agent can take. \n\n  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration.  \n\n- The utility associated with a state S. \n\n  Max reward that can be obtained after being in state S is used in value iteration, not policy iteration.  \n\nPolicy is implicitly updated in value iteration. \n\n- True \n\n  Policy corresponds to the action paired with the max Q-value. \n\nCompared to value iteration, policy iteration often converges in fewer iterations but is more costly (i.e. greater time complexity) per iteration. \n\n- True \n\n  Policy iteration converges in fewer iterations, but takes O(|S|^3) per iteration, whereas value iteration takes O(|A|*|S|^2). \n\nThe utility function estimate must be completely accurate in order to get an optimal policy.? \n\n- False \n\n  The utility is a human defined function to evaluate the state and thus it cannot be completely correct. But it could still obtain an optimal policy as long as it describes the state properly. \n\nPolicy is explicitly updated in value iteration. \n\n- False \n\n  Policy is implicitly updated in value iteration, see textbook section 17.2. \n\nWhat is the principle of MEU? \n\n- An agent should maximize the weighted average of their utilities.\n  \n\n\n## Module 8 Definitions\n* **Utility function** - Maps from outcome (states of the world) to real numbers that describe an agen's preferences\n* **Expected utility** - your definition here\n* **Principle of maximum expected utility** - A rational agent should choose the action that **maximizes its expected utility, given its knowledge**\n* **Meu principle** - Given any preferences satisfying these constraints, there exists a real-valued function U such that $U(A) \\geq U(B) \\Leftrightarrow A \\succurlyeq B$\n* **Etc.** - your definition here\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 Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\nReinforcement Learning Important Ideas:\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\nBasic idea:\n- Receive feedback in the form of **rewards**\n- Agent's utility is defined by the reward function\n- Must (learn to) act so as to **maximize expected rewards**\n- All learning is based on observed sampels of outcomes \n\nMDP vs Reinforcement Learning\nIn MDP: \n\n- A set of states $s \\in S$\n- A set of actions (per state) A \n- A model $T(s,a,s')$\n- A reward function $R(s,a,s')$\n- Looking for a policy $\\pi(s)$ \n\nReinforcement learning: do not know T or R \n\n- We do not know which states are good or what the actions do \n\n- Must actually try actions and states out to learn \n\nModel-Based Learning (Try to learn the probability, i.e. the Model)\n- Learn an approximate modle based on experiences \n\n- Solve for values as if the learned model were correct \n\n- Step 1: Learn empirical MDP model \n\n  Count outcomes $s'$ for each $s, a$ \n\n  Normalize to give an estimate of $\\hat{T}(s,a,s')$ \n\n  Discover each $\\hat{R}(s,a,s')$ where we experience $(s,a,s')$ \n\n- Step 2: Solve the learned MDP, for example, by using value iteration \n\n  Train and test \n\nModel-Free Learning \n- Input: a fixed policy $\\pi(s)$\n- Do not know the transitions $T(s,a,s')$\n- Do not know the rewards $R(s,a,s')$\n- Goal is to learn the state values\n- Learner is along for the ride. No choice about what actions to take. Just excute the policy and learn from experience \n\nDirect Evaluation\n- Compute values for each state under $\\pi$ \n- Act according to $\\pi$ \n- Every time you visit a state, write what the sum of discounted rewards turned out to be\n- Average those samples \n\n- Good about Direct Evaluation: easy to understand, does not require knowledge of T and R. Eventually compultes the correct average values\n- Problems with Direct Evaluation: wastes information about state connections, each state must be learned separately, takes long time \n\nWhy not use Policy Evaluation?\n- Simplified Bellman updates calculate $V$ for a fixed policy\n- Key problem: we cannot update $V$ without knowing $T$ and $R$\nOne Step further: Sample-Based Policy Evaluation\n- We want to improve our estimate of $V$ by computing these averages: \n\n  $V^{\\pi}_{k+1} \\leftarrow \\sum_{s'}T(s,\\pi(s),s')[R(s,\\pi(s),s')+\\gamma V^{\\pi}_{k}(s')]$\n- Idea: take samples of outcomes $s'$ by doing the action and average: \n\n  sample1 $= R(s,\\pi(s),s'_{1} + \\gamma V^{\\pi}_{k}(s'_1))$ \n\n  sample2 $= R(s,\\pi(s),s'_{2} + \\gamma V^{\\pi}_{k}(s'_2))$ \n\n  sampleN $= R(s,\\pi(s),s'_{n} + \\gamma V^{\\pi}_{k}(s'_n))$ \n\n  $V^{\\pi}_{k+1} \\leftarrow (1/n) \\sum_{i} sample_i$ \n\n**TEMPORAL DIFFERENCE LEARNING**\n- Big idea: learn from every experience. Update $V(s)$ each time we experience a transition $(s,a,s',r)$ \n\n- Likely outcomes $s'$ will contribute updates more often \n\n- Policy still fixed, still doing evaluation. Move values toward value of whatever successor occurs: running average. \n\n  Sample of $V(s)$: sample $= R(s,\\pi(s),s') + \\gamma V^{\\pi}(s')$ \n\n  Update to $V(s)$: $V^{\\pi}(s) \\leftarrow (1-a)V^{\\pi}(s) + (a)$ sample \n\n  Same update: $V(s)$: $V^{\\pi}(s) \\leftarrow V^{\\pi}(s) + (a)$ $($ sample $-V^{\\pi}(s))$ \n\nExponential Moving Average\n- Exponential moving average is the running interpolation update: $x_n = (1-a) \\cdot x_{n-1} + a \\cdot x_n $ \n\n- Makes recent samples more important \n\n- Decreasing learning rate (alpha) can give converging averages \n\nProblems with Temporal Value Learning \n- TD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages\n- However, if we want to turn values into a (new) policy, we are sunk: \n\n  $\\pi(s) = arg \\max_{a} Q(s,a)$ \n\n  $Q(s,a) = \\sum_{s'} T(s,a,s') [R(s,a,s') + \\gamma V(s')]$\n\n  Still need the $T$ here. \n\n  Idea: learn Q-values, not values \n\n  Make action selection model-free too! \n\n**ACTIVE REINFORCEMENT LEARNING**\n- Full reinforcement learning: optimal policies \n- You do not know the transitions $T$ \n\n- You do not know the rewards $R$ \n\n- You choose the actions now \n\n- Goal: learn the optimal policy and values \n\n- In this case, learner makes choices. Fundamental tradeoff: exploration vs exploitation \n\n- This is NOT offline planning. You actually take actions in the world and find out what happens \n\n- Learn $Q(s,a)$ value as you go \n\n  Receive a sample $(s,a,s',r) \n\n  Consider your old estimate $Q(s,a)$ \n\n  Consider your new sample estimate: \n\n  $ sample = R(s,a,s') + \\gamma \\max_{a'} Q(s',a')$ \n\n- Formula: \n\n  $Q(s,a) \\leftarrow (1-a) Q(s,a) + (a)[sample]$ \n\n**Q-LEARNING PROPERTIES**\n- Amazing result: Q-learning converges to optimal policy, even if you're acting suboptimally\n- This is called off-policy learning \n- Caveats: \n\n  You have to explore enough \n\n  You have to eventually make the learning rate small enough \n\n  ... but not decrease it too quickly \n\n  Basically, in the limit, it does not matter how you select actions \n\nExploration vs Exploitation \nSchemes for forcing exploration\n- Random action ($\\epsilon$-greedy) \n\n- Problem with random actions:\n  You do eventually explore the space, but keep thrashing around once learning is done \n\n  One solution: lower $\\epsilon$ over time\n- Exploration function: takes a value estimate $u$ and a visit count $n$, and returns an optimistic utility: \n\n  $f(u,n) = u + k/n $ /n\n  Regular Q-update: $Q(s,a) \\leftarrow a R(s,a,s') + \\gamma \\max_{a'} Q(s',a')$ \n\n  Modified Q-update: $Q(s,a) \\leftarrow a R(s,a,s') + \\gamma \\max_{a'}f(Q(s',a'), N(s',a'))$ \n\nRegret\n- Even if you learn the optimal policy, you still make mistakes along the way! \n\n- Regret is a measure of your total mistake cost: the difference between your (expected) rewards, including youthful suboptimality, and optimal (expected) rewards \n\n- Minimizing regret goes beyond learning to be optimal – it requires optimally learning to be optimal \n\n- Example: random exploration and exploration functions both end up optimal, but random exploration has higher regret \n\nApproximate Q-Learning\n- Sliding scale\n- Adjust weights\n- There is no guarantee that it will always find the optimal policy. \n\nQuestions \n\nWhich of the following is given to the agent when using passive reinforcement learning? Check all that apply. \n\n- All of the states that can be reached by the agent. \n\n  The goal of passive reinforcement learning is to compute values for each state under policy π, the transition and reward are not required for direction evaluation. \n\n- The agent’s policy π. \n\n  The goal of passive reinforcement learning is to compute values for each state under policy π, the transition and reward are not required for direction evaluation. \n\nDirect utility estimation computes a Utility function U by considering the connection between the utility of a state and the utility of its successor states. \n\n- False \n\n  Direct utility estimation only use the sample transitions. \n\nWhich of the following is true of both adaptive dynamic programming (ADP) learning and temporal-difference (TD) learning? \n\n- The utility of a state is adjusted locally to agree with the utility of at least one successor state. \n\n  The utility of a state is adjusted locally to agree with the utility of at least one successor state. \n\nWhich of the following equations are updates for TD Q-learning?  Check all that apply. \n\n- Q(s,a)←Q(s,a)+α(R(s)+γmaxa′Q(s′,a′)−Q(s,a)) \n\nWhat is this equation $$U(s)=R(s)+\\gamma \\max _{a} \\sum_{s^{\\prime}} P\\left(s^{\\prime} \\mid s, a\right) U\\left(s^{\\prime}\right)$$ ? \n\n- The Bellman equation \n\nQ-learning with linear function approximation (weighted linear function of a set of features) will always converge to the optimal policy. \n\n- False \n\n  It is possible for Q learning with linear function approximation to converge to the optimal policy, but there is no guarantee that it always finds such an optimal policy. For example, consider the problem where the true Q-function is a quadratic function. Q(s, a) where a= 0 or 1 and s can be any real number and the true function is Q(s,0) = s^2 and Q(s,1) = 3s^4 for all s. Then if our function approximator is linear Q(s,a) = k*s + l*a + b, then there exists no k,l, and b that can represent the true Q function because we are trying to fit a linear to a quadratic function. \n\nIn reinforcement learning, a deterministic policy is \n\n- A mapping from states to actions \n\n\n\n## Module 9 Definitions\n* **Deterministic policy** - A mapping from states to actions\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \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 Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nUncertainty\n- Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms) \n\n- Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present) \n\n- Model: Agent knows something about how the known variables relate to the unknown variables \n\nWhat Probabilities are about?\nLike logical assertions, probabilities are about possible worlds. Instead of strictly ruling out possibilities (where a logical assertion is false), probabilities quantify how likely a particular possible world is. \n\nIn probability theory, the possible worlds are called the sample space, and they mutually exclusive and exhaustive. \n\nA fully specified probability model associates a probability P(𝑤) with each possible world 𝑤 \n\nAxioms of Probability\n- The probability of any possible world is between 0 and 1\n- The total probability of the set of all possible world is 1 \n\nProbabilistic Models: \n- (Random) variables with domains\n- Assignments are called outcomes\n- Joint distributions: say whether assignments (outcomes) are likely\n- Normalized: sum to 1.0\n- Ideally: only certain variables directly interact \n\nMarginal Distributions\n- Marginal distributions are sub-tables which eliminate variables\n- Marginalization (summing out): Combine collapsed rows by adding \n\n  $P(t) = \\sum_{s}P(t,s)$ \n\n  $P(s) = \\sum_{t}P(t,s)$ \n\n- Takes $d^n$ to fully map out these tables \nConditional Probabilities\n- A simple relation between joint and conditional probabilities \n\n  $P(a|b) = P(a,b)/P(b)$ \n\nProbabilistic Inference \n- Probabilistic inference: compute a desired probability from other known probabilities (e.g. conditional from joint) \n\nInference by Enumeration \n- General Cases \n\n  Evidence variables: $E_1, ..., E_k = e_1, ... e_k$ \n\n  Query variable: $Q$ \n\n  Hidden variables: $H_1,..., H_r$ \n\n- Step 1: Select the entries consistent with the evidence \n\n  Step 2: Sum out H to get joint of Query and Evidence \n\n  $P(Q,e_1,...,e_k) = \\sum_{h_1,...,h_k} P(Q,h_1,...,h_k,e_1,...,e_k)$ \n\n  Step 3: Normalize \n\n  $1/Z$ \n\n  $Z = \\sum_{q}P(Q,e_1,...,e_k)$\n\n  $P(Q|e_1,...,e_k) = (1/Z)P(Q,e_1,...,e_k)$ \n\nProduct Rule \n\n$P(y)P(x|y) = P(x,y)$ \n\nChain Rule \n\n$P(x_1,x_2,...,x_n) = \\prod_{i}P(x_i | x_1,...,x_{i-1})$ \n\nBayes's Rule \n\n$P(x,y) = P(x|y)P(y) = P(y|x)P(x)$ \n\nProbabilistic Language Modeling\n- Goal: compute the probability of a sentence or sequence of words \n\n  P(W) = P(w1,w2,w3,w4,w5...wn) \n\n- Related task: probability of an upcoming word \n\n  P(w5|w1,w2,w3,w4) \n\n- A model that computes either of these \n\n  P(W) or P(wn|w1,w2...wn-1) is called a language model \n\n- **Uses the Chain Rule** \n\nN-Gram Models\n- In general this is an insufficient model of language because language has long-distance dependencies \n\nQuestions \n\nWhich of the following must be true of the probabilities of two events, A and B, if A is independent of B? \n\n- P(A | B) = P(A) \n\n- P(B | A) = P(B) \n\n- P(A ∨ B) = P(A) + P(B) - P(A ∧ B) \n\n- P(A ∧ B) = P(A) P(B) \n\nWhich of the following are equivalent to the joint probability P(X1,X2,X3,X4)? Check all that apply. \n\n- P(X2,X1)P(X3|X2,X1)P(X4|X3,X2,X1) \n\n- P(X1|X2,X3,X4)P(X4)P(X3|X4)P(X2|X3,X4) \n \n- P(X1)P(X2|X1)P(X3|X2,X1)P(X4|X3,X2,X1) \n\nIn a bigram model, one assumes that words w{i} and w{i - 2} are independent for i > 2. \n\n- True \n\n  Bigram model only considers the w{i - 1}. \n\nWhen we compute a tri-gram, we normalize the following to add up to 1: \n\n- the probabilities of all words w given w{i - 1}, w{i - 2} \n\n  Trigram model considers the previous two words. \n\nHow can we estimate the probability of a sentence P(w1, w2, …, wN)?  \n\n- By applying the chain rule. \n\nWhat is the effect of the Markov assumption in n-gram language models? \n\n- It makes it possible to estimate the probabilities from data. \n\n  N-gram could learn the conditional probability from the document. \n\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\nConditional Independence\n- X and Y are **independent** if: \n\n  For all $x, y$, $P(x,y) = P(x)P(y)$ \n\n- X and Y are **conditionally independent** given Z \n\n  For all $x, y, z$, $P(x,y|z) = P(x|y)P(y|z)$ \n\n- Unconditional (absolute) independence very rare, and it doesn’t help us make inferences about other variables. \n\n- Conditional independence is our most basic and robust form of knowledge about uncertain environments. \n\n- X is conditionally independent of Y given Z, if and only if: \n\n  For all $x, y, z$, $P(x,y|z) = P(x|z)P(y|z)$ \n\n  or equivalently, if and only if: \n\n  For all $x, y, z$, $P(x|z,y) = P(x|z)$ (Knowing y does not matter...) \n\nBayes Nets Assumptions \n\n$P(x_i | x_1,...,x_{i-1}) = P(x_i | parents(X_i))$ \n\n$P(x,y,z) = P(x)P(y|x)P(z|y)$ \n\nD-separation \n\n- Study independence properties for triples \n\n- Analyze complex cases in terms of member triples \n\nReachability \n\n- if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent \n\n- **Almost works, but not quite** \n\n**ACTIVE / INACTIVE PATHS** \n\nQuestion: Are X and Y conditionally independent given evidence variables {Z}? \n\n- Yes, if X and Y “d-separated” by Z \n\n- Consider all (undirected) paths from X to Y \n\n- No active paths = independence! \n\nA path is active if each triple is active: \n\n- Causal chain A → B → C where B is unobserved (either direction) \n\n- Common cause A ← B → C where B is unobserved \n\n- Common effect (aka v-structure) \n\n  A → B ← C where B or one of its descendants is observed \n\n- **All it takes to block a path is a single inactive segment** \n\nQuestions \n\nThe conditional probability distribution of a variable in a Bayesian network should be specified based on the probability distributions of all of the other variables (nodes). \n\n- False \n\n  Based on its ancestors(parents), see textbook 14.1 \n\nEvery variable in a Bayes net is independent of all of its descendants given its children. \n\n- False \n\n  It is independent given its parent. \n\nWhich of the following is true of locally structured (sparse) systems? Select all that apply. \n\n- The structure grows linearly in complexity (rather than exponentially). \n\n  Textbook section 14.2, definition of locally structured (sparse) systems. \n\nMore than one Bayesian network can be used to represent the same joint distribution. \n\n- True \n\nIf two variables (nodes) X and Y in a Bayesian network do not share a path, which of the following must be true? \n\n- X and Y are conditionally independent. \n\n\n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## 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 Your summary here \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\nNaive Bayes \n\n- Assume all features are independent effects of the label \n\n  $P(Y | F_{0,0},...,F_{15,15})$ proportional to $P(Y) \\prod_{i,j}P(F_{i,j} |Y)$ \n\nGeneral Naive Bayes \n\n- $P(Y,F_1,...,F_n) = P(Y) \\prod_{i}P(F_i|Y)$ \n\n  |Y| x |F| to the n values -> n x |F| x |Y| parameters \n\n- We only have to specify how each feature depends on the class \n\n- Total number of parameters is linear in number of features \n\n- Model is very simplistic, but often works anyway \n\nWhat do we need in order to use Naive Bayes? \n- Inference method (we just saw this part) \n\n- Estimates of local conditional probability tables \n\nImportant Concepts\n- Data: labeled instances, e.g. emails marked spam/ham \n\n  Training set \n\n  Held out (dev) set \n\n  Test set\n- Features: attribute-value pairs which characterize each x \n\n- Experimentation cycle \n\n  Learn parameters (e.g. model probabilities) on training set \n\n  (Tune hyperparameters on held-out set) \n\n  Compute accuracy of test set \n\n  Very important: never “peek” at the test set! \n\n- Evaluation \n\n  Accuracy: fraction of instances predicted correctly \n\n- Overfitting and generalization \n\n  Want a classifier which does well on test data \n\n  Overfitting: fitting the training data very closely, but not generalizing well \n\n- **To generalize better: we need to smooth or regularize the estimates** \n\nParameter Estimation\n- Estimating the distribution of a random variable\n- Empirically: use training data (learning!) \n\n  E.g.: for each outcome x, look at the empirical rate of that value: \n\n  $P_{ML}(x) = count(x) / total samples$ \n\n  This is the estimate that maximizes the likelihood of the data \n\n  $L_(x,theta) = \\prod_{i} P_{theta}(x_i)$ \n\n  $theta_{ML} = arg \\max_{theta} \\prod_{i} P_{theta}(X_i)$ \n\nLaplace Smoothing \n\n- Pretend you saw every outcome once more than you actually did \n\n  $P_{LAP}(x) = (c(x) + 1) / (\\sum_{x}[c(x) + 1])$ \n\n  $P_{LAP}(x) = (c(x) + 1) / (N + |X|])$ \n\n- Pretend you saw every outcome k extra times \n\n  $P_{LAP}(x) = (c(x) + k) / (N + k|X|])$ \n\nTuning on Held-out Data \n\n- Parameters: the probabilities P(X|Y), P(Y) \n- Hyperparameters: e.g. the amount / type of smoothing to do, k, α \n\n- Tune hyperparameters on different data \n\n- For each value of the hyperparameters, train and test on the held-out data \n\nPERCEPTRON \n\n- Notational Changes \n\n  $\\sum_{j} w_j x_j = w \\cdot x$ \n\n- With bias term $b$ \n\n  $\\sum_{j} w_j x_j = w \\cdot x + b$ \n\nLearning weights from examples\n- Perceptions can be used for all kinds of classification problems \n\n- Think of the inputs as features representing something we want to classify \n\n- The feature values for inputs are fixed, but we can choose different weight vectors. Depending on the weight vector that we pick, we will get a different classifier \n\nWeight Updates \n- Start with weights = 0 \n\n- For each training instance \n\n  Classify with current weights \n\n  If correct (i.e., y=y*), no change! \n\n  If **WRONG**: adjust the weight vector \n\n- If wrong, adjust the weight vector by **adding or subtracting the feature fector** \n\n  $w = w + y* \\cdot f$\nMulticlass Decision Rule \n\n- If we have multiple classes: \n\n  A weight vector for each class \n\n  Score (activation) of a class y \n\n  $w_y \\cdot f(x)$ \n\n  Prediction highest score wins \n\n  $y = arg \\max_{y} w_y \\cdot f(x)$\nUpdating Weights in Multiclass Perceptron \n\n- Start with all weights = 0 \n\n- Pick up training examples one by one \n\n- Predict with current weights \n\n  $y = arg \\max_{y} w_y \\cdot f(x)$ \n\n- If correct, no change! \n\n- If wrong: lower score of wrong answer, raise score of right answer \n\n  $w_y = w_y - f(x)$ \n\n  $w_{y^*} = w_{y^*} + f(x)$\nProperties of Perceptrons \n- Separability: true if some parameters get the training set perfectly correct \n\n- Convergence: if the training is separable, perceptron will eventually converge (binary case) \n\n- Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability \n\nProblems with Perceptron\n- Noise: if the data isn’t separable, weights might thrash \n\n- Mediocre generalization: finds a “barely” separating solution \n\n- Overtraining: test / held-out accuracy usually rises, then falls \n\nFixing the Perceptron \n\n- MIRA = Margin Infused Relaxed Algorithm \n\n- Choose an update size that fixes the current mistake... ... but, minimizes the change to w \n\n  $w_y = w_y - tau f(x)$ \n\n  $w_{y^*} = w_{y^*} + tau f(x)$\n- Support Vector Machines \n\n  Maximizing the margin: good according to intuition, theory, practice Only support vectors matter; other training examples are ignorable \n\n  Support vector machines (SVMs) find the separator with max margin \n\n  Basically, SVMs are MIRA where you optimize over all examples at once \n\nNon-Linear Separators\n- Kenel trick\n- General idea: the original feature space can always be mapped to some higher-dimensional feature space where the training set is separable \n\nCLASSIFICATION COMPARISON \n\nNaive Bayes \n\n- Builds a model training data \n\n- Gives prediction probabilities \n\n- Strong assumptions about feature independence • One pass through data (counting) \n\nPerceptrons / MIRA \n\n- Makes less assumptions about data \n\n- Mistake-driven learning \n\n- Multiple passes through data (prediction) \n\n- Often more accurate \n\nQuestions \n\nThe Naive Bayes model is “naive” because it assumes that the features are conditionally independent of each other, given the class. \n\n- True \n\nWrite down the form of the joint probability model P(X1,X2,X3,Y) for this data using the Naive Bayes assumption. (Y is the class) \n\n- P(Y)P(X_1|Y)P(X_2|Y)P(X_3|Y) \n\n  In naive bayes, the features are conditionally independent of each other, given the class. \n\nIn the perceptron training algorithm, weights are updated after every training instance. \n\n- False \n\n  Training is error-driven - weights are only updated when the predicted label is incorrect. \n\nConsider a two-dimensional data distribution where points belonging to class A are arranged around the origin in a circle with radius ra, and points belonging to class B are arranged around the origin in a circle with radius rb, where ra<rb \n\n- can separate the two classes if we use feature augmentation. \n\n  If we augment the input with the features x2,y2, and a bias term, the problem becomes linearly separable. Decaying the learning rate will ensure that the weight vector converges, but since the unaugmented data is not linearly separable, this will still fail to separate the classes. Changing the order in which the instances are fed into the perceptron will not allow the perceptron to find a separating boundary. \n\nFor which of the following datasets would a single perceptron be unable to find a separating boundary (assuming we do not add additional features to the data): \n\n- Class A: {(0,0), (1,1)}; Class B: {(0,1), (1,0)} \n\n  The correct answer corresponds to the XOR problem, which is not linearly separable. All other options are linearly separable. \n\nGiven a non-random dataset, the perceptron algorithm guarantees that the weight vector will converge after a finite number of training iterations. \n\n- False \n\n  This is only true if the dataset is linearly separable. If it is not, the weight vector may fluctuate infinitely. The fluctuation can be remedied by techniques such as learning rate decay, but the basic perceptron algorithm is not guaranteed to converge. \n\nThe inference procedure for the perceptron classification algorithm is best summarized as: \n\n- Compute a weighted sum, then apply a threshold. \n\n  First, we compute the dot product of the weight vector and the input vector (that is, a weighted sum of the input features), and then threshold this value to output either true or false. If you picked the \"datum separatus\" option, you should consider transferring to Hogwarts. \n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \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 Your summary here \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\nClassifier Components\n1. Training Corpus of M observations input/output pairs (x,y) \n\n2. A feature representation of the input. For each input observation $x^i$, this will be a vector of features $[x_1,x_2,...,x_n]$ \n\n3. A classification function that computes the estimated class $\\hat{y}$ via $p(y|x)$ \n\n4. An objective function for learning, usually involving minimizing error on training examples \n\n5. An algorithm for optimizing the objective function \n\nLogistic Regression\n- From a training set, a vector of **weights** and a **bias term** \n\n  $z = \\sum_{i} w_i x_i + b$ \n\n  $z = w \\cdot x + b$ \n\nSigmoid Function\n- $f(x) = 1 / (1+e^{-x})$ \n\n- $P(y=1) = sigmoid(w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$ \n\n- $\\hat{y} = 1$ if $P(y=1 | x) > 0.5$ and $0$ otherwise \n\n- Reason for having is to avoid step change in classification function \n\nLearning in logistic regression\n- We learn the parameters (weights + bias) via learning. \n\n- An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss. \n\n- An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function \n\n**Loss Functions** \n\n- We need to determine for some observation $x$ how close the classifier output $\\hat{y} = sigmoid(w \\cdot x + b)$ is to the correct output $y$, which is 0 or 1 \n\n- One example is the mean squared error \n\n- We use a loss function that prefers the correct class labels of the training example to be more likely. \n\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. \n\n- The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss \n\nLoss on all training examples \n\n$log p(training labels) = log \\prod^{m}_{i=1}p(y^{i}|x^{i})$ \n\n$= \\sum^{m}_{i=1} log p(y^i | x^i)$ \n\n$= -\\sum^{m}_{i=1} L_{CE}(\\hat{y}^i | y^i)$ \n\nFinding good parameters \n\n$theta = arg \\min_{theta} (1/m) \\sum^{m}_{i=1} L_{CE}(y^i,x^i,theta)$ \n\nGradient Descent \n\n- a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction. \n\nGlobal vs Local Minimums \n\n- For logistic regression, this loss function is conveniently convex. \n\n- A convex function has just one minimum, so there are no local minima to get stuck in. \n\n- **THIS IS WHY THE CROSS-ENTROPY LOSS IS CHOSEN**\nHow much should we update the parameter by? \n\n- The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η. \n\n- A higher/faster learning rate means that we should move w more on each step. \n\nThe Gradient \n\n- The derivative of this function for one observation vector x for a single weight wj is: \n\n  $del L_{CE}(w,b) / del w_j = [s(w \\cdot x + b) - y] x_j$ \n\n- The gradient is a very intuitive value: the difference between the true y and our estimate for x, multiplied by the corresponding input value xj \n\nRegularization \n\n- Overfitting is a problem with many machine learning models. Overfitting results in poor generalization and poor performance on unseen test set. \n\n- In logistic regression, if a feature only occurs in one class then it will get a high weight. Sometimes we are just modelling noisy factors that just accidentally correlate with the class. \n\n- Regularization is a way to penalize large weights. A regularization term is added to the loss function. \n\n- Lasso regression uses L1 regularization \n\n- Ridge regression uses L2 regularization \n\nMultinomial logistic regression \n\n- Instead of binary classification, we often want more than two classes. For sentiment classification we might extend the class labels to be positive, negative, and neutral. \n\n- We want to know the probability of y for each class c ∈ C, p(y = c|x). \n\n- To get a proper probability, we will use a generalization of the sigmoid function called the softmax function  \n\n  $softmax(z_i) = e^{z_j} / (\\sum^{k}_{j=1} e^{z_j})$ for $1 \\leq i \\leq k$ \n\nSoftmax \n\n- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of values normalized into probabilities: \n\n  $softmax(z) = [e^{z_1} / (\\sum^{k}_{i=1}e^{z_i}),e^{z_2} / (\\sum^{k}_{i=1}e^{z_i}),...,e^{z_k} / (\\sum^{k}_{i=1}e^{z_i})]$ \n\n- For example, for this input: \n\n  $z = [0.6, 1.1, -1.5, 1.2, 3.2, -1.1]$ \n\n  Softmax $= [0.056, 0.090, 0.007, 0.099, 0.74, 0.010]$ \n\n  $z = 3.2$ is chosen \n\nNeural Networks \n\nSigmoid smoothness is crucial \n\n- Smoothness of σ means that small changes in the weights wj and in the bias b will produce a small change the output from the neuron \n\n- Δoutput is a linear function of the changes Δwj and Δb \n\n- This makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output \n\nNeural Networks Activation Functions \n\n- Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z \n\n- The output of this function is called the activation value for the unit, represented by the variable a. The output of a neural network is called y, so if the activation of a node is the final output of a network then \n\n- $y = a = f(z)$ \n\n- There are 3 commonly used non-linear functions used for f: The sigmoid function, The tanh function, The rectified linear unit ReLU \n \nQuestions \n\nWhich of the following are true about linear classifiers? Please check all that apply. \n\n- When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output. \n\n- They can be used for both regression and classification. \n\nWhich of the following best characterizes the difference between parametric and nonparametric models? \n\n- A parametric model has a fixed size on the number of parameters. \n\nWhen performing k-means clustering, each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration. \n\n- False \n\n  This is only true of agglomerative clustering.  \n\nFor linearly separable data, there exists only one decision boundary that separates the classes. \n\n- False \n\n  There could be multiple boundaries, but their performance may vary. \n\nIs it possible that the assignment of observations to clusters do not change between successive iterations in K-Means? \n\n- Yes \n\n  When approaching the converge point, the state may not change. \n\nRelative to single-layer perceptrons, neural networks gain their power from \n\n- stacking of layers \n\n  Multi-layer architecture of neural network provides enough parameters to get better performance on the task.  \n\nIn neural networks, nonlinear activation functions: Please check all that apply. \n\n- Help to learn nonlinear decision boundaries. \n\n- Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable. \n\n\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\nClassifier Components\n1. Training Corpus of M observations input/output pairs (x,y) \n\n2. A feature representation of the input. For each input observation $x^i$, this will be a vector of features $[x_1,x_2,...,x_n]$ \n\n3. A classification function that computes the estimated class $\\hat{y}$ via $p(y|x)$ \n\n4. An objective function for learning, usually involving minimizing error on training examples \n\n5. An algorithm for optimizing the objective function \n\nLogistic Regression\n- From a training set, a vector of **weights** and a **bias term** \n\n  $z = \\sum_{i} w_i x_i + b$ \n\n  $z = w \\cdot x + b$ \n\nSigmoid Function\n- $f(x) = 1 / (1+e^{-x})$ \n\n- $P(y=1) = sigmoid(w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$ \n\n- $\\hat{y} = 1$ if $P(y=1 | x) > 0.5$ and $0$ otherwise \n\n- Reason for having is to avoid step change in classification function \n\nLearning in logistic regression\n- We learn the parameters (weights + bias) via learning. \n\n- An objective function or loss function that tells us distance between the system output and the gold output. We will use cross-entropy loss. \n\n- An algorithm for optimizing the objective function. We will use stochastic gradient descent to minimize the loss function \n\n**Loss Functions** \n\n- We need to determine for some observation $x$ how close the classifier output $\\hat{y} = sigmoid(w \\cdot x + b)$ is to the correct output $y$, which is 0 or 1 \n\n- One example is the mean squared error \n\n- We use a loss function that prefers the correct class labels of the training example to be more likely. \n\n- Conditional maximum likelihood estimation: Choose parameters w, b that maximize the (log) probabilities of the true labels in the training data. \n\n- The resulting loss function is the negative log likelihood loss, more commonly called the cross entropy loss \n\nLoss on all training examples \n\n$log p(training labels) = log \\prod^{m}_{i=1}p(y^{i}|x^{i})$ \n\n$= \\sum^{m}_{i=1} log p(y^i | x^i)$ \n\n$= -\\sum^{m}_{i=1} L_{CE}(\\hat{y}^i | y^i)$ \n\nFinding good parameters \n\n$theta = arg \\min_{theta} (1/m) \\sum^{m}_{i=1} L_{CE}(y^i,x^i,theta)$ \n\nGradient Descent \n\n- a method that finds a minimum of a function by figuring out in which direction (in the space of the parameters θ) the function’s slope is rising the most steeply, and moving in the opposite direction. \n\nGlobal vs Local Minimums \n\n- For logistic regression, this loss function is conveniently convex. \n\n- A convex function has just one minimum, so there are no local minima to get stuck in. \n\n- **THIS IS WHY THE CROSS-ENTROPY LOSS IS CHOSEN**\nHow much should we update the parameter by? \n\n- The magnitude of the amount to move in gradient descent is the value of the slope weighted by a learning rate η. \n\n- A higher/faster learning rate means that we should move w more on each step. \n\nThe Gradient \n\n- The derivative of this function for one observation vector x for a single weight wj is: \n\n  $del L_{CE}(w,b) / del w_j = [s(w \\cdot x + b) - y] x_j$ \n\n- The gradient is a very intuitive value: the difference between the true y and our estimate for x, multiplied by the corresponding input value xj \n\nRegularization \n\n- Overfitting is a problem with many machine learning models. Overfitting results in poor generalization and poor performance on unseen test set. \n\n- In logistic regression, if a feature only occurs in one class then it will get a high weight. Sometimes we are just modelling noisy factors that just accidentally correlate with the class. \n\n- Regularization is a way to penalize large weights. A regularization term is added to the loss function. \n\n- Lasso regression uses L1 regularization \n\n- Ridge regression uses L2 regularization \n\nMultinomial logistic regression \n\n- Instead of binary classification, we often want more than two classes. For sentiment classification we might extend the class labels to be positive, negative, and neutral. \n\n- We want to know the probability of y for each class c ∈ C, p(y = c|x). \n\n- To get a proper probability, we will use a generalization of the sigmoid function called the softmax function  \n\n  $softmax(z_i) = e^{z_j} / (\\sum^{k}_{j=1} e^{z_j})$ for $1 \\leq i \\leq k$ \n\nSoftmax \n\n- The softmax function takes in an input vector z = [z1,z2,...,zk] and outputs a vector of values normalized into probabilities: \n\n  $softmax(z) = [e^{z_1} / (\\sum^{k}_{i=1}e^{z_i}),e^{z_2} / (\\sum^{k}_{i=1}e^{z_i}),...,e^{z_k} / (\\sum^{k}_{i=1}e^{z_i})]$ \n\n- For example, for this input: \n\n  $z = [0.6, 1.1, -1.5, 1.2, 3.2, -1.1]$ \n\n  Softmax $= [0.056, 0.090, 0.007, 0.099, 0.74, 0.010]$ \n\n  $z = 3.2$ is chosen \n\nNeural Networks \n\nSigmoid smoothness is crucial \n\n- Smoothness of σ means that small changes in the weights wj and in the bias b will produce a small change the output from the neuron \n\n- Δoutput is a linear function of the changes Δwj and Δb \n\n- This makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output \n\nNeural Networks Activation Functions \n\n- Instead of directly outputting z = w·x+b, which is a linear function of x, neuron units apply a non-linear function f to z \n\n- The output of this function is called the activation value for the unit, represented by the variable a. The output of a neural network is called y, so if the activation of a node is the final output of a network then \n\n- $y = a = f(z)$ \n\n- There are 3 commonly used non-linear functions used for f: The sigmoid function, The tanh function, The rectified linear unit ReLU \n \nQuestions \n\nWhich of the following are true about linear classifiers? Please check all that apply. \n\n- When using the perceptron learning rule, the weights are updated when the actual output does not match the hypothesis output. \n\n- They can be used for both regression and classification. \n\nWhich of the following best characterizes the difference between parametric and nonparametric models? \n\n- A parametric model has a fixed size on the number of parameters. \n\nWhen performing k-means clustering, each observation always starts in its own cluster, and then pairs of clusters are merged in each iteration. \n\n- False \n\n  This is only true of agglomerative clustering.  \n\nFor linearly separable data, there exists only one decision boundary that separates the classes. \n\n- False \n\n  There could be multiple boundaries, but their performance may vary. \n\nIs it possible that the assignment of observations to clusters do not change between successive iterations in K-Means? \n\n- Yes \n\n  When approaching the converge point, the state may not change. \n\nRelative to single-layer perceptrons, neural networks gain their power from \n\n- stacking of layers \n\n  Multi-layer architecture of neural network provides enough parameters to get better performance on the task.  \n\nIn neural networks, nonlinear activation functions: Please check all that apply. \n\n- Help to learn nonlinear decision boundaries. \n\n- Make it possible to do the gradient calculation in backpropagation, as opposed to using step function which isn't differentiable. \n\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}