{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "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": "a5dfa8bf-33ae-4c32-8d91-5c6d154af422"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3af2494b-16a5-4c1d-9fe2-a88dc1363b34"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "sample_equation = r\"\"\" $P(\\textnormal{RESULT}(a)=s') = \\sum_s P(s)P(s'|s,a)$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" \n",
        "Decision theory: choose among actiins based on desirability of their immediate outcomes (episodic) \\n\n",
        "Why doesn't MEU solve the AI problem? \\n\n",
        "\\t MEU formalizes what an agent should do but doesn't operationalize it. \n",
        "\\t To use MEU, we have to estimate probability distribution and utility function \n",
        "\\t which reflects perf. measure. \\n\n",
        " \"\"\"  \n",
        "chapter16_2 =  \"\"\"\n",
        "MEU is not the only rational way to make decisions. \\n\n",
        "A ≻ B: prefer A over B \\n\n",
        "A ~ B: indifferent between A and B \\n\n",
        "A ≻~ B: prefers A over B or is indifferent between them \\n\n",
        "\n",
        "L = [p1, S1; p2, S2;...pn,Sn] || probabilities, outcomes \\n\n",
        "\n",
        "Axioms of Utility Theory -- if these violated, irrational behavior \\n\n",
        "<b>Orderability:</b> agent can't avoid deciding. so exactly 1 of 3 above principles holds \\n\n",
        "\\t Given two lotteries, a rational agent must either prefer one or be indifferent \\n\n",
        "<b>Transitivity:</b> A ≻ B and B ≻ C --> A ≻ C \\n\n",
        "<b>Continuity:</b> A ≻ B ≻ C, then there is a probability p where agent is indifferent between \\n\n",
        "lottery for A and C and sure chance of getting B. [p, A; 1-p, C] ~ B \\n\n",
        "<b>Substitutability:</b> if agent indifferent between 2 lotteries (A and B), agent is indifferent between: \\n\n",
        "[p, A; 1-p, C] ~ [p,B;1-p,C] \\n\n",
        "<b>Monotonicity:</b> if A ≻ B, agent prefers lottery with higher probability for A: \\n\n",
        "[p, A; 1-p, B] ≻ [q,A;1-q,B] (p>q) \\n\n",
        "<b>Decomposability:</b> we can reduce compound lotteries: \\n\n",
        "[p, A; 1-p, [q,B;1-q,C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C] \\n\n",
        "\n",
        "Consequences of Axioms \\n\n",
        "<b>Existence of Utility function</b>: U(A) > U(B) if and only if A ≻ B. \\n\n",
        "U(A) = U(B) if and only if A ~ B. \\n\n",
        "<b>Expected Utility of a Lottery</b>: sum of probability of each outcome * utility of outcome \\n\n",
        "\n",
        "Just because there is a utility function, doesn't mean agent is necessarily maximizing it\n",
        "\"\"\"\n",
        "chapter16_3 =  \"\"\" \n",
        "If we normalize the utilities, we can see what probablity (p) to assign to the min utility \\n \n",
        "and (1-p) to max utility so that p equals the value of the outcome we're looking at. \\n\n",
        "To find the value that people place on their lives: micromort, QALY \\n\n",
        "Money has a monotonic preference (always prefer more). Utility function is NOT monotonic \n",
        "(i.e. many people would turn down a gamble for more money compared to get less money for sure ) \\n\n",
        "Risk-averse agents have a concave down utility curve. Risk-neutral have linear curve. \\n\n",
        "\n",
        "Allias paradox: \\n\n",
        "Descriptive theory shows a different way of people choosing between 2 options to get money than normative theory. \\n\n",
        "This could be because of the certainty effect -- people want the upside that they are guaranteed of rather \\n\n",
        "than a higher one that they have a chance, not for sure, of getting \\n\n",
        "Ellsberg paradox: \\n\n",
        "\\t people have ambiguity aversion -- they would rather go with a known chance than \n",
        "\\t a chance that is unknown \\n\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \n",
        "Markov Decision Process (MDP): a sequential decision problem for a fully observable, stochastic environment with \\n\n",
        "a Markovian transition model and additive rewards.\n",
        "\\t has: set of states, actions, transition model, reward function, initial state || terminal state is optional\n",
        "\\t the solution is a policy - there can be multiple optimal policies.\n",
        "\\t even if same policy executed muliple times, could get different state/action sequence\n",
        "\\t can solve using DP \\n\n",
        "\n",
        "If we use discounted utilities w/ infinite horizons, optimal policy is independent of starting state \\n\n",
        "\n",
        "Why do we use additive discounted rewards? \\n\n",
        "\\t value near-term reward smore than rewards later in the future\n",
        "\\t economic rewards are more valuable now than later\n",
        "\\t rewards may never arrive the longer you wait \n",
        "\\t if you prefer one future to another starting tomorrow, you should still prefer that \n",
        "\\t future today so you need additive discounting for that\n",
        "\\t removes infinities \\n\n",
        "\n",
        "The optimal policy is the argmax_a Q(s,a) \\n\n",
        "If we represent MDPs with a table, the table will be sparse. Use DDNs: \\n\n",
        "\\t set of state features\n",
        "\\t set of possible actions\n",
        "\\t 2-stage decision network with chance nodes for each feature (at time 0 and time 1)\n",
        "\\t decision node for action taken\n",
        "\n",
        "\"\"\"\n",
        "chapter17_2 =  \"\"\"\n",
        "Offline Algorithms for solving MDPs:\n",
        "\n",
        "<b>Value Iteration</b>: start with random initial utility values and keep updating until equilibrium \\n\n",
        "\\t update step is called Bellman update\n",
        "\\t apply update at same time to all states\n",
        "\\t exponential time O(S^2 A) to converge to equilibrium \\n\n",
        "<b>Policy Iteration</b>: alternate between policy eval and policy improvement \\n\n",
        "\\t Policy Eval: given a policy, calc the utility of each state if we execute policy. \n",
        "\\t O(S^2) per iteration\n",
        "\\t Policy Improvement: calculate a new MEU policy based on utilities. it is optimal\n",
        "\\t terminates when policy improvement causes no change in utilities \\n\n",
        "\n",
        "What insight leads from value iteration to policy iteration? \\n\n",
        "\\t We can get an optimal policy with an inaccurate utility function for value iteration \\n\n",
        "\n",
        "How does the Bellman equation help us leverage dynamic programming? \\n\n",
        "\\t Bellman equation lets us express the utility of a state recursively as utilities of \n",
        "\\t its neighbors \\n\n",
        "\n",
        "Small state spaces: policy eval is the most efficient \\n\n",
        "Large state spaces: do modified policy iteration \\n\n",
        "\n",
        "asynchronous policy iteration: \\n\n",
        "\\t always converges to optimal policy\n",
        "\\t can design more efficient heuristic algorithms \\n\n",
        "\n",
        "linear programming: \\n\n",
        "\\t Utility of each state (U(s)) is a variable\n",
        "\\t minimize U(s) for each state where U(s) >= sum of neighboring state utilities\n",
        "\\t not as efficient as using DP for solving MDPs \\n\n",
        "\n",
        "Real-time dynamic programming: \\n\n",
        "\\t set a bound on error in utilities using an expectimax tree\n",
        "\\t find depth in tree where sum of rewards below this depth is less than error bound\n",
        "\\t this depth is how we can get close to optimal decisions\n",
        "\\t if large branching factor, take avg of samples of outcomes from action to approx\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" \n",
        "What is the difference between the utility function and performance measure of an agent? \\n\n",
        "\\t performance measure gives a score for a history\n",
        "\\t utility function applies to the very next state; it can guide future actions \\n\n",
        "Q-Function = action-utility function \\n\n",
        "If we assume stationary preferences, we can only define utilities as additive or discounted \\n\n",
        "To avoid infinite utilities: \\n\n",
        "\\t finite horizon, discounting, absorbing state (guarantee we reach terminal state)\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any term in the textbook or lecture, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 25 words long.\n",
        "\n",
        "module8_definitions = {\n",
        "\"utility function\" : \"desirability of a state -- a number\",\n",
        "\"expected utility\" : \"average utility of all possible outcomes of an action, weighted by their probability\",\n",
        "\"maximum expected utility (MEU)\": \"agent picks action with max exp. utility\",\n",
        "\"lottery\": \"set of outcomes for each action\",\n",
        "\"ordinal utility/value function\": \"if deterministic, agent only needs ranking of states, not actual values\",\n",
        "\"preference elicitation\": \"give humans choices and observe preferences to form utility function\",\n",
        "\"normalized utilities\": \"scale of 0 to 1\",\n",
        "\"standard lottery\": \"[p, U_min; 1-p, U_max]\",\n",
        "\"transition model\": \"outcome of each action from every state. transitions are Markovian\",\n",
        "\"Markovian\": \"when we don't care about history -- probability of s' from s only depends on s\",\n",
        "\"environment history\": \"sequence of states and actions\",\n",
        "\"policy\": \"specifies what agent should do for any state it reaches\",\n",
        "\"optimal policy (π*)\": \"gives us highest expected utility\",\n",
        "\"finite horizon\": \"after a fixed time, the game is over. this leads to nonstationary policies\",\n",
        "\"infinite horizon\": \"no fixed deadline, so optimal action based on current state. this leads to stationary policies\",\n",
        "\"additive discounted rewards\": \"utility of a history is sum of all previous rewards R0 + discount*R1 + discount^2*R2...\",\n",
        "\"discount factor\": \"between 0 and 1\",\n",
        "\"additive rewards\": \"when discount factor = 1\",\n",
        "\"proper policy\": \"guaranteed to reach a terminal state eventually. can use discount = 1\",\n",
        "\"average reward\": \"can be used to compare infinite sequences. take avg. reward at each time step\",\n",
        "\"Bellman equations\": \"give us the utilities for states based on exp. utility of future state sequences\",\n",
        "\"Q-function Q(s,a)\": \"expected utility of taking action a in state s. find the max Q(s,a) to get utility of s\",\n",
        "\"potential\": \"(discount factor * potential_s') - potential_s <-- this is the gradient of potential\",\n",
        "\"shaping theorem\": \"all policies are optimal for any Reward = (discount factor * potential_s') - potential_s\",\n",
        "\"dynamic decision networks (DDns)\": \"factored representations -- good for modeling large state space problems\",\n",
        "\"policy loss\": \"this most utility an agent can lose by executing a policy instead of optimal policy\",\n",
        "\"Modified policy iteration\": \"utility of state in next policy is the sum of utilities of neighboring states\",\n",
        "\"asynchronous policy iteration\": \"apply policy improvement/value iteration to a subset of states at each step\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a1fb1c6c-2751-4dd8-c708-7e2f30587dcb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory: choose among actiins based on desirability of their immediate outcomes (episodic) \n\nWhy doesn't MEU solve the AI problem? \n\n\t MEU formalizes what an agent should do but doesn't operationalize it. \n\t To use MEU, we have to estimate probability distribution and utility function \n\t which reflects perf. measure. \n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nMEU is not the only rational way to make decisions. \n\nA ≻ B: prefer A over B \n\nA ~ B: indifferent between A and B \n\nA ≻~ B: prefers A over B or is indifferent between them \n\n\nL = [p1, S1; p2, S2;...pn,Sn] || probabilities, outcomes \n\n\nAxioms of Utility Theory -- if these violated, irrational behavior \n\n<b>Orderability:</b> agent can't avoid deciding. so exactly 1 of 3 above principles holds \n\n\t Given two lotteries, a rational agent must either prefer one or be indifferent \n\n<b>Transitivity:</b> A ≻ B and B ≻ C --> A ≻ C \n\n<b>Continuity:</b> A ≻ B ≻ C, then there is a probability p where agent is indifferent between \n\nlottery for A and C and sure chance of getting B. [p, A; 1-p, C] ~ B \n\n<b>Substitutability:</b> if agent indifferent between 2 lotteries (A and B), agent is indifferent between: \n\n[p, A; 1-p, C] ~ [p,B;1-p,C] \n\n<b>Monotonicity:</b> if A ≻ B, agent prefers lottery with higher probability for A: \n\n[p, A; 1-p, B] ≻ [q,A;1-q,B] (p>q) \n\n<b>Decomposability:</b> we can reduce compound lotteries: \n\n[p, A; 1-p, [q,B;1-q,C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C] \n\n\nConsequences of Axioms \n\n<b>Existence of Utility function</b>: U(A) > U(B) if and only if A ≻ B. \n\nU(A) = U(B) if and only if A ~ B. \n\n<b>Expected Utility of a Lottery</b>: sum of probability of each outcome * utility of outcome \n\n\nJust because there is a utility function, doesn't mean agent is necessarily maximizing it\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nIf we normalize the utilities, we can see what probablity (p) to assign to the min utility \n \nand (1-p) to max utility so that p equals the value of the outcome we're looking at. \n\nTo find the value that people place on their lives: micromort, QALY \n\nMoney has a monotonic preference (always prefer more). Utility function is NOT monotonic \n(i.e. many people would turn down a gamble for more money compared to get less money for sure ) \n\nRisk-averse agents have a concave down utility curve. Risk-neutral have linear curve. \n\n\nAllias paradox: \n\nDescriptive theory shows a different way of people choosing between 2 options to get money than normative theory. \n\nThis could be because of the certainty effect -- people want the upside that they are guaranteed of rather \n\nthan a higher one that they have a chance, not for sure, of getting \n\nEllsberg paradox: \n\n\t people have ambiguity aversion -- they would rather go with a known chance than \n\t a chance that is unknown \n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nMarkov Decision Process (MDP): a sequential decision problem for a fully observable, stochastic environment with \n\na Markovian transition model and additive rewards.\n\t has: set of states, actions, transition model, reward function, initial state || terminal state is optional\n\t the solution is a policy - there can be multiple optimal policies.\n\t even if same policy executed muliple times, could get different state/action sequence\n\t can solve using DP \n\n\nIf we use discounted utilities w/ infinite horizons, optimal policy is independent of starting state \n\n\nWhy do we use additive discounted rewards? \n\n\t value near-term reward smore than rewards later in the future\n\t economic rewards are more valuable now than later\n\t rewards may never arrive the longer you wait \n\t if you prefer one future to another starting tomorrow, you should still prefer that \n\t future today so you need additive discounting for that\n\t removes infinities \n\n\nThe optimal policy is the argmax_a Q(s,a) \n\nIf we represent MDPs with a table, the table will be sparse. Use DDNs: \n\n\t set of state features\n\t set of possible actions\n\t 2-stage decision network with chance nodes for each feature (at time 0 and time 1)\n\t decision node for action taken\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nOffline Algorithms for solving MDPs:\n\n<b>Value Iteration</b>: start with random initial utility values and keep updating until equilibrium \n\n\t update step is called Bellman update\n\t apply update at same time to all states\n\t exponential time O(S^2 A) to converge to equilibrium \n\n<b>Policy Iteration</b>: alternate between policy eval and policy improvement \n\n\t Policy Eval: given a policy, calc the utility of each state if we execute policy. \n\t O(S^2) per iteration\n\t Policy Improvement: calculate a new MEU policy based on utilities. it is optimal\n\t terminates when policy improvement causes no change in utilities \n\n\nWhat insight leads from value iteration to policy iteration? \n\n\t We can get an optimal policy with an inaccurate utility function for value iteration \n\n\nHow does the Bellman equation help us leverage dynamic programming? \n\n\t Bellman equation lets us express the utility of a state recursively as utilities of \n\t its neighbors \n\n\nSmall state spaces: policy eval is the most efficient \n\nLarge state spaces: do modified policy iteration \n\n\nasynchronous policy iteration: \n\n\t always converges to optimal policy\n\t can design more efficient heuristic algorithms \n\n\nlinear programming: \n\n\t Utility of each state (U(s)) is a variable\n\t minimize U(s) for each state where U(s) >= sum of neighboring state utilities\n\t not as efficient as using DP for solving MDPs \n\n\nReal-time dynamic programming: \n\n\t set a bound on error in utilities using an expectimax tree\n\t find depth in tree where sum of rewards below this depth is less than error bound\n\t this depth is how we can get close to optimal decisions\n\t if large branching factor, take avg of samples of outcomes from action to approx\n\n\n## Module 8 Lecture Notes\n \nWhat is the difference between the utility function and performance measure of an agent? \n\n\t performance measure gives a score for a history\n\t utility function applies to the very next state; it can guide future actions \n\nQ-Function = action-utility function \n\nIf we assume stationary preferences, we can only define utilities as additive or discounted \n\nTo avoid infinite utilities: \n\n\t finite horizon, discounting, absorbing state (guarantee we reach terminal state)\n\n \n\n## Module 8 Definitions\n* **Utility function** - desirability of a state -- a number\n* **Expected utility** - average utility of all possible outcomes of an action, weighted by their probability\n* **Maximum expected utility (meu)** - agent picks action with max exp. utility\n* **Lottery** - set of outcomes for each action\n* **Ordinal utility/value function** - if deterministic, agent only needs ranking of states, not actual values\n* **Preference elicitation** - give humans choices and observe preferences to form utility function\n* **Normalized utilities** - scale of 0 to 1\n* **Standard lottery** - [p, U_min; 1-p, U_max]\n* **Transition model** - outcome of each action from every state. transitions are Markovian\n* **Markovian** - when we don't care about history -- probability of s' from s only depends on s\n* **Environment history** - sequence of states and actions\n* **Policy** - specifies what agent should do for any state it reaches\n* **Optimal policy (π*)** - gives us highest expected utility\n* **Finite horizon** - after a fixed time, the game is over. this leads to nonstationary policies\n* **Infinite horizon** - no fixed deadline, so optimal action based on current state. this leads to stationary policies\n* **Additive discounted rewards** - utility of a history is sum of all previous rewards R0 + discount*R1 + discount^2*R2...\n* **Discount factor** - between 0 and 1\n* **Additive rewards** - when discount factor = 1\n* **Proper policy** - guaranteed to reach a terminal state eventually. can use discount = 1\n* **Average reward** - can be used to compare infinite sequences. take avg. reward at each time step\n* **Bellman equations** - give us the utilities for states based on exp. utility of future state sequences\n* **Q-function q(s,a)** - expected utility of taking action a in state s. find the max Q(s,a) to get utility of s\n* **Potential** - (discount factor * potential_s') - potential_s <-- this is the gradient of potential\n* **Shaping theorem** - all policies are optimal for any Reward = (discount factor * potential_s') - potential_s\n* **Dynamic decision networks (ddns)** - factored representations -- good for modeling large state space problems\n* **Policy loss** - this most utility an agent can lose by executing a policy instead of optimal policy\n* **Modified policy iteration** - utility of state in next policy is the sum of utilities of neighboring states\n* **Asynchronous policy iteration** - apply policy improvement/value iteration to a subset of states at each step\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 =  \"\"\" Markov reward process is an MDP but only 1 possible action. \n",
        "Each bandit problem has multiple arms. Each arm is independent and is a MRP.\n",
        "\n",
        "One-armed bandit -- idea is that 1 arm gives different rewards and another gives constant. \\n\n",
        "\\t have to decide when you want to switch to the constant rewards (if ever) \\n\n",
        "\n",
        "Bernoulli bandit -- each arm gives either 0 or 1 rewards with a fixed but unknown probability \\n\n",
        "Bandit policies \\n\n",
        "\\t upper confidence bound heuristic: get a confidence interval for the value of each arm. choose arm with highest\n",
        "\\t upper bound on CI \n",
        "\\t Thompson sampling: choose arm randomly based on probability that arm is optimal given samples so far \\n\n",
        "\n",
        "For a BSP, the optimal policy may have actions that are suboptimal for some of the arms. Unless discount factor \\n\n",
        "is 1 (no cost for delaying rewards to any MDP), this will happen \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Reinforcement learning vs MDPs: \\n\n",
        "\\t in RL, agent is not given the MDP; it is in the MDP. \n",
        "\\t in RL, agent doesn't know transition model, rewards\n",
        "\\t in both, the values for the transition model are not known in advance \n",
        "\\t MDPs are offline learning but RL is online learning\"\"\"\n",
        "\n",
        "chapter22_2 =  \"\"\" Policy evaluation vs Passive RL: \\n\n",
        "\\t Passive RL agent doesn't know transition model&reward function, but policy eval does \\n\n",
        "\n",
        "<b>Direct utility estimation:</b> \n",
        "\\t compute values for each state under the policy by averaging the sum of discounted rewards that occur each time state visited\n",
        "\\t ignores the connections between states, so misses opps. for learning\n",
        "\\t converges very slowly \\n\n",
        "\n",
        "<b>Adaptive Dynamic Programming:</b> takes the transition model and observed rewards and calculates utility of each state \\n\n",
        "\\t use heuristics (i.e. prioritized sweeping) to improve speed \n",
        "\\t builds on direct utility estimation to use the Bellman equations \\n\n",
        "\n",
        "<b>Temporal Difference Learning:</b> use transitions that have been observed to adjust utilities of observed states \\n\n",
        "\\t model-free way to do policy eval\n",
        "\\t U*(s) = U(s) + learningRate*[Reward + discountRate*U(s') - U(s)]\n",
        "\\t this is adjusting the utility estimates to an equilibrium\n",
        "\\t **NO NEED for transition model** \n",
        "\\t learns utilities, but not q-values, so hard to turn into a new policy\n",
        "\\t slower than ADP&higher variability, but simpler&less computation per observation\n",
        "\\t ADP adjusts state to agree with <b>all</b> successors\n",
        "\\t TD adjusts state to agree with <b>observed</b> successor \"\"\"\n",
        "\n",
        "chapter22_3 =  \"\"\" Active RL: \\n\n",
        "agent learns full transition model, not just model associated with fixed policy (passive RL).\n",
        "next, agent decides action based on utility function using Bellman equations \\n\n",
        "\n",
        "\n",
        "What is wrong with greedy agents? \\n\n",
        "\\t learned model!=true environment so what is optimal in model might be suboptimal in env\n",
        "\\t need to trade-off between exploitation and exploration\n",
        "\\t use GLIE to try each action in each state unlimited times to ensure optimal action \\n\n",
        "\n",
        "GLIE: \\n\n",
        "\\t give more utility to more unexplored state-action pairs \\n\n",
        "\n",
        "Three approaches to find a reasonably accurate true model: \\n\n",
        "\\t Bayesian RL\n",
        "\\t Robust control theory: get worst possible result for any action&find which action has best one\n",
        "\\t problem: very conservative behavior\n",
        "\\t Use human knowledge to determine constraints and enforce them \\n\n",
        "\n",
        "TD Q-Learning: \\n\n",
        "\\t doesn't need a transition model and P(s'|s,a) \\n\n",
        "\n",
        "Q-Learning vs SARSA: \\n\n",
        "\\t Q-learning gets Q-value from the best action in s' but SARSA lets action happen \n",
        "\\t and then backs up Q-value for that action\n",
        "\\t if agent always picks best Q-value action, then Q-Learning = SARSA\n",
        "\\t Q-Learning: off-policy. SARSA: on-policy\n",
        "\\t Q-learning can learn optimal Q-function Q w/o ever executing optimal policy\n",
        "\\t Q-learning more flexible, SARSA better if policy has other agents involved\n",
        "\\t both learn optimal policy but slower than ADP \"\"\"\n",
        "\n",
        "chapter22_4 =  \"\"\" \n",
        "Utility = weights*features. RL approximates these weights in function approximation. \\n\n",
        "Function approx allows us to represent utility/Q for large state spaces + inductive generalization \\n\n",
        "\\t inductive generalization: agent can generalize from visited to unvisited states\n",
        "\\t FA generalizes by changing utilities for all states based on each \n",
        "\\t observed transition between states \\n\n",
        "Direct utility estimation: for each state, extracts sum of rewards from state until termination \\n\n",
        "Can apply Widrow-Hoff Rule (gradient descent) to DEU, TD Learning, Q-Learning \\n\n",
        "\n",
        "Catastrophic forgetting: car learns how to stay in middle of the road perfectly but then abruptly \\n\n",
        "veers off the side. Use experience replay to apply Q-learning to samples of the experience. \\n\n",
        "\n",
        "Fully observable state -- learning the model is supervised problem \\n\n",
        "Partially observable state -- Bayesian networks, NN, etc \\n\n",
        "\n",
        "Use Deep NN because you may not be able to come up with all features yourself/linear approx isn't good enough \\n\n",
        "\\t obstacles: difficult to get good performance, unpredictable with variance in test/train data \\n\n",
        "\n",
        "Reward shaping helps us deal with sparse rewards and speeds up learning but have to be careful of not maximizing \\n\n",
        "pseudorewards instead of rewards. \\n\n",
        "\n",
        "Hierarchical RL: start with partial problem that outlines structure of agent's behavior. \\n\n",
        "By associating a function with each choice, program learns function to decide which choice. \\n\n",
        "\"\"\"\n",
        "chapter22_5 =  \"\"\"\n",
        "Q-learning vs policy search: \\n\n",
        "\\t Q-learning algo finds param value that is close to Q* \n",
        "\\t policy search finds param value that gets good performance \\n\n",
        "\n",
        "Policy search uses stochastic policy representation (prob. of selecting action from state) \\n\n",
        "so that small change in param value doesn't change the action taken. We can use <b>softmax</b> \\n\n",
        "to get probabilities. \\n\n",
        "\"\"\"\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "MDP: \\n\n",
        "\\t A set of states, Initial states, Terminal states, Transition Model, Reward function \\n\n",
        "Model-Free Learning: \\n\n",
        "\\t no transition model. at each action, compare actual vs expected outcome. \n",
        "\\t so we track utility and nothing else \\n\n",
        "We can force exploration by assigning low prob to acting randomly and high prob to acting on current policy \\n\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"exploitation\": \"use the best action that has been found so far\",\n",
        "\"exploration\": \"get more information by looking at unknown states/actions. could lead to higher rewards\",\n",
        "\"regret\": \"difference between achieved rewards and optimal rewards. relative goodness of exploration procedures\",\n",
        "\"bandit problems\": \"has index function. overall are an MDP\",\n",
        "\"one-armed bandit\": \"1 arm produces different rewards each time. another gives the same reward each time. So pulling the first arm--you give up reward on other arm\",\n",
        "\"stopping time\": \"when you stopped pulling the arm\",\n",
        "\"Gittins index\": \"equation defining the value for the arm that gives same reward each time (lambda)\",\n",
        "\"selection problem\": \"*no index function*. don't have to minimize test failures. focus on getting a good decision ASAP\",\n",
        "\"bandit superprocess (BSP)\": \"each arm is a MDP instead of just a MRP. i.e. multitasking\",\n",
        "\"opportunity cost\": \"how much utility is given up by not devoting that amount of time to another arm\",\n",
        "\"dominating policy\": \"policy where an arm's optimal policy is not affected by opportunity cost\",\n",
        "\"reinforcements\": \"rewards\",\n",
        "\"reinforcement learning\": \"through interactions with world, agent gets reinforcements based on how it is performing. want to maximize rewards\",\n",
        "\"sparse reward\": \"has little to no information. i.e. chess, racing\",\n",
        "\"intermediate reward\": \"can be calculated based on a point won, run scored, etc. i.e. tennis, cricket\",\n",
        "\"model-based RL\": \"uses a transition model to interpret rewards and act. model could be known or unknown. learn utility function\",\n",
        "\"model-free RL\": \"no transition model involved\",\n",
        "\"action-utility learning\": \"Q-learning. get the expected utility of taking an action\",\n",
        "\"Q-learning\": \"learn a Q function: Q(s,a). expected reward from state s onward if action a. find action with highest Q.\",\n",
        "\"policy search\": \"learn a policy mapping from states to actions. (aka reflex agent)\",\n",
        "\"passive RL\": \"fixed policy in fully observable environment. agent learns utilities of each state\",\n",
        "\"direct utility estimation\": \"expected reward from the current state and onward\",\n",
        "\"active RL\": \"agent themself decides the actions to take\",\n",
        "\"adaptive dynamic programming\": \"learns transition model and uses DP to solve MDPs\",\n",
        "\"prioritized sweeping heuristic\": \"adjust states that have <b>likely</b> successors that have just had large changes to their utilities\",\n",
        "\"greedy agent\": \"takes action that it currently thinks is optimal. not always the right choice\",\n",
        "\"GLIE\": \"Greedy in the limit of infinite exploration\",\n",
        "\"irreversible actions\": \"no set of actions can restore us to the state before the irreversible action\",\n",
        "\"absorbing state\": \"no action can cause a reward\",\n",
        "\"Bayesian RL\": \"prior: hypothesis of true model (h). P(h|e). e is the observations so far\",\n",
        "\"robust control theory\": \"H is possible models, no probabilities. Optimal robust policy: best outcome in worst case of H\",\n",
        "\"SARSA\": \"state, action, reward, state, action. Similar to Q-learning\",\n",
        "\"off-policy algorithm\": \"determines worth of action and assumes we stop using current policy\",\n",
        "\"on-policy algorithm\": \"determines worth of action and assumes we keep using current policy\",\n",
        "\"function approximation\": \"construct an approximation of true utility/Q function\",\n",
        "\"Widrow-Hoff/delta rule\": \"gradient descent for linear regression -- updates weights based on diff between target&output\",\n",
        "\"catastrophic forgetting\": \"neural network forgets previously learned info when it gets new info\",\n",
        "\"experience replay\": \"store agent's experiences at each timestep so they can be used in learning\",\n",
        "\"credit assignment\": \"problem of it being hard to measure action's influence on future rewards\",\n",
        "\"reward shaping\": \"add additional (pseudo) rewards for making progress, not just on actions\",\n",
        "\"hierarchical RL\": \"breaking down action sequences into smaller sequences to improve learning\",\n",
        "\"joint state space\": \"each state consists of physical state and machine state\",\n",
        "\"policy\": \"function mapping states to actions\",\n",
        "\"policy search\": \"finding policy performance until performance stops changing\",\n",
        "\"correlated sampling\": \"each program has the same options instead of doing random sampling\",\n",
        "\"online learning\": \"actually take actions in the real world\",\n",
        "\"contraction\": \"Part of the proof of convergence for the value iteration algorithm\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d2cd0406-25e0-450a-aaec-abc35cdd2021"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Markov reward process is an MDP but only 1 possible action. \nEach bandit problem has multiple arms. Each arm is independent and is a MRP.\n\nOne-armed bandit -- idea is that 1 arm gives different rewards and another gives constant. \n\n\t have to decide when you want to switch to the constant rewards (if ever) \n\n\nBernoulli bandit -- each arm gives either 0 or 1 rewards with a fixed but unknown probability \n\nBandit policies \n\n\t upper confidence bound heuristic: get a confidence interval for the value of each arm. choose arm with highest\n\t upper bound on CI \n\t Thompson sampling: choose arm randomly based on probability that arm is optimal given samples so far \n\n\nFor a BSP, the optimal policy may have actions that are suboptimal for some of the arms. Unless discount factor \n\nis 1 (no cost for delaying rewards to any MDP), this will happen \n\n## AIMA Chapter 22.1 Learning from Rewards\n Reinforcement learning vs MDPs: \n\n\t in RL, agent is not given the MDP; it is in the MDP. \n\t in RL, agent doesn't know transition model, rewards\n\t in both, the values for the transition model are not known in advance \n\t MDPs are offline learning but RL is online learning\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Policy evaluation vs Passive RL: \n\n\t Passive RL agent doesn't know transition model&reward function, but policy eval does \n\n\n<b>Direct utility estimation:</b> \n\t compute values for each state under the policy by averaging the sum of discounted rewards that occur each time state visited\n\t ignores the connections between states, so misses opps. for learning\n\t converges very slowly \n\n\n<b>Adaptive Dynamic Programming:</b> takes the transition model and observed rewards and calculates utility of each state \n\n\t use heuristics (i.e. prioritized sweeping) to improve speed \n\t builds on direct utility estimation to use the Bellman equations \n\n\n<b>Temporal Difference Learning:</b> use transitions that have been observed to adjust utilities of observed states \n\n\t model-free way to do policy eval\n\t U*(s) = U(s) + learningRate*[Reward + discountRate*U(s') - U(s)]\n\t this is adjusting the utility estimates to an equilibrium\n\t **NO NEED for transition model** \n\t learns utilities, but not q-values, so hard to turn into a new policy\n\t slower than ADP&higher variability, but simpler&less computation per observation\n\t ADP adjusts state to agree with <b>all</b> successors\n\t TD adjusts state to agree with <b>observed</b> successor \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Active RL: \n\nagent learns full transition model, not just model associated with fixed policy (passive RL).\nnext, agent decides action based on utility function using Bellman equations \n\n\n\nWhat is wrong with greedy agents? \n\n\t learned model!=true environment so what is optimal in model might be suboptimal in env\n\t need to trade-off between exploitation and exploration\n\t use GLIE to try each action in each state unlimited times to ensure optimal action \n\n\nGLIE: \n\n\t give more utility to more unexplored state-action pairs \n\n\nThree approaches to find a reasonably accurate true model: \n\n\t Bayesian RL\n\t Robust control theory: get worst possible result for any action&find which action has best one\n\t problem: very conservative behavior\n\t Use human knowledge to determine constraints and enforce them \n\n\nTD Q-Learning: \n\n\t doesn't need a transition model and P(s'|s,a) \n\n\nQ-Learning vs SARSA: \n\n\t Q-learning gets Q-value from the best action in s' but SARSA lets action happen \n\t and then backs up Q-value for that action\n\t if agent always picks best Q-value action, then Q-Learning = SARSA\n\t Q-Learning: off-policy. SARSA: on-policy\n\t Q-learning can learn optimal Q-function Q w/o ever executing optimal policy\n\t Q-learning more flexible, SARSA better if policy has other agents involved\n\t both learn optimal policy but slower than ADP \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \nUtility = weights*features. RL approximates these weights in function approximation. \n\nFunction approx allows us to represent utility/Q for large state spaces + inductive generalization \n\n\t inductive generalization: agent can generalize from visited to unvisited states\n\t FA generalizes by changing utilities for all states based on each \n\t observed transition between states \n\nDirect utility estimation: for each state, extracts sum of rewards from state until termination \n\nCan apply Widrow-Hoff Rule (gradient descent) to DEU, TD Learning, Q-Learning \n\n\nCatastrophic forgetting: car learns how to stay in middle of the road perfectly but then abruptly \n\nveers off the side. Use experience replay to apply Q-learning to samples of the experience. \n\n\nFully observable state -- learning the model is supervised problem \n\nPartially observable state -- Bayesian networks, NN, etc \n\n\nUse Deep NN because you may not be able to come up with all features yourself/linear approx isn't good enough \n\n\t obstacles: difficult to get good performance, unpredictable with variance in test/train data \n\n\nReward shaping helps us deal with sparse rewards and speeds up learning but have to be careful of not maximizing \n\npseudorewards instead of rewards. \n\n\nHierarchical RL: start with partial problem that outlines structure of agent's behavior. \n\nBy associating a function with each choice, program learns function to decide which choice. \n\n\n\n## Module 9 Lecture Notes\n \nMDP: \n\n\t A set of states, Initial states, Terminal states, Transition Model, Reward function \n\nModel-Free Learning: \n\n\t no transition model. at each action, compare actual vs expected outcome. \n\t so we track utility and nothing else \n\nWe can force exploration by assigning low prob to acting randomly and high prob to acting on current policy \n\n\n\n## Module 9 Definitions\n* **Exploitation** - use the best action that has been found so far\n* **Exploration** - get more information by looking at unknown states/actions. could lead to higher rewards\n* **Regret** - difference between achieved rewards and optimal rewards. relative goodness of exploration procedures\n* **Bandit problems** - has index function. overall are an MDP\n* **One-armed bandit** - 1 arm produces different rewards each time. another gives the same reward each time. So pulling the first arm--you give up reward on other arm\n* **Stopping time** - when you stopped pulling the arm\n* **Gittins index** - equation defining the value for the arm that gives same reward each time (lambda)\n* **Selection problem** - *no index function*. don't have to minimize test failures. focus on getting a good decision ASAP\n* **Bandit superprocess (bsp)** - each arm is a MDP instead of just a MRP. i.e. multitasking\n* **Opportunity cost** - how much utility is given up by not devoting that amount of time to another arm\n* **Dominating policy** - policy where an arm's optimal policy is not affected by opportunity cost\n* **Reinforcements** - rewards\n* **Reinforcement learning** - through interactions with world, agent gets reinforcements based on how it is performing. want to maximize rewards\n* **Sparse reward** - has little to no information. i.e. chess, racing\n* **Intermediate reward** - can be calculated based on a point won, run scored, etc. i.e. tennis, cricket\n* **Model-based rl** - uses a transition model to interpret rewards and act. model could be known or unknown. learn utility function\n* **Model-free rl** - no transition model involved\n* **Action-utility learning** - Q-learning. get the expected utility of taking an action\n* **Q-learning** - learn a Q function: Q(s,a). expected reward from state s onward if action a. find action with highest Q.\n* **Policy search** - finding policy performance until performance stops changing\n* **Passive rl** - fixed policy in fully observable environment. agent learns utilities of each state\n* **Direct utility estimation** - expected reward from the current state and onward\n* **Active rl** - agent themself decides the actions to take\n* **Adaptive dynamic programming** - learns transition model and uses DP to solve MDPs\n* **Prioritized sweeping heuristic** - adjust states that have <b>likely</b> successors that have just had large changes to their utilities\n* **Greedy agent** - takes action that it currently thinks is optimal. not always the right choice\n* **Glie** - Greedy in the limit of infinite exploration\n* **Irreversible actions** - no set of actions can restore us to the state before the irreversible action\n* **Absorbing state** - no action can cause a reward\n* **Bayesian rl** - prior: hypothesis of true model (h). P(h|e). e is the observations so far\n* **Robust control theory** - H is possible models, no probabilities. Optimal robust policy: best outcome in worst case of H\n* **Sarsa** - state, action, reward, state, action. Similar to Q-learning\n* **Off-policy algorithm** - determines worth of action and assumes we stop using current policy\n* **On-policy algorithm** - determines worth of action and assumes we keep using current policy\n* **Function approximation** - construct an approximation of true utility/Q function\n* **Widrow-hoff/delta rule** - gradient descent for linear regression -- updates weights based on diff between target&output\n* **Catastrophic forgetting** - neural network forgets previously learned info when it gets new info\n* **Experience replay** - store agent's experiences at each timestep so they can be used in learning\n* **Credit assignment** - problem of it being hard to measure action's influence on future rewards\n* **Reward shaping** - add additional (pseudo) rewards for making progress, not just on actions\n* **Hierarchical rl** - breaking down action sequences into smaller sequences to improve learning\n* **Joint state space** - each state consists of physical state and machine state\n* **Policy** - function mapping states to actions\n* **Correlated sampling** - each program has the same options instead of doing random sampling\n* **Online learning** - actually take actions in the real world\n* **Contraction** - Part of the proof of convergence for the value iteration algorithm\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 = \"\"\"Hard to use only logic because: \\n\n",
        "\\t laziness (too hard to use so many rules)\n",
        "\\t theoretical ignorance (there will never be a complete set)\n",
        "\\t practice ignorance (could be uncertain about a rule) \\n\n",
        "Therefore, agent can only provide a *degree* of belief \\n\n",
        "\n",
        "Theory of probability: way to summarize uncertainty from ignorance and laziness \\n\n",
        "Utility of a state is relative to an agent \\n\n",
        "Decision theory says agent is only rational if it chooses action with highest exp. utility \\n\n",
        "\"\"\"\n",
        "chapter12_2 = \"\"\" \n",
        "Set of possible worlds is mutually exclusive and exhaustive \\n\n",
        "\\t P(a|b) = P(a and b)/P(b) \\n\n",
        "\\t Product rule: P(a and b) = P(a|b) * P(b) \n",
        "\\t Chain rule: P(a,b,c) = P(a)P(b|a) P(c|a,b) \n",
        "\\t chain rule: N! ways to apply it to N boolean variables \\n\n",
        "\n",
        "<b>inclusion-exclusion principle:</b> \\n\n",
        "\\t P(a or b) = P(a) + P(b) - P(a and b)\n",
        " \"\"\"\n",
        "chapter12_3 = \"\"\"\n",
        "Full joint distr. tables are rarely used because domains usually too big\n",
        " \"\"\"\n",
        "chapter12_4 = \"\"\"\n",
        "<b>Independence:</b> \\n\n",
        "\\t P(X|Y) = P(X) ; P(Y|X) = P(Y) ; P(X,Y) = P(X)P(Y)\n",
        "\\t ind. assertions can reduce the size of domain and complexity of inference problem\n",
        "\\t size of representation grows O(2^n)\n",
        " \"\"\"\n",
        "chapter12_5 = \"\"\"\n",
        "<b>Bayes Rule</b>: P(Y|X) = P(X|Y)P(Y) / P(X) \\n\n",
        "\\t LHS is diagnostic direction, RHS is causal direction\n",
        "\\t can add normalization constant in numerator to make entries on LHS sum to 1\n",
        "\\t diagnostic knowledge is more fragile than causal knowledge \\n\n",
        "<b>Conditional Independence</b>: \\n\n",
        "\\t P(X,Y|Z) = P(X|Z)P(Y|Z)\n",
        "\\t P(X|Y,Z) = P(X|Z) and P(Y|X,Z) = P(Y|Z)\n",
        "\\t cond. indp. can allow prob. systems to scale up\n",
        "\\t they are more available than absolute indp. assertions\n",
        "\\t size of rep grows O(n)\n",
        " \"\"\"\n",
        "chapter12_6 = \"\"\"\n",
        "<b>Naive Bayes</b>: assumes input variables are independent \\n\n",
        "\\t text classification; take proportion of documents that word is in\n",
        "\\t not good to use for problems where posterior prob. accuracy matters (medical)\n",
        "\"\"\"\n",
        "chapter12_7 = \"\"\"\n",
        "\"\"\"\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 = \"\"\"\n",
        "Use ngrams to approximate the history instead of using the entire history \\n\n",
        "ngram: only the previous n-1 words are the history \\n\n",
        "\\t markov assumption: prob of word is dependent only on some # of previous words \\n\n",
        "To estimate probabilities, use MLE: \\n\n",
        "\\t compute count of bigram -- numerator\n",
        "\\t compute total number of times history occurred -- normalization (denominator) \n",
        "\\t relative frequency: numerator/denominator \n",
        "\\t problems: zeros, out of vocab words \n",
        " \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" \n",
        "80% train, 10% development, 10% test \\n\n",
        "Can only compare perplexities of models if they use identical vocabularies \\n\n",
        "Intrinsic perplexity improvement doesn't guarantee extrinsic improvement in performance \\n\n",
        "\"\"\"\n",
        "SLP_chapter3_3 = \"\"\" \n",
        "Sampling from a language model: \\n\n",
        "\\t generate sentences based on likelihood defined by model\n",
        "\\t this way, we get sentences with higher prob based on model\n",
        "\\t allows us to visualize what kind of knowledge a language model has\n",
        "\"\"\"\n",
        "SLP_chapter3_4 = \"\"\"\n",
        "Implications of ngram models being dependent on training corpus: \\n\n",
        "\\t probabilities encode specific facts about training corpus\n",
        "\\t as N goes up, ngrams do better job of modeling training corpus \\n\n",
        "How to improve on pure statistical models for language modeling: \\n\n",
        "\\t genre: training corpus should have documents from same genre\n",
        "\\t dialect/variety: training corpus documents should have same dialect as task \\n\n",
        "\n",
        "Sparsity is usually another issue -- you get zero probabilities \\n\n",
        "\\t can turned an open vocab problem into closed vocab problem\n",
        "\\t replace unknown words with <UNK>\n",
        "\n",
        "\"\"\"\n",
        "SLP_chapter3_5 = \"\"\"\n",
        "What to do with words that are in vocab, but appear in test set with unseen context?: \\n\n",
        "\\t Laplace smoothing: add 1 to all ngram counts\n",
        "\\t add-k smoothing: instead of add 1, add k (fraction) to all ngram counts\n",
        "\\t add-k smoothing -- the k can be chosen using a development set\n",
        "\\t backoff: if don't have sufficient evidence w/ ngram, go to n-1 gram, etc until get some counts\n",
        "\\t interpolation: mix prob. estimates from all n, n-1, etc grams\n",
        "\\t interpolation -- add up lambda*estimate for each ngram \\n\n",
        "Katz backoff: when you backoff, discount the higher-order ngram counts \\n\n",
        "Discount ratio: smoothed count / unsmoothed count\n",
        " \"\"\"\n",
        "SLP_chapter3_7 = \"\"\"\n",
        "How to create efficient language models? \\n\n",
        "\\t Bloom filter: space-efficient data structure to test if element is in a set\n",
        "\\t pruning ngrams that have greater than a certain count\n",
        "\\t stupid backoff: don't discount the higher-order ngram counts\n",
        "\\t stupid backoff -- if higher order has zero count, just move on to n-1\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\"\n",
        "Size of joint prob distr with n variables, d domain size: d^n \\n\n",
        "Probabilistic Language Modeling: \\n\n",
        "\\t model that computes probability of sentence/seq of words/word \\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"belief state\" : \"representation of all possible states that agent can be in\",\n",
        "\"rational decision\": \"depends on 1) relative importance of goals and 2) likelihood of achieving them\",\n",
        "\"utility theory\": \"every state/sequence of states has a degree of usefulness to agent\",\n",
        "\"decision theory\": \"probability theory + utility theory\",\n",
        "\"MEU (maximum expected utility)\": \"choose action with highest exp.utility, avg over all possible outcomes\",\n",
        "\"prior probability\": \"P(event)\",\n",
        "\"conditional/posterior probability\": \"P(event|another event)\",\n",
        "\"Bernoulli\": \"outcome is binary\",\n",
        "\"probability distribution\": \"assign a prob to every possible value of a random variable\",\n",
        "\"categorical distribution\": \"finite, discrete range of values\",\n",
        "\"probability density function\": \"used with continuous variables\",\n",
        "\"joint probability distribution\": \"usually expressed using a table. all prob sum to 1\",\n",
        "\"probabilistic inference\": \"computing posterior probabilities\",\n",
        "\"marginal probability\": \"probability of an event occuring (sum an entire row/col in a joint prob table\",\n",
        "\"independence\": \"aka absolute independence and marginal independence\",\n",
        "\"syntactic\": \"relating to the use of language\",\n",
        "\"log probabilities\": \"used so we don't get small numbers, since probabilities between 0 and 1. take e^(sum of log probs)\",\n",
        "\"extrinsic evaluation\": \"apply a language model in an actual application and measure how the application improves\",\n",
        "\"intrinsic evaluation\": \"measures model quality using metrics, not an application\",\n",
        "\"perplexity\": \"measures performance of language model -- lower is better\",\n",
        "\"branching factor\": \"number of words that could follow a word\",\n",
        "\"weighted average branching factor\": \"aka perplexity, since you take a weighted average for each word\",\n",
        "\"closed vocabulary\": \"test set only contains words from a vocabulary\",\n",
        "\"open vocabulary\": \"test set can contain unknown words that aren't in vocabulary\",\n",
        "\"discounting\": \"lowering some non-zero counts to get the probability that will be assigned to zero counts\"\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "4b7adc3f-3649-4eab-9718-e033a6ac55d4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nHard to use only logic because: \n\n\t laziness (too hard to use so many rules)\n\t theoretical ignorance (there will never be a complete set)\n\t practice ignorance (could be uncertain about a rule) \n\nTherefore, agent can only provide a *degree* of belief \n\n\nTheory of probability: way to summarize uncertainty from ignorance and laziness \n\nUtility of a state is relative to an agent \n\nDecision theory says agent is only rational if it chooses action with highest exp. utility \n\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n \nSet of possible worlds is mutually exclusive and exhaustive \n\n\t P(a|b) = P(a and b)/P(b) \n\n\t Product rule: P(a and b) = P(a|b) * P(b) \n\t Chain rule: P(a,b,c) = P(a)P(b|a) P(c|a,b) \n\t chain rule: N! ways to apply it to N boolean variables \n\n\n<b>inclusion-exclusion principle:</b> \n\n\t P(a or b) = P(a) + P(b) - P(a and b)\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\nFull joint distr. tables are rarely used because domains usually too big\n \n\n## AIMA Chapter 12.4 Independence\n\n<b>Independence:</b> \n\n\t P(X|Y) = P(X) ; P(Y|X) = P(Y) ; P(X,Y) = P(X)P(Y)\n\t ind. assertions can reduce the size of domain and complexity of inference problem\n\t size of representation grows O(2^n)\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n<b>Bayes Rule</b>: P(Y|X) = P(X|Y)P(Y) / P(X) \n\n\t LHS is diagnostic direction, RHS is causal direction\n\t can add normalization constant in numerator to make entries on LHS sum to 1\n\t diagnostic knowledge is more fragile than causal knowledge \n\n<b>Conditional Independence</b>: \n\n\t P(X,Y|Z) = P(X|Z)P(Y|Z)\n\t P(X|Y,Z) = P(X|Z) and P(Y|X,Z) = P(Y|Z)\n\t cond. indp. can allow prob. systems to scale up\n\t they are more available than absolute indp. assertions\n\t size of rep grows O(n)\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n<b>Naive Bayes</b>: assumes input variables are independent \n\n\t text classification; take proportion of documents that word is in\n\t not good to use for problems where posterior prob. accuracy matters (medical)\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n\n## SLP Chapter 3.1 N-Grams\n\nUse ngrams to approximate the history instead of using the entire history \n\nngram: only the previous n-1 words are the history \n\n\t markov assumption: prob of word is dependent only on some # of previous words \n\nTo estimate probabilities, use MLE: \n\n\t compute count of bigram -- numerator\n\t compute total number of times history occurred -- normalization (denominator) \n\t relative frequency: numerator/denominator \n\t problems: zeros, out of vocab words \n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n80% train, 10% development, 10% test \n\nCan only compare perplexities of models if they use identical vocabularies \n\nIntrinsic perplexity improvement doesn't guarantee extrinsic improvement in performance \n\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n \nSampling from a language model: \n\n\t generate sentences based on likelihood defined by model\n\t this way, we get sentences with higher prob based on model\n\t allows us to visualize what kind of knowledge a language model has\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\nImplications of ngram models being dependent on training corpus: \n\n\t probabilities encode specific facts about training corpus\n\t as N goes up, ngrams do better job of modeling training corpus \n\nHow to improve on pure statistical models for language modeling: \n\n\t genre: training corpus should have documents from same genre\n\t dialect/variety: training corpus documents should have same dialect as task \n\n\nSparsity is usually another issue -- you get zero probabilities \n\n\t can turned an open vocab problem into closed vocab problem\n\t replace unknown words with <UNK>\n\n\n\n## SLP Chapter 3.5 Smoothing\n\nWhat to do with words that are in vocab, but appear in test set with unseen context?: \n\n\t Laplace smoothing: add 1 to all ngram counts\n\t add-k smoothing: instead of add 1, add k (fraction) to all ngram counts\n\t add-k smoothing -- the k can be chosen using a development set\n\t backoff: if don't have sufficient evidence w/ ngram, go to n-1 gram, etc until get some counts\n\t interpolation: mix prob. estimates from all n, n-1, etc grams\n\t interpolation -- add up lambda*estimate for each ngram \n\nKatz backoff: when you backoff, discount the higher-order ngram counts \n\nDiscount ratio: smoothed count / unsmoothed count\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\nHow to create efficient language models? \n\n\t Bloom filter: space-efficient data structure to test if element is in a set\n\t pruning ngrams that have greater than a certain count\n\t stupid backoff: don't discount the higher-order ngram counts\n\t stupid backoff -- if higher order has zero count, just move on to n-1\n\n\n## Module 10 Lecture Notes\n\nSize of joint prob distr with n variables, d domain size: d^n \n\nProbabilistic Language Modeling: \n\n\t model that computes probability of sentence/seq of words/word \n\n\n\n## Module 10 Definitions\n* **Belief state** - representation of all possible states that agent can be in\n* **Rational decision** - depends on 1) relative importance of goals and 2) likelihood of achieving them\n* **Utility theory** - every state/sequence of states has a degree of usefulness to agent\n* **Decision theory** - probability theory + utility theory\n* **Meu (maximum expected utility)** - choose action with highest exp.utility, avg over all possible outcomes\n* **Prior probability** - P(event)\n* **Conditional/posterior probability** - P(event|another event)\n* **Bernoulli** - outcome is binary\n* **Probability distribution** - assign a prob to every possible value of a random variable\n* **Categorical distribution** - finite, discrete range of values\n* **Probability density function** - used with continuous variables\n* **Joint probability distribution** - usually expressed using a table. all prob sum to 1\n* **Probabilistic inference** - computing posterior probabilities\n* **Marginal probability** - probability of an event occuring (sum an entire row/col in a joint prob table\n* **Independence** - aka absolute independence and marginal independence\n* **Syntactic** - relating to the use of language\n* **Log probabilities** - used so we don't get small numbers, since probabilities between 0 and 1. take e^(sum of log probs)\n* **Extrinsic evaluation** - apply a language model in an actual application and measure how the application improves\n* **Intrinsic evaluation** - measures model quality using metrics, not an application\n* **Perplexity** - measures performance of language model -- lower is better\n* **Branching factor** - number of words that could follow a word\n* **Weighted average branching factor** - aka perplexity, since you take a weighted average for each word\n* **Closed vocabulary** - test set only contains words from a vocabulary\n* **Open vocabulary** - test set can contain unknown words that aren't in vocabulary\n* **Discounting** - lowering some non-zero counts to get the probability that will be assigned to zero counts\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 = \"\"\"\n",
        "Bayesian Network: DAGs \\n\n",
        "\\t node: random variable\n",
        "\\t directed arrows: X -> Y means X is parent of Y\n",
        "\\t each node has P(X|Parents(X)) \\n\n",
        "\n",
        "<b>Conditional Probability Table (CPT):</b> only used for discrete variables \\n\n",
        "\\t local probability info attached to each node\n",
        "\\t **specified based on the probability distribution of JUST the parents\n",
        "\\t each row contains conditional probability of each conditioning case\n",
        "  \"\"\"\n",
        "chapter13_2 = \"\"\"\n",
        "syntax: DAG with local prob. info at each node \\n\n",
        "semantics: how the syntax corresponds to the joint distribution \\n\n",
        "chain rule: holds for any set of RVs \\n\n",
        "\\t P(x1...xN) = P(xN|xN-1...x1)*P(xN-1|xN-2...x1)...P(x2|x1)*P(x1) \\n\n",
        "\n",
        "Bayes network is correct representation of domain if each node is conditionally ind of predecessors: \\n\n",
        "\\t nodes: determine set of RV and then order them\n",
        "\\t links: chose a minimal set of parents for each node and insert a link. Write CPT \\n\n",
        "\n",
        "Bayes nets: always acyclic and always don't have redundant probability values \\n\n",
        "\\t definition: describes models using conditional probabilities\n",
        "\\t semantics: topology (graph) + local conditional probabilities for each node\n",
        "\\t more compact that full joint probability distr. because locally structured \n",
        "\\t use causal over diagnostic models to make the ordering better\n",
        "\\t size: if boolean variables: 2^N. if nodes have up to k parents: O(N*2^k+1) \\n\n",
        "\n",
        "Bayes nets don't HAVE to be causal; can have arrows represent correlation instead \\n\n",
        "\n",
        "D-separation: \\n\n",
        "\\t subgraph consists of X,Y,Z -- ancestral subgraph\n",
        "\\t add links between any nodes that share a common child -- moral graph\n",
        "\\t replace directed links with undirected links\n",
        "\\t if Z blocks all paths between X and Y, Z d-separates X and Y\n",
        "\\t this also means X is conditionally independent of Y given Z \\n\n",
        "A variable's Markov blanket d-separates it from all other variables. \\n\n",
        "\n",
        "Noisy logical relationships assumptions for the model: \\n\n",
        "\\t all possible causes are listed (if not, leak node)\n",
        "\\t inhibition of a parent is indp. of inhibitions of other parents to cause child node to be true\n",
        "\\t O(k) parameters instead of O(2^k) \\n\n",
        "\n",
        "Handling continuous variables: \\n\n",
        "\\t discretization: divide into fixed set of intervals\n",
        "\\t define using a standard prob. density function \\n\n",
        "  \"\"\"\n",
        "chapter13_3 = \"\"\" \n",
        "Query can be answered using a Bayes Net by summing the products of all the cond. prob. \\n\n",
        "\n",
        "Enumeration-Ask Algorithm: \\n\n",
        "\\t DFS, left to right recursion\n",
        "\\t space complexity: linear, time: O(2^n)\n",
        "\\t contains repeated subexpressions, which is wasteful \\n\n",
        "\n",
        "Variable Elimination Algorithm: \\n\n",
        "\\t expressions are evaluated right to left\n",
        "\\t removes variables that aren't ancestor of query or evidence variable\n",
        "\\t uses DP, so intermediate results are stored\n",
        "\\t factor for P(m|a) = vector with P(m|a) and P(m|¬a)\n",
        "\\t better than enumeration algo \\n\n",
        "\n",
        "Complexity of CSPs and Bayes nets are closely connected: \\n\n",
        "\\t tree width: bounds CSP complexity but is also applicable to Bayes \\n\n",
        "\n",
        "Clustering: \\n\n",
        "\\t put network into polytree form using clustering\n",
        "\\t use constraint propagation \n",
        "\\t neighboring nodes must agree on posterior probability of variables that are shared\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\"\n",
        "A ⫫ B means A and B are independent \\n\n",
        "A ⫫ B|C means that A and B are conditionally independent given C \\n\n",
        "D-Separation has 3 cases: causal chain, common cause, common effect \\n\n",
        "\\t to see if 2 variables are independent, check all undirected paths between them\n",
        "\\t A causal chain is inactive if not all tuples are active \n",
        "\\t if a node is observed, then it is active\n",
        "\\t if one or more paths is active, then independence not certain\n",
        "\\t if all paths are inactive, then independence is certain\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"conditioning case\" : \"possible combo of values for a the parent nodes of a node\",\n",
        "\"topological order\": \"order of DAG\",\n",
        "\"locally structured\": \"each subcomponent only interacts with a bounded number of components. Linear complexity growth\",\n",
        "\"Markov blanket\": \"parents, children, children's parents. a variable should be conditionally independent of all other nodes given this\",\n",
        "\"deterministic node\": \"value is specified exactly by the values of parents. no uncertainty\",\n",
        "\"context-specific independence\": \"variable is cond. indp. of SOME parents given CERTAIN VALUES of other parents\",\n",
        "\"noisy-OR relation\": \"generalize OR but allow uncertainty for each parent to cause child to be true\",\n",
        "\"leak node\": \"covers any other causes (parents) that might not be specified\",\n",
        "\"hybrid Bayesian network\": \"network with both discrete and continuous variables\",\n",
        "\"linear-Gaussian cond. distr.\": \"child-Gaussian distr. mean varies linearly with parent. SD is fixed\",\n",
        "\"conditional Gaussian\": \"discrete variables as parents of continuous variables\",\n",
        "\"hidden variables\": \"ensure network is sparse enough w/ manageable # of parameters. in between input and output\",\n",
        "\"factor\": \"matrix indexed by values of its argument variables\",\n",
        "\"pointwise product\": \"multiply 2 functions to get another function by multiplying their values at each part of domain\",\n",
        "\"polytrees/singly connected\": \"at most 1 undirected path in network. time and space complexity is linear\",\n",
        "\"multiply connected\": \">1 undirected paths. exponential time and space. \",\n",
        "\"clustering/join tree\": \"join nodes to form cluster nodes to create polytree\",\n",
        "\"meganode\": \"node resulting from a combo of nodes\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7b41b8b5-ebce-408c-80a6-f12e344f1461"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\nBayesian Network: DAGs \n\n\t node: random variable\n\t directed arrows: X -> Y means X is parent of Y\n\t each node has P(X|Parents(X)) \n\n\n<b>Conditional Probability Table (CPT):</b> only used for discrete variables \n\n\t local probability info attached to each node\n\t **specified based on the probability distribution of JUST the parents\n\t each row contains conditional probability of each conditioning case\n  \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nsyntax: DAG with local prob. info at each node \n\nsemantics: how the syntax corresponds to the joint distribution \n\nchain rule: holds for any set of RVs \n\n\t P(x1...xN) = P(xN|xN-1...x1)*P(xN-1|xN-2...x1)...P(x2|x1)*P(x1) \n\n\nBayes network is correct representation of domain if each node is conditionally ind of predecessors: \n\n\t nodes: determine set of RV and then order them\n\t links: chose a minimal set of parents for each node and insert a link. Write CPT \n\n\nBayes nets: always acyclic and always don't have redundant probability values \n\n\t definition: describes models using conditional probabilities\n\t semantics: topology (graph) + local conditional probabilities for each node\n\t more compact that full joint probability distr. because locally structured \n\t use causal over diagnostic models to make the ordering better\n\t size: if boolean variables: 2^N. if nodes have up to k parents: O(N*2^k+1) \n\n\nBayes nets don't HAVE to be causal; can have arrows represent correlation instead \n\n\nD-separation: \n\n\t subgraph consists of X,Y,Z -- ancestral subgraph\n\t add links between any nodes that share a common child -- moral graph\n\t replace directed links with undirected links\n\t if Z blocks all paths between X and Y, Z d-separates X and Y\n\t this also means X is conditionally independent of Y given Z \n\nA variable's Markov blanket d-separates it from all other variables. \n\n\nNoisy logical relationships assumptions for the model: \n\n\t all possible causes are listed (if not, leak node)\n\t inhibition of a parent is indp. of inhibitions of other parents to cause child node to be true\n\t O(k) parameters instead of O(2^k) \n\n\nHandling continuous variables: \n\n\t discretization: divide into fixed set of intervals\n\t define using a standard prob. density function \n\n  \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \nQuery can be answered using a Bayes Net by summing the products of all the cond. prob. \n\n\nEnumeration-Ask Algorithm: \n\n\t DFS, left to right recursion\n\t space complexity: linear, time: O(2^n)\n\t contains repeated subexpressions, which is wasteful \n\n\nVariable Elimination Algorithm: \n\n\t expressions are evaluated right to left\n\t removes variables that aren't ancestor of query or evidence variable\n\t uses DP, so intermediate results are stored\n\t factor for P(m|a) = vector with P(m|a) and P(m|¬a)\n\t better than enumeration algo \n\n\nComplexity of CSPs and Bayes nets are closely connected: \n\n\t tree width: bounds CSP complexity but is also applicable to Bayes \n\n\nClustering: \n\n\t put network into polytree form using clustering\n\t use constraint propagation \n\t neighboring nodes must agree on posterior probability of variables that are shared\n\n\n## Module 11 Lecture Notes\n\nA ⫫ B means A and B are independent \n\nA ⫫ B|C means that A and B are conditionally independent given C \n\nD-Separation has 3 cases: causal chain, common cause, common effect \n\n\t to see if 2 variables are independent, check all undirected paths between them\n\t A causal chain is inactive if not all tuples are active \n\t if a node is observed, then it is active\n\t if one or more paths is active, then independence not certain\n\t if all paths are inactive, then independence is certain\n\n\n## Module 11 Definitions\n* **Conditioning case** - possible combo of values for a the parent nodes of a node\n* **Topological order** - order of DAG\n* **Locally structured** - each subcomponent only interacts with a bounded number of components. Linear complexity growth\n* **Markov blanket** - parents, children, children's parents. a variable should be conditionally independent of all other nodes given this\n* **Deterministic node** - value is specified exactly by the values of parents. no uncertainty\n* **Context-specific independence** - variable is cond. indp. of SOME parents given CERTAIN VALUES of other parents\n* **Noisy-or relation** - generalize OR but allow uncertainty for each parent to cause child to be true\n* **Leak node** - covers any other causes (parents) that might not be specified\n* **Hybrid bayesian network** - network with both discrete and continuous variables\n* **Linear-gaussian cond. distr.** - child-Gaussian distr. mean varies linearly with parent. SD is fixed\n* **Conditional gaussian** - discrete variables as parents of continuous variables\n* **Hidden variables** - ensure network is sparse enough w/ manageable # of parameters. in between input and output\n* **Factor** - matrix indexed by values of its argument variables\n* **Pointwise product** - multiply 2 functions to get another function by multiplying their values at each part of domain\n* **Polytrees/singly connected** - at most 1 undirected path in network. time and space complexity is linear\n* **Multiply connected** - >1 undirected paths. exponential time and space. \n* **Clustering/join tree** - join nodes to form cluster nodes to create polytree\n* **Meganode** - node resulting from a combo of nodes\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 = \"\"\" \n",
        "Improving agents using ML depends on: \\n\n",
        "\\t which component to improve, prior knowledge of agent, data and feedback \\n\n",
        "\n",
        "Components of agents: \\n\n",
        "\\t direct mapping from conditions on current state to actions\n",
        "\\t ability to infer relevant properties of world from percept sequence\n",
        "\\t info about how world evolves + results of agent's actions\n",
        "\\t utility info about each state\n",
        "\\t action-value info\n",
        "\\t goals\n",
        "\\t problem generator, critic, and learning element to allow for improvement \\n\n",
        "\n",
        "3 types of learning: supervised, unsupervised, RL \n",
        "\"\"\"\n",
        "chapter19_2 = \"\"\"\n",
        "High bias: linear functions, any function very fitted to data \\n\n",
        "Low bias: piecewise linear function, decision trees, RF \\n\n",
        "High variance: very high degree polynomial, KNN, RF \\n\n",
        "Low variance: linear function \\n\n",
        "\n",
        "Why do we want simple hypothesis spaces: \\n\n",
        "\\t computational complexity too high with more complex\n",
        "\\t hard to replicate using a complex one \n",
        " \"\"\"\n",
        "chapter19_3 = \"\"\" \n",
        "Decision trees: \\n\n",
        "\\t split on attribute that makes the most difference in classification for an example\n",
        "\\t entropy: -ΣP(v)*log_2P*v) ; sum over each possible value of variable v \n",
        "\\t use pruning (remove nodes with low information gain) to combat overfitting \n",
        "\\t H_o: no underlying pattern. use statistical sig test to decide what to prune \\n\n",
        "We can make decision trees more useful by handling: \\n\n",
        "\\t missing data\n",
        "\\t continuous attr: use a split point (i.e. Weight > 160), IG Ratio, Equality test\n",
        "\\t continuous-valued output attr: use a regr. tree \\n\n",
        "Overall: \\n\n",
        "\\t easy to understand, scale to large datasets\n",
        "\\t versatile with discrete/cont variables + class/regr\n",
        "\\t can have suboptimal accuracy, unstable (adding 1 example can change everything) \\n\n",
        "\n",
        "Overfitting becomes more likely as we increase # of attributes, less likely as we increase # of data points \\n\n",
        "Problem with early stopping: can't recognize when we need a combo of attr. instead of 1 \\n\n",
        "\"\"\"\n",
        "chapter19_4 = \"\"\" \n",
        "Model selection starts with a small model which probably underfits and then iterates thru more complex models \\n\n",
        "\\t train error will decrease as complexity (# of tree nodes, # of params) increases\n",
        "\\t val/test set error will decrease for a while but increase when overfitting begins\n",
        "\\t want to minimze the loss function \\n\n",
        "Reasons the hypothesis differs from the real function: \\n\n",
        "\\t unrealizability, variance, noise, computational complexity\n",
        "\\t noise -- could return different values of f(x) for x\n",
        "\\t complexity -- if complex function, could be too much to search \\n\n",
        "Simplifying models: \\n\n",
        "\\t regularization, feature selection \\n\n",
        "\n",
        "population based training (PBT): \\n\n",
        "\\t uses random search to train models with dif hyperparam values\n",
        "\\t then next set of models is trained based on previous hyperparam values\n",
        " \"\"\"\n",
        "chapter19_5 = \"\"\"\n",
        "Approximately correct hypothesis: error is less than some E \\n\n",
        "\\t sample complexity: # of required examples \\n\n",
        "To obtain real generalization to unseen examples: \\n\n",
        "\\t bring prior knowledge for the problem\n",
        "\\t get algorithm to return a simple consistent hypothesis\n",
        "\\t focus on learnable subsets of hypothesis space \\n\n",
        "\n",
        "Decision lists: \\n\n",
        "\\t if test succeeds, decision list specifies value to return\n",
        "\\t if test fails, go to next test in list \n",
        "\\t simpler than decision tree because they only branch in 1 direction \n",
        "\\t but individual tests are more complex than decision trees \\n\n",
        " \"\"\"\n",
        "chapter19_6 = \"\"\"\n",
        "Gradient descent: finds the minimum of a function\\n\n",
        "\\t start at any point in weight space, compute estimate of gradient, \n",
        "\\t move in direction opposite to steepest slope\n",
        "\\t repeat until converged\n",
        "\\t weight = weight - alpha*derivative(Loss(w))\n",
        "\\t alpha: step size/learning rate \\n\n",
        "\n",
        "Batch gradient descent: \\n\n",
        "\\t gradient descent on all of the training data at once \\n\n",
        "\n",
        "Stochastic gradient descent: \\n\n",
        "\\t randomly sample 1 training example at each step and gradient descent on it\n",
        "\\t minibatch: randomly sample M training examples at each step\n",
        "\\t convergence of minibatch SGD not guaranteed\n",
        "\\t SGD useful for when data is coming in 1 at a time and isn't stationary \\n\n",
        "\n",
        "With univariate LR, no overfitting. But multivariate LR, you can have overfitting: \\n\n",
        "\\t use regularization -- L1 (sum of abs values), L2 (sum of squares)\n",
        "\\t L1 produces a sparse model (can set weights to 0) \\n\n",
        "\n",
        "Linear functions can be used for classification too: \\n\n",
        "\\t decision boundary will separate 2 classes (if linear, then linear separator) \\n\n",
        "Perceptron Learning Rule: \\n\n",
        "\\t if output correct, no change to weights\n",
        "\\t if y is 1 but correct is 0, increase weight when x is pos, decrease when x is neg\n",
        "\\t if y is 0 but correct is 1, decrease weight when x is pos, increase when x is neg\n",
        "\\t applied to 1 point in training set at a time \\n\n",
        "We can soften the threshold function using logistic function so that we can account for \\n\n",
        "some points not being exactly 0 or 1. We can use the L2 loss function here. If data is \\n\n",
        "linearly separable, log. regr. takes longer to converge than lin. regr., but more predictable. \\n\n",
        "If data noisy/nonseparable, log. regr. better.\n",
        " \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" \n",
        "Multinomial Naive Bayes: \\n\n",
        "\\t estimate of correct class = P(d|c)P(c)\n",
        "\\t dropped denominator: P(d); perform this for every class and get argmax\n",
        "\\t generative model\n",
        "\\t P(d|c): likelihood, P(c): prior \\n\n",
        "\n",
        "Because computing likelihood*prior is tough, we assume: \\n\n",
        "\\t bag of words -- position doesn't matter\n",
        "\\t naive Bayes -- conditional probabilities are indp. of each other so we can multiply\n",
        "\"\"\"\n",
        "slp_chapter4_2 = \"\"\"\n",
        "When we have unknown words (words only in test set, not training), remove them from test \\n\n",
        "Remove stopwords (frequent words with no meaning)\n",
        " \"\"\"\n",
        "slp_chapter4_3 = \"\"\"\"\"\"\n",
        "slp_chapter4_4 = \"\"\"\n",
        "Binary multinomial Naive Bayes: \\n\n",
        "\\t remove all duplicate words so we just have max 1 count of word per doc \\n\n",
        "To deal with negation, add \"NOT\" prefix to each word after token of logical negation \\n\n",
        "If it's hard to estimate +/- sentiment because not enought training data, use sentiment lexicons: \\n\n",
        "\\t can add a feature for y/n if word is in + lexicon and y/n if word is in - lexicon\n",
        " \"\"\"\n",
        "slp_chapter4_5 = \"\"\"\n",
        "Spam detection: \\n\n",
        "\\t can predefine certain sets of words as features \\n\n",
        "Language ID: which language a piece of text is: \\n\n",
        "\\t use character n-grams (i.e. 2-gram:'zw', 3-gram:'bya')\n",
        "\\t use byte n-grams (i.e. everything is string of raw bytes (including space))\n",
        "\"\"\"\n",
        "slp_chapter4_6 = \"\"\"\n",
        "Naive Bayes can be viewed as set of class-specific unigram language models: \\n\n",
        "\\t model for each class = unigram language model\n",
        "\"\"\"\n",
        "slp_chapter4_7 = \"\"\"\n",
        "Confusion matrix uses system output + gold labels: \\n\n",
        "\\t accuracy not good for text classification -- bad metric w/ unbalanced classes\n",
        "\\t precision: TP / (TP + FP)\n",
        "\\t recall: TP / (TP + FN)\n",
        "\\t F-measure: P*R*(B^2+1) / P*(B^2) + R | B > 1 favors recall, B < 1 favors precision\n",
        "\\t B = 1 then F-measure = 2PR/(P+R) \\n\n",
        "\n",
        "Classification for > 2 classes: \\n\n",
        "\\t macroaveraging -- when performance on all classes is equally important\n",
        "\\t microaveraging -- dominated by more frequent class\n",
        "\"\"\"\n",
        "slp_chapter4_8 = \"\"\"\n",
        "Use cross-validation if we don't have enough data to split into a dev/validation set as well\n",
        "\"\"\"\n",
        "slp_chapter4_9 = \"\"\"\n",
        "Use statistical sig. tests to see if a model is better than another model: \\n\n",
        "\\t H_o: effect size is less than or equal to 0 (A is not better than B)\n",
        "\\t H_a: effect size is greater than 0 (A is better than B) \\n\n",
        "How do we compute probability? \\n\n",
        "\\t non parametric tests based on sampling\n",
        "\\t create versions of experimental setup (i.e. lots of test sets)&then set threshold\n",
        "\\t approximate randomization and boostrap tests are 2 common tests using in NLP \\n\n",
        "\n",
        "Paired bootstrap test: \\n\n",
        "\\t Use bootstrapping to get N different test sets and then run models on each test set\n",
        "\\t count number of times effect size is positive and divide by N to get p-value\n",
        "\"\"\"\n",
        "slp_chapter4_10 = \"\"\"\n",
        "Harms from classifiers: \\n\n",
        "\\t Representational harms: system demeans a social group, so a sentiment classifier, \n",
        "\\t for example, could be misrepresented\n",
        "\\t toxicity detection: task of detecting hate speech, abuse, etc but can cause harm\n",
        "\\t can incorrectly flag non-toxic sentences as toxic because of bias \\n\n",
        "\n",
        "We can mitigate this with a model card: documents an ML model with info about: \\n\n",
        "\\t training algo and data, eval data, intended use and users, model performance\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\"\n",
        "confidence form a classifier: how sure the classifier is of classification \\n\n",
        "\\t y which results in maximum P(y|x)\n",
        "\\t weak calibration: higher confidence means higher accuracy\n",
        "\\t strong calibration: confidence predicts accuracy rate \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"learning\" : \"improving performance after observing the world\",\n",
        "\"machine learning\": \"when the learning is done by a computer\",\n",
        "\"induction\": \"specific observations -> general rule. might be incorrect\",\n",
        "\"deduction\": \"accepted facts -> inference. correct if premises are correct\",\n",
        "\"factored representation\": \"vector of attribute values\",\n",
        "\"supervised learning\": \"observes input-output pairs and learns a function\",\n",
        "\"unsupervised learning\": \"no feedback -- learn the patterns in input. i.e. clustering\",\n",
        "\"RL\": \"learn from series of rewards and punishments\",\n",
        "\"consistent hypothesis\": \"always evaluates to the right y-value for all training examples\",\n",
        "\"best-fit function\": \"hypothesis is close to being the right y-value for all examples\",\n",
        "\"bias\": \"tendence of hypothesis to deviate from expected value when average over training sets\",\n",
        "\"variance\": \"amount of change in hypothesis due to changes in training data\",\n",
        "\"decision tree\": \"function mapping attributes to a single output value\",\n",
        "\"learning curve\": \"plot of the training/cross-validation error versus the sample size\",\n",
        "\"entropy\": \"measures uncertainty of RV. more info = less entropy\",\n",
        "\"information gain\": \"expected reduction in entropy\",\n",
        "\"early stopping\": \"decision tree stops generating nodes when there is no good attr. to split on\",\n",
        "\"equality test\": \"check if a variable is equal to a value or not\",\n",
        "\"stationarity\": \"all future examples will be like the past. conditional prob table doesn't change over time\",\n",
        "\"i.i.d\": \"independent and identically distributed\",\n",
        "\"error rate\": \"proportion of times that the hypothesis doesn't result in the actual label\",\n",
        "\"LOOCV\": \"when k = n in k-fold cross validation\",\n",
        "\"model selection\": \"chooses a good hypothesis space\",\n",
        "\"model optimization/training\": \"finds the best hypothesis in the selected space\",\n",
        "\"interpolated model\": \"model exactly fits the training data\",\n",
        "\"loss function\": \"amount of utility lost by making the wrong prediction\",\n",
        "\"realizable learning problem\": \"hypothesis space actually contains the true function\",\n",
        "\"regularization\": \"adding a penalty to complex hypotheses\",\n",
        "\"grid search\": \"try all combinations of values for hyperparameters\",\n",
        "\"random search\": \"samples uniformly from all possible values if grid search will take too long\",\n",
        "\"Bayesian optimization\": \"treat finding optimal hyperparams as an ML model -- input (hyperparams), output(model perf)\",\n",
        "\"computational learning theory\": \"AI, statistics, theoretical CS\",\n",
        "\"probably approximately correct (PAC)\": \"any hypothesis that is consistent with large training set will be PAC\",\n",
        "\"PAC Learning\": \"an algorithm that returns hypotheses that are PAC\",\n",
        "\"decision lists\": \"series of tests which are conjunctions of literals\",\n",
        "\"convex\": \"loss function for every linear regre problem with L2 loss function. no local minima\",\n",
        "\"epoch\": \"step covering all training examples\",\n",
        "\"threshold function\": \"sets a threshold for what to classify a point as\",\n",
        "\"bag of words\": \"unordered set of words with their position ignored. words + their frequencies in doc\",\n",
        "\"generative model\": \"learns everything about classes in depth. uses distribution of data to return a probability\",\n",
        "\"discriminative model\": \"can only learn the differences between classes, not all of the features\",\n",
        "\"linear classifiers\": \"use linear combo of inputs. naive bayes, log regr\",\n",
        "\"sentiment lexicons\": \"list of words pre-annotated with positive or negative sentiment\",\n",
        "\"gold labels\": \"human-defined labels for classification\",\n",
        "\"precision\": \"percent of items that system labeled + that are +\",\n",
        "\"recall\": \"percent of items out of whole input that are correctly labeled\",\n",
        "\"macroaveraging\": \"compute performance for each class, then average over classes\",\n",
        "\"microaveraging\": \"collect decisions for all classes into 1 confusion matrix and then compute P/R\",\n",
        "\"effect size\": \"number measuring strength of relationship between 2 models/variables\",\n",
        "\"p-value\": \"assuming H_o is true, probability of seeing effect size we saw or greater\",\n",
        "\"paired tests\": \"compare 2 sets of observations that are aligned (model A and B on same data points)\",\n",
        "\"bootstrapping\": \"random sampling with replacement\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "83c85d63-ded3-41f7-e4f9-1b3160a704a5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 19.1\", chapter19_1),\n",
        "  (\"AIMA Chapter 19.2\", chapter19_2),\n",
        "  (\"AIMA Chapter 19.3\", chapter19_3),\n",
        "  (\"AIMA Chapter 19.4\", chapter19_4),\n",
        "  (\"AIMA Chapter 19.5\", chapter19_5),\n",
        "  (\"AIMA Chapter 19.6\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1\n \nImproving agents using ML depends on: \n\n\t which component to improve, prior knowledge of agent, data and feedback \n\n\nComponents of agents: \n\n\t direct mapping from conditions on current state to actions\n\t ability to infer relevant properties of world from percept sequence\n\t info about how world evolves + results of agent's actions\n\t utility info about each state\n\t action-value info\n\t goals\n\t problem generator, critic, and learning element to allow for improvement \n\n\n3 types of learning: supervised, unsupervised, RL \n\n\n## AIMA Chapter 19.2\n\nHigh bias: linear functions, any function very fitted to data \n\nLow bias: piecewise linear function, decision trees, RF \n\nHigh variance: very high degree polynomial, KNN, RF \n\nLow variance: linear function \n\n\nWhy do we want simple hypothesis spaces: \n\n\t computational complexity too high with more complex\n\t hard to replicate using a complex one \n \n\n## AIMA Chapter 19.3\n \nDecision trees: \n\n\t split on attribute that makes the most difference in classification for an example\n\t entropy: -ΣP(v)*log_2P*v) ; sum over each possible value of variable v \n\t use pruning (remove nodes with low information gain) to combat overfitting \n\t H_o: no underlying pattern. use statistical sig test to decide what to prune \n\nWe can make decision trees more useful by handling: \n\n\t missing data\n\t continuous attr: use a split point (i.e. Weight > 160), IG Ratio, Equality test\n\t continuous-valued output attr: use a regr. tree \n\nOverall: \n\n\t easy to understand, scale to large datasets\n\t versatile with discrete/cont variables + class/regr\n\t can have suboptimal accuracy, unstable (adding 1 example can change everything) \n\n\nOverfitting becomes more likely as we increase # of attributes, less likely as we increase # of data points \n\nProblem with early stopping: can't recognize when we need a combo of attr. instead of 1 \n\n\n\n## AIMA Chapter 19.4\n \nModel selection starts with a small model which probably underfits and then iterates thru more complex models \n\n\t train error will decrease as complexity (# of tree nodes, # of params) increases\n\t val/test set error will decrease for a while but increase when overfitting begins\n\t want to minimze the loss function \n\nReasons the hypothesis differs from the real function: \n\n\t unrealizability, variance, noise, computational complexity\n\t noise -- could return different values of f(x) for x\n\t complexity -- if complex function, could be too much to search \n\nSimplifying models: \n\n\t regularization, feature selection \n\n\npopulation based training (PBT): \n\n\t uses random search to train models with dif hyperparam values\n\t then next set of models is trained based on previous hyperparam values\n \n\n## AIMA Chapter 19.5\n\nApproximately correct hypothesis: error is less than some E \n\n\t sample complexity: # of required examples \n\nTo obtain real generalization to unseen examples: \n\n\t bring prior knowledge for the problem\n\t get algorithm to return a simple consistent hypothesis\n\t focus on learnable subsets of hypothesis space \n\n\nDecision lists: \n\n\t if test succeeds, decision list specifies value to return\n\t if test fails, go to next test in list \n\t simpler than decision tree because they only branch in 1 direction \n\t but individual tests are more complex than decision trees \n\n \n\n## AIMA Chapter 19.6\n\nGradient descent: finds the minimum of a function\n\n\t start at any point in weight space, compute estimate of gradient, \n\t move in direction opposite to steepest slope\n\t repeat until converged\n\t weight = weight - alpha*derivative(Loss(w))\n\t alpha: step size/learning rate \n\n\nBatch gradient descent: \n\n\t gradient descent on all of the training data at once \n\n\nStochastic gradient descent: \n\n\t randomly sample 1 training example at each step and gradient descent on it\n\t minibatch: randomly sample M training examples at each step\n\t convergence of minibatch SGD not guaranteed\n\t SGD useful for when data is coming in 1 at a time and isn't stationary \n\n\nWith univariate LR, no overfitting. But multivariate LR, you can have overfitting: \n\n\t use regularization -- L1 (sum of abs values), L2 (sum of squares)\n\t L1 produces a sparse model (can set weights to 0) \n\n\nLinear functions can be used for classification too: \n\n\t decision boundary will separate 2 classes (if linear, then linear separator) \n\nPerceptron Learning Rule: \n\n\t if output correct, no change to weights\n\t if y is 1 but correct is 0, increase weight when x is pos, decrease when x is neg\n\t if y is 0 but correct is 1, decrease weight when x is pos, increase when x is neg\n\t applied to 1 point in training set at a time \n\nWe can soften the threshold function using logistic function so that we can account for \n\nsome points not being exactly 0 or 1. We can use the L2 loss function here. If data is \n\nlinearly separable, log. regr. takes longer to converge than lin. regr., but more predictable. \n\nIf data noisy/nonseparable, log. regr. better.\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n \nMultinomial Naive Bayes: \n\n\t estimate of correct class = P(d|c)P(c)\n\t dropped denominator: P(d); perform this for every class and get argmax\n\t generative model\n\t P(d|c): likelihood, P(c): prior \n\n\nBecause computing likelihood*prior is tough, we assume: \n\n\t bag of words -- position doesn't matter\n\t naive Bayes -- conditional probabilities are indp. of each other so we can multiply\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\nWhen we have unknown words (words only in test set, not training), remove them from test \n\nRemove stopwords (frequent words with no meaning)\n \n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\nBinary multinomial Naive Bayes: \n\n\t remove all duplicate words so we just have max 1 count of word per doc \n\nTo deal with negation, add \"NOT\" prefix to each word after token of logical negation \n\nIf it's hard to estimate +/- sentiment because not enought training data, use sentiment lexicons: \n\n\t can add a feature for y/n if word is in + lexicon and y/n if word is in - lexicon\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\nSpam detection: \n\n\t can predefine certain sets of words as features \n\nLanguage ID: which language a piece of text is: \n\n\t use character n-grams (i.e. 2-gram:'zw', 3-gram:'bya')\n\t use byte n-grams (i.e. everything is string of raw bytes (including space))\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\nNaive Bayes can be viewed as set of class-specific unigram language models: \n\n\t model for each class = unigram language model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\nConfusion matrix uses system output + gold labels: \n\n\t accuracy not good for text classification -- bad metric w/ unbalanced classes\n\t precision: TP / (TP + FP)\n\t recall: TP / (TP + FN)\n\t F-measure: P*R*(B^2+1) / P*(B^2) + R | B > 1 favors recall, B < 1 favors precision\n\t B = 1 then F-measure = 2PR/(P+R) \n\n\nClassification for > 2 classes: \n\n\t macroaveraging -- when performance on all classes is equally important\n\t microaveraging -- dominated by more frequent class\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\nUse cross-validation if we don't have enough data to split into a dev/validation set as well\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\nUse statistical sig. tests to see if a model is better than another model: \n\n\t H_o: effect size is less than or equal to 0 (A is not better than B)\n\t H_a: effect size is greater than 0 (A is better than B) \n\nHow do we compute probability? \n\n\t non parametric tests based on sampling\n\t create versions of experimental setup (i.e. lots of test sets)&then set threshold\n\t approximate randomization and boostrap tests are 2 common tests using in NLP \n\n\nPaired bootstrap test: \n\n\t Use bootstrapping to get N different test sets and then run models on each test set\n\t count number of times effect size is positive and divide by N to get p-value\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\nHarms from classifiers: \n\n\t Representational harms: system demeans a social group, so a sentiment classifier, \n\t for example, could be misrepresented\n\t toxicity detection: task of detecting hate speech, abuse, etc but can cause harm\n\t can incorrectly flag non-toxic sentences as toxic because of bias \n\n\nWe can mitigate this with a model card: documents an ML model with info about: \n\n\t training algo and data, eval data, intended use and users, model performance\n\n\n## Module 12 Lecture Notes\n\nconfidence form a classifier: how sure the classifier is of classification \n\n\t y which results in maximum P(y|x)\n\t weak calibration: higher confidence means higher accuracy\n\t strong calibration: confidence predicts accuracy rate \n\n\n\n## Module 12 Definitions\n* **Learning** - improving performance after observing the world\n* **Machine learning** - when the learning is done by a computer\n* **Induction** - specific observations -> general rule. might be incorrect\n* **Deduction** - accepted facts -> inference. correct if premises are correct\n* **Factored representation** - vector of attribute values\n* **Supervised learning** - observes input-output pairs and learns a function\n* **Unsupervised learning** - no feedback -- learn the patterns in input. i.e. clustering\n* **Rl** - learn from series of rewards and punishments\n* **Consistent hypothesis** - always evaluates to the right y-value for all training examples\n* **Best-fit function** - hypothesis is close to being the right y-value for all examples\n* **Bias** - tendence of hypothesis to deviate from expected value when average over training sets\n* **Variance** - amount of change in hypothesis due to changes in training data\n* **Decision tree** - function mapping attributes to a single output value\n* **Learning curve** - plot of the training/cross-validation error versus the sample size\n* **Entropy** - measures uncertainty of RV. more info = less entropy\n* **Information gain** - expected reduction in entropy\n* **Early stopping** - decision tree stops generating nodes when there is no good attr. to split on\n* **Equality test** - check if a variable is equal to a value or not\n* **Stationarity** - all future examples will be like the past. conditional prob table doesn't change over time\n* **I.i.d** - independent and identically distributed\n* **Error rate** - proportion of times that the hypothesis doesn't result in the actual label\n* **Loocv** - when k = n in k-fold cross validation\n* **Model selection** - chooses a good hypothesis space\n* **Model optimization/training** - finds the best hypothesis in the selected space\n* **Interpolated model** - model exactly fits the training data\n* **Loss function** - amount of utility lost by making the wrong prediction\n* **Realizable learning problem** - hypothesis space actually contains the true function\n* **Regularization** - adding a penalty to complex hypotheses\n* **Grid search** - try all combinations of values for hyperparameters\n* **Random search** - samples uniformly from all possible values if grid search will take too long\n* **Bayesian optimization** - treat finding optimal hyperparams as an ML model -- input (hyperparams), output(model perf)\n* **Computational learning theory** - AI, statistics, theoretical CS\n* **Probably approximately correct (pac)** - any hypothesis that is consistent with large training set will be PAC\n* **Pac learning** - an algorithm that returns hypotheses that are PAC\n* **Decision lists** - series of tests which are conjunctions of literals\n* **Convex** - loss function for every linear regre problem with L2 loss function. no local minima\n* **Epoch** - step covering all training examples\n* **Threshold function** - sets a threshold for what to classify a point as\n* **Bag of words** - unordered set of words with their position ignored. words + their frequencies in doc\n* **Generative model** - learns everything about classes in depth. uses distribution of data to return a probability\n* **Discriminative model** - can only learn the differences between classes, not all of the features\n* **Linear classifiers** - use linear combo of inputs. naive bayes, log regr\n* **Sentiment lexicons** - list of words pre-annotated with positive or negative sentiment\n* **Gold labels** - human-defined labels for classification\n* **Precision** - percent of items that system labeled + that are +\n* **Recall** - percent of items out of whole input that are correctly labeled\n* **Macroaveraging** - compute performance for each class, then average over classes\n* **Microaveraging** - collect decisions for all classes into 1 confusion matrix and then compute P/R\n* **Effect size** - number measuring strength of relationship between 2 models/variables\n* **P-value** - assuming H_o is true, probability of seeing effect size we saw or greater\n* **Paired tests** - compare 2 sets of observations that are aligned (model A and B on same data points)\n* **Bootstrapping** - random sampling with replacement\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 = \"\"\" \n",
        "Naive Bayes is generative, LR is discriminative \\n\n",
        "\\t generative model will use P(d|c) and P(c) to get P(c|d)\n",
        "\\t discriminative model will try to compute P(c|d) directly \\n\n",
        "4 Components of ML system for classification: \\n\n",
        "\\t feature representation of input, classification function to compute predicted class\n",
        "\\t objective function for learning, algorithm to optimize objective function \\n\n",
        "\n",
        "LR learns vector of weights and bias term \\n\n",
        "Sigmoid maps 1/(1+e^(-z)) to range [0,1] \\n\n",
        "\\t z is dot product of weights and x-values + bias\n",
        "\\t squashes outliers near 0 and 1\n",
        "\\t differentiable\n",
        "\\t 1-sigmoid(x) = sigmoid(-x)\n",
        "\\t uses decision boundary to determine the class \\n\n",
        "\n",
        "Both NB and LR -- have to design feature interactions by hand \\n\n",
        "\\t can use feature templates to create a lot\n",
        "\\t rep. learning reduces human effort&learns features automatically using unsup. learning \\n\n",
        "\n",
        "LR vs NB; \\n\n",
        "\\t NB assumes indp. between features but LR is more robust to correlated features\n",
        "\\t NB less accurate but good for short docs, easy/fast to train \n",
        " \"\"\"\n",
        "slp_chapter5_2 = \"\"\" \n",
        "LR measures difference between correct and predicted using loss/cost function \\n\n",
        "Optimization algo used in LR is gradient descent\n",
        "\"\"\"\n",
        "slp_chapter5_3 = \"\"\"\n",
        "Conditional MLE: \\n\n",
        "\\t choose weights and bias that maximize log(prob) of true y labels in training data\n",
        "\\t this is the same as minimizing the cross-entropy\n",
        "\\t cross entropy loss: -log likelihood\n",
        " \"\"\"\n",
        "slp_chapter5_4 = \"\"\"\n",
        "Gradient descent: finds minimum of function by moving in opposite direction of steepest rise in slope \\n\n",
        "\\t LR loss function is convex -- only 1 minimum, so GD works great\n",
        "\\t gradient is weighted by learning rate -- higher rate means move faster @ each step\n",
        "\\t multiple features-take partial derivative wrt each feature to get gradient vector \n",
        "\\t gradient: x*(diff between true y and predicted y) \\n\n",
        "SGD: \\n\n",
        "\\t computes gradient after each training example\n",
        "\\t learning rate is a hyperparameter\n",
        "\\t can be choppy, so minibatch \\n\n",
        "MiniBatch GD: \\n\n",
        "\\t computes gradient over batches of training examples\n",
        "\\t batch training: gradient over entire training set at once, but this is high cost\n",
        "\\t minibatch: take m examples; this can be vectorized so it's faster\n",
        " \"\"\"\n",
        "slp_chapter5_5 = \"\"\"\n",
        "To avoid overfitting, add regularization to the objective function: \\n\n",
        "\\t L2 ridge-Euclidean distance (shortest distance)||L1 lasso--Manhattan distance (sum of all real distances) \n",
        "\\t L2 -- weights have Gaussian distribution || L1 -- Laplace prior on weights\n",
        " \"\"\"\n",
        "slp_chapter5_6 = \"\"\"\n",
        "softmax(z_i): e^z_i / sum(e^z_j) over all z \\n\n",
        "\\t use this instead of sigmoid when multinomial regr. \\n\n",
        "Multinomial LR: \\n\n",
        "\\t need separate weight vectors and biases for each class\n",
        "\\t loss function: sum(logs of each output class), weighted by probability of true class\n",
        "\\t negative log likelihood loss\n",
        " \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"\n",
        "\\n\n",
        "activation functions: sigmoid, tanh, RELU \\n\n",
        "\\t tanh:(e^z-e^-z)/(e^z+e^-z);range[-1,1]; smoothly differentiable&maps outliers towards mean\n",
        "\\t RELU: max(z,0) -- range[0,z]; close to linear but when negative, very different\n",
        "\\t sigmoid: 1/(1+e^(-z)) -- range[0,1]; differentiable \\n\n",
        "Vanishing gradient: problem where gradients get too close to 0; avoidable with RELU\n",
        "\"\"\"\n",
        "slp_chapter7_2 = \"\"\"\n",
        "Perceptron: has binary output and a linear activation function \\n\n",
        "\\t properties: separability, convergence, mistake bound\n",
        "\\t problems: noise, mediocre generalization, overtraining \n",
        "\\t converges to minimum-error solution when LR decreases as training time increases \\n\n",
        "XOR is not a linearly separable function so we need NN \\n\n",
        "\\t XOR: True if 1 statement is True, False if both statements are True\n",
        " \"\"\"\n",
        "slp_chapter7_3 = \"\"\"\n",
        "Feedforward NN/multilayer perceptrons: multilayer, outputs are passed from lower to higher level \\n\n",
        "\\t hidden layers taken weighted sum of inputs and apply non-linear activation function \n",
        "\\t each layer is full-connected (takes all outputs from previous layer as inputs)\n",
        "\\t hidden layer output (h) = activationfunction*(Wx+b)\n",
        "\\t output layer: gives prob. distr. across the output nodes\n",
        "\\t we use softmax to convert output vector from values --> probabilities\n",
        "\"\"\"\n",
        "slp_chapter7_4 = \"\"\"\n",
        "NN for NLP: \\n\n",
        "\\t pretraining: instead of using human-made features, uses embeddings as inputs\n",
        "\"\"\"\n",
        "slp_chapter7_5 = \"\"\"\n",
        "Neural language modeling: predicting words from prior word context: \\n\n",
        "\\t Neural vs N-gram: neural can handle longer histories, better generalization,\n",
        "\\t more accurate, no smoothing\n",
        "\\t But, n-gram is more interpretable, less complex, faster to train\n",
        "\\t words are representated by their embeddings \\n\n",
        "Forward inference/decoding: \\n\n",
        "\\t running forward pass on NN to get output\n",
        "\\t each previous word is represented as one-hot vector that \n",
        "\\t is the length of every distinct word in vocab\n",
        "\\t embedding matrix has column for every distinct word\n",
        "\\t multiply one-hot vector * embedding matrix to get the embedding for the word\n",
        "\\t all the previous words' embeddings make up the embedding layer\n",
        "\"\"\"\n",
        "slp_chapter7_6 = \"\"\"\n",
        "Training neural nets: \\n\n",
        "\\t use cross-entropy loss as loss function; same process as LR\n",
        "\\t use GD: compute partial derivative of loss function wrt each parameter\n",
        "\\t it is hard to compute partial derivative for a NN with multiple layers, so \n",
        "\\t we use error backpropagation\n",
        "\\t Error back-propagation enables us to correctly update all layers in the neural network \\n\n",
        "To prevent overfitting \\n\n",
        "\\t dropout: randomly dropping some units during training\n",
        "\\t tune hyperparams: learning rate, mini-batch size, model architecture (i.e. # of layers)\n",
        "\"\"\"\n",
        "slp_chapter7_7 = \"\"\"\n",
        "Training neural language model: \\n\n",
        "\\t classes are the words in the vocabulary, \n",
        "\\t so prediction is the probability of word being next word\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\"\n",
        "A perceptron converges to a minimum-error solution when learning rate decreases as training time increases \\n\n",
        "Why do we use non-linear activation functions in a multi-layer neural network? \\n\n",
        "If we used a linear activation function, the resulting network would be equivalent to a single-layer network \\n\n",
        "Smoothness is crucial - you want a small change in weights and bias will produce small change in output \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"period disambiguation\" : \"deciding if period is part of a word or the end of sentence\",    \n",
        "\"softmax regression\": \"multinomial regression\",\n",
        "\"one-hot vector\": \"1 value is 1 and the rest are 0\",\n",
        "\"hard classification\": \"only 1 class is the correct one\",\n",
        "\"freeze\": \"keep embedding matrix E constant throughout training; can do this for some tasks\",\n",
        "\"MIRA\": \"margin infused relaxed algorithm\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a3928af2-244c-457f-b6d1-831bbb536757"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nNaive Bayes is generative, LR is discriminative \n\n\t generative model will use P(d|c) and P(c) to get P(c|d)\n\t discriminative model will try to compute P(c|d) directly \n\n4 Components of ML system for classification: \n\n\t feature representation of input, classification function to compute predicted class\n\t objective function for learning, algorithm to optimize objective function \n\n\nLR learns vector of weights and bias term \n\nSigmoid maps 1/(1+e^(-z)) to range [0,1] \n\n\t z is dot product of weights and x-values + bias\n\t squashes outliers near 0 and 1\n\t differentiable\n\t 1-sigmoid(x) = sigmoid(-x)\n\t uses decision boundary to determine the class \n\n\nBoth NB and LR -- have to design feature interactions by hand \n\n\t can use feature templates to create a lot\n\t rep. learning reduces human effort&learns features automatically using unsup. learning \n\n\nLR vs NB; \n\n\t NB assumes indp. between features but LR is more robust to correlated features\n\t NB less accurate but good for short docs, easy/fast to train \n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nLR measures difference between correct and predicted using loss/cost function \n\nOptimization algo used in LR is gradient descent\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\nConditional MLE: \n\n\t choose weights and bias that maximize log(prob) of true y labels in training data\n\t this is the same as minimizing the cross-entropy\n\t cross entropy loss: -log likelihood\n \n\n## SLP Chapter 5.4 Gradient Descent\n\nGradient descent: finds minimum of function by moving in opposite direction of steepest rise in slope \n\n\t LR loss function is convex -- only 1 minimum, so GD works great\n\t gradient is weighted by learning rate -- higher rate means move faster @ each step\n\t multiple features-take partial derivative wrt each feature to get gradient vector \n\t gradient: x*(diff between true y and predicted y) \n\nSGD: \n\n\t computes gradient after each training example\n\t learning rate is a hyperparameter\n\t can be choppy, so minibatch \n\nMiniBatch GD: \n\n\t computes gradient over batches of training examples\n\t batch training: gradient over entire training set at once, but this is high cost\n\t minibatch: take m examples; this can be vectorized so it's faster\n \n\n## SLP Chapter 5.5 Regularization\n\nTo avoid overfitting, add regularization to the objective function: \n\n\t L2 ridge-Euclidean distance (shortest distance)||L1 lasso--Manhattan distance (sum of all real distances) \n\t L2 -- weights have Gaussian distribution || L1 -- Laplace prior on weights\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n\nsoftmax(z_i): e^z_i / sum(e^z_j) over all z \n\n\t use this instead of sigmoid when multinomial regr. \n\nMultinomial LR: \n\n\t need separate weight vectors and biases for each class\n\t loss function: sum(logs of each output class), weighted by probability of true class\n\t negative log likelihood loss\n \n\n## SLP Chapter 7.1 Units\n\n\n\nactivation functions: sigmoid, tanh, RELU \n\n\t tanh:(e^z-e^-z)/(e^z+e^-z);range[-1,1]; smoothly differentiable&maps outliers towards mean\n\t RELU: max(z,0) -- range[0,z]; close to linear but when negative, very different\n\t sigmoid: 1/(1+e^(-z)) -- range[0,1]; differentiable \n\nVanishing gradient: problem where gradients get too close to 0; avoidable with RELU\n\n\n## SLP Chapter 7.2 The XOR problem\n\nPerceptron: has binary output and a linear activation function \n\n\t properties: separability, convergence, mistake bound\n\t problems: noise, mediocre generalization, overtraining \n\t converges to minimum-error solution when LR decreases as training time increases \n\nXOR is not a linearly separable function so we need NN \n\n\t XOR: True if 1 statement is True, False if both statements are True\n \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\nFeedforward NN/multilayer perceptrons: multilayer, outputs are passed from lower to higher level \n\n\t hidden layers taken weighted sum of inputs and apply non-linear activation function \n\t each layer is full-connected (takes all outputs from previous layer as inputs)\n\t hidden layer output (h) = activationfunction*(Wx+b)\n\t output layer: gives prob. distr. across the output nodes\n\t we use softmax to convert output vector from values --> probabilities\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\nNN for NLP: \n\n\t pretraining: instead of using human-made features, uses embeddings as inputs\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\nNeural language modeling: predicting words from prior word context: \n\n\t Neural vs N-gram: neural can handle longer histories, better generalization,\n\t more accurate, no smoothing\n\t But, n-gram is more interpretable, less complex, faster to train\n\t words are representated by their embeddings \n\nForward inference/decoding: \n\n\t running forward pass on NN to get output\n\t each previous word is represented as one-hot vector that \n\t is the length of every distinct word in vocab\n\t embedding matrix has column for every distinct word\n\t multiply one-hot vector * embedding matrix to get the embedding for the word\n\t all the previous words' embeddings make up the embedding layer\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\nTraining neural nets: \n\n\t use cross-entropy loss as loss function; same process as LR\n\t use GD: compute partial derivative of loss function wrt each parameter\n\t it is hard to compute partial derivative for a NN with multiple layers, so \n\t we use error backpropagation\n\t Error back-propagation enables us to correctly update all layers in the neural network \n\nTo prevent overfitting \n\n\t dropout: randomly dropping some units during training\n\t tune hyperparams: learning rate, mini-batch size, model architecture (i.e. # of layers)\n\n\n## SLP Chapter 7.7 Training the neural language model\n\nTraining neural language model: \n\n\t classes are the words in the vocabulary, \n\t so prediction is the probability of word being next word\n\n\n## Module 13 Lecture Notes\n\nA perceptron converges to a minimum-error solution when learning rate decreases as training time increases \n\nWhy do we use non-linear activation functions in a multi-layer neural network? \n\nIf we used a linear activation function, the resulting network would be equivalent to a single-layer network \n\nSmoothness is crucial - you want a small change in weights and bias will produce small change in output \n\n\n\n\n## Module 13 Definitions\n* **Period disambiguation** - deciding if period is part of a word or the end of sentence\n* **Softmax regression** - multinomial regression\n* **One-hot vector** - 1 value is 1 and the rest are 0\n* **Hard classification** - only 1 class is the correct one\n* **Freeze** - keep embedding matrix E constant throughout training; can do this for some tasks\n* **Mira** - margin infused relaxed algorithm\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 = \"\"\"\n",
        "Issues with FF NN: \\n\n",
        "1) limited context: only have access to words in the window, but usually you need more \\n\n",
        "2) using windows-hard to learn deeper meaning, especially if phrase has been split over windows\n",
        " \"\"\"\n",
        "slp_chapter9_2 = \"\"\"\n",
        "Recurrent Neural Network (RNN): contains cycle within network \\n\n",
        "**the hidden layer's input is the output of previous layer WITH the value of hidden layer from previous timestep \\n\n",
        "**this allows us to use information from earlier processing and give us variable lengths of prior context \\n\n",
        "How inference works? \\n\n",
        "**multiple input with weight matrix W, hidden layer from previous timestep with weight matrix U \\n\n",
        "**add the 2 values together and pass thru activation function to get new activation value \\n\n",
        "Training: \\n\n",
        "\\t 3 sets of weights to update: W, U, V (weights from hidden to output layer)\n",
        "\\t 2 pass algorithm: 1) forward inference thru network\n",
        "\\t 2) go in reverse, compute gradients as we go&error terms to use in each hidden layer\n",
        "\"\"\"\n",
        "slp_chapter9_3 = \"\"\"\n",
        "RNN Language Models: \\n\n",
        "**process input seq 1 at a time; no limited context problem because can look up seq of words of any length \\n\n",
        "\\t forward inference is the same as RNN with embeddings as input and using E matrix\n",
        "\\t use corpus of text for training data\n",
        "\\t cross-entropy is loss function\n",
        "\\t teacher forcing is used \\n\n",
        "**V is also a set of word embeddings just like E, so we can use weight tying if we want to reduce # of params\n",
        " \"\"\"\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 = \"\"\"\n",
        "Lexical semantics: study of word meaning \\n\n",
        "\\t lemma: word that is a form of other words (i.e. mouse is lemma of mice)\n",
        "\\t wordforms are the other words that are similar to the lemma\n",
        "\\t word sense: every meaning of word (i.e. mouse can be animal, device) \n",
        "\\t can be represented using WordNet tree \\n\n",
        "3 dimensions of affective meaning: \\n\n",
        "\\t valence: pleasantness\n",
        "\\t arousal: intensity of emotion\n",
        "\\t dominance: degree of control exerted\n",
        "\"\"\"\n",
        "slp_chapter6_2 = \"\"\"\n",
        "Vector semantics: \\n\n",
        "1) tf-idf: meaning of word defined by function of counts of nearby words, results in sparse vectors \\n\n",
        "2) word2vec: results in dense vectors \\n\n",
        "3) cosine: use embeddings to compute semantic similarity between 2 pieces of text\n",
        "\"\"\"\n",
        "slp_chapter6_3 = \"\"\"\n",
        "co-occurence matrices represent how often words occur together \\n\n",
        "\n",
        "1) term-document matrix \\n\n",
        "\\t rows: words in vocab, columns: documents\n",
        "\\t good for finding similar documents using similar column vectors \\n\n",
        "2) term-term matrix \\n\n",
        "\\t aka word-word or term-context\n",
        "\\t rows: words in vocab, columns: words in vocab \\n\n",
        "** each cell is # of times row word appeared in same context window (i.e. document, window of size 2) as column word\n",
        "\"\"\"\n",
        "slp_chapter6_4 = \"\"\"\n",
        "cosine: high value means very similar, 0 means completely dissimilar \\n\n",
        "\\t problem: dot product favors longer vectors, so we normalize it\n",
        "\\t cosine similarity: cos(θ) = a•b / (|a||b|); -1 means opposite, 1 means exactly same\n",
        "\\t vector length: |x| = sqrt(sum of the squared values of each number in the vector)\n",
        "\\t unit vector: divide a vector by its vector length\n",
        "\"\"\"\n",
        "slp_chapter6_8 = \"\"\"\n",
        "embeddings are shorter versions of the word vectors used in previous models and they are dense \\n\n",
        "Dense is better in NLP than sparse because: \\n\n",
        "\\t fewer weights for classifier to learn, less overfitting, better capture synonymy \\n\n",
        "\n",
        "Word2vec: fast, efficient to train, easily available with pretrained embeddings \\n\n",
        "\\t uses static embeddings\n",
        "\\t instead of counting how often a word occurs near another word, \n",
        "\\t train a classifier to predict if a word is likely to show up near another word \n",
        "\\t the weights we learn from this will be the embeddings for each word \n",
        "\\t words close to each other will have more similar embeddings \\n\n",
        "\n",
        "Skip-Gram: \\n\n",
        "\\t treat each target word and neighboring context word as positive examples\n",
        "\\t randomly sample other words to get neg. examples\n",
        "\\t use LR to train classifier for positive vs. negative\n",
        "\\t use learned weights as embeddings\n",
        "\\t initialize 2 embeddings - W for word and C for context\n",
        "\\t classifer assigns prob. based on how similar context window is to target word\n",
        "\\t sigmoid applied to dot product of embeddings of target word with context word \\n\n",
        "\n",
        "Skip-Gram Algorithm \\n\n",
        "\\t assign a random embedding to each word in vocab\n",
        "\\t iteratively shift each word's embedding to be more like the words it is near\n",
        "\\t maximize similarity of word + positive contexts and minimize word + neg contexts \\n\n",
        "key points: SG learns 2 embeddings per word (target and context), can just add them together\n",
        "\"\"\"\n",
        "slp_chapter6_10 = \"\"\"\n",
        "Semantic properties of embeddings: \\n\n",
        "\\t first-order co-occurence: 2 words are near each other in corpus (i.e. wrote, book)\n",
        "\\t second-order co-occurence: 2 words have similar neighbors (i.e. wrote, said, remarked)\n",
        "\\t parallelogram model: uses analogies --> predicted b*=argmin distance(x, a*-a+b)\n",
        "\"\"\"\n",
        "slp_chapter6_11 = \"\"\"\n",
        "Bias in Embeddings: \\n\n",
        "\\t allocational harm: system allocate jobs/credit unfairly to groups (i.e. hiring bias)\n",
        "\\t embeddings amplify bias\n",
        "\\t representational harm: system demeans/ignores certain groups\n",
        "\"\"\"\n",
        "slp_chapter6_12 = \"\"\"\n",
        "Evaluating Vector Models: \\n\n",
        "\\t similarity: algorithm's word similarity scores vs human's similarity ratings \\n\n",
        "All embedding algorithsm suffer from inherent variability, so we should train multiple embeddings\n",
        "and use bootstrap sampling over documents\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\"\n",
        "Word meaning representation should encode: \\n\n",
        "1) synonyms, antonyms, connotations, semantic roles, support for entailment \\n\n",
        "2) entailment: mathematically well-undestood, powerful for logical operations, knowledge comes from somewhere \\n\n",
        "TF-IDF: \n",
        "\\t term frequency: how often word occurred in a document\n",
        "\\t inverse document frequency: 1/# of documents word occurred in \\n\n",
        "Curse of dimensionality: if vocab is too large, too many params to estimate \\n\n",
        "\\Language modeling learns a function that returns the joint probability \\n\n",
        "\\t issues: curse of dimensionality, n-gram models are bad at generalizing\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"teacher forcing\":\"always give model correct next word to use as input for next step instead of using best prediction from previous time step\",    \n",
        "\"weight tying\": \"E and V matrices are similar, so just use a single set of embeddings instead. E = V\",\n",
        "\"distributional hypothesis\": \"words that occur in similar contexts have similar meanings\",\n",
        "\"vector semantics\": \"interprets word meaning by learning embeddings to explain distr. hypothesis\",\n",
        "\"polysemous\": \"a word that has multiple word senses\",\n",
        "\"word sense disambiguation\": \"figuring out which word sense is being used in a context\",\n",
        "\"propositional meaning\": \"when 2 words are direct synonyms\",\n",
        "\"principle of contrast\": \"difference in linguistic form can change the meaning of word (i.e. H20 in science, water for hike)\",\n",
        "\"similarity\": \"can use humans to judge\",\n",
        "\"relatedness/assocation\": \"i.e. coffee and cup, scalpel and surgeon. typically part of same semantic field\",\n",
        "\"semantic field\": \"set of words that have structured relationship to each other. use in topic modeling\",\n",
        "\"LDA\": \"unsupervised learning on text to get associated words\",\n",
        "\"semantic frame\": \"set of words that denote the perspectives in an event (i.e. buy and sell). important for question answering\",\n",
        "\"connotations\": \"aspects of a word's meaning that are related to the writer/reader's emotions/sentiment/etc\",\n",
        "\"information retrieval\": \"finding the document that best matches the query\",\n",
        "\"skip-gram with negative sampling\": \"aka word2vec\",\n",
        "\"static embeddings\": \"method learns 1 fixed embedding for each word\",\n",
        "\"contextual embeddings\": \"vector for each word is different in different contexts\",\n",
        "\"self-supervision\": \"unsupervised learning where withhold some information about data, and task network with predicting it\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d7472ea9-05d0-4c2f-f983-3b7f95fbc11d"
      },
      "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 14 Lecture Notes\", module14_lecture_notes)\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\nIssues with FF NN: \n\n1) limited context: only have access to words in the window, but usually you need more \n\n2) using windows-hard to learn deeper meaning, especially if phrase has been split over windows\n \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\nRecurrent Neural Network (RNN): contains cycle within network \n\n**the hidden layer's input is the output of previous layer WITH the value of hidden layer from previous timestep \n\n**this allows us to use information from earlier processing and give us variable lengths of prior context \n\nHow inference works? \n\n**multiple input with weight matrix W, hidden layer from previous timestep with weight matrix U \n\n**add the 2 values together and pass thru activation function to get new activation value \n\nTraining: \n\n\t 3 sets of weights to update: W, U, V (weights from hidden to output layer)\n\t 2 pass algorithm: 1) forward inference thru network\n\t 2) go in reverse, compute gradients as we go&error terms to use in each hidden layer\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\nRNN Language Models: \n\n**process input seq 1 at a time; no limited context problem because can look up seq of words of any length \n\n\t forward inference is the same as RNN with embeddings as input and using E matrix\n\t use corpus of text for training data\n\t cross-entropy is loss function\n\t teacher forcing is used \n\n**V is also a set of word embeddings just like E, so we can use weight tying if we want to reduce # of params\n \n\n## SLP Chapter 6.1 Lexical Semantics\n\nLexical semantics: study of word meaning \n\n\t lemma: word that is a form of other words (i.e. mouse is lemma of mice)\n\t wordforms are the other words that are similar to the lemma\n\t word sense: every meaning of word (i.e. mouse can be animal, device) \n\t can be represented using WordNet tree \n\n3 dimensions of affective meaning: \n\n\t valence: pleasantness\n\t arousal: intensity of emotion\n\t dominance: degree of control exerted\n\n\n## SLP Chapter 6.2 Vector Semantics\n\nVector semantics: \n\n1) tf-idf: meaning of word defined by function of counts of nearby words, results in sparse vectors \n\n2) word2vec: results in dense vectors \n\n3) cosine: use embeddings to compute semantic similarity between 2 pieces of text\n\n\n## SLP Chapter 6.3 Words and Vectors\n\nco-occurence matrices represent how often words occur together \n\n\n1) term-document matrix \n\n\t rows: words in vocab, columns: documents\n\t good for finding similar documents using similar column vectors \n\n2) term-term matrix \n\n\t aka word-word or term-context\n\t rows: words in vocab, columns: words in vocab \n\n** each cell is # of times row word appeared in same context window (i.e. document, window of size 2) as column word\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\ncosine: high value means very similar, 0 means completely dissimilar \n\n\t problem: dot product favors longer vectors, so we normalize it\n\t cosine similarity: cos(θ) = a•b / (|a||b|); -1 means opposite, 1 means exactly same\n\t vector length: |x| = sqrt(sum of the squared values of each number in the vector)\n\t unit vector: divide a vector by its vector length\n\n\n## SLP Chapter 6.8 Word2vec\n\nembeddings are shorter versions of the word vectors used in previous models and they are dense \n\nDense is better in NLP than sparse because: \n\n\t fewer weights for classifier to learn, less overfitting, better capture synonymy \n\n\nWord2vec: fast, efficient to train, easily available with pretrained embeddings \n\n\t uses static embeddings\n\t instead of counting how often a word occurs near another word, \n\t train a classifier to predict if a word is likely to show up near another word \n\t the weights we learn from this will be the embeddings for each word \n\t words close to each other will have more similar embeddings \n\n\nSkip-Gram: \n\n\t treat each target word and neighboring context word as positive examples\n\t randomly sample other words to get neg. examples\n\t use LR to train classifier for positive vs. negative\n\t use learned weights as embeddings\n\t initialize 2 embeddings - W for word and C for context\n\t classifer assigns prob. based on how similar context window is to target word\n\t sigmoid applied to dot product of embeddings of target word with context word \n\n\nSkip-Gram Algorithm \n\n\t assign a random embedding to each word in vocab\n\t iteratively shift each word's embedding to be more like the words it is near\n\t maximize similarity of word + positive contexts and minimize word + neg contexts \n\nkey points: SG learns 2 embeddings per word (target and context), can just add them together\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\nSemantic properties of embeddings: \n\n\t first-order co-occurence: 2 words are near each other in corpus (i.e. wrote, book)\n\t second-order co-occurence: 2 words have similar neighbors (i.e. wrote, said, remarked)\n\t parallelogram model: uses analogies --> predicted b*=argmin distance(x, a*-a+b)\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\nBias in Embeddings: \n\n\t allocational harm: system allocate jobs/credit unfairly to groups (i.e. hiring bias)\n\t embeddings amplify bias\n\t representational harm: system demeans/ignores certain groups\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\nEvaluating Vector Models: \n\n\t similarity: algorithm's word similarity scores vs human's similarity ratings \n\nAll embedding algorithsm suffer from inherent variability, so we should train multiple embeddings\nand use bootstrap sampling over documents\n\n\n## Module 14 Lecture Notes\n\nWord meaning representation should encode: \n\n1) synonyms, antonyms, connotations, semantic roles, support for entailment \n\n2) entailment: mathematically well-undestood, powerful for logical operations, knowledge comes from somewhere \n\nTF-IDF: \n\t term frequency: how often word occurred in a document\n\t inverse document frequency: 1/# of documents word occurred in \n\nCurse of dimensionality: if vocab is too large, too many params to estimate \n\n\\Language modeling learns a function that returns the joint probability \n\n\t issues: curse of dimensionality, n-gram models are bad at generalizing\n \n\n## Module 14 Definitions\n* **Teacher forcing** - always give model correct next word to use as input for next step instead of using best prediction from previous time step\n* **Weight tying** - E and V matrices are similar, so just use a single set of embeddings instead. E = V\n* **Distributional hypothesis** - words that occur in similar contexts have similar meanings\n* **Vector semantics** - interprets word meaning by learning embeddings to explain distr. hypothesis\n* **Polysemous** - a word that has multiple word senses\n* **Word sense disambiguation** - figuring out which word sense is being used in a context\n* **Propositional meaning** - when 2 words are direct synonyms\n* **Principle of contrast** - difference in linguistic form can change the meaning of word (i.e. H20 in science, water for hike)\n* **Similarity** - can use humans to judge\n* **Relatedness/assocation** - i.e. coffee and cup, scalpel and surgeon. typically part of same semantic field\n* **Semantic field** - set of words that have structured relationship to each other. use in topic modeling\n* **Lda** - unsupervised learning on text to get associated words\n* **Semantic frame** - set of words that denote the perspectives in an event (i.e. buy and sell). important for question answering\n* **Connotations** - aspects of a word's meaning that are related to the writer/reader's emotions/sentiment/etc\n* **Information retrieval** - finding the document that best matches the query\n* **Skip-gram with negative sampling** - aka word2vec\n* **Static embeddings** - method learns 1 fixed embedding for each word\n* **Contextual embeddings** - vector for each word is different in different contexts\n* **Self-supervision** - unsupervised learning where withhold some information about data, and task network with predicting it\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": "ea993326-f2fa-44b4-8155-5ac24e009c9b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory: choose among actiins based on desirability of their immediate outcomes (episodic) \n\nWhy doesn't MEU solve the AI problem? \n\n\t MEU formalizes what an agent should do but doesn't operationalize it. \n\t To use MEU, we have to estimate probability distribution and utility function \n\t which reflects perf. measure. \n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nMEU is not the only rational way to make decisions. \n\nA ≻ B: prefer A over B \n\nA ~ B: indifferent between A and B \n\nA ≻~ B: prefers A over B or is indifferent between them \n\n\nL = [p1, S1; p2, S2;...pn,Sn] || probabilities, outcomes \n\n\nAxioms of Utility Theory -- if these violated, irrational behavior \n\n<b>Orderability:</b> agent can't avoid deciding. so exactly 1 of 3 above principles holds \n\n\t Given two lotteries, a rational agent must either prefer one or be indifferent \n\n<b>Transitivity:</b> A ≻ B and B ≻ C --> A ≻ C \n\n<b>Continuity:</b> A ≻ B ≻ C, then there is a probability p where agent is indifferent between \n\nlottery for A and C and sure chance of getting B. [p, A; 1-p, C] ~ B \n\n<b>Substitutability:</b> if agent indifferent between 2 lotteries (A and B), agent is indifferent between: \n\n[p, A; 1-p, C] ~ [p,B;1-p,C] \n\n<b>Monotonicity:</b> if A ≻ B, agent prefers lottery with higher probability for A: \n\n[p, A; 1-p, B] ≻ [q,A;1-q,B] (p>q) \n\n<b>Decomposability:</b> we can reduce compound lotteries: \n\n[p, A; 1-p, [q,B;1-q,C]] ~ [p, A; (1-p)q, B; (1-p)(1-q), C] \n\n\nConsequences of Axioms \n\n<b>Existence of Utility function</b>: U(A) > U(B) if and only if A ≻ B. \n\nU(A) = U(B) if and only if A ~ B. \n\n<b>Expected Utility of a Lottery</b>: sum of probability of each outcome * utility of outcome \n\n\nJust because there is a utility function, doesn't mean agent is necessarily maximizing it\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nIf we normalize the utilities, we can see what probablity (p) to assign to the min utility \n \nand (1-p) to max utility so that p equals the value of the outcome we're looking at. \n\nTo find the value that people place on their lives: micromort, QALY \n\nMoney has a monotonic preference (always prefer more). Utility function is NOT monotonic \n(i.e. many people would turn down a gamble for more money compared to get less money for sure ) \n\nRisk-averse agents have a concave down utility curve. Risk-neutral have linear curve. \n\n\nAllias paradox: \n\nDescriptive theory shows a different way of people choosing between 2 options to get money than normative theory. \n\nThis could be because of the certainty effect -- people want the upside that they are guaranteed of rather \n\nthan a higher one that they have a chance, not for sure, of getting \n\nEllsberg paradox: \n\n\t people have ambiguity aversion -- they would rather go with a known chance than \n\t a chance that is unknown \n\n\n\n## AIMA Chapter 17.1 Sequential Decision Problems\n \nMarkov Decision Process (MDP): a sequential decision problem for a fully observable, stochastic environment with \n\na Markovian transition model and additive rewards.\n\t has: set of states, actions, transition model, reward function, initial state || terminal state is optional\n\t the solution is a policy - there can be multiple optimal policies.\n\t even if same policy executed muliple times, could get different state/action sequence\n\t can solve using DP \n\n\nIf we use discounted utilities w/ infinite horizons, optimal policy is independent of starting state \n\n\nWhy do we use additive discounted rewards? \n\n\t value near-term reward smore than rewards later in the future\n\t economic rewards are more valuable now than later\n\t rewards may never arrive the longer you wait \n\t if you prefer one future to another starting tomorrow, you should still prefer that \n\t future today so you need additive discounting for that\n\t removes infinities \n\n\nThe optimal policy is the argmax_a Q(s,a) \n\nIf we represent MDPs with a table, the table will be sparse. Use DDNs: \n\n\t set of state features\n\t set of possible actions\n\t 2-stage decision network with chance nodes for each feature (at time 0 and time 1)\n\t decision node for action taken\n\n\n\n## AIMA Chapter 17.2 Algorithms for MDPs\n\nOffline Algorithms for solving MDPs:\n\n<b>Value Iteration</b>: start with random initial utility values and keep updating until equilibrium \n\n\t update step is called Bellman update\n\t apply update at same time to all states\n\t exponential time O(S^2 A) to converge to equilibrium \n\n<b>Policy Iteration</b>: alternate between policy eval and policy improvement \n\n\t Policy Eval: given a policy, calc the utility of each state if we execute policy. \n\t O(S^2) per iteration\n\t Policy Improvement: calculate a new MEU policy based on utilities. it is optimal\n\t terminates when policy improvement causes no change in utilities \n\n\nWhat insight leads from value iteration to policy iteration? \n\n\t We can get an optimal policy with an inaccurate utility function for value iteration \n\n\nHow does the Bellman equation help us leverage dynamic programming? \n\n\t Bellman equation lets us express the utility of a state recursively as utilities of \n\t its neighbors \n\n\nSmall state spaces: policy eval is the most efficient \n\nLarge state spaces: do modified policy iteration \n\n\nasynchronous policy iteration: \n\n\t always converges to optimal policy\n\t can design more efficient heuristic algorithms \n\n\nlinear programming: \n\n\t Utility of each state (U(s)) is a variable\n\t minimize U(s) for each state where U(s) >= sum of neighboring state utilities\n\t not as efficient as using DP for solving MDPs \n\n\nReal-time dynamic programming: \n\n\t set a bound on error in utilities using an expectimax tree\n\t find depth in tree where sum of rewards below this depth is less than error bound\n\t this depth is how we can get close to optimal decisions\n\t if large branching factor, take avg of samples of outcomes from action to approx\n\n\n## Module 8 Lecture Notes\n \nWhat is the difference between the utility function and performance measure of an agent? \n\n\t performance measure gives a score for a history\n\t utility function applies to the very next state; it can guide future actions \n\nQ-Function = action-utility function \n\nIf we assume stationary preferences, we can only define utilities as additive or discounted \n\nTo avoid infinite utilities: \n\n\t finite horizon, discounting, absorbing state (guarantee we reach terminal state)\n\n \n\n## Module 8 Definitions\n* **Utility function** - desirability of a state -- a number\n* **Expected utility** - average utility of all possible outcomes of an action, weighted by their probability\n* **Maximum expected utility (meu)** - agent picks action with max exp. utility\n* **Lottery** - set of outcomes for each action\n* **Ordinal utility/value function** - if deterministic, agent only needs ranking of states, not actual values\n* **Preference elicitation** - give humans choices and observe preferences to form utility function\n* **Normalized utilities** - scale of 0 to 1\n* **Standard lottery** - [p, U_min; 1-p, U_max]\n* **Transition model** - outcome of each action from every state. transitions are Markovian\n* **Markovian** - when we don't care about history -- probability of s' from s only depends on s\n* **Environment history** - sequence of states and actions\n* **Policy** - specifies what agent should do for any state it reaches\n* **Optimal policy (π*)** - gives us highest expected utility\n* **Finite horizon** - after a fixed time, the game is over. this leads to nonstationary policies\n* **Infinite horizon** - no fixed deadline, so optimal action based on current state. this leads to stationary policies\n* **Additive discounted rewards** - utility of a history is sum of all previous rewards R0 + discount*R1 + discount^2*R2...\n* **Discount factor** - between 0 and 1\n* **Additive rewards** - when discount factor = 1\n* **Proper policy** - guaranteed to reach a terminal state eventually. can use discount = 1\n* **Average reward** - can be used to compare infinite sequences. take avg. reward at each time step\n* **Bellman equations** - give us the utilities for states based on exp. utility of future state sequences\n* **Q-function q(s,a)** - expected utility of taking action a in state s. find the max Q(s,a) to get utility of s\n* **Potential** - (discount factor * potential_s') - potential_s <-- this is the gradient of potential\n* **Shaping theorem** - all policies are optimal for any Reward = (discount factor * potential_s') - potential_s\n* **Dynamic decision networks (ddns)** - factored representations -- good for modeling large state space problems\n* **Policy loss** - this most utility an agent can lose by executing a policy instead of optimal policy\n* **Modified policy iteration** - utility of state in next policy is the sum of utilities of neighboring states\n* **Asynchronous policy iteration** - apply policy improvement/value iteration to a subset of states at each step\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Markov reward process is an MDP but only 1 possible action. \nEach bandit problem has multiple arms. Each arm is independent and is a MRP.\n\nOne-armed bandit -- idea is that 1 arm gives different rewards and another gives constant. \n\n\t have to decide when you want to switch to the constant rewards (if ever) \n\n\nBernoulli bandit -- each arm gives either 0 or 1 rewards with a fixed but unknown probability \n\nBandit policies \n\n\t upper confidence bound heuristic: get a confidence interval for the value of each arm. choose arm with highest\n\t upper bound on CI \n\t Thompson sampling: choose arm randomly based on probability that arm is optimal given samples so far \n\n\nFor a BSP, the optimal policy may have actions that are suboptimal for some of the arms. Unless discount factor \n\nis 1 (no cost for delaying rewards to any MDP), this will happen \n\n## AIMA Chapter 22.1 Learning from Rewards\n Reinforcement learning vs MDPs: \n\n\t in RL, agent is not given the MDP; it is in the MDP. \n\t in RL, agent doesn't know transition model, rewards\n\t in both, the values for the transition model are not known in advance \n\t MDPs are offline learning but RL is online learning\n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Policy evaluation vs Passive RL: \n\n\t Passive RL agent doesn't know transition model&reward function, but policy eval does \n\n\n<b>Direct utility estimation:</b> \n\t compute values for each state under the policy by averaging the sum of discounted rewards that occur each time state visited\n\t ignores the connections between states, so misses opps. for learning\n\t converges very slowly \n\n\n<b>Adaptive Dynamic Programming:</b> takes the transition model and observed rewards and calculates utility of each state \n\n\t use heuristics (i.e. prioritized sweeping) to improve speed \n\t builds on direct utility estimation to use the Bellman equations \n\n\n<b>Temporal Difference Learning:</b> use transitions that have been observed to adjust utilities of observed states \n\n\t model-free way to do policy eval\n\t U*(s) = U(s) + learningRate*[Reward + discountRate*U(s') - U(s)]\n\t this is adjusting the utility estimates to an equilibrium\n\t **NO NEED for transition model** \n\t learns utilities, but not q-values, so hard to turn into a new policy\n\t slower than ADP&higher variability, but simpler&less computation per observation\n\t ADP adjusts state to agree with <b>all</b> successors\n\t TD adjusts state to agree with <b>observed</b> successor \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Active RL: \n\nagent learns full transition model, not just model associated with fixed policy (passive RL).\nnext, agent decides action based on utility function using Bellman equations \n\n\n\nWhat is wrong with greedy agents? \n\n\t learned model!=true environment so what is optimal in model might be suboptimal in env\n\t need to trade-off between exploitation and exploration\n\t use GLIE to try each action in each state unlimited times to ensure optimal action \n\n\nGLIE: \n\n\t give more utility to more unexplored state-action pairs \n\n\nThree approaches to find a reasonably accurate true model: \n\n\t Bayesian RL\n\t Robust control theory: get worst possible result for any action&find which action has best one\n\t problem: very conservative behavior\n\t Use human knowledge to determine constraints and enforce them \n\n\nTD Q-Learning: \n\n\t doesn't need a transition model and P(s'|s,a) \n\n\nQ-Learning vs SARSA: \n\n\t Q-learning gets Q-value from the best action in s' but SARSA lets action happen \n\t and then backs up Q-value for that action\n\t if agent always picks best Q-value action, then Q-Learning = SARSA\n\t Q-Learning: off-policy. SARSA: on-policy\n\t Q-learning can learn optimal Q-function Q w/o ever executing optimal policy\n\t Q-learning more flexible, SARSA better if policy has other agents involved\n\t both learn optimal policy but slower than ADP \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n \nUtility = weights*features. RL approximates these weights in function approximation. \n\nFunction approx allows us to represent utility/Q for large state spaces + inductive generalization \n\n\t inductive generalization: agent can generalize from visited to unvisited states\n\t FA generalizes by changing utilities for all states based on each \n\t observed transition between states \n\nDirect utility estimation: for each state, extracts sum of rewards from state until termination \n\nCan apply Widrow-Hoff Rule (gradient descent) to DEU, TD Learning, Q-Learning \n\n\nCatastrophic forgetting: car learns how to stay in middle of the road perfectly but then abruptly \n\nveers off the side. Use experience replay to apply Q-learning to samples of the experience. \n\n\nFully observable state -- learning the model is supervised problem \n\nPartially observable state -- Bayesian networks, NN, etc \n\n\nUse Deep NN because you may not be able to come up with all features yourself/linear approx isn't good enough \n\n\t obstacles: difficult to get good performance, unpredictable with variance in test/train data \n\n\nReward shaping helps us deal with sparse rewards and speeds up learning but have to be careful of not maximizing \n\npseudorewards instead of rewards. \n\n\nHierarchical RL: start with partial problem that outlines structure of agent's behavior. \n\nBy associating a function with each choice, program learns function to decide which choice. \n\n\n\n## Module 9 Lecture Notes\n \nMDP: \n\n\t A set of states, Initial states, Terminal states, Transition Model, Reward function \n\nModel-Free Learning: \n\n\t no transition model. at each action, compare actual vs expected outcome. \n\t so we track utility and nothing else \n\nWe can force exploration by assigning low prob to acting randomly and high prob to acting on current policy \n\n\n\n## Module 9 Definitions\n* **Exploitation** - use the best action that has been found so far\n* **Exploration** - get more information by looking at unknown states/actions. could lead to higher rewards\n* **Regret** - difference between achieved rewards and optimal rewards. relative goodness of exploration procedures\n* **Bandit problems** - has index function. overall are an MDP\n* **One-armed bandit** - 1 arm produces different rewards each time. another gives the same reward each time. So pulling the first arm--you give up reward on other arm\n* **Stopping time** - when you stopped pulling the arm\n* **Gittins index** - equation defining the value for the arm that gives same reward each time (lambda)\n* **Selection problem** - *no index function*. don't have to minimize test failures. focus on getting a good decision ASAP\n* **Bandit superprocess (bsp)** - each arm is a MDP instead of just a MRP. i.e. multitasking\n* **Opportunity cost** - how much utility is given up by not devoting that amount of time to another arm\n* **Dominating policy** - policy where an arm's optimal policy is not affected by opportunity cost\n* **Reinforcements** - rewards\n* **Reinforcement learning** - through interactions with world, agent gets reinforcements based on how it is performing. want to maximize rewards\n* **Sparse reward** - has little to no information. i.e. chess, racing\n* **Intermediate reward** - can be calculated based on a point won, run scored, etc. i.e. tennis, cricket\n* **Model-based rl** - uses a transition model to interpret rewards and act. model could be known or unknown. learn utility function\n* **Model-free rl** - no transition model involved\n* **Action-utility learning** - Q-learning. get the expected utility of taking an action\n* **Q-learning** - learn a Q function: Q(s,a). expected reward from state s onward if action a. find action with highest Q.\n* **Policy search** - finding policy performance until performance stops changing\n* **Passive rl** - fixed policy in fully observable environment. agent learns utilities of each state\n* **Direct utility estimation** - expected reward from the current state and onward\n* **Active rl** - agent themself decides the actions to take\n* **Adaptive dynamic programming** - learns transition model and uses DP to solve MDPs\n* **Prioritized sweeping heuristic** - adjust states that have <b>likely</b> successors that have just had large changes to their utilities\n* **Greedy agent** - takes action that it currently thinks is optimal. not always the right choice\n* **Glie** - Greedy in the limit of infinite exploration\n* **Irreversible actions** - no set of actions can restore us to the state before the irreversible action\n* **Absorbing state** - no action can cause a reward\n* **Bayesian rl** - prior: hypothesis of true model (h). P(h|e). e is the observations so far\n* **Robust control theory** - H is possible models, no probabilities. Optimal robust policy: best outcome in worst case of H\n* **Sarsa** - state, action, reward, state, action. Similar to Q-learning\n* **Off-policy algorithm** - determines worth of action and assumes we stop using current policy\n* **On-policy algorithm** - determines worth of action and assumes we keep using current policy\n* **Function approximation** - construct an approximation of true utility/Q function\n* **Widrow-hoff/delta rule** - gradient descent for linear regression -- updates weights based on diff between target&output\n* **Catastrophic forgetting** - neural network forgets previously learned info when it gets new info\n* **Experience replay** - store agent's experiences at each timestep so they can be used in learning\n* **Credit assignment** - problem of it being hard to measure action's influence on future rewards\n* **Reward shaping** - add additional (pseudo) rewards for making progress, not just on actions\n* **Hierarchical rl** - breaking down action sequences into smaller sequences to improve learning\n* **Joint state space** - each state consists of physical state and machine state\n* **Policy** - function mapping states to actions\n* **Correlated sampling** - each program has the same options instead of doing random sampling\n* **Online learning** - actually take actions in the real world\n* **Contraction** - Part of the proof of convergence for the value iteration algorithm\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\nHard to use only logic because: \n\n\t laziness (too hard to use so many rules)\n\t theoretical ignorance (there will never be a complete set)\n\t practice ignorance (could be uncertain about a rule) \n\nTherefore, agent can only provide a *degree* of belief \n\n\nTheory of probability: way to summarize uncertainty from ignorance and laziness \n\nUtility of a state is relative to an agent \n\nDecision theory says agent is only rational if it chooses action with highest exp. utility \n\n\n\n## AIMA Chapter 12.2 Basic Probability Notation\n \nSet of possible worlds is mutually exclusive and exhaustive \n\n\t P(a|b) = P(a and b)/P(b) \n\n\t Product rule: P(a and b) = P(a|b) * P(b) \n\t Chain rule: P(a,b,c) = P(a)P(b|a) P(c|a,b) \n\t chain rule: N! ways to apply it to N boolean variables \n\n\n<b>inclusion-exclusion principle:</b> \n\n\t P(a or b) = P(a) + P(b) - P(a and b)\n \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n\nFull joint distr. tables are rarely used because domains usually too big\n \n\n## AIMA Chapter 12.4 Independence\n\n<b>Independence:</b> \n\n\t P(X|Y) = P(X) ; P(Y|X) = P(Y) ; P(X,Y) = P(X)P(Y)\n\t ind. assertions can reduce the size of domain and complexity of inference problem\n\t size of representation grows O(2^n)\n \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n\n<b>Bayes Rule</b>: P(Y|X) = P(X|Y)P(Y) / P(X) \n\n\t LHS is diagnostic direction, RHS is causal direction\n\t can add normalization constant in numerator to make entries on LHS sum to 1\n\t diagnostic knowledge is more fragile than causal knowledge \n\n<b>Conditional Independence</b>: \n\n\t P(X,Y|Z) = P(X|Z)P(Y|Z)\n\t P(X|Y,Z) = P(X|Z) and P(Y|X,Z) = P(Y|Z)\n\t cond. indp. can allow prob. systems to scale up\n\t they are more available than absolute indp. assertions\n\t size of rep grows O(n)\n \n\n## AIMA Chapter 12.6 Naive Bayes Models\n\n<b>Naive Bayes</b>: assumes input variables are independent \n\n\t text classification; take proportion of documents that word is in\n\t not good to use for problems where posterior prob. accuracy matters (medical)\n\n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n\n\n\n## SLP Chapter 3.1 N-Grams\n\nUse ngrams to approximate the history instead of using the entire history \n\nngram: only the previous n-1 words are the history \n\n\t markov assumption: prob of word is dependent only on some # of previous words \n\nTo estimate probabilities, use MLE: \n\n\t compute count of bigram -- numerator\n\t compute total number of times history occurred -- normalization (denominator) \n\t relative frequency: numerator/denominator \n\t problems: zeros, out of vocab words \n \n\n## SLP Chapter 3.2 Evaluating Language Models\n \n80% train, 10% development, 10% test \n\nCan only compare perplexities of models if they use identical vocabularies \n\nIntrinsic perplexity improvement doesn't guarantee extrinsic improvement in performance \n\n\n\n## SLP Chapter 3.3 Sampling sentences from a language model\n \nSampling from a language model: \n\n\t generate sentences based on likelihood defined by model\n\t this way, we get sentences with higher prob based on model\n\t allows us to visualize what kind of knowledge a language model has\n\n\n## SLP Chapter 3.4 Generalization and Zeros\n\nImplications of ngram models being dependent on training corpus: \n\n\t probabilities encode specific facts about training corpus\n\t as N goes up, ngrams do better job of modeling training corpus \n\nHow to improve on pure statistical models for language modeling: \n\n\t genre: training corpus should have documents from same genre\n\t dialect/variety: training corpus documents should have same dialect as task \n\n\nSparsity is usually another issue -- you get zero probabilities \n\n\t can turned an open vocab problem into closed vocab problem\n\t replace unknown words with <UNK>\n\n\n\n## SLP Chapter 3.5 Smoothing\n\nWhat to do with words that are in vocab, but appear in test set with unseen context?: \n\n\t Laplace smoothing: add 1 to all ngram counts\n\t add-k smoothing: instead of add 1, add k (fraction) to all ngram counts\n\t add-k smoothing -- the k can be chosen using a development set\n\t backoff: if don't have sufficient evidence w/ ngram, go to n-1 gram, etc until get some counts\n\t interpolation: mix prob. estimates from all n, n-1, etc grams\n\t interpolation -- add up lambda*estimate for each ngram \n\nKatz backoff: when you backoff, discount the higher-order ngram counts \n\nDiscount ratio: smoothed count / unsmoothed count\n \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n\nHow to create efficient language models? \n\n\t Bloom filter: space-efficient data structure to test if element is in a set\n\t pruning ngrams that have greater than a certain count\n\t stupid backoff: don't discount the higher-order ngram counts\n\t stupid backoff -- if higher order has zero count, just move on to n-1\n\n\n## Module 10 Lecture Notes\n\nSize of joint prob distr with n variables, d domain size: d^n \n\nProbabilistic Language Modeling: \n\n\t model that computes probability of sentence/seq of words/word \n\n\n\n## Module 10 Definitions\n* **Belief state** - representation of all possible states that agent can be in\n* **Rational decision** - depends on 1) relative importance of goals and 2) likelihood of achieving them\n* **Utility theory** - every state/sequence of states has a degree of usefulness to agent\n* **Decision theory** - probability theory + utility theory\n* **Meu (maximum expected utility)** - choose action with highest exp.utility, avg over all possible outcomes\n* **Prior probability** - P(event)\n* **Conditional/posterior probability** - P(event|another event)\n* **Bernoulli** - outcome is binary\n* **Probability distribution** - assign a prob to every possible value of a random variable\n* **Categorical distribution** - finite, discrete range of values\n* **Probability density function** - used with continuous variables\n* **Joint probability distribution** - usually expressed using a table. all prob sum to 1\n* **Probabilistic inference** - computing posterior probabilities\n* **Marginal probability** - probability of an event occuring (sum an entire row/col in a joint prob table\n* **Independence** - aka absolute independence and marginal independence\n* **Syntactic** - relating to the use of language\n* **Log probabilities** - used so we don't get small numbers, since probabilities between 0 and 1. take e^(sum of log probs)\n* **Extrinsic evaluation** - apply a language model in an actual application and measure how the application improves\n* **Intrinsic evaluation** - measures model quality using metrics, not an application\n* **Perplexity** - measures performance of language model -- lower is better\n* **Branching factor** - number of words that could follow a word\n* **Weighted average branching factor** - aka perplexity, since you take a weighted average for each word\n* **Closed vocabulary** - test set only contains words from a vocabulary\n* **Open vocabulary** - test set can contain unknown words that aren't in vocabulary\n* **Discounting** - lowering some non-zero counts to get the probability that will be assigned to zero counts\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n\nBayesian Network: DAGs \n\n\t node: random variable\n\t directed arrows: X -> Y means X is parent of Y\n\t each node has P(X|Parents(X)) \n\n\n<b>Conditional Probability Table (CPT):</b> only used for discrete variables \n\n\t local probability info attached to each node\n\t **specified based on the probability distribution of JUST the parents\n\t each row contains conditional probability of each conditioning case\n  \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n\nsyntax: DAG with local prob. info at each node \n\nsemantics: how the syntax corresponds to the joint distribution \n\nchain rule: holds for any set of RVs \n\n\t P(x1...xN) = P(xN|xN-1...x1)*P(xN-1|xN-2...x1)...P(x2|x1)*P(x1) \n\n\nBayes network is correct representation of domain if each node is conditionally ind of predecessors: \n\n\t nodes: determine set of RV and then order them\n\t links: chose a minimal set of parents for each node and insert a link. Write CPT \n\n\nBayes nets: always acyclic and always don't have redundant probability values \n\n\t definition: describes models using conditional probabilities\n\t semantics: topology (graph) + local conditional probabilities for each node\n\t more compact that full joint probability distr. because locally structured \n\t use causal over diagnostic models to make the ordering better\n\t size: if boolean variables: 2^N. if nodes have up to k parents: O(N*2^k+1) \n\n\nBayes nets don't HAVE to be causal; can have arrows represent correlation instead \n\n\nD-separation: \n\n\t subgraph consists of X,Y,Z -- ancestral subgraph\n\t add links between any nodes that share a common child -- moral graph\n\t replace directed links with undirected links\n\t if Z blocks all paths between X and Y, Z d-separates X and Y\n\t this also means X is conditionally independent of Y given Z \n\nA variable's Markov blanket d-separates it from all other variables. \n\n\nNoisy logical relationships assumptions for the model: \n\n\t all possible causes are listed (if not, leak node)\n\t inhibition of a parent is indp. of inhibitions of other parents to cause child node to be true\n\t O(k) parameters instead of O(2^k) \n\n\nHandling continuous variables: \n\n\t discretization: divide into fixed set of intervals\n\t define using a standard prob. density function \n\n  \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n \nQuery can be answered using a Bayes Net by summing the products of all the cond. prob. \n\n\nEnumeration-Ask Algorithm: \n\n\t DFS, left to right recursion\n\t space complexity: linear, time: O(2^n)\n\t contains repeated subexpressions, which is wasteful \n\n\nVariable Elimination Algorithm: \n\n\t expressions are evaluated right to left\n\t removes variables that aren't ancestor of query or evidence variable\n\t uses DP, so intermediate results are stored\n\t factor for P(m|a) = vector with P(m|a) and P(m|¬a)\n\t better than enumeration algo \n\n\nComplexity of CSPs and Bayes nets are closely connected: \n\n\t tree width: bounds CSP complexity but is also applicable to Bayes \n\n\nClustering: \n\n\t put network into polytree form using clustering\n\t use constraint propagation \n\t neighboring nodes must agree on posterior probability of variables that are shared\n\n\n## Module 11 Lecture Notes\n\nA ⫫ B means A and B are independent \n\nA ⫫ B|C means that A and B are conditionally independent given C \n\nD-Separation has 3 cases: causal chain, common cause, common effect \n\n\t to see if 2 variables are independent, check all undirected paths between them\n\t A causal chain is inactive if not all tuples are active \n\t if a node is observed, then it is active\n\t if one or more paths is active, then independence not certain\n\t if all paths are inactive, then independence is certain\n\n\n## Module 11 Definitions\n* **Conditioning case** - possible combo of values for a the parent nodes of a node\n* **Topological order** - order of DAG\n* **Locally structured** - each subcomponent only interacts with a bounded number of components. Linear complexity growth\n* **Markov blanket** - parents, children, children's parents. a variable should be conditionally independent of all other nodes given this\n* **Deterministic node** - value is specified exactly by the values of parents. no uncertainty\n* **Context-specific independence** - variable is cond. indp. of SOME parents given CERTAIN VALUES of other parents\n* **Noisy-or relation** - generalize OR but allow uncertainty for each parent to cause child to be true\n* **Leak node** - covers any other causes (parents) that might not be specified\n* **Hybrid bayesian network** - network with both discrete and continuous variables\n* **Linear-gaussian cond. distr.** - child-Gaussian distr. mean varies linearly with parent. SD is fixed\n* **Conditional gaussian** - discrete variables as parents of continuous variables\n* **Hidden variables** - ensure network is sparse enough w/ manageable # of parameters. in between input and output\n* **Factor** - matrix indexed by values of its argument variables\n* **Pointwise product** - multiply 2 functions to get another function by multiplying their values at each part of domain\n* **Polytrees/singly connected** - at most 1 undirected path in network. time and space complexity is linear\n* **Multiply connected** - >1 undirected paths. exponential time and space. \n* **Clustering/join tree** - join nodes to form cluster nodes to create polytree\n* **Meganode** - node resulting from a combo of nodes\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 19.1\n \nImproving agents using ML depends on: \n\n\t which component to improve, prior knowledge of agent, data and feedback \n\n\nComponents of agents: \n\n\t direct mapping from conditions on current state to actions\n\t ability to infer relevant properties of world from percept sequence\n\t info about how world evolves + results of agent's actions\n\t utility info about each state\n\t action-value info\n\t goals\n\t problem generator, critic, and learning element to allow for improvement \n\n\n3 types of learning: supervised, unsupervised, RL \n\n\n## AIMA Chapter 19.2\n\nHigh bias: linear functions, any function very fitted to data \n\nLow bias: piecewise linear function, decision trees, RF \n\nHigh variance: very high degree polynomial, KNN, RF \n\nLow variance: linear function \n\n\nWhy do we want simple hypothesis spaces: \n\n\t computational complexity too high with more complex\n\t hard to replicate using a complex one \n \n\n## AIMA Chapter 19.3\n \nDecision trees: \n\n\t split on attribute that makes the most difference in classification for an example\n\t entropy: -ΣP(v)*log_2P*v) ; sum over each possible value of variable v \n\t use pruning (remove nodes with low information gain) to combat overfitting \n\t H_o: no underlying pattern. use statistical sig test to decide what to prune \n\nWe can make decision trees more useful by handling: \n\n\t missing data\n\t continuous attr: use a split point (i.e. Weight > 160), IG Ratio, Equality test\n\t continuous-valued output attr: use a regr. tree \n\nOverall: \n\n\t easy to understand, scale to large datasets\n\t versatile with discrete/cont variables + class/regr\n\t can have suboptimal accuracy, unstable (adding 1 example can change everything) \n\n\nOverfitting becomes more likely as we increase # of attributes, less likely as we increase # of data points \n\nProblem with early stopping: can't recognize when we need a combo of attr. instead of 1 \n\n\n\n## AIMA Chapter 19.4\n \nModel selection starts with a small model which probably underfits and then iterates thru more complex models \n\n\t train error will decrease as complexity (# of tree nodes, # of params) increases\n\t val/test set error will decrease for a while but increase when overfitting begins\n\t want to minimze the loss function \n\nReasons the hypothesis differs from the real function: \n\n\t unrealizability, variance, noise, computational complexity\n\t noise -- could return different values of f(x) for x\n\t complexity -- if complex function, could be too much to search \n\nSimplifying models: \n\n\t regularization, feature selection \n\n\npopulation based training (PBT): \n\n\t uses random search to train models with dif hyperparam values\n\t then next set of models is trained based on previous hyperparam values\n \n\n## AIMA Chapter 19.5\n\nApproximately correct hypothesis: error is less than some E \n\n\t sample complexity: # of required examples \n\nTo obtain real generalization to unseen examples: \n\n\t bring prior knowledge for the problem\n\t get algorithm to return a simple consistent hypothesis\n\t focus on learnable subsets of hypothesis space \n\n\nDecision lists: \n\n\t if test succeeds, decision list specifies value to return\n\t if test fails, go to next test in list \n\t simpler than decision tree because they only branch in 1 direction \n\t but individual tests are more complex than decision trees \n\n \n\n## AIMA Chapter 19.6\n\nGradient descent: finds the minimum of a function\n\n\t start at any point in weight space, compute estimate of gradient, \n\t move in direction opposite to steepest slope\n\t repeat until converged\n\t weight = weight - alpha*derivative(Loss(w))\n\t alpha: step size/learning rate \n\n\nBatch gradient descent: \n\n\t gradient descent on all of the training data at once \n\n\nStochastic gradient descent: \n\n\t randomly sample 1 training example at each step and gradient descent on it\n\t minibatch: randomly sample M training examples at each step\n\t convergence of minibatch SGD not guaranteed\n\t SGD useful for when data is coming in 1 at a time and isn't stationary \n\n\nWith univariate LR, no overfitting. But multivariate LR, you can have overfitting: \n\n\t use regularization -- L1 (sum of abs values), L2 (sum of squares)\n\t L1 produces a sparse model (can set weights to 0) \n\n\nLinear functions can be used for classification too: \n\n\t decision boundary will separate 2 classes (if linear, then linear separator) \n\nPerceptron Learning Rule: \n\n\t if output correct, no change to weights\n\t if y is 1 but correct is 0, increase weight when x is pos, decrease when x is neg\n\t if y is 0 but correct is 1, decrease weight when x is pos, increase when x is neg\n\t applied to 1 point in training set at a time \n\nWe can soften the threshold function using logistic function so that we can account for \n\nsome points not being exactly 0 or 1. We can use the L2 loss function here. If data is \n\nlinearly separable, log. regr. takes longer to converge than lin. regr., but more predictable. \n\nIf data noisy/nonseparable, log. regr. better.\n \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n \nMultinomial Naive Bayes: \n\n\t estimate of correct class = P(d|c)P(c)\n\t dropped denominator: P(d); perform this for every class and get argmax\n\t generative model\n\t P(d|c): likelihood, P(c): prior \n\n\nBecause computing likelihood*prior is tough, we assume: \n\n\t bag of words -- position doesn't matter\n\t naive Bayes -- conditional probabilities are indp. of each other so we can multiply\n\n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n\nWhen we have unknown words (words only in test set, not training), remove them from test \n\nRemove stopwords (frequent words with no meaning)\n \n\n## SLP Chapter 4.3 Worked Example\n\n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n\nBinary multinomial Naive Bayes: \n\n\t remove all duplicate words so we just have max 1 count of word per doc \n\nTo deal with negation, add \"NOT\" prefix to each word after token of logical negation \n\nIf it's hard to estimate +/- sentiment because not enought training data, use sentiment lexicons: \n\n\t can add a feature for y/n if word is in + lexicon and y/n if word is in - lexicon\n \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n\nSpam detection: \n\n\t can predefine certain sets of words as features \n\nLanguage ID: which language a piece of text is: \n\n\t use character n-grams (i.e. 2-gram:'zw', 3-gram:'bya')\n\t use byte n-grams (i.e. everything is string of raw bytes (including space))\n\n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n\nNaive Bayes can be viewed as set of class-specific unigram language models: \n\n\t model for each class = unigram language model\n\n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n\nConfusion matrix uses system output + gold labels: \n\n\t accuracy not good for text classification -- bad metric w/ unbalanced classes\n\t precision: TP / (TP + FP)\n\t recall: TP / (TP + FN)\n\t F-measure: P*R*(B^2+1) / P*(B^2) + R | B > 1 favors recall, B < 1 favors precision\n\t B = 1 then F-measure = 2PR/(P+R) \n\n\nClassification for > 2 classes: \n\n\t macroaveraging -- when performance on all classes is equally important\n\t microaveraging -- dominated by more frequent class\n\n\n## SLP Chapter 4.8 Test sets and Cross-validation\n\nUse cross-validation if we don't have enough data to split into a dev/validation set as well\n\n\n## SLP Chapter 4.9 Statistical Significance Testing\n\nUse statistical sig. tests to see if a model is better than another model: \n\n\t H_o: effect size is less than or equal to 0 (A is not better than B)\n\t H_a: effect size is greater than 0 (A is better than B) \n\nHow do we compute probability? \n\n\t non parametric tests based on sampling\n\t create versions of experimental setup (i.e. lots of test sets)&then set threshold\n\t approximate randomization and boostrap tests are 2 common tests using in NLP \n\n\nPaired bootstrap test: \n\n\t Use bootstrapping to get N different test sets and then run models on each test set\n\t count number of times effect size is positive and divide by N to get p-value\n\n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n\nHarms from classifiers: \n\n\t Representational harms: system demeans a social group, so a sentiment classifier, \n\t for example, could be misrepresented\n\t toxicity detection: task of detecting hate speech, abuse, etc but can cause harm\n\t can incorrectly flag non-toxic sentences as toxic because of bias \n\n\nWe can mitigate this with a model card: documents an ML model with info about: \n\n\t training algo and data, eval data, intended use and users, model performance\n\n\n## Module 12 Lecture Notes\n\nconfidence form a classifier: how sure the classifier is of classification \n\n\t y which results in maximum P(y|x)\n\t weak calibration: higher confidence means higher accuracy\n\t strong calibration: confidence predicts accuracy rate \n\n\n\n## Module 12 Definitions\n* **Learning** - improving performance after observing the world\n* **Machine learning** - when the learning is done by a computer\n* **Induction** - specific observations -> general rule. might be incorrect\n* **Deduction** - accepted facts -> inference. correct if premises are correct\n* **Factored representation** - vector of attribute values\n* **Supervised learning** - observes input-output pairs and learns a function\n* **Unsupervised learning** - no feedback -- learn the patterns in input. i.e. clustering\n* **Rl** - learn from series of rewards and punishments\n* **Consistent hypothesis** - always evaluates to the right y-value for all training examples\n* **Best-fit function** - hypothesis is close to being the right y-value for all examples\n* **Bias** - tendence of hypothesis to deviate from expected value when average over training sets\n* **Variance** - amount of change in hypothesis due to changes in training data\n* **Decision tree** - function mapping attributes to a single output value\n* **Learning curve** - plot of the training/cross-validation error versus the sample size\n* **Entropy** - measures uncertainty of RV. more info = less entropy\n* **Information gain** - expected reduction in entropy\n* **Early stopping** - decision tree stops generating nodes when there is no good attr. to split on\n* **Equality test** - check if a variable is equal to a value or not\n* **Stationarity** - all future examples will be like the past. conditional prob table doesn't change over time\n* **I.i.d** - independent and identically distributed\n* **Error rate** - proportion of times that the hypothesis doesn't result in the actual label\n* **Loocv** - when k = n in k-fold cross validation\n* **Model selection** - chooses a good hypothesis space\n* **Model optimization/training** - finds the best hypothesis in the selected space\n* **Interpolated model** - model exactly fits the training data\n* **Loss function** - amount of utility lost by making the wrong prediction\n* **Realizable learning problem** - hypothesis space actually contains the true function\n* **Regularization** - adding a penalty to complex hypotheses\n* **Grid search** - try all combinations of values for hyperparameters\n* **Random search** - samples uniformly from all possible values if grid search will take too long\n* **Bayesian optimization** - treat finding optimal hyperparams as an ML model -- input (hyperparams), output(model perf)\n* **Computational learning theory** - AI, statistics, theoretical CS\n* **Probably approximately correct (pac)** - any hypothesis that is consistent with large training set will be PAC\n* **Pac learning** - an algorithm that returns hypotheses that are PAC\n* **Decision lists** - series of tests which are conjunctions of literals\n* **Convex** - loss function for every linear regre problem with L2 loss function. no local minima\n* **Epoch** - step covering all training examples\n* **Threshold function** - sets a threshold for what to classify a point as\n* **Bag of words** - unordered set of words with their position ignored. words + their frequencies in doc\n* **Generative model** - learns everything about classes in depth. uses distribution of data to return a probability\n* **Discriminative model** - can only learn the differences between classes, not all of the features\n* **Linear classifiers** - use linear combo of inputs. naive bayes, log regr\n* **Sentiment lexicons** - list of words pre-annotated with positive or negative sentiment\n* **Gold labels** - human-defined labels for classification\n* **Precision** - percent of items that system labeled + that are +\n* **Recall** - percent of items out of whole input that are correctly labeled\n* **Macroaveraging** - compute performance for each class, then average over classes\n* **Microaveraging** - collect decisions for all classes into 1 confusion matrix and then compute P/R\n* **Effect size** - number measuring strength of relationship between 2 models/variables\n* **P-value** - assuming H_o is true, probability of seeing effect size we saw or greater\n* **Paired tests** - compare 2 sets of observations that are aligned (model A and B on same data points)\n* **Bootstrapping** - random sampling with replacement\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n \nNaive Bayes is generative, LR is discriminative \n\n\t generative model will use P(d|c) and P(c) to get P(c|d)\n\t discriminative model will try to compute P(c|d) directly \n\n4 Components of ML system for classification: \n\n\t feature representation of input, classification function to compute predicted class\n\t objective function for learning, algorithm to optimize objective function \n\n\nLR learns vector of weights and bias term \n\nSigmoid maps 1/(1+e^(-z)) to range [0,1] \n\n\t z is dot product of weights and x-values + bias\n\t squashes outliers near 0 and 1\n\t differentiable\n\t 1-sigmoid(x) = sigmoid(-x)\n\t uses decision boundary to determine the class \n\n\nBoth NB and LR -- have to design feature interactions by hand \n\n\t can use feature templates to create a lot\n\t rep. learning reduces human effort&learns features automatically using unsup. learning \n\n\nLR vs NB; \n\n\t NB assumes indp. between features but LR is more robust to correlated features\n\t NB less accurate but good for short docs, easy/fast to train \n \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n \nLR measures difference between correct and predicted using loss/cost function \n\nOptimization algo used in LR is gradient descent\n\n\n## SLP Chapter 5.3 The cross-entropy loss function\n\nConditional MLE: \n\n\t choose weights and bias that maximize log(prob) of true y labels in training data\n\t this is the same as minimizing the cross-entropy\n\t cross entropy loss: -log likelihood\n \n\n## SLP Chapter 5.4 Gradient Descent\n\nGradient descent: finds minimum of function by moving in opposite direction of steepest rise in slope \n\n\t LR loss function is convex -- only 1 minimum, so GD works great\n\t gradient is weighted by learning rate -- higher rate means move faster @ each step\n\t multiple features-take partial derivative wrt each feature to get gradient vector \n\t gradient: x*(diff between true y and predicted y) \n\nSGD: \n\n\t computes gradient after each training example\n\t learning rate is a hyperparameter\n\t can be choppy, so minibatch \n\nMiniBatch GD: \n\n\t computes gradient over batches of training examples\n\t batch training: gradient over entire training set at once, but this is high cost\n\t minibatch: take m examples; this can be vectorized so it's faster\n \n\n## SLP Chapter 5.5 Regularization\n\nTo avoid overfitting, add regularization to the objective function: \n\n\t L2 ridge-Euclidean distance (shortest distance)||L1 lasso--Manhattan distance (sum of all real distances) \n\t L2 -- weights have Gaussian distribution || L1 -- Laplace prior on weights\n \n\n## SLP Chapter 5.6 Multinomial logistic regression\n\nsoftmax(z_i): e^z_i / sum(e^z_j) over all z \n\n\t use this instead of sigmoid when multinomial regr. \n\nMultinomial LR: \n\n\t need separate weight vectors and biases for each class\n\t loss function: sum(logs of each output class), weighted by probability of true class\n\t negative log likelihood loss\n \n\n## SLP Chapter 7.1 Units\n\n\n\nactivation functions: sigmoid, tanh, RELU \n\n\t tanh:(e^z-e^-z)/(e^z+e^-z);range[-1,1]; smoothly differentiable&maps outliers towards mean\n\t RELU: max(z,0) -- range[0,z]; close to linear but when negative, very different\n\t sigmoid: 1/(1+e^(-z)) -- range[0,1]; differentiable \n\nVanishing gradient: problem where gradients get too close to 0; avoidable with RELU\n\n\n## SLP Chapter 7.2 The XOR problem\n\nPerceptron: has binary output and a linear activation function \n\n\t properties: separability, convergence, mistake bound\n\t problems: noise, mediocre generalization, overtraining \n\t converges to minimum-error solution when LR decreases as training time increases \n\nXOR is not a linearly separable function so we need NN \n\n\t XOR: True if 1 statement is True, False if both statements are True\n \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n\nFeedforward NN/multilayer perceptrons: multilayer, outputs are passed from lower to higher level \n\n\t hidden layers taken weighted sum of inputs and apply non-linear activation function \n\t each layer is full-connected (takes all outputs from previous layer as inputs)\n\t hidden layer output (h) = activationfunction*(Wx+b)\n\t output layer: gives prob. distr. across the output nodes\n\t we use softmax to convert output vector from values --> probabilities\n\n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n\nNN for NLP: \n\n\t pretraining: instead of using human-made features, uses embeddings as inputs\n\n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n\nNeural language modeling: predicting words from prior word context: \n\n\t Neural vs N-gram: neural can handle longer histories, better generalization,\n\t more accurate, no smoothing\n\t But, n-gram is more interpretable, less complex, faster to train\n\t words are representated by their embeddings \n\nForward inference/decoding: \n\n\t running forward pass on NN to get output\n\t each previous word is represented as one-hot vector that \n\t is the length of every distinct word in vocab\n\t embedding matrix has column for every distinct word\n\t multiply one-hot vector * embedding matrix to get the embedding for the word\n\t all the previous words' embeddings make up the embedding layer\n\n\n## SLP Chapter 7.6 Training Neural Nets\n\nTraining neural nets: \n\n\t use cross-entropy loss as loss function; same process as LR\n\t use GD: compute partial derivative of loss function wrt each parameter\n\t it is hard to compute partial derivative for a NN with multiple layers, so \n\t we use error backpropagation\n\t Error back-propagation enables us to correctly update all layers in the neural network \n\nTo prevent overfitting \n\n\t dropout: randomly dropping some units during training\n\t tune hyperparams: learning rate, mini-batch size, model architecture (i.e. # of layers)\n\n\n## SLP Chapter 7.7 Training the neural language model\n\nTraining neural language model: \n\n\t classes are the words in the vocabulary, \n\t so prediction is the probability of word being next word\n\n\n## Module 13 Lecture Notes\n\nA perceptron converges to a minimum-error solution when learning rate decreases as training time increases \n\nWhy do we use non-linear activation functions in a multi-layer neural network? \n\nIf we used a linear activation function, the resulting network would be equivalent to a single-layer network \n\nSmoothness is crucial - you want a small change in weights and bias will produce small change in output \n\n\n\n\n## Module 13 Definitions\n* **Period disambiguation** - deciding if period is part of a word or the end of sentence\n* **Softmax regression** - multinomial regression\n* **One-hot vector** - 1 value is 1 and the rest are 0\n* **Hard classification** - only 1 class is the correct one\n* **Freeze** - keep embedding matrix E constant throughout training; can do this for some tasks\n* **Mira** - margin infused relaxed algorithm\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n\nIssues with FF NN: \n\n1) limited context: only have access to words in the window, but usually you need more \n\n2) using windows-hard to learn deeper meaning, especially if phrase has been split over windows\n \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n\nRecurrent Neural Network (RNN): contains cycle within network \n\n**the hidden layer's input is the output of previous layer WITH the value of hidden layer from previous timestep \n\n**this allows us to use information from earlier processing and give us variable lengths of prior context \n\nHow inference works? \n\n**multiple input with weight matrix W, hidden layer from previous timestep with weight matrix U \n\n**add the 2 values together and pass thru activation function to get new activation value \n\nTraining: \n\n\t 3 sets of weights to update: W, U, V (weights from hidden to output layer)\n\t 2 pass algorithm: 1) forward inference thru network\n\t 2) go in reverse, compute gradients as we go&error terms to use in each hidden layer\n\n\n## SLP Chapter 9.3 RNNs as Language Models\n\nRNN Language Models: \n\n**process input seq 1 at a time; no limited context problem because can look up seq of words of any length \n\n\t forward inference is the same as RNN with embeddings as input and using E matrix\n\t use corpus of text for training data\n\t cross-entropy is loss function\n\t teacher forcing is used \n\n**V is also a set of word embeddings just like E, so we can use weight tying if we want to reduce # of params\n \n\n## SLP Chapter 6.1 Lexical Semantics\n\nLexical semantics: study of word meaning \n\n\t lemma: word that is a form of other words (i.e. mouse is lemma of mice)\n\t wordforms are the other words that are similar to the lemma\n\t word sense: every meaning of word (i.e. mouse can be animal, device) \n\t can be represented using WordNet tree \n\n3 dimensions of affective meaning: \n\n\t valence: pleasantness\n\t arousal: intensity of emotion\n\t dominance: degree of control exerted\n\n\n## SLP Chapter 6.2 Vector Semantics\n\nVector semantics: \n\n1) tf-idf: meaning of word defined by function of counts of nearby words, results in sparse vectors \n\n2) word2vec: results in dense vectors \n\n3) cosine: use embeddings to compute semantic similarity between 2 pieces of text\n\n\n## SLP Chapter 6.3 Words and Vectors\n\nco-occurence matrices represent how often words occur together \n\n\n1) term-document matrix \n\n\t rows: words in vocab, columns: documents\n\t good for finding similar documents using similar column vectors \n\n2) term-term matrix \n\n\t aka word-word or term-context\n\t rows: words in vocab, columns: words in vocab \n\n** each cell is # of times row word appeared in same context window (i.e. document, window of size 2) as column word\n\n\n## SLP Chapter 6.4 Cosine for measuring similarity\n\ncosine: high value means very similar, 0 means completely dissimilar \n\n\t problem: dot product favors longer vectors, so we normalize it\n\t cosine similarity: cos(θ) = a•b / (|a||b|); -1 means opposite, 1 means exactly same\n\t vector length: |x| = sqrt(sum of the squared values of each number in the vector)\n\t unit vector: divide a vector by its vector length\n\n\n## SLP Chapter 6.8 Word2vec\n\nembeddings are shorter versions of the word vectors used in previous models and they are dense \n\nDense is better in NLP than sparse because: \n\n\t fewer weights for classifier to learn, less overfitting, better capture synonymy \n\n\nWord2vec: fast, efficient to train, easily available with pretrained embeddings \n\n\t uses static embeddings\n\t instead of counting how often a word occurs near another word, \n\t train a classifier to predict if a word is likely to show up near another word \n\t the weights we learn from this will be the embeddings for each word \n\t words close to each other will have more similar embeddings \n\n\nSkip-Gram: \n\n\t treat each target word and neighboring context word as positive examples\n\t randomly sample other words to get neg. examples\n\t use LR to train classifier for positive vs. negative\n\t use learned weights as embeddings\n\t initialize 2 embeddings - W for word and C for context\n\t classifer assigns prob. based on how similar context window is to target word\n\t sigmoid applied to dot product of embeddings of target word with context word \n\n\nSkip-Gram Algorithm \n\n\t assign a random embedding to each word in vocab\n\t iteratively shift each word's embedding to be more like the words it is near\n\t maximize similarity of word + positive contexts and minimize word + neg contexts \n\nkey points: SG learns 2 embeddings per word (target and context), can just add them together\n\n\n## SLP Chapter 6.10 Semantic properties of embeddings\n\nSemantic properties of embeddings: \n\n\t first-order co-occurence: 2 words are near each other in corpus (i.e. wrote, book)\n\t second-order co-occurence: 2 words have similar neighbors (i.e. wrote, said, remarked)\n\t parallelogram model: uses analogies --> predicted b*=argmin distance(x, a*-a+b)\n\n\n## SLP Chapter 6.11 Bias and Embeddings\n\nBias in Embeddings: \n\n\t allocational harm: system allocate jobs/credit unfairly to groups (i.e. hiring bias)\n\t embeddings amplify bias\n\t representational harm: system demeans/ignores certain groups\n\n\n## SLP Chapter 6.12 Evaluating Vector Models\n\nEvaluating Vector Models: \n\n\t similarity: algorithm's word similarity scores vs human's similarity ratings \n\nAll embedding algorithsm suffer from inherent variability, so we should train multiple embeddings\nand use bootstrap sampling over documents\n\n\n## Module 14 Lecture Notes\n\nWord meaning representation should encode: \n\n1) synonyms, antonyms, connotations, semantic roles, support for entailment \n\n2) entailment: mathematically well-undestood, powerful for logical operations, knowledge comes from somewhere \n\nTF-IDF: \n\t term frequency: how often word occurred in a document\n\t inverse document frequency: 1/# of documents word occurred in \n\nCurse of dimensionality: if vocab is too large, too many params to estimate \n\n\\Language modeling learns a function that returns the joint probability \n\n\t issues: curse of dimensionality, n-gram models are bad at generalizing\n \n\n## Module 14 Definitions\n* **Teacher forcing** - always give model correct next word to use as input for next step instead of using best prediction from previous time step\n* **Weight tying** - E and V matrices are similar, so just use a single set of embeddings instead. E = V\n* **Distributional hypothesis** - words that occur in similar contexts have similar meanings\n* **Vector semantics** - interprets word meaning by learning embeddings to explain distr. hypothesis\n* **Polysemous** - a word that has multiple word senses\n* **Word sense disambiguation** - figuring out which word sense is being used in a context\n* **Propositional meaning** - when 2 words are direct synonyms\n* **Principle of contrast** - difference in linguistic form can change the meaning of word (i.e. H20 in science, water for hike)\n* **Similarity** - can use humans to judge\n* **Relatedness/assocation** - i.e. coffee and cup, scalpel and surgeon. typically part of same semantic field\n* **Semantic field** - set of words that have structured relationship to each other. use in topic modeling\n* **Lda** - unsupervised learning on text to get associated words\n* **Semantic frame** - set of words that denote the perspectives in an event (i.e. buy and sell). important for question answering\n* **Connotations** - aspects of a word's meaning that are related to the writer/reader's emotions/sentiment/etc\n* **Information retrieval** - finding the document that best matches the query\n* **Skip-gram with negative sampling** - aka word2vec\n* **Static embeddings** - method learns 1 fixed embedding for each word\n* **Contextual embeddings** - vector for each word is different in different contexts\n* **Self-supervision** - unsupervised learning where withhold some information about data, and task network with predicting it\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}