{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": " CIS521_midterm_2_notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 2\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "11d80255-c1ca-40ea-9de9-1f1571487adb"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "ea4eb53c-6dad-41e4-9636-f70f5dc08447"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 8 - Markov Decision Process"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 16, “Making Simple Decisions” (16.1-16.3)\n",
        "\n",
        "q_val = r\"\"\" $V^*(s) = max_a Q^*(s,a)$ \"\"\"\n",
        "\n",
        "q_val2 = r\"\"\" $Q^*(s,a)= \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^*(s')]$ \"\"\"\n",
        "\n",
        "chapter16_1 = \"\"\" Chapter 16.1 summary. \"\"\"\n",
        "chapter16_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 17, “Making Complex Decision” (17.1-17.2)\n",
        "chapter17_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter17_2 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module8_lecture_notes = \"\"\"\n",
        "\n",
        "### Stochastic or Probabilistic Task Environments: MDPs\n",
        "\n",
        "MDPs are a kind of non-deterministic search problem that are applicable \\\n",
        "in a fully observable task environment where outcomes are non-deterministic. The \\\n",
        "solutions to MDPs are called policies. We will look at Expectimax, \\\n",
        "Value iteration, and Policy iteration to solve MDPs.\n",
        "\n",
        "#### Introduction\n",
        "\n",
        "Toy Problem : Navigating an Asteroid Field \n",
        "+ navigating a fully observable gridworld \n",
        "+ starting at a start state, and picking an action at each turn\n",
        "+ terminates at asteroid crashor reaching planet \n",
        "+ stochasticenvironmenty, when we pick an action the result of the action is uncertain\n",
        "  + there is some probability of moving up and some probability of something weird happening\n",
        "+ we must define a probabilistic transition model\n",
        "\n",
        "Stochastic Transition Model\n",
        "+ transition function T(s, a, s') (current state s, action I apply in s a, and next state s')\n",
        "+ p(s'|s,a) is the probability that the transition function is taking on \n",
        "+ we ignore the historyup until the current point, Markov Property\n",
        "\n",
        "Reward Function\n",
        "+ rewards can be positive or negative, bounded by a max value\n",
        "+ since rewards are sequential, we must extablish a utility function in a sequence of states\n",
        "+ an agentcan recieve a reward at eeach state, not only at the goal state \n",
        "+ R(s, a, s') is reward of taking action a in state s to get to state s'\n",
        "+ rewards are additive over. all steps you take\n",
        "\n",
        "\n",
        "\n",
        "#### MDP Formulation\n",
        "\n",
        "Markov Decision Process: a sequential decision model for a fully observable \n",
        "environment with a stochastic transition model with additive rewards (non-determinstic search)\n",
        "\n",
        "Formal Definition \n",
        "+ a set of states S\n",
        "+ a set of actions A\n",
        "+ the transition function T(s, a, s') called the model\n",
        "+ the reward function R(s, a, s') or R(s')\n",
        "+ initial and terminal states\n",
        "+ solution is a policy pi(s) = a (a function that tells the agent what action it should take if its at state s)\n",
        "+ in a gridworld, can be represented by arrows on a grid\n",
        "+ we would like to find the optimal policy, pi* (depends on reward function)\n",
        "+ because of non-determinism (if i execute the same policy many times I will gget a diff score every time)\n",
        "+ use the expected utility of all possible paths\n",
        "+ games may have an infinite horizon! bounce around forever \n",
        "\n",
        "Should we value more reward sooner or later? How do we model this? Rewards now because if we \\\n",
        "defer them into  the future there is some chance we do not end up with them.\n",
        "\n",
        "Discounting Term : how much we are willing to postpone immediate gratification\n",
        "discount value is gamma \n",
        "\n",
        "We can vizualise the search as an expectimax tree, where at each layer we apply the discount \n",
        "\n",
        "Stationary Preferences: if i prefer seq a to seq b [a1, a2, a3] > [b1, b2, b3], then [r, a1, a2,a3] > [r, b1, b2,b3]\n",
        "\n",
        "Two ways to define utilities: \n",
        "+ U[r1, r2, r3....] = r1+r2+r3\n",
        "+U[r1, r2, r3....] = r1+gr2+g^2r3\n",
        "\n",
        "To handle infinite utility:\n",
        "+ Only allowing a finite horizon (k steps until game over) and non-stationary policy (depends on time left in the game)\n",
        "+ discounting (eventuallywill converge as a sum)\n",
        "+ absorbing state (ifyou runany policy long enough a terminal state will be reached )\n",
        "\n",
        "\n",
        "#### Value Iteration Algorithm\n",
        " algorithm for choosing optimal actions\n",
        " + start with V_0(s)= 0 : notimee steps left means an expected reward sum of 0 (subscript is thenumber of timesteps remaining)\n",
        " + $V_{k+1} = \\max_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V_k^*(s')]$ BELLMAN EQUATION\n",
        " + do this recursively (increase k at each iteration)\n",
        " + $O(S^2A)$ every state may be connected to all other states (O(mmn)) in a fully connected graph\n",
        " + approximationswill reach optimal values because of the vanishing rewrad in thediscount factor\n",
        "\n",
        " Convergence* : finding the optimal policy \n",
        " + How do we know $V_k$ will converge? two cases \n",
        "  + max depth M, theen V_M holds as best policy\n",
        "  + if discount is less than 1, any state can be viewed to converge because each layer has exponential decay\n",
        "\n",
        "#### Policy Evaluation\n",
        "\n",
        "+ given a policy $\\pi$, what values do I get from it? \n",
        "+ if i fixes a policy $\\pi$ the tree gets much simpler\n",
        "+ $V^{\\pi}(s)= \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+ \\gamma V^{\\pi}(s')]$\n",
        "+ we can do this recursively $O(S^2)$ same as value iteration\n",
        "+ or, can be solvedas a system of linear equations \n",
        "\n",
        "Policy Extraction\n",
        "+ given a set of values we assume are correct, what policy should w take? \n",
        "+ we do a mini expectimax\n",
        "+ $\\pi ^* (s) = argmax_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^{*}(s')]$\n",
        "+ gets policy implied by the values\n",
        "\n",
        "#### Policy Iteration Algorithm\n",
        "+ value iteration is slow (both iteration and convergence), policy convergence is much better!\n",
        "+ Step 1: calculate the utilitiy of a fixed policy \n",
        "  + $V_{k+1}^{\\pi}(s)= \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+ \\gamma V_k^{\\pi}(s')]$ until values converge \n",
        "  + no max operation, values converge must faster\n",
        "+ Step 2: Improve by updating the policy using a one-step look ahead (estimate of how good itis to be at a particular state)\n",
        "  + $\\pi_{i+1} ^* (s) = argmax_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^{\\pi_i}(s')]$\n",
        "\n",
        "#### Comparing Value Iteration to Policy Iteration\n",
        "+ in Value iteration\n",
        "  + every iteration updates both value and policy (implicitly by taking max a )\n",
        "  + we dont track policy, but were continually recomputing it \n",
        "+ in policy iteration\n",
        "  + several passes that. update utilitygiven a policy (fast)\n",
        "  + a new policy is chosen after evaluation\n",
        "  + if no better exists, we are done \n",
        "\n",
        "\n",
        "#### Maximum Expected Utility\n",
        "+ why should we average utilitties instead of minimax? \n",
        "  + minimax looks a the WORST CASE, assuming playing against an adversary\n",
        "+ a rational agent should pick the action that maximizes the exoected utility given its knowledge about the world \n",
        "+ where do these utilities come from, how do we know they exist, is averaging the right way to do this? \n",
        "+ expectimax does not have insensitivity to transformations, MAGNITUDES MATTER\n",
        "\n",
        "Utilities\n",
        "+ map of state of thee world onto a real valued number \n",
        "+ represents the agent's preferencees of how good an outcome is \n",
        "+ Thm: any rational preference can be summarized by its utility function\n",
        "+ hard wire utilities and let behaviors emerge\n",
        "\n",
        "Prefereneces\n",
        "+ prizes A, B\n",
        "+ lotteries L = [p, A; 1-p, B]\n",
        "+ preferenece A > B\n",
        "+ Indifference A ~ B\n",
        "\n",
        "Axioms:\n",
        "\n",
        "+ Transitivity : $(A > B) \\wedge (B > C) \\Rightarrow (A > C)$\n",
        "+ Orderability : $(A > B) \\vee ( B > A) \\vee (A ~ B)$\n",
        "+ Continuity: $A > B > C \\Rightarrow \\exists p [p, A; 1-p, C] ~ B$\n",
        "+ Substitutability: $A ~ B \\Rightarrow [p, A; 1-p, C] ~ [p, B; 1-p, C]$\n",
        "+ Monotonicity: $ A > B \\Rightarrow ( p \\geq q \\Leftrightarrow [p, A; 1-p, C] ~ [q, A; 1-q, B])$ (If an agent prefers A to B \\\n",
        "and there are two lotteries with outcomes A and B, then the agent must prefer the lottery that has a higher probability for A.)\n",
        "+ Given anny preferences that satisfy those axioms, there exists a real valued function that satisfies your preferences \n",
        "+ $U([p_1, S_1,....,p_n,S_n]) = \\sum_ip_iU(S_i)$\n",
        "+ MEU\n",
        "\n",
        "Utility Scales \n",
        "+ normalize utilitues between $u_-$ and $u_+$\n",
        "+ micromorts, one millionth cance of death\n",
        "+ QALYs, quality adjusted life years\n",
        "\n",
        "Human Utilities \n",
        "+ associate best possible prize with p and worst catastrophe with 1-p\n",
        "+ find the p that makes you indiffereent, then you know the utility\n",
        "+ money does not behavee as a utility function\n",
        "+ Expected monetary value of a lottery is p \\$X + 1-p\\$Y\n",
        "+ sometimes people are isk averse, avoid lottery over the money\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 8.\n",
        "# You can define any bolded term in the textbook, \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",
        "\"optimal Q value\" : \"expected utility of having taken action a from state s and then acting optimally (p(s') + r(s') * discounted s')\",\n",
        "\"Q*(s,a)\": q_val2,\n",
        "\"V*(s)\" : \"expected utility startingin s and acting optimally\" + q_val,\n",
        "\"pi*(s)\" : \"optimal policy from state s\",\n",
        "\"policy\": \"takes in a state and returns a best action that an agent can take when it finds that state\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 8\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3103
        },
        "cellView": "form",
        "outputId": "14af762d-40eb-4618-c9a1-4d99366db8fd"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module8_sections = [\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"AIMA Chapter 17.1 Sequential Decision Problems\", chapter17_1),\n",
        "  (\"AIMA Chapter 17.2 Algorithms for MDPs\", chapter17_2),\n",
        "  (\"Module 8 Lecture Notes\", module8_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 25):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module8_markdown = format_module(8, \"Markov Decision Processes\", module8_sections, module8_definitions)\n",
        "display(Markdown(module8_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n\n\n### Stochastic or Probabilistic Task Environments: MDPs\n\nMDPs are a kind of non-deterministic search problem that are applicable in a fully observable task environment where outcomes are non-deterministic. The solutions to MDPs are called policies. We will look at Expectimax, Value iteration, and Policy iteration to solve MDPs.\n\n#### Introduction\n\nToy Problem : Navigating an Asteroid Field \n+ navigating a fully observable gridworld \n+ starting at a start state, and picking an action at each turn\n+ terminates at asteroid crashor reaching planet \n+ stochasticenvironmenty, when we pick an action the result of the action is uncertain\n  + there is some probability of moving up and some probability of something weird happening\n+ we must define a probabilistic transition model\n\nStochastic Transition Model\n+ transition function T(s, a, s') (current state s, action I apply in s a, and next state s')\n+ p(s'|s,a) is the probability that the transition function is taking on \n+ we ignore the historyup until the current point, Markov Property\n\nReward Function\n+ rewards can be positive or negative, bounded by a max value\n+ since rewards are sequential, we must extablish a utility function in a sequence of states\n+ an agentcan recieve a reward at eeach state, not only at the goal state \n+ R(s, a, s') is reward of taking action a in state s to get to state s'\n+ rewards are additive over. all steps you take\n\n\n\n#### MDP Formulation\n\nMarkov Decision Process: a sequential decision model for a fully observable \nenvironment with a stochastic transition model with additive rewards (non-determinstic search)\n\nFormal Definition \n+ a set of states S\n+ a set of actions A\n+ the transition function T(s, a, s') called the model\n+ the reward function R(s, a, s') or R(s')\n+ initial and terminal states\n+ solution is a policy pi(s) = a (a function that tells the agent what action it should take if its at state s)\n+ in a gridworld, can be represented by arrows on a grid\n+ we would like to find the optimal policy, pi* (depends on reward function)\n+ because of non-determinism (if i execute the same policy many times I will gget a diff score every time)\n+ use the expected utility of all possible paths\n+ games may have an infinite horizon! bounce around forever \n\nShould we value more reward sooner or later? How do we model this? Rewards now because if we defer them into  the future there is some chance we do not end up with them.\n\nDiscounting Term : how much we are willing to postpone immediate gratification\ndiscount value is gamma \n\nWe can vizualise the search as an expectimax tree, where at each layer we apply the discount \n\nStationary Preferences: if i prefer seq a to seq b [a1, a2, a3] > [b1, b2, b3], then [r, a1, a2,a3] > [r, b1, b2,b3]\n\nTwo ways to define utilities: \n+ U[r1, r2, r3....] = r1+r2+r3\n+U[r1, r2, r3....] = r1+gr2+g^2r3\n\nTo handle infinite utility:\n+ Only allowing a finite horizon (k steps until game over) and non-stationary policy (depends on time left in the game)\n+ discounting (eventuallywill converge as a sum)\n+ absorbing state (ifyou runany policy long enough a terminal state will be reached )\n\n\n#### Value Iteration Algorithm\n algorithm for choosing optimal actions\n + start with V_0(s)= 0 : notimee steps left means an expected reward sum of 0 (subscript is thenumber of timesteps remaining)\n + $V_{k+1} = \\max_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V_k^*(s')]$ BELLMAN EQUATION\n + do this recursively (increase k at each iteration)\n + $O(S^2A)$ every state may be connected to all other states (O(mmn)) in a fully connected graph\n + approximationswill reach optimal values because of the vanishing rewrad in thediscount factor\n\n Convergence* : finding the optimal policy \n + How do we know $V_k$ will converge? two cases \n  + max depth M, theen V_M holds as best policy\n  + if discount is less than 1, any state can be viewed to converge because each layer has exponential decay\n\n#### Policy Evaluation\n\n+ given a policy $\\pi$, what values do I get from it? \n+ if i fixes a policy $\\pi$ the tree gets much simpler\n+ $V^{\\pi}(s)= \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+ \\gamma V^{\\pi}(s')]$\n+ we can do this recursively $O(S^2)$ same as value iteration\n+ or, can be solvedas a system of linear equations \n\nPolicy Extraction\n+ given a set of values we assume are correct, what policy should w take? \n+ we do a mini expectimax\n+ $\\pi ^* (s) = argmax_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^{*}(s')]$\n+ gets policy implied by the values\n\n#### Policy Iteration Algorithm\n+ value iteration is slow (both iteration and convergence), policy convergence is much better!\n+ Step 1: calculate the utilitiy of a fixed policy \n  + $V_{k+1}^{\\pi}(s)= \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+ \\gamma V_k^{\\pi}(s')]$ until values converge \n  + no max operation, values converge must faster\n+ Step 2: Improve by updating the policy using a one-step look ahead (estimate of how good itis to be at a particular state)\n  + $\\pi_{i+1} ^* (s) = argmax_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^{\\pi_i}(s')]$\n\n#### Comparing Value Iteration to Policy Iteration\n+ in Value iteration\n  + every iteration updates both value and policy (implicitly by taking max a )\n  + we dont track policy, but were continually recomputing it \n+ in policy iteration\n  + several passes that. update utilitygiven a policy (fast)\n  + a new policy is chosen after evaluation\n  + if no better exists, we are done \n\n\n#### Maximum Expected Utility\n+ why should we average utilitties instead of minimax? \n  + minimax looks a the WORST CASE, assuming playing against an adversary\n+ a rational agent should pick the action that maximizes the exoected utility given its knowledge about the world \n+ where do these utilities come from, how do we know they exist, is averaging the right way to do this? \n+ expectimax does not have insensitivity to transformations, MAGNITUDES MATTER\n\nUtilities\n+ map of state of thee world onto a real valued number \n+ represents the agent's preferencees of how good an outcome is \n+ Thm: any rational preference can be summarized by its utility function\n+ hard wire utilities and let behaviors emerge\n\nPrefereneces\n+ prizes A, B\n+ lotteries L = [p, A; 1-p, B]\n+ preferenece A > B\n+ Indifference A ~ B\n\nAxioms:\n\n+ Transitivity : $(A > B) \\wedge (B > C) \\Rightarrow (A > C)$\n+ Orderability : $(A > B) \u000bee ( B > A) \u000bee (A ~ B)$\n+ Continuity: $A > B > C \\Rightarrow \\exists p [p, A; 1-p, C] ~ B$\n+ Substitutability: $A ~ B \\Rightarrow [p, A; 1-p, C] ~ [p, B; 1-p, C]$\n+ Monotonicity: $ A > B \\Rightarrow ( p \\geq q \\Leftrightarrow [p, A; 1-p, C] ~ [q, A; 1-q, B])$ (If an agent prefers A to B and there are two lotteries with outcomes A and B, then the agent must prefer the lottery that has a higher probability for A.)\n+ Given anny preferences that satisfy those axioms, there exists a real valued function that satisfies your preferences \n+ $U([p_1, S_1,....,p_n,S_n]) = \\sum_ip_iU(S_i)$\n+ MEU\n\nUtility Scales \n+ normalize utilitues between $u_-$ and $u_+$\n+ micromorts, one millionth cance of death\n+ QALYs, quality adjusted life years\n\nHuman Utilities \n+ associate best possible prize with p and worst catastrophe with 1-p\n+ find the p that makes you indiffereent, then you know the utility\n+ money does not behavee as a utility function\n+ Expected monetary value of a lottery is p \\$X + 1-p\\$Y\n+ sometimes people are isk averse, avoid lottery over the money\n\n\n\n## Module 8 Definitions\n* **Optimal q value** - expected utility of having taken action a from state s and then acting optimally (p(s') + r(s') * discounted s')\n* **Q*(s,a)** -  $Q^*(s,a)= \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^*(s')]$ \n* **V*(s)** - expected utility startingin s and acting optimally $V^*(s) = max_a Q^*(s,a)$ \n* **Pi*(s)** - optimal policy from state s\n* **Policy** - takes in a state and returns a best action that an agent can take when it finds that state\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 9 - Reinforcement Learning"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# Russell and Norvig, AIMA Section 17.3 “Bandit Problems”\n",
        "chapter17_3 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 22 “Reinforcement Learning” (Sections 22.1-22.5)\n",
        "chapter22_1 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_2 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_3 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_4 =  \"\"\" Your summary here \"\"\"\n",
        "chapter22_5 =  \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module9_lecture_notes = \"\"\"\n",
        "\n",
        "### Introduction to Reinforcement Learning\n",
        "\n",
        "+ in MDPs, even though the environment was stochastic, we knew the probability dist over states and the rewards\n",
        "+ we no longer have that given to us, we have to learn it\n",
        "+ multi arm bandits (like slot machines in vegas) offline planning, you don't have to play at all to do this\n",
        "+ What if you don't know the probabilities? You try it out\n",
        "+ MDPs are planning, we now have to learn\n",
        "+ Ideas\n",
        "  + exploration : the amount of time you have to do to try new things to havee enough info\n",
        "  + exploitation: eventually, you have to use what you know\n",
        "  + Regret: even if you learn, you make mistakes\n",
        "  + Sampling: because of chance, you have to try thinsg repeatedly\n",
        "  + Difficulty: learning is harder than solving an MDP\n",
        "\n",
        "+ a set of states S\n",
        "+ a set of actions A\n",
        "+ a model T(s, a,  s') NOT GIVEN\n",
        "+ reward function R(s, a, s') NOT GIVEN\n",
        "+ still looking for $\\pi(s)$\n",
        "\n",
        "Model Based Learning: approximate T by learning, $\\hat{T}$ and what we have experienced, then plug it in as an MDP\n",
        "\n",
        "### Passive Reinforcement Learning: Model Free\n",
        "+ take an action and compare reesults of what we thought was gonna happen towhat actually did happen\n",
        "+ if there is a deviation, we adjust the values\n",
        "+ Simplified task policy evaluation \n",
        "  + given a policy, how good is it? watch the outcomes \n",
        "  + the learner is just along for the ride\n",
        "  + not offline, you still have to do the policy\n",
        "  + direct evaluation, according to pi, average together observed values (run through to the end)\n",
        "    + you do not need to keep track of instantaneous reward \n",
        "    + does not take into account structure, takes a long time to learn\n",
        "+ why don't we use policy evaluation? with recursive iteration (as in module 8) we would need T and R, and we don't have that \n",
        "+ can we make soething similar to policy evaluation without T and R?\n",
        "+ take samples of s' and average over all of the samples\n",
        "  + $sample_1 = R(s, \\pi(s), s'_1) + \\gamma V^{\\pi}_k(s'_1)$\n",
        "  + $sample_2 = R(s, \\pi(s), s'_2) + \\gamma V^{\\pi}_k(s'_2)$\n",
        "  + $sample_n = R(s, \\pi(s), s'_n) + \\gamma V^{\\pi}_k(s'_n)$\n",
        "  + $V^{\\pi}_{k+1} = \\\\frac{1}{n} \\sum_i sample_i$\n",
        "  + can we guarantee that we will be in s n times? we cant do it again and again\n",
        "  + this is NOT possible\n",
        "\n",
        "### Temporal Difference Learning\n",
        "+ learn from every experience \n",
        "+ Update V(s) every time you experieence (s, a, s', r)\n",
        "+ things that are more likely to occur will update values more often \n",
        "+ follow pi, keep a running average \n",
        "+ $sample = R(s, \\pi(s), s') + \\gamma V^{\\pi}_k(s')$\n",
        "+ $V^{\\pi}(s) = (1- \\\\alpha) V^{\\pi}(s) + \\\\alpha sample$\n",
        " + $V^{\\pi}(s) = V^{\\pi}(s) + \\\\alpha (sample -  V^{\\pi}(s))$\n",
        "+ alpha is the learning rate, how much new samples contribute to the updates\n",
        "+ comparing current extimates against sample value, called interpolation\n",
        "+ more recent samples end up being more important over time (1 - $\\\\alpha$ gets exponentially decayed)\\\n",
        "+ this is modeel free learning\n",
        "+ problems with this: \n",
        "  + wee cannot turn values into a new policy, we need q values (what is the best action to take at s\n",
        "  + we only have the value of the states \n",
        "\n",
        "### Active Reinforcement Learning (Q - Learning)\n",
        "+ we still dont know transitions or rewards, we want to learn the optimal policy \n",
        "+ Q state is a state action pair\n",
        "+ instead of being.  iven a policy, like in passive, you get to make all of the choices\n",
        "+ exploration (try to do new, risk) v exploitation (using the knowledge youve acrued so far to make predictions)\n",
        "\n",
        "Q- Value Iteration\n",
        "+ start with a time delimited number of step $V_0(s) = 0$(subscript is the number of steps left)\n",
        "+ Given $V_k$ calculate $V_{k+1}$ using bellman equation (see above) bottom up recursion works nicely here (DP)\n",
        "+ But, when looking to determine a policy, value of Q state is easier to do policy extraction\n",
        "+ So, transforming this notion\n",
        "  + $Q_0(s,a)$\n",
        "  + $Q_{k+1}(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma max_{a'}Q_k^*(s', a')]$\n",
        "  + you can easily extract actions to buold a policy from this\n",
        "\n",
        "Q-Learning \n",
        "+ a bit different than q value iteration since we dont know T and R\n",
        "+ Q learning is sample based Q-value iteration \n",
        "+ learn Q values as we go\n",
        "+ a sample is (s, a, s', r) we are in s, we choose a, we non-deterministically end up in s', and get a reward r\n",
        "+ consider the current Q(s,a) that you have (old approx)\n",
        "+ $sample = R(s, a, s') + \\gamma \\max_{a'} Q(s',a')$\n",
        "+ keep a running average (there is no gurantee that you will ever end up in a state again)\n",
        "  + UPDATE $Q(s, a) = (1- \\\\alpha)Q(s, a)+ \\\\alpha(sample)$\n",
        "  + $\\\\alpha$ is the learning rate, how much we trust new data versus estimates we accrued\n",
        "+ we converge to the optimal policy EVEN IF we act suboptimally\n",
        "+ called off-policy learning \n",
        "  + you have to learn enough (try new things)\n",
        "  + you have to make the learning rate small enough\n",
        "\n",
        "### Exploration vs Exploitation\n",
        "+ ineviatble tradeoff between trying new things and going based off of knowledge \n",
        "\n",
        "How do we Explore? \n",
        "+ Simplest method: $\\epsilon$- greedy\n",
        "  + generate a random number\n",
        "  + if its less than $\\epsilon$ act randomly\n",
        "  + else act on current policy\n",
        "  + epsolon is small, and. acts as a prrobability\n",
        "  + using randomness, we may repeat bad actions during the random step\n",
        "    + to fix: decrease epsilon over time \n",
        "    + encode a function to weight the random actions \n",
        "\n",
        "Exploration Function\n",
        "+ eexplore areas whos badness is not yet established, eventually stop exploring \n",
        "+ $f(u, n) = u + \\\\frac{k}{n}$ $u$ is current utility estimate of a state and n is the number of times its been explored\n",
        "  + if its a good state we will visit again, if its a bad state we only visit while n is small\n",
        "+ REGULAR UPDATE $Q(s, a) = \\\\alpha(R(s, a, s') + \\gamma \\max_{a'} Q(s',a')$\n",
        "+ MODIFIED UPDATE $Q(s, a) = \\\\alpha(R(s, a, s') + \\gamma \\max_{a'} f(Q(s',a'), N(s',a'))$\n",
        "\n",
        "Regret\n",
        "+ you will eventually get to the optimal policy, but not sure how quickly\n",
        "+ regret measures how many mistakes you made overtime\n",
        "  + the difference between your expected rewards and optimal expected rewards\n",
        "  + minimizing regret tries to learn optimal as quickly as possible\n",
        "\n",
        "### Approximate Q-Learning \n",
        "+ when there are lots of possible states, we ecant visit every one \n",
        "+ generalize about states \n",
        "+ Q-Learning maintains a huge table of state action pairrs\n",
        "  + for large game states like chess, this is not possible \n",
        "\n",
        "Generalizing Across States\n",
        "+ we cannot possibly learn about every single state\n",
        "+ learn through observation from training states\n",
        "+ generalize to new statees that wee have never seen before that are somehow SIMILAR\n",
        "+ flashback -- evaluation functions, take a partial completed state and take feeatures to make an estimate \n",
        "  + quantifying features and assigning weights to them\n",
        "\n",
        "Linear Value Function\n",
        "+ using a feature representation, we can write a q function or value function for any state using weights \n",
        "  + $V(s) = w_1f_1(s) + w_2f_2(s)+...+w_nf_n(s)$\n",
        "  + $Q(s,a) = w_1f_1(s) + w_2f_2(s,a)+...+w_nf_n(s,a)$\n",
        "+ advantage: experiencee is summed up in a few powerful numbers\n",
        "+ states may share the same features but be different, and we miss that \n",
        "+ learning algorithm setsthe weights automatically\n",
        "+ transition = (s, a, r, s')\n",
        "+ difference = $[r + \\gamma \\max_{a'}Q(s', a')] - Q(s, a)$ difference from what i though i would get from what it is seeming like i am getting now \n",
        "  + Exact Q learning,  take current q and add in alpha times difference \n",
        "  + approximate q learning $w_i = w_i + \\\\alpha [difference]f_i(s,a)$ update weights in proportion to the feature value\n",
        "  + intuitive interpretation, each of the weights is like a slider\n",
        "  + formal justification, online least squares\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module9_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3089
        },
        "cellView": "form",
        "outputId": "e58f0552-5b8d-44a9-e547-47140134a0bc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module9_sections = [\n",
        "  (\"AIMA Chapter 17.3 Bandit Problems\", chapter17_3),\n",
        "  (\"AIMA Chapter 22.1 Learning from Rewards\", chapter22_1),\n",
        "  (\"AIMA Chapter 22.2 Passive Reinforcement Learning\", chapter22_2),\n",
        "  (\"AIMA Chapter 22.3 Active Reinforcement Learning\", chapter22_3),\n",
        "  (\"AIMA Chapter 22.4 Generalization in Reinforcement Learning\", chapter22_4),\n",
        "  (\"Module 9 Lecture Notes\", module9_lecture_notes),\n",
        "]\n",
        "\n",
        "module9_markdown = format_module(9, \"Reinforcement Learning\", module9_sections, module9_definitions)\n",
        "display(Markdown(module9_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n\n### Introduction to Reinforcement Learning\n\n+ in MDPs, even though the environment was stochastic, we knew the probability dist over states and the rewards\n+ we no longer have that given to us, we have to learn it\n+ multi arm bandits (like slot machines in vegas) offline planning, you don't have to play at all to do this\n+ What if you don't know the probabilities? You try it out\n+ MDPs are planning, we now have to learn\n+ Ideas\n  + exploration : the amount of time you have to do to try new things to havee enough info\n  + exploitation: eventually, you have to use what you know\n  + Regret: even if you learn, you make mistakes\n  + Sampling: because of chance, you have to try thinsg repeatedly\n  + Difficulty: learning is harder than solving an MDP\n\n+ a set of states S\n+ a set of actions A\n+ a model T(s, a,  s') NOT GIVEN\n+ reward function R(s, a, s') NOT GIVEN\n+ still looking for $\\pi(s)$\n\nModel Based Learning: approximate T by learning, $\\hat{T}$ and what we have experienced, then plug it in as an MDP\n\n### Passive Reinforcement Learning: Model Free\n+ take an action and compare reesults of what we thought was gonna happen towhat actually did happen\n+ if there is a deviation, we adjust the values\n+ Simplified task policy evaluation \n  + given a policy, how good is it? watch the outcomes \n  + the learner is just along for the ride\n  + not offline, you still have to do the policy\n  + direct evaluation, according to pi, average together observed values (run through to the end)\n    + you do not need to keep track of instantaneous reward \n    + does not take into account structure, takes a long time to learn\n+ why don't we use policy evaluation? with recursive iteration (as in module 8) we would need T and R, and we don't have that \n+ can we make soething similar to policy evaluation without T and R?\n+ take samples of s' and average over all of the samples\n  + $sample_1 = R(s, \\pi(s), s'_1) + \\gamma V^{\\pi}_k(s'_1)$\n  + $sample_2 = R(s, \\pi(s), s'_2) + \\gamma V^{\\pi}_k(s'_2)$\n  + $sample_n = R(s, \\pi(s), s'_n) + \\gamma V^{\\pi}_k(s'_n)$\n  + $V^{\\pi}_{k+1} = \\frac{1}{n} \\sum_i sample_i$\n  + can we guarantee that we will be in s n times? we cant do it again and again\n  + this is NOT possible\n\n### Temporal Difference Learning\n+ learn from every experience \n+ Update V(s) every time you experieence (s, a, s', r)\n+ things that are more likely to occur will update values more often \n+ follow pi, keep a running average \n+ $sample = R(s, \\pi(s), s') + \\gamma V^{\\pi}_k(s')$\n+ $V^{\\pi}(s) = (1- \\alpha) V^{\\pi}(s) + \\alpha sample$\n + $V^{\\pi}(s) = V^{\\pi}(s) + \\alpha (sample -  V^{\\pi}(s))$\n+ alpha is the learning rate, how much new samples contribute to the updates\n+ comparing current extimates against sample value, called interpolation\n+ more recent samples end up being more important over time (1 - $\\alpha$ gets exponentially decayed)+ this is modeel free learning\n+ problems with this: \n  + wee cannot turn values into a new policy, we need q values (what is the best action to take at s\n  + we only have the value of the states \n\n### Active Reinforcement Learning (Q - Learning)\n+ we still dont know transitions or rewards, we want to learn the optimal policy \n+ Q state is a state action pair\n+ instead of being.  iven a policy, like in passive, you get to make all of the choices\n+ exploration (try to do new, risk) v exploitation (using the knowledge youve acrued so far to make predictions)\n\nQ- Value Iteration\n+ start with a time delimited number of step $V_0(s) = 0$(subscript is the number of steps left)\n+ Given $V_k$ calculate $V_{k+1}$ using bellman equation (see above) bottom up recursion works nicely here (DP)\n+ But, when looking to determine a policy, value of Q state is easier to do policy extraction\n+ So, transforming this notion\n  + $Q_0(s,a)$\n  + $Q_{k+1}(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma max_{a'}Q_k^*(s', a')]$\n  + you can easily extract actions to buold a policy from this\n\nQ-Learning \n+ a bit different than q value iteration since we dont know T and R\n+ Q learning is sample based Q-value iteration \n+ learn Q values as we go\n+ a sample is (s, a, s', r) we are in s, we choose a, we non-deterministically end up in s', and get a reward r\n+ consider the current Q(s,a) that you have (old approx)\n+ $sample = R(s, a, s') + \\gamma \\max_{a'} Q(s',a')$\n+ keep a running average (there is no gurantee that you will ever end up in a state again)\n  + UPDATE $Q(s, a) = (1- \\alpha)Q(s, a)+ \\alpha(sample)$\n  + $\\alpha$ is the learning rate, how much we trust new data versus estimates we accrued\n+ we converge to the optimal policy EVEN IF we act suboptimally\n+ called off-policy learning \n  + you have to learn enough (try new things)\n  + you have to make the learning rate small enough\n\n### Exploration vs Exploitation\n+ ineviatble tradeoff between trying new things and going based off of knowledge \n\nHow do we Explore? \n+ Simplest method: $\\epsilon$- greedy\n  + generate a random number\n  + if its less than $\\epsilon$ act randomly\n  + else act on current policy\n  + epsolon is small, and. acts as a prrobability\n  + using randomness, we may repeat bad actions during the random step\n    + to fix: decrease epsilon over time \n    + encode a function to weight the random actions \n\nExploration Function\n+ eexplore areas whos badness is not yet established, eventually stop exploring \n+ $f(u, n) = u + \\frac{k}{n}$ $u$ is current utility estimate of a state and n is the number of times its been explored\n  + if its a good state we will visit again, if its a bad state we only visit while n is small\n+ REGULAR UPDATE $Q(s, a) = \\alpha(R(s, a, s') + \\gamma \\max_{a'} Q(s',a')$\n+ MODIFIED UPDATE $Q(s, a) = \\alpha(R(s, a, s') + \\gamma \\max_{a'} f(Q(s',a'), N(s',a'))$\n\nRegret\n+ you will eventually get to the optimal policy, but not sure how quickly\n+ regret measures how many mistakes you made overtime\n  + the difference between your expected rewards and optimal expected rewards\n  + minimizing regret tries to learn optimal as quickly as possible\n\n### Approximate Q-Learning \n+ when there are lots of possible states, we ecant visit every one \n+ generalize about states \n+ Q-Learning maintains a huge table of state action pairrs\n  + for large game states like chess, this is not possible \n\nGeneralizing Across States\n+ we cannot possibly learn about every single state\n+ learn through observation from training states\n+ generalize to new statees that wee have never seen before that are somehow SIMILAR\n+ flashback -- evaluation functions, take a partial completed state and take feeatures to make an estimate \n  + quantifying features and assigning weights to them\n\nLinear Value Function\n+ using a feature representation, we can write a q function or value function for any state using weights \n  + $V(s) = w_1f_1(s) + w_2f_2(s)+...+w_nf_n(s)$\n  + $Q(s,a) = w_1f_1(s) + w_2f_2(s,a)+...+w_nf_n(s,a)$\n+ advantage: experiencee is summed up in a few powerful numbers\n+ states may share the same features but be different, and we miss that \n+ learning algorithm setsthe weights automatically\n+ transition = (s, a, r, s')\n+ difference = $[r + \\gamma \\max_{a'}Q(s', a')] - Q(s, a)$ difference from what i though i would get from what it is seeming like i am getting now \n  + Exact Q learning,  take current q and add in alpha times difference \n  + approximate q learning $w_i = w_i + \\alpha [difference]f_i(s,a)$ update weights in proportion to the feature value\n  + intuitive interpretation, each of the weights is like a slider\n  + formal justification, online least squares\n\n\n\n\n\n\n## Module 9 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 10 - Probabilities and Language Models"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 12 “Quantifying Uncertainty” (Sections 12.1-12.7)\n",
        "chapter12_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_6 = \"\"\" Your summary here \"\"\"\n",
        "chapter12_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Jurafsky and Martin, Speech and Language Processing Chapter 3 “N-Gram Language Models”  (Sections 3.1-3.5,3.7)\n",
        "SLP_chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "SLP_chapter3_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module10_lecture_notes = \"\"\" \n",
        "\n",
        "### Review on Probabilities \n",
        "+ often faced with needing to reason about uncertainty\n",
        "+ using probabiloty to reason and predict\n",
        "+ unobserved variables (what we dont know will happen)\n",
        "+ observed variables are things that we know have happened\n",
        "+ agent knows something about known variables that help predict about unknowns\n",
        "\n",
        "+ probabilities are about possible worlds, quantify likelihood of occurrence\n",
        "+ possible worlds are sample space, they are mutually exclusive and exhaustive \n",
        "+ P(w) for each world w\n",
        "+ random variable is an apsect of the world about which we have uncertainty\n",
        "\n",
        "\n",
        "Axioms of Probability \n",
        "+ $0 \\leq P(w) \\leq 1$\n",
        "+ $ \\sum_{w \\in \\Omega} P(w) = 1$\n",
        "\n",
        "### Distributions\n",
        "+ for each unobserved RV there will be an associated set of probabilities (in a table)\n",
        "\n",
        "Joint Distrubutions\n",
        "+ specifying a real number outcome for each RV $X_1, X_2, ....X_n$\n",
        "+ you can make a joint table to represent this \n",
        "+ what is the size of this for n variables with domain sizes d?? $$d^n$$ (impractical!!)\n",
        "  + we can learn how variables interrelate \n",
        "\n",
        "Probabilistic Moxdel \n",
        "+ joit dist over a group of RVs \n",
        "+ each RV has a domain and a set of assignments is outcomes\n",
        "+ probabilistic models are all normalized \n",
        "+ an event is a set of outcomes \n",
        "+ hot AND sunny is different than hot OR sunny \n",
        "\n",
        "Marginal Distributions\n",
        "+ sub tables of a probability model that isolate or remove some variables that we dont care about \n",
        "\n",
        "Conditionals \n",
        "+ $P(a|b) = \\\\frac{P(a,b)}{P(b)}$\n",
        "\n",
        "### Probabilistic Inference and Rules\n",
        "+ weve got some desired probability, but we are given other sets of probbility \n",
        "+ distrributions change as we get more evidence \n",
        "+ 3 sets of things \n",
        "  + evidence variables : things that we know what happened \n",
        "  + query variables: reasoning about these \n",
        "  + hidden variables: we know they are happening but we dont reason about them \n",
        "  + we find $P(Q | e_1,...,e_k)$\n",
        "  + we are given joint table\n",
        "    + sum out H to get joint of Q and es ($P(Q, e_1, ..., e_k$)\n",
        "    + now we have to normalize to convert it back to a probability dist \n",
        "\n",
        "what if innstead given marginal or conditional?? \n",
        "\n",
        "+ product rule $P(x,y) = P(y)*P(x|y)$\n",
        "+ chain rule $P(x1, x2, x3) = P(x1) P(x2|x1) P(x3|x2, x1)$\n",
        "+ two ways to factor a joint probability\n",
        "  + Bayes Rule $P(x,y) = P(x)P(y|x) = P(y)P(x|y)$\n",
        "\n",
        "### Probabalistic Language Models\n",
        "+ autocomplete, machine translation, spell correct,.... \n",
        "  + all of these are probabilistic language models \n",
        "\n",
        "+ goal is compute the probabilisty of a sequence of words\n",
        "+ given a current sequence, what is the probability that this is the next one \n",
        "+ correspond each word to a RV\n",
        "+ we end up using chain rule and joint distrubutions\n",
        " \n",
        "\n",
        "How do we estimate theseprobabilities?? \n",
        "+ one way, maximum likelihood estimation\n",
        "  + count up occurrrences and divide\n",
        "  + problem: it is dependent on you seeing it in the corpus, need huge dataset\n",
        "+ make a simplifying assumption: markov\n",
        "  + probability of next state only depends on the current state (previous k words)\n",
        "  + so, how much history should we use???\n",
        "    + unigram (no history), bigram(one word history), trigram(2 words history), 4-gram(3 words)\n",
        "\n",
        "Markov History\n",
        "+ Eugene Onegin count up russian character probabilities in 1913\n",
        "+ 1928 n-gram used to approx english by Shannon\n",
        "+ 1956 Comsky defines finite markov models (incapable of modeling grammar) (linguists ignore him)\n",
        "+ 1980s IBM Jelenik uses n-gram modeling for speech recognition\n",
        "+ 1993 Jelinek again develops statistical machine translation \n",
        "  + $argmax_ep(e|f)=p(e)p(f|e)$\n",
        "+ jelenik left IBM for hopkins\n",
        "+ Brown and Mercer move to renaissance Tech (hedge fund) use this stat modeling\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 25 words long.\n",
        "module10_definitions = {\n",
        "\"term\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "vkT6NkaX8wBq"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2604
        },
        "cellView": "form",
        "outputId": "14aefe16-e04a-49c9-b250-6a46d8f6f7ea"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module10_sections = [\n",
        "  (\"AIMA Chapter 12.1 Acting under Uncertainty\", chapter12_1),\n",
        "  (\"AIMA Chapter 12.2 Basic Probability Notation\", chapter12_2),\n",
        "  (\"AIMA Chapter 12.3 Inference Using Full Joint Distributions\", chapter12_3),\n",
        "  (\"AIMA Chapter 12.4 Independence\", chapter12_4),\n",
        "  (\"AIMA Chapter 12.5 Bayes’ Rule and Its Use\", chapter12_5),\n",
        "  (\"AIMA Chapter 12.6 Naive Bayes Models\", chapter12_6),\n",
        "  (\"AIMA Chapter 12.7 The Wumpus World Revisited\", chapter12_7),\n",
        "  (\"SLP Chapter 3.1 N-Grams\", SLP_chapter3_1),\n",
        "  (\"SLP Chapter 3.2 Evaluating Language Models\", SLP_chapter3_2),\n",
        "  (\"SLP Chapter 3.3 Sampling sentences from a language model\", SLP_chapter3_3),\n",
        "  (\"SLP Chapter 3.4 Generalization and Zeros\", SLP_chapter3_4),\n",
        "  (\"SLP Chapter 3.5 Smoothing\", SLP_chapter3_5),\n",
        "  (\"SLP Chapter 3.7 Huge Language Models and Stupid Backoff\", SLP_chapter3_7),\n",
        "  (\"Module 10 Lecture Notes\", module10_lecture_notes),\n",
        "]\n",
        "\n",
        "module10_markdown = format_module(10, \"Probabilies and Language Models\", module10_sections, module10_definitions)\n",
        "display(Markdown(module10_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \n\n### Review on Probabilities \n+ often faced with needing to reason about uncertainty\n+ using probabiloty to reason and predict\n+ unobserved variables (what we dont know will happen)\n+ observed variables are things that we know have happened\n+ agent knows something about known variables that help predict about unknowns\n\n+ probabilities are about possible worlds, quantify likelihood of occurrence\n+ possible worlds are sample space, they are mutually exclusive and exhaustive \n+ P(w) for each world w\n+ random variable is an apsect of the world about which we have uncertainty\n\n\nAxioms of Probability \n+ $0 \\leq P(w) \\leq 1$\n+ $ \\sum_{w \\in \\Omega} P(w) = 1$\n\n### Distributions\n+ for each unobserved RV there will be an associated set of probabilities (in a table)\n\nJoint Distrubutions\n+ specifying a real number outcome for each RV $X_1, X_2, ....X_n$\n+ you can make a joint table to represent this \n+ what is the size of this for n variables with domain sizes d?? $$d^n$$ (impractical!!)\n  + we can learn how variables interrelate \n\nProbabilistic Moxdel \n+ joit dist over a group of RVs \n+ each RV has a domain and a set of assignments is outcomes\n+ probabilistic models are all normalized \n+ an event is a set of outcomes \n+ hot AND sunny is different than hot OR sunny \n\nMarginal Distributions\n+ sub tables of a probability model that isolate or remove some variables that we dont care about \n\nConditionals \n+ $P(a|b) = \\frac{P(a,b)}{P(b)}$\n\n### Probabilistic Inference and Rules\n+ weve got some desired probability, but we are given other sets of probbility \n+ distrributions change as we get more evidence \n+ 3 sets of things \n  + evidence variables : things that we know what happened \n  + query variables: reasoning about these \n  + hidden variables: we know they are happening but we dont reason about them \n  + we find $P(Q | e_1,...,e_k)$\n  + we are given joint table\n    + sum out H to get joint of Q and es ($P(Q, e_1, ..., e_k$)\n    + now we have to normalize to convert it back to a probability dist \n\nwhat if innstead given marginal or conditional?? \n\n+ product rule $P(x,y) = P(y)*P(x|y)$\n+ chain rule $P(x1, x2, x3) = P(x1) P(x2|x1) P(x3|x2, x1)$\n+ two ways to factor a joint probability\n  + Bayes Rule $P(x,y) = P(x)P(y|x) = P(y)P(x|y)$\n\n### Probabalistic Language Models\n+ autocomplete, machine translation, spell correct,.... \n  + all of these are probabilistic language models \n\n+ goal is compute the probabilisty of a sequence of words\n+ given a current sequence, what is the probability that this is the next one \n+ correspond each word to a RV\n+ we end up using chain rule and joint distrubutions\n \n\nHow do we estimate theseprobabilities?? \n+ one way, maximum likelihood estimation\n  + count up occurrrences and divide\n  + problem: it is dependent on you seeing it in the corpus, need huge dataset\n+ make a simplifying assumption: markov\n  + probability of next state only depends on the current state (previous k words)\n  + so, how much history should we use???\n    + unigram (no history), bigram(one word history), trigram(2 words history), 4-gram(3 words)\n\nMarkov History\n+ Eugene Onegin count up russian character probabilities in 1913\n+ 1928 n-gram used to approx english by Shannon\n+ 1956 Comsky defines finite markov models (incapable of modeling grammar) (linguists ignore him)\n+ 1980s IBM Jelenik uses n-gram modeling for speech recognition\n+ 1993 Jelinek again develops statistical machine translation \n  + $argmax_ep(e|f)=p(e)p(f|e)$\n+ jelenik left IBM for hopkins\n+ Brown and Mercer move to renaissance Tech (hedge fund) use this stat modeling\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 11 - Probabilistic Reasoning and Bayes’ Nets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "3ae03871-6e47-41b3-a41c-acaf3353b294"
      },
      "source": [
        "# Russell and Norvig, Russell and Norvig, AIMA Chapter 13 “Probabilistic Reasoning” (13.1, 13.2, 13.3)\n",
        "chapter13_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter13_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module11_lecture_notes = \"\"\" \n",
        "\n",
        "### Probabalstic Models and Bayes Nets\n",
        "+ Probability models inform us about how the actions of our world impact different occurences. Bayes Nets are more attractive than full\n",
        "+ joint probability distributions because they compactly show us what events impact others within smaller tables.\n",
        "+ Bayes Nets are able to achieve this compactness by making assumptions on independence of variables.\n",
        "+ Independence - we know something about variable A but this knowledge has no impact on the occurence of variable B.\n",
        "\n",
        "### Review of Independce \n",
        "+ Conditional Independence: $P(x,y |z) = P(x|z) * P(y|z)$ which is expressed as $X \\indep Y|Z$\n",
        "+ Alarm \\indep Fire|Smoke$ - In english this means that Alarm and Fire are independent of one another if we see Smoke\n",
        "+ Conditional Indpendence tells us a lot about the world and is useful in building models\n",
        "+ Equivilant definition of Conditional Independence: $P(x| z,y) = P(x|z)$\n",
        "+ $P(z|x, y) = P(x,y,z) / P(x,y)$\n",
        "\n",
        "\n",
        "### Bayes Net Properties\n",
        "+ $P(x_i | x_1 ... x_{i-1}) = P(x_i| parents(X_i)) $\n",
        "+ This means that the probability of variable x_i is conditional not on all of its preceding variables but only its direct parents\n",
        "+ D-seperation: We build our bayes net off of some known conditional independence, often tho other conditional independence arises in net\n",
        "+ How do we read it off? With D- Seperation - understanding independence with triples.\n",
        "+ D-Seperation:\n",
        "   + Causal Chain\n",
        "       + X => Y => Z\n",
        "       + Low Pressure => Rain => Traffic\n",
        "       + $ P(X,Y,Z) = P(X)P(Y|X)P(z|y) $\n",
        "       + X is not independent of Z\n",
        "   + Common Cause\n",
        "       + Y => X, Y=> Z\n",
        "       + Project Due => Forums Busy, Project Due => Office Hours Full\n",
        "       + $ P(x,y,z) = P(y)P(x|y)P(z|y) $\n",
        "       + X is not independent of Z\n",
        "       + However, Z is independent given X and Y\n",
        "   + Common Effect\n",
        "       + x => Z, Y => Z\n",
        "       + raining => traffic, ballgame => traffic\n",
        "       + X and Y are independent\n",
        "       + X and Y are not independent given Z    \n",
        "\n",
        "#### Reachability and Path\n",
        "+ Suppose we have BN, Q: Are two variables in BN indep?\n",
        "+ Solution: Analyze the graph\n",
        "+ We can break down complex graph into instances of the three examples above\n",
        "+ Question: Are X and Y conditionally indep given evidence variables {Z}?\n",
        "   + Yes if X and Y are d-seperated by Z, meaning that all undirected paths from X to Y are non-active\n",
        "   + Active Triple => Non-Independence\n",
        "   + Inactive Tripe => Independence\n",
        "   + A Path is 'active' if all triples along the path are active\n",
        "\n",
        "### D-Seperation\n",
        "+ What is we want to determine if two variables are conditionally independent\n",
        "+ $ X_i \\indep X_j | \\{ X_{k_1}, ..., X_{k_n} \\} $\n",
        "+ Look at all undirected paths between I and J, look at all triples along each path\n",
        "+ If one or more paths are actives then independence is not guarenteed\n",
        "+ If all paths inactive then independence is guarenteed\n",
        "+ This means that you can have an independence between X and Y, even if there exists an active triple as long as this active triple is in an inactive path (at least one other triple along this path is inactive).\n",
        "\n",
        "### Inferences\n",
        "+ Inference: calculating some useful quantity from a joint probability distribution\n",
        "+ Inference by Enumeration\n",
        "    + We break all variables in BN into three categories\n",
        "    + Evidence Variables: ones we know the outcomes to $e_1 ... e_n $\n",
        "    + Query Variables: what we care about reasoning about\n",
        "    + Hidden Variables: All other variables (we usually care less about this)\n",
        "    + We want $ P(Q | e_1 ... e_k) $. In order to get we ...\n",
        "         + Step 1: select entries consistent with evidence\n",
        "         + Step 2: Sum out hidden variables to get joint of query and evidence\n",
        "         + Step 3: Normalize $ * 1/Z $ so that we have a probability distribution\n",
        "    + E.X. $ P(B | j+, m+)$ => probability there was a break in given that you have calls from jon and mary\n",
        "    + This can be expressed mathematically as: $ \\sum_{e,a} P(B,e,a,+j,+m)$ where e and a are non-observed variables.\n",
        "    + $= \\sum_{e,a} P(B) P(e) P(a|B,e)P(+j|a)P(+m|a)$    \n",
        "    + where we sum over all possible combinations of values of hidden variables e and a \n",
        "+ This process can become very slow with a large number of unobserved variables. \n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "![]\n",
        "\n",
        "module11_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "/bin/bash: []: command not found\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1690
        },
        "cellView": "form",
        "outputId": "eeccbe31-a3e2-46b3-deb4-56886cfa143b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module11_sections = [\n",
        "  (\"AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\", chapter13_1),\n",
        "  (\"AIMA Chapter 13.2 The Semantics of Bayesian Networks\", chapter13_2),\n",
        "  (\"AIMA 13.3 Exact Inference in Bayesian Networks\", chapter13_3),\n",
        "  (\"Module 11 Lecture Notes\", module11_lecture_notes),\n",
        "]\n",
        "\n",
        "module11_markdown = format_module(11, \"Probabilistic Reasoning and Bayes’ Nets\", \n",
        "                         module11_sections, \n",
        "                         module11_definitions)\n",
        "display(Markdown(module11_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \n\n### Probabalstic Models and Bayes Nets\n+ Probability models inform us about how the actions of our world impact different occurences. Bayes Nets are more attractive than full\n+ joint probability distributions because they compactly show us what events impact others within smaller tables.\n+ Bayes Nets are able to achieve this compactness by making assumptions on independence of variables.\n+ Independence - we know something about variable A but this knowledge has no impact on the occurence of variable B.\n\n### Review of Independce \n+ Conditional Independence: $P(x,y |z) = P(x|z) * P(y|z)$ which is expressed as $X \\indep Y|Z$\n+ Alarm \\indep Fire|Smoke$ - In english this means that Alarm and Fire are independent of one another if we see Smoke\n+ Conditional Indpendence tells us a lot about the world and is useful in building models\n+ Equivilant definition of Conditional Independence: $P(x| z,y) = P(x|z)$\n+ $P(z|x, y) = P(x,y,z) / P(x,y)$\n\n\n### Bayes Net Properties\n+ $P(x_i | x_1 ... x_{i-1}) = P(x_i| parents(X_i)) $\n+ This means that the probability of variable x_i is conditional not on all of its preceding variables but only its direct parents\n+ D-seperation: We build our bayes net off of some known conditional independence, often tho other conditional independence arises in net\n+ How do we read it off? With D- Seperation - understanding independence with triples.\n+ D-Seperation:\n   + Causal Chain\n       + X => Y => Z\n       + Low Pressure => Rain => Traffic\n       + $ P(X,Y,Z) = P(X)P(Y|X)P(z|y) $\n       + X is not independent of Z\n   + Common Cause\n       + Y => X, Y=> Z\n       + Project Due => Forums Busy, Project Due => Office Hours Full\n       + $ P(x,y,z) = P(y)P(x|y)P(z|y) $\n       + X is not independent of Z\n       + However, Z is independent given X and Y\n   + Common Effect\n       + x => Z, Y => Z\n       + raining => traffic, ballgame => traffic\n       + X and Y are independent\n       + X and Y are not independent given Z    \n\n#### Reachability and Path\n+ Suppose we have BN, Q: Are two variables in BN indep?\n+ Solution: Analyze the graph\n+ We can break down complex graph into instances of the three examples above\n+ Question: Are X and Y conditionally indep given evidence variables {Z}?\n   + Yes if X and Y are d-seperated by Z, meaning that all undirected paths from X to Y are non-active\n   + Active Triple => Non-Independence\n   + Inactive Tripe => Independence\n   + A Path is 'active' if all triples along the path are active\n\n### D-Seperation\n+ What is we want to determine if two variables are conditionally independent\n+ $ X_i \\indep X_j | \\{ X_{k_1}, ..., X_{k_n} \\} $\n+ Look at all undirected paths between I and J, look at all triples along each path\n+ If one or more paths are actives then independence is not guarenteed\n+ If all paths inactive then independence is guarenteed\n+ This means that you can have an independence between X and Y, even if there exists an active triple as long as this active triple is in an inactive path (at least one other triple along this path is inactive).\n\n### Inferences\n+ Inference: calculating some useful quantity from a joint probability distribution\n+ Inference by Enumeration\n    + We break all variables in BN into three categories\n    + Evidence Variables: ones we know the outcomes to $e_1 ... e_n $\n    + Query Variables: what we care about reasoning about\n    + Hidden Variables: All other variables (we usually care less about this)\n    + We want $ P(Q | e_1 ... e_k) $. In order to get we ...\n         + Step 1: select entries consistent with evidence\n         + Step 2: Sum out hidden variables to get joint of query and evidence\n         + Step 3: Normalize $ * 1/Z $ so that we have a probability distribution\n    + E.X. $ P(B | j+, m+)$ => probability there was a break in given that you have calls from jon and mary\n    + This can be expressed mathematically as: $ \\sum_{e,a} P(B,e,a,+j,+m)$ where e and a are non-observed variables.\n    + $= \\sum_{e,a} P(B) P(e) P(a|B,e)P(+j|a)P(+m|a)$    \n    + where we sum over all possible combinations of values of hidden variables e and a \n+ This process can become very slow with a large number of unobserved variables. \n\n\n\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 12 - Naive Bayes and Perceptrons"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 19 “Learning from Examples” (Sections 19.1-19.6)\n",
        "\n",
        "chapter19_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter19_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Speech and Language Processing Chapter 4 “Naive Bayes and Sentiment Classification”\n",
        "slp_chapter4_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_7 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_9 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter4_10 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module12_lecture_notes = \"\"\" \n",
        "\n",
        "### Overview\n",
        "+ Naive Bayes and Perceptrons use labelled training data to learn a classification decision.\n",
        "+ Learning involves learning the probability of a feature given another feature.\n",
        "+ Perceptrons are different from Naive Bayes in that they don't compute probability of feature - instead they compute a distribution\n",
        "+ of weights for classification. With each misclassification perceptrons update their distribution.\n",
        "+ Perceptrons form the building blocks of neural networks\n",
        "\n",
        "### Classification Task\n",
        "+ Up until now these probabilities for BN's have been given to us - now we have to compute them. We typically do this with ML\n",
        "+ Regression - we want ML to determine some numeric value for us based on data\n",
        "+ Classification - there are a finite number of possible results we want ML to tell us which result current instance is\n",
        "+ E.X. spam classification based on text of email. We create vector of words and associated likelhood of spam, classify based on it\n",
        "+ Additional E.X. Digit classification based on handwritten examples\n",
        "+ Typically need large quantity of labelled data and features used to make classification\n",
        "+ Model Based Classification: build a model (similar to a BN model)\n",
        "  + Instantiate any observed features\n",
        "  + Query for the distribution of the label conditioned on the features\n",
        "  + Spam/Ham would be the query where the variables that we know are the ones in email\n",
        "  + How do we structure BN?\n",
        "  + How do we learn probabilites of all the variables?\n",
        "\n",
        "\n",
        "### Naive Bayes\n",
        "+ Start by assuming that all features are independent of one another and dependent on the label\n",
        "+ We accumulate giant probability table of $ P(F_2 | SPAM)$  $ P(F_1 | SPAM) $ $ P(F_1 | NON-SPAM) $\n",
        "+ Each new input to the model will have binary values for the above expressions (either in the email or not, either coordinate is colored or not)\n",
        "+ Model: $P(Y|F_{0,0} ... F_{n,n}) = P(Y) \\Pi P(F_i | Y) $\n",
        "+ We only have to specify how each feature depends on the class, therefore LINEAR in the number of variables.\n",
        "+ Inference\n",
        "  + We have an input features, we get conditional probability of each label based on features, sum and normalize by dividing by features\n",
        "+ In order to compute the table with examples $ P(F_2 | LABEL)$ we come up with probability estimates for each label. E.X. think of coordinate in grid and probability of it being digit 1 through 9\n",
        "\n",
        "\n",
        "### Basic Concepts in ML\n",
        "+ Training Data - we give model labeled data so that it can train itself\n",
        "+ Test Data - We see how well model did after getting trained\n",
        "+ Held-Out Set - useful for hyperparamets of model (almost like a practice test before test data)\n",
        "+ Overfitting - we over model the data, for idiocynicaries that appear in the training data but not in the real world\n",
        "+ E.X. think about a three with a small smudge on the end, if we overfit we might see this smudge alone and determine that this value cannot be 3\n",
        "+ Most of the time overfitting comes at the result of assigning 0 probability to unseen events in training data\n",
        "+ In order to fix this we smooth our estimates. How do we do this?\n",
        "  + Elicitation - ask a human\n",
        "  + Empirically - use training data, number of times seen divided by number of samples \n",
        "+ What about unseen events?\n",
        "  + Lets pretend that we saw each event once more than we actually did and then recompute empirically as we had (Laplace Smoothing)\n",
        "  + We can also Laplace smooth with 2,3, ... 100 etc. depending on the circumstance\n",
        "  + Can also perform Linear Interpolation (Laplace performs poorly for $P(X|Y)$ when $|X|$ or $|Y|$ are very large)\n",
        "    + $P_{LIN}(x|y) = \\gamma P'(x|y) + (1.0 - \\alpha)P'(x)$ where P(x) is conditional probability of label and alpha is a hyperparameter\n",
        "+ Generally speaking we \n",
        "  + Learn parameters from training data\n",
        "  + Tune hyperparameters on our held-out data (k value for laplace, or alpha for linear interpolation)\n",
        "+ We tend to compare the accuracy of our models to some 'baseline' which is the current success rate in classification of the given task  \n",
        "\n",
        "\n",
        "### Perceptrons\n",
        "+ Linear Classifers (Binary Perceptrons)\n",
        "   + Input is a vector of feature values <#free: 2, your_name: 0, misspelled: 2 ...>\n",
        "   + We take the dot product of this vector with our vector which has weights corresponding to each vector <#free:4, your_name:-1, misspelled:1 ... >\n",
        "   + If dot product is positive then output +1, else we output -1\n",
        "   + It is our job to learn this weight vector\n",
        "      + We begin with weight vector with all 0s\n",
        "      + If we misclassify, then we update weight vector $w = w + (y' * f)$, where $y'$ is correct label and f is curr weight in example\n",
        "\n",
        "+ MultiClass Classifiers\n",
        "   + We have a weight vector $w_y$ for each classification\n",
        "   + We score each classification by $w_y * f(x)$\n",
        "   + We predict by choosing the classification which yeilds the max score\n",
        "   + If we misclassify... \n",
        "       + lower score of wrong $w_y = w_y - f(x) $\n",
        "       + raise score of right $w_{y'} = w_{y'} + f(x) $ \n",
        "\n",
        "+ Properties of Perceptrons\n",
        "   + Seperability: true if some parameters get training set perfectly correct (basically says you can perfectly classify into unique buckets) occurs in some cases\n",
        "   + Convergence: if training is seperable, then perceptron will eventually converge\n",
        "   + mistake bound: $ mistake < k / /sigma ^2 $ if not seperable then we can bound by the expression prior\n",
        "\n",
        "+ Problems with Perceptrons\n",
        "   + Noise: if data isn't seperable then weights might thrash back and forth, it helps to average weights of perceptron over time to prevent this\n",
        "   + Overtraining can occur\n",
        "   + Mediocre Generalizaiton - create seperating solution (works for testing data), but a better seperating solution exists\n",
        "\n",
        "### Improvements to Perceptrons and SVM\n",
        "+ Idea: adjust weight update to mitigate the negative effects, weight variable is tau $\\tau$ (MIRA)\n",
        "+ $\\tau = ((w_y' - w_{y*}')*f + 1) / (2f * f) $\n",
        "+ $ w_y = w_y' - \\tau * f(x) $\n",
        "+ Cause perceptron to converge faster, evade the noise\n",
        "\n",
        "+ Support Vector Machines - good for dealing with medoicre generalization. Allows you to obtain best possible seperating solution.\n",
        "+ Non-Linear Separators - if unable to seperate data linearly can seperate in higher dimensions, i.e. squaring input data and then seperating\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module12_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3004
        },
        "cellView": "form",
        "outputId": "c99cbef8-eeb6-49ac-8b38-cb14d6558f92"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module12_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter19_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter19_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter19_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter19_4),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter19_5),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter19_6),\n",
        "  (\"SLP Chapter 4.1 Naive Bayes Classifiers\", slp_chapter4_1),\n",
        "  (\"SLP Chapter 4.2 Training the Naive Bayes Classifier\", slp_chapter4_2),\n",
        "  (\"SLP Chapter 4.3 Worked Example\", slp_chapter4_3),\n",
        "  (\"SLP Chapter 4.4 Optimizing for Sentiment Analysis\", slp_chapter4_4),\n",
        "  (\"SLP Chapter 4.5 Naive Bayes for other text classification tasks\", slp_chapter4_5),\n",
        "  (\"SLP Chapter 4.6 Naive Bayes as a Language Model\", slp_chapter4_6),\n",
        "  (\"SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\", slp_chapter4_7),\n",
        "  (\"SLP Chapter 4.8 Test sets and Cross-validation\", slp_chapter4_8),\n",
        "  (\"SLP Chapter 4.9 Statistical Significance Testing\", slp_chapter4_9),\n",
        "  (\"SLP Chapter 4.10 Avoiding Harms in Classification\", slp_chapter4_10),\n",
        "  (\"Module 12 Lecture Notes\", module12_lecture_notes),\n",
        "]\n",
        "\n",
        "module12_markdown = format_module(12, \"Naive Bayes and Perceptrons\", \n",
        "                         module12_sections, \n",
        "                         module12_definitions)\n",
        "display(Markdown(module12_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n\n### Overview\n+ Naive Bayes and Perceptrons use labelled training data to learn a classification decision.\n+ Learning involves learning the probability of a feature given another feature.\n+ Perceptrons are different from Naive Bayes in that they don't compute probability of feature - instead they compute a distribution\n+ of weights for classification. With each misclassification perceptrons update their distribution.\n+ Perceptrons form the building blocks of neural networks\n\n### Classification Task\n+ Up until now these probabilities for BN's have been given to us - now we have to compute them. We typically do this with ML\n+ Regression - we want ML to determine some numeric value for us based on data\n+ Classification - there are a finite number of possible results we want ML to tell us which result current instance is\n+ E.X. spam classification based on text of email. We create vector of words and associated likelhood of spam, classify based on it\n+ Additional E.X. Digit classification based on handwritten examples\n+ Typically need large quantity of labelled data and features used to make classification\n+ Model Based Classification: build a model (similar to a BN model)\n  + Instantiate any observed features\n  + Query for the distribution of the label conditioned on the features\n  + Spam/Ham would be the query where the variables that we know are the ones in email\n  + How do we structure BN?\n  + How do we learn probabilites of all the variables?\n\n\n### Naive Bayes\n+ Start by assuming that all features are independent of one another and dependent on the label\n+ We accumulate giant probability table of $ P(F_2 | SPAM)$  $ P(F_1 | SPAM) $ $ P(F_1 | NON-SPAM) $\n+ Each new input to the model will have binary values for the above expressions (either in the email or not, either coordinate is colored or not)\n+ Model: $P(Y|F_{0,0} ... F_{n,n}) = P(Y) \\Pi P(F_i | Y) $\n+ We only have to specify how each feature depends on the class, therefore LINEAR in the number of variables.\n+ Inference\n  + We have an input features, we get conditional probability of each label based on features, sum and normalize by dividing by features\n+ In order to compute the table with examples $ P(F_2 | LABEL)$ we come up with probability estimates for each label. E.X. think of coordinate in grid and probability of it being digit 1 through 9\n\n\n### Basic Concepts in ML\n+ Training Data - we give model labeled data so that it can train itself\n+ Test Data - We see how well model did after getting trained\n+ Held-Out Set - useful for hyperparamets of model (almost like a practice test before test data)\n+ Overfitting - we over model the data, for idiocynicaries that appear in the training data but not in the real world\n+ E.X. think about a three with a small smudge on the end, if we overfit we might see this smudge alone and determine that this value cannot be 3\n+ Most of the time overfitting comes at the result of assigning 0 probability to unseen events in training data\n+ In order to fix this we smooth our estimates. How do we do this?\n  + Elicitation - ask a human\n  + Empirically - use training data, number of times seen divided by number of samples \n+ What about unseen events?\n  + Lets pretend that we saw each event once more than we actually did and then recompute empirically as we had (Laplace Smoothing)\n  + We can also Laplace smooth with 2,3, ... 100 etc. depending on the circumstance\n  + Can also perform Linear Interpolation (Laplace performs poorly for $P(X|Y)$ when $|X|$ or $|Y|$ are very large)\n    + $P_{LIN}(x|y) = \\gamma P'(x|y) + (1.0 - \u0007lpha)P'(x)$ where P(x) is conditional probability of label and alpha is a hyperparameter\n+ Generally speaking we \n  + Learn parameters from training data\n  + Tune hyperparameters on our held-out data (k value for laplace, or alpha for linear interpolation)\n+ We tend to compare the accuracy of our models to some 'baseline' which is the current success rate in classification of the given task  \n\n\n### Perceptrons\n+ Linear Classifers (Binary Perceptrons)\n   + Input is a vector of feature values <#free: 2, your_name: 0, misspelled: 2 ...>\n   + We take the dot product of this vector with our vector which has weights corresponding to each vector <#free:4, your_name:-1, misspelled:1 ... >\n   + If dot product is positive then output +1, else we output -1\n   + It is our job to learn this weight vector\n      + We begin with weight vector with all 0s\n      + If we misclassify, then we update weight vector $w = w + (y' * f)$, where $y'$ is correct label and f is curr weight in example\n\n+ MultiClass Classifiers\n   + We have a weight vector $w_y$ for each classification\n   + We score each classification by $w_y * f(x)$\n   + We predict by choosing the classification which yeilds the max score\n   + If we misclassify... \n       + lower score of wrong $w_y = w_y - f(x) $\n       + raise score of right $w_{y'} = w_{y'} + f(x) $ \n\n+ Properties of Perceptrons\n   + Seperability: true if some parameters get training set perfectly correct (basically says you can perfectly classify into unique buckets) occurs in some cases\n   + Convergence: if training is seperable, then perceptron will eventually converge\n   + mistake bound: $ mistake < k / /sigma ^2 $ if not seperable then we can bound by the expression prior\n\n+ Problems with Perceptrons\n   + Noise: if data isn't seperable then weights might thrash back and forth, it helps to average weights of perceptron over time to prevent this\n   + Overtraining can occur\n   + Mediocre Generalizaiton - create seperating solution (works for testing data), but a better seperating solution exists\n\n### Improvements to Perceptrons and SVM\n+ Idea: adjust weight update to mitigate the negative effects, weight variable is tau $\tau$ (MIRA)\n+ $\tau = ((w_y' - w_{y*}')*f + 1) / (2f * f) $\n+ $ w_y = w_y' - \tau * f(x) $\n+ Cause perceptron to converge faster, evade the noise\n\n+ Support Vector Machines - good for dealing with medoicre generalization. Allows you to obtain best possible seperating solution.\n+ Non-Linear Separators - if unable to seperate data linearly can seperate in higher dimensions, i.e. squaring input data and then seperating\n \n\n## Module 12 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "# Module 13 - Neural Networks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Jurafsky and Martin, Speech and Language Processing Chapter 5 “Logistic Regression” (5.1-5.6)\n",
        "\n",
        "slp_chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter5_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 7 “Neural Networks and Neural Language Models”\n",
        "\n",
        "slp_chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_6 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter7_7 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module13_lecture_notes = \"\"\" \n",
        "\n",
        "### Logistic Regression\n",
        "\n",
        "Classifier Components\n",
        "+ train a corpus of M observations in input output pairs $(x^{(i)}, y^{(i)})$\n",
        "+ we need to transform this into feature representation\n",
        "+ wee need to take a feature represenetation as an input to a function with classification as the output via a probability distribution\n",
        "+ we need of method of \"how good\" the curreent classification function is, calleed objectivee fun (or loss fun)\n",
        "+ optimization routine, how to adjust to minimize loss\n",
        "\n",
        "Sentiment Classifier\n",
        "+ take text -> features -> output. label + or - \n",
        "+ logistic regression solves this by learning from a training seet, witgh weights and a bias term \n",
        "+ $z = \\sum_i w_ix_i + b$ (dot product of z and w + b)\n",
        "+ z is unbounded\n",
        "+ MAIN CHANGE FROM PRECEPTRONS : Z SQUISHED TO BETWEEN 0 AND 1\n",
        "+ $ y = \\\\frac{1}{1 + e^{-z}}$ sigmoid function, where $z = w \\cdot x + b$\n",
        "+ decision boundary : naturally falls at 0.5\n",
        "+ how do we extract features from raw text input??\n",
        "  + in NLP, define the amount of features in. thee text \n",
        "  + x1 = number of positive lexicon words in the review\n",
        "  + x2 = count of negativee lexicon words\n",
        "  + x3 = does no appear? \n",
        "  + x4 = number of. first and second person pronouns\n",
        "  + x5 = does ! appear\n",
        "  + x6 log of the word count \n",
        "  + weights?? can be given, can be learned\n",
        "\n",
        "Learning in Logistic Regression\n",
        "+ learn the weights and the bias term with loss function and optimization routine\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "### Loss Functions\n",
        "Mean Squared error: \n",
        "$L_{MSE}(\\hat{y}, y) = \\\\frac{1}{2} (\\hat{y}-y)^2$\n",
        "\n",
        "Cross entropy loss: find a type of maximum likelihood estimator, choose params w, b that maximize the probability \\\n",
        "that we get the true label\n",
        "\n",
        "+ maximie the probability of the correct label $p(y|x) = \\hat{y}^y(1-\\hat{y})^{1-y}$\n",
        "+ why is this the function, y = 1 or y = 0 os the exponent tells us which part of the equation matters\n",
        "+ if y is 1, we try to maximize y hat, if y is 0 wee try to maximize 1 - y hat\n",
        "+ take the log of both sides $log(p(y|x)) = log(\\hat{y}^y(1-\\hat{y})^{1-y}) = y log(\\hat{y}) + (1-y) log(1-\\hat{y})$ where $\\hat{y} = \\sigma(w \\cdot x + b)$\n",
        "+ finally $L_{CE} = - [y log(\\sigma(w \\cdot x + b)) + (1-y) log(1-\\sigma(w \\cdot x + b))$]$ (flip sign to maximize a negative, minimize loss )\n",
        "+ correct: lowerr, incorrect: higher\n",
        "+ Total loss is sum of all of the losses (since we work in log space )\n",
        "\n",
        "Finding good parameters - Gradient Descent:\n",
        "+ argmin average loss\n",
        "+ gradient descent is to figure out for each of our weights, what direction should we  movee in (inc or dec) to lower loss\n",
        "+ find the most extreme downward slope\n",
        "+ convex optimization (loss is convex (global minimum))\n",
        "  + non convex is a much harder problem to solve \n",
        "  + define a step size that is the same as the learning rate $\\eta$ \"eta\"\n",
        "  + to get slope, derivativee if the loss function\n",
        "  + $\\\\frac{\\delta L_{CE}(w,b)}{\\delta w_j} = [\\sigma(w \\cdot x + b) - y]x_j\n",
        "  + difference between the true label and our eextimate times thee corresponding value of that feature\n",
        "\n",
        "### Stochastic Gradient Descent \n",
        "+ we have N weights, for each of the weieghts in the weight vector, how much should we updatee it and in what direction??\n",
        "+ what are the derivatives if the loss with respect to each weight compared to the true value\n",
        "+ $\\delta w_iL(f(x, \\\\theta), y)$ in a vector of length n COPY THESE EQS FROM THE SLIDEES\n",
        "+ $\\\\theta_{t+1} = \\\\theta_t\n",
        "\n",
        "The Gradient\n",
        "+ tot update $\\\\theta$\n",
        "+  $L_{CE} = - [y log(\\hat{y}) + (1-y) log(1-\\hat{y})$]$\n",
        "+ derivative if this for one observation x and a single weight is :\n",
        "  + $ \\\\frac{\\delta L_{CE}(\\hat{y),y)}{\\deltaw_j} = [\\hat{y-y}]x_j$\n",
        "  + the derivative of the loss with respect to a single input and a single weight is the difference of the prediction and the actual value times the value xj\n",
        "+ COPY QS FROM SLIDES\n",
        "+ the gradient is take what we had before and add it up \n",
        "+ $ \\\\frac{\\delta L_{CE}(\\hat{y),y)}{\\deltaw_j} = [\\hat{y-y}]x_j$\n",
        "\n",
        "The Stochastic Gradient Descent Algorithm\n",
        "+ initialize all weights to be zeros \n",
        "+ iterate some numsbe of times \n",
        "+ grab some item in random order xi, yi\n",
        "+ use classifier to. say what is the estimate y. hat\n",
        "+ compute loss by comparing y hat to y\n",
        "+ compute the gradienr and store it in the vector \n",
        "+ update the weights by subtracting out learning rate times gradient vector \n",
        "\n",
        "Example\n",
        "+ sentiment classification, + or -\n",
        "+ 2 features, 1 is count of num positive features, 2 is count of number of. negative words \n",
        "+ three weights, the two counts and the bias\n",
        "+ set all weights to zero intially\n",
        "+ select xi, yi (you have an input vector p = 3, n = 2, b = 1) yi = 1 (positive)\n",
        "+ $\\\\theta_1 = [0, 0, 0]$\n",
        "+ learning rate $\\eta = 0.1$\n",
        "+ $\\\\theta_2 = \\\\theta_1 - \\eta \\\\nabla_\\\\theta L(f(x^1, \\\\theta_1), y^1)$\n",
        "\n",
        "\n",
        "Batching \n",
        "+ we usually batch a bunch of items together for batch training \n",
        "+ usually, we do mini batch training group items together, update for that batch, and continue\n",
        "+ we usually pick this based on GPU memory constraints \n",
        "\n",
        "Regularization\n",
        "+ overfitting solution, adding penalty into the loss function that stop weights from getting too large \n",
        "+ we do this using some potential terms \n",
        "  + L1 is a linear function on the weights similar to manhattan distance \n",
        "  + L2 is a quadratic function uses the square of the l2 norm (euclidian distance) usually easier because of continuous derviative\n",
        "+ main goal is keep weight values small\n",
        "\n",
        "Multinomial Logisitc Regression\n",
        "+ what if we care about a problem with more than just binary classification\n",
        "+ ie positive, negative, neutral sentiment\n",
        "+ softmax takes an input vector and outputs a vector of values normalized into probabilities\n",
        "+ this can be interpreted as a probability distrubution on multiple classes \n",
        "\n",
        "### Neural Networks \n",
        "+ biological inspiration preceptron in the 1950s\n",
        "  + take inputs ansd assign them weights and if we sum the product of inputs and weights with an activation function we make a decision\n",
        "  + just like the human neuron (many inputs, one neuron, one output)\n",
        "  + in our brain, we have a lot of interconnected neurons\n",
        "+ everything is interconnected \n",
        "+ output of one neuron can be an input to other neurons \n",
        "+ feed-forward neural network architecture\n",
        "  + incoming arcts are inputs, ourgoing arcs are transmissions\n",
        "  + input layer, hidden layers (we do not directly observe), and an output layer\n",
        "  + training is more complicated, there are several layers that we do not see\n",
        "  + no need for feature engineering, the whole input raw is filtered thru using hidden layers\n",
        "  + tradeoff: time spent picking the right architechture/model \n",
        "\n",
        "\n",
        "Sigmoid Neurons\n",
        "+ a small change in one of the weight values represents a small change in the resulting output\n",
        "+ z = xw+b, $\\\\sigma = e^{-z}$\n",
        "\n",
        "Activation Functions \n",
        "+ sigmoid is one of these,  but there are a lof of different ones that we can use \n",
        "+ three most used\n",
        "  + sigmoid (s curve)\n",
        "  + tangent (s curve)\n",
        "  + reLU (0 and then linear)\n",
        "\n",
        "Feed-Forward Neural Network\n",
        "+ simplest kind, fully connected (each item is connected to every other item in the next layer)\n",
        "+ multilayer, no cycles\n",
        "+ layer 0 is input layer, final layer is output layer, anything in between is hidden layer\n",
        "+ three steps per layer \n",
        "  + w * x\n",
        "  + add in bias b \n",
        "  + apply the activation function to it \n",
        "  + difference from logistic regression (change the dot product to a matrix multiply (singe every element in the layer has a weight vector))\n",
        "\n",
        "  + each nerual unit is a logistic regression classifier\n",
        "+ if this is the final layer, stick itinto a softmax function that gives us a distrubution over \n",
        "\n",
        "Training Neural Nets \n",
        "+ how do we attribute errors? (in logistic regression it was a simple derivative)\n",
        "+ we need a loss function (reuse $L_{CE}$), an optimization algorithm (reuse stochastic gradient descent), gradient to update (NEW) \n",
        "\n",
        "\n",
        "Computing the gradient\n",
        "+ the simple derviativesonly giveoutput for the last layer\n",
        "+ we must lopok back through all previous layers even though loss can only be computed at the final layer\n",
        "+ error backpropogation algorithm\n",
        "  + backward differentiation, what are the components of a function that I am trying to derive\n",
        "  + graph the steps in the computation\n",
        "  + computing the answeer is called a forward pass(start at inputs, compute everything, compute loss at the end )\n",
        "  + how do wee compute derivatives from this? how much does each step cotribute to final answer\n",
        "    + use chain rule!\n",
        "    + derivative of l with respect to each of the inputs using the chain rule on all of the intermediate steps\n",
        "    + do the backward pass to compute the partial derivatives (using the computer values from the forward pass)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module13_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3823
        },
        "cellView": "form",
        "outputId": "fd68a09e-b45a-4b30-e004-e3376a9d144a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module13_sections = [\n",
        "  (\"SLP Chapter 5.1 Classification: the sigmoid\", slp_chapter5_1),\n",
        "  (\"SLP Chapter 5.2 Learning in Logistic Regression\", slp_chapter5_2),\n",
        "  (\"SLP Chapter 5.3 The cross-entropy loss function\", slp_chapter5_3),\n",
        "  (\"SLP Chapter 5.4 Gradient Descent\", slp_chapter5_4),\n",
        "  (\"SLP Chapter 5.5 Regularization\", slp_chapter5_5),\n",
        "  (\"SLP Chapter 5.6 Multinomial logistic regression\", slp_chapter5_6),\n",
        "\n",
        "  (\"SLP Chapter 7.1 Units\", slp_chapter7_1),\n",
        "  (\"SLP Chapter 7.2 The XOR problem\", slp_chapter7_2),\n",
        "  (\"SLP Chapter 7.3 Feedforward Neural Networks\", slp_chapter7_3),\n",
        "  (\"SLP Chapter 7.4 Feedforward networks for NLP: Classification\", slp_chapter7_4),\n",
        "  (\"SLP Chapter 7.5 Feedforward Neural Language Modeling\", slp_chapter7_5),\n",
        "  (\"SLP Chapter 7.6 Training Neural Nets\", slp_chapter7_6),\n",
        "  (\"SLP Chapter 7.7 Training the neural language model\", slp_chapter7_7),\n",
        "  (\"Module 13 Lecture Notes\", module13_lecture_notes),\n",
        "]\n",
        "\n",
        "module13_markdown = format_module(13, \"Neural Networks\", \n",
        "                         module13_sections, \n",
        "                         module13_definitions)\n",
        "display(Markdown(module13_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n### Logistic Regression\n\nClassifier Components\n+ train a corpus of M observations in input output pairs $(x^{(i)}, y^{(i)})$\n+ we need to transform this into feature representation\n+ wee need to take a feature represenetation as an input to a function with classification as the output via a probability distribution\n+ we need of method of \"how good\" the curreent classification function is, calleed objectivee fun (or loss fun)\n+ optimization routine, how to adjust to minimize loss\n\nSentiment Classifier\n+ take text -> features -> output. label + or - \n+ logistic regression solves this by learning from a training seet, witgh weights and a bias term \n+ $z = \\sum_i w_ix_i + b$ (dot product of z and w + b)\n+ z is unbounded\n+ MAIN CHANGE FROM PRECEPTRONS : Z SQUISHED TO BETWEEN 0 AND 1\n+ $ y = \\frac{1}{1 + e^{-z}}$ sigmoid function, where $z = w \\cdot x + b$\n+ decision boundary : naturally falls at 0.5\n+ how do we extract features from raw text input??\n  + in NLP, define the amount of features in. thee text \n  + x1 = number of positive lexicon words in the review\n  + x2 = count of negativee lexicon words\n  + x3 = does no appear? \n  + x4 = number of. first and second person pronouns\n  + x5 = does ! appear\n  + x6 log of the word count \n  + weights?? can be given, can be learned\n\nLearning in Logistic Regression\n+ learn the weights and the bias term with loss function and optimization routine\n\n\n\n\n\n### Loss Functions\nMean Squared error: \n$L_{MSE}(\\hat{y}, y) = \\frac{1}{2} (\\hat{y}-y)^2$\n\nCross entropy loss: find a type of maximum likelihood estimator, choose params w, b that maximize the probability that we get the true label\n\n+ maximie the probability of the correct label $p(y|x) = \\hat{y}^y(1-\\hat{y})^{1-y}$\n+ why is this the function, y = 1 or y = 0 os the exponent tells us which part of the equation matters\n+ if y is 1, we try to maximize y hat, if y is 0 wee try to maximize 1 - y hat\n+ take the log of both sides $log(p(y|x)) = log(\\hat{y}^y(1-\\hat{y})^{1-y}) = y log(\\hat{y}) + (1-y) log(1-\\hat{y})$ where $\\hat{y} = \\sigma(w \\cdot x + b)$\n+ finally $L_{CE} = - [y log(\\sigma(w \\cdot x + b)) + (1-y) log(1-\\sigma(w \\cdot x + b))$]$ (flip sign to maximize a negative, minimize loss )\n+ correct: lowerr, incorrect: higher\n+ Total loss is sum of all of the losses (since we work in log space )\n\nFinding good parameters - Gradient Descent:\n+ argmin average loss\n+ gradient descent is to figure out for each of our weights, what direction should we  movee in (inc or dec) to lower loss\n+ find the most extreme downward slope\n+ convex optimization (loss is convex (global minimum))\n  + non convex is a much harder problem to solve \n  + define a step size that is the same as the learning rate $\\eta$ \"eta\"\n  + to get slope, derivativee if the loss function\n  + $\\frac{\\delta L_{CE}(w,b)}{\\delta w_j} = [\\sigma(w \\cdot x + b) - y]x_j\n  + difference between the true label and our eextimate times thee corresponding value of that feature\n\n### Stochastic Gradient Descent \n+ we have N weights, for each of the weieghts in the weight vector, how much should we updatee it and in what direction??\n+ what are the derivatives if the loss with respect to each weight compared to the true value\n+ $\\delta w_iL(f(x, \\theta), y)$ in a vector of length n COPY THESE EQS FROM THE SLIDEES\n+ $\\theta_{t+1} = \\theta_t\n\nThe Gradient\n+ tot update $\\theta$\n+  $L_{CE} = - [y log(\\hat{y}) + (1-y) log(1-\\hat{y})$]$\n+ derivative if this for one observation x and a single weight is :\n  + $ \\frac{\\delta L_{CE}(\\hat{y),y)}{\\deltaw_j} = [\\hat{y-y}]x_j$\n  + the derivative of the loss with respect to a single input and a single weight is the difference of the prediction and the actual value times the value xj\n+ COPY QS FROM SLIDES\n+ the gradient is take what we had before and add it up \n+ $ \\frac{\\delta L_{CE}(\\hat{y),y)}{\\deltaw_j} = [\\hat{y-y}]x_j$\n\nThe Stochastic Gradient Descent Algorithm\n+ initialize all weights to be zeros \n+ iterate some numsbe of times \n+ grab some item in random order xi, yi\n+ use classifier to. say what is the estimate y. hat\n+ compute loss by comparing y hat to y\n+ compute the gradienr and store it in the vector \n+ update the weights by subtracting out learning rate times gradient vector \n\nExample\n+ sentiment classification, + or -\n+ 2 features, 1 is count of num positive features, 2 is count of number of. negative words \n+ three weights, the two counts and the bias\n+ set all weights to zero intially\n+ select xi, yi (you have an input vector p = 3, n = 2, b = 1) yi = 1 (positive)\n+ $\\theta_1 = [0, 0, 0]$\n+ learning rate $\\eta = 0.1$\n+ $\\theta_2 = \\theta_1 - \\eta \\nabla_\\theta L(f(x^1, \\theta_1), y^1)$\n\n\nBatching \n+ we usually batch a bunch of items together for batch training \n+ usually, we do mini batch training group items together, update for that batch, and continue\n+ we usually pick this based on GPU memory constraints \n\nRegularization\n+ overfitting solution, adding penalty into the loss function that stop weights from getting too large \n+ we do this using some potential terms \n  + L1 is a linear function on the weights similar to manhattan distance \n  + L2 is a quadratic function uses the square of the l2 norm (euclidian distance) usually easier because of continuous derviative\n+ main goal is keep weight values small\n\nMultinomial Logisitc Regression\n+ what if we care about a problem with more than just binary classification\n+ ie positive, negative, neutral sentiment\n+ softmax takes an input vector and outputs a vector of values normalized into probabilities\n+ this can be interpreted as a probability distrubution on multiple classes \n\n### Neural Networks \n+ biological inspiration preceptron in the 1950s\n  + take inputs ansd assign them weights and if we sum the product of inputs and weights with an activation function we make a decision\n  + just like the human neuron (many inputs, one neuron, one output)\n  + in our brain, we have a lot of interconnected neurons\n+ everything is interconnected \n+ output of one neuron can be an input to other neurons \n+ feed-forward neural network architecture\n  + incoming arcts are inputs, ourgoing arcs are transmissions\n  + input layer, hidden layers (we do not directly observe), and an output layer\n  + training is more complicated, there are several layers that we do not see\n  + no need for feature engineering, the whole input raw is filtered thru using hidden layers\n  + tradeoff: time spent picking the right architechture/model \n\n\nSigmoid Neurons\n+ a small change in one of the weight values represents a small change in the resulting output\n+ z = xw+b, $\\sigma = e^{-z}$\n\nActivation Functions \n+ sigmoid is one of these,  but there are a lof of different ones that we can use \n+ three most used\n  + sigmoid (s curve)\n  + tangent (s curve)\n  + reLU (0 and then linear)\n\nFeed-Forward Neural Network\n+ simplest kind, fully connected (each item is connected to every other item in the next layer)\n+ multilayer, no cycles\n+ layer 0 is input layer, final layer is output layer, anything in between is hidden layer\n+ three steps per layer \n  + w * x\n  + add in bias b \n  + apply the activation function to it \n  + difference from logistic regression (change the dot product to a matrix multiply (singe every element in the layer has a weight vector))\n\n  + each nerual unit is a logistic regression classifier\n+ if this is the final layer, stick itinto a softmax function that gives us a distrubution over \n\nTraining Neural Nets \n+ how do we attribute errors? (in logistic regression it was a simple derivative)\n+ we need a loss function (reuse $L_{CE}$), an optimization algorithm (reuse stochastic gradient descent), gradient to update (NEW) \n\n\nComputing the gradient\n+ the simple derviativesonly giveoutput for the last layer\n+ we must lopok back through all previous layers even though loss can only be computed at the final layer\n+ error backpropogation algorithm\n  + backward differentiation, what are the components of a function that I am trying to derive\n  + graph the steps in the computation\n  + computing the answeer is called a forward pass(start at inputs, compute everything, compute loss at the end )\n  + how do wee compute derivatives from this? how much does each step cotribute to final answer\n    + use chain rule!\n    + derivative of l with respect to each of the inputs using the chain rule on all of the intermediate steps\n    + do the backward pass to compute the partial derivatives (using the computer values from the forward pass)\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "# Module 14 - Natural Language Processing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Jurafsky and Martin, Chapter 9 “Sequence Processing with Recurrent Networks” (Sections 9.1-9.3)\n",
        "\n",
        "slp_chapter9_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter9_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Jurafsky and Martin, Chapter 6 “Vector Semantics and Embeddings” (6.1-6.4, 6.8, 6.10-6.12)\n",
        "\n",
        "slp_chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_8 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_10 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_11 = \"\"\" Your summary here \"\"\"\n",
        "slp_chapter6_12 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module14_lecture_notes = \"\"\" \n",
        "\n",
        "#### Natural Language Processing\n",
        "\n",
        "### Intro\n",
        "+ Goal: Have machines communicate with words like a human would\n",
        "+ Vector Space Models - every word is representing as vector, where vector \n",
        "+ represents properties of that word.\n",
        "+ Sometimes these models end up with racism or sexism, as a result of being \n",
        "+ trained on this type of data\n",
        "\n",
        "### Natural Language Models\n",
        "+ Estimating probability of next word given previous x words\n",
        "+ Estimate probability of sentence consisting of word sequence $w_{1:n}$\n",
        "\n",
        "\n",
        "+ What happens if a certain 'next word' example was not seen in training data?\n",
        "   + Then we laplace smooth the data such that the probability of the word occuring \n",
        "   + is non-negative.\n",
        "\n",
        "+Neural Language Models Advantages\n",
        "   + Don't need smoothing\n",
        "   + They can handle much longer histories\n",
        "   + They can generalize over contexts of similar words\n",
        "   + Neural LMs tend to have much higher predictive accuracy than n-gram LMs\n",
        "\n",
        "+ Because we are creating vector for each word, it is easy to compare words for similarity\n",
        "+ by comparing their vectors.\n",
        "+ Express joint probability of word sequence in terms of the word vectors for the words in that sequence \n",
        "+ Simaltaneously learn the word vectors are the parameters of the function\n",
        "\n",
        "+ More on neural LMs\n",
        "   + Input - k-gram of words $w_{1:k} $\n",
        "   + Output - probability distribution over the next word\n",
        "   + On Input \n",
        "      + Start with one-hot vectors (binary vector only one non-zero term represents the word)\n",
        "      + Then the projection layer where a d-dimensional vector gives actual weights that we learn for each word\n",
        "      + Then the hidden layer where the previous k words are analyzed based on their order\n",
        "      + Ultimately the output layer which gives us the probability of each word in our vocab\n",
        "      + being the next word - we take the largest probability.\n",
        "+ Probability tables: give us probability of next table given previously queried x previous words\n",
        "\n",
        "\n",
        "### Lexical Semantic Models\n",
        "+ Broadly speaking this is putting logic into a word model to generate conclusions\n",
        "\n",
        "+ How do we represent the meaning of a word\n",
        "+ LMs represent words as a string of letters, but we ideally want meaning to encode\n",
        "   + Synonyms\n",
        "   + Anyonyms\n",
        "   + Connotations\n",
        "   + Semantic Roles\n",
        "   + Support for entailment (dog exists within animal), allows us to apply  logic to language\n",
        "\n",
        "### Vector Semantic Models 1\n",
        "+ Each word is representing as a point in vector space\n",
        "+ Words close to one another are semantically similar\n",
        "+ Compare vectors to get this similarity\n",
        "+ Takes advantage of the fact that though most words don't have synonms that words\n",
        "+ are similar to one another\n",
        "+ I.E. tall and high are similar to one another\n",
        "\n",
        "+ Distributional Hypothesis of Language\n",
        "   + optometrist and eye-doctor share many uttterance environments\n",
        "   + information retrieval: given input turn into vector find similar vector in our corpus of words \n",
        "   + Term Document matrix: allows you to find similar documents or similar words (depending on col or row)\n",
        "        + If we want to compare words we can take two documents and say three words\n",
        "        + We can take the values at (word, document) within or Term-Document matrix and make\n",
        "        + an (x,y) point in 2D space for each word, we can than compare the euclidian\n",
        "        + distance of these words to compare their similarity\n",
        "\n",
        "        + We can normalize these values by squaring the (word, document) value for each word taking the square root and then normalizing\n",
        "        + on the scale of 0 to 1, this brings these words closer together graphically\n",
        "        + Can also take cosine distance between these words in x-y space to find similarity\n",
        "\n",
        "### Vector Semantic Models 2\n",
        "\n",
        "+ Term-by-Term Matrix: every word is both a row and column vector\n",
        "   + cell - represnets how often a word appears in a context window surrounding other word\n",
        "   + context window - words adjacent to our current word (by k words) \n",
        "\n",
        "+ Language tends to have a long distance dependency\n",
        "   + The pictures ARE beatiful\n",
        "   + The pictures of the old man ARE beatiful\n",
        "\n",
        "+ Raw word frequency is not always a great measure of association between words\n",
        "   + Can be skered to \"of\" and \"the\"\n",
        "   + We want to have a measure of whetehr context word is informative of target word\n",
        "   + We can do TF-IDF: Term Frequency * inverse document frequency\n",
        "   + Equivilant to (how often word occurs in document) * (1 over the number of documents that it occured in)\n",
        "\n",
        "\n",
        "### Word Embeddings\n",
        "+ We have talked about words in large sparse matricies thus far\n",
        "+ Alernative is short and dense vectors\n",
        "\n",
        "+How do we get dense vectors? Train a classifier\n",
        "   + Treat target word and a neighboring context word as positive examples\n",
        "   + Randomly sample other words in lexicon to get negative examples\n",
        "   + Use logistic regression to train a classifier to distinguish the two cases\n",
        "   + Use the weights as the embeddings\n",
        "   + If we build model for 'apricot' and there is example 'tablesppon of apricot preserves or ...'\n",
        "   + then we want these surrounding words to be high\n",
        "   + then we choose random samples (not including the word apricot), we want those words to be low\n",
        "+ This entire process is called Word2Vec\n",
        "+ It is fast and easy to train\n",
        "+ Sometimes these embeddings capture relational meanings \n",
        "   + Unle -> Aunt\n",
        "   + King -> Queen\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module14_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2778
        },
        "outputId": "df010a38-86fb-4f0c-c690-fe6af5e297df"
      },
      "source": [
        "4#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module14_sections = [\n",
        "  (\"SLP Chapter 9.1 Language Models Revisited\", slp_chapter9_1),\n",
        "  (\"SLP Chapter 9.2 Recurrent Neural Networks\", slp_chapter9_2),\n",
        "  (\"SLP Chapter 9.3 RNNs as Language Models\", slp_chapter9_3),\n",
        "\n",
        "  (\"SLP Chapter 6.1 Lexical Semantics\", slp_chapter6_1),\n",
        "  (\"SLP Chapter 6.2 Vector Semantics\", slp_chapter6_2),\n",
        "  (\"SLP Chapter 6.3 Words and Vectors\", slp_chapter6_3),\n",
        "  (\"SLP Chapter 6.4 Cosine for measuring similarity\", slp_chapter6_4),\n",
        "  (\"SLP Chapter 6.8 Word2vec\", slp_chapter6_8),\n",
        "  (\"SLP Chapter 6.10 Semantic properties of embeddings\", slp_chapter6_10),\n",
        "  (\"SLP Chapter 6.11 Bias and Embeddings\", slp_chapter6_11),\n",
        "  (\"SLP Chapter 6.12 Evaluating Vector Models\", slp_chapter6_12),\n",
        "  (\"Module 13 Lecture Notes\", module14_lecture_notes),\n",
        "]\n",
        "\n",
        "module14_markdown = format_module(14, \"Natural Language Processing\", \n",
        "                         module14_sections, \n",
        "                         module14_definitions)\n",
        "display(Markdown(module14_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n#### Natural Language Processing\n\n### Intro\n+ Goal: Have machines communicate with words like a human would\n+ Vector Space Models - every word is representing as vector, where vector \n+ represents properties of that word.\n+ Sometimes these models end up with racism or sexism, as a result of being \n+ trained on this type of data\n\n### Natural Language Models\n+ Estimating probability of next word given previous x words\n+ Estimate probability of sentence consisting of word sequence $w_{1:n}$\n\n\n+ What happens if a certain 'next word' example was not seen in training data?\n   + Then we laplace smooth the data such that the probability of the word occuring \n   + is non-negative.\n\n+Neural Language Models Advantages\n   + Don't need smoothing\n   + They can handle much longer histories\n   + They can generalize over contexts of similar words\n   + Neural LMs tend to have much higher predictive accuracy than n-gram LMs\n\n+ Because we are creating vector for each word, it is easy to compare words for similarity\n+ by comparing their vectors.\n+ Express joint probability of word sequence in terms of the word vectors for the words in that sequence \n+ Simaltaneously learn the word vectors are the parameters of the function\n\n+ More on neural LMs\n   + Input - k-gram of words $w_{1:k} $\n   + Output - probability distribution over the next word\n   + On Input \n      + Start with one-hot vectors (binary vector only one non-zero term represents the word)\n      + Then the projection layer where a d-dimensional vector gives actual weights that we learn for each word\n      + Then the hidden layer where the previous k words are analyzed based on their order\n      + Ultimately the output layer which gives us the probability of each word in our vocab\n      + being the next word - we take the largest probability.\n+ Probability tables: give us probability of next table given previously queried x previous words\n\n\n### Lexical Semantic Models\n+ Broadly speaking this is putting logic into a word model to generate conclusions\n\n+ How do we represent the meaning of a word\n+ LMs represent words as a string of letters, but we ideally want meaning to encode\n   + Synonyms\n   + Anyonyms\n   + Connotations\n   + Semantic Roles\n   + Support for entailment (dog exists within animal), allows us to apply  logic to language\n\n### Vector Semantic Models 1\n+ Each word is representing as a point in vector space\n+ Words close to one another are semantically similar\n+ Compare vectors to get this similarity\n+ Takes advantage of the fact that though most words don't have synonms that words\n+ are similar to one another\n+ I.E. tall and high are similar to one another\n\n+ Distributional Hypothesis of Language\n   + optometrist and eye-doctor share many uttterance environments\n   + information retrieval: given input turn into vector find similar vector in our corpus of words \n   + Term Document matrix: allows you to find similar documents or similar words (depending on col or row)\n        + If we want to compare words we can take two documents and say three words\n        + We can take the values at (word, document) within or Term-Document matrix and make\n        + an (x,y) point in 2D space for each word, we can than compare the euclidian\n        + distance of these words to compare their similarity\n\n        + We can normalize these values by squaring the (word, document) value for each word taking the square root and then normalizing\n        + on the scale of 0 to 1, this brings these words closer together graphically\n        + Can also take cosine distance between these words in x-y space to find similarity\n\n### Vector Semantic Models 2\n\n+ Term-by-Term Matrix: every word is both a row and column vector\n   + cell - represnets how often a word appears in a context window surrounding other word\n   + context window - words adjacent to our current word (by k words) \n\n+ Language tends to have a long distance dependency\n   + The pictures ARE beatiful\n   + The pictures of the old man ARE beatiful\n\n+ Raw word frequency is not always a great measure of association between words\n   + Can be skered to \"of\" and \"the\"\n   + We want to have a measure of whetehr context word is informative of target word\n   + We can do TF-IDF: Term Frequency * inverse document frequency\n   + Equivilant to (how often word occurs in document) * (1 over the number of documents that it occured in)\n\n\n### Word Embeddings\n+ We have talked about words in large sparse matricies thus far\n+ Alernative is short and dense vectors\n\n+How do we get dense vectors? Train a classifier\n   + Treat target word and a neighboring context word as positive examples\n   + Randomly sample other words in lexicon to get negative examples\n   + Use logistic regression to train a classifier to distinguish the two cases\n   + Use the weights as the embeddings\n   + If we build model for 'apricot' and there is example 'tablesppon of apricot preserves or ...'\n   + then we want these surrounding words to be high\n   + then we choose random samples (not including the word apricot), we want those words to be low\n+ This entire process is called Word2Vec\n+ It is fast and easy to train\n+ Sometimes these embeddings capture relational meanings \n   + Unle -> Aunt\n   + King -> Queen\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 19957
        },
        "id": "T3cm1WV542_a",
        "outputId": "4a1f4421-6575-45aa-a58b-de4ca677515f"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module8_markdown, \n",
        "                             module9_markdown, \n",
        "                             module10_markdown, \n",
        "                             module11_markdown, \n",
        "                             module12_markdown,\n",
        "                             module13_markdown,\n",
        "                             module14_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 8: Markov Decision Processes\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Chapter 16.1 summary. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## AIMA Chapter 17.1 Sequential Decision Problems\n Your summary here \n\n## AIMA Chapter 17.2 Algorithms for MDPs\n Your summary here \n\n## Module 8 Lecture Notes\n\n\n### Stochastic or Probabilistic Task Environments: MDPs\n\nMDPs are a kind of non-deterministic search problem that are applicable in a fully observable task environment where outcomes are non-deterministic. The solutions to MDPs are called policies. We will look at Expectimax, Value iteration, and Policy iteration to solve MDPs.\n\n#### Introduction\n\nToy Problem : Navigating an Asteroid Field \n+ navigating a fully observable gridworld \n+ starting at a start state, and picking an action at each turn\n+ terminates at asteroid crashor reaching planet \n+ stochasticenvironmenty, when we pick an action the result of the action is uncertain\n  + there is some probability of moving up and some probability of something weird happening\n+ we must define a probabilistic transition model\n\nStochastic Transition Model\n+ transition function T(s, a, s') (current state s, action I apply in s a, and next state s')\n+ p(s'|s,a) is the probability that the transition function is taking on \n+ we ignore the historyup until the current point, Markov Property\n\nReward Function\n+ rewards can be positive or negative, bounded by a max value\n+ since rewards are sequential, we must extablish a utility function in a sequence of states\n+ an agentcan recieve a reward at eeach state, not only at the goal state \n+ R(s, a, s') is reward of taking action a in state s to get to state s'\n+ rewards are additive over. all steps you take\n\n\n\n#### MDP Formulation\n\nMarkov Decision Process: a sequential decision model for a fully observable \nenvironment with a stochastic transition model with additive rewards (non-determinstic search)\n\nFormal Definition \n+ a set of states S\n+ a set of actions A\n+ the transition function T(s, a, s') called the model\n+ the reward function R(s, a, s') or R(s')\n+ initial and terminal states\n+ solution is a policy pi(s) = a (a function that tells the agent what action it should take if its at state s)\n+ in a gridworld, can be represented by arrows on a grid\n+ we would like to find the optimal policy, pi* (depends on reward function)\n+ because of non-determinism (if i execute the same policy many times I will gget a diff score every time)\n+ use the expected utility of all possible paths\n+ games may have an infinite horizon! bounce around forever \n\nShould we value more reward sooner or later? How do we model this? Rewards now because if we defer them into  the future there is some chance we do not end up with them.\n\nDiscounting Term : how much we are willing to postpone immediate gratification\ndiscount value is gamma \n\nWe can vizualise the search as an expectimax tree, where at each layer we apply the discount \n\nStationary Preferences: if i prefer seq a to seq b [a1, a2, a3] > [b1, b2, b3], then [r, a1, a2,a3] > [r, b1, b2,b3]\n\nTwo ways to define utilities: \n+ U[r1, r2, r3....] = r1+r2+r3\n+U[r1, r2, r3....] = r1+gr2+g^2r3\n\nTo handle infinite utility:\n+ Only allowing a finite horizon (k steps until game over) and non-stationary policy (depends on time left in the game)\n+ discounting (eventuallywill converge as a sum)\n+ absorbing state (ifyou runany policy long enough a terminal state will be reached )\n\n\n#### Value Iteration Algorithm\n algorithm for choosing optimal actions\n + start with V_0(s)= 0 : notimee steps left means an expected reward sum of 0 (subscript is thenumber of timesteps remaining)\n + $V_{k+1} = \\max_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V_k^*(s')]$ BELLMAN EQUATION\n + do this recursively (increase k at each iteration)\n + $O(S^2A)$ every state may be connected to all other states (O(mmn)) in a fully connected graph\n + approximationswill reach optimal values because of the vanishing rewrad in thediscount factor\n\n Convergence* : finding the optimal policy \n + How do we know $V_k$ will converge? two cases \n  + max depth M, theen V_M holds as best policy\n  + if discount is less than 1, any state can be viewed to converge because each layer has exponential decay\n\n#### Policy Evaluation\n\n+ given a policy $\\pi$, what values do I get from it? \n+ if i fixes a policy $\\pi$ the tree gets much simpler\n+ $V^{\\pi}(s)= \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+ \\gamma V^{\\pi}(s')]$\n+ we can do this recursively $O(S^2)$ same as value iteration\n+ or, can be solvedas a system of linear equations \n\nPolicy Extraction\n+ given a set of values we assume are correct, what policy should w take? \n+ we do a mini expectimax\n+ $\\pi ^* (s) = argmax_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^{*}(s')]$\n+ gets policy implied by the values\n\n#### Policy Iteration Algorithm\n+ value iteration is slow (both iteration and convergence), policy convergence is much better!\n+ Step 1: calculate the utilitiy of a fixed policy \n  + $V_{k+1}^{\\pi}(s)= \\sum_{s'} T(s,\\pi(s),s')[R(s,\\pi(s),s')+ \\gamma V_k^{\\pi}(s')]$ until values converge \n  + no max operation, values converge must faster\n+ Step 2: Improve by updating the policy using a one-step look ahead (estimate of how good itis to be at a particular state)\n  + $\\pi_{i+1} ^* (s) = argmax_a \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^{\\pi_i}(s')]$\n\n#### Comparing Value Iteration to Policy Iteration\n+ in Value iteration\n  + every iteration updates both value and policy (implicitly by taking max a )\n  + we dont track policy, but were continually recomputing it \n+ in policy iteration\n  + several passes that. update utilitygiven a policy (fast)\n  + a new policy is chosen after evaluation\n  + if no better exists, we are done \n\n\n#### Maximum Expected Utility\n+ why should we average utilitties instead of minimax? \n  + minimax looks a the WORST CASE, assuming playing against an adversary\n+ a rational agent should pick the action that maximizes the exoected utility given its knowledge about the world \n+ where do these utilities come from, how do we know they exist, is averaging the right way to do this? \n+ expectimax does not have insensitivity to transformations, MAGNITUDES MATTER\n\nUtilities\n+ map of state of thee world onto a real valued number \n+ represents the agent's preferencees of how good an outcome is \n+ Thm: any rational preference can be summarized by its utility function\n+ hard wire utilities and let behaviors emerge\n\nPrefereneces\n+ prizes A, B\n+ lotteries L = [p, A; 1-p, B]\n+ preferenece A > B\n+ Indifference A ~ B\n\nAxioms:\n\n+ Transitivity : $(A > B) \\wedge (B > C) \\Rightarrow (A > C)$\n+ Orderability : $(A > B) \u000bee ( B > A) \u000bee (A ~ B)$\n+ Continuity: $A > B > C \\Rightarrow \\exists p [p, A; 1-p, C] ~ B$\n+ Substitutability: $A ~ B \\Rightarrow [p, A; 1-p, C] ~ [p, B; 1-p, C]$\n+ Monotonicity: $ A > B \\Rightarrow ( p \\geq q \\Leftrightarrow [p, A; 1-p, C] ~ [q, A; 1-q, B])$ (If an agent prefers A to B and there are two lotteries with outcomes A and B, then the agent must prefer the lottery that has a higher probability for A.)\n+ Given anny preferences that satisfy those axioms, there exists a real valued function that satisfies your preferences \n+ $U([p_1, S_1,....,p_n,S_n]) = \\sum_ip_iU(S_i)$\n+ MEU\n\nUtility Scales \n+ normalize utilitues between $u_-$ and $u_+$\n+ micromorts, one millionth cance of death\n+ QALYs, quality adjusted life years\n\nHuman Utilities \n+ associate best possible prize with p and worst catastrophe with 1-p\n+ find the p that makes you indiffereent, then you know the utility\n+ money does not behavee as a utility function\n+ Expected monetary value of a lottery is p \\$X + 1-p\\$Y\n+ sometimes people are isk averse, avoid lottery over the money\n\n\n\n## Module 8 Definitions\n* **Optimal q value** - expected utility of having taken action a from state s and then acting optimally (p(s') + r(s') * discounted s')\n* **Q*(s,a)** -  $Q^*(s,a)= \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma V^*(s')]$ \n* **V*(s)** - expected utility startingin s and acting optimally $V^*(s) = max_a Q^*(s,a)$ \n* **Pi*(s)** - optimal policy from state s\n* **Policy** - takes in a state and returns a best action that an agent can take when it finds that state\n\n\n# Module 9: Reinforcement Learning\n## AIMA Chapter 17.3 Bandit Problems\n Your summary here \n\n## AIMA Chapter 22.1 Learning from Rewards\n Your summary here \n\n## AIMA Chapter 22.2 Passive Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.3 Active Reinforcement Learning\n Your summary here \n\n## AIMA Chapter 22.4 Generalization in Reinforcement Learning\n Your summary here \n\n## Module 9 Lecture Notes\n\n\n### Introduction to Reinforcement Learning\n\n+ in MDPs, even though the environment was stochastic, we knew the probability dist over states and the rewards\n+ we no longer have that given to us, we have to learn it\n+ multi arm bandits (like slot machines in vegas) offline planning, you don't have to play at all to do this\n+ What if you don't know the probabilities? You try it out\n+ MDPs are planning, we now have to learn\n+ Ideas\n  + exploration : the amount of time you have to do to try new things to havee enough info\n  + exploitation: eventually, you have to use what you know\n  + Regret: even if you learn, you make mistakes\n  + Sampling: because of chance, you have to try thinsg repeatedly\n  + Difficulty: learning is harder than solving an MDP\n\n+ a set of states S\n+ a set of actions A\n+ a model T(s, a,  s') NOT GIVEN\n+ reward function R(s, a, s') NOT GIVEN\n+ still looking for $\\pi(s)$\n\nModel Based Learning: approximate T by learning, $\\hat{T}$ and what we have experienced, then plug it in as an MDP\n\n### Passive Reinforcement Learning: Model Free\n+ take an action and compare reesults of what we thought was gonna happen towhat actually did happen\n+ if there is a deviation, we adjust the values\n+ Simplified task policy evaluation \n  + given a policy, how good is it? watch the outcomes \n  + the learner is just along for the ride\n  + not offline, you still have to do the policy\n  + direct evaluation, according to pi, average together observed values (run through to the end)\n    + you do not need to keep track of instantaneous reward \n    + does not take into account structure, takes a long time to learn\n+ why don't we use policy evaluation? with recursive iteration (as in module 8) we would need T and R, and we don't have that \n+ can we make soething similar to policy evaluation without T and R?\n+ take samples of s' and average over all of the samples\n  + $sample_1 = R(s, \\pi(s), s'_1) + \\gamma V^{\\pi}_k(s'_1)$\n  + $sample_2 = R(s, \\pi(s), s'_2) + \\gamma V^{\\pi}_k(s'_2)$\n  + $sample_n = R(s, \\pi(s), s'_n) + \\gamma V^{\\pi}_k(s'_n)$\n  + $V^{\\pi}_{k+1} = \\frac{1}{n} \\sum_i sample_i$\n  + can we guarantee that we will be in s n times? we cant do it again and again\n  + this is NOT possible\n\n### Temporal Difference Learning\n+ learn from every experience \n+ Update V(s) every time you experieence (s, a, s', r)\n+ things that are more likely to occur will update values more often \n+ follow pi, keep a running average \n+ $sample = R(s, \\pi(s), s') + \\gamma V^{\\pi}_k(s')$\n+ $V^{\\pi}(s) = (1- \\alpha) V^{\\pi}(s) + \\alpha sample$\n + $V^{\\pi}(s) = V^{\\pi}(s) + \\alpha (sample -  V^{\\pi}(s))$\n+ alpha is the learning rate, how much new samples contribute to the updates\n+ comparing current extimates against sample value, called interpolation\n+ more recent samples end up being more important over time (1 - $\\alpha$ gets exponentially decayed)+ this is modeel free learning\n+ problems with this: \n  + wee cannot turn values into a new policy, we need q values (what is the best action to take at s\n  + we only have the value of the states \n\n### Active Reinforcement Learning (Q - Learning)\n+ we still dont know transitions or rewards, we want to learn the optimal policy \n+ Q state is a state action pair\n+ instead of being.  iven a policy, like in passive, you get to make all of the choices\n+ exploration (try to do new, risk) v exploitation (using the knowledge youve acrued so far to make predictions)\n\nQ- Value Iteration\n+ start with a time delimited number of step $V_0(s) = 0$(subscript is the number of steps left)\n+ Given $V_k$ calculate $V_{k+1}$ using bellman equation (see above) bottom up recursion works nicely here (DP)\n+ But, when looking to determine a policy, value of Q state is easier to do policy extraction\n+ So, transforming this notion\n  + $Q_0(s,a)$\n  + $Q_{k+1}(s,a) = \\sum_{s'} T(s,a,s')[R(s,a,s')+ \\gamma max_{a'}Q_k^*(s', a')]$\n  + you can easily extract actions to buold a policy from this\n\nQ-Learning \n+ a bit different than q value iteration since we dont know T and R\n+ Q learning is sample based Q-value iteration \n+ learn Q values as we go\n+ a sample is (s, a, s', r) we are in s, we choose a, we non-deterministically end up in s', and get a reward r\n+ consider the current Q(s,a) that you have (old approx)\n+ $sample = R(s, a, s') + \\gamma \\max_{a'} Q(s',a')$\n+ keep a running average (there is no gurantee that you will ever end up in a state again)\n  + UPDATE $Q(s, a) = (1- \\alpha)Q(s, a)+ \\alpha(sample)$\n  + $\\alpha$ is the learning rate, how much we trust new data versus estimates we accrued\n+ we converge to the optimal policy EVEN IF we act suboptimally\n+ called off-policy learning \n  + you have to learn enough (try new things)\n  + you have to make the learning rate small enough\n\n### Exploration vs Exploitation\n+ ineviatble tradeoff between trying new things and going based off of knowledge \n\nHow do we Explore? \n+ Simplest method: $\\epsilon$- greedy\n  + generate a random number\n  + if its less than $\\epsilon$ act randomly\n  + else act on current policy\n  + epsolon is small, and. acts as a prrobability\n  + using randomness, we may repeat bad actions during the random step\n    + to fix: decrease epsilon over time \n    + encode a function to weight the random actions \n\nExploration Function\n+ eexplore areas whos badness is not yet established, eventually stop exploring \n+ $f(u, n) = u + \\frac{k}{n}$ $u$ is current utility estimate of a state and n is the number of times its been explored\n  + if its a good state we will visit again, if its a bad state we only visit while n is small\n+ REGULAR UPDATE $Q(s, a) = \\alpha(R(s, a, s') + \\gamma \\max_{a'} Q(s',a')$\n+ MODIFIED UPDATE $Q(s, a) = \\alpha(R(s, a, s') + \\gamma \\max_{a'} f(Q(s',a'), N(s',a'))$\n\nRegret\n+ you will eventually get to the optimal policy, but not sure how quickly\n+ regret measures how many mistakes you made overtime\n  + the difference between your expected rewards and optimal expected rewards\n  + minimizing regret tries to learn optimal as quickly as possible\n\n### Approximate Q-Learning \n+ when there are lots of possible states, we ecant visit every one \n+ generalize about states \n+ Q-Learning maintains a huge table of state action pairrs\n  + for large game states like chess, this is not possible \n\nGeneralizing Across States\n+ we cannot possibly learn about every single state\n+ learn through observation from training states\n+ generalize to new statees that wee have never seen before that are somehow SIMILAR\n+ flashback -- evaluation functions, take a partial completed state and take feeatures to make an estimate \n  + quantifying features and assigning weights to them\n\nLinear Value Function\n+ using a feature representation, we can write a q function or value function for any state using weights \n  + $V(s) = w_1f_1(s) + w_2f_2(s)+...+w_nf_n(s)$\n  + $Q(s,a) = w_1f_1(s) + w_2f_2(s,a)+...+w_nf_n(s,a)$\n+ advantage: experiencee is summed up in a few powerful numbers\n+ states may share the same features but be different, and we miss that \n+ learning algorithm setsthe weights automatically\n+ transition = (s, a, r, s')\n+ difference = $[r + \\gamma \\max_{a'}Q(s', a')] - Q(s, a)$ difference from what i though i would get from what it is seeming like i am getting now \n  + Exact Q learning,  take current q and add in alpha times difference \n  + approximate q learning $w_i = w_i + \\alpha [difference]f_i(s,a)$ update weights in proportion to the feature value\n  + intuitive interpretation, each of the weights is like a slider\n  + formal justification, online least squares\n\n\n\n\n\n\n## Module 9 Definitions\n* **Term** - your definition here\n\n\n# Module 10: Probabilies and Language Models\n## AIMA Chapter 12.1 Acting under Uncertainty\n Your summary here \n\n## AIMA Chapter 12.2 Basic Probability Notation\n Your summary here \n\n## AIMA Chapter 12.3 Inference Using Full Joint Distributions\n Your summary here \n\n## AIMA Chapter 12.4 Independence\n Your summary here \n\n## AIMA Chapter 12.5 Bayes’ Rule and Its Use\n Your summary here \n\n## AIMA Chapter 12.6 Naive Bayes Models\n Your summary here \n\n## AIMA Chapter 12.7 The Wumpus World Revisited\n Your summary here \n\n## SLP Chapter 3.1 N-Grams\n Your summary here \n\n## SLP Chapter 3.2 Evaluating Language Models\n Your summary here \n\n## SLP Chapter 3.3 Sampling sentences from a language model\n Your summary here \n\n## SLP Chapter 3.4 Generalization and Zeros\n Your summary here \n\n## SLP Chapter 3.5 Smoothing\n Your summary here \n\n## SLP Chapter 3.7 Huge Language Models and Stupid Backoff\n Your summary here \n\n## Module 10 Lecture Notes\n \n\n### Review on Probabilities \n+ often faced with needing to reason about uncertainty\n+ using probabiloty to reason and predict\n+ unobserved variables (what we dont know will happen)\n+ observed variables are things that we know have happened\n+ agent knows something about known variables that help predict about unknowns\n\n+ probabilities are about possible worlds, quantify likelihood of occurrence\n+ possible worlds are sample space, they are mutually exclusive and exhaustive \n+ P(w) for each world w\n+ random variable is an apsect of the world about which we have uncertainty\n\n\nAxioms of Probability \n+ $0 \\leq P(w) \\leq 1$\n+ $ \\sum_{w \\in \\Omega} P(w) = 1$\n\n### Distributions\n+ for each unobserved RV there will be an associated set of probabilities (in a table)\n\nJoint Distrubutions\n+ specifying a real number outcome for each RV $X_1, X_2, ....X_n$\n+ you can make a joint table to represent this \n+ what is the size of this for n variables with domain sizes d?? $$d^n$$ (impractical!!)\n  + we can learn how variables interrelate \n\nProbabilistic Moxdel \n+ joit dist over a group of RVs \n+ each RV has a domain and a set of assignments is outcomes\n+ probabilistic models are all normalized \n+ an event is a set of outcomes \n+ hot AND sunny is different than hot OR sunny \n\nMarginal Distributions\n+ sub tables of a probability model that isolate or remove some variables that we dont care about \n\nConditionals \n+ $P(a|b) = \\frac{P(a,b)}{P(b)}$\n\n### Probabilistic Inference and Rules\n+ weve got some desired probability, but we are given other sets of probbility \n+ distrributions change as we get more evidence \n+ 3 sets of things \n  + evidence variables : things that we know what happened \n  + query variables: reasoning about these \n  + hidden variables: we know they are happening but we dont reason about them \n  + we find $P(Q | e_1,...,e_k)$\n  + we are given joint table\n    + sum out H to get joint of Q and es ($P(Q, e_1, ..., e_k$)\n    + now we have to normalize to convert it back to a probability dist \n\nwhat if innstead given marginal or conditional?? \n\n+ product rule $P(x,y) = P(y)*P(x|y)$\n+ chain rule $P(x1, x2, x3) = P(x1) P(x2|x1) P(x3|x2, x1)$\n+ two ways to factor a joint probability\n  + Bayes Rule $P(x,y) = P(x)P(y|x) = P(y)P(x|y)$\n\n### Probabalistic Language Models\n+ autocomplete, machine translation, spell correct,.... \n  + all of these are probabilistic language models \n\n+ goal is compute the probabilisty of a sequence of words\n+ given a current sequence, what is the probability that this is the next one \n+ correspond each word to a RV\n+ we end up using chain rule and joint distrubutions\n \n\nHow do we estimate theseprobabilities?? \n+ one way, maximum likelihood estimation\n  + count up occurrrences and divide\n  + problem: it is dependent on you seeing it in the corpus, need huge dataset\n+ make a simplifying assumption: markov\n  + probability of next state only depends on the current state (previous k words)\n  + so, how much history should we use???\n    + unigram (no history), bigram(one word history), trigram(2 words history), 4-gram(3 words)\n\nMarkov History\n+ Eugene Onegin count up russian character probabilities in 1913\n+ 1928 n-gram used to approx english by Shannon\n+ 1956 Comsky defines finite markov models (incapable of modeling grammar) (linguists ignore him)\n+ 1980s IBM Jelenik uses n-gram modeling for speech recognition\n+ 1993 Jelinek again develops statistical machine translation \n  + $argmax_ep(e|f)=p(e)p(f|e)$\n+ jelenik left IBM for hopkins\n+ Brown and Mercer move to renaissance Tech (hedge fund) use this stat modeling\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 10 Definitions\n* **Term** - your definition here\n\n\n# Module 11: Probabilistic Reasoning and Bayes’ Nets\n## AIMA Chapter 13.1 Representing Knowledge in an Uncertain Domain\n Your summary here \n\n## AIMA Chapter 13.2 The Semantics of Bayesian Networks\n Your summary here \n\n## AIMA 13.3 Exact Inference in Bayesian Networks\n Your summary here \n\n## Module 11 Lecture Notes\n \n\n### Probabalstic Models and Bayes Nets\n+ Probability models inform us about how the actions of our world impact different occurences. Bayes Nets are more attractive than full\n+ joint probability distributions because they compactly show us what events impact others within smaller tables.\n+ Bayes Nets are able to achieve this compactness by making assumptions on independence of variables.\n+ Independence - we know something about variable A but this knowledge has no impact on the occurence of variable B.\n\n### Review of Independce \n+ Conditional Independence: $P(x,y |z) = P(x|z) * P(y|z)$ which is expressed as $X \\indep Y|Z$\n+ Alarm \\indep Fire|Smoke$ - In english this means that Alarm and Fire are independent of one another if we see Smoke\n+ Conditional Indpendence tells us a lot about the world and is useful in building models\n+ Equivilant definition of Conditional Independence: $P(x| z,y) = P(x|z)$\n+ $P(z|x, y) = P(x,y,z) / P(x,y)$\n\n\n### Bayes Net Properties\n+ $P(x_i | x_1 ... x_{i-1}) = P(x_i| parents(X_i)) $\n+ This means that the probability of variable x_i is conditional not on all of its preceding variables but only its direct parents\n+ D-seperation: We build our bayes net off of some known conditional independence, often tho other conditional independence arises in net\n+ How do we read it off? With D- Seperation - understanding independence with triples.\n+ D-Seperation:\n   + Causal Chain\n       + X => Y => Z\n       + Low Pressure => Rain => Traffic\n       + $ P(X,Y,Z) = P(X)P(Y|X)P(z|y) $\n       + X is not independent of Z\n   + Common Cause\n       + Y => X, Y=> Z\n       + Project Due => Forums Busy, Project Due => Office Hours Full\n       + $ P(x,y,z) = P(y)P(x|y)P(z|y) $\n       + X is not independent of Z\n       + However, Z is independent given X and Y\n   + Common Effect\n       + x => Z, Y => Z\n       + raining => traffic, ballgame => traffic\n       + X and Y are independent\n       + X and Y are not independent given Z    \n\n#### Reachability and Path\n+ Suppose we have BN, Q: Are two variables in BN indep?\n+ Solution: Analyze the graph\n+ We can break down complex graph into instances of the three examples above\n+ Question: Are X and Y conditionally indep given evidence variables {Z}?\n   + Yes if X and Y are d-seperated by Z, meaning that all undirected paths from X to Y are non-active\n   + Active Triple => Non-Independence\n   + Inactive Tripe => Independence\n   + A Path is 'active' if all triples along the path are active\n\n### D-Seperation\n+ What is we want to determine if two variables are conditionally independent\n+ $ X_i \\indep X_j | \\{ X_{k_1}, ..., X_{k_n} \\} $\n+ Look at all undirected paths between I and J, look at all triples along each path\n+ If one or more paths are actives then independence is not guarenteed\n+ If all paths inactive then independence is guarenteed\n+ This means that you can have an independence between X and Y, even if there exists an active triple as long as this active triple is in an inactive path (at least one other triple along this path is inactive).\n\n### Inferences\n+ Inference: calculating some useful quantity from a joint probability distribution\n+ Inference by Enumeration\n    + We break all variables in BN into three categories\n    + Evidence Variables: ones we know the outcomes to $e_1 ... e_n $\n    + Query Variables: what we care about reasoning about\n    + Hidden Variables: All other variables (we usually care less about this)\n    + We want $ P(Q | e_1 ... e_k) $. In order to get we ...\n         + Step 1: select entries consistent with evidence\n         + Step 2: Sum out hidden variables to get joint of query and evidence\n         + Step 3: Normalize $ * 1/Z $ so that we have a probability distribution\n    + E.X. $ P(B | j+, m+)$ => probability there was a break in given that you have calls from jon and mary\n    + This can be expressed mathematically as: $ \\sum_{e,a} P(B,e,a,+j,+m)$ where e and a are non-observed variables.\n    + $= \\sum_{e,a} P(B) P(e) P(a|B,e)P(+j|a)P(+m|a)$    \n    + where we sum over all possible combinations of values of hidden variables e and a \n+ This process can become very slow with a large number of unobserved variables. \n\n\n\n\n \n\n## Module 11 Definitions\n* **Concept** - definition\n\n\n# Module 12: Naive Bayes and Perceptrons\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## SLP Chapter 4.1 Naive Bayes Classifiers\n Your summary here \n\n## SLP Chapter 4.2 Training the Naive Bayes Classifier\n Your summary here \n\n## SLP Chapter 4.3 Worked Example\n Your summary here \n\n## SLP Chapter 4.4 Optimizing for Sentiment Analysis\n Your summary here \n\n## SLP Chapter 4.5 Naive Bayes for other text classification tasks\n Your summary here \n\n## SLP Chapter 4.6 Naive Bayes as a Language Model\n Your summary here \n\n## SLP Chapter 4.7 Evaluation: Precision, Recall, F-measure\n Your summary here \n\n## SLP Chapter 4.8 Test sets and Cross-validation\n Your summary here \n\n## SLP Chapter 4.9 Statistical Significance Testing\n Your summary here \n\n## SLP Chapter 4.10 Avoiding Harms in Classification\n Your summary here \n\n## Module 12 Lecture Notes\n \n\n### Overview\n+ Naive Bayes and Perceptrons use labelled training data to learn a classification decision.\n+ Learning involves learning the probability of a feature given another feature.\n+ Perceptrons are different from Naive Bayes in that they don't compute probability of feature - instead they compute a distribution\n+ of weights for classification. With each misclassification perceptrons update their distribution.\n+ Perceptrons form the building blocks of neural networks\n\n### Classification Task\n+ Up until now these probabilities for BN's have been given to us - now we have to compute them. We typically do this with ML\n+ Regression - we want ML to determine some numeric value for us based on data\n+ Classification - there are a finite number of possible results we want ML to tell us which result current instance is\n+ E.X. spam classification based on text of email. We create vector of words and associated likelhood of spam, classify based on it\n+ Additional E.X. Digit classification based on handwritten examples\n+ Typically need large quantity of labelled data and features used to make classification\n+ Model Based Classification: build a model (similar to a BN model)\n  + Instantiate any observed features\n  + Query for the distribution of the label conditioned on the features\n  + Spam/Ham would be the query where the variables that we know are the ones in email\n  + How do we structure BN?\n  + How do we learn probabilites of all the variables?\n\n\n### Naive Bayes\n+ Start by assuming that all features are independent of one another and dependent on the label\n+ We accumulate giant probability table of $ P(F_2 | SPAM)$  $ P(F_1 | SPAM) $ $ P(F_1 | NON-SPAM) $\n+ Each new input to the model will have binary values for the above expressions (either in the email or not, either coordinate is colored or not)\n+ Model: $P(Y|F_{0,0} ... F_{n,n}) = P(Y) \\Pi P(F_i | Y) $\n+ We only have to specify how each feature depends on the class, therefore LINEAR in the number of variables.\n+ Inference\n  + We have an input features, we get conditional probability of each label based on features, sum and normalize by dividing by features\n+ In order to compute the table with examples $ P(F_2 | LABEL)$ we come up with probability estimates for each label. E.X. think of coordinate in grid and probability of it being digit 1 through 9\n\n\n### Basic Concepts in ML\n+ Training Data - we give model labeled data so that it can train itself\n+ Test Data - We see how well model did after getting trained\n+ Held-Out Set - useful for hyperparamets of model (almost like a practice test before test data)\n+ Overfitting - we over model the data, for idiocynicaries that appear in the training data but not in the real world\n+ E.X. think about a three with a small smudge on the end, if we overfit we might see this smudge alone and determine that this value cannot be 3\n+ Most of the time overfitting comes at the result of assigning 0 probability to unseen events in training data\n+ In order to fix this we smooth our estimates. How do we do this?\n  + Elicitation - ask a human\n  + Empirically - use training data, number of times seen divided by number of samples \n+ What about unseen events?\n  + Lets pretend that we saw each event once more than we actually did and then recompute empirically as we had (Laplace Smoothing)\n  + We can also Laplace smooth with 2,3, ... 100 etc. depending on the circumstance\n  + Can also perform Linear Interpolation (Laplace performs poorly for $P(X|Y)$ when $|X|$ or $|Y|$ are very large)\n    + $P_{LIN}(x|y) = \\gamma P'(x|y) + (1.0 - \u0007lpha)P'(x)$ where P(x) is conditional probability of label and alpha is a hyperparameter\n+ Generally speaking we \n  + Learn parameters from training data\n  + Tune hyperparameters on our held-out data (k value for laplace, or alpha for linear interpolation)\n+ We tend to compare the accuracy of our models to some 'baseline' which is the current success rate in classification of the given task  \n\n\n### Perceptrons\n+ Linear Classifers (Binary Perceptrons)\n   + Input is a vector of feature values <#free: 2, your_name: 0, misspelled: 2 ...>\n   + We take the dot product of this vector with our vector which has weights corresponding to each vector <#free:4, your_name:-1, misspelled:1 ... >\n   + If dot product is positive then output +1, else we output -1\n   + It is our job to learn this weight vector\n      + We begin with weight vector with all 0s\n      + If we misclassify, then we update weight vector $w = w + (y' * f)$, where $y'$ is correct label and f is curr weight in example\n\n+ MultiClass Classifiers\n   + We have a weight vector $w_y$ for each classification\n   + We score each classification by $w_y * f(x)$\n   + We predict by choosing the classification which yeilds the max score\n   + If we misclassify... \n       + lower score of wrong $w_y = w_y - f(x) $\n       + raise score of right $w_{y'} = w_{y'} + f(x) $ \n\n+ Properties of Perceptrons\n   + Seperability: true if some parameters get training set perfectly correct (basically says you can perfectly classify into unique buckets) occurs in some cases\n   + Convergence: if training is seperable, then perceptron will eventually converge\n   + mistake bound: $ mistake < k / /sigma ^2 $ if not seperable then we can bound by the expression prior\n\n+ Problems with Perceptrons\n   + Noise: if data isn't seperable then weights might thrash back and forth, it helps to average weights of perceptron over time to prevent this\n   + Overtraining can occur\n   + Mediocre Generalizaiton - create seperating solution (works for testing data), but a better seperating solution exists\n\n### Improvements to Perceptrons and SVM\n+ Idea: adjust weight update to mitigate the negative effects, weight variable is tau $\tau$ (MIRA)\n+ $\tau = ((w_y' - w_{y*}')*f + 1) / (2f * f) $\n+ $ w_y = w_y' - \tau * f(x) $\n+ Cause perceptron to converge faster, evade the noise\n\n+ Support Vector Machines - good for dealing with medoicre generalization. Allows you to obtain best possible seperating solution.\n+ Non-Linear Separators - if unable to seperate data linearly can seperate in higher dimensions, i.e. squaring input data and then seperating\n \n\n## Module 12 Definitions\n* **Concept** - definition\n\n\n# Module 13: Neural Networks\n## SLP Chapter 5.1 Classification: the sigmoid\n Your summary here \n\n## SLP Chapter 5.2 Learning in Logistic Regression\n Your summary here \n\n## SLP Chapter 5.3 The cross-entropy loss function\n Your summary here \n\n## SLP Chapter 5.4 Gradient Descent\n Your summary here \n\n## SLP Chapter 5.5 Regularization\n Your summary here \n\n## SLP Chapter 5.6 Multinomial logistic regression\n Your summary here \n\n## SLP Chapter 7.1 Units\n Your summary here \n\n## SLP Chapter 7.2 The XOR problem\n Your summary here \n\n## SLP Chapter 7.3 Feedforward Neural Networks\n Your summary here \n\n## SLP Chapter 7.4 Feedforward networks for NLP: Classification\n Your summary here \n\n## SLP Chapter 7.5 Feedforward Neural Language Modeling\n Your summary here \n\n## SLP Chapter 7.6 Training Neural Nets\n Your summary here \n\n## SLP Chapter 7.7 Training the neural language model\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n### Logistic Regression\n\nClassifier Components\n+ train a corpus of M observations in input output pairs $(x^{(i)}, y^{(i)})$\n+ we need to transform this into feature representation\n+ wee need to take a feature represenetation as an input to a function with classification as the output via a probability distribution\n+ we need of method of \"how good\" the curreent classification function is, calleed objectivee fun (or loss fun)\n+ optimization routine, how to adjust to minimize loss\n\nSentiment Classifier\n+ take text -> features -> output. label + or - \n+ logistic regression solves this by learning from a training seet, witgh weights and a bias term \n+ $z = \\sum_i w_ix_i + b$ (dot product of z and w + b)\n+ z is unbounded\n+ MAIN CHANGE FROM PRECEPTRONS : Z SQUISHED TO BETWEEN 0 AND 1\n+ $ y = \\frac{1}{1 + e^{-z}}$ sigmoid function, where $z = w \\cdot x + b$\n+ decision boundary : naturally falls at 0.5\n+ how do we extract features from raw text input??\n  + in NLP, define the amount of features in. thee text \n  + x1 = number of positive lexicon words in the review\n  + x2 = count of negativee lexicon words\n  + x3 = does no appear? \n  + x4 = number of. first and second person pronouns\n  + x5 = does ! appear\n  + x6 log of the word count \n  + weights?? can be given, can be learned\n\nLearning in Logistic Regression\n+ learn the weights and the bias term with loss function and optimization routine\n\n\n\n\n\n### Loss Functions\nMean Squared error: \n$L_{MSE}(\\hat{y}, y) = \\frac{1}{2} (\\hat{y}-y)^2$\n\nCross entropy loss: find a type of maximum likelihood estimator, choose params w, b that maximize the probability that we get the true label\n\n+ maximie the probability of the correct label $p(y|x) = \\hat{y}^y(1-\\hat{y})^{1-y}$\n+ why is this the function, y = 1 or y = 0 os the exponent tells us which part of the equation matters\n+ if y is 1, we try to maximize y hat, if y is 0 wee try to maximize 1 - y hat\n+ take the log of both sides $log(p(y|x)) = log(\\hat{y}^y(1-\\hat{y})^{1-y}) = y log(\\hat{y}) + (1-y) log(1-\\hat{y})$ where $\\hat{y} = \\sigma(w \\cdot x + b)$\n+ finally $L_{CE} = - [y log(\\sigma(w \\cdot x + b)) + (1-y) log(1-\\sigma(w \\cdot x + b))$]$ (flip sign to maximize a negative, minimize loss )\n+ correct: lowerr, incorrect: higher\n+ Total loss is sum of all of the losses (since we work in log space )\n\nFinding good parameters - Gradient Descent:\n+ argmin average loss\n+ gradient descent is to figure out for each of our weights, what direction should we  movee in (inc or dec) to lower loss\n+ find the most extreme downward slope\n+ convex optimization (loss is convex (global minimum))\n  + non convex is a much harder problem to solve \n  + define a step size that is the same as the learning rate $\\eta$ \"eta\"\n  + to get slope, derivativee if the loss function\n  + $\\frac{\\delta L_{CE}(w,b)}{\\delta w_j} = [\\sigma(w \\cdot x + b) - y]x_j\n  + difference between the true label and our eextimate times thee corresponding value of that feature\n\n### Stochastic Gradient Descent \n+ we have N weights, for each of the weieghts in the weight vector, how much should we updatee it and in what direction??\n+ what are the derivatives if the loss with respect to each weight compared to the true value\n+ $\\delta w_iL(f(x, \\theta), y)$ in a vector of length n COPY THESE EQS FROM THE SLIDEES\n+ $\\theta_{t+1} = \\theta_t\n\nThe Gradient\n+ tot update $\\theta$\n+  $L_{CE} = - [y log(\\hat{y}) + (1-y) log(1-\\hat{y})$]$\n+ derivative if this for one observation x and a single weight is :\n  + $ \\frac{\\delta L_{CE}(\\hat{y),y)}{\\deltaw_j} = [\\hat{y-y}]x_j$\n  + the derivative of the loss with respect to a single input and a single weight is the difference of the prediction and the actual value times the value xj\n+ COPY QS FROM SLIDES\n+ the gradient is take what we had before and add it up \n+ $ \\frac{\\delta L_{CE}(\\hat{y),y)}{\\deltaw_j} = [\\hat{y-y}]x_j$\n\nThe Stochastic Gradient Descent Algorithm\n+ initialize all weights to be zeros \n+ iterate some numsbe of times \n+ grab some item in random order xi, yi\n+ use classifier to. say what is the estimate y. hat\n+ compute loss by comparing y hat to y\n+ compute the gradienr and store it in the vector \n+ update the weights by subtracting out learning rate times gradient vector \n\nExample\n+ sentiment classification, + or -\n+ 2 features, 1 is count of num positive features, 2 is count of number of. negative words \n+ three weights, the two counts and the bias\n+ set all weights to zero intially\n+ select xi, yi (you have an input vector p = 3, n = 2, b = 1) yi = 1 (positive)\n+ $\\theta_1 = [0, 0, 0]$\n+ learning rate $\\eta = 0.1$\n+ $\\theta_2 = \\theta_1 - \\eta \\nabla_\\theta L(f(x^1, \\theta_1), y^1)$\n\n\nBatching \n+ we usually batch a bunch of items together for batch training \n+ usually, we do mini batch training group items together, update for that batch, and continue\n+ we usually pick this based on GPU memory constraints \n\nRegularization\n+ overfitting solution, adding penalty into the loss function that stop weights from getting too large \n+ we do this using some potential terms \n  + L1 is a linear function on the weights similar to manhattan distance \n  + L2 is a quadratic function uses the square of the l2 norm (euclidian distance) usually easier because of continuous derviative\n+ main goal is keep weight values small\n\nMultinomial Logisitc Regression\n+ what if we care about a problem with more than just binary classification\n+ ie positive, negative, neutral sentiment\n+ softmax takes an input vector and outputs a vector of values normalized into probabilities\n+ this can be interpreted as a probability distrubution on multiple classes \n\n### Neural Networks \n+ biological inspiration preceptron in the 1950s\n  + take inputs ansd assign them weights and if we sum the product of inputs and weights with an activation function we make a decision\n  + just like the human neuron (many inputs, one neuron, one output)\n  + in our brain, we have a lot of interconnected neurons\n+ everything is interconnected \n+ output of one neuron can be an input to other neurons \n+ feed-forward neural network architecture\n  + incoming arcts are inputs, ourgoing arcs are transmissions\n  + input layer, hidden layers (we do not directly observe), and an output layer\n  + training is more complicated, there are several layers that we do not see\n  + no need for feature engineering, the whole input raw is filtered thru using hidden layers\n  + tradeoff: time spent picking the right architechture/model \n\n\nSigmoid Neurons\n+ a small change in one of the weight values represents a small change in the resulting output\n+ z = xw+b, $\\sigma = e^{-z}$\n\nActivation Functions \n+ sigmoid is one of these,  but there are a lof of different ones that we can use \n+ three most used\n  + sigmoid (s curve)\n  + tangent (s curve)\n  + reLU (0 and then linear)\n\nFeed-Forward Neural Network\n+ simplest kind, fully connected (each item is connected to every other item in the next layer)\n+ multilayer, no cycles\n+ layer 0 is input layer, final layer is output layer, anything in between is hidden layer\n+ three steps per layer \n  + w * x\n  + add in bias b \n  + apply the activation function to it \n  + difference from logistic regression (change the dot product to a matrix multiply (singe every element in the layer has a weight vector))\n\n  + each nerual unit is a logistic regression classifier\n+ if this is the final layer, stick itinto a softmax function that gives us a distrubution over \n\nTraining Neural Nets \n+ how do we attribute errors? (in logistic regression it was a simple derivative)\n+ we need a loss function (reuse $L_{CE}$), an optimization algorithm (reuse stochastic gradient descent), gradient to update (NEW) \n\n\nComputing the gradient\n+ the simple derviativesonly giveoutput for the last layer\n+ we must lopok back through all previous layers even though loss can only be computed at the final layer\n+ error backpropogation algorithm\n  + backward differentiation, what are the components of a function that I am trying to derive\n  + graph the steps in the computation\n  + computing the answeer is called a forward pass(start at inputs, compute everything, compute loss at the end )\n  + how do wee compute derivatives from this? how much does each step cotribute to final answer\n    + use chain rule!\n    + derivative of l with respect to each of the inputs using the chain rule on all of the intermediate steps\n    + do the backward pass to compute the partial derivatives (using the computer values from the forward pass)\n\n\n\n\n\n\n\n\n\n\n \n\n## Module 13 Definitions\n* **Concept** - definition\n\n\n# Module 14: Natural Language Processing\n## SLP Chapter 9.1 Language Models Revisited\n Your summary here \n\n## SLP Chapter 9.2 Recurrent Neural Networks\n Your summary here \n\n## SLP Chapter 9.3 RNNs as Language Models\n Your summary here \n\n## SLP Chapter 6.1 Lexical Semantics\n Your summary here \n\n## SLP Chapter 6.2 Vector Semantics\n Your summary here \n\n## SLP Chapter 6.3 Words and Vectors\n Your summary here \n\n## SLP Chapter 6.4 Cosine for measuring similarity\n Your summary here \n\n## SLP Chapter 6.8 Word2vec\n Your summary here \n\n## SLP Chapter 6.10 Semantic properties of embeddings\n Your summary here \n\n## SLP Chapter 6.11 Bias and Embeddings\n Your summary here \n\n## SLP Chapter 6.12 Evaluating Vector Models\n Your summary here \n\n## Module 13 Lecture Notes\n \n\n#### Natural Language Processing\n\n### Intro\n+ Goal: Have machines communicate with words like a human would\n+ Vector Space Models - every word is representing as vector, where vector \n+ represents properties of that word.\n+ Sometimes these models end up with racism or sexism, as a result of being \n+ trained on this type of data\n\n### Natural Language Models\n+ Estimating probability of next word given previous x words\n+ Estimate probability of sentence consisting of word sequence $w_{1:n}$\n\n\n+ What happens if a certain 'next word' example was not seen in training data?\n   + Then we laplace smooth the data such that the probability of the word occuring \n   + is non-negative.\n\n+Neural Language Models Advantages\n   + Don't need smoothing\n   + They can handle much longer histories\n   + They can generalize over contexts of similar words\n   + Neural LMs tend to have much higher predictive accuracy than n-gram LMs\n\n+ Because we are creating vector for each word, it is easy to compare words for similarity\n+ by comparing their vectors.\n+ Express joint probability of word sequence in terms of the word vectors for the words in that sequence \n+ Simaltaneously learn the word vectors are the parameters of the function\n\n+ More on neural LMs\n   + Input - k-gram of words $w_{1:k} $\n   + Output - probability distribution over the next word\n   + On Input \n      + Start with one-hot vectors (binary vector only one non-zero term represents the word)\n      + Then the projection layer where a d-dimensional vector gives actual weights that we learn for each word\n      + Then the hidden layer where the previous k words are analyzed based on their order\n      + Ultimately the output layer which gives us the probability of each word in our vocab\n      + being the next word - we take the largest probability.\n+ Probability tables: give us probability of next table given previously queried x previous words\n\n\n### Lexical Semantic Models\n+ Broadly speaking this is putting logic into a word model to generate conclusions\n\n+ How do we represent the meaning of a word\n+ LMs represent words as a string of letters, but we ideally want meaning to encode\n   + Synonyms\n   + Anyonyms\n   + Connotations\n   + Semantic Roles\n   + Support for entailment (dog exists within animal), allows us to apply  logic to language\n\n### Vector Semantic Models 1\n+ Each word is representing as a point in vector space\n+ Words close to one another are semantically similar\n+ Compare vectors to get this similarity\n+ Takes advantage of the fact that though most words don't have synonms that words\n+ are similar to one another\n+ I.E. tall and high are similar to one another\n\n+ Distributional Hypothesis of Language\n   + optometrist and eye-doctor share many uttterance environments\n   + information retrieval: given input turn into vector find similar vector in our corpus of words \n   + Term Document matrix: allows you to find similar documents or similar words (depending on col or row)\n        + If we want to compare words we can take two documents and say three words\n        + We can take the values at (word, document) within or Term-Document matrix and make\n        + an (x,y) point in 2D space for each word, we can than compare the euclidian\n        + distance of these words to compare their similarity\n\n        + We can normalize these values by squaring the (word, document) value for each word taking the square root and then normalizing\n        + on the scale of 0 to 1, this brings these words closer together graphically\n        + Can also take cosine distance between these words in x-y space to find similarity\n\n### Vector Semantic Models 2\n\n+ Term-by-Term Matrix: every word is both a row and column vector\n   + cell - represnets how often a word appears in a context window surrounding other word\n   + context window - words adjacent to our current word (by k words) \n\n+ Language tends to have a long distance dependency\n   + The pictures ARE beatiful\n   + The pictures of the old man ARE beatiful\n\n+ Raw word frequency is not always a great measure of association between words\n   + Can be skered to \"of\" and \"the\"\n   + We want to have a measure of whetehr context word is informative of target word\n   + We can do TF-IDF: Term Frequency * inverse document frequency\n   + Equivilant to (how often word occurs in document) * (1 over the number of documents that it occured in)\n\n\n### Word Embeddings\n+ We have talked about words in large sparse matricies thus far\n+ Alernative is short and dense vectors\n\n+How do we get dense vectors? Train a classifier\n   + Treat target word and a neighboring context word as positive examples\n   + Randomly sample other words in lexicon to get negative examples\n   + Use logistic regression to train a classifier to distinguish the two cases\n   + Use the weights as the embeddings\n   + If we build model for 'apricot' and there is example 'tablesppon of apricot preserves or ...'\n   + then we want these surrounding words to be high\n   + then we choose random samples (not including the word apricot), we want those words to be low\n+ This entire process is called Word2Vec\n+ It is fast and easy to train\n+ Sometimes these embeddings capture relational meanings \n   + Unle -> Aunt\n   + King -> Queen\n\n \n\n## Module 14 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZzMQW6y1_WK1"
      },
      "source": [
        ""
      ],
      "execution_count": 18,
      "outputs": []
    }
  ]
}