{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ea3ee0dd-4323-4f20-b943-ee7fca7486b4"
      },
      "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": 67,
      "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": "bf4524a6-2efb-47c2-f6d3-7fb4c8736a63"
      },
      "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": 68,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 69,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"\n",
        "- **orderability**: exactly one of (A>B), (B>A), (A~B) holds\n",
        "- **transivity**: (A>B) and (B>A) => (A>C)\n",
        "- **continuity**: A>B>C => exists p, [p,A; 1-p,C]~B\n",
        "- **substitutability**: (A ~ B) => [p,A; 1-p,C]~[p,B; 1-p,C]\n",
        "- **monotonicity**: A>B=>(p>q <=> [p,A; 1-p,B]>[q,A; 1-q,B])\n",
        "- **decomposibility**: [p,A; 1-p,[q,B; 1-q,C]]~[p,A; (1-p)q,B; (1-p)(1-q),C]\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "- utility on economics\n",
        "\n",
        "  - people prefer more money than less, which is a **monotonic preference**\n",
        "  -**expected monetary value** (EMV): utility is not directly proportional to monetary value (but proportional to the log of value)\n",
        "  -**risk-averse**: prefer sure thing with payoff that is less than the EMV of a gamble\n",
        "  -**risk-seeking**: prefer unsure thing with payoff that is more than the EMV of a gamble\n",
        "  -**certainty equivalent**: the value an agent will accept in a gamble\n",
        "  -**insurance preminum**: EMV - certainty equivalent (risk-aversion->insurance industry)\n",
        "  -**risk netural**: gambles with small sums expect risk-netural\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "- **Markov decision process (MDP)**\n",
        "\n",
        "  - a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards \n",
        "  - consists of:\n",
        "\n",
        "    - a set of states, a set of actions in each state, a transition model $P(s'|s,a)$, and a reward function $A(s,a,s')$\n",
        "\n",
        "  - **policy**: what agent should do for any state that the agent might reach $\\\\pi(x)$\n",
        "\n",
        "    - the quality of a policy is measured by the expected utility of possible environment histories generated by that policy\n",
        "\n",
        "- **finite horizon**: there is a fixed time N after that the game is over\n",
        "\n",
        "  - **nonstationary**: a policy that depends on how much time is left\n",
        "\n",
        "- **infinite horizon**: there is no time limit\n",
        "\n",
        " - **stationary**: a policy that only depends on the current state\n",
        "\n",
        "- **discount factor $\\\\gamma$**: the performance of the agent for current rewards over future ones\n",
        "\n",
        "- **proper policy**: a policy that is guaranteed to reach a terminal state\n",
        "\n",
        "- **Bellman equation**: $U(s) = \\\\max_{a\\\\in A(s)} \\\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\\\gamma U(s')] $\n",
        "\n",
        "- **Q function**: $Q(s,a)=\\\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\\\gamma U(s')]$\n",
        "\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "- **value iteration** ($O(S^2A)$): if there are n possible states, then apply n times Bellman equation\n",
        "\n",
        "  - **Bellman update** ($O(S^2)$): $U_{i+1}(s) = \\\\max_{a\\\\in A(s)} \\\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\\\gamma U_i(s')] $\n",
        "  - will converge eventually\n",
        "  - problems:\n",
        "\n",
        "    - too slow\n",
        "    - max at each state rarely changes\n",
        "    - policy often converges before values\n",
        "  - Contraction: part of the proof of convergence for the value iteration algorithm.\n",
        "\n",
        "- **policy iteration**: \n",
        "\n",
        "  - **policy evaluation**: calculate utilties for some fixed policy until convergence\n",
        "    \n",
        "  -> $U_{i+1}(s) =  \\\\sum_{s'} P(s'|s,\\\\pi_i(s))[R(s,\\\\pi_i(s),s')+\\\\gamma U_i(s')] $\n",
        "\n",
        "  - **policy improvement**: update policy value using one-step looking ahead with resulting converged utilities as future value\n",
        "\n",
        "  -> $\\\\pi_{i+1}(s) =  argmax_{a} \\\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\\\gamma U_i(s')] $\n",
        "\n",
        "  - repeat until policy converage\n",
        "  \n",
        "  - remove max, equation turns linear, faster than value iteration\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "- if we assume **stationary preference**, there are only two ways to define utilities\n",
        "\n",
        "  - additive and discounted\n",
        "\n",
        "- infinite utility:\n",
        "\n",
        "  - finite horizon (limited time)\n",
        "  - discounting\n",
        "  - absorbing state: guarantee that for every policy, a terminal state would be eventually reached\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"agent's preference\",\n",
        "\"expected utility\" : \"the average utility value of the outcomes\",\n",
        "\"maximum expected utility (MEU)\": \"rational agent should choose the action that maximizes the agent's expected utility\",\n",
        "\"preference elicitation\": \"find out the utility function of humans\",\n",
        "\"unbias\": \"expected value of error is zero\",\n",
        "\"normative theory\": \"how a rational agent should act\",\n",
        "\"descriptive theory\": \"how an actual agent really act\",\n",
        "\"certainty effect\": \"people are strongly attracted to gains that are certain\",\n",
        "\"ambiguity aversion\": \"people choose the known probability rather than the unknown\",\n",
        "\"framing effect\": \"the wording of a decsion problem may impact agent's decision\",\n",
        "\"anchoring effect\": \"prefer making relative untility judgement than absolute one\",\n",
        "\"Markovian\": \"the probability of reaching s' from s depends only on s and not the history of early states\",\n",
        "\"environment history\": \"sequence of states and actions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 70,
      "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
        },
        "cellView": "form",
        "outputId": "ececf6c4-196c-431c-a5a2-d0cd2e167545"
      },
      "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": 71,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- **orderability**: exactly one of (A>B), (B>A), (A~B) holds\n- **transivity**: (A>B) and (B>A) => (A>C)\n- **continuity**: A>B>C => exists p, [p,A; 1-p,C]~B\n- **substitutability**: (A ~ B) => [p,A; 1-p,C]~[p,B; 1-p,C]\n- **monotonicity**: A>B=>(p>q <=> [p,A; 1-p,B]>[q,A; 1-q,B])\n- **decomposibility**: [p,A; 1-p,[q,B; 1-q,C]]~[p,A; (1-p)q,B; (1-p)(1-q),C]\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- utility on economics\n\n  - people prefer more money than less, which is a **monotonic preference**\n  -**expected monetary value** (EMV): utility is not directly proportional to monetary value (but proportional to the log of value)\n  -**risk-averse**: prefer sure thing with payoff that is less than the EMV of a gamble\n  -**risk-seeking**: prefer unsure thing with payoff that is more than the EMV of a gamble\n  -**certainty equivalent**: the value an agent will accept in a gamble\n  -**insurance preminum**: EMV - certainty equivalent (risk-aversion->insurance industry)\n  -**risk netural**: gambles with small sums expect risk-netural\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- **Markov decision process (MDP)**\n\n  - a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards \n  - consists of:\n\n    - a set of states, a set of actions in each state, a transition model $P(s'|s,a)$, and a reward function $A(s,a,s')$\n\n  - **policy**: what agent should do for any state that the agent might reach $\\pi(x)$\n\n    - the quality of a policy is measured by the expected utility of possible environment histories generated by that policy\n\n- **finite horizon**: there is a fixed time N after that the game is over\n\n  - **nonstationary**: a policy that depends on how much time is left\n\n- **infinite horizon**: there is no time limit\n\n - **stationary**: a policy that only depends on the current state\n\n- **discount factor $\\gamma$**: the performance of the agent for current rewards over future ones\n\n- **proper policy**: a policy that is guaranteed to reach a terminal state\n\n- **Bellman equation**: $U(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')] $\n\n- **Q function**: $Q(s,a)=\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- **value iteration** ($O(S^2A)$): if there are n possible states, then apply n times Bellman equation\n\n  - **Bellman update** ($O(S^2)$): $U_{i+1}(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')] $\n  - will converge eventually\n  - problems:\n\n    - too slow\n    - max at each state rarely changes\n    - policy often converges before values\n  - Contraction: part of the proof of convergence for the value iteration algorithm.\n\n- **policy iteration**: \n\n  - **policy evaluation**: calculate utilties for some fixed policy until convergence\n    \n  -> $U_{i+1}(s) =  \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')] $\n\n  - **policy improvement**: update policy value using one-step looking ahead with resulting converged utilities as future value\n\n  -> $\\pi_{i+1}(s) =  argmax_{a} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')] $\n\n  - repeat until policy converage\n  \n  - remove max, equation turns linear, faster than value iteration\n\n\n## Module 8 Lecture Notes\n\n- if we assume **stationary preference**, there are only two ways to define utilities\n\n  - additive and discounted\n\n- infinite utility:\n\n  - finite horizon (limited time)\n  - discounting\n  - absorbing state: guarantee that for every policy, a terminal state would be eventually reached\n\n\n## Module 8 Definitions\n* **Utility function** - agent's preference\n* **Expected utility** - the average utility value of the outcomes\n* **Maximum expected utility (meu)** - rational agent should choose the action that maximizes the agent's expected utility\n* **Preference elicitation** - find out the utility function of humans\n* **Unbias** - expected value of error is zero\n* **Normative theory** - how a rational agent should act\n* **Descriptive theory** - how an actual agent really act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - people choose the known probability rather than the unknown\n* **Framing effect** - the wording of a decsion problem may impact agent's decision\n* **Anchoring effect** - prefer making relative untility judgement than absolute one\n* **Markovian** - the probability of reaching s' from s depends only on s and not the history of early states\n* **Environment history** - sequence of states and actions\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",
        "- **exploitation**: current best actions\n",
        "- **exploration**: previous unknown states\n",
        "- **bandit problem**: each arm $M_i$ is a **Markov reward process** (an MDP with only one possible action $a_i$)\n",
        "- **Gittins index**: the maximum obtainable utility per unit of discounted time\n",
        "\n",
        "  - pull the arms with the highest Gittins index\n",
        "\n",
        "- Bernoulli brandit: each arm produces either 0 or 1 with a fixed but unknown probability\n",
        "- Bandit superprocess (BSP): each arm is a full MDP, for **multi-tasking**\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "- **reinforcement learning**: agent periodically receives rewards that reflects how well it is doing\n",
        "- **model-based RL**: use a transition model to help interpret the reward signals\n",
        "\n",
        "  - step 1: learn empirical MDP model\n",
        "  - step 2: solved the learned MDP problem\n",
        "- **model-free RL**: \n",
        "  \n",
        "  - **action-utility learning**: action utitlity learning: **Q-learning**\n",
        "  - **policy search**: agent learns a policy that directly maps states from actions \n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" \n",
        "- **passive reinforcement learning**: policy evaluation\n",
        "\n",
        "  - fully observable environment, a fixed policy $\\\\pi(s)$ that determines actions\n",
        "  - unknown $P(s'|s,a)$ and $R(s,a,s')$\n",
        "  - try to learn $U^{\\\\pi}(s)$\n",
        "\n",
        "- **direct utility estimation**: the utility of a state is defined as the expected total reward from that state onward (**reward-to-go**)\n",
        "\n",
        "  - compute values for each state under $\\\\pi$, compute the average over the sample\n",
        "  - ignore the connections between states -> miss the opportunities for learning\n",
        "\n",
        "- **sample-based policy evaluation**: takes the samples of outcome s' and then average\n",
        "\n",
        "  - $sample_1 = R(s,\\\\pi_i(s),s_1')+\\\\gamma U^{\\\\pi}_k(s_1')$\n",
        "  - $sample_2 = R(s,\\\\pi_i(s),s_2')+\\\\gamma U^{\\\\pi}_k(s_2')$\n",
        "  - $U^{\\\\pi}_{k+1}=avg(samples)$\n",
        "\n",
        "- **adaptive dynamic programming**: use the learned transition model and observed rewards\n",
        "\n",
        "  - to learn transition model: $P(s'|s,a)$ is represented as a table, and estimated directly from the counts that are accumulated in N_{s'|sa}\n",
        "  - the count records how ofter s' is reached when executing a in s\n",
        "\n",
        "- **temporal-difference learning**: use observed transition to adjust the utilities of the observed states\n",
        "\n",
        "  - $sample=R(s,\\\\pi_i(s),s')+\\\\gamma U^{\\\\pi}(s')$\n",
        "  - **temporal-difference equation**: $U^{\\\\pi}(s) =  U^{\\\\pi}(s)+\\\\alpha (sample-U^{\\\\pi}(s))= (1-\\\\alpha)U^{\\\\pi}(s)+\\\\alpha sample$\n",
        "  - $\\\\alpha$ is the learning rate\n",
        "  - use the difference between the successive states\n",
        "  - $R(s,\\\\pi_i(s),s')+\\\\gamma U^{\\\\pi}(s')-U^{\\\\pi}(s)$ is an error signal, and the update is intended to reduce the error\n",
        "  - **problem**: can't turn values into a new policy\n",
        "\n",
        "- TD adjusts a state to agree with its observed successor, ADP adjusts the state to agree with all of the successors that might occur, weighted by their probabilities\n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "- **active reinforcement learning**: decide what actions to take (learn optional policies)\n",
        "\n",
        "  - learn a complete transition model with outcome probabilities for all actions, not just the fixed policy\n",
        "\n",
        "- **greedy in the limit of infinite exploration (GLIE)**: try infinite times to find the optimal solution\n",
        "- since in reality some actions are irreversible, we need to choose a policy that is reasonbly well for the whole range of models\n",
        "  that have chance of being the true model, even if the policy happens to be suboptimal\n",
        "\n",
        "  - **Bayesian reinforcement learning**\n",
        "  - **robust control theory**\n",
        "\n",
        "- **Q-learning**: avoids the need for a transition model, by learning an action-utility function Q(s,a) instead of a utility function U(s)\n",
        "\n",
        "  - $Q(s,a)=\\\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\\\gamma max_{a'}Q_k(s',a')]$\n",
        "  - Q(s,a) denotes total discounted reward if agent takes action a in s and acts optimally afterward\n",
        "  - $sample=R(s,a,s')+\\\\gamma \\\\max_{a'}Q(s',a')$\n",
        "  - $ Q(s,a) =  (1-\\\\alpha)Q(s,a)+\\\\alpha sample $\n",
        "  - **Q-learning** converges to optimal policy, even if you act suboptimally  \n",
        "  - **off-policy**: stops the current policy and uses the one that choose the best action\n",
        "  - caveat:\n",
        "  \n",
        "    - have to explore enough\n",
        "    - eventually make learning rate small enough, but not decrease it too quickly \n",
        "\n",
        "- **SARSA**(state, action, reward, state, action): close relative of Q-learning\n",
        "\n",
        "  - $Q(s,a) =  Q(s,a)+\\\\alpha [R(s,a,s')+\\\\gamma Q(s',a')-Q(s,a)] $\n",
        "  - **on-policy**: stick with the current policy \n",
        "  - may get penaltized when exploration\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "- **function approximation**: constructing a compact approximation of true utility function or Q-function\n",
        "- linear approximation\n",
        "  - $U(s) = w_1 f_1(s) + ... + w_n f_n(s)$\n",
        "  - $Q(s,s) = w_1 f_1(s,a) + ... + w_n f_n(s,a)$\n",
        "    - pros: easy\n",
        "    - cons: states may share features but be very different in value\n",
        "  -> $w_i=w_i+\\\\alpha (R(s,a,s')+\\\\gamma \\\\max_{a'}Q(s',a')-Q(s,a)) f_i(s,a)$\n",
        "  - **approximating direct utility estimation**\n",
        "  - **approximating temporal-difference learning**\n",
        "    - **catastrophic forgetting** and **experience replay** (keep reliving crashing behaviors at regular intervals)\n",
        "- nonlinear approximation\n",
        "- **hierachical reinforcement learning (HRL)**\n",
        "- **policy search**\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "- **regret**: a measure of total mistake cost (difference between expected rewards and optimal rewards)\n",
        "  - random exploration has a higher regret\n",
        "  - The relative goodness of exploration procedures.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"sparse reward\" : \"in most states the agent is given no reward signal at all\",\n",
        "\"greedy agent\": \"greedily takes the action that it currently believes to be the optimal at each step\",\n",
        "\"absorbing state\": \"no action has any effect and no rewards are received\"\n",
        "}"
      ],
      "execution_count": 72,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ac29bf56-4b2f-4c40-c311-925e8dce3e4c"
      },
      "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": 73,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- **exploitation**: current best actions\n- **exploration**: previous unknown states\n- **bandit problem**: each arm $M_i$ is a **Markov reward process** (an MDP with only one possible action $a_i$)\n- **Gittins index**: the maximum obtainable utility per unit of discounted time\n\n  - pull the arms with the highest Gittins index\n\n- Bernoulli brandit: each arm produces either 0 or 1 with a fixed but unknown probability\n- Bandit superprocess (BSP): each arm is a full MDP, for **multi-tasking**\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- **reinforcement learning**: agent periodically receives rewards that reflects how well it is doing\n- **model-based RL**: use a transition model to help interpret the reward signals\n\n  - step 1: learn empirical MDP model\n  - step 2: solved the learned MDP problem\n- **model-free RL**: \n  \n  - **action-utility learning**: action utitlity learning: **Q-learning**\n  - **policy search**: agent learns a policy that directly maps states from actions \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n- **passive reinforcement learning**: policy evaluation\n\n  - fully observable environment, a fixed policy $\\pi(s)$ that determines actions\n  - unknown $P(s'|s,a)$ and $R(s,a,s')$\n  - try to learn $U^{\\pi}(s)$\n\n- **direct utility estimation**: the utility of a state is defined as the expected total reward from that state onward (**reward-to-go**)\n\n  - compute values for each state under $\\pi$, compute the average over the sample\n  - ignore the connections between states -> miss the opportunities for learning\n\n- **sample-based policy evaluation**: takes the samples of outcome s' and then average\n\n  - $sample_1 = R(s,\\pi_i(s),s_1')+\\gamma U^{\\pi}_k(s_1')$\n  - $sample_2 = R(s,\\pi_i(s),s_2')+\\gamma U^{\\pi}_k(s_2')$\n  - $U^{\\pi}_{k+1}=avg(samples)$\n\n- **adaptive dynamic programming**: use the learned transition model and observed rewards\n\n  - to learn transition model: $P(s'|s,a)$ is represented as a table, and estimated directly from the counts that are accumulated in N_{s'|sa}\n  - the count records how ofter s' is reached when executing a in s\n\n- **temporal-difference learning**: use observed transition to adjust the utilities of the observed states\n\n  - $sample=R(s,\\pi_i(s),s')+\\gamma U^{\\pi}(s')$\n  - **temporal-difference equation**: $U^{\\pi}(s) =  U^{\\pi}(s)+\\alpha (sample-U^{\\pi}(s))= (1-\\alpha)U^{\\pi}(s)+\\alpha sample$\n  - $\\alpha$ is the learning rate\n  - use the difference between the successive states\n  - $R(s,\\pi_i(s),s')+\\gamma U^{\\pi}(s')-U^{\\pi}(s)$ is an error signal, and the update is intended to reduce the error\n  - **problem**: can't turn values into a new policy\n\n- TD adjusts a state to agree with its observed successor, ADP adjusts the state to agree with all of the successors that might occur, weighted by their probabilities\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- **active reinforcement learning**: decide what actions to take (learn optional policies)\n\n  - learn a complete transition model with outcome probabilities for all actions, not just the fixed policy\n\n- **greedy in the limit of infinite exploration (GLIE)**: try infinite times to find the optimal solution\n- since in reality some actions are irreversible, we need to choose a policy that is reasonbly well for the whole range of models\n  that have chance of being the true model, even if the policy happens to be suboptimal\n\n  - **Bayesian reinforcement learning**\n  - **robust control theory**\n\n- **Q-learning**: avoids the need for a transition model, by learning an action-utility function Q(s,a) instead of a utility function U(s)\n\n  - $Q(s,a)=\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q_k(s',a')]$\n  - Q(s,a) denotes total discounted reward if agent takes action a in s and acts optimally afterward\n  - $sample=R(s,a,s')+\\gamma \\max_{a'}Q(s',a')$\n  - $ Q(s,a) =  (1-\\alpha)Q(s,a)+\\alpha sample $\n  - **Q-learning** converges to optimal policy, even if you act suboptimally  \n  - **off-policy**: stops the current policy and uses the one that choose the best action\n  - caveat:\n  \n    - have to explore enough\n    - eventually make learning rate small enough, but not decrease it too quickly \n\n- **SARSA**(state, action, reward, state, action): close relative of Q-learning\n\n  - $Q(s,a) =  Q(s,a)+\\alpha [R(s,a,s')+\\gamma Q(s',a')-Q(s,a)] $\n  - **on-policy**: stick with the current policy \n  - may get penaltized when exploration\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n- **function approximation**: constructing a compact approximation of true utility function or Q-function\n- linear approximation\n  - $U(s) = w_1 f_1(s) + ... + w_n f_n(s)$\n  - $Q(s,s) = w_1 f_1(s,a) + ... + w_n f_n(s,a)$\n    - pros: easy\n    - cons: states may share features but be very different in value\n  -> $w_i=w_i+\\alpha (R(s,a,s')+\\gamma \\max_{a'}Q(s',a')-Q(s,a)) f_i(s,a)$\n  - **approximating direct utility estimation**\n  - **approximating temporal-difference learning**\n    - **catastrophic forgetting** and **experience replay** (keep reliving crashing behaviors at regular intervals)\n- nonlinear approximation\n- **hierachical reinforcement learning (HRL)**\n- **policy search**\n\n\n## Module 9 Lecture Notes\n\n- **regret**: a measure of total mistake cost (difference between expected rewards and optimal rewards)\n  - random exploration has a higher regret\n  - The relative goodness of exploration procedures.\n\n\n\n## Module 9 Definitions\n* **Sparse reward** - in most states the agent is given no reward signal at all\n* **Greedy agent** - greedily takes the action that it currently believes to be the optimal at each step\n* **Absorbing state** - no action has any effect and no rewards are received\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",
        "- decision theory = probability theory + utility theory\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\"\n",
        "- **sample space**: the set of all possible worlds, mutually exclusive and exhaustive\n",
        "- **unconditional probability (prior)** vs **conditional probability (posterior)**\n",
        "- $P(a|b)=P(a,b)/P(b)$ or $P(a,b) = P(a|b)P(b)$ (product rule)\n",
        "- **random variable**\n",
        "- **Bernoulli**: a random variable with range {0,1}\n",
        "- **probability distribution** (discrete) vs **probability density function** (continuous)\n",
        "  - **joint probability distribution**\n",
        "- **probabilistic model**: a joint distribution over a set of random variables\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "- **probability inference**: computation of posterior probabilities for query proposition given observed evidence\n",
        "- **marginalization**: $P(Y)= \\\\sum_z P(Y, Z=z)$\n",
        "- **conditioning**: $P(Y)= \\\\sum_z P(Y|Z)P(Z)$\n",
        "\"\"\"\n",
        "chapter12_4 = \"\"\" \n",
        "- **independence**: $P(X|Y)=P(X)$ or $P(X,Y)=P(X)P(Y)$\n",
        "\"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "- **Bayes'rule**: $P(b|a)=P(a|b)P(b)/P(a)$\n",
        "- **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "- **Naive Bayes model**: $P(C, E1, E2, .., En)=P(C)\\\\prod_i P(E_i|C)$\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" \n",
        "- **chain rule of probability**: $P(X_1,...,X_n)= \\\\prod_{k=1}^n P(X_k|X_{1:k-1})$\n",
        "- **joint probability** of words in a sentence**: $P(w_1w_2...w_n)=\\\\prod_{i}^n P(w_i|w_1w_2...w_{i-1})$\n",
        "- **maximum likelihood estimation (MLE)**: to esitmate the probability\n",
        "  - get the count of the corpus and then normalize it\n",
        "  - $P(w_n|w_{n-1}) = C(w_{n-1}w_n)/\\\\sum_w C(w_{n-1}w)$\n",
        "  - $P(\\\\text{won}|\\\\text{the underdog team})=Count(\\\\text{the underdog team won})/Count(\\\\text{the underdog team})$\n",
        "  - problem: the exact sentence might not been seen in the corpus -> requires a huge dataset\n",
        "- **Markov assumption**: the probability of a word only depends on the previous words\n",
        "  - $P(w_1w_2...w_n)=\\\\prod_{i}^n P(w_i|w_{i-k}...w_{i-1})$\n",
        "  - $P(\\\\text{won}|\\\\text{the underdog team})=P(\\\\text{won}|\\\\text{underdog team})$\n",
        "- **N-gram**\n",
        "  - instead of computing the probability of the whole history, we approximate the history by just the last few words\n",
        "  - $P(w_{1:n})=\\\\prod_{k=1}^n P(w_k|w_{k-1})$\n",
        "- **log probability**: \n",
        "  - since probabilities are less than 1, the more probabilities we multiply together, the smaller the product becomes\n",
        "  - $p1*p2*p3=log(p1+p2+p3)=log(p1)+log(p2)+log(p3)$\n",
        "  - avoid underflow, and adding is faster than multiplying\n",
        "\n",
        " \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" \n",
        "- **perplexity**: metric to measure the quality of n-gram models on a test set\n",
        "  - $PP(W)=(\\\\prod_{i=1}^N 1/P(w_i|X_{i-1})^{1/N}$\n",
        "  - the higher the conditional probabilities of the word, the lower the perplexity is\n",
        "  - the weighted average branching factor of a language\n",
        " \"\"\"\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "- **sampling**: choose random points according to their likelihood\n",
        " \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" \n",
        "- **zero**: things don't occur in training set but in test set\n",
        "- **unknown word**: occur in **open vacabulary** system\n",
        "  - convert words not shown in the fixed vocab list as UNK, then estimate the prob of UNK as other words do\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "- **smoothing**: to deal with known words appear in the unseen context in the test set\n",
        "  - **discounting** some non-zero counts in order to get the probability mass that will assign to the zero counts\n",
        "  - $d=c*/c$\n",
        "- **Laplace smoothing**: add one\n",
        "  - $P_{Laplace}(w_i)=(c_i+1)/(N+V)$\n",
        "  - **adjusted count c* ** = $(c_i+1)N/(N+V)$\n",
        "- **add-k smoothing**: \n",
        "  - $P_{Add-k}(w_n|w_{n-1})=(C(w_{n-1}w_n)+k)/(C(w_{n-1})+kV)$\n",
        "- **backoff**: use trigram if the evidence is sufficient, otherwise use bigram, otherwise use unigram\n",
        "- **interpolation**: mix the probabilties from multiple n-grams, weight and combine them\n",
        "- **Good-Turing**: for unseen context, use backoff\n",
        "\"\"\"\n",
        "SLP_chapter3_7 = \"\"\" \n",
        "- **stupid backoff**: with a large language model, a much simpler algorithm may be very sufficient\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"belief state\" : \"a representation of the set of all possible world states it might be in\",\n",
        "\"extrinsic evaluation\": \"embed in a system and see how the model improves the application\",\n",
        "\"intrinsic evaluation\": \"measure the quality of model without application\",\n",
        "\"probabilistic inference\": \"compute a desired probability from other known probabilities\",\n",
        "\"probabilistic language model\": \"model computes the prob of a sentence, or prob of upcoming word\"\n",
        "}"
      ],
      "execution_count": 74,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7cf009c8-44a3-48a5-fe02-eef0ffba047b"
      },
      "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": 75,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- decision theory = probability theory + utility theory\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- **sample space**: the set of all possible worlds, mutually exclusive and exhaustive\n- **unconditional probability (prior)** vs **conditional probability (posterior)**\n- $P(a|b)=P(a,b)/P(b)$ or $P(a,b) = P(a|b)P(b)$ (product rule)\n- **random variable**\n- **Bernoulli**: a random variable with range {0,1}\n- **probability distribution** (discrete) vs **probability density function** (continuous)\n  - **joint probability distribution**\n- **probabilistic model**: a joint distribution over a set of random variables\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- **probability inference**: computation of posterior probabilities for query proposition given observed evidence\n- **marginalization**: $P(Y)= \\sum_z P(Y, Z=z)$\n- **conditioning**: $P(Y)= \\sum_z P(Y|Z)P(Z)$\n\n\n## AIMA Chapter 12.4 Independence\n \n- **independence**: $P(X|Y)=P(X)$ or $P(X,Y)=P(X)P(Y)$\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n- **Bayes'rule**: $P(b|a)=P(a|b)P(b)/P(a)$\n- **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- **Naive Bayes model**: $P(C, E1, E2, .., En)=P(C)\\prod_i P(E_i|C)$\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n \n- **chain rule of probability**: $P(X_1,...,X_n)= \\prod_{k=1}^n P(X_k|X_{1:k-1})$\n- **joint probability** of words in a sentence**: $P(w_1w_2...w_n)=\\prod_{i}^n P(w_i|w_1w_2...w_{i-1})$\n- **maximum likelihood estimation (MLE)**: to esitmate the probability\n  - get the count of the corpus and then normalize it\n  - $P(w_n|w_{n-1}) = C(w_{n-1}w_n)/\\sum_w C(w_{n-1}w)$\n  - $P(\\text{won}|\\text{the underdog team})=Count(\\text{the underdog team won})/Count(\\text{the underdog team})$\n  - problem: the exact sentence might not been seen in the corpus -> requires a huge dataset\n- **Markov assumption**: the probability of a word only depends on the previous words\n  - $P(w_1w_2...w_n)=\\prod_{i}^n P(w_i|w_{i-k}...w_{i-1})$\n  - $P(\\text{won}|\\text{the underdog team})=P(\\text{won}|\\text{underdog team})$\n- **N-gram**\n  - instead of computing the probability of the whole history, we approximate the history by just the last few words\n  - $P(w_{1:n})=\\prod_{k=1}^n P(w_k|w_{k-1})$\n- **log probability**: \n  - since probabilities are less than 1, the more probabilities we multiply together, the smaller the product becomes\n  - $p1*p2*p3=log(p1+p2+p3)=log(p1)+log(p2)+log(p3)$\n  - avoid underflow, and adding is faster than multiplying\n\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n- **perplexity**: metric to measure the quality of n-gram models on a test set\n  - $PP(W)=(\\prod_{i=1}^N 1/P(w_i|X_{i-1})^{1/N}$\n  - the higher the conditional probabilities of the word, the lower the perplexity is\n  - the weighted average branching factor of a language\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n- **sampling**: choose random points according to their likelihood\n \n\n## SLP Chapter 3.4 Generalization and Zeros\n \n- **zero**: things don't occur in training set but in test set\n- **unknown word**: occur in **open vacabulary** system\n  - convert words not shown in the fixed vocab list as UNK, then estimate the prob of UNK as other words do\n\n\n## SLP Chapter 3.5 Smoothing\n\n- **smoothing**: to deal with known words appear in the unseen context in the test set\n  - **discounting** some non-zero counts in order to get the probability mass that will assign to the zero counts\n  - $d=c*/c$\n- **Laplace smoothing**: add one\n  - $P_{Laplace}(w_i)=(c_i+1)/(N+V)$\n  - **adjusted count c* ** = $(c_i+1)N/(N+V)$\n- **add-k smoothing**: \n  - $P_{Add-k}(w_n|w_{n-1})=(C(w_{n-1}w_n)+k)/(C(w_{n-1})+kV)$\n- **backoff**: use trigram if the evidence is sufficient, otherwise use bigram, otherwise use unigram\n- **interpolation**: mix the probabilties from multiple n-grams, weight and combine them\n- **Good-Turing**: for unseen context, use backoff\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n \n- **stupid backoff**: with a large language model, a much simpler algorithm may be very sufficient\n \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states it might be in\n* **Extrinsic evaluation** - embed in a system and see how the model improves the application\n* **Intrinsic evaluation** - measure the quality of model without application\n* **Probabilistic inference** - compute a desired probability from other known probabilities\n* **Probabilistic language model** - model computes the prob of a sentence, or prob of upcoming word\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",
        "- recall **independence**: $P(X|Y)=P(X)$ or $P(X,Y)=P(X)P(Y)$\n",
        "  - X ⫫ Y\n",
        "  - a simplying model assumption\n",
        "- recall **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$ or $P(X|Z, Y)=P(X|Z)$\n",
        "  - - X ⫫ Y | Z\n",
        "- Bayes' net help us express conditional independence\n",
        "  - a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n",
        "  - nodes: variables, arc: interaction (conditional distribution)\n",
        "  - A1->X, A2->X, A3->X, so P(X|A1,A2,A3)\n",
        "    - form **conditional probability table** (cpt)\n",
        "    - rows: **conditioning cases**: possible combination of the values of parent nodes\n",
        "- not every BN can represent every joint distribution\n",
        "\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\" \n",
        "- **casual chain**: X->Y->Z, $P(x,y,z)=P(x)P(y|x)P(z|y)$\n",
        "  - guaranteed X is independent of Z, no!\n",
        "  - guaranteed X is independent of Z given Y\n",
        "  - evidence along the chain \"blocks\" the influence \n",
        "- **common cause**: X<-Y->Z, $P(x,y,z)=Py)P(x|y)P(z|y)$\n",
        "  - guaranteed X is independent of Z, no!\n",
        "  - guaranteed X is independent of Z given Y\n",
        "  - observing the cause blocks influence between effects\n",
        "- **comman effect**: X->Z<-Y\n",
        "  - X and Y are independent\n",
        "  - X and Y are NOT independent given Z\n",
        "- **d-seperation**: \n",
        "  - no active path (all paths are inactive) -> conditionally independence\n",
        "  - a path is active is each triple is active\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" \n",
        "- calculate some useful quantity from a joint distribution\n",
        "  - posterior probability: $P(Q|E_1=e_1, ..., E_k=e_k)$\n",
        "  - most likely explanation: $argmax_q P(Q=q|E_1=e_1, ..., E_k=e_k)$\n",
        "- **inference by enumeration**:\n",
        "  - $P(X|e)= \\\\alpha P(X,e)=\\\\alpha \\\\sum_y P(X,e,y)$\n",
        "  - **very slow**: join up the whole joint distribution before you sum out the hidden variables\n",
        "- **variable elimination**\n",
        "  - Interleave joining and marginalizing\n",
        "  - faster than inference by enumeration\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "- size of a Bayes' Net:\n",
        "  - a joint distribution over N Boolean variables: $2^N$\n",
        "  - an N-node set if nodes have up to k parents: $O(N*2^{k+1})$, huge space saving\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian network\" : \"represent the dependencies among variables and full joint distribution\",    \n",
        "\"absolute independence\": \"no interaction between variables\",\n",
        "\"locally structured system (sparse)\": \"the compactness of Bayes' Net, each subcomponent interact with only a bounded number of component\",\n",
        "\"locally structured system cont.\": \"The structure grows linearly in complexity (rather than exponentially)\",\n",
        "}\n"
      ],
      "execution_count": 76,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "1e1d3d03-28a4-4fdd-c9e3-075db100a98a"
      },
      "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": 77,
      "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- recall **independence**: $P(X|Y)=P(X)$ or $P(X,Y)=P(X)P(Y)$\n  - X ⫫ Y\n  - a simplying model assumption\n- recall **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$ or $P(X|Z, Y)=P(X|Z)$\n  - - X ⫫ Y | Z\n- Bayes' net help us express conditional independence\n  - a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n  - nodes: variables, arc: interaction (conditional distribution)\n  - A1->X, A2->X, A3->X, so P(X|A1,A2,A3)\n    - form **conditional probability table** (cpt)\n    - rows: **conditioning cases**: possible combination of the values of parent nodes\n- not every BN can represent every joint distribution\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n- **casual chain**: X->Y->Z, $P(x,y,z)=P(x)P(y|x)P(z|y)$\n  - guaranteed X is independent of Z, no!\n  - guaranteed X is independent of Z given Y\n  - evidence along the chain \"blocks\" the influence \n- **common cause**: X<-Y->Z, $P(x,y,z)=Py)P(x|y)P(z|y)$\n  - guaranteed X is independent of Z, no!\n  - guaranteed X is independent of Z given Y\n  - observing the cause blocks influence between effects\n- **comman effect**: X->Z<-Y\n  - X and Y are independent\n  - X and Y are NOT independent given Z\n- **d-seperation**: \n  - no active path (all paths are inactive) -> conditionally independence\n  - a path is active is each triple is active\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n- calculate some useful quantity from a joint distribution\n  - posterior probability: $P(Q|E_1=e_1, ..., E_k=e_k)$\n  - most likely explanation: $argmax_q P(Q=q|E_1=e_1, ..., E_k=e_k)$\n- **inference by enumeration**:\n  - $P(X|e)= \\alpha P(X,e)=\\alpha \\sum_y P(X,e,y)$\n  - **very slow**: join up the whole joint distribution before you sum out the hidden variables\n- **variable elimination**\n  - Interleave joining and marginalizing\n  - faster than inference by enumeration\n\n\n## Module 11 Lecture Notes\n\n- size of a Bayes' Net:\n  - a joint distribution over N Boolean variables: $2^N$\n  - an N-node set if nodes have up to k parents: $O(N*2^{k+1})$, huge space saving\n\n\n## Module 11 Definitions\n* **Bayesian network** - represent the dependencies among variables and full joint distribution\n* **Absolute independence** - no interaction between variables\n* **Locally structured system (sparse)** - the compactness of Bayes' Net, each subcomponent interact with only a bounded number of component\n* **Locally structured system cont.** - The structure grows linearly in complexity (rather than exponentially)\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",
        "- indunction: based on everyday's knowledge induce what will happen tomorrow\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\" \n",
        "- exploratory data analysis: examine the data with statistical tests and visualizations\n",
        "- bias: the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" 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",
        "- how to acquire model from data:\n",
        "  - learning parameters (probabilities)\n",
        "  - learning structure (BN graphs)\n",
        "  - learning hidden concepts (clustering)\n",
        "- **naive bayes**: assume all features are independent effects of the label\n",
        "  - $P(Y, F_1...F_n)=P(Y)\\\\prod_i P(F_i|Y)$ \n",
        "  - only need to specify how each feature depends on the class\n",
        "  - total number of parameters is linear in the number of features\n",
        "  - probabilities are called the **parameters** of the model\n",
        "- naive bayes in NLP: \n",
        "  - **bag of words**: each position is identically distributed, all position have the same $P(W|Y)$\n",
        "    - insensitive to the order of words\n",
        "- overfit: we can't go around giving unseen event zero probability\n",
        "- need **smooth** and **regularization** to better generalize\n",
        "- Laplace smoothing: +1, +k (extended)\n",
        "- **Linear interpolation**: $P_{LIN}(x|y)=\\\\alpha P_{hat}(x|y)+(1-\\\\alpha) P_{hat}(x)$\n",
        "- **baseline**: most frequent label\n",
        "- **confidence**: represent how sure the classifier is of the classification\n",
        "  - $confidence(x)= max_y P(y|x)$\n",
        "  - higher confidence means higher accuracy\n",
        "- **perceptron**:\n",
        "  - **linear classifier**: input are feature values, each feature has a weight \n",
        "  - binary perceptron: y=1 if $w\\\\cdot f(x)>=0$, y=1 if $w\\\\cdot f(x)<0$\n",
        "  -> if wrong: $w=w+y^* \\\\cdot f$\n",
        "  - multiclass perceptron: $y=argmax_y  w_y\\\\cdot f(x)$\n",
        "  -> if wrong: lower the weight: $w_y=w_y-f(x)$\n",
        "  -> else: raise the score: $w_y=w_y+f(x)$\n",
        "- property of perceptrons\n",
        "  - **separability**: true if some parameters get the training set perfectly correct\n",
        "  - **convergence**: if the training is separable, perceptron, will eventually converge (binary search)\n",
        "  - **mistake bound**: the maximum number of mistakes related to the **margin** or degree of separability: $mistakes < k/margin^2$\n",
        "- problems with perceptrons\n",
        "  - noise: if data isn't separable, weights might trash\n",
        "  - mediocre generalization: finds a \"barely\" separating solution\n",
        "  - overtraining \n",
        "- fixing these problems:\n",
        "  - **MIRA (margin infused relaxed algorithm)**\n",
        "    - minimum perceptron update: adjust the weight update (minimize the change to it) to mitigate the effect\n",
        "    - maximum step size: cap the maximum possible value \n",
        "    -> converage faster, better on noisy data \n",
        "  - **support vector machine**:\n",
        "    - maximizing the margin, only support vector matters\n",
        "- naive bayes vs perceptron/MIRA\n",
        "  - NB: give prediction probabilities, strong assumption about feature independence, one pass through data\n",
        "  - perceptron/MIRA: mistaken-driven learning, less assumption about data, multiple pass through data   \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"confidence\" : \"represent how sure the classifier is of the classification\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0d44281a-724a-4b3a-a902-90944367d159"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n \n- indunction: based on everyday's knowledge induce what will happen tomorrow\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n- exploratory data analysis: examine the data with statistical tests and visualizations\n- bias: the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n- how to acquire model from data:\n  - learning parameters (probabilities)\n  - learning structure (BN graphs)\n  - learning hidden concepts (clustering)\n- **naive bayes**: assume all features are independent effects of the label\n  - $P(Y, F_1...F_n)=P(Y)\\prod_i P(F_i|Y)$ \n  - only need to specify how each feature depends on the class\n  - total number of parameters is linear in the number of features\n  - probabilities are called the **parameters** of the model\n- naive bayes in NLP: \n  - **bag of words**: each position is identically distributed, all position have the same $P(W|Y)$\n    - insensitive to the order of words\n- overfit: we can't go around giving unseen event zero probability\n- need **smooth** and **regularization** to better generalize\n- Laplace smoothing: +1, +k (extended)\n- **Linear interpolation**: $P_{LIN}(x|y)=\\alpha P_{hat}(x|y)+(1-\\alpha) P_{hat}(x)$\n- **baseline**: most frequent label\n- **confidence**: represent how sure the classifier is of the classification\n  - $confidence(x)= max_y P(y|x)$\n  - higher confidence means higher accuracy\n- **perceptron**:\n  - **linear classifier**: input are feature values, each feature has a weight \n  - binary perceptron: y=1 if $w\\cdot f(x)>=0$, y=1 if $w\\cdot f(x)<0$\n  -> if wrong: $w=w+y^* \\cdot f$\n  - multiclass perceptron: $y=argmax_y  w_y\\cdot f(x)$\n  -> if wrong: lower the weight: $w_y=w_y-f(x)$\n  -> else: raise the score: $w_y=w_y+f(x)$\n- property of perceptrons\n  - **separability**: true if some parameters get the training set perfectly correct\n  - **convergence**: if the training is separable, perceptron, will eventually converge (binary search)\n  - **mistake bound**: the maximum number of mistakes related to the **margin** or degree of separability: $mistakes < k/margin^2$\n- problems with perceptrons\n  - noise: if data isn't separable, weights might trash\n  - mediocre generalization: finds a \"barely\" separating solution\n  - overtraining \n- fixing these problems:\n  - **MIRA (margin infused relaxed algorithm)**\n    - minimum perceptron update: adjust the weight update (minimize the change to it) to mitigate the effect\n    - maximum step size: cap the maximum possible value \n    -> converage faster, better on noisy data \n  - **support vector machine**:\n    - maximizing the margin, only support vector matters\n- naive bayes vs perceptron/MIRA\n  - NB: give prediction probabilities, strong assumption about feature independence, one pass through data\n  - perceptron/MIRA: mistaken-driven learning, less assumption about data, multiple pass through data   \n \n\n## Module 12 Definitions\n* **Confidence** - represent how sure the classifier is of the classification\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "- classifier component:\n",
        "  - feature representation\n",
        "  - classification function: compute the estimated class\n",
        "  - objective function: minimize error on training example\n",
        "  - optimizing: the objective function\n",
        "- **logistic regression**:\n",
        "  - $z=w\\\\cdot x+b$\n",
        "  - $\\\\sigma(z)=y/(1+e^{-z})$ (sigmoid function)\n",
        "  - $y_{hat}=P(y=1)=\\\\sigma(z)$\n",
        "  - decision boundary: 1 if P(y=1)>0.5, else 0\n",
        "  - **loss function** (tell us the distance between the estimated output and golden output): **cross-entropy loss**\n",
        "    - **mean squared error**: \n",
        "  -> $L_{MSE}(y_{hat},y)=(y_{hat}-y)^2/2$\n",
        "  - **optimizer**: minimizing loss function : **gradient descent**\n",
        "- **cross-entropy loss**:\n",
        "  - 1. a function that maximizes the probability of the correct label: $p(y|x)= y_{hat}^y(1-y_{hat})^{1-y}$\n",
        "  - 2. change to log and flip the sign (to minimize): $L_{CE}(y_{hat},y)=-[ylog(y_{hat})+(1-y)log(1-y_{hat})]$\n",
        "  - loss on all training examples: $log(p(training labels))=log\\\\prod_{i=1}^m p(y^i|x^i)=-\\\\sum_{i=1}^m L_{CE}(y_{hat}^i/y^i)$\n",
        "- **gradient descent**: find a minimum of a function by figuring out which direction the function's slope is rising in the most steeply, and moving in the opposite direction\n",
        "  - $w^{t+1}=w^t-\\\\eta (d/dw)f(x;w)$\n",
        "  - $\\\\eta$: learning rate \n",
        "  - final equation: $\\\\theta_{t+1}=\\\\theta_t \\\\nabla L(f(x;\\\\theta),y)$\n",
        "  - derivative of this function: $\\\\partial L_{CE}(w,b)/\\\\partial w_j = [\\\\sigma (w\\\\cdot x+b)-y]x_j$\n",
        "- **stochastic gradient descent**: single training example at a time and update its weight on that example\n",
        "- **batch training**: compute gradient over entire dataset\n",
        "- **mini-batch training**: train on small batch\n",
        "- for multiclassification, instead of using sigmoid, we use **softmax** which normalizes its output and return probability distribution\n",
        "  - $softmax(z_i)= e^{z_j}/\\\\sum_{j=1}^k e^{z_j}, 1\\le i \\le k$\n",
        "- **feed forward neural network**: **multilayer network, all units are fully connected, no cycles\"\n",
        "  - $h=\\\\sigma(Wx+b)$\n",
        "  - $z=Uh$\n",
        "  - $y=softmax(z)$\n",
        "  - loss function: cross-entropy loss\n",
        "  - optimization algorithm: gradient descent\n",
        "  - a way of computing the gradient of the loss function: error propagation\n",
        "- cross-entropy loss:\n",
        "  - if binary: $L_{CE}(y_{hat},y)=-[ylog(y_{hat})+(1-y)log(1-y_{hat})]$\n",
        "  - if multi: $L_{CE}(y_{hat},y)=-\\\\sum_{i=1}^{C}y_i log(y_i^{hat})$\n",
        "  - but if there is only one correct answer: $L_{CE}(y_{hat},y)=-log(y_i^{hat})$\n",
        "- logistic regression's way of computing gradient only give correct update for the last layer. NN requires looking back on all earlier layer\n",
        "-> **error backpropagation algorithm**: use chain rules to compute the derivative\n",
        "  - $f(x)= u(v(w(x)))$ -> $df/dx=(du/dv)*(dv/dw)*(dw/dx)$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"convex\" : \"a convex function has one minimum\",   \n",
        "\"smoothness of $\\\\sigma$\": \"small changes in the weights $w_j$ and in the bias b will produce small change the output from neuron\" ,\n",
        "\"computation graph\": \"represents the process of computing a mathematical expression\"\n",
        "}\n"
      ],
      "execution_count": 80,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a0951b9b-9a8e-470c-82bd-50a1712227df"
      },
      "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": 81,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n- classifier component:\n  - feature representation\n  - classification function: compute the estimated class\n  - objective function: minimize error on training example\n  - optimizing: the objective function\n- **logistic regression**:\n  - $z=w\\cdot x+b$\n  - $\\sigma(z)=y/(1+e^{-z})$ (sigmoid function)\n  - $y_{hat}=P(y=1)=\\sigma(z)$\n  - decision boundary: 1 if P(y=1)>0.5, else 0\n  - **loss function** (tell us the distance between the estimated output and golden output): **cross-entropy loss**\n    - **mean squared error**: \n  -> $L_{MSE}(y_{hat},y)=(y_{hat}-y)^2/2$\n  - **optimizer**: minimizing loss function : **gradient descent**\n- **cross-entropy loss**:\n  - 1. a function that maximizes the probability of the correct label: $p(y|x)= y_{hat}^y(1-y_{hat})^{1-y}$\n  - 2. change to log and flip the sign (to minimize): $L_{CE}(y_{hat},y)=-[ylog(y_{hat})+(1-y)log(1-y_{hat})]$\n  - loss on all training examples: $log(p(training labels))=log\\prod_{i=1}^m p(y^i|x^i)=-\\sum_{i=1}^m L_{CE}(y_{hat}^i/y^i)$\n- **gradient descent**: find a minimum of a function by figuring out which direction the function's slope is rising in the most steeply, and moving in the opposite direction\n  - $w^{t+1}=w^t-\\eta (d/dw)f(x;w)$\n  - $\\eta$: learning rate \n  - final equation: $\\theta_{t+1}=\\theta_t \\nabla L(f(x;\\theta),y)$\n  - derivative of this function: $\\partial L_{CE}(w,b)/\\partial w_j = [\\sigma (w\\cdot x+b)-y]x_j$\n- **stochastic gradient descent**: single training example at a time and update its weight on that example\n- **batch training**: compute gradient over entire dataset\n- **mini-batch training**: train on small batch\n- for multiclassification, instead of using sigmoid, we use **softmax** which normalizes its output and return probability distribution\n  - $softmax(z_i)= e^{z_j}/\\sum_{j=1}^k e^{z_j}, 1\\le i \\le k$\n- **feed forward neural network**: **multilayer network, all units are fully connected, no cycles\"\n  - $h=\\sigma(Wx+b)$\n  - $z=Uh$\n  - $y=softmax(z)$\n  - loss function: cross-entropy loss\n  - optimization algorithm: gradient descent\n  - a way of computing the gradient of the loss function: error propagation\n- cross-entropy loss:\n  - if binary: $L_{CE}(y_{hat},y)=-[ylog(y_{hat})+(1-y)log(1-y_{hat})]$\n  - if multi: $L_{CE}(y_{hat},y)=-\\sum_{i=1}^{C}y_i log(y_i^{hat})$\n  - but if there is only one correct answer: $L_{CE}(y_{hat},y)=-log(y_i^{hat})$\n- logistic regression's way of computing gradient only give correct update for the last layer. NN requires looking back on all earlier layer\n-> **error backpropagation algorithm**: use chain rules to compute the derivative\n  - $f(x)= u(v(w(x)))$ -> $df/dx=(du/dv)*(dv/dw)*(dw/dx)$\n\n\n\n## Module 13 Definitions\n* **Convex** - a convex function has one minimum\n* **Smoothness of $\\sigma$** - small changes in the weights $w_j$ and in the bias b will produce small change the output from neuron\n* **Computation graph** - represents the process of computing a mathematical expression\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",
        "- **term-document matrix**:\n",
        "  - column vectors are documents\n",
        "  - each row vector is a term\n",
        "  - value cell is how often that term occurred in the document\n",
        "  - the length of the document vector is the size of vocabulary\n",
        "  - document vector can be sparse (most values are 0)\n",
        "  - measure the similarity of documents by comparing their column vectors\n",
        "  - measure the similarity of terms by comparing their row vectors\n",
        "- **vector L2 (length) normalization**:\n",
        "  - value cell$/||u||$, $||u||=\\\\sqrt{\\\\sum_{i=1}^n u_i^2}$\n",
        "  - compare the euclidean distance, or **cosine distance**\n",
        "- **term-term (term-context) matrix**:\n",
        "  - value cell is how often that a term occurred in the context of another term\n",
        "  - **context window**\n",
        "- raw word frequency is not a great measure of associations between words (very skewed on \"of\")\n",
        "-> TF-IDF, or PPMI\n",
        "  - TF: how often a word occurred in a document\n",
        "  - IDF: 1/the number of documents that it occurred in\n",
        "- problems of **language modeling**\n",
        "  - there are too many parameters to accurately estimate, **curse of dimensionality**\n",
        "  - in n-gram-based model, we fail to generalize to related words\n",
        "- **neural language model**: \n",
        "  - pros: no need to smoothing, handle longer histories, generalize context of similar words, higher accuracy\n",
        "  - cons: slower to train\n",
        "  - first k-1 words are features, and the last word is used as the target label for classification\n",
        "  - train using cross-entropy loss\n",
        "- train a classifer to get dense vector\n",
        "  - Word2Vec: predict the surrounding words in a context window of 2C\n",
        "  - **negative sampling**: randomly sample other lexicon to get negative samples\n",
        "- embeddings (vector model of meaning) capture relational meaning\n",
        "  - especially good at modeling similarity and analogy\n",
        "  - can use sparse models (td-idf) or dense models (Word2Vec)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"sparse\" : \"most elements are zeros\",\n",
        "\"dense\": \"most elements are non-zeros, better generalize, faster to apply in ML\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "21f72121-ac26-438f-e003-781a72de86c3"
      },
      "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": 83,
      "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- **term-document matrix**:\n  - column vectors are documents\n  - each row vector is a term\n  - value cell is how often that term occurred in the document\n  - the length of the document vector is the size of vocabulary\n  - document vector can be sparse (most values are 0)\n  - measure the similarity of documents by comparing their column vectors\n  - measure the similarity of terms by comparing their row vectors\n- **vector L2 (length) normalization**:\n  - value cell$/||u||$, $||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$\n  - compare the euclidean distance, or **cosine distance**\n- **term-term (term-context) matrix**:\n  - value cell is how often that a term occurred in the context of another term\n  - **context window**\n- raw word frequency is not a great measure of associations between words (very skewed on \"of\")\n-> TF-IDF, or PPMI\n  - TF: how often a word occurred in a document\n  - IDF: 1/the number of documents that it occurred in\n- problems of **language modeling**\n  - there are too many parameters to accurately estimate, **curse of dimensionality**\n  - in n-gram-based model, we fail to generalize to related words\n- **neural language model**: \n  - pros: no need to smoothing, handle longer histories, generalize context of similar words, higher accuracy\n  - cons: slower to train\n  - first k-1 words are features, and the last word is used as the target label for classification\n  - train using cross-entropy loss\n- train a classifer to get dense vector\n  - Word2Vec: predict the surrounding words in a context window of 2C\n  - **negative sampling**: randomly sample other lexicon to get negative samples\n- embeddings (vector model of meaning) capture relational meaning\n  - especially good at modeling similarity and analogy\n  - can use sparse models (td-idf) or dense models (Word2Vec)\n\n\n## Module 14 Definitions\n* **Sparse** - most elements are zeros\n* **Dense** - most elements are non-zeros, better generalize, faster to apply in ML\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": "1cd080c1-106d-45f7-ef38-57fbf9f9c946"
      },
      "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": 84,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n- **orderability**: exactly one of (A>B), (B>A), (A~B) holds\n- **transivity**: (A>B) and (B>A) => (A>C)\n- **continuity**: A>B>C => exists p, [p,A; 1-p,C]~B\n- **substitutability**: (A ~ B) => [p,A; 1-p,C]~[p,B; 1-p,C]\n- **monotonicity**: A>B=>(p>q <=> [p,A; 1-p,B]>[q,A; 1-q,B])\n- **decomposibility**: [p,A; 1-p,[q,B; 1-q,C]]~[p,A; (1-p)q,B; (1-p)(1-q),C]\n\n\n## AIMA Chapter 16.3 Utility Functions\n\n- utility on economics\n\n  - people prefer more money than less, which is a **monotonic preference**\n  -**expected monetary value** (EMV): utility is not directly proportional to monetary value (but proportional to the log of value)\n  -**risk-averse**: prefer sure thing with payoff that is less than the EMV of a gamble\n  -**risk-seeking**: prefer unsure thing with payoff that is more than the EMV of a gamble\n  -**certainty equivalent**: the value an agent will accept in a gamble\n  -**insurance preminum**: EMV - certainty equivalent (risk-aversion->insurance industry)\n  -**risk netural**: gambles with small sums expect risk-netural\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\n- **Markov decision process (MDP)**\n\n  - a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards \n  - consists of:\n\n    - a set of states, a set of actions in each state, a transition model $P(s'|s,a)$, and a reward function $A(s,a,s')$\n\n  - **policy**: what agent should do for any state that the agent might reach $\\pi(x)$\n\n    - the quality of a policy is measured by the expected utility of possible environment histories generated by that policy\n\n- **finite horizon**: there is a fixed time N after that the game is over\n\n  - **nonstationary**: a policy that depends on how much time is left\n\n- **infinite horizon**: there is no time limit\n\n - **stationary**: a policy that only depends on the current state\n\n- **discount factor $\\gamma$**: the performance of the agent for current rewards over future ones\n\n- **proper policy**: a policy that is guaranteed to reach a terminal state\n\n- **Bellman equation**: $U(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')] $\n\n- **Q function**: $Q(s,a)=\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\n- **value iteration** ($O(S^2A)$): if there are n possible states, then apply n times Bellman equation\n\n  - **Bellman update** ($O(S^2)$): $U_{i+1}(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')] $\n  - will converge eventually\n  - problems:\n\n    - too slow\n    - max at each state rarely changes\n    - policy often converges before values\n  - Contraction: part of the proof of convergence for the value iteration algorithm.\n\n- **policy iteration**: \n\n  - **policy evaluation**: calculate utilties for some fixed policy until convergence\n    \n  -> $U_{i+1}(s) =  \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')] $\n\n  - **policy improvement**: update policy value using one-step looking ahead with resulting converged utilities as future value\n\n  -> $\\pi_{i+1}(s) =  argmax_{a} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')] $\n\n  - repeat until policy converage\n  \n  - remove max, equation turns linear, faster than value iteration\n\n\n## Module 8 Lecture Notes\n\n- if we assume **stationary preference**, there are only two ways to define utilities\n\n  - additive and discounted\n\n- infinite utility:\n\n  - finite horizon (limited time)\n  - discounting\n  - absorbing state: guarantee that for every policy, a terminal state would be eventually reached\n\n\n## Module 8 Definitions\n* **Utility function** - agent's preference\n* **Expected utility** - the average utility value of the outcomes\n* **Maximum expected utility (meu)** - rational agent should choose the action that maximizes the agent's expected utility\n* **Preference elicitation** - find out the utility function of humans\n* **Unbias** - expected value of error is zero\n* **Normative theory** - how a rational agent should act\n* **Descriptive theory** - how an actual agent really act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - people choose the known probability rather than the unknown\n* **Framing effect** - the wording of a decsion problem may impact agent's decision\n* **Anchoring effect** - prefer making relative untility judgement than absolute one\n* **Markovian** - the probability of reaching s' from s depends only on s and not the history of early states\n* **Environment history** - sequence of states and actions\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\n- **exploitation**: current best actions\n- **exploration**: previous unknown states\n- **bandit problem**: each arm $M_i$ is a **Markov reward process** (an MDP with only one possible action $a_i$)\n- **Gittins index**: the maximum obtainable utility per unit of discounted time\n\n  - pull the arms with the highest Gittins index\n\n- Bernoulli brandit: each arm produces either 0 or 1 with a fixed but unknown probability\n- Bandit superprocess (BSP): each arm is a full MDP, for **multi-tasking**\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- **reinforcement learning**: agent periodically receives rewards that reflects how well it is doing\n- **model-based RL**: use a transition model to help interpret the reward signals\n\n  - step 1: learn empirical MDP model\n  - step 2: solved the learned MDP problem\n- **model-free RL**: \n  \n  - **action-utility learning**: action utitlity learning: **Q-learning**\n  - **policy search**: agent learns a policy that directly maps states from actions \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n \n- **passive reinforcement learning**: policy evaluation\n\n  - fully observable environment, a fixed policy $\\pi(s)$ that determines actions\n  - unknown $P(s'|s,a)$ and $R(s,a,s')$\n  - try to learn $U^{\\pi}(s)$\n\n- **direct utility estimation**: the utility of a state is defined as the expected total reward from that state onward (**reward-to-go**)\n\n  - compute values for each state under $\\pi$, compute the average over the sample\n  - ignore the connections between states -> miss the opportunities for learning\n\n- **sample-based policy evaluation**: takes the samples of outcome s' and then average\n\n  - $sample_1 = R(s,\\pi_i(s),s_1')+\\gamma U^{\\pi}_k(s_1')$\n  - $sample_2 = R(s,\\pi_i(s),s_2')+\\gamma U^{\\pi}_k(s_2')$\n  - $U^{\\pi}_{k+1}=avg(samples)$\n\n- **adaptive dynamic programming**: use the learned transition model and observed rewards\n\n  - to learn transition model: $P(s'|s,a)$ is represented as a table, and estimated directly from the counts that are accumulated in N_{s'|sa}\n  - the count records how ofter s' is reached when executing a in s\n\n- **temporal-difference learning**: use observed transition to adjust the utilities of the observed states\n\n  - $sample=R(s,\\pi_i(s),s')+\\gamma U^{\\pi}(s')$\n  - **temporal-difference equation**: $U^{\\pi}(s) =  U^{\\pi}(s)+\\alpha (sample-U^{\\pi}(s))= (1-\\alpha)U^{\\pi}(s)+\\alpha sample$\n  - $\\alpha$ is the learning rate\n  - use the difference between the successive states\n  - $R(s,\\pi_i(s),s')+\\gamma U^{\\pi}(s')-U^{\\pi}(s)$ is an error signal, and the update is intended to reduce the error\n  - **problem**: can't turn values into a new policy\n\n- TD adjusts a state to agree with its observed successor, ADP adjusts the state to agree with all of the successors that might occur, weighted by their probabilities\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n- **active reinforcement learning**: decide what actions to take (learn optional policies)\n\n  - learn a complete transition model with outcome probabilities for all actions, not just the fixed policy\n\n- **greedy in the limit of infinite exploration (GLIE)**: try infinite times to find the optimal solution\n- since in reality some actions are irreversible, we need to choose a policy that is reasonbly well for the whole range of models\n  that have chance of being the true model, even if the policy happens to be suboptimal\n\n  - **Bayesian reinforcement learning**\n  - **robust control theory**\n\n- **Q-learning**: avoids the need for a transition model, by learning an action-utility function Q(s,a) instead of a utility function U(s)\n\n  - $Q(s,a)=\\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q_k(s',a')]$\n  - Q(s,a) denotes total discounted reward if agent takes action a in s and acts optimally afterward\n  - $sample=R(s,a,s')+\\gamma \\max_{a'}Q(s',a')$\n  - $ Q(s,a) =  (1-\\alpha)Q(s,a)+\\alpha sample $\n  - **Q-learning** converges to optimal policy, even if you act suboptimally  \n  - **off-policy**: stops the current policy and uses the one that choose the best action\n  - caveat:\n  \n    - have to explore enough\n    - eventually make learning rate small enough, but not decrease it too quickly \n\n- **SARSA**(state, action, reward, state, action): close relative of Q-learning\n\n  - $Q(s,a) =  Q(s,a)+\\alpha [R(s,a,s')+\\gamma Q(s',a')-Q(s,a)] $\n  - **on-policy**: stick with the current policy \n  - may get penaltized when exploration\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n- **function approximation**: constructing a compact approximation of true utility function or Q-function\n- linear approximation\n  - $U(s) = w_1 f_1(s) + ... + w_n f_n(s)$\n  - $Q(s,s) = w_1 f_1(s,a) + ... + w_n f_n(s,a)$\n    - pros: easy\n    - cons: states may share features but be very different in value\n  -> $w_i=w_i+\\alpha (R(s,a,s')+\\gamma \\max_{a'}Q(s',a')-Q(s,a)) f_i(s,a)$\n  - **approximating direct utility estimation**\n  - **approximating temporal-difference learning**\n    - **catastrophic forgetting** and **experience replay** (keep reliving crashing behaviors at regular intervals)\n- nonlinear approximation\n- **hierachical reinforcement learning (HRL)**\n- **policy search**\n\n\n## Module 9 Lecture Notes\n\n- **regret**: a measure of total mistake cost (difference between expected rewards and optimal rewards)\n  - random exploration has a higher regret\n  - The relative goodness of exploration procedures.\n\n\n\n## Module 9 Definitions\n* **Sparse reward** - in most states the agent is given no reward signal at all\n* **Greedy agent** - greedily takes the action that it currently believes to be the optimal at each step\n* **Absorbing state** - no action has any effect and no rewards are received\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n\n- decision theory = probability theory + utility theory\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\n- **sample space**: the set of all possible worlds, mutually exclusive and exhaustive\n- **unconditional probability (prior)** vs **conditional probability (posterior)**\n- $P(a|b)=P(a,b)/P(b)$ or $P(a,b) = P(a|b)P(b)$ (product rule)\n- **random variable**\n- **Bernoulli**: a random variable with range {0,1}\n- **probability distribution** (discrete) vs **probability density function** (continuous)\n  - **joint probability distribution**\n- **probabilistic model**: a joint distribution over a set of random variables\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\n- **probability inference**: computation of posterior probabilities for query proposition given observed evidence\n- **marginalization**: $P(Y)= \\sum_z P(Y, Z=z)$\n- **conditioning**: $P(Y)= \\sum_z P(Y|Z)P(Z)$\n\n\n## AIMA Chapter 12.4 Independence\n \n- **independence**: $P(X|Y)=P(X)$ or $P(X,Y)=P(X)P(Y)$\n\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n- **Bayes'rule**: $P(b|a)=P(a|b)P(b)/P(a)$\n- **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n- **Naive Bayes model**: $P(C, E1, E2, .., En)=P(C)\\prod_i P(E_i|C)$\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n \n- **chain rule of probability**: $P(X_1,...,X_n)= \\prod_{k=1}^n P(X_k|X_{1:k-1})$\n- **joint probability** of words in a sentence**: $P(w_1w_2...w_n)=\\prod_{i}^n P(w_i|w_1w_2...w_{i-1})$\n- **maximum likelihood estimation (MLE)**: to esitmate the probability\n  - get the count of the corpus and then normalize it\n  - $P(w_n|w_{n-1}) = C(w_{n-1}w_n)/\\sum_w C(w_{n-1}w)$\n  - $P(\\text{won}|\\text{the underdog team})=Count(\\text{the underdog team won})/Count(\\text{the underdog team})$\n  - problem: the exact sentence might not been seen in the corpus -> requires a huge dataset\n- **Markov assumption**: the probability of a word only depends on the previous words\n  - $P(w_1w_2...w_n)=\\prod_{i}^n P(w_i|w_{i-k}...w_{i-1})$\n  - $P(\\text{won}|\\text{the underdog team})=P(\\text{won}|\\text{underdog team})$\n- **N-gram**\n  - instead of computing the probability of the whole history, we approximate the history by just the last few words\n  - $P(w_{1:n})=\\prod_{k=1}^n P(w_k|w_{k-1})$\n- **log probability**: \n  - since probabilities are less than 1, the more probabilities we multiply together, the smaller the product becomes\n  - $p1*p2*p3=log(p1+p2+p3)=log(p1)+log(p2)+log(p3)$\n  - avoid underflow, and adding is faster than multiplying\n\n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n- **perplexity**: metric to measure the quality of n-gram models on a test set\n  - $PP(W)=(\\prod_{i=1}^N 1/P(w_i|X_{i-1})^{1/N}$\n  - the higher the conditional probabilities of the word, the lower the perplexity is\n  - the weighted average branching factor of a language\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n- **sampling**: choose random points according to their likelihood\n \n\n## SLP Chapter 3.4 Generalization and Zeros\n \n- **zero**: things don't occur in training set but in test set\n- **unknown word**: occur in **open vacabulary** system\n  - convert words not shown in the fixed vocab list as UNK, then estimate the prob of UNK as other words do\n\n\n## SLP Chapter 3.5 Smoothing\n\n- **smoothing**: to deal with known words appear in the unseen context in the test set\n  - **discounting** some non-zero counts in order to get the probability mass that will assign to the zero counts\n  - $d=c*/c$\n- **Laplace smoothing**: add one\n  - $P_{Laplace}(w_i)=(c_i+1)/(N+V)$\n  - **adjusted count c* ** = $(c_i+1)N/(N+V)$\n- **add-k smoothing**: \n  - $P_{Add-k}(w_n|w_{n-1})=(C(w_{n-1}w_n)+k)/(C(w_{n-1})+kV)$\n- **backoff**: use trigram if the evidence is sufficient, otherwise use bigram, otherwise use unigram\n- **interpolation**: mix the probabilties from multiple n-grams, weight and combine them\n- **Good-Turing**: for unseen context, use backoff\n\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n \n- **stupid backoff**: with a large language model, a much simpler algorithm may be very sufficient\n \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - a representation of the set of all possible world states it might be in\n* **Extrinsic evaluation** - embed in a system and see how the model improves the application\n* **Intrinsic evaluation** - measure the quality of model without application\n* **Probabilistic inference** - compute a desired probability from other known probabilities\n* **Probabilistic language model** - model computes the prob of a sentence, or prob of upcoming word\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\n- recall **independence**: $P(X|Y)=P(X)$ or $P(X,Y)=P(X)P(Y)$\n  - X ⫫ Y\n  - a simplying model assumption\n- recall **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$ or $P(X|Z, Y)=P(X|Z)$\n  - - X ⫫ Y | Z\n- Bayes' net help us express conditional independence\n  - a technique for describing complex joint distributions (models) using simple, local distributions (conditional probabilities)\n  - nodes: variables, arc: interaction (conditional distribution)\n  - A1->X, A2->X, A3->X, so P(X|A1,A2,A3)\n    - form **conditional probability table** (cpt)\n    - rows: **conditioning cases**: possible combination of the values of parent nodes\n- not every BN can represent every joint distribution\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n- **casual chain**: X->Y->Z, $P(x,y,z)=P(x)P(y|x)P(z|y)$\n  - guaranteed X is independent of Z, no!\n  - guaranteed X is independent of Z given Y\n  - evidence along the chain \"blocks\" the influence \n- **common cause**: X<-Y->Z, $P(x,y,z)=Py)P(x|y)P(z|y)$\n  - guaranteed X is independent of Z, no!\n  - guaranteed X is independent of Z given Y\n  - observing the cause blocks influence between effects\n- **comman effect**: X->Z<-Y\n  - X and Y are independent\n  - X and Y are NOT independent given Z\n- **d-seperation**: \n  - no active path (all paths are inactive) -> conditionally independence\n  - a path is active is each triple is active\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \n- calculate some useful quantity from a joint distribution\n  - posterior probability: $P(Q|E_1=e_1, ..., E_k=e_k)$\n  - most likely explanation: $argmax_q P(Q=q|E_1=e_1, ..., E_k=e_k)$\n- **inference by enumeration**:\n  - $P(X|e)= \\alpha P(X,e)=\\alpha \\sum_y P(X,e,y)$\n  - **very slow**: join up the whole joint distribution before you sum out the hidden variables\n- **variable elimination**\n  - Interleave joining and marginalizing\n  - faster than inference by enumeration\n\n\n## Module 11 Lecture Notes\n\n- size of a Bayes' Net:\n  - a joint distribution over N Boolean variables: $2^N$\n  - an N-node set if nodes have up to k parents: $O(N*2^{k+1})$, huge space saving\n\n\n## Module 11 Definitions\n* **Bayesian network** - represent the dependencies among variables and full joint distribution\n* **Absolute independence** - no interaction between variables\n* **Locally structured system (sparse)** - the compactness of Bayes' Net, each subcomponent interact with only a bounded number of component\n* **Locally structured system cont.** - The structure grows linearly in complexity (rather than exponentially)\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n \n- indunction: based on everyday's knowledge induce what will happen tomorrow\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n- exploratory data analysis: examine the data with statistical tests and visualizations\n- bias: the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n- how to acquire model from data:\n  - learning parameters (probabilities)\n  - learning structure (BN graphs)\n  - learning hidden concepts (clustering)\n- **naive bayes**: assume all features are independent effects of the label\n  - $P(Y, F_1...F_n)=P(Y)\\prod_i P(F_i|Y)$ \n  - only need to specify how each feature depends on the class\n  - total number of parameters is linear in the number of features\n  - probabilities are called the **parameters** of the model\n- naive bayes in NLP: \n  - **bag of words**: each position is identically distributed, all position have the same $P(W|Y)$\n    - insensitive to the order of words\n- overfit: we can't go around giving unseen event zero probability\n- need **smooth** and **regularization** to better generalize\n- Laplace smoothing: +1, +k (extended)\n- **Linear interpolation**: $P_{LIN}(x|y)=\\alpha P_{hat}(x|y)+(1-\\alpha) P_{hat}(x)$\n- **baseline**: most frequent label\n- **confidence**: represent how sure the classifier is of the classification\n  - $confidence(x)= max_y P(y|x)$\n  - higher confidence means higher accuracy\n- **perceptron**:\n  - **linear classifier**: input are feature values, each feature has a weight \n  - binary perceptron: y=1 if $w\\cdot f(x)>=0$, y=1 if $w\\cdot f(x)<0$\n  -> if wrong: $w=w+y^* \\cdot f$\n  - multiclass perceptron: $y=argmax_y  w_y\\cdot f(x)$\n  -> if wrong: lower the weight: $w_y=w_y-f(x)$\n  -> else: raise the score: $w_y=w_y+f(x)$\n- property of perceptrons\n  - **separability**: true if some parameters get the training set perfectly correct\n  - **convergence**: if the training is separable, perceptron, will eventually converge (binary search)\n  - **mistake bound**: the maximum number of mistakes related to the **margin** or degree of separability: $mistakes < k/margin^2$\n- problems with perceptrons\n  - noise: if data isn't separable, weights might trash\n  - mediocre generalization: finds a \"barely\" separating solution\n  - overtraining \n- fixing these problems:\n  - **MIRA (margin infused relaxed algorithm)**\n    - minimum perceptron update: adjust the weight update (minimize the change to it) to mitigate the effect\n    - maximum step size: cap the maximum possible value \n    -> converage faster, better on noisy data \n  - **support vector machine**:\n    - maximizing the margin, only support vector matters\n- naive bayes vs perceptron/MIRA\n  - NB: give prediction probabilities, strong assumption about feature independence, one pass through data\n  - perceptron/MIRA: mistaken-driven learning, less assumption about data, multiple pass through data   \n \n\n## Module 12 Definitions\n* **Confidence** - represent how sure the classifier is of the classification\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n- classifier component:\n  - feature representation\n  - classification function: compute the estimated class\n  - objective function: minimize error on training example\n  - optimizing: the objective function\n- **logistic regression**:\n  - $z=w\\cdot x+b$\n  - $\\sigma(z)=y/(1+e^{-z})$ (sigmoid function)\n  - $y_{hat}=P(y=1)=\\sigma(z)$\n  - decision boundary: 1 if P(y=1)>0.5, else 0\n  - **loss function** (tell us the distance between the estimated output and golden output): **cross-entropy loss**\n    - **mean squared error**: \n  -> $L_{MSE}(y_{hat},y)=(y_{hat}-y)^2/2$\n  - **optimizer**: minimizing loss function : **gradient descent**\n- **cross-entropy loss**:\n  - 1. a function that maximizes the probability of the correct label: $p(y|x)= y_{hat}^y(1-y_{hat})^{1-y}$\n  - 2. change to log and flip the sign (to minimize): $L_{CE}(y_{hat},y)=-[ylog(y_{hat})+(1-y)log(1-y_{hat})]$\n  - loss on all training examples: $log(p(training labels))=log\\prod_{i=1}^m p(y^i|x^i)=-\\sum_{i=1}^m L_{CE}(y_{hat}^i/y^i)$\n- **gradient descent**: find a minimum of a function by figuring out which direction the function's slope is rising in the most steeply, and moving in the opposite direction\n  - $w^{t+1}=w^t-\\eta (d/dw)f(x;w)$\n  - $\\eta$: learning rate \n  - final equation: $\\theta_{t+1}=\\theta_t \\nabla L(f(x;\\theta),y)$\n  - derivative of this function: $\\partial L_{CE}(w,b)/\\partial w_j = [\\sigma (w\\cdot x+b)-y]x_j$\n- **stochastic gradient descent**: single training example at a time and update its weight on that example\n- **batch training**: compute gradient over entire dataset\n- **mini-batch training**: train on small batch\n- for multiclassification, instead of using sigmoid, we use **softmax** which normalizes its output and return probability distribution\n  - $softmax(z_i)= e^{z_j}/\\sum_{j=1}^k e^{z_j}, 1\\le i \\le k$\n- **feed forward neural network**: **multilayer network, all units are fully connected, no cycles\"\n  - $h=\\sigma(Wx+b)$\n  - $z=Uh$\n  - $y=softmax(z)$\n  - loss function: cross-entropy loss\n  - optimization algorithm: gradient descent\n  - a way of computing the gradient of the loss function: error propagation\n- cross-entropy loss:\n  - if binary: $L_{CE}(y_{hat},y)=-[ylog(y_{hat})+(1-y)log(1-y_{hat})]$\n  - if multi: $L_{CE}(y_{hat},y)=-\\sum_{i=1}^{C}y_i log(y_i^{hat})$\n  - but if there is only one correct answer: $L_{CE}(y_{hat},y)=-log(y_i^{hat})$\n- logistic regression's way of computing gradient only give correct update for the last layer. NN requires looking back on all earlier layer\n-> **error backpropagation algorithm**: use chain rules to compute the derivative\n  - $f(x)= u(v(w(x)))$ -> $df/dx=(du/dv)*(dv/dw)*(dw/dx)$\n\n\n\n## Module 13 Definitions\n* **Convex** - a convex function has one minimum\n* **Smoothness of $\\sigma$** - small changes in the weights $w_j$ and in the bias b will produce small change the output from neuron\n* **Computation graph** - represents the process of computing a mathematical expression\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- **term-document matrix**:\n  - column vectors are documents\n  - each row vector is a term\n  - value cell is how often that term occurred in the document\n  - the length of the document vector is the size of vocabulary\n  - document vector can be sparse (most values are 0)\n  - measure the similarity of documents by comparing their column vectors\n  - measure the similarity of terms by comparing their row vectors\n- **vector L2 (length) normalization**:\n  - value cell$/||u||$, $||u||=\\sqrt{\\sum_{i=1}^n u_i^2}$\n  - compare the euclidean distance, or **cosine distance**\n- **term-term (term-context) matrix**:\n  - value cell is how often that a term occurred in the context of another term\n  - **context window**\n- raw word frequency is not a great measure of associations between words (very skewed on \"of\")\n-> TF-IDF, or PPMI\n  - TF: how often a word occurred in a document\n  - IDF: 1/the number of documents that it occurred in\n- problems of **language modeling**\n  - there are too many parameters to accurately estimate, **curse of dimensionality**\n  - in n-gram-based model, we fail to generalize to related words\n- **neural language model**: \n  - pros: no need to smoothing, handle longer histories, generalize context of similar words, higher accuracy\n  - cons: slower to train\n  - first k-1 words are features, and the last word is used as the target label for classification\n  - train using cross-entropy loss\n- train a classifer to get dense vector\n  - Word2Vec: predict the surrounding words in a context window of 2C\n  - **negative sampling**: randomly sample other lexicon to get negative samples\n- embeddings (vector model of meaning) capture relational meaning\n  - especially good at modeling similarity and analogy\n  - can use sparse models (td-idf) or dense models (Word2Vec)\n\n\n## Module 14 Definitions\n* **Sparse** - most elements are zeros\n* **Dense** - most elements are non-zeros, better generalize, faster to apply in ML\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}