{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Ernest CIS521 MT2 notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "72ba3047-adf2-467a-ca9a-ae69166d4329"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ca0f8a5a-52de-44c7-f10e-a6488c6f3701"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "- **Maximum Expected Utility (MEU) Principle**: Rational agent should choose actions that maximise their expected utility\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"\n",
        "**Theorem**: Given any preferences satisfying the axioms of utility theory, there exists some real-valued function $U$ such that $$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$$\n",
        "$$U([p_1, S_1; \\ldots; p_n, S_n]) = \\sum_{i = 1}^n p_iS_i$$\n",
        "\n",
        "- Positive affine transformations of the form $U'(S) = aU(S) + b$ don't change the utility function\n",
        "- If prizes are deterministic (no probability), only ordinal utility can be determined (i.e. only preferences matter, numbers don't matter)\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "For a lottery $L = [p, \\$X; 1 - p, \\$Y]$, the **Expected Monetary Value** $EMV(L) = pX + (1 - p)Y$, \\\n",
        "with utility $U(L) = pU(\\$X) + (1 - p)U(\\$Y)$.    \n",
        "Usually, $U(L) < EMV(L)$. \n",
        "\n",
        "$\\hat{EU}(a) = $ *estimated* expected utility\n",
        "\n",
        "- **Preference elicitation**: Presenting a human with the **standard lottery** $[p, A; 1 - p, B]$ and adjusting $p$ such that preferences are indifferent \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "- A policy $\\pi$ specifies what the agent should do for any state $s$ that the agent reaches     \n",
        "- An optimal policy $\\pi^*$ = policy with the maximum expected utility\n",
        "- **Nonstationary policy**: policy that depends on time remaining      \n",
        "- **Stationary policy**: optimal action depends only on current state (no time limit)   \n",
        "\n",
        "- **Stationary preferences** on reward sequences: $$[a_1, a_2, \\ldots] > [b_1, b_2, \\ldots] \\longleftrightarrow [r, a_1, a_2, \\ldots] > [r, b_1, b_2, \\ldots]$$,\n",
        "i.e. if you prefer one future to another, you would maintain the same preference if that future were to start today\n",
        "- **Theorem**: Assuming stationary preferences, there are only 2 ways to define utilities:\n",
        "* Additive utility: $U([r_0, r_1, \\ldots]) = r_0 + r_1 + r_2 + \\ldots$      \n",
        "* Discounted utility: $U([r_0, r_1, \\ldots]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 + \\ldots$   \n",
        "\n",
        "- Dealing with infinite utilities:\n",
        "1. Finite horizon (terminate episodes after fixed no. of steps), use nonstationary policies\n",
        "2. Discounting (use $0 < \\gamma < 1$, where $\\gamma$ is the discount rate)\n",
        "* Smaller $\\gamma$ means smaller \"horizon\"\n",
        "3. Have an absorbing state (ensures that each policy reaches a terminal state)\n",
        "\n",
        "- **Shaping Theorem**: Optimal policies remain invariant under transformations of the form $$R'(S, a, s') = R(s, a, s') + \\gamma\\phi(s') - \\phi(s')$$, where $\\phi(s)$ is any function in terms of $s$\n",
        "- Call $\\phi(s)$ the *potential* function\n",
        "\n",
        "- **Dynamic Decision Network (DDN)**: factored representation of MDP (each state described in terms of features)\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "- Let $V_k(s)$ = optimal value of state $s$ if game ends in $k$ more steps, i.e. what a depth-$k$ expectimax would give from $s$\n",
        "- **Value Iteration**: Apply Bellman update to each state $s$,\n",
        "- Problems with Value Iteration:      \n",
        "1. Slow, $O(S^2A)$ per iteration      \n",
        "2. Max value at each state rarely changes       \n",
        "2. Policy often converges long before the value              \n",
        "- **Policy Iteration**: Given a policy $\\pi_i$, calculate $U_i = U^{\\pi_i}$, the utility of each state if the policy $\\pi_i$ were to be executed\n",
        "- **Policy Improvement**: Calculate a new MEU policy $π_{i + 1}$ using one-step look ahead function, $O(S^2)$\n",
        "\n",
        "- Policy iteration algorithm alternates between policy evaluation & policy improvement until convergence       \n",
        "- *Modified Policy Iteration*: Fix a policy, apply a few value iteration steps to approximate utilities    \n",
        "- *Asynchronous Policy Iteration*: Pick *any* subset of states and apply policy improvement / value iteration to that subset     \n",
        "\n",
        "- MDPs can be solved in **polynomial time** wrt the no. of states and actions\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "\n",
        "- **MEU Principle (Maximum Expected Utility)**: Agents are rational if they choose the action that yields the highest expected utility\n",
        "\n",
        "\n",
        "|                         **Value Iteration**                         |                                                    **Policy Iteration**                                                   |\n",
        "|:---------------------------------------------------------------:|:---------------------------------------------------------------------------------------------------------------------:|\n",
        "| $O(S^2A)$ per iteration                                         | $O(S^2)$ per iteration                                                                                                |\n",
        "| Every iteration updates both values and (implicitly) the policy | Several passes that update utilities with fixed policy. After evaluating the policy, choose a new (improved) policy.  |\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\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"(16. 3) Certainty equivalent\": \"The value an agent accepts in place of a lottery\",\n",
        "\"(16.3) Insurance premium\": \"Difference between a lottery's EMV and its certainty equivalent\",\n",
        "\"(16.3) Unbiased esimate\": \"Error between estimate and actual value is 0, i.e. $E(\\hat{EU}(A) - EU(A)) = 0$\",\n",
        "\"(16.3) Optimizer's curse\": \"Estimated expected utility is overly high\",\n",
        "\"(16.3) Certainty effect\": \"People prefer deterministic over stochastic games\",\n",
        "\"(16.3) Anchoring effect\": \"People prefer making relative utility judgements over absolute ones\",\n",
        "\"(17.1) Proper policy\": \"Policy guaranteed to reach a terminal state\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "49632b1f-fe82-4b70-bcec-dabc9f732335"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- **Maximum Expected Utility (MEU) Principle**: Rational agent should choose actions that maximise their expected utility\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n**Theorem**: Given any preferences satisfying the axioms of utility theory, there exists some real-valued function $U$ such that $$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$$\n$$U([p_1, S_1; \\ldots; p_n, S_n]) = \\sum_{i = 1}^n p_iS_i$$\n\n- Positive affine transformations of the form $U'(S) = aU(S) + b$ don't change the utility function\n- If prizes are deterministic (no probability), only ordinal utility can be determined (i.e. only preferences matter, numbers don't matter)\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nFor a lottery $L = [p, \\$X; 1 - p, \\$Y]$, the **Expected Monetary Value** $EMV(L) = pX + (1 - p)Y$, with utility $U(L) = pU(\\$X) + (1 - p)U(\\$Y)$.    \nUsually, $U(L) < EMV(L)$. \n\n$\\hat{EU}(a) = $ *estimated* expected utility\n\n- **Preference elicitation**: Presenting a human with the **standard lottery** $[p, A; 1 - p, B]$ and adjusting $p$ such that preferences are indifferent \n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- A policy $\\pi$ specifies what the agent should do for any state $s$ that the agent reaches     \n- An optimal policy $\\pi^*$ = policy with the maximum expected utility\n- **Nonstationary policy**: policy that depends on time remaining      \n- **Stationary policy**: optimal action depends only on current state (no time limit)   \n\n- **Stationary preferences** on reward sequences: $$[a_1, a_2, \\ldots] > [b_1, b_2, \\ldots] \\longleftrightarrow [r, a_1, a_2, \\ldots] > [r, b_1, b_2, \\ldots]$$,\ni.e. if you prefer one future to another, you would maintain the same preference if that future were to start today\n- **Theorem**: Assuming stationary preferences, there are only 2 ways to define utilities:\n* Additive utility: $U([r_0, r_1, \\ldots]) = r_0 + r_1 + r_2 + \\ldots$      \n* Discounted utility: $U([r_0, r_1, \\ldots]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 + \\ldots$   \n\n- Dealing with infinite utilities:\n1. Finite horizon (terminate episodes after fixed no. of steps), use nonstationary policies\n2. Discounting (use $0 < \\gamma < 1$, where $\\gamma$ is the discount rate)\n* Smaller $\\gamma$ means smaller \"horizon\"\n3. Have an absorbing state (ensures that each policy reaches a terminal state)\n\n- **Shaping Theorem**: Optimal policies remain invariant under transformations of the form $$R'(S, a, s') = R(s, a, s') + \\gamma\\phi(s') - \\phi(s')$$, where $\\phi(s)$ is any function in terms of $s$\n- Call $\\phi(s)$ the *potential* function\n\n- **Dynamic Decision Network (DDN)**: factored representation of MDP (each state described in terms of features)\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- Let $V_k(s)$ = optimal value of state $s$ if game ends in $k$ more steps, i.e. what a depth-$k$ expectimax would give from $s$\n- **Value Iteration**: Apply Bellman update to each state $s$,\n- Problems with Value Iteration:      \n1. Slow, $O(S^2A)$ per iteration      \n2. Max value at each state rarely changes       \n2. Policy often converges long before the value              \n- **Policy Iteration**: Given a policy $\\pi_i$, calculate $U_i = U^{\\pi_i}$, the utility of each state if the policy $\\pi_i$ were to be executed\n- **Policy Improvement**: Calculate a new MEU policy $π_{i + 1}$ using one-step look ahead function, $O(S^2)$\n\n- Policy iteration algorithm alternates between policy evaluation & policy improvement until convergence       \n- *Modified Policy Iteration*: Fix a policy, apply a few value iteration steps to approximate utilities    \n- *Asynchronous Policy Iteration*: Pick *any* subset of states and apply policy improvement / value iteration to that subset     \n\n- MDPs can be solved in **polynomial time** wrt the no. of states and actions\n\n\n## Module 8 Lecture Notes\n\n\n- **MEU Principle (Maximum Expected Utility)**: Agents are rational if they choose the action that yields the highest expected utility\n\n\n|                         **Value Iteration**                         |                                                    **Policy Iteration**                                                   |\n|:---------------------------------------------------------------:|:---------------------------------------------------------------------------------------------------------------------:|\n| $O(S^2A)$ per iteration                                         | $O(S^2)$ per iteration                                                                                                |\n| Every iteration updates both values and (implicitly) the policy | Several passes that update utilities with fixed policy. After evaluating the policy, choose a new (improved) policy.  |\n\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **(16. 3) certainty equivalent** - The value an agent accepts in place of a lottery\n* **(16.3) insurance premium** - Difference between a lottery's EMV and its certainty equivalent\n* **(16.3) unbiased esimate** - Error between estimate and actual value is 0, i.e. $E(\\hat{EU}(A) - EU(A)) = 0$\n* **(16.3) optimizer's curse** - Estimated expected utility is overly high\n* **(16.3) certainty effect** - People prefer deterministic over stochastic games\n* **(16.3) anchoring effect** - People prefer making relative utility judgements over absolute ones\n* **(17.1) proper policy** - Policy guaranteed to reach a terminal state\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "- On an n-armed bandit, each arm $M_i$ is a **Markov Reward Process** (MDP w/ only one action), arms are independent\n",
        "- The overall bandit is an MDP \n",
        "\n",
        "- **Gittins Index** for an arm $M$: Maximum obtainable utility per unit of discounted time\n",
        "- Optimal policy for a bandit problem: Pull the arm w/ the highest Gittins Index, then update Gittins indices\n",
        "- **Bernoulli Bandit**: Each arm $M_i$ is a Bernoulli process with success probability $\\mu_i$ \n",
        "- **Bandit Superprocess (BSP)**: Each arm is a full MDP (multitasking)      \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "\n",
        "**Model-Based RL**     \n",
        "- Learn a transition model (estimate $\\hat{T}(s, a, s')$) by observing rewards that are yielded when we perform actions\n",
        "- Count outsomes s' for each s and normalize to estimate $\\hat{T}(s, a, s')$\n",
        "- Solve the learned MDP as before\n",
        "\n",
        "\n",
        "**Model-Free RL**\n",
        "1.**Q-Learning**: learn a **Q-function** $Q(s, a)$, which is the sum of rewards from state $s$ onward after taking action $a$\n",
        "- After learning the Q-function, for each state s, choose the action a that has the highest Q-value\n",
        "\n",
        "2. **Policy search** (reflex agent)\n",
        "- Learn a policy $\\pi(s)$ (what action to do at each state)\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "**Passive RL**\n",
        "- Input: fixed policy $\\pi(s)$\n",
        "- Task: Learn the utilities of states according to $\\pi(s)$ (**Policy Evaluation**)\n",
        "(agent just executes the policy, can't choose actions)\n",
        "\n",
        "**Direct Utility Estimation / Direct Evaluation**   \n",
        "- Compute values for each state under policy $\\pi$\n",
        "- Every time we visit a state, record the sum of discounted rewards, and average these samples\n",
        "|                                        Pros                                       |                      Cons                     |\n",
        "|:---------------------------------------------------------------------------------:|:---------------------------------------------:|\n",
        "| Doesn't require any knowledge of the transition or reward functions               | Need to learn each state's utility separately |\n",
        "| Sample average converges to true expectation as we perform infinitely many trials | Ignores connections between states            |\n",
        "\n",
        "\n",
        "**Adaptive Dynamic Programming**\n",
        "- Learn the transition model of the MDP and solve it (apply policy evaluation)\n",
        "\n",
        "**Temporal-Difference Learning** (see paper notes)\n",
        "- Policy fixed, still doing policy evaluation\n",
        "- Update the value V(s) every time we transition from s to s' via an action\n",
        "- The outcomes s' which are more likely will contribute more update to V(s)\n",
        "- Adjusts a state so that it agrees with its observed successor\n",
        "**Exponential Moving Average**: place greater emphasis on recent samples\n",
        "|                       Pros                      |               Cons              |\n",
        "|:-----------------------------------------------:|:-------------------------------:|\n",
        "| Converges to the true value in the limit        | Can't turn values into a policy |\n",
        "| Simple, requires less computation per iteration |                                 |\n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "\n",
        "**Active Reinforcement Learning**\n",
        "- Goal: learn optimal policy / values (transition & reward function unknown)\n",
        "- Agent can **choose actions** now!\n",
        "\n",
        "- **Greedy agent**: greedily takes the action believed to be optimal at each step\n",
        "- **Exploration-Exploitation Tradeoff**: Explore unknown states to gain more information that could lead to a change in policy, or choose the best action to maximise current reward?\n",
        "- GLIE Schemes: Try each state an unbounded no. of times to avoid missing an optimal action\n",
        "\n",
        "**Q-Learning**\n",
        "- **Off-Policy**: Learns Q-values that answer the question \"what is this action worth if we stop following the current policy and start acting according to a policy that chooses the best estimated action\"\n",
        "- Need to explore enough, make learning rate small enough      \n",
        "- In the limit, it doesn't matter how actions are chosen    \n",
        "\n",
        "- Alternative: **On-Policy**: Learns Q-values that answer the question \"what is this action worth in this state if we stick with the current policy?@\n",
        "\n",
        "**$\\epsilon$-Greedy Agents**\n",
        "- With small probability $\\epsilon$, act randomly, and with probability $1 - \\epsilon$, follow current policy\n",
        "- Forces exploration\n",
        "- Pros: Explores the entire space eventually\n",
        "- Cons: Thrashes around once learning is done (solution: lower $\\epsilon$ over time)\n",
        "\n",
        "**Exploration Functions**\n",
        "- Idea: explore areas whose badness is not established and eventually stop exploring\n",
        "- Takes a value estimate u, a visit count n, and returns an optimistic utility\n",
        "$$f(u, n) = u + k/n$$\n",
        "- Note that $\\lim_{n -> \\infty} f(u, n) = u$ (converges to utility estimate in the limit)\n",
        "- When $n$ is small, $k$ dominates \n",
        "- Determines how preference for high utility values is traded off against preference for rarely-tried acions (i.e. greed vs curiosity)\n",
        "- $k$ determines how much exploration to do\n",
        "\n",
        "**Regret**: Total mistake cost (difference between actual expected rewards and optimal expected rewards)\n",
        "- Random exploration has higher regret than exploration functions  \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"\n",
        "- **Approximating direct utility estimation**: Use a supervised learning algorithm to learn weights for a linear combination of feature values\n",
        "- **Catastrophic forgetting**: Tendency to forget old information upon learning new information       \n",
        "- Solution: **Experience replay**: Replay past experiences at regular intervals to ensure accuracy of value function    \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "- Solving MDPs is offline planning -- don't need to actually play the game    \n",
        "- Reinforcement learning: Online planning, must play the game and learn to act to **maximise expected rewards**\n",
        "- All learning done through observed rewards that the agent receives\n",
        "\n",
        "- Idea behind RL: assume a MDP and looking for a policy $\\pi(s)$, but we don't know the transition model or the reward function!\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"N-armed bandit\" : \"Slot machine with n arms\",\n",
        "\"Sparse rewards\": \"Zero reward for most states\",\n",
        "\"Expected reward to go of a state s\": \"Expected total reward from state s onward\",\n",
        "\"GLIE\": \"Greedy in the Limit of Infinit Exploration\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "dcc22d9a-627a-40da-ef44-6d13eadd7512"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- On an n-armed bandit, each arm $M_i$ is a **Markov Reward Process** (MDP w/ only one action), arms are independent\n- The overall bandit is an MDP \n\n- **Gittins Index** for an arm $M$: Maximum obtainable utility per unit of discounted time\n- Optimal policy for a bandit problem: Pull the arm w/ the highest Gittins Index, then update Gittins indices\n- **Bernoulli Bandit**: Each arm $M_i$ is a Bernoulli process with success probability $\\mu_i$ \n- **Bandit Superprocess (BSP)**: Each arm is a full MDP (multitasking)      \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n\n**Model-Based RL**     \n- Learn a transition model (estimate $\\hat{T}(s, a, s')$) by observing rewards that are yielded when we perform actions\n- Count outsomes s' for each s and normalize to estimate $\\hat{T}(s, a, s')$\n- Solve the learned MDP as before\n\n\n**Model-Free RL**\n1.**Q-Learning**: learn a **Q-function** $Q(s, a)$, which is the sum of rewards from state $s$ onward after taking action $a$\n- After learning the Q-function, for each state s, choose the action a that has the highest Q-value\n\n2. **Policy search** (reflex agent)\n- Learn a policy $\\pi(s)$ (what action to do at each state)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n**Passive RL**\n- Input: fixed policy $\\pi(s)$\n- Task: Learn the utilities of states according to $\\pi(s)$ (**Policy Evaluation**)\n(agent just executes the policy, can't choose actions)\n\n**Direct Utility Estimation / Direct Evaluation**   \n- Compute values for each state under policy $\\pi$\n- Every time we visit a state, record the sum of discounted rewards, and average these samples\n|                                        Pros                                       |                      Cons                     |\n|:---------------------------------------------------------------------------------:|:---------------------------------------------:|\n| Doesn't require any knowledge of the transition or reward functions               | Need to learn each state's utility separately |\n| Sample average converges to true expectation as we perform infinitely many trials | Ignores connections between states            |\n\n\n**Adaptive Dynamic Programming**\n- Learn the transition model of the MDP and solve it (apply policy evaluation)\n\n**Temporal-Difference Learning** (see paper notes)\n- Policy fixed, still doing policy evaluation\n- Update the value V(s) every time we transition from s to s' via an action\n- The outcomes s' which are more likely will contribute more update to V(s)\n- Adjusts a state so that it agrees with its observed successor\n**Exponential Moving Average**: place greater emphasis on recent samples\n|                       Pros                      |               Cons              |\n|:-----------------------------------------------:|:-------------------------------:|\n| Converges to the true value in the limit        | Can't turn values into a policy |\n| Simple, requires less computation per iteration |                                 |\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n\n**Active Reinforcement Learning**\n- Goal: learn optimal policy / values (transition & reward function unknown)\n- Agent can **choose actions** now!\n\n- **Greedy agent**: greedily takes the action believed to be optimal at each step\n- **Exploration-Exploitation Tradeoff**: Explore unknown states to gain more information that could lead to a change in policy, or choose the best action to maximise current reward?\n- GLIE Schemes: Try each state an unbounded no. of times to avoid missing an optimal action\n\n**Q-Learning**\n- **Off-Policy**: Learns Q-values that answer the question \"what is this action worth if we stop following the current policy and start acting according to a policy that chooses the best estimated action\"\n- Need to explore enough, make learning rate small enough      \n- In the limit, it doesn't matter how actions are chosen    \n\n- Alternative: **On-Policy**: Learns Q-values that answer the question \"what is this action worth in this state if we stick with the current policy?@\n\n**$\\epsilon$-Greedy Agents**\n- With small probability $\\epsilon$, act randomly, and with probability $1 - \\epsilon$, follow current policy\n- Forces exploration\n- Pros: Explores the entire space eventually\n- Cons: Thrashes around once learning is done (solution: lower $\\epsilon$ over time)\n\n**Exploration Functions**\n- Idea: explore areas whose badness is not established and eventually stop exploring\n- Takes a value estimate u, a visit count n, and returns an optimistic utility\n$$f(u, n) = u + k/n$$\n- Note that $\\lim_{n -> \\infty} f(u, n) = u$ (converges to utility estimate in the limit)\n- When $n$ is small, $k$ dominates \n- Determines how preference for high utility values is traded off against preference for rarely-tried acions (i.e. greed vs curiosity)\n- $k$ determines how much exploration to do\n\n**Regret**: Total mistake cost (difference between actual expected rewards and optimal expected rewards)\n- Random exploration has higher regret than exploration functions  \n\n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n- **Approximating direct utility estimation**: Use a supervised learning algorithm to learn weights for a linear combination of feature values\n- **Catastrophic forgetting**: Tendency to forget old information upon learning new information       \n- Solution: **Experience replay**: Replay past experiences at regular intervals to ensure accuracy of value function    \n\n\n\n\n## Module 9 Lecture Notes\n\n- Solving MDPs is offline planning -- don't need to actually play the game    \n- Reinforcement learning: Online planning, must play the game and learn to act to **maximise expected rewards**\n- All learning done through observed rewards that the agent receives\n\n- Idea behind RL: assume a MDP and looking for a policy $\\pi(s)$, but we don't know the transition model or the reward function!\n\n\n\n\n\n## Module 9 Definitions\n* **N-armed bandit** - Slot machine with n arms\n* **Sparse rewards** - Zero reward for most states\n* **Expected reward to go of a state s** - Expected total reward from state s onward\n* **Glie** - Greedy in the Limit of Infinit Exploration\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 = \"\"\"\n",
        "- Goal: Compute $P(w | h)$, probability of a word w given a history h\n",
        "- **N-gram models** allow us to **approximate** the history using the last n-1 words in the past\n",
        "- Eg. **Unigram models** have no history\n",
        "- Eg. **Bigram models** have 1 word as history\n",
        "\n",
        "- **Maximum Likelihood Estimate**: Get counts from a corpus and normalize counts between [0, 1]\n",
        "- Problems with MLE: \n",
        "1. Assigns zero probabilities to unseen n-grams (avoid zeros with smoothing)\n",
        "2. Can't deal with unknown words / out of vocabulary items (replace any word not in lexicon with <unk>)\n",
        "\n",
        "- In practice, we add log probabilities (avoids numeric underflow):\n",
        "$$log(p_1 * p_2 * p_3) = log(p_1) + log(p_2) + log(p_3)$$\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "- **Backoff**: If n-gram has zero counts, use n-1 gram (shorter history), and continue backing off until we reach a history that has some counts\n",
        "- **Interpolation**: Take a weighted average of all n-gram estimators (for different) n\n",
        "$$P(w_n | w_{n-2} w_{n-1}) = \\lambda_1(w_{n-2:n-1})P(w_n) + \\lambda_2(w_{n-2:n-1})P(w_n | w_{n-1}) + \\lambda_3(w_{n-2:n-1})P(w_n | w_{n-1} w_{n-2})$$\n",
        "- **Held-out corpus**: Additional corpus that we use to set hyperparameters    \n",
        "- **Katz backoff**: If we've seen this n-gram before, use a discounted probability, else recursively backoff to the Katz backoff for the shorter history n-1 gram\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "**Stupid backoff**: No discounting of probabilities for higher-order n-grams (n-grams with higher n) -> does not produce a probability distribution     \n",
        "- If an n-gram has zero count, we backoff to an n-1 gram, weighted by a fixed weight $\\lambda$      \n",
        "\n",
        "$$S(w_i | w_{i - k + 1: i - 1}) = \\cfrac{count(w_{i-k+1:i})}{count(w_{i-k+1:i-1})}  ~if  ~count(w_{i-k+1:i}) >  0$$          \n",
        "$$ S(w_i | w_{i - k + 1: i - 1}) = \\lambda S( w_{i - k + 2: i - 1}) ~otherwise$$                             \n",
        "\n",
        "- Terminates in the unigram, which has probability $S(w) = \\cfrac{count(w)}{N}$  \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "**Inclusion-Exclusion Principle**: $P(A \\cup B) = P(A) + P(B) - P(A \\cap B)$    \n",
        "**De Finetti's Theorem**: If an agent has some degree of belief in proposition $a$, they should be able to state odds at which it is indifferent to a bet for or against $a$    \n",
        "(i.e. no rational agent can have beliefs that violate probability axioms)         \n",
        "\n",
        "**Marginal Distributions** $$P(X_1) = \\sum_{x_2} P(X_1, X_2 = x_2)$$ (sum out the probabilities for the other variable's outcome)         \n",
        "**Conditional Probability**: $$P(A | B) = \\cfrac{P(A \\cap B)}{P(B)}$$                   \n",
        "**Chain Rule**: $$P(A \\cap B) = P(A | B)P(B)$$                          \n",
        "$$P(X_1, X_2, X_3) = P(X_1)P(X_2 | X_1)P(X_3 | X_1, X_2)$$             \n",
        "$$P(X_1, X_2, \\ldots, X_n) = \\prod_{i} P(X_i | X_1 \\ldots X_{i - 1})$$             \n",
        "\n",
        "**Bayes' Rule**: $$P(A | B) = \\cfrac{P(B | A)P(A)}{P(B)}$$      \n",
        "General version conditionalized on background evidence $e$: $$P(Y | X, e) = \\cfrac{P(X | Y, e)P(Y | e)}{P(X | e)}$$        \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Markov assumption\" : \"Probability of a word depends only on the probability of the previous word\",\n",
        "\"Prior\": \"Unconditional probability of an event $P(A)$ (our belief before new evidence is taken into account)\",\n",
        "\"Posterior\": \"The conditional Probability $P(A | B)$ (our belief after taking into account new evidence)\",\n",
        "\"Gold labels\": \"Human-defined labels\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4c5c0f8c-1917-416c-b2e0-6ec4016299b9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n 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\n- Goal: Compute $P(w | h)$, probability of a word w given a history h\n- **N-gram models** allow us to **approximate** the history using the last n-1 words in the past\n- Eg. **Unigram models** have no history\n- Eg. **Bigram models** have 1 word as history\n\n- **Maximum Likelihood Estimate**: Get counts from a corpus and normalize counts between [0, 1]\n- Problems with MLE: \n1. Assigns zero probabilities to unseen n-grams (avoid zeros with smoothing)\n2. Can't deal with unknown words / out of vocabulary items (replace any word not in lexicon with <unk>)\n\n- In practice, we add log probabilities (avoids numeric underflow):\n$$log(p_1 * p_2 * p_3) = log(p_1) + log(p_2) + log(p_3)$$\n\n\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n\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\n- **Backoff**: If n-gram has zero counts, use n-1 gram (shorter history), and continue backing off until we reach a history that has some counts\n- **Interpolation**: Take a weighted average of all n-gram estimators (for different) n\n$$P(w_n | w_{n-2} w_{n-1}) = \\lambda_1(w_{n-2:n-1})P(w_n) + \\lambda_2(w_{n-2:n-1})P(w_n | w_{n-1}) + \\lambda_3(w_{n-2:n-1})P(w_n | w_{n-1} w_{n-2})$$\n- **Held-out corpus**: Additional corpus that we use to set hyperparameters    \n- **Katz backoff**: If we've seen this n-gram before, use a discounted probability, else recursively backoff to the Katz backoff for the shorter history n-1 gram\n\n\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n**Stupid backoff**: No discounting of probabilities for higher-order n-grams (n-grams with higher n) -> does not produce a probability distribution     \n- If an n-gram has zero count, we backoff to an n-1 gram, weighted by a fixed weight $\\lambda$      \n\n$$S(w_i | w_{i - k + 1: i - 1}) = \\cfrac{count(w_{i-k+1:i})}{count(w_{i-k+1:i-1})}  ~if  ~count(w_{i-k+1:i}) >  0$$          \n$$ S(w_i | w_{i - k + 1: i - 1}) = \\lambda S( w_{i - k + 2: i - 1}) ~otherwise$$                             \n\n- Terminates in the unigram, which has probability $S(w) = \\cfrac{count(w)}{N}$  \n\n\n\n\n\n\n## Module 10 Lecture Notes\n\n**Inclusion-Exclusion Principle**: $P(A \\cup B) = P(A) + P(B) - P(A \\cap B)$    \n**De Finetti's Theorem**: If an agent has some degree of belief in proposition $a$, they should be able to state odds at which it is indifferent to a bet for or against $a$    \n(i.e. no rational agent can have beliefs that violate probability axioms)         \n\n**Marginal Distributions** $$P(X_1) = \\sum_{x_2} P(X_1, X_2 = x_2)$$ (sum out the probabilities for the other variable's outcome)         \n**Conditional Probability**: $$P(A | B) = \\cfrac{P(A \\cap B)}{P(B)}$$                   \n**Chain Rule**: $$P(A \\cap B) = P(A | B)P(B)$$                          \n$$P(X_1, X_2, X_3) = P(X_1)P(X_2 | X_1)P(X_3 | X_1, X_2)$$             \n$$P(X_1, X_2, \\ldots, X_n) = \\prod_{i} P(X_i | X_1 \\ldots X_{i - 1})$$             \n\n**Bayes' Rule**: $$P(A | B) = \\cfrac{P(B | A)P(A)}{P(B)}$$      \nGeneral version conditionalized on background evidence $e$: $$P(Y | X, e) = \\cfrac{P(X | Y, e)P(Y | e)}{P(X | e)}$$        \n\n\n## Module 10 Definitions\n* **Markov assumption** - Probability of a word depends only on the probability of the previous word\n* **Prior** - Unconditional probability of an event $P(A)$ (our belief before new evidence is taken into account)\n* **Posterior** - The conditional Probability $P(A | B)$ (our belief after taking into account new evidence)\n* **Gold labels** - Human-defined labels\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",
        "\n",
        "\n",
        "**Independent RVs**: $$A \\perp \\!\\!\\! \\perp B \\Longleftrightarrow P(A, B) = P(A)P(B)$$\n",
        "**Conditional Independence**: X is independent of Y given Z $$(X \\perp \\!\\!\\! \\perp Y) | Z \\Longleftrightarrow P(X, Y | Z) = P(X|Z)P(Y|Z)$$               \n",
        "$$(X \\perp \\!\\!\\! \\perp Y) | Z \\Longleftrightarrow P(Y|X, Z) = P(Y | Z)$$           \n",
        "(eg. Umbrella is conditionally independent of Traffic given Rain)          \n",
        "- Conditional probability table (CPT) for $n$ independent RVs grows by $O(2^n)$\n",
        "- CPT for $n$ conditionally independent RVs grows by $O(n)$               \n",
        "- Conditional independence allows probabilistic systems to scale up    \n",
        "\n",
        "\n",
        "**Conditional probability tables (CPTs)**\n",
        "- For discrete RVs only       \n",
        "- Each row in a CPT must sum to 1        \n",
        "- Each row in a CPT contains the conditional probability of each RV in a **conditioning case** (combination of values of each RV)       \n",
        "- A CPT for a Boolean variable with $k$ parents contains $2^k$ rows        \n",
        "\n",
        "\n",
        "**Inference by Enumeration**: \n",
        "- Evidence Variables: $E_1, \\ldots E_k = e_1, \\ldots e_k$     \n",
        "- Query variable: $Q$ (Variables whose value we wish to know)\n",
        "- Hidden variables $H_1, \\ldots H_r$ (variables we don't care about)\n",
        "\n",
        "$$P(Q, e_1, \\ldots, e_k) = \\cfrac{1}{Z} \\displaystyle \\sum_{h_1, \\ldots, h_r} P(Q, h_1, \\ldots h_r, e_1, \\ldots, e_r)$$     \n",
        "$$where ~Z = \\displaystyle \\sum_{q \\in Val(Q)} P(Q, e_1, \\ldots, e_k)$$         \n",
        "(i.e. the normalization factor $Z$ is the sum of the joint probabilities over all possible values of $Q$ -- need to sum as we don't know the value of $Q$ a priori)\n",
        "\n",
        "1.) Find all entries in the conditional probability table containing the values $e_1, \\ldots, e_k$ for the evidence variables $E_1, \\ldots, E_k$         \n",
        "2.) Sum over the outcomes of hidden variables $h_1, \\ldots, h_r$        \n",
        "3.) Normalize by Z\n",
        "\n",
        "- Cons: Inference by Enumeration is slow, takes $O(2^n)$ time for $n$ Boolean variables           \n",
        "(need to join the whole joint distribution before summing out hidden variables)          \n",
        "- Improvement: Use **Variable Elimination** (NP-Hard)         \n",
        "\n",
        "**Variable Elimination** \n",
        "- Improvement on Inference by Enumeration                 \n",
        "- Interleave joining and marginalizing          \n",
        "- Dynamic programming:  Store intermediate results, and for each variable, only sum over portions of the expression that depend on the variable        \n",
        "\n",
        "**Bayes' Nets (BN)**             \n",
        "Bayes' Nets are DAGs where:     \n",
        "- Each RV corresponds to a node\n",
        "- Each node $X_i$ comes with a probability distribution $P(X_i | Parents(X_i))$ (CPT which quantifies how the values of $X_i$'s parents affect $X_i$)          \n",
        "- Intuition: An edge $X \\longrightarrow Y$ means that $X$ has a *direct influence* on $Y$         \n",
        "- Acutally: Graph topology encodes conditional independence: $P(X_i ~| ~X_1,  \\ldots, X_{i - 1}) = P(X_i ~| ~parents(X_i))\n",
        "- Each variable in a BN is conditionally independent of its non-descendants, including its parents     \n",
        "- Each variable in a BN is conditionally indepndent of all other nodes in the BN, given its parents, children and children's parents               \n",
        "(i.e. given its **Markov Blanket**)              \n",
        "\n",
        "- To see what probability a BN gives to a full assignment of values to RVs $X_1, \\ldots, X_n$, multiply the relevant conditionals:       \n",
        "$$P(X_1, \\ldots, X_n) = \\prod_{i = 1}^n P(X_i ~| ~parents(X_i))$$             \n",
        "- **Not every Bayes' Net can represent every joint distribution** (graph topology enforces certain conditional probabilities)            \n",
        "- BN with no edges (n isolated nodes): $n$ absolutely independent RVs      \n",
        "\n",
        "**Constructing a BN**        \n",
        "1.) Rewrite joint distribution in terms of conditional probabilities using chain rule       \n",
        "$$P(X_1, \\ldots, X_n) = \\prod_{i = 1}^n P(X_i ~| ~X_1, \\ldots, X_{i - 1})$$                \n",
        "2.) Label nodes in topological order, i.e. choose a minimal set of parents for each $X_i$ s.t. $Parents(X_i) \\subseteq \\{X_1, \\ldots, X_{i - 1}\\}$     \n",
        "3.) For each $X_i$, write down the CPT $P(X_i ~| ~Parents(X_i))$          \n",
        "\n",
        "**Locally Structured / Sparse systems** (BNs being one such example)          \n",
        "- Each subcomponent interacts with a bounded no. of other components        \n",
        "- **Linear** growth in complexity        \n",
        "- In a BN with $n$ nodes, each node has at most $k$ parents for some sufficiently $k$       \n",
        "- If all $n$ RVs are Boolean variables, then the CPT for each node will have at most $2^n$ entries\n",
        "- A BN with $n$ Boolean variables has size $O(n * 2^{k + 1})$ (*linear* with respect to $n$)       \n",
        "(the $2^{k + 1}$ term is because we need to consider value assignments for the current node in addition to the parents' values) \n",
        "\n",
        "\n",
        "**D-Separation Algorithm** (Gives conditional indendence guarantees from the graph alone)                                 \n",
        "- Goal: Is $X_i$ conditionally independent of $X_j$ given a set of variables $\\{X_{k_1}, \\ldots, X_{k_n}\\}$ ?          \n",
        "(i.e. is $X_i \\perp \\!\\!\\! \\perp X_j | \\{X_{k_1}, \\ldots, X_{k_n}\\} ? $  )                \n",
        "\n",
        "1.) Consider the **ancestral subgraph** of $X_i, X_j, \\{X_{k_1}, \\ldots, X_{k_n}\\}$ and their ancestors            \n",
        "2.) Construct the **moral graph** by adding links between any unlinked pair of nodes that share a common child         \n",
        "3.) Replace all directed edges by undirected edges       \n",
        "4.) If $Z = \\{X_{k_1}, \\ldots, X_{k_n}\\}$ blocks all paths between $X_i$ and $X_j$ in the resultant graph, i.e. $Z$ **d-separates** $X_i$ and $X_j$,         \n",
        "then $X_i$ is conditionally independent of $X_j$ given $Z$              \n",
        "Otherwise, $X_i$ is *not* conditionally independent of $X_j$ given $Z$     \n",
        "\n",
        "Alternative for 4.)      \n",
        "- Check all undirected paths between $X_i$ and $X_j$       \n",
        "- If all such paths are inactive, then $X_i$ is conditionally independent of $X_j$ given $Z$         \n",
        "- Otherwise, if there is at least one active path, then $X_i$ is *not* conditionally independent of $X_j$ given $Z$         \n",
        "\n",
        "**Active / Inactive paths** (see paper notes)             \n",
        "- Types of active triples:      \n",
        "- **Casual Chain**: A -> B -> C where B is unobserved     \n",
        "- **Common Cause**: A <- B -> C where B is unobserved (here B is the common cause of A and B)        \n",
        "- **Common Effect (V-Structure)** A -> B <- C where B or one of its descendents is observed           \n",
        "- A path is active if each triple of contiguous nodes in the path is active          \n",
        "- A single inactive triple can block a path      \n",
        "\n",
        "**Implications of D-Separation for Structure of BNs**          \n",
        "- Given a BN, we can run D-Separation to build a list of conditional independences that are true and of the form  $X_i \\perp \\!\\!\\! \\perp X_j | \\{X_{k_1}, \\ldots, X_{k_n}\\}$      \n",
        "- This list determines the set of probability distributions that can be represented             \n",
        "\n",
        "**Singly-Connected Networks / Polytrees**\n",
        "- At most one undirected path between any pair of nodes in the network       \n",
        "- Inference by Elimination has **linear** time/space complexity (linear in the size of the CPT for the network)      \n",
        "- Size of CPT = no. of entries in CPT     \n",
        "- Use clustering algorithms / **join tree algorithms** to join individual nodes into cluster nodes (**meganodes**) and form a polytree\n",
        "(eg. Boolean nodes X and Y are joined to form a node **X + Y**, which has $2^2 = 4$ possible values)                         \n",
        "\n",
        "**Multiply-Connected networks** \n",
        "- Multiple undirected paths between any pair of nodes        \n",
        "- Inference by Elimination has **expoenential** time/space complexity (exponential in the size of the CPT)         \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Deterministic node\": \"Value specified *exactly* by its parents' values\",\n",
        "\"Context-Specific Independence (CSI)\" : \"A RV is conditionally independent of some of its parents given *certain values* of other RVs\",   \n",
        "\"Noisy-OR relation\": \"A is true $\\Longleftrightarrow$ B, C or D are true\",\n",
        "\"Hybrid Bayesian Network\": \"Bayesian Network with both discrete and continuous RVs\"\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "2002d136-eeaf-44ce-a834-7de80f36eb37"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n 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\n\n\n**Independent RVs**: $$A \\perp \\!\\!\\! \\perp B \\Longleftrightarrow P(A, B) = P(A)P(B)$$\n**Conditional Independence**: X is independent of Y given Z $$(X \\perp \\!\\!\\! \\perp Y) | Z \\Longleftrightarrow P(X, Y | Z) = P(X|Z)P(Y|Z)$$               \n$$(X \\perp \\!\\!\\! \\perp Y) | Z \\Longleftrightarrow P(Y|X, Z) = P(Y | Z)$$           \n(eg. Umbrella is conditionally independent of Traffic given Rain)          \n- Conditional probability table (CPT) for $n$ independent RVs grows by $O(2^n)$\n- CPT for $n$ conditionally independent RVs grows by $O(n)$               \n- Conditional independence allows probabilistic systems to scale up    \n\n\n**Conditional probability tables (CPTs)**\n- For discrete RVs only       \n- Each row in a CPT must sum to 1        \n- Each row in a CPT contains the conditional probability of each RV in a **conditioning case** (combination of values of each RV)       \n- A CPT for a Boolean variable with $k$ parents contains $2^k$ rows        \n\n\n**Inference by Enumeration**: \n- Evidence Variables: $E_1, \\ldots E_k = e_1, \\ldots e_k$     \n- Query variable: $Q$ (Variables whose value we wish to know)\n- Hidden variables $H_1, \\ldots H_r$ (variables we don't care about)\n\n$$P(Q, e_1, \\ldots, e_k) = \\cfrac{1}{Z} \\displaystyle \\sum_{h_1, \\ldots, h_r} P(Q, h_1, \\ldots h_r, e_1, \\ldots, e_r)$$     \n$$where ~Z = \\displaystyle \\sum_{q \\in Val(Q)} P(Q, e_1, \\ldots, e_k)$$         \n(i.e. the normalization factor $Z$ is the sum of the joint probabilities over all possible values of $Q$ -- need to sum as we don't know the value of $Q$ a priori)\n\n1.) Find all entries in the conditional probability table containing the values $e_1, \\ldots, e_k$ for the evidence variables $E_1, \\ldots, E_k$         \n2.) Sum over the outcomes of hidden variables $h_1, \\ldots, h_r$        \n3.) Normalize by Z\n\n- Cons: Inference by Enumeration is slow, takes $O(2^n)$ time for $n$ Boolean variables           \n(need to join the whole joint distribution before summing out hidden variables)          \n- Improvement: Use **Variable Elimination** (NP-Hard)         \n\n**Variable Elimination** \n- Improvement on Inference by Enumeration                 \n- Interleave joining and marginalizing          \n- Dynamic programming:  Store intermediate results, and for each variable, only sum over portions of the expression that depend on the variable        \n\n**Bayes' Nets (BN)**             \nBayes' Nets are DAGs where:     \n- Each RV corresponds to a node\n- Each node $X_i$ comes with a probability distribution $P(X_i | Parents(X_i))$ (CPT which quantifies how the values of $X_i$'s parents affect $X_i$)          \n- Intuition: An edge $X \\longrightarrow Y$ means that $X$ has a *direct influence* on $Y$         \n- Acutally: Graph topology encodes conditional independence: $P(X_i ~| ~X_1,  \\ldots, X_{i - 1}) = P(X_i ~| ~parents(X_i))\n- Each variable in a BN is conditionally independent of its non-descendants, including its parents     \n- Each variable in a BN is conditionally indepndent of all other nodes in the BN, given its parents, children and children's parents               \n(i.e. given its **Markov Blanket**)              \n\n- To see what probability a BN gives to a full assignment of values to RVs $X_1, \\ldots, X_n$, multiply the relevant conditionals:       \n$$P(X_1, \\ldots, X_n) = \\prod_{i = 1}^n P(X_i ~| ~parents(X_i))$$             \n- **Not every Bayes' Net can represent every joint distribution** (graph topology enforces certain conditional probabilities)            \n- BN with no edges (n isolated nodes): $n$ absolutely independent RVs      \n\n**Constructing a BN**        \n1.) Rewrite joint distribution in terms of conditional probabilities using chain rule       \n$$P(X_1, \\ldots, X_n) = \\prod_{i = 1}^n P(X_i ~| ~X_1, \\ldots, X_{i - 1})$$                \n2.) Label nodes in topological order, i.e. choose a minimal set of parents for each $X_i$ s.t. $Parents(X_i) \\subseteq \\{X_1, \\ldots, X_{i - 1}\\}$     \n3.) For each $X_i$, write down the CPT $P(X_i ~| ~Parents(X_i))$          \n\n**Locally Structured / Sparse systems** (BNs being one such example)          \n- Each subcomponent interacts with a bounded no. of other components        \n- **Linear** growth in complexity        \n- In a BN with $n$ nodes, each node has at most $k$ parents for some sufficiently $k$       \n- If all $n$ RVs are Boolean variables, then the CPT for each node will have at most $2^n$ entries\n- A BN with $n$ Boolean variables has size $O(n * 2^{k + 1})$ (*linear* with respect to $n$)       \n(the $2^{k + 1}$ term is because we need to consider value assignments for the current node in addition to the parents' values) \n\n\n**D-Separation Algorithm** (Gives conditional indendence guarantees from the graph alone)                                 \n- Goal: Is $X_i$ conditionally independent of $X_j$ given a set of variables $\\{X_{k_1}, \\ldots, X_{k_n}\\}$ ?          \n(i.e. is $X_i \\perp \\!\\!\\! \\perp X_j | \\{X_{k_1}, \\ldots, X_{k_n}\\} ? $  )                \n\n1.) Consider the **ancestral subgraph** of $X_i, X_j, \\{X_{k_1}, \\ldots, X_{k_n}\\}$ and their ancestors            \n2.) Construct the **moral graph** by adding links between any unlinked pair of nodes that share a common child         \n3.) Replace all directed edges by undirected edges       \n4.) If $Z = \\{X_{k_1}, \\ldots, X_{k_n}\\}$ blocks all paths between $X_i$ and $X_j$ in the resultant graph, i.e. $Z$ **d-separates** $X_i$ and $X_j$,         \nthen $X_i$ is conditionally independent of $X_j$ given $Z$              \nOtherwise, $X_i$ is *not* conditionally independent of $X_j$ given $Z$     \n\nAlternative for 4.)      \n- Check all undirected paths between $X_i$ and $X_j$       \n- If all such paths are inactive, then $X_i$ is conditionally independent of $X_j$ given $Z$         \n- Otherwise, if there is at least one active path, then $X_i$ is *not* conditionally independent of $X_j$ given $Z$         \n\n**Active / Inactive paths** (see paper notes)             \n- Types of active triples:      \n- **Casual Chain**: A -> B -> C where B is unobserved     \n- **Common Cause**: A <- B -> C where B is unobserved (here B is the common cause of A and B)        \n- **Common Effect (V-Structure)** A -> B <- C where B or one of its descendents is observed           \n- A path is active if each triple of contiguous nodes in the path is active          \n- A single inactive triple can block a path      \n\n**Implications of D-Separation for Structure of BNs**          \n- Given a BN, we can run D-Separation to build a list of conditional independences that are true and of the form  $X_i \\perp \\!\\!\\! \\perp X_j | \\{X_{k_1}, \\ldots, X_{k_n}\\}$      \n- This list determines the set of probability distributions that can be represented             \n\n**Singly-Connected Networks / Polytrees**\n- At most one undirected path between any pair of nodes in the network       \n- Inference by Elimination has **linear** time/space complexity (linear in the size of the CPT for the network)      \n- Size of CPT = no. of entries in CPT     \n- Use clustering algorithms / **join tree algorithms** to join individual nodes into cluster nodes (**meganodes**) and form a polytree\n(eg. Boolean nodes X and Y are joined to form a node **X + Y**, which has $2^2 = 4$ possible values)                         \n\n**Multiply-Connected networks** \n- Multiple undirected paths between any pair of nodes        \n- Inference by Elimination has **expoenential** time/space complexity (exponential in the size of the CPT)         \n\n\n\n## Module 11 Definitions\n* **Deterministic node** - Value specified *exactly* by its parents' values\n* **Context-specific independence (csi)** - A RV is conditionally independent of some of its parents given *certain values* of other RVs\n* **Noisy-or relation** - A is true $\\Longleftrightarrow$ B, C or D are true\n* **Hybrid bayesian network** - Bayesian Network with both discrete and continuous RVs\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "\n",
        "- **Classification**: output is from a finite set of values      \n",
        "- **Regresion**: output is a number          \n",
        "- **Supervised Learning**: Agent observes pairs of the form (input, output) and learns a function that maps input to output,       \n",
        "and predicts a **label** for new inputs        \n",
        "- **Unsupervised Learning**: Learns patterns in the input without any explicit feedback (eg. clustering)            \n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\"\n",
        "**Tuning ML models**\n",
        "- Learn parameters (eg. model probabilities) on **training set**      \n",
        "- Train hyperparameters on **held-out** set      \n",
        "- Use **validation set** to evaluate candidate models and pick the best ones      \n",
        "- Use **test set** to final unbiased evaluation         \n",
        "\n",
        "**Leave-One-Out Cross Validation (LOOCV)**: k-fold Cross Validation with $k = n$\n",
        "\"\"\"\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 = \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\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",
        "\n",
        "**Naive Bayes Classifiers**     \n",
        "- Class label $Y$\n",
        "- Features $F_1, \\ldots, F_n$ (evidence variables)   \n",
        "$$P(Y, F_1, \\ldots, F_n) = P(Y)\\prod_{i}P(F_i | Y)$$                    \n",
        "- **Parameters** (denoted by $\\theta$): the prior probability $P(Y)$ and the posterior probabilities $P(F_i | Y)$          \n",
        "\n",
        "**Parameter Estimation**\n",
        "1. **Maximum likelihood estimate**: compute relative frequencies from training data (maximises likelihood of data) \n",
        "$$P_{ML}(x) = \\cfrac{count(x)}{total samples}$$                  \n",
        "2. **Linear Interpolation**\n",
        "$$P_{LIN}(X | Y) = \\alpha \\hat{P}(X | Y) + (1 - \\alpha)\\hat{P}(X)$$\n",
        "- Need to first get empirical P(X) and P(X|Y) from data   \n",
        "\n",
        "**Generalization / Overfitting** \n",
        "- Relative frequency parameters will overfit the training data! (Unable to generalize)            \n",
        "- Need to use smoothing / regularization to avoid overfitting!              \n",
        "\n",
        "**Naive Bayes for Text**           \n",
        "- Iterate through word positions and consider $W_i$, the word at position $i$ in the text:            \n",
        "- Use a bag of words (words allowed to repeat -- insensitive to word ordering)              \n",
        "- Assume all $W_i$ are identially distributed and independent (iid),       \n",
        "i.e. each position shares the same conditional probability $P(W_i | Y)$               \n",
        "- Goal: Predict labels                \n",
        "$$P(Y, W_1, \\ldots, W_n) = P(Y) \\displaystyle \\prod_{i = 1}^n P(W_i | Y)$$        \n",
        "$$Y_{NB} = argmax_{y \\in Y} P(Y) \\displaystyle \\prod_{i = 1}^n P(W_i | Y)$$        \n",
        "       \n",
        "- Assumes that the features $F_1, \\ldots, F_n$ are conditionally independent given $Y$          \n",
        "- Assumes words appear independently in documents (keeps track only of the frequency of words)         \n",
        "- In practice, calculations done in log space to avoid numeric underflow:       \n",
        "$$C_{NB} =  \\displaystyle argmax_{c \\in C} log(P(C)) + \\sum_{i \\in positions} P(F_i | Y)$$\n",
        "\n",
        "\n",
        "**Perceptrons**\n",
        "- Data is **separable** holds if some parameters get training set perfectly correct      \n",
        "- If data isn't **separable**, weights meight thrash\n",
        "- **Averaged perceptron**: average weight vectors over time            \n",
        "- **mediocre generalization**: Barely separable solution is found          \n",
        "- If training data is separable, binary perceptrons will eventually converge       \n",
        "- **Mistake bound**: maximum no. of mistakes    \n",
        "\n",
        "**Fixing Perceptrons**\n",
        "- **Adjust weight update**: MIRA chooses an udpate size for w that fixes the current mistake       \n",
        "- Cap maximum possible update size        \n",
        "\n",
        "|            **Naive Bayes**           | **Perceptrons / MIRA**                |\n",
        "|:--------------------------------:|-----------------------------------|\n",
        "| Builds a model training data     | Makes less assumptions about data |\n",
        "| Gives prediction probabilities   | Mistake-driven learning           |\n",
        "| Assumes independence of features | Multiple passes through data      |\n",
        "| One pass through data            | More accurate                     |\n",
        "\n",
        "\n",
        "- We can use perceptron networks to compute any logical function      \n",
        "- A single neural unit can't be used to compute XOR      \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"Training Data\": \"\",\n",
        "\"Held-out Data\" : \"Subset of data used for tuning hyperparameters\",  \n",
        "\"Stationarity\": \"Assumption that the future is like the past\"  \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b6bf29e1-b104-4e19-d8a0-2c8dff74cd03"
      },
      "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 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection & Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.5 Theory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 Linear Regression & Classification\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n\n\n- **Classification**: output is from a finite set of values      \n- **Regresion**: output is a number          \n- **Supervised Learning**: Agent observes pairs of the form (input, output) and learns a function that maps input to output,       \nand predicts a **label** for new inputs        \n- **Unsupervised Learning**: Learns patterns in the input without any explicit feedback (eg. clustering)            \n\n\n\n\n\n## AIMA Chapter 19.2 Supervised Learning\n\n**Tuning ML models**\n- Learn parameters (eg. model probabilities) on **training set**      \n- Train hyperparameters on **held-out** set      \n- Use **validation set** to evaluate candidate models and pick the best ones      \n- Use **test set** to final unbiased evaluation         \n\n**Leave-One-Out Cross Validation (LOOCV)**: k-fold Cross Validation with $k = n$\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n Your summary here \n\n## AIMA Chapter 19.4 Model Selection & Optimization\n Your summary here \n\n## AIMA Chapter 16.5 Theory of Learning\n Your summary here \n\n## AIMA Chapter 19.6 Linear Regression & Classification\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\n\n\n\n\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\n\n**Naive Bayes Classifiers**     \n- Class label $Y$\n- Features $F_1, \\ldots, F_n$ (evidence variables)   \n$$P(Y, F_1, \\ldots, F_n) = P(Y)\\prod_{i}P(F_i | Y)$$                    \n- **Parameters** (denoted by $\theta$): the prior probability $P(Y)$ and the posterior probabilities $P(F_i | Y)$          \n\n**Parameter Estimation**\n1. **Maximum likelihood estimate**: compute relative frequencies from training data (maximises likelihood of data) \n$$P_{ML}(x) = \\cfrac{count(x)}{total samples}$$                  \n2. **Linear Interpolation**\n$$P_{LIN}(X | Y) = \u0007lpha \\hat{P}(X | Y) + (1 - \u0007lpha)\\hat{P}(X)$$\n- Need to first get empirical P(X) and P(X|Y) from data   \n\n**Generalization / Overfitting** \n- Relative frequency parameters will overfit the training data! (Unable to generalize)            \n- Need to use smoothing / regularization to avoid overfitting!              \n\n**Naive Bayes for Text**           \n- Iterate through word positions and consider $W_i$, the word at position $i$ in the text:            \n- Use a bag of words (words allowed to repeat -- insensitive to word ordering)              \n- Assume all $W_i$ are identially distributed and independent (iid),       \ni.e. each position shares the same conditional probability $P(W_i | Y)$               \n- Goal: Predict labels                \n$$P(Y, W_1, \\ldots, W_n) = P(Y) \\displaystyle \\prod_{i = 1}^n P(W_i | Y)$$        \n$$Y_{NB} = argmax_{y \\in Y} P(Y) \\displaystyle \\prod_{i = 1}^n P(W_i | Y)$$        \n       \n- Assumes that the features $F_1, \\ldots, F_n$ are conditionally independent given $Y$          \n- Assumes words appear independently in documents (keeps track only of the frequency of words)         \n- In practice, calculations done in log space to avoid numeric underflow:       \n$$C_{NB} =  \\displaystyle argmax_{c \\in C} log(P(C)) + \\sum_{i \\in positions} P(F_i | Y)$$\n\n\n**Perceptrons**\n- Data is **separable** holds if some parameters get training set perfectly correct      \n- If data isn't **separable**, weights meight thrash\n- **Averaged perceptron**: average weight vectors over time            \n- **mediocre generalization**: Barely separable solution is found          \n- If training data is separable, binary perceptrons will eventually converge       \n- **Mistake bound**: maximum no. of mistakes    \n\n**Fixing Perceptrons**\n- **Adjust weight update**: MIRA chooses an udpate size for w that fixes the current mistake       \n- Cap maximum possible update size        \n\n|            **Naive Bayes**           | **Perceptrons / MIRA**                |\n|:--------------------------------:|-----------------------------------|\n| Builds a model training data     | Makes less assumptions about data |\n| Gives prediction probabilities   | Mistake-driven learning           |\n| Assumes independence of features | Multiple passes through data      |\n| One pass through data            | More accurate                     |\n\n\n- We can use perceptron networks to compute any logical function      \n- A single neural unit can't be used to compute XOR      \n\n\n## Module 12 Definitions\n* **Training data** - \n* **Held-out data** - Subset of data used for tuning hyperparameters\n* **Stationarity** - Assumption that the future is like the past\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"\n",
        "** ML Classifier Components**\n",
        "1.) Feature representation of input      \n",
        "2.) Classification function which computes the estimated class $\\hat{y}$ via the probability $P(y | x)$       \n",
        "3.) Objective function for learning (minimize error on training examples)     \n",
        "4.) Algorithm for optimising objective function            \n",
        "\n",
        "**Logistic Regression**\n",
        "- Learns a vector of **weights** and a **bias term**\n",
        "- Learns $z = w \\cdot x + b$, where $x$ is a feature vector, and $b$ is the bias term        \n",
        "(z is a weight sum of the evidence for the class)              \n",
        "- Turn z into a probability by feeding it into the **sigmoid / logistic function**         \n",
        "\n",
        "**Cross-Entropy Loss Function**       \n",
        "- $L(\\hat{y}, y)$ = how much the classifier output $\\hat{y}$ differs from the correct output $y$        \n",
        "\n",
        "**Gradient Descent**\n",
        "- Finds the minimum of loss function by figuring out which direction (in space of parameters $\\theta$) the loss function's gradient increases most steeply, and \n",
        "then moves in the opposite direction          \n",
        "- **Convex unctions**: only has one minimum (no local minima) -- logistic function is one of them        \n",
        "\n",
        "\n",
        "**Softmax / Multinomial logistic regression**: \n",
        "- Takes in a vector and outputs a vector of values normalized into probabilities       \n",
        "\n",
        "**Neural networks**\n",
        "- Sigmoid neurons have a smooth activiation function      \n",
        "- Can choose small changes in weights/biases to achieve any desired small change in output      \n",
        "- Commonly used non-linear activation functions: sigmoid, tanh, ReLU      \n",
        "\n",
        "\n",
        "**Feed-forward Neural Network**\n",
        "- Multilayer network    \n",
        "- All units typically **fully-connected**\n",
        "- No cycles    \n",
        "\n",
        "**Computation Graphs**\n",
        "- Uses chain rule from calculus       \n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ec835a4e-0f5d-4466-e0a4-863db27a8089"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n** ML Classifier Components**\n1.) Feature representation of input      \n2.) Classification function which computes the estimated class $\\hat{y}$ via the probability $P(y | x)$       \n3.) Objective function for learning (minimize error on training examples)     \n4.) Algorithm for optimising objective function            \n\n**Logistic Regression**\n- Learns a vector of **weights** and a **bias term**\n- Learns $z = w \\cdot x + b$, where $x$ is a feature vector, and $b$ is the bias term        \n(z is a weight sum of the evidence for the class)              \n- Turn z into a probability by feeding it into the **sigmoid / logistic function**         \n\n**Cross-Entropy Loss Function**       \n- $L(\\hat{y}, y)$ = how much the classifier output $\\hat{y}$ differs from the correct output $y$        \n\n**Gradient Descent**\n- Finds the minimum of loss function by figuring out which direction (in space of parameters $\theta$) the loss function's gradient increases most steeply, and \nthen moves in the opposite direction          \n- **Convex unctions**: only has one minimum (no local minima) -- logistic function is one of them        \n\n\n**Softmax / Multinomial logistic regression**: \n- Takes in a vector and outputs a vector of values normalized into probabilities       \n\n**Neural networks**\n- Sigmoid neurons have a smooth activiation function      \n- Can choose small changes in weights/biases to achieve any desired small change in output      \n- Commonly used non-linear activation functions: sigmoid, tanh, ReLU      \n\n\n**Feed-forward Neural Network**\n- Multilayer network    \n- All units typically **fully-connected**\n- No cycles    \n\n**Computation Graphs**\n- Uses chain rule from calculus       \n\n\n\n\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 Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "**Neural Network Language Models (NN LMs)**         \n",
        "\n",
        "Input: k-gram of words $w_{1:k}$\n",
        "Output: Probability distribution over the next word         \n",
        "1. Associate each word with a vector representation (an **embedding vector**)   \n",
        "2. Express joint probability function of a word sequence in terms of the word vectors for those words       \n",
        "3. Learn word vectors and parameters of the function      \n",
        "- Probability function expressed using a **multi-layer, feed-forward neural network**         \n",
        "\n",
        "Advantages:     \n",
        "- Better perplexity scores than regular n-gram LMs      \n",
        "- NN LMs can scale to large orders of words (parameters associated only with individual words, not n-grams)          \n",
        "- NN LMs can generalize across context          \n",
        "\n",
        "\n",
        "**Word2Vec**\n",
        "- Learn dense embeddings for words in training corpus while predicitng words\n",
        "- Train classifier to predict neighboring words in a context window of 2C surrounding words      \n",
        "- Idea: Instead of counting how often each word $w$ occurs near a target word, train a classifer which predicts whether $w$ is likely to show up near the target word       \n",
        "- Take the learned classifer weights as the word embeddings       \n",
        "\n",
        "**Skip-Gram Algorithm**\n",
        "1. Treat target word & neighboring context word (within a given context window) as positive examples        \n",
        "2. Randomly sample other words in lexicon to get negative samples          \n",
        "3. Use logistic regression to train classifer (gradient descent)               \n",
        "4. Use weights as embeddings        \n",
        "\n",
        "- Word vectors can be used to solve analogies\n",
        "- Embeddings reflect cultural biases\n",
        "\n",
        "\n",
        "\n",
        "**Sparse vs dense vectors**     \n",
        "- Dense vectors have many non-zero entries        \n",
        "- Short vectors easier to use as features in ML (need to tune fewer weights)     \n",
        "- Dense vectors generalize better than storing explicit counts          \n",
        "- Short, dense vectors do better at capturing synonymy            \n",
        "\n",
        "\n",
        "\n",
        "\n",
        "Advantages:     \n",
        "- Fast, easy to train\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "730298d4-7460-486c-8050-27b762727d10"
      },
      "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 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n\n- Vector semantics and embeddings                   \n- **Distributional hypothesis**: link between similarity in how words are distributed and similarity in what they mean – synonyms tend to occur in the same environment\n- **Embeddings**: representations of meaning of words                   \n- -can be static or dynamic                   \n- Lexical semantics                   \n- **Lemma/citation form**: the form of a word (eg. sing is lemma for sing, sang, sung, its wordforms)                   \n- **Synonymy**: one word has a sense whose meaning is identical to a sense of another word, or nearly identical                   \n- Same propositional meaning if two words are substitutable for one another in any sentence without changing the truth conditions of the sentence                   \n- **Word similarity**: similar in terms of semantics/meaning (eg. cat related to dog)                   \n- **Word relatedness**: associations (eg. coffee related to cup)                   \n- **semantic field**: a set of words which cover a particular semantic domain and bear structured relations with each other (eg. domain of restaurant: food, chef, waiter)                   \n- **Semantic frame**: set of words that denote perspectives or participants in a particular type of event                   \n- **Sentiment**: Positive or negative evaluation language                   \n- Words vary along three dimensions of affective meaning:                   \n- **-valence**: the pleasantness of the stimulus                   \n- **-arousal**: the intensity of emotion provoked by the stimulus                   \n- **-dominance**: the degree of control exerted by the stimulus                   \n- **Vector semantics**: standard way to represent word                   \n- -can be dense or sparse                   \n- **Term-document matrix**: each row represents a word in the vocabulary, each column represents a document from some collection of documents                   \n- **Term-term / Term-context matrix**:  columns are labeled by words rather word-word matrix than documents                   \n- Cosine can measure similarity  (normalized dot product)                   \n- **Tf-idf weighting**: term frequency (in each document) * inverse document frequency (of each term)    \n- Use TF-IDF to transform word vectors\n\n- Pointwise mutual information: how often two events x and y occur, compared with what we would expect if they were independent                \n- -bias toward infrequent events                   \n- **first-order co-occurrence**: words that are typically nearby each other.                    \n- **second-order co-occurrence**: similar second-order co-occurrence neighbors                   \n\n**Neural Network Language Models (NN LMs)**         \n\nInput: k-gram of words $w_{1:k}$\nOutput: Probability distribution over the next word         \n1. Associate each word with a vector representation (an **embedding vector**)   \n2. Express joint probability function of a word sequence in terms of the word vectors for those words       \n3. Learn word vectors and parameters of the function      \n- Probability function expressed using a **multi-layer, feed-forward neural network**         \n\nAdvantages:     \n- Better perplexity scores than regular n-gram LMs      \n- NN LMs can scale to large orders of words (parameters associated only with individual words, not n-grams)          \n- NN LMs can generalize across context          \n\n\n**Word2Vec**\n- Learn dense embeddings for words in training corpus while predicitng words\n- Train classifier to predict neighboring words in a context window of 2C surrounding words      \n- Idea: Instead of counting how often each word $w$ occurs near a target word, train a classifer which predicts whether $w$ is likely to show up near the target word       \n- Take the learned classifer weights as the word embeddings       \n\n**Skip-Gram Algorithm**\n1. Treat target word & neighboring context word (within a given context window) as positive examples        \n2. Randomly sample other words in lexicon to get negative samples          \n3. Use logistic regression to train classifer (gradient descent)               \n4. Use weights as embeddings        \n\n- Word vectors can be used to solve analogies\n- Embeddings reflect cultural biases\n\n\n\n**Sparse vs dense vectors**     \n- Dense vectors have many non-zero entries        \n- Short vectors easier to use as features in ML (need to tune fewer weights)     \n- Dense vectors generalize better than storing explicit counts          \n- Short, dense vectors do better at capturing synonymy            \n\n\n\n\nAdvantages:     \n- Fast, easy to train\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": "98f09ffb-e1e8-4f6c-8478-583cf278b8a9"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n- **Maximum Expected Utility (MEU) Principle**: Rational agent should choose actions that maximise their expected utility\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n**Theorem**: Given any preferences satisfying the axioms of utility theory, there exists some real-valued function $U$ such that $$U(A) \\geq U(B) \\Longleftrightarrow A \\succeq B$$\n$$U([p_1, S_1; \\ldots; p_n, S_n]) = \\sum_{i = 1}^n p_iS_i$$\n\n- Positive affine transformations of the form $U'(S) = aU(S) + b$ don't change the utility function\n- If prizes are deterministic (no probability), only ordinal utility can be determined (i.e. only preferences matter, numbers don't matter)\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nFor a lottery $L = [p, \\$X; 1 - p, \\$Y]$, the **Expected Monetary Value** $EMV(L) = pX + (1 - p)Y$, with utility $U(L) = pU(\\$X) + (1 - p)U(\\$Y)$.    \nUsually, $U(L) < EMV(L)$. \n\n$\\hat{EU}(a) = $ *estimated* expected utility\n\n- **Preference elicitation**: Presenting a human with the **standard lottery** $[p, A; 1 - p, B]$ and adjusting $p$ such that preferences are indifferent \n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- A policy $\\pi$ specifies what the agent should do for any state $s$ that the agent reaches     \n- An optimal policy $\\pi^*$ = policy with the maximum expected utility\n- **Nonstationary policy**: policy that depends on time remaining      \n- **Stationary policy**: optimal action depends only on current state (no time limit)   \n\n- **Stationary preferences** on reward sequences: $$[a_1, a_2, \\ldots] > [b_1, b_2, \\ldots] \\longleftrightarrow [r, a_1, a_2, \\ldots] > [r, b_1, b_2, \\ldots]$$,\ni.e. if you prefer one future to another, you would maintain the same preference if that future were to start today\n- **Theorem**: Assuming stationary preferences, there are only 2 ways to define utilities:\n* Additive utility: $U([r_0, r_1, \\ldots]) = r_0 + r_1 + r_2 + \\ldots$      \n* Discounted utility: $U([r_0, r_1, \\ldots]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 + \\ldots$   \n\n- Dealing with infinite utilities:\n1. Finite horizon (terminate episodes after fixed no. of steps), use nonstationary policies\n2. Discounting (use $0 < \\gamma < 1$, where $\\gamma$ is the discount rate)\n* Smaller $\\gamma$ means smaller \"horizon\"\n3. Have an absorbing state (ensures that each policy reaches a terminal state)\n\n- **Shaping Theorem**: Optimal policies remain invariant under transformations of the form $$R'(S, a, s') = R(s, a, s') + \\gamma\\phi(s') - \\phi(s')$$, where $\\phi(s)$ is any function in terms of $s$\n- Call $\\phi(s)$ the *potential* function\n\n- **Dynamic Decision Network (DDN)**: factored representation of MDP (each state described in terms of features)\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- Let $V_k(s)$ = optimal value of state $s$ if game ends in $k$ more steps, i.e. what a depth-$k$ expectimax would give from $s$\n- **Value Iteration**: Apply Bellman update to each state $s$,\n- Problems with Value Iteration:      \n1. Slow, $O(S^2A)$ per iteration      \n2. Max value at each state rarely changes       \n2. Policy often converges long before the value              \n- **Policy Iteration**: Given a policy $\\pi_i$, calculate $U_i = U^{\\pi_i}$, the utility of each state if the policy $\\pi_i$ were to be executed\n- **Policy Improvement**: Calculate a new MEU policy $π_{i + 1}$ using one-step look ahead function, $O(S^2)$\n\n- Policy iteration algorithm alternates between policy evaluation & policy improvement until convergence       \n- *Modified Policy Iteration*: Fix a policy, apply a few value iteration steps to approximate utilities    \n- *Asynchronous Policy Iteration*: Pick *any* subset of states and apply policy improvement / value iteration to that subset     \n\n- MDPs can be solved in **polynomial time** wrt the no. of states and actions\n\n\n## Module 8 Lecture Notes\n\n\n- **MEU Principle (Maximum Expected Utility)**: Agents are rational if they choose the action that yields the highest expected utility\n\n\n|                         **Value Iteration**                         |                                                    **Policy Iteration**                                                   |\n|:---------------------------------------------------------------:|:---------------------------------------------------------------------------------------------------------------------:|\n| $O(S^2A)$ per iteration                                         | $O(S^2)$ per iteration                                                                                                |\n| Every iteration updates both values and (implicitly) the policy | Several passes that update utilities with fixed policy. After evaluating the policy, choose a new (improved) policy.  |\n\n\n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **(16. 3) certainty equivalent** - The value an agent accepts in place of a lottery\n* **(16.3) insurance premium** - Difference between a lottery's EMV and its certainty equivalent\n* **(16.3) unbiased esimate** - Error between estimate and actual value is 0, i.e. $E(\\hat{EU}(A) - EU(A)) = 0$\n* **(16.3) optimizer's curse** - Estimated expected utility is overly high\n* **(16.3) certainty effect** - People prefer deterministic over stochastic games\n* **(16.3) anchoring effect** - People prefer making relative utility judgements over absolute ones\n* **(17.1) proper policy** - Policy guaranteed to reach a terminal state\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- On an n-armed bandit, each arm $M_i$ is a **Markov Reward Process** (MDP w/ only one action), arms are independent\n- The overall bandit is an MDP \n\n- **Gittins Index** for an arm $M$: Maximum obtainable utility per unit of discounted time\n- Optimal policy for a bandit problem: Pull the arm w/ the highest Gittins Index, then update Gittins indices\n- **Bernoulli Bandit**: Each arm $M_i$ is a Bernoulli process with success probability $\\mu_i$ \n- **Bandit Superprocess (BSP)**: Each arm is a full MDP (multitasking)      \n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n\n**Model-Based RL**     \n- Learn a transition model (estimate $\\hat{T}(s, a, s')$) by observing rewards that are yielded when we perform actions\n- Count outsomes s' for each s and normalize to estimate $\\hat{T}(s, a, s')$\n- Solve the learned MDP as before\n\n\n**Model-Free RL**\n1.**Q-Learning**: learn a **Q-function** $Q(s, a)$, which is the sum of rewards from state $s$ onward after taking action $a$\n- After learning the Q-function, for each state s, choose the action a that has the highest Q-value\n\n2. **Policy search** (reflex agent)\n- Learn a policy $\\pi(s)$ (what action to do at each state)\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\n**Passive RL**\n- Input: fixed policy $\\pi(s)$\n- Task: Learn the utilities of states according to $\\pi(s)$ (**Policy Evaluation**)\n(agent just executes the policy, can't choose actions)\n\n**Direct Utility Estimation / Direct Evaluation**   \n- Compute values for each state under policy $\\pi$\n- Every time we visit a state, record the sum of discounted rewards, and average these samples\n|                                        Pros                                       |                      Cons                     |\n|:---------------------------------------------------------------------------------:|:---------------------------------------------:|\n| Doesn't require any knowledge of the transition or reward functions               | Need to learn each state's utility separately |\n| Sample average converges to true expectation as we perform infinitely many trials | Ignores connections between states            |\n\n\n**Adaptive Dynamic Programming**\n- Learn the transition model of the MDP and solve it (apply policy evaluation)\n\n**Temporal-Difference Learning** (see paper notes)\n- Policy fixed, still doing policy evaluation\n- Update the value V(s) every time we transition from s to s' via an action\n- The outcomes s' which are more likely will contribute more update to V(s)\n- Adjusts a state so that it agrees with its observed successor\n**Exponential Moving Average**: place greater emphasis on recent samples\n|                       Pros                      |               Cons              |\n|:-----------------------------------------------:|:-------------------------------:|\n| Converges to the true value in the limit        | Can't turn values into a policy |\n| Simple, requires less computation per iteration |                                 |\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n\n**Active Reinforcement Learning**\n- Goal: learn optimal policy / values (transition & reward function unknown)\n- Agent can **choose actions** now!\n\n- **Greedy agent**: greedily takes the action believed to be optimal at each step\n- **Exploration-Exploitation Tradeoff**: Explore unknown states to gain more information that could lead to a change in policy, or choose the best action to maximise current reward?\n- GLIE Schemes: Try each state an unbounded no. of times to avoid missing an optimal action\n\n**Q-Learning**\n- **Off-Policy**: Learns Q-values that answer the question \"what is this action worth if we stop following the current policy and start acting according to a policy that chooses the best estimated action\"\n- Need to explore enough, make learning rate small enough      \n- In the limit, it doesn't matter how actions are chosen    \n\n- Alternative: **On-Policy**: Learns Q-values that answer the question \"what is this action worth in this state if we stick with the current policy?@\n\n**$\\epsilon$-Greedy Agents**\n- With small probability $\\epsilon$, act randomly, and with probability $1 - \\epsilon$, follow current policy\n- Forces exploration\n- Pros: Explores the entire space eventually\n- Cons: Thrashes around once learning is done (solution: lower $\\epsilon$ over time)\n\n**Exploration Functions**\n- Idea: explore areas whose badness is not established and eventually stop exploring\n- Takes a value estimate u, a visit count n, and returns an optimistic utility\n$$f(u, n) = u + k/n$$\n- Note that $\\lim_{n -> \\infty} f(u, n) = u$ (converges to utility estimate in the limit)\n- When $n$ is small, $k$ dominates \n- Determines how preference for high utility values is traded off against preference for rarely-tried acions (i.e. greed vs curiosity)\n- $k$ determines how much exploration to do\n\n**Regret**: Total mistake cost (difference between actual expected rewards and optimal expected rewards)\n- Random exploration has higher regret than exploration functions  \n\n\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n\n- **Approximating direct utility estimation**: Use a supervised learning algorithm to learn weights for a linear combination of feature values\n- **Catastrophic forgetting**: Tendency to forget old information upon learning new information       \n- Solution: **Experience replay**: Replay past experiences at regular intervals to ensure accuracy of value function    \n\n\n\n\n## Module 9 Lecture Notes\n\n- Solving MDPs is offline planning -- don't need to actually play the game    \n- Reinforcement learning: Online planning, must play the game and learn to act to **maximise expected rewards**\n- All learning done through observed rewards that the agent receives\n\n- Idea behind RL: assume a MDP and looking for a policy $\\pi(s)$, but we don't know the transition model or the reward function!\n\n\n\n\n\n## Module 9 Definitions\n* **N-armed bandit** - Slot machine with n arms\n* **Sparse rewards** - Zero reward for most states\n* **Expected reward to go of a state s** - Expected total reward from state s onward\n* **Glie** - Greedy in the Limit of Infinit Exploration\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\n- Goal: Compute $P(w | h)$, probability of a word w given a history h\n- **N-gram models** allow us to **approximate** the history using the last n-1 words in the past\n- Eg. **Unigram models** have no history\n- Eg. **Bigram models** have 1 word as history\n\n- **Maximum Likelihood Estimate**: Get counts from a corpus and normalize counts between [0, 1]\n- Problems with MLE: \n1. Assigns zero probabilities to unseen n-grams (avoid zeros with smoothing)\n2. Can't deal with unknown words / out of vocabulary items (replace any word not in lexicon with <unk>)\n\n- In practice, we add log probabilities (avoids numeric underflow):\n$$log(p_1 * p_2 * p_3) = log(p_1) + log(p_2) + log(p_3)$$\n\n\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n\n\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\n- **Backoff**: If n-gram has zero counts, use n-1 gram (shorter history), and continue backing off until we reach a history that has some counts\n- **Interpolation**: Take a weighted average of all n-gram estimators (for different) n\n$$P(w_n | w_{n-2} w_{n-1}) = \\lambda_1(w_{n-2:n-1})P(w_n) + \\lambda_2(w_{n-2:n-1})P(w_n | w_{n-1}) + \\lambda_3(w_{n-2:n-1})P(w_n | w_{n-1} w_{n-2})$$\n- **Held-out corpus**: Additional corpus that we use to set hyperparameters    \n- **Katz backoff**: If we've seen this n-gram before, use a discounted probability, else recursively backoff to the Katz backoff for the shorter history n-1 gram\n\n\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n**Stupid backoff**: No discounting of probabilities for higher-order n-grams (n-grams with higher n) -> does not produce a probability distribution     \n- If an n-gram has zero count, we backoff to an n-1 gram, weighted by a fixed weight $\\lambda$      \n\n$$S(w_i | w_{i - k + 1: i - 1}) = \\cfrac{count(w_{i-k+1:i})}{count(w_{i-k+1:i-1})}  ~if  ~count(w_{i-k+1:i}) >  0$$          \n$$ S(w_i | w_{i - k + 1: i - 1}) = \\lambda S( w_{i - k + 2: i - 1}) ~otherwise$$                             \n\n- Terminates in the unigram, which has probability $S(w) = \\cfrac{count(w)}{N}$  \n\n\n\n\n\n\n## Module 10 Lecture Notes\n\n**Inclusion-Exclusion Principle**: $P(A \\cup B) = P(A) + P(B) - P(A \\cap B)$    \n**De Finetti's Theorem**: If an agent has some degree of belief in proposition $a$, they should be able to state odds at which it is indifferent to a bet for or against $a$    \n(i.e. no rational agent can have beliefs that violate probability axioms)         \n\n**Marginal Distributions** $$P(X_1) = \\sum_{x_2} P(X_1, X_2 = x_2)$$ (sum out the probabilities for the other variable's outcome)         \n**Conditional Probability**: $$P(A | B) = \\cfrac{P(A \\cap B)}{P(B)}$$                   \n**Chain Rule**: $$P(A \\cap B) = P(A | B)P(B)$$                          \n$$P(X_1, X_2, X_3) = P(X_1)P(X_2 | X_1)P(X_3 | X_1, X_2)$$             \n$$P(X_1, X_2, \\ldots, X_n) = \\prod_{i} P(X_i | X_1 \\ldots X_{i - 1})$$             \n\n**Bayes' Rule**: $$P(A | B) = \\cfrac{P(B | A)P(A)}{P(B)}$$      \nGeneral version conditionalized on background evidence $e$: $$P(Y | X, e) = \\cfrac{P(X | Y, e)P(Y | e)}{P(X | e)}$$        \n\n\n## Module 10 Definitions\n* **Markov assumption** - Probability of a word depends only on the probability of the previous word\n* **Prior** - Unconditional probability of an event $P(A)$ (our belief before new evidence is taken into account)\n* **Posterior** - The conditional Probability $P(A | B)$ (our belief after taking into account new evidence)\n* **Gold labels** - Human-defined labels\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\n\n\n**Independent RVs**: $$A \\perp \\!\\!\\! \\perp B \\Longleftrightarrow P(A, B) = P(A)P(B)$$\n**Conditional Independence**: X is independent of Y given Z $$(X \\perp \\!\\!\\! \\perp Y) | Z \\Longleftrightarrow P(X, Y | Z) = P(X|Z)P(Y|Z)$$               \n$$(X \\perp \\!\\!\\! \\perp Y) | Z \\Longleftrightarrow P(Y|X, Z) = P(Y | Z)$$           \n(eg. Umbrella is conditionally independent of Traffic given Rain)          \n- Conditional probability table (CPT) for $n$ independent RVs grows by $O(2^n)$\n- CPT for $n$ conditionally independent RVs grows by $O(n)$               \n- Conditional independence allows probabilistic systems to scale up    \n\n\n**Conditional probability tables (CPTs)**\n- For discrete RVs only       \n- Each row in a CPT must sum to 1        \n- Each row in a CPT contains the conditional probability of each RV in a **conditioning case** (combination of values of each RV)       \n- A CPT for a Boolean variable with $k$ parents contains $2^k$ rows        \n\n\n**Inference by Enumeration**: \n- Evidence Variables: $E_1, \\ldots E_k = e_1, \\ldots e_k$     \n- Query variable: $Q$ (Variables whose value we wish to know)\n- Hidden variables $H_1, \\ldots H_r$ (variables we don't care about)\n\n$$P(Q, e_1, \\ldots, e_k) = \\cfrac{1}{Z} \\displaystyle \\sum_{h_1, \\ldots, h_r} P(Q, h_1, \\ldots h_r, e_1, \\ldots, e_r)$$     \n$$where ~Z = \\displaystyle \\sum_{q \\in Val(Q)} P(Q, e_1, \\ldots, e_k)$$         \n(i.e. the normalization factor $Z$ is the sum of the joint probabilities over all possible values of $Q$ -- need to sum as we don't know the value of $Q$ a priori)\n\n1.) Find all entries in the conditional probability table containing the values $e_1, \\ldots, e_k$ for the evidence variables $E_1, \\ldots, E_k$         \n2.) Sum over the outcomes of hidden variables $h_1, \\ldots, h_r$        \n3.) Normalize by Z\n\n- Cons: Inference by Enumeration is slow, takes $O(2^n)$ time for $n$ Boolean variables           \n(need to join the whole joint distribution before summing out hidden variables)          \n- Improvement: Use **Variable Elimination** (NP-Hard)         \n\n**Variable Elimination** \n- Improvement on Inference by Enumeration                 \n- Interleave joining and marginalizing          \n- Dynamic programming:  Store intermediate results, and for each variable, only sum over portions of the expression that depend on the variable        \n\n**Bayes' Nets (BN)**             \nBayes' Nets are DAGs where:     \n- Each RV corresponds to a node\n- Each node $X_i$ comes with a probability distribution $P(X_i | Parents(X_i))$ (CPT which quantifies how the values of $X_i$'s parents affect $X_i$)          \n- Intuition: An edge $X \\longrightarrow Y$ means that $X$ has a *direct influence* on $Y$         \n- Acutally: Graph topology encodes conditional independence: $P(X_i ~| ~X_1,  \\ldots, X_{i - 1}) = P(X_i ~| ~parents(X_i))\n- Each variable in a BN is conditionally independent of its non-descendants, including its parents     \n- Each variable in a BN is conditionally indepndent of all other nodes in the BN, given its parents, children and children's parents               \n(i.e. given its **Markov Blanket**)              \n\n- To see what probability a BN gives to a full assignment of values to RVs $X_1, \\ldots, X_n$, multiply the relevant conditionals:       \n$$P(X_1, \\ldots, X_n) = \\prod_{i = 1}^n P(X_i ~| ~parents(X_i))$$             \n- **Not every Bayes' Net can represent every joint distribution** (graph topology enforces certain conditional probabilities)            \n- BN with no edges (n isolated nodes): $n$ absolutely independent RVs      \n\n**Constructing a BN**        \n1.) Rewrite joint distribution in terms of conditional probabilities using chain rule       \n$$P(X_1, \\ldots, X_n) = \\prod_{i = 1}^n P(X_i ~| ~X_1, \\ldots, X_{i - 1})$$                \n2.) Label nodes in topological order, i.e. choose a minimal set of parents for each $X_i$ s.t. $Parents(X_i) \\subseteq \\{X_1, \\ldots, X_{i - 1}\\}$     \n3.) For each $X_i$, write down the CPT $P(X_i ~| ~Parents(X_i))$          \n\n**Locally Structured / Sparse systems** (BNs being one such example)          \n- Each subcomponent interacts with a bounded no. of other components        \n- **Linear** growth in complexity        \n- In a BN with $n$ nodes, each node has at most $k$ parents for some sufficiently $k$       \n- If all $n$ RVs are Boolean variables, then the CPT for each node will have at most $2^n$ entries\n- A BN with $n$ Boolean variables has size $O(n * 2^{k + 1})$ (*linear* with respect to $n$)       \n(the $2^{k + 1}$ term is because we need to consider value assignments for the current node in addition to the parents' values) \n\n\n**D-Separation Algorithm** (Gives conditional indendence guarantees from the graph alone)                                 \n- Goal: Is $X_i$ conditionally independent of $X_j$ given a set of variables $\\{X_{k_1}, \\ldots, X_{k_n}\\}$ ?          \n(i.e. is $X_i \\perp \\!\\!\\! \\perp X_j | \\{X_{k_1}, \\ldots, X_{k_n}\\} ? $  )                \n\n1.) Consider the **ancestral subgraph** of $X_i, X_j, \\{X_{k_1}, \\ldots, X_{k_n}\\}$ and their ancestors            \n2.) Construct the **moral graph** by adding links between any unlinked pair of nodes that share a common child         \n3.) Replace all directed edges by undirected edges       \n4.) If $Z = \\{X_{k_1}, \\ldots, X_{k_n}\\}$ blocks all paths between $X_i$ and $X_j$ in the resultant graph, i.e. $Z$ **d-separates** $X_i$ and $X_j$,         \nthen $X_i$ is conditionally independent of $X_j$ given $Z$              \nOtherwise, $X_i$ is *not* conditionally independent of $X_j$ given $Z$     \n\nAlternative for 4.)      \n- Check all undirected paths between $X_i$ and $X_j$       \n- If all such paths are inactive, then $X_i$ is conditionally independent of $X_j$ given $Z$         \n- Otherwise, if there is at least one active path, then $X_i$ is *not* conditionally independent of $X_j$ given $Z$         \n\n**Active / Inactive paths** (see paper notes)             \n- Types of active triples:      \n- **Casual Chain**: A -> B -> C where B is unobserved     \n- **Common Cause**: A <- B -> C where B is unobserved (here B is the common cause of A and B)        \n- **Common Effect (V-Structure)** A -> B <- C where B or one of its descendents is observed           \n- A path is active if each triple of contiguous nodes in the path is active          \n- A single inactive triple can block a path      \n\n**Implications of D-Separation for Structure of BNs**          \n- Given a BN, we can run D-Separation to build a list of conditional independences that are true and of the form  $X_i \\perp \\!\\!\\! \\perp X_j | \\{X_{k_1}, \\ldots, X_{k_n}\\}$      \n- This list determines the set of probability distributions that can be represented             \n\n**Singly-Connected Networks / Polytrees**\n- At most one undirected path between any pair of nodes in the network       \n- Inference by Elimination has **linear** time/space complexity (linear in the size of the CPT for the network)      \n- Size of CPT = no. of entries in CPT     \n- Use clustering algorithms / **join tree algorithms** to join individual nodes into cluster nodes (**meganodes**) and form a polytree\n(eg. Boolean nodes X and Y are joined to form a node **X + Y**, which has $2^2 = 4$ possible values)                         \n\n**Multiply-Connected networks** \n- Multiple undirected paths between any pair of nodes        \n- Inference by Elimination has **expoenential** time/space complexity (exponential in the size of the CPT)         \n\n\n\n## Module 11 Definitions\n* **Deterministic node** - Value specified *exactly* by its parents' values\n* **Context-specific independence (csi)** - A RV is conditionally independent of some of its parents given *certain values* of other RVs\n* **Noisy-or relation** - A is true $\\Longleftrightarrow$ B, C or D are true\n* **Hybrid bayesian network** - Bayesian Network with both discrete and continuous RVs\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n\n\n- **Classification**: output is from a finite set of values      \n- **Regresion**: output is a number          \n- **Supervised Learning**: Agent observes pairs of the form (input, output) and learns a function that maps input to output,       \nand predicts a **label** for new inputs        \n- **Unsupervised Learning**: Learns patterns in the input without any explicit feedback (eg. clustering)            \n\n\n\n\n\n## AIMA Chapter 19.2 Supervised Learning\n\n**Tuning ML models**\n- Learn parameters (eg. model probabilities) on **training set**      \n- Train hyperparameters on **held-out** set      \n- Use **validation set** to evaluate candidate models and pick the best ones      \n- Use **test set** to final unbiased evaluation         \n\n**Leave-One-Out Cross Validation (LOOCV)**: k-fold Cross Validation with $k = n$\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n Your summary here \n\n## AIMA Chapter 19.4 Model Selection & Optimization\n Your summary here \n\n## AIMA Chapter 16.5 Theory of Learning\n Your summary here \n\n## AIMA Chapter 19.6 Linear Regression & Classification\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\n\n\n\n\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\n\n**Naive Bayes Classifiers**     \n- Class label $Y$\n- Features $F_1, \\ldots, F_n$ (evidence variables)   \n$$P(Y, F_1, \\ldots, F_n) = P(Y)\\prod_{i}P(F_i | Y)$$                    \n- **Parameters** (denoted by $\theta$): the prior probability $P(Y)$ and the posterior probabilities $P(F_i | Y)$          \n\n**Parameter Estimation**\n1. **Maximum likelihood estimate**: compute relative frequencies from training data (maximises likelihood of data) \n$$P_{ML}(x) = \\cfrac{count(x)}{total samples}$$                  \n2. **Linear Interpolation**\n$$P_{LIN}(X | Y) = \u0007lpha \\hat{P}(X | Y) + (1 - \u0007lpha)\\hat{P}(X)$$\n- Need to first get empirical P(X) and P(X|Y) from data   \n\n**Generalization / Overfitting** \n- Relative frequency parameters will overfit the training data! (Unable to generalize)            \n- Need to use smoothing / regularization to avoid overfitting!              \n\n**Naive Bayes for Text**           \n- Iterate through word positions and consider $W_i$, the word at position $i$ in the text:            \n- Use a bag of words (words allowed to repeat -- insensitive to word ordering)              \n- Assume all $W_i$ are identially distributed and independent (iid),       \ni.e. each position shares the same conditional probability $P(W_i | Y)$               \n- Goal: Predict labels                \n$$P(Y, W_1, \\ldots, W_n) = P(Y) \\displaystyle \\prod_{i = 1}^n P(W_i | Y)$$        \n$$Y_{NB} = argmax_{y \\in Y} P(Y) \\displaystyle \\prod_{i = 1}^n P(W_i | Y)$$        \n       \n- Assumes that the features $F_1, \\ldots, F_n$ are conditionally independent given $Y$          \n- Assumes words appear independently in documents (keeps track only of the frequency of words)         \n- In practice, calculations done in log space to avoid numeric underflow:       \n$$C_{NB} =  \\displaystyle argmax_{c \\in C} log(P(C)) + \\sum_{i \\in positions} P(F_i | Y)$$\n\n\n**Perceptrons**\n- Data is **separable** holds if some parameters get training set perfectly correct      \n- If data isn't **separable**, weights meight thrash\n- **Averaged perceptron**: average weight vectors over time            \n- **mediocre generalization**: Barely separable solution is found          \n- If training data is separable, binary perceptrons will eventually converge       \n- **Mistake bound**: maximum no. of mistakes    \n\n**Fixing Perceptrons**\n- **Adjust weight update**: MIRA chooses an udpate size for w that fixes the current mistake       \n- Cap maximum possible update size        \n\n|            **Naive Bayes**           | **Perceptrons / MIRA**                |\n|:--------------------------------:|-----------------------------------|\n| Builds a model training data     | Makes less assumptions about data |\n| Gives prediction probabilities   | Mistake-driven learning           |\n| Assumes independence of features | Multiple passes through data      |\n| One pass through data            | More accurate                     |\n\n\n- We can use perceptron networks to compute any logical function      \n- A single neural unit can't be used to compute XOR      \n\n\n## Module 12 Definitions\n* **Training data** - \n* **Held-out data** - Subset of data used for tuning hyperparameters\n* **Stationarity** - Assumption that the future is like the past\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n\n** ML Classifier Components**\n1.) Feature representation of input      \n2.) Classification function which computes the estimated class $\\hat{y}$ via the probability $P(y | x)$       \n3.) Objective function for learning (minimize error on training examples)     \n4.) Algorithm for optimising objective function            \n\n**Logistic Regression**\n- Learns a vector of **weights** and a **bias term**\n- Learns $z = w \\cdot x + b$, where $x$ is a feature vector, and $b$ is the bias term        \n(z is a weight sum of the evidence for the class)              \n- Turn z into a probability by feeding it into the **sigmoid / logistic function**         \n\n**Cross-Entropy Loss Function**       \n- $L(\\hat{y}, y)$ = how much the classifier output $\\hat{y}$ differs from the correct output $y$        \n\n**Gradient Descent**\n- Finds the minimum of loss function by figuring out which direction (in space of parameters $\theta$) the loss function's gradient increases most steeply, and \nthen moves in the opposite direction          \n- **Convex unctions**: only has one minimum (no local minima) -- logistic function is one of them        \n\n\n**Softmax / Multinomial logistic regression**: \n- Takes in a vector and outputs a vector of values normalized into probabilities       \n\n**Neural networks**\n- Sigmoid neurons have a smooth activiation function      \n- Can choose small changes in weights/biases to achieve any desired small change in output      \n- Commonly used non-linear activation functions: sigmoid, tanh, ReLU      \n\n\n**Feed-forward Neural Network**\n- Multilayer network    \n- All units typically **fully-connected**\n- No cycles    \n\n**Computation Graphs**\n- Uses chain rule from calculus       \n\n\n\n\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 Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n\n- Vector semantics and embeddings                   \n- **Distributional hypothesis**: link between similarity in how words are distributed and similarity in what they mean – synonyms tend to occur in the same environment\n- **Embeddings**: representations of meaning of words                   \n- -can be static or dynamic                   \n- Lexical semantics                   \n- **Lemma/citation form**: the form of a word (eg. sing is lemma for sing, sang, sung, its wordforms)                   \n- **Synonymy**: one word has a sense whose meaning is identical to a sense of another word, or nearly identical                   \n- Same propositional meaning if two words are substitutable for one another in any sentence without changing the truth conditions of the sentence                   \n- **Word similarity**: similar in terms of semantics/meaning (eg. cat related to dog)                   \n- **Word relatedness**: associations (eg. coffee related to cup)                   \n- **semantic field**: a set of words which cover a particular semantic domain and bear structured relations with each other (eg. domain of restaurant: food, chef, waiter)                   \n- **Semantic frame**: set of words that denote perspectives or participants in a particular type of event                   \n- **Sentiment**: Positive or negative evaluation language                   \n- Words vary along three dimensions of affective meaning:                   \n- **-valence**: the pleasantness of the stimulus                   \n- **-arousal**: the intensity of emotion provoked by the stimulus                   \n- **-dominance**: the degree of control exerted by the stimulus                   \n- **Vector semantics**: standard way to represent word                   \n- -can be dense or sparse                   \n- **Term-document matrix**: each row represents a word in the vocabulary, each column represents a document from some collection of documents                   \n- **Term-term / Term-context matrix**:  columns are labeled by words rather word-word matrix than documents                   \n- Cosine can measure similarity  (normalized dot product)                   \n- **Tf-idf weighting**: term frequency (in each document) * inverse document frequency (of each term)    \n- Use TF-IDF to transform word vectors\n\n- Pointwise mutual information: how often two events x and y occur, compared with what we would expect if they were independent                \n- -bias toward infrequent events                   \n- **first-order co-occurrence**: words that are typically nearby each other.                    \n- **second-order co-occurrence**: similar second-order co-occurrence neighbors                   \n\n**Neural Network Language Models (NN LMs)**         \n\nInput: k-gram of words $w_{1:k}$\nOutput: Probability distribution over the next word         \n1. Associate each word with a vector representation (an **embedding vector**)   \n2. Express joint probability function of a word sequence in terms of the word vectors for those words       \n3. Learn word vectors and parameters of the function      \n- Probability function expressed using a **multi-layer, feed-forward neural network**         \n\nAdvantages:     \n- Better perplexity scores than regular n-gram LMs      \n- NN LMs can scale to large orders of words (parameters associated only with individual words, not n-grams)          \n- NN LMs can generalize across context          \n\n\n**Word2Vec**\n- Learn dense embeddings for words in training corpus while predicitng words\n- Train classifier to predict neighboring words in a context window of 2C surrounding words      \n- Idea: Instead of counting how often each word $w$ occurs near a target word, train a classifer which predicts whether $w$ is likely to show up near the target word       \n- Take the learned classifer weights as the word embeddings       \n\n**Skip-Gram Algorithm**\n1. Treat target word & neighboring context word (within a given context window) as positive examples        \n2. Randomly sample other words in lexicon to get negative samples          \n3. Use logistic regression to train classifer (gradient descent)               \n4. Use weights as embeddings        \n\n- Word vectors can be used to solve analogies\n- Embeddings reflect cultural biases\n\n\n\n**Sparse vs dense vectors**     \n- Dense vectors have many non-zero entries        \n- Short vectors easier to use as features in ML (need to tune fewer weights)     \n- Dense vectors generalize better than storing explicit counts          \n- Short, dense vectors do better at capturing synonymy            \n\n\n\n\nAdvantages:     \n- Fast, easy to train\n\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}