{
  "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",
      "execution_count": 164,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "lzaavW96tcxM",
        "outputId": "17f29538-751a-4c10-a55b-fd9fc8280542"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "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)))"
      ]
    },
    {
      "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",
      "execution_count": 165,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "8DvZ57A-djo1",
        "outputId": "604c1713-218b-4a54-8d06-279613cc501e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 166,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 167,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "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",
        "chapter16_2 =  \"\"\"  \"\"\"\n",
        "chapter16_3 =  \"\"\"  \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" \"\"\"\n",
        "chapter17_2 =  \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\" Stochastic/probabilistic environment, where agent will have to figure the best action to take. \\n\n",
        "MDP's are a kind og non-deterministic search problem. Applicable in a fully observable task env where we have to make a sequence of decisions\n",
        "and where the outcome of our actions is non-deterministic\\n\n",
        "Ways to solve MDP's: (1) Expectimax search, (2) Value iteration, (3) Policy Iteration \n",
        "MDP: kind of nondeterministic search, projects an expectimax-like search tree\n",
        "\\n  - 1) sequential decision problem (2) fully observable env (3) stochastic transition model (4) has additive rewards \\n\n",
        "\\n  - need set of states, actions, transition model, reward function, initial state, optionally one or more terminal states \\n\n",
        "SOLUTION == POLICY (bc of non-determinism in MDP's, cannot simply give a sequence of actions)\\n\n",
        "maps from a state onto the action to take if the agent is in that state\\n\n",
        "π* = optimal policy, which depends on reward function \\n\n",
        "\\n  - Same policies may lead to different sequence of states and actions (env history) and thus a different score under the reward function\n",
        "\\n- compute the expected utility of all possible paths generated by a policy \\n\n",
        "Discounting term : determines how much to postpone immediate gratification for later reward \\n\n",
        "- reasonable to maximize sum of rewards, also reasonable to prefer rewards now to rewards later. one soln: values of rewards decay exponentially\n",
        "\\n - Why discount? sooner rewards probably have higher utility than later rewards, also helps algos converge \\n\n",
        "Infinite utilities: problem - what if game lasts forever?\n",
        "\\n - soln: finite horizon (depth-limited search) or discounting or absorbing state: guarentee that for every policy, a terminal state will eventually be reached (e.g. overheated in racing) \\n\n",
        "Value iteration\n",
        "\\n - (1) start w Vo(s) = 0. (2) Given vector of Vk(s) values, do one play of expectimax from each state (3) repeat until convergence (4) TIME COMPLX: O(AS^2) \\n\n",
        "\\n - (k = num iterations/Bellman updates)\n",
        "\\n CONVERGENCE: How do we know the V_{k} vectors will converge? \n",
        "\\n  - (1) If tree has max depth M, then V_{m} holds the actual untruncated values (2) If discount < 1 \\n\n",
        "\\n  - Bellman equation is the basis for V.I. algo solving MDPs\n",
        "\n",
        "POLICY EVALUATION: Instead of figuring out optimal val of each state, try to figure out what best policies are \\n\n",
        "- iterate over policies rather than states. How do we calc the V's for a fixed policy pi?\n",
        "(Idea 1) Turn recursive Bellman eq into updates (like value iteration). TIME COMPLX O(S^2) per iter (idea 2) without the maxes, the Bellman eq are just a linear system \\n\n",
        "\\n - given a policy, calculate the utility of each state if that policy were to be executed\n",
        "\\n - $O(S^2)$ per iter\n",
        "\n",
        "\\n POLICY IMPROVEMENT: calculate a new MEU policy $pi_{i+1}$ using one-step look ahead based on $U_i$\n",
        "\n",
        "\\n - Imagine we have the optimal values V*(s). How should we act => do a mini expectimax (one-step). this is policy extraction, since it gets the policy implied by the values \\n\n",
        "\\n - Imagine we have the optimal q-values. How to act => just pick the best action implied by those two values. actions are easier select from q-values than values \\n\n",
        "\n",
        "PROBLEMS W VALUE ITERATION: \n",
        "\\n  - (1) Slow, O(S^2A) per iter (but also converges exponentially fast ^k) (2) The \"max\" at each state rarely changes (3) Policy often converges long before the values\n",
        "\\n - alt approach for optimal values: (1) Policy iteration, calc utils for some fixed policy until convergence (2) policy improvement, update policy using one step look ahead with resulting converged (but not optimal) utils as future vals (3) repeat until convergence (this is POLICY ITERATION. still optimal and can converge much faster) \\n\n",
        "\n",
        "VALUE ITERATION VS POLICY ITERATION: both compute the same, all optimal vals \\n\n",
        " - value: each iter updates both values and policy. we dont track policy, but take max over actions implicitly recomputes it \\n\n",
        " - policy: we do several passes that update utils with fixed policy (each pass is fast bc consider only one action at a time) (2) after policy evaluated, new policy chosen (slow like value iter pass) (3) new policy is better or we're done \\n\n",
        "\n",
        "SUMMARY: MDP ALG \\n\n",
        "- want to either (1) compute optimal vals, use value or policy iter (2) compute vals for particular policy: use policy evaluation (3) turn vals into a policy: use policy extraction (one step lookahead). \\n \n",
        "these all look the same!! only differ only in whether we plug a fixed policy or max over actions \\n\n",
        "\n",
        "MAXIMUM EXPECTED UTILITY: worst case is not going to always happen! \\n\n",
        "- for worst-case minimax reasoning, terminal function scale doesnt matter (1) we just want better states to have higher evaluations to get correct order (2) called insensitivity to monotonic transformations \\n\n",
        "\n",
        "RATIONAL PREFERENCES: we want some constraints on preferences before we call them rational \n",
        "\\n  - Axiom of Transitivity: Prefer A over B and prefer B over lottery C, implies A preferred over C \n",
        "\\n  - Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p, A; 1-p, C] \\sim B$ (some lotery B between A, C, there exists probability p that makes you indifferent to B)\n",
        "\\n  - Orderability: Exactly one of $(A \\succ B), (B \\succ A), (A \\sim B)$ holds. Given 2 lotteries, a rational agent must prefer one or rathem equal (cannot avoid deciding)\n",
        "\\n  - Substitutability: $A \\succ B \\Rightarrow [p,A; 1-p, C] \\sim [p, B; 1-p, C]$ (if neither prefer A, B, then some lottery in between that u have equal preference over that lottery)\n",
        "\\n  - Monotonicity: $A \\succ B \\Rightarrow (p \\geq q \\Leftrightarrow [p, A; 1-p, B] \\succeq [q, A; 1-q, B])$ (if A better than B, i prefer greater p than q)\n",
        "\\n  - Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability (long one)\n",
        "\n",
        "\\n EXISTENCE OF A UTILITY FUNCTION: \n",
        "\\n  - if agent's preference obey the axioms of utility, then exists a function U s.t. U(A) > U(B) iff A is preferred to B, and U(A)=U(B) if indifferent\n",
        "\n",
        "\\n EXPECTED UTIL OF A LOTTERY:\n",
        "\\n  -  sum of probabilities of each outcome times the utility of that outcome\n",
        "\n",
        "\\n MEU Principle: \n",
        "\\n  - Given any preferences satisfying these contraints, exists a real values function U s.t.: \n",
        "\\n  - $U(A) \\geq U(B) \\Leftrightarrow A\\simeq B , U([p_1, S_1; ... ; p_n, S_n]) = \\sum_{i}^{}p_iU(S_i)$ (values assigned by U preserve preferences of both prizes and lotteries)\n",
        "\\n  - (1) Choose the action that maxes expected util (2) Note: agent can be rational (consistent w MEU) w/o representing or manipulating utils and probabilities (3) e.g. lookup table for perfect tic-tac-toe, reflex vacuum cleaner. Money does NOT behave as util funciton, but can talk about utility of having money or being in debt \n",
        "\\n  - Fundamental idea of decision theory is that an agent is rational iff it choices the action that yields highest expected utility, avged over all possible outcomes of the action \n",
        "\n",
        "\\n EXTRA NOTES:\n",
        "\\n  - Markov property: given the past state, the present and future are dependent\n",
        "\\n  - In n-gram language models, Markov assumption makes it possible to estimate the probabilities from data\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",
        "\"policy\" : \"takes in a state and returns best action agent could take when it finds itself in that state/ SOLUTION TO A MDP\",\n",
        "\"reward function\" : \"rewards can be positive or sequestion but have a max bound. agent can also receive reward at each time step\",\n",
        "\"principle of maximum expected utility\": \"a rational agent should choose the action that maximizes its expected util, given its knowledge\",\n",
        "\"lottery\": \"situations with uncertain prizes (mixture of outcomes where their probability gets attached)\", \n",
        "\"contraction\":\"part of the proof of convergence for value iteration\",\n",
        "\"preference elicitation\": \"involves presenting choices to the human and using observed preferences to pin down the underlying utility function\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "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",
      "execution_count": 168,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2137
        },
        "id": "gYYeNcdM_maE",
        "outputId": "77151724-e715-4750-a061-2c40fddb2a8c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 8: Markov Decision Processes\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "  \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "  \n",
              "\n",
              "## AIMA Chapter 17.1 Sequential Decision Problems\n",
              " \n",
              "\n",
              "## AIMA Chapter 17.2 Algorithms for MDPs\n",
              " \n",
              "\n",
              "## Module 8 Lecture Notes\n",
              " Stochastic/probabilistic environment, where agent will have to figure the best action to take. \n",
              "\n",
              "MDP's are a kind og non-deterministic search problem. Applicable in a fully observable task env where we have to make a sequence of decisions\n",
              "and where the outcome of our actions is non-deterministic\n",
              "\n",
              "Ways to solve MDP's: (1) Expectimax search, (2) Value iteration, (3) Policy Iteration \n",
              "MDP: kind of nondeterministic search, projects an expectimax-like search tree\n",
              "\n",
              "  - 1) sequential decision problem (2) fully observable env (3) stochastic transition model (4) has additive rewards \n",
              "\n",
              "\n",
              "  - need set of states, actions, transition model, reward function, initial state, optionally one or more terminal states \n",
              "\n",
              "SOLUTION == POLICY (bc of non-determinism in MDP's, cannot simply give a sequence of actions)\n",
              "\n",
              "maps from a state onto the action to take if the agent is in that state\n",
              "\n",
              "π* = optimal policy, which depends on reward function \n",
              "\n",
              "\n",
              "  - Same policies may lead to different sequence of states and actions (env history) and thus a different score under the reward function\n",
              "\n",
              "- compute the expected utility of all possible paths generated by a policy \n",
              "\n",
              "Discounting term : determines how much to postpone immediate gratification for later reward \n",
              "\n",
              "- reasonable to maximize sum of rewards, also reasonable to prefer rewards now to rewards later. one soln: values of rewards decay exponentially\n",
              "\n",
              " - Why discount? sooner rewards probably have higher utility than later rewards, also helps algos converge \n",
              "\n",
              "Infinite utilities: problem - what if game lasts forever?\n",
              "\n",
              " - soln: finite horizon (depth-limited search) or discounting or absorbing state: guarentee that for every policy, a terminal state will eventually be reached (e.g. overheated in racing) \n",
              "\n",
              "Value iteration\n",
              "\n",
              " - (1) start w Vo(s) = 0. (2) Given vector of Vk(s) values, do one play of expectimax from each state (3) repeat until convergence (4) TIME COMPLX: O(AS^2) \n",
              "\n",
              "\n",
              " - (k = num iterations/Bellman updates)\n",
              "\n",
              " CONVERGENCE: How do we know the V_{k} vectors will converge? \n",
              "\n",
              "  - (1) If tree has max depth M, then V_{m} holds the actual untruncated values (2) If discount < 1 \n",
              "\n",
              "\n",
              "  - Bellman equation is the basis for V.I. algo solving MDPs\n",
              "\n",
              "POLICY EVALUATION: Instead of figuring out optimal val of each state, try to figure out what best policies are \n",
              "\n",
              "- iterate over policies rather than states. How do we calc the V's for a fixed policy pi?\n",
              "(Idea 1) Turn recursive Bellman eq into updates (like value iteration). TIME COMPLX O(S^2) per iter (idea 2) without the maxes, the Bellman eq are just a linear system \n",
              "\n",
              "\n",
              " - given a policy, calculate the utility of each state if that policy were to be executed\n",
              "\n",
              " - $O(S^2)$ per iter\n",
              "\n",
              "\n",
              " POLICY IMPROVEMENT: calculate a new MEU policy $pi_{i+1}$ using one-step look ahead based on $U_i$\n",
              "\n",
              "\n",
              " - Imagine we have the optimal values V*(s). How should we act => do a mini expectimax (one-step). this is policy extraction, since it gets the policy implied by the values \n",
              "\n",
              "\n",
              " - Imagine we have the optimal q-values. How to act => just pick the best action implied by those two values. actions are easier select from q-values than values \n",
              "\n",
              "\n",
              "PROBLEMS W VALUE ITERATION: \n",
              "\n",
              "  - (1) Slow, O(S^2A) per iter (but also converges exponentially fast ^k) (2) The \"max\" at each state rarely changes (3) Policy often converges long before the values\n",
              "\n",
              " - alt approach for optimal values: (1) Policy iteration, calc utils for some fixed policy until convergence (2) policy improvement, update policy using one step look ahead with resulting converged (but not optimal) utils as future vals (3) repeat until convergence (this is POLICY ITERATION. still optimal and can converge much faster) \n",
              "\n",
              "\n",
              "VALUE ITERATION VS POLICY ITERATION: both compute the same, all optimal vals \n",
              "\n",
              " - value: each iter updates both values and policy. we dont track policy, but take max over actions implicitly recomputes it \n",
              "\n",
              " - policy: we do several passes that update utils with fixed policy (each pass is fast bc consider only one action at a time) (2) after policy evaluated, new policy chosen (slow like value iter pass) (3) new policy is better or we're done \n",
              "\n",
              "\n",
              "SUMMARY: MDP ALG \n",
              "\n",
              "- want to either (1) compute optimal vals, use value or policy iter (2) compute vals for particular policy: use policy evaluation (3) turn vals into a policy: use policy extraction (one step lookahead). \n",
              " \n",
              "these all look the same!! only differ only in whether we plug a fixed policy or max over actions \n",
              "\n",
              "\n",
              "MAXIMUM EXPECTED UTILITY: worst case is not going to always happen! \n",
              "\n",
              "- for worst-case minimax reasoning, terminal function scale doesnt matter (1) we just want better states to have higher evaluations to get correct order (2) called insensitivity to monotonic transformations \n",
              "\n",
              "\n",
              "RATIONAL PREFERENCES: we want some constraints on preferences before we call them rational \n",
              "\n",
              "  - Axiom of Transitivity: Prefer A over B and prefer B over lottery C, implies A preferred over C \n",
              "\n",
              "  - Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p, A; 1-p, C] \\sim B$ (some lotery B between A, C, there exists probability p that makes you indifferent to B)\n",
              "\n",
              "  - Orderability: Exactly one of $(A \\succ B), (B \\succ A), (A \\sim B)$ holds. Given 2 lotteries, a rational agent must prefer one or rathem equal (cannot avoid deciding)\n",
              "\n",
              "  - Substitutability: $A \\succ B \\Rightarrow [p,A; 1-p, C] \\sim [p, B; 1-p, C]$ (if neither prefer A, B, then some lottery in between that u have equal preference over that lottery)\n",
              "\n",
              "  - Monotonicity: $A \\succ B \\Rightarrow (p \\geq q \\Leftrightarrow [p, A; 1-p, B] \\succeq [q, A; 1-q, B])$ (if A better than B, i prefer greater p than q)\n",
              "\n",
              "  - Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability (long one)\n",
              "\n",
              "\n",
              " EXISTENCE OF A UTILITY FUNCTION: \n",
              "\n",
              "  - if agent's preference obey the axioms of utility, then exists a function U s.t. U(A) > U(B) iff A is preferred to B, and U(A)=U(B) if indifferent\n",
              "\n",
              "\n",
              " EXPECTED UTIL OF A LOTTERY:\n",
              "\n",
              "  -  sum of probabilities of each outcome times the utility of that outcome\n",
              "\n",
              "\n",
              " MEU Principle: \n",
              "\n",
              "  - Given any preferences satisfying these contraints, exists a real values function U s.t.: \n",
              "\n",
              "  - $U(A) \\geq U(B) \\Leftrightarrow A\\simeq B , U([p_1, S_1; ... ; p_n, S_n]) = \\sum_{i}^{}p_iU(S_i)$ (values assigned by U preserve preferences of both prizes and lotteries)\n",
              "\n",
              "  - (1) Choose the action that maxes expected util (2) Note: agent can be rational (consistent w MEU) w/o representing or manipulating utils and probabilities (3) e.g. lookup table for perfect tic-tac-toe, reflex vacuum cleaner. Money does NOT behave as util funciton, but can talk about utility of having money or being in debt \n",
              "\n",
              "  - Fundamental idea of decision theory is that an agent is rational iff it choices the action that yields highest expected utility, avged over all possible outcomes of the action \n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              "  - Markov property: given the past state, the present and future are dependent\n",
              "\n",
              "  - In n-gram language models, Markov assumption makes it possible to estimate the probabilities from data\n",
              "\n",
              "\n",
              "\n",
              "## Module 8 Definitions\n",
              "* **Policy** - takes in a state and returns best action agent could take when it finds itself in that state/ SOLUTION TO A MDP\n",
              "* **Reward function** - rewards can be positive or sequestion but have a max bound. agent can also receive reward at each time step\n",
              "* **Principle of maximum expected utility** - a rational agent should choose the action that maximizes its expected util, given its knowledge\n",
              "* **Lottery** - situations with uncertain prizes (mixture of outcomes where their probability gets attached)\n",
              "* **Contraction** - part of the proof of convergence for value iteration\n",
              "* **Preference elicitation** - involves presenting choices to the human and using observed preferences to pin down the underlying utility function\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 169,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" n-armed bandit has $n$ levers - behind each is a fixed but unknown probability distribution of winnings; each pull samples from that distribution \n",
        "\\n  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\"  \"\"\"\n",
        "chapter22_2 =  \"\"\" \"\"\"\n",
        "chapter22_3 =  \"\"\" \"\"\"\n",
        "chapter22_4 =  \"\"\" \"\"\"\n",
        "chapter22_5 =  \"\"\" \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\" \n",
        "In MDP,\n",
        "\\n -  agent is given reward and transition function. In reinforcement learning, agent must learn both of these functions by interacting with the world \n",
        "\\n -  Everytime agent takes an action in the world, will receive instantaneous reward (feedback). GOAL: maximize its expected rewards over time using observations \n",
        "\\n  - Tradeoff between Exploration + Exploitation. (Exploration) Agent must try new actions including where reward may be worse than another action (Exploitation) Use knowledge learned so far to choose best action for expected rewards\n",
        "\\n -  though stochastic, we knew what the probability distribution over the states was\n",
        "\\n Model-based learning: \n",
        "\\n  - where transition function is represented using explicit probabilistic model \n",
        "\\n Temporal Difference Learning: \n",
        "\\n  - agent is able to update beliefs about world after every single action it takes using some kind of exponential moving average\n",
        "\\n Regret: \n",
        "\\n  - lets us measure total rewards got from a particular exploration strategy and compare that against the total expected rewards we would get if agent had been able to follow optimal policy the whole time\n",
        "\n",
        "\\n REINFORCEMENT LEARNING: still assume a MDP \n",
        "\\n  - (1) set of states s \\in S (2) set of actions per state A (3) model T(s, a, s') (4) reward function R(s, a, s')\n",
        "\\n  - Still looking for a policy π(s)\n",
        "\\n  - New twist: don't know T or R (i.e. we dont know which states are good or what the actions do, must actually try actions and states to learn)\n",
        "\\n  - Offline (MDPs (think about it)) vs Online (Reinforcement Learning (try things out))\n",
        "\\n  - Value iteration + Policy Iteration are OFFLINE Algs (like A*) \n",
        "\n",
        "\\n MODEL-BASED LEARNING\n",
        "\\n  - Model-based idea: (1) learn approximate model based on exp (2) solve for values as if learned model is correct\n",
        "\\n  - Step 1: Learnign Empirical MDP model (1) count outcomes s' for each s, a (2) normalize to give an estimate of T(s, a, s') (3) discover each R(s, a, s') when we experience (s,a,s')\n",
        "\\n  - Step 2: Solve the learned MDP (e.g. use value iteration as before) \n",
        "\n",
        "\\n MODEL-FREE LEARNING\n",
        "\\n  - instead, take an action. every time we do so, we compare the results to what we thought was going to happen to actuality. when something better or worse happens, take values and adjust it \n",
        "\\n PASSIVE REIN. LEARN.: let someone else choose the policy and we try and see outcome (we're gonna figure out exactly the same kind of thing that policy evaluation did) \n",
        "\\n  - Simplified task: policy Evaluation (input) fixed policy π(s), dont know transitions and rewards (goal) learn state values\n",
        "\\n  - in this case (1) learner is \"along for the ride (2) no choice about what actions to take (3) just execute policy and learn that exp (4) NOT offline planning - actually take actions in the world \n",
        "\\n DIRECT EVALUATION\n",
        "\\n  - Goal: Compute values for each state under π\n",
        "\\n  - Idea: average together observed sample values (1. act according to π 2. everytime u visit a state, write down what the sum of discounted rewards turned out to be 3. avg those samples)\n",
        "\\n ACTION-UTILITY LEARNING (Q-learning)\n",
        "\\n  - Given Q-function, agent can choose what to do in $s$ by finding the action w highest $Q-value$\n",
        "\n",
        "\\n PROS and CONS of DIRECT EVALUATION\n",
        "\\n  - Pros (1) easy to understand (2) doesnt requirement any knowledge of T, R (3) eventually computes the correct avg values, using just sample transitions\n",
        "\\n  - Cons (1) wastes info about state connections (2) each state must be learned separately (3) so, takes a long time to learn\n",
        "\\n  - Why not use policy evaluation? Fully exploits connections btw states, but unfortunately need T and R to do it\n",
        "\n",
        "\\n TEMPORAL DIFFERENCE LEARNING\n",
        "\\n  - Big idea: learn from every experience (1) update V(s) each time we exp a transition (2) likely outcomes s' will contribute updates more often\n",
        "\\n  - Temporal difference learning of values (1) policy still fixed, still doing evaluation (2) move values toward value of whatever successor occurs: running average\n",
        "\n",
        "\\n EXPONENTIAL MOVING AVERAGE\n",
        "\\n - More recent samples are more important (discount is exponentiated).\n",
        "\\n - Forgets about the past. Decreasing learning rate (alpha) can give converging averages \n",
        "\n",
        "\\n PROBLEMS WITH TD VALUE LEARNING\n",
        "\\n  - It is a model free way to do policy eval, mimicking Bellman updates w running sample averages\n",
        "\\n  - However, if want to turn values into a new policy, we're sunk\n",
        "\\n  - Idea: learn Q-values, not values. Makes action selection model-free too!\n",
        "\n",
        "\\n ACTIVE REINFORCEMENT LEARNING\n",
        "\\n  - Full Reinforcement Learning: optimal policies (like value iteration)\n",
        "\\n  - (1) dont know transitions + rewards (2) you choose the actions now \n",
        "\\n  - GOAL: learn optimal policy/values\n",
        "\\n  - (1) learner makes choices (2) exploration vs exploitation (3) NOT offline planning \n",
        "\n",
        "\\n Q-VALUE ITERATION \n",
        "\\n  - (1) Value iteration: find successive (depth-limited values) \n",
        "\\n  - (2) Q-values are more useful, so compute them instead \n",
        "\n",
        "\\n Q-LEARNING: sample-based Q-value iteration\n",
        "\\n -  Learn Q(s, a) values as you go (1) receive a sample (s, a, s', r) (2) consider old esimate Q(s, a) (3) consider new sample estimate $sample = R(s, a, s') + \\gamma max_{a'}Q(s', a')$(4) incorporate new estimate into a running average $Q(s, a) \\leftarrow (1- alpha)Q(s, a) + (alpha)[sample]$\n",
        "\\n -  PROPERTIES: converges to optimal policy, even if youre acting suboptimally!\n",
        "\\n -  Called OFF-POLICY LEARNING\n",
        "\\n  - Caveats: (1) have to explore enough (2) have to eventually make learning rate small enough.. but not decrease it too quickly (closer to zero learning rate = keep knowledge of past) (3) in the limit, doesnt matter how u select actions!\n",
        "\n",
        "\\n Q-learning requires exploring in order to learn optimal policy\n",
        "\\n -  To force exploration: random ($\\epsilon$ greedy) or exploration functions \n",
        "\\n  - When to explore? Better idea: explore areas whose badness is not yet established, eventually stop exploring \n",
        "\\n  Exploration function: takes a value estimate u and visit count n, returns optimistic utility $f(u, n) = u + k/n)$ \n",
        "\\n  - (REGULAR Q-UPDATE) $Q(s, a) \\leftarrow_{a} R(s, a, s') + \\gamma max_{a'}Q(s', a')$\n",
        "\\n  - (MODIFIED Q-UPDATE) $Q(s, a) \\leftarrow_{a} R(s, a, s') + \\gamma max_{a'}f(Q(s', a'), N(s',a'))$\n",
        "\\n  - Note: this propagates the \"bonus\" back to states that lead to unknown states as well \n",
        "\n",
        "\\n REGRET: even if u learn optimal policy, still make mistakes along the way\n",
        "\\n  - minimizing regret requires optimally learning to be optimal\n",
        "\n",
        "\\n APPROXIMATE Q-LEARNING\n",
        "\\n  - GENERALIZING ACROSS STATES: basic q-learning keeps a table of all q-values\n",
        "\\n  - In realistic situations, we cannot possibly learn about every single state (1) too many states to vist them all in training (2) too many states to hold the q-tables in memory\n",
        "\\n  - Instead, want to generalize (1) learn about some small num of training states from exp (2) gneeralize that exp to new, similar sitations \n",
        "\\n  - Intuitive interpretation: adjust weights of active features (e.g. if something unexpectedly bad happens, blame all features that were on)\n",
        "\\n  - Formal Justification: online least squares\n",
        "\n",
        "\\n LINEAR VALUE FUNCTION: using a feature representation, we can write a q function (or value function) for any state using few weights\n",
        "\\n  - $V(s) = w_1f_1(s) +... + w_nf_n(s)$\n",
        "\\n  - $Q(s, a) =  w_1f_1(s, a) +... + w_nf_n(s, a)$\n",
        "\\n  - Advantage: our experience is summed up in a few powerful numbers | Disadvantage: states may share features but actually be very different in value\n",
        "\n",
        "\\n EXTRA NOTES \n",
        "\\n  - Q-function in reinforcement learning is action-utility function\n",
        "\\n  - For a partially observable environment, learning problem is more difficult bc next percept is no longer a label for the state prediction problem  \n",
        "\\n  Linear functions: when using perceptron learning rule, weights are updated when the actual output does not match the hypothesis output \n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"exploration\":\"try unknown actions to get info\",\n",
        "\"exploitation\": \"eventually, have to use what you know\",\n",
        "\"regret\": \"even if u learn intelligently, you have to try things repeatedly\",\n",
        "\"regret\": \"measure of total mistake cost: diff btwn your expected rewards, including youthful suboptimality, and optimal (expected) rewards)\",\n",
        "\"difficulty\" : \"learning can be much harder than solving a known MDP\", \n",
        "\"n-armed bandit\": \"\",\n",
        "\"policy search\":\"agent learns policy pi(s) that maps directly states to actions (reflex agent)\",\n",
        "\"absorbing state\":\"where no actions have any effect and no rewards are received (IRL, many actions are irreversable)\",\n",
        "\"pseudorewards\":\"additional rewards supplied to speed up learning\",\n",
        "\n",
        "\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 170,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2676
        },
        "id": "ydOK__lwWgdp",
        "outputId": "95270732-3873-4010-a7ba-74a007fa43f3"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 9: Reinforcement Learning\n",
              "## AIMA Chapter 17.3 Bandit Problems\n",
              " n-armed bandit has $n$ levers - behind each is a fixed but unknown probability distribution of winnings; each pull samples from that distribution \n",
              "\n",
              "  \n",
              "\n",
              "## AIMA Chapter 22.1 Learning from Rewards\n",
              "  \n",
              "\n",
              "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
              " \n",
              "\n",
              "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
              " \n",
              "\n",
              "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
              " \n",
              "\n",
              "## Module 9 Lecture Notes\n",
              " \n",
              "In MDP,\n",
              "\n",
              " -  agent is given reward and transition function. In reinforcement learning, agent must learn both of these functions by interacting with the world \n",
              "\n",
              " -  Everytime agent takes an action in the world, will receive instantaneous reward (feedback). GOAL: maximize its expected rewards over time using observations \n",
              "\n",
              "  - Tradeoff between Exploration + Exploitation. (Exploration) Agent must try new actions including where reward may be worse than another action (Exploitation) Use knowledge learned so far to choose best action for expected rewards\n",
              "\n",
              " -  though stochastic, we knew what the probability distribution over the states was\n",
              "\n",
              " Model-based learning: \n",
              "\n",
              "  - where transition function is represented using explicit probabilistic model \n",
              "\n",
              " Temporal Difference Learning: \n",
              "\n",
              "  - agent is able to update beliefs about world after every single action it takes using some kind of exponential moving average\n",
              "\n",
              " Regret: \n",
              "\n",
              "  - lets us measure total rewards got from a particular exploration strategy and compare that against the total expected rewards we would get if agent had been able to follow optimal policy the whole time\n",
              "\n",
              "\n",
              " REINFORCEMENT LEARNING: still assume a MDP \n",
              "\n",
              "  - (1) set of states s \\in S (2) set of actions per state A (3) model T(s, a, s') (4) reward function R(s, a, s')\n",
              "\n",
              "  - Still looking for a policy π(s)\n",
              "\n",
              "  - New twist: don't know T or R (i.e. we dont know which states are good or what the actions do, must actually try actions and states to learn)\n",
              "\n",
              "  - Offline (MDPs (think about it)) vs Online (Reinforcement Learning (try things out))\n",
              "\n",
              "  - Value iteration + Policy Iteration are OFFLINE Algs (like A*) \n",
              "\n",
              "\n",
              " MODEL-BASED LEARNING\n",
              "\n",
              "  - Model-based idea: (1) learn approximate model based on exp (2) solve for values as if learned model is correct\n",
              "\n",
              "  - Step 1: Learnign Empirical MDP model (1) count outcomes s' for each s, a (2) normalize to give an estimate of T(s, a, s') (3) discover each R(s, a, s') when we experience (s,a,s')\n",
              "\n",
              "  - Step 2: Solve the learned MDP (e.g. use value iteration as before) \n",
              "\n",
              "\n",
              " MODEL-FREE LEARNING\n",
              "\n",
              "  - instead, take an action. every time we do so, we compare the results to what we thought was going to happen to actuality. when something better or worse happens, take values and adjust it \n",
              "\n",
              " PASSIVE REIN. LEARN.: let someone else choose the policy and we try and see outcome (we're gonna figure out exactly the same kind of thing that policy evaluation did) \n",
              "\n",
              "  - Simplified task: policy Evaluation (input) fixed policy π(s), dont know transitions and rewards (goal) learn state values\n",
              "\n",
              "  - in this case (1) learner is \"along for the ride (2) no choice about what actions to take (3) just execute policy and learn that exp (4) NOT offline planning - actually take actions in the world \n",
              "\n",
              " DIRECT EVALUATION\n",
              "\n",
              "  - Goal: Compute values for each state under π\n",
              "\n",
              "  - Idea: average together observed sample values (1. act according to π 2. everytime u visit a state, write down what the sum of discounted rewards turned out to be 3. avg those samples)\n",
              "\n",
              " ACTION-UTILITY LEARNING (Q-learning)\n",
              "\n",
              "  - Given Q-function, agent can choose what to do in $s$ by finding the action w highest $Q-value$\n",
              "\n",
              "\n",
              " PROS and CONS of DIRECT EVALUATION\n",
              "\n",
              "  - Pros (1) easy to understand (2) doesnt requirement any knowledge of T, R (3) eventually computes the correct avg values, using just sample transitions\n",
              "\n",
              "  - Cons (1) wastes info about state connections (2) each state must be learned separately (3) so, takes a long time to learn\n",
              "\n",
              "  - Why not use policy evaluation? Fully exploits connections btw states, but unfortunately need T and R to do it\n",
              "\n",
              "\n",
              " TEMPORAL DIFFERENCE LEARNING\n",
              "\n",
              "  - Big idea: learn from every experience (1) update V(s) each time we exp a transition (2) likely outcomes s' will contribute updates more often\n",
              "\n",
              "  - Temporal difference learning of values (1) policy still fixed, still doing evaluation (2) move values toward value of whatever successor occurs: running average\n",
              "\n",
              "\n",
              " EXPONENTIAL MOVING AVERAGE\n",
              "\n",
              " - More recent samples are more important (discount is exponentiated).\n",
              "\n",
              " - Forgets about the past. Decreasing learning rate (alpha) can give converging averages \n",
              "\n",
              "\n",
              " PROBLEMS WITH TD VALUE LEARNING\n",
              "\n",
              "  - It is a model free way to do policy eval, mimicking Bellman updates w running sample averages\n",
              "\n",
              "  - However, if want to turn values into a new policy, we're sunk\n",
              "\n",
              "  - Idea: learn Q-values, not values. Makes action selection model-free too!\n",
              "\n",
              "\n",
              " ACTIVE REINFORCEMENT LEARNING\n",
              "\n",
              "  - Full Reinforcement Learning: optimal policies (like value iteration)\n",
              "\n",
              "  - (1) dont know transitions + rewards (2) you choose the actions now \n",
              "\n",
              "  - GOAL: learn optimal policy/values\n",
              "\n",
              "  - (1) learner makes choices (2) exploration vs exploitation (3) NOT offline planning \n",
              "\n",
              "\n",
              " Q-VALUE ITERATION \n",
              "\n",
              "  - (1) Value iteration: find successive (depth-limited values) \n",
              "\n",
              "  - (2) Q-values are more useful, so compute them instead \n",
              "\n",
              "\n",
              " Q-LEARNING: sample-based Q-value iteration\n",
              "\n",
              " -  Learn Q(s, a) values as you go (1) receive a sample (s, a, s', r) (2) consider old esimate Q(s, a) (3) consider new sample estimate $sample = R(s, a, s') + \\gamma max_{a'}Q(s', a')$(4) incorporate new estimate into a running average $Q(s, a) \\leftarrow (1- alpha)Q(s, a) + (alpha)[sample]$\n",
              "\n",
              " -  PROPERTIES: converges to optimal policy, even if youre acting suboptimally!\n",
              "\n",
              " -  Called OFF-POLICY LEARNING\n",
              "\n",
              "  - Caveats: (1) have to explore enough (2) have to eventually make learning rate small enough.. but not decrease it too quickly (closer to zero learning rate = keep knowledge of past) (3) in the limit, doesnt matter how u select actions!\n",
              "\n",
              "\n",
              " Q-learning requires exploring in order to learn optimal policy\n",
              "\n",
              " -  To force exploration: random ($\\epsilon$ greedy) or exploration functions \n",
              "\n",
              "  - When to explore? Better idea: explore areas whose badness is not yet established, eventually stop exploring \n",
              "\n",
              "  Exploration function: takes a value estimate u and visit count n, returns optimistic utility $f(u, n) = u + k/n)$ \n",
              "\n",
              "  - (REGULAR Q-UPDATE) $Q(s, a) \\leftarrow_{a} R(s, a, s') + \\gamma max_{a'}Q(s', a')$\n",
              "\n",
              "  - (MODIFIED Q-UPDATE) $Q(s, a) \\leftarrow_{a} R(s, a, s') + \\gamma max_{a'}f(Q(s', a'), N(s',a'))$\n",
              "\n",
              "  - Note: this propagates the \"bonus\" back to states that lead to unknown states as well \n",
              "\n",
              "\n",
              " REGRET: even if u learn optimal policy, still make mistakes along the way\n",
              "\n",
              "  - minimizing regret requires optimally learning to be optimal\n",
              "\n",
              "\n",
              " APPROXIMATE Q-LEARNING\n",
              "\n",
              "  - GENERALIZING ACROSS STATES: basic q-learning keeps a table of all q-values\n",
              "\n",
              "  - In realistic situations, we cannot possibly learn about every single state (1) too many states to vist them all in training (2) too many states to hold the q-tables in memory\n",
              "\n",
              "  - Instead, want to generalize (1) learn about some small num of training states from exp (2) gneeralize that exp to new, similar sitations \n",
              "\n",
              "  - Intuitive interpretation: adjust weights of active features (e.g. if something unexpectedly bad happens, blame all features that were on)\n",
              "\n",
              "  - Formal Justification: online least squares\n",
              "\n",
              "\n",
              " LINEAR VALUE FUNCTION: using a feature representation, we can write a q function (or value function) for any state using few weights\n",
              "\n",
              "  - $V(s) = w_1f_1(s) +... + w_nf_n(s)$\n",
              "\n",
              "  - $Q(s, a) =  w_1f_1(s, a) +... + w_nf_n(s, a)$\n",
              "\n",
              "  - Advantage: our experience is summed up in a few powerful numbers | Disadvantage: states may share features but actually be very different in value\n",
              "\n",
              "\n",
              " EXTRA NOTES \n",
              "\n",
              "  - Q-function in reinforcement learning is action-utility function\n",
              "\n",
              "  - For a partially observable environment, learning problem is more difficult bc next percept is no longer a label for the state prediction problem  \n",
              "\n",
              "  Linear functions: when using perceptron learning rule, weights are updated when the actual output does not match the hypothesis output \n",
              "\n",
              "\n",
              "## Module 9 Definitions\n",
              "* **Exploration** - try unknown actions to get info\n",
              "* **Exploitation** - eventually, have to use what you know\n",
              "* **Regret** - measure of total mistake cost: diff btwn your expected rewards, including youthful suboptimality, and optimal (expected) rewards)\n",
              "* **Difficulty** - learning can be much harder than solving a known MDP\n",
              "* **N-armed bandit** - \n",
              "* **Policy search** - agent learns policy pi(s) that maps directly states to actions (reflex agent)\n",
              "* **Absorbing state** - where no actions have any effect and no rewards are received (IRL, many actions are irreversable)\n",
              "* **Pseudorewards** - additional rewards supplied to speed up learning\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 171,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" \"\"\"\n",
        "chapter12_2 = \"\"\"  \"\"\"\n",
        "chapter12_3 = \"\"\" \"\"\"\n",
        "chapter12_4 = \"\"\"  \"\"\"\n",
        "chapter12_5 = \"\"\" \"\"\"\n",
        "chapter12_6 = \"\"\"  \"\"\"\n",
        "chapter12_7 = \"\"\" \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" \n",
        "\\n The assumption that the probability of a word depends only on the previous word is called a Markov assumption.  \n",
        "\\n n-grams are Markov models that estimate words from a fixed window of previous words. n-gram probabilities can be estimated by counting in a corpus and normalizing (the maximum likelihood estimate) \n",
        "\\n n-gram language models are evaluated extrinsically in some task or intrinsically using perplexity\n",
        "\\n \"\"\"\n",
        "SLP_chapter3_2 = \"\"\"  \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" \"\"\"\n",
        "SLP_chapter3_4 = \"\"\"  \"\"\"\n",
        "SLP_chapter3_5 = \"\"\"  \"\"\"\n",
        "SLP_chapter3_7 = \"\"\"   \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "UNCERTAINTY\n",
        "\\n  - Observed Variables (evidence): agent knows certain things about state of world (e.g. sensor readings) \n",
        "\\n  - Unobserved Variables (states): agent needs to reason about other aspects (e.g. where object is) \n",
        "\\n  - Model:agnet knows somethign about how the known variables relate to the unknown variables \n",
        "\\n  - Joint distribution (e.g. $P(X_1=x_1, X_2=x_2)$) - can calculate the probability of an event\n",
        "\\n  - Marginal Distributions are sumtables which elimiate variables (Marginalization=summing out: combine collapsed rows by adding)\n",
        "\\n  - Conditional Probabilities; simple relation between joint and conditional probabilities\n",
        "\n",
        "\\n  PROBABILISTIC INFERENCE: compute a desired probability from other known probabilities (e.g conditional from joint)\n",
        "\\n  - We general compute conditional probabilities (represent the agent's belieefs given the evidence) \n",
        "\\n  - Probabilities change with new evidence (observing new evidence causes beliefs to be updated)\n",
        "\n",
        "\\n INFERENCE BY ENUMERATION: we want $P(Q|e_1...e_k)$\n",
        "\\n  - (1) Select entries consistent w/evidence (2) Sum out hidden variables to get joint of query and evidence (3) normalize \n",
        "\n",
        "\\n CHAIN RULE: write any joint distribution as an incremental product of conditional distributions \n",
        "\\n  - $P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2) $\n",
        "\\n  - = $P(x_1,..., x_n)\\prod_{i}^{} P(x_i|x_i....x_{i-1})$\n",
        "\\n Bayes' Rule\n",
        "\\n  - $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
        "\n",
        "\\n PROBABILISTIC LANGUAGE MODELS: goal-assign a probability to a sentence\n",
        "\\n  - (1) autocomplete for texting (2) machine translation (3) spelling correction (4) speech recognition\n",
        "\\n PROBABILISTIC LANGUAGE MODELING: \n",
        "\\n  - Goal: compute probability of a sentence or seq of words $P(W) = P(w_1...w_n)$\n",
        "\\n  - Related Task: probability of an upcoming word $P(w_5|w_1...w_4)$\n",
        "\\n  - Model that computes either of these, $P(W) or P(w_n | w_1...w_{n-1}) is a LANGUAGE MODEL$\n",
        "\\n  - Compute this joint probability using chain rule \n",
        "\n",
        "\\n CHAIN RULE\n",
        "\\n  - Recall: P(B|A) = P(A, B) / P(A) ---> P(A, B) = P(A)P(B|A) \n",
        "\\n -  Chain rule in general: $P(x_1, x_2,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x1, x2)..P(x_n|x1...xn-1)$\n",
        "\\n  - Joint prob of words in a sentence: $P(w1w2w3..wn) = prod_{i}^{} P(w_i|w_1w_2...w_{i-1})$\n",
        "\n",
        "\\n EXTRA NOTES:\n",
        "\\n -  If process is stationary, the conditional probability table does not change over time \n",
        "\\n -  Dynamic Bayesian Model (DBN), uncessary for construction: multiple state and evidence variables\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"random variable\" : \"some aspect of the world about which we (may) have uncertainty\",\n",
        "\"joint distribution\" : \"over a set of random variables specifies a real number for each assignment (or outcome)\",\n",
        "\"event\" : \"set E of outcomes\",\n",
        "\"conditional distribution\":\"probabilities distributions over some variabels given fixed values of others\",\n",
        "\"perplexity\":\"of a model P on a sequence of words W is 2 raised to the power of this cross-entropy\",\n",
        "\"perplexity\": \"of a test set according to a lang model is the geometric mean of the inverse test set probability computed by the model \"\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 172,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1677
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "b75e92fa-0964-49e2-e995-f98e20e70170"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 10: Probabilies and Language Models\n",
              "## AIMA Chapter 12.1 Acting under Uncertainty\n",
              " \n",
              "\n",
              "## AIMA Chapter 12.2 Basic Probability Notation\n",
              "  \n",
              "\n",
              "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
              " \n",
              "\n",
              "## AIMA Chapter 12.4 Independence\n",
              "  \n",
              "\n",
              "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
              " \n",
              "\n",
              "## AIMA Chapter 12.6 Naive Bayes Models\n",
              "  \n",
              "\n",
              "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
              " \n",
              "\n",
              "## SLP Chapter 3.1 N-Grams\n",
              " \n",
              "\n",
              " The assumption that the probability of a word depends only on the previous word is called a Markov assumption.  \n",
              "\n",
              " n-grams are Markov models that estimate words from a fixed window of previous words. n-gram probabilities can be estimated by counting in a corpus and normalizing (the maximum likelihood estimate) \n",
              "\n",
              " n-gram language models are evaluated extrinsically in some task or intrinsically using perplexity\n",
              "\n",
              " \n",
              "\n",
              "## SLP Chapter 3.2 Evaluating Language Models\n",
              "  \n",
              "\n",
              "## SLP Chapter 3.3 Sampling sentences from a language model\n",
              " \n",
              "\n",
              "## SLP Chapter 3.4 Generalization and Zeros\n",
              "  \n",
              "\n",
              "## SLP Chapter 3.5 Smoothing\n",
              "  \n",
              "\n",
              "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
              "   \n",
              "\n",
              "## Module 10 Lecture Notes\n",
              " \n",
              "UNCERTAINTY\n",
              "\n",
              "  - Observed Variables (evidence): agent knows certain things about state of world (e.g. sensor readings) \n",
              "\n",
              "  - Unobserved Variables (states): agent needs to reason about other aspects (e.g. where object is) \n",
              "\n",
              "  - Model:agnet knows somethign about how the known variables relate to the unknown variables \n",
              "\n",
              "  - Joint distribution (e.g. $P(X_1=x_1, X_2=x_2)$) - can calculate the probability of an event\n",
              "\n",
              "  - Marginal Distributions are sumtables which elimiate variables (Marginalization=summing out: combine collapsed rows by adding)\n",
              "\n",
              "  - Conditional Probabilities; simple relation between joint and conditional probabilities\n",
              "\n",
              "\n",
              "  PROBABILISTIC INFERENCE: compute a desired probability from other known probabilities (e.g conditional from joint)\n",
              "\n",
              "  - We general compute conditional probabilities (represent the agent's belieefs given the evidence) \n",
              "\n",
              "  - Probabilities change with new evidence (observing new evidence causes beliefs to be updated)\n",
              "\n",
              "\n",
              " INFERENCE BY ENUMERATION: we want $P(Q|e_1...e_k)$\n",
              "\n",
              "  - (1) Select entries consistent w/evidence (2) Sum out hidden variables to get joint of query and evidence (3) normalize \n",
              "\n",
              "\n",
              " CHAIN RULE: write any joint distribution as an incremental product of conditional distributions \n",
              "\n",
              "  - $P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2) $\n",
              "\n",
              "  - = $P(x_1,..., x_n)\\prod_{i}^{} P(x_i|x_i....x_{i-1})$\n",
              "\n",
              " Bayes' Rule\n",
              "\n",
              "  - $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
              "\n",
              "\n",
              " PROBABILISTIC LANGUAGE MODELS: goal-assign a probability to a sentence\n",
              "\n",
              "  - (1) autocomplete for texting (2) machine translation (3) spelling correction (4) speech recognition\n",
              "\n",
              " PROBABILISTIC LANGUAGE MODELING: \n",
              "\n",
              "  - Goal: compute probability of a sentence or seq of words $P(W) = P(w_1...w_n)$\n",
              "\n",
              "  - Related Task: probability of an upcoming word $P(w_5|w_1...w_4)$\n",
              "\n",
              "  - Model that computes either of these, $P(W) or P(w_n | w_1...w_{n-1}) is a LANGUAGE MODEL$\n",
              "\n",
              "  - Compute this joint probability using chain rule \n",
              "\n",
              "\n",
              " CHAIN RULE\n",
              "\n",
              "  - Recall: P(B|A) = P(A, B) / P(A) ---> P(A, B) = P(A)P(B|A) \n",
              "\n",
              " -  Chain rule in general: $P(x_1, x_2,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x1, x2)..P(x_n|x1...xn-1)$\n",
              "\n",
              "  - Joint prob of words in a sentence: $P(w1w2w3..wn) = prod_{i}^{} P(w_i|w_1w_2...w_{i-1})$\n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              " -  If process is stationary, the conditional probability table does not change over time \n",
              "\n",
              " -  Dynamic Bayesian Model (DBN), uncessary for construction: multiple state and evidence variables\n",
              "\n",
              "\n",
              "\n",
              "## Module 10 Definitions\n",
              "* **Random variable** - some aspect of the world about which we (may) have uncertainty\n",
              "* **Joint distribution** - over a set of random variables specifies a real number for each assignment (or outcome)\n",
              "* **Event** - set E of outcomes\n",
              "* **Conditional distribution** - probabilities distributions over some variabels given fixed values of others\n",
              "* **Perplexity** - of a test set according to a lang model is the geometric mean of the inverse test set probability computed by the model \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 173,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\"  \"\"\"\n",
        "chapter13_2 = \"\"\"   \"\"\"\n",
        "chapter13_3 = \"\"\" the time and space complexity of exact inference in polytrees is linear in the size of the network \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" AI agent that uses probabilistic model can make inferences about the world\n",
        "\\n Bayes Nets: graphical models where nodes in graph represent variables and probabalistic model and the arcs represent the relationship between the diff variables in our model\n",
        "\\n - much more compact representation where we've got a smaller num of probability tables that will have to estimate and populate \n",
        "\\n  - x and y are independent if the joint probability is equal to the two marginal probabilities of X and Y (P(x) * P(y))\n",
        "\\n CONDITIONAL INDEPENDENCE: X and Y are C.I. given Z: $P(x, y|z) = P(x|z)P(y|z)\n",
        "\\n  - Unconditional (absolute) independence is very rare and doesnt help us make inferences about other variables$\n",
        "\n",
        "\\n BAYES NETS ASSUMPTIONS: $P(x_i|x_1...x_{i-1}) = P(x_i|parents(X_i))$\n",
        "\\n  - Beyond the chain rule->bayes net conditional independence assumptions, there are often additional conditional independences and can be read off the graph\n",
        "\\n  - Important tool for us to model how we think the world works\n",
        "\\n D-SEPARATION: D=descendents, allows us to study the independent properties of triples in our graph\n",
        "\\n - Any complex BN e.g. can be broken down into repetiations of the 3 cases to check if 2 vars are independent\n",
        "\\n - 1. Causal Chain (Z->Y->Z)\n",
        "\\n - X not guaranteed independent of Z, but is if Z given Y\n",
        "\\n - 2. Common Cause (X<-Y->Z)\n",
        "\\n - X not guaranteed independent of Z since both due to Y\n",
        "\\n - X is guar. ind. of Z given Y\n",
        "\\n - 3. Common Effect (X->Z<-Y)\n",
        "\\n - X and Y independent\n",
        "\\n - X and Y not guaranteed independent of Z\n",
        "\n",
        "\\n ARE TWO VARIABLES IN A BN INDEPENDENT?\n",
        "\\n  - Soln: analze the graph. Any complex example can be broken into repetitions of the three canonical cases \n",
        "\\n  - A path is active if each triple is active\n",
        "\\n  - If all paths are inactive, then independence is guarenteed\n",
        "\n",
        "\\n INFERENCE (we want to make some inferences about the world, given some partial observations)\n",
        "\\n INFERENCE BY ENUMERATION \n",
        "\\n -  General Case: evidence variables, query* variables, hidden variables \n",
        "\\n -  We want $P(Q|e_1...e_k)$\n",
        "\\n -  (1) Select the entries consistent with the evidence (2) Sum out H to get joint of Query and evidence (3) Normalize \n",
        "\\n -  Given unlimited time, inference in BNs is easy \n",
        "\\n -  A query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network\n",
        "\n",
        "\n",
        "\\n INFERENCE BY ENUMERATION vs VARIABLE ELIMIR\n",
        "\\n -  Why is inf by enum slow? You join up the whole joint distribution before you sum out the hidden variables\n",
        "\\n -  Advanced technique: variable elimination - interleave joining and marignalizing - still NP-hard but much faster \n",
        "\n",
        "\\n Nice thing, bayesian networks allows us to make some indenpendent assumptions to simplify the process of making those inferences and to simplify our modeling in such a way that we could understnad the relationship between different parts of our model\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module11_definitions = {\n",
        "\"inference\" : \"calculating some useful quantity from a joint probability distribution\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 174,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1178
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "8f902e08-a67a-467f-b918-3866a9455645"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
              "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
              "  \n",
              "\n",
              "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
              "   \n",
              "\n",
              "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
              " the time and space complexity of exact inference in polytrees is linear in the size of the network \n",
              "\n",
              "## Module 11 Lecture Notes\n",
              " AI agent that uses probabilistic model can make inferences about the world\n",
              "\n",
              " Bayes Nets: graphical models where nodes in graph represent variables and probabalistic model and the arcs represent the relationship between the diff variables in our model\n",
              "\n",
              " - much more compact representation where we've got a smaller num of probability tables that will have to estimate and populate \n",
              "\n",
              "  - x and y are independent if the joint probability is equal to the two marginal probabilities of X and Y (P(x) * P(y))\n",
              "\n",
              " CONDITIONAL INDEPENDENCE: X and Y are C.I. given Z: $P(x, y|z) = P(x|z)P(y|z)\n",
              "\n",
              "  - Unconditional (absolute) independence is very rare and doesnt help us make inferences about other variables$\n",
              "\n",
              "\n",
              " BAYES NETS ASSUMPTIONS: $P(x_i|x_1...x_{i-1}) = P(x_i|parents(X_i))$\n",
              "\n",
              "  - Beyond the chain rule->bayes net conditional independence assumptions, there are often additional conditional independences and can be read off the graph\n",
              "\n",
              "  - Important tool for us to model how we think the world works\n",
              "\n",
              " D-SEPARATION: D=descendents, allows us to study the independent properties of triples in our graph\n",
              "\n",
              " - Any complex BN e.g. can be broken down into repetiations of the 3 cases to check if 2 vars are independent\n",
              "\n",
              " - 1. Causal Chain (Z->Y->Z)\n",
              "\n",
              " - X not guaranteed independent of Z, but is if Z given Y\n",
              "\n",
              " - 2. Common Cause (X<-Y->Z)\n",
              "\n",
              " - X not guaranteed independent of Z since both due to Y\n",
              "\n",
              " - X is guar. ind. of Z given Y\n",
              "\n",
              " - 3. Common Effect (X->Z<-Y)\n",
              "\n",
              " - X and Y independent\n",
              "\n",
              " - X and Y not guaranteed independent of Z\n",
              "\n",
              "\n",
              " ARE TWO VARIABLES IN A BN INDEPENDENT?\n",
              "\n",
              "  - Soln: analze the graph. Any complex example can be broken into repetitions of the three canonical cases \n",
              "\n",
              "  - A path is active if each triple is active\n",
              "\n",
              "  - If all paths are inactive, then independence is guarenteed\n",
              "\n",
              "\n",
              " INFERENCE (we want to make some inferences about the world, given some partial observations)\n",
              "\n",
              " INFERENCE BY ENUMERATION \n",
              "\n",
              " -  General Case: evidence variables, query* variables, hidden variables \n",
              "\n",
              " -  We want $P(Q|e_1...e_k)$\n",
              "\n",
              " -  (1) Select the entries consistent with the evidence (2) Sum out H to get joint of Query and evidence (3) Normalize \n",
              "\n",
              " -  Given unlimited time, inference in BNs is easy \n",
              "\n",
              " -  A query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network\n",
              "\n",
              "\n",
              "\n",
              " INFERENCE BY ENUMERATION vs VARIABLE ELIMIR\n",
              "\n",
              " -  Why is inf by enum slow? You join up the whole joint distribution before you sum out the hidden variables\n",
              "\n",
              " -  Advanced technique: variable elimination - interleave joining and marignalizing - still NP-hard but much faster \n",
              "\n",
              "\n",
              " Nice thing, bayesian networks allows us to make some indenpendent assumptions to simplify the process of making those inferences and to simplify our modeling in such a way that we could understnad the relationship between different parts of our model\n",
              "\n",
              "\n",
              "\n",
              "## Module 11 Definitions\n",
              "* **Inference** - calculating some useful quantity from a joint probability distribution\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 175,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\"   \"\"\"\n",
        "chapter19_2 = \"\"\"  \"\"\"\n",
        "chapter19_3 = \"\"\"  \"\"\"\n",
        "chapter19_4 = \"\"\"  \"\"\"\n",
        "chapter19_5 = \"\"\"   \"\"\"\n",
        "chapter19_6 = \"\"\"   \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\"   \"\"\"\n",
        "slp_chapter4_2 = \"\"\"   \"\"\"\n",
        "slp_chapter4_3 = \"\"\"   \"\"\"\n",
        "slp_chapter4_4 = \"\"\"   \"\"\"\n",
        "slp_chapter4_5 = \"\"\"   \"\"\"\n",
        "slp_chapter4_6 = \"\"\"   \"\"\"\n",
        "slp_chapter4_7 = \"\"\" \"\"\"\n",
        "slp_chapter4_8 = \"\"\" \"\"\"\n",
        "slp_chapter4_9 = \"\"\"  \"\"\"\n",
        "slp_chapter4_10 = \"\"\"  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" Perceptrons learn differently than a naive Bayes classifier\n",
        "\\n -  Rather than learning a set of probabilities, perceptron have a weight associated with each feature that they use for their classification decision every time they make a misclassification decision on an item in teh training set, perceptron update their weights in order to better classify that example\n",
        "\\n  - Up until now: how to use a model to make optimal decisions\n",
        "\\n Machine Learning: How to aquire a model from data/exp (1) learning params (e.g probabilties)(2) learning structure (e.g. BN graphs) (3) learning hidden concepts (e.g. clustering) \n",
        "\\n MODEL BASED CLASSIFICATION \n",
        "\\n  - Approach (1) build a model (e.g. bayes net) where both the label and features are random variables (2) instantiate any observed features (3) query for the distribution of the label conditioned on the features\n",
        "\\n GENERAL NAIVE BAYES\n",
        "\\n  - $P(Y, F_1, ... F_n) = P(Y)\\prod_{i}{}P(F_i|Y)$\n",
        "\\n INFERENCE FOR NAIVE BAYES\n",
        "\\n -  Goal: compute posterior distribution over label variable Y \n",
        "\\n  - (1) get joint probability of label and evidence for each label (2) sum to get probability of evidence (3) normalize by dividing step 1 by step 2\n",
        "\\n -  What do we need in order to use naive bayes? (1) inference method (2) estimates of local conditional probability tables\n",
        "\\n CONCEPTS FOR ML \n",
        "\\n  - Data: labeled instances (e.g.) emails marked spam \n",
        "\\n  - training, held out, test set\n",
        "\\n  - Features: attribute-value pairs which characterize each x\n",
        "\\n  - Experimentation cycle\n",
        "\\n -  Learn parameters (e.g. model probabilities on training set), tune hyperparameters on held-out set, compute accuracy of test set, never peek at test set!\n",
        "\\n -  Evaluation - accuracy: fraction of instances predicted correctly\n",
        "\\n -  Overfitting and generalization \n",
        "\\n -  want a classifier which does well on test data\n",
        "\\n -  Overfitting: fitting training data closely, but not generalizing well\n",
        "\\n GENERALIZATION AND OVERFITTING \n",
        "\\n -  Relative freq parameters will overfit the training data\n",
        "\\n  - As an extreme case, imagine using entire email as only feature\n",
        "\\n  - To generalize better, we need to smooth or regularize the estimates\n",
        "\\n PARAMETER ESTIMATION: estimating the distribution of a random variable\n",
        "\\n -  Elicitation: ask a human / expert\n",
        "\\n -  Expirically: use training data (learning) -> e.g. for each outcome x, look at empirical rate of that value (count(x) / total samples). multiply probabilities to get estimate of maximizing the likelihood of the data\n",
        "\\n MAXIMUM LIKELIHOOD\n",
        "\\n -  Relative freqs are the maximum likelihood estimates \n",
        "\\n LAPLACE SMOOTHING (one way to avoid zero probabilities)\n",
        "\\n -  Laplace's estimate: pretend you saw every outcome once more than actuality (E.G. if you see 2 red, 3 blue, maximum likelihood estimate is 2/3 for red, 1/3 blue. laplacian estimate is 3/5 red, 2/5 blue)\n",
        "\\n ESTIMATION: LINEAR INTERPOLATION (another way to avoid zero probabilities) \n",
        "\\n -  Also get the empirical P(X) from the data. make sure the estimate of P(X|Y) isnt too different from empirical P(X)\n",
        "\\n -  in practice, laplace often performs poorly for P(X|Y) if |X| or |Y| is very large\n",
        "\n",
        "\\n How do we pick the best parameterization of our models and then how do we pick the best estimates of our model parameters, values of hyperparams\n",
        "\\n TUNING ON HELD-OUT DATA\n",
        "\\n  - 2 unknowns: Parameters: the probabilities P(X|Y), P(Y). Hyperparameters: e.g. the amount/type of smoothing to do, k, alpha\n",
        "\\n What should we learn where?\n",
        "\\n -  (1) Learn parameters from training data (2) tune hyperparams on different data (3) for each val of hyperparameters, train and test on held-out data (4) choose the best value and do a final test on test data \n",
        "\\n WHAT TO DO ABOUT ERRORS\n",
        "\\n  - More features! \n",
        "\\n BASELINES (if our classifier is getting good accuracy, we actually need to put that into perspective)\n",
        "\\n  - (1) get a baseline. very simple straw  man procedures. help determine how hard a task is, help know what \"good\" accuracy is\n",
        "\\n  - Weak baseline: most frequent label classifier. for real research, use previous work as a strong baseline\n",
        "\n",
        "\\n SUMMARY\n",
        "\\n  - (1) Bayes rule lets us do diagnostic queries with causal probabilities (2) naive bayes assumption takes all feature to be independent given the class label (3) we can build classifiers out of a naive Bayes model using training data (4) smoothing esimates is important in real systems (4) classifier confidences are useful when you can get them \n",
        "\n",
        "\\n PERCEPTRON\n",
        "\\n  - idea of accepting a bunch of inputs and combining them somehow into an activation function and transmitting a signal onwards (mathematical representation) \n",
        "\\n  - Learning: binary perceptron \n",
        "\\n  - (1) start with weights = 0. for each training instance, classify w current weights. if correct (i.e. y=y*), no change. if wrong, adjust weight vector\n",
        "\n",
        "\\n MULTICLASS DECISION RULE\n",
        "\\n  - if multiple classes, weight vector for each class( $w_y$). score of a class y ($w_y f(x)$). prediction highest score wins ($y = arg_y max w_y f(x)$)\n",
        "\\n PROPERTIES OF PERCEPTRONS\n",
        "\\n  - Separability: true if some params get the training set perfectly correct\n",
        "\\n  - Convergence: if training is separable, perceptron will eventually converge (binary case) \n",
        "\\n  - Mistake bound: max num of mistakes (binary case) related to the margin or degree of separability ($mistakes \\lt k/\\delta^2$)\n",
        "\n",
        "\\n PROBLEMS W PERCEPTRON\n",
        "\\n  - Noise: if data isnt separable, weights might thrash. (avging weight vectors over time can help (avged perceptron)) \n",
        "\\n  - Mediocre generalization: finds a \"barely\" separating soln\n",
        "\\n  - Overtraining: test/held-out accuracy usually rises, then falls. overtraining is a kind of overfitting \n",
        "\n",
        "\\n FIXING THE PERCEPTRON\n",
        "\\n -  Idea: adjust weight update to mitigate these effects\n",
        "\\n MAXIMUM STEP SIZE\n",
        "\\n  - In practice, also bad to make updates too large (e.g. may be labeled incorrectly, mght not have enough features )\n",
        "\\n SOLN: cap max possible value of $tau$ w some constant C\n",
        "\\n -  tau corresponds to an optimization that assumes non seperable data. usually converges faster than perceptron. usually better, especially on noisy data\n",
        "\\n SUPPORT VECTOR MACHINES\n",
        "\\n  - Maximizing the margin: good according to intuition, theory, practice\n",
        "\\n  - Only support vectors matter; other training examples are ignorable\n",
        "\\n  - Support vector machines (SVMs) find the separator with max margin \n",
        "\n",
        "\\n CLASSIFICATION COMPARISON\n",
        "\\n  - Naive Bayes (1) builds a model training data (2) gives prediction probabilities (3) strong assumptions about feature independence (4) one pass through data (counting)\n",
        "\\n  - Perceptrons / MIRA: (1) makes less assumptions about data (2) mistake-driven learning (3) multiple passes through data (prediction) (4) often more accurate \n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"naive bayes\" : \"assume all features are independent effects of the label\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 176,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2808
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "2a7ffc08-dde6-4967-a58f-a7b2b47e1281"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 12: Naive Bayes and Perceptrons\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "   \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "  \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "   \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.3 Worked Example\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
              " \n",
              "\n",
              "## SLP Chapter 4.8 Test sets and Cross-validation\n",
              " \n",
              "\n",
              "## SLP Chapter 4.9 Statistical Significance Testing\n",
              "  \n",
              "\n",
              "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
              "  \n",
              "\n",
              "## Module 12 Lecture Notes\n",
              " Perceptrons learn differently than a naive Bayes classifier\n",
              "\n",
              " -  Rather than learning a set of probabilities, perceptron have a weight associated with each feature that they use for their classification decision every time they make a misclassification decision on an item in teh training set, perceptron update their weights in order to better classify that example\n",
              "\n",
              "  - Up until now: how to use a model to make optimal decisions\n",
              "\n",
              " Machine Learning: How to aquire a model from data/exp (1) learning params (e.g probabilties)(2) learning structure (e.g. BN graphs) (3) learning hidden concepts (e.g. clustering) \n",
              "\n",
              " MODEL BASED CLASSIFICATION \n",
              "\n",
              "  - Approach (1) build a model (e.g. bayes net) where both the label and features are random variables (2) instantiate any observed features (3) query for the distribution of the label conditioned on the features\n",
              "\n",
              " GENERAL NAIVE BAYES\n",
              "\n",
              "  - $P(Y, F_1, ... F_n) = P(Y)\\prod_{i}{}P(F_i|Y)$\n",
              "\n",
              " INFERENCE FOR NAIVE BAYES\n",
              "\n",
              " -  Goal: compute posterior distribution over label variable Y \n",
              "\n",
              "  - (1) get joint probability of label and evidence for each label (2) sum to get probability of evidence (3) normalize by dividing step 1 by step 2\n",
              "\n",
              " -  What do we need in order to use naive bayes? (1) inference method (2) estimates of local conditional probability tables\n",
              "\n",
              " CONCEPTS FOR ML \n",
              "\n",
              "  - Data: labeled instances (e.g.) emails marked spam \n",
              "\n",
              "  - training, held out, test set\n",
              "\n",
              "  - Features: attribute-value pairs which characterize each x\n",
              "\n",
              "  - Experimentation cycle\n",
              "\n",
              " -  Learn parameters (e.g. model probabilities on training set), tune hyperparameters on held-out set, compute accuracy of test set, never peek at test set!\n",
              "\n",
              " -  Evaluation - accuracy: fraction of instances predicted correctly\n",
              "\n",
              " -  Overfitting and generalization \n",
              "\n",
              " -  want a classifier which does well on test data\n",
              "\n",
              " -  Overfitting: fitting training data closely, but not generalizing well\n",
              "\n",
              " GENERALIZATION AND OVERFITTING \n",
              "\n",
              " -  Relative freq parameters will overfit the training data\n",
              "\n",
              "  - As an extreme case, imagine using entire email as only feature\n",
              "\n",
              "  - To generalize better, we need to smooth or regularize the estimates\n",
              "\n",
              " PARAMETER ESTIMATION: estimating the distribution of a random variable\n",
              "\n",
              " -  Elicitation: ask a human / expert\n",
              "\n",
              " -  Expirically: use training data (learning) -> e.g. for each outcome x, look at empirical rate of that value (count(x) / total samples). multiply probabilities to get estimate of maximizing the likelihood of the data\n",
              "\n",
              " MAXIMUM LIKELIHOOD\n",
              "\n",
              " -  Relative freqs are the maximum likelihood estimates \n",
              "\n",
              " LAPLACE SMOOTHING (one way to avoid zero probabilities)\n",
              "\n",
              " -  Laplace's estimate: pretend you saw every outcome once more than actuality (E.G. if you see 2 red, 3 blue, maximum likelihood estimate is 2/3 for red, 1/3 blue. laplacian estimate is 3/5 red, 2/5 blue)\n",
              "\n",
              " ESTIMATION: LINEAR INTERPOLATION (another way to avoid zero probabilities) \n",
              "\n",
              " -  Also get the empirical P(X) from the data. make sure the estimate of P(X|Y) isnt too different from empirical P(X)\n",
              "\n",
              " -  in practice, laplace often performs poorly for P(X|Y) if |X| or |Y| is very large\n",
              "\n",
              "\n",
              " How do we pick the best parameterization of our models and then how do we pick the best estimates of our model parameters, values of hyperparams\n",
              "\n",
              " TUNING ON HELD-OUT DATA\n",
              "\n",
              "  - 2 unknowns: Parameters: the probabilities P(X|Y), P(Y). Hyperparameters: e.g. the amount/type of smoothing to do, k, alpha\n",
              "\n",
              " What should we learn where?\n",
              "\n",
              " -  (1) Learn parameters from training data (2) tune hyperparams on different data (3) for each val of hyperparameters, train and test on held-out data (4) choose the best value and do a final test on test data \n",
              "\n",
              " WHAT TO DO ABOUT ERRORS\n",
              "\n",
              "  - More features! \n",
              "\n",
              " BASELINES (if our classifier is getting good accuracy, we actually need to put that into perspective)\n",
              "\n",
              "  - (1) get a baseline. very simple straw  man procedures. help determine how hard a task is, help know what \"good\" accuracy is\n",
              "\n",
              "  - Weak baseline: most frequent label classifier. for real research, use previous work as a strong baseline\n",
              "\n",
              "\n",
              " SUMMARY\n",
              "\n",
              "  - (1) Bayes rule lets us do diagnostic queries with causal probabilities (2) naive bayes assumption takes all feature to be independent given the class label (3) we can build classifiers out of a naive Bayes model using training data (4) smoothing esimates is important in real systems (4) classifier confidences are useful when you can get them \n",
              "\n",
              "\n",
              " PERCEPTRON\n",
              "\n",
              "  - idea of accepting a bunch of inputs and combining them somehow into an activation function and transmitting a signal onwards (mathematical representation) \n",
              "\n",
              "  - Learning: binary perceptron \n",
              "\n",
              "  - (1) start with weights = 0. for each training instance, classify w current weights. if correct (i.e. y=y*), no change. if wrong, adjust weight vector\n",
              "\n",
              "\n",
              " MULTICLASS DECISION RULE\n",
              "\n",
              "  - if multiple classes, weight vector for each class( $w_y$). score of a class y ($w_y f(x)$). prediction highest score wins ($y = arg_y max w_y f(x)$)\n",
              "\n",
              " PROPERTIES OF PERCEPTRONS\n",
              "\n",
              "  - Separability: true if some params get the training set perfectly correct\n",
              "\n",
              "  - Convergence: if training is separable, perceptron will eventually converge (binary case) \n",
              "\n",
              "  - Mistake bound: max num of mistakes (binary case) related to the margin or degree of separability ($mistakes \\lt k/\\delta^2$)\n",
              "\n",
              "\n",
              " PROBLEMS W PERCEPTRON\n",
              "\n",
              "  - Noise: if data isnt separable, weights might thrash. (avging weight vectors over time can help (avged perceptron)) \n",
              "\n",
              "  - Mediocre generalization: finds a \"barely\" separating soln\n",
              "\n",
              "  - Overtraining: test/held-out accuracy usually rises, then falls. overtraining is a kind of overfitting \n",
              "\n",
              "\n",
              " FIXING THE PERCEPTRON\n",
              "\n",
              " -  Idea: adjust weight update to mitigate these effects\n",
              "\n",
              " MAXIMUM STEP SIZE\n",
              "\n",
              "  - In practice, also bad to make updates too large (e.g. may be labeled incorrectly, mght not have enough features )\n",
              "\n",
              " SOLN: cap max possible value of $tau$ w some constant C\n",
              "\n",
              " -  tau corresponds to an optimization that assumes non seperable data. usually converges faster than perceptron. usually better, especially on noisy data\n",
              "\n",
              " SUPPORT VECTOR MACHINES\n",
              "\n",
              "  - Maximizing the margin: good according to intuition, theory, practice\n",
              "\n",
              "  - Only support vectors matter; other training examples are ignorable\n",
              "\n",
              "  - Support vector machines (SVMs) find the separator with max margin \n",
              "\n",
              "\n",
              " CLASSIFICATION COMPARISON\n",
              "\n",
              "  - Naive Bayes (1) builds a model training data (2) gives prediction probabilities (3) strong assumptions about feature independence (4) one pass through data (counting)\n",
              "\n",
              "  - Perceptrons / MIRA: (1) makes less assumptions about data (2) mistake-driven learning (3) multiple passes through data (prediction) (4) often more accurate \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 12 Definitions\n",
              "* **Naive bayes** - assume all features are independent effects of the label\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 177,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\"   \"\"\"\n",
        "slp_chapter5_2 = \"\"\"  \"\"\"\n",
        "slp_chapter5_3 = \"\"\"   \"\"\"\n",
        "slp_chapter5_4 = \"\"\"  \"\"\"\n",
        "slp_chapter5_5 = \"\"\"   \"\"\"\n",
        "slp_chapter5_6 = \"\"\" \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\"   \"\"\"\n",
        "slp_chapter7_2 = \"\"\"   \"\"\"\n",
        "slp_chapter7_3 = \"\"\"  \"\"\"\n",
        "slp_chapter7_4 = \"\"\"  \"\"\"\n",
        "slp_chapter7_5 = \"\"\"  \"\"\"\n",
        "slp_chapter7_6 = \"\"\" \"\"\"\n",
        "slp_chapter7_7 = \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" The basic neural units that are used in neural networks are similar to the Perceptron \n",
        "\\n Both have set of weights and bias terms that are automatically learned from data \n",
        "\\n Can think of a neural network as a bunch of stacked perceptron. Early NN were called Multilayer perceptron \n",
        "\\n NN use a loss function \n",
        "\\n When updating the weights, need to attribute which of the weights from which parts of the neural network structure caused the error\n",
        "\\n bc the NN has many stacked hidden layers, this can be tricky. Soln - Backpropagation! Uses differentiation over the network to undersand how each neural unit is affected by the ones it is connected to\n",
        "\\n Neural Architectures: refer to how the neurons in the NN are organized, what kind of structure they form\n",
        "\n",
        "\\n CLASSIFIER COMPONENTS\n",
        "\\n -  ML classifiers require a training corpus of M observations input/output pairs ($x^{(i)}, y^{(i)}$)\n",
        "\\n -  Feature representation of the input. For each input observation $x^{(i)}$, this will be a vector of features [X1, x2..xn]\n",
        "\\n -  Classification function that computes the estimated class y-hat via $p(y|x)$\n",
        "\\n -  Objective function for learning, usually involving minimizing error on training examples \n",
        "\\n -  Algorithm for optimizing the objective function \n",
        "\n",
        "\\n SENTIMENT CLASSIFIER \n",
        "\\n  - Difference between perceptron is that we're gonna change what the range of outputs of our classifier can be\n",
        "\n",
        "\\n LEARNING IN LOGISTIC REGRESSION\n",
        "\\n  - How to get weights of the model? We learn the params (weights + bias) via learning. Requires (1) objective function or loss function that tells us distance between system output and gold output. Will use cross-entropy loss (2) algorithm for optimizing objective function. will use stochastic gradient descent to minimize loss function\n",
        "\n",
        "\\n LOSS FUNCTIONS\n",
        "\\n  - Mean squared error $L_{MSE}(y-hat, y) = 1/2(y-hat-y)^2$\n",
        "\\n  - We use a loss function that prefers the correct class labels of the training example to be more likely\n",
        "\\n -  Conditional maximum likelihood estimation: choose params w, b that maximize the (log) probabilities of the true labels in the training data\n",
        "\\n -  Resulting loss function is the negative log likelihood loss, more commonly called cross entropy loss\n",
        "\\n CROSS-ENTROPY LOSS\n",
        "\\n -  $L_{CE}(y-hat, y) = -logp(y|x) = -[ylogy-hat + (1 - y)log(1-y-hat)]$\n",
        "\\n -  $y-hat = \\sigma (wx) + b$\n",
        "\\n  - Why does minimizing this negative log probability do what we want? We want the loss to be smaller if the model's estimate is close to correct, and we want the loss to be bigger if it is confused\n",
        "\\n -  If prediction is correct, CE loss is lower, else higher\n",
        "\\n LOSS ON ALL TRAINING EXAMPLES\n",
        "\\n -  $logp(training lables) = log \\prod_{i =1}{m}p(y^{(i)}|x^{(i)}) = \\prod_{i =1}{m}logp(y^{(i)}|x^{(i)}) = - \\sum_{i =1}{m}L_{CE}(y-hat^{(i)}|y^{(i)})$\n",
        "\n",
        "\\n FINDING GOOD PARAMETERS\n",
        "\\n  - Gradient descent to find good settings for our weights and bias by minimizing loss function \n",
        "\\n -  finds a min of a function by figuring out which direction the function's slope is rising the most steeply, and moving in the opposite direction\n",
        "\n",
        "\\n LEARNING THE PARAMETERS - HOW TO GET WEIGHTS OF MODEL: if requires: \n",
        "\\n - objective or loss function, use C.E. Loss\n",
        "\\n - alg for optimizing ojective function - use Stoachastic gradient descent to minimize the loss function \n",
        "\n",
        "\\n GLOBAL VS LOCAL MINIMUMS\n",
        "\\n -  for logistic regression, this loss function is conveniently convex\n",
        "\\n -  convex function has just one min, so no local min to get stuck in -> grad desc starting anyway is guarenteed to find min \n",
        "\\n -  Magnitude of amt to move in gradient descent is value of slope weighted by learning rate n\n",
        "\\n -  higher/faster learning rate means we should move w more on each step\n",
        "\n",
        "\\n Derivative of CE-loss is (model's prediction - truth) * val of feature j \n",
        "\n",
        "\\n MINI-BATCH TRAINING\n",
        "\\n  - stochastic gradient descent chooses a single random example at a time and updates weights on that example. as a result the updates can fluctuate\n",
        "\\n -  ALTERNATIVE; batch training, computes gradient over entire dataset - gives better estimate of where to move but takes a long time to compute\n",
        "\\n -  commonly used compromise is min-batch training. batch size can be 512 or 1024 selected often based on computational resourcees. loss is accumulated \n",
        "\\n REGULARIZATION\n",
        "\\n  - In logistic regression, if a feature only occurs in one class, then will get a high weight. \n",
        "\\n  - Regularization is a way to penalize large weights\n",
        "\\n MULTINOMIAL LOGISTIC REGRESSION\n",
        "\\n  - Instead of binary classification, might want more classes - use generalization of sigmoid function called softmax function\n",
        "\n",
        "\\n NEURAL NETWORKS\n",
        "\\n  - Output of one layer is input to another layer. One node output goes into all next layer's nodes\n",
        "\\n  - Like perceptron, logistic regression uses vector of weights and a bias term (dot product z = w*x + b)\n",
        "\\n ACTIVATION FUNCTIONS \n",
        "\\n -  Building neural networks, want an activation function \n",
        "\\n -  3 Commonly used non-linear functions for f: sigmoid, tanh, rectified linear unit ReLU\n",
        "\\n -  The sigmoid function maps the output into range [0,1] and it is differentiable\n",
        "\\n -  The tanh function is a variant of the sigmoid function and maps outlier values toward the mean \n",
        "\\n FEED-FORWARD NN\n",
        "\\n  - Simplest kind of NN. Multilayer network, all units are usually fully-connected, no cycles\n",
        "\\n  - outputs from each layer are passes to units in the next higher layer, and no outputs are passed back to lower layers \n",
        "\n",
        "\\n TRAINING NEURAL NETS\n",
        "\\n  - What do we need? (1) A loss function - cross-entropy loss (2) optimization algo - gradient desc (3) A way of computing the gradient of the loss function - error propagation \n",
        "\\n -  If the neural network is a binary classifier with a sigmoid at the final layer, the loss function is exactly the same as CE-Loss\n",
        "\\n COMPUTING THE GRADIENT\n",
        "\\n -  For deeper networks, computing the gradients requires looking back thru all earlier layers in network, even though the loss is only computed w respect to the output of the network\n",
        "\\n -  Soln: Error Backpropagation Alg\n",
        "\\n COMPUTATION GRAPHS\n",
        "\\n -  Although backpropagation was invented for neural nets, related to general procedure called backward differentiation which depends on computation graphs\n",
        "\\n -  In a forward pass graph, we apply each operation from left to right \n",
        "\\n  - Backward differentiation uses chain rule\n",
        "\n",
        "\\n EXTRA NOTES:\n",
        "\\n  - The result of ReLU for negative numbers is NOT the same as a linear function \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"loss function\" : \"quantifies how wrong the model's predictions are for each item in training \",  \n",
        "\"computation graph\":\"represents the process of computing a mathematical expression, broken down into separate operations (each op a node in graph)\",  \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 178,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2644
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "b7ec0d51-dde1-4798-d236-941b38e13e50"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 13: Neural Networks\n",
              "## SLP Chapter 5.1 Classification: the sigmoid\n",
              "   \n",
              "\n",
              "## SLP Chapter 5.2 Learning in Logistic Regression\n",
              "  \n",
              "\n",
              "## SLP Chapter 5.3 The cross-entropy loss function\n",
              "   \n",
              "\n",
              "## SLP Chapter 5.4 Gradient Descent\n",
              "  \n",
              "\n",
              "## SLP Chapter 5.5 Regularization\n",
              "   \n",
              "\n",
              "## SLP Chapter 5.6 Multinomial logistic regression\n",
              " \n",
              "\n",
              "## SLP Chapter 7.1 Units\n",
              "   \n",
              "\n",
              "## SLP Chapter 7.2 The XOR problem\n",
              "   \n",
              "\n",
              "## SLP Chapter 7.3 Feedforward Neural Networks\n",
              "  \n",
              "\n",
              "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
              "  \n",
              "\n",
              "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
              "  \n",
              "\n",
              "## SLP Chapter 7.6 Training Neural Nets\n",
              " \n",
              "\n",
              "## SLP Chapter 7.7 Training the neural language model\n",
              " \n",
              "\n",
              "## Module 13 Lecture Notes\n",
              " The basic neural units that are used in neural networks are similar to the Perceptron \n",
              "\n",
              " Both have set of weights and bias terms that are automatically learned from data \n",
              "\n",
              " Can think of a neural network as a bunch of stacked perceptron. Early NN were called Multilayer perceptron \n",
              "\n",
              " NN use a loss function \n",
              "\n",
              " When updating the weights, need to attribute which of the weights from which parts of the neural network structure caused the error\n",
              "\n",
              " bc the NN has many stacked hidden layers, this can be tricky. Soln - Backpropagation! Uses differentiation over the network to undersand how each neural unit is affected by the ones it is connected to\n",
              "\n",
              " Neural Architectures: refer to how the neurons in the NN are organized, what kind of structure they form\n",
              "\n",
              "\n",
              " CLASSIFIER COMPONENTS\n",
              "\n",
              " -  ML classifiers require a training corpus of M observations input/output pairs ($x^{(i)}, y^{(i)}$)\n",
              "\n",
              " -  Feature representation of the input. For each input observation $x^{(i)}$, this will be a vector of features [X1, x2..xn]\n",
              "\n",
              " -  Classification function that computes the estimated class y-hat via $p(y|x)$\n",
              "\n",
              " -  Objective function for learning, usually involving minimizing error on training examples \n",
              "\n",
              " -  Algorithm for optimizing the objective function \n",
              "\n",
              "\n",
              " SENTIMENT CLASSIFIER \n",
              "\n",
              "  - Difference between perceptron is that we're gonna change what the range of outputs of our classifier can be\n",
              "\n",
              "\n",
              " LEARNING IN LOGISTIC REGRESSION\n",
              "\n",
              "  - How to get weights of the model? We learn the params (weights + bias) via learning. Requires (1) objective function or loss function that tells us distance between system output and gold output. Will use cross-entropy loss (2) algorithm for optimizing objective function. will use stochastic gradient descent to minimize loss function\n",
              "\n",
              "\n",
              " LOSS FUNCTIONS\n",
              "\n",
              "  - Mean squared error $L_{MSE}(y-hat, y) = 1/2(y-hat-y)^2$\n",
              "\n",
              "  - We use a loss function that prefers the correct class labels of the training example to be more likely\n",
              "\n",
              " -  Conditional maximum likelihood estimation: choose params w, b that maximize the (log) probabilities of the true labels in the training data\n",
              "\n",
              " -  Resulting loss function is the negative log likelihood loss, more commonly called cross entropy loss\n",
              "\n",
              " CROSS-ENTROPY LOSS\n",
              "\n",
              " -  $L_{CE}(y-hat, y) = -logp(y|x) = -[ylogy-hat + (1 - y)log(1-y-hat)]$\n",
              "\n",
              " -  $y-hat = \\sigma (wx) + b$\n",
              "\n",
              "  - Why does minimizing this negative log probability do what we want? We want the loss to be smaller if the model's estimate is close to correct, and we want the loss to be bigger if it is confused\n",
              "\n",
              " -  If prediction is correct, CE loss is lower, else higher\n",
              "\n",
              " LOSS ON ALL TRAINING EXAMPLES\n",
              "\n",
              " -  $logp(training lables) = log \\prod_{i =1}{m}p(y^{(i)}|x^{(i)}) = \\prod_{i =1}{m}logp(y^{(i)}|x^{(i)}) = - \\sum_{i =1}{m}L_{CE}(y-hat^{(i)}|y^{(i)})$\n",
              "\n",
              "\n",
              " FINDING GOOD PARAMETERS\n",
              "\n",
              "  - Gradient descent to find good settings for our weights and bias by minimizing loss function \n",
              "\n",
              " -  finds a min of a function by figuring out which direction the function's slope is rising the most steeply, and moving in the opposite direction\n",
              "\n",
              "\n",
              " LEARNING THE PARAMETERS - HOW TO GET WEIGHTS OF MODEL: if requires: \n",
              "\n",
              " - objective or loss function, use C.E. Loss\n",
              "\n",
              " - alg for optimizing ojective function - use Stoachastic gradient descent to minimize the loss function \n",
              "\n",
              "\n",
              " GLOBAL VS LOCAL MINIMUMS\n",
              "\n",
              " -  for logistic regression, this loss function is conveniently convex\n",
              "\n",
              " -  convex function has just one min, so no local min to get stuck in -> grad desc starting anyway is guarenteed to find min \n",
              "\n",
              " -  Magnitude of amt to move in gradient descent is value of slope weighted by learning rate n\n",
              "\n",
              " -  higher/faster learning rate means we should move w more on each step\n",
              "\n",
              "\n",
              " Derivative of CE-loss is (model's prediction - truth) * val of feature j \n",
              "\n",
              "\n",
              " MINI-BATCH TRAINING\n",
              "\n",
              "  - stochastic gradient descent chooses a single random example at a time and updates weights on that example. as a result the updates can fluctuate\n",
              "\n",
              " -  ALTERNATIVE; batch training, computes gradient over entire dataset - gives better estimate of where to move but takes a long time to compute\n",
              "\n",
              " -  commonly used compromise is min-batch training. batch size can be 512 or 1024 selected often based on computational resourcees. loss is accumulated \n",
              "\n",
              " REGULARIZATION\n",
              "\n",
              "  - In logistic regression, if a feature only occurs in one class, then will get a high weight. \n",
              "\n",
              "  - Regularization is a way to penalize large weights\n",
              "\n",
              " MULTINOMIAL LOGISTIC REGRESSION\n",
              "\n",
              "  - Instead of binary classification, might want more classes - use generalization of sigmoid function called softmax function\n",
              "\n",
              "\n",
              " NEURAL NETWORKS\n",
              "\n",
              "  - Output of one layer is input to another layer. One node output goes into all next layer's nodes\n",
              "\n",
              "  - Like perceptron, logistic regression uses vector of weights and a bias term (dot product z = w*x + b)\n",
              "\n",
              " ACTIVATION FUNCTIONS \n",
              "\n",
              " -  Building neural networks, want an activation function \n",
              "\n",
              " -  3 Commonly used non-linear functions for f: sigmoid, tanh, rectified linear unit ReLU\n",
              "\n",
              " -  The sigmoid function maps the output into range [0,1] and it is differentiable\n",
              "\n",
              " -  The tanh function is a variant of the sigmoid function and maps outlier values toward the mean \n",
              "\n",
              " FEED-FORWARD NN\n",
              "\n",
              "  - Simplest kind of NN. Multilayer network, all units are usually fully-connected, no cycles\n",
              "\n",
              "  - outputs from each layer are passes to units in the next higher layer, and no outputs are passed back to lower layers \n",
              "\n",
              "\n",
              " TRAINING NEURAL NETS\n",
              "\n",
              "  - What do we need? (1) A loss function - cross-entropy loss (2) optimization algo - gradient desc (3) A way of computing the gradient of the loss function - error propagation \n",
              "\n",
              " -  If the neural network is a binary classifier with a sigmoid at the final layer, the loss function is exactly the same as CE-Loss\n",
              "\n",
              " COMPUTING THE GRADIENT\n",
              "\n",
              " -  For deeper networks, computing the gradients requires looking back thru all earlier layers in network, even though the loss is only computed w respect to the output of the network\n",
              "\n",
              " -  Soln: Error Backpropagation Alg\n",
              "\n",
              " COMPUTATION GRAPHS\n",
              "\n",
              " -  Although backpropagation was invented for neural nets, related to general procedure called backward differentiation which depends on computation graphs\n",
              "\n",
              " -  In a forward pass graph, we apply each operation from left to right \n",
              "\n",
              "  - Backward differentiation uses chain rule\n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              "  - The result of ReLU for negative numbers is NOT the same as a linear function \n",
              "\n",
              " \n",
              "\n",
              "## Module 13 Definitions\n",
              "* **Loss function** - quantifies how wrong the model's predictions are for each item in training \n",
              "* **Computation graph** - represents the process of computing a mathematical expression, broken down into separate operations (each op a node in graph)\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 179,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\"   \"\"\"\n",
        "slp_chapter9_2 = \"\"\"  \"\"\"\n",
        "slp_chapter9_3 = \"\"\"  \"\"\"\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",
        "slp_chapter6_2 = \"\"\" \"\"\"\n",
        "slp_chapter6_3 = \"\"\"  \"\"\"\n",
        "slp_chapter6_4 = \"\"\"  \"\"\"\n",
        "slp_chapter6_8 = \"\"\"   \"\"\"\n",
        "slp_chapter6_10 = \"\"\" \"\"\"\n",
        "slp_chapter6_11 = \"\"\" \"\"\"\n",
        "slp_chapter6_12 = \"\"\"  \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" Neural Language Models advantages over n-gram LMs\n",
        "\\n  - 1. No smoothing needed 2. Can handle much longer historiess 3. Can generalize over contexts of similar words 4. Neural LMs tend to have higher predictive accuracy than n-gram LMs \n",
        "\\n  - Disadvantage: slower to train than traditional n-gram LMs \n",
        "\\n NEURAL LMs\n",
        "\\n  - 1. Associate each word in the vocab w a vector-representation, theyby creating notion of similarity btw words 2. Express joint probability function of a word seq in terms of word vectors for the words in that sequence 3. Simultaneously learn the word vectors and the parameters of teh function \n",
        "\\n  - Word vectors are dim=30-100 dense, low dim. The probability func is expressed as the product of conditional probabilities of the next word given the previous word, using a multi-layer, feed forward neural network\n",
        "\\n  - Input: k-gram of words $w_{1:k}$, Output: Probability idstribution over next word\n",
        "\\n  - $k$ context words are treated as a word window. Each word is associated w an embedding vector \n",
        "\\n  - Input vector $x$ just concatenates v(w) for each of the k words $x = [v(w_1);...;v(w_k)]$. Is fed into a NN w 1+ hidden layers\n",
        "\\n - Tend to have much higher predictive accuracy than n-gram LMs\n",
        "\\n - can generalize over contexts of similar words\n",
        "\\n - dont need smoothing \n",
        "\\n TRAINING (e.g. training examples are simply word k-grams from the corpus)\n",
        "\\n  - Identities of the first k-1 words are used as features, adn teh last word is used as the target label for the classifation\n",
        "\\n  - Conceptually model is trained using cross-entropy loss\n",
        "\\n PROBABILITY TABLES\n",
        "\\n  - Construct tables to look up the probability of seeing a word given a history \n",
        "\\n UNSEEN SEQUENCES\n",
        "\\n  - What happens when we have a new (unseen) combo of n words? \n",
        "\\n  - 1. Back-off 2. Smoothing/interpolation (we are basically stitching together short sequences of observed words) \n",
        "\\n  - Alternate idea: Intuition - take a sentence, and use it when we assign probabilities to similar sentences (the cat is walking in the bedroom -> the dog is running around the room) \n",
        "\\n NEURAL PROBABILISTIC LM \n",
        "\\n  - 1. Use a vector space model where the words are vectors w real values (gives a way to compute word similarity)\n",
        "\\n  - 2. Define a function that returns a joint probability of words in a sequence based on a sequence of these vectors\n",
        "\\n  - Simultaneously learn the word representations and the probability function from data\n",
        "\\n  - Seeing one of the cat/dog sentences allows them to increase the probabiltiy for that sentence AND its combinatorial # of \"neighbor\" sentences in vector space\n",
        "\\n WORD EMBEDDINGS\n",
        "\\n  - When the ~50 dim vectors that result from training a neural LM are projected down to 2-dim, we see a lot of words that are intuitively similar to each other are close together \n",
        "\\n WORD MEANING - How to represent meaning of a word?\n",
        "\\n  - Ideally, we want a meaning representation to encode (1) Synonyms (2) Antonyms (3) Connotations, words that are pos or neg (4) Semantic Roles, buy sell and pay are different parts of the same underlying purchasing event (5) Support for entailment\n",
        "\\n ENTAILMENT IN FORMAL SEMANTICS\n",
        "\\n - Mathematically well-understhood, powerful machinery for handling logical ops, but knowledge must come from somewhere else\n",
        "\n",
        "\\n Vector Space Models does not allow us to perform same kind of operations as if we had a taxonomic representation of word meaning \n",
        "\\n  - But instead will let us do it at a large scale and do other operations. Automatically extract konowledge about a language from a giant corpus\n",
        "\\n WORD SIMILARITY \n",
        "\\n  - most words dont have many synonyms, but do have a lot of similar words \n",
        "\\n  - Intuition of distributional word similarity: two words are similar if they have similar word contexts \n",
        "\\n  - Cosine does L2 normalization too. Cosine angle between vectors tell the similarity\n",
        "\n",
        "\\n TERM DOCUMENT MATRIX\n",
        "\\n  - Column Vector: Document (prob will be sparse (lots of zeros), =size of vocab)\n",
        "\\n  - Row: Term\n",
        "\\n  - Cell: How often word occured in that document\n",
        "\\n  - Length of document vectors is size of vocabulary\n",
        "\\n TERM-TERM Matrix\n",
        "\\n  - Length of vector is now |V| instead of number of documents\n",
        "\\n  - Cell value indicates how often a word appears in a context window surrounding a word\n",
        "\\n CONTEXT WINDOWS\n",
        "\\n  - w-2, w-1 target word w+1 w+2\n",
        "\\n ALTERNATES TO COUNTS\n",
        "\\n  - Raw word freq is not a great measure of association between words. We'd rather have a measure that asks whether a context word is particularly informative about the target word\n",
        "\\n  - Instead of raw counts, common to transform vectors using TF-IDR or PPMI \n",
        "\\n  - TF-IDF (Term freq inverse document frequency)\n",
        "\\n -  How often a word occurred in doc, 1 over the number of docs that it occured on\n",
        "\n",
        "\\n SPARSE VS DENSE VECTORS\n",
        "\\n  - Co-occurence matrix (weighted by TF-IDF or mutual info). long (len(V) = 50000+) and sparse (most elem=0)\n",
        "\\n -  Alternative: learn vectors that are short (200-1000) and dense (most elem nonzero)\n",
        "\\n HOW TO GET DENSE VECTORS\n",
        "\\n  - 1 way: train a classifier\n",
        "\\n  - 1. Treat target word and neighboring context word as positive examples 2. Randomly sample other words in lexicon to get negative samples 3. use logistic regression to train a classifier to distinguish those two cases 4. use the weights as the embeddings\n",
        "\n",
        "\\n WORD2VEC (learn embeddings as part of the process of word prediction)\n",
        "\\n   - Train a classifier to predict neighboring words, inspired by NN lang models. in doing so, learn dense embeddings for the words in the training corpus\n",
        "\\n -  Advantages: fast, easy to train (faster than SVD), avail online \n",
        "\n",
        "\\n EXTRA NOTES:\n",
        "\\n -  n-gram language models are typically evaluated by perplexity on a test set\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 180,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2306
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "64537b86-96eb-49a3-fcdf-0c2c8821c1f6"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 14: Natural Language Processing\n",
              "## SLP Chapter 9.1 Language Models Revisited\n",
              "   \n",
              "\n",
              "## SLP Chapter 9.2 Recurrent Neural Networks\n",
              "  \n",
              "\n",
              "## SLP Chapter 9.3 RNNs as Language Models\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.1 Lexical Semantics\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.2 Vector Semantics\n",
              " \n",
              "\n",
              "## SLP Chapter 6.3 Words and Vectors\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.4 Cosine for measuring similarity\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.8 Word2vec\n",
              "   \n",
              "\n",
              "## SLP Chapter 6.10 Semantic properties of embeddings\n",
              " \n",
              "\n",
              "## SLP Chapter 6.11 Bias and Embeddings\n",
              " \n",
              "\n",
              "## SLP Chapter 6.12 Evaluating Vector Models\n",
              "  \n",
              "\n",
              "## Module 14 Lecture Notes\n",
              " Neural Language Models advantages over n-gram LMs\n",
              "\n",
              "  - 1. No smoothing needed 2. Can handle much longer historiess 3. Can generalize over contexts of similar words 4. Neural LMs tend to have higher predictive accuracy than n-gram LMs \n",
              "\n",
              "  - Disadvantage: slower to train than traditional n-gram LMs \n",
              "\n",
              " NEURAL LMs\n",
              "\n",
              "  - 1. Associate each word in the vocab w a vector-representation, theyby creating notion of similarity btw words 2. Express joint probability function of a word seq in terms of word vectors for the words in that sequence 3. Simultaneously learn the word vectors and the parameters of teh function \n",
              "\n",
              "  - Word vectors are dim=30-100 dense, low dim. The probability func is expressed as the product of conditional probabilities of the next word given the previous word, using a multi-layer, feed forward neural network\n",
              "\n",
              "  - Input: k-gram of words $w_{1:k}$, Output: Probability idstribution over next word\n",
              "\n",
              "  - $k$ context words are treated as a word window. Each word is associated w an embedding vector \n",
              "\n",
              "  - Input vector $x$ just concatenates v(w) for each of the k words $x = [v(w_1);...;v(w_k)]$. Is fed into a NN w 1+ hidden layers\n",
              "\n",
              " - Tend to have much higher predictive accuracy than n-gram LMs\n",
              "\n",
              " - can generalize over contexts of similar words\n",
              "\n",
              " - dont need smoothing \n",
              "\n",
              " TRAINING (e.g. training examples are simply word k-grams from the corpus)\n",
              "\n",
              "  - Identities of the first k-1 words are used as features, adn teh last word is used as the target label for the classifation\n",
              "\n",
              "  - Conceptually model is trained using cross-entropy loss\n",
              "\n",
              " PROBABILITY TABLES\n",
              "\n",
              "  - Construct tables to look up the probability of seeing a word given a history \n",
              "\n",
              " UNSEEN SEQUENCES\n",
              "\n",
              "  - What happens when we have a new (unseen) combo of n words? \n",
              "\n",
              "  - 1. Back-off 2. Smoothing/interpolation (we are basically stitching together short sequences of observed words) \n",
              "\n",
              "  - Alternate idea: Intuition - take a sentence, and use it when we assign probabilities to similar sentences (the cat is walking in the bedroom -> the dog is running around the room) \n",
              "\n",
              " NEURAL PROBABILISTIC LM \n",
              "\n",
              "  - 1. Use a vector space model where the words are vectors w real values (gives a way to compute word similarity)\n",
              "\n",
              "  - 2. Define a function that returns a joint probability of words in a sequence based on a sequence of these vectors\n",
              "\n",
              "  - Simultaneously learn the word representations and the probability function from data\n",
              "\n",
              "  - Seeing one of the cat/dog sentences allows them to increase the probabiltiy for that sentence AND its combinatorial # of \"neighbor\" sentences in vector space\n",
              "\n",
              " WORD EMBEDDINGS\n",
              "\n",
              "  - When the ~50 dim vectors that result from training a neural LM are projected down to 2-dim, we see a lot of words that are intuitively similar to each other are close together \n",
              "\n",
              " WORD MEANING - How to represent meaning of a word?\n",
              "\n",
              "  - Ideally, we want a meaning representation to encode (1) Synonyms (2) Antonyms (3) Connotations, words that are pos or neg (4) Semantic Roles, buy sell and pay are different parts of the same underlying purchasing event (5) Support for entailment\n",
              "\n",
              " ENTAILMENT IN FORMAL SEMANTICS\n",
              "\n",
              " - Mathematically well-understhood, powerful machinery for handling logical ops, but knowledge must come from somewhere else\n",
              "\n",
              "\n",
              " Vector Space Models does not allow us to perform same kind of operations as if we had a taxonomic representation of word meaning \n",
              "\n",
              "  - But instead will let us do it at a large scale and do other operations. Automatically extract konowledge about a language from a giant corpus\n",
              "\n",
              " WORD SIMILARITY \n",
              "\n",
              "  - most words dont have many synonyms, but do have a lot of similar words \n",
              "\n",
              "  - Intuition of distributional word similarity: two words are similar if they have similar word contexts \n",
              "\n",
              "  - Cosine does L2 normalization too. Cosine angle between vectors tell the similarity\n",
              "\n",
              "\n",
              " TERM DOCUMENT MATRIX\n",
              "\n",
              "  - Column Vector: Document (prob will be sparse (lots of zeros), =size of vocab)\n",
              "\n",
              "  - Row: Term\n",
              "\n",
              "  - Cell: How often word occured in that document\n",
              "\n",
              "  - Length of document vectors is size of vocabulary\n",
              "\n",
              " TERM-TERM Matrix\n",
              "\n",
              "  - Length of vector is now |V| instead of number of documents\n",
              "\n",
              "  - Cell value indicates how often a word appears in a context window surrounding a word\n",
              "\n",
              " CONTEXT WINDOWS\n",
              "\n",
              "  - w-2, w-1 target word w+1 w+2\n",
              "\n",
              " ALTERNATES TO COUNTS\n",
              "\n",
              "  - Raw word freq is not a great measure of association between words. We'd rather have a measure that asks whether a context word is particularly informative about the target word\n",
              "\n",
              "  - Instead of raw counts, common to transform vectors using TF-IDR or PPMI \n",
              "\n",
              "  - TF-IDF (Term freq inverse document frequency)\n",
              "\n",
              " -  How often a word occurred in doc, 1 over the number of docs that it occured on\n",
              "\n",
              "\n",
              " SPARSE VS DENSE VECTORS\n",
              "\n",
              "  - Co-occurence matrix (weighted by TF-IDF or mutual info). long (len(V) = 50000+) and sparse (most elem=0)\n",
              "\n",
              " -  Alternative: learn vectors that are short (200-1000) and dense (most elem nonzero)\n",
              "\n",
              " HOW TO GET DENSE VECTORS\n",
              "\n",
              "  - 1 way: train a classifier\n",
              "\n",
              "  - 1. Treat target word and neighboring context word as positive examples 2. Randomly sample other words in lexicon to get negative samples 3. use logistic regression to train a classifier to distinguish those two cases 4. use the weights as the embeddings\n",
              "\n",
              "\n",
              " WORD2VEC (learn embeddings as part of the process of word prediction)\n",
              "\n",
              "   - Train a classifier to predict neighboring words, inspired by NN lang models. in doing so, learn dense embeddings for the words in the training corpus\n",
              "\n",
              " -  Advantages: fast, easy to train (faster than SVD), avail online \n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              " -  n-gram language models are typically evaluated by perplexity on a test set\n",
              "\n",
              "\n",
              "\n",
              "## Module 14 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 182,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 15291
        },
        "id": "T3cm1WV542_a",
        "outputId": "ce06a766-d90e-4c74-f4da-de4ffd9e66ba"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 8: Markov Decision Processes\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "  \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "  \n",
              "\n",
              "## AIMA Chapter 17.1 Sequential Decision Problems\n",
              " \n",
              "\n",
              "## AIMA Chapter 17.2 Algorithms for MDPs\n",
              " \n",
              "\n",
              "## Module 8 Lecture Notes\n",
              " Stochastic/probabilistic environment, where agent will have to figure the best action to take. \n",
              "\n",
              "MDP's are a kind og non-deterministic search problem. Applicable in a fully observable task env where we have to make a sequence of decisions\n",
              "and where the outcome of our actions is non-deterministic\n",
              "\n",
              "Ways to solve MDP's: (1) Expectimax search, (2) Value iteration, (3) Policy Iteration \n",
              "MDP: kind of nondeterministic search, projects an expectimax-like search tree\n",
              "\n",
              "  - 1) sequential decision problem (2) fully observable env (3) stochastic transition model (4) has additive rewards \n",
              "\n",
              "\n",
              "  - need set of states, actions, transition model, reward function, initial state, optionally one or more terminal states \n",
              "\n",
              "SOLUTION == POLICY (bc of non-determinism in MDP's, cannot simply give a sequence of actions)\n",
              "\n",
              "maps from a state onto the action to take if the agent is in that state\n",
              "\n",
              "π* = optimal policy, which depends on reward function \n",
              "\n",
              "\n",
              "  - Same policies may lead to different sequence of states and actions (env history) and thus a different score under the reward function\n",
              "\n",
              "- compute the expected utility of all possible paths generated by a policy \n",
              "\n",
              "Discounting term : determines how much to postpone immediate gratification for later reward \n",
              "\n",
              "- reasonable to maximize sum of rewards, also reasonable to prefer rewards now to rewards later. one soln: values of rewards decay exponentially\n",
              "\n",
              " - Why discount? sooner rewards probably have higher utility than later rewards, also helps algos converge \n",
              "\n",
              "Infinite utilities: problem - what if game lasts forever?\n",
              "\n",
              " - soln: finite horizon (depth-limited search) or discounting or absorbing state: guarentee that for every policy, a terminal state will eventually be reached (e.g. overheated in racing) \n",
              "\n",
              "Value iteration\n",
              "\n",
              " - (1) start w Vo(s) = 0. (2) Given vector of Vk(s) values, do one play of expectimax from each state (3) repeat until convergence (4) TIME COMPLX: O(AS^2) \n",
              "\n",
              "\n",
              " - (k = num iterations/Bellman updates)\n",
              "\n",
              " CONVERGENCE: How do we know the V_{k} vectors will converge? \n",
              "\n",
              "  - (1) If tree has max depth M, then V_{m} holds the actual untruncated values (2) If discount < 1 \n",
              "\n",
              "\n",
              "  - Bellman equation is the basis for V.I. algo solving MDPs\n",
              "\n",
              "POLICY EVALUATION: Instead of figuring out optimal val of each state, try to figure out what best policies are \n",
              "\n",
              "- iterate over policies rather than states. How do we calc the V's for a fixed policy pi?\n",
              "(Idea 1) Turn recursive Bellman eq into updates (like value iteration). TIME COMPLX O(S^2) per iter (idea 2) without the maxes, the Bellman eq are just a linear system \n",
              "\n",
              "\n",
              " - given a policy, calculate the utility of each state if that policy were to be executed\n",
              "\n",
              " - $O(S^2)$ per iter\n",
              "\n",
              "\n",
              " POLICY IMPROVEMENT: calculate a new MEU policy $pi_{i+1}$ using one-step look ahead based on $U_i$\n",
              "\n",
              "\n",
              " - Imagine we have the optimal values V*(s). How should we act => do a mini expectimax (one-step). this is policy extraction, since it gets the policy implied by the values \n",
              "\n",
              "\n",
              " - Imagine we have the optimal q-values. How to act => just pick the best action implied by those two values. actions are easier select from q-values than values \n",
              "\n",
              "\n",
              "PROBLEMS W VALUE ITERATION: \n",
              "\n",
              "  - (1) Slow, O(S^2A) per iter (but also converges exponentially fast ^k) (2) The \"max\" at each state rarely changes (3) Policy often converges long before the values\n",
              "\n",
              " - alt approach for optimal values: (1) Policy iteration, calc utils for some fixed policy until convergence (2) policy improvement, update policy using one step look ahead with resulting converged (but not optimal) utils as future vals (3) repeat until convergence (this is POLICY ITERATION. still optimal and can converge much faster) \n",
              "\n",
              "\n",
              "VALUE ITERATION VS POLICY ITERATION: both compute the same, all optimal vals \n",
              "\n",
              " - value: each iter updates both values and policy. we dont track policy, but take max over actions implicitly recomputes it \n",
              "\n",
              " - policy: we do several passes that update utils with fixed policy (each pass is fast bc consider only one action at a time) (2) after policy evaluated, new policy chosen (slow like value iter pass) (3) new policy is better or we're done \n",
              "\n",
              "\n",
              "SUMMARY: MDP ALG \n",
              "\n",
              "- want to either (1) compute optimal vals, use value or policy iter (2) compute vals for particular policy: use policy evaluation (3) turn vals into a policy: use policy extraction (one step lookahead). \n",
              " \n",
              "these all look the same!! only differ only in whether we plug a fixed policy or max over actions \n",
              "\n",
              "\n",
              "MAXIMUM EXPECTED UTILITY: worst case is not going to always happen! \n",
              "\n",
              "- for worst-case minimax reasoning, terminal function scale doesnt matter (1) we just want better states to have higher evaluations to get correct order (2) called insensitivity to monotonic transformations \n",
              "\n",
              "\n",
              "RATIONAL PREFERENCES: we want some constraints on preferences before we call them rational \n",
              "\n",
              "  - Axiom of Transitivity: Prefer A over B and prefer B over lottery C, implies A preferred over C \n",
              "\n",
              "  - Continuity: $A \\succ B \\succ C \\Rightarrow \\exists p [p, A; 1-p, C] \\sim B$ (some lotery B between A, C, there exists probability p that makes you indifferent to B)\n",
              "\n",
              "  - Orderability: Exactly one of $(A \\succ B), (B \\succ A), (A \\sim B)$ holds. Given 2 lotteries, a rational agent must prefer one or rathem equal (cannot avoid deciding)\n",
              "\n",
              "  - Substitutability: $A \\succ B \\Rightarrow [p,A; 1-p, C] \\sim [p, B; 1-p, C]$ (if neither prefer A, B, then some lottery in between that u have equal preference over that lottery)\n",
              "\n",
              "  - Monotonicity: $A \\succ B \\Rightarrow (p \\geq q \\Leftrightarrow [p, A; 1-p, B] \\succeq [q, A; 1-q, B])$ (if A better than B, i prefer greater p than q)\n",
              "\n",
              "  - Decomposability: Compound lotteries can be reduced to simpler ones using laws of probability (long one)\n",
              "\n",
              "\n",
              " EXISTENCE OF A UTILITY FUNCTION: \n",
              "\n",
              "  - if agent's preference obey the axioms of utility, then exists a function U s.t. U(A) > U(B) iff A is preferred to B, and U(A)=U(B) if indifferent\n",
              "\n",
              "\n",
              " EXPECTED UTIL OF A LOTTERY:\n",
              "\n",
              "  -  sum of probabilities of each outcome times the utility of that outcome\n",
              "\n",
              "\n",
              " MEU Principle: \n",
              "\n",
              "  - Given any preferences satisfying these contraints, exists a real values function U s.t.: \n",
              "\n",
              "  - $U(A) \\geq U(B) \\Leftrightarrow A\\simeq B , U([p_1, S_1; ... ; p_n, S_n]) = \\sum_{i}^{}p_iU(S_i)$ (values assigned by U preserve preferences of both prizes and lotteries)\n",
              "\n",
              "  - (1) Choose the action that maxes expected util (2) Note: agent can be rational (consistent w MEU) w/o representing or manipulating utils and probabilities (3) e.g. lookup table for perfect tic-tac-toe, reflex vacuum cleaner. Money does NOT behave as util funciton, but can talk about utility of having money or being in debt \n",
              "\n",
              "  - Fundamental idea of decision theory is that an agent is rational iff it choices the action that yields highest expected utility, avged over all possible outcomes of the action \n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              "  - Markov property: given the past state, the present and future are dependent\n",
              "\n",
              "  - In n-gram language models, Markov assumption makes it possible to estimate the probabilities from data\n",
              "\n",
              "\n",
              "\n",
              "## Module 8 Definitions\n",
              "* **Policy** - takes in a state and returns best action agent could take when it finds itself in that state/ SOLUTION TO A MDP\n",
              "* **Reward function** - rewards can be positive or sequestion but have a max bound. agent can also receive reward at each time step\n",
              "* **Principle of maximum expected utility** - a rational agent should choose the action that maximizes its expected util, given its knowledge\n",
              "* **Lottery** - situations with uncertain prizes (mixture of outcomes where their probability gets attached)\n",
              "* **Contraction** - part of the proof of convergence for value iteration\n",
              "* **Preference elicitation** - involves presenting choices to the human and using observed preferences to pin down the underlying utility function\n",
              "\n",
              "\n",
              "# Module 9: Reinforcement Learning\n",
              "## AIMA Chapter 17.3 Bandit Problems\n",
              " n-armed bandit has $n$ levers - behind each is a fixed but unknown probability distribution of winnings; each pull samples from that distribution \n",
              "\n",
              "  \n",
              "\n",
              "## AIMA Chapter 22.1 Learning from Rewards\n",
              "  \n",
              "\n",
              "## AIMA Chapter 22.2 Passive Reinforcement Learning\n",
              " \n",
              "\n",
              "## AIMA Chapter 22.3 Active Reinforcement Learning\n",
              " \n",
              "\n",
              "## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n",
              " \n",
              "\n",
              "## Module 9 Lecture Notes\n",
              " \n",
              "In MDP,\n",
              "\n",
              " -  agent is given reward and transition function. In reinforcement learning, agent must learn both of these functions by interacting with the world \n",
              "\n",
              " -  Everytime agent takes an action in the world, will receive instantaneous reward (feedback). GOAL: maximize its expected rewards over time using observations \n",
              "\n",
              "  - Tradeoff between Exploration + Exploitation. (Exploration) Agent must try new actions including where reward may be worse than another action (Exploitation) Use knowledge learned so far to choose best action for expected rewards\n",
              "\n",
              " -  though stochastic, we knew what the probability distribution over the states was\n",
              "\n",
              " Model-based learning: \n",
              "\n",
              "  - where transition function is represented using explicit probabilistic model \n",
              "\n",
              " Temporal Difference Learning: \n",
              "\n",
              "  - agent is able to update beliefs about world after every single action it takes using some kind of exponential moving average\n",
              "\n",
              " Regret: \n",
              "\n",
              "  - lets us measure total rewards got from a particular exploration strategy and compare that against the total expected rewards we would get if agent had been able to follow optimal policy the whole time\n",
              "\n",
              "\n",
              " REINFORCEMENT LEARNING: still assume a MDP \n",
              "\n",
              "  - (1) set of states s \\in S (2) set of actions per state A (3) model T(s, a, s') (4) reward function R(s, a, s')\n",
              "\n",
              "  - Still looking for a policy π(s)\n",
              "\n",
              "  - New twist: don't know T or R (i.e. we dont know which states are good or what the actions do, must actually try actions and states to learn)\n",
              "\n",
              "  - Offline (MDPs (think about it)) vs Online (Reinforcement Learning (try things out))\n",
              "\n",
              "  - Value iteration + Policy Iteration are OFFLINE Algs (like A*) \n",
              "\n",
              "\n",
              " MODEL-BASED LEARNING\n",
              "\n",
              "  - Model-based idea: (1) learn approximate model based on exp (2) solve for values as if learned model is correct\n",
              "\n",
              "  - Step 1: Learnign Empirical MDP model (1) count outcomes s' for each s, a (2) normalize to give an estimate of T(s, a, s') (3) discover each R(s, a, s') when we experience (s,a,s')\n",
              "\n",
              "  - Step 2: Solve the learned MDP (e.g. use value iteration as before) \n",
              "\n",
              "\n",
              " MODEL-FREE LEARNING\n",
              "\n",
              "  - instead, take an action. every time we do so, we compare the results to what we thought was going to happen to actuality. when something better or worse happens, take values and adjust it \n",
              "\n",
              " PASSIVE REIN. LEARN.: let someone else choose the policy and we try and see outcome (we're gonna figure out exactly the same kind of thing that policy evaluation did) \n",
              "\n",
              "  - Simplified task: policy Evaluation (input) fixed policy π(s), dont know transitions and rewards (goal) learn state values\n",
              "\n",
              "  - in this case (1) learner is \"along for the ride (2) no choice about what actions to take (3) just execute policy and learn that exp (4) NOT offline planning - actually take actions in the world \n",
              "\n",
              " DIRECT EVALUATION\n",
              "\n",
              "  - Goal: Compute values for each state under π\n",
              "\n",
              "  - Idea: average together observed sample values (1. act according to π 2. everytime u visit a state, write down what the sum of discounted rewards turned out to be 3. avg those samples)\n",
              "\n",
              " ACTION-UTILITY LEARNING (Q-learning)\n",
              "\n",
              "  - Given Q-function, agent can choose what to do in $s$ by finding the action w highest $Q-value$\n",
              "\n",
              "\n",
              " PROS and CONS of DIRECT EVALUATION\n",
              "\n",
              "  - Pros (1) easy to understand (2) doesnt requirement any knowledge of T, R (3) eventually computes the correct avg values, using just sample transitions\n",
              "\n",
              "  - Cons (1) wastes info about state connections (2) each state must be learned separately (3) so, takes a long time to learn\n",
              "\n",
              "  - Why not use policy evaluation? Fully exploits connections btw states, but unfortunately need T and R to do it\n",
              "\n",
              "\n",
              " TEMPORAL DIFFERENCE LEARNING\n",
              "\n",
              "  - Big idea: learn from every experience (1) update V(s) each time we exp a transition (2) likely outcomes s' will contribute updates more often\n",
              "\n",
              "  - Temporal difference learning of values (1) policy still fixed, still doing evaluation (2) move values toward value of whatever successor occurs: running average\n",
              "\n",
              "\n",
              " EXPONENTIAL MOVING AVERAGE\n",
              "\n",
              " - More recent samples are more important (discount is exponentiated).\n",
              "\n",
              " - Forgets about the past. Decreasing learning rate (alpha) can give converging averages \n",
              "\n",
              "\n",
              " PROBLEMS WITH TD VALUE LEARNING\n",
              "\n",
              "  - It is a model free way to do policy eval, mimicking Bellman updates w running sample averages\n",
              "\n",
              "  - However, if want to turn values into a new policy, we're sunk\n",
              "\n",
              "  - Idea: learn Q-values, not values. Makes action selection model-free too!\n",
              "\n",
              "\n",
              " ACTIVE REINFORCEMENT LEARNING\n",
              "\n",
              "  - Full Reinforcement Learning: optimal policies (like value iteration)\n",
              "\n",
              "  - (1) dont know transitions + rewards (2) you choose the actions now \n",
              "\n",
              "  - GOAL: learn optimal policy/values\n",
              "\n",
              "  - (1) learner makes choices (2) exploration vs exploitation (3) NOT offline planning \n",
              "\n",
              "\n",
              " Q-VALUE ITERATION \n",
              "\n",
              "  - (1) Value iteration: find successive (depth-limited values) \n",
              "\n",
              "  - (2) Q-values are more useful, so compute them instead \n",
              "\n",
              "\n",
              " Q-LEARNING: sample-based Q-value iteration\n",
              "\n",
              " -  Learn Q(s, a) values as you go (1) receive a sample (s, a, s', r) (2) consider old esimate Q(s, a) (3) consider new sample estimate $sample = R(s, a, s') + \\gamma max_{a'}Q(s', a')$(4) incorporate new estimate into a running average $Q(s, a) \\leftarrow (1- alpha)Q(s, a) + (alpha)[sample]$\n",
              "\n",
              " -  PROPERTIES: converges to optimal policy, even if youre acting suboptimally!\n",
              "\n",
              " -  Called OFF-POLICY LEARNING\n",
              "\n",
              "  - Caveats: (1) have to explore enough (2) have to eventually make learning rate small enough.. but not decrease it too quickly (closer to zero learning rate = keep knowledge of past) (3) in the limit, doesnt matter how u select actions!\n",
              "\n",
              "\n",
              " Q-learning requires exploring in order to learn optimal policy\n",
              "\n",
              " -  To force exploration: random ($\\epsilon$ greedy) or exploration functions \n",
              "\n",
              "  - When to explore? Better idea: explore areas whose badness is not yet established, eventually stop exploring \n",
              "\n",
              "  Exploration function: takes a value estimate u and visit count n, returns optimistic utility $f(u, n) = u + k/n)$ \n",
              "\n",
              "  - (REGULAR Q-UPDATE) $Q(s, a) \\leftarrow_{a} R(s, a, s') + \\gamma max_{a'}Q(s', a')$\n",
              "\n",
              "  - (MODIFIED Q-UPDATE) $Q(s, a) \\leftarrow_{a} R(s, a, s') + \\gamma max_{a'}f(Q(s', a'), N(s',a'))$\n",
              "\n",
              "  - Note: this propagates the \"bonus\" back to states that lead to unknown states as well \n",
              "\n",
              "\n",
              " REGRET: even if u learn optimal policy, still make mistakes along the way\n",
              "\n",
              "  - minimizing regret requires optimally learning to be optimal\n",
              "\n",
              "\n",
              " APPROXIMATE Q-LEARNING\n",
              "\n",
              "  - GENERALIZING ACROSS STATES: basic q-learning keeps a table of all q-values\n",
              "\n",
              "  - In realistic situations, we cannot possibly learn about every single state (1) too many states to vist them all in training (2) too many states to hold the q-tables in memory\n",
              "\n",
              "  - Instead, want to generalize (1) learn about some small num of training states from exp (2) gneeralize that exp to new, similar sitations \n",
              "\n",
              "  - Intuitive interpretation: adjust weights of active features (e.g. if something unexpectedly bad happens, blame all features that were on)\n",
              "\n",
              "  - Formal Justification: online least squares\n",
              "\n",
              "\n",
              " LINEAR VALUE FUNCTION: using a feature representation, we can write a q function (or value function) for any state using few weights\n",
              "\n",
              "  - $V(s) = w_1f_1(s) +... + w_nf_n(s)$\n",
              "\n",
              "  - $Q(s, a) =  w_1f_1(s, a) +... + w_nf_n(s, a)$\n",
              "\n",
              "  - Advantage: our experience is summed up in a few powerful numbers | Disadvantage: states may share features but actually be very different in value\n",
              "\n",
              "\n",
              " EXTRA NOTES \n",
              "\n",
              "  - Q-function in reinforcement learning is action-utility function\n",
              "\n",
              "  - For a partially observable environment, learning problem is more difficult bc next percept is no longer a label for the state prediction problem  \n",
              "\n",
              "  Linear functions: when using perceptron learning rule, weights are updated when the actual output does not match the hypothesis output \n",
              "\n",
              "\n",
              "## Module 9 Definitions\n",
              "* **Exploration** - try unknown actions to get info\n",
              "* **Exploitation** - eventually, have to use what you know\n",
              "* **Regret** - measure of total mistake cost: diff btwn your expected rewards, including youthful suboptimality, and optimal (expected) rewards)\n",
              "* **Difficulty** - learning can be much harder than solving a known MDP\n",
              "* **N-armed bandit** - \n",
              "* **Policy search** - agent learns policy pi(s) that maps directly states to actions (reflex agent)\n",
              "* **Absorbing state** - where no actions have any effect and no rewards are received (IRL, many actions are irreversable)\n",
              "* **Pseudorewards** - additional rewards supplied to speed up learning\n",
              "\n",
              "\n",
              "# Module 10: Probabilies and Language Models\n",
              "## AIMA Chapter 12.1 Acting under Uncertainty\n",
              " \n",
              "\n",
              "## AIMA Chapter 12.2 Basic Probability Notation\n",
              "  \n",
              "\n",
              "## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n",
              " \n",
              "\n",
              "## AIMA Chapter 12.4 Independence\n",
              "  \n",
              "\n",
              "## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n",
              " \n",
              "\n",
              "## AIMA Chapter 12.6 Naive Bayes Models\n",
              "  \n",
              "\n",
              "## AIMA Chapter 12.7 The Wumpus World Revisited\n",
              " \n",
              "\n",
              "## SLP Chapter 3.1 N-Grams\n",
              " \n",
              "\n",
              " The assumption that the probability of a word depends only on the previous word is called a Markov assumption.  \n",
              "\n",
              " n-grams are Markov models that estimate words from a fixed window of previous words. n-gram probabilities can be estimated by counting in a corpus and normalizing (the maximum likelihood estimate) \n",
              "\n",
              " n-gram language models are evaluated extrinsically in some task or intrinsically using perplexity\n",
              "\n",
              " \n",
              "\n",
              "## SLP Chapter 3.2 Evaluating Language Models\n",
              "  \n",
              "\n",
              "## SLP Chapter 3.3 Sampling sentences from a language model\n",
              " \n",
              "\n",
              "## SLP Chapter 3.4 Generalization and Zeros\n",
              "  \n",
              "\n",
              "## SLP Chapter 3.5 Smoothing\n",
              "  \n",
              "\n",
              "## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n",
              "   \n",
              "\n",
              "## Module 10 Lecture Notes\n",
              " \n",
              "UNCERTAINTY\n",
              "\n",
              "  - Observed Variables (evidence): agent knows certain things about state of world (e.g. sensor readings) \n",
              "\n",
              "  - Unobserved Variables (states): agent needs to reason about other aspects (e.g. where object is) \n",
              "\n",
              "  - Model:agnet knows somethign about how the known variables relate to the unknown variables \n",
              "\n",
              "  - Joint distribution (e.g. $P(X_1=x_1, X_2=x_2)$) - can calculate the probability of an event\n",
              "\n",
              "  - Marginal Distributions are sumtables which elimiate variables (Marginalization=summing out: combine collapsed rows by adding)\n",
              "\n",
              "  - Conditional Probabilities; simple relation between joint and conditional probabilities\n",
              "\n",
              "\n",
              "  PROBABILISTIC INFERENCE: compute a desired probability from other known probabilities (e.g conditional from joint)\n",
              "\n",
              "  - We general compute conditional probabilities (represent the agent's belieefs given the evidence) \n",
              "\n",
              "  - Probabilities change with new evidence (observing new evidence causes beliefs to be updated)\n",
              "\n",
              "\n",
              " INFERENCE BY ENUMERATION: we want $P(Q|e_1...e_k)$\n",
              "\n",
              "  - (1) Select entries consistent w/evidence (2) Sum out hidden variables to get joint of query and evidence (3) normalize \n",
              "\n",
              "\n",
              " CHAIN RULE: write any joint distribution as an incremental product of conditional distributions \n",
              "\n",
              "  - $P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1, x_2) $\n",
              "\n",
              "  - = $P(x_1,..., x_n)\\prod_{i}^{} P(x_i|x_i....x_{i-1})$\n",
              "\n",
              " Bayes' Rule\n",
              "\n",
              "  - $P(x, y) = P(x|y)P(y) = P(y|x)P(x)$\n",
              "\n",
              "\n",
              " PROBABILISTIC LANGUAGE MODELS: goal-assign a probability to a sentence\n",
              "\n",
              "  - (1) autocomplete for texting (2) machine translation (3) spelling correction (4) speech recognition\n",
              "\n",
              " PROBABILISTIC LANGUAGE MODELING: \n",
              "\n",
              "  - Goal: compute probability of a sentence or seq of words $P(W) = P(w_1...w_n)$\n",
              "\n",
              "  - Related Task: probability of an upcoming word $P(w_5|w_1...w_4)$\n",
              "\n",
              "  - Model that computes either of these, $P(W) or P(w_n | w_1...w_{n-1}) is a LANGUAGE MODEL$\n",
              "\n",
              "  - Compute this joint probability using chain rule \n",
              "\n",
              "\n",
              " CHAIN RULE\n",
              "\n",
              "  - Recall: P(B|A) = P(A, B) / P(A) ---> P(A, B) = P(A)P(B|A) \n",
              "\n",
              " -  Chain rule in general: $P(x_1, x_2,...x_n) = P(x_1)P(x_2|x_1)P(x_3|x1, x2)..P(x_n|x1...xn-1)$\n",
              "\n",
              "  - Joint prob of words in a sentence: $P(w1w2w3..wn) = prod_{i}^{} P(w_i|w_1w_2...w_{i-1})$\n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              " -  If process is stationary, the conditional probability table does not change over time \n",
              "\n",
              " -  Dynamic Bayesian Model (DBN), uncessary for construction: multiple state and evidence variables\n",
              "\n",
              "\n",
              "\n",
              "## Module 10 Definitions\n",
              "* **Random variable** - some aspect of the world about which we (may) have uncertainty\n",
              "* **Joint distribution** - over a set of random variables specifies a real number for each assignment (or outcome)\n",
              "* **Event** - set E of outcomes\n",
              "* **Conditional distribution** - probabilities distributions over some variabels given fixed values of others\n",
              "* **Perplexity** - of a test set according to a lang model is the geometric mean of the inverse test set probability computed by the model \n",
              "\n",
              "\n",
              "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n",
              "## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n",
              "  \n",
              "\n",
              "## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n",
              "   \n",
              "\n",
              "## AIMA 13.3 Exact Inference in Bayesian Networks\n",
              " the time and space complexity of exact inference in polytrees is linear in the size of the network \n",
              "\n",
              "## Module 11 Lecture Notes\n",
              " AI agent that uses probabilistic model can make inferences about the world\n",
              "\n",
              " Bayes Nets: graphical models where nodes in graph represent variables and probabalistic model and the arcs represent the relationship between the diff variables in our model\n",
              "\n",
              " - much more compact representation where we've got a smaller num of probability tables that will have to estimate and populate \n",
              "\n",
              "  - x and y are independent if the joint probability is equal to the two marginal probabilities of X and Y (P(x) * P(y))\n",
              "\n",
              " CONDITIONAL INDEPENDENCE: X and Y are C.I. given Z: $P(x, y|z) = P(x|z)P(y|z)\n",
              "\n",
              "  - Unconditional (absolute) independence is very rare and doesnt help us make inferences about other variables$\n",
              "\n",
              "\n",
              " BAYES NETS ASSUMPTIONS: $P(x_i|x_1...x_{i-1}) = P(x_i|parents(X_i))$\n",
              "\n",
              "  - Beyond the chain rule->bayes net conditional independence assumptions, there are often additional conditional independences and can be read off the graph\n",
              "\n",
              "  - Important tool for us to model how we think the world works\n",
              "\n",
              " D-SEPARATION: D=descendents, allows us to study the independent properties of triples in our graph\n",
              "\n",
              " - Any complex BN e.g. can be broken down into repetiations of the 3 cases to check if 2 vars are independent\n",
              "\n",
              " - 1. Causal Chain (Z->Y->Z)\n",
              "\n",
              " - X not guaranteed independent of Z, but is if Z given Y\n",
              "\n",
              " - 2. Common Cause (X<-Y->Z)\n",
              "\n",
              " - X not guaranteed independent of Z since both due to Y\n",
              "\n",
              " - X is guar. ind. of Z given Y\n",
              "\n",
              " - 3. Common Effect (X->Z<-Y)\n",
              "\n",
              " - X and Y independent\n",
              "\n",
              " - X and Y not guaranteed independent of Z\n",
              "\n",
              "\n",
              " ARE TWO VARIABLES IN A BN INDEPENDENT?\n",
              "\n",
              "  - Soln: analze the graph. Any complex example can be broken into repetitions of the three canonical cases \n",
              "\n",
              "  - A path is active if each triple is active\n",
              "\n",
              "  - If all paths are inactive, then independence is guarenteed\n",
              "\n",
              "\n",
              " INFERENCE (we want to make some inferences about the world, given some partial observations)\n",
              "\n",
              " INFERENCE BY ENUMERATION \n",
              "\n",
              " -  General Case: evidence variables, query* variables, hidden variables \n",
              "\n",
              " -  We want $P(Q|e_1...e_k)$\n",
              "\n",
              " -  (1) Select the entries consistent with the evidence (2) Sum out H to get joint of Query and evidence (3) Normalize \n",
              "\n",
              " -  Given unlimited time, inference in BNs is easy \n",
              "\n",
              " -  A query can be answered using a Bayes net by computing sums of products of conditional probabilities from the network\n",
              "\n",
              "\n",
              "\n",
              " INFERENCE BY ENUMERATION vs VARIABLE ELIMIR\n",
              "\n",
              " -  Why is inf by enum slow? You join up the whole joint distribution before you sum out the hidden variables\n",
              "\n",
              " -  Advanced technique: variable elimination - interleave joining and marignalizing - still NP-hard but much faster \n",
              "\n",
              "\n",
              " Nice thing, bayesian networks allows us to make some indenpendent assumptions to simplify the process of making those inferences and to simplify our modeling in such a way that we could understnad the relationship between different parts of our model\n",
              "\n",
              "\n",
              "\n",
              "## Module 11 Definitions\n",
              "* **Inference** - calculating some useful quantity from a joint probability distribution\n",
              "\n",
              "\n",
              "# Module 12: Naive Bayes and Perceptrons\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "   \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "  \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "  \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "   \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.1 Naive Bayes Classifiers\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.2 Training the Naive Bayes Classifier\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.3 Worked Example\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.6 Naive Bayes as a Language Model\n",
              "   \n",
              "\n",
              "## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n",
              " \n",
              "\n",
              "## SLP Chapter 4.8 Test sets and Cross-validation\n",
              " \n",
              "\n",
              "## SLP Chapter 4.9 Statistical Significance Testing\n",
              "  \n",
              "\n",
              "## SLP Chapter 4.10 Avoiding Harms in Classification\n",
              "  \n",
              "\n",
              "## Module 12 Lecture Notes\n",
              " Perceptrons learn differently than a naive Bayes classifier\n",
              "\n",
              " -  Rather than learning a set of probabilities, perceptron have a weight associated with each feature that they use for their classification decision every time they make a misclassification decision on an item in teh training set, perceptron update their weights in order to better classify that example\n",
              "\n",
              "  - Up until now: how to use a model to make optimal decisions\n",
              "\n",
              " Machine Learning: How to aquire a model from data/exp (1) learning params (e.g probabilties)(2) learning structure (e.g. BN graphs) (3) learning hidden concepts (e.g. clustering) \n",
              "\n",
              " MODEL BASED CLASSIFICATION \n",
              "\n",
              "  - Approach (1) build a model (e.g. bayes net) where both the label and features are random variables (2) instantiate any observed features (3) query for the distribution of the label conditioned on the features\n",
              "\n",
              " GENERAL NAIVE BAYES\n",
              "\n",
              "  - $P(Y, F_1, ... F_n) = P(Y)\\prod_{i}{}P(F_i|Y)$\n",
              "\n",
              " INFERENCE FOR NAIVE BAYES\n",
              "\n",
              " -  Goal: compute posterior distribution over label variable Y \n",
              "\n",
              "  - (1) get joint probability of label and evidence for each label (2) sum to get probability of evidence (3) normalize by dividing step 1 by step 2\n",
              "\n",
              " -  What do we need in order to use naive bayes? (1) inference method (2) estimates of local conditional probability tables\n",
              "\n",
              " CONCEPTS FOR ML \n",
              "\n",
              "  - Data: labeled instances (e.g.) emails marked spam \n",
              "\n",
              "  - training, held out, test set\n",
              "\n",
              "  - Features: attribute-value pairs which characterize each x\n",
              "\n",
              "  - Experimentation cycle\n",
              "\n",
              " -  Learn parameters (e.g. model probabilities on training set), tune hyperparameters on held-out set, compute accuracy of test set, never peek at test set!\n",
              "\n",
              " -  Evaluation - accuracy: fraction of instances predicted correctly\n",
              "\n",
              " -  Overfitting and generalization \n",
              "\n",
              " -  want a classifier which does well on test data\n",
              "\n",
              " -  Overfitting: fitting training data closely, but not generalizing well\n",
              "\n",
              " GENERALIZATION AND OVERFITTING \n",
              "\n",
              " -  Relative freq parameters will overfit the training data\n",
              "\n",
              "  - As an extreme case, imagine using entire email as only feature\n",
              "\n",
              "  - To generalize better, we need to smooth or regularize the estimates\n",
              "\n",
              " PARAMETER ESTIMATION: estimating the distribution of a random variable\n",
              "\n",
              " -  Elicitation: ask a human / expert\n",
              "\n",
              " -  Expirically: use training data (learning) -> e.g. for each outcome x, look at empirical rate of that value (count(x) / total samples). multiply probabilities to get estimate of maximizing the likelihood of the data\n",
              "\n",
              " MAXIMUM LIKELIHOOD\n",
              "\n",
              " -  Relative freqs are the maximum likelihood estimates \n",
              "\n",
              " LAPLACE SMOOTHING (one way to avoid zero probabilities)\n",
              "\n",
              " -  Laplace's estimate: pretend you saw every outcome once more than actuality (E.G. if you see 2 red, 3 blue, maximum likelihood estimate is 2/3 for red, 1/3 blue. laplacian estimate is 3/5 red, 2/5 blue)\n",
              "\n",
              " ESTIMATION: LINEAR INTERPOLATION (another way to avoid zero probabilities) \n",
              "\n",
              " -  Also get the empirical P(X) from the data. make sure the estimate of P(X|Y) isnt too different from empirical P(X)\n",
              "\n",
              " -  in practice, laplace often performs poorly for P(X|Y) if |X| or |Y| is very large\n",
              "\n",
              "\n",
              " How do we pick the best parameterization of our models and then how do we pick the best estimates of our model parameters, values of hyperparams\n",
              "\n",
              " TUNING ON HELD-OUT DATA\n",
              "\n",
              "  - 2 unknowns: Parameters: the probabilities P(X|Y), P(Y). Hyperparameters: e.g. the amount/type of smoothing to do, k, alpha\n",
              "\n",
              " What should we learn where?\n",
              "\n",
              " -  (1) Learn parameters from training data (2) tune hyperparams on different data (3) for each val of hyperparameters, train and test on held-out data (4) choose the best value and do a final test on test data \n",
              "\n",
              " WHAT TO DO ABOUT ERRORS\n",
              "\n",
              "  - More features! \n",
              "\n",
              " BASELINES (if our classifier is getting good accuracy, we actually need to put that into perspective)\n",
              "\n",
              "  - (1) get a baseline. very simple straw  man procedures. help determine how hard a task is, help know what \"good\" accuracy is\n",
              "\n",
              "  - Weak baseline: most frequent label classifier. for real research, use previous work as a strong baseline\n",
              "\n",
              "\n",
              " SUMMARY\n",
              "\n",
              "  - (1) Bayes rule lets us do diagnostic queries with causal probabilities (2) naive bayes assumption takes all feature to be independent given the class label (3) we can build classifiers out of a naive Bayes model using training data (4) smoothing esimates is important in real systems (4) classifier confidences are useful when you can get them \n",
              "\n",
              "\n",
              " PERCEPTRON\n",
              "\n",
              "  - idea of accepting a bunch of inputs and combining them somehow into an activation function and transmitting a signal onwards (mathematical representation) \n",
              "\n",
              "  - Learning: binary perceptron \n",
              "\n",
              "  - (1) start with weights = 0. for each training instance, classify w current weights. if correct (i.e. y=y*), no change. if wrong, adjust weight vector\n",
              "\n",
              "\n",
              " MULTICLASS DECISION RULE\n",
              "\n",
              "  - if multiple classes, weight vector for each class( $w_y$). score of a class y ($w_y f(x)$). prediction highest score wins ($y = arg_y max w_y f(x)$)\n",
              "\n",
              " PROPERTIES OF PERCEPTRONS\n",
              "\n",
              "  - Separability: true if some params get the training set perfectly correct\n",
              "\n",
              "  - Convergence: if training is separable, perceptron will eventually converge (binary case) \n",
              "\n",
              "  - Mistake bound: max num of mistakes (binary case) related to the margin or degree of separability ($mistakes \\lt k/\\delta^2$)\n",
              "\n",
              "\n",
              " PROBLEMS W PERCEPTRON\n",
              "\n",
              "  - Noise: if data isnt separable, weights might thrash. (avging weight vectors over time can help (avged perceptron)) \n",
              "\n",
              "  - Mediocre generalization: finds a \"barely\" separating soln\n",
              "\n",
              "  - Overtraining: test/held-out accuracy usually rises, then falls. overtraining is a kind of overfitting \n",
              "\n",
              "\n",
              " FIXING THE PERCEPTRON\n",
              "\n",
              " -  Idea: adjust weight update to mitigate these effects\n",
              "\n",
              " MAXIMUM STEP SIZE\n",
              "\n",
              "  - In practice, also bad to make updates too large (e.g. may be labeled incorrectly, mght not have enough features )\n",
              "\n",
              " SOLN: cap max possible value of $tau$ w some constant C\n",
              "\n",
              " -  tau corresponds to an optimization that assumes non seperable data. usually converges faster than perceptron. usually better, especially on noisy data\n",
              "\n",
              " SUPPORT VECTOR MACHINES\n",
              "\n",
              "  - Maximizing the margin: good according to intuition, theory, practice\n",
              "\n",
              "  - Only support vectors matter; other training examples are ignorable\n",
              "\n",
              "  - Support vector machines (SVMs) find the separator with max margin \n",
              "\n",
              "\n",
              " CLASSIFICATION COMPARISON\n",
              "\n",
              "  - Naive Bayes (1) builds a model training data (2) gives prediction probabilities (3) strong assumptions about feature independence (4) one pass through data (counting)\n",
              "\n",
              "  - Perceptrons / MIRA: (1) makes less assumptions about data (2) mistake-driven learning (3) multiple passes through data (prediction) (4) often more accurate \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 12 Definitions\n",
              "* **Naive bayes** - assume all features are independent effects of the label\n",
              "\n",
              "\n",
              "# Module 13: Neural Networks\n",
              "## SLP Chapter 5.1 Classification: the sigmoid\n",
              "   \n",
              "\n",
              "## SLP Chapter 5.2 Learning in Logistic Regression\n",
              "  \n",
              "\n",
              "## SLP Chapter 5.3 The cross-entropy loss function\n",
              "   \n",
              "\n",
              "## SLP Chapter 5.4 Gradient Descent\n",
              "  \n",
              "\n",
              "## SLP Chapter 5.5 Regularization\n",
              "   \n",
              "\n",
              "## SLP Chapter 5.6 Multinomial logistic regression\n",
              " \n",
              "\n",
              "## SLP Chapter 7.1 Units\n",
              "   \n",
              "\n",
              "## SLP Chapter 7.2 The XOR problem\n",
              "   \n",
              "\n",
              "## SLP Chapter 7.3 Feedforward Neural Networks\n",
              "  \n",
              "\n",
              "## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n",
              "  \n",
              "\n",
              "## SLP Chapter 7.5 Feedforward Neural Language Modeling\n",
              "  \n",
              "\n",
              "## SLP Chapter 7.6 Training Neural Nets\n",
              " \n",
              "\n",
              "## SLP Chapter 7.7 Training the neural language model\n",
              " \n",
              "\n",
              "## Module 13 Lecture Notes\n",
              " The basic neural units that are used in neural networks are similar to the Perceptron \n",
              "\n",
              " Both have set of weights and bias terms that are automatically learned from data \n",
              "\n",
              " Can think of a neural network as a bunch of stacked perceptron. Early NN were called Multilayer perceptron \n",
              "\n",
              " NN use a loss function \n",
              "\n",
              " When updating the weights, need to attribute which of the weights from which parts of the neural network structure caused the error\n",
              "\n",
              " bc the NN has many stacked hidden layers, this can be tricky. Soln - Backpropagation! Uses differentiation over the network to undersand how each neural unit is affected by the ones it is connected to\n",
              "\n",
              " Neural Architectures: refer to how the neurons in the NN are organized, what kind of structure they form\n",
              "\n",
              "\n",
              " CLASSIFIER COMPONENTS\n",
              "\n",
              " -  ML classifiers require a training corpus of M observations input/output pairs ($x^{(i)}, y^{(i)}$)\n",
              "\n",
              " -  Feature representation of the input. For each input observation $x^{(i)}$, this will be a vector of features [X1, x2..xn]\n",
              "\n",
              " -  Classification function that computes the estimated class y-hat via $p(y|x)$\n",
              "\n",
              " -  Objective function for learning, usually involving minimizing error on training examples \n",
              "\n",
              " -  Algorithm for optimizing the objective function \n",
              "\n",
              "\n",
              " SENTIMENT CLASSIFIER \n",
              "\n",
              "  - Difference between perceptron is that we're gonna change what the range of outputs of our classifier can be\n",
              "\n",
              "\n",
              " LEARNING IN LOGISTIC REGRESSION\n",
              "\n",
              "  - How to get weights of the model? We learn the params (weights + bias) via learning. Requires (1) objective function or loss function that tells us distance between system output and gold output. Will use cross-entropy loss (2) algorithm for optimizing objective function. will use stochastic gradient descent to minimize loss function\n",
              "\n",
              "\n",
              " LOSS FUNCTIONS\n",
              "\n",
              "  - Mean squared error $L_{MSE}(y-hat, y) = 1/2(y-hat-y)^2$\n",
              "\n",
              "  - We use a loss function that prefers the correct class labels of the training example to be more likely\n",
              "\n",
              " -  Conditional maximum likelihood estimation: choose params w, b that maximize the (log) probabilities of the true labels in the training data\n",
              "\n",
              " -  Resulting loss function is the negative log likelihood loss, more commonly called cross entropy loss\n",
              "\n",
              " CROSS-ENTROPY LOSS\n",
              "\n",
              " -  $L_{CE}(y-hat, y) = -logp(y|x) = -[ylogy-hat + (1 - y)log(1-y-hat)]$\n",
              "\n",
              " -  $y-hat = \\sigma (wx) + b$\n",
              "\n",
              "  - Why does minimizing this negative log probability do what we want? We want the loss to be smaller if the model's estimate is close to correct, and we want the loss to be bigger if it is confused\n",
              "\n",
              " -  If prediction is correct, CE loss is lower, else higher\n",
              "\n",
              " LOSS ON ALL TRAINING EXAMPLES\n",
              "\n",
              " -  $logp(training lables) = log \\prod_{i =1}{m}p(y^{(i)}|x^{(i)}) = \\prod_{i =1}{m}logp(y^{(i)}|x^{(i)}) = - \\sum_{i =1}{m}L_{CE}(y-hat^{(i)}|y^{(i)})$\n",
              "\n",
              "\n",
              " FINDING GOOD PARAMETERS\n",
              "\n",
              "  - Gradient descent to find good settings for our weights and bias by minimizing loss function \n",
              "\n",
              " -  finds a min of a function by figuring out which direction the function's slope is rising the most steeply, and moving in the opposite direction\n",
              "\n",
              "\n",
              " LEARNING THE PARAMETERS - HOW TO GET WEIGHTS OF MODEL: if requires: \n",
              "\n",
              " - objective or loss function, use C.E. Loss\n",
              "\n",
              " - alg for optimizing ojective function - use Stoachastic gradient descent to minimize the loss function \n",
              "\n",
              "\n",
              " GLOBAL VS LOCAL MINIMUMS\n",
              "\n",
              " -  for logistic regression, this loss function is conveniently convex\n",
              "\n",
              " -  convex function has just one min, so no local min to get stuck in -> grad desc starting anyway is guarenteed to find min \n",
              "\n",
              " -  Magnitude of amt to move in gradient descent is value of slope weighted by learning rate n\n",
              "\n",
              " -  higher/faster learning rate means we should move w more on each step\n",
              "\n",
              "\n",
              " Derivative of CE-loss is (model's prediction - truth) * val of feature j \n",
              "\n",
              "\n",
              " MINI-BATCH TRAINING\n",
              "\n",
              "  - stochastic gradient descent chooses a single random example at a time and updates weights on that example. as a result the updates can fluctuate\n",
              "\n",
              " -  ALTERNATIVE; batch training, computes gradient over entire dataset - gives better estimate of where to move but takes a long time to compute\n",
              "\n",
              " -  commonly used compromise is min-batch training. batch size can be 512 or 1024 selected often based on computational resourcees. loss is accumulated \n",
              "\n",
              " REGULARIZATION\n",
              "\n",
              "  - In logistic regression, if a feature only occurs in one class, then will get a high weight. \n",
              "\n",
              "  - Regularization is a way to penalize large weights\n",
              "\n",
              " MULTINOMIAL LOGISTIC REGRESSION\n",
              "\n",
              "  - Instead of binary classification, might want more classes - use generalization of sigmoid function called softmax function\n",
              "\n",
              "\n",
              " NEURAL NETWORKS\n",
              "\n",
              "  - Output of one layer is input to another layer. One node output goes into all next layer's nodes\n",
              "\n",
              "  - Like perceptron, logistic regression uses vector of weights and a bias term (dot product z = w*x + b)\n",
              "\n",
              " ACTIVATION FUNCTIONS \n",
              "\n",
              " -  Building neural networks, want an activation function \n",
              "\n",
              " -  3 Commonly used non-linear functions for f: sigmoid, tanh, rectified linear unit ReLU\n",
              "\n",
              " -  The sigmoid function maps the output into range [0,1] and it is differentiable\n",
              "\n",
              " -  The tanh function is a variant of the sigmoid function and maps outlier values toward the mean \n",
              "\n",
              " FEED-FORWARD NN\n",
              "\n",
              "  - Simplest kind of NN. Multilayer network, all units are usually fully-connected, no cycles\n",
              "\n",
              "  - outputs from each layer are passes to units in the next higher layer, and no outputs are passed back to lower layers \n",
              "\n",
              "\n",
              " TRAINING NEURAL NETS\n",
              "\n",
              "  - What do we need? (1) A loss function - cross-entropy loss (2) optimization algo - gradient desc (3) A way of computing the gradient of the loss function - error propagation \n",
              "\n",
              " -  If the neural network is a binary classifier with a sigmoid at the final layer, the loss function is exactly the same as CE-Loss\n",
              "\n",
              " COMPUTING THE GRADIENT\n",
              "\n",
              " -  For deeper networks, computing the gradients requires looking back thru all earlier layers in network, even though the loss is only computed w respect to the output of the network\n",
              "\n",
              " -  Soln: Error Backpropagation Alg\n",
              "\n",
              " COMPUTATION GRAPHS\n",
              "\n",
              " -  Although backpropagation was invented for neural nets, related to general procedure called backward differentiation which depends on computation graphs\n",
              "\n",
              " -  In a forward pass graph, we apply each operation from left to right \n",
              "\n",
              "  - Backward differentiation uses chain rule\n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              "  - The result of ReLU for negative numbers is NOT the same as a linear function \n",
              "\n",
              " \n",
              "\n",
              "## Module 13 Definitions\n",
              "* **Loss function** - quantifies how wrong the model's predictions are for each item in training \n",
              "* **Computation graph** - represents the process of computing a mathematical expression, broken down into separate operations (each op a node in graph)\n",
              "\n",
              "\n",
              "# Module 14: Natural Language Processing\n",
              "## SLP Chapter 9.1 Language Models Revisited\n",
              "   \n",
              "\n",
              "## SLP Chapter 9.2 Recurrent Neural Networks\n",
              "  \n",
              "\n",
              "## SLP Chapter 9.3 RNNs as Language Models\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.1 Lexical Semantics\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.2 Vector Semantics\n",
              " \n",
              "\n",
              "## SLP Chapter 6.3 Words and Vectors\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.4 Cosine for measuring similarity\n",
              "  \n",
              "\n",
              "## SLP Chapter 6.8 Word2vec\n",
              "   \n",
              "\n",
              "## SLP Chapter 6.10 Semantic properties of embeddings\n",
              " \n",
              "\n",
              "## SLP Chapter 6.11 Bias and Embeddings\n",
              " \n",
              "\n",
              "## SLP Chapter 6.12 Evaluating Vector Models\n",
              "  \n",
              "\n",
              "## Module 14 Lecture Notes\n",
              " Neural Language Models advantages over n-gram LMs\n",
              "\n",
              "  - 1. No smoothing needed 2. Can handle much longer historiess 3. Can generalize over contexts of similar words 4. Neural LMs tend to have higher predictive accuracy than n-gram LMs \n",
              "\n",
              "  - Disadvantage: slower to train than traditional n-gram LMs \n",
              "\n",
              " NEURAL LMs\n",
              "\n",
              "  - 1. Associate each word in the vocab w a vector-representation, theyby creating notion of similarity btw words 2. Express joint probability function of a word seq in terms of word vectors for the words in that sequence 3. Simultaneously learn the word vectors and the parameters of teh function \n",
              "\n",
              "  - Word vectors are dim=30-100 dense, low dim. The probability func is expressed as the product of conditional probabilities of the next word given the previous word, using a multi-layer, feed forward neural network\n",
              "\n",
              "  - Input: k-gram of words $w_{1:k}$, Output: Probability idstribution over next word\n",
              "\n",
              "  - $k$ context words are treated as a word window. Each word is associated w an embedding vector \n",
              "\n",
              "  - Input vector $x$ just concatenates v(w) for each of the k words $x = [v(w_1);...;v(w_k)]$. Is fed into a NN w 1+ hidden layers\n",
              "\n",
              " - Tend to have much higher predictive accuracy than n-gram LMs\n",
              "\n",
              " - can generalize over contexts of similar words\n",
              "\n",
              " - dont need smoothing \n",
              "\n",
              " TRAINING (e.g. training examples are simply word k-grams from the corpus)\n",
              "\n",
              "  - Identities of the first k-1 words are used as features, adn teh last word is used as the target label for the classifation\n",
              "\n",
              "  - Conceptually model is trained using cross-entropy loss\n",
              "\n",
              " PROBABILITY TABLES\n",
              "\n",
              "  - Construct tables to look up the probability of seeing a word given a history \n",
              "\n",
              " UNSEEN SEQUENCES\n",
              "\n",
              "  - What happens when we have a new (unseen) combo of n words? \n",
              "\n",
              "  - 1. Back-off 2. Smoothing/interpolation (we are basically stitching together short sequences of observed words) \n",
              "\n",
              "  - Alternate idea: Intuition - take a sentence, and use it when we assign probabilities to similar sentences (the cat is walking in the bedroom -> the dog is running around the room) \n",
              "\n",
              " NEURAL PROBABILISTIC LM \n",
              "\n",
              "  - 1. Use a vector space model where the words are vectors w real values (gives a way to compute word similarity)\n",
              "\n",
              "  - 2. Define a function that returns a joint probability of words in a sequence based on a sequence of these vectors\n",
              "\n",
              "  - Simultaneously learn the word representations and the probability function from data\n",
              "\n",
              "  - Seeing one of the cat/dog sentences allows them to increase the probabiltiy for that sentence AND its combinatorial # of \"neighbor\" sentences in vector space\n",
              "\n",
              " WORD EMBEDDINGS\n",
              "\n",
              "  - When the ~50 dim vectors that result from training a neural LM are projected down to 2-dim, we see a lot of words that are intuitively similar to each other are close together \n",
              "\n",
              " WORD MEANING - How to represent meaning of a word?\n",
              "\n",
              "  - Ideally, we want a meaning representation to encode (1) Synonyms (2) Antonyms (3) Connotations, words that are pos or neg (4) Semantic Roles, buy sell and pay are different parts of the same underlying purchasing event (5) Support for entailment\n",
              "\n",
              " ENTAILMENT IN FORMAL SEMANTICS\n",
              "\n",
              " - Mathematically well-understhood, powerful machinery for handling logical ops, but knowledge must come from somewhere else\n",
              "\n",
              "\n",
              " Vector Space Models does not allow us to perform same kind of operations as if we had a taxonomic representation of word meaning \n",
              "\n",
              "  - But instead will let us do it at a large scale and do other operations. Automatically extract konowledge about a language from a giant corpus\n",
              "\n",
              " WORD SIMILARITY \n",
              "\n",
              "  - most words dont have many synonyms, but do have a lot of similar words \n",
              "\n",
              "  - Intuition of distributional word similarity: two words are similar if they have similar word contexts \n",
              "\n",
              "  - Cosine does L2 normalization too. Cosine angle between vectors tell the similarity\n",
              "\n",
              "\n",
              " TERM DOCUMENT MATRIX\n",
              "\n",
              "  - Column Vector: Document (prob will be sparse (lots of zeros), =size of vocab)\n",
              "\n",
              "  - Row: Term\n",
              "\n",
              "  - Cell: How often word occured in that document\n",
              "\n",
              "  - Length of document vectors is size of vocabulary\n",
              "\n",
              " TERM-TERM Matrix\n",
              "\n",
              "  - Length of vector is now |V| instead of number of documents\n",
              "\n",
              "  - Cell value indicates how often a word appears in a context window surrounding a word\n",
              "\n",
              " CONTEXT WINDOWS\n",
              "\n",
              "  - w-2, w-1 target word w+1 w+2\n",
              "\n",
              " ALTERNATES TO COUNTS\n",
              "\n",
              "  - Raw word freq is not a great measure of association between words. We'd rather have a measure that asks whether a context word is particularly informative about the target word\n",
              "\n",
              "  - Instead of raw counts, common to transform vectors using TF-IDR or PPMI \n",
              "\n",
              "  - TF-IDF (Term freq inverse document frequency)\n",
              "\n",
              " -  How often a word occurred in doc, 1 over the number of docs that it occured on\n",
              "\n",
              "\n",
              " SPARSE VS DENSE VECTORS\n",
              "\n",
              "  - Co-occurence matrix (weighted by TF-IDF or mutual info). long (len(V) = 50000+) and sparse (most elem=0)\n",
              "\n",
              " -  Alternative: learn vectors that are short (200-1000) and dense (most elem nonzero)\n",
              "\n",
              " HOW TO GET DENSE VECTORS\n",
              "\n",
              "  - 1 way: train a classifier\n",
              "\n",
              "  - 1. Treat target word and neighboring context word as positive examples 2. Randomly sample other words in lexicon to get negative samples 3. use logistic regression to train a classifier to distinguish those two cases 4. use the weights as the embeddings\n",
              "\n",
              "\n",
              " WORD2VEC (learn embeddings as part of the process of word prediction)\n",
              "\n",
              "   - Train a classifier to predict neighboring words, inspired by NN lang models. in doing so, learn dense embeddings for the words in the training corpus\n",
              "\n",
              " -  Advantages: fast, easy to train (faster than SVD), avail online \n",
              "\n",
              "\n",
              " EXTRA NOTES:\n",
              "\n",
              " -  n-gram language models are typically evaluated by perplexity on a test set\n",
              "\n",
              "\n",
              "\n",
              "## Module 14 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Default title text\n",
        "# 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))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Template_for CIS521_midterm_2_notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
