{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm_2_notes_Shunde Tu.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": "3d2ebff5-d06d-4d3b-95f1-794dbfb62df9"
      },
      "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": 255,
      "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": "69792d24-9f79-4df7-b9e8-84bb336b0f18"
      },
      "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": 256,
      "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": "markdown",
      "source": [
        ""
      ],
      "metadata": {
        "id": "Dmm_xzE_g4bi"
      }
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 257,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Rational agent choose an action based on maximum expected utility (MEU), based on evidence e\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"\n",
        "* Orderability (must have a preference)\n",
        "* Transitivity: A>B, B>C then A>C\n",
        "* Continuity: If A>B>C, ∃ p, such that [p,A:(1-p),C] ~ B\n",
        "* Substitutability\n",
        "* Monotonicity A>B => p>q <=> [p,A: 1-p, B]>[q,A: 1-q, B]\n",
        "* Decomposability\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "* Optimizer's curse: estimated expect utility too high\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "**Stochastic Transition Model**\n",
        "* P(s' | s, a). Probability of reaching state s' from s, with action a\n",
        "\n",
        "**Markov Decision Process**\n",
        "* Sequential decision problem, fully observable, stochastic environment\n",
        "* Markovian transition model, additive rewards\n",
        "* Markovian means probability of reaching state s' from s depends only on s, not on earlier states\n",
        "\n",
        "**Policy**\n",
        "* Solution of what an agent should do for any state: π(s) for state s\n",
        "* Optimal policy: policy with highest expected utility, or π*\n",
        "\n",
        "**Finite vs. infinite horizons***\n",
        "* Finite: optimal action depends on how many times left, so policy is non-stationary (policies that depends on time)\n",
        "* Infinite: No reason to behave different in the smae state at different times, so stationary \n",
        "\n",
        "**Reward**\n",
        "* Can be additive reward\n",
        "* Or discounted rewward γ (between 0 and 1): U = R(s0)+*R(s1)+γ^2*R(s2)+...\n",
        "\"\"\"\n",
        "\n",
        "chapter17_2 =  \"\"\"\n",
        "**Bellman equation**\n",
        "* $V^*(s) = \\max\\limits_{a} Q^*(s,a)$\n",
        "* $V^*(s) = \\max\\limits_{a \\subseteq A(s)} \\sum_{s'} T(s,a,s') [R(s,a,s') + γ V^*(s')]$\n",
        "\n",
        "**Value iteration**\n",
        "* Non-linear Equations(due to max) => need an iterative appraoch\n",
        "* Start with arbitrary initial value, calculate RHS, plug into LHS - repeat until we reach equalibrium\n",
        "* Eventually converges to unique solutions\n",
        "* Policy loss: $U_{π_i}(s)$ - utility if we do $π_i$ in state s, $||U_{π_i}(s) - U||$ is policy loss (U is true utility)\n",
        "* Bellman update: $U_{i+1}(s) = \\max\\limits_{a \\subseteq A(s)} \\sum_{s'} P(s'|s,a) [R(s,a,s') + γ U_i (s')]$.\n",
        "* Slides version of Bellman update: $V_{k+1}(s) = \\max\\limits_{a} \\sum_{s'} T(s,a,s') [R(s,a,s') + γ V_k (s')]$.\n",
        "* Start with $V_0(s)=0$, repeat until convergence\n",
        "* (slides) complexity: $O(S^2 A)$ of each iteration\n",
        "\n",
        "**Policy iteration**\n",
        "* Step 1: Policy evaluation - calculate $U_{π_i}(s)$ based on policy $π_i$ (utility of each state)\n",
        "* Policy improvement: calculate new MEU policy $π_{i+1}$, with one-step look-ahead of $U_{π_i}$\n",
        "* Terminates when policy improvement yields no change in utilities\n",
        "* Slides version: $V^{\\pi}(s) = \\sum_{s'} T(s, \\pi (s), s') [R(s,\\pi (s),s') + γ V^{\\pi} (s')]$.\n",
        "* Textbook version: $U_i(s) = \\sum_{s'} P(s'|s, \\pi_i(s)) [R(s,\\pi_i(s),s') + γ U_i(s')]$\n",
        "* Benefit: a linear function\n",
        "* (slides): $O(S^2)$ per iteration\n",
        "* n-states: n linear equations with n unknowns, which can be solved in O(n^3) by linear algebra methods\n",
        "* Asynchronous policy iteration: pick any subset of states and apply policy improvement / simplified value iteration, guaranteed to find optimal policy (with conditions) => freedom to choose any state to update\n",
        "* Can compute actions from values using policy extraction: $\\pi^* (s) = arg \\max\\limits_{a} \\sum\\limits_{s'} T(s,a,s')[R(s,a,s') + γ V^* (s')]$\n",
        "* Can compute from Q-values, which is easier $\\pi^* (s) = arg \\max\\limits_{a} Q^*(s,a)$\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "**MDP\n",
        "* Probability of arriving at s' only depends on s and not history of earlist states (so Markovian transition)\n",
        "* MDP search trees: s is a state; (s,a) is a q-state, (s,a,s') is a transition - T(s,a,s')=P(s'|s,a)\n",
        "\n",
        "**Problem with value iteration**\n",
        "* It's slow $O(S^2 A)$ per iteration\n",
        "* Max at each state rarely changes\n",
        "* Policy often converges long before values\n",
        "\n",
        "**Comparison**\n",
        "* Value iteration: every iteration updates both values and (implicitly) policy - policy not tracked but taking max implicitly recomputes it\n",
        "* Policy iteration: after policy is evaluated, a new policy is chosen (still slow)\n",
        "\n",
        "**Algorithm summary**\n",
        "* Compute optimal value: use value iteration or policy iteration\n",
        "* Compute value for particular policy: policy evaluation\n",
        "* Turn value into policy: policy extraction\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",
        "\"MDP\" : \"Transition model (probabilistic outcome of actions) and reward function (for each state)\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 258,
      "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": "9cfda105-485e-4ff0-c709-f892d56f5e0e"
      },
      "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": 259,
      "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 Rational agent choose an action based on maximum expected utility (MEU), based on evidence e $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* Orderability (must have a preference)\n* Transitivity: A>B, B>C then A>C\n* Continuity: If A>B>C, ∃ p, such that [p,A:(1-p),C] ~ B\n* Substitutability\n* Monotonicity A>B => p>q <=> [p,A: 1-p, B]>[q,A: 1-q, B]\n* Decomposability\n \n\n## AIMA Chapter 16.3 Utility Functions\n\n* Optimizer's curse: estimated expect utility too high\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n**Stochastic Transition Model**\n* P(s' | s, a). Probability of reaching state s' from s, with action a\n\n**Markov Decision Process**\n* Sequential decision problem, fully observable, stochastic environment\n* Markovian transition model, additive rewards\n* Markovian means probability of reaching state s' from s depends only on s, not on earlier states\n\n**Policy**\n* Solution of what an agent should do for any state: π(s) for state s\n* Optimal policy: policy with highest expected utility, or π*\n\n**Finite vs. infinite horizons***\n* Finite: optimal action depends on how many times left, so policy is non-stationary (policies that depends on time)\n* Infinite: No reason to behave different in the smae state at different times, so stationary \n\n**Reward**\n* Can be additive reward\n* Or discounted rewward γ (between 0 and 1): U = R(s0)+*R(s1)+γ^2*R(s2)+...\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n**Bellman equation**\n* $V^*(s) = \\max\\limits_{a} Q^*(s,a)$\n* $V^*(s) = \\max\\limits_{a \\subseteq A(s)} \\sum_{s'} T(s,a,s') [R(s,a,s') + γ V^*(s')]$\n\n**Value iteration**\n* Non-linear Equations(due to max) => need an iterative appraoch\n* Start with arbitrary initial value, calculate RHS, plug into LHS - repeat until we reach equalibrium\n* Eventually converges to unique solutions\n* Policy loss: $U_{π_i}(s)$ - utility if we do $π_i$ in state s, $||U_{π_i}(s) - U||$ is policy loss (U is true utility)\n* Bellman update: $U_{i+1}(s) = \\max\\limits_{a \\subseteq A(s)} \\sum_{s'} P(s'|s,a) [R(s,a,s') + γ U_i (s')]$.\n* Slides version of Bellman update: $V_{k+1}(s) = \\max\\limits_{a} \\sum_{s'} T(s,a,s') [R(s,a,s') + γ V_k (s')]$.\n* Start with $V_0(s)=0$, repeat until convergence\n* (slides) complexity: $O(S^2 A)$ of each iteration\n\n**Policy iteration**\n* Step 1: Policy evaluation - calculate $U_{π_i}(s)$ based on policy $π_i$ (utility of each state)\n* Policy improvement: calculate new MEU policy $π_{i+1}$, with one-step look-ahead of $U_{π_i}$\n* Terminates when policy improvement yields no change in utilities\n* Slides version: $V^{\\pi}(s) = \\sum_{s'} T(s, \\pi (s), s') [R(s,\\pi (s),s') + γ V^{\\pi} (s')]$.\n* Textbook version: $U_i(s) = \\sum_{s'} P(s'|s, \\pi_i(s)) [R(s,\\pi_i(s),s') + γ U_i(s')]$\n* Benefit: a linear function\n* (slides): $O(S^2)$ per iteration\n* n-states: n linear equations with n unknowns, which can be solved in O(n^3) by linear algebra methods\n* Asynchronous policy iteration: pick any subset of states and apply policy improvement / simplified value iteration, guaranteed to find optimal policy (with conditions) => freedom to choose any state to update\n* Can compute actions from values using policy extraction: $\\pi^* (s) = arg \\max\\limits_{a} \\sum\\limits_{s'} T(s,a,s')[R(s,a,s') + γ V^* (s')]$\n* Can compute from Q-values, which is easier $\\pi^* (s) = arg \\max\\limits_{a} Q^*(s,a)$\n\n\n## Module 8 Lecture Notes\n\n**MDP\n* Probability of arriving at s' only depends on s and not history of earlist states (so Markovian transition)\n* MDP search trees: s is a state; (s,a) is a q-state, (s,a,s') is a transition - T(s,a,s')=P(s'|s,a)\n\n**Problem with value iteration**\n* It's slow $O(S^2 A)$ per iteration\n* Max at each state rarely changes\n* Policy often converges long before values\n\n**Comparison**\n* Value iteration: every iteration updates both values and (implicitly) policy - policy not tracked but taking max implicitly recomputes it\n* Policy iteration: after policy is evaluated, a new policy is chosen (still slow)\n\n**Algorithm summary**\n* Compute optimal value: use value iteration or policy iteration\n* Compute value for particular policy: policy evaluation\n* Turn value into policy: policy extraction\n\n\n\n## Module 8 Definitions\n* **Mdp** - Transition model (probabilistic outcome of actions) and reward function (for each 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",
        "**General**\n",
        "* Exploitation: follow current best action to obtain rewards\n",
        "* Exploration: explore unknown states and actions to gain information\n",
        "* one-armed bandit: one arm generates arbitrary sequence of rewards; the other arm generates fixed rewards - First iteration takes O(n), and afterwards O(1)\n",
        "* Pull arm with highest Gittins index, then update the indices\n",
        "\n",
        "**Bernoulli bandit**\n",
        "* Each arm Mi has reward of 0 or 1, with a fixed but unknown probability μ_i.\n",
        "* State of arm Mi: si and fi, number successes (1s) and failures (0s) so far\n",
        "* Transition probability: predicts the next outcome based on information so far\n",
        "* The counts are initialized to 1 - initial probablity 1/2 and 1/2\n",
        "* The Markov reward process\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" \n",
        "**General**\n",
        "* Reinforcement learning: use observed rewards to learn optimal policy\n",
        "\n",
        "**Type of Agent**\n",
        "* Utility-based: learns utility function on states\n",
        "* Q-learning: learns action-utility function (Q-function)\n",
        "* Reflex agent - learns policy which maps from states to actions\n",
        "\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "**Passive learning**\n",
        "* Agent policy is fixed, but agent does not know transition model, or rewards function\n",
        "* Direct utility estimation: estimate utility based on samples, but missed information (from Bellman equation), converges very slowly\n",
        "* Adaptive dynamic programing: can learn the resulting state (output) from state-action pair (input). Better approaces than MLE are Bayesian reinforcement learning and robust control theory\n",
        "* Temporal-difference learning: after transition s->s', $U_π(s) = U_π (s) + α (R(s) + γ U_π(s') - U_π(s))$, where α is the learning rate. \n",
        "* Due to exponential moving average - makes more recent samples more important - we can decrease learning rate to give converging averages\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "**Active learning**\n",
        "* Agent must learn what to do\n",
        "* Agent needs to learn model with outcome probability distributions associated w/ all actions \n",
        "* Obey Bellman equation, and can be solved using value iteration or policy iteration\n",
        "* Greedy agent - seldom converges to optimal policy\n",
        "* Solution: GILE: a simple one is to have the agent explorer a random action 1/t of the time, and follow current best policy otherwise\n",
        "\n",
        "**Exploration function**\n",
        "* U+(s) = R(s) + γ max (over a) f(Σ (over s') P(s'|s,a)U+(s'), N(s,a))\n",
        "* N(s,a) - # of times action a attempted in s\n",
        "* f(u,n) should be increasing in u but decreasing in n (if tried many attempts, then less useful to try again)\n",
        "\n",
        "**Q-learning**\n",
        "* Learns action-utility representation\n",
        "* Q(s,a) - value of action a in state s. $U(s) = \\max\\limits_a Q (s,a)$\n",
        "* Model-free method - does not need a transition model\n",
        "* Model: $Q(s,a) = Q(s,a) +  α (R(s) + γ \\max\\limits_{a'} Q(s',a') - Q(s,a))$\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "* Function approximation can compress a problem with too many states with something more managable. In chess - becomes a linear combination of chess pieces\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "**Policy search**\n",
        "* Motivation: to avoid value of policy change discontinuously\n",
        "* usually use a stochatic policy representation - has probaiblity of selecting action a in state s\n",
        "* Soft-max: generalization of logistic function. π_θ (s,a) = exp (Q_θ (s,a) / Σ (over a') exp ((Q_θ (s,a')\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "**Reinforcement learning**\n",
        "* MDP is offline planning\n",
        "* Don't know T or R, but still look for policy π\n",
        "\n",
        "**Model-based learning**\n",
        "* Learn empirical MDP model (by counting outcomes s' for each s,a), discover R when we experience (s,a,s')\n",
        "* Then solve the learned MDP using value iteration\n",
        "\n",
        "**Active/Full reinforcement learning**\n",
        "* Don't know transition T(s,a,s'), or reward R(s,a,s')\n",
        "* Learn optimal policy/values\n",
        "* Tradeoff: exploration vs. exploitation\n",
        "\n",
        "**Q-value iteration**\n",
        "* $V_{k+1}(s) = \\max\\limits_{a} \\sum\\limits_{s'} T(s,a,s') [R(s,a,s') + γ V_k (s')]$.\n",
        "* A better D-tour: $Q_{k+1}(s,a) = \\sum\\limits_{s'} T(s,a,s') [R(s,a,s') + γ \\max\\limits_{a'} V_k (s')]$.\n",
        "\n",
        "**Q-learning**\n",
        "* Sample-based Q-value iteration\n",
        "* Learn Q(s,a) values as you go - update sample estimates\n",
        "* Converges to optimal policy - even if acting suboptimally: off-policy learning\n",
        "* Have to explore enough, eventually make the learning rate small enough, but not decrease it too quickly\n",
        "* In the limit, doesn't matter how you select actions\n",
        "\n",
        "**Random exploration**\n",
        "* Choose random actions ε greedy\n",
        "* Act randomly with (small) probability ε\n",
        "* Act on current policy with probability 1-ε\n",
        "* Lower ε over time to prevent from thrashing around\n",
        "\n",
        "**Exploration function**\n",
        "* Better than random action - explorer areas where badness is not yet established\n",
        "* $f(u,n)=u+k/n$\n",
        "* Regular Q-update: $Q (s,a) = _α [R(s,a,s') + γ \\max\\limits_{a'} Q(s',a')]$.\n",
        "* Modified Q-update: $Q (s,a) = _α [R(s,a,s') + γ \\max\\limits_{a'} f(Q(s',a'),N(s',a')]$.\n",
        "\n",
        "**Regret**\n",
        "* Diff between your (expected) rewards, and optimal (expected) rewards\n",
        "* Minimizing regret - requires optimaly learning to be optimal\n",
        "* Random exploration has higher regret than exploration functions\n",
        "\n",
        "**Appexomiate Q-learning**\n",
        "* Cannot get all Q values (can't learn every single state)\n",
        "* Using a feature representation - linear representation\n",
        "* Exact Q-learning: $Q(s,a) = Q(s,a)+ α [difference]\n",
        "* Approximate Q-learning: $w_i = w_i + α[difference]f_i(s,a)$, adjust weights of active features\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Regret\" : \"number of additional mistakes (or total mistake cost) we make vs a clairvoyant who had the best prediction record\",\n",
        "}"
      ],
      "execution_count": 260,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "702a839e-b04a-4889-fc76-5e6a349bb8cb"
      },
      "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": 261,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n**General**\n* Exploitation: follow current best action to obtain rewards\n* Exploration: explore unknown states and actions to gain information\n* one-armed bandit: one arm generates arbitrary sequence of rewards; the other arm generates fixed rewards - First iteration takes O(n), and afterwards O(1)\n* Pull arm with highest Gittins index, then update the indices\n\n**Bernoulli bandit**\n* Each arm Mi has reward of 0 or 1, with a fixed but unknown probability μ_i.\n* State of arm Mi: si and fi, number successes (1s) and failures (0s) so far\n* Transition probability: predicts the next outcome based on information so far\n* The counts are initialized to 1 - initial probablity 1/2 and 1/2\n* The Markov reward process\n\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n \n**General**\n* Reinforcement learning: use observed rewards to learn optimal policy\n\n**Type of Agent**\n* Utility-based: learns utility function on states\n* Q-learning: learns action-utility function (Q-function)\n* Reflex agent - learns policy which maps from states to actions\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n**Passive learning**\n* Agent policy is fixed, but agent does not know transition model, or rewards function\n* Direct utility estimation: estimate utility based on samples, but missed information (from Bellman equation), converges very slowly\n* Adaptive dynamic programing: can learn the resulting state (output) from state-action pair (input). Better approaces than MLE are Bayesian reinforcement learning and robust control theory\n* Temporal-difference learning: after transition s->s', $U_π(s) = U_π (s) + α (R(s) + γ U_π(s') - U_π(s))$, where α is the learning rate. \n* Due to exponential moving average - makes more recent samples more important - we can decrease learning rate to give converging averages\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \n**Active learning**\n* Agent must learn what to do\n* Agent needs to learn model with outcome probability distributions associated w/ all actions \n* Obey Bellman equation, and can be solved using value iteration or policy iteration\n* Greedy agent - seldom converges to optimal policy\n* Solution: GILE: a simple one is to have the agent explorer a random action 1/t of the time, and follow current best policy otherwise\n\n**Exploration function**\n* U+(s) = R(s) + γ max (over a) f(Σ (over s') P(s'|s,a)U+(s'), N(s,a))\n* N(s,a) - # of times action a attempted in s\n* f(u,n) should be increasing in u but decreasing in n (if tried many attempts, then less useful to try again)\n\n**Q-learning**\n* Learns action-utility representation\n* Q(s,a) - value of action a in state s. $U(s) = \\max\\limits_a Q (s,a)$\n* Model-free method - does not need a transition model\n* Model: $Q(s,a) = Q(s,a) +  α (R(s) + γ \\max\\limits_{a'} Q(s',a') - Q(s,a))$\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n* Function approximation can compress a problem with too many states with something more managable. In chess - becomes a linear combination of chess pieces\n\n\n## Module 9 Lecture Notes\n\n**Reinforcement learning**\n* MDP is offline planning\n* Don't know T or R, but still look for policy π\n\n**Model-based learning**\n* Learn empirical MDP model (by counting outcomes s' for each s,a), discover R when we experience (s,a,s')\n* Then solve the learned MDP using value iteration\n\n**Active/Full reinforcement learning**\n* Don't know transition T(s,a,s'), or reward R(s,a,s')\n* Learn optimal policy/values\n* Tradeoff: exploration vs. exploitation\n\n**Q-value iteration**\n* $V_{k+1}(s) = \\max\\limits_{a} \\sum\\limits_{s'} T(s,a,s') [R(s,a,s') + γ V_k (s')]$.\n* A better D-tour: $Q_{k+1}(s,a) = \\sum\\limits_{s'} T(s,a,s') [R(s,a,s') + γ \\max\\limits_{a'} V_k (s')]$.\n\n**Q-learning**\n* Sample-based Q-value iteration\n* Learn Q(s,a) values as you go - update sample estimates\n* Converges to optimal policy - even if acting suboptimally: off-policy learning\n* Have to explore enough, eventually make the learning rate small enough, but not decrease it too quickly\n* In the limit, doesn't matter how you select actions\n\n**Random exploration**\n* Choose random actions ε greedy\n* Act randomly with (small) probability ε\n* Act on current policy with probability 1-ε\n* Lower ε over time to prevent from thrashing around\n\n**Exploration function**\n* Better than random action - explorer areas where badness is not yet established\n* $f(u,n)=u+k/n$\n* Regular Q-update: $Q (s,a) = _α [R(s,a,s') + γ \\max\\limits_{a'} Q(s',a')]$.\n* Modified Q-update: $Q (s,a) = _α [R(s,a,s') + γ \\max\\limits_{a'} f(Q(s',a'),N(s',a')]$.\n\n**Regret**\n* Diff between your (expected) rewards, and optimal (expected) rewards\n* Minimizing regret - requires optimaly learning to be optimal\n* Random exploration has higher regret than exploration functions\n\n**Appexomiate Q-learning**\n* Cannot get all Q values (can't learn every single state)\n* Using a feature representation - linear representation\n* Exact Q-learning: $Q(s,a) = Q(s,a)+ α [difference]\n* Approximate Q-learning: $w_i = w_i + α[difference]f_i(s,a)$, adjust weights of active features\n\n\n## Module 9 Definitions\n* **Regret** - number of additional mistakes (or total mistake cost) we make vs a clairvoyant who had the best prediction record\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \n",
        "* Sources of uncertainty: laziness, theoretical ignorance, practical ignorance\n",
        "* Decision theory = probability + utility\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "* sample space: set of all possible worlds\n",
        "* Kolmogorov's axioms - P (a v b) = P(a) + P(b) - P(a^b)\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\" \n",
        "* marginal probability: probability distribution over a subset of variables or a single variable\n",
        "* marginalization - summing out\n",
        "* Inference: P (X | e) = α P (X, e) = α Σ (over y) P(X, e, y)\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        "* Independence definition: P (X|Y) = P(X), or P(Y|X) = P(Y), or P(X,Y) = P(X)P(Y)\n",
        "\"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "**Bayes Rule**\n",
        "* P(Y|X) = P(X|Y)P(Y) / P(X)\n",
        "* Generalized version with backgroudn evidence e P(Y|X,e) = P(X|Y,e)P(Y|e) / P(X|e)\n",
        "* With normalization: P(Y|X) = α P(X|Y)P(Y), where α = 1 / P(X)\n",
        "\n",
        "**Conditional independence**\n",
        "* Definition: X and Y are conditionally independent given Z <=> Any x,y,z P(x,y|z) = P(x|z)*P(y|z).\n",
        "* Equivalent definition: If x, y are conditionally independent given z <=> P(x|y,z) = P(x|z) <=> P(y|x,z) = P(y|z)\n",
        "* P(x|y,z) = P(x,y,z) | P(y,z) = [P(x,y|z) * P(z)] / [P(z)*P(y|z)] = [P(x|z)*P(y|z)*P(z)] / [P(z)*P(y|z)] = P(x|z)\n",
        "* We can prove P(y|x,z) = P(y|z) with similar methods.\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "**Naive Bayes model**\n",
        "* P(Cause,Effect_1,...,Effect_n) = P(Cause) Π (over i) P(Effect_i | Cause)\n",
        "* P(Cause|e) = α P(Cause) Π (over j) P(e_j| Cause): Probability of each cause (given environment e) = multiply the prior probability of such cause, by the product of the conditional probabilities of each observed effects given this cause (then normalize)\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\"\n",
        "* Probability can do better than logical inference alone (so do not need to choose randomly)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" \n",
        "**N-grams**\n",
        "* P(w1:n) = P(w1)P(w2|w1)P(w3|w1:2)...P(wn|w1:n-1)\n",
        "* BIgram: only use the conditional probability of the previous ONE word, or P(wn|w1:n-1) alomst equals P(wn|wn-1)\n",
        "* Use log probabilities - to prevent numerical underflow\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = \"\"\" \n",
        "** Perplexity**\n",
        "* PP for short\n",
        "* Inverse probability of the test set (normalized by # of words): higher conditional probability => lower perplexity\n",
        "* Weighted average branching factor - # of possible next words that can follow a given word\n",
        "* A language model with lower perplexity is a better model (other things being equal)\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "* visualizing a language model by sampling\n",
        "\"\"\"\n",
        "SLP_chapter3_4 = \"\"\" \n",
        "* Out of vocabulary (OOV) words (zeros!)\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\" \n",
        "** Smoothing**\n",
        "* Laplace Smoothing - add one to n-gram counts (Before we normalize) to avoid 0 probability\n",
        "* Add-k smoothing (both numerator and denominator)\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "* Huge Language Models:\n",
        "* Stupid Backoff: simple algorithm with large language models\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "**General**\n",
        "* Chain rule: $P(x_1, x_2,...x_n) = ∏ \\limits_{i} P(X_i|x_1,...x_{i-1})$\n",
        "* Language model: a model that computes with $P(W) =P(w_1, w_2, ...w_n)$, or $P(w_n|w_1,w_2,...w_{n-1})$\n",
        "* Under Markov assumption, only depends on previous k words, $P(w_1, w_2,...w_n) = ∏ \\limits_{i}^{n} P(w_i|w_{i-k},...w_{i-1})$\n",
        "* Unigram - no history; bi-gram - 1 word history; tri-gram: 2-words history; 4-gram: 3-words history\n",
        "* Unigram model: $P(w_1 w_2...w_n) = ∏ \\limits_{i}^{n} P(w_i)$\n",
        "* Bigram model: $P(w_i|w_1 w_2...w_{i-1}) = P(w_i|w_{i-1})$\n",
        "* In practise, do everything in log space\n",
        "\n",
        "**Maximum Likehood Estimate**\n",
        "* A way to estimate conditional probability\n",
        "* Problem: Out of vocabulary items (OOV)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 262,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "c437834e-ebd8-4d95-9755-0c3e98b86815"
      },
      "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": 263,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n* Sources of uncertainty: laziness, theoretical ignorance, practical ignorance\n* Decision theory = probability + utility\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n* sample space: set of all possible worlds\n* Kolmogorov's axioms - P (a v b) = P(a) + P(b) - P(a^b)\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n* marginal probability: probability distribution over a subset of variables or a single variable\n* marginalization - summing out\n* Inference: P (X | e) = α P (X, e) = α Σ (over y) P(X, e, y)\n\n\n## AIMA Chapter 12.4 Independence\n \n* Independence definition: P (X|Y) = P(X), or P(Y|X) = P(Y), or P(X,Y) = P(X)P(Y)\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n**Bayes Rule**\n* P(Y|X) = P(X|Y)P(Y) / P(X)\n* Generalized version with backgroudn evidence e P(Y|X,e) = P(X|Y,e)P(Y|e) / P(X|e)\n* With normalization: P(Y|X) = α P(X|Y)P(Y), where α = 1 / P(X)\n\n**Conditional independence**\n* Definition: X and Y are conditionally independent given Z <=> Any x,y,z P(x,y|z) = P(x|z)*P(y|z).\n* Equivalent definition: If x, y are conditionally independent given z <=> P(x|y,z) = P(x|z) <=> P(y|x,z) = P(y|z)\n* P(x|y,z) = P(x,y,z) | P(y,z) = [P(x,y|z) * P(z)] / [P(z)*P(y|z)] = [P(x|z)*P(y|z)*P(z)] / [P(z)*P(y|z)] = P(x|z)\n* We can prove P(y|x,z) = P(y|z) with similar methods.\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n**Naive Bayes model**\n* P(Cause,Effect_1,...,Effect_n) = P(Cause) Π (over i) P(Effect_i | Cause)\n* P(Cause|e) = α P(Cause) Π (over j) P(e_j| Cause): Probability of each cause (given environment e) = multiply the prior probability of such cause, by the product of the conditional probabilities of each observed effects given this cause (then normalize)\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n* Probability can do better than logical inference alone (so do not need to choose randomly)\n\n\n## SLP Chapter 3.1 N-Grams\n \n**N-grams**\n* P(w1:n) = P(w1)P(w2|w1)P(w3|w1:2)...P(wn|w1:n-1)\n* BIgram: only use the conditional probability of the previous ONE word, or P(wn|w1:n-1) alomst equals P(wn|wn-1)\n* Use log probabilities - to prevent numerical underflow\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n \n** Perplexity**\n* PP for short\n* Inverse probability of the test set (normalized by # of words): higher conditional probability => lower perplexity\n* Weighted average branching factor - # of possible next words that can follow a given word\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n* visualizing a language model by sampling\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n \n* Out of vocabulary (OOV) words (zeros!)\n\n\n## SLP Chapter 3.5 Smoothing\n \n** Smoothing**\n* Laplace Smoothing - add one to n-gram counts (Before we normalize) to avoid 0 probability\n* Add-k smoothing (both numerator and denominator)\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n* Huge Language Models:\n* Stupid Backoff: simple algorithm with large language models\n\n\n## Module 10 Lecture Notes\n\n**General**\n* Chain rule: $P(x_1, x_2,...x_n) = ∏ \\limits_{i} P(X_i|x_1,...x_{i-1})$\n* Language model: a model that computes with $P(W) =P(w_1, w_2, ...w_n)$, or $P(w_n|w_1,w_2,...w_{n-1})$\n* Under Markov assumption, only depends on previous k words, $P(w_1, w_2,...w_n) = ∏ \\limits_{i}^{n} P(w_i|w_{i-k},...w_{i-1})$\n* Unigram - no history; bi-gram - 1 word history; tri-gram: 2-words history; 4-gram: 3-words history\n* Unigram model: $P(w_1 w_2...w_n) = ∏ \\limits_{i}^{n} P(w_i)$\n* Bigram model: $P(w_i|w_1 w_2...w_{i-1}) = P(w_i|w_{i-1})$\n* In practise, do everything in log space\n\n**Maximum Likehood Estimate**\n* A way to estimate conditional probability\n* Problem: Out of vocabulary items (OOV)\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" \n",
        "* Bayesian network: dependencies among variables\n",
        "* P(x1,...xn) = Π (i=1 to n) θ(x_i | parents (x_i))\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "**Bayes Net**\n",
        "* P(x1,...xn) = Π (i=1 to n) θ(x_i | parents (x_i)), where θ is conditional probabilities (from joint distribution)\n",
        "* P(x1,...xn)= P(x_n|x_n-1,...x_1)P(x_n-1|...,x1) = Π (i=1 to n) P(x_i|x_i-1,....x_1)\n",
        "* We should number the nodes according to topological order, which case P(x_i|=Parents(x+i))\n",
        "* Bayes net can be more compact than full joint distribution (n*2^k vs. 2^n)\n",
        "\n",
        "**Conditional independence**\n",
        "* Variable - conditionally independent of non-descendants, given parents\n",
        "* Markov blanket: variable conditionally independent of all other nodes (given parents, children, and children's parents) \n",
        "\n",
        "**D-seperation (more general than Markov Chain)** \n",
        "* Whether set X conditionally independent of set Y, given set Z - check whether Z d-seperates X and Y\n",
        "* A variable's Markov blanket d-seperates it from other variables\n",
        "\n",
        "**D-seperation process**\n",
        "* Consider anchestrtal subgraph - X,Y,Z + their anchestors\n",
        "* Moral graph: add links between unlinked pair of nodes with common child\n",
        "* Replace directed links w/ undirected links\n",
        "* If Z blocks all paths between X and Y => Z d-seperates X and Y (X, Y conditionally independent, given Z)\n",
        "\n",
        "**Bayes nets Continous variables*\n",
        "* Discretization - devide values into several intervals (and now discrete)\n",
        "* Non-parametric\n",
        "* Hybrid - both discrete and continuous\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\"\n",
        "**Exact inference**\n",
        "* Inference by enumeration\n",
        "* Variable elimination algorithm - simple and efficient for answering individual queries - takes O(n^2)\n",
        "* Joint tree algorithm - takes O(n)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "**Conditional independence**\n",
        "* $X \\perp Y$: for ∀ x, y, P(x,y)=P(x)P(y)\n",
        "* $X \\perp Y|Z$: for ∀ x, y, z, P(x,y|z)=P(x|z)P(y|z), or equivaelently ∀ x, y, z, P(x|z,y)=P(x|z)\n",
        "\n",
        "**Bayes Net**\n",
        "* $P(x_i|x_1,...x_{i-1})=P(x_i|parents(X_i))$\n",
        "\n",
        "**D-seperation**\n",
        "* Study independence properties for triples\n",
        "* Causal chains (x=>y=>z), P(x,y,z) = P(x)*P(y|x)*P(z|y): P(z|x,y) = P(x,y,z)|P(x,y)=(P(x)*P(y|x)*P(z|y))/(P(x)*P(y|x))=P(z|y).  So $X \\perp Z|Y$\n",
        "* Common Cause: (y=>x, and y=>z),P(x,y,z)=P(y)P(x|y)P(z|y): P(z|x,y)=P(x,y,z)|P(x,y)=(P(y)P(x|y)P(z|y))/(P(y)P(x|y))=P(z|y). So $X \\perp Z|Y$\n",
        "* Common effect (x=>z, y=>z): x, y are independent, but they're not conditionally independent given z, due to competition as explanation (Observing an effect activates influence between possible causes.)\n",
        "\n",
        "**Active vs. inactive**\n",
        "* Inactive for causal chain (blocks middle), common cause (block cause), or common effect (do not block common effect)\n",
        "* Need a single, inactive segment to block a path\n",
        "* Is $X_i$ and $X_j$ conditionally independent? Check all (undirected) paths between $X_i$ and $X_j$, If one more more path active, then conditional independence not guaranteed\n",
        "\n",
        "**Inference**\n",
        "* Given posterior probability, calculate most likely explanation\n",
        "* Inference by emuneration - slow, as you join up the whole joint distribution before you sum out the hidden variables\n",
        "* Variable elimination: Interleave joining and marginalizing, Still NP-hard, but usually much faster than inference by enumeration\n",
        "\n",
        "**Dynamic Bayesian networks (DBN)**\n",
        "* extend standard Bayesian networks to handle temporal probability models\n",
        "* Corresponds to a Bayesian network with infinitely many variables\n",
        "* Must specify three kinds of information: prior distribution over the state variables, $P(X_0)$;  transition model $P(X_{t+1}|X_t)$; and the sensor model $P(E_t | X_t)$\n",
        "\n",
        "**locally structured (sparse) systems**\n",
        "* Each subcomponent interacts directly with only a limited number of other components\n",
        "* usually associated with linear rather than exponential complexity\n",
        "* Bayesian networks is an example, Bayesian networks is compact\n",
        "\n",
        "**Other**\n",
        "* A nonparametric model - cannot be characterized by a finite set of parameters.- examples: instance-based learning or memory-based learning\n",
        "* \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 273,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "79f0c699-7ee6-46ff-b065-5b84ffa21b7d"
      },
      "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": 274,
      "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 \n* Bayesian network: dependencies among variables\n* P(x1,...xn) = Π (i=1 to n) θ(x_i | parents (x_i))\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n**Bayes Net**\n* P(x1,...xn) = Π (i=1 to n) θ(x_i | parents (x_i)), where θ is conditional probabilities (from joint distribution)\n* P(x1,...xn)= P(x_n|x_n-1,...x_1)P(x_n-1|...,x1) = Π (i=1 to n) P(x_i|x_i-1,....x_1)\n* We should number the nodes according to topological order, which case P(x_i|=Parents(x+i))\n* Bayes net can be more compact than full joint distribution (n*2^k vs. 2^n)\n\n**Conditional independence**\n* Variable - conditionally independent of non-descendants, given parents\n* Markov blanket: variable conditionally independent of all other nodes (given parents, children, and children's parents) \n\n**D-seperation (more general than Markov Chain)** \n* Whether set X conditionally independent of set Y, given set Z - check whether Z d-seperates X and Y\n* A variable's Markov blanket d-seperates it from other variables\n\n**D-seperation process**\n* Consider anchestrtal subgraph - X,Y,Z + their anchestors\n* Moral graph: add links between unlinked pair of nodes with common child\n* Replace directed links w/ undirected links\n* If Z blocks all paths between X and Y => Z d-seperates X and Y (X, Y conditionally independent, given Z)\n\n**Bayes nets Continous variables*\n* Discretization - devide values into several intervals (and now discrete)\n* Non-parametric\n* Hybrid - both discrete and continuous\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n**Exact inference**\n* Inference by enumeration\n* Variable elimination algorithm - simple and efficient for answering individual queries - takes O(n^2)\n* Joint tree algorithm - takes O(n)\n\n\n## Module 11 Lecture Notes\n\n**Conditional independence**\n* $X \\perp Y$: for ∀ x, y, P(x,y)=P(x)P(y)\n* $X \\perp Y|Z$: for ∀ x, y, z, P(x,y|z)=P(x|z)P(y|z), or equivaelently ∀ x, y, z, P(x|z,y)=P(x|z)\n\n**Bayes Net**\n* $P(x_i|x_1,...x_{i-1})=P(x_i|parents(X_i))$\n\n**D-seperation**\n* Study independence properties for triples\n* Causal chains (x=>y=>z), P(x,y,z) = P(x)*P(y|x)*P(z|y): P(z|x,y) = P(x,y,z)|P(x,y)=(P(x)*P(y|x)*P(z|y))/(P(x)*P(y|x))=P(z|y).  So $X \\perp Z|Y$\n* Common Cause: (y=>x, and y=>z),P(x,y,z)=P(y)P(x|y)P(z|y): P(z|x,y)=P(x,y,z)|P(x,y)=(P(y)P(x|y)P(z|y))/(P(y)P(x|y))=P(z|y). So $X \\perp Z|Y$\n* Common effect (x=>z, y=>z): x, y are independent, but they're not conditionally independent given z, due to competition as explanation (Observing an effect activates influence between possible causes.)\n\n**Active vs. inactive**\n* Inactive for causal chain (blocks middle), common cause (block cause), or common effect (do not block common effect)\n* Need a single, inactive segment to block a path\n* Is $X_i$ and $X_j$ conditionally independent? Check all (undirected) paths between $X_i$ and $X_j$, If one more more path active, then conditional independence not guaranteed\n\n**Inference**\n* Given posterior probability, calculate most likely explanation\n* Inference by emuneration - slow, as you join up the whole joint distribution before you sum out the hidden variables\n* Variable elimination: Interleave joining and marginalizing, Still NP-hard, but usually much faster than inference by enumeration\n\n**Dynamic Bayesian networks (DBN)**\n* extend standard Bayesian networks to handle temporal probability models\n* Corresponds to a Bayesian network with infinitely many variables\n* Must specify three kinds of information: prior distribution over the state variables, $P(X_0)$;  transition model $P(X_{t+1}|X_t)$; and the sensor model $P(E_t | X_t)$\n\n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "**Type of learning**\n",
        "* Supervised: observe input-output (label) pairs, and learn the mapping\n",
        "* Unsupervised: learn pattern without explicit feedback: for example, clustering\n",
        "* Reinforcement learning: learn from reward and punishment\n",
        " \"\"\"\n",
        "chapter19_2 = \"\"\" \n",
        "* Bias-variance tradeoff: choice between fitting training data well vs. generalizes better\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\"\n",
        "* Decision tree\n",
        "* Happy-curve: more training data => better accuracy\n",
        "* Entropy: measure of uncertainty for random variable: more information => less entropy\n",
        "* Entropy: H(V) = Σ (over k) P(v_k) log 2 (1/P(v_k)) = -Σ (over k) P(v_k) log2 P(v_k)\n",
        "* H (Fair dice) = -(0.5log (2) 0.5+0.5log (2) 0.5)=1\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\" \n",
        "* Regularization - explicitly penalizes complex hypothesis\n",
        " \"\"\"\n",
        "chapter19_5 = \"\"\" \n",
        "* Decision tree - specific to a particular learning algorithm\n",
        "* Decision list - more general\n",
        "* Probably approximately correct (PAC) - hypothesis consistent with large enough training data - unlikely to be seriously wrong\n",
        "* PAC learning: returns hypothesis which are roughly correct\n",
        "\"\"\"\n",
        "chapter19_6 = \"\"\"\n",
        "**Gradient descent**\n",
        "* Choose any starting point\n",
        "* Computer greadient - and move a small amount in the steepest downhill direction\n",
        "* Repeat until converge on a point\n",
        "* $W_i = W_i - α * ∂/∂W_i Loss (W)$\n",
        "* α is the step size, or learning rate - can be fixed or decrease over time\n",
        "\n",
        "**Multi-variate linear regression**\n",
        "* Normal equation w* = (XT X)^-1 XT y\n",
        "\"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "* naive Bayes classifier\n",
        "* c_hat= argmax (c ∈ C) P(c|d) = argmax P(d|c) * P(c) (we can drop denominator p(d))\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "**General**\n",
        "* Bayes rule lets us do diagnostic queries with causal probabilities\n",
        "* Naïve Bayes: Assume all features are independent effects of the class label\n",
        "* General Naïve Bayes model: $P(Y, F_1, ...F_n)=P(Y) \\prod\\limits_{i} P(F_i)|Y)$\n",
        "* We can build classifiers out of a naïve Bayes model using training data \n",
        "\n",
        "**Bag-of-words Naïve Bayes**\n",
        "* Features: $W_i$ is the word at positon i\n",
        "* As before: predict label conditioned on feature variables (spam vs. ham)\n",
        "* As before: assume features are conditionally independent given label\n",
        "* New: each $W_i$ is identically distributed\n",
        "* Called “bag-of-words” because model is insensitive to word order or reordering\n",
        "* All positions share the same conditional probs P(W|Y)\n",
        "\n",
        "**Training**\n",
        "* training set (for training)\n",
        "* held out set: practice exam\n",
        "* test set: final exam\n",
        "\n",
        "**Smoothing**\n",
        "* Laplace (add 1): often performs poorly for P(X|Y) when |X| is large, or when |Y| is ver large\n",
        "* Linear interpolation $P_{LIN} (x|y) = α \\hat{P}(x|y)+ (1-α) \\hat{P}(x)$\n",
        "\n",
        "**Linear classifier**\n",
        "* Inputs are feature values\n",
        "* Each feature has a weight\n",
        "* Sum is the activation\n",
        "\n",
        "**Learning - binary perception**\n",
        "* classify w/ current weight\n",
        "* If correct (i.e., y=y*), no change!\n",
        "* If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1. w=w+y*f\n",
        "\n",
        "**Multiclass Decision Rule**\n",
        "* we have weight vector $w_y$\n",
        "* score (activation) of a class y: $w_y * f(x)$\n",
        "* prediction highest score wins $y=arg \\max\\limits_{y} w_y * f(x)$\n",
        "* start w/ all 0 weights\n",
        "* pick up training example one by one\n",
        "* predict current weights using $y=arg \\max\\limits_{y} w_y * f(x)$\n",
        "* if correct, no change, if wrong - lower score of wrong answer,raise score of right answer: $w_y = w_y - f(x)$, $w_{y*} = w_{y*} + f(x)$\n",
        "\n",
        "**Perception**\n",
        "* Weights, bias and dot products\n",
        "* if w*x+b>0, output 1, otherwise 0\n",
        "\n",
        "**Perception problem**\n",
        "* noise: if the data isn’t separable, weights might thrash\n",
        "* Mediocre generalization: finds a “barely” separating solution\n",
        "* Overtraining: test / held-out accuracy usually rises, then falls\n",
        "* Solution: MIRA (Margin Infused Relaxed Algorithm): choose an update size that fixes the current mistak, but, minimizes the change to w (minimum correcting update)\n",
        "* In practice, also bad to make updates that are too large, so cap with a constant C\n",
        "* SVM(Support Vector Machines): Maximizing the margin: good according to intuition, theory, practice (finds seperator with max margin)\n",
        "* In both MIRA and SVM - optimize over all examples at once\n",
        "\n",
        "**Naïve Bayes vs. Perceptrons/MIRA**\n",
        "* Naïve Bayes: Strong assumptions about feature independence; One pass through data (counting)\n",
        "* Perceptrons: makes less assumptions; mistake-driven learning; multiple-passes through data (prediction), often more accurate\n",
        "\n",
        "**XOR problem**\n",
        "* A single neural unit cannot be used to compute the XOR function\n",
        "\n",
        "**Activation Functions**\n",
        "* Sigmoid\n",
        "* tanh: Hyperbolic tangent, $(e^{2x}-1)/(e^{2x}+1)$; a variant of the sigmoid function and maps outlier values toward the mean\n",
        "* rectified linear unit ReLU\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 266,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "2db1a6d7-c84d-4051-9abd-813e0cdaaca4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 267,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n**Type of learning**\n* Supervised: observe input-output (label) pairs, and learn the mapping\n* Unsupervised: learn pattern without explicit feedback: for example, clustering\n* Reinforcement learning: learn from reward and punishment\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n* Bias-variance tradeoff: choice between fitting training data well vs. generalizes better\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n* Decision tree\n* Happy-curve: more training data => better accuracy\n* Entropy: measure of uncertainty for random variable: more information => less entropy\n* Entropy: H(V) = Σ (over k) P(v_k) log 2 (1/P(v_k)) = -Σ (over k) P(v_k) log2 P(v_k)\n* H (Fair dice) = -(0.5log (2) 0.5+0.5log (2) 0.5)=1\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \n* Regularization - explicitly penalizes complex hypothesis\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n* Decision tree - specific to a particular learning algorithm\n* Decision list - more general\n* Probably approximately correct (PAC) - hypothesis consistent with large enough training data - unlikely to be seriously wrong\n* PAC learning: returns hypothesis which are roughly correct\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n**Gradient descent**\n* Choose any starting point\n* Computer greadient - and move a small amount in the steepest downhill direction\n* Repeat until converge on a point\n* $W_i = W_i - α * ∂/∂W_i Loss (W)$\n* α is the step size, or learning rate - can be fixed or decrease over time\n\n**Multi-variate linear regression**\n* Normal equation w* = (XT X)^-1 XT y\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n* naive Bayes classifier\n* c_hat= argmax (c ∈ C) P(c|d) = argmax P(d|c) * P(c) (we can drop denominator p(d))\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n**General**\n* Bayes rule lets us do diagnostic queries with causal probabilities\n* Naïve Bayes: Assume all features are independent effects of the class label\n* General Naïve Bayes model: $P(Y, F_1, ...F_n)=P(Y) \\prod\\limits_{i} P(F_i)|Y)$\n* We can build classifiers out of a naïve Bayes model using training data \n\n**Bag-of-words Naïve Bayes**\n* Features: $W_i$ is the word at positon i\n* As before: predict label conditioned on feature variables (spam vs. ham)\n* As before: assume features are conditionally independent given label\n* New: each $W_i$ is identically distributed\n* Called “bag-of-words” because model is insensitive to word order or reordering\n* All positions share the same conditional probs P(W|Y)\n\n**Training**\n* training set (for training)\n* held out set: practice exam\n* test set: final exam\n\n**Smoothing**\n* Laplace (add 1): often performs poorly for P(X|Y) when |X| is large, or when |Y| is ver large\n* Linear interpolation $P_{LIN} (x|y) = α \\hat{P}(x|y)+ (1-α) \\hat{P}(x)$\n\n**Linear classifier**\n* Inputs are feature values\n* Each feature has a weight\n* Sum is the activation\n\n**Learning - binary perception**\n* classify w/ current weight\n* If correct (i.e., y=y*), no change!\n* If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1. w=w+y*f\n\n**Multiclass Decision Rule**\n* we have weight vector $w_y$\n* score (activation) of a class y: $w_y * f(x)$\n* prediction highest score wins $y=arg \\max\\limits_{y} w_y * f(x)$\n* start w/ all 0 weights\n* pick up training example one by one\n* predict current weights using $y=arg \\max\\limits_{y} w_y * f(x)$\n* if correct, no change, if wrong - lower score of wrong answer,raise score of right answer: $w_y = w_y - f(x)$, $w_{y*} = w_{y*} + f(x)$\n\n**Perception**\n* Weights, bias and dot products\n* if w*x+b>0, output 1, otherwise 0\n\n**Perception problem**\n* noise: if the data isn’t separable, weights might thrash\n* Mediocre generalization: finds a “barely” separating solution\n* Overtraining: test / held-out accuracy usually rises, then falls\n* Solution: MIRA (Margin Infused Relaxed Algorithm): choose an update size that fixes the current mistak, but, minimizes the change to w (minimum correcting update)\n* In practice, also bad to make updates that are too large, so cap with a constant C\n* SVM(Support Vector Machines): Maximizing the margin: good according to intuition, theory, practice (finds seperator with max margin)\n* In both MIRA and SVM - optimize over all examples at once\n\n**Naïve Bayes vs. Perceptrons/MIRA**\n* Naïve Bayes: Strong assumptions about feature independence; One pass through data (counting)\n* Perceptrons: makes less assumptions; mistake-driven learning; multiple-passes through data (prediction), often more accurate\n\n**XOR problem**\n* A single neural unit cannot be used to compute the XOR function\n\n**Activation Functions**\n* Sigmoid\n* tanh: Hyperbolic tangent, $(e^{2x}-1)/(e^{2x}+1)$\n* rectified linear unit ReLU\n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" \n",
        "**Logistic Regression**\n",
        "* logistic regression is a discriminative classifier - only try to learn to distinguish the classes\n",
        "* Naive Bayes is a generative classifier - try to understand differences between classes\n",
        "* logistic regression - probabilistic classifier, use supervised machine learning (same as Bayes)\n",
        "* Has training & testing\n",
        "\n",
        "**Four components for classification with ML**\n",
        "* Feature representation of input\n",
        "* Classification function which computes y_hat (estimated class), via P(y|x) - can use sigmoid or softmax\n",
        "* Objective function for learning: cross-entropy loss function\n",
        "* Optimization Algorithm: stochastic gradient descent\n",
        "\n",
        "**Classification with Sigmoid function**\n",
        "* The sigmoid function σ(z) = 1/(1+e^-z) takes any value and maps it to the range [0;1].\n",
        "* z=w*x+b (dot product), where b is biased term\n",
        "* Need a boundary value\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_2 = \"\"\"\n",
        "* Objective: learn parameters (w and b) that make y_hat for each training set as close to true y as possible.\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_3 = \"\"\"\n",
        "* $L(\\hat{y}, y) = \\hat{y}$ differs from the true y\n",
        "* Choose w,b s.t. we maximize the log probability of the true y in the training data, given the observations x.\n",
        "* Cross-entropy loss: negative log likelihood loss\n",
        "* $p(y|x) = \\hat{y}|^y * (1 - \\hat{y})^(1-y)$\n",
        "* Take log: $ylog(\\hat{y}) + (1-y) log(1-\\hat{y})$\n",
        "* To minimize loss, flip the sign: $-ylog(\\hat{y}) - (1-y) log(1-\\hat{y})$\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter5_4 = \"\"\" \n",
        "**How Gradient descent work - Find the gradient of the loss function and move in the opposite direction**\n",
        "* Choose any starting point\n",
        "* Computer gradient - and move a small amount in the steepest downhill direction\n",
        "* Repeat until converge on a point\n",
        "\"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "* Add -α R(q) (regulationzation term) to avoid over-fitting\n",
        "* L2 regularization - Σ θj^2 - Euclidean distance\n",
        "* L1 regularization - Σ |θj| - Manhattan distance\n",
        "\"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "**multinomial logistic regression, a.k.a. softmax regression**\n",
        "* Uses a generalization of the sigmoid\n",
        "* softmax$(z_i) = e^{z_i} / (\\sum\\limits_{j=1}^{k} e^{z_j})$, for $1 \\leq i \\leq k$\n",
        "* softmax normalizes the output and turns it into a probability distribution.\n",
        "\"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\n",
        "**Relu - rectified linear unit, also called the ReLU, y=max(z,0)\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "**Classifier components**\n",
        "* Feature representation of input - which is a factor of features $[x_1,x_2,...x_n]$\n",
        "* Classification function which computs $\\hat{y}$ via p(y|x)\n",
        "* objective function for learning - usually minimizing error on training examples\n",
        "* algorithm for optimizing objective function\n",
        "* Sentiment classification: estimate P(y=1|x)\n",
        "\n",
        "**Logistic regression**\n",
        "* $z=\\sum\\limits_{i}w_ix_i + b$, or $z=w \\cdot x + b$\n",
        "\n",
        "**Sigmoid**\n",
        "* $y=1/(1+e^{-z})$\n",
        "* $P(y=1)= \\sigma (w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$\n",
        "* Decision boundary: $\\hat{y}=1$ if $P(y=1|x)>0.5$\n",
        "* How to get weights? (A) An loss function that tells us distance between the system output and the gold output; (B) stochastic gradient descent to minimize the loss function.\n",
        "* Cross-entropy loss: negative log likelihood loss (maximize likelihood = minimize loss ratio): $-ylog(\\hat{y}) - (1-y) log(1-\\hat{y})$ \n",
        "* with $\\hat{y} = \\sigma (w \\cdot x + b)$, we have $-ylog(\\sigma (w \\cdot x + b)) - (1-y) log(1-\\sigma (w \\cdot x + b))$\n",
        "* We want loss be smaller if the model’s estimate is close to correct, and loss to be bigger if it is confused.\n",
        "\n",
        "**Gradient descent**\n",
        "* Find weights and bias by minimizing loss: $\\hat{θ} = arg \\min\\limits_{θ} 1/m \\sum\\limits_{i=1}^{m} L_{CE} (y^{(i)},x^{(i)}; θ)$\n",
        "* Finds a minimum of a function by figuring out in which direction (in terms of θ) the function has the steepest slope, and moving in the opposite direction\n",
        "* For logistic regression: $L_{CE}(w,b) =- [ylog(\\sigma (w \\cdot x + b)) + (1-y) log(1-\\sigma (w \\cdot x + b))]$\n",
        "* $∂L_{CE}/∂W_j =  [\\sigma (w \\cdot x + b)-y]x_j$\n",
        "* $∂L_{CE}/∂b =  [\\sigma (w \\cdot x + b)-y]$\n",
        "* Cost over batch of data: $Cost(w,b) = -1/m \\sum\\limits_{i=1}^{m} y^{(i)} log(\\sigma (w \\cdot x^{(i)} + b)) + (1-y^{(i)}) log(1-\\sigma (w \\cdot x^{(i)} + b))$\n",
        "* Gradient for multiple points $∂ Cost(w,b)/∂W_j = \\sum\\limits_{i=1}^{m} [\\sigma (w \\cdot x^{(i)} + b)-y^{(i)}]x_j^{(i)}$\n",
        "\n",
        "**Regularization**\n",
        "* Penalize large weights. A regularization term is added to the loss function.\n",
        "* Lasso regression uses L1 regularization\n",
        "* Ridge regression uses L2 regularization\n",
        "\n",
        "**Feed-Forward Neural Network**\n",
        "* Simplest N.N.\n",
        "* Multilayer network, all units usually fully-connected, and no cycles.\n",
        "\n",
        "**Hidden Layer Computation**\n",
        "* Step 1: multiply the weight matrix by the input vector x,\n",
        "* Step 2. add the bias vector b, and\n",
        "* Step 3. apply the activation function g (such as Sigmoid)\n",
        "* Output h = σ(Wx+b), σ is sigmoid function\n",
        "\n",
        "**All layer**\n",
        "* Takes an input vector x, outputs a probability distribution y, and is parameterized by weight matrices W and U and a bias vector b:\n",
        "* h = σ(Wx+b)\n",
        "* z = Uh\n",
        "* y = softmax(z)\n",
        "\n",
        "**Backpropagation**\n",
        "* Related to general procedure called backward differentiation\n",
        "* Depends on the notion of computation graphs => process of computing a mathematical expression. Computation broken down to seperate operations, each represented by a node in a graph \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 268,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "897ca67e-90ed-4196-fd8f-337af79dadeb"
      },
      "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": 269,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \n**Logistic Regression**\n* logistic regression is a discriminative classifier - only try to learn to distinguish the classes\n* Naive Bayes is a generative classifier - try to understand differences between classes\n* logistic regression - probabilistic classifier, use supervised machine learning (same as Bayes)\n* Has training & testing\n\n**Four components for classification with ML**\n* Feature representation of input\n* Classification function which computes y_hat (estimated class), via P(y|x) - can use sigmoid or softmax\n* Objective function for learning: cross-entropy loss function\n* Optimization Algorithm: stochastic gradient descent\n\n**Classification with Sigmoid function**\n* The sigmoid function σ(z) = 1/(1+e^-z) takes any value and maps it to the range [0;1].\n* z=w*x+b (dot product), where b is biased term\n* Need a boundary value\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n* Objective: learn parameters (w and b) that make y_hat for each training set as close to true y as possible.\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n* $L(\\hat{y}, y) = \\hat{y}$ differs from the true y\n* Choose w,b s.t. we maximize the log probability of the true y in the training data, given the observations x.\n* Cross-entropy loss: negative log likelihood loss\n* $p(y|x) = \\hat{y}|^y * (1 - \\hat{y})^(1-y)$\n* Take log: $ylog(\\hat{y}) + (1-y) log(1-\\hat{y})$\n* To minimize loss, flip the sign: $-ylog(\\hat{y}) - (1-y) log(1-\\hat{y})$\n\n\n## SLP Chapter 5.4 Gradient Descent\n \n**How Gradient descent work - Find the gradient of the loss function and move in the opposite direction**\n* Choose any starting point\n* Computer gradient - and move a small amount in the steepest downhill direction\n* Repeat until converge on a point\n\n\n## SLP Chapter 5.5 Regularization\n\n* Add -α R(q) (regulationzation term) to avoid over-fitting\n* L2 regularization - Σ θj^2 - Euclidean distance\n* L1 regularization - Σ |θj| - Manhattan distance\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n**multinomial logistic regression, a.k.a. softmax regression**\n* Uses a generalization of the sigmoid\n* softmax$(z_i) = e^{z_i} / (\\sum\\limits_{j=1}^{k} e^{z_j})$, for $1 \\leq i \\leq k$\n* softmax normalizes the output and turns it into a probability distribution.\n\n\n## SLP Chapter 7.1 Units\n\n**Relu - rectified linear unit, also called the ReLU, y=max(z,0)\n\n\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\n**Classifier components**\n* Feature representation of input - which is a factor of features $[x_1,x_2,...x_n]$\n* Classification function which computs $\\hat{y}$ via p(y|x)\n* objective function for learning - usually minimizing error on training examples\n* algorithm for optimizing objective function\n* Sentiment classification: estimate P(y=1|x)\n\n**Logistic regression**\n* $z=\\sum\\limits_{i}w_ix_i + b$, or $z=w \\cdot x + b$\n\n**Sigmoid**\n* $y=1/(1+e^{-z})$\n* $P(y=1)= \\sigma (w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$\n* Decision boundary: $\\hat{y}=1$ if $P(y=1|x)>0.5$\n* How to get weights? (A) An loss function that tells us distance between the system output and the gold output; (B) stochastic gradient descent to minimize the loss function.\n* Cross-entropy loss: negative log likelihood loss (maximize likelihood = minimize loss ratio): $-ylog(\\hat{y}) - (1-y) log(1-\\hat{y})$ \n* with $\\hat{y} = \\sigma (w \\cdot x + b)$, we have $-ylog(\\sigma (w \\cdot x + b)) - (1-y) log(1-\\sigma (w \\cdot x + b))$\n* We want loss be smaller if the model’s estimate is close to correct, and loss to be bigger if it is confused.\n\n**Gradient descent**\n* Find weights and bias by minimizing loss: $\\hat{θ} = arg \\min\\limits_{θ} 1/m \\sum\\limits_{i=1}^{m} L_{CE} (y^{(i)},x^{(i)}; θ)$\n* Finds a minimum of a function by figuring out in which direction (in terms of θ) the function has the steepest slope, and moving in the opposite direction\n* For logistic regression: $L_{CE}(w,b) =- [ylog(\\sigma (w \\cdot x + b)) + (1-y) log(1-\\sigma (w \\cdot x + b))]$\n* $∂L_{CE}/∂W_j =  [\\sigma (w \\cdot x + b)-y]x_j$\n* $∂L_{CE}/∂b =  [\\sigma (w \\cdot x + b)-y]$\n* Cost over batch of data: $Cost(w,b) = -1/m \\sum\\limits_{i=1}^{m} y^{(i)} log(\\sigma (w \\cdot x^{(i)} + b)) + (1-y^{(i)}) log(1-\\sigma (w \\cdot x^{(i)} + b))$\n* Gradient for multiple points $∂ Cost(w,b)/∂W_j = \\sum\\limits_{i=1}^{m} [\\sigma (w \\cdot x^{(i)} + b)-y^{(i)}]x_j^{(i)}$\n\n**Regularization**\n* Penalize large weights. A regularization term is added to the loss function.\n* Lasso regression uses L1 regularization\n* Ridge regression uses L2 regularization\n\n**Feed-Forward Neural Network**\n* Simplest N.N.\n* Multilayer network, all units usually fully-connected, and no cycles.\n\n**Hidden Layer Computation**\n* Step 1: multiply the weight matrix by the input vector x,\n* Step 2. add the bias vector b, and\n* Step 3. apply the activation function g (such as Sigmoid)\n* Output h = σ(Wx+b), σ is sigmoid function\n\n**All layer**\n* Takes an input vector x, outputs a probability distribution y, and is parameterized by weight matrices W and U and a bias vector b:\n* h = σ(Wx+b)\n* z = Uh\n* y = softmax(z)\n\n**Backpropagation**\n* Related to general procedure called backward differentiation\n* Depends on the notion of computation graphs => process of computing a mathematical expression. Computation broken down to seperate operations, each represented by a node in a graph \n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "**Neural Language Models - advantage over n-gram LMs**\n",
        "* Advantage: (A)don’t need smoothing; (B)Can handle much longer histories; (C)Generalize over contexts of similar words (generalizes better as prior context is represented by embeddings); (D) Much higher predictive accuracy than n-gram models.\n",
        "* Disadvantage: slower to train than traditional n-gram LMs\n",
        "\n",
        "**Neural LM**\n",
        "* Input: k-gram of words $W_{1:k}$\n",
        "* Output: probability distribution over next word\n",
        "* The k context words are treated as a word window. Each word associated with an embedding vector\n",
        "\n",
        "**General**\n",
        "* polysemous: A word that has multiple meanings . We call each of these aspects of the meaning word sense.\n",
        "* Semantic field: set of words which cover a semantic domain and bear structured relations with each other\n",
        "* Connotation: effective meanings. Three dimensions: valence (pleasantness), arousal (intensity of emotion), dominance (degree of control)\n",
        "* Word embedding: representation of words for text analysis, in the form of a vector that encodes the meaning of the word -  words that are closer in the vector space are similar in meaning\n",
        "\n",
        "**Term-document matrix**\n",
        "* Document vectors can be sparse; \n",
        "* Rows: Documents\n",
        "* Columns: words (in entirely would be vocabulary)\n",
        "* Can measure similarity between two documents, by comparing their column vectors - can detect plagiarism\n",
        "* Can measure similarity between two words, by comparing two rows\n",
        "\n",
        "**vector comparison**\n",
        "<br>docx  doc y   ||u||\n",
        "<br>A       2       4       4.47\n",
        "<br>B       10       15       18.02\n",
        "<br>C       14       10       17.20\n",
        "\n",
        "**vector comparison - after normalize**\n",
        "<br>docx  doc y   ||u||\n",
        "<br>A       2/4.47    4/4.47       4.47\n",
        "<br>B       10/18.02       15/18.02       18.02\n",
        "<br>C       14/17.20       10/17.20       17.20\n",
        "\n",
        "**Cosine Distance**\n",
        "* $1- u \\cdot v/(||u||*||v||)$\n",
        "\n",
        "**Term-term matrix**\n",
        "* How often word A appears in a context surrounding word B\n",
        "* context windows: w-2, w-1, target_word, w+1, w+2\n",
        "\n",
        "**Alternatives to count**\n",
        "* Raw word frequency not a great measure of association between words: 'the' and 'of' are very frequent, but maybe not the most informative\n",
        "* common to transform vectors using TF-IDF or PPMI\n",
        "* TF-IDF: A sparse model. Term frequency (How often a word occurred in a document) * inverse document frequency (1/number of documents that it occured in)\n",
        "* how to get dense vectors? Train a classifier\n",
        "\n",
        "**Word2Vec (a dense model. GLoVE also a dense model)**\n",
        "* Learn embeddings as part of word prediction.\n",
        "* Train a classifier to predict neighboring words (is word A likely to be near word B)\n",
        "* Inspired by NN LMs\n",
        "* Learn dense embeddings for the words in the training corpus.\n",
        "* Advantages: easy to train (much faster than SVD - singular value decomposition); available online in the word2vec package\n",
        "* Skip-Gram Training Data: target, and +/- two words\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 270,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2af0e4d8-e1d5-4458-d8f3-4da008805153"
      },
      "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": 271,
      "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**Neural Language Models - advantage over n-gram LMs**\n* Advantage: (A)don’t need smoothing; (B)Can handle much longer histories; (C)Generalize over contexts of similar words (generalizes better as prior context is represented by embeddings); (D) Much higher predictive accuracy than n-gram models.\n* Disadvantage: slower to train than traditional n-gram LMs\n\n**Neural LM**\n* Input: k-gram of words $W_{1:k}$\n* Output: probability distribution over next word\n* The k context words are treated as a word window. Each word associated with an embedding vector\n\n**General**\n* polysemous: A word that has multiple meanings . We call each of these aspects of the meaning word sense.\n* Semantic field: set of words which cover a semantic domain and bear structured relations with each other\n* Connotation: effective meanings. Three dimensions: valence (pleasantness), arousal (intensity of emotion), dominance (degree of control)\n* Word embedding: representation of words for text analysis, in the form of a vector that encodes the meaning of the word -  words that are closer in the vector space are similar in meaning\n\n**Term-document matrix**\n* Document vectors can be sparse; \n* Rows: Documents\n* Columns: words (in entirely would be vocabulary)\n* Can measure similarity between two documents, by comparing their column vectors - can detect plagiarism\n* Can measure similarity between two words, by comparing two rows\n\n**vector comparison**\n<br>docx  doc y   ||u||\n<br>A       2       4       4.47\n<br>B       10       15       18.02\n<br>C       14       10       17.20\n\n**vector comparison - after normalize**\n<br>docx  doc y   ||u||\n<br>A       2/4.47    4/4.47       4.47\n<br>B       10/18.02       15/18.02       18.02\n<br>C       14/17.20       10/17.20       17.20\n\n**Cosine Distance**\n* $1- u \\cdot v/(||u||*||v||)$\n\n**Term-term matrix**\n* How often word A appears in a context surrounding word B\n* context windows: w-2, w-1, target_word, w+1, w+2\n\n**Alternatives to count**\n* Raw word frequency not a great measure of association between words: 'the' and 'of' are very frequent, but maybe not the most informative\n* common to transform vectors using TF-IDF or PPMI\n* TF-IDF: A sparse model. Term frequency (How often a word occurred in a document) * inverse document frequency (1/number of documents that it occured in)\n* how to get dense vectors? Train a classifier\n\n**Word2Vec (a dense model. GLoVE also a dense model)**\n* Learn embeddings as part of word prediction.\n* Train a classifier to predict neighboring words (is word A likely to be near word B)\n* Inspired by NN LMs\n* Learn dense embeddings for the words in the training corpus.\n* Advantages: easy to train (much faster than SVD - singular value decomposition); available online in the word2vec package\n* Skip-Gram Training Data: target, and +/- two words\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": "d6284d04-a0fc-4625-a1c1-43fbf5b4a134"
      },
      "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": 272,
      "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 Rational agent choose an action based on maximum expected utility (MEU), based on evidence e $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* Orderability (must have a preference)\n* Transitivity: A>B, B>C then A>C\n* Continuity: If A>B>C, ∃ p, such that [p,A:(1-p),C] ~ B\n* Substitutability\n* Monotonicity A>B => p>q <=> [p,A: 1-p, B]>[q,A: 1-q, B]\n* Decomposability\n \n\n## AIMA Chapter 16.3 Utility Functions\n\n* Optimizer's curse: estimated expect utility too high\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n**Stochastic Transition Model**\n* P(s' | s, a). Probability of reaching state s' from s, with action a\n\n**Markov Decision Process**\n* Sequential decision problem, fully observable, stochastic environment\n* Markovian transition model, additive rewards\n* Markovian means probability of reaching state s' from s depends only on s, not on earlier states\n\n**Policy**\n* Solution of what an agent should do for any state: π(s) for state s\n* Optimal policy: policy with highest expected utility, or π*\n\n**Finite vs. infinite horizons***\n* Finite: optimal action depends on how many times left, so policy is non-stationary (policies that depends on time)\n* Infinite: No reason to behave different in the smae state at different times, so stationary \n\n**Reward**\n* Can be additive reward\n* Or discounted rewward γ (between 0 and 1): U = R(s0)+*R(s1)+γ^2*R(s2)+...\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n**Bellman equation**\n* $V^*(s) = \\max\\limits_{a} Q^*(s,a)$\n* $V^*(s) = \\max\\limits_{a \\subseteq A(s)} \\sum_{s'} T(s,a,s') [R(s,a,s') + γ V^*(s')]$\n\n**Value iteration**\n* Non-linear Equations(due to max) => need an iterative appraoch\n* Start with arbitrary initial value, calculate RHS, plug into LHS - repeat until we reach equalibrium\n* Eventually converges to unique solutions\n* Policy loss: $U_{π_i}(s)$ - utility if we do $π_i$ in state s, $||U_{π_i}(s) - U||$ is policy loss (U is true utility)\n* Bellman update: $U_{i+1}(s) = \\max\\limits_{a \\subseteq A(s)} \\sum_{s'} P(s'|s,a) [R(s,a,s') + γ U_i (s')]$.\n* Slides version of Bellman update: $V_{k+1}(s) = \\max\\limits_{a} \\sum_{s'} T(s,a,s') [R(s,a,s') + γ V_k (s')]$.\n* Start with $V_0(s)=0$, repeat until convergence\n* (slides) complexity: $O(S^2 A)$ of each iteration\n\n**Policy iteration**\n* Step 1: Policy evaluation - calculate $U_{π_i}(s)$ based on policy $π_i$ (utility of each state)\n* Policy improvement: calculate new MEU policy $π_{i+1}$, with one-step look-ahead of $U_{π_i}$\n* Terminates when policy improvement yields no change in utilities\n* Slides version: $V^{\\pi}(s) = \\sum_{s'} T(s, \\pi (s), s') [R(s,\\pi (s),s') + γ V^{\\pi} (s')]$.\n* Textbook version: $U_i(s) = \\sum_{s'} P(s'|s, \\pi_i(s)) [R(s,\\pi_i(s),s') + γ U_i(s')]$\n* Benefit: a linear function\n* (slides): $O(S^2)$ per iteration\n* n-states: n linear equations with n unknowns, which can be solved in O(n^3) by linear algebra methods\n* Asynchronous policy iteration: pick any subset of states and apply policy improvement / simplified value iteration, guaranteed to find optimal policy (with conditions) => freedom to choose any state to update\n* Can compute actions from values using policy extraction: $\\pi^* (s) = arg \\max\\limits_{a} \\sum\\limits_{s'} T(s,a,s')[R(s,a,s') + γ V^* (s')]$\n* Can compute from Q-values, which is easier $\\pi^* (s) = arg \\max\\limits_{a} Q^*(s,a)$\n\n\n## Module 8 Lecture Notes\n\n**MDP\n* Probability of arriving at s' only depends on s and not history of earlist states (so Markovian transition)\n* MDP search trees: s is a state; (s,a) is a q-state, (s,a,s') is a transition - T(s,a,s')=P(s'|s,a)\n\n**Problem with value iteration**\n* It's slow $O(S^2 A)$ per iteration\n* Max at each state rarely changes\n* Policy often converges long before values\n\n**Comparison**\n* Value iteration: every iteration updates both values and (implicitly) policy - policy not tracked but taking max implicitly recomputes it\n* Policy iteration: after policy is evaluated, a new policy is chosen (still slow)\n\n**Algorithm summary**\n* Compute optimal value: use value iteration or policy iteration\n* Compute value for particular policy: policy evaluation\n* Turn value into policy: policy extraction\n\n\n\n## Module 8 Definitions\n* **Mdp** - Transition model (probabilistic outcome of actions) and reward function (for each state)\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n**General**\n* Exploitation: follow current best action to obtain rewards\n* Exploration: explore unknown states and actions to gain information\n* one-armed bandit: one arm generates arbitrary sequence of rewards; the other arm generates fixed rewards - First iteration takes O(n), and afterwards O(1)\n* Pull arm with highest Gittins index, then update the indices\n\n**Bernoulli bandit**\n* Each arm Mi has reward of 0 or 1, with a fixed but unknown probability μ_i.\n* State of arm Mi: si and fi, number successes (1s) and failures (0s) so far\n* Transition probability: predicts the next outcome based on information so far\n* The counts are initialized to 1 - initial probablity 1/2 and 1/2\n* The Markov reward process\n\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n \n**General**\n* Reinforcement learning: use observed rewards to learn optimal policy\n\n**Type of Agent**\n* Utility-based: learns utility function on states\n* Q-learning: learns action-utility function (Q-function)\n* Reflex agent - learns policy which maps from states to actions\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n**Passive learning**\n* Agent policy is fixed, but agent does not know transition model, or rewards function\n* Direct utility estimation: estimate utility based on samples, but missed information (from Bellman equation), converges very slowly\n* Adaptive dynamic programing: can learn the resulting state (output) from state-action pair (input). Better approaces than MLE are Bayesian reinforcement learning and robust control theory\n* Temporal-difference learning: after transition s->s', $U_π(s) = U_π (s) + α (R(s) + γ U_π(s') - U_π(s))$, where α is the learning rate. \n* Due to exponential moving average - makes more recent samples more important - we can decrease learning rate to give converging averages\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \n**Active learning**\n* Agent must learn what to do\n* Agent needs to learn model with outcome probability distributions associated w/ all actions \n* Obey Bellman equation, and can be solved using value iteration or policy iteration\n* Greedy agent - seldom converges to optimal policy\n* Solution: GILE: a simple one is to have the agent explorer a random action 1/t of the time, and follow current best policy otherwise\n\n**Exploration function**\n* U+(s) = R(s) + γ max (over a) f(Σ (over s') P(s'|s,a)U+(s'), N(s,a))\n* N(s,a) - # of times action a attempted in s\n* f(u,n) should be increasing in u but decreasing in n (if tried many attempts, then less useful to try again)\n\n**Q-learning**\n* Learns action-utility representation\n* Q(s,a) - value of action a in state s. $U(s) = \\max\\limits_a Q (s,a)$\n* Model-free method - does not need a transition model\n* Model: $Q(s,a) = Q(s,a) +  α (R(s) + γ \\max\\limits_{a'} Q(s',a') - Q(s,a))$\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n* Function approximation can compress a problem with too many states with something more managable. In chess - becomes a linear combination of chess pieces\n\n\n## Module 9 Lecture Notes\n\n**Reinforcement learning**\n* MDP is offline planning\n* Don't know T or R, but still look for policy π\n\n**Model-based learning**\n* Learn empirical MDP model (by counting outcomes s' for each s,a), discover R when we experience (s,a,s')\n* Then solve the learned MDP using value iteration\n\n**Active/Full reinforcement learning**\n* Don't know transition T(s,a,s'), or reward R(s,a,s')\n* Learn optimal policy/values\n* Tradeoff: exploration vs. exploitation\n\n**Q-value iteration**\n* $V_{k+1}(s) = \\max\\limits_{a} \\sum\\limits_{s'} T(s,a,s') [R(s,a,s') + γ V_k (s')]$.\n* A better D-tour: $Q_{k+1}(s,a) = \\sum\\limits_{s'} T(s,a,s') [R(s,a,s') + γ \\max\\limits_{a'} V_k (s')]$.\n\n**Q-learning**\n* Sample-based Q-value iteration\n* Learn Q(s,a) values as you go - update sample estimates\n* Converges to optimal policy - even if acting suboptimally: off-policy learning\n* Have to explore enough, eventually make the learning rate small enough, but not decrease it too quickly\n* In the limit, doesn't matter how you select actions\n\n**Random exploration**\n* Choose random actions ε greedy\n* Act randomly with (small) probability ε\n* Act on current policy with probability 1-ε\n* Lower ε over time to prevent from thrashing around\n\n**Exploration function**\n* Better than random action - explorer areas where badness is not yet established\n* $f(u,n)=u+k/n$\n* Regular Q-update: $Q (s,a) = _α [R(s,a,s') + γ \\max\\limits_{a'} Q(s',a')]$.\n* Modified Q-update: $Q (s,a) = _α [R(s,a,s') + γ \\max\\limits_{a'} f(Q(s',a'),N(s',a')]$.\n\n**Regret**\n* Diff between your (expected) rewards, and optimal (expected) rewards\n* Minimizing regret - requires optimaly learning to be optimal\n* Random exploration has higher regret than exploration functions\n\n**Appexomiate Q-learning**\n* Cannot get all Q values (can't learn every single state)\n* Using a feature representation - linear representation\n* Exact Q-learning: $Q(s,a) = Q(s,a)+ α [difference]\n* Approximate Q-learning: $w_i = w_i + α[difference]f_i(s,a)$, adjust weights of active features\n\n\n## Module 9 Definitions\n* **Regret** - number of additional mistakes (or total mistake cost) we make vs a clairvoyant who had the best prediction record\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \n* Sources of uncertainty: laziness, theoretical ignorance, practical ignorance\n* Decision theory = probability + utility\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n* sample space: set of all possible worlds\n* Kolmogorov's axioms - P (a v b) = P(a) + P(b) - P(a^b)\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n \n* marginal probability: probability distribution over a subset of variables or a single variable\n* marginalization - summing out\n* Inference: P (X | e) = α P (X, e) = α Σ (over y) P(X, e, y)\n\n\n## AIMA Chapter 12.4 Independence\n \n* Independence definition: P (X|Y) = P(X), or P(Y|X) = P(Y), or P(X,Y) = P(X)P(Y)\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n**Bayes Rule**\n* P(Y|X) = P(X|Y)P(Y) / P(X)\n* Generalized version with backgroudn evidence e P(Y|X,e) = P(X|Y,e)P(Y|e) / P(X|e)\n* With normalization: P(Y|X) = α P(X|Y)P(Y), where α = 1 / P(X)\n\n**Conditional independence**\n* Definition: X and Y are conditionally independent given Z <=> Any x,y,z P(x,y|z) = P(x|z)*P(y|z).\n* Equivalent definition: If x, y are conditionally independent given z <=> P(x|y,z) = P(x|z) <=> P(y|x,z) = P(y|z)\n* P(x|y,z) = P(x,y,z) | P(y,z) = [P(x,y|z) * P(z)] / [P(z)*P(y|z)] = [P(x|z)*P(y|z)*P(z)] / [P(z)*P(y|z)] = P(x|z)\n* We can prove P(y|x,z) = P(y|z) with similar methods.\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n \n**Naive Bayes model**\n* P(Cause,Effect_1,...,Effect_n) = P(Cause) Π (over i) P(Effect_i | Cause)\n* P(Cause|e) = α P(Cause) Π (over j) P(e_j| Cause): Probability of each cause (given environment e) = multiply the prior probability of such cause, by the product of the conditional probabilities of each observed effects given this cause (then normalize)\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n* Probability can do better than logical inference alone (so do not need to choose randomly)\n\n\n## SLP Chapter 3.1 N-Grams\n \n**N-grams**\n* P(w1:n) = P(w1)P(w2|w1)P(w3|w1:2)...P(wn|w1:n-1)\n* BIgram: only use the conditional probability of the previous ONE word, or P(wn|w1:n-1) alomst equals P(wn|wn-1)\n* Use log probabilities - to prevent numerical underflow\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n \n** Perplexity**\n* PP for short\n* Inverse probability of the test set (normalized by # of words): higher conditional probability => lower perplexity\n* Weighted average branching factor - # of possible next words that can follow a given word\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n* visualizing a language model by sampling\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n \n* Out of vocabulary (OOV) words (zeros!)\n\n\n## SLP Chapter 3.5 Smoothing\n \n** Smoothing**\n* Laplace Smoothing - add one to n-gram counts (Before we normalize) to avoid 0 probability\n* Add-k smoothing (both numerator and denominator)\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\n* Huge Language Models:\n* Stupid Backoff: simple algorithm with large language models\n\n\n## Module 10 Lecture Notes\n\n**General**\n* Chain rule: $P(x_1, x_2,...x_n) = ∏ \\limits_{i} P(X_i|x_1,...x_{i-1})$\n* Language model: a model that computes with $P(W) =P(w_1, w_2, ...w_n)$, or $P(w_n|w_1,w_2,...w_{n-1})$\n* Under Markov assumption, only depends on previous k words, $P(w_1, w_2,...w_n) = ∏ \\limits_{i}^{n} P(w_i|w_{i-k},...w_{i-1})$\n* Unigram - no history; bi-gram - 1 word history; tri-gram: 2-words history; 4-gram: 3-words history\n* Unigram model: $P(w_1 w_2...w_n) = ∏ \\limits_{i}^{n} P(w_i)$\n* Bigram model: $P(w_i|w_1 w_2...w_{i-1}) = P(w_i|w_{i-1})$\n* In practise, do everything in log space\n\n**Maximum Likehood Estimate**\n* A way to estimate conditional probability\n* Problem: Out of vocabulary items (OOV)\n\n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \n* Bayesian network: dependencies among variables\n* P(x1,...xn) = Π (i=1 to n) θ(x_i | parents (x_i))\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\n**Bayes Net**\n* P(x1,...xn) = Π (i=1 to n) θ(x_i | parents (x_i)), where θ is conditional probabilities (from joint distribution)\n* P(x1,...xn)= P(x_n|x_n-1,...x_1)P(x_n-1|...,x1) = Π (i=1 to n) P(x_i|x_i-1,....x_1)\n* We should number the nodes according to topological order, which case P(x_i|=Parents(x+i))\n* Bayes net can be more compact than full joint distribution (n*2^k vs. 2^n)\n\n**Conditional independence**\n* Variable - conditionally independent of non-descendants, given parents\n* Markov blanket: variable conditionally independent of all other nodes (given parents, children, and children's parents) \n\n**D-seperation (more general than Markov Chain)** \n* Whether set X conditionally independent of set Y, given set Z - check whether Z d-seperates X and Y\n* A variable's Markov blanket d-seperates it from other variables\n\n**D-seperation process**\n* Consider anchestrtal subgraph - X,Y,Z + their anchestors\n* Moral graph: add links between unlinked pair of nodes with common child\n* Replace directed links w/ undirected links\n* If Z blocks all paths between X and Y => Z d-seperates X and Y (X, Y conditionally independent, given Z)\n\n**Bayes nets Continous variables*\n* Discretization - devide values into several intervals (and now discrete)\n* Non-parametric\n* Hybrid - both discrete and continuous\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\n**Exact inference**\n* Inference by enumeration\n* Variable elimination algorithm - simple and efficient for answering individual queries - takes O(n^2)\n* Joint tree algorithm - takes O(n)\n\n\n## Module 11 Lecture Notes\n\n**Conditional independence**\n* $X \\perp Y$: for ∀ x, y, P(x,y)=P(x)P(y)\n* $X \\perp Y|Z$: for ∀ x, y, z, P(x,y|z)=P(x|z)P(y|z), or equivaelently ∀ x, y, z, P(x|z,y)=P(x|z)\n\n**Bayes Net**\n* $P(x_i|x_1,...x_{i-1})=P(x_i|parents(X_i))$\n\n**D-seperation**\n* Study independence properties for triples\n* Causal chains (x=>y=>z), P(x,y,z) = P(x)*P(y|x)*P(z|y): P(z|x,y) = P(x,y,z)|P(x,y)=(P(x)*P(y|x)*P(z|y))/(P(x)*P(y|x))=P(z|y).  So $X \\perp Z|Y$\n* Common Cause: (y=>x, and y=>z),P(x,y,z)=P(y)P(x|y)P(z|y): P(z|x,y)=P(x,y,z)|P(x,y)=(P(y)P(x|y)P(z|y))/(P(y)P(x|y))=P(z|y). So $X \\perp Z|Y$\n* Common effect (x=>z, y=>z): x, y are independent, but they're not conditionally independent given z, due to competition as explanation (Observing an effect activates influence between possible causes.)\n\n**Active vs. inactive**\n* Inactive for causal chain (blocks middle), common cause (block cause), or common effect (do not block common effect)\n* Need a single, inactive segment to block a path\n* Is $X_i$ and $X_j$ conditionally independent? Check all (undirected) paths between $X_i$ and $X_j$, If one more more path active, then conditional independence not guaranteed\n\n**Inference**\n* Given posterior probability, calculate most likely explanation\n* Inference by emuneration - slow, as you join up the whole joint distribution before you sum out the hidden variables\n* Variable elimination: Interleave joining and marginalizing, Still NP-hard, but usually much faster than inference by enumeration\n\n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\n**Type of learning**\n* Supervised: observe input-output (label) pairs, and learn the mapping\n* Unsupervised: learn pattern without explicit feedback: for example, clustering\n* Reinforcement learning: learn from reward and punishment\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n* Bias-variance tradeoff: choice between fitting training data well vs. generalizes better\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n* Decision tree\n* Happy-curve: more training data => better accuracy\n* Entropy: measure of uncertainty for random variable: more information => less entropy\n* Entropy: H(V) = Σ (over k) P(v_k) log 2 (1/P(v_k)) = -Σ (over k) P(v_k) log2 P(v_k)\n* H (Fair dice) = -(0.5log (2) 0.5+0.5log (2) 0.5)=1\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \n* Regularization - explicitly penalizes complex hypothesis\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \n* Decision tree - specific to a particular learning algorithm\n* Decision list - more general\n* Probably approximately correct (PAC) - hypothesis consistent with large enough training data - unlikely to be seriously wrong\n* PAC learning: returns hypothesis which are roughly correct\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n**Gradient descent**\n* Choose any starting point\n* Computer greadient - and move a small amount in the steepest downhill direction\n* Repeat until converge on a point\n* $W_i = W_i - α * ∂/∂W_i Loss (W)$\n* α is the step size, or learning rate - can be fixed or decrease over time\n\n**Multi-variate linear regression**\n* Normal equation w* = (XT X)^-1 XT y\n\n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\n* naive Bayes classifier\n* c_hat= argmax (c ∈ C) P(c|d) = argmax P(d|c) * P(c) (we can drop denominator p(d))\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n**General**\n* Bayes rule lets us do diagnostic queries with causal probabilities\n* Naïve Bayes: Assume all features are independent effects of the class label\n* General Naïve Bayes model: $P(Y, F_1, ...F_n)=P(Y) \\prod\\limits_{i} P(F_i)|Y)$\n* We can build classifiers out of a naïve Bayes model using training data \n\n**Bag-of-words Naïve Bayes**\n* Features: $W_i$ is the word at positon i\n* As before: predict label conditioned on feature variables (spam vs. ham)\n* As before: assume features are conditionally independent given label\n* New: each $W_i$ is identically distributed\n* Called “bag-of-words” because model is insensitive to word order or reordering\n* All positions share the same conditional probs P(W|Y)\n\n**Training**\n* training set (for training)\n* held out set: practice exam\n* test set: final exam\n\n**Smoothing**\n* Laplace (add 1): often performs poorly for P(X|Y) when |X| is large, or when |Y| is ver large\n* Linear interpolation $P_{LIN} (x|y) = α \\hat{P}(x|y)+ (1-α) \\hat{P}(x)$\n\n**Linear classifier**\n* Inputs are feature values\n* Each feature has a weight\n* Sum is the activation\n\n**Learning - binary perception**\n* classify w/ current weight\n* If correct (i.e., y=y*), no change!\n* If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1. w=w+y*f\n\n**Multiclass Decision Rule**\n* we have weight vector $w_y$\n* score (activation) of a class y: $w_y * f(x)$\n* prediction highest score wins $y=arg \\max\\limits_{y} w_y * f(x)$\n* start w/ all 0 weights\n* pick up training example one by one\n* predict current weights using $y=arg \\max\\limits_{y} w_y * f(x)$\n* if correct, no change, if wrong - lower score of wrong answer,raise score of right answer: $w_y = w_y - f(x)$, $w_{y*} = w_{y*} + f(x)$\n\n**Perception**\n* Weights, bias and dot products\n* if w*x+b>0, output 1, otherwise 0\n\n**Perception problem**\n* noise: if the data isn’t separable, weights might thrash\n* Mediocre generalization: finds a “barely” separating solution\n* Overtraining: test / held-out accuracy usually rises, then falls\n* Solution: MIRA (Margin Infused Relaxed Algorithm): choose an update size that fixes the current mistak, but, minimizes the change to w (minimum correcting update)\n* In practice, also bad to make updates that are too large, so cap with a constant C\n* SVM(Support Vector Machines): Maximizing the margin: good according to intuition, theory, practice (finds seperator with max margin)\n* In both MIRA and SVM - optimize over all examples at once\n\n**Naïve Bayes vs. Perceptrons/MIRA**\n* Naïve Bayes: Strong assumptions about feature independence; One pass through data (counting)\n* Perceptrons: makes less assumptions; mistake-driven learning; multiple-passes through data (prediction), often more accurate\n\n**XOR problem**\n* A single neural unit cannot be used to compute the XOR function\n\n**Activation Functions**\n* Sigmoid\n* tanh: Hyperbolic tangent, $(e^{2x}-1)/(e^{2x}+1)$\n* rectified linear unit ReLU\n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \n**Logistic Regression**\n* logistic regression is a discriminative classifier - only try to learn to distinguish the classes\n* Naive Bayes is a generative classifier - try to understand differences between classes\n* logistic regression - probabilistic classifier, use supervised machine learning (same as Bayes)\n* Has training & testing\n\n**Four components for classification with ML**\n* Feature representation of input\n* Classification function which computes y_hat (estimated class), via P(y|x) - can use sigmoid or softmax\n* Objective function for learning: cross-entropy loss function\n* Optimization Algorithm: stochastic gradient descent\n\n**Classification with Sigmoid function**\n* The sigmoid function σ(z) = 1/(1+e^-z) takes any value and maps it to the range [0;1].\n* z=w*x+b (dot product), where b is biased term\n* Need a boundary value\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n\n* Objective: learn parameters (w and b) that make y_hat for each training set as close to true y as possible.\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\n* $L(\\hat{y}, y) = \\hat{y}$ differs from the true y\n* Choose w,b s.t. we maximize the log probability of the true y in the training data, given the observations x.\n* Cross-entropy loss: negative log likelihood loss\n* $p(y|x) = \\hat{y}|^y * (1 - \\hat{y})^(1-y)$\n* Take log: $ylog(\\hat{y}) + (1-y) log(1-\\hat{y})$\n* To minimize loss, flip the sign: $-ylog(\\hat{y}) - (1-y) log(1-\\hat{y})$\n\n\n## SLP Chapter 5.4 Gradient Descent\n \n**How Gradient descent work - Find the gradient of the loss function and move in the opposite direction**\n* Choose any starting point\n* Computer gradient - and move a small amount in the steepest downhill direction\n* Repeat until converge on a point\n\n\n## SLP Chapter 5.5 Regularization\n\n* Add -α R(q) (regulationzation term) to avoid over-fitting\n* L2 regularization - Σ θj^2 - Euclidean distance\n* L1 regularization - Σ |θj| - Manhattan distance\n\n\n## SLP Chapter 5.6 Multinomial logistic regression\n\n**multinomial logistic regression, a.k.a. softmax regression**\n* Uses a generalization of the sigmoid\n* softmax$(z_i) = e^{z_i} / (\\sum\\limits_{j=1}^{k} e^{z_j})$, for $1 \\leq i \\leq k$\n* softmax normalizes the output and turns it into a probability distribution.\n\n\n## SLP Chapter 7.1 Units\n\n**Relu - rectified linear unit, also called the ReLU, y=max(z,0)\n\n\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\n**Classifier components**\n* Feature representation of input - which is a factor of features $[x_1,x_2,...x_n]$\n* Classification function which computs $\\hat{y}$ via p(y|x)\n* objective function for learning - usually minimizing error on training examples\n* algorithm for optimizing objective function\n* Sentiment classification: estimate P(y=1|x)\n\n**Logistic regression**\n* $z=\\sum\\limits_{i}w_ix_i + b$, or $z=w \\cdot x + b$\n\n**Sigmoid**\n* $y=1/(1+e^{-z})$\n* $P(y=1)= \\sigma (w \\cdot x + b) = 1/(1+e^{-(w \\cdot x + b)})$\n* Decision boundary: $\\hat{y}=1$ if $P(y=1|x)>0.5$\n* How to get weights? (A) An loss function that tells us distance between the system output and the gold output; (B) stochastic gradient descent to minimize the loss function.\n* Cross-entropy loss: negative log likelihood loss (maximize likelihood = minimize loss ratio): $-ylog(\\hat{y}) - (1-y) log(1-\\hat{y})$ \n* with $\\hat{y} = \\sigma (w \\cdot x + b)$, we have $-ylog(\\sigma (w \\cdot x + b)) - (1-y) log(1-\\sigma (w \\cdot x + b))$\n* We want loss be smaller if the model’s estimate is close to correct, and loss to be bigger if it is confused.\n\n**Gradient descent**\n* Find weights and bias by minimizing loss: $\\hat{θ} = arg \\min\\limits_{θ} 1/m \\sum\\limits_{i=1}^{m} L_{CE} (y^{(i)},x^{(i)}; θ)$\n* Finds a minimum of a function by figuring out in which direction (in terms of θ) the function has the steepest slope, and moving in the opposite direction\n* For logistic regression: $L_{CE}(w,b) =- [ylog(\\sigma (w \\cdot x + b)) + (1-y) log(1-\\sigma (w \\cdot x + b))]$\n* $∂L_{CE}/∂W_j =  [\\sigma (w \\cdot x + b)-y]x_j$\n* $∂L_{CE}/∂b =  [\\sigma (w \\cdot x + b)-y]$\n* Cost over batch of data: $Cost(w,b) = -1/m \\sum\\limits_{i=1}^{m} y^{(i)} log(\\sigma (w \\cdot x^{(i)} + b)) + (1-y^{(i)}) log(1-\\sigma (w \\cdot x^{(i)} + b))$\n* Gradient for multiple points $∂ Cost(w,b)/∂W_j = \\sum\\limits_{i=1}^{m} [\\sigma (w \\cdot x^{(i)} + b)-y^{(i)}]x_j^{(i)}$\n\n**Regularization**\n* Penalize large weights. A regularization term is added to the loss function.\n* Lasso regression uses L1 regularization\n* Ridge regression uses L2 regularization\n\n**Feed-Forward Neural Network**\n* Simplest N.N.\n* Multilayer network, all units usually fully-connected, and no cycles.\n\n**Hidden Layer Computation**\n* Step 1: multiply the weight matrix by the input vector x,\n* Step 2. add the bias vector b, and\n* Step 3. apply the activation function g (such as Sigmoid)\n* Output h = σ(Wx+b), σ is sigmoid function\n\n**All layer**\n* Takes an input vector x, outputs a probability distribution y, and is parameterized by weight matrices W and U and a bias vector b:\n* h = σ(Wx+b)\n* z = Uh\n* y = softmax(z)\n\n**Backpropagation**\n* Related to general procedure called backward differentiation\n* Depends on the notion of computation graphs => process of computing a mathematical expression. Computation broken down to seperate operations, each represented by a node in a graph \n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\n\n**Neural Language Models - advantage over n-gram LMs**\n* Advantage: (A)don’t need smoothing; (B)Can handle much longer histories; (C)Generalize over contexts of similar words (generalizes better as prior context is represented by embeddings); (D) Much higher predictive accuracy than n-gram models.\n* Disadvantage: slower to train than traditional n-gram LMs\n\n**Neural LM**\n* Input: k-gram of words $W_{1:k}$\n* Output: probability distribution over next word\n* The k context words are treated as a word window. Each word associated with an embedding vector\n\n**General**\n* polysemous: A word that has multiple meanings . We call each of these aspects of the meaning word sense.\n* Semantic field: set of words which cover a semantic domain and bear structured relations with each other\n* Connotation: effective meanings. Three dimensions: valence (pleasantness), arousal (intensity of emotion), dominance (degree of control)\n* Word embedding: representation of words for text analysis, in the form of a vector that encodes the meaning of the word -  words that are closer in the vector space are similar in meaning\n\n**Term-document matrix**\n* Document vectors can be sparse; \n* Rows: Documents\n* Columns: words (in entirely would be vocabulary)\n* Can measure similarity between two documents, by comparing their column vectors - can detect plagiarism\n* Can measure similarity between two words, by comparing two rows\n\n**vector comparison**\n<br>docx  doc y   ||u||\n<br>A       2       4       4.47\n<br>B       10       15       18.02\n<br>C       14       10       17.20\n\n**vector comparison - after normalize**\n<br>docx  doc y   ||u||\n<br>A       2/4.47    4/4.47       4.47\n<br>B       10/18.02       15/18.02       18.02\n<br>C       14/17.20       10/17.20       17.20\n\n**Cosine Distance**\n* $1- u \\cdot v/(||u||*||v||)$\n\n**Term-term matrix**\n* How often word A appears in a context surrounding word B\n* context windows: w-2, w-1, target_word, w+1, w+2\n\n**Alternatives to count**\n* Raw word frequency not a great measure of association between words: 'the' and 'of' are very frequent, but maybe not the most informative\n* common to transform vectors using TF-IDF or PPMI\n* TF-IDF: A sparse model. Term frequency (How often a word occurred in a document) * inverse document frequency (1/number of documents that it occured in)\n* how to get dense vectors? Train a classifier\n\n**Word2Vec (a dense model. GLoVE also a dense model)**\n* Learn embeddings as part of word prediction.\n* Train a classifier to predict neighboring words (is word A likely to be near word B)\n* Inspired by NN LMs\n* Learn dense embeddings for the words in the training corpus.\n* Advantages: easy to train (much faster than SVD - singular value decomposition); available online in the word2vec package\n* Skip-Gram Training Data: target, and +/- two words\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}