{
  "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": "fbbc07a7-e435-4c03-e4f3-d5e69f65b56e"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8a238016-2a3d-4635-baf3-638434c870ae"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = \"\"\" $P({RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        " \n",
        "chapter16_1 = \"\"\" - sample question: $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\n",
        "\n",
        "-  **Expected utility (EU)**: $EU(a)=\\sum_{s'}P(RESULT(a)=s')U(s')$\n",
        "\n",
        "- **MEU**: a rational agent should choose the action which maximizes its EU: *action=$argmax_a EU(a)$*\n",
        "- Relationship between **utility function** and **performance measure**: Utility function reflects like how people value a particular state, it is internal. Performance measure gives a score for a history of states, while utility function can be used to guide agent's action for next step. \"\"\"\n",
        "chapter16_2 =  \"\"\" - Lottery: $L=[p_1,S_1;...,p_n,S_n]$\n",
        "\n",
        "- **6 preference constraints** (axioms of utility theory): \n",
        "  - Orderability: Either $A \\succ B$ or $B \\succ A$ or $A \\sim B$ holds \n",
        "  - Transitivity: $A \\succ B and B \\succ C \\Rightarrow A \\succ C$. \n",
        "  - Continuity: $A\\succ B \\succ C \\Rightarrow \\exists p,[p,A;1-p,C]\\sim B$ \n",
        "  - Substitutability: $A\\sim B\\Rightarrow [p,A;1-p,C]\\sim [p,B;1-p,C]$\n",
        "  - Monotonicity: $A\\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B]\\succ [q,A;1-q,B])$\n",
        "  - Decomposability: $[p,A;1-p,[q,B; 1-q,C]]\\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n",
        "\n",
        "-  **Existence of utility function**: If an agent's preferences obey the above 6 axioms, then there exists a utility function U such that **U(A)>U(B)** if and only if A is preferred to B, and **U(A)=U(B)** if and only if agent is indifferent between A and B.\n",
        "\n",
        "- **Expected utility of lottery**: $U([p_1,S_1;...;p_n,S_n])=\\sum_{i} p_iU(S_i)$\n",
        "\n",
        "- The axioms of utility theory only guarantees that under some conditions, a utility function exists, but it is **NOT NECESSARILY UNIQUE**. $U'(s)=aU(s)+b$, **affine transformation** does not change agent policy (a>0).\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 =  \"\"\" - **preference elicitation**: present choices to human, based on observed preferences, pin down the utility function. \n",
        "\n",
        "- Best outcome: $U(S)=u_{\\\\top}$, worst outcome: $U(s)=u_{\\\\bot}$. Normalized utility: $u_{\\\\top}=1,u_{\\\\bot}=0$\n",
        "\n",
        "- **Standard lottery**: $[p,u_{\\\\top};1-p,u_{\\\\bot}]$. We can let one choose between standard lottery and S, adjust $p$ until one becomes indifferent. Then we get his utility: $U(S)=p$\n",
        "\n",
        "- **micromort**: one in a million chance of death\n",
        "\n",
        "- **EMV**: expected monetary value, which is the weighted summation of each possible monetary value. **Should NOT assume it is equal to Expected Utility**. For money, utility function is not linear in EMV. But if you have a lot of money, you will have a linear utility function in money over some range. \n",
        "\n",
        "- Utility function in money curve: Concave for positive money, convex for negative money (debt) \n",
        "\n",
        "- In the positive region, people tend to be **risk-averse**, they prefer a sure thing with a payoff less than the EMV of a lottery. That is, $U(L)<U(S_{EMV(L)})$. Conversely, in negative region, agent tends to be **risk-seeking** \n",
        "\n",
        "- **certainty equivalent**: The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. For example, say a lottery of earning 1000 with p=1/2, while 0 also with p=1/2. If an agent will be satisfied with 400 FOR SURE (or larger), then his certainty equivalent would be 400. \n",
        "\n",
        "- **insurance premium=EMV(L)-certainty equivalent of L**\n",
        "\n",
        "- If the true EU is unattainable for some reason, we may calculate an estimator of it: $\\hat{EU}(a)$. An **unbiased estimator**: $E[\\hat{EU(a)}-EU(a)]=0$\n",
        "\n",
        "- **Optimizer's cursor**: Even if we have an unbiased estimator of EU, we may still be overly optimistic and get bad results.  Because we select the action with the highest utility estimate, we are favoring the overly optimistic estimates, and that is the source of the bias. Such effect will be accumulated as sample size goes up.  \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"- Sequential Decision Problems: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process, or MDP\n",
        "\n",
        "- **Markovian transition model**: $P(s'|s,a)$, **Reward**: $R(s,a,s')$\n",
        "\n",
        "- **optimal policy**: a policy that yields highest expected utility\n",
        "\n",
        "- **stationary vs non-stationary policy**: With a finite horizon, an optimal action in a given state may depend on how much time is left. A policy that depends on the time is called nonstationary. If the game is infinite, the optimal policy does not depend on time, it is stationary. \n",
        "\n",
        "- **additive discounted rewards**: $U([s_0,a_0,s_1,a_1,...])=R(s_0,a_0,s_1)+\\gamma R(s_1,a_1,s_2)+\\gamma ^2R(s_2,a_2,s3)+...$\n",
        "\n",
        "- A policy that is guaranteed to reach a terminal state is called a **proper policy**. \n",
        "\n",
        "- **How to evaluate policy**: calculate expected utility based on history: $U^{\\pi}(s)=E[\\sum_{t=0}^{\\infty}\\gamma ^{t}R(S_t,\\pi(S_t),S_{t+1})]$. The expectation is with respect to the probability distribution over state sequences. **Optimal policy**: $\\pi^*_s=argmax_{\\pi}U^{\\pi}(s)$, where s is the starting state. If the game is stationary, optimal policy DOES NOT depend on starting state and will be always optimal. \n",
        "\n",
        "- **Bellman Equation**: the utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action thereafter. $U(s)=max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$. We can derive optimal policy from Bellman Equation: $\\pi^*(s)=argmax_a  \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n",
        "\n",
        "- **action-utility function Q(s, a)**: expected utility of taking an action in a state. $Q(s,a)=\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]=\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q(s',a')]$. **Relationship** to U: $U(s)=max_a Q(s,a)$\n",
        "\n",
        "- **Extract optimal policy from Q value**: $\\pi^*(s)=argmax_aQ(s,a)$\n",
        "\n",
        "- Affine transformation $R'(s,a,s')=mR(s,a,s')+b$ does **NOT** change optimal policy. \n",
        "\n",
        "- **Shaping theorem**: Let $\\Phi(s)$ be any function of state s. The following transformation leaves optimal policy unchanged: $R'(s,a,s')=R(s,a,s')+\\gamma \\Phi(s')-\\Phi(s)$. $\\Phi(s)$ is called a potential function.  \"\"\"\n",
        "chapter17_2 =  \"\"\" - **Value iteration**: Perform Bellman update: $U_{i+1}(s)=max_{a\\in A(s)}\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')]=max_{a\\in A(s)}Q(s,a)$. In each round, we perform Bellman update for all states, until the utility values converge. Notice: we need to update all utility values **simultaneously** using old values. Value iteration will converge to **unique set of solutions** to the Bellman equations, and the policy extracted from it is optimal.\n",
        "\n",
        "- **Contraction**: a function that (a) has one and only one fixed point; (b) Applying it to any input will move the input closer to fixed point. In the limit sense, any input will reach fixed point through repeatedly apply this function. \n",
        "\n",
        "- The Bellman update is a contraction by a factor of $\\gamma$ on the space of utility vectors So, value iteration will converge exponentially, i.e. it reaches optimal point in logarithmic steps w.r.t $\\gamma$ and $R_{max}$\n",
        "\n",
        "- **policy loss**: Suppose after i iterations of value iteration we get estimated utility $U_i(s)$ of the true utility $U(s)$. We can obtain the MEU policy $\\pi_i$ using one-step look-ahead, then the policy loss is: $||U^{\\pi_i}-U||$, where $U^{\\pi_i}$ means the utility we will obtain executing $\\pi_i$ starting from state s.\n",
        "\n",
        "- **policy iteration**: starting with some policy $\\pi_0$, alternate between the 2 steps: \n",
        "  - **policy evaluation**: Fix policy $\\pi_i$, calculate $U_i(s)=U^{\\pi_i}(s)=\\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$, the utility of each state if policy $\\pi$ were to be executed. We have n equations and n unknowns, which could be solved in O(n^3) time using a linear solver.\n",
        "  - **policy improvement**: Calculate a new MEU policy $\\pi_{i+1}$ using one-step look-ahead based on $U_i(s)$. $a^*(s)=argmax_a Q(s,a)$\n",
        "  - until policy improvement causes no change in utilities\n",
        "  - **Modified policy iteration**: during the evaluation phase, instead of directly solving the equations, perform several *value iteration* steps, to find the utility values. $U_{i+1}(s)\\leftarrow \\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$\n",
        "\n",
        "- **Linear Programming**: solve the following optimization problem: minimize all utilities, $U(s)$, for any s, constrained by $U(s)\\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "3ea42a2d-cd24-4c94-e9dd-6e9ee5dfcd5b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n - sample question: $P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\n\n-  **Expected utility (EU)**: $EU(a)=\\sum_{s'}P(RESULT(a)=s')U(s')$\n\n- **MEU**: a rational agent should choose the action which maximizes its EU: *action=$argmax_a EU(a)$*\n- Relationship between **utility function** and **performance measure**: Utility function reflects like how people value a particular state, it is internal. Performance measure gives a score for a history of states, while utility function can be used to guide agent's action for next step. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n - Lottery: $L=[p_1,S_1;...,p_n,S_n]$\n\n- **6 preference constraints** (axioms of utility theory): \n  - Orderability: Either $A \\succ B$ or $B \\succ A$ or $A \\sim B$ holds \n  - Transitivity: $A \\succ B and B \\succ C \\Rightarrow A \\succ C$. \n  - Continuity: $A\\succ B \\succ C \\Rightarrow \\exists p,[p,A;1-p,C]\\sim B$ \n  - Substitutability: $A\\sim B\\Rightarrow [p,A;1-p,C]\\sim [p,B;1-p,C]$\n  - Monotonicity: $A\\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B]\\succ [q,A;1-q,B])$\n  - Decomposability: $[p,A;1-p,[q,B; 1-q,C]]\\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n\n-  **Existence of utility function**: If an agent's preferences obey the above 6 axioms, then there exists a utility function U such that **U(A)>U(B)** if and only if A is preferred to B, and **U(A)=U(B)** if and only if agent is indifferent between A and B.\n\n- **Expected utility of lottery**: $U([p_1,S_1;...;p_n,S_n])=\\sum_{i} p_iU(S_i)$\n\n- The axioms of utility theory only guarantees that under some conditions, a utility function exists, but it is **NOT NECESSARILY UNIQUE**. $U'(s)=aU(s)+b$, **affine transformation** does not change agent policy (a>0).\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n - **preference elicitation**: present choices to human, based on observed preferences, pin down the utility function. \n\n- Best outcome: $U(S)=u_{\\top}$, worst outcome: $U(s)=u_{\\bot}$. Normalized utility: $u_{\\top}=1,u_{\\bot}=0$\n\n- **Standard lottery**: $[p,u_{\\top};1-p,u_{\\bot}]$. We can let one choose between standard lottery and S, adjust $p$ until one becomes indifferent. Then we get his utility: $U(S)=p$\n\n- **micromort**: one in a million chance of death\n\n- **EMV**: expected monetary value, which is the weighted summation of each possible monetary value. **Should NOT assume it is equal to Expected Utility**. For money, utility function is not linear in EMV. But if you have a lot of money, you will have a linear utility function in money over some range. \n\n- Utility function in money curve: Concave for positive money, convex for negative money (debt) \n\n- In the positive region, people tend to be **risk-averse**, they prefer a sure thing with a payoff less than the EMV of a lottery. That is, $U(L)<U(S_{EMV(L)})$. Conversely, in negative region, agent tends to be **risk-seeking** \n\n- **certainty equivalent**: The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. For example, say a lottery of earning 1000 with p=1/2, while 0 also with p=1/2. If an agent will be satisfied with 400 FOR SURE (or larger), then his certainty equivalent would be 400. \n\n- **insurance premium=EMV(L)-certainty equivalent of L**\n\n- If the true EU is unattainable for some reason, we may calculate an estimator of it: $\\hat{EU}(a)$. An **unbiased estimator**: $E[\\hat{EU(a)}-EU(a)]=0$\n\n- **Optimizer's cursor**: Even if we have an unbiased estimator of EU, we may still be overly optimistic and get bad results.  Because we select the action with the highest utility estimate, we are favoring the overly optimistic estimates, and that is the source of the bias. Such effect will be accumulated as sample size goes up.  \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n- Sequential Decision Problems: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process, or MDP\n\n- **Markovian transition model**: $P(s'|s,a)$, **Reward**: $R(s,a,s')$\n\n- **optimal policy**: a policy that yields highest expected utility\n\n- **stationary vs non-stationary policy**: With a finite horizon, an optimal action in a given state may depend on how much time is left. A policy that depends on the time is called nonstationary. If the game is infinite, the optimal policy does not depend on time, it is stationary. \n\n- **additive discounted rewards**: $U([s_0,a_0,s_1,a_1,...])=R(s_0,a_0,s_1)+\\gamma R(s_1,a_1,s_2)+\\gamma ^2R(s_2,a_2,s3)+...$\n\n- A policy that is guaranteed to reach a terminal state is called a **proper policy**. \n\n- **How to evaluate policy**: calculate expected utility based on history: $U^{\\pi}(s)=E[\\sum_{t=0}^{\\infty}\\gamma ^{t}R(S_t,\\pi(S_t),S_{t+1})]$. The expectation is with respect to the probability distribution over state sequences. **Optimal policy**: $\\pi^*_s=argmax_{\\pi}U^{\\pi}(s)$, where s is the starting state. If the game is stationary, optimal policy DOES NOT depend on starting state and will be always optimal. \n\n- **Bellman Equation**: the utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action thereafter. $U(s)=max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$. We can derive optimal policy from Bellman Equation: $\\pi^*(s)=argmax_a  \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n\n- **action-utility function Q(s, a)**: expected utility of taking an action in a state. $Q(s,a)=\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]=\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q(s',a')]$. **Relationship** to U: $U(s)=max_a Q(s,a)$\n\n- **Extract optimal policy from Q value**: $\\pi^*(s)=argmax_aQ(s,a)$\n\n- Affine transformation $R'(s,a,s')=mR(s,a,s')+b$ does **NOT** change optimal policy. \n\n- **Shaping theorem**: Let $\\Phi(s)$ be any function of state s. The following transformation leaves optimal policy unchanged: $R'(s,a,s')=R(s,a,s')+\\gamma \\Phi(s')-\\Phi(s)$. $\\Phi(s)$ is called a potential function.  \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n - **Value iteration**: Perform Bellman update: $U_{i+1}(s)=max_{a\\in A(s)}\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')]=max_{a\\in A(s)}Q(s,a)$. In each round, we perform Bellman update for all states, until the utility values converge. Notice: we need to update all utility values **simultaneously** using old values. Value iteration will converge to **unique set of solutions** to the Bellman equations, and the policy extracted from it is optimal.\n\n- **Contraction**: a function that (a) has one and only one fixed point; (b) Applying it to any input will move the input closer to fixed point. In the limit sense, any input will reach fixed point through repeatedly apply this function. \n\n- The Bellman update is a contraction by a factor of $\\gamma$ on the space of utility vectors So, value iteration will converge exponentially, i.e. it reaches optimal point in logarithmic steps w.r.t $\\gamma$ and $R_{max}$\n\n- **policy loss**: Suppose after i iterations of value iteration we get estimated utility $U_i(s)$ of the true utility $U(s)$. We can obtain the MEU policy $\\pi_i$ using one-step look-ahead, then the policy loss is: $||U^{\\pi_i}-U||$, where $U^{\\pi_i}$ means the utility we will obtain executing $\\pi_i$ starting from state s.\n\n- **policy iteration**: starting with some policy $\\pi_0$, alternate between the 2 steps: \n  - **policy evaluation**: Fix policy $\\pi_i$, calculate $U_i(s)=U^{\\pi_i}(s)=\\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$, the utility of each state if policy $\\pi$ were to be executed. We have n equations and n unknowns, which could be solved in O(n^3) time using a linear solver.\n  - **policy improvement**: Calculate a new MEU policy $\\pi_{i+1}$ using one-step look-ahead based on $U_i(s)$. $a^*(s)=argmax_a Q(s,a)$\n  - until policy improvement causes no change in utilities\n  - **Modified policy iteration**: during the evaluation phase, instead of directly solving the equations, perform several *value iteration* steps, to find the utility values. $U_{i+1}(s)\\leftarrow \\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$\n\n- **Linear Programming**: solve the following optimization problem: minimize all utilities, $U(s)$, for any s, constrained by $U(s)\\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n\n \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" - define **bandits problem**: Each arm $M_i$ is a **Markov reward process** or **MRP**, that is, an MDP with only one possible action $a_i$. It has states $S_i$, transition model $P_i(s'|s,a_i)$, and reward $R_i(s,a_i,s')$. The arm defines a distribution over sequences of rewards $R_{i,0},R_{i,1},R_{i,2}...$, where each $R_{i,t}$ is a random variable. The overall bandit problem is an **MDP**: the state space is given by the Cartesian product  $S=S_1\\times S_2\\times ... \\times S_n$; the actions are $a_1,a_2,...,a_n$; the transition model updates the state of whichever arm is selected, according to its specific transition model, leaving the other arms unchanged; and the discount factor is $\\gamma$. Note that the arms are **independent**. \n",
        "\n",
        "- **One-armed bandits**: There is only one arm to pull. If there are two arms, $M$ and $M_{\\lambda}$, $M$ has reward sequence $R_0,R_1,R_2...$ while $M_{\\lambda}$ has a constant (known) reward $\\lambda$, this could also be regarded as a one-armed bandits. The opportunity cost of not pulling in each step is $\\lambda$ \n",
        "\n",
        "- Optimal policy for one-armed bandits: pull $M$ for $t=0,1,...,T-1$, and always pull $M_{\\lambda}$ starting from $T$. $T$ is called the stopping time. Special case: $T$ could be 0 (immediately pull $M_{\\lambda}$ from the beginning), $\\infty$ (never pull $M_{\\lambda}$) or some value in between. \n",
        "\n",
        "- **Gittins index**: $\\lambda = max_{T>0} \\frac{E(\\sum_{t=0}^{T-1}\\gamma^tR_t)}{\\sum_{t=0}^{T-1}\\gamma^t}$, describes the maximum obtainable utility per unit of discounted time. This provides an optimal policy for any bandits problem: pull the arm that has the highest Gittins index, and update the Gittins index. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" **Classify RL algorithms**:\n",
        "\n",
        "- model-based: the agent uses a transition model of the environment to help interpret the reward signals and make decisions. The transition model could be known, or unknown initially and learned through interaction. \n",
        "- model-free: the agent does not keep a transition model. It learns a direct representation how to behave, in two variants: (a) action-utility function: eg **Q-learning**. (b) policy search: eg a reflex agent\n",
        "- passive RL: given a fixed policy, the agent learns $U(s),Q(s,a)$ and/or the transition model\n",
        "- active RL: the agent needs to figure out a policy by itself at the same time.  \"\"\"\n",
        "chapter22_2 =  \"\"\" - passive RL: the agent just follows a given policy $\\pi$ and learns $U^{\\pi}(s)$, similar to policy evaluation except that it does not know transition model nor the reward. \n",
        "\n",
        "- Learn expected utility: $U^{\\pi}(s)=E[\\sum_{t=0}^{\\infty}\\gamma ^tR(S_t,\\pi(S_t),S_{t+1})]=\\sum_{s'}P(s'|s,a)[R(s,\\pi(s),s')+\\gamma U^{\\pi}(s')]$ (*)\n",
        "\n",
        "- **direct utility estimation**: take average of **direct rewards** from multiple trials and use it as the utility value of states \n",
        "\n",
        "- **adaptive dynamic programming (ADP)**: The agent will estimate the model $P(s'|s,a)$ by counting $N_{s'|s,a}$, # times agent goes to s' by action a in state s, and estimate $U(s)$ by using similar procedure in policy evaluation, solve linear equations (*) (using  dynamic programming and plugging the rewards received)\n",
        "\n",
        "- **temporal difference learning (TD)**: update equation $U^{\\pi}(s)=U^{\\pi}(s)+\\alpha [R(s,\\pi(s),s')+\\gamma U^{\\pi}(s')-U^{\\pi}(s)]$, based on observed transition (s,a,s'). **It does not need a transition model to perform update**. In the limit, it will converge to the correct utility values for all states. We can design learning rate $\\alpha$ as a decreasing function of #visitations of states. As a particular state is visited for more and more times, we reduce the scale of TD update to stabilize. \n",
        "\n",
        "- Relationship between ADP and TD: (a) They both do local update, to make utility estimates agree with its successors; (b) TD adjust a state to agree with its *observed* successor, while ADP adjust a state to reflect all its possible successors, weighted by corresponding probability. \n",
        "\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" - **greedy agent**: take actions based on what it currently believes to be best. The policy it learned is not necessarily the true model in true environment, therefore its policy might be sub-optimal. \n",
        "\n",
        "- **GLIE**: greedy in the limit of infinite exploration. By introducing in **exploration**, the agent must try each action in each state for some times in case it misses an optimal action. \n",
        "\n",
        "- **exploration function**: Let $U^{+}(s)$ be some optimistic estimate of utility, $N(s,a)$ be the number of times seen (s, a). Then the update using exploration function *f* is: $U^{+}(s)\\leftarrow max_af(\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U^{+}(s')],N(s,a))$. *f* determines how greedy the agent (exploration-exploitation tradeoff), it is increasing in *u* and decreasing in *N*. \n",
        "\n",
        "- absorbing state: a state in which no action can be taken and no rewards get received. Just a dead end. \n",
        "\n",
        "- **safe exploration**: We need to guarantee that the agent's exploration will not lead to catastrophic result. In other words, we need to choose a policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, even if the policy happens to be suboptimal for the maximum-likelihood model.  Popular ways: \n",
        "  - Bayesian reinforcement learning\n",
        "  - robust control theory\n",
        "\n",
        "- **Temporal Difference Q-learning**: model-free approach combining Q learning and TD update. \n",
        "  - **Q-learning Bellman equation:** $Q(s,a)=\\sum_{s'}P(s'|s,a)[R(s,a,s')+max_{a'} Q(s',a')]$\n",
        "  - Q-learning TD update: $Q(s,a)\\leftarrow Q(s,a)+\\alpha[R(s,a,s')+\\gamma max_{a'} Q(s',a')-Q(s,a)]$. This is executed whenever an action a is executed in state s leading to state s'. \n",
        "  - This approach does need a transition model. \n",
        "\n",
        "- **Q-learning** is off-policy, because it performs q-value update based on the best case (max operator over $Q(s',a')$)  \"\"\"\n",
        "chapter22_4 =  \"\"\" - **function approximate**: Learning all expected utilities might not be efficient in real problem, as the size of state space and action space goes up. So, we need to use some function to approximate the utilities and Q values: $\\hat{U}_{\\theta}(s)=\\theta_1 f_1(s)+\\theta_2 f_2(s)+...+\\theta_n f_n(s)$\n",
        "\n",
        "- **Adv of approximate RL**: can learn based on limited training sets and a small set of states, and **generalize** to other states. \n",
        "\n",
        "- Update step in TD learning and Q learning: For TD, it is: $\\theta_i \\leftarrow \\theta_i + \\alpha [R(s,a,s')+\\gamma \\hat{U}_{\\theta}(s')-\\hat{U}_{\\theta}(s)]\\frac{\\partial \\hat{U}_{\\theta}(s)}{\\partial \\theta_i}$. For Q-learning, it becomes: $\\theta_i \\leftarrow \\theta_i+\\alpha [R(s,a,s')+\\gamma max_{a'}\\hat{Q}_{\\theta}(s',a')-\\hat{Q}_{\\theta}(s,a)]\\frac{\\partial \\hat{Q}_{\\theta}(s,a)}{\\partial \\theta_i}$ \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" **Regret** is a measure of your total \n",
        "mistake cost: the difference between \n",
        "your (expected) rewards, including \n",
        "youthful suboptimality, and optimal \n",
        "(expected) rewards\n",
        "Minimizing regret goes beyond \n",
        "learning to be optimal – it requires \n",
        "optimally learning to be optimal \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8a964244-d532-4435-901f-9e2b70a3e9af"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n - define **bandits problem**: Each arm $M_i$ is a **Markov reward process** or **MRP**, that is, an MDP with only one possible action $a_i$. It has states $S_i$, transition model $P_i(s'|s,a_i)$, and reward $R_i(s,a_i,s')$. The arm defines a distribution over sequences of rewards $R_{i,0},R_{i,1},R_{i,2}...$, where each $R_{i,t}$ is a random variable. The overall bandit problem is an **MDP**: the state space is given by the Cartesian product  $S=S_1\times S_2\times ... \times S_n$; the actions are $a_1,a_2,...,a_n$; the transition model updates the state of whichever arm is selected, according to its specific transition model, leaving the other arms unchanged; and the discount factor is $\\gamma$. Note that the arms are **independent**. \n\n- **One-armed bandits**: There is only one arm to pull. If there are two arms, $M$ and $M_{\\lambda}$, $M$ has reward sequence $R_0,R_1,R_2...$ while $M_{\\lambda}$ has a constant (known) reward $\\lambda$, this could also be regarded as a one-armed bandits. The opportunity cost of not pulling in each step is $\\lambda$ \n\n- Optimal policy for one-armed bandits: pull $M$ for $t=0,1,...,T-1$, and always pull $M_{\\lambda}$ starting from $T$. $T$ is called the stopping time. Special case: $T$ could be 0 (immediately pull $M_{\\lambda}$ from the beginning), $\\infty$ (never pull $M_{\\lambda}$) or some value in between. \n\n- **Gittins index**: $\\lambda = max_{T>0} \frac{E(\\sum_{t=0}^{T-1}\\gamma^tR_t)}{\\sum_{t=0}^{T-1}\\gamma^t}$, describes the maximum obtainable utility per unit of discounted time. This provides an optimal policy for any bandits problem: pull the arm that has the highest Gittins index, and update the Gittins index. \n\n## AIMA Chapter 22.1 Learning from Rewards\n **Classify RL algorithms**:\n\n- model-based: the agent uses a transition model of the environment to help interpret the reward signals and make decisions. The transition model could be known, or unknown initially and learned through interaction. \n- model-free: the agent does not keep a transition model. It learns a direct representation how to behave, in two variants: (a) action-utility function: eg **Q-learning**. (b) policy search: eg a reflex agent\n- passive RL: given a fixed policy, the agent learns $U(s),Q(s,a)$ and/or the transition model\n- active RL: the agent needs to figure out a policy by itself at the same time.  \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n - passive RL: the agent just follows a given policy $\\pi$ and learns $U^{\\pi}(s)$, similar to policy evaluation except that it does not know transition model nor the reward. \n\n- Learn expected utility: $U^{\\pi}(s)=E[\\sum_{t=0}^{\\infty}\\gamma ^tR(S_t,\\pi(S_t),S_{t+1})]=\\sum_{s'}P(s'|s,a)[R(s,\\pi(s),s')+\\gamma U^{\\pi}(s')]$ (*)\n\n- **direct utility estimation**: take average of **direct rewards** from multiple trials and use it as the utility value of states \n\n- **adaptive dynamic programming (ADP)**: The agent will estimate the model $P(s'|s,a)$ by counting $N_{s'|s,a}$, # times agent goes to s' by action a in state s, and estimate $U(s)$ by using similar procedure in policy evaluation, solve linear equations (*) (using  dynamic programming and plugging the rewards received)\n\n- **temporal difference learning (TD)**: update equation $U^{\\pi}(s)=U^{\\pi}(s)+\u0007lpha [R(s,\\pi(s),s')+\\gamma U^{\\pi}(s')-U^{\\pi}(s)]$, based on observed transition (s,a,s'). **It does not need a transition model to perform update**. In the limit, it will converge to the correct utility values for all states. We can design learning rate $\u0007lpha$ as a decreasing function of #visitations of states. As a particular state is visited for more and more times, we reduce the scale of TD update to stabilize. \n\n- Relationship between ADP and TD: (a) They both do local update, to make utility estimates agree with its successors; (b) TD adjust a state to agree with its *observed* successor, while ADP adjust a state to reflect all its possible successors, weighted by corresponding probability. \n\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n - **greedy agent**: take actions based on what it currently believes to be best. The policy it learned is not necessarily the true model in true environment, therefore its policy might be sub-optimal. \n\n- **GLIE**: greedy in the limit of infinite exploration. By introducing in **exploration**, the agent must try each action in each state for some times in case it misses an optimal action. \n\n- **exploration function**: Let $U^{+}(s)$ be some optimistic estimate of utility, $N(s,a)$ be the number of times seen (s, a). Then the update using exploration function *f* is: $U^{+}(s)\\leftarrow max_af(\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U^{+}(s')],N(s,a))$. *f* determines how greedy the agent (exploration-exploitation tradeoff), it is increasing in *u* and decreasing in *N*. \n\n- absorbing state: a state in which no action can be taken and no rewards get received. Just a dead end. \n\n- **safe exploration**: We need to guarantee that the agent's exploration will not lead to catastrophic result. In other words, we need to choose a policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, even if the policy happens to be suboptimal for the maximum-likelihood model.  Popular ways: \n  - Bayesian reinforcement learning\n  - robust control theory\n\n- **Temporal Difference Q-learning**: model-free approach combining Q learning and TD update. \n  - **Q-learning Bellman equation:** $Q(s,a)=\\sum_{s'}P(s'|s,a)[R(s,a,s')+max_{a'} Q(s',a')]$\n  - Q-learning TD update: $Q(s,a)\\leftarrow Q(s,a)+\u0007lpha[R(s,a,s')+\\gamma max_{a'} Q(s',a')-Q(s,a)]$. This is executed whenever an action a is executed in state s leading to state s'. \n  - This approach does need a transition model. \n\n- **Q-learning** is off-policy, because it performs q-value update based on the best case (max operator over $Q(s',a')$)  \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n - **function approximate**: Learning all expected utilities might not be efficient in real problem, as the size of state space and action space goes up. So, we need to use some function to approximate the utilities and Q values: $\\hat{U}_{\theta}(s)=\theta_1 f_1(s)+\theta_2 f_2(s)+...+\theta_n f_n(s)$\n\n- **Adv of approximate RL**: can learn based on limited training sets and a small set of states, and **generalize** to other states. \n\n- Update step in TD learning and Q learning: For TD, it is: $\theta_i \\leftarrow \theta_i + \u0007lpha [R(s,a,s')+\\gamma \\hat{U}_{\theta}(s')-\\hat{U}_{\theta}(s)]\frac{\\partial \\hat{U}_{\theta}(s)}{\\partial \theta_i}$. For Q-learning, it becomes: $\theta_i \\leftarrow \theta_i+\u0007lpha [R(s,a,s')+\\gamma max_{a'}\\hat{Q}_{\theta}(s',a')-\\hat{Q}_{\theta}(s,a)]\frac{\\partial \\hat{Q}_{\theta}(s,a)}{\\partial \theta_i}$ \n\n## Module 9 Lecture Notes\n **Regret** is a measure of your total \nmistake cost: the difference between \nyour (expected) rewards, including \nyouthful suboptimality, and optimal \n(expected) rewards\nMinimizing regret goes beyond \nlearning to be optimal – it requires \noptimally learning to be optimal \n\n## Module 9 Definitions\n* **Term** - your definition here\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 = \"\"\" - decision theory = probability theory + utility theory (what agent prefers and how likely to achieve that)\n",
        "\n",
        "- **MEU** (maximum expected utility): The fundamental idea of decision theory is that an agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action. \"\"\"\n",
        "chapter12_2 = \"\"\" - Notation: Sample space $\\\\Omega$, an element in it $\\\\omega$. \n",
        "\n",
        "- **inclusion-exclusion principle**: $P(a \\\\or b)=P(a)+P(b)-P(a \\\\and b)$\n",
        "\n",
        "- Kolmogorov’s axioms\n",
        "  - $0\\\\leq P(\\\\omega) \\\\leq 1 $ and $\\\\sum_{\\\\omega}P(\\\\omega)=1$\n",
        "  - inclusion-exclusion principle \"\"\"\n",
        "chapter12_3 = \"\"\" - **conditioning rule**: $P(Y)=\\\\sum_{Z}P(Y|Z)P(Z)$\n",
        "\n",
        "- Calculate conditional probability when some marginal probability is unavailable: Let $X$ be the variable we are interested in, $E$ is observed evidence, $Y$ be all the other unobserved vars, then $P(X|e)= \\\\alpha P(X, e)= \\\\alpha \\sum_y P(X,e,y)$. The key thing is to calculate the **relative proportion** of $X$ given $E=e$ and then normalize the proportions.   \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" - **Bayes Rule**: $P(Y|X)=\\\\frac{P(X|Y)P(Y)}{P(X)}$ \n",
        "\n",
        "- **conditionalized version**: $P(Y|X,e)=\\\\frac{P(X|Y,e)P(Y|e)}{P(X|e)}$\n",
        "\n",
        "- Application: $P(cause|effect)=\\\\frac{P(effect|cause)P(cause)}{P(effect)}$. **Causal: ** $P(effect|cause)$, **Diagnostic**: $P(cause|effect)$\n",
        "\n",
        "- Avoid calculate $P(effect)$: $P(cause|effect)=\\\\alpha P(effect|cause)P(cause)$, where $\\\\alpha$ is a normalization factor. Do this for every possible cause, and normalize. Essential reason: $P(effect)$ is just a constant\n",
        "\n",
        "- **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$ or $P(X|Y,Z)=P(X|Z)$, or $P(Y|X,Z)=P(Y|Z)$\n",
        "\n",
        "- Let the effect be described by a series of variables: $P(X_1,X_2,...,X_n|Cause)$, by assuming conditional independence, it becomes: $P(X_1|Cause)P(X_2|Cause)...P(X_n|Cause)$. Reduce running time from **exponential** to **linear**, thus allows the equation to **scale up well**. \n",
        "\n",
        " \"\"\"\n",
        "chapter12_6 = \"\"\" - **Naive Bayes**: $P(Cause, Effect_1,Effect_2,...,Effect_n)=P(Cause)\\\\prod_i P(Effect_i|Cause)$\n",
        "\n",
        "- Let $E$ be observed effect, $Y$ be all the other unobserved effect. Then Naive Bayes equation: $P(Cause|e)=\\\\alpha \\\\sum_y P(Cause,e,y)=\\\\alpha \\\\sum_y P(Cause)P(y|Cause)\\\\prod_j P(e_j|Cause)=\\\\alpha P(Cause)\\\\prod_j P(e_j|Cause) $ \n",
        "\n",
        "- The Naive Bayes approach scales well, and does not depend on unobserved effects.  \"\"\"\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 = \"\"\" - Use chain rule to compute joint probability: $P(w_{1:n})=P(w_1)P(w_2|w_1)P(w_3|w_{1:2})...P(w_n|w_{1:n-1})=\\\\prod_{i=1}^{n}P(w_i|w_{1:i-1})$\n",
        "\n",
        "- N-gram model: For example for bigram, use $P(w_i|w_{i-1})$ to approximate $P(w_i|w_{1:i-1})$. For general N, $P(w_i|w_{1:i-1})\\\\approx P(w_i|w_{i-N+1:i})$ ->**Markovian assumption**\n",
        "\n",
        "- **MLE for N-gram probabilities**: Use **relative frequency**, which is counts from some dataset and normalize. For instance, for bigram, $P(w_n|w_{n-1})=\\\\frac{C(w_nw_{n-1})}{C(w_{n-1})}$. For general case, $P(w_n|w_{n-N+1:n-1})=\\\\frac{C(w_{n-N+1:n-1}w_n)}{C(w_{n-N+1:n-1})}$ \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" - train set: train model; test set (held-out set): test model on unseen data. We evaluate model by checking its probability of generating the test data. \n",
        "\n",
        "- development set (devset): Initial test set used for tuning parameters. The aim is to leave some fresh test set to see the true performance of model. \n",
        "\n",
        "- **perplexity**: The perplexity (sometimes called *PP* for short) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. For test set $W=w_1 w_2...w_n$, $PP(W)=P(w_1 w_2...w_n)^{-\\\\frac{1}{N}}=\\\\sqrt[N]{\\\\frac{1}{P(w_1 w_2 ... w_N)}}=\\\\sqrt[N]{\\\\prod_{i=1}^{N}\\\\frac{1}{P(w_i|w_1...w_{i-1})}}$. Minimize perplexity = maximize the test set probability given the model\n",
        "\n",
        "- perplexity = weighted average branching factor  \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" - **Smoothing (or discounting) **: Sometimes a word may appear in a different context in test set as that in the training set. (Note that this word is **not unknown**, just the context is different). To avoid a zero probability, we need smoothing. \n",
        "\n",
        "- Original unigram model: $P(w_i)=\\\\frac{c_i}{N}$, **Laplacian smoothing**: $P_{Lap}(w_i)=\\\\frac{c_i+1}{N+V}$, where $V$ is the size of vocabulary (all distinct words from set). **adjusted count**: $c^*_i=(c_i+1)\\\\frac{N}{N+V}$. We can normalize $c^*_i$ using N to get proper probability distribution. **relative discount**: $d_c=\\\\frac{c^*}{c}$\n",
        "\n",
        "- Bigram case: originally it is $P(w_n|w_{n-1})=\\\\frac{C(w_{n-1}w_n)}{C(w_{n-1})}$, **Laplacian smoothed**: $P(w_{n}|w_{n-1})=\\\\frac{C(w_{n-1}w_n)+1}{\\sum_w (C(w_{n-1}w)+1)}=\\\\frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V}$, $c^*(w_{n-1}w_n)=\\\\frac{[C(w_{n-1}w_n)+1]\\\\times C(w_{n-1})}{C(w_{n-1})+V}$\n",
        "\n",
        "- Problem with Laplacian smoothing: shift too much probability mass from seen to unseen events\n",
        "\n",
        "- Generalization: **add-k smoothing**: $P^*(w_n|w_{n-1})=\\\\frac{C(w_{n-1}w_n)+k}{C(w_{n-1})+kV}$, where k is a float in (0, 1) \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\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",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "1c4c7c77-35bb-4598-c27e-fe40d054acfb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n - decision theory = probability theory + utility theory (what agent prefers and how likely to achieve that)\n\n- **MEU** (maximum expected utility): The fundamental idea of decision theory is that an agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n - Notation: Sample space $\\Omega$, an element in it $\\omega$. \n\n- **inclusion-exclusion principle**: $P(a \\or b)=P(a)+P(b)-P(a \\and b)$\n\n- Kolmogorov’s axioms\n  - $0\\leq P(\\omega) \\leq 1 $ and $\\sum_{\\omega}P(\\omega)=1$\n  - inclusion-exclusion principle \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n - **conditioning rule**: $P(Y)=\\sum_{Z}P(Y|Z)P(Z)$\n\n- Calculate conditional probability when some marginal probability is unavailable: Let $X$ be the variable we are interested in, $E$ is observed evidence, $Y$ be all the other unobserved vars, then $P(X|e)= \\alpha P(X, e)= \\alpha \\sum_y P(X,e,y)$. The key thing is to calculate the **relative proportion** of $X$ given $E=e$ and then normalize the proportions.   \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n - **Bayes Rule**: $P(Y|X)=\\frac{P(X|Y)P(Y)}{P(X)}$ \n\n- **conditionalized version**: $P(Y|X,e)=\\frac{P(X|Y,e)P(Y|e)}{P(X|e)}$\n\n- Application: $P(cause|effect)=\\frac{P(effect|cause)P(cause)}{P(effect)}$. **Causal: ** $P(effect|cause)$, **Diagnostic**: $P(cause|effect)$\n\n- Avoid calculate $P(effect)$: $P(cause|effect)=\\alpha P(effect|cause)P(cause)$, where $\\alpha$ is a normalization factor. Do this for every possible cause, and normalize. Essential reason: $P(effect)$ is just a constant\n\n- **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$ or $P(X|Y,Z)=P(X|Z)$, or $P(Y|X,Z)=P(Y|Z)$\n\n- Let the effect be described by a series of variables: $P(X_1,X_2,...,X_n|Cause)$, by assuming conditional independence, it becomes: $P(X_1|Cause)P(X_2|Cause)...P(X_n|Cause)$. Reduce running time from **exponential** to **linear**, thus allows the equation to **scale up well**. \n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n - **Naive Bayes**: $P(Cause, Effect_1,Effect_2,...,Effect_n)=P(Cause)\\prod_i P(Effect_i|Cause)$\n\n- Let $E$ be observed effect, $Y$ be all the other unobserved effect. Then Naive Bayes equation: $P(Cause|e)=\\alpha \\sum_y P(Cause,e,y)=\\alpha \\sum_y P(Cause)P(y|Cause)\\prod_j P(e_j|Cause)=\\alpha P(Cause)\\prod_j P(e_j|Cause) $ \n\n- The Naive Bayes approach scales well, and does not depend on unobserved effects.  \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n - Use chain rule to compute joint probability: $P(w_{1:n})=P(w_1)P(w_2|w_1)P(w_3|w_{1:2})...P(w_n|w_{1:n-1})=\\prod_{i=1}^{n}P(w_i|w_{1:i-1})$\n\n- N-gram model: For example for bigram, use $P(w_i|w_{i-1})$ to approximate $P(w_i|w_{1:i-1})$. For general N, $P(w_i|w_{1:i-1})\\approx P(w_i|w_{i-N+1:i})$ ->**Markovian assumption**\n\n- **MLE for N-gram probabilities**: Use **relative frequency**, which is counts from some dataset and normalize. For instance, for bigram, $P(w_n|w_{n-1})=\\frac{C(w_nw_{n-1})}{C(w_{n-1})}$. For general case, $P(w_n|w_{n-N+1:n-1})=\\frac{C(w_{n-N+1:n-1}w_n)}{C(w_{n-N+1:n-1})}$ \n\n## SLP Chapter 3.2 Evaluating Language Models\n - train set: train model; test set (held-out set): test model on unseen data. We evaluate model by checking its probability of generating the test data. \n\n- development set (devset): Initial test set used for tuning parameters. The aim is to leave some fresh test set to see the true performance of model. \n\n- **perplexity**: The perplexity (sometimes called *PP* for short) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. For test set $W=w_1 w_2...w_n$, $PP(W)=P(w_1 w_2...w_n)^{-\\frac{1}{N}}=\\sqrt[N]{\\frac{1}{P(w_1 w_2 ... w_N)}}=\\sqrt[N]{\\prod_{i=1}^{N}\\frac{1}{P(w_i|w_1...w_{i-1})}}$. Minimize perplexity = maximize the test set probability given the model\n\n- perplexity = weighted average branching factor  \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n - **Smoothing (or discounting) **: Sometimes a word may appear in a different context in test set as that in the training set. (Note that this word is **not unknown**, just the context is different). To avoid a zero probability, we need smoothing. \n\n- Original unigram model: $P(w_i)=\\frac{c_i}{N}$, **Laplacian smoothing**: $P_{Lap}(w_i)=\\frac{c_i+1}{N+V}$, where $V$ is the size of vocabulary (all distinct words from set). **adjusted count**: $c^*_i=(c_i+1)\\frac{N}{N+V}$. We can normalize $c^*_i$ using N to get proper probability distribution. **relative discount**: $d_c=\\frac{c^*}{c}$\n\n- Bigram case: originally it is $P(w_n|w_{n-1})=\\frac{C(w_{n-1}w_n)}{C(w_{n-1})}$, **Laplacian smoothed**: $P(w_{n}|w_{n-1})=\\frac{C(w_{n-1}w_n)+1}{\\sum_w (C(w_{n-1}w)+1)}=\\frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V}$, $c^*(w_{n-1}w_n)=\\frac{[C(w_{n-1}w_n)+1]\\times C(w_{n-1})}{C(w_{n-1})+V}$\n\n- Problem with Laplacian smoothing: shift too much probability mass from seen to unseen events\n\n- Generalization: **add-k smoothing**: $P^*(w_n|w_{n-1})=\\frac{C(w_{n-1}w_n)+k}{C(w_{n-1})+kV}$, where k is a float in (0, 1) \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" - **Bayesian network**: Basically a directed acyclic graph (DAG). The topology structure specifies the independence and dependence relationships\n",
        "\n",
        "- CPT stands for conditional probability table (only for *discreate variables*)\n",
        "\n",
        "- How to get joint probability from Bayes Net: $P(x_1, x_2, ..., x_n)= \\\\prod_{i=1}^{n}P(x_i|parents(x_i))$\n",
        "\n",
        "- **How to build a Bayes Net**: Based on **Chain rule**, $P(x_1, x_2,...,x_n)= P(x_n|x_{n-1}, ..., x_1)P(x_{n-1}|x_{n-2},...,x_1)...P(x_2|x_1)P(x_1)= \\\\prod_{i=1}^{n}P(x_i|x_{i-1}...x_1)$, where $P(X_i|X_{i-1},...,X_1)=P(X_i|parents(X_i))$. Links between nodes should represent **direct influence**. \n",
        "\n",
        "- Bayesian Nets is usually more efficient than joint probability to represent the domain, because it is **local structured**, i.e. each variable depends only on a limited amount of other variables, no matter how large the total #variables is. This reduces computational cost to **linear**. \n",
        "\n",
        "- The **order** of adding variables to the Bayesian nets matters a lot. It is better to follow **causal order**, which leads to fewer \n",
        "\n",
        "- links, easier computation or probs, so on. Conversely, **diagnostic order** gives more awkward structure. \n",
        "\n",
        "- **Conditional independence in Bayesian nets**: \n",
        "  - Each variable is conditionally independent of its non-descendants, given its parents. \n",
        "  - Each variable is conditionally independent of all other variables in the network, given its parents, children, and parents of its children - that is, given its **Markovian blanket** \n",
        "\n",
        "- General case: Whether a set of nodes X is conditionally independent of another set Y, given a third set Z. \n",
        "  - Consider the **ancestral subgraph**, which consists X, Y, Z and their ancestors\n",
        "  - Add links between any unlinked pairs of nodes that share a common child, to get a **moral graph**\n",
        "  - Replace all directed links with undirected links\n",
        "  - If Z blocks all links between X and Y in the resulting graph, then Z d-separates X and Y. In that case, X is conditionally independent of Y, given Z. Otherwise, X and Y are not necessarily conditionally independent. \n",
        "\n",
        "- Handle continuous variables: (a) Discretization; (b) Define variable using some common distribution, like Gaussian; (c) nonparametric representation, to define the conditional distribution implicitly with a collection of instances\n",
        "\n",
        "- **hybrid bayesian network**: A BN with both discrete and continuous variables\n",
        "\n",
        "- Time complexity: Suppose n boolean variables, using joint probability, time complexity: $O(2^n)$. Using BN, suppose each node has up to k parents, it is reduced to $O(n2^k)$ \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 910
        },
        "cellView": "form",
        "outputId": "403ef066-f13d-4ec1-8b1e-b37af6917dda"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n - **Bayesian network**: Basically a directed acyclic graph (DAG). The topology structure specifies the independence and dependence relationships\n\n- CPT stands for conditional probability table (only for *discreate variables*)\n\n- How to get joint probability from Bayes Net: $P(x_1, x_2, ..., x_n)= \\prod_{i=1}^{n}P(x_i|parents(x_i))$\n\n- **How to build a Bayes Net**: Based on **Chain rule**, $P(x_1, x_2,...,x_n)= P(x_n|x_{n-1}, ..., x_1)P(x_{n-1}|x_{n-2},...,x_1)...P(x_2|x_1)P(x_1)= \\prod_{i=1}^{n}P(x_i|x_{i-1}...x_1)$, where $P(X_i|X_{i-1},...,X_1)=P(X_i|parents(X_i))$. Links between nodes should represent **direct influence**. \n\n- Bayesian Nets is usually more efficient than joint probability to represent the domain, because it is **local structured**, i.e. each variable depends only on a limited amount of other variables, no matter how large the total #variables is. This reduces computational cost to **linear**. \n\n- The **order** of adding variables to the Bayesian nets matters a lot. It is better to follow **causal order**, which leads to fewer \n\n- links, easier computation or probs, so on. Conversely, **diagnostic order** gives more awkward structure. \n\n- **Conditional independence in Bayesian nets**: \n  - Each variable is conditionally independent of its non-descendants, given its parents. \n  - Each variable is conditionally independent of all other variables in the network, given its parents, children, and parents of its children - that is, given its **Markovian blanket** \n\n- General case: Whether a set of nodes X is conditionally independent of another set Y, given a third set Z. \n  - Consider the **ancestral subgraph**, which consists X, Y, Z and their ancestors\n  - Add links between any unlinked pairs of nodes that share a common child, to get a **moral graph**\n  - Replace all directed links with undirected links\n  - If Z blocks all links between X and Y in the resulting graph, then Z d-separates X and Y. In that case, X is conditionally independent of Y, given Z. Otherwise, X and Y are not necessarily conditionally independent. \n\n- Handle continuous variables: (a) Discretization; (b) Define variable using some common distribution, like Gaussian; (c) nonparametric representation, to define the conditional distribution implicitly with a collection of instances\n\n- **hybrid bayesian network**: A BN with both discrete and continuous variables\n\n- Time complexity: Suppose n boolean variables, using joint probability, time complexity: $O(2^n)$. Using BN, suppose each node has up to k parents, it is reduced to $O(n2^k)$ \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"**multinomial naive Bayes classifier:** an unordered set of words with their position, keeping only their frequency in the document. A probabilistic classifier, \n",
        "meaning that for a document d, out of all classes $c \\in C$ the classifier returns the class $\\hat{c}$ which has the maximum posterior probability given the document $\\hat{c}=argmaxP(c|d)$\n",
        "\n",
        "**Bayesian inference:** $P(x|y)$=$P(y|x)P(x)\\over P(y)$, $\\hat{c}=argmaxP(c|d)=argmax$ $P(d|c)P(c)\\over P(d)$\n",
        "\n",
        "**prior probability likelihood:** $\\hat{c}=argmax\\overbrace{P(d|c)}^{likelihood}\\overbrace{P(c)}^{prior}$, we represent a document $d$ as a set of features $f_1,f_2,...,f_n$: \n",
        "$\\hat{c}=argmax\\overbrace{f_1,f_2,...,f_n|c)}^{likelihood}\\overbrace{P(c)}^{prior}$\n",
        "\n",
        "**naive Bayes assumption:** conditional independence assumption that the probabilities $P(f_i|c)$ are independent given the class $c$ and hence can be 'naively' multiplied as follows\n",
        "$P(f_1,f_2,...,f_n|c)=P(f_1|c)P(f_2|c)...P(f_n|c)$\"\"\"\n",
        "slp_chapter4_2 = \"\"\"**How can we learned the probabilities $P(c)$ and $P(f_i|c)$?** consider maximum likelihood estimate, simply use the frequencies in the data, prior $P(c)$ we ask \n",
        "what percentage of the documents in our training set are in each class $c$. Let $N_c$ be the number of documents in our training data with class $c$ and $N_doc$ be the total number of documents. \n",
        "Then: $\\hat{P}(c)=$ $N_c\\over N_doc$, the probability $P(fi|c)$, we assume a feature is just the existence of a word in the document's bag of words, and so we'll want P(wi|c), which we compute as\n",
        "the fraction of times the word $w_i$ appears among all words in all documents of topic $c$. We first concatenate all documents with category c into one big “category c” text.\n",
        "Then we use the frequency of $w_i$ in this concatenated document to give a maximum likelihood estimate of the probability: $\\hat{P}(w_i|c)=$  $count(w_i,c)\\over \\sum_{w\\in V} count(w,c)$, Here the vocabulary \n",
        "$V$ consists of the union of all the word types in all classes, not just the words in one class $c$\n",
        "\n",
        "**Add-one(Laplace) smoothing:** suppose there are no training documents that both contain the word “fantastic” and are classified as positive. $\\hat{P}(\"fantastic\"|positive)=$  $count(\"fantastic\",positive)\\over \n",
        "\\sum_{w\\in V} count(w,positive)$ $=0$, but since naive Bayes naively multiplies all the feature likelihoods together, zero probabilities in the likelihood term for any class will cause the probability of the\n",
        "class to be zero, we use $\\hat{P}(w_i|c)=$  $count(w_i,c)+1\\over \\sum_{w\\in V} (count(w,c)+1)$\n",
        "\n",
        "**unknown words and stop words:** remove words in test data but not in training data from the test document and not include any probability for them at all, and also ignore stop wordd(very frequent words) like \n",
        "$the$ and $a$.\n",
        "\"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\"**multinomial naive Bayes:** whether a word occurs or not seems to matter more than its frequency, thus clipping the word counts in each document at 1\n",
        "\n",
        "**how to deal with negation:** during text normalization, prepend the prefix $NOT_$ to every word after a token of logical negation (n't, not, no, never) until the next punctuation mark.\n",
        "\n",
        "**sentiment lexicons:** lists of words that are preannotated with positive or negative sentiment.\"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\"**naive Bayes model can be viewed as a set of class-specific unigram language models, in which the model for each class instantiates a unigram language model:**  Since the \n",
        "likelihood features from the naive Bayes model assign a probability to each word $P(word|c)$, the model also assigns a probability to each sentence: $P(s|c)=\\prod_{i \\in positions} P(w_i|c)$\n",
        "\"\"\"\n",
        "slp_chapter4_7 = \"\"\"**confusion matrix:** true positive(system positive & gold positive), false positive(system positive & gold negative), false negative(system negative & gold positive), true negative(system negative & gold negative)\n",
        "\n",
        "**Presition(measures the percentage of the items that the system detected that are in fact positive):** $Presition=$ $true positives \\over true positives + false positives$\n",
        "\n",
        "**Recall(measures the percentage of items actually present in the input that were correctly identified by the system):** $Recall=$ $true positives \\over true positives + false negatives$\n",
        "\n",
        "**F-mearure:** $F_{beta}=$ $(beta^2 + 1)PR \\over beta^2P + R$ $beta>1$, favor recall, opposite is the same\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\"**Cross validation:** we randomly choose a training and test set division of our data, train our classifier, and then compute the error rate on the test set. Then \n",
        "we repeat with a different randomly selected training set and test set. We do this sampling process 10 times and average these 10 runs to get an average error rate. This is called 10-fold cross-validation.\n",
        "\n",
        "**How to deal with overestimation of the system:** create a fixed training set and test set, then do 10-fold cross-validation inside the training set, but compute error rate the normal way in the test set.\"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" - **Naive Bayes**: Assume effects are independent of each other, given the label. $P(Y|X_1,X_2,...,X_N)=Y(Y)\\\\prod_{i=1}^{N}P(X_i|Y)$, time complexity: $|Y|\\\\times N\\\\times |X|$ where |Y| and |X| are the domain size of X and Y, respectively. This is obviously smaller than using the joint model $P(Y,X_1,...,X_N)$ with independence assumption $|Y|\\\\times |X|^N$\n",
        "\n",
        "- Bag of words: Use Naive Bayes for text classification. DOES NOT consider the ordering of words. Each word is identically and (conditionally) independently distributed, given the label. \n",
        "\n",
        "- Learn parameters on training set -> tune hyperparameters on held out set -> test accuracy on test set\n",
        "\n",
        "- **maximum likelihood estimator (MLE)**: $P_{MLE}(x)=\\\\frac{Count(x)}{All_samples}$\n",
        "\n",
        "- To address \"unseen data\" problem: (a) Laplacian smoothing (b) Linear interpolation: $P_{LIN}(x|y)=\\\\alpha \\\\hat{P}(x|y)+(1-\\\\alpha)\\\\hat{P}(x)$, where $\\\\hat{P}(x|y)$ and $\\\\hat{P}(x)$ are empirical distribution we get from training data. \n",
        "\n",
        "- **Confidence of classifier**: Describes how sure the classifier about its decision. $confidence(x)=max_y P(y|x)$ \n",
        "\n",
        "- **Perceptron**: \n",
        "  - Linear classification: $activation(x)=\\sum_i w_if_i(x)=w · f$, activation function is just SUM. $w$本质上是分类平面的法向量\n",
        "  - positive -> y*=1, negative -> y*= -1\n",
        "  - How to update weights: If $y=y^*$, no change. If incorrect, $w\\leftarrow w+y^*·f$ (Here $y^*$ is the groundtruth)\n",
        "  - **Multi-class perceptron**: One weight vector $w_y$ for each class. Prediction: $y=argmax_y w_y·f$. If prediction is correct, no need to change. If wrong, $w_y\\leftarrow w_y-f, w_{y^*}\\leftarrow w_{y^*}+f$, lower score of wrong answer, higher score of correct answer\n",
        "  - Problems with perceptron: Weights do not make sense when data is nonseparable, generalizes poorly ... \n",
        "  - **Solution**: **MIRA (margin infused relaxed algorithm)** and **minimum correcting update**. We want to minimize the changes in weight: $min_w \\\\frac{1}{2}||w_y-w'_y||^2$, s.t. $ w_{y^*}·f(x)\\\\geq w_y ·f(x)+1$. Update: $w_y = w_y'-\\\\tau f(x),w_{y^*}=w_{y^*}'+\\\\tau f(x)$ (* denotes ground-truth)\n",
        "  - $min_w \\\\frac{1}{2}||w_y - w'_y||^2 \\\\Leftrightarrow min_{\\\\tau}||\\\\tau f||^2$. Combined with the update equation, $(w_{y^*}'+\\\\tau f)·f=(w'_y-\\\\tau f)·f+1, \\\\tau=\\\\frac{(w'_y-w'_{y^*})·f+1}{2f·f}$\n",
        "  - In practice, a too large step-size is also bad => can cap the maximum step size $\\\\tau ^* = min(\\\\tau, C)$ (C is some constant)\n",
        "\n",
        "- **SVM**: $min_w \\\\frac{1}{2}||w||^2,s.t.\\\\forall i,y,w_{y^*}·f(x)\\\\geq w_y ·f(x)+1$\n",
        "\n",
        "- Logical functions: Networks of perceptrons can represent any logical operator.  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "baff096c-fadf-4a16-c34d-235aec679e93"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n**multinomial naive Bayes classifier:** an unordered set of words with their position, keeping only their frequency in the document. A probabilistic classifier, \nmeaning that for a document d, out of all classes $c \\in C$ the classifier returns the class $\\hat{c}$ which has the maximum posterior probability given the document $\\hat{c}=argmaxP(c|d)$\n\n**Bayesian inference:** $P(x|y)$=$P(y|x)P(x)\\over P(y)$, $\\hat{c}=argmaxP(c|d)=argmax$ $P(d|c)P(c)\\over P(d)$\n\n**prior probability likelihood:** $\\hat{c}=argmax\\overbrace{P(d|c)}^{likelihood}\\overbrace{P(c)}^{prior}$, we represent a document $d$ as a set of features $f_1,f_2,...,f_n$: \n$\\hat{c}=argmax\\overbrace{f_1,f_2,...,f_n|c)}^{likelihood}\\overbrace{P(c)}^{prior}$\n\n**naive Bayes assumption:** conditional independence assumption that the probabilities $P(f_i|c)$ are independent given the class $c$ and hence can be 'naively' multiplied as follows\n$P(f_1,f_2,...,f_n|c)=P(f_1|c)P(f_2|c)...P(f_n|c)$\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n**How can we learned the probabilities $P(c)$ and $P(f_i|c)$?** consider maximum likelihood estimate, simply use the frequencies in the data, prior $P(c)$ we ask \nwhat percentage of the documents in our training set are in each class $c$. Let $N_c$ be the number of documents in our training data with class $c$ and $N_doc$ be the total number of documents. \nThen: $\\hat{P}(c)=$ $N_c\\over N_doc$, the probability $P(fi|c)$, we assume a feature is just the existence of a word in the document's bag of words, and so we'll want P(wi|c), which we compute as\nthe fraction of times the word $w_i$ appears among all words in all documents of topic $c$. We first concatenate all documents with category c into one big “category c” text.\nThen we use the frequency of $w_i$ in this concatenated document to give a maximum likelihood estimate of the probability: $\\hat{P}(w_i|c)=$  $count(w_i,c)\\over \\sum_{w\\in V} count(w,c)$, Here the vocabulary \n$V$ consists of the union of all the word types in all classes, not just the words in one class $c$\n\n**Add-one(Laplace) smoothing:** suppose there are no training documents that both contain the word “fantastic” and are classified as positive. $\\hat{P}(\"fantastic\"|positive)=$  $count(\"fantastic\",positive)\\over \n\\sum_{w\\in V} count(w,positive)$ $=0$, but since naive Bayes naively multiplies all the feature likelihoods together, zero probabilities in the likelihood term for any class will cause the probability of the\nclass to be zero, we use $\\hat{P}(w_i|c)=$  $count(w_i,c)+1\\over \\sum_{w\\in V} (count(w,c)+1)$\n\n**unknown words and stop words:** remove words in test data but not in training data from the test document and not include any probability for them at all, and also ignore stop wordd(very frequent words) like \n$the$ and $a$.\n\n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n**multinomial naive Bayes:** whether a word occurs or not seems to matter more than its frequency, thus clipping the word counts in each document at 1\n\n**how to deal with negation:** during text normalization, prepend the prefix $NOT_$ to every word after a token of logical negation (n't, not, no, never) until the next punctuation mark.\n\n**sentiment lexicons:** lists of words that are preannotated with positive or negative sentiment.\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**naive Bayes model can be viewed as a set of class-specific unigram language models, in which the model for each class instantiates a unigram language model:**  Since the \nlikelihood features from the naive Bayes model assign a probability to each word $P(word|c)$, the model also assigns a probability to each sentence: $P(s|c)=\\prod_{i \\in positions} P(w_i|c)$\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n**confusion matrix:** true positive(system positive & gold positive), false positive(system positive & gold negative), false negative(system negative & gold positive), true negative(system negative & gold negative)\n\n**Presition(measures the percentage of the items that the system detected that are in fact positive):** $Presition=$ $true positives \\over true positives + false positives$\n\n**Recall(measures the percentage of items actually present in the input that were correctly identified by the system):** $Recall=$ $true positives \\over true positives + false negatives$\n\n**F-mearure:** $F_{beta}=$ $(beta^2 + 1)PR \\over beta^2P + R$ $beta>1$, favor recall, opposite is the same\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n**Cross validation:** we randomly choose a training and test set division of our data, train our classifier, and then compute the error rate on the test set. Then \nwe repeat with a different randomly selected training set and test set. We do this sampling process 10 times and average these 10 runs to get an average error rate. This is called 10-fold cross-validation.\n\n**How to deal with overestimation of the system:** create a fixed training set and test set, then do 10-fold cross-validation inside the training set, but compute error rate the normal way in the test set.\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 - **Naive Bayes**: Assume effects are independent of each other, given the label. $P(Y|X_1,X_2,...,X_N)=Y(Y)\\prod_{i=1}^{N}P(X_i|Y)$, time complexity: $|Y|\\times N\\times |X|$ where |Y| and |X| are the domain size of X and Y, respectively. This is obviously smaller than using the joint model $P(Y,X_1,...,X_N)$ with independence assumption $|Y|\\times |X|^N$\n\n- Bag of words: Use Naive Bayes for text classification. DOES NOT consider the ordering of words. Each word is identically and (conditionally) independently distributed, given the label. \n\n- Learn parameters on training set -> tune hyperparameters on held out set -> test accuracy on test set\n\n- **maximum likelihood estimator (MLE)**: $P_{MLE}(x)=\\frac{Count(x)}{All_samples}$\n\n- To address \"unseen data\" problem: (a) Laplacian smoothing (b) Linear interpolation: $P_{LIN}(x|y)=\\alpha \\hat{P}(x|y)+(1-\\alpha)\\hat{P}(x)$, where $\\hat{P}(x|y)$ and $\\hat{P}(x)$ are empirical distribution we get from training data. \n\n- **Confidence of classifier**: Describes how sure the classifier about its decision. $confidence(x)=max_y P(y|x)$ \n\n- **Perceptron**: \n  - Linear classification: $activation(x)=\\sum_i w_if_i(x)=w · f$, activation function is just SUM. $w$本质上是分类平面的法向量\n  - positive -> y*=1, negative -> y*= -1\n  - How to update weights: If $y=y^*$, no change. If incorrect, $w\\leftarrow w+y^*·f$ (Here $y^*$ is the groundtruth)\n  - **Multi-class perceptron**: One weight vector $w_y$ for each class. Prediction: $y=argmax_y w_y·f$. If prediction is correct, no need to change. If wrong, $w_y\\leftarrow w_y-f, w_{y^*}\\leftarrow w_{y^*}+f$, lower score of wrong answer, higher score of correct answer\n  - Problems with perceptron: Weights do not make sense when data is nonseparable, generalizes poorly ... \n  - **Solution**: **MIRA (margin infused relaxed algorithm)** and **minimum correcting update**. We want to minimize the changes in weight: $min_w \\frac{1}{2}||w_y-w'_y||^2$, s.t. $ w_{y^*}·f(x)\\geq w_y ·f(x)+1$. Update: $w_y = w_y'-\\tau f(x),w_{y^*}=w_{y^*}'+\\tau f(x)$ (* denotes ground-truth)\n  - $min_w \\frac{1}{2}||w_y - w'_y||^2 \\Leftrightarrow min_{\\tau}||\\tau f||^2$. Combined with the update equation, $(w_{y^*}'+\\tau f)·f=(w'_y-\\tau f)·f+1, \\tau=\\frac{(w'_y-w'_{y^*})·f+1}{2f·f}$\n  - In practice, a too large step-size is also bad => can cap the maximum step size $\\tau ^* = min(\\tau, C)$ (C is some constant)\n\n- **SVM**: $min_w \\frac{1}{2}||w||^2,s.t.\\forall i,y,w_{y^*}·f(x)\\geq w_y ·f(x)+1$\n\n- Logical functions: Networks of perceptrons can represent any logical operator.  \n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = r\"\"\"**The difference of logistic regression and naive bayes:** naive bayes is a generative model but logistic regression is a discriminative model.\n",
        "\n",
        "**Weight and bias:** $z=(\\sum_{i=1}^n w_ix_i) + b$\n",
        "\n",
        "**Sigmoid function:** $y=\\sigma (z)=$ $1\\over 1 + e^{-z}$, making the linear layer to the probabilities.\n",
        "\n",
        "**Decision boundary:** $\\hat{y}=1\\quad if P(y=1|x)>0.5$, $\\hat{y}=0 \\quad otherwise$\n",
        "\"\"\"\n",
        "slp_chapter5_2 = \"\"\"**lost fuction and cost function:** the distance between the system output and the gold output, and the average of the loss function of multiple samples.\n",
        "\n",
        "**How to learn the parameters:** gradient descent, stochastic gradient descent, mini_batch gradient descent.\"\"\"\n",
        "slp_chapter5_3 = r\"\"\"**The lost function of the logistic regression:** cross-entropy loss, $L(\\hat{y}, y)=$ How much $\\hat{y}$ differs from the true $y$   \n",
        "$L_{CE}(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\"\"\"\n",
        "slp_chapter5_4 = r\"\"\"**Convex function:** A convex function has just one minimum; there are no local minima to get stuck in, so gradient\n",
        "descent starting from any point is guaranteed to find the minimum.\n",
        "\n",
        "**Gradient:** The gradient descent algorithm answers this question by finding the gradient of the loss function at the current point and moving in the opposite direction. \n",
        "The gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function.\n",
        "\n",
        "**Learning rate:** The magnitude of the amount to move in gradient descent is the value of the slope $d\\over dw$ $f(x; w)$ weighted by a learning rate $η$.\n",
        "\n",
        "**Mini-batch training and stochastic gradient decent:** in batch training we compute the gradient over the entire dataset. By seeing so many examples, batch training offers \n",
        "a superb estimate of which direction to move the weights, at the cost of spending a lot of time processing every single example in the training set to compute this perfect direction.\n",
        "In mini-batch training, we train on a group of m examples that is less than the whole dataset. (If $m=1$ we are doing stochastic).\"\"\"\n",
        "slp_chapter5_5 = \"\"\"**Regularization is also called generalization:** the purpose is to reduce overfitting.\"\"\"\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 = \"\"\" - Classifier component: feature $x=[x_1,x_2,...,x_n]$, classification function $p(y|x)$, loss function, optimizer. For **logistic regression**, we use **cross entropy loss** and **stochastic gradient descent**. \n",
        "\n",
        "- **logistic regression**: for each $x \\\\in X$, where $X$ denotes the training set, calculate $z=w · x+b, p(y=1|x)= \\\\hat{y}=Sigmoid(z)= \\\\frac{1}{1+e^{-z}}$\n",
        "\n",
        "- **Loss function**: Maximize the log likelihood on training set <=> minimize cross entropy loss (negative log likelihood). \n",
        "  - For one sample $(x, y)$, likelihood: $p(y|x)=\\\\hat{y}^y (1- \\\\hat{y})^{1-y}$, log: $logp(y|x)=y log \\\\hat{y}+(1-y)log(1- \\\\hat{y})$\n",
        "  - **CE**: $L_{CE}(y, \\\\hat{y})=-(ylog \\\\hat{y}+(1-y)log(1- \\\\hat{y}))$\n",
        "  - Take average across the training set: $L_{CE}=-log\\prod_{i=1}^n \\hat{y_i}^{y_i}(1- \\\\hat{y_i})^{1-y_i}=-\\sum [y_i log( \\\\hat{y_i})+(1-y_i)log(1- \\\\hat{y_i})]$ (divide by training set size to average)\n",
        "  - **gradient descent**: $w^{t+1}=w^{t}-\\eta \\\\frac{d}{dw}L_{CE}( \\\\hat{y}, y|x)$. $\\\\frac{ \\partial L_{CE}}{\\partial w_i}=(\\sigma(w · x + b)-y)x_i$. The gradient for multiple data points is just the sum of individual gradients. \n",
        "  - One useful property: $d \\sigma / dz=(1- \\sigma) \\sigma$\n",
        "  - **multinomial Cross entropy**: $L_{CE}=- \\\\sum_{i=1}^{k}y_i log( \\\\hat{y_i})$, k is # classes\n",
        "\n",
        "- **Stochastic gradient descent** chooses one single example at a time to update the parameters. Can also use a batch (over entire dataset) or minibatch version. \n",
        "\n",
        "- LASSO regression: uses l1 regularization; **ridge regression**: uses l2 regularization\n",
        "\n",
        "- For **multi-class classification**: use **softmax** as a generalization to sigmoid. The probability that an instance belong to class i among k classes: $softmax(z_i)= \\\\frac{e^{z_i}}{ \\\\sum_{j=1}^k e^{z_j}}, i \\\\in [1,...,k]$\n",
        "\n",
        "- **activation function**: $a=f(z)$, a can be Sigmoid, tanh, rectified linear unit (ReLU). ReLU: $f(x)=max(x,0)$  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8ed29656-b64d-4bb6-8e5d-616b8be06912"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n**The difference of logistic regression and naive bayes:** naive bayes is a generative model but logistic regression is a discriminative model.\n\n**Weight and bias:** $z=(\\sum_{i=1}^n w_ix_i) + b$\n\n**Sigmoid function:** $y=\\sigma (z)=$ $1\\over 1 + e^{-z}$, making the linear layer to the probabilities.\n\n**Decision boundary:** $\\hat{y}=1\\quad if P(y=1|x)>0.5$, $\\hat{y}=0 \\quad otherwise$\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n**lost fuction and cost function:** the distance between the system output and the gold output, and the average of the loss function of multiple samples.\n\n**How to learn the parameters:** gradient descent, stochastic gradient descent, mini_batch gradient descent.\n\n## SLP Chapter 5.3 The cross-entropy loss function\n**The lost function of the logistic regression:** cross-entropy loss, $L(\\hat{y}, y)=$ How much $\\hat{y}$ differs from the true $y$   \n$L_{CE}(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n\n## SLP Chapter 5.4 Gradient Descent\n**Convex function:** A convex function has just one minimum; there are no local minima to get stuck in, so gradient\ndescent starting from any point is guaranteed to find the minimum.\n\n**Gradient:** The gradient descent algorithm answers this question by finding the gradient of the loss function at the current point and moving in the opposite direction. \nThe gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function.\n\n**Learning rate:** The magnitude of the amount to move in gradient descent is the value of the slope $d\\over dw$ $f(x; w)$ weighted by a learning rate $η$.\n\n**Mini-batch training and stochastic gradient decent:** in batch training we compute the gradient over the entire dataset. By seeing so many examples, batch training offers \na superb estimate of which direction to move the weights, at the cost of spending a lot of time processing every single example in the training set to compute this perfect direction.\nIn mini-batch training, we train on a group of m examples that is less than the whole dataset. (If $m=1$ we are doing stochastic).\n\n## SLP Chapter 5.5 Regularization\n**Regularization is also called generalization:** the purpose is to reduce overfitting.\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 - Classifier component: feature $x=[x_1,x_2,...,x_n]$, classification function $p(y|x)$, loss function, optimizer. For **logistic regression**, we use **cross entropy loss** and **stochastic gradient descent**. \n\n- **logistic regression**: for each $x \\in X$, where $X$ denotes the training set, calculate $z=w · x+b, p(y=1|x)= \\hat{y}=Sigmoid(z)= \\frac{1}{1+e^{-z}}$\n\n- **Loss function**: Maximize the log likelihood on training set <=> minimize cross entropy loss (negative log likelihood). \n  - For one sample $(x, y)$, likelihood: $p(y|x)=\\hat{y}^y (1- \\hat{y})^{1-y}$, log: $logp(y|x)=y log \\hat{y}+(1-y)log(1- \\hat{y})$\n  - **CE**: $L_{CE}(y, \\hat{y})=-(ylog \\hat{y}+(1-y)log(1- \\hat{y}))$\n  - Take average across the training set: $L_{CE}=-log\\prod_{i=1}^n \\hat{y_i}^{y_i}(1- \\hat{y_i})^{1-y_i}=-\\sum [y_i log( \\hat{y_i})+(1-y_i)log(1- \\hat{y_i})]$ (divide by training set size to average)\n  - **gradient descent**: $w^{t+1}=w^{t}-\\eta \\frac{d}{dw}L_{CE}( \\hat{y}, y|x)$. $\\frac{ \\partial L_{CE}}{\\partial w_i}=(\\sigma(w · x + b)-y)x_i$. The gradient for multiple data points is just the sum of individual gradients. \n  - One useful property: $d \\sigma / dz=(1- \\sigma) \\sigma$\n  - **multinomial Cross entropy**: $L_{CE}=- \\sum_{i=1}^{k}y_i log( \\hat{y_i})$, k is # classes\n\n- **Stochastic gradient descent** chooses one single example at a time to update the parameters. Can also use a batch (over entire dataset) or minibatch version. \n\n- LASSO regression: uses l1 regularization; **ridge regression**: uses l2 regularization\n\n- For **multi-class classification**: use **softmax** as a generalization to sigmoid. The probability that an instance belong to class i among k classes: $softmax(z_i)= \\frac{e^{z_i}}{ \\sum_{j=1}^k e^{z_j}}, i \\in [1,...,k]$\n\n- **activation function**: $a=f(z)$, a can be Sigmoid, tanh, rectified linear unit (ReLU). ReLU: $f(x)=max(x,0)$  \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" \n",
        "**Goal:** Explore the two architectures primarily through the lens of probabilistic.\n",
        "\n",
        "**Language Model:** give us the ability to assign a conditional probability to every next word, giving a distribution over the entire vocabulary.\n",
        "\n",
        "**First equation:** $P(w_{1:n})= \\prod_{i=1}^{n}P(w_i|w_{<i})$: provides a clear training objective based on the model for next word in a sequence.\n",
        "\n",
        "**Two methods to instantiate probabilistic language model:** N-gram models, feedforward neural networks with sliding windows, but are constrained by Markov assumption: \n",
        "$P(w_{n}|w_{1:n-1})≈P(w_{n}|w_{(n-N+1):(n-1)})$, which has a fixed preceding context of size N: any input that occured earlier than that has no bearing on the outcome.\n",
        "            \n",
        "**Evaluation:** examine how well the  language model predict unseen data. Good models assign higher probabilities to unseen data. We use **preplexity(PP)** as a measure \n",
        "of model $θ$ quality.\n",
        "\"\"\"\n",
        "slp_chapter9_2 = \"\"\"  \n",
        "**Definition for RNN:** any network that contains a cycle within its network connections, which is any network where the value of a unit is dependent on its earlier outputs as an input.\n",
        "\n",
        "**RNN process:** an input vector represesnt the current input. Then multiply a weight matrix and pass through a non-linear activation function to compute the values \n",
        "for a layer of hidden units which is used to calculate the corresponding output.\n",
        "\n",
        "**Difference between Feedforward network and RNN:** RNN augments the input to the compuation at the hidden layer with the value of the hidden layer from the preceding point in time.\n",
        "  \n",
        "             \"\"\"\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 = \"\"\" \n",
        "**Lexical Semantics:** draw on results in the linguistic study of meaning.\n",
        "\n",
        "**Lemmas:** citation form (verb), the specific forms are called wordforms. The lemmas can be polysemous.\n",
        "\n",
        "**Synonymy:** when one word has a sense whose meaning is identical to a sense of another word, or nearly identical, we say the two senses of those two words are synonyms.\n",
        "\n",
        "**Propositional meaning:** two words are synonymous if they are substitutable for one another in any sentence without changing \n",
        "            the truth conditions of the sentence, the situations in which the sentence would be true.\n",
        "\n",
        "**Principle of Contrast:** states that a difference in linguistic form is always associated with some difference in meaning.\n",
        "\n",
        "**Word similarity:** While words don’t have many synonyms, most words do have lots of similar words.\n",
        "\n",
        "**Word relatedness:** The meaning of two words can be related in ways.\n",
        "             \"\"\"\n",
        "slp_chapter6_2 = \"\"\" \n",
        "**Vector Semantics:** standard way to represent word meaning in NLP.\n",
        "\n",
        "**Embeddings:** vectors for representing words.\n",
        "\n",
        "**tf-idf model:** an important baseline, the meaning of a word is defined by a simple function of the counts of nearby words. \n",
        "            We will see that this method results in very long vectors that are sparse.\n",
        "\n",
        "**word2vec model:** construct short, dense vectors that have useful semantic properties\n",
        "            \n",
        "**cosine:** the standard way to use embeddings to compute semantic similarity, between two words, two sentences, or two documents, \n",
        "            an important tool in practical applications\"\"\"\n",
        "slp_chapter6_3 = \"\"\" \n",
        "Vector or distributional models of meaning are generally based on a **co-occurrence matrix**, a way of representing how often words co-occur.\n",
        "\n",
        "**term-document matrix:** each row represents a word in the vocabulary and each column represents a document from some collection of documents.\n",
        "Words in each document(row vector), document of each words(column vector).\n",
        "\n",
        "**Term-document matrices** were originally defined as a means of finding similar documents for the task of document information retrieval.Information retrieval \n",
        "is the task of finding the document d from the D documents in some collection that best matches a query q.\n",
        "            \n",
        "**term-term matrix(word-word matrix or term-context matrix):** columns are labeled by words rather than documents. dimensionality: |V|*|V|\"\"\"\n",
        "slp_chapter6_4 = \"\"\" \n",
        "**Cosine for measuring similarity:** Use dot product(inner product) which has high values in same dimensions, zero in orthogonal vectors.\n",
        "**Problem:** it favors long vectors and we’d like a similarity metric that tells us how similar two words are regardless of their frequency and length. So, we use normalized dot product.\n",
        "For unit vectors, the dot product is the same as the cosine, $cos(v, w) =$ $vw\\over |v||w|$.\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter6_8 = \"\"\" \n",
        "**Word2vec:** short dense vectors embeddings are short with the number of dimensions d ranging from 50-1000. The values will be real-valued numbers that can be negative, \n",
        "which makes the dense vector works better in NLP. The lower dimensionality makes the classifier learn faster. The dense vector is also good at capturing synoymy.\n",
        "\n",
        "**The advantages of word2vec:** fast and efficient to train and easily avaiable online with code and pretrained embeddings. Static embedding(learn one fixed embedding for each word in the vocabulary).\n",
        "\n",
        "**self-supervision:** obtains supervisory signals from the data itself\n",
        "\n",
        "**why word2vec is simpler than neural network language model:** word2vec simplifies the task(makes it binary classification instead of word prediction) **and**\n",
        "word2vec simplifies the architecture(training a logistic regression classifier instead of a multi-layer neural network with hidden layers that demand more sophisticated training algorithms).\n",
        "\n",
        "**process of slip-gram:** (1)given a tuple $(w,c)$ of a target word $w$ paired with a candidate context word $c$, return the probability that $c$ is context word: $P(+|w,c)$\n",
        "(2)the probablity that the word is not a real context for $w$, just 1 minus the real $c$ probability: $P(-|w,c) = 1 - P(+|w,c)$ (3)base the proability on embedding similarity: \n",
        "two vectors are similar if they have a high dot product, Similarity(w,c) ≈ c*w (4)Since dot product can be negative while probability cannot be negative, use logistic or \n",
        "sigmoid function (5)Model the probability that the word $c$ is a real context word for target word $w$: $P(+|w,c) =$ $\\sigma(c*w)=$ $1\\over 1+exp^{-c*w}$\n",
        "(6)As $c$ is not a real context word for $w$: $P(-|w,c) = 1 - P(+|w,c)$\n",
        "(7)As many context words in the window and Skip-gram makes the simplying assumption that all context words are independent\n",
        "\n",
        "**Learning skip-gram embeddings:** skip-gram with negative sampling(SGNS) uses more negative examples than positive examples with a ratio $k$ between them, for each $(w, c_{positive})$, \n",
        "create $k$ negative samples, each consisting of the target $w$ plus a \"noise word(a random word from the lexicon, constrained not to be the target word w)\" $c_negative$.\n",
        "The noise words are chosen according to their weighted unigram frequency $P_{α}(w)$, where $α$ is a weight.\n",
        "            \n",
        "**The learning algorithm:** adjust those embeddings to (1)Maximize the similarity of the target word, context word pairs (w; c_{pos}) drawn from the positive examples\n",
        "(2)Minimize the similarity of the (w;c_neg) pairs from the negative examples. By minimizing the loss function $L_{CE} = -log[P(+|w,c_{pos})$ $\\prod_{i=1}^k$ $P(-|w,c_{neg_{i}})] = -[log \\sigma(c_{pos}w) + $\n",
        " $\\sum_{i=1}^k$ $log \\sigma(-c_{neg_{i}}w)]$\n",
        "            \"\"\"\n",
        "slp_chapter6_10 = \"\"\" \n",
        "**Semantic properties of embeddings:** 1. Different types of similarity or association: (1)Shorter context windows tend to lead to representations that are a bit more syntactic, \n",
        "since the information comes from immediately nearby words. (2)When the vectors are computed from short context windows, the most similar words to a target word w tend to be semantically similar words \n",
        "with the same parts of speech. (3)When vectors are computed from long context windows, the highest cosine words to a target word w tend to be words that are topically related \n",
        "but not similar. (4)first-order co-occurrence(syntagmatic association): if they are typically nearby each other, second-order co-occurrence(paradigmatic association): if they have similar neighbors. 2. Analogy/Relational Similarity: (1)parallelogram model: solving simple analogy problems of the form $a$ is to $b$ as $a*$ is to what? (2)Equation: $\\hat{b}^* = argmax_x distance(x, a^*-a+b)$\n",
        "\"\"\"\n",
        "slp_chapter6_11 = \"\"\" \n",
        "1. allocational harm: a system alloharm cates resources (jobs or credit) unfairly to different groups\n",
        "\n",
        "2. Embeddins reflect the statistics of their input and amplify bias.\n",
        "\n",
        "3. gendered terms become more gendered in embedding space than they were in the input text statistics\n",
        "\n",
        "4. Embeddings encodes the implicit associations that are a property of human reasoning.\n",
        "\n",
        "5. reprerepresentational harm: a harm caused by a system demeaning or even ignoring some social groups\n",
        "\n",
        "6. debiasing: reduce bias in embeddings not eliminate it\n",
        "  (1): developing a transformation of the embedding space that removes gender stereotypes but preserves definitional gender\n",
        "  (2): changing the training procedure\n",
        "             \"\"\"\n",
        "slp_chapter6_12 = \"\"\" \n",
        "**how to Evaluating Vector Models:**\n",
        "\n",
        "1. Evaluation metric for vector model: extrinsic evaluation on tasks using vectors in an NLP task and seeing whether this improves performance over some other model\n",
        "\n",
        "2. Intrinsic evalution matric is to test their performance on similarity: computing the correlation between an algorithm’s word similarity scores and word similarity ratings assigned by humans.\n",
        "\n",
        "3. Dataset: \n",
        "\n",
        "  (1): WordSim-353: a commonly used set of ratings from 0 to 10 for 353 noun pairs\n",
        "\n",
        "  (2): SimLex-999: is a more difficult dataset that quantifies similarity (cup, mug) rather than relatedness (cup, coffee), and including both concrete and abstract adjective, noun and verb pairs\n",
        "\n",
        "  (3): TOEFL: a set of 80 questions,  each consisting of a target word with 4 additional word choices; the task is to choose which is the correct synonym\n",
        "\n",
        "4. Slightly more realistic are intrinsic similarity tasks that include context\n",
        "\n",
        "5. Another task used for evaluation is the analogy task where the system has to solve problems of the form a is to b as a* is to b*.\n",
        "\n",
        "6. All embedding algorithms suffer from inherent variability:\n",
        "\n",
        "  (1): because of randomness in the initialization and the random negative sampling, algorithms like word2vec may produce different results even from the same dataset, and individual documents in a collection may strongly impact the resulting embeddings\n",
        "\n",
        "  (2): When embeddings are used to study word associations in particular corpora, therefore, it is best practice to train multiple embeddings with bootstrap sampling over documents and average the results.\n",
        "            \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" - N-gram way: **Goal**: Estimate the probability of getting a sentence $P(w_{1:n}) \\\\approx \\\\prod_{i=1}^{n}P(w_i|w_{i-k:i-1})$, where $P(w_{i+1}=m|w_{i-k:i})=\\\\frac{Count(w_{i-k:i+1})}{Count(w_{i-k:i})}$, or a smoothed version $P(w_{i+1}=m|w_{i-k:i})=\\\\frac{Count(w_{i-k:i+1})+\\\\alpha}{Count(w_{i-k:i})+\\\\alpha|V|}$\n",
        "\n",
        "- **Neural (Probabilistic) Language Model**: \n",
        "\n",
        "  - Key: represent each word using an **embedding** (usually **low dimensional, dense vector**). The network simultaneously learn embeddings and probability parameters. Let the dimension of embedding be $d_w$, then embedding each word is $v(w) \\\\in \\R^{d_w}$\n",
        "\n",
        "  - Input: **Concatenation** of the embedding of each word in the sequence $w_{1:k}$, $x=[v(w_1); v(w_2);...;v(w_k)]$\n",
        "  - Output: Probability distribution of $w_{k+1}$\n",
        "  - For each k-gram, using words i-k+1:i-1 to calculate input, word k as ground-truth\n",
        "  - Typically train using CE loss \n",
        "  - Advantages: Lower perplexity score, can use longer sequence, **generalize well to unseen contexts** (eg. in training set we only have \"a cute dog\", but in the test set we can get \"a cute cat\"). By-product: we can get a set of word embeddings. \n",
        "\n",
        "- **Vector semantics**\n",
        "  - Core question: How to represent the meaning of a word\n",
        "  - **meaning**: synonym (similar), antonym (opposite), connotation (positive or negative), semantic roles (buy, sell, pay are different parts of the same underlying *purchasing* event), support for entailment. \n",
        "  - Measure word **similarity**: If two words almost always occur in the same environments, they are similar words => useful in question answering task\n",
        "  - **vector space model**: Essentially clustering. Project word (document) into some high dimensional space. Whenever we have a query, project it into the same space and see what words (documents) are close to it.\n",
        "  - **term-document matrix**: Each row represent a term (word), each column represents a document. Entry value: How often does a term occur in a document. **Application of term-document matrix:** Compare two columns can detect plagiarism, Compare two rows implies synonym and antonyms. Can use **cosine distance** to measure similarity between two words $u$ and $v$: $L_{cos}(u,v)=1-\\\\frac{u·v}{|u|·|v|}$. \n",
        "  - **term-term matrix** (=term context matrix): $|V|\\\\times|V|$ matrix. Entry value represents how often a word appears in context window of the other word. **Context window** could be something as simple as *past 2 and coming 2 words surrounding one*, or more complicated dependency relationship like subject and verb. \n",
        "  - **TF-IDF**: term frequency in a document / #number of documents the word of interest occurs in. Simply relying on word count will skew model towards \"the\" \"of\", etc. TF-IDF solves the problem. TF-IDF is mainly used in **sparse vector**. \n",
        "  - **How to get dense vectors representing co-occurrences**: 1. Treat the target word and a neighboring context word as positive examples.  2. Randomly sample other words in the lexicon to get negative samples. 3. Use logistic regression to train a classifier to distinguish those two cases.  4. Use the weights as the embeddings. **Examples of dense vector**: Word2Vec\n",
        "\n",
        "- **Word2Vec**: Learn dense word embeddings simultaneously when learning to predict words. A classifier gets trained to predict neighboring words. We make positive samples (true positive word pairs) and negative samples (randomly generated) to train this classifier, encourage positive samples to have high similarity, and negative samples to have low similarity score in the projection space. **In a word, use running text as supervised training data**\n",
        "\n",
        "- **skip gram**: A method to train embeddings in Word2Vec. **How it works**: 1. Treat the target word and a neighboring context  word as positive examples. 2. Randomly sample other words in the lexicon to get  negative samples 3. Use logistic regression to train a classifier to  distinguish those two cases 4. Use the weights as the embeddings \n",
        "\n",
        "- **Evaluate word embeddings**: Compare to human scores on word similarity-type tasks. Examples: (1) **intrinsic**: A group of experts judge how similar each pair of words is. Compare the model score with expert judgement. (2) **Compute correlation**: Also rely on expert knowledge, but instead of directly giving score to each pair, ask question like \"(love, affair) ><= (professor tomato)?\"\n",
        "\n",
        "- **Vector arithmetic**: Based on learned embeddings, answer questions like \"man (a) is to king (a\\*) like women (b) is to ? (b\\*)\". b\\*= b\\*-b+a. Convert **relational meanings** to just vector arithmetic calculations. We can find $b^*$ by optimize: $argmax_{b^*\\in V}cos(b^*, a^*-a+b)=argmax_{b^* \\in V}cos(b^*-b,a^*-a)=argmax_{b^*\\in V}[cos(b^*,b)-cos(b^*,a)+cos(b^*,a^*)]$\n",
        "\n",
        "- **useful formula**: $1- \\\\sigma(z)=\\\\sigma(-z)$\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ae183055-c645-4fe3-849c-45b5c423bed6"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n \n**Goal:** Explore the two architectures primarily through the lens of probabilistic.\n\n**Language Model:** give us the ability to assign a conditional probability to every next word, giving a distribution over the entire vocabulary.\n\n**First equation:** $P(w_{1:n})= \\prod_{i=1}^{n}P(w_i|w_{<i})$: provides a clear training objective based on the model for next word in a sequence.\n\n**Two methods to instantiate probabilistic language model:** N-gram models, feedforward neural networks with sliding windows, but are constrained by Markov assumption: \n$P(w_{n}|w_{1:n-1})≈P(w_{n}|w_{(n-N+1):(n-1)})$, which has a fixed preceding context of size N: any input that occured earlier than that has no bearing on the outcome.\n            \n**Evaluation:** examine how well the  language model predict unseen data. Good models assign higher probabilities to unseen data. We use **preplexity(PP)** as a measure \nof model $θ$ quality.\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n  \n**Definition for RNN:** any network that contains a cycle within its network connections, which is any network where the value of a unit is dependent on its earlier outputs as an input.\n\n**RNN process:** an input vector represesnt the current input. Then multiply a weight matrix and pass through a non-linear activation function to compute the values \nfor a layer of hidden units which is used to calculate the corresponding output.\n\n**Difference between Feedforward network and RNN:** RNN augments the input to the compuation at the hidden layer with the value of the hidden layer from the preceding point in time.\n  \n             \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n \n**Lexical Semantics:** draw on results in the linguistic study of meaning.\n\n**Lemmas:** citation form (verb), the specific forms are called wordforms. The lemmas can be polysemous.\n\n**Synonymy:** when one word has a sense whose meaning is identical to a sense of another word, or nearly identical, we say the two senses of those two words are synonyms.\n\n**Propositional meaning:** two words are synonymous if they are substitutable for one another in any sentence without changing \n            the truth conditions of the sentence, the situations in which the sentence would be true.\n\n**Principle of Contrast:** states that a difference in linguistic form is always associated with some difference in meaning.\n\n**Word similarity:** While words don’t have many synonyms, most words do have lots of similar words.\n\n**Word relatedness:** The meaning of two words can be related in ways.\n             \n\n## SLP Chapter 6.2 Vector Semantics\n \n**Vector Semantics:** standard way to represent word meaning in NLP.\n\n**Embeddings:** vectors for representing words.\n\n**tf-idf model:** an important baseline, the meaning of a word is defined by a simple function of the counts of nearby words. \n            We will see that this method results in very long vectors that are sparse.\n\n**word2vec model:** construct short, dense vectors that have useful semantic properties\n            \n**cosine:** the standard way to use embeddings to compute semantic similarity, between two words, two sentences, or two documents, \n            an important tool in practical applications\n\n## SLP Chapter 6.3 Words and Vectors\n \nVector or distributional models of meaning are generally based on a **co-occurrence matrix**, a way of representing how often words co-occur.\n\n**term-document matrix:** each row represents a word in the vocabulary and each column represents a document from some collection of documents.\nWords in each document(row vector), document of each words(column vector).\n\n**Term-document matrices** were originally defined as a means of finding similar documents for the task of document information retrieval.Information retrieval \nis the task of finding the document d from the D documents in some collection that best matches a query q.\n            \n**term-term matrix(word-word matrix or term-context matrix):** columns are labeled by words rather than documents. dimensionality: |V|*|V|\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n \n**Cosine for measuring similarity:** Use dot product(inner product) which has high values in same dimensions, zero in orthogonal vectors.\n**Problem:** it favors long vectors and we’d like a similarity metric that tells us how similar two words are regardless of their frequency and length. So, we use normalized dot product.\nFor unit vectors, the dot product is the same as the cosine, $cos(v, w) =$ $vw\\over |v||w|$.\n\n\n## SLP Chapter 6.8 Word2vec\n \n**Word2vec:** short dense vectors embeddings are short with the number of dimensions d ranging from 50-1000. The values will be real-valued numbers that can be negative, \nwhich makes the dense vector works better in NLP. The lower dimensionality makes the classifier learn faster. The dense vector is also good at capturing synoymy.\n\n**The advantages of word2vec:** fast and efficient to train and easily avaiable online with code and pretrained embeddings. Static embedding(learn one fixed embedding for each word in the vocabulary).\n\n**self-supervision:** obtains supervisory signals from the data itself\n\n**why word2vec is simpler than neural network language model:** word2vec simplifies the task(makes it binary classification instead of word prediction) **and**\nword2vec simplifies the architecture(training a logistic regression classifier instead of a multi-layer neural network with hidden layers that demand more sophisticated training algorithms).\n\n**process of slip-gram:** (1)given a tuple $(w,c)$ of a target word $w$ paired with a candidate context word $c$, return the probability that $c$ is context word: $P(+|w,c)$\n(2)the probablity that the word is not a real context for $w$, just 1 minus the real $c$ probability: $P(-|w,c) = 1 - P(+|w,c)$ (3)base the proability on embedding similarity: \ntwo vectors are similar if they have a high dot product, Similarity(w,c) ≈ c*w (4)Since dot product can be negative while probability cannot be negative, use logistic or \nsigmoid function (5)Model the probability that the word $c$ is a real context word for target word $w$: $P(+|w,c) =$ $\\sigma(c*w)=$ $1\\over 1+exp^{-c*w}$\n(6)As $c$ is not a real context word for $w$: $P(-|w,c) = 1 - P(+|w,c)$\n(7)As many context words in the window and Skip-gram makes the simplying assumption that all context words are independent\n\n**Learning skip-gram embeddings:** skip-gram with negative sampling(SGNS) uses more negative examples than positive examples with a ratio $k$ between them, for each $(w, c_{positive})$, \ncreate $k$ negative samples, each consisting of the target $w$ plus a \"noise word(a random word from the lexicon, constrained not to be the target word w)\" $c_negative$.\nThe noise words are chosen according to their weighted unigram frequency $P_{α}(w)$, where $α$ is a weight.\n            \n**The learning algorithm:** adjust those embeddings to (1)Maximize the similarity of the target word, context word pairs (w; c_{pos}) drawn from the positive examples\n(2)Minimize the similarity of the (w;c_neg) pairs from the negative examples. By minimizing the loss function $L_{CE} = -log[P(+|w,c_{pos})$ $\\prod_{i=1}^k$ $P(-|w,c_{neg_{i}})] = -[log \\sigma(c_{pos}w) + $\n $\\sum_{i=1}^k$ $log \\sigma(-c_{neg_{i}}w)]$\n            \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \n**Semantic properties of embeddings:** 1. Different types of similarity or association: (1)Shorter context windows tend to lead to representations that are a bit more syntactic, \nsince the information comes from immediately nearby words. (2)When the vectors are computed from short context windows, the most similar words to a target word w tend to be semantically similar words \nwith the same parts of speech. (3)When vectors are computed from long context windows, the highest cosine words to a target word w tend to be words that are topically related \nbut not similar. (4)first-order co-occurrence(syntagmatic association): if they are typically nearby each other, second-order co-occurrence(paradigmatic association): if they have similar neighbors. 2. Analogy/Relational Similarity: (1)parallelogram model: solving simple analogy problems of the form $a$ is to $b$ as $a*$ is to what? (2)Equation: $\\hat{b}^* = argmax_x distance(x, a^*-a+b)$\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n \n1. allocational harm: a system alloharm cates resources (jobs or credit) unfairly to different groups\n\n2. Embeddins reflect the statistics of their input and amplify bias.\n\n3. gendered terms become more gendered in embedding space than they were in the input text statistics\n\n4. Embeddings encodes the implicit associations that are a property of human reasoning.\n\n5. reprerepresentational harm: a harm caused by a system demeaning or even ignoring some social groups\n\n6. debiasing: reduce bias in embeddings not eliminate it\n  (1): developing a transformation of the embedding space that removes gender stereotypes but preserves definitional gender\n  (2): changing the training procedure\n             \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \n**how to Evaluating Vector Models:**\n\n1. Evaluation metric for vector model: extrinsic evaluation on tasks using vectors in an NLP task and seeing whether this improves performance over some other model\n\n2. Intrinsic evalution matric is to test their performance on similarity: computing the correlation between an algorithm’s word similarity scores and word similarity ratings assigned by humans.\n\n3. Dataset: \n\n  (1): WordSim-353: a commonly used set of ratings from 0 to 10 for 353 noun pairs\n\n  (2): SimLex-999: is a more difficult dataset that quantifies similarity (cup, mug) rather than relatedness (cup, coffee), and including both concrete and abstract adjective, noun and verb pairs\n\n  (3): TOEFL: a set of 80 questions,  each consisting of a target word with 4 additional word choices; the task is to choose which is the correct synonym\n\n4. Slightly more realistic are intrinsic similarity tasks that include context\n\n5. Another task used for evaluation is the analogy task where the system has to solve problems of the form a is to b as a* is to b*.\n\n6. All embedding algorithms suffer from inherent variability:\n\n  (1): because of randomness in the initialization and the random negative sampling, algorithms like word2vec may produce different results even from the same dataset, and individual documents in a collection may strongly impact the resulting embeddings\n\n  (2): When embeddings are used to study word associations in particular corpora, therefore, it is best practice to train multiple embeddings with bootstrap sampling over documents and average the results.\n            \n\n## Module 14 Lecture Notes\n - N-gram way: **Goal**: Estimate the probability of getting a sentence $P(w_{1:n}) \\approx \\prod_{i=1}^{n}P(w_i|w_{i-k:i-1})$, where $P(w_{i+1}=m|w_{i-k:i})=\\frac{Count(w_{i-k:i+1})}{Count(w_{i-k:i})}$, or a smoothed version $P(w_{i+1}=m|w_{i-k:i})=\\frac{Count(w_{i-k:i+1})+\\alpha}{Count(w_{i-k:i})+\\alpha|V|}$\n\n- **Neural (Probabilistic) Language Model**: \n\n  - Key: represent each word using an **embedding** (usually **low dimensional, dense vector**). The network simultaneously learn embeddings and probability parameters. Let the dimension of embedding be $d_w$, then embedding each word is $v(w) \\in \\R^{d_w}$\n\n  - Input: **Concatenation** of the embedding of each word in the sequence $w_{1:k}$, $x=[v(w_1); v(w_2);...;v(w_k)]$\n  - Output: Probability distribution of $w_{k+1}$\n  - For each k-gram, using words i-k+1:i-1 to calculate input, word k as ground-truth\n  - Typically train using CE loss \n  - Advantages: Lower perplexity score, can use longer sequence, **generalize well to unseen contexts** (eg. in training set we only have \"a cute dog\", but in the test set we can get \"a cute cat\"). By-product: we can get a set of word embeddings. \n\n- **Vector semantics**\n  - Core question: How to represent the meaning of a word\n  - **meaning**: synonym (similar), antonym (opposite), connotation (positive or negative), semantic roles (buy, sell, pay are different parts of the same underlying *purchasing* event), support for entailment. \n  - Measure word **similarity**: If two words almost always occur in the same environments, they are similar words => useful in question answering task\n  - **vector space model**: Essentially clustering. Project word (document) into some high dimensional space. Whenever we have a query, project it into the same space and see what words (documents) are close to it.\n  - **term-document matrix**: Each row represent a term (word), each column represents a document. Entry value: How often does a term occur in a document. **Application of term-document matrix:** Compare two columns can detect plagiarism, Compare two rows implies synonym and antonyms. Can use **cosine distance** to measure similarity between two words $u$ and $v$: $L_{cos}(u,v)=1-\\frac{u·v}{|u|·|v|}$. \n  - **term-term matrix** (=term context matrix): $|V|\\times|V|$ matrix. Entry value represents how often a word appears in context window of the other word. **Context window** could be something as simple as *past 2 and coming 2 words surrounding one*, or more complicated dependency relationship like subject and verb. \n  - **TF-IDF**: term frequency in a document / #number of documents the word of interest occurs in. Simply relying on word count will skew model towards \"the\" \"of\", etc. TF-IDF solves the problem. TF-IDF is mainly used in **sparse vector**. \n  - **How to get dense vectors representing co-occurrences**: 1. Treat the target word and a neighboring context word as positive examples.  2. Randomly sample other words in the lexicon to get negative samples. 3. Use logistic regression to train a classifier to distinguish those two cases.  4. Use the weights as the embeddings. **Examples of dense vector**: Word2Vec\n\n- **Word2Vec**: Learn dense word embeddings simultaneously when learning to predict words. A classifier gets trained to predict neighboring words. We make positive samples (true positive word pairs) and negative samples (randomly generated) to train this classifier, encourage positive samples to have high similarity, and negative samples to have low similarity score in the projection space. **In a word, use running text as supervised training data**\n\n- **skip gram**: A method to train embeddings in Word2Vec. **How it works**: 1. Treat the target word and a neighboring context  word as positive examples. 2. Randomly sample other words in the lexicon to get  negative samples 3. Use logistic regression to train a classifier to  distinguish those two cases 4. Use the weights as the embeddings \n\n- **Evaluate word embeddings**: Compare to human scores on word similarity-type tasks. Examples: (1) **intrinsic**: A group of experts judge how similar each pair of words is. Compare the model score with expert judgement. (2) **Compute correlation**: Also rely on expert knowledge, but instead of directly giving score to each pair, ask question like \"(love, affair) ><= (professor tomato)?\"\n\n- **Vector arithmetic**: Based on learned embeddings, answer questions like \"man (a) is to king (a\\*) like women (b) is to ? (b\\*)\". b\\*= b\\*-b+a. Convert **relational meanings** to just vector arithmetic calculations. We can find $b^*$ by optimize: $argmax_{b^*\\in V}cos(b^*, a^*-a+b)=argmax_{b^* \\in V}cos(b^*-b,a^*-a)=argmax_{b^*\\in V}[cos(b^*,b)-cos(b^*,a)+cos(b^*,a^*)]$\n\n- **useful formula**: $1- \\sigma(z)=\\sigma(-z)$\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "949207da-520e-4ebf-c63c-2942ab4c8f2b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n - sample question: $P(\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$\n\n-  **Expected utility (EU)**: $EU(a)=\\sum_{s'}P(RESULT(a)=s')U(s')$\n\n- **MEU**: a rational agent should choose the action which maximizes its EU: *action=$argmax_a EU(a)$*\n- Relationship between **utility function** and **performance measure**: Utility function reflects like how people value a particular state, it is internal. Performance measure gives a score for a history of states, while utility function can be used to guide agent's action for next step. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n - Lottery: $L=[p_1,S_1;...,p_n,S_n]$\n\n- **6 preference constraints** (axioms of utility theory): \n  - Orderability: Either $A \\succ B$ or $B \\succ A$ or $A \\sim B$ holds \n  - Transitivity: $A \\succ B and B \\succ C \\Rightarrow A \\succ C$. \n  - Continuity: $A\\succ B \\succ C \\Rightarrow \\exists p,[p,A;1-p,C]\\sim B$ \n  - Substitutability: $A\\sim B\\Rightarrow [p,A;1-p,C]\\sim [p,B;1-p,C]$\n  - Monotonicity: $A\\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B]\\succ [q,A;1-q,B])$\n  - Decomposability: $[p,A;1-p,[q,B; 1-q,C]]\\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n\n-  **Existence of utility function**: If an agent's preferences obey the above 6 axioms, then there exists a utility function U such that **U(A)>U(B)** if and only if A is preferred to B, and **U(A)=U(B)** if and only if agent is indifferent between A and B.\n\n- **Expected utility of lottery**: $U([p_1,S_1;...;p_n,S_n])=\\sum_{i} p_iU(S_i)$\n\n- The axioms of utility theory only guarantees that under some conditions, a utility function exists, but it is **NOT NECESSARILY UNIQUE**. $U'(s)=aU(s)+b$, **affine transformation** does not change agent policy (a>0).\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n - **preference elicitation**: present choices to human, based on observed preferences, pin down the utility function. \n\n- Best outcome: $U(S)=u_{\\top}$, worst outcome: $U(s)=u_{\\bot}$. Normalized utility: $u_{\\top}=1,u_{\\bot}=0$\n\n- **Standard lottery**: $[p,u_{\\top};1-p,u_{\\bot}]$. We can let one choose between standard lottery and S, adjust $p$ until one becomes indifferent. Then we get his utility: $U(S)=p$\n\n- **micromort**: one in a million chance of death\n\n- **EMV**: expected monetary value, which is the weighted summation of each possible monetary value. **Should NOT assume it is equal to Expected Utility**. For money, utility function is not linear in EMV. But if you have a lot of money, you will have a linear utility function in money over some range. \n\n- Utility function in money curve: Concave for positive money, convex for negative money (debt) \n\n- In the positive region, people tend to be **risk-averse**, they prefer a sure thing with a payoff less than the EMV of a lottery. That is, $U(L)<U(S_{EMV(L)})$. Conversely, in negative region, agent tends to be **risk-seeking** \n\n- **certainty equivalent**: The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. For example, say a lottery of earning 1000 with p=1/2, while 0 also with p=1/2. If an agent will be satisfied with 400 FOR SURE (or larger), then his certainty equivalent would be 400. \n\n- **insurance premium=EMV(L)-certainty equivalent of L**\n\n- If the true EU is unattainable for some reason, we may calculate an estimator of it: $\\hat{EU}(a)$. An **unbiased estimator**: $E[\\hat{EU(a)}-EU(a)]=0$\n\n- **Optimizer's cursor**: Even if we have an unbiased estimator of EU, we may still be overly optimistic and get bad results.  Because we select the action with the highest utility estimate, we are favoring the overly optimistic estimates, and that is the source of the bias. Such effect will be accumulated as sample size goes up.  \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n- Sequential Decision Problems: a sequential decision problem for a fully observable, stochastic environment with a Markovian transition model and additive rewards is called a Markov decision process, or MDP\n\n- **Markovian transition model**: $P(s'|s,a)$, **Reward**: $R(s,a,s')$\n\n- **optimal policy**: a policy that yields highest expected utility\n\n- **stationary vs non-stationary policy**: With a finite horizon, an optimal action in a given state may depend on how much time is left. A policy that depends on the time is called nonstationary. If the game is infinite, the optimal policy does not depend on time, it is stationary. \n\n- **additive discounted rewards**: $U([s_0,a_0,s_1,a_1,...])=R(s_0,a_0,s_1)+\\gamma R(s_1,a_1,s_2)+\\gamma ^2R(s_2,a_2,s3)+...$\n\n- A policy that is guaranteed to reach a terminal state is called a **proper policy**. \n\n- **How to evaluate policy**: calculate expected utility based on history: $U^{\\pi}(s)=E[\\sum_{t=0}^{\\infty}\\gamma ^{t}R(S_t,\\pi(S_t),S_{t+1})]$. The expectation is with respect to the probability distribution over state sequences. **Optimal policy**: $\\pi^*_s=argmax_{\\pi}U^{\\pi}(s)$, where s is the starting state. If the game is stationary, optimal policy DOES NOT depend on starting state and will be always optimal. \n\n- **Bellman Equation**: the utility of a state is the expected reward for the next transition plus the discounted utility of the next state, assuming that the agent chooses the optimal action thereafter. $U(s)=max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$. We can derive optimal policy from Bellman Equation: $\\pi^*(s)=argmax_a  \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n\n- **action-utility function Q(s, a)**: expected utility of taking an action in a state. $Q(s,a)=\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]=\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma max_{a'}Q(s',a')]$. **Relationship** to U: $U(s)=max_a Q(s,a)$\n\n- **Extract optimal policy from Q value**: $\\pi^*(s)=argmax_aQ(s,a)$\n\n- Affine transformation $R'(s,a,s')=mR(s,a,s')+b$ does **NOT** change optimal policy. \n\n- **Shaping theorem**: Let $\\Phi(s)$ be any function of state s. The following transformation leaves optimal policy unchanged: $R'(s,a,s')=R(s,a,s')+\\gamma \\Phi(s')-\\Phi(s)$. $\\Phi(s)$ is called a potential function.  \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n - **Value iteration**: Perform Bellman update: $U_{i+1}(s)=max_{a\\in A(s)}\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')]=max_{a\\in A(s)}Q(s,a)$. In each round, we perform Bellman update for all states, until the utility values converge. Notice: we need to update all utility values **simultaneously** using old values. Value iteration will converge to **unique set of solutions** to the Bellman equations, and the policy extracted from it is optimal.\n\n- **Contraction**: a function that (a) has one and only one fixed point; (b) Applying it to any input will move the input closer to fixed point. In the limit sense, any input will reach fixed point through repeatedly apply this function. \n\n- The Bellman update is a contraction by a factor of $\\gamma$ on the space of utility vectors So, value iteration will converge exponentially, i.e. it reaches optimal point in logarithmic steps w.r.t $\\gamma$ and $R_{max}$\n\n- **policy loss**: Suppose after i iterations of value iteration we get estimated utility $U_i(s)$ of the true utility $U(s)$. We can obtain the MEU policy $\\pi_i$ using one-step look-ahead, then the policy loss is: $||U^{\\pi_i}-U||$, where $U^{\\pi_i}$ means the utility we will obtain executing $\\pi_i$ starting from state s.\n\n- **policy iteration**: starting with some policy $\\pi_0$, alternate between the 2 steps: \n  - **policy evaluation**: Fix policy $\\pi_i$, calculate $U_i(s)=U^{\\pi_i}(s)=\\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$, the utility of each state if policy $\\pi$ were to be executed. We have n equations and n unknowns, which could be solved in O(n^3) time using a linear solver.\n  - **policy improvement**: Calculate a new MEU policy $\\pi_{i+1}$ using one-step look-ahead based on $U_i(s)$. $a^*(s)=argmax_a Q(s,a)$\n  - until policy improvement causes no change in utilities\n  - **Modified policy iteration**: during the evaluation phase, instead of directly solving the equations, perform several *value iteration* steps, to find the utility values. $U_{i+1}(s)\\leftarrow \\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$\n\n- **Linear Programming**: solve the following optimization problem: minimize all utilities, $U(s)$, for any s, constrained by $U(s)\\geq \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$\n\n \n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n - define **bandits problem**: Each arm $M_i$ is a **Markov reward process** or **MRP**, that is, an MDP with only one possible action $a_i$. It has states $S_i$, transition model $P_i(s'|s,a_i)$, and reward $R_i(s,a_i,s')$. The arm defines a distribution over sequences of rewards $R_{i,0},R_{i,1},R_{i,2}...$, where each $R_{i,t}$ is a random variable. The overall bandit problem is an **MDP**: the state space is given by the Cartesian product  $S=S_1\times S_2\times ... \times S_n$; the actions are $a_1,a_2,...,a_n$; the transition model updates the state of whichever arm is selected, according to its specific transition model, leaving the other arms unchanged; and the discount factor is $\\gamma$. Note that the arms are **independent**. \n\n- **One-armed bandits**: There is only one arm to pull. If there are two arms, $M$ and $M_{\\lambda}$, $M$ has reward sequence $R_0,R_1,R_2...$ while $M_{\\lambda}$ has a constant (known) reward $\\lambda$, this could also be regarded as a one-armed bandits. The opportunity cost of not pulling in each step is $\\lambda$ \n\n- Optimal policy for one-armed bandits: pull $M$ for $t=0,1,...,T-1$, and always pull $M_{\\lambda}$ starting from $T$. $T$ is called the stopping time. Special case: $T$ could be 0 (immediately pull $M_{\\lambda}$ from the beginning), $\\infty$ (never pull $M_{\\lambda}$) or some value in between. \n\n- **Gittins index**: $\\lambda = max_{T>0} \frac{E(\\sum_{t=0}^{T-1}\\gamma^tR_t)}{\\sum_{t=0}^{T-1}\\gamma^t}$, describes the maximum obtainable utility per unit of discounted time. This provides an optimal policy for any bandits problem: pull the arm that has the highest Gittins index, and update the Gittins index. \n\n## AIMA Chapter 22.1 Learning from Rewards\n **Classify RL algorithms**:\n\n- model-based: the agent uses a transition model of the environment to help interpret the reward signals and make decisions. The transition model could be known, or unknown initially and learned through interaction. \n- model-free: the agent does not keep a transition model. It learns a direct representation how to behave, in two variants: (a) action-utility function: eg **Q-learning**. (b) policy search: eg a reflex agent\n- passive RL: given a fixed policy, the agent learns $U(s),Q(s,a)$ and/or the transition model\n- active RL: the agent needs to figure out a policy by itself at the same time.  \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n - passive RL: the agent just follows a given policy $\\pi$ and learns $U^{\\pi}(s)$, similar to policy evaluation except that it does not know transition model nor the reward. \n\n- Learn expected utility: $U^{\\pi}(s)=E[\\sum_{t=0}^{\\infty}\\gamma ^tR(S_t,\\pi(S_t),S_{t+1})]=\\sum_{s'}P(s'|s,a)[R(s,\\pi(s),s')+\\gamma U^{\\pi}(s')]$ (*)\n\n- **direct utility estimation**: take average of **direct rewards** from multiple trials and use it as the utility value of states \n\n- **adaptive dynamic programming (ADP)**: The agent will estimate the model $P(s'|s,a)$ by counting $N_{s'|s,a}$, # times agent goes to s' by action a in state s, and estimate $U(s)$ by using similar procedure in policy evaluation, solve linear equations (*) (using  dynamic programming and plugging the rewards received)\n\n- **temporal difference learning (TD)**: update equation $U^{\\pi}(s)=U^{\\pi}(s)+\u0007lpha [R(s,\\pi(s),s')+\\gamma U^{\\pi}(s')-U^{\\pi}(s)]$, based on observed transition (s,a,s'). **It does not need a transition model to perform update**. In the limit, it will converge to the correct utility values for all states. We can design learning rate $\u0007lpha$ as a decreasing function of #visitations of states. As a particular state is visited for more and more times, we reduce the scale of TD update to stabilize. \n\n- Relationship between ADP and TD: (a) They both do local update, to make utility estimates agree with its successors; (b) TD adjust a state to agree with its *observed* successor, while ADP adjust a state to reflect all its possible successors, weighted by corresponding probability. \n\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n - **greedy agent**: take actions based on what it currently believes to be best. The policy it learned is not necessarily the true model in true environment, therefore its policy might be sub-optimal. \n\n- **GLIE**: greedy in the limit of infinite exploration. By introducing in **exploration**, the agent must try each action in each state for some times in case it misses an optimal action. \n\n- **exploration function**: Let $U^{+}(s)$ be some optimistic estimate of utility, $N(s,a)$ be the number of times seen (s, a). Then the update using exploration function *f* is: $U^{+}(s)\\leftarrow max_af(\\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U^{+}(s')],N(s,a))$. *f* determines how greedy the agent (exploration-exploitation tradeoff), it is increasing in *u* and decreasing in *N*. \n\n- absorbing state: a state in which no action can be taken and no rewards get received. Just a dead end. \n\n- **safe exploration**: We need to guarantee that the agent's exploration will not lead to catastrophic result. In other words, we need to choose a policy that works reasonably well for the whole range of models that have a reasonable chance of being the true model, even if the policy happens to be suboptimal for the maximum-likelihood model.  Popular ways: \n  - Bayesian reinforcement learning\n  - robust control theory\n\n- **Temporal Difference Q-learning**: model-free approach combining Q learning and TD update. \n  - **Q-learning Bellman equation:** $Q(s,a)=\\sum_{s'}P(s'|s,a)[R(s,a,s')+max_{a'} Q(s',a')]$\n  - Q-learning TD update: $Q(s,a)\\leftarrow Q(s,a)+\u0007lpha[R(s,a,s')+\\gamma max_{a'} Q(s',a')-Q(s,a)]$. This is executed whenever an action a is executed in state s leading to state s'. \n  - This approach does need a transition model. \n\n- **Q-learning** is off-policy, because it performs q-value update based on the best case (max operator over $Q(s',a')$)  \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n - **function approximate**: Learning all expected utilities might not be efficient in real problem, as the size of state space and action space goes up. So, we need to use some function to approximate the utilities and Q values: $\\hat{U}_{\theta}(s)=\theta_1 f_1(s)+\theta_2 f_2(s)+...+\theta_n f_n(s)$\n\n- **Adv of approximate RL**: can learn based on limited training sets and a small set of states, and **generalize** to other states. \n\n- Update step in TD learning and Q learning: For TD, it is: $\theta_i \\leftarrow \theta_i + \u0007lpha [R(s,a,s')+\\gamma \\hat{U}_{\theta}(s')-\\hat{U}_{\theta}(s)]\frac{\\partial \\hat{U}_{\theta}(s)}{\\partial \theta_i}$. For Q-learning, it becomes: $\theta_i \\leftarrow \theta_i+\u0007lpha [R(s,a,s')+\\gamma max_{a'}\\hat{Q}_{\theta}(s',a')-\\hat{Q}_{\theta}(s,a)]\frac{\\partial \\hat{Q}_{\theta}(s,a)}{\\partial \theta_i}$ \n\n## Module 9 Lecture Notes\n **Regret** is a measure of your total \nmistake cost: the difference between \nyour (expected) rewards, including \nyouthful suboptimality, and optimal \n(expected) rewards\nMinimizing regret goes beyond \nlearning to be optimal – it requires \noptimally learning to be optimal \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n - decision theory = probability theory + utility theory (what agent prefers and how likely to achieve that)\n\n- **MEU** (maximum expected utility): The fundamental idea of decision theory is that an agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n - Notation: Sample space $\\Omega$, an element in it $\\omega$. \n\n- **inclusion-exclusion principle**: $P(a \\or b)=P(a)+P(b)-P(a \\and b)$\n\n- Kolmogorov’s axioms\n  - $0\\leq P(\\omega) \\leq 1 $ and $\\sum_{\\omega}P(\\omega)=1$\n  - inclusion-exclusion principle \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n - **conditioning rule**: $P(Y)=\\sum_{Z}P(Y|Z)P(Z)$\n\n- Calculate conditional probability when some marginal probability is unavailable: Let $X$ be the variable we are interested in, $E$ is observed evidence, $Y$ be all the other unobserved vars, then $P(X|e)= \\alpha P(X, e)= \\alpha \\sum_y P(X,e,y)$. The key thing is to calculate the **relative proportion** of $X$ given $E=e$ and then normalize the proportions.   \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n - **Bayes Rule**: $P(Y|X)=\\frac{P(X|Y)P(Y)}{P(X)}$ \n\n- **conditionalized version**: $P(Y|X,e)=\\frac{P(X|Y,e)P(Y|e)}{P(X|e)}$\n\n- Application: $P(cause|effect)=\\frac{P(effect|cause)P(cause)}{P(effect)}$. **Causal: ** $P(effect|cause)$, **Diagnostic**: $P(cause|effect)$\n\n- Avoid calculate $P(effect)$: $P(cause|effect)=\\alpha P(effect|cause)P(cause)$, where $\\alpha$ is a normalization factor. Do this for every possible cause, and normalize. Essential reason: $P(effect)$ is just a constant\n\n- **conditional independence**: $P(X,Y|Z)=P(X|Z)P(Y|Z)$ or $P(X|Y,Z)=P(X|Z)$, or $P(Y|X,Z)=P(Y|Z)$\n\n- Let the effect be described by a series of variables: $P(X_1,X_2,...,X_n|Cause)$, by assuming conditional independence, it becomes: $P(X_1|Cause)P(X_2|Cause)...P(X_n|Cause)$. Reduce running time from **exponential** to **linear**, thus allows the equation to **scale up well**. \n\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n - **Naive Bayes**: $P(Cause, Effect_1,Effect_2,...,Effect_n)=P(Cause)\\prod_i P(Effect_i|Cause)$\n\n- Let $E$ be observed effect, $Y$ be all the other unobserved effect. Then Naive Bayes equation: $P(Cause|e)=\\alpha \\sum_y P(Cause,e,y)=\\alpha \\sum_y P(Cause)P(y|Cause)\\prod_j P(e_j|Cause)=\\alpha P(Cause)\\prod_j P(e_j|Cause) $ \n\n- The Naive Bayes approach scales well, and does not depend on unobserved effects.  \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n - Use chain rule to compute joint probability: $P(w_{1:n})=P(w_1)P(w_2|w_1)P(w_3|w_{1:2})...P(w_n|w_{1:n-1})=\\prod_{i=1}^{n}P(w_i|w_{1:i-1})$\n\n- N-gram model: For example for bigram, use $P(w_i|w_{i-1})$ to approximate $P(w_i|w_{1:i-1})$. For general N, $P(w_i|w_{1:i-1})\\approx P(w_i|w_{i-N+1:i})$ ->**Markovian assumption**\n\n- **MLE for N-gram probabilities**: Use **relative frequency**, which is counts from some dataset and normalize. For instance, for bigram, $P(w_n|w_{n-1})=\\frac{C(w_nw_{n-1})}{C(w_{n-1})}$. For general case, $P(w_n|w_{n-N+1:n-1})=\\frac{C(w_{n-N+1:n-1}w_n)}{C(w_{n-N+1:n-1})}$ \n\n## SLP Chapter 3.2 Evaluating Language Models\n - train set: train model; test set (held-out set): test model on unseen data. We evaluate model by checking its probability of generating the test data. \n\n- development set (devset): Initial test set used for tuning parameters. The aim is to leave some fresh test set to see the true performance of model. \n\n- **perplexity**: The perplexity (sometimes called *PP* for short) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. For test set $W=w_1 w_2...w_n$, $PP(W)=P(w_1 w_2...w_n)^{-\\frac{1}{N}}=\\sqrt[N]{\\frac{1}{P(w_1 w_2 ... w_N)}}=\\sqrt[N]{\\prod_{i=1}^{N}\\frac{1}{P(w_i|w_1...w_{i-1})}}$. Minimize perplexity = maximize the test set probability given the model\n\n- perplexity = weighted average branching factor  \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n - **Smoothing (or discounting) **: Sometimes a word may appear in a different context in test set as that in the training set. (Note that this word is **not unknown**, just the context is different). To avoid a zero probability, we need smoothing. \n\n- Original unigram model: $P(w_i)=\\frac{c_i}{N}$, **Laplacian smoothing**: $P_{Lap}(w_i)=\\frac{c_i+1}{N+V}$, where $V$ is the size of vocabulary (all distinct words from set). **adjusted count**: $c^*_i=(c_i+1)\\frac{N}{N+V}$. We can normalize $c^*_i$ using N to get proper probability distribution. **relative discount**: $d_c=\\frac{c^*}{c}$\n\n- Bigram case: originally it is $P(w_n|w_{n-1})=\\frac{C(w_{n-1}w_n)}{C(w_{n-1})}$, **Laplacian smoothed**: $P(w_{n}|w_{n-1})=\\frac{C(w_{n-1}w_n)+1}{\\sum_w (C(w_{n-1}w)+1)}=\\frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V}$, $c^*(w_{n-1}w_n)=\\frac{[C(w_{n-1}w_n)+1]\\times C(w_{n-1})}{C(w_{n-1})+V}$\n\n- Problem with Laplacian smoothing: shift too much probability mass from seen to unseen events\n\n- Generalization: **add-k smoothing**: $P^*(w_n|w_{n-1})=\\frac{C(w_{n-1}w_n)+k}{C(w_{n-1})+kV}$, where k is a float in (0, 1) \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n - **Bayesian network**: Basically a directed acyclic graph (DAG). The topology structure specifies the independence and dependence relationships\n\n- CPT stands for conditional probability table (only for *discreate variables*)\n\n- How to get joint probability from Bayes Net: $P(x_1, x_2, ..., x_n)= \\prod_{i=1}^{n}P(x_i|parents(x_i))$\n\n- **How to build a Bayes Net**: Based on **Chain rule**, $P(x_1, x_2,...,x_n)= P(x_n|x_{n-1}, ..., x_1)P(x_{n-1}|x_{n-2},...,x_1)...P(x_2|x_1)P(x_1)= \\prod_{i=1}^{n}P(x_i|x_{i-1}...x_1)$, where $P(X_i|X_{i-1},...,X_1)=P(X_i|parents(X_i))$. Links between nodes should represent **direct influence**. \n\n- Bayesian Nets is usually more efficient than joint probability to represent the domain, because it is **local structured**, i.e. each variable depends only on a limited amount of other variables, no matter how large the total #variables is. This reduces computational cost to **linear**. \n\n- The **order** of adding variables to the Bayesian nets matters a lot. It is better to follow **causal order**, which leads to fewer \n\n- links, easier computation or probs, so on. Conversely, **diagnostic order** gives more awkward structure. \n\n- **Conditional independence in Bayesian nets**: \n  - Each variable is conditionally independent of its non-descendants, given its parents. \n  - Each variable is conditionally independent of all other variables in the network, given its parents, children, and parents of its children - that is, given its **Markovian blanket** \n\n- General case: Whether a set of nodes X is conditionally independent of another set Y, given a third set Z. \n  - Consider the **ancestral subgraph**, which consists X, Y, Z and their ancestors\n  - Add links between any unlinked pairs of nodes that share a common child, to get a **moral graph**\n  - Replace all directed links with undirected links\n  - If Z blocks all links between X and Y in the resulting graph, then Z d-separates X and Y. In that case, X is conditionally independent of Y, given Z. Otherwise, X and Y are not necessarily conditionally independent. \n\n- Handle continuous variables: (a) Discretization; (b) Define variable using some common distribution, like Gaussian; (c) nonparametric representation, to define the conditional distribution implicitly with a collection of instances\n\n- **hybrid bayesian network**: A BN with both discrete and continuous variables\n\n- Time complexity: Suppose n boolean variables, using joint probability, time complexity: $O(2^n)$. Using BN, suppose each node has up to k parents, it is reduced to $O(n2^k)$ \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n**multinomial naive Bayes classifier:** an unordered set of words with their position, keeping only their frequency in the document. A probabilistic classifier, \nmeaning that for a document d, out of all classes $c \\in C$ the classifier returns the class $\\hat{c}$ which has the maximum posterior probability given the document $\\hat{c}=argmaxP(c|d)$\n\n**Bayesian inference:** $P(x|y)$=$P(y|x)P(x)\\over P(y)$, $\\hat{c}=argmaxP(c|d)=argmax$ $P(d|c)P(c)\\over P(d)$\n\n**prior probability likelihood:** $\\hat{c}=argmax\\overbrace{P(d|c)}^{likelihood}\\overbrace{P(c)}^{prior}$, we represent a document $d$ as a set of features $f_1,f_2,...,f_n$: \n$\\hat{c}=argmax\\overbrace{f_1,f_2,...,f_n|c)}^{likelihood}\\overbrace{P(c)}^{prior}$\n\n**naive Bayes assumption:** conditional independence assumption that the probabilities $P(f_i|c)$ are independent given the class $c$ and hence can be 'naively' multiplied as follows\n$P(f_1,f_2,...,f_n|c)=P(f_1|c)P(f_2|c)...P(f_n|c)$\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n**How can we learned the probabilities $P(c)$ and $P(f_i|c)$?** consider maximum likelihood estimate, simply use the frequencies in the data, prior $P(c)$ we ask \nwhat percentage of the documents in our training set are in each class $c$. Let $N_c$ be the number of documents in our training data with class $c$ and $N_doc$ be the total number of documents. \nThen: $\\hat{P}(c)=$ $N_c\\over N_doc$, the probability $P(fi|c)$, we assume a feature is just the existence of a word in the document's bag of words, and so we'll want P(wi|c), which we compute as\nthe fraction of times the word $w_i$ appears among all words in all documents of topic $c$. We first concatenate all documents with category c into one big “category c” text.\nThen we use the frequency of $w_i$ in this concatenated document to give a maximum likelihood estimate of the probability: $\\hat{P}(w_i|c)=$  $count(w_i,c)\\over \\sum_{w\\in V} count(w,c)$, Here the vocabulary \n$V$ consists of the union of all the word types in all classes, not just the words in one class $c$\n\n**Add-one(Laplace) smoothing:** suppose there are no training documents that both contain the word “fantastic” and are classified as positive. $\\hat{P}(\"fantastic\"|positive)=$  $count(\"fantastic\",positive)\\over \n\\sum_{w\\in V} count(w,positive)$ $=0$, but since naive Bayes naively multiplies all the feature likelihoods together, zero probabilities in the likelihood term for any class will cause the probability of the\nclass to be zero, we use $\\hat{P}(w_i|c)=$  $count(w_i,c)+1\\over \\sum_{w\\in V} (count(w,c)+1)$\n\n**unknown words and stop words:** remove words in test data but not in training data from the test document and not include any probability for them at all, and also ignore stop wordd(very frequent words) like \n$the$ and $a$.\n\n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n**multinomial naive Bayes:** whether a word occurs or not seems to matter more than its frequency, thus clipping the word counts in each document at 1\n\n**how to deal with negation:** during text normalization, prepend the prefix $NOT_$ to every word after a token of logical negation (n't, not, no, never) until the next punctuation mark.\n\n**sentiment lexicons:** lists of words that are preannotated with positive or negative sentiment.\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**naive Bayes model can be viewed as a set of class-specific unigram language models, in which the model for each class instantiates a unigram language model:**  Since the \nlikelihood features from the naive Bayes model assign a probability to each word $P(word|c)$, the model also assigns a probability to each sentence: $P(s|c)=\\prod_{i \\in positions} P(w_i|c)$\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n**confusion matrix:** true positive(system positive & gold positive), false positive(system positive & gold negative), false negative(system negative & gold positive), true negative(system negative & gold negative)\n\n**Presition(measures the percentage of the items that the system detected that are in fact positive):** $Presition=$ $true positives \\over true positives + false positives$\n\n**Recall(measures the percentage of items actually present in the input that were correctly identified by the system):** $Recall=$ $true positives \\over true positives + false negatives$\n\n**F-mearure:** $F_{beta}=$ $(beta^2 + 1)PR \\over beta^2P + R$ $beta>1$, favor recall, opposite is the same\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n**Cross validation:** we randomly choose a training and test set division of our data, train our classifier, and then compute the error rate on the test set. Then \nwe repeat with a different randomly selected training set and test set. We do this sampling process 10 times and average these 10 runs to get an average error rate. This is called 10-fold cross-validation.\n\n**How to deal with overestimation of the system:** create a fixed training set and test set, then do 10-fold cross-validation inside the training set, but compute error rate the normal way in the test set.\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 - **Naive Bayes**: Assume effects are independent of each other, given the label. $P(Y|X_1,X_2,...,X_N)=Y(Y)\\prod_{i=1}^{N}P(X_i|Y)$, time complexity: $|Y|\\times N\\times |X|$ where |Y| and |X| are the domain size of X and Y, respectively. This is obviously smaller than using the joint model $P(Y,X_1,...,X_N)$ with independence assumption $|Y|\\times |X|^N$\n\n- Bag of words: Use Naive Bayes for text classification. DOES NOT consider the ordering of words. Each word is identically and (conditionally) independently distributed, given the label. \n\n- Learn parameters on training set -> tune hyperparameters on held out set -> test accuracy on test set\n\n- **maximum likelihood estimator (MLE)**: $P_{MLE}(x)=\\frac{Count(x)}{All_samples}$\n\n- To address \"unseen data\" problem: (a) Laplacian smoothing (b) Linear interpolation: $P_{LIN}(x|y)=\\alpha \\hat{P}(x|y)+(1-\\alpha)\\hat{P}(x)$, where $\\hat{P}(x|y)$ and $\\hat{P}(x)$ are empirical distribution we get from training data. \n\n- **Confidence of classifier**: Describes how sure the classifier about its decision. $confidence(x)=max_y P(y|x)$ \n\n- **Perceptron**: \n  - Linear classification: $activation(x)=\\sum_i w_if_i(x)=w · f$, activation function is just SUM. $w$本质上是分类平面的法向量\n  - positive -> y*=1, negative -> y*= -1\n  - How to update weights: If $y=y^*$, no change. If incorrect, $w\\leftarrow w+y^*·f$ (Here $y^*$ is the groundtruth)\n  - **Multi-class perceptron**: One weight vector $w_y$ for each class. Prediction: $y=argmax_y w_y·f$. If prediction is correct, no need to change. If wrong, $w_y\\leftarrow w_y-f, w_{y^*}\\leftarrow w_{y^*}+f$, lower score of wrong answer, higher score of correct answer\n  - Problems with perceptron: Weights do not make sense when data is nonseparable, generalizes poorly ... \n  - **Solution**: **MIRA (margin infused relaxed algorithm)** and **minimum correcting update**. We want to minimize the changes in weight: $min_w \\frac{1}{2}||w_y-w'_y||^2$, s.t. $ w_{y^*}·f(x)\\geq w_y ·f(x)+1$. Update: $w_y = w_y'-\\tau f(x),w_{y^*}=w_{y^*}'+\\tau f(x)$ (* denotes ground-truth)\n  - $min_w \\frac{1}{2}||w_y - w'_y||^2 \\Leftrightarrow min_{\\tau}||\\tau f||^2$. Combined with the update equation, $(w_{y^*}'+\\tau f)·f=(w'_y-\\tau f)·f+1, \\tau=\\frac{(w'_y-w'_{y^*})·f+1}{2f·f}$\n  - In practice, a too large step-size is also bad => can cap the maximum step size $\\tau ^* = min(\\tau, C)$ (C is some constant)\n\n- **SVM**: $min_w \\frac{1}{2}||w||^2,s.t.\\forall i,y,w_{y^*}·f(x)\\geq w_y ·f(x)+1$\n\n- Logical functions: Networks of perceptrons can represent any logical operator.  \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n**The difference of logistic regression and naive bayes:** naive bayes is a generative model but logistic regression is a discriminative model.\n\n**Weight and bias:** $z=(\\sum_{i=1}^n w_ix_i) + b$\n\n**Sigmoid function:** $y=\\sigma (z)=$ $1\\over 1 + e^{-z}$, making the linear layer to the probabilities.\n\n**Decision boundary:** $\\hat{y}=1\\quad if P(y=1|x)>0.5$, $\\hat{y}=0 \\quad otherwise$\n\n\n## SLP Chapter 5.2 Learning in Logistic Regression\n**lost fuction and cost function:** the distance between the system output and the gold output, and the average of the loss function of multiple samples.\n\n**How to learn the parameters:** gradient descent, stochastic gradient descent, mini_batch gradient descent.\n\n## SLP Chapter 5.3 The cross-entropy loss function\n**The lost function of the logistic regression:** cross-entropy loss, $L(\\hat{y}, y)=$ How much $\\hat{y}$ differs from the true $y$   \n$L_{CE}(\\hat{y}, y) = -[ylog\\hat{y} + (1-y)log(1-\\hat{y})]$\n\n## SLP Chapter 5.4 Gradient Descent\n**Convex function:** A convex function has just one minimum; there are no local minima to get stuck in, so gradient\ndescent starting from any point is guaranteed to find the minimum.\n\n**Gradient:** The gradient descent algorithm answers this question by finding the gradient of the loss function at the current point and moving in the opposite direction. \nThe gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function.\n\n**Learning rate:** The magnitude of the amount to move in gradient descent is the value of the slope $d\\over dw$ $f(x; w)$ weighted by a learning rate $η$.\n\n**Mini-batch training and stochastic gradient decent:** in batch training we compute the gradient over the entire dataset. By seeing so many examples, batch training offers \na superb estimate of which direction to move the weights, at the cost of spending a lot of time processing every single example in the training set to compute this perfect direction.\nIn mini-batch training, we train on a group of m examples that is less than the whole dataset. (If $m=1$ we are doing stochastic).\n\n## SLP Chapter 5.5 Regularization\n**Regularization is also called generalization:** the purpose is to reduce overfitting.\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 - Classifier component: feature $x=[x_1,x_2,...,x_n]$, classification function $p(y|x)$, loss function, optimizer. For **logistic regression**, we use **cross entropy loss** and **stochastic gradient descent**. \n\n- **logistic regression**: for each $x \\in X$, where $X$ denotes the training set, calculate $z=w · x+b, p(y=1|x)= \\hat{y}=Sigmoid(z)= \\frac{1}{1+e^{-z}}$\n\n- **Loss function**: Maximize the log likelihood on training set <=> minimize cross entropy loss (negative log likelihood). \n  - For one sample $(x, y)$, likelihood: $p(y|x)=\\hat{y}^y (1- \\hat{y})^{1-y}$, log: $logp(y|x)=y log \\hat{y}+(1-y)log(1- \\hat{y})$\n  - **CE**: $L_{CE}(y, \\hat{y})=-(ylog \\hat{y}+(1-y)log(1- \\hat{y}))$\n  - Take average across the training set: $L_{CE}=-log\\prod_{i=1}^n \\hat{y_i}^{y_i}(1- \\hat{y_i})^{1-y_i}=-\\sum [y_i log( \\hat{y_i})+(1-y_i)log(1- \\hat{y_i})]$ (divide by training set size to average)\n  - **gradient descent**: $w^{t+1}=w^{t}-\\eta \\frac{d}{dw}L_{CE}( \\hat{y}, y|x)$. $\\frac{ \\partial L_{CE}}{\\partial w_i}=(\\sigma(w · x + b)-y)x_i$. The gradient for multiple data points is just the sum of individual gradients. \n  - One useful property: $d \\sigma / dz=(1- \\sigma) \\sigma$\n  - **multinomial Cross entropy**: $L_{CE}=- \\sum_{i=1}^{k}y_i log( \\hat{y_i})$, k is # classes\n\n- **Stochastic gradient descent** chooses one single example at a time to update the parameters. Can also use a batch (over entire dataset) or minibatch version. \n\n- LASSO regression: uses l1 regularization; **ridge regression**: uses l2 regularization\n\n- For **multi-class classification**: use **softmax** as a generalization to sigmoid. The probability that an instance belong to class i among k classes: $softmax(z_i)= \\frac{e^{z_i}}{ \\sum_{j=1}^k e^{z_j}}, i \\in [1,...,k]$\n\n- **activation function**: $a=f(z)$, a can be Sigmoid, tanh, rectified linear unit (ReLU). ReLU: $f(x)=max(x,0)$  \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n \n**Goal:** Explore the two architectures primarily through the lens of probabilistic.\n\n**Language Model:** give us the ability to assign a conditional probability to every next word, giving a distribution over the entire vocabulary.\n\n**First equation:** $P(w_{1:n})= \\prod_{i=1}^{n}P(w_i|w_{<i})$: provides a clear training objective based on the model for next word in a sequence.\n\n**Two methods to instantiate probabilistic language model:** N-gram models, feedforward neural networks with sliding windows, but are constrained by Markov assumption: \n$P(w_{n}|w_{1:n-1})≈P(w_{n}|w_{(n-N+1):(n-1)})$, which has a fixed preceding context of size N: any input that occured earlier than that has no bearing on the outcome.\n            \n**Evaluation:** examine how well the  language model predict unseen data. Good models assign higher probabilities to unseen data. We use **preplexity(PP)** as a measure \nof model $θ$ quality.\n\n\n## SLP Chapter 9.2 Recurrent Neural Networks\n  \n**Definition for RNN:** any network that contains a cycle within its network connections, which is any network where the value of a unit is dependent on its earlier outputs as an input.\n\n**RNN process:** an input vector represesnt the current input. Then multiply a weight matrix and pass through a non-linear activation function to compute the values \nfor a layer of hidden units which is used to calculate the corresponding output.\n\n**Difference between Feedforward network and RNN:** RNN augments the input to the compuation at the hidden layer with the value of the hidden layer from the preceding point in time.\n  \n             \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n \n**Lexical Semantics:** draw on results in the linguistic study of meaning.\n\n**Lemmas:** citation form (verb), the specific forms are called wordforms. The lemmas can be polysemous.\n\n**Synonymy:** when one word has a sense whose meaning is identical to a sense of another word, or nearly identical, we say the two senses of those two words are synonyms.\n\n**Propositional meaning:** two words are synonymous if they are substitutable for one another in any sentence without changing \n            the truth conditions of the sentence, the situations in which the sentence would be true.\n\n**Principle of Contrast:** states that a difference in linguistic form is always associated with some difference in meaning.\n\n**Word similarity:** While words don’t have many synonyms, most words do have lots of similar words.\n\n**Word relatedness:** The meaning of two words can be related in ways.\n             \n\n## SLP Chapter 6.2 Vector Semantics\n \n**Vector Semantics:** standard way to represent word meaning in NLP.\n\n**Embeddings:** vectors for representing words.\n\n**tf-idf model:** an important baseline, the meaning of a word is defined by a simple function of the counts of nearby words. \n            We will see that this method results in very long vectors that are sparse.\n\n**word2vec model:** construct short, dense vectors that have useful semantic properties\n            \n**cosine:** the standard way to use embeddings to compute semantic similarity, between two words, two sentences, or two documents, \n            an important tool in practical applications\n\n## SLP Chapter 6.3 Words and Vectors\n \nVector or distributional models of meaning are generally based on a **co-occurrence matrix**, a way of representing how often words co-occur.\n\n**term-document matrix:** each row represents a word in the vocabulary and each column represents a document from some collection of documents.\nWords in each document(row vector), document of each words(column vector).\n\n**Term-document matrices** were originally defined as a means of finding similar documents for the task of document information retrieval.Information retrieval \nis the task of finding the document d from the D documents in some collection that best matches a query q.\n            \n**term-term matrix(word-word matrix or term-context matrix):** columns are labeled by words rather than documents. dimensionality: |V|*|V|\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n \n**Cosine for measuring similarity:** Use dot product(inner product) which has high values in same dimensions, zero in orthogonal vectors.\n**Problem:** it favors long vectors and we’d like a similarity metric that tells us how similar two words are regardless of their frequency and length. So, we use normalized dot product.\nFor unit vectors, the dot product is the same as the cosine, $cos(v, w) =$ $vw\\over |v||w|$.\n\n\n## SLP Chapter 6.8 Word2vec\n \n**Word2vec:** short dense vectors embeddings are short with the number of dimensions d ranging from 50-1000. The values will be real-valued numbers that can be negative, \nwhich makes the dense vector works better in NLP. The lower dimensionality makes the classifier learn faster. The dense vector is also good at capturing synoymy.\n\n**The advantages of word2vec:** fast and efficient to train and easily avaiable online with code and pretrained embeddings. Static embedding(learn one fixed embedding for each word in the vocabulary).\n\n**self-supervision:** obtains supervisory signals from the data itself\n\n**why word2vec is simpler than neural network language model:** word2vec simplifies the task(makes it binary classification instead of word prediction) **and**\nword2vec simplifies the architecture(training a logistic regression classifier instead of a multi-layer neural network with hidden layers that demand more sophisticated training algorithms).\n\n**process of slip-gram:** (1)given a tuple $(w,c)$ of a target word $w$ paired with a candidate context word $c$, return the probability that $c$ is context word: $P(+|w,c)$\n(2)the probablity that the word is not a real context for $w$, just 1 minus the real $c$ probability: $P(-|w,c) = 1 - P(+|w,c)$ (3)base the proability on embedding similarity: \ntwo vectors are similar if they have a high dot product, Similarity(w,c) ≈ c*w (4)Since dot product can be negative while probability cannot be negative, use logistic or \nsigmoid function (5)Model the probability that the word $c$ is a real context word for target word $w$: $P(+|w,c) =$ $\\sigma(c*w)=$ $1\\over 1+exp^{-c*w}$\n(6)As $c$ is not a real context word for $w$: $P(-|w,c) = 1 - P(+|w,c)$\n(7)As many context words in the window and Skip-gram makes the simplying assumption that all context words are independent\n\n**Learning skip-gram embeddings:** skip-gram with negative sampling(SGNS) uses more negative examples than positive examples with a ratio $k$ between them, for each $(w, c_{positive})$, \ncreate $k$ negative samples, each consisting of the target $w$ plus a \"noise word(a random word from the lexicon, constrained not to be the target word w)\" $c_negative$.\nThe noise words are chosen according to their weighted unigram frequency $P_{α}(w)$, where $α$ is a weight.\n            \n**The learning algorithm:** adjust those embeddings to (1)Maximize the similarity of the target word, context word pairs (w; c_{pos}) drawn from the positive examples\n(2)Minimize the similarity of the (w;c_neg) pairs from the negative examples. By minimizing the loss function $L_{CE} = -log[P(+|w,c_{pos})$ $\\prod_{i=1}^k$ $P(-|w,c_{neg_{i}})] = -[log \\sigma(c_{pos}w) + $\n $\\sum_{i=1}^k$ $log \\sigma(-c_{neg_{i}}w)]$\n            \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n \n**Semantic properties of embeddings:** 1. Different types of similarity or association: (1)Shorter context windows tend to lead to representations that are a bit more syntactic, \nsince the information comes from immediately nearby words. (2)When the vectors are computed from short context windows, the most similar words to a target word w tend to be semantically similar words \nwith the same parts of speech. (3)When vectors are computed from long context windows, the highest cosine words to a target word w tend to be words that are topically related \nbut not similar. (4)first-order co-occurrence(syntagmatic association): if they are typically nearby each other, second-order co-occurrence(paradigmatic association): if they have similar neighbors. 2. Analogy/Relational Similarity: (1)parallelogram model: solving simple analogy problems of the form $a$ is to $b$ as $a*$ is to what? (2)Equation: $\\hat{b}^* = argmax_x distance(x, a^*-a+b)$\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n \n1. allocational harm: a system alloharm cates resources (jobs or credit) unfairly to different groups\n\n2. Embeddins reflect the statistics of their input and amplify bias.\n\n3. gendered terms become more gendered in embedding space than they were in the input text statistics\n\n4. Embeddings encodes the implicit associations that are a property of human reasoning.\n\n5. reprerepresentational harm: a harm caused by a system demeaning or even ignoring some social groups\n\n6. debiasing: reduce bias in embeddings not eliminate it\n  (1): developing a transformation of the embedding space that removes gender stereotypes but preserves definitional gender\n  (2): changing the training procedure\n             \n\n## SLP Chapter 6.12 Evaluating Vector Models\n \n**how to Evaluating Vector Models:**\n\n1. Evaluation metric for vector model: extrinsic evaluation on tasks using vectors in an NLP task and seeing whether this improves performance over some other model\n\n2. Intrinsic evalution matric is to test their performance on similarity: computing the correlation between an algorithm’s word similarity scores and word similarity ratings assigned by humans.\n\n3. Dataset: \n\n  (1): WordSim-353: a commonly used set of ratings from 0 to 10 for 353 noun pairs\n\n  (2): SimLex-999: is a more difficult dataset that quantifies similarity (cup, mug) rather than relatedness (cup, coffee), and including both concrete and abstract adjective, noun and verb pairs\n\n  (3): TOEFL: a set of 80 questions,  each consisting of a target word with 4 additional word choices; the task is to choose which is the correct synonym\n\n4. Slightly more realistic are intrinsic similarity tasks that include context\n\n5. Another task used for evaluation is the analogy task where the system has to solve problems of the form a is to b as a* is to b*.\n\n6. All embedding algorithms suffer from inherent variability:\n\n  (1): because of randomness in the initialization and the random negative sampling, algorithms like word2vec may produce different results even from the same dataset, and individual documents in a collection may strongly impact the resulting embeddings\n\n  (2): When embeddings are used to study word associations in particular corpora, therefore, it is best practice to train multiple embeddings with bootstrap sampling over documents and average the results.\n            \n\n## Module 14 Lecture Notes\n - N-gram way: **Goal**: Estimate the probability of getting a sentence $P(w_{1:n}) \\approx \\prod_{i=1}^{n}P(w_i|w_{i-k:i-1})$, where $P(w_{i+1}=m|w_{i-k:i})=\\frac{Count(w_{i-k:i+1})}{Count(w_{i-k:i})}$, or a smoothed version $P(w_{i+1}=m|w_{i-k:i})=\\frac{Count(w_{i-k:i+1})+\\alpha}{Count(w_{i-k:i})+\\alpha|V|}$\n\n- **Neural (Probabilistic) Language Model**: \n\n  - Key: represent each word using an **embedding** (usually **low dimensional, dense vector**). The network simultaneously learn embeddings and probability parameters. Let the dimension of embedding be $d_w$, then embedding each word is $v(w) \\in \\R^{d_w}$\n\n  - Input: **Concatenation** of the embedding of each word in the sequence $w_{1:k}$, $x=[v(w_1); v(w_2);...;v(w_k)]$\n  - Output: Probability distribution of $w_{k+1}$\n  - For each k-gram, using words i-k+1:i-1 to calculate input, word k as ground-truth\n  - Typically train using CE loss \n  - Advantages: Lower perplexity score, can use longer sequence, **generalize well to unseen contexts** (eg. in training set we only have \"a cute dog\", but in the test set we can get \"a cute cat\"). By-product: we can get a set of word embeddings. \n\n- **Vector semantics**\n  - Core question: How to represent the meaning of a word\n  - **meaning**: synonym (similar), antonym (opposite), connotation (positive or negative), semantic roles (buy, sell, pay are different parts of the same underlying *purchasing* event), support for entailment. \n  - Measure word **similarity**: If two words almost always occur in the same environments, they are similar words => useful in question answering task\n  - **vector space model**: Essentially clustering. Project word (document) into some high dimensional space. Whenever we have a query, project it into the same space and see what words (documents) are close to it.\n  - **term-document matrix**: Each row represent a term (word), each column represents a document. Entry value: How often does a term occur in a document. **Application of term-document matrix:** Compare two columns can detect plagiarism, Compare two rows implies synonym and antonyms. Can use **cosine distance** to measure similarity between two words $u$ and $v$: $L_{cos}(u,v)=1-\\frac{u·v}{|u|·|v|}$. \n  - **term-term matrix** (=term context matrix): $|V|\\times|V|$ matrix. Entry value represents how often a word appears in context window of the other word. **Context window** could be something as simple as *past 2 and coming 2 words surrounding one*, or more complicated dependency relationship like subject and verb. \n  - **TF-IDF**: term frequency in a document / #number of documents the word of interest occurs in. Simply relying on word count will skew model towards \"the\" \"of\", etc. TF-IDF solves the problem. TF-IDF is mainly used in **sparse vector**. \n  - **How to get dense vectors representing co-occurrences**: 1. Treat the target word and a neighboring context word as positive examples.  2. Randomly sample other words in the lexicon to get negative samples. 3. Use logistic regression to train a classifier to distinguish those two cases.  4. Use the weights as the embeddings. **Examples of dense vector**: Word2Vec\n\n- **Word2Vec**: Learn dense word embeddings simultaneously when learning to predict words. A classifier gets trained to predict neighboring words. We make positive samples (true positive word pairs) and negative samples (randomly generated) to train this classifier, encourage positive samples to have high similarity, and negative samples to have low similarity score in the projection space. **In a word, use running text as supervised training data**\n\n- **skip gram**: A method to train embeddings in Word2Vec. **How it works**: 1. Treat the target word and a neighboring context  word as positive examples. 2. Randomly sample other words in the lexicon to get  negative samples 3. Use logistic regression to train a classifier to  distinguish those two cases 4. Use the weights as the embeddings \n\n- **Evaluate word embeddings**: Compare to human scores on word similarity-type tasks. Examples: (1) **intrinsic**: A group of experts judge how similar each pair of words is. Compare the model score with expert judgement. (2) **Compute correlation**: Also rely on expert knowledge, but instead of directly giving score to each pair, ask question like \"(love, affair) ><= (professor tomato)?\"\n\n- **Vector arithmetic**: Based on learned embeddings, answer questions like \"man (a) is to king (a\\*) like women (b) is to ? (b\\*)\". b\\*= b\\*-b+a. Convert **relational meanings** to just vector arithmetic calculations. We can find $b^*$ by optimize: $argmax_{b^*\\in V}cos(b^*, a^*-a+b)=argmax_{b^* \\in V}cos(b^*-b,a^*-a)=argmax_{b^*\\in V}[cos(b^*,b)-cos(b^*,a)+cos(b^*,a^*)]$\n\n- **useful formula**: $1- \\sigma(z)=\\sigma(-z)$\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}