{
 "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",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lzaavW96tcxM",
    "outputId": "54580f1e-22eb-4657-8e14-104a615b6276"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 116 words long, so you could write an additional 384 words.\n"
     ]
    }
   ],
   "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)))"
   ]
  },
  {
   "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",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "2cd4c8a2-805b-483a-8fae-409ce38e0560"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n"
     ]
    }
   ],
   "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))"
   ]
  },
  {
   "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",
   "execution_count": 1,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 8 - Markov Decision Process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
    "\n",
    "chapter16_1 = \"\"\"\n",
    "1. MEU principle *formalize* \"rational agent should do 'the right thing'\" but doesn't *operationalize* that advice. \n",
    "2. The utility function applies to the very *next* state. \n",
    "\"\"\" \n",
    "chapter16_2 =  \"\"\"\n",
    "**Axioms** of utility\n",
    "\n",
    "1. Orderability: A>B or B>A or A~B\n",
    "2. Transitivity: A>B, B>C => A>C\n",
    "3. Continuity: A>B>C => $\\exists$ p, [p, A; 1-p, C] ~ B\n",
    "4. Substitutability: A~B => [p, A; 1-p, C] ~ [p, B; 1-p, C]\n",
    "5. Monotonicity: A>B => (p>q <=> [p, A; 1-p, B] > [q, A; 1-q, B])\n",
    "6. Decomposability: 数乘分配律 [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; 1-p, (1-p)q, B; (1-p)(1-q), C]\n",
    "\n",
    "**Existence**: if an agent's preferences obey axioms, $\\exists$ utility function. \n",
    "\"\"\"\n",
    "chapter16_3 =  \"\"\"\n",
    "- Risk-averse: concave utility function. Prefer sure things. \n",
    "- Risk-seeking: convex utility function. \n",
    "- Risk-neutral: linear utility function. \n",
    "- Certainty equivalent: the (certain) value in lieu of a lottery. \n",
    "- Insurance premium:= expected value - certainty equivalent. **Same U, delta in x-axis (in graph).** Risk aversion suggests positive insurance premium. \n",
    "\n",
    "1. Decision theory is a normative theory. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
    "chapter17_1 = \"\"\"\n",
    "1. Methods for solving MDPs usually involve **dynamic programming** (recursively breaking the problem into smaller pieces and remembering the optimal solutions to the pieces). \n",
    "2. Infinite horizon just indicates that there is no **fixed** deadline (doesn't mean interminable). \n",
    "3. **Bellman equation** : $$U(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
    "4. **Q-function** (action-utility function): expected utility of taking a given action in a given state. $$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
    "5. Shaping theorem: $\\Phi(s)$ is any function of state s, after the transformation $$R'(s,a,s') = R(s,a,s') + \\gamma\\Phi(s')-\\Phi(s)$$ the optimal policy won't change. \n",
    "\"\"\"\n",
    "chapter17_2 =  \"\"\"\n",
    "1. ***Value Iteration***\n",
    "    \n",
    "    *n* Bellman equations for *n* unknown states (n utilities). Do Bellman update ($U = \\max_{a\\in A(s)}{Q}$ for each state)\n",
    "    $$ U_{i+1}(s) \\gets \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')]$$\n",
    "    until $|U_{i+1}(s)-U_i(s)|\\leq\\epsilon(1-\\gamma)\\gamma$ for each state, where $\\epsilon$ is the maximum error of utility. \n",
    "\n",
    "\n",
    "2. ***Policy Iteration***\n",
    "\n",
    "    Policy valuation: calculate U **given** a policy $\\pi$. \n",
    "    \n",
    "    Policy improvement: calculate a new MEU policy ($a = argmax{Q}$ for each state). \n",
    "    \n",
    "    Repeat until no change in utilities. \n",
    "    \n",
    "    i.e. Solve simplified version of Bellman equation\n",
    "    $$ U_{i}(s) = \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$ (substitute $a$ by $\\pi_i(s)$). \n",
    "\n",
    "\n",
    "3. Modified Policy Iteration\n",
    "\n",
    "    Do simplified Bellman update for some number of times\n",
    "    $$ U_{i+1}(s) \\gets \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$\n",
    "    \n",
    "\n",
    "4. Asynchronous Policy Iteration\n",
    "\n",
    "    Apply update (policy improvement or simplified value iteration) to subsets of states. \n",
    "    \n",
    "    \n",
    "5. Linear Programming\n",
    "\n",
    "    Minimize *U(s)* for all *s* s.t. for every state *s* and every action *a* $$U(s) \\geq \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module8_lecture_notes = \"\"\"\n",
    "- MDP: set of states; set of actions; transition function; reward function; initial state(; terminal state(s))\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 8.\n",
    "# You can define any term in the textbook or lecture, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 25 words long.\n",
    "\n",
    "module8_definitions = {\n",
    "    \"MEU\" : \"maximum expected utility (rational agent)\", \n",
    "    \"value function / ordinal utility function\" : \"only preferences ranking matters, the numbers don't matter\",\n",
    "    \"preference elicitation\" : \"present the choices, and determine the utility fuinction by observed preferences\",\n",
    "    \"contraction\" : \"operator that makes difference between estimates smaller\",\n",
    "    \"normalized utility\" : \"worst = 0, best = 1\",\n",
    "    \"normative theory\" : \"how should act\", \n",
    "    \"descriptive theory\" : \"how acutally act\", \n",
    "    \"certainty effect\" : \"people are attracted by certain gains\",\n",
    "    \"ambiguity aversion\" : \"people prefer known probabilities\",\n",
    "    \"framing effect\" : \"same probability, different statement => different actions\",\n",
    "    \"anchoring effect\" : \"people prefer relative utility judgement\",\n",
    "    \"environment history\" : \"a sequence of states and actions\",\n",
    "    \"policy (solution)\" : \"specifies actions at each possibly reached state\",\n",
    "    \"finite horizon\" : \"game is over after time N (fixed)\",\n",
    "    \"nonstationary policy\" : \"depend on time\",\n",
    "    \"stationary policy\" : \"depend only on current state (usually in games with infinite horizon)\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "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",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 572
    },
    "id": "gYYeNcdM_maE",
    "outputId": "207ec42d-9028-4960-d00c-85836a9d5f16",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "1. MEU principle *formalize* \"rational agent should do 'the right thing'\" but doesn't *operationalize* that advice. \n",
       "2. The utility function applies to the very *next* state. \n",
       "\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "**Axioms** of utility\n",
       "\n",
       "1. Orderability: A>B or B>A or A~B\n",
       "2. Transitivity: A>B, B>C => A>C\n",
       "3. Continuity: A>B>C => $\\exists$ p, [p, A; 1-p, C] ~ B\n",
       "4. Substitutability: A~B => [p, A; 1-p, C] ~ [p, B; 1-p, C]\n",
       "5. Monotonicity: A>B => (p>q <=> [p, A; 1-p, B] > [q, A; 1-q, B])\n",
       "6. Decomposability: 数乘分配律 [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; 1-p, (1-p)q, B; (1-p)(1-q), C]\n",
       "\n",
       "**Existence**: if an agent's preferences obey axioms, $\\exists$ utility function. \n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "- Risk-averse: concave utility function. Prefer sure things. \n",
       "- Risk-seeking: convex utility function. \n",
       "- Risk-neutral: linear utility function. \n",
       "- Certainty equivalent: the (certain) value in lieu of a lottery. \n",
       "- Insurance premium:= expected value - certainty equivalent. **Same U, delta in x-axis (in graph).** Risk aversion suggests positive insurance premium. \n",
       "\n",
       "1. Decision theory is a normative theory. \n",
       "\n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       "\n",
       "1. Methods for solving MDPs usually involve **dynamic programming** (recursively breaking the problem into smaller pieces and remembering the optimal solutions to the pieces). \n",
       "2. Infinite horizon just indicates that there is no **fixed** deadline (doesn't mean interminable). \n",
       "3. **Bellman equation** : $$U(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
       "4. **Q-function** (action-utility function): expected utility of taking a given action in a given state. $$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
       "5. Shaping theorem: $\\Phi(s)$ is any function of state s, after the transformation $$R'(s,a,s') = R(s,a,s') + \\gamma\\Phi(s')-\\Phi(s)$$ the optimal policy won't change. \n",
       "\n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       "\n",
       "1. ***Value Iteration***\n",
       "    \n",
       "    *n* Bellman equations for *n* unknown states (n utilities). Do Bellman update ($U = \\max_{a\\in A(s)}{Q}$ for each state)\n",
       "    $$ U_{i+1}(s) \\gets \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')]$$\n",
       "    until $|U_{i+1}(s)-U_i(s)|\\leq\\epsilon(1-\\gamma)\\gamma$ for each state, where $\\epsilon$ is the maximum error of utility. \n",
       "\n",
       "\n",
       "2. ***Policy Iteration***\n",
       "\n",
       "    Policy valuation: calculate U **given** a policy $\\pi$. \n",
       "    \n",
       "    Policy improvement: calculate a new MEU policy ($a = argmax{Q}$ for each state). \n",
       "    \n",
       "    Repeat until no change in utilities. \n",
       "    \n",
       "    i.e. Solve simplified version of Bellman equation\n",
       "    $$ U_{i}(s) = \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$ (substitute $a$ by $\\pi_i(s)$). \n",
       "\n",
       "\n",
       "3. Modified Policy Iteration\n",
       "\n",
       "    Do simplified Bellman update for some number of times\n",
       "    $$ U_{i+1}(s) \\gets \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$\n",
       "    \n",
       "\n",
       "4. Asynchronous Policy Iteration\n",
       "\n",
       "    Apply update (policy improvement or simplified value iteration) to subsets of states. \n",
       "    \n",
       "    \n",
       "5. Linear Programming\n",
       "\n",
       "    Minimize *U(s)* for all *s* s.t. for every state *s* and every action *a* $$U(s) \\geq \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
       "\n",
       "\n",
       "## Module 8 Lecture Notes\n",
       "\n",
       "- MDP: set of states; set of actions; transition function; reward function; initial state(; terminal state(s))\n",
       "\n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Meu** - maximum expected utility (rational agent)\n",
       "* **Value function / ordinal utility function** - only preferences ranking matters, the numbers don't matter\n",
       "* **Preference elicitation** - present the choices, and determine the utility fuinction by observed preferences\n",
       "* **Contraction** - operator that makes difference between estimates smaller\n",
       "* **Normalized utility** - worst = 0, best = 1\n",
       "* **Normative theory** - how should act\n",
       "* **Descriptive theory** - how acutally act\n",
       "* **Certainty effect** - people are attracted by certain gains\n",
       "* **Ambiguity aversion** - people prefer known probabilities\n",
       "* **Framing effect** - same probability, different statement => different actions\n",
       "* **Anchoring effect** - people prefer relative utility judgement\n",
       "* **Environment history** - a sequence of states and actions\n",
       "* **Policy (solution)** - specifies actions at each possibly reached state\n",
       "* **Finite horizon** - game is over after time N (fixed)\n",
       "* **Nonstationary policy** - depend on time\n",
       "* **Stationary policy** - depend only on current state (usually in games with infinite horizon)\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "# Module 9 - Reinforcement Learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
    "chapter17_3 =  \"\"\"\n",
    "1. Tradeoff between **exploration** and **exploitation**. \n",
    "2. Arms are independent since the agent can work on only one arm at a time. \n",
    "3. Gittins index: an optimal strategy is indifferent between **(a)** running $M$ up to the best possible stopping time\n",
    "and then switch to $M_\\lambda$, and **(b)** running $M$ immediately. i.e.\n",
    "\n",
    "$$E[(\\sum^{T-1}_{t=0}\\gamma^tR_t)+\\sum^\\infty_{t=T}\\gamma^t\\lambda] = \\sum^\\infty_{t=0}\\gamma^t\\lambda $$\n",
    "\n",
    "i.e.\n",
    "$$\\lambda=\\max_{T>0} ({E(\\sum^{T-1}_{t=0}\\gamma^tR_t)}/{E(\\sum^{T-1}_{t=0}\\gamma^t)})$$\n",
    "\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
    "chapter22_1 =  \"\"\"\n",
    "1. The goals in MDP and RL are the same: maximizing the expected sum of rewards. However, in RL the MDP problem is learned but not given. \n",
    "2. **Model-based RL**: Learn the transition model or use the known transition model, and learn a utility function, to make decisions. \n",
    "3. **Model-free RL**: Neither learn or know the transition model.\n",
    "- **Q-learning / Action-utility learning** learns Q-functions. \n",
    "- **Policy search** learns the mapping from states to actions (reflex agent). \n",
    "\"\"\"\n",
    "chapter22_2 =  \"\"\"\n",
    "1. **Passive RL**: policy fixed, the agent learns utilities of states. (similar to policy evaluation)\n",
    "2. Direct utility estimation: $U(s) = E(total-reward-from-next-state)$, reward-to-go. This ignores $U(next-state)$, so it converges slowly. \n",
    "3. Adaptive dynamic progamming (ADP): uses learned transition model and known rewards in the equation. \n",
    "Can use modified policy iteration. \n",
    "$$U_i(s) = \\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$\n",
    "4. Temporal-difference learning: $a$ is learning rate\n",
    "$$U^\\pi(s) \\gets U^\\pi(s) + a [R(s,\\pi(s),s')+\\gamma U^\\pi(s')-U^\\pi(s)]$$\n",
    "- If $a$ decreases as the number of times a state has been visited increases, $U^\\pi(s)$ will converge to the correct value. \n",
    "- TD updates don't need a transition model. \n",
    "5. Difference between ADP and DP: \n",
    "ADP adjusts a state to agree with *all* successors weighted by probabilities. \n",
    "TD adjusts a state to agree with *observed* successors (makes one adjustment per observed transition). \n",
    "TD can be viewed as an inaccurate but efficient approximation to ADP. \n",
    "6. Advantage of approximate ADP: the early learned transition model is often far from correct, \n",
    "so there is no need to calculate exact utility function to match it. \n",
    "7. Approximate ADP can use decreasing $a$ so that adjustments are gentler as transition model is more accurate. \n",
    "\"\"\"\n",
    "chapter22_3 =  \"\"\"\n",
    "1. **Active RL**: the agent also learns the policy (satisfies Bellman equation). \n",
    "2. GLIE, greedy in the limit of infinite exploration: try each action in each state an unbounded number of times. \n",
    "This scheme guarantees that an ADP agent can eventually learn the true transition model and the true optimal policy.\n",
    "- An approach to implementing GLIE is to give some weight to actions that haven't been tried often. \n",
    "3. Approach 1, Bayesian RL: assumes a prior probability P(h) on hypothesis *h* about <u>what the true model is</u>. \n",
    "$$\\pi^* = arg\\max_\\pi \\sum_h P(h|observations)U^\\pi_h$$\n",
    "4. Approach 2, Robust control theory: doesn't assign probabilities to models. \n",
    "$$\\pi^* = arg\\max_\\pi\\min_h U_H^\\pi$$\n",
    "This is an **optimal robust policy** that gives best outcome in the worst case over H. \n",
    "5. Q-learning TD update (whenever action *a* is executed in state *s* leading to state *s'*):\n",
    "$$Q(s,a) \\gets Q(s,a)+α[R(s,a,s')+\\gamma\\max_{a'}Q(s',a')-Q(s,a)]$$\n",
    "- Advantage: A TD Q-learning agent **doesn't** need a transition model either for traning or action selection. \n",
    "- Disadvantage: The Q-learning agent has difficulty with sparse rewards since it has no means of looking into the future. \n",
    "6. SARSA, state, action, reward, state, action. The only difference with TD Q-learning update is that it uses Q-value of actually taken action instead of $\\max_{a'}Q$. \n",
    "- Q-learning is an <u>**off-policy**</u> learning algorithm, comparing Q-value with greedy policy (from now). \n",
    "- SARSA is an <u>**on-policy**</u> learning algorithm, comparing Q-value with original policy. \n",
    "\"\"\"\n",
    "chapter22_4 =  \"\"\"\n",
    "1. Approximate the true utility function (or Q-function) by weightede ($θ$) linear combination of feartures. \n",
    "$$U_θ(s) = Θ\\cdot F$$\n",
    "2. RL can generalize from its experiences because updating $θ_i$ will change values of $U_θ$ for **each** state. \n",
    "3. Linear function approximation: the utility (or Q) function must be linear in the features. \n",
    "4. TD learning problem 1: easily diverges with active learning and nonlinear functions. \n",
    "5. TD learning problem 2: catastrophic forgetting. Being in the safe place for a long time resulting in forgetting the dangerous place, \n",
    "since the value function becomes flat. Solution: experience replay. \n",
    "6. Solution 1 to sparse rewards (long action sequences): **reward shaping**. Gives the agent pseudorewards (addtional rewards) for making progress. \n",
    "7. Solution 2 to sparse rewards: HRL, hierarchical RL, begins with a partial program. \n",
    "Hierarchical structure of behavior provides an *additive decomposition* of the utility function. \n",
    "\"\"\"\n",
    "chapter22_5 =  \"\"\"\n",
    "1. Policy search: change the policy as long as performance improves. \n",
    "2. Policy search where policy is <u>represented</u> by Q-functions is not the same as Q-learning. \n",
    "- Policy search finds an estimated Q-function that gives optimal performance; Q-learning finds an Q-function close to real Q-function. \n",
    "- When depth is different, $θ$ that gives good results (Policy search) might be very different from\n",
    "$θ$ that estimates utility function more accurately (Q-learning). \n",
    "3. Stochastic policy gives the probability of selecting action *a* in state *s*. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module9_lecture_notes = \"\"\"\n",
    "1. MDP is offline planning (no need to actually **play** the game).RL is online learning. \n",
    "2. Model-based learning: step 1, learn empirical MDP model; step 2, solve the learned MDP. \n",
    "3. Problem with **direct evaluation**:\n",
    "- each state must be learned separately -> wastes information about state connections\n",
    "- takes a long time to learn\n",
    "4. Exponential moving average is one kind of TD learning. \n",
    "5. **Regret** is a measure of total mistake cost. \n",
    "6. Linear value (evaluation) function: able to be decomposed into linearly additive weights * features. \n",
    "\"\"\"\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module9_definitions = {\n",
    "    \"bandit problem\" : \"an MDP, state space given by Cartesian product\", \n",
    "    \"Bernoulli bandit\" : \"a bandit with reward 0/1 with a fixed probability\",\n",
    "    \"selection problem\" : \"choosing the best option as quickly as possible with fixed cost of trials\",\n",
    "    \"BSP, bandit superprocess\" : \"each arm is a Markov decision process\",\n",
    "    \"reinforcement learning\" : \"an agent interacts with the world and periodically receives rewards\",\n",
    "    \"prioritized sweeping\" : \"prefers to adjust states whose likely successors have just been made a lot adjustments\",\n",
    "    \"online learning algorithm\" : \"updates the parameters after each trial\",\n",
    "    \"supervised learning\" : \"learning a model for an (fully) observable environment\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 536
    },
    "id": "ydOK__lwWgdp",
    "outputId": "4707dfb3-647d-4ac6-9ce2-8249951a4723",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       "\n",
       "1. Tradeoff between **exploration** and **exploitation**. \n",
       "2. Arms are independent since the agent can work on only one arm at a time. \n",
       "3. Gittins index: an optimal strategy is indifferent between **(a)** running $M$ up to the best possible stopping time\n",
       "and then switch to $M_\\lambda$, and **(b)** running $M$ immediately. i.e.\n",
       "\n",
       "$$E[(\\sum^{T-1}_{t=0}\\gamma^tR_t)+\\sum^\\infty_{t=T}\\gamma^t\\lambda] = \\sum^\\infty_{t=0}\\gamma^t\\lambda $$\n",
       "\n",
       "i.e.\n",
       "$$\\lambda=\\max_{T>0} ({E(\\sum^{T-1}_{t=0}\\gamma^tR_t)}/{E(\\sum^{T-1}_{t=0}\\gamma^t)})$$\n",
       "\n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       "\n",
       "1. The goals in MDP and RL are the same: maximizing the expected sum of rewards. However, in RL the MDP problem is learned but not given. \n",
       "2. **Model-based RL**: Learn the transition model or use the known transition model, and learn a utility function, to make decisions. \n",
       "3. **Model-free RL**: Neither learn or know the transition model.\n",
       "- **Q-learning / Action-utility learning** learns Q-functions. \n",
       "- **Policy search** learns the mapping from states to actions (reflex agent). \n",
       "\n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       "\n",
       "1. **Passive RL**: policy fixed, the agent learns utilities of states. (similar to policy evaluation)\n",
       "2. Direct utility estimation: $U(s) = E(total-reward-from-next-state)$, reward-to-go. This ignores $U(next-state)$, so it converges slowly. \n",
       "3. Adaptive dynamic progamming (ADP): uses learned transition model and known rewards in the equation. \n",
       "Can use modified policy iteration. \n",
       "$$U_i(s) = \\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$\n",
       "4. Temporal-difference learning: $a$ is learning rate\n",
       "$$U^\\pi(s) \\gets U^\\pi(s) + a [R(s,\\pi(s),s')+\\gamma U^\\pi(s')-U^\\pi(s)]$$\n",
       "- If $a$ decreases as the number of times a state has been visited increases, $U^\\pi(s)$ will converge to the correct value. \n",
       "- TD updates don't need a transition model. \n",
       "5. Difference between ADP and DP: \n",
       "ADP adjusts a state to agree with *all* successors weighted by probabilities. \n",
       "TD adjusts a state to agree with *observed* successors (makes one adjustment per observed transition). \n",
       "TD can be viewed as an inaccurate but efficient approximation to ADP. \n",
       "6. Advantage of approximate ADP: the early learned transition model is often far from correct, \n",
       "so there is no need to calculate exact utility function to match it. \n",
       "7. Approximate ADP can use decreasing $a$ so that adjustments are gentler as transition model is more accurate. \n",
       "\n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       "\n",
       "1. **Active RL**: the agent also learns the policy (satisfies Bellman equation). \n",
       "2. GLIE, greedy in the limit of infinite exploration: try each action in each state an unbounded number of times. \n",
       "This scheme guarantees that an ADP agent can eventually learn the true transition model and the true optimal policy.\n",
       "- An approach to implementing GLIE is to give some weight to actions that haven't been tried often. \n",
       "3. Approach 1, Bayesian RL: assumes a prior probability P(h) on hypothesis *h* about <u>what the true model is</u>. \n",
       "$$\\pi^* = arg\\max_\\pi \\sum_h P(h|observations)U^\\pi_h$$\n",
       "4. Approach 2, Robust control theory: doesn't assign probabilities to models. \n",
       "$$\\pi^* = arg\\max_\\pi\\min_h U_H^\\pi$$\n",
       "This is an **optimal robust policy** that gives best outcome in the worst case over H. \n",
       "5. Q-learning TD update (whenever action *a* is executed in state *s* leading to state *s'*):\n",
       "$$Q(s,a) \\gets Q(s,a)+α[R(s,a,s')+\\gamma\\max_{a'}Q(s',a')-Q(s,a)]$$\n",
       "- Advantage: A TD Q-learning agent **doesn't** need a transition model either for traning or action selection. \n",
       "- Disadvantage: The Q-learning agent has difficulty with sparse rewards since it has no means of looking into the future. \n",
       "6. SARSA, state, action, reward, state, action. The only difference with TD Q-learning update is that it uses Q-value of actually taken action instead of $\\max_{a'}Q$. \n",
       "- Q-learning is an <u>**off-policy**</u> learning algorithm, comparing Q-value with greedy policy (from now). \n",
       "- SARSA is an <u>**on-policy**</u> learning algorithm, comparing Q-value with original policy. \n",
       "\n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       "\n",
       "1. Approximate the true utility function (or Q-function) by weightede ($θ$) linear combination of feartures. \n",
       "$$U_θ(s) = Θ\\cdot F$$\n",
       "2. RL can generalize from its experiences because updating $θ_i$ will change values of $U_θ$ for **each** state. \n",
       "3. Linear function approximation: the utility (or Q) function must be linear in the features. \n",
       "4. TD learning problem 1: easily diverges with active learning and nonlinear functions. \n",
       "5. TD learning problem 2: catastrophic forgetting. Being in the safe place for a long time resulting in forgetting the dangerous place, \n",
       "since the value function becomes flat. Solution: experience replay. \n",
       "6. Solution 1 to sparse rewards (long action sequences): **reward shaping**. Gives the agent pseudorewards (addtional rewards) for making progress. \n",
       "7. Solution 2 to sparse rewards: HRL, hierarchical RL, begins with a partial program. \n",
       "Hierarchical structure of behavior provides an *additive decomposition* of the utility function. \n",
       "\n",
       "\n",
       "## Module 9 Lecture Notes\n",
       "\n",
       "1. MDP is offline planning (no need to actually **play** the game).RL is online learning. \n",
       "2. Model-based learning: step 1, learn empirical MDP model; step 2, solve the learned MDP. \n",
       "3. Problem with **direct evaluation**:\n",
       "- each state must be learned separately -> wastes information about state connections\n",
       "- takes a long time to learn\n",
       "4. Exponential moving average is one kind of TD learning. \n",
       "5. **Regret** is a measure of total mistake cost. \n",
       "6. Linear value (evaluation) function: able to be decomposed into linearly additive weights * features. \n",
       "\n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Bandit problem** - an MDP, state space given by Cartesian product\n",
       "* **Bernoulli bandit** - a bandit with reward 0/1 with a fixed probability\n",
       "* **Selection problem** - choosing the best option as quickly as possible with fixed cost of trials\n",
       "* **Bsp, bandit superprocess** - each arm is a Markov decision process\n",
       "* **Reinforcement learning** - an agent interacts with the world and periodically receives rewards\n",
       "* **Prioritized sweeping** - prefers to adjust states whose likely successors have just been made a lot adjustments\n",
       "* **Online learning algorithm** - updates the parameters after each trial\n",
       "* **Supervised learning** - learning a model for an (fully) observable environment\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "# Module 10 - Probabilities and Language Models"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
    "chapter12_1 = \"\"\"\n",
    "1. Logic inference fails for uncertainty problems because of: \n",
    "- Laziness: too hard to set rules without exceptions. \n",
    "- Theoretical ignorance: no complete theory to set rules. \n",
    "- Practical ignorance: even though rules are complete, information to make a judgement may not be available. \n",
    "2. An agent should prefer states with higher utility among all possible outcomes (i.e. specified states). \n",
    "\"\"\"\n",
    "chapter12_2 = \"\"\"\n",
    "Prior probability means unconditional probability. \n",
    "\"\"\"\n",
    "chapter12_3 = \"\"\"\n",
    "Marginalization (summing out) means *P(Y) = sum_z(Y, Z=z)*. \n",
    "\"\"\"\n",
    "chapter12_4 = \"\"\"\n",
    "Independence of probability. \n",
    "\"\"\"\n",
    "chapter12_5 = \"\"\"\n",
    "Conditional independence:\n",
    "$$P(X,Y|Z)=P(X|Z)P(Y|Z)$$\n",
    "\"\"\"\n",
    "chapter12_6 = \"\"\"\n",
    "1. **Naive Bayes model**:\n",
    "$$P(Cause,Effect_1,...,Effect_n)=P(Cause)Π_iP(Effect_i|Cause)$$\n",
    "To be rigorous, we should separate observed and unobserved effects. \n",
    "So LHS effects should be observed, and RHS should times a parameter α. \n",
    "2. Naive Bayes model assumes that words occur independently in documents. \n",
    "3. Dynamic Bayesian model needs: sensor model, transition model, prior distribution over state variables. \n",
    "\"\"\"\n",
    "chapter12_7 = \"\"\"\n",
    "Calculating probabilities for unobserved aspects of the world makes decisions of a (purely) logical agent more efficient. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
    "SLP_chapter3_1 = \"\"\"\n",
    "1. Using chain rule of probability, **k-gram** model computes the probability of a given word given previous text by\n",
    "$$P(w_n|w_{1:n-1}) = P(w_{n-k+1})P(w_{n-k+2}|w_{n-k})...P(w_n|w_{n-k+1:n-1})$$\n",
    "2. **Markov assumption**: the probability of a word depends only on the previous words (rather than the whole context). \n",
    "\"\"\"\n",
    "SLP_chapter3_2 = \"\"\"\n",
    "1. Extrinsic evaluation, embedding the model in an application, is the only way to know whether a particular improvement helps the task or not, though expensive. \n",
    "2. Intrinsic evaluation measures the quality of a model without application. We train the models on the training set (training corpus), \n",
    "and run them on the test set. The model that assigns a higher (the highest) probability to the test set is better (the best).\n",
    "3. Perplexity (for a test set $W$):\n",
    "$$PP(W)=\\sqrt[N]{Π_{i=1}^N{1\\over P(w_i|w_{1:i-1})}}$$\n",
    "e.g. for bigram model\n",
    "$$PP(W)=\\sqrt[N]{Π_{i=1}^N{1\\over P(w_i|w_{i-1})}}$$\n",
    "\"\"\"\n",
    "SLP_chapter3_3 = \"\"\"\n",
    "Sampling from a language model means to generate some sentences according to their likelihood defined by the model. \n",
    "\"\"\"\n",
    "SLP_chapter3_4 = \"\"\"\n",
    "1. Unknown words bring 2 problems: it means that we probably underestimate the probability of some words; \n",
    "we cannot compute perplexity when there is zero probability. \n",
    "\"\"\"\n",
    "SLP_chapter3_5 = \"\"\"\n",
    "1. **Laplace smoothing** (add-one smoothing):\n",
    "$$P_{Laplace}(w_i)={c_i+1\\over N+V}$$\n",
    "where $c_i$ is count of $w_i$, $N$ is total number of word tokens, and $V$ is the number of words in the vocabulary. \n",
    "The **adjusted count** \n",
    "$$c^*=(c_i+1){N\\over N+V}$$\n",
    "For bigram\n",
    "$$P_{Laplace}(w_n|w_{n-1})={C(w_{n-1}w_n)+1\\over C(w_{n-1})+V}$$\n",
    "Adjusted count\n",
    "$$c^*(w_{n-1}w_n)={[C(w_{n-1}w_n)+1]\\cdot C(w_{n-1}) \\over C(w_{n-1})+V}$$\n",
    "2. Add-k smoothing:\n",
    "$$P_{Laplace}(w_n|w_{n-1})={C(w_{n-1}w_n)+k\\over C(w_{n-1})+kV}$$\n",
    "3. Interpolation 插值:\n",
    "$$\\hat{P}(w_n|w_{n-1}w_{n-2})=λ_1P(w_n)+λ_2P(w_n|w_{n-1})+λ_3P(w_n|w_{n-2}w_{n-1})$$\n",
    "where sum of $λ_i=1$. \n",
    "4. Backoff n-gram model: if the n-gram has zero counts, approximate it by backing off to (n-1)-gram (repeat until it has non-zero counts). \n",
    "\"\"\"\n",
    "SLP_chapter3_7 = \"\"\"\n",
    "Stupid backoff: no discount for higher-order probabilities. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module10_lecture_notes = \"\"\"\n",
    "1. Goal of Probabilistic language models: assign a probability to a sentence. \n",
    "2. Unigram model uses no history; bigram model uses 1 word as history. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Each definition should be at most 25 words long.\n",
    "module10_definitions = {\n",
    "    \"decision theory\" : \"probability theory + utility theory\", \n",
    "    \"MEU\" : \"maximum expected utility\",\n",
    "    \"OOV rate\" : \"percentage of out-of-vocabulary words in the test set\",\n",
    "    \"held-out corpus\" : \"additional training corpus for setting hyperparameters (by MLE)\", \n",
    "    \"Markov property\" : \"given present, past and future are independent\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "4fdba22e-1975-4df0-bcfc-2e257d6bae8b",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       "\n",
       "1. Logic inference fails for uncertainty problems because of: \n",
       "- Laziness: too hard to set rules without exceptions. \n",
       "- Theoretical ignorance: no complete theory to set rules. \n",
       "- Practical ignorance: even though rules are complete, information to make a judgement may not be available. \n",
       "2. An agent should prefer states with higher utility among all possible outcomes (i.e. specified states). \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       "\n",
       "Prior probability means unconditional probability. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       "\n",
       "Marginalization (summing out) means *P(Y) = sum_z(Y, Z=z)*. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       "\n",
       "Independence of probability. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       "\n",
       "Conditional independence:\n",
       "$$P(X,Y|Z)=P(X|Z)P(Y|Z)$$\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       "\n",
       "1. **Naive Bayes model**:\n",
       "$$P(Cause,Effect_1,...,Effect_n)=P(Cause)Π_iP(Effect_i|Cause)$$\n",
       "To be rigorous, we should separate observed and unobserved effects. \n",
       "So LHS effects should be observed, and RHS should times a parameter α. \n",
       "2. Naive Bayes model assumes that words occur independently in documents. \n",
       "3. Dynamic Bayesian model needs: sensor model, transition model, prior distribution over state variables. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       "\n",
       "Calculating probabilities for unobserved aspects of the world makes decisions of a (purely) logical agent more efficient. \n",
       "\n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       "\n",
       "1. Using chain rule of probability, **k-gram** model computes the probability of a given word given previous text by\n",
       "$$P(w_n|w_{1:n-1}) = P(w_{n-k+1})P(w_{n-k+2}|w_{n-k})...P(w_n|w_{n-k+1:n-1})$$\n",
       "2. **Markov assumption**: the probability of a word depends only on the previous words (rather than the whole context). \n",
       "\n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       "\n",
       "1. Extrinsic evaluation, embedding the model in an application, is the only way to know whether a particular improvement helps the task or not, though expensive. \n",
       "2. Intrinsic evaluation measures the quality of a model without application. We train the models on the training set (training corpus), \n",
       "and run them on the test set. The model that assigns a higher (the highest) probability to the test set is better (the best).\n",
       "3. Perplexity (for a test set $W$):\n",
       "$$PP(W)=\\sqrt[N]{Π_{i=1}^N{1\\over P(w_i|w_{1:i-1})}}$$\n",
       "e.g. for bigram model\n",
       "$$PP(W)=\\sqrt[N]{Π_{i=1}^N{1\\over P(w_i|w_{i-1})}}$$\n",
       "\n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       "\n",
       "Sampling from a language model means to generate some sentences according to their likelihood defined by the model. \n",
       "\n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       "\n",
       "1. Unknown words bring 2 problems: it means that we probably underestimate the probability of some words; \n",
       "we cannot compute perplexity when there is zero probability. \n",
       "\n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       "\n",
       "1. **Laplace smoothing** (add-one smoothing):\n",
       "$$P_{Laplace}(w_i)={c_i+1\\over N+V}$$\n",
       "where $c_i$ is count of $w_i$, $N$ is total number of word tokens, and $V$ is the number of words in the vocabulary. \n",
       "The **adjusted count** \n",
       "$$c^*=(c_i+1){N\\over N+V}$$\n",
       "For bigram\n",
       "$$P_{Laplace}(w_n|w_{n-1})={C(w_{n-1}w_n)+1\\over C(w_{n-1})+V}$$\n",
       "Adjusted count\n",
       "$$c^*(w_{n-1}w_n)={[C(w_{n-1}w_n)+1]\\cdot C(w_{n-1}) \\over C(w_{n-1})+V}$$\n",
       "2. Add-k smoothing:\n",
       "$$P_{Laplace}(w_n|w_{n-1})={C(w_{n-1}w_n)+k\\over C(w_{n-1})+kV}$$\n",
       "3. Interpolation 插值:\n",
       "$$\\hat{P}(w_n|w_{n-1}w_{n-2})=λ_1P(w_n)+λ_2P(w_n|w_{n-1})+λ_3P(w_n|w_{n-2}w_{n-1})$$\n",
       "where sum of $λ_i=1$. \n",
       "4. Backoff n-gram model: if the n-gram has zero counts, approximate it by backing off to (n-1)-gram (repeat until it has non-zero counts). \n",
       "\n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       "\n",
       "Stupid backoff: no discount for higher-order probabilities. \n",
       "\n",
       "\n",
       "## Module 10 Lecture Notes\n",
       "\n",
       "1. Goal of Probabilistic language models: assign a probability to a sentence. \n",
       "2. Unigram model uses no history; bigram model uses 1 word as history. \n",
       "\n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Decision theory** - probability theory + utility theory\n",
       "* **Meu** - maximum expected utility\n",
       "* **Oov rate** - percentage of out-of-vocabulary words in the test set\n",
       "* **Held-out corpus** - additional training corpus for setting hyperparameters (by MLE)\n",
       "* **Markov property** - given present, past and future are independent\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "# Module 11 - Probabilistic Reasoning and Bayes’ Nets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
    "chapter13_1 = \"\"\"\n",
    "1. **Bayesian network** can represent any full joint probability distribution. \n",
    "2. Construct a Bayesian network:\n",
    "- Node $→$ random variable. \n",
    "- Directed edge from node X to Y, then X is a parent of Y. \n",
    "This intuitively means X directly influence Y. BN is acyclic. \n",
    "- Each node has associated probability information $θ(X_i|parents(X_i))$ that \n",
    "quantifies the effect of the parents on the node with finite number of parameters. \n",
    "- The above construction specifies conditional independence relationships in the domain. \n",
    "- Construction of BN over one joint distribution is not unique. \n",
    "\"\"\"\n",
    "chapter13_2 = \"\"\"\n",
    "1. $$P(x_1,...,x_n)=Π_{i=1}^n P(x_i|parents(X_i))$$\n",
    "2. Two ways to handle BN with continuous variables:\n",
    "- Discretization, dividing values into intervals. \n",
    "- Nonparametric representation, defining distribution with a collection of instances. \n",
    "\"\"\"\n",
    "chapter13_3 = \"\"\"\n",
    "1. Inference by enumeration (sum up products of conditional probabilities from BN)\n",
    "$$P(X|e)=αP(X,e)=α\\sum_y P(X,e,y)$$\n",
    "where $P(X,e,y)$ can be written as products of conditional probabilities (chain rule). \n",
    "2. Time complexity for BN with *n* Boolean variables is $O(2^n)$. \n",
    "3. Sparse (locally structured) systems grow linearly in complexity. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module11_lecture_notes = \"\"\"\n",
    "1. BN implicitly encode joint distributions. \n",
    "2. BN need not be causal. \n",
    "3. Size of an N-node net if nodes have up to *k* parents: $O(N\\cdot 2^{k+1})$.\n",
    "4. Notations of independence:\n",
    "- $X⊥Y$ (双竖线⊥) X and Y are independent. \n",
    "- $X⊥Y|Z$ (双竖线⊥) X and Y are conditionally independent given Z. \n",
    "5. If **no active paths** between node X and Y (given evidence variable(s) Z), they are (conditionally) independent. \n",
    "6. **Active triples** (if each triple is active, path is active)\n",
    "- Causal chain: $A→ B→ C$, B unobserved. \n",
    "- Common cause: $A\\gets B→ C$, B unobserved.\n",
    "- Common effect: $A→ B\\gets C$, B or one child of B is observed.\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module11_definitions = {\n",
    "    \"CPT\" : \"conditional probability table\", \n",
    "    \"stationary\" : \"CPT unchanged through time\",\n",
    "    \"syntax of BN\" : \"a directed acyclic graph + probability information attached to each node\",\n",
    "    \"hybrid BN\" : \"BN with both discrete and continuous variables\",\n",
    "    \"query variable\" : \"we care about\",\n",
    "    \"evidence variable\" : \"use as conditions\"\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 404
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "bb20c901-7476-453f-ca5d-5634317a6eef"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       "\n",
       "1. **Bayesian network** can represent any full joint probability distribution. \n",
       "2. Construct a Bayesian network:\n",
       "- Node $→$ random variable. \n",
       "- Directed edge from node X to Y, then X is a parent of Y. \n",
       "This intuitively means X directly influence Y. BN is acyclic. \n",
       "- Each node has associated probability information $θ(X_i|parents(X_i))$ that \n",
       "quantifies the effect of the parents on the node with finite number of parameters. \n",
       "- The above construction specifies conditional independence relationships in the domain. \n",
       "- Construction of BN over one joint distribution is not unique. \n",
       "\n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       "\n",
       "1. $$P(x_1,...,x_n)=Π_{i=1}^n P(x_i|parents(X_i))$$\n",
       "2. Two ways to handle BN with continuous variables:\n",
       "- Discretization, dividing values into intervals. \n",
       "- Nonparametric representation, defining distribution with a collection of instances. \n",
       "\n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       "\n",
       "1. Inference by enumeration (sum up products of conditional probabilities from BN)\n",
       "$$P(X|e)=αP(X,e)=α\\sum_y P(X,e,y)$$\n",
       "where $P(X,e,y)$ can be written as products of conditional probabilities (chain rule). \n",
       "2. Time complexity for BN with *n* Boolean variables is $O(2^n)$. \n",
       "3. Sparse (locally structured) systems grow linearly in complexity. \n",
       "\n",
       "\n",
       "## Module 11 Lecture Notes\n",
       "\n",
       "1. BN implicitly encode joint distributions. \n",
       "2. BN need not be causal. \n",
       "3. Size of an N-node net if nodes have up to *k* parents: $O(N\\cdot 2^{k+1})$.\n",
       "4. Notations of independence:\n",
       "- $X⊥Y$ (双竖线⊥) X and Y are independent. \n",
       "- $X⊥Y|Z$ (双竖线⊥) X and Y are conditionally independent given Z. \n",
       "5. If **no active paths** between node X and Y (given evidence variable(s) Z), they are (conditionally) independent. \n",
       "6. **Active triples** (if each triple is active, path is active)\n",
       "- Causal chain: $A→ B→ C$, B unobserved. \n",
       "- Common cause: $A\\gets B→ C$, B unobserved.\n",
       "- Common effect: $A→ B\\gets C$, B or one child of B is observed.\n",
       "\n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Cpt** - conditional probability table\n",
       "* **Stationary** - CPT unchanged through time\n",
       "* **Syntax of bn** - a directed acyclic graph + probability information attached to each node\n",
       "* **Hybrid bn** - BN with both discrete and continuous variables\n",
       "* **Query variable** - we care about\n",
       "* **Evidence variable** - use as conditions\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "# Module 12 - Naive Bayes and Perceptrons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
    "\n",
    "chapter19_1 = \"\"\"Your summary here \"\"\"\n",
    "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
    "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
    "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module12_lecture_notes = \"\"\"\n",
    "1. \"Naive\" because it **assumes** <u>that the features are conditionally independent of each other, given the class.</u>\n",
    "\n",
    "------------------------------------------------\n",
    "\n",
    "***Machine Learning***\n",
    "\n",
    "1. Goal of ML: acquire a model from data/experience. Learn parameters, structure, and/or hidden concepts. \n",
    "2. Model-based classification\n",
    "- Build a model (labels and features are random variables)\n",
    "- Instantiate observed features\n",
    "- Solve the distribution of the label conditional on features\n",
    "3. General naive Bayes model (values $|Y|\\cdot|F|^n$, parameters $n\\cdot|F|\\cdot|Y|$)\n",
    "$$P(Y,F_1,...,F_n)=P(Y)Π_i P(F_i|Y)$$\n",
    "4. Naive Bayes inference\n",
    "- Get joint probability of P(Y,f_1,...,f_n) for each label $Y=y_i$. \n",
    "- $P(y_i,f_1,...,f_n)=P(y_i)Π_k P(f_k|y_i)$\n",
    "- $P(f_1,...,f_n)=\\sum_i P(y_i)Π_k P(f_k|y_i)$\n",
    "- $P(Y|f_1,...,f_n)={P(y_i)Π_k P(f_k|y_i)\\over P(f_1,...,f_n)}$ for each $Y=y_i$\n",
    "5. Naive Bayes for text (**bag-of -words**)\n",
    "$$P(Y,W_1,...,W_n)=P(Y)Π_i P(W_i|Y)$$\n",
    "where $W_i$ is the word in the *i*th position. \n",
    "$P(Y)$ are prior. \n",
    "Conditional probabilities on the RHS come from training set. \n",
    "The model is insensitive to word order. \n",
    "6. Smoothing is used to generalize better. \n",
    "7. Parametric model has fixed number of parameters. \n",
    "\n",
    "------------------------------------------------\n",
    "\n",
    "***Perceptrons***\n",
    "\n",
    "1. **Activation** for linear classifier $ω\\cdot f(x)$ (vector product) is positive, then output is 1; o.w. output is 0. \n",
    "2. Training binary perceptron (to learn $ω$)\n",
    "- Predict $y$, if correct, no change in $ω$\n",
    "- If wrong, $ω+=y^*\\cdot f(x)$, **where $y^*$ is actual label**. \n",
    "3. Multiclass situation: a weight vector for each class. \n",
    "Predict $y=arg\\max_y ω_y\\cdot f(x)$.\n",
    "- Training, if correct, no change. \n",
    "- If wrong, $ω_y-=f(x)$ (lower for predicted), $ω_{y^*}+=f(x)$ (higher for actual).\n",
    "4. If the training set is linearly separable, perceptron will converge (binary case). \n",
    "5. MIRA: fix current mistake and minimize the change to $ω$. i.e. Solve\n",
    "$$\\min {1\\over 2}\\sum_y ||ω_y-ω'_y||^2$$\n",
    "given $ω_{y^*}\\cdot f(x) \\geq ω_y\\cdot f(x)+1$, here +1 helps to generalize. \n",
    "Here, $ω_y=ω'_y-τf(x),ω_{y^*}=ω'_{y^*}+τf(x)$. \n",
    "Solve τ\n",
    "$$τ={(ω'_y-ω'_{y^*})\\cdot f+1\\over 2f\\cdot f}$$\n",
    "6. **Support vector machine** find the optimal linear separator. \n",
    "In SVM model, only support vectors matter, while other training examples are ignorable. \n",
    "SVM is MIRA where you optimize over all examples at once.\n",
    "$$\\min {1\\over 2}\\sum_y ||ω_y||^2$$\n",
    "also given $ω_{y^*}\\cdot f(x) \\geq ω_y\\cdot f(x)+1$. \n",
    "7. Bias term: output = 0 if weights*features + bias <= 0. \n",
    "8. Decaying learning rate -> perceptron converges to minimum-error solution. \n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module12_definitions = {\n",
    "    \"XOR\" : \"异或, cannot be solved using linear separator\",\n",
    "    \"sigmoid function\":\"1/(1+exp(-x))\",\n",
    "    \"ReLU\" : \"0 if x<=0 else x\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "368045f0-506c-4710-91cc-280458a3b324",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "Your summary here \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       " Your summary here \n",
       "\n",
       "## Module 12 Lecture Notes\n",
       "\n",
       "1. \"Naive\" because it **assumes** <u>that the features are conditionally independent of each other, given the class.</u>\n",
       "\n",
       "------------------------------------------------\n",
       "\n",
       "***Machine Learning***\n",
       "\n",
       "1. Goal of ML: acquire a model from data/experience. Learn parameters, structure, and/or hidden concepts. \n",
       "2. Model-based classification\n",
       "- Build a model (labels and features are random variables)\n",
       "- Instantiate observed features\n",
       "- Solve the distribution of the label conditional on features\n",
       "3. General naive Bayes model (values $|Y|\\cdot|F|^n$, parameters $n\\cdot|F|\\cdot|Y|$)\n",
       "$$P(Y,F_1,...,F_n)=P(Y)Π_i P(F_i|Y)$$\n",
       "4. Naive Bayes inference\n",
       "- Get joint probability of P(Y,f_1,...,f_n) for each label $Y=y_i$. \n",
       "- $P(y_i,f_1,...,f_n)=P(y_i)Π_k P(f_k|y_i)$\n",
       "- $P(f_1,...,f_n)=\\sum_i P(y_i)Π_k P(f_k|y_i)$\n",
       "- $P(Y|f_1,...,f_n)={P(y_i)Π_k P(f_k|y_i)\\over P(f_1,...,f_n)}$ for each $Y=y_i$\n",
       "5. Naive Bayes for text (**bag-of -words**)\n",
       "$$P(Y,W_1,...,W_n)=P(Y)Π_i P(W_i|Y)$$\n",
       "where $W_i$ is the word in the *i*th position. \n",
       "$P(Y)$ are prior. \n",
       "Conditional probabilities on the RHS come from training set. \n",
       "The model is insensitive to word order. \n",
       "6. Smoothing is used to generalize better. \n",
       "7. Parametric model has fixed number of parameters. \n",
       "\n",
       "------------------------------------------------\n",
       "\n",
       "***Perceptrons***\n",
       "\n",
       "1. **Activation** for linear classifier $ω\\cdot f(x)$ (vector product) is positive, then output is 1; o.w. output is 0. \n",
       "2. Training binary perceptron (to learn $ω$)\n",
       "- Predict $y$, if correct, no change in $ω$\n",
       "- If wrong, $ω+=y^*\\cdot f(x)$, **where $y^*$ is actual label**. \n",
       "3. Multiclass situation: a weight vector for each class. \n",
       "Predict $y=arg\\max_y ω_y\\cdot f(x)$.\n",
       "- Training, if correct, no change. \n",
       "- If wrong, $ω_y-=f(x)$ (lower for predicted), $ω_{y^*}+=f(x)$ (higher for actual).\n",
       "4. If the training set is linearly separable, perceptron will converge (binary case). \n",
       "5. MIRA: fix current mistake and minimize the change to $ω$. i.e. Solve\n",
       "$$\\min {1\\over 2}\\sum_y ||ω_y-ω'_y||^2$$\n",
       "given $ω_{y^*}\\cdot f(x) \\geq ω_y\\cdot f(x)+1$, here +1 helps to generalize. \n",
       "Here, $ω_y=ω'_y-τf(x),ω_{y^*}=ω'_{y^*}+τf(x)$. \n",
       "Solve τ\n",
       "$$τ={(ω'_y-ω'_{y^*})\\cdot f+1\\over 2f\\cdot f}$$\n",
       "6. **Support vector machine** find the optimal linear separator. \n",
       "In SVM model, only support vectors matter, while other training examples are ignorable. \n",
       "SVM is MIRA where you optimize over all examples at once.\n",
       "$$\\min {1\\over 2}\\sum_y ||ω_y||^2$$\n",
       "also given $ω_{y^*}\\cdot f(x) \\geq ω_y\\cdot f(x)+1$. \n",
       "7. Bias term: output = 0 if weights*features + bias <= 0. \n",
       "8. Decaying learning rate -> perceptron converges to minimum-error solution. \n",
       "\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Xor** - 异或, cannot be solved using linear separator\n",
       "* **Sigmoid function** - 1/(1+exp(-x))\n",
       "* **Relu** - 0 if x<=0 else x\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "# Module 13 - Neural Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
    "\n",
    "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
    "\n",
    "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module13_lecture_notes = \"\"\"\n",
    "***Logistic Regression***\n",
    "1. Probability *P(y=1) = sigmoid($w\\cdot x+b$)*. \n",
    "2. Like perceptions, logistic regression also uses $w\\cdot x+b$, \n",
    "but adding the sigmoid transform (instead of outputting the linear result directly).\n",
    "2. **Cross-entropy loss**\n",
    "$$L_{CE}(\\hat{y},y)=-[y\\log{\\hat{y}}+(1-y)\\log{(1-\\hat{y})}]$$\n",
    "where $\\hat{y}=σ(w\\cdot x)+b$. \n",
    "3. **Gradient descent** is a method of minimizing a function by\n",
    "moving in the opposite direction of gradient. \n",
    "We use it to minimize the loss function and find the parameters. \n",
    "4. For logistic regression, the loss function we use is convex, so there is no local minimal to get stuck in. \n",
    "5. Gradient for logistic regression ${\\partial{L_{CE}(w,b)}\\over \\partial{w_j}} = [σ(w\\cdot x+b)-y]x_j$. \n",
    "i.e. Error in prediction times input value. \n",
    "6. **Stochastic gradient descent** (α is learning rate)\n",
    "```\n",
    "Repeat T times:\n",
    "    for each training example (x_i, y_i) (random order, not 1,2,..,n):\n",
    "        predict y\n",
    "        compute loss\n",
    "        compute the gradient of teh loss function\n",
    "        parameters <- parameters - α*gradient\n",
    "return parameters\n",
    "```\n",
    "7. Multinomial (multiclass) logistic regression uses softmax function ${e^{z_i}\\over \\sum_{j=1}^k e^{z_j}}$. \n",
    "\n",
    "------------------------------------------\n",
    "\n",
    "***Neural Networks***\n",
    "1. Neuron units apply a non-linear function, called **activation function**, \n",
    "to the linear output $w\\cdot x+b$. 3 common activation functions: *sigmoid*, *tanh*, *ReLU*. \n",
    "2. The simplest kind of NN is the *Feed-forward Neural Network Multilayer* network, \n",
    "where all units are fully-connected, no cycles. \n",
    "3. $w\\cdot x+b$ in each layer; activation after each layer (before next layer); softmax before output. \n",
    "4. **Computational graph** represents the process of computing a mathematical expression. \n",
    "5. With a computational graph, we can calculate the differentiation of output function with respect to the input variables using chain rule. \n",
    "6. Error back-propagation ensures us to correctly update all layers (o.w. only correct for the last layer). \n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module13_definitions = {\n",
    "    \"classifier\" : \"feature representation, classification function, objective function, optimizing the objective function\",\n",
    "    \"objective function\" : \"usually involves minimizing error on training examples\",\n",
    "    \"decision boundary\" : \"predict=1 if probability > decision boundary, 0 otherwise\",\n",
    "    \"batch training\" : \"computes gradient over the entire dataset\",\n",
    "    \"mini-batch training\" : \"train on a small batch\",\n",
    "    \"error propagation\" : \"a way of computing the gradient of the loss function\",\n",
    "    \"error propagation (specific)\" : \"error in random variable causes error in the function of it\"\n",
    "    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "0f2b5c93-aa8c-423d-df56-f6e338176ded",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       "\n",
       "***Logistic Regression***\n",
       "1. Probability *P(y=1) = sigmoid($w\\cdot x+b$)*. \n",
       "2. Like perceptions, logistic regression also uses $w\\cdot x+b$, \n",
       "but adding the sigmoid transform (instead of outputting the linear result directly).\n",
       "2. **Cross-entropy loss**\n",
       "$$L_{CE}(\\hat{y},y)=-[y\\log{\\hat{y}}+(1-y)\\log{(1-\\hat{y})}]$$\n",
       "where $\\hat{y}=σ(w\\cdot x)+b$. \n",
       "3. **Gradient descent** is a method of minimizing a function by\n",
       "moving in the opposite direction of gradient. \n",
       "We use it to minimize the loss function and find the parameters. \n",
       "4. For logistic regression, the loss function we use is convex, so there is no local minimal to get stuck in. \n",
       "5. Gradient for logistic regression ${\\partial{L_{CE}(w,b)}\\over \\partial{w_j}} = [σ(w\\cdot x+b)-y]x_j$. \n",
       "i.e. Error in prediction times input value. \n",
       "6. **Stochastic gradient descent** (α is learning rate)\n",
       "```\n",
       "Repeat T times:\n",
       "    for each training example (x_i, y_i) (random order, not 1,2,..,n):\n",
       "        predict y\n",
       "        compute loss\n",
       "        compute the gradient of teh loss function\n",
       "        parameters <- parameters - α*gradient\n",
       "return parameters\n",
       "```\n",
       "7. Multinomial (multiclass) logistic regression uses softmax function ${e^{z_i}\\over \\sum_{j=1}^k e^{z_j}}$. \n",
       "\n",
       "------------------------------------------\n",
       "\n",
       "***Neural Networks***\n",
       "1. Neuron units apply a non-linear function, called **activation function**, \n",
       "to the linear output $w\\cdot x+b$. 3 common activation functions: *sigmoid*, *tanh*, *ReLU*. \n",
       "2. The simplest kind of NN is the *Feed-forward Neural Network Multilayer* network, \n",
       "where all units are fully-connected, no cycles. \n",
       "3. $w\\cdot x+b$ in each layer; activation after each layer (before next layer); softmax before output. \n",
       "4. **Computational graph** represents the process of computing a mathematical expression. \n",
       "5. With a computational graph, we can calculate the differentiation of output function with respect to the input variables using chain rule. \n",
       "6. Error back-propagation ensures us to correctly update all layers (o.w. only correct for the last layer). \n",
       "\n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Classifier** - feature representation, classification function, objective function, optimizing the objective function\n",
       "* **Objective function** - usually involves minimizing error on training examples\n",
       "* **Decision boundary** - predict=1 if probability > decision boundary, 0 otherwise\n",
       "* **Batch training** - computes gradient over the entire dataset\n",
       "* **Mini-batch training** - train on a small batch\n",
       "* **Error propagation** - a way of computing the gradient of the loss function\n",
       "* **Error propagation (specific)** - error in random variable causes error in the function of it\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "# Module 14 - Natural Language Processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
    "\n",
    "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
    "\n",
    "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
    "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module14_lecture_notes = \"\"\"\n",
    "1. Neural language models, advantage over n-gram LMs (disadvantage: slower):\n",
    "- don't need smoothing\n",
    "- can handle much longer histories\n",
    "- can generalize over contexts of similar words\n",
    "- tend to have much higher predictive accuracy\n",
    "2. Each word is associated with an embedding vector. \n",
    "Word embedding project (using a V*M matrix) a word in vocabulary onto the whole context (much higher dimension). \n",
    "Word embedding can capture relational meaning in the language. \n",
    "3. Neural probabilistic LM learns $P(w_t|w_1,...,w_t)$, where $w_1,...,w_t \\in$ vocabulary. \n",
    "4. **Term-document matrix** (V*M) \n",
    "- document (column) vectors can be sparse\n",
    "- evaluate similarity of documents by comparing their vectors\n",
    "5. Comparison between words (row vector) uses **L2 (length) normalization (Euclidean distance)**. Divide the vector by\n",
    "$$||u||=\\sqrt{\\sum_{i=1}^n u^2_i}$$\n",
    "Additionally, cosine distance is computed by\n",
    "$$1-{u\\cdot v\\over ||u||||v||}$$\n",
    "6. Term-term matrix (term-context matrix). Value in cell (a,b) is the frequency of word b appears (in a context window) surrounding word a. \n",
    "7. Use TF-IDF instead of raw counts: term frequency (in a document) * inverse document frequency (1 over number of documents it occurred in)\n",
    "8. Train a classifier to get dense vectors, **skip-gram algorithm**\n",
    "- positive samples: target word and neighboring context\n",
    "- negative samples: random samples of other words in the lexicon\n",
    "- use logistic regression to train a classifier to distinguish +/-\n",
    "- use learned weights as the embeddings\n",
    "9. Goal of skip-gram: *P(+(or -)|target, context)*. \n",
    "Compute by dot product $t\\cdot c$? No (not a probability). \n",
    "Instead, use sigmoid\n",
    "$$ P(+|t,c)={1\\over 1+e^{-t\\cdot c}}, P(-|t,c)=1-P(+|t,c)$$\n",
    "for multiple context words, **assume** they are independent\n",
    "$$ P(+|t,c_{1:k})=Π_{i=1}^k{1\\over 1+e^{-t\\cdot c_i}}$$\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module14_definitions = {\n",
    "    \"curse of dimensionality\" : \"too many parameters to accurately estimate\",\n",
    "    \"reweighting models (examples)\" : \"L2 norm, TF-IDF, PPMI, probabilities\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 930
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "02418688-7f1b-4a12-ac5e-d695d2403e0f",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       "\n",
       "1. Neural language models, advantage over n-gram LMs (disadvantage: slower):\n",
       "- don't need smoothing\n",
       "- can handle much longer histories\n",
       "- can generalize over contexts of similar words\n",
       "- tend to have much higher predictive accuracy\n",
       "2. Each word is associated with an embedding vector. \n",
       "Word embedding project (using a V*M matrix) a word in vocabulary onto the whole context (much higher dimension). \n",
       "Word embedding can capture relational meaning in the language. \n",
       "3. Neural probabilistic LM learns $P(w_t|w_1,...,w_t)$, where $w_1,...,w_t \\in$ vocabulary. \n",
       "4. **Term-document matrix** (V*M) \n",
       "- document (column) vectors can be sparse\n",
       "- evaluate similarity of documents by comparing their vectors\n",
       "5. Comparison between words (row vector) uses **L2 (length) normalization (Euclidean distance)**. Divide the vector by\n",
       "$$||u||=\\sqrt{\\sum_{i=1}^n u^2_i}$$\n",
       "Additionally, cosine distance is computed by\n",
       "$$1-{u\\cdot v\\over ||u||||v||}$$\n",
       "6. Term-term matrix (term-context matrix). Value in cell (a,b) is the frequency of word b appears (in a context window) surrounding word a. \n",
       "7. Use TF-IDF instead of raw counts: term frequency (in a document) * inverse document frequency (1 over number of documents it occurred in)\n",
       "8. Train a classifier to get dense vectors, **skip-gram algorithm**\n",
       "- positive samples: target word and neighboring context\n",
       "- negative samples: random samples of other words in the lexicon\n",
       "- use logistic regression to train a classifier to distinguish +/-\n",
       "- use learned weights as the embeddings\n",
       "9. Goal of skip-gram: *P(+(or -)|target, context)*. \n",
       "Compute by dot product $t\\cdot c$? No (not a probability). \n",
       "Instead, use sigmoid\n",
       "$$ P(+|t,c)={1\\over 1+e^{-t\\cdot c}}, P(-|t,c)=1-P(+|t,c)$$\n",
       "for multiple context words, **assume** they are independent\n",
       "$$ P(+|t,c_{1:k})=Π_{i=1}^k{1\\over 1+e^{-t\\cdot c_i}}$$\n",
       "\n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Curse of dimensionality** - too many parameters to accurately estimate\n",
       "* **Reweighting models (examples)** - L2 norm, TF-IDF, PPMI, probabilities\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module14_sections = [\n",
    "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
    "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
    "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
    "\n",
    "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
    "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
    "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
    "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
    "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
    "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
    "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
    "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
    "  (\"Module 13 Lecture Notes\", 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))"
   ]
  },
  {
   "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",
   "execution_count": 102,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "T3cm1WV542_a",
    "outputId": "6743ab4e-1890-4e40-9844-ed00f9cf2612",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 8: Markov Decision Processes\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "1. MEU principle *formalize* \"rational agent should do 'the right thing'\" but doesn't *operationalize* that advice. \n",
       "2. The utility function applies to the very *next* state. \n",
       "\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "**Axioms** of utility\n",
       "\n",
       "1. Orderability: A>B or B>A or A~B\n",
       "2. Transitivity: A>B, B>C => A>C\n",
       "3. Continuity: A>B>C => $\\exists$ p, [p, A; 1-p, C] ~ B\n",
       "4. Substitutability: A~B => [p, A; 1-p, C] ~ [p, B; 1-p, C]\n",
       "5. Monotonicity: A>B => (p>q <=> [p, A; 1-p, B] > [q, A; 1-q, B])\n",
       "6. Decomposability: 数乘分配律 [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; 1-p, (1-p)q, B; (1-p)(1-q), C]\n",
       "\n",
       "**Existence**: if an agent's preferences obey axioms, $\\exists$ utility function. \n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "- Risk-averse: concave utility function. Prefer sure things. \n",
       "- Risk-seeking: convex utility function. \n",
       "- Risk-neutral: linear utility function. \n",
       "- Certainty equivalent: the (certain) value in lieu of a lottery. \n",
       "- Insurance premium:= expected value - certainty equivalent. **Same U, delta in x-axis (in graph).** Risk aversion suggests positive insurance premium. \n",
       "\n",
       "1. Decision theory is a normative theory. \n",
       "\n",
       "\n",
       "## AIMA Chapter 17.1 Sequential Decision Problems\n",
       "\n",
       "1. Methods for solving MDPs usually involve **dynamic programming** (recursively breaking the problem into smaller pieces and remembering the optimal solutions to the pieces). \n",
       "2. Infinite horizon just indicates that there is no **fixed** deadline (doesn't mean interminable). \n",
       "3. **Bellman equation** : $$U(s) = \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
       "4. **Q-function** (action-utility function): expected utility of taking a given action in a given state. $$Q(s,a) = \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
       "5. Shaping theorem: $\\Phi(s)$ is any function of state s, after the transformation $$R'(s,a,s') = R(s,a,s') + \\gamma\\Phi(s')-\\Phi(s)$$ the optimal policy won't change. \n",
       "\n",
       "\n",
       "## AIMA Chapter 17.2 Algorithms for MDPs\n",
       "\n",
       "1. ***Value Iteration***\n",
       "    \n",
       "    *n* Bellman equations for *n* unknown states (n utilities). Do Bellman update ($U = \\max_{a\\in A(s)}{Q}$ for each state)\n",
       "    $$ U_{i+1}(s) \\gets \\max_{a\\in A(s)} \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U_i(s')]$$\n",
       "    until $|U_{i+1}(s)-U_i(s)|\\leq\\epsilon(1-\\gamma)\\gamma$ for each state, where $\\epsilon$ is the maximum error of utility. \n",
       "\n",
       "\n",
       "2. ***Policy Iteration***\n",
       "\n",
       "    Policy valuation: calculate U **given** a policy $\\pi$. \n",
       "    \n",
       "    Policy improvement: calculate a new MEU policy ($a = argmax{Q}$ for each state). \n",
       "    \n",
       "    Repeat until no change in utilities. \n",
       "    \n",
       "    i.e. Solve simplified version of Bellman equation\n",
       "    $$ U_{i}(s) = \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$ (substitute $a$ by $\\pi_i(s)$). \n",
       "\n",
       "\n",
       "3. Modified Policy Iteration\n",
       "\n",
       "    Do simplified Bellman update for some number of times\n",
       "    $$ U_{i+1}(s) \\gets \\sum_{s'} P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$\n",
       "    \n",
       "\n",
       "4. Asynchronous Policy Iteration\n",
       "\n",
       "    Apply update (policy improvement or simplified value iteration) to subsets of states. \n",
       "    \n",
       "    \n",
       "5. Linear Programming\n",
       "\n",
       "    Minimize *U(s)* for all *s* s.t. for every state *s* and every action *a* $$U(s) \\geq \\sum_{s'} P(s'|s,a)[R(s,a,s')+\\gamma U(s')]$$\n",
       "\n",
       "\n",
       "## Module 8 Lecture Notes\n",
       "\n",
       "- MDP: set of states; set of actions; transition function; reward function; initial state(; terminal state(s))\n",
       "\n",
       "\n",
       "## Module 8 Definitions\n",
       "* **Meu** - maximum expected utility (rational agent)\n",
       "* **Value function / ordinal utility function** - only preferences ranking matters, the numbers don't matter\n",
       "* **Preference elicitation** - present the choices, and determine the utility fuinction by observed preferences\n",
       "* **Contraction** - operator that makes difference between estimates smaller\n",
       "* **Normalized utility** - worst = 0, best = 1\n",
       "* **Normative theory** - how should act\n",
       "* **Descriptive theory** - how acutally act\n",
       "* **Certainty effect** - people are attracted by certain gains\n",
       "* **Ambiguity aversion** - people prefer known probabilities\n",
       "* **Framing effect** - same probability, different statement => different actions\n",
       "* **Anchoring effect** - people prefer relative utility judgement\n",
       "* **Environment history** - a sequence of states and actions\n",
       "* **Policy (solution)** - specifies actions at each possibly reached state\n",
       "* **Finite horizon** - game is over after time N (fixed)\n",
       "* **Nonstationary policy** - depend on time\n",
       "* **Stationary policy** - depend only on current state (usually in games with infinite horizon)\n",
       "\n",
       "\n",
       "# Module 9: Reinforcement Learning\n",
       "## AIMA Chapter 17.3 Bandit Problems\n",
       "\n",
       "1. Tradeoff between **exploration** and **exploitation**. \n",
       "2. Arms are independent since the agent can work on only one arm at a time. \n",
       "3. Gittins index: an optimal strategy is indifferent between **(a)** running $M$ up to the best possible stopping time\n",
       "and then switch to $M_\\lambda$, and **(b)** running $M$ immediately. i.e.\n",
       "\n",
       "$$E[(\\sum^{T-1}_{t=0}\\gamma^tR_t)+\\sum^\\infty_{t=T}\\gamma^t\\lambda] = \\sum^\\infty_{t=0}\\gamma^t\\lambda $$\n",
       "\n",
       "i.e.\n",
       "$$\\lambda=\\max_{T>0} ({E(\\sum^{T-1}_{t=0}\\gamma^tR_t)}/{E(\\sum^{T-1}_{t=0}\\gamma^t)})$$\n",
       "\n",
       "\n",
       "## AIMA Chapter 22.1 Learning from Rewards\n",
       "\n",
       "1. The goals in MDP and RL are the same: maximizing the expected sum of rewards. However, in RL the MDP problem is learned but not given. \n",
       "2. **Model-based RL**: Learn the transition model or use the known transition model, and learn a utility function, to make decisions. \n",
       "3. **Model-free RL**: Neither learn or know the transition model.\n",
       "- **Q-learning / Action-utility learning** learns Q-functions. \n",
       "- **Policy search** learns the mapping from states to actions (reflex agent). \n",
       "\n",
       "\n",
       "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
       "\n",
       "1. **Passive RL**: policy fixed, the agent learns utilities of states. (similar to policy evaluation)\n",
       "2. Direct utility estimation: $U(s) = E(total-reward-from-next-state)$, reward-to-go. This ignores $U(next-state)$, so it converges slowly. \n",
       "3. Adaptive dynamic progamming (ADP): uses learned transition model and known rewards in the equation. \n",
       "Can use modified policy iteration. \n",
       "$$U_i(s) = \\sum_{s'}P(s'|s,\\pi_i(s))[R(s,\\pi_i(s),s')+\\gamma U_i(s')]$$\n",
       "4. Temporal-difference learning: $a$ is learning rate\n",
       "$$U^\\pi(s) \\gets U^\\pi(s) + a [R(s,\\pi(s),s')+\\gamma U^\\pi(s')-U^\\pi(s)]$$\n",
       "- If $a$ decreases as the number of times a state has been visited increases, $U^\\pi(s)$ will converge to the correct value. \n",
       "- TD updates don't need a transition model. \n",
       "5. Difference between ADP and DP: \n",
       "ADP adjusts a state to agree with *all* successors weighted by probabilities. \n",
       "TD adjusts a state to agree with *observed* successors (makes one adjustment per observed transition). \n",
       "TD can be viewed as an inaccurate but efficient approximation to ADP. \n",
       "6. Advantage of approximate ADP: the early learned transition model is often far from correct, \n",
       "so there is no need to calculate exact utility function to match it. \n",
       "7. Approximate ADP can use decreasing $a$ so that adjustments are gentler as transition model is more accurate. \n",
       "\n",
       "\n",
       "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
       "\n",
       "1. **Active RL**: the agent also learns the policy (satisfies Bellman equation). \n",
       "2. GLIE, greedy in the limit of infinite exploration: try each action in each state an unbounded number of times. \n",
       "This scheme guarantees that an ADP agent can eventually learn the true transition model and the true optimal policy.\n",
       "- An approach to implementing GLIE is to give some weight to actions that haven't been tried often. \n",
       "3. Approach 1, Bayesian RL: assumes a prior probability P(h) on hypothesis *h* about <u>what the true model is</u>. \n",
       "$$\\pi^* = arg\\max_\\pi \\sum_h P(h|observations)U^\\pi_h$$\n",
       "4. Approach 2, Robust control theory: doesn't assign probabilities to models. \n",
       "$$\\pi^* = arg\\max_\\pi\\min_h U_H^\\pi$$\n",
       "This is an **optimal robust policy** that gives best outcome in the worst case over H. \n",
       "5. Q-learning TD update (whenever action *a* is executed in state *s* leading to state *s'*):\n",
       "$$Q(s,a) \\gets Q(s,a)+α[R(s,a,s')+\\gamma\\max_{a'}Q(s',a')-Q(s,a)]$$\n",
       "- Advantage: A TD Q-learning agent **doesn't** need a transition model either for traning or action selection. \n",
       "- Disadvantage: The Q-learning agent has difficulty with sparse rewards since it has no means of looking into the future. \n",
       "6. SARSA, state, action, reward, state, action. The only difference with TD Q-learning update is that it uses Q-value of actually taken action instead of $\\max_{a'}Q$. \n",
       "- Q-learning is an <u>**off-policy**</u> learning algorithm, comparing Q-value with greedy policy (from now). \n",
       "- SARSA is an <u>**on-policy**</u> learning algorithm, comparing Q-value with original policy. \n",
       "\n",
       "\n",
       "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
       "\n",
       "1. Approximate the true utility function (or Q-function) by weightede ($θ$) linear combination of feartures. \n",
       "$$U_θ(s) = Θ\\cdot F$$\n",
       "2. RL can generalize from its experiences because updating $θ_i$ will change values of $U_θ$ for **each** state. \n",
       "3. Linear function approximation: the utility (or Q) function must be linear in the features. \n",
       "4. TD learning problem 1: easily diverges with active learning and nonlinear functions. \n",
       "5. TD learning problem 2: catastrophic forgetting. Being in the safe place for a long time resulting in forgetting the dangerous place, \n",
       "since the value function becomes flat. Solution: experience replay. \n",
       "6. Solution 1 to sparse rewards (long action sequences): **reward shaping**. Gives the agent pseudorewards (addtional rewards) for making progress. \n",
       "7. Solution 2 to sparse rewards: HRL, hierarchical RL, begins with a partial program. \n",
       "Hierarchical structure of behavior provides an *additive decomposition* of the utility function. \n",
       "\n",
       "\n",
       "## Module 9 Lecture Notes\n",
       "\n",
       "1. MDP is offline planning (no need to actually **play** the game).RL is online learning. \n",
       "2. Model-based learning: step 1, learn empirical MDP model; step 2, solve the learned MDP. \n",
       "3. Problem with **direct evaluation**:\n",
       "- each state must be learned separately -> wastes information about state connections\n",
       "- takes a long time to learn\n",
       "4. Exponential moving average is one kind of TD learning. \n",
       "5. **Regret** is a measure of total mistake cost. \n",
       "6. Linear value (evaluation) function: able to be decomposed into linearly additive weights * features. \n",
       "\n",
       "\n",
       "## Module 9 Definitions\n",
       "* **Bandit problem** - an MDP, state space given by Cartesian product\n",
       "* **Bernoulli bandit** - a bandit with reward 0/1 with a fixed probability\n",
       "* **Selection problem** - choosing the best option as quickly as possible with fixed cost of trials\n",
       "* **Bsp, bandit superprocess** - each arm is a Markov decision process\n",
       "* **Reinforcement learning** - an agent interacts with the world and periodically receives rewards\n",
       "* **Prioritized sweeping** - prefers to adjust states whose likely successors have just been made a lot adjustments\n",
       "* **Online learning algorithm** - updates the parameters after each trial\n",
       "* **Supervised learning** - learning a model for an (fully) observable environment\n",
       "\n",
       "\n",
       "# Module 10: Probabilies and Language Models\n",
       "## AIMA Chapter 12.1 Acting under Uncertainty\n",
       "\n",
       "1. Logic inference fails for uncertainty problems because of: \n",
       "- Laziness: too hard to set rules without exceptions. \n",
       "- Theoretical ignorance: no complete theory to set rules. \n",
       "- Practical ignorance: even though rules are complete, information to make a judgement may not be available. \n",
       "2. An agent should prefer states with higher utility among all possible outcomes (i.e. specified states). \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.2 Basic Probability Notation\n",
       "\n",
       "Prior probability means unconditional probability. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
       "\n",
       "Marginalization (summing out) means *P(Y) = sum_z(Y, Z=z)*. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.4 Independence\n",
       "\n",
       "Independence of probability. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
       "\n",
       "Conditional independence:\n",
       "$$P(X,Y|Z)=P(X|Z)P(Y|Z)$$\n",
       "\n",
       "\n",
       "## AIMA Chapter 12.6 Naive Bayes Models\n",
       "\n",
       "1. **Naive Bayes model**:\n",
       "$$P(Cause,Effect_1,...,Effect_n)=P(Cause)Π_iP(Effect_i|Cause)$$\n",
       "To be rigorous, we should separate observed and unobserved effects. \n",
       "So LHS effects should be observed, and RHS should times a parameter α. \n",
       "2. Naive Bayes model assumes that words occur independently in documents. \n",
       "\n",
       "\n",
       "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
       "\n",
       "Calculating probabilities for unobserved aspects of the world makes decisions of a (purely) logical agent more efficient. \n",
       "\n",
       "\n",
       "## SLP Chapter 3.1 N-Grams\n",
       "\n",
       "1. Using chain rule of probability, **k-gram** model computes the probability of a given word given previous text by\n",
       "$$P(w_n|w_{1:n-1}) = P(w_{n-k+1})P(w_{n-k+2}|w_{n-k})...P(w_n|w_{n-k+1:n-1})$$\n",
       "2. **Markov assumption**: the probability of a word depends only on the previous words (rather than the whole context). \n",
       "\n",
       "\n",
       "## SLP Chapter 3.2 Evaluating Language Models\n",
       "\n",
       "1. Extrinsic evaluation, embedding the model in an application, is the only way to know whether a particular improvement helps the task or not, though expensive. \n",
       "2. Intrinsic evaluation measures the quality of a model without application. We train the models on the training set (training corpus), \n",
       "and run them on the test set. The model that assigns a higher (the highest) probability to the test set is better (the best).\n",
       "3. Perplexity (for a test set $W$):\n",
       "$$PP(W)=\\sqrt[N]{Π_{i=1}^N{1\\over P(w_i|w_{1:i-1})}}$$\n",
       "e.g. for bigram model\n",
       "$$PP(W)=\\sqrt[N]{Π_{i=1}^N{1\\over P(w_i|w_{i-1})}}$$\n",
       "\n",
       "\n",
       "## SLP Chapter 3.3 Sampling sentences from a language model\n",
       "\n",
       "Sampling from a language model means to generate some sentences according to their likelihood defined by the model. \n",
       "\n",
       "\n",
       "## SLP Chapter 3.4 Generalization and Zeros\n",
       "\n",
       "1. Unknown words bring 2 problems: it means that we probably underestimate the probability of some words; \n",
       "we cannot compute perplexity when there is zero probability. \n",
       "\n",
       "\n",
       "## SLP Chapter 3.5 Smoothing\n",
       "\n",
       "1. **Laplace smoothing** (add-one smoothing):\n",
       "$$P_{Laplace}(w_i)={c_i+1\\over N+V}$$\n",
       "where $c_i$ is count of $w_i$, $N$ is total number of word tokens, and $V$ is the number of words in the vocabulary. \n",
       "The **adjusted count** \n",
       "$$c^*=(c_i+1){N\\over N+V}$$\n",
       "For bigram\n",
       "$$P_{Laplace}(w_n|w_{n-1})={C(w_{n-1}w_n)+1\\over C(w_{n-1})+V}$$\n",
       "Adjusted count\n",
       "$$c^*(w_{n-1}w_n)={[C(w_{n-1}w_n)+1]\\cdot C(w_{n-1}) \\over C(w_{n-1})+V}$$\n",
       "2. Add-k smoothing:\n",
       "$$P_{Laplace}(w_n|w_{n-1})={C(w_{n-1}w_n)+k\\over C(w_{n-1})+kV}$$\n",
       "3. Interpolation 插值:\n",
       "$$\\hat{P}(w_n|w_{n-1}w_{n-2})=λ_1P(w_n)+λ_2P(w_n|w_{n-1})+λ_3P(w_n|w_{n-2}w_{n-1})$$\n",
       "where sum of $λ_i=1$. \n",
       "4. Backoff n-gram model: if the n-gram has zero counts, approximate it by backing off to (n-1)-gram (repeat until it has non-zero counts). \n",
       "\n",
       "\n",
       "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
       "\n",
       "Stupid backoff: no discount for higher-order probabilities. \n",
       "\n",
       "\n",
       "## Module 10 Lecture Notes\n",
       "\n",
       "1. Goal of Probabilistic language models: assign a probability to a sentence. \n",
       "2. Unigram model uses no history; bigram model uses 1 word as history. \n",
       "\n",
       "\n",
       "## Module 10 Definitions\n",
       "* **Decision theory** - probability theory + utility theory\n",
       "* **Meu** - maximum expected utility\n",
       "* **Oov rate** - percentage of out-of-vocabulary words in the test set\n",
       "* **Held-out corpus** - additional training corpus for setting hyperparameters (by MLE)\n",
       "* **Markov property** - given present, past and future are independent\n",
       "\n",
       "\n",
       "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
       "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
       "\n",
       "1. **Bayesian network** can represent any full joint probability distribution. \n",
       "2. Construct a Bayesian network:\n",
       "- Node $→$ random variable. \n",
       "- Directed edge from node X to Y, then X is a parent of Y. \n",
       "This intuitively means X directly influence Y. BN is acyclic. \n",
       "- Each node has associated probability information $θ(X_i|parents(X_i))$ that \n",
       "quantifies the effect of the parents on the node with finite number of parameters. \n",
       "- The above construction specifies conditional independence relationships in the domain. \n",
       "\n",
       "\n",
       "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
       "\n",
       "1. $$P(x_1,...,x_n)=Π_{i=1}^n P(x_i|parents(X_i))$$\n",
       "2. Two ways to handle BN with continuous variables:\n",
       "- Discretization, dividing values into intervals. \n",
       "- Nonparametric representation, defining distribution with a collection of instances. \n",
       "\n",
       "\n",
       "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
       "\n",
       "1. Inference by enumeration (sum up products of conditional probabilities from BN)\n",
       "$$P(X|e)=αP(X,e)=α\\sum_y P(X,e,y)$$\n",
       "where $P(X,e,y)$ can be written as products of conditional probabilities (chain rule). \n",
       "2. Time complexity for BN with *n* Boolean variables is $O(2^n)$. \n",
       "\n",
       "\n",
       "## Module 11 Lecture Notes\n",
       "\n",
       "1. BN implicitly encode joint distributions. \n",
       "2. BN need not be causal. \n",
       "3. Size of an N-node net if nodes have up to *k* parents: $O(N\\cdot 2^{k+1})$.\n",
       "4. Notations of independence:\n",
       "- $X⊥Y$ (双竖线⊥) X and Y are independent. \n",
       "- $X⊥Y|Z$ (双竖线⊥) X and Y are conditionally independent given Z. \n",
       "5. If **no active paths** between node X and Y (given evidence variable(s) Z), they are (conditionally) independent. \n",
       "6. **Active triples** (if each triple is active, path is active)\n",
       "- Causal chain: $A→ B→ C$, B unobserved. \n",
       "- Common cause: $A\\gets B→ C$, B unobserved.\n",
       "- Common effect: $A→ B\\gets C$, B or one child of B is observed.\n",
       "\n",
       "\n",
       "## Module 11 Definitions\n",
       "* **Cpt** - conditional probability table\n",
       "* **Stationary** - CPT unchanged through time\n",
       "* **Syntax of bn** - a directed acyclic graph + probability information attached to each node\n",
       "* **Hybrid bn** - BN with both discrete and continuous variables\n",
       "* **Query variable** - we care about\n",
       "* **Evidence variable** - use as conditions\n",
       "\n",
       "\n",
       "# Module 12: Naive Bayes and Perceptrons\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "Your summary here \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.3 Worked Example\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.8 Test sets and Cross-validation\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.9 Statistical Significance Testing\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
       " Your summary here \n",
       "\n",
       "## Module 12 Lecture Notes\n",
       "\n",
       "1. \"Naive\" because it **assumes** <u>that the features are conditionally independent of each other, given the class.</u>\n",
       "\n",
       "------------------------------------------------\n",
       "\n",
       "***Machine Learning***\n",
       "\n",
       "1. Goal of ML: acquire a model from data/experience. Learn parameters, structure, and/or hidden concepts. \n",
       "2. Model-based classification\n",
       "- Build a model (labels and features are random variables)\n",
       "- Instantiate observed features\n",
       "- Solve the distribution of the label conditional on features\n",
       "3. General naive Bayes model (values $|Y|\\cdot|F|^n$, parameters $n\\cdot|F|\\cdot|Y|$)\n",
       "$$P(Y,F_1,...,F_n)=P(Y)Π_i P(F_i|Y)$$\n",
       "4. Naive Bayes inference\n",
       "- Get joint probability of P(Y,f_1,...,f_n) for each label $Y=y_i$. \n",
       "- $P(y_i,f_1,...,f_n)=P(y_i)Π_k P(f_k|y_i)$\n",
       "- $P(f_1,...,f_n)=\\sum_i P(y_i)Π_k P(f_k|y_i)$\n",
       "- $P(Y|f_1,...,f_n)={P(y_i)Π_k P(f_k|y_i)\\over P(f_1,...,f_n)}$ for each $Y=y_i$\n",
       "5. Naive Bayes for text (**bag-of -words**)\n",
       "$$P(Y,W_1,...,W_n)=P(Y)Π_i P(W_i|Y)$$\n",
       "where $W_i$ is the word in the *i*th position. \n",
       "$P(Y)$ are prior. \n",
       "Conditional probabilities on the RHS come from training set. \n",
       "The model is insensitive to word order. \n",
       "6. Smoothing is used to generalize better. \n",
       "\n",
       "------------------------------------------------\n",
       "\n",
       "***Perceptrons***\n",
       "\n",
       "1. Activation for linear classifier $ω\\cdot f(x)$ (vector product) is positive, then output is 1; o.w. output is -1. \n",
       "2. Training binary perceptron (to learn $ω$)\n",
       "- Predict $y$, if correct, no change in $ω$\n",
       "- If wrong, $ω+=y^*\\cdot f(x)$, **where $y^*$ is actual label**. \n",
       "3. Multiclass situation: a weight vector for each class. \n",
       "Predict $y=arg\\max_y ω_y\\cdot f(x)$.\n",
       "- Training, if correct, no change. \n",
       "- If wrong, $ω_y-=f(x)$ (lower for predicted), $ω_{y^*}+=f(x)$ (higher for actual).\n",
       "4. If the training set is linearly separable, perceptron will converge (binary case). \n",
       "5. MIRA: fix current mistake and minimize the change to $ω$. i.e. Solve\n",
       "$$\\min {1\\over 2}\\sum_y ||ω_y-ω'_y||^2$$\n",
       "given $ω_{y^*}\\cdot f(x) \\geq ω_y\\cdot f(x)+1$, here +1 helps to generalize. \n",
       "Here, $ω_y=ω'_y-τf(x),ω_{y^*}=ω'_{y^*}+τf(x)$. \n",
       "Solve τ\n",
       "$$τ={(ω'_y-ω'_{y^*})\\cdot f+1\\over 2f\\cdot f}$$\n",
       "6. **Support vector machine** find the optimal linear separator. \n",
       "In SVM model, only support vectors matter, while other training examples are ignorable. \n",
       "SVM is MIRA where you optimize over all examples at once.\n",
       "$$\\min {1\\over 2}\\sum_y ||ω_y||^2$$\n",
       "also given $ω_{y^*}\\cdot f(x) \\geq ω_y\\cdot f(x)+1$. \n",
       "7. Bias term: output = 0 if weights*features + bias <= 0. \n",
       "\n",
       "\n",
       "## Module 12 Definitions\n",
       "* **Xor** - 异或, cannot be solved using linear separator\n",
       "* **Sigmoid function** - 1/(1+exp(-x))\n",
       "* **Relu** - 0 if x<=0 else x\n",
       "\n",
       "\n",
       "# Module 13: Neural Networks\n",
       "## SLP Chapter 5.1 Classification: the sigmoid\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.2 Learning in Logistic Regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.3 The cross-entropy loss function\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.4 Gradient Descent\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.5 Regularization\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 5.6 Multinomial logistic regression\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.1 Units\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.2 The XOR problem\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.3 Feedforward Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.6 Training Neural Nets\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 7.7 Training the neural language model\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       "\n",
       "***Logistic Regression***\n",
       "1. Probability *P(y=1) = sigmoid($w\\cdot x+b$)*. \n",
       "2. Like perceptions, logistic regression also uses $w\\cdot x+b$, \n",
       "but adding the sigmoid transform (instead of outputting the linear result directly).\n",
       "2. **Cross-entropy loss**\n",
       "$$L_{CE}(\\hat{y},y)=-[y\\log{\\hat{y}}+(1-y)\\log{(1-\\hat{y})}]$$\n",
       "where $\\hat{y}=σ(w\\cdot x)+b$. \n",
       "3. **Gradient descent** is a method of minimizing a function by\n",
       "moving in the opposite direction of gradient. \n",
       "We use it to minimize the loss function and find the parameters. \n",
       "4. For logistic regression, the loss function we use is convex, so there is no local minimal to get stuck in. \n",
       "5. Gradient for logistic regression ${\\partial{L_{CE}(w,b)}\\over \\partial{w_j}} = [σ(w\\cdot x+b)-y]x_j$. \n",
       "i.e. Error in prediction times input value. \n",
       "6. **Stochastic gradient descent** (α is learning rate)\n",
       "```\n",
       "Repeat T times:\n",
       "    for each training example (x_i, y_i) (random order, not 1,2,..,n):\n",
       "        predict y\n",
       "        compute loss\n",
       "        compute the gradient of teh loss function\n",
       "        parameters <- parameters - α*gradient\n",
       "return parameters\n",
       "```\n",
       "7. Multinomial (multiclass) logistic regression uses softmax function ${e^{z_i}\\over \\sum_{j=1}^k e^{z_j}}$. \n",
       "\n",
       "------------------------------------------\n",
       "\n",
       "***Neural Networks***\n",
       "1. Neuron units apply a non-linear function, called **activation function**, \n",
       "to the linear output $w\\cdot x+b$. 3 common activation functions: *sigmoid*, *tanh*, *ReLU*. \n",
       "2. The simplest kind of NN is the *Feed-forward Neural Network Multilayer* network, \n",
       "where all units are fully-connected, no cycles. \n",
       "3. $w\\cdot x+b$ in each layer; activation after each layer (before next layer); softmax before output. \n",
       "4. **Computational graph** represents the process of computing a mathematical expression. \n",
       "5. With a computational graph, we can calculate the differentiation of output function with respect to the input variables using chain rule. \n",
       "\n",
       "\n",
       "## Module 13 Definitions\n",
       "* **Classifier** - feature representation, classification function, objective function, optimizing the objective function\n",
       "* **Objective function** - usually involves minimizing error on training examples\n",
       "* **Decision boundary** - predict=1 if probability > decision boundary, 0 otherwise\n",
       "* **Batch training** - computes gradient over the entire dataset\n",
       "* **Mini-batch training** - train on a small batch\n",
       "* **Error propagation** - a way of computing the gradient of the loss function\n",
       "* **Error propagation (specific)** - error in random variable causes error in the function of it\n",
       "\n",
       "\n",
       "# Module 14: Natural Language Processing\n",
       "## SLP Chapter 9.1 Language Models Revisited\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.2 Recurrent Neural Networks\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 9.3 RNNs as Language Models\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.1 Lexical Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.2 Vector Semantics\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.3 Words and Vectors\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.4 Cosine for measuring similarity\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.8 Word2vec\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.10 Semantic properties of embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.11 Bias and Embeddings\n",
       " Your summary here \n",
       "\n",
       "## SLP Chapter 6.12 Evaluating Vector Models\n",
       " Your summary here \n",
       "\n",
       "## Module 13 Lecture Notes\n",
       "\n",
       "***Logistic Regression***\n",
       "1. Probability *P(y=1) = sigmoid($w\\cdot x+b$)*. \n",
       "2. Like perceptions, logistic regression also uses $w\\cdot x+b$, \n",
       "but adding the sigmoid transform (instead of outputting the linear result directly).\n",
       "2. **Cross-entropy loss**\n",
       "$$L_{CE}(\\hat{y},y)=-[y\\log{\\hat{y}}+(1-y)\\log{(1-\\hat{y})}]$$\n",
       "where $\\hat{y}=σ(w\\cdot x)+b$. \n",
       "3. **Gradient descent** is a method of minimizing a function by\n",
       "moving in the opposite direction of gradient. \n",
       "We use it to minimize the loss function and find the parameters. \n",
       "4. For logistic regression, the loss function we use is convex, so there is no local minimal to get stuck in. \n",
       "5. Gradient for logistic regression ${\\partial{L_{CE}(w,b)}\\over \\partial{w_j}} = [σ(w\\cdot x+b)-y]x_j$. \n",
       "i.e. Error in prediction times input value. \n",
       "6. **Stochastic gradient descent** (α is learning rate)\n",
       "```\n",
       "Repeat T times:\n",
       "    for each training example (x_i, y_i) (random order, not 1,2,..,n):\n",
       "        predict y\n",
       "        compute loss\n",
       "        compute the gradient of teh loss function\n",
       "        parameters <- parameters - α*gradient\n",
       "return parameters\n",
       "```\n",
       "7. Multinomial (multiclass) logistic regression uses softmax function ${e^{z_i}\\over \\sum_{j=1}^k e^{z_j}}$. \n",
       "\n",
       "------------------------------------------\n",
       "\n",
       "***Neural Networks***\n",
       "1. Neuron units apply a non-linear function, called **activation function**, \n",
       "to the linear output $w\\cdot x+b$. 3 common activation functions: *sigmoid*, *tanh*, *ReLU*. \n",
       "2. The simplest kind of NN is the *Feed-forward Neural Network Multilayer* network, \n",
       "where all units are fully-connected, no cycles. \n",
       "3. $w\\cdot x+b$ in each layer; activation after each layer (before next layer); softmax before output. \n",
       "4. **Computational graph** represents the process of computing a mathematical expression. \n",
       "5. With a computational graph, we can calculate the differentiation of output function with respect to the input variables using chain rule. \n",
       "\n",
       "\n",
       "## Module 14 Definitions\n",
       "* **Curse of dimensionality** - too many parameters to accurately estimate\n",
       "* **Reweighting models (examples)** - L2 norm, TF-IDF, PPMI, probabilities\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Template_for CIS521_midterm_2_notes.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
