{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Nguyen_CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e89a7218-1f3d-405c-93e9-bd4bd4f62c24"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1fde28eb-f1df-4045-bb41-b786efe977a7"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "\n",
        "chapter16_1 = \"\"\" Agent assigns a probability to each possible current state $s$.\n",
        "The transition model $P(RESULT(a)=s') = \\sum_s P(s)P(s'|s,a)$ give the probability that action $a$ in state $s$ reaches arbitrary state $s'$.\n",
        "The __utility function__ $U(s)$ tells us the desirability of a state. __Expected utility__ is the average utility value of outcomes\n",
        "and the probability they occur.\n",
        "\n",
        "__Maximum expected utility (MEU)__ says a rational agent should choose an expected utility-maximizing action.\n",
        "The principle *formalize* the notion that agent should \"do the right thing\", NOT actually __operationalize__ t.\n",
        "Things like estimating a probability distribution over all possible states of the world requires \"perception, learning, representation, and inference.\"\n",
        "Computing $P(RESULT(a)=s')$ requires a __causal model__ of the world.\n",
        "\n",
        "Over a __history__, if an agents acts to maximize on a correct function $U(s)$,\n",
        "then agent will achieve the highest possible performance score (average over all possible environments).\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter16_2 =  \"\"\" But what makes MEU, the average, so special as part of the decision making proces?\n",
        "We can do some constraints on rational preferences:\n",
        "\n",
        "$A\\succ B$: A \\succeeds B means agent prefers A to B.\n",
        "\n",
        "$A\\sim B$: A \\similar to B means agent is indifferent.\n",
        "\n",
        "$A\\succeq B$: A \\succ or equal to B means agent prefers A over B or is indifferent.\n",
        "\n",
        "Set of outcomes for each action a \"lottery\": $L=[p_1, S_1; p_2, S2; ... p_n, S_n]$ of probabilities and States.\n",
        "Each outcome $S_i$ can be an atomic state or *another* lottery. Some properies:\n",
        "\n",
        "- Orderability: Agent must always decide between two lotteries. Cannot avoid deciding.\n",
        "Exactly one of $A\\succ B$, $B\\succ A$, or $A\\sim B$ holds.\n",
        "\n",
        "- Transitivity: If agent prefers A to B and B to C, then agent must prefer A to C: $(A\\succ B)\\wedge(B\\succ C)=> (A\\succ C)$.\n",
        "\n",
        "- Continuity: If lottery B is between A and C in preference, there is some probability $p$ for which agent will be indifferent between B\n",
        "and the lotery yielding A with probability $p$ and C with probability $1-p$.\n",
        "\n",
        "- Substitutability: If agent is indifferent between lotteries A and B, then agent is indifferent between two more complex lotteries\n",
        "that are the same except that B is substituted for A. Holds REGARDLESS of the probabilites and lottery outcomes.\n",
        "\n",
        "- Monotonicity: Suppose two lotteries have __same__ two possible outcomes A and B.\n",
        "If agents prefers A to B, then agent must prefer lottery with higher probability!\n",
        "\n",
        "- Decomposability: Compound lotteries can be reduced/compressed to simpler ones using laws of probability.\n",
        "\"No fun in gambling\" rule is an example. \n",
        "\n",
        "These are the __axioms__ of utility theory (but really preferences as they say nothing about utility function).\n",
        "From these, we can derive __theorems__, which will establish that a utility function __exists__ for ANY rational agent.\n",
        "Does not establish that it is *unique*.\n",
        "\n",
        "Utility function does not change it gets transformed like this: $U'(S)=aU(S)+b$, where $a$ and $b$ are constants and $a$ is positive.\n",
        "\n",
        "In a game-play and deterministic environment, agent needs only a preferences __ranking__ on states, meaning numbers don't matter!\n",
        "This is called a __value function__ or __ordinal utility function__. Agent's preference behavior does not mean\n",
        "agent is *explicitly* maximizing utility function in choosing.\n",
        "\n",
        "Rational behavior can be generated a number of ways and can be implemented with table lookup (with small number of possible states).\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\" \n",
        "Utility functions map from lotteries to real numbers\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "Transition model is __stochastic__ and transitions are __Markovian__, meaning the probability of reaching $s'$ from $s$ depends only\n",
        "on $s$ and NOT on earlier states. Since decisions are sequential, utility function depend on *specific* sequence of states and actions called an __environment history__.\n",
        "NOT on a single state. For every transition, agent receives a __reward__ by $R(s, a, s')$.\n",
        "\n",
        "If 9 state of -0.04 and 1 state of +1, then reward is (9*-0.04)+1 = 0.64.\n",
        "\n",
        "Markov Decision process consists of: set of states (init state $s_0$), set of ACTIONS, a transition model $P(s'|s,a)$ and reward function $R(s,a,s')$.\n",
        "Usually involves __dynamic programming__ (recursively breaking problem into smaller pieces and remembering optimal solutions to the pieces).\n",
        "\n",
        "Since sequential, solution must specify moves agent should do to reach any given state.\n",
        "\n",
        "Quality of policy is measured by expected utility of possible environment histories generated by the policy.\n",
        "__Optimal utility__, $\\pi^*$, yields highest expected utility. Agent consults current percept and executes action $pi^*(s)$.\n",
        "Policy represenst a \"simple relfex\" agent.\n",
        "\n",
        "There are often multiple optimal policies. In examples where agent is indifferent about going left or going right.\n",
        "\n",
        "Utilities over time: utility function on environment histories described as $U_h([s_0, a_0, s_1, a_1, ..., s_{N+k}])$, where $s_i$ is state and $a_i$ is action.\n",
        "__Finite horizon vs. infinite horizon__: In a fixed time $N$, the game ends after a $N$ iterations.\n",
        "This limits what the agent can do - whether or not there is plenty of time to explore before going to the end state.\n",
        "Time-dependent policies are called __nonstationary__. With no time limit, no reason to behave differently in same state at different times.\n",
        "\n",
        "__Additive discounted rewards__: Discount factor $\\gamma$ is a number between 0 (less significant) and 1 (more significant) to rewards at each state.\n",
        "\n",
        "$U_h=R(s_0,a_0,s_1)+\\gamma\\cdot R(s_1,a_1,s_2)+\\gamma^2 \\cdot R(s_2,a_2,s_3) + ...$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter17_2 =  \"\"\"\n",
        "Bellman equation is basis for __value iteration__ alogirthm to solve MDPs. For $n$ possible states, there are $n$ Bellman equations.\n",
        "\n",
        "Possible to solve with __linear programming__.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "21b0233b-9146-48f4-c88d-195ea937b22c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent assigns a probability to each possible current state $s$.\nThe transition model $P(RESULT(a)=s') = \\sum_s P(s)P(s'|s,a)$ give the probability that action $a$ in state $s$ reaches arbitrary state $s'$.\nThe __utility function__ $U(s)$ tells us the desirability of a state. __Expected utility__ is the average utility value of outcomes\nand the probability they occur.\n\n__Maximum expected utility (MEU)__ says a rational agent should choose an expected utility-maximizing action.\nThe principle *formalize* the notion that agent should \"do the right thing\", NOT actually __operationalize__ t.\nThings like estimating a probability distribution over all possible states of the world requires \"perception, learning, representation, and inference.\"\nComputing $P(RESULT(a)=s')$ requires a __causal model__ of the world.\n\nOver a __history__, if an agents acts to maximize on a correct function $U(s)$,\nthen agent will achieve the highest possible performance score (average over all possible environments).\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n But what makes MEU, the average, so special as part of the decision making proces?\nWe can do some constraints on rational preferences:\n\n$A\\succ B$: A \\succeeds B means agent prefers A to B.\n\n$A\\sim B$: A \\similar to B means agent is indifferent.\n\n$A\\succeq B$: A \\succ or equal to B means agent prefers A over B or is indifferent.\n\nSet of outcomes for each action a \"lottery\": $L=[p_1, S_1; p_2, S2; ... p_n, S_n]$ of probabilities and States.\nEach outcome $S_i$ can be an atomic state or *another* lottery. Some properies:\n\n- Orderability: Agent must always decide between two lotteries. Cannot avoid deciding.\nExactly one of $A\\succ B$, $B\\succ A$, or $A\\sim B$ holds.\n\n- Transitivity: If agent prefers A to B and B to C, then agent must prefer A to C: $(A\\succ B)\\wedge(B\\succ C)=> (A\\succ C)$.\n\n- Continuity: If lottery B is between A and C in preference, there is some probability $p$ for which agent will be indifferent between B\nand the lotery yielding A with probability $p$ and C with probability $1-p$.\n\n- Substitutability: If agent is indifferent between lotteries A and B, then agent is indifferent between two more complex lotteries\nthat are the same except that B is substituted for A. Holds REGARDLESS of the probabilites and lottery outcomes.\n\n- Monotonicity: Suppose two lotteries have __same__ two possible outcomes A and B.\nIf agents prefers A to B, then agent must prefer lottery with higher probability!\n\n- Decomposability: Compound lotteries can be reduced/compressed to simpler ones using laws of probability.\n\"No fun in gambling\" rule is an example. \n\nThese are the __axioms__ of utility theory (but really preferences as they say nothing about utility function).\nFrom these, we can derive __theorems__, which will establish that a utility function __exists__ for ANY rational agent.\nDoes not establish that it is *unique*.\n\nUtility function does not change it gets transformed like this: $U'(S)=aU(S)+b$, where $a$ and $b$ are constants and $a$ is positive.\n\nIn a game-play and deterministic environment, agent needs only a preferences __ranking__ on states, meaning numbers don't matter!\nThis is called a __value function__ or __ordinal utility function__. Agent's preference behavior does not mean\nagent is *explicitly* maximizing utility function in choosing.\n\nRational behavior can be generated a number of ways and can be implemented with table lookup (with small number of possible states).\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nUtility functions map from lotteries to real numbers\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nTransition model is __stochastic__ and transitions are __Markovian__, meaning the probability of reaching $s'$ from $s$ depends only\non $s$ and NOT on earlier states. Since decisions are sequential, utility function depend on *specific* sequence of states and actions called an __environment history__.\nNOT on a single state. For every transition, agent receives a __reward__ by $R(s, a, s')$.\n\nIf 9 state of -0.04 and 1 state of +1, then reward is (9*-0.04)+1 = 0.64.\n\nMarkov Decision process consists of: set of states (init state $s_0$), set of ACTIONS, a transition model $P(s'|s,a)$ and reward function $R(s,a,s')$.\nUsually involves __dynamic programming__ (recursively breaking problem into smaller pieces and remembering optimal solutions to the pieces).\n\nSince sequential, solution must specify moves agent should do to reach any given state.\n\nQuality of policy is measured by expected utility of possible environment histories generated by the policy.\n__Optimal utility__, $\\pi^*$, yields highest expected utility. Agent consults current percept and executes action $pi^*(s)$.\nPolicy represenst a \"simple relfex\" agent.\n\nThere are often multiple optimal policies. In examples where agent is indifferent about going left or going right.\n\nUtilities over time: utility function on environment histories described as $U_h([s_0, a_0, s_1, a_1, ..., s_{N+k}])$, where $s_i$ is state and $a_i$ is action.\n__Finite horizon vs. infinite horizon__: In a fixed time $N$, the game ends after a $N$ iterations.\nThis limits what the agent can do - whether or not there is plenty of time to explore before going to the end state.\nTime-dependent policies are called __nonstationary__. With no time limit, no reason to behave differently in same state at different times.\n\n__Additive discounted rewards__: Discount factor $\\gamma$ is a number between 0 (less significant) and 1 (more significant) to rewards at each state.\n\n$U_h=R(s_0,a_0,s_1)+\\gamma\\cdot R(s_1,a_1,s_2)+\\gamma^2 \\cdot R(s_2,a_2,s_3) + ...$\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nBellman equation is basis for __value iteration__ alogirthm to solve MDPs. For $n$ possible states, there are $n$ Bellman equations.\n\nPossible to solve with __linear programming__.\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 546
        },
        "cellView": "form",
        "outputId": "2cad3185-d16a-418d-e1d9-5c8be9199dc4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \n",
        "To make choices, agent must have __preferences__ among different possible outcomes.\n",
        "\n",
        "Decision theory = Probability theory + utility theory\n",
        "\n",
        "Fundamental idea of decision theory is that agent acts by MEU.\n",
        "\"\"\"\n",
        "\n",
        "chapter12_2 = \"\"\"\n",
        "Set of all possible worlds is called the __sample space__, where words are mutually exlcusive exhaustive.\n",
        "A probability model associates numerical probability with each possible world.\n",
        "\n",
        "$\\sum_{w\\in\\Omega}P(w)=1$ where $w$ is a world. Can also be something like a proposition.\n",
        "\n",
        "Probabilities when rolling dice such as $P(Total=11)$ are called unconditional or prior probs.\n",
        "They refer to degrees of \"belief\" in a proposition without needing *any* other information.\n",
        "But we usually have evidence, so __conditional/posterior__ probability is more applicable.\n",
        "\n",
        "Example: When going to dentist, $P(cavity)=0.2$ might be of interest. But if toothache, then $P(cavity|toothache)$ is the one that matters.\n",
        "Conditional probability can be derived from __product rule__: $P(a\\wedge b)=P(a|b)\\cdot P(b)$.\n",
        "\n",
        "In probability, variables are called __random variables__. Every RV is a function that maps domain of possible worlds $\\Omega$ to some __range__.\n",
        "In dice, $Total$ is an rv. range is $\\{1,2,3,4,5,6\\}$. In a Boolean rv, range can be {True, False} making a $Bernoulli$ distribution.\n",
        "\n",
        "Inclusion-exclusion principle: $P(a\\wedge) = P(a)+P(b)-P(a\\wedge b)$.\n",
        "\"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "Axioms of probabilit constrain probabilities of logically related propositions. An agent that violates the axioms *must* behave irrationally.\n",
        "\n",
        "It is tough to get a __full joint probability distribution__ in the real world since it is often too large.\n",
        "However, when we have the probability of each complete value assingments to rv, we should use it!\n",
        "\n",
        "__Absolute independence__ betwen rvs allows the full joint distribution to be factored into smaller joint distribtutions, greatly reducing its complexity.\n",
        "\"\"\"\n",
        "\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "chapter12_6 = \"\"\"\n",
        "Formula for __naive Bayes__ model:\n",
        "\n",
        "$P(Cause, Effect_1,..., Effect_n)=P(Cause)\\prod_i P(Effect_i|Cause)$\n",
        "\n",
        "It is \"naive\" because it over simplifies independence even though the \"effect\" variables might not be *strictly* independent.\n",
        "Very appropriate for $text classification$ tasks.\n",
        "\"\"\"\n",
        "\n",
        "chapter12_7 = \"\"\"\n",
        "Wumpus-world agent can calculate probabilites for unobserved aspects of the world to improve decision making with __conditional independence__.\n",
        "\n",
        "Example: Wumpus knows that a pit causes breezes in neighboring squares and each square other than [1, 1] constains pit with probability 0.2.\n",
        "He can compute 2 random variables, 1) Whether or not square is a pit and 2) If square is breezy.\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 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\"\n",
        "Perplexity as evaluation method. The higher the conditional probability of a word sequence, the lower the perplexity.\n",
        "Minimizing perplexity is equivalent to maximizing the test set probability.\n",
        "\n",
        "$PP(W) = P(w_1 \\cdot w_2...w_N)^\\frac{-1}{N}$\n",
        "\n",
        "The more information the n-gram gives us about a word sequence (a sentence), the lower the perplexity (so the lower the better).\n",
        "Higher values indicate the input was “perplexing” from the model’s point of view, hence the term perplexity.\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_3 = \"\"\"\n",
        "N-gram model is very dependent on training corpus.\n",
        "\n",
        "Unknowne words are called __out of vocabulary (OOV)__ words. In an \"open vocabulary\" system, OOV words are modeled as <UNK>.\n",
        "\"\"\"\n",
        "\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "Smoothing is used to prevent a language model from assigning zero probabilities to unseen words.\n",
        "We \"shave off a bit of probability mass from some frequent events and give it to events we have never seen.\"\n",
        "\n",
        "Laplace, Add-k smoothing, Backoff & Interpolation.\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"factored representation\" : \"possible world represented by set of variable/value pairs\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0xEQXnWpuaPd"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "a2fcceb4-c6ba-4d59-bc1d-545b17b51307"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \nTo make choices, agent must have __preferences__ among different possible outcomes.\n\nDecision theory = Probability theory + utility theory\n\nFundamental idea of decision theory is that agent acts by MEU.\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\nSet of all possible worlds is called the __sample space__, where words are mutually exlcusive exhaustive.\nA probability model associates numerical probability with each possible world.\n\n$\\sum_{w\\in\\Omega}P(w)=1$ where $w$ is a world. Can also be something like a proposition.\n\nProbabilities when rolling dice such as $P(Total=11)$ are called unconditional or prior probs.\nThey refer to degrees of \"belief\" in a proposition without needing *any* other information.\nBut we usually have evidence, so __conditional/posterior__ probability is more applicable.\n\nExample: When going to dentist, $P(cavity)=0.2$ might be of interest. But if toothache, then $P(cavity|toothache)$ is the one that matters.\nConditional probability can be derived from __product rule__: $P(a\\wedge b)=P(a|b)\\cdot P(b)$.\n\nIn probability, variables are called __random variables__. Every RV is a function that maps domain of possible worlds $\\Omega$ to some __range__.\nIn dice, $Total$ is an rv. range is $\\{1,2,3,4,5,6\\}$. In a Boolean rv, range can be {True, False} making a $Bernoulli$ distribution.\n\nInclusion-exclusion principle: $P(a\\wedge) = P(a)+P(b)-P(a\\wedge b)$.\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\nAxioms of probabilit constrain probabilities of logically related propositions. An agent that violates the axioms *must* behave irrationally.\n\nIt is tough to get a __full joint probability distribution__ in the real world since it is often too large.\nHowever, when we have the probability of each complete value assingments to rv, we should use it!\n\n__Absolute independence__ betwen rvs allows the full joint distribution to be factored into smaller joint distribtutions, greatly reducing its complexity.\n\n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n\nFormula for __naive Bayes__ model:\n\n$P(Cause, Effect_1,..., Effect_n)=P(Cause)\\prod_i P(Effect_i|Cause)$\n\nIt is \"naive\" because it over simplifies independence even though the \"effect\" variables might not be *strictly* independent.\nVery appropriate for $text classification$ tasks.\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\nWumpus-world agent can calculate probabilites for unobserved aspects of the world to improve decision making with __conditional independence__.\n\nExample: Wumpus knows that a pit causes breezes in neighboring squares and each square other than [1, 1] constains pit with probability 0.2.\nHe can compute 2 random variables, 1) Whether or not square is a pit and 2) If square is breezy.\n\n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n\nPerplexity as evaluation method. The higher the conditional probability of a word sequence, the lower the perplexity.\nMinimizing perplexity is equivalent to maximizing the test set probability.\n\n$PP(W) = P(w_1 \\cdot w_2...w_N)^\frac{-1}{N}$\n\nThe more information the n-gram gives us about a word sequence (a sentence), the lower the perplexity (so the lower the better).\nHigher values indicate the input was “perplexing” from the model’s point of view, hence the term perplexity.\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\nN-gram model is very dependent on training corpus.\n\nUnknowne words are called __out of vocabulary (OOV)__ words. In an \"open vocabulary\" system, OOV words are modeled as <UNK>.\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\nSmoothing is used to prevent a language model from assigning zero probabilities to unseen words.\nWe \"shave off a bit of probability mass from some frequent events and give it to events we have never seen.\"\n\nLaplace, Add-k smoothing, Backoff & Interpolation.\n\n\n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Factored representation** - possible world represented by set of variable/value pairs\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "Independence and conditional independence relationships among variables can reduce __significantly__ the number of probabilities\n",
        "that need to be specified to achieve the full joint distribution.\n",
        "\n",
        "__Bayesian network__ can be used to represent dependencies among variables.\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 453
        },
        "cellView": "form",
        "outputId": "20dae15a-6a73-467e-dbc1-8cac4ec3aadc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\nIndependence and conditional independence relationships among variables can reduce __significantly__ the number of probabilities\nthat need to be specified to achieve the full joint distribution.\n\n__Bayesian network__ can be used to represent dependencies among variables.\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"\n",
        "Multinomial Naive Bayes classifier makes simplifying assumption about features' independence.\n",
        "In the classifier, document is represented as a __bag-of-words__, an unordered set of words with their position __ignore__.\n",
        "Example: the word \"me\" would be recorded as appearing 5 times, \"you\" 6 times, etc.\n",
        "\n",
        "Step 1: Determine vocabulary from training corpus. \n",
        "\n",
        "Step 2: Estimate $P(c_j)$ and P(x)k|c_j), where the first is number of documents in topic $c$ divided by total number of documents.\n",
        "The latter is number of docs of topic j containing word $x_k$ over Total number of docs of topic j.\n",
        "\n",
        "For all word $x_i$ in current document, return class $C$ from quation: ${c_hat} = argmax (P(c|d))$, where $d$ is document, and $c\\in C$ is all classes such that the classifer return class c_hat (estimate of the correct class).\n",
        "Class $c$ can be \"positive\" or \"negative\".\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_2 = \"\"\"\n",
        "In sentiment classification, we concatenate all documents with category $c$ of interest into one *big* text.\n",
        "We then use frequency of $w_i$ to give a maximum likelihood of the probability:\n",
        "\n",
        "${P_hat}(w_i|c) = \\frac{count (w_i, c)}{\\sum_{w\\in V}count(w,c)}$\n",
        "\n",
        "Probalem: When we try estimate the likelihood of \"fantastic\" given the class *positive*, but no positive class training doc contains the word.\n",
        "Probability would then be 0. Solution: We can do add-one smoothing to improve the count.\n",
        "\n",
        "In sentiment classification, we also remove *unknown* words.\n",
        "\n",
        "Naive Bayes with binarized features seem to work better for many text-classification tasks!!\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\"\n",
        "Contingency table helps identify Precision, Recall, and Accuracy.\n",
        "In spam detection, true positives mean detecting spam and actually get spam. False negatives means detecting non-spam but actually spam.\n",
        "\n",
        "Accuracy is the percentage of predicting the right class for all documents.\n",
        "BUT, this does not work well when classes are unbalanced. So we care about Precision and Recall.\n",
        "\n",
        "Precision: when system detects spam, what percentage is actually spam.\n",
        "\n",
        "${Precision} = \\\\frac{\\\\text{true positives}}{\\\\text{true positives + false positives}}$\n",
        "\n",
        "Recall: what percentage of items in the input that system actually correctly predict.\n",
        "\n",
        "$Recall=\\\\frac{\\\\text{true positives}}{\\\\text{true positives + false negatives}}$\n",
        "\n",
        "The higher the both of these, the better! In example, high recall means the model is correctly detecting the spams (true positives) with a high percentage. __F-1__ score is a harmony between the two.\n",
        "\n",
        "In multi-label classification, the contingency table's is called a __confusion matrix__.\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_8 = \"\"\"\n",
        "Training test set is used to train model. Development test set is used to tune parameters. Devset helps avoid overfitting.\n",
        "\n",
        "In order to save lots of data for training, devset might not be large enough to be representative. We would like to utilize __all__ data for both training and test.\n",
        "Solution: __Cross validation__ means __randomly__ choosing a training and test set divsion of the data, then compute error rate on test set.\n",
        "\n",
        "For example, we can do this 10 times and average the errors of the 10 runs, called it \"10-fold cross-validation\".\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"gold labels\" : \"human-identified standard labels\",\n",
        "\"contingency labels\": \"table of 4 cells of true/false and positive/negative\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8f4a92ea-d12d-4703-bd1a-c63e055f58be"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\nMultinomial Naive Bayes classifier makes simplifying assumption about features' independence.\nIn the classifier, document is represented as a __bag-of-words__, an unordered set of words with their position __ignore__.\nExample: the word \"me\" would be recorded as appearing 5 times, \"you\" 6 times, etc.\n\n${c_hat} = argmax (P(c|d))$, where $d$ is document, and $c\\in C$ is all classes such that the classifer return class c_hat (estimate of the correct class).\nClass $c$ can be \"positive\" or \"negative\".\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\nIn sentiment classification, we concatenate all documents with category $c$ of interest into one *big* text.\nWe then use frequency of $w_i$ to give a maximum likelihood of the probability:\n\n${P_hat}(w_i|c) = \frac{count (w_i, c)}{\\sum_{w\\in V}count(w,c)}$\n\nProbalem: When we try estimate the likelihood of \"fantastic\" given the class *positive*, but no positive class training doc contains the word.\nProbability would then be 0. Solution: We can do add-one smoothing to improve the count.\n\nIn sentiment classification, we also remove *unknown* words.\n\nNaive Bayes with binarized features seem to work better for many text-classification tasks!!\n\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\nContingency table helps identify Precision, Recall, and Accuracy.\nIn spam detection, true positives mean detecting spam and actually get spam. False negatives means detecting non-spam but actually spam.\n\nAccuracy is the percentage of predicting the right class for all documents.\nBUT, this does not work well when classes are unbalanced. So we care about Precision and Recall.\n\nPrecision: when system detects spam, what percentage is actually spam.\n\n${Precision} = \\frac{\\text{true positives}}{\\text{true positives + false positives}}$\n\nRecall: what percentage of items in the input that system actually correctly predict.\n\n$Recall=\\frac{\\text{true positives}}{\\text{true positives + false negatives}}$\n\nThe higher the both of these, the better! In example, high recall means the model is correctly detecting the spams (true positives) with a high percentage. __F-1__ score is a harmony between the two.\n\nIn multi-label classification, the contingency table's is called a __confusion matrix__.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\nTraining test set is used to train model. Development test set is used to tune parameters. Devset helps avoid overfitting.\n\nIn order to save lots of data for training, devset might not be large enough to be representative. We would like to utilize __all__ data for both training and test.\nSolution: __Cross validation__ means __randomly__ choosing a training and test set divsion of the data, then compute error rate on test set.\n\nFor example, we can do this 10 times and average the errors of the 10 runs, called it \"10-fold cross-validation\".\n\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 Your summary here \n\n## Module 12 Definitions\n* **Gold labels** - human-identified standard labels\n* **Contingency labels** - table of 4 cells of true/false and positive/negative\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\n",
        "Neural networks take in vector of input values and produces a __single_ output value.\n",
        "Use of modern neural nets is called \"deep learning\", since it's \"deep\" in the sense of having many layers.\n",
        "\n",
        "Building block of a neural network is a single computational __unit__. A neural unit taking a weighted sum of inputs with __one__additional term\n",
        "in the sum is called a \"bias term\".\n",
        "\n",
        "$z=b+\\sum_i w_ix_i = z=w\\cdot x+b$\n",
        "\n",
        "Here, $b$ is a bias and $z$ is the weighted sum.\n",
        "In other words, $z$ is also a weight vector with scalar bias $b$. We can replace the sum calling it a __dot product__.\n",
        "\n",
        "Instead of using $z$, a linear function of  of $x$ as the output, neural units uses a __non-linear function__ $f$.\n",
        "There are 3 popular non-linear functions $f()$ used to __activate__ a value, all of which maps output into the range $[0,1]$.\n",
        "One of such is __Sigmoid__:\n",
        "\n",
        "$y=\\\\frac{1}{1+exp(-(w\\cdot x+b))}$\n",
        "\n",
        "Given weight vector and bias: $w=[0.2, 0.3, 0.9]$, $b=0.5$ for input $x=[0.5, 0.6, 0.1]$.\n",
        "Output would be:\n",
        "\n",
        "$y=\\\\frac{1}{1+exp(-(w\\cdot x+b))}=\\\\frac{1}{1+e^{-(0.5*0.2+0.6*0.3+0.1*0.9)+0.5)}}=e^{-0.87}=0.7$\n",
        "\n",
        "The simplest activation (and most commonly used) is the \"rectified linear unit\" called __ReLU__: $y=max(x,0)$\n",
        "\n",
        "In sigmoid or tanh functions, high values of $z$ results in values of y that are __saturated__, meaning extremely close to 1 and a problem for learning.\n",
        "ReLU has nice properties that resulting from being close to linear - does not have this problem since output of values close to 1 also approaches 1 in \"nice gentle linear way.\"\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_2 = \"\"\"\n",
        "XOR Truth Table: only either or but __not both__ (slightly different from OR).\n",
        "It is easy to build a perceptron that can compute AND and OR but not possble for XOR since perceptron is a linear classifier (and XOR is not linearly separable).\n",
        "\n",
        "For two-dimensional inputs $x_1$ and $x_2$, the perception equation is: $w_1 x_1 + w_2 x_2 + b=0$.\n",
        "This line is a linearly separable __decision boundary__. If more than 2 inputs, decision boundary becomes a hyperplane (same idea, splitting the space into two categories).\n",
        "\n",
        "Solution: Neural networks are the only way to solve XOR (non-linearly separable data).\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_3 = \"\"\"\n",
        "__Feedforward__ is a multilayer network with units connecting no cycles (a DAG!).\n",
        "Outputs from units in each layer are passed to units in the next higher layer (no outputs passing back).\n",
        "Networks *with cycles* are called recurrent neural network.\n",
        "\n",
        "Three kinds of nodes: input units, hidden units, and output units.\n",
        "\n",
        "A convenient function to __normalize__ a vector of real values (converting a vector to values between 0 and 1 (summing to 1)) is called __softmax__ function.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_4 = \"\"\"\n",
        "First, in training, we need a __loss function__ to model distance between model ouput and \"gold\" output.\n",
        "__Cross-entropy loss__, often used for logistic regression, can also be used.\n",
        "\n",
        "Second, we need to find parameters to minimize the loss function such as __gradient descent__.\n",
        "\n",
        "Third, gradient descent requires knowing the gradient of the loss function.\n",
        "\n",
        "Cross-entropy loss is the log probability of the \"correct\" class.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "slp_chapter7_5 = \"\"\"\n",
        "Feedforward neural LM approximates the probability of a word given the entire prior context based on the previous $N$ words.\n",
        "4-gram means estimating the probability $P(w_t=i|w_{t-1}, w_{t-2}, w_{t-3})$. Note: Neural net language models are strikingly slower to train, so for many tasks, n-gram is a fine tool.\n",
        "\n",
        "Embeddings: idea is to encode it so that prior word context can be generalizable to many words.\n",
        "Example is \"When I get home I feed the cat\" - ngram would not know that \"dog\" can be substitute in, but neural LM would know that\n",
        "\"dog\" and \"cat\" have similar embeddings!\n",
        "\n",
        "\"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "45eae0d7-0e21-42cc-d80a-7ead3353a502"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n 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\nNeural networks take in vector of input values and produces a __single_ output value.\nUse of modern neural nets is called \"deep learning\", since it's \"deep\" in the sense of having many layers.\n\nBuilding block of a neural network is a single computational __unit__. A neural unit taking a weighted sum of inputs with __one__additional term\nin the sum is called a \"bias term\".\n\n$z=b+\\sum_i w_ix_i = z=w\\cdot x+b$\n\nHere, $b$ is a bias and $z$ is the weighted sum.\nIn other words, $z$ is also a weight vector with scalar bias $b$. We can replace the sum calling it a __dot product__.\n\nInstead of using $z$, a linear function of  of $x$ as the output, neural units uses a __non-linear function__ $f$.\nThere are 3 popular non-linear functions $f()$ used to __activate__ a value, all of which maps output into the range $[0,1]$.\nOne of such is __Sigmoid__:\n\n$y=\\frac{1}{1+exp(-(w\\cdot x+b))}$\n\nGiven weight vector and bias: $w=[0.2, 0.3, 0.9]$, $b=0.5$ for input $x=[0.5, 0.6, 0.1]$.\nOutput would be:\n\n$y=\\frac{1}{1+exp(-(w\\cdot x+b))}=\\frac{1}{1+e^{-(0.5*0.2+0.6*0.3+0.1*0.9)+0.5)}}=e^{-0.87}=0.7$\n\nThe simplest activation (and most commonly used) is the \"rectified linear unit\" called __ReLU__: $y=max(x,0)$\n\nIn sigmoid or tanh functions, high values of $z$ results in values of y that are __saturated__, meaning extremely close to 1 and a problem for learning.\nReLU has nice properties that resulting from being close to linear - does not have this problem since output of values close to 1 also approaches 1 in \"nice gentle linear way.\"\n\n\n## SLP Chapter 7.2 The XOR problem\n\nXOR Truth Table: only either or but __not both__ (slightly different from OR).\nIt is easy to build a perceptron that can compute AND and OR but not possble for XOR since perceptron is a linear classifier (and XOR is not linearly separable).\n\nFor two-dimensional inputs $x_1$ and $x_2$, the perception equation is: $w_1 x_1 + w_2 x_2 + b=0$.\nThis line is a linearly separable __decision boundary__. If more than 2 inputs, decision boundary becomes a hyperplane (same idea, splitting the space into two categories).\n\nSolution: Neural networks are the only way to solve XOR (non-linearly separable data).\n\n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\n__Feedforward__ is a multilayer network with units connecting no cycles (a DAG!).\nOutputs from units in each layer are passed to units in the next higher layer (no outputs passing back).\nNetworks *with cycles* are called recurrent neural network.\n\nThree kinds of nodes: input units, hidden units, and output units.\n\nA convenient function to __normalize__ a vector of real values (converting a vector to values between 0 and 1 (summing to 1)) is called __softmax__ function.\n\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\nIn training, we need a __loss function__ to model distance between model ouput and \"gold\" output.\n\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 947
        },
        "outputId": "1046ef32-ad6f-4ff6-dddf-e1ca9511c6ce"
      },
      "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\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "c2f968ca-0bb6-453e-9afc-5049670d554c"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Agent assigns a probability to each possible current state $s$.\nThe transition model $P(RESULT(a)=s') = \\sum_s P(s)P(s'|s,a)$ give the probability that action $a$ in state $s$ reaches arbitrary state $s'$.\nThe __utility function__ $U(s)$ tells us the desirability of a state. __Expected utility__ is the average utility value of outcomes\nand the probability they occur.\n\n__Maximum expected utility (MEU)__ says a rational agent should choose an expected utility-maximizing action.\nThe principle *formalize* the notion that agent should \"do the right thing\", NOT actually __operationalize__ t.\nThings like estimating a probability distribution over all possible states of the world requires \"perception, learning, representation, and inference.\"\nComputing $P(RESULT(a)=s')$ requires a __causal model__ of the world.\n\nOver a __history__, if an agents acts to maximize on a correct function $U(s)$,\nthen agent will achieve the highest possible performance score (average over all possible environments).\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n But what makes MEU, the average, so special as part of the decision making proces?\nWe can do some constraints on rational preferences:\n\n$A\\succ B$: A \\succeeds B means agent prefers A to B.\n\n$A\\sim B$: A \\similar to B means agent is indifferent.\n\n$A\\succeq B$: A \\succ or equal to B means agent prefers A over B or is indifferent.\n\nSet of outcomes for each action a \"lottery\": $L=[p_1, S_1; p_2, S2; ... p_n, S_n]$ of probabilities and States.\nEach outcome $S_i$ can be an atomic state or *another* lottery. Some properies:\n\n- Orderability: Agent must always decide between two lotteries. Cannot avoid deciding.\nExactly one of $A\\succ B$, $B\\succ A$, or $A\\sim B$ holds.\n\n- Transitivity: If agent prefers A to B and B to C, then agent must prefer A to C: $(A\\succ B)\\wedge(B\\succ C)=> (A\\succ C)$.\n\n- Continuity: If lottery B is between A and C in preference, there is some probability $p$ for which agent will be indifferent between B\nand the lotery yielding A with probability $p$ and C with probability $1-p$.\n\n- Substitutability: If agent is indifferent between lotteries A and B, then agent is indifferent between two more complex lotteries\nthat are the same except that B is substituted for A. Holds REGARDLESS of the probabilites and lottery outcomes.\n\n- Monotonicity: Suppose two lotteries have __same__ two possible outcomes A and B.\nIf agents prefers A to B, then agent must prefer lottery with higher probability!\n\n- Decomposability: Compound lotteries can be reduced/compressed to simpler ones using laws of probability.\n\"No fun in gambling\" rule is an example. \n\nThese are the __axioms__ of utility theory (but really preferences as they say nothing about utility function).\nFrom these, we can derive __theorems__, which will establish that a utility function __exists__ for ANY rational agent.\nDoes not establish that it is *unique*.\n\nUtility function does not change it gets transformed like this: $U'(S)=aU(S)+b$, where $a$ and $b$ are constants and $a$ is positive.\n\nIn a game-play and deterministic environment, agent needs only a preferences __ranking__ on states, meaning numbers don't matter!\nThis is called a __value function__ or __ordinal utility function__. Agent's preference behavior does not mean\nagent is *explicitly* maximizing utility function in choosing.\n\nRational behavior can be generated a number of ways and can be implemented with table lookup (with small number of possible states).\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nUtility functions map from lotteries to real numbers\n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nTransition model is __stochastic__ and transitions are __Markovian__, meaning the probability of reaching $s'$ from $s$ depends only\non $s$ and NOT on earlier states. Since decisions are sequential, utility function depend on *specific* sequence of states and actions called an __environment history__.\nNOT on a single state. For every transition, agent receives a __reward__ by $R(s, a, s')$.\n\nIf 9 state of -0.04 and 1 state of +1, then reward is (9*-0.04)+1 = 0.64.\n\nMarkov Decision process consists of: set of states (init state $s_0$), set of ACTIONS, a transition model $P(s'|s,a)$ and reward function $R(s,a,s')$.\nUsually involves __dynamic programming__ (recursively breaking problem into smaller pieces and remembering optimal solutions to the pieces).\n\nSince sequential, solution must specify moves agent should do to reach any given state.\n\nQuality of policy is measured by expected utility of possible environment histories generated by the policy.\n__Optimal utility__, $\\pi^*$, yields highest expected utility. Agent consults current percept and executes action $pi^*(s)$.\nPolicy represenst a \"simple relfex\" agent.\n\nThere are often multiple optimal policies. In examples where agent is indifferent about going left or going right.\n\nUtilities over time: utility function on environment histories described as $U_h([s_0, a_0, s_1, a_1, ..., s_{N+k}])$, where $s_i$ is state and $a_i$ is action.\n__Finite horizon vs. infinite horizon__: In a fixed time $N$, the game ends after a $N$ iterations.\nThis limits what the agent can do - whether or not there is plenty of time to explore before going to the end state.\nTime-dependent policies are called __nonstationary__. With no time limit, no reason to behave differently in same state at different times.\n\n__Additive discounted rewards__: Discount factor $\\gamma$ is a number between 0 (less significant) and 1 (more significant) to rewards at each state.\n\n$U_h=R(s_0,a_0,s_1)+\\gamma\\cdot R(s_1,a_1,s_2)+\\gamma^2 \\cdot R(s_2,a_2,s_3) + ...$\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nBellman equation is basis for __value iteration__ alogirthm to solve MDPs. For $n$ possible states, there are $n$ Bellman equations.\n\nPossible to solve with __linear programming__.\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \nTo make choices, agent must have __preferences__ among different possible outcomes.\n\nDecision theory = Probability theory + utility theory\n\nFundamental idea of decision theory is that agent acts by MEU.\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n\nSet of all possible worlds is called the __sample space__, where words are mutually exlcusive exhaustive.\nA probability model associates numerical probability with each possible world.\n\n$\\sum_{w\\in\\Omega}P(w)=1$ where $w$ is a world. Can also be something like a proposition.\n\nProbabilities when rolling dice such as $P(Total=11)$ are called unconditional or prior probs.\nThey refer to degrees of \"belief\" in a proposition without needing *any* other information.\nBut we usually have evidence, so __conditional/posterior__ probability is more applicable.\n\nExample: When going to dentist, $P(cavity)=0.2$ might be of interest. But if toothache, then $P(cavity|toothache)$ is the one that matters.\nConditional probability can be derived from __product rule__: $P(a\\wedge b)=P(a|b)\\cdot P(b)$.\n\nIn probability, variables are called __random variables__. Every RV is a function that maps domain of possible worlds $\\Omega$ to some __range__.\nIn dice, $Total$ is an rv. range is $\\{1,2,3,4,5,6\\}$. In a Boolean rv, range can be {True, False} making a $Bernoulli$ distribution.\n\nInclusion-exclusion principle: $P(a\\wedge) = P(a)+P(b)-P(a\\wedge b)$.\n\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\nAxioms of probabilit constrain probabilities of logically related propositions. An agent that violates the axioms *must* behave irrationally.\n\nIt is tough to get a __full joint probability distribution__ in the real world since it is often too large.\nHowever, when we have the probability of each complete value assingments to rv, we should use it!\n\n__Absolute independence__ betwen rvs allows the full joint distribution to be factored into smaller joint distribtutions, greatly reducing its complexity.\n\n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n\nFormula for __naive Bayes__ model:\n\n$P(Cause, Effect_1,..., Effect_n)=P(Cause)\\prod_i P(Effect_i|Cause)$\n\nIt is \"naive\" because it over simplifies independence even though the \"effect\" variables might not be *strictly* independent.\nVery appropriate for $text classification$ tasks.\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\nWumpus-world agent can calculate probabilites for unobserved aspects of the world to improve decision making with __conditional independence__.\n\nExample: Wumpus knows that a pit causes breezes in neighboring squares and each square other than [1, 1] constains pit with probability 0.2.\nHe can compute 2 random variables, 1) Whether or not square is a pit and 2) If square is breezy.\n\n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n\nPerplexity as evaluation method. The higher the conditional probability of a word sequence, the lower the perplexity.\nMinimizing perplexity is equivalent to maximizing the test set probability.\n\n$PP(W) = P(w_1 \\cdot w_2...w_N)^\frac{-1}{N}$\n\nThe more information the n-gram gives us about a word sequence (a sentence), the lower the perplexity (so the lower the better).\nHigher values indicate the input was “perplexing” from the model’s point of view, hence the term perplexity.\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\nN-gram model is very dependent on training corpus.\n\nUnknowne words are called __out of vocabulary (OOV)__ words. In an \"open vocabulary\" system, OOV words are modeled as <UNK>.\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\nSmoothing is used to prevent a language model from assigning zero probabilities to unseen words.\nWe \"shave off a bit of probability mass from some frequent events and give it to events we have never seen.\"\n\nLaplace, Add-k smoothing, Backoff & Interpolation.\n\n\n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Factored representation** - possible world represented by set of variable/value pairs\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\nIndependence and conditional independence relationships among variables can reduce __significantly__ the number of probabilities\nthat need to be specified to achieve the full joint distribution.\n\n__Bayesian network__ can be used to represent dependencies among variables.\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n\nMultinomial Naive Bayes classifier makes simplifying assumption about features' independence.\nIn the classifier, document is represented as a __bag-of-words__, an unordered set of words with their position __ignore__.\nExample: the word \"me\" would be recorded as appearing 5 times, \"you\" 6 times, etc.\n\n${c_hat} = argmax (P(c|d))$, where $d$ is document, and $c\\in C$ is all classes such that the classifer return class c_hat (estimate of the correct class).\nClass $c$ can be \"positive\" or \"negative\".\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\nIn sentiment classification, we concatenate all documents with category $c$ of interest into one *big* text.\nWe then use frequency of $w_i$ to give a maximum likelihood of the probability:\n\n${P_hat}(w_i|c) = \frac{count (w_i, c)}{\\sum_{w\\in V}count(w,c)}$\n\nProbalem: When we try estimate the likelihood of \"fantastic\" given the class *positive*, but no positive class training doc contains the word.\nProbability would then be 0. Solution: We can do add-one smoothing to improve the count.\n\nIn sentiment classification, we also remove *unknown* words.\n\nNaive Bayes with binarized features seem to work better for many text-classification tasks!!\n\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\nContingency table helps identify Precision, Recall, and Accuracy.\nIn spam detection, true positives mean detecting spam and actually get spam. False negatives means detecting non-spam but actually spam.\n\nAccuracy is the percentage of predicting the right class for all documents.\nBUT, this does not work well when classes are unbalanced. So we care about Precision and Recall.\n\nPrecision: when system detects spam, what percentage is actually spam.\n\n${Precision} = \\frac{\\text{true positives}}{\\text{true positives + false positives}}$\n\nRecall: what percentage of items in the input that system actually correctly predict.\n\n$Recall=\\frac{\\text{true positives}}{\\text{true positives + false negatives}}$\n\nThe higher the both of these, the better! In example, high recall means the model is correctly detecting the spams (true positives) with a high percentage. __F-1__ score is a harmony between the two.\n\nIn multi-label classification, the contingency table's is called a __confusion matrix__.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\nTraining test set is used to train model. Development test set is used to tune parameters. Devset helps avoid overfitting.\n\nIn order to save lots of data for training, devset might not be large enough to be representative. We would like to utilize __all__ data for both training and test.\nSolution: __Cross validation__ means __randomly__ choosing a training and test set divsion of the data, then compute error rate on test set.\n\nFor example, we can do this 10 times and average the errors of the 10 runs, called it \"10-fold cross-validation\".\n\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 Your summary here \n\n## Module 12 Definitions\n* **Gold labels** - human-identified standard labels\n* **Contingency labels** - table of 4 cells of true/false and positive/negative\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\nNeural networks take in vector of input values and produces a __single_ output value.\nUse of modern neural nets is called \"deep learning\", since it's \"deep\" in the sense of having many layers.\n\nBuilding block of a neural network is a single computational __unit__. A neural unit taking a weighted sum of inputs with __one__additional term\nin the sum is called a \"bias term\".\n\n$z=b+\\sum_i w_ix_i$\n\n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}