{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Namita- Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1718c30e-a810-48af-9bcb-c89270e3f082"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "80620571-1e0f-491b-b1c4-b2eef4bc4c85"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "The agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence,EU(a), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n",
        "\n",
        "The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility: argmax EU(a).\n",
        "\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments).\n",
        " \"\"\"\n",
        "chapter16_2 =  \"\"\"We can think of the set of outcomes for each action as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1... Sn that occur with probabilities p1...pn is written\n",
        "L = [p1,S1: p2,S2: p3,S3...pn,Sn].\n",
        "Utility function is not unique. And the numbers don’t matter, only the preference.\n",
        "As in game-playing, in a deterministic environment, an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \"\"\"\n",
        "chapter16_3 =  \"\"\"Utility functions map lotteries to real numbers.\n",
        "Preference elicitation: involves presenting choices to the human and using the observed preferences to pin down the underlying utility function.\n",
        "\n",
        "Measurements of Utility:\n",
        "> One common “currency” used in medical and safety analysis is the micromort, a one in a million chance of death.\n",
        "> QALY: quality-adjusted life year. Patients are willing to accept a shorter life expectancy to avoid a disability.\n",
        "Utility of money:\n",
        "We say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\n",
        "Expected Monetary Value: summation of probability*utility.\n",
        "premium.\n",
        "It is a straightforward matter to calculate the distribution of the maximum of the  estimates and hence quantify the extent of our disappointment. (This calculation is a special case of computing an order statistic, the distribution of any particular ranked element of a sample.) \n",
        " \n",
        "Decision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act.\n",
        "The value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. \n",
        "The difference between the EMV of a lottery and its certainty equivalent is called the insurance \n",
        "This tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse. Can be avoided using Bayesian Priors. (MLE and MAP).\n",
        "Ambiguity Aversion:  Most people elect the known probability rather than the unknown unknowns.\n",
        "Yet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect.\n",
        "People feel more comfortable making relative utility judgments rather than absolute ones. I may have little idea how much I might enjoy the various wines offered by a restaurant. The restaurant takes advantage of this by offering an expensive bottle that nobody will buy, but which serves to skew upward the customer’s estimate of the value of all wines, making a 55 dollar bottle seem like a bargain. This is called the anchoring effect.\n",
        "The evidence for human irrationality is also questioned by researchers in the field of evolutionary psychology, who point to the fact that our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal numbers. \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Transition function: P(s’|s,a)\n",
        "Finite Horizon: A finite horizon means that there is a fixed time N after which nothing matters—the game is over, so to speak.\n",
        " So, with a finite horizon, an optimal action in a given state may depend on how much time is left. A policy that depends on the time is called nonstationary.\n",
        "Infinite Horizon  -> stationary\n",
        "Reasons why additive discounted rewards make sense:\n",
        "> empirical, rewards sooner than later.\n",
        "> economical (monetary). Discount factor of gamma → interest rate of (1/gamma) - 1\n",
        "> A third reason is uncertainty about the true rewards.\n",
        "> natural property of preferences over histories.\n",
        "> conveniently makes some nasty infinities go away.\n",
        " \n",
        "A policy that is guaranteed to reach a terminal state is called a proper policy.\n",
        "Expected Utility:\n",
        "\n",
        "\n",
        "Bellman’s equation:\n",
        "\n",
        "\n",
        "Another important quantity is the action-utility function, or Q-function.\n",
        "\n",
        "\n",
        "So adding a potential-based reward to any other reward shouldn’t change the optimal policy.\n",
        "Bayesian networks with decision, reward, and utility nodes to create dynamic decision networks, or DDNs. \"\"\"\n",
        "chapter17_2 =  \"\"\"Value Iteration Algorithm:\n",
        "Solved using Bellman update:\n",
        "\n",
        "We can think of the value iteration algorithm as propagating information through the state space by means of local updates.\n",
        "Why do Values converge?\n",
        "> A contraction is a function of one argument that, when applied to two different inputs in turn, produces two output values that are “closer together,” by at least some constant factor, than the original inputs.\n",
        "> We measure distance between utilities using MAX NORM.\n",
        "> the Bellman update is a contraction by a factor of gamma on the space of utility vectors. \n",
        "> error is reduced by the factor of gamma in each iteration\n",
        "No of iterations needed to converge:\n",
        "\n",
        "Policy loss: is the most the agent can lose by executing  πi  instead of the optimal policy  π∗\n",
        "I.e \n",
        " \n",
        " \n",
        "POLICY ITERATION:\n",
        "POLICY EVALUATION: given a policy πi, calculate Ui=Uπi, the utility of each state if πi were to be executed.\n",
        "POLICY IMPROVEMENT: Calculate a new MEU policy πi+1, using one-step look-ahead based on Ui \n",
        " \n",
        "How do we implement Policy-Evaluation? It turns out that doing so is simpler than solving the standard Bellman equations (which is what value iteration does) because the action in each state is fixed by the policy. \n",
        "\n",
        "Time complexity = O(n^3)\n",
        " \n",
        "Modified Policy Iteration: For larger states, to reduce time complexity\n",
        "> It turns out that doing so is simpler than solving the standard Bellman equations (which is what value iteration does), because the action in each state is fixed by the policy. \n",
        "\n",
        "The algorithms we have described so far require updating the utility or policy for all states at once. It turns out that this is not strictly necessary. In fact, on each iteration, we can pick any subset of states and apply either kind of updating (policy improvement or simplified value iteration) to that subset. This very general algorithm is called asynchronous policy iteration.\n",
        " \n",
        "Linear Programming:\n",
        "Linear programming or LP is a general approach for formulating constrained optimization problems, and there are many industrial-strength LP solvers available\n",
        "\n",
        "Online Algorithms for MDP:\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" > Navigating the Asteroid world: transition model is stochastic.\n",
        "> Transition function: T(s’,a,s) =  p(s’|s,a) (markovian, instead of having a successor of the state)\n",
        "> Reward function - utility or reward function for the agent. \n",
        "> Rewards can be positive/negative but bounded by max value. \n",
        "> As decision process is sequential, utility function is specified on sequence of states and actions: R(s’,a,s).\n",
        " > A Markov decision process or MDP is \n",
        "• a sequential decision problem \n",
        "• for a fully observable environment \n",
        "• with a stochastic transition model \n",
        "• that has additive rewards MDPs are non-deterministic search problems. One way of solving them is via expectimax search. \n",
        " \n",
        "MDP formulation: set of states, set of actions, transition function, reward function, the initial state, optionally one or more terminal states.\n",
        " \n",
        "Solution to MDP is a policy. A policy maps from a state onto the action to take if the agent is in that state. Because you might end up in a state you didn’t expect to, hence every state needs to be mapped to an action.\n",
        " \n",
        "Even if the same policy is executed multiple times by the agent, this may lead to a different sequence of states and actions (environment history), and thus a different score under the reward function. Therefore we need to compute the expected utility of all the possible paths generated by a policy. Depends highly on the reward of each state.\n",
        " \n",
        "The performance of an agent in an MDP is the sum of the rewards for the transitions it takes.\n",
        " \n",
        "Utility of Sequences: if each sequence has different rewards -> maximize the reward, get reward now than later because of stochasticity.\n",
        " \n",
        "Stationary Preferences:\n",
        "\n",
        " \n",
        "\n",
        "Infinite Utilities?!\n",
        "▪Problem: What if the game lasts forever? Do we get infinite rewards?\n",
        "▪Solutions:\n",
        "▪ Finite horizon: (similar to depth-limited search)\n",
        "▪ Terminate episodes after a fixed T steps (e.g. life)\n",
        "▪ Gives nonstationary policies ( depends on time left)\n",
        "▪ Discounting: use 0 <gamma < 1\n",
        "▪ Smaller gamma means smaller “horizon” – shorter term focus\n",
        "▪ Absorbing state: guarantee that for every policy, a terminal state will eventually be reached (like “overheated” for racing)\n",
        "Optimal Quantities\n",
        "▪ The value (utility) of a state s: V * (s) = expected utility starting in s and acting optimally \n",
        "▪ The value (utility) of a q-state (s,a): Q* (s,a) = expected utility starting out having taken action a from state s and (thereafter) acting optimally \n",
        "▪ The optimal policy:  pi* (s) = optimal action from state s\n",
        "\n",
        "Value Iteration: complexity is O(a*s^2)\n",
        "Policy Evaluation: no best policy given, just follow pi blindly: O(s^2)\n",
        "\n",
        "Optimal policy, policy extraction:\n",
        "\n",
        " \n",
        "How V under policy looks like:\n",
        "\n",
        "How Q looks like:\n",
        "\n",
        "\n",
        " \n",
        "Policy Iteration Algorithm:\n",
        "To tackle problems with Value Iteration -> \n",
        "Value iteration repeats bellman updates and it’s slow. The max at each state barely changes, only value changes. Therefore, value convergence happens way after action (policy) convergence.\n",
        "Policy Iteration algo:\n",
        "Alternative approach for optimal values:\n",
        "• Step 1: Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n",
        "• Step 2: Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future values\n",
        "• Step 3: Repeat steps until policy converges!\n",
        "• It’s still optimal!\n",
        "• Can converge (much) faster under some conditions\n",
        " \n",
        "UTILITIES:\n",
        "A rational agent should choose the action that maximizes its expected utility, given its knowledge.\n",
        "For worst case minimax reasoning, insensitivity to monotonic functions: max doesn't change with, example, x to x^2, decision remains the same.\n",
        "But for, average case expectimax, we need magnitudes to be meaningful.\n",
        "Utilities are functions from outcomes (states of the world) to real numbers that describe an agent’s preferences.\n",
        " \n",
        "\n",
        " \n",
        "\n",
        " \n",
        "Utility Scales\n",
        "▪ Normalized utilities: u+ = 1.0, u- = 0.0\n",
        "▪ Micromorts: one-millionth chance of death, useful for paying to reduce product risks, etc.\n",
        "▪ QALYs: quality-adjusted life years, useful for medical decisions involving substantial risk\n",
        "▪ Note: behavior is invariant under positive linear transformation\n",
        "▪ With deterministic prizes only (no lottery choices), only ordinal utility can be determined, i.e., total order on prizes\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"Your definition here\",\n",
        "\"expected utility\" : \"your definition here\",\n",
        "\"etc.\": \"your definition here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "703baca9-e652-49ab-b0f7-8b8c43fb40a2"
      },
      "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": 3,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence,EU(a), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility: argmax EU(a).\n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments).\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nWe can think of the set of outcomes for each action as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1... Sn that occur with probabilities p1...pn is written\nL = [p1,S1: p2,S2: p3,S3...pn,Sn].\nUtility function is not unique. And the numbers don’t matter, only the preference.\nAs in game-playing, in a deterministic environment, an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions map lotteries to real numbers.\nPreference elicitation: involves presenting choices to the human and using the observed preferences to pin down the underlying utility function.\n\nMeasurements of Utility:\n> One common “currency” used in medical and safety analysis is the micromort, a one in a million chance of death.\n> QALY: quality-adjusted life year. Patients are willing to accept a shorter life expectancy to avoid a disability.\nUtility of money:\nWe say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\nExpected Monetary Value: summation of probability*utility.\npremium.\nIt is a straightforward matter to calculate the distribution of the maximum of the  estimates and hence quantify the extent of our disappointment. (This calculation is a special case of computing an order statistic, the distribution of any particular ranked element of a sample.) \n \nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act.\nThe value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. \nThe difference between the EMV of a lottery and its certainty equivalent is called the insurance \nThis tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse. Can be avoided using Bayesian Priors. (MLE and MAP).\nAmbiguity Aversion:  Most people elect the known probability rather than the unknown unknowns.\nYet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect.\nPeople feel more comfortable making relative utility judgments rather than absolute ones. I may have little idea how much I might enjoy the various wines offered by a restaurant. The restaurant takes advantage of this by offering an expensive bottle that nobody will buy, but which serves to skew upward the customer’s estimate of the value of all wines, making a 55 dollar bottle seem like a bargain. This is called the anchoring effect.\nThe evidence for human irrationality is also questioned by researchers in the field of evolutionary psychology, who point to the fact that our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal numbers. \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Transition function: P(s’|s,a)\nFinite Horizon: A finite horizon means that there is a fixed time N after which nothing matters—the game is over, so to speak.\n So, with a finite horizon, an optimal action in a given state may depend on how much time is left. A policy that depends on the time is called nonstationary.\nInfinite Horizon  -> stationary\nReasons why additive discounted rewards make sense:\n> empirical, rewards sooner than later.\n> economical (monetary). Discount factor of gamma → interest rate of (1/gamma) - 1\n> A third reason is uncertainty about the true rewards.\n> natural property of preferences over histories.\n> conveniently makes some nasty infinities go away.\n \nA policy that is guaranteed to reach a terminal state is called a proper policy.\nExpected Utility:\n\n\nBellman’s equation:\n\n\nAnother important quantity is the action-utility function, or Q-function.\n\n\nSo adding a potential-based reward to any other reward shouldn’t change the optimal policy.\nBayesian networks with decision, reward, and utility nodes to create dynamic decision networks, or DDNs. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nValue Iteration Algorithm:\nSolved using Bellman update:\n\nWe can think of the value iteration algorithm as propagating information through the state space by means of local updates.\nWhy do Values converge?\n> A contraction is a function of one argument that, when applied to two different inputs in turn, produces two output values that are “closer together,” by at least some constant factor, than the original inputs.\n> We measure distance between utilities using MAX NORM.\n> the Bellman update is a contraction by a factor of gamma on the space of utility vectors. \n> error is reduced by the factor of gamma in each iteration\nNo of iterations needed to converge:\n\nPolicy loss: is the most the agent can lose by executing  πi  instead of the optimal policy  π∗\nI.e \n \n \nPOLICY ITERATION:\nPOLICY EVALUATION: given a policy πi, calculate Ui=Uπi, the utility of each state if πi were to be executed.\nPOLICY IMPROVEMENT: Calculate a new MEU policy πi+1, using one-step look-ahead based on Ui \n \nHow do we implement Policy-Evaluation? It turns out that doing so is simpler than solving the standard Bellman equations (which is what value iteration does) because the action in each state is fixed by the policy. \n\nTime complexity = O(n^3)\n \nModified Policy Iteration: For larger states, to reduce time complexity\n> It turns out that doing so is simpler than solving the standard Bellman equations (which is what value iteration does), because the action in each state is fixed by the policy. \n\nThe algorithms we have described so far require updating the utility or policy for all states at once. It turns out that this is not strictly necessary. In fact, on each iteration, we can pick any subset of states and apply either kind of updating (policy improvement or simplified value iteration) to that subset. This very general algorithm is called asynchronous policy iteration.\n \nLinear Programming:\nLinear programming or LP is a general approach for formulating constrained optimization problems, and there are many industrial-strength LP solvers available\n\nOnline Algorithms for MDP:\n \n\n## Module 8 Lecture Notes\n > Navigating the Asteroid world: transition model is stochastic.\n> Transition function: T(s’,a,s) =  p(s’|s,a) (markovian, instead of having a successor of the state)\n> Reward function - utility or reward function for the agent. \n> Rewards can be positive/negative but bounded by max value. \n> As decision process is sequential, utility function is specified on sequence of states and actions: R(s’,a,s).\n > A Markov decision process or MDP is \n• a sequential decision problem \n• for a fully observable environment \n• with a stochastic transition model \n• that has additive rewards MDPs are non-deterministic search problems. One way of solving them is via expectimax search. \n \nMDP formulation: set of states, set of actions, transition function, reward function, the initial state, optionally one or more terminal states.\n \nSolution to MDP is a policy. A policy maps from a state onto the action to take if the agent is in that state. Because you might end up in a state you didn’t expect to, hence every state needs to be mapped to an action.\n \nEven if the same policy is executed multiple times by the agent, this may lead to a different sequence of states and actions (environment history), and thus a different score under the reward function. Therefore we need to compute the expected utility of all the possible paths generated by a policy. Depends highly on the reward of each state.\n \nThe performance of an agent in an MDP is the sum of the rewards for the transitions it takes.\n \nUtility of Sequences: if each sequence has different rewards -> maximize the reward, get reward now than later because of stochasticity.\n \nStationary Preferences:\n\n \n\nInfinite Utilities?!\n▪Problem: What if the game lasts forever? Do we get infinite rewards?\n▪Solutions:\n▪ Finite horizon: (similar to depth-limited search)\n▪ Terminate episodes after a fixed T steps (e.g. life)\n▪ Gives nonstationary policies ( depends on time left)\n▪ Discounting: use 0 <gamma < 1\n▪ Smaller gamma means smaller “horizon” – shorter term focus\n▪ Absorbing state: guarantee that for every policy, a terminal state will eventually be reached (like “overheated” for racing)\nOptimal Quantities\n▪ The value (utility) of a state s: V * (s) = expected utility starting in s and acting optimally \n▪ The value (utility) of a q-state (s,a): Q* (s,a) = expected utility starting out having taken action a from state s and (thereafter) acting optimally \n▪ The optimal policy:  pi* (s) = optimal action from state s\n\nValue Iteration: complexity is O(a*s^2)\nPolicy Evaluation: no best policy given, just follow pi blindly: O(s^2)\n\nOptimal policy, policy extraction:\n\n \nHow V under policy looks like:\n\nHow Q looks like:\n\n\n \nPolicy Iteration Algorithm:\nTo tackle problems with Value Iteration -> \nValue iteration repeats bellman updates and it’s slow. The max at each state barely changes, only value changes. Therefore, value convergence happens way after action (policy) convergence.\nPolicy Iteration algo:\nAlternative approach for optimal values:\n• Step 1: Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n• Step 2: Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future values\n• Step 3: Repeat steps until policy converges!\n• It’s still optimal!\n• Can converge (much) faster under some conditions\n \nUTILITIES:\nA rational agent should choose the action that maximizes its expected utility, given its knowledge.\nFor worst case minimax reasoning, insensitivity to monotonic functions: max doesn't change with, example, x to x^2, decision remains the same.\nBut for, average case expectimax, we need magnitudes to be meaningful.\nUtilities are functions from outcomes (states of the world) to real numbers that describe an agent’s preferences.\n \n\n \n\n \nUtility Scales\n▪ Normalized utilities: u+ = 1.0, u- = 0.0\n▪ Micromorts: one-millionth chance of death, useful for paying to reduce product risks, etc.\n▪ QALYs: quality-adjusted life years, useful for medical decisions involving substantial risk\n▪ Note: behavior is invariant under positive linear transformation\n▪ With deterministic prizes only (no lottery choices), only ordinal utility can be determined, i.e., total order on prizes\n \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Bandit Problems Definition:\n",
        "> Each arm Mi is a Markov reward process or MRP, that is, an MDP with only one possible action Ai It has states Si, transition model Pi(s′|s,ai), and reward Ri(s,ai,s′).The arm defines a distribution over sequences of rewards Ri,0,Ri,1,Ri,2,…, where each Ri,t is a random variable.\n",
        "> The overall bandit problem is an MDP: the state space is given by the Cartesian product S=S1×⋯×Sn; the actions are a1,…,an; the transition model updates the state of whichever arm Mi is selected, according to its specific transition model, leaving the other arms unchanged; and the discount factor is γ.\n",
        "2 armed bandits - one has same rewards each time, other has arbitrary sequence of rewards. You have to switch between the two at the right time.\n",
        "With just one arm, the only choice is whether to pull again or to stop. If you pull the first arm T times (i.e., at times 0,1,…,T−1 we say that the stopping time is T.\n",
        "\n",
        "The value defined above is known as the gittins index of M. ​​The remarkable thing about the Gittins index is that it provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins indices.Reduces time complexity from O(n) to O(1)\n",
        "The Gittins index is a measure of the reward that can be achieved through a given stochastic process with certain properties, namely: the process has an ultimate termination state and evolves with an option, at each intermediate state, of terminating.\n",
        "\n",
        "\n",
        "\n",
        "Perhaps the simplest and best-known instance of a bandit problem is the Bernoulli bandit, where each arm Mi produces a reward of 0 or 1 with a fixed but unknown probability \n",
        "μi.  We assign exploration bonuses to states which are rarely visited.\n",
        "\n",
        "Approximately optimal bandit policies: The basic idea is to use the samples from each arm to establish a confidence interval for the value of the arm, that is, a range within which the value can be estimated to lie with high confidence. then choose the arm with the highest upper bound on its confidence interval. A UCB policy simply picks the arm with the highest UCB value.\n",
        "\n",
        "A second method, Thompson sampling, chooses an arm randomly according to the probability that the arm is in fact optimal, given the samples so far.\n",
        "\n",
        "The task of choosing the best option under these conditions is called a selection problem.\n",
        "\n",
        "The concept of metalevel decision problems such as deciding what computations to make during a game-tree search prior to making a move.\n",
        "\n",
        "An important generalization of the bandit process is the bandit superprocess or BSP, in which each arm is a full Markov decision process in its own right, rather than being a Markov reward process with only one possible action.\n",
        "\n",
        "interaction can be modeled by the notion of opportunity cost: how much utility is given up per time step by not devoting that time step to another arm. \n",
        "Dominating policy: which thus gives an upper bound on the value of acting in the arm.\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Sparse rewards: —the win/loss rewards for chess and racing - only allotted at end of game.\n",
        "Model Based (MDPs and Dynamic Programming) - explicitly learning p(s’|s,a) and r(s’|s,a), they learn a utility function.\n",
        "Model free (Q learning - Action-utility learning and SARSA - passive reinforcement learning, POLICY SEARCH: The agent learns a policy  that maps directly from states to actions. This is a reflex agent! \"\"\"\n",
        "chapter22_2 =  \"\"\" Agent doesn't know P or R.\n",
        "Direct Utility Estimation: utility of a state is defined as the expected total reward from that state onward.\n",
        "Adaptive dynamic programming (ADP): fix the policy, apply bellman equation, solve using Linear Algebra\n",
        "Modified policy iteration: using a simplified value iteration process to update the utility estimates after each change to the learned model. Because the model usually changes only slightly with each observation, the value iteration process can use the previous utility estimates as initial values and typically converge very quickly.\n",
        "Temporal Difference Learning:\n",
        "\n",
        "> Pseudo experience:  extend the TD approach to use a transition model to generate several pseudoexperiences—transitions that the TD agent can imagine might happen, given its current model. For each observed transition, the TD agent can generate a large number of imaginary transitions. In this way, the resulting utility estimates will approximate more and more closely those of ADP—of course, at the expense of increased computation time.\n",
        "> The prioritized sweeping heuristic prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n",
        " \"\"\"\n",
        "chapter22_3 =  \"\"\" An active learning agent gets to decide what actions to take.\n",
        "Greedy Agent:  because it greedily takes the action that it currently believes to be optimal at each step.\n",
        "GLIE: greedy in the limit of infinite exploration.\n",
        "Safe Exploration Techniques:\n",
        "> Bayesian reinforcement learning, assumes a prior probability P(h) over hypotheses h about what the true model is; the posterior probability P(h|e) is obtained in the usual way by Bayes’ rule given the observations to date.\n",
        "> exploration POMDP whose belief states are distributions over models. In principle, this exploration POMDP can be formulated and solved before the agent ever sets foot in the world.\n",
        "> The robust control approach can be considered as a game between the agent and an adversary, where the adversary gets to pick the worst possible result for any action, and the policy we get is the minimax solution for the game.\n",
        "Temporal difference Q learning: SARSA (on policy), Q learning (off policy)\n",
        " \"\"\"\n",
        "chapter22_4 =  \"\"\" Reinforcement Learning - learn the probability distribution, Q learning.\n",
        "Model-Based Idea:\n",
        "Learn an approximate model based on experiences\n",
        "Solve for values as if the learned model were correct\n",
        "Step 1: Learn empirical MDP model\n",
        "Count outcomes s’ for each T(s, a,s’)\n",
        "Normalize to give an estimate of\n",
        "Discover each when we experience R(s, a, s’)\n",
        "Step 2: Solve the learned MDP\n",
        "For example, use value iteration, as before.\n",
        " \n",
        "Model Free Idea:\n",
        "No track of transition learning\n",
        "Passive Reinforcement: someone else chooses the policy for us.\n",
        "Simplified task: policy evaluation\n",
        "Input: a fixed policy π(s)\n",
        "You don’t know the transitions T(s,a,s’)\n",
        "You don’t know the rewards R(s,a,s’)\n",
        "Goal: learn the state values\n",
        "Direct Evaluation: Taking average from particular states\n",
        "What’s good about direct evaluation?\n",
        "> It’s easy to understand\n",
        "> It doesn’t require any knowledge of T, R\n",
        "> It eventually computes the correct average values, using just sample transitions\n",
        "What's bad about it?\n",
        "> It wastes information about state connections\n",
        "> Each state must be learned separately\n",
        "> So, it takes a long time to learn and more number of samples\n",
        " \n",
        "Policy Evaluation: T and R needed -> Sample based Policy Evaluation -> But how to go back from terminal state to start state? Would the state be visited n times? No guarantee!\n",
        " \n",
        "Temporal Difference: Instead of update after n steps, update the values every single time, Model Free\n",
        "\n",
        "Exponential moving average ->  gives more attention to recent updates\n",
        "\n",
        "Value under policy, hence they’ll change with every policy.\n",
        "Therefore, Q value is needed.\n",
        "Q learning: Off policy learning - even though you are acting sub optimally, you converge to the optimal value.\n",
        "Makes action selection, model free. Online planning!\n",
        "Difference between value iteration and Q value iteration:\n",
        "\n",
        "\n",
        "Exploration vs Exploitation: epsilon greedy\n",
        "Exploration functions: \n",
        "When to explore?\n",
        "Random actions: explore a fixed amount\n",
        "Better idea: explore areas whose badness is not (yet) established, eventually stop exploring.\n",
        "Takes a value estimate u and a visit count n, and returns an optimistic utility. f(u,n) = u + k/n.\n",
        "k/n is the bonus function. n=0, k/n is high and more likely toi visit\n",
        "\n",
        " \n",
        "Approximate Q learning:\n",
        "Instead of having to learn state every state, generalize about similar states\n",
        "Linear Value function:\n",
        " \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\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",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f248f0b0-990c-44d0-a3a4-4171fcffd91a"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Bandit Problems Definition:\n> Each arm Mi is a Markov reward process or MRP, that is, an MDP with only one possible action Ai It has states Si, transition model Pi(s′|s,ai), and reward Ri(s,ai,s′).The arm defines a distribution over sequences of rewards Ri,0,Ri,1,Ri,2,…, where each Ri,t is a random variable.\n> The overall bandit problem is an MDP: the state space is given by the Cartesian product S=S1×⋯×Sn; the actions are a1,…,an; the transition model updates the state of whichever arm Mi is selected, according to its specific transition model, leaving the other arms unchanged; and the discount factor is γ.\n2 armed bandits - one has same rewards each time, other has arbitrary sequence of rewards. You have to switch between the two at the right time.\nWith just one arm, the only choice is whether to pull again or to stop. If you pull the first arm T times (i.e., at times 0,1,…,T−1 we say that the stopping time is T.\n\nThe value defined above is known as the gittins index of M. ​​The remarkable thing about the Gittins index is that it provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins indices.Reduces time complexity from O(n) to O(1)\nThe Gittins index is a measure of the reward that can be achieved through a given stochastic process with certain properties, namely: the process has an ultimate termination state and evolves with an option, at each intermediate state, of terminating.\n\n\n\nPerhaps the simplest and best-known instance of a bandit problem is the Bernoulli bandit, where each arm Mi produces a reward of 0 or 1 with a fixed but unknown probability \nμi.  We assign exploration bonuses to states which are rarely visited.\n\nApproximately optimal bandit policies: The basic idea is to use the samples from each arm to establish a confidence interval for the value of the arm, that is, a range within which the value can be estimated to lie with high confidence. then choose the arm with the highest upper bound on its confidence interval. A UCB policy simply picks the arm with the highest UCB value.\n\nA second method, Thompson sampling, chooses an arm randomly according to the probability that the arm is in fact optimal, given the samples so far.\n\nThe task of choosing the best option under these conditions is called a selection problem.\n\nThe concept of metalevel decision problems such as deciding what computations to make during a game-tree search prior to making a move.\n\nAn important generalization of the bandit process is the bandit superprocess or BSP, in which each arm is a full Markov decision process in its own right, rather than being a Markov reward process with only one possible action.\n\ninteraction can be modeled by the notion of opportunity cost: how much utility is given up per time step by not devoting that time step to another arm. \nDominating policy: which thus gives an upper bound on the value of acting in the arm.\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n Sparse rewards: —the win/loss rewards for chess and racing - only allotted at end of game.\nModel Based (MDPs and Dynamic Programming) - explicitly learning p(s’|s,a) and r(s’|s,a), they learn a utility function.\nModel free (Q learning - Action-utility learning and SARSA - passive reinforcement learning, POLICY SEARCH: The agent learns a policy  that maps directly from states to actions. This is a reflex agent! \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Agent doesn't know P or R.\nDirect Utility Estimation: utility of a state is defined as the expected total reward from that state onward.\nAdaptive dynamic programming (ADP): fix the policy, apply bellman equation, solve using Linear Algebra\nModified policy iteration: using a simplified value iteration process to update the utility estimates after each change to the learned model. Because the model usually changes only slightly with each observation, the value iteration process can use the previous utility estimates as initial values and typically converge very quickly.\nTemporal Difference Learning:\n\n> Pseudo experience:  extend the TD approach to use a transition model to generate several pseudoexperiences—transitions that the TD agent can imagine might happen, given its current model. For each observed transition, the TD agent can generate a large number of imaginary transitions. In this way, the resulting utility estimates will approximate more and more closely those of ADP—of course, at the expense of increased computation time.\n> The prioritized sweeping heuristic prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n An active learning agent gets to decide what actions to take.\nGreedy Agent:  because it greedily takes the action that it currently believes to be optimal at each step.\nGLIE: greedy in the limit of infinite exploration.\nSafe Exploration Techniques:\n> Bayesian reinforcement learning, assumes a prior probability P(h) over hypotheses h about what the true model is; the posterior probability P(h|e) is obtained in the usual way by Bayes’ rule given the observations to date.\n> exploration POMDP whose belief states are distributions over models. In principle, this exploration POMDP can be formulated and solved before the agent ever sets foot in the world.\n> The robust control approach can be considered as a game between the agent and an adversary, where the adversary gets to pick the worst possible result for any action, and the policy we get is the minimax solution for the game.\nTemporal difference Q learning: SARSA (on policy), Q learning (off policy)\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Reinforcement Learning - learn the probability distribution, Q learning.\nModel-Based Idea:\nLearn an approximate model based on experiences\nSolve for values as if the learned model were correct\nStep 1: Learn empirical MDP model\nCount outcomes s’ for each T(s, a,s’)\nNormalize to give an estimate of\nDiscover each when we experience R(s, a, s’)\nStep 2: Solve the learned MDP\nFor example, use value iteration, as before.\n \nModel Free Idea:\nNo track of transition learning\nPassive Reinforcement: someone else chooses the policy for us.\nSimplified task: policy evaluation\nInput: a fixed policy π(s)\nYou don’t know the transitions T(s,a,s’)\nYou don’t know the rewards R(s,a,s’)\nGoal: learn the state values\nDirect Evaluation: Taking average from particular states\nWhat’s good about direct evaluation?\n> It’s easy to understand\n> It doesn’t require any knowledge of T, R\n> It eventually computes the correct average values, using just sample transitions\nWhat's bad about it?\n> It wastes information about state connections\n> Each state must be learned separately\n> So, it takes a long time to learn and more number of samples\n \nPolicy Evaluation: T and R needed -> Sample based Policy Evaluation -> But how to go back from terminal state to start state? Would the state be visited n times? No guarantee!\n \nTemporal Difference: Instead of update after n steps, update the values every single time, Model Free\n\nExponential moving average ->  gives more attention to recent updates\n\nValue under policy, hence they’ll change with every policy.\nTherefore, Q value is needed.\nQ learning: Off policy learning - even though you are acting sub optimally, you converge to the optimal value.\nMakes action selection, model free. Online planning!\nDifference between value iteration and Q value iteration:\n\n\nExploration vs Exploitation: epsilon greedy\nExploration functions: \nWhen to explore?\nRandom actions: explore a fixed amount\nBetter idea: explore areas whose badness is not (yet) established, eventually stop exploring.\nTakes a value estimate u and a visit count n, and returns an optimistic utility. f(u,n) = u + k/n.\nk/n is the bonus function. n=0, k/n is high and more likely toi visit\n\n \nApproximate Q learning:\nInstead of having to learn state every state, generalize about similar states\nLinear Value function:\n \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" The best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation.\n",
        "An intrinsic evaluation metric is one that measures the quality of a model independent of any application.\n",
        "In practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (PP) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. \n",
        "\n",
        "Thus, minimizing perplexity is equivalent to maximizing the test set probability according to the language model.As we see above, the more information the n-gram gives us about the word sequence, the lower the perplexity. (perplexity is related inversely to the likelihood of the test sequence according to the model).\n",
        " \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" One important way to visualize what kind of knowledge a language model embodies is to sample from it. Sampling from a distribution means to choose random points according to their likelihood.We choose a random value between 0 and 1, find that point on the probability line, and print the word whose interval includes this chosen value. We continue choosing random numbers and generating words until we randomly generate the sentence-final token . \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" The n-gram model, like many statistical models, is dependent on the training corpus. One implication of this is that the probabilities often encode specific facts about a given training corpus. Another implication is that n-grams do a better and better job of modeling the training corpus as we increase the value of N.\n",
        "One step is to be sure to use a training corpus that has a similar genre to whatever task we are trying to accomplish. To build a language model for translating legal documents, we need a training corpus of legal documents. To build a language model for a question-answering system, we need a training corpus of questions. It is equally important to get training data in the appropriate dialect or variety, especially when processing social media posts or spoken transcripts.\n",
        "Matching genres and dialects is still not sufficient. Our models may still be subject to the problem of sparsity. \n",
        "Dealing with OOV:\n",
        "1. Choose a vocabulary (word list) that is fixed in advance. \n",
        "2. Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step. \n",
        "3. Estimate the probabilities from its counts just like any other regular word in the training set.\n",
        " \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" The simplest way to do smoothing is to add one to all the n-gram counts, before we normalize them into probabilities. All the counts that used to be zero will now have a count of 1, the counts of 1 will be 2, and so on. This algorithm is called Laplace smoothing. \n",
        "A related way to view smoothing is as discounting (lowering) some non-zero counts in order to get the probability mass that will be assigned to the zero counts. Thus, instead of referring to the discounted counts c* , we might describe a smoothing algorithm in terms of a relative discount dc, the ratio of the discounted counts to the original counts: dc = c*/c.\n",
        "K smoothing: adding k(0.5,0.25 etc) instead of 1.\n",
        " \n",
        "In other words, sometimes using less context is a good thing, helping to generalize more for contexts that the model hasn’t learned much about. There are two ways backoff to use this n-gram “hierarchy”. In backoff, we use the trigram if the evidence is sufficient, otherwise we use the bigram, otherwise the unigram. In other words, we only “back off” to a lower-order n-gram if we have zero evidence for a higher-order interpolation n-gram. By contrast, in interpolation, we always mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram, and unigram counts.\n",
        "Interpolation:\n",
        "\n",
        "Lambda, a hyperparameter can be set by cross validation, validation set or use EM.\n",
        "Katz Backoff: In order for a backoff model to give a correct probability distribution, we have to discount the higher-order n-grams to save some probability mass for the lower order n-grams.\n",
        "Katz backoff is often combined with a smoothing method called Good-Turing. The combined Good-Turing backoff algorithm involves quite detailed computation for estimating the Good-Turing smoothing and the P ∗ and α values. \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" An n-gram language model can also be shrunk by pruning, for example only storing n-grams with counts greater than some threshold or using entropy to prune less-important n-grams. Another option is to build approximate language models using techniques like Bloom filters.\n",
        "Stupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. If a higher-order n-gram has a zero count, we simply backoff to a lower order n-gram, weighted by a fixed (context-independent) weight. This algorithm does not produce a probability distribution. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" > Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms).\n",
        "> Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present).\n",
        "> Model: Agent knows something about how the known variables relate to the unknown variables.\n",
        "> A random variable is some aspect of the world about which we (may) have uncertainty.\n",
        "> Chain Rule:\n",
        "\n",
        "One goal: assign a probability to a sentence:\n",
        "• Autocomplete for texting\n",
        "• Machine Translation\n",
        "• Spelling Correction\n",
        "• Speech Recognition\n",
        "MLE estimate of the next word: just count and divide!\n",
        "Simplifying Assumption = Markov Assumption!\n",
        "Bigram:   ; \n",
        "MLE problems: \n",
        "> We do everything in log space, Avoid underflow, (also adding is faster than multiplying)\n",
        "> Out of vocabulary items (OOV), <unk> to deal with OOVs, Normalize training data by replacing any word not in L with <unk>, Avoid zeros with smoothing\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "142134d7-213c-4afd-84d7-e08dc392c0f3"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n The best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation.\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application.\nIn practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (PP) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. \n\nThus, minimizing perplexity is equivalent to maximizing the test set probability according to the language model.As we see above, the more information the n-gram gives us about the word sequence, the lower the perplexity. (perplexity is related inversely to the likelihood of the test sequence according to the model).\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n One important way to visualize what kind of knowledge a language model embodies is to sample from it. Sampling from a distribution means to choose random points according to their likelihood.We choose a random value between 0 and 1, find that point on the probability line, and print the word whose interval includes this chosen value. We continue choosing random numbers and generating words until we randomly generate the sentence-final token . \n\n## SLP Chapter 3.4 Generalization and Zeros\n The n-gram model, like many statistical models, is dependent on the training corpus. One implication of this is that the probabilities often encode specific facts about a given training corpus. Another implication is that n-grams do a better and better job of modeling the training corpus as we increase the value of N.\nOne step is to be sure to use a training corpus that has a similar genre to whatever task we are trying to accomplish. To build a language model for translating legal documents, we need a training corpus of legal documents. To build a language model for a question-answering system, we need a training corpus of questions. It is equally important to get training data in the appropriate dialect or variety, especially when processing social media posts or spoken transcripts.\nMatching genres and dialects is still not sufficient. Our models may still be subject to the problem of sparsity. \nDealing with OOV:\n1. Choose a vocabulary (word list) that is fixed in advance. \n2. Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step. \n3. Estimate the probabilities from its counts just like any other regular word in the training set.\n \n\n## SLP Chapter 3.5 Smoothing\n The simplest way to do smoothing is to add one to all the n-gram counts, before we normalize them into probabilities. All the counts that used to be zero will now have a count of 1, the counts of 1 will be 2, and so on. This algorithm is called Laplace smoothing. \nA related way to view smoothing is as discounting (lowering) some non-zero counts in order to get the probability mass that will be assigned to the zero counts. Thus, instead of referring to the discounted counts c* , we might describe a smoothing algorithm in terms of a relative discount dc, the ratio of the discounted counts to the original counts: dc = c*/c.\nK smoothing: adding k(0.5,0.25 etc) instead of 1.\n \nIn other words, sometimes using less context is a good thing, helping to generalize more for contexts that the model hasn’t learned much about. There are two ways backoff to use this n-gram “hierarchy”. In backoff, we use the trigram if the evidence is sufficient, otherwise we use the bigram, otherwise the unigram. In other words, we only “back off” to a lower-order n-gram if we have zero evidence for a higher-order interpolation n-gram. By contrast, in interpolation, we always mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram, and unigram counts.\nInterpolation:\n\nLambda, a hyperparameter can be set by cross validation, validation set or use EM.\nKatz Backoff: In order for a backoff model to give a correct probability distribution, we have to discount the higher-order n-grams to save some probability mass for the lower order n-grams.\nKatz backoff is often combined with a smoothing method called Good-Turing. The combined Good-Turing backoff algorithm involves quite detailed computation for estimating the Good-Turing smoothing and the P ∗ and α values. \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n An n-gram language model can also be shrunk by pruning, for example only storing n-grams with counts greater than some threshold or using entropy to prune less-important n-grams. Another option is to build approximate language models using techniques like Bloom filters.\nStupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. If a higher-order n-gram has a zero count, we simply backoff to a lower order n-gram, weighted by a fixed (context-independent) weight. This algorithm does not produce a probability distribution. \n\n## Module 10 Lecture Notes\n > Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms).\n> Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present).\n> Model: Agent knows something about how the known variables relate to the unknown variables.\n> A random variable is some aspect of the world about which we (may) have uncertainty.\n> Chain Rule:\n\nOne goal: assign a probability to a sentence:\n• Autocomplete for texting\n• Machine Translation\n• Spelling Correction\n• Speech Recognition\nMLE estimate of the next word: just count and divide!\nSimplifying Assumption = Markov Assumption!\nBigram:   ; \nMLE problems: \n> We do everything in log space, Avoid underflow, (also adding is faster than multiplying)\n> Out of vocabulary items (OOV), <unk> to deal with OOVs, Normalize training data by replacing any word not in L with <unk>, Avoid zeros with smoothing\n \n \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" The compactness of Bayesian networks is an example of a general property of locally structured (also called sparse) systems. In a locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity.\n",
        "Each variable is conditionally independent of its non-descendants, given its parents.\n",
        "A variable is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket.\n",
        "\n",
        "Bayes’ Net for Continuous variables: One way to handle continuous variables is with discretization—that is, dividing up the possible values into a fixed set of intervals.\n",
        "Yet another solution—sometimes called a nonparametric representation—is to define the conditional distribution implicitly with a collection of instances, each containing specific values of the parent and child variables. Example - Gaussian.\n",
        "A network with both discrete and continuous variables is called a hybrid Bayesian network:\n",
        "> probit: (probability unit model) uses conditional gaussian distribution model.\n",
        "> expit or inverse logit: It uses logistic function\n",
        " \"\"\"\n",
        "chapter13_3 = \"\"\" The basic task for any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event—usually, some assignment of values to a set of evidence variables.\n",
        "X denotes the query variable; E denotes the set of evidence variables E1,…,Em, and e is a particular observed event; Y denotes the hidden (nonevidence, nonquery) variables Y1,…,Yℓ. Thus, the complete set of variables is {X}∪E∪Y. A typical query asks for the posterior probability distribution P(X|e).\n",
        "Inference by Enumeration: O(n*2^n)\n",
        "\n",
        "This can be reduced to O(2^n) by taking advantage of the nested structure of the computation. In symbolic terms, this means moving the summations inwards as far as possible in expressions.\n",
        " to \n",
        "Variable Elimination:\n",
        "This is a form of dynamic programming. \n",
        "Evaluating expressions right to left i.e bottom-up.\n",
        "Each factor is a matrix indexed by the values of its argument variables.\n",
        "Pointwise product operation: \n",
        "\n",
        "Complexity of Exact Inference: The complexity of exact inference in Bayes nets depends strongly on the structure of the network.\n",
        "There are singly connected networks or polytrees, and they have a particularly nice property: The time and space complexity of exact inference in polytrees is linear in the size of the network.\n",
        "For multi connected - exponential time complexity. NP Hard problem.\n",
        "Satisfiability (often abbreviated SAT) is the problem of determining whether there exists an interpretation that satisfies the formula. In other words, it establishes whether the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to true.\n",
        "Measures such as tree width, which bound the complexity of solving a CSP, can also be applied directly to Bayes nets. Moreover, the variable elimination algorithm can be generalized to solve CSPs as well as Bayes nets.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Evidence variable can block paths in causal chains:\n",
        "Conditionally independent if no active path between them (d- separation algo).\n",
        "Inference: calculating some useful quantity from a joint probability distribution.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 806
        },
        "cellView": "form",
        "outputId": "dab80139-d74e-407c-ea17-1afffa588ca7"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The compactness of Bayesian networks is an example of a general property of locally structured (also called sparse) systems. In a locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity.\nEach variable is conditionally independent of its non-descendants, given its parents.\nA variable is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket.\n\nBayes’ Net for Continuous variables: One way to handle continuous variables is with discretization—that is, dividing up the possible values into a fixed set of intervals.\nYet another solution—sometimes called a nonparametric representation—is to define the conditional distribution implicitly with a collection of instances, each containing specific values of the parent and child variables. Example - Gaussian.\nA network with both discrete and continuous variables is called a hybrid Bayesian network:\n> probit: (probability unit model) uses conditional gaussian distribution model.\n> expit or inverse logit: It uses logistic function\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n The basic task for any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event—usually, some assignment of values to a set of evidence variables.\nX denotes the query variable; E denotes the set of evidence variables E1,…,Em, and e is a particular observed event; Y denotes the hidden (nonevidence, nonquery) variables Y1,…,Yℓ. Thus, the complete set of variables is {X}∪E∪Y. A typical query asks for the posterior probability distribution P(X|e).\nInference by Enumeration: O(n*2^n)\n\nThis can be reduced to O(2^n) by taking advantage of the nested structure of the computation. In symbolic terms, this means moving the summations inwards as far as possible in expressions.\n to \nVariable Elimination:\nThis is a form of dynamic programming. \nEvaluating expressions right to left i.e bottom-up.\nEach factor is a matrix indexed by the values of its argument variables.\nPointwise product operation: \n\nComplexity of Exact Inference: The complexity of exact inference in Bayes nets depends strongly on the structure of the network.\nThere are singly connected networks or polytrees, and they have a particularly nice property: The time and space complexity of exact inference in polytrees is linear in the size of the network.\nFor multi connected - exponential time complexity. NP Hard problem.\nSatisfiability (often abbreviated SAT) is the problem of determining whether there exists an interpretation that satisfies the formula. In other words, it establishes whether the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to true.\nMeasures such as tree width, which bound the complexity of solving a CSP, can also be applied directly to Bayes nets. Moreover, the variable elimination algorithm can be generalized to solve CSPs as well as Bayes nets.\n \n\n## Module 11 Lecture Notes\n Evidence variable can block paths in causal chains:\nConditionally independent if no active path between them (d- separation algo).\nInference: calculating some useful quantity from a joint probability distribution.\n \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" With alternative vocabulary, we can say that h is a model of the data, drawn from a model class H, or we can say a function drawn from a function class. We call the output yi as the ground truth—the true answer we are asking our model to predict.\n",
        "Hypothesis space -> prior knowledge.\n",
        "By bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space. \"\"\"\n",
        "chapter19_3 = \"\"\" The decision tree learning algorithm chooses the attribute with the highest Importance. We will now show how to measure importance, using the notion of information gain, which is defined in terms of entropy.\n",
        "Entropy is a measure of the uncertainty of a random variable; the more information, the less entropy. A random variable with only one possible value—a coin that always comes up heads—has no uncertainty and thus its entropy is defined as zero.\n",
        " \"\"\"\n",
        "chapter19_4 = \"\"\" We say that a model that exactly fits all the training data has interpolated the data. Model classes typically start to overfit as the capacity approaches the point of interpolation. \"\"\"\n",
        "chapter19_5 = \"\"\" Thus, any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC). ​​Any learning algorithm that returns hypotheses that are probably approximately correct is called a PAC learning algorithm; we can use this approach to provide bounds on the performance of various learning algorithms.\n",
        "One can think of an approximately correct hypothesis as being “close” to the true function in hypothesis space: it lies inside what is called the ϵ-ball around the true function f. The hypothesis space outside this ball is called Hbad.\n",
        "\n",
        "Decision lists resemble decision trees, but their overall structure is simpler: they branch only in one direction.\n",
        "On the other hand, if we restrict the size of each test to at most k literals, then it is possible for the learning algorithm to generalize successfully from a small number of examples. We use the notation k -DL for a decision list with up to k conjunctions.\n",
        " \"\"\"\n",
        "chapter19_6 = \"\"\" The solution for such unknown words is to ignore them—remove them from the test\n",
        "document and not include any probability for them at all.\n",
        "Stop words: the, a \"\"\"\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 = \"\"\" Naïve Bayes: Assume all features are independent effects of the label\n",
        "\n",
        "Changes complexity from |Y|*|F|^n to n*|Y|*|F|.\n",
        "Total number of parameters are linear in terms of features.\n",
        "Start with a bunch of probabilities: P(Y) and the P(Fi|Y) tables. Use standard inference to compute P(Y|F1…Fn).\n",
        "Estimates of local conditional probability tables:\n",
        "• P(Y), the prior over labels\n",
        "• P(Fi|Y) for each feature (evidence variable)\n",
        "• These probabilities are collectively called the parameters of the model and denoted by theta\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "421f4e6e-1de7-43f1-9b0e-c5dd50f0bf03"
      },
      "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": 11,
      "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 With alternative vocabulary, we can say that h is a model of the data, drawn from a model class H, or we can say a function drawn from a function class. We call the output yi as the ground truth—the true answer we are asking our model to predict.\nHypothesis space -> prior knowledge.\nBy bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n The decision tree learning algorithm chooses the attribute with the highest Importance. We will now show how to measure importance, using the notion of information gain, which is defined in terms of entropy.\nEntropy is a measure of the uncertainty of a random variable; the more information, the less entropy. A random variable with only one possible value—a coin that always comes up heads—has no uncertainty and thus its entropy is defined as zero.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n We say that a model that exactly fits all the training data has interpolated the data. Model classes typically start to overfit as the capacity approaches the point of interpolation. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Thus, any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC). ​​Any learning algorithm that returns hypotheses that are probably approximately correct is called a PAC learning algorithm; we can use this approach to provide bounds on the performance of various learning algorithms.\nOne can think of an approximately correct hypothesis as being “close” to the true function in hypothesis space: it lies inside what is called the ϵ-ball around the true function f. The hypothesis space outside this ball is called Hbad.\n\nDecision lists resemble decision trees, but their overall structure is simpler: they branch only in one direction.\nOn the other hand, if we restrict the size of each test to at most k literals, then it is possible for the learning algorithm to generalize successfully from a small number of examples. We use the notation k -DL for a decision list with up to k conjunctions.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n The solution for such unknown words is to ignore them—remove them from the test\ndocument and not include any probability for them at all.\nStop words: the, a \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 Naïve Bayes: Assume all features are independent effects of the label\n\nChanges complexity from |Y|*|F|^n to n*|Y|*|F|.\nTotal number of parameters are linear in terms of features.\nStart with a bunch of probabilities: P(Y) and the P(Fi|Y) tables. Use standard inference to compute P(Y|F1…Fn).\nEstimates of local conditional probability tables:\n• P(Y), the prior over labels\n• P(Fi|Y) for each feature (evidence variable)\n• These probabilities are collectively called the parameters of the model and denoted by theta\n \n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" The input to the neural network is a k-gram of words w1:k.\n",
        "The output is a probability distribution over the next word.\n",
        "The k context words are treated as a word window. Each word is associated with an\n",
        "embedding vector.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "696ddb5d-80ee-48a9-a144-96583d5db1d0"
      },
      "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": 21,
      "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 The input to the neural network is a k-gram of words w1:k.\nThe output is a probability distribution over the next word.\nThe k context words are treated as a word window. Each word is associated with an\nembedding vector.\n \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" In this section we introduce one method for computing embeddings: skip-gram with negative sampling, sometimes called SGNS. The skip-gram algorithm is one word2vec of two algorithms in a software package called word2vec, and so sometimes the algorithm is loosely referred to as word2vec.\n",
        "Skip gram: 4- context words: +--2\n",
        "There are many kinds of static embeddings. An extension of word2vec, fasttext addresses a problem with word2vec as we have presented it so far: it has no good way to deal with unknown words — words that appear in a test corpus but were unseen in the training corpus.\n",
        "Fasttext deals with these problems by using subword models, representing each word as itself plus a bag of constituent n-grams, with special boundary symbols < and > added to each word. For example, n = 3 the word where would be represented by the sequence plus the character n-grams: <wh, whe, her, ere, re>\n",
        "Two words have first-order co-occurrence (sometimes called syntagmatic association) if they are typically nearby each other. Thus wrote is a first-order associate of book or poem. Two words have second-order co-occurrence (sometimes called paradigmatic association) if they have similar neighbors. Thus wrote is a second-order associate of words like said or remarked.  \"\"\"\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": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5110ef46-25e8-4443-baf0-c9dde16e5c68"
      },
      "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": 18,
      "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 In this section we introduce one method for computing embeddings: skip-gram with negative sampling, sometimes called SGNS. The skip-gram algorithm is one word2vec of two algorithms in a software package called word2vec, and so sometimes the algorithm is loosely referred to as word2vec.\nSkip gram: 4- context words: +--2\nThere are many kinds of static embeddings. An extension of word2vec, fasttext addresses a problem with word2vec as we have presented it so far: it has no good way to deal with unknown words — words that appear in a test corpus but were unseen in the training corpus.\nFasttext deals with these problems by using subword models, representing each word as itself plus a bag of constituent n-grams, with special boundary symbols < and > added to each word. For example, n = 3 the word where would be represented by the sequence plus the character n-grams: <wh, whe, her, ere, re>\nTwo words have first-order co-occurrence (sometimes called syntagmatic association) if they are typically nearby each other. Thus wrote is a first-order associate of book or poem. Two words have second-order co-occurrence (sometimes called paradigmatic association) if they have similar neighbors. Thus wrote is a second-order associate of words like said or remarked.  \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": "4d7ca6cc-28ae-4a0c-fc92-b45febb06536"
      },
      "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": 22,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence,EU(a), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility: argmax EU(a).\n\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments).\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nWe can think of the set of outcomes for each action as a lottery—think of each action as a ticket. A lottery L with possible outcomes S1... Sn that occur with probabilities p1...pn is written\nL = [p1,S1: p2,S2: p3,S3...pn,Sn].\nUtility function is not unique. And the numbers don’t matter, only the preference.\nAs in game-playing, in a deterministic environment, an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions map lotteries to real numbers.\nPreference elicitation: involves presenting choices to the human and using the observed preferences to pin down the underlying utility function.\n\nMeasurements of Utility:\n> One common “currency” used in medical and safety analysis is the micromort, a one in a million chance of death.\n> QALY: quality-adjusted life year. Patients are willing to accept a shorter life expectancy to avoid a disability.\nUtility of money:\nWe say that the agent exhibits a monotonic preference for more money. This does not mean that money behaves as a utility function, because it says nothing about preferences between lotteries involving money.\nExpected Monetary Value: summation of probability*utility.\npremium.\nIt is a straightforward matter to calculate the distribution of the maximum of the  estimates and hence quantify the extent of our disappointment. (This calculation is a special case of computing an order statistic, the distribution of any particular ranked element of a sample.) \n \nDecision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans—really do act.\nThe value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. \nThe difference between the EMV of a lottery and its certainty equivalent is called the insurance \nThis tendency for the estimated expected utility of the best choice to be too high is called the optimizer’s curse. Can be avoided using Bayesian Priors. (MLE and MAP).\nAmbiguity Aversion:  Most people elect the known probability rather than the unknown unknowns.\nYet another problem is that the exact wording of a decision problem can have a big impact on the agent’s choices; this is called the framing effect.\nPeople feel more comfortable making relative utility judgments rather than absolute ones. I may have little idea how much I might enjoy the various wines offered by a restaurant. The restaurant takes advantage of this by offering an expensive bottle that nobody will buy, but which serves to skew upward the customer’s estimate of the value of all wines, making a 55 dollar bottle seem like a bargain. This is called the anchoring effect.\nThe evidence for human irrationality is also questioned by researchers in the field of evolutionary psychology, who point to the fact that our brain’s decision-making mechanisms did not evolve to solve word problems with probabilities and prizes stated as decimal numbers. \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Transition function: P(s’|s,a)\nFinite Horizon: A finite horizon means that there is a fixed time N after which nothing matters—the game is over, so to speak.\n So, with a finite horizon, an optimal action in a given state may depend on how much time is left. A policy that depends on the time is called nonstationary.\nInfinite Horizon  -> stationary\nReasons why additive discounted rewards make sense:\n> empirical, rewards sooner than later.\n> economical (monetary). Discount factor of gamma → interest rate of (1/gamma) - 1\n> A third reason is uncertainty about the true rewards.\n> natural property of preferences over histories.\n> conveniently makes some nasty infinities go away.\n \nA policy that is guaranteed to reach a terminal state is called a proper policy.\nExpected Utility:\n\n\nBellman’s equation:\n\n\nAnother important quantity is the action-utility function, or Q-function.\n\n\nSo adding a potential-based reward to any other reward shouldn’t change the optimal policy.\nBayesian networks with decision, reward, and utility nodes to create dynamic decision networks, or DDNs. \n\n## AIMA Chapter 17.2 Algorithms for MDPs\nValue Iteration Algorithm:\nSolved using Bellman update:\n\nWe can think of the value iteration algorithm as propagating information through the state space by means of local updates.\nWhy do Values converge?\n> A contraction is a function of one argument that, when applied to two different inputs in turn, produces two output values that are “closer together,” by at least some constant factor, than the original inputs.\n> We measure distance between utilities using MAX NORM.\n> the Bellman update is a contraction by a factor of gamma on the space of utility vectors. \n> error is reduced by the factor of gamma in each iteration\nNo of iterations needed to converge:\n\nPolicy loss: is the most the agent can lose by executing  πi  instead of the optimal policy  π∗\nI.e \n \n \nPOLICY ITERATION:\nPOLICY EVALUATION: given a policy πi, calculate Ui=Uπi, the utility of each state if πi were to be executed.\nPOLICY IMPROVEMENT: Calculate a new MEU policy πi+1, using one-step look-ahead based on Ui \n \nHow do we implement Policy-Evaluation? It turns out that doing so is simpler than solving the standard Bellman equations (which is what value iteration does) because the action in each state is fixed by the policy. \n\nTime complexity = O(n^3)\n \nModified Policy Iteration: For larger states, to reduce time complexity\n> It turns out that doing so is simpler than solving the standard Bellman equations (which is what value iteration does), because the action in each state is fixed by the policy. \n\nThe algorithms we have described so far require updating the utility or policy for all states at once. It turns out that this is not strictly necessary. In fact, on each iteration, we can pick any subset of states and apply either kind of updating (policy improvement or simplified value iteration) to that subset. This very general algorithm is called asynchronous policy iteration.\n \nLinear Programming:\nLinear programming or LP is a general approach for formulating constrained optimization problems, and there are many industrial-strength LP solvers available\n\nOnline Algorithms for MDP:\n \n\n## Module 8 Lecture Notes\n > Navigating the Asteroid world: transition model is stochastic.\n> Transition function: T(s’,a,s) =  p(s’|s,a) (markovian, instead of having a successor of the state)\n> Reward function - utility or reward function for the agent. \n> Rewards can be positive/negative but bounded by max value. \n> As decision process is sequential, utility function is specified on sequence of states and actions: R(s’,a,s).\n > A Markov decision process or MDP is \n• a sequential decision problem \n• for a fully observable environment \n• with a stochastic transition model \n• that has additive rewards MDPs are non-deterministic search problems. One way of solving them is via expectimax search. \n \nMDP formulation: set of states, set of actions, transition function, reward function, the initial state, optionally one or more terminal states.\n \nSolution to MDP is a policy. A policy maps from a state onto the action to take if the agent is in that state. Because you might end up in a state you didn’t expect to, hence every state needs to be mapped to an action.\n \nEven if the same policy is executed multiple times by the agent, this may lead to a different sequence of states and actions (environment history), and thus a different score under the reward function. Therefore we need to compute the expected utility of all the possible paths generated by a policy. Depends highly on the reward of each state.\n \nThe performance of an agent in an MDP is the sum of the rewards for the transitions it takes.\n \nUtility of Sequences: if each sequence has different rewards -> maximize the reward, get reward now than later because of stochasticity.\n \nStationary Preferences:\n\n \n\nInfinite Utilities?!\n▪Problem: What if the game lasts forever? Do we get infinite rewards?\n▪Solutions:\n▪ Finite horizon: (similar to depth-limited search)\n▪ Terminate episodes after a fixed T steps (e.g. life)\n▪ Gives nonstationary policies ( depends on time left)\n▪ Discounting: use 0 <gamma < 1\n▪ Smaller gamma means smaller “horizon” – shorter term focus\n▪ Absorbing state: guarantee that for every policy, a terminal state will eventually be reached (like “overheated” for racing)\nOptimal Quantities\n▪ The value (utility) of a state s: V * (s) = expected utility starting in s and acting optimally \n▪ The value (utility) of a q-state (s,a): Q* (s,a) = expected utility starting out having taken action a from state s and (thereafter) acting optimally \n▪ The optimal policy:  pi* (s) = optimal action from state s\n\nValue Iteration: complexity is O(a*s^2)\nPolicy Evaluation: no best policy given, just follow pi blindly: O(s^2)\n\nOptimal policy, policy extraction:\n\n \nHow V under policy looks like:\n\nHow Q looks like:\n\n\n \nPolicy Iteration Algorithm:\nTo tackle problems with Value Iteration -> \nValue iteration repeats bellman updates and it’s slow. The max at each state barely changes, only value changes. Therefore, value convergence happens way after action (policy) convergence.\nPolicy Iteration algo:\nAlternative approach for optimal values:\n• Step 1: Policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence\n• Step 2: Policy improvement: update policy using one-step lookahead with resulting converged (but not optimal!) utilities as future values\n• Step 3: Repeat steps until policy converges!\n• It’s still optimal!\n• Can converge (much) faster under some conditions\n \nUTILITIES:\nA rational agent should choose the action that maximizes its expected utility, given its knowledge.\nFor worst case minimax reasoning, insensitivity to monotonic functions: max doesn't change with, example, x to x^2, decision remains the same.\nBut for, average case expectimax, we need magnitudes to be meaningful.\nUtilities are functions from outcomes (states of the world) to real numbers that describe an agent’s preferences.\n \n\n \n\n \nUtility Scales\n▪ Normalized utilities: u+ = 1.0, u- = 0.0\n▪ Micromorts: one-millionth chance of death, useful for paying to reduce product risks, etc.\n▪ QALYs: quality-adjusted life years, useful for medical decisions involving substantial risk\n▪ Note: behavior is invariant under positive linear transformation\n▪ With deterministic prizes only (no lottery choices), only ordinal utility can be determined, i.e., total order on prizes\n \n\n## Module 8 Definitions\n* **Utility function** - Your definition here\n* **Expected utility** - your definition here\n* **Etc.** - your definition here\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Bandit Problems Definition:\n> Each arm Mi is a Markov reward process or MRP, that is, an MDP with only one possible action Ai It has states Si, transition model Pi(s′|s,ai), and reward Ri(s,ai,s′).The arm defines a distribution over sequences of rewards Ri,0,Ri,1,Ri,2,…, where each Ri,t is a random variable.\n> The overall bandit problem is an MDP: the state space is given by the Cartesian product S=S1×⋯×Sn; the actions are a1,…,an; the transition model updates the state of whichever arm Mi is selected, according to its specific transition model, leaving the other arms unchanged; and the discount factor is γ.\n2 armed bandits - one has same rewards each time, other has arbitrary sequence of rewards. You have to switch between the two at the right time.\nWith just one arm, the only choice is whether to pull again or to stop. If you pull the first arm T times (i.e., at times 0,1,…,T−1 we say that the stopping time is T.\n\nThe value defined above is known as the gittins index of M. ​​The remarkable thing about the Gittins index is that it provides a very simple optimal policy for any bandit problem: pull the arm that has the highest Gittins index, then update the Gittins indices.Reduces time complexity from O(n) to O(1)\nThe Gittins index is a measure of the reward that can be achieved through a given stochastic process with certain properties, namely: the process has an ultimate termination state and evolves with an option, at each intermediate state, of terminating.\n\n\n\nPerhaps the simplest and best-known instance of a bandit problem is the Bernoulli bandit, where each arm Mi produces a reward of 0 or 1 with a fixed but unknown probability \nμi.  We assign exploration bonuses to states which are rarely visited.\n\nApproximately optimal bandit policies: The basic idea is to use the samples from each arm to establish a confidence interval for the value of the arm, that is, a range within which the value can be estimated to lie with high confidence. then choose the arm with the highest upper bound on its confidence interval. A UCB policy simply picks the arm with the highest UCB value.\n\nA second method, Thompson sampling, chooses an arm randomly according to the probability that the arm is in fact optimal, given the samples so far.\n\nThe task of choosing the best option under these conditions is called a selection problem.\n\nThe concept of metalevel decision problems such as deciding what computations to make during a game-tree search prior to making a move.\n\nAn important generalization of the bandit process is the bandit superprocess or BSP, in which each arm is a full Markov decision process in its own right, rather than being a Markov reward process with only one possible action.\n\ninteraction can be modeled by the notion of opportunity cost: how much utility is given up per time step by not devoting that time step to another arm. \nDominating policy: which thus gives an upper bound on the value of acting in the arm.\n \n\n## AIMA Chapter 22.1 Learning from Rewards\n Sparse rewards: —the win/loss rewards for chess and racing - only allotted at end of game.\nModel Based (MDPs and Dynamic Programming) - explicitly learning p(s’|s,a) and r(s’|s,a), they learn a utility function.\nModel free (Q learning - Action-utility learning and SARSA - passive reinforcement learning, POLICY SEARCH: The agent learns a policy  that maps directly from states to actions. This is a reflex agent! \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Agent doesn't know P or R.\nDirect Utility Estimation: utility of a state is defined as the expected total reward from that state onward.\nAdaptive dynamic programming (ADP): fix the policy, apply bellman equation, solve using Linear Algebra\nModified policy iteration: using a simplified value iteration process to update the utility estimates after each change to the learned model. Because the model usually changes only slightly with each observation, the value iteration process can use the previous utility estimates as initial values and typically converge very quickly.\nTemporal Difference Learning:\n\n> Pseudo experience:  extend the TD approach to use a transition model to generate several pseudoexperiences—transitions that the TD agent can imagine might happen, given its current model. For each observed transition, the TD agent can generate a large number of imaginary transitions. In this way, the resulting utility estimates will approximate more and more closely those of ADP—of course, at the expense of increased computation time.\n> The prioritized sweeping heuristic prefers to make adjustments to states whose likely successors have just undergone a large adjustment in their own utility estimates.\n \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n An active learning agent gets to decide what actions to take.\nGreedy Agent:  because it greedily takes the action that it currently believes to be optimal at each step.\nGLIE: greedy in the limit of infinite exploration.\nSafe Exploration Techniques:\n> Bayesian reinforcement learning, assumes a prior probability P(h) over hypotheses h about what the true model is; the posterior probability P(h|e) is obtained in the usual way by Bayes’ rule given the observations to date.\n> exploration POMDP whose belief states are distributions over models. In principle, this exploration POMDP can be formulated and solved before the agent ever sets foot in the world.\n> The robust control approach can be considered as a game between the agent and an adversary, where the adversary gets to pick the worst possible result for any action, and the policy we get is the minimax solution for the game.\nTemporal difference Q learning: SARSA (on policy), Q learning (off policy)\n \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Reinforcement Learning - learn the probability distribution, Q learning.\nModel-Based Idea:\nLearn an approximate model based on experiences\nSolve for values as if the learned model were correct\nStep 1: Learn empirical MDP model\nCount outcomes s’ for each T(s, a,s’)\nNormalize to give an estimate of\nDiscover each when we experience R(s, a, s’)\nStep 2: Solve the learned MDP\nFor example, use value iteration, as before.\n \nModel Free Idea:\nNo track of transition learning\nPassive Reinforcement: someone else chooses the policy for us.\nSimplified task: policy evaluation\nInput: a fixed policy π(s)\nYou don’t know the transitions T(s,a,s’)\nYou don’t know the rewards R(s,a,s’)\nGoal: learn the state values\nDirect Evaluation: Taking average from particular states\nWhat’s good about direct evaluation?\n> It’s easy to understand\n> It doesn’t require any knowledge of T, R\n> It eventually computes the correct average values, using just sample transitions\nWhat's bad about it?\n> It wastes information about state connections\n> Each state must be learned separately\n> So, it takes a long time to learn and more number of samples\n \nPolicy Evaluation: T and R needed -> Sample based Policy Evaluation -> But how to go back from terminal state to start state? Would the state be visited n times? No guarantee!\n \nTemporal Difference: Instead of update after n steps, update the values every single time, Model Free\n\nExponential moving average ->  gives more attention to recent updates\n\nValue under policy, hence they’ll change with every policy.\nTherefore, Q value is needed.\nQ learning: Off policy learning - even though you are acting sub optimally, you converge to the optimal value.\nMakes action selection, model free. Online planning!\nDifference between value iteration and Q value iteration:\n\n\nExploration vs Exploitation: epsilon greedy\nExploration functions: \nWhen to explore?\nRandom actions: explore a fixed amount\nBetter idea: explore areas whose badness is not (yet) established, eventually stop exploring.\nTakes a value estimate u and a visit count n, and returns an optimistic utility. f(u,n) = u + k/n.\nk/n is the bonus function. n=0, k/n is high and more likely toi visit\n\n \nApproximate Q learning:\nInstead of having to learn state every state, generalize about similar states\nLinear Value function:\n \n\n## Module 9 Lecture Notes\n Your summary here \n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n The best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. Such end-to-end evaluation is called extrinsic evaluation.\nAn intrinsic evaluation metric is one that measures the quality of a model independent of any application.\nIn practice we don’t use raw probability as our metric for evaluating language models, but a variant called perplexity. The perplexity (PP) of a language model on a test set is the inverse probability of the test set, normalized by the number of words. \n\nThus, minimizing perplexity is equivalent to maximizing the test set probability according to the language model.As we see above, the more information the n-gram gives us about the word sequence, the lower the perplexity. (perplexity is related inversely to the likelihood of the test sequence according to the model).\n \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n One important way to visualize what kind of knowledge a language model embodies is to sample from it. Sampling from a distribution means to choose random points according to their likelihood.We choose a random value between 0 and 1, find that point on the probability line, and print the word whose interval includes this chosen value. We continue choosing random numbers and generating words until we randomly generate the sentence-final token . \n\n## SLP Chapter 3.4 Generalization and Zeros\n The n-gram model, like many statistical models, is dependent on the training corpus. One implication of this is that the probabilities often encode specific facts about a given training corpus. Another implication is that n-grams do a better and better job of modeling the training corpus as we increase the value of N.\nOne step is to be sure to use a training corpus that has a similar genre to whatever task we are trying to accomplish. To build a language model for translating legal documents, we need a training corpus of legal documents. To build a language model for a question-answering system, we need a training corpus of questions. It is equally important to get training data in the appropriate dialect or variety, especially when processing social media posts or spoken transcripts.\nMatching genres and dialects is still not sufficient. Our models may still be subject to the problem of sparsity. \nDealing with OOV:\n1. Choose a vocabulary (word list) that is fixed in advance. \n2. Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step. \n3. Estimate the probabilities from its counts just like any other regular word in the training set.\n \n\n## SLP Chapter 3.5 Smoothing\n The simplest way to do smoothing is to add one to all the n-gram counts, before we normalize them into probabilities. All the counts that used to be zero will now have a count of 1, the counts of 1 will be 2, and so on. This algorithm is called Laplace smoothing. \nA related way to view smoothing is as discounting (lowering) some non-zero counts in order to get the probability mass that will be assigned to the zero counts. Thus, instead of referring to the discounted counts c* , we might describe a smoothing algorithm in terms of a relative discount dc, the ratio of the discounted counts to the original counts: dc = c*/c.\nK smoothing: adding k(0.5,0.25 etc) instead of 1.\n \nIn other words, sometimes using less context is a good thing, helping to generalize more for contexts that the model hasn’t learned much about. There are two ways backoff to use this n-gram “hierarchy”. In backoff, we use the trigram if the evidence is sufficient, otherwise we use the bigram, otherwise the unigram. In other words, we only “back off” to a lower-order n-gram if we have zero evidence for a higher-order interpolation n-gram. By contrast, in interpolation, we always mix the probability estimates from all the n-gram estimators, weighing and combining the trigram, bigram, and unigram counts.\nInterpolation:\n\nLambda, a hyperparameter can be set by cross validation, validation set or use EM.\nKatz Backoff: In order for a backoff model to give a correct probability distribution, we have to discount the higher-order n-grams to save some probability mass for the lower order n-grams.\nKatz backoff is often combined with a smoothing method called Good-Turing. The combined Good-Turing backoff algorithm involves quite detailed computation for estimating the Good-Turing smoothing and the P ∗ and α values. \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n An n-gram language model can also be shrunk by pruning, for example only storing n-grams with counts greater than some threshold or using entropy to prune less-important n-grams. Another option is to build approximate language models using techniques like Bloom filters.\nStupid backoff gives up the idea of trying to make the language model a true probability distribution. There is no discounting of the higher-order probabilities. If a higher-order n-gram has a zero count, we simply backoff to a lower order n-gram, weighted by a fixed (context-independent) weight. This algorithm does not produce a probability distribution. \n\n## Module 10 Lecture Notes\n > Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms).\n> Unobserved variables (states): Agent needs to reason about other aspects (e.g. where an object is or what disease is present).\n> Model: Agent knows something about how the known variables relate to the unknown variables.\n> A random variable is some aspect of the world about which we (may) have uncertainty.\n> Chain Rule:\n\nOne goal: assign a probability to a sentence:\n• Autocomplete for texting\n• Machine Translation\n• Spelling Correction\n• Speech Recognition\nMLE estimate of the next word: just count and divide!\nSimplifying Assumption = Markov Assumption!\nBigram:   ; \nMLE problems: \n> We do everything in log space, Avoid underflow, (also adding is faster than multiplying)\n> Out of vocabulary items (OOV), <unk> to deal with OOVs, Normalize training data by replacing any word not in L with <unk>, Avoid zeros with smoothing\n \n \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n The compactness of Bayesian networks is an example of a general property of locally structured (also called sparse) systems. In a locally structured system, each subcomponent interacts directly with only a bounded number of other components, regardless of the total number of components. Local structure is usually associated with linear rather than exponential growth in complexity.\nEach variable is conditionally independent of its non-descendants, given its parents.\nA variable is conditionally independent of all other nodes in the network, given its parents, children, and children’s parents—that is, given its Markov blanket.\n\nBayes’ Net for Continuous variables: One way to handle continuous variables is with discretization—that is, dividing up the possible values into a fixed set of intervals.\nYet another solution—sometimes called a nonparametric representation—is to define the conditional distribution implicitly with a collection of instances, each containing specific values of the parent and child variables. Example - Gaussian.\nA network with both discrete and continuous variables is called a hybrid Bayesian network:\n> probit: (probability unit model) uses conditional gaussian distribution model.\n> expit or inverse logit: It uses logistic function\n \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n The basic task for any probabilistic inference system is to compute the posterior probability distribution for a set of query variables, given some observed event—usually, some assignment of values to a set of evidence variables.\nX denotes the query variable; E denotes the set of evidence variables E1,…,Em, and e is a particular observed event; Y denotes the hidden (nonevidence, nonquery) variables Y1,…,Yℓ. Thus, the complete set of variables is {X}∪E∪Y. A typical query asks for the posterior probability distribution P(X|e).\nInference by Enumeration: O(n*2^n)\n\nThis can be reduced to O(2^n) by taking advantage of the nested structure of the computation. In symbolic terms, this means moving the summations inwards as far as possible in expressions.\n to \nVariable Elimination:\nThis is a form of dynamic programming. \nEvaluating expressions right to left i.e bottom-up.\nEach factor is a matrix indexed by the values of its argument variables.\nPointwise product operation: \n\nComplexity of Exact Inference: The complexity of exact inference in Bayes nets depends strongly on the structure of the network.\nThere are singly connected networks or polytrees, and they have a particularly nice property: The time and space complexity of exact inference in polytrees is linear in the size of the network.\nFor multi connected - exponential time complexity. NP Hard problem.\nSatisfiability (often abbreviated SAT) is the problem of determining whether there exists an interpretation that satisfies the formula. In other words, it establishes whether the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to true.\nMeasures such as tree width, which bound the complexity of solving a CSP, can also be applied directly to Bayes nets. Moreover, the variable elimination algorithm can be generalized to solve CSPs as well as Bayes nets.\n \n\n## Module 11 Lecture Notes\n Evidence variable can block paths in causal chains:\nConditionally independent if no active path between them (d- separation algo).\nInference: calculating some useful quantity from a joint probability distribution.\n \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n With alternative vocabulary, we can say that h is a model of the data, drawn from a model class H, or we can say a function drawn from a function class. We call the output yi as the ground truth—the true answer we are asking our model to predict.\nHypothesis space -> prior knowledge.\nBy bias we mean (loosely) the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training sets. Bias often results from restrictions imposed by the hypothesis space. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n The decision tree learning algorithm chooses the attribute with the highest Importance. We will now show how to measure importance, using the notion of information gain, which is defined in terms of entropy.\nEntropy is a measure of the uncertainty of a random variable; the more information, the less entropy. A random variable with only one possible value—a coin that always comes up heads—has no uncertainty and thus its entropy is defined as zero.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n We say that a model that exactly fits all the training data has interpolated the data. Model classes typically start to overfit as the capacity approaches the point of interpolation. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Thus, any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be seriously wrong: that is, it must be probably approximately correct (PAC). ​​Any learning algorithm that returns hypotheses that are probably approximately correct is called a PAC learning algorithm; we can use this approach to provide bounds on the performance of various learning algorithms.\nOne can think of an approximately correct hypothesis as being “close” to the true function in hypothesis space: it lies inside what is called the ϵ-ball around the true function f. The hypothesis space outside this ball is called Hbad.\n\nDecision lists resemble decision trees, but their overall structure is simpler: they branch only in one direction.\nOn the other hand, if we restrict the size of each test to at most k literals, then it is possible for the learning algorithm to generalize successfully from a small number of examples. We use the notation k -DL for a decision list with up to k conjunctions.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n The solution for such unknown words is to ignore them—remove them from the test\ndocument and not include any probability for them at all.\nStop words: the, a \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 Naïve Bayes: Assume all features are independent effects of the label\n\nChanges complexity from |Y|*|F|^n to n*|Y|*|F|.\nTotal number of parameters are linear in terms of features.\nStart with a bunch of probabilities: P(Y) and the P(Fi|Y) tables. Use standard inference to compute P(Y|F1…Fn).\nEstimates of local conditional probability tables:\n• P(Y), the prior over labels\n• P(Fi|Y) for each feature (evidence variable)\n• These probabilities are collectively called the parameters of the model and denoted by theta\n \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n The input to the neural network is a k-gram of words w1:k.\nThe output is a probability distribution over the next word.\nThe k context words are treated as a word window. Each word is associated with an\nembedding vector.\n \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n In this section we introduce one method for computing embeddings: skip-gram with negative sampling, sometimes called SGNS. The skip-gram algorithm is one word2vec of two algorithms in a software package called word2vec, and so sometimes the algorithm is loosely referred to as word2vec.\nSkip gram: 4- context words: +--2\nThere are many kinds of static embeddings. An extension of word2vec, fasttext addresses a problem with word2vec as we have presented it so far: it has no good way to deal with unknown words — words that appear in a test corpus but were unseen in the training corpus.\nFasttext deals with these problems by using subword models, representing each word as itself plus a bag of constituent n-grams, with special boundary symbols < and > added to each word. For example, n = 3 the word where would be represented by the sequence plus the character n-grams: <wh, whe, her, ere, re>\nTwo words have first-order co-occurrence (sometimes called syntagmatic association) if they are typically nearby each other. Thus wrote is a first-order associate of book or poem. Two words have second-order co-occurrence (sometimes called paradigmatic association) if they have similar neighbors. Thus wrote is a second-order associate of words like said or remarked.  \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": {}
        }
      ]
    }
  ]
}