{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4c4031db-93ba-45cb-f16f-d4fafda3b681"
      },
      "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": 1,
      "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": "608b7aa8-c69d-4a96-bed7-97247f8286ea"
      },
      "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": 2,
      "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": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \"\"\"  + sample_equation\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "  Markovian Transition Models = Stochastic Transition Models\n",
        "    p(s' | s, a) or T(s, a, s')\n",
        "  Markov Decision Process is\n",
        "    a sequential decision problem\n",
        "    for a fully observal environment\n",
        "    with a stochastic transition model\n",
        "    that has additive rewards\n",
        "  MDPs are a non deterministic search problem => solve via expectimax search\n",
        "  To find a solution for MDPs, you need\n",
        "    Set of states S\n",
        "    Set of actions A\n",
        "    Transition function T(s, a, s')\n",
        "      probability p(s' | s, a), the probability is called the model\n",
        "    Reward function R(s, a, s')\n",
        "    Initial state s0\n",
        "    Optionally, one or more terminal states\n",
        "  Solution of an MDP is a policy pi(s) = a, in search problems called a plan\n",
        "    pi*(s) = a is optimal policy\n",
        "  Expected utility\n",
        "    Uh (of enviroment history) \n",
        "      Uh([s0, a0, s1, a1, ...])\n",
        "      = R(s0, a0, s1) + R(s1, a1, s2) + ...\n",
        "  Discounting\n",
        "    Prefer rewards now\n",
        "    Decays exponentially => 1, gamma, gamma^2, ...\n",
        "    Discount because sooner rewards probs have higher utility than later\n",
        "    Also helps algo converge\n",
        "  Stationary preference\n",
        "    [a1, a2, ...] > [b1, b2, ...] <=> [r, a1, a2, ...] > [r, b1, b2, ...]\n",
        "  If stationary preference, then only two ways to define utilities\n",
        "    Additive utility: U([r0, r1, r2, ...]) = r0 + r1 + r2\n",
        "    Discounted utility: U([r0, r1, r2, ...]) = r0 + gamma * r1, + gamma^2 * r2\n",
        "  Infinite Game Solutions\n",
        "    Finite horizon:\n",
        "      terminate after fixed T steps or\n",
        "      nonstationary policies (pi depends on time left)\n",
        "    Discounting: use 0 < gamma < 1\n",
        "      smaller gamma = smaller horizon\n",
        "    Absorbing state: guarantee that for every policy, a terminal state\n",
        "      will eventually be reached\n",
        "  Value (utility) of a state s = V*(s) acting optimally\n",
        "  Value of a q-state(s, a) = Q*(s, a)\n",
        "    expected utility starting out having taken action a from state s and\n",
        "    thereafter acting optimally\n",
        "  V*(s) = max_a Q*(s, a)\n",
        "  Q*(s, a) = sigma_s' T(s, a, s') [R(s, a, s') + gamma * V*(s')]\n",
        "  V*(s) = max_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n",
        "  Problem: states repeated and tree goes forever\n",
        "  Idea: Time-limited values\n",
        "    Define V_k(s) to be optimal value of s if the game ends in k time\n",
        "  Value iteration\n",
        "    Start with V_0(s) = 0\n",
        "    Given vector V_k(s), do one ply of expectimax\n",
        "    V_k+1 (s) <- max_a sigma_s' T(s, a, s')[R(s, a, s') + gamma V_k(s')]\n",
        "    repeat until convergence\n",
        "    Complexity of each iteration is O(S^2 * A)\n",
        "    Theorem: will converge to unique optimal values\n",
        "      approximations get refined towards optimal values\n",
        "      Policy may converge long before values do\n",
        "    Convergence\n",
        "      How do we know V_k will converge?\n",
        "        Case 1: if tree has max depth M, then V_M holds for actual untruncated\n",
        "          values\n",
        "        Case 2: if discount < 1\n",
        "          V_k and V_k+1 is viewed as depth k+1 expectimax results in nearly\n",
        "          identical search trees\n",
        "          bottom layer V_k+1 has actual rewards, V_k has zeros\n",
        "          last layer is at best all R_max, at worst R_min, but everything\n",
        "          is discounted by gamma^k\n",
        "          So V_k and V_k+1 differ at most gamma^k max |R|\n",
        "          as k increases, value converge\n",
        "  Bellman Equations\n",
        "    Definition of \"optimal utility\" via expectimax recurrence gives us\n",
        "    simple one-step lookahead relationship amongst optimal utility values\n",
        "    V*(s) = max_a Q*(s, a)\n",
        "    Q*(s, a) = sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n",
        "    V*(s) = max_a sigma_s' T(s, a, s') [R(s, a, s') + gamma * V*(s')]\n",
        "  Fixed Policies => do optimal action, do what pi says\n",
        "    For fixed policy pi,\n",
        "      V_pi(s) = sigma_s' T(s, pi(s), s')[R(s, pi(s), s') + gamma V^pi(s')]\n",
        "      How calculate?\n",
        "        idea 1: turn to updates\n",
        "          v_0^pi(s) = 0\n",
        "          v_k+w^pi(s) <- sum_s' T(s, pi(s), s')[R(,s pi(s), s') + \n",
        "                          gamma * V_k^pi(s')]\n",
        "        idea 2: just a linear system without maxes\n",
        "  Policy extraction\n",
        "    given optimal values V*(s), how act?\n",
        "    mini-expectimax (one step)\n",
        "    pi*(s) = argmax_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n",
        "    if given optimal q-values, trivial\n",
        "    pi*(s) = argmax_a Q*(s, a)\n",
        "  Problems with value iteration\n",
        "    repeats bellman updates\n",
        "    => slow - O(S^2 A) per iteration\n",
        "      max rarely changes\n",
        "      policy converges long before values\n",
        "    Alternative: Policy iteration\n",
        "      step 1: policy evaluation, calculate utilities for some fixed policy\n",
        "        (not optimal tho) until convergence\n",
        "      step 2: policy improvement, update policy using one-step look-ahead with\n",
        "        resulting converged but not optimal utilities as future values\n",
        "      repeat until converges\n",
        "      still optimal and can converge much faster\n",
        "      Evaluation: for fixed current policy pi, find values with policy\n",
        "        evaluation (iterate until values converge)\n",
        "        v^(pi_i)_k+1(s) <- \n",
        "          sigma_s' T(s, pi_i(s), s')[R(s, pi_i(s), s')+gamma * V_k^(pi_i)(s')]\n",
        "        improvement, for fixed values get better policy using policy extraction\n",
        "          one step lookahead\n",
        "          pi_i+1(s) = \n",
        "            argmax_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V^(pi_i)(s')]\n",
        "  Comparison\n",
        "    Both value/policy compute same thing (optimal values)\n",
        "    Value iteration:\n",
        "      every iteration updates both the value and implicitly the policy\n",
        "      dont track policy but taking max over actions implicitly recomputes it\n",
        "    policy iteration:\n",
        "      several passes that update utilities with fixed policy\n",
        "        pass is fast bc only condier one action not all\n",
        "      after policy evaluated, new policy chosen (slow like value iter pass)\n",
        "      new policy will be better (or done)\n",
        "    both are dynamic programs for solving MDPs\n",
        "  Summary\n",
        "    compute optimal values: use value iter or policy iter\n",
        "    compute val for particular policy: policy evaluation\n",
        "    turn values into policy: policy extraction (one-step lookahead)\n",
        "    all variations of bellman updates\n",
        "    all use one-step lookahead expectimax fragments\n",
        "    differ only whether we plug in fixed policy or max over actions\n",
        "  Utilities\n",
        "    Why average utilities? instead of minimax\n",
        "    Principle of maximum expected utility\n",
        "    What utilities to use?\n",
        "      for worst case, terminal functrion scale doesnt matter\n",
        "      i.e. insensitivity to monotonic transformations\n",
        "    Summarize agent's goals\n",
        "  Preferences\n",
        "    Preference => A > B\n",
        "    Indifference => A ~ B\n",
        "    Axioms of Rationality\n",
        "      Orderability => (A > B) \\/ (B > A) \\/ (A ~ B)\n",
        "      Transitivity => (A > B) /\\ (B > C) => (A > C)\n",
        "      Continuity => (A > B > C) => there exists p st [p, A; 1-p, C] ~ B\n",
        "      Substitutability => A ~ B => [p, A; 1-p, C] ~ [p, B; 1-p, C]\n",
        "      Monotonicity => A > B => p >= q <=> [p, A; 1-p, B] >= [q, A; 1-q, B]\n",
        "  Maximum Expected Utility Principle\n",
        "    given any pref satisfying these constraints, there exists real value\n",
        "    functioned U st\n",
        "      U(A) >= U(B) <=> A >= B\n",
        "      U([p1, S1; ... ; pn, Sn]) = sigma_i pi U(Si)\n",
        "    i.e. values assigned by U preserve pref of both prizes and lotteries\n",
        "    - Choose action that maximizes expected utility\n",
        "    - note agent can be rational (consistent with MEU) without ever\n",
        "    representing/manipulating utilities/probabilities\n",
        "  Utilities Scales\n",
        "    Normalized Utilities: u_+ = 1.0, u_- = 0.0\n",
        "    Micromorts: 1/million chance of death,\n",
        "      good for paying to reduce product risk\n",
        "    QALYs: quality-adjusted life years, useful for medical decisions w risk\n",
        "    Behavior is invariant under positive linear transformation\n",
        "      U'(x) = k_1 * U(x) + k2 where k1 > 0\n",
        "    W/ deterministic prizes only, only ordinal utility can be determined\n",
        "  Human Utilities\n",
        "    How get number of human utility\n",
        "    Standard approach:\n",
        "      Compare prize A to standard lottery L_p between\n",
        "        best possible prize u+ probability p\n",
        "        worst possible catastrophe u_- with probability 1-p\n",
        "      Adjust p until indifference A ~ L_p\n",
        "      resulting p is utility [0, 1]\n",
        "  Money\n",
        "    does not behave as a utility function, but can talk about utility of\n",
        "    having money/being in debt\n",
        "    given lottery L = [p, $X; (1-p), $Y]\n",
        "      expected monetary value EMV(L) = p*X + (1-p)*Y\n",
        "      U(L) = p*U($X) + (1-p)*U($Y)\n",
        "      Typically U(L) < U(EMV(L)) => people are risk-averse\n",
        "      when deep in debt, people are risk-prone\n",
        "  Ex. Insurance\n",
        "    L = [0.5, $1000; 0.5, $0]\n",
        "    EMV(L) = $500\n",
        "    Certainty equivalent = $400\n",
        "      $100 is insurance premium\n",
        "      people pay to reduce risk\n",
        "      if everyone risk-neutral, no insurance\n",
        "  Ex. Human Rationality\n",
        "    People prefer lower EV but guaranteed\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\" : \"Reward for agent when moving from s to s' via a\",\n",
        "\"policy\" : \"solution for an MDP\",\n",
        "\"expected utility\" : \"average utility of all possible paths from policy\",\n",
        "\"Principle of maximum expected utility\" : \"a rational agent should choose the \\\n",
        "  action that maximizes its expected utility, given its knowledge\",\n",
        "\"insensitivity to monotonic transformations\" : \"better states higher eval \\\n",
        "  i.e. just get order right\",\n",
        "\"utilities\" : \"functions from outcomes to real numbers that describe pref\",\n",
        "\"lotteries\" : \"situations with uncertain prizes, L = [p, A; (1-p), B]\",\n",
        "\"ordinal utility\" : \"total order on prizes\"\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "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": "c5508159-8e6f-4424-d697-0bb5ad457d8b"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'Module 8 Lecture Notes' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n\n  Markovian Transition Models = Stochastic Transition Models\n    p(s' | s, a) or T(s, a, s')\n  Markov Decision Process is\n    a sequential decision problem\n    for a fully observal environment\n    with a stochastic transition model\n    that has additive rewards\n  MDPs are a non deterministic search problem => solve via expectimax search\n  To find a solution for MDPs, you need\n    Set of states S\n    Set of actions A\n    Transition function T(s, a, s')\n      probability p(s' | s, a), the probability is called the model\n    Reward function R(s, a, s')\n    Initial state s0\n    Optionally, one or more terminal states\n  Solution of an MDP is a policy pi(s) = a, in search problems called a plan\n    pi*(s) = a is optimal policy\n  Expected utility\n    Uh (of enviroment history) \n      Uh([s0, a0, s1, a1, ...])\n      = R(s0, a0, s1) + R(s1, a1, s2) + ...\n  Discounting\n    Prefer rewards now\n    Decays exponentially => 1, gamma, gamma^2, ...\n    Discount because sooner rewards probs have higher utility than later\n    Also helps algo converge\n  Stationary preference\n    [a1, a2, ...] > [b1, b2, ...] <=> [r, a1, a2, ...] > [r, b1, b2, ...]\n  If stationary preference, then only two ways to define utilities\n    Additive utility: U([r0, r1, r2, ...]) = r0 + r1 + r2\n    Discounted utility: U([r0, r1, r2, ...]) = r0 + gamma * r1, + gamma^2 * r2\n  Infinite Game Solutions\n    Finite horizon:\n      terminate after fixed T steps or\n      nonstationary policies (pi depends on time left)\n    Discounting: use 0 < gamma < 1\n      smaller gamma = smaller horizon\n    Absorbing state: guarantee that for every policy, a terminal state\n      will eventually be reached\n  Value (utility) of a state s = V*(s) acting optimally\n  Value of a q-state(s, a) = Q*(s, a)\n    expected utility starting out having taken action a from state s and\n    thereafter acting optimally\n  V*(s) = max_a Q*(s, a)\n  Q*(s, a) = sigma_s' T(s, a, s') [R(s, a, s') + gamma * V*(s')]\n  V*(s) = max_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n  Problem: states repeated and tree goes forever\n  Idea: Time-limited values\n    Define V_k(s) to be optimal value of s if the game ends in k time\n  Value iteration\n    Start with V_0(s) = 0\n    Given vector V_k(s), do one ply of expectimax\n    V_k+1 (s) <- max_a sigma_s' T(s, a, s')[R(s, a, s') + gamma V_k(s')]\n    repeat until convergence\n    Complexity of each iteration is O(S^2 * A)\n    Theorem: will converge to unique optimal values\n      approximations get refined towards optimal values\n      Policy may converge long before values do\n    Convergence\n      How do we know V_k will converge?\n        Case 1: if tree has max depth M, then V_M holds for actual untruncated\n          values\n        Case 2: if discount < 1\n          V_k and V_k+1 is viewed as depth k+1 expectimax results in nearly\n          identical search trees\n          bottom layer V_k+1 has actual rewards, V_k has zeros\n          last layer is at best all R_max, at worst R_min, but everything\n          is discounted by gamma^k\n          So V_k and V_k+1 differ at most gamma^k max |R|\n          as k increases, value converge\n  Bellman Equations\n    Definition of \"optimal utility\" via expectimax recurrence gives us\n    simple one-step lookahead relationship amongst optimal utility values\n    V*(s) = max_a Q*(s, a)\n    Q*(s, a) = sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n    V*(s) = max_a sigma_s' T(s, a, s') [R(s, a, s') + gamma * V*(s')]\n  Fixed Policies => do optimal action, do what pi says\n    For fixed policy pi,\n      V_pi(s) = sigma_s' T(s, pi(s), s')[R(s, pi(s), s') + gamma V^pi(s')]\n      How calculate?\n        idea 1: turn to updates\n          v_0^pi(s) = 0\n          v_k+w^pi(s) <- sum_s' T(s, pi(s), s')[R(,s pi(s), s') + \n                          gamma * V_k^pi(s')]\n        idea 2: just a linear system without maxes\n  Policy extraction\n    given optimal values V*(s), how act?\n    mini-expectimax (one step)\n    pi*(s) = argmax_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n    if given optimal q-values, trivial\n    pi*(s) = argmax_a Q*(s, a)\n  Problems with value iteration\n    repeats bellman updates\n    => slow - O(S^2 A) per iteration\n      max rarely changes\n      policy converges long before values\n    Alternative: Policy iteration\n      step 1: policy evaluation, calculate utilities for some fixed policy\n        (not optimal tho) until convergence\n      step 2: policy improvement, update policy using one-step look-ahead with\n        resulting converged but not optimal utilities as future values\n      repeat until converges\n      still optimal and can converge much faster\n      Evaluation: for fixed current policy pi, find values with policy\n        evaluation (iterate until values converge)\n        v^(pi_i)_k+1(s) <- \n          sigma_s' T(s, pi_i(s), s')[R(s, pi_i(s), s')+gamma * V_k^(pi_i)(s')]\n        improvement, for fixed values get better policy using policy extraction\n          one step lookahead\n          pi_i+1(s) = \n            argmax_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V^(pi_i)(s')]\n  Comparison\n    Both value/policy compute same thing (optimal values)\n    Value iteration:\n      every iteration updates both the value and implicitly the policy\n      dont track policy but taking max over actions implicitly recomputes it\n    policy iteration:\n      several passes that update utilities with fixed policy\n        pass is fast bc only condier one action not all\n      after policy evaluated, new policy chosen (slow like value iter pass)\n      new policy will be better (or done)\n    both are dynamic programs for solving MDPs\n  Summary\n    compute optimal values: use value iter or policy iter\n    compute val for particular policy: policy evaluation\n    turn values into policy: policy extraction (one-step lookahead)\n    all variations of bellman updates\n    all use one-step lookahead expectimax fragments\n    differ only whether we plug in fixed policy or max over actions\n  Utilities\n    Why average utilities? instead of minimax\n    Principle of maximum expected utility\n    What utilities to use?\n      for worst case, terminal functrion scale doesnt matter\n      i.e. insensitivity to monotonic transformations\n    Summarize agent's goals\n  Preferences\n    Preference => A > B\n    Indifference => A ~ B\n    Axioms of Rationality\n      Orderability => (A > B) \\/ (B > A) \\/ (A ~ B)\n      Transitivity => (A > B) /\\ (B > C) => (A > C)\n      Continuity => (A > B > C) => there exists p st [p, A; 1-p, C] ~ B\n      Substitutability => A ~ B => [p, A; 1-p, C] ~ [p, B; 1-p, C]\n      Monotonicity => A > B => p >= q <=> [p, A; 1-p, B] >= [q, A; 1-q, B]\n  Maximum Expected Utility Principle\n    given any pref satisfying these constraints, there exists real value\n    functioned U st\n      U(A) >= U(B) <=> A >= B\n      U([p1, S1; ... ; pn, Sn]) = sigma_i pi U(Si)\n    i.e. values assigned by U preserve pref of both prizes and lotteries\n    - Choose action that maximizes expected utility\n    - note agent can be rational (consistent with MEU) without ever\n    representing/manipulating utilities/probabilities\n  Utilities Scales\n    Normalized Utilities: u_+ = 1.0, u_- = 0.0\n    Micromorts: 1/million chance of death,\n      good for paying to reduce product risk\n    QALYs: quality-adjusted life years, useful for medical decisions w risk\n    Behavior is invariant under positive linear transformation\n      U'(x) = k_1 * U(x) + k2 where k1 > 0\n    W/ deterministic prizes only, only ordinal utility can be determined\n  Human Utilities\n    How get number of human utility\n    Standard approach:\n      Compare prize A to standard lottery L_p between\n        best possible prize u+ probability p\n        worst possible catastrophe u_- with probability 1-p\n      Adjust p until indifference A ~ L_p\n      resulting p is utility [0, 1]\n  Money\n    does not behave as a utility function, but can talk about utility of\n    having money/being in debt\n    given lottery L = [p, $X; (1-p), $Y]\n      expected monetary value EMV(L) = p*X + (1-p)*Y\n      U(L) = p*U($X) + (1-p)*U($Y)\n      Typically U(L) < U(EMV(L)) => people are risk-averse\n      when deep in debt, people are risk-prone\n  Ex. Insurance\n    L = [0.5, $1000; 0.5, $0]\n    EMV(L) = $500\n    Certainty equivalent = $400\n      $100 is insurance premium\n      people pay to reduce risk\n      if everyone risk-neutral, no insurance\n  Ex. Human Rationality\n    People prefer lower EV but guaranteed\n  \n\n## Module 8 Definitions\n* **Utility function** - Reward for agent when moving from s to s' via a\n* **Policy** - solution for an MDP\n* **Expected utility** - average utility of all possible paths from policy\n* **Principle of maximum expected utility** - a rational agent should choose the   action that maximizes its expected utility, given its knowledge\n* **Insensitivity to monotonic transformations** - better states higher eval   i.e. just get order right\n* **Utilities** - functions from outcomes to real numbers that describe pref\n* **Lotteries** - situations with uncertain prizes, L = [p, A; (1-p), B]\n* **Ordinal utility** - total order on prizes\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "  Offline Planning\n",
        "    Determine quantities through computation\n",
        "    need to know details of MDP, don't actually play game\n",
        "  Reinforcement Learning - an MDP but cant just use computation\n",
        "    need to act to figure out\n",
        "    Basic idea:\n",
        "      Receive feedback in form of rewards\n",
        "      Agents utility is defined by the reward function\n",
        "      learn to maximize expected rewards\n",
        "      all learning based on observed sample of outcomes\n",
        "    Still assume a MDP\n",
        "      set of states S\n",
        "      set of actions (per state) A\n",
        "      model T(s, a, s')\n",
        "      reward function R(s, a, s')\n",
        "      looking for pi(s)\n",
        "      twist: don't know T or R\n",
        "  Model-Based Learning\n",
        "    Model-Based idea:\n",
        "      learn approximate model based on exp\n",
        "      solve for values as if learned model was correct\n",
        "      step 1: learn empirical MDP model\n",
        "        count outcomes s' for each s, a\n",
        "        normalize to give an estimate of T^(hat)(s, a, s')\n",
        "        discover each R^(hat)(s, a, s') when we experience (s, a, s')\n",
        "      step 2: solve learned MDP\n",
        "        ex. use value iteration\n",
        "  Passive Reinforcement Learning\n",
        "    Simplified task: policy evaluation\n",
        "    input: fixed policy pi(s)\n",
        "    dont know transitions T(s, a, s'), rewards R(s, a, s')\n",
        "    Goals: learn state values\n",
        "    Learner along for the ride, no choice about actions, just execute and learn\n",
        "  Direct Evaluation\n",
        "    Goal: compute values for each state under pi\n",
        "    Idea: average together observed sample values\n",
        "      act according to pi\n",
        "      everytime visit a state, write down sum of discounted rewards\n",
        "      average samples\n",
        "    Good:\n",
        "      easy, no knowledge of T, R, eventually computes correct average values\n",
        "    Bad:\n",
        "      wastes info about state connections, each state learned separately\n",
        "  Why not use policy evaluation/bellman updates? - we need T and R\n",
        "  Solution: sample-based policy evaluation\n",
        "    Want to improve our estimate of V by computing these averages\n",
        "      V^pi_k+1(s) <- \n",
        "        sigma_s' T(s, pi(s), s')[R(s, pi(s), s') + gamma * V^pi_k(s')]\n",
        "    samples of outcomes s' by doing action and average\n",
        "      sample1 = R(s, pi(s), s1') + gamma * V^pi_k(s1')\n",
        "      sample2 = R(s, pi(s), s2') + gamma * V^pi_k(s2')\n",
        "      ...\n",
        "      V^pi_k+1(s) <- (1/n) * sigma_i sample_i\n",
        "  Temporal Difference Learning\n",
        "    Learn from every experience\n",
        "    Update V(s) every time experience transition (s, a, s', r)\n",
        "    Likely outcomes s' will contribute updates more often\n",
        "    Policy still fixed, still doing evaluation\n",
        "    Essentially running average\n",
        "    Sample of V(s): sample = R(s, pi(s), s') + gamma * V^pi(s')\n",
        "    Update to V(s): V^pi(s) <- (1-alpha)V^pi(s) + (alpha)sample\n",
        "    Same update: V^pi(s) <- V^pi(s) + alpha(sample - V^pi(s))\n",
        "  Exponential Moving Average\n",
        "    Running interpolation update: x^bar_n = (1-alpha)x^bar_n-1 + alpha * x_n\n",
        "    Recent samples are more important\n",
        "    x^bar_n = (x_n + (1-alpha)x_n-1 + (1-alpha)^2 x_n-2 + ...) \n",
        "      / (1 + (1-alpha) + (1-alpha)^2)\n",
        "    Decreasing alpha can give converging averages\n",
        "  Problems with TD Value Learning\n",
        "    model-free way to do policy evaluation, mimicking bellman updates w/\n",
        "      running sample averages\n",
        "    If we want to turn values into new policy, fails\n",
        "    Idea: learn Q-values, not values\n",
        "    Makes action selection model free too\n",
        "  Active Reinforcement Learning\n",
        "    Full reinforcement learning\n",
        "      You don't know the transition, rewards\n",
        "      You choose actions now\n",
        "      Goal: learn optimal policy/values\n",
        "    Learner makes choice\n",
        "      fundamental tradeoff: exploration vs exploitation\n",
        "    Not offline planning\n",
        "  Q-Value Iteration\n",
        "    Value iteration: find successive (depth-limited) values\n",
        "    But Q-values are more useful, so compute instead\n",
        "    Q0(s, a) = 0, guaranteed right\n",
        "    Given Q_k, calculate depth k+1 q-vals for all q-states\n",
        "    Q_k+1(s, a) <-\n",
        "      sigma_s' T(s, a, s')[R(s, a, s') + gamma * max_a' Q_k(s', a')]\n",
        "  Q-learning: sample based Q-value iteration\n",
        "    Q_k+1(s, a) <-\n",
        "      sigma_s' T(s, a, s') [R(s, a, s') + gamma * max_a' Q_k(s', a')]\n",
        "    Learn Q(s, a) as you go\n",
        "    Receive sample (s, a, s', r)\n",
        "    Consider old estimate Q(s, a)\n",
        "    Consider your new sample estimate\n",
        "      sample = R(s, a, s') + gamma * max_a' Q(s', a')\n",
        "      Incorporate new estimate into running average\n",
        "      Q(s, a) <- (1-alpha)Q(s, a) + (alpha)[sample]\n",
        "    Properties\n",
        "      Q-learning converges to optimal policy, even if acting suboptimally\n",
        "      Off-policy learning\n",
        "      Caveats\n",
        "        Have to explore enough\n",
        "        Have to eventually make learning rate small enough, but not decrease\n",
        "        too quickly\n",
        "  How to explore?\n",
        "    Simplest: random actions (epsilon-greedy)\n",
        "      Every time step, flip a coin\n",
        "      With small prob epsilon, act randomly\n",
        "      With large prob 1-epsilon, act on current policy\n",
        "      Problems:\n",
        "        eventually explore space, but keep thrashing around until learning done\n",
        "        One solution: lower epsilon over time\n",
        "        Another: exploration functions\n",
        "  Exploration functions\n",
        "    Idea: explore areas whose badness is not yet established, eventually\n",
        "      stop exploring\n",
        "    Func: takes a value estimate u and a visit count n, and returns an\n",
        "      optimistic utility f(u, n) = u + k/n\n",
        "    Regular Q-update: Q(s, a) <-_alpha R(s, a, s') + gamma * max_a' Q(s', a')\n",
        "    Modified Q-update: Q(s, a) <-_alpha\n",
        "      R(s, a, s') + gamma * max_a' f(Q(s', a'), N(s', a'))\n",
        "    Regret:\n",
        "      difference between your expected rewards including youthful suboptimality\n",
        "      and optimal expected rewards\n",
        "      Minimizing regret requires optimally learning be optimal\n",
        "        Ex. random exploration and exploration functions both optimal, but\n",
        "          random exploration has higher regret\n",
        "  Approximate Q-Learning\n",
        "    Generalizing across states\n",
        "    Basic Q-learning keeps table of all q values\n",
        "    Realistically, can't learn about every single state\n",
        "    Generalize: learn about some small number of training states from experience\n",
        "      Generalize to new, similar situations\n",
        "    Flashback: evaluation functions\n",
        "      ideal function: returns actual minimax value of position\n",
        "      in practice: weighted linear sum of features\n",
        "    Linear Value Functions\n",
        "      w/ feature representation, write q func for any state\n",
        "      V(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)\n",
        "      Q(s, a) = w1f1(s, a) + w2f2(s, a) + ... + wnfn(s, a)\n",
        "      Adv: our experience summed up in a few numbers\n",
        "      Disadv: states may share features, but be very diff in value\n",
        "    Key formula\n",
        "      Q(s, a) = w1f1(s, a) + w2f2(s, a) + ... + wnfn(s, a)\n",
        "    Q-learning with linear Q-functions\n",
        "      transitions = (s, a, r, s')\n",
        "      difference = [r + gamma * max_a' Q(s', a')] - Q(s, a)\n",
        "      Q(s, a) <- Q(s, a) + alpha[difference]\n",
        "      w_i <- w_i + alpha[difference]f_i(s, a)\n",
        "      Intuitive interpretation:\n",
        "        adjust weights of active features\n",
        "      Formal justification: online least squares\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"Exploration\" : \"Try unknown actions to get information\",\n",
        "\"Exploitation\" : \"Eventually, have to use what you know\",\n",
        "\"Regret\" : \"Even if learn intelligently, make mistakes\",\n",
        "\"Sampling\" : \"Because of chance, have to try repeatedly\",\n",
        "\"Difficulty\" : \"Learning harder than solving known MDP\",\n",
        "\"alpha\" : \"learning rate\",\n",
        "\"off-policy learning\" : \"converges to optimal policy even if acting suboptimally\",\n",
        "\"regret\" : \"measure of your total mistake cost\"\n",
        "\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e7b36457-4a21-49ce-8965-0f41b3630c46"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n  Offline Planning\n    Determine quantities through computation\n    need to know details of MDP, don't actually play game\n  Reinforcement Learning - an MDP but cant just use computation\n    need to act to figure out\n    Basic idea:\n      Receive feedback in form of rewards\n      Agents utility is defined by the reward function\n      learn to maximize expected rewards\n      all learning based on observed sample of outcomes\n    Still assume a MDP\n      set of states S\n      set of actions (per state) A\n      model T(s, a, s')\n      reward function R(s, a, s')\n      looking for pi(s)\n      twist: don't know T or R\n  Model-Based Learning\n    Model-Based idea:\n      learn approximate model based on exp\n      solve for values as if learned model was correct\n      step 1: learn empirical MDP model\n        count outcomes s' for each s, a\n        normalize to give an estimate of T^(hat)(s, a, s')\n        discover each R^(hat)(s, a, s') when we experience (s, a, s')\n      step 2: solve learned MDP\n        ex. use value iteration\n  Passive Reinforcement Learning\n    Simplified task: policy evaluation\n    input: fixed policy pi(s)\n    dont know transitions T(s, a, s'), rewards R(s, a, s')\n    Goals: learn state values\n    Learner along for the ride, no choice about actions, just execute and learn\n  Direct Evaluation\n    Goal: compute values for each state under pi\n    Idea: average together observed sample values\n      act according to pi\n      everytime visit a state, write down sum of discounted rewards\n      average samples\n    Good:\n      easy, no knowledge of T, R, eventually computes correct average values\n    Bad:\n      wastes info about state connections, each state learned separately\n  Why not use policy evaluation/bellman updates? - we need T and R\n  Solution: sample-based policy evaluation\n    Want to improve our estimate of V by computing these averages\n      V^pi_k+1(s) <- \n        sigma_s' T(s, pi(s), s')[R(s, pi(s), s') + gamma * V^pi_k(s')]\n    samples of outcomes s' by doing action and average\n      sample1 = R(s, pi(s), s1') + gamma * V^pi_k(s1')\n      sample2 = R(s, pi(s), s2') + gamma * V^pi_k(s2')\n      ...\n      V^pi_k+1(s) <- (1/n) * sigma_i sample_i\n  Temporal Difference Learning\n    Learn from every experience\n    Update V(s) every time experience transition (s, a, s', r)\n    Likely outcomes s' will contribute updates more often\n    Policy still fixed, still doing evaluation\n    Essentially running average\n    Sample of V(s): sample = R(s, pi(s), s') + gamma * V^pi(s')\n    Update to V(s): V^pi(s) <- (1-alpha)V^pi(s) + (alpha)sample\n    Same update: V^pi(s) <- V^pi(s) + alpha(sample - V^pi(s))\n  Exponential Moving Average\n    Running interpolation update: x^bar_n = (1-alpha)x^bar_n-1 + alpha * x_n\n    Recent samples are more important\n    x^bar_n = (x_n + (1-alpha)x_n-1 + (1-alpha)^2 x_n-2 + ...) \n      / (1 + (1-alpha) + (1-alpha)^2)\n    Decreasing alpha can give converging averages\n  Problems with TD Value Learning\n    model-free way to do policy evaluation, mimicking bellman updates w/\n      running sample averages\n    If we want to turn values into new policy, fails\n    Idea: learn Q-values, not values\n    Makes action selection model free too\n  Active Reinforcement Learning\n    Full reinforcement learning\n      You don't know the transition, rewards\n      You choose actions now\n      Goal: learn optimal policy/values\n    Learner makes choice\n      fundamental tradeoff: exploration vs exploitation\n    Not offline planning\n  Q-Value Iteration\n    Value iteration: find successive (depth-limited) values\n    But Q-values are more useful, so compute instead\n    Q0(s, a) = 0, guaranteed right\n    Given Q_k, calculate depth k+1 q-vals for all q-states\n    Q_k+1(s, a) <-\n      sigma_s' T(s, a, s')[R(s, a, s') + gamma * max_a' Q_k(s', a')]\n  Q-learning: sample based Q-value iteration\n    Q_k+1(s, a) <-\n      sigma_s' T(s, a, s') [R(s, a, s') + gamma * max_a' Q_k(s', a')]\n    Learn Q(s, a) as you go\n    Receive sample (s, a, s', r)\n    Consider old estimate Q(s, a)\n    Consider your new sample estimate\n      sample = R(s, a, s') + gamma * max_a' Q(s', a')\n      Incorporate new estimate into running average\n      Q(s, a) <- (1-alpha)Q(s, a) + (alpha)[sample]\n    Properties\n      Q-learning converges to optimal policy, even if acting suboptimally\n      Off-policy learning\n      Caveats\n        Have to explore enough\n        Have to eventually make learning rate small enough, but not decrease\n        too quickly\n  How to explore?\n    Simplest: random actions (epsilon-greedy)\n      Every time step, flip a coin\n      With small prob epsilon, act randomly\n      With large prob 1-epsilon, act on current policy\n      Problems:\n        eventually explore space, but keep thrashing around until learning done\n        One solution: lower epsilon over time\n        Another: exploration functions\n  Exploration functions\n    Idea: explore areas whose badness is not yet established, eventually\n      stop exploring\n    Func: takes a value estimate u and a visit count n, and returns an\n      optimistic utility f(u, n) = u + k/n\n    Regular Q-update: Q(s, a) <-_alpha R(s, a, s') + gamma * max_a' Q(s', a')\n    Modified Q-update: Q(s, a) <-_alpha\n      R(s, a, s') + gamma * max_a' f(Q(s', a'), N(s', a'))\n    Regret:\n      difference between your expected rewards including youthful suboptimality\n      and optimal expected rewards\n      Minimizing regret requires optimally learning be optimal\n        Ex. random exploration and exploration functions both optimal, but\n          random exploration has higher regret\n  Approximate Q-Learning\n    Generalizing across states\n    Basic Q-learning keeps table of all q values\n    Realistically, can't learn about every single state\n    Generalize: learn about some small number of training states from experience\n      Generalize to new, similar situations\n    Flashback: evaluation functions\n      ideal function: returns actual minimax value of position\n      in practice: weighted linear sum of features\n    Linear Value Functions\n      w/ feature representation, write q func for any state\n      V(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)\n      Q(s, a) = w1f1(s, a) + w2f2(s, a) + ... + wnfn(s, a)\n      Adv: our experience summed up in a few numbers\n      Disadv: states may share features, but be very diff in value\n    Key formula\n      Q(s, a) = w1f1(s, a) + w2f2(s, a) + ... + wnfn(s, a)\n    Q-learning with linear Q-functions\n      transitions = (s, a, r, s')\n      difference = [r + gamma * max_a' Q(s', a')] - Q(s, a)\n      Q(s, a) <- Q(s, a) + alpha[difference]\n      w_i <- w_i + alpha[difference]f_i(s, a)\n      Intuitive interpretation:\n        adjust weights of active features\n      Formal justification: online least squares\n\n\n## Module 9 Definitions\n* **Exploration** - Try unknown actions to get information\n* **Exploitation** - Eventually, have to use what you know\n* **Regret** - Even if learn intelligently, make mistakes\n* **Sampling** - Because of chance, have to try repeatedly\n* **Difficulty** - Learning harder than solving known MDP\n* **Alpha** - learning rate\n* **Off-policy learning** - converges to optimal policy even if acting suboptimally\n* **Regret** - measure of your total mistake cost\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "  Probabilities are about possible worlds\n",
        "    How likely a world is\n",
        "  Probability model = P(w) with each possible world w\n",
        "  Axioms of Probability\n",
        "    0 <= P(w) <= 1 for every w\n",
        "    sigma_(w in Omega) P(w) = 1\n",
        "  Probability Distributions\n",
        "    Joint distribution over set of Random Variable RVs\n",
        "      specify real number for each outcome\n",
        "      ex P(X1 = x1, X2 = x2, ... Xn = xn)\n",
        "      Still P(x1, x2, ...) >= 0\n",
        "      and sigma_(x1, x2, ...) P(x1, x2, ...) = 1\n",
        "  Probabilistic model\n",
        "    A joint distribution over a set of random variables\n",
        "    Assignments called outcomes\n",
        "    Noramlized: sum to 1.0\n",
        "    Ideally only certain variables directly interact\n",
        "  Event is set E of outcomes\n",
        "    P(E) = sigma_(x1, x2, ... in E) P(x1, ...)\n",
        "  Marginal distributions\n",
        "    sub-tables that eliminate variables\n",
        "    Combine collapsed rows by adding\n",
        "  Conditional probabilities\n",
        "    P(a|b) = P(a, b)/P(b)\n",
        "    probability given fixed values of other\n",
        "  Probabilistic inference\n",
        "    Inference by enumeration\n",
        "    Evidence variables: E1, ... Ek = e1, ... ek\n",
        "    Query* variables: Q\n",
        "    Hidden variables: H1, ... Hr\n",
        "    Together, all variables X1, X2, ...\n",
        "    We want P(Q|e1, ... ek)\n",
        "    Step 1: Select entries consistent w/ evidence\n",
        "      pick P(Q, e1, ..., ek)\n",
        "    Step 2: sum out hidden variables to get joint query and evidence\n",
        "      sigma_(h1..hr) P(Q, h1, ..., hr, e1, ..., ek)\n",
        "    Step 3: normalize\n",
        "      * 1/Z\n",
        "      Z = sum_q P(Q, e1, ..., ek)\n",
        "      P(Q|e1, ... ek) = 1/Z P(Q, e1, ... ek)\n",
        "  Probabilistic Language Models\n",
        "    One Goal: assign probability to a sentence\n",
        "      P(W) = P(w1, w2, ..., wn)\n",
        "      related task: probability of upcoming word\n",
        "        P(w5|w1, w2, w3, w4)\n",
        "      model is Language Model or LM\n",
        "        P(W) or P(wn|w1, ..., w_n-1)\n",
        "    Other tasks: summarization, question-answering, dialog systems\n",
        "    Better: the grammar\n",
        "  Compute P(W) using chain rule\n",
        "  Simplifying = Markov Assumption\n",
        "    Only depends on previous k words, not whole context\n",
        "    K = number of context words\n",
        "  Unigram model\n",
        "    P(w1w2...wn) = Pi_i P(wi)\n",
        "  Bigram\n",
        "    P(wi|w1w2...wi-1) = P(wi|wi-1)\n",
        "  N-gram models insufficient because of long-distance dependencies\n",
        "  Maximum Likelihood Estimate\n",
        "    P(wi|wi-1) = count(wi-1, wi) / count(wi-1)\n",
        "  Problems for MLE\n",
        "    zero probability events (never seen combo again)\n",
        "    out of vocabular items\n",
        "      use filler <unk>\n",
        "    fixed lexicon L of size V\n",
        "    normalize training day - replace words not in L with <unk>\n",
        "    avoid zeros with smoothing\n",
        "  Practical Issues\n",
        "    do everything in log space\n",
        "      avoid underflow\n",
        "      faster than multiplying\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"Observed variables (evidence)\" : \"Agent knows certain things about state \\\n",
        "  of the world e.g., sensor readings or symptoms\",\n",
        "\"Unobserved variable (states)\" : \"Agent need to reason about other aspects \\\n",
        "  e.g. where an object is\",\n",
        "\"Mode\" : \"Agent knows something about how the known variable relate to \\\n",
        "  unknown variables\",\n",
        "\"Sample space\" : \"possible worlds, mutually exclusive and exhaustive\",\n",
        "\"Distribution\" : \"table of probability values\",\n",
        "\"Probabilistic inference\" : \"compute desired probability from other known \\\n",
        "  probability\",\n",
        "\"Product Rule\" : \"P(y)P(x|y) = P(x, y)\",\n",
        "\"Chain Rule\" : \"P(x1, x2, x3) = P(x1)P(x2|x1)P(x3|x1, x2)\\\n",
        "  P(x1, x2, ..., xn) = Pi_i P(xi|x1, ..., x_i-1)\",\n",
        "\"Bayes' Rule\" : \"P(x, y) = P(x|y)P(y) = P(y|x)P(x) => \\\n",
        "  P(x|y) = P(y|x)/P(y) * P(x)\",\n",
        "\"unigram/bigram/trigram/4-gram\" : \"0/1/2/3/4 word as history\",\n",
        "\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "b0ddbed7-e3a7-4dea-8d72-15a14bd83ef6"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n  Probabilities are about possible worlds\n    How likely a world is\n  Probability model = P(w) with each possible world w\n  Axioms of Probability\n    0 <= P(w) <= 1 for every w\n    sigma_(w in Omega) P(w) = 1\n  Probability Distributions\n    Joint distribution over set of Random Variable RVs\n      specify real number for each outcome\n      ex P(X1 = x1, X2 = x2, ... Xn = xn)\n      Still P(x1, x2, ...) >= 0\n      and sigma_(x1, x2, ...) P(x1, x2, ...) = 1\n  Probabilistic model\n    A joint distribution over a set of random variables\n    Assignments called outcomes\n    Noramlized: sum to 1.0\n    Ideally only certain variables directly interact\n  Event is set E of outcomes\n    P(E) = sigma_(x1, x2, ... in E) P(x1, ...)\n  Marginal distributions\n    sub-tables that eliminate variables\n    Combine collapsed rows by adding\n  Conditional probabilities\n    P(a|b) = P(a, b)/P(b)\n    probability given fixed values of other\n  Probabilistic inference\n    Inference by enumeration\n    Evidence variables: E1, ... Ek = e1, ... ek\n    Query* variables: Q\n    Hidden variables: H1, ... Hr\n    Together, all variables X1, X2, ...\n    We want P(Q|e1, ... ek)\n    Step 1: Select entries consistent w/ evidence\n      pick P(Q, e1, ..., ek)\n    Step 2: sum out hidden variables to get joint query and evidence\n      sigma_(h1..hr) P(Q, h1, ..., hr, e1, ..., ek)\n    Step 3: normalize\n      * 1/Z\n      Z = sum_q P(Q, e1, ..., ek)\n      P(Q|e1, ... ek) = 1/Z P(Q, e1, ... ek)\n  Probabilistic Language Models\n    One Goal: assign probability to a sentence\n      P(W) = P(w1, w2, ..., wn)\n      related task: probability of upcoming word\n        P(w5|w1, w2, w3, w4)\n      model is Language Model or LM\n        P(W) or P(wn|w1, ..., w_n-1)\n    Other tasks: summarization, question-answering, dialog systems\n    Better: the grammar\n  Compute P(W) using chain rule\n  Simplifying = Markov Assumption\n    Only depends on previous k words, not whole context\n    K = number of context words\n  Unigram model\n    P(w1w2...wn) = Pi_i P(wi)\n  Bigram\n    P(wi|w1w2...wi-1) = P(wi|wi-1)\n  N-gram models insufficient because of long-distance dependencies\n  Maximum Likelihood Estimate\n    P(wi|wi-1) = count(wi-1, wi) / count(wi-1)\n  Problems for MLE\n    zero probability events (never seen combo again)\n    out of vocabular items\n      use filler <unk>\n    fixed lexicon L of size V\n    normalize training day - replace words not in L with <unk>\n    avoid zeros with smoothing\n  Practical Issues\n    do everything in log space\n      avoid underflow\n      faster than multiplying\n\n\n\n## Module 10 Definitions\n* **Observed variables (evidence)** - Agent knows certain things about state   of the world e.g., sensor readings or symptoms\n* **Unobserved variable (states)** - Agent need to reason about other aspects   e.g. where an object is\n* **Mode** - Agent knows something about how the known variable relate to   unknown variables\n* **Sample space** - possible worlds, mutually exclusive and exhaustive\n* **Distribution** - table of probability values\n* **Probabilistic inference** - compute desired probability from other known   probability\n* **Product rule** - P(y)P(x|y) = P(x, y)\n* **Chain rule** - P(x1, x2, x3) = P(x1)P(x2|x1)P(x3|x1, x2)  P(x1, x2, ..., xn) = Pi_i P(xi|x1, ..., x_i-1)\n* **Bayes' rule** - P(x, y) = P(x|y)P(y) = P(y|x)P(x) =>   P(x|y) = P(y|x)/P(y) * P(x)\n* **Unigram/bigram/trigram/4-gram** - 0/1/2/3/4 word as history\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "  Models describe how (a portion of) the world works\n",
        "  Models are always simplifications\n",
        "  Independence is a simplifying modeling assumption\n",
        "  Unconditional/absolute independence very rare\n",
        "  Conditional independence is our most basic/robust form of knowledge abt\n",
        "    uncertain events\n",
        "  X is conditionally independent of Y given Z => X _||_ Y | Z\n",
        "    iff forall x,y,z P(x, y|z) = P(x|z)P(y|z)\n",
        "    or\n",
        "    iff P(x|z, y) = P(x|z)\n",
        "  Two problems with using full joint distribution tables\n",
        "    Unless a few vars, joint is way too big\n",
        "    Hard to learn/estimate anything empirically about more than a few vars\n",
        "      at a time\n",
        "  Bayes' net\n",
        "    a technique for describing complex join distributions (models) using\n",
        "      simple local distributions (conditional probabilities)\n",
        "    called graphical models\n",
        "    local interactions chain together to give global, indirect interactions\n",
        "  Graphical Model Notation\n",
        "    Nodes: vars (w/ domains)\n",
        "      observed or unobserved (assigned or unassigned)\n",
        "    Arcs: interactions\n",
        "      direct influence between variables\n",
        "      formally encode conditional independence\n",
        "  Bayes' net semantics\n",
        "    Set of nodes, one per var\n",
        "    Directed acyclic graph\n",
        "    Conditional distribution for each node\n",
        "      collection of distributions over X, one for each combo of parents' value\n",
        "        P(X|a1, ... an)\n",
        "        a1, ... an are parents\n",
        "    CPT: conditional probability table\n",
        "    Description of a noisy causal process\n",
        "    Bayes net = topology (graph) + local conditional probabilities\n",
        "  Bayes' net implicitly encode join distributions\n",
        "    as a product of local conditional distributions\n",
        "    to see what BN gives to full assignment, multiply all relavent conditionals\n",
        "    P(x1, x2, ... xn) = Pi^n_i=1 P(xi|parents(Xi))\n",
        "    Why do we guarantee this?\n",
        "      Chain rule + assume conditional independence\n",
        "    Not every BN can represent every joint distribution\n",
        "  Causality?\n",
        "    When BN reflect true causal pattners\n",
        "    often simpler\n",
        "    BN need not actually be causal\n",
        "    What arrows mean?\n",
        "      Topology may happen to encode causul structure\n",
        "      Topology really encodes conditional independence\n",
        "  Size of BN\n",
        "    Join distribution over N boolean vars -> 2^N\n",
        "    How big is N-node net if nodes have up to k parents\n",
        "    O(N*2^k+1)\n",
        "    Save space\n",
        "    Conditional iindependence is property of distribution\n",
        "  BN Assumptions\n",
        "    Assumes additional conditional independences\n",
        "  Causal Chains\n",
        "    X->Y->Z => P(x, y, z) = P(x)P(y|x)P(z|y)\n",
        "    guaranteed X independent of Z? no\n",
        "    guaranteed X independent of Z given Y? yes\n",
        "    Common cause configuration\n",
        "    Observing an effect activates influence between possible causes\n",
        "  General Question: in a given BN, are two variables independent?\n",
        "    Solution: analyze graph\n",
        "    Reachability: almost works\n",
        "    Active/Inactive paths\n",
        "      no active paths = independence\n",
        "      Path is active if each triple is active\n",
        "        Causal chain A -> B -> C where B unobserved\n",
        "        Common cause A <- B -> C b unobserved\n",
        "        Common effect A -> B <- C\n",
        "      Only block path is single inactive segment\n",
        "  D-Separation\n",
        "    Query: X_i _||_ X_j | {X_(k_1), ..., X_(k_n)}\n",
        "    Check all undirected paths between X_i X_j\n",
        "    If one or more active, independence not guaranteed\n",
        "    otherwise, guaranteed\n",
        "  Summary\n",
        "    BN compactly encode joint distribution\n",
        "    Guaranteed independence of distributions deduced from graph structure\n",
        "    D-separation gives precise conditional independence from graph alone\n",
        "    BN's joint distribution may have further conditional independence that\n",
        "      is not detectable until you inspect its specific distribution\n",
        "  Inference\n",
        "    Examples:\n",
        "      Posterior Probability\n",
        "        P(Q|E1 = e1, ... E_k = ek)\n",
        "      Most likely explanation\n",
        "        argmax_q P(Q = q|E1 = e1...)\n",
        "    Inference by enumeration in Bayes' Net\n",
        "      Use inference by enumeration\n",
        "      Slow bc join whole joint distribution before sum out hidden variables\n",
        "    Advance technique: Variable elimination\n",
        "      \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"Independence\" : \"two vars independent if forall x, y: P(x, y) = P(x)P(y) \\\n",
        "  or P(x|y) = P(x), shown as X _||_ Y\",\n",
        "\"Inference\" : \"calculate some useful quantity from a joint probability \\\n",
        "  distribution\"\n",
        "}\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 949
        },
        "cellView": "form",
        "outputId": "700378b8-05bb-4fae-dd3f-5c81b41f457a"
      },
      "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": 11,
      "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\n  Models describe how (a portion of) the world works\n  Models are always simplifications\n  Independence is a simplifying modeling assumption\n  Unconditional/absolute independence very rare\n  Conditional independence is our most basic/robust form of knowledge abt\n    uncertain events\n  X is conditionally independent of Y given Z => X _||_ Y | Z\n    iff forall x,y,z P(x, y|z) = P(x|z)P(y|z)\n    or\n    iff P(x|z, y) = P(x|z)\n  Two problems with using full joint distribution tables\n    Unless a few vars, joint is way too big\n    Hard to learn/estimate anything empirically about more than a few vars\n      at a time\n  Bayes' net\n    a technique for describing complex join distributions (models) using\n      simple local distributions (conditional probabilities)\n    called graphical models\n    local interactions chain together to give global, indirect interactions\n  Graphical Model Notation\n    Nodes: vars (w/ domains)\n      observed or unobserved (assigned or unassigned)\n    Arcs: interactions\n      direct influence between variables\n      formally encode conditional independence\n  Bayes' net semantics\n    Set of nodes, one per var\n    Directed acyclic graph\n    Conditional distribution for each node\n      collection of distributions over X, one for each combo of parents' value\n        P(X|a1, ... an)\n        a1, ... an are parents\n    CPT: conditional probability table\n    Description of a noisy causal process\n    Bayes net = topology (graph) + local conditional probabilities\n  Bayes' net implicitly encode join distributions\n    as a product of local conditional distributions\n    to see what BN gives to full assignment, multiply all relavent conditionals\n    P(x1, x2, ... xn) = Pi^n_i=1 P(xi|parents(Xi))\n    Why do we guarantee this?\n      Chain rule + assume conditional independence\n    Not every BN can represent every joint distribution\n  Causality?\n    When BN reflect true causal pattners\n    often simpler\n    BN need not actually be causal\n    What arrows mean?\n      Topology may happen to encode causul structure\n      Topology really encodes conditional independence\n  Size of BN\n    Join distribution over N boolean vars -> 2^N\n    How big is N-node net if nodes have up to k parents\n    O(N*2^k+1)\n    Save space\n    Conditional iindependence is property of distribution\n  BN Assumptions\n    Assumes additional conditional independences\n  Causal Chains\n    X->Y->Z => P(x, y, z) = P(x)P(y|x)P(z|y)\n    guaranteed X independent of Z? no\n    guaranteed X independent of Z given Y? yes\n    Common cause configuration\n    Observing an effect activates influence between possible causes\n  General Question: in a given BN, are two variables independent?\n    Solution: analyze graph\n    Reachability: almost works\n    Active/Inactive paths\n      no active paths = independence\n      Path is active if each triple is active\n        Causal chain A -> B -> C where B unobserved\n        Common cause A <- B -> C b unobserved\n        Common effect A -> B <- C\n      Only block path is single inactive segment\n  D-Separation\n    Query: X_i _||_ X_j | {X_(k_1), ..., X_(k_n)}\n    Check all undirected paths between X_i X_j\n    If one or more active, independence not guaranteed\n    otherwise, guaranteed\n  Summary\n    BN compactly encode joint distribution\n    Guaranteed independence of distributions deduced from graph structure\n    D-separation gives precise conditional independence from graph alone\n    BN's joint distribution may have further conditional independence that\n      is not detectable until you inspect its specific distribution\n  Inference\n    Examples:\n      Posterior Probability\n        P(Q|E1 = e1, ... E_k = ek)\n      Most likely explanation\n        argmax_q P(Q = q|E1 = e1...)\n    Inference by enumeration in Bayes' Net\n      Use inference by enumeration\n      Slow bc join whole joint distribution before sum out hidden variables\n    Advance technique: Variable elimination\n      \n\n\n## Module 11 Definitions\n* **Independence** - two vars independent if forall x, y: P(x, y) = P(x)P(y)   or P(x|y) = P(x), shown as X _||_ Y\n* **Inference** - calculate some useful quantity from a joint probability   distribution\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "  Model-based classification\n",
        "    Build model where label, features are RVs\n",
        "    Instantiate any observed features\n",
        "    Query for distribution of label condition on features\n",
        "  Naive Bayes: Assume all features are independent effects of label\n",
        "  General Naive Bayes\n",
        "    P(Y, F1 ... Fn) = P(Y)Pi_i P(Fi|Y)\n",
        "    Parameters linear w number of features\n",
        "  Inference for Naive Bayes\n",
        "    Compute posterior distribution over label variable Y\n",
        "    Step 1: get joint probability of label + evidence for each label\n",
        "    Step 2: sum to get probability of evidence\n",
        "    Step 3: normalize by dividing Step 1 by Step 2\n",
        "  What do we need for Naive Bayes?\n",
        "    Inference method\n",
        "      Start with P(Y) and P(Fi|Y)\n",
        "      Standard inference to compute P(Y|F1 ... Fn)\n",
        "    Estimate of local conditional probability tables\n",
        "      P(Y) prior over labels\n",
        "      P(Fi|Y) for each feature (evidence variable)\n",
        "      These probabilities are collectively called the parameters of the model\n",
        "        denoted by theta\n",
        "  Naive Bayes for Text\n",
        "    Bag of Words Naive Bayes\n",
        "    Features: Wi is word at position i\n",
        "    As before: predict label conditioned on feature variables\n",
        "    As before: assume features are conditionally independent given label\n",
        "    New: each Wi is identically distributed\n",
        "    General model:\n",
        "      P(Y, W1 ... Wn) = P(Y)Pi_i P(Wi|Y)\n",
        "    Tied distributions and bag of words\n",
        "      Usually each variable get its own conditional probability distribution\n",
        "        P(F|Y)\n",
        "      In bag of word model\n",
        "        Each position is identically distributed\n",
        "        All positions share same conditional probs P(W|Y)\n",
        "      Called bag of words because model is insensitive to word order\n",
        "  Data: labeled instances\n",
        "    Training set/held out set/test set\n",
        "  Features: attribute-value pairs which characterize each x\n",
        "  Experimentation cycle\n",
        "    Learn parameters (e.g. model probabilities) on training set\n",
        "    Tune hyperparameters on held-out set\n",
        "    Compute accuracy of test set\n",
        "    Very important: never peek at the test set\n",
        "  Evaluation\n",
        "    Accuracy: fraction of instances predicted correctly\n",
        "  Overfitting and generalization\n",
        "    Want a classifier which does well on test data\n",
        "    Overfitting: fitting training data closely, but not generalizing well\n",
        "  Relative frequency parameters will overfit the training data\n",
        "    need to smooth/regularize estimates\n",
        "  Parameter estimation\n",
        "    Use training data\n",
        "    For each outcome x, look at the empirical rate of that value\n",
        "    This is the estimate that maximizes likelihood of the data\n",
        "  Maximum Likelihood\n",
        "    Relative frequencies are maximum likelihood estimates\n",
        "    P_ML(x) = count(x) / total samples\n",
        "    theta_ML = argmax_theta Pi_i P_theta(X_i)\n",
        "  Laplace Smoothing\n",
        "    Laplace's estimate\n",
        "      P_LAP(x) = c(x) + 1 / N + |X|\n",
        "    Extended\n",
        "      Pretend you saw every outcome k extra times\n",
        "      k = strength of prior\n",
        "      P_LAP,k(x) = c(x) + k / N + k|X|\n",
        "      for conditionals\n",
        "      P_LAP,k(x|y) = c(x, y) + k / c(y) + k |X|\n",
        "  Estimation: Linear interpolation\n",
        "    get empirical P(X)\n",
        "    make sure P(X|Y) isn't too different from P(X)\n",
        "    P_LIN(x|y) = alpha P^hat(x|y) + (1.0 - alpha)P^hat(x)\n",
        "  Two unknowns: parameters, hyperparameters\n",
        "    Learn parameters from training data\n",
        "    Tune hyperparameters on different data \n",
        "  Baselines\n",
        "    First step: get a baseline\n",
        "      Help determine how hard task is, what is \"good\" accuracy\n",
        "    Weak baseline: most frequent label classifier'\n",
        "    Better is previous work for real research\n",
        "  Confidence of a probabilistic classifier\n",
        "    Posterior over the top label\n",
        "    confidence(x) = max_y P(y|x)\n",
        "    how sure classifier is of classification\n",
        "    Weak calibration: higher confidence => higher accuracy\n",
        "    Strong calibration: confidence predicts accuracy rate\n",
        "  Summary\n",
        "    Bayes rule let us do diagnostic queries with causal probabilities\n",
        "    Naive Bayes takes all features to be independent given class label\n",
        "    smoothing estimates important\n",
        "  Perceptron\n",
        "  Linear classifiers\n",
        "    Inputs = feature values\n",
        "    feature has weight\n",
        "    sum is activation\n",
        "    activation_w(x) = sum_i w_i * f_i(x) = w * f(x)\n",
        "    positive activation output 1\n",
        "    negative, output -1\n",
        "  Binary decision rules\n",
        "    Weight vector is a hyperplane\n",
        "    one side +1, other -1\n",
        "  Learning: Binary perceptron\n",
        "    start with weights = 0\n",
        "    for each training instance classify with current weight\n",
        "    y = +1 if w * f(x) >= 0\n",
        "    = -1 if w * f(x) < 0\n",
        "    if correct, no change\n",
        "    wrong, adjust weight vector\n",
        "    w = w + y* * f\n",
        "  Multiclass decision rule\n",
        "    w_y weight vector for each class\n",
        "    w_y * f(x) score of a class y\n",
        "    prediction highest score wins\n",
        "    y = argmax_y w_y * f(x)\n",
        "    predict\n",
        "      y = argmax_y w_y * f(x)\n",
        "      if wrong\n",
        "        w_y = w_y - f(x)\n",
        "        w_y* = w_y* + f(x)\n",
        "  Perceptron property\n",
        "    Separability: true if parameters get training set perfectly correct\n",
        "    Convergence: if training is separable, perceptron eventually converge\n",
        "    Mistake bound: max number of mistakes related to margin/degree of\n",
        "      separability\n",
        "      mistakes < k / delta^2\n",
        "  Problems with perceptron\n",
        "    noise: averaging weight vectors over time can help\n",
        "    mediocre generalization - barely separating solution\n",
        "    overtraining test\n",
        "  Fixing perceptron\n",
        "    adjust weight update to mitigate effects\n",
        "    MIRA* choose update size that fixes mistake but minimizes change to w\n",
        "    min_w 1/2 sigma_y ||w_y - w'_y||^2\n",
        "    w_y* * f(x) >= w_y * f(x) + 1\n",
        "    minimum correcting update\n",
        "    tau = (w'_y - w'_y*) * f + 1 / 2f * f\n",
        "    maximum step size\n",
        "      bad to make updates too large\n",
        "      solution: cap maximum possible value w some constant c\n",
        "      converges faster than perceptron, better on noisy data\n",
        "  Support Vector Machines\n",
        "    Maximize the margin\n",
        "    SVM find separator with max margin\n",
        "    min_w 1/2 ||w||^2\n",
        "    forall i,y w_y* * f(x_i) >= w_y * f(x_i) + 1\n",
        "  Perceptrons/MIRA vs Naive Bayes\n",
        "    Makes less assumptions about data\n",
        "    Mistake driven learning\n",
        "    Multiple passes through data\n",
        "    Often more accurate\n",
        "  Non-linear separators\n",
        "    Can map to higher dimensional space\n",
        "    Original feature space can always be mapped to some higher dimensional\n",
        "      feature space where training set is separable\n",
        "  Logical functions\n",
        "    Perceptrons can compute any logical gate\n",
        "    XOR problem\n",
        "      a single neural unit cannot comptue XOR function\n",
        "  Activation Functions\n",
        "    Instead of directly outputting z = w*x + b\n",
        "    Neuron units apply non-linear function f to z\n",
        "    Output is activation value for unit, represented by a\n",
        "    y = a = f(z)\n",
        "    Commonly used ones: sigmoid, tanh, rectified lienar unit ReLU\n",
        "  \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"Parameter Estimation\" : \"Estimating the distribution of a random variable\",\n",
        "\"Laplace's estimate\" : \"Pretend you saw every outcome once more than you \\\n",
        "  actually did\",\n",
        "\"perceptron's bias\" : \"-1 * threshold\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ed2c7a54-f00c-4898-9f25-0b28b7670e45"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n  Model-based classification\n    Build model where label, features are RVs\n    Instantiate any observed features\n    Query for distribution of label condition on features\n  Naive Bayes: Assume all features are independent effects of label\n  General Naive Bayes\n    P(Y, F1 ... Fn) = P(Y)Pi_i P(Fi|Y)\n    Parameters linear w number of features\n  Inference for Naive Bayes\n    Compute posterior distribution over label variable Y\n    Step 1: get joint probability of label + evidence for each label\n    Step 2: sum to get probability of evidence\n    Step 3: normalize by dividing Step 1 by Step 2\n  What do we need for Naive Bayes?\n    Inference method\n      Start with P(Y) and P(Fi|Y)\n      Standard inference to compute P(Y|F1 ... Fn)\n    Estimate of local conditional probability tables\n      P(Y) prior over labels\n      P(Fi|Y) for each feature (evidence variable)\n      These probabilities are collectively called the parameters of the model\n        denoted by theta\n  Naive Bayes for Text\n    Bag of Words Naive Bayes\n    Features: Wi is word at position i\n    As before: predict label conditioned on feature variables\n    As before: assume features are conditionally independent given label\n    New: each Wi is identically distributed\n    General model:\n      P(Y, W1 ... Wn) = P(Y)Pi_i P(Wi|Y)\n    Tied distributions and bag of words\n      Usually each variable get its own conditional probability distribution\n        P(F|Y)\n      In bag of word model\n        Each position is identically distributed\n        All positions share same conditional probs P(W|Y)\n      Called bag of words because model is insensitive to word order\n  Data: labeled instances\n    Training set/held out set/test set\n  Features: attribute-value pairs which characterize each x\n  Experimentation cycle\n    Learn parameters (e.g. model probabilities) on training set\n    Tune hyperparameters on held-out set\n    Compute accuracy of test set\n    Very important: never peek at the test set\n  Evaluation\n    Accuracy: fraction of instances predicted correctly\n  Overfitting and generalization\n    Want a classifier which does well on test data\n    Overfitting: fitting training data closely, but not generalizing well\n  Relative frequency parameters will overfit the training data\n    need to smooth/regularize estimates\n  Parameter estimation\n    Use training data\n    For each outcome x, look at the empirical rate of that value\n    This is the estimate that maximizes likelihood of the data\n  Maximum Likelihood\n    Relative frequencies are maximum likelihood estimates\n    P_ML(x) = count(x) / total samples\n    theta_ML = argmax_theta Pi_i P_theta(X_i)\n  Laplace Smoothing\n    Laplace's estimate\n      P_LAP(x) = c(x) + 1 / N + |X|\n    Extended\n      Pretend you saw every outcome k extra times\n      k = strength of prior\n      P_LAP,k(x) = c(x) + k / N + k|X|\n      for conditionals\n      P_LAP,k(x|y) = c(x, y) + k / c(y) + k |X|\n  Estimation: Linear interpolation\n    get empirical P(X)\n    make sure P(X|Y) isn't too different from P(X)\n    P_LIN(x|y) = alpha P^hat(x|y) + (1.0 - alpha)P^hat(x)\n  Two unknowns: parameters, hyperparameters\n    Learn parameters from training data\n    Tune hyperparameters on different data \n  Baselines\n    First step: get a baseline\n      Help determine how hard task is, what is \"good\" accuracy\n    Weak baseline: most frequent label classifier'\n    Better is previous work for real research\n  Confidence of a probabilistic classifier\n    Posterior over the top label\n    confidence(x) = max_y P(y|x)\n    how sure classifier is of classification\n    Weak calibration: higher confidence => higher accuracy\n    Strong calibration: confidence predicts accuracy rate\n  Summary\n    Bayes rule let us do diagnostic queries with causal probabilities\n    Naive Bayes takes all features to be independent given class label\n    smoothing estimates important\n  Perceptron\n  Linear classifiers\n    Inputs = feature values\n    feature has weight\n    sum is activation\n    activation_w(x) = sum_i w_i * f_i(x) = w * f(x)\n    positive activation output 1\n    negative, output -1\n  Binary decision rules\n    Weight vector is a hyperplane\n    one side +1, other -1\n  Learning: Binary perceptron\n    start with weights = 0\n    for each training instance classify with current weight\n    y = +1 if w * f(x) >= 0\n    = -1 if w * f(x) < 0\n    if correct, no change\n    wrong, adjust weight vector\n    w = w + y* * f\n  Multiclass decision rule\n    w_y weight vector for each class\n    w_y * f(x) score of a class y\n    prediction highest score wins\n    y = argmax_y w_y * f(x)\n    predict\n      y = argmax_y w_y * f(x)\n      if wrong\n        w_y = w_y - f(x)\n        w_y* = w_y* + f(x)\n  Perceptron property\n    Separability: true if parameters get training set perfectly correct\n    Convergence: if training is separable, perceptron eventually converge\n    Mistake bound: max number of mistakes related to margin/degree of\n      separability\n      mistakes < k / delta^2\n  Problems with perceptron\n    noise: averaging weight vectors over time can help\n    mediocre generalization - barely separating solution\n    overtraining test\n  Fixing perceptron\n    adjust weight update to mitigate effects\n    MIRA* choose update size that fixes mistake but minimizes change to w\n    min_w 1/2 sigma_y ||w_y - w'_y||^2\n    w_y* * f(x) >= w_y * f(x) + 1\n    minimum correcting update\n    tau = (w'_y - w'_y*) * f + 1 / 2f * f\n    maximum step size\n      bad to make updates too large\n      solution: cap maximum possible value w some constant c\n      converges faster than perceptron, better on noisy data\n  Support Vector Machines\n    Maximize the margin\n    SVM find separator with max margin\n    min_w 1/2 ||w||^2\n    forall i,y w_y* * f(x_i) >= w_y * f(x_i) + 1\n  Perceptrons/MIRA vs Naive Bayes\n    Makes less assumptions about data\n    Mistake driven learning\n    Multiple passes through data\n    Often more accurate\n  Non-linear separators\n    Can map to higher dimensional space\n    Original feature space can always be mapped to some higher dimensional\n      feature space where training set is separable\n  Logical functions\n    Perceptrons can compute any logical gate\n    XOR problem\n      a single neural unit cannot comptue XOR function\n  Activation Functions\n    Instead of directly outputting z = w*x + b\n    Neuron units apply non-linear function f to z\n    Output is activation value for unit, represented by a\n    y = a = f(z)\n    Commonly used ones: sigmoid, tanh, rectified lienar unit ReLU\n  \n\n\n## Module 12 Definitions\n* **Parameter estimation** - Estimating the distribution of a random variable\n* **Laplace's estimate** - Pretend you saw every outcome once more than you   actually did\n* **Perceptron's bias** - -1 * threshold\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "  Logistic Regression\n",
        "  Classifier components\n",
        "  ML classifiers require M observations input/output pairs (xi,yi)\n",
        "    1. feature representation of input. for each xi, [x1, x2, x3,...]\n",
        "    2. classification function computes y hat via p(y|x)\n",
        "    3. objective function for learning, usually minimize error\n",
        "    4. algo to ooptimize objective function\n",
        "  Sentiment classifier\n",
        "    Positive (1) or negative (0)\n",
        "    Want to estimate P(y=1|x)\n",
        "    Logistic regression uses vector of weights and bias term\n",
        "    z = w dot x + b\n",
        "  Decision boundary\n",
        "  Learning in logistic regression\n",
        "    Loss function\n",
        "      For some x, how class is classifier output to correct output\n",
        "      L(y^hat, y)\n",
        "      mean squared error\n",
        "        L_MSE(y^hat, y) = 1/2 (y^hat - y)^2\n",
        "      Cross-entropy loss\n",
        "        Conditional MLE: choose parameters w, b that max the log prob of\n",
        "          true labels in training data\n",
        "        Resulting loss function is negative log likelihood loss, aka\n",
        "        cross-entropy loss\n",
        "    Algorithm to optimize objective function\n",
        "      Stochastic gardient descent\n",
        "  Loss function for classification\n",
        "    maximize p(y|x) = y^hat^y (1-y^hat)^(1-y)\n",
        "    y=1 => p(y|x) = y^hat\n",
        "    y=0 => p(y|x) = 1-y^hat\n",
        "    change to logs\n",
        "      log p(y|x) = y log y^hat + (1-y) log(1-y^hat)\n",
        "    Cross entropy loss\n",
        "    L_CE(y^hat, y) = -log p(y|x) = -[y log y^hat + (1-y)log(1-y^hat)]\n",
        "    can plug in y^hat = sigma * (w * x) + b\n",
        "    Loss should be smaller if close to correct, bigger if confused\n",
        "  Finding good parameters\n",
        "    theta^hat = argmin_theta 1/m sigma^m_i=1 L_ce(y^i, x^i; theta)\n",
        "  Gradient descent\n",
        "    For logistic function, loss func is convex\n",
        "    has one minimum, so guaranteed min\n",
        "  Learning rate\n",
        "    magnitude of amount to move in grad desc is value of slope weighted\n",
        "      by learning rate eta\n",
        "  Gradient\n",
        "    to update theta, need definition of gradient\n",
        "    DeltaL(f(x; theta), y)\n",
        "    Derivative of cross-entropy loss\n",
        "    Cost(w, b) = 1/m sigma^m_i=1 L_CE(y^hat i, y^i)\n",
        "    Loss is average loss over m examples\n",
        "  Stochastic gradient descent\n",
        "    for each training tuple\n",
        "    compute y^hat i = f(x^i; theta)\n",
        "    compute loss L(y^hat(i), y^i)\n",
        "    g <- Delta_theta L(f(x^i; theta), y^i)\n",
        "    theta <- theta - eta * g\n",
        "    return theta\n",
        "  Mini-batch training\n",
        "    stochastic gradient chooses single random ex\n",
        "    batch training - compute gradient over entire dataset\n",
        "    better estimate but longer\n",
        "    compromise is mini-batch training\n",
        "  Regularization\n",
        "    overfitting problem\n",
        "    Lasso/Ridge\n",
        "  Multinomial logistic regression\n",
        "    softmax(z_i) = e^(z_j) / sigma^k_j=1 e^(z_j) 1 <= i <= k\n",
        "    softmax takes input vector, output vector vals normalized into probabilities\n",
        "  Neural Networks\n",
        "    Problem: small change in weight/bias can cause output to flip\n",
        "    Solution: sigmoid neuron\n",
        "  Smoothness crucial\n",
        "    Smoothness of sigma => small changes in weight/bias = small change in output\n",
        "    delta_output ~= sigma_j delta output/delta w_j * Delta w_j +\n",
        "      delta output / delta b * Delta b\n",
        "    Delta output is linear function wrt Delta wj, Delta b\n",
        "  Feed-Forward Neural Network\n",
        "    Simplest NN\n",
        "    Multilayer network, all units fully connected, no cycles\n",
        "    Single hidden unit has w, b (weight vector, bias scalar)\n",
        "    combine for hidden layer is weight matrix W and single bias b\n",
        "    advantage is using matrix operations\n",
        "    U is weight matrix\n",
        "    h = sigma(Wx + b)\n",
        "    z = Uh\n",
        "    y = softmax(z)\n",
        "  Training Neural Nets\n",
        "    loss function - cross-entropy loss\n",
        "    optimization algo - gradient descent\n",
        "    compute gradient of loss - error propogation\n",
        "  Multinomial cross-entropy loss\n",
        "    L_CE(y^hat, y) = -sigma^C_i=1 y_i log y^hat_i\n",
        "  Computation graph\n",
        "    Backward differentiation\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"gradient descent\" : \"method finds min of func by figuring in which \\\n",
        "  direction (in space of params theta) the slope is most steep, \\\n",
        "  then move opp-dir\",\n",
        "\"learning rate\" : \"magnitude of amount to move in gradient descent\",\n",
        "\"theta\" : \"weights to func\",\n",
        "\"Lasso\" : \"L1 regularization\",\n",
        "\"Ridge\" : \"L2 regularization\",\n",
        "\"softmax function\" : \"generalization of sigmoid\",\n",
        "\"vector h\" : \"output of hidden layer\",\n",
        "\"Computation graph\" : \"process of computing math expression, broken down into \\\n",
        "  separate operations i.e. one node=op\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "e2427520-704c-4f97-eb5f-748313fbb126"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'gradient descent' is too long!\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n  Logistic Regression\n  Classifier components\n  ML classifiers require M observations input/output pairs (xi,yi)\n    1. feature representation of input. for each xi, [x1, x2, x3,...]\n    2. classification function computes y hat via p(y|x)\n    3. objective function for learning, usually minimize error\n    4. algo to ooptimize objective function\n  Sentiment classifier\n    Positive (1) or negative (0)\n    Want to estimate P(y=1|x)\n    Logistic regression uses vector of weights and bias term\n    z = w dot x + b\n  Decision boundary\n  Learning in logistic regression\n    Loss function\n      For some x, how class is classifier output to correct output\n      L(y^hat, y)\n      mean squared error\n        L_MSE(y^hat, y) = 1/2 (y^hat - y)^2\n      Cross-entropy loss\n        Conditional MLE: choose parameters w, b that max the log prob of\n          true labels in training data\n        Resulting loss function is negative log likelihood loss, aka\n        cross-entropy loss\n    Algorithm to optimize objective function\n      Stochastic gardient descent\n  Loss function for classification\n    maximize p(y|x) = y^hat^y (1-y^hat)^(1-y)\n    y=1 => p(y|x) = y^hat\n    y=0 => p(y|x) = 1-y^hat\n    change to logs\n      log p(y|x) = y log y^hat + (1-y) log(1-y^hat)\n    Cross entropy loss\n    L_CE(y^hat, y) = -log p(y|x) = -[y log y^hat + (1-y)log(1-y^hat)]\n    can plug in y^hat = sigma * (w * x) + b\n    Loss should be smaller if close to correct, bigger if confused\n  Finding good parameters\n    theta^hat = argmin_theta 1/m sigma^m_i=1 L_ce(y^i, x^i; theta)\n  Gradient descent\n    For logistic function, loss func is convex\n    has one minimum, so guaranteed min\n  Learning rate\n    magnitude of amount to move in grad desc is value of slope weighted\n      by learning rate eta\n  Gradient\n    to update theta, need definition of gradient\n    DeltaL(f(x; theta), y)\n    Derivative of cross-entropy loss\n    Cost(w, b) = 1/m sigma^m_i=1 L_CE(y^hat i, y^i)\n    Loss is average loss over m examples\n  Stochastic gradient descent\n    for each training tuple\n    compute y^hat i = f(x^i; theta)\n    compute loss L(y^hat(i), y^i)\n    g <- Delta_theta L(f(x^i; theta), y^i)\n    theta <- theta - eta * g\n    return theta\n  Mini-batch training\n    stochastic gradient chooses single random ex\n    batch training - compute gradient over entire dataset\n    better estimate but longer\n    compromise is mini-batch training\n  Regularization\n    overfitting problem\n    Lasso/Ridge\n  Multinomial logistic regression\n    softmax(z_i) = e^(z_j) / sigma^k_j=1 e^(z_j) 1 <= i <= k\n    softmax takes input vector, output vector vals normalized into probabilities\n  Neural Networks\n    Problem: small change in weight/bias can cause output to flip\n    Solution: sigmoid neuron\n  Smoothness crucial\n    Smoothness of sigma => small changes in weight/bias = small change in output\n    delta_output ~= sigma_j delta output/delta w_j * Delta w_j +\n      delta output / delta b * Delta b\n    Delta output is linear function wrt Delta wj, Delta b\n  Feed-Forward Neural Network\n    Simplest NN\n    Multilayer network, all units fully connected, no cycles\n    Single hidden unit has w, b (weight vector, bias scalar)\n    combine for hidden layer is weight matrix W and single bias b\n    advantage is using matrix operations\n    U is weight matrix\n    h = sigma(Wx + b)\n    z = Uh\n    y = softmax(z)\n  Training Neural Nets\n    loss function - cross-entropy loss\n    optimization algo - gradient descent\n    compute gradient of loss - error propogation\n  Multinomial cross-entropy loss\n    L_CE(y^hat, y) = -sigma^C_i=1 y_i log y^hat_i\n  Computation graph\n    Backward differentiation\n\n\n## Module 13 Definitions\n* **Gradient descent** - method finds min of func by figuring in which   direction (in space of params theta) the slope is most steep,   then move opp-dir\n* **Learning rate** - magnitude of amount to move in gradient descent\n* **Theta** - weights to func\n* **Lasso** - L1 regularization\n* **Ridge** - L2 regularization\n* **Softmax function** - generalization of sigmoid\n* **Vector h** - output of hidden layer\n* **Computation graph** - process of computing math expression, broken down into   separate operations i.e. one node=op\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "  NLP\n",
        "  How represent meaning of word?\n",
        "    Encode\n",
        "      Synonyms, antonyms, connotations, semantic roles, entailment\n",
        "  Vector Space Model\n",
        "    document is point in space\n",
        "    query is pseudo document\n",
        "    perform IR by retreiving document whose vectors are close together in this\n",
        "      space to query vector\n",
        "  Document Similarity\n",
        "    Plagiarism detection\n",
        "  Context window\n",
        "    +/- n words\n",
        "    problem, long distance dependencies\n",
        "    syntax to define word's context\n",
        "  Neural Language Model > n-gram LM\n",
        "    no need smoothing\n",
        "    longer histories\n",
        "    generalize context of similar word\n",
        "    higher accuracy\n",
        "    slower to train tho\n",
        "    associate each word in vocab w/ vector rep -> notion of similarity\n",
        "    express joint prob func of word seq in terms of word vec for words\n",
        "      in that sequence\n",
        "    simultaneously learn word vectors and parameter of func\n",
        "    input: k-gram of words w_1:k\n",
        "    output: prob distribution over next word\n",
        "    k context word = word window\n",
        "    each word has embedding vector\n",
        "    input vector concatenates v(w) for each of the k words\n",
        "  Word2Vec\n",
        "    Predict each neighboring word in a context window of 2c of surrounding words\n",
        "    run text as implicitly supervised training data\n",
        "  Term-by-document/term-context matrices are long and sparse\n",
        "  Sparse vs dense vectors\n",
        "    Short = easier as features\n",
        "    Dense = generalize better\n",
        "  Skip-gram algo\n",
        "    1. treat target word/neighbor context as positive examples\n",
        "    2. randomly sample other words in lexicon to get negative sample\n",
        "    3. use logistic regression to train classifier for two cases\n",
        "    4. use weights as embedding\n",
        "  How compute p(+|t, c)\n",
        "    intuition: words are likely to appear near similar words\n",
        "    model similarity with dot product\n",
        "    similarity(t, c) ~= t dot c\n",
        "    problem, dot product is not a probability\n",
        "    use sigmoid\n",
        "    assume all context words independent\n",
        "  alpha = 3/4\n",
        "    dont use unigram frequency\n",
        "    P_alpha(w) = count(w)^alpha / sum_w count(w)^alpha\n",
        "  Summary(Word2Vec)\n",
        "    start w V random 300-dimension vectors as initial embeddings\n",
        "    use logistic regression as above\n",
        "  Solving analogies w vector embeddings\n",
        "    Embeddings capture relational meaning\n",
        "  Embeddings reflect cultural bias\n",
        "  \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"Connotation\" : \"words that are positive or negative\",   \n",
        "\"Semantic roles\" : \"buy, sell, pay are different parts of same underlying event\",\n",
        "\"entailment\" : \"a => b\",\n",
        "\"word similarity\" : \"like cat and dog, similar but diff\",\n",
        "\"distributional hypothesis\" : \"similar word context = synonym\",\n",
        "\"TF-IDF\" : \"term frequency * inverse document frequency\",\n",
        "\"term frequency\" : \"how often word in document\",\n",
        "\"inverse document frequency\" : \"1/ number of documents it is in\",\n",
        "\"sparse\" : \"most elements are 0\",\n",
        "\"embeddings\" : \"vector models of meaning, good at similarity/analogies\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "cee75fdc-361d-4903-97e3-e18468cd834d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n\n  Logistic Regression\n  Classifier components\n  ML classifiers require M observations input/output pairs (xi,yi)\n    1. feature representation of input. for each xi, [x1, x2, x3,...]\n    2. classification function computes y hat via p(y|x)\n    3. objective function for learning, usually minimize error\n    4. algo to ooptimize objective function\n  Sentiment classifier\n    Positive (1) or negative (0)\n    Want to estimate P(y=1|x)\n    Logistic regression uses vector of weights and bias term\n    z = w dot x + b\n  Decision boundary\n  Learning in logistic regression\n    Loss function\n      For some x, how class is classifier output to correct output\n      L(y^hat, y)\n      mean squared error\n        L_MSE(y^hat, y) = 1/2 (y^hat - y)^2\n      Cross-entropy loss\n        Conditional MLE: choose parameters w, b that max the log prob of\n          true labels in training data\n        Resulting loss function is negative log likelihood loss, aka\n        cross-entropy loss\n    Algorithm to optimize objective function\n      Stochastic gardient descent\n  Loss function for classification\n    maximize p(y|x) = y^hat^y (1-y^hat)^(1-y)\n    y=1 => p(y|x) = y^hat\n    y=0 => p(y|x) = 1-y^hat\n    change to logs\n      log p(y|x) = y log y^hat + (1-y) log(1-y^hat)\n    Cross entropy loss\n    L_CE(y^hat, y) = -log p(y|x) = -[y log y^hat + (1-y)log(1-y^hat)]\n    can plug in y^hat = sigma * (w * x) + b\n    Loss should be smaller if close to correct, bigger if confused\n  Finding good parameters\n    theta^hat = argmin_theta 1/m sigma^m_i=1 L_ce(y^i, x^i; theta)\n  Gradient descent\n    For logistic function, loss func is convex\n    has one minimum, so guaranteed min\n  Learning rate\n    magnitude of amount to move in grad desc is value of slope weighted\n      by learning rate eta\n  Gradient\n    to update theta, need definition of gradient\n    DeltaL(f(x; theta), y)\n    Derivative of cross-entropy loss\n    Cost(w, b) = 1/m sigma^m_i=1 L_CE(y^hat i, y^i)\n    Loss is average loss over m examples\n  Stochastic gradient descent\n    for each training tuple\n    compute y^hat i = f(x^i; theta)\n    compute loss L(y^hat(i), y^i)\n    g <- Delta_theta L(f(x^i; theta), y^i)\n    theta <- theta - eta * g\n    return theta\n  Mini-batch training\n    stochastic gradient chooses single random ex\n    batch training - compute gradient over entire dataset\n    better estimate but longer\n    compromise is mini-batch training\n  Regularization\n    overfitting problem\n    Lasso/Ridge\n  Multinomial logistic regression\n    softmax(z_i) = e^(z_j) / sigma^k_j=1 e^(z_j) 1 <= i <= k\n    softmax takes input vector, output vector vals normalized into probabilities\n  Neural Networks\n    Problem: small change in weight/bias can cause output to flip\n    Solution: sigmoid neuron\n  Smoothness crucial\n    Smoothness of sigma => small changes in weight/bias = small change in output\n    delta_output ~= sigma_j delta output/delta w_j * Delta w_j +\n      delta output / delta b * Delta b\n    Delta output is linear function wrt Delta wj, Delta b\n  Feed-Forward Neural Network\n    Simplest NN\n    Multilayer network, all units fully connected, no cycles\n    Single hidden unit has w, b (weight vector, bias scalar)\n    combine for hidden layer is weight matrix W and single bias b\n    advantage is using matrix operations\n    U is weight matrix\n    h = sigma(Wx + b)\n    z = Uh\n    y = softmax(z)\n  Training Neural Nets\n    loss function - cross-entropy loss\n    optimization algo - gradient descent\n    compute gradient of loss - error propogation\n  Multinomial cross-entropy loss\n    L_CE(y^hat, y) = -sigma^C_i=1 y_i log y^hat_i\n  Computation graph\n    Backward differentiation\n\n\n## Module 14 Definitions\n* **Connotation** - words that are positive or negative\n* **Semantic roles** - buy, sell, pay are different parts of same underlying event\n* **Entailment** - a => b\n* **Word similarity** - like cat and dog, similar but diff\n* **Distributional hypothesis** - similar word context = synonym\n* **Tf-idf** - term frequency * inverse document frequency\n* **Term frequency** - how often word in document\n* **Inverse document frequency** - 1/ number of documents it is in\n* **Sparse** - most elements are 0\n* **Embeddings** - vector models of meaning, good at similarity/analogies\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": "89822b92-9a7d-4bb3-af7e-f505e11d4d63"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'Module 8 Lecture Notes' is too long!\n# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary.  $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n\n  Markovian Transition Models = Stochastic Transition Models\n    p(s' | s, a) or T(s, a, s')\n  Markov Decision Process is\n    a sequential decision problem\n    for a fully observal environment\n    with a stochastic transition model\n    that has additive rewards\n  MDPs are a non deterministic search problem => solve via expectimax search\n  To find a solution for MDPs, you need\n    Set of states S\n    Set of actions A\n    Transition function T(s, a, s')\n      probability p(s' | s, a), the probability is called the model\n    Reward function R(s, a, s')\n    Initial state s0\n    Optionally, one or more terminal states\n  Solution of an MDP is a policy pi(s) = a, in search problems called a plan\n    pi*(s) = a is optimal policy\n  Expected utility\n    Uh (of enviroment history) \n      Uh([s0, a0, s1, a1, ...])\n      = R(s0, a0, s1) + R(s1, a1, s2) + ...\n  Discounting\n    Prefer rewards now\n    Decays exponentially => 1, gamma, gamma^2, ...\n    Discount because sooner rewards probs have higher utility than later\n    Also helps algo converge\n  Stationary preference\n    [a1, a2, ...] > [b1, b2, ...] <=> [r, a1, a2, ...] > [r, b1, b2, ...]\n  If stationary preference, then only two ways to define utilities\n    Additive utility: U([r0, r1, r2, ...]) = r0 + r1 + r2\n    Discounted utility: U([r0, r1, r2, ...]) = r0 + gamma * r1, + gamma^2 * r2\n  Infinite Game Solutions\n    Finite horizon:\n      terminate after fixed T steps or\n      nonstationary policies (pi depends on time left)\n    Discounting: use 0 < gamma < 1\n      smaller gamma = smaller horizon\n    Absorbing state: guarantee that for every policy, a terminal state\n      will eventually be reached\n  Value (utility) of a state s = V*(s) acting optimally\n  Value of a q-state(s, a) = Q*(s, a)\n    expected utility starting out having taken action a from state s and\n    thereafter acting optimally\n  V*(s) = max_a Q*(s, a)\n  Q*(s, a) = sigma_s' T(s, a, s') [R(s, a, s') + gamma * V*(s')]\n  V*(s) = max_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n  Problem: states repeated and tree goes forever\n  Idea: Time-limited values\n    Define V_k(s) to be optimal value of s if the game ends in k time\n  Value iteration\n    Start with V_0(s) = 0\n    Given vector V_k(s), do one ply of expectimax\n    V_k+1 (s) <- max_a sigma_s' T(s, a, s')[R(s, a, s') + gamma V_k(s')]\n    repeat until convergence\n    Complexity of each iteration is O(S^2 * A)\n    Theorem: will converge to unique optimal values\n      approximations get refined towards optimal values\n      Policy may converge long before values do\n    Convergence\n      How do we know V_k will converge?\n        Case 1: if tree has max depth M, then V_M holds for actual untruncated\n          values\n        Case 2: if discount < 1\n          V_k and V_k+1 is viewed as depth k+1 expectimax results in nearly\n          identical search trees\n          bottom layer V_k+1 has actual rewards, V_k has zeros\n          last layer is at best all R_max, at worst R_min, but everything\n          is discounted by gamma^k\n          So V_k and V_k+1 differ at most gamma^k max |R|\n          as k increases, value converge\n  Bellman Equations\n    Definition of \"optimal utility\" via expectimax recurrence gives us\n    simple one-step lookahead relationship amongst optimal utility values\n    V*(s) = max_a Q*(s, a)\n    Q*(s, a) = sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n    V*(s) = max_a sigma_s' T(s, a, s') [R(s, a, s') + gamma * V*(s')]\n  Fixed Policies => do optimal action, do what pi says\n    For fixed policy pi,\n      V_pi(s) = sigma_s' T(s, pi(s), s')[R(s, pi(s), s') + gamma V^pi(s')]\n      How calculate?\n        idea 1: turn to updates\n          v_0^pi(s) = 0\n          v_k+w^pi(s) <- sum_s' T(s, pi(s), s')[R(,s pi(s), s') + \n                          gamma * V_k^pi(s')]\n        idea 2: just a linear system without maxes\n  Policy extraction\n    given optimal values V*(s), how act?\n    mini-expectimax (one step)\n    pi*(s) = argmax_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V*(s')]\n    if given optimal q-values, trivial\n    pi*(s) = argmax_a Q*(s, a)\n  Problems with value iteration\n    repeats bellman updates\n    => slow - O(S^2 A) per iteration\n      max rarely changes\n      policy converges long before values\n    Alternative: Policy iteration\n      step 1: policy evaluation, calculate utilities for some fixed policy\n        (not optimal tho) until convergence\n      step 2: policy improvement, update policy using one-step look-ahead with\n        resulting converged but not optimal utilities as future values\n      repeat until converges\n      still optimal and can converge much faster\n      Evaluation: for fixed current policy pi, find values with policy\n        evaluation (iterate until values converge)\n        v^(pi_i)_k+1(s) <- \n          sigma_s' T(s, pi_i(s), s')[R(s, pi_i(s), s')+gamma * V_k^(pi_i)(s')]\n        improvement, for fixed values get better policy using policy extraction\n          one step lookahead\n          pi_i+1(s) = \n            argmax_a sigma_s' T(s, a, s')[R(s, a, s') + gamma * V^(pi_i)(s')]\n  Comparison\n    Both value/policy compute same thing (optimal values)\n    Value iteration:\n      every iteration updates both the value and implicitly the policy\n      dont track policy but taking max over actions implicitly recomputes it\n    policy iteration:\n      several passes that update utilities with fixed policy\n        pass is fast bc only condier one action not all\n      after policy evaluated, new policy chosen (slow like value iter pass)\n      new policy will be better (or done)\n    both are dynamic programs for solving MDPs\n  Summary\n    compute optimal values: use value iter or policy iter\n    compute val for particular policy: policy evaluation\n    turn values into policy: policy extraction (one-step lookahead)\n    all variations of bellman updates\n    all use one-step lookahead expectimax fragments\n    differ only whether we plug in fixed policy or max over actions\n  Utilities\n    Why average utilities? instead of minimax\n    Principle of maximum expected utility\n    What utilities to use?\n      for worst case, terminal functrion scale doesnt matter\n      i.e. insensitivity to monotonic transformations\n    Summarize agent's goals\n  Preferences\n    Preference => A > B\n    Indifference => A ~ B\n    Axioms of Rationality\n      Orderability => (A > B) \\/ (B > A) \\/ (A ~ B)\n      Transitivity => (A > B) /\\ (B > C) => (A > C)\n      Continuity => (A > B > C) => there exists p st [p, A; 1-p, C] ~ B\n      Substitutability => A ~ B => [p, A; 1-p, C] ~ [p, B; 1-p, C]\n      Monotonicity => A > B => p >= q <=> [p, A; 1-p, B] >= [q, A; 1-q, B]\n  Maximum Expected Utility Principle\n    given any pref satisfying these constraints, there exists real value\n    functioned U st\n      U(A) >= U(B) <=> A >= B\n      U([p1, S1; ... ; pn, Sn]) = sigma_i pi U(Si)\n    i.e. values assigned by U preserve pref of both prizes and lotteries\n    - Choose action that maximizes expected utility\n    - note agent can be rational (consistent with MEU) without ever\n    representing/manipulating utilities/probabilities\n  Utilities Scales\n    Normalized Utilities: u_+ = 1.0, u_- = 0.0\n    Micromorts: 1/million chance of death,\n      good for paying to reduce product risk\n    QALYs: quality-adjusted life years, useful for medical decisions w risk\n    Behavior is invariant under positive linear transformation\n      U'(x) = k_1 * U(x) + k2 where k1 > 0\n    W/ deterministic prizes only, only ordinal utility can be determined\n  Human Utilities\n    How get number of human utility\n    Standard approach:\n      Compare prize A to standard lottery L_p between\n        best possible prize u+ probability p\n        worst possible catastrophe u_- with probability 1-p\n      Adjust p until indifference A ~ L_p\n      resulting p is utility [0, 1]\n  Money\n    does not behave as a utility function, but can talk about utility of\n    having money/being in debt\n    given lottery L = [p, $X; (1-p), $Y]\n      expected monetary value EMV(L) = p*X + (1-p)*Y\n      U(L) = p*U($X) + (1-p)*U($Y)\n      Typically U(L) < U(EMV(L)) => people are risk-averse\n      when deep in debt, people are risk-prone\n  Ex. Insurance\n    L = [0.5, $1000; 0.5, $0]\n    EMV(L) = $500\n    Certainty equivalent = $400\n      $100 is insurance premium\n      people pay to reduce risk\n      if everyone risk-neutral, no insurance\n  Ex. Human Rationality\n    People prefer lower EV but guaranteed\n  \n\n## Module 8 Definitions\n* **Utility function** - Reward for agent when moving from s to s' via a\n* **Policy** - solution for an MDP\n* **Expected utility** - average utility of all possible paths from policy\n* **Principle of maximum expected utility** - a rational agent should choose the   action that maximizes its expected utility, given its knowledge\n* **Insensitivity to monotonic transformations** - better states higher eval   i.e. just get order right\n* **Utilities** - functions from outcomes to real numbers that describe pref\n* **Lotteries** - situations with uncertain prizes, L = [p, A; (1-p), B]\n* **Ordinal utility** - total order on prizes\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n  Offline Planning\n    Determine quantities through computation\n    need to know details of MDP, don't actually play game\n  Reinforcement Learning - an MDP but cant just use computation\n    need to act to figure out\n    Basic idea:\n      Receive feedback in form of rewards\n      Agents utility is defined by the reward function\n      learn to maximize expected rewards\n      all learning based on observed sample of outcomes\n    Still assume a MDP\n      set of states S\n      set of actions (per state) A\n      model T(s, a, s')\n      reward function R(s, a, s')\n      looking for pi(s)\n      twist: don't know T or R\n  Model-Based Learning\n    Model-Based idea:\n      learn approximate model based on exp\n      solve for values as if learned model was correct\n      step 1: learn empirical MDP model\n        count outcomes s' for each s, a\n        normalize to give an estimate of T^(hat)(s, a, s')\n        discover each R^(hat)(s, a, s') when we experience (s, a, s')\n      step 2: solve learned MDP\n        ex. use value iteration\n  Passive Reinforcement Learning\n    Simplified task: policy evaluation\n    input: fixed policy pi(s)\n    dont know transitions T(s, a, s'), rewards R(s, a, s')\n    Goals: learn state values\n    Learner along for the ride, no choice about actions, just execute and learn\n  Direct Evaluation\n    Goal: compute values for each state under pi\n    Idea: average together observed sample values\n      act according to pi\n      everytime visit a state, write down sum of discounted rewards\n      average samples\n    Good:\n      easy, no knowledge of T, R, eventually computes correct average values\n    Bad:\n      wastes info about state connections, each state learned separately\n  Why not use policy evaluation/bellman updates? - we need T and R\n  Solution: sample-based policy evaluation\n    Want to improve our estimate of V by computing these averages\n      V^pi_k+1(s) <- \n        sigma_s' T(s, pi(s), s')[R(s, pi(s), s') + gamma * V^pi_k(s')]\n    samples of outcomes s' by doing action and average\n      sample1 = R(s, pi(s), s1') + gamma * V^pi_k(s1')\n      sample2 = R(s, pi(s), s2') + gamma * V^pi_k(s2')\n      ...\n      V^pi_k+1(s) <- (1/n) * sigma_i sample_i\n  Temporal Difference Learning\n    Learn from every experience\n    Update V(s) every time experience transition (s, a, s', r)\n    Likely outcomes s' will contribute updates more often\n    Policy still fixed, still doing evaluation\n    Essentially running average\n    Sample of V(s): sample = R(s, pi(s), s') + gamma * V^pi(s')\n    Update to V(s): V^pi(s) <- (1-alpha)V^pi(s) + (alpha)sample\n    Same update: V^pi(s) <- V^pi(s) + alpha(sample - V^pi(s))\n  Exponential Moving Average\n    Running interpolation update: x^bar_n = (1-alpha)x^bar_n-1 + alpha * x_n\n    Recent samples are more important\n    x^bar_n = (x_n + (1-alpha)x_n-1 + (1-alpha)^2 x_n-2 + ...) \n      / (1 + (1-alpha) + (1-alpha)^2)\n    Decreasing alpha can give converging averages\n  Problems with TD Value Learning\n    model-free way to do policy evaluation, mimicking bellman updates w/\n      running sample averages\n    If we want to turn values into new policy, fails\n    Idea: learn Q-values, not values\n    Makes action selection model free too\n  Active Reinforcement Learning\n    Full reinforcement learning\n      You don't know the transition, rewards\n      You choose actions now\n      Goal: learn optimal policy/values\n    Learner makes choice\n      fundamental tradeoff: exploration vs exploitation\n    Not offline planning\n  Q-Value Iteration\n    Value iteration: find successive (depth-limited) values\n    But Q-values are more useful, so compute instead\n    Q0(s, a) = 0, guaranteed right\n    Given Q_k, calculate depth k+1 q-vals for all q-states\n    Q_k+1(s, a) <-\n      sigma_s' T(s, a, s')[R(s, a, s') + gamma * max_a' Q_k(s', a')]\n  Q-learning: sample based Q-value iteration\n    Q_k+1(s, a) <-\n      sigma_s' T(s, a, s') [R(s, a, s') + gamma * max_a' Q_k(s', a')]\n    Learn Q(s, a) as you go\n    Receive sample (s, a, s', r)\n    Consider old estimate Q(s, a)\n    Consider your new sample estimate\n      sample = R(s, a, s') + gamma * max_a' Q(s', a')\n      Incorporate new estimate into running average\n      Q(s, a) <- (1-alpha)Q(s, a) + (alpha)[sample]\n    Properties\n      Q-learning converges to optimal policy, even if acting suboptimally\n      Off-policy learning\n      Caveats\n        Have to explore enough\n        Have to eventually make learning rate small enough, but not decrease\n        too quickly\n  How to explore?\n    Simplest: random actions (epsilon-greedy)\n      Every time step, flip a coin\n      With small prob epsilon, act randomly\n      With large prob 1-epsilon, act on current policy\n      Problems:\n        eventually explore space, but keep thrashing around until learning done\n        One solution: lower epsilon over time\n        Another: exploration functions\n  Exploration functions\n    Idea: explore areas whose badness is not yet established, eventually\n      stop exploring\n    Func: takes a value estimate u and a visit count n, and returns an\n      optimistic utility f(u, n) = u + k/n\n    Regular Q-update: Q(s, a) <-_alpha R(s, a, s') + gamma * max_a' Q(s', a')\n    Modified Q-update: Q(s, a) <-_alpha\n      R(s, a, s') + gamma * max_a' f(Q(s', a'), N(s', a'))\n    Regret:\n      difference between your expected rewards including youthful suboptimality\n      and optimal expected rewards\n      Minimizing regret requires optimally learning be optimal\n        Ex. random exploration and exploration functions both optimal, but\n          random exploration has higher regret\n  Approximate Q-Learning\n    Generalizing across states\n    Basic Q-learning keeps table of all q values\n    Realistically, can't learn about every single state\n    Generalize: learn about some small number of training states from experience\n      Generalize to new, similar situations\n    Flashback: evaluation functions\n      ideal function: returns actual minimax value of position\n      in practice: weighted linear sum of features\n    Linear Value Functions\n      w/ feature representation, write q func for any state\n      V(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)\n      Q(s, a) = w1f1(s, a) + w2f2(s, a) + ... + wnfn(s, a)\n      Adv: our experience summed up in a few numbers\n      Disadv: states may share features, but be very diff in value\n    Key formula\n      Q(s, a) = w1f1(s, a) + w2f2(s, a) + ... + wnfn(s, a)\n    Q-learning with linear Q-functions\n      transitions = (s, a, r, s')\n      difference = [r + gamma * max_a' Q(s', a')] - Q(s, a)\n      Q(s, a) <- Q(s, a) + alpha[difference]\n      w_i <- w_i + alpha[difference]f_i(s, a)\n      Intuitive interpretation:\n        adjust weights of active features\n      Formal justification: online least squares\n\n\n## Module 9 Definitions\n* **Exploration** - Try unknown actions to get information\n* **Exploitation** - Eventually, have to use what you know\n* **Regret** - Even if learn intelligently, make mistakes\n* **Sampling** - Because of chance, have to try repeatedly\n* **Difficulty** - Learning harder than solving known MDP\n* **Alpha** - learning rate\n* **Off-policy learning** - converges to optimal policy even if acting suboptimally\n* **Regret** - measure of your total mistake cost\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n\n  Probabilities are about possible worlds\n    How likely a world is\n  Probability model = P(w) with each possible world w\n  Axioms of Probability\n    0 <= P(w) <= 1 for every w\n    sigma_(w in Omega) P(w) = 1\n  Probability Distributions\n    Joint distribution over set of Random Variable RVs\n      specify real number for each outcome\n      ex P(X1 = x1, X2 = x2, ... Xn = xn)\n      Still P(x1, x2, ...) >= 0\n      and sigma_(x1, x2, ...) P(x1, x2, ...) = 1\n  Probabilistic model\n    A joint distribution over a set of random variables\n    Assignments called outcomes\n    Noramlized: sum to 1.0\n    Ideally only certain variables directly interact\n  Event is set E of outcomes\n    P(E) = sigma_(x1, x2, ... in E) P(x1, ...)\n  Marginal distributions\n    sub-tables that eliminate variables\n    Combine collapsed rows by adding\n  Conditional probabilities\n    P(a|b) = P(a, b)/P(b)\n    probability given fixed values of other\n  Probabilistic inference\n    Inference by enumeration\n    Evidence variables: E1, ... Ek = e1, ... ek\n    Query* variables: Q\n    Hidden variables: H1, ... Hr\n    Together, all variables X1, X2, ...\n    We want P(Q|e1, ... ek)\n    Step 1: Select entries consistent w/ evidence\n      pick P(Q, e1, ..., ek)\n    Step 2: sum out hidden variables to get joint query and evidence\n      sigma_(h1..hr) P(Q, h1, ..., hr, e1, ..., ek)\n    Step 3: normalize\n      * 1/Z\n      Z = sum_q P(Q, e1, ..., ek)\n      P(Q|e1, ... ek) = 1/Z P(Q, e1, ... ek)\n  Probabilistic Language Models\n    One Goal: assign probability to a sentence\n      P(W) = P(w1, w2, ..., wn)\n      related task: probability of upcoming word\n        P(w5|w1, w2, w3, w4)\n      model is Language Model or LM\n        P(W) or P(wn|w1, ..., w_n-1)\n    Other tasks: summarization, question-answering, dialog systems\n    Better: the grammar\n  Compute P(W) using chain rule\n  Simplifying = Markov Assumption\n    Only depends on previous k words, not whole context\n    K = number of context words\n  Unigram model\n    P(w1w2...wn) = Pi_i P(wi)\n  Bigram\n    P(wi|w1w2...wi-1) = P(wi|wi-1)\n  N-gram models insufficient because of long-distance dependencies\n  Maximum Likelihood Estimate\n    P(wi|wi-1) = count(wi-1, wi) / count(wi-1)\n  Problems for MLE\n    zero probability events (never seen combo again)\n    out of vocabular items\n      use filler <unk>\n    fixed lexicon L of size V\n    normalize training day - replace words not in L with <unk>\n    avoid zeros with smoothing\n  Practical Issues\n    do everything in log space\n      avoid underflow\n      faster than multiplying\n\n\n\n## Module 10 Definitions\n* **Observed variables (evidence)** - Agent knows certain things about state   of the world e.g., sensor readings or symptoms\n* **Unobserved variable (states)** - Agent need to reason about other aspects   e.g. where an object is\n* **Mode** - Agent knows something about how the known variable relate to   unknown variables\n* **Sample space** - possible worlds, mutually exclusive and exhaustive\n* **Distribution** - table of probability values\n* **Probabilistic inference** - compute desired probability from other known   probability\n* **Product rule** - P(y)P(x|y) = P(x, y)\n* **Chain rule** - P(x1, x2, x3) = P(x1)P(x2|x1)P(x3|x1, x2)  P(x1, x2, ..., xn) = Pi_i P(xi|x1, ..., x_i-1)\n* **Bayes' rule** - P(x, y) = P(x|y)P(y) = P(y|x)P(x) =>   P(x|y) = P(y|x)/P(y) * P(x)\n* **Unigram/bigram/trigram/4-gram** - 0/1/2/3/4 word as history\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\n  Models describe how (a portion of) the world works\n  Models are always simplifications\n  Independence is a simplifying modeling assumption\n  Unconditional/absolute independence very rare\n  Conditional independence is our most basic/robust form of knowledge abt\n    uncertain events\n  X is conditionally independent of Y given Z => X _||_ Y | Z\n    iff forall x,y,z P(x, y|z) = P(x|z)P(y|z)\n    or\n    iff P(x|z, y) = P(x|z)\n  Two problems with using full joint distribution tables\n    Unless a few vars, joint is way too big\n    Hard to learn/estimate anything empirically about more than a few vars\n      at a time\n  Bayes' net\n    a technique for describing complex join distributions (models) using\n      simple local distributions (conditional probabilities)\n    called graphical models\n    local interactions chain together to give global, indirect interactions\n  Graphical Model Notation\n    Nodes: vars (w/ domains)\n      observed or unobserved (assigned or unassigned)\n    Arcs: interactions\n      direct influence between variables\n      formally encode conditional independence\n  Bayes' net semantics\n    Set of nodes, one per var\n    Directed acyclic graph\n    Conditional distribution for each node\n      collection of distributions over X, one for each combo of parents' value\n        P(X|a1, ... an)\n        a1, ... an are parents\n    CPT: conditional probability table\n    Description of a noisy causal process\n    Bayes net = topology (graph) + local conditional probabilities\n  Bayes' net implicitly encode join distributions\n    as a product of local conditional distributions\n    to see what BN gives to full assignment, multiply all relavent conditionals\n    P(x1, x2, ... xn) = Pi^n_i=1 P(xi|parents(Xi))\n    Why do we guarantee this?\n      Chain rule + assume conditional independence\n    Not every BN can represent every joint distribution\n  Causality?\n    When BN reflect true causal pattners\n    often simpler\n    BN need not actually be causal\n    What arrows mean?\n      Topology may happen to encode causul structure\n      Topology really encodes conditional independence\n  Size of BN\n    Join distribution over N boolean vars -> 2^N\n    How big is N-node net if nodes have up to k parents\n    O(N*2^k+1)\n    Save space\n    Conditional iindependence is property of distribution\n  BN Assumptions\n    Assumes additional conditional independences\n  Causal Chains\n    X->Y->Z => P(x, y, z) = P(x)P(y|x)P(z|y)\n    guaranteed X independent of Z? no\n    guaranteed X independent of Z given Y? yes\n    Common cause configuration\n    Observing an effect activates influence between possible causes\n  General Question: in a given BN, are two variables independent?\n    Solution: analyze graph\n    Reachability: almost works\n    Active/Inactive paths\n      no active paths = independence\n      Path is active if each triple is active\n        Causal chain A -> B -> C where B unobserved\n        Common cause A <- B -> C b unobserved\n        Common effect A -> B <- C\n      Only block path is single inactive segment\n  D-Separation\n    Query: X_i _||_ X_j | {X_(k_1), ..., X_(k_n)}\n    Check all undirected paths between X_i X_j\n    If one or more active, independence not guaranteed\n    otherwise, guaranteed\n  Summary\n    BN compactly encode joint distribution\n    Guaranteed independence of distributions deduced from graph structure\n    D-separation gives precise conditional independence from graph alone\n    BN's joint distribution may have further conditional independence that\n      is not detectable until you inspect its specific distribution\n  Inference\n    Examples:\n      Posterior Probability\n        P(Q|E1 = e1, ... E_k = ek)\n      Most likely explanation\n        argmax_q P(Q = q|E1 = e1...)\n    Inference by enumeration in Bayes' Net\n      Use inference by enumeration\n      Slow bc join whole joint distribution before sum out hidden variables\n    Advance technique: Variable elimination\n      \n\n\n## Module 11 Definitions\n* **Independence** - two vars independent if forall x, y: P(x, y) = P(x)P(y)   or P(x|y) = P(x), shown as X _||_ Y\n* **Inference** - calculate some useful quantity from a joint probability   distribution\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n\n  Model-based classification\n    Build model where label, features are RVs\n    Instantiate any observed features\n    Query for distribution of label condition on features\n  Naive Bayes: Assume all features are independent effects of label\n  General Naive Bayes\n    P(Y, F1 ... Fn) = P(Y)Pi_i P(Fi|Y)\n    Parameters linear w number of features\n  Inference for Naive Bayes\n    Compute posterior distribution over label variable Y\n    Step 1: get joint probability of label + evidence for each label\n    Step 2: sum to get probability of evidence\n    Step 3: normalize by dividing Step 1 by Step 2\n  What do we need for Naive Bayes?\n    Inference method\n      Start with P(Y) and P(Fi|Y)\n      Standard inference to compute P(Y|F1 ... Fn)\n    Estimate of local conditional probability tables\n      P(Y) prior over labels\n      P(Fi|Y) for each feature (evidence variable)\n      These probabilities are collectively called the parameters of the model\n        denoted by theta\n  Naive Bayes for Text\n    Bag of Words Naive Bayes\n    Features: Wi is word at position i\n    As before: predict label conditioned on feature variables\n    As before: assume features are conditionally independent given label\n    New: each Wi is identically distributed\n    General model:\n      P(Y, W1 ... Wn) = P(Y)Pi_i P(Wi|Y)\n    Tied distributions and bag of words\n      Usually each variable get its own conditional probability distribution\n        P(F|Y)\n      In bag of word model\n        Each position is identically distributed\n        All positions share same conditional probs P(W|Y)\n      Called bag of words because model is insensitive to word order\n  Data: labeled instances\n    Training set/held out set/test set\n  Features: attribute-value pairs which characterize each x\n  Experimentation cycle\n    Learn parameters (e.g. model probabilities) on training set\n    Tune hyperparameters on held-out set\n    Compute accuracy of test set\n    Very important: never peek at the test set\n  Evaluation\n    Accuracy: fraction of instances predicted correctly\n  Overfitting and generalization\n    Want a classifier which does well on test data\n    Overfitting: fitting training data closely, but not generalizing well\n  Relative frequency parameters will overfit the training data\n    need to smooth/regularize estimates\n  Parameter estimation\n    Use training data\n    For each outcome x, look at the empirical rate of that value\n    This is the estimate that maximizes likelihood of the data\n  Maximum Likelihood\n    Relative frequencies are maximum likelihood estimates\n    P_ML(x) = count(x) / total samples\n    theta_ML = argmax_theta Pi_i P_theta(X_i)\n  Laplace Smoothing\n    Laplace's estimate\n      P_LAP(x) = c(x) + 1 / N + |X|\n    Extended\n      Pretend you saw every outcome k extra times\n      k = strength of prior\n      P_LAP,k(x) = c(x) + k / N + k|X|\n      for conditionals\n      P_LAP,k(x|y) = c(x, y) + k / c(y) + k |X|\n  Estimation: Linear interpolation\n    get empirical P(X)\n    make sure P(X|Y) isn't too different from P(X)\n    P_LIN(x|y) = alpha P^hat(x|y) + (1.0 - alpha)P^hat(x)\n  Two unknowns: parameters, hyperparameters\n    Learn parameters from training data\n    Tune hyperparameters on different data \n  Baselines\n    First step: get a baseline\n      Help determine how hard task is, what is \"good\" accuracy\n    Weak baseline: most frequent label classifier'\n    Better is previous work for real research\n  Confidence of a probabilistic classifier\n    Posterior over the top label\n    confidence(x) = max_y P(y|x)\n    how sure classifier is of classification\n    Weak calibration: higher confidence => higher accuracy\n    Strong calibration: confidence predicts accuracy rate\n  Summary\n    Bayes rule let us do diagnostic queries with causal probabilities\n    Naive Bayes takes all features to be independent given class label\n    smoothing estimates important\n  Perceptron\n  Linear classifiers\n    Inputs = feature values\n    feature has weight\n    sum is activation\n    activation_w(x) = sum_i w_i * f_i(x) = w * f(x)\n    positive activation output 1\n    negative, output -1\n  Binary decision rules\n    Weight vector is a hyperplane\n    one side +1, other -1\n  Learning: Binary perceptron\n    start with weights = 0\n    for each training instance classify with current weight\n    y = +1 if w * f(x) >= 0\n    = -1 if w * f(x) < 0\n    if correct, no change\n    wrong, adjust weight vector\n    w = w + y* * f\n  Multiclass decision rule\n    w_y weight vector for each class\n    w_y * f(x) score of a class y\n    prediction highest score wins\n    y = argmax_y w_y * f(x)\n    predict\n      y = argmax_y w_y * f(x)\n      if wrong\n        w_y = w_y - f(x)\n        w_y* = w_y* + f(x)\n  Perceptron property\n    Separability: true if parameters get training set perfectly correct\n    Convergence: if training is separable, perceptron eventually converge\n    Mistake bound: max number of mistakes related to margin/degree of\n      separability\n      mistakes < k / delta^2\n  Problems with perceptron\n    noise: averaging weight vectors over time can help\n    mediocre generalization - barely separating solution\n    overtraining test\n  Fixing perceptron\n    adjust weight update to mitigate effects\n    MIRA* choose update size that fixes mistake but minimizes change to w\n    min_w 1/2 sigma_y ||w_y - w'_y||^2\n    w_y* * f(x) >= w_y * f(x) + 1\n    minimum correcting update\n    tau = (w'_y - w'_y*) * f + 1 / 2f * f\n    maximum step size\n      bad to make updates too large\n      solution: cap maximum possible value w some constant c\n      converges faster than perceptron, better on noisy data\n  Support Vector Machines\n    Maximize the margin\n    SVM find separator with max margin\n    min_w 1/2 ||w||^2\n    forall i,y w_y* * f(x_i) >= w_y * f(x_i) + 1\n  Perceptrons/MIRA vs Naive Bayes\n    Makes less assumptions about data\n    Mistake driven learning\n    Multiple passes through data\n    Often more accurate\n  Non-linear separators\n    Can map to higher dimensional space\n    Original feature space can always be mapped to some higher dimensional\n      feature space where training set is separable\n  Logical functions\n    Perceptrons can compute any logical gate\n    XOR problem\n      a single neural unit cannot comptue XOR function\n  Activation Functions\n    Instead of directly outputting z = w*x + b\n    Neuron units apply non-linear function f to z\n    Output is activation value for unit, represented by a\n    y = a = f(z)\n    Commonly used ones: sigmoid, tanh, rectified lienar unit ReLU\n  \n\n\n## Module 12 Definitions\n* **Parameter estimation** - Estimating the distribution of a random variable\n* **Laplace's estimate** - Pretend you saw every outcome once more than you   actually did\n* **Perceptron's bias** - -1 * threshold\n\n\n## WARNING: Your definition of 'gradient descent' is too long!\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n\n  Logistic Regression\n  Classifier components\n  ML classifiers require M observations input/output pairs (xi,yi)\n    1. feature representation of input. for each xi, [x1, x2, x3,...]\n    2. classification function computes y hat via p(y|x)\n    3. objective function for learning, usually minimize error\n    4. algo to ooptimize objective function\n  Sentiment classifier\n    Positive (1) or negative (0)\n    Want to estimate P(y=1|x)\n    Logistic regression uses vector of weights and bias term\n    z = w dot x + b\n  Decision boundary\n  Learning in logistic regression\n    Loss function\n      For some x, how class is classifier output to correct output\n      L(y^hat, y)\n      mean squared error\n        L_MSE(y^hat, y) = 1/2 (y^hat - y)^2\n      Cross-entropy loss\n        Conditional MLE: choose parameters w, b that max the log prob of\n          true labels in training data\n        Resulting loss function is negative log likelihood loss, aka\n        cross-entropy loss\n    Algorithm to optimize objective function\n      Stochastic gardient descent\n  Loss function for classification\n    maximize p(y|x) = y^hat^y (1-y^hat)^(1-y)\n    y=1 => p(y|x) = y^hat\n    y=0 => p(y|x) = 1-y^hat\n    change to logs\n      log p(y|x) = y log y^hat + (1-y) log(1-y^hat)\n    Cross entropy loss\n    L_CE(y^hat, y) = -log p(y|x) = -[y log y^hat + (1-y)log(1-y^hat)]\n    can plug in y^hat = sigma * (w * x) + b\n    Loss should be smaller if close to correct, bigger if confused\n  Finding good parameters\n    theta^hat = argmin_theta 1/m sigma^m_i=1 L_ce(y^i, x^i; theta)\n  Gradient descent\n    For logistic function, loss func is convex\n    has one minimum, so guaranteed min\n  Learning rate\n    magnitude of amount to move in grad desc is value of slope weighted\n      by learning rate eta\n  Gradient\n    to update theta, need definition of gradient\n    DeltaL(f(x; theta), y)\n    Derivative of cross-entropy loss\n    Cost(w, b) = 1/m sigma^m_i=1 L_CE(y^hat i, y^i)\n    Loss is average loss over m examples\n  Stochastic gradient descent\n    for each training tuple\n    compute y^hat i = f(x^i; theta)\n    compute loss L(y^hat(i), y^i)\n    g <- Delta_theta L(f(x^i; theta), y^i)\n    theta <- theta - eta * g\n    return theta\n  Mini-batch training\n    stochastic gradient chooses single random ex\n    batch training - compute gradient over entire dataset\n    better estimate but longer\n    compromise is mini-batch training\n  Regularization\n    overfitting problem\n    Lasso/Ridge\n  Multinomial logistic regression\n    softmax(z_i) = e^(z_j) / sigma^k_j=1 e^(z_j) 1 <= i <= k\n    softmax takes input vector, output vector vals normalized into probabilities\n  Neural Networks\n    Problem: small change in weight/bias can cause output to flip\n    Solution: sigmoid neuron\n  Smoothness crucial\n    Smoothness of sigma => small changes in weight/bias = small change in output\n    delta_output ~= sigma_j delta output/delta w_j * Delta w_j +\n      delta output / delta b * Delta b\n    Delta output is linear function wrt Delta wj, Delta b\n  Feed-Forward Neural Network\n    Simplest NN\n    Multilayer network, all units fully connected, no cycles\n    Single hidden unit has w, b (weight vector, bias scalar)\n    combine for hidden layer is weight matrix W and single bias b\n    advantage is using matrix operations\n    U is weight matrix\n    h = sigma(Wx + b)\n    z = Uh\n    y = softmax(z)\n  Training Neural Nets\n    loss function - cross-entropy loss\n    optimization algo - gradient descent\n    compute gradient of loss - error propogation\n  Multinomial cross-entropy loss\n    L_CE(y^hat, y) = -sigma^C_i=1 y_i log y^hat_i\n  Computation graph\n    Backward differentiation\n\n\n## Module 13 Definitions\n* **Gradient descent** - method finds min of func by figuring in which   direction (in space of params theta) the slope is most steep,   then move opp-dir\n* **Learning rate** - magnitude of amount to move in gradient descent\n* **Theta** - weights to func\n* **Lasso** - L1 regularization\n* **Ridge** - L2 regularization\n* **Softmax function** - generalization of sigmoid\n* **Vector h** - output of hidden layer\n* **Computation graph** - process of computing math expression, broken down into   separate operations i.e. one node=op\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n\n  Logistic Regression\n  Classifier components\n  ML classifiers require M observations input/output pairs (xi,yi)\n    1. feature representation of input. for each xi, [x1, x2, x3,...]\n    2. classification function computes y hat via p(y|x)\n    3. objective function for learning, usually minimize error\n    4. algo to ooptimize objective function\n  Sentiment classifier\n    Positive (1) or negative (0)\n    Want to estimate P(y=1|x)\n    Logistic regression uses vector of weights and bias term\n    z = w dot x + b\n  Decision boundary\n  Learning in logistic regression\n    Loss function\n      For some x, how class is classifier output to correct output\n      L(y^hat, y)\n      mean squared error\n        L_MSE(y^hat, y) = 1/2 (y^hat - y)^2\n      Cross-entropy loss\n        Conditional MLE: choose parameters w, b that max the log prob of\n          true labels in training data\n        Resulting loss function is negative log likelihood loss, aka\n        cross-entropy loss\n    Algorithm to optimize objective function\n      Stochastic gardient descent\n  Loss function for classification\n    maximize p(y|x) = y^hat^y (1-y^hat)^(1-y)\n    y=1 => p(y|x) = y^hat\n    y=0 => p(y|x) = 1-y^hat\n    change to logs\n      log p(y|x) = y log y^hat + (1-y) log(1-y^hat)\n    Cross entropy loss\n    L_CE(y^hat, y) = -log p(y|x) = -[y log y^hat + (1-y)log(1-y^hat)]\n    can plug in y^hat = sigma * (w * x) + b\n    Loss should be smaller if close to correct, bigger if confused\n  Finding good parameters\n    theta^hat = argmin_theta 1/m sigma^m_i=1 L_ce(y^i, x^i; theta)\n  Gradient descent\n    For logistic function, loss func is convex\n    has one minimum, so guaranteed min\n  Learning rate\n    magnitude of amount to move in grad desc is value of slope weighted\n      by learning rate eta\n  Gradient\n    to update theta, need definition of gradient\n    DeltaL(f(x; theta), y)\n    Derivative of cross-entropy loss\n    Cost(w, b) = 1/m sigma^m_i=1 L_CE(y^hat i, y^i)\n    Loss is average loss over m examples\n  Stochastic gradient descent\n    for each training tuple\n    compute y^hat i = f(x^i; theta)\n    compute loss L(y^hat(i), y^i)\n    g <- Delta_theta L(f(x^i; theta), y^i)\n    theta <- theta - eta * g\n    return theta\n  Mini-batch training\n    stochastic gradient chooses single random ex\n    batch training - compute gradient over entire dataset\n    better estimate but longer\n    compromise is mini-batch training\n  Regularization\n    overfitting problem\n    Lasso/Ridge\n  Multinomial logistic regression\n    softmax(z_i) = e^(z_j) / sigma^k_j=1 e^(z_j) 1 <= i <= k\n    softmax takes input vector, output vector vals normalized into probabilities\n  Neural Networks\n    Problem: small change in weight/bias can cause output to flip\n    Solution: sigmoid neuron\n  Smoothness crucial\n    Smoothness of sigma => small changes in weight/bias = small change in output\n    delta_output ~= sigma_j delta output/delta w_j * Delta w_j +\n      delta output / delta b * Delta b\n    Delta output is linear function wrt Delta wj, Delta b\n  Feed-Forward Neural Network\n    Simplest NN\n    Multilayer network, all units fully connected, no cycles\n    Single hidden unit has w, b (weight vector, bias scalar)\n    combine for hidden layer is weight matrix W and single bias b\n    advantage is using matrix operations\n    U is weight matrix\n    h = sigma(Wx + b)\n    z = Uh\n    y = softmax(z)\n  Training Neural Nets\n    loss function - cross-entropy loss\n    optimization algo - gradient descent\n    compute gradient of loss - error propogation\n  Multinomial cross-entropy loss\n    L_CE(y^hat, y) = -sigma^C_i=1 y_i log y^hat_i\n  Computation graph\n    Backward differentiation\n\n\n## Module 14 Definitions\n* **Connotation** - words that are positive or negative\n* **Semantic roles** - buy, sell, pay are different parts of same underlying event\n* **Entailment** - a => b\n* **Word similarity** - like cat and dog, similar but diff\n* **Distributional hypothesis** - similar word context = synonym\n* **Tf-idf** - term frequency * inverse document frequency\n* **Term frequency** - how often word in document\n* **Inverse document frequency** - 1/ number of documents it is in\n* **Sparse** - most elements are 0\n* **Embeddings** - vector models of meaning, good at similarity/analogies\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}