{
  "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": "8603568f-7df8-4ecc-fbe4-13c875bc8a58"
      },
      "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": "cc5d78a3-0ccd-4a1c-ae1d-460656bac747"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "padding = \"   \\n\"\n",
        "equation1 = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "equation2 = r\"\"\" $EU(a) = \\sum_{s'} P(\\textnormal{RESULT}(a)=s')U(s')$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\"\n",
        "MEU: maximum expected utility \\n\n",
        "\"\"\" + equation1 + padding + equation2\n",
        "\n",
        "prefer = r\"\"\"$A \\succ B$\"\"\" + \"  the agent prefers A over B \\n\"\n",
        "indifferent = r\"\"\"$A \\sim B$\"\"\" + \" the agent is indifferent between A and B \\n\"\n",
        "lottery = r\"\"\"Lottery: $L = [p_1,S_1; p_2,S_2;\\cdots; p_n,S_n]$\"\"\" + padding\n",
        "\n",
        "chapter16_2 =  prefer  + padding + indifferent + padding + lottery + \"\"\"orderability, transitivity, continuity, substitutability, monotonicity, and decomposability\"\"\"\n",
        "chapter16_3 =  \"\"\" In reality, people's behaviors are not always rational. \"\"\"\n",
        "\n",
        "BellmanEquation = r\"\"\"$U(s) = \\max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')] = \\max_a Q(s,a)$\"\"\"\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" An optimal policy is a policy that yields the highest expected utility \\n\n",
        "Additive undiscounted rewards will generally be infinite within infinite horizons. So we use discounted rewards. \\n\n",
        " \"\"\" + BellmanEquation\n",
        "chapter17_2 =  r\"\"\" Value Iteration: $V_{k+1}(s) = \\max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V_k(s')]$  Repeat until convergence Complexity of each iteration: $O(S^2A)$\n",
        "\n",
        "Policy $\\pi^*(s) = \\argmax_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V_k(s')]$\n",
        "Policy Evalutaion: $V^{\\pi_i}_{k+1}(s) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V^{\\pi_i}_k(s')]$\n",
        "\n",
        "\n",
        "One-step look-ahead: $\\pi_{i+1}(s) = \\argmax_a \\sum_{s'}T(s,a,s')[R(s,a, s')+\\gamma V^{\\pi}(s')]$\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Transitions are Markovian: the probability of arriving in s' only depends on s and not the history of earlier states. \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"express the desirability of a state\",\n",
        "\"expected utility\" : \"average utility value of the outcomes, weighted by the probability that the outcome occurs\",\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": 800
        },
        "outputId": "6af00a2d-5a95-409f-e71c-e28e474824a5"
      },
      "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: maximum expected utility \n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$    \n $EU(a) = \\sum_{s'} P(\\textnormal{RESULT}(a)=s')U(s')$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n$A \\succ B$  the agent prefers A over B \n   \n$A \\sim B$ the agent is indifferent between A and B \n   \nLottery: $L = [p_1,S_1; p_2,S_2;\\cdots; p_n,S_n]$   \norderability, transitivity, continuity, substitutability, monotonicity, and decomposability\n\n## AIMA Chapter 16.3 Utility Functions\n In reality, people's behaviors are not always rational. \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n An optimal policy is a policy that yields the highest expected utility \n\nAdditive undiscounted rewards will generally be infinite within infinite horizons. So we use discounted rewards. \n\n $U(s) = \\max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')] = \\max_a Q(s,a)$\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value Iteration: $V_{k+1}(s) = \\max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V_k(s')]$  Repeat until convergence Complexity of each iteration: $O(S^2A)$\n\nPolicy $\\pi^*(s) = \\argmax_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V_k(s')]$\nPolicy Evalutaion: $V^{\\pi_i}_{k+1}(s) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V^{\\pi_i}_k(s')]$\n\n\nOne-step look-ahead: $\\pi_{i+1}(s) = \\argmax_a \\sum_{s'}T(s,a,s')[R(s,a, s')+\\gamma V^{\\pi}(s')]$\n\n\n## Module 8 Lecture Notes\n Transitions are Markovian: the probability of arriving in s' only depends on s and not the history of earlier states. \n\n\n\n\n## Module 8 Definitions\n* **Utility function** - express the desirability of a state\n* **Expected utility** - average utility value of the outcomes, weighted by the probability that the outcome occurs\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 =  \"\"\" Multi-armed Bandit Problem \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Reinforcement learning differs from “just solving an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. \"\"\"\n",
        "chapter22_2 =  \"\"\" Passive learning agent: to learn the utility function where the agent does not know the transition model\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "Qlearning = r\"\"\"$Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma \\max_{a'}Q(s',a')] \\\\ Q(s,a) \\leftarrow Q(s,a) + \\alpha[R(s,a,s')+\\gamma \\max_{a'}Q(s',a')-Q(s,a)] = （1-\\alpha）Q(s,a)+\\alpha [sample]$\"\"\"\n",
        "\n",
        "\n",
        "chapter22_3 =  \"\"\" Active learning agent gets to decide what actions to take.\n",
        "\n",
        "Q(s,a) denotes the expected total discounted reward if the agent takes action a in s and acts optimally thereafter.\n",
        "\n",
        "\n",
        "Q-learning is an off-policy learning algorithm and SARSA is an on-policy algorithm.\n",
        "\n",
        "Q-leaning:\n",
        "\n",
        "\n",
        "\n",
        "\"\"\" + Qlearning\n",
        "\n",
        "\n",
        "Approximate_learning = r\"\"\"$V(s) = w_1f_1(s)+w_2f_2(s)+\\cdots+w_nf_n(s) \n",
        " Q(s,a) = w_1f_1(s,a)+w_2f_2(s,a)+\\cdots+w_nf_n(s,a)$ \n",
        "  difference = $[r + \\gamma \\max_{a'}Q(s',a')]-Q(s,a)$\n",
        "  $w_i \\leftarrow w_i + \\alpha[$difference$] f_i(s,a)$\n",
        "  \n",
        "  \"\"\"\n",
        "chapter22_4 =  \"\"\" \n",
        "\n",
        "\n",
        " \"\"\" + Approximate_learning\n",
        "chapter22_5 =  \"\"\" policy is a function that maps states to actions \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "Important ideas in reinforcement learning that came up: Exploration, Exploitation, Regret, Sampling, Difficulty\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"GLIE\" : \"greedy in the limit of infinite exploration\",\n",
        "\"SARSA\": r\"\"\"$Q(s,a) \\leftarrow Q(s,a) + \\alpha[R(s,a,s')+\\gamma Q(s',a')-Q(s,a)]$\"\"\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 709
        },
        "cellView": "form",
        "outputId": "2d8646b7-4414-4956-c314-b392f91dc56a"
      },
      "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 Multi-armed Bandit Problem \n\n## AIMA Chapter 22.1 Learning from Rewards\n Reinforcement learning differs from “just solving an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Passive learning agent: to learn the utility function where the agent does not know the transition model\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Active learning agent gets to decide what actions to take.\n\nQ(s,a) denotes the expected total discounted reward if the agent takes action a in s and acts optimally thereafter.\n\n\nQ-learning is an off-policy learning algorithm and SARSA is an on-policy algorithm.\n\nQ-leaning:\n\n\n\n$Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma \\max_{a'}Q(s',a')] \\\\ Q(s,a) \\leftarrow Q(s,a) + \\alpha[R(s,a,s')+\\gamma \\max_{a'}Q(s',a')-Q(s,a)] = （1-\\alpha）Q(s,a)+\\alpha [sample]$\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n\n\n $V(s) = w_1f_1(s)+w_2f_2(s)+\\cdots+w_nf_n(s) \n Q(s,a) = w_1f_1(s,a)+w_2f_2(s,a)+\\cdots+w_nf_n(s,a)$ \n  difference = $[r + \\gamma \\max_{a'}Q(s',a')]-Q(s,a)$\n  $w_i \\leftarrow w_i + \\alpha[$difference$] f_i(s,a)$\n  \n  \n\n## Module 9 Lecture Notes\n \nImportant ideas in reinforcement learning that came up: Exploration, Exploitation, Regret, Sampling, Difficulty\n \n\n## Module 9 Definitions\n* **Glie** - greedy in the limit of infinite exploration\n* **Sarsa** - $Q(s,a) \\leftarrow Q(s,a) + \\alpha[R(s,a,s')+\\gamma Q(s',a')-Q(s,a)]$\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Decision theory = Probability theory + Utility theory. \"\"\"\n",
        "chapter12_2 = r\"\"\" prior probabilities refer to degrees of belief in propositions in the absence of any other information.\n",
        "$P(a|b) = \\frac{P(a,b)}{P(b)}$\n",
        "$P(a\\lor b) = P(a) + P(b) - P(a\\land b)$\n",
        " \"\"\"\n",
        "chapter12_3 = r\"\"\" Marginalization: $P(Y) = \\sum_z P(Y,Z=z) $\"\"\"\n",
        "chapter12_4 = r\"\"\" Independence: $P(a,b) = P(a)P(b)$  \"\"\"\n",
        "chapter12_5 = r\"\"\" Bayes' Rule: $P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}$ \"\"\"\n",
        "chapter12_6 = r\"\"\" \n",
        "Naive Bayes (effects are conditional independent with each other): $P(cause, effect_1, \\cdots, effect_n) = P(cause)\\prod_i P(effect_i|cause)$\n",
        "\n",
        " \"\"\"\n",
        "chapter12_7 = \"\"\" A probabilistic agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable. \"\"\"\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 = r\"\"\" N-gram language model : $P(w_n|w_{1:n-1}) = P(w_n|w_{n-N+1:n-1}) $ \n",
        "\n",
        "Maximum likelihood estimation for bigram: $P(w_n|w_n-1) = \\frac{count(w_{n-1}, w_{n})}{count(w_{n-1})}$\n",
        "\"\"\"\n",
        "SLP_chapter3_2 = r\"\"\" Perplexity: $PP(W) = P(w_1,w_2,\\cdots, w_N)^{-\\frac{1}{N}} = \\sqrt[N]{\\prod_{i=1}^{N}\\frac{1}{P(w_i|w_1\\cdots w_{i-1})}}$ \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Sampling from a distribution means to choose random points according to their likelihood. Thus sampling from a language model (which represents a distribution over sentences) means to generate some sentences, choosing\n",
        "each sentence according to its likelihood as defined by the model. Thus we are more likely to generate sentences that the model thinks have a high probability and less likely to generate sentences that the model thinks have a low probability. \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" \n",
        "An open vocabulary system open vocabulary is one in which we model these potential unknown words in the test set by adding a pseudo-word called <UNK>.\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\" To keep a language model from assigning zero probability to these unseen events, we’ll have to shave off a bit of probability mass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting. \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Efficiency considerations are important when building language models that use such large sets of n-grams. Rather than store each word as a string, it is generally represented in memory as a 64-bit hash number, with the words themselves stored on disk. Probabilities are generally quantized using only 4-8 bits (instead of 8-byte floats), and n-grams are stored in reverse tries. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = r\"\"\" \n",
        "Chain Rule: $P(x_1, x_2, \\cdots, x_n) = \\prod_i P(x_i|x_1, \\cdots, x_{i-1})$\n",
        "e.g.: $P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$\n",
        "\n",
        "Probabilistic Language Modeling\n",
        "Goal: compute the probability of a sentence or sequence of words\n",
        "$P(W) = P(w_1,\\cdots, w_n)$\n",
        "\n",
        "Related task: probability of an upcoming word\n",
        "$P(w_5|w_1, w_2, w_3, w_4)$\n",
        "\n",
        "A model that computes either of these is called a language model.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Markov Assumption\" : \"Only depends on the previous k words, not the whole context\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "1d727f3c-eaeb-4013-99bb-47880b02ee4c"
      },
      "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 Decision theory = Probability theory + Utility theory. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n prior probabilities refer to degrees of belief in propositions in the absence of any other information.\n$P(a|b) = \\frac{P(a,b)}{P(b)}$\n$P(a\\lor b) = P(a) + P(b) - P(a\\land b)$\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Marginalization: $P(Y) = \\sum_z P(Y,Z=z) $\n\n## AIMA Chapter 12.4 Independence\n Independence: $P(a,b) = P(a)P(b)$  \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes' Rule: $P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}$ \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nNaive Bayes (effects are conditional independent with each other): $P(cause, effect_1, \\cdots, effect_n) = P(cause)\\prod_i P(effect_i|cause)$\n\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n A probabilistic agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable. \n\n## SLP Chapter 3.1 N-Grams\n N-gram language model : $P(w_n|w_{1:n-1}) = P(w_n|w_{n-N+1:n-1}) $ \n\nMaximum likelihood estimation for bigram: $P(w_n|w_n-1) = \\frac{count(w_{n-1}, w_{n})}{count(w_{n-1})}$\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n Perplexity: $PP(W) = P(w_1,w_2,\\cdots, w_N)^{-\\frac{1}{N}} = \\sqrt[N]{\\prod_{i=1}^{N}\\frac{1}{P(w_i|w_1\\cdots w_{i-1})}}$ \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Sampling from a distribution means to choose random points according to their likelihood. Thus sampling from a language model (which represents a distribution over sentences) means to generate some sentences, choosing\neach sentence according to its likelihood as defined by the model. Thus we are more likely to generate sentences that the model thinks have a high probability and less likely to generate sentences that the model thinks have a low probability. \n\n## SLP Chapter 3.4 Generalization and Zeros\n \nAn open vocabulary system open vocabulary is one in which we model these potential unknown words in the test set by adding a pseudo-word called <UNK>.\n\n\n\n## SLP Chapter 3.5 Smoothing\n To keep a language model from assigning zero probability to these unseen events, we’ll have to shave off a bit of probability mass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting. \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Efficiency considerations are important when building language models that use such large sets of n-grams. Rather than store each word as a string, it is generally represented in memory as a 64-bit hash number, with the words themselves stored on disk. Probabilities are generally quantized using only 4-8 bits (instead of 8-byte floats), and n-grams are stored in reverse tries. \n\n## Module 10 Lecture Notes\n \nChain Rule: $P(x_1, x_2, \\cdots, x_n) = \\prod_i P(x_i|x_1, \\cdots, x_{i-1})$\ne.g.: $P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$\n\nProbabilistic Language Modeling\nGoal: compute the probability of a sentence or sequence of words\n$P(W) = P(w_1,\\cdots, w_n)$\n\nRelated task: probability of an upcoming word\n$P(w_5|w_1, w_2, w_3, w_4)$\n\nA model that computes either of these is called a language model.\n\n\n \n\n## Module 10 Definitions\n* **Markov assumption** - Only depends on the previous k words, not the whole context\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 = r\"\"\" \n",
        "Bayesian network is a directed graph (Directed Acyclic Graph) in which each node is annotated with quantitative probability information:\n",
        "\n",
        "Node: a random variable (associated local conditional probability information $P(x_i| parent(x_i)$)\n",
        "\n",
        "\n",
        "Directed Links: If there is an arrow from node X to node Y, X is said to be a parent of Y.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter13_2 = r\"\"\" \n",
        "$P(x_1,\\cdots, x_n) = \\prod_{i=1}^n P(x_i|parents(x_i))$\n",
        "\n",
        "The variable in Bayes Network is conditionally independent of its other predecessors, given its parents.\n",
        "A node is conditionally independant of its non-descendants given its parents. \n",
        "\n",
        "A node X is conditionally independant of all other nodes in the network given its Markov blanket.\n",
        "\n",
        "\"\"\"\n",
        "chapter13_3 = r\"\"\"\n",
        "Inference by Enumeration:\n",
        "Evidence variables: $E_1, \\cdots, E_k = e_1, \\cdots e_k$\n",
        "\n",
        "Query variable: $Q$\n",
        "\n",
        "Hidden variables: $H_1, \\cdots, H_r$\n",
        "\n",
        "We want $P(Q|e_1, \\cdots, e_k)$\n",
        "\n",
        "\n",
        "$P(Q,e_1,\\cdots,e_k) = \\sum_{h_1,\\cdots, h_r} P(Q, H_1, \\cdots,H_r, e_1, \\cdots, e_k)$ (use chain rule)\n",
        "\n",
        "$Z = \\sum_q P(Q,e_1,\\cdots, e_k) $\n",
        "\n",
        "$P(Q|e_1, \\cdots, e_k) = \\frac{1}{Z}P(Q,e_1,\\cdots,e_k)$\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = r\"\"\" \n",
        "joint distribution over N Boolean variables: $2^N$\n",
        "\n",
        "N-node net in which nodes have up tp k parents: $N*2^{k+1}$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"CPT\" : \"conditional probability table\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 734
        },
        "cellView": "form",
        "outputId": "28d7f97c-358b-4960-e3fa-3bb1544ac928"
      },
      "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 \nBayesian network is a directed graph (Directed Acyclic Graph) in which each node is annotated with quantitative probability information:\n\nNode: a random variable (associated local conditional probability information $P(x_i| parent(x_i)$)\n\n\nDirected Links: If there is an arrow from node X to node Y, X is said to be a parent of Y.\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n$P(x_1,\\cdots, x_n) = \\prod_{i=1}^n P(x_i|parents(x_i))$\n\nThe variable in Bayes Network is conditionally independent of its other predecessors, given its parents.\nA node is conditionally independant of its non-descendants given its parents. \n\nA node X is conditionally independant of all other nodes in the network given its Markov blanket.\n\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\nInference by Enumeration:\nEvidence variables: $E_1, \\cdots, E_k = e_1, \\cdots e_k$\n\nQuery variable: $Q$\n\nHidden variables: $H_1, \\cdots, H_r$\n\nWe want $P(Q|e_1, \\cdots, e_k)$\n\n\n$P(Q,e_1,\\cdots,e_k) = \\sum_{h_1,\\cdots, h_r} P(Q, H_1, \\cdots,H_r, e_1, \\cdots, e_k)$ (Use chain rule)\n\n$Z = \\sum_q P(Q,e_1,\\cdots, e_k) $\n\n$P(Q|e_1, \\cdots, e_k) = \\frac{1}{Z}P(Q,e_1,\\cdots,e_k)$\n\n \n\n## Module 11 Lecture Notes\n \njoint distribution over N Boolean variables: $2^N$\n\nN-node net in which nodes have up tp k parents: $N*2^{k+1}$\n\n\n## Module 11 Definitions\n* **Cpt** - conditional probability table\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 = \"\"\" Supervised Learning, Unsupervised Learning, Reinforcement Learning \"\"\"\n",
        "chapter19_2 = \"\"\" There is a bias–variance tradeoff: a choice between more complex, low-bias\n",
        "hypotheses that fit the training data well and simpler, low-variance hypotheses that may\n",
        "generalize better. \n",
        "\n",
        "Ockham’s razor\n",
        "\"\"\"\n",
        "chapter19_3 = r\"\"\" Entropy: $H(V) = \\sum_k P(v_k)log(\\frac{1}{P(v_k)})$\n",
        "\n",
        " \"\"\"\n",
        "chapter19_4 = r\"\"\" Model selection chooses a good hypothesis space, and optimization (also called training) finds the best hypothesis within that space.\n",
        "\n",
        "This process of explicitly penalizing complex hypotheses is called regularization. Regularization term has a hyperparameter $\\lambda$.\n",
        "\n",
        "\"\"\"\n",
        "chapter19_5 = \"\"\" Any hypothesis that is consistent with a sufficiently large set of training examples is\n",
        "unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC). \"\"\"\n",
        "chapter19_6 = \"\"\" L1 regularization tends to produce a sparse model. \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = r\"\"\" Naive Bayes(strong assumptions about feature independence):\n",
        "$P(Y,F_1,\\cdots, F_n) = P(Y) \\prod_i P(F_i|Y)$\n",
        " \"\"\"\n",
        "slp_chapter4_2 = \"\"\" The unknown words or very frequently occurred words will be ignored. \"\"\"\n",
        "slp_chapter4_3 = \"\"\" maximum likelihood training \"\"\"\n",
        "slp_chapter4_4 = \"\"\" \n",
        "Trick 1: whether a word occurs or not seems to matter more than its frequency\n",
        "\n",
        "Trick 2: negation (NOT_)\n",
        "\n",
        " \"\"\"\n",
        "slp_chapter4_5 = \"\"\" A common solution here, rather than using all the words as individual features,\n",
        "is to predefine likely sets of words or phrases as features, combined with features\n",
        "that are not purely linguistic. \"\"\"\n",
        "slp_chapter4_6 = r\"\"\" $P(s|c) = \\prod_{i} P(w_i | c) $\"\"\"\n",
        "slp_chapter4_7 = r\"\"\" precision: $\\frac{TP}{TP+FP}$ recall = $\\frac{TP}{TP+FN}$ accuracy=$\\frac{TP+TN}{TP+FP+TN+FN}$ \n",
        "\n",
        "Naive Bayes algorithm is  a multi-class classification algorithm.\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\" K-fold cross-validation. \"\"\"\n",
        "slp_chapter4_9 = \"\"\"There are two common non-parametric tests used in NLP: approximate ranapproximate\n",
        "domization and the bootstrap test.\"\"\"\n",
        "slp_chapter4_10 = \"\"\" representational harms \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" SVM : Maximizing the margin, only support vectors matter \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"LOOCV\" : \"leave-one-out cross-validation\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7db83bf7-c9f1-405f-ae8c-b62c83816796"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 The Theory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 Linear Regression and Classification\", 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 19.1 Forms of Learning\n Supervised Learning, Unsupervised Learning, Reinforcement Learning \n\n## AIMA Chapter 19.2 Supervised Learning\n There is a bias–variance tradeoff: a choice between more complex, low-bias\nhypotheses that fit the training data well and simpler, low-variance hypotheses that may\ngeneralize better. \n\nOckham’s razor\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n Entropy: $H(V) = \\sum_k P(v_k)log(\\frac{1}{P(v_k)})$\n\n \n\n## AIMA Chapter 19.4 Model Selection and Optimization\n Model selection chooses a good hypothesis space, and optimization (also called training) finds the best hypothesis within that space.\n\nThis process of explicitly penalizing complex hypotheses is called regularization. Regularization term has a hyperparameter $\\lambda$.\n\n\n\n## AIMA Chapter 19.5 The Theory of Learning\n Any hypothesis that is consistent with a sufficiently large set of training examples is\nunlikely to be seriously wrong: that is, it must be probably approximately correct (PAC). \n\n## AIMA Chapter 19.6 Linear Regression and Classification\n L1 regularization tends to produce a sparse model. \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Naive Bayes(strong assumptions about feature independence):\n$P(Y,F_1,\\cdots, F_n) = P(Y) \\prod_i P(F_i|Y)$\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n The unknown words or very frequently occurred words will be ignored. \n\n## SLP Chapter 4.3 Worked Example\n maximum likelihood training \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \nTrick 1: whether a word occurs or not seems to matter more than its frequency\n\nTrick 2: negation (NOT_)\n\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n A common solution here, rather than using all the words as individual features,\nis to predefine likely sets of words or phrases as features, combined with features\nthat are not purely linguistic. \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n $P(s|c) = \\prod_{i} P(w_i | c) $\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n precision: $\\frac{TP}{TP+FP}$ recall = $\\frac{TP}{TP+FN}$ accuracy=$\\frac{TP+TN}{TP+FP+TN+FN}$ \n\nNaive Bayes algorithm is  a multi-class classification algorithm.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n K-fold cross-validation. \n\n## SLP Chapter 4.9 Statistical Significance Testing\nThere are two common non-parametric tests used in NLP: approximate ranapproximate\ndomization and the bootstrap test.\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n representational harms \n\n## Module 12 Lecture Notes\n SVM : Maximizing the margin, only support vectors matter \n\n## Module 12 Definitions\n* **Loocv** - leave-one-out cross-validation\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 = r\"\"\" \n",
        "sigmoid: $\\sigma(z) = \\frac{1}{1+e^{-z}}$\n",
        "\n",
        "$1-\\sigma(x) = \\sigma(-x)$\n",
        "\n",
        "$\\sigma'(x) = \\sigma(x)(1-\\sigma(x))$\n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" cross-entropy loss \"\"\"\n",
        "slp_chapter5_3 = r\"\"\" $L = ylog \\hat{y} + (1-y)log (1-\\hat{y})$ \"\"\"\n",
        "slp_chapter5_4 = r\"\"\" $\\frac{\\partial}{\\partial \\theta_j}J(\\theta) = (h_\\theta (x) - y)x_j$ \"\"\"\n",
        "slp_chapter5_5 = \"\"\" L2 prefers weight vectors with many small weights, L1 prefers sparse\n",
        "solutions with some larger weights but many more weights set to zero.\"\"\"\n",
        "slp_chapter5_6 = r\"\"\" Softmax: $\\frac{exp(z_i)}{\\sum_{j=1}^k exp(z_j)}$ \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = r\"\"\" Unit: $z=b+\\sum_i w_i x_i $ \"\"\"\n",
        "slp_chapter7_2 = \"\"\" 2 layer network can solve XOR \"\"\"\n",
        "slp_chapter7_3 = \"\"\" One of the reasons we use non-linear activation functions for each layer\n",
        "in a neural network is that if we did not, the resulting network is exactly equivalent to\n",
        "a single-layer network. \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Neural language models represent words in this prior context by their embeddings,\n",
        "rather than just by their word identity as used in n-gram language models.\"\"\"\n",
        "slp_chapter7_5 = \"\"\" A one-hot vector is\n",
        "a vector that has one element equal to 1—in the dimension corresponding to that\n",
        "word’s index in the vocabulary— while all the other elements are set to zero. \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Loss, Optimizer, Gradient \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Neural language models use a neural network as a probabilistic classifier, to\n",
        "compute the probability of the next word given the previous n words. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = r\"\"\" \n",
        "Stochastic gradient descent chooses a single random example at a time and updates\n",
        "its weights on that example. As a result the updates can fluctuate.\n",
        "An alternate is batch training, which computes the gradient over the entire dataset.\n",
        "This gives a much better estimate of which direction to move the weights but takes a\n",
        "long time to compute.\n",
        "A commonly used compromise is mini-batch training, where we train on a small\n",
        "batch. The batch size can be 512 or 1024, often selected based on computational\n",
        "resources, so that all examples in the mini-batch can be processed in parallel. The loss\n",
        "is then accumulated.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"MLP\" : \"multi-layer perceptrons\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "bc6b2061-6a96-4853-8195-c11c90f75741"
      },
      "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 \nsigmoid: $\\sigma(z) = \\frac{1}{1+e^{-z}}$\n\n$1-\\sigma(x) = \\sigma(-x)$\n\n$\\sigma'(x) = \\sigma(x)(1-\\sigma(x))$\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n cross-entropy loss \n\n## SLP Chapter 5.3 The cross-entropy loss function\n $L = ylog \\hat{y} + (1-y)log (1-\\hat{y})$ \n\n## SLP Chapter 5.4 Gradient Descent\n $\\frac{\\partial}{\\partial \\theta_j}J(\\theta) = (h_\\theta (x) - y)x_j$ \n\n## SLP Chapter 5.5 Regularization\n L2 prefers weight vectors with many small weights, L1 prefers sparse\nsolutions with some larger weights but many more weights set to zero.\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Softmax: $\\frac{exp(z_i)}{\\sum_{j=1}^k exp(z_j)}$ \n\n## SLP Chapter 7.1 Units\n Unit: $z=b+\\sum_i w_i x_i $ \n\n## SLP Chapter 7.2 The XOR problem\n 2 layer network can solve XOR \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n One of the reasons we use non-linear activation functions for each layer\nin a neural network is that if we did not, the resulting network is exactly equivalent to\na single-layer network. \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Neural language models represent words in this prior context by their embeddings,\nrather than just by their word identity as used in n-gram language models.\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n A one-hot vector is\na vector that has one element equal to 1—in the dimension corresponding to that\nword’s index in the vocabulary— while all the other elements are set to zero. \n\n## SLP Chapter 7.6 Training Neural Nets\n Loss, Optimizer, Gradient \n\n## SLP Chapter 7.7 Training the neural language model\n Neural language models use a neural network as a probabilistic classifier, to\ncompute the probability of the next word given the previous n words. \n\n## Module 13 Lecture Notes\n \nStochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\nAn alternate is batch training, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\nA commonly used compromise is mini-batch training, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n\n\n## Module 13 Definitions\n* **Mlp** - multi-layer perceptrons\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 = r\"\"\" $PP_\\theta(w_{1:n}) = \\sqrt[n]{\\prod_{i=1}^n \\frac{1}{P_\\theta(w_i|w_{1:n-1})}}$ \"\"\"\n",
        "slp_chapter9_2 = r\"\"\" RNN: $h_i \\leftarrow g(Uh_{i-1} + W_x_i)$ \"\"\"\n",
        "slp_chapter9_3 = \"\"\" RNN language models process the input sequence one word at\n",
        "a time, attempting to predict the next word from the current word and the previous\n",
        "hidden state. RNNs don’t have the limited context problem that n-gram models\n",
        "have, since the hidden state can in principle represent information about all of the\n",
        "preceding words all the way back to the beginning of the sequence.\"\"\"\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 = \"\"\" Lexical Semantics: linguistics side \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Vector Semantics: math side \"\"\"\n",
        "slp_chapter6_3 = \"\"\" In a term-document matrix, each row represents a word in the vocabulary and each matrix column represents a document from some collection of documents. \"\"\"\n",
        "slp_chapter6_4 = r\"\"\" The cosine similarity metric between two vectors v and w : $cos(v,w) = \\frac{v \\dot w}{|v||w|}$\"\"\"\n",
        "slp_chapter6_8 = \"\"\" Word2vec embeddings are static embeddings, meaning that the method learns one fixed embedding for each word in the embeddings vocabulary. \n",
        "\n",
        "\"\"\"\n",
        "slp_chapter6_10 = \"\"\" semantic property of embeddings: capture relational meanings, extract changes over time \"\"\"\n",
        "slp_chapter6_11 = \"\"\" In addition to their ability to learn word meaning from text, embedding also reproduce the implicit biases and stereotypes that were latent in the text. \"\"\"\n",
        "slp_chapter6_12 = \"\"\" The most common metric is to test models' performances on similarity, computing the correlation between an\n",
        "algorithm’s word similarity scores and word similarity ratings assigned by humans. \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Embeddings = vector models of meaning \n",
        "\n",
        "More fine-grained than just a string or index\n",
        "\n",
        "Especially good at modeling similarity/analogy\n",
        "\n",
        "sparse models (tf-idf) \n",
        "\n",
        "dense models (word2vec, GLoVE)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"SGNS\" : \"skip-gram with negative sampling\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "149e281a-c063-495e-cb1d-42366af50004"
      },
      "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 $PP_\\theta(w_{1:n}) = \\sqrt[n]{\\prod_{i=1}^n \\frac{1}{P_\\theta(w_i|w_{1:n-1})}}$ \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n RNN: $h_i \\leftarrow g(Uh_{i-1} + W_x_i)$ \n\n## SLP Chapter 9.3 RNNs as Language Models\n RNN language models process the input sequence one word at\na time, attempting to predict the next word from the current word and the previous\nhidden state. RNNs don’t have the limited context problem that n-gram models\nhave, since the hidden state can in principle represent information about all of the\npreceding words all the way back to the beginning of the sequence.\n\n## SLP Chapter 6.1 Lexical Semantics\n Lexical Semantics: linguistics side \n\n## SLP Chapter 6.2 Vector Semantics\n Vector Semantics: math side \n\n## SLP Chapter 6.3 Words and Vectors\n In a term-document matrix, each row represents a word in the vocabulary and each matrix column represents a document from some collection of documents. \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n The cosine similarity metric between two vectors v and w : $cos(v,w) = \\frac{v \\dot w}{|v||w|}$\n\n## SLP Chapter 6.8 Word2vec\n Word2vec embeddings are static embeddings, meaning that the method learns one fixed embedding for each word in the embeddings vocabulary. \n\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n semantic property of embeddings: capture relational meanings, extract changes over time \n\n## SLP Chapter 6.11 Bias and Embeddings\n In addition to their ability to learn word meaning from text, embedding also reproduce the implicit biases and stereotypes that were latent in the text. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n The most common metric is to test models' performances on similarity, computing the correlation between an\nalgorithm’s word similarity scores and word similarity ratings assigned by humans. \n\n## Module 13 Lecture Notes\n \nStochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\nAn alternate is batch training, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\nA commonly used compromise is mini-batch training, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n\n\n## Module 14 Definitions\n* **Sgns** - skip-gram with negative sampling\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "48ef0147-9db9-4415-9dee-105470a5af90"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nMEU: maximum expected utility \n\n $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$    \n $EU(a) = \\sum_{s'} P(\\textnormal{RESULT}(a)=s')U(s')$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n$A \\succ B$  the agent prefers A over B \n   \n$A \\sim B$ the agent is indifferent between A and B \n   \nLottery: $L = [p_1,S_1; p_2,S_2;\\cdots; p_n,S_n]$   \norderability, transitivity, continuity, substitutability, monotonicity, and decomposability\n\n## AIMA Chapter 16.3 Utility Functions\n In reality, people's behaviors are not always rational. \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n An optimal policy is a policy that yields the highest expected utility \n\nAdditive undiscounted rewards will generally be infinite within infinite horizons. So we use discounted rewards. \n\n $U(s) = \\max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma U(s')] = \\max_a Q(s,a)$\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Value Iteration: $V_{k+1}(s) = \\max_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V_k(s')]$  Repeat until convergence Complexity of each iteration: $O(S^2A)$\n\nPolicy $\\pi^*(s) = \\argmax_a \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V_k(s')]$\nPolicy Evalutaion: $V^{\\pi_i}_{k+1}(s) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma V^{\\pi_i}_k(s')]$\n\n\nOne-step look-ahead: $\\pi_{i+1}(s) = \\argmax_a \\sum_{s'}T(s,a,s')[R(s,a, s')+\\gamma V^{\\pi}(s')]$\n\n\n## Module 8 Lecture Notes\n Transitions are Markovian: the probability of arriving in s' only depends on s and not the history of earlier states. \n\n\n\n\n## Module 8 Definitions\n* **Utility function** - express the desirability of a state\n* **Expected utility** - average utility value of the outcomes, weighted by the probability that the outcome occurs\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Multi-armed Bandit Problem \n\n## AIMA Chapter 22.1 Learning from Rewards\n Reinforcement learning differs from “just solving an MDP” because the agent is not given the MDP as a problem to solve; the agent is in the MDP. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Passive learning agent: to learn the utility function where the agent does not know the transition model\n\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Active learning agent gets to decide what actions to take.\n\nQ(s,a) denotes the expected total discounted reward if the agent takes action a in s and acts optimally thereafter.\n\n\nQ-learning is an off-policy learning algorithm and SARSA is an on-policy algorithm.\n\nQ-leaning:\n\n\n\n$Q(s,a) = \\sum_{s'}P(s'|s,a)[R(s,a,s')+\\gamma \\max_{a'}Q(s',a')] \\\\ Q(s,a) \\leftarrow Q(s,a) + \\alpha[R(s,a,s')+\\gamma \\max_{a'}Q(s',a')-Q(s,a)] = （1-\\alpha）Q(s,a)+\\alpha [sample]$\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \n\n\n $V(s) = w_1f_1(s)+w_2f_2(s)+\\cdots+w_nf_n(s) \n Q(s,a) = w_1f_1(s,a)+w_2f_2(s,a)+\\cdots+w_nf_n(s,a)$ \n  difference = $[r + \\gamma \\max_{a'}Q(s',a')]-Q(s,a)$\n  $w_i \\leftarrow w_i + \\alpha[$difference$] f_i(s,a)$\n  \n  \n\n## Module 9 Lecture Notes\n \nImportant ideas in reinforcement learning that came up: Exploration, Exploitation, Regret, Sampling, Difficulty\n \n\n## Module 9 Definitions\n* **Glie** - greedy in the limit of infinite exploration\n* **Sarsa** - $Q(s,a) \\leftarrow Q(s,a) + \\alpha[R(s,a,s')+\\gamma Q(s',a')-Q(s,a)]$\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Decision theory = Probability theory + Utility theory. \n\n## AIMA Chapter 12.2 Basic Probability Notation\n prior probabilities refer to degrees of belief in propositions in the absence of any other information.\n$P(a|b) = \\frac{P(a,b)}{P(b)}$\n$P(a\\lor b) = P(a) + P(b) - P(a\\land b)$\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Marginalization: $P(Y) = \\sum_z P(Y,Z=z) $\n\n## AIMA Chapter 12.4 Independence\n Independence: $P(a,b) = P(a)P(b)$  \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Bayes' Rule: $P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}$ \n\n## AIMA Chapter 12.6 Naive Bayes Models\n \nNaive Bayes (effects are conditional independent with each other): $P(cause, effect_1, \\cdots, effect_n) = P(cause)\\prod_i P(effect_i|cause)$\n\n \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n A probabilistic agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable. \n\n## SLP Chapter 3.1 N-Grams\n N-gram language model : $P(w_n|w_{1:n-1}) = P(w_n|w_{n-N+1:n-1}) $ \n\nMaximum likelihood estimation for bigram: $P(w_n|w_n-1) = \\frac{count(w_{n-1}, w_{n})}{count(w_{n-1})}$\n\n\n## SLP Chapter 3.2 Evaluating Language Models\n Perplexity: $PP(W) = P(w_1,w_2,\\cdots, w_N)^{-\\frac{1}{N}} = \\sqrt[N]{\\prod_{i=1}^{N}\\frac{1}{P(w_i|w_1\\cdots w_{i-1})}}$ \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Sampling from a distribution means to choose random points according to their likelihood. Thus sampling from a language model (which represents a distribution over sentences) means to generate some sentences, choosing\neach sentence according to its likelihood as defined by the model. Thus we are more likely to generate sentences that the model thinks have a high probability and less likely to generate sentences that the model thinks have a low probability. \n\n## SLP Chapter 3.4 Generalization and Zeros\n \nAn open vocabulary system open vocabulary is one in which we model these potential unknown words in the test set by adding a pseudo-word called <UNK>.\n\n\n\n## SLP Chapter 3.5 Smoothing\n To keep a language model from assigning zero probability to these unseen events, we’ll have to shave off a bit of probability mass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting. \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Efficiency considerations are important when building language models that use such large sets of n-grams. Rather than store each word as a string, it is generally represented in memory as a 64-bit hash number, with the words themselves stored on disk. Probabilities are generally quantized using only 4-8 bits (instead of 8-byte floats), and n-grams are stored in reverse tries. \n\n## Module 10 Lecture Notes\n \nChain Rule: $P(x_1, x_2, \\cdots, x_n) = \\prod_i P(x_i|x_1, \\cdots, x_{i-1})$\ne.g.: $P(x_1,x_2,x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$\n\nProbabilistic Language Modeling\nGoal: compute the probability of a sentence or sequence of words\n$P(W) = P(w_1,\\cdots, w_n)$\n\nRelated task: probability of an upcoming word\n$P(w_5|w_1, w_2, w_3, w_4)$\n\nA model that computes either of these is called a language model.\n\n\n \n\n## Module 10 Definitions\n* **Markov assumption** - Only depends on the previous k words, not the whole context\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n \nBayesian network is a directed graph (Directed Acyclic Graph) in which each node is annotated with quantitative probability information:\n\nNode: a random variable (associated local conditional probability information $P(x_i| parent(x_i)$)\n\n\nDirected Links: If there is an arrow from node X to node Y, X is said to be a parent of Y.\n\n\n \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n \n$P(x_1,\\cdots, x_n) = \\prod_{i=1}^n P(x_i|parents(x_i))$\n\nThe variable in Bayes Network is conditionally independent of its other predecessors, given its parents.\nA node is conditionally independant of its non-descendants given its parents. \n\nA node X is conditionally independant of all other nodes in the network given its Markov blanket.\n\n\n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n\nInference by Enumeration:\nEvidence variables: $E_1, \\cdots, E_k = e_1, \\cdots e_k$\n\nQuery variable: $Q$\n\nHidden variables: $H_1, \\cdots, H_r$\n\nWe want $P(Q|e_1, \\cdots, e_k)$\n\n\n$P(Q,e_1,\\cdots,e_k) = \\sum_{h_1,\\cdots, h_r} P(Q, H_1, \\cdots,H_r, e_1, \\cdots, e_k)$ (Use chain rule)\n\n$Z = \\sum_q P(Q,e_1,\\cdots, e_k) $\n\n$P(Q|e_1, \\cdots, e_k) = \\frac{1}{Z}P(Q,e_1,\\cdots,e_k)$\n\n \n\n## Module 11 Lecture Notes\n \njoint distribution over N Boolean variables: $2^N$\n\nN-node net in which nodes have up tp k parents: $N*2^{k+1}$\n\n\n## Module 11 Definitions\n* **Cpt** - conditional probability table\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n Supervised Learning, Unsupervised Learning, Reinforcement Learning \n\n## AIMA Chapter 19.2 Supervised Learning\n There is a bias–variance tradeoff: a choice between more complex, low-bias\nhypotheses that fit the training data well and simpler, low-variance hypotheses that may\ngeneralize better. \n\nOckham’s razor\n\n\n## AIMA Chapter 19.3 Learning Decision Trees\n Entropy: $H(V) = \\sum_k P(v_k)log(\\frac{1}{P(v_k)})$\n\n \n\n## AIMA Chapter 19.4 Model Selection and Optimization\n Model selection chooses a good hypothesis space, and optimization (also called training) finds the best hypothesis within that space.\n\nThis process of explicitly penalizing complex hypotheses is called regularization. Regularization term has a hyperparameter $\\lambda$.\n\n\n\n## AIMA Chapter 19.5 The Theory of Learning\n Any hypothesis that is consistent with a sufficiently large set of training examples is\nunlikely to be seriously wrong: that is, it must be probably approximately correct (PAC). \n\n## AIMA Chapter 19.6 Linear Regression and Classification\n L1 regularization tends to produce a sparse model. \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Naive Bayes(strong assumptions about feature independence):\n$P(Y,F_1,\\cdots, F_n) = P(Y) \\prod_i P(F_i|Y)$\n \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n The unknown words or very frequently occurred words will be ignored. \n\n## SLP Chapter 4.3 Worked Example\n maximum likelihood training \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n \nTrick 1: whether a word occurs or not seems to matter more than its frequency\n\nTrick 2: negation (NOT_)\n\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n A common solution here, rather than using all the words as individual features,\nis to predefine likely sets of words or phrases as features, combined with features\nthat are not purely linguistic. \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n $P(s|c) = \\prod_{i} P(w_i | c) $\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n precision: $\\frac{TP}{TP+FP}$ recall = $\\frac{TP}{TP+FN}$ accuracy=$\\frac{TP+TN}{TP+FP+TN+FN}$ \n\nNaive Bayes algorithm is  a multi-class classification algorithm.\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n K-fold cross-validation. \n\n## SLP Chapter 4.9 Statistical Significance Testing\nThere are two common non-parametric tests used in NLP: approximate ranapproximate\ndomization and the bootstrap test.\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n representational harms \n\n## Module 12 Lecture Notes\n SVM : Maximizing the margin, only support vectors matter \n\n## Module 12 Definitions\n* **Loocv** - leave-one-out cross-validation\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nsigmoid: $\\sigma(z) = \\frac{1}{1+e^{-z}}$\n\n$1-\\sigma(x) = \\sigma(-x)$\n\n$\\sigma'(x) = \\sigma(x)(1-\\sigma(x))$\n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n cross-entropy loss \n\n## SLP Chapter 5.3 The cross-entropy loss function\n $L = ylog \\hat{y} + (1-y)log (1-\\hat{y})$ \n\n## SLP Chapter 5.4 Gradient Descent\n $\\frac{\\partial}{\\partial \\theta_j}J(\\theta) = (h_\\theta (x) - y)x_j$ \n\n## SLP Chapter 5.5 Regularization\n L2 prefers weight vectors with many small weights, L1 prefers sparse\nsolutions with some larger weights but many more weights set to zero.\n\n## SLP Chapter 5.6 Multinomial logistic regression\n Softmax: $\\frac{exp(z_i)}{\\sum_{j=1}^k exp(z_j)}$ \n\n## SLP Chapter 7.1 Units\n Unit: $z=b+\\sum_i w_i x_i $ \n\n## SLP Chapter 7.2 The XOR problem\n 2 layer network can solve XOR \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n One of the reasons we use non-linear activation functions for each layer\nin a neural network is that if we did not, the resulting network is exactly equivalent to\na single-layer network. \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Neural language models represent words in this prior context by their embeddings,\nrather than just by their word identity as used in n-gram language models.\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n A one-hot vector is\na vector that has one element equal to 1—in the dimension corresponding to that\nword’s index in the vocabulary— while all the other elements are set to zero. \n\n## SLP Chapter 7.6 Training Neural Nets\n Loss, Optimizer, Gradient \n\n## SLP Chapter 7.7 Training the neural language model\n Neural language models use a neural network as a probabilistic classifier, to\ncompute the probability of the next word given the previous n words. \n\n## Module 13 Lecture Notes\n \nStochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\nAn alternate is batch training, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\nA commonly used compromise is mini-batch training, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n\n\n## Module 13 Definitions\n* **Mlp** - multi-layer perceptrons\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n $PP_\\theta(w_{1:n}) = \\sqrt[n]{\\prod_{i=1}^n \\frac{1}{P_\\theta(w_i|w_{1:n-1})}}$ \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n RNN: $h_i \\leftarrow g(Uh_{i-1} + W_x_i)$ \n\n## SLP Chapter 9.3 RNNs as Language Models\n RNN language models process the input sequence one word at\na time, attempting to predict the next word from the current word and the previous\nhidden state. RNNs don’t have the limited context problem that n-gram models\nhave, since the hidden state can in principle represent information about all of the\npreceding words all the way back to the beginning of the sequence.\n\n## SLP Chapter 6.1 Lexical Semantics\n Lexical Semantics: linguistics side \n\n## SLP Chapter 6.2 Vector Semantics\n Vector Semantics: math side \n\n## SLP Chapter 6.3 Words and Vectors\n In a term-document matrix, each row represents a word in the vocabulary and each matrix column represents a document from some collection of documents. \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n The cosine similarity metric between two vectors v and w : $cos(v,w) = \\frac{v \\dot w}{|v||w|}$\n\n## SLP Chapter 6.8 Word2vec\n Word2vec embeddings are static embeddings, meaning that the method learns one fixed embedding for each word in the embeddings vocabulary. \n\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n semantic property of embeddings: capture relational meanings, extract changes over time \n\n## SLP Chapter 6.11 Bias and Embeddings\n In addition to their ability to learn word meaning from text, embedding also reproduce the implicit biases and stereotypes that were latent in the text. \n\n## SLP Chapter 6.12 Evaluating Vector Models\n The most common metric is to test models' performances on similarity, computing the correlation between an\nalgorithm’s word similarity scores and word similarity ratings assigned by humans. \n\n## Module 13 Lecture Notes\n \nStochastic gradient descent chooses a single random example at a time and updates\nits weights on that example. As a result the updates can fluctuate.\nAn alternate is batch training, which computes the gradient over the entire dataset.\nThis gives a much better estimate of which direction to move the weights but takes a\nlong time to compute.\nA commonly used compromise is mini-batch training, where we train on a small\nbatch. The batch size can be 512 or 1024, often selected based on computational\nresources, so that all examples in the mini-batch can be processed in parallel. The loss\nis then accumulated.\n\n\n\n## Module 14 Definitions\n* **Sgns** - skip-gram with negative sampling\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AGHG6woP9Nac"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ufSUHVy-9Nr8"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OL10ekwC9N4S"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}