{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c77d5753-2fee-4d20-b37f-4a42b07ac0d4"
      },
      "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": "b304ad4d-8d66-4cbf-a1bb-65ff61e870f9"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"Agent has a utility function. MEU doesn't operationalize\n",
        "how to choose best action. Could also be uncertain about utility function.\n",
        "Performance measure is for entire history, utility function applies to next\n",
        "state, so can guide action.\n",
        "\"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\"Can lottery with possible outcomes and probabilities is \n",
        "L = [p_1, S_1; p_2, S_2;...; p_n, S_n]. Outcome S_i can be atomic state or\n",
        "another lottery. Six axioms of utility: orderability, transitivity, continuity,\n",
        "substitutability, monotonicity, decomposability. If any are violated, agent will\n",
        "exhibit irrational behavior. If agent is rational, exists function U such that\n",
        "U(A)>U(B) iff A>B and U(A)=U(B) iff A~B. Utility functions aren't unique. Will still\n",
        "be valid if U(S) -> aU(S)+b if a>0. For deterministic environment, agent only\n",
        "needs preference of states, exact numbers don't matter (value/ordinal function).\n",
        "Agent isn't necessarily explicitly maximizing utility (e.g. might have lookup \n",
        "table for states).\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"Can rate different events by asking agent to choose between\n",
        "S and lottery [p, U_best; (1-p), U_worst] (could used normalized). When agent\n",
        "is indifferent, p is utility of S. Utility of money is usually logarithmic-concave\n",
        "for positive wealth. Looks kind of logistic/tanh for full range (S shaped).\n",
        "U(L) < U(S_EMV(L)) because of concavity where EMV is expected monetary value.\n",
        "People are risk averse for positive wealth but become risk seeking at large\n",
        "negative wealth. For small  changes relative to current wealth, changes are\n",
        "approximately linear. Estimates of utility function are often overly\n",
        "optimistic. Can use Bayes' rule to avoid optimizer's curse.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"Environment often isn't deterministic. Utility function will\n",
        "depend on sequence of states. Markov decision process (MDP) consists of\n",
        "set of states, set of actions in each state, transition model, and reward function.\n",
        "Can solve MDPs with dynamic programming. Policy is simple reflex agent. Additive\n",
        "discounting is the only form of utility that satisfies stationarity. Also necessary\n",
        "for infinite sequences of rewards.\n",
        "Bellman equation: U(s) = max_{a in A(s)} sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*U(s')]\n",
        "U(s) = max_a Q(s, a). pi*(s) = argmax_a Q(s, a)\n",
        "For Q functions: Q(s, a) = sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*U(s')]\n",
        "For Q functions: Q(s, a) = sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*max_{a'} Q(s', a')]\n",
        "Could represent P(s', s, a) and R(s, a, s') with table of size |S|^2|A|. If sparse,\n",
        "can be O(|S||A|)\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"Value iteration, policy iteration, and linear programming are\n",
        "offline and generate exact solutions. Monte-Carlo is online and gives approximate\n",
        "solution. Value iteration uses Bellman equation. With n states, have n Bellman\n",
        "equations (nonlinear), and use iteration. Update is applied simultaneously to\n",
        "all states. With infinite iterations, will converge to unique solutions (and\n",
        "policy extracted is optimal). Contraction only has one fixed point. When the contraction\n",
        "function is applied to any argument, it gets closer to the fixed point. Bellman\n",
        "update is a contraction by factor of gamma on space of utility vectors (measured\n",
        "by max norm). Value iteration converges exponentially quickly. Policy often becomes\n",
        "optimal long before U_i has converged (policy loss goes to 0). Policy iteration\n",
        "terminates when policy improvement step doesn't change utilities. No max operation,\n",
        "so Bellman's equations are linear. Can be solved in O(n^3) using linear algebra.\n",
        "Can reduce solving MDPs to linear programming. Use U(s) as variables in program.\n",
        "Maximize utilities subject to inequalities of Bellman's equation U(s) >=...\n",
        "for every state and action. Can use Expectiminimax to solve MDPs as long as gamma\n",
        "isn't too close to 1. Could have large branching factor, so not so feasible.\n",
        "Can use Monte Carlo to sample from possible values of game instead of playing\n",
        "them all out.\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\" : \"assigns a single number to express desirability of state\",\n",
        "\"expected utility\" : \"weighted average of utility of outcomes\",\n",
        "\"maximum expected utility\": \"rational agent should choose action that maximizes expected utility\",\n",
        "\"performance measure\": \"gives score for history (sequence of states)\",\n",
        "\"orderability\": \"Either A>B, B>A, A~B\",\n",
        "\"transitivity\": \"(A>B)^(B>C) => (A>C)\",\n",
        "\"continuity\": \"A>B>C => exists p such that [p, A; 1-p, C] ~ B\",\n",
        "\"substitutability\": \"A~B => [p, A; 1-p, C] ~ [p, B; 1-p, C] (or can use >)\",\n",
        "\"monotonicity\": \"(A>B)^(p>q) <=> [p, A; 1-p, B] > [q, A; 1-p, B]\",\n",
        "\"decomposability\": \"[p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C]\",\n",
        "\"expected utility of lottery\": \"weighted sum of utility of lottery states\",\n",
        "\"preference elicitation\": \"presenting choices to people and using observed preferences to pin down utility function\",\n",
        "\"normialized utility\": \"scale utility to between 0 and 1\",\n",
        "\"micromort\": \"1 in a million chance of dying, used for value people place on own lives\",\n",
        "\"QALY\": \"quality-adjusted life year, used for medical decisions\",\n",
        "\"monotonic preference\": \"more is better (like money)\",\n",
        "\"certainty equivalent\": \"value an agent will accept instead of lottery\",\n",
        "\"insurance premium\": \"difference between EMV of lottery and certainty equivalent\",\n",
        "\"risk-neutral\": \"linear curve for utility of asset\",\n",
        "\"unbiased\": \"E(U_hat(a) - EU(a)) = 0\",\n",
        "\"order statistic\": \"distribution of any particular ranked element of sample\",\n",
        "\"optimizer's curse\": \"tendency of estimated expected utility of best choice to be too high\",\n",
        "\"normative theory\": \"describes how rational agent should act\",\n",
        "\"descriptive theory\": \"describes how agents actually act\",\n",
        "\"certainty effect\": \"people are attracted togains that are certain\",\n",
        "\"framing effect\": \"people choose differently when options are presented as gains or losses\",\n",
        "\"anchoring effect\": \"presenting options just to skew perception of other options\",\n",
        "\"markovian\": \"probability of reaching s' from s only depends on s, not entire history\",\n",
        "\"dynamic programming\": \"simplifying problem by recursively breaking it into smaller pieces and remembering their solutions\",\n",
        "\"policy\": \"action recommeded in a given state\",\n",
        "\"optimal policy\": \"policy that yields highest expected utility\",\n",
        "\"finite horizon\": \"after fixed time, nothing matters and game is over\",\n",
        "\"nonstationary\": \"policy depends on time (if has finite horizon)\",\n",
        "\"stationary\": \"policy doesn't depend on time (e.g. with infinite horizon)\",\n",
        "\"additive discounted rewards\": \"utility of state/action history is discounted sum of future rewards\",\n",
        "\"proper policy\": \"policy guaranteed to reach terminal state\",\n",
        "\"Q function\": \"expected utility of taking a given action in a given state\",\n",
        "\"shaping theorem\": \"R'(s, a, s') = R(s, a, s') + gamma*phi(s') - phi(s) for any function phi doesn't change optimal policy\",\n",
        "\"potential\": \"phi(s), used to guide agent in right direction with most immediate action\",\n",
        "\"dynamic decision networks\": \"factored representations and have exponential complexity advantage over atomic representations\",\n",
        "\"Bellman update\": \"use Bellman's equation as an update function for U(s)\",\n",
        "\"contraction\": \"function of one argument that when applied to different inputs, outputs values that are closer together\",\n",
        "\"policy loss\": \"||U_{pi_i} (s) - U|| where U is optimal policy\",\n",
        "\"policy iteration\": \"alternates between policy evaluation and policy improvement\",\n",
        "\"policy evaluation\": \"given policy, calculate utility of each state\",\n",
        "\"policy improvement\": \"given state values, use one-step look-ahead for action\",\n",
        "\"modified policy iteration\": \"use simplified Bellman update instead of solving for exact solutions\",\n",
        "\"asynchronous policy iteration\": \"update subset of states at a time, not all, avoiding bad states/actions\",\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": "0fda89d2-c1b5-4fd7-988f-c47df7c60c46",
        "cellView": "form"
      },
      "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\nAgent has a utility function. MEU doesn't operationalize\nhow to choose best action. Could also be uncertain about utility function.\nPerformance measure is for entire history, utility function applies to next\nstate, so can guide action.\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nCan lottery with possible outcomes and probabilities is \nL = [p_1, S_1; p_2, S_2;...; p_n, S_n]. Outcome S_i can be atomic state or\nanother lottery. Six axioms of utility: orderability, transitivity, continuity,\nsubstitutability, monotonicity, decomposability. If any are violated, agent will\nexhibit irrational behavior. If agent is rational, exists function U such that\nU(A)>U(B) iff A>B and U(A)=U(B) iff A~B. Utility functions aren't unique. Will still\nbe valid if U(S) -> aU(S)+b if a>0. For deterministic environment, agent only\nneeds preference of states, exact numbers don't matter (value/ordinal function).\nAgent isn't necessarily explicitly maximizing utility (e.g. might have lookup \ntable for states).\n\n\n## AIMA Chapter 16.3 Utility Functions\nCan rate different events by asking agent to choose between\nS and lottery [p, U_best; (1-p), U_worst] (could used normalized). When agent\nis indifferent, p is utility of S. Utility of money is usually logarithmic-concave\nfor positive wealth. Looks kind of logistic/tanh for full range (S shaped).\nU(L) < U(S_EMV(L)) because of concavity where EMV is expected monetary value.\nPeople are risk averse for positive wealth but become risk seeking at large\nnegative wealth. For small  changes relative to current wealth, changes are\napproximately linear. Estimates of utility function are often overly\noptimistic. Can use Bayes' rule to avoid optimizer's curse.\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nEnvironment often isn't deterministic. Utility function will\ndepend on sequence of states. Markov decision process (MDP) consists of\nset of states, set of actions in each state, transition model, and reward function.\nCan solve MDPs with dynamic programming. Policy is simple reflex agent. Additive\ndiscounting is the only form of utility that satisfies stationarity. Also necessary\nfor infinite sequences of rewards.\nBellman equation: U(s) = max_{a in A(s)} sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*U(s')]\nU(s) = max_a Q(s, a). pi*(s) = argmax_a Q(s, a)\nFor Q functions: Q(s, a) = sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*U(s')]\nFor Q functions: Q(s, a) = sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*max_{a'} Q(s', a')]\nCould represent P(s', s, a) and R(s, a, s') with table of size |S|^2|A|. If sparse,\ncan be O(|S||A|)\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\nValue iteration, policy iteration, and linear programming are\noffline and generate exact solutions. Monte-Carlo is online and gives approximate\nsolution. Value iteration uses Bellman equation. With n states, have n Bellman\nequations (nonlinear), and use iteration. Update is applied simultaneously to\nall states. With infinite iterations, will converge to unique solutions (and\npolicy extracted is optimal). Contraction only has one fixed point. When the contraction\nfunction is applied to any argument, it gets closer to the fixed point. Bellman\nupdate is a contraction by factor of gamma on space of utility vectors (measured\nby max norm). Value iteration converges exponentially quickly. Policy often becomes\noptimal long before U_i has converged (policy loss goes to 0). Policy iteration\nterminates when policy improvement step doesn't change utilities. No max operation,\nso Bellman's equations are linear. Can be solved in O(n^3) using linear algebra.\nCan reduce solving MDPs to linear programming. Use U(s) as variables in program.\nMaximize utilities subject to inequalities of Bellman's equation U(s) >=...\nfor every state and action. Can use Expectiminimax to solve MDPs as long as gamma\nisn't too close to 1. Could have large branching factor, so not so feasible.\nCan use Monte Carlo to sample from possible values of game instead of playing\nthem all out.\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - assigns a single number to express desirability of state\n* **Expected utility** - weighted average of utility of outcomes\n* **Maximum expected utility** - rational agent should choose action that maximizes expected utility\n* **Performance measure** - gives score for history (sequence of states)\n* **Orderability** - Either A>B, B>A, A~B\n* **Transitivity** - (A>B)^(B>C) => (A>C)\n* **Continuity** - A>B>C => exists p such that [p, A; 1-p, C] ~ B\n* **Substitutability** - A~B => [p, A; 1-p, C] ~ [p, B; 1-p, C] (or can use >)\n* **Monotonicity** - (A>B)^(p>q) <=> [p, A; 1-p, B] > [q, A; 1-p, B]\n* **Decomposability** - [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C]\n* **Expected utility of lottery** - weighted sum of utility of lottery states\n* **Preference elicitation** - presenting choices to people and using observed preferences to pin down utility function\n* **Normialized utility** - scale utility to between 0 and 1\n* **Micromort** - 1 in a million chance of dying, used for value people place on own lives\n* **Qaly** - quality-adjusted life year, used for medical decisions\n* **Monotonic preference** - more is better (like money)\n* **Certainty equivalent** - value an agent will accept instead of lottery\n* **Insurance premium** - difference between EMV of lottery and certainty equivalent\n* **Risk-neutral** - linear curve for utility of asset\n* **Unbiased** - E(U_hat(a) - EU(a)) = 0\n* **Order statistic** - distribution of any particular ranked element of sample\n* **Optimizer's curse** - tendency of estimated expected utility of best choice to be too high\n* **Normative theory** - describes how rational agent should act\n* **Descriptive theory** - describes how agents actually act\n* **Certainty effect** - people are attracted togains that are certain\n* **Framing effect** - people choose differently when options are presented as gains or losses\n* **Anchoring effect** - presenting options just to skew perception of other options\n* **Markovian** - probability of reaching s' from s only depends on s, not entire history\n* **Dynamic programming** - simplifying problem by recursively breaking it into smaller pieces and remembering their solutions\n* **Policy** - action recommeded in a given state\n* **Optimal policy** - policy that yields highest expected utility\n* **Finite horizon** - after fixed time, nothing matters and game is over\n* **Nonstationary** - policy depends on time (if has finite horizon)\n* **Stationary** - policy doesn't depend on time (e.g. with infinite horizon)\n* **Additive discounted rewards** - utility of state/action history is discounted sum of future rewards\n* **Proper policy** - policy guaranteed to reach terminal state\n* **Q function** - expected utility of taking a given action in a given state\n* **Shaping theorem** - R'(s, a, s') = R(s, a, s') + gamma*phi(s') - phi(s) for any function phi doesn't change optimal policy\n* **Potential** - phi(s), used to guide agent in right direction with most immediate action\n* **Dynamic decision networks** - factored representations and have exponential complexity advantage over atomic representations\n* **Bellman update** - use Bellman's equation as an update function for U(s)\n* **Contraction** - function of one argument that when applied to different inputs, outputs values that are closer together\n* **Policy loss** - ||U_{pi_i} (s) - U|| where U is optimal policy\n* **Policy iteration** - alternates between policy evaluation and policy improvement\n* **Policy evaluation** - given policy, calculate utility of each state\n* **Policy improvement** - given state values, use one-step look-ahead for action\n* **Modified policy iteration** - use simplified Bellman update instead of solving for exact solutions\n* **Asynchronous policy iteration** - update subset of states at a time, not all, avoiding bad states/actions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"Pull arm that has highest Gittins index, then update Gittins\n",
        "index. Optimal decision on first iteration takes O(n) where n is number of arms.\n",
        "Each decision after that is O(1). Can establish confidence interval for each arm\n",
        "and choose arm that has highest upper bound on confidence interval. No algorithm\n",
        "can have regret that grows more slowly than O(logN). No index function exists for\n",
        "selection problems. Globally optimal policy for BSP can include actions that\n",
        "are suboptimal from view of constituent MDP.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"In reinforcement learning, agent interacts with the world and\n",
        "periodically receives rewards (reinforcements) to tell it how well it's doing.\n",
        "Like solving an MDP except not given the MDP, it is in the MDP. Doesn't necessarily\n",
        "know the transition model or reward. Rewards are often sparse. In model based,\n",
        "agent could learn transition model or already know it.\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"Passive RL is similar to policy evaluation, but doesn't know\n",
        "transition model or reward function. Executes trials using policy. Adaptive\n",
        "dynamic programming (ADP) agent learns transition model that connects states\n",
        "based on constraints among utilities. Could also use modified policy iteration.\n",
        "Temporal difference (TD): U(s) <- U(s) + alpha*[R(s, pi(s), s') + gamma*U(s') - U(s)]\n",
        "Acts like weighted average of old estimate and new estimate of state values.\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"For active RL, agent needs to learn a complete transition model\n",
        "for all actions, not just model for fixed policy. Once agent has utility function\n",
        "that is optimal for model, can extract optimal action by one step look ahead. GLIE\n",
        "scheme is guaranteed to learn true transition model and can then exploit. Could\n",
        "have exploration function that tells agent how much to explore. Can use TD update\n",
        "with Q-learning, which doesn't need a transition model.\n",
        "Q(s, a) <- Q(s, a) + alpha*[R(s, a, s') + gamma*max Q(s', a') - Q(s, a)].\n",
        "SARSA is like Q-learning but waits until action a' is taken before updating\n",
        "Q(s, a). If algorithm is greedy, they are identical. If agent is exploring and\n",
        "yields negative reward, SARSA penalizes, Q-learning doesn't. Q-learning is\n",
        "off-policy, SARSA is on-policy.\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\"Can use evaluation function/function approximation instead\n",
        "of true utility or Q value. Could use weighted linear combination of features.\n",
        "Use supervised learning. For state utilities,\n",
        "theta_i(s) <- theta_i(s) + alpha*[R(s, pi(s), s') +\n",
        "gamma*U_{hat}(s') - U_{hat}(s)] dU_{hat}(s)/dtheta_i\n",
        "for utilities and \n",
        "theta_i(s) <- theta_i(s) + alpha*[R(s, pi(s), s') +\n",
        "gamma*max_{a'}Q_{hat}(s', a') - Q_{hat}(s, a)] dQ_{hat}(s, a)/dtheta_i\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"If policy is differentiable, can follow policy gradient to \n",
        "improve it. If not, can use empirical gradient by trying different values.\n",
        "Doesn't work if environment and policy aren't deterministic.\n",
        "\"\"\"\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",
        "\"m-armed bandit\" : \"slot machine with n levers\",\n",
        "\"exploration\": \"try arm that hasn't been played yet\",\n",
        "\"exploitation\": \"use best arm from ones already tried\",\n",
        "\"Markov reward process\": \"MDP with only one possible action\",\n",
        "\"Gittins index\": \"tipping point of when to switch arms\",\n",
        "\"restart MDP\": \"actions are either continue playing or quit and take home winnings\",\n",
        "\"Bernoulli bandit\": \"each arm produces reward of 1 with probability mu otherwise 0\",\n",
        "\"upper confidence bound policy\": \"pick arm with highest upper bound on confidence level\",\n",
        "\"Thompson sampling\": \"choose arm randomly accoring to probability that it is optimal given past samples\",\n",
        "\"selection problem\": \"fixed cost for each test, try to find optimal as fast as possible\",\n",
        "\"metalevel decision problem\": \"e.g. deciding what computations to make during game-tree search\",\n",
        "\"bandit superprocess\": \"each arm is a full MDP\",\n",
        "\"opportunity cost\": \"how much is given up by not choosing an arm\",\n",
        "\"dominating policy\": \"optimal policy if it exists\",\n",
        "\"model based RL\": \"agent uses transition model\",\n",
        "\"model free RL\": \"agent doesn't know or learn transition model (action-utility vs policy search)\",\n",
        "\"action-utility learning\": \"like Q-learning\",\n",
        "\"policy search\": \"learns policy that maps directly from states to actions (reflex agent)\",\n",
        "\"passive RL\": \"agent's policy is fixed, learn utility of states\",\n",
        "\"active RL\": \"agent also has to figure out what to do\",\n",
        "\"apprenticeship learning\": \"training agent using demonstration rather than reward\",\n",
        "\"direct utility estimation\": \"utility is expected total reward from that state onward (reward to go)\",\n",
        "\"pseudoexperience\": \"experience generated by simulating current transition model\",\n",
        "\"prioritized sweeping\": \"heuristic to prefer to make adjustments to states whose likely successors have undergone large adjustment in utility\",\n",
        "\"greedy agent\": \"agent that takes action that it currently believes is optimal\",\n",
        "\"greedy in the limit of infinite exploration (GLIE)\": \"try each action unbounded number of times to avoid probability that it missed optimal action\",\n",
        "\"absorbing state\": \"no actions have any effect and no rewards are received\",\n",
        "\"Bayesian RL\": \"assumes a prior over true model. Use Bayes' rule with observations for transition probabilities\",\n",
        "\"exploration POMDP\": \"agent will continue learning in future,, belief states are distributed over models\",\n",
        "\"robust control theory\": \"set of possible models H without assigning probabilities, policy gives best outcome in worst case\",\n",
        "\"Widrow-Hoff rule/delta rule\": \"gradient descent for parameters in estimation function\",\n",
        "\"catastrophic forgetting\": \"forgets something about world and messes up\",\n",
        "\"experience replay\": \"agent relives earlier mistakes to make sure it doesn't forget\",\n",
        "\"credit assignment problem\": \"how does it know which action to credit/blame for outcome\",\n",
        "\"reward shaping\": \"supplying agent with additional rewards (pseudorewards) for making progress\",\n",
        "\"hierarchical RL\": \"break up long action sequence and learn those\",\n",
        "\"correlated sampling\": \"generate a bunch of simulations and have agents play same action\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "64e93ce5-1a1e-4bc6-9a20-cc4589d7a1f9"
      },
      "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\nPull arm that has highest Gittins index, then update Gittins\nindex. Optimal decision on first iteration takes O(n) where n is number of arms.\nEach decision after that is O(1). Can establish confidence interval for each arm\nand choose arm that has highest upper bound on confidence interval. No algorithm\ncan have regret that grows more slowly than O(logN). No index function exists for\nselection problems. Globally optimal policy for BSP can include actions that\nare suboptimal from view of constituent MDP.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\nIn reinforcement learning, agent interacts with the world and\nperiodically receives rewards (reinforcements) to tell it how well it's doing.\nLike solving an MDP except not given the MDP, it is in the MDP. Doesn't necessarily\nknow the transition model or reward. Rewards are often sparse. In model based,\nagent could learn transition model or already know it.\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nPassive RL is similar to policy evaluation, but doesn't know\ntransition model or reward function. Executes trials using policy. Adaptive\ndynamic programming (ADP) agent learns transition model that connects states\nbased on constraints among utilities. Could also use modified policy iteration.\nTemporal difference (TD): U(s) <- U(s) + alpha*[R(s, pi(s), s') + gamma*U(s') - U(s)]\nActs like weighted average of old estimate and new estimate of state values.\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nFor active RL, agent needs to learn a complete transition model\nfor all actions, not just model for fixed policy. Once agent has utility function\nthat is optimal for model, can extract optimal action by one step look ahead. GLIE\nscheme is guaranteed to learn true transition model and can then exploit. Could\nhave exploration function that tells agent how much to explore. Can use TD update\nwith Q-learning, which doesn't need a transition model.\nQ(s, a) <- Q(s, a) + alpha*[R(s, a, s') + gamma*max Q(s', a') - Q(s, a)].\nSARSA is like Q-learning but waits until action a' is taken before updating\nQ(s, a). If algorithm is greedy, they are identical. If agent is exploring and\nyields negative reward, SARSA penalizes, Q-learning doesn't. Q-learning is\noff-policy, SARSA is on-policy.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nCan use evaluation function/function approximation instead\nof true utility or Q value. Could use weighted linear combination of features.\nUse supervised learning. For state utilities,\ntheta_i(s) <- theta_i(s) + alpha*[R(s, pi(s), s') +\ngamma*U_{hat}(s') - U_{hat}(s)] dU_{hat}(s)/dtheta_i\nfor utilities and \ntheta_i(s) <- theta_i(s) + alpha*[R(s, pi(s), s') +\ngamma*max_{a'}Q_{hat}(s', a') - Q_{hat}(s, a)] dQ_{hat}(s, a)/dtheta_i\n\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **M-armed bandit** - slot machine with n levers\n* **Exploration** - try arm that hasn't been played yet\n* **Exploitation** - use best arm from ones already tried\n* **Markov reward process** - MDP with only one possible action\n* **Gittins index** - tipping point of when to switch arms\n* **Restart mdp** - actions are either continue playing or quit and take home winnings\n* **Bernoulli bandit** - each arm produces reward of 1 with probability mu otherwise 0\n* **Upper confidence bound policy** - pick arm with highest upper bound on confidence level\n* **Thompson sampling** - choose arm randomly accoring to probability that it is optimal given past samples\n* **Selection problem** - fixed cost for each test, try to find optimal as fast as possible\n* **Metalevel decision problem** - e.g. deciding what computations to make during game-tree search\n* **Bandit superprocess** - each arm is a full MDP\n* **Opportunity cost** - how much is given up by not choosing an arm\n* **Dominating policy** - optimal policy if it exists\n* **Model based rl** - agent uses transition model\n* **Model free rl** - agent doesn't know or learn transition model (action-utility vs policy search)\n* **Action-utility learning** - like Q-learning\n* **Policy search** - learns policy that maps directly from states to actions (reflex agent)\n* **Passive rl** - agent's policy is fixed, learn utility of states\n* **Active rl** - agent also has to figure out what to do\n* **Apprenticeship learning** - training agent using demonstration rather than reward\n* **Direct utility estimation** - utility is expected total reward from that state onward (reward to go)\n* **Pseudoexperience** - experience generated by simulating current transition model\n* **Prioritized sweeping** - heuristic to prefer to make adjustments to states whose likely successors have undergone large adjustment in utility\n* **Greedy agent** - agent that takes action that it currently believes is optimal\n* **Greedy in the limit of infinite exploration (glie)** - try each action unbounded number of times to avoid probability that it missed optimal action\n* **Absorbing state** - no actions have any effect and no rewards are received\n* **Bayesian rl** - assumes a prior over true model. Use Bayes' rule with observations for transition probabilities\n* **Exploration pomdp** - agent will continue learning in future,, belief states are distributed over models\n* **Robust control theory** - set of possible models H without assigning probabilities, policy gives best outcome in worst case\n* **Widrow-hoff rule/delta rule** - gradient descent for parameters in estimation function\n* **Catastrophic forgetting** - forgets something about world and messes up\n* **Experience replay** - agent relives earlier mistakes to make sure it doesn't forget\n* **Credit assignment problem** - how does it know which action to credit/blame for outcome\n* **Reward shaping** - supplying agent with additional rewards (pseudorewards) for making progress\n* **Hierarchical rl** - break up long action sequence and learn those\n* **Correlated sampling** - generate a bunch of simulations and have agents play same action\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"Inference by enumeration: have evidence variables E,\n",
        "query variable Q, and hidden variables H. Want P(Q|e1, e2...ek). Find joint\n",
        "probability of P(Q, e1...ek) by summing across hidden variables. Normalize by\n",
        "dividing by sum_q P(Q, e1...ek). Use chain rule to get probability of a word\n",
        "given previous word(s). MLE-can count words (but some probabilities are 0). Can\n",
        "make Markov assumption that probability only depends on previous n words.\n",
        "Unigram: k=0 (just probability of word). Bigram: n=1 (given previous word) etc.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"concept\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b0c9113a-d439-4a57-99ef-bad75aea8c1e"
      },
      "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 Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \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 Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \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\nInference by enumeration: have evidence variables E,\nquery variable Q, and hidden variables H. Want P(Q|e1, e2...ek). Find joint\nprobability of P(Q, e1...ek) by summing across hidden variables. Normalize by\ndividing by sum_q P(Q, e1...ek). Use chain rule to get probability of a word\ngiven previous word(s). MLE-can count words (but some probabilities are 0). Can\nmake Markov assumption that probability only depends on previous n words.\nUnigram: k=0 (just probability of word). Bigram: n=1 (given previous word) etc.\n\n\n## Module 10 Definitions\n* **Concept** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"Specifying full joint distribution is intractable. Bayesian\n",
        "networks can represent any full joint probability and often do so concisely.\n",
        "Directed graph where each node has probability information representing a\n",
        "random variable (discrete or continuous). Arrows from parents to children. Each node\n",
        "has probability given parents using parameters. Can represent using conditional\n",
        "probability table (for discrete).\n",
        "\"\"\"\n",
        "chapter13_2 = \"\"\"Syntax of Bayes net is a DAG with local probability information.\n",
        "Semantics defines how syntax corresponds to joint distribution over network variables.\n",
        "Nets are locally structured (linear rather than exponential growth).\n",
        "\"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"Joint probability over n boolean variables: 2^n. Bayes\n",
        "net with n variables and maximum of k parents is O(n2^(k+1)). D-separation\n",
        "separates nodes so that they are independent given other node. Every node in path\n",
        "must be active in order for the path to be active. Inference by enumeration isn't\n",
        "efficient. Variable elimination iterweaves joining and marginalizing. Asymptotic\n",
        "run time is still exponential, but average is better.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian networks\" : \"DAG used to represent dependencies among variables\",   \n",
        "\"conditioning case\": \"combination of values for parents\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 515
        },
        "cellView": "form",
        "outputId": "b902974a-f532-4de7-8118-3ca1c600b019"
      },
      "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\nSpecifying full joint distribution is intractable. Bayesian\nnetworks can represent any full joint probability and often do so concisely.\nDirected graph where each node has probability information representing a\nrandom variable (discrete or continuous). Arrows from parents to children. Each node\nhas probability given parents using parameters. Can represent using conditional\nprobability table (for discrete).\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nSyntax of Bayes net is a DAG with local probability information.\nSemantics defines how syntax corresponds to joint distribution over network variables.\nNets are locally structured (linear rather than exponential growth).\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\nJoint probability over n boolean variables: 2^n. Bayes\nnet with n variables and maximum of k parents is O(n2^(k+1)). D-separation\nseparates nodes so that they are independent given other node. Every node in path\nmust be active in order for the path to be active. Inference by enumeration isn't\nefficient. Variable elimination iterweaves joining and marginalizing. Asymptotic\nrun time is still exponential, but average is better.\n\n\n## Module 11 Definitions\n* **Bayesian networks** - DAG used to represent dependencies among variables\n* **Conditioning case** - combination of values for parents\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 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"Want to predict P(y|f1, f2, f3) where f is a feature.\n",
        "Assume features are independent given label. Before, was |y| |f|^n parameters, but\n",
        "goes to n|f| |y| parameters. Query variable is class label. Need to estimate P(y),\n",
        "which is prior over labels. Then estimate P(fi|y) for each feature. Could estimate\n",
        "probability of words using MLE, but results in zeros. Laplace smoothing adds one\n",
        "pseudocount to every word. Could also add count of k to every word. Linear interpolation\n",
        "takes into account both conditional and unconditional probabilities. For perceptron,\n",
        "have input features x1...xn and internal weights w1...wn. take weighted sum of\n",
        "features times weights and compare to threshold. If <= 0, output 0. If > 0,\n",
        "output 1. Can also have bias term to change threshold, so predict from w.x+b.\n",
        "High bias means likely to fire, low bias means unlikely to fire. Forms\n",
        "separating hyperplane. When training, only change when prediction is wrong. If so,\n",
        "w <- w + y*f(x). For multiclass, have weight vector for each class. Calculate score\n",
        "for each class and choose one with highest. If wrong, increment true class weight\n",
        "by f(x) and decrement incorrect class weight by f(x). Will converge if linearly\n",
        "separable with mistakes < k/delta^2 where k = num of features and delta is margin.\n",
        "If nonseparable, won't converge. Could average weight vectors over time. SVM picks\n",
        "best separating hyperplane. For nonlinear data, can transform features or project\n",
        "into higher dimensional space.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"backoff\" : \"if haven't seen trigram, try bigram probability, then unigram\",\n",
        "\"linear interpolation\": \"alpha*P(x|y) + (1-alpha)*P(x) where alpha is hyperparameter\",\n",
        "\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": "8193755b-8323-4dc5-bc6b-0d1683a32478"
      },
      "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 Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\nWant to predict P(y|f1, f2, f3) where f is a feature.\nAssume features are independent given label. Before, was |y| |f|^n parameters, but\ngoes to n|f| |y| parameters. Query variable is class label. Need to estimate P(y),\nwhich is prior over labels. Then estimate P(fi|y) for each feature. Could estimate\nprobability of words using MLE, but results in zeros. Laplace smoothing adds one\npseudocount to every word. Could also add count of k to every word. Linear interpolation\ntakes into account both conditional and unconditional probabilities. For perceptron,\nhave input features x1...xn and internal weights w1...wn. take weighted sum of\nfeatures times weights and compare to threshold. If <= 0, output 0. If > 0,\noutput 1. Can also have bias term to change threshold, so predict from w.x+b.\nHigh bias means likely to fire, low bias means unlikely to fire. Forms\nseparating hyperplane. When training, only change when prediction is wrong. If so,\nw <- w + y*f(x). For multiclass, have weight vector for each class. Calculate score\nfor each class and choose one with highest. If wrong, increment true class weight\nby f(x) and decrement incorrect class weight by f(x). Will converge if linearly\nseparable with mistakes < k/delta^2 where k = num of features and delta is margin.\nIf nonseparable, won't converge. Could average weight vectors over time. SVM picks\nbest separating hyperplane. For nonlinear data, can transform features or project\ninto higher dimensional space.\n\n\n## Module 12 Definitions\n* **Backoff** - if haven't seen trigram, try bigram probability, then unigram\n* **Linear interpolation** - alpha*P(x|y) + (1-alpha)*P(x) where alpha is hyperparameter\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"Logistic regression: P(+|x) = 1/(1+e^-(w.x+b)).\n",
        "Threshold of 0.5 to predict + or -. For sentiment classification, could count\n",
        "positive or negative words (from lexicon), could count instances of certain\n",
        "words, etc. P(y|x) = y_hat^y (1-y_hat)^(1-y). Want to minimize cross entropy\n",
        "loss -log P(y|x). Convex, so global minimum. Use gradient descent.\n",
        "w_{t+1} <- w_t - eta * d\\dw [Loss]. Update weights simultaneously using gradient.\n",
        "Even if logistic regression classifies correctly, keeps pushing weights further.\n",
        "Minimize loss, not maximize classification accuracy. For stochastic gradient descent,\n",
        "use datapoints one at a time instead of full set (batch). Can also use minibatch.\n",
        "Need to regularize to avoid overfitting (L1 penalty=LASSO, L2=Ridge). For\n",
        "multiclass logistic regression uses softmax over outputs of sigmoid with\n",
        "weight vector for each class to normalize to probability distribution.\n",
        "e^zj/(sum_i e^z_i). Feed forward neural network is fully connected with no\n",
        "cycles.Have input layer, hidden layers, and output layer. Perceptrons have\n",
        "step function at w.x+b, and logistic regression is better for neurons because\n",
        "it has a smooth derivative. Could also use ReLU or tanh. Have a weight matrix\n",
        "for each layer e.g. h = sigma(Wx+b). Make computation graph. For forward pass,\n",
        "plug in values for inputs and compute output. For backward pass, use chain rule\n",
        "finding partial derivative of output with respect to each weight (chain together\n",
        "partials). Can then use gradient descent.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0fd8a51e-fadd-493e-c759-4a88861b8670"
      },
      "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 Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\nLogistic regression: P(+|x) = 1/(1+e^-(w.x+b)).\nThreshold of 0.5 to predict + or -. For sentiment classification, could count\npositive or negative words (from lexicon), could count instances of certain\nwords, etc. P(y|x) = y_hat^y (1-y_hat)^(1-y). Want to minimize cross entropy\nloss -log P(y|x). Convex, so global minimum. Use gradient descent.\nw_{t+1} <- w_t - eta * d\\dw [Loss]. Update weights simultaneously using gradient.\nEven if logistic regression classifies correctly, keeps pushing weights further.\nMinimize loss, not maximize classification accuracy. For stochastic gradient descent,\nuse datapoints one at a time instead of full set (batch). Can also use minibatch.\nNeed to regularize to avoid overfitting (L1 penalty=LASSO, L2=Ridge). For\nmulticlass logistic regression uses softmax over outputs of sigmoid with\nweight vector for each class to normalize to probability distribution.\ne^zj/(sum_i e^z_i). Feed forward neural network is fully connected with no\ncycles.Have input layer, hidden layers, and output layer. Perceptrons have\nstep function at w.x+b, and logistic regression is better for neurons because\nit has a smooth derivative. Could also use ReLU or tanh. Have a weight matrix\nfor each layer e.g. h = sigma(Wx+b). Make computation graph. For forward pass,\nplug in values for inputs and compute output. For backward pass, use chain rule\nfinding partial derivative of output with respect to each weight (chain together\npartials). Can then use gradient descent.\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"N-grams represent words as sequence of letters\n",
        "or index in vocabulary list. Want to be able to represent synonyms, antonyms,\n",
        "connotations, semantic roles, etc. Want support for entailment. Can make 'nym'\n",
        "directory manually that allows formilized logic-based inference. A lot of work\n",
        "even for single language. Could use vector space model. Words that are similar\n",
        "should be close in vector space. Distributional hypothesis says that words in\n",
        "similar contexts are synonyms. Can make term-document matrix where each cell is\n",
        "how many times word appears in document. Very sparse. Can compare documents\n",
        "by their column vectors (e.g. user query for plagiarism). Can also compare words\n",
        "by row vectors. Frequency impacts similarity measure, so normalize vectors.\n",
        "Use cosine distance (angle between vectors) 1 - u.v/||u||||v||.\n",
        "Could also have term-term matrix that tracks how often each word appears in\n",
        "context of another word. Can have long-term dependencies. Can also use\n",
        "parser to associate words together and create dependency arcs. Most frequent\n",
        "words often aren't informative. TF-IDF (term frequency-inverse document frequency)\n",
        "reduces contributions of common words. Co-occurrence matrices are long sparse\n",
        "vectors. Want short and dense (word embeddings). Neural language models don't\n",
        "need smoothing like n-grams. Can handle much longer history and generalize\n",
        "contexts.Associate each word with a vector representation. Train model that\n",
        "takes in k-gram of words and predicts probability over next words. Context\n",
        "words are treated like word window. Embeddings are byproduct of leanred\n",
        "model but can then be used independently. Word2vec uses each neighboring\n",
        "word on both sides as positive example and generates k randomly sampled words\n",
        "from text as negative example, then trains on both examples. Predicts how\n",
        "likely a word is to show up near given word. Don't care about answer, but\n",
        "use to learn embeddings of words. Like implicitly supervised learning with\n",
        "no manual supervision. Skip-gram; treat target word and neighboring\n",
        "context as positive example, randomly sample other words in lexicon as negative\n",
        "examples. Use logistic regression to classify positive and negative examples.\n",
        "Similarity between target and context is t.c. Assume all context words are\n",
        "independent given target. Learn two matrices W and C to learn word as both\n",
        "target and context. Can either use W and throw away C, or merge them. Can\n",
        "evaluate model based on how similar two words are compared to similarity\n",
        "with different word. Concordant pairs = +1, discordant pairs = -1. By ordering,\n",
        "shows correlation with human judgement. With tight context window, most similar\n",
        "words are words that are used in same context. With broader window, most similar\n",
        "words are words that are topically similar. Can perform vector math using\n",
        "embeddings (like addition and subtraction). Can measure usage throughout time\n",
        "by training on historical texts. Can look at associations between different\n",
        "words. Can test attitudes throughout time with different names or adjectives.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "78d0acb7-7bad-435a-8324-d985ac7efe7b",
        "cellView": "form"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 14 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\nN-grams represent words as sequence of letters\nor index in vocabulary list. Want to be able to represent synonyms, antonyms,\nconnotations, semantic roles, etc. Want support for entailment. Can make 'nym'\ndirectory manually that allows formilized logic-based inference. A lot of work\neven for single language. Could use vector space model. Words that are similar\nshould be close in vector space. Distributional hypothesis says that words in\nsimilar contexts are synonyms. Can make term-document matrix where each cell is\nhow many times word appears in document. Very sparse. Can compare documents\nby their column vectors (e.g. user query for plagiarism). Can also compare words\nby row vectors. Frequency impacts similarity measure, so normalize vectors.\nUse cosine distance (angle between vectors) 1 - u.v/||u||||v||.\nCould also have term-term matrix that tracks how often each word appears in\ncontext of another word. Can have long-term dependencies. Can also use\nparser to associate words together and create dependency arcs. Most frequent\nwords often aren't informative. TF-IDF (term frequency-inverse document frequency)\nreduces contributions of common words. Co-occurrence matrices are long sparse\nvectors. Want short and dense (word embeddings). Neural language models don't\nneed smoothing like n-grams. Can handle much longer history and generalize\ncontexts.Associate each word with a vector representation. Train model that\ntakes in k-gram of words and predicts probability over next words. Context\nwords are treated like word window. Embeddings are byproduct of leanred\nmodel but can then be used independently. Word2vec uses each neighboring\nword on both sides as positive example and generates k randomly sampled words\nfrom text as negative example, then trains on both examples. Predicts how\nlikely a word is to show up near given word. Don't care about answer, but\nuse to learn embeddings of words. Like implicitly supervised learning with\nno manual supervision. Skip-gram; treat target word and neighboring\ncontext as positive example, randomly sample other words in lexicon as negative\nexamples. Use logistic regression to classify positive and negative examples.\nSimilarity between target and context is t.c. Assume all context words are\nindependent given target. Learn two matrices W and C to learn word as both\ntarget and context. Can either use W and throw away C, or merge them. Can\nevaluate model based on how similar two words are compared to similarity\nwith different word. Concordant pairs = +1, discordant pairs = -1. By ordering,\nshows correlation with human judgement. With tight context window, most similar\nwords are words that are used in same context. With broader window, most similar\nwords are words that are topically similar. Can perform vector math using\nembeddings (like addition and subtraction). Can measure usage throughout time\nby training on historical texts. Can look at associations between different\nwords. Can test attitudes throughout time with different names or adjectives.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "847a02d1-a1df-4754-bbfc-2ec1ac5052a5"
      },
      "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\nAgent has a utility function. MEU doesn't operationalize\nhow to choose best action. Could also be uncertain about utility function.\nPerformance measure is for entire history, utility function applies to next\nstate, so can guide action.\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nCan lottery with possible outcomes and probabilities is \nL = [p_1, S_1; p_2, S_2;...; p_n, S_n]. Outcome S_i can be atomic state or\nanother lottery. Six axioms of utility: orderability, transitivity, continuity,\nsubstitutability, monotonicity, decomposability. If any are violated, agent will\nexhibit irrational behavior. If agent is rational, exists function U such that\nU(A)>U(B) iff A>B and U(A)=U(B) iff A~B. Utility functions aren't unique. Will still\nbe valid if U(S) -> aU(S)+b if a>0. For deterministic environment, agent only\nneeds preference of states, exact numbers don't matter (value/ordinal function).\nAgent isn't necessarily explicitly maximizing utility (e.g. might have lookup \ntable for states).\n\n\n## AIMA Chapter 16.3 Utility Functions\nCan rate different events by asking agent to choose between\nS and lottery [p, U_best; (1-p), U_worst] (could used normalized). When agent\nis indifferent, p is utility of S. Utility of money is usually logarithmic-concave\nfor positive wealth. Looks kind of logistic/tanh for full range (S shaped).\nU(L) < U(S_EMV(L)) because of concavity where EMV is expected monetary value.\nPeople are risk averse for positive wealth but become risk seeking at large\nnegative wealth. For small  changes relative to current wealth, changes are\napproximately linear. Estimates of utility function are often overly\noptimistic. Can use Bayes' rule to avoid optimizer's curse.\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nEnvironment often isn't deterministic. Utility function will\ndepend on sequence of states. Markov decision process (MDP) consists of\nset of states, set of actions in each state, transition model, and reward function.\nCan solve MDPs with dynamic programming. Policy is simple reflex agent. Additive\ndiscounting is the only form of utility that satisfies stationarity. Also necessary\nfor infinite sequences of rewards.\nBellman equation: U(s) = max_{a in A(s)} sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*U(s')]\nU(s) = max_a Q(s, a). pi*(s) = argmax_a Q(s, a)\nFor Q functions: Q(s, a) = sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*U(s')]\nFor Q functions: Q(s, a) = sum_{s'} P(s'|s, a)[R(s, a, s') + gamma*max_{a'} Q(s', a')]\nCould represent P(s', s, a) and R(s, a, s') with table of size |S|^2|A|. If sparse,\ncan be O(|S||A|)\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\nValue iteration, policy iteration, and linear programming are\noffline and generate exact solutions. Monte-Carlo is online and gives approximate\nsolution. Value iteration uses Bellman equation. With n states, have n Bellman\nequations (nonlinear), and use iteration. Update is applied simultaneously to\nall states. With infinite iterations, will converge to unique solutions (and\npolicy extracted is optimal). Contraction only has one fixed point. When the contraction\nfunction is applied to any argument, it gets closer to the fixed point. Bellman\nupdate is a contraction by factor of gamma on space of utility vectors (measured\nby max norm). Value iteration converges exponentially quickly. Policy often becomes\noptimal long before U_i has converged (policy loss goes to 0). Policy iteration\nterminates when policy improvement step doesn't change utilities. No max operation,\nso Bellman's equations are linear. Can be solved in O(n^3) using linear algebra.\nCan reduce solving MDPs to linear programming. Use U(s) as variables in program.\nMaximize utilities subject to inequalities of Bellman's equation U(s) >=...\nfor every state and action. Can use Expectiminimax to solve MDPs as long as gamma\nisn't too close to 1. Could have large branching factor, so not so feasible.\nCan use Monte Carlo to sample from possible values of game instead of playing\nthem all out.\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - assigns a single number to express desirability of state\n* **Expected utility** - weighted average of utility of outcomes\n* **Maximum expected utility** - rational agent should choose action that maximizes expected utility\n* **Performance measure** - gives score for history (sequence of states)\n* **Orderability** - Either A>B, B>A, A~B\n* **Transitivity** - (A>B)^(B>C) => (A>C)\n* **Continuity** - A>B>C => exists p such that [p, A; 1-p, C] ~ B\n* **Substitutability** - A~B => [p, A; 1-p, C] ~ [p, B; 1-p, C] (or can use >)\n* **Monotonicity** - (A>B)^(p>q) <=> [p, A; 1-p, B] > [q, A; 1-p, B]\n* **Decomposability** - [p, A; 1-p, [q, B; 1-q, C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C]\n* **Expected utility of lottery** - weighted sum of utility of lottery states\n* **Preference elicitation** - presenting choices to people and using observed preferences to pin down utility function\n* **Normialized utility** - scale utility to between 0 and 1\n* **Micromort** - 1 in a million chance of dying, used for value people place on own lives\n* **Qaly** - quality-adjusted life year, used for medical decisions\n* **Monotonic preference** - more is better (like money)\n* **Certainty equivalent** - value an agent will accept instead of lottery\n* **Insurance premium** - difference between EMV of lottery and certainty equivalent\n* **Risk-neutral** - linear curve for utility of asset\n* **Unbiased** - E(U_hat(a) - EU(a)) = 0\n* **Order statistic** - distribution of any particular ranked element of sample\n* **Optimizer's curse** - tendency of estimated expected utility of best choice to be too high\n* **Normative theory** - describes how rational agent should act\n* **Descriptive theory** - describes how agents actually act\n* **Certainty effect** - people are attracted togains that are certain\n* **Framing effect** - people choose differently when options are presented as gains or losses\n* **Anchoring effect** - presenting options just to skew perception of other options\n* **Markovian** - probability of reaching s' from s only depends on s, not entire history\n* **Dynamic programming** - simplifying problem by recursively breaking it into smaller pieces and remembering their solutions\n* **Policy** - action recommeded in a given state\n* **Optimal policy** - policy that yields highest expected utility\n* **Finite horizon** - after fixed time, nothing matters and game is over\n* **Nonstationary** - policy depends on time (if has finite horizon)\n* **Stationary** - policy doesn't depend on time (e.g. with infinite horizon)\n* **Additive discounted rewards** - utility of state/action history is discounted sum of future rewards\n* **Proper policy** - policy guaranteed to reach terminal state\n* **Q function** - expected utility of taking a given action in a given state\n* **Shaping theorem** - R'(s, a, s') = R(s, a, s') + gamma*phi(s') - phi(s) for any function phi doesn't change optimal policy\n* **Potential** - phi(s), used to guide agent in right direction with most immediate action\n* **Dynamic decision networks** - factored representations and have exponential complexity advantage over atomic representations\n* **Bellman update** - use Bellman's equation as an update function for U(s)\n* **Contraction** - function of one argument that when applied to different inputs, outputs values that are closer together\n* **Policy loss** - ||U_{pi_i} (s) - U|| where U is optimal policy\n* **Policy iteration** - alternates between policy evaluation and policy improvement\n* **Policy evaluation** - given policy, calculate utility of each state\n* **Policy improvement** - given state values, use one-step look-ahead for action\n* **Modified policy iteration** - use simplified Bellman update instead of solving for exact solutions\n* **Asynchronous policy iteration** - update subset of states at a time, not all, avoiding bad states/actions\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nPull arm that has highest Gittins index, then update Gittins\nindex. Optimal decision on first iteration takes O(n) where n is number of arms.\nEach decision after that is O(1). Can establish confidence interval for each arm\nand choose arm that has highest upper bound on confidence interval. No algorithm\ncan have regret that grows more slowly than O(logN). No index function exists for\nselection problems. Globally optimal policy for BSP can include actions that\nare suboptimal from view of constituent MDP.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\nIn reinforcement learning, agent interacts with the world and\nperiodically receives rewards (reinforcements) to tell it how well it's doing.\nLike solving an MDP except not given the MDP, it is in the MDP. Doesn't necessarily\nknow the transition model or reward. Rewards are often sparse. In model based,\nagent could learn transition model or already know it.\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nPassive RL is similar to policy evaluation, but doesn't know\ntransition model or reward function. Executes trials using policy. Adaptive\ndynamic programming (ADP) agent learns transition model that connects states\nbased on constraints among utilities. Could also use modified policy iteration.\nTemporal difference (TD): U(s) <- U(s) + alpha*[R(s, pi(s), s') + gamma*U(s') - U(s)]\nActs like weighted average of old estimate and new estimate of state values.\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nFor active RL, agent needs to learn a complete transition model\nfor all actions, not just model for fixed policy. Once agent has utility function\nthat is optimal for model, can extract optimal action by one step look ahead. GLIE\nscheme is guaranteed to learn true transition model and can then exploit. Could\nhave exploration function that tells agent how much to explore. Can use TD update\nwith Q-learning, which doesn't need a transition model.\nQ(s, a) <- Q(s, a) + alpha*[R(s, a, s') + gamma*max Q(s', a') - Q(s, a)].\nSARSA is like Q-learning but waits until action a' is taken before updating\nQ(s, a). If algorithm is greedy, they are identical. If agent is exploring and\nyields negative reward, SARSA penalizes, Q-learning doesn't. Q-learning is\noff-policy, SARSA is on-policy.\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nCan use evaluation function/function approximation instead\nof true utility or Q value. Could use weighted linear combination of features.\nUse supervised learning. For state utilities,\ntheta_i(s) <- theta_i(s) + alpha*[R(s, pi(s), s') +\ngamma*U_{hat}(s') - U_{hat}(s)] dU_{hat}(s)/dtheta_i\nfor utilities and \ntheta_i(s) <- theta_i(s) + alpha*[R(s, pi(s), s') +\ngamma*max_{a'}Q_{hat}(s', a') - Q_{hat}(s, a)] dQ_{hat}(s, a)/dtheta_i\n\n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **M-armed bandit** - slot machine with n levers\n* **Exploration** - try arm that hasn't been played yet\n* **Exploitation** - use best arm from ones already tried\n* **Markov reward process** - MDP with only one possible action\n* **Gittins index** - tipping point of when to switch arms\n* **Restart mdp** - actions are either continue playing or quit and take home winnings\n* **Bernoulli bandit** - each arm produces reward of 1 with probability mu otherwise 0\n* **Upper confidence bound policy** - pick arm with highest upper bound on confidence level\n* **Thompson sampling** - choose arm randomly accoring to probability that it is optimal given past samples\n* **Selection problem** - fixed cost for each test, try to find optimal as fast as possible\n* **Metalevel decision problem** - e.g. deciding what computations to make during game-tree search\n* **Bandit superprocess** - each arm is a full MDP\n* **Opportunity cost** - how much is given up by not choosing an arm\n* **Dominating policy** - optimal policy if it exists\n* **Model based rl** - agent uses transition model\n* **Model free rl** - agent doesn't know or learn transition model (action-utility vs policy search)\n* **Action-utility learning** - like Q-learning\n* **Policy search** - learns policy that maps directly from states to actions (reflex agent)\n* **Passive rl** - agent's policy is fixed, learn utility of states\n* **Active rl** - agent also has to figure out what to do\n* **Apprenticeship learning** - training agent using demonstration rather than reward\n* **Direct utility estimation** - utility is expected total reward from that state onward (reward to go)\n* **Pseudoexperience** - experience generated by simulating current transition model\n* **Prioritized sweeping** - heuristic to prefer to make adjustments to states whose likely successors have undergone large adjustment in utility\n* **Greedy agent** - agent that takes action that it currently believes is optimal\n* **Greedy in the limit of infinite exploration (glie)** - try each action unbounded number of times to avoid probability that it missed optimal action\n* **Absorbing state** - no actions have any effect and no rewards are received\n* **Bayesian rl** - assumes a prior over true model. Use Bayes' rule with observations for transition probabilities\n* **Exploration pomdp** - agent will continue learning in future,, belief states are distributed over models\n* **Robust control theory** - set of possible models H without assigning probabilities, policy gives best outcome in worst case\n* **Widrow-hoff rule/delta rule** - gradient descent for parameters in estimation function\n* **Catastrophic forgetting** - forgets something about world and messes up\n* **Experience replay** - agent relives earlier mistakes to make sure it doesn't forget\n* **Credit assignment problem** - how does it know which action to credit/blame for outcome\n* **Reward shaping** - supplying agent with additional rewards (pseudorewards) for making progress\n* **Hierarchical rl** - break up long action sequence and learn those\n* **Correlated sampling** - generate a bunch of simulations and have agents play same action\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \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 Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \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\nInference by enumeration: have evidence variables E,\nquery variable Q, and hidden variables H. Want P(Q|e1, e2...ek). Find joint\nprobability of P(Q, e1...ek) by summing across hidden variables. Normalize by\ndividing by sum_q P(Q, e1...ek). Use chain rule to get probability of a word\ngiven previous word(s). MLE-can count words (but some probabilities are 0). Can\nmake Markov assumption that probability only depends on previous n words.\nUnigram: k=0 (just probability of word). Bigram: n=1 (given previous word) etc.\n\n\n## Module 10 Definitions\n* **Concept** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\nSpecifying full joint distribution is intractable. Bayesian\nnetworks can represent any full joint probability and often do so concisely.\nDirected graph where each node has probability information representing a\nrandom variable (discrete or continuous). Arrows from parents to children. Each node\nhas probability given parents using parameters. Can represent using conditional\nprobability table (for discrete).\n\n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nSyntax of Bayes net is a DAG with local probability information.\nSemantics defines how syntax corresponds to joint distribution over network variables.\nNets are locally structured (linear rather than exponential growth).\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\nJoint probability over n boolean variables: 2^n. Bayes\nnet with n variables and maximum of k parents is O(n2^(k+1)). D-separation\nseparates nodes so that they are independent given other node. Every node in path\nmust be active in order for the path to be active. Inference by enumeration isn't\nefficient. Variable elimination iterweaves joining and marginalizing. Asymptotic\nrun time is still exponential, but average is better.\n\n\n## Module 11 Definitions\n* **Bayesian networks** - DAG used to represent dependencies among variables\n* **Conditioning case** - combination of values for parents\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\nWant to predict P(y|f1, f2, f3) where f is a feature.\nAssume features are independent given label. Before, was |y| |f|^n parameters, but\ngoes to n|f| |y| parameters. Query variable is class label. Need to estimate P(y),\nwhich is prior over labels. Then estimate P(fi|y) for each feature. Could estimate\nprobability of words using MLE, but results in zeros. Laplace smoothing adds one\npseudocount to every word. Could also add count of k to every word. Linear interpolation\ntakes into account both conditional and unconditional probabilities. For perceptron,\nhave input features x1...xn and internal weights w1...wn. take weighted sum of\nfeatures times weights and compare to threshold. If <= 0, output 0. If > 0,\noutput 1. Can also have bias term to change threshold, so predict from w.x+b.\nHigh bias means likely to fire, low bias means unlikely to fire. Forms\nseparating hyperplane. When training, only change when prediction is wrong. If so,\nw <- w + y*f(x). For multiclass, have weight vector for each class. Calculate score\nfor each class and choose one with highest. If wrong, increment true class weight\nby f(x) and decrement incorrect class weight by f(x). Will converge if linearly\nseparable with mistakes < k/delta^2 where k = num of features and delta is margin.\nIf nonseparable, won't converge. Could average weight vectors over time. SVM picks\nbest separating hyperplane. For nonlinear data, can transform features or project\ninto higher dimensional space.\n\n\n## Module 12 Definitions\n* **Backoff** - if haven't seen trigram, try bigram probability, then unigram\n* **Linear interpolation** - alpha*P(x|y) + (1-alpha)*P(x) where alpha is hyperparameter\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\nLogistic regression: P(+|x) = 1/(1+e^-(w.x+b)).\nThreshold of 0.5 to predict + or -. For sentiment classification, could count\npositive or negative words (from lexicon), could count instances of certain\nwords, etc. P(y|x) = y_hat^y (1-y_hat)^(1-y). Want to minimize cross entropy\nloss -log P(y|x). Convex, so global minimum. Use gradient descent.\nw_{t+1} <- w_t - eta * d\\dw [Loss]. Update weights simultaneously using gradient.\nEven if logistic regression classifies correctly, keeps pushing weights further.\nMinimize loss, not maximize classification accuracy. For stochastic gradient descent,\nuse datapoints one at a time instead of full set (batch). Can also use minibatch.\nNeed to regularize to avoid overfitting (L1 penalty=LASSO, L2=Ridge). For\nmulticlass logistic regression uses softmax over outputs of sigmoid with\nweight vector for each class to normalize to probability distribution.\ne^zj/(sum_i e^z_i). Feed forward neural network is fully connected with no\ncycles.Have input layer, hidden layers, and output layer. Perceptrons have\nstep function at w.x+b, and logistic regression is better for neurons because\nit has a smooth derivative. Could also use ReLU or tanh. Have a weight matrix\nfor each layer e.g. h = sigma(Wx+b). Make computation graph. For forward pass,\nplug in values for inputs and compute output. For backward pass, use chain rule\nfinding partial derivative of output with respect to each weight (chain together\npartials). Can then use gradient descent.\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 14 Lecture Notes\nN-grams represent words as sequence of letters\nor index in vocabulary list. Want to be able to represent synonyms, antonyms,\nconnotations, semantic roles, etc. Want support for entailment. Can make 'nym'\ndirectory manually that allows formilized logic-based inference. A lot of work\neven for single language. Could use vector space model. Words that are similar\nshould be close in vector space. Distributional hypothesis says that words in\nsimilar contexts are synonyms. Can make term-document matrix where each cell is\nhow many times word appears in document. Very sparse. Can compare documents\nby their column vectors (e.g. user query for plagiarism). Can also compare words\nby row vectors. Frequency impacts similarity measure, so normalize vectors.\nUse cosine distance (angle between vectors) 1 - u.v/||u||||v||.\nCould also have term-term matrix that tracks how often each word appears in\ncontext of another word. Can have long-term dependencies. Can also use\nparser to associate words together and create dependency arcs. Most frequent\nwords often aren't informative. TF-IDF (term frequency-inverse document frequency)\nreduces contributions of common words. Co-occurrence matrices are long sparse\nvectors. Want short and dense (word embeddings). Neural language models don't\nneed smoothing like n-grams. Can handle much longer history and generalize\ncontexts.Associate each word with a vector representation. Train model that\ntakes in k-gram of words and predicts probability over next words. Context\nwords are treated like word window. Embeddings are byproduct of leanred\nmodel but can then be used independently. Word2vec uses each neighboring\nword on both sides as positive example and generates k randomly sampled words\nfrom text as negative example, then trains on both examples. Predicts how\nlikely a word is to show up near given word. Don't care about answer, but\nuse to learn embeddings of words. Like implicitly supervised learning with\nno manual supervision. Skip-gram; treat target word and neighboring\ncontext as positive example, randomly sample other words in lexicon as negative\nexamples. Use logistic regression to classify positive and negative examples.\nSimilarity between target and context is t.c. Assume all context words are\nindependent given target. Learn two matrices W and C to learn word as both\ntarget and context. Can either use W and throw away C, or merge them. Can\nevaluate model based on how similar two words are compared to similarity\nwith different word. Concordant pairs = +1, discordant pairs = -1. By ordering,\nshows correlation with human judgement. With tight context window, most similar\nwords are words that are used in same context. With broader window, most similar\nwords are words that are topically similar. Can perform vector math using\nembeddings (like addition and subtraction). Can measure usage throughout time\nby training on historical texts. Can look at associations between different\nwords. Can test attitudes throughout time with different names or adjectives.\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}