{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8c265db6-5735-48cf-f4ea-053e4055be17"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1226e6ed-14a7-44e4-b2cd-378db8b3fdba"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "MEU formalizes what an agent should do, but doesn't operationalize it. Estimating \n",
        "P(RESULT(a)=s') requires perception, knowledge representation and learning. Computing the result\n",
        "requires a causal model. \n",
        "\n",
        "If an agent acts to maximize a utility function that correctly reflects the performance measure, \n",
        "then it will achieve that highest possible score (averaged over environments)\n",
        "\"\"\" \n",
        "chapter16_2 =  \"\"\" \n",
        "Utility theory axioms\n",
        "\n",
        "Orderability: agent prefers one outcome, or finds them equally preferable (must decide)\n",
        "Transitivity\n",
        "Continuity: A>B>C => exists p s.t. [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 iff [p,A; 1-p, B]>[q,A; 1-q, B]) (agent prefers A then prefers loterry with higher probability for A)\n",
        "Decomposability: [p, A; 1-p, [q, B; 1-q, C]]=[p,A; (1-p)q,b; (1-p)(1-q),C] compound lotteries can be reduced to simpler ones, no fun in gambling\n",
        "\n",
        "Existence of UF: U(A)>U(B) iff A>B, U(A)=U(B) iff A=B\n",
        "Expected U of lottery: U([p_1, S_1;...;p_n, S_n])=sum_i(p_i*U(S_i))\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\"\n",
        "monotonic preference: more is better (money)\n",
        "money not a utility function \n",
        "risk aversion: U(L)<U(S_{EMV(L)}), better be handed x money than participate in lottery where EMV is x\n",
        "certainty equivalent: the money an agent accepts in lieu of lottery\n",
        "insurance premium: EMV(L)-certainty equiv\n",
        "unbiased: assuming that diff between estimated EU and actual EU is 0\n",
        "favouring highest utility: favouring overly optimistic estimates even when we're unbiased on average for each gives decision\n",
        "optimizer's curse: when sampling decisions, decisions with higher expected utility tend to also be more optimistic\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"\n",
        "utility function R(s,a,s') for action a to transition from s to s'\n",
        "\n",
        "MDP: \n",
        "\n",
        "S: states\n",
        "ACTIONS(s): set of actions in each state\n",
        "P(s'|s,a): transition model\n",
        "R(s,a,s'): reward fuction\n",
        "(gamma: discount)\n",
        "\n",
        "finite horizons mean nonstationary policy\n",
        "\n",
        "additive discounted rewards:\n",
        "U([s_0, a_0, ..., s_n, a_n]) = R(s_0, a_0, s_1) + ... + gamma^n(s_n, a_n, s_{n+1})\n",
        "\n",
        "gamma: discount factor [0,1], closer to 1 agent more willing to wait for long-term rewards, purely additive at gamma=1\n",
        "\n",
        "Reasons for discount:\n",
        "\n",
        "1) empirical \n",
        "2) economic \n",
        "3) future may never arrive (1-gamma chance of unexpected termination) \n",
        "4) if you prefer future A to B, you should prefer present A to present  B\n",
        "5) unitilities with undiscoutned rewards will tend to be unfinite if no guaratee of reaching terminal state\n",
        "\n",
        "expected utility of executing pi in s:\n",
        "U(pi)(s)=E[sum_(t=0)^inf(gamma^t*R(S_t, pi(S_t), S_{t+1}))]\n",
        "\n",
        "pi*=argmax_{pi}U(pi)(s)\n",
        "\n",
        "so, true utility of s is just U(pi*)(s)\n",
        "\n",
        "pi*(s) = argmax_{a in A(s)} sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))]\n",
        "\n",
        "(action with best value)\n",
        "\n",
        "bellman equation: \n",
        "\n",
        "U(s) = max_{a in A(s)} sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))]\n",
        "\n",
        "(best value)\n",
        "\n",
        "action-utility function Q: expected utility of taking a in given state (Q value)\n",
        "\n",
        "pi*(s) = argmax_a Q(s,a)\n",
        "\n",
        "Q(s,a) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))] = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*max_{a'}*Q(s', a'))]\n",
        "\n",
        "Shaping theorem:\n",
        "\n",
        "R'(s,a,s')=R(s,a,s')+gamma*PHI(s')-PHI(s) transformation leaves optimal policy unchanged\n",
        "\n",
        "Representations:\n",
        "\n",
        "3D tables |S|^2|A|. Because sparase (s can only transition to bounded s'), size can be reduced to O(|S|*|A|)\n",
        "\n",
        "dynamic decision networks: factored representations with exponential complexion advantage over atomic representations\n",
        " \"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "value iteration:\n",
        "\n",
        "def VI(MDP, e): (e is max error allowed in utility of state)\n",
        "  U, U'= vectors of utilities for states in S\n",
        "  delta: max relative change in utility of any state, initially 0\n",
        "  while delta <= e(1-gamma)/gamma:\n",
        "    U=U'\n",
        "    delta = 0\n",
        "    for s in S:\n",
        "      U'[s]=max_{a in A(s)} Q(s,a, MDP, U) (gamma as defined in MDP to find Q)\n",
        "      if abs(U'[s]-U[s])>delta:\n",
        "        delta = abs(U'[s]-U[s])\n",
        "  return U\n",
        "\n",
        "converges to actual U\n",
        "\n",
        "fast convergence for small gamma (slow otherwise), but this gives agent short horizon\n",
        "\n",
        "policy iteration:\n",
        "\n",
        "def PI(MDP):\n",
        "  U: utilities in S\n",
        "  pi: policy vector indexed by state (initially random)\n",
        "\n",
        "  while not unchanged:\n",
        "    U=POLICY_EVAL(pi, U, MDP)\n",
        "    unchanged = true\n",
        "    for s in S:\n",
        "      a* = argmax_{a in A(s)} Q(mdp, s, a, U)\n",
        "      if Q(mdp, s, a*, U)>Q(mdp, s, pi[s], U):\n",
        "        pi[s]=a*\n",
        "        unchanged = false\n",
        "  return pi\n",
        "\n",
        "\n",
        "POLICY_EVAL(pi, U, MDP): the utility U(s) of each state if pi was executed\n",
        "\n",
        "U(s)=sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))] (bellman eq without taking max over a, a=pi(s))\n",
        "\n",
        "O(n^3) for n states\n",
        "\n",
        "modified policy iteration: using estimates to reduce complexity\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "    \"utility function\" : \"U(s) single number to express state desirability\",\n",
        "    \"expected utility\": \"EU(a)=sum(P(RESULT(a)=s')U(s'))(for all successors s')\",\n",
        "    \"max expected utility principle (MEU)\": \"a=argmax(EU(a)) (over a)\",\n",
        "    \"ordinal utility function\": \"U'(S)=a*U(S)+b, retains order under transformations\",\n",
        "    \"transition model\": \"outcome of each action in each state\",\n",
        "    \"markovian\": \"probability of reaching s' from s doesn't depend on history\",\n",
        "\"dynamic programing\": \"simplifying by recursively breaking problem into smaller pieces\",\n",
        "\"policy\": \"pi(s), the recomended action given state s\",\n",
        "\"optimal policy\": \"yields highest expected utility\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"nonstationary policy\": \"depends on time (finite horizon)\",\n",
        "\"proper policy\": \"guaranteed to reach terminal state\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f809819e-9f7b-4189-d392-50bfd4d6a7a4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nMEU formalizes what an agent should do, but doesn't operationalize it. Estimating \nP(RESULT(a)=s') requires perception, knowledge representation and learning. Computing the result\nrequires a causal model. \n\nIf an agent acts to maximize a utility function that correctly reflects the performance measure, \nthen it will achieve that highest possible score (averaged over environments)\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nUtility theory axioms\n\nOrderability: agent prefers one outcome, or finds them equally preferable (must decide)\nTransitivity\nContinuity: A>B>C => exists p s.t. [p,A; 1-p, C]=B\nSubstitutability: A=B => [p,A; 1-p, C]=[p,B; 1-p, C]\nMonotonicity: A>B => (p>q iff [p,A; 1-p, B]>[q,A; 1-q, B]) (agent prefers A then prefers loterry with higher probability for A)\nDecomposability: [p, A; 1-p, [q, B; 1-q, C]]=[p,A; (1-p)q,b; (1-p)(1-q),C] compound lotteries can be reduced to simpler ones, no fun in gambling\n\nExistence of UF: U(A)>U(B) iff A>B, U(A)=U(B) iff A=B\nExpected U of lottery: U([p_1, S_1;...;p_n, S_n])=sum_i(p_i*U(S_i))\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nmonotonic preference: more is better (money)\nmoney not a utility function \nrisk aversion: U(L)<U(S_{EMV(L)}), better be handed x money than participate in lottery where EMV is x\ncertainty equivalent: the money an agent accepts in lieu of lottery\ninsurance premium: EMV(L)-certainty equiv\nunbiased: assuming that diff between estimated EU and actual EU is 0\nfavouring highest utility: favouring overly optimistic estimates even when we're unbiased on average for each gives decision\noptimizer's curse: when sampling decisions, decisions with higher expected utility tend to also be more optimistic\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n\nutility function R(s,a,s') for action a to transition from s to s'\n\nMDP: \n\nS: states\nACTIONS(s): set of actions in each state\nP(s'|s,a): transition model\nR(s,a,s'): reward fuction\n(gamma: discount)\n\nfinite horizons mean nonstationary policy\n\nadditive discounted rewards:\nU([s_0, a_0, ..., s_n, a_n]) = R(s_0, a_0, s_1) + ... + gamma^n(s_n, a_n, s_{n+1})\n\ngamma: discount factor [0,1], closer to 1 agent more willing to wait for long-term rewards, purely additive at gamma=1\n\nReasons for discount:\n\n1) empirical \n2) economic \n3) future may never arrive (1-gamma chance of unexpected termination) \n4) if you prefer future A to B, you should prefer present A to present  B\n5) unitilities with undiscoutned rewards will tend to be unfinite if no guaratee of reaching terminal state\n\nexpected utility of executing pi in s:\nU(pi)(s)=E[sum_(t=0)^inf(gamma^t*R(S_t, pi(S_t), S_{t+1}))]\n\npi*=argmax_{pi}U(pi)(s)\n\nso, true utility of s is just U(pi*)(s)\n\npi*(s) = argmax_{a in A(s)} sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))]\n\n(action with best value)\n\nbellman equation: \n\nU(s) = max_{a in A(s)} sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))]\n\n(best value)\n\naction-utility function Q: expected utility of taking a in given state (Q value)\n\npi*(s) = argmax_a Q(s,a)\n\nQ(s,a) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))] = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*max_{a'}*Q(s', a'))]\n\nShaping theorem:\n\nR'(s,a,s')=R(s,a,s')+gamma*PHI(s')-PHI(s) transformation leaves optimal policy unchanged\n\nRepresentations:\n\n3D tables |S|^2|A|. Because sparase (s can only transition to bounded s'), size can be reduced to O(|S|*|A|)\n\ndynamic decision networks: factored representations with exponential complexion advantage over atomic representations\n \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nvalue iteration:\n\ndef VI(MDP, e): (e is max error allowed in utility of state)\n  U, U'= vectors of utilities for states in S\n  delta: max relative change in utility of any state, initially 0\n  while delta <= e(1-gamma)/gamma:\n    U=U'\n    delta = 0\n    for s in S:\n      U'[s]=max_{a in A(s)} Q(s,a, MDP, U) (gamma as defined in MDP to find Q)\n      if abs(U'[s]-U[s])>delta:\n        delta = abs(U'[s]-U[s])\n  return U\n\nconverges to actual U\n\nfast convergence for small gamma (slow otherwise), but this gives agent short horizon\n\npolicy iteration:\n\ndef PI(MDP):\n  U: utilities in S\n  pi: policy vector indexed by state (initially random)\n\n  while not unchanged:\n    U=POLICY_EVAL(pi, U, MDP)\n    unchanged = true\n    for s in S:\n      a* = argmax_{a in A(s)} Q(mdp, s, a, U)\n      if Q(mdp, s, a*, U)>Q(mdp, s, pi[s], U):\n        pi[s]=a*\n        unchanged = false\n  return pi\n\n\nPOLICY_EVAL(pi, U, MDP): the utility U(s) of each state if pi was executed\n\nU(s)=sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))] (bellman eq without taking max over a, a=pi(s))\n\nO(n^3) for n states\n\nmodified policy iteration: using estimates to reduce complexity\n\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - U(s) single number to express state desirability\n* **Expected utility** - your definition here\n* **Max expected utility principle (meu)** - a=argmax(EU(a)) (over a)\n* **Ordinal utility function** - U'(S)=a*U(S)+b, retains order under transformations\n* **Transition model** - outcome of each action in each state\n* **Markovian** - probability of reaching s' from s doesn't depend on history\n* **Dynamic programing** - simplifying by recursively breaking problem into smaller pieces\n* **Policy** - pi(s), the recomended action given state s\n* **Optimal policy** - yields highest expected utility\n* **Nonstationary policy** - depends on time (finite horizon)\n* **Proper policy** - guaranteed to reach terminal state\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"\n",
        "Reinforcement learning: agent not given the MDP, needs to learn the transition model, reward function etc\n",
        "\n",
        "model based RL: uses the transition model to interpret reward signals, often learn U(s) in terms of sum of rewards from s onward\n",
        "\n",
        "e.g. chess model knows how to move, learns what moves are good\n",
        "\n",
        "model-free: doesn't know or learn the transition model, instead a direct representation of target behaviour\n",
        "\n",
        "Q-learning: learns Q(s,a). given s, agent chooses a with highest q-value\n",
        "Policy learning: learns policy pi(s). reflex agent. \n",
        "\n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\"\n",
        "Passive learning: like policy evaluation task, but agent doesn't know P(s, a, s') or R(s,a,s')\n",
        "\n",
        "direct utility estimation: estimating total reward from this state onward (reward to go)\n",
        "U(s) is determined by the reward and the expected utility of successor states:\n",
        "\n",
        "U_i(s) = sum_{s'}[P(s'|s,pi_i(s))*(R(s,pi_i(s),s')+gamma*U(s'))]\n",
        "\n",
        "passive adaptive dynamic programming: (eg passive agent) plug in learned reward function R and model P into above eq to calculate utilities of states\n",
        "or use modified policy iteration\n",
        "\n",
        "def PASSIVE_ADP(percept): \n",
        "  current state s', reward signal r = percept\n",
        "  globals\n",
        "  pi: fixed policy\n",
        "  mdp: P, R, A, gamma\n",
        "  U: table of state utilities, initially empty\n",
        "  N_{s'|s, a}: table of outcome count vectors indexed by state, action, initially 0\n",
        "  s,a: the previous state and action, initially null\n",
        "\n",
        "  if s' is new:\n",
        "    U[s']=0\n",
        "  if s is not None:\n",
        "    N_{s'|s, a}[s,a][s']+=1\n",
        "    R[s,a.s']=r\n",
        "    add a to A[s]\n",
        "    P(.|s,a)= NORMALISE(N_{s'|s, a}[s,a])\n",
        "    U=POLICY_EVAL(pi, U, MDP) (see noted for module 8)\n",
        "    s,a=s', pi[s']\n",
        "    return a\n",
        "\n",
        "\n",
        "\n",
        "passive temporal diff learning: \n",
        "\n",
        "learns utility estimates using temporal diffs, step size alpha(n) (learning rate param) used to esure convergence\n",
        "\n",
        "no need for transition model to perform updates, environment supplies connections between neighbouring states\n",
        "\n",
        "def PASSIVE_TDL(percept):\n",
        "  (globals as with PASSIVE_ADP, one diff:)\n",
        "  N_s: table of frequences of states (unlike in ADP)\n",
        "\n",
        "  if s' is new:\n",
        "    U[s']=0\n",
        "  if s is not None:\n",
        "    N_s[s]+=1\n",
        "    U[s]=U[s]+ cross(alpha*(N_s[s]), r+gamma*U[s']-U[s]) #TD Equation\n",
        "  s = s'\n",
        "  return pi[s']\n",
        "\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\" \n",
        "Bayesian reinforcement learning:\n",
        "\n",
        "given hypothesis h about true model, experience e,\n",
        "\n",
        "pi* = argmax_{pi}sum_{h}P(h|e)U^{pi}_h\n",
        "U^{pi}_h: expected utility, averaged over all states, of executing pi in model h\n",
        "\n",
        "exploration POMDP, can be solved without observing, but intractable\n",
        "\n",
        "def TDL_Q(percept):\n",
        "  N_s,a: table of frequences of states/action pairs\n",
        "\n",
        "  if s is not None:\n",
        "    N_s,a[s,a]+=1\n",
        "    Q[s,a]=Q[s,a]+ alpha*(N_s,a[s,a])(r+gamma* max_{a'}( Q[s', a']-Q[s,a])) \n",
        "  s,a=s', argmax_{a'} f(Q[s'a], N_s,a[s',a'])\n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "Widrow-hoff rule (delta rule):\n",
        "\n",
        "theta_i = theta_i+alpha(partial of error / partial of theta_i)\n",
        "where error = (square diff of predicted - actual value) /2\n",
        "\n",
        "for linearfunction approximations:\n",
        "\n",
        "w_i<-w_i+a[diff] (as in lecture, for each feature)\n",
        "\n",
        "catastrophic forgetting: learning too well, forgetting about unsafe areas\n",
        "experience replay: keep replaying past trajectories\n",
        " \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "POLICY EVALUATION (for fixed policy):\n",
        "\n",
        "direct evaluation: \n",
        "act according to pi, keep track of sum of discounted rewards\n",
        "average samples (not estimating probabilities, we're estimating the value of being in a state)\n",
        "\n",
        "plus: doesn't require knowledge of model P, rewards R, eventually computes values by sampling transitions\n",
        "negative: wastes info about state connections, each state learned separately, so long time to learn\n",
        "\n",
        "sample based policy evaluation:\n",
        "Compute U by computing averages:\n",
        "U(s) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))]\n",
        "\n",
        "Take samples of outcomes s' (by doing action) and average\n",
        "\n",
        "U(s) = 1/n * sum_i(sample_i)\n",
        "sample_i = R(s, pi(s), s'_i)+gamma*U(s'_i) # for given pi\n",
        "\n",
        "problem: no guarantee that we'll end up in s n times\n",
        "\n",
        "TDL:\n",
        "update U(s) every time we experience transition (s, a, s', reward)\n",
        "likely outcomes s' will contribute updates more often (will be weighted more heavily)\n",
        "policy still fixed \n",
        "\n",
        "U(s) <- U(s)+alpha(sample - U(s)) (diff between what we observed and what we expected, interpolation)\n",
        "sample = R(s,pi(s),s')+gamma*U(s')\n",
        "\n",
        "eponential moving average\n",
        "running interpolation update makes recent samples more important\n",
        "\n",
        "model free\n",
        "\n",
        "problem: can't turn values into a new policy\n",
        "pi(s)=argmax_a Q(s,a)\n",
        "Q(s,a) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))], so we need P and R\n",
        "\n",
        "learn Q values instead, not values\n",
        "\n",
        "ACTIVE LEARNING:\n",
        "\n",
        "Q learning:\n",
        "\n",
        "Q_0(s,a)=0, we know to be right\n",
        "\n",
        "given Q_k:\n",
        "\n",
        "Q_{k+1}(s,a) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*max_{a'}*Q_k(s', a'))]\n",
        "\n",
        "learn Q(s,a) on the fly\n",
        "\n",
        "sample = R(s,a,s')+gamma*max_{a'}(Q_k(s', a'))\n",
        "\n",
        "Q(s,a)<-Q(s,a)+alpha(sample-Q(s,a)) update\n",
        "\n",
        "alpha=1, then Q(s,a) cancels out, only the sample counts\n",
        "alpha=0, then samples aren't used at all\n",
        "\n",
        "learning rate can decrease over time\n",
        "\n",
        "EXPLORATION:\n",
        "\n",
        "Forcing exploration: \n",
        "\n",
        "random actions (lower randomness over time)\n",
        "\n",
        "explore unexplored areas (exploration function)\n",
        "f(u, n) = n+k/n (u=utility, n=times state visited, k=constant)\n",
        "\n",
        "modified q-update\n",
        "\n",
        "sample = R(s,a,s')+gamma*max_{a'}f(Q_k(s', a'), N(s', a')) (give bonus to exploring when N is small)\n",
        "\n",
        "regret: minimizing: optimally learning to be optimal. random exploration has higher regret\n",
        "\n",
        "APROXIMATE: \n",
        "\n",
        "linear value function: \n",
        "\n",
        "V(s) = w_1*f_1(s) + ... + w_n*f_n(s) (features * weights)\n",
        "Q(s,a) = w_1*f_1(s, a)+...\n",
        "\n",
        "Learning algorithm changes weights\n",
        "\n",
        "transition=(s,a,r,s')\n",
        "difference = [r+gamma(max(Q(s',a')))]-Q(s,a) what I expected vs what I got\n",
        "Q(s,a)<-Q(s,a)+a[difference] exact Qs\n",
        "w_i<-w_i+a[diff]*f_i(s,a) approximate Qs\n",
        "\n",
        "f_i(s,a): whether or not feature is active\n",
        "\n",
        "if something bad happens, blame features that were on, disprefer states with those features\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"sparse rewards\" : \"in the majority of states the agents is given no informative reward signal\",\n",
        "\"passive RL\" : \"fixed policy, learning utility of states\",\n",
        "\"active RL\" : \"policy not fixed, agent needs to explore environment to learn how to behave\",\n",
        "\"apprentiship learning\": \"demonstrations instead of reward signals\",\n",
        "\"pseudoexperience\": \"adjustments by the ADP, transitions the TD agent thinks might happen, given current model\",\n",
        "\"prioritised sweeping heuristic\": \"adjust states whose likely successors have undergone large change of utility estimates\",\n",
        "\"greedy agent\": \"takes actions it thinks are best in each step\",\n",
        "\"glie\": \"greedy in limit of infinite exploration, try each action in each state an unbounded number of times\",\n",
        "\"exploration function\": \"determines the greed vs exploration tradeoff\",\n",
        "\"absorbing state\": \"no further actions or rewards possible\",\n",
        "\"POMDP\": \"partially observable MDP\",\n",
        "\"credit assignment problem\": \"which of the multiple features at play were responsible for success (without playing trillions of games)\",\n",
        "\"reward shaping\": \"pseudorewards for making progress\",\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "1d17b214-c48c-4691-8eba-eda66f1aeb84"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n\nReinforcement learning: agent not given the MDP, needs to learn the transition model, reward function etc\n\nmodel based RL: uses the transition model to interpret reward signals, often learn U(s) in terms of sum of rewards from s onward\n\ne.g. chess model knows how to move, learns what moves are good\n\nmodel-free: doesn't know or learn the transition model, instead a direct representation of target behaviour\n\nQ-learning: learns Q(s,a). given s, agent chooses a with highest q-value\nPolicy learning: learns policy pi(s). reflex agent. \n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\nPassive learning: like policy evaluation task, but agent doesn't know P(s, a, s') or R(s,a,s')\n\ndirect utility estimation: estimating total reward from this state onward (reward to go)\nU(s) is determined by the reward and the expected utility of successor states:\n\nU_i(s) = sum_{s'}[P(s'|s,pi_i(s))*(R(s,pi_i(s),s')+gamma*U(s'))]\n\npassive adaptive dynamic programming: (eg passive agent) plug in learned reward function R and model P into above eq to calculate utilities of states\nor use modified policy iteration\n\ndef PASSIVE_ADP(percept): \n  current state s', reward signal r = percept\n  globals\n  pi: fixed policy\n  mdp: P, R, A, gamma\n  U: table of state utilities, initially empty\n  N_{s'|s, a}: table of outcome count vectors indexed by state, action, initially 0\n  s,a: the previous state and action, initially null\n\n  if s' is new:\n    U[s']=0\n  if s is not None:\n    N_{s'|s, a}[s,a][s']+=1\n    R[s,a.s']=r\n    add a to A[s]\n    P(.|s,a)= NORMALISE(N_{s'|s, a}[s,a])\n    U=POLICY_EVAL(pi, U, MDP) (see noted for module 8)\n    s,a=s', pi[s']\n    return a\n\n\n\npassive temporal diff learning: \n\nlearns utility estimates using temporal diffs, step size alpha(n) (learning rate param) used to esure convergence\n\nno need for transition model to perform updates, environment supplies connections between neighbouring states\n\ndef PASSIVE_TDL(percept):\n  (globals as with PASSIVE_ADP, one diff:)\n  N_s: table of frequences of states (unlike in ADP)\n\n  if s' is new:\n    U[s']=0\n  if s is not None:\n    N_s[s]+=1\n    U[s]=U[s]+ cross(alpha*(N_s[s]), r+gamma*U[s']-U[s]) #TD Equation\n  s = s'\n  return pi[s']\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n \nBayesian reinforcement learning:\n\ngiven hypothesis h about true model, experience e,\n\npi* = argmax_{pi}sum_{h}P(h|e)U^{pi}_h\nU^{pi}_h: expected utility, averaged over all states, of executing pi in model h\n\nexploration POMDP, can be solved without observing, but intractable\n\ndef TDL_Q(percept):\n  N_s,a: table of frequences of states/action pairs\n\n  if s is not None:\n    N_s,a[s,a]+=1\n    Q[s,a]=Q[s,a]+ alpha*(N_s,a[s,a])(r+gamma* max_{a'}( Q[s', a']-Q[s,a])) \n  s,a=s', argmax_{a'} f(Q[s'a], N_s,a[s',a'])\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \nWidrow-hoff rule (delta rule):\n\ntheta_i = theta_i+alpha(partial of error / partial of theta_i)\nwhere error = (square diff of predicted - actual value) /2\n\nfor linearfunction approximations:\n\nw_i<-w_i+a[diff] (as in lecture, for each feature)\n\ncatastrophic forgetting: learning too well, forgetting about unsafe areas\nexperience replay: keep replaying past trajectories\n \n\n## Module 9 Lecture Notes\n \nPOLICY EVALUATION (for fixed policy):\n\ndirect evaluation: \nact according to pi, keep track of sum of discounted rewards\naverage samples (not estimating probabilities, we're estimating the value of being in a state)\n\nplus: doesn't require knowledge of model P, rewards R, eventually computes values by sampling transitions\nnegative: wastes info about state connections, each state learned separately, so long time to learn\n\nsample based policy evaluation:\nCompute U by computing averages:\nU(s) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))]\n\nTake samples of outcomes s' (by doing action) and average\n\nU(s) = 1/n * sum_i(sample_i)\nsample_i = R(s, pi(s), s'_i)+gamma*U(s'_i) # for given pi\n\nproblem: no guarantee that we'll end up in s n times\n\nTDL:\nupdate U(s) every time we experience transition (s, a, s', reward)\nlikely outcomes s' will contribute updates more often (will be weighted more heavily)\npolicy still fixed \n\nU(s) <- U(s)+alpha(sample - U(s)) (diff between what we observed and what we expected, interpolation)\nsample = R(s,pi(s),s')+gamma*U(s')\n\neponential moving average\nrunning interpolation update makes recent samples more important\n\nmodel free\n\nproblem: can't turn values into a new policy\npi(s)=argmax_a Q(s,a)\nQ(s,a) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*U(s'))], so we need P and R\n\nlearn Q values instead, not values\n\nACTIVE LEARNING:\n\nQ learning:\n\nQ_0(s,a)=0, we know to be right\n\ngiven Q_k:\n\nQ_{k+1}(s,a) = sum_{s'}[P(s'|s,a)*(R(s,a,s')+gamma*max_{a'}*Q_k(s', a'))]\n\nlearn Q(s,a) on the fly\n\nsample = R(s,a,s')+gamma*max_{a'}(Q_k(s', a'))\n\nQ(s,a)<-Q(s,a)+alpha(sample-Q(s,a)) update\n\nalpha=1, then Q(s,a) cancels out, only the sample counts\nalpha=0, then samples aren't used at all\n\nlearning rate can decrease over time\n\nEXPLORATION:\n\nForcing exploration: \n\nrandom actions (lower randomness over time)\n\nexplore unexplored areas (exploration function)\nf(u, n) = n+k/n (u=utility, n=times state visited, k=constant)\n\nmodified q-update\n\nsample = R(s,a,s')+gamma*max_{a'}f(Q_k(s', a'), N(s', a')) (give bonus to exploring when N is small)\n\nregret: minimizing: optimally learning to be optimal. random exploration has higher regret\n\nAPROXIMATE: \n\nlinear value function: \n\nV(s) = w_1*f_1(s) + ... + w_n*f_n(s) (features * weights)\nQ(s,a) = w_1*f_1(s, a)+...\n\nLearning algorithm changes weights\n\ntransition=(s,a,r,s')\ndifference = [r+gamma(max(Q(s',a')))]-Q(s,a) what I expected vs what I got\nQ(s,a)<-Q(s,a)+a[difference] exact Qs\nw_i<-w_i+a[diff]*f_i(s,a) approximate Qs\n\nf_i(s,a): whether or not feature is active\n\nif something bad happens, blame features that were on, disprefer states with those features\n\n\n \n\n## Module 9 Definitions\n* **Sparse rewards** - in the majority of states the agents is given no informative reward signal\n* **Passive rl** - fixed policy, learning utility of states\n* **Active rl** - policy not fixed, agent needs to explore environment to learn how to behave\n* **Apprentiship learning** - demonstrations instead of reward signals\n* **Pseudoexperience** - adjustments by the ADP, transitions the TD agent thinks might happen, given current model\n* **Prioritised sweeping heuristic** - adjust states whose likely successors have undergone large change of utility estimates\n* **Greedy agent** - takes actions it thinks are best in each step\n* **Glie** - greedy in limit of infinite exploration, try each action in each state an unbounded number of times\n* **Exploration function** - determines the greed vs exploration tradeoff\n* **Absorbing state** - no further actions or rewards possible\n* **Pomdp** - partially observable MDP\n* **Credit assignment problem** - which of the multiple features at play were responsible for success (without playing trillions of games)\n* **Reward shaping** - pseudorewards for making progress\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \n",
        "Logical inference fails for large domains because:\n",
        "\n",
        "laziness: too much work to list all if thens\n",
        "theoretical ignorance: what's the correct if then\n",
        "practical ignorance: how do we know the if holds\n",
        "\n",
        "decision theory: probability theory + utility theory\n",
        "\n",
        " \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "causal direction: P(effect|cause)\n",
        "diagnostic direction: P(cause|effect)\n",
        "\n",
        " \"\"\"\n",
        "chapter12_6 = \"\"\" \n",
        "naive bayes:\n",
        "\n",
        "P(cause, effect1, ..., effect_n) = P(cause) * product_i(P(effect_i|cause))\n",
        "\n",
        "P(cause|e)=norm * P(cause) * product_i(P(e_i|cause))\n",
        "\n",
        "e=observed effects\n",
        "\n",
        "all effects assumed to be independent\n",
        "works well in practice\n",
        "\n",
        "text classification: cause is the type, effects are presence/absence of key words\n",
        "(P(category) is estimated on the basis of previously enumerated categories)\n",
        " \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "size of distribution of n variables with domain size d: d^n\n",
        "marginal distribution: eliminate variables from joint distributions\n",
        "\n",
        "P(a|b)=P(a,b)/P(b)\n",
        "\n",
        "independence:\n",
        "\n",
        "\n",
        "P(A ∨ B) = P(A) + P(B) - P(A ∧ B)\n",
        "P(B | A) = P(B)\n",
        "P(A ∧ B) = P(A) P(B)\n",
        "P(A | B) = P(A)\n",
        "\n",
        "P(X1,X2,X3,X4)=P(X2,X1)P(X3|X2,X1)P(X4|X3,X2,X1) \n",
        "=P(X1|X2,X3,X4)P(X4)P(X3|X4)P(X2|X3,X4)\n",
        "=P(X1)P(X2|X1)P(X3|X2,X1)P(X4|X3,X2,X1)\n",
        "(chain rule)\n",
        "\n",
        "Larguage:\n",
        "\n",
        "n-gramm:\n",
        "\n",
        "w{i} and w{i - n} are independent \n",
        "P(w|w{i-1}, ... w{i-n+1})=1 for all w\n",
        "P(w1, w2, …, wN) estimated by applying chain rule\n",
        "Markov assumption: long distance relations irrelevant, probabilities are estimated from preceding n words\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "    \"MEU principle\": \"agent chooses action with highest utility averaged over all possible outcomes\",\n",
        "    \"sample space\": \"set of all possible worlds\",\n",
        "    \"probability model\":\"function from possible word omega to numerical value, s.t. sum over worlds=1\",\n",
        "    \"product rule\":\"P(A ∧ B) = P(A|B) P(B)\",\n",
        "    \"inclusion exclusion principle\":\"P(A ∨ B) = P(A) + P(B) - P(A ∧ B)\",\n",
        "    \"unconditional/prior prob\" : \"degree of belief without any further info\",\n",
        "    \"conditional/posterior prob\": \"P(a|b)=P(a,b)/P(b)\",\n",
        "    \"bernoulli distribution\": \"range is {0,1}\",\n",
        "    \"probability distribution\": \"assignment of probability for a random variable\",\n",
        "    \"categorical distribution\": \"prob dist of rv with finite discreet range\",\n",
        "    \"prob density function\": \"expression of distribution for continuous variables\",\n",
        "    \"independence x,y\": \"P(X,Y)=P(X)P(Y)\",\n",
        "    \"prob inference\":\"computing posterior probs given observed evidence\",\n",
        "    \"marginal prob\":\"P(Y)=sum_z(P(Y, Z=z)) (marginalization, summing out)\",\n",
        "    \"conditioning rule\":\"P(Y)=sum_z(P(Y|z)P(z))\",\n",
        "    \"bayes\": \"P(cause|effect)=P(effect|cause)P(cause)/P(effect)\",\n",
        "    \"conditional independence x,y\": \"P(X,Y|Z)=P(X|Z)P(Y|Z), P(X|Z,Y)=P(X|Z)\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b616a4b9-ef8b-4901-afaa-9125d4c906b0"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n \nLogical inference fails for large domains because:\n\nlaziness: too much work to list all if thens\ntheoretical ignorance: what's the correct if then\npractical ignorance: how do we know the if holds\n\ndecision theory: probability theory + utility theory\n\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 Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nnaive bayes:\n\nP(cause, effect1, ..., effect_n) = P(cause) * product_i(P(effect_i|cause))\n\nall effects assumed to be independent\nworks well in practice\n\ntext classification: cause is the type, effects are presence/absence of key words\n(P(category) is estimated on the basis of previously enumerated categories)\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\nsize of distribution of n variables with domain size d: d^n\nmarginal distribution: eliminate variables from joint distributions\n\nP(a|b)=P(a,b)/P(b)\n\nindependence:\n\n\nP(A ∨ B) = P(A) + P(B) - P(A ∧ B)\nP(B | A) = P(B)\nP(A ∧ B) = P(A) P(B)\nP(A | B) = P(A)\n\nP(X1,X2,X3,X4)=P(X2,X1)P(X3|X2,X1)P(X4|X3,X2,X1) \n=P(X1|X2,X3,X4)P(X4)P(X3|X4)P(X2|X3,X4)\n=P(X1)P(X2|X1)P(X3|X2,X1)P(X4|X3,X2,X1)\n(chain rule)\n\nLarguage:\n\nn-gramm:\n\nw{i} and w{i - n} are independent \nP(w|w{i-1}, ... w{i-n+1})=1 for all w\nP(w1, w2, …, wN) estimated by applying chain rule\nMarkov assumption: long distance relations irrelevant, probabilities are estimated from preceding n words\n \n\n## Module 10 Definitions\n* **Unconditional/prior prob** - degree of belief without any further info\n* **Conditional/posterior prob** - P(a|b)=P(a,b)/P(b)\n* **Bernoulli distribution** - range is {0,1}\n* **Probability distribution** - assignment of probability for a random variable\n* **Categorical distribution** - prob dist of rv with finite discreet range\n* **Prob density function** - expression of distribution for continuous variables\n* **Independence** - P(X,Y)=P(X)P(Y)\n* **Conditional independence** - P(X,Y|Z)=P(X|Z)P(Y|Z)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"\n",
        "Bayesian net: graph struct to represent any full joint prob distribution \n",
        "\n",
        "(must smaller than tabular representations whose size grows exponentially on the number of vars)\n",
        "\n",
        "each node corresponds to a random var (discreete or continuous)\n",
        "DAG, \n",
        "nodes have associated prob info P(X_i|Parents(X_i)), quantifying the effect of parents on node (conditional prob table)\n",
        "\n",
        "edge A->B, A is prior (or marginal) if no parent, containts P(A) info, B contains P(B|A)\n",
        " \"\"\"\n",
        "chapter13_2 = \"\"\" \n",
        "\n",
        "P(x_1...,x_n)=product(P(X_i|Parents(X_i)))\n",
        "\n",
        "P(X_i|X_{i-1},...,X_1)=P(X_i|Parents(X_i)) given that nodes are ordered topologically\n",
        "\n",
        "causal models involve fewer numbers, and the numbers are easier to find\n",
        "\n",
        "causal direction: P(effect|cause) effect->cause\n",
        "diagnostic direction: P(cause|effect) cause->effect\n",
        "\n",
        "each variable is conditionally independent of it non-descendants, given parents\n",
        "each variable is conditionally independent of all nodes, given parents, children, and children's parents (Markov blanket)\n",
        "\n",
        "D-separation (Z d-separates X,Y):\n",
        "\n",
        "consider X,Y,Z and ancestors (ancestral graph)\n",
        "link nodes that have a common child (moral graph)\n",
        "replace directed links by undirected links\n",
        "if Z blocks all X-Y paths, then Z d-separates X,Y\n",
        "\n",
        "(so network defines a set of conditional independence properties)\n",
        "\n",
        "canonical distribution: doesn't need a conditional distribution table to be fully specified, e.g. deterministic nodes\n",
        "(otherwise O(2^k) table for k parents)\n",
        "\n",
        "context specific independence: node conditionally independent of parents given certain values of others\n",
        "\n",
        "noisy or: uncertainty about ability of parent to cause child=true\n",
        "assuming: 1) all possible causes listed (otherwise we can add leak node for unknown cause)\n",
        "2) inhibition of each parent is independent of inhibition of other parents\n",
        "can be described using O(k) params instead of O(2^k) making learning easier\n",
        "\n",
        "\n",
        "continuous variables solutions:\n",
        "discretisation\n",
        "define continuous variable using probability density function\n",
        "nonparametric representation: collection of instances each containing specific parent-child values\n",
        "hybrid net: both continuous and discreet vars\n",
        "\n",
        "continuous var with cont parents: linear gausian distribution\n",
        "cont with discrete parents: conditional gaussian\n",
        "discrete with cont parents: probit or inverse logit\n",
        "discrete with discrete: as above, canonical, conditional dist table etc\n",
        "\n",
        "hidden vars used to make net reasonably sparse\n",
        "\n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\" \n",
        "inference by enumeration:\n",
        "\n",
        "a query \n",
        "\n",
        "like backtracking, linear space, O(2^n) time for n boolean variables\n",
        "\n",
        "variable elimination\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "\n",
        "unconditional independence: very rare, doesn't help make inferences about other vars\n",
        "conditional ind: most basic and robust form of knowledge about uncertain environments\n",
        "\n",
        "Bayes net:\n",
        "\n",
        "Causal chain X->Y->Z, X,Z independent\n",
        "\n",
        "P(Z|X,Y)=P(X,Y,Z)/P(X,Y)=P(Z|Y)\n",
        "\n",
        "P(X,Y,Z)=P(X)P(Y|X)P(Z|Y), P(X,Y)=P(X)P(Y|X), everything cancels out\n",
        "\n",
        "Common cause Y->X, Y->Z, X,Y not guaranteed to be independent, but conditionally independent\n",
        "\n",
        "P(Z|X,Y)=P(Z|X) or P(Z|Y)\n",
        "\n",
        "Common effect: X->Z, Y->Z, X,Y independent, not independent given Z (not conditionally)\n",
        "\n",
        "A,B conditionally independent if ANY triplet paths between them are innactive\n",
        "\n",
        "active: (u: unobserved, o:observed)\n",
        "u->u->u (causal)\n",
        "u->u,u->u (common cause unobserved)\n",
        "u->o, u->o (common effect observed)\n",
        "u->u, u->u, u------>o (common effect+causal chain) \n",
        "\n",
        "inactive:\n",
        "u->o->u (causal)\n",
        "o->u,o->u (common cause unobserved)\n",
        "u->u, u->u (common effect unobserved)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"sparse systems\" : \"local structure complexity grows linearly, subcomponents interact with bounded other components\",  \n",
        "\"markov blanket of node\": \"parents, children, and children's parents\",\n",
        "\"d-separation\":\"Z d-separates X,Y iff X,Y are conditionally independent given Z\" \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 428
        },
        "cellView": "form",
        "outputId": "d8ffde6f-e797-4c76-e377-d425db3ac6f8"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n\n\nunconditional independence: very rare, doesn't help make inferences about other vars\nconditional ind: most basic and robust form of knowledge about uncertain environments\n\n\n\n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"\n",
        "no prior knowledge vs transfer learning\n",
        "\n",
        "induction: specific => general\n",
        "\n",
        "feedback types:\n",
        "supervised learning (minimising loss)\n",
        "unsupervised learning (learn patterns without feedback)\n",
        "reinforcement learning (maximising utility)\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\" \n",
        "consistent hypothesis: fits all training data\n",
        "variance: change in hypothesis due to data fluctuation (danger to overfit)\n",
        "bias: deviation from predicted value averaged over datasets\n",
        "\n",
        "\"\"\"\n",
        "chapter19_3 = \"\"\" \n",
        "def LEARN_DECISION_TREE(examples, attributes, parent_examples) returns tree:\n",
        "  if examples is empty return PLURALITY_VALUE(parent_examples)\n",
        "  else if all examples have the same classification return classification\n",
        "  else if attributes is empty return PLURALITY_VALUE(examples)\n",
        "  else:\n",
        "    A=argmax_{a in attributes}IMPORTANCE(a, examples)\n",
        "    tree=new decision tree with root test A\n",
        "    for v of A:\n",
        "      exs={e:e in examples and e.A=v}\n",
        "      subtree = LEARN_DECISION_TREE(exs, attrs-A, examples)\n",
        "      add subtree as branch to tree\n",
        "    return tree\n",
        "\n",
        "\n",
        "entropy: measure of uncertainty\n",
        "\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\" \n",
        "stationarity assumption: future like past\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "marginal/prior probability in bayes net: no parent\n",
        "\n",
        "for each feature F, P(F|Y) nodes, where Y is the class\n",
        "\n",
        "naive bayes: params linear to the number of features\n",
        "simplistic but works well\n",
        "\n",
        "to find the probability of the label:\n",
        "calculate prob of evidence: sum_j(P(y_j)*product_i(P(f_i|y_j))) (for prior P(y_j))\n",
        "\n",
        "finally P(Y=y_j)=P(Y=y_j, evidence)/P(evidence)\n",
        "\n",
        "we need estimates of local conditionals and prior of the labels themselves (parameters)\n",
        "they come from data\n",
        "\n",
        "avoid assigning unseen events 0 probabilities\n",
        "\n",
        "Estimating parameters:\n",
        "\n",
        "ellicitation: ask a human\n",
        "\n",
        "empirically: count(x)/total samples, problem: unseen events\n",
        "\n",
        "laplace estimate: (or other smoothing) count(x)+1/sum_x(total samples(x)+1), we saw everything one more time than we did, no 0s\n",
        "as a side effect, non-0 probs for classes never seen\n",
        "laplace with 0 is just counting, can also have any other value (saw everything 100 extra times etc)\n",
        "\n",
        "interpolation (linear): get P(X) from data, make sure that P(X|Y) isn't too different from empirical P(X)\n",
        "\n",
        "P(x|y)=alpha*P_hat(x|y)_(1-alpha)P_hat(x), for alpha=1 we just default to empirical likelihood estimator\n",
        "\n",
        "\n",
        "perceptron: convergence guarantee iff data linearly separable\n",
        "\n",
        "issues:\n",
        "thrashing weights: average weights vectors over time\n",
        "barely separating solution\n",
        "overtraining: early stopping (once accuracy on heldout set starts decreasing)\n",
        "\n",
        "Fix: MIRA (Margin Infused Relaxed Algo)\n",
        "Choose update size that fixes mistake\n",
        "\n",
        "Comparison:\n",
        "Bayes:\n",
        "Builds a model training data\n",
        "Gives prediction probs\n",
        "Strong indepence assumptions\n",
        "One pass through data (count)\n",
        "\n",
        "Perceptron/MIRA:\n",
        "Fewer assumptions\n",
        "Mistake-driven learning\n",
        "Multiple passes through data\n",
        "Often more accurate\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"classification task\" : \"outputs one of a finite set of values\",    \n",
        "\"regression\" : \"outputs a number\",  \n",
        "\"parameters\":\"estimates of local conditionals and prior of the labels themselves\",\n",
        "\"perceptron learning rule\":\"w_i=w_i+alpha(y-y')x_i\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "04686183-5dfb-4a22-9659-93ecbf9684ff"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n\nno prior knowledge vs transfer learning\n\ninduction: specific => general\n\nfeedback types:\nsupervised learning (minimising loss)\nunsupervised learning (learn patterns without feedback)\nreinforcement learning (maximising utility)\n\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nconsistent hypothesis: fits all training data\nvariance: change in hypothesis due to data fluctuation (danger to overfit)\nbias: deviation from predicted value averaged over datasets\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \ndef LEARN_DECISION_TREE(examples, attributes, parent_examples) returns tree:\n  if examples is empty return PLURALITY_VALUE(parent_examples)\n  else if all examples have the same classification return classification\n  else if attributes is empty return PLURALITY_VALUE(examples)\n  else:\n    A=argmax_{a in attributes}IMPORTANCE(a, examples)\n    tree=new decision tree with root test A\n    for v of A:\n      exs={e:e in examples and e.A=v}\n      subtree = LEARN_DECISION_TREE(exs, attrs-A, examples)\n      add subtree as branch to tree\n    return tree\n\n\nentropy: measure of uncertainty\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nstationarity assumption: future like past\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \nmarginal/prior probability in bayes net: no parent\n\nfor each feature F, P(F|Y) nodes, where Y is the class\n\nnaive bayes: params linear to the number of features\nsimplistic but works well\n\nto find the probability of the label:\ncalculate prob of evidence: sum_j(P(y_j)*product_i(P(f_i|y_j))) (for prior P(y_j))\n\nfinally P(Y=y_j)=P(Y=y_j, evidence)/P(evidence)\n\nwe need estimates of local conditionals and prior of the labels themselves (parameters)\nthey come from data\n\navoid assigning unseen events 0 probabilities\n\nEstimating parameters:\n\nellicitation: ask a human\n\nempirically: count(x)/total samples, problem: unseen events\n\nlaplace estimate: (or other smoothing) count(x)+1/sum_x(total samples(x)+1), we saw everything one more time than we did, no 0s\nas a side effect, non-0 probs for classes never seen\nlaplace with 0 is just counting, can also have any other value (saw everything 100 extra times etc)\n\ninterpolation (linear): get P(X) from data, make sure that P(X|Y) isn't too different from empirical P(X)\n\nP(x|y)=alpha*P_hat(x|y)_(1-alpha)P_hat(x), for alpha=1 we just default to empirical likelihood estimator\n\n\nperceptron: convergence guarantee iff data linearly separable\n\nissues:\nthrashing weights: average weights vectors over time\nbarely separating solution\novertraining: early stopping (once accuracy on heldout set starts decreasing)\n\nFix: MIRA (Margin Infused Relaxed Algo)\nChoose update size that fixes mistake\n\nComparison:\nBayes:\nBuilds a model training data\nGives prediction probs\nStrong indepence assumptions\nOne pass through data (count)\n\nPerceptron/MIRA:\nFewer assumptions\nMistake-driven learning\nMultiple passes through data\nOften more accurate\n \n\n## Module 12 Definitions\n* **Classification task** - outputs one of a finite set of values\n* **Regression** - outputs a number\n* **Parameters** - estimates of local conditionals and prior of the labels themselves\n* **Perceptron learning rule** - w_i=w_i+alpha(y-y')x_i\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 = \"\"\" \n",
        "\n",
        "theta' = argmax sigma log(P(y_i|x_i)-alpha*R(theta)\n",
        "R(theta): regularization term\n",
        "\n",
        "L2 regularization: divide by eucledian distance of vector from origin\n",
        "\n",
        "L1 reg: manhattan distance (sum of values of weights)\n",
        "\n",
        "used to avoid overfitting\n",
        " \"\"\"\n",
        "slp_chapter5_6 = \"\"\" \n",
        "softmax regression, multinomial logistic regression\n",
        "\n",
        "generalisation of sigmoid, softmax\n",
        "\n",
        "given vector z with k dimensions:\n",
        "\n",
        "softmax(z_i)=exp(z_i)/sum(exp(z_j)) for j=1 to k, itself a vector, take largest\n",
        "\n",
        "denominator used to normalize values to probabilities\n",
        "\n",
        "loss function: \n",
        "\n",
        "-[log(exp(w_k*x+b)/sum_j(exp(w_j*x+b)))], where k is correct class\n",
        "\n",
        " \"\"\"\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 = \"\"\" \n",
        "feedforward net: no cycles\n",
        " \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "\n",
        "classifier components:\n",
        "  feature representation\n",
        "  classification function\n",
        "  objective function for learning (involving minimising error on training examples)\n",
        "  algorithm for optimizing objective function\n",
        "\n",
        "logistic regression solves tasks by learning a set of weights and a bias term\n",
        "\n",
        "unlike perceptron, can bound values of outputs, by using sigmoid function\n",
        "\n",
        "P(y=1)=sigma(w * x + b) (dot product)\n",
        "\n",
        "objective function: cross-entropy loss\n",
        "stochastic gradient descent to minimize loss function\n",
        "\n",
        "Loss functions:\n",
        "\n",
        "y': prediction\n",
        "y: actual\n",
        "\n",
        "mean squared error: L(y', y)=(y'-y)/2 (ok for linear regression, but hard to optimize)\n",
        "\n",
        "cross entropy (negative log likelihood): \n",
        "\n",
        "maximise: p(y|x)=y'^y(1-y')^(1-y) (prob given inputs)\n",
        "\n",
        "log(p(y|x))=log(y'^y(1-y')^(1-y))=y'log(y)+(1-y')log(1-y)\n",
        "\n",
        "so,\n",
        "\n",
        "L(y', y)= -log(p(y|x)) = -[y'log(y)+(1-y')log(1-y)]\n",
        "y'= sigma(w*x+b) (substitute y' above)\n",
        "\n",
        "Lower cross entropy => better classifier\n",
        "\n",
        "Gradient descent:\n",
        "\n",
        "find partial derivative of loss with respect to each weight:\n",
        "\n",
        "delta(Loss(y',y))/delta(w_i)=[sigma(w*x+b)-y]x (partial derivative)\n",
        "\n",
        "(see perceptron learning rule)\n",
        "minimize average \n",
        "\n",
        "theta_{t+1}=theta_t-eta*der_{theta}L(f(x_i,theta), y_i)\n",
        "\n",
        "where eta is the learning rate (times that with gradient vector)\n",
        "\n",
        "\n",
        "NN layer: perceptron + activation function\n",
        "\n",
        "nonlinear activation functions are differentiable, and help learn non-linear decision boundaries\n",
        "\n",
        "back propagation: uses chain rule\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "cce5f73c-8f0b-4f06-a857-7c70c0e7b69b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n \n\ntheta' = argmax sigma log(P(y_i|x_i)-alpha*R(theta)\nR(theta): regularization term\n\nL2 regularization: divide by eucledian distance of vector from origin\n\nL1 reg: manhattan distance (sum of values of weights)\n\nused to avoid overfitting\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n \nsoftmax regression, multinomial logistic regression\n\ngeneralisation of sigmoid, softmax\n\ngiven vector z with k dimensions:\n\nsoftmax(z_i)=exp(z_i)/sum(exp(z_j)) for j=1 to k, itself a vector, take largest\n\ndenominator used to normalize values to probabilities\n\nloss function: \n\n-[log(exp(w_k*x+b)/sum_j(exp(w_j*x+b)))], where k is correct class\n\n \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 \nfeedforward net: no cycles\n \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n\nclassifier components:\n  feature representation\n  classification function\n  objective function for learning (involving minimising error on training examples)\n  algorithm for optimizing objective function\n\nlogistic regression solves tasks by learning a set of weights and a bias term\n\nunlike perceptron, can bound values of outputs, by using sigmoid function\n\nP(y=1)=sigma(w * x + b) (dot product)\n\nobjective function: cross-entropy loss\nstochastic gradient descent to minimize loss function\n\nLoss functions:\n\ny': prediction\ny: actual\n\nmean squared error: L(y', y)=(y'-y)/2 (ok for linear regression, but hard to optimize)\n\ncross entropy (negative log likelihood): \n\nmaximise: p(y|x)=y'^y(1-y')^(1-y) (prob given inputs)\n\nlog(p(y|x))=log(y'^y(1-y')^(1-y))=y'log(y)+(1-y')log(1-y)\n\nso,\n\nL(y', y)= -log(p(y|x)) = -[y'log(y)+(1-y')log(1-y)]\ny'= sigma(w*x+b) (substitute y' above)\n\nLower cross entropy => better classifier\n\nGradient descent:\n\nfind partial derivative of loss with respect to each weight:\n\ndelta(Loss(y',y))/delta(w_i)=[sigma(w*x+b)-y]x (partial derivative)\n\nminimize average \n\ntheta_{t+1}=theta_t-eta*der_{theta}L(f(x_i,theta), y_i)\n\nwhere eta is the learning rate (times that with gradient vector)\n\n\nNN layer: perceptron + activation function\n\nnonlinear activation functions are differentiable, and help learn non-linear decision boundaries\n\nback propagation: uses chain rule\n\n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "\n",
        "encoding word meaning:\n",
        "synonyms\n",
        "antonyms\n",
        "connotatioopns\n",
        "semantics roles\n",
        "entailment\n",
        "\n",
        "co-occurence matrix:\n",
        "can just count instances of words adjacent to target word\n",
        "\n",
        "TF-IDF:\n",
        "Term frequence * inverse of document frequency\n",
        "\n",
        "PPMI\n",
        "\n",
        "co-occurence matrices are sparse.\n",
        "\n",
        "vs dense vectors (by training a classifier), e.g. word2vec\n",
        "\n",
        "classifier to predict which words are true neighbours\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 930
        },
        "outputId": "02418688-7f1b-4a12-ac5e-d695d2403e0f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 236
        },
        "id": "T3cm1WV542_a",
        "outputId": "2a81ee0c-0821-4066-d52a-225ffe2de227"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "NameError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-5-30af9c4efda6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# This will generate the full set of notes that you can use for your exam.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m full_markdown = \"\\n\\n\".join([module8_markdown, \n\u001b[0m\u001b[1;32m      3\u001b[0m                              \u001b[0mmodule9_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m                              \u001b[0mmodule10_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m                              \u001b[0mmodule11_markdown\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mNameError\u001b[0m: name 'module8_markdown' is not defined"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "XQFp-C8CAVWx"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}