{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8aec2dec-8047-4ab2-f7c4-fa630c536034"
      },
      "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": 16,
      "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": "0458a5ee-2d59-417c-940c-e6a8e93abe95"
      },
      "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": 17,
      "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": 18,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "outputId": "84f82db2-7d6a-4667-f8c7-f94ec2c214d5",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "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",
        "#additive_utility = \"\"\"$U([r_0,r_1,r_2,...])$ = r_0 + r_1 + r_2 + ...\"\"\"  \n",
        "#discounted_utility = \"\"\"$U([r_0,r_1,r_2,...])$ = r_0 + \\gamma*r_1 + \\gamma^2*r_2 + ...\"\"\"  \n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary: \"\"\" #+ sample_equation \n",
        "chapter16_2 =  \"\"\" Chapter 16.2 summary:  The primary issue for utility theory is to understand how preferences between complex lotteries \n",
        "are related to preferences between the underlying states in those lotteries. To address this issue \n",
        "we list six constraints that we require any reasonable preference relation to obey: \\\n",
        "\n",
        "ORDERABILITY: Given any two lotteries, a rational agent must either prefer one \n",
        "to the other or else rate the two as equally preferable. That is, the agent cannot avoid deciding. \n",
        "As we said on page 490, refusing to bet is like refusing to allow time to pass. Exactly one of (A ' \n",
        "B), (B ' A), or (A ? B) holds. \\\n",
        "\n",
        "TRANSITIVITY: Given any three lotteries, if an \n",
        "agent prefers A to B and prefers B to C, then the agent must prefer A to C. (A ' B) ? (B ' C) ? (A \n",
        "' C) . \\\n",
        "\n",
        "CONTINUITY: If some lottery B is between A and C in preference, then there \n",
        "is some probability p for which the rational agent will be indifferent between getting B for sure \n",
        "and the lottery that yields A with probability p and C with probability 1 ? p. A ' B ' C ? ? p [p, \n",
        "A; 1 ? p, C] ? B . \\\n",
        "\n",
        "SUBSTITUTABILITY: If an agent is indifferent between \n",
        "two lotteries A and B, then the agent is indifferent between two more complex lotteries that are \n",
        "the same except that B 2 We apologize to readers whose local airlines no longer offer food on \n",
        "long flights. Section 16.2. The Basis of Utility Theory 613 is substituted for A in one of them. \n",
        "This holds regardless of the probabilities and the other outcome(s) in the lotteries. A ? B ? [p, \n",
        "A; 1 ? p, C] ? [p, B; 1 ? p, C] . This also holds if we substitute ' for ? in this axiom. \\\n",
        "\n",
        "MONOTONICITY: Suppose two lotteries have the same two possible outcomes, \n",
        "A and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher \n",
        "probability for A (and vice versa). A ' B ? (p>q ? [p, A; 1 ? p, B] ' [q, A; 1 ? q,B]). \\\n",
        "\n",
        "DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones \n",
        "using the laws of probability. This has been called the no fun in gambling rule because it says \n",
        "that two consecutive lotteries can be compressed into a single equivalent lottery, as shown in \n",
        "Figure 16.1(b).3 [p, A; 1 ? p, [q,B; 1 ? q, C]] ? [p, A; (1 ? p)q,B; (1 ? p)(1 ? q), C] . These \n",
        "constraints are known as the axioms of utility theory. Each axiom can be motivated by showing \n",
        "that an agent that violates it will exhibit patently irrational behavior in some situations. \"\"\"\n",
        "\n",
        "chapter16_3 =  \"\"\" Chapter 16.3 summary: \"\"\" \n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Chapter 17.1 summary:  \"\"\"\n",
        "chapter17_2 =  \"\"\" Chapter 17.2 summary: There is direct relation btwn\n",
        "utility of a state and the utility of its neighbors: the utility of a state is immediate reward\n",
        "for that state plus the exp discounted utility of the next state. The utility of a state is given by\n",
        "$U(s) = R(s) + γ max_{a∈A(s)}s P(s | s, a)U(s)$\n",
        "The utilities of thestates—defined as the expected utility of subsequent state sequences—are\n",
        "solutions of the set of Bellman eq.\n",
        "Let us look at one of the Bellman eqs for the 4 × 3 world. The equation for the\n",
        "state (1,1) is\n",
        "U(1, 1) = −0.04 + γ max[ 0.8U(1, 2) + 0.1U(2, 1) + 0.1U(1, 1), (Up)\n",
        "0.9U(1, 1) + 0.1U(1, 2), (Left)\n",
        "0.9U(1, 1) + 0.1U(2, 1), (Down)\n",
        "0.8U(2, 1) + 0.1U(1, 2) + 0.1U(1, 1) ]. (Right)\n",
        "Up is the best action.\n",
        "The value iteration algorithm\n",
        "The Bellman eq is basis of value iteration algorithm for MDPs. With n possible states, \n",
        "there are n Bellman eqs, one for each state. The n equations\n",
        "contain n unknowns—the utilities of the states. So we would like to solve these simultaneous\n",
        "equations to find the utilities. The equations are nonlinear, because the\n",
        "“max” operator is not a linear operator. So try an iterative approach. Start with arbitrary initial values for the utilities,\n",
        "calculate the right-hand side of the equation, and plug it into the left-hand side—thereby\n",
        "updating the utility of each state from the utilities of its neighbors. We repeat this until we\n",
        "reach an equilibrium. Let Ui(s) be the utility value for state s at the ith iteration. The iteration\n",
        "BELLMAN UPDATE step, called a Bellman update, looks like this:\n",
        "Ui+1(s) ← R(s) + γ max_{a∈A(s)} SUMMATION P(s | s, a)Ui(s)\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Module 8 summary: Only two ways to define utilities, additive or discounted \\\n",
        "additive_utility = $U([r_0,r_1,r_2,...]) = r_0 + r_1 + r_2 + ...$  \\\n",
        "discounted_utility = $U([r_0,r_1,r_2,...]) = r_0 + gamma * r_1 + gamma^2 * r_2 + ...$  \\\n",
        "additive discounted rewards utility of a history = $U_h([s_0,a_0,s_1,a_1,s_2,a_2,...])$ = $R(s_0,a_0,_s_1) + gamma * R(s_1,a_1,_s_2) + gamma^2 * R(s_2,a_2,_s_3) + ...$ \\\n",
        "$U(s) = \\max_{a} Q(s,a)$ \\\n",
        "\n",
        "$\\pi^*(s) = \\argmax Q(s,a)$ \\\n",
        "\n",
        "Representing MDP, 3D table for $P(s^'|s,a)$ and $R(s,a,s^')$ \\\n",
        "\n",
        "Problem:  What if the game lasts forever?  Do we get infinite rewards? \\\n",
        "Solution: finite horizon (like depth limited search), terminate after fixed steps, gives nonstationary policies since \\\n",
        "dependent on time left.  Discount between 0 and 1.  Smaller discount means smaller horizon. \\\n",
        "Policy iteration vs value iteration...PI starts with random policy \\\n",
        "algorithm is more complex, guaranteed to converge, cheaper to computer, requires few iterations to converge and faster. \\\n",
        "Value iteration starts with random value function, algo is simpler, gtd to converge, more expensive to compute $O(S^2A)$ \n",
        "requires more iterations to converge and slower.\\\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\" : \"captures agent's preferences\",\n",
        "\"expected utility\" : \"avg utility value of outcomes accounting for outcome probability\",\n",
        "\"policy loss\": \"Most an agent can underperform the optimal policy by choosing a non optimal policy\",\n",
        "\"sequential decision problems\" : \"agent utility is function of sequence of decisions\",\n",
        "\"transition model\" : \"defines outcome of each action in each state\",\n",
        "\"Markovian\" : \"probability of reading $s^'$ from $s$ depends only on $s$ and not on the history of earlier states\",\n",
        "\"reward\" : \"$R(s,a,s^')$ rewards can be positive or negative bounded by +/-$R_\\mathrm{max}$\",\n",
        "\"Markov decision process\" : \"sequential decision problem in fully observable stochastic environment with Markovian transition model and additive rewards\",\n",
        "\"Dynamic programming\" : \"problem simplification, recursively breaks it into smaller pieces, remembering optimal solutions to pieces\",\n",
        "\"policy\" : \"maps how the agent should act for any state that the agent might reach\",\n",
        "\"optimal policy\" : \"policy that maximizes expected utility\",\n",
        "\"nonstationary\" : \"In finite horizon, best action given a state may be a function of how much time is left\",\n",
        "\"stationary\" : \"optimal policy is stationary if it does not behave differently in same state at different times\",\n",
        "\"additive discounted rewards\" : \"used to calculate utility of state sequences\",\n",
        "\"discount factor\" : \"between 0 and 1.  discount close to 0 means rewards in distant future as less attractive.\",\n",
        "\"proper policy\" : \" policy gtd to reach a terminal state\",\n",
        "\"Bellman equation\" : \"current state utility is expected reward from next transition plus discounted utility of next state\",\n",
        "\"Q-function (action-utility function)\" : \"Q(s,a) is the expected utility of taking a given action in a given state\",\n",
        "\"shaping theorem\" : \"relates to fact that additive reward decomposition of tulities leads to more freedom in describing rewards\",\n",
        "\"sparse\" : \"most entries are zeros, table representation still $O(|S||A|)$\",\n",
        "\n",
        "\"value iteration\" : \"algo for solving MDP, exact solutions offline, we coputer the optimal state value function by iterating over $v(s)$estimate updates \",\n",
        "\"policy iteration\" : \"algo for solving MDP, exact solutions offline, start by choosing arbitrary policy $\\pi$ and iteratively evaluate and improve the policy until convergence\",\n",
        "\"linear programming\" : \"algo for solving MDP, exact solutions offline\",\n",
        "\"Monte Carlo programming\" : \"family of online algos for solving MDP\",\n",
        "\"Bellman update\" : \"iteration step, update applied simultaneously to all states at each iteration\",\n",
        "\"contraction\" : \"shows value iteration converges, has only one fixed point, function value must get closer to the fixed point\",\n",
        "\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter16_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter16_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter16_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter16_2))\n",
        "\n",
        "print(\"The length in words is\", len(chapter16_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter16_3))\n",
        "\n",
        "print(\"The length in words is\", len(chapter17_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter17_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter17_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter17_2))\n",
        "\n",
        "print(\"The lecture length in words is\", len(module8_lecture_notes.split(' ')))\n",
        "print(\"The lecture length in characters is\", len(module8_lecture_notes))\n"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 5\n",
            "The length in characters is 23\n",
            "The length in words is 466\n",
            "The length in characters is 2409\n",
            "The length in words is 5\n",
            "The length in characters is 23\n",
            "The length in words is 6\n",
            "The length in characters is 24\n",
            "The length in words is 266\n",
            "The length in characters is 1607\n",
            "The lecture length in words is 174\n",
            "The lecture length in characters is 1153\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        ""
      ],
      "metadata": {
        "id": "aTAqGL7GbQvM"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "pioz0mv9bRWy"
      },
      "execution_count": 19,
      "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": "83418c95-3435-4387-ff50-d9459881f0b8"
      },
      "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": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary: \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Chapter 16.2 summary:  The primary issue for utility theory is to understand how preferences between complex lotteries \nare related to preferences between the underlying states in those lotteries. To address this issue \nwe list six constraints that we require any reasonable preference relation to obey: \nORDERABILITY: Given any two lotteries, a rational agent must either prefer one \nto the other or else rate the two as equally preferable. That is, the agent cannot avoid deciding. \nAs we said on page 490, refusing to bet is like refusing to allow time to pass. Exactly one of (A ' \nB), (B ' A), or (A ? B) holds. \nTRANSITIVITY: Given any three lotteries, if an \nagent prefers A to B and prefers B to C, then the agent must prefer A to C. (A ' B) ? (B ' C) ? (A \n' C) . \nCONTINUITY: If some lottery B is between A and C in preference, then there \nis some probability p for which the rational agent will be indifferent between getting B for sure \nand the lottery that yields A with probability p and C with probability 1 ? p. A ' B ' C ? ? p [p, \nA; 1 ? p, C] ? B . \nSUBSTITUTABILITY: If an agent is indifferent between \ntwo lotteries A and B, then the agent is indifferent between two more complex lotteries that are \nthe same except that B 2 We apologize to readers whose local airlines no longer offer food on \nlong flights. Section 16.2. The Basis of Utility Theory 613 is substituted for A in one of them. \nThis holds regardless of the probabilities and the other outcome(s) in the lotteries. A ? B ? [p, \nA; 1 ? p, C] ? [p, B; 1 ? p, C] . This also holds if we substitute ' for ? in this axiom. \nMONOTONICITY: Suppose two lotteries have the same two possible outcomes, \nA and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher \nprobability for A (and vice versa). A ' B ? (p>q ? [p, A; 1 ? p, B] ' [q, A; 1 ? q,B]). \nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones \nusing the laws of probability. This has been called the no fun in gambling rule because it says \nthat two consecutive lotteries can be compressed into a single equivalent lottery, as shown in \nFigure 16.1(b).3 [p, A; 1 ? p, [q,B; 1 ? q, C]] ? [p, A; (1 ? p)q,B; (1 ? p)(1 ? q), C] . These \nconstraints are known as the axioms of utility theory. Each axiom can be motivated by showing \nthat an agent that violates it will exhibit patently irrational behavior in some situations. \n\n## AIMA Chapter 16.3 Utility Functions\n Chapter 16.3 summary: \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Chapter 17.1 summary:  \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Chapter 17.2 summary: There is direct relation btwn\nutility of a state and the utility of its neighbors: the utility of a state is immediate reward\nfor that state plus the exp discounted utility of the next state. The utility of a state is given by\n$U(s) = R(s) + γ max_{a∈A(s)}s P(s | s, a)U(s)$\nThe utilities of thestates—defined as the expected utility of subsequent state sequences—are\nsolutions of the set of Bellman eq.\nLet us look at one of the Bellman eqs for the 4 × 3 world. The equation for the\nstate (1,1) is\nU(1, 1) = −0.04 + γ max[ 0.8U(1, 2) + 0.1U(2, 1) + 0.1U(1, 1), (Up)\n0.9U(1, 1) + 0.1U(1, 2), (Left)\n0.9U(1, 1) + 0.1U(2, 1), (Down)\n0.8U(2, 1) + 0.1U(1, 2) + 0.1U(1, 1) ]. (Right)\nUp is the best action.\nThe value iteration algorithm\nThe Bellman eq is basis of value iteration algorithm for MDPs. With n possible states, \nthere are n Bellman eqs, one for each state. The n equations\ncontain n unknowns—the utilities of the states. So we would like to solve these simultaneous\nequations to find the utilities. The equations are nonlinear, because the\n“max” operator is not a linear operator. So try an iterative approach. Start with arbitrary initial values for the utilities,\ncalculate the right-hand side of the equation, and plug it into the left-hand side—thereby\nupdating the utility of each state from the utilities of its neighbors. We repeat this until we\nreach an equilibrium. Let Ui(s) be the utility value for state s at the ith iteration. The iteration\nBELLMAN UPDATE step, called a Bellman update, looks like this:\nUi+1(s) ← R(s) + γ max_{a∈A(s)} SUMMATION P(s | s, a)Ui(s)\n\n\n## Module 8 Lecture Notes\n Module 8 summary: Only two ways to define utilities, additive or discounted additive_utility = $U([r_0,r_1,r_2,...]) = r_0 + r_1 + r_2 + ...$  discounted_utility = $U([r_0,r_1,r_2,...]) = r_0 + gamma * r_1 + gamma^2 * r_2 + ...$  additive discounted rewards utility of a history = $U_h([s_0,a_0,s_1,a_1,s_2,a_2,...])$ = $R(s_0,a_0,_s_1) + gamma * R(s_1,a_1,_s_2) + gamma^2 * R(s_2,a_2,_s_3) + ...$ $U(s) = \\max_{a} Q(s,a)$ \n$\\pi^*(s) = \u0007rgmax Q(s,a)$ \nRepresenting MDP, 3D table for $P(s^'|s,a)$ and $R(s,a,s^')$ \nProblem:  What if the game lasts forever?  Do we get infinite rewards? Solution: finite horizon (like depth limited search), terminate after fixed steps, gives nonstationary policies since dependent on time left.  Discount between 0 and 1.  Smaller discount means smaller horizon. Policy iteration vs value iteration...PI starts with random policy algorithm is more complex, guaranteed to converge, cheaper to computer, requires few iterations to converge and faster. Value iteration starts with random value function, algo is simpler, gtd to converge, more expensive to compute $O(S^2A)$ \nrequires more iterations to converge and slower.\n\n## Module 8 Definitions\n* **Utility function** - captures agent's preferences\n* **Expected utility** - avg utility value of outcomes accounting for outcome probability\n* **Policy loss** - Most an agent can underperform the optimal policy by choosing a non optimal policy\n* **Sequential decision problems** - agent utility is function of sequence of decisions\n* **Transition model** - defines outcome of each action in each state\n* **Markovian** - probability of reading $s^'$ from $s$ depends only on $s$ and not on the history of earlier states\n* **Reward** - $R(s,a,s^')$ rewards can be positive or negative bounded by +/-$R_\\mathrm{max}$\n* **Markov decision process** - sequential decision problem in fully observable stochastic environment with Markovian transition model and additive rewards\n* **Dynamic programming** - problem simplification, recursively breaks it into smaller pieces, remembering optimal solutions to pieces\n* **Policy** - maps how the agent should act for any state that the agent might reach\n* **Optimal policy** - policy that maximizes expected utility\n* **Nonstationary** - In finite horizon, best action given a state may be a function of how much time is left\n* **Stationary** - optimal policy is stationary if it does not behave differently in same state at different times\n* **Additive discounted rewards** - used to calculate utility of state sequences\n* **Discount factor** - between 0 and 1.  discount close to 0 means rewards in distant future as less attractive.\n* **Proper policy** -  policy gtd to reach a terminal state\n* **Bellman equation** - current state utility is expected reward from next transition plus discounted utility of next state\n* **Q-function (action-utility function)** - Q(s,a) is the expected utility of taking a given action in a given state\n* **Shaping theorem** - relates to fact that additive reward decomposition of tulities leads to more freedom in describing rewards\n* **Sparse** - most entries are zeros, table representation still $O(|S||A|)$\n* **Value iteration** - algo for solving MDP, exact solutions offline, we coputer the optimal state value function by iterating over $v(s)$estimate updates \n* **Policy iteration** - algo for solving MDP, exact solutions offline, start by choosing arbitrary policy $\\pi$ and iteratively evaluate and improve the policy until convergence\n* **Linear programming** - algo for solving MDP, exact solutions offline\n* **Monte carlo programming** - family of online algos for solving MDP\n* **Bellman update** - iteration step, update applied simultaneously to all states at each iteration\n* **Contraction** - shows value iteration converges, has only one fixed point, function value must get closer to the fixed point\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "79cc3fd6-3a3b-46f5-e07e-ae6a933fdbb5"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Chapter 17.3 summary:  It is possible to get an optimal policy when the utility function estimate is inaccurate. If one action is \\\n",
        "better than others, then the magnitude of utilities on the states need not be precise...alternative way to find optimal policies. The policy iteration \\\n",
        "algorithm alternates the following two steps, beginning from some initial policy $\\pi_0$: \\\n",
        "\n",
        "\n",
        "Policy evaluation: given a policy \\pi_i, calc Ui = Uπi , the utility of each state if πi were to be executed. \\\n",
        "\n",
        "Policy improvement: Calc a new MEU policy pi_{i+1}, using one-step look-ahead POLICY based on Ui.\\\n",
        "The algo terminates when policy improvement step yields no change in the utilities. We know that \\\n",
        "utility function Ui is a fixed point of Bellman update, so it is a solution to Bellman eqs, and πi must be an optimal policy. \\\n",
        "Finite state space has finite many policies, and each iteration can be shown to yield a better policy, policy iteration must terminate. \\\n",
        "The policy improvement step is obviously straightforward.  Implementing policy evaluation  \\\n",
        "is much simpler than solving the standard Bellman eqs (which is what value iteration does), because the action in \\\n",
        "each state is fixed by the policy.  Important point is these eqs are linear, because the “max” operator has been\\\n",
        "removed. For n states, we have n linear eqs with n unknowns, which can be solved exactly in time $O(n^3)$ by std linear algebra.\\\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Chapter 22.1 summary:  Same goal as MDP to maximize the exp sum of rewards, but reinforcement learning differs from \\\n",
        "from 'just solving an MDP' because the agent is not given the MDP as a problem to solve.  The agent is in 'in' the MDP.  It may not know the \\\n",
        "transition model or the reward function.  \n",
        "\"\"\"\n",
        "chapter22_2 =  \"\"\" Chapter 22.2 summary: Passive learning task is similar to the policy evaluation task, part of the policy iteration algo. \\\n",
        "The difference is that the passive learning agent does not know the transition model $P(s^'|s,a)$ which specifies the probability of reaching state $s'$\\\n",
        "from state s after doing action s; nor does it know the reward function $R(s,a,s^')$, the reward for each transition.\"\"\"\n",
        "chapter22_3 =  \"\"\" Chapter 22.3 summary: Here, f(u, n) is called the exploration function. It determines how greed (preference for\n",
        "high values of u) is traded off against curiosity (preference for actions that have not been\n",
        "tried often and have low n). The function f(u, n) should be increasing in u and decreasing\n",
        "in n. Obviously, there are many possible functions that fit these conditions. One particularly\n",
        "simple definition is\n",
        "f(u, n) = \u0018 R+ if n<Ne\n",
        "u otherwise\n",
        "where R+ is an optimistic estimate of the best possible reward obtainable in any state and Ne\n",
        "is a fixed parameter. This will have the effect of making the agent try each action–state pair\n",
        "at least Ne times.\"\"\"\n",
        "chapter22_4 =  \"\"\" Chapter 22.4 summary: \"\"\"\n",
        "chapter22_5 =  \"\"\" Chapter 22.5 summary: Policy search is the simplest of all the methods in this chapter: the \\\n",
        "idea is to keep twiddling the policy as long as its performance improves, then stop. \\\n",
        "Let us begin with the policies themselves. Remember that a policy π is a function that \\\n",
        "maps states to actions. We are interested primarily in parameterized representations of π that \\\n",
        "have far fewer parameters than there are states in the state space (just as in the preceding \\\n",
        "section). For example, we could represent π by a collection of parameterized Q-functions, \\\n",
        "one for each action, and take the action with the highest predicted value: \\\n",
        "π(s) = maxa Qˆθ(s, a).\n",
        "\n",
        "Each Q-function could be a linear function of the parameters θ, or it could be a nonlinear function \\\n",
        "such as a neural network. Policy search will then adjust the parameters θ to improve the policy. \\\n",
        "Notice that if the policy is represented by Qfunctions, then policy search results in a process that learns Q-functions. \\\n",
        "This process is not the same as Q-learning! In Q-learning with function approximation, the algorithm finds \\\n",
        "a value of θ such that Qˆθ is “close” to Q∗, the optimal Q-function. Policy search, on the \\\n",
        "other hand, finds a value of θ that results in good performance; the values found by the two \\\n",
        "methods may differ very substantially. \\\n",
        "\n",
        "One problem with policy representations of the kind given in Equation (21.14) is that\n",
        "there will be values of θ such that an infinitesimal change in θ causes the policy to switch from one\n",
        "action to another. This means that the value of the policy may also change discontinuously,\n",
        "which makes gradient-based search difficult. For this reason, policy search methods often use\n",
        "stochastic policy representation πθ(s, a), which specifies the probability of selecting action\n",
        "SOFTMAX FUNCTION a in state s. One popular representation is the softmax function:\n",
        "πθ(s, a) = eQˆθ(s,a)/aeQˆθ(s,a).\n",
        "Softmax becomes nearly deterministic if one action is much better than the others, but it\n",
        "always gives a differentiable function of θ; hence, the value of the policy (which depends in\n",
        "Section 21.5. Policy Search 849\n",
        "a continuous fashion on the action selection probabilities) is a differentiable function of θ.\n",
        "Softmax is a generalization of the logistic function to multiple variables.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" Summary:  exploration is you have to try unknown actions to get information.  Exploitation eventually you have to use \\\n",
        "what you know.  Regret...even if you learn intelligently, you make mistakes.  Sampling...because of chance, you try things repeatedly.  \\\n",
        "Regret is the difference between your expected rewards, including youthful suboptimality and optimal expected rewards.  Minimizing regret requires\\\n",
        "optimally learning to be optimal.  Random exploration and exploration functions both end up optimal, but random exploration has higher regret. \\\n",
        "Difficulty...learning can be much harder than solving a known MDP. Temporal difference learning...learn from every experience.  $V(s)$ is updated \\\n",
        "everytime we experience a transition $(s, a, s^', r)$.  Direct evaluation's goal is to compute the values for each state under \\pi by averaging \\\n",
        "together observed sample values.  Act according to \\pi, everytime you visit a state, write down what the sum of the discounted rewards turned out to be.\\\n",
        "Average those samples.  Direct evaluation is easy to understand, doesn't require any knowledge of T,R and eventually computes the correct avg values.  \\\n",
        "Direct evaluation wastes info about state connections, each state is learned separately and it takes a long time. \\\n",
        "Q-learning converges to optimal policy - even if you're activing suboptimally...this is called off-policy learning...\\\n",
        "caveats...you have to explore enough, you have to eventually make the learning rate small enough (but not decrease \\\n",
        "too quickly), basically in the limit it doesn't matter how you select actions\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "\"policy iteration\" : \"algo to learn optimal policy which maximizes long term discounted reward\",\n",
        "\"policy evaluation\" : \"given a policy, calculate the utility of each state assuming we used that policy\",\n",
        "\"policy improvement\" : \"Use a new MEU policy and iterate one-step at a time looking ahead current utility\",\n",
        "\"Dynamic decision networks (DDN)\" : \"factored representations extending dynamic bayesian networks with decision, reward and utility inputs\",\n",
        "\"sparse rewards\" : \"chess and racing example, majority of states no information\",\n",
        "\"Model based reinforcement learning\" : \"agent applies transition model to environment to make decisions.  may develop transition model if not given\",\n",
        "\"Model-free reinforcement learning\" : \"Does not get or learn transition model, uses: action-utility learning (Q-learning) and policy search\",\n",
        "\"Action-utility learning\" : \"Most common form is Q-learning.  \",\n",
        "\"Q-learning\" : \"agent leans Q-function representing sum of rewards from state s and onward if action a taken\",\n",
        "\"Policy search\" : \"uses policy, which maps from states to actions.  Would be a reflex agent.\",\n",
        "\"Passive reinforcement learning\" : \"Agent has fixed policy and must learn utilities of states (or state action pairs)\",\n",
        "\"Active reinforcement learning\" : \"Agent must learn how to proceed in environment (exploration vs exploitation)\",\n",
        "\"Passive learning agent\" : \"Tries to learn utility function starting at state s and total discounted reward from policy \\pi\",\n",
        "\"reward-to-go\" : \"expected sum of rewards from that state and future states\",\n",
        "\"Direct utility estimation\" : \"utility is based the reward-to-go\",\n",
        "\"adaptive dynamic programming\" : \"uses constraints among state utilities by learning transition model that connects the states\",\n",
        "\"curiosity\" : \"type of reward function that uses prediction error as reward determinant\",\n",
        "\"prioritized sweeping\" : \"heuristic which favors adjustments to states whose likely successor have undergone large adjustment to their utility estimates\",\n",
        "\"active learning agent\" : \"Decides own actions to take, no fixed policy\",\n",
        "\"greedy agent\" : \"does not learn true utilities or the true optimal policy, takes what it think is optimal at each step\",\n",
        "\"regret\" : \"quantifies relative goodness of exploration procedures\",\n",
        "\"absorbing state\" : \"no actions have effects and no rewards received\",\n",
        "\"off-policy\" : \"Q-learing, willing to optimize by learning Q-values not necessarily based on current policy\",\n",
        "\"on-policy\" : \"SARSA is on-policy, penalizes negative action, what is action worth in this state if I stick with policy?\",\n",
        "\"catastrophic forgetting\" : \"tendency for neutral network to forget information they learned.  Experience replay is a solution\",\n",
        "\"reward shaping\" : \"Supply agent with additional (smaller?) more frequent rewards (psuedorewards) along way to goals\",\n",
        "\"Policy search\" : \"Easiest form of RL, keep fiddling with the policy as long as its performance continues to improve, otherwise stop\",\n",
        "\"softmax\" : \"form of stochastic policy that specifies probability of choosing action a while in state s\",\n",
        "\"policy value\" : \"expected reward-to-go when a given policy is implemented\",\n",
        "\"correlated sampling\" : \"can be applied to policy search, number of random sequences depends on complexity of policy space not underlying domain\",\n",
        "\"\" : \"\",\n",
        "\n",
        "}\n",
        "\n",
        "\n",
        "print(\"The length in words is\", len(chapter17_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter17_3))\n",
        "\n",
        "print(\"The length in words is\", len(chapter22_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter22_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter22_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter22_2))\n",
        "\n",
        "print(\"The 22.3 length in words is\", len(chapter22_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter22_3))\n",
        "\n",
        "print(\"The 22.4 length in words is\", len(chapter22_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter22_4))\n",
        "\n",
        "print(\"The 22.5 length in words is\", len(chapter22_5.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter22_5))\n",
        "\n",
        "print(\"The lecture length in words is\", len(module9_lecture_notes.split(' ')))\n",
        "print(\"The lecture length in characters is\", len(module9_lecture_notes))\n"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 233\n",
            "The length in characters is 1386\n",
            "The length in words is 61\n",
            "The length in characters is 301\n",
            "The length in words is 62\n",
            "The length in characters is 391\n",
            "The 22.3 length in words is 106\n",
            "The length in characters is 655\n",
            "The 22.4 length in words is 5\n",
            "The length in characters is 23\n",
            "The 22.5 length in words is 361\n",
            "The length in characters is 2262\n",
            "The lecture length in words is 239\n",
            "The lecture length in characters is 1560\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "22aa1dff-b80f-4625-8351-2e5b568235f3"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"AIMA Chapter 22.5 Policy Search\", chapter22_5),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Chapter 17.3 summary:  It is possible to get an optimal policy when the utility function estimate is inaccurate. If one action is better than others, then the magnitude of utilities on the states need not be precise...alternative way to find optimal policies. The policy iteration algorithm alternates the following two steps, beginning from some initial policy $\\pi_0$: \n\nPolicy evaluation: given a policy \\pi_i, calc Ui = Uπi , the utility of each state if πi were to be executed. \nPolicy improvement: Calc a new MEU policy pi_{i+1}, using one-step look-ahead POLICY based on Ui.The algo terminates when policy improvement step yields no change in the utilities. We know that utility function Ui is a fixed point of Bellman update, so it is a solution to Bellman eqs, and πi must be an optimal policy. Finite state space has finite many policies, and each iteration can be shown to yield a better policy, policy iteration must terminate. The policy improvement step is obviously straightforward.  Implementing policy evaluation  is much simpler than solving the standard Bellman eqs (which is what value iteration does), because the action in each state is fixed by the policy.  Important point is these eqs are linear, because the “max” operator has beenremoved. For n states, we have n linear eqs with n unknowns, which can be solved exactly in time $O(n^3)$ by std linear algebra.\n\n## AIMA Chapter 22.1 Learning from Rewards\n Chapter 22.1 summary:  Same goal as MDP to maximize the exp sum of rewards, but reinforcement learning differs from from 'just solving an MDP' because the agent is not given the MDP as a problem to solve.  The agent is in 'in' the MDP.  It may not know the transition model or the reward function.  \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Chapter 22.2 summary: Passive learning task is similar to the policy evaluation task, part of the policy iteration algo. The difference is that the passive learning agent does not know the transition model $P(s^'|s,a)$ which specifies the probability of reaching state $s'$from state s after doing action s; nor does it know the reward function $R(s,a,s^')$, the reward for each transition.\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Chapter 22.3 summary: Here, f(u, n) is called the exploration function. It determines how greed (preference for\nhigh values of u) is traded off against curiosity (preference for actions that have not been\ntried often and have low n). The function f(u, n) should be increasing in u and decreasing\nin n. Obviously, there are many possible functions that fit these conditions. One particularly\nsimple definition is\nf(u, n) = \u0018 R+ if n<Ne\nu otherwise\nwhere R+ is an optimistic estimate of the best possible reward obtainable in any state and Ne\nis a fixed parameter. This will have the effect of making the agent try each action–state pair\nat least Ne times.\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Chapter 22.4 summary: \n\n## AIMA Chapter 22.5 Policy Search\n Chapter 22.5 summary: Policy search is the simplest of all the methods in this chapter: the idea is to keep twiddling the policy as long as its performance improves, then stop. Let us begin with the policies themselves. Remember that a policy π is a function that maps states to actions. We are interested primarily in parameterized representations of π that have far fewer parameters than there are states in the state space (just as in the preceding section). For example, we could represent π by a collection of parameterized Q-functions, one for each action, and take the action with the highest predicted value: π(s) = maxa Qˆθ(s, a).\n\nEach Q-function could be a linear function of the parameters θ, or it could be a nonlinear function such as a neural network. Policy search will then adjust the parameters θ to improve the policy. Notice that if the policy is represented by Qfunctions, then policy search results in a process that learns Q-functions. This process is not the same as Q-learning! In Q-learning with function approximation, the algorithm finds a value of θ such that Qˆθ is “close” to Q∗, the optimal Q-function. Policy search, on the other hand, finds a value of θ that results in good performance; the values found by the two methods may differ very substantially. \nOne problem with policy representations of the kind given in Equation (21.14) is that\nthere will be values of θ such that an infinitesimal change in θ causes the policy to switch from one\naction to another. This means that the value of the policy may also change discontinuously,\nwhich makes gradient-based search difficult. For this reason, policy search methods often use\nstochastic policy representation πθ(s, a), which specifies the probability of selecting action\nSOFTMAX FUNCTION a in state s. One popular representation is the softmax function:\nπθ(s, a) = eQˆθ(s,a)/aeQˆθ(s,a).\nSoftmax becomes nearly deterministic if one action is much better than the others, but it\nalways gives a differentiable function of θ; hence, the value of the policy (which depends in\nSection 21.5. Policy Search 849\na continuous fashion on the action selection probabilities) is a differentiable function of θ.\nSoftmax is a generalization of the logistic function to multiple variables.\n\n## Module 9 Lecture Notes\n Summary:  exploration is you have to try unknown actions to get information.  Exploitation eventually you have to use what you know.  Regret...even if you learn intelligently, you make mistakes.  Sampling...because of chance, you try things repeatedly.  Regret is the difference between your expected rewards, including youthful suboptimality and optimal expected rewards.  Minimizing regret requiresoptimally learning to be optimal.  Random exploration and exploration functions both end up optimal, but random exploration has higher regret. Difficulty...learning can be much harder than solving a known MDP. Temporal difference learning...learn from every experience.  $V(s)$ is updated everytime we experience a transition $(s, a, s^', r)$.  Direct evaluation's goal is to compute the values for each state under \\pi by averaging together observed sample values.  Act according to \\pi, everytime you visit a state, write down what the sum of the discounted rewards turned out to be.Average those samples.  Direct evaluation is easy to understand, doesn't require any knowledge of T,R and eventually computes the correct avg values.  Direct evaluation wastes info about state connections, each state is learned separately and it takes a long time. Q-learning converges to optimal policy - even if you're activing suboptimally...this is called off-policy learning...caveats...you have to explore enough, you have to eventually make the learning rate small enough (but not decrease too quickly), basically in the limit it doesn't matter how you select actions\n\n## Module 9 Definitions\n* **Term** - your definition here\n* **Policy iteration** - algo to learn optimal policy which maximizes long term discounted reward\n* **Policy evaluation** - given a policy, calculate the utility of each state assuming we used that policy\n* **Policy improvement** - Use a new MEU policy and iterate one-step at a time looking ahead current utility\n* **Dynamic decision networks (ddn)** - factored representations extending dynamic bayesian networks with decision, reward and utility inputs\n* **Sparse rewards** - chess and racing example, majority of states no information\n* **Model based reinforcement learning** - agent applies transition model to environment to make decisions.  may develop transition model if not given\n* **Model-free reinforcement learning** - Does not get or learn transition model, uses: action-utility learning (Q-learning) and policy search\n* **Action-utility learning** - Most common form is Q-learning.  \n* **Q-learning** - agent leans Q-function representing sum of rewards from state s and onward if action a taken\n* **Policy search** - Easiest form of RL, keep fiddling with the policy as long as its performance continues to improve, otherwise stop\n* **Passive reinforcement learning** - Agent has fixed policy and must learn utilities of states (or state action pairs)\n* **Active reinforcement learning** - Agent must learn how to proceed in environment (exploration vs exploitation)\n* **Passive learning agent** - Tries to learn utility function starting at state s and total discounted reward from policy \\pi\n* **Reward-to-go** - expected sum of rewards from that state and future states\n* **Direct utility estimation** - utility is based the reward-to-go\n* **Adaptive dynamic programming** - uses constraints among state utilities by learning transition model that connects the states\n* **Curiosity** - type of reward function that uses prediction error as reward determinant\n* **Prioritized sweeping** - heuristic which favors adjustments to states whose likely successor have undergone large adjustment to their utility estimates\n* **Active learning agent** - Decides own actions to take, no fixed policy\n* **Greedy agent** - does not learn true utilities or the true optimal policy, takes what it think is optimal at each step\n* **Regret** - quantifies relative goodness of exploration procedures\n* **Absorbing state** - no actions have effects and no rewards received\n* **Off-policy** - Q-learing, willing to optimize by learning Q-values not necessarily based on current policy\n* **On-policy** - SARSA is on-policy, penalizes negative action, what is action worth in this state if I stick with policy?\n* **Catastrophic forgetting** - tendency for neutral network to forget information they learned.  Experience replay is a solution\n* **Reward shaping** - Supply agent with additional (smaller?) more frequent rewards (psuedorewards) along way to goals\n* **Softmax** - form of stochastic policy that specifies probability of choosing action a while in state s\n* **Policy value** - expected reward-to-go when a given policy is implemented\n* **Correlated sampling** - can be applied to policy search, number of random sequences depends on complexity of policy space not underlying domain\n* **** - \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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "09c5a2ff-ffd7-483a-bdd1-54f75db1448b"
      },
      "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 = \"\"\" Chapter 12.5 summary: Applying Bayes’ rule: The simple case\n",
        "On the surface, Bayes’ rule does not seem very useful. It allows us to compute the single\n",
        "term P(b | a) in terms of three terms: P(a | b), P(b), and P(a). That seems like two steps\n",
        "backwards, but Bayes’ rule is useful in practice because there are many cases where we do\n",
        "have good probability estimates for these three numbers and need to compute the fourth.\n",
        "Often, we perceive as evidence the effect of some unknown cause and we would like to\n",
        "determine that cause. In that case, Bayes’ rule becomes\n",
        "$P(cause|effect) = \\\\frac{P(effect|cause)P(cause)}{P(effect)}$ \\\n",
        "The conditional probability P(effect | cause) quantifies the relationship in the causal direction, whereas P(cause | effect) \\\n",
        "describes the diagnostic direction. In a task such as medical diagnosis, we often have conditional probabilities \\\n",
        "on causal relationships (that is, the doctor knows P(symptoms | disease)) and want to derive a diagnosis, P(disease | symptoms). For\n",
        "example, a doctor knows that the disease meningitis causes the patient to have a stiff neck, say, 70% of the time. \\\n",
        "\n",
        "The doctor also knows some unconditional facts: the prior probability that a patient has meningitis is 1/50,000, and \\\n",
        "the prior probability that any patient has a stiff neck is 1%. Letting s be the proposition that the patient has a stiff neck and m be the\n",
        "proposition that the patient has meningitis, we have\n",
        "P(s|m)=0.7\n",
        "P(m)=1/50000\n",
        "P(s)=0.01\n",
        "$P(m|s) = \\\\frac{P(s|m)P(m)}{P(s)} = \\\\frac{0.7 × 1/50000}{0.01} = 0.0014$\n",
        "That is, we expect less than 1 in 700 patients with a stiff neck to have meningitis. Notice that\n",
        "even though a stiff neck is quite strongly indicated by meningitis (with probability 0.7), the\n",
        "probability of meningitis in the patient remains small. This is because the prior probability of\n",
        "stiff necks is much higher than that of meningitis. \n",
        "\n",
        "for n symptoms that are all conditionally indepdent given Cavity, the size of the represetntation grows as O(n) instead of $O(n^2)$ \\ \n",
        "This means conditional indepdence assertions can allow probabilitistic systems to scale up; they are more commonly available than absolute\\\n",
        "indepdence.  Conceptually, Caivty separates Toothache and Catch because is it a direct cause of both of them.\n",
        "\n",
        "\"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here Naive Bayes, naive because it is often used in cases where the effect variables are not strictly independent given the \\\n",
        "cause variable.\"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" Module10_lecture_summary: unigram uses no history, bigram useus 1 word as history, \\\n",
        "trigram uses 2 words as history, 4-gram uses 3 words as history...n-gram models insufficient because language has \\\n",
        "long-distance dependencies.  Estimating bigram probabilities (the maximum likelihood estimate) \\\n",
        "$P(w_i|w_{i-1} = \\\\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$\\\n",
        "Problems for maximi=um likelihood estimate is lots of zero probabilities with out of vocabulary items.  Fixed lexicon L of size V.\\\n",
        "Avoid zeros with smoothing.  Use log space for probabilties to avoid underflow (super small numbers). \\ \n",
        "\n",
        "$log(p_1 * p_2) = logp_1 + logp_2$\n",
        "\n",
        "\n",
        "What we need for Naive Bayes: inference method (start with bunch of probabilities, use std inference), estimate local conditional\\\n",
        "probability tables.  These probabilities are collectively called the parameters\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Random variables\" : \"variables in probability space, represented with capital letters\",\n",
        "\"product rule\" : \"$P(a \\land b) = P(a|b)P(b)$ or $P(a \\land b) = P(b|a)P(a)$\",\n",
        "\"Bernoulli distribution\" : \"variable value is either 0 or 1\",\n",
        "\"probability density function\" : \"probability weighted representation of random variable value at x\",\n",
        "\"inclusion-exclusion principle\" : \"$P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\",\n",
        "\"marginal probability\" : \"probability of an event regardless of the outcome of another variable\",\n",
        "\"bad of words Naive Bayes\" : \"model is insensitive to word order or reordering\",\n",
        "\"extrinsic language model evaluation\" : \"dependent on application or against different model\",\n",
        "\"intrinsic language model evaluation\" : \"measures quality of model irrespective of the application\",\n",
        "\"perplexity\" : \"inverse  probability of the test set normalized by the number of words\",\n",
        "\"\" : \"\",\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter12_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter12_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter12_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter12_2))\n",
        "\n",
        "print(\"The length in words is\", len(chapter12_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter12_3))\n",
        "\n",
        "print(\"The 12.4 length in words is\", len(chapter12_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter12_4))\n",
        "\n",
        "print(\"The 12.5 length in words is\", len(chapter12_5.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter12_5))\n",
        "\n",
        "print(\"The 3.1 length in words is\", len(SLP_chapter3_1.split(' ')))\n",
        "print(\"The length in characters is\", len(SLP_chapter3_1))\n",
        "\n",
        "print(\"The lecture length in words is\", len(module10_lecture_notes.split(' ')))\n",
        "print(\"The lecture length in characters is\", len(module10_lecture_notes))\n",
        "\n",
        "\n"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 5\n",
            "The length in characters is 19\n",
            "The length in words is 5\n",
            "The length in characters is 19\n",
            "The length in words is 5\n",
            "The length in characters is 19\n",
            "The 12.4 length in words is 5\n",
            "The length in characters is 19\n",
            "The 12.5 length in words is 345\n",
            "The length in characters is 2253\n",
            "The 3.1 length in words is 5\n",
            "The length in characters is 19\n",
            "The lecture length in words is 113\n",
            "The lecture length in characters is 834\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "3bd709af-e242-4b61-afcd-16e00238e416"
      },
      "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": 24,
      "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 Chapter 12.5 summary: Applying Bayes’ rule: The simple case\nOn the surface, Bayes’ rule does not seem very useful. It allows us to compute the single\nterm P(b | a) in terms of three terms: P(a | b), P(b), and P(a). That seems like two steps\nbackwards, but Bayes’ rule is useful in practice because there are many cases where we do\nhave good probability estimates for these three numbers and need to compute the fourth.\nOften, we perceive as evidence the effect of some unknown cause and we would like to\ndetermine that cause. In that case, Bayes’ rule becomes\n$P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}$ The conditional probability P(effect | cause) quantifies the relationship in the causal direction, whereas P(cause | effect) describes the diagnostic direction. In a task such as medical diagnosis, we often have conditional probabilities on causal relationships (that is, the doctor knows P(symptoms | disease)) and want to derive a diagnosis, P(disease | symptoms). For\nexample, a doctor knows that the disease meningitis causes the patient to have a stiff neck, say, 70% of the time. \nThe doctor also knows some unconditional facts: the prior probability that a patient has meningitis is 1/50,000, and the prior probability that any patient has a stiff neck is 1%. Letting s be the proposition that the patient has a stiff neck and m be the\nproposition that the patient has meningitis, we have\nP(s|m)=0.7\nP(m)=1/50000\nP(s)=0.01\n$P(m|s) = \\frac{P(s|m)P(m)}{P(s)} = \\frac{0.7 × 1/50000}{0.01} = 0.0014$\nThat is, we expect less than 1 in 700 patients with a stiff neck to have meningitis. Notice that\neven though a stiff neck is quite strongly indicated by meningitis (with probability 0.7), the\nprobability of meningitis in the patient remains small. This is because the prior probability of\nstiff necks is much higher than that of meningitis. \n\nfor n symptoms that are all conditionally indepdent given Cavity, the size of the represetntation grows as O(n) instead of $O(n^2)$ \\ \nThis means conditional indepdence assertions can allow probabilitistic systems to scale up; they are more commonly available than absoluteindepdence.  Conceptually, Caivty separates Toothache and Catch because is it a direct cause of both of them.\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here Naive Bayes, naive because it is often used in cases where the effect variables are not strictly independent given the cause variable.\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Module10_lecture_summary: unigram uses no history, bigram useus 1 word as history, trigram uses 2 words as history, 4-gram uses 3 words as history...n-gram models insufficient because language has long-distance dependencies.  Estimating bigram probabilities (the maximum likelihood estimate) $P(w_i|w_{i-1} = \\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$Problems for maximi=um likelihood estimate is lots of zero probabilities with out of vocabulary items.  Fixed lexicon L of size V.Avoid zeros with smoothing.  Use log space for probabilties to avoid underflow (super small numbers). \\ \n\n$log(p_1 * p_2) = logp_1 + logp_2$\n\n\nWhat we need for Naive Bayes: inference method (start with bunch of probabilities, use std inference), estimate local conditionalprobability tables.  These probabilities are collectively called the parameters\n\n\n## Module 10 Definitions\n* **Random variables** - variables in probability space, represented with capital letters\n* **Product rule** - $P(a \\land b) = P(a|b)P(b)$ or $P(a \\land b) = P(b|a)P(a)$\n* **Bernoulli distribution** - variable value is either 0 or 1\n* **Probability density function** - probability weighted representation of random variable value at x\n* **Inclusion-exclusion principle** - $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n* **Marginal probability** - probability of an event regardless of the outcome of another variable\n* **Bad of words naive bayes** - model is insensitive to word order or reordering\n* **Extrinsic language model evaluation** - dependent on application or against different model\n* **Intrinsic language model evaluation** - measures quality of model irrespective of the application\n* **Perplexity** - inverse  probability of the test set normalized by the number of words\n* **** - \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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d3fcd9b8-0b8e-4ff8-ef95-c071c70b74b1"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" Module 11 summary:  Active/Inactive paths, Question: are X and Y conditionally \\\n",
        "indepdent given evidence variables {Z}?  Yes, if X and Y 'D-separated' by Z.  Consider all (undirected) paths from X to Y. \\\n",
        "No active paths = independence.  A path is active if each triple is active:  Causal chain A -> B -> C -> where B is unobserved \\\n",
        "in (either direction).  Common effect (aka v-structure).  A->B<-C where B or one of its descendents is observed.\n",
        "\n",
        "All it takes to block a path is a single inactive segment.\n",
        "\n",
        "Given a Bayes net structure, can run d-separation algorithm to build a complete list of conditional independences that are \\\n",
        "necessarily true of the form $X_i \\independent X_j | {X_{k_1}, ... , X_{k_n}}$\n",
        "\n",
        "Inference by enumeration is slow.  You join up the whole joint distribution before you sum out the hidden variables. \\\n",
        "Variable elimination interleave joining and marginalizing.  Still NP-hard, but usually faster than inference by enumeration.\n",
        "\n",
        "MIRA(margin infused related algorithm)...adjust the weight update to mitigate the overfitting \\\n",
        "$\\tau = \\frac{w^'_y - w^'_y* * f + 1}{2f * f}$\n",
        "maximum step size would be $tau^* = min(tau, c)$ where c is some constant \\ \n",
        "\n",
        "XOR problem:  single layer neural network cannot be used to computer XOR.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"hidden variables\" : \"Bayes net variales, neither input or output but used to keep network sparse\",\n",
        "\"Gibbs sampling\" : \"form of monte carlo markov chain algo that generates a sequence of observations approximated from specified distribution\",\n",
        "\"variable elimination algorithm\" : \"form of dynamic programming\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",  \n",
        "}\n",
        "\n",
        "\n",
        "print(\"The length in words is\", len(chapter13_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter13_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter13_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter13_2))\n",
        "\n",
        "print(\"The length in words is\", len(chapter13_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter13_3))\n",
        "\n",
        "\n",
        "print(\"The lecture length in words is\", len(module11_lecture_notes.split(' ')))\n",
        "print(\"The lecture length in characters is\", len(module11_lecture_notes))\n",
        "\n",
        "\n"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 5\n",
            "The length in characters is 19\n",
            "The length in words is 5\n",
            "The length in characters is 19\n",
            "The length in words is 5\n",
            "The length in characters is 19\n",
            "The lecture length in words is 208\n",
            "The lecture length in characters is 1242\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 670
        },
        "cellView": "form",
        "outputId": "a8e1d60b-710a-43a8-f945-c717a577b63a"
      },
      "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": 26,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Module 11 summary:  Active/Inactive paths, Question: are X and Y conditionally indepdent given evidence variables {Z}?  Yes, if X and Y 'D-separated' by Z.  Consider all (undirected) paths from X to Y. No active paths = independence.  A path is active if each triple is active:  Causal chain A -> B -> C -> where B is unobserved in (either direction).  Common effect (aka v-structure).  A->B<-C where B or one of its descendents is observed.\n\nAll it takes to block a path is a single inactive segment.\n\nGiven a Bayes net structure, can run d-separation algorithm to build a complete list of conditional independences that are necessarily true of the form $X_i \\independent X_j | {X_{k_1}, ... , X_{k_n}}$\n\nInference by enumeration is slow.  You join up the whole joint distribution before you sum out the hidden variables. Variable elimination interleave joining and marginalizing.  Still NP-hard, but usually faster than inference by enumeration.\n\nMIRA(margin infused related algorithm)...adjust the weight update to mitigate the overfitting $\tau = \frac{w^'_y - w^'_y* * f + 1}{2f * f}$\nmaximum step size would be $tau^* = min(tau, c)$ where c is some constant \\ \n\nXOR problem:  single layer neural network cannot be used to computer XOR.\n\n\n\n## Module 11 Definitions\n* **Hidden variables** - Bayes net variales, neither input or output but used to keep network sparse\n* **Gibbs sampling** - form of monte carlo markov chain algo that generates a sequence of observations approximated from specified distribution\n* **Variable elimination algorithm** - form of dynamic programming\n* **** - \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 = \"\"\" Forms of learning \"\"\"\n",
        "chapter19_2 = \"\"\" Supervised learning \"\"\"\n",
        "chapter19_3 = \"\"\" Learning decision trees \"\"\"\n",
        "chapter19_4 = \"\"\" Model selection and optimization \"\"\"\n",
        "chapter19_5 = \"\"\" Theory of learning -  \"\"\"\n",
        "chapter19_6 = \"\"\" Linear regression and classification \"\"\"\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 = \"\"\" Chapter 4.7 summary:  metrics addresses accuracy of %system detected vs gold labels.\\\n",
        "$F-measure = \\\\frac{(\\beta^2 + 1)PR}{\\beta^2P + R}$, where \\beta weights relative importance of precision and recall \\\n",
        "Values of \\beta > 1 favor recall and values of \\beta < 1 favor precision.  Most common to set \\beta = 1, equally \\\n",
        "weighting precision and recall.\"\"\"\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 = \"\"\" Module 12 summary:  \n",
        "Laplace performs poorly for P(X|Y) when |X| is large or |Y| is large. \\\n",
        "Perceptrons/MIRA vs Naive Bayes:  makes less assumptions about data, mistake \\\n",
        "driven learning, multiple passes through data (prediction), often more accurate.\\\n",
        "Naive Bayes builds model training data, gives prediction probabilities, strong \\\n",
        "assumptions about feature independence and one pass through data (counting).\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"precision\" : \"\\\\frac{true positives}{true positives + false positives}\",\n",
        "\"recall\" : \"\\\\frac{true positives}{true positives + false negatives}\",\n",
        "\"F-measure\" : \"incorporates both precision and recall\",\n",
        "\"\" : \"\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "638c015c-99f7-4c2a-80ed-b7a0f4110ec0"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1 Forms of Learning\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2 Supervised Learning\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3 Learning Decision Trees\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4 Model Selection and Optimization\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5 Theory of Learning\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6 Linear Regression and Classification\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n Forms of learning \n\n## AIMA Chapter 19.2 Supervised Learning\n Supervised learning \n\n## AIMA Chapter 19.3 Learning Decision Trees\n Learning decision trees \n\n## AIMA Chapter 19.4 Model Selection and Optimization\n Model selection and optimization \n\n## AIMA Chapter 19.5 Theory of Learning\n Theory of learning -  \n\n## AIMA Chapter 19.6 Linear Regression and Classification\n Linear regression and classification \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 Chapter 4.7 summary:  metrics addresses accuracy of %system detected vs gold labels.$F-measure = \\frac{(\beta^2 + 1)PR}{\beta^2P + R}$, where \beta weights relative importance of precision and recall Values of \beta > 1 favor recall and values of \beta < 1 favor precision.  Most common to set \beta = 1, equally weighting precision and recall.\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 Module 12 summary:  \nLaplace performs poorly for P(X|Y) when |X| is large or |Y| is large. Perceptrons/MIRA vs Naive Bayes:  makes less assumptions about data, mistake driven learning, multiple passes through data (prediction), often more accurate.Naive Bayes builds model training data, gives prediction probabilities, strong assumptions about feature independence and one pass through data (counting).\n\n## Module 12 Definitions\n* **** - \n* **Precision** - \\frac{true positives}{true positives + false positives}\n* **Recall** - \\frac{true positives}{true positives + false negatives}\n* **F-measure** - incorporates both precision and recall\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 = \"\"\" XOR is not a linearly separable function. But it can be calcuated by a layered \\\n",
        "network of units. \"\"\"\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 = \"\"\" Module13 lecture summary:  Activiation funds output activation values.  summation of w*x*b isn't\\\n",
        "output directly since it would be a linear function of x.  Neuron units apply a non-linear function f to z.  3 common non-linear \\\n",
        "functions used for f include: sigmoid function, tanh function and rectified linear unit ReLU.\n",
        "\n",
        "To train neural networks, we need:  a loss function (cross-entropy loss), an optimization algorithm (gradient descent) and \\\n",
        "a way of computing the gradient of the loss function\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"logistic regression\" : \"applies a logistic function to model a binary variable...binary regression\",\n",
        "\"regularization\" : \"used to reduce parameter values to address overfittin\",\n",
        "\"L2 regularization\" : \"quadratic function of weights, uses squared values, same as Euclidean distance\",\n",
        "\"L1 regularization\" : \"linear function of weights, sum of absolute values of the weights, Manhattan distance\",\n",
        "\"lasso regression\" : \"L1 regularization\",\n",
        "\"ridge regression\" : \"L2 regularization\",\n",
        "\"multinomial logistic regression\" : \"softmax regression\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",\n",
        "\"\" : \"\",    \n",
        "}\n"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "bee70962-57b6-407e-ef5c-651d921b665d"
      },
      "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": 30,
      "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 XOR is not a linearly separable function. But it can be calcuated by a layered network of units. \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 Module13 lecture summary:  Activiation funds output activation values.  summation of w*x*b isn'toutput directly since it would be a linear function of x.  Neuron units apply a non-linear function f to z.  3 common non-linear functions used for f include: sigmoid function, tanh function and rectified linear unit ReLU.\n\nTo train neural networks, we need:  a loss function (cross-entropy loss), an optimization algorithm (gradient descent) and a way of computing the gradient of the loss function\n \n\n## Module 13 Definitions\n* **Logistic regression** - applies a logistic function to model a binary variable...binary regression\n* **Regularization** - used to reduce parameter values to address overfittin\n* **L2 regularization** - quadratic function of weights, uses squared values, same as Euclidean distance\n* **L1 regularization** - linear function of weights, sum of absolute values of the weights, Manhattan distance\n* **Lasso regression** - L1 regularization\n* **Ridge regression** - L2 regularization\n* **Multinomial logistic regression** - softmax regression\n* **** - \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 = \"\"\" Vectors representing words are called embeddings.  We can visual the embeddings to see related \\\n",
        "words clustered closer to each other.\"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Module 14 lecture summary:  TF-IDF is alternative to raw count, \\\n",
        "TF-IDF = term frequency * inverse document frequency, where term frequency is how often a word occurred in a document \\\n",
        "inverse document frequency is 1 over the number of documents that it occurred in.  For example, this is handy when \\\n",
        "something like \"the\" occurs frequently but offers little insight. \n",
        "\n",
        "Word embedding, negative sampling example: \\\n",
        "lemon, a [tablespoon{c1} of{c2} apricot{w} preserves{c3} or{c4} ] jam...we want predictions of these words to be high\\\n",
        "\n",
        "we want these words to be low:\\\n",
        "[cement metaphysical dead coaxial apriot aattendant when forever puddle] use neural network to increase or decrease \\\n",
        "similarity scores.\n",
        "\n",
        "Advantages of NN LM's:  better results (better preplexity), can scale to larger orders of N since they deal with individual \\\n",
        "words and not n-grams.  They can generalize across contexts.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"Dense vector\" : \"most elements are non-zero\",\n",
        "\"sparse vector\" : \"most elements are zero\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "97c9b245-ed8a-492a-d5bf-0a30f4003245"
      },
      "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",
        "  (\"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": 32,
      "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 Vectors representing words are called embeddings.  We can visual the embeddings to see related words clustered closer to each other.\n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Module13 lecture summary:  Activiation funds output activation values.  summation of w*x*b isn'toutput directly since it would be a linear function of x.  Neuron units apply a non-linear function f to z.  3 common non-linear functions used for f include: sigmoid function, tanh function and rectified linear unit ReLU.\n\nTo train neural networks, we need:  a loss function (cross-entropy loss), an optimization algorithm (gradient descent) and a way of computing the gradient of the loss function\n \n\n## Module 14 Definitions\n* **Dense vector** - most elements are non-zero\n* **Sparse vector** - most elements are zero\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": "df285d92-0822-4464-f164-00c2d8a000fc"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary: \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Chapter 16.2 summary:  The primary issue for utility theory is to understand how preferences between complex lotteries \nare related to preferences between the underlying states in those lotteries. To address this issue \nwe list six constraints that we require any reasonable preference relation to obey: \nORDERABILITY: Given any two lotteries, a rational agent must either prefer one \nto the other or else rate the two as equally preferable. That is, the agent cannot avoid deciding. \nAs we said on page 490, refusing to bet is like refusing to allow time to pass. Exactly one of (A ' \nB), (B ' A), or (A ? B) holds. \nTRANSITIVITY: Given any three lotteries, if an \nagent prefers A to B and prefers B to C, then the agent must prefer A to C. (A ' B) ? (B ' C) ? (A \n' C) . \nCONTINUITY: If some lottery B is between A and C in preference, then there \nis some probability p for which the rational agent will be indifferent between getting B for sure \nand the lottery that yields A with probability p and C with probability 1 ? p. A ' B ' C ? ? p [p, \nA; 1 ? p, C] ? B . \nSUBSTITUTABILITY: If an agent is indifferent between \ntwo lotteries A and B, then the agent is indifferent between two more complex lotteries that are \nthe same except that B 2 We apologize to readers whose local airlines no longer offer food on \nlong flights. Section 16.2. The Basis of Utility Theory 613 is substituted for A in one of them. \nThis holds regardless of the probabilities and the other outcome(s) in the lotteries. A ? B ? [p, \nA; 1 ? p, C] ? [p, B; 1 ? p, C] . This also holds if we substitute ' for ? in this axiom. \nMONOTONICITY: Suppose two lotteries have the same two possible outcomes, \nA and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher \nprobability for A (and vice versa). A ' B ? (p>q ? [p, A; 1 ? p, B] ' [q, A; 1 ? q,B]). \nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones \nusing the laws of probability. This has been called the no fun in gambling rule because it says \nthat two consecutive lotteries can be compressed into a single equivalent lottery, as shown in \nFigure 16.1(b).3 [p, A; 1 ? p, [q,B; 1 ? q, C]] ? [p, A; (1 ? p)q,B; (1 ? p)(1 ? q), C] . These \nconstraints are known as the axioms of utility theory. Each axiom can be motivated by showing \nthat an agent that violates it will exhibit patently irrational behavior in some situations. \n\n## AIMA Chapter 16.3 Utility Functions\n Chapter 16.3 summary: \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Chapter 17.1 summary:  \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Chapter 17.2 summary: There is direct relation btwn\nutility of a state and the utility of its neighbors: the utility of a state is immediate reward\nfor that state plus the exp discounted utility of the next state. The utility of a state is given by\n$U(s) = R(s) + γ max_{a∈A(s)}s P(s | s, a)U(s)$\nThe utilities of thestates—defined as the expected utility of subsequent state sequences—are\nsolutions of the set of Bellman eq.\nLet us look at one of the Bellman eqs for the 4 × 3 world. The equation for the\nstate (1,1) is\nU(1, 1) = −0.04 + γ max[ 0.8U(1, 2) + 0.1U(2, 1) + 0.1U(1, 1), (Up)\n0.9U(1, 1) + 0.1U(1, 2), (Left)\n0.9U(1, 1) + 0.1U(2, 1), (Down)\n0.8U(2, 1) + 0.1U(1, 2) + 0.1U(1, 1) ]. (Right)\nUp is the best action.\nThe value iteration algorithm\nThe Bellman eq is basis of value iteration algorithm for MDPs. With n possible states, \nthere are n Bellman eqs, one for each state. The n equations\ncontain n unknowns—the utilities of the states. So we would like to solve these simultaneous\nequations to find the utilities. The equations are nonlinear, because the\n“max” operator is not a linear operator. So try an iterative approach. Start with arbitrary initial values for the utilities,\ncalculate the right-hand side of the equation, and plug it into the left-hand side—thereby\nupdating the utility of each state from the utilities of its neighbors. We repeat this until we\nreach an equilibrium. Let Ui(s) be the utility value for state s at the ith iteration. The iteration\nBELLMAN UPDATE step, called a Bellman update, looks like this:\nUi+1(s) ← R(s) + γ max_{a∈A(s)} SUMMATION P(s | s, a)Ui(s)\n\n\n## Module 8 Lecture Notes\n Module 8 summary: Only two ways to define utilities, additive or discounted additive_utility = $U([r_0,r_1,r_2,...]) = r_0 + r_1 + r_2 + ...$  discounted_utility = $U([r_0,r_1,r_2,...]) = r_0 + gamma * r_1 + gamma^2 * r_2 + ...$  additive discounted rewards utility of a history = $U_h([s_0,a_0,s_1,a_1,s_2,a_2,...])$ = $R(s_0,a_0,_s_1) + gamma * R(s_1,a_1,_s_2) + gamma^2 * R(s_2,a_2,_s_3) + ...$ $U(s) = \\max_{a} Q(s,a)$ \n$\\pi^*(s) = \u0007rgmax Q(s,a)$ \nRepresenting MDP, 3D table for $P(s^'|s,a)$ and $R(s,a,s^')$ \nProblem:  What if the game lasts forever?  Do we get infinite rewards? Solution: finite horizon (like depth limited search), terminate after fixed steps, gives nonstationary policies since dependent on time left.  Discount between 0 and 1.  Smaller discount means smaller horizon. Policy iteration vs value iteration...PI starts with random policy algorithm is more complex, guaranteed to converge, cheaper to computer, requires few iterations to converge and faster. Value iteration starts with random value function, algo is simpler, gtd to converge, more expensive to compute $O(S^2A)$ \nrequires more iterations to converge and slower.\n\n## Module 8 Definitions\n* **Utility function** - captures agent's preferences\n* **Expected utility** - avg utility value of outcomes accounting for outcome probability\n* **Policy loss** - Most an agent can underperform the optimal policy by choosing a non optimal policy\n* **Sequential decision problems** - agent utility is function of sequence of decisions\n* **Transition model** - defines outcome of each action in each state\n* **Markovian** - probability of reading $s^'$ from $s$ depends only on $s$ and not on the history of earlier states\n* **Reward** - $R(s,a,s^')$ rewards can be positive or negative bounded by +/-$R_\\mathrm{max}$\n* **Markov decision process** - sequential decision problem in fully observable stochastic environment with Markovian transition model and additive rewards\n* **Dynamic programming** - problem simplification, recursively breaks it into smaller pieces, remembering optimal solutions to pieces\n* **Policy** - maps how the agent should act for any state that the agent might reach\n* **Optimal policy** - policy that maximizes expected utility\n* **Nonstationary** - In finite horizon, best action given a state may be a function of how much time is left\n* **Stationary** - optimal policy is stationary if it does not behave differently in same state at different times\n* **Additive discounted rewards** - used to calculate utility of state sequences\n* **Discount factor** - between 0 and 1.  discount close to 0 means rewards in distant future as less attractive.\n* **Proper policy** -  policy gtd to reach a terminal state\n* **Bellman equation** - current state utility is expected reward from next transition plus discounted utility of next state\n* **Q-function (action-utility function)** - Q(s,a) is the expected utility of taking a given action in a given state\n* **Shaping theorem** - relates to fact that additive reward decomposition of tulities leads to more freedom in describing rewards\n* **Sparse** - most entries are zeros, table representation still $O(|S||A|)$\n* **Value iteration** - algo for solving MDP, exact solutions offline, we coputer the optimal state value function by iterating over $v(s)$estimate updates \n* **Policy iteration** - algo for solving MDP, exact solutions offline, start by choosing arbitrary policy $\\pi$ and iteratively evaluate and improve the policy until convergence\n* **Linear programming** - algo for solving MDP, exact solutions offline\n* **Monte carlo programming** - family of online algos for solving MDP\n* **Bellman update** - iteration step, update applied simultaneously to all states at each iteration\n* **Contraction** - shows value iteration converges, has only one fixed point, function value must get closer to the fixed point\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Chapter 17.3 summary:  It is possible to get an optimal policy when the utility function estimate is inaccurate. If one action is better than others, then the magnitude of utilities on the states need not be precise...alternative way to find optimal policies. The policy iteration algorithm alternates the following two steps, beginning from some initial policy $\\pi_0$: \n\nPolicy evaluation: given a policy \\pi_i, calc Ui = Uπi , the utility of each state if πi were to be executed. \nPolicy improvement: Calc a new MEU policy pi_{i+1}, using one-step look-ahead POLICY based on Ui.The algo terminates when policy improvement step yields no change in the utilities. We know that utility function Ui is a fixed point of Bellman update, so it is a solution to Bellman eqs, and πi must be an optimal policy. Finite state space has finite many policies, and each iteration can be shown to yield a better policy, policy iteration must terminate. The policy improvement step is obviously straightforward.  Implementing policy evaluation  is much simpler than solving the standard Bellman eqs (which is what value iteration does), because the action in each state is fixed by the policy.  Important point is these eqs are linear, because the “max” operator has beenremoved. For n states, we have n linear eqs with n unknowns, which can be solved exactly in time $O(n^3)$ by std linear algebra.\n\n## AIMA Chapter 22.1 Learning from Rewards\n Chapter 22.1 summary:  Same goal as MDP to maximize the exp sum of rewards, but reinforcement learning differs from from 'just solving an MDP' because the agent is not given the MDP as a problem to solve.  The agent is in 'in' the MDP.  It may not know the transition model or the reward function.  \n\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Chapter 22.2 summary: Passive learning task is similar to the policy evaluation task, part of the policy iteration algo. The difference is that the passive learning agent does not know the transition model $P(s^'|s,a)$ which specifies the probability of reaching state $s'$from state s after doing action s; nor does it know the reward function $R(s,a,s^')$, the reward for each transition.\n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Chapter 22.3 summary: Here, f(u, n) is called the exploration function. It determines how greed (preference for\nhigh values of u) is traded off against curiosity (preference for actions that have not been\ntried often and have low n). The function f(u, n) should be increasing in u and decreasing\nin n. Obviously, there are many possible functions that fit these conditions. One particularly\nsimple definition is\nf(u, n) = \u0018 R+ if n<Ne\nu otherwise\nwhere R+ is an optimistic estimate of the best possible reward obtainable in any state and Ne\nis a fixed parameter. This will have the effect of making the agent try each action–state pair\nat least Ne times.\n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Chapter 22.4 summary: \n\n## AIMA Chapter 22.5 Policy Search\n Chapter 22.5 summary: Policy search is the simplest of all the methods in this chapter: the idea is to keep twiddling the policy as long as its performance improves, then stop. Let us begin with the policies themselves. Remember that a policy π is a function that maps states to actions. We are interested primarily in parameterized representations of π that have far fewer parameters than there are states in the state space (just as in the preceding section). For example, we could represent π by a collection of parameterized Q-functions, one for each action, and take the action with the highest predicted value: π(s) = maxa Qˆθ(s, a).\n\nEach Q-function could be a linear function of the parameters θ, or it could be a nonlinear function such as a neural network. Policy search will then adjust the parameters θ to improve the policy. Notice that if the policy is represented by Qfunctions, then policy search results in a process that learns Q-functions. This process is not the same as Q-learning! In Q-learning with function approximation, the algorithm finds a value of θ such that Qˆθ is “close” to Q∗, the optimal Q-function. Policy search, on the other hand, finds a value of θ that results in good performance; the values found by the two methods may differ very substantially. \nOne problem with policy representations of the kind given in Equation (21.14) is that\nthere will be values of θ such that an infinitesimal change in θ causes the policy to switch from one\naction to another. This means that the value of the policy may also change discontinuously,\nwhich makes gradient-based search difficult. For this reason, policy search methods often use\nstochastic policy representation πθ(s, a), which specifies the probability of selecting action\nSOFTMAX FUNCTION a in state s. One popular representation is the softmax function:\nπθ(s, a) = eQˆθ(s,a)/aeQˆθ(s,a).\nSoftmax becomes nearly deterministic if one action is much better than the others, but it\nalways gives a differentiable function of θ; hence, the value of the policy (which depends in\nSection 21.5. Policy Search 849\na continuous fashion on the action selection probabilities) is a differentiable function of θ.\nSoftmax is a generalization of the logistic function to multiple variables.\n\n## Module 9 Lecture Notes\n Summary:  exploration is you have to try unknown actions to get information.  Exploitation eventually you have to use what you know.  Regret...even if you learn intelligently, you make mistakes.  Sampling...because of chance, you try things repeatedly.  Regret is the difference between your expected rewards, including youthful suboptimality and optimal expected rewards.  Minimizing regret requiresoptimally learning to be optimal.  Random exploration and exploration functions both end up optimal, but random exploration has higher regret. Difficulty...learning can be much harder than solving a known MDP. Temporal difference learning...learn from every experience.  $V(s)$ is updated everytime we experience a transition $(s, a, s^', r)$.  Direct evaluation's goal is to compute the values for each state under \\pi by averaging together observed sample values.  Act according to \\pi, everytime you visit a state, write down what the sum of the discounted rewards turned out to be.Average those samples.  Direct evaluation is easy to understand, doesn't require any knowledge of T,R and eventually computes the correct avg values.  Direct evaluation wastes info about state connections, each state is learned separately and it takes a long time. Q-learning converges to optimal policy - even if you're activing suboptimally...this is called off-policy learning...caveats...you have to explore enough, you have to eventually make the learning rate small enough (but not decrease too quickly), basically in the limit it doesn't matter how you select actions\n\n## Module 9 Definitions\n* **Term** - your definition here\n* **Policy iteration** - algo to learn optimal policy which maximizes long term discounted reward\n* **Policy evaluation** - given a policy, calculate the utility of each state assuming we used that policy\n* **Policy improvement** - Use a new MEU policy and iterate one-step at a time looking ahead current utility\n* **Dynamic decision networks (ddn)** - factored representations extending dynamic bayesian networks with decision, reward and utility inputs\n* **Sparse rewards** - chess and racing example, majority of states no information\n* **Model based reinforcement learning** - agent applies transition model to environment to make decisions.  may develop transition model if not given\n* **Model-free reinforcement learning** - Does not get or learn transition model, uses: action-utility learning (Q-learning) and policy search\n* **Action-utility learning** - Most common form is Q-learning.  \n* **Q-learning** - agent leans Q-function representing sum of rewards from state s and onward if action a taken\n* **Policy search** - Easiest form of RL, keep fiddling with the policy as long as its performance continues to improve, otherwise stop\n* **Passive reinforcement learning** - Agent has fixed policy and must learn utilities of states (or state action pairs)\n* **Active reinforcement learning** - Agent must learn how to proceed in environment (exploration vs exploitation)\n* **Passive learning agent** - Tries to learn utility function starting at state s and total discounted reward from policy \\pi\n* **Reward-to-go** - expected sum of rewards from that state and future states\n* **Direct utility estimation** - utility is based the reward-to-go\n* **Adaptive dynamic programming** - uses constraints among state utilities by learning transition model that connects the states\n* **Curiosity** - type of reward function that uses prediction error as reward determinant\n* **Prioritized sweeping** - heuristic which favors adjustments to states whose likely successor have undergone large adjustment to their utility estimates\n* **Active learning agent** - Decides own actions to take, no fixed policy\n* **Greedy agent** - does not learn true utilities or the true optimal policy, takes what it think is optimal at each step\n* **Regret** - quantifies relative goodness of exploration procedures\n* **Absorbing state** - no actions have effects and no rewards received\n* **Off-policy** - Q-learing, willing to optimize by learning Q-values not necessarily based on current policy\n* **On-policy** - SARSA is on-policy, penalizes negative action, what is action worth in this state if I stick with policy?\n* **Catastrophic forgetting** - tendency for neutral network to forget information they learned.  Experience replay is a solution\n* **Reward shaping** - Supply agent with additional (smaller?) more frequent rewards (psuedorewards) along way to goals\n* **Softmax** - form of stochastic policy that specifies probability of choosing action a while in state s\n* **Policy value** - expected reward-to-go when a given policy is implemented\n* **Correlated sampling** - can be applied to policy search, number of random sequences depends on complexity of policy space not underlying domain\n* **** - \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 Chapter 12.5 summary: Applying Bayes’ rule: The simple case\nOn the surface, Bayes’ rule does not seem very useful. It allows us to compute the single\nterm P(b | a) in terms of three terms: P(a | b), P(b), and P(a). That seems like two steps\nbackwards, but Bayes’ rule is useful in practice because there are many cases where we do\nhave good probability estimates for these three numbers and need to compute the fourth.\nOften, we perceive as evidence the effect of some unknown cause and we would like to\ndetermine that cause. In that case, Bayes’ rule becomes\n$P(cause|effect) = \\frac{P(effect|cause)P(cause)}{P(effect)}$ The conditional probability P(effect | cause) quantifies the relationship in the causal direction, whereas P(cause | effect) describes the diagnostic direction. In a task such as medical diagnosis, we often have conditional probabilities on causal relationships (that is, the doctor knows P(symptoms | disease)) and want to derive a diagnosis, P(disease | symptoms). For\nexample, a doctor knows that the disease meningitis causes the patient to have a stiff neck, say, 70% of the time. \nThe doctor also knows some unconditional facts: the prior probability that a patient has meningitis is 1/50,000, and the prior probability that any patient has a stiff neck is 1%. Letting s be the proposition that the patient has a stiff neck and m be the\nproposition that the patient has meningitis, we have\nP(s|m)=0.7\nP(m)=1/50000\nP(s)=0.01\n$P(m|s) = \\frac{P(s|m)P(m)}{P(s)} = \\frac{0.7 × 1/50000}{0.01} = 0.0014$\nThat is, we expect less than 1 in 700 patients with a stiff neck to have meningitis. Notice that\neven though a stiff neck is quite strongly indicated by meningitis (with probability 0.7), the\nprobability of meningitis in the patient remains small. This is because the prior probability of\nstiff necks is much higher than that of meningitis. \n\nfor n symptoms that are all conditionally indepdent given Cavity, the size of the represetntation grows as O(n) instead of $O(n^2)$ \\ \nThis means conditional indepdence assertions can allow probabilitistic systems to scale up; they are more commonly available than absoluteindepdence.  Conceptually, Caivty separates Toothache and Catch because is it a direct cause of both of them.\n\n\n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here Naive Bayes, naive because it is often used in cases where the effect variables are not strictly independent given the cause variable.\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n Module10_lecture_summary: unigram uses no history, bigram useus 1 word as history, trigram uses 2 words as history, 4-gram uses 3 words as history...n-gram models insufficient because language has long-distance dependencies.  Estimating bigram probabilities (the maximum likelihood estimate) $P(w_i|w_{i-1} = \\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$Problems for maximi=um likelihood estimate is lots of zero probabilities with out of vocabulary items.  Fixed lexicon L of size V.Avoid zeros with smoothing.  Use log space for probabilties to avoid underflow (super small numbers). \\ \n\n$log(p_1 * p_2) = logp_1 + logp_2$\n\n\nWhat we need for Naive Bayes: inference method (start with bunch of probabilities, use std inference), estimate local conditionalprobability tables.  These probabilities are collectively called the parameters\n\n\n## Module 10 Definitions\n* **Random variables** - variables in probability space, represented with capital letters\n* **Product rule** - $P(a \\land b) = P(a|b)P(b)$ or $P(a \\land b) = P(b|a)P(a)$\n* **Bernoulli distribution** - variable value is either 0 or 1\n* **Probability density function** - probability weighted representation of random variable value at x\n* **Inclusion-exclusion principle** - $P(a \\lor b) = P(a) + P(b) - P(a \\land b)$\n* **Marginal probability** - probability of an event regardless of the outcome of another variable\n* **Bad of words naive bayes** - model is insensitive to word order or reordering\n* **Extrinsic language model evaluation** - dependent on application or against different model\n* **Intrinsic language model evaluation** - measures quality of model irrespective of the application\n* **Perplexity** - inverse  probability of the test set normalized by the number of words\n* **** - \n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n Module 11 summary:  Active/Inactive paths, Question: are X and Y conditionally indepdent given evidence variables {Z}?  Yes, if X and Y 'D-separated' by Z.  Consider all (undirected) paths from X to Y. No active paths = independence.  A path is active if each triple is active:  Causal chain A -> B -> C -> where B is unobserved in (either direction).  Common effect (aka v-structure).  A->B<-C where B or one of its descendents is observed.\n\nAll it takes to block a path is a single inactive segment.\n\nGiven a Bayes net structure, can run d-separation algorithm to build a complete list of conditional independences that are necessarily true of the form $X_i \\independent X_j | {X_{k_1}, ... , X_{k_n}}$\n\nInference by enumeration is slow.  You join up the whole joint distribution before you sum out the hidden variables. Variable elimination interleave joining and marginalizing.  Still NP-hard, but usually faster than inference by enumeration.\n\nMIRA(margin infused related algorithm)...adjust the weight update to mitigate the overfitting $\tau = \frac{w^'_y - w^'_y* * f + 1}{2f * f}$\nmaximum step size would be $tau^* = min(tau, c)$ where c is some constant \\ \n\nXOR problem:  single layer neural network cannot be used to computer XOR.\n\n\n\n## Module 11 Definitions\n* **Hidden variables** - Bayes net variales, neither input or output but used to keep network sparse\n* **Gibbs sampling** - form of monte carlo markov chain algo that generates a sequence of observations approximated from specified distribution\n* **Variable elimination algorithm** - form of dynamic programming\n* **** - \n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1 Forms of Learning\n Forms of learning \n\n## AIMA Chapter 19.2 Supervised Learning\n Supervised learning \n\n## AIMA Chapter 19.3 Learning Decision Trees\n Learning decision trees \n\n## AIMA Chapter 19.4 Model Selection and Optimization\n Model selection and optimization \n\n## AIMA Chapter 19.5 Theory of Learning\n Theory of learning -  \n\n## AIMA Chapter 19.6 Linear Regression and Classification\n Linear regression and classification \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 Chapter 4.7 summary:  metrics addresses accuracy of %system detected vs gold labels.$F-measure = \\frac{(\beta^2 + 1)PR}{\beta^2P + R}$, where \beta weights relative importance of precision and recall Values of \beta > 1 favor recall and values of \beta < 1 favor precision.  Most common to set \beta = 1, equally weighting precision and recall.\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 Module 12 summary:  \nLaplace performs poorly for P(X|Y) when |X| is large or |Y| is large. Perceptrons/MIRA vs Naive Bayes:  makes less assumptions about data, mistake driven learning, multiple passes through data (prediction), often more accurate.Naive Bayes builds model training data, gives prediction probabilities, strong assumptions about feature independence and one pass through data (counting).\n\n## Module 12 Definitions\n* **** - \n* **Precision** - \\frac{true positives}{true positives + false positives}\n* **Recall** - \\frac{true positives}{true positives + false negatives}\n* **F-measure** - incorporates both precision and recall\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 XOR is not a linearly separable function. But it can be calcuated by a layered network of units. \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 Module13 lecture summary:  Activiation funds output activation values.  summation of w*x*b isn'toutput directly since it would be a linear function of x.  Neuron units apply a non-linear function f to z.  3 common non-linear functions used for f include: sigmoid function, tanh function and rectified linear unit ReLU.\n\nTo train neural networks, we need:  a loss function (cross-entropy loss), an optimization algorithm (gradient descent) and a way of computing the gradient of the loss function\n \n\n## Module 13 Definitions\n* **Logistic regression** - applies a logistic function to model a binary variable...binary regression\n* **Regularization** - used to reduce parameter values to address overfittin\n* **L2 regularization** - quadratic function of weights, uses squared values, same as Euclidean distance\n* **L1 regularization** - linear function of weights, sum of absolute values of the weights, Manhattan distance\n* **Lasso regression** - L1 regularization\n* **Ridge regression** - L2 regularization\n* **Multinomial logistic regression** - softmax regression\n* **** - \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 Vectors representing words are called embeddings.  We can visual the embeddings to see related words clustered closer to each other.\n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n Module13 lecture summary:  Activiation funds output activation values.  summation of w*x*b isn'toutput directly since it would be a linear function of x.  Neuron units apply a non-linear function f to z.  3 common non-linear functions used for f include: sigmoid function, tanh function and rectified linear unit ReLU.\n\nTo train neural networks, we need:  a loss function (cross-entropy loss), an optimization algorithm (gradient descent) and a way of computing the gradient of the loss function\n \n\n## Module 14 Definitions\n* **Dense vector** - most elements are non-zero\n* **Sparse vector** - most elements are zero\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        ""
      ],
      "metadata": {
        "id": "ep6F2KjPOEDH"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from google.colab import drive\n",
        "drive.mount('/content/drive')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "N2MSlwHTNXd5",
        "outputId": "7008ede9-f3a8-4663-b90a-bb29e3e1267f"
      },
      "execution_count": 36,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Drive already mounted at /content/drive; to attempt to forcibly remount, call drive.mount(\"/content/drive\", force_remount=True).\n"
          ]
        }
      ]
    }
  ]
}