{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "99905402-4402-42f6-91c6-ac6d7fc81374"
      },
      "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": 1,
      "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/",
          "height": 0
        },
        "outputId": "e4a81c00-fc9e-495d-e247-98526208b157"
      },
      "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": 2,
      "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": 3,
      "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 assigns P(s) to each possible s. $P(s'|s,a)$ is a transition model\"\"\"  + sample_equation \\\n",
        "+ \"\"\"MEU formalizes that an intelligent agent should do the right thing, but doesn't operatinalize it \\n\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\n",
        "the agent will achieve the highest possible performance score (averaged over all the possible\n",
        "environments)\"\"\"\n",
        "chapter16_2 =  \"\"\"Think of the set of outcomes for each action as a lottery $L=[p_1,S_1;p_2,S_2;...]$. Axions of utility \n",
        "theory:6 constraints\n",
        "- orderability:  Given any two lotteries, a rational agent must either prefer one or rate them as equally preferable\n",
        "- transitivity: $(A ≻ B) ∧ (B ≻ C) ⇒ (A ≻ C)$\n",
        "- continuity: $A ≻ B ≻ C ⇒ ∃ p  [p, A;  1 − p, C] ∼ B$\n",
        "- substitutability: $A ∼ B ⇒ [p, A;  1 − p, C] ∼ [p, B; 1 − p, C]$\n",
        "- monotonicity: $A ≻ B ⇒ (p > q⇔[p, A;  1 − p, B] ≻ [q, A;  1 − q, B])$\n",
        "- decomposability (no fun in gambling): $p, A;  1 − p, [q, B;  1 − q, C]] ∼ [p, A;  (1 − p)q, B;  (1 − p)(1 − q), C]$ \n",
        "\\n Rational preferences lead to existence of utility function+expected utility of a lottery. \n",
        "By observing a rational agent’s behavior, an observer can learn about the utility function\n",
        "that represents what the agent is actually trying to achieve (even if the agent doesn’t know\n",
        "it).\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"Assuming normalized utilities, the utility of is given by p in\n",
        "standard lottery $[p, u⊤;  (1 − p), u⊥]$ \\n\n",
        "decision theory is a normative thoery = how agent should act\\n\n",
        "descriptive theory = how actual agents really act\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"Actions are unreliable. Each step has a reward R. A sequential decision problem for a fully observable, stochastic environment\n",
        "with a Markovian transition model and additive rewards is called a Markov decision\n",
        "process (MDP). \\n Components = set of states, actions A(s), transition model, reward function\n",
        "- Optimal policy choose the action that maximizes the\n",
        "reward for the next step plus the expected discounted utility of the subsequent state $π∗(s) = argmax_{a∈A(s)}∑_{s′} P(s′|s, a)[R(s, a, s′) + γU(s′)]$ \\n\n",
        "- The utility of a state is the expected reward for the next\n",
        "transition plus the discounted utility of the next state, assuming that the agent chooses the optimal\n",
        "action: Bellman equation $U(s)=max_{a∈A(s)}∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$\n",
        "- Q-function/action-utility function: expected utility of taking a given action in a given state. $U(s) = max_a Q(s, a)$\n",
        "and $π∗(s) = argmax_a Q(s, a)$\n",
        "- Bellman eq for Q-function: $Q(s,a) = ∑_{s′}P(s′|s, a)[R(s, a, s′) + γ U(s′)]= ∑_{s′}P(s′|s, a)[R(s, a, s′) + γmax_a Q(s', a')]$\\n\n",
        "Representing MDPs\n",
        "- simplest=3d table size $|S|^2|A|$\n",
        "- sparse table $|S||A|$\n",
        "- dynamic bayesian networks(DDN)=factored representations\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"4 algo: 3 offline [value iteration, policy iteration, and linear programming] + online [Monte carlo planning]\\n\n",
        "- value iteration: bellman update $U_{i+1}(s)<--max_{a∈A(s)}∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$. \n",
        "update is assumed to be applied simultaneously to all the states at each iteration. \n",
        "Guarantee to each an equilitbrium: final U values are unique solutions, policy is optimal. Think of value iteration algo as\n",
        "propagating information through the state space by means of local updates. Proof using contraction\n",
        "- policy iteration: it's possible to get optimal policy even when U estimate is inaccurate. 2 steps terminates\n",
        "when policy improvment yields no change in U\n",
        "-- policy evaluation: given a policy $\\pi_i$, calculate $U_i = U^{πi}$\n",
        "-- policy improvement: calculate a new MEU policy $\\pi_{i+1}$using one-step look-ahead based on $U_i$\n",
        "-- simplified bellman eq. $Ui(s) = ∑_{s′}P(s′|s, πi(s))[R(s, πi(s), s′) + γUi(s′)]$\n",
        "-- all these eqs are linear (no max): runtime $O(n^3)$\n",
        "- Linear programming: we seek to\n",
        "minimize for all subject to the inequalities $U(s)\\geq ∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$ in polynomial time\n",
        "- online/expectiminimax/RTDP\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"Scales for utility and reward are arbitrary: affine transformation leaves the optimal decision unchanged.\n",
        "Sequential decision problems: incorporates \n",
        "utilities, uncertainty, and sensing, and include search/planning problems as special cases. \n",
        "Can solve using dynamic programming. Solution is called a policy $\\pi(s)$. A\n",
        "policy represents the agent function explicitly --> it's a simple\n",
        "reflex agent, computed from the information used for a utility-based agent \\n\n",
        "Additive discounted rewards with discount factor $Uh([s0, a0, s1, a1, s2,…]) = R(s0, a0, s1) + γR(s1, a1, s2) + γ\n",
        "2R(s2, a2, s3) + ⋯$ \\n\n",
        "Optimal policy is\n",
        "independent of the starting state\"\"\"\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\" : \"single number reflection of the agent's preference/desirablility of a state\",\n",
        "\"expected utility\" : \"average utility over the outcomes weighted by probability of each outcome\",\n",
        "\"Principle of maximum expected utility(MEU)\": \"a rational agent should choose action that maximizes the expected utility\",\n",
        "\"preference elicitation\": \"present choice to humans and use oberserved preference to define human's utility func\",\n",
        "\"insurance premium\": \"different bw EMV of a lottery vs its certianity equivalent\",\n",
        "\"optimizer's curse\": \"tendency for the estimated EU of best choice to be too high\",\n",
        "\"markovian\": \"probability of reaching s' from s depends only on s, not the history\",\n",
        "\"environtment history\": \"sequence of states and actions. Utility function depends on this\",\n",
        "\"finite horizon\": \"there is a fixed time N which after that nothing matters/game over\",\n",
        "\"nonstationary\": \"policy that depends on time\",\n",
        "\"contraction\": \"function appliedd to 2 inputs to produce outputs closer together\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "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": 1594
        },
        "outputId": "78029292-4c5e-4163-a715-fca9b185db55"
      },
      "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": 5,
      "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 assigns P(s) to each possible s. $P(s'|s,a)$ is a transition model $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ MEU formalizes that an intelligent agent should do the right thing, but doesn't operatinalize it \n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible\nenvironments)\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nThink of the set of outcomes for each action as a lottery $L=[p_1,S_1;p_2,S_2;...]$. Axions of utility \ntheory:6 constraints\n- orderability:  Given any two lotteries, a rational agent must either prefer one or rate them as equally preferable\n- transitivity: $(A ≻ B) ∧ (B ≻ C) ⇒ (A ≻ C)$\n- continuity: $A ≻ B ≻ C ⇒ ∃ p  [p, A;  1 − p, C] ∼ B$\n- substitutability: $A ∼ B ⇒ [p, A;  1 − p, C] ∼ [p, B; 1 − p, C]$\n- monotonicity: $A ≻ B ⇒ (p > q⇔[p, A;  1 − p, B] ≻ [q, A;  1 − q, B])$\n- decomposability (no fun in gambling): $p, A;  1 − p, [q, B;  1 − q, C]] ∼ [p, A;  (1 − p)q, B;  (1 − p)(1 − q), C]$ \n\n Rational preferences lead to existence of utility function+expected utility of a lottery. \nBy observing a rational agent’s behavior, an observer can learn about the utility function\nthat represents what the agent is actually trying to achieve (even if the agent doesn’t know\nit).\n\n\n## AIMA Chapter 16.3 Utility Functions\nAssuming normalized utilities, the utility of is given by p in\nstandard lottery $[p, u⊤;  (1 − p), u⊥]$ \n\ndecision theory is a normative thoery = how agent should act\n\ndescriptive theory = how actual agents really act\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nActions are unreliable. Each step has a reward R. A sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a Markov decision\nprocess (MDP). \n Components = set of states, actions A(s), transition model, reward function\n- Optimal policy choose the action that maximizes the\nreward for the next step plus the expected discounted utility of the subsequent state $π∗(s) = argmax_{a∈A(s)}∑_{s′} P(s′|s, a)[R(s, a, s′) + γU(s′)]$ \n\n- The utility of a state is the expected reward for the next\ntransition plus the discounted utility of the next state, assuming that the agent chooses the optimal\naction: Bellman equation $U(s)=max_{a∈A(s)}∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$\n- Q-function/action-utility function: expected utility of taking a given action in a given state. $U(s) = max_a Q(s, a)$\nand $π∗(s) = argmax_a Q(s, a)$\n- Bellman eq for Q-function: $Q(s,a) = ∑_{s′}P(s′|s, a)[R(s, a, s′) + γ U(s′)]= ∑_{s′}P(s′|s, a)[R(s, a, s′) + γmax_a Q(s', a')]$\n\nRepresenting MDPs\n- simplest=3d table size $|S|^2|A|$\n- sparse table $|S||A|$\n- dynamic bayesian networks(DDN)=factored representations\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n4 algo: 3 offline [value iteration, policy iteration, and linear programming] + online [Monte carlo planning]\n\n- value iteration: bellman update $U_{i+1}(s)<--max_{a∈A(s)}∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$. \nupdate is assumed to be applied simultaneously to all the states at each iteration. \nGuarantee to each an equilitbrium: final U values are unique solutions, policy is optimal. Think of value iteration algo as\npropagating information through the state space by means of local updates. Proof using contraction\n- policy iteration: it's possible to get optimal policy even when U estimate is inaccurate. 2 steps terminates\nwhen policy improvment yields no change in U\n-- policy evaluation: given a policy $\\pi_i$, calculate $U_i = U^{πi}$\n-- policy improvement: calculate a new MEU policy $\\pi_{i+1}$using one-step look-ahead based on $U_i$\n-- simplified bellman eq. $Ui(s) = ∑_{s′}P(s′|s, πi(s))[R(s, πi(s), s′) + γUi(s′)]$\n-- all these eqs are linear (no max): runtime $O(n^3)$\n- Linear programming: we seek to\nminimize for all subject to the inequalities $U(s)\\geq ∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$ in polynomial time\n- online/expectiminimax/RTDP\n\n\n## Module 8 Lecture Notes\nScales for utility and reward are arbitrary: affine transformation leaves the optimal decision unchanged.\nSequential decision problems: incorporates \nutilities, uncertainty, and sensing, and include search/planning problems as special cases. \nCan solve using dynamic programming. Solution is called a policy $\\pi(s)$. A\npolicy represents the agent function explicitly --> it's a simple\nreflex agent, computed from the information used for a utility-based agent \n\nAdditive discounted rewards with discount factor $Uh([s0, a0, s1, a1, s2,…]) = R(s0, a0, s1) + γR(s1, a1, s2) + γ\n2R(s2, a2, s3) + ⋯$ \n\nOptimal policy is\nindependent of the starting state\n\n## Module 8 Definitions\n* **Utility function** - single number reflection of the agent's preference/desirablility of a state\n* **Expected utility** - average utility over the outcomes weighted by probability of each outcome\n* **Principle of maximum expected utility(meu)** - a rational agent should choose action that maximizes the expected utility\n* **Preference elicitation** - present choice to humans and use oberserved preference to define human's utility func\n* **Insurance premium** - different bw EMV of a lottery vs its certianity equivalent\n* **Optimizer's curse** - tendency for the estimated EU of best choice to be too high\n* **Markovian** - probability of reaching s' from s depends only on s, not the history\n* **Environtment history** - sequence of states and actions. Utility function depends on this\n* **Finite horizon** - there is a fixed time N which after that nothing matters/game over\n* **Nonstationary** - policy that depends on time\n* **Contraction** - function appliedd to 2 inputs to produce outputs closer together\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 =  \"\"\"one-armed bandit = slot machine. n-armed bandit has n levers, behind each lever\n",
        "is a fixed but unknown probability distribution of winnings. The gambler must choose which lever to play on each successive coin.\n",
        "Tradeoff bw exploitation of the current best action to obtain rewards and exploration\n",
        "of previously unknown states and actions to gain information \\n\n",
        "Bandit problem: Each arm $M_i$ is a Markov reward process or MRP, that is, an MDP with only one\n",
        "possible action . It has states S, transition model $P_i(s'|s,a_i)$, and reward R.\n",
        "The arm defines a distribution over sequences of rewards where each $R_{i,t}$ is a random variable.\n",
        "The overall bandit problem is an MDP: the state space is given by the Cartesian product.\n",
        "The transition model updates the state of\n",
        "whichever arm is selected, according to its specific transition model, leaving the\n",
        "other arms unchanged\\n\n",
        "Optimal policy: pull the arm that has the highest Gittins index, then update the Gittins\n",
        "indices\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "- Model-based reinforcement learning: use a transition model of the environment to interpret reward signals and decide \n",
        "how to act. In partially observable environments, the transition\n",
        "model is also useful for state estimation. Model-based reinforcement\n",
        "learning systems often learn U(s) = sum of rewards from state s onward\n",
        "- Model-free RL: agent neither knows or learns a transition model for the envi BUT learns a more \n",
        "direct representation of how to behave\n",
        "-- action-utility learning[Q-learning]\n",
        "-- policy search/reflex agent\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"Passive learning agent:\n",
        "fixed policy, the agent tries to learn $U^\\pi(s)=$the expected total discounted reward if policy $\\pi$\n",
        "is executed beginning in state s. Similar to policy evaluation task\n",
        "$U^\\pi(s) = E[∑^\\infty_{t=0}γ^tR(St,π(St),St+1)]$ \n",
        "- direct utility estimation:  reduced reinforcement learning to a standard supervised learning\n",
        "problem in which each example is a (state, reward-to-go) pair BUT it ignores\n",
        " The utility of a state is determined by the reward and the expected utility of\n",
        "the successor states (bellman), leading to too large hypothesis space & slow convergence\n",
        "- adaptive dymanic programming(ADP): takes advantage of the constraints\n",
        "among the utilities of states by learning the transition model that connects them and solving\n",
        "the corresponding Markov decision process using dynamic programming. Plugging in learned P and R\n",
        "- temporal-difference learning: use the observed\n",
        "transitions to adjust the utilities of the observed states so that they agree with the constraint\n",
        "equations. Doesn't learn quite as fast as the ADP agent and shows much\n",
        "higher variability, but it is much simpler and requires much less computation per\n",
        "observation. TD equation $U\n",
        "π\n",
        "(s) ← U\n",
        "π\n",
        "(s) + α[R(s,π(s),s\n",
        "′\n",
        ") + γUπ\n",
        "(s\n",
        "′\n",
        ") − U\n",
        "π\n",
        "(s)], \\\\alpha$ is the learning rate. Each adjustment made by ADP could be seen, from the TD point of view, as a result of a\n",
        "pseudoexperience generated by simulating the current transition model\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"decide what actions to take. Active dymanic programming(ADP) agent\n",
        "- need to learn a complete transition model P for all actions. \n",
        "- agent has a choice of actions: U defined by the optimal policy/obey bellman eq.\n",
        "- at each step? optimal policy?\n",
        "The greedy agent has overlooked the fact that actions do more than provide rewards; they\n",
        "also provide information in the form of percepts in the resulting states.\n",
        "The use of $U+$means that the benefits of exploration are propagated back from the edges of\n",
        "unexplored regions, so that actions that lead toward unexplored regions are weighted more\n",
        "highly, rather than just actions that are themselves unfamiliar \\n\n",
        "Safe exploration\n",
        "- bayesian reinforcement learning: assume a prior $P(h)$. Posterior $P(h|e)$, we have $π\n",
        "∗ = argmax_π ∑_hP(h|e)U_π^h$. Exploration POMDP\n",
        "- robust control theory:  allows for a set of possible\n",
        "models $H$ without assigning probabilities to them, and defines an optimal robust policy as\n",
        "one that gives the best outcome in the worst case over $H$. Like agent vs adversary. Lead to \n",
        "conservative behavior\\n\n",
        "TD Q-learning/SARSA: $Q(s,a) ← Q(s,a) + α[R(s,a,s′) + γ max_{a′}Q(s′,a′) − Q(s,a)]$avoids the need for a model by learning an action-utility function Q\n",
        " instead of U. But cant look into the future, may have difficulty when rewards are sparse\n",
        "and long action sequences must be constructed to reach them. Qlearning is off-policy but SARSA is on-policy\n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\"function approximation = the process of constructing a compact approximation of the true utility\n",
        "function or Q-function = saves space\n",
        "- approximating direct utility estimation: widrow-hoff rule, delta rule\n",
        "- approximating TD learning \\n\n",
        "credit assigment problem: figure out what it did wrong.\\n\n",
        "Reward shaping: supply the agent with \n",
        "additional rewards[pseudorewards] for making progress. We can create new reward function \n",
        "$R\n",
        "′\n",
        "(s,a,s\n",
        "′\n",
        ") = R(s,a,s\n",
        "′\n",
        ") + γΦ(s\n",
        "′\n",
        ") − Φ(s)$ \\n\n",
        "and hierarchical RL are helpful for learning complex behaviors esp. with sparse rewards\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" key idea: keep twiddling the policy as long as its performance improves, then stop \\n\n",
        "Policy is a discontinuous function, so policy search method often use a stochasitc policy $π_θ(s,a)$/softmax function\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"Goal = maximize expected sum of rewards BUT in RL the agent is \n",
        "not given the MDP to solve. Instead, it's in the MDP. May not know the transition model or the reward function \\n\n",
        "regret = u(possible action) - u(action taken)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Gittins index\" : \"(of M) describes the maximum obtainable utility per unit of discounted time\",\n",
        "\"passive reinforcement learning\": \"learn the utility of states as the agent's policy is fixed\",\n",
        "\"passive reinforcement learning\": \"agent has to figure out what to do\",\n",
        "\"GLIE\": \"greedy in the limit of infinite exploration\",\n",
        "\"SARSA\": \"similar to Q-learning but update with the Q-value of action a' that is actually taken (not max a')\",\n",
        "\"as\": \"as\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1463
        },
        "cellView": "form",
        "outputId": "5fbcee36-1d87-4303-c4a2-e0fc6ddd695a"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\none-armed bandit = slot machine. n-armed bandit has n levers, behind each lever\nis a fixed but unknown probability distribution of winnings. The gambler must choose which lever to play on each successive coin.\nTradeoff bw exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information \n\nBandit problem: Each arm $M_i$ is a Markov reward process or MRP, that is, an MDP with only one\npossible action . It has states S, transition model $P_i(s'|s,a_i)$, and reward R.\nThe arm defines a distribution over sequences of rewards where each $R_{i,t}$ is a random variable.\nThe overall bandit problem is an MDP: the state space is given by the Cartesian product.\nThe transition model updates the state of\nwhichever arm is selected, according to its specific transition model, leaving the\nother arms unchanged\n\nOptimal policy: pull the arm that has the highest Gittins index, then update the Gittins\nindices\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- Model-based reinforcement learning: use a transition model of the environment to interpret reward signals and decide \nhow to act. In partially observable environments, the transition\nmodel is also useful for state estimation. Model-based reinforcement\nlearning systems often learn U(s) = sum of rewards from state s onward\n- Model-free RL: agent neither knows or learns a transition model for the envi BUT learns a more \ndirect representation of how to behave\n-- action-utility learning[Q-learning]\n-- policy search/reflex agent\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nPassive learning agent:\nfixed policy, the agent tries to learn $U^\\pi(s)=$the expected total discounted reward if policy $\\pi$\nis executed beginning in state s. Similar to policy evaluation task\n$U^\\pi(s) = E[∑^\\infty_{t=0}γ^tR(St,π(St),St+1)]$ \n- direct utility estimation:  reduced reinforcement learning to a standard supervised learning\nproblem in which each example is a (state, reward-to-go) pair BUT it ignores\n The utility of a state is determined by the reward and the expected utility of\nthe successor states (bellman), leading to too large hypothesis space & slow convergence\n- adaptive dymanic programming(ADP): takes advantage of the constraints\namong the utilities of states by learning the transition model that connects them and solving\nthe corresponding Markov decision process using dynamic programming. Plugging in learned P and R\n- temporal-difference learning: use the observed\ntransitions to adjust the utilities of the observed states so that they agree with the constraint\nequations. Doesn't learn quite as fast as the ADP agent and shows much\nhigher variability, but it is much simpler and requires much less computation per\nobservation. TD equation $U\nπ\n(s) ← U\nπ\n(s) + α[R(s,π(s),s\n′\n) + γUπ\n(s\n′\n) − U\nπ\n(s)], \\alpha$ is the learning rate. Each adjustment made by ADP could be seen, from the TD point of view, as a result of a\npseudoexperience generated by simulating the current transition model\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\ndecide what actions to take. Active dymanic programming(ADP) agent\n- need to learn a complete transition model P for all actions. \n- agent has a choice of actions: U defined by the optimal policy/obey bellman eq.\n- at each step? optimal policy?\nThe greedy agent has overlooked the fact that actions do more than provide rewards; they\nalso provide information in the form of percepts in the resulting states.\nThe use of $U+$means that the benefits of exploration are propagated back from the edges of\nunexplored regions, so that actions that lead toward unexplored regions are weighted more\nhighly, rather than just actions that are themselves unfamiliar \n\nSafe exploration\n- bayesian reinforcement learning: assume a prior $P(h)$. Posterior $P(h|e)$, we have $π\n∗ = argmax_π ∑_hP(h|e)U_π^h$. Exploration POMDP\n- robust control theory:  allows for a set of possible\nmodels $H$ without assigning probabilities to them, and defines an optimal robust policy as\none that gives the best outcome in the worst case over $H$. Like agent vs adversary. Lead to \nconservative behavior\n\nTD Q-learning/SARSA: $Q(s,a) ← Q(s,a) + α[R(s,a,s′) + γ max_{a′}Q(s′,a′) − Q(s,a)]$avoids the need for a model by learning an action-utility function Q\n instead of U. But cant look into the future, may have difficulty when rewards are sparse\nand long action sequences must be constructed to reach them. Qlearning is off-policy but SARSA is on-policy\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nfunction approximation = the process of constructing a compact approximation of the true utility\nfunction or Q-function = saves space\n- approximating direct utility estimation: widrow-hoff rule, delta rule\n- approximating TD learning \n\ncredit assigment problem: figure out what it did wrong.\n\nReward shaping: supply the agent with \nadditional rewards[pseudorewards] for making progress. We can create new reward function \n$R\n′\n(s,a,s\n′\n) = R(s,a,s\n′\n) + γΦ(s\n′\n) − Φ(s)$ \n\nand hierarchical RL are helpful for learning complex behaviors esp. with sparse rewards\n\n\n## Module 9 Lecture Notes\nGoal = maximize expected sum of rewards BUT in RL the agent is \nnot given the MDP to solve. Instead, it's in the MDP. May not know the transition model or the reward function \n\nregret = u(possible action) - u(action taken)\n\n\n\n## Module 9 Definitions\n* **Gittins index** - (of M) describes the maximum obtainable utility per unit of discounted time\n* **Passive reinforcement learning** - agent has to figure out what to do\n* **Glie** - greedy in the limit of infinite exploration\n* **Sarsa** - similar to Q-learning but update with the Q-value of action a' that is actually taken (not max a')\n* **As** - as\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\"Decision theory = probability theory + utility theory\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\"$P(a ∧ b) = P(a | b)P(b)$ Bayes' rule: $P(a | b) = \\\\frac{P(b|a)P(b)}{P(a)}$\"\"\"\n",
        "chapter12_6 = \"\"\"$P(Cause, Effect_1,… , Effect_n) = P(Cause)∏_i P(Effect_i| Cause)$ \\n\n",
        "Then the standard method for inference from the joint\n",
        "distribution $P(Cause | e) = α∑_y P(Cause, e, y)= α P(Cause)∏_j P (ej∣Cause)$.  For each possible cause, multiply the prior probability of the cause by the product\n",
        "of the conditional probabilities of the observed effects given the cause; then normalize the\n",
        "result. The run time of this calculation is linear in the number of observed effects and does\n",
        "not depend on the number of unobserved effects\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" “Out of the times we saw the history h, how many times was it followed by\n",
        "the word w. $P(w1:n) = P(w1)P(w2|w1)P(w3|w1:2)...P(wn|w1:n−1)$ \\n\n",
        "n-gram model intuition: approximate the history by just the last few words. Bigram assumes $P(w_n|w_{1:n−1}) ≈ P(w_n|w_{n−1})$.\n",
        "Generalize into n-gram (looks n−1 words into the past)\"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Perplexity:weighted average branching factor $PP(W) = P(w1w2 ...wN)^{-1/N}$\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\"Laplace smoothing(add-one), add-k\"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "stationary process = the conditional probability table does not change over time \\n\n",
        "P(Toothache | Detect , Cavity) = P(Toothache | Cavity) \\n\n",
        "P(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity)\\n\n",
        "Conditionally independent: $P(x,y|z)=p(x|z)P(y|z)$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Markov assumption\" : \"probability of a word depends only on the previous word\",\n",
        "\"perplexity\":\"e inverse probability of the test set, normalized by the number of words\",\n",
        "\"perplexity\":\"asdf\",\n",
        "\"perplexity\":\"asdf\",\n",
        "\"perplexity\":\"asdf\",\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1294
        },
        "cellView": "form",
        "outputId": "3755ffc2-452c-4ab3-a32a-0f98ff17170b"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nDecision theory = probability theory + utility theory\n\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$P(a ∧ b) = P(a | b)P(b)$ Bayes' rule: $P(a | b) = \\frac{P(b|a)P(b)}{P(a)}$\n\n## AIMA Chapter 12.6 Naive Bayes Models\n$P(Cause, Effect_1,… , Effect_n) = P(Cause)∏_i P(Effect_i| Cause)$ \n\nThen the standard method for inference from the joint\ndistribution $P(Cause | e) = α∑_y P(Cause, e, y)= α P(Cause)∏_j P (ej∣Cause)$.  For each possible cause, multiply the prior probability of the cause by the product\nof the conditional probabilities of the observed effects given the cause; then normalize the\nresult. The run time of this calculation is linear in the number of observed effects and does\nnot depend on the number of unobserved effects\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n “Out of the times we saw the history h, how many times was it followed by\nthe word w. $P(w1:n) = P(w1)P(w2|w1)P(w3|w1:2)...P(wn|w1:n−1)$ \n\nn-gram model intuition: approximate the history by just the last few words. Bigram assumes $P(w_n|w_{1:n−1}) ≈ P(w_n|w_{n−1})$.\nGeneralize into n-gram (looks n−1 words into the past)\n\n## SLP Chapter 3.2 Evaluating Language Models\n Perplexity:weighted average branching factor $PP(W) = P(w1w2 ...wN)^{-1/N}$\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\nLaplace smoothing(add-one), add-k\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nstationary process = the conditional probability table does not change over time \n\nP(Toothache | Detect , Cavity) = P(Toothache | Cavity) \n\nP(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity)\n\nConditionally independent: $P(x,y|z)=p(x|z)P(y|z)$\n\n\n## Module 10 Definitions\n* **Markov assumption** - probability of a word depends only on the previous word\n* **Perplexity** - asdf\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Inference by Enumeration (slow:  join up the whole joint distribution before you sum out the hidden variables)\n",
        " vs. Variable Elimination\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Conditional independence is our most basic and robust form\n",
        "of knowledge about uncertain environments. Bayes’ nets: a technique for describing complex joint\n",
        "distributions (models) using simple, local\n",
        "distributions (conditional probabilities). Bayes’ nets implicitly encode joint distributions \\n\n",
        "Arrow: Topology really encodes conditional independence. BNs advantage: huge space savings $2^N \\implies O(N*2^{k+1})$,\n",
        "easier to elicit local CPTs, faster to answer queries. \\n\n",
        "D-separation\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"CPT\" : \"conditional probability table\",    \n",
        "\"concept\" : \"definition\", \n",
        "}\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 512
        },
        "cellView": "form",
        "outputId": "c21ca258-ab6f-48f9-fc01-3ce1514b368f"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Inference by Enumeration (slow:  join up the whole joint distribution before you sum out the hidden variables)\n vs. Variable Elimination\n\n## Module 11 Lecture Notes\n Conditional independence is our most basic and robust form\nof knowledge about uncertain environments. Bayes’ nets: a technique for describing complex joint\ndistributions (models) using simple, local\ndistributions (conditional probabilities). Bayes’ nets implicitly encode joint distributions \n\nArrow: Topology really encodes conditional independence. BNs advantage: huge space savings $2^N \\implies O(N*2^{k+1})$,\neasier to elicit local CPTs, faster to answer queries. \n\nD-separation\n\n\n## Module 11 Definitions\n* **Cpt** - conditional probability table\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" $P(X \n",
        "1\n",
        "​\n",
        " ,X \n",
        "2\n",
        "​\n",
        " ,X \n",
        "3\n",
        "​\n",
        " ,Y)=P(Y)P(X \n",
        "1\n",
        "​\n",
        " ∣Y)P(X \n",
        "2\n",
        "​\n",
        " ∣Y)P(X \n",
        "3\n",
        "​\n",
        " ∣Y)$\"\"\"\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 = \"\"\" The naïve Bayes assumption takes all features to be independent given\n",
        "the class label. What do we need in order to use Naïve Bayes?\n",
        "- inference method: use standard inference to compute $ P(Y|F_1…F_n)$\n",
        "- estimates of local conditional probability tables:\n",
        "-- $P(Y)$, the prior over labels\n",
        "-- $P(F_i|Y)$. These probs are called parameters $\\\\theta$ \\n\n",
        "Parameter estimation: elicitation[ask human] or empirical[use training data]\\n\n",
        "Relative frequencies are the maximum likelihood estimates $\\\\theta_{ML}=argmax_{\\\\theta}P(X|\\\\theta)$. \n",
        "Laplace smoothing, Linear interpolation \\n\n",
        "PERCEPTRONS\\n\n",
        "Start with weights = 0. For each training instance\n",
        "- classify with current weights. $y=+1, w\\cdot f(x)\\geq 0$ -1 otherwise OR \n",
        "multiclass $y=argmax_y w_y\\cdot f(x)$\n",
        "- if correct, no change\n",
        "- if wrong, adjust the weight vector $w=w+y*\\cdot f$ (subtract if $y*=-1$) OR \n",
        "multiclass lower/raise score of wrong/right answer. $w_y=w_y-f(x), w_y*=w_y*+f(x)$\\n\n",
        "Properties\n",
        "- $bias = -threshold$\n",
        "- Convergence: if the training is separable, perceptron\n",
        "will eventually converge (binary case)\n",
        "- Mistake Bound: the maximum number of mistakes related to the margin or degree of\n",
        "separability. mistakes $< k/\\\\delta^2$\n",
        "- solution: maximum step size cap the maximum possible value of t with some\n",
        "constant C. Converges faster, better on noisy data\\n\n",
        "SVM: find the separator with max margin\\n\n",
        "- only support vectors matter\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"induction\" : \"going from observations to a general rule, can be incorrect\",    \n",
        "\"concept\" : \"definition\",   \n",
        "\"concept\" : \"definition\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1727
        },
        "outputId": "fa89c0a1-5bde-4dc0-b049-9d28e82fa40b"
      },
      "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 19.1 \", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 \", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 \", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 \", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 \", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 \", 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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 \n Your summary here \n\n## AIMA Chapter 19.2 \n Your summary here \n\n## AIMA Chapter 19.3 \n Your summary here \n\n## AIMA Chapter 19.4 \n Your summary here \n\n## AIMA Chapter 19.5 \n Your summary here \n\n## AIMA Chapter 19.6 \n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n $P(X \n1\n​\n ,X \n2\n​\n ,X \n3\n​\n ,Y)=P(Y)P(X \n1\n​\n ∣Y)P(X \n2\n​\n ∣Y)P(X \n3\n​\n ∣Y)$\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n The naïve Bayes assumption takes all features to be independent given\nthe class label. What do we need in order to use Naïve Bayes?\n- inference method: use standard inference to compute $ P(Y|F_1…F_n)$\n- estimates of local conditional probability tables:\n-- $P(Y)$, the prior over labels\n-- $P(F_i|Y)$. These probs are called parameters $\\theta$ \n\nParameter estimation: elicitation[ask human] or empirical[use training data]\n\nRelative frequencies are the maximum likelihood estimates $\\theta_{ML}=argmax_{\\theta}P(X|\\theta)$. \nLaplace smoothing, Linear interpolation \n\nPERCEPTRONS\n\nStart with weights = 0. For each training instance\n- classify with current weights. $y=+1, w\\cdot f(x)\\geq 0$ -1 otherwise OR \nmulticlass $y=argmax_y w_y\\cdot f(x)$\n- if correct, no change\n- if wrong, adjust the weight vector $w=w+y*\\cdot f$ (subtract if $y*=-1$) OR \nmulticlass lower/raise score of wrong/right answer. $w_y=w_y-f(x), w_y*=w_y*+f(x)$\n\nProperties\n- $bias = -threshold$\n- Convergence: if the training is separable, perceptron\nwill eventually converge (binary case)\n- Mistake Bound: the maximum number of mistakes related to the margin or degree of\nseparability. mistakes $< k/\\delta^2$\n- solution: maximum step size cap the maximum possible value of t with some\nconstant C. Converges faster, better on noisy data\n\nSVM: find the separator with max margin\n\n- only support vectors matter\n \n\n## Module 12 Definitions\n* **Induction** - going from observations to a general rule, can be incorrect\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" 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\\n \n",
        "- given an instance x computes the probability $P(y = 1|x)$\n",
        "- sigmoid function $y=1/(1+e^{-z})=1/(1+e^{-(wx+b)})$\n",
        "- loss function: ie. MSE, cross entropy loss[negative log likelihood loss]\n",
        "- Gradient descent is a method that finds a minimum of a function by figuring out in\n",
        "which direction (in the space of the parameters θ) the function’s slope is rising the most\n",
        "steeply, and moving in the opposite direction\n",
        "- loss function of logistic regression is convex = one minimum\n",
        "- Stochastic gradient descent chooses a single random example at a time and updates\n",
        "its weights on that example. As a result the updates can fluctuate.\n",
        "- Alternative: batch training computes the gradient over the entire dataset.\n",
        "This gives a much better estimate of which direction to move the weights but takes a\n",
        "long time to compute\n",
        "- compromise: mini-batch training ie. batch of 512/1024 \\n\n",
        "NEURAL NETWORK\\n\n",
        "- sigmoid neurons: solve a problem that a small change in the w or b of single perceptron in the network\n",
        "can causes output flip from 0 to 1\n",
        "- smoothness! small changes in the weights wj and in the bias b will\n",
        "produce a small change the output from the neuron\n",
        "- activation function: nonlinear ie. sigmoid, tanh (steeper), ReLU\n",
        "- The simplest kind of NN is the Feed-Forward Neural Network\n",
        "- output of hidden layer $h = σ(Wx+b)$, $z=Uh$, $y=softmax(z)$ softmax normalizes the output and turns it into a\n",
        "probability distribution\n",
        "- error backpropagation algorithm: procedure called backward differentiation, which depends on the notion of\n",
        "computation graphs \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1401
        },
        "cellView": "form",
        "outputId": "7186cf3c-38e2-42e8-8061-35594997f2aa"
      },
      "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": 15,
      "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\n \n- given an instance x computes the probability $P(y = 1|x)$\n- sigmoid function $y=1/(1+e^{-z})=1/(1+e^{-(wx+b)})$\n- loss function: ie. MSE, cross entropy loss[negative log likelihood loss]\n- Gradient descent is a method that finds a minimum of a function by figuring out in\nwhich direction (in the space of the parameters θ) the function’s slope is rising the most\nsteeply, and moving in the opposite direction\n- loss function of logistic regression is convex = one minimum\n- Stochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\n- Alternative: batch training computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute\n- compromise: mini-batch training ie. batch of 512/1024 \n\nNEURAL NETWORK\n\n- sigmoid neurons: solve a problem that a small change in the w or b of single perceptron in the network\ncan causes output flip from 0 to 1\n- smoothness! small changes in the weights wj and in the bias b will\nproduce a small change the output from the neuron\n- activation function: nonlinear ie. sigmoid, tanh (steeper), ReLU\n- The simplest kind of NN is the Feed-Forward Neural Network\n- output of hidden layer $h = σ(Wx+b)$, $z=Uh$, $y=softmax(z)$ softmax normalizes the output and turns it into a\nprobability distribution\n- error backpropagation algorithm: procedure called backward differentiation, which depends on the notion of\ncomputation graphs \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 = \"\"\" word meaning: we want to encode\n",
        "1. Synonyms – words that have similar meanings\n",
        "2. Antonyms – words that have opposite meanings\n",
        "3. Connotations – words that are positive or negative\n",
        "4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\n",
        "purchasing event\n",
        "5. Support for entailment\n",
        "- distributional word similarity: Intuition for algorithm:\n",
        "Two words are similar if they have similar word contexts\n",
        "- vector space model\n",
        "- term-document matrix: each column vector represents a document, each row represents a term. Value\n",
        "in a cell shows how often that term occurred in that document. Measure document similarity = comparing columns.\n",
        "- term-term [term-context] matrix: length of vector is now $|V|$.\n",
        "Context window\n",
        "- co-occurence matrix is long and sparse. Alternative: learn vectors that are short and dense\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\"Instead of raw counts, it’s common to transform vectors using TF-IDF or PPMI \n",
        "- TF[how often a word occured in a doc] * IDF[1/number of docs that it occured in] \\n\n",
        "language modeling\n",
        "- goal: learn a function that returns joint probability\n",
        "- difficulty: too many parameters (curse of dimensionality), In n-gram-based models we fail to generalize to related words/word\n",
        "sequences that we have observed\n",
        "- chain rule: assume that next word only depends on the prev n-1 words $P(w_1w_2...w_t)=\\Pi P(w_t|w_1w_2...w_{t-1})$\n",
        "- unseen sequences: \n",
        "-- back off\n",
        "-- smoothing/interpolation\n",
        "\"\"\"\n",
        "slp_chapter6_3 = \"\"\"Neural Language models have several advantages over n-gram LMs:\n",
        "1. They don’t need smoothing\n",
        "2. They can handle much longer histories.\n",
        "3. They can generalize over contexts of similar words.\n",
        "4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n",
        "5. byproduct = word embeddings\n",
        "Disadvantage: slower to train than traditional n-gram LMs\\n\n",
        "Neural LMs\n",
        "1. Associate each word in the vocabulary with a vector-representation, thereby\n",
        "creating a notion of similarity between words.\n",
        "2. Express the joint probability function of a word sequence in terms of the word\n",
        "vectors for the words in that sequence.\n",
        "3. Simultaneously learn the word vectors and the parameters of the function.\n",
        "\"\"\"\n",
        "slp_chapter6_4 = \"\"\"Word2Vec:\n",
        "- Learn embeddings as part of the process\n",
        "of word prediction.\n",
        "- Train a classifier to predict neighboring\n",
        "words\n",
        "- Inspired by NN LMs. learn dense embeddings for\n",
        "the words in the training corpus.\n",
        "- fast and easy to train (than SVD)\n",
        "- Predict each neighboring word in a context window of 2C of surrounding words. Use \"negative sampling\" of \n",
        "random noise words for training. take the learned classifier weights as\n",
        "the word embeddings\n",
        "\"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1995
        },
        "outputId": "ae4d592d-9145-4ecf-db54-7c2c02786820"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 17,
      "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 word meaning: we want to encode\n1. Synonyms – words that have similar meanings\n2. Antonyms – words that have opposite meanings\n3. Connotations – words that are positive or negative\n4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\npurchasing event\n5. Support for entailment\n- distributional word similarity: Intuition for algorithm:\nTwo words are similar if they have similar word contexts\n- vector space model\n- term-document matrix: each column vector represents a document, each row represents a term. Value\nin a cell shows how often that term occurred in that document. Measure document similarity = comparing columns.\n- term-term [term-context] matrix: length of vector is now $|V|$.\nContext window\n- co-occurence matrix is long and sparse. Alternative: learn vectors that are short and dense\n\n\n## SLP Chapter 6.2 Vector Semantics\nInstead of raw counts, it’s common to transform vectors using TF-IDF or PPMI \n- TF[how often a word occured in a doc] * IDF[1/number of docs that it occured in] \n\nlanguage modeling\n- goal: learn a function that returns joint probability\n- difficulty: too many parameters (curse of dimensionality), In n-gram-based models we fail to generalize to related words/word\nsequences that we have observed\n- chain rule: assume that next word only depends on the prev n-1 words $P(w_1w_2...w_t)=\\Pi P(w_t|w_1w_2...w_{t-1})$\n- unseen sequences: \n-- back off\n-- smoothing/interpolation\n\n\n## SLP Chapter 6.3 Words and Vectors\nNeural Language models have several advantages over n-gram LMs:\n1. They don’t need smoothing\n2. They can handle much longer histories.\n3. They can generalize over contexts of similar words.\n4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n5. byproduct = word embeddings\nDisadvantage: slower to train than traditional n-gram LMs\n\nNeural LMs\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n3. Simultaneously learn the word vectors and the parameters of the function.\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\nWord2Vec:\n- Learn embeddings as part of the process\nof word prediction.\n- Train a classifier to predict neighboring\nwords\n- Inspired by NN LMs. learn dense embeddings for\nthe words in the training corpus.\n- fast and easy to train (than SVD)\n- Predict each neighboring word in a context window of 2C of surrounding words. Use \"negative sampling\" of \nrandom noise words for training. take the learned classifier weights as\nthe word embeddings\n\n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\nLogistic regression\n \n- given an instance x computes the probability $P(y = 1|x)$\n- sigmoid function $y=1/(1+e^{-z})=1/(1+e^{-(wx+b)})$\n- loss function: ie. MSE, cross entropy loss[negative log likelihood loss]\n- Gradient descent is a method that finds a minimum of a function by figuring out in\nwhich direction (in the space of the parameters θ) the function’s slope is rising the most\nsteeply, and moving in the opposite direction\n- loss function of logistic regression is convex = one minimum\n- Stochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\n- Alternative: batch training computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute\n- compromise: mini-batch training ie. batch of 512/1024 \n\nNEURAL NETWORK\n\n- sigmoid neurons: solve a problem that a small change in the w or b of single perceptron in the network\ncan causes output flip from 0 to 1\n- smoothness! small changes in the weights wj and in the bias b will\nproduce a small change the output from the neuron\n- activation function: nonlinear ie. sigmoid, tanh (steeper), ReLU\n- The simplest kind of NN is the Feed-Forward Neural Network\n- output of hidden layer $h = σ(Wx+b)$, $z=Uh$, $y=softmax(z)$ softmax normalizes the output and turns it into a\nprobability distribution\n- error backpropagation algorithm: procedure called backward differentiation, which depends on the notion of\ncomputation graphs \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": 9941
        },
        "id": "T3cm1WV542_a",
        "outputId": "ca51ed5c-56e9-4d36-983a-d8bbd9c0486c"
      },
      "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": 18,
      "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 assigns P(s) to each possible s. $P(s'|s,a)$ is a transition model $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ MEU formalizes that an intelligent agent should do the right thing, but doesn't operatinalize it \n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible\nenvironments)\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nThink of the set of outcomes for each action as a lottery $L=[p_1,S_1;p_2,S_2;...]$. Axions of utility \ntheory:6 constraints\n- orderability:  Given any two lotteries, a rational agent must either prefer one or rate them as equally preferable\n- transitivity: $(A ≻ B) ∧ (B ≻ C) ⇒ (A ≻ C)$\n- continuity: $A ≻ B ≻ C ⇒ ∃ p  [p, A;  1 − p, C] ∼ B$\n- substitutability: $A ∼ B ⇒ [p, A;  1 − p, C] ∼ [p, B; 1 − p, C]$\n- monotonicity: $A ≻ B ⇒ (p > q⇔[p, A;  1 − p, B] ≻ [q, A;  1 − q, B])$\n- decomposability (no fun in gambling): $p, A;  1 − p, [q, B;  1 − q, C]] ∼ [p, A;  (1 − p)q, B;  (1 − p)(1 − q), C]$ \n\n Rational preferences lead to existence of utility function+expected utility of a lottery. \nBy observing a rational agent’s behavior, an observer can learn about the utility function\nthat represents what the agent is actually trying to achieve (even if the agent doesn’t know\nit).\n\n\n## AIMA Chapter 16.3 Utility Functions\nAssuming normalized utilities, the utility of is given by p in\nstandard lottery $[p, u⊤;  (1 − p), u⊥]$ \n\ndecision theory is a normative thoery = how agent should act\n\ndescriptive theory = how actual agents really act\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\nActions are unreliable. Each step has a reward R. A sequential decision problem for a fully observable, stochastic environment\nwith a Markovian transition model and additive rewards is called a Markov decision\nprocess (MDP). \n Components = set of states, actions A(s), transition model, reward function\n- Optimal policy choose the action that maximizes the\nreward for the next step plus the expected discounted utility of the subsequent state $π∗(s) = argmax_{a∈A(s)}∑_{s′} P(s′|s, a)[R(s, a, s′) + γU(s′)]$ \n\n- The utility of a state is the expected reward for the next\ntransition plus the discounted utility of the next state, assuming that the agent chooses the optimal\naction: Bellman equation $U(s)=max_{a∈A(s)}∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$\n- Q-function/action-utility function: expected utility of taking a given action in a given state. $U(s) = max_a Q(s, a)$\nand $π∗(s) = argmax_a Q(s, a)$\n- Bellman eq for Q-function: $Q(s,a) = ∑_{s′}P(s′|s, a)[R(s, a, s′) + γ U(s′)]= ∑_{s′}P(s′|s, a)[R(s, a, s′) + γmax_a Q(s', a')]$\n\nRepresenting MDPs\n- simplest=3d table size $|S|^2|A|$\n- sparse table $|S||A|$\n- dynamic bayesian networks(DDN)=factored representations\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n4 algo: 3 offline [value iteration, policy iteration, and linear programming] + online [Monte carlo planning]\n\n- value iteration: bellman update $U_{i+1}(s)<--max_{a∈A(s)}∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$. \nupdate is assumed to be applied simultaneously to all the states at each iteration. \nGuarantee to each an equilitbrium: final U values are unique solutions, policy is optimal. Think of value iteration algo as\npropagating information through the state space by means of local updates. Proof using contraction\n- policy iteration: it's possible to get optimal policy even when U estimate is inaccurate. 2 steps terminates\nwhen policy improvment yields no change in U\n-- policy evaluation: given a policy $\\pi_i$, calculate $U_i = U^{πi}$\n-- policy improvement: calculate a new MEU policy $\\pi_{i+1}$using one-step look-ahead based on $U_i$\n-- simplified bellman eq. $Ui(s) = ∑_{s′}P(s′|s, πi(s))[R(s, πi(s), s′) + γUi(s′)]$\n-- all these eqs are linear (no max): runtime $O(n^3)$\n- Linear programming: we seek to\nminimize for all subject to the inequalities $U(s)\\geq ∑_{s′}P(s′|s,a)[R(s, a,s′)+ γ U(s′)]$ in polynomial time\n- online/expectiminimax/RTDP\n\n\n## Module 8 Lecture Notes\nScales for utility and reward are arbitrary: affine transformation leaves the optimal decision unchanged.\nSequential decision problems: incorporates \nutilities, uncertainty, and sensing, and include search/planning problems as special cases. \nCan solve using dynamic programming. Solution is called a policy $\\pi(s)$. A\npolicy represents the agent function explicitly --> it's a simple\nreflex agent, computed from the information used for a utility-based agent \n\nAdditive discounted rewards with discount factor $Uh([s0, a0, s1, a1, s2,…]) = R(s0, a0, s1) + γR(s1, a1, s2) + γ\n2R(s2, a2, s3) + ⋯$ \n\nOptimal policy is\nindependent of the starting state\n\n## Module 8 Definitions\n* **Utility function** - single number reflection of the agent's preference/desirablility of a state\n* **Expected utility** - average utility over the outcomes weighted by probability of each outcome\n* **Principle of maximum expected utility(meu)** - a rational agent should choose action that maximizes the expected utility\n* **Preference elicitation** - present choice to humans and use oberserved preference to define human's utility func\n* **Insurance premium** - different bw EMV of a lottery vs its certianity equivalent\n* **Optimizer's curse** - tendency for the estimated EU of best choice to be too high\n* **Markovian** - probability of reaching s' from s depends only on s, not the history\n* **Environtment history** - sequence of states and actions. Utility function depends on this\n* **Finite horizon** - there is a fixed time N which after that nothing matters/game over\n* **Nonstationary** - policy that depends on time\n* **Contraction** - function appliedd to 2 inputs to produce outputs closer together\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\none-armed bandit = slot machine. n-armed bandit has n levers, behind each lever\nis a fixed but unknown probability distribution of winnings. The gambler must choose which lever to play on each successive coin.\nTradeoff bw exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information \n\nBandit problem: Each arm $M_i$ is a Markov reward process or MRP, that is, an MDP with only one\npossible action . It has states S, transition model $P_i(s'|s,a_i)$, and reward R.\nThe arm defines a distribution over sequences of rewards where each $R_{i,t}$ is a random variable.\nThe overall bandit problem is an MDP: the state space is given by the Cartesian product.\nThe transition model updates the state of\nwhichever arm is selected, according to its specific transition model, leaving the\nother arms unchanged\n\nOptimal policy: pull the arm that has the highest Gittins index, then update the Gittins\nindices\n\n## AIMA Chapter 22.1 Learning from Rewards\n\n- Model-based reinforcement learning: use a transition model of the environment to interpret reward signals and decide \nhow to act. In partially observable environments, the transition\nmodel is also useful for state estimation. Model-based reinforcement\nlearning systems often learn U(s) = sum of rewards from state s onward\n- Model-free RL: agent neither knows or learns a transition model for the envi BUT learns a more \ndirect representation of how to behave\n-- action-utility learning[Q-learning]\n-- policy search/reflex agent\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nPassive learning agent:\nfixed policy, the agent tries to learn $U^\\pi(s)=$the expected total discounted reward if policy $\\pi$\nis executed beginning in state s. Similar to policy evaluation task\n$U^\\pi(s) = E[∑^\\infty_{t=0}γ^tR(St,π(St),St+1)]$ \n- direct utility estimation:  reduced reinforcement learning to a standard supervised learning\nproblem in which each example is a (state, reward-to-go) pair BUT it ignores\n The utility of a state is determined by the reward and the expected utility of\nthe successor states (bellman), leading to too large hypothesis space & slow convergence\n- adaptive dymanic programming(ADP): takes advantage of the constraints\namong the utilities of states by learning the transition model that connects them and solving\nthe corresponding Markov decision process using dynamic programming. Plugging in learned P and R\n- temporal-difference learning: use the observed\ntransitions to adjust the utilities of the observed states so that they agree with the constraint\nequations. Doesn't learn quite as fast as the ADP agent and shows much\nhigher variability, but it is much simpler and requires much less computation per\nobservation. TD equation $U\nπ\n(s) ← U\nπ\n(s) + α[R(s,π(s),s\n′\n) + γUπ\n(s\n′\n) − U\nπ\n(s)], \\alpha$ is the learning rate. Each adjustment made by ADP could be seen, from the TD point of view, as a result of a\npseudoexperience generated by simulating the current transition model\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\ndecide what actions to take. Active dymanic programming(ADP) agent\n- need to learn a complete transition model P for all actions. \n- agent has a choice of actions: U defined by the optimal policy/obey bellman eq.\n- at each step? optimal policy?\nThe greedy agent has overlooked the fact that actions do more than provide rewards; they\nalso provide information in the form of percepts in the resulting states.\nThe use of $U+$means that the benefits of exploration are propagated back from the edges of\nunexplored regions, so that actions that lead toward unexplored regions are weighted more\nhighly, rather than just actions that are themselves unfamiliar \n\nSafe exploration\n- bayesian reinforcement learning: assume a prior $P(h)$. Posterior $P(h|e)$, we have $π\n∗ = argmax_π ∑_hP(h|e)U_π^h$. Exploration POMDP\n- robust control theory:  allows for a set of possible\nmodels $H$ without assigning probabilities to them, and defines an optimal robust policy as\none that gives the best outcome in the worst case over $H$. Like agent vs adversary. Lead to \nconservative behavior\n\nTD Q-learning/SARSA: $Q(s,a) ← Q(s,a) + α[R(s,a,s′) + γ max_{a′}Q(s′,a′) − Q(s,a)]$avoids the need for a model by learning an action-utility function Q\n instead of U. But cant look into the future, may have difficulty when rewards are sparse\nand long action sequences must be constructed to reach them. Qlearning is off-policy but SARSA is on-policy\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nfunction approximation = the process of constructing a compact approximation of the true utility\nfunction or Q-function = saves space\n- approximating direct utility estimation: widrow-hoff rule, delta rule\n- approximating TD learning \n\ncredit assigment problem: figure out what it did wrong.\n\nReward shaping: supply the agent with \nadditional rewards[pseudorewards] for making progress. We can create new reward function \n$R\n′\n(s,a,s\n′\n) = R(s,a,s\n′\n) + γΦ(s\n′\n) − Φ(s)$ \n\nand hierarchical RL are helpful for learning complex behaviors esp. with sparse rewards\n\n\n## Module 9 Lecture Notes\nGoal = maximize expected sum of rewards BUT in RL the agent is \nnot given the MDP to solve. Instead, it's in the MDP. May not know the transition model or the reward function \n\nregret = u(possible action) - u(action taken)\n\n\n\n## Module 9 Definitions\n* **Gittins index** - (of M) describes the maximum obtainable utility per unit of discounted time\n* **Passive reinforcement learning** - agent has to figure out what to do\n* **Glie** - greedy in the limit of infinite exploration\n* **Sarsa** - similar to Q-learning but update with the Q-value of action a' that is actually taken (not max a')\n* **As** - as\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nDecision theory = probability theory + utility theory\n\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$P(a ∧ b) = P(a | b)P(b)$ Bayes' rule: $P(a | b) = \\frac{P(b|a)P(b)}{P(a)}$\n\n## AIMA Chapter 12.6 Naive Bayes Models\n$P(Cause, Effect_1,… , Effect_n) = P(Cause)∏_i P(Effect_i| Cause)$ \n\nThen the standard method for inference from the joint\ndistribution $P(Cause | e) = α∑_y P(Cause, e, y)= α P(Cause)∏_j P (ej∣Cause)$.  For each possible cause, multiply the prior probability of the cause by the product\nof the conditional probabilities of the observed effects given the cause; then normalize the\nresult. The run time of this calculation is linear in the number of observed effects and does\nnot depend on the number of unobserved effects\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n “Out of the times we saw the history h, how many times was it followed by\nthe word w. $P(w1:n) = P(w1)P(w2|w1)P(w3|w1:2)...P(wn|w1:n−1)$ \n\nn-gram model intuition: approximate the history by just the last few words. Bigram assumes $P(w_n|w_{1:n−1}) ≈ P(w_n|w_{n−1})$.\nGeneralize into n-gram (looks n−1 words into the past)\n\n## SLP Chapter 3.2 Evaluating Language Models\n Perplexity:weighted average branching factor $PP(W) = P(w1w2 ...wN)^{-1/N}$\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\nLaplace smoothing(add-one), add-k\n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nstationary process = the conditional probability table does not change over time \n\nP(Toothache | Detect , Cavity) = P(Toothache | Cavity) \n\nP(Toothache, Detect | Cavity) = P(Toothache | Cavity) P(Detect | Cavity)\n\nConditionally independent: $P(x,y|z)=p(x|z)P(y|z)$\n\n\n## Module 10 Definitions\n* **Markov assumption** - probability of a word depends only on the previous word\n* **Perplexity** - asdf\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Inference by Enumeration (slow:  join up the whole joint distribution before you sum out the hidden variables)\n vs. Variable Elimination\n\n## Module 11 Lecture Notes\n Conditional independence is our most basic and robust form\nof knowledge about uncertain environments. Bayes’ nets: a technique for describing complex joint\ndistributions (models) using simple, local\ndistributions (conditional probabilities). Bayes’ nets implicitly encode joint distributions \n\nArrow: Topology really encodes conditional independence. BNs advantage: huge space savings $2^N \\implies O(N*2^{k+1})$,\neasier to elicit local CPTs, faster to answer queries. \n\nD-separation\n\n\n## Module 11 Definitions\n* **Cpt** - conditional probability table\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 \n Your summary here \n\n## AIMA Chapter 19.2 \n Your summary here \n\n## AIMA Chapter 19.3 \n Your summary here \n\n## AIMA Chapter 19.4 \n Your summary here \n\n## AIMA Chapter 19.5 \n Your summary here \n\n## AIMA Chapter 19.6 \n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n $P(X \n1\n​\n ,X \n2\n​\n ,X \n3\n​\n ,Y)=P(Y)P(X \n1\n​\n ∣Y)P(X \n2\n​\n ∣Y)P(X \n3\n​\n ∣Y)$\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n The naïve Bayes assumption takes all features to be independent given\nthe class label. What do we need in order to use Naïve Bayes?\n- inference method: use standard inference to compute $ P(Y|F_1…F_n)$\n- estimates of local conditional probability tables:\n-- $P(Y)$, the prior over labels\n-- $P(F_i|Y)$. These probs are called parameters $\\theta$ \n\nParameter estimation: elicitation[ask human] or empirical[use training data]\n\nRelative frequencies are the maximum likelihood estimates $\\theta_{ML}=argmax_{\\theta}P(X|\\theta)$. \nLaplace smoothing, Linear interpolation \n\nPERCEPTRONS\n\nStart with weights = 0. For each training instance\n- classify with current weights. $y=+1, w\\cdot f(x)\\geq 0$ -1 otherwise OR \nmulticlass $y=argmax_y w_y\\cdot f(x)$\n- if correct, no change\n- if wrong, adjust the weight vector $w=w+y*\\cdot f$ (subtract if $y*=-1$) OR \nmulticlass lower/raise score of wrong/right answer. $w_y=w_y-f(x), w_y*=w_y*+f(x)$\n\nProperties\n- $bias = -threshold$\n- Convergence: if the training is separable, perceptron\nwill eventually converge (binary case)\n- Mistake Bound: the maximum number of mistakes related to the margin or degree of\nseparability. mistakes $< k/\\delta^2$\n- solution: maximum step size cap the maximum possible value of t with some\nconstant C. Converges faster, better on noisy data\n\nSVM: find the separator with max margin\n\n- only support vectors matter\n \n\n## Module 12 Definitions\n* **Induction** - going from observations to a general rule, can be incorrect\n* **Concept** - definition\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\n \n- given an instance x computes the probability $P(y = 1|x)$\n- sigmoid function $y=1/(1+e^{-z})=1/(1+e^{-(wx+b)})$\n- loss function: ie. MSE, cross entropy loss[negative log likelihood loss]\n- Gradient descent is a method that finds a minimum of a function by figuring out in\nwhich direction (in the space of the parameters θ) the function’s slope is rising the most\nsteeply, and moving in the opposite direction\n- loss function of logistic regression is convex = one minimum\n- Stochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\n- Alternative: batch training computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute\n- compromise: mini-batch training ie. batch of 512/1024 \n\nNEURAL NETWORK\n\n- sigmoid neurons: solve a problem that a small change in the w or b of single perceptron in the network\ncan causes output flip from 0 to 1\n- smoothness! small changes in the weights wj and in the bias b will\nproduce a small change the output from the neuron\n- activation function: nonlinear ie. sigmoid, tanh (steeper), ReLU\n- The simplest kind of NN is the Feed-Forward Neural Network\n- output of hidden layer $h = σ(Wx+b)$, $z=Uh$, $y=softmax(z)$ softmax normalizes the output and turns it into a\nprobability distribution\n- error backpropagation algorithm: procedure called backward differentiation, which depends on the notion of\ncomputation graphs \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 word meaning: we want to encode\n1. Synonyms – words that have similar meanings\n2. Antonyms – words that have opposite meanings\n3. Connotations – words that are positive or negative\n4. Semantic Roles – buy, sell, and pay are different parts of the same underlying\npurchasing event\n5. Support for entailment\n- distributional word similarity: Intuition for algorithm:\nTwo words are similar if they have similar word contexts\n- vector space model\n- term-document matrix: each column vector represents a document, each row represents a term. Value\nin a cell shows how often that term occurred in that document. Measure document similarity = comparing columns.\n- term-term [term-context] matrix: length of vector is now $|V|$.\nContext window\n- co-occurence matrix is long and sparse. Alternative: learn vectors that are short and dense\n\n\n## SLP Chapter 6.2 Vector Semantics\nInstead of raw counts, it’s common to transform vectors using TF-IDF or PPMI \n- TF[how often a word occured in a doc] * IDF[1/number of docs that it occured in] \n\nlanguage modeling\n- goal: learn a function that returns joint probability\n- difficulty: too many parameters (curse of dimensionality), In n-gram-based models we fail to generalize to related words/word\nsequences that we have observed\n- chain rule: assume that next word only depends on the prev n-1 words $P(w_1w_2...w_t)=\\Pi P(w_t|w_1w_2...w_{t-1})$\n- unseen sequences: \n-- back off\n-- smoothing/interpolation\n\n\n## SLP Chapter 6.3 Words and Vectors\nNeural Language models have several advantages over n-gram LMs:\n1. They don’t need smoothing\n2. They can handle much longer histories.\n3. They can generalize over contexts of similar words.\n4. Neural LMs tend to have much higher predictive accuracy than n-gram LMs.\n5. byproduct = word embeddings\nDisadvantage: slower to train than traditional n-gram LMs\n\nNeural LMs\n1. Associate each word in the vocabulary with a vector-representation, thereby\ncreating a notion of similarity between words.\n2. Express the joint probability function of a word sequence in terms of the word\nvectors for the words in that sequence.\n3. Simultaneously learn the word vectors and the parameters of the function.\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\nWord2Vec:\n- Learn embeddings as part of the process\nof word prediction.\n- Train a classifier to predict neighboring\nwords\n- Inspired by NN LMs. learn dense embeddings for\nthe words in the training corpus.\n- fast and easy to train (than SVD)\n- Predict each neighboring word in a context window of 2C of surrounding words. Use \"negative sampling\" of \nrandom noise words for training. take the learned classifier weights as\nthe word embeddings\n\n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\nLogistic regression\n \n- given an instance x computes the probability $P(y = 1|x)$\n- sigmoid function $y=1/(1+e^{-z})=1/(1+e^{-(wx+b)})$\n- loss function: ie. MSE, cross entropy loss[negative log likelihood loss]\n- Gradient descent is a method that finds a minimum of a function by figuring out in\nwhich direction (in the space of the parameters θ) the function’s slope is rising the most\nsteeply, and moving in the opposite direction\n- loss function of logistic regression is convex = one minimum\n- Stochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\n- Alternative: batch training computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute\n- compromise: mini-batch training ie. batch of 512/1024 \n\nNEURAL NETWORK\n\n- sigmoid neurons: solve a problem that a small change in the w or b of single perceptron in the network\ncan causes output flip from 0 to 1\n- smoothness! small changes in the weights wj and in the bias b will\nproduce a small change the output from the neuron\n- activation function: nonlinear ie. sigmoid, tanh (steeper), ReLU\n- The simplest kind of NN is the Feed-Forward Neural Network\n- output of hidden layer $h = σ(Wx+b)$, $z=Uh$, $y=softmax(z)$ softmax normalizes the output and turns it into a\nprobability distribution\n- error backpropagation algorithm: procedure called backward differentiation, which depends on the notion of\ncomputation graphs \n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}