{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Divya_CIS 521 Midterm 2 Notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "elCCgY64spuq"
      ]
    },
    "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": "a1d54eb8-6717-4609-d53a-fb0f86b5dbba"
      },
      "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": 22,
      "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": "ca268197-41f8-4018-e6a2-753000f4d0a2"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 24,
      "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 = \"\"\"MEU principle formalizes that intelligent agent should do right thing, but does not operationalize \n",
        "that advice. If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\n",
        "the agent will achieve the highest possible performance score, averaged over all possible environments. Performance measure applied \n",
        "retrospectively after an agent completes a sequence of actions VS utility function applies to the very next state used to guide actions \n",
        "step by step.\"\"\"\n",
        "\n",
        "chapter16_2 =  \"\"\"(1) ORDERABILITY: given any two lotteries, a rational agent must either prefer one or else rate equally preferable\n",
        "(2) TRANSITIVITY: given any three lotteries, if agent prefers A to B and B to C, must prefer A to C (3) CONTINUITY: if B is between A and C \n",
        "in preference, there is a probability p for which agent is indifferent between getting B for sure and the lottery that yields A with probability p\n",
        "and C with probability 1-p (4) SUBSTITUTABILITY: if agent indifferent between A and B, also indifferent between two more complex lotteries that are \n",
        "same except B substituted for A in one of them (5) MONOTONICITY: if agent prefers A to B, agent must prefer lottery that has a higher probability for A\n",
        "and vice versa (6) DECOMPOSABILITY: compound lotteries can be reduced to simpler ones using probability laws. Existence of utility function: if agent's preferences\n",
        "obey axioms of utility, exists function U such that U(A) > U(B) iff A > B, and U(A) = U(B) if indifferent. \"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\"Agents exhibit a monotonic preference for more money. Most people have a utility function that is concave for positive wealth. \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\"The utility of an environment history is the sum of the rewards received. MDP consists of a set of states (with initial state), set of \n",
        "actions in each state, a transition model, and a reward function. The quality of a policy is measured by the expected utility of the possible environment histories generated \n",
        "by that policy. When discount factor is close to 0, rewards in the distant future are viewed as insignificant, and when close to 1, agent is more willing to wait for long-term \n",
        "rewards. The existence of improper policies can cause the standard algorithms for solving MDPs to fail with additive rewards- good reason for using discounted rewards. \n",
        "With using discounted utilities and infinite horizons, optimal policy is independent of the starting state. The utility of a state is the expected reward for the next transition \n",
        "plus the discounted utility of the next state, assuming choosing optimal action. \"\"\"\n",
        "\n",
        "chapter17_2 =  \"\"\"n possible states so n Bellman equations->start with arbitrary initial values for the utilities, update utility of each state from the utilities of its neighbors; repeat \n",
        "until equilibrium. This is guaranteed to reach an equilibrium, and final utility values are solutions to Bellman equations. Convergence of value iteration: repeated application of a contraction always \n",
        "reaches the fixed point in the limit. The Bellman update is a contraction by a factor of gamma on the space of utility vectors, so value iteration always converges to a unique solution \n",
        "of the Bellman equations whenever gamma < 1. We can get fast convergence if we make gamma small, but this gives the agent a short horizon and can miss long-term effects of actions. Policy iteration \n",
        "algorithm terminates when policy improvement step yields no change in the utilities. For small state spaces, policy evaluation using exact solution methods is most efficient. MDPs can be solved in time polynomial \n",
        "to the number of states and actions and the number of bits required to specify the model. Value iteration and policy iteration are offline algorithms, generate an optimal solution for the \n",
        "problem which can be executed by simple agent. EXPECTIMAX algorithm builds tree of alternating max and chance nodes, evaluation function applied to nonterminal leaves of tree, decision extracted \n",
        "from search tree by backing up utility values from leaves, taking average at chance nodes, and taking max at decision nodes\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"U(s) assigns a single number to express desirability of a state\",\n",
        "\"expected utility\": \"of an action EU(a) is average utility value of outcomes weighted by outcome probability\",\n",
        "\"maximum expected utility (MEU)\" : \"rational agent should choose action that maximizes agent's expected utility\",\n",
        "\"performance measure\": \"gives a score for a history - a sequence of states\",\n",
        "\"lottery\": \"a lottery L with possible outcomes S1,..,Sn that occurs with probabilities P1,...,pn written L=[p1,S1;p2,S2,...,pn,Sn]\",\n",
        "\"expected utility of lottery\": \"sum of probability of each outcome times the utility of that outcome\",\n",
        "\"value function\": \"or ordinal utility function; agent only needs preference ranking on states, numbers don't matter\",\n",
        "\"preference elicitation\": \"presenting choices to the human and using the observed preferences to pin down underlying utility function\",\n",
        "\"normalized utilities\": \"use scale with worst possible catastrophe at U(S) = 0 and best possible prize at at U(S) = 1\",\n",
        "\"value of a statistical life\": \"used by agencies to determine the costs and benefits of regulations and interventions\",\n",
        "\"micromort\": \"one in a million chance of death\",\n",
        "\"QALY\": \"quality-adjusted life year (shorter life expectancy to avoid disability)\",\n",
        "\"risk-averse\": \"prefer a sure thing with a payoff that is less than the expected monetary value of a gamble\",\n",
        "\"certainty equivalent\": \"the value an agent will accept in lieu of a lottery\",\n",
        "\"insurance premium\": \"difference between the EMV of a lottery and its certainty equivalent\",\n",
        "\"unbiased\": \"expected value of the error between estimate of expected utility and true utility is zero\",\n",
        "\"order statistic\": \"the distribution of any particular ranked element of a sample\",\n",
        "\"optimizer's curse\": \"tendency for the estimated expected utility of the best choice to be too high\",\n",
        "\"normative theory\": \"describes how a rational agent should act\",\n",
        "\"descriptive theory\": \"describes how actual agents really do act\",\n",
        "\"certainty effect\": \"people are strongly attracted to gains that are certain\",\n",
        "\"ambiguity aversion\": \"most people elect the known probability rather than the unknown unknowns\",\n",
        "\"framing effect\": \"exact wording of a decision problem can have a big impact on agent's choice\",\n",
        "\"anchoring effect\": \"people feel more comfortable making relative utility judgments rather than absolute ones\",\n",
        "\"evolutionary psychology\": \"our brain's decision-making mechanisms did not evolve to solve word problems with decimal numbers\",\n",
        "\"sequential decision problems\": \"agent's utility depends on a sequence of decisions\",\n",
        "\"transition model\": \"describes the outcome of each action in each state\",\n",
        "\"Markovian\": \"the probability of reaching s' from s depends only on s and not on earlier states history\",\n",
        "\"environment history\": \"the sequence of states and actions\",\n",
        "\"markov decision process (MDP)\": \"sequential decision problem, fully observable, stochastic environment, Markovian transition model, additive rewards\",\n",
        "\"dynamic programming\": \"method for solving MDP; recursively breaking into smaller pieces and remembering optimal solutions to those\",\n",
        "\"policy\": \"a solution that specifies what agent should do for any state that agent might reach; pi(s) is action recommend for state s\",\n",
        "\"optimal policy\": \"policy that yields the highest expected utility, pi*\",\n",
        "\"finite horizon\": \"vs infinite horizon; there is a fixed time N after which nothing matters/game is over; depends on how much time is left\",\n",
        "\"nonstationary\": \"policy that depends on the time\",\n",
        "\"stationary\": \"optimal action depends only on the current state, since no fixed time limit\",\n",
        "\"discount factor\": \"describes preference of an agent for current rewards over future rewards\",\n",
        "\"additive rewards\": \"when discount factor is exactly one\",\n",
        "\"proper policy\": \"a policy that is guaranteed to reach a terminal state\",\n",
        "\"average reward\": \"obtained per time step; can be used to compare infinite sequences\",\n",
        "\"action-utility function\": \"Q-function; Q(s,a) is the expected utility of taking a given action in a given state\",\n",
        "\"shaping theorem\": \"R'(s,a,s') = R(s,a,s') + gamma*function(s')-function(s) leaves optimal policy unchanged\",\n",
        "\"dynamic decision networks (DDNs)\": \"represent MDPs with decision, reward, and utility nodes\",\n",
        "\"bellman update\": \"iteration step that is applied simultaneously to all the states at each iteration\",\n",
        "\"contraction\": \"function that when applied to two different inputs produces two output values closer together by constant factor\",\n",
        "\"policy iteration algorithm\": \"alternates between policy evaluation and policy improvement\",\n",
        "\"policy evaluation\": \"given a policy pi_i, calculate U_i = U^pi_i, the utility of each state if pi_i is executed\",\n",
        "\"policy improvement\": \"calculate a new MEU policy pi_i+1 using one-step look-ahead based on U_i\",\n",
        "\"modified policy iteration\": \"for large state spaces, perform simplified value iteration steps (fixed policy) to utility approximation\",\n",
        "\"asynchronous policy iteration\": \"on each iteration, pick a subset of states and apply improvement or iteration to subset\",\n",
        "\"real-time dynamic programming (RTDP)\": \"explored states are sub-MDP of original MDP; can solved using algorithms to yield curret state decision\"\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "62a2886e-49e0-4adb-a789-c47d3aa53150"
      },
      "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": 26,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nMEU principle formalizes that intelligent agent should do right thing, but does not operationalize \nthat advice. If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score, averaged over all possible environments. Performance measure applied \nretrospectively after an agent completes a sequence of actions VS utility function applies to the very next state used to guide actions \nstep by step.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n(1) ORDERABILITY: given any two lotteries, a rational agent must either prefer one or else rate equally preferable\n(2) TRANSITIVITY: given any three lotteries, if agent prefers A to B and B to C, must prefer A to C (3) CONTINUITY: if B is between A and C \nin preference, there is a probability p for which agent is indifferent between getting B for sure and the lottery that yields A with probability p\nand C with probability 1-p (4) SUBSTITUTABILITY: if agent indifferent between A and B, also indifferent between two more complex lotteries that are \nsame except B substituted for A in one of them (5) MONOTONICITY: if agent prefers A to B, agent must prefer lottery that has a higher probability for A\nand vice versa (6) DECOMPOSABILITY: compound lotteries can be reduced to simpler ones using probability laws. Existence of utility function: if agent's preferences\nobey axioms of utility, exists function U such that U(A) > U(B) iff A > B, and U(A) = U(B) if indifferent. \n\n## AIMA Chapter 16.3 Utility Functions\nAgents exhibit a monotonic preference for more money. Most people have a utility function that is concave for positive wealth. \n\n## AIMA Chapter 17.1 Sequential Decision Problems\nThe utility of an environment history is the sum of the rewards received. MDP consists of a set of states (with initial state), set of \nactions in each state, a transition model, and a reward function. The quality of a policy is measured by the expected utility of the possible environment histories generated \nby that policy. When discount factor is close to 0, rewards in the distant future are viewed as insignificant, and when close to 1, agent is more willing to wait for long-term \nrewards. The existence of improper policies can cause the standard algorithms for solving MDPs to fail with additive rewards- good reason for using discounted rewards. \nWith using discounted utilities and infinite horizons, optimal policy is independent of the starting state. The utility of a state is the expected reward for the next transition \nplus the discounted utility of the next state, assuming choosing optimal action. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nn possible states so n Bellman equations->start with arbitrary initial values for the utilities, update utility of each state from the utilities of its neighbors; repeat \nuntil equilibrium. This is guaranteed to reach an equilibrium, and final utility values are solutions to Bellman equations. Convergence of value iteration: repeated application of a contraction always \nreaches the fixed point in the limit. The Bellman update is a contraction by a factor of gamma on the space of utility vectors, so value iteration always converges to a unique solution \nof the Bellman equations whenever gamma < 1. We can get fast convergence if we make gamma small, but this gives the agent a short horizon and can miss long-term effects of actions. Policy iteration \nalgorithm terminates when policy improvement step yields no change in the utilities. For small state spaces, policy evaluation using exact solution methods is most efficient. MDPs can be solved in time polynomial \nto the number of states and actions and the number of bits required to specify the model. Value iteration and policy iteration are offline algorithms, generate an optimal solution for the \nproblem which can be executed by simple agent. EXPECTIMAX algorithm builds tree of alternating max and chance nodes, evaluation function applied to nonterminal leaves of tree, decision extracted \nfrom search tree by backing up utility values from leaves, taking average at chance nodes, and taking max at decision nodes\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - U(s) assigns a single number to express desirability of a state\n* **Expected utility** - of an action EU(a) is average utility value of outcomes weighted by outcome probability\n* **Maximum expected utility (meu)** - rational agent should choose action that maximizes agent's expected utility\n* **Performance measure** - gives a score for a history - a sequence of states\n* **Lottery** - a lottery L with possible outcomes S1,..,Sn that occurs with probabilities P1,...,pn written L=[p1,S1;p2,S2,...,pn,Sn]\n* **Expected utility of lottery** - sum of probability of each outcome times the utility of that outcome\n* **Value function** - or ordinal utility function; agent only needs preference ranking on states, numbers don't matter\n* **Preference elicitation** - presenting choices to the human and using the observed preferences to pin down underlying utility function\n* **Normalized utilities** - use scale with worst possible catastrophe at U(S) = 0 and best possible prize at at U(S) = 1\n* **Value of a statistical life** - used by agencies to determine the costs and benefits of regulations and interventions\n* **Micromort** - one in a million chance of death\n* **Qaly** - quality-adjusted life year (shorter life expectancy to avoid disability)\n* **Risk-averse** - prefer a sure thing with a payoff that is less than the expected monetary value of a gamble\n* **Certainty equivalent** - the value an agent will accept in lieu of a lottery\n* **Insurance premium** - difference between the EMV of a lottery and its certainty equivalent\n* **Unbiased** - expected value of the error between estimate of expected utility and true utility is zero\n* **Order statistic** - the distribution of any particular ranked element of a sample\n* **Optimizer's curse** - tendency for the estimated expected utility of the best choice to be too high\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - most people elect the known probability rather than the unknown unknowns\n* **Framing effect** - exact wording of a decision problem can have a big impact on agent's choice\n* **Anchoring effect** - people feel more comfortable making relative utility judgments rather than absolute ones\n* **Evolutionary psychology** - our brain's decision-making mechanisms did not evolve to solve word problems with decimal numbers\n* **Sequential decision problems** - agent's utility depends on a sequence of decisions\n* **Transition model** - describes the outcome of each action in each state\n* **Markovian** - the probability of reaching s' from s depends only on s and not on earlier states history\n* **Environment history** - the sequence of states and actions\n* **Markov decision process (mdp)** - sequential decision problem, fully observable, stochastic environment, Markovian transition model, additive rewards\n* **Dynamic programming** - method for solving MDP; recursively breaking into smaller pieces and remembering optimal solutions to those\n* **Policy** - a solution that specifies what agent should do for any state that agent might reach; pi(s) is action recommend for state s\n* **Optimal policy** - policy that yields the highest expected utility, pi*\n* **Finite horizon** - vs infinite horizon; there is a fixed time N after which nothing matters/game is over; depends on how much time is left\n* **Nonstationary** - policy that depends on the time\n* **Stationary** - optimal action depends only on the current state, since no fixed time limit\n* **Discount factor** - describes preference of an agent for current rewards over future rewards\n* **Additive rewards** - when discount factor is exactly one\n* **Proper policy** - a policy that is guaranteed to reach a terminal state\n* **Average reward** - obtained per time step; can be used to compare infinite sequences\n* **Action-utility function** - Q-function; Q(s,a) is the expected utility of taking a given action in a given state\n* **Shaping theorem** - R'(s,a,s') = R(s,a,s') + gamma*function(s')-function(s) leaves optimal policy unchanged\n* **Dynamic decision networks (ddns)** - represent MDPs with decision, reward, and utility nodes\n* **Bellman update** - iteration step that is applied simultaneously to all the states at each iteration\n* **Contraction** - function that when applied to two different inputs produces two output values closer together by constant factor\n* **Policy iteration algorithm** - alternates between policy evaluation and policy improvement\n* **Policy evaluation** - given a policy pi_i, calculate U_i = U^pi_i, the utility of each state if pi_i is executed\n* **Policy improvement** - calculate a new MEU policy pi_i+1 using one-step look-ahead based on U_i\n* **Modified policy iteration** - for large state spaces, perform simplified value iteration steps (fixed policy) to utility approximation\n* **Asynchronous policy iteration** - on each iteration, pick a subset of states and apply improvement or iteration to subset\n* **Real-time dynamic programming (rtdp)** - explored states are sub-MDP of original MDP; can solved using algorithms to yield curret state decision\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 =  \"\"\"Exploitation of current best action to obtain rewards vs exploration of previously unknown states and actions to gain information, which \n",
        "can sometimes be converted into better policy/long-term rewards. Each arm M_i is a MRP, an MDP with one action, states S_i, transition model P_i(s'|s,a_i), reward \n",
        "R_i(s, a_i, s'). Arm defines distribution over sequences of rewards R_i,0, R_i,1, etc.. where each R_i,t is a random variable. Overall bandit problem is an MDP. One-Armed Bandit \n",
        "problem: first arm M yields arbitrary sequence R0, R1, R2,... and second arm yields M_lambda yields lambda, lambda, lambda..for some known fixed constant lambda. \n",
        "Gittins index provides a very simple optimal policy for any bandit problem: pull arm with highest Gittins index then update the Gittens indices. At the tipping point where optimal \n",
        "policy is indifferent between choosing arm M and choosing the fixed arm M_lambda, value of choosing M is same as value of choosing an infinite sequence of lambda-rewards. \n",
        "For Bernoulli bandit, state of each arm M_i defined by s_i and f_i, counts of successes and failures respectively. Transition probability predicts 1 with (s_i)/(s_i+f_i) and vice versa. \n",
        "No index function exists for selection problems. Optimal bandit algorithms explore much less than optimal selection algorithms, because bandit algorithm assumes that a failed trial costs \n",
        "real money. Globally optimal policy for a BSP may include actions that are locally suboptimal from POV of constituent MDP in which they are taken. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"Reinforcement learning differs from MDP because agent is not given the MDP as a problem to solve; agent is in the MDP. It may not know the transition model or reward function and \n",
        "must act in order to learn more. Action-utility learning and policy search are types of model-free reinforcement learning. \"\"\"\n",
        "\n",
        "chapter22_2 =  \"\"\"Can reduce reinforcement learning to standard supervised learning problem in which each example is (state, reward-to-go) pair. The utility of a state is determined by the reward and the \n",
        "expected utility of the successor states. Direct utility estimation learns nothing until the end of the trial; searches for U in a hypothesis space that is much larger than it needs to be, includes functions that \n",
        "violate the Bellman equations; converges very slowly. In ADP, passive learning agent plugs in learned transition model and observed rewards to calculate state utilities. Learning transition model is easy: for each \n",
        "training example, update transition model table, couting how often state s' is reached when executing a in s. In temporal difference learning, apply following update when transition occurs from state s to state s' via action \n",
        "pi(s): U_pi(s) = U_pi(s) + alpha*TD, where alpha is learning rate parameter. If turn alpha into function that decreases as the number of times a state has been visited increases, U_pi(s) will converge to correct value. TD does not \n",
        "learn quite as fast as ADP agent and shows higher variability, but much simpler and less computation per observation. We can generate more efficient versions of ADP by bounding number of adjustements made after each observed transition or can use \n",
        "a heuristic to rank the possible adjustements and carry out most significant ones. Using heuristics, approximate ADP algorithms can learn roughly as fast as full ADP and be more efficient. \"\"\"\n",
        "\n",
        "chapter22_3 =  \"\"\"Optimal action can lead to suboptimal results since the learned model is not the same as the true environment. Actions do more than provide rewards, they also provide information in the form of percepts in the resulting states. \n",
        "ADP agent using GLIE scheme can eventually learn the true transition model and operate under exploitation. Example of GLIE schemes: choose random action at time step t with probability 1/t else follow greedy policy. OR give weight to actions that \n",
        "agent has not tried very often and avoid action that are believed to be of low utility. Can use exploration function R+ if n < N_e and u otherwise, where R+ is optimistic estimate of the best possible reward obtainable in any state and N_e is fixed parameter. \n",
        "Agent will be able to try each state at least N_e times. As exploration proceeds, states and actions near start state might be tried a large number of times. If used U in RHS of equation, more pessimistic utility estimate, agent would become \n",
        "disinclined to explore further. Using U+ means that benefits of exploration are propagated back from the edges of unexplored regions, so that actions that lead toward unexplored regions are weighted more highly. By choosing a policy based solely on the estimated model, \n",
        "it is acting as if the model were correct which is not necessarily a good idea. Better idea is to choose a policy that works well for whole range of models that have reasonable chance of being the true model, even if policy happens to be suboptimal for the maximum-likelihood \n",
        "model. In Bayesian reinforcement learning, U_h^pi is the expected utility averaged overall start states, obtained by executing policy pi in model h. In robust control theory, defines an optimal robust policy as one that gives the best outcome in the worst case over H, where \n",
        "set H is the set of models that exceed some likelihood threshold on P(h|e). In Q-learning, knowing Q-function enables agent to act optimally by choosing (action to maximize Q(s,a) with no need of look-ahead. A TD Q-learning agent does not need a transition model either for learning \n",
        "or for action selection. Difference between SARSA and Q-learning: the latter backs up the Q-value from the best action in state s', while SARSA waits until an action is taken and backs up the Q-value for that action. Two algorithms are identical if agent is greedy and always takes \n",
        "action with the best Q-value. Q-learning more flexible than SARSA, since Q-learning agent can learn how to behave well under variety of exploration policies. SARSA appropriate if policy being partly controlled by other agents or programs, so better to learn Q-function for what will \n",
        "actually happen rather than if able to pick the best action. \"\"\"\n",
        "\n",
        "chapter22_4 =  \"\"\"Given a collection of trials, we obtain a set of sample values of U_theta(x,y) and we can find best fit in the sense of minimizing the squared error using standard linear regression. If u_j(s) is the observed total reward from state s onward in the jth trial, then \n",
        "then error is defined as half the squared difference of the predicted total and the actual total. The rate of change of the error with respect to each parameter moves the parameter in the direction of decreasing the error. Changing the parameters theta_i in response to an observed transition between \n",
        "two states also changes the values of U_theta for every other state-- function approximation allows reinforcement learner to generalize from its experiences. Experience replay: learning algorithm can retrain trajectories from entire learning process and replay those trajectories to ensure value function still accurate \n",
        "for state space it no longer vists. For partially observable environment, learning problem is much more difficult because the next percept is no longer a label for the state prediction problem. Need to go beyond linear function approximators (1) may be no good linear function that comes close to approximating the \n",
        "utility function of Q-function (2) may not be able to invent the necessary features, esp in new domains -> explore more complex, nonlinear function approximators. With deep RL, often difficult to get good performance and trained system may behave unpredictably if environment differs even a little from training data. \n",
        "In reward shaping, pseudorewards can speed up learnign enormously but risky because agent will learn to maximize pseudorewards rather than true rewards. In HRL, learning process converts the partial agent program into a complete program by learning how each choice should be made. Each choice in partial program invokes \n",
        "subroutine that may itself make further choices all the way down to primitive actions that can be executed directly. Partial program provides general know-how-overall scaffolding and structural organization for complex behaviors, and the learning process works out all the details. In HRL, the overall utility decomposes into \n",
        "several terms, each of which depends on only a few variables-- learning occurs much more quickly than if we try to learn a single utility function that depends on all the variables. \"\"\"\n",
        "\n",
        "chapter22_5 =  \"\"\"Interested in parameterized representations of pi that have far fewer parameters than thee are states in the state space. In Q-learning, finds a value of theta such that Q_theta is close to Q, the optimal Q-function. Whereas in policy search, it finds a value of theta that results in good performance--> resulting \n",
        "values may differ. Policy is a discontinuous function of the parameters when the actions are discrete-there will be values of theta such that an infinitesimal change in theta causes the policy to switch from one action to another. With softmax function, parameter B > 0 modules softness of softmax; B large comapred to separation between \n",
        "Q-values, softmax approaches a hard max; if B close to 0, softmax approaches uniform random choice among actions; for all finite values of B, softmax provides differentiable function of theta, so policy is a differential function of theta. When environment/policy is nondeterministic, can try to run lots of trials, measuring sampel variance \n",
        "and using it to determine if enough trials have been run to get reliable indication of direction of improvement for p(theta). Correlated sampling removes measurement error due to inputs to policies that are received. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"n-armed bandit\" : \"has n levers, behind each is fixed but unknown probability distribution of winnings\",\n",
        "\"exploitation\": \"of the current best action to obtain rewards\",\n",
        "\"exploration\": \"of previously unknown states and actions to gain information; can be converted to better policy\",\n",
        "\"Markov reward process\": \"MDP with only one possible action\",\n",
        "\"one-armed bandit\": \"one arm M that produces rewards R_0, R_1, R_2,..and costs lambda for each pull\",\n",
        "\"stopping time\": \"if you pull the first arm T times @0, 1,...,T-1, stopping time is T\",\n",
        "\"Gittins index\": \"of an arm M; describes the maximum obtainable utility per unit of discounted time\",\n",
        "\"restart MDP\": \"could replace choice to get infinite sequence of lambda-rewards with choice to go back and restart M from initial\",\n",
        "\"Bernoulli bandit\": \"each arm M_i produces a reward of 0 or 1 with fixed but unknown probability mu_i.\" ,\n",
        "\"exploration bonus\": \"associated with arms only tried a few times VS arms with higher payoff probabilities which are preferred\",\n",
        "\"confidence interval\": \"range within which the value of arm can be estimated to lie with high confidence\",\n",
        "\"upper confidence bound/UCB heuristic\": \"policy that chooses arm with highest UCB value (current mean value + multiple of SD of value uncertainty\",\n",
        "\"Thompson sampling\": \"choose an arm randomly according to the probability that the arm is optimal, given samples so far\",\n",
        "\"selection problem\": \"task of choosing the best option under conditions that don't have to minimize test failures\",\n",
        "\"bandit superprocess\": \"BSP; each arm is a full MDP in its own right, rather than being a MRP with only one possible action\",\n",
        "\"opportunity cost\": \"how much utility is given up per time step by not devoting that time step to another arm\",\n",
        "\"dominating policy\": \"an optimal policy in a given arm is unaffected by the opportunity cost; converting arm into a MRP\",\n",
        "\"supervised learning\": \"an agent learns by passively observing example input/output pairs provided by a teacher\",\n",
        "\"reinforcement learning\": \"an agent interacts with the world and receives rewards/reinforcements that reflect how well it is doing\",\n",
        "\"sparse rewards\": \"in the vast majority of states, the agent is given no informative reward signal at all\",\n",
        "\"model-based reinforcement learning\": \"agent uses transition model of environment to help interpret the reward signals and making how to act decisions\",\n",
        "\"model-free reinforcement learning\": \"agent knows nor learns a transition model for environment; learns direct representation of how to behave\",\n",
        "\"action-utility learning\": \"Q-learning, where agent learns a Q-function Q(s,a) denoting sum of rewrds from state s onward if action a is taken\",\n",
        "\"policy search\": \"agent learns a policy pi(s) that maps from states to actions; a reflex agent\",\n",
        "\"passive reinforcement learning\": \"an agent's policy is fixed and task is to learn the utilities of states/or state-action pairs\",\n",
        "\"active reinforcement learning\": \"agent must also figure out what to do\",\n",
        "\"exploration\": \"agent must experience as much as possible of its environment in order to learn how to behave in it\",\n",
        "\"apprenticeship learning\": \"training a learning agent using demonstrations rather than reward signals\",\n",
        "\"passive learning agent\": \"trying to learn the utility function U_pi(s)- expected total discounted reward if policy on state s\",\n",
        "\"direct utility estimation\": \"utility of a state is defined as the expected total reward from that state onward/expected reward-to-go\",\n",
        "\"adaptive dynamic programming (ADP)\": \"takes advantage of constraints among utilities of states by learning transition model that connects them and solves corresponding MDP\",\n",
        "\"modified policy iteration\": \"use a simplified value iteration process to update the utility estimates after each change to learned model\",\n",
        "\"temporal-differene (TD)\": \"an error signal; intended to reduce the error; R(s,pi(s),s') + gamma*U_pi(s') - U_pi(s)\",\n",
        "\"prioritized sweeping\": \"heuristic that prefers to make adjustments to states whose likely successors have just undergone large adjustment to own utility estimates\",\n",
        "\"active learning agent\": \"gets to decide what actions to take; no fixed policy determines its behavior\",\n",
        "\"greedy agent\": \"greedily takes the action that it currently believes to be optimal at each step; sticks to policy; never learns utilities of other states\",\n",
        "\"GLIE\": \"greedy in the limit of infinite exploration; try each action in each state infinite times to avoid having finite probability that optimal action is missed\",\n",
        "\"irreversible\": \"no subsequent sequence of actions can restore the state to what it was before the irreversible action was taken\",\n",
        "\"absorbing state\": \"no actions have any effect and no rewards are received\",\n",
        "\"Bayesian reinforcement learning\": \"assumes prior probability P(h) over hypotheses h about what true model is\",\n",
        "\"posterior probability\": \"P(h|e) is obtained in the usual way by Bayes' rule given the observations to date\",\n",
        "\"exploration POMDP\": \"if agent continues learning in future, must consider effects of future observations on its beliefs about transition model\",\n",
        "\"robust control theory\": \"allows for a set of possible models H without assigning probabilities to them\",\n",
        "\"Q-learning\": \"method that avoids need for model by learning Q(s,a): expected total discounted reward if take action a in s and action optimally afterwards\",\n",
        "\"SARSA (state, action, reward, state, action\": \"updates the Q-value of the action a' that is actually taken\",\n",
        "\"off-policy\": \"What would this action be worth in this state, assuming I stop using whatever policy rn and start acting to policy that chooses best action\",\n",
        "\"on-policy\": \"What would this action be worth in this state, assuming I stick with my policy?\",\n",
        "\"evaluation function\": \"a compact measure of desirability for potentially vast state spaces; approximate utility function\",\n",
        "\"function approximation\": \"process of constructing a compact approximation of the true utility function or Q-function\",\n",
        "\"features\": \"can approximate utility function using weighted linear combination of features; U_theta(s)=theta_1*f_1(s) + theta_2*f_2(s) + ...\",\n",
        "\"catastrohic forgetting\": \"ex: car learned too well; learned entire central region of road is safe and forgotten that region closer to edge is dangerous\",\n",
        "\"experience replay\": \"ex: ensures car keeps reliving its youthful crashing behavior at regular intervals\",\n",
        "\"deep reinforcement learning system\": \"reinforcement learning system that uses a deep network as a function approximator\",\n",
        "\"credit assignment problem\": \"many primitive actions required to achieve nonzero reward- need to work out what agent did wrong\",\n",
        "\"reward shaping\": \"supplying agent with additional rewards (pseudorewards) for making progress\",\n",
        "\"hierarchical reinforcement learning (HRL)\": \"break up long action sequences into few smaller pieces, etc, until action sequences short enough to make learning easy\",\n",
        "\"partial program\": \"HRL agent begins with this outline of a hierarchical structure for its behavior\",\n",
        "\"choose\": \"operator in partial program that allows agent to choose any element of the specified set\",\n",
        "\"joint state space\": \"each state (s,m) is composed of a physical state s and a machine state m\",\n",
        "\"machine state\": \"defined by current internal state of agent program, PC for each subroutine, values of arguments, variables, etc\",\n",
        "\"choice state\": \"sigma(s, m) is one in which the program counter for m is at a choice point in the agent program\",\n",
        "\"additive decomposition\": \"hierarchical structure of behavior means can break up overall utility function in this manner\",\n",
        "\"policy search\": \"keep twiddling the policy as long as its performance improves, then stop\",\n",
        "\"stochastic policy\": \"pi_theta(s, a) which specifies the probability of selecting action a in state s\",\n",
        "\"policy value\": \"p(theta), the expected reward-to-go when pi_theta is executed\",\n",
        "\"policy gradient\": \"vector delta_theta(p(theta)) for optimization problem of p(theta)\",\n",
        "\"empirical gradient\": \"evaluating the change in policy value for small increments in each parameters; converges to local optimum in policy space\",\n",
        "\"correlated sampling\": \"use an environment simulator in which the random-number sequences can be repeated (ex: blackjack-each program plays same set of hands)\"\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "803c4917-97dd-4b91-8022-cf7b8d3b9c87"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nExploitation of current best action to obtain rewards vs exploration of previously unknown states and actions to gain information, which \ncan sometimes be converted into better policy/long-term rewards. Each arm M_i is a MRP, an MDP with one action, states S_i, transition model P_i(s'|s,a_i), reward \nR_i(s, a_i, s'). Arm defines distribution over sequences of rewards R_i,0, R_i,1, etc.. where each R_i,t is a random variable. Overall bandit problem is an MDP. One-Armed Bandit \nproblem: first arm M yields arbitrary sequence R0, R1, R2,... and second arm yields M_lambda yields lambda, lambda, lambda..for some known fixed constant lambda. \nGittins index provides a very simple optimal policy for any bandit problem: pull arm with highest Gittins index then update the Gittens indices. At the tipping point where optimal \npolicy is indifferent between choosing arm M and choosing the fixed arm M_lambda, value of choosing M is same as value of choosing an infinite sequence of lambda-rewards. \nFor Bernoulli bandit, state of each arm M_i defined by s_i and f_i, counts of successes and failures respectively. Transition probability predicts 1 with (s_i)/(s_i+f_i) and vice versa. \nNo index function exists for selection problems. Optimal bandit algorithms explore much less than optimal selection algorithms, because bandit algorithm assumes that a failed trial costs \nreal money. Globally optimal policy for a BSP may include actions that are locally suboptimal from POV of constituent MDP in which they are taken. \n\n## AIMA Chapter 22.1 Learning from Rewards\nReinforcement learning differs from MDP because agent is not given the MDP as a problem to solve; agent is in the MDP. It may not know the transition model or reward function and \nmust act in order to learn more. Action-utility learning and policy search are types of model-free reinforcement learning. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nCan reduce reinforcement learning to standard supervised learning problem in which each example is (state, reward-to-go) pair. The utility of a state is determined by the reward and the \nexpected utility of the successor states. Direct utility estimation learns nothing until the end of the trial; searches for U in a hypothesis space that is much larger than it needs to be, includes functions that \nviolate the Bellman equations; converges very slowly. In ADP, passive learning agent plugs in learned transition model and observed rewards to calculate state utilities. Learning transition model is easy: for each \ntraining example, update transition model table, couting how often state s' is reached when executing a in s. In temporal difference learning, apply following update when transition occurs from state s to state s' via action \npi(s): U_pi(s) = U_pi(s) + alpha*TD, where alpha is learning rate parameter. If turn alpha into function that decreases as the number of times a state has been visited increases, U_pi(s) will converge to correct value. TD does not \nlearn quite as fast as ADP agent and shows higher variability, but much simpler and less computation per observation. We can generate more efficient versions of ADP by bounding number of adjustements made after each observed transition or can use \na heuristic to rank the possible adjustements and carry out most significant ones. Using heuristics, approximate ADP algorithms can learn roughly as fast as full ADP and be more efficient. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nOptimal action can lead to suboptimal results since the learned model is not the same as the true environment. Actions do more than provide rewards, they also provide information in the form of percepts in the resulting states. \nADP agent using GLIE scheme can eventually learn the true transition model and operate under exploitation. Example of GLIE schemes: choose random action at time step t with probability 1/t else follow greedy policy. OR give weight to actions that \nagent has not tried very often and avoid action that are believed to be of low utility. Can use exploration function R+ if n < N_e and u otherwise, where R+ is optimistic estimate of the best possible reward obtainable in any state and N_e is fixed parameter. \nAgent will be able to try each state at least N_e times. As exploration proceeds, states and actions near start state might be tried a large number of times. If used U in RHS of equation, more pessimistic utility estimate, agent would become \ndisinclined to explore further. Using U+ means that benefits of exploration are propagated back from the edges of unexplored regions, so that actions that lead toward unexplored regions are weighted more highly. By choosing a policy based solely on the estimated model, \nit is acting as if the model were correct which is not necessarily a good idea. Better idea is to choose a policy that works well for whole range of models that have reasonable chance of being the true model, even if policy happens to be suboptimal for the maximum-likelihood \nmodel. In Bayesian reinforcement learning, U_h^pi is the expected utility averaged overall start states, obtained by executing policy pi in model h. In robust control theory, defines an optimal robust policy as one that gives the best outcome in the worst case over H, where \nset H is the set of models that exceed some likelihood threshold on P(h|e). In Q-learning, knowing Q-function enables agent to act optimally by choosing (action to maximize Q(s,a) with no need of look-ahead. A TD Q-learning agent does not need a transition model either for learning \nor for action selection. Difference between SARSA and Q-learning: the latter backs up the Q-value from the best action in state s', while SARSA waits until an action is taken and backs up the Q-value for that action. Two algorithms are identical if agent is greedy and always takes \naction with the best Q-value. Q-learning more flexible than SARSA, since Q-learning agent can learn how to behave well under variety of exploration policies. SARSA appropriate if policy being partly controlled by other agents or programs, so better to learn Q-function for what will \nactually happen rather than if able to pick the best action. \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nGiven a collection of trials, we obtain a set of sample values of U_theta(x,y) and we can find best fit in the sense of minimizing the squared error using standard linear regression. If u_j(s) is the observed total reward from state s onward in the jth trial, then \nthen error is defined as half the squared difference of the predicted total and the actual total. The rate of change of the error with respect to each parameter moves the parameter in the direction of decreasing the error. Changing the parameters theta_i in response to an observed transition between \ntwo states also changes the values of U_theta for every other state-- function approximation allows reinforcement learner to generalize from its experiences. Experience replay: learning algorithm can retrain trajectories from entire learning process and replay those trajectories to ensure value function still accurate \nfor state space it no longer vists. For partially observable environment, learning problem is much more difficult because the next percept is no longer a label for the state prediction problem. Need to go beyond linear function approximators (1) may be no good linear function that comes close to approximating the \nutility function of Q-function (2) may not be able to invent the necessary features, esp in new domains -> explore more complex, nonlinear function approximators. With deep RL, often difficult to get good performance and trained system may behave unpredictably if environment differs even a little from training data. \nIn reward shaping, pseudorewards can speed up learnign enormously but risky because agent will learn to maximize pseudorewards rather than true rewards. In HRL, learning process converts the partial agent program into a complete program by learning how each choice should be made. Each choice in partial program invokes \nsubroutine that may itself make further choices all the way down to primitive actions that can be executed directly. Partial program provides general know-how-overall scaffolding and structural organization for complex behaviors, and the learning process works out all the details. In HRL, the overall utility decomposes into \nseveral terms, each of which depends on only a few variables-- learning occurs much more quickly than if we try to learn a single utility function that depends on all the variables. \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **N-armed bandit** - has n levers, behind each is fixed but unknown probability distribution of winnings\n* **Exploitation** - of the current best action to obtain rewards\n* **Exploration** - agent must experience as much as possible of its environment in order to learn how to behave in it\n* **Markov reward process** - MDP with only one possible action\n* **One-armed bandit** - one arm M that produces rewards R_0, R_1, R_2,..and costs lambda for each pull\n* **Stopping time** - if you pull the first arm T times @0, 1,...,T-1, stopping time is T\n* **Gittins index** - of an arm M; describes the maximum obtainable utility per unit of discounted time\n* **Restart mdp** - could replace choice to get infinite sequence of lambda-rewards with choice to go back and restart M from initial\n* **Bernoulli bandit** - each arm M_i produces a reward of 0 or 1 with fixed but unknown probability mu_i.\n* **Exploration bonus** - associated with arms only tried a few times VS arms with higher payoff probabilities which are preferred\n* **Confidence interval** - range within which the value of arm can be estimated to lie with high confidence\n* **Upper confidence bound/ucb heuristic** - policy that chooses arm with highest UCB value (current mean value + multiple of SD of value uncertainty\n* **Thompson sampling** - choose an arm randomly according to the probability that the arm is optimal, given samples so far\n* **Selection problem** - task of choosing the best option under conditions that don't have to minimize test failures\n* **Bandit superprocess** - BSP; each arm is a full MDP in its own right, rather than being a MRP with only one possible action\n* **Opportunity cost** - how much utility is given up per time step by not devoting that time step to another arm\n* **Dominating policy** - an optimal policy in a given arm is unaffected by the opportunity cost; converting arm into a MRP\n* **Supervised learning** - an agent learns by passively observing example input/output pairs provided by a teacher\n* **Reinforcement learning** - an agent interacts with the world and receives rewards/reinforcements that reflect how well it is doing\n* **Sparse rewards** - in the vast majority of states, the agent is given no informative reward signal at all\n* **Model-based reinforcement learning** - agent uses transition model of environment to help interpret the reward signals and making how to act decisions\n* **Model-free reinforcement learning** - agent knows nor learns a transition model for environment; learns direct representation of how to behave\n* **Action-utility learning** - Q-learning, where agent learns a Q-function Q(s,a) denoting sum of rewrds from state s onward if action a is taken\n* **Policy search** - keep twiddling the policy as long as its performance improves, then stop\n* **Passive reinforcement learning** - an agent's policy is fixed and task is to learn the utilities of states/or state-action pairs\n* **Active reinforcement learning** - agent must also figure out what to do\n* **Apprenticeship learning** - training a learning agent using demonstrations rather than reward signals\n* **Passive learning agent** - trying to learn the utility function U_pi(s)- expected total discounted reward if policy on state s\n* **Direct utility estimation** - utility of a state is defined as the expected total reward from that state onward/expected reward-to-go\n* **Adaptive dynamic programming (adp)** - takes advantage of constraints among utilities of states by learning transition model that connects them and solves corresponding MDP\n* **Modified policy iteration** - use a simplified value iteration process to update the utility estimates after each change to learned model\n* **Temporal-differene (td)** - an error signal; intended to reduce the error; R(s,pi(s),s') + gamma*U_pi(s') - U_pi(s)\n* **Prioritized sweeping** - heuristic that prefers to make adjustments to states whose likely successors have just undergone large adjustment to own utility estimates\n* **Active learning agent** - gets to decide what actions to take; no fixed policy determines its behavior\n* **Greedy agent** - greedily takes the action that it currently believes to be optimal at each step; sticks to policy; never learns utilities of other states\n* **Glie** - greedy in the limit of infinite exploration; try each action in each state infinite times to avoid having finite probability that optimal action is missed\n* **Irreversible** - no subsequent sequence of actions can restore the state to what it was before the irreversible action was taken\n* **Absorbing state** - no actions have any effect and no rewards are received\n* **Bayesian reinforcement learning** - assumes prior probability P(h) over hypotheses h about what true model is\n* **Posterior probability** - P(h|e) is obtained in the usual way by Bayes' rule given the observations to date\n* **Exploration pomdp** - if agent continues learning in future, must consider effects of future observations on its beliefs about transition model\n* **Robust control theory** - allows for a set of possible models H without assigning probabilities to them\n* **Q-learning** - method that avoids need for model by learning Q(s,a): expected total discounted reward if take action a in s and action optimally afterwards\n* **Sarsa (state, action, reward, state, action** - updates the Q-value of the action a' that is actually taken\n* **Off-policy** - What would this action be worth in this state, assuming I stop using whatever policy rn and start acting to policy that chooses best action\n* **On-policy** - What would this action be worth in this state, assuming I stick with my policy?\n* **Evaluation function** - a compact measure of desirability for potentially vast state spaces; approximate utility function\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n* **Features** - can approximate utility function using weighted linear combination of features; U_theta(s)=theta_1*f_1(s) + theta_2*f_2(s) + ...\n* **Catastrohic forgetting** - ex: car learned too well; learned entire central region of road is safe and forgotten that region closer to edge is dangerous\n* **Experience replay** - ex: ensures car keeps reliving its youthful crashing behavior at regular intervals\n* **Deep reinforcement learning system** - reinforcement learning system that uses a deep network as a function approximator\n* **Credit assignment problem** - many primitive actions required to achieve nonzero reward- need to work out what agent did wrong\n* **Reward shaping** - supplying agent with additional rewards (pseudorewards) for making progress\n* **Hierarchical reinforcement learning (hrl)** - break up long action sequences into few smaller pieces, etc, until action sequences short enough to make learning easy\n* **Partial program** - HRL agent begins with this outline of a hierarchical structure for its behavior\n* **Choose** - operator in partial program that allows agent to choose any element of the specified set\n* **Joint state space** - each state (s,m) is composed of a physical state s and a machine state m\n* **Machine state** - defined by current internal state of agent program, PC for each subroutine, values of arguments, variables, etc\n* **Choice state** - sigma(s, m) is one in which the program counter for m is at a choice point in the agent program\n* **Additive decomposition** - hierarchical structure of behavior means can break up overall utility function in this manner\n* **Stochastic policy** - pi_theta(s, a) which specifies the probability of selecting action a in state s\n* **Policy value** - p(theta), the expected reward-to-go when pi_theta is executed\n* **Policy gradient** - vector delta_theta(p(theta)) for optimization problem of p(theta)\n* **Empirical gradient** - evaluating the change in policy value for small increments in each parameters; converges to local optimum in policy space\n* **Correlated sampling** - use an environment simulator in which the random-number sequences can be repeated (ex: blackjack-each program plays same set of hands)\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 = \"\"\"The rational decision depends on both the relative importance of various goals and the likelihood that, and degree to \n",
        "which, they will be achieved. The theory of probability provides a way of summarizing the uncertainty that comes from our laziness and ignorance. \n",
        "Probability statements are made with respect to a knowledge state, not with respect to the real world. Utility theory: every state, or state sequence, \n",
        "has a degree of usefulness, or utility, to an agent and that the agent will prefer states with higher utility. \"\"\"\n",
        "\n",
        "chapter12_2 = \"\"\"Conditional probability: P(A|B) = P(A and B)/P(B). A possible world is defined to be an assignment of values to all of the random variables \n",
        "under consideration.\"\"\"\n",
        "\n",
        "chapter12_3 = \"\"\"General inference procedure: P(X|e) = alpha*P(X,e) = alpha*sum for each y[P(X, e, y)], where e is the observed values for the evidence \n",
        "variables, y is the values of the unobserved variables\"\"\"\n",
        "\n",
        "chapter12_4 = \"\"\"If the complete set of variables can be divided into independent subsets, then the full joint distribution can be factored into separate joint \n",
        "distributions on those subsets.\"\"\"\n",
        "\n",
        "chapter12_5 = \"\"\"More general version of Bayes' rule conditionalized on background evidence e: P(Y|X,e) = (P(X|Y,e) * P(Y|e))/P(X|e). General form of Bayes' rule with \n",
        "normalization is P(Y,X) = alpha*P(X|Y)P(Y). Diagnostic knowledge is often more fragile than causal knowledge. Conditional independence assertions can allow probabilistic systems\n",
        "to scale up; they are much more commonly available than absolute independence assertions. \"\"\"\n",
        "\n",
        "chapter12_6 = \"\"\"For each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause, then \n",
        "nromalize the result. Runtime of this calculation is linear in number of observed effects- does not depend on number of unobserved effects. For text classification, to categorize \n",
        "a new document, check which key words appear in the document and then apply equation to obtain posterior probability distribution over categories. Violate of independence in naive \n",
        "Bayes model means that final posterior probabilities will be much closer to 1/0 than it should be; model is overconfident in its predictions. \"\"\"\n",
        "\n",
        "chapter12_7 = \"\"\"\"\"\"\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 = \"\"\"General equation for the n-gram approximation to the conditional probability of the next word in a sequence is P(w_n|w_1:n-1) = P(w_n|w_n-N+1:n-1). \n",
        "Always represent and compute language model probabilities in log format as log probabilities: p1*p2*p3*p4 = exp(log(p1) + log(p2) + log(p3) + log(p4))\"\"\"\n",
        "\n",
        "SLP_chapter3_2 = \"\"\"Fit the test set means whichever model assigns a higher probability to the test set (more accurately predicts the test set) is a better model->tighter fit to the test data, better \n",
        "predicts the details of the test data. Minimizing perplexity is equivalent to maximizing the test set probability according to the lanugage model. The more information the n-gram gives us about the word\n",
        "sequence, the lower the perplexity. An intrinsic improvement in perplexity does not guarantee an extrinsic improvement in the performance of a language processing task. \"\"\"\n",
        "\n",
        "SLP_chapter3_3 = \"\"\"\"\"\"\n",
        "\n",
        "SLP_chapter3_4 = \"\"\"Probabilities often encode specific facts about a given training corpus. N-grams do a better and better job of modeling the training corpus as we increase the value of N. The longer the \n",
        "context on which we train the model, the more coherent the sentences. When building n-gram models, use a training corpus that has a similar genre to whatever task we are trying to accomplish. Important to get training \n",
        "data in the appropriate dialect or variety. Zeroes means we are underestimating the probability of all sorts of words that might occur. Also, if the probability of any word in the test set is 0, the entire probability of the \n",
        "test set is 0. Thus, cannot compute perplexity. Can deal with unknown words by (1) choose vocabulary that is fixed (2) convert in training set any OOV word to <UNK> in text normalization step (3) estimate probabilities for <UNK> \n",
        "from its counts just like any other regular word in the training set OR create a vocabulary and replace words in the training data by <UNK> based on their frequency (ex: replace by <UNK> all words that occur fewer than n times in \n",
        "the training set. or select a vocabulary size V in adfance and choose top V words by frequency and replace rest by <UNK>). Overall, perplexities should only be compared across language models with the same vocabularies. \"\"\"\n",
        "\n",
        "SLP_chapter3_5 = \"\"\"P_laplace(w_i) = (c_i+1)/(N + V). P_add-k(w_n|w_n-1) = (C(w_n-1w_n)+k)/(C(w_n-1)+kV). Lambda values for interpolation are learned from a held-out corups- an additional training corpus that we use to set hyperparameters->fix \n",
        "the n-gram probabilities and then search for the lambda values that give us the highest probability of the held out set. In order for backoff model to give correct probability distribution, we have to discount the higher-order n-grams to save some \n",
        "probability mass for the lower-order n-grams. \"\"\"\n",
        "\n",
        "SLP_chapter3_7 = \"\"\"Efficiency considerations are important when building language models that use such large sets of n-grams-> usually represent a word in memory as 64-bit hash number, with the words themselves stored on disk. \n",
        "Can also do pruning, and store n-grams with counts greater than some threshold or use entropy to prune less-important n-grams or Bloom Filters. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"belief state\" : \"representation of the set of all possible world states that agent might be in\",\n",
        "\"laziness\": \"too much work to list the complete set of antecedents or consequents needed to ensure exceptionless rule/too hard\",\n",
        "\"theoretical ignorance\": \"medical science has no complete theory for the domain\",\n",
        "\"practical ignorance\": \"even if know all rules, might be uncertain about patient because not all test can/have been run\",\n",
        "\"probability thoery\": \"main tool for dealing with degrees of beliefs\",\n",
        "\"ontological commitments\": \"the world is composed of facts that do or do not hold in any particular case\",\n",
        "\"epistemological commitments\": \"a logical agent believes each sentence to be true or false or has no opinion/probabilistic agent has numerical degree of belief 0-1\",\n",
        "\"outcome\": \"a completely specified state\",\n",
        "\"utility theory\": \"used to represent preferences and reason quantitatively with them\",\n",
        "\"decision theory\": \"preferences, as expressed by utilities, are combined with probabilities in general theory of rational decisions\",\n",
        "\"maximum expected utility (MEU)\": \"an agent is rational iff it chooses the action that yields the highest expected utility, averaged over all possible action outcomes\",\n",
        "\"sample space\": \"the set of all possible worlds; mutually exclusive and exhaustive\",\n",
        "\"probability model\": \"associates a numerical probability P(w) with each possible world\",\n",
        "\"proposition\": \"a set of worlds, synonymous with events; its probability is the sum of probabilities of worlds it holds\",\n",
        "\"unconditional/prior probabilities\": \"degrees of belief in propositions in the absence of any other information\",\n",
        "\"conditional/posterior probabilities\": \"the probabilitiy given some evidence that has already been revealed\",\n",
        "\"product rule\": \"P(A and B) = P(A|B) * P(B)\",\n",
        "\"factored representation\": \"a possible world is represented by a set of variable/value pairs\",\n",
        "\"random variables\": \"variables in probability theory; begin with an uppercase letter; maps from domain of possible worlds to some range\",\n",
        "\"Bernoulli\": \"distribution in which the range is the set {0,1}\",\n",
        "\"probability distribution\": \"an assignment of a probability for each possible value of the random variable\",\n",
        "\"categorical distribution\": \"probability distribution with a finite, discrete range\",\n",
        "\"probability density function\": \"define the probability that a random variable takes on some value x as a parameterized function of x\",\n",
        "\"joint probability distribution\": \"distribution denoting probabilities of all combinations of multiple variables\",\n",
        "\"full joint probability distribution\": \"joint distribution for all of the random variables\",\n",
        "\"inclusion-exclusion principle\": \"P(a OR b) = P(a) + P(b) = P(a AND b)\",\n",
        "\"probabilistic inference\": \"the computation of posterior probabilities for query propositions given observed evidence\",\n",
        "\"marginal probabilitiy\": \"extracting the distribution over some subset of variables or a single variable\",\n",
        "\"marginalization\": \"summing out; sum up the probabilities for each possible value of the other variables, theyreby taking them out of the equation\",\n",
        "\"independence\": \"P(a|b) = P(a) or P(b|a) = P(b) or P(a and b) = P(a)P(b)\",\n",
        "\"Bayes' rule\": \"P(b|a) = (P(a|b)*P(b))/P(a) OR P(cause|effect) = (P(effect|cause)*P(cause))/P(effect)\",\n",
        "\"causal direction\": \"P(effect|cause)\",\n",
        "\"diagnostic direction\": \"P(cause|effect)\",\n",
        "\"conditional independence\": \"P(X,Y|Z) = P(X|Z)P(Y|Z) => P(X|Y,Z) = P(X|Z) and P(Y|X,Z) = P(Y,Z)\",\n",
        "\"separation\": \"decomposition of large probabilistic domains into weakly connected subsets through conditional independence\",\n",
        "\"naive Bayes model/Bayesian classifier\": \"P(Causes, Effect_1, ..., Effect_n) = P(Cause)product for each i[P(Effect_i|Cause)]\",\n",
        "\"text classification\": \"given a text, decide which of a predefined set of classes or categories it belongs to\",\n",
        "\"chain rule of probability\": \"P(w1:n) = P(w1)*P(w2|w1)*P(w3|w1:2)...P(wn|w1:n-1)\",\n",
        "\"bigram model\": \"approximates the probability of a word given all the previous words by only using conditional probability of preceding word\",\n",
        "\"Markov assumption\": \"probability of a word depends only the previous word\",\n",
        "\"n-gram\": \"looks n-1 words into the past\",\n",
        "\"maximum likelihood estimation (MLE)\": \"way to estimate bigram or n-gram probabilities\",\n",
        "\"relative frequency\": \"dividing the observed frequency of a particular sequence by the observed frequency of a prefix\",\n",
        "\"extrinsic evaluation\": \"evaluate the performance of a language model by embedding it into an application and measure how much application improves\",\n",
        "\"intrinsic evaluation\": \"metric that measures the quality of a model independent of any application\",\n",
        "\"training set/training corpus\": \"the corpus an n-gram model is trained on\",\n",
        "\"test set/test corpus\": \"an unseen data set on which we can measure the quality of an n-gram model performance on\",\n",
        "\"held out\": \"test sets that is not in training set because we hold them out from the training data\",\n",
        "\"training on the test set\": \"introduces a bias that makes probabilities all look too high, causes inaccuracies in perplexity\",\n",
        "\"perplexity\": \"of a language model on a test set is inverse probability of the test set normalized by number of words\",\n",
        "\"weighted average branching factor\": \"the number of possible next words that can follow any word\",\n",
        "\"sampling\": \"choose random points from a distribution according to their likelihood/generate sentences, choosing each according to likelihood defined by language model\",\n",
        "\"sparsity\": \"because any corpus is limited, some perfectly acceptable English word sequences are bound to missing from it\",\n",
        "\"zeros\": \"things that don't ever occur in the training set but do occur in the test set\",\n",
        "\"closed vocabulary\": \"system in which the test set can only contain words from the lexicon, no unknown/out of vocabulary (OOV) words\",\n",
        "\"OOV rate\": \"the percentage of OOV words that appear in the test set\",\n",
        "\"open vocabulary\": \"we model the potential unknown words in the test set by adding a pseudo-word called <UNK>\",\n",
        "\"smoothing/discounting\": \"to keep language model from assigning zero probability to words in unseen contexts, shave off probability mass from more frequent events and given to these\",\n",
        "\"laplace smoothing\": \"add one to all the n-gram counts before we normalize them into probabilities/add-one smoothing\",\n",
        "\"adjusted count\": \"c_i* = ((c_i+1)*N)/(N+V)\",\n",
        "\"discounting\": \"lowering some non-zero counts in order to get the probability mass that will be assigned to the zero counts\",\n",
        "\"discount\": \"d_c = c*/c -> ratio of the discounted counts to the original counts\",\n",
        "\"add-k smoothing\": \"instead of adding 1 to each count, add fractional count k- moves less of the probability mass from the seen to the unseen events\",\n",
        "\"less context\": \"sometimes a good thing; helps to generalize more for contexts that the model hasn't learned much about\",\n",
        "\"backoff\": \"we use trigram if evidence is sufficient, else use bigram, else use unigram->backoff to lower-order n-gram if zero evidence for higher-order n-gram\",\n",
        "\"interpolation\": \"mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram, and unigram counts\",\n",
        "\"EM algorithm\": \"an iterative learning algorithm that converges on locally optimal lambdas\",\n",
        "\"Katz backoff\": \"rely on a discounted probability P* if we've seen this n-gram before, else recursively back off to Katz probability for shorter-history N-1-gram; combined with Good-Turing\",\n",
        "\"stupid backoff\": \"tries to make the language model a true probability distribution-no discounting of the higher-order probabilities\"\n",
        "}"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "45e24f80-dee3-4846-bc84-74ea3a9c5bf6"
      },
      "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": 30,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nThe rational decision depends on both the relative importance of various goals and the likelihood that, and degree to \nwhich, they will be achieved. The theory of probability provides a way of summarizing the uncertainty that comes from our laziness and ignorance. \nProbability statements are made with respect to a knowledge state, not with respect to the real world. Utility theory: every state, or state sequence, \nhas a degree of usefulness, or utility, to an agent and that the agent will prefer states with higher utility. \n\n## AIMA Chapter 12.2 Basic Probability Notation\nConditional probability: P(A|B) = P(A and B)/P(B). A possible world is defined to be an assignment of values to all of the random variables \nunder consideration.\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nGeneral inference procedure: P(X|e) = alpha*P(X,e) = alpha*sum for each y[P(X, e, y)], where e is the observed values for the evidence \nvariables, y is the values of the unobserved variables\n\n## AIMA Chapter 12.4 Independence\nIf the complete set of variables can be divided into independent subsets, then the full joint distribution can be factored into separate joint \ndistributions on those subsets.\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\nMore general version of Bayes' rule conditionalized on background evidence e: P(Y|X,e) = (P(X|Y,e) * P(Y|e))/P(X|e). General form of Bayes' rule with \nnormalization is P(Y,X) = alpha*P(X|Y)P(Y). Diagnostic knowledge is often more fragile than causal knowledge. Conditional independence assertions can allow probabilistic systems\nto scale up; they are much more commonly available than absolute independence assertions. \n\n## AIMA Chapter 12.6 Naive Bayes Models\nFor each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause, then \nnromalize the result. Runtime of this calculation is linear in number of observed effects- does not depend on number of unobserved effects. For text classification, to categorize \na new document, check which key words appear in the document and then apply equation to obtain posterior probability distribution over categories. Violate of independence in naive \nBayes model means that final posterior probabilities will be much closer to 1/0 than it should be; model is overconfident in its predictions. \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\nGeneral equation for the n-gram approximation to the conditional probability of the next word in a sequence is P(w_n|w_1:n-1) = P(w_n|w_n-N+1:n-1). \nAlways represent and compute language model probabilities in log format as log probabilities: p1*p2*p3*p4 = exp(log(p1) + log(p2) + log(p3) + log(p4))\n\n## SLP Chapter 3.2 Evaluating Language Models\nFit the test set means whichever model assigns a higher probability to the test set (more accurately predicts the test set) is a better model->tighter fit to the test data, better \npredicts the details of the test data. Minimizing perplexity is equivalent to maximizing the test set probability according to the lanugage model. The more information the n-gram gives us about the word\nsequence, the lower the perplexity. An intrinsic improvement in perplexity does not guarantee an extrinsic improvement in the performance of a language processing task. \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n\n## SLP Chapter 3.4 Generalization and Zeros\nProbabilities often encode specific facts about a given training corpus. N-grams do a better and better job of modeling the training corpus as we increase the value of N. The longer the \ncontext on which we train the model, the more coherent the sentences. When building n-gram models, use a training corpus that has a similar genre to whatever task we are trying to accomplish. Important to get training \ndata in the appropriate dialect or variety. Zeroes means we are underestimating the probability of all sorts of words that might occur. Also, if the probability of any word in the test set is 0, the entire probability of the \ntest set is 0. Thus, cannot compute perplexity. Can deal with unknown words by (1) choose vocabulary that is fixed (2) convert in training set any OOV word to <UNK> in text normalization step (3) estimate probabilities for <UNK> \nfrom its counts just like any other regular word in the training set OR create a vocabulary and replace words in the training data by <UNK> based on their frequency (ex: replace by <UNK> all words that occur fewer than n times in \nthe training set. or select a vocabulary size V in adfance and choose top V words by frequency and replace rest by <UNK>). Overall, perplexities should only be compared across language models with the same vocabularies. \n\n## SLP Chapter 3.5 Smoothing\nP_laplace(w_i) = (c_i+1)/(N + V). P_add-k(w_n|w_n-1) = (C(w_n-1w_n)+k)/(C(w_n-1)+kV). Lambda values for interpolation are learned from a held-out corups- an additional training corpus that we use to set hyperparameters->fix \nthe n-gram probabilities and then search for the lambda values that give us the highest probability of the held out set. In order for backoff model to give correct probability distribution, we have to discount the higher-order n-grams to save some \nprobability mass for the lower-order n-grams. \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nEfficiency considerations are important when building language models that use such large sets of n-grams-> usually represent a word in memory as 64-bit hash number, with the words themselves stored on disk. \nCan also do pruning, and store n-grams with counts greater than some threshold or use entropy to prune less-important n-grams or Bloom Filters. \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - representation of the set of all possible world states that agent might be in\n* **Laziness** - too much work to list the complete set of antecedents or consequents needed to ensure exceptionless rule/too hard\n* **Theoretical ignorance** - medical science has no complete theory for the domain\n* **Practical ignorance** - even if know all rules, might be uncertain about patient because not all test can/have been run\n* **Probability thoery** - main tool for dealing with degrees of beliefs\n* **Ontological commitments** - the world is composed of facts that do or do not hold in any particular case\n* **Epistemological commitments** - a logical agent believes each sentence to be true or false or has no opinion/probabilistic agent has numerical degree of belief 0-1\n* **Outcome** - a completely specified state\n* **Utility theory** - used to represent preferences and reason quantitatively with them\n* **Decision theory** - preferences, as expressed by utilities, are combined with probabilities in general theory of rational decisions\n* **Maximum expected utility (meu)** - an agent is rational iff it chooses the action that yields the highest expected utility, averaged over all possible action outcomes\n* **Sample space** - the set of all possible worlds; mutually exclusive and exhaustive\n* **Probability model** - associates a numerical probability P(w) with each possible world\n* **Proposition** - a set of worlds, synonymous with events; its probability is the sum of probabilities of worlds it holds\n* **Unconditional/prior probabilities** - degrees of belief in propositions in the absence of any other information\n* **Conditional/posterior probabilities** - the probabilitiy given some evidence that has already been revealed\n* **Product rule** - P(A and B) = P(A|B) * P(B)\n* **Factored representation** - a possible world is represented by a set of variable/value pairs\n* **Random variables** - variables in probability theory; begin with an uppercase letter; maps from domain of possible worlds to some range\n* **Bernoulli** - distribution in which the range is the set {0,1}\n* **Probability distribution** - an assignment of a probability for each possible value of the random variable\n* **Categorical distribution** - probability distribution with a finite, discrete range\n* **Probability density function** - define the probability that a random variable takes on some value x as a parameterized function of x\n* **Joint probability distribution** - distribution denoting probabilities of all combinations of multiple variables\n* **Full joint probability distribution** - joint distribution for all of the random variables\n* **Inclusion-exclusion principle** - P(a OR b) = P(a) + P(b) = P(a AND b)\n* **Probabilistic inference** - the computation of posterior probabilities for query propositions given observed evidence\n* **Marginal probabilitiy** - extracting the distribution over some subset of variables or a single variable\n* **Marginalization** - summing out; sum up the probabilities for each possible value of the other variables, theyreby taking them out of the equation\n* **Independence** - P(a|b) = P(a) or P(b|a) = P(b) or P(a and b) = P(a)P(b)\n* **Bayes' rule** - P(b|a) = (P(a|b)*P(b))/P(a) OR P(cause|effect) = (P(effect|cause)*P(cause))/P(effect)\n* **Causal direction** - P(effect|cause)\n* **Diagnostic direction** - P(cause|effect)\n* **Conditional independence** - P(X,Y|Z) = P(X|Z)P(Y|Z) => P(X|Y,Z) = P(X|Z) and P(Y|X,Z) = P(Y,Z)\n* **Separation** - decomposition of large probabilistic domains into weakly connected subsets through conditional independence\n* **Naive bayes model/bayesian classifier** - P(Causes, Effect_1, ..., Effect_n) = P(Cause)product for each i[P(Effect_i|Cause)]\n* **Text classification** - given a text, decide which of a predefined set of classes or categories it belongs to\n* **Chain rule of probability** - P(w1:n) = P(w1)*P(w2|w1)*P(w3|w1:2)...P(wn|w1:n-1)\n* **Bigram model** - approximates the probability of a word given all the previous words by only using conditional probability of preceding word\n* **Markov assumption** - probability of a word depends only the previous word\n* **N-gram** - looks n-1 words into the past\n* **Maximum likelihood estimation (mle)** - way to estimate bigram or n-gram probabilities\n* **Relative frequency** - dividing the observed frequency of a particular sequence by the observed frequency of a prefix\n* **Extrinsic evaluation** - evaluate the performance of a language model by embedding it into an application and measure how much application improves\n* **Intrinsic evaluation** - metric that measures the quality of a model independent of any application\n* **Training set/training corpus** - the corpus an n-gram model is trained on\n* **Test set/test corpus** - an unseen data set on which we can measure the quality of an n-gram model performance on\n* **Held out** - test sets that is not in training set because we hold them out from the training data\n* **Training on the test set** - introduces a bias that makes probabilities all look too high, causes inaccuracies in perplexity\n* **Perplexity** - of a language model on a test set is inverse probability of the test set normalized by number of words\n* **Weighted average branching factor** - the number of possible next words that can follow any word\n* **Sampling** - choose random points from a distribution according to their likelihood/generate sentences, choosing each according to likelihood defined by language model\n* **Sparsity** - because any corpus is limited, some perfectly acceptable English word sequences are bound to missing from it\n* **Zeros** - things that don't ever occur in the training set but do occur in the test set\n* **Closed vocabulary** - system in which the test set can only contain words from the lexicon, no unknown/out of vocabulary (OOV) words\n* **Oov rate** - the percentage of OOV words that appear in the test set\n* **Open vocabulary** - we model the potential unknown words in the test set by adding a pseudo-word called <UNK>\n* **Smoothing/discounting** - to keep language model from assigning zero probability to words in unseen contexts, shave off probability mass from more frequent events and given to these\n* **Laplace smoothing** - add one to all the n-gram counts before we normalize them into probabilities/add-one smoothing\n* **Adjusted count** - c_i* = ((c_i+1)*N)/(N+V)\n* **Discounting** - lowering some non-zero counts in order to get the probability mass that will be assigned to the zero counts\n* **Discount** - d_c = c*/c -> ratio of the discounted counts to the original counts\n* **Add-k smoothing** - instead of adding 1 to each count, add fractional count k- moves less of the probability mass from the seen to the unseen events\n* **Less context** - sometimes a good thing; helps to generalize more for contexts that the model hasn't learned much about\n* **Backoff** - we use trigram if evidence is sufficient, else use bigram, else use unigram->backoff to lower-order n-gram if zero evidence for higher-order n-gram\n* **Interpolation** - mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram, and unigram counts\n* **Em algorithm** - an iterative learning algorithm that converges on locally optimal lambdas\n* **Katz backoff** - rely on a discounted probability P* if we've seen this n-gram before, else recursively back off to Katz probability for shorter-history N-1-gram; combined with Good-Turing\n* **Stupid backoff** - tries to make the language model a true probability distribution-no discounting of the higher-order probabilities\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 = \"\"\"Bayesian network is a directed graph where each node corresponds to random variable, directed links/arrows connect pairs of nodes (X->Y means X is a parent of Y), graph is a DAG, \n",
        "each node X_i has probability information theta(X_i|Parents(X_i)) which quantifies effect of parents on node using finite number of parameters. \"\"\"\n",
        "\n",
        "chapter13_2 = \"\"\"P(x1,...,xn) = product(1 to n)[P(x_i|parents(X_i))], so each entry in the joint distribution is represented by the product of the appropriate elemnts of the local conditional \n",
        "distributions in the Bayes net. The Bayesian network is a correct representation of the domain only if each node is conditionally independent of its other predecessors in the node ordering, given \n",
        "its parents. The parents of node X_i should contain all those nodes in X_1,...,X_i-1 that directly influece X_i. Bayes net contain no redundant probability values. Often leave out links even though \n",
        "a slight dependency exists because slight gain in accuracy is not worth the additional complexity in the network. If we stick to a causal model, we end up having to specify fewer numbers and the numbers \n",
        "will often be easier to come up with. Each variable is conditionally independent of its non-descendants, given its parents. A variable is conditionally independent of all other nodes in the network, given \n",
        "its parents, children, and children's parents (Markov blanket). Noise-OR assumption rule: P(x_i|parents(X_i)) = 1- product(j:X_j=true)[q_j], where q_j is the inhibition probability for parent j. \n",
        "A network containing only continous variables with linear-Gaussian distributions has a joint distribution that is a multivariate Gaussian distribution over all variables. For distributions with discrete\n",
        "variables with continuous parents, probit model and alternative is expit or inverse logit model, using logistic function. \"\"\"\n",
        "\n",
        "chapter13_3 = \"\"\"P(X|e) = alpha*P(X,e) = alpha*sum(for each y)[P(X,e,y)]. A query can be answered by using a Bayes net by computing sums of products of conditional probabilities from the network. The enumeration\n",
        "algorithm for exact inference in Bayes net takes O(2^n) time when there are n Boolean variables. Summing out a variable from a product of factors is done by adding up the submatrices formed by fixing the variable to each \n",
        "of its values in turn--any factor that does not depend on the variable to be summed out can be moved outside the summation. The time and space requirements of variable elimination are dominated by the size of the largest \n",
        "factor constructed during the operation of the algorithm->method: eliminate whichever variable minimizes the size of the next factor to be constructed. **Every variable that is not an ancestor of a query variable or \n",
        "evidence variable is irrelevant to the query. Bayes net inference is #P-hard (number-P hard), which is strictly harder than NP-complete problems. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Bayesian network\" : \"represents dependencies among variables in any full join probability distribution\",   \n",
        "\"conditional probability table (CPT)\": \"local probability information attached to each node in network; each row contains conditional probability of each node value for a conditioning case\",\n",
        "\"conditioning case\": \"a possible combination of values for the parent nodes\",\n",
        "\"chain rule\": \"reducing each joint probability to a conditional probability and a joint probability on a smaller set of variables; P(X_i,X_i-1,...X_1)=P(X_i|Parents(X_i))\",\n",
        "\"topological order\": \"any order consistent with the directed graph structure\",\n",
        "\"locally structure/sparse\": \"system in which each subcomponents interacts directly with only a bounded number of other components\",\n",
        "\"Markov blanket\": \"a variable's parents, children, and children's parents\",\n",
        "\"moral graph\": \"add links between any unlinked pair of nodes that share a common child\",\n",
        "\"d-separates\": \"if third set Z blocks all paths between X AND Y in moral graph, Z d-separates X and Y->X conditionally independent of Y given Z\",\n",
        "\"deterministic node\": \"a node that has its value specified exactly by the values of its parents, with no uncertainty\",\n",
        "\"context-specific independence (CSI)\": \"a conditional distribution exhibits CSI if a variable is conditionally independent of some of its parents given certain values of others\",\n",
        "\"noisy\": \"logical relationships that are uncertain\",\n",
        "\"noisy-OR\": \"generalization of the logical OR; allows for uncertainty about the ability of each parent to cause the child to be true\",\n",
        "\"leak node\": \"covers miscellaneuous causes not listed in other nodes\",\n",
        "\"discretization\": \"a way of handling continuous variables; dividing up possible values into fixed set of intervals\",\n",
        "\"nonparametric representation\": \"define the conditional distribution implicitly with a collection of instances, each containing values of parent and child variables\",\n",
        "\"hybrid Bayesian network\": \"a network with both discrete and continuous variables\",\n",
        "\"linear-Gaussian\": \"conditional distribution in which child has Gaussian distribution whose mean varies linearly with value of parent and whose standard deviation is fixed\",\n",
        "\"conditional Gaussian\": \"when discrete variables are added as parents of continous variables; given any assignment to discrete variables, continuous variable distribution is Gaussian\",\n",
        "\"hidden variables\": \"neither input or output variables, are essential for structuring network so that it is reasonably sparse with manageable number of parameters\",\n",
        "\"variable elimination\": \"algorithm in which expressions are evaluated right-to-left, intermediate results stored, and summations over each variable done only for portions that depend on variable\",\n",
        "\"pointwise product\": \"f(X_1...X_j,Y_1,...,Y_k) x g(Y_1,...Y_k,Z_1,...Z_l) = h(X_1...X_j,Y_1,...Y_k,Z_1,...Z_l)\",\n",
        "\"singly connected networks/polytrees\": \"family of networks in which there is at most one undirected path-time/space complexity linear in size of network\",\n",
        "\"multiply connected networks\": \"variable elimination can have exponential time and space complexity\",\n",
        "\"weighted model counting (WMC)\": \"sums the total weight of the satisfying assignments for SAT expression-weight is product of conditional probabilities for each variable assignment given parents\",\n",
        "\"clustering/join tree algorithms\": \"join individual nodes of network to form cluster nodes in such a way that resulting network is polytree- O(n) time\"\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "db86b800-6185-48e6-aa7d-667628ae9671"
      },
      "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": 32,
      "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\nBayesian network is a directed graph where each node corresponds to random variable, directed links/arrows connect pairs of nodes (X->Y means X is a parent of Y), graph is a DAG, \neach node X_i has probability information theta(X_i|Parents(X_i)) which quantifies effect of parents on node using finite number of parameters. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nP(x1,...,xn) = product(1 to n)[P(x_i|parents(X_i))], so each entry in the joint distribution is represented by the product of the appropriate elemnts of the local conditional \ndistributions in the Bayes net. The Bayesian network is a correct representation of the domain only if each node is conditionally independent of its other predecessors in the node ordering, given \nits parents. The parents of node X_i should contain all those nodes in X_1,...,X_i-1 that directly influece X_i. Bayes net contain no redundant probability values. Often leave out links even though \na slight dependency exists because slight gain in accuracy is not worth the additional complexity in the network. If we stick to a causal model, we end up having to specify fewer numbers and the numbers \nwill often be easier to come up with. Each variable is conditionally independent of its non-descendants, given its parents. A variable is conditionally independent of all other nodes in the network, given \nits parents, children, and children's parents (Markov blanket). Noise-OR assumption rule: P(x_i|parents(X_i)) = 1- product(j:X_j=true)[q_j], where q_j is the inhibition probability for parent j. \nA network containing only continous variables with linear-Gaussian distributions has a joint distribution that is a multivariate Gaussian distribution over all variables. For distributions with discrete\nvariables with continuous parents, probit model and alternative is expit or inverse logit model, using logistic function. \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\nP(X|e) = alpha*P(X,e) = alpha*sum(for each y)[P(X,e,y)]. A query can be answered by using a Bayes net by computing sums of products of conditional probabilities from the network. The enumeration\nalgorithm for exact inference in Bayes net takes O(2^n) time when there are n Boolean variables. Summing out a variable from a product of factors is done by adding up the submatrices formed by fixing the variable to each \nof its values in turn--any factor that does not depend on the variable to be summed out can be moved outside the summation. The time and space requirements of variable elimination are dominated by the size of the largest \nfactor constructed during the operation of the algorithm->method: eliminate whichever variable minimizes the size of the next factor to be constructed. **Every variable that is not an ancestor of a query variable or \nevidence variable is irrelevant to the query. Bayes net inference is #P-hard (number-P hard), which is strictly harder than NP-complete problems. \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Bayesian network** - represents dependencies among variables in any full join probability distribution\n* **Conditional probability table (cpt)** - local probability information attached to each node in network; each row contains conditional probability of each node value for a conditioning case\n* **Conditioning case** - a possible combination of values for the parent nodes\n* **Chain rule** - reducing each joint probability to a conditional probability and a joint probability on a smaller set of variables; P(X_i,X_i-1,...X_1)=P(X_i|Parents(X_i))\n* **Topological order** - any order consistent with the directed graph structure\n* **Locally structure/sparse** - system in which each subcomponents interacts directly with only a bounded number of other components\n* **Markov blanket** - a variable's parents, children, and children's parents\n* **Moral graph** - add links between any unlinked pair of nodes that share a common child\n* **D-separates** - if third set Z blocks all paths between X AND Y in moral graph, Z d-separates X and Y->X conditionally independent of Y given Z\n* **Deterministic node** - a node that has its value specified exactly by the values of its parents, with no uncertainty\n* **Context-specific independence (csi)** - a conditional distribution exhibits CSI if a variable is conditionally independent of some of its parents given certain values of others\n* **Noisy** - logical relationships that are uncertain\n* **Noisy-or** - generalization of the logical OR; allows for uncertainty about the ability of each parent to cause the child to be true\n* **Leak node** - covers miscellaneuous causes not listed in other nodes\n* **Discretization** - a way of handling continuous variables; dividing up possible values into fixed set of intervals\n* **Nonparametric representation** - define the conditional distribution implicitly with a collection of instances, each containing values of parent and child variables\n* **Hybrid bayesian network** - a network with both discrete and continuous variables\n* **Linear-gaussian** - conditional distribution in which child has Gaussian distribution whose mean varies linearly with value of parent and whose standard deviation is fixed\n* **Conditional gaussian** - when discrete variables are added as parents of continous variables; given any assignment to discrete variables, continuous variable distribution is Gaussian\n* **Hidden variables** - neither input or output variables, are essential for structuring network so that it is reasonably sparse with manageable number of parameters\n* **Variable elimination** - algorithm in which expressions are evaluated right-to-left, intermediate results stored, and summations over each variable done only for portions that depend on variable\n* **Pointwise product** - f(X_1...X_j,Y_1,...,Y_k) x g(Y_1,...Y_k,Z_1,...Z_l) = h(X_1...X_j,Y_1,...Y_k,Z_1,...Z_l)\n* **Singly connected networks/polytrees** - family of networks in which there is at most one undirected path-time/space complexity linear in size of network\n* **Multiply connected networks** - variable elimination can have exponential time and space complexity\n* **Weighted model counting (wmc)** - sums the total weight of the satisfying assignments for SAT expression-weight is product of conditional probabilities for each variable assignment given parents\n* **Clustering/join tree algorithms** - join individual nodes of network to form cluster nodes in such a way that resulting network is polytree- O(n) time\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "46a86531-b5e8-45e1-b6e8-ebfaeb96ca61"
      },
      "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": 34,
      "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 Your summary here \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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 35,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "541f83e9-af57-4636-d7c7-fb97fdb5c907"
      },
      "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": 36,
      "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 Your summary here \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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 945
        },
        "outputId": "4653372d-ae30-45a2-9c27-70d8b0232cad"
      },
      "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": 38,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "ec9db465-e079-426c-c974-d4bfb6ea2960"
      },
      "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": 39,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nMEU principle formalizes that intelligent agent should do right thing, but does not operationalize \nthat advice. If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score, averaged over all possible environments. Performance measure applied \nretrospectively after an agent completes a sequence of actions VS utility function applies to the very next state used to guide actions \nstep by step.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n(1) ORDERABILITY: given any two lotteries, a rational agent must either prefer one or else rate equally preferable\n(2) TRANSITIVITY: given any three lotteries, if agent prefers A to B and B to C, must prefer A to C (3) CONTINUITY: if B is between A and C \nin preference, there is a probability p for which agent is indifferent between getting B for sure and the lottery that yields A with probability p\nand C with probability 1-p (4) SUBSTITUTABILITY: if agent indifferent between A and B, also indifferent between two more complex lotteries that are \nsame except B substituted for A in one of them (5) MONOTONICITY: if agent prefers A to B, agent must prefer lottery that has a higher probability for A\nand vice versa (6) DECOMPOSABILITY: compound lotteries can be reduced to simpler ones using probability laws. Existence of utility function: if agent's preferences\nobey axioms of utility, exists function U such that U(A) > U(B) iff A > B, and U(A) = U(B) if indifferent. \n\n## AIMA Chapter 16.3 Utility Functions\nAgents exhibit a monotonic preference for more money. Most people have a utility function that is concave for positive wealth. \n\n## AIMA Chapter 17.1 Sequential Decision Problems\nThe utility of an environment history is the sum of the rewards received. MDP consists of a set of states (with initial state), set of \nactions in each state, a transition model, and a reward function. The quality of a policy is measured by the expected utility of the possible environment histories generated \nby that policy. When discount factor is close to 0, rewards in the distant future are viewed as insignificant, and when close to 1, agent is more willing to wait for long-term \nrewards. The existence of improper policies can cause the standard algorithms for solving MDPs to fail with additive rewards- good reason for using discounted rewards. \nWith using discounted utilities and infinite horizons, optimal policy is independent of the starting state. The utility of a state is the expected reward for the next transition \nplus the discounted utility of the next state, assuming choosing optimal action. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nn possible states so n Bellman equations->start with arbitrary initial values for the utilities, update utility of each state from the utilities of its neighbors; repeat \nuntil equilibrium. This is guaranteed to reach an equilibrium, and final utility values are solutions to Bellman equations. Convergence of value iteration: repeated application of a contraction always \nreaches the fixed point in the limit. The Bellman update is a contraction by a factor of gamma on the space of utility vectors, so value iteration always converges to a unique solution \nof the Bellman equations whenever gamma < 1. We can get fast convergence if we make gamma small, but this gives the agent a short horizon and can miss long-term effects of actions. Policy iteration \nalgorithm terminates when policy improvement step yields no change in the utilities. For small state spaces, policy evaluation using exact solution methods is most efficient. MDPs can be solved in time polynomial \nto the number of states and actions and the number of bits required to specify the model. Value iteration and policy iteration are offline algorithms, generate an optimal solution for the \nproblem which can be executed by simple agent. EXPECTIMAX algorithm builds tree of alternating max and chance nodes, evaluation function applied to nonterminal leaves of tree, decision extracted \nfrom search tree by backing up utility values from leaves, taking average at chance nodes, and taking max at decision nodes\n\n## Module 8 Lecture Notes\n Your summary here \n\n## Module 8 Definitions\n* **Utility function** - U(s) assigns a single number to express desirability of a state\n* **Expected utility** - of an action EU(a) is average utility value of outcomes weighted by outcome probability\n* **Maximum expected utility (meu)** - rational agent should choose action that maximizes agent's expected utility\n* **Performance measure** - gives a score for a history - a sequence of states\n* **Lottery** - a lottery L with possible outcomes S1,..,Sn that occurs with probabilities P1,...,pn written L=[p1,S1;p2,S2,...,pn,Sn]\n* **Expected utility of lottery** - sum of probability of each outcome times the utility of that outcome\n* **Value function** - or ordinal utility function; agent only needs preference ranking on states, numbers don't matter\n* **Preference elicitation** - presenting choices to the human and using the observed preferences to pin down underlying utility function\n* **Normalized utilities** - use scale with worst possible catastrophe at U(S) = 0 and best possible prize at at U(S) = 1\n* **Value of a statistical life** - used by agencies to determine the costs and benefits of regulations and interventions\n* **Micromort** - one in a million chance of death\n* **Qaly** - quality-adjusted life year (shorter life expectancy to avoid disability)\n* **Risk-averse** - prefer a sure thing with a payoff that is less than the expected monetary value of a gamble\n* **Certainty equivalent** - the value an agent will accept in lieu of a lottery\n* **Insurance premium** - difference between the EMV of a lottery and its certainty equivalent\n* **Unbiased** - expected value of the error between estimate of expected utility and true utility is zero\n* **Order statistic** - the distribution of any particular ranked element of a sample\n* **Optimizer's curse** - tendency for the estimated expected utility of the best choice to be too high\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how actual agents really do act\n* **Certainty effect** - people are strongly attracted to gains that are certain\n* **Ambiguity aversion** - most people elect the known probability rather than the unknown unknowns\n* **Framing effect** - exact wording of a decision problem can have a big impact on agent's choice\n* **Anchoring effect** - people feel more comfortable making relative utility judgments rather than absolute ones\n* **Evolutionary psychology** - our brain's decision-making mechanisms did not evolve to solve word problems with decimal numbers\n* **Sequential decision problems** - agent's utility depends on a sequence of decisions\n* **Transition model** - describes the outcome of each action in each state\n* **Markovian** - the probability of reaching s' from s depends only on s and not on earlier states history\n* **Environment history** - the sequence of states and actions\n* **Markov decision process (mdp)** - sequential decision problem, fully observable, stochastic environment, Markovian transition model, additive rewards\n* **Dynamic programming** - method for solving MDP; recursively breaking into smaller pieces and remembering optimal solutions to those\n* **Policy** - a solution that specifies what agent should do for any state that agent might reach; pi(s) is action recommend for state s\n* **Optimal policy** - policy that yields the highest expected utility, pi*\n* **Finite horizon** - vs infinite horizon; there is a fixed time N after which nothing matters/game is over; depends on how much time is left\n* **Nonstationary** - policy that depends on the time\n* **Stationary** - optimal action depends only on the current state, since no fixed time limit\n* **Discount factor** - describes preference of an agent for current rewards over future rewards\n* **Additive rewards** - when discount factor is exactly one\n* **Proper policy** - a policy that is guaranteed to reach a terminal state\n* **Average reward** - obtained per time step; can be used to compare infinite sequences\n* **Action-utility function** - Q-function; Q(s,a) is the expected utility of taking a given action in a given state\n* **Shaping theorem** - R'(s,a,s') = R(s,a,s') + gamma*function(s')-function(s) leaves optimal policy unchanged\n* **Dynamic decision networks (ddns)** - represent MDPs with decision, reward, and utility nodes\n* **Bellman update** - iteration step that is applied simultaneously to all the states at each iteration\n* **Contraction** - function that when applied to two different inputs produces two output values closer together by constant factor\n* **Policy iteration algorithm** - alternates between policy evaluation and policy improvement\n* **Policy evaluation** - given a policy pi_i, calculate U_i = U^pi_i, the utility of each state if pi_i is executed\n* **Policy improvement** - calculate a new MEU policy pi_i+1 using one-step look-ahead based on U_i\n* **Modified policy iteration** - for large state spaces, perform simplified value iteration steps (fixed policy) to utility approximation\n* **Asynchronous policy iteration** - on each iteration, pick a subset of states and apply improvement or iteration to subset\n* **Real-time dynamic programming (rtdp)** - explored states are sub-MDP of original MDP; can solved using algorithms to yield curret state decision\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\nExploitation of current best action to obtain rewards vs exploration of previously unknown states and actions to gain information, which \ncan sometimes be converted into better policy/long-term rewards. Each arm M_i is a MRP, an MDP with one action, states S_i, transition model P_i(s'|s,a_i), reward \nR_i(s, a_i, s'). Arm defines distribution over sequences of rewards R_i,0, R_i,1, etc.. where each R_i,t is a random variable. Overall bandit problem is an MDP. One-Armed Bandit \nproblem: first arm M yields arbitrary sequence R0, R1, R2,... and second arm yields M_lambda yields lambda, lambda, lambda..for some known fixed constant lambda. \nGittins index provides a very simple optimal policy for any bandit problem: pull arm with highest Gittins index then update the Gittens indices. At the tipping point where optimal \npolicy is indifferent between choosing arm M and choosing the fixed arm M_lambda, value of choosing M is same as value of choosing an infinite sequence of lambda-rewards. \nFor Bernoulli bandit, state of each arm M_i defined by s_i and f_i, counts of successes and failures respectively. Transition probability predicts 1 with (s_i)/(s_i+f_i) and vice versa. \nNo index function exists for selection problems. Optimal bandit algorithms explore much less than optimal selection algorithms, because bandit algorithm assumes that a failed trial costs \nreal money. Globally optimal policy for a BSP may include actions that are locally suboptimal from POV of constituent MDP in which they are taken. \n\n## AIMA Chapter 22.1 Learning from Rewards\nReinforcement learning differs from MDP because agent is not given the MDP as a problem to solve; agent is in the MDP. It may not know the transition model or reward function and \nmust act in order to learn more. Action-utility learning and policy search are types of model-free reinforcement learning. \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\nCan reduce reinforcement learning to standard supervised learning problem in which each example is (state, reward-to-go) pair. The utility of a state is determined by the reward and the \nexpected utility of the successor states. Direct utility estimation learns nothing until the end of the trial; searches for U in a hypothesis space that is much larger than it needs to be, includes functions that \nviolate the Bellman equations; converges very slowly. In ADP, passive learning agent plugs in learned transition model and observed rewards to calculate state utilities. Learning transition model is easy: for each \ntraining example, update transition model table, couting how often state s' is reached when executing a in s. In temporal difference learning, apply following update when transition occurs from state s to state s' via action \npi(s): U_pi(s) = U_pi(s) + alpha*TD, where alpha is learning rate parameter. If turn alpha into function that decreases as the number of times a state has been visited increases, U_pi(s) will converge to correct value. TD does not \nlearn quite as fast as ADP agent and shows higher variability, but much simpler and less computation per observation. We can generate more efficient versions of ADP by bounding number of adjustements made after each observed transition or can use \na heuristic to rank the possible adjustements and carry out most significant ones. Using heuristics, approximate ADP algorithms can learn roughly as fast as full ADP and be more efficient. \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\nOptimal action can lead to suboptimal results since the learned model is not the same as the true environment. Actions do more than provide rewards, they also provide information in the form of percepts in the resulting states. \nADP agent using GLIE scheme can eventually learn the true transition model and operate under exploitation. Example of GLIE schemes: choose random action at time step t with probability 1/t else follow greedy policy. OR give weight to actions that \nagent has not tried very often and avoid action that are believed to be of low utility. Can use exploration function R+ if n < N_e and u otherwise, where R+ is optimistic estimate of the best possible reward obtainable in any state and N_e is fixed parameter. \nAgent will be able to try each state at least N_e times. As exploration proceeds, states and actions near start state might be tried a large number of times. If used U in RHS of equation, more pessimistic utility estimate, agent would become \ndisinclined to explore further. Using U+ means that benefits of exploration are propagated back from the edges of unexplored regions, so that actions that lead toward unexplored regions are weighted more highly. By choosing a policy based solely on the estimated model, \nit is acting as if the model were correct which is not necessarily a good idea. Better idea is to choose a policy that works well for whole range of models that have reasonable chance of being the true model, even if policy happens to be suboptimal for the maximum-likelihood \nmodel. In Bayesian reinforcement learning, U_h^pi is the expected utility averaged overall start states, obtained by executing policy pi in model h. In robust control theory, defines an optimal robust policy as one that gives the best outcome in the worst case over H, where \nset H is the set of models that exceed some likelihood threshold on P(h|e). In Q-learning, knowing Q-function enables agent to act optimally by choosing (action to maximize Q(s,a) with no need of look-ahead. A TD Q-learning agent does not need a transition model either for learning \nor for action selection. Difference between SARSA and Q-learning: the latter backs up the Q-value from the best action in state s', while SARSA waits until an action is taken and backs up the Q-value for that action. Two algorithms are identical if agent is greedy and always takes \naction with the best Q-value. Q-learning more flexible than SARSA, since Q-learning agent can learn how to behave well under variety of exploration policies. SARSA appropriate if policy being partly controlled by other agents or programs, so better to learn Q-function for what will \nactually happen rather than if able to pick the best action. \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\nGiven a collection of trials, we obtain a set of sample values of U_theta(x,y) and we can find best fit in the sense of minimizing the squared error using standard linear regression. If u_j(s) is the observed total reward from state s onward in the jth trial, then \nthen error is defined as half the squared difference of the predicted total and the actual total. The rate of change of the error with respect to each parameter moves the parameter in the direction of decreasing the error. Changing the parameters theta_i in response to an observed transition between \ntwo states also changes the values of U_theta for every other state-- function approximation allows reinforcement learner to generalize from its experiences. Experience replay: learning algorithm can retrain trajectories from entire learning process and replay those trajectories to ensure value function still accurate \nfor state space it no longer vists. For partially observable environment, learning problem is much more difficult because the next percept is no longer a label for the state prediction problem. Need to go beyond linear function approximators (1) may be no good linear function that comes close to approximating the \nutility function of Q-function (2) may not be able to invent the necessary features, esp in new domains -> explore more complex, nonlinear function approximators. With deep RL, often difficult to get good performance and trained system may behave unpredictably if environment differs even a little from training data. \nIn reward shaping, pseudorewards can speed up learnign enormously but risky because agent will learn to maximize pseudorewards rather than true rewards. In HRL, learning process converts the partial agent program into a complete program by learning how each choice should be made. Each choice in partial program invokes \nsubroutine that may itself make further choices all the way down to primitive actions that can be executed directly. Partial program provides general know-how-overall scaffolding and structural organization for complex behaviors, and the learning process works out all the details. In HRL, the overall utility decomposes into \nseveral terms, each of which depends on only a few variables-- learning occurs much more quickly than if we try to learn a single utility function that depends on all the variables. \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **N-armed bandit** - has n levers, behind each is fixed but unknown probability distribution of winnings\n* **Exploitation** - of the current best action to obtain rewards\n* **Exploration** - agent must experience as much as possible of its environment in order to learn how to behave in it\n* **Markov reward process** - MDP with only one possible action\n* **One-armed bandit** - one arm M that produces rewards R_0, R_1, R_2,..and costs lambda for each pull\n* **Stopping time** - if you pull the first arm T times @0, 1,...,T-1, stopping time is T\n* **Gittins index** - of an arm M; describes the maximum obtainable utility per unit of discounted time\n* **Restart mdp** - could replace choice to get infinite sequence of lambda-rewards with choice to go back and restart M from initial\n* **Bernoulli bandit** - each arm M_i produces a reward of 0 or 1 with fixed but unknown probability mu_i.\n* **Exploration bonus** - associated with arms only tried a few times VS arms with higher payoff probabilities which are preferred\n* **Confidence interval** - range within which the value of arm can be estimated to lie with high confidence\n* **Upper confidence bound/ucb heuristic** - policy that chooses arm with highest UCB value (current mean value + multiple of SD of value uncertainty\n* **Thompson sampling** - choose an arm randomly according to the probability that the arm is optimal, given samples so far\n* **Selection problem** - task of choosing the best option under conditions that don't have to minimize test failures\n* **Bandit superprocess** - BSP; each arm is a full MDP in its own right, rather than being a MRP with only one possible action\n* **Opportunity cost** - how much utility is given up per time step by not devoting that time step to another arm\n* **Dominating policy** - an optimal policy in a given arm is unaffected by the opportunity cost; converting arm into a MRP\n* **Supervised learning** - an agent learns by passively observing example input/output pairs provided by a teacher\n* **Reinforcement learning** - an agent interacts with the world and receives rewards/reinforcements that reflect how well it is doing\n* **Sparse rewards** - in the vast majority of states, the agent is given no informative reward signal at all\n* **Model-based reinforcement learning** - agent uses transition model of environment to help interpret the reward signals and making how to act decisions\n* **Model-free reinforcement learning** - agent knows nor learns a transition model for environment; learns direct representation of how to behave\n* **Action-utility learning** - Q-learning, where agent learns a Q-function Q(s,a) denoting sum of rewrds from state s onward if action a is taken\n* **Policy search** - keep twiddling the policy as long as its performance improves, then stop\n* **Passive reinforcement learning** - an agent's policy is fixed and task is to learn the utilities of states/or state-action pairs\n* **Active reinforcement learning** - agent must also figure out what to do\n* **Apprenticeship learning** - training a learning agent using demonstrations rather than reward signals\n* **Passive learning agent** - trying to learn the utility function U_pi(s)- expected total discounted reward if policy on state s\n* **Direct utility estimation** - utility of a state is defined as the expected total reward from that state onward/expected reward-to-go\n* **Adaptive dynamic programming (adp)** - takes advantage of constraints among utilities of states by learning transition model that connects them and solves corresponding MDP\n* **Modified policy iteration** - use a simplified value iteration process to update the utility estimates after each change to learned model\n* **Temporal-differene (td)** - an error signal; intended to reduce the error; R(s,pi(s),s') + gamma*U_pi(s') - U_pi(s)\n* **Prioritized sweeping** - heuristic that prefers to make adjustments to states whose likely successors have just undergone large adjustment to own utility estimates\n* **Active learning agent** - gets to decide what actions to take; no fixed policy determines its behavior\n* **Greedy agent** - greedily takes the action that it currently believes to be optimal at each step; sticks to policy; never learns utilities of other states\n* **Glie** - greedy in the limit of infinite exploration; try each action in each state infinite times to avoid having finite probability that optimal action is missed\n* **Irreversible** - no subsequent sequence of actions can restore the state to what it was before the irreversible action was taken\n* **Absorbing state** - no actions have any effect and no rewards are received\n* **Bayesian reinforcement learning** - assumes prior probability P(h) over hypotheses h about what true model is\n* **Posterior probability** - P(h|e) is obtained in the usual way by Bayes' rule given the observations to date\n* **Exploration pomdp** - if agent continues learning in future, must consider effects of future observations on its beliefs about transition model\n* **Robust control theory** - allows for a set of possible models H without assigning probabilities to them\n* **Q-learning** - method that avoids need for model by learning Q(s,a): expected total discounted reward if take action a in s and action optimally afterwards\n* **Sarsa (state, action, reward, state, action** - updates the Q-value of the action a' that is actually taken\n* **Off-policy** - What would this action be worth in this state, assuming I stop using whatever policy rn and start acting to policy that chooses best action\n* **On-policy** - What would this action be worth in this state, assuming I stick with my policy?\n* **Evaluation function** - a compact measure of desirability for potentially vast state spaces; approximate utility function\n* **Function approximation** - process of constructing a compact approximation of the true utility function or Q-function\n* **Features** - can approximate utility function using weighted linear combination of features; U_theta(s)=theta_1*f_1(s) + theta_2*f_2(s) + ...\n* **Catastrohic forgetting** - ex: car learned too well; learned entire central region of road is safe and forgotten that region closer to edge is dangerous\n* **Experience replay** - ex: ensures car keeps reliving its youthful crashing behavior at regular intervals\n* **Deep reinforcement learning system** - reinforcement learning system that uses a deep network as a function approximator\n* **Credit assignment problem** - many primitive actions required to achieve nonzero reward- need to work out what agent did wrong\n* **Reward shaping** - supplying agent with additional rewards (pseudorewards) for making progress\n* **Hierarchical reinforcement learning (hrl)** - break up long action sequences into few smaller pieces, etc, until action sequences short enough to make learning easy\n* **Partial program** - HRL agent begins with this outline of a hierarchical structure for its behavior\n* **Choose** - operator in partial program that allows agent to choose any element of the specified set\n* **Joint state space** - each state (s,m) is composed of a physical state s and a machine state m\n* **Machine state** - defined by current internal state of agent program, PC for each subroutine, values of arguments, variables, etc\n* **Choice state** - sigma(s, m) is one in which the program counter for m is at a choice point in the agent program\n* **Additive decomposition** - hierarchical structure of behavior means can break up overall utility function in this manner\n* **Stochastic policy** - pi_theta(s, a) which specifies the probability of selecting action a in state s\n* **Policy value** - p(theta), the expected reward-to-go when pi_theta is executed\n* **Policy gradient** - vector delta_theta(p(theta)) for optimization problem of p(theta)\n* **Empirical gradient** - evaluating the change in policy value for small increments in each parameters; converges to local optimum in policy space\n* **Correlated sampling** - use an environment simulator in which the random-number sequences can be repeated (ex: blackjack-each program plays same set of hands)\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nThe rational decision depends on both the relative importance of various goals and the likelihood that, and degree to \nwhich, they will be achieved. The theory of probability provides a way of summarizing the uncertainty that comes from our laziness and ignorance. \nProbability statements are made with respect to a knowledge state, not with respect to the real world. Utility theory: every state, or state sequence, \nhas a degree of usefulness, or utility, to an agent and that the agent will prefer states with higher utility. \n\n## AIMA Chapter 12.2 Basic Probability Notation\nConditional probability: P(A|B) = P(A and B)/P(B). A possible world is defined to be an assignment of values to all of the random variables \nunder consideration.\n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\nGeneral inference procedure: P(X|e) = alpha*P(X,e) = alpha*sum for each y[P(X, e, y)], where e is the observed values for the evidence \nvariables, y is the values of the unobserved variables\n\n## AIMA Chapter 12.4 Independence\nIf the complete set of variables can be divided into independent subsets, then the full joint distribution can be factored into separate joint \ndistributions on those subsets.\n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\nMore general version of Bayes' rule conditionalized on background evidence e: P(Y|X,e) = (P(X|Y,e) * P(Y|e))/P(X|e). General form of Bayes' rule with \nnormalization is P(Y,X) = alpha*P(X|Y)P(Y). Diagnostic knowledge is often more fragile than causal knowledge. Conditional independence assertions can allow probabilistic systems\nto scale up; they are much more commonly available than absolute independence assertions. \n\n## AIMA Chapter 12.6 Naive Bayes Models\nFor each possible cause, multiply the prior probability of the cause by the product of the conditional probabilities of the observed effects given the cause, then \nnromalize the result. Runtime of this calculation is linear in number of observed effects- does not depend on number of unobserved effects. For text classification, to categorize \na new document, check which key words appear in the document and then apply equation to obtain posterior probability distribution over categories. Violate of independence in naive \nBayes model means that final posterior probabilities will be much closer to 1/0 than it should be; model is overconfident in its predictions. \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n## SLP Chapter 3.1 N-Grams\nGeneral equation for the n-gram approximation to the conditional probability of the next word in a sequence is P(w_n|w_1:n-1) = P(w_n|w_n-N+1:n-1). \nAlways represent and compute language model probabilities in log format as log probabilities: p1*p2*p3*p4 = exp(log(p1) + log(p2) + log(p3) + log(p4))\n\n## SLP Chapter 3.2 Evaluating Language Models\nFit the test set means whichever model assigns a higher probability to the test set (more accurately predicts the test set) is a better model->tighter fit to the test data, better \npredicts the details of the test data. Minimizing perplexity is equivalent to maximizing the test set probability according to the lanugage model. The more information the n-gram gives us about the word\nsequence, the lower the perplexity. An intrinsic improvement in perplexity does not guarantee an extrinsic improvement in the performance of a language processing task. \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n\n\n## SLP Chapter 3.4 Generalization and Zeros\nProbabilities often encode specific facts about a given training corpus. N-grams do a better and better job of modeling the training corpus as we increase the value of N. The longer the \ncontext on which we train the model, the more coherent the sentences. When building n-gram models, use a training corpus that has a similar genre to whatever task we are trying to accomplish. Important to get training \ndata in the appropriate dialect or variety. Zeroes means we are underestimating the probability of all sorts of words that might occur. Also, if the probability of any word in the test set is 0, the entire probability of the \ntest set is 0. Thus, cannot compute perplexity. Can deal with unknown words by (1) choose vocabulary that is fixed (2) convert in training set any OOV word to <UNK> in text normalization step (3) estimate probabilities for <UNK> \nfrom its counts just like any other regular word in the training set OR create a vocabulary and replace words in the training data by <UNK> based on their frequency (ex: replace by <UNK> all words that occur fewer than n times in \nthe training set. or select a vocabulary size V in adfance and choose top V words by frequency and replace rest by <UNK>). Overall, perplexities should only be compared across language models with the same vocabularies. \n\n## SLP Chapter 3.5 Smoothing\nP_laplace(w_i) = (c_i+1)/(N + V). P_add-k(w_n|w_n-1) = (C(w_n-1w_n)+k)/(C(w_n-1)+kV). Lambda values for interpolation are learned from a held-out corups- an additional training corpus that we use to set hyperparameters->fix \nthe n-gram probabilities and then search for the lambda values that give us the highest probability of the held out set. In order for backoff model to give correct probability distribution, we have to discount the higher-order n-grams to save some \nprobability mass for the lower-order n-grams. \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\nEfficiency considerations are important when building language models that use such large sets of n-grams-> usually represent a word in memory as 64-bit hash number, with the words themselves stored on disk. \nCan also do pruning, and store n-grams with counts greater than some threshold or use entropy to prune less-important n-grams or Bloom Filters. \n\n## Module 10 Lecture Notes\n Your summary here \n\n## Module 10 Definitions\n* **Belief state** - representation of the set of all possible world states that agent might be in\n* **Laziness** - too much work to list the complete set of antecedents or consequents needed to ensure exceptionless rule/too hard\n* **Theoretical ignorance** - medical science has no complete theory for the domain\n* **Practical ignorance** - even if know all rules, might be uncertain about patient because not all test can/have been run\n* **Probability thoery** - main tool for dealing with degrees of beliefs\n* **Ontological commitments** - the world is composed of facts that do or do not hold in any particular case\n* **Epistemological commitments** - a logical agent believes each sentence to be true or false or has no opinion/probabilistic agent has numerical degree of belief 0-1\n* **Outcome** - a completely specified state\n* **Utility theory** - used to represent preferences and reason quantitatively with them\n* **Decision theory** - preferences, as expressed by utilities, are combined with probabilities in general theory of rational decisions\n* **Maximum expected utility (meu)** - an agent is rational iff it chooses the action that yields the highest expected utility, averaged over all possible action outcomes\n* **Sample space** - the set of all possible worlds; mutually exclusive and exhaustive\n* **Probability model** - associates a numerical probability P(w) with each possible world\n* **Proposition** - a set of worlds, synonymous with events; its probability is the sum of probabilities of worlds it holds\n* **Unconditional/prior probabilities** - degrees of belief in propositions in the absence of any other information\n* **Conditional/posterior probabilities** - the probabilitiy given some evidence that has already been revealed\n* **Product rule** - P(A and B) = P(A|B) * P(B)\n* **Factored representation** - a possible world is represented by a set of variable/value pairs\n* **Random variables** - variables in probability theory; begin with an uppercase letter; maps from domain of possible worlds to some range\n* **Bernoulli** - distribution in which the range is the set {0,1}\n* **Probability distribution** - an assignment of a probability for each possible value of the random variable\n* **Categorical distribution** - probability distribution with a finite, discrete range\n* **Probability density function** - define the probability that a random variable takes on some value x as a parameterized function of x\n* **Joint probability distribution** - distribution denoting probabilities of all combinations of multiple variables\n* **Full joint probability distribution** - joint distribution for all of the random variables\n* **Inclusion-exclusion principle** - P(a OR b) = P(a) + P(b) = P(a AND b)\n* **Probabilistic inference** - the computation of posterior probabilities for query propositions given observed evidence\n* **Marginal probabilitiy** - extracting the distribution over some subset of variables or a single variable\n* **Marginalization** - summing out; sum up the probabilities for each possible value of the other variables, theyreby taking them out of the equation\n* **Independence** - P(a|b) = P(a) or P(b|a) = P(b) or P(a and b) = P(a)P(b)\n* **Bayes' rule** - P(b|a) = (P(a|b)*P(b))/P(a) OR P(cause|effect) = (P(effect|cause)*P(cause))/P(effect)\n* **Causal direction** - P(effect|cause)\n* **Diagnostic direction** - P(cause|effect)\n* **Conditional independence** - P(X,Y|Z) = P(X|Z)P(Y|Z) => P(X|Y,Z) = P(X|Z) and P(Y|X,Z) = P(Y,Z)\n* **Separation** - decomposition of large probabilistic domains into weakly connected subsets through conditional independence\n* **Naive bayes model/bayesian classifier** - P(Causes, Effect_1, ..., Effect_n) = P(Cause)product for each i[P(Effect_i|Cause)]\n* **Text classification** - given a text, decide which of a predefined set of classes or categories it belongs to\n* **Chain rule of probability** - P(w1:n) = P(w1)*P(w2|w1)*P(w3|w1:2)...P(wn|w1:n-1)\n* **Bigram model** - approximates the probability of a word given all the previous words by only using conditional probability of preceding word\n* **Markov assumption** - probability of a word depends only the previous word\n* **N-gram** - looks n-1 words into the past\n* **Maximum likelihood estimation (mle)** - way to estimate bigram or n-gram probabilities\n* **Relative frequency** - dividing the observed frequency of a particular sequence by the observed frequency of a prefix\n* **Extrinsic evaluation** - evaluate the performance of a language model by embedding it into an application and measure how much application improves\n* **Intrinsic evaluation** - metric that measures the quality of a model independent of any application\n* **Training set/training corpus** - the corpus an n-gram model is trained on\n* **Test set/test corpus** - an unseen data set on which we can measure the quality of an n-gram model performance on\n* **Held out** - test sets that is not in training set because we hold them out from the training data\n* **Training on the test set** - introduces a bias that makes probabilities all look too high, causes inaccuracies in perplexity\n* **Perplexity** - of a language model on a test set is inverse probability of the test set normalized by number of words\n* **Weighted average branching factor** - the number of possible next words that can follow any word\n* **Sampling** - choose random points from a distribution according to their likelihood/generate sentences, choosing each according to likelihood defined by language model\n* **Sparsity** - because any corpus is limited, some perfectly acceptable English word sequences are bound to missing from it\n* **Zeros** - things that don't ever occur in the training set but do occur in the test set\n* **Closed vocabulary** - system in which the test set can only contain words from the lexicon, no unknown/out of vocabulary (OOV) words\n* **Oov rate** - the percentage of OOV words that appear in the test set\n* **Open vocabulary** - we model the potential unknown words in the test set by adding a pseudo-word called <UNK>\n* **Smoothing/discounting** - to keep language model from assigning zero probability to words in unseen contexts, shave off probability mass from more frequent events and given to these\n* **Laplace smoothing** - add one to all the n-gram counts before we normalize them into probabilities/add-one smoothing\n* **Adjusted count** - c_i* = ((c_i+1)*N)/(N+V)\n* **Discounting** - lowering some non-zero counts in order to get the probability mass that will be assigned to the zero counts\n* **Discount** - d_c = c*/c -> ratio of the discounted counts to the original counts\n* **Add-k smoothing** - instead of adding 1 to each count, add fractional count k- moves less of the probability mass from the seen to the unseen events\n* **Less context** - sometimes a good thing; helps to generalize more for contexts that the model hasn't learned much about\n* **Backoff** - we use trigram if evidence is sufficient, else use bigram, else use unigram->backoff to lower-order n-gram if zero evidence for higher-order n-gram\n* **Interpolation** - mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram, and unigram counts\n* **Em algorithm** - an iterative learning algorithm that converges on locally optimal lambdas\n* **Katz backoff** - rely on a discounted probability P* if we've seen this n-gram before, else recursively back off to Katz probability for shorter-history N-1-gram; combined with Good-Turing\n* **Stupid backoff** - tries to make the language model a true probability distribution-no discounting of the higher-order probabilities\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\nBayesian network is a directed graph where each node corresponds to random variable, directed links/arrows connect pairs of nodes (X->Y means X is a parent of Y), graph is a DAG, \neach node X_i has probability information theta(X_i|Parents(X_i)) which quantifies effect of parents on node using finite number of parameters. \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\nP(x1,...,xn) = product(1 to n)[P(x_i|parents(X_i))], so each entry in the joint distribution is represented by the product of the appropriate elemnts of the local conditional \ndistributions in the Bayes net. The Bayesian network is a correct representation of the domain only if each node is conditionally independent of its other predecessors in the node ordering, given \nits parents. The parents of node X_i should contain all those nodes in X_1,...,X_i-1 that directly influece X_i. Bayes net contain no redundant probability values. Often leave out links even though \na slight dependency exists because slight gain in accuracy is not worth the additional complexity in the network. If we stick to a causal model, we end up having to specify fewer numbers and the numbers \nwill often be easier to come up with. Each variable is conditionally independent of its non-descendants, given its parents. A variable is conditionally independent of all other nodes in the network, given \nits parents, children, and children's parents (Markov blanket). Noise-OR assumption rule: P(x_i|parents(X_i)) = 1- product(j:X_j=true)[q_j], where q_j is the inhibition probability for parent j. \nA network containing only continous variables with linear-Gaussian distributions has a joint distribution that is a multivariate Gaussian distribution over all variables. For distributions with discrete\nvariables with continuous parents, probit model and alternative is expit or inverse logit model, using logistic function. \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\nP(X|e) = alpha*P(X,e) = alpha*sum(for each y)[P(X,e,y)]. A query can be answered by using a Bayes net by computing sums of products of conditional probabilities from the network. The enumeration\nalgorithm for exact inference in Bayes net takes O(2^n) time when there are n Boolean variables. Summing out a variable from a product of factors is done by adding up the submatrices formed by fixing the variable to each \nof its values in turn--any factor that does not depend on the variable to be summed out can be moved outside the summation. The time and space requirements of variable elimination are dominated by the size of the largest \nfactor constructed during the operation of the algorithm->method: eliminate whichever variable minimizes the size of the next factor to be constructed. **Every variable that is not an ancestor of a query variable or \nevidence variable is irrelevant to the query. Bayes net inference is #P-hard (number-P hard), which is strictly harder than NP-complete problems. \n\n## Module 11 Lecture Notes\n Your summary here \n\n## Module 11 Definitions\n* **Bayesian network** - represents dependencies among variables in any full join probability distribution\n* **Conditional probability table (cpt)** - local probability information attached to each node in network; each row contains conditional probability of each node value for a conditioning case\n* **Conditioning case** - a possible combination of values for the parent nodes\n* **Chain rule** - reducing each joint probability to a conditional probability and a joint probability on a smaller set of variables; P(X_i,X_i-1,...X_1)=P(X_i|Parents(X_i))\n* **Topological order** - any order consistent with the directed graph structure\n* **Locally structure/sparse** - system in which each subcomponents interacts directly with only a bounded number of other components\n* **Markov blanket** - a variable's parents, children, and children's parents\n* **Moral graph** - add links between any unlinked pair of nodes that share a common child\n* **D-separates** - if third set Z blocks all paths between X AND Y in moral graph, Z d-separates X and Y->X conditionally independent of Y given Z\n* **Deterministic node** - a node that has its value specified exactly by the values of its parents, with no uncertainty\n* **Context-specific independence (csi)** - a conditional distribution exhibits CSI if a variable is conditionally independent of some of its parents given certain values of others\n* **Noisy** - logical relationships that are uncertain\n* **Noisy-or** - generalization of the logical OR; allows for uncertainty about the ability of each parent to cause the child to be true\n* **Leak node** - covers miscellaneuous causes not listed in other nodes\n* **Discretization** - a way of handling continuous variables; dividing up possible values into fixed set of intervals\n* **Nonparametric representation** - define the conditional distribution implicitly with a collection of instances, each containing values of parent and child variables\n* **Hybrid bayesian network** - a network with both discrete and continuous variables\n* **Linear-gaussian** - conditional distribution in which child has Gaussian distribution whose mean varies linearly with value of parent and whose standard deviation is fixed\n* **Conditional gaussian** - when discrete variables are added as parents of continous variables; given any assignment to discrete variables, continuous variable distribution is Gaussian\n* **Hidden variables** - neither input or output variables, are essential for structuring network so that it is reasonably sparse with manageable number of parameters\n* **Variable elimination** - algorithm in which expressions are evaluated right-to-left, intermediate results stored, and summations over each variable done only for portions that depend on variable\n* **Pointwise product** - f(X_1...X_j,Y_1,...,Y_k) x g(Y_1,...Y_k,Z_1,...Z_l) = h(X_1...X_j,Y_1,...Y_k,Z_1,...Z_l)\n* **Singly connected networks/polytrees** - family of networks in which there is at most one undirected path-time/space complexity linear in size of network\n* **Multiply connected networks** - variable elimination can have exponential time and space complexity\n* **Weighted model counting (wmc)** - sums the total weight of the satisfying assignments for SAT expression-weight is product of conditional probabilities for each variable assignment given parents\n* **Clustering/join tree algorithms** - join individual nodes of network to form cluster nodes in such a way that resulting network is polytree- O(n) time\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 Your summary here \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 Your summary here \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 Your summary here \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0qdw-p3jz8ez"
      },
      "source": [
        ""
      ],
      "execution_count": 39,
      "outputs": []
    }
  ]
}