{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "elCCgY64spuq",
        "9xRbdqDox2zD"
      ]
    },
    "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": "244a30f8-39c3-46cf-83f4-9116a1ed468c"
      },
      "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": "28a3e65b-f6db-4d98-e155-99bca9a3e155"
      },
      "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",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" **MDPs:** fully observable environment, sequential decision process, stochastic/non-deterministic outcomes, additive rewards.\n",
        "\n",
        "**Stochastic transition model** is p(s'|s, a) read as the probability of arriving in satet s' given that we are in state s and we selected an action a.\n",
        "\n",
        "**Transition model**: T(s, a, s') = p(s'|s, a)\n",
        "\n",
        "**Reward Function**: Utility is sum of expected rewards over a sequence of actions. Rewards can be +ve or -ve.\n",
        "The decision process is sequential, so the agent can get a reward at each time step. R(s, a, s'). Rewards are **additive**.\n",
        "\n",
        "We need the following to describe an MDP:\n",
        "1. A set of states s belongs to S\n",
        "2. A set of actions A (a belongs to A)\n",
        "3. A transition function T(s, a, s') (probabilty - which is the model)\n",
        "4. A reward function R(s, a, s')\n",
        "5. An initial state $s_0$\n",
        "6. Optionally, one or more termminal states\n",
        "\n",
        "A solution to an MDP is a policy. A policy maps from a state onto the action\n",
        "to take if the agent is in that state.\n",
        "\n",
        "$\\pi (s) = a$ implies that $\\pi$ tells the agent what action to take at state s. In search problems the solution is a **plan**. $\\pi *$ denotes the optimal policy.\n",
        "\n",
        "*Note: Even though the policy told me to go right here, there’s no guarantee that me picking the action Right will result in me moving right. It’s stochastic!*\n",
        "\n",
        "Even if the same policy is executed multiple times by the agent, this may lead to different sequence of states and actions (environment history), and thus a different score under the reward function. \n",
        "Therefore we need to compute the expected utility of all the possible paths generated by a policy.\n",
        "\n",
        "**Discounting**: Sometimes an agent can be stuck in an infinite loop (keeps bouncing off a wall), here the rewards will keep on getting added. To avoid this we have discount.\n",
        "Each time we descend a level, we multiply in the discount once.\n",
        "Sooner rewards probably do have higher utility than later rewards. Also helps our algorithms converge\n",
        "\n",
        "$$ Additive utility: U([r_0, ...]) = r_0 + r_1 + ... $$\n",
        "$$ Discounted utility: U([r_0, ...]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 ... $$\n",
        "\n",
        "Problem: What if the game lasts forever? Do we get infinite rewards?\n",
        "\n",
        "Solutions:\n",
        "▪ Finite horizon: (similar to depth-limited search)\\n\n",
        "▪ Terminate episodes after a fixed T steps (e.g. life)\\n\n",
        "▪ Gives nonstationary policies (gamma depends on time left)\\n\n",
        "▪ Discounting: use 0 < $\\gamma$ < 1\\n\n",
        "\n",
        "Smaller $\\gamma$ menas smaller \"horizon\" which means a short term focus.\n",
        "\n",
        "**Optimal Quantities**:\\n\n",
        "1. *Value (utility) of a state s*: V*(s), expected utility starting in s and acting optimally\n",
        "2. *Value of a q-state (s, a)*: Q*(s, a) = expected utility starting out, having taken action a from state s\n",
        "3. *Optimal policy*: $\\pi*(s)$ = optimal action from state s\n",
        "\n",
        "**Recursive definition of Value**:\\n\n",
        "1. $ V*(s) = max_a Q*(s, a) $\n",
        "2. $ Q*(s, a) = \\sum T(s, a, s') [R(s, a, s') + \\gamma V*(s')] $\n",
        "3. $ V*(s) = max_a  \\sum T(s, a, s') [R(s, a, s') + \\gamma V*(s')] $\n",
        "\n",
        "These are the bellman equations ^. (Definition of “optimal utility” via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values).\n",
        "\n",
        "**Value Iteration**:\\n\n",
        "1. Start with $V_0(s) = 0$. No time steps left means an expected reward sum of zero.\n",
        "2. Given vector $V_k (s)$ of values, do one ply of expectimax from each state: \\n\n",
        "       $ V_k+1 (s) = max_a \\sum T(s, a, s') [R(s, a, s') + \\gamma V_k(s')]$\n",
        "3. Repeat until convergence\n",
        "4. Complexity of each iteration is $O(S^2 A)$ \\n\n",
        "Note: Policy may converge long before the values do.\n",
        " \n",
        "**Policy Evaluation**:\\n\n",
        "Use a fixed policy. We still have a recursive relation with a one-step look-ahead.\n",
        "\n",
        "\n",
        "$ V^\\pi (s) = \\sum_s' T(s, \\pi(s), s') [R(s, \\pi(s), s') + \\gamma V^\\pi (s')]$ \\n\n",
        "Note that the MAX is gone since there is only one policy.\n",
        "\n",
        "Efficiency: $O(S^2)$\n",
        "\n",
        "Without the maxes, its just a set of linear equations.\n",
        "\n",
        "Given values, calculate best policies.\n",
        "\n",
        "Do a mini-expectimax: $\\pi *(s) = argmax_a \\sum \\sum_s' T(s, \\pi(s), s') [R(s, \\pi(s), s') + \\gamma V^* (s')]$. This is called \n",
        "policy extraction, since it gets the policy implied by the values.\n",
        "\n",
        "**Computing actions from q-values**: $ \\pi*(s) = argmax_a Q*(s, a) $. \n",
        "\n",
        "*Actions are easier to select from q-vals than vals.*\n",
        "\n",
        "**Policy Iteration**: \\n\n",
        "Problems with Value iteration: its slow, the max at each stage rarely changes, policy coverges long before the values.\n",
        "\n",
        "1. Policy evaluation: calculate utilities for some fixed policy\n",
        "2. update policy using one steap look ahead, with utilities as future values\n",
        "3. repeat until convergence.\n",
        "\n",
        "This is optimal (gives optimal policy)\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\" : \"Assigns a single number to express the desirability of a state\",\n",
        "\"expected utility\" : \"average of utility values, weighted by the probability that the outcome occurs\",\n",
        "\"principle of MEU\":\"that a rational agent should choose the action that maximizes the agent’s expected utility\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "937320fb-27cd-4d13-dd0d-cccbc3b03752"
      },
      "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 Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n **MDPs:** fully observable environment, sequential decision process, stochastic/non-deterministic outcomes, additive rewards.\n\n**Stochastic transition model** is p(s'|s, a) read as the probability of arriving in satet s' given that we are in state s and we selected an action a.\n\n**Transition model**: T(s, a, s') = p(s'|s, a)\n\n**Reward Function**: Utility is sum of expected rewards over a sequence of actions. Rewards can be +ve or -ve.\nThe decision process is sequential, so the agent can get a reward at each time step. R(s, a, s'). Rewards are **additive**.\n\nWe need the following to describe an MDP:\n1. A set of states s belongs to S\n2. A set of actions A (a belongs to A)\n3. A transition function T(s, a, s') (probabilty - which is the model)\n4. A reward function R(s, a, s')\n5. An initial state $s_0$\n6. Optionally, one or more termminal states\n\nA solution to an MDP is a policy. A policy maps from a state onto the action\nto take if the agent is in that state.\n\n$\\pi (s) = a$ implies that $\\pi$ tells the agent what action to take at state s. In search problems the solution is a **plan**. $\\pi *$ denotes the optimal policy.\n\n*Note: Even though the policy told me to go right here, there’s no guarantee that me picking the action Right will result in me moving right. It’s stochastic!*\n\nEven if the same policy is executed multiple times by the agent, this may lead to different sequence of states and actions (environment history), and thus a different score under the reward function. \nTherefore we need to compute the expected utility of all the possible paths generated by a policy.\n\n**Discounting**: Sometimes an agent can be stuck in an infinite loop (keeps bouncing off a wall), here the rewards will keep on getting added. To avoid this we have discount.\nEach time we descend a level, we multiply in the discount once.\nSooner rewards probably do have higher utility than later rewards. Also helps our algorithms converge\n\n$$ Additive utility: U([r_0, ...]) = r_0 + r_1 + ... $$\n$$ Discounted utility: U([r_0, ...]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 ... $$\n\nProblem: What if the game lasts forever? Do we get infinite rewards?\n\nSolutions:\n▪ Finite horizon: (similar to depth-limited search)\n\n▪ Terminate episodes after a fixed T steps (e.g. life)\n\n▪ Gives nonstationary policies (gamma depends on time left)\n\n▪ Discounting: use 0 < $\\gamma$ < 1\n\n\nSmaller $\\gamma$ menas smaller \"horizon\" which means a short term focus.\n\n**Optimal Quantities**:\n\n1. *Value (utility) of a state s*: V*(s), expected utility starting in s and acting optimally\n2. *Value of a q-state (s, a)*: Q*(s, a) = expected utility starting out, having taken action a from state s\n3. *Optimal policy*: $\\pi*(s)$ = optimal action from state s\n\n**Recursive definition of Value**:\n\n1. $ V*(s) = max_a Q*(s, a) $\n2. $ Q*(s, a) = \\sum T(s, a, s') [R(s, a, s') + \\gamma V*(s')] $\n3. $ V*(s) = max_a  \\sum T(s, a, s') [R(s, a, s') + \\gamma V*(s')] $\n\nThese are the bellman equations ^. (Definition of “optimal utility” via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values).\n\n**Value Iteration**:\n\n1. Start with $V_0(s) = 0$. No time steps left means an expected reward sum of zero.\n2. Given vector $V_k (s)$ of values, do one ply of expectimax from each state: \n\n       $ V_k+1 (s) = max_a \\sum T(s, a, s') [R(s, a, s') + \\gamma V_k(s')]$\n3. Repeat until convergence\n4. Complexity of each iteration is $O(S^2 A)$ \n\nNote: Policy may converge long before the values do.\n \n**Policy Evaluation**:\n\nUse a fixed policy. We still have a recursive relation with a one-step look-ahead.\n\n\n$ V^\\pi (s) = \\sum_s' T(s, \\pi(s), s') [R(s, \\pi(s), s') + \\gamma V^\\pi (s')]$ \n\nNote that the MAX is gone since there is only one policy.\n\nEfficiency: $O(S^2)$\n\nWithout the maxes, its just a set of linear equations.\n\nGiven values, calculate best policies.\n\nDo a mini-expectimax: $\\pi *(s) = argmax_a \\sum \\sum_s' T(s, \\pi(s), s') [R(s, \\pi(s), s') + \\gamma V^* (s')]$. This is called \npolicy extraction, since it gets the policy implied by the values.\n\n**Computing actions from q-values**: $ \\pi*(s) = argmax_a Q*(s, a) $. \n\n*Actions are easier to select from q-vals than vals.*\n\n**Policy Iteration**: \n\nProblems with Value iteration: its slow, the max at each stage rarely changes, policy coverges long before the values.\n\n1. Policy evaluation: calculate utilities for some fixed policy\n2. update policy using one steap look ahead, with utilities as future values\n3. repeat until convergence.\n\nThis is optimal (gives optimal policy)\n\n\n\n## Module 8 Definitions\n* **Utility function** - Assigns a single number to express the desirability of a state\n* **Expected utility** - average of utility values, weighted by the probability that the outcome occurs\n* **Principle of meu** - that a rational agent should choose the action that maximizes the agent’s expected utility\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\"\n",
        "A one-armed bandit is a slot machine. A gambler can insert a coin, pull the\n",
        "lever, and collect the winnings (if any). An -armed bandit has levers. Behind each lever\n",
        "is a fixed but unknown probability distribution of winnings; each pull samples from that\n",
        "unknown distribution.\n",
        "\n",
        "The gambler must choose which lever to play on each successive coin—the one that has paid\n",
        "off best, or maybe one that has not been tried yet? This is an example of the ubiquitous\n",
        "tradeoff between exploitation of the current best action to obtain rewards and exploration\n",
        "of previously unknown states and actions to gain information, which can in some cases be\n",
        "converted into a better policy and better long-term rewards. \n",
        "\n",
        "Each arm is a Markov reward process (MRP) that is, an MDP with only one possible action $a_i$.\n",
        "\n",
        "$ maxE_{T>0} = [(\\\\sum^{T-1}_t=0 \\\\gamma^t R_t) + \\\\sum^\\\\infinity_t=T \\\\gamma^t \\\\lambda] = \\\\sum^\\\\infinity_t=0 \\\\gamma^t \\\\lambda $\n",
        "This is called the Gittins index - provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins\n",
        "indices.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "\n",
        "chapter22_1 =  \"\"\"\n",
        "All learning is from observed samples of outcomes.\n",
        "An alternative is reinforcement learning (RL), in which an agent interacts with the world\n",
        "and periodically receives rewards that reflect how well it is doing.\n",
        "E.g.: in chess - 1 is for winning, 0 is for losing and 0.5 for a draw.\n",
        "The goal of RL is same as MDPs - **maximize the expected sum of rewards**. \n",
        "The difference is that the agent is not given an MDP to solve, the agent is *in* the MDP.\n",
        "RL is much easier than supervised learning in the sense that devising rewards is much easier.\n",
        "\n",
        "**Types of RL:**\n",
        "\n",
        "1.Model-based reinforcement learning: agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act.\n",
        "In partially observable environments, the transition model is also useful for state estimation.\n",
        "Model-based reinforcement learning systems often learn a utility function U(s) - in terms of sum of rewards from state s onwards.\n",
        "\n",
        "Learn an approximate model based on experiences; solve for values as if the learned model were correct (estimated T and R)\n",
        "Step 1: Learn MDP model\n",
        "Step 2: Solve the learned MDP model: Value iteration, policy etc.\n",
        "\n",
        "Model will be learnt after ALL samples are observed. (this is called -)\n",
        "\n",
        "2. Model-free reinforcement learning: In these approaches the agent neither\n",
        "knows nor learns a transition model for the environment. Instead, it learns a more direct\n",
        "representation of how to behave. \\n\n",
        "    a. Action-utility learning: The most common form of action-utility learning is Q-learning, where the\n",
        "agent learns a Q-function, or Q(s, a), denoting sum of rewards from state s onward if action a is taken.  Given a Q-function, the agent can choose\n",
        "what to do in s by finding the action with the highest Q-value.\\n\n",
        "    b. Policy Search: The agent learns a policy $\\pi (s)$ that maps directly from states to actions. This is a reflex agent.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter22_2 =  \"\"\"\n",
        "Take an action. Compare the action from what we expected to what actually happened.\n",
        "No track of T(s, a, s') or R(s, a, s') functions. Solving MDPs is offline planning (you don't actually play the game)\n",
        "\n",
        "Policy Evaluation: input a fixed policy $\\pi(s)$. Just execute the policy and learn from experience\n",
        "This is NOT offline planning. You actually take actions in the world.\n",
        "\n",
        "**Direct Evaluation**\n",
        "\"\"\"\n",
        "chapter22_3 =  \"\"\"\n",
        "$$sample = R(s, a, s') + \\gamma max_a' Q(s', a')$$\n",
        "$$Q(s, a) = (1-\\\\alpha)Q(s, a) + \\\\alpha * sample$$\n",
        "\n",
        "Q-learning properties:\n",
        "Amazing result: Q-learning converges to optimal policy -- even\n",
        "if you’re acting suboptimally! This is called off-policy learning.\n",
        "\n",
        "Caveats: \n",
        "You have to explore enough.\n",
        "You have to eventually make the learning rate.\n",
        "small enough...but not decrease it too quickly.\n",
        "Basically, in the limit, it doesn’t matter how you select actions.\n",
        "\n",
        "**Epsilon greedy exploration**: with probability $\\\\epsilon$, act randomly, with probability $1-\\\\epsilon$, act on current policy.\n",
        "Problems with random actions? You do eventually explore the space, but keep\n",
        "thrashing around once learning is done. One solution: lower ε over time Another solution: exploration functions.\n",
        "\n",
        "**Exploration function:** takes values estimate u and a visit count n, returns optimistic utility\n",
        "\n",
        "**Regret** is a measure of your total mistake cost: the difference between your (expected) rewards, including\n",
        "youthful suboptimality, and optimal\n",
        "(expected) rewards\n",
        "Minimizing regret goes beyond\n",
        "learning to be optimal – it requires\n",
        "optimally learning to be optimal\n",
        "\"\"\"\n",
        "chapter22_4 =  \"\"\" Basic Q-Learning keeps a table of all q-values. In realistic situations, we cannot possibly learn about every single state! Too many states to visit them all in training. Too many states to hold the q-tables in memory.\n",
        "$Eval(s) = V(s) = w_1 f_1(s) + .... + w_n f_n(s)$\n",
        "\n",
        "$Q(s, a) = w_1 f_1(s, a) + .... + w_n f_n(s, a)$\n",
        "\n",
        "Advantage: our experience is summed up in a few powerful numbers.\\n\n",
        "Disadvantage: states may share features but actually be very different in value!\n",
        "\n",
        "**Approx Q-learning**:\n",
        "$difference = [r + \\\\gamma max Q(s', a')] - Q(s, a)$\\n\n",
        "$Q(s, a) = Q(s, a) + \\\\alpha * difference (exact Qs)$\\n\n",
        "$w_i = w_i + \\\\alpha * difference f_i(s, a) (approx Qs)$\n",
        "\n",
        "Intuitive interpretation: Adjust weights of active features.\n",
        "\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "**Passive reinforcement learning:**\n",
        "**Policy Evaluation:** input a fixed policy $\\pi(s)$. Just execute the policy and learn from experience\n",
        "This is NOT offline planning. You actually take actions in the world.\n",
        "\n",
        "**Direct Evaluation**\n",
        "Goal: Compute values for each state under π \n",
        "Idea: Average together observed sample values\n",
        "Act according to π\n",
        "Every time you visit a state, write down what the sum of discounted rewards turned out to be Average those samples.\n",
        "\n",
        "*From each state go to the end and use that rewards avg to calculate value of current state.*\n",
        "Bad thing: It wastes information about state connections. Each state must be learned separately. So, it takes a long time to learn.\n",
        "\n",
        "**Sample based policy evaluation**\n",
        "Take samples of outcomes s' by doing action, and average.\n",
        "$sample1 = R(s, \\pi(s), s_1') + \\gamma V_k(s_1')$\n",
        "\n",
        "$sample2 = R(s, \\pi(s), s_2') + \\gamma V_k(s_2')$\n",
        "\n",
        "$V_k+1(s) = 1/n \\sum(sample_i)$\n",
        "\n",
        "**Temporal difference learning:**\n",
        "Update V(s) each time we experience a transition (s, a, s', r).\n",
        "Things that are likely to occur will update more often.\n",
        "Policy is still fixed, we are evaluating.\n",
        "This is a running average.\n",
        "$ V(s) = (1- \\\\alpha) V(s) + \\\\alpha * sample $ (interpolate.. learning rate alpha).\n",
        "\n",
        "Running interpolation: (1-\\\\alpha) will get exponentially decayed. Objects in the very distant past will become less important.\n",
        "\n",
        "Problems with TD Value learning: \n",
        "TD value leaning is a model-free way to do policy evaluation, mimicking\n",
        "Bellman updates with running sample averages. However, if we want to turn values into a (new) policy, we’re sunk\n",
        "\n",
        "Idea: learn Q-values, not values. This will makes action selection model-free too!\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"stopping time\" : \"Stop after pulling the lever T times\",\n",
        "\"sparse rewards\":\"vase majority of the states, the agent is not given any informative reward signal at all. (chess)\",\n",
        "'exploration': 'trying unknown actions to get information',\n",
        "'exploitation':'eventually, use what you know',\n",
        "'regret':'even if you learn intelligently, you make mistakes',\n",
        "'sampling':' because of chance, you have to try things repeatedly',\n",
        "'difficulty':'learning can be much harder than solving a known MDP'\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "89fa9f8a-c0df-4e1b-fe2a-76e91163d71b"
      },
      "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",
        "  (\"AIMA Chapter 22.5 Policy Search\", chapter22_5),\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\nA one-armed bandit is a slot machine. A gambler can insert a coin, pull the\nlever, and collect the winnings (if any). An -armed bandit has levers. Behind each lever\nis a fixed but unknown probability distribution of winnings; each pull samples from that\nunknown distribution.\n\nThe gambler must choose which lever to play on each successive coin—the one that has paid\noff best, or maybe one that has not been tried yet? This is an example of the ubiquitous\ntradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information, which can in some cases be\nconverted into a better policy and better long-term rewards. \n\nEach arm is a Markov reward process (MRP) that is, an MDP with only one possible action $a_i$.\n\n$ maxE_{T>0} = [(\\sum^{T-1}_t=0 \\gamma^t R_t) + \\sum^\\infinity_t=T \\gamma^t \\lambda] = \\sum^\\infinity_t=0 \\gamma^t \\lambda $\nThis is called the Gittins index - provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins\nindices.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nAll learning is from observed samples of outcomes.\nAn alternative is reinforcement learning (RL), in which an agent interacts with the world\nand periodically receives rewards that reflect how well it is doing.\nE.g.: in chess - 1 is for winning, 0 is for losing and 0.5 for a draw.\nThe goal of RL is same as MDPs - **maximize the expected sum of rewards**. \nThe difference is that the agent is not given an MDP to solve, the agent is *in* the MDP.\nRL is much easier than supervised learning in the sense that devising rewards is much easier.\n\n**Types of RL:**\n\n1.Model-based reinforcement learning: agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act.\nIn partially observable environments, the transition model is also useful for state estimation.\nModel-based reinforcement learning systems often learn a utility function U(s) - in terms of sum of rewards from state s onwards.\n\nLearn an approximate model based on experiences; solve for values as if the learned model were correct (estimated T and R)\nStep 1: Learn MDP model\nStep 2: Solve the learned MDP model: Value iteration, policy etc.\n\nModel will be learnt after ALL samples are observed. (this is called -)\n\n2. Model-free reinforcement learning: In these approaches the agent neither\nknows nor learns a transition model for the environment. Instead, it learns a more direct\nrepresentation of how to behave. \n\n    a. Action-utility learning: The most common form of action-utility learning is Q-learning, where the\nagent learns a Q-function, or Q(s, a), denoting sum of rewards from state s onward if action a is taken.  Given a Q-function, the agent can choose\nwhat to do in s by finding the action with the highest Q-value.\n\n    b. Policy Search: The agent learns a policy $\\pi (s)$ that maps directly from states to actions. This is a reflex agent.\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\nTake an action. Compare the action from what we expected to what actually happened.\nNo track of T(s, a, s') or R(s, a, s') functions. Solving MDPs is offline planning (you don't actually play the game)\n\nPolicy Evaluation: input a fixed policy $\\pi(s)$. Just execute the policy and learn from experience\nThis is NOT offline planning. You actually take actions in the world.\n\n**Direct Evaluation**\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n$$sample = R(s, a, s') + \\gamma max_a' Q(s', a')$$\n$$Q(s, a) = (1-\\alpha)Q(s, a) + \\alpha * sample$$\n\nQ-learning properties:\nAmazing result: Q-learning converges to optimal policy -- even\nif you’re acting suboptimally! This is called off-policy learning.\n\nCaveats: \nYou have to explore enough.\nYou have to eventually make the learning rate.\nsmall enough...but not decrease it too quickly.\nBasically, in the limit, it doesn’t matter how you select actions.\n\n**Epsilon greedy exploration**: with probability $\\epsilon$, act randomly, with probability $1-\\epsilon$, act on current policy.\nProblems with random actions? You do eventually explore the space, but keep\nthrashing around once learning is done. One solution: lower ε over time Another solution: exploration functions.\n\n**Exploration function:** takes values estimate u and a visit count n, returns optimistic utility\n\n**Regret** is a measure of your total mistake cost: the difference between your (expected) rewards, including\nyouthful suboptimality, and optimal\n(expected) rewards\nMinimizing regret goes beyond\nlearning to be optimal – it requires\noptimally learning to be optimal\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Basic Q-Learning keeps a table of all q-values. In realistic situations, we cannot possibly learn about every single state! Too many states to visit them all in training. Too many states to hold the q-tables in memory.\n$Eval(s) = V(s) = w_1 f_1(s) + .... + w_n f_n(s)$\n\n$Q(s, a) = w_1 f_1(s, a) + .... + w_n f_n(s, a)$\n\nAdvantage: our experience is summed up in a few powerful numbers.\n\nDisadvantage: states may share features but actually be very different in value!\n\n**Approx Q-learning**:\n$difference = [r + \\gamma max Q(s', a')] - Q(s, a)$\n\n$Q(s, a) = Q(s, a) + \\alpha * difference (exact Qs)$\n\n$w_i = w_i + \\alpha * difference f_i(s, a) (approx Qs)$\n\nIntuitive interpretation: Adjust weights of active features.\n\n\n\n## AIMA Chapter 22.5 Policy Search\n Your summary here \n\n## Module 9 Lecture Notes\n \n**Passive reinforcement learning:**\n**Policy Evaluation:** input a fixed policy $\\pi(s)$. Just execute the policy and learn from experience\nThis is NOT offline planning. You actually take actions in the world.\n\n**Direct Evaluation**\nGoal: Compute values for each state under π \nIdea: Average together observed sample values\nAct according to π\nEvery time you visit a state, write down what the sum of discounted rewards turned out to be Average those samples.\n\n*From each state go to the end and use that rewards avg to calculate value of current state.*\nBad thing: It wastes information about state connections. Each state must be learned separately. So, it takes a long time to learn.\n\n**Sample based policy evaluation**\nTake samples of outcomes s' by doing action, and average.\n$sample1 = R(s, \\pi(s), s_1') + \\gamma V_k(s_1')$\n\n$sample2 = R(s, \\pi(s), s_2') + \\gamma V_k(s_2')$\n\n$V_k+1(s) = 1/n \\sum(sample_i)$\n\n**Temporal difference learning:**\nUpdate V(s) each time we experience a transition (s, a, s', r).\nThings that are likely to occur will update more often.\nPolicy is still fixed, we are evaluating.\nThis is a running average.\n$ V(s) = (1- \\alpha) V(s) + \\alpha * sample $ (interpolate.. learning rate alpha).\n\nRunning interpolation: (1-\\alpha) will get exponentially decayed. Objects in the very distant past will become less important.\n\nProblems with TD Value learning: \nTD value leaning is a model-free way to do policy evaluation, mimicking\nBellman updates with running sample averages. However, if we want to turn values into a (new) policy, we’re sunk\n\nIdea: learn Q-values, not values. This will makes action selection model-free too!\n\n\n\n## Module 9 Definitions\n* **Stopping time** - Stop after pulling the lever T times\n* **Sparse rewards** - vase majority of the states, the agent is not given any informative reward signal at all. (chess)\n* **Exploration** - trying unknown actions to get information\n* **Exploitation** - eventually, use what you know\n* **Regret** - even if you learn intelligently, you make mistakes\n* **Sampling** -  because of chance, you have to try things repeatedly\n* **Difficulty** - learning can be much harder than solving a known MDP\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "Bayes' Rule: $$P(b|a) = \\\\frac{P(a|b) P(b)}{P(a)}$$\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "Let’s see how a naive Bayes model can be used for the task of text classification: given a\n",
        "text, decide which of a predefined set of classes or categories it belongs to. Here the “cause”\n",
        "is the $Category$ variable, and the “effect” variables are the presence or absence of certain key\n",
        "words,$HasWord_i$.\n",
        "\n",
        "The task is to classify each sentence into a —the major sections of the newspaper:\n",
        "news, sports, business, weather, or entertainment. The naive Bayes model consists of the\n",
        "prior probabilities P(category) and conditional prob $P(HasWord_i | Category)$.\n",
        "\n",
        "\n",
        "The naive Bayes model assumes that words occur independently in documents, with\n",
        "frequencies determined by the document category. This independence assumption is clearly\n",
        "violated in practice. For example, the phrase “first quarter” occurs more frequently in\n",
        "business (or sports) articles than would be suggested by multiplying the probabilities of\n",
        "“first” and “quarter.\n",
        "\n",
        "\"\"\"\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",
        "\n",
        "**Product Rule**: $P(y) P(x|y) = P(x, y) $ \\n\n",
        "**Chain Rule**: $ P(a, b, c) = P(a) P(b|a) P(c|b,a) $\n",
        "\n",
        "**Bayes' Rule**: $ P(x, y) = P(y) P(x|y) = P(x) P(y|x) $ \\n\n",
        "\n",
        "$ P(x|y) = \\\\frac {P(x) P(y|x)} {P(y)} $\n",
        "\n",
        "**Probabilistic Language Model**: \n",
        "\n",
        "P(W) = P(w1, w2,....wn) [compute the probability of a sentence or sequence of words]\\n\n",
        "p(wn|w1, w2,...wn-1) [Related task: probability of an upcoming word] \\n\n",
        "A model that computes either is called a language model (LM).\n",
        "\n",
        "unigram:no history, bigram: 1 word as history, trigram,.. so on.\n",
        "\n",
        "**Unigram model:**\\n\n",
        "\n",
        "$ P(w_1 w_2 ... w_n) = \\\\prod_i P(w_i) $\n",
        "\n",
        "**Markov Assumption**: Only depends on previous k words, not the whole context.\n",
        "\n",
        "*Estimating bigram probabilities*: \\n\n",
        "\n",
        "$ P(w_i | w_{i-1}) = \\\\frac{count(w_{i-1}, w_i)}{count(w_{i-1})} $\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"axioms of probability\" : \"all probs between 0 and 1, sum of all probs = 1\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1621
        },
        "cellView": "form",
        "outputId": "67b99d2a-39db-4ecd-ec33-b1f28888ed0b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\nBayes' Rule: $$P(b|a) = \\frac{P(a|b) P(b)}{P(a)}$$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\nLet’s see how a naive Bayes model can be used for the task of text classification: given a\ntext, decide which of a predefined set of classes or categories it belongs to. Here the “cause”\nis the $Category$ variable, and the “effect” variables are the presence or absence of certain key\nwords,$HasWord_i$.\n\nThe task is to classify each sentence into a —the major sections of the newspaper:\nnews, sports, business, weather, or entertainment. The naive Bayes model consists of the\nprior probabilities P(category) and conditional prob $P(HasWord_i | Category)$.\n\n\nThe naive Bayes model assumes that words occur independently in documents, with\nfrequencies determined by the document category. This independence assumption is clearly\nviolated in practice. For example, the phrase “first quarter” occurs more frequently in\nbusiness (or sports) articles than would be suggested by multiplying the probabilities of\n“first” and “quarter.\n\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\n\n**Product Rule**: $P(y) P(x|y) = P(x, y) $ \n\n**Chain Rule**: $ P(a, b, c) = P(a) P(b|a) P(c|b,a) $\n\n**Bayes' Rule**: $ P(x, y) = P(y) P(x|y) = P(x) P(y|x) $ \n\n\n$ P(x|y) = \\frac {P(x) P(y|x)} {P(y)} $\n\n**Probabilistic Language Model**: \n\nP(W) = P(w1, w2,....wn) [compute the probability of a sentence or sequence of words]\n\np(wn|w1, w2,...wn-1) [Related task: probability of an upcoming word] \n\nA model that computes either is called a language model (LM).\n\nunigram:no history, bigram: 1 word as history, trigram,.. so on.\n\n**Unigram model:**\n\n\n$ P(w_1 w_2 ... w_n) = \\prod_i P(w_i) $\n\n**Markov Assumption**: Only depends on previous k words, not the whole context.\n\n*Estimating bigram probabilities*: \n\n\n$ P(w_i | w_{i-1}) = \\frac{count(w_{i-1}, w_i)}{count(w_{i-1})} $\n\n\n## Module 10 Definitions\n* **Axioms of probability** - all probs between 0 and 1, sum of all probs = 1\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 471
        },
        "cellView": "form",
        "outputId": "fc9cadcf-ec66-4c3b-96c5-0ca7d1413147"
      },
      "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 Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" 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",
        "\n",
        "**Naive Bayes**: \\n\n",
        "1. Get joint probability distribution over label variable Y \n",
        "\n",
        "$ P(Y, f_1, ... f_n) = [P(y_1, f_1, .. f_n) P(y_2, f_1, .. f_n), ... P(y_k, f_1, .. f_n)]^T $ \n",
        "\n",
        "$ P(Y, f_1, ... f_n) = [P(y_1) \\prod_i P(f_i | y_1) P(y_2) \\prod_i P(f_i | y_2)....] $ \n",
        "\n",
        "2. Sum to get the probability of evidence\n",
        "3. Normalize by dividing step 1 by step 2\n",
        "\n",
        "\n",
        "Bag-of-words Naïve Bayes (generative model):\\n\n",
        "• Features: Wi is the word at positon i\n",
        "• As before: predict label conditioned on feature variables (spam vs. ham)\n",
        "• As before: assume features are conditionally independent given label\n",
        "• New: each Wi is identically distributed\n",
        "\n",
        "$P(Y, W_1, ... W_n) = P(Y) \\prod_i P(W_i | Y) $\n",
        "\n",
        "“Tied” distributions and bag-of-words: \\n\n",
        "• Usually, each variable gets its own conditional probability distribution P(F|Y)\n",
        "• In a bag-of-words model\n",
        "• Each position is identically distributed\n",
        "• All positions share the same conditional probs P(W|Y)\n",
        "• Why make this assumption?\n",
        "• Called “bag-of-words” because model is insensitive to word order or reordering\n",
        "\n",
        "\n",
        "**Perceptron:**\n",
        "\n",
        "Inputs are **feature values**, each feature has a **weight**, sum is **activation**.\n",
        "\n",
        "$activation_w(x) = \\sum_i w_i f_i(x) = w f(x) $\n",
        "\n",
        "If the activation is positive - output +1, if negative: output -1 (Binary).\n",
        "\n",
        "Prediction highest score wins: $ y = argmax_y (w_y f(x)) $\n",
        "\n",
        "*Learning in binary perceptron*: \\n\n",
        "1. Start with wights = 0\\n\n",
        "2. For each training instance, classify with current weights (given above how to)\n",
        "\n",
        "3. If correct (y=y*), no change\n",
        "\n",
        "4. If wrong, adjust weight vector by adding or subtracting the feature vector. $w = w + y* f$.\n",
        "\n",
        "\n",
        "**Classification comparison**: \n",
        "\n",
        "Naïve Bayes\\n\n",
        "• Builds a model training data \\n\n",
        "• Gives prediction probabilities \\n\n",
        "• Strong assumptions about feature independence \\n\n",
        "• One pass through data (counting) \\n\n",
        "\n",
        "Perceptrons / MIRA: \\n\n",
        "• Makes less assumptions about data \\n\n",
        "• Mistake-driven learning \\n\n",
        "• Multiple passes through data (prediction) \\n\n",
        "• Often more accurate \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2182
        },
        "cellView": "form",
        "outputId": "c29e1617-8ea7-488c-f8ac-e63d187b43b6"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n\n**Naive Bayes**: \n\n1. Get joint probability distribution over label variable Y \n\n$ P(Y, f_1, ... f_n) = [P(y_1, f_1, .. f_n) P(y_2, f_1, .. f_n), ... P(y_k, f_1, .. f_n)]^T $ \n\n$ P(Y, f_1, ... f_n) = [P(y_1) \\prod_i P(f_i | y_1) P(y_2) \\prod_i P(f_i | y_2)....] $ \n\n2. Sum to get the probability of evidence\n3. Normalize by dividing step 1 by step 2\n\n\nBag-of-words Naïve Bayes (generative model):\n\n• Features: Wi is the word at positon i\n• As before: predict label conditioned on feature variables (spam vs. ham)\n• As before: assume features are conditionally independent given label\n• New: each Wi is identically distributed\n\n$P(Y, W_1, ... W_n) = P(Y) \\prod_i P(W_i | Y) $\n\n“Tied” distributions and bag-of-words: \n\n• Usually, each variable gets its own conditional probability distribution P(F|Y)\n• In a bag-of-words model\n• Each position is identically distributed\n• All positions share the same conditional probs P(W|Y)\n• Why make this assumption?\n• Called “bag-of-words” because model is insensitive to word order or reordering\n\n\n**Perceptron:**\n\nInputs are **feature values**, each feature has a **weight**, sum is **activation**.\n\n$activation_w(x) = \\sum_i w_i f_i(x) = w f(x) $\n\nIf the activation is positive - output +1, if negative: output -1 (Binary).\n\nPrediction highest score wins: $ y = argmax_y (w_y f(x)) $\n\n*Learning in binary perceptron*: \n\n1. Start with wights = 0\n\n2. For each training instance, classify with current weights (given above how to)\n\n3. If correct (y=y*), no change\n\n4. If wrong, adjust weight vector by adding or subtracting the feature vector. $w = w + y* f$.\n\n\n**Classification comparison**: \n\nNaïve Bayes\n\n• Builds a model training data \n\n• Gives prediction probabilities \n\n• Strong assumptions about feature independence \n\n• One pass through data (counting) \n\n\nPerceptrons / MIRA: \n\n• Makes less assumptions about data \n\n• Mistake-driven learning \n\n• Multiple passes through data (prediction) \n\n• Often more accurate \n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "Classifier components: \\n\n",
        "1. Feature representation of the input [x1, x2... xn]\n",
        "2. A classification function that computes the estimated class y_hat via p(y|x)\n",
        "3. An objective function for learning, usually involvinf minimizing error on training samples\n",
        "4. An algorithm for optimizing objective function.\n",
        "\n",
        "Decision boundary for sigmoid: P(y=1) = sigmoid(wx + b)\\n\n",
        "y_hat = 1 if P(y=1|x) > 0.5 else 0\n",
        "\n",
        "Loss function:  \n",
        "\n",
        "$log p(y|x) = y log(y^{hat}) + (1-y)log(1-y^{hat}) $\n",
        "\n",
        "This tells us what log likelihood should be\n",
        "maximized. But for loss functions, we want to\n",
        "minimize things, so we’ll flip the sign. This is called cross-entropy loss.\n",
        "\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": 1308
        },
        "cellView": "form",
        "outputId": "c65558c3-5eb5-47f4-eec0-9117c32ad7f0"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\nClassifier components: \n\n1. Feature representation of the input [x1, x2... xn]\n2. A classification function that computes the estimated class y_hat via p(y|x)\n3. An objective function for learning, usually involvinf minimizing error on training samples\n4. An algorithm for optimizing objective function.\n\nDecision boundary for sigmoid: P(y=1) = sigmoid(wx + b)\n\ny_hat = 1 if P(y=1|x) > 0.5 else 0\n\nLoss function:  \n\n$log p(y|x) = y log(y^{hat}) + (1-y)log(1-y^{hat}) $\n\nThis tells us what log likelihood should be\nmaximized. But for loss functions, we want to\nminimize things, so we’ll flip the sign. This is called cross-entropy loss.\n\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",
        "L2 norm is used to normalize data that makes sure words that are similar are closer to each other.\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": 1175
        },
        "outputId": "cab7923c-2a57-4281-eef9-d23a12a7c6fb"
      },
      "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\nClassifier components: \n\n1. Feature representation of the input [x1, x2... xn]\n2. A classification function that computes the estimated class y_hat via p(y|x)\n3. An objective function for learning, usually involvinf minimizing error on training samples\n4. An algorithm for optimizing objective function.\n\nDecision boundary for sigmoid: P(y=1) = sigmoid(wx + b)\n\ny_hat = 1 if P(y=1|x) > 0.5 else 0\n\nLoss function:  \n\n$log p(y|x) = y log(y^{hat}) + (1-y)log(1-y^{hat}) $\n\nThis tells us what log likelihood should be\nmaximized. But for loss functions, we want to\nminimize things, so we’ll flip the sign. This is called cross-entropy loss.\n\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 11331
        },
        "id": "T3cm1WV542_a",
        "outputId": "3b33d0ed-f294-4f07-a692-6cd8acf7b003"
      },
      "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 Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n **MDPs:** fully observable environment, sequential decision process, stochastic/non-deterministic outcomes, additive rewards.\n\n**Stochastic transition model** is p(s'|s, a) read as the probability of arriving in satet s' given that we are in state s and we selected an action a.\n\n**Transition model**: T(s, a, s') = p(s'|s, a)\n\n**Reward Function**: Utility is sum of expected rewards over a sequence of actions. Rewards can be +ve or -ve.\nThe decision process is sequential, so the agent can get a reward at each time step. R(s, a, s'). Rewards are **additive**.\n\nWe need the following to describe an MDP:\n1. A set of states s belongs to S\n2. A set of actions A (a belongs to A)\n3. A transition function T(s, a, s') (probabilty - which is the model)\n4. A reward function R(s, a, s')\n5. An initial state $s_0$\n6. Optionally, one or more termminal states\n\nA solution to an MDP is a policy. A policy maps from a state onto the action\nto take if the agent is in that state.\n\n$\\pi (s) = a$ implies that $\\pi$ tells the agent what action to take at state s. In search problems the solution is a **plan**. $\\pi *$ denotes the optimal policy.\n\n*Note: Even though the policy told me to go right here, there’s no guarantee that me picking the action Right will result in me moving right. It’s stochastic!*\n\nEven if the same policy is executed multiple times by the agent, this may lead to different sequence of states and actions (environment history), and thus a different score under the reward function. \nTherefore we need to compute the expected utility of all the possible paths generated by a policy.\n\n**Discounting**: Sometimes an agent can be stuck in an infinite loop (keeps bouncing off a wall), here the rewards will keep on getting added. To avoid this we have discount.\nEach time we descend a level, we multiply in the discount once.\nSooner rewards probably do have higher utility than later rewards. Also helps our algorithms converge\n\n$$ Additive utility: U([r_0, ...]) = r_0 + r_1 + ... $$\n$$ Discounted utility: U([r_0, ...]) = r_0 + \\gamma r_1 + \\gamma^2 r_2 ... $$\n\nProblem: What if the game lasts forever? Do we get infinite rewards?\n\nSolutions:\n▪ Finite horizon: (similar to depth-limited search)\n\n▪ Terminate episodes after a fixed T steps (e.g. life)\n\n▪ Gives nonstationary policies (gamma depends on time left)\n\n▪ Discounting: use 0 < $\\gamma$ < 1\n\n\nSmaller $\\gamma$ menas smaller \"horizon\" which means a short term focus.\n\n**Optimal Quantities**:\n\n1. *Value (utility) of a state s*: V*(s), expected utility starting in s and acting optimally\n2. *Value of a q-state (s, a)*: Q*(s, a) = expected utility starting out, having taken action a from state s\n3. *Optimal policy*: $\\pi*(s)$ = optimal action from state s\n\n**Recursive definition of Value**:\n\n1. $ V*(s) = max_a Q*(s, a) $\n2. $ Q*(s, a) = \\sum T(s, a, s') [R(s, a, s') + \\gamma V*(s')] $\n3. $ V*(s) = max_a  \\sum T(s, a, s') [R(s, a, s') + \\gamma V*(s')] $\n\nThese are the bellman equations ^. (Definition of “optimal utility” via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values).\n\n**Value Iteration**:\n\n1. Start with $V_0(s) = 0$. No time steps left means an expected reward sum of zero.\n2. Given vector $V_k (s)$ of values, do one ply of expectimax from each state: \n\n       $ V_k+1 (s) = max_a \\sum T(s, a, s') [R(s, a, s') + \\gamma V_k(s')]$\n3. Repeat until convergence\n4. Complexity of each iteration is $O(S^2 A)$ \n\nNote: Policy may converge long before the values do.\n \n**Policy Evaluation**:\n\nUse a fixed policy. We still have a recursive relation with a one-step look-ahead.\n\n\n$ V^\\pi (s) = \\sum_s' T(s, \\pi(s), s') [R(s, \\pi(s), s') + \\gamma V^\\pi (s')]$ \n\nNote that the MAX is gone since there is only one policy.\n\nEfficiency: $O(S^2)$\n\nWithout the maxes, its just a set of linear equations.\n\nGiven values, calculate best policies.\n\nDo a mini-expectimax: $\\pi *(s) = argmax_a \\sum \\sum_s' T(s, \\pi(s), s') [R(s, \\pi(s), s') + \\gamma V^* (s')]$. This is called \npolicy extraction, since it gets the policy implied by the values.\n\n**Computing actions from q-values**: $ \\pi*(s) = argmax_a Q*(s, a) $. \n\n*Actions are easier to select from q-vals than vals.*\n\n**Policy Iteration**: \n\nProblems with Value iteration: its slow, the max at each stage rarely changes, policy coverges long before the values.\n\n1. Policy evaluation: calculate utilities for some fixed policy\n2. update policy using one steap look ahead, with utilities as future values\n3. repeat until convergence.\n\nThis is optimal (gives optimal policy)\n\n\n\n## Module 8 Definitions\n* **Utility function** - Assigns a single number to express the desirability of a state\n* **Expected utility** - average of utility values, weighted by the probability that the outcome occurs\n* **Principle of meu** - that a rational agent should choose the action that maximizes the agent’s expected utility\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n\nA one-armed bandit is a slot machine. A gambler can insert a coin, pull the\nlever, and collect the winnings (if any). An -armed bandit has levers. Behind each lever\nis a fixed but unknown probability distribution of winnings; each pull samples from that\nunknown distribution.\n\nThe gambler must choose which lever to play on each successive coin—the one that has paid\noff best, or maybe one that has not been tried yet? This is an example of the ubiquitous\ntradeoff between exploitation of the current best action to obtain rewards and exploration\nof previously unknown states and actions to gain information, which can in some cases be\nconverted into a better policy and better long-term rewards. \n\nEach arm is a Markov reward process (MRP) that is, an MDP with only one possible action $a_i$.\n\n$ maxE_{T>0} = [(\\sum^{T-1}_t=0 \\gamma^t R_t) + \\sum^\\infinity_t=T \\gamma^t \\lambda] = \\sum^\\infinity_t=0 \\gamma^t \\lambda $\nThis is called the Gittins index - provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins\nindices.\n\n\n## AIMA Chapter 22.1 Learning from Rewards\n\nAll learning is from observed samples of outcomes.\nAn alternative is reinforcement learning (RL), in which an agent interacts with the world\nand periodically receives rewards that reflect how well it is doing.\nE.g.: in chess - 1 is for winning, 0 is for losing and 0.5 for a draw.\nThe goal of RL is same as MDPs - **maximize the expected sum of rewards**. \nThe difference is that the agent is not given an MDP to solve, the agent is *in* the MDP.\nRL is much easier than supervised learning in the sense that devising rewards is much easier.\n\n**Types of RL:**\n\n1.Model-based reinforcement learning: agent uses a transition model of the environment to help interpret the reward signals and to make decisions about how to act.\nIn partially observable environments, the transition model is also useful for state estimation.\nModel-based reinforcement learning systems often learn a utility function U(s) - in terms of sum of rewards from state s onwards.\n\nLearn an approximate model based on experiences; solve for values as if the learned model were correct (estimated T and R)\nStep 1: Learn MDP model\nStep 2: Solve the learned MDP model: Value iteration, policy etc.\n\nModel will be learnt after ALL samples are observed. (this is called -)\n\n2. Model-free reinforcement learning: In these approaches the agent neither\nknows nor learns a transition model for the environment. Instead, it learns a more direct\nrepresentation of how to behave. \n\n    a. Action-utility learning: The most common form of action-utility learning is Q-learning, where the\nagent learns a Q-function, or Q(s, a), denoting sum of rewards from state s onward if action a is taken.  Given a Q-function, the agent can choose\nwhat to do in s by finding the action with the highest Q-value.\n\n    b. Policy Search: The agent learns a policy $\\pi (s)$ that maps directly from states to actions. This is a reflex agent.\n\n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n\nTake an action. Compare the action from what we expected to what actually happened.\nNo track of T(s, a, s') or R(s, a, s') functions. Solving MDPs is offline planning (you don't actually play the game)\n\nPolicy Evaluation: input a fixed policy $\\pi(s)$. Just execute the policy and learn from experience\nThis is NOT offline planning. You actually take actions in the world.\n\n**Direct Evaluation**\n\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n\n$$sample = R(s, a, s') + \\gamma max_a' Q(s', a')$$\n$$Q(s, a) = (1-\\alpha)Q(s, a) + \\alpha * sample$$\n\nQ-learning properties:\nAmazing result: Q-learning converges to optimal policy -- even\nif you’re acting suboptimally! This is called off-policy learning.\n\nCaveats: \nYou have to explore enough.\nYou have to eventually make the learning rate.\nsmall enough...but not decrease it too quickly.\nBasically, in the limit, it doesn’t matter how you select actions.\n\n**Epsilon greedy exploration**: with probability $\\epsilon$, act randomly, with probability $1-\\epsilon$, act on current policy.\nProblems with random actions? You do eventually explore the space, but keep\nthrashing around once learning is done. One solution: lower ε over time Another solution: exploration functions.\n\n**Exploration function:** takes values estimate u and a visit count n, returns optimistic utility\n\n**Regret** is a measure of your total mistake cost: the difference between your (expected) rewards, including\nyouthful suboptimality, and optimal\n(expected) rewards\nMinimizing regret goes beyond\nlearning to be optimal – it requires\noptimally learning to be optimal\n\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Basic Q-Learning keeps a table of all q-values. In realistic situations, we cannot possibly learn about every single state! Too many states to visit them all in training. Too many states to hold the q-tables in memory.\n$Eval(s) = V(s) = w_1 f_1(s) + .... + w_n f_n(s)$\n\n$Q(s, a) = w_1 f_1(s, a) + .... + w_n f_n(s, a)$\n\nAdvantage: our experience is summed up in a few powerful numbers.\n\nDisadvantage: states may share features but actually be very different in value!\n\n**Approx Q-learning**:\n$difference = [r + \\gamma max Q(s', a')] - Q(s, a)$\n\n$Q(s, a) = Q(s, a) + \\alpha * difference (exact Qs)$\n\n$w_i = w_i + \\alpha * difference f_i(s, a) (approx Qs)$\n\nIntuitive interpretation: Adjust weights of active features.\n\n\n\n## AIMA Chapter 22.5 Policy Search\n Your summary here \n\n## Module 9 Lecture Notes\n \n**Passive reinforcement learning:**\n**Policy Evaluation:** input a fixed policy $\\pi(s)$. Just execute the policy and learn from experience\nThis is NOT offline planning. You actually take actions in the world.\n\n**Direct Evaluation**\nGoal: Compute values for each state under π \nIdea: Average together observed sample values\nAct according to π\nEvery time you visit a state, write down what the sum of discounted rewards turned out to be Average those samples.\n\n*From each state go to the end and use that rewards avg to calculate value of current state.*\nBad thing: It wastes information about state connections. Each state must be learned separately. So, it takes a long time to learn.\n\n**Sample based policy evaluation**\nTake samples of outcomes s' by doing action, and average.\n$sample1 = R(s, \\pi(s), s_1') + \\gamma V_k(s_1')$\n\n$sample2 = R(s, \\pi(s), s_2') + \\gamma V_k(s_2')$\n\n$V_k+1(s) = 1/n \\sum(sample_i)$\n\n**Temporal difference learning:**\nUpdate V(s) each time we experience a transition (s, a, s', r).\nThings that are likely to occur will update more often.\nPolicy is still fixed, we are evaluating.\nThis is a running average.\n$ V(s) = (1- \\alpha) V(s) + \\alpha * sample $ (interpolate.. learning rate alpha).\n\nRunning interpolation: (1-\\alpha) will get exponentially decayed. Objects in the very distant past will become less important.\n\nProblems with TD Value learning: \nTD value leaning is a model-free way to do policy evaluation, mimicking\nBellman updates with running sample averages. However, if we want to turn values into a (new) policy, we’re sunk\n\nIdea: learn Q-values, not values. This will makes action selection model-free too!\n\n\n\n## Module 9 Definitions\n* **Stopping time** - Stop after pulling the lever T times\n* **Sparse rewards** - vase majority of the states, the agent is not given any informative reward signal at all. (chess)\n* **Exploration** - trying unknown actions to get information\n* **Exploitation** - eventually, use what you know\n* **Regret** - even if you learn intelligently, you make mistakes\n* **Sampling** -  because of chance, you have to try things repeatedly\n* **Difficulty** - learning can be much harder than solving a known MDP\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\nBayes' Rule: $$P(b|a) = \\frac{P(a|b) P(b)}{P(a)}$$\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n\nLet’s see how a naive Bayes model can be used for the task of text classification: given a\ntext, decide which of a predefined set of classes or categories it belongs to. Here the “cause”\nis the $Category$ variable, and the “effect” variables are the presence or absence of certain key\nwords,$HasWord_i$.\n\nThe task is to classify each sentence into a —the major sections of the newspaper:\nnews, sports, business, weather, or entertainment. The naive Bayes model consists of the\nprior probabilities P(category) and conditional prob $P(HasWord_i | Category)$.\n\n\nThe naive Bayes model assumes that words occur independently in documents, with\nfrequencies determined by the document category. This independence assumption is clearly\nviolated in practice. For example, the phrase “first quarter” occurs more frequently in\nbusiness (or sports) articles than would be suggested by multiplying the probabilities of\n“first” and “quarter.\n\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\n\n**Product Rule**: $P(y) P(x|y) = P(x, y) $ \n\n**Chain Rule**: $ P(a, b, c) = P(a) P(b|a) P(c|b,a) $\n\n**Bayes' Rule**: $ P(x, y) = P(y) P(x|y) = P(x) P(y|x) $ \n\n\n$ P(x|y) = \\frac {P(x) P(y|x)} {P(y)} $\n\n**Probabilistic Language Model**: \n\nP(W) = P(w1, w2,....wn) [compute the probability of a sentence or sequence of words]\n\np(wn|w1, w2,...wn-1) [Related task: probability of an upcoming word] \n\nA model that computes either is called a language model (LM).\n\nunigram:no history, bigram: 1 word as history, trigram,.. so on.\n\n**Unigram model:**\n\n\n$ P(w_1 w_2 ... w_n) = \\prod_i P(w_i) $\n\n**Markov Assumption**: Only depends on previous k words, not the whole context.\n\n*Estimating bigram probabilities*: \n\n\n$ P(w_i | w_{i-1}) = \\frac{count(w_{i-1}, w_i)}{count(w_{i-1})} $\n\n\n## Module 10 Definitions\n* **Axioms of probability** - all probs between 0 and 1, sum of all probs = 1\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n 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\n\n**Naive Bayes**: \n\n1. Get joint probability distribution over label variable Y \n\n$ P(Y, f_1, ... f_n) = [P(y_1, f_1, .. f_n) P(y_2, f_1, .. f_n), ... P(y_k, f_1, .. f_n)]^T $ \n\n$ P(Y, f_1, ... f_n) = [P(y_1) \\prod_i P(f_i | y_1) P(y_2) \\prod_i P(f_i | y_2)....] $ \n\n2. Sum to get the probability of evidence\n3. Normalize by dividing step 1 by step 2\n\n\nBag-of-words Naïve Bayes (generative model):\n\n• Features: Wi is the word at positon i\n• As before: predict label conditioned on feature variables (spam vs. ham)\n• As before: assume features are conditionally independent given label\n• New: each Wi is identically distributed\n\n$P(Y, W_1, ... W_n) = P(Y) \\prod_i P(W_i | Y) $\n\n“Tied” distributions and bag-of-words: \n\n• Usually, each variable gets its own conditional probability distribution P(F|Y)\n• In a bag-of-words model\n• Each position is identically distributed\n• All positions share the same conditional probs P(W|Y)\n• Why make this assumption?\n• Called “bag-of-words” because model is insensitive to word order or reordering\n\n\n**Perceptron:**\n\nInputs are **feature values**, each feature has a **weight**, sum is **activation**.\n\n$activation_w(x) = \\sum_i w_i f_i(x) = w f(x) $\n\nIf the activation is positive - output +1, if negative: output -1 (Binary).\n\nPrediction highest score wins: $ y = argmax_y (w_y f(x)) $\n\n*Learning in binary perceptron*: \n\n1. Start with wights = 0\n\n2. For each training instance, classify with current weights (given above how to)\n\n3. If correct (y=y*), no change\n\n4. If wrong, adjust weight vector by adding or subtracting the feature vector. $w = w + y* f$.\n\n\n**Classification comparison**: \n\nNaïve Bayes\n\n• Builds a model training data \n\n• Gives prediction probabilities \n\n• Strong assumptions about feature independence \n\n• One pass through data (counting) \n\n\nPerceptrons / MIRA: \n\n• Makes less assumptions about data \n\n• Mistake-driven learning \n\n• Multiple passes through data (prediction) \n\n• Often more accurate \n\n\n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\nClassifier components: \n\n1. Feature representation of the input [x1, x2... xn]\n2. A classification function that computes the estimated class y_hat via p(y|x)\n3. An objective function for learning, usually involvinf minimizing error on training samples\n4. An algorithm for optimizing objective function.\n\nDecision boundary for sigmoid: P(y=1) = sigmoid(wx + b)\n\ny_hat = 1 if P(y=1|x) > 0.5 else 0\n\nLoss function:  \n\n$log p(y|x) = y log(y^{hat}) + (1-y)log(1-y^{hat}) $\n\nThis tells us what log likelihood should be\nmaximized. But for loss functions, we want to\nminimize things, so we’ll flip the sign. This is called cross-entropy loss.\n\n\n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n\nClassifier components: \n\n1. Feature representation of the input [x1, x2... xn]\n2. A classification function that computes the estimated class y_hat via p(y|x)\n3. An objective function for learning, usually involvinf minimizing error on training samples\n4. An algorithm for optimizing objective function.\n\nDecision boundary for sigmoid: P(y=1) = sigmoid(wx + b)\n\ny_hat = 1 if P(y=1|x) > 0.5 else 0\n\nLoss function:  \n\n$log p(y|x) = y log(y^{hat}) + (1-y)log(1-y^{hat}) $\n\nThis tells us what log likelihood should be\nmaximized. But for loss functions, we want to\nminimize things, so we’ll flip the sign. This is called cross-entropy loss.\n\n\n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "CqPu_x8qtTJM"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}